Tests for btree implementation used by range trees

Additional test cases for the btree implementation, see #9181.

Reviewed-by: Paul Dagnelie <[email protected]>
Reviewed-by: Brian Behlendorf <[email protected]>
Signed-off-by: John Kennedy <[email protected]>
Closes #9717 

10 files changed, 692 insertions, 2 deletions

diff --git a/configure.ac b/configure.ac
index aa5363796..1160897f3 100644
--- a/configure.ac
+++ b/configure.ac
@@ -187,6 +187,7 @@ AC_CONFIG_FILES([
 	tests/zfs-tests/Makefile
 	tests/zfs-tests/callbacks/Makefile
 	tests/zfs-tests/cmd/Makefile
+	tests/zfs-tests/cmd/btree_test/Makefile
 	tests/zfs-tests/cmd/chg_usr_exec/Makefile
 	tests/zfs-tests/cmd/devname2devid/Makefile
 	tests/zfs-tests/cmd/dir_rd_update/Makefile
@@ -222,6 +223,7 @@ AC_CONFIG_FILES([
 	tests/zfs-tests/tests/functional/arc/Makefile
 	tests/zfs-tests/tests/functional/atime/Makefile
 	tests/zfs-tests/tests/functional/bootfs/Makefile
+	tests/zfs-tests/tests/functional/btree/Makefile
 	tests/zfs-tests/tests/functional/cache/Makefile
 	tests/zfs-tests/tests/functional/cachefile/Makefile
 	tests/zfs-tests/tests/functional/casenorm/Makefile
diff --git a/tests/runfiles/common.run b/tests/runfiles/common.run
index 89e4492dd..87849af65 100644
--- a/tests/runfiles/common.run
+++ b/tests/runfiles/common.run
@@ -39,6 +39,12 @@ tests = ['bootfs_001_pos', 'bootfs_002_neg', 'bootfs_003_pos',
     'bootfs_008_pos']
 tags = ['functional', 'bootfs']
 
+[tests/functional/btree]
+tests = ['btree_positive', 'btree_negative']
+tags = ['functional', 'btree']
+pre =
+post =
+
 [tests/functional/cache]
 tests = ['cache_001_pos', 'cache_002_pos', 'cache_003_pos', 'cache_004_neg',
     'cache_005_neg', 'cache_006_pos', 'cache_007_neg', 'cache_008_neg',
diff --git a/tests/zfs-tests/cmd/Makefile.am b/tests/zfs-tests/cmd/Makefile.am
index 934587b1a..20e85cf6b 100644
--- a/tests/zfs-tests/cmd/Makefile.am
+++ b/tests/zfs-tests/cmd/Makefile.am
@@ -1,6 +1,7 @@
 EXTRA_DIST = file_common.h
 
 SUBDIRS = \
+	btree_test \
 	chg_usr_exec \
 	devname2devid \
 	dir_rd_update \
diff --git a/tests/zfs-tests/cmd/btree_test/Makefile.am b/tests/zfs-tests/cmd/btree_test/Makefile.am
new file mode 100644
index 000000000..632f04726
--- /dev/null
+++ b/tests/zfs-tests/cmd/btree_test/Makefile.am
@@ -0,0 +1,32 @@
+#
+# 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 $(top_srcdir)/config/Rules.am
+
+pkgexecdir = $(datadir)/@PACKAGE@/zfs-tests/bin
+
+DEFAULT_INCLUDES += \
+	-I$(top_srcdir)/include \
+	-I$(top_srcdir)/lib/libspl/include
+
+# Unconditionally enable ASSERTs
+AM_CPPFLAGS += -DDEBUG -UNDEBUG
+
+pkgexec_PROGRAMS = btree_test
+btree_test_SOURCES = btree_test.c
+
+btree_test_LDADD = \
+	$(top_builddir)/lib/libavl/libavl.la \
+	$(top_builddir)/lib/libzpool/libzpool.la
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 000000000..e1995c03a
--- /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);
+}
diff --git a/tests/zfs-tests/include/commands.cfg b/tests/zfs-tests/include/commands.cfg
index 6f41a3273..64b34f477 100644
--- a/tests/zfs-tests/include/commands.cfg
+++ b/tests/zfs-tests/include/commands.cfg
@@ -1,5 +1,5 @@
 #
-# Copyright (c) 2016, 2018 by Delphix. All rights reserved.
+# Copyright (c) 2016, 2019 by Delphix. All rights reserved.
 # These variables are used by zfs-tests.sh to constrain which utilities
 # may be used by the suite. The suite will create a directory which is
 # the only element of $PATH and create symlinks from that dir to the
@@ -175,7 +175,8 @@ export ZFS_FILES='zdb
     zgenhostid
     zstreamdump'
 
-export ZFSTEST_FILES='chg_usr_exec
+export ZFSTEST_FILES='btree_test
+    chg_usr_exec
     devname2devid
     dir_rd_update
     file_check
diff --git a/tests/zfs-tests/tests/functional/Makefile.am b/tests/zfs-tests/tests/functional/Makefile.am
index d4e038718..bd484b2da 100644
--- a/tests/zfs-tests/tests/functional/Makefile.am
+++ b/tests/zfs-tests/tests/functional/Makefile.am
@@ -4,6 +4,7 @@ SUBDIRS = \
 	arc \
 	atime \
 	bootfs \
+	btree \
 	cache \
 	cachefile \
 	casenorm \
diff --git a/tests/zfs-tests/tests/functional/btree/Makefile.am b/tests/zfs-tests/tests/functional/btree/Makefile.am
new file mode 100644
index 000000000..333209d98
--- /dev/null
+++ b/tests/zfs-tests/tests/functional/btree/Makefile.am
@@ -0,0 +1,20 @@
+#
+# 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.
+#
+
+pkgdatadir = $(datadir)/@PACKAGE@/zfs-tests/tests/functional/btree
+
+dist_pkgdata_SCRIPTS = \
+	btree_positive.ksh \
+	btree_negative.ksh
diff --git a/tests/zfs-tests/tests/functional/btree/btree_negative.ksh b/tests/zfs-tests/tests/functional/btree/btree_negative.ksh
new file mode 100755
index 000000000..399cd5ee9
--- /dev/null
+++ b/tests/zfs-tests/tests/functional/btree/btree_negative.ksh
@@ -0,0 +1,38 @@
+#!/usr/bin/ksh -p
+
+#
+# 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.
+#
+
+. $STF_SUITE/include/libtest.shlib
+
+#
+# Description:
+# Verify that the btree functions don't allow bad inputs
+#
+# insert_duplicate - Callers may not add values that are already in the tree
+# remove_missing   - Callers may not remove values that are not in the tree
+#
+# Note: These invocations cause btree_test to crash, but the program disables
+# core dumps first. As such, we can't use log_mustnot because it explicitly
+# looks for return values that correspond to a core dump and cause a test
+# failure.
+
+btree_test -n insert_duplicate
+[[ $? -eq 0 ]] && log_fail "Failure from insert_duplicate"
+
+btree_test -n remove_missing
+[[ $? -eq 0 ]] && log_fail "Failure from remove_missing"
+
+log_pass "Btree negative tests passed"
diff --git a/tests/zfs-tests/tests/functional/btree/btree_positive.ksh b/tests/zfs-tests/tests/functional/btree/btree_positive.ksh
new file mode 100755
index 000000000..ec58d37a8
--- /dev/null
+++ b/tests/zfs-tests/tests/functional/btree/btree_positive.ksh
@@ -0,0 +1,35 @@
+#!/usr/bin/ksh -p
+
+#
+# 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.
+#
+
+. $STF_SUITE/include/libtest.shlib
+
+#
+# Description:
+# The `btree_test` binary runs a series of positive tests when called
+# without arguments.
+#
+# insert_find_remove - Basic functionality test
+# find_without_index - Using the find function with a NULL argument
+# drain_tree         - Fill the tree then empty it using the first and last
+#                      functions
+# stress_tree        - Allow the tree to have items added and removed for a
+#                      given amount of time
+#
+
+log_must btree_test
+
+log_pass "Btree positive tests passed"