From 4289074d548ef6325c7a21fb05697ee624f6aa5c Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 23 Jun 2020 20:05:25 -0400 Subject: [PATCH] wip: pass 678642 tc Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 4 +- lib/maple_tree.c | 1038 ++++++++++++++++++------------------ 2 files changed, 510 insertions(+), 532 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 7cd1e8a02907..374889c82194 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -190,6 +190,7 @@ enum maple_type { struct maple_tree { spinlock_t ma_lock; unsigned int ma_flags; + unsigned int ma_height; void __rcu *ma_root; }; @@ -197,6 +198,7 @@ struct maple_tree { .ma_lock = __SPIN_LOCK_UNLOCKED(name.ma_lock), \ .ma_flags = flags, \ .ma_root = NULL, \ + .ma_height = 0, \ } #define DEFINE_MTREE(name) \ @@ -241,7 +243,7 @@ struct ma_state { struct maple_node *alloc; /* Allocated nodes for this operation */ struct maple_enode *span_enode; /* Pointer to maple parent/slot that set the max */ int full_cnt; /* (+ full nodes) / (- number of almost empty) nodes above */ - unsigned char last_cnt; /* count of levels where @last was previously contained */ + unsigned char depth; /* depth of tree descent during write */ }; #define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock)) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 1843270b2c60..7e79a6aa395e 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -828,7 +828,6 @@ static inline void mas_ascend(struct ma_state *mas) p_enode = mt_mk_node(mte_parent(mas->node), mas_parent_enum(mas, mas->node)); - if (_ma_is_root(a_node)) goto no_parent; @@ -1174,7 +1173,7 @@ static inline unsigned long mas_leaf_max_gap(struct ma_state *mas) pstart = mas->min; for (i = 0; i < mt_slots[mt]; i++) { - printk("Checking %u\n", i); + //printk("Checking %u\n", i); pend = mas_get_safe_pivot(mas, i); if (!pend && i) pend = mas->max; @@ -1185,8 +1184,8 @@ static inline unsigned long mas_leaf_max_gap(struct ma_state *mas) if (!mt_is_empty(entry) || xa_is_retry(entry)) goto next; - printk("gap %lu in %u\n", gap, i); - printk("%lu - %lu + 1\n", pend, pstart); + //printk("gap %lu in %u\n", gap, i); + //printk("%lu - %lu + 1\n", pend, pstart); if (gap > max_gap) max_gap = gap; @@ -1198,7 +1197,7 @@ next: pstart = pend + 1; } done: - printk("max gap is %lu\n", max_gap); + //printk("max gap is %lu\n", max_gap); return max_gap; } @@ -1398,8 +1397,10 @@ static inline void mas_adopt_children(struct ma_state *mas, child = _mte_get_rcu_slot(parent, slot, type, mas->tree); if (!mt_is_empty(child)) { - printk("set parent of %p\n", child); + printk("set parent of child %p slot %u\n", child, slot); + printk("parent is %p\n", parent); mte_set_parent(child, parent, slot); + printk("%p parent is %p\n", child, mte_parent(child)); } } } @@ -1410,7 +1411,8 @@ static inline void mas_adopt_children(struct ma_state *mas, * @push: push the old node onto the allocated nodes in mas->alloc * */ -static inline void _mas_replace(struct ma_state *mas, bool free, bool push) +static inline void _mas_replace(struct ma_state *mas, bool free, bool push, + bool adopt) { struct maple_node *mn = mas_mn(mas); struct maple_enode *parent = NULL; @@ -1418,6 +1420,7 @@ static inline void _mas_replace(struct ma_state *mas, bool free, bool push) unsigned char slot = 0; if (mte_is_root(mas->node)) { + printk("It's root\n"); prev = mas->tree->ma_root; } else { enum maple_type ptype = mas_parent_enum(mas, mas->node); @@ -1431,7 +1434,7 @@ static inline void _mas_replace(struct ma_state *mas, bool free, bool push) if (mte_to_node(prev) == mn) return; - if (!mte_is_leaf(mas->node)) + if (adopt && !mte_is_leaf(mas->node)) mas_adopt_children(mas, mas->node); if (mte_is_root(mas->node)) { @@ -1453,7 +1456,7 @@ static inline void _mas_replace(struct ma_state *mas, bool free, bool push) } static inline void mas_replace(struct ma_state *mas) { - _mas_replace(mas, true, false); + _mas_replace(mas, true, false, true); } static inline void mas_gap_link(struct ma_state *mas, struct maple_enode *parent, @@ -1487,7 +1490,7 @@ static inline enum maple_type mas_ptype_leaf(struct ma_state *mas) } } -#define MAPLE_BIG_NODE_SLOTS (MAPLE_NODE_SLOTS + 1) +#define MAPLE_BIG_NODE_SLOTS (MAPLE_NODE_SLOTS * 2 + 1) struct maple_big_node { struct maple_pnode *parent; struct maple_enode *slot[MAPLE_BIG_NODE_SLOTS]; @@ -1495,11 +1498,21 @@ struct maple_big_node { unsigned long gap[MAPLE_BIG_NODE_SLOTS]; }; +struct maple_clean_list { + struct maple_enode *enode; + struct list_head list; +}; + static bool mas_check_split_parent(struct ma_state *mas, unsigned char slot, struct ma_state *child_mas) { - printk("Checking slot %u\n", slot); - if (mte_parent(mas_get_rcu_slot(mas, slot)) != mas_mn(mas)) + void *entry = mas_get_rcu_slot(mas, slot); + + if (!entry) + return false; + + printk("parent of entry %u is %p\n", slot, mte_parent(entry)); + if (mte_parent(entry) != mas_mn(mas)) return false; mas_set_slot(child_mas, slot); @@ -1510,6 +1523,7 @@ static inline void mas_find_l_split(struct ma_state *mas, struct ma_state *l_mas { unsigned char i, end = mas_data_end(mas); 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; } @@ -1545,6 +1559,10 @@ static inline int mab_calc_split(struct maple_big_node *b_node, int size, { int split = (size + 1) / 2; // Assume equal split. + if (size > 2* slot_cnt) { + split = (size + 2) / 3; + } + 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 @@ -1575,8 +1593,12 @@ static inline int mas_mab_cp(struct ma_state *mas, unsigned char mas_start, int i, j; printk("%s: cp %u - %u\n", __func__, mas_start, mas_end); for (i = mas_start, j = mab_start; i < mas_end; i++, j++) { - printk("cp mas %u\n", i); + //printk("cp mas %u\n", i); b_node->slot[j] = mas_get_rcu_slot(mas, i); + if (!mte_is_leaf(mas->node) && mt_is_alloc(mas->tree)) { + b_node->gap[j] = mte_get_gap(mas->node, i); + printk("gap %d is %lu\n", j, b_node->gap[j]); + } if (i < mt_pivot_count(mas->node)) { printk("get safe pivot for %u\n", i); b_node->pivot[j] = mas_get_safe_pivot(mas, i); @@ -1588,8 +1610,6 @@ static inline int mas_mab_cp(struct ma_state *mas, unsigned char mas_start, b_node->slot[j], b_node->pivot[j]); break; } - if (!mte_is_leaf(mas->node) && mt_is_alloc(mas->tree)) - b_node->gap[j] = mte_get_gap(mas->node, i); if ((j && !b_node->pivot[j]) || (mas->max == b_node->pivot[j])) // end of node. @@ -1605,6 +1625,7 @@ static inline int mab_mas_cp(struct maple_big_node *b_node, int i, j; printk("%s: cp %u - %u to mas\n", __func__, mab_start, mab_end - 1); for (i = mab_start, j = mas_start; i < mab_end; i++, j++) { + //printk("i %d end %u\n", i, mab_end); if(j && !b_node->pivot[i]) { printk("no pivot at %u\n", i); break; @@ -1631,11 +1652,11 @@ static inline int mas_commit_rebalance(struct ma_state *mas, unsigned char new_end) { unsigned char p_end, end = 0, slot_cnt, split, b; - unsigned char l_child = 0, r_child = 0; + unsigned char slot, l_child = 0, r_child = 0; char empty = mas->full_cnt * -1; int height = 0; struct maple_enode *left, *right; - unsigned long l_piv; + unsigned long l_piv, l_gap = 0, r_gap = 0; printk("Need to rebalance %d levels\n", empty); MA_STATE(orig_mas, mas->tree, mas->index, mas->last); @@ -1680,12 +1701,14 @@ static inline int mas_commit_rebalance(struct ma_state *mas, alloc = true; mas_prev_node(&cp, 0); printk("prev node is %p\n", cp.node); - end = mas_data_end(&cp); - printk("prev end %u and new_end %u\n", end, new_end); - mab_shift_right(b_node, new_end + 1, end + 1, alloc); - mas_mab_cp(&cp, 0, end + 1, b_node, 0); - end += new_end + 1; - p_slot--; + if (!mas_is_none(&cp)) { + end = mas_data_end(&cp); + printk("prev end %u and new_end %u\n", end, new_end); + mab_shift_right(b_node, new_end + 1, end + 1, alloc); + mas_mab_cp(&cp, 0, end + 1, b_node, 0); + end += new_end + 1; + p_slot--; + } } mas_dup_state(&cp, mas); @@ -1712,7 +1735,7 @@ static inline int mas_commit_rebalance(struct ma_state *mas, printk("Using end %u\n", split); } else if (mte_is_leaf(mas->node)) // leaf split is special - split = mab_calc_split(b_node, end, slot_cnt, + split = mab_calc_split(b_node, end, slot_cnt, mas->min); else // internal nodes share 1/2, with the larger half going left. split = (end + 1) / 2; @@ -1722,6 +1745,12 @@ static inline int mas_commit_rebalance(struct ma_state *mas, printk("%s: left will have %u - %u\n", __func__, 0, split + 1); mab_mas_cp(b_node, 0, split + 1, &cp, 0); l_piv = cp.max; + if (mt_is_alloc(mas->tree)) { + if (mte_is_leaf(left)) + l_gap = mas_leaf_max_gap(&cp); + else + l_gap = mas_max_gap(&cp, &slot); + } if (end >= slot_cnt) { right = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), @@ -1729,6 +1758,13 @@ static inline int mas_commit_rebalance(struct ma_state *mas, cp.node = right; printk("%s: right will have %u - %u\n", __func__, split + 1, end + 1); mab_mas_cp(b_node, split + 1, end + 1, &cp, 0); + if (mt_is_alloc(mas->tree)) { + if (mte_is_leaf(right)) + r_gap = mas_leaf_max_gap(&cp); + else + r_gap = mas_max_gap(&cp, &slot); + } + } else { // Totally merged with the left. right = NULL; @@ -1755,12 +1791,17 @@ static inline int mas_commit_rebalance(struct ma_state *mas, r_child = l_child = b; printk("Set %u to %p\n", b, mte_to_node(left)); b_node->slot[b] = left; + if (mt_is_alloc(mas->tree)) + b_node->gap[b] = l_gap; b_node->pivot[b++] = l_piv; p_slot++; if (right) { + printk("Include right at b_node %u\n", b); r_child = b; b_node->slot[b] = right; printk("Set %u to %p\n", b, mte_to_node(right)); + if (mt_is_alloc(mas->tree)) + b_node->gap[b] = r_gap; b_node->pivot[b++] = mas_get_safe_pivot(mas, p_slot); } p_slot++; @@ -1794,12 +1835,15 @@ new_root_node: mas->node = cp.node; /* Kill leaf node(s) */ - mas_set_node_dead(&orig_mas); - smp_wmb(); + if (!mte_is_root(cp.node)) { + mas_set_node_dead(&orig_mas); + smp_wmb(); + } /* Insert new data */ - _mas_replace(mas, false, false); + _mas_replace(mas, false, false, true); + mas_update_gap(mas, false); /* Adoption routine... */ @@ -1818,16 +1862,13 @@ static inline int mas_commit_split(struct ma_state *mas, int i; printk("%s\n", __func__); - mt_dump(mas->tree); MA_STATE(orig_mas, mas->tree, mas->index, mas->last); - MA_STATE(parent, mas->tree, mas->index, mas->last); MA_STATE(l_mas, mas->tree, mas->index, mas->last); MA_STATE(r_mas, mas->tree, mas->index, mas->last); - MA_STATE(prev_l_mas, mas->tree, mas->index, mas->last); - MA_STATE(prev_r_mas, mas->tree, mas->index, mas->last); + MA_STATE(orig_l_mas, mas->tree, mas->index, mas->last); + MA_STATE(orig_r_mas, mas->tree, mas->index, mas->last); mas_dup_state(&orig_mas, mas); - mas_dup_state(&parent, mas); // Allocation failures will happen early. // TODO: Increase this by one when optimizing with a rebalance. @@ -1850,6 +1891,7 @@ static inline int mas_commit_split(struct ma_state *mas, struct maple_node *l, *r; enum maple_type type = mte_node_type(mas->node); unsigned char slot_cnt = mt_slot_count(mas->node); /* should be full. */ + bool cp = true; printk("height %d\n", height); @@ -1873,23 +1915,30 @@ static inline int mas_commit_split(struct ma_state *mas, if (i < mt_pivots[type]) mte_set_pivot(ancestor, i, b_node->pivot[i]); - if (mt_is_alloc(mas->tree)) + if (mt_is_alloc(mas->tree)) { + printk("Set gap %i to %lu\n", i, b_node->gap[i]); mte_set_gap(ancestor, i, b_node->gap[i]); + } } // Set the parent for the children. - printk("Placing left %u and right %u\n", - mas_get_slot(&l_mas), mas_get_slot(&r_mas)); + printk("Placing left %u and right %u in %p\n", + mas_get_slot(&l_mas), mas_get_slot(&r_mas), ancestor); + printk("l %p and r %p\n", mas_mn(&l_mas), mas_mn(&r_mas)); mte_set_parent(l_mas.node, ancestor, mas_get_slot(&l_mas)); mte_set_parent(r_mas.node, ancestor, mas_get_slot(&r_mas)); mte_to_node(ancestor)->parent = mas_mn(mas)->parent; + if (mas->full_cnt >= mas->tree->ma_height) + mas->tree->ma_height++; continue; } l = ma_mnode_ptr(mas_next_alloc(mas)); r = ma_mnode_ptr(mas_next_alloc(mas)); + printk("l = %p\n", l); + printk("r - %p\n", r); mas_dup_state(&l_mas, mas); mas_dup_state(&r_mas, mas); @@ -1929,44 +1978,50 @@ static inline int mas_commit_split(struct ma_state *mas, */ /* internal node split - cut in half for now. */ - i = mab_mas_cp(b_node, 0, (slot_cnt/2) + 1, &l_mas, 0); + split = (slot_cnt + 1) / 2; + printk("split is %u %u %u\n", split, mas_get_slot(&l_mas), + mas_get_slot(&r_mas)); + i = mab_mas_cp(b_node, 0, split + 1, &l_mas, 0); l_mas.max = b_node->pivot[i - 1]; printk("l_mas.max %lu\n", l_mas.max); r_mas.min = l_mas.max + 1; mab_mas_cp(b_node, i, slot_cnt + 1, &r_mas, 0); - p_slot = mas_get_slot(&prev_l_mas); - if (p_slot < split) { - // prev left side is on left. - mte_set_parent(prev_l_mas.node, l_mas.node, + p_slot = mas_get_slot(&orig_l_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. + mte_set_parent(orig_l_mas.node, l_mas.node, p_slot); - } else { - mte_set_parent(prev_l_mas.node, r_mas.node, + else + mte_set_parent(orig_l_mas.node, r_mas.node, + p_slot - split + 1); + + p_slot = mas_get_slot(&orig_r_mas); + if (p_slot <= split) // prev right side is on left. + mte_set_parent(orig_r_mas.node, l_mas.node, + p_slot); + else + mte_set_parent(orig_r_mas.node, r_mas.node, p_slot - split + 1); - } - if (p_slot + 1 < split) { - // prev right side is on left. - mte_set_parent(prev_r_mas.node, l_mas.node, - p_slot + 1); - } else { - mte_set_parent(prev_r_mas.node, r_mas.node, - p_slot + 1 - split + 2); - } } i = 0; memset(b_node, 0, sizeof(struct maple_big_node)); - if (!mte_is_root(parent.node)) { - printk("Ascend parent %p\n", mas_mn(&parent)); - mas_ascend(&parent); /* Go up a level */ - printk("Parent is %p\n", mas_mn(&parent)); - i = mas_mab_cp(&parent, 0, mas_get_slot(&l_mas), - b_node, 0); + if (mte_is_root(mas->node)) + cp = false; + else { + mas_ascend(mas); + mas_set_slot(mas, mte_parent_slot(mas->node)); } + if (cp) + i = mas_mab_cp(mas, 0, mas_get_slot(&l_mas), b_node, 0); + split = i; printk("Split is %u\n", split); b_node->slot[i] = l_mas.node; - printk("Set piv to %lu and insert l_mas node %p\n", l_mas.max, l_mas.node); + printk("l_mas %p[%u] piv %lu\n", mas_mn(&l_mas), i, l_mas.max); b_node->pivot[i] = l_mas.max; mas_set_slot(&l_mas, i); if (mt_is_alloc(mas->tree)) { @@ -1978,21 +2033,22 @@ static inline int mas_commit_split(struct ma_state *mas, b_node->gap[i] = mas_max_gap(&l_mas, &slot); b_node->gap[i + 1] = mas_max_gap(&r_mas, &slot); } + printk("Setting %p gap to %lu\n", + mas_mn(&l_mas), b_node->gap[i]); + printk("Setting %p gap to %lu\n", + mas_mn(&r_mas), b_node->gap[i+1]); } b_node->slot[++i] = r_mas.node; b_node->pivot[i] = r_mas.max; mas_set_slot(&r_mas, i); printk("New right is in %u (%p)\n", i, b_node->slot[i]); printk("piv right is %lu\n", r_mas.max); - mas_dup_state(&prev_l_mas, &l_mas); - mas_dup_state(&prev_r_mas, &r_mas); - if (!mte_is_root(mas->node)) { - mas_ascend(mas); - printk("get rest of parent %u-%u\n", i, mt_slot_count(parent.node) + 1); - i = mas_mab_cp(&parent, split + 1, - mt_slot_count(parent.node) + 1, b_node, + mas_dup_state(&orig_l_mas, &l_mas); + mas_dup_state(&orig_r_mas, &r_mas); + if (cp) + i = mas_mab_cp(mas, split + 1, + mt_slot_count(mas->node), b_node, i + 1); - } } @@ -2005,7 +2061,7 @@ static inline int mas_commit_split(struct ma_state *mas, smp_wmb(); // Insert the new data in the tree - _mas_replace(mas, false, false); + _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 @@ -2013,49 +2069,59 @@ static inline int mas_commit_split(struct ma_state *mas, * children with the correct parent. Once the new children are found, * then set the correct parent in all of of the parent's children. */ - mas_dup_state(&prev_l_mas, mas); - mas_dup_state(&prev_r_mas, mas); - while (!mte_is_leaf(prev_l_mas.node)) { - if (mte_is_leaf(l_mas.node)) - goto adoption; - - mas_find_l_split(&prev_l_mas, &l_mas); - printk("new child of %p is %p\n", mas_mn(&prev_l_mas), mas_mn(&l_mas)); - printk("%d New node is %p\n", __LINE__, mas_mn(&l_mas)); + 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(&prev_l_mas, prev_l_mas.node); - mas_dup_state(&prev_l_mas, &prev_r_mas); - mas_find_l_split(&prev_l_mas, &l_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 %p\n", __LINE__, mas_mn(&l_mas)); - mas_find_r_split(&prev_r_mas, &r_mas); - printk("new child of %p is %p\n", mas_mn(&prev_r_mas), mas_mn(&r_mas)); + 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_dup_state(&prev_r_mas, &prev_l_mas); - mas_find_r_split(&prev_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); } -adoption: - printk("Adopt children of %p\n", mas_mn(&prev_l_mas)); - printk("%d New node is %p\n", __LINE__, mas_mn(&l_mas)); - mas_adopt_children(&prev_l_mas, prev_l_mas.node); - if (prev_r_mas.node != prev_l_mas.node) - mas_adopt_children(&prev_r_mas, prev_r_mas.node); + printk("%d New node is at %u\n", __LINE__, mas_get_slot(&r_mas)); - if (mte_is_leaf(l_mas.node)) - break; + 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_dup_state(&prev_l_mas, &l_mas); 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_dup_state(&prev_r_mas, &r_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"); } - mt_dump(mas->tree); return 1; } + static inline int mas_commit_b_node(struct ma_state *mas, struct maple_big_node *b_node, unsigned char end) @@ -2075,12 +2141,15 @@ static inline int mas_commit_b_node(struct ma_state *mas, return 0; new_node = mt_mk_node(mas_next_alloc(mas), mte_node_type(mas->node)); + printk("Set %p parent to %p\n", mte_to_node(new_node), mas_mn(mas)->parent); mte_to_node(new_node)->parent = mas_mn(mas)->parent; + printk("Replace %p\n", mas_mn(mas)); mas->node = new_node; printk("Copy out 0-%u\n", end); mab_mas_cp(b_node, 0, end + 1, mas, 0); - _mas_replace(mas, true, false); + _mas_replace(mas, true, false, true); + mas_update_gap(mas, false); return 2; } @@ -2127,6 +2196,7 @@ static inline int mas_root_expand(struct ma_state *mas, void *entry) /* swap the new root into the tree */ rcu_assign_pointer(mas->tree->ma_root, mte_mk_root(mas->node)); + mas->tree->ma_height = 1; return slot; } static inline int ma_root_ptr(struct ma_state *mas, void *entry, @@ -2198,7 +2268,6 @@ static inline bool mas_is_span_wr(struct ma_state *mas, unsigned long piv, } mas->span_enode = mas->node; - mas->last_cnt = 0; return true; } @@ -2277,13 +2346,13 @@ static inline bool mas_wr_walk(struct ma_state *mas, unsigned long *range_min, mas->span_enode = NULL; mas->full_cnt = 0; - mas->last_cnt = 0; + mas->depth = 0; while (true) { type = mte_node_type(mas->node); + mas->depth++; - mas->last_cnt++; end = mas_data_end(mas); printk("End of %p is %u max of %u\n", mas_mn(mas), end, mt_slots[type]); if (unlikely(!mas_node_walk(mas, type, range_min, range_max))) @@ -2363,171 +2432,6 @@ static inline void mas_move_slot(struct ma_state *mas, unsigned char slot, } -/* Private - * mas_inactive_rebalance() - Rebalance l_mas and r_mas to have the necessary - * number of occupied slots. - * - * @l_mas - the left maple state - * @p_l_mas - the left parent maple state. - * @r_mas - the right maple state - * @p_r_mas - the right parent maple state. - * - * Note: r_mas may be completely consumed in this operation. - * - */ -static inline bool mas_inactive_rebalance(struct ma_state *mas, - struct ma_state *l_mas, - struct ma_state *r_mas) -{ - unsigned char l_end = mas_data_end(l_mas); - unsigned char r_end = mas_data_end(r_mas); - struct maple_big_node b_node; - unsigned char b = 0; - unsigned long min; - unsigned char slot_cnt, slot, split; - bool overwrite_left = false; - struct ma_state *target = l_mas; - struct maple_node *n_node; - unsigned long piv; - unsigned char p_slot = mte_parent_slot(l_mas->node); - bool ret = false; - - memset(&b_node, 0, sizeof(struct maple_big_node)); - MA_STATE(next, r_mas->tree, r_mas->index, r_mas->last); - MA_STATE(parent, l_mas->tree, l_mas->index, l_mas->last); - - printk("l_end = %u min %u\n", l_end, mt_min_slot_cnt(l_mas->node)); - if ((l_end + r_end + 1 < mt_slot_count(l_mas->node)) || - (l_end < mt_min_slot_cnt(l_mas->node))) { - printk("Include left node\n"); - mas_mab_cp(l_mas, 0, l_end + 1, &b_node, b); - b = l_end; - overwrite_left = true; - printk("b is %u\n", b); - } - - if (overwrite_left || (r_end < mt_min_slot_cnt(r_mas->node))) { - printk("Include right node\n"); - if (overwrite_left) - b++; // count slot 0 if there is data - mas_mab_cp(r_mas, 0, r_end + 1, &b_node, b); - b += r_end; - } - - if (!overwrite_left && (r_end + 1 >= mt_min_slot_cnt(r_mas->node))) { - printk("No rebalance\n"); - return false; // No rebalancing. - } - - printk("b is %u\n", b); - if ((overwrite_left && b <= mt_min_slot_cnt(l_mas->node)) || - (!overwrite_left && b <= mt_min_slot_cnt(r_mas->node))) { - /* Left and Right don't have enough for a node, balance with the - * node to the right - if it exists. - */ - printk("b = %u\n", b); - mas_dup_state(&next, r_mas); - mas_next_node(&next, ULONG_MAX); - if (!mas_is_none(&next)) { - slot = mas_data_end(&next); - mas_mab_cp(&next, 0, slot, &b_node, b); - b += slot; - } else { - printk("Just created invalid tree?\n"); - BUG_ON(1); - } - } - - printk("b = %u mt_slot_count = %u\n", b, mt_slot_count(l_mas->node)); - if (b < mt_slot_count(l_mas->node)) { - split = b; - } else { - /* Set up to copy data out of the big node by calculating the split and - * setting the target. */ - split = b / 2; - if (overwrite_left) { - slot_cnt = mt_slot_count(l_mas->node); - min = l_mas->min; - } else { - slot_cnt = mt_slot_count(r_mas->node); - min = r_mas->min; - target = r_mas; - } - - if (mte_is_leaf(l_mas->node)) - split = mab_calc_split(&b_node, b, slot_cnt, min); - } - - - /* Now, redistribute the data in b_node across l_mas->node, r_mas->node, - * and a new node (if necessary). - */ - /* First, put data into target */ - printk("%s: left will have %u - %u\n", __func__, 0, split); - slot = mab_mas_cp(&b_node, 0, split + 1, target, 0); - mas_zero_to_end(target, split + 1); - - if (split == b) // Everything went left. - goto fixup_parent; - - /* Then switch targets, either to a new node or to r_mas */ - if (overwrite_left) { - target = r_mas; - } else { - printk("FIXME: Broken\n"); - n_node = mte_to_node(next.node); - target = &next; - target->node = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), - mte_node_type(target->node)); - } - - /* Put the remainder of the data into the next target */ - printk("%s: right will have %u - %u\n", __func__, slot, b+1); - mab_mas_cp(&b_node, slot, b + 1, target, 0); - mas_zero_to_end(target, b + 1 - slot); - - /* Rewrite parent pointer(s) and potentially create a new parent for - * ma_state next. - */ -fixup_parent: - mas_dup_state(&parent, l_mas); - mas_ascend(&parent); - // Set old pivot. - if (split == b) { - printk("Consumed right\n"); - mte_set_pivot(parent.node, p_slot, r_mas->max); - piv = mas_get_safe_pivot(&parent, ++p_slot); - while (piv && p_slot < mt_slot_count(parent.node) - 1) { - mte_set_rcu_slot(parent.node, p_slot, - mas_get_rcu_slot(&parent, p_slot + 1)); - piv = mas_get_safe_pivot(&parent, ++p_slot); - mte_set_pivot(parent.node, p_slot - 1, piv); - } - - } else { - mte_set_pivot(parent.node, p_slot, l_mas->max); - if (!mas_is_none(&next) && !mas_is_start(&next)) { - //FIXME: Create new parent and put it in the tree. - } - /* Fix up r_mas slot and p_r_mas */ - if (overwrite_left) { - unsigned char r = mas_get_slot(r_mas) + l_end + 1; - printk("r slot %u\n", r); - if (r > split) - r -= split - 1; - else - ret = true; - - // Get parent - // update parent. - //mte_set_parent(r_mas->node, parent, r); - // Update the slot. - printk("Update slot to %u\n", r); - mas_set_slot(r_mas, r); - } - } - return ret; -} static inline bool __mas_walk(struct ma_state *mas, unsigned long *range_min, unsigned long *range_max); /* Private @@ -2540,60 +2444,74 @@ static inline bool __mas_walk(struct ma_state *mas, unsigned long *range_min, */ static inline int mas_spanning_store(struct ma_state *mas, void *entry) { - unsigned char slot, r_slot, l_slot = mas_get_slot(mas); unsigned long range_min, range_max; unsigned long l_gap = 0, r_gap = 0; - bool store_left = (entry ? true : false); - enum maple_type type; - struct maple_enode *left = NULL, *right, *ancestor; + unsigned char b_end = 0; // big_node end. + unsigned char l_slot, r_slot; + struct maple_big_node b_node; + int node_cnt = 0; + void *contents = NULL; + struct maple_enode *l, *r, *next = NULL; + + MA_STATE(orig_l_mas, mas->tree, mas->index, mas->index); + MA_STATE(orig_r_mas, mas->tree, mas->index, mas->index); + // Holds new left and right sub-tree + MA_STATE(l_mas, mas->tree, mas->index, mas->index); + MA_STATE(r_mas, mas->tree, mas->index, mas->index); + + // Leaf nodes + MA_STATE(prev_l_mas, mas->tree, mas->index, mas->index); + MA_STATE(prev_r_mas, mas->tree, mas->index, mas->index); printk("%s: %d\n", __func__, __LINE__); - // FIXME: Allocation count, height * 2 + 1 ? - mas_node_cnt(mas, 32); // 32 is an entire page. - if (mas_is_err(mas)) { - printk("Error %d\n", xa_err(mas->node)); - return 0; - } - MA_STATE(r_mas, mas->tree, mas->index, mas->last); // right - MA_STATE(old_r_mas, mas->tree, mas->index, mas->last); // right previous + if (mas->full_cnt > 0) + node_cnt = 1 + mas->full_cnt * 2; // For split upwards. - MA_STATE(l_mas, mas->tree, mas->index, mas->last); // left - MA_STATE(old_l_mas, mas->tree, mas->index, mas->last); // left previous + /* one for parent, one for potential 3rd node at bottom, + * two for every level below the split location. + */ + node_cnt += 2 + (mas->tree->ma_height - mas->depth) * 2; + + printk("Node_cnt is %u (%u - %u) * 2 with full %d\n", node_cnt, + mas->tree->ma_height, mas->depth, mas->full_cnt); + + mas_node_cnt(mas, node_cnt); + if (mas_is_err(mas)) + return 0; mas_dup_state(&l_mas, mas); - l_mas.last = l_mas.index; - __mas_walk(&l_mas, &range_min, &range_max); - l_slot = mas_get_slot(&l_mas); + l_mas.last = l_mas.index; // Avoid spanning store - mas_dup_state(&r_mas, &l_mas); + // Set up right side. + mas_dup_state(&r_mas, mas); r_mas.last++; r_mas.index = r_mas.last; - mas_set_slot(&r_mas, mte_parent_slot(l_mas.node)); - mas_next_node(&r_mas, ULONG_MAX); - mas_set_slot(&r_mas, 0); - // range_max is used below, so keep r_mas walk after l_mas. __mas_walk(&r_mas, &range_min, &range_max); - r_slot = mas_get_slot(&r_mas); r_mas.last = r_mas.index = mas->last; + r_slot = mas_get_slot(&r_mas); + printk("r_slot is %u\n", r_slot); - printk("%s: l_slot %p[%u] r_slot %p[%u]\n", __func__, - mas_mn(&l_mas), l_slot, - mas_mn(&r_mas), r_slot); - - /* No entry means storing right, otherwise check for full nodes and swap - * to right if the left is full and the right is not. - */ - if (store_left) { - if (mas_data_end(&l_mas) == mt_slot_count(l_mas.node) - 1) { - if (mas_data_end(&r_mas) < mt_slot_count(r_mas.node)) - store_left = false; + if (!entry) { + /* Check if there is a null in the next slot on the right */ + if (!mas_get_rcu_slot(&r_mas, r_slot)) { + mas->last = mas_get_safe_pivot(&r_mas, r_slot); + if (!mas->last) + mas->last = mas->max; + r_mas.last = r_mas.index = mas->last; + r_slot++; } - + if (range_max == r_mas.max) + printk("NULL could be in the next node?\n"); } - printk("%s: store %s\n", __func__, store_left ? "left" : "right"); - /* Expand store of NULL, if necessary */ + // Set up lift side. + __mas_walk(&l_mas, &range_min, &range_max); + l_slot = mas_get_slot(&l_mas); + printk("Start at %u\n", l_slot); + contents = mas_get_rcu_slot(&l_mas, l_slot); + + if (!entry) { /* Check if there is a null in the previous slot on the left */ if (!l_slot) { @@ -2603,271 +2521,300 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) mas->index = mte_get_pivot(l_mas.node, l_slot - 2) + 1; else mas->index = mas->min; + l_slot--; } - - /* Check if there is a null in the next slot on the right */ - if (!mas_get_rcu_slot(&r_mas, r_slot)) { - mas->last = mas_get_safe_pivot(&r_mas, r_slot); - if (!mas->last) - mas->last = mas->max; - } - if (range_max == r_mas.max) - printk("NULL could be in the next node?\n"); - } + printk("end at %u\n", l_slot); + printk("%s: final range is %lu-%lu at slot %u or %u\n", __func__, mas->index, mas->last, mas_get_slot(&l_mas), mas_get_slot(&r_mas)); - /* FIXME: What about detecting a split here? */ - - // if the parent is root - // check if a level can be removed. - // FIXME: Move this somewhere above here. - if (!mte_is_root(mas->node)) { - printk("potentially drop a level?\n"); -// if (!l_slot && r_slot == mas_data_end(parent)) -// printk("Drop a level\n"); - } - mas_dup_state(&r_mas, mas); - mas_dup_state(&l_mas, mas); - type = mte_node_type(mas->node); - l_mas.last = l_mas.index; - mas_node_walk(&l_mas, type, &range_min, &range_max); - // Set up the right side maple state to point to the correct slot - r_mas.last++; - r_mas.index = r_mas.last; // Just point to the right. - mas_node_walk(&r_mas, type, &range_min, &range_max); - - mas_dup_state(&old_r_mas, &r_mas); - mas_dup_state(&old_l_mas, &l_mas); - r_slot = mas_get_slot(&r_mas); - l_slot = mas_get_slot(&l_mas); - slot = r_slot; - printk("%s: copy %p[0-%u] for left\n", __func__, mas_mn(mas), l_slot); - printk("%s: copy %p[%u] over right\n", __func__, mas_mn(mas), r_slot); - - // Set up the left side maple state to point to just the left. - l_mas.last = mas->index; + mas_dup_state(&orig_l_mas, &l_mas); + mas_dup_state(&orig_r_mas, &r_mas); + while (orig_l_mas.node != mas->span_enode) { + unsigned char split, slot_cnt = mt_slot_count(orig_l_mas.node); + memset(&b_node, 0, sizeof(struct maple_big_node)); + // Add l_mas.node to clean_list. + // Fill out big node with left contents. + printk("%s: %p and %p\n", __func__, mas_mn(&orig_l_mas), + mas_mn(&orig_r_mas)); + printk("l_slot %u r_slot %u\n", l_slot, r_slot); + b_end = mas_mab_cp(&orig_l_mas, 0, l_slot, &b_node, 0); + + // if leaf set data + if (mte_is_leaf(orig_l_mas.node)) { + printk("Leaf and b_end %u\n", b_end); + // Terminate old entry at l_slot. + if (range_min < mas->index) { + b_node.slot[b_end] = contents; + b_node.pivot[b_end++] = mas->index - 1; + } - // Make a new node, etc. - ancestor = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), type); - l_mas.node = ancestor; - r_mas.node = l_mas.node; - // Set the middle pivot of the ancestor. - mas_mn(&l_mas)->parent = mas_mn(mas)->parent; // Copy the parent. - mas->node = l_mas.node; // Save for later. + // Insert new entry. + b_node.slot[b_end] = entry; + b_node.pivot[b_end++] = mas->last; + printk("Set %lu to %p\n", mas->last, entry); + } else { + // Not a leaf means new_l_mas goes at l_slot. + b_node.slot[b_end] = l_mas.node; + b_node.pivot[b_end++] = l_mas.max; - do { - if (mte_is_leaf(r_mas.node) && !store_left) { - // Store value in right side. - printk("r store %p[%u] %lu %p\n", mas_mn(&r_mas), slot, - r_mas.last - 1, entry); - mte_set_rcu_slot(r_mas.node, slot, entry); - mte_set_pivot(r_mas.node, slot, r_mas.last - 1); - if (entry || mas_get_rcu_slot(&old_r_mas, r_slot)) - slot++; + if (next) { + b_node.slot[b_end] = next; + b_node.pivot[b_end++] = r_mas.min - 1; + } + if (r_mas.node != l_mas.node) { + b_node.slot[b_end] = r_mas.node; + b_node.pivot[b_end++] = r_mas.max; + } } - // Copy right to new node. - for (; r_slot < mt_slot_count(r_mas.node); r_slot++) { - unsigned long piv = - mas_get_safe_pivot(&old_r_mas, r_slot); - if (!piv) // Node end. - break; - printk("r cp %p[%u] -> %p[%u]\n", - mas_mn(&old_r_mas), r_slot, - mas_mn(&r_mas), slot); - printk("val is %lu -> %p\n", piv, mas_get_rcu_slot(&old_r_mas, r_slot)); - mte_set_rcu_slot(r_mas.node, slot, - mas_get_rcu_slot(&old_r_mas, r_slot)); - if (r_slot < mt_pivot_count(r_mas.node)) - mte_set_pivot(r_mas.node, slot, piv); - r_mas.max = piv; - - if (mt_is_alloc(mas->tree) && !ma_is_leaf(type)) - mte_set_gap(r_mas.node, slot, - mte_get_gap(old_r_mas.node, r_slot)); - slot++; + // Add r_mas.node to clean_list. + b_end = mas_mab_cp(&orig_r_mas, r_slot, + mas_data_end(&orig_r_mas) + 1, &b_node, + b_end); + + if (b_end < mt_min_slot_cnt(orig_l_mas.node)) { + printk("Steal some data from right\n"); + mas_set_slot(&orig_r_mas, + mte_parent_slot(orig_r_mas.node)); + mas_next_node(&orig_r_mas, ULONG_MAX); + if (!mas_is_none(&orig_r_mas)) { + // Add r_mas.node to clean_list. + // r_mas is now at the next node.. + b_end = mas_mab_cp(&orig_r_mas, 0, + mas_data_end(&orig_r_mas) + 1, + &b_node, b_end); + } else { + // Use prev. + // shift b_node by prev size + // copy in prev. + // fix l_slot/r_slot ? + } } + /* Now that l_mas data and r_mas data is in big_node, divide the data + * into two nodes of equal size and continue to do so up the tree for + * each level. + */ - // Copy left to new node. - type = mte_node_type(l_mas.node); - for (slot = 0; slot < l_slot; slot++) { - unsigned long piv; - - printk("l cp %p[%u] -> %p[%u]\n", - mas_mn(&old_l_mas), slot, - mas_mn(&l_mas), slot); - printk("val is %lu -> %p\n", - mte_get_pivot(old_l_mas.node, slot), - mas_get_rcu_slot(&old_l_mas, slot)); - - piv = mte_get_pivot(old_l_mas.node, slot); - mte_set_rcu_slot(l_mas.node, slot, - mas_get_rcu_slot(&old_l_mas, slot)); - mte_set_rcu_slot(l_mas.node, slot, - mas_get_rcu_slot(&old_l_mas, slot)); - mte_set_pivot(l_mas.node, slot,piv); - l_mas.max = piv; - if (mt_is_alloc(mas->tree) && !ma_is_leaf(type)) - mte_set_gap(l_mas.node, slot, - mte_get_gap(old_l_mas.node, slot)); + /* Calc split between 1 or 3 nodes */ + printk("b_end %u slot_cnt %u\n", b_end, slot_cnt); + if (b_end < slot_cnt) { + split = b_end; + } else { + split = mab_calc_split(&b_node, b_end, slot_cnt, + orig_l_mas.min); } - if (ma_is_leaf(type)) { - unsigned long piv = l_mas.index - 1; - printk("piv = %lu\n", piv); - - // If this truncates a range, terminate the range. - if (mte_get_pivot(l_mas.node, l_slot - 1) > piv) - mte_set_pivot(l_mas.node, l_slot - 1, piv); - - if (store_left) { - // Store new range. - mte_set_rcu_slot(l_mas.node, l_slot, entry); - if (slot < mt_pivot_count(l_mas.node)) - mte_set_pivot(l_mas.node, l_slot, - l_mas.last); - l_mas.max = l_mas.last; - } + printk("%s: %u entries in b_node split is %u\n", __func__, + b_end, split); - } else { - // Overwrite the pivot between the two nodes with the - // correct value. - if (store_left) - l_mas.max = mas->last; - else - l_mas.max = mas->index - 1; - mte_set_pivot(l_mas.node, l_slot, l_mas.max); + l = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), + mte_node_type(orig_l_mas.node)); - if (!left) { - mte_set_rcu_slot(l_mas.node, l_slot, - mas_get_rcu_slot(&old_l_mas, l_slot)); - if (mt_is_alloc(mas->tree)) - mte_set_gap(l_mas.node, l_slot, - mte_get_gap(old_l_mas.node, slot)); + if (split == b_end) + r = NULL; + else + r = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), + mte_node_type(orig_r_mas.node)); + + // Set the parents of the previous loop. + if (!mte_is_leaf(orig_l_mas.node)) { + if (l_slot <= split) + mte_set_parent(l_mas.node, l, l_slot); + else + mte_set_parent(l_mas.node, r, l_slot - split); + l_slot++; + if (next) { + if (l_slot <= split) + mte_set_parent(next, l, l_slot); + else + mte_set_parent(next, r, l_slot - split); + l_slot++; + } + if (r_mas.node != l_mas.node) { + if (l_slot <= split) + mte_set_parent(r_mas.node, l, l_slot); + else + mte_set_parent(r_mas.node, r, + l_slot - split); } } - // Rebalance left + right + (possibly) node to the right of right - if (l_mas.node != r_mas.node) { - printk("Old %p and %p\n", - mas_mn(&old_l_mas), mas_mn(&old_r_mas)); - printk("Rebalance between %p and %p\n", - mas_mn(&l_mas), mas_mn(&r_mas)); - mas_inactive_rebalance(mas, &l_mas, &r_mas); + if (b_end > (slot_cnt + mt_slot_count(orig_r_mas.node))) + next = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), + mte_node_type(orig_r_mas.node)); + + l_mas.node = l; + r_mas.node = l; + if (r) + r_mas.node = r; + + l_mas.min = orig_l_mas.min; + mab_mas_cp(&b_node, 0, split + 1, &l_mas, 0); + l_mas.max = b_node.pivot[split]; + printk("l_mas is %lu split %u\n", l_mas.max, split); + + if (r) + r_mas.min = l_mas.max + 1; + if (next) { + printk("Copy to 3rd node\n"); + r_mas.node = next; + mab_mas_cp(&b_node, split + 1, 1 + split * 2, &r_mas, 0); + r_mas.node = r; + split *= 2; + r_mas.min = b_node.pivot[split]; + } + if (r) { + mab_mas_cp(&b_node, split + 1, b_end + 1, &r_mas, 0); + r_mas.max = b_node.pivot[b_end]; + printk("r_mas.max is %lu\n", r_mas.max); } - l_slot = mas_get_slot(&l_mas); - r_slot = mas_get_slot(&r_mas); - printk("l_slot %u and r_slot %u\n", l_slot, r_slot); - // FIXME: Mark modified nodes dead, set the parents of the new - // nodes only. - - - // Check parent for rebalance or removal? - // - /* FIXME: Rebalance across gap means changing pivots up the tree - * to the ancestor, r_mas may now fall on the same side as - * l_mas, what does that look like? - if (unlikely(0) - mas_spanning_rebalance(&l_mas, &r_mas); - */ - if (ma_is_leaf(type)) // Don't descend if this is a leaf. - break; + if (mte_is_leaf(l)) { + mas_dup_state(&prev_l_mas, &l_mas); + if (l_mas.node == r_mas.node) + mas_dup_state(&prev_r_mas, &l_mas); + else + mas_dup_state(&prev_r_mas, &r_mas); + } - // Set up for a new run. - mas_descend(&old_r_mas); - mas_descend(&old_l_mas); - type = mte_node_type(old_r_mas.node); - // Create next nodes. - left = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), type); - printk("Set parent of %p to %p[%u]\n", left, mas_mn(&l_mas), l_slot); - mte_set_parent(left, l_mas.node, l_slot); - mte_set_rcu_slot(l_mas.node, l_slot, left); - mas_descend(&l_mas); - right = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), type); - printk("Set parent of %p to %p[%u]\n", right, mas_mn(&r_mas), r_slot); - mte_set_parent(right, r_mas.node, r_slot); - mte_set_rcu_slot(r_mas.node, r_slot, right); - mas_descend(&r_mas); + printk("Setup for next loop %p %p\n", mas_mn(&orig_l_mas), + mas_mn(&orig_r_mas)); + mas_ascend(&orig_l_mas); + mas_ascend(&orig_r_mas); + + mas_set_slot(&orig_r_mas, 0); + orig_r_mas.index = orig_r_mas.last = r_mas.max + 1; + printk("node walk %p for %lu\n", mas_mn(&orig_r_mas), r_mas.max + 1); + mas_node_walk(&orig_r_mas, mte_node_type(orig_r_mas.node), + &range_min, &range_max); + r_slot = mas_get_slot(&orig_r_mas); + orig_r_mas.index = orig_r_mas.last = r_mas.max; + + mas_set_slot(&orig_l_mas, 0); + printk("Walk %p for %lu\n", mas_mn(&orig_l_mas), orig_l_mas.index); + mas_node_walk(&orig_l_mas, mte_node_type(orig_l_mas.node), + &range_min, &range_max); + l_slot = mas_get_slot(&orig_l_mas); + } + printk("Done looping over spanning mess\n"); - mas_set_slot(&old_l_mas, 0); - mas_node_walk(&old_l_mas, type, &range_min, &range_max); - mas_set_slot(&old_r_mas, 0); - mas_node_walk(&old_r_mas, type, &range_min, &range_max); - - l_slot = mas_get_slot(&old_l_mas); - r_slot = mas_get_slot(&old_r_mas); - // Copy the slot info across to l_mas, r_mas even though the - // nodes are empty. - mas_set_slot(&l_mas, l_slot); - mas_set_slot(&r_mas, r_slot); - slot = 0; - printk("New loop, copy %p[0-%u] and %p[%u-end]\n", - mas_mn(&old_l_mas), l_slot, mas_mn(&old_r_mas), r_slot); - } while (1); + if (!l_slot && mte_is_root(orig_l_mas.node) && + l_mas.max == orig_l_mas.max) { + printk("New root %p\n", mas_mn(&l_mas)); + l = l_mas.node; + goto new_root; + } + memset(&b_node, 0, sizeof(struct maple_big_node)); + b_end = mas_mab_cp(&orig_l_mas, 0, l_slot, &b_node, 0); + b_node.slot[b_end] = l_mas.node; + printk("Set b_end %u to left %p\n", b_end, l_mas.node); + printk("l_mas.max = %lu\n", l_mas.max); + b_node.pivot[b_end++] = l_mas.max; + if (next) { + b_node.slot[b_end] = next; + printk("Set b_end %u to next %p\n", b_end, next); + b_node.pivot[b_end++] = r_mas.min - 1; + } - printk("Done loop\n"); + if (l_mas.node != r_mas.node) { + b_node.slot[b_end] = r_mas.node; + printk("Set b_end %u to right %p %lu\n", b_end, r_mas.node, r_mas.max); + b_node.pivot[b_end++] = r_mas.max; + } + while (mas_get_safe_pivot(&orig_l_mas, r_slot) <= mas->last && + r_slot <= mas_data_end(&orig_l_mas)) { + printk("skip %u\n", r_slot); + r_slot++; + } + if (orig_l_mas.max != r_mas.max && + orig_l_mas.max != l_mas.max) + b_end = mas_mab_cp(&orig_l_mas, r_slot, + mas_data_end(&orig_l_mas) + 1, &b_node, + b_end); - // mark modified node(s?) dead. - // NOTE: Rebalanced nodes not in this sub-tree are already marked dead. - mas_set_node_dead(&old_l_mas); - mas_set_node_dead(&old_r_mas); - smp_wmb(); - // insert new sub-tree - mas->node = ancestor; - printk("Replace tree\n\n"); - _mas_replace(mas, false, false); - mt_dump(mas->tree); + // Check for overfull node and split upwards. + if (b_end > mt_slot_count(orig_l_mas.node)) { + printk("Splitting up required (%u)\n", b_end); + } + + l = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), + mte_node_type(orig_l_mas.node)); + + printk("l_slot is %u for %p\n", l_slot, mas_mn(&l_mas)); + mte_set_parent(l_mas.node, l, l_slot); + if (next) + mte_set_parent(next, l, ++l_slot); + if (r_mas.node != l_mas.node) { + mte_set_parent(r_mas.node, l, ++l_slot); + printk("l_slot is %u for %p\n", l_slot, mas_mn(&r_mas)); + } + + + mas_dup_state(&l_mas, &orig_l_mas); + l_mas.node = l; + mab_mas_cp(&b_node, 0, b_end + 1, &l_mas, 0); +new_root: + mas_mn(&l_mas)->parent = mas_mn(mas)->parent; + mas->node = l_mas.node; + + // FIXME: Mark modified nodes as dead. + + // Insert new sub-tree + _mas_replace(mas, false, false, true); + + if (mte_is_leaf(mas->node)) + return 1; if (mt_is_alloc(mas->tree)) { - l_gap = mas_leaf_max_gap(&l_mas); - l_slot = mte_parent_slot(l_mas.node); - r_gap = mas_leaf_max_gap(&r_mas); - r_slot = mte_parent_slot(r_mas.node); + l_gap = mas_leaf_max_gap(&prev_l_mas); + l_slot = mte_parent_slot(prev_l_mas.node); + r_gap = mas_leaf_max_gap(&prev_r_mas); + r_slot = mte_parent_slot(prev_r_mas.node); } do { - // ascend - mas_dup_state(&old_l_mas, &l_mas); - mas_dup_state(&old_r_mas, &r_mas); - mas_ascend(&l_mas); - mas_ascend(&r_mas); + mas_dup_state(&l_mas, &prev_l_mas); + mas_dup_state(&r_mas, &prev_r_mas); + // Ascend. + mas_ascend(&prev_l_mas); + mas_ascend(&prev_r_mas); if (mt_is_alloc(mas->tree)) { - // mas_update_gap and friends (don't recursively do this) - mte_set_gap(l_mas.node, l_slot, l_gap); - l_gap = mas_max_gap(&l_mas, &l_slot); - l_slot = mte_parent_slot(l_mas.node); - - mte_set_gap(r_mas.node, r_slot, r_gap); - r_gap = mas_max_gap(&r_mas, &r_slot); - r_slot = mte_parent_slot(r_mas.node); + // mas_update_gap and friends (don't recursively do this) + printk("Set gap %p[%u] %lu\n", mas_mn(&prev_l_mas), l_slot, l_gap); + mte_set_gap(prev_l_mas.node, l_slot, l_gap); + l_gap = mas_max_gap(&prev_l_mas, &l_slot); + l_slot = mte_parent_slot(prev_l_mas.node); + + printk("Set gap %p[%u] %lu\n", mas_mn(&prev_r_mas), r_slot, r_gap); + mte_set_gap(prev_r_mas.node, r_slot, r_gap); + r_gap = mas_max_gap(&prev_r_mas, &r_slot); + r_slot = mte_parent_slot(prev_r_mas.node); } - // adopt children of nodes that don't have the correct parent - mas_adopt_children(&old_l_mas, l_mas.node); - mas_adopt_children(&old_r_mas, r_mas.node); + // adopt children of nodes that don't have the correct parent + mas_adopt_children(&l_mas, prev_l_mas.node); + mas_adopt_children(&r_mas, prev_r_mas.node); - } while (l_mas.node != ancestor); + } while (prev_l_mas.node != l); mas_update_gap(&l_mas, false); - - - if (mt_is_alloc(mas->tree)) mas_update_gap(mas, false); + // Free list of collected nodes. + // FIXME return 1; - } + static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite) { unsigned long r_max, r_min; @@ -2947,10 +2894,10 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite mas->last, mas_get_slot(mas)); } - mt_dump(mas->tree); memset(&b_node, 0, sizeof(struct maple_big_node)); printk("Copy 0-%u\n", slot); new_end = mas_mab_cp(mas, 0, slot, &b_node, 0); + printk("new_end is %u\n", new_end); if(r_min < mas->index) { b_node.slot[new_end] = content; @@ -2960,18 +2907,18 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite b_node.slot[new_end] = entry; printk("Setting %u %p\n", new_end, entry); - b_node.pivot[new_end++] = mas->last; + b_node.pivot[new_end] = mas->last; if (mas->last < r_max) { - b_node.slot[new_end] = content; + b_node.slot[++new_end] = content; printk("Setting %u %p\n", new_end, content); - b_node.pivot[new_end++] = r_max; + b_node.pivot[new_end] = r_max; } // Check if this is an append operation. end = mas_data_end(mas); - if ((new_end <= slot_cnt) && ((slot > end) || !end)) { + if ((new_end < slot_cnt) && ((slot > end) || !end)) { // Appending printk("Appending to %p[%u] %lu\n", mas_mn(mas), slot, mas->index); if (r_min < mas->index) @@ -2986,9 +2933,10 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite do { printk("Skip %u\n", slot); r_max = mas_get_safe_pivot(mas, ++slot); - } while ((r_max <= mas->last) && (slot < slot_cnt)); + } while ((r_max <= mas->last) && (slot <= end)); - new_end = mas_mab_cp(mas, slot, slot_cnt, &b_node, new_end); + if (mas->last < mas_get_safe_pivot(mas, slot)) + new_end = mas_mab_cp(mas, slot, end + 1, &b_node, new_end + 1); // count the node as full if it has not already been counted. if (new_end >= slot_cnt && end < slot_cnt) @@ -3972,7 +3920,6 @@ static inline void mas_rev_awalk(struct ma_state *mas, unsigned long size) if (mas_is_err(mas)) return; - mt_dump(mas->tree); mas_set_slot(mas, mas_data_end(mas)); @@ -4347,6 +4294,7 @@ void *_mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max, void *entry = NULL; bool leaf; unsigned char slot; + MA_STATE(mas, mt, *index, *index); if (!start && !(*index)) @@ -4364,8 +4312,7 @@ void *_mt_find(struct maple_tree *mt, unsigned long *index, unsigned long max, while (mas_search_cont(&mas, range_start, max, entry)) { entry = _mas_next(&mas, max, &range_start); - if (mt_is_empty(entry) || xa_is_zero(entry) || - xa_is_retry(entry)) + if (mt_is_empty(entry) || xa_is_zero(entry)) entry = NULL; } @@ -4983,6 +4930,34 @@ void mas_validate_parent_slot(struct ma_state *mas) } } } +void mas_validate_child_slot(struct ma_state *mas) { + enum maple_type type = mte_node_type(mas->node); + struct maple_enode *child; + unsigned char i; + + if (mte_is_leaf(mas->node)) + return; + + for (i = 0; i < mt_slots[type]; i++) { + child = mte_get_rcu_slot(mas->node, i, mas->tree); + if (!child) + break; + + if (mte_parent_slot(child) != i) { + pr_err("child has incorrect slot at "MA_PTR"[%u] " + MA_PTR" is set to %u\n", mas_mn(mas), + i, mte_to_node(child), mte_parent_slot(child)); + MT_BUG_ON(mas->tree, 1); + } + + if (mte_parent(child) != mte_to_node(mas->node)) { + pr_err("child "MA_PTR" has parent "MA_PTR" not "MA_PTR"\n", + mte_to_node(child), mte_parent(child), + mte_to_node(mas->node)); + MT_BUG_ON(mas->tree, 1); + } + } +} /** * Validate all pivots are within mas->min and mas->max. */ @@ -5032,6 +5007,7 @@ static inline void mas_dfs_postorder(struct ma_state *mas, unsigned long max) struct maple_enode *p = MAS_NONE, *mn = mas->node; unsigned long p_min, p_max; + mas_set_slot(mas, mte_parent_slot(mas->node)); mas_next_node(mas, max); if (mas->node != MAS_NONE) return; @@ -5062,14 +5038,14 @@ static inline void mas_dfs_postorder(struct ma_state *mas, unsigned long max) */ void mt_validate(struct maple_tree *mt) { -printk("Not supported yet\n"); -return; MA_STATE(mas, mt, 0, 0); rcu_read_lock(); mas_start(&mas); mas_first_entry(&mas, ULONG_MAX); while (mas.node != MAS_NONE) { + printk("Checking %p\n", mas_mn(&mas)); mas_validate_parent_slot(&mas); + mas_validate_child_slot(&mas); mas_validate_limits(&mas); if (mt_is_alloc(mt)) mas_validate_gaps(&mas); -- 2.50.1