From c52785a8b50b15cb91d6225ca2ad625d3cd2f9ba Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Wed, 31 Jul 2019 21:08:19 -0400 Subject: [PATCH] maple_tree: Add restarts for interaters on dead nodes. also fix the testcase for the iterators for the zero entry test. Signed-off-by: Liam R. Howlett --- lib/maple_tree.c | 33 +++++++++++++++++++++++++++------ lib/test_maple_tree.c | 7 +++++++ 2 files changed, 34 insertions(+), 6 deletions(-) diff --git a/lib/maple_tree.c b/lib/maple_tree.c index e88a09faaabf..140735796602 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -559,7 +559,7 @@ static inline struct maple_enode *_ma_get_rcu_slot( struct maple_enode *p = __ma_get_rcu_slot(mn, slot, type); if (mt_dead_node(mn)) - return NULL; + return MAS_START; return p; } @@ -2237,6 +2237,7 @@ mas_next_nentry (struct ma_state *mas, unsigned long max, unsigned long *piv) no_entry: return false; } + static inline unsigned long mas_next_entry (struct ma_state *mas, unsigned long max) { @@ -2262,6 +2263,18 @@ mas_next_entry (struct ma_state *mas, unsigned long max) } return pivot; } +static inline unsigned long +mas_safe_next_entry (struct ma_state *mas, unsigned long max) +{ + unsigned long piv; +retry: + piv = mas_next_entry(mas, max); + if (mas->node == MAS_NONE) + return piv; + if (mas_dead_node(mas, mas->index)) + goto retry; + return piv; +} /* Private * Combine nulls with the same pivot value * @@ -2699,7 +2712,10 @@ void *mas_find(struct ma_state *mas, unsigned long max) if (mas->node == MAS_START) { _mas_walk(mas); + do {} while(mas_dead_node(mas, mas->index)); + slot = ma_get_slot(mas); + last_piv = ma_get_safe_pivot(mas, slot); if (slot != MAPLE_NODE_SLOTS) entry = ma_get_rcu_slot(mas->node, slot); @@ -2712,16 +2728,17 @@ void *mas_find(struct ma_state *mas, unsigned long max) } } - last_piv = mas_next_entry(mas, max); - if (mas->node == MAS_NONE) { + last_piv = mas_safe_next_entry(mas, max); + if (mas->node == MAS_NONE) goto not_found; - } + slot = ma_get_slot(mas); entry = ma_get_rcu_slot(mas->node, slot); if (!entry) goto not_found; + mas->index = ma_get_prev_pivot(mas, slot) + 1; done: mas->last = last_piv; @@ -2749,10 +2766,13 @@ static inline void *mt_find(struct maple_tree *mt, unsigned long start, rcu_read_lock(); _mas_walk(&mas); + do {} while (mas_dead_node(&mas, mas.index)); + slot = ma_get_slot(&mas); if (slot != MAPLE_NODE_SLOTS) entry = ma_get_rcu_slot(mas.node, slot); + if (xa_is_zero(entry)) entry = NULL; @@ -2760,10 +2780,11 @@ static inline void *mt_find(struct maple_tree *mt, unsigned long start, goto done; retry: - mas_next_entry(&mas, max); + mas_safe_next_entry(&mas, max); if (mas.node == MAS_NONE) goto done; + slot = ma_get_slot(&mas); entry = ma_get_rcu_slot(mas.node, slot); if (xa_is_zero(entry)) @@ -2791,7 +2812,7 @@ static inline void *mt_find_after(struct maple_tree *mt, unsigned long *index, _mas_walk(&mas); retry: ma_set_slot(&mas, ma_get_slot(&mas) + 1); - mas_next_entry(&mas, max); + mas_safe_next_entry(&mas, max); if (mas.node == MAS_NONE) goto done; diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index 103ac70cf239..4b4998cc8291 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -412,9 +412,16 @@ static noinline void check_find(struct maple_tree *mt) val = 1; } + val = 0; max = 300; // A value big enough to include XA_ZERO_ENTRY at 64. mt_for_each(mt, entry, index, max) { MT_BUG_ON(mt, xa_mk_value(val) != entry); + val <<= 2; + if (val == 64) // Skip zero entry. + val <<= 2; + // For zero check. + if (!val) + val = 1; } -- 2.50.1