aboutsummaryrefslogtreecommitdiff
path: root/tests/zfs-tests/cmd/btree_test/btree_test.c
diff options
context:
space:
mode:
Diffstat (limited to 'tests/zfs-tests/cmd/btree_test/btree_test.c')
-rw-r--r--tests/zfs-tests/cmd/btree_test/btree_test.c554
1 files changed, 554 insertions, 0 deletions
diff --git a/tests/zfs-tests/cmd/btree_test/btree_test.c b/tests/zfs-tests/cmd/btree_test/btree_test.c
new file mode 100644
index 000000000000..e1995c03af3e
--- /dev/null
+++ b/tests/zfs-tests/cmd/btree_test/btree_test.c
@@ -0,0 +1,554 @@
+/*
+ * This file and its contents are supplied under the terms of the
+ * Common Development and Distribution License ("CDDL"), version 1.0.
+ * You may only use this file in accordance with the terms of version
+ * 1.0 of the CDDL.
+ *
+ * A full copy of the text of the CDDL should have accompanied this
+ * source. A copy of the CDDL is also available via the Internet at
+ * http://www.illumos.org/license/CDDL.
+ */
+
+/*
+ * Copyright (c) 2019 by Delphix. All rights reserved.
+ */
+
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/avl.h>
+#include <sys/btree.h>
+#include <sys/time.h>
+#include <sys/resource.h>
+
+#define BUFSIZE 256
+
+int seed = 0;
+int stress_timeout = 180;
+int contents_frequency = 100;
+int tree_limit = 64 * 1024;
+boolean_t stress_only = B_FALSE;
+
+static void
+usage(int exit_value)
+{
+ (void) fprintf(stderr, "Usage:\tbtree_test -n <test_name>\n");
+ (void) fprintf(stderr, "\tbtree_test -s [-r <seed>] [-l <limit>] "
+ "[-t timeout>] [-c check_contents]\n");
+ (void) fprintf(stderr, "\tbtree_test [-r <seed>] [-l <limit>] "
+ "[-t timeout>] [-c check_contents]\n");
+ (void) fprintf(stderr, "\n With the -n option, run the named "
+ "negative test. With the -s option,\n");
+ (void) fprintf(stderr, " run the stress test according to the "
+ "other options passed. With\n");
+ (void) fprintf(stderr, " neither, run all the positive tests, "
+ "including the stress test with\n");
+ (void) fprintf(stderr, " the default options.\n");
+ (void) fprintf(stderr, "\n Options that control the stress test\n");
+ (void) fprintf(stderr, "\t-c stress iterations after which to compare "
+ "tree contents [default: 100]\n");
+ (void) fprintf(stderr, "\t-l the largest value to allow in the tree "
+ "[default: 1M]\n");
+ (void) fprintf(stderr, "\t-r random seed [default: from "
+ "gettimeofday()]\n");
+ (void) fprintf(stderr, "\t-t seconds to let the stress test run "
+ "[default: 180]\n");
+ exit(exit_value);
+}
+
+typedef struct int_node {
+ avl_node_t node;
+ uint64_t data;
+} int_node_t;
+
+/*
+ * Utility functions
+ */
+
+static int
+avl_compare(const void *v1, const void *v2)
+{
+ const int_node_t *n1 = v1;
+ const int_node_t *n2 = v2;
+ uint64_t a = n1->data;
+ uint64_t b = n2->data;
+
+ return (TREE_CMP(a, b));
+}
+
+static int
+zfs_btree_compare(const void *v1, const void *v2)
+{
+ const uint64_t *a = v1;
+ const uint64_t *b = v2;
+
+ return (TREE_CMP(*a, *b));
+}
+
+static void
+verify_contents(avl_tree_t *avl, zfs_btree_t *bt)
+{
+ static int count = 0;
+ zfs_btree_index_t bt_idx = {0};
+ int_node_t *node;
+ uint64_t *data;
+
+ boolean_t forward = count % 2 == 0 ? B_TRUE : B_FALSE;
+ count++;
+
+ ASSERT3U(avl_numnodes(avl), ==, zfs_btree_numnodes(bt));
+ if (forward == B_TRUE) {
+ node = avl_first(avl);
+ data = zfs_btree_first(bt, &bt_idx);
+ } else {
+ node = avl_last(avl);
+ data = zfs_btree_last(bt, &bt_idx);
+ }
+
+ while (node != NULL) {
+ ASSERT3U(*data, ==, node->data);
+ if (forward == B_TRUE) {
+ data = zfs_btree_next(bt, &bt_idx, &bt_idx);
+ node = AVL_NEXT(avl, node);
+ } else {
+ data = zfs_btree_prev(bt, &bt_idx, &bt_idx);
+ node = AVL_PREV(avl, node);
+ }
+ }
+}
+
+static void
+verify_node(avl_tree_t *avl, zfs_btree_t *bt, int_node_t *node)
+{
+ zfs_btree_index_t bt_idx = {0};
+ zfs_btree_index_t bt_idx2 = {0};
+ int_node_t *inp;
+ uint64_t data = node->data;
+ uint64_t *rv = NULL;
+
+ ASSERT3U(avl_numnodes(avl), ==, zfs_btree_numnodes(bt));
+ ASSERT3P((rv = (uint64_t *)zfs_btree_find(bt, &data, &bt_idx)), !=,
+ NULL);
+ ASSERT3S(*rv, ==, data);
+ ASSERT3P(zfs_btree_get(bt, &bt_idx), !=, NULL);
+ ASSERT3S(data, ==, *(uint64_t *)zfs_btree_get(bt, &bt_idx));
+
+ if ((inp = AVL_NEXT(avl, node)) != NULL) {
+ ASSERT3P((rv = zfs_btree_next(bt, &bt_idx, &bt_idx2)), !=,
+ NULL);
+ ASSERT3P(rv, ==, zfs_btree_get(bt, &bt_idx2));
+ ASSERT3S(inp->data, ==, *rv);
+ } else {
+ ASSERT3U(data, ==, *(uint64_t *)zfs_btree_last(bt, &bt_idx));
+ }
+
+ if ((inp = AVL_PREV(avl, node)) != NULL) {
+ ASSERT3P((rv = zfs_btree_prev(bt, &bt_idx, &bt_idx2)), !=,
+ NULL);
+ ASSERT3P(rv, ==, zfs_btree_get(bt, &bt_idx2));
+ ASSERT3S(inp->data, ==, *rv);
+ } else {
+ ASSERT3U(data, ==, *(uint64_t *)zfs_btree_first(bt, &bt_idx));
+ }
+}
+
+/*
+ * Tests
+ */
+
+/* Verify that zfs_btree_find works correctly with a NULL index. */
+static int
+find_without_index(zfs_btree_t *bt, char *why)
+{
+ u_longlong_t *p, i = 12345;
+
+ zfs_btree_add(bt, &i);
+ if ((p = (u_longlong_t *)zfs_btree_find(bt, &i, NULL)) == NULL ||
+ *p != i) {
+ snprintf(why, BUFSIZE, "Unexpectedly found %llu\n",
+ p == NULL ? 0 : *p);
+ return (1);
+ }
+
+ i++;
+
+ if ((p = (u_longlong_t *)zfs_btree_find(bt, &i, NULL)) != NULL) {
+ snprintf(why, BUFSIZE, "Found bad value: %llu\n", *p);
+ return (1);
+ }
+
+ return (0);
+}
+
+/* Verify simple insertion and removal from the tree. */
+static int
+insert_find_remove(zfs_btree_t *bt, char *why)
+{
+ u_longlong_t *p, i = 12345;
+ zfs_btree_index_t bt_idx = {0};
+
+ /* Insert 'i' into the tree, and attempt to find it again. */
+ zfs_btree_add(bt, &i);
+ if ((p = (u_longlong_t *)zfs_btree_find(bt, &i, &bt_idx)) == NULL) {
+ snprintf(why, BUFSIZE, "Didn't find value in tree\n");
+ return (1);
+ } else if (*p != i) {
+ snprintf(why, BUFSIZE, "Found (%llu) in tree\n", *p);
+ return (1);
+ }
+ ASSERT3S(zfs_btree_numnodes(bt), ==, 1);
+ zfs_btree_verify(bt);
+
+ /* Remove 'i' from the tree, and verify it is not found. */
+ zfs_btree_remove(bt, &i);
+ if ((p = (u_longlong_t *)zfs_btree_find(bt, &i, &bt_idx)) != NULL) {
+ snprintf(why, BUFSIZE, "Found removed value (%llu)\n", *p);
+ return (1);
+ }
+ ASSERT3S(zfs_btree_numnodes(bt), ==, 0);
+ zfs_btree_verify(bt);
+
+ return (0);
+}
+
+/*
+ * Add a number of random entries into a btree and avl tree. Then walk them
+ * backwards and forwards while emptying the tree, verifying the trees look
+ * the same.
+ */
+static int
+drain_tree(zfs_btree_t *bt, char *why)
+{
+ uint64_t *p;
+ avl_tree_t avl;
+ int i = 0;
+ int_node_t *node;
+ avl_index_t avl_idx = {0};
+ zfs_btree_index_t bt_idx = {0};
+
+ avl_create(&avl, avl_compare, sizeof (int_node_t),
+ offsetof(int_node_t, node));
+
+ /* Fill both trees with the same data */
+ for (i = 0; i < 64 * 1024; i++) {
+ void *ret;
+
+ u_longlong_t randval = random();
+ node = malloc(sizeof (int_node_t));
+ if ((p = (uint64_t *)zfs_btree_find(bt, &randval, &bt_idx)) !=
+ NULL) {
+ continue;
+ }
+ zfs_btree_add_idx(bt, &randval, &bt_idx);
+
+ node->data = randval;
+ if ((ret = avl_find(&avl, node, &avl_idx)) != NULL) {
+ snprintf(why, BUFSIZE, "Found in avl: %llu\n", randval);
+ return (1);
+ }
+ avl_insert(&avl, node, avl_idx);
+ }
+
+ /* Remove data from either side of the trees, comparing the data */
+ while (avl_numnodes(&avl) != 0) {
+ uint64_t *data;
+
+ ASSERT3U(avl_numnodes(&avl), ==, zfs_btree_numnodes(bt));
+ if (avl_numnodes(&avl) % 2 == 0) {
+ node = avl_first(&avl);
+ data = zfs_btree_first(bt, &bt_idx);
+ } else {
+ node = avl_last(&avl);
+ data = zfs_btree_last(bt, &bt_idx);
+ }
+ ASSERT3U(node->data, ==, *data);
+ zfs_btree_remove_idx(bt, &bt_idx);
+ avl_remove(&avl, node);
+
+ if (avl_numnodes(&avl) == 0) {
+ break;
+ }
+
+ node = avl_first(&avl);
+ ASSERT3U(node->data, ==,
+ *(uint64_t *)zfs_btree_first(bt, NULL));
+ node = avl_last(&avl);
+ ASSERT3U(node->data, ==, *(uint64_t *)zfs_btree_last(bt, NULL));
+ }
+ ASSERT3S(zfs_btree_numnodes(bt), ==, 0);
+
+ void *avl_cookie = NULL;
+ while ((node = avl_destroy_nodes(&avl, &avl_cookie)) != NULL)
+ free(node);
+ avl_destroy(&avl);
+
+ return (0);
+}
+
+/*
+ * This test uses an avl and btree, and continually processes new random
+ * values. Each value is either removed or inserted, depending on whether
+ * or not it is found in the tree. The test periodically checks that both
+ * trees have the same data and does consistency checks. This stress
+ * option can also be run on its own from the command line.
+ */
+static int
+stress_tree(zfs_btree_t *bt, char *why)
+{
+ avl_tree_t avl;
+ int_node_t *node;
+ struct timeval tp;
+ time_t t0;
+ int insertions = 0, removals = 0, iterations = 0;
+ u_longlong_t max = 0, min = UINT64_MAX;
+
+ (void) gettimeofday(&tp, NULL);
+ t0 = tp.tv_sec;
+
+ avl_create(&avl, avl_compare, sizeof (int_node_t),
+ offsetof(int_node_t, node));
+
+ while (1) {
+ zfs_btree_index_t bt_idx = {0};
+ avl_index_t avl_idx = {0};
+
+ uint64_t randval = random() % tree_limit;
+ node = malloc(sizeof (*node));
+ node->data = randval;
+
+ max = randval > max ? randval : max;
+ min = randval < min ? randval : min;
+
+ void *ret = avl_find(&avl, node, &avl_idx);
+ if (ret == NULL) {
+ insertions++;
+ avl_insert(&avl, node, avl_idx);
+ ASSERT3P(zfs_btree_find(bt, &randval, &bt_idx), ==,
+ NULL);
+ zfs_btree_add_idx(bt, &randval, &bt_idx);
+ verify_node(&avl, bt, node);
+ } else {
+ removals++;
+ verify_node(&avl, bt, ret);
+ zfs_btree_remove(bt, &randval);
+ avl_remove(&avl, ret);
+ free(ret);
+ free(node);
+ }
+
+ zfs_btree_verify(bt);
+
+ iterations++;
+ if (iterations % contents_frequency == 0) {
+ verify_contents(&avl, bt);
+ }
+
+ zfs_btree_verify(bt);
+
+ (void) gettimeofday(&tp, NULL);
+ if (tp.tv_sec > t0 + stress_timeout) {
+ fprintf(stderr, "insertions/removals: %u/%u\nmax/min: "
+ "%llu/%llu\n", insertions, removals, max, min);
+ break;
+ }
+ }
+
+ void *avl_cookie = NULL;
+ while ((node = avl_destroy_nodes(&avl, &avl_cookie)) != NULL)
+ free(node);
+ avl_destroy(&avl);
+
+ if (stress_only) {
+ zfs_btree_index_t *idx = NULL;
+ uint64_t *rv;
+
+ while ((rv = zfs_btree_destroy_nodes(bt, &idx)) != NULL)
+ ;
+ zfs_btree_verify(bt);
+ }
+
+ return (0);
+}
+
+/*
+ * Verify inserting a duplicate value will cause a crash.
+ * Note: negative test; return of 0 is a failure.
+ */
+static int
+insert_duplicate(zfs_btree_t *bt)
+{
+ uint64_t *p, i = 23456;
+ zfs_btree_index_t bt_idx = {0};
+
+ if ((p = (uint64_t *)zfs_btree_find(bt, &i, &bt_idx)) != NULL) {
+ fprintf(stderr, "Found value in empty tree.\n");
+ return (0);
+ }
+ zfs_btree_add_idx(bt, &i, &bt_idx);
+ if ((p = (uint64_t *)zfs_btree_find(bt, &i, &bt_idx)) == NULL) {
+ fprintf(stderr, "Did not find expected value.\n");
+ return (0);
+ }
+
+ /* Crash on inserting a duplicate */
+ zfs_btree_add_idx(bt, &i, NULL);
+
+ return (0);
+}
+
+/*
+ * Verify removing a non-existent value will cause a crash.
+ * Note: negative test; return of 0 is a failure.
+ */
+static int
+remove_missing(zfs_btree_t *bt)
+{
+ uint64_t *p, i = 23456;
+ zfs_btree_index_t bt_idx = {0};
+
+ if ((p = (uint64_t *)zfs_btree_find(bt, &i, &bt_idx)) != NULL) {
+ fprintf(stderr, "Found value in empty tree.\n");
+ return (0);
+ }
+
+ /* Crash removing a nonexistent entry */
+ zfs_btree_remove(bt, &i);
+
+ return (0);
+}
+
+static int
+do_negative_test(zfs_btree_t *bt, char *test_name)
+{
+ int rval = 0;
+ struct rlimit rlim = {0};
+ setrlimit(RLIMIT_CORE, &rlim);
+
+ if (strcmp(test_name, "insert_duplicate") == 0) {
+ rval = insert_duplicate(bt);
+ } else if (strcmp(test_name, "remove_missing") == 0) {
+ rval = remove_missing(bt);
+ }
+
+ /*
+ * Return 0, since callers will expect non-zero return values for
+ * these tests, and we should have crashed before getting here anyway.
+ */
+ (void) fprintf(stderr, "Test: %s returned %d.\n", test_name, rval);
+ return (0);
+}
+
+typedef struct btree_test {
+ const char *name;
+ int (*func)(zfs_btree_t *, char *);
+} btree_test_t;
+
+static btree_test_t test_table[] = {
+ { "insert_find_remove", insert_find_remove },
+ { "find_without_index", find_without_index },
+ { "drain_tree", drain_tree },
+ { "stress_tree", stress_tree },
+ { NULL, NULL }
+};
+
+int
+main(int argc, char *argv[])
+{
+ char *negative_test = NULL;
+ int failed_tests = 0;
+ struct timeval tp;
+ zfs_btree_t bt;
+ char c;
+
+ while ((c = getopt(argc, argv, "c:l:n:r:st:")) != -1) {
+ switch (c) {
+ case 'c':
+ contents_frequency = atoi(optarg);
+ break;
+ case 'l':
+ tree_limit = atoi(optarg);
+ break;
+ case 'n':
+ negative_test = optarg;
+ break;
+ case 'r':
+ seed = atoi(optarg);
+ break;
+ case 's':
+ stress_only = B_TRUE;
+ break;
+ case 't':
+ stress_timeout = atoi(optarg);
+ break;
+ case 'h':
+ default:
+ usage(1);
+ break;
+ }
+ }
+ argc -= optind;
+ argv += optind;
+ optind = 1;
+
+
+ if (seed == 0) {
+ (void) gettimeofday(&tp, NULL);
+ seed = tp.tv_sec;
+ }
+ srandom(seed);
+
+ zfs_btree_init();
+ zfs_btree_create(&bt, zfs_btree_compare, sizeof (uint64_t));
+
+ /*
+ * This runs the named negative test. None of them should
+ * return, as they both cause crashes.
+ */
+ if (negative_test) {
+ return (do_negative_test(&bt, negative_test));
+ }
+
+ fprintf(stderr, "Seed: %u\n", seed);
+
+ /*
+ * This is a stress test that does operations on a btree over the
+ * requested timeout period, verifying them against identical
+ * operations in an avl tree.
+ */
+ if (stress_only != 0) {
+ return (stress_tree(&bt, NULL));
+ }
+
+ /* Do the positive tests */
+ btree_test_t *test = &test_table[0];
+ while (test->name) {
+ int retval;
+ uint64_t *rv;
+ char why[BUFSIZE] = {0};
+ zfs_btree_index_t *idx = NULL;
+
+ (void) fprintf(stdout, "%-20s", test->name);
+ retval = test->func(&bt, why);
+
+ if (retval == 0) {
+ (void) fprintf(stdout, "ok\n");
+ } else {
+ (void) fprintf(stdout, "failed with %d\n", retval);
+ if (strlen(why) != 0)
+ (void) fprintf(stdout, "\t%s\n", why);
+ why[0] = '\0';
+ failed_tests++;
+ }
+
+ /* Remove all the elements and re-verify the tree */
+ while ((rv = zfs_btree_destroy_nodes(&bt, &idx)) != NULL)
+ ;
+ zfs_btree_verify(&bt);
+
+ test++;
+ }
+
+ zfs_btree_verify(&bt);
+ zfs_btree_fini();
+
+ return (failed_tests);
+}
generated by cgit v1.2.3 (git 2.25.1) at 2024-04-16 05:35:54 +0000