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