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
dumpTree()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
bailOut()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
bailOutWithKey(void * key,uint16 length)96 bailOutWithKey(void* key, uint16 length)
97 {
98 dumpKey(key, length);
99 putchar('\n');
100 bailOut();
101 }
102
103
104 void
dumpKey(void * key,int32 length)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("%lld", *(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
dumpKeys()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
generateName(int32 i,char * name,int32 * _length)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
fillBuffer(void * buffer,int32 start)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
createKeys()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
checkTreeContents(BPlusTree * tree)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 %lld 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 %lld (should be %lld)\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 = %lld, %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
checkTreeIntegrity(BPlusTree * tree)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
checkTree(BPlusTree * tree)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
addAllKeys(Transaction & transaction,BPlusTree * tree)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
removeAllKeys(Transaction & transaction,BPlusTree * tree)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
duplicateTest(Transaction & transaction,BPlusTree * tree)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
addRandomSet(Transaction & transaction,BPlusTree * tree,int32 num)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
removeRandomSet(Transaction & transaction,BPlusTree * tree,int32 num)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
usage(char * program)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
main(int argc,char ** argv)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