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