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