From 5fda47a79635e234d44339b18ca1ec2d617ce3a5 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 10 Dec 2020 12:16:16 -0500 Subject: [PATCH] maple_tree: Optimize mas_next() and drop unused mas_first_entry() user. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 143 +++++++++++++++-------------------------------- 1 file changed, 44 insertions(+), 99 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 5c104994e77a..5bd61cd196e2 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -1261,16 +1261,20 @@ static inline void mas_update_gap(struct ma_state *mas) * @limit: the maximum index to check. * Returns: The start of the range. */ -static inline unsigned long mas_first_entry(struct ma_state *mas, - unsigned long limit) +static inline void *mas_first_entry(struct ma_state *mas, + unsigned long limit, unsigned long *r_start) { - unsigned long max = mas->max, range_start = mas->min; + unsigned long max; + unsigned long range_start; unsigned char offset; unsigned long *pivots; struct maple_node *mn; void **slots; enum maple_type mt; + void *entry = NULL; + range_start = mas->min; + max = mas->max; while (likely(!mte_is_leaf(mas->node))) { mn = mas_mn(mas); mt = mte_node_type(mas->node); @@ -1284,14 +1288,13 @@ static inline unsigned long mas_first_entry(struct ma_state *mas, mn = mas_mn(mas); mt = mte_node_type(mas->node); slots = ma_slots(mn, mt); - /* 0 or 1 must be set */ offset = 0; - range_start = mas->min; if (range_start > limit) goto none; - if(likely(mas_slot(mas, slots, offset))) + entry = mas_slot(mas, slots, offset); + if(likely(entry)) goto done; pivots = ma_pivots(mn, mt); @@ -1300,14 +1303,16 @@ static inline unsigned long mas_first_entry(struct ma_state *mas, if (range_start > limit) goto none; - if(likely(mas_slot(mas, slots, ++offset))) + entry = mas_slot(mas, slots, offset); + if(likely(entry)) goto done; none: mas->node = MAS_NONE; done: mas->offset = offset; - return range_start; + *r_start = range_start; + return entry; } /* @@ -3759,7 +3764,7 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit) * entry and range_start to the start value for that entry. If there is no * entry, returns false. */ -static inline bool mas_next_nentry(struct ma_state *mas, unsigned long max, +static inline void *mas_next_nentry(struct ma_state *mas, unsigned long max, unsigned long *range_start) { enum maple_type type = mte_node_type(mas->node); @@ -3769,6 +3774,7 @@ static inline bool mas_next_nentry(struct ma_state *mas, unsigned long max, unsigned char count, offset = mas->offset; unsigned long *pivots = ma_pivots(node, type); void **slots; + void *entry = NULL; r_start = mas_safe_min(mas, pivots, offset); if (r_start > max) { @@ -3776,27 +3782,15 @@ static inline bool mas_next_nentry(struct ma_state *mas, unsigned long max, goto no_entry; } - if (type == maple_arange_64) - count = ma_meta_end(node, type); - else - count = mt_pivots[type]; - - - if (!ma_is_leaf(type)) { - if (count < offset) - goto no_entry; - - pivot = _mas_safe_pivot(mas, pivots, offset, type); - goto found; - } - + count = mt_pivots[type]; slots = ma_slots(node, type); while (offset < count) { pivot = pivots[offset]; if (!pivot) goto no_entry; - if (mas_slot(mas, slots, offset)) + entry = mas_slot(mas, slots, offset); + if (entry) goto found; r_start = pivot + 1; @@ -3806,68 +3800,25 @@ static inline bool mas_next_nentry(struct ma_state *mas, unsigned long max, } offset++; } + pivot = _mas_safe_pivot(mas, pivots, offset, type); if (!pivot) goto no_entry; - if (mas_slot(mas, slots, offset)) + entry = mas_slot(mas, slots, offset); + if (entry) goto found; no_entry: *range_start = r_start; - return false; + return NULL; found: mas->last = pivot; *range_start = r_start; mas->offset = offset; - return true; -} - -/* - * - * Returns the pivot which points to the entry with the highest index. - * @mas slot is set to the entry location. - * @limit is the minimum index to check. - * - */ -static inline void *mas_last_entry(struct ma_state *mas, - unsigned long limit) -{ - unsigned long prev_min, prev_max, range_start = 0; - unsigned char slot = 1; - void *entry; - - if (mas_start(mas) || mas_is_none(mas)) - return NULL; - - prev_min = mas->min; - prev_max = mas->max; - while (range_start < limit) { - mas->offset = slot; - if (!mas_next_nentry(mas, limit, &range_start)) { - entry = mas_get_slot(mas, slot - 1); - if (mte_is_leaf(mas->node)) { - mas->last = mte_pivot(mas->node, slot - 1); - mas->index = mte_pivot(mas->node, slot - 2) + 1; - return entry; - } - - mas->max = prev_max; - mas->min = prev_min; - mas->node = entry; - slot = 0; - } else { - slot = mas->offset + 1; - prev_min = prev_max + 1; - if (range_start > prev_min) - prev_min = range_start; - range_start = prev_min; - prev_max = mas->last; - } - } - return NULL; + return entry; } /* @@ -3892,23 +3843,17 @@ static inline void *__mas_next(struct ma_state *mas, unsigned long limit, retry: r_start = mas->last + 1; + if (unlikely(mas->offset >= mt_slots[mt])) + goto next_node; + while (!mas_is_none(mas)) { - if (mas->offset >= mt_slots[mt]) - goto next_node; - - if (!ma_is_leaf(mt) || !mas->offset) { - prev_node = mas->node; - 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, &r_start)) - break; + if (likely(ma_is_leaf(mt))) + entry = mas_next_nentry(mas, limit, &r_start); + else + entry = mas_first_entry(mas, limit, &r_start); - if (r_start > limit) { + if (unlikely((r_start > limit))) { *range_start = limit; mas->index = mas->last = limit; mas->offset = offset; @@ -3916,6 +3861,14 @@ retry: return NULL; } + if (likely(entry)) { + if (unlikely(mas_dead_node(mas, index))) + goto retry; + + *range_start = r_start; + return entry; + } + next_node: prev_node = mas->node; offset = mas->offset; @@ -3924,18 +3877,9 @@ next_node: mt = mte_node_type(mas->node); } - if (mas_is_none(mas)) { - *range_start = limit; - mas->last = limit; - return NULL; - } - - entry = mas_get_slot(mas, mas->offset); - if (mas_dead_node(mas, index)) - goto retry; - - *range_start = r_start; - return entry; + *range_start = limit; + mas->last = limit; + return NULL; } /* @@ -5721,6 +5665,7 @@ void mt_validate_nulls(struct maple_tree *mt) void mt_validate(struct maple_tree *mt) { unsigned char end; + unsigned long r_start; MA_STATE(mas, mt, 0, 0); rcu_read_lock(); @@ -5728,7 +5673,7 @@ void mt_validate(struct maple_tree *mt) if (!mas_searchable(&mas)) goto done; - mas_first_entry(&mas, ULONG_MAX); + mas_first_entry(&mas, ULONG_MAX, &r_start); while (!mas_is_none(&mas)) { if (!mte_is_root(mas.node)) { end = mas_data_end(&mas); -- 2.50.1