| Message ID | 20230505174204.2665599-32-Liam.Howlett@oracle.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | Maple tree mas_{next,prev}_range() and cleanup | expand |
On Fri, May 05, 2023 at 01:41:59PM -0400, Liam R. Howlett wrote: > 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. > > Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com> > --- > include/linux/maple_tree.h | 1 + > lib/maple_tree.c | 160 +++++++++++++++++++++++++++---------- > 2 files changed, 121 insertions(+), 40 deletions(-) > > diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h > index a4cd8f891a090..542b09118a09f 100644 > --- a/include/linux/maple_tree.h > +++ b/include/linux/maple_tree.h > @@ -467,6 +467,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 e050fd1f7cce8..f060c71965c0d 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -5924,18 +5924,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; > @@ -5953,7 +5943,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)) { > @@ -5961,18 +5952,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_slot); Hi Liam, I guess you want to export mas_prev_range symbol instead of mas_prev_slot. > + > /** > * mt_prev() - get the previous value in the maple tree > * @mt: The maple tree > @@ -6116,20 +6153,15 @@ 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: The maple state > - * @min: The minimum value to check. > + * mas_find_rev_setup() - Internal function to set up mas_find_*_rev() > * > - * 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. > + * 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; > @@ -6141,7 +6173,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; > @@ -6149,14 +6181,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))) { > @@ -6170,22 +6200,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. > > -- > 2.39.2 >
* Vernon Yang <vernon2gm@gmail.com> [230508 09:27]: > On Fri, May 05, 2023 at 01:41:59PM -0400, Liam R. Howlett wrote: > > 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. > > > > Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com> > > --- > > include/linux/maple_tree.h | 1 + > > lib/maple_tree.c | 160 +++++++++++++++++++++++++++---------- > > 2 files changed, 121 insertions(+), 40 deletions(-) > > > > diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h > > index a4cd8f891a090..542b09118a09f 100644 > > --- a/include/linux/maple_tree.h > > +++ b/include/linux/maple_tree.h > > @@ -467,6 +467,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 e050fd1f7cce8..f060c71965c0d 100644 > > --- a/lib/maple_tree.c > > +++ b/lib/maple_tree.c > > @@ -5924,18 +5924,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; > > @@ -5953,7 +5943,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)) { > > @@ -5961,18 +5952,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_slot); > > Hi Liam, > > I guess you want to export mas_prev_range symbol instead of mas_prev_slot. Yes.. and it mas_prev_slot should be static. Thanks for catching this. I noticed this only after the bot complained about non-static functions in this series. Regards, Liam
diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h index a4cd8f891a090..542b09118a09f 100644 --- a/include/linux/maple_tree.h +++ b/include/linux/maple_tree.h @@ -467,6 +467,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 e050fd1f7cce8..f060c71965c0d 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -5924,18 +5924,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; @@ -5953,7 +5943,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)) { @@ -5961,18 +5952,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_slot); + /** * mt_prev() - get the previous value in the maple tree * @mt: The maple tree @@ -6116,20 +6153,15 @@ 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: The maple state - * @min: The minimum value to check. + * mas_find_rev_setup() - Internal function to set up mas_find_*_rev() * - * 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. + * 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; @@ -6141,7 +6173,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; @@ -6149,14 +6181,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))) { @@ -6170,22 +6200,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.
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. Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com> --- include/linux/maple_tree.h | 1 + lib/maple_tree.c | 160 +++++++++++++++++++++++++++---------- 2 files changed, 121 insertions(+), 40 deletions(-)