[PATCH bpf-next v1] bpf: Use hlist_nulls_replace_rcu() when updating htab elements

[PATCH bpf-next v1] bpf: Use hlist_nulls_replace_rcu() when updating htab elements

[xuanqiang.luo]

From: Xuanqiang Luo <luoxuanqiang@kylinos.cn>

When updating an existing element, the current code does
hlist_nulls_add_head_rcu() followed by hlist_nulls_del_rcu(), exposing
a transient state where both old and new elements are visible to
concurrent RCU traversals.

Use hlist_nulls_replace_rcu() to atomically replace the old element in
place, so RCU readers always see a consistent hash chain.

Signed-off-by: Xuanqiang Luo <luoxuanqiang@kylinos.cn>
---
 kernel/bpf/hashtab.c | 16 ++++++----------
 1 file changed, 6 insertions(+), 10 deletions(-)

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 3dd9b4924ae4f..b20e82bd253dc 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -1246,18 +1246,16 @@ static long htab_map_update_elem(struct bpf_map *map, void *key, void *value,
 		goto err;
 	}
 
-	/* add new element to the head of the list, so that
-	 * concurrent search will find it before old elem
-	 */
-	hlist_nulls_add_head_rcu(&l_new->hash_node, head);
 	if (l_old) {
-		hlist_nulls_del_rcu(&l_old->hash_node);
+		hlist_nulls_replace_rcu(&l_old->hash_node, &l_new->hash_node);
 
 		/* l_old has already been stashed in htab->extra_elems, free
 		 * its special fields before it is available for reuse.
 		 */
 		if (htab_is_prealloc(htab))
 			check_and_free_fields(htab, l_old);
+	} else {
+		hlist_nulls_add_head_rcu(&l_new->hash_node, head);
 	}
 	htab_unlock_bucket(b, flags);
 	if (l_old && !htab_is_prealloc(htab))
@@ -1319,13 +1317,11 @@ static long htab_lru_map_update_elem(struct bpf_map *map, void *key, void *value
 	if (ret)
 		goto err;
 
-	/* add new element to the head of the list, so that
-	 * concurrent search will find it before old elem
-	 */
-	hlist_nulls_add_head_rcu(&l_new->hash_node, head);
 	if (l_old) {
 		bpf_lru_node_set_ref(&l_new->lru_node);
-		hlist_nulls_del_rcu(&l_old->hash_node);
+		hlist_nulls_replace_rcu(&l_old->hash_node, &l_new->hash_node);
+	} else {
+		hlist_nulls_add_head_rcu(&l_new->hash_node, head);
 	}
 	ret = 0;
 
-- 
2.43.0

Re: [PATCH bpf-next v1] bpf: Use hlist_nulls_replace_rcu() when updating htab elements

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 2978 bytes --]

>     bpf: Use hlist_nulls_replace_rcu() when updating htab elements
>
>     When updating an existing element, the current code does
>     hlist_nulls_add_head_rcu() followed by hlist_nulls_del_rcu(), exposing
>     a transient state where both old and new elements are visible to
>     concurrent RCU traversals.
>
>     Use hlist_nulls_replace_rcu() to atomically replace the old element in
>     place, so RCU readers always see a consistent hash chain.
>
>     Signed-off-by: Xuanqiang Luo <luoxuanqiang@kylinos.cn>

This looks like a bug fix that should include:

  Fixes: 4fe8435909fd ("bpf: convert htab map to hlist_nulls")

The bug was introduced by commit 4fe8435909fd which added the
hlist_nulls_add_head_rcu() followed by hlist_nulls_del_rcu() pattern,
exposing a transient state where both old and new elements are visible
to concurrent RCU traversals.

> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> index 3dd9b4924ae4..b20e82bd253d 100644
> --- a/kernel/bpf/hashtab.c
> +++ b/kernel/bpf/hashtab.c
> @@ -1246,18 +1246,16 @@ static long htab_map_update_elem(struct bpf_map *map, void *key, void *value,
>  		goto err;
>  	}
>
> -	/* add new element to the head of the list, so that
> -	 * concurrent search will find it before old elem
> -	 */
> -	hlist_nulls_add_head_rcu(&l_new->hash_node, head);
>  	if (l_old) {
> -		hlist_nulls_del_rcu(&l_old->hash_node);
> +		hlist_nulls_replace_rcu(&l_old->hash_node, &l_new->hash_node);
>
>  		/* l_old has already been stashed in htab->extra_elems, free
>  		 * its special fields before it is available for reuse.
>  		 */
>  		if (htab_is_prealloc(htab))
>  			check_and_free_fields(htab, l_old);
> +	} else {
> +		hlist_nulls_add_head_rcu(&l_new->hash_node, head);
>  	}

