From 335e83c185addcb28c615f893fc3a72287c2bdd8 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Mon, 14 Sep 2020 12:47:22 -0400 Subject: [PATCH] maple_tree: Rework mas_next Attempt to optimize mas_next Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 2 +- lib/maple_tree.c | 93 +++++++++++--------------------------- 2 files changed, 27 insertions(+), 68 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index a3264f6e8272..5239bd1469e7 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -362,7 +362,7 @@ static inline void mt_init(struct maple_tree *mt) static inline bool mt_in_rcu(struct maple_tree *mt) { - return mt->ma_flags & MAPLE_USE_RCU; + return !!(mt->ma_flags & MAPLE_USE_RCU); } /** * mt_clear_in_rcu() - Switch the tree to non-RCU mode. diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 66fb2a429be4..059205758392 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -963,7 +963,7 @@ static inline struct maple_enode *mas_start(struct ma_state *mas) void *entry = NULL; if (mas_is_err(mas)) - goto done; + return NULL; if (mas_is_start(mas)) { struct maple_enode *root; @@ -977,7 +977,9 @@ static inline struct maple_enode *mas_start(struct ma_state *mas) root = mte_safe_root(mas->tree->ma_root); - if (!xa_is_node(mas->tree->ma_root)) { + if (xa_is_node(mas->tree->ma_root)) { + mas->node = root; + } else { // Single entry tree. if (mas->index > 0) goto done; @@ -985,8 +987,6 @@ static inline struct maple_enode *mas_start(struct ma_state *mas) entry = mas->tree->ma_root; mas->node = MAS_ROOT; mas_set_offset(mas, MAPLE_NODE_SLOTS); - } else { - mas->node = root; } } @@ -1155,53 +1155,6 @@ static inline void mas_update_gap(struct ma_state *mas) mas_parent_gap(mas, pslot, max_gap); } - -/* - * mas_first_node() - Finds the first node in mas->node and returns the pivot, - * mas->max if no node is found. Node is returned as mas->node which may be - * MAS_NONE. - * - * Note, if we descend to a leaf, then the slot is not valid. - * - * @mas: maple state - * @limit: The maximum index to consider valid. - */ -static inline unsigned long mas_first_node(struct ma_state *mas, - unsigned long limit) -{ - int offset = mas_offset(mas) - 1; - enum maple_type mt = mte_node_type(mas->node); - unsigned long pivot, min = mas->min; - void **slots = ma_get_slots(mte_to_node(mas->node), mt); - - while (++offset < mt_slots[mt]) { - struct maple_enode *mn; - - pivot = _mas_safe_pivot(mas, offset, mt); - if (pivot > limit) - goto no_entry; - - mn = rcu_dereference(slots[offset]); - if (!mn) { - min = pivot + 1; - continue; - } - - // Non-leaf nodes need to descend. - if (!mte_is_leaf(mas->node)) { - mas->max = pivot; - mas->min = min; - mas->node = mn; - } - mas_set_offset(mas, offset); - return pivot; - } - -no_entry: - mas->node = MAS_NONE; - return mas->max; -} - /* * mas_first_entry() - * Returns the pivot which points to the entry with the * lowest index. @@ -1212,25 +1165,31 @@ no_entry: static inline unsigned long mas_first_entry(struct ma_state *mas, unsigned long limit) { - unsigned long pivot; + void **slots, *entry; + int offset = 0; + unsigned long pivot = mas->min; - while (1) { - pivot = mas_first_node(mas, limit); - if (mas_is_none(mas)) - return pivot; + while (!mte_is_leaf(mas->node)) { + mas->max = mte_get_pivot(mas->node, 0); + slots = ma_get_slots(mte_to_node(mas->node), + mte_node_type(mas->node)); + mas->node = slots[0]; + } - if (mte_is_leaf(mas->node)) { - // Get the leaf slot. - mas_set_offset(mas, 0); - mas_first_node(mas, limit); - if (mas_is_none(mas)) - return limit; - return mas_safe_pivot(mas, - mas_offset(mas)); - } + slots = ma_get_slots(mte_to_node(mas->node), mte_node_type(mas->node)); - mas_set_offset(mas, 0); + while ((pivot < limit) && (offset < mt_slot_count(mas->node))) { + pivot = mas_safe_pivot(mas, offset); + entry = rcu_dereference(slots[offset]); + if (entry) { + mas_set_offset(mas, offset); + return pivot; + } + offset++; } + + mas->node = MAS_NONE; + return pivot; } /* @@ -3421,7 +3380,7 @@ retry: struct maple_enode *last_node = mas->node; slot = mas_offset(mas); - if (slot > mt_slot_count(mas->node)) + if (slot >= mt_slot_count(mas->node)) goto next_node; if (!mte_is_leaf(mas->node) || !mas_offset(mas)) { -- 2.50.1