[PATCH] hashtable: remove a redundant check in hash_for_each_xxx()

[PATCH] hashtable: remove a redundant check in hash_for_each_xxx()

[Wei Yang]

The three hash_for_each_xxx() helper iterate the hash table with help
of hlist_for_each_entry_xxx(), which breaks the loop only when obj is
NULL.

This means the check during each iteration is redundant. This patch
removes it.

Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
---
 include/linux/hashtable.h | 9 +++------
 1 file changed, 3 insertions(+), 6 deletions(-)

diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
index f6c666730b8c..a15719ed303f 100644
--- a/include/linux/hashtable.h
+++ b/include/linux/hashtable.h
@@ -124,8 +124,7 @@ static inline void hash_del_rcu(struct hlist_node *node)
  * @member: the name of the hlist_node within the struct
  */
 #define hash_for_each(name, bkt, obj, member)				\
-	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
-			(bkt)++)\
+	for ((bkt) = 0, obj = NULL; (bkt) < HASH_SIZE(name); (bkt)++)	\
 		hlist_for_each_entry(obj, &name[bkt], member)
 
 /**
@@ -136,8 +135,7 @@ static inline void hash_del_rcu(struct hlist_node *node)
  * @member: the name of the hlist_node within the struct
  */
 #define hash_for_each_rcu(name, bkt, obj, member)			\
-	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
-			(bkt)++)\
+	for ((bkt) = 0, obj = NULL; (bkt) < HASH_SIZE(name); (bkt)++)	\
 		hlist_for_each_entry_rcu(obj, &name[bkt], member)
 
 /**
@@ -150,8 +148,7 @@ static inline void hash_del_rcu(struct hlist_node *node)
  * @member: the name of the hlist_node within the struct
  */
 #define hash_for_each_safe(name, bkt, tmp, obj, member)			\
-	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
-			(bkt)++)\
+	for ((bkt) = 0, obj = NULL; (bkt) < HASH_SIZE(name); (bkt)++)	\
 		hlist_for_each_entry_safe(obj, tmp, &name[bkt], member)
 
 /**
-- 
2.23.0

Re: [PATCH] hashtable: remove a redundant check in hash_for_each_xxx()

[Greg KH]

On Wed, Oct 06, 2021 at 03:21:00PM +0000, Wei Yang wrote:
> The three hash_for_each_xxx() helper iterate the hash table with help
> of hlist_for_each_entry_xxx(), which breaks the loop only when obj is
> NULL.
> 
> This means the check during each iteration is redundant. This patch
> removes it.

Are you sure that the compiler didn't already remove it?  Is the code
output the same or different with this change?

How did you test this?

thanks,

greg k-h

Re: [PATCH] hashtable: remove a redundant check in hash_for_each_xxx()

[NeilBrown]

On Thu, 07 Oct 2021, Wei Yang wrote:
> The three hash_for_each_xxx() helper iterate the hash table with help
> of hlist_for_each_entry_xxx(), which breaks the loop only when obj is
> NULL.
> 
> This means the check during each iteration is redundant. This patch
> removes it.
> 
> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
> ---
>  include/linux/hashtable.h | 9 +++------
>  1 file changed, 3 insertions(+), 6 deletions(-)
> 
> diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
> index f6c666730b8c..a15719ed303f 100644
> --- a/include/linux/hashtable.h
> +++ b/include/linux/hashtable.h
> @@ -124,8 +124,7 @@ static inline void hash_del_rcu(struct hlist_node *node)
>   * @member: the name of the hlist_node within the struct
>   */
>  #define hash_for_each(name, bkt, obj, member)				\
> -	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
> -			(bkt)++)\
> +	for ((bkt) = 0, obj = NULL; (bkt) < HASH_SIZE(name); (bkt)++)	\
>  		hlist_for_each_entry(obj, &name[bkt], member)

I think you are missing an important property of this code.
What we have here is a new loop command (hash_for_each()) that is
constructed from 2 nested loops.  This sort of construct is in general
difficult to use because in C it is common to use "break" to exit a loop
early.  'break' cannot exit two levels of loop though.  So if you aren't
careful, doing something like

  hash_for_each() {
     do something
     if (some test)
        break;
  }

might not do what you expect.  The 'break' will exit the inner loop, but
not the outer loop.  That could easily lead to buggy code.

