From 33760b4118b114ef9f181d2ebebbabd49e612a16 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 3 Dec 2020 12:03:10 -0500 Subject: [PATCH] maple_tree: Optimize mas_get_empty_area{_rev}() etc Take advantage of locality of reference by not dereferencing in some functions. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 149 ++++++++++++++++++++++++----------------------- 1 file changed, 75 insertions(+), 74 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 18a87263fee3..781432f3b291 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -822,7 +822,7 @@ ascend: } no_parent: - if (ma_is_root(a_node)) { + if (unlikely(ma_is_root(a_node))) { parent_is_root: if (!set_min) min = 0; @@ -2945,23 +2945,26 @@ exists: bool mas_is_span_wr(struct ma_state *mas, unsigned long piv, enum maple_type type, void *entry) { - if (piv > mas->last) // Contained in this pivot + unsigned long last = mas->last; + unsigned long max = mas->max; + + if (piv > last) // Contained in this pivot return false; if (unlikely(ma_is_leaf(type))) { - if (mas->last < mas->max) // Fits in the node, but may span slots. + if (last < max) // Fits in the node, but may span slots. return false; - if ((mas->last == mas->max) && entry) // Writes to the end of the node but not null. + if ((last == max) && entry) // Writes to the end of the node but not null. return false; - } else if ((piv == mas->last) && entry) { + } else if ((piv == last) && entry) { return false; } /* Writing ULONG_MAX is not a spanning write regardless of the value * being written as long as the range fits in the node. */ - if ((mas->last == ULONG_MAX) && (mas->last == mas->max)) + if ((last == ULONG_MAX) && (last == max)) return false; trace_mas_is_span_wr(mas, piv, entry); @@ -2974,7 +2977,7 @@ static inline void mas_node_walk(struct ma_state *mas, enum maple_type type, { unsigned long *pivots = ma_pivots(mas_mn(mas), type); unsigned char offset, count; - unsigned long min, max; + unsigned long min, max, index; if (unlikely(ma_is_dense(type))) { (*range_max) = (*range_min) = mas->index; @@ -2988,6 +2991,7 @@ static inline void mas_node_walk(struct ma_state *mas, enum maple_type type, if (unlikely(offset == count)) goto max; + index = mas->index; while (offset < count) { max = pivots[offset]; @@ -2995,7 +2999,7 @@ static inline void mas_node_walk(struct ma_state *mas, enum maple_type type, break; } - if (mas->index <= max) + if (index <= max) goto done; min = max + 1; @@ -3881,13 +3885,17 @@ void *mas_prev(struct ma_state *mas, unsigned long min) } EXPORT_SYMBOL_GPL(mas_prev); -bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) +static inline bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) { enum maple_type type = mte_node_type(mas->node); struct maple_node *node = mas_mn(mas); unsigned long *pivots, *gaps = NULL; void **slots; - unsigned long gap, max, min; + unsigned long gap, max, min, index; + unsigned char offset; + + if (unlikely(mas_is_err(mas))) + return true; if (ma_is_dense(type)) { // dense nodes. mas->offset = (unsigned char)(mas->index - mas->min); @@ -4267,49 +4275,12 @@ static int mas_fill_gap(struct ma_state *mas, void *entry, unsigned char slot, return 0; } -void mas_set_fwd_index(struct ma_state *mas, unsigned long size) -{ - unsigned long min = mas->min; - unsigned char slot = mas->offset; - // At this point, mas->node points to the right node and we have a - // slot that has a sufficient gap. - if (slot) - min = mte_pivot(mas->node, slot - 1) + 1; - - mas->min = min; - mas->max = mas_safe_pivot(mas, slot); - - if (mas->index < min) - mas->index = min; - mas->last = mas->index + size - 1; -} - -void mas_set_rev_index(struct ma_state *mas, unsigned long size) -{ - unsigned long gap_max = mas->max; // in-tree gap. - unsigned long range_max = mas->last; // range window we are searching in. - - // rev_awalk has set mas->min and mas->max to the gap values. - // If the maximum is outside the window we are searching, then use the - // last location in the search. - // mas->max and mas->min is the range of the gap. - // mas->index and mas->last are currently set to the search range. - - // Trim the upper limit to the max. - if (gap_max > range_max) - gap_max = range_max; - - mas->last = gap_max; - mas->index = mas->last - size + 1; -} - -static void _mas_sparse_area(struct ma_state *mas, - unsigned long min, unsigned long max, - unsigned long size, bool fwd) +static inline void _mas_sparse_area(struct ma_state *mas, unsigned long min, + unsigned long max, unsigned long size, bool fwd) { unsigned long start = 0; - if (!mas_is_none(mas)) + if (!unlikely(mas_is_none(mas))) start++; // mas_is_ptr if (start < min) @@ -4324,52 +4295,82 @@ static void _mas_sparse_area(struct ma_state *mas, mas->index = max; } -static inline int _mas_get_empty_area(struct ma_state *mas, - unsigned long min, unsigned long max, - unsigned long size, bool forward) +int mas_get_empty_area(struct ma_state *mas, unsigned long min, + unsigned long max, unsigned long size) { + unsigned char offset; + unsigned long *pivots; + enum maple_type mt; mas_start(mas); // Empty set. if (mas_is_none(mas) || mas_is_ptr(mas)) { - _mas_sparse_area(mas, min, max, size, forward); + _mas_sparse_area(mas, min, max, size, true); return 0; } // The start of the window can only be within these values. mas->index = min; mas->last = max; + mas_awalk(mas, size); - if (forward) - mas_awalk(mas, size); - else - mas_rev_awalk(mas, size); - - - if (mas_is_err(mas)) + if (unlikely(mas_is_err(mas))) return xa_err(mas->node); - if (mas->offset == MAPLE_NODE_SLOTS) + offset = mas->offset; + if (unlikely(offset == MAPLE_NODE_SLOTS)) return -EBUSY; - if (forward) - mas_set_fwd_index(mas, size); - else - mas_set_rev_index(mas, size); + mt = mte_node_type(mas->node); + pivots = ma_pivots(mas_mn(mas), mt); + if (offset) + mas->min = pivots[offset - 1] + 1; - return 0; -} + if (offset < mt_pivots[mt]) + mas->max = pivots[offset]; -int mas_get_empty_area(struct ma_state *mas, unsigned long min, - unsigned long max, unsigned long size) -{ - return _mas_get_empty_area(mas, min, max, size, true); + if (mas->index < mas->min) + mas->index = mas->min; + + mas->last = mas->index + size - 1; + return 0; } int mas_get_empty_area_rev(struct ma_state *mas, unsigned long min, unsigned long max, unsigned long size) { - return _mas_get_empty_area(mas, min, max, size, false); + mas_start(mas); + + // Empty set. + if (mas_is_none(mas) || mas_is_ptr(mas)) { + _mas_sparse_area(mas, min, max, size, false); + return 0; + } + + // The start of the window can only be within these values. + mas->index = min; + mas->last = max; + mas_rev_awalk(mas, size); + + + if (unlikely(mas_is_err(mas))) + return xa_err(mas->node); + + if (unlikely(mas->offset == MAPLE_NODE_SLOTS)) + return -EBUSY; + + /* mas_rev_awalk() has set mas->min and mas->max to the gap values. If + * the maximum is outside the window we are searching, then use the last + * location in the search. + * mas->max and mas->min is the range of the gap. + * mas->index and mas->last are currently set to the search range. + */ + // Trim the upper limit to the max. + if (mas->max <= mas->last) + mas->last = mas->max; + + mas->index = mas->last - size + 1; + return 0; } /* @@ -4434,7 +4435,7 @@ static inline int mas_rev_alloc(struct ma_state *mas, unsigned long min, { int ret = 0; - ret = _mas_get_empty_area(mas, min, max, size, false); + ret = mas_get_empty_area_rev(mas, min, max, size); if (ret) return ret; -- 2.50.1