From 52872b7f37732ca1bdd3ca3102937b3b49cc6ca2 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 2 Jan 2020 16:07:02 -0500 Subject: [PATCH] maple_tree: WIP, still hosed.. Pass: 583922 Run:583923 Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 143 +++++++++++++----------------------------- lib/test_maple_tree.c | 19 ------ 2 files changed, 42 insertions(+), 120 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index b2fc76e678bf..18fbebaf3038 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1100,7 +1100,6 @@ static inline unsigned char mas_data_end(const struct ma_state *mas, } printk("data end with counted nulls %p\n", mas_mn(mas)); printk("%u %u %u\n", slot, (*coalesce), counted_null); - mt_dump(mas->tree); (*coalesce) = (*coalesce) - counted_null + 1; slot -= counted_null; } @@ -2023,7 +2022,6 @@ static inline int mas_split(struct ma_state *mas, unsigned char slot, MA_STATE(right , mas->tree, mas->index, mas->last); type = mte_node_type(mas->node); - //mt_dump(mas->tree); if (mte_is_root(mas->node)) { old_parent = full; if (mt_is_alloc(mas->tree)) @@ -2050,7 +2048,6 @@ static inline int mas_split(struct ma_state *mas, unsigned char slot, if (mas_is_err(mas)) return 0; - //mt_dump(mas->tree); mas_dup_state(&parent, mas); if (split < p_slot) p_slot -= split; @@ -2249,7 +2246,6 @@ static inline int _mas_add_slot_cnt(struct ma_state *mas, void *last_entry; int req_slots = 0; - mt_dump(mas->tree); end = mas_data_end(mas, mte_node_type(mas->node), &last_piv, &coalesce); printk("end of %p %u %u %lu\n", mas_mn(mas), end, coalesce, last_piv); @@ -2371,7 +2367,6 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, int ret = 0; - printk("here\n"); if (ma_is_dense(this_type)) { ret = _mas_add_dense(mas, entry, slot, this_type, overwrite, active); @@ -2384,8 +2379,6 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, if (slot > slot_cnt) // search returned MAPLE_NODE_SLOTS slot = old_end + 1; - printk("Using %p[%u]\n", mas_mn(mas), slot); - _mas_get_range(mas, slot, &min, &max); if (slot <= old_end) @@ -2393,8 +2386,6 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, // Check early failures. if (!overwrite) { - printk("check early failures? %lu > %lu and !contents %s\n", - mas->last, max, !contents ? "yes" : "no"); if (mas->last > max) { // spans range. mas_set_err(mas, -ERANGE); return 0; @@ -2404,7 +2395,6 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, return 0; } } - printk("do the add\n"); // At this point, the we can perform the add. @@ -3052,14 +3042,11 @@ static inline void* _mas_prev(struct ma_state *mas, unsigned long limit) unsigned long max = mas->max; unsigned char slot; - printk("Starting at %p\n", mas->node); while(!mas_is_none(mas)) { if (mas_prev_nentry(mas, limit, &max)) break; - printk("going to prev node\n"); mas_prev_node(mas, limit); - printk("here %p\n", mas->node); mas_set_slot(mas, mt_slot_count(mas->node) - 1); } @@ -3148,55 +3135,10 @@ static inline void mas_coalesce_pivots(struct ma_state *mas, int slot, } } - -static inline int mas_update_empty_pivots(struct ma_state *mas, - unsigned char p_slot) -{ - unsigned long piv; - unsigned char coalesce, old_end, slot; - enum maple_type type = mte_node_type(mas->node); - - MA_STATE(prev, mas->tree, mas->index, mas->last); - - mas_dup_state(&prev, mas); - printk("Looking for prev val of %p[%u]\n", mas_mn(&prev), - mas_get_slot(&prev)); - if (mte_is_root(prev.node)) { - mas_prev_nentry(mas, 0, &piv); - } else { - mas_set_slot(&prev, p_slot); - mas_encoded_parent(&prev); - mas_prev_node(&prev, 0); - } - printk("Found in node %p[%u]\n", mas_mn(&prev), mas_get_slot(&prev)); - if (mas_is_none(&prev)) - return 1; - - old_end = mas_data_end(&prev, type, &piv, &coalesce); - if (old_end >= mt_pivots[type]) - return 1; // setting the pivot would cause incorrect data. - - printk("old end is %u\n", old_end); - if (!mte_get_rcu_slot(prev.node, old_end)) { // ends in NULL - mte_set_pivot(prev.node, old_end, mas->max); - printk("%s: Setting %p[%u] to %lu\n", __func__, mas_mn(&prev), - old_end, mas->max); - } - - // do while.. - p_slot = mte_parent_slot(prev.node); - mas_encoded_parent(&prev); - printk("%s: Setting %p[%u] to %lu\n", __func__, mas_mn(&prev), - p_slot, mas->max); - mte_set_pivot(prev.node, p_slot, mas->max); - return 0; -} - static inline void mas_coalesce_empty(struct ma_state *mas, struct maple_enode *eparent, unsigned char p_slot, enum maple_type p_type) { - printk("Coalesce empty\n"); mte_set_rcu_slot(eparent, p_slot, XA_SKIP_ENTRY); mas_set_slot(mas, p_slot); mas_coalesce_pivots(mas, p_slot, p_type, true); @@ -3258,7 +3200,6 @@ static inline int mas_rebalance(struct ma_state *mas, unsigned char end, mas_set_slot(&p_state, this_p_slot); if (mas_prev_nentry(&p_state, 0, &r_piv)) { // If there is a node to the left, rebalance the left - //mt_dump(p_state.tree); mas_descend(&p_state); end = mas_data_end(&p_state, mte_node_type(p_state.node), &l_piv, &coalesce); @@ -3267,6 +3208,7 @@ static inline int mas_rebalance(struct ma_state *mas, unsigned char end, // No left or right, rebalance the parent. // But first, remove this entry if it's empty. if (end < coalesce) { + printk("%d empty\n", __LINE__); mas_coalesce_empty(&p_state, p_state.node, this_p_slot, mte_node_type(p_state.node)); } @@ -3286,7 +3228,9 @@ static inline int mas_rebalance(struct ma_state *mas, unsigned char end, r_end = mas_data_end(&r_state, mte_node_type(r_enode), &l_piv, &r_coalesce); r_slot_cnt = ma_hard_data(r_end, r_coalesce); - if (r_end < r_coalesce) { + printk("r_slot_cnt %u\n", r_slot_cnt); + if (r_end < r_coalesce && r_state.max != ULONG_MAX) { + printk("skip entry?\n"); // This node needs to be a skip entry. all_slots = l_slot_cnt; new_type = mte_node_type(this_enode); @@ -3300,22 +3244,38 @@ static inline int mas_rebalance(struct ma_state *mas, unsigned char end, if (all_slots > mt_slot_count(this_enode) - 1) node_cnt++; + printk("here %d l_slot_cnt %d\n", __LINE__, l_slot_cnt); + // check if left ends in NULL + if (l_slot_cnt && !mte_get_rcu_slot(this_enode, l_slot_cnt)) + l_null_end = true; + + printk("r_end and r_coalesce %u %u\n", r_end, r_coalesce); + if ((r_end == r_coalesce) && l_null_end) { // no space needed.. + printk("ends in null at %p[%u] => %ld\n", this_enode, l_slot_cnt, r_state.max); + mte_set_pivot(this_enode, l_slot_cnt, r_state.max); + do { + mas_encoded_parent(mas); + mte_set_pivot(mas->node, this_p_slot, r_state.max); + this_p_slot = mte_parent_slot(mas->node); + } while (!mte_is_root(mas->node)); + return 0; + } mas_node_cnt(mas, node_cnt); if (mas_is_err(mas)) return 0; + printk("here %d\n", __LINE__); // Coalesce this_enode into a new node. cp.dst_end = l_slot_cnt; mas_copy(mas, &cp); // cp.dst now has coalesced this_enode. - // check if left ends in NULL, right start in NULL.. - if (!mte_get_rcu_slot(cp.dst, cp.dst_start - 1)) - l_null_end = true; + // check if right start in NULL.. if (mt_will_coalesce(mte_get_rcu_slot(r_enode, 0)) || - !mte_get_rcu_slot(r_enode, 0)) + !mte_get_rcu_slot(r_enode, 0)) r_null_start = true; + printk("r first is %p\n", mte_get_rcu_slot(r_enode, 0)); if (l_null_end && r_null_start) { all_slots--; @@ -3334,42 +3294,34 @@ static inline int mas_rebalance(struct ma_state *mas, unsigned char end, cp.src_end = r_end; else cp.dst_end = (all_slots + 1)/ 2; // Take 1/2 the entries. - printk("Copy %p[%u-%u] to %p[%u-%u]\n", mas_mn(&r_state), cp.src_start, - cp.src_end, mte_to_node(cp.dst), cp.dst_start, cp.dst_end); + printk("Copy %p[%u-%u] to %p[%u-%u]\n", mas_mn(&r_state), cp.src_start, cp.src_end, mte_to_node(cp.dst), cp.dst_start, cp.dst_end); - printk("min of %lu or %lu\n", mte_get_pivot(cp.dst, cp.dst_start-1), - r_state.min); _mas_copy(&r_state, &cp, - mte_get_pivot(cp.dst, cp.dst_start-1)); // cp.dst is now complete, place it in the tree. + mte_get_pivot(cp.dst, cp.dst_start-1)); // cp.dst is now complete, place it in the tree. mte_to_node(cp.dst)->parent = mte_to_node(this_enode)->parent; - printk("%p == %p\n", this_enode, mas->node); new_type = mte_node_type(cp.dst); - printk("Replace %p with %p\n", mas_mn(mas), mte_to_node(cp.dst)); mas->node = cp.dst; mas_replace(mas); - mt_dump(mas->tree); - l_piv = mas_get_safe_pivot(mas, cp.dst_start - 1); + mas->max = r_state.max; + mas_data_end(mas, mte_node_type(mas->node), &l_piv, &coalesce); + mas->max = l_piv; ret = mt_slot_count(mas->node) - cp.dst_start + 1; mte_set_pivot(p_state.node, this_p_slot, l_piv); right_empty: if (all_slots <= mt_slots[new_type] - 1) { - printk("right consumed %p\n", mas_mn(&r_state)); // Right was entirely consumed. void *entry = XA_SKIP_ENTRY; ret = mt_slots[new_type] - all_slots; if (!ret) ret = 1; + r_p_slot = mte_parent_slot(r_enode); - printk("Zero %p[%u] (%u)\n", mas_mn(&p_state), r_p_slot, - mt_pivot_count(mas->node)); - if (r_p_slot < mt_pivot_count(mas->node)) { - if (!mas_update_empty_pivots(&r_state, r_p_slot)) { - mte_set_rcu_slot(p_state.node, r_p_slot, entry); - mte_free(r_enode); - } - } + mte_set_rcu_slot(p_state.node, r_p_slot, entry); + if (r_p_slot < mt_pivot_count(mas->node)) + mte_set_pivot(p_state.node, r_p_slot, l_piv); + mte_free(r_enode); p_coalesce = true; goto right_done; } @@ -3381,11 +3333,10 @@ right_empty: mas_copy(&r_state, &cp); // cp.dst is coalesced remainder of r_enode. mte_to_node(cp.dst)->parent = mte_to_node(r_enode)->parent; r_state.node = cp.dst; - r_piv = mas_get_safe_pivot(&r_state, cp.dst_start - 1); r_p_slot = mte_parent_slot(r_enode); mas_replace(&r_state); - if (r_p_slot < mt_pivot_count(p_state.node)-1) - mte_set_pivot(p_state.node, r_p_slot, r_piv); + if (r_p_slot < mt_pivot_count(p_state.node) - 1) + mte_set_pivot(p_state.node, r_p_slot, r_state.max); right_done: @@ -3399,7 +3350,6 @@ right_done: */ if (p_coalesce) mas_coalesce(&p_state); - //mt_dump(mas->tree); return ret; } @@ -3516,22 +3466,22 @@ start: /* If there is any space to save, try to reallocate */ h_data = ma_hard_data(end, coalesce); if (h_data < mt_min_slots[this_type] - 1) { + printk("rebalance?\n"); if (mas_rebalance(mas, end, coalesce)) goto done; if (mas_is_err(mas)) { if (h_data >= 1) return; - + if (mas->max == ULONG_MAX) + return; // Single entry and allocation failed, free this_enode + printk("failure path?\n"); mas->node = this_enode; mas_encoded_parent(mas); - printk("here?\n"); - if (mas_update_empty_pivots(mas, p_slot)) - return; - mas_coalesce_empty(mas, eparent, p_slot, p_type); check_parent = true; + mas->node = this_enode; goto done; } } @@ -3545,12 +3495,9 @@ start: goto check_start; if (end <= coalesce) { - printk("here??\n"); - if (mas_update_empty_pivots(mas, p_slot)) - return; + printk("%d empty\n", __LINE__); mas_coalesce_empty(mas, eparent, p_slot, p_type); check_parent = true; - goto done; } // Check if next node starts with null. @@ -3576,8 +3523,6 @@ start: if (!slot) { // Empty node... - if (mas_update_empty_pivots(mas, p_slot)) - return; mas_coalesce_empty(mas, eparent, p_slot, p_type); check_parent = true; piv = mas->min; @@ -4238,11 +4183,9 @@ skip_r_count: mas_for_each(&l_mas, entry, mas->index - 1) { new_mas.index = l_mas.index; new_mas.last = l_mas.index; - printk("Insert %lu->%lu\n", new_mas.index, new_mas.last); ma_inactive_insert(&new_mas, entry); if (mas_is_err(&new_mas)) BUG_ON(1); - //mt_dump(new_mas.tree); } // Insert the new value. @@ -4400,7 +4343,6 @@ static inline int mas_add(struct ma_state *mas, void *entry, bool overwrite, } /* Do the add */ - printk("Adding to %p[%u]\n", mas_mn(mas), slot); ret = _mas_add(mas, entry, overwrite, active); if (mas_is_err(mas) && xa_err(mas->node) == -ERANGE) mas_set_err(mas, -EEXIST); @@ -4825,7 +4767,6 @@ int mtree_insert_range(struct maple_tree *mt, unsigned long first, mtree_lock(ms.tree); retry: - printk("Add %lu\n", first); mas_add(&ms, entry, false, true); if (mas_nomem(&ms, gfp)) goto retry; diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index c15c484372f4..b0790bb9bdf0 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -735,11 +735,9 @@ static noinline void check_erase_testset(struct maple_tree *mt) // Coalesce testing - printk("here we go %d\n", __LINE__); erase_check_insert(mt, 0); erase_check_insert(mt, 2); - printk("here we go %d\n", __LINE__); for (int i = 5; i < 25; i++) { erase_check_insert(mt, i); for (int j = i; j >= 0; j--) { @@ -747,7 +745,6 @@ static noinline void check_erase_testset(struct maple_tree *mt) } } - printk("here we go %d\n", __LINE__); erase_check_erase(mt, 14); //6015 for (int i = 0; i < 25; i++) { if (i == 14) @@ -755,7 +752,6 @@ static noinline void check_erase_testset(struct maple_tree *mt) else erase_check_load(mt, i); } - printk("here we go %d\n", __LINE__); erase_check_erase(mt, 16); //7002 for (int i = 0; i < 25; i++) { if (i == 16 || i == 14) @@ -764,7 +760,6 @@ static noinline void check_erase_testset(struct maple_tree *mt) erase_check_load(mt, i); } - printk("here we go %d\n", __LINE__); mt_set_non_kernel(1); erase_check_erase(mt, 13); //6012 @@ -774,7 +769,6 @@ static noinline void check_erase_testset(struct maple_tree *mt) else erase_check_load(mt, i); } - printk("here we go %d\n", __LINE__); erase_check_erase(mt, 15); //7003 for (int i = 0; i < 25; i++) { @@ -784,7 +778,6 @@ static noinline void check_erase_testset(struct maple_tree *mt) erase_check_load(mt, i); } - printk("here we go %d\n", __LINE__); mt_set_non_kernel(2); erase_check_erase(mt, 17); //7008 *should* cause coalesce. for (int i = 0; i < 25; i++) { @@ -793,7 +786,6 @@ static noinline void check_erase_testset(struct maple_tree *mt) else erase_check_load(mt, i); } - printk("here we go %d\n", __LINE__); erase_check_erase(mt, 18); //7012 for (int i = 0; i < 25; i++) { @@ -803,7 +795,6 @@ static noinline void check_erase_testset(struct maple_tree *mt) erase_check_load(mt, i); } - printk("here we go %d\n", __LINE__); mt_set_non_kernel(2); erase_check_erase(mt, 19); //7015 for (int i = 0; i < 25; i++) { @@ -813,7 +804,6 @@ static noinline void check_erase_testset(struct maple_tree *mt) erase_check_load(mt, i); } - printk("here we go %d\n", __LINE__); erase_check_erase(mt, 20); //8003 for (int i = 0; i < 25; i++) { if (i <= 20 && i >= 13) @@ -822,7 +812,6 @@ static noinline void check_erase_testset(struct maple_tree *mt) erase_check_load(mt, i); } - printk("here we go %d\n", __LINE__); mt_set_non_kernel(2); erase_check_erase(mt, 21); //8002 for (int i = 0; i < 25; i++) { @@ -832,7 +821,6 @@ static noinline void check_erase_testset(struct maple_tree *mt) erase_check_load(mt, i); } - printk("here we go %d\n", __LINE__); mt_set_non_kernel(1); erase_check_erase(mt, 22); //8008 for (int i = 0; i < 25; i++) { @@ -843,7 +831,6 @@ static noinline void check_erase_testset(struct maple_tree *mt) } for (int i = 23; i < 25; i++) { erase_check_erase(mt, i); - mt_dump(mt); } for (int i = 0; i < 25; i++) { if (i <= 25 && i >= 13) @@ -851,19 +838,14 @@ static noinline void check_erase_testset(struct maple_tree *mt) else erase_check_load(mt, i); } - mt_dump(mt); - printk("here we go %d\n", __LINE__); // Shrinking tree test. // for (int i = 13; i < ARRAY_SIZE(set); i++) { - mt_dump(mt); - printk("Insert %ld\n", set[i]); erase_check_insert(mt, i); } - printk("here we go %d\n", __LINE__); mt_set_non_kernel(99); for (int i = 18; i < ARRAY_SIZE(set); i++) { erase_check_erase(mt, i); @@ -875,7 +857,6 @@ static noinline void check_erase_testset(struct maple_tree *mt) } } mt_set_non_kernel(35); - printk("here we go %d\n", __LINE__); for (int i = 0; i < 18; i++) { erase_check_erase(mt, i); for (int j = 0; j < ARRAY_SIZE(set); j++) { -- 2.50.1