From 3591f0a37fd58b3d948e8f94b44db3dd26fa1e96 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Sun, 5 Jan 2020 04:50:01 -0500 Subject: [PATCH] maple_tree: WIP, fixes mas_rebalance pivot promotion to avoid adding to non-leafs, fixes end detection in corner case, still hosed at 584531 Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 285 ++++++++++++++++++++++++++++++++++++++---- lib/test_maple_tree.c | 2 + 2 files changed, 263 insertions(+), 24 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index ed6663a0e7f4..e322eb707405 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -877,7 +877,7 @@ static inline struct maple_node *mas_next_alloc(struct ma_state *ms) return NULL; cnt = mas_get_alloc_cnt(ms); - printk("%s: TAKE %d\n", __func__, cnt); +// printk("%s: TAKE %d\n", __func__, cnt); mn = mas_get_alloc(ms); if (cnt == 1) { ms->alloc = NULL; @@ -901,10 +901,10 @@ static inline void mas_push_node(struct ma_state *mas, struct maple_enode *used) struct maple_node *node = mas_get_alloc(mas); int cnt; - printk("%s: PUSH %p\n", __func__, used); +// printk("%s: PUSH %p\n", __func__, used); memset(reuse, 0, sizeof(*reuse)); cnt = mas_get_alloc_cnt(mas); - printk("%s: cnt %d\n", __func__, cnt); +// printk("%s: cnt %d\n", __func__, cnt); if (cnt == 0) { mas->alloc = reuse; } else if (cnt <= 15) { @@ -918,7 +918,7 @@ static inline void mas_push_node(struct ma_state *mas, struct maple_enode *used) smn->slot[cnt % 15] = reuse; } cnt = mas_get_alloc_cnt(mas); - printk("%s: cnt %d\n", __func__, cnt); +// printk("%s: cnt %d\n", __func__, cnt); BUG_ON(!mas_get_alloc_cnt(mas)); } @@ -1114,7 +1114,7 @@ static inline unsigned char mas_data_end(const struct ma_state *mas, entry = _mte_get_rcu_slot(mn, slot, type); if (mt_will_coalesce(entry)) { - if (piv == prev_piv) { + if (piv == prev_piv || !slot) { (*coalesce)++; } //counted_null = true; @@ -1153,8 +1153,6 @@ static inline int ma_hard_data(unsigned long end, return end - coalesce; } -#define mas_do_split mas_ma_cp - static inline struct maple_node *mas_switch_nodes(struct ma_state *cp, struct ma_state *left, struct ma_state *right, unsigned long piv) @@ -1287,8 +1285,10 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas, attempt_insert = true; - split = mas_cp_calc_split(mas, mas_type, append); - printk("Using split of %d\n", split); + if (right) { + split = mas_cp_calc_split(mas, mas_type, append); + printk("Using split of %d\n", split); + } if (left) { mas_dup_state(&cp, left); @@ -1373,9 +1373,8 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas, printk("Written piv %lu\n", written_piv); if (written_piv == cp.index - 1) i = 1; // previous pivot matches exactly. - else if (!src_slot && written_piv == cp.index) { + else if (!src_slot && written_piv == cp.index) i = 1; // mas->min matches exactly. - } printk("piv2 %lu <= last %lu\n", piv[2], cp.last); if (appending) @@ -1403,12 +1402,14 @@ static inline unsigned char mas_ma_cp(struct ma_state *mas, wmb = true; if (mt_is_empty(loop_entry)) { - if (null_run) { + if (null_run) slot--; - } + null_run = true; - } else + } else { null_run = false; + } + mas_ma_cp_store(mn, mn_type, slot, piv[i], loop_entry, wmb); @@ -1445,6 +1446,8 @@ skip_src_slot: if (right && update_gaps) parent->ma64.gap[p_slot] = max_gap; + else + ret = src_slot - 1; printk("Done\n"); return ret; @@ -1780,6 +1783,7 @@ void mte_destroy_walk(struct maple_enode *mn) mte_free(mn); } + static inline unsigned long _mas_copy(struct ma_state *mas, struct ma_cp *cp, unsigned long min) { @@ -1809,6 +1813,7 @@ static inline unsigned long _mas_copy(struct ma_state *mas, struct ma_cp *cp, dloc <= cp->dst_end) { void *entry; + printk("%u to %u\n", sloc, dloc); if (prev_piv >= mas->max) break; @@ -1857,12 +1862,15 @@ static inline unsigned long _mas_copy(struct ma_state *mas, struct ma_cp *cp, if (sloc && piv == prev_piv) goto next_src_slot; - if (dloc < pivot_cnt) + if (dloc < pivot_cnt) { + printk("piv %p[%u] -> %lu\n", cp->dst, dloc, piv); mte_set_pivot(cp->dst, dloc, piv); + } if (dtype == maple_arange_64) mte_cp_gap(cp->dst, dloc, cp->src, sloc); + printk("%p[%u] -> %p[%u]\n", cp->src, sloc, cp->dst, dloc); mte_cp_rcu_slot(cp->dst, dloc++, cp->src, sloc); prev_piv = piv; next_src_slot: @@ -2312,8 +2320,6 @@ static inline int _mas_add_slot_cnt(struct ma_state *mas, printk("End is now %d\n", end); req_slots = req_slots + end - coalesce; - if (mas->index != min) - req_slots++; printk("req slots %d\n", req_slots); @@ -2324,6 +2330,7 @@ static inline int _mas_add_slot_cnt(struct ma_state *mas, if (!last_entry) // nothing at the last slot. return req_slots; + printk("req slots returned as %d\n", req_slots+1); return req_slots + 1; } static inline int __mas_add(struct ma_state *mas, void *entry, @@ -2392,6 +2399,7 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, unsigned char slot_cnt = mt_slots[this_type] - 1; struct maple_enode *prev_enode = NULL; void *contents = NULL; + bool append = false; int ret = 0; @@ -2440,7 +2448,7 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, } printk("Adding %lu-%lu\n", mas->index, mas->last); - new_end = _mas_add_slot_cnt(mas, slot, min, max); + new_end = _mas_add_slot_cnt(mas, slot, min, max) - coalesce; mt_dump(mas->tree); printk("%s: %p new_end %u slot_cnt %u\n", __func__, mas_mn(mas), new_end, slot_cnt); @@ -2468,7 +2476,11 @@ static inline int _mas_add(struct ma_state *mas, void *entry, bool overwrite, } prev_enode = mas->node; printk("slot %u old_end %u\n", slot, old_end); - __mas_add(mas, entry, old_end, active, slot > old_end); + if (slot > old_end && !coalesce) + append = true; + // FIXME: append (slot > old_end) may cause coalescing which wouldn't + // be + __mas_add(mas, entry, old_end, active, append); complete: @@ -3193,6 +3205,223 @@ static inline void mas_coalesce_empty(struct ma_state *mas, * */ static inline void mas_coalesce(struct ma_state *mas); +#if 0 +static inline int mas_rebalance(struct ma_state *mas, unsigned char end, + unsigned char coalesce) +{ + struct maple_enode *r_enode, *this_enode = mas->node; + unsigned long ret = 0; + unsigned char this_p_slot, r_p_slot; // Parent slots (this one and right) + unsigned char all_slots; // Total slots needed for this and right node. + unsigned char l_slot_cnt, r_slot_cnt; // left and right slot counts + unsigned long l_piv, r_piv = 0; // left and right pivots + unsigned char r_end, r_coalesce; // right node end and values that can be coalesced. + unsigned char node_cnt = 0; // Number of nodes to allocate + unsigned char r_take; + enum maple_type new_type; + bool p_coalesce = false; // coalesce parent. + bool l_null_end = false, r_null_start = false; + struct maple_node new_node; + struct ma_state *src = mas; + int i = 0; + + MA_STATE(p_state, mas->tree, mas->index, mas->last); + MA_STATE(r_state, mas->tree, mas->index, mas->last); + MA_STATE(cp_state, mas->tree, mas->index, mas->last); + MA_CP(cp, this_enode, NULL, 0, end); + + + printk("%s: %p\n", __func__, mas_mn(mas)); + mt_dump(mas->tree); + l_slot_cnt = ma_hard_data(end, coalesce); + if (mte_is_root(this_enode)) + return mas_coalesce_node(mas, end, coalesce, true); + + this_p_slot = mte_parent_slot(this_enode); + mas_dup_state(&p_state, mas); // set the parent node, etc. + mas_encoded_parent(&p_state); // Actually make it the parent. + + // Get the next entry. + mas_set_slot(&p_state, this_p_slot + 1); + if (!mas_next_nentry(&p_state, ULONG_MAX, &r_piv)) { + // this_enode is the right-most node of the parent. + // Reset parent info. + mas_dup_state(&p_state, mas); + mas_encoded_parent(&p_state); + 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 + mas_descend(&p_state); + end = mas_data_end(&p_state, + mte_node_type(p_state.node), &l_piv, &coalesce); + return mas_rebalance(&p_state, end, coalesce); + } + // 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)); + } + mas_coalesce(&p_state); + if (mas_is_err(&p_state)) { + mas->node = p_state.node; + return 0; + } + return 1; + } + + // If we reached here, then the node to the right exists. + // set the ma_state information and save a copy for this slot. + mas_dup_state(&r_state, &p_state); + mas_descend(&r_state); + r_enode = r_state.node; + + 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); + 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); + l_piv = r_state.max; + goto right_empty; + } + // Add 1 for each slot 0. + all_slots = r_slot_cnt + 2 + l_slot_cnt; + r_take = r_slot_cnt; + node_cnt = 1; + if (all_slots > mt_slot_count(this_enode) - 1) { + node_cnt++; + r_take = mt_slot_count(this_enode) / 2; + } + + if (r_take > r_slot_cnt) + r_take = r_slot_cnt; + + printk("%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 { // FIXME: What about non-end nodes? + 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; + } + + + if (end < coalesce) { // Left is empty, just copy right. + l_slot_cnt = -1; + ret = r_slot_cnt; + goto left_empty; + } + + mas_node_cnt(mas, node_cnt); + if (mas_is_err(mas)) + return 0; + printk("%d: nodes %u\n", __LINE__, node_cnt); + + mas_dup_state(&cp_state, mas); + // for each entry from right to copy, + cp_state.index = r_state.min; + cp_state.node = mt_mk_node(mas_next_alloc(mas), + mte_node_type(this_enode)); + + + l_slot_cnt = end; + + for (i = 0; i <= r_take; i++) { + // set cp_state->index, cp_state->last, entry + void *entry = mte_get_rcu_slot(r_enode, i); + if (!entry || mt_will_coalesce(entry)) { + cp_state.index = mte_get_pivot(r_enode, i)+1; + continue; + } + cp_state.last = mte_get_pivot(r_enode, i); + // copy node on first run, append after. + // + // call mas_ma_cp(&cp_state, 0, &l_state, type, l_slot_cnt + 1?, + // entry, i == 0 ? false : true) + printk("\tma_cp with %lu-%lu -> %p\n", cp_state.index, cp_state.last, + entry); + l_slot_cnt = mas_ma_cp(mas, 0, &cp_state, NULL, NULL, + mte_node_type(this_enode), l_slot_cnt, entry, + i == 0 ? false : true); + cp_state.index = cp_state.last + 1; + cp_state.max = cp_state.last; // update cp state max. + cp.src_start = i; + } + // if right isn't fully consumed + // mas_copy to new right. + // + + mte_to_node(cp_state.node)->parent = mte_to_node(this_enode)->parent; + mas->node = cp_state.node; + printk("mas node is %p\n", mas_mn(mas)); + new_type = mte_node_type(cp_state.node); + mas_replace(mas); + mas->max = cp_state.max; + ret = l_slot_cnt; + mte_set_pivot(p_state.node, this_p_slot, mas->max); + +right_empty: + printk("Right empty goto\n"); + if (node_cnt < 2) { + printk("Right is empty, skip\n"); + // 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); + 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; + } +left_empty: + + cp.src = r_state.node; + cp.src_end = r_end; + cp.dst = NULL; + cp.dst_start = l_slot_cnt + 1; + cp.dst_end = r_end; + printk("Copy %p to ?[%u-%u]\n", cp.src, cp.dst_start, cp.dst_end); + 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_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_state.max); + + +right_done: + // Set the parent slots to l_piv for all skip slots.. + while (r_p_slot-- > this_p_slot) + mte_set_pivot(p_state.node, r_p_slot, l_piv); + + /* If there is a freed node, then mas->node must point to the parent + * which contained the freed node so it can also be checked for + * coalescing. + */ + if (p_coalesce) + mas_coalesce(&p_state); + return ret; +} +#else static inline int mas_rebalance(struct ma_state *mas, unsigned char end, unsigned char coalesce) { @@ -3212,6 +3441,7 @@ static inline int mas_rebalance(struct ma_state *mas, unsigned char end, MA_STATE(r_state, mas->tree, mas->index, mas->last); MA_CP(cp, this_enode, NULL, 0, end); + printk("%s: %p\n", __func__, mas_mn(mas)); l_slot_cnt = ma_hard_data(end, coalesce); if (mte_is_root(this_enode)) return mas_coalesce_node(mas, end, coalesce, true); @@ -3274,7 +3504,7 @@ 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); + printk("%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; @@ -3297,6 +3527,7 @@ static inline int mas_rebalance(struct ma_state *mas, unsigned char end, // Coalesce this_enode into a new node. cp.dst_end = l_slot_cnt; + printk("%d Copy %p[%u-%u] to %p[%u-%u]\n", __LINE__, mas_mn(mas), cp.src_start, cp.src_end, "??", cp.dst_start, cp.dst_end); mas_copy(mas, &cp); // cp.dst now has coalesced this_enode. @@ -3333,8 +3564,11 @@ static inline int mas_rebalance(struct ma_state *mas, unsigned char end, mas->node = cp.dst; mas_replace(mas); mas->max = r_state.max; - mas_data_end(mas, mte_node_type(mas->node), &l_piv, &coalesce); - mas->max = l_piv; + if (all_slots > mt_slots[new_type] - 1) { + mas_data_end(mas, mte_node_type(mas->node), &l_piv, &coalesce); + mas->max = l_piv; + } + l_piv = mas->max; ret = mt_slot_count(mas->node) - cp.dst_start + 1; mte_set_pivot(p_state.node, this_p_slot, l_piv); @@ -3382,6 +3616,7 @@ right_done: mas_coalesce(&p_state); return ret; } +#endif /** Private * @@ -3497,8 +3732,10 @@ start: 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)) + if (mas_rebalance(mas, end, coalesce)) { + mt_dump(mas->tree); goto done; + } if (mas_is_err(mas)) { if (h_data >= 1) @@ -3525,7 +3762,7 @@ start: goto check_start; if (end <= coalesce) { - printk("%d empty\n", __LINE__); + printk("%d empty %p\n", __LINE__, mas_mn(mas)); mas_coalesce_empty(mas, eparent, p_slot, p_type); check_parent = true; } diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 81a86e6e6b87..e59f7d6ea9d8 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -862,6 +862,8 @@ static noinline void check_erase_testset(struct maple_tree *mt) } mt_set_non_kernel(35); for (int i = 0; i < 18; i++) { + mt_dump(mt); + printk("\tCheck erase of %lu\n", set[i]); erase_check_erase(mt, i); for (int j = 0; j < ARRAY_SIZE(set); j++) { if (j < 18 && j > i) -- 2.50.1