From 39a483f54bd5a9d30ddb7923433a2b3e872bd284 Mon Sep 17 00:00:00 2001 From: Matthew Wilcox Date: Thu, 20 Dec 2018 14:41:03 -0500 Subject: [PATCH] maple_tree: Fix mt_dump Conform to new definition of maple tree Signed-off-by: Matthew Wilcox --- include/linux/maple_tree.h | 15 +++++- lib/maple_tree.c | 70 ++++++++++++++++--------- tools/testing/radix-tree/linux/kernel.h | 1 + tools/testing/radix-tree/maple.c | 21 ++++++++ 4 files changed, 82 insertions(+), 25 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index eca9137a189d..4c135f49d08c 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -112,10 +112,23 @@ struct maple_node { struct maple_sparse_21 ms21; struct maple_sparse_16 ms16; struct maple_sparse_9 ms9; - struct maple_sparse_6 ms6; + struct maple_sparse_6 ms6; }; }; +enum maple_type { + maple_dense, + maple_range_64, + maple_range_32, + maple_range_16, + maple_sparse_64, + maple_sparse_32, + maple_sparse_21, + maple_sparse_16, + maple_sparse_9, + maple_sparse_6, +}; + struct maple_tree { spinlock_t ma_lock; unsigned int ma_flags; diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ce0d636acbb5..42d49595eb7f 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -17,16 +17,16 @@ static inline bool mas_is_start(struct ma_state *ms) 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); + return (struct maple_node *)((unsigned long)entry & ~127); } -static inline void *ma_mk_node(const struct maple_node *node) +static inline +void *ma_mk_node(const struct maple_node *node, enum maple_type type) { BUG_ON(xa_is_node(node)); - return (void *)((unsigned long)node | 2); + return (void *)((unsigned long)node | (type << 2) | 2); } - void mtree_init(struct maple_tree *mt) { spin_lock_init(&mt->ma_lock); mt->ma_flags = 0; @@ -50,7 +50,8 @@ void mtree_destroy(struct maple_tree *mt) { } #ifdef MT_DEBUG -void mn_dump(void *entry, unsigned long min, unsigned long max) +void mn_dump(void *entry, unsigned long min, unsigned long max, + unsigned int depth) { if (min == max) pr_info("%lu: ", min); @@ -58,24 +59,30 @@ void mn_dump(void *entry, unsigned long min, unsigned long max) 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; + struct maple_range_64 *node = &ma_to_node(entry)->mr64; + unsigned long first = 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("node %p depth %d parent %p contents: ", node, depth, + node->parent); + for (i = 0; i < MAPLE_RANGE64_SLOTS - 1; i++) { + pr_cont("%p %lu ", node->slot[i], node->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) + pr_cont("%p\n", node->slot[i]); + + for (i = 0; i < MAPLE_RANGE64_SLOTS; i++) { + unsigned long last = max; + + if (i < (MAPLE_RANGE64_SLOTS - 1)) + last = node->pivot[i]; + if (last == 0 && i > 0) break; - prev = next; + mn_dump(node->slot[i], first, last, depth + 1); + if (last > max) { + pr_err("node %p last (%lu) > max (%lu) at pivot %d!\n", node, last, max, i); + break; + } + first = last + 1; } } else if (xa_is_value(entry)) pr_cont("value %ld (0x%lx) [%p]\n", xa_to_value(entry), @@ -88,16 +95,31 @@ void mn_dump(void *entry, unsigned long min, unsigned long max) pr_cont("UNKNOWN ENTRY (%p)\n", entry); } +unsigned long mt_max[] = { + MAPLE_NODE_SLOTS, + ULONG_MAX, + UINT_MAX, + (1UL << 16) - 1, + ULONG_MAX, + UINT_MAX, + (1UL << 21) - 1, + (1UL << 16) - 1, + (1UL << 9) - 1, + (1UL << 6) - 1, +}; + void mt_dump(const struct maple_tree *mt) { void *entry = mt->ma_root; - unsigned long min = 0; - unsigned long max = ULONG_MAX; + unsigned long 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); + else + max = mt_max[xa_to_internal(entry) & 15]; + + pr_info("maple_tree(%p) flags %X, root %p, max %lu\n", + mt, mt->ma_flags, entry, max); + mn_dump(entry, 0, max, 0); } #endif diff --git a/tools/testing/radix-tree/linux/kernel.h b/tools/testing/radix-tree/linux/kernel.h index 39867fd80c8f..c5c9d05f29da 100644 --- a/tools/testing/radix-tree/linux/kernel.h +++ b/tools/testing/radix-tree/linux/kernel.h @@ -14,6 +14,7 @@ #include "../../../include/linux/kconfig.h" #define printk printf +#define pr_err printk #define pr_info printk #define pr_debug printk #define pr_cont printk diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 7f1ce8e45686..9838f144545f 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -17,8 +17,29 @@ #undef MT_DEBUG #include "../../../lib/test_maple_tree.c" +void farmer_tests(void) +{ + struct maple_node *node; + DEFINE_MTREE(tree); + mt_dump(&tree); + + tree.ma_root = xa_mk_value(0); + mt_dump(&tree); + + posix_memalign(&node, 128, 128); + node->parent = (void *)((unsigned long)(&tree) | 1); + node->slot[0] = xa_mk_value(0); + node->slot[1] = xa_mk_value(1); + node->mr64.pivot[0] = 0; + node->mr64.pivot[1] = 1; + node->mr64.pivot[2] = 0; + tree.ma_root = ma_mk_node(node, maple_range_64); + mt_dump(&tree); +} + void maple_tree_tests(void) { + farmer_tests(); maple_tree_seed(); maple_tree_harvest(); } -- 2.50.1