From 93a686506a154597c3c6abf18493c01a5ff8edd0 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 14 Sep 2020 16:04:04 -0400 Subject: [PATCH] maple_tree: Optimize mas_awalk Search from the back of the node without finding the end of the data first. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 173 ++++++++++++++++++++++++------------------ lib/test_maple_tree.c | 2 +- 2 files changed, 102 insertions(+), 73 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 059205758392..660629c06ea4 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -477,32 +477,56 @@ static inline void mas_set_offset(struct ma_state *mas, int offset) } /* - * ma_get_pivot() - Get the pivot of a node. + * ma_get_pivots() - Get the pivot of a node. * @node - the maple node. - * @piv - the pivot to retrieve. * @type - the node type. * * Returns: The value of the @piv in the @node. */ -static inline unsigned long ma_get_pivot(const struct maple_node *node, - unsigned char piv, enum maple_type type) +static inline unsigned long *ma_get_pivots(struct maple_node *node, + enum maple_type type) { switch (type) { case maple_arange_64: - return node->ma64.pivot[piv]; + return node->ma64.pivot; case maple_range_64: case maple_leaf_64: - return node->mr64.pivot[piv]; + return node->mr64.pivot; case maple_dense: default: - return 0; + return NULL; + } +} + +static inline unsigned long *ma_get_gaps(struct maple_node *node, + enum maple_type type) +{ + switch (type) { + case maple_arange_64: + return node->ma64.gap; + case maple_range_64: + case maple_leaf_64: + case maple_dense: + default: + return NULL; } } static inline unsigned long _mte_get_pivot(const struct maple_enode *mn, unsigned char piv, enum maple_type type) { - return ma_get_pivot(mte_to_node(mn), piv, type); + struct maple_node *node = mte_to_node(mn); + + switch (type) { + case maple_arange_64: + return node->ma64.pivot[piv]; + case maple_range_64: + case maple_leaf_64: + return node->mr64.pivot[piv]; + case maple_dense: + default: + return 0; + } } static inline unsigned long mte_get_pivot(const struct maple_enode *mn, @@ -1413,7 +1437,9 @@ static inline void mas_mab_cp(struct ma_state *mas, unsigned char mas_start, mte_node_type(mas->node)); for (i = mas_start, j = mab_start; i <= mas_end; i++, j++) { - b_node->slot[j] = slots[i]; + b_node->slot[j] = rcu_dereference_protected(slots[i], + lockdep_is_held(&mas->tree->ma_lock)); + if (!mte_is_leaf(mas->node) && mt_is_alloc(mas->tree)) b_node->gap[j] = mte_get_gap(mas->node, i); @@ -3474,88 +3500,91 @@ void *mas_prev(struct ma_state *mas, unsigned long min) } EXPORT_SYMBOL_GPL(mas_prev); -static inline bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) +bool _mas_rev_awalk(struct ma_state *mas, unsigned long size) { + struct maple_node *node = mas_mn(mas); enum maple_type type = mte_node_type(mas->node); - unsigned char slot = mas_offset(mas); - unsigned long max, min = mas->min; - unsigned long gap = 0; - bool found = false; + unsigned long *pivots, *gaps; + void **slots; + unsigned char offset = mas_offset(mas); + unsigned long max; + unsigned long gap, min; - max = _mas_safe_pivot(mas, slot, type); - switch (type) { - case maple_leaf_64: - default: - do { - min = mas_safe_min(mas, slot); - /* last is below this range */ - if (mas->last < min) - goto next_slot; + if (ma_is_dense(type)) { // dense nodes. + mas_set_offset(mas, (unsigned char)(mas->index - mas->min)); + return true; + } - /* index is above this range.*/ - if (mas->index > max) { - mas_set_err(mas, -EBUSY); - return false; - } + pivots = ma_get_pivots(node, type); + slots = ma_get_slots(node, type); + if (!ma_is_leaf(type)) + gaps = ma_get_gaps(node, type); - if (ma_is_leaf(type)) { - if (mas_get_slot(mas, slot)) - goto next_slot; - - gap = max - min + 1; - } else { - gap = mte_get_gap(mas->node, slot); + if (offset == mt_pivots[type]) { + // Initial start, walk until the end of the data. + while (--offset) { + if (pivots[offset]) { + if (pivots[offset] < mas->max) + offset++; + break; } + } + } - if (size > mas->last - min + 1) - goto next_slot; + min = _mas_safe_pivot(mas, offset, type) + 1; + do { + max = min - 1; + min = mas_safe_min(mas, offset); + if (mas->last < min) + continue; - if (size > gap) - goto next_slot; + if (mas->index > max) { + mas_set_err(mas, -EBUSY); + return false; + } - if (ma_is_leaf(type)) { - mas->min = min; - mas->max = min + gap - 1; - found = true; - } - break; + if (!ma_is_leaf(type)) + gap = gaps[offset]; + else if (rcu_dereference_protected(slots[offset], + lockdep_is_held(&mas->tree->ma_lock))) + continue; // no gap in leaf. + else + gap = max - min + 1; -next_slot: - if (!slot) - goto ascend; + if (size > gap) // gap too small + continue; - max = min - 1; - } while (slot--); - break; + if (size > mas->last - min + 1) + continue; - case maple_dense: - slot = mas->index - mas->min; - found = true; + if (ma_is_leaf(type)) { + mas->min = min; + mas->max = min + gap - 1; + mas_set_offset(mas, offset); + return true; + } break; - } + } while (offset--); - if (!ma_is_leaf(type)) { //descend - struct maple_enode *next; - - next = mas_get_slot(mas, slot); - mas->min = min; - mas->max = max; - if (!next) - goto ascend; - - mas->node = next; - slot = mas_data_end(mas); - max = mas_safe_pivot(mas, slot); + if (offset >= mt_slots[type]) { // node exhausted. + offset = 0; + goto ascend; } - mas_set_offset(mas, slot); - return found; + //descend + mas->node = rcu_dereference_protected(slots[offset], + lockdep_is_held(&mas->tree->ma_lock)); + mas->min = min; + mas->max = max; + mas_set_offset(mas, mt_pivot_count(mas->node)); + return false; + ascend: if (mte_is_root(mas->node)) mas_set_err(mas, -EBUSY); - mas_set_offset(mas, slot); - return found; + mas_set_offset(mas, offset); + return false; } static inline bool _mas_awalk(struct ma_state *mas, unsigned long size) @@ -3743,7 +3772,7 @@ static inline void mas_rev_awalk(struct ma_state *mas, unsigned long size) { struct maple_enode *last = NULL; - mas_set_offset(mas, mas_data_end(mas)); + mas_set_offset(mas, mt_pivot_count(mas->node)); /* There are 4 options: * go to child (descend) diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 25846872432b..74d56e8c4100 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -31686,7 +31686,7 @@ static noinline void check_alloc_rev_range(struct maple_tree *mt) holes[i+2] >> 12)); #if DEBUG_REV_RANGE pr_debug("Found %lu %lu\n", mas.index, mas.last); - pr_deubg("gap %lu %lu\n", (holes[i] >> 12), + pr_debug("gap %lu %lu\n", (holes[i] >> 12), (holes[i+1] >> 12)); #endif MT_BUG_ON(mt, mas.last + 1 != (holes[i+1] >> 12)); -- 2.50.1