From 89f499f35c11af61ba7075ddc23209d10805a25a Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 18 May 2023 10:55:14 -0400 Subject: maple_tree: add format option to mt_dump() Allow different formatting strings to be used when dumping the tree. Currently supports hex and decimal. Link: https://lkml.kernel.org/r/20230518145544.1722059-6-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: David Binderman Cc: Peng Zhang Cc: Sergey Senozhatsky Cc: Vernon Yang Cc: Wei Yang Signed-off-by: Andrew Morton --- include/linux/maple_tree.h | 9 +++++++-- 1 file changed, 7 insertions(+), 2 deletions(-) (limited to 'include/linux/maple_tree.h') diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 1fadb5f5978b..140fb271be4a 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -670,10 +670,15 @@ void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max); #ifdef CONFIG_DEBUG_MAPLE_TREE +enum mt_dump_format { + mt_dump_dec, + mt_dump_hex, +}; + extern atomic_t maple_tree_tests_run; extern atomic_t maple_tree_tests_passed; -void mt_dump(const struct maple_tree *mt); +void mt_dump(const struct maple_tree *mt, enum mt_dump_format format); void mt_validate(struct maple_tree *mt); void mt_cache_shrink(void); #define MT_BUG_ON(__tree, __x) do { \ @@ -681,7 +686,7 @@ void mt_cache_shrink(void); if (__x) { \ pr_info("BUG at %s:%d (%u)\n", \ __func__, __LINE__, __x); \ - mt_dump(__tree); \ + mt_dump(__tree, mt_dump_hex); \ pr_info("Pass: %u Run:%u\n", \ atomic_read(&maple_tree_tests_passed), \ atomic_read(&maple_tree_tests_run)); \ -- cgit v1.2.3 From f0a1f866aba1ca62ef6f17d1c441eba65f2d6845 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 18 May 2023 10:55:15 -0400 Subject: maple_tree: add debug BUG_ON and WARN_ON variants Add debug macros to dump the maple state and/or the tree for both warning and bug_on calls. Link: https://lkml.kernel.org/r/20230518145544.1722059-7-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: David Binderman Cc: Peng Zhang Cc: Sergey Senozhatsky Cc: Vernon Yang Cc: Wei Yang Signed-off-by: Andrew Morton --- include/linux/maple_tree.h | 100 +++++++++++++++++++++++++++++++++++++++++++-- lib/maple_tree.c | 34 ++++++++++++++- 2 files changed, 129 insertions(+), 5 deletions(-) (limited to 'include/linux/maple_tree.h') diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 140fb271be4a..204d7941a39e 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -482,13 +482,13 @@ static inline void mas_init(struct ma_state *mas, struct maple_tree *tree, } /* Checks if a mas has not found anything */ -static inline bool mas_is_none(struct ma_state *mas) +static inline bool mas_is_none(const struct ma_state *mas) { return mas->node == MAS_NONE; } /* Checks if a mas has been paused */ -static inline bool mas_is_paused(struct ma_state *mas) +static inline bool mas_is_paused(const struct ma_state *mas) { return mas->node == MAS_PAUSE; } @@ -679,6 +679,8 @@ extern atomic_t maple_tree_tests_run; extern atomic_t maple_tree_tests_passed; void mt_dump(const struct maple_tree *mt, enum mt_dump_format format); +void mas_dump(const struct ma_state *mas); +void mas_wr_dump(const struct ma_wr_state *wr_mas); void mt_validate(struct maple_tree *mt); void mt_cache_shrink(void); #define MT_BUG_ON(__tree, __x) do { \ @@ -695,8 +697,100 @@ void mt_cache_shrink(void); atomic_inc(&maple_tree_tests_passed); \ } \ } while (0) + +#define MAS_BUG_ON(__mas, __x) do { \ + atomic_inc(&maple_tree_tests_run); \ + if (__x) { \ + pr_info("BUG at %s:%d (%u)\n", \ + __func__, __LINE__, __x); \ + mas_dump(__mas); \ + mt_dump((__mas)->tree, mt_dump_hex); \ + pr_info("Pass: %u Run:%u\n", \ + atomic_read(&maple_tree_tests_passed), \ + atomic_read(&maple_tree_tests_run)); \ + dump_stack(); \ + } else { \ + atomic_inc(&maple_tree_tests_passed); \ + } \ +} while (0) + +#define MAS_WR_BUG_ON(__wrmas, __x) do { \ + atomic_inc(&maple_tree_tests_run); \ + if (__x) { \ + pr_info("BUG at %s:%d (%u)\n", \ + __func__, __LINE__, __x); \ + mas_wr_dump(__wrmas); \ + mas_dump((__wrmas)->mas); \ + mt_dump((__wrmas)->mas->tree, mt_dump_hex); \ + pr_info("Pass: %u Run:%u\n", \ + atomic_read(&maple_tree_tests_passed), \ + atomic_read(&maple_tree_tests_run)); \ + dump_stack(); \ + } else { \ + atomic_inc(&maple_tree_tests_passed); \ + } \ +} while (0) + +#define MT_WARN_ON(__tree, __x) ({ \ + int ret = !!(__x); \ + atomic_inc(&maple_tree_tests_run); \ + if (ret) { \ + pr_info("WARN at %s:%d (%u)\n", \ + __func__, __LINE__, __x); \ + mt_dump(__tree, mt_dump_hex); \ + pr_info("Pass: %u Run:%u\n", \ + atomic_read(&maple_tree_tests_passed), \ + atomic_read(&maple_tree_tests_run)); \ + dump_stack(); \ + } else { \ + atomic_inc(&maple_tree_tests_passed); \ + } \ + unlikely(ret); \ +}) + +#define MAS_WARN_ON(__mas, __x) ({ \ + int ret = !!(__x); \ + atomic_inc(&maple_tree_tests_run); \ + if (ret) { \ + pr_info("WARN at %s:%d (%u)\n", \ + __func__, __LINE__, __x); \ + mas_dump(__mas); \ + mt_dump((__mas)->tree, mt_dump_hex); \ + pr_info("Pass: %u Run:%u\n", \ + atomic_read(&maple_tree_tests_passed), \ + atomic_read(&maple_tree_tests_run)); \ + dump_stack(); \ + } else { \ + atomic_inc(&maple_tree_tests_passed); \ + } \ + unlikely(ret); \ +}) + +#define MAS_WR_WARN_ON(__wrmas, __x) ({ \ + int ret = !!(__x); \ + atomic_inc(&maple_tree_tests_run); \ + if (ret) { \ + pr_info("WARN at %s:%d (%u)\n", \ + __func__, __LINE__, __x); \ + mas_wr_dump(__wrmas); \ + mas_dump((__wrmas)->mas); \ + mt_dump((__wrmas)->mas->tree, mt_dump_hex); \ + pr_info("Pass: %u Run:%u\n", \ + atomic_read(&maple_tree_tests_passed), \ + atomic_read(&maple_tree_tests_run)); \ + dump_stack(); \ + } else { \ + atomic_inc(&maple_tree_tests_passed); \ + } \ + unlikely(ret); \ +}) #else -#define MT_BUG_ON(__tree, __x) BUG_ON(__x) +#define MT_BUG_ON(__tree, __x) BUG_ON(__x) +#define MAS_BUG_ON(__mas, __x) BUG_ON(__x) +#define MAS_WR_BUG_ON(__mas, __x) BUG_ON(__x) +#define MT_WARN_ON(__tree, __x) WARN_ON(__x) +#define MAS_WARN_ON(__mas, __x) WARN_ON(__x) +#define MAS_WR_WARN_ON(__mas, __x) WARN_ON(__x) #endif /* CONFIG_DEBUG_MAPLE_TREE */ #endif /*_LINUX_MAPLE_TREE_H */ diff --git a/lib/maple_tree.c b/lib/maple_tree.c index dfa0271101d2..ff16b6c0ac08 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -240,12 +240,12 @@ static inline void mas_set_err(struct ma_state *mas, long err) mas->node = MA_ERROR(err); } -static inline bool mas_is_ptr(struct ma_state *mas) +static inline bool mas_is_ptr(const struct ma_state *mas) { return mas->node == MAS_ROOT; } -static inline bool mas_is_start(struct ma_state *mas) +static inline bool mas_is_start(const struct ma_state *mas) { return mas->node == MAS_START; } @@ -7246,4 +7246,34 @@ done: } EXPORT_SYMBOL_GPL(mt_validate); +void mas_dump(const struct ma_state *mas) +{ + pr_err("MAS: tree=%p enode=%p ", mas->tree, mas->node); + if (mas_is_none(mas)) + pr_err("(MAS_NONE) "); + else if (mas_is_ptr(mas)) + pr_err("(MAS_ROOT) "); + else if (mas_is_start(mas)) + pr_err("(MAS_START) "); + else if (mas_is_paused(mas)) + pr_err("(MAS_PAUSED) "); + + pr_err("[%u] index=%lx last=%lx\n", mas->offset, mas->index, mas->last); + pr_err(" min=%lx max=%lx alloc=%p, depth=%u, flags=%x\n", + mas->min, mas->max, mas->alloc, mas->depth, mas->mas_flags); + if (mas->index > mas->last) + pr_err("Check index & last\n"); +} +EXPORT_SYMBOL_GPL(mas_dump); + +void mas_wr_dump(const struct ma_wr_state *wr_mas) +{ + pr_err("WR_MAS: node=%p r_min=%lx r_max=%lx\n", + wr_mas->node, wr_mas->r_min, wr_mas->r_max); + pr_err(" type=%u off_end=%u, node_end=%u, end_piv=%lx\n", + wr_mas->type, wr_mas->offset_end, wr_mas->node_end, + wr_mas->end_piv); +} +EXPORT_SYMBOL_GPL(mas_wr_dump); + #endif /* CONFIG_DEBUG_MAPLE_TREE */ -- cgit v1.2.3 From 7f2f9dc16fee59afdec2df8c794e97c36e387257 Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 18 May 2023 10:55:17 -0400 Subject: maple_tree: change RCU checks to WARN_ON() instead of BUG_ON() If RCU is enabled and the tree isn't locked, just warn the user and avoid crashing the kernel. Link: https://lkml.kernel.org/r/20230518145544.1722059-9-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: David Binderman Cc: Peng Zhang Cc: Sergey Senozhatsky Cc: Vernon Yang Cc: Wei Yang Signed-off-by: Andrew Morton --- include/linux/maple_tree.h | 4 ++-- 1 file changed, 2 insertions(+), 2 deletions(-) (limited to 'include/linux/maple_tree.h') diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 204d7941a39e..ed92abf4c1fb 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -616,7 +616,7 @@ static inline void mt_clear_in_rcu(struct maple_tree *mt) return; if (mt_external_lock(mt)) { - BUG_ON(!mt_lock_is_held(mt)); + WARN_ON(!mt_lock_is_held(mt)); mt->ma_flags &= ~MT_FLAGS_USE_RCU; } else { mtree_lock(mt); @@ -635,7 +635,7 @@ static inline void mt_set_in_rcu(struct maple_tree *mt) return; if (mt_external_lock(mt)) { - BUG_ON(!mt_lock_is_held(mt)); + WARN_ON(!mt_lock_is_held(mt)); mt->ma_flags |= MT_FLAGS_USE_RCU; } else { mtree_lock(mt); -- cgit v1.2.3 From 6169b553195a193c52a675e45a9578f595fe194f Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 18 May 2023 10:55:37 -0400 Subject: maple_tree: add mas_next_range() and mas_find_range() interfaces Some users of the maple tree may want to move to the next range in the tree, even if it stores a NULL. This family of function provides that functionality by advancing one slot at a time and returning the result, while mas_contiguous() will iterate over the range and stop on encountering the first NULL. Link: https://lkml.kernel.org/r/20230518145544.1722059-29-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: David Binderman Cc: Peng Zhang Cc: Sergey Senozhatsky Cc: Vernon Yang Cc: Wei Yang Signed-off-by: Andrew Morton --- include/linux/maple_tree.h | 3 +- lib/maple_tree.c | 172 ++++++++++++++++++++++++++++++++------------- 2 files changed, 124 insertions(+), 51 deletions(-) (limited to 'include/linux/maple_tree.h') diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index ed92abf4c1fb..9d040043858a 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -455,6 +455,7 @@ void *mas_erase(struct ma_state *mas); int mas_store_gfp(struct ma_state *mas, void *entry, gfp_t gfp); void mas_store_prealloc(struct ma_state *mas, void *entry); void *mas_find(struct ma_state *mas, unsigned long max); +void *mas_find_range(struct ma_state *mas, unsigned long max); void *mas_find_rev(struct ma_state *mas, unsigned long min); int mas_preallocate(struct ma_state *mas, gfp_t gfp); bool mas_is_err(struct ma_state *mas); @@ -467,6 +468,7 @@ int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries); void *mas_prev(struct ma_state *mas, unsigned long min); void *mas_next(struct ma_state *mas, unsigned long max); +void *mas_next_range(struct ma_state *mas, unsigned long max); int mas_empty_area(struct ma_state *mas, unsigned long min, unsigned long max, unsigned long size); @@ -528,7 +530,6 @@ static inline void mas_reset(struct ma_state *mas) #define mas_for_each(__mas, __entry, __max) \ while (((__entry) = mas_find((__mas), (__max))) != NULL) - /** * mas_set_range() - Set up Maple Tree operation state for a different index. * @mas: Maple Tree operation state. diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 205664f46e58..41c152718000 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4793,13 +4793,10 @@ again: */ static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit) { - void *entry = NULL; - if (mas->last >= limit) return NULL; - entry = mas_next_slot(mas, limit, false); - return entry; + return mas_next_slot(mas, limit, false); } /* @@ -5880,18 +5877,8 @@ int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries) } EXPORT_SYMBOL_GPL(mas_expected_entries); -/** - * mas_next() - Get the next entry. - * @mas: The maple state - * @max: The maximum index to check. - * - * Returns the next entry after @mas->index. - * Must hold rcu_read_lock or the write lock. - * Can return the zero entry. - * - * Return: The next entry or %NULL - */ -void *mas_next(struct ma_state *mas, unsigned long max) +static inline bool mas_next_setup(struct ma_state *mas, unsigned long max, + void **entry) { bool was_none = mas_is_none(mas); @@ -5899,24 +5886,71 @@ void *mas_next(struct ma_state *mas, unsigned long max) mas->node = MAS_START; if (mas_is_start(mas)) - mas_walk(mas); /* Retries on dead nodes handled by mas_walk */ + *entry = mas_walk(mas); /* Retries on dead nodes handled by mas_walk */ if (mas_is_ptr(mas)) { + *entry = NULL; if (was_none && mas->index == 0) { mas->index = mas->last = 0; - return mas_root(mas); + return true; } mas->index = 1; mas->last = ULONG_MAX; mas->node = MAS_NONE; - return NULL; + return true; } - /* Retries on dead nodes handled by mas_next_entry */ - return mas_next_entry(mas, max); + if (mas_is_none(mas)) + return true; + return false; +} + +/** + * mas_next() - Get the next entry. + * @mas: The maple state + * @max: The maximum index to check. + * + * Returns the next entry after @mas->index. + * Must hold rcu_read_lock or the write lock. + * Can return the zero entry. + * + * Return: The next entry or %NULL + */ +void *mas_next(struct ma_state *mas, unsigned long max) +{ + void *entry = NULL; + + if (mas_next_setup(mas, max, &entry)) + return entry; + + /* Retries on dead nodes handled by mas_next_slot */ + return mas_next_slot(mas, max, false); } EXPORT_SYMBOL_GPL(mas_next); +/** + * mas_next_range() - Advance the maple state to the next range + * @mas: The maple state + * @max: The maximum index to check. + * + * Sets @mas->index and @mas->last to the range. + * Must hold rcu_read_lock or the write lock. + * Can return the zero entry. + * + * Return: The next entry or %NULL + */ +void *mas_next_range(struct ma_state *mas, unsigned long max) +{ + void *entry = NULL; + + if (mas_next_setup(mas, max, &entry)) + return entry; + + /* Retries on dead nodes handled by mas_next_slot */ + return mas_next_slot(mas, max, true); +} +EXPORT_SYMBOL_GPL(mas_next_range); + /** * mt_next() - get the next value in the maple tree * @mt: The maple tree @@ -6026,49 +6060,41 @@ void mas_pause(struct ma_state *mas) EXPORT_SYMBOL_GPL(mas_pause); /** - * mas_find() - On the first call, find the entry at or after mas->index up to - * %max. Otherwise, find the entry after mas->index. + * mas_find_setup() - Internal function to set up mas_find*(). * @mas: The maple state - * @max: The maximum value to check. - * - * Must hold rcu_read_lock or the write lock. - * If an entry exists, last and index are updated accordingly. - * May set @mas->node to MAS_NONE. + * @max: The maximum index + * @entry: Pointer to the entry * - * Return: The entry or %NULL. + * Returns: True if entry is the answer, false otherwise. */ -void *mas_find(struct ma_state *mas, unsigned long max) +static inline bool mas_find_setup(struct ma_state *mas, unsigned long max, + void **entry) { + *entry = NULL; + if (unlikely(mas_is_none(mas))) { if (unlikely(mas->last >= max)) - return NULL; + return true; mas->index = mas->last; mas->node = MAS_START; - } - - if (unlikely(mas_is_paused(mas))) { + } else if (unlikely(mas_is_paused(mas))) { if (unlikely(mas->last >= max)) - return NULL; + return true; mas->node = MAS_START; mas->index = ++mas->last; - } - - - if (unlikely(mas_is_ptr(mas))) + } else if (unlikely(mas_is_ptr(mas))) goto ptr_out_of_range; if (unlikely(mas_is_start(mas))) { /* First run or continue */ - void *entry; - if (mas->index > max) - return NULL; + return true; - entry = mas_walk(mas); - if (entry) - return entry; + *entry = mas_walk(mas); + if (*entry) + return true; } @@ -6076,23 +6102,69 @@ void *mas_find(struct ma_state *mas, unsigned long max) if (unlikely(mas_is_ptr(mas))) goto ptr_out_of_range; - return NULL; + return true; } if (mas->index == max) - return NULL; + return true; - /* Retries on dead nodes handled by mas_next_slot */ - return mas_next_slot(mas, max, false); + return false; ptr_out_of_range: mas->node = MAS_NONE; mas->index = 1; mas->last = ULONG_MAX; - return NULL; + return true; +} + +/** + * mas_find() - On the first call, find the entry at or after mas->index up to + * %max. Otherwise, find the entry after mas->index. + * @mas: The maple state + * @max: The maximum value to check. + * + * Must hold rcu_read_lock or the write lock. + * If an entry exists, last and index are updated accordingly. + * May set @mas->node to MAS_NONE. + * + * Return: The entry or %NULL. + */ +void *mas_find(struct ma_state *mas, unsigned long max) +{ + void *entry = NULL; + + if (mas_find_setup(mas, max, &entry)) + return entry; + + /* Retries on dead nodes handled by mas_next_slot */ + return mas_next_slot(mas, max, false); } EXPORT_SYMBOL_GPL(mas_find); +/** + * mas_find_range() - On the first call, find the entry at or after + * mas->index up to %max. Otherwise, advance to the next slot mas->index. + * @mas: The maple state + * @max: The maximum value to check. + * + * Must hold rcu_read_lock or the write lock. + * If an entry exists, last and index are updated accordingly. + * May set @mas->node to MAS_NONE. + * + * Return: The entry or %NULL. + */ +void *mas_find_range(struct ma_state *mas, unsigned long max) +{ + void *entry; + + if (mas_find_setup(mas, max, &entry)) + return entry; + + /* Retries on dead nodes handled by mas_next_slot */ + return mas_next_slot(mas, max, true); +} +EXPORT_SYMBOL_GPL(mas_find_range); + /** * mas_find_rev: On the first call, find the first non-null entry at or below * mas->index down to %min. Otherwise find the first non-null entry below -- cgit v1.2.3 From 6b9e93e0102048e64681c2fa265ae81c221f6c6d Mon Sep 17 00:00:00 2001 From: "Liam R. Howlett" Date: Thu, 18 May 2023 10:55:40 -0400 Subject: maple_tree: add mas_prev_range() and mas_find_range_rev interface Some users of the maple tree may want to move to the previous range regardless of the value stored there. Add this interface as well as the 'find' variant to support walking to the first value, then iterating over the previous ranges. Link: https://lkml.kernel.org/r/20230518145544.1722059-32-Liam.Howlett@oracle.com Signed-off-by: Liam R. Howlett Cc: Vernon Yang Cc: David Binderman Cc: Peng Zhang Cc: Sergey Senozhatsky Cc: Wei Yang Signed-off-by: Andrew Morton --- include/linux/maple_tree.h | 2 + lib/maple_tree.c | 161 ++++++++++++++++++++++++++++++++++----------- 2 files changed, 124 insertions(+), 39 deletions(-) (limited to 'include/linux/maple_tree.h') diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 9d040043858a..541675229568 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -457,6 +457,7 @@ void mas_store_prealloc(struct ma_state *mas, void *entry); void *mas_find(struct ma_state *mas, unsigned long max); void *mas_find_range(struct ma_state *mas, unsigned long max); void *mas_find_rev(struct ma_state *mas, unsigned long min); +void *mas_find_range_rev(struct ma_state *mas, unsigned long max); int mas_preallocate(struct ma_state *mas, gfp_t gfp); bool mas_is_err(struct ma_state *mas); @@ -467,6 +468,7 @@ void mas_destroy(struct ma_state *mas); int mas_expected_entries(struct ma_state *mas, unsigned long nr_entries); void *mas_prev(struct ma_state *mas, unsigned long min); +void *mas_prev_range(struct ma_state *mas, unsigned long max); void *mas_next(struct ma_state *mas, unsigned long max); void *mas_next_range(struct ma_state *mas, unsigned long max); diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 9c7e765c809d..59c15f8b4793 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -5919,18 +5919,8 @@ void *mt_next(struct maple_tree *mt, unsigned long index, unsigned long max) } EXPORT_SYMBOL_GPL(mt_next); -/** - * mas_prev() - Get the previous entry - * @mas: The maple state - * @min: The minimum value to check. - * - * Must hold rcu_read_lock or the write lock. - * Will reset mas to MAS_START if the node is MAS_NONE. Will stop on not - * searchable nodes. - * - * Return: the previous value or %NULL. - */ -void *mas_prev(struct ma_state *mas, unsigned long min) +static inline bool mas_prev_setup(struct ma_state *mas, unsigned long min, + void **entry) { if (mas->index <= min) goto none; @@ -5948,7 +5938,8 @@ void *mas_prev(struct ma_state *mas, unsigned long min) if (!mas->index) goto none; mas->index = mas->last = 0; - return mas_root(mas); + *entry = mas_root(mas); + return true; } if (mas_is_none(mas)) { @@ -5956,18 +5947,64 @@ void *mas_prev(struct ma_state *mas, unsigned long min) /* Walked to out-of-range pointer? */ mas->index = mas->last = 0; mas->node = MAS_ROOT; - return mas_root(mas); + *entry = mas_root(mas); + return true; } - return NULL; + return true; } - return mas_prev_slot(mas, min, false); + + return false; none: mas->node = MAS_NONE; - return NULL; + return true; +} + +/** + * mas_prev() - Get the previous entry + * @mas: The maple state + * @min: The minimum value to check. + * + * Must hold rcu_read_lock or the write lock. + * Will reset mas to MAS_START if the node is MAS_NONE. Will stop on not + * searchable nodes. + * + * Return: the previous value or %NULL. + */ +void *mas_prev(struct ma_state *mas, unsigned long min) +{ + void *entry = NULL; + + if (mas_prev_setup(mas, min, &entry)) + return entry; + + return mas_prev_slot(mas, min, false); } EXPORT_SYMBOL_GPL(mas_prev); +/** + * mas_prev_range() - Advance to the previous range + * @mas: The maple state + * @min: The minimum value to check. + * + * Sets @mas->index and @mas->last to the range. + * Must hold rcu_read_lock or the write lock. + * Will reset mas to MAS_START if the node is MAS_NONE. Will stop on not + * searchable nodes. + * + * Return: the previous value or %NULL. + */ +void *mas_prev_range(struct ma_state *mas, unsigned long min) +{ + void *entry = NULL; + + if (mas_prev_setup(mas, min, &entry)) + return entry; + + return mas_prev_slot(mas, min, true); +} +EXPORT_SYMBOL_GPL(mas_prev_range); + /** * mt_prev() - get the previous value in the maple tree * @mt: The maple tree @@ -6114,20 +6151,18 @@ void *mas_find_range(struct ma_state *mas, unsigned long max) EXPORT_SYMBOL_GPL(mas_find_range); /** - * mas_find_rev: On the first call, find the first non-null entry at or below - * mas->index down to %min. Otherwise find the first non-null entry below - * mas->index down to %min. + * mas_find_rev_setup() - Internal function to set up mas_find_*_rev() * @mas: The maple state - * @min: The minimum value to check. - * - * Must hold rcu_read_lock or the write lock. - * If an entry exists, last and index are updated accordingly. - * May set @mas->node to MAS_NONE. + * @min: The minimum index + * @entry: Pointer to the entry * - * Return: The entry or %NULL. + * Returns: True if entry is the answer, false otherwise. */ -void *mas_find_rev(struct ma_state *mas, unsigned long min) +static inline bool mas_find_rev_setup(struct ma_state *mas, unsigned long min, + void **entry) { + *entry = NULL; + if (unlikely(mas_is_none(mas))) { if (mas->index <= min) goto none; @@ -6139,7 +6174,7 @@ void *mas_find_rev(struct ma_state *mas, unsigned long min) if (unlikely(mas_is_paused(mas))) { if (unlikely(mas->index <= min)) { mas->node = MAS_NONE; - return NULL; + return true; } mas->node = MAS_START; mas->last = --mas->index; @@ -6147,14 +6182,12 @@ void *mas_find_rev(struct ma_state *mas, unsigned long min) if (unlikely(mas_is_start(mas))) { /* First run or continue */ - void *entry; - if (mas->index < min) - return NULL; + return true; - entry = mas_walk(mas); - if (entry) - return entry; + *entry = mas_walk(mas); + if (*entry) + return true; } if (unlikely(!mas_searchable(mas))) { @@ -6168,22 +6201,72 @@ void *mas_find_rev(struct ma_state *mas, unsigned long min) */ mas->last = mas->index = 0; mas->node = MAS_ROOT; - return mas_root(mas); + *entry = mas_root(mas); + return true; } } if (mas->index < min) - return NULL; + return true; - /* Retries on dead nodes handled by mas_prev_slot */ - return mas_prev_slot(mas, min, false); + return false; none: mas->node = MAS_NONE; - return NULL; + return true; +} + +/** + * mas_find_rev: On the first call, find the first non-null entry at or below + * mas->index down to %min. Otherwise find the first non-null entry below + * mas->index down to %min. + * @mas: The maple state + * @min: The minimum value to check. + * + * Must hold rcu_read_lock or the write lock. + * If an entry exists, last and index are updated accordingly. + * May set @mas->node to MAS_NONE. + * + * Return: The entry or %NULL. + */ +void *mas_find_rev(struct ma_state *mas, unsigned long min) +{ + void *entry; + + if (mas_find_rev_setup(mas, min, &entry)) + return entry; + + /* Retries on dead nodes handled by mas_prev_slot */ + return mas_prev_slot(mas, min, false); + } EXPORT_SYMBOL_GPL(mas_find_rev); +/** + * mas_find_range_rev: On the first call, find the first non-null entry at or + * below mas->index down to %min. Otherwise advance to the previous slot after + * mas->index down to %min. + * @mas: The maple state + * @min: The minimum value to check. + * + * Must hold rcu_read_lock or the write lock. + * If an entry exists, last and index are updated accordingly. + * May set @mas->node to MAS_NONE. + * + * Return: The entry or %NULL. + */ +void *mas_find_range_rev(struct ma_state *mas, unsigned long min) +{ + void *entry; + + if (mas_find_rev_setup(mas, min, &entry)) + return entry; + + /* Retries on dead nodes handled by mas_prev_slot */ + return mas_prev_slot(mas, min, true); +} +EXPORT_SYMBOL_GPL(mas_find_range_rev); + /** * mas_erase() - Find the range in which index resides and erase the entire * range. -- cgit v1.2.3 From 06b27ce36a1a3dc5ea6f8314d0c7d1baa9f8ece7 Mon Sep 17 00:00:00 2001 From: Peng Zhang Date: Wed, 24 May 2023 11:12:47 +0800 Subject: maple_tree: relocate the declaration of mas_empty_area_rev(). Relocate the declaration of mas_empty_area_rev() so that mas_empty_area() and mas_empty_area_rev() are together. Link: https://lkml.kernel.org/r/20230524031247.65949-11-zhangpeng.00@bytedance.com Signed-off-by: Peng Zhang Reviewed-by: Liam R. Howlett Signed-off-by: Andrew Morton --- include/linux/maple_tree.h | 12 ++++++------ 1 file changed, 6 insertions(+), 6 deletions(-) (limited to 'include/linux/maple_tree.h') diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index 541675229568..295548cca8b3 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -474,6 +474,12 @@ void *mas_next_range(struct ma_state *mas, unsigned long max); int mas_empty_area(struct ma_state *mas, unsigned long min, unsigned long max, unsigned long size); +/* + * This finds an empty area from the highest address to the lowest. + * AKA "Topdown" version, + */ +int mas_empty_area_rev(struct ma_state *mas, unsigned long min, + unsigned long max, unsigned long size); static inline void mas_init(struct ma_state *mas, struct maple_tree *tree, unsigned long addr) @@ -497,12 +503,6 @@ static inline bool mas_is_paused(const struct ma_state *mas) return mas->node == MAS_PAUSE; } -/* - * This finds an empty area from the highest address to the lowest. - * AKA "Topdown" version, - */ -int mas_empty_area_rev(struct ma_state *mas, unsigned long min, - unsigned long max, unsigned long size); /** * mas_reset() - Reset a Maple Tree operation state. * @mas: Maple Tree operation state. -- cgit v1.2.3