| Message ID | 20230425140955.3834476-28-Liam.Howlett@oracle.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | Maple tree mas_{next,prev}_range() and cleanup | expand |
Hi Liam,
kernel test robot noticed the following build warnings:
[auto build test WARNING on akpm-mm/mm-everything]
[also build test WARNING on linus/master v6.3 next-20230425]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]
url: https://github.com/intel-lab-lkp/linux/commits/Liam-R-Howlett/maple_tree-Fix-static-analyser-cppcheck-issue/20230425-233958
base: https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-everything
patch link: https://lore.kernel.org/r/20230425140955.3834476-28-Liam.Howlett%40oracle.com
patch subject: [PATCH 27/34] maple_tree: Introduce mas_next_slot() interface
config: x86_64-randconfig-a003-20230424 (https://download.01.org/0day-ci/archive/20230426/202304260907.iHgOR74J-lkp@intel.com/config)
compiler: clang version 14.0.6 (https://github.com/llvm/llvm-project f28c006a5895fc0e329fe15fead81e37457cb1d1)
reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
chmod +x ~/bin/make.cross
# https://github.com/intel-lab-lkp/linux/commit/0e736b8a8054e7f0b216320d2458a00b54fcd2b0
git remote add linux-review https://github.com/intel-lab-lkp/linux
git fetch --no-tags linux-review Liam-R-Howlett/maple_tree-Fix-static-analyser-cppcheck-issue/20230425-233958
git checkout 0e736b8a8054e7f0b216320d2458a00b54fcd2b0
# save the config file
mkdir build_dir && cp config build_dir/.config
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 O=build_dir ARCH=x86_64 olddefconfig
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 O=build_dir ARCH=x86_64 SHELL=/bin/bash
If you fix the issue, kindly add following tag where applicable
| Reported-by: kernel test robot <lkp@intel.com>
| Link: https://lore.kernel.org/oe-kbuild-all/202304260907.iHgOR74J-lkp@intel.com/
All warnings (new ones prefixed by >>):
>> lib/maple_tree.c:4710:7: warning: no previous prototype for function 'mas_next_slot' [-Wmissing-prototypes]
void *mas_next_slot(struct ma_state *mas, unsigned long max)
^
lib/maple_tree.c:4710:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
void *mas_next_slot(struct ma_state *mas, unsigned long max)
^
static
lib/maple_tree.c:4780:10: error: implicit declaration of function 'mas_next_slot_limit' is invalid in C99 [-Werror,-Wimplicit-function-declaration]
entry = mas_next_slot_limit(mas, limit);
^
lib/maple_tree.c:4780:10: note: did you mean 'mas_next_slot'?
lib/maple_tree.c:4710:7: note: 'mas_next_slot' declared here
void *mas_next_slot(struct ma_state *mas, unsigned long max)
^
lib/maple_tree.c:4780:8: warning: incompatible integer to pointer conversion assigning to 'void *' from 'int' [-Wint-conversion]
entry = mas_next_slot_limit(mas, limit);
^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
lib/maple_tree.c:4787:9: warning: incompatible integer to pointer conversion returning 'int' from a function with result type 'void *' [-Wint-conversion]
return mas_next_slot_limit(mas, limit);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3 warnings and 1 error generated.
vim +/mas_next_slot +4710 lib/maple_tree.c
4701
4702 /*
4703 * mas_next_slot() - Get the entry in the next slot
4704 *
4705 * @mas: The maple state
4706 * @max: The maximum starting range
4707 *
4708 * Return: The entry in the next slot which is possibly NULL
4709 */
> 4710 void *mas_next_slot(struct ma_state *mas, unsigned long max)
4711 {
4712 void __rcu **slots;
4713 unsigned long *pivots;
4714 unsigned long pivot;
4715 enum maple_type type;
4716 struct maple_node *node;
4717 unsigned char data_end;
4718 unsigned long save_point = mas->last;
4719 void *entry;
4720
4721 retry:
4722 node = mas_mn(mas);
4723 type = mte_node_type(mas->node);
4724 pivots = ma_pivots(node, type);
4725 data_end = ma_data_end(node, type, pivots, mas->max);
4726 pivot = mas_logical_pivot(mas, pivots, mas->offset, type);
4727 if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
4728 goto retry;
4729
4730 if (pivot >= max)
4731 return NULL;
4732
4733 if (likely(data_end > mas->offset)) {
4734 mas->offset++;
4735 mas->index = mas->last + 1;
4736 } else {
4737 if (mas_next_node(mas, node, max)) {
4738 mas_rewalk(mas, save_point);
4739 goto retry;
4740 }
4741
4742 if (mas_is_none(mas))
4743 return NULL;
4744
4745 mas->offset = 0;
4746 mas->index = mas->min;
4747 node = mas_mn(mas);
4748 type = mte_node_type(mas->node);
4749 pivots = ma_pivots(node, type);
4750 }
4751
4752 slots = ma_slots(node, type);
4753 mas->last = mas_logical_pivot(mas, pivots, mas->offset, type);
4754 entry = mas_slot(mas, slots, mas->offset);
4755 if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
4756 goto retry;
4757
4758 return entry;
4759 }
4760
Hi Liam,
kernel test robot noticed the following build errors:
[auto build test ERROR on akpm-mm/mm-everything]
[also build test ERROR on linus/master v6.3 next-20230425]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]
url: https://github.com/intel-lab-lkp/linux/commits/Liam-R-Howlett/maple_tree-Fix-static-analyser-cppcheck-issue/20230425-233958
base: https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-everything
patch link: https://lore.kernel.org/r/20230425140955.3834476-28-Liam.Howlett%40oracle.com
patch subject: [PATCH 27/34] maple_tree: Introduce mas_next_slot() interface
config: x86_64-kexec (https://download.01.org/0day-ci/archive/20230426/202304262143.kjXZTgwU-lkp@intel.com/config)
compiler: gcc-11 (Debian 11.3.0-8) 11.3.0
reproduce (this is a W=1 build):
# https://github.com/intel-lab-lkp/linux/commit/0e736b8a8054e7f0b216320d2458a00b54fcd2b0
git remote add linux-review https://github.com/intel-lab-lkp/linux
git fetch --no-tags linux-review Liam-R-Howlett/maple_tree-Fix-static-analyser-cppcheck-issue/20230425-233958
git checkout 0e736b8a8054e7f0b216320d2458a00b54fcd2b0
# save the config file
mkdir build_dir && cp config build_dir/.config
make W=1 O=build_dir ARCH=x86_64 olddefconfig
make W=1 O=build_dir ARCH=x86_64 SHELL=/bin/bash
If you fix the issue, kindly add following tag where applicable
| Reported-by: kernel test robot <lkp@intel.com>
| Link: https://lore.kernel.org/oe-kbuild-all/202304262143.kjXZTgwU-lkp@intel.com/
All error/warnings (new ones prefixed by >>):
lib/maple_tree.c:4710:7: warning: no previous prototype for 'mas_next_slot' [-Wmissing-prototypes]
4710 | void *mas_next_slot(struct ma_state *mas, unsigned long max)
| ^~~~~~~~~~~~~
lib/maple_tree.c: In function 'mas_next_entry':
>> lib/maple_tree.c:4780:17: error: implicit declaration of function 'mas_next_slot_limit'; did you mean 'mas_next_slot'? [-Werror=implicit-function-declaration]
4780 | entry = mas_next_slot_limit(mas, limit);
| ^~~~~~~~~~~~~~~~~~~
| mas_next_slot
>> lib/maple_tree.c:4780:15: warning: assignment to 'void *' from 'int' makes pointer from integer without a cast [-Wint-conversion]
4780 | entry = mas_next_slot_limit(mas, limit);
| ^
>> lib/maple_tree.c:4787:16: warning: returning 'int' from a function with return type 'void *' makes pointer from integer without a cast [-Wint-conversion]
4787 | return mas_next_slot_limit(mas, limit);
| ^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
cc1: some warnings being treated as errors
vim +4780 lib/maple_tree.c
4760
4761 /*
4762 * mas_next_entry() - Internal function to get the next entry.
4763 * @mas: The maple state
4764 * @limit: The maximum range start.
4765 *
4766 * Set the @mas->node to the next entry and the range_start to
4767 * the beginning value for the entry. Does not check beyond @limit.
4768 * Sets @mas->index and @mas->last to the limit if it is hit.
4769 * Restarts on dead nodes.
4770 *
4771 * Return: the next entry or %NULL.
4772 */
4773 static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit)
4774 {
4775 void *entry = NULL;
4776
4777 if (mas->last >= limit)
4778 return NULL;
4779
> 4780 entry = mas_next_slot_limit(mas, limit);
4781 if (entry)
4782 return entry;
4783
4784 if (mas_is_none(mas))
4785 return NULL;
4786
> 4787 return mas_next_slot_limit(mas, limit);
4788 }
4789
在 2023/4/25 22:09, Liam R. Howlett 写道: > Sometimes, during a tree walk, the user needs the next slot regardless > of if it is empty or not. Add an interface to get the next slot. > > Since there are no consecutive NULLs allowed in the tree, the mas_next() > function can only advance two slots at most. So use the new > mas_next_slot() interface to align both implementations. > > Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com> > --- > lib/maple_tree.c | 178 +++++++++++++++++++---------------------------- > 1 file changed, 71 insertions(+), 107 deletions(-) > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > index 31cbfd7b44728..fe6c9da6f2bd5 100644 > --- a/lib/maple_tree.c > +++ b/lib/maple_tree.c > @@ -4619,15 +4619,16 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, > if (mas->max >= max) > goto no_entry; > > + min = mas->max + 1; > + if (min > max) > + goto no_entry; Unnecessary check due to mas->max < max. > + > level = 0; > do { > if (ma_is_root(node)) > goto no_entry; > > - min = mas->max + 1; > - if (min > max) > - goto no_entry; > - > + /* Walk up. */ > if (unlikely(mas_ascend(mas))) > return 1; > > @@ -4645,13 +4646,12 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, > slots = ma_slots(node, mt); > pivot = mas_safe_pivot(mas, pivots, ++offset, mt); > while (unlikely(level > 1)) { > - /* Descend, if necessary */ > + level--; > enode = mas_slot(mas, slots, offset); > if (unlikely(ma_dead_node(node))) > return 1; > > mas->node = enode; > - level--; > node = mas_mn(mas); > mt = mte_node_type(mas->node); > slots = ma_slots(node, mt); > @@ -4680,85 +4680,84 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, > return 0; > } > > +static inline void mas_rewalk(struct ma_state *mas, unsigned long index) > +{ > +retry: > + mas_set(mas, index); > + mas_state_walk(mas); > + if (mas_is_start(mas)) > + goto retry; > +} > + > +static inline bool mas_rewalk_if_dead(struct ma_state *mas, > + struct maple_node *node, const unsigned long index) > +{ > + if (unlikely(ma_dead_node(node))) { > + mas_rewalk(mas, index); > + return true; > + } > + return false; > +} > + > /* > - * mas_next_nentry() - Get the next node entry > - * @mas: The maple state > - * @max: The maximum value to check > - * @*range_start: Pointer to store the start of the range. > + * mas_next_slot() - Get the entry in the next slot > * > - * Sets @mas->offset to the offset of the next node entry, @mas->last to the > - * pivot of the entry. > + * @mas: The maple state > + * @max: The maximum starting range > * > - * Return: The next entry, %NULL otherwise > + * Return: The entry in the next slot which is possibly NULL > */ > -static inline void *mas_next_nentry(struct ma_state *mas, > - struct maple_node *node, unsigned long max, enum maple_type type) > +void *mas_next_slot(struct ma_state *mas, unsigned long max) > { > - unsigned char count; > - unsigned long pivot; > - unsigned long *pivots; > void __rcu **slots; > + unsigned long *pivots; > + unsigned long pivot; > + enum maple_type type; > + struct maple_node *node; > + unsigned char data_end; > + unsigned long save_point = mas->last; > void *entry; > > - if (mas->last == mas->max) { > - mas->index = mas->max; > - return NULL; > - } > - > - slots = ma_slots(node, type); > +retry: > + node = mas_mn(mas); > + type = mte_node_type(mas->node); > pivots = ma_pivots(node, type); > - count = ma_data_end(node, type, pivots, mas->max); > - if (unlikely(ma_dead_node(node))) > - return NULL; > - > - mas->index = mas_safe_min(mas, pivots, mas->offset); > - if (unlikely(ma_dead_node(node))) > - return NULL; > - > - if (mas->index > max) > - return NULL; > + data_end = ma_data_end(node, type, pivots, mas->max); > + pivot = mas_logical_pivot(mas, pivots, mas->offset, type); > + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) > + goto retry; > > - if (mas->offset > count) > + if (pivot >= max) > return NULL; > > - while (mas->offset < count) { > - pivot = pivots[mas->offset]; > - entry = mas_slot(mas, slots, mas->offset); > - if (ma_dead_node(node)) > - return NULL; > - > - mas->last = pivot; > - if (entry) > - return entry; > - > - if (pivot >= max) > - return NULL; > + if (likely(data_end > mas->offset)) { > + mas->offset++; > + mas->index = mas->last + 1; > + } else { > + if (mas_next_node(mas, node, max)) { > + mas_rewalk(mas, save_point); > + goto retry; > + } > > - if (pivot >= mas->max) > + if (mas_is_none(mas)) > return NULL; > > - mas->index = pivot + 1; > - mas->offset++; > + mas->offset = 0; > + mas->index = mas->min; > + node = mas_mn(mas); > + type = mte_node_type(mas->node); > + pivots = ma_pivots(node, type); > } > > - pivot = mas_logical_pivot(mas, pivots, mas->offset, type); > + slots = ma_slots(node, type); > + mas->last = mas_logical_pivot(mas, pivots, mas->offset, type); > entry = mas_slot(mas, slots, mas->offset); > - if (ma_dead_node(node)) > - return NULL; > + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) > + goto retry; > > - mas->last = pivot; > return entry; > } > > -static inline void mas_rewalk(struct ma_state *mas, unsigned long index) > -{ > -retry: > - mas_set(mas, index); > - mas_state_walk(mas); > - if (mas_is_start(mas)) > - goto retry; > -} > - > /* > * mas_next_entry() - Internal function to get the next entry. > * @mas: The maple state > @@ -4774,47 +4773,18 @@ static inline void mas_rewalk(struct ma_state *mas, unsigned long index) > static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit) > { > void *entry = NULL; > - struct maple_node *node; > - unsigned long last; > - enum maple_type mt; > > if (mas->last >= limit) > return NULL; > > - last = mas->last; > -retry: > - node = mas_mn(mas); > - mt = mte_node_type(mas->node); > - mas->offset++; > - if (unlikely(mas->offset >= mt_slots[mt])) { > - mas->offset = mt_slots[mt] - 1; > - goto next_node; > - } > - > - while (!mas_is_none(mas)) { > - entry = mas_next_nentry(mas, node, limit, mt); > - if (unlikely(ma_dead_node(node))) { > - mas_rewalk(mas, last); > - goto retry; > - } > - > - if (likely(entry)) > - return entry; > - > - if (unlikely((mas->last >= limit))) > - return NULL; > + entry = mas_next_slot_limit(mas, limit); > + if (entry) > + return entry; > > -next_node: > - if (unlikely(mas_next_node(mas, node, limit))) { > - mas_rewalk(mas, last); > - goto retry; > - } > - mas->offset = 0; > - node = mas_mn(mas); > - mt = mte_node_type(mas->node); > - } > + if (mas_is_none(mas)) > + return NULL; > > - return NULL; > + return mas_next_slot_limit(mas, limit); > } > > /* > @@ -4845,10 +4815,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, > slots = ma_slots(mn, mt); > pivots = ma_pivots(mn, mt); > count = ma_data_end(mn, mt, pivots, mas->max); > - if (unlikely(ma_dead_node(mn))) { > - mas_rewalk(mas, index); > + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) > goto retry; > - } > > offset = mas->offset - 1; > if (offset >= mt_slots[mt]) > @@ -4861,10 +4829,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, > pivot = pivots[offset]; > } > > - if (unlikely(ma_dead_node(mn))) { > - mas_rewalk(mas, index); > + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) > goto retry; > - } > > while (offset && !mas_slot(mas, slots, offset)) { > pivot = pivots[--offset]; > @@ -4881,10 +4847,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, > > min = mas_safe_min(mas, pivots, offset); > entry = mas_slot(mas, slots, offset); > - if (unlikely(ma_dead_node(mn))) { > - mas_rewalk(mas, index); > + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) > goto retry; > - } > > mas->offset = offset; > mas->last = pivot;
Hi Liam,
kernel test robot noticed the following build errors:
[auto build test ERROR on akpm-mm/mm-everything]
[also build test ERROR on linus/master v6.3 next-20230427]
[If your patch is applied to the wrong git tree, kindly drop us a note.
And when submitting patch, we suggest to use '--base' as documented in
https://git-scm.com/docs/git-format-patch#_base_tree_information]
url: https://github.com/intel-lab-lkp/linux/commits/Liam-R-Howlett/maple_tree-Fix-static-analyser-cppcheck-issue/20230425-233958
base: https://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm.git mm-everything
patch link: https://lore.kernel.org/r/20230425140955.3834476-28-Liam.Howlett%40oracle.com
patch subject: [PATCH 27/34] maple_tree: Introduce mas_next_slot() interface
config: i386-randconfig-a005-20230424 (https://download.01.org/0day-ci/archive/20230428/202304281651.cfC6scj6-lkp@intel.com/config)
compiler: clang version 14.0.6 (https://github.com/llvm/llvm-project f28c006a5895fc0e329fe15fead81e37457cb1d1)
reproduce (this is a W=1 build):
wget https://raw.githubusercontent.com/intel/lkp-tests/master/sbin/make.cross -O ~/bin/make.cross
chmod +x ~/bin/make.cross
# https://github.com/intel-lab-lkp/linux/commit/0e736b8a8054e7f0b216320d2458a00b54fcd2b0
git remote add linux-review https://github.com/intel-lab-lkp/linux
git fetch --no-tags linux-review Liam-R-Howlett/maple_tree-Fix-static-analyser-cppcheck-issue/20230425-233958
git checkout 0e736b8a8054e7f0b216320d2458a00b54fcd2b0
# save the config file
mkdir build_dir && cp config build_dir/.config
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 O=build_dir ARCH=i386 olddefconfig
COMPILER_INSTALL_PATH=$HOME/0day COMPILER=clang make.cross W=1 O=build_dir ARCH=i386 SHELL=/bin/bash
If you fix the issue, kindly add following tag where applicable
| Reported-by: kernel test robot <lkp@intel.com>
| Link: https://lore.kernel.org/oe-kbuild-all/202304281651.cfC6scj6-lkp@intel.com/
All error/warnings (new ones prefixed by >>):
lib/maple_tree.c:4710:7: warning: no previous prototype for function 'mas_next_slot' [-Wmissing-prototypes]
void *mas_next_slot(struct ma_state *mas, unsigned long max)
^
lib/maple_tree.c:4710:1: note: declare 'static' if the function is not intended to be used outside of this translation unit
void *mas_next_slot(struct ma_state *mas, unsigned long max)
^
static
>> lib/maple_tree.c:4780:10: error: implicit declaration of function 'mas_next_slot_limit' is invalid in C99 [-Werror,-Wimplicit-function-declaration]
entry = mas_next_slot_limit(mas, limit);
^
lib/maple_tree.c:4780:10: note: did you mean 'mas_next_slot'?
lib/maple_tree.c:4710:7: note: 'mas_next_slot' declared here
void *mas_next_slot(struct ma_state *mas, unsigned long max)
^
>> lib/maple_tree.c:4780:8: warning: incompatible integer to pointer conversion assigning to 'void *' from 'int' [-Wint-conversion]
entry = mas_next_slot_limit(mas, limit);
^ ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
>> lib/maple_tree.c:4787:9: warning: incompatible integer to pointer conversion returning 'int' from a function with result type 'void *' [-Wint-conversion]
return mas_next_slot_limit(mas, limit);
^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
3 warnings and 1 error generated.
vim +/mas_next_slot_limit +4780 lib/maple_tree.c
4701
4702 /*
4703 * mas_next_slot() - Get the entry in the next slot
4704 *
4705 * @mas: The maple state
4706 * @max: The maximum starting range
4707 *
4708 * Return: The entry in the next slot which is possibly NULL
4709 */
> 4710 void *mas_next_slot(struct ma_state *mas, unsigned long max)
4711 {
4712 void __rcu **slots;
4713 unsigned long *pivots;
4714 unsigned long pivot;
4715 enum maple_type type;
4716 struct maple_node *node;
4717 unsigned char data_end;
4718 unsigned long save_point = mas->last;
4719 void *entry;
4720
4721 retry:
4722 node = mas_mn(mas);
4723 type = mte_node_type(mas->node);
4724 pivots = ma_pivots(node, type);
4725 data_end = ma_data_end(node, type, pivots, mas->max);
4726 pivot = mas_logical_pivot(mas, pivots, mas->offset, type);
4727 if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
4728 goto retry;
4729
4730 if (pivot >= max)
4731 return NULL;
4732
4733 if (likely(data_end > mas->offset)) {
4734 mas->offset++;
4735 mas->index = mas->last + 1;
4736 } else {
4737 if (mas_next_node(mas, node, max)) {
4738 mas_rewalk(mas, save_point);
4739 goto retry;
4740 }
4741
4742 if (mas_is_none(mas))
4743 return NULL;
4744
4745 mas->offset = 0;
4746 mas->index = mas->min;
4747 node = mas_mn(mas);
4748 type = mte_node_type(mas->node);
4749 pivots = ma_pivots(node, type);
4750 }
4751
4752 slots = ma_slots(node, type);
4753 mas->last = mas_logical_pivot(mas, pivots, mas->offset, type);
4754 entry = mas_slot(mas, slots, mas->offset);
4755 if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
4756 goto retry;
4757
4758 return entry;
4759 }
4760
4761 /*
4762 * mas_next_entry() - Internal function to get the next entry.
4763 * @mas: The maple state
4764 * @limit: The maximum range start.
4765 *
4766 * Set the @mas->node to the next entry and the range_start to
4767 * the beginning value for the entry. Does not check beyond @limit.
4768 * Sets @mas->index and @mas->last to the limit if it is hit.
4769 * Restarts on dead nodes.
4770 *
4771 * Return: the next entry or %NULL.
4772 */
4773 static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit)
4774 {
4775 void *entry = NULL;
4776
4777 if (mas->last >= limit)
4778 return NULL;
4779
> 4780 entry = mas_next_slot_limit(mas, limit);
4781 if (entry)
4782 return entry;
4783
4784 if (mas_is_none(mas))
4785 return NULL;
4786
> 4787 return mas_next_slot_limit(mas, limit);
4788 }
4789
* Peng Zhang <perlyzhang@gmail.com> [230428 02:48]: > > > 在 2023/4/25 22:09, Liam R. Howlett 写道: > > Sometimes, during a tree walk, the user needs the next slot regardless > > of if it is empty or not. Add an interface to get the next slot. > > > > Since there are no consecutive NULLs allowed in the tree, the mas_next() > > function can only advance two slots at most. So use the new > > mas_next_slot() interface to align both implementations. > > > > Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com> > > --- > > lib/maple_tree.c | 178 +++++++++++++++++++---------------------------- > > 1 file changed, 71 insertions(+), 107 deletions(-) > > > > diff --git a/lib/maple_tree.c b/lib/maple_tree.c > > index 31cbfd7b44728..fe6c9da6f2bd5 100644 > > --- a/lib/maple_tree.c > > +++ b/lib/maple_tree.c > > @@ -4619,15 +4619,16 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, > > if (mas->max >= max) > > goto no_entry; > > + min = mas->max + 1; > > + if (min > max) > > + goto no_entry; > Unnecessary check due to mas->max < max. Thanks, I will address this in v2. > > + > > level = 0; > > do { > > if (ma_is_root(node)) > > goto no_entry; > > - min = mas->max + 1; > > - if (min > max) > > - goto no_entry; > > - > > + /* Walk up. */ > > if (unlikely(mas_ascend(mas))) > > return 1; > > @@ -4645,13 +4646,12 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, > > slots = ma_slots(node, mt); > > pivot = mas_safe_pivot(mas, pivots, ++offset, mt); > > while (unlikely(level > 1)) { > > - /* Descend, if necessary */ > > + level--; > > enode = mas_slot(mas, slots, offset); > > if (unlikely(ma_dead_node(node))) > > return 1; > > mas->node = enode; > > - level--; > > node = mas_mn(mas); > > mt = mte_node_type(mas->node); > > slots = ma_slots(node, mt); > > @@ -4680,85 +4680,84 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, > > return 0; > > } > > +static inline void mas_rewalk(struct ma_state *mas, unsigned long index) > > +{ > > +retry: > > + mas_set(mas, index); > > + mas_state_walk(mas); > > + if (mas_is_start(mas)) > > + goto retry; > > +} > > + > > +static inline bool mas_rewalk_if_dead(struct ma_state *mas, > > + struct maple_node *node, const unsigned long index) > > +{ > > + if (unlikely(ma_dead_node(node))) { > > + mas_rewalk(mas, index); > > + return true; > > + } > > + return false; > > +} > > + > > /* > > - * mas_next_nentry() - Get the next node entry > > - * @mas: The maple state > > - * @max: The maximum value to check > > - * @*range_start: Pointer to store the start of the range. > > + * mas_next_slot() - Get the entry in the next slot > > * > > - * Sets @mas->offset to the offset of the next node entry, @mas->last to the > > - * pivot of the entry. > > + * @mas: The maple state > > + * @max: The maximum starting range > > * > > - * Return: The next entry, %NULL otherwise > > + * Return: The entry in the next slot which is possibly NULL > > */ > > -static inline void *mas_next_nentry(struct ma_state *mas, > > - struct maple_node *node, unsigned long max, enum maple_type type) > > +void *mas_next_slot(struct ma_state *mas, unsigned long max) > > { > > - unsigned char count; > > - unsigned long pivot; > > - unsigned long *pivots; > > void __rcu **slots; > > + unsigned long *pivots; > > + unsigned long pivot; > > + enum maple_type type; > > + struct maple_node *node; > > + unsigned char data_end; > > + unsigned long save_point = mas->last; > > void *entry; > > - if (mas->last == mas->max) { > > - mas->index = mas->max; > > - return NULL; > > - } > > - > > - slots = ma_slots(node, type); > > +retry: > > + node = mas_mn(mas); > > + type = mte_node_type(mas->node); > > pivots = ma_pivots(node, type); > > - count = ma_data_end(node, type, pivots, mas->max); > > - if (unlikely(ma_dead_node(node))) > > - return NULL; > > - > > - mas->index = mas_safe_min(mas, pivots, mas->offset); > > - if (unlikely(ma_dead_node(node))) > > - return NULL; > > - > > - if (mas->index > max) > > - return NULL; > > + data_end = ma_data_end(node, type, pivots, mas->max); > > + pivot = mas_logical_pivot(mas, pivots, mas->offset, type); > > + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) > > + goto retry; > > - if (mas->offset > count) > > + if (pivot >= max) > > return NULL; > > - while (mas->offset < count) { > > - pivot = pivots[mas->offset]; > > - entry = mas_slot(mas, slots, mas->offset); > > - if (ma_dead_node(node)) > > - return NULL; > > - > > - mas->last = pivot; > > - if (entry) > > - return entry; > > - > > - if (pivot >= max) > > - return NULL; > > + if (likely(data_end > mas->offset)) { > > + mas->offset++; > > + mas->index = mas->last + 1; > > + } else { > > + if (mas_next_node(mas, node, max)) { > > + mas_rewalk(mas, save_point); > > + goto retry; > > + } > > - if (pivot >= mas->max) > > + if (mas_is_none(mas)) > > return NULL; > > - mas->index = pivot + 1; > > - mas->offset++; > > + mas->offset = 0; > > + mas->index = mas->min; > > + node = mas_mn(mas); > > + type = mte_node_type(mas->node); > > + pivots = ma_pivots(node, type); > > } > > - pivot = mas_logical_pivot(mas, pivots, mas->offset, type); > > + slots = ma_slots(node, type); > > + mas->last = mas_logical_pivot(mas, pivots, mas->offset, type); > > entry = mas_slot(mas, slots, mas->offset); > > - if (ma_dead_node(node)) > > - return NULL; > > + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) > > + goto retry; > > - mas->last = pivot; > > return entry; > > } > > -static inline void mas_rewalk(struct ma_state *mas, unsigned long index) > > -{ > > -retry: > > - mas_set(mas, index); > > - mas_state_walk(mas); > > - if (mas_is_start(mas)) > > - goto retry; > > -} > > - > > /* > > * mas_next_entry() - Internal function to get the next entry. > > * @mas: The maple state > > @@ -4774,47 +4773,18 @@ static inline void mas_rewalk(struct ma_state *mas, unsigned long index) > > static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit) > > { > > void *entry = NULL; > > - struct maple_node *node; > > - unsigned long last; > > - enum maple_type mt; > > if (mas->last >= limit) > > return NULL; > > - last = mas->last; > > -retry: > > - node = mas_mn(mas); > > - mt = mte_node_type(mas->node); > > - mas->offset++; > > - if (unlikely(mas->offset >= mt_slots[mt])) { > > - mas->offset = mt_slots[mt] - 1; > > - goto next_node; > > - } > > - > > - while (!mas_is_none(mas)) { > > - entry = mas_next_nentry(mas, node, limit, mt); > > - if (unlikely(ma_dead_node(node))) { > > - mas_rewalk(mas, last); > > - goto retry; > > - } > > - > > - if (likely(entry)) > > - return entry; > > - > > - if (unlikely((mas->last >= limit))) > > - return NULL; > > + entry = mas_next_slot_limit(mas, limit); > > + if (entry) > > + return entry; > > -next_node: > > - if (unlikely(mas_next_node(mas, node, limit))) { > > - mas_rewalk(mas, last); > > - goto retry; > > - } > > - mas->offset = 0; > > - node = mas_mn(mas); > > - mt = mte_node_type(mas->node); > > - } > > + if (mas_is_none(mas)) > > + return NULL; > > - return NULL; > > + return mas_next_slot_limit(mas, limit); > > } > > /* > > @@ -4845,10 +4815,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, > > slots = ma_slots(mn, mt); > > pivots = ma_pivots(mn, mt); > > count = ma_data_end(mn, mt, pivots, mas->max); > > - if (unlikely(ma_dead_node(mn))) { > > - mas_rewalk(mas, index); > > + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) > > goto retry; > > - } > > offset = mas->offset - 1; > > if (offset >= mt_slots[mt]) > > @@ -4861,10 +4829,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, > > pivot = pivots[offset]; > > } > > - if (unlikely(ma_dead_node(mn))) { > > - mas_rewalk(mas, index); > > + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) > > goto retry; > > - } > > while (offset && !mas_slot(mas, slots, offset)) { > > pivot = pivots[--offset]; > > @@ -4881,10 +4847,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, > > min = mas_safe_min(mas, pivots, offset); > > entry = mas_slot(mas, slots, offset); > > - if (unlikely(ma_dead_node(mn))) { > > - mas_rewalk(mas, index); > > + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) > > goto retry; > > - } > > mas->offset = offset; > > mas->last = pivot;
diff --git a/lib/maple_tree.c b/lib/maple_tree.c index 31cbfd7b44728..fe6c9da6f2bd5 100644 --- a/lib/maple_tree.c +++ b/lib/maple_tree.c @@ -4619,15 +4619,16 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, if (mas->max >= max) goto no_entry; + min = mas->max + 1; + if (min > max) + goto no_entry; + level = 0; do { if (ma_is_root(node)) goto no_entry; - min = mas->max + 1; - if (min > max) - goto no_entry; - + /* Walk up. */ if (unlikely(mas_ascend(mas))) return 1; @@ -4645,13 +4646,12 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, slots = ma_slots(node, mt); pivot = mas_safe_pivot(mas, pivots, ++offset, mt); while (unlikely(level > 1)) { - /* Descend, if necessary */ + level--; enode = mas_slot(mas, slots, offset); if (unlikely(ma_dead_node(node))) return 1; mas->node = enode; - level--; node = mas_mn(mas); mt = mte_node_type(mas->node); slots = ma_slots(node, mt); @@ -4680,85 +4680,84 @@ static inline int mas_next_node(struct ma_state *mas, struct maple_node *node, return 0; } +static inline void mas_rewalk(struct ma_state *mas, unsigned long index) +{ +retry: + mas_set(mas, index); + mas_state_walk(mas); + if (mas_is_start(mas)) + goto retry; +} + +static inline bool mas_rewalk_if_dead(struct ma_state *mas, + struct maple_node *node, const unsigned long index) +{ + if (unlikely(ma_dead_node(node))) { + mas_rewalk(mas, index); + return true; + } + return false; +} + /* - * mas_next_nentry() - Get the next node entry - * @mas: The maple state - * @max: The maximum value to check - * @*range_start: Pointer to store the start of the range. + * mas_next_slot() - Get the entry in the next slot * - * Sets @mas->offset to the offset of the next node entry, @mas->last to the - * pivot of the entry. + * @mas: The maple state + * @max: The maximum starting range * - * Return: The next entry, %NULL otherwise + * Return: The entry in the next slot which is possibly NULL */ -static inline void *mas_next_nentry(struct ma_state *mas, - struct maple_node *node, unsigned long max, enum maple_type type) +void *mas_next_slot(struct ma_state *mas, unsigned long max) { - unsigned char count; - unsigned long pivot; - unsigned long *pivots; void __rcu **slots; + unsigned long *pivots; + unsigned long pivot; + enum maple_type type; + struct maple_node *node; + unsigned char data_end; + unsigned long save_point = mas->last; void *entry; - if (mas->last == mas->max) { - mas->index = mas->max; - return NULL; - } - - slots = ma_slots(node, type); +retry: + node = mas_mn(mas); + type = mte_node_type(mas->node); pivots = ma_pivots(node, type); - count = ma_data_end(node, type, pivots, mas->max); - if (unlikely(ma_dead_node(node))) - return NULL; - - mas->index = mas_safe_min(mas, pivots, mas->offset); - if (unlikely(ma_dead_node(node))) - return NULL; - - if (mas->index > max) - return NULL; + data_end = ma_data_end(node, type, pivots, mas->max); + pivot = mas_logical_pivot(mas, pivots, mas->offset, type); + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) + goto retry; - if (mas->offset > count) + if (pivot >= max) return NULL; - while (mas->offset < count) { - pivot = pivots[mas->offset]; - entry = mas_slot(mas, slots, mas->offset); - if (ma_dead_node(node)) - return NULL; - - mas->last = pivot; - if (entry) - return entry; - - if (pivot >= max) - return NULL; + if (likely(data_end > mas->offset)) { + mas->offset++; + mas->index = mas->last + 1; + } else { + if (mas_next_node(mas, node, max)) { + mas_rewalk(mas, save_point); + goto retry; + } - if (pivot >= mas->max) + if (mas_is_none(mas)) return NULL; - mas->index = pivot + 1; - mas->offset++; + mas->offset = 0; + mas->index = mas->min; + node = mas_mn(mas); + type = mte_node_type(mas->node); + pivots = ma_pivots(node, type); } - pivot = mas_logical_pivot(mas, pivots, mas->offset, type); + slots = ma_slots(node, type); + mas->last = mas_logical_pivot(mas, pivots, mas->offset, type); entry = mas_slot(mas, slots, mas->offset); - if (ma_dead_node(node)) - return NULL; + if (unlikely(mas_rewalk_if_dead(mas, node, save_point))) + goto retry; - mas->last = pivot; return entry; } -static inline void mas_rewalk(struct ma_state *mas, unsigned long index) -{ -retry: - mas_set(mas, index); - mas_state_walk(mas); - if (mas_is_start(mas)) - goto retry; -} - /* * mas_next_entry() - Internal function to get the next entry. * @mas: The maple state @@ -4774,47 +4773,18 @@ static inline void mas_rewalk(struct ma_state *mas, unsigned long index) static inline void *mas_next_entry(struct ma_state *mas, unsigned long limit) { void *entry = NULL; - struct maple_node *node; - unsigned long last; - enum maple_type mt; if (mas->last >= limit) return NULL; - last = mas->last; -retry: - node = mas_mn(mas); - mt = mte_node_type(mas->node); - mas->offset++; - if (unlikely(mas->offset >= mt_slots[mt])) { - mas->offset = mt_slots[mt] - 1; - goto next_node; - } - - while (!mas_is_none(mas)) { - entry = mas_next_nentry(mas, node, limit, mt); - if (unlikely(ma_dead_node(node))) { - mas_rewalk(mas, last); - goto retry; - } - - if (likely(entry)) - return entry; - - if (unlikely((mas->last >= limit))) - return NULL; + entry = mas_next_slot_limit(mas, limit); + if (entry) + return entry; -next_node: - if (unlikely(mas_next_node(mas, node, limit))) { - mas_rewalk(mas, last); - goto retry; - } - mas->offset = 0; - node = mas_mn(mas); - mt = mte_node_type(mas->node); - } + if (mas_is_none(mas)) + return NULL; - return NULL; + return mas_next_slot_limit(mas, limit); } /* @@ -4845,10 +4815,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, slots = ma_slots(mn, mt); pivots = ma_pivots(mn, mt); count = ma_data_end(mn, mt, pivots, mas->max); - if (unlikely(ma_dead_node(mn))) { - mas_rewalk(mas, index); + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) goto retry; - } offset = mas->offset - 1; if (offset >= mt_slots[mt]) @@ -4861,10 +4829,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, pivot = pivots[offset]; } - if (unlikely(ma_dead_node(mn))) { - mas_rewalk(mas, index); + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) goto retry; - } while (offset && !mas_slot(mas, slots, offset)) { pivot = pivots[--offset]; @@ -4881,10 +4847,8 @@ static inline void *mas_prev_nentry(struct ma_state *mas, unsigned long limit, min = mas_safe_min(mas, pivots, offset); entry = mas_slot(mas, slots, offset); - if (unlikely(ma_dead_node(mn))) { - mas_rewalk(mas, index); + if (unlikely(mas_rewalk_if_dead(mas, mn, index))) goto retry; - } mas->offset = offset; mas->last = pivot;
Sometimes, during a tree walk, the user needs the next slot regardless of if it is empty or not. Add an interface to get the next slot. Since there are no consecutive NULLs allowed in the tree, the mas_next() function can only advance two slots at most. So use the new mas_next_slot() interface to align both implementations. Signed-off-by: Liam R. Howlett <Liam.Howlett@oracle.com> --- lib/maple_tree.c | 178 +++++++++++++++++++---------------------------- 1 file changed, 71 insertions(+), 107 deletions(-)