From 6eb5550cd73ab4c169f677713f4762c760e0b742 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 7 Dec 2020 16:02:52 -0500 Subject: [PATCH] maple_tree: A bunch of optimizations Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 67 ++++++++++++++++++++++++++---------------------- 1 file changed, 37 insertions(+), 30 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 74645b54f571a..38b7bdee6124c 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3010,10 +3010,12 @@ static inline void mas_node_walk(struct ma_state *mas, enum maple_type type, index = mas->index; max = pivots[offset]; - if (index <= max) + if (unlikely(index <= max)) goto done; + if (unlikely(!max && offset)) goto max; + offset++; min = max + 1; while (offset < count) { @@ -3972,10 +3974,12 @@ static bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) pivots = ma_pivots(node, type); slots = ma_slots(node, type); - offset = mas->offset; - if (!ma_is_leaf(type)) + if (ma_is_leaf(type)) + gaps = NULL; + else gaps = ma_gaps(node, type); + offset = mas->offset; min = mas_safe_min(mas, pivots, offset); while (mas->last < min) // Skip out of bounds. min = mas_safe_min(mas, pivots, --offset); @@ -3984,7 +3988,7 @@ static bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) index = mas->index; while (index <= max) { gap = 0; - if (!ma_is_leaf(type)) + if (gaps) gap = gaps[offset]; else if (!mas_slot(mas, slots, offset)) gap = max - min + 1; @@ -3993,14 +3997,15 @@ static bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) if ((size <= gap) && (size <= mas->last - min + 1)) break; - if (ma_is_leaf(type)) { + if (!gaps) { // Skip the next slot, it cannot be a gap. if (offset < 2) goto ascend; offset -= 2; max = pivots[offset]; - goto next; + min = mas_safe_min(mas, pivots, offset); + continue; } } @@ -4009,7 +4014,6 @@ static bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) offset--; max = min - 1; -next: min = mas_safe_min(mas, pivots, offset); } @@ -4177,9 +4181,6 @@ retry: static inline bool mas_search_cont(struct ma_state *mas, unsigned long index, unsigned long max, void *entry) { - if (mas_is_start(mas)) - return true; - if (index >= max) return false; @@ -4189,6 +4190,9 @@ static inline bool mas_search_cont(struct ma_state *mas, unsigned long index, if (mas_is_err(mas)) return false; + if (mas_is_start(mas)) + return true; + if (entry) return false; @@ -4243,7 +4247,7 @@ static inline bool mas_rewind_node(struct ma_state *mas) return true; } -static void mas_rev_awalk(struct ma_state *mas, unsigned long size) +static bool mas_rev_awalk(struct ma_state *mas, unsigned long size) { struct maple_enode *last = NULL; @@ -4256,11 +4260,14 @@ static void mas_rev_awalk(struct ma_state *mas, unsigned long size) * found the gap. (return, slot != MAPLE_NODE_SLOTS) */ while (!_mas_rev_awalk(mas, size)) { - if (last == mas->node) - mas_rewind_node(mas); - else + if (last == mas->node) { + if (!mas_rewind_node(mas)) + return false; + } else { last = mas->node; + } } + return true; } /* Skip this slot in the parent. */ @@ -4428,10 +4435,7 @@ int mas_get_empty_area_rev(struct ma_state *mas, unsigned long min, // 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))) + if (unlikely(!mas_rev_awalk(mas, size))) return xa_err(mas->node); if (unlikely(mas->offset == MAPLE_NODE_SLOTS)) @@ -4542,22 +4546,23 @@ no_gap: static inline void *mas_range_load(struct ma_state *mas, unsigned long *range_min, unsigned long *range_max) { - void *entry = NULL; + unsigned long index = mas->index; + if (mas_is_none(mas)) + mas->node = MAS_START; + + if (_mas_walk(mas, range_min, range_max)) + if (unlikely(mas->node == MAS_ROOT)) + return mas_root(mas); retry: - if (_mas_walk(mas, range_min, range_max)) { - if (mas->last == 0 && mas_is_ptr(mas)) - return mte_safe_root(mas->tree->ma_root); + if (mas_dead_node(mas, index)) + goto retry; - if (mas->offset >= MAPLE_NODE_SLOTS) - return NULL; + if (mas->offset == MAPLE_NODE_SLOTS) + return NULL; // Not found. - entry = mas_get_slot(mas, mas->offset); - if (mte_dead_node(mas->node)) - goto retry; - } + return mas_get_slot(mas, mas->offset); - return entry; } void *mas_load(struct ma_state *mas) @@ -4588,7 +4593,9 @@ static void *_mas_next(struct ma_state *mas, unsigned long limit, mas->index = *range_start; if (entry) return entry; - } else if (!mas_searchable(mas)) + } + + if (unlikely(!mas_searchable(mas))) return NULL; entry = __mas_next(mas, limit, range_start); -- 2.50.1