1#
2# directory.py
3#
4# This source file is part of the FoundationDB open source project
5#
6# Copyright 2013-2018 Apple Inc. and the FoundationDB project authors
7#
8# Licensed under the Apache License, Version 2.0 (the "License");
9# you may not use this file except in compliance with the License.
10# You may obtain a copy of the License at
11#
12#     http://www.apache.org/licenses/LICENSE-2.0
13#
14# Unless required by applicable law or agreed to in writing, software
15# distributed under the License is distributed on an "AS IS" BASIS,
16# WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
17# See the License for the specific language governing permissions and
18# limitations under the License.
19#
20
21import random
22
23import fdb
24
25from bindingtester import FDB_API_VERSION
26from bindingtester import util
27
28from bindingtester.tests import Test, Instruction, InstructionSet, ResultSpecification
29from bindingtester.tests import test_util, directory_util
30
31from bindingtester.tests.directory_state_tree import DirectoryStateTreeNode
32
33fdb.api_version(FDB_API_VERSION)
34
35
36class DirectoryTest(Test):
37
38    def __init__(self, subspace):
39        super(DirectoryTest, self).__init__(subspace)
40        self.stack_subspace = subspace['stack']
41        self.directory_log = subspace['directory_log']['directory']
42        self.subspace_log = subspace['directory_log']['subspace']
43        self.prefix_log = subspace['prefix_log']
44
45        self.prepopulated_dirs = []
46        self.next_path = 1
47
48    def ensure_default_directory_subspace(self, instructions, path):
49        directory_util.create_default_directory_subspace(instructions, path, self.random)
50
51        child = self.root.add_child(path, DirectoryStateTreeNode(True, True, has_known_prefix=True))
52        self.dir_list.append(child)
53        self.dir_index = directory_util.DEFAULT_DIRECTORY_INDEX
54
55    def generate_layer(self):
56        if random.random() < 0.7:
57            return ''
58        else:
59            choice = random.randint(0, 3)
60            if choice == 0:
61                return 'partition'
62            elif choice == 1:
63                return 'test_layer'
64            else:
65                return self.random.random_string(random.randint(0, 5))
66
67    def setup(self, args):
68        self.dir_index = 0
69        self.random = test_util.RandomGenerator(args.max_int_bits, args.api_version, args.types)
70
71    def generate(self, args, thread_number):
72        instructions = InstructionSet()
73
74        op_choices = ['NEW_TRANSACTION', 'COMMIT']
75
76        general = ['DIRECTORY_CREATE_SUBSPACE', 'DIRECTORY_CREATE_LAYER']
77
78        op_choices += general
79
80        directory_mutations = ['DIRECTORY_CREATE_OR_OPEN', 'DIRECTORY_CREATE', 'DIRECTORY_MOVE', 'DIRECTORY_MOVE_TO',
81                               'DIRECTORY_REMOVE', 'DIRECTORY_REMOVE_IF_EXISTS']
82        directory_reads = ['DIRECTORY_EXISTS', 'DIRECTORY_OPEN', 'DIRECTORY_LIST']
83
84        directory_db_mutations = [x + '_DATABASE' for x in directory_mutations]
85        directory_db_reads = [x + '_DATABASE' for x in directory_reads]
86        directory_snapshot_reads = [x + '_SNAPSHOT' for x in directory_reads]
87
88        directory = []
89        directory += directory_mutations
90        directory += directory_reads
91        directory += directory_db_mutations
92        directory += directory_db_reads
93
94        if not args.no_directory_snapshot_ops:
95            directory += directory_snapshot_reads
96
97        subspace = ['DIRECTORY_PACK_KEY', 'DIRECTORY_UNPACK_KEY', 'DIRECTORY_RANGE', 'DIRECTORY_CONTAINS', 'DIRECTORY_OPEN_SUBSPACE']
98
99        instructions.append('NEW_TRANSACTION')
100
101        default_path = unicode('default%d' % self.next_path)
102        self.next_path += 1
103        self.dir_list = directory_util.setup_directories(instructions, default_path, self.random)
104        self.root = self.dir_list[0]
105
106        instructions.push_args(0)
107        instructions.append('DIRECTORY_CHANGE')
108
109        # Generate some directories that we are going to create in advance. This tests that other bindings
110        # are compatible with the Python implementation
111        self.prepopulated_dirs = [(generate_path(min_length=1), self.generate_layer()) for i in range(5)]
112
113        for path, layer in self.prepopulated_dirs:
114            instructions.push_args(layer)
115            instructions.push_args(*test_util.with_length(path))
116            instructions.append('DIRECTORY_OPEN')
117            self.dir_list.append(self.root.add_child(path, DirectoryStateTreeNode(True, True, has_known_prefix=False, is_partition=(layer=='partition'))))
118            # print('%d. Selected %s, dir=%s, dir_id=%s, has_known_prefix=%s, dir_list_len=%d' \
119            #       % (len(instructions), 'DIRECTORY_OPEN', repr(self.dir_index), self.dir_list[-1].dir_id, False, len(self.dir_list)-1))
120
121        instructions.setup_complete()
122
123        for i in range(args.num_ops):
124            if random.random() < 0.5:
125                while True:
126                    self.dir_index = random.randrange(0, len(self.dir_list))
127                    if not self.dir_list[self.dir_index].state.is_partition or not self.dir_list[self.dir_index].state.deleted:
128                        break
129
130                instructions.push_args(self.dir_index)
131                instructions.append('DIRECTORY_CHANGE')
132
133            dir_entry = self.dir_list[self.dir_index]
134
135            choices = op_choices[:]
136            if dir_entry.state.is_directory:
137                choices += directory
138            if dir_entry.state.is_subspace:
139                choices += subspace
140
141            op = random.choice(choices)
142
143            # print('%d. Selected %s, dir=%d, dir_id=%d, has_known_prefix=%d, dir_list_len=%d' \
144            #       % (len(instructions), op, self.dir_index, dir_entry.dir_id, dir_entry.state.has_known_prefix, len(self.dir_list)))
145
146            if op.endswith('_DATABASE') or op.endswith('_SNAPSHOT'):
147                root_op = op[0:-9]
148            else:
149                root_op = op
150
151            if root_op == 'NEW_TRANSACTION':
152                instructions.append(op)
153
154            elif root_op == 'COMMIT':
155                test_util.blocking_commit(instructions)
156
157            elif root_op == 'DIRECTORY_CREATE_SUBSPACE':
158                path = generate_path()
159                instructions.push_args(generate_prefix(require_unique=False, is_partition=True))
160                instructions.push_args(*test_util.with_length(path))
161                instructions.append(op)
162                self.dir_list.append(DirectoryStateTreeNode(False, True, has_known_prefix=True))
163
164            elif root_op == 'DIRECTORY_CREATE_LAYER':
165                indices = []
166
167                prefixes = [generate_prefix(require_unique=args.concurrency==1, is_partition=True) for i in range(2)]
168                for i in range(2):
169                    instructions.push_args(prefixes[i])
170                    instructions.push_args(*test_util.with_length(generate_path()))
171                    instructions.append('DIRECTORY_CREATE_SUBSPACE')
172                    indices.append(len(self.dir_list))
173                    self.dir_list.append(DirectoryStateTreeNode(False, True, has_known_prefix=True))
174
175                instructions.push_args(random.choice([0, 1]))
176                instructions.push_args(*indices)
177                instructions.append(op)
178                self.dir_list.append(DirectoryStateTreeNode.get_layer(prefixes[0]))
179
180            elif root_op == 'DIRECTORY_CREATE_OR_OPEN':
181                # Because allocated prefixes are non-deterministic, we cannot have overlapping
182                # transactions that allocate/remove these prefixes in a comparison test
183                if op.endswith('_DATABASE') and args.concurrency == 1:
184                    test_util.blocking_commit(instructions)
185
186                path = generate_path()
187                op_args = test_util.with_length(path) + (self.generate_layer(),)
188                directory_util.push_instruction_and_record_prefix(instructions, op, op_args, path, len(self.dir_list), self.random, self.prefix_log)
189
190                if not op.endswith('_DATABASE') and args.concurrency == 1:
191                    test_util.blocking_commit(instructions)
192
193                child_entry = dir_entry.get_descendent(path)
194                if child_entry is None:
195                    child_entry = DirectoryStateTreeNode(True, True)
196
197                child_entry.state.has_known_prefix = False
198                self.dir_list.append(dir_entry.add_child(path, child_entry))
199
200            elif root_op == 'DIRECTORY_CREATE':
201                layer = self.generate_layer()
202                is_partition = layer == 'partition'
203
204                prefix = generate_prefix(require_unique=is_partition and args.concurrency==1, is_partition=is_partition, min_length=0)
205
206                # Because allocated prefixes are non-deterministic, we cannot have overlapping
207                # transactions that allocate/remove these prefixes in a comparison test
208                if op.endswith('_DATABASE') and args.concurrency == 1:  # and allow_empty_prefix:
209                    test_util.blocking_commit(instructions)
210
211                path = generate_path()
212                op_args = test_util.with_length(path) + (layer, prefix)
213                if prefix is None:
214                    directory_util.push_instruction_and_record_prefix(
215                        instructions, op, op_args, path, len(self.dir_list), self.random, self.prefix_log)
216                else:
217                    instructions.push_args(*op_args)
218                    instructions.append(op)
219
220                if not op.endswith('_DATABASE') and args.concurrency == 1:  # and allow_empty_prefix:
221                    test_util.blocking_commit(instructions)
222
223                child_entry = dir_entry.get_descendent(path)
224                if child_entry is None:
225                    child_entry = DirectoryStateTreeNode(True, True, has_known_prefix=bool(prefix))
226                elif not bool(prefix):
227                    child_entry.state.has_known_prefix = False
228
229                if is_partition:
230                    child_entry.state.is_partition = True
231
232                self.dir_list.append(dir_entry.add_child(path, child_entry))
233
234            elif root_op == 'DIRECTORY_OPEN':
235                path = generate_path()
236                instructions.push_args(self.generate_layer())
237                instructions.push_args(*test_util.with_length(path))
238                instructions.append(op)
239
240                child_entry = dir_entry.get_descendent(path)
241                if child_entry is None:
242                    self.dir_list.append(DirectoryStateTreeNode(False, False, has_known_prefix=False))
243                else:
244                    self.dir_list.append(dir_entry.add_child(path, child_entry))
245
246            elif root_op == 'DIRECTORY_MOVE':
247                old_path = generate_path()
248                new_path = generate_path()
249                instructions.push_args(*(test_util.with_length(old_path) + test_util.with_length(new_path)))
250                instructions.append(op)
251
252                child_entry = dir_entry.get_descendent(old_path)
253                if child_entry is None:
254                    self.dir_list.append(DirectoryStateTreeNode(False, False, has_known_prefix=False))
255                else:
256                    self.dir_list.append(dir_entry.add_child(new_path, child_entry))
257
258                # Make sure that the default directory subspace still exists after moving the specified directory
259                if dir_entry.state.is_directory and not dir_entry.state.is_subspace and old_path == (u'',):
260                    self.ensure_default_directory_subspace(instructions, default_path)
261
262            elif root_op == 'DIRECTORY_MOVE_TO':
263                new_path = generate_path()
264                instructions.push_args(*test_util.with_length(new_path))
265                instructions.append(op)
266
267                child_entry = dir_entry.get_descendent(())
268                if child_entry is None:
269                    self.dir_list.append(DirectoryStateTreeNode(False, False, has_known_prefix=False))
270                else:
271                    self.dir_list.append(dir_entry.add_child(new_path, child_entry))
272
273                # Make sure that the default directory subspace still exists after moving the current directory
274                self.ensure_default_directory_subspace(instructions, default_path)
275
276            elif root_op == 'DIRECTORY_REMOVE' or root_op == 'DIRECTORY_REMOVE_IF_EXISTS':
277                # Because allocated prefixes are non-deterministic, we cannot have overlapping
278                # transactions that allocate/remove these prefixes in a comparison test
279                if op.endswith('_DATABASE') and args.concurrency == 1:
280                    test_util.blocking_commit(instructions)
281
282                path = ()
283                count = random.randint(0, 1)
284                if count == 1:
285                    path = generate_path()
286                    instructions.push_args(*test_util.with_length(path))
287
288                instructions.push_args(count)
289                instructions.append(op)
290
291                dir_entry.delete(path)
292
293                # Make sure that the default directory subspace still exists after removing the specified directory
294                if path == () or (dir_entry.state.is_directory and not dir_entry.state.is_subspace and path == (u'',)):
295                    self.ensure_default_directory_subspace(instructions, default_path)
296
297            elif root_op == 'DIRECTORY_LIST' or root_op == 'DIRECTORY_EXISTS':
298                path = ()
299                count = random.randint(0, 1)
300                if count == 1:
301                    path = generate_path()
302                    instructions.push_args(*test_util.with_length(path))
303                instructions.push_args(count)
304                instructions.append(op)
305
306            elif root_op == 'DIRECTORY_PACK_KEY':
307                t = self.random.random_tuple(5)
308                instructions.push_args(*test_util.with_length(t))
309                instructions.append(op)
310                instructions.append('DIRECTORY_STRIP_PREFIX')
311
312            elif root_op == 'DIRECTORY_UNPACK_KEY' or root_op == 'DIRECTORY_CONTAINS':
313                if not dir_entry.state.has_known_prefix or random.random() < 0.2 or root_op == 'DIRECTORY_UNPACK_KEY':
314                    t = self.random.random_tuple(5)
315                    instructions.push_args(*test_util.with_length(t))
316                    instructions.append('DIRECTORY_PACK_KEY')
317                    instructions.append(op)
318                else:
319                    instructions.push_args(fdb.tuple.pack(self.random.random_tuple(5)))
320                    instructions.append(op)
321
322            elif root_op == 'DIRECTORY_RANGE' or root_op == 'DIRECTORY_OPEN_SUBSPACE':
323                t = self.random.random_tuple(5)
324                instructions.push_args(*test_util.with_length(t))
325                instructions.append(op)
326                if root_op == 'DIRECTORY_OPEN_SUBSPACE':
327                    self.dir_list.append(DirectoryStateTreeNode(False, True, dir_entry.state.has_known_prefix))
328                else:
329                    test_util.to_front(instructions, 1)
330                    instructions.append('DIRECTORY_STRIP_PREFIX')
331                    test_util.to_front(instructions, 1)
332                    instructions.append('DIRECTORY_STRIP_PREFIX')
333
334        instructions.begin_finalization()
335
336        test_util.blocking_commit(instructions)
337
338        instructions.append('NEW_TRANSACTION')
339
340        for i, dir_entry in enumerate(self.dir_list):
341            instructions.push_args(i)
342            instructions.append('DIRECTORY_CHANGE')
343            if dir_entry.state.is_directory:
344                instructions.push_args(self.directory_log.key())
345                instructions.append('DIRECTORY_LOG_DIRECTORY')
346            if dir_entry.state.has_known_prefix and dir_entry.state.is_subspace:
347                # print('%d. Logging subspace: %d' % (i, dir_entry.dir_id))
348                instructions.push_args(self.subspace_log.key())
349                instructions.append('DIRECTORY_LOG_SUBSPACE')
350            if (i + 1) % 100 == 0:
351                test_util.blocking_commit(instructions)
352
353        test_util.blocking_commit(instructions)
354
355        instructions.push_args(self.stack_subspace.key())
356        instructions.append('LOG_STACK')
357
358        test_util.blocking_commit(instructions)
359        return instructions
360
361    def pre_run(self, db, args):
362        for (path, layer) in self.prepopulated_dirs:
363            try:
364                util.get_logger().debug('Prepopulating directory: %r (layer=%r)' % (path, layer))
365                fdb.directory.create_or_open(db, path, layer)
366            except Exception as e:
367                util.get_logger().debug('Could not create directory %r: %r' % (path, e))
368                pass
369
370    def validate(self, db, args):
371        errors = []
372        # This check doesn't work in the current test because of the way we use partitions.
373        # If a partition is created, allocates a prefix, and then is removed, subsequent prefix
374        # allocations could collide with prior ones. We can get around this by not allowing
375        # a removed directory (or partition) to be used, but that weakens the test in another way.
376        # errors += directory_util.check_for_duplicate_prefixes(db, self.prefix_log)
377        return errors
378
379    def get_result_specifications(self):
380        return [
381            ResultSpecification(self.stack_subspace, key_start_index=1, ordering_index=1, global_error_filter=[1007, 1021]),
382            ResultSpecification(self.directory_log, ordering_index=0),
383            ResultSpecification(self.subspace_log, ordering_index=0)
384        ]
385
386
387# Utility functions
388
389
390def generate_path(min_length=0):
391    length = int(random.random() * random.random() * (4 - min_length)) + min_length
392    path = ()
393    for i in range(length):
394        if random.random() < 0.05:
395            path = path + (u'',)
396        else:
397            path = path + (random.choice([u'1', u'2', u'3']),)
398
399    return path
400
401
402def generate_prefix(require_unique=False, is_partition=False, min_length=1):
403    fixed_prefix = 'abcdefg'
404    if not require_unique and min_length == 0 and random.random() < 0.8:
405        return None
406    elif require_unique or is_partition or min_length > len(fixed_prefix) or random.random() < 0.5:
407        if require_unique:
408            min_length = max(min_length, 16)
409
410        length = random.randint(min_length, min_length+5)
411        if length == 0:
412            return ''
413
414        if not is_partition:
415            first = chr(random.randint(ord('\x1d'), 255) % 255)
416            return first + ''.join(chr(random.randrange(0, 256)) for i in range(0, length - 1))
417        else:
418            return ''.join(chr(random.randrange(ord('\x02'), ord('\x14'))) for i in range(0, length))
419    else:
420        prefix = fixed_prefix
421        generated = prefix[0:random.randrange(min_length, len(prefix))]
422        return generated
423