From e7518804d9f936ac5b5cbdae68cdee79e8cc849d Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Fri, 29 Nov 2024 17:15:53 -0500 Subject: [PATCH] maple_tree: Add skipping slot support Allow maple node state to jump entire slots when necessary. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 53 ++++++++++++++++++++++++++++++------------------ 1 file changed, 33 insertions(+), 20 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index b20dc3931160..96b58ce48570 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3175,6 +3175,7 @@ struct ma_node_part { void *slots[3]; unsigned long gaps[2]; bool unfinished; + unsigned char skip; }; struct ma_node_state { @@ -3189,35 +3190,37 @@ struct ma_node_state { unsigned char insert; enum maple_type type; unsigned char end; + bool alloc; }; static inline void mns_node_part_leaf_init(struct ma_node_part *ma_part, - struct ma_wr_state *wr_mas) + struct ma_wr_state *wr_mas, struct ma_node_state *src) { ma_part->pos = 0; ma_part->size = 0; - //printk("%s: %lx - %lx store %lx - %lx\n", __func__, - // wr_mas->r_min, wr_mas->r_max, - // wr_mas->mas->index, wr_mas->mas->last); + //printk("%s: %lx - %lx store %lx - %lx\n", __func__, wr_mas->r_min, wr_mas->r_max, wr_mas->mas->index, wr_mas->mas->last); if (wr_mas->r_min < wr_mas->mas->index) { ma_part->pivots[0] = wr_mas->mas->index - 1; ma_part->slots[0] = wr_mas->content; ma_part->size++; + //printk("r_min remains\n"); } ma_part->pivots[ma_part->size] = wr_mas->mas->last; ma_part->slots[ma_part->size] = wr_mas->entry; ma_part->size++; - if (wr_mas->r_max > wr_mas->mas->last) { - ma_part->pivots[ma_part->size] = wr_mas->r_max; - ma_part->slots[ma_part->size] = wr_mas->content; + if (wr_mas->end_piv > wr_mas->mas->last) { + ma_part->pivots[ma_part->size] = wr_mas->end_piv; + ma_part->slots[ma_part->size] = src->slots[wr_mas->offset_end]; ma_part->size++; + //printk("r_max remains\n"); } ma_part->unfinished = false; ma_part->dst_max_off = 255; + ma_part->skip = wr_mas->offset_end - wr_mas->mas->offset + 1; } static inline @@ -3236,6 +3239,7 @@ void mns_node_part_init(struct ma_node_part *ma_part, ma_part->size = 2; ma_part->unfinished = false; ma_part->dst_max_off = 255; + ma_part->skip = 1; } static inline @@ -3498,7 +3502,7 @@ static inline unsigned char mas_wr_new_end(struct ma_wr_state *wr_mas) static inline void mas_wr_converged(struct ma_node_state *src, struct ma_node_state *dst, struct ma_node_part *ma_part, - struct ma_state *mas, unsigned int skip) + struct ma_state *mas) { mns_node_init(dst, mas_pop_node(mas), src->type); @@ -3506,7 +3510,7 @@ static inline void mas_wr_converged(struct ma_node_state *src, mns_cp(src, dst, mas->offset); mns_insert_part(ma_part, dst); - src->offset += skip; + src->offset += ma_part->skip; if (src->offset <= mas->end) mns_cp(src, dst, mas->end - src->offset + 1); @@ -3565,7 +3569,8 @@ static inline void mns_in_left(struct ma_node_state *src, mns_cp(src, left, mas->offset); mns_insert_part(ma_part, left); - src->offset++; + src->offset+= ma_part->skip; + //printk("\t\tsrc L offset adjusted to %u\n", src->offset); if (left->offset <= split) mns_cp(src, left, split - left->offset + 1); @@ -3592,7 +3597,8 @@ static inline void mns_in_right(struct ma_node_state *src, mns_cp(src, right, cp); mns_insert_part(ma_part, right); - src->offset++; + src->offset+= ma_part->skip; + //printk("\t\tsrc offset adjusted to %u\n", src->offset); if (src->offset <= mas->end) mns_cp(src, right, mas->end - src->offset + 1); } @@ -3677,7 +3683,8 @@ static void mas_wr_rebalance_nodes( ma_part->dst_max_off = split; mns_insert_part(ma_part, left); - l_src->offset++; + l_src->offset+= ma_part->skip; + //printk("%d\n", __LINE__); if (left->offset <= split) mns_cp(l_src, left, split - left->offset + 1); @@ -3697,8 +3704,9 @@ static void mas_wr_rebalance_nodes( r_end + new_end + 1, ma_part); right->min = left->max + 1; mns_cp(l_src, right, mas_off - l_src->offset); - l_src->offset++; mns_insert_part(ma_part, right); + //printk("%d\n", __LINE__); + l_src->offset+= ma_part->skip; if (l_end >= l_src->offset) mns_cp(l_src, right, l_end - l_src->offset + 1); } @@ -3714,7 +3722,8 @@ static void mas_wr_rebalance_nodes( right->min = left->max + 1; mns_cp(r_src, right, mas_off); mns_insert_part(ma_part, right); - r_src->offset++; + //printk("%d\n", __LINE__); + r_src->offset+= ma_part->skip; if (r_src->offset <= r_end) mns_cp(r_src, right, r_end - r_src->offset + 1); @@ -3728,7 +3737,8 @@ static void mas_wr_rebalance_nodes( mns_cp(r_src, left, mas_off); ma_part->dst_max_off = split; mns_insert_part(ma_part, left); - r_src->offset++; + //printk("%d\n", __LINE__); + r_src->offset+= ma_part->skip; if (r_src->offset < r_split) mns_cp(r_src, left, r_split - r_src->offset); @@ -3747,7 +3757,8 @@ static void mas_wr_rebalance_nodes( if (mas_off > r_src->offset) mns_cp(r_src, right, mas_off - r_src->offset); mns_insert_part(ma_part, right); - r_src->offset++; + //printk("%d\n", __LINE__); + r_src->offset+= ma_part->skip; } if (r_src->offset <= r_end) @@ -3849,7 +3860,8 @@ try_right: mas->end = p_end; mas->offset = p_off; mns_node_part_init(ma_part, left, right); - mas_wr_converged(&parent, &new_parent, ma_part, mas, /* skip = */ 2); + ma_part->skip = 2; + mas_wr_converged(&parent, &new_parent, ma_part, mas); src->enode = parent.enode; mas->node = new_parent.enode; return true; @@ -3876,18 +3888,19 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) trace_ma_op(__func__, mas); + //printk("\t\t%s\n", __func__); //mt_dump(mas->tree, mt_dump_hex); height = mas_mt_height(mas); /* FIXME: Save this? */ total = mas_wr_new_end(wr_mas); split = (total + 1) / 2; mas->depth = height; - mns_node_part_leaf_init(&ma_part, wr_mas); /* First split the leaves */ mns_node_init(&left, mas_pop_node(mas), wr_mas->type); mns_node_init(&right, mas_pop_node(mas), wr_mas->type); mns_mas_init(&src, mas); + mns_node_part_leaf_init(&ma_part, wr_mas, &src); src.max = mas->max; src.min = mas->min; @@ -3933,7 +3946,7 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) if ((height > 1) && (mas_wr_try_rebalance(mas, &src, mas->end + 1, &left, &right, &ma_part))) - goto rebalanced; + goto rebalanced; left.min = src.min; right.max = src.max; @@ -3955,7 +3968,7 @@ new_root: mas->end = 0; mas_set_height(mas); converged: - mas_wr_converged(&src, &parent, &ma_part, mas, /* skip = */ 1); + mas_wr_converged(&src, &parent, &ma_part, mas); mas->node = parent.enode; rebalanced: mas_wmb_replace(mas, src.enode); -- 2.49.0