linux-kernel - Re: [PATCH] hashtable: remove a redundant check in hash_for_each

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date:   Thu, 7 Oct 2021 00:30:58 +0000
From:   Wei Yang <richard.weiyang@...il.com>
To:     NeilBrown <neilb@...e.de>
Cc:     Wei Yang <richard.weiyang@...il.com>, kuba@...nel.org,
        gregkh@...uxfoundation.org, mojha@...eaurora.org, jkosina@...e.cz,
        linux-kernel@...r.kernel.org
Subject: Re: [PATCH] hashtable: remove a redundant check in
 hash_for_each_xxx()

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@...il.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@...e.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