But this macro *is* careful.  If the loop body *does* use break, then
the inner loop will abort but 'obj' will still be non-NULL.  The test
for NULL in the outer loop causes the outer loop to abort too - as the
programmer probably expected.

So by removing the 'obj == NULL' test, you would cause any usage which
breaks out of the loop to now be incorrect.

I recommend that instead of this patch, you provide a patch which
improves the documentation to make this clear. e.g.

  Note: it is safe to 'break' out of this loop even though it is a two
  nested loops.  The 'obj == NULL' test ensures that when the inner loop
  is broken, the outer loop will break too.

Thanks,
NeilBrown


>  
>  /**
> @@ -136,8 +135,7 @@ static inline void hash_del_rcu(struct hlist_node *node)
>   * @member: the name of the hlist_node within the struct
>   */
>  #define hash_for_each_rcu(name, bkt, obj, member)			\
> -	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
> -			(bkt)++)\
> +	for ((bkt) = 0, obj = NULL; (bkt) < HASH_SIZE(name); (bkt)++)	\
>  		hlist_for_each_entry_rcu(obj, &name[bkt], member)
>  
>  /**
> @@ -150,8 +148,7 @@ static inline void hash_del_rcu(struct hlist_node *node)
>   * @member: the name of the hlist_node within the struct
>   */
>  #define hash_for_each_safe(name, bkt, tmp, obj, member)			\
> -	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
> -			(bkt)++)\
> +	for ((bkt) = 0, obj = NULL; (bkt) < HASH_SIZE(name); (bkt)++)	\
>  		hlist_for_each_entry_safe(obj, tmp, &name[bkt], member)
>  
>  /**
> -- 
> 2.23.0
> 
> 

Re: [PATCH] hashtable: remove a redundant check in hash_for_each_xxx()

[Wei Yang]

On Thu, Oct 07, 2021 at 08:16:11AM +1100, NeilBrown wrote:
>On Thu, 07 Oct 2021, Wei Yang wrote:
>> The three hash_for_each_xxx() helper iterate the hash table with help
>> of hlist_for_each_entry_xxx(), which breaks the loop only when obj is
>> NULL.
>> 
>> This means the check during each iteration is redundant. This patch
>> removes it.
>> 
>> Signed-off-by: Wei Yang <richard.weiyang@gmail.com>
>> ---
>>  include/linux/hashtable.h | 9 +++------
>>  1 file changed, 3 insertions(+), 6 deletions(-)
>> 
>> diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
>> index f6c666730b8c..a15719ed303f 100644
>> --- a/include/linux/hashtable.h
>> +++ b/include/linux/hashtable.h
>> @@ -124,8 +124,7 @@ static inline void hash_del_rcu(struct hlist_node *node)
>>   * @member: the name of the hlist_node within the struct
>>   */
>>  #define hash_for_each(name, bkt, obj, member)				\
>> -	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
>> -			(bkt)++)\
>> +	for ((bkt) = 0, obj = NULL; (bkt) < HASH_SIZE(name); (bkt)++)	\
>>  		hlist_for_each_entry(obj, &name[bkt], member)
>
>I think you are missing an important property of this code.
>What we have here is a new loop command (hash_for_each()) that is
>constructed from 2 nested loops.  This sort of construct is in general
>difficult to use because in C it is common to use "break" to exit a loop
>early.  'break' cannot exit two levels of loop though.  So if you aren't
>careful, doing something like
>
>  hash_for_each() {
>     do something
>     if (some test)
>        break;
>  }
>
>might not do what you expect.  The 'break' will exit the inner loop, but
>not the outer loop.  That could easily lead to buggy code.
>
>But this macro *is* careful.  If the loop body *does* use break, then
>the inner loop will abort but 'obj' will still be non-NULL.  The test
>for NULL in the outer loop causes the outer loop to abort too - as the
>programmer probably expected.
>

Thanks for pointing out. I missed this case.

>So by removing the 'obj == NULL' test, you would cause any usage which
>breaks out of the loop to now be incorrect.
>
>I recommend that instead of this patch, you provide a patch which
>improves the documentation to make this clear. e.g.
>
>  Note: it is safe to 'break' out of this loop even though it is a two
>  nested loops.  The 'obj == NULL' test ensures that when the inner loop
>  is broken, the outer loop will break too.
>

