From 092bf68e227e6ecbab449c448d12d0d11166067a Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 28 Sep 2020 16:07:21 -0400 Subject: [PATCH] maple_tree: Drop dup_tree() Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 179 ------------------------------------------ lib/test_maple_tree.c | 111 +++++++------------------- 2 files changed, 27 insertions(+), 263 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index e1f9b358a903..c6dd92c9c6c4 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4348,185 +4348,6 @@ done: mas->node = MAS_NONE; } -static inline struct maple_enode *mas_dup_node(struct ma_state *oldmas, - struct ma_state *mas) -{ - 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) -{ - - int alloc_cnt = min(*node_cnt, MA_MAX_ALLOC); - /* Allocate nodes for new tree. Maximum will be 16 ** height */ - *node_cnt -= alloc_cnt; - mas_node_cnt(mas, alloc_cnt); - if (mas_is_err(mas)) - return; -} - -void mas_dup_pause(struct ma_state *mas) -{ - mas->span_enode = mas->node; -} - -bool mas_dup_is_paused(struct ma_state *mas) -{ - if (mas->span_enode) - return true; - return false; -} - -void mas_dup_resume(struct ma_state *mas) -{ - mas->node = mas->span_enode; - mas->span_enode = NULL; -} - -static inline void mas_dup_children(struct ma_state *mas, int *node_cnt) -{ - struct maple_node *child; - struct maple_enode *oldchild, *echild; - unsigned char offset, end = mt_slot_count(mas->node); - int allocated = mas_alloc_cnt(mas); - void **slots = ma_slots(mte_to_node(mas->node), - mte_node_type(mas->node)); - - if (allocated < end) { - mas_dup_pause(mas); - *node_cnt += allocated; - mas_dup_alloc(mas, node_cnt); - if (mas_is_err(mas)) - return; - - mas_dup_resume(mas); - } - - for(offset = 0; offset < end; offset++) { - oldchild = slots[offset]; - if (!oldchild) - return; - - child = mas_next_alloc(mas); - echild = mt_mk_node(child, mte_node_type(oldchild)); - slots[offset] = echild; - memcpy(child, mte_to_node(oldchild), sizeof(struct maple_node)); - } -} - -static inline bool mas_dup_advance(struct ma_state *oldmas, - struct ma_state *mas) -{ - mas_dfs_preorder(oldmas); - mas_dfs_preorder(mas); - - if (mas_is_none(oldmas)) - return false; - - return true; -} - -static inline void mas_dup_tree_start(struct ma_state *oldmas, - struct ma_state *mas, - int *node_cnt) -{ - if (xa_is_node(mas->tree->ma_root)) - goto dup_children; - - if (mas->alloc) - goto allocated; - - // Get first node (root) - if (mas_is_start(oldmas)) // get the root. - mas_dfs_preorder(oldmas); - - *node_cnt = 1; - - if (!mte_is_leaf(oldmas->node)) { - *node_cnt += mas_data_end(oldmas) + 1; - *node_cnt *= 1 << (4 * (mas_mt_height(oldmas) - 2)); // assume all other levels full. - } - - mas_dup_alloc(mas, node_cnt); - if (mas_is_err(mas)) - return; - -allocated: - mas->tree->ma_flags = oldmas->tree->ma_flags; - - mas->node = mas_dup_node(oldmas, mas); - 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)); - -dup_children: - if (!mte_is_leaf(oldmas->node)) { - mas_dup_children(mas, node_cnt); - if (mas_is_err(mas)) - return; - - 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; - } - - if (mas_dup_is_paused(mas)) { - mas_dup_resume(mas); - goto continue_dup; - } - - if (mas_is_start(mas)) - mas_dup_tree_start(oldmas, mas, node_cnt); - - if (mas_is_err(mas)) - return; - - if (mte_is_leaf(oldmas->node)) - return; - - while(mas_dup_advance(oldmas, mas)) { - if (mte_is_leaf(oldmas->node)) - continue; - -continue_dup: - mas_dup_children(mas, node_cnt); - if (mas_is_err(mas)) - return; - - mas_adopt_children(mas, mas->node); - } -} - -void mas_dup_tree(struct ma_state *oldmas, struct ma_state *mas) -{ - int node_cnt = 0; - - if (!oldmas->tree->ma_root) - return; - - mtree_lock(mas->tree); -retry: - _mas_dup_tree(oldmas, mas, &node_cnt); - if (mas_nomem(mas, GFP_KERNEL)) - goto retry; - - mtree_unlock(mas->tree); -} - -void mas_dup_store(struct ma_state *mas, void *entry) { - mas_next(mas, ULONG_MAX); - mte_set_slot(mas->node, mas_offset(mas), entry); -} - static inline unsigned char mas_dead_leaves(struct ma_state *mas, void **slots) { struct maple_node *node; diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index c83017e2ca3b..915f1841e2e2 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -32428,87 +32428,40 @@ static void check_dfs_preorder(struct maple_tree *mt) MT_BUG_ON(mt, count != 72); } -static void check_dup_tree(struct maple_tree *oldmt) +static noinline void check_forking(struct maple_tree *mt) { - 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); + struct maple_tree newmt; + int i, max = 300000, count = 1000000; + void *val; + MA_STATE(mas, mt, 0, 0); + MA_STATE(newmas, mt, 0, 0); +// for (i = max; i > 0; i-=10) + for (i = 0; i < max; i+=10) + mtree_store_range(mt, i, i + 5, xa_mk_value(i), GFP_KERNEL); - for (max = 257; max > 0; max--) { + for (i = 0; i < count; i++) { + mt_set_non_kernel(99999); + mtree_init(&newmt, MAPLE_ALLOC_RANGE); + newmas.tree = &newmt; + mas_reset(&newmas); 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++) - check_index_load(&mt, i); - - check_load(&mt, max + 1, NULL); - mas_reset(&mas); - for (i = 0; i <= max; i++) - mas_dup_store(&mas, xa_mk_value(i+100)); - - for (i = 0; i <= max; i++) - check_load(&mt, i, xa_mk_value(i+100)); - - mtree_destroy(&mt); -} - -static void jitters(struct maple_tree *mt) -{ - unsigned long i, max = 300; - - for (i = max; i > 0; i--) { - mtree_test_store_range(mt, i*10, i*10 + 9, xa_mk_value(i*10)); - } - - i = 272; - mtree_test_store_range(mt, i*10 + 4, i*10 + 9, NULL); - i = 274; - mtree_test_store_range(mt, i*10, i*10 + 9, NULL); - i = 273; - max = 10000000; - while(max--) { - mtree_test_store_range(mt, i*10, i*10 + 12, xa_mk_value(i*10)); - mtree_test_store_range(mt, i*10+10, i*10 + 12, NULL); + mas_lock(&mas); + mas_for_each(&mas, val, ULONG_MAX) { + newmas.index = mas.index; + newmas.last = mas.last; + mas_store(&newmas, val); + } + mas_empty_alloc(&newmas); + mas_unlock(&mas); +// mt_validate(&newmt); + mt_set_non_kernel(0); + mtree_destroy(&newmt); } - return; } - static DEFINE_MTREE(tree); - static int maple_tree_seed(void) { unsigned long set[] = {5015, 5014, 5017, 25, 1000, @@ -32517,13 +32470,10 @@ static int maple_tree_seed(void) void *ptr = &set; pr_info("\nTEST STARTING\n\n"); -// goto skip1; -#if 1 +#if 0 mtree_init(&tree, MAPLE_ALLOC_RANGE); - jitters(&tree); + check_forking(&tree); mtree_destroy(&tree); - - goto skip; #endif @@ -32535,16 +32485,11 @@ static int maple_tree_seed(void) check_dfs_preorder(&tree); mtree_destroy(&tree); - mtree_init(&tree, 0); - check_dup_tree(&tree); - mtree_destroy(&tree); - /* Test ranges (store and insert) */ mtree_init(&tree, 0); check_ranges(&tree); mtree_destroy(&tree); -skip1: mtree_init(&tree, MAPLE_ALLOC_RANGE); check_alloc_range(&tree); mtree_destroy(&tree); @@ -32608,11 +32553,9 @@ skip1: /* Clear out the tree */ mtree_destroy(&tree); -//skip: mtree_init(&tree, 0); check_erase_testset(&tree); mtree_destroy(&tree); -// exit(0); mtree_init(&tree, 0); /* -- 2.50.1