1 /* 2 * Copyright 2001-2015, Axel Dörfler, axeld@pinc-software.de. 3 * This file may be used under the terms of the MIT License. 4 */ 5 6 7 //! BFS B+Tree torture test 8 9 10 #include <set> 11 #include <string> 12 13 #include <ctype.h> 14 #include <stdio.h> 15 #include <stdlib.h> 16 #include <string.h> 17 #include <sys/stat.h> 18 19 #include <List.h> 20 21 #include "BPlusTree.h" 22 #include "Inode.h" 23 #include "Volume.h" 24 25 26 #define DEFAULT_ITERATIONS 10 27 #define DEFAULT_NUM_KEYS 100 28 #define DEFAULT_KEY_TYPE S_STR_INDEX 29 30 #define MIN_STRING 3 31 #define MAX_STRING 256 32 33 struct key { 34 void* data; 35 uint32 length; 36 int32 in; 37 int32 count; 38 off_t value; 39 }; 40 41 key* gKeys; 42 int32 gNum = DEFAULT_NUM_KEYS; 43 int32 gType = DEFAULT_KEY_TYPE; 44 int32 gTreeCount = 0; 45 bool gVerbose, gExcessive; 46 int32 gIterations = DEFAULT_ITERATIONS; 47 int32 gHard = 1; 48 Volume* gVolume; 49 int32 gSeed = 42; 50 51 // from cache.cpp (yes, we are that mean) 52 extern BList gBlocks; 53 54 55 // prototypes 56 void bailOut(); 57 void bailOutWithKey(void* key, uint16 length); 58 void dumpTree(); 59 void dumpKey(void* key, int32 length); 60 void dumpKeys(); 61 62 63 void 64 dumpTree() 65 { 66 puts("\n*** Tree-Dump:\n"); 67 68 bplustree_header* header = (bplustree_header*)gBlocks.ItemAt(0); 69 dump_bplustree_header(header); 70 71 for (int32 i = 1; i < gBlocks.CountItems(); i++) { 72 bplustree_node* node = (bplustree_node*)gBlocks.ItemAt(i); 73 printf("\n--- %s node at %ld --------------------------------------\n", 74 node->overflow_link == BPLUSTREE_NULL ? "leaf" : "index", 75 i * BPLUSTREE_NODE_SIZE); 76 dump_bplustree_node(node, header, gVolume); 77 } 78 } 79 80 81 void 82 bailOut() 83 { 84 if (gVerbose) { 85 // dump the tree 86 dumpTree(); 87 } 88 89 // in any case, write the tree back to disk 90 shutdown_cache(gVolume->Device(), gVolume->BlockSize()); 91 exit(-1); 92 } 93 94 95 void 96 bailOutWithKey(void* key, uint16 length) 97 { 98 dumpKey(key, length); 99 putchar('\n'); 100 bailOut(); 101 } 102 103 104 void 105 dumpKey(void* key, int32 length) 106 { 107 switch (gType) { 108 case S_STR_INDEX: 109 printf("\"%s\" (%ld bytes)", (char*)key, length); 110 break; 111 case S_INT_INDEX: 112 printf("%ld", *(int32*)key); 113 break; 114 case S_UINT_INDEX: 115 printf("%lu", *(uint32*)key); 116 break; 117 case S_LONG_LONG_INDEX: 118 printf("%Ld", *(int64*)key); 119 break; 120 case S_ULONG_LONG_INDEX: 121 printf("%Lu", *(uint64*)key); 122 break; 123 case S_FLOAT_INDEX: 124 printf("%g", *(float*)key); 125 break; 126 case S_DOUBLE_INDEX: 127 printf("%g", *(double*)key); 128 break; 129 } 130 if ((gType == S_INT_INDEX || gType == S_UINT_INDEX 131 || gType == S_FLOAT_INDEX) && length != 4) 132 printf(" (wrong length %ld)", length); 133 else if ((gType == S_LONG_LONG_INDEX || gType == S_ULONG_LONG_INDEX 134 || gType == S_DOUBLE_INDEX) && length != 8) 135 printf(" (wrong length %ld)", length); 136 } 137 138 139 void 140 dumpKeys() 141 { 142 const char* type; 143 switch (gType) { 144 case S_STR_INDEX: 145 type = "string"; 146 break; 147 case S_INT_INDEX: 148 type = "int32"; 149 break; 150 case S_UINT_INDEX: 151 type = "uint32"; 152 break; 153 case S_LONG_LONG_INDEX: 154 type = "int64"; 155 break; 156 case S_ULONG_LONG_INDEX: 157 type = "uint64"; 158 break; 159 case S_FLOAT_INDEX: 160 type = "float"; 161 break; 162 case S_DOUBLE_INDEX: 163 type = "double"; 164 break; 165 default: 166 debugger("unknown type in gType"); 167 return; 168 } 169 printf("Dumping %ld keys of type %s\n", gNum, type); 170 171 for (int32 i = 0; i < gNum; i++) { 172 printf("% 8ld. (%3ld) key = ", i, gKeys[i].in); 173 dumpKey(gKeys[i].data, gKeys[i].length); 174 putchar('\n'); 175 } 176 } 177 178 179 // #pragma mark - Key generation 180 181 182 void 183 generateName(int32 i, char* name, int32* _length) 184 { 185 int32 length = rand() % (MAX_STRING - MIN_STRING) + MIN_STRING; 186 for (int32 i = 0; i < length; i++) { 187 int32 c = int32(52.0 * rand() / RAND_MAX); 188 if (c >= 26) 189 name[i] = 'A' + c - 26; 190 else 191 name[i] = 'a' + c; 192 } 193 name[length] = 0; 194 *_length = length; 195 } 196 197 198 void 199 fillBuffer(void* buffer, int32 start) 200 { 201 for (int32 i = 0; i < gNum; i++) { 202 switch (gType) { 203 case S_INT_INDEX: 204 { 205 int32* array = (int32*)buffer; 206 array[i] = start + i; 207 break; 208 } 209 case S_UINT_INDEX: 210 { 211 uint32* array = (uint32*)buffer; 212 array[i] = start + i; 213 break; 214 } 215 case S_LONG_LONG_INDEX: 216 { 217 int64* array = (int64*)buffer; 218 array[i] = start + i; 219 break; 220 } 221 case S_ULONG_LONG_INDEX: 222 { 223 uint64* array = (uint64*)buffer; 224 array[i] = start + i; 225 break; 226 } 227 case S_FLOAT_INDEX: 228 { 229 float* array = (float*)buffer; 230 array[i] = start + i * 1.0001; 231 break; 232 } 233 case S_DOUBLE_INDEX: 234 { 235 double* array = (double*)buffer; 236 array[i] = start + i * 1.0001; 237 break; 238 } 239 } 240 gKeys[i].value = i; 241 } 242 } 243 244 245 status_t 246 createKeys() 247 { 248 gKeys = (key*)malloc(gNum * sizeof(key)); 249 if (gKeys == NULL) 250 return B_NO_MEMORY; 251 252 if (gType == S_STR_INDEX) { 253 std::set<std::string> set; 254 255 for (int32 i = 0; i < gNum; i++) { 256 char name[B_FILE_NAME_LENGTH]; 257 int32 length; 258 int32 tries = 0; 259 std::set<std::string>::const_iterator found; 260 261 // create unique keys! 262 while (tries++ < 100) { 263 generateName(i, name, &length); 264 found = set.find(string(name)); 265 if (found == set.end()) 266 break; 267 } 268 269 if (found != set.end()) { 270 printf("Couldn't create unique key list!\n"); 271 dumpKeys(); 272 bailOut(); 273 } 274 275 gKeys[i].data = malloc(length + 1); 276 memcpy(gKeys[i].data, name, length + 1); 277 gKeys[i].length = length; 278 gKeys[i].in = 0; 279 gKeys[i].count = 0; 280 gKeys[i].value = i; 281 set.insert(name); 282 } 283 } else { 284 int32 length; 285 int32 start = 0; 286 switch (gType) { 287 case S_FLOAT_INDEX: 288 case S_INT_INDEX: 289 start = -gNum / 2; 290 case S_UINT_INDEX: 291 length = 4; 292 break; 293 case S_DOUBLE_INDEX: 294 case S_LONG_LONG_INDEX: 295 start = -gNum / 2; 296 case S_ULONG_LONG_INDEX: 297 length = 8; 298 break; 299 default: 300 return B_BAD_VALUE; 301 } 302 uint8* buffer = (uint8*)malloc(length * gNum); 303 if (buffer == NULL) 304 return B_NO_MEMORY; 305 306 for (int32 i = 0; i < gNum; i++) { 307 gKeys[i].data = (void*)(buffer + i * length); 308 gKeys[i].length = length; 309 gKeys[i].in = 0; 310 gKeys[i].count = 0; 311 } 312 fillBuffer(buffer, start); 313 } 314 return B_OK; 315 } 316 317 318 // #pragma mark - Validity checker 319 320 321 void 322 checkTreeContents(BPlusTree* tree) 323 { 324 // reset counter 325 for (int32 i = 0; i < gNum; i++) 326 gKeys[i].count = 0; 327 328 TreeIterator iterator(tree); 329 char key[B_FILE_NAME_LENGTH]; 330 uint16 length; 331 uint16 duplicate; 332 off_t value; 333 status_t status; 334 while ((status = iterator.GetNextEntry(key, &length, B_FILE_NAME_LENGTH, 335 &value, &duplicate)) == B_OK) { 336 if (value < 0 || value >= gNum) { 337 iterator.Dump(); 338 printf("\ninvalid value %Ld in tree: ", value); 339 bailOutWithKey(key, length); 340 } 341 if (gKeys[value].value != value) { 342 iterator.Dump(); 343 printf("\nkey pointing to the wrong value %Ld (should be %Ld)\n", 344 value, gKeys[value].value); 345 bailOutWithKey(key, length); 346 } 347 if (length != gKeys[value].length 348 || memcmp(key, gKeys[value].data, length)) { 349 iterator.Dump(); 350 printf("\nkeys don't match (key index = %Ld, %ld times in tree, " 351 "%ld. occassion):\n\tfound: ", value, gKeys[value].in, 352 gKeys[value].count + 1); 353 dumpKey(key, length); 354 printf("\n\texpected: "); 355 dumpKey(gKeys[value].data, gKeys[value].length); 356 putchar('\n'); 357 bailOut(); 358 } 359 360 gKeys[value].count++; 361 } 362 if (status != B_ENTRY_NOT_FOUND) { 363 printf("TreeIterator::GetNext() returned: %s\n", strerror(status)); 364 iterator.Dump(); 365 bailOut(); 366 } 367 368 for (int32 i = 0; i < gNum; i++) { 369 if (gKeys[i].in != gKeys[i].count) { 370 printf("Key "); 371 dumpKey(gKeys[i].data, gKeys[i].length); 372 printf(" found only %ld from %ld\n", gKeys[i].count, gKeys[i].in); 373 bailOut(); 374 } 375 } 376 } 377 378 379 /*! Simple test, just seeks down to every key - if it's in and couldn't 380 be found or it's not in and can be found, something must be wrong 381 */ 382 void 383 checkTreeIntegrity(BPlusTree* tree) 384 { 385 TreeIterator iterator(tree); 386 for (int32 i = 0; i < gNum; i++) { 387 status_t status = iterator.Find((uint8*)gKeys[i].data, gKeys[i].length); 388 if (gKeys[i].in == 0) { 389 if (status == B_OK) { 390 printf("found key %" B_PRId32 " even though it's not in!\n", i); 391 bailOutWithKey(gKeys[i].data, gKeys[i].length); 392 } 393 } else if (status != B_OK) { 394 printf("TreeIterator::Find() returned: %s\n", strerror(status)); 395 bailOutWithKey(gKeys[i].data, gKeys[i].length); 396 } 397 } 398 } 399 400 401 void 402 checkTree(BPlusTree* tree) 403 { 404 if (!gExcessive) 405 printf("* Check tree...\n"); 406 407 checkTreeContents(tree); 408 checkTreeIntegrity(tree); 409 410 bool errorsFound = false; 411 tree->Validate(false, errorsFound); 412 if (errorsFound) { 413 printf("BPlusTree::Validate() found errors\n"); 414 bailOut(); 415 } 416 } 417 418 419 // #pragma mark - "Torture" functions 420 421 422 void 423 addAllKeys(Transaction& transaction, BPlusTree* tree) 424 { 425 printf("*** Adding all keys to the tree...\n"); 426 for (int32 i = 0; i < gNum; i++) { 427 status_t status = tree->Insert(transaction, (uint8*)gKeys[i].data, 428 gKeys[i].length, gKeys[i].value); 429 if (status != B_OK) { 430 printf("BPlusTree::Insert() returned: %s\n", strerror(status)); 431 printf("key: "); 432 bailOutWithKey(gKeys[i].data, gKeys[i].length); 433 } else { 434 gKeys[i].in++; 435 gTreeCount++; 436 } 437 } 438 checkTree(tree); 439 } 440 441 442 void 443 removeAllKeys(Transaction& transaction, BPlusTree* tree) 444 { 445 printf("*** Removing all keys from the tree...\n"); 446 for (int32 i = 0; i < gNum; i++) { 447 while (gKeys[i].in > 0) { 448 status_t status = tree->Remove(transaction, (uint8*)gKeys[i].data, 449 gKeys[i].length, gKeys[i].value); 450 if (status != B_OK) { 451 printf("BPlusTree::Remove() returned: %s\n", strerror(status)); 452 printf("key: "); 453 dumpKey(gKeys[i].data, gKeys[i].length); 454 putchar('\n'); 455 } else { 456 gKeys[i].in--; 457 gTreeCount--; 458 } 459 } 460 } 461 checkTree(tree); 462 463 } 464 465 466 void 467 duplicateTest(Transaction& transaction, BPlusTree* tree) 468 { 469 int32 index = int32(1.0 * gNum * rand() / RAND_MAX); 470 if (index == gNum) 471 index = gNum - 1; 472 473 printf("*** Duplicate test with key "); 474 dumpKey(gKeys[index].data, gKeys[index].length); 475 puts("..."); 476 477 status_t status; 478 479 int32 insertTotal = 0; 480 for (int32 i = 0; i < 8; i++) { 481 int32 insertCount = int32(1000.0 * rand() / RAND_MAX); 482 if (gVerbose) { 483 printf("* insert %ld to %ld old entries...\n", insertCount, 484 insertTotal + gKeys[index].in); 485 } 486 487 for (int32 j = 0; j < insertCount; j++) { 488 status = tree->Insert(transaction, (uint8*)gKeys[index].data, 489 gKeys[index].length, gKeys[index].value); 490 if (status != B_OK) { 491 printf("BPlusTree::Insert() returned: %s\n", strerror(status)); 492 bailOutWithKey(gKeys[index].data, gKeys[index].length); 493 } 494 insertTotal++; 495 gTreeCount++; 496 gKeys[index].in++; 497 498 if (gExcessive) 499 checkTree(tree); 500 } 501 502 int32 count; 503 if (i < 7) { 504 count = int32(1000.0 * rand() / RAND_MAX); 505 if (count > insertTotal) 506 count = insertTotal; 507 } else 508 count = insertTotal; 509 510 if (gVerbose) { 511 printf("* remove %ld from %ld entries...\n", count, 512 insertTotal + gKeys[index].in); 513 } 514 515 for (int32 j = 0; j < count; j++) { 516 status_t status = tree->Remove(transaction, 517 (uint8*)gKeys[index].data, gKeys[index].length, 518 gKeys[index].value); 519 if (status != B_OK) { 520 printf("BPlusTree::Remove() returned: %s\n", strerror(status)); 521 bailOutWithKey(gKeys[index].data, gKeys[index].length); 522 } 523 insertTotal--; 524 gTreeCount--; 525 gKeys[index].in--; 526 527 if (gExcessive) 528 checkTree(tree); 529 } 530 } 531 532 if (gExcessive) 533 checkTree(tree); 534 } 535 536 537 void 538 addRandomSet(Transaction& transaction, BPlusTree* tree, int32 num) 539 { 540 printf("*** Add random set to tree (%ld to %ld old entries)...\n", 541 num, gTreeCount); 542 543 for (int32 i = 0; i < num; i++) { 544 int32 index = int32(1.0 * gNum * rand() / RAND_MAX); 545 if (index == gNum) 546 index = gNum - 1; 547 548 if (gVerbose) { 549 printf("adding key %ld (%ld times in the tree)\n", index, 550 gKeys[index].in); 551 } 552 553 status_t status = tree->Insert(transaction, (uint8*)gKeys[index].data, 554 gKeys[index].length, gKeys[index].value); 555 if (status != B_OK) { 556 printf("BPlusTree::Insert() returned: %s\n", strerror(status)); 557 bailOutWithKey(gKeys[index].data, gKeys[index].length); 558 } 559 gKeys[index].in++; 560 gTreeCount++; 561 562 if (gExcessive) 563 checkTree(tree); 564 } 565 if (!gExcessive) 566 checkTree(tree); 567 } 568 569 570 void 571 removeRandomSet(Transaction& transaction, BPlusTree* tree, int32 num) 572 { 573 printf("*** Remove random set from tree (%ld from %ld entries)...\n", 574 num, gTreeCount); 575 576 int32 tries = 500; 577 578 for (int32 i = 0; i < num; i++) { 579 if (gTreeCount < 1) 580 break; 581 582 int32 index = int32(1.0 * gNum * rand() / RAND_MAX); 583 if (index == gNum) 584 index = gNum - 1; 585 586 if (gKeys[index].in == 0) { 587 i--; 588 if (tries-- < 0) 589 break; 590 continue; 591 } 592 593 if (gVerbose) { 594 printf("removing key %ld (%ld times in the tree)\n", index, 595 gKeys[index].in); 596 } 597 598 status_t status = tree->Remove(transaction, (uint8*)gKeys[index].data, 599 gKeys[index].length, gKeys[index].value); 600 if (status != B_OK) { 601 printf("BPlusTree::Remove() returned: %s\n", strerror(status)); 602 bailOutWithKey(gKeys[index].data, gKeys[index].length); 603 } 604 gKeys[index].in--; 605 gTreeCount--; 606 607 if (gExcessive) 608 checkTree(tree); 609 } 610 if (!gExcessive) 611 checkTree(tree); 612 } 613 614 615 // #pragma mark - 616 617 618 void 619 usage(char* program) 620 { 621 if (strrchr(program, '/')) 622 program = strrchr(program, '/') + 1; 623 fprintf(stderr, "usage: %s [-veh] [-t type] [-n keys] [-i iterations] " 624 "[-h times] [-r seed]\n" 625 "BFS B+Tree torture test\n" 626 "\t-t\ttype is one of string, int32, uint32, int64, uint64, float,\n" 627 "\t\tor double; defaults to string.\n" 628 "\t-n\tkeys is the number of keys to be used,\n" 629 "\t\tminimum is 1, defaults to %d.\n" 630 "\t-i\titerations is the number of the test cycles, defaults to %d.\n" 631 "\t-r\tthe seed for the random function, defaults to %ld.\n" 632 "\t-h\tremoves the keys and start over again for x times.\n" 633 "\t-e\texcessive validity tests: tree contents will be tested after " 634 "every operation\n" 635 "\t-v\tfor verbose output.\n", 636 program, DEFAULT_NUM_KEYS, DEFAULT_ITERATIONS, gSeed); 637 exit(0); 638 } 639 640 641 int 642 main(int argc, char** argv) 643 { 644 char* program = argv[0]; 645 646 while (*++argv) { 647 char* arg = *argv; 648 if (*arg == '-') { 649 if (arg[1] == '-') 650 usage(program); 651 652 while (*++arg && isalpha(*arg)) { 653 switch (*arg) { 654 case 'v': 655 gVerbose = true; 656 break; 657 case 'e': 658 gExcessive = true; 659 break; 660 case 't': 661 if (*++argv == NULL) 662 usage(program); 663 664 if (!strcmp(*argv, "string")) 665 gType = S_STR_INDEX; 666 else if (!strcmp(*argv, "int32") 667 || !strcmp(*argv, "int")) 668 gType = S_INT_INDEX; 669 else if (!strcmp(*argv, "uint32") 670 || !strcmp(*argv, "uint")) 671 gType = S_UINT_INDEX; 672 else if (!strcmp(*argv, "int64") 673 || !strcmp(*argv, "llong")) 674 gType = S_LONG_LONG_INDEX; 675 else if (!strcmp(*argv, "uint64") 676 || !strcmp(*argv, "ullong")) 677 gType = S_ULONG_LONG_INDEX; 678 else if (!strcmp(*argv, "float")) 679 gType = S_FLOAT_INDEX; 680 else if (!strcmp(*argv, "double")) 681 gType = S_DOUBLE_INDEX; 682 else 683 usage(program); 684 break; 685 case 'n': 686 if (*++argv == NULL || !isdigit(**argv)) 687 usage(program); 688 689 gNum = atoi(*argv); 690 if (gNum < 1) 691 gNum = 1; 692 break; 693 case 'h': 694 if (*++argv == NULL || !isdigit(**argv)) 695 usage(program); 696 697 gHard = atoi(*argv); 698 if (gHard < 1) 699 gHard = 1; 700 break; 701 case 'i': 702 if (*++argv == NULL || !isdigit(**argv)) 703 usage(program); 704 705 gIterations = atoi(*argv); 706 if (gIterations < 1) 707 gIterations = 1; 708 break; 709 case 'r': 710 if (*++argv == NULL || !isdigit(**argv)) 711 usage(program); 712 713 gSeed = atoi(*argv); 714 break; 715 } 716 } 717 } else 718 break; 719 } 720 721 // we do want to have reproducible random keys 722 if (gVerbose) 723 printf("Set seed to %ld\n", gSeed); 724 srand(gSeed); 725 726 Inode inode("tree.data", gType | S_ALLOW_DUPS); 727 rw_lock_write_lock(&inode.Lock()); 728 gVolume = inode.GetVolume(); 729 Transaction transaction(gVolume, 0); 730 731 init_cache(gVolume->Device(), gVolume->BlockSize()); 732 733 // Create the tree, the keys, and add all keys to the tree initially 734 735 BPlusTree tree(transaction, &inode); 736 status_t status = tree.InitCheck(); 737 if (status != B_OK) { 738 fprintf(stderr, "creating tree failed: %s\n", strerror(status)); 739 bailOut(); 740 } 741 742 printf("*** Creating %ld keys...\n", gNum); 743 status = createKeys(); 744 if (status != B_OK) { 745 fprintf(stderr, "creating keys failed: %s\n", strerror(status)); 746 bailOut(); 747 } 748 749 if (gVerbose) 750 dumpKeys(); 751 752 for (int32 j = 0; j < gHard; j++) { 753 addAllKeys(transaction, &tree); 754 755 // Run the tests (they will exit the app, if an error occurs) 756 757 for (int32 i = 0; i < gIterations; i++) { 758 printf("---------- Test iteration %ld --------------------------\n", 759 i + 1); 760 761 addRandomSet(transaction, &tree, 762 int32(1.0 * gNum * rand() / RAND_MAX)); 763 removeRandomSet(transaction, &tree, 764 int32(1.0 * gNum * rand() / RAND_MAX)); 765 duplicateTest(transaction, &tree); 766 } 767 768 removeAllKeys(transaction, &tree); 769 } 770 771 transaction.Done(); 772 773 // Of course, we would have to free all our memory in a real application 774 // here... 775 776 // write the cache back to the tree 777 shutdown_cache(gVolume->Device(), gVolume->BlockSize()); 778 return 0; 779 } 780 781