Here is a draft patch based on you comment:

diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
index f6c666730b8c..2ff4cb5e6a22 100644
--- a/include/linux/hashtable.h
+++ b/include/linux/hashtable.h
@@ -116,6 +116,13 @@ static inline void hash_del_rcu(struct hlist_node *node)
 	hlist_del_init_rcu(node);
 }
 
+/**
+ * Note: the following three hash_for_each[_xxx] helpers introduce a new loop
+ * command that is constructed from 2 nested loops. It is safe to 'break' out
+ * of this loop even though it is a two nested loops.  The 'obj == NULL' test
+ * ensures that when the inner loop is broken, the outer loop will break too.
+ */
+
 /**
  * hash_for_each - iterate over a hashtable
  * @name: hashtable to iterate


If you feel good, I would like to add 

Sugguested-by: NeilBrown <neilb@suse.de>

>Thanks,
>NeilBrown
>
>
>>  
>>  /**
>> @@ -136,8 +135,7 @@ static inline void hash_del_rcu(struct hlist_node *node)
>>   * @member: the name of the hlist_node within the struct
>>   */
>>  #define hash_for_each_rcu(name, bkt, obj, member)			\
>> -	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
>> -			(bkt)++)\
>> +	for ((bkt) = 0, obj = NULL; (bkt) < HASH_SIZE(name); (bkt)++)	\
>>  		hlist_for_each_entry_rcu(obj, &name[bkt], member)
>>  
>>  /**
>> @@ -150,8 +148,7 @@ static inline void hash_del_rcu(struct hlist_node *node)
>>   * @member: the name of the hlist_node within the struct
>>   */
>>  #define hash_for_each_safe(name, bkt, tmp, obj, member)			\
>> -	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
>> -			(bkt)++)\
>> +	for ((bkt) = 0, obj = NULL; (bkt) < HASH_SIZE(name); (bkt)++)	\
>>  		hlist_for_each_entry_safe(obj, tmp, &name[bkt], member)
>>  
>>  /**
>> -- 
>> 2.23.0
>> 
>> 

-- 
Wei Yang
Help you, Help me

Re: [PATCH] hashtable: remove a redundant check in hash_for_each_xxx()

[NeilBrown]

On Thu, 07 Oct 2021, Wei Yang wrote:
> 
> Here is a draft patch based on you comment:
> 
> diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
> index f6c666730b8c..2ff4cb5e6a22 100644
> --- a/include/linux/hashtable.h
> +++ b/include/linux/hashtable.h
> @@ -116,6 +116,13 @@ static inline void hash_del_rcu(struct hlist_node *node)
>  	hlist_del_init_rcu(node);
>  }
>  
> +/**
> + * Note: the following three hash_for_each[_xxx] helpers introduce a new loop
> + * command that is constructed from 2 nested loops. It is safe to 'break' out
> + * of this loop even though it is a two nested loops.  The 'obj == NULL' test
> + * ensures that when the inner loop is broken, the outer loop will break too.
> + */
> +
>  /**
>   * hash_for_each - iterate over a hashtable
>   * @name: hashtable to iterate
> 
> 
> If you feel good, I would like to add 
> 
> Sugguested-by: NeilBrown <neilb@suse.de>

That's definitely an improvement.

I'd probably put it in the kernel-doc comment for hash_for_each,
then in the other two just put the "it is safe" bit.  Something like
the following.  But I don't feel strongly about it.
I'm happy to say
  Reviewed-by: NeilBrown <neilb@suse.de>

for your patch.

Thanks,
NeilBrown


diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
index f6c666730b8c..61db940c9501 100644
--- a/include/linux/hashtable.h
+++ b/include/linux/hashtable.h
@@ -122,6 +122,10 @@ static inline void hash_del_rcu(struct hlist_node *node)
  * @bkt: integer to use as bucket loop cursor
  * @obj: the type * to use as a loop cursor for each entry
  * @member: the name of the hlist_node within the struct
+ *
+ * Note: It is safe to 'break' out of this loop even though it is a two
+ * nested loops.  The 'obj == NULL' test ensures that when the inner loop
+ * is broken, the outer loop will break too.
  */
 #define hash_for_each(name, bkt, obj, member)				\
 	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
@@ -134,6 +138,8 @@ static inline void hash_del_rcu(struct hlist_node *node)
  * @bkt: integer to use as bucket loop cursor
  * @obj: the type * to use as a loop cursor for each entry
  * @member: the name of the hlist_node within the struct
+ *
+ * It is safe to 'break' out of this loop.
  */
 #define hash_for_each_rcu(name, bkt, obj, member)			\
 	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
@@ -148,6 +154,8 @@ static inline void hash_del_rcu(struct hlist_node *node)
  * @tmp: a &struct hlist_node used for temporary storage
  * @obj: the type * to use as a loop cursor for each entry
  * @member: the name of the hlist_node within the struct
+ *
+ * It is safe to 'break' out of this loop.
  */
 #define hash_for_each_safe(name, bkt, tmp, obj, member)			\
 	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\

Re: [PATCH] hashtable: remove a redundant check in hash_for_each_xxx()

[Wei Yang]

On Thu, Oct 07, 2021 at 11:50:22AM +1100, NeilBrown wrote:
>On Thu, 07 Oct 2021, Wei Yang wrote:
>> 
>> Here is a draft patch based on you comment:
>> 
>> diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
>> index f6c666730b8c..2ff4cb5e6a22 100644
>> --- a/include/linux/hashtable.h
>> +++ b/include/linux/hashtable.h
>> @@ -116,6 +116,13 @@ static inline void hash_del_rcu(struct hlist_node *node)
>>  	hlist_del_init_rcu(node);
>>  }
>>  
>> +/**
>> + * Note: the following three hash_for_each[_xxx] helpers introduce a new loop
>> + * command that is constructed from 2 nested loops. It is safe to 'break' out
>> + * of this loop even though it is a two nested loops.  The 'obj == NULL' test
>> + * ensures that when the inner loop is broken, the outer loop will break too.
>> + */
>> +
>>  /**
>>   * hash_for_each - iterate over a hashtable
>>   * @name: hashtable to iterate
>> 
>> 
>> If you feel good, I would like to add 
>> 
>> Sugguested-by: NeilBrown <neilb@suse.de>
>
>That's definitely an improvement.
>
>I'd probably put it in the kernel-doc comment for hash_for_each,
>then in the other two just put the "it is safe" bit.  Something like
>the following.  But I don't feel strongly about it.
>I'm happy to say
>  Reviewed-by: NeilBrown <neilb@suse.de>
>

Thanks for your detailed instruction :-)

>for your patch.
>
>Thanks,
>NeilBrown
>
>
>diff --git a/include/linux/hashtable.h b/include/linux/hashtable.h
>index f6c666730b8c..61db940c9501 100644
>--- a/include/linux/hashtable.h
>+++ b/include/linux/hashtable.h
>@@ -122,6 +122,10 @@ static inline void hash_del_rcu(struct hlist_node *node)
>  * @bkt: integer to use as bucket loop cursor
>  * @obj: the type * to use as a loop cursor for each entry
>  * @member: the name of the hlist_node within the struct
>+ *
>+ * Note: It is safe to 'break' out of this loop even though it is a two
>+ * nested loops.  The 'obj == NULL' test ensures that when the inner loop
>+ * is broken, the outer loop will break too.
>  */
> #define hash_for_each(name, bkt, obj, member)				\
> 	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
>@@ -134,6 +138,8 @@ static inline void hash_del_rcu(struct hlist_node *node)
>  * @bkt: integer to use as bucket loop cursor
>  * @obj: the type * to use as a loop cursor for each entry
>  * @member: the name of the hlist_node within the struct
>+ *
>+ * It is safe to 'break' out of this loop.
>  */
> #define hash_for_each_rcu(name, bkt, obj, member)			\
> 	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\
>@@ -148,6 +154,8 @@ static inline void hash_del_rcu(struct hlist_node *node)
>  * @tmp: a &struct hlist_node used for temporary storage
>  * @obj: the type * to use as a loop cursor for each entry
>  * @member: the name of the hlist_node within the struct
>+ *
>+ * It is safe to 'break' out of this loop.
>  */
> #define hash_for_each_safe(name, bkt, tmp, obj, member)			\
> 	for ((bkt) = 0, obj = NULL; obj == NULL && (bkt) < HASH_SIZE(name);\

-- 
Wei Yang
Help you, Help me