summaryrefslogtreecommitdiff
path: root/test/unit
diff options
context:
space:
mode:
Diffstat (limited to 'test/unit')
-rw-r--r--test/unit/Makefile65
-rw-r--r--test/unit/Makefile.in33
-rw-r--r--test/unit/bcache_t.c1036
-rw-r--r--test/unit/bcache_utils_t.c474
-rw-r--r--test/unit/bitset_t.c99
-rw-r--r--test/unit/config_t.c154
-rw-r--r--test/unit/dmlist_t.c49
-rw-r--r--test/unit/dmstatus_t.c84
-rw-r--r--test/unit/framework.c66
-rw-r--r--test/unit/framework.h51
-rw-r--r--test/unit/io_engine_t.c229
-rw-r--r--test/unit/matcher_t.c122
-rw-r--r--test/unit/percent_t.c102
-rw-r--r--test/unit/radix_tree_t.c852
-rw-r--r--test/unit/rt_case1.c1669
-rw-r--r--test/unit/run.c335
-rw-r--r--test/unit/string_t.c72
-rw-r--r--test/unit/unit-test.sh21
-rw-r--r--test/unit/units.h55
-rw-r--r--test/unit/vdo_t.c325
20 files changed, 5662 insertions, 231 deletions
diff --git a/test/unit/Makefile b/test/unit/Makefile
new file mode 100644
index 0000000..05e2501
--- /dev/null
+++ b/test/unit/Makefile
@@ -0,0 +1,65 @@
+# Copyright (C) 2011-2018 Red Hat, Inc. All rights reserved.
+#
+# This file is part of LVM2.
+#
+# This copyrighted material is made available to anyone wishing to use,
+# modify, copy, or redistribute it subject to the terms and conditions
+# of the GNU General Public License v.2.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software Foundation,
+# Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+# NOTE: this Makefile only works as 'include' for toplevel Makefile
+# which defined all top_* variables
+
+UNIT_SOURCE=\
+ device_mapper/vdo/status.c \
+ \
+ test/unit/bcache_t.c \
+ test/unit/bcache_utils_t.c \
+ test/unit/bitset_t.c \
+ test/unit/config_t.c \
+ test/unit/dmlist_t.c \
+ test/unit/dmstatus_t.c \
+ test/unit/framework.c \
+ test/unit/io_engine_t.c \
+ test/unit/matcher_t.c \
+ test/unit/percent_t.c \
+ test/unit/radix_tree_t.c \
+ test/unit/run.c \
+ test/unit/string_t.c \
+ test/unit/vdo_t.c
+
+test/unit/radix_tree_t.o: test/unit/rt_case1.c
+
+UNIT_TARGET = test/unit/unit-test
+UNIT_DEPENDS = $(UNIT_SOURCE:%.c=%.d)
+UNIT_OBJECTS = $(UNIT_SOURCE:%.c=%.o)
+CLEAN_TARGETS += $(UNIT_DEPENDS) $(UNIT_OBJECTS) \
+ $(UNIT_SOURCE:%.c=%.gcda) \
+ $(UNIT_SOURCE:%.c=%.gcno) \
+ $(UNIT_TARGET)
+
+lib/liblvm-internal.a: lib
+libdaemon/client/libdaemonclient.a: libdaemon
+
+$(UNIT_TARGET): $(UNIT_OBJECTS) $(LVMINTERNAL_LIBS)
+ @echo " [LD] $@"
+ $(Q) $(CC) $(CFLAGS) $(LDFLAGS) $(EXTRA_EXEC_LDFLAGS) \
+ -o $@ $+ $(LVMLIBS)
+
+.PHONY: run-unit-test unit-test
+unit-test: $(UNIT_TARGET)
+run-unit-test: $(UNIT_TARGET)
+ @echo "Running unit tests"
+ test -n "$$LVM_TEST_DIR" || LVM_TEST_DIR=$${TMPDIR:-/tmp} ;\
+ TESTDIR=$$(mktemp -d -t -p "$$LVM_TEST_DIR" "LVMTEST.XXXXXXXXXX") ;\
+ cd "$$TESTDIR" ;\
+ LD_LIBRARY_PATH=$(abs_top_builddir)/libdm:$(abs_top_builddir)/daemons/dmeventd $(abs_top_builddir)/$(UNIT_TARGET) run ;\
+ cd $$OLDPWD ;\
+ $(RM) -r "$${TESTDIR:?}"
+
+ifeq ("$(DEPENDS)","yes")
+-include $(UNIT_SOURCE:%.c=%.d)
+endif
diff --git a/test/unit/Makefile.in b/test/unit/Makefile.in
deleted file mode 100644
index 740eb14..0000000
--- a/test/unit/Makefile.in
+++ /dev/null
@@ -1,33 +0,0 @@
-# Copyright (C) 2011-2012 Red Hat, Inc. All rights reserved.
-#
-# This file is part of LVM2.
-#
-# This copyrighted material is made available to anyone wishing to use,
-# modify, copy, or redistribute it subject to the terms and conditions
-# of the GNU General Public License v.2.
-#
-# You should have received a copy of the GNU General Public License
-# along with this program; if not, write to the Free Software Foundation,
-# Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
-
-srcdir = @srcdir@
-top_srcdir = @top_srcdir@
-top_builddir = @top_builddir@
-
-VPATH = $(srcdir)
-ifeq ("@TESTING@", "yes")
-SOURCES = bitset_t.c matcher_t.c config_t.c string_t.c run.c
-TARGETS = run
-endif
-
-include $(top_builddir)/make.tmpl
-ifeq ("$(TESTING)", "yes")
-LDLIBS += -ldevmapper @CUNIT_LIBS@
-CFLAGS += @CUNIT_CFLAGS@
-
-check: unit
-
-unit: $(TARGETS)
- @echo Running unit tests
- LD_LIBRARY_PATH=$(top_builddir)/libdm ./$(TARGETS)
-endif
diff --git a/test/unit/bcache_t.c b/test/unit/bcache_t.c
new file mode 100644
index 0000000..2668d3f
--- /dev/null
+++ b/test/unit/bcache_t.c
@@ -0,0 +1,1036 @@
+/*
+ * Copyright (C) 2018 Red Hat, Inc. All rights reserved.
+ *
+ * This file is part of LVM2.
+ *
+ * This copyrighted material is made available to anyone wishing to use,
+ * modify, copy, or redistribute it subject to the terms and conditions
+ * of the GNU General Public License v.2.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include "units.h"
+#include "lib/device/bcache.h"
+
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <unistd.h>
+
+#define SHOW_MOCK_CALLS 0
+
+/*----------------------------------------------------------------
+ * Mock engine
+ *--------------------------------------------------------------*/
+struct mock_engine {
+ struct io_engine e;
+ struct dm_list expected_calls;
+ struct dm_list issued_io;
+ unsigned max_io;
+ sector_t block_size;
+};
+
+enum method {
+ E_DESTROY,
+ E_ISSUE,
+ E_WAIT,
+ E_MAX_IO
+};
+
+struct mock_call {
+ struct dm_list list;
+ enum method m;
+
+ bool match_args;
+ enum dir d;
+ int di;
+ block_address b;
+ bool issue_r;
+ bool wait_r;
+};
+
+struct mock_io {
+ struct dm_list list;
+ int di;
+ sector_t sb;
+ sector_t se;
+ void *data;
+ void *context;
+ bool r;
+};
+
+static const char *_show_method(enum method m)
+{
+ switch (m) {
+ case E_DESTROY:
+ return "destroy()";
+ case E_ISSUE:
+ return "issue()";
+ case E_WAIT:
+ return "wait()";
+ case E_MAX_IO:
+ return "max_io()";
+ }
+
+ return "<unknown>";
+}
+
+static void _expect(struct mock_engine *e, enum method m)
+{
+ struct mock_call *mc = malloc(sizeof(*mc));
+
+ T_ASSERT(mc);
+ mc->m = m;
+ mc->match_args = false;
+ dm_list_add(&e->expected_calls, &mc->list);
+}
+
+static void _expect_read(struct mock_engine *e, int di, block_address b)
+{
+ struct mock_call *mc = malloc(sizeof(*mc));
+
+ T_ASSERT(mc);
+ mc->m = E_ISSUE;
+ mc->match_args = true;
+ mc->d = DIR_READ;
+ mc->di = di;
+ mc->b = b;
+ mc->issue_r = true;
+ mc->wait_r = true;
+ dm_list_add(&e->expected_calls, &mc->list);
+}
+
+static void _expect_read_any(struct mock_engine *e)
+{
+ struct mock_call *mc = malloc(sizeof(*mc));
+
+ T_ASSERT(mc);
+ mc->m = E_ISSUE;
+ mc->match_args = false;
+ mc->issue_r = true;
+ mc->wait_r = true;
+ dm_list_add(&e->expected_calls, &mc->list);
+}
+
+static void _expect_write(struct mock_engine *e, int di, block_address b)
+{
+ struct mock_call *mc = malloc(sizeof(*mc));
+
+ T_ASSERT(mc);
+ mc->m = E_ISSUE;
+ mc->match_args = true;
+ mc->d = DIR_WRITE;
+ mc->di = di;
+ mc->b = b;
+ mc->issue_r = true;
+ mc->wait_r = true;
+ dm_list_add(&e->expected_calls, &mc->list);
+}
+
+static void _expect_read_bad_issue(struct mock_engine *e, int di, block_address b)
+{
+ struct mock_call *mc = malloc(sizeof(*mc));
+
+ T_ASSERT(mc);
+ mc->m = E_ISSUE;
+ mc->match_args = true;
+ mc->d = DIR_READ;
+ mc->di = di;
+ mc->b = b;
+ mc->issue_r = false;
+ mc->wait_r = true;
+ dm_list_add(&e->expected_calls, &mc->list);
+}
+
+static void _expect_write_bad_issue(struct mock_engine *e, int di, block_address b)
+{
+ struct mock_call *mc = malloc(sizeof(*mc));
+
+ T_ASSERT(mc);
+ mc->m = E_ISSUE;
+ mc->match_args = true;
+ mc->d = DIR_WRITE;
+ mc->di = di;
+ mc->b = b;
+ mc->issue_r = false;
+ mc->wait_r = true;
+ dm_list_add(&e->expected_calls, &mc->list);
+}
+
+static void _expect_read_bad_wait(struct mock_engine *e, int di, block_address b)
+{
+ struct mock_call *mc = malloc(sizeof(*mc));
+
+ T_ASSERT(mc);
+ mc->m = E_ISSUE;
+ mc->match_args = true;
+ mc->d = DIR_READ;
+ mc->di = di;
+ mc->b = b;
+ mc->issue_r = true;
+ mc->wait_r = false;
+ dm_list_add(&e->expected_calls, &mc->list);
+}
+
+static void _expect_write_bad_wait(struct mock_engine *e, int di, block_address b)
+{
+ struct mock_call *mc = malloc(sizeof(*mc));
+
+ T_ASSERT(mc);
+ mc->m = E_ISSUE;
+ mc->match_args = true;
+ mc->d = DIR_WRITE;
+ mc->di = di;
+ mc->b = b;
+ mc->issue_r = true;
+ mc->wait_r = false;
+ dm_list_add(&e->expected_calls, &mc->list);
+}
+
+static struct mock_call *_match_pop(struct mock_engine *e, enum method m)
+{
+
+ struct mock_call *mc;
+
+ if (dm_list_empty(&e->expected_calls))
+ test_fail("unexpected call to method %s\n", _show_method(m));
+
+ mc = dm_list_item(e->expected_calls.n, struct mock_call);
+ dm_list_del(&mc->list);
+
+ if (mc->m != m)
+ test_fail("expected %s, but got %s\n", _show_method(mc->m), _show_method(m));
+#if SHOW_MOCK_CALLS
+ else
+ fprintf(stderr, "%s called (expected)\n", _show_method(m));
+#endif
+
+ return mc;
+}
+
+static void _match(struct mock_engine *e, enum method m)
+{
+ free(_match_pop(e, m));
+}
+
+static void _no_outstanding_expectations(struct mock_engine *e)
+{
+ struct mock_call *mc;
+
+ if (!dm_list_empty(&e->expected_calls)) {
+ fprintf(stderr, "unsatisfied expectations:\n");
+ dm_list_iterate_items (mc, &e->expected_calls)
+ fprintf(stderr, " %s\n", _show_method(mc->m));
+ }
+ T_ASSERT(dm_list_empty(&e->expected_calls));
+}
+
+static struct mock_engine *_to_mock(struct io_engine *e)
+{
+ return container_of(e, struct mock_engine, e);
+}
+
+static void _mock_destroy(struct io_engine *e)
+{
+ struct mock_engine *me = _to_mock(e);
+
+ _match(me, E_DESTROY);
+ T_ASSERT(dm_list_empty(&me->issued_io));
+ T_ASSERT(dm_list_empty(&me->expected_calls));
+ free(_to_mock(e));
+}
+
+static bool _mock_issue(struct io_engine *e, enum dir d, int di,
+ sector_t sb, sector_t se, void *data, void *context)
+{
+ bool r, wait_r;
+ struct mock_io *io;
+ struct mock_call *mc;
+ struct mock_engine *me = _to_mock(e);
+
+ mc = _match_pop(me, E_ISSUE);
+ if (mc->match_args) {
+ T_ASSERT(d == mc->d);
+ T_ASSERT(di == mc->di);
+ T_ASSERT(sb == mc->b * me->block_size);
+ T_ASSERT(se == (mc->b + 1) * me->block_size);
+ }
+ r = mc->issue_r;
+ wait_r = mc->wait_r;
+ free(mc);
+
+ if (r) {
+ io = malloc(sizeof(*io));
+ if (!io)
+ abort();
+
+ io->di = di;
+ io->sb = sb;
+ io->se = se;
+ io->data = data;
+ io->context = context;
+ io->r = wait_r;
+
+ dm_list_add(&me->issued_io, &io->list);
+ }
+
+ return r;
+}
+
+static bool _mock_wait(struct io_engine *e, io_complete_fn fn)
+{
+ struct mock_io *io;
+ struct mock_engine *me = _to_mock(e);
+ _match(me, E_WAIT);
+
+ // FIXME: provide a way to control how many are completed and whether
+ // they error.
+ T_ASSERT(!dm_list_empty(&me->issued_io));
+ io = dm_list_item(me->issued_io.n, struct mock_io);
+ dm_list_del(&io->list);
+ fn(io->context, io->r ? 0 : -EIO);
+ free(io);
+
+ return true;
+}
+
+static unsigned _mock_max_io(struct io_engine *e)
+{
+ struct mock_engine *me = _to_mock(e);
+ _match(me, E_MAX_IO);
+ return me->max_io;
+}
+
+static struct mock_engine *_mock_create(unsigned max_io, sector_t block_size)
+{
+ struct mock_engine *m = malloc(sizeof(*m));
+
+ T_ASSERT(m);
+
+ m->e.destroy = _mock_destroy;
+ m->e.issue = _mock_issue;
+ m->e.wait = _mock_wait;
+ m->e.max_io = _mock_max_io;
+
+ m->max_io = max_io;
+ m->block_size = block_size;
+ dm_list_init(&m->expected_calls);
+ dm_list_init(&m->issued_io);
+
+ return m;
+}
+
+/*----------------------------------------------------------------
+ * Fixtures
+ *--------------------------------------------------------------*/
+struct fixture {
+ struct mock_engine *me;
+ struct bcache *cache;
+};
+
+static struct fixture *_fixture_init(sector_t block_size, unsigned nr_cache_blocks)
+{
+ struct fixture *f = malloc(sizeof(*f));
+
+ T_ASSERT(f);
+
+ f->me = _mock_create(16, block_size);
+ T_ASSERT(f->me);
+
+ _expect(f->me, E_MAX_IO);
+ f->cache = bcache_create(block_size, nr_cache_blocks, &f->me->e);
+ T_ASSERT(f->cache);
+
+ return f;
+}
+
+static void _fixture_exit(struct fixture *f)
+{
+ if (f) {
+ _expect(f->me, E_DESTROY);
+ bcache_destroy(f->cache);
+
+ free(f);
+ }
+}
+
+static void *_small_fixture_init(void)
+{
+ return _fixture_init(128, 16);
+}
+
+static void _small_fixture_exit(void *context)
+{
+ _fixture_exit(context);
+}
+
+static void *_large_fixture_init(void)
+{
+ return _fixture_init(128, 1024);
+}
+
+static void _large_fixture_exit(void *context)
+{
+ _fixture_exit(context);
+}
+
+/*----------------------------------------------------------------
+ * Tests
+ *--------------------------------------------------------------*/
+#define MEG 2048
+#define SECTOR_SHIFT 9
+#define PAGE_SIZE_SECTORS ((PAGE_SIZE) >> SECTOR_SHIFT)
+
+static void good_create(sector_t block_size, unsigned nr_cache_blocks)
+{
+ struct bcache *cache;
+ struct mock_engine *me = _mock_create(16, 128);
+
+ _expect(me, E_MAX_IO);
+ cache = bcache_create(block_size, nr_cache_blocks, &me->e);
+ T_ASSERT(cache);
+
+ _expect(me, E_DESTROY);
+ bcache_destroy(cache);
+}
+
+static void bad_create(sector_t block_size, unsigned nr_cache_blocks)
+{
+ struct bcache *cache;
+ struct mock_engine *me = _mock_create(16, 128);
+
+ _expect(me, E_MAX_IO);
+ cache = bcache_create(block_size, nr_cache_blocks, &me->e);
+ T_ASSERT(!cache);
+
+ _expect(me, E_DESTROY);
+ me->e.destroy(&me->e);
+}
+
+static void test_create(void *fixture)
+{
+ good_create(PAGE_SIZE_SECTORS, 16);
+}
+
+static void test_nr_cache_blocks_must_be_positive(void *fixture)
+{
+ bad_create(PAGE_SIZE_SECTORS, 0);
+}
+
+static void test_block_size_must_be_positive(void *fixture)
+{
+ bad_create(0, 16);
+}
+
+static void test_block_size_must_be_multiple_of_page_size(void *fixture)
+{
+ static unsigned _bad_examples[] = {3, 9, 13, 1025};
+
+ unsigned i;
+
+ for (i = 0; i < DM_ARRAY_SIZE(_bad_examples); i++)
+ bad_create(_bad_examples[i], 16);
+
+ for (i = 1; i < 100; i++)
+ good_create(i * PAGE_SIZE_SECTORS, 16);
+}
+
+static void test_get_triggers_read(void *context)
+{
+ struct fixture *f = context;
+
+ int di = 17; // arbitrary key
+ struct block *b;
+
+ _expect_read(f->me, di, 0);
+ _expect(f->me, E_WAIT);
+ T_ASSERT(bcache_get(f->cache, di, 0, 0, &b));
+ bcache_put(b);
+
+ _expect_read(f->me, di, 1);
+ _expect(f->me, E_WAIT);
+ T_ASSERT(bcache_get(f->cache, di, 1, GF_DIRTY, &b));
+ _expect_write(f->me, di, 1);
+ _expect(f->me, E_WAIT);
+ bcache_put(b);
+}
+
+static void test_repeated_reads_are_cached(void *context)
+{
+ struct fixture *f = context;
+
+ int di = 17; // arbitrary key
+ unsigned i;
+ struct block *b;
+
+ _expect_read(f->me, di, 0);
+ _expect(f->me, E_WAIT);
+ for (i = 0; i < 100; i++) {
+ T_ASSERT(bcache_get(f->cache, di, 0, 0, &b));
+ bcache_put(b);
+ }
+}
+
+static void test_block_gets_evicted_with_many_reads(void *context)
+{
+ struct fixture *f = context;
+
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+ const unsigned nr_cache_blocks = 16;
+
+ int di = 17; // arbitrary key
+ unsigned i;
+ struct block *b;
+
+ for (i = 0; i < nr_cache_blocks; i++) {
+ _expect_read(me, di, i);
+ _expect(me, E_WAIT);
+ T_ASSERT(bcache_get(cache, di, i, 0, &b));
+ bcache_put(b);
+ }
+
+ // Not enough cache blocks to hold this one
+ _expect_read(me, di, nr_cache_blocks);
+ _expect(me, E_WAIT);
+ T_ASSERT(bcache_get(cache, di, nr_cache_blocks, 0, &b));
+ bcache_put(b);
+
+ // Now if we run through we should find one block has been
+ // evicted. We go backwards because the oldest is normally
+ // evicted first.
+ _expect_read_any(me);
+ _expect(me, E_WAIT);
+ for (i = nr_cache_blocks; i; i--) {
+ T_ASSERT(bcache_get(cache, di, i - 1, 0, &b));
+ bcache_put(b);
+ }
+}
+
+static void test_prefetch_issues_a_read(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+ const unsigned nr_cache_blocks = 16;
+
+ int di = 17; // arbitrary key
+ unsigned i;
+ struct block *b;
+
+ for (i = 0; i < nr_cache_blocks; i++) {
+ // prefetch should not wait
+ _expect_read(me, di, i);
+ bcache_prefetch(cache, di, i);
+ }
+ _no_outstanding_expectations(me);
+
+ for (i = 0; i < nr_cache_blocks; i++) {
+ _expect(me, E_WAIT);
+ T_ASSERT(bcache_get(cache, di, i, 0, &b));
+ bcache_put(b);
+ }
+}
+
+static void test_too_many_prefetches_does_not_trigger_a_wait(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+
+ const unsigned nr_cache_blocks = 16;
+ int di = 17; // arbitrary key
+ unsigned i;
+
+ for (i = 0; i < 10 * nr_cache_blocks; i++) {
+ // prefetch should not wait
+ if (i < nr_cache_blocks)
+ _expect_read(me, di, i);
+ bcache_prefetch(cache, di, i);
+ }
+
+ // Destroy will wait for any in flight IO triggered by prefetches.
+ for (i = 0; i < nr_cache_blocks; i++)
+ _expect(me, E_WAIT);
+}
+
+static void test_dirty_data_gets_written_back(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+
+ int di = 17; // arbitrary key
+ struct block *b;
+
+ // Expect the read
+ _expect_read(me, di, 0);
+ _expect(me, E_WAIT);
+ T_ASSERT(bcache_get(cache, di, 0, GF_DIRTY, &b));
+ bcache_put(b);
+
+ // Expect the write
+ _expect_write(me, di, 0);
+ _expect(me, E_WAIT);
+}
+
+static void test_zeroed_data_counts_as_dirty(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+
+ int di = 17; // arbitrary key
+ struct block *b;
+
+ // No read
+ T_ASSERT(bcache_get(cache, di, 0, GF_ZERO, &b));
+ bcache_put(b);
+
+ // Expect the write
+ _expect_write(me, di, 0);
+ _expect(me, E_WAIT);
+}
+
+static void test_flush_waits_for_all_dirty(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+
+ const unsigned count = 16;
+ int di = 17; // arbitrary key
+ unsigned i;
+ struct block *b;
+
+ for (i = 0; i < count; i++) {
+ if (i % 2) {
+ T_ASSERT(bcache_get(cache, di, i, GF_ZERO, &b));
+ } else {
+ _expect_read(me, di, i);
+ _expect(me, E_WAIT);
+ T_ASSERT(bcache_get(cache, di, i, 0, &b));
+ }
+ bcache_put(b);
+ }
+
+ for (i = 0; i < count; i++) {
+ if (i % 2)
+ _expect_write(me, di, i);
+ }
+
+ for (i = 0; i < count; i++) {
+ if (i % 2)
+ _expect(me, E_WAIT);
+ }
+
+ T_ASSERT(bcache_flush(cache));
+ _no_outstanding_expectations(me);
+}
+
+static void test_multiple_files(void *context)
+{
+ static int _dis[] = {1, 128, 345, 678, 890};
+
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+ struct block *b;
+ unsigned i;
+
+ for (i = 0; i < DM_ARRAY_SIZE(_dis); i++) {
+ _expect_read(me, _dis[i], 0);
+ _expect(me, E_WAIT);
+
+ T_ASSERT(bcache_get(cache, _dis[i], 0, 0, &b));
+ bcache_put(b);
+ }
+}
+
+static void test_read_bad_issue(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+ struct block *b;
+
+ _expect_read_bad_issue(me, 17, 0);
+ T_ASSERT(!bcache_get(cache, 17, 0, 0, &b));
+}
+
+static void test_read_bad_issue_intermittent(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+ struct block *b;
+ int di = 17;
+
+ _expect_read_bad_issue(me, di, 0);
+ T_ASSERT(!bcache_get(cache, di, 0, 0, &b));
+
+ _expect_read(me, di, 0);
+ _expect(me, E_WAIT);
+ T_ASSERT(bcache_get(cache, di, 0, 0, &b));
+ bcache_put(b);
+}
+
+static void test_read_bad_wait(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+ struct block *b;
+ int di = 17;
+
+ _expect_read_bad_wait(me, di, 0);
+ _expect(me, E_WAIT);
+ T_ASSERT(!bcache_get(cache, di, 0, 0, &b));
+}
+
+static void test_read_bad_wait_intermittent(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+ struct block *b;
+ int di = 17;
+
+ _expect_read_bad_wait(me, di, 0);
+ _expect(me, E_WAIT);
+ T_ASSERT(!bcache_get(cache, di, 0, 0, &b));
+
+ _expect_read(me, di, 0);
+ _expect(me, E_WAIT);
+ T_ASSERT(bcache_get(cache, di, 0, 0, &b));
+ bcache_put(b);
+}
+
+static void test_write_bad_issue_stops_flush(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+ struct block *b;
+ int di = 17;
+
+ T_ASSERT(bcache_get(cache, di, 0, GF_ZERO, &b));
+ _expect_write_bad_issue(me, di, 0);
+ bcache_put(b);
+ T_ASSERT(!bcache_flush(cache));
+
+ // we'll let it succeed the second time
+ _expect_write(me, di, 0);
+ _expect(me, E_WAIT);
+ T_ASSERT(bcache_flush(cache));
+}
+
+static void test_write_bad_io_stops_flush(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+ struct block *b;
+ int di = 17;
+
+ T_ASSERT(bcache_get(cache, di, 0, GF_ZERO, &b));
+ _expect_write_bad_wait(me, di, 0);
+ _expect(me, E_WAIT);
+ bcache_put(b);
+ T_ASSERT(!bcache_flush(cache));
+
+ // we'll let it succeed the second time
+ _expect_write(me, di, 0);
+ _expect(me, E_WAIT);
+ T_ASSERT(bcache_flush(cache));
+}
+
+static void test_invalidate_not_present(void *context)
+{
+ struct fixture *f = context;
+ struct bcache *cache = f->cache;
+ int di = 17;
+
+ T_ASSERT(bcache_invalidate(cache, di, 0));
+}
+
+static void test_invalidate_present(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+ struct block *b;
+ int di = 17;
+
+ _expect_read(me, di, 0);
+ _expect(me, E_WAIT);
+ T_ASSERT(bcache_get(cache, di, 0, 0, &b));
+ bcache_put(b);
+
+ T_ASSERT(bcache_invalidate(cache, di, 0));
+}
+
+static void test_invalidate_after_read_error(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+ struct block *b;
+ int di = 17;
+
+ _expect_read_bad_issue(me, di, 0);
+ T_ASSERT(!bcache_get(cache, di, 0, 0, &b));
+ T_ASSERT(bcache_invalidate(cache, di, 0));
+}
+
+static void test_invalidate_after_write_error(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+ struct block *b;
+ int di = 17;
+
+ T_ASSERT(bcache_get(cache, di, 0, GF_ZERO, &b));
+ bcache_put(b);
+
+ // invalidate should fail if the write fails
+ _expect_write_bad_wait(me, di, 0);
+ _expect(me, E_WAIT);
+ T_ASSERT(!bcache_invalidate(cache, di, 0));
+
+ // and should succeed if the write does
+ _expect_write(me, di, 0);
+ _expect(me, E_WAIT);
+ T_ASSERT(bcache_invalidate(cache, di, 0));
+
+ // a read is not required to get the block
+ _expect_read(me, di, 0);
+ _expect(me, E_WAIT);
+ T_ASSERT(bcache_get(cache, di, 0, 0, &b));
+ bcache_put(b);
+}
+
+static void test_invalidate_held_block(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+ struct block *b;
+ int di = 17;
+
+ T_ASSERT(bcache_get(cache, di, 0, GF_ZERO, &b));
+
+ T_ASSERT(!bcache_invalidate(cache, di, 0));
+
+ _expect_write(me, di, 0);
+ _expect(me, E_WAIT);
+ bcache_put(b);
+}
+
+//----------------------------------------------------------------
+// abort tests
+
+static void test_abort_no_blocks(void *context)
+{
+ struct fixture *f = context;
+ struct bcache *cache = f->cache;
+ int di = 17;
+
+ // We have no expectations
+ bcache_abort_di(cache, di);
+}
+
+static void test_abort_single_block(void *context)
+{
+ struct fixture *f = context;
+ struct bcache *cache = f->cache;
+ struct block *b;
+ int di = 17;
+
+ T_ASSERT(bcache_get(cache, di, 0, GF_ZERO, &b));
+ bcache_put(b);
+
+ bcache_abort_di(cache, di);
+
+ // no write should be issued
+ T_ASSERT(bcache_flush(cache));
+}
+
+static void test_abort_forces_reread(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+ struct block *b;
+ int di = 17;
+
+ _expect_read(me, di, 0);
+ _expect(me, E_WAIT);
+ T_ASSERT(bcache_get(cache, di, 0, GF_DIRTY, &b));
+ bcache_put(b);
+
+ bcache_abort_di(cache, di);
+ T_ASSERT(bcache_flush(cache));
+
+ // Check the block is re-read
+ _expect_read(me, di, 0);
+ _expect(me, E_WAIT);
+ T_ASSERT(bcache_get(cache, di, 0, 0, &b));
+ bcache_put(b);
+}
+
+static void test_abort_only_specific_di(void *context)
+{
+ struct fixture *f = context;
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+ struct block *b;
+ int di1 = 17, di2 = 18;
+
+ T_ASSERT(bcache_get(cache, di1, 0, GF_ZERO, &b));
+ bcache_put(b);
+
+ T_ASSERT(bcache_get(cache, di1, 1, GF_ZERO, &b));
+ bcache_put(b);
+
+ T_ASSERT(bcache_get(cache, di2, 0, GF_ZERO, &b));
+ bcache_put(b);
+
+ T_ASSERT(bcache_get(cache, di2, 1, GF_ZERO, &b));
+ bcache_put(b);
+
+ bcache_abort_di(cache, di2);
+
+ // writes for di1 should still be issued
+ _expect_write(me, di1, 0);
+ _expect_write(me, di1, 1);
+
+ _expect(me, E_WAIT);
+ _expect(me, E_WAIT);
+
+ T_ASSERT(bcache_flush(cache));
+}
+
+//----------------------------------------------------------------
+// Chasing a bug reported by dct
+
+static void _cycle(struct fixture *f, unsigned nr_cache_blocks)
+{
+ struct mock_engine *me = f->me;
+ struct bcache *cache = f->cache;
+
+ unsigned i;
+ struct block *b;
+
+ for (i = 0; i < nr_cache_blocks; i++) {
+ // prefetch should not wait
+ _expect_read(me, i, 0);
+ bcache_prefetch(cache, i, 0);
+ }
+
+ // This double checks the reads occur in response to the prefetch
+ _no_outstanding_expectations(me);
+
+ for (i = 0; i < nr_cache_blocks; i++) {
+ _expect(me, E_WAIT);
+ T_ASSERT(bcache_get(cache, i, 0, 0, &b));
+ bcache_put(b);
+ }
+
+ _no_outstanding_expectations(me);
+}
+
+static void test_concurrent_reads_after_invalidate(void *context)
+{
+ struct fixture *f = context;
+ unsigned i, nr_cache_blocks = 16;
+
+ _cycle(f, nr_cache_blocks);
+ for (i = 0; i < nr_cache_blocks; i++)
+ bcache_invalidate_di(f->cache, i);
+ _cycle(f, nr_cache_blocks);
+}
+
+/*----------------------------------------------------------------
+ * Top level
+ *--------------------------------------------------------------*/
+#define T(path, desc, fn) register_test(ts, "/base/device/bcache/" path, desc, fn)
+
+static struct test_suite *_tiny_tests(void)
+{
+ struct test_suite *ts = test_suite_create(NULL, NULL);
+ if (!ts) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+
+ T("create-destroy", "simple create/destroy", test_create);
+ T("cache-blocks-positive", "nr cache blocks must be positive", test_nr_cache_blocks_must_be_positive);
+ T("block-size-positive", "block size must be positive", test_block_size_must_be_positive);
+ T("block-size-multiple-page", "block size must be a multiple of page size", test_block_size_must_be_multiple_of_page_size);
+
+ return ts;
+}
+
+static struct test_suite *_small_tests(void)
+{
+ struct test_suite *ts = test_suite_create(_small_fixture_init, _small_fixture_exit);
+ if (!ts) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+
+ T("get-reads", "bcache_get() triggers read", test_get_triggers_read);
+ T("reads-cached", "repeated reads are cached", test_repeated_reads_are_cached);
+ T("blocks-get-evicted", "block get evicted with many reads", test_block_gets_evicted_with_many_reads);
+ T("prefetch-reads", "prefetch issues a read", test_prefetch_issues_a_read);
+ T("prefetch-never-waits", "too many prefetches does not trigger a wait", test_too_many_prefetches_does_not_trigger_a_wait);
+ T("writeback-occurs", "dirty data gets written back", test_dirty_data_gets_written_back);
+ T("zero-flag-dirties", "zeroed data counts as dirty", test_zeroed_data_counts_as_dirty);
+ T("read-multiple-files", "read from multiple files", test_multiple_files);
+ T("read-bad-issue", "read fails if io engine unable to issue", test_read_bad_issue);
+ T("read-bad-issue-intermittent", "failed issue, followed by succes", test_read_bad_issue_intermittent);
+ T("read-bad-io", "read issued ok, but io fails", test_read_bad_wait);
+ T("read-bad-io-intermittent", "failed io, followed by success", test_read_bad_wait_intermittent);
+ T("write-bad-issue-stops-flush", "flush fails temporarily if any block fails to write", test_write_bad_issue_stops_flush);
+ T("write-bad-io-stops-flush", "flush fails temporarily if any block fails to write", test_write_bad_io_stops_flush);
+ T("invalidate-not-present", "invalidate a block that isn't in the cache", test_invalidate_not_present);
+ T("invalidate-present", "invalidate a block that is in the cache", test_invalidate_present);
+ T("invalidate-read-error", "invalidate a block that errored", test_invalidate_after_read_error);
+ T("invalidate-write-error", "invalidate a block that errored", test_invalidate_after_write_error);
+ T("invalidate-fails-in-held", "invalidating a held block fails", test_invalidate_held_block);
+
+ T("abort-with-no-blocks", "you can call abort, even if there are no blocks in the cache", test_abort_no_blocks);
+ T("abort-single-block", "single block get silently discarded", test_abort_single_block);
+ T("abort-forces-read", "if a block has been discarded then another read is necc.", test_abort_forces_reread);
+ T("abort-specific-di", "abort doesn't effect other dis", test_abort_only_specific_di);
+
+ T("concurrent-reads-after-invalidate", "prefetch should still issue concurrent reads after invalidate",
+ test_concurrent_reads_after_invalidate);
+
+ return ts;
+}
+
+static struct test_suite *_large_tests(void)
+{
+ struct test_suite *ts = test_suite_create(_large_fixture_init, _large_fixture_exit);
+ if (!ts) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+
+ T("flush-waits", "flush waits for all dirty", test_flush_waits_for_all_dirty);
+
+ return ts;
+}
+
+void bcache_tests(struct dm_list *all_tests)
+{
+ dm_list_add(all_tests, &_tiny_tests()->list);
+ dm_list_add(all_tests, &_small_tests()->list);
+ dm_list_add(all_tests, &_large_tests()->list);
+}
diff --git a/test/unit/bcache_utils_t.c b/test/unit/bcache_utils_t.c
new file mode 100644
index 0000000..f052924
--- /dev/null
+++ b/test/unit/bcache_utils_t.c
@@ -0,0 +1,474 @@
+/*
+ * Copyright (C) 2018 Red Hat, Inc. All rights reserved.
+ *
+ * This file is part of LVM2.
+ *
+ * This copyrighted material is made available to anyone wishing to use,
+ * modify, copy, or redistribute it subject to the terms and conditions
+ * of the GNU General Public License v.2.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include "units.h"
+#include "lib/device/bcache.h"
+
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+#include <sys/statvfs.h>
+
+//----------------------------------------------------------------
+
+#define T_BLOCK_SIZE (PAGE_SIZE)
+#define NR_BLOCKS 64
+#define INIT_PATTERN 123
+
+struct fixture {
+ int fd;
+ int di;
+ char fname[32];
+ struct bcache *cache;
+};
+
+static inline uint8_t _pattern_at(uint8_t pat, uint8_t byte)
+{
+ return pat + byte;
+}
+
+static uint64_t byte(block_address b, uint64_t offset)
+{
+ return b * T_BLOCK_SIZE + offset;
+}
+
+static void *_fix_init(struct io_engine *engine)
+{
+ uint8_t buffer[T_BLOCK_SIZE];
+ struct fixture *f = malloc(sizeof(*f));
+ unsigned b, i;
+ static int _runs_is_tmpfs = -1;
+
+ memset(buffer, 0, sizeof(buffer));
+ T_ASSERT(f);
+
+ if (_runs_is_tmpfs == -1) {
+ snprintf(f->fname, sizeof(f->fname), "unit-test-XXXXXX");
+ /* coverity[secure_temp] don't care */
+ f->fd = mkstemp(f->fname);
+ T_ASSERT(f->fd >= 0);
+ (void) close(f->fd);
+ // test if we can reopen with O_DIRECT
+ if ((f->fd = open(f->fname, O_RDWR | O_DIRECT)) >= 0) {
+ _runs_is_tmpfs = 0;
+ (void) close(f->fd);
+ } else {
+ _runs_is_tmpfs = 1; // likely running on tmpfs
+ printf(" Running test in tmpfs, *NOT* using O_DIRECT\n");
+ }
+ (void) unlink(f->fname);
+ }
+
+ snprintf(f->fname, sizeof(f->fname), "unit-test-XXXXXX");
+ /* coverity[secure_temp] don't care */
+ f->fd = mkstemp(f->fname);
+ T_ASSERT(f->fd >= 0);
+
+ for (b = 0; b < NR_BLOCKS; b++) {
+ for (i = 0; i < sizeof(buffer); i++)
+ buffer[i] = _pattern_at(INIT_PATTERN, byte(b, i));
+ T_ASSERT(write(f->fd, buffer, T_BLOCK_SIZE) > 0);
+ }
+
+ if (!_runs_is_tmpfs) {
+ (void) close(f->fd);
+ // reopen with O_DIRECT
+ f->fd = open(f->fname, O_RDWR | O_DIRECT);
+ T_ASSERT(f->fd >= 0);
+ }
+
+ f->cache = bcache_create(T_BLOCK_SIZE / 512, NR_BLOCKS, engine);
+ T_ASSERT(f->cache);
+
+ f->di = bcache_set_fd(f->fd);
+
+ return f;
+}
+
+static void *_async_init(void)
+{
+ struct io_engine *e = create_async_io_engine();
+ T_ASSERT(e);
+ return _fix_init(e);
+}
+
+static void *_sync_init(void)
+{
+ struct io_engine *e = create_sync_io_engine();
+ T_ASSERT(e);
+ return _fix_init(e);
+}
+
+static void _fix_exit(void *fixture)
+{
+ struct fixture *f = fixture;
+
+ if (f) {
+ bcache_destroy(f->cache);
+ (void) close(f->fd);
+ bcache_clear_fd(f->di);
+ (void) unlink(f->fname);
+ free(f);
+ }
+}
+
+//----------------------------------------------------------------
+
+static void _verify_bytes(struct block *b, uint64_t base,
+ uint64_t offset, uint64_t len, uint8_t pat)
+{
+ unsigned i;
+
+ for (i = 0; i < len; i++)
+ T_ASSERT_EQUAL(((uint8_t *) b->data)[offset + i], _pattern_at(pat, base + offset + i));
+}
+
+static uint64_t _min(uint64_t lhs, uint64_t rhs)
+{
+ return rhs < lhs ? rhs : lhs;
+}
+
+static void _verify(struct fixture *f, uint64_t byte_b, uint64_t byte_e, uint8_t pat)
+{
+ struct block *b;
+ block_address bb = byte_b / T_BLOCK_SIZE;
+ block_address be = (byte_e + T_BLOCK_SIZE - 1) / T_BLOCK_SIZE;
+ uint64_t offset = byte_b % T_BLOCK_SIZE;
+ uint64_t blen, len = byte_e - byte_b;
+
+ // Verify via bcache_read_bytes
+ {
+ unsigned i;
+ size_t len2 = byte_e - byte_b;
+ uint8_t *buffer = malloc(len2);
+
+ T_ASSERT(buffer);
+ memset(buffer, 0, len2);
+
+ T_ASSERT(bcache_read_bytes(f->cache, f->di, byte_b, len2, buffer));
+ for (i = 0; i < len; i++)
+ T_ASSERT_EQUAL(buffer[i], _pattern_at(pat, byte_b + i));
+ free(buffer);
+ }
+
+ // Verify again, driving bcache directly
+ for (; bb != be; bb++) {
+ T_ASSERT(bcache_get(f->cache, f->di, bb, 0, &b));
+
+ blen = _min(T_BLOCK_SIZE - offset, len);
+ _verify_bytes(b, bb * T_BLOCK_SIZE, offset, blen, pat);
+
+ offset = 0;
+ len -= blen;
+
+ bcache_put(b);
+ }
+}
+
+static void _verify_set(struct fixture *f, uint64_t byte_b, uint64_t byte_e, uint8_t val)
+{
+ unsigned i;
+ struct block *b;
+ block_address bb = byte_b / T_BLOCK_SIZE;
+ block_address be = (byte_e + T_BLOCK_SIZE - 1) / T_BLOCK_SIZE;
+ uint64_t offset = byte_b % T_BLOCK_SIZE;
+ uint64_t blen, len = byte_e - byte_b;
+
+ for (; bb != be; bb++) {
+ T_ASSERT(bcache_get(f->cache, f->di, bb, 0, &b));
+
+ blen = _min(T_BLOCK_SIZE - offset, len);
+ for (i = 0; i < blen; i++)
+ T_ASSERT(((uint8_t *) b->data)[offset + i] == val);
+
+ offset = 0;
+ len -= blen;
+
+ bcache_put(b);
+ }
+}
+
+static void _verify_zeroes(struct fixture *f, uint64_t byte_b, uint64_t byte_e)
+{
+ _verify_set(f, byte_b, byte_e, 0);
+}
+
+static void _do_write(struct fixture *f, uint64_t byte_b, uint64_t byte_e, uint8_t pat)
+{
+ unsigned i;
+ size_t len = byte_e - byte_b;
+ uint8_t *buffer = malloc(len);
+
+ T_ASSERT(buffer);
+ memset(buffer, 0, len);
+
+ for (i = 0; i < len; i++)
+ buffer[i] = _pattern_at(pat, byte_b + i);
+
+ T_ASSERT(bcache_write_bytes(f->cache, f->di, byte_b, byte_e - byte_b, buffer));
+ free(buffer);
+}
+
+static void _do_zero(struct fixture *f, uint64_t byte_b, uint64_t byte_e)
+{
+ T_ASSERT(bcache_zero_bytes(f->cache, f->di, byte_b, byte_e - byte_b));
+}
+
+static void _do_set(struct fixture *f, uint64_t byte_b, uint64_t byte_e, uint8_t val)
+{
+ T_ASSERT(bcache_set_bytes(f->cache, f->di, byte_b, byte_e - byte_b, val));
+}
+
+static void _reopen(struct fixture *f)
+{
+ struct io_engine *engine;
+
+ bcache_destroy(f->cache);
+ engine = create_async_io_engine();
+ T_ASSERT(engine);
+
+ f->cache = bcache_create(T_BLOCK_SIZE / 512, NR_BLOCKS, engine);
+ T_ASSERT(f->cache);
+
+ f->di = bcache_set_fd(f->fd);
+}
+
+//----------------------------------------------------------------
+
+static uint8_t _random_pattern(void)
+{
+ /* coverity[dont_call] don't care */
+ return random();
+}
+
+static uint64_t _max_byte(void)
+{
+ return T_BLOCK_SIZE * NR_BLOCKS;
+}
+
+static void _rwv_cycle(struct fixture *f, uint64_t b, uint64_t e)
+{
+ uint8_t pat = _random_pattern();
+
+ _verify(f, b, e, INIT_PATTERN);
+ _do_write(f, b, e, pat);
+ _reopen(f);
+ _verify(f, b < 128 ? 0 : b - 128, b, INIT_PATTERN);
+ _verify(f, b, e, pat);
+ _verify(f, e, _min(e + 128, _max_byte()), INIT_PATTERN);
+}
+
+static void _test_rw_first_block(void *fixture)
+{
+ _rwv_cycle(fixture, byte(0, 0), byte(0, T_BLOCK_SIZE));
+}
+
+static void _test_rw_last_block(void *fixture)
+{
+ uint64_t last_block = NR_BLOCKS - 1;
+ _rwv_cycle(fixture, byte(last_block, 0),
+ byte(last_block, T_BLOCK_SIZE));
+}
+
+static void _test_rw_several_whole_blocks(void *fixture)
+{
+ _rwv_cycle(fixture, byte(5, 0), byte(10, 0));
+}
+
+static void _test_rw_within_single_block(void *fixture)
+{
+ _rwv_cycle(fixture, byte(7, 3), byte(7, T_BLOCK_SIZE / 2));
+}
+
+static void _test_rw_cross_one_boundary(void *fixture)
+{
+ _rwv_cycle(fixture, byte(13, 43), byte(14, 43));
+}
+
+static void _test_rw_many_boundaries(void *fixture)
+{
+ _rwv_cycle(fixture, byte(13, 13), byte(23, 13));
+}
+
+//----------------------------------------------------------------
+
+static void _zero_cycle(struct fixture *f, uint64_t b, uint64_t e)
+{
+ _verify(f, b, e, INIT_PATTERN);
+ _do_zero(f, b, e);
+ _reopen(f);
+ _verify(f, b < 128 ? 0 : b - 128, b, INIT_PATTERN);
+ _verify_zeroes(f, b, e);
+ _verify(f, e, _min(e + 128, _max_byte()), INIT_PATTERN);
+}
+
+static void _test_zero_first_block(void *fixture)
+{
+ _zero_cycle(fixture, byte(0, 0), byte(0, T_BLOCK_SIZE));
+}
+
+static void _test_zero_last_block(void *fixture)
+{
+ uint64_t last_block = NR_BLOCKS - 1;
+ _zero_cycle(fixture, byte(last_block, 0), byte(last_block, T_BLOCK_SIZE));
+}
+
+static void _test_zero_several_whole_blocks(void *fixture)
+{
+ _zero_cycle(fixture, byte(5, 0), byte(10, 0));
+}
+
+static void _test_zero_within_single_block(void *fixture)
+{
+ _zero_cycle(fixture, byte(7, 3), byte(7, T_BLOCK_SIZE / 2));
+}
+
+static void _test_zero_cross_one_boundary(void *fixture)
+{
+ _zero_cycle(fixture, byte(13, 43), byte(14, 43));
+}
+
+static void _test_zero_many_boundaries(void *fixture)
+{
+ _zero_cycle(fixture, byte(13, 13), byte(23, 13));
+}
+
+//----------------------------------------------------------------
+
+static void _set_cycle(struct fixture *f, uint64_t b, uint64_t e)
+{
+ uint8_t val = _random_pattern();
+
+ _verify(f, b, e, INIT_PATTERN);
+ _do_set(f, b, e, val);
+ _reopen(f);
+ _verify(f, b < 128 ? 0 : b - 128, b, INIT_PATTERN);
+ _verify_set(f, b, e, val);
+ _verify(f, e, _min(e + 128, _max_byte()), INIT_PATTERN);
+}
+
+static void _test_set_first_block(void *fixture)
+{
+ _set_cycle(fixture, byte(0, 0), byte(0, T_BLOCK_SIZE));
+}
+
+static void _test_set_last_block(void *fixture)
+{
+ uint64_t last_block = NR_BLOCKS - 1;
+ _set_cycle(fixture, byte(last_block, 0), byte(last_block, T_BLOCK_SIZE));
+}
+
+static void _test_set_several_whole_blocks(void *fixture)
+{
+ _set_cycle(fixture, byte(5, 0), byte(10, 0));
+}
+
+static void _test_set_within_single_block(void *fixture)
+{
+ _set_cycle(fixture, byte(7, 3), byte(7, T_BLOCK_SIZE / 2));
+}
+
+static void _test_set_cross_one_boundary(void *fixture)
+{
+ _set_cycle(fixture, byte(13, 43), byte(14, 43));
+}
+
+static void _test_set_many_boundaries(void *fixture)
+{
+ _set_cycle(fixture, byte(13, 13), byte(23, 13));
+}
+
+//----------------------------------------------------------------
+
+#define T(path, desc, fn) register_test(ts, "/base/device/bcache/utils/async/" path, desc, fn)
+
+static struct test_suite *_async_tests(void)
+{
+ struct test_suite *ts = test_suite_create(_async_init, _fix_exit);
+ if (!ts) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+
+#define T(path, desc, fn) register_test(ts, "/base/device/bcache/utils/async/" path, desc, fn)
+ T("rw-first-block", "read/write/verify the first block", _test_rw_first_block);
+ T("rw-last-block", "read/write/verify the last block", _test_rw_last_block);
+ T("rw-several-blocks", "read/write/verify several whole blocks", _test_rw_several_whole_blocks);
+ T("rw-within-single-block", "read/write/verify within single block", _test_rw_within_single_block);
+ T("rw-cross-one-boundary", "read/write/verify across one boundary", _test_rw_cross_one_boundary);
+ T("rw-many-boundaries", "read/write/verify many boundaries", _test_rw_many_boundaries);
+
+ T("zero-first-block", "zero the first block", _test_zero_first_block);
+ T("zero-last-block", "zero the last block", _test_zero_last_block);
+ T("zero-several-blocks", "zero several whole blocks", _test_zero_several_whole_blocks);
+ T("zero-within-single-block", "zero within single block", _test_zero_within_single_block);
+ T("zero-cross-one-boundary", "zero across one boundary", _test_zero_cross_one_boundary);
+ T("zero-many-boundaries", "zero many boundaries", _test_zero_many_boundaries);
+
+ T("set-first-block", "set the first block", _test_set_first_block);
+ T("set-last-block", "set the last block", _test_set_last_block);
+ T("set-several-blocks", "set several whole blocks", _test_set_several_whole_blocks);
+ T("set-within-single-block", "set within single block", _test_set_within_single_block);
+ T("set-cross-one-boundary", "set across one boundary", _test_set_cross_one_boundary);
+ T("set-many-boundaries", "set many boundaries", _test_set_many_boundaries);
+#undef T
+
+ return ts;
+}
+
+
+static struct test_suite *_sync_tests(void)
+{
+ struct test_suite *ts = test_suite_create(_sync_init, _fix_exit);
+ if (!ts) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+
+#define T(path, desc, fn) register_test(ts, "/base/device/bcache/utils/sync/" path, desc, fn)
+ T("rw-first-block", "read/write/verify the first block", _test_rw_first_block);
+ T("rw-last-block", "read/write/verify the last block", _test_rw_last_block);
+ T("rw-several-blocks", "read/write/verify several whole blocks", _test_rw_several_whole_blocks);
+ T("rw-within-single-block", "read/write/verify within single block", _test_rw_within_single_block);
+ T("rw-cross-one-boundary", "read/write/verify across one boundary", _test_rw_cross_one_boundary);
+ T("rw-many-boundaries", "read/write/verify many boundaries", _test_rw_many_boundaries);
+
+ T("zero-first-block", "zero the first block", _test_zero_first_block);
+ T("zero-last-block", "zero the last block", _test_zero_last_block);
+ T("zero-several-blocks", "zero several whole blocks", _test_zero_several_whole_blocks);
+ T("zero-within-single-block", "zero within single block", _test_zero_within_single_block);
+ T("zero-cross-one-boundary", "zero across one boundary", _test_zero_cross_one_boundary);
+ T("zero-many-boundaries", "zero many boundaries", _test_zero_many_boundaries);
+
+ T("set-first-block", "set the first block", _test_set_first_block);
+ T("set-last-block", "set the last block", _test_set_last_block);
+ T("set-several-blocks", "set several whole blocks", _test_set_several_whole_blocks);
+ T("set-within-single-block", "set within single block", _test_set_within_single_block);
+ T("set-cross-one-boundary", "set across one boundary", _test_set_cross_one_boundary);
+ T("set-many-boundaries", "set many boundaries", _test_set_many_boundaries);
+#undef T
+
+ return ts;
+}
+
+void bcache_utils_tests(struct dm_list *all_tests)
+{
+ dm_list_add(all_tests, &_async_tests()->list);
+ dm_list_add(all_tests, &_sync_tests()->list);
+}
+
diff --git a/test/unit/bitset_t.c b/test/unit/bitset_t.c
index 499de32..1e74e12 100644
--- a/test/unit/bitset_t.c
+++ b/test/unit/bitset_t.c
@@ -9,38 +9,43 @@
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
- * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
-#include "libdevmapper.h"
-#include <CUnit/CUnit.h>
-
-int bitset_init(void);
-int bitset_fini(void);
+#include "units.h"
+#include "device_mapper/all.h"
enum {
NR_BITS = 137
};
-static struct dm_pool *mem;
+static void *_mem_init(void) {
+ struct dm_pool *mem = dm_pool_create("bitset test", 1024);
+ if (!mem) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
-int bitset_init(void) {
- mem = dm_pool_create("bitset test", 1024);
- return mem == NULL;
+ return mem;
}
-int bitset_fini(void) {
- dm_pool_destroy(mem);
- return 0;
+static void _mem_exit(void *mem)
+{
+ if (mem)
+ dm_pool_destroy(mem);
}
-static void test_get_next(void)
+static void test_get_next(void *fixture)
{
+ struct dm_pool *mem = fixture;
+
int i, j, last = 0, first;
dm_bitset_t bs = dm_bitset_create(mem, NR_BITS);
+ T_ASSERT(bs);
+
for (i = 0; i < NR_BITS; i++)
- CU_ASSERT(!dm_bit(bs, i));
+ T_ASSERT(!dm_bit(bs, i));
for (i = 0, j = 1; i < NR_BITS; i += j, j++)
dm_bit_set(bs, i);
@@ -53,10 +58,10 @@ static void test_get_next(void)
} else
last = dm_bit_get_next(bs, last);
- CU_ASSERT(last == i);
+ T_ASSERT(last == i);
}
- CU_ASSERT(dm_bit_get_next(bs, last) == -1);
+ T_ASSERT(dm_bit_get_next(bs, last) == -1);
}
static void bit_flip(dm_bitset_t bs, int bit)
@@ -68,37 +73,48 @@ static void bit_flip(dm_bitset_t bs, int bit)
dm_bit_set(bs, bit);
}
-static void test_equal(void)
+static void test_equal(void *fixture)
{
+ struct dm_pool *mem = fixture;
dm_bitset_t bs1 = dm_bitset_create(mem, NR_BITS);
dm_bitset_t bs2 = dm_bitset_create(mem, NR_BITS);
- int i, j;
+ int i, j;
+
+ T_ASSERT(bs1);
+ T_ASSERT(bs2);
+
for (i = 0, j = 1; i < NR_BITS; i += j, j++) {
dm_bit_set(bs1, i);
dm_bit_set(bs2, i);
}
- CU_ASSERT(dm_bitset_equal(bs1, bs2));
- CU_ASSERT(dm_bitset_equal(bs2, bs1));
+ T_ASSERT(dm_bitset_equal(bs1, bs2));
+ T_ASSERT(dm_bitset_equal(bs2, bs1));
for (i = 0; i < NR_BITS; i++) {
bit_flip(bs1, i);
- CU_ASSERT(!dm_bitset_equal(bs1, bs2));
- CU_ASSERT(!dm_bitset_equal(bs2, bs1));
+ T_ASSERT(!dm_bitset_equal(bs1, bs2));
+ T_ASSERT(!dm_bitset_equal(bs2, bs1));
- CU_ASSERT(dm_bitset_equal(bs1, bs1)); /* comparing with self */
+ T_ASSERT(dm_bitset_equal(bs1, bs1)); /* comparing with self */
bit_flip(bs1, i);
}
}
-static void test_and(void)
+static void test_and(void *fixture)
{
+ struct dm_pool *mem = fixture;
dm_bitset_t bs1 = dm_bitset_create(mem, NR_BITS);
dm_bitset_t bs2 = dm_bitset_create(mem, NR_BITS);
dm_bitset_t bs3 = dm_bitset_create(mem, NR_BITS);
- int i, j;
+ int i, j;
+
+ T_ASSERT(bs1);
+ T_ASSERT(bs2);
+ T_ASSERT(bs3);
+
for (i = 0, j = 1; i < NR_BITS; i += j, j++) {
dm_bit_set(bs1, i);
dm_bit_set(bs2, i);
@@ -106,9 +122,9 @@ static void test_and(void)
dm_bit_and(bs3, bs1, bs2);
- CU_ASSERT(dm_bitset_equal(bs1, bs2));
- CU_ASSERT(dm_bitset_equal(bs1, bs3));
- CU_ASSERT(dm_bitset_equal(bs2, bs3));
+ T_ASSERT(dm_bitset_equal(bs1, bs2));
+ T_ASSERT(dm_bitset_equal(bs1, bs3));
+ T_ASSERT(dm_bitset_equal(bs2, bs3));
dm_bit_clear_all(bs1);
dm_bit_clear_all(bs2);
@@ -122,12 +138,23 @@ static void test_and(void)
dm_bit_and(bs3, bs1, bs2);
for (i = 0; i < NR_BITS; i++)
- CU_ASSERT(!dm_bit(bs3, i));
+ T_ASSERT(!dm_bit(bs3, i));
+}
+
+#define T(path, desc, fn) register_test(ts, "/base/data-struct/bitset/" path, desc, fn)
+
+void bitset_tests(struct dm_list *all_tests)
+{
+ struct test_suite *ts = test_suite_create(_mem_init, _mem_exit);
+ if (!ts) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+
+ T("get_next", "get next set bit", test_get_next);
+ T("equal", "equality", test_equal);
+ T("and", "and all bits", test_and);
+
+ dm_list_add(all_tests, &ts->list);
}
-CU_TestInfo bitset_list[] = {
- { (char*)"get_next", test_get_next },
- { (char*)"equal", test_equal },
- { (char*)"and", test_and },
- CU_TEST_INFO_NULL
-};
diff --git a/test/unit/config_t.c b/test/unit/config_t.c
index 9a8b693..cd539ab 100644
--- a/test/unit/config_t.c
+++ b/test/unit/config_t.c
@@ -9,25 +9,26 @@
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
- * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
-#include "libdevmapper.h"
-#include <CUnit/CUnit.h>
+#include "units.h"
+#include "device_mapper/all.h"
-int config_init(void);
-int config_fini(void);
-
-static struct dm_pool *mem;
+static void *_mem_init(void)
+{
+ struct dm_pool *mem = dm_pool_create("config test", 1024);
+ if (!mem) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
-int config_init(void) {
- mem = dm_pool_create("config test", 1024);
- return mem == NULL;
+ return mem;
}
-int config_fini(void) {
+static void _mem_exit(void *mem)
+{
dm_pool_destroy(mem);
- return 0;
}
static const char *conf =
@@ -60,97 +61,120 @@ static const char *overlay =
" }\n"
"}\n";
-static void test_parse(void)
+static void test_parse(void *fixture)
{
struct dm_config_tree *tree = dm_config_from_string(conf);
const struct dm_config_value *value;
- CU_ASSERT((long) tree);
- CU_ASSERT(dm_config_has_node(tree->root, "id"));
- CU_ASSERT(dm_config_has_node(tree->root, "physical_volumes"));
- CU_ASSERT(dm_config_has_node(tree->root, "physical_volumes/pv0"));
- CU_ASSERT(dm_config_has_node(tree->root, "physical_volumes/pv0/id"));
+ T_ASSERT((long) tree);
+ T_ASSERT(dm_config_has_node(tree->root, "id"));
+ T_ASSERT(dm_config_has_node(tree->root, "physical_volumes"));
+ T_ASSERT(dm_config_has_node(tree->root, "physical_volumes/pv0"));
+ T_ASSERT(dm_config_has_node(tree->root, "physical_volumes/pv0/id"));
- CU_ASSERT(!strcmp(dm_config_find_str(tree->root, "id", "foo"), "yada-yada"));
- CU_ASSERT(!strcmp(dm_config_find_str(tree->root, "idt", "foo"), "foo"));
+ T_ASSERT(!strcmp(dm_config_find_str(tree->root, "id", "foo"), "yada-yada"));
+ T_ASSERT(!strcmp(dm_config_find_str(tree->root, "idt", "foo"), "foo"));
- CU_ASSERT(!strcmp(dm_config_find_str(tree->root, "physical_volumes/pv0/bb", "foo"), "foo"));
- CU_ASSERT(!strcmp(dm_config_find_str(tree->root, "physical_volumes/pv0/id", "foo"), "abcd-efgh"));
+ T_ASSERT(!strcmp(dm_config_find_str(tree->root, "physical_volumes/pv0/bb", "foo"), "foo"));
+ T_ASSERT(!strcmp(dm_config_find_str(tree->root, "physical_volumes/pv0/id", "foo"), "abcd-efgh"));
- CU_ASSERT(!dm_config_get_uint32(tree->root, "id", NULL));
- CU_ASSERT(dm_config_get_uint32(tree->root, "extent_size", NULL));
+ T_ASSERT(!dm_config_get_uint32(tree->root, "id", NULL));
+ T_ASSERT(dm_config_get_uint32(tree->root, "extent_size", NULL));
/* FIXME: Currently everything parses as a list, even if it's not */
- // CU_ASSERT(!dm_config_get_list(tree->root, "id", NULL));
- // CU_ASSERT(!dm_config_get_list(tree->root, "extent_size", NULL));
+ // T_ASSERT(!dm_config_get_list(tree->root, "id", NULL));
+ // T_ASSERT(!dm_config_get_list(tree->root, "extent_size", NULL));
- CU_ASSERT(dm_config_get_list(tree->root, "flags", &value));
- CU_ASSERT(value->next == NULL); /* an empty list */
- CU_ASSERT(dm_config_get_list(tree->root, "status", &value));
- CU_ASSERT(value->next != NULL); /* a non-empty list */
+ T_ASSERT(dm_config_get_list(tree->root, "flags", &value));
+ T_ASSERT(value->next == NULL); /* an empty list */
+ T_ASSERT(dm_config_get_list(tree->root, "status", &value));
+ T_ASSERT(value->next != NULL); /* a non-empty list */
dm_config_destroy(tree);
}
-static void test_clone(void)
+static void test_clone(void *fixture)
{
struct dm_config_tree *tree = dm_config_from_string(conf);
- struct dm_config_node *n = dm_config_clone_node(tree, tree->root, 1);
+ struct dm_config_node *n;
const struct dm_config_value *value;
+ T_ASSERT(tree);
+
+ n = dm_config_clone_node(tree, tree->root, 1);
+
+ T_ASSERT(n);
+
/* Check that the nodes are actually distinct. */
- CU_ASSERT(n != tree->root);
- CU_ASSERT(n->sib != tree->root->sib);
- CU_ASSERT(dm_config_find_node(n, "physical_volumes") != NULL);
- CU_ASSERT(dm_config_find_node(tree->root, "physical_volumes") != NULL);
- CU_ASSERT(dm_config_find_node(n, "physical_volumes") != dm_config_find_node(tree->root, "physical_volumes"));
+ T_ASSERT(n != tree->root);
+ T_ASSERT(n->sib != tree->root->sib);
+ T_ASSERT(dm_config_find_node(n, "physical_volumes") != NULL);
+ T_ASSERT(dm_config_find_node(tree->root, "physical_volumes") != NULL);
+ T_ASSERT(dm_config_find_node(n, "physical_volumes") != dm_config_find_node(tree->root, "physical_volumes"));
- CU_ASSERT(dm_config_has_node(n, "id"));
- CU_ASSERT(dm_config_has_node(n, "physical_volumes"));
- CU_ASSERT(dm_config_has_node(n, "physical_volumes/pv0"));
- CU_ASSERT(dm_config_has_node(n, "physical_volumes/pv0/id"));
+ T_ASSERT(dm_config_has_node(n, "id"));
+ T_ASSERT(dm_config_has_node(n, "physical_volumes"));
+ T_ASSERT(dm_config_has_node(n, "physical_volumes/pv0"));
+ T_ASSERT(dm_config_has_node(n, "physical_volumes/pv0/id"));
- CU_ASSERT(!strcmp(dm_config_find_str(n, "id", "foo"), "yada-yada"));
- CU_ASSERT(!strcmp(dm_config_find_str(n, "idt", "foo"), "foo"));
+ T_ASSERT(!strcmp(dm_config_find_str(n, "id", "foo"), "yada-yada"));
+ T_ASSERT(!strcmp(dm_config_find_str(n, "idt", "foo"), "foo"));
- CU_ASSERT(!strcmp(dm_config_find_str(n, "physical_volumes/pv0/bb", "foo"), "foo"));
- CU_ASSERT(!strcmp(dm_config_find_str(n, "physical_volumes/pv0/id", "foo"), "abcd-efgh"));
+ T_ASSERT(!strcmp(dm_config_find_str(n, "physical_volumes/pv0/bb", "foo"), "foo"));
+ T_ASSERT(!strcmp(dm_config_find_str(n, "physical_volumes/pv0/id", "foo"), "abcd-efgh"));
- CU_ASSERT(!dm_config_get_uint32(n, "id", NULL));
- CU_ASSERT(dm_config_get_uint32(n, "extent_size", NULL));
+ T_ASSERT(!dm_config_get_uint32(n, "id", NULL));
+ T_ASSERT(dm_config_get_uint32(n, "extent_size", NULL));
/* FIXME: Currently everything parses as a list, even if it's not */
- // CU_ASSERT(!dm_config_get_list(tree->root, "id", NULL));
- // CU_ASSERT(!dm_config_get_list(tree->root, "extent_size", NULL));
+ // T_ASSERT(!dm_config_get_list(tree->root, "id", NULL));
+ // T_ASSERT(!dm_config_get_list(tree->root, "extent_size", NULL));
- CU_ASSERT(dm_config_get_list(n, "flags", &value));
- CU_ASSERT(value->next == NULL); /* an empty list */
- CU_ASSERT(dm_config_get_list(n, "status", &value));
- CU_ASSERT(value->next != NULL); /* a non-empty list */
+ T_ASSERT(dm_config_get_list(n, "flags", &value));
+ T_ASSERT(value->next == NULL); /* an empty list */
+ T_ASSERT(dm_config_get_list(n, "status", &value));
+ T_ASSERT(value->next != NULL); /* a non-empty list */
dm_config_destroy(tree);
}
-static void test_cascade(void)
+static void test_cascade(void *fixture)
{
struct dm_config_tree *t1 = dm_config_from_string(conf),
*t2 = dm_config_from_string(overlay),
- *tree = dm_config_insert_cascaded_tree(t2, t1);
+ *tree;
+
+ T_ASSERT(t1);
+ T_ASSERT(t2);
- CU_ASSERT(!strcmp(dm_config_tree_find_str(tree, "id", "foo"), "yoda-soda"));
- CU_ASSERT(!strcmp(dm_config_tree_find_str(tree, "idt", "foo"), "foo"));
+ tree = dm_config_insert_cascaded_tree(t2, t1);
- CU_ASSERT(!strcmp(dm_config_tree_find_str(tree, "physical_volumes/pv0/bb", "foo"), "foo"));
- CU_ASSERT(!strcmp(dm_config_tree_find_str(tree, "physical_volumes/pv1/id", "foo"), "hgfe-dcba"));
- CU_ASSERT(!strcmp(dm_config_tree_find_str(tree, "physical_volumes/pv3/id", "foo"), "dbcd-efgh"));
+ T_ASSERT(tree);
+
+ T_ASSERT(!strcmp(dm_config_tree_find_str(tree, "id", "foo"), "yoda-soda"));
+ T_ASSERT(!strcmp(dm_config_tree_find_str(tree, "idt", "foo"), "foo"));
+
+ T_ASSERT(!strcmp(dm_config_tree_find_str(tree, "physical_volumes/pv0/bb", "foo"), "foo"));
+ T_ASSERT(!strcmp(dm_config_tree_find_str(tree, "physical_volumes/pv1/id", "foo"), "hgfe-dcba"));
+ T_ASSERT(!strcmp(dm_config_tree_find_str(tree, "physical_volumes/pv3/id", "foo"), "dbcd-efgh"));
dm_config_destroy(t1);
dm_config_destroy(t2);
}
-CU_TestInfo config_list[] = {
- { (char*)"parse", test_parse },
- { (char*)"clone", test_clone },
- { (char*)"cascade", test_cascade },
- CU_TEST_INFO_NULL
+#define T(path, desc, fn) register_test(ts, "/metadata/config/" path, desc, fn)
+
+void config_tests(struct dm_list *all_tests)
+{
+ struct test_suite *ts = test_suite_create(_mem_init, _mem_exit);
+ if (!ts) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+
+ T("parse", "parsing various", test_parse);
+ T("clone", "duplicating a config tree", test_clone);
+ T("cascade", "cascade", test_cascade);
+
+ dm_list_add(all_tests, &ts->list);
};
diff --git a/test/unit/dmlist_t.c b/test/unit/dmlist_t.c
new file mode 100644
index 0000000..0e33385
--- /dev/null
+++ b/test/unit/dmlist_t.c
@@ -0,0 +1,49 @@
+/*
+ * Copyright (C) 2015 Red Hat, Inc. All rights reserved.
+ *
+ * This file is part of LVM2.
+ *
+ * This copyrighted material is made available to anyone wishing to use,
+ * modify, copy, or redistribute it subject to the terms and conditions
+ * of the GNU General Public License v.2.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include "units.h"
+#include "device_mapper/all.h"
+
+static void test_dmlist_splice(void *fixture)
+{
+ unsigned i;
+ struct dm_list a[10];
+ struct dm_list list1;
+ struct dm_list list2;
+
+ dm_list_init(&list1);
+ dm_list_init(&list2);
+
+ for (i = 0; i < DM_ARRAY_SIZE(a); i++)
+ dm_list_add(&list1, &a[i]);
+
+ dm_list_splice(&list2, &list1);
+ T_ASSERT(dm_list_size(&list1) == 0);
+ T_ASSERT(dm_list_size(&list2) == 10);
+}
+
+#define T(path, desc, fn) register_test(ts, "/base/data-struct/list/" path, desc, fn)
+
+void dm_list_tests(struct dm_list *all_tests)
+{
+ struct test_suite *ts = test_suite_create(NULL, NULL);
+ if (!ts) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+
+ T("splice", "joining lists together", test_dmlist_splice);
+
+ dm_list_add(all_tests, &ts->list);
+}
diff --git a/test/unit/dmstatus_t.c b/test/unit/dmstatus_t.c
new file mode 100644
index 0000000..ac2015e
--- /dev/null
+++ b/test/unit/dmstatus_t.c
@@ -0,0 +1,84 @@
+/*
+ * Copyright (C) 2015 Red Hat, Inc. All rights reserved.
+ *
+ * This file is part of LVM2.
+ *
+ * This copyrighted material is made available to anyone wishing to use,
+ * modify, copy, or redistribute it subject to the terms and conditions
+ * of the GNU General Public License v.2.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include "units.h"
+#include "device_mapper/all.h"
+
+static void *_mem_init(void)
+{
+ struct dm_pool *mem = dm_pool_create("dmstatus test", 1024);
+ if (!mem) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+
+ return mem;
+}
+
+static void _mem_exit(void *mem)
+{
+ dm_pool_destroy(mem);
+}
+
+static void _test_mirror_status(void *fixture)
+{
+ struct dm_pool *mem = fixture;
+ struct dm_status_mirror *s = NULL;
+
+ T_ASSERT(dm_get_status_mirror(mem,
+ "2 253:1 253:2 80/81 1 AD 3 disk 253:0 A",
+ &s));
+ if (s) {
+ T_ASSERT_EQUAL(s->total_regions, 81);
+ T_ASSERT_EQUAL(s->insync_regions, 80);
+ T_ASSERT_EQUAL(s->dev_count, 2);
+ T_ASSERT_EQUAL(s->devs[0].health, 'A');
+ T_ASSERT_EQUAL(s->devs[0].major, 253);
+ T_ASSERT_EQUAL(s->devs[0].minor, 1);
+ T_ASSERT_EQUAL(s->devs[1].health, 'D');
+ T_ASSERT_EQUAL(s->devs[1].major, 253);
+ T_ASSERT_EQUAL(s->devs[1].minor, 2);
+ T_ASSERT_EQUAL(s->log_count, 1);
+ T_ASSERT_EQUAL(s->logs[0].major, 253);
+ T_ASSERT_EQUAL(s->logs[0].minor, 0);
+ T_ASSERT_EQUAL(s->logs[0].health, 'A');
+ T_ASSERT(!strcmp(s->log_type, "disk"));
+ }
+
+ T_ASSERT(dm_get_status_mirror(mem,
+ "4 253:1 253:2 253:3 253:4 10/10 1 ADFF 1 core",
+ &s));
+ if (s) {
+ T_ASSERT_EQUAL(s->total_regions, 10);
+ T_ASSERT_EQUAL(s->insync_regions, 10);
+ T_ASSERT_EQUAL(s->dev_count, 4);
+ T_ASSERT_EQUAL(s->devs[3].minor, 4);
+ T_ASSERT_EQUAL(s->devs[3].health, 'F');
+ T_ASSERT_EQUAL(s->log_count, 0);
+ T_ASSERT(!strcmp(s->log_type, "core"));
+ }
+}
+
+void dm_status_tests(struct dm_list *all_tests)
+{
+ struct test_suite *ts = test_suite_create(_mem_init, _mem_exit);
+ if (!ts) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+
+ register_test(ts, "/device-mapper/mirror/status", "parsing mirror status", _test_mirror_status);
+ dm_list_add(all_tests, &ts->list);
+}
+
diff --git a/test/unit/framework.c b/test/unit/framework.c
new file mode 100644
index 0000000..de9a8b1
--- /dev/null
+++ b/test/unit/framework.c
@@ -0,0 +1,66 @@
+#include "framework.h"
+
+/*----------------------------------------------------------------
+ * Assertions
+ *--------------------------------------------------------------*/
+
+jmp_buf test_k;
+#define TEST_FAILED 1
+
+void test_fail(const char *fmt, ...)
+{
+ va_list ap;
+
+ va_start(ap, fmt);
+ vfprintf(stderr, fmt, ap);
+ va_end(ap);
+ fprintf(stderr, "\n");
+
+ longjmp(test_k, TEST_FAILED);
+}
+
+struct test_suite *test_suite_create(void *(*fixture_init)(void),
+ void (*fixture_exit)(void *))
+{
+ struct test_suite *ts = malloc(sizeof(*ts));
+ if (ts) {
+ ts->fixture_init = fixture_init;
+ ts->fixture_exit = fixture_exit;
+ dm_list_init(&ts->tests);
+ }
+
+ return ts;
+}
+
+void test_suite_destroy(struct test_suite *ts)
+{
+ struct test_details *td, *tmp;
+
+ dm_list_iterate_items_safe (td, tmp, &ts->tests) {
+ dm_list_del(&td->list);
+ free(td);
+ }
+
+ free(ts);
+}
+
+bool register_test(struct test_suite *ts,
+ const char *path, const char *desc,
+ void (*fn)(void *))
+{
+ struct test_details *t = malloc(sizeof(*t));
+ if (!t) {
+ fprintf(stderr, "out of memory\n");
+ return false;
+ }
+
+ t->parent = ts;
+ t->path = path;
+ t->desc = desc;
+ t->fn = fn;
+ dm_list_add(&ts->tests, &t->list);
+
+ return true;
+}
+
+//-----------------------------------------------------------------
diff --git a/test/unit/framework.h b/test/unit/framework.h
new file mode 100644
index 0000000..f7f5b5b
--- /dev/null
+++ b/test/unit/framework.h
@@ -0,0 +1,51 @@
+#ifndef TEST_UNIT_FRAMEWORK_H
+#define TEST_UNIT_FRAMEWORK_H
+
+#include "device_mapper/all.h"
+
+#include <stdbool.h>
+#include <stdint.h>
+#include <setjmp.h>
+
+//-----------------------------------------------------------------
+
+// A test suite gathers a set of tests with a common fixture together.
+struct test_suite {
+ struct dm_list list;
+
+ void *(*fixture_init)(void);
+ void (*fixture_exit)(void *);
+ struct dm_list tests;
+};
+
+struct test_details {
+ struct test_suite *parent;
+ struct dm_list list;
+
+ const char *path;
+ const char *desc;
+ void (*fn)(void *);
+};
+
+struct test_suite *test_suite_create(void *(*fixture_init)(void),
+ void (*fixture_exit)(void *));
+void test_suite_destroy(struct test_suite *ts);
+
+bool register_test(struct test_suite *ts,
+ const char *path, const char *desc, void (*fn)(void *));
+
+void test_fail(const char *fmt, ...)
+ __attribute__((noreturn, format (printf, 1, 2)));
+
+#define T_ASSERT(e) do {if (!(e)) {test_fail("assertion failed: '%s'", # e);} } while(0)
+#define T_ASSERT_EQUAL(x, y) T_ASSERT((x) == (y))
+#define T_ASSERT_NOT_EQUAL(x, y) T_ASSERT((x) != (y))
+
+extern jmp_buf test_k;
+#define TEST_FAILED 1
+
+#define PAGE_SIZE ({ int ps = sysconf(_SC_PAGESIZE); (ps > 0) ? ps : 4096 ; })
+
+//-----------------------------------------------------------------
+
+#endif
diff --git a/test/unit/io_engine_t.c b/test/unit/io_engine_t.c
new file mode 100644
index 0000000..2f6ea5b
--- /dev/null
+++ b/test/unit/io_engine_t.c
@@ -0,0 +1,229 @@
+/*
+ * Copyright (C) 2018 Red Hat, Inc. All rights reserved.
+ *
+ * This file is part of LVM2.
+ *
+ * This copyrighted material is made available to anyone wishing to use,
+ * modify, copy, or redistribute it subject to the terms and conditions
+ * of the GNU General Public License v.2.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include "units.h"
+#include "lib/device/bcache.h"
+
+#include <errno.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <sys/types.h>
+#include <sys/stat.h>
+#include <fcntl.h>
+#include <unistd.h>
+
+//----------------------------------------------------------------
+
+#define SECTOR_SHIFT 9
+#define SECTOR_SIZE 512
+#define BLOCK_SIZE_SECTORS 8
+#define PAGE_SIZE_SECTORS ((PAGE_SIZE) >> SECTOR_SHIFT)
+#define NR_BLOCKS 64
+
+struct fixture {
+ struct io_engine *e;
+ uint8_t *data;
+
+ char fname[64];
+ int fd;
+ int di;
+};
+
+static void _fill_buffer(uint8_t *buffer, uint8_t seed, size_t count)
+{
+ unsigned i;
+ uint8_t b = seed;
+
+ for (i = 0; i < count; i++) {
+ buffer[i] = b;
+ b = ((b << 5) + b) + i;
+ }
+}
+
+static void _check_buffer(uint8_t *buffer, uint8_t seed, size_t count)
+{
+ unsigned i;
+ uint8_t b = seed;
+
+ for (i = 0; i < count; i++) {
+ T_ASSERT_EQUAL(buffer[i], b);
+ b = ((b << 5) + b) + i;
+ }
+}
+
+static void _print_buffer(const char *name, uint8_t *buffer, size_t count)
+{
+ unsigned col;
+
+ fprintf(stderr, "%s:\n", name);
+ while (count) {
+ for (col = 0; count && col < 20; col++) {
+ fprintf(stderr, "%x, ", (unsigned) *buffer);
+ col++;
+ buffer++;
+ count--;
+ }
+ fprintf(stderr, "\n");
+ }
+}
+
+static void *_fix_init(void)
+{
+ struct fixture *f = malloc(sizeof(*f));
+
+ T_ASSERT(f);
+ f->e = create_async_io_engine();
+ T_ASSERT(f->e);
+ if (posix_memalign((void **) &f->data, PAGE_SIZE, SECTOR_SIZE * BLOCK_SIZE_SECTORS))
+ test_fail("posix_memalign failed");
+
+ snprintf(f->fname, sizeof(f->fname), "unit-test-XXXXXX");
+ /* coverity[secure_temp] don't care */
+ f->fd = mkstemp(f->fname);
+ T_ASSERT(f->fd >= 0);
+
+ _fill_buffer(f->data, 123, SECTOR_SIZE * BLOCK_SIZE_SECTORS);
+
+ T_ASSERT(write(f->fd, f->data, SECTOR_SIZE * BLOCK_SIZE_SECTORS) > 0);
+ T_ASSERT(lseek(f->fd, 0, SEEK_SET) != -1);
+
+ return f;
+}
+
+static void _fix_exit(void *fixture)
+{
+ struct fixture *f = fixture;
+
+ if (f) {
+ (void) close(f->fd);
+ bcache_clear_fd(f->di);
+ (void) unlink(f->fname);
+ free(f->data);
+ if (f->e)
+ f->e->destroy(f->e);
+ free(f);
+ }
+}
+
+static void _test_create(void *fixture)
+{
+ // empty
+}
+
+struct io {
+ bool completed;
+ int error;
+};
+
+static void _io_init(struct io *io)
+{
+ io->completed = false;
+ io->error = 0;
+}
+
+static void _complete_io(void *context, int io_error)
+{
+ struct io *io = context;
+ io->completed = true;
+ io->error = io_error;
+}
+
+static void _test_read(void *fixture)
+{
+ struct fixture *f = fixture;
+ struct io io;
+ struct bcache *cache = bcache_create(PAGE_SIZE_SECTORS, BLOCK_SIZE_SECTORS, f->e);
+ T_ASSERT(cache);
+
+ f->di = bcache_set_fd(f->fd);
+
+ T_ASSERT(f->di >= 0);
+
+ _io_init(&io);
+ T_ASSERT(f->e->issue(f->e, DIR_READ, f->di, 0, BLOCK_SIZE_SECTORS, f->data, &io));
+ T_ASSERT(f->e->wait(f->e, _complete_io));
+ T_ASSERT(io.completed);
+ T_ASSERT(!io.error);
+
+ _check_buffer(f->data, 123, SECTOR_SIZE * BLOCK_SIZE_SECTORS);
+}
+
+static void _test_write(void *fixture)
+{
+ struct fixture *f = fixture;
+ struct io io;
+ struct bcache *cache = bcache_create(PAGE_SIZE_SECTORS, BLOCK_SIZE_SECTORS, f->e);
+ T_ASSERT(cache);
+
+ f->di = bcache_set_fd(f->fd);
+
+ T_ASSERT(f->di >= 0);
+
+ _io_init(&io);
+ T_ASSERT(f->e->issue(f->e, DIR_WRITE, f->di, 0, BLOCK_SIZE_SECTORS, f->data, &io));
+ T_ASSERT(f->e->wait(f->e, _complete_io));
+ T_ASSERT(io.completed);
+ T_ASSERT(!io.error);
+}
+
+static void _test_write_bytes(void *fixture)
+{
+ struct fixture *f = fixture;
+
+ unsigned offset = 345;
+ char buf_out[32];
+ char buf_in[32];
+ struct bcache *cache = bcache_create(PAGE_SIZE_SECTORS, BLOCK_SIZE_SECTORS, f->e);
+ T_ASSERT(cache);
+
+ f->di = bcache_set_fd(f->fd);
+
+ // T_ASSERT(bcache_read_bytes(cache, f->di, offset, sizeof(buf_in), buf_in));
+ _fill_buffer((uint8_t *) buf_out, 234, sizeof(buf_out));
+ T_ASSERT(bcache_write_bytes(cache, f->di, offset, sizeof(buf_out), buf_out));
+ T_ASSERT(bcache_read_bytes(cache, f->di, offset, sizeof(buf_in), buf_in));
+
+ _print_buffer("buf_out", (uint8_t *) buf_out, sizeof(buf_out));
+ _print_buffer("buf_in", (uint8_t *) buf_in, sizeof(buf_in));
+ T_ASSERT(!memcmp(buf_out, buf_in, sizeof(buf_out)));
+
+ bcache_destroy(cache);
+ f->e = NULL; // already destroyed
+}
+
+//----------------------------------------------------------------
+
+#define T(path, desc, fn) register_test(ts, "/base/device/bcache/io-engine/" path, desc, fn)
+
+static struct test_suite *_tests(void)
+{
+ struct test_suite *ts = test_suite_create(_fix_init, _fix_exit);
+ if (!ts) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+
+ T("create-destroy", "simple create/destroy", _test_create);
+ T("read", "read sanity check", _test_read);
+ T("write", "write sanity check", _test_write);
+ T("bcache-write-bytes", "test the utility fns", _test_write_bytes);
+
+ return ts;
+}
+
+void io_engine_tests(struct dm_list *all_tests)
+{
+ dm_list_add(all_tests, &_tests()->list);
+}
+
diff --git a/test/unit/matcher_t.c b/test/unit/matcher_t.c
index 7331a82..89b2988 100644
--- a/test/unit/matcher_t.c
+++ b/test/unit/matcher_t.c
@@ -10,76 +10,120 @@
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
- * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
-#include "libdevmapper.h"
-#include "log.h"
+#include "units.h"
+#include "device_mapper/all.h"
-#include <stdio.h>
-#include <ctype.h>
-#include <string.h>
-#include <sys/types.h>
-#include <sys/stat.h>
-#include <unistd.h>
-#include <fcntl.h>
-#include <sys/mman.h>
-
-#include <CUnit/CUnit.h>
#include "matcher_data.h"
-int regex_init(void);
-int regex_fini(void);
-
-static struct dm_pool *mem = NULL;
+static void *_mem_init(void)
+{
+ struct dm_pool *mem = dm_pool_create("bitset test", 1024);
+ if (!mem) {
+ fprintf(stderr, "out of memory");
+ exit(1);
+ }
-int regex_init(void) {
- mem = dm_pool_create("bitset test", 1024);
- return mem == NULL;
+ return mem;
}
-int regex_fini(void) {
+static void _mem_exit(void *mem)
+{
dm_pool_destroy(mem);
- return 0;
}
-static struct dm_regex *make_scanner(const char **rx)
+static struct dm_regex *make_scanner(struct dm_pool *mem, const char **rx)
{
struct dm_regex *scanner;
int nrx = 0;
for (; rx[nrx]; ++nrx);
scanner = dm_regex_create(mem, rx, nrx);
- CU_ASSERT_FATAL(scanner != NULL);
+ T_ASSERT(scanner != NULL);
return scanner;
}
-static void test_fingerprints(void) {
+static void test_fingerprints(void *fixture)
+{
+ struct dm_pool *mem = fixture;
struct dm_regex *scanner;
- scanner = make_scanner(dev_patterns);
- CU_ASSERT_EQUAL(dm_regex_fingerprint(scanner), 0x7f556c09);
+ scanner = make_scanner(mem, dev_patterns);
+ T_ASSERT_EQUAL(dm_regex_fingerprint(scanner), 0x7f556c09);
- scanner = make_scanner(random_patterns);
- CU_ASSERT_EQUAL(dm_regex_fingerprint(scanner), 0x9f11076c);
+ scanner = make_scanner(mem, random_patterns);
+ T_ASSERT_EQUAL(dm_regex_fingerprint(scanner), 0x9f11076c);
}
-static void test_matching(void) {
+static void test_matching(void *fixture)
+{
+ struct dm_pool *mem = fixture;
struct dm_regex *scanner;
int i;
- scanner = make_scanner(dev_patterns);
+ scanner = make_scanner(mem, dev_patterns);
for (i = 0; devices[i].str; ++i)
- CU_ASSERT_EQUAL(dm_regex_match(scanner, devices[i].str), devices[i].expected - 1);
+ T_ASSERT_EQUAL(dm_regex_match(scanner, devices[i].str), devices[i].expected - 1);
- scanner = make_scanner(nonprint_patterns);
+ scanner = make_scanner(mem, nonprint_patterns);
for (i = 0; nonprint[i].str; ++i)
- CU_ASSERT_EQUAL(dm_regex_match(scanner, nonprint[i].str), nonprint[i].expected - 1);
+ T_ASSERT_EQUAL(dm_regex_match(scanner, nonprint[i].str), nonprint[i].expected - 1);
}
-CU_TestInfo regex_list[] = {
- { (char*)"fingerprints", test_fingerprints },
- { (char*)"matching", test_matching },
- CU_TEST_INFO_NULL
-};
+static void test_kabi_query(void *fixture)
+{
+ // Remember, matches regexes from last to first.
+ static const char *_patterns[] = {
+ ".*", ".*/dev/md.*", "loop"
+ };
+
+ static struct {
+ const char *input;
+ int r;
+ } _cases[] = {
+ {"foo", 0},
+ {"/dev/mapper/vg-lvol1", 0},
+ {"/dev/mapper/vglvol1", 0},
+ {"/dev/md1", 1},
+ {"loop", 2},
+ };
+
+ int r;
+ unsigned i;
+ struct dm_pool *mem = fixture;
+ struct dm_regex *scanner;
+
+ scanner = dm_regex_create(mem, _patterns, DM_ARRAY_SIZE(_patterns));
+ T_ASSERT(scanner != NULL);
+
+ for (i = 0; i < DM_ARRAY_SIZE(_cases); i++) {
+ r = dm_regex_match(scanner, _cases[i].input);
+ if (r != _cases[i].r) {
+ test_fail("'%s' expected to match '%s', but matched %s",
+ _cases[i].input,
+ _cases[i].r >= DM_ARRAY_SIZE(_patterns) ? "<nothing>" : _patterns[_cases[i].r],
+ r >= DM_ARRAY_SIZE(_patterns) ? "<nothing>" : _patterns[r]);
+ }
+ }
+
+}
+
+#define T(path, desc, fn) register_test(ts, "/base/regex/" path, desc, fn)
+
+void regex_tests(struct dm_list *all_tests)
+{
+ struct test_suite *ts = test_suite_create(_mem_init, _mem_exit);
+ if (!ts) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+
+ T("fingerprints", "not sure", test_fingerprints);
+ T("matching", "test the matcher with a variety of regexes", test_matching);
+ T("kabi-query", "test the matcher with some specific patterns", test_kabi_query);
+
+ dm_list_add(all_tests, &ts->list);
+}
diff --git a/test/unit/percent_t.c b/test/unit/percent_t.c
new file mode 100644
index 0000000..3575e12
--- /dev/null
+++ b/test/unit/percent_t.c
@@ -0,0 +1,102 @@
+/*
+ * Copyright (C) 2017 Red Hat, Inc. All rights reserved.
+ *
+ * This file is part of LVM2.
+ *
+ * This copyrighted material is made available to anyone wishing to use,
+ * modify, copy, or redistribute it subject to the terms and conditions
+ * of the GNU General Public License v.2.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include "units.h"
+#include "device_mapper/all.h"
+
+#include <stdio.h>
+#include <string.h>
+
+static void test_percent_100(void *fixture)
+{
+ char buf[32];
+
+ /* Check 100% is shown only for DM_PERCENT_100*/
+ dm_percent_t p_100 = dm_make_percent(100, 100);
+ dm_percent_t p1_100 = dm_make_percent(100000, 100000);
+ dm_percent_t n_100 = dm_make_percent(999999, 1000000);
+
+ T_ASSERT_EQUAL(p_100, DM_PERCENT_100);
+ T_ASSERT_EQUAL(p1_100, DM_PERCENT_100);
+ T_ASSERT_NOT_EQUAL(n_100, DM_PERCENT_100);
+
+ (void) dm_snprintf(buf, sizeof(buf), "%.2f", dm_percent_to_float(p_100));
+ T_ASSERT_EQUAL(strcmp(buf, "100.00"), 0);
+
+ (void) dm_snprintf(buf, sizeof(buf), "%.2f", dm_percent_to_float(p1_100));
+ T_ASSERT_EQUAL(strcmp(buf, "100.00"), 0);
+
+ (void) dm_snprintf(buf, sizeof(buf), "%.2f", dm_percent_to_float(n_100));
+ T_ASSERT_NOT_EQUAL(strcmp(buf, "99.99"), 0); /* Would like to gett */
+
+ (void) dm_snprintf(buf, sizeof(buf), "%.2f", dm_percent_to_round_float(n_100, 2));
+ T_ASSERT_EQUAL(strcmp(buf, "99.99"), 0);
+
+ (void) dm_snprintf(buf, sizeof(buf), "%.3f", dm_percent_to_round_float(n_100, 3));
+ T_ASSERT_EQUAL(strcmp(buf, "99.999"), 0);
+
+ (void) dm_snprintf(buf, sizeof(buf), "%.4f", dm_percent_to_round_float(n_100, 4));
+ T_ASSERT_EQUAL(strcmp(buf, "99.9999"), 0);
+
+ (void) dm_snprintf(buf, sizeof(buf), "%d", (int)dm_percent_to_round_float(n_100, 0));
+ T_ASSERT_EQUAL(strcmp(buf, "99"), 0);
+}
+
+static void test_percent_0(void *fixture)
+{
+ char buf[32];
+
+ /* Check 0% is shown only for DM_PERCENT_0 */
+ dm_percent_t p_0 = dm_make_percent(0, 100);
+ dm_percent_t p1_0 = dm_make_percent(0, 100000);
+ dm_percent_t n_0 = dm_make_percent(1, 1000000);
+
+ T_ASSERT_EQUAL(p_0, DM_PERCENT_0);
+ T_ASSERT_EQUAL(p1_0, DM_PERCENT_0);
+ T_ASSERT_NOT_EQUAL(n_0, DM_PERCENT_0);
+
+ (void) dm_snprintf(buf, sizeof(buf), "%.2f", dm_percent_to_float(p_0));
+ T_ASSERT_EQUAL(strcmp(buf, "0.00"), 0);
+
+ (void) dm_snprintf(buf, sizeof(buf), "%.2f", dm_percent_to_float(p1_0));
+ T_ASSERT_EQUAL(strcmp(buf, "0.00"), 0);
+
+ (void) dm_snprintf(buf, sizeof(buf), "%.2f", dm_percent_to_float(n_0));
+ T_ASSERT_NOT_EQUAL(strcmp(buf, "0.01"), 0);
+
+ (void) dm_snprintf(buf, sizeof(buf), "%.2f", dm_percent_to_round_float(n_0, 2));
+ T_ASSERT_EQUAL(strcmp(buf, "0.01"), 0);
+
+ (void) dm_snprintf(buf, sizeof(buf), "%.3f", dm_percent_to_round_float(n_0, 3));
+ T_ASSERT_EQUAL(strcmp(buf, "0.001"), 0);
+
+ (void) dm_snprintf(buf, sizeof(buf), "%d", (int)dm_percent_to_round_float(n_0, 0));
+ T_ASSERT_EQUAL(strcmp(buf, "1"), 0);
+}
+
+#define T(path, desc, fn) register_test(ts, "/base/formatting/percent/" path, desc, fn)
+
+void percent_tests(struct dm_list *all_tests)
+{
+ struct test_suite *ts = test_suite_create(NULL, NULL);
+ if (!ts) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+
+ T("100", "Pretty printing of percentages near 100%", test_percent_100);
+ T("0", "Pretty printing of percentages near 0%", test_percent_0);
+
+ dm_list_add(all_tests, &ts->list);
+}
diff --git a/test/unit/radix_tree_t.c b/test/unit/radix_tree_t.c
new file mode 100644
index 0000000..b80e4f8
--- /dev/null
+++ b/test/unit/radix_tree_t.c
@@ -0,0 +1,852 @@
+// Copyright (C) 2018 Red Hat, Inc. All rights reserved.
+//
+// This file is part of LVM2.
+//
+// This copyrighted material is made available to anyone wishing to use,
+// modify, copy, or redistribute it subject to the terms and conditions
+// of the GNU Lesser General Public License v.2.1.
+//
+// You should have received a copy of the GNU Lesser General Public License
+// along with this program; if not, write to the Free Software Foundation,
+// Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+#include "units.h"
+#include "base/data-struct/radix-tree.h"
+#include "base/memory/container_of.h"
+
+#include <stdio.h>
+#include <stdlib.h>
+
+//----------------------------------------------------------------
+
+static void *rt_init(void)
+{
+ struct radix_tree *rt = radix_tree_create(NULL, NULL);
+ T_ASSERT(rt);
+ return rt;
+}
+
+static void rt_exit(void *fixture)
+{
+ if (fixture)
+ radix_tree_destroy(fixture);
+}
+
+static void test_create_destroy(void *fixture)
+{
+ T_ASSERT(fixture);
+}
+
+static void test_insert_one(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ union radix_value v;
+ unsigned char k = 'a';
+ v.n = 65;
+ T_ASSERT(radix_tree_insert(rt, &k, &k + 1, v));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ v.n = 0;
+ T_ASSERT(radix_tree_lookup(rt, &k, &k + 1, &v));
+ T_ASSERT_EQUAL(v.n, 65);
+}
+
+static void test_single_byte_keys(void *fixture)
+{
+ unsigned i, count = 256;
+ struct radix_tree *rt = fixture;
+ union radix_value v;
+ uint8_t k;
+
+ for (i = 0; i < count; i++) {
+ k = i;
+ v.n = 100 + i;
+ T_ASSERT(radix_tree_insert(rt, &k, &k + 1, v));
+ }
+
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ for (i = 0; i < count; i++) {
+ k = i;
+ T_ASSERT(radix_tree_lookup(rt, &k, &k + 1, &v));
+ T_ASSERT_EQUAL(v.n, 100 + i);
+ }
+}
+
+static void test_overwrite_single_byte_keys(void *fixture)
+{
+ unsigned i, count = 256;
+ struct radix_tree *rt = fixture;
+ union radix_value v;
+ uint8_t k;
+
+ for (i = 0; i < count; i++) {
+ k = i;
+ v.n = 100 + i;
+ T_ASSERT(radix_tree_insert(rt, &k, &k + 1, v));
+ }
+
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ for (i = 0; i < count; i++) {
+ k = i;
+ v.n = 1000 + i;
+ T_ASSERT(radix_tree_insert(rt, &k, &k + 1, v));
+ }
+
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ for (i = 0; i < count; i++) {
+ k = i;
+ T_ASSERT(radix_tree_lookup(rt, &k, &k + 1, &v));
+ T_ASSERT_EQUAL(v.n, 1000 + i);
+ }
+}
+
+static void test_16_bit_keys(void *fixture)
+{
+ unsigned i, count = 1 << 16;
+ struct radix_tree *rt = fixture;
+ union radix_value v;
+ uint8_t k[2];
+
+ for (i = 0; i < count; i++) {
+ k[0] = i / 256;
+ k[1] = i % 256;
+ v.n = 100 + i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ }
+
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ for (i = 0; i < count; i++) {
+ k[0] = i / 256;
+ k[1] = i % 256;
+ T_ASSERT(radix_tree_lookup(rt, k, k + sizeof(k), &v));
+ T_ASSERT_EQUAL(v.n, 100 + i);
+ }
+}
+
+static void test_prefix_keys(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ union radix_value v;
+ uint8_t k[2];
+
+ k[0] = 100;
+ k[1] = 200;
+ v.n = 1024;
+ T_ASSERT(radix_tree_insert(rt, k, k + 1, v));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ v.n = 2345;
+ T_ASSERT(radix_tree_insert(rt, k, k + 2, v));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ T_ASSERT(radix_tree_lookup(rt, k, k + 1, &v));
+ T_ASSERT_EQUAL(v.n, 1024);
+ T_ASSERT(radix_tree_lookup(rt, k, k + 2, &v));
+ T_ASSERT_EQUAL(v.n, 2345);
+}
+
+static void test_prefix_keys_reversed(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ union radix_value v;
+ uint8_t k[2];
+
+ k[0] = 100;
+ k[1] = 200;
+ v.n = 1024;
+ T_ASSERT(radix_tree_insert(rt, k, k + 2, v));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ v.n = 2345;
+ T_ASSERT(radix_tree_insert(rt, k, k + 1, v));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ T_ASSERT(radix_tree_lookup(rt, k, k + 2, &v));
+ T_ASSERT_EQUAL(v.n, 1024);
+ T_ASSERT(radix_tree_lookup(rt, k, k + 1, &v));
+ T_ASSERT_EQUAL(v.n, 2345);
+}
+
+static void _gen_key(uint8_t *b, uint8_t *e)
+{
+ for (; b != e; b++)
+ /* coverity[dont_call] don't care */
+ *b = rand() % 256;
+}
+
+static void test_sparse_keys(void *fixture)
+{
+ unsigned n;
+ struct radix_tree *rt = fixture;
+ union radix_value v;
+ uint8_t k[32];
+
+ for (n = 0; n < 100000; n++) {
+ _gen_key(k, k + sizeof(k));
+ v.n = 1234;
+ T_ASSERT(radix_tree_insert(rt, k, k + 32, v));
+ // FIXME: remove
+ //T_ASSERT(radix_tree_is_well_formed(rt));
+ }
+ T_ASSERT(radix_tree_is_well_formed(rt));
+}
+
+static void test_remove_one(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ uint8_t k[4];
+ union radix_value v;
+
+ _gen_key(k, k + sizeof(k));
+ v.n = 1234;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ T_ASSERT(radix_tree_remove(rt, k, k + sizeof(k)));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ T_ASSERT(!radix_tree_lookup(rt, k, k + sizeof(k), &v));
+}
+
+static void test_remove_one_byte_keys(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ unsigned i, j;
+ uint8_t k[1];
+ union radix_value v;
+
+ for (i = 0; i < 256; i++) {
+ k[0] = i;
+ v.n = i + 1000;
+ T_ASSERT(radix_tree_insert(rt, k, k + 1, v));
+ }
+
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ for (i = 0; i < 256; i++) {
+ k[0] = i;
+ T_ASSERT(radix_tree_remove(rt, k, k + 1));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ for (j = i + 1; j < 256; j++) {
+ k[0] = j;
+ T_ASSERT(radix_tree_lookup(rt, k, k + 1, &v));
+ if (v.n != j + 1000)
+ test_fail("v.n (%u) != j + 1000 (%u)\n",
+ (unsigned) v.n,
+ (unsigned) j + 1000);
+ }
+ }
+
+ for (i = 0; i < 256; i++) {
+ k[0] = i;
+ T_ASSERT(!radix_tree_lookup(rt, k, k + 1, &v));
+ }
+}
+
+static void test_remove_one_byte_keys_reversed(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ unsigned i, j;
+ uint8_t k[1];
+ union radix_value v;
+
+ for (i = 0; i < 256; i++) {
+ k[0] = i;
+ v.n = i + 1000;
+ T_ASSERT(radix_tree_insert(rt, k, k + 1, v));
+ }
+
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ for (i = 256; i; i--) {
+ k[0] = i - 1;
+ T_ASSERT(radix_tree_remove(rt, k, k + 1));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ for (j = 0; j < i - 1; j++) {
+ k[0] = j;
+ T_ASSERT(radix_tree_lookup(rt, k, k + 1, &v));
+ if (v.n != j + 1000)
+ test_fail("v.n (%u) != j + 1000 (%u)\n",
+ (unsigned) v.n,
+ (unsigned) j + 1000);
+ }
+ }
+
+ for (i = 0; i < 256; i++) {
+ k[0] = i;
+ T_ASSERT(!radix_tree_lookup(rt, k, k + 1, &v));
+ }
+}
+static void test_remove_prefix_keys(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ unsigned i, j;
+ uint8_t k[32];
+ union radix_value v;
+
+ _gen_key(k, k + sizeof(k));
+
+ for (i = 0; i < 32; i++) {
+ v.n = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + i, v));
+ }
+
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ for (i = 0; i < 32; i++) {
+ T_ASSERT(radix_tree_remove(rt, k, k + i));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ for (j = i + 1; j < 32; j++) {
+ T_ASSERT(radix_tree_lookup(rt, k, k + j, &v));
+ T_ASSERT_EQUAL(v.n, j);
+ }
+ }
+
+ for (i = 0; i < 32; i++)
+ T_ASSERT(!radix_tree_lookup(rt, k, k + i, &v));
+}
+
+static void test_remove_prefix_keys_reversed(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ unsigned i, j;
+ uint8_t k[32];
+ union radix_value v;
+
+ _gen_key(k, k + sizeof(k));
+
+ for (i = 0; i < 32; i++) {
+ v.n = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + i, v));
+ }
+
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ for (i = 0; i < 32; i++) {
+ T_ASSERT(radix_tree_remove(rt, k, k + (31 - i)));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ for (j = 0; j < 31 - i; j++) {
+ T_ASSERT(radix_tree_lookup(rt, k, k + j, &v));
+ T_ASSERT_EQUAL(v.n, j);
+ }
+ }
+
+ for (i = 0; i < 32; i++)
+ T_ASSERT(!radix_tree_lookup(rt, k, k + i, &v));
+}
+
+static void test_remove_prefix(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ unsigned i, count = 0;
+ uint8_t k[4];
+ union radix_value v;
+
+ // populate some random 32bit keys
+ for (i = 0; i < 100000; i++) {
+ _gen_key(k, k + sizeof(k));
+ if (k[0] == 21)
+ count++;
+ v.n = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ }
+
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ // remove keys in a sub range
+ k[0] = 21;
+ T_ASSERT_EQUAL(radix_tree_remove_prefix(rt, k, k + 1), count);
+ T_ASSERT(radix_tree_is_well_formed(rt));
+}
+
+static void test_remove_prefix_single(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ uint8_t k[4];
+ union radix_value v;
+
+ _gen_key(k, k + sizeof(k));
+ v.n = 1234;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ T_ASSERT_EQUAL(radix_tree_remove_prefix(rt, k, k + 2), 1);
+ T_ASSERT(radix_tree_is_well_formed(rt));
+}
+
+static void test_size(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ unsigned i, dup_count = 0;
+ uint8_t k[2];
+ union radix_value v;
+
+ // populate some random 16bit keys
+ for (i = 0; i < 10000; i++) {
+ _gen_key(k, k + sizeof(k));
+ if (radix_tree_lookup(rt, k, k + sizeof(k), &v))
+ dup_count++;
+ v.n = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ }
+
+ T_ASSERT_EQUAL(radix_tree_size(rt), 10000 - dup_count);
+ T_ASSERT(radix_tree_is_well_formed(rt));
+}
+
+struct visitor {
+ struct radix_tree_iterator it;
+ unsigned count;
+};
+
+static bool _visit(struct radix_tree_iterator *it,
+ uint8_t *kb, uint8_t *ke, union radix_value v)
+{
+ struct visitor *vt = container_of(it, struct visitor, it);
+ vt->count++;
+ return true;
+}
+
+static void test_iterate_all(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ unsigned i;
+ uint8_t k[4];
+ union radix_value v;
+ struct visitor vt;
+
+ // populate some random 32bit keys
+ for (i = 0; i < 100000; i++) {
+ _gen_key(k, k + sizeof(k));
+ v.n = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ }
+
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ vt.count = 0;
+ vt.it.visit = _visit;
+ radix_tree_iterate(rt, NULL, NULL, &vt.it);
+ T_ASSERT_EQUAL(vt.count, radix_tree_size(rt));
+}
+
+static void test_iterate_subset(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ unsigned i, subset_count = 0;
+ uint8_t k[3];
+ union radix_value v;
+ struct visitor vt;
+
+ // populate some random 32bit keys
+ for (i = 0; i < 100000; i++) {
+ _gen_key(k, k + sizeof(k));
+ if (k[0] == 21 && k[1] == 12)
+ subset_count++;
+ v.n = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ }
+
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ vt.count = 0;
+ vt.it.visit = _visit;
+ k[0] = 21;
+ k[1] = 12;
+ radix_tree_iterate(rt, k, k + 2, &vt.it);
+ T_ASSERT_EQUAL(vt.count, subset_count);
+}
+
+static void test_iterate_single(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ uint8_t k[6];
+ union radix_value v;
+ struct visitor vt;
+
+ _gen_key(k, k + sizeof(k));
+ v.n = 1234;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ vt.count = 0;
+ vt.it.visit = _visit;
+ radix_tree_iterate(rt, k, k + 3, &vt.it);
+ T_ASSERT_EQUAL(vt.count, 1);
+}
+
+static void test_iterate_vary_middle(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+ unsigned i;
+ uint8_t k[6];
+ union radix_value v;
+ struct visitor vt;
+
+ _gen_key(k, k + sizeof(k));
+ for (i = 0; i < 16; i++) {
+ k[3] = i;
+ v.n = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ }
+
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ vt.it.visit = _visit;
+ for (i = 0; i < 16; i++) {
+ vt.count = 0;
+ k[3] = i;
+ radix_tree_iterate(rt, k, k + 4, &vt.it);
+ T_ASSERT_EQUAL(vt.count, 1);
+ }
+}
+
+//----------------------------------------------------------------
+
+#define DTR_COUNT 100
+
+struct counter {
+ unsigned c;
+ uint8_t present[DTR_COUNT];
+};
+
+static void _counting_dtr(void *context, union radix_value v)
+{
+ struct counter *c = context;
+ c->c++;
+ T_ASSERT(v.n < DTR_COUNT);
+ c->present[v.n] = 0;
+}
+
+static void test_remove_calls_dtr(void *fixture)
+{
+ struct counter c;
+ struct radix_tree *rt = radix_tree_create(_counting_dtr, &c);
+ T_ASSERT(rt);
+
+ // Bug hunting, so I need the keys to be deterministic
+ srand(0);
+
+ c.c = 0;
+ memset(c.present, 1, sizeof(c.present));
+
+ {
+ unsigned i;
+ uint8_t keys[DTR_COUNT * 3];
+ union radix_value v;
+
+ // generate and insert a lot of keys
+ for (i = 0; i < DTR_COUNT; i++) {
+ bool found = false;
+ do {
+ v.n = i;
+ uint8_t *k = keys + (i * 3);
+ _gen_key(k, k + 3);
+ if (!radix_tree_lookup(rt, k, k + 3, &v)) {
+ T_ASSERT(radix_tree_insert(rt, k, k + 3, v));
+ found = true;
+ }
+
+ } while (!found);
+ }
+
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ // double check
+ for (i = 0; i < DTR_COUNT; i++) {
+ uint8_t *k = keys + (i * 3);
+ T_ASSERT(radix_tree_lookup(rt, k, k + 3, &v));
+ }
+
+ for (i = 0; i < DTR_COUNT; i++) {
+ uint8_t *k = keys + (i * 3);
+ // FIXME: check the values get passed to the dtr
+ T_ASSERT(radix_tree_remove(rt, k, k + 3));
+ }
+
+ T_ASSERT(c.c == DTR_COUNT);
+ for (i = 0; i < DTR_COUNT; i++)
+ T_ASSERT(!c.present[i]);
+ }
+
+ radix_tree_destroy(rt);
+}
+
+static void test_destroy_calls_dtr(void *fixture)
+{
+ unsigned i;
+ struct counter c;
+ struct radix_tree *rt = radix_tree_create(_counting_dtr, &c);
+ T_ASSERT(rt);
+
+ // Bug hunting, so I need the keys to be deterministic
+ srand(0);
+
+ c.c = 0;
+ memset(c.present, 1, sizeof(c.present));
+
+ {
+ uint8_t keys[DTR_COUNT * 3];
+ union radix_value v;
+
+ // generate and insert a lot of keys
+ for (i = 0; i < DTR_COUNT; i++) {
+ bool found = false;
+ do {
+ v.n = i;
+ uint8_t *k = keys + (i * 3);
+ _gen_key(k, k + 3);
+ if (!radix_tree_lookup(rt, k, k + 3, &v)) {
+ T_ASSERT(radix_tree_insert(rt, k, k + 3, v));
+ found = true;
+ }
+
+ } while (!found);
+ }
+
+ T_ASSERT(radix_tree_is_well_formed(rt));
+ }
+
+ radix_tree_destroy(rt);
+ T_ASSERT(c.c == DTR_COUNT);
+ for (i = 0; i < DTR_COUNT; i++)
+ T_ASSERT(!c.present[i]);
+}
+
+//----------------------------------------------------------------
+
+static void test_bcache_scenario(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+
+ unsigned i;
+ uint8_t k[6];
+ union radix_value v;
+
+ memset(k, 0, sizeof(k));
+
+ for (i = 0; i < 3; i++) {
+ // it has to be the 4th byte that varies to
+ // trigger the bug.
+ k[4] = i;
+ v.n = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ }
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ k[4] = 0;
+ T_ASSERT(radix_tree_remove(rt, k, k + sizeof(k)));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ k[4] = i;
+ v.n = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+}
+
+//----------------------------------------------------------------
+
+static void _bcs2_step1(struct radix_tree *rt)
+{
+ unsigned i;
+ uint8_t k[12];
+ union radix_value v;
+
+ memset(k, 0, sizeof(k));
+ for (i = 0x6; i < 0x69; i++) {
+ k[0] = i;
+ v.n = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ }
+ T_ASSERT(radix_tree_is_well_formed(rt));
+}
+
+static void _bcs2_step2(struct radix_tree *rt)
+{
+ unsigned i;
+ uint8_t k[12];
+
+ memset(k, 0, sizeof(k));
+ for (i = 0x6; i < 0x69; i++) {
+ k[0] = i;
+ radix_tree_remove_prefix(rt, k, k + 4);
+ }
+ T_ASSERT(radix_tree_is_well_formed(rt));
+}
+
+static void test_bcache_scenario2(void *fixture)
+{
+ unsigned i;
+ struct radix_tree *rt = fixture;
+ uint8_t k[12];
+ union radix_value v;
+
+ _bcs2_step1(rt);
+ _bcs2_step2(rt);
+
+ memset(k, 0, sizeof(k));
+ for (i = 0; i < 50; i++) {
+ k[0] = 0x6;
+ v.n = 0x6;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ radix_tree_remove_prefix(rt, k, k + 4);
+ }
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ _bcs2_step1(rt);
+ _bcs2_step2(rt);
+ _bcs2_step1(rt);
+ _bcs2_step2(rt);
+
+ memset(k, 0, sizeof(k));
+ for(i = 0x6; i < 0x37; i++) {
+ k[0] = i;
+ k[4] = 0xf;
+ k[5] = 0x1;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ k[4] = 0;
+ k[5] = 0;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ }
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ memset(k, 0, sizeof(k));
+ for (i = 0x38; i < 0x69; i++) {
+ k[0] = i - 0x32;
+ k[4] = 0xf;
+ k[5] = 1;
+ T_ASSERT(radix_tree_remove(rt, k, k + sizeof(k)));
+
+ k[0] = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+
+ k[0] = i - 0x32;
+ k[4] = 0;
+ k[5] = 0;
+ T_ASSERT(radix_tree_remove(rt, k, k + sizeof(k)));
+
+ k[0] = i;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ }
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ memset(k, 0, sizeof(k));
+ k[0] = 0x6;
+ radix_tree_remove_prefix(rt, k, k + 4);
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ k[0] = 0x38;
+ k[4] = 0xf;
+ k[5] = 0x1;
+ T_ASSERT(radix_tree_remove(rt, k, k + sizeof(k)));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ memset(k, 0, sizeof(k));
+ k[0] = 0x6;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ k[0] = 0x7;
+ radix_tree_remove_prefix(rt, k, k + 4);
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ k[0] = 0x38;
+ T_ASSERT(radix_tree_remove(rt, k, k + sizeof(k)));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+
+ k[0] = 7;
+ T_ASSERT(radix_tree_insert(rt, k, k + sizeof(k), v));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+}
+
+//----------------------------------------------------------------
+
+struct key_parts {
+ uint32_t fd;
+ uint64_t b;
+} __attribute__ ((packed));
+
+union key {
+ struct key_parts parts;
+ uint8_t bytes[12];
+};
+
+static void __lookup_matches(struct radix_tree *rt, int fd, uint64_t b, uint64_t expected)
+{
+ union key k;
+ union radix_value v;
+
+ k.parts.fd = fd;
+ k.parts.b = b;
+ T_ASSERT(radix_tree_lookup(rt, k.bytes, k.bytes + sizeof(k.bytes), &v));
+ T_ASSERT(v.n == expected);
+}
+
+static void __lookup_fails(struct radix_tree *rt, int fd, uint64_t b)
+{
+ union key k;
+ union radix_value v;
+
+ k.parts.fd = fd;
+ k.parts.b = b;
+ T_ASSERT(!radix_tree_lookup(rt, k.bytes, k.bytes + sizeof(k.bytes), &v));
+}
+
+static void __insert(struct radix_tree *rt, int fd, uint64_t b, uint64_t n)
+{
+ union key k;
+ union radix_value v;
+
+ k.parts.fd = fd;
+ k.parts.b = b;
+ v.n = n;
+ T_ASSERT(radix_tree_insert(rt, k.bytes, k.bytes + sizeof(k.bytes), v));
+}
+
+static void __invalidate(struct radix_tree *rt, int fd)
+{
+ union key k;
+
+ k.parts.fd = fd;
+ radix_tree_remove_prefix(rt, k.bytes, k.bytes + sizeof(k.parts.fd));
+ T_ASSERT(radix_tree_is_well_formed(rt));
+}
+
+static void test_bcache_scenario3(void *fixture)
+{
+ struct radix_tree *rt = fixture;
+
+ #include "test/unit/rt_case1.c"
+}
+
+//----------------------------------------------------------------
+#define T(path, desc, fn) register_test(ts, "/base/data-struct/radix-tree/" path, desc, fn)
+
+void radix_tree_tests(struct dm_list *all_tests)
+{
+ struct test_suite *ts = test_suite_create(rt_init, rt_exit);
+ if (!ts) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+
+ T("create-destroy", "create and destroy an empty tree", test_create_destroy);
+ T("insert-one", "insert one trivial trivial key", test_insert_one);
+ T("insert-single-byte-keys", "inserts many single byte keys", test_single_byte_keys);
+ T("overwrite-single-byte-keys", "overwrite many single byte keys", test_overwrite_single_byte_keys);
+ T("insert-16-bit-keys", "insert many 16bit keys", test_16_bit_keys);
+ T("prefix-keys", "prefixes of other keys are valid keys", test_prefix_keys);
+ T("prefix-keys-reversed", "prefixes of other keys are valid keys", test_prefix_keys_reversed);
+ T("sparse-keys", "see what the memory usage is for sparsely distributed keys", test_sparse_keys);
+ T("remove-one", "remove one entry", test_remove_one);
+ T("remove-one-byte-keys", "remove many one byte keys", test_remove_one_byte_keys);
+ T("remove-one-byte-keys-reversed", "remove many one byte keys reversed", test_remove_one_byte_keys_reversed);
+ T("remove-prefix-keys", "remove a set of keys that have common prefixes", test_remove_prefix_keys);
+ T("remove-prefix-keys-reversed", "remove a set of keys that have common prefixes (reversed)", test_remove_prefix_keys_reversed);
+ T("remove-prefix", "remove a subrange", test_remove_prefix);
+ T("remove-prefix-single", "remove a subrange with a single entry", test_remove_prefix_single);
+ T("size-spots-duplicates", "duplicate entries aren't counted twice", test_size);
+ T("iterate-all", "iterate all entries in tree", test_iterate_all);
+ T("iterate-subset", "iterate a subset of entries in tree", test_iterate_subset);
+ T("iterate-single", "iterate a subset that contains a single entry", test_iterate_single);
+ T("iterate-vary-middle", "iterate keys that vary in the middle", test_iterate_vary_middle);
+ T("remove-calls-dtr", "remove should call the dtr for the value", test_remove_calls_dtr);
+ T("destroy-calls-dtr", "destroy should call the dtr for all values", test_destroy_calls_dtr);
+ T("bcache-scenario", "A specific series of keys from a bcache scenario", test_bcache_scenario);
+ T("bcache-scenario-2", "A second series of keys from a bcache scenario", test_bcache_scenario2);
+ T("bcache-scenario-3", "A third series of keys from a bcache scenario", test_bcache_scenario3);
+
+ dm_list_add(all_tests, &ts->list);
+}
+//----------------------------------------------------------------
diff --git a/test/unit/rt_case1.c b/test/unit/rt_case1.c
new file mode 100644
index 0000000..c1677d1
--- /dev/null
+++ b/test/unit/rt_case1.c
@@ -0,0 +1,1669 @@
+ __lookup_fails(rt, 6, 0);
+ __insert(rt, 6, 0, 0);
+ __lookup_fails(rt, 7, 0);
+ __insert(rt, 7, 0, 1);
+ __lookup_fails(rt, 8, 0);
+ __insert(rt, 8, 0, 2);
+ __lookup_fails(rt, 9, 0);
+ __insert(rt, 9, 0, 3);
+ __lookup_fails(rt, 10, 0);
+ __insert(rt, 10, 0, 4);
+ __lookup_fails(rt, 11, 0);
+ __insert(rt, 11, 0, 5);
+ __lookup_fails(rt, 12, 0);
+ __insert(rt, 12, 0, 6);
+ __lookup_fails(rt, 13, 0);
+ __insert(rt, 13, 0, 7);
+ __lookup_fails(rt, 14, 0);
+ __insert(rt, 14, 0, 8);
+ __lookup_fails(rt, 15, 0);
+ __insert(rt, 15, 0, 9);
+ __lookup_fails(rt, 16, 0);
+ __insert(rt, 16, 0, 10);
+ __lookup_fails(rt, 17, 0);
+ __insert(rt, 17, 0, 11);
+ __lookup_fails(rt, 18, 0);
+ __insert(rt, 18, 0, 12);
+ __lookup_fails(rt, 19, 0);
+ __insert(rt, 19, 0, 13);
+ __lookup_fails(rt, 20, 0);
+ __insert(rt, 20, 0, 14);
+ __lookup_fails(rt, 21, 0);
+ __insert(rt, 21, 0, 15);
+ __lookup_fails(rt, 22, 0);
+ __insert(rt, 22, 0, 16);
+ __lookup_fails(rt, 23, 0);
+ __insert(rt, 23, 0, 17);
+ __lookup_fails(rt, 24, 0);
+ __insert(rt, 24, 0, 18);
+ __lookup_fails(rt, 25, 0);
+ __insert(rt, 25, 0, 19);
+ __lookup_fails(rt, 26, 0);
+ __insert(rt, 26, 0, 20);
+ __lookup_fails(rt, 27, 0);
+ __insert(rt, 27, 0, 21);
+ __lookup_fails(rt, 28, 0);
+ __insert(rt, 28, 0, 22);
+ __lookup_fails(rt, 29, 0);
+ __insert(rt, 29, 0, 23);
+ __lookup_fails(rt, 30, 0);
+ __insert(rt, 30, 0, 24);
+ __lookup_fails(rt, 31, 0);
+ __insert(rt, 31, 0, 25);
+ __lookup_fails(rt, 32, 0);
+ __insert(rt, 32, 0, 26);
+ __lookup_fails(rt, 33, 0);
+ __insert(rt, 33, 0, 27);
+ __lookup_fails(rt, 34, 0);
+ __insert(rt, 34, 0, 28);
+ __lookup_fails(rt, 35, 0);
+ __insert(rt, 35, 0, 29);
+ __lookup_fails(rt, 36, 0);
+ __insert(rt, 36, 0, 30);
+ __lookup_fails(rt, 37, 0);
+ __insert(rt, 37, 0, 31);
+ __lookup_fails(rt, 38, 0);
+ __insert(rt, 38, 0, 32);
+ __lookup_fails(rt, 39, 0);
+ __insert(rt, 39, 0, 33);
+ __lookup_fails(rt, 40, 0);
+ __insert(rt, 40, 0, 34);
+ __lookup_fails(rt, 41, 0);
+ __insert(rt, 41, 0, 35);
+ __lookup_fails(rt, 42, 0);
+ __insert(rt, 42, 0, 36);
+ __lookup_fails(rt, 43, 0);
+ __insert(rt, 43, 0, 37);
+ __lookup_fails(rt, 44, 0);
+ __insert(rt, 44, 0, 38);
+ __lookup_fails(rt, 45, 0);
+ __insert(rt, 45, 0, 39);
+ __lookup_fails(rt, 46, 0);
+ __insert(rt, 46, 0, 40);
+ __lookup_fails(rt, 47, 0);
+ __insert(rt, 47, 0, 41);
+ __lookup_fails(rt, 48, 0);
+ __insert(rt, 48, 0, 42);
+ __lookup_fails(rt, 49, 0);
+ __insert(rt, 49, 0, 43);
+ __lookup_fails(rt, 50, 0);
+ __insert(rt, 50, 0, 44);
+ __lookup_fails(rt, 51, 0);
+ __insert(rt, 51, 0, 45);
+ __lookup_fails(rt, 52, 0);
+ __insert(rt, 52, 0, 46);
+ __lookup_fails(rt, 53, 0);
+ __insert(rt, 53, 0, 47);
+ __lookup_fails(rt, 54, 0);
+ __insert(rt, 54, 0, 48);
+ __lookup_fails(rt, 55, 0);
+ __insert(rt, 55, 0, 49);
+ __lookup_fails(rt, 56, 0);
+ __insert(rt, 56, 0, 50);
+ __lookup_fails(rt, 57, 0);
+ __insert(rt, 57, 0, 51);
+ __lookup_fails(rt, 58, 0);
+ __insert(rt, 58, 0, 52);
+ __lookup_fails(rt, 59, 0);
+ __insert(rt, 59, 0, 53);
+ __lookup_fails(rt, 60, 0);
+ __insert(rt, 60, 0, 54);
+ __lookup_fails(rt, 61, 0);
+ __insert(rt, 61, 0, 55);
+ __lookup_fails(rt, 62, 0);
+ __insert(rt, 62, 0, 56);
+ __lookup_fails(rt, 63, 0);
+ __insert(rt, 63, 0, 57);
+ __lookup_fails(rt, 64, 0);
+ __insert(rt, 64, 0, 58);
+ __lookup_fails(rt, 65, 0);
+ __insert(rt, 65, 0, 59);
+ __lookup_fails(rt, 66, 0);
+ __insert(rt, 66, 0, 60);
+ __lookup_fails(rt, 67, 0);
+ __insert(rt, 67, 0, 61);
+ __lookup_fails(rt, 68, 0);
+ __insert(rt, 68, 0, 62);
+ __lookup_fails(rt, 69, 0);
+ __insert(rt, 69, 0, 63);
+ __lookup_fails(rt, 70, 0);
+ __insert(rt, 70, 0, 64);
+ __lookup_fails(rt, 71, 0);
+ __insert(rt, 71, 0, 65);
+ __lookup_fails(rt, 72, 0);
+ __insert(rt, 72, 0, 66);
+ __lookup_fails(rt, 73, 0);
+ __insert(rt, 73, 0, 67);
+ __lookup_fails(rt, 74, 0);
+ __insert(rt, 74, 0, 68);
+ __lookup_fails(rt, 75, 0);
+ __insert(rt, 75, 0, 69);
+ __lookup_fails(rt, 76, 0);
+ __insert(rt, 76, 0, 70);
+ __lookup_fails(rt, 77, 0);
+ __insert(rt, 77, 0, 71);
+ __lookup_fails(rt, 78, 0);
+ __insert(rt, 78, 0, 72);
+ __lookup_fails(rt, 79, 0);
+ __insert(rt, 79, 0, 73);
+ __lookup_fails(rt, 80, 0);
+ __insert(rt, 80, 0, 74);
+ __lookup_fails(rt, 81, 0);
+ __insert(rt, 81, 0, 75);
+ __lookup_fails(rt, 82, 0);
+ __insert(rt, 82, 0, 76);
+ __lookup_fails(rt, 83, 0);
+ __insert(rt, 83, 0, 77);
+ __lookup_fails(rt, 84, 0);
+ __insert(rt, 84, 0, 78);
+ __lookup_fails(rt, 85, 0);
+ __insert(rt, 85, 0, 79);
+ __lookup_fails(rt, 86, 0);
+ __insert(rt, 86, 0, 80);
+ __lookup_fails(rt, 87, 0);
+ __insert(rt, 87, 0, 81);
+ __lookup_fails(rt, 88, 0);
+ __insert(rt, 88, 0, 82);
+ __lookup_fails(rt, 89, 0);
+ __insert(rt, 89, 0, 83);
+ __lookup_fails(rt, 90, 0);
+ __insert(rt, 90, 0, 84);
+ __lookup_fails(rt, 91, 0);
+ __insert(rt, 91, 0, 85);
+ __lookup_fails(rt, 92, 0);
+ __insert(rt, 92, 0, 86);
+ __lookup_fails(rt, 93, 0);
+ __insert(rt, 93, 0, 87);
+ __lookup_fails(rt, 94, 0);
+ __insert(rt, 94, 0, 88);
+ __lookup_fails(rt, 95, 0);
+ __insert(rt, 95, 0, 89);
+ __lookup_fails(rt, 96, 0);
+ __insert(rt, 96, 0, 90);
+ __lookup_fails(rt, 97, 0);
+ __insert(rt, 97, 0, 91);
+ __lookup_fails(rt, 98, 0);
+ __insert(rt, 98, 0, 92);
+ __lookup_fails(rt, 99, 0);
+ __insert(rt, 99, 0, 93);
+ __lookup_fails(rt, 100, 0);
+ __insert(rt, 100, 0, 94);
+ __lookup_fails(rt, 101, 0);
+ __insert(rt, 101, 0, 95);
+ __lookup_fails(rt, 102, 0);
+ __insert(rt, 102, 0, 96);
+ __lookup_fails(rt, 103, 0);
+ __insert(rt, 103, 0, 97);
+ __lookup_fails(rt, 104, 0);
+ __insert(rt, 104, 0, 98);
+ __lookup_fails(rt, 105, 0);
+ __insert(rt, 105, 0, 99);
+ __lookup_fails(rt, 106, 0);
+ __insert(rt, 106, 0, 100);
+ __lookup_fails(rt, 107, 0);
+ __insert(rt, 107, 0, 101);
+ __lookup_fails(rt, 108, 0);
+ __insert(rt, 108, 0, 102);
+ __lookup_fails(rt, 109, 0);
+ __insert(rt, 109, 0, 103);
+ __lookup_fails(rt, 110, 0);
+ __insert(rt, 110, 0, 104);
+ __lookup_fails(rt, 111, 0);
+ __insert(rt, 111, 0, 105);
+ __lookup_fails(rt, 112, 0);
+ __insert(rt, 112, 0, 106);
+ __lookup_fails(rt, 113, 0);
+ __insert(rt, 113, 0, 107);
+ __lookup_fails(rt, 114, 0);
+ __insert(rt, 114, 0, 108);
+ __lookup_fails(rt, 115, 0);
+ __insert(rt, 115, 0, 109);
+ __lookup_fails(rt, 116, 0);
+ __insert(rt, 116, 0, 110);
+ __lookup_fails(rt, 117, 0);
+ __insert(rt, 117, 0, 111);
+ __lookup_fails(rt, 118, 0);
+ __insert(rt, 118, 0, 112);
+ __lookup_fails(rt, 119, 0);
+ __insert(rt, 119, 0, 113);
+ __lookup_fails(rt, 120, 0);
+ __insert(rt, 120, 0, 114);
+ __lookup_fails(rt, 121, 0);
+ __insert(rt, 121, 0, 115);
+ __lookup_fails(rt, 122, 0);
+ __insert(rt, 122, 0, 116);
+ __lookup_fails(rt, 123, 0);
+ __insert(rt, 123, 0, 117);
+ __lookup_fails(rt, 124, 0);
+ __insert(rt, 124, 0, 118);
+ __lookup_fails(rt, 125, 0);
+ __insert(rt, 125, 0, 119);
+ __lookup_fails(rt, 126, 0);
+ __insert(rt, 126, 0, 120);
+ __lookup_fails(rt, 127, 0);
+ __insert(rt, 127, 0, 121);
+ __lookup_fails(rt, 128, 0);
+ __insert(rt, 128, 0, 122);
+ __lookup_fails(rt, 129, 0);
+ __insert(rt, 129, 0, 123);
+ __lookup_fails(rt, 130, 0);
+ __insert(rt, 130, 0, 124);
+ __lookup_fails(rt, 131, 0);
+ __insert(rt, 131, 0, 125);
+ __lookup_fails(rt, 132, 0);
+ __insert(rt, 132, 0, 126);
+ __lookup_fails(rt, 133, 0);
+ __insert(rt, 133, 0, 127);
+ __lookup_fails(rt, 134, 0);
+ __insert(rt, 134, 0, 128);
+ __lookup_fails(rt, 135, 0);
+ __insert(rt, 135, 0, 129);
+ __lookup_fails(rt, 136, 0);
+ __insert(rt, 136, 0, 130);
+ __lookup_fails(rt, 137, 0);
+ __insert(rt, 137, 0, 131);
+ __lookup_fails(rt, 138, 0);
+ __insert(rt, 138, 0, 132);
+ __lookup_fails(rt, 139, 0);
+ __insert(rt, 139, 0, 133);
+ __lookup_fails(rt, 140, 0);
+ __insert(rt, 140, 0, 134);
+ __lookup_fails(rt, 141, 0);
+ __insert(rt, 141, 0, 135);
+ __lookup_fails(rt, 142, 0);
+ __insert(rt, 142, 0, 136);
+ __lookup_fails(rt, 143, 0);
+ __insert(rt, 143, 0, 137);
+ __lookup_fails(rt, 144, 0);
+ __insert(rt, 144, 0, 138);
+ __lookup_fails(rt, 145, 0);
+ __insert(rt, 145, 0, 139);
+ __lookup_fails(rt, 146, 0);
+ __insert(rt, 146, 0, 140);
+ __lookup_fails(rt, 147, 0);
+ __insert(rt, 147, 0, 141);
+ __lookup_fails(rt, 148, 0);
+ __insert(rt, 148, 0, 142);
+ __lookup_fails(rt, 149, 0);
+ __insert(rt, 149, 0, 143);
+ __lookup_fails(rt, 150, 0);
+ __insert(rt, 150, 0, 144);
+ __lookup_fails(rt, 151, 0);
+ __insert(rt, 151, 0, 145);
+ __lookup_fails(rt, 152, 0);
+ __insert(rt, 152, 0, 146);
+ __lookup_fails(rt, 153, 0);
+ __insert(rt, 153, 0, 147);
+ __lookup_fails(rt, 154, 0);
+ __insert(rt, 154, 0, 148);
+ __lookup_fails(rt, 155, 0);
+ __insert(rt, 155, 0, 149);
+ __lookup_fails(rt, 156, 0);
+ __insert(rt, 156, 0, 150);
+ __lookup_fails(rt, 157, 0);
+ __insert(rt, 157, 0, 151);
+ __lookup_fails(rt, 158, 0);
+ __insert(rt, 158, 0, 152);
+ __lookup_fails(rt, 159, 0);
+ __insert(rt, 159, 0, 153);
+ __lookup_fails(rt, 160, 0);
+ __insert(rt, 160, 0, 154);
+ __lookup_fails(rt, 161, 0);
+ __insert(rt, 161, 0, 155);
+ __lookup_fails(rt, 162, 0);
+ __insert(rt, 162, 0, 156);
+ __lookup_fails(rt, 163, 0);
+ __insert(rt, 163, 0, 157);
+ __lookup_fails(rt, 164, 0);
+ __insert(rt, 164, 0, 158);
+ __lookup_fails(rt, 165, 0);
+ __insert(rt, 165, 0, 159);
+ __lookup_fails(rt, 166, 0);
+ __insert(rt, 166, 0, 160);
+ __lookup_fails(rt, 167, 0);
+ __insert(rt, 167, 0, 161);
+ __lookup_fails(rt, 168, 0);
+ __insert(rt, 168, 0, 162);
+ __lookup_fails(rt, 169, 0);
+ __insert(rt, 169, 0, 163);
+ __lookup_fails(rt, 170, 0);
+ __insert(rt, 170, 0, 164);
+ __lookup_fails(rt, 171, 0);
+ __insert(rt, 171, 0, 165);
+ __lookup_fails(rt, 172, 0);
+ __insert(rt, 172, 0, 166);
+ __lookup_fails(rt, 173, 0);
+ __insert(rt, 173, 0, 167);
+ __lookup_fails(rt, 174, 0);
+ __insert(rt, 174, 0, 168);
+ __lookup_fails(rt, 175, 0);
+ __insert(rt, 175, 0, 169);
+ __lookup_fails(rt, 176, 0);
+ __insert(rt, 176, 0, 170);
+ __lookup_fails(rt, 177, 0);
+ __insert(rt, 177, 0, 171);
+ __lookup_fails(rt, 178, 0);
+ __insert(rt, 178, 0, 172);
+ __lookup_fails(rt, 179, 0);
+ __insert(rt, 179, 0, 173);
+ __lookup_fails(rt, 180, 0);
+ __insert(rt, 180, 0, 174);
+ __lookup_fails(rt, 181, 0);
+ __insert(rt, 181, 0, 175);
+ __lookup_fails(rt, 182, 0);
+ __insert(rt, 182, 0, 176);
+ __lookup_fails(rt, 183, 0);
+ __insert(rt, 183, 0, 177);
+ __lookup_fails(rt, 184, 0);
+ __insert(rt, 184, 0, 178);
+ __lookup_fails(rt, 185, 0);
+ __insert(rt, 185, 0, 179);
+ __lookup_fails(rt, 186, 0);
+ __insert(rt, 186, 0, 180);
+ __lookup_fails(rt, 187, 0);
+ __insert(rt, 187, 0, 181);
+ __lookup_fails(rt, 188, 0);
+ __insert(rt, 188, 0, 182);
+ __lookup_fails(rt, 189, 0);
+ __insert(rt, 189, 0, 183);
+ __lookup_fails(rt, 190, 0);
+ __insert(rt, 190, 0, 184);
+ __lookup_fails(rt, 191, 0);
+ __insert(rt, 191, 0, 185);
+ __lookup_fails(rt, 192, 0);
+ __insert(rt, 192, 0, 186);
+ __lookup_fails(rt, 193, 0);
+ __insert(rt, 193, 0, 187);
+ __lookup_fails(rt, 194, 0);
+ __insert(rt, 194, 0, 188);
+ __lookup_fails(rt, 195, 0);
+ __insert(rt, 195, 0, 189);
+ __lookup_fails(rt, 196, 0);
+ __insert(rt, 196, 0, 190);
+ __lookup_fails(rt, 197, 0);
+ __insert(rt, 197, 0, 191);
+ __lookup_fails(rt, 198, 0);
+ __insert(rt, 198, 0, 192);
+ __lookup_fails(rt, 199, 0);
+ __insert(rt, 199, 0, 193);
+ __lookup_fails(rt, 200, 0);
+ __insert(rt, 200, 0, 194);
+ __lookup_fails(rt, 201, 0);
+ __insert(rt, 201, 0, 195);
+ __lookup_fails(rt, 202, 0);
+ __insert(rt, 202, 0, 196);
+ __lookup_fails(rt, 203, 0);
+ __insert(rt, 203, 0, 197);
+ __lookup_fails(rt, 204, 0);
+ __insert(rt, 204, 0, 198);
+ __lookup_fails(rt, 205, 0);
+ __insert(rt, 205, 0, 199);
+ __lookup_matches(rt, 6, 0, 0);
+ __invalidate(rt, 6);
+ __lookup_matches(rt, 7, 0, 1);
+ __invalidate(rt, 7);
+ __lookup_matches(rt, 8, 0, 2);
+ __invalidate(rt, 8);
+ __lookup_matches(rt, 9, 0, 3);
+ __invalidate(rt, 9);
+ __lookup_matches(rt, 10, 0, 4);
+ __invalidate(rt, 10);
+ __lookup_matches(rt, 11, 0, 5);
+ __invalidate(rt, 11);
+ __lookup_matches(rt, 12, 0, 6);
+ __lookup_matches(rt, 13, 0, 7);
+ __invalidate(rt, 13);
+ __lookup_matches(rt, 14, 0, 8);
+ __invalidate(rt, 14);
+ __lookup_matches(rt, 15, 0, 9);
+ __invalidate(rt, 15);
+ __lookup_matches(rt, 16, 0, 10);
+ __invalidate(rt, 16);
+ __lookup_matches(rt, 17, 0, 11);
+ __invalidate(rt, 17);
+ __lookup_matches(rt, 18, 0, 12);
+ __invalidate(rt, 18);
+ __lookup_matches(rt, 19, 0, 13);
+ __invalidate(rt, 19);
+ __lookup_matches(rt, 20, 0, 14);
+ __invalidate(rt, 20);
+ __lookup_matches(rt, 21, 0, 15);
+ __invalidate(rt, 21);
+ __lookup_matches(rt, 22, 0, 16);
+ __invalidate(rt, 22);
+ __lookup_matches(rt, 23, 0, 17);
+ __invalidate(rt, 23);
+ __lookup_matches(rt, 24, 0, 18);
+ __invalidate(rt, 24);
+ __lookup_matches(rt, 25, 0, 19);
+ __invalidate(rt, 25);
+ __lookup_matches(rt, 26, 0, 20);
+ __invalidate(rt, 26);
+ __lookup_matches(rt, 27, 0, 21);
+ __invalidate(rt, 27);
+ __lookup_matches(rt, 28, 0, 22);
+ __invalidate(rt, 28);
+ __lookup_matches(rt, 29, 0, 23);
+ __invalidate(rt, 29);
+ __lookup_matches(rt, 30, 0, 24);
+ __invalidate(rt, 30);
+ __lookup_matches(rt, 31, 0, 25);
+ __invalidate(rt, 31);
+ __lookup_matches(rt, 32, 0, 26);
+ __invalidate(rt, 32);
+ __lookup_matches(rt, 33, 0, 27);
+ __invalidate(rt, 33);
+ __lookup_matches(rt, 34, 0, 28);
+ __invalidate(rt, 34);
+ __lookup_matches(rt, 35, 0, 29);
+ __invalidate(rt, 35);
+ __lookup_matches(rt, 36, 0, 30);
+ __invalidate(rt, 36);
+ __lookup_matches(rt, 37, 0, 31);
+ __invalidate(rt, 37);
+ __lookup_matches(rt, 38, 0, 32);
+ __invalidate(rt, 38);
+ __lookup_matches(rt, 39, 0, 33);
+ __invalidate(rt, 39);
+ __lookup_matches(rt, 40, 0, 34);
+ __invalidate(rt, 40);
+ __lookup_matches(rt, 41, 0, 35);
+ __invalidate(rt, 41);
+ __lookup_matches(rt, 42, 0, 36);
+ __invalidate(rt, 42);
+ __lookup_matches(rt, 43, 0, 37);
+ __invalidate(rt, 43);
+ __lookup_matches(rt, 44, 0, 38);
+ __invalidate(rt, 44);
+ __lookup_matches(rt, 45, 0, 39);
+ __invalidate(rt, 45);
+ __lookup_matches(rt, 46, 0, 40);
+ __lookup_fails(rt, 46, 5);
+ __insert(rt, 46, 5, 200);
+ __lookup_matches(rt, 46, 5, 200);
+ __lookup_fails(rt, 46, 6);
+ __insert(rt, 46, 6, 201);
+ __lookup_fails(rt, 46, 7);
+ __insert(rt, 46, 7, 202);
+ __lookup_fails(rt, 46, 8);
+ __insert(rt, 46, 8, 203);
+ __lookup_matches(rt, 46, 5, 200);
+ __lookup_matches(rt, 46, 6, 201);
+ __lookup_matches(rt, 46, 7, 202);
+ __lookup_matches(rt, 46, 8, 203);
+ __lookup_matches(rt, 47, 0, 41);
+ __invalidate(rt, 47);
+ __lookup_matches(rt, 48, 0, 42);
+ __invalidate(rt, 48);
+ __lookup_matches(rt, 49, 0, 43);
+ __invalidate(rt, 49);
+ __lookup_matches(rt, 50, 0, 44);
+ __invalidate(rt, 50);
+ __lookup_matches(rt, 51, 0, 45);
+ __invalidate(rt, 51);
+ __lookup_matches(rt, 52, 0, 46);
+ __invalidate(rt, 52);
+ __lookup_matches(rt, 53, 0, 47);
+ __invalidate(rt, 53);
+ __lookup_matches(rt, 54, 0, 48);
+ __invalidate(rt, 54);
+ __lookup_matches(rt, 55, 0, 49);
+ __invalidate(rt, 55);
+ __lookup_matches(rt, 56, 0, 50);
+ __invalidate(rt, 56);
+ __lookup_matches(rt, 57, 0, 51);
+ __invalidate(rt, 57);
+ __lookup_matches(rt, 58, 0, 52);
+ __invalidate(rt, 58);
+ __lookup_matches(rt, 59, 0, 53);
+ __invalidate(rt, 59);
+ __lookup_matches(rt, 60, 0, 54);
+ __invalidate(rt, 60);
+ __lookup_matches(rt, 61, 0, 55);
+ __invalidate(rt, 61);
+ __lookup_matches(rt, 62, 0, 56);
+ __invalidate(rt, 62);
+ __lookup_matches(rt, 63, 0, 57);
+ __invalidate(rt, 63);
+ __lookup_matches(rt, 64, 0, 58);
+ __invalidate(rt, 64);
+ __lookup_matches(rt, 65, 0, 59);
+ __lookup_fails(rt, 65, 1);
+ __insert(rt, 65, 1, 204);
+ __lookup_fails(rt, 65, 2);
+ __insert(rt, 65, 2, 205);
+ __lookup_fails(rt, 65, 3);
+ __insert(rt, 65, 3, 206);
+ __lookup_fails(rt, 65, 4);
+ __insert(rt, 65, 4, 207);
+ __lookup_matches(rt, 65, 0, 59);
+ __lookup_matches(rt, 65, 1, 204);
+ __lookup_matches(rt, 65, 2, 205);
+ __lookup_matches(rt, 65, 3, 206);
+ __lookup_matches(rt, 65, 4, 207);
+ __lookup_matches(rt, 66, 0, 60);
+ __invalidate(rt, 66);
+ __lookup_matches(rt, 67, 0, 61);
+ __invalidate(rt, 67);
+ __lookup_matches(rt, 68, 0, 62);
+ __invalidate(rt, 68);
+ __lookup_matches(rt, 69, 0, 63);
+ __invalidate(rt, 69);
+ __lookup_matches(rt, 70, 0, 64);
+ __invalidate(rt, 70);
+ __lookup_matches(rt, 71, 0, 65);
+ __invalidate(rt, 71);
+ __lookup_matches(rt, 72, 0, 66);
+ __invalidate(rt, 72);
+ __lookup_matches(rt, 73, 0, 67);
+ __invalidate(rt, 73);
+ __lookup_matches(rt, 74, 0, 68);
+ __invalidate(rt, 74);
+ __lookup_matches(rt, 75, 0, 69);
+ __invalidate(rt, 75);
+ __lookup_matches(rt, 76, 0, 70);
+ __invalidate(rt, 76);
+ __lookup_matches(rt, 77, 0, 71);
+ __invalidate(rt, 77);
+ __lookup_matches(rt, 78, 0, 72);
+ __invalidate(rt, 78);
+ __lookup_matches(rt, 79, 0, 73);
+ __invalidate(rt, 79);
+ __lookup_matches(rt, 80, 0, 74);
+ __invalidate(rt, 80);
+ __lookup_matches(rt, 81, 0, 75);
+ __invalidate(rt, 81);
+ __lookup_matches(rt, 82, 0, 76);
+ __invalidate(rt, 82);
+ __lookup_matches(rt, 83, 0, 77);
+ __invalidate(rt, 83);
+ __lookup_matches(rt, 84, 0, 78);
+ __invalidate(rt, 84);
+ __lookup_matches(rt, 85, 0, 79);
+ __invalidate(rt, 85);
+ __lookup_matches(rt, 86, 0, 80);
+ __invalidate(rt, 86);
+ __lookup_matches(rt, 87, 0, 81);
+ __invalidate(rt, 87);
+ __lookup_matches(rt, 88, 0, 82);
+ __invalidate(rt, 88);
+ __lookup_matches(rt, 89, 0, 83);
+ __invalidate(rt, 89);
+ __lookup_matches(rt, 90, 0, 84);
+ __invalidate(rt, 90);
+ __lookup_matches(rt, 91, 0, 85);
+ __invalidate(rt, 91);
+ __lookup_matches(rt, 92, 0, 86);
+ __invalidate(rt, 92);
+ __lookup_matches(rt, 93, 0, 87);
+ __invalidate(rt, 93);
+ __lookup_matches(rt, 94, 0, 88);
+ __invalidate(rt, 94);
+ __lookup_matches(rt, 95, 0, 89);
+ __invalidate(rt, 95);
+ __lookup_matches(rt, 96, 0, 90);
+ __lookup_matches(rt, 97, 0, 91);
+ __invalidate(rt, 97);
+ __lookup_matches(rt, 98, 0, 92);
+ __invalidate(rt, 98);
+ __lookup_matches(rt, 99, 0, 93);
+ __invalidate(rt, 99);
+ __lookup_matches(rt, 100, 0, 94);
+ __invalidate(rt, 100);
+ __lookup_matches(rt, 101, 0, 95);
+ __invalidate(rt, 101);
+ __lookup_matches(rt, 102, 0, 96);
+ __invalidate(rt, 102);
+ __lookup_matches(rt, 103, 0, 97);
+ __invalidate(rt, 103);
+ __lookup_matches(rt, 104, 0, 98);
+ __invalidate(rt, 104);
+ __lookup_matches(rt, 105, 0, 99);
+ __invalidate(rt, 105);
+ __lookup_matches(rt, 106, 0, 100);
+ __invalidate(rt, 106);
+ __lookup_matches(rt, 107, 0, 101);
+ __invalidate(rt, 107);
+ __lookup_matches(rt, 108, 0, 102);
+ __invalidate(rt, 108);
+ __lookup_matches(rt, 109, 0, 103);
+ __invalidate(rt, 109);
+ __lookup_matches(rt, 110, 0, 104);
+ __invalidate(rt, 110);
+ __lookup_matches(rt, 111, 0, 105);
+ __invalidate(rt, 111);
+ __lookup_matches(rt, 112, 0, 106);
+ __invalidate(rt, 112);
+ __lookup_matches(rt, 113, 0, 107);
+ __invalidate(rt, 113);
+ __lookup_matches(rt, 114, 0, 108);
+ __invalidate(rt, 114);
+ __lookup_matches(rt, 115, 0, 109);
+ __invalidate(rt, 115);
+ __lookup_matches(rt, 116, 0, 110);
+ __invalidate(rt, 116);
+ __lookup_matches(rt, 117, 0, 111);
+ __invalidate(rt, 117);
+ __lookup_matches(rt, 118, 0, 112);
+ __invalidate(rt, 118);
+ __lookup_matches(rt, 119, 0, 113);
+ __invalidate(rt, 119);
+ __lookup_matches(rt, 120, 0, 114);
+ __invalidate(rt, 120);
+ __lookup_matches(rt, 121, 0, 115);
+ __invalidate(rt, 121);
+ __lookup_matches(rt, 122, 0, 116);
+ __invalidate(rt, 122);
+ __lookup_matches(rt, 123, 0, 117);
+ __invalidate(rt, 123);
+ __lookup_matches(rt, 124, 0, 118);
+ __invalidate(rt, 124);
+ __lookup_matches(rt, 125, 0, 119);
+ __invalidate(rt, 125);
+ __lookup_matches(rt, 126, 0, 120);
+ __invalidate(rt, 126);
+ __lookup_matches(rt, 127, 0, 121);
+ __invalidate(rt, 127);
+ __lookup_matches(rt, 128, 0, 122);
+ __invalidate(rt, 128);
+ __lookup_matches(rt, 129, 0, 123);
+ __invalidate(rt, 129);
+ __lookup_matches(rt, 130, 0, 124);
+ __invalidate(rt, 130);
+ __lookup_matches(rt, 131, 0, 125);
+ __invalidate(rt, 131);
+ __lookup_matches(rt, 132, 0, 126);
+ __invalidate(rt, 132);
+ __lookup_matches(rt, 133, 0, 127);
+ __invalidate(rt, 133);
+ __lookup_matches(rt, 134, 0, 128);
+ __invalidate(rt, 134);
+ __lookup_matches(rt, 135, 0, 129);
+ __invalidate(rt, 135);
+ __lookup_matches(rt, 136, 0, 130);
+ __invalidate(rt, 136);
+ __lookup_matches(rt, 137, 0, 131);
+ __invalidate(rt, 137);
+ __lookup_matches(rt, 138, 0, 132);
+ __invalidate(rt, 138);
+ __lookup_matches(rt, 139, 0, 133);
+ __invalidate(rt, 139);
+ __lookup_matches(rt, 140, 0, 134);
+ __invalidate(rt, 140);
+ __lookup_matches(rt, 141, 0, 135);
+ __invalidate(rt, 141);
+ __lookup_matches(rt, 142, 0, 136);
+ __invalidate(rt, 142);
+ __lookup_matches(rt, 143, 0, 137);
+ __invalidate(rt, 143);
+ __lookup_matches(rt, 144, 0, 138);
+ __invalidate(rt, 144);
+ __lookup_matches(rt, 145, 0, 139);
+ __invalidate(rt, 145);
+ __lookup_matches(rt, 146, 0, 140);
+ __invalidate(rt, 146);
+ __lookup_matches(rt, 147, 0, 141);
+ __invalidate(rt, 147);
+ __lookup_matches(rt, 148, 0, 142);
+ __invalidate(rt, 148);
+ __lookup_matches(rt, 149, 0, 143);
+ __invalidate(rt, 149);
+ __lookup_matches(rt, 150, 0, 144);
+ __invalidate(rt, 150);
+ __lookup_matches(rt, 151, 0, 145);
+ __invalidate(rt, 151);
+ __lookup_matches(rt, 152, 0, 146);
+ __invalidate(rt, 152);
+ __lookup_matches(rt, 153, 0, 147);
+ __invalidate(rt, 153);
+ __lookup_matches(rt, 154, 0, 148);
+ __invalidate(rt, 154);
+ __lookup_matches(rt, 155, 0, 149);
+ __invalidate(rt, 155);
+ __lookup_matches(rt, 156, 0, 150);
+ __invalidate(rt, 156);
+ __lookup_matches(rt, 157, 0, 151);
+ __invalidate(rt, 157);
+ __lookup_matches(rt, 158, 0, 152);
+ __invalidate(rt, 158);
+ __lookup_matches(rt, 159, 0, 153);
+ __invalidate(rt, 159);
+ __lookup_matches(rt, 160, 0, 154);
+ __invalidate(rt, 160);
+ __lookup_matches(rt, 161, 0, 155);
+ __invalidate(rt, 161);
+ __lookup_matches(rt, 162, 0, 156);
+ __invalidate(rt, 162);
+ __lookup_matches(rt, 163, 0, 157);
+ __lookup_matches(rt, 164, 0, 158);
+ __invalidate(rt, 164);
+ __lookup_matches(rt, 165, 0, 159);
+ __invalidate(rt, 165);
+ __lookup_matches(rt, 166, 0, 160);
+ __invalidate(rt, 166);
+ __lookup_matches(rt, 167, 0, 161);
+ __invalidate(rt, 167);
+ __lookup_matches(rt, 168, 0, 162);
+ __invalidate(rt, 168);
+ __lookup_matches(rt, 169, 0, 163);
+ __invalidate(rt, 169);
+ __lookup_matches(rt, 170, 0, 164);
+ __invalidate(rt, 170);
+ __lookup_matches(rt, 171, 0, 165);
+ __invalidate(rt, 171);
+ __lookup_matches(rt, 172, 0, 166);
+ __invalidate(rt, 172);
+ __lookup_matches(rt, 173, 0, 167);
+ __invalidate(rt, 173);
+ __lookup_matches(rt, 174, 0, 168);
+ __invalidate(rt, 174);
+ __lookup_matches(rt, 175, 0, 169);
+ __invalidate(rt, 175);
+ __lookup_matches(rt, 176, 0, 170);
+ __invalidate(rt, 176);
+ __lookup_matches(rt, 177, 0, 171);
+ __invalidate(rt, 177);
+ __lookup_matches(rt, 178, 0, 172);
+ __invalidate(rt, 178);
+ __lookup_matches(rt, 179, 0, 173);
+ __invalidate(rt, 179);
+ __lookup_matches(rt, 180, 0, 174);
+ __invalidate(rt, 180);
+ __lookup_matches(rt, 181, 0, 175);
+ __invalidate(rt, 181);
+ __lookup_matches(rt, 182, 0, 176);
+ __invalidate(rt, 182);
+ __lookup_matches(rt, 183, 0, 177);
+ __invalidate(rt, 183);
+ __lookup_matches(rt, 184, 0, 178);
+ __invalidate(rt, 184);
+ __lookup_matches(rt, 185, 0, 179);
+ __invalidate(rt, 185);
+ __lookup_matches(rt, 186, 0, 180);
+ __invalidate(rt, 186);
+ __lookup_matches(rt, 187, 0, 181);
+ __invalidate(rt, 187);
+ __lookup_matches(rt, 188, 0, 182);
+ __invalidate(rt, 188);
+ __lookup_matches(rt, 189, 0, 183);
+ __invalidate(rt, 189);
+ __lookup_matches(rt, 190, 0, 184);
+ __invalidate(rt, 190);
+ __lookup_matches(rt, 191, 0, 185);
+ __invalidate(rt, 191);
+ __lookup_matches(rt, 192, 0, 186);
+ __invalidate(rt, 192);
+ __lookup_matches(rt, 193, 0, 187);
+ __invalidate(rt, 193);
+ __lookup_matches(rt, 194, 0, 188);
+ __invalidate(rt, 194);
+ __lookup_matches(rt, 195, 0, 189);
+ __invalidate(rt, 195);
+ __lookup_matches(rt, 196, 0, 190);
+ __invalidate(rt, 196);
+ __lookup_matches(rt, 197, 0, 191);
+ __invalidate(rt, 197);
+ __lookup_matches(rt, 198, 0, 192);
+ __invalidate(rt, 198);
+ __lookup_matches(rt, 199, 0, 193);
+ __invalidate(rt, 199);
+ __lookup_matches(rt, 200, 0, 194);
+ __invalidate(rt, 200);
+ __lookup_matches(rt, 201, 0, 195);
+ __invalidate(rt, 201);
+ __lookup_matches(rt, 202, 0, 196);
+ __invalidate(rt, 202);
+ __lookup_matches(rt, 203, 0, 197);
+ __invalidate(rt, 203);
+ __lookup_matches(rt, 204, 0, 198);
+ __invalidate(rt, 204);
+ __lookup_matches(rt, 205, 0, 199);
+ __invalidate(rt, 205);
+ __lookup_fails(rt, 6, 0);
+ __insert(rt, 6, 0, 208);
+ __lookup_fails(rt, 7, 0);
+ __insert(rt, 7, 0, 209);
+ __lookup_fails(rt, 8, 0);
+ __insert(rt, 8, 0, 210);
+ __lookup_fails(rt, 9, 0);
+ __insert(rt, 9, 0, 211);
+ __lookup_fails(rt, 10, 0);
+ __insert(rt, 10, 0, 212);
+ __lookup_fails(rt, 11, 0);
+ __insert(rt, 11, 0, 213);
+ __lookup_fails(rt, 13, 0);
+ __insert(rt, 13, 0, 214);
+ __lookup_fails(rt, 14, 0);
+ __insert(rt, 14, 0, 215);
+ __lookup_fails(rt, 15, 0);
+ __insert(rt, 15, 0, 216);
+ __lookup_fails(rt, 16, 0);
+ __insert(rt, 16, 0, 217);
+ __lookup_fails(rt, 17, 0);
+ __insert(rt, 17, 0, 218);
+ __lookup_fails(rt, 18, 0);
+ __insert(rt, 18, 0, 219);
+ __lookup_fails(rt, 19, 0);
+ __insert(rt, 19, 0, 220);
+ __lookup_fails(rt, 20, 0);
+ __insert(rt, 20, 0, 221);
+ __lookup_fails(rt, 21, 0);
+ __insert(rt, 21, 0, 222);
+ __lookup_fails(rt, 22, 0);
+ __insert(rt, 22, 0, 223);
+ __lookup_fails(rt, 23, 0);
+ __insert(rt, 23, 0, 224);
+ __lookup_fails(rt, 24, 0);
+ __insert(rt, 24, 0, 225);
+ __lookup_fails(rt, 25, 0);
+ __insert(rt, 25, 0, 226);
+ __lookup_fails(rt, 26, 0);
+ __insert(rt, 26, 0, 227);
+ __lookup_fails(rt, 27, 0);
+ __insert(rt, 27, 0, 228);
+ __lookup_fails(rt, 28, 0);
+ __insert(rt, 28, 0, 229);
+ __lookup_fails(rt, 29, 0);
+ __insert(rt, 29, 0, 230);
+ __lookup_fails(rt, 30, 0);
+ __insert(rt, 30, 0, 231);
+ __lookup_fails(rt, 31, 0);
+ __insert(rt, 31, 0, 232);
+ __lookup_fails(rt, 32, 0);
+ __insert(rt, 32, 0, 233);
+ __lookup_fails(rt, 33, 0);
+ __insert(rt, 33, 0, 234);
+ __lookup_fails(rt, 34, 0);
+ __insert(rt, 34, 0, 235);
+ __lookup_fails(rt, 35, 0);
+ __insert(rt, 35, 0, 236);
+ __lookup_fails(rt, 36, 0);
+ __insert(rt, 36, 0, 237);
+ __lookup_fails(rt, 37, 0);
+ __insert(rt, 37, 0, 238);
+ __lookup_fails(rt, 38, 0);
+ __insert(rt, 38, 0, 239);
+ __lookup_fails(rt, 39, 0);
+ __insert(rt, 39, 0, 240);
+ __lookup_fails(rt, 40, 0);
+ __insert(rt, 40, 0, 241);
+ __lookup_fails(rt, 41, 0);
+ __insert(rt, 41, 0, 242);
+ __lookup_fails(rt, 42, 0);
+ __insert(rt, 42, 0, 243);
+ __lookup_fails(rt, 43, 0);
+ __insert(rt, 43, 0, 244);
+ __lookup_fails(rt, 44, 0);
+ __insert(rt, 44, 0, 245);
+ __lookup_fails(rt, 45, 0);
+ __insert(rt, 45, 0, 246);
+ __lookup_fails(rt, 47, 0);
+ __insert(rt, 47, 0, 247);
+ __lookup_fails(rt, 48, 0);
+ __insert(rt, 48, 0, 248);
+ __lookup_fails(rt, 49, 0);
+ __insert(rt, 49, 0, 249);
+ __lookup_fails(rt, 50, 0);
+ __insert(rt, 50, 0, 250);
+ __lookup_fails(rt, 51, 0);
+ __insert(rt, 51, 0, 251);
+ __lookup_fails(rt, 52, 0);
+ __insert(rt, 52, 0, 252);
+ __lookup_fails(rt, 53, 0);
+ __insert(rt, 53, 0, 253);
+ __lookup_fails(rt, 54, 0);
+ __insert(rt, 54, 0, 254);
+ __lookup_fails(rt, 55, 0);
+ __insert(rt, 55, 0, 255);
+ __lookup_fails(rt, 56, 0);
+ __insert(rt, 56, 0, 256);
+ __lookup_fails(rt, 57, 0);
+ __insert(rt, 57, 0, 257);
+ __lookup_fails(rt, 58, 0);
+ __insert(rt, 58, 0, 258);
+ __lookup_fails(rt, 59, 0);
+ __insert(rt, 59, 0, 259);
+ __lookup_fails(rt, 60, 0);
+ __insert(rt, 60, 0, 260);
+ __lookup_fails(rt, 61, 0);
+ __insert(rt, 61, 0, 261);
+ __lookup_fails(rt, 62, 0);
+ __insert(rt, 62, 0, 262);
+ __lookup_fails(rt, 63, 0);
+ __insert(rt, 63, 0, 263);
+ __lookup_fails(rt, 64, 0);
+ __insert(rt, 64, 0, 264);
+ __lookup_fails(rt, 66, 0);
+ __insert(rt, 66, 0, 265);
+ __lookup_fails(rt, 67, 0);
+ __insert(rt, 67, 0, 266);
+ __lookup_fails(rt, 68, 0);
+ __insert(rt, 68, 0, 267);
+ __lookup_fails(rt, 69, 0);
+ __insert(rt, 69, 0, 268);
+ __lookup_fails(rt, 70, 0);
+ __insert(rt, 70, 0, 269);
+ __lookup_fails(rt, 71, 0);
+ __insert(rt, 71, 0, 270);
+ __lookup_fails(rt, 72, 0);
+ __insert(rt, 72, 0, 271);
+ __lookup_fails(rt, 73, 0);
+ __insert(rt, 73, 0, 272);
+ __lookup_fails(rt, 74, 0);
+ __insert(rt, 74, 0, 273);
+ __lookup_fails(rt, 75, 0);
+ __insert(rt, 75, 0, 274);
+ __lookup_fails(rt, 76, 0);
+ __insert(rt, 76, 0, 275);
+ __lookup_fails(rt, 77, 0);
+ __insert(rt, 77, 0, 276);
+ __lookup_fails(rt, 78, 0);
+ __insert(rt, 78, 0, 277);
+ __lookup_fails(rt, 79, 0);
+ __insert(rt, 79, 0, 278);
+ __lookup_fails(rt, 80, 0);
+ __insert(rt, 80, 0, 279);
+ __lookup_fails(rt, 81, 0);
+ __insert(rt, 81, 0, 280);
+ __lookup_fails(rt, 82, 0);
+ __insert(rt, 82, 0, 281);
+ __lookup_fails(rt, 83, 0);
+ __insert(rt, 83, 0, 282);
+ __lookup_fails(rt, 84, 0);
+ __insert(rt, 84, 0, 283);
+ __lookup_fails(rt, 85, 0);
+ __insert(rt, 85, 0, 284);
+ __lookup_fails(rt, 86, 0);
+ __insert(rt, 86, 0, 285);
+ __lookup_fails(rt, 87, 0);
+ __insert(rt, 87, 0, 286);
+ __lookup_fails(rt, 88, 0);
+ __insert(rt, 88, 0, 287);
+ __lookup_fails(rt, 89, 0);
+ __insert(rt, 89, 0, 288);
+ __lookup_fails(rt, 90, 0);
+ __insert(rt, 90, 0, 289);
+ __lookup_fails(rt, 91, 0);
+ __insert(rt, 91, 0, 290);
+ __lookup_fails(rt, 92, 0);
+ __insert(rt, 92, 0, 291);
+ __lookup_fails(rt, 93, 0);
+ __insert(rt, 93, 0, 292);
+ __lookup_fails(rt, 94, 0);
+ __insert(rt, 94, 0, 293);
+ __lookup_fails(rt, 95, 0);
+ __insert(rt, 95, 0, 294);
+ __lookup_fails(rt, 97, 0);
+ __insert(rt, 97, 0, 295);
+ __lookup_fails(rt, 98, 0);
+ __insert(rt, 98, 0, 296);
+ __lookup_fails(rt, 99, 0);
+ __insert(rt, 99, 0, 297);
+ __lookup_fails(rt, 100, 0);
+ __insert(rt, 100, 0, 298);
+ __lookup_fails(rt, 101, 0);
+ __insert(rt, 101, 0, 299);
+ __lookup_fails(rt, 102, 0);
+ __insert(rt, 102, 0, 300);
+ __lookup_fails(rt, 103, 0);
+ __insert(rt, 103, 0, 301);
+ __lookup_fails(rt, 104, 0);
+ __insert(rt, 104, 0, 302);
+ __lookup_fails(rt, 105, 0);
+ __insert(rt, 105, 0, 303);
+ __lookup_fails(rt, 106, 0);
+ __insert(rt, 106, 0, 304);
+ __lookup_fails(rt, 107, 0);
+ __insert(rt, 107, 0, 305);
+ __lookup_fails(rt, 108, 0);
+ __insert(rt, 108, 0, 306);
+ __lookup_fails(rt, 109, 0);
+ __insert(rt, 109, 0, 307);
+ __lookup_fails(rt, 110, 0);
+ __insert(rt, 110, 0, 308);
+ __lookup_fails(rt, 111, 0);
+ __insert(rt, 111, 0, 309);
+ __lookup_fails(rt, 112, 0);
+ __insert(rt, 112, 0, 310);
+ __lookup_fails(rt, 113, 0);
+ __insert(rt, 113, 0, 311);
+ __lookup_fails(rt, 114, 0);
+ __insert(rt, 114, 0, 312);
+ __lookup_fails(rt, 115, 0);
+ __insert(rt, 115, 0, 313);
+ __lookup_fails(rt, 116, 0);
+ __insert(rt, 116, 0, 314);
+ __lookup_fails(rt, 117, 0);
+ __insert(rt, 117, 0, 315);
+ __lookup_fails(rt, 118, 0);
+ __insert(rt, 118, 0, 316);
+ __lookup_fails(rt, 119, 0);
+ __insert(rt, 119, 0, 317);
+ __lookup_fails(rt, 120, 0);
+ __insert(rt, 120, 0, 318);
+ __lookup_fails(rt, 121, 0);
+ __insert(rt, 121, 0, 319);
+ __lookup_fails(rt, 122, 0);
+ __insert(rt, 122, 0, 320);
+ __lookup_fails(rt, 123, 0);
+ __insert(rt, 123, 0, 321);
+ __lookup_fails(rt, 124, 0);
+ __insert(rt, 124, 0, 322);
+ __lookup_fails(rt, 125, 0);
+ __insert(rt, 125, 0, 323);
+ __lookup_fails(rt, 126, 0);
+ __insert(rt, 126, 0, 324);
+ __lookup_fails(rt, 127, 0);
+ __insert(rt, 127, 0, 325);
+ __lookup_fails(rt, 128, 0);
+ __insert(rt, 128, 0, 326);
+ __lookup_fails(rt, 129, 0);
+ __insert(rt, 129, 0, 327);
+ __lookup_fails(rt, 130, 0);
+ __insert(rt, 130, 0, 328);
+ __lookup_fails(rt, 131, 0);
+ __insert(rt, 131, 0, 329);
+ __lookup_fails(rt, 132, 0);
+ __insert(rt, 132, 0, 330);
+ __lookup_fails(rt, 133, 0);
+ __insert(rt, 133, 0, 331);
+ __lookup_fails(rt, 134, 0);
+ __insert(rt, 134, 0, 332);
+ __lookup_fails(rt, 135, 0);
+ __insert(rt, 135, 0, 333);
+ __lookup_fails(rt, 136, 0);
+ __insert(rt, 136, 0, 334);
+ __lookup_fails(rt, 137, 0);
+ __insert(rt, 137, 0, 335);
+ __lookup_fails(rt, 138, 0);
+ __insert(rt, 138, 0, 336);
+ __lookup_fails(rt, 139, 0);
+ __insert(rt, 139, 0, 337);
+ __lookup_fails(rt, 140, 0);
+ __insert(rt, 140, 0, 338);
+ __lookup_fails(rt, 141, 0);
+ __insert(rt, 141, 0, 339);
+ __lookup_fails(rt, 142, 0);
+ __insert(rt, 142, 0, 340);
+ __lookup_fails(rt, 143, 0);
+ __insert(rt, 143, 0, 341);
+ __lookup_fails(rt, 144, 0);
+ __insert(rt, 144, 0, 342);
+ __lookup_fails(rt, 145, 0);
+ __insert(rt, 145, 0, 343);
+ __lookup_fails(rt, 146, 0);
+ __insert(rt, 146, 0, 344);
+ __lookup_fails(rt, 147, 0);
+ __insert(rt, 147, 0, 345);
+ __lookup_fails(rt, 148, 0);
+ __insert(rt, 148, 0, 346);
+ __lookup_fails(rt, 149, 0);
+ __insert(rt, 149, 0, 347);
+ __lookup_fails(rt, 150, 0);
+ __insert(rt, 150, 0, 348);
+ __lookup_fails(rt, 151, 0);
+ __insert(rt, 151, 0, 349);
+ __lookup_fails(rt, 152, 0);
+ __insert(rt, 152, 0, 350);
+ __lookup_fails(rt, 153, 0);
+ __insert(rt, 153, 0, 351);
+ __lookup_fails(rt, 154, 0);
+ __insert(rt, 154, 0, 352);
+ __lookup_fails(rt, 155, 0);
+ __insert(rt, 155, 0, 353);
+ __lookup_fails(rt, 156, 0);
+ __insert(rt, 156, 0, 354);
+ __lookup_fails(rt, 157, 0);
+ __insert(rt, 157, 0, 355);
+ __lookup_fails(rt, 158, 0);
+ __insert(rt, 158, 0, 356);
+ __lookup_fails(rt, 159, 0);
+ __insert(rt, 159, 0, 357);
+ __lookup_fails(rt, 160, 0);
+ __insert(rt, 160, 0, 358);
+ __lookup_fails(rt, 161, 0);
+ __insert(rt, 161, 0, 359);
+ __lookup_fails(rt, 162, 0);
+ __insert(rt, 162, 0, 360);
+ __lookup_fails(rt, 164, 0);
+ __insert(rt, 164, 0, 361);
+ __lookup_fails(rt, 165, 0);
+ __insert(rt, 165, 0, 362);
+ __lookup_fails(rt, 166, 0);
+ __insert(rt, 166, 0, 363);
+ __lookup_fails(rt, 167, 0);
+ __insert(rt, 167, 0, 364);
+ __lookup_fails(rt, 168, 0);
+ __insert(rt, 168, 0, 365);
+ __lookup_fails(rt, 169, 0);
+ __insert(rt, 169, 0, 366);
+ __lookup_fails(rt, 170, 0);
+ __insert(rt, 170, 0, 367);
+ __lookup_fails(rt, 171, 0);
+ __insert(rt, 171, 0, 368);
+ __lookup_fails(rt, 172, 0);
+ __insert(rt, 172, 0, 369);
+ __lookup_fails(rt, 173, 0);
+ __insert(rt, 173, 0, 370);
+ __lookup_fails(rt, 174, 0);
+ __insert(rt, 174, 0, 371);
+ __lookup_fails(rt, 175, 0);
+ __insert(rt, 175, 0, 372);
+ __lookup_fails(rt, 176, 0);
+ __insert(rt, 176, 0, 373);
+ __lookup_fails(rt, 177, 0);
+ __insert(rt, 177, 0, 374);
+ __lookup_fails(rt, 178, 0);
+ __insert(rt, 178, 0, 375);
+ __lookup_fails(rt, 179, 0);
+ __insert(rt, 179, 0, 376);
+ __lookup_fails(rt, 180, 0);
+ __insert(rt, 180, 0, 377);
+ __lookup_fails(rt, 181, 0);
+ __insert(rt, 181, 0, 378);
+ __lookup_fails(rt, 182, 0);
+ __insert(rt, 182, 0, 379);
+ __lookup_fails(rt, 183, 0);
+ __insert(rt, 183, 0, 380);
+ __lookup_fails(rt, 184, 0);
+ __insert(rt, 184, 0, 381);
+ __lookup_fails(rt, 185, 0);
+ __insert(rt, 185, 0, 382);
+ __lookup_fails(rt, 186, 0);
+ __insert(rt, 186, 0, 383);
+ __lookup_fails(rt, 187, 0);
+ __insert(rt, 187, 0, 384);
+ __lookup_fails(rt, 188, 0);
+ __insert(rt, 188, 0, 385);
+ __lookup_fails(rt, 189, 0);
+ __insert(rt, 189, 0, 386);
+ __lookup_fails(rt, 190, 0);
+ __insert(rt, 190, 0, 387);
+ __lookup_fails(rt, 191, 0);
+ __insert(rt, 191, 0, 388);
+ __lookup_fails(rt, 192, 0);
+ __insert(rt, 192, 0, 389);
+ __lookup_fails(rt, 193, 0);
+ __insert(rt, 193, 0, 390);
+ __lookup_fails(rt, 194, 0);
+ __insert(rt, 194, 0, 391);
+ __lookup_fails(rt, 195, 0);
+ __insert(rt, 195, 0, 392);
+ __lookup_fails(rt, 196, 0);
+ __insert(rt, 196, 0, 393);
+ __lookup_fails(rt, 197, 0);
+ __insert(rt, 197, 0, 394);
+ __lookup_fails(rt, 198, 0);
+ __insert(rt, 198, 0, 395);
+ __lookup_fails(rt, 199, 0);
+ __insert(rt, 199, 0, 396);
+ __lookup_fails(rt, 200, 0);
+ __insert(rt, 200, 0, 397);
+ __lookup_fails(rt, 201, 0);
+ __insert(rt, 201, 0, 398);
+ __lookup_fails(rt, 202, 0);
+ __insert(rt, 202, 0, 399);
+ __lookup_fails(rt, 203, 0);
+ __insert(rt, 203, 0, 400);
+ __lookup_fails(rt, 204, 0);
+ __insert(rt, 204, 0, 401);
+ __lookup_fails(rt, 205, 0);
+ __insert(rt, 205, 0, 402);
+ __lookup_fails(rt, 206, 0);
+ __insert(rt, 206, 0, 403);
+ __lookup_fails(rt, 207, 0);
+ __insert(rt, 207, 0, 404);
+ __lookup_fails(rt, 208, 0);
+ __insert(rt, 208, 0, 405);
+ __lookup_fails(rt, 209, 0);
+ __insert(rt, 209, 0, 406);
+ __lookup_fails(rt, 210, 0);
+ __insert(rt, 210, 0, 407);
+ __lookup_matches(rt, 6, 0, 208);
+ __invalidate(rt, 6);
+ __lookup_matches(rt, 7, 0, 209);
+ __invalidate(rt, 7);
+ __lookup_matches(rt, 8, 0, 210);
+ __invalidate(rt, 8);
+ __lookup_matches(rt, 9, 0, 211);
+ __invalidate(rt, 9);
+ __lookup_matches(rt, 10, 0, 212);
+ __invalidate(rt, 10);
+ __lookup_matches(rt, 11, 0, 213);
+ __invalidate(rt, 11);
+ __lookup_matches(rt, 13, 0, 214);
+ __invalidate(rt, 13);
+ __lookup_matches(rt, 14, 0, 215);
+ __invalidate(rt, 14);
+ __lookup_matches(rt, 15, 0, 216);
+ __invalidate(rt, 15);
+ __lookup_matches(rt, 16, 0, 217);
+ __invalidate(rt, 16);
+ __lookup_matches(rt, 17, 0, 218);
+ __invalidate(rt, 17);
+ __lookup_matches(rt, 18, 0, 219);
+ __invalidate(rt, 18);
+ __lookup_matches(rt, 19, 0, 220);
+ __invalidate(rt, 19);
+ __lookup_matches(rt, 20, 0, 221);
+ __invalidate(rt, 20);
+ __lookup_matches(rt, 21, 0, 222);
+ __invalidate(rt, 21);
+ __lookup_matches(rt, 22, 0, 223);
+ __invalidate(rt, 22);
+ __lookup_matches(rt, 23, 0, 224);
+ __invalidate(rt, 23);
+ __lookup_matches(rt, 24, 0, 225);
+ __invalidate(rt, 24);
+ __lookup_matches(rt, 25, 0, 226);
+ __invalidate(rt, 25);
+ __lookup_matches(rt, 26, 0, 227);
+ __invalidate(rt, 26);
+ __lookup_matches(rt, 27, 0, 228);
+ __invalidate(rt, 27);
+ __lookup_matches(rt, 28, 0, 229);
+ __invalidate(rt, 28);
+ __lookup_matches(rt, 29, 0, 230);
+ __invalidate(rt, 29);
+ __lookup_matches(rt, 30, 0, 231);
+ __invalidate(rt, 30);
+ __lookup_matches(rt, 31, 0, 232);
+ __invalidate(rt, 31);
+ __lookup_matches(rt, 32, 0, 233);
+ __invalidate(rt, 32);
+ __lookup_matches(rt, 33, 0, 234);
+ __invalidate(rt, 33);
+ __lookup_matches(rt, 34, 0, 235);
+ __invalidate(rt, 34);
+ __lookup_matches(rt, 35, 0, 236);
+ __invalidate(rt, 35);
+ __lookup_matches(rt, 36, 0, 237);
+ __invalidate(rt, 36);
+ __lookup_matches(rt, 37, 0, 238);
+ __invalidate(rt, 37);
+ __lookup_matches(rt, 38, 0, 239);
+ __invalidate(rt, 38);
+ __lookup_matches(rt, 39, 0, 240);
+ __invalidate(rt, 39);
+ __lookup_matches(rt, 40, 0, 241);
+ __invalidate(rt, 40);
+ __lookup_matches(rt, 41, 0, 242);
+ __invalidate(rt, 41);
+ __lookup_matches(rt, 42, 0, 243);
+ __invalidate(rt, 42);
+ __lookup_matches(rt, 43, 0, 244);
+ __invalidate(rt, 43);
+ __lookup_matches(rt, 44, 0, 245);
+ __invalidate(rt, 44);
+ __lookup_matches(rt, 45, 0, 246);
+ __invalidate(rt, 45);
+ __lookup_matches(rt, 47, 0, 247);
+ __invalidate(rt, 47);
+ __lookup_matches(rt, 48, 0, 248);
+ __invalidate(rt, 48);
+ __lookup_matches(rt, 49, 0, 249);
+ __invalidate(rt, 49);
+ __lookup_matches(rt, 50, 0, 250);
+ __invalidate(rt, 50);
+ __lookup_matches(rt, 51, 0, 251);
+ __invalidate(rt, 51);
+ __lookup_matches(rt, 52, 0, 252);
+ __invalidate(rt, 52);
+ __lookup_matches(rt, 53, 0, 253);
+ __invalidate(rt, 53);
+ __lookup_matches(rt, 54, 0, 254);
+ __invalidate(rt, 54);
+ __lookup_matches(rt, 55, 0, 255);
+ __invalidate(rt, 55);
+ __lookup_matches(rt, 56, 0, 256);
+ __invalidate(rt, 56);
+ __lookup_matches(rt, 57, 0, 257);
+ __invalidate(rt, 57);
+ __lookup_matches(rt, 58, 0, 258);
+ __invalidate(rt, 58);
+ __lookup_matches(rt, 59, 0, 259);
+ __invalidate(rt, 59);
+ __lookup_matches(rt, 60, 0, 260);
+ __invalidate(rt, 60);
+ __lookup_matches(rt, 61, 0, 261);
+ __invalidate(rt, 61);
+ __lookup_matches(rt, 62, 0, 262);
+ __invalidate(rt, 62);
+ __lookup_matches(rt, 63, 0, 263);
+ __invalidate(rt, 63);
+ __lookup_matches(rt, 64, 0, 264);
+ __invalidate(rt, 64);
+ __lookup_matches(rt, 66, 0, 265);
+ __invalidate(rt, 66);
+ __lookup_matches(rt, 67, 0, 266);
+ __invalidate(rt, 67);
+ __lookup_matches(rt, 68, 0, 267);
+ __invalidate(rt, 68);
+ __lookup_matches(rt, 69, 0, 268);
+ __invalidate(rt, 69);
+ __lookup_matches(rt, 70, 0, 269);
+ __invalidate(rt, 70);
+ __lookup_matches(rt, 71, 0, 270);
+ __invalidate(rt, 71);
+ __lookup_matches(rt, 72, 0, 271);
+ __invalidate(rt, 72);
+ __lookup_matches(rt, 73, 0, 272);
+ __lookup_matches(rt, 74, 0, 273);
+ __invalidate(rt, 74);
+ __lookup_matches(rt, 75, 0, 274);
+ __invalidate(rt, 75);
+ __lookup_matches(rt, 76, 0, 275);
+ __invalidate(rt, 76);
+ __lookup_matches(rt, 77, 0, 276);
+ __invalidate(rt, 77);
+ __lookup_matches(rt, 78, 0, 277);
+ __invalidate(rt, 78);
+ __lookup_matches(rt, 79, 0, 278);
+ __invalidate(rt, 79);
+ __lookup_matches(rt, 80, 0, 279);
+ __invalidate(rt, 80);
+ __lookup_matches(rt, 81, 0, 280);
+ __invalidate(rt, 81);
+ __lookup_matches(rt, 82, 0, 281);
+ __invalidate(rt, 82);
+ __lookup_matches(rt, 83, 0, 282);
+ __invalidate(rt, 83);
+ __lookup_matches(rt, 84, 0, 283);
+ __invalidate(rt, 84);
+ __lookup_matches(rt, 85, 0, 284);
+ __invalidate(rt, 85);
+ __lookup_matches(rt, 86, 0, 285);
+ __invalidate(rt, 86);
+ __lookup_matches(rt, 87, 0, 286);
+ __invalidate(rt, 87);
+ __lookup_matches(rt, 88, 0, 287);
+ __invalidate(rt, 88);
+ __lookup_matches(rt, 89, 0, 288);
+ __invalidate(rt, 89);
+ __lookup_matches(rt, 90, 0, 289);
+ __invalidate(rt, 90);
+ __lookup_matches(rt, 91, 0, 290);
+ __invalidate(rt, 91);
+ __lookup_matches(rt, 92, 0, 291);
+ __invalidate(rt, 92);
+ __lookup_matches(rt, 93, 0, 292);
+ __invalidate(rt, 93);
+ __lookup_matches(rt, 94, 0, 293);
+ __invalidate(rt, 94);
+ __lookup_matches(rt, 95, 0, 294);
+ __invalidate(rt, 95);
+ __lookup_matches(rt, 97, 0, 295);
+ __invalidate(rt, 97);
+ __lookup_matches(rt, 98, 0, 296);
+ __invalidate(rt, 98);
+ __lookup_matches(rt, 99, 0, 297);
+ __invalidate(rt, 99);
+ __lookup_matches(rt, 100, 0, 298);
+ __invalidate(rt, 100);
+ __lookup_matches(rt, 101, 0, 299);
+ __invalidate(rt, 101);
+ __lookup_matches(rt, 102, 0, 300);
+ __invalidate(rt, 102);
+ __lookup_matches(rt, 103, 0, 301);
+ __invalidate(rt, 103);
+ __lookup_matches(rt, 104, 0, 302);
+ __invalidate(rt, 104);
+ __lookup_matches(rt, 105, 0, 303);
+ __invalidate(rt, 105);
+ __lookup_matches(rt, 106, 0, 304);
+ __invalidate(rt, 106);
+ __lookup_matches(rt, 107, 0, 305);
+ __invalidate(rt, 107);
+ __lookup_matches(rt, 108, 0, 306);
+ __invalidate(rt, 108);
+ __lookup_matches(rt, 109, 0, 307);
+ __invalidate(rt, 109);
+ __lookup_matches(rt, 110, 0, 308);
+ __invalidate(rt, 110);
+ __lookup_matches(rt, 111, 0, 309);
+ __invalidate(rt, 111);
+ __lookup_matches(rt, 112, 0, 310);
+ __invalidate(rt, 112);
+ __lookup_matches(rt, 113, 0, 311);
+ __invalidate(rt, 113);
+ __lookup_matches(rt, 114, 0, 312);
+ __invalidate(rt, 114);
+ __lookup_matches(rt, 115, 0, 313);
+ __invalidate(rt, 115);
+ __lookup_matches(rt, 116, 0, 314);
+ __invalidate(rt, 116);
+ __lookup_matches(rt, 117, 0, 315);
+ __invalidate(rt, 117);
+ __lookup_matches(rt, 118, 0, 316);
+ __invalidate(rt, 118);
+ __lookup_matches(rt, 119, 0, 317);
+ __invalidate(rt, 119);
+ __lookup_matches(rt, 120, 0, 318);
+ __invalidate(rt, 120);
+ __lookup_matches(rt, 121, 0, 319);
+ __invalidate(rt, 121);
+ __lookup_matches(rt, 122, 0, 320);
+ __invalidate(rt, 122);
+ __lookup_matches(rt, 123, 0, 321);
+ __invalidate(rt, 123);
+ __lookup_matches(rt, 124, 0, 322);
+ __invalidate(rt, 124);
+ __lookup_matches(rt, 125, 0, 323);
+ __invalidate(rt, 125);
+ __lookup_matches(rt, 126, 0, 324);
+ __invalidate(rt, 126);
+ __lookup_matches(rt, 127, 0, 325);
+ __invalidate(rt, 127);
+ __lookup_matches(rt, 128, 0, 326);
+ __invalidate(rt, 128);
+ __lookup_matches(rt, 129, 0, 327);
+ __invalidate(rt, 129);
+ __lookup_matches(rt, 130, 0, 328);
+ __invalidate(rt, 130);
+ __lookup_matches(rt, 131, 0, 329);
+ __invalidate(rt, 131);
+ __lookup_matches(rt, 132, 0, 330);
+ __invalidate(rt, 132);
+ __lookup_matches(rt, 133, 0, 331);
+ __invalidate(rt, 133);
+ __lookup_matches(rt, 134, 0, 332);
+ __invalidate(rt, 134);
+ __lookup_matches(rt, 135, 0, 333);
+ __invalidate(rt, 135);
+ __lookup_matches(rt, 136, 0, 334);
+ __invalidate(rt, 136);
+ __lookup_matches(rt, 137, 0, 335);
+ __invalidate(rt, 137);
+ __lookup_matches(rt, 138, 0, 336);
+ __invalidate(rt, 138);
+ __lookup_matches(rt, 139, 0, 337);
+ __invalidate(rt, 139);
+ __lookup_matches(rt, 140, 0, 338);
+ __invalidate(rt, 140);
+ __lookup_matches(rt, 141, 0, 339);
+ __invalidate(rt, 141);
+ __lookup_matches(rt, 142, 0, 340);
+ __invalidate(rt, 142);
+ __lookup_matches(rt, 143, 0, 341);
+ __invalidate(rt, 143);
+ __lookup_matches(rt, 144, 0, 342);
+ __invalidate(rt, 144);
+ __lookup_matches(rt, 145, 0, 343);
+ __invalidate(rt, 145);
+ __lookup_matches(rt, 146, 0, 344);
+ __invalidate(rt, 146);
+ __lookup_matches(rt, 147, 0, 345);
+ __invalidate(rt, 147);
+ __lookup_matches(rt, 148, 0, 346);
+ __invalidate(rt, 148);
+ __lookup_matches(rt, 149, 0, 347);
+ __invalidate(rt, 149);
+ __lookup_matches(rt, 150, 0, 348);
+ __invalidate(rt, 150);
+ __lookup_matches(rt, 151, 0, 349);
+ __invalidate(rt, 151);
+ __lookup_matches(rt, 152, 0, 350);
+ __invalidate(rt, 152);
+ __lookup_matches(rt, 153, 0, 351);
+ __invalidate(rt, 153);
+ __lookup_matches(rt, 154, 0, 352);
+ __invalidate(rt, 154);
+ __lookup_matches(rt, 155, 0, 353);
+ __invalidate(rt, 155);
+ __lookup_matches(rt, 156, 0, 354);
+ __invalidate(rt, 156);
+ __lookup_matches(rt, 157, 0, 355);
+ __invalidate(rt, 157);
+ __lookup_matches(rt, 158, 0, 356);
+ __invalidate(rt, 158);
+ __lookup_matches(rt, 159, 0, 357);
+ __invalidate(rt, 159);
+ __lookup_matches(rt, 160, 0, 358);
+ __invalidate(rt, 160);
+ __lookup_matches(rt, 161, 0, 359);
+ __invalidate(rt, 161);
+ __lookup_matches(rt, 162, 0, 360);
+ __invalidate(rt, 162);
+ __lookup_matches(rt, 164, 0, 361);
+ __invalidate(rt, 164);
+ __lookup_matches(rt, 165, 0, 362);
+ __invalidate(rt, 165);
+ __lookup_matches(rt, 166, 0, 363);
+ __invalidate(rt, 166);
+ __lookup_matches(rt, 167, 0, 364);
+ __invalidate(rt, 167);
+ __lookup_matches(rt, 168, 0, 365);
+ __invalidate(rt, 168);
+ __lookup_matches(rt, 169, 0, 366);
+ __invalidate(rt, 169);
+ __lookup_matches(rt, 170, 0, 367);
+ __invalidate(rt, 170);
+ __lookup_matches(rt, 171, 0, 368);
+ __invalidate(rt, 171);
+ __lookup_matches(rt, 172, 0, 369);
+ __invalidate(rt, 172);
+ __lookup_matches(rt, 173, 0, 370);
+ __invalidate(rt, 173);
+ __lookup_matches(rt, 174, 0, 371);
+ __invalidate(rt, 174);
+ __lookup_matches(rt, 175, 0, 372);
+ __invalidate(rt, 175);
+ __lookup_matches(rt, 176, 0, 373);
+ __invalidate(rt, 176);
+ __lookup_matches(rt, 177, 0, 374);
+ __invalidate(rt, 177);
+ __lookup_matches(rt, 178, 0, 375);
+ __invalidate(rt, 178);
+ __lookup_matches(rt, 179, 0, 376);
+ __invalidate(rt, 179);
+ __lookup_matches(rt, 180, 0, 377);
+ __invalidate(rt, 180);
+ __lookup_matches(rt, 181, 0, 378);
+ __invalidate(rt, 181);
+ __lookup_matches(rt, 182, 0, 379);
+ __invalidate(rt, 182);
+ __lookup_matches(rt, 183, 0, 380);
+ __invalidate(rt, 183);
+ __lookup_matches(rt, 184, 0, 381);
+ __invalidate(rt, 184);
+ __lookup_matches(rt, 185, 0, 382);
+ __invalidate(rt, 185);
+ __lookup_matches(rt, 186, 0, 383);
+ __invalidate(rt, 186);
+ __lookup_matches(rt, 187, 0, 384);
+ __invalidate(rt, 187);
+ __lookup_matches(rt, 188, 0, 385);
+ __invalidate(rt, 188);
+ __lookup_matches(rt, 189, 0, 386);
+ __invalidate(rt, 189);
+ __lookup_matches(rt, 190, 0, 387);
+ __invalidate(rt, 190);
+ __lookup_matches(rt, 191, 0, 388);
+ __invalidate(rt, 191);
+ __lookup_matches(rt, 192, 0, 389);
+ __invalidate(rt, 192);
+ __lookup_matches(rt, 193, 0, 390);
+ __invalidate(rt, 193);
+ __lookup_matches(rt, 194, 0, 391);
+ __invalidate(rt, 194);
+ __lookup_matches(rt, 195, 0, 392);
+ __invalidate(rt, 195);
+ __lookup_matches(rt, 196, 0, 393);
+ __invalidate(rt, 196);
+ __lookup_matches(rt, 197, 0, 394);
+ __invalidate(rt, 197);
+ __lookup_matches(rt, 198, 0, 395);
+ __invalidate(rt, 198);
+ __lookup_matches(rt, 199, 0, 396);
+ __invalidate(rt, 199);
+ __lookup_matches(rt, 200, 0, 397);
+ __invalidate(rt, 200);
+ __lookup_matches(rt, 201, 0, 398);
+ __invalidate(rt, 201);
+ __lookup_matches(rt, 202, 0, 399);
+ __invalidate(rt, 202);
+ __lookup_matches(rt, 203, 0, 400);
+ __invalidate(rt, 203);
+ __lookup_matches(rt, 204, 0, 401);
+ __invalidate(rt, 204);
+ __lookup_matches(rt, 205, 0, 402);
+ __invalidate(rt, 205);
+ __lookup_matches(rt, 206, 0, 403);
+ __invalidate(rt, 206);
+ __lookup_matches(rt, 207, 0, 404);
+ __invalidate(rt, 207);
+ __lookup_matches(rt, 208, 0, 405);
+ __invalidate(rt, 208);
+ __lookup_matches(rt, 209, 0, 406);
+ __invalidate(rt, 209);
+ __lookup_matches(rt, 210, 0, 407);
+ __invalidate(rt, 210);
+ __lookup_fails(rt, 6, 0);
+ __insert(rt, 6, 0, 408);
+ __lookup_fails(rt, 7, 0);
+ __insert(rt, 7, 0, 409);
+ __lookup_fails(rt, 8, 0);
+ __insert(rt, 8, 0, 410);
+ __lookup_fails(rt, 9, 0);
+ __insert(rt, 9, 0, 411);
+ __lookup_fails(rt, 10, 0);
+ __insert(rt, 10, 0, 412);
+ __lookup_fails(rt, 11, 0);
+ __insert(rt, 11, 0, 413);
+ __lookup_fails(rt, 13, 0);
+ __insert(rt, 13, 0, 414);
+ __lookup_fails(rt, 14, 0);
+ __insert(rt, 14, 0, 415);
+ __lookup_fails(rt, 15, 0);
+ __insert(rt, 15, 0, 416);
+ __lookup_fails(rt, 16, 0);
+ __insert(rt, 16, 0, 417);
+ __lookup_fails(rt, 17, 0);
+ __insert(rt, 17, 0, 418);
+ __lookup_fails(rt, 18, 0);
+ __insert(rt, 18, 0, 419);
+ __lookup_fails(rt, 19, 0);
+ __insert(rt, 19, 0, 420);
+ __lookup_fails(rt, 20, 0);
+ __insert(rt, 20, 0, 421);
+ __lookup_fails(rt, 21, 0);
+ __insert(rt, 21, 0, 422);
+ __lookup_fails(rt, 22, 0);
+ __insert(rt, 22, 0, 423);
+ __lookup_fails(rt, 23, 0);
+ __insert(rt, 23, 0, 424);
+ __lookup_matches(rt, 6, 0, 408);
+ __invalidate(rt, 6);
+ __lookup_matches(rt, 7, 0, 409);
+ __invalidate(rt, 7);
+ __lookup_matches(rt, 8, 0, 410);
+ __invalidate(rt, 8);
+ __lookup_matches(rt, 9, 0, 411);
+ __invalidate(rt, 9);
+ __lookup_matches(rt, 10, 0, 412);
+ __invalidate(rt, 10);
+ __lookup_matches(rt, 11, 0, 413);
+ __invalidate(rt, 11);
+ __lookup_matches(rt, 13, 0, 414);
+ __invalidate(rt, 13);
+ __lookup_matches(rt, 14, 0, 415);
diff --git a/test/unit/run.c b/test/unit/run.c
index 482498a..84b867b 100644
--- a/test/unit/run.c
+++ b/test/unit/run.c
@@ -1,29 +1,312 @@
-#include <CUnit/CUnit.h>
-#include <CUnit/Basic.h>
-
-#define DECL(n) \
- extern CU_TestInfo n ## _list[]; \
- int n ## _init(void); \
- int n ## _fini(void);
-#define USE(n) { (char*) #n, n##_init, n##_fini, n##_list }
-
-DECL(bitset);
-DECL(regex);
-DECL(config);
-DECL(string);
-
-CU_SuiteInfo suites[] = {
- USE(bitset),
- USE(regex),
- USE(config),
- USE(string),
- CU_SUITE_INFO_NULL
+#include "units.h"
+
+#include <getopt.h>
+#include <regex.h>
+#include <stdio.h>
+#include <stdlib.h>
+#include <setjmp.h>
+#include <unistd.h>
+
+//-----------------------------------------------------------------
+
+#define MAX_COMPONENTS 16
+
+struct token {
+ const char *b, *e;
};
-int main(int argc, char **argv) {
- CU_initialize_registry();
- CU_register_suites(suites);
- CU_basic_set_mode(CU_BRM_VERBOSE);
- CU_basic_run_tests();
- return CU_get_number_of_failures() != 0;
+static bool _pop_component(const char *path, struct token *result)
+{
+ const char *b, *e;
+
+ while (*path && *path == '/')
+ path++;
+
+ b = path;
+ while (*path && (*path != '/'))
+ path++;
+ e = path;
+
+ if (b == e)
+ return false;
+
+ result->b = b;
+ result->e = e;
+ return true;
+}
+
+static unsigned _split_components(const char *path, struct token *toks, unsigned len)
+{
+ unsigned count = 0;
+ struct token tok;
+ tok.e = path;
+
+ while (len && _pop_component(tok.e, &tok)) {
+ *toks = tok;
+ toks++;
+ count++;
+ len--;
+ }
+
+ return count;
+}
+
+static void _indent(FILE *stream, unsigned count)
+{
+ unsigned i;
+
+ for (i = 0; i < count; i++)
+ fprintf(stream, " ");
+}
+
+static void _print_token(FILE *stream, struct token *t)
+{
+ const char *ptr;
+
+ for (ptr = t->b; ptr != t->e; ptr++)
+ fprintf(stream, "%c", *ptr);
+}
+
+static int _char_cmp(char l, char r)
+{
+ if (l < r)
+ return -1;
+
+ else if (r < l)
+ return 1;
+
+ else
+ return 0;
+}
+
+static int _tok_cmp(struct token *lhs, struct token *rhs)
+{
+ const char *l = lhs->b, *le = lhs->e;
+ const char *r = rhs->b, *re = rhs->e;
+
+ while ((l != le) && (r != re) && (*l == *r)) {
+ l++;
+ r++;
+ }
+
+ if ((l != le) && (r != re))
+ return _char_cmp(*l, *r);
+
+ else if (r != re)
+ return -1;
+
+ else if (l != le)
+ return 1;
+
+ else
+ return 0;
+}
+
+static void _print_path_delta(FILE *stream,
+ struct token *old, unsigned old_len,
+ struct token *new, unsigned new_len,
+ const char *desc)
+{
+ unsigned i, common_prefix = 0, len, d;
+ unsigned max_prefix = old_len < new_len ? old_len : new_len;
+
+ for (i = 0; i < max_prefix; i++) {
+ if (_tok_cmp(old + i, new + i))
+ break;
+ else
+ common_prefix++;
+ }
+
+ for (; i < new_len; i++) {
+ _indent(stream, common_prefix);
+ _print_token(stream, new + i);
+ common_prefix++;
+ if (i < new_len - 1)
+ fprintf(stream, "\n");
+ }
+
+ len = (new_len > 0) ? common_prefix * 2 + (new[new_len - 1].e - new[new_len - 1].b) : 0;
+
+ fprintf(stream, " ");
+ for (d = len; d < 60; d++)
+ fprintf(stream, ".");
+ fprintf(stream, " ");
+ fprintf(stream, "%s", desc);
+ fprintf(stream, "\n");
+}
+
+typedef struct token comp_t[MAX_COMPONENTS];
+
+static void _list_tests(struct test_details **tests, unsigned nr)
+{
+ unsigned i, current = 0, current_len, last_len = 0;
+
+ comp_t components[2];
+
+ for (i = 0; i < nr; i++) {
+ struct test_details *t = tests[i];
+ current_len = _split_components(t->path, components[current], MAX_COMPONENTS);
+ _print_path_delta(stderr, components[!current], last_len,
+ components[current], current_len, t->desc);
+
+ last_len = current_len;
+ current = !current;
+ }
+}
+
+static void _destroy_tests(struct dm_list *suites)
+{
+ struct test_suite *ts, *tmp;
+
+ dm_list_iterate_items_safe (ts, tmp, suites)
+ test_suite_destroy(ts);
+}
+
+static const char *red(bool c)
+{
+ return c ? "\x1B[31m" : "";
+}
+
+static const char *green(bool c)
+{
+ return c ? "\x1B[32m" : "";
+}
+
+static const char *normal(bool c)
+{
+ return c ? "\x1B[0m" : "";
+}
+
+static void _run_test(struct test_details *t, bool use_colour, unsigned *passed, unsigned *total)
+{
+ void *fixture;
+ struct test_suite *ts = t->parent;
+ fprintf(stderr, "[RUN ] %s\n", t->path);
+
+ (*total)++;
+ if (setjmp(test_k))
+ fprintf(stderr, "%s[ FAIL]%s %s\n", red(use_colour), normal(use_colour), t->path);
+ else {
+ if (ts->fixture_init)
+ fixture = ts->fixture_init();
+ else
+ fixture = NULL;
+
+ t->fn(fixture);
+
+ if (ts->fixture_exit)
+ ts->fixture_exit(fixture);
+
+ (*passed)++;
+ fprintf(stderr, "%s[ OK]%s\n", green(use_colour), normal(use_colour));
+ /* coverity[leaked_storage] fixture released by fixture_exit */
+ }
}
+
+static bool _run_tests(struct test_details **tests, unsigned nr)
+{
+ bool use_colour = isatty(fileno(stderr));
+ unsigned i, passed = 0, total = 0;
+
+ for (i = 0; i < nr; i++)
+ _run_test(tests[i], use_colour, &passed, &total);
+
+ fprintf(stderr, "\n%u/%u tests passed\n", passed, total);
+
+ return passed == total;
+}
+
+static void _usage(void)
+{
+ fprintf(stderr, "Usage: unit-test <list|run> [pattern]\n");
+}
+
+static int _cmp_paths(const void *lhs, const void *rhs)
+{
+ struct test_details *l = *((struct test_details **) lhs);
+ struct test_details *r = *((struct test_details **) rhs);
+
+ return strcmp(l->path, r->path);
+}
+
+static unsigned _filter(const char *pattern, struct test_details **tests, unsigned nr)
+{
+ unsigned i, found = 0;
+ regex_t rx;
+
+ if (regcomp(&rx, pattern, 0)) {
+ fprintf(stderr, "couldn't compile regex '%s'\n", pattern);
+ exit(1);
+ }
+
+ for (i = 0; i < nr; i++)
+ if (tests[i] && !regexec(&rx, tests[i]->path, 0, NULL, 0))
+ tests[found++] = tests[i];
+
+ regfree(&rx);
+
+ return found;
+}
+
+int main(int argc, char **argv)
+{
+ int r;
+ unsigned i, nr_tests;
+ struct test_suite *ts;
+ struct test_details *t, **t_array;
+ struct dm_list suites;
+
+ dm_list_init(&suites);
+ register_all_tests(&suites);
+
+ // count all tests
+ nr_tests = 0;
+ dm_list_iterate_items (ts, &suites)
+ dm_list_iterate_items (t, &ts->tests)
+ nr_tests++;
+
+ // stick them in an array
+ t_array = malloc(sizeof(*t_array) * nr_tests);
+ if (!t_array) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+ memset(t_array, 0, sizeof(*t_array) * nr_tests);
+
+ i = 0;
+ dm_list_iterate_items (ts, &suites)
+ dm_list_iterate_items (t, &ts->tests)
+ t_array[i++] = t;
+
+ // filter
+ if (argc == 3)
+ nr_tests = _filter(argv[2], t_array, nr_tests);
+
+ // sort
+ qsort(t_array, nr_tests, sizeof(*t_array), _cmp_paths);
+
+ // run or list them
+ if (argc == 1)
+ r = !_run_tests(t_array, nr_tests);
+ else {
+ const char *cmd = argv[1];
+ if (!strcmp(cmd, "run"))
+ r = !_run_tests(t_array, nr_tests);
+
+ else if (!strcmp(cmd, "list")) {
+ _list_tests(t_array, nr_tests);
+ r = 0;
+
+ } else {
+ _usage();
+ r = 1;
+ }
+ }
+
+ free(t_array);
+ _destroy_tests(&suites);
+
+ return r;
+}
+
+//-----------------------------------------------------------------
diff --git a/test/unit/string_t.c b/test/unit/string_t.c
index df72505..82c6448 100644
--- a/test/unit/string_t.c
+++ b/test/unit/string_t.c
@@ -9,50 +9,48 @@
*
* You should have received a copy of the GNU General Public License
* along with this program; if not, write to the Free Software Foundation,
- * Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
*/
-#include "libdevmapper.h"
+#include "units.h"
+#include "device_mapper/all.h"
#include <stdio.h>
#include <string.h>
-#include <CUnit/CUnit.h>
-
-int string_init(void);
-int string_fini(void);
-
-static struct dm_pool *mem = NULL;
-
-int string_init(void)
+#if 0
+static int _mem_init(void)
{
- mem = dm_pool_create("string test", 1024);
+ struct dm_pool *mem = dm_pool_create("string test", 1024);
+ if (!mem) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
- return (mem == NULL);
+ return mem;
}
-int string_fini(void)
+static void _mem_exit(void *mem)
{
dm_pool_destroy(mem);
-
- return 0;
}
/* TODO: Add more string unit tests here */
+#endif
-static void test_strncpy(void)
+static void test_strncpy(void *fixture)
{
const char st[] = "1234567890";
char buf[sizeof(st)];
- CU_ASSERT_EQUAL(dm_strncpy(buf, st, sizeof(buf)), 1);
- CU_ASSERT_EQUAL(strcmp(buf, st), 0);
+ T_ASSERT_EQUAL(dm_strncpy(buf, st, sizeof(buf)), 1);
+ T_ASSERT_EQUAL(strcmp(buf, st), 0);
- CU_ASSERT_EQUAL(dm_strncpy(buf, st, sizeof(buf) - 1), 0);
- CU_ASSERT_EQUAL(strlen(buf) + 1, sizeof(buf) - 1);
+ T_ASSERT_EQUAL(dm_strncpy(buf, st, sizeof(buf) - 1), 0);
+ T_ASSERT_EQUAL(strlen(buf) + 1, sizeof(buf) - 1);
}
-static void test_asprint(void)
+static void test_asprint(void *fixture)
{
const char st0[] = "";
const char st1[] = "12345678901";
@@ -61,23 +59,33 @@ static void test_asprint(void)
int a;
a = dm_asprintf(&buf, "%s", st0);
- CU_ASSERT_EQUAL(strcmp(buf, st0), 0);
- CU_ASSERT_EQUAL(a, sizeof(st0));
+ T_ASSERT_EQUAL(strcmp(buf, st0), 0);
+ T_ASSERT_EQUAL(a, sizeof(st0));
free(buf);
a = dm_asprintf(&buf, "%s", st1);
- CU_ASSERT_EQUAL(strcmp(buf, st1), 0);
- CU_ASSERT_EQUAL(a, sizeof(st1));
+ T_ASSERT_EQUAL(strcmp(buf, st1), 0);
+ T_ASSERT_EQUAL(a, sizeof(st1));
free(buf);
a = dm_asprintf(&buf, "%s", st2);
- CU_ASSERT_EQUAL(a, sizeof(st2));
- CU_ASSERT_EQUAL(strcmp(buf, st2), 0);
+ T_ASSERT_EQUAL(a, sizeof(st2));
+ T_ASSERT_EQUAL(strcmp(buf, st2), 0);
free(buf);
}
-CU_TestInfo string_list[] = {
- { (char*)"asprint", test_asprint },
- { (char*)"strncpy", test_strncpy },
- CU_TEST_INFO_NULL
-};
+#define T(path, desc, fn) register_test(ts, "/base/data-struct/string/" path, desc, fn)
+
+void string_tests(struct dm_list *all_tests)
+{
+ struct test_suite *ts = test_suite_create(NULL, NULL);
+ if (!ts) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ }
+
+ T("asprint", "tests asprint", test_asprint);
+ T("strncpy", "tests string copying", test_strncpy);
+
+ dm_list_add(all_tests, &ts->list);
+}
diff --git a/test/unit/unit-test.sh b/test/unit/unit-test.sh
new file mode 100644
index 0000000..f545f14
--- /dev/null
+++ b/test/unit/unit-test.sh
@@ -0,0 +1,21 @@
+#!/bin/sh
+# Copyright (C) 2018 Red Hat, Inc. All rights reserved.
+#
+# This file is part of LVM2.
+#
+# This copyrighted material is made available to anyone wishing to use,
+# modify, copy, or redistribute it subject to the terms and conditions
+# of the GNU General Public License v.2.
+#
+# You should have received a copy of the GNU General Public License
+# along with this program; if not, write to the Free Software Foundation,
+# Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+
+SKIP_WITH_LVMLOCKD=1
+SKIP_WITH_LVMPOLLD=1
+
+SKIP_ROOT_DM_CHECK=1
+
+. lib/inittest
+
+aux unittest run
diff --git a/test/unit/units.h b/test/unit/units.h
new file mode 100644
index 0000000..d7ac6ad
--- /dev/null
+++ b/test/unit/units.h
@@ -0,0 +1,55 @@
+/*
+ * Copyright (C) 2018 Red Hat, Inc. All rights reserved.
+ *
+ * This file is part of LVM2.
+ *
+ * This copyrighted material is made available to anyone wishing to use,
+ * modify, copy, or redistribute it subject to the terms and conditions
+ * of the GNU General Public License v.2.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#ifndef TEST_UNIT_UNITS_H
+#define TEST_UNIT_UNITS_H
+
+#include "framework.h"
+
+//-----------------------------------------------------------------
+
+// Declare the function that adds tests suites here ...
+void bcache_tests(struct dm_list *suites);
+void bcache_utils_tests(struct dm_list *suites);
+void bitset_tests(struct dm_list *suites);
+void config_tests(struct dm_list *suites);
+void dm_list_tests(struct dm_list *suites);
+void dm_status_tests(struct dm_list *suites);
+void io_engine_tests(struct dm_list *suites);
+void percent_tests(struct dm_list *suites);
+void radix_tree_tests(struct dm_list *suites);
+void regex_tests(struct dm_list *suites);
+void string_tests(struct dm_list *suites);
+void vdo_tests(struct dm_list *suites);
+
+// ... and call it in here.
+static inline void register_all_tests(struct dm_list *suites)
+{
+ bcache_tests(suites);
+ bcache_utils_tests(suites);
+ bitset_tests(suites);
+ config_tests(suites);
+ dm_list_tests(suites);
+ dm_status_tests(suites);
+ io_engine_tests(suites);
+ percent_tests(suites);
+ radix_tree_tests(suites);
+ regex_tests(suites);
+ string_tests(suites);
+ vdo_tests(suites);
+}
+
+//-----------------------------------------------------------------
+
+#endif
diff --git a/test/unit/vdo_t.c b/test/unit/vdo_t.c
new file mode 100644
index 0000000..27ad26b
--- /dev/null
+++ b/test/unit/vdo_t.c
@@ -0,0 +1,325 @@
+/*
+ * Copyright (C) 2018 Red Hat, Inc. All rights reserved.
+ *
+ * This file is part of LVM2.
+ *
+ * This copyrighted material is made available to anyone wishing to use,
+ * modify, copy, or redistribute it subject to the terms and conditions
+ * of the GNU General Public License v.2.
+ *
+ * You should have received a copy of the GNU General Public License
+ * along with this program; if not, write to the Free Software Foundation,
+ * Inc., 51 Franklin Street, Fifth Floor, Boston, MA 02110-1301 USA
+ */
+
+#include "units.h"
+#include "device_mapper/vdo/target.h"
+
+//----------------------------------------------------------------
+
+static bool _status_eq(struct dm_vdo_status *lhs, struct dm_vdo_status *rhs)
+{
+ return !strcmp(lhs->device, rhs->device) &&
+ (lhs->operating_mode == rhs->operating_mode) &&
+ (lhs->recovering == rhs->recovering) &&
+ (lhs->index_state == rhs->index_state) &&
+ (lhs->compression_state == rhs->compression_state) &&
+ (lhs->used_blocks == rhs->used_blocks) &&
+ (lhs->total_blocks == rhs->total_blocks);
+}
+
+#if 0
+static const char *_op_mode(enum dm_vdo_operating_mode m)
+{
+ switch (m) {
+ case DM_VDO_MODE_RECOVERING:
+ return "recovering";
+ case DM_VDO_MODE_READ_ONLY:
+ return "read-only";
+ case DM_VDO_MODE_NORMAL:
+ return "normal";
+ }
+
+ return "<unknown>";
+}
+
+static const char *_index_state(enum dm_vdo_index_state is)
+{
+ switch (is) {
+ case DM_VDO_INDEX_ERROR:
+ return "error";
+ case DM_VDO_INDEX_CLOSED:
+ return "closed";
+ case DM_VDO_INDEX_OPENING:
+ return "opening";
+ case DM_VDO_INDEX_CLOSING:
+ return "closing";
+ case DM_VDO_INDEX_OFFLINE:
+ return "offline";
+ case DM_VDO_INDEX_ONLINE:
+ return "online";
+ case DM_VDO_INDEX_UNKNOWN:
+ return "unknown";
+ }
+
+ return "<unknown>";
+}
+
+static void _print_status(FILE *stream, struct dm_vdo_status *s)
+{
+ fprintf(stream, "<status| %s ", s->device);
+ fprintf(stream, "%s ", _op_mode(s->operating_mode));
+ fprintf(stream, "%s ", s->recovering ? "recovering" : "-");
+ fprintf(stream, "%s ", _index_state(s->index_state));
+ fprintf(stream, "%s ", s->compression_state == DM_VDO_COMPRESSION_ONLINE ? "online" : "offline");
+ fprintf(stream, "%llu ", (unsigned long long) s->used_blocks);
+ fprintf(stream, "%llu", (unsigned long long) s->total_blocks);
+ fprintf(stream, ">");
+}
+#endif
+
+struct example_good {
+ const char *input;
+ struct dm_vdo_status status;
+};
+
+static void _check_good(struct example_good *es, unsigned count)
+{
+ unsigned i;
+
+ for (i = 0; i < count; i++) {
+ struct example_good *e = es + i;
+ struct dm_vdo_status_parse_result pr;
+
+ T_ASSERT(dm_vdo_status_parse(NULL, e->input, &pr));
+#if 0
+ _print_status(stderr, pr.status);
+ fprintf(stderr, "\n");
+ _print_status(stderr, &e->status);
+ fprintf(stderr, "\n");
+#endif
+ T_ASSERT(_status_eq(&e->status, pr.status));
+ free(pr.status);
+ }
+}
+
+struct example_bad {
+ const char *input;
+ const char *reason;
+};
+
+static void _check_bad(struct example_bad *es, unsigned count)
+{
+ unsigned i;
+
+ for (i = 0; i < count; i++) {
+ struct example_bad *e = es + i;
+ struct dm_vdo_status_parse_result pr;
+
+ T_ASSERT(!dm_vdo_status_parse(NULL, e->input, &pr));
+ T_ASSERT(!strcmp(e->reason, pr.error));
+ }
+}
+
+static void _test_device_names_good(void *fixture)
+{
+ static struct example_good _es[] = {
+ {"foo1234 read-only - error online 0 1234",
+ {(char *) "foo1234", DM_VDO_MODE_READ_ONLY, false, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ {"f read-only - error online 0 1234",
+ {(char *) "f", DM_VDO_MODE_READ_ONLY, false, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ };
+
+ _check_good(_es, DM_ARRAY_SIZE(_es));
+}
+
+static void _test_operating_mode_good(void *fixture)
+{
+ static struct example_good _es[] = {
+ {"device-name recovering - error online 0 1234",
+ {(char *) "device-name", DM_VDO_MODE_RECOVERING, false, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ {"device-name read-only - error online 0 1234",
+ {(char *) "device-name", DM_VDO_MODE_READ_ONLY, false, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ {"device-name normal - error online 0 1234",
+ {(char *) "device-name", DM_VDO_MODE_NORMAL, false, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ };
+
+ _check_good(_es, DM_ARRAY_SIZE(_es));
+}
+
+static void _test_operating_mode_bad(void *fixture)
+{
+ static struct example_bad _es[] = {
+ {"device-name investigating - error online 0 1234",
+ "couldn't parse 'operating mode'"}};
+
+ _check_bad(_es, DM_ARRAY_SIZE(_es));
+}
+
+static void _test_recovering_good(void *fixture)
+{
+ static struct example_good _es[] = {
+ {"device-name recovering - error online 0 1234",
+ {(char *) "device-name", DM_VDO_MODE_RECOVERING, false, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ {"device-name read-only recovering error online 0 1234",
+ {(char *) "device-name", DM_VDO_MODE_READ_ONLY, true, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ };
+
+ _check_good(_es, DM_ARRAY_SIZE(_es));
+}
+
+static void _test_recovering_bad(void *fixture)
+{
+ static struct example_bad _es[] = {
+ {"device-name normal fish error online 0 1234",
+ "couldn't parse 'recovering'"}};
+
+ _check_bad(_es, DM_ARRAY_SIZE(_es));
+}
+
+static void _test_index_state_good(void *fixture)
+{
+ static struct example_good _es[] = {
+ {"device-name recovering - error online 0 1234",
+ {(char *) "device-name", DM_VDO_MODE_RECOVERING, false, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ {"device-name recovering - closed online 0 1234",
+ {(char *) "device-name", DM_VDO_MODE_RECOVERING, false, DM_VDO_INDEX_CLOSED, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ {"device-name recovering - opening online 0 1234",
+ {(char *) "device-name", DM_VDO_MODE_RECOVERING, false, DM_VDO_INDEX_OPENING, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ {"device-name recovering - closing online 0 1234",
+ {(char *) "device-name", DM_VDO_MODE_RECOVERING, false, DM_VDO_INDEX_CLOSING, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ {"device-name recovering - offline online 0 1234",
+ {(char *) "device-name", DM_VDO_MODE_RECOVERING, false, DM_VDO_INDEX_OFFLINE, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ {"device-name recovering - online online 0 1234",
+ {(char *) "device-name", DM_VDO_MODE_RECOVERING, false, DM_VDO_INDEX_ONLINE, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ {"device-name recovering - unknown online 0 1234",
+ {(char *) "device-name", DM_VDO_MODE_RECOVERING, false, DM_VDO_INDEX_UNKNOWN, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ };
+
+ _check_good(_es, DM_ARRAY_SIZE(_es));
+}
+
+static void _test_index_state_bad(void *fixture)
+{
+ static struct example_bad _es[] = {
+ {"device-name normal - fish online 0 1234",
+ "couldn't parse 'index state'"}};
+
+ _check_bad(_es, DM_ARRAY_SIZE(_es));
+}
+
+static void _test_compression_state_good(void *fixture)
+{
+ static struct example_good _es[] = {
+ {"device-name recovering - error online 0 1234",
+ {(char *) "device-name", DM_VDO_MODE_RECOVERING, false, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ {"device-name read-only - error offline 0 1234",
+ {(char *) "device-name", DM_VDO_MODE_READ_ONLY, false, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_OFFLINE, 0, 1234}},
+ };
+
+ _check_good(_es, DM_ARRAY_SIZE(_es));
+}
+
+static void _test_compression_state_bad(void *fixture)
+{
+ static struct example_bad _es[] = {
+ {"device-name normal - error fish 0 1234",
+ "couldn't parse 'compression state'"}};
+
+ _check_bad(_es, DM_ARRAY_SIZE(_es));
+}
+
+static void _test_used_blocks_good(void *fixture)
+{
+ static struct example_good _es[] = {
+ {"device-name recovering - error online 0 1234",
+ {(char *) "device-name", DM_VDO_MODE_RECOVERING, false, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ {"device-name read-only - error offline 1 1234",
+ {(char *) "device-name", DM_VDO_MODE_READ_ONLY, false, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_OFFLINE, 1, 1234}},
+ {"device-name read-only - error offline 12 1234",
+ {(char *) "device-name", DM_VDO_MODE_READ_ONLY, false, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_OFFLINE, 12, 1234}},
+ {"device-name read-only - error offline 3456 1234",
+ {(char *) "device-name", DM_VDO_MODE_READ_ONLY, false, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_OFFLINE, 3456, 1234}},
+ };
+
+ _check_good(_es, DM_ARRAY_SIZE(_es));
+}
+
+static void _test_used_blocks_bad(void *fixture)
+{
+ static struct example_bad _es[] = {
+ {"device-name normal - error online fish 1234",
+ "couldn't parse 'used blocks'"}};
+
+ _check_bad(_es, DM_ARRAY_SIZE(_es));
+}
+
+static void _test_total_blocks_good(void *fixture)
+{
+ static struct example_good _es[] = {
+ {"device-name recovering - error online 0 1234",
+ {(char *) "device-name", DM_VDO_MODE_RECOVERING, false, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_ONLINE, 0, 1234}},
+ {"device-name recovering - error online 0 1",
+ {(char *) "device-name", DM_VDO_MODE_RECOVERING, false, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_ONLINE, 0, 1}},
+ {"device-name recovering - error online 0 0",
+ {(char *) "device-name", DM_VDO_MODE_RECOVERING, false, DM_VDO_INDEX_ERROR, DM_VDO_COMPRESSION_ONLINE, 0, 0}},
+ };
+
+ _check_good(_es, DM_ARRAY_SIZE(_es));
+}
+
+static void _test_total_blocks_bad(void *fixture)
+{
+ static struct example_bad _es[] = {
+ {"device-name normal - error online 0 fish",
+ "couldn't parse 'total blocks'"}};
+
+ _check_bad(_es, DM_ARRAY_SIZE(_es));
+}
+
+static void _test_status_bad(void *fixture)
+{
+ struct example_bad _bad[] = {
+ {"", "couldn't get token for device"},
+ {"device-name read-only - error online 0 1000 lksd", "too many tokens"}
+ };
+
+ _check_bad(_bad, DM_ARRAY_SIZE(_bad));
+}
+
+//----------------------------------------------------------------
+
+#define T(path, desc, fn) register_test(ts, "/device-mapper/vdo/status/" path, desc, fn)
+
+static struct test_suite *_tests(void)
+{
+ struct test_suite *ts = test_suite_create(NULL, NULL);
+ if (!ts) {
+ fprintf(stderr, "out of memory\n");
+ exit(1);
+ };
+
+ T("device-names", "parse various device names", _test_device_names_good);
+ T("operating-mode-good", "operating mode, good examples", _test_operating_mode_good);
+ T("operating-mode-bad", "operating mode, bad examples", _test_operating_mode_bad);
+ T("recovering-good", "recovering, good examples", _test_recovering_good);
+ T("recovering-bad", "recovering, bad examples", _test_recovering_bad);
+ T("index-state-good", "index state, good examples", _test_index_state_good);
+ T("index-state-bad", "index state, bad examples", _test_index_state_bad);
+ T("compression-state-good", "compression state, good examples", _test_compression_state_good);
+ T("compression-state-bad", "compression state, bad examples", _test_compression_state_bad);
+ T("used-blocks-good", "used blocks, good examples", _test_used_blocks_good);
+ T("used-blocks-bad", "used blocks, bad examples", _test_used_blocks_bad);
+ T("total-blocks-good", "total blocks, good examples", _test_total_blocks_good);
+ T("total-blocks-bad", "total blocks, bad examples", _test_total_blocks_bad);
+ T("bad", "parse various badly formed vdo status lines", _test_status_bad);
+
+ return ts;
+}
+
+void vdo_tests(struct dm_list *all_tests)
+{
+ dm_list_add(all_tests, &_tests()->list);
+}
+
+//----------------------------------------------------------------
generated by cgit v1.2.3 (git 2.25.1) at 2024-11-25 22:30:11 +0000