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