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