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