From c73932906ee44eab5ff46556b3f694edf5bc5ed6 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Sun, 6 Dec 2020 19:57:40 -0500 Subject: [PATCH] maple_tree: Optimize _mas_store() slow path When entering the slow path, only zero what is necessary after the data is set. Also, don't calculate things twice when not necessary Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 103 ++++++++++++++++++++++++++--------------------- 1 file changed, 58 insertions(+), 45 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index b33dcfec3789..93ae822f17ae 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1565,7 +1565,7 @@ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start, unsigned long *gaps = NULL; int i = mas_start, j = mab_start; - for (i = mas_start, j = mab_start; i <= mas_end; i++, j++) { + for (; i <= mas_end; i++, j++) { b_node->pivot[j] = _mas_safe_pivot(mas, pivots, i, mt); if ((mas->max == b_node->pivot[j]) || @@ -1575,17 +1575,16 @@ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start, } } - memcpy(b_node->slot + mab_start, - slots + mas_start, - sizeof(void *) * (j - mab_start)); + b_node->b_end = j; + j -= mab_start; + + memcpy(b_node->slot + mab_start, slots + mas_start, sizeof(void *) * j); if (!mte_is_leaf(mas->node) && mt_is_alloc(mas->tree)) { gaps = ma_gaps(node, mt); - memcpy(b_node->gap + mab_start, - gaps + mas_start, - sizeof(unsigned long) * (j - mab_start)); + memcpy(b_node->gap + mab_start, gaps + mas_start, + sizeof(unsigned long) * j); } - b_node->b_end = j; } /* @@ -1609,34 +1608,31 @@ static inline void mab_mas_cp(struct maple_big_node *b_node, if (mab_end - mab_start > mt_pivots[mt]) mab_end--; - for (i = mab_start; i <= mab_end; i++, j++) { - if (j && !b_node->pivot[i]) - break; - - pivots[j] = b_node->pivot[i]; - } + i = mab_start; + pivots[j++] = b_node->pivot[i++]; + do { + pivots[j++] = b_node->pivot[i++]; + } while (i <= mab_end && likely(b_node->pivot[i])); memcpy(slots, b_node->slot + mab_start, sizeof(void *) * (i - mab_start)); - if (!ma_is_leaf(mt) && mt_is_alloc(mas->tree)) { + mas->max = b_node->pivot[i - 1]; + if (likely(!ma_is_leaf(mt) && mt_is_alloc(mas->tree))) { unsigned long max_gap = 0; - unsigned char offset = 15, tmp; - unsigned char end = i - mab_start; - - gaps = ma_gaps(mas_mn(mas), mt); - for (tmp = 0; tmp < end; tmp++) { - gaps[tmp] = b_node->gap[mab_start + tmp]; - if (gaps[tmp] > max_gap) { - offset = tmp; - max_gap = gaps[tmp]; + unsigned char offset = 15; + unsigned char end = j - 1; + + gaps = ma_gaps(node, mt); + do { + gaps[--j] = b_node->gap[--i]; + if (gaps[j] > max_gap) { + offset = j; + max_gap = gaps[j]; } - } -// memcpy(gaps, b_node->gap + mab_start, -// sizeof(unsigned long) * end); - ma_set_meta(node, mt, offset, end - 1); + } while (j); + ma_set_meta(node, mt, offset, end); } - mas->max = b_node->pivot[--i]; } /* @@ -1711,11 +1707,13 @@ static inline unsigned char mas_store_b_node(struct ma_state *mas, void *entry, unsigned char end) { unsigned char slot = mas->offset; - void *contents = mas_get_slot(mas, slot); + void *contents; unsigned char b_end = 0; // Possible underflow of piv will wrap back to 0 before use. unsigned long piv = mas->min - 1; - unsigned long *pivots = ma_pivots(mas_mn(mas), b_node->type); + struct maple_node *node = mas_mn(mas); + enum maple_type mt = mte_node_type(mas->node); + unsigned long *pivots = ma_pivots(node, mt); // Copy start data up to insert. if (slot) { @@ -1724,6 +1722,7 @@ static inline unsigned char mas_store_b_node(struct ma_state *mas, piv = b_node->pivot[b_end - 1]; } + contents = mas_slot(mas, ma_slots(node, mt), slot); // Handle range starting after old range if (piv + 1 < mas->index) { b_node->slot[b_end] = contents; @@ -1738,10 +1737,10 @@ static inline unsigned char mas_store_b_node(struct ma_state *mas, b_node->pivot[b_end] = mas->last; // Handle new range ending before old range ends - piv = _mas_safe_pivot(mas, pivots, slot, b_node->type); + piv = _mas_safe_pivot(mas, pivots, slot, mt); if (piv > mas->last) { if (piv == ULONG_MAX) - mas_bulk_rebalance(mas, b_node->b_end, b_node->type); + mas_bulk_rebalance(mas, b_node->b_end, mt); b_node->slot[++b_end] = contents; if (!contents) @@ -1756,7 +1755,7 @@ static inline unsigned char mas_store_b_node(struct ma_state *mas, // Handle range overwrites do { - piv = _mas_safe_pivot(mas, pivots, ++slot, b_node->type); + piv = _mas_safe_pivot(mas, pivots, ++slot, mt); } while ((piv <= mas->last) && (slot <= end)); // Copy end data to the end of the node. @@ -2638,9 +2637,9 @@ static inline void mast_fill_bnode(struct maple_subtree_state *mast, { bool cp = true; struct maple_enode *old = mas->node; - unsigned char split; + unsigned char split, zero; - memset(mast->bn, 0, sizeof(struct maple_big_node)); + mast->bn->b_end = 0; if (mte_is_root(mas->node)) { cp = false; } else { @@ -2665,6 +2664,13 @@ static inline void mast_fill_bnode(struct maple_subtree_state *mast, mast->bn, mast->bn->b_end); mast->bn->b_end--; mast->bn->type = mte_node_type(mas->node); + + zero = MAPLE_BIG_NODE_SLOTS - mast->bn->b_end - 2; + memset(mast->bn->gap + mast->bn->b_end + 1, 0, + sizeof(unsigned long) * zero); + memset(mast->bn->slot + mast->bn->b_end + 1, 0, sizeof(void*) * zero--); + memset(mast->bn->pivot + mast->bn->b_end + 1, 0, + sizeof(unsigned long) * zero); } @@ -2857,15 +2863,16 @@ static inline int mas_commit_b_node(struct ma_state *mas, unsigned char end) { struct maple_enode *new_node; + unsigned char b_end = b_node->b_end; + enum maple_type b_type = b_node->type; - if ((b_node->b_end < mt_min_slots[b_node->type]) && + if ((b_end < mt_min_slots[b_type]) && (!mte_is_root(mas->node)) && (mas_mt_height(mas) > 1)) return mas_rebalance(mas, b_node); - if (b_node->b_end >= mt_slots[b_node->type]) { + if (b_end >= mt_slots[b_type]) return mas_split(mas, b_node); - } if (mas_reuse_node(mas, b_node, end)) goto reused_node; @@ -2878,7 +2885,7 @@ static inline int mas_commit_b_node(struct ma_state *mas, mte_to_node(new_node)->parent = mas_mn(mas)->parent; mas->node = new_node; - mab_mas_cp(b_node, 0, b_node->b_end, mas); + mab_mas_cp(b_node, 0, b_end, mas); mas_replace(mas, false); reused_node: mas_update_gap(mas); @@ -3432,11 +3439,12 @@ try_node_store: static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite) { unsigned long r_max, r_min; - unsigned char end; + unsigned char end, zero; void *content = NULL; struct maple_big_node b_node; void **slots; enum maple_type mt; + struct maple_node *node; int ret = 0; @@ -3465,9 +3473,10 @@ 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 */ mt = mte_node_type(mas->node); - slots = ma_slots(mas_mn(mas), mt); + node = mas_mn(mas); + slots = ma_slots(node, mt); content = slots[mas->offset]; - if (!overwrite && ((mas->last > r_max) || content)) { + if (!overwrite && (content || (mas->last > r_max))) { mas_set_err(mas, -EEXIST); return content; } @@ -3482,7 +3491,7 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite mas->last = r_max; // if this one is null the next and prev are not. } else { - unsigned long *pivots = ma_pivots(mas_mn(mas), mt); + unsigned long *pivots = ma_pivots(node, mt); // Check next slot if we are overwriting the end. if ((mas->last == r_max) && !slots[mas->offset + 1]) { if (mas->offset < mt_pivots[mt] - 1 && @@ -3521,11 +3530,15 @@ static inline void *_mas_store(struct ma_state *mas, void *entry, bool overwrite return content; /* Slow path. */ - memset(&b_node, 0, sizeof(struct maple_big_node)); b_node.type = mte_node_type(mas->node); b_node.b_end = mas_store_b_node(mas, &b_node, entry, end); b_node.min = mas->min; + zero = MAPLE_BIG_NODE_SLOTS - b_node.b_end - 1; + memset(b_node.slot + b_node.b_end + 1, 0, sizeof(void *) * zero--); + memset(b_node.pivot + b_node.b_end + 1, 0, + sizeof(unsigned long) * zero); + if (!mas_commit_b_node(mas, &b_node, end)) return NULL; -- 2.50.1