From 177e89222b60177955c6f1ed30896cb9648a53d0 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 27 May 2025 15:17:32 -0400 Subject: [PATCH] fix off by one and new root issue Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 2 +- lib/maple_tree.c | 162 ++++++++++++++++++++++++------- tools/testing/radix-tree/maple.c | 8 +- 3 files changed, 135 insertions(+), 37 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index cbbcd18d4186..9a09a4a4e046 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -692,7 +692,7 @@ void mt_cache_shrink(void); pr_info("WARN at %s:%d (%u)\n", \ __func__, __LINE__, __x); \ mas_dump(__mas); \ - mt_dump((__mas)->tree, mt_dump_hex); \ + mt_dump((__mas)->tree, mt_dump_dec); \ pr_info("Pass: %u Run:%u\n", \ atomic_read(&maple_tree_tests_passed), \ atomic_read(&maple_tree_tests_run)); \ diff --git a/lib/maple_tree.c b/lib/maple_tree.c index b8a982aeacb9..cb1dc601f470 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2561,9 +2561,17 @@ static inline void mas_topiary_replace(struct ma_state *mas, n++; } + printk("adopt child of %p\n", mas_mn(&tmp[i])); mas_adopt_children(&tmp[i], tmp[i].node); } + if (!n) { + printk("No new nodes beyond %p %p %p\n", + mas_mn(&tmp[0]), + mas_mn(&tmp[1]), + mas_mn(&tmp[2])); + + } if (MAS_WARN_ON(mas, n == 0)) break; @@ -2574,6 +2582,7 @@ static inline void mas_topiary_replace(struct ma_state *mas, tmp[i] = tmp_next[i]; } + printk("\n\nGC\n"); /* Collect the old nodes that need to be discarded */ if (mte_is_leaf(old_enode)) return mas_free(mas, old_enode); @@ -2591,6 +2600,7 @@ static inline void mas_topiary_replace(struct ma_state *mas, continue; while (n < 3) { + printk("find child of %p\n", mas_mn(&tmp[i])); if (!mas_find_child(&tmp[i], &tmp_next[n])) break; @@ -2604,6 +2614,13 @@ static inline void mas_topiary_replace(struct ma_state *mas, } } + if (!n) { + printk("No nodes beyond %p %p %p\n", + mas_mn(&tmp[0]), + mas_mn(&tmp[1]), + mas_mn(&tmp[2])); + + } if (MAS_WARN_ON(mas, n == 0)) break; @@ -3158,7 +3175,7 @@ void mns_node_part_span_leaf_init(struct ma_node_part *part, part->skip = wr_r->offset_end - wr_l->mas->offset + 1; if (wr_r->node != wr_l->node) - part->skip += wr_l->mas->end; + part->skip += wr_l->mas->end + 1; part->leaf = true; printk("%s skip %u (1 + %u - %u",__func__, part->skip, @@ -4814,6 +4831,8 @@ static inline void mas_wr_extend_null(struct ma_wr_state *wr_mas) { struct ma_state *mas = wr_mas->mas; + printk("check %p[%u]\n", wr_mas->node, wr_mas->offset_end); + printk(" slot is %p\n", wr_mas->slots); if (!wr_mas->slots[wr_mas->offset_end]) { /* If this one is null, the next and prev are not */ mas->last = wr_mas->end_piv; @@ -4852,10 +4871,11 @@ static __always_inline void mas_wr_end_piv(struct ma_wr_state *wr_mas) unsigned long last = wr_mas->mas->last; unsigned long *pivs = wr_mas->pivots; - printk("last is %u\n", last); + printk("last is %u, check %p %u\n", last, wr_mas->mas->node, wr_mas->mas->end); if (last > pivs[wr_mas->mas->end - 1]) { wr_mas->offset_end = wr_mas->mas->end; wr_mas->end_piv = wr_mas->mas->max; + printk("okay, set offset_end to %u end piv %lu\n", wr_mas->offset_end, wr_mas->end_piv); return; } @@ -4936,7 +4956,10 @@ static void spanning_append(struct split_data *sd, struct ma_node_info *src, { struct ma_node_state *state; + printk("append to state %u\n", sd->len); + fflush(stdout); state = &sd->states[sd->len]; + printk("size %u > %u - %u + 1\n", size, src->end, src->offset); if (size > src->end - src->offset + 1) size = src->end - src->offset + 1; @@ -4989,6 +5012,8 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) unsigned long min; bool force_more = false; + unsigned char new_end; + mas = wr_mas->mas; trace_ma_op(__func__, mas); printk("\n\n\n\t\t\t\t%s\n", __func__); @@ -5000,23 +5025,32 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) else sd.is_alloc = false; - /* FIXME: Can this happen? probably not? */ if (unlikely(!mas->index && mas->last == ULONG_MAX)) return mas_new_root(mas, wr_mas->entry); r_mas = *mas; r_mas.index = r_mas.last; mas_wr_walk_index(&r_wr_mas); - if (!wr_mas->entry && r_mas.offset == r_mas.end) { - printk("Check next node for null in slot 0\n"); + if (!wr_mas->entry) { + printk("Check next range for null from %p[%u]\n", r_mas.node, r_mas.offset); if (mas_next_range(&r_mas, ULONG_MAX)) { + printk("next range is not null\n"); mas_prev_range(&r_mas, 0); } else { - r_wr_mas.offset_end = 0; - r_wr_mas.node = mte_to_node(r_mas.node); - r_wr_mas.type = mte_node_type(r_mas.node); - r_wr_mas.slots = ma_slots(r_wr_mas.node, r_wr_mas.type); - r_wr_mas.pivots = ma_pivots(r_wr_mas.node, r_wr_mas.type); + printk("next range IS null %p[%u]\n", r_mas.node, r_mas.offset); + r_wr_mas.offset_end = r_mas.offset; + if (r_wr_mas.node != mte_to_node(r_mas.node)) { + printk("new node\n"); + r_wr_mas.node = mte_to_node(r_mas.node); + r_wr_mas.type = mte_node_type(r_mas.node); + r_wr_mas.slots = ma_slots(r_wr_mas.node, r_wr_mas.type); + r_wr_mas.pivots = ma_pivots(r_wr_mas.node, r_wr_mas.type); + } + if (r_wr_mas.offset_end == r_mas.end) { + r_mas.last = r_mas.max; + } else { + r_mas.last = r_wr_mas.pivots[r_wr_mas.offset_end]; + } } } r_mas.index = r_mas.min; @@ -5026,10 +5060,14 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) /* Set up left side. */ mas_wr_walk_index(wr_mas); mas_wr_extend_null(wr_mas); + if (unlikely(!mas->index && r_mas.last == ULONG_MAX)) + return mas_new_root(mas, wr_mas->entry); + printk("\nwr_mas min %lu write covers %u - %u\n", mas->min, mas->offset, wr_mas->offset_end); - printk("At %p and r_mas %p\n", mas_mn(mas), mas_mn(&r_mas)); + printk("At %p[%u] and r_mas %p[%u]\n", mas_mn(mas), mas->offset, + mas_mn(&r_mas), r_mas.offset); printk("r_mas: end piv is %lu max %lu\n", r_wr_mas.end_piv, r_mas.max); wr_mas->end_piv = r_wr_mas.end_piv; @@ -5071,14 +5109,23 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) * */ /* Set up sources (up to 3) + part (always) */ - sd.new_end = mas->end - part.skip + 1 + part.size; - max_s = 2; + max_s = 0; + sd.new_end = mas->end - part.skip + part.size; + if (mas->offset) { + printk("offset %u < %u\n", mas->offset, mas->end); + max_s = 1; + } + if (r_mas.node != mas->node) { - sd.new_end += r_mas.end; + sd.new_end += r_mas.end + 1; + } + if (r_wr_mas.offset_end < r_mas.end) { + printk("offset_end %u < %u\n", r_wr_mas.offset_end, r_mas.end); max_s++; } - printk("\tAt %p and r_mas %p\n", mas_mn(mas), mas_mn(&r_mas)); + printk("At %p[%u] and r_mas %p[%u]\n", mas_mn(mas), mas->offset, + mas_mn(&r_mas), r_mas.offset); printk("new end is %u (%u + %u - %u + 1 + %u)\n", sd.new_end, r_mas.end, mas->end, part.skip, part.size); mas_wr_ascend_init(&r_mas, &r_parent); @@ -5089,13 +5136,15 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) !ma_is_root(left.node) && (left.min || right.max != ULONG_MAX)) || unlikely(force_more)) { + //FIXME: Remove force_more in favour of a static inline force_more = false; /* Take in more nodes */ printk("!!! %d min slots not met\n", __LINE__); if (r_parent.insert_off < r_parent.end) { src[++max_s] = &other; - printk("%d: set src %u\n", __LINE__, 2); - mas_next_node(&r_mas, r_parent.node, ULONG_MAX); + printk("%d: set src %u\n", __LINE__, max_s); + //mas_next_node(&r_mas, r_parent.node, ULONG_MAX); + r_mas.offset++; r_parent.insert_off++; other = r_parent; printk("r_parent insert off is now %u\n", @@ -5105,26 +5154,31 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) printk("%d: set src %u\n", __LINE__, s); src[0] = &other; s++; - mas_prev_node(mas, 0); + max_s++; + //mas_prev_node(mas, 0); + mas->offset--; parent.insert_off--; other = parent; printk("Looks like there is a left sibling\n"); + printk("mas is now %p[%u]\n", mas_mn(mas), mas->offset); } else if (r_parent.max > ULONG_MAX) { - printk("%d: set src %u\n", __LINE__, 2); + printk("%d: set src %u\n", __LINE__, 2); src[++max_s] = &other; + printk("%d: set src %u\n", __LINE__, max_s); mas_next_node(&r_mas, r_parent.node, ULONG_MAX); mni_mas_init(&other, &r_mas); - r_parent.insert_off++; + //r_parent.insert_off++; printk("Looks like there is a right cousin\n"); BUG_ON(1); } else { BUG_ON(!parent.min); - printk("%d: set src %u\n", __LINE__, s); + printk("%d: set src %u\n", __LINE__, s); src[0] = &other; s++; + max_s++; mas_prev_node(mas, 0); mni_mas_init(&other, &r_mas); - parent.insert_off--; + //parent.insert_off--; printk("Looks like there is a left cousin\n"); BUG_ON(1); } @@ -5133,6 +5187,12 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) printk("descended other into %p with end %u\n", other.node, other.end); sd.new_end += other.end + 1; printk("new end is now %u\n", sd.new_end); + } else { + printk("sd_new_end %u < %u\n", + sd.new_end, mt_min_slots[left.type]); + printk("left is root %s\n", + ma_is_root(left.node) ? "yes" : "no"); + printk("l min %lu r max %lu\n", left.min, right.max); } /* A source by any other name.. */ @@ -5154,32 +5214,36 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) if (right.insert_off < right.end) { s++; - printk("%d: set src %u\n", __LINE__, s); + printk("%d: set src %u\n", __LINE__, s); src[s] = &right; right.offset = right.insert_off + 1; } + printk("s is %u and max_s is %u\n", s, max_s); printk("Start right at %u end is %u\n", right.offset, right.end); mni_node_init(&dst[d], mas_pop_node(mas), left.type); printk("new_end %u max is %u\n", sd.new_end, mt_slots[left.type]); if (sd.new_end >= 2 * mt_slots[left.type]) { + printk("\ttriple\n"); sd.split = sd.new_end / 3; sd.mid = sd.split * 2; d++; mni_node_init(&dst[d], mas_pop_node(mas), left.type); d++; mni_node_init(&dst[d], mas_pop_node(mas), left.type); - } else if (sd.new_end > mt_slots[left.type]) { + } else if (sd.new_end >= mt_slots[left.type]) { + printk("\tdouble\n"); sd.split = sd.new_end / 2; sd.mid = sd.new_end; d++; mni_node_init(&dst[d], mas_pop_node(mas), left.type); } else { + printk("\tsingle\n"); sd.split = sd.new_end; sd.mid = sd.new_end; } - printk("limits %u %u %u\n", sd.split, sd.mid, sd.new_end); + printk("limits %u %u %u | node %u\n", sd.split, sd.mid, sd.new_end, mt_slots[left.type]); limits[0] = sd.split; limits[1] = sd.mid; limits[2] = sd.new_end; @@ -5199,13 +5263,15 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) printk("limits is %u/%u\n", limits[d], sd.offset); printk("pass %u dst %p (%p)\n", d, &dst[d], dst[d].node); + printk("use src %u/%u\n", s, max_s); spanning_append(&sd, src[s], &dst[d], max); /* destination full */ printk("offset %u > %u\n", sd.offset, limits[d]); if (sd.offset > limits[d]) { /* Check NULL.. */ - if (ma_is_leaf(src[s]->type) - && mns_ends_in_null(&sd.states[sd.len - 1])) { + if (ma_is_leaf(src[s]->type) && + mns_ends_in_null(&sd.states[sd.len - 1]) && + src[s]->max != ULONG_MAX) { printk("\tnull correction\n"); if (sd.states[sd.len - 1].size > 1) sd.states[sd.len - 1].size--; @@ -5224,10 +5290,12 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) /* Source exhausted */ if (src[s]->offset > src[s]->end) { + printk("src %u end is %u\n", s, src[s]->end); src[s]->offset = 0; s++; } - } while (sd.offset < sd.new_end); + printk("sd offset %u vs new end %u\n", sd.offset, sd.new_end); + } while (sd.offset <= sd.new_end); dst[max_d].offset = 0; printk("\n\n"); @@ -5248,6 +5316,7 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) printk("r_parent %p %u parent %p %u\n", r_parent.node, r_parent.insert_off , parent.node, parent.insert_off); + printk("dst range %lu and %lu\n", dst[0].min, dst[max_d].max); if (!dst[0].min && dst[max_d].max == ULONG_MAX) { printk("New Root\n\n"); mas->depth = height + 1; @@ -5259,7 +5328,7 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) part.skip = r_parent.insert_off - parent.insert_off + 1; if (r_parent.node != parent.node) - part.skip += parent.end; + part.skip += parent.end + 1; printk("->Set skip to %u\n", part.skip); @@ -5268,9 +5337,36 @@ static void mas_wr_spanning_store(struct ma_wr_state *wr_mas) mni_mas_init(&left, mas); mni_mas_init(&right, &r_mas); printk("again\n\n"); - } while ((parent.node != r_parent.node) || - mas->end - part.skip + part.size >= mt_slots[parent.type]); - + printk("parent %p and r %p\n", + parent.node, r_parent.node); + printk("next size is %u (%u - %u + %u)\n", + mas->end - part.skip + part.size, + mas->end, part.skip, part.size); + + new_end = mas->end - part.skip + part.size; + if (parent.node != r_parent.node) + new_end += r_mas.end + 1; + + printk("new end is %u\n", new_end); + if (!parent.min && r_parent.max == ULONG_MAX) { + if (new_end < mt_slots[parent.type]) { + printk("break\n"); + break; + } + printk("root detected, but too big\n"); + } + printk("parent min %lu rparent max %lu\n", + parent.min, r_parent.max); + printk("nodes are %p and %p\n", parent.node, r_parent.node); + printk("new_end is %u\n", new_end); + } while (new_end < mt_min_slots[parent.type] || + (parent.node != r_parent.node) || + (new_end >= mt_slots[parent.type])); + /* + || + (!ma_is_root(parent.node) && + mas->end - part.skip + part.size < mt_min_slots[parent.type])); + */ //sd.new_end = r_mas.end + mas->end - part.skip + 1 + part.size; printk("\n\nDone %u vs %u\n", mas->end - part.skip + part.size, mt_slots[parent.type]); @@ -5280,7 +5376,7 @@ converged: left.enode = parent.enode; mas->node = new_parent.enode; new_root: - printk("replace %p with %p\n", left.enode, mas->node); + printk("replace %p with %p\n", mte_to_node(left.enode), mte_to_node(mas->node)); mas_wmb_replace(mas, left.enode); mtree_range_walk(mas); mt_dump(mas->tree, mt_dump_dec); diff --git a/tools/testing/radix-tree/maple.c b/tools/testing/radix-tree/maple.c index 2164e6990a2e..53d985196e22 100644 --- a/tools/testing/radix-tree/maple.c +++ b/tools/testing/radix-tree/maple.c @@ -36370,6 +36370,7 @@ void farmer_tests(void) struct maple_node *node; DEFINE_MTREE(tree); + goto skip; mt_dump(&tree, mt_dump_dec); mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE | MT_FLAGS_LOCK_EXTERN | MT_FLAGS_USE_RCU); @@ -36414,6 +36415,7 @@ void farmer_tests(void) check_prealloc(&tree); mtree_destroy(&tree); +skip: mt_init_flags(&tree, MT_FLAGS_ALLOC_RANGE); check_spanning_write(&tree); mtree_destroy(&tree); @@ -36543,10 +36545,10 @@ static void regression_tests(void) void maple_tree_tests(void) { - maple_tree_seed(); - maple_tree_harvest(); +// maple_tree_seed(); +// maple_tree_harvest(); #if !defined(BENCH) - regression_tests(); +// regression_tests(); farmer_tests(); #endif } -- 2.50.1