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