From e3ea74c5b71a34993b05a06a420f10037b6a6e6c Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Wed, 10 Jun 2020 21:13:38 -0400 Subject: [PATCH] maple_tree: WIP, start passing big data through for all stores Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 487 +++++++++++++++++------------------------- lib/test_maple_tree.c | 19 +- 2 files changed, 208 insertions(+), 298 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index f515d7549302..400a686c4b62 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1125,6 +1125,9 @@ static inline unsigned char _mas_data_end(const struct ma_state *mas, unsigned long piv = mas->min, prev_piv = mas->min; for (; slot < mt_slot_count(mas->node); slot++) { piv = _mas_get_safe_pivot(mas, slot, type); + if (piv >= mas->max) + break; + if (!piv && slot) { piv = prev_piv; slot--; @@ -1500,7 +1503,6 @@ static bool mas_check_split_parent(struct ma_state *mas, unsigned char slot, return false; mas_set_slot(child_mas, slot); - mas_descend(child_mas); return true; } @@ -1527,13 +1529,14 @@ static inline void mas_find_r_split(struct ma_state *mas, struct ma_state *r_mas static inline int mab_calc_split(struct maple_big_node *b_node, int size, unsigned char slot_cnt, unsigned long min) { - int split = size / 2; // Assume equal split. + int split = (size + 1) / 2; // Assume equal split. 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 */ - while ((b_node->pivot[split] - min) < slot_cnt) { + while (((b_node->pivot[split] - min) < slot_cnt) && + split < slot_cnt) { printk("Skipping ahead due to min span\n"); split++; } @@ -1553,7 +1556,9 @@ static inline int mas_mab_cp(struct ma_state *mas, unsigned char mas_start, unsigned char mab_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); b_node->slot[j] = mas_get_rcu_slot(mas, i); if (i < mt_pivot_count(mas->node)) { b_node->pivot[j] = mas_get_safe_pivot(mas, i); @@ -1567,6 +1572,10 @@ static inline int mas_mab_cp(struct ma_state *mas, unsigned char mas_start, } 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. + break; } return j; } @@ -1576,12 +1585,14 @@ static inline int mab_mas_cp(struct maple_big_node *b_node, struct ma_state *mas, unsigned char mas_start) { int i, j; + printk("%s: cp %u - %u\n", __func__, mab_start, mab_end - 1); for (i = mab_start, j = mas_start; i < mab_end; i++, j++) { if(j && !b_node->pivot[i]) break; mas->max = b_node->pivot[i]; mte_set_rcu_slot(mas->node, j, b_node->slot[i]); + printk("Set %u %lu %p\n", j, b_node->pivot[i], b_node->slot[i]); if (j < mt_pivot_count(mas->node)) mte_set_pivot(mas->node, j, b_node->pivot[i]); @@ -1592,75 +1603,17 @@ static inline int mab_mas_cp(struct maple_big_node *b_node, return i; } -static inline int mas_split_leaf(struct ma_state *mas, struct ma_state *l_mas, - struct ma_state *r_mas, void *entry, - unsigned char new_end) -{ - unsigned char slot = mas_get_slot(mas); // The store of entry here. - unsigned char slot_cnt = mt_slot_count(mas->node); - struct maple_big_node b_node; - unsigned long piv; - void *contents; - int ret = 0; - int i = 0, end; - - b_node.slot[slot] = NULL; - - printk("Slot %u put in %lu-%lu\n", slot, mas->index, mas->last); - i = mas_mab_cp(mas, 0, slot, &b_node, 0); - piv = b_node.pivot[i]; - contents = b_node.slot[i]; - - if (mas->index > piv) { - b_node.pivot[i++] = mas->index - 1; - printk("!Set %u slot %p => piv %lu\n", i, b_node.slot[i-1], b_node.pivot[i-1]); - } - - b_node.pivot[i] = mas->last; - printk(".Set %u slot %p => piv %lu\n", i, entry, b_node.pivot[i]); - b_node.slot[i++] = entry; - if (mas->last < piv) { - printk("+Set %u slot %p => piv %lu\n", i, contents, piv); - b_node.pivot[i] = piv; - b_node.slot[i++] = contents; - } - - i = mas_mab_cp(mas, slot + 1, slot_cnt, &b_node, i); - printk("i = %u\n", i); - printk("Zero %u\n", i); - b_node.slot[i] = NULL; - b_node.pivot[i--] = 0; - - end = i; - ret = i / 2; - ret = mab_calc_split(&b_node, i, slot_cnt, mas->min); - - // Copy values up to ret to left. - i = mab_mas_cp(&b_node, 0, ret + 1, l_mas, 0); - printk("l_max is %lu\n", l_mas->max); - mas_set_slot(l_mas, mte_parent_slot(mas->node)); - printk("r_min is %lu\n", piv + 1); - r_mas->min = piv + 1; - - // In the case of empty. - mte_set_pivot(r_mas->node, 0, r_mas->max); - printk("We are missing one here.. end %u ret %u\n", end, ret); - mab_mas_cp(&b_node, ret + 2, end + 1, r_mas, 0); - mas_set_slot(r_mas, mas_get_slot(l_mas) + 1); - - return ret; -} - -static inline int mas_commit_store_split(struct ma_state *mas, void *entry, - unsigned char new_end) +static inline int mas_commit_split(struct ma_state *mas, + struct maple_big_node *b_node, + unsigned char new_end) { struct maple_enode *ancestor = MAS_NONE; - struct maple_big_node big_node; unsigned char split = 0; int height = 0; 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); @@ -1672,8 +1625,6 @@ static inline int mas_commit_store_split(struct ma_state *mas, void *entry, mas_dup_state(&orig_mas, mas); mas_dup_state(&parent, mas); -// mas->full_cnt++; // For leaf node. - // Allocation failures will happen early. // TODO: Increase this by one when optimizing with a rebalance. mas_node_cnt(mas, 1 + mas->full_cnt * 2); @@ -1694,6 +1645,8 @@ static inline int mas_commit_store_split(struct ma_state *mas, void *entry, while (height++ <= mas->full_cnt) { 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. */ + printk("height %d\n", height); if (height > mas->full_cnt) { @@ -1710,15 +1663,15 @@ static inline int mas_commit_store_split(struct ma_state *mas, void *entry, ancestor = mt_mk_node(ma_mnode_ptr(mas_next_alloc(mas)), type); for (i = 0; i < mt_slots[type]; i++) { - if (!big_node.pivot[i]) + if (!b_node->pivot[i]) break; - mte_set_rcu_slot(ancestor, i, big_node.slot[i]); + mte_set_rcu_slot(ancestor, i, b_node->slot[i]); if (i < mt_pivots[type]) mte_set_pivot(ancestor, i, - big_node.pivot[i]); + b_node->pivot[i]); if (mt_is_alloc(mas->tree)) mte_set_gap(ancestor, i, - big_node.gap[i]); + b_node->gap[i]); } // Set the parent for the children. printk("Placing left %u and right %u\n", @@ -1740,10 +1693,27 @@ static inline int mas_commit_store_split(struct ma_state *mas, void *entry, r_mas.node = mt_mk_node(r, type); if (mte_is_leaf(mas->node)) { printk("Splitting leaf %p\n", mas_mn(mas)); - split = mas_split_leaf(mas, &l_mas, &r_mas, entry, - new_end); + split = mab_calc_split(b_node, new_end, slot_cnt, + mas->min); + printk("Splitting at %u\n", split); + if (split < slot_cnt) + i = mab_mas_cp(b_node, 0, split + 1, &l_mas, 0); + else + i = mab_mas_cp(b_node, 0, slot_cnt, &l_mas, 0); + + mte_set_pivot(r_mas.node, 0, r_mas.max); + mab_mas_cp(b_node, i, new_end+ 1, &r_mas, 0); + + printk("l_max is %lu\n", l_mas.max); + mas_set_slot(&l_mas, mte_parent_slot(mas->node)); + r_mas.min = l_mas.max + 1; + printk("r_min is %lu\n", r_mas.min); + + // In the case of empty. + printk("We are missing one here.. end %u split %u\n", + new_end, split); + mas_set_slot(&r_mas, mas_get_slot(&l_mas) + 1); } else { - unsigned char slot_cnt = mt_slot_count(mas->node); /* should be full. */ unsigned char p_slot; /* TODO: Check rebalancing to avoid continuing walking @@ -1754,10 +1724,11 @@ static inline int mas_commit_store_split(struct ma_state *mas, void *entry, */ /* internal node split - cut in half for now. */ - i = mab_mas_cp(&big_node, 0, slot_cnt/2, &l_mas, 0); - l_mas.max = big_node.pivot[i]; + i = mab_mas_cp(b_node, 0, (slot_cnt/2) + 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(&big_node, i, slot_cnt + 1, &r_mas, 0); + 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. @@ -1778,55 +1749,52 @@ static inline int mas_commit_store_split(struct ma_state *mas, void *entry, } 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), - &big_node, 0); + b_node, 0); } split = i; printk("Split is %u\n", split); - big_node.slot[i] = l_mas.node; - big_node.pivot[i] = l_mas.max; + 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); + b_node->pivot[i] = l_mas.max; mas_set_slot(&l_mas, i); if (mt_is_alloc(mas->tree)) { if (mte_is_leaf(l_mas.node)) { - big_node.gap[i] = mas_leaf_max_gap(&l_mas); - big_node.gap[i + 1] = mas_leaf_max_gap(&r_mas); + b_node->gap[i] = mas_leaf_max_gap(&l_mas); + b_node->gap[i + 1] = mas_leaf_max_gap(&r_mas); } else { unsigned char slot; - big_node.gap[i] = mas_max_gap(&l_mas, &slot); - big_node.gap[i + 1] = - mas_max_gap(&r_mas, &slot); + b_node->gap[i] = mas_max_gap(&l_mas, &slot); + b_node->gap[i + 1] = mas_max_gap(&r_mas, &slot); } } - big_node.slot[++i] = r_mas.node; - big_node.pivot[i] = r_mas.max; + 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, big_node.slot[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); - printk("Zero %u\n", i + 1); - big_node.pivot[i + 1] = 0; - big_node.slot[i + 1] = NULL; if (!mte_is_root(mas->node)) { mas_ascend(mas); i++; i = mas_mab_cp(&parent, i, mt_slot_count(parent.node), - &big_node, i + 1); - printk("Zero %u\n", i); - big_node.pivot[i] = 0; - big_node.slot[i] = NULL; + b_node, i + 1); } } mas->node = ancestor; - printk("Using %p\n", ancestor); + printk("Using %p (%p)\n", ancestor, mte_to_node(ancestor)); BUG_ON(mas_is_none(mas)); // Set the original node as dead + printk("Killing orig_mas %p\n", mas_mn(&orig_mas)); mas_set_node_dead(&orig_mas); smp_wmb(); @@ -1841,16 +1809,20 @@ static inline int mas_commit_store_split(struct ma_state *mas, void *entry, */ mas_dup_state(&prev_l_mas, mas); mas_dup_state(&prev_r_mas, mas); - while (!mte_is_leaf(l_mas.node)) { + 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)); if (mas_is_none(&l_mas)) { 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); } + 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)); @@ -1859,98 +1831,34 @@ static inline int mas_commit_store_split(struct ma_state *mas, void *entry, mas_dup_state(&prev_r_mas, &prev_l_mas); mas_find_r_split(&prev_r_mas, &l_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); - mas_descend(&l_mas); - mas_dup_state(&prev_l_mas, &l_mas); if (prev_r_mas.node != prev_l_mas.node) mas_adopt_children(&prev_r_mas, prev_r_mas.node); - mas_descend(&r_mas); + + if (mte_is_leaf(l_mas.node)) + break; + + mas_dup_state(&prev_l_mas, &l_mas); + mas_descend(&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); } mt_dump(mas->tree); return 1; } -/* Private - * mas_wr_slot_cnt() - Calculate the slots required to write @entry. - * @mas - the maple state - * @r_min - the minimum range of the slot in @mas - * @r_max - the maximum range of the slot in @mas - * @entry - the entry that is going to be written. - * - * Note: May return larger than the node can hold. - */ -static inline unsigned char mas_wr_slot_cnt(struct ma_state *mas, - unsigned long r_min, unsigned long r_max, - void *entry) +static inline int mas_commit_b_node(struct ma_state *mas, + struct maple_big_node *b_node, + unsigned char end) { - unsigned char new_end = mas_data_end(mas); - unsigned char i, slot = mas_get_slot(mas); - void *contents = mas_get_rcu_slot(mas, slot); - unsigned long end_max = r_max; - - printk("Checking slot %u with %lu-%lu\n", slot, r_min, r_max); - printk(" entry %p with %lu-%lu\n", entry, mas->index, mas->last); - if (!contents && !entry) - goto check_spans_slots; // Overwriting a null with nulls. - - if (mas->index > r_min) - new_end++; - - if (mas->last < r_max) - new_end++; - else if (mas->last > r_max) - goto check_spans_slots; - - printk("%s: new_end is now %u\n", __func__, new_end); - return new_end; - -check_spans_slots: // A store may span slots but - - i = slot; - while (end_max < mas->last && i < mt_slot_count(mas->node) - 1) { - printk("Checking %u\n", i); - if (new_end == slot) - break; - end_max = mte_get_pivot(mas->node, ++i); - new_end--; - } - - printk("%s: check_spans_slot new_end is now %u\n", __func__, new_end); - return new_end; -} - -static inline int mas_commit_store(struct ma_state *mas, unsigned long r_min, - unsigned long r_max, unsigned char new_end, - void *entry, bool active) -{ - void *this_entry; - unsigned long piv; - unsigned char slot, end, i, j; struct maple_enode *new_node; - printk("Commit store %lu\n", mas->index); - if (new_end > mt_slot_count(mas->node)) - return mas_commit_store_split(mas, entry, new_end); - - piv = mas->last; - this_entry = entry; - end = mas_data_end(mas); - slot = mas_get_slot(mas); - - if ((slot > end) || !end) { - printk("Appending new end %u and %u\n", new_end, end); - // Appending - if (new_end != end + 1) { - mte_set_rcu_slot(mas->node, slot + 1, entry); - mte_set_pivot(mas->node, slot + 1, mas->last); - this_entry = NULL; - piv = mas->index - 1; - } - - mte_set_rcu_slot(mas->node, slot, this_entry); - mte_set_pivot(mas->node, slot, piv); - goto done; - } + printk("Commit\n"); + if (end >= mt_slot_count(mas->node)) + return mas_commit_split(mas, b_node, end); mas_node_cnt(mas, 1); if (mas_is_err(mas)) @@ -1958,53 +1866,13 @@ static inline int mas_commit_store(struct ma_state *mas, unsigned long r_min, new_node = mt_mk_node(mas_next_alloc(mas), mte_node_type(mas->node)); mte_to_node(new_node)->parent = mas_mn(mas)->parent; - printk("Copy 0 - %u\n", slot); - for (i = 0; i <= slot; i++) { - this_entry = mas_get_rcu_slot(mas, i); - mte_set_rcu_slot(new_node, i, this_entry); - piv = mte_get_pivot(mas->node, i); - mte_set_pivot(new_node, i, piv); - } - i--; - - j = i; - printk("r_min %lu\n", r_min); - if (j && mas->index != r_min) { - printk("Stop pivot %u at %lu\n", j - 1, mas->index - 1); - mte_set_pivot(new_node, j - 1, mas->index - 1); - } - - printk("last piv is %lu\n", piv); - printk("Setting %u to %lu\n", j, mas->last); - mte_set_rcu_slot(new_node, j, entry); - mte_set_pivot(new_node, j++, mas->last); - - if (mas->last < r_max ) { - printk("Setting %u\n", j); - mte_set_rcu_slot(new_node, j, this_entry); - mte_set_pivot(new_node, j++, piv); - } - - for (i = slot + 1; i <= end; i++, j++) { - piv = mas_get_safe_pivot(mas, i); - if (mas->last >= piv) - continue; - - printk("Setting %u\n", j); - mte_set_rcu_slot(new_node, j, mas_get_rcu_slot(mas, i)); - if (j < mt_pivot_count(new_node)) - mte_set_pivot(new_node, j, piv); - - } - printk("Replace %p with %p\n", mas_mn(mas), mte_to_node(new_node)); mas->node = new_node; - mt_dump(mas->tree); - mas_replace(mas); -done: - if (mt_is_alloc(mas->tree)) - mas_update_gap(mas, false); - return new_end - end; + printk("Copy out 0-%u\n", end); + mab_mas_cp(b_node, 0, end + 1, mas, 0); + _mas_replace(mas, true, false); + return 2; + } // FIXME: When task_size / page_size -1 works, check to ensure we are @@ -2184,9 +2052,6 @@ static inline bool mas_wr_walk(struct ma_state *mas, unsigned long *range_min, mas->full_cnt++; end = mas_data_end(mas); printk("End of %p is %u type %u\n", mas_mn(mas), end, mt_slots[type] - 1); - if (end < mt_slots[type] - 1) - mas->full_cnt = 0; - if (unlikely(!mas_node_walk(mas, type, range_min, range_max))) return false; @@ -2196,6 +2061,10 @@ static inline bool mas_wr_walk(struct ma_state *mas, unsigned long *range_min, if (ma_is_leaf(type)) return true; + if (end < mt_slots[type] - 1) + mas->full_cnt = 0; + + next = mas_get_rcu_slot(mas, mas_get_slot(mas)); @@ -2310,7 +2179,9 @@ static inline void mas_inactive_rebalance(struct ma_state *mas, unsigned char slot_cnt, slot, split; bool overwrite_left = false; struct ma_state *target = l_mas; + struct maple_node *n_node; + memset(&b_node, 0, sizeof(struct maple_big_node)); MA_STATE(next, r_mas->tree, r_mas->index, r_mas->last); if (l_end <= mt_min_slot_cnt(l_mas->node)) { @@ -2366,6 +2237,7 @@ static inline void mas_inactive_rebalance(struct ma_state *mas, if (overwrite_left) { target = r_mas; } else { + 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)); @@ -2380,6 +2252,7 @@ static inline void mas_inactive_rebalance(struct ma_state *mas, if (!mas_is_none(&next) && !mas_is_start(&next)) { //FIXME: Create new parent and put it in the tree. + n_node->parent = ma_parent_ptr(n_node); } /* Fix up r_mas slot and p_r_mas */ @@ -2537,7 +2410,7 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) // nodes only. // - // Rebalance left + right + node to right of right + // Rebalance left + right + (possibly) node to the right of right mas_inactive_rebalance(mas, &l_mas, &p_l_mas, &r_mas, &p_r_mas); l_slot = mas_get_slot(&l_mas); r_slot = mas_get_slot(&r_mas); @@ -2604,12 +2477,13 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite) { unsigned long r_max, r_min; - unsigned char new_end; + unsigned char end, new_end, slot; void *content = NULL; + struct maple_big_node b_node; int ret = 0; - printk("Start: %s %d store %lu-%lu\n", __func__, __LINE__, + printk("\nStart: %s %d store %lu-%lu\n", __func__, __LINE__, mas->index, mas->last); if (mas_start(mas) || (mas_is_none(mas) || mas->node == MAS_ROOT)) @@ -2643,13 +2517,74 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite /* At this point, we are at the leaf node that needs to be altered. */ /* Calculate needed space */ - new_end = mas_wr_slot_cnt(mas, r_min, r_max, entry); - content = mas_get_rcu_slot(mas, mas_get_slot(mas)); + slot = mas_get_slot(mas); + content = mas_get_rcu_slot(mas, slot); if (!overwrite && ((mas->last > r_max) || content )) { mas_set_err(mas, -EEXIST); goto done; } - ret = mas_commit_store(mas, r_min, r_max, new_end, entry, true); + + /* Expand store of NULL, if necessary */ + if (!entry) { + if (!content) + mas->index = r_min; + if (!mas_get_rcu_slot(mas, slot - 1)) { + if (slot > 1) + mas->index = mte_get_pivot(mas->node, slot - 2) + 1; + else + mas->index = mas->min; + } + if ((r_max != mas->max) && !mas_get_rcu_slot(mas, slot + 1)) + mas->last = mas_get_safe_pivot(mas, slot + 1); + mas_set_slot(mas, --slot); + mas_node_walk(mas, mte_node_type(mas->node), &r_min, &r_max); + printk("store is now %lu-%lu at slot %u\n", mas->index, + mas->last, mas_get_slot(mas)); + } + + end = mas_data_end(mas); + if ((slot > end) || !end) { + // Appending + if (r_min < mas->index) + mte_set_pivot(mas->node, slot++, mas->index - 1); + + mte_set_rcu_slot(mas->node, slot, entry); + mte_set_pivot(mas->node, slot, mas->last); + goto done; + } + + 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); + + if(r_min < mas->index) { + b_node.slot[new_end] = content; + printk("Setting %u %p\n", new_end, content); + b_node.pivot[new_end++] = mas->index - 1; + } + + b_node.slot[new_end] = entry; + printk("Setting %u %p\n", new_end, entry); + b_node.pivot[new_end++] = mas->last; + + if (mas->last < r_max) { + b_node.slot[new_end] = content; + printk("Setting %u %p\n", new_end, content); + b_node.pivot[new_end++] = r_max; + } + + + do { + printk("Skip %u\n", slot); + r_max = mas_get_safe_pivot(mas, ++slot); + } while ((r_max <= mas->last) && (slot < mt_slot_count(mas->node))); + + new_end = mas_mab_cp(mas, slot, mt_slot_count(mas->node), &b_node, + new_end); + mas_commit_b_node(mas, &b_node, new_end); + if (mas_is_err(mas)) + ret = 3; done: if (ret > 2) @@ -3376,6 +3311,7 @@ static inline bool _mas_awalk(struct ma_state *mas, unsigned long size) type = mte_node_type(mas->node); pivot_cnt = mt_pivots[type]; + printk("%d %p[%u]\n", __LINE__, mas_mn(mas), mas_get_slot(mas)); switch (type) { case maple_leaf_64: @@ -3385,6 +3321,7 @@ static inline bool _mas_awalk(struct ma_state *mas, unsigned long size) pivot = _mas_get_safe_pivot(mas, i, type); + printk("%d %p[%u] %lu\n", __LINE__, mas_mn(mas), i, pivot); /* End of data in this leaf */ if (i && !pivot) { if (min > mas->max) @@ -3426,10 +3363,12 @@ next: default: pivot = 0; i = mas_get_slot(mas); + if (i) + min = _mas_get_safe_pivot(mas, i - 1, type) + 1; for (; i <= pivot_cnt; i++) { unsigned long this_gap; - pivot = _mas_get_safe_pivot(mas, i, type); + printk("%d %p[%u] %lu\n", __LINE__, mas_mn(mas), i, pivot); if (i && !pivot) goto ascend; @@ -3443,12 +3382,12 @@ next: min = pivot + 1; if (mas->last < min) { + printk("%lu < %lu\n", mas->last, min); mas_set_err(mas, -EBUSY); return true; } } goto ascend; // exhausted internal node. - break; case maple_dense: @@ -3462,6 +3401,7 @@ descend: if (!ma_is_leaf(type)) { //descend struct maple_enode *next; + printk("%d %p\n", __LINE__, mas_mn(mas)); next = mas_get_rcu_slot(mas, i); mas->min = min; @@ -3476,11 +3416,13 @@ descend: mas_set_slot(mas, i); return found; + ascend: if (mte_is_root(mas->node)) found = true; mas_set_slot(mas, i); + printk("found %s\n", found ? "yes": "no"); return found; } @@ -3645,7 +3587,6 @@ static inline bool mas_rewind_node(struct ma_state *mas); static inline void mas_rev_awalk(struct ma_state *mas, unsigned long size) { struct maple_enode *last = NULL; - unsigned char slot; mas_start(mas); if (mas_is_none(mas)) { @@ -3658,8 +3599,8 @@ static inline void mas_rev_awalk(struct ma_state *mas, unsigned long size) if (mas_is_err(mas)) return; - slot = mas_data_end(mas); - mas_set_slot(mas, slot); + mt_dump(mas->tree); + mas_set_slot(mas, mas_data_end(mas)); /* There are 4 options: @@ -3694,6 +3635,7 @@ static inline void mas_awalk(struct ma_state *mas, unsigned long size) * found the gap. (return, slot != MAPLE_NODE_SLOTS) */ while (!mas_is_err(mas) && !_mas_awalk(mas, size)) { + printk("%d mas node is %p last %p\n", __LINE__, mas_mn(mas), last); if (last == mas->node) mas_skip_node(mas); else @@ -3799,13 +3741,19 @@ static inline int _mas_get_unmapped_area(struct ma_state *mas, mas->index = min; mas->last = max; + printk("%d mas node is %p walk %lu-%lu for %lu\n", __LINE__, + mas_mn(mas), mas->index, mas->last, size); if (forward) mas_awalk(mas, size); else mas_rev_awalk(mas, size); - if (mas_is_err(mas)) + printk("%d mas node is %p\n", __LINE__, mas_mn(mas)); + + if (mas_is_err(mas)) { + printk("error is %u\n", xa_err(mas->node)); return xa_err(mas->node); + } if (mas_get_slot(mas) == MAPLE_NODE_SLOTS) return -EBUSY; @@ -4097,6 +4045,7 @@ static inline bool mas_skip_node(struct ma_state *mas) unsigned char slot; do { + printk("Skip node %p\n", mas_mn(mas)); if (mte_is_root(mas->node)) { slot = mas_get_slot(mas); if (slot > mt_slot_count(mas->node) - 1) { @@ -4105,12 +4054,15 @@ static inline bool mas_skip_node(struct ma_state *mas) } } else { slot = mte_parent_slot(mas->node); + printk("skip parent slot %u\n", slot); mas_ascend(mas); + printk("%d mas node is %p\n", __LINE__, mas_mn(mas)); } } while (slot > mt_slot_count(mas->node) - 1); mas_set_slot(mas, ++slot); mas_update_limits(mas, slot, mte_node_type(mas->node)); + printk("%d mas node is %p\n", __LINE__, mas_mn(mas)); return true; } /* Private @@ -4122,64 +4074,19 @@ static inline bool mas_skip_node(struct ma_state *mas) */ static inline void *mas_erase(struct ma_state *mas) { - unsigned char slot; unsigned long r_max, r_min; void *entry = NULL; - bool new_node = false; printk("Start: erase %lu\n", mas->index); - if (!xa_is_node(mas->tree->ma_root)) { - if (mas->index) - return NULL; - entry = rcu_dereference_protected(mas->tree->ma_root, - lockdep_is_held(&mas->tree->ma_lock)); - rcu_assign_pointer(mas->tree->ma_root, NULL); - return entry; + entry = mas_range_load(mas, &r_min, &r_max, true); + printk("Erase %lu-%lu\n", r_min, r_max); + if (entry) { + mas->index = r_min; + mas->last = r_max; + _mas_store(mas, NULL, true); } - - if (!mas_wr_walk(mas, &r_max, &r_min, entry)) { - if (mas->span_enode) { - // Walk down to the node to get the value - // entry = mas_load maybe? - - // Need to span_store a null? - mas_spanning_store(mas, NULL); - return entry; - } - /* Not a leaf = broken tree. */ - // FIXME, rebuild? - return 0; - } - - /* At this point, we are at the leaf node that needs to be altered. */ - /* Calculate needed space */ - mas_wr_slot_cnt(mas, r_min, r_max, entry); - slot = mas_get_slot(mas); - entry = mas_get_rcu_slot(mas, slot); - - if (!entry) - return entry; - - mte_set_rcu_slot(mas->node, slot, NULL); - - if (slot && !mas_get_rcu_slot(mas, slot - 1)) - new_node = true; - - if ((slot < mt_slot_count(mas->node) - 1) && - !mas_get_rcu_slot(mas, slot + 1)) - new_node = true; - - if (!new_node) - return entry; - - // Need to replace the node as there are two nulls. - mas_node_cnt(mas, 1); - if (mas_is_err(mas)) - return 0; - - new_node = mt_mk_node(mas_next_alloc(mas), mte_node_type(mas->node)); - return entry; + } diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 100e04f55c13..d315d5c40409 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -30139,11 +30139,11 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt) MA_STATE(mas, mt, 0, 0); - +#define DEBUG_REV_RANGE 1 for (i = 0; i < range_cnt; i += 2) { /* Inclusive, Inclusive (with the -1) */ -#if 0 +#if DEBUG_REV_RANGE pr_debug("\t%s: Insert %lu-%lu\n", __func__, range[i] >> 12, (range[i + 1] >> 12) - 1); #endif @@ -30154,7 +30154,7 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt) for (i = 0; i < ARRAY_SIZE(holes); i += 3) { -#if 0 +#if DEBUG_REV_RANGE pr_debug("Search from %lu-%lu for gap %lu should be at %lu\n", min, holes[i+1]>>12, holes[i+2]>>12, holes[i] >> 12); @@ -30162,7 +30162,7 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt) MT_BUG_ON(mt, mas_get_unmapped_area_rev(&mas, min, holes[i+1] >> 12, holes[i+2] >> 12)); -#if 0 +#if DEBUG_REV_RANGE printk("Found %lu %lu\n", mas.index, mas.last); printk("gap %lu %lu\n", (holes[i] >> 12), (holes[i+1] >> 12)); @@ -30174,13 +30174,13 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt) } for (i = 0; i < req_range_cnt; i += 5) { - /* - pr_debug("\tRequest between %lu-%lu size %lu, should get %lu\n", +#if DEBUG_REV_RANGE + pr_debug("\tReverse request between %lu-%lu size %lu, should get %lu\n", req_range[i] >> 12, (req_range[i + 1] >> 12) - 1, req_range[i+2] >> 12, req_range[i+3] >> 12); - */ +#endif check_mtree_alloc_rrange(mt, req_range[i] >> 12, // start req_range[i+1] >> 12, // end @@ -30191,6 +30191,7 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt) mt_validate(mt); } + mt_set_non_kernel(1); mtree_erase(mt, 34148798727); // create a deleted range. check_mtree_alloc_rrange(mt, 0, 34359052173, 210253414, 34148798725, 0, mt); @@ -30312,6 +30313,8 @@ static noinline void check_alloc_range(struct maple_tree *mt) MA_STATE(mas, mt, 0, 0); unsigned long min = 0x565234af2000; for (i = 0; i < ARRAY_SIZE(holes); i+= 3) { + pr_debug("\tGet unmapped %lu-%lu size %lu\n", min >> 12, + holes[i+1] >> 12, holes[i+2] >> 12); MT_BUG_ON(mt, mas_get_unmapped_area(&mas, min >> 12, holes[i+1] >> 12, holes[i+2] >> 12)); @@ -30320,7 +30323,7 @@ static noinline void check_alloc_range(struct maple_tree *mt) mas_reset(&mas); } for (i = 0; i < req_range_cnt; i += 5) { -#if 0 +#if 1 pr_debug("\tTest %d: %lu-%lu size %lu expected %lu\n", i/5, req_range[i] >> 12, req_range[i + 1] >> 12, -- 2.50.1