From ba27886de11c7fb643963484e47ba7d2763e54c3 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Wed, 24 Jun 2020 21:40:53 -0400 Subject: [PATCH] wip: maple_tree: factor out descend and node adoption Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 175 +++++++++++++++++++++++++---------------------- 1 file changed, 93 insertions(+), 82 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 53a3b740bab0..f2e6a1c2b31f 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1489,41 +1489,43 @@ struct maple_clean_list { struct list_head list; }; -static bool mas_check_split_parent(struct ma_state *mas, unsigned char slot, - struct ma_state *child_mas) +static inline struct maple_enode *mas_check_split_parent(struct ma_state *mas, + unsigned char slot) { void *entry = mas_get_rcu_slot(mas, slot); if (!entry) - return false; + return NULL; printk("parent of entry %u is %p\n", slot, mte_parent(entry)); if (mte_parent(entry) != mas_mn(mas)) - return false; + return NULL; - mas_set_slot(child_mas, slot); - return true; + return entry; } -static inline void mas_find_l_split(struct ma_state *mas, struct ma_state *l_mas) +static inline struct maple_enode *mas_find_l_split(struct ma_state *mas) { unsigned char i, end = mas_data_end(mas); + struct maple_enode *en; + for (i = 0; i <= end; i++) { printk("%s: Checking %p[%i]\n", __func__, mas_mn(mas), i); - if (mas_check_split_parent(mas, i, l_mas)) - return; + if ((en = mas_check_split_parent(mas, i))) + return en; } - l_mas->node = MAS_NONE; + return NULL; } -static inline void mas_find_r_split(struct ma_state *mas, struct ma_state *r_mas) +static inline struct maple_enode *mas_find_r_split(struct ma_state *mas) { unsigned char i = mas_data_end(mas); + struct maple_enode *en; + do { - if (mas_check_split_parent(mas, i, r_mas)) - return; - } while (i--); - r_mas->node = MAS_NONE; + en = mas_check_split_parent(mas, i); + } while (!en && i--); + return en; } static inline void mab_shift_right(struct maple_big_node *b_node, @@ -1549,13 +1551,13 @@ static inline int mab_calc_split(struct maple_big_node *b_node, int size, split = (size + 1) / 3; } - printk("Guessing leaf split of %u (size is %d)\n", split, size); + //printk("Guessing leaf split of %u (size is %d)\n", split, size); /* Avoid ending a node in NULL and avoid having a range less than the * slot count */ while (((b_node->pivot[split] - min) < slot_cnt) && split < slot_cnt) { - printk("Skipping ahead due to min span\n"); + //printk("Skipping ahead due to min span\n"); split++; } @@ -1565,7 +1567,7 @@ static inline int mab_calc_split(struct maple_big_node *b_node, int size, else split--; } - printk("Setting split (leaf split) to %u\n", split); + //printk("Setting split (leaf split) to %u\n", split); return split; } @@ -1633,7 +1635,61 @@ static inline unsigned long mas_next_node(struct ma_state *mas, unsigned long max); static inline void mas_prev_node(struct ma_state *mas, unsigned long limit); -static inline int mas_commit_rebalance(struct ma_state *mas, +static inline void mas_descend_adopt(struct ma_state *mas) +{ + struct maple_enode *l_enode, *r_enode; + + MA_STATE(l_mas, mas->tree, mas->index, mas->last); + MA_STATE(r_mas, mas->tree, mas->index, mas->last); + + mas_dup_state(&l_mas, mas); + mas_dup_state(&r_mas, mas); + + /* The new nodes have the correct parent set, so follow the child with + * the correct parent on each split. If there is no child with the + * correct parent, then the other side of the split will have two + * children with the correct parent. Once the new children are found, + * then set the correct parent in all of of the parent's children. + */ + while (!mte_is_leaf(l_mas.node)) { + printk("start of l %p is %p\n", mas_mn(&l_mas), l_mas.node); + printk("start of r %p is %p\n", mas_mn(&r_mas), r_mas.node); + if (!(l_enode = mas_find_l_split(&l_mas))) { + printk("\tChecking right\n"); + mas_adopt_children(&l_mas, l_mas.node); + mas_dup_state(&l_mas, &r_mas); + if (!(l_enode = mas_find_l_split(&l_mas))) { + mas_adopt_children(&r_mas, r_mas.node); + break; + } + } + + printk("%d New node is %p\n", __LINE__, mte_to_node(l_enode)); + + if (!(r_enode = mas_find_r_split(&r_mas))) { + printk("\tChecking left\n"); + mas_adopt_children(&r_mas, r_mas.node); + mas_dup_state(&r_mas, &l_mas); + r_enode = mas_find_r_split(&r_mas); + } + printk("%d New node is %p\n", __LINE__, mte_to_node(r_enode)); + + printk("Adopt children of l %p\n", mas_mn(&l_mas)); + mas_adopt_children(&l_mas, l_mas.node); + if (r_mas.node != l_mas.node) { + printk("Adopt children of r %p\n", mas_mn(&r_mas)); + mas_adopt_children(&r_mas, r_mas.node); + } + l_mas.node = l_enode; + r_mas.node = r_enode; + + printk("%d New node is %p\n", __LINE__, mas_mn(&l_mas)); + printk("%d New node is %p\n", __LINE__, mas_mn(&r_mas)); + printk("\n"); + } +} + +static inline int mas_rebalance(struct ma_state *mas, struct maple_big_node *b_node, unsigned char new_end) { @@ -1830,7 +1886,7 @@ new_root_node: return 0; } -static inline int mas_commit_split(struct ma_state *mas, +static inline int mas_split(struct ma_state *mas, struct maple_big_node *b_node, unsigned char new_end) { @@ -1969,20 +2025,27 @@ static inline int mas_commit_split(struct ma_state *mas, printk("setting parents of %p and %p to %p and %p\n", mas_mn(&orig_l_mas), mas_mn(&orig_r_mas), mas_mn(&l_mas), mas_mn(&r_mas)); - if (p_slot <= split) // prev left side is on left. + if (p_slot <= split) { // prev left side is on left. mte_set_parent(orig_l_mas.node, l_mas.node, p_slot); - else + printk("p_slot of %p is %u\n", orig_l_mas.node, p_slot); + } + else { mte_set_parent(orig_l_mas.node, r_mas.node, - p_slot - split + 1); + p_slot - split - 1); + printk("p_slot of %p is %u\n", orig_l_mas.node, p_slot - split - 1); + } p_slot = mas_get_slot(&orig_r_mas); - if (p_slot <= split) // prev right side is on left. + if (p_slot <= split) {// prev right side is on left. mte_set_parent(orig_r_mas.node, l_mas.node, p_slot); - else + printk("p_slot of %p is %u\n", orig_r_mas.node, p_slot); + } else { mte_set_parent(orig_r_mas.node, r_mas.node, - p_slot - split + 1); + p_slot - split - 1); + printk("p_slot of %p is %u\n", orig_r_mas.node, p_slot - split - 1); + } } i = 0; @@ -2036,63 +2099,11 @@ static inline int mas_commit_split(struct ma_state *mas, // Insert the new data in the tree _mas_replace(mas, false, false, false); - /* The new nodes have the correct parent set, so follow the child with - * the correct parent on each split. If there is no child with the - * correct parent, then the other side of the split will have two - * children with the correct parent. Once the new children are found, - * then set the correct parent in all of of the parent's children. - */ if (mt_is_alloc(mas->tree)) mas_update_gap(mas, false); mt_dump(mas->tree); printk("Start at %p\n", mas_mn(mas)); - mas_dup_state(&orig_l_mas, mas); - mas_dup_state(&orig_r_mas, mas); - mas_dup_state(&l_mas, mas); - mas_dup_state(&r_mas, mas); - while (!mte_is_leaf(orig_l_mas.node)) { - - printk("start of %p is %p\n", mas_mn(&orig_l_mas), l_mas.node); - mas_find_l_split(&orig_l_mas, &l_mas); - if (mas_is_none(&l_mas)) { - printk("Checking right\n"); - mas_dup_state(&l_mas, &r_mas); - mas_adopt_children(&orig_l_mas, orig_l_mas.node); - mas_dup_state(&orig_l_mas, &orig_r_mas); - mas_find_l_split(&orig_l_mas, &l_mas); - } - if (mas_is_none(&l_mas)) { - mas_adopt_children(&orig_r_mas, orig_r_mas.node); - break; - } - - printk("%d New node is at %u\n", __LINE__, mas_get_slot(&l_mas)); - - mas_find_r_split(&orig_r_mas, &r_mas); - if (mas_is_none(&r_mas)) { - printk("Checking left\n"); - mas_dup_state(&r_mas, &l_mas); - mas_adopt_children(&orig_r_mas, orig_r_mas.node); - mas_dup_state(&orig_r_mas, &orig_l_mas); - mas_find_r_split(&orig_r_mas, &r_mas); - } - printk("%d New node is at %u\n", __LINE__, mas_get_slot(&r_mas)); - - printk("Adopt children of %p\n", mas_mn(&orig_l_mas)); - mas_adopt_children(&orig_l_mas, orig_l_mas.node); - if (orig_r_mas.node != orig_l_mas.node) { - printk("Adopt children of %p\n", mas_mn(&orig_l_mas)); - mas_adopt_children(&orig_r_mas, orig_r_mas.node); - } - - mas_descend(&l_mas); - mas_dup_state(&orig_l_mas, &l_mas); - printk("%d New node is %p\n", __LINE__, mas_mn(&l_mas)); - mas_descend(&r_mas); - mas_dup_state(&orig_r_mas, &r_mas); - printk("%d New node is %p\n", __LINE__, mas_mn(&r_mas)); - printk("\n"); - } + mas_descend_adopt(mas); return 1; } @@ -2105,10 +2116,10 @@ static inline int mas_commit_b_node(struct ma_state *mas, printk("Commit\n"); if ((end < mt_min_slot_cnt(mas->node)) && !mte_is_root(mas->node)) { printk("end %u min slot %u\n", end, mt_min_slot_cnt(mas->node)); - return mas_commit_rebalance(mas, b_node, end); + return mas_rebalance(mas, b_node, end); } else if (end >= mt_slot_count(mas->node)) - return mas_commit_split(mas, b_node, end); + return mas_split(mas, b_node, end); mas_node_cnt(mas, 1); if (mas_is_err(mas)) @@ -4893,7 +4904,7 @@ void mas_validate_parent_slot(struct ma_state *mas) } else if (ma_get_rcu_slot(parent, i, p_type, mas->tree) == mas->node) { pr_err("parent contains invalid child at "MA_PTR"[%u] " - MA_PTR"\n", parent, i, mas_mn(mas)); + MA_PTR" p_slot %u\n", parent, i, mas_mn(mas), p_slot); MT_BUG_ON(mas->tree, ma_get_rcu_slot(parent, i, p_type, mas->tree) == mas->node); -- 2.50.1