From 42260ed212553710834b4943f163f9f38542f1b0 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 8 Nov 2019 11:50:55 -0500 Subject: [PATCH] maple_tree: Fix maple state max/min issues When adding the validations, a number of concerns were raised on the updating of the state information for max/min. These have been addressed and mas_next tests have been added. mas_find and mt_find have been rewritten with the new mas_next. Two new range functions have been added: mas_range_load() and _mas_range_walk(). Both are able to return the range in which a given index falls. Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 12 +- lib/maple_tree.c | 344 ++++++++++----------- lib/test_maple_tree.c | 69 +++-- tools/testing/radix-tree/ma_xa_benchmark.c | 2 +- tools/testing/radix-tree/maple.c | 4 +- 5 files changed, 223 insertions(+), 208 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 3230aaa6a7cd..8fa8a6e0a31f 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -315,8 +315,6 @@ void maple_tree_init(void); static inline void mas_reset(struct ma_state *mas) { mas->node = MAS_START; - mas->max = ULONG_MAX; - mas->min = 0; } /** @@ -344,8 +342,8 @@ static inline void mas_reset(struct ma_state *mas) * */ #define mt_for_each(tree, entry, index, max) \ - for (entry = mt_find(mt, index, max); \ - entry; entry = mt_find_after(mt, &index, max)) + for (entry = mt_find(mt, &index, max, true); \ + entry; entry = mt_find(mt, &index, max, false)) bool mas_retry(struct ma_state *mas, const void *entry); @@ -362,9 +360,9 @@ bool mas_retry(struct ma_state *mas, const void *entry); static inline void mas_set_range(struct ma_state *mas, unsigned long start, unsigned long last) { - mas->index = start; - mas->last = last; - mas->node = MAS_START; + mas->index = start; + mas->last = last; + mas->node = MAS_START; } /** diff --git a/lib/maple_tree.c b/lib/maple_tree.c index c85bbb6bb4a1..172300cf246c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -183,6 +183,20 @@ static inline bool mas_is_start(struct ma_state *mas) return mas->node == MAS_START; } + +static inline bool mas_searchable(struct ma_state *mas) +{ + if (!mas->node) + return false; + + if (mas_is_none(mas)) + return false; + + if (mas_is_ptr(mas)) + return false; + + return true; +} static inline struct maple_node *mte_to_node(const struct maple_enode *entry) { return (struct maple_node *)((unsigned long)entry & ~127); @@ -1007,6 +1021,7 @@ static inline struct maple_enode *mas_start(struct ma_state *mas) mas->node = MAS_NONE; mas->min = 0; + mas->max = ULONG_MAX; if (!mas->tree->ma_root) // empty tree. goto done; @@ -1409,27 +1424,29 @@ no_entry: * */ static inline unsigned long mas_first_entry(struct ma_state *mas, - unsigned long max) + unsigned long limit) { unsigned long pivot; while (1) { - pivot = mas_first_node(mas, max); - if (mas->node == MAS_NONE) + pivot = mas_first_node(mas, limit); + if (mas_is_none(mas)) return pivot; if (mte_is_leaf(mas->node)) { // Get the leaf slot. mas_set_slot(mas, 0); - pivot = mas_first_node(mas, max); - return pivot; + mas_first_node(mas, limit); + if (!mas_get_slot(mas)) + return mas->min; + else + return mas_get_safe_pivot(mas, mas_get_slot(mas)-1); } mas_set_slot(mas, 0); } } - void mte_destroy_walk(struct maple_enode *mn) { struct maple_enode *node; @@ -2549,12 +2566,15 @@ found: } /** Private - * next node entry + * mas_next_nentry() - Next node entry. Set the @mas slot to the next valid + * entry and range_start to the start value for that entry. If there is no + * entry, returns false. */ static inline bool mas_next_nentry(struct ma_state *mas, unsigned long max, - unsigned long *piv) + unsigned long *range_start) { unsigned long pivot = mas->min; + unsigned long r_start = *range_start; unsigned char slot = mas_get_slot(mas); unsigned char count = mt_slot_count(mas->node); void *entry; @@ -2565,7 +2585,6 @@ static inline bool mas_next_nentry(struct ma_state *mas, unsigned long max, if (slot != 0 && pivot == 0) goto no_entry; - *piv = pivot; entry = mte_get_rcu_slot(mas->node, slot); if (!mt_is_empty(entry)) goto found; @@ -2574,6 +2593,7 @@ static inline bool mas_next_nentry(struct ma_state *mas, unsigned long max, if (pivot >= max) goto no_entry; + r_start = pivot + 1; slot++; } @@ -2581,56 +2601,97 @@ no_entry: return false; found: + mas->last = pivot; + *range_start = r_start; mas_set_slot(mas, slot); return true; } - -static inline void *_mas_next(struct ma_state *mas, unsigned long max, - unsigned long *pivot) +/** Private + * + * __mas_next() Set the @mas->node to the next entry and the range_start to + * the beginning value for the entry. Does not check beyond @limit. + * + * May return NULL. + * + */ +static inline void *__mas_next(struct ma_state *mas, unsigned long limit, + unsigned long *range_start) { void *entry = NULL; unsigned long index = mas->index; + unsigned char slot = mas_get_slot(mas); + mas_set_slot(mas, slot + 1); - do { - if (mas->node == MAS_NONE) - return NULL; +retry: + *range_start = mas->last + 1; - if (!mte_is_leaf(mas->node)) { - *pivot = mas_first_entry(mas, max); - } else { - while (mas->node != MAS_NONE) { - unsigned char p_slot; - if (mas_next_nentry(mas, max, pivot)) - break; + while (!mas_is_none(mas)) { + unsigned char p_slot = 0; + if (!mte_is_leaf(mas->node) || !mas_get_slot(mas)) { + *range_start = mas_first_entry(mas, limit); + if (mas_is_none(mas)) + return NULL; + } + if (mas_next_nentry(mas, limit, range_start)) { + break; + } - if (mte_is_root(mas->node)) { - mas->node = MAS_NONE; - break; - } + p_slot = mte_parent_slot(mas->node); + mas_set_slot(mas, p_slot); + mas_next_node(mas, limit); + mas_set_slot(mas, 0); + } - p_slot = mte_parent_slot(mas->node); - mas_set_slot(mas, p_slot); - mas_next_node(mas, max); - if (mas->node != MAS_NONE) { - mas_set_slot(mas, 0); - } - } - } - if (mas_is_none(mas)) - return NULL; - entry = mte_get_rcu_slot(mas->node, mas_get_slot(mas)); - } while (mas_dead_node(mas, index)); + if (mas_is_none(mas)) + return NULL; + entry = mte_get_rcu_slot(mas->node, mas_get_slot(mas)); + if (mas_dead_node(mas, index)) + goto retry; return entry; } + +void *mas_range_load(struct ma_state *mas, unsigned long *range_min, + unsigned long *range_max); +/* Private + * + * _mas_next() - Finds the next entry, sets index to the start of the range. + * + */ +static inline void *_mas_next(struct ma_state *mas, unsigned long max, + unsigned long *range_start) +{ + void *entry = NULL; + + if (mas->node && !mas_searchable(mas)) + return NULL; + + if (!mas->node || mas_is_start(mas)) { // First run. + unsigned long range_max; + entry = mas_range_load(mas, range_start, &range_max); + } + + if (entry) + return entry; + + return __mas_next(mas, max, range_start); +} + +/* + * mas_next() - Get the next entry. Can return the zero entry. mas->node + * must be a valid node and not a special value. Unsafe for single entry + * trees. + * + */ static inline void *mas_next(struct ma_state *mas, unsigned long max) { - unsigned long piv; + unsigned long index = 0; - return _mas_next(mas, max, &piv); + return _mas_next(mas, max, &index); } +EXPORT_SYMBOL_GPL(mas_next); static inline int mas_coalesce_node(struct ma_state *mas, unsigned char end, unsigned char coalesce, bool replace) @@ -3377,14 +3438,17 @@ ascend: } /* - * Private: Returns true if mas->node is a leaf - * + * Private + * __mas_walk(): Locates a value and sets the mas->node and slot accordingly. + * range_min and range_max are set to the range which the entry is valid. + * Returns true if mas->node is a leaf. * * Will not point to a skip entry. * May point to a deleted or retry entry. * */ -static inline bool __mas_walk(struct ma_state *mas) +static inline bool __mas_walk(struct ma_state *mas, unsigned long *range_min, + unsigned long *range_max) { enum maple_type type; struct maple_enode *next; @@ -3449,11 +3513,19 @@ skip_entry: } done: mas_set_slot(mas, i); + *range_max = max; + *range_min = min; return ret; } - -static inline bool _mas_walk(struct ma_state *mas) +/** Private + * _mas_range_walk(): A walk that supports returning the range in which an + * index is located. + * + */ +static inline bool _mas_range_walk(struct ma_state *mas, + unsigned long *range_min, unsigned long *range_max) { + void *entry = mas_start(mas); if (entry) @@ -3468,7 +3540,14 @@ static inline bool _mas_walk(struct ma_state *mas) return true; mas_set_slot(mas, 0); - return __mas_walk(mas); + return __mas_walk(mas, range_min, range_max); +} + +static inline bool _mas_walk(struct ma_state *mas) +{ + unsigned long range_max, range_min; + + return _mas_range_walk(mas, &range_min, &range_max); } /* Private @@ -3489,20 +3568,6 @@ static inline int mas_safe_slot(struct ma_state *mas, unsigned char *slot, } return false; } - -static inline bool mas_searchable(struct ma_state *mas) -{ - if (!mas->node) - return false; - - if (mas_is_none(mas)) - return false; - - if (mas_is_ptr(mas)) - return false; - - return true; -} static inline int mas_dead_node(struct ma_state *mas, unsigned long index) { if (!mas_searchable(mas)) @@ -3527,52 +3592,15 @@ static inline int mas_dead_node(struct ma_state *mas, unsigned long index) */ void *mas_find(struct ma_state *mas, unsigned long max) { + unsigned long index = 0; void *entry = NULL; - unsigned long range_end; - unsigned char slot = 0; - unsigned char start_index = mas->index; - bool mas_start = false; - if (!mas_searchable(mas)) - goto not_found; + entry = _mas_next(mas, max, &index); - - if (mas_is_start(mas)) { - mas_start = true; - } - _mas_walk(mas); -retry: - if (mas_start) { - if (mas_is_ptr(mas) && !mas->index) - entry = mas->tree->ma_root; - - if (mas_is_none(mas)) - goto not_found; - - slot = mas_get_slot(mas); - if (slot != MAPLE_NODE_SLOTS) { - entry = mte_get_rcu_slot(mas->node, slot); - range_end = mas_get_safe_pivot(mas, slot); - } - } - - if (mt_is_empty(entry)) { - entry = _mas_next(mas, max, &range_end); - } - - if (mas_dead_node(mas, start_index)) - goto retry; - - if (entry) { - mas->index = range_end + 1; - mas->last = mas->index; - } + if (entry) + mas->index = index; return entry; - -not_found: - mas->node = MAS_NONE; - return NULL; } EXPORT_SYMBOL_GPL(mas_find); @@ -3584,15 +3612,21 @@ EXPORT_SYMBOL_GPL(mas_find); * on an entry. Those users should call this function before they drop * the lock. It resets the @mas to be suitable for the next iteration * of the loop after the user has reacquired the lock. If most entries - * found during a walk require you to call xas_pause(), the xa_for_each() + * found during a walk require you to call mas_pause(), the mt_for_each() * iterator may be more appropriate. * */ void mas_pause(struct ma_state *mas) { + // Overflow protection. + if (mas->last == ULONG_MAX) { + mas->node = MAS_NONE; + return; + } + mas_reset(mas); - mas->index = mas->last + 1; mas->last++; + mas->index = mas->last; } EXPORT_SYMBOL_GPL(mas_pause); @@ -3601,82 +3635,27 @@ EXPORT_SYMBOL_GPL(mas_pause); * Note: Does not return the zero entry. * returns an entry. */ -void *mt_find(struct maple_tree *mt, unsigned long start, - unsigned long max) +void *mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max, + bool start) { - MA_STATE(mas, mt, start, start); - unsigned char slot; + unsigned long range_start = 0; void *entry = NULL; + MA_STATE(mas, mt, *index, *index); rcu_read_lock(); - do { - mas.index = start; + if (!start) _mas_walk(&mas); - if (mas_is_none(&mas)) - goto done; - - if (mas_is_ptr(&mas)) { - if (!start) - entry = mas.tree->ma_root; - goto done; - } - - slot = mas_get_slot(&mas); - if (slot != MAPLE_NODE_SLOTS) - entry = mte_get_rcu_slot(mas.node, slot); - - if (xa_is_zero(entry)) - entry = NULL; - - if (mt_is_empty(entry)) - entry = mas_next(&mas, max); - } while (mas_dead_node(&mas, start)); + if (start) + entry = _mas_next(&mas, max, &range_start); -done: + if (entry) + *index = mas.last + 1; rcu_read_unlock(); - return entry; -} -EXPORT_SYMBOL(mt_find); - -/* mt_find_after() - Search up from the entry of index until an entry is - * found. - * - * Modifies index and last to point to the newly found range. - */ -void *mt_find_after(struct maple_tree *mt, unsigned long *index, - unsigned long max) -{ - MA_STATE(mas, mt, *index, *index); - unsigned char slot; - void *entry = NULL; - - rcu_read_lock(); - _mas_walk(&mas); - if (mas_is_none(&mas)) - goto done; - - if (mas_is_ptr(&mas)) - goto done; -retry: - mas_set_slot(&mas, mas_get_slot(&mas) + 1); - mas_next(&mas, max); - if (mas_is_none(&mas)) - goto done; - - slot = mas_get_slot(&mas); - entry = mte_get_rcu_slot(mas.node, slot); - if (xa_is_zero(entry)) - goto retry; - - *index = mas_get_safe_pivot(&mas, slot); -done: - rcu_read_unlock(); return entry; - } -EXPORT_SYMBOL(mt_find_after); +EXPORT_SYMBOL(mt_find); static inline void ma_inactive_insert(struct ma_state *mas, void *entry); static inline int mas_replace_tree(struct ma_state *mas, void *new_entry) @@ -4100,14 +4079,16 @@ no_gap: * Find where ms->index is located and return the entry. * mas->node will point to the node containing the entry. * + * range_min and range_max will be set accordingly. * */ -void *mas_load(struct ma_state *mas) +void *mas_range_load(struct ma_state *mas, unsigned long *range_min, + unsigned long *range_max) { void *entry = NULL; retry: - if (_mas_walk(mas)) { + if (_mas_range_walk(mas, range_min, range_max)) { unsigned char slot = MAPLE_NODE_SLOTS; if (mas_is_ptr(mas) && mas->last == 0) @@ -4120,7 +4101,6 @@ retry: entry = mte_get_rcu_slot(mas->node, slot); if (mte_dead_node(mas->node)) goto retry; - } if (mas_is_none(mas)) @@ -4135,6 +4115,11 @@ retry: return entry; } +void *mas_load(struct ma_state *mas) +{ + unsigned long range_max, range_min; + return mas_range_load(mas, &range_min, &range_max); +} static inline bool mas_rewind_node(struct ma_state *mas) { unsigned char slot; @@ -4424,7 +4409,7 @@ void mtree_destroy(struct maple_tree *mt) EXPORT_SYMBOL(mtree_destroy); -#ifdef MT_DEBUG +#ifdef CONFIG_DEBUG_MAPLE_TREE void mt_dump_node(void *entry, unsigned long min, unsigned long max, unsigned int depth); void mt_dump_range(unsigned long min, unsigned long max, unsigned int depth) @@ -4603,10 +4588,9 @@ unsigned long mt_get_alloc_size(void) // Tree validations -/** Private - * - * Calculate the maximum gap in a leaf and check if that's what is reported in - * the parent. +/** + * Calculate the maximum gap in a node and check if that's what is reported in + * the parent (unless root). */ void mas_validate_gaps(struct ma_state *mas) { @@ -4664,6 +4648,9 @@ counted: != max_gap); } +/** + * Validate all pivots are within mas->min and mas->max. + */ void mas_validate_limits(struct ma_state *mas) { if (mte_is_root(mas->node)) @@ -4708,6 +4695,11 @@ static inline void mas_dfs_postorder(struct ma_state *mas, unsigned long max) mas->max = p_max; mas->min = p_min; } +/** + * validate a maple tree by checking: + * 1. The limits (pivots are within mas->min to mas->max) + * 2. The gap is correctly set in the parents + */ void mt_validate(struct maple_tree *mt) { MA_STATE(mas, mt, 0, 0); diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index f7dc5208ebf6..e1790a9f5f81 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -446,11 +446,9 @@ static noinline void check_find(struct maple_tree *mt) if (!val) val = 1; - if (val == 256) { - mas_pause(&mas); - mas_unlock(&mas); - mas_lock(&mas); - } + mas_pause(&mas); + mas_unlock(&mas); + mas_lock(&mas); } mas_unlock(&mas); @@ -466,6 +464,32 @@ static noinline void check_find(struct maple_tree *mt) val = 1; } + // Range check.. + // Insert ULONG_MAX + MT_BUG_ON(mt, mtree_insert_index(mt, ULONG_MAX, GFP_KERNEL)); + + val = 0; + mas_set(&mas, 0); + mas_reset(&mas); + mas_lock(&mas); + mas_for_each(&mas, entry, ULONG_MAX) { + if (val == 64) + MT_BUG_ON(mt, entry != XA_ZERO_ENTRY); + else if (val == 4398046511104) + MT_BUG_ON(mt, entry != xa_mk_value(ULONG_MAX & LONG_MAX)); + else + MT_BUG_ON(mt, xa_mk_value(val) != entry); + val <<= 2; + + // For zero check. + if (!val) + val = 1; + mas_pause(&mas); + mas_unlock(&mas); + mas_lock(&mas); + } + mas_unlock(&mas); + mtree_destroy(mt); } @@ -647,6 +671,7 @@ static noinline void check_erase_testset(struct maple_tree *mt) erase_check_load(mt, i); } + mt_set_non_kernel(1); erase_check_erase(mt, 13); //6012 for (int i = 0; i < 25; i++) { @@ -1040,25 +1065,24 @@ static noinline void check_ranges(struct maple_tree *mt) static noinline void check_next_entry(struct maple_tree *mt) { -// void *entry = NULL; - unsigned long limit = 30, i = 1; + void *entry = NULL; + unsigned long limit = 30, i = 0; MT_BUG_ON(mt, !mtree_empty(mt)); -// MA_STATE(mas, mt, i, i); + MA_STATE(mas, mt, i, i); check_seq(mt, limit, false); rcu_read_lock(); -#if 0 - for (;i >= limit; i++) { - //mas_next_entry - MT_BUG_ON(mt, entry != i(void*)); - i++; + + for (;i <= limit + 1; i++) { + entry = mas_next(&mas, limit); + if (i > limit) + MT_BUG_ON(mt, entry != NULL); + else + MT_BUG_ON(mt, xa_mk_value(i) != entry); + mas.index = mas.max = i; } - BUG_ON(i != limit); - mas -#endif rcu_read_unlock(); mtree_destroy(mt); - } static noinline void check_prev_entry(struct maple_tree *mt) @@ -1085,11 +1109,6 @@ static int maple_tree_seed(void) mtree_init(&tree, 0); check_new_node(&tree); - mtree_init(&tree, 0); - check_next_entry(&tree); - - mtree_init(&tree, 0); - check_prev_entry(&tree); /* Test ranges (store and insert) */ mtree_init(&tree, 0); @@ -1222,9 +1241,15 @@ static int maple_tree_seed(void) check_upper_bound_split(&tree); check_mid_split(&tree); + mtree_init(&tree, 0); + check_next_entry(&tree); check_find(&tree); check_find_2(&tree); + + mtree_init(&tree, 0); + check_prev_entry(&tree); + rcu_barrier(); pr_info("maple_tree: %u of %u tests passed\n", tests_passed, tests_run); diff --git a/tools/testing/radix-tree/ma_xa_benchmark.c b/tools/testing/radix-tree/ma_xa_benchmark.c index 2a6ce73d9ee1..f6218898cebb 100644 --- a/tools/testing/radix-tree/ma_xa_benchmark.c +++ b/tools/testing/radix-tree/ma_xa_benchmark.c @@ -4,7 +4,7 @@ * Copyright (c) 2019 Liam R. Howlett */ -#define MT_DEBUG +#define CONFIG_DEBUG_MAPLE_TREE #define XA_DEBUG #include "test.h" #include diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 224717d7cbb7..f4a05b4dfe44 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -4,7 +4,7 @@ * Copyright (c) 2018 Liam R. Howlett */ -#define MT_DEBUG +#define CONFIG_DEBUG_MAPLE_TREE #include "test.h" #define module_init(x) @@ -14,7 +14,7 @@ #define dump_stack() assert(0) #include "../../../lib/maple_tree.c" -#undef MT_DEBUG +#undef CONFIG_DEBUG_MAPLE_TREE #include "../../../lib/test_maple_tree.c" void farmer_tests(void) -- 2.50.1