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
33struct key {
34	void*	data;
35	uint32	length;
36	int32	in;
37	int32	count;
38	off_t	value;
39};
40
41key* gKeys;
42int32 gNum = DEFAULT_NUM_KEYS;
43int32 gType = DEFAULT_KEY_TYPE;
44int32 gTreeCount = 0;
45bool gVerbose, gExcessive;
46int32 gIterations = DEFAULT_ITERATIONS;
47int32 gHard = 1;
48Volume* gVolume;
49int32 gSeed = 42;
50
51// from cache.cpp (yes, we are that mean)
52extern BList gBlocks;
53
54
55// prototypes
56void bailOut();
57void bailOutWithKey(void* key, uint16 length);
58void dumpTree();
59void dumpKey(void* key, int32 length);
60void dumpKeys();
61
62
63void
64dumpTree()
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
81void
82bailOut()
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
95void
96bailOutWithKey(void* key, uint16 length)
97{
98	dumpKey(key, length);
99	putchar('\n');
100	bailOut();
101}
102
103
104void
105dumpKey(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
139void
140dumpKeys()
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
182void
183generateName(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
198void
199fillBuffer(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
245status_t
246createKeys()
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
321void
322checkTreeContents(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*/
382void
383checkTreeIntegrity(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
401void
402checkTree(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
422void
423addAllKeys(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
442void
443removeAllKeys(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
466void
467duplicateTest(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
537void
538addRandomSet(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
570void
571removeRandomSet(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
618void
619usage(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
641int
642main(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