From 32be32cb2bf309f4fb3a101aba31022384e07ce7 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Wed, 26 Feb 2025 21:20:19 -0500 Subject: [PATCH] mt_wr_split_data() Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 241 ++++++++++++++++++++++++++++++++++++++--------- 1 file changed, 195 insertions(+), 46 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 30220efa1f8a..d1f6dcb2b49d 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3150,8 +3150,8 @@ struct ma_node_state { }; unsigned char start; /* The start offset into the source*/ unsigned char size; /* The size to copy or insert */ - struct ma_node_info *dst; /* The destination node */ bool use_part; + struct ma_node_info *dst; /* The destination node */ }; /* @@ -3213,6 +3213,7 @@ void mni_node_part_init(struct ma_node_part *ma_part, ma_part->unfinished = false; ma_part->dst_max_off = 255; ma_part->skip = 1; + ma_part->leaf = false; } static __always_inline @@ -3351,6 +3352,7 @@ void mns_mni_init(struct ma_node_state *mns, struct ma_node_info *dst, mns->dst = dst; mns->start = start; mns->size = len; + mns->use_part = false; printk("Dst %p <= [%u] + %u\n", dst, start, len); } @@ -3634,7 +3636,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); + printk("space is %u data size is %u\n", space, data_size); /* Greedy rebalance */ if (space <= data_size) return 0; @@ -3656,6 +3658,8 @@ void mas_wr_ascend_init(struct ma_state *mas, struct ma_node_info *ni) ni->enode = mas->node; ni->node = mte_to_node(mas->node); ni->type = mte_node_type(mas->node); + ni->min = mas->min; + ni->max = mas->max; _mni_node_init(ni, ni->node, ni->type); mni_set_end(ni); ni->insert_off = mas->offset; @@ -3913,6 +3917,8 @@ static inline void mas_wr_converged(struct ma_node_info *src, mns_mni_init(&converged[i], dst, 0, src->insert_off); converged[i].info = src; off = src->insert_off; + printk("converged use_part is %s\n", + converged[i].use_part ? "a part" : "not a part"); i++; } @@ -3941,6 +3947,92 @@ static inline void mas_wr_converged(struct ma_node_info *src, mni_finalise(dst); } +static int mt_wr_split_data(struct ma_node_info *src, + struct ma_node_info *left, struct ma_node_info *right, + struct ma_node_part *ma_part, unsigned char split, + unsigned char insert, unsigned char size, unsigned char offset, + unsigned char node_ins_end, unsigned char total_data, + struct ma_node_state *state, int i) + +{ + unsigned char insert_end; + unsigned char node_off, part_off; + struct ma_node_info *to; + + insert_end = insert + ma_part->size - 1; + to = left; + node_off = 0; /* src */ + part_off = 0; + printk("offset is %u insert %u insert end %u total data %u\n", + offset, insert, insert_end, total_data); + printk("split %u\n", split); + do { + unsigned char copied = 0; + + if (offset >= insert && offset < insert_end) { + copied = min(ma_part->size - part_off, size); + printk("B:Insert at %u/%u size %u\n", offset, total_data, copied); + state[i].part = ma_part; + mns_mni_init(&state[i], to, part_off, copied); + state[i].use_part = true; + part_off += copied; + node_off = node_ins_end + 1; + } else { + state[i].info = src; + if (offset < insert_end) { + /* + * First part of node, may split across node + * boundaries though + */ + printk("A: min of %u and %u (%u - %u)\n", size, insert - offset, insert, offset); + copied = min(size, insert - offset); + } else { + printk("C: min of %u and %u\n", size, total_data - offset +1 ); + copied = min(size, src->end - node_off + 1); + } + + printk("size is %u split %u\n", size, split); + printk("cp at %u/%u size %u\n", offset, total_data, copied); + mns_mni_init(&state[i], to, node_off, copied); + + node_off += copied; + } + + offset += copied; + size -= copied; + printk("next offset %u\n", offset); + if ((to == left) && (offset >= split)) { + printk("Check null\n"); + if (mns_ends_in_null(&state[i])) { + printk("null split, adjust - 1\n"); + if (!state[i].use_part && offset != insert) { + state[i].size++; + split++; + offset++; + size--; + node_off++; + } else { + state[i].size--; + split--; + offset--; + size++; + if (!state[i].use_part) + node_off--; + } + printk("offset %u node_off %u\n", offset, node_off); + } + printk("Switch to right\n"); + size = total_data - split; + to = right; + split = 255; + } + i++; + printk("node off is %u vs %u\n", node_off, src->end); + } while (node_off <= src->end); + + return i; +} + /* * mas_wr_try_rebalance() - Try to rebalance two nodes, this may not work out. * @src: The source node state @@ -3954,12 +4046,13 @@ static inline void mas_wr_converged(struct ma_node_info *src, static bool mas_wr_try_rebalance(struct ma_state *mas, struct ma_node_info *src, unsigned char new_end, struct ma_node_info *left, struct ma_node_info *right, - struct ma_node_part *ma_part, unsigned char insert_end) + struct ma_node_part *ma_part, unsigned char node_ins_end) { struct ma_state tmp_mas; struct ma_node_info src2, parent, new_parent; - struct ma_node_state state[4]; + struct ma_node_state state[5]; unsigned char split, max, i; + unsigned char total_data, size, offset, insert; bool left_store = false; /* @@ -4001,6 +4094,7 @@ static bool mas_wr_try_rebalance(struct ma_state *mas, mas_ascend(&tmp_mas); try_right: tmp_mas.offset = parent.insert_off + 1; + printk("check parent offset %u\n", tmp_mas.offset); mas_descend(&tmp_mas); mni_mas_init(&src2, &tmp_mas); mni_set_end(&src2); @@ -4016,11 +4110,52 @@ try_right: printk("right will be rebalanced against this one.\n"); } + /* The rebalance operation will succeed. */ + + i = 0; + offset = 0; + total_data = src2.end + new_end + 1; + if (left_store) { + printk("left store\n"); + /* Left pushes data right. */ + insert = mas->offset; + size = split; + } else { + printk("right store\n"); + /* Right pushes data left */ + insert = mas->offset + src2.end + 1; + offset += src2.end + 1; + size = split - src2.end; + printk("size is %u = %u - %u\n", size, split, src2.end); + + printk("first store %p\n", src2.node); + state[i].info = &src2; + mns_mni_init(&state[i], left, 0, src2.end + 1); + i++; + } + + /* - * At this point, the rebalance operation will succeed. + * Offset indexed into new data + * split indexed into new data + * size is the remainder of the data requested to this node */ - i = 0; + /* + * There are two splits of src, at insert and insert_end. + * There can also be a split between nodes that may happen at these + * boundaries, or elsewhere. + */ + printk("do the splitting of data\n"); + i = mt_wr_split_data(src, left, right, ma_part, split, insert, size, + offset, node_ins_end, total_data, state, i); + if (left_store) { + printk("Cp right %p 0 - %u\n", src2.node, src2.end); + state[i].info = &src2; + mns_mni_init(&state[i++], right, 0, src2.end + 1); + } + +#if 0 if (left_store) { unsigned char space; @@ -4085,9 +4220,7 @@ try_right: mns_mni_init(&state[i++], right, split + 1, mas->end - split + 1); } else { printk("right store\n"); - /* - * Right pushes data left - */ + /* Right pushes data left */ state[i].info = &src2; mns_mni_init(&state[i], left, 0, src2.end + 1); i++; @@ -4101,12 +4234,30 @@ try_right: printk("Check null\n"); if (mns_ends_in_null(&state[i])) { printk("null split, adjust - 1\n"); - state[i].size++; - split++; + if (split + 1 < mas->offset) { + state[i].size++; + split++; + } else { + state[i].size--; + split--; + } + } i++; + + if (split + 1 < mas->offset) { + printk("cp src from %u - %u to right\n", split + 1, mas->offset - split + 1); + state[++i].info = src; + mns_mni_init(&state[i++], right, split + 1, mas->offset - split + 1); + } + + printk("insert part\n"); + state[i].part = ma_part; + mns_mni_init(&state[i], right, 0, ma_part->size); + state[i++].use_part = true; + } else { - unsigned char space = split - mas->offset + 1; + unsigned char l_size; /* Size of data remaining for left node */ /* split >= mas->offset */ if (mas->offset) { @@ -4116,34 +4267,38 @@ try_right: i++; } - if (space < ma_part->size) { + l_size = split - mas->offset + 1; + if (l_size < ma_part->size) { + unsigned char ma_remainder; + state[i].part = ma_part; - mns_mni_init(&state[i], left, 0, space); + mns_mni_init(&state[i], left, 0, l_size); state[i].use_part = true; + if (mns_ends_in_null(&state[i])) { printk("null split, adjust - 1\n"); state[i].size--; - split--; + l_size--; } i++; + ma_remainder = ma_part->size - l_size; state[i].part = ma_part; - mns_mni_init(&state[i], right, space, - ma_part->size - space + 1); + mns_mni_init(&state[i], right, l_size, + ma_remainder); 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++; - } + l_size -= ma_part->size; - if (space) { - state[i].info = src; - mns_mni_init(&state[i], left, insert_end, space); - i++; + if (l_size) { + state[i].info = src; + mns_mni_init(&state[i], left, insert_end, l_size); + i++; + insert_end += l_size - 1; + } } printk("Copy up to insert, do the insert maybe in two nodes\n"); } @@ -4155,29 +4310,20 @@ try_right: 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, 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; - } - if (insert_end > mas->end) { - printk("End bit now\n"); + if (insert_end < mas->end) { + printk("End bit now %u vs %u\n", insert_end, mas->end); state[i].info = src; mns_mni_init(&state[i++], right, insert_end + 1, mas->end - insert_end + 1); } } +#endif 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; @@ -4400,6 +4546,7 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) printk("Splitting leaf at %u store at %u\n", split, mas->offset); left.min = mas->min; right.max = mas->max; +#if 1 if (split >= mas->offset) { unsigned char space; @@ -4413,16 +4560,17 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) 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); + mns_mni_init(&state[i], &left, 0, ma_part.size); + state[i++].use_part = true; 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); + state[i].use_part = true; if (mns_ends_in_null(&state[i])) { printk("%d %u NULL split\n", __LINE__, i); state[i].size--; @@ -4433,9 +4581,9 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) 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); + state[i].use_part = true; i++; space = 0; } @@ -4491,12 +4639,12 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) printk("src is info %p\n", src_info.node); } } +#endif mns_assemble(state, i); mni_finalise(&left); mni_finalise(&right); mni_node_part_init(&ma_part, &left, &right); - ma_part.leaf = false; if (height == 1) { printk("src parent is %p\n", src_info.node->parent); @@ -4536,15 +4684,16 @@ static void mas_wr_split(struct ma_wr_state *wr_mas) } state[i].part = &ma_part; - state[i].use_part = true; space = split - mas->offset + 1; if (space >= ma_part.size) { - mns_mni_init(&state[i++], &left, 0, ma_part.size); + mns_mni_init(&state[i], &left, 0, ma_part.size); + state[i++].use_part = true; } else { - mns_mni_init(&state[i++], &left, 0, space); + mns_mni_init(&state[i], &left, 0, space); + state[i++].use_part = true; state[i].part = &ma_part; - state[i].use_part = true; - mns_mni_init(&state[i++], &right, space - 1, ma_part.size); + mns_mni_init(&state[i], &right, space - 1, ma_part.size); + state[i++].use_part = true; } -- 2.49.0