xref: /illumos-gate/usr/src/test/zfs-tests/cmd/btree_test/btree_test.c (revision db8a370dba45fa238d7ad5ac85e2fffef8713c75)
1 /*
2  * This file and its contents are supplied under the terms of the
3  * Common Development and Distribution License ("CDDL"), version 1.0.
4  * You may only use this file in accordance with the terms of version
5  * 1.0 of the CDDL.
6  *
7  * A full copy of the text of the CDDL should have accompanied this
8  * source.  A copy of the CDDL is also available via the Internet at
9  * http://www.illumos.org/license/CDDL.
10  */
11 
12 /*
13  * Copyright (c) 2019 by Delphix. All rights reserved.
14  */
15 
16 #include <stdio.h>
17 #include <stdlib.h>
18 #include <string.h>
19 #include <sys/avl.h>
20 #include <sys/btree.h>
21 #include <sys/time.h>
22 #include <sys/resource.h>
23 
24 #define	BUFSIZE 256
25 
26 int seed = 0;
27 int stress_timeout = 180;
28 int contents_frequency = 100;
29 int tree_limit = 64 * 1024;
30 boolean_t stress_only = B_FALSE;
31 
32 static void
usage(int exit_value)33 usage(int exit_value)
34 {
35 	(void) fprintf(stderr, "Usage:\tbtree_test -n <test_name>\n");
36 	(void) fprintf(stderr, "\tbtree_test -s [-r <seed>] [-l <limit>] "
37 	    "[-t timeout>] [-c check_contents]\n");
38 	(void) fprintf(stderr, "\tbtree_test [-r <seed>] [-l <limit>] "
39 	    "[-t timeout>] [-c check_contents]\n");
40 	(void) fprintf(stderr, "\n    With the -n option, run the named "
41 	    "negative test. With the -s option,\n");
42 	(void) fprintf(stderr, "    run the stress test according to the "
43 	    "other options passed. With\n");
44 	(void) fprintf(stderr, "    neither, run all the positive tests, "
45 	    "including the stress test with\n");
46 	(void) fprintf(stderr, "    the default options.\n");
47 	(void) fprintf(stderr, "\n    Options that control the stress test\n");
48 	(void) fprintf(stderr, "\t-c stress iterations after which to compare "
49 	    "tree contents [default: 100]\n");
50 	(void) fprintf(stderr, "\t-l the largest value to allow in the tree "
51 	    "[default: 1M]\n");
52 	(void) fprintf(stderr, "\t-r random seed [default: from "
53 	    "gettimeofday()]\n");
54 	(void) fprintf(stderr, "\t-t seconds to let the stress test run "
55 	    "[default: 180]\n");
56 	exit(exit_value);
57 }
58 
59 typedef struct int_node {
60 	avl_node_t node;
61 	uint64_t data;
62 } int_node_t;
63 
64 /*
65  * Utility functions
66  */
67 
68 static int
avl_compare(const void * v1,const void * v2)69 avl_compare(const void *v1, const void *v2)
70 {
71 	const int_node_t *n1 = v1;
72 	const int_node_t *n2 = v2;
73 	uint64_t a = n1->data;
74 	uint64_t b = n2->data;
75 
76 	return (TREE_CMP(a, b));
77 }
78 
79 static int
zfs_btree_compare(const void * v1,const void * v2)80 zfs_btree_compare(const void *v1, const void *v2)
81 {
82 	const uint64_t *a = v1;
83 	const uint64_t *b = v2;
84 
85 	return (TREE_CMP(*a, *b));
86 }
87 
88 static void
verify_contents(avl_tree_t * avl,zfs_btree_t * bt)89 verify_contents(avl_tree_t *avl, zfs_btree_t *bt)
90 {
91 	static int count = 0;
92 	zfs_btree_index_t bt_idx = {0};
93 	int_node_t *node;
94 	uint64_t *data;
95 
96 	boolean_t forward = count % 2 == 0 ? B_TRUE : B_FALSE;
97 	count++;
98 
99 	ASSERT3U(avl_numnodes(avl), ==, zfs_btree_numnodes(bt));
100 	if (forward == B_TRUE) {
101 		node = avl_first(avl);
102 		data = zfs_btree_first(bt, &bt_idx);
103 	} else {
104 		node = avl_last(avl);
105 		data = zfs_btree_last(bt, &bt_idx);
106 	}
107 
108 	while (node != NULL) {
109 		ASSERT3U(*data, ==, node->data);
110 		if (forward == B_TRUE) {
111 			data = zfs_btree_next(bt, &bt_idx, &bt_idx);
112 			node = AVL_NEXT(avl, node);
113 		} else {
114 			data = zfs_btree_prev(bt, &bt_idx, &bt_idx);
115 			node = AVL_PREV(avl, node);
116 		}
117 	}
118 }
119 
120 static void
verify_node(avl_tree_t * avl,zfs_btree_t * bt,int_node_t * node)121 verify_node(avl_tree_t *avl, zfs_btree_t *bt, int_node_t *node)
122 {
123 	zfs_btree_index_t bt_idx = {0};
124 	zfs_btree_index_t bt_idx2 = {0};
125 	int_node_t *inp;
126 	uint64_t data = node->data;
127 	uint64_t *rv = NULL;
128 
129 	ASSERT3U(avl_numnodes(avl), ==, zfs_btree_numnodes(bt));
130 	ASSERT3P((rv = (uint64_t *)zfs_btree_find(bt, &data, &bt_idx)), !=,
131 	    NULL);
132 	ASSERT3S(*rv, ==, data);
133 	ASSERT3P(zfs_btree_get(bt, &bt_idx), !=, NULL);
134 	ASSERT3S(data, ==, *(uint64_t *)zfs_btree_get(bt, &bt_idx));
135 
136 	if ((inp = AVL_NEXT(avl, node)) != NULL) {
137 		ASSERT3P((rv = zfs_btree_next(bt, &bt_idx, &bt_idx2)), !=,
138 		    NULL);
139 		ASSERT3P(rv, ==, zfs_btree_get(bt, &bt_idx2));
140 		ASSERT3S(inp->data, ==, *rv);
141 	} else {
142 		ASSERT3U(data, ==, *(uint64_t *)zfs_btree_last(bt, &bt_idx));
143 	}
144 
145 	if ((inp = AVL_PREV(avl, node)) != NULL) {
146 		ASSERT3P((rv = zfs_btree_prev(bt, &bt_idx, &bt_idx2)), !=,
147 		    NULL);
148 		ASSERT3P(rv, ==, zfs_btree_get(bt, &bt_idx2));
149 		ASSERT3S(inp->data, ==, *rv);
150 	} else {
151 		ASSERT3U(data, ==, *(uint64_t *)zfs_btree_first(bt, &bt_idx));
152 	}
153 }
154 
155 /*
156  * Tests
157  */
158 
159 /* Verify that zfs_btree_find works correctly with a NULL index. */
160 static int
find_without_index(zfs_btree_t * bt,char * why)161 find_without_index(zfs_btree_t *bt, char *why)
162 {
163 	u_longlong_t *p, i = 12345;
164 
165 	zfs_btree_add(bt, &i);
166 	if ((p = (u_longlong_t *)zfs_btree_find(bt, &i, NULL)) == NULL ||
167 	    *p != i) {
168 		(void) snprintf(why, BUFSIZE, "Unexpectedly found %llu\n",
169 		    p == NULL ? 0 : *p);
170 		return (1);
171 	}
172 
173 	i++;
174 
175 	if ((p = (u_longlong_t *)zfs_btree_find(bt, &i, NULL)) != NULL) {
176 		(void) snprintf(why, BUFSIZE, "Found bad value: %llu\n", *p);
177 		return (1);
178 	}
179 
180 	return (0);
181 }
182 
183 /* Verify simple insertion and removal from the tree. */
184 static int
insert_find_remove(zfs_btree_t * bt,char * why)185 insert_find_remove(zfs_btree_t *bt, char *why)
186 {
187 	u_longlong_t *p, i = 12345;
188 	zfs_btree_index_t bt_idx = {0};
189 
190 	/* Insert 'i' into the tree, and attempt to find it again. */
191 	zfs_btree_add(bt, &i);
192 	if ((p = (u_longlong_t *)zfs_btree_find(bt, &i, &bt_idx)) == NULL) {
193 		(void) snprintf(why, BUFSIZE, "Didn't find value in tree\n");
194 		return (1);
195 	} else if (*p != i) {
196 		(void) snprintf(why, BUFSIZE, "Found (%llu) in tree\n", *p);
197 		return (1);
198 	}
199 	ASSERT3S(zfs_btree_numnodes(bt), ==, 1);
200 	zfs_btree_verify(bt);
201 
202 	/* Remove 'i' from the tree, and verify it is not found. */
203 	zfs_btree_remove(bt, &i);
204 	if ((p = (u_longlong_t *)zfs_btree_find(bt, &i, &bt_idx)) != NULL) {
205 		(void) snprintf(why, BUFSIZE,
206 		    "Found removed value (%llu)\n", *p);
207 		return (1);
208 	}
209 	ASSERT3S(zfs_btree_numnodes(bt), ==, 0);
210 	zfs_btree_verify(bt);
211 
212 	return (0);
213 }
214 
215 /*
216  * Add a number of random entries into a btree and avl tree. Then walk them
217  * backwards and forwards while emptying the tree, verifying the trees look
218  * the same.
219  */
220 static int
drain_tree(zfs_btree_t * bt,char * why)221 drain_tree(zfs_btree_t *bt, char *why)
222 {
223 	uint64_t *p;
224 	avl_tree_t avl;
225 	int i = 0;
226 	int_node_t *node;
227 	avl_index_t avl_idx = {0};
228 	zfs_btree_index_t bt_idx = {0};
229 
230 	avl_create(&avl, avl_compare, sizeof (int_node_t),
231 	    offsetof(int_node_t, node));
232 
233 	/* Fill both trees with the same data */
234 	for (i = 0; i < 64 * 1024; i++) {
235 		void *ret;
236 
237 		u_longlong_t randval = random();
238 		if ((p = (uint64_t *)zfs_btree_find(bt, &randval, &bt_idx)) !=
239 		    NULL) {
240 			continue;
241 		}
242 		zfs_btree_add_idx(bt, &randval, &bt_idx);
243 
244 		node = malloc(sizeof (int_node_t));
245 		ASSERT3P(node, !=, NULL);
246 
247 		node->data = randval;
248 		if ((ret = avl_find(&avl, node, &avl_idx)) != NULL) {
249 			(void) snprintf(why, BUFSIZE,
250 			    "Found in avl: %llu\n", randval);
251 			return (1);
252 		}
253 		avl_insert(&avl, node, avl_idx);
254 	}
255 
256 	/* Remove data from either side of the trees, comparing the data */
257 	while (avl_numnodes(&avl) != 0) {
258 		uint64_t *data;
259 
260 		ASSERT3U(avl_numnodes(&avl), ==, zfs_btree_numnodes(bt));
261 		if (avl_numnodes(&avl) % 2 == 0) {
262 			node = avl_first(&avl);
263 			data = zfs_btree_first(bt, &bt_idx);
264 		} else {
265 			node = avl_last(&avl);
266 			data = zfs_btree_last(bt, &bt_idx);
267 		}
268 		ASSERT3U(node->data, ==, *data);
269 		zfs_btree_remove_idx(bt, &bt_idx);
270 		avl_remove(&avl, node);
271 
272 		if (avl_numnodes(&avl) == 0) {
273 			break;
274 		}
275 
276 		node = avl_first(&avl);
277 		ASSERT3U(node->data, ==,
278 		    *(uint64_t *)zfs_btree_first(bt, NULL));
279 		node = avl_last(&avl);
280 		ASSERT3U(node->data, ==, *(uint64_t *)zfs_btree_last(bt, NULL));
281 	}
282 	ASSERT3S(zfs_btree_numnodes(bt), ==, 0);
283 
284 	void *avl_cookie = NULL;
285 	while ((node = avl_destroy_nodes(&avl, &avl_cookie)) != NULL)
286 		free(node);
287 	avl_destroy(&avl);
288 
289 	return (0);
290 }
291 
292 /*
293  * This test uses an avl and btree, and continually processes new random
294  * values. Each value is either removed or inserted, depending on whether
295  * or not it is found in the tree. The test periodically checks that both
296  * trees have the same data and does consistency checks. This stress
297  * option can also be run on its own from the command line.
298  */
299 static int
stress_tree(zfs_btree_t * bt,char * why __unused)300 stress_tree(zfs_btree_t *bt, char *why __unused)
301 {
302 	avl_tree_t avl;
303 	int_node_t *node;
304 	struct timeval tp;
305 	time_t t0;
306 	int insertions = 0, removals = 0, iterations = 0;
307 	u_longlong_t max = 0, min = UINT64_MAX;
308 
309 	(void) gettimeofday(&tp, NULL);
310 	t0 = tp.tv_sec;
311 
312 	avl_create(&avl, avl_compare, sizeof (int_node_t),
313 	    offsetof(int_node_t, node));
314 
315 	while (1) {
316 		zfs_btree_index_t bt_idx = {0};
317 		avl_index_t avl_idx = {0};
318 
319 		uint64_t randval = random() % tree_limit;
320 		node = malloc(sizeof (*node));
321 		node->data = randval;
322 
323 		max = randval > max ? randval : max;
324 		min = randval < min ? randval : min;
325 
326 		void *ret = avl_find(&avl, node, &avl_idx);
327 		if (ret == NULL) {
328 			insertions++;
329 			avl_insert(&avl, node, avl_idx);
330 			ASSERT3P(zfs_btree_find(bt, &randval, &bt_idx), ==,
331 			    NULL);
332 			zfs_btree_add_idx(bt, &randval, &bt_idx);
333 			verify_node(&avl, bt, node);
334 		} else {
335 			removals++;
336 			verify_node(&avl, bt, ret);
337 			zfs_btree_remove(bt, &randval);
338 			avl_remove(&avl, ret);
339 			free(ret);
340 			free(node);
341 		}
342 
343 		zfs_btree_verify(bt);
344 
345 		iterations++;
346 		if (iterations % contents_frequency == 0) {
347 			verify_contents(&avl, bt);
348 		}
349 
350 		zfs_btree_verify(bt);
351 
352 		(void) gettimeofday(&tp, NULL);
353 		if (tp.tv_sec > t0 + stress_timeout) {
354 			fprintf(stderr, "insertions/removals: %u/%u\nmax/min: "
355 			    "%llu/%llu\n", insertions, removals, max, min);
356 			break;
357 		}
358 	}
359 
360 	void *avl_cookie = NULL;
361 	while ((node = avl_destroy_nodes(&avl, &avl_cookie)) != NULL)
362 		free(node);
363 	avl_destroy(&avl);
364 
365 	if (stress_only) {
366 		zfs_btree_index_t *idx = NULL;
367 		uint64_t *rv;
368 
369 		while ((rv = zfs_btree_destroy_nodes(bt, &idx)) != NULL)
370 			;
371 		zfs_btree_verify(bt);
372 	}
373 
374 	return (0);
375 }
376 
377 /*
378  * Verify inserting a duplicate value will cause a crash.
379  * Note: negative test; return of 0 is a failure.
380  */
381 static int
insert_duplicate(zfs_btree_t * bt)382 insert_duplicate(zfs_btree_t *bt)
383 {
384 	uint64_t *p, i = 23456;
385 	zfs_btree_index_t bt_idx = {0};
386 
387 	if ((p = (uint64_t *)zfs_btree_find(bt, &i, &bt_idx)) != NULL) {
388 		fprintf(stderr, "Found value in empty tree.\n");
389 		return (0);
390 	}
391 	zfs_btree_add_idx(bt, &i, &bt_idx);
392 	if ((p = (uint64_t *)zfs_btree_find(bt, &i, &bt_idx)) == NULL) {
393 		fprintf(stderr, "Did not find expected value.\n");
394 		return (0);
395 	}
396 
397 	/* Crash on inserting a duplicate */
398 	zfs_btree_add_idx(bt, &i, NULL);
399 
400 	return (0);
401 }
402 
403 /*
404  * Verify removing a non-existent value will cause a crash.
405  * Note: negative test; return of 0 is a failure.
406  */
407 static int
remove_missing(zfs_btree_t * bt)408 remove_missing(zfs_btree_t *bt)
409 {
410 	uint64_t *p, i = 23456;
411 	zfs_btree_index_t bt_idx = {0};
412 
413 	if ((p = (uint64_t *)zfs_btree_find(bt, &i, &bt_idx)) != NULL) {
414 		fprintf(stderr, "Found value in empty tree.\n");
415 		return (0);
416 	}
417 
418 	/* Crash removing a nonexistent entry */
419 	zfs_btree_remove(bt, &i);
420 
421 	return (0);
422 }
423 
424 static int
do_negative_test(zfs_btree_t * bt,char * test_name)425 do_negative_test(zfs_btree_t *bt, char *test_name)
426 {
427 	int rval = 0;
428 	struct rlimit rlim = {0};
429 
430 	(void) setrlimit(RLIMIT_CORE, &rlim);
431 
432 	if (strcmp(test_name, "insert_duplicate") == 0) {
433 		rval = insert_duplicate(bt);
434 	} else if (strcmp(test_name, "remove_missing") == 0) {
435 		rval = remove_missing(bt);
436 	}
437 
438 	/*
439 	 * Return 0, since callers will expect non-zero return values for
440 	 * these tests, and we should have crashed before getting here anyway.
441 	 */
442 	(void) fprintf(stderr, "Test: %s returned %d.\n", test_name, rval);
443 	return (0);
444 }
445 
446 typedef struct btree_test {
447 	const char	*name;
448 	int		(*func)(zfs_btree_t *, char *);
449 } btree_test_t;
450 
451 static btree_test_t test_table[] = {
452 	{ "insert_find_remove",		insert_find_remove	},
453 	{ "find_without_index",		find_without_index	},
454 	{ "drain_tree",			drain_tree		},
455 	{ "stress_tree",		stress_tree		},
456 	{ NULL,				NULL			}
457 };
458 
459 int
main(int argc,char * argv[])460 main(int argc, char *argv[])
461 {
462 	char *negative_test = NULL;
463 	int failed_tests = 0;
464 	struct timeval tp;
465 	zfs_btree_t bt;
466 	int c;
467 
468 	while ((c = getopt(argc, argv, "c:l:n:r:st:")) != -1) {
469 		switch (c) {
470 		case 'c':
471 			contents_frequency = atoi(optarg);
472 			break;
473 		case 'l':
474 			tree_limit = atoi(optarg);
475 			break;
476 		case 'n':
477 			negative_test = optarg;
478 			break;
479 		case 'r':
480 			seed = atoi(optarg);
481 			break;
482 		case 's':
483 			stress_only = B_TRUE;
484 			break;
485 		case 't':
486 			stress_timeout = atoi(optarg);
487 			break;
488 		case 'h':
489 		default:
490 			usage(1);
491 			break;
492 		}
493 	}
494 	argc -= optind;
495 	argv += optind;
496 	optind = 1;
497 
498 
499 	if (seed == 0) {
500 		(void) gettimeofday(&tp, NULL);
501 		seed = tp.tv_sec;
502 	}
503 	srandom(seed);
504 
505 	zfs_btree_init();
506 	zfs_btree_create(&bt, zfs_btree_compare, sizeof (uint64_t));
507 
508 	/*
509 	 * This runs the named negative test. None of them should
510 	 * return, as they both cause crashes.
511 	 */
512 	if (negative_test) {
513 		return (do_negative_test(&bt, negative_test));
514 	}
515 
516 	fprintf(stderr, "Seed: %u\n", seed);
517 
518 	/*
519 	 * This is a stress test that does operations on a btree over the
520 	 * requested timeout period, verifying them against identical
521 	 * operations in an avl tree.
522 	 */
523 	if (stress_only != 0) {
524 		return (stress_tree(&bt, NULL));
525 	}
526 
527 	/* Do the positive tests */
528 	btree_test_t *test = &test_table[0];
529 	while (test->name) {
530 		int retval;
531 		uint64_t *rv;
532 		char why[BUFSIZE] = {0};
533 		zfs_btree_index_t *idx = NULL;
534 
535 		(void) fprintf(stdout, "%-20s", test->name);
536 		retval = test->func(&bt, why);
537 
538 		if (retval == 0) {
539 			(void) fprintf(stdout, "ok\n");
540 		} else {
541 			(void) fprintf(stdout, "failed with %d\n", retval);
542 			if (strlen(why) != 0)
543 				(void) fprintf(stdout, "\t%s\n", why);
544 			why[0] = '\0';
545 			failed_tests++;
546 		}
547 
548 		/* Remove all the elements and re-verify the tree */
549 		while ((rv = zfs_btree_destroy_nodes(&bt, &idx)) != NULL)
550 			;
551 		zfs_btree_verify(&bt);
552 
553 		test++;
554 	}
555 
556 	zfs_btree_verify(&bt);
557 	zfs_btree_fini();
558 
559 	return (failed_tests);
560 }
561