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