From 63ad6e850f3941897dc02ed75f8775d1767420a0 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Tue, 1 Dec 2020 16:30:47 -0500 Subject: [PATCH] maple_tree: optimize some more Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 103 +++++++++++++++++++++++++++++------------------ 1 file changed, 64 insertions(+), 39 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index e5531bf4dfe2..19f87c067991 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -757,10 +757,20 @@ static inline void mas_dup_state(struct ma_state *dst, struct ma_state *src) */ static inline void mas_descend(struct ma_state *mas) { + enum maple_type type; + unsigned long *pivots; + struct maple_node *node; + void **slots; + + node = mas_mn(mas); + type = mte_node_type(mas->node); + pivots = ma_pivots(node, type); + slots = ma_slots(node, type); + if (mas->offset) - mas->min = mas_safe_pivot(mas, mas->offset - 1) + 1; - mas->max = mas_safe_pivot(mas, mas->offset); - mas->node = mas_get_slot(mas, mas->offset); + mas->min = pivots[mas->offset - 1] + 1; + mas->max = _mas_safe_pivot(mas, pivots, mas->offset, type); + mas->node = mas_slot(mas, slots, mas->offset); } static inline void mte_set_gap(const struct maple_enode *mn, @@ -998,10 +1008,10 @@ static inline struct maple_enode *mas_start(struct ma_state *mas) { void *entry = NULL; - if (mas_is_err(mas)) + if (unlikely(mas_is_err(mas))) return NULL; - if (mas_is_start(mas)) { + if (likely(mas_is_start(mas))) { struct maple_enode *root; mas->node = MAS_NONE; @@ -1009,12 +1019,12 @@ static inline struct maple_enode *mas_start(struct ma_state *mas) mas->max = ULONG_MAX; mas->depth = 0; mas->offset = 0; - if (!mas_root(mas)) // empty tree. + if (unlikely(!mas_root(mas))) // empty tree. goto done; root = mte_safe_root(mas_root(mas)); - if (xa_is_node(mas_root(mas))) { + if (unlikely(xa_is_node(mas_root(mas)))) { mas->node = root; } else { // Single entry tree. @@ -1142,18 +1152,20 @@ static inline unsigned long mas_leaf_max_gap(struct ma_state *mas) } static inline unsigned long ma_max_gap(struct maple_node *node, unsigned long *gaps, enum maple_type mt, - unsigned char *offset) + unsigned char *off) { - unsigned char i = ma_meta_end(node, mt); + unsigned char offset, i; unsigned long max_gap = 0; + i = offset = ma_meta_end(node, mt); do { if (gaps[i] > max_gap) { max_gap = gaps[i]; - *offset = i; + offset = i; } } while (i--); + *off = offset; return max_gap; } @@ -1265,27 +1277,30 @@ static inline unsigned long mas_first_entry(struct ma_state *mas, unsigned long limit) { void **slots, *entry; - unsigned long range_start = mas->min; + unsigned long max = mas->max, range_start = mas->min; + unsigned char offset; - while (!mte_is_leaf(mas->node)) { - mas->max = mte_pivot(mas->node, 0); - slots = ma_slots(mte_to_node(mas->node), - mte_node_type(mas->node)); - mas->node = slots[0]; + while (likely(!mte_is_leaf(mas->node))) { + max = mte_pivot(mas->node, 0); + mas->node = mas_get_slot(mas, 0); } + mas->max = max; slots = ma_slots(mte_to_node(mas->node), mte_node_type(mas->node)); - mas->offset = 0; - while ((range_start < limit) && (mas->offset < mt_slot_count(mas->node))) { - entry = mas_slot(mas, slots, mas->offset); + offset = 0; + while ((range_start < limit) && + (offset < mt_slot_count(mas->node))) { + entry = mas_slot(mas, slots, offset); if (entry) - return range_start; - range_start = mas_safe_pivot(mas, mas->offset) + 1; - mas->offset++; + goto done; + range_start = mas_safe_pivot(mas, offset) + 1; + offset++; } mas->node = MAS_NONE; +done: + mas->offset = offset; return range_start; } @@ -1307,7 +1322,7 @@ static inline void mas_adopt_children(struct ma_state *mas, for (offset = 0; offset < mt_slots[type]; offset++) { child = slots[offset]; - if (!child) + if (unlikely(!child)) break; mte_set_parent(child, parent, offset); } @@ -1367,18 +1382,24 @@ static inline void mas_replace(struct ma_state *mas, bool advanced) * */ static inline bool mas_new_child(struct ma_state *mas, struct ma_state *child) + __must_hold(mas->tree->lock) { - enum maple_type mt = mte_node_type(mas->node); - unsigned char offset; + enum maple_type mt; + unsigned char offset, count; struct maple_enode *entry; - void **slots = ma_slots(mte_to_node(mas->node), mt); + struct maple_node *node; + void **slots; - for (offset = mas->offset; offset < mt_slots[mt]; offset++) { + mt = mte_node_type(mas->node); + node = mas_mn(mas); + slots = ma_slots(node, mt); + count = mt_slots[mt]; + for (offset = mas->offset; offset < count; offset++) { entry = slots[offset]; - if (!entry) // end of node data. + if (unlikely(!entry)) // end of node data. break; - if (mte_parent(entry) == mas_mn(mas)) { + if (mte_parent(entry) == node) { mas->offset = offset; mas_dup_state(child, mas); mas->offset = offset + 1; @@ -2952,7 +2973,7 @@ static inline void mas_node_walk(struct ma_state *mas, enum maple_type type, unsigned long *range_min, unsigned long *range_max) { unsigned long *pivots = ma_pivots(mas_mn(mas), type); - unsigned char offset; + unsigned char offset, count; unsigned long min, max; if (unlikely(ma_is_dense(type))) { @@ -2963,10 +2984,11 @@ static inline void mas_node_walk(struct ma_state *mas, enum maple_type type, offset = mas->offset; min = mas_safe_min(mas, pivots, offset); - if (unlikely(offset == mt_pivots[type])) + count = mt_pivots[type]; + if (unlikely(offset == count)) goto max; - while (offset < mt_pivots[type]) { + while (offset < count) { max = pivots[offset]; if (unlikely(!max && offset)) { @@ -3092,7 +3114,7 @@ static inline bool __mas_walk(struct ma_state *mas, unsigned long *range_min, mas->depth++; mas_node_walk(mas, type, range_min, range_max); - if (unlikely(ma_is_leaf(type))) + if (ma_is_leaf(type)) return true; next = mas_get_slot(mas, mas->offset); @@ -3642,12 +3664,13 @@ static inline bool mas_next_nentry(struct ma_state *mas, unsigned long max, enum maple_type type = mte_node_type(mas->node); unsigned long pivot = mas->min; unsigned long r_start; - unsigned char offset = mas->offset; + unsigned char count, offset = mas->offset; unsigned long *pivots = ma_pivots(mas_mn(mas), type); void **slots = ma_slots(mas_mn(mas), type); + count = mt_slots[type]; r_start = mas_safe_min(mas, pivots, offset); - while (offset < mt_slots[type]) { + while (offset < count) { pivot = _mas_safe_pivot(mas, pivots, offset, type); if (!pivot && offset) goto no_entry; @@ -3743,10 +3766,11 @@ static inline void *__mas_next(struct ma_state *mas, unsigned long limit, unsigned char offset = mas->offset; unsigned long index = mas->index; enum maple_type mt = mte_node_type(mas->node); + unsigned long r_start; mas->offset++; retry: - *range_start = mas->last + 1; + r_start = mas->last + 1; while (!mas_is_none(mas)) { if (mas->offset >= mt_slots[mt]) @@ -3754,17 +3778,17 @@ retry: if (!ma_is_leaf(mt) || !mas->offset) { prev_node = mas->node; - *range_start = mas_first_entry(mas, limit); + r_start = mas_first_entry(mas, limit); if (mas_is_none(mas)) { mas->node = prev_node; goto next_node; } } - if (mas_next_nentry(mas, limit, range_start)) + if (mas_next_nentry(mas, limit, &r_start)) break; - if (*range_start > limit) { + if (r_start > limit) { *range_start = limit; mas->index = mas->last = limit; mas->offset = offset; @@ -3790,6 +3814,7 @@ next_node: if (mas_dead_node(mas, index)) goto retry; + *range_start = r_start; return entry; } -- 2.50.1