Does this atomic replacement approach actually solve the lookup problem?

During review of Hou Tao's earlier v1 patch that used the same approach,
Alexei Starovoitov raised a fundamental concern:

  "This atomic replacement doesn't really solve anything. lookup will see
   one element. That element could be deleted by another thread. bucket
   lock and either two step update or single step don't change anything
   from the pov of bpf prog doing lookup."

Reference: https://lore.kernel.org/bpf/CAADnVQKD94q-G4N=w9PJU+k6gPhM8GmUYcyfj=33B_mKX6Qbjw@mail.gmail.com/

Hou Tao acknowledged this limitation and abandoned this approach in v2,
instead implementing atomic updates only for htab of maps. This patch
appears to be a re-implementation of the abandoned v1 approach without
addressing the fundamental concerns raised during that review.

Can you clarify how this approach addresses the concerns that led to
abandonment of the similar change in Hou Tao's earlier patch series?

[ ... ]


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/26496972451

Re: [PATCH bpf-next v1] bpf: Use hlist_nulls_replace_rcu() when updating htab elements

[luoxuanqiang]

在 2026/5/27 16:06, bot+bpf-ci@kernel.org 写道:
>>      bpf: Use hlist_nulls_replace_rcu() when updating htab elements
>>
>>      When updating an existing element, the current code does
>>      hlist_nulls_add_head_rcu() followed by hlist_nulls_del_rcu(), exposing
>>      a transient state where both old and new elements are visible to
>>      concurrent RCU traversals.
>>
>>      Use hlist_nulls_replace_rcu() to atomically replace the old element in
>>      place, so RCU readers always see a consistent hash chain.
>>
>>      Signed-off-by: Xuanqiang Luo <luoxuanqiang@kylinos.cn>
> This looks like a bug fix that should include:
>
>    Fixes: 4fe8435909fd ("bpf: convert htab map to hlist_nulls")
>
> The bug was introduced by commit 4fe8435909fd which added the
> hlist_nulls_add_head_rcu() followed by hlist_nulls_del_rcu() pattern,
> exposing a transient state where both old and new elements are visible
> to concurrent RCU traversals.
>
>> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
>> index 3dd9b4924ae4..b20e82bd253d 100644
>> --- a/kernel/bpf/hashtab.c
>> +++ b/kernel/bpf/hashtab.c
>> @@ -1246,18 +1246,16 @@ static long htab_map_update_elem(struct bpf_map *map, void *key, void *value,
>>   		goto err;
>>   	}
>>
>> -	/* add new element to the head of the list, so that
>> -	 * concurrent search will find it before old elem
>> -	 */
>> -	hlist_nulls_add_head_rcu(&l_new->hash_node, head);
>>   	if (l_old) {
>> -		hlist_nulls_del_rcu(&l_old->hash_node);
>> +		hlist_nulls_replace_rcu(&l_old->hash_node, &l_new->hash_node);
>>
>>   		/* l_old has already been stashed in htab->extra_elems, free
>>   		 * its special fields before it is available for reuse.
>>   		 */
>>   		if (htab_is_prealloc(htab))
>>   			check_and_free_fields(htab, l_old);
>> +	} else {
>> +		hlist_nulls_add_head_rcu(&l_new->hash_node, head);
>>   	}
> Does this atomic replacement approach actually solve the lookup problem?
>
> During review of Hou Tao's earlier v1 patch that used the same approach,
> Alexei Starovoitov raised a fundamental concern:
>
>    "This atomic replacement doesn't really solve anything. lookup will see
>     one element. That element could be deleted by another thread. bucket
>     lock and either two step update or single step don't change anything
>     from the pov of bpf prog doing lookup."
>
> Reference: https://lore.kernel.org/bpf/CAADnVQKD94q-G4N=w9PJU+k6gPhM8GmUYcyfj=33B_mKX6Qbjw@mail.gmail.com/
>
> Hou Tao acknowledged this limitation and abandoned this approach in v2,
> instead implementing atomic updates only for htab of maps. This patch
> appears to be a re-implementation of the abandoned v1 approach without
> addressing the fundamental concerns raised during that review.
>
> Can you clarify how this approach addresses the concerns that led to
> abandonment of the similar change in Hou Tao's earlier patch series?
>
> [ ... ]
>
>
> ---
> AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
> See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md
>
> CI run summary: https://github.com/kernel-patches/bpf/actions/runs/26496972451
I read the earlier discussion and realized I missed it, and I also missed
Hou Tao's updated patch 2c304172e0319 ("bpf: Support atomic update for htab
of maps") which already addressed this.

Sorry, My patch is outdated, please ignore it.

Thanks.