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
usage(int exit_value)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
avl_compare(const void * v1,const void * v2)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
zfs_btree_compare(const void * v1,const void * v2)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
verify_contents(avl_tree_t * avl,zfs_btree_t * bt)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
verify_node(avl_tree_t * avl,zfs_btree_t * bt,int_node_t * node)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
find_without_index(zfs_btree_t * bt,char * why)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
insert_find_remove(zfs_btree_t * bt,char * why)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
drain_tree(zfs_btree_t * bt,char * why)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
stress_tree(zfs_btree_t * bt,char * why)295 stress_tree(zfs_btree_t *bt, char *why)
296 {
297 avl_tree_t avl;
298 int_node_t *node;
299 struct timeval tp;
300 time_t t0;
301 int insertions = 0, removals = 0, iterations = 0;
302 u_longlong_t max = 0, min = UINT64_MAX;
303
304 (void) gettimeofday(&tp, NULL);
305 t0 = tp.tv_sec;
306
307 avl_create(&avl, avl_compare, sizeof (int_node_t),
308 offsetof(int_node_t, node));
309
310 while (1) {
311 zfs_btree_index_t bt_idx = {0};
312 avl_index_t avl_idx = {0};
313
314 uint64_t randval = random() % tree_limit;
315 node = malloc(sizeof (*node));
316 node->data = randval;
317
318 max = randval > max ? randval : max;
319 min = randval < min ? randval : min;
320
321 void *ret = avl_find(&avl, node, &avl_idx);
322 if (ret == NULL) {
323 insertions++;
324 avl_insert(&avl, node, avl_idx);
325 ASSERT3P(zfs_btree_find(bt, &randval, &bt_idx), ==,
326 NULL);
327 zfs_btree_add_idx(bt, &randval, &bt_idx);
328 verify_node(&avl, bt, node);
329 } else {
330 removals++;
331 verify_node(&avl, bt, ret);
332 zfs_btree_remove(bt, &randval);
333 avl_remove(&avl, ret);
334 free(ret);
335 free(node);
336 }
337
338 zfs_btree_verify(bt);
339
340 iterations++;
341 if (iterations % contents_frequency == 0) {
342 verify_contents(&avl, bt);
343 }
344
345 zfs_btree_verify(bt);
346
347 (void) gettimeofday(&tp, NULL);
348 if (tp.tv_sec > t0 + stress_timeout) {
349 fprintf(stderr, "insertions/removals: %u/%u\nmax/min: "
350 "%llu/%llu\n", insertions, removals, max, min);
351 break;
352 }
353 }
354
355 void *avl_cookie = NULL;
356 while ((node = avl_destroy_nodes(&avl, &avl_cookie)) != NULL)
357 free(node);
358 avl_destroy(&avl);
359
360 if (stress_only) {
361 zfs_btree_index_t *idx = NULL;
362 uint64_t *rv;
363
364 while ((rv = zfs_btree_destroy_nodes(bt, &idx)) != NULL)
365 ;
366 zfs_btree_verify(bt);
367 }
368
369 return (0);
370 }
371
372 /*
373 * Verify inserting a duplicate value will cause a crash.
374 * Note: negative test; return of 0 is a failure.
375 */
376 static int
insert_duplicate(zfs_btree_t * bt)377 insert_duplicate(zfs_btree_t *bt)
378 {
379 uint64_t *p, i = 23456;
380 zfs_btree_index_t bt_idx = {0};
381
382 if ((p = (uint64_t *)zfs_btree_find(bt, &i, &bt_idx)) != NULL) {
383 fprintf(stderr, "Found value in empty tree.\n");
384 return (0);
385 }
386 zfs_btree_add_idx(bt, &i, &bt_idx);
387 if ((p = (uint64_t *)zfs_btree_find(bt, &i, &bt_idx)) == NULL) {
388 fprintf(stderr, "Did not find expected value.\n");
389 return (0);
390 }
391
392 /* Crash on inserting a duplicate */
393 zfs_btree_add_idx(bt, &i, NULL);
394
395 return (0);
396 }
397
398 /*
399 * Verify removing a non-existent value will cause a crash.
400 * Note: negative test; return of 0 is a failure.
401 */
402 static int
remove_missing(zfs_btree_t * bt)403 remove_missing(zfs_btree_t *bt)
404 {
405 uint64_t *p, i = 23456;
406 zfs_btree_index_t bt_idx = {0};
407
408 if ((p = (uint64_t *)zfs_btree_find(bt, &i, &bt_idx)) != NULL) {
409 fprintf(stderr, "Found value in empty tree.\n");
410 return (0);
411 }
412
413 /* Crash removing a nonexistent entry */
414 zfs_btree_remove(bt, &i);
415
416 return (0);
417 }
418
419 static int
do_negative_test(zfs_btree_t * bt,char * test_name)420 do_negative_test(zfs_btree_t *bt, char *test_name)
421 {
422 int rval = 0;
423 struct rlimit rlim = {0};
424 setrlimit(RLIMIT_CORE, &rlim);
425
426 if (strcmp(test_name, "insert_duplicate") == 0) {
427 rval = insert_duplicate(bt);
428 } else if (strcmp(test_name, "remove_missing") == 0) {
429 rval = remove_missing(bt);
430 }
431
432 /*
433 * Return 0, since callers will expect non-zero return values for
434 * these tests, and we should have crashed before getting here anyway.
435 */
436 (void) fprintf(stderr, "Test: %s returned %d.\n", test_name, rval);
437 return (0);
438 }
439
440 typedef struct btree_test {
441 const char *name;
442 int (*func)(zfs_btree_t *, char *);
443 } btree_test_t;
444
445 static btree_test_t test_table[] = {
446 { "insert_find_remove", insert_find_remove },
447 { "find_without_index", find_without_index },
448 { "drain_tree", drain_tree },
449 { "stress_tree", stress_tree },
450 { NULL, NULL }
451 };
452
453 int
main(int argc,char * argv[])454 main(int argc, char *argv[])
455 {
456 char *negative_test = NULL;
457 int failed_tests = 0;
458 struct timeval tp;
459 zfs_btree_t bt;
460 int c;
461
462 while ((c = getopt(argc, argv, "c:l:n:r:st:")) != -1) {
463 switch (c) {
464 case 'c':
465 contents_frequency = atoi(optarg);
466 break;
467 case 'l':
468 tree_limit = atoi(optarg);
469 break;
470 case 'n':
471 negative_test = optarg;
472 break;
473 case 'r':
474 seed = atoi(optarg);
475 break;
476 case 's':
477 stress_only = B_TRUE;
478 break;
479 case 't':
480 stress_timeout = atoi(optarg);
481 break;
482 case 'h':
483 default:
484 usage(1);
485 break;
486 }
487 }
488 argc -= optind;
489 argv += optind;
490 optind = 1;
491
492
493 if (seed == 0) {
494 (void) gettimeofday(&tp, NULL);
495 seed = tp.tv_sec;
496 }
497 srandom(seed);
498
499 zfs_btree_init();
500 zfs_btree_create(&bt, zfs_btree_compare, sizeof (uint64_t));
501
502 /*
503 * This runs the named negative test. None of them should
504 * return, as they both cause crashes.
505 */
506 if (negative_test) {
507 return (do_negative_test(&bt, negative_test));
508 }
509
510 fprintf(stderr, "Seed: %u\n", seed);
511
512 /*
513 * This is a stress test that does operations on a btree over the
514 * requested timeout period, verifying them against identical
515 * operations in an avl tree.
516 */
517 if (stress_only != 0) {
518 return (stress_tree(&bt, NULL));
519 }
520
521 /* Do the positive tests */
522 btree_test_t *test = &test_table[0];
523 while (test->name) {
524 int retval;
525 uint64_t *rv;
526 char why[BUFSIZE] = {0};
527 zfs_btree_index_t *idx = NULL;
528
529 (void) fprintf(stdout, "%-20s", test->name);
530 retval = test->func(&bt, why);
531
532 if (retval == 0) {
533 (void) fprintf(stdout, "ok\n");
534 } else {
535 (void) fprintf(stdout, "failed with %d\n", retval);
536 if (strlen(why) != 0)
537 (void) fprintf(stdout, "\t%s\n", why);
538 why[0] = '\0';
539 failed_tests++;
540 }
541
542 /* Remove all the elements and re-verify the tree */
543 while ((rv = zfs_btree_destroy_nodes(&bt, &idx)) != NULL)
544 ;
545 zfs_btree_verify(&bt);
546
547 test++;
548 }
549
550 zfs_btree_verify(&bt);
551 zfs_btree_fini();
552
553 return (failed_tests);
554 }
555