From 412e81f93e4b54ab9364d32d680c4824d6f00a5e Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 1 Aug 2019 14:09:25 -0400 Subject: [PATCH] maple_tree: Add mas_pause for pausing iterator. Also add testcases for the pause function. Signed-off-by: Liam R. Howlett --- include/linux/maple_tree.h | 15 ++++++++++----- lib/maple_tree.c | 27 ++++++++++++++++++++++----- lib/test_maple_tree.c | 22 ++++++++++++++++++++++ 3 files changed, 54 insertions(+), 10 deletions(-) diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 9a5821a67ebd..9e5956511cf8 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -168,17 +168,18 @@ struct maple_tree { #define DEFINE_MTREE(name) \ struct maple_tree name = MTREE_INIT(name, 0) -#define mtree_lock(mt) spin_lock(&mt->ma_lock) -#define mtree_unlock(mt) spin_unlock(&mt->ma_lock) +#define mtree_lock(mt) spin_lock((&mt->ma_lock)) +#define mtree_unlock(mt) spin_unlock((&mt->ma_lock)) + void mtree_init(struct maple_tree *mt, unsigned int ma_flags); void *mtree_load(struct maple_tree *mt, unsigned long index); int mtree_insert(struct maple_tree *mt, unsigned long index, void *entry, gfp_t gfp); -int mtree_insert_range(struct maple_tree mt*, unsigned long first, +int mtree_insert_range(struct maple_tree *mt, unsigned long first, unsigned long last, void *entry, gfp_t gfp); -int mtree_erase(struct maple_tree mt*, unsigned long index); -void mtree_destroy(struct maple_tree mt*); +int mtree_erase(struct maple_tree *mt, unsigned long index); +void mtree_destroy(struct maple_tree *mt); /** * mtree_empty() - Determine if a tree has any present entries. @@ -224,6 +225,10 @@ struct ma_state { struct maple_node *alloc; /* Allocated nodes for this operation */ }; +#define mas_lock(mas) spin_lock(&((mas)->tree->ma_lock)) +#define mas_unlock(mas) spin_unlock(&((mas)->tree->ma_lock)) + + /* * Special values for ma_state.node. * MAS_START means we have not searched the tree. diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 38929095837c..e8c055d67249 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -2697,8 +2697,8 @@ static inline int mas_dead_node(struct ma_state *mas, unsigned long index) return 1; } -/* mas_find: - * Finds first entry that overlaps the range. +/** + * mas_find - Find the first entry that overlaps the range. * If mas->node is root, finds mas->index and returns the value. If the * value is null, returns the next non-null range. * If mas->node is not root, finds the next range after the range that @@ -2706,7 +2706,7 @@ static inline int mas_dead_node(struct ma_state *mas, unsigned long index) * * If an entry exists, last and index are updated accordingly. * - * returns entry or null + * returns entry or null and set mas->node to MAS_NONE. */ void *mas_find(struct ma_state *mas, unsigned long max) { @@ -2749,7 +2749,7 @@ void *mas_find(struct ma_state *mas, unsigned long max) mas->index = ma_get_prev_pivot(mas, slot) + 1; done: mas->last = last_piv; - ma_set_slot(mas, slot+1); + ma_set_slot(mas, slot + 1); return entry; not_found: @@ -2758,7 +2758,24 @@ not_found: } - +/** + * mas_pause() - Pause a mas_find/mas_for_each to drop the lock. + * + * Some users need to pause a walk and drop the lock they're holding in + * order to yield to a higher priority thread or carry out an operation + * on an entry. Those users should call this function before they drop + * the lock. It resets the @mas to be suitable for the next iteration + * of the loop after the user has reacquired the lock. If most entries + * found during a walk require you to call xas_pause(), the xa_for_each() + * iterator may be more appropriate. + * + */ +void mas_pause(struct ma_state *mas) +{ + mas_reset(mas); + mas->index = mas->last + 1; + mas->last++; +} /* mt_find() - Search from start up until an entry is found. * * Note: Does not return the zero entry. diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c index ac74e7adce38..61c02271052a 100644 --- a/lib/test_maple_tree.c +++ b/lib/test_maple_tree.c @@ -429,6 +429,28 @@ static noinline void check_find(struct maple_tree *mt) val = 1; } + + /* Test mas_pause */ + val = 0; + mas_reset(&mas); + mas.index = val; + mas_for_each(&mas, entry, ULONG_MAX) { + if (val != 64) + MT_BUG_ON(mt, xa_mk_value(val) != entry); + else + MT_BUG_ON(mt, entry != XA_ZERO_ENTRY); + val <<= 2; + // For zero check. + if (!val) + val = 1; + + if (val == 256) { + mas_pause(&mas); + mas_unlock(&mas); + mas_lock(&mas); + } + } + val = 0; max = 300; // A value big enough to include XA_ZERO_ENTRY at 64. mt_for_each(mt, entry, index, max) { -- 2.50.1