tests/zfs-tests/cmd/btree_test/btree_test.c

   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         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
 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
 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
 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
 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 }