From a0554420fabc68ada0dfe28f61223149cb0258c7 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 18 Feb 2025 21:45:42 -0500 Subject: [PATCH] progress, I guess Split and reblance testing Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 208 +++++++++++++++++++++++++++++++++++------------ 1 file changed, 156 insertions(+), 52 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 6f6b748657ee..30220efa1f8a 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3201,6 +3201,7 @@ void mni_node_part_init(struct ma_node_part *ma_part, printk("set slot 0 to %p\n", left->enode); ma_part->slots[0] = left->enode; ma_part->pivots[0] = left->max; + printk("pivot 0 is %lu\n", left->max); ma_part->gaps[0] = left->max_gap; ma_part->slots[1] = right->enode; @@ -3453,8 +3454,7 @@ void mni_finalise(struct ma_node_info *p) unsigned long max_gap; unsigned char len; - //printk("%s: offset is %u range %lx - %lx\n", __func__, - // p->offset, p->min, p->max); + printk("%s: offset is %u range %lx - %lx\n", __func__, p->offset, p->min, p->max); len = mt_slots[p->type] - p->offset; //printk("len is %u %u - %u\n", len, mt_slots[p->type], p->offset); @@ -3515,6 +3515,7 @@ void mni_finalise(struct ma_node_info *p) for (; i <= offset; i++) { /* data == no gap. */ + printk("gap check %u\n", i); if (slots[i]) continue; @@ -3633,6 +3634,7 @@ unsigned char mas_wr_rebalance_calc(unsigned char data_size, node_size = mt_slots[mt]; space = node_size * 2 - 2; + printk("space is %u\n", space); /* Greedy rebalance */ if (space <= data_size) return 0; @@ -3651,6 +3653,7 @@ static inline void mas_wr_ascend_init(struct ma_state *mas, struct ma_node_info *ni) { mas_ascend(mas); + ni->enode = mas->node; ni->node = mte_to_node(mas->node); ni->type = mte_node_type(mas->node); _mni_node_init(ni, ni->node, ni->type); @@ -3806,6 +3809,7 @@ void mns_assemble(struct ma_node_state *states, unsigned char len) unsigned long max; struct ma_node_info *last_dst; + printk("\n\n%s %u\n", __func__, len); last_dst = states[0].dst; max = 0; for (i = 0; i < len; i++) { @@ -3816,10 +3820,13 @@ void mns_assemble(struct ma_node_state *states, unsigned char len) unsigned char size; unsigned char piv_overflow = 0; + printk("%d: cp to %p + %u\n", i, ns->dst->node, ns->dst->offset); if (last_dst != ns->dst) { WARN_ON_ONCE(!max); ns->dst->min = max + 1; + printk("Set min %lu\n", ns->dst->min); } + last_dst = ns->dst; d_slots = ns->dst->slots + ns->dst->offset; printk("Store at %p\n", d_slots); @@ -3870,9 +3877,10 @@ void mns_assemble(struct ma_node_state *states, unsigned char len) memcpy(d_gap, s_gap, size * sizeof(unsigned long)); } - if (ns->dst->offset + size >= mt_pivots[ns->dst->type]) + if (ns->dst->offset + size > mt_pivots[ns->dst->type]) { + printk("dst overflow\n"); piv_overflow = 1; - else if (piv_overflow) { /* Source overflow */ + } else if (piv_overflow) { /* Source overflow */ printk("source overflow, set pivot to %lu\n", max); *(d_piv + size - 1) = max; } @@ -3884,6 +3892,7 @@ void mns_assemble(struct ma_node_state *states, unsigned char len) memcpy(d_piv, s_piv, size * sizeof(unsigned long)); ns->dst->max = max; } + printk("\n\n"); } static inline void mas_wr_converged(struct ma_node_info *src, @@ -3960,25 +3969,31 @@ static bool mas_wr_try_rebalance(struct ma_state *mas, tmp_mas = *mas; mas_wr_ascend_init(&tmp_mas, &parent); - //printk("parent %p has end %u %p\n", parent.node, parent.end, parent.slots[parent.end]); + printk("parent %p has end %u %p\n", parent.node, parent.end, parent.slots[parent.end]); max = mt_slots[src->type] - 1; if (ma_is_leaf(src->type)) max--; src->end = mas->end; - if (!parent.insert_off) /* No left sibling */ + if (!parent.insert_off) /* No left sibling */ { + printk("no left, try right\n"); goto try_right; /* There must be a right sibling */ + } /* Check for space in left sibling */ tmp_mas.offset--; mas_descend(&tmp_mas); mni_mas_init(&src2, &tmp_mas); + printk("data size is calculated as %u\n", src2.end + new_end); split = mas_wr_rebalance_calc(src2.end + new_end, src2.type); + printk("Split calc to %u\n", split); + if (split) { parent.insert_off--; /* Left will be src2, right will be src */ left->min = src2.min; right->max = src->max; + printk("left will be rebalanced against this one.\n"); } else { if (parent.end <= parent.insert_off) return false; @@ -3998,6 +4013,7 @@ try_right: /* Left will be src, right will be src2 */ left->min = src->min; right->max = src2.max; + printk("right will be rebalanced against this one.\n"); } /* @@ -4008,6 +4024,7 @@ try_right: if (left_store) { unsigned char space; + printk("left store\n"); /* * Left pushes data right. * Fill left up to split from l_src and ma_part - Func_1 @@ -4026,26 +4043,33 @@ try_right: /* The insert part spans the left and right */ mns_mni_init(&state[i], left, 0, space); if (mns_ends_in_null(&state[i])) { - state[i].size--; - split--; + if (split + space < mt_slots[left->type]) { + state[i].size++; + split++; + } else { + state[i].size--; + split--; + } } space = ma_part->size - state[i].size; i++; - /* - * fill right from ma_part and l_src - Func_1 - */ - state[i].part = ma_part; - state[i].use_part = true; - mns_mni_init(&state[i], right, state[i - 1].size, - space); - i++; + /* + * fill right from ma_part and l_src - Func_1 + */ + if (space) { + state[i].part = ma_part; + state[i].use_part = true; + mns_mni_init(&state[i], right, + state[i - 1].size, space); + i++; + } } if (split > insert_end) { state[i].info = src; mns_mni_init(&state[i], left, insert_end + 1, - split - insert_end + 1); + split - insert_end + 1); if (mns_ends_in_null(&state[i])) { state[i].size--; @@ -4060,52 +4084,115 @@ try_right: state[i].info = &src2; mns_mni_init(&state[i++], right, split + 1, mas->end - split + 1); } else { + printk("right store\n"); /* * Right pushes data left - * Copy left to new left - Func_2 */ state[i].info = &src2; - mns_mni_init(&state[i], left, 0, split); - if (mns_ends_in_null(&state[i])) { - state[i].size--; - split--; - } + mns_mni_init(&state[i], left, 0, src2.end + 1); i++; + printk("outright cp left %p\n", src2.node); + split -= src2.end; + printk("Split is indexed into right now %u vs insert %u\n", split, mas->offset); + if (split < mas->offset) { + printk("Push more into left\n"); + state[i].info = src; + mns_mni_init(&state[i], left, 0, split); + printk("Check null\n"); + if (mns_ends_in_null(&state[i])) { + printk("null split, adjust - 1\n"); + state[i].size++; + split++; + } + i++; + } else { + unsigned char space = split - mas->offset + 1; + + /* split >= mas->offset */ + if (mas->offset) { + printk("Push up to offset into left\n"); + state[i].info = src; + mns_mni_init(&state[i], left, 0, mas->offset); + i++; + } + + if (space < ma_part->size) { + state[i].part = ma_part; + mns_mni_init(&state[i], left, 0, space); + state[i].use_part = true; + if (mns_ends_in_null(&state[i])) { + printk("null split, adjust - 1\n"); + state[i].size--; + split--; + } + i++; + + state[i].part = ma_part; + mns_mni_init(&state[i], right, space, + ma_part->size - space + 1); + state[i++].use_part = true; + space = 0; + } else { + state[i].part = ma_part; + mns_mni_init(&state[i], left, 0, ma_part->size); + state[i++].use_part = true; + space -= ma_part->size; + space++; + } + + if (space) { + state[i].info = src; + mns_mni_init(&state[i], left, insert_end, space); + i++; + } + printk("Copy up to insert, do the insert maybe in two nodes\n"); + } /* * copy from right or ma_part to split to new left - Func_1 * fill right from ma_part and r_src - Func_1 */ - state[i].info = &src2; - mns_mni_init(&state[i++], right, split + 1, - src2.end + 1); - if (mas->offset) { + printk("\tat offset %u and insert is %u\n", split, mas->offset); + if (split < mas->offset) { + printk("cp src from %u to %u\n", split, mas->offset - split); state[i].info = src; - mns_mni_init(&state[i++], right, 0, mas->offset); + mns_mni_init(&state[i++], right, split, mas->offset - split); + printk("insert part\n"); + state[i].part = ma_part; + mns_mni_init(&state[i], right, 0, ma_part->size); + state[i++].use_part = true; } - state[i].part = ma_part; - mns_mni_init(&state[i], right, 0, ma_part->size); - state[i++].use_part = true; if (insert_end > mas->end) { + printk("End bit now\n"); state[i].info = src; mns_mni_init(&state[i++], right, insert_end + 1, mas->end - insert_end + 1); } } + mns_assemble(state, i); mni_finalise(left); mni_finalise(right); + mni_node_part_init(ma_part, left, right); + ma_part->leaf = false; mas_ascend(mas); mas->end = parent.end; mas->offset = parent.insert_off; - mni_node_part_init(ma_part, left, right); ma_part->skip = 2; mas_wr_converged(&parent, &new_parent, ma_part, mas); src->enode = parent.enode; mas->node = new_parent.enode; + printk("Replace %p with %p\n", mas->node, src->enode); + +#if 0 + mas_wmb_replace(mas, src->enode); + mtree_range_walk(mas); + mt_dump(mas->tree, mt_dump_hex); + exit(0); +#endif return true; } @@ -4299,8 +4386,6 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) mns_mas_init(&src, &src_info, mas); mns_node_part_leaf_init(&ma_part, wr_mas, &src_info); total = mas->end + ma_part.size - 1; - split = (total + 1) / 2; - printk("Splitting leaf at %u store at %u\n", split, mas->offset); if (mt_is_alloc(mas->tree)) { right.alloc = left.alloc = true; @@ -4311,6 +4396,8 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) &right, &ma_part, wr_mas->offset_end)) goto rebalanced; + split = (total + 1) / 2; + printk("Splitting leaf at %u store at %u\n", split, mas->offset); left.min = mas->min; right.max = mas->max; if (split >= mas->offset) { @@ -4318,49 +4405,60 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) printk("Store in left\n"); if (mas->offset) { + printk("%d %u\n", __LINE__, i); state[i].info = &src_info; printk("src is info %p\n", src_info.node); mns_mni_init(&state[i++], &left, 0, mas->offset); } + printk("%d %u\n", __LINE__, i); state[i].part = &ma_part; state[i].use_part = true; space = split - mas->offset + 1; if (space >= ma_part.size) { + printk("%d %u\n", __LINE__, i); mns_mni_init(&state[i++], &left, 0, ma_part.size); + space -= ma_part.size; } else { + printk("%d %u\n", __LINE__, i); /* The insert part spans the left and right */ mns_mni_init(&state[i], &left, 0, space); if (mns_ends_in_null(&state[i])) { + printk("%d %u NULL split\n", __LINE__, i); state[i].size--; split--; } space = ma_part.size - state[i].size; i++; + printk("%d %u\n", __LINE__, i); state[i].part = &ma_part; state[i].use_part = true; mns_mni_init(&state[i], &right, state[i - 1].size, space); i++; + space = 0; } - if (split > wr_mas->offset_end) { + if (space) { + printk("%d %u\n", __LINE__, i); state[i].info = &src_info; printk("src is info %p\n", src_info.node); mns_mni_init(&state[i], &left, wr_mas->offset_end + 1, - split - wr_mas->offset_end + 1); + space); if (mns_ends_in_null(&state[i])) { + printk("%d %u NULL split\n", __LINE__, i); state[i - 1].size--; split--; } i++; } + printk("%d %u\n", __LINE__, i); state[i].info = &src_info; printk("src is info %p\n", src_info.node); - mns_mni_init(&state[i++], &right, split + 1, mas->end - split + 1); + mns_mni_init(&state[i++], &right, split + 1, mas->end - split); } else { printk("Store in right\n"); printk("src is info %p\n", src_info.node); @@ -4374,28 +4472,27 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) } i++; - if (mas->offset >= split) { + + if (mas->offset > split) { + printk("right node will get %u - %u\n", split, mas->offset - split); state[i].info = &src_info; - printk("src is info %p\n", src_info.node); mns_mni_init(&state[i++], &right, split, mas->offset - split); + printk("src is info %p\n", src_info.node); } - printk("Store part next 0 - %u\n", ma_part.size - 1); + printk("Store part next 0 + %u\n", ma_part.size); state[i].part = &ma_part; mns_mni_init(&state[i], &right, 0, ma_part.size); state[i++].use_part = true; - if (wr_mas->offset_end > mas->end) { + if (wr_mas->offset_end < mas->end) { state[i].info = &src_info; - printk("src is info %p\n", src_info.node); mns_mni_init(&state[i++], &right, wr_mas->offset_end + 1, - mas->end - wr_mas->offset_end + 1); + mas->end - wr_mas->offset_end); + printk("src is info %p\n", src_info.node); } } - printk("\n\nAssemble %u\n", i); mns_assemble(state, i); - printk("\n\n"); - mni_finalise(&left); mni_finalise(&right); mni_node_part_init(&ma_part, &left, &right); @@ -4410,6 +4507,7 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) //printk("%d height is %d\n", __LINE__, height); while (--height) { i = 0; + printk("===================Start of loop\n"); mas_wr_ascend_init(mas, &src_info); mas->end = src_info.end; total = mas->end + 1; @@ -4431,6 +4529,7 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) if (split >= mas->offset) { unsigned char space; /* size remaining in left */ + printk("%d\n", __LINE__); if (mas->offset) { state[i].info = &src_info; mns_mni_init(&state[i++], &left, 0, mas->offset); @@ -4463,23 +4562,27 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) state[i].info = &src_info; mns_mni_init(&state[i++], &right, split + 1, mas->end - split + 1); } else { + printk("%d\n", __LINE__); + printk("src is %p\n", src_info.node); state[i].info = &src_info; mns_mni_init(&state[i], &left, 0, split); if (mns_ends_in_null(&state[i])) { - state[i].size--; - split--; + state[i].size++; + split++; } i++; - if (mas->offset > split + 1) { + if (mas->offset > split) { state[i].info = &src_info; - mns_mni_init(&state[i++], &right, split + 1, - mas->offset - split + 1); + printk("\t\tcp %u-%u\n", split , mas->offset); + mns_mni_init(&state[i++], &right, split, + mas->offset - split); } state[i].part = &ma_part; mns_mni_init(&state[i], &right, 0, ma_part.size); state[i++].use_part = true; - if (wr_mas->offset_end > mas->end) { + if (wr_mas->offset_end < mas->end) { + printk("%d\n", __LINE__); state[i].info = &src_info; mns_mni_init(&state[i++], &right, wr_mas->offset_end + 1, mas->end - wr_mas->offset_end + 1); @@ -4490,6 +4593,7 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) mni_finalise(&left); mni_finalise(&right); mni_node_part_init(&ma_part, &left, &right); + printk("End of loop\n"); } new_root: -- 2.50.1