From 3921c301a090b0b6850489d199503b991854d39a Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Wed, 12 Aug 2020 14:11:49 -0400 Subject: [PATCH] maple_tree: start pushing left for leaves Also, remove dup code Signed-off-by: Liam R. Howlett --- include/trace/events/maple_tree.h | 8 +- lib/maple_tree.c | 187 ++++++++++++++++++++---------- 2 files changed, 132 insertions(+), 63 deletions(-) diff --git a/include/trace/events/maple_tree.h b/include/trace/events/maple_tree.h index 72260a147c07..3348d63342cb 100644 --- a/include/trace/events/maple_tree.h +++ b/include/trace/events/maple_tree.h @@ -30,7 +30,7 @@ TRACE_EVENT(mas_split, __entry->last = mas->last; ), - TP_printk("mas_split:\t%lu-%lu", + TP_printk("\t%lu-%lu", (unsigned long) __entry->index, (unsigned long) __entry->last ) @@ -54,7 +54,7 @@ TRACE_EVENT(mas_spanning_store, __entry->last = mas->last; ), - TP_printk("mas_spanning_store:\t%lu-%lu", + TP_printk("\t%lu-%lu", (unsigned long) __entry->index, (unsigned long) __entry->last ) @@ -78,7 +78,7 @@ TRACE_EVENT(mas_rebalance, __entry->last = mas->last; ), - TP_printk("mas_rebalance:\t%lu-%lu", + TP_printk("\t%lu-%lu", (unsigned long) __entry->index, (unsigned long) __entry->last ) @@ -102,7 +102,7 @@ TRACE_EVENT(mas_spanning_rebalance, __entry->last = mas->last; ), - TP_printk("mas_spanning_rebalance:\t%lu-%lu", + TP_printk("\t%lu-%lu", (unsigned long) __entry->index, (unsigned long) __entry->last ) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index dc78f3ddc88f..a6bd76444f55 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1812,39 +1812,68 @@ static inline void mast_topiary(struct maple_subtree_state *mast) mat_add(mast->destroy, mas_get_rcu_slot(mast->orig_r, slot)); } +static inline void mast_rebalance_next(struct maple_subtree_state *mast, + struct maple_enode *old_r) +{ + unsigned char b_end = mast->bn->b_end; + unsigned char end = mas_data_end(mast->orig_r); + + mas_mab_cp(mast->orig_r, 0, end, mast->bn, b_end); + mat_add(mast->free, old_r); + mast->orig_r->last = mast->orig_r->max; + if (old_r == mast->orig_l->node) + mast->orig_l->node = mast->orig_r->node; +} + +static inline void mast_rebalance_prev(struct maple_subtree_state *mast, + struct maple_enode *old_l) +{ + unsigned char end = mas_data_end(mast->orig_l); + unsigned char b_end = mast->bn->b_end; + + mab_shift_right(mast->bn, end + 1); + mas_mab_cp(mast->orig_l, 0, end, mast->bn, 0); + mat_add(mast->free, old_l); + if (mast->orig_r->node == old_l) + mast->orig_r->node = mast->orig_l->node; + mast->l->min = mast->orig_l->min; + mast->orig_l->index = mast->orig_l->min; + mast->bn->b_end = end + 1 + b_end; + mas_set_slot(mast->l, mas_get_slot(mast->l) + end + 1); +} +static inline bool mast_sibling_rebalance_left(struct maple_subtree_state *mast) +{ + struct maple_enode *old_r = mast->orig_r->node; + struct maple_enode *old_l = mast->orig_l->node; + + if (mas_prev_sibling(mast->orig_l)) { + mast_rebalance_prev(mast, old_l); + return true; + } + if (mas_next_sibling(mast->orig_r)) { + mast_rebalance_next(mast, old_r); + return true; + } + return false; +} + /* - * mast_rebalance_from_siblings() - Rebalance from nodes with the same parents. + * mast_sibling_rebalance_right() - Rebalance from nodes with the same parents. * Check the right side, then the left. Data is copied into the @mast->bn. * * @mast: The maple_subtree_state. */ -static inline bool mast_rebalance_from_siblings(struct maple_subtree_state *mast) +static inline bool mast_sibling_rebalance_right(struct maple_subtree_state *mast) { - struct maple_enode *left = mast->orig_l->node; - struct maple_enode *right = mast->orig_r->node; - unsigned char b_end = mast->bn->b_end; - unsigned char end; + struct maple_enode *old_r = mast->orig_r->node; + struct maple_enode *old_l = mast->orig_l->node; if (mas_next_sibling(mast->orig_r)) { - end = mas_data_end(mast->orig_r); - mas_mab_cp(mast->orig_r, 0, end, mast->bn, b_end); - mat_add(mast->free, right); - if (right == left) - mast->orig_l->node = mast->orig_r->node; - mast->orig_r->last = mast->orig_r->max; + mast_rebalance_next(mast, old_r); return true; } if (mas_prev_sibling(mast->orig_l)) { - end = mas_data_end(mast->orig_l); - mab_shift_right(mast->bn, end + 1); - mas_mab_cp(mast->orig_l, 0, end, mast->bn, 0); - mat_add(mast->free, left); - if (right == left) - mast->orig_r->node = mast->orig_l->node; - mast->l->min = mast->orig_l->min; - mast->orig_l->index = mast->orig_l->min; - mast->bn->b_end = end + 1 + b_end; - mas_set_slot(mast->l, mas_get_slot(mast->l) + end + 1); + mast_rebalance_prev(mast, old_l); return true; } return false; @@ -1854,27 +1883,21 @@ static inline void mas_prev_node(struct ma_state *mas, unsigned long limit); static inline unsigned long mas_next_node(struct ma_state *mas, unsigned long max); /* - * mast_rebalance_from_cousins() - Rebalance from nodes with different parents. + * mast_cousin_rebalance_right() - Rebalance from nodes with different parents. * Check the right side, then the left. Data is copied into the @mast->bn. * * @mast: The maple_subtree_state. */ -static inline bool mast_rebalance_from_cousins(struct maple_subtree_state *mast) +static inline bool mast_cousin_rebalance_right(struct maple_subtree_state *mast) { - unsigned char end, b_end; - struct maple_enode *left = mast->orig_l->node; - struct maple_enode *right = mast->orig_r->node; + struct maple_enode *old_l = mast->orig_l->node; + struct maple_enode *old_r = mast->orig_r->node; mas_set_slot(mast->orig_r, mte_parent_slot(mast->orig_r->node)); mas_next_node(mast->orig_r, ULONG_MAX); if (!mas_is_none(mast->orig_r)) { - end = mas_data_end(mast->orig_r); - mas_mab_cp(mast->orig_r, 0, end, mast->bn, mast->bn->b_end); - mast->orig_r->last = mast->orig_r->max; - mat_add(mast->free, right); - if (right == left) - mast->orig_l->node = mast->orig_r->node; + mast_rebalance_next(mast, old_r); return true; } mas_dup_state(mast->orig_r, mast->orig_l); @@ -1887,19 +1910,8 @@ static inline bool mast_rebalance_from_cousins(struct maple_subtree_state *mast) return false; } - mat_add(mast->free, left); - if (right == left) - mast->orig_r->node = mast->orig_l->node; - mas_set_slot(mast->orig_l, 0); - mast->orig_l->index = mast->orig_l->min; - end = mas_data_end(mast->orig_l); - b_end = mast->bn->b_end; - mab_shift_right(mast->bn, end + 1); - mas_mab_cp(mast->orig_l, 0, end, mast->bn, 0); - mast->l->min = mast->orig_l->min; - mast->bn->b_end = b_end + end + 1; - mas_set_slot(mast->l, mas_get_slot(mast->l) + end + 1); + mast_rebalance_prev(mast, old_l); return true; } /* @@ -2309,8 +2321,8 @@ static inline int mas_spanning_rebalance(struct ma_state *mas, break; // Try to get enough data for the next iteration. - if (!mast_rebalance_from_siblings(mast)) - if (!mast_rebalance_from_cousins(mast)) + if (!mast_sibling_rebalance_right(mast)) + if (!mast_cousin_rebalance_right(mast)) break; if (!count) count++; @@ -2387,7 +2399,6 @@ static inline int mas_rebalance(struct ma_state *mas, r_mas.last = r_mas.index = r_mas.max; } else { - mas_prev_sibling(&l_mas); shift = mas_data_end(&l_mas) + 1; mab_shift_right(b_node, shift); @@ -2520,7 +2531,57 @@ static inline int mas_split(struct ma_state *mas, mas_wmb_replace(mas, mast.free, NULL); return 1; } +static inline int mas_cnt_positive(struct ma_state *mas) +{ + if (mas->full_cnt < 0) + return mas->full_cnt * -1; + return mas->full_cnt; +} +static inline bool mas_fits_left(struct ma_state *mas, + struct maple_big_node *b_node) +{ + unsigned char slot_total = b_node->b_end; + unsigned char end, space; + char empty_cnt = mas_cnt_positive(mas); + struct maple_subtree_state mast; + + MA_STATE(l_mas, mas->tree, mas->index, mas->last); + mas_dup_state(&l_mas, mas); + l_mas.depth = mas->depth; + + if (!mas_prev_sibling(&l_mas)) + return false; + + end = mas_data_end(&l_mas); + slot_total += end; + + space = 2 * mt_slot_count(mas->node) - 1; + if (mas->max == ULONG_MAX) + space--; + + if (slot_total > space) + return false; + + empty_cnt++; + + mas_node_cnt(mas, 1 + empty_cnt * 2); + if (mas_is_err(mas)) + return false; + + b_node->b_end++; + mab_shift_right(b_node, end + 1); + mas_mab_cp(&l_mas, 0, end, b_node, 0); + b_node->b_end = slot_total + 2; + l_mas.index = l_mas.last = l_mas.min; + mas->index = mas->last = mas->max; + + mast.orig_l = &l_mas; + mast.orig_r = mas; + mast.bn = b_node; + mas_spanning_rebalance(mas, &mast, empty_cnt); + return true; +} static inline int mas_commit_b_node(struct ma_state *mas, struct maple_big_node *b_node) { @@ -2531,8 +2592,16 @@ static inline int mas_commit_b_node(struct ma_state *mas, (mas->tree->ma_height > 1)) return mas_rebalance(mas, b_node); - if (b_node->b_end >= mt_slot_count(mas->node)) + + if (b_node->b_end >= mt_slot_count(mas->node)) { + if (mas_fits_left(mas, b_node)) + return 1; + + if (mas_is_err(mas)) + return 0; + return mas_split(mas, b_node); + } mas_node_cnt(mas, 1); if (mas_is_err(mas)) @@ -2708,12 +2777,6 @@ static inline bool mas_node_walk(struct ma_state *mas, enum maple_type type, mas_set_slot(mas, i); return ret; } -static inline int mas_cnt_positive(struct ma_state *mas) -{ - if (mas->full_cnt < 0) - return mas->full_cnt * -1; - return mas->full_cnt; -} static inline void mas_cnt_full(struct ma_state *mas) { if (mas->full_cnt < 0) @@ -2895,14 +2958,13 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) trace_mas_spanning_store(mas); // Leaf nodes if (mas->full_cnt > 0) - node_cnt = 1 + mas->full_cnt * 2; // For split upwards. + node_cnt = mas->full_cnt; // For split upwards. else - node_cnt = 1 + -1 * mas->full_cnt * 2; // For rebalance upwards. - + node_cnt = -1 * mas->full_cnt; // For rebalance upwards. /* Node rebalancing may occur due to this store, so there may be two new * entries per level plus a new root. */ - node_cnt += 1 + mas->tree->ma_height * 3; + node_cnt += 1 + mas->tree->ma_height * 2; mas_node_cnt(mas, node_cnt); if (mas_is_err(mas)) return 0; @@ -2959,6 +3021,13 @@ static inline int mas_spanning_store(struct ma_state *mas, void *entry) // Calc the number of iterations of combining and splitting that will // need to occur. count = mas_cnt_positive(mas) + mas->tree->ma_height - mas->depth + 1; + if (!count) { + mt_dump(mas->tree); + printk("%p insert %lu-%lu\n", mas_mn(mas), mas->index, mas->last); + printk("%u + %u - %u + 1\n", mas_cnt_positive(mas), + mas->tree->ma_height, mas->depth); + } + BUG_ON(!count); // Combine l_mas and r_mas and split them up evenly again. return mas_spanning_rebalance(mas, &mast, count); -- 2.50.1