From d3d79236dd6a1bcca3c9d7d789338aa42936ce56 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Wed, 16 Oct 2019 22:00:41 -0400 Subject: [PATCH] maple_tree: Fix mas_find search. There was a bug when a null occurred in a non-leaf node. This commit addresses that issue as well as trying to fix dead node detection. Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 1 + lib/maple_tree.c | 138 +++++++++++++++++++++---------------- 2 files changed, 79 insertions(+), 60 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 704467372509..06041c4041fe 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -402,6 +402,7 @@ static inline void mas_set_range(struct ma_state *mas, unsigned long start, */ static inline void mas_set(struct ma_state *mas, unsigned long index) { + mas_set_range(mas, index, index); } #endif diff --git a/lib/maple_tree.c b/lib/maple_tree.c index dd0360f634f9..8df4eae5e686 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -3437,12 +3437,22 @@ static inline int mas_safe_slot(struct ma_state *mas, unsigned char *slot, return false; } -static inline int mas_dead_node(struct ma_state *mas, unsigned long index) +static inline bool mas_searchable(struct ma_state *mas) { - if (mas->node == MAS_NONE) - return 0; - if (!mas->node) + return false; + + if (mas_is_none(mas)) + return false; + + if (mas_is_ptr(mas)) + return false; + + return true; +} +static inline int mas_dead_node(struct ma_state *mas, unsigned long index) +{ + if (!mas_searchable(mas)) return 0; if (!mte_dead_node(mas->node)) @@ -3477,51 +3487,60 @@ void *mas_find(struct ma_state *mas, unsigned long max) void *entry = NULL; unsigned long last_piv; unsigned char slot = 0; + unsigned char start_index = mas->index; - if (!mas->node) + if (!mas_searchable(mas)) goto not_found; - if (mas_is_start(mas)) { - if (!_mas_walk(mas)) - return NULL; + do { + if (mas_is_start(mas)) { + _mas_walk(mas); + if (mas_is_ptr(mas)) + entry = mas->tree->ma_root; - if (mas->node == MAS_ROOT) - return mas->tree->ma_root; + if (mas_is_none(mas)) + goto not_found; - do {} while (mas_dead_node(mas, mas->index)); + slot = mas_get_slot(mas); - if (mas->node == MAS_NONE) - goto not_found; + if (slot != MAPLE_NODE_SLOTS) + entry = mte_get_rcu_slot(mas->node, slot); - slot = mas_get_slot(mas); + if (mt_is_empty(entry)) { + last_piv = mas_safe_next_entry(mas, max); + if (mas_is_none(mas)) + goto not_found; - last_piv = mas_get_safe_pivot(mas, slot); - if (slot != MAPLE_NODE_SLOTS) - entry = mte_get_rcu_slot(mas->node, slot); + if (!mte_is_leaf(mas->node)) { + mas_set_slot(mas, 0); + last_piv = mas_first_entry(mas, max); + } + entry = mte_get_rcu_slot(mas->node, slot); + } else { + last_piv = mas_get_safe_pivot(mas, slot); + } - if (entry) { - mas->index = last_piv; + mas->index = mas_get_prev_pivot(mas, slot) + 1; if (last_piv) mas->index--; - goto done; - } - } - if (mas->node == MAS_ROOT) - goto not_found; + } else { - last_piv = mas_safe_next_entry(mas, max); - if (mas->node == MAS_NONE) - goto not_found; + last_piv = mas_safe_next_entry(mas, max); + if (mas_is_none(mas)) + goto not_found; - slot = mas_get_slot(mas); - entry = mte_get_rcu_slot(mas->node, slot); - if (!entry) - goto not_found; + slot = mas_get_slot(mas); + entry = mte_get_rcu_slot(mas->node, slot); + if (!entry) + goto not_found; + + + mas->index = mas_get_prev_pivot(mas, slot) + 1; + } + } while (mas_dead_node(mas, start_index)); - mas->index = mas_get_prev_pivot(mas, slot) + 1; -done: mas->last = last_piv; mas_set_slot(mas, slot + 1); return entry; @@ -3567,39 +3586,38 @@ void *mt_find(struct maple_tree *mt, unsigned long start, rcu_read_lock(); _mas_walk(&mas); - if (mas_is_none(&mas)) - goto done; - - if (mas_is_ptr(&mas)) { - if (!start) - entry = mas.tree->ma_root; - goto done; - } - - do {} while (mas_dead_node(&mas, mas.index)); - - slot = mas_get_slot(&mas); - if (slot != MAPLE_NODE_SLOTS) - entry = mte_get_rcu_slot(mas.node, slot); - + do { + if (mas_is_none(&mas)) + goto done; - if (xa_is_zero(entry)) - entry = NULL; + if (mas_is_ptr(&mas)) { + if (!start) + entry = mas.tree->ma_root; + goto done; + } - if (entry) - goto done; + slot = mas_get_slot(&mas); + if (slot != MAPLE_NODE_SLOTS) + entry = mte_get_rcu_slot(mas.node, slot); retry: - mas_safe_next_entry(&mas, max); - if (mas_is_none(&mas)) - goto done; - + if (xa_is_zero(entry)) + entry = NULL; - slot = mas_get_slot(&mas); - entry = mte_get_rcu_slot(mas.node, slot); - if (xa_is_zero(entry)) - goto retry; + if (mt_is_advanced(entry)) { + mas_safe_next_entry(&mas, max); + if (mas_is_none(&mas)) { + entry = NULL; + } else if (!mte_is_leaf(mas.node)) { + mas_set_slot(&mas, 0); + mas_first_entry(&mas, max); + } + slot = mas_get_slot(&mas); + entry = mte_get_rcu_slot(mas.node, slot); + goto retry; + } + } while (mas_dead_node(&mas, mas.index)); done: rcu_read_unlock(); -- 2.49.0