btree_test.c

Version: - FREEBSD - FREEBSD-13-STABLE - FREEBSD-13-0 - FREEBSD-12-STABLE - FREEBSD-12-0 - FREEBSD-11-STABLE - FREEBSD-11-0 - FREEBSD-10-STABLE - FREEBSD-10-0 - FREEBSD-9-STABLE - FREEBSD-9-0 - FREEBSD-8-STABLE - FREEBSD-8-0 - FREEBSD-7-STABLE - FREEBSD-7-0 - FREEBSD-6-STABLE - FREEBSD-6-0 - FREEBSD-5-STABLE - FREEBSD-5-0 - FREEBSD-4-STABLE - FREEBSD-3-STABLE - FREEBSD22 - l41 - OPENBSD - linux-2.6 - MK84 - PLAN9 - xnu-8792
SearchContext: - none - 3 - 10
    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, 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 }
Cache object: 71bc145ae21c0e0e7190def57d4c78c6
[ source navigation ] [ diff markup ] [ identifier search ] [ freetext search ] [ file search ] [ list types ] [ track identifier ]
This page is part of the FreeBSD/Linux Linux Kernel Cross-Reference, and was automatically generated using a modified version of the LXR engine.
FreeBSD/Linux Kernel Cross Reference sys/contrib/openzfs/tests/zfs-tests/cmd/btree_test.c

FreeBSD/Linux Kernel Cross Reference
sys/contrib/openzfs/tests/zfs-tests/cmd/btree_test.c
