From ed42f2322d67b9d2beb81c9741b3f8709a09d703 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 24 Aug 2020 15:22:20 -0400 Subject: [PATCH] maple_tree: Fix dup tree walk up and add more testcases. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 41 +++++++++++++++++++++++------------------ lib/test_maple_tree.c | 35 ++++++++++++++++++++++++++++++++++- 2 files changed, 57 insertions(+), 19 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 2ad26104f18f..0d15a5cc99fa 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4314,14 +4314,15 @@ static inline void mas_dfs_preorder(struct ma_state *mas) return; } - if (mte_is_leaf(mas->node) && mte_is_root(mas->node)) { - mas->node = MAS_NONE; - return; - } + if (mte_is_leaf(mas->node) && mte_is_root(mas->node)) + goto done; walk_up: if (mte_is_leaf(mas->node) || (slot >= mt_slot_count(mas->node))) { + if (mte_is_root(mas->node)) + goto done; + slot = mte_parent_slot(mas->node) + 1; mas->node = mt_mk_node(mte_parent(mas->node), mas_parent_enum(mas, mas->node)); @@ -4331,9 +4332,8 @@ walk_up: prev = mas->node; mas->node = mas_get_rcu_slot(mas, slot); if (!mas->node) { - mas->node = MAS_NONE; if (mte_is_root(prev)) - return; + goto done; mas->node = prev; slot = mte_parent_slot(mas->node) + 1; @@ -4343,15 +4343,16 @@ walk_up: } return; +done: + mas->node = MAS_NONE; } static inline struct maple_enode *mas_dup_node(struct ma_state *oldmas, struct ma_state *mas) { - struct maple_enode *enode= mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), - mte_node_type(oldmas->node)); - memcpy(mte_to_node(enode), mas_mn(oldmas), sizeof(struct maple_node)); - return enode; + struct maple_node *node= mas_next_alloc(mas); + memcpy(node, mas_mn(oldmas), sizeof(struct maple_node)); + return mt_mk_node(node, mte_node_type(oldmas->node)); } static inline void mas_dup_alloc(struct ma_state *mas, int *node_cnt) { @@ -4417,9 +4418,12 @@ static inline void mas_dup_tree_start(struct ma_state *oldmas, if (mas_is_start(oldmas)) // get the root. mas_dfs_preorder(oldmas); - *node_cnt = mas_data_end(oldmas) + 1; - *node_cnt *= 1 << (4 * (oldmas->tree->ma_height - 2)); // assume all other levels full. - (*node_cnt)++; + *node_cnt = 1; + + if (!mte_is_leaf(oldmas->node)) { + *node_cnt += mas_data_end(oldmas) + 1; + *node_cnt *= 1 << (4 * (oldmas->tree->ma_height - 2)); // assume all other levels full. + } mas_dup_alloc(mas, node_cnt); if (mas_is_err(mas)) @@ -4428,15 +4432,18 @@ static inline void mas_dup_tree_start(struct ma_state *oldmas, allocated: mas->node = mas_dup_node(oldmas, mas); - mas_dup_children(mas, node_cnt); - mas_adopt_children(mas, mas->node); mte_to_node(mas->node)->parent = ma_parent_ptr( ((unsigned long)mas->tree | MA_ROOT_PARENT)); rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); + if (!mte_is_leaf(oldmas->node)) { + mas_dup_children(mas, node_cnt); + mas_adopt_children(mas, mas->node); + } } void _mas_dup_tree(struct ma_state *oldmas, struct ma_state *mas, int *node_cnt) { if (!xa_is_node(oldmas->tree->ma_root)) { + // A pointer. mas->tree->ma_root = oldmas->tree->ma_root; return; } @@ -4467,14 +4474,12 @@ retry_dup_children: mas_adopt_children(mas, mas->node); } - mas_nomem(mas, GFP_KERNEL); - } void mas_dup_tree(struct ma_state *oldmas, struct ma_state *mas) { int node_cnt = 0; - if (!oldmas->tree->ma_root) // empty tree. + if (!oldmas->tree->ma_root) return; mtree_lock(mas->tree); diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 327660914d67..73f4f44dd7fa 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -32088,12 +32088,44 @@ static void check_dfs_preorder(struct maple_tree *mt) static void check_dup_tree(struct maple_tree *oldmt) { - unsigned long i, max = 10000; + unsigned long i, max = 10; MA_STATE(oldmas, oldmt, 0, 0); DEFINE_MTREE(mt); MA_STATE(mas, &mt, 0, 0); + mas_dup_tree(&oldmas, &mas); + + check_seq(oldmt, max, false); + mas_dup_tree(&oldmas, &mas); + for (i = 0; i <= max; i++) + check_index_load(&mt, i); + + check_load(&mt, max + 1, NULL); + + mtree_destroy(&mt); + mtree_destroy(oldmt); + + + max = 254; + mas_reset(&mas); + mas_reset(&oldmas); + mtree_init(oldmt, 0); + mtree_init(&mt, 0); + check_seq(oldmt, max, false); + mas_dup_tree(&oldmas, &mas); + for (i = 0; i <= max; i++) + check_index_load(&mt, i); + + check_load(&mt, max + 1, NULL); + mtree_destroy(&mt); + mtree_destroy(oldmt); + + max = 5000; // for depth of 3 on 256 nodes. + mas_reset(&mas); + mas_reset(&oldmas); + mtree_init(oldmt, 0); + mtree_init(&mt, 0); check_seq(oldmt, max, false); mas_dup_tree(&oldmas, &mas); for (i = 0; i <= max; i++) @@ -32102,6 +32134,7 @@ static void check_dup_tree(struct maple_tree *oldmt) check_load(&mt, max + 1, NULL); mtree_destroy(&mt); } + static DEFINE_MTREE(tree); static int maple_tree_seed(void) -- 2.50.1