From 006012c67b8b65025b2069d5d5f57e4e452169c6 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Wed, 19 Dec 2018 15:43:14 -0500 Subject: [PATCH] maple_tree: Testing framework and stubbed out maple_tree.c Also fix some compile issues with header. Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 12 +- lib/maple_tree.c | 94 +++++ lib/test_maple_tree.c | 358 ++++++++++++++++++++ tools/testing/radix-tree/.gitignore | 1 + tools/testing/radix-tree/Makefile | 9 +- tools/testing/radix-tree/linux/maple_tree.h | 1 + tools/testing/radix-tree/maple.c | 35 ++ 7 files changed, 503 insertions(+), 7 deletions(-) create mode 100644 lib/test_maple_tree.c create mode 100644 tools/testing/radix-tree/linux/maple_tree.h create mode 100644 tools/testing/radix-tree/maple.c diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 04362554799d..369977f64207 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -25,6 +25,7 @@ * * Nodes in the tree point to their parent unless bit 0 is set. */ +#define CONFIG_64BIT #ifdef CONFIG_64BIT #define MAPLE_NODE_SLOTS 15 /* 128 bytes including ->parent */ #define MAPLE_RANGE64_SLOTS 8 /* 128 bytes */ @@ -131,8 +132,8 @@ struct maple_tree { #define DEFINE_MTREE(name) \ struct maple_tree name = MTREE_INIT(name, 0) -#define mtree_lock(mt) spin_lock(&mt->lock); -#define mtree_unlock(mt) spin_unlock(&mt->lock); +#define mtree_lock(mt) spin_lock(&mt->ma_lock); +#define mtree_unlock(mt) spin_unlock(&mt->ma_lock); void mtree_init(struct maple_tree *); void *mtree_load(struct maple_tree *, unsigned long index); @@ -140,6 +141,7 @@ int mtree_insert(struct maple_tree *, unsigned long index, void *entry, gfp_t); int mtree_insert_range(struct maple_tree *, unsigned long first, unsigned long last, void *entry, gfp_t); int mtree_erase(struct maple_tree *, unsigned long index); +void mtree_destroy(struct maple_tree *); /** * mtree_empty() - Determine if a tree has any present entries. @@ -185,11 +187,11 @@ struct ma_state { #define MAS_NONE ((struct maple_node *)9UL) #define MA_ERROR(err) ((struct maple_node *)(((unsigned long)err << 2) | 2UL)) -#define MA_STATE(name, tree, first, last) \ +#define MA_STATE(name, mt, first, end) \ struct ma_state name = { \ - .tree = tree, \ + .tree = mt, \ .index = first, \ - .last = last, \ + .last = end, \ .node = MAS_START, \ .min = 0, \ .max = ULONG_MAX, \ diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 5afbb2cca6e7..ce0d636acbb5 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -7,3 +7,97 @@ */ #include + + +static inline bool mas_is_start(struct ma_state *ms) +{ + return ms->node == MAS_START; +} + +static inline struct maple_node *ma_to_node(const void *entry) +{ + BUG_ON(!xa_is_node(entry)); + return (struct maple_node *)((unsigned long)entry - 2); +} + +static inline void *ma_mk_node(const struct maple_node *node) +{ + BUG_ON(xa_is_node(node)); + return (void *)((unsigned long)node | 2); +} + + +void mtree_init(struct maple_tree *mt) { + spin_lock_init(&mt->ma_lock); + mt->ma_flags = 0; + mt->ma_root = NULL; +} +void *mtree_load(struct maple_tree *mt, unsigned long index) { + return NULL; +} +int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry, gfp_t gfp) { + return -EINVAL; +} +int mtree_insert_range(struct maple_tree *mt, unsigned long first, + unsigned long last, void *entry, gfp_t gfp) { + return -EINVAL; +} +int mtree_erase(struct maple_tree *mt, unsigned long index) { + return -EINVAL; +} + +void mtree_destroy(struct maple_tree *mt) { +} + +#ifdef MT_DEBUG +void mn_dump(void *entry, unsigned long min, unsigned long max) +{ + if (min == max) + pr_info("%lu: ", min); + else + pr_info("%lu-%lu: ", min, max); + + if (xa_is_node(entry)) { + struct maple_sparse_64 *mn64 = &ma_to_node(entry)->ms64; + unsigned long prev = min; + unsigned int i; + + pr_cont("node %p parent %p contents: ", mn64, mn64->parent); + for (i = 0; i < MAPLE_RANGE64_SLOTS; i++) { + pr_cont("%p %lu ", mn64->slot[i], mn64->pivot[i]); + } + pr_cont("%p\n", mn64->slot[i]); + + for (i = 0; i < MAPLE_RANGE64_SLOTS -1; i++) { + unsigned long next = max + 1; + if (i < MAPLE_RANGE64_SLOTS) + next = mn64->pivot[i]; + mn_dump(mn64->slot[i], prev, next - 1); + if (next == 0 || (next - 1) >= max) + break; + prev = next; + } + } else if (xa_is_value(entry)) + pr_cont("value %ld (0x%lx) [%p]\n", xa_to_value(entry), + xa_to_value(entry), entry); + else if (!xa_is_internal(entry)) + pr_cont("%p\n", entry); + else if (xa_is_zero(entry)) + pr_cont("zero (%ld)\n", xa_to_internal(entry)); + else + pr_cont("UNKNOWN ENTRY (%p)\n", entry); +} + +void mt_dump(const struct maple_tree *mt) +{ + void *entry = mt->ma_root; + unsigned long min = 0; + unsigned long max = ULONG_MAX; + + if (!xa_is_node(entry)) + max = 0; + pr_info("maple_tree(%p) flags %X, root %p, min %lu, max %lu\n", + mt, mt->ma_flags, entry, min, max); + mn_dump(entry, min, max); +} +#endif diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c new file mode 100644 index 000000000000..db202646d09e --- /dev/null +++ b/lib/test_maple_tree.c @@ -0,0 +1,358 @@ +// SPDX-License-Identifier: GPL-2.0+ +/* + * test_maple_tree.c: Test the maple tree API + * Copyright (c) 2018 Liam R. Howlett + * Author: Liam R. Howlett + */ + +#include +#include + +static unsigned int tests_run; +static unsigned int tests_passed; + +#ifndef MAPLE_TREE_DEBUG +# ifdef __KERNEL__ +void mt_dump(const struct maple_tree *mt) { } +# endif +#undef MT_BUG_ON +#define MT_BUG_ON(tree, x) do { \ + tests_run++; \ + if (x) { \ + printk("BUG at %s:%d (%u)\n", \ + __func__, __LINE__, x); \ + mt_dump(tree); \ + printk("Pass: %u Run:%u\n", tests_passed, tests_run); \ + dump_stack(); \ + } else { \ + tests_passed++; \ + } \ +} while (0) +#endif + +static +int mtree_insert_index(struct maple_tree *mt, unsigned long index, gfp_t gfp) +{ + return mtree_insert(mt, index, xa_mk_value(index & LONG_MAX), gfp); +} + +static int mtree_test_insert(struct maple_tree *mt, unsigned long index, + void *ptr) +{ + return mtree_insert(mt, index, ptr, GFP_KERNEL); +} + +static int mtree_test_insert_range(struct maple_tree *mt, unsigned long start, + unsigned long end, void *ptr) +{ + return mtree_insert_range(mt, start, end, ptr, GFP_KERNEL); +} + +static void *mtree_test_load(struct maple_tree *mt, unsigned long index) +{ + return mtree_load(mt, index); +} + + +static noinline void check_insert_range(struct maple_tree *mt, + unsigned long start, unsigned long end, void *ptr) +{ + int ret = -EINVAL; + ret = mtree_test_insert_range(mt, start, end, ptr); + MT_BUG_ON(mt, ret != 0); +} + +static noinline void check_insert(struct maple_tree *mt, unsigned long index, + void *ptr) +{ + int ret = -EINVAL; + ret = mtree_test_insert(mt, index, ptr); + MT_BUG_ON(mt, ret != 0); +} + +static noinline void check_dup_insert(struct maple_tree *mt, + unsigned long index, void *ptr) +{ + int ret = -EINVAL; + ret = mtree_test_insert(mt, index, ptr); + MT_BUG_ON(mt, ret != -EEXIST); +} + + +static noinline void check_load(struct maple_tree *mt, unsigned long index, + void *ptr) +{ + void *ret = mtree_test_load(mt, index); + + MT_BUG_ON(mt, ret != ptr); +} + +static noinline +void check_index_load(struct maple_tree *mt, unsigned long index) +{ + return check_load(mt, index, xa_mk_value(index & LONG_MAX)); +} + +static noinline void check_nomem(struct maple_tree *mt) +{ +#if 0 + MA_STATE(ms, mt, 1, 1); + + MT_BUG_ON(mt, !mtree_empty(mt)); + + /* Storing something at 1 requires memory allocation */ + MT_BUG_ON(mt, mtree_insert_index(mt, 1, GFP_ATOMIC) != -ENOMEM); + /* Storing something at 0 does not */ + MT_BUG_ON(mt, mtree_insert_index(mt, 0, GFP_ATOMIC) != 0); + + /* + * Simulate two threads racing; the first one fails to allocate + * memory to insert an entry at 1, then the second one succeeds + * in allocating memory to insert an entry at 2. The first one + * then needs to free the node it allocated. LeakSanitizer will + * notice this, as will the 'nr_allocated' debugging aid in the + * userspace test suite. + */ + mtree_lock(mt); + _maple_setup_insert(&ms); + MT_BUG_ON(mt, ms.node != MA_ERROR(-ENOMEM)); + _maple_insert(&ms, xa_mk_value(1)); + mas_nomem(&ms, GFP_KERNEL); + MT_BUG_ON(mt, ms.node != MAS_START); + mtree_unlock(mt); + MT_BUG_ON(mt, mtree_insert_index(mt, 2, GFP_KERNEL) != 0); + mtree_lock(mt); + _maple_setup_insert(&ms); + _maple_insert(&ms, xa_mk_value(1)); + mas_nomem(&ms, GFP_KERNEL); + mtree_unlock(mt); +#endif + + mtree_destroy(mt); +} + +static noinline int alloc_req(struct ma_state *ms) { + return (int)(((unsigned long)ms->alloc & 0x03)); +} +static noinline void check_new_node(struct maple_tree *mt) +{ +#if 0 + + struct maple_node *mn; + MA_STATE(ms, mt, 0, 0); + + /* Try allocating 3 nodes */ + mtree_lock(mt); + maple_state_node(&ms, 3); // req allocate 3 node. + MT_BUG_ON(mt, alloc_req(&ms) != 3); // Allocation request of 3. + + MT_BUG_ON(mt, ms.node != MA_ERROR(-ENOMEM)); // Allocate failed. + MT_BUG_ON(mt, !mas_nomem(&ms, GFP_KERNEL)); + + + MT_BUG_ON(mt, ma_get_alloc_cnt(&ms) != 3); + mn = ma_get_alloc(&ms); + MT_BUG_ON(mt, mn == NULL); + MT_BUG_ON(mt, mn->slot[0] == NULL); + MT_BUG_ON(mt, mn->slot[1] == NULL); + mas_nomem(&ms, GFP_KERNEL); // free; + mtree_unlock(mt); + + + /* Try allocating 1 node, then 2 more */ + mtree_lock(mt); + maple_state_node(&ms, 1); // allocate 1 node. + MT_BUG_ON(mt, alloc_req(&ms) != 1); // Allocation request of 1. + MT_BUG_ON(mt, !mas_nomem(&ms, GFP_KERNEL)); // Validate allocation request. + mn = ma_get_alloc(&ms); + + MT_BUG_ON(mt, mn == NULL); + MT_BUG_ON(mt, mn->slot[0] != NULL); + MT_BUG_ON(mt, mn->slot[1] != NULL); + MT_BUG_ON(mt, ma_get_alloc_cnt(&ms) != 1); + maple_state_node(&ms, 3); // req allocate 3 node. + MT_BUG_ON(mt, ma_get_alloc_cnt(&ms) != 1); // Still only 1 allocated. + MT_BUG_ON(mt, ma_get_alloc_req(&ms) != 2); // Allocation request of 2. + + mas_nomem(&ms, GFP_KERNEL); // Validate request for 2 more. + MT_BUG_ON(mt, mn == NULL); + MT_BUG_ON(mt, mn->slot[0] == NULL); + MT_BUG_ON(mt, mn->slot[1] == NULL); + MT_BUG_ON(mt, ma_get_alloc_cnt(&ms) != 3); // Ensure we counted 3. + mas_nomem(&ms, GFP_KERNEL); // Free. + + mtree_unlock(mt); + mtree_destroy(mt); +#endif +} +static noinline void check_seq(struct maple_tree *mt) +{ + int i, j; + + MT_BUG_ON(mt, !mtree_empty(mt)); + + for (i = 0; i < 16; i++) { + MT_BUG_ON(mt, mtree_insert_index(mt, i, GFP_KERNEL)); + for (j = 0; j <= i; j++) + check_index_load(mt, j); + check_load(mt, i + 1, NULL); + } + mtree_destroy(mt); +} + +static noinline void check_double_insert_leaf(struct maple_tree *mt) +{ + unsigned long i, j; + unsigned long huge = 4000UL * 1000 * 1000; + + MT_BUG_ON(mt, !mtree_empty(mt)); + + i = huge; + while (i > 0x80) { + check_insert(mt, i, xa_mk_value(i)); + for (j = huge; j >= i; j /= 2) { + check_load(mt, j, xa_mk_value(j)); + check_load(mt, j+1, NULL); + } + i /= 2; + } + mtree_destroy(mt); +} + +static DEFINE_MTREE(tree); + +static int maple_tree_seed(void) +{ + unsigned long set[] = {15, 14, 17, 25, 1000, + 1001, 1002, 1003, 1005, 0, + 3}; + unsigned long r[] = {10, 15, 20, 25, 22}; // For range testing + void *ptr = &set; + + + mtree_init(&tree); + check_new_node(&tree); + check_double_insert_leaf(&tree); + check_load(&tree, set[0], NULL); // See if 15 -> NULL + + check_insert(&tree, set[9], &tree); // Insert 0 + check_load(&tree, set[9], &tree); // See if 0 -> &tree + check_load(&tree, set[0], NULL); // See if 15 -> NULL + + check_insert(&tree, set[10], ptr); // Insert 3 + check_load(&tree, set[9], &tree); // See if 0 -> &tree + + check_load(&tree, set[10], ptr); // See if 3 -> ptr + + /* Clear out the tree */ + mtree_destroy(&tree); + + /* Try to insert, insert a dup, and load back what was inserted. */ + mtree_init(&tree); + check_insert(&tree, set[0], &tree); // Insert 15 + check_dup_insert(&tree, set[0], &tree); // Insert 15 again + check_load(&tree, set[0], &tree); // See if 15 -> &tree + + /* Second set of tests try to load a value that doesn't exist, inserts + * a second value, then loads the value again + */ + check_load(&tree, set[1], NULL); // See if 14 -> NULL + check_insert(&tree, set[1], ptr); // insert 14 -> ptr + check_load(&tree, set[1], ptr); // See if 14 -> ptr + check_load(&tree, set[0], &tree); // See if 15 -> &tree + + /* Tree currently contains: + * p[0]: 14 -> (nil) p[1]: 15 -> ptr p[2]: 16 -> &tree p[3]: 0 -> (nil) + */ + check_insert(&tree, set[6], ptr); // insert 1002 -> ptr + check_insert(&tree, set[7], &tree); // insert 1003 -> &tree + + check_load(&tree, set[0], &tree); // See if 15 -> &tree + check_load(&tree, set[1], ptr); // See if 14 -> ptr + check_load(&tree, set[6], ptr); // See if 1002 -> ptr + check_load(&tree, set[7], &tree); // 1003 = &tree ? + + /* Clear out tree */ + mtree_destroy(&tree); + + mtree_init(&tree); + /* Test inserting into a NULL hole. */ + check_insert(&tree, set[5], ptr); // insert 1001 -> ptr + check_insert(&tree, set[7], &tree); // insert 1003 -> &tree + check_insert(&tree, set[6], ptr); // insert 1002 -> ptr + check_load(&tree, set[5], ptr); // See if 1001 -> ptr + check_load(&tree, set[6], ptr); // See if 1002 -> ptr + check_load(&tree, set[7], &tree); // See if 1003 -> &tree + + /* Clear out the tree */ + mtree_destroy(&tree); + + mtree_init(&tree); + + check_insert_range(&tree, r[0], r[1], ptr); // Insert 10-15 => ptr + check_insert_range(&tree, r[2], r[3], ptr); // Insert 20-25 => &tree + + /* Clear out the tree */ + mtree_destroy(&tree); + + mtree_init(&tree); +/* + * set[] = {15, 14, 17, 25, 1000, + * 1001, 1002, 1003, 1005, 0, + * 3}; + */ + + check_insert(&tree, set[0], ptr); // 15 + check_insert(&tree, set[1], &tree); // 14 + check_insert(&tree, set[2], ptr); // 17 + check_insert(&tree, set[3], &tree); // 25. + check_insert(&tree, set[4], ptr); // 1000 < Should split. + check_load(&tree, set[0], ptr); + check_load(&tree, set[1], &tree); + check_load(&tree, set[2], ptr); + check_load(&tree, set[3], &tree); //25 + check_load(&tree, set[4], ptr); + check_insert(&tree, set[5], &tree); // 1001 + check_load(&tree, set[0], ptr); + check_load(&tree, set[1], &tree); + check_load(&tree, set[2], ptr); + check_load(&tree, set[3], &tree); + check_load(&tree, set[4], ptr); + check_load(&tree, set[5], &tree); + check_insert(&tree, set[6], ptr); + check_load(&tree, set[0], ptr); + check_load(&tree, set[1], &tree); + check_load(&tree, set[2], ptr); + check_load(&tree, set[3], &tree); + check_load(&tree, set[4], ptr); + check_load(&tree, set[5], &tree); + check_load(&tree, set[6], ptr); + check_insert(&tree, set[7], &tree); + check_insert(&tree, set[8], ptr); + check_insert(&tree, set[9], &tree); + check_load(&tree, set[0], ptr); + check_load(&tree, set[1], &tree); + check_load(&tree, set[2], ptr); + check_load(&tree, set[3], &tree); + check_load(&tree, set[4], ptr); + check_load(&tree, set[5], &tree); + check_load(&tree, set[6], ptr); + check_load(&tree, set[9], &tree); + mtree_destroy(&tree); + + check_nomem(&tree); + check_seq(&tree); + + printk("maple_tree: %u of %u tests passed\n", tests_passed, tests_run); + return (tests_run == tests_passed) ? 0 : -EINVAL; +} + +static void maple_tree_harvest(void) +{ + +} + +module_init(maple_tree_seed); +module_exit(maple_tree_harvest); +MODULE_AUTHOR("Liam R. Howlett "); +MODULE_LICENSE("GPL"); diff --git a/tools/testing/radix-tree/.gitignore b/tools/testing/radix-tree/.gitignore index d971516401e6..897b67ad78d6 100644 --- a/tools/testing/radix-tree/.gitignore +++ b/tools/testing/radix-tree/.gitignore @@ -6,3 +6,4 @@ main multiorder radix-tree.c xarray +maple diff --git a/tools/testing/radix-tree/Makefile b/tools/testing/radix-tree/Makefile index aa6abfe0749c..3e0fa6ae0e0a 100644 --- a/tools/testing/radix-tree/Makefile +++ b/tools/testing/radix-tree/Makefile @@ -4,8 +4,8 @@ CFLAGS += -I. -I../../include -g -Og -Wall -D_LGPL_SOURCE -fsanitize=address \ -fsanitize=undefined LDFLAGS += -fsanitize=address -fsanitize=undefined LDLIBS+= -lpthread -lurcu -TARGETS = main idr-test multiorder xarray -CORE_OFILES := xarray.o radix-tree.o idr.o linux.o test.o find_bit.o bitmap.o +TARGETS = main idr-test multiorder xarray maple +CORE_OFILES := xarray.o radix-tree.o idr.o linux.o test.o find_bit.o bitmap.o maple.o OFILES = main.o $(CORE_OFILES) regression1.o regression2.o regression3.o \ regression4.o tag_check.o multiorder.o idr-test.o iteration_check.o \ iteration_check_2.o benchmark.o @@ -28,6 +28,8 @@ idr-test: idr-test.o $(CORE_OFILES) xarray: $(CORE_OFILES) +maple: $(CORE_OFILES) + multiorder: multiorder.o $(CORE_OFILES) clean: @@ -39,6 +41,7 @@ $(OFILES): Makefile *.h */*.h generated/map-shift.h \ ../../include/linux/*.h \ ../../include/asm/*.h \ ../../../include/linux/xarray.h \ + ../../../include/linux/maple_tree.h \ ../../../include/linux/radix-tree.h \ ../../../include/linux/idr.h @@ -50,6 +53,8 @@ idr.c: ../../../lib/idr.c xarray.o: ../../../lib/xarray.c ../../../lib/test_xarray.c +maple.o: ../../../lib/maple_tree.c ../../../lib/test_maple_tree.c + generated/map-shift.h: @if ! grep -qws $(SHIFT) generated/map-shift.h; then \ echo "#define XA_CHUNK_SHIFT $(SHIFT)" > \ diff --git a/tools/testing/radix-tree/linux/maple_tree.h b/tools/testing/radix-tree/linux/maple_tree.h new file mode 100644 index 000000000000..dbf00f34d877 --- /dev/null +++ b/tools/testing/radix-tree/linux/maple_tree.h @@ -0,0 +1 @@ +#include "../../../../include/linux/maple_tree.h" diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c new file mode 100644 index 000000000000..7f1ce8e45686 --- /dev/null +++ b/tools/testing/radix-tree/maple.c @@ -0,0 +1,35 @@ +// SPDX-License-Identifier: GPL-2.0+ +/* + * maple_tree.c: Userspace shim for maple tree test-suite + * Copyright (c) 2018 Liam R. Howlett + */ + +#define MT_DEBUG +#include "test.h" + +#define module_init(x) +#define module_exit(x) +#define MODULE_AUTHOR(x) +#define MODULE_LICENSE(x) +#define dump_stack() assert(0) + +#include "../../../lib/maple_tree.c" +#undef MT_DEBUG +#include "../../../lib/test_maple_tree.c" + +void maple_tree_tests(void) +{ + maple_tree_seed(); + maple_tree_harvest(); +} + +int __weak main(void) +{ + radix_tree_init(); + maple_tree_tests(); + radix_tree_cpu_dead(1); + rcu_barrier(); + if (nr_allocated) + printf("nr_allocated = %d\n", nr_allocated); + return 0; +} -- 2.50.1