Skip to contentSkip to conversation

bpf: Use hlist_nulls_replace_rcu() when updating htab elements

PATCH In review [email protected] 3 participants 4 messages May 27 BPF

lore
Share & tools
lore
#0 lore raw

PATCH 1/1 bpf: Use hlist_nulls_replace_rcu() when updating htab elements

From: Xuanqiang Luo <[email protected]>

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.

---
 kernel/bpf/hashtab.c | 16 ++++++----------
 1 file changed, 6 insertions(+), 10 deletions(-)
kernel/bpf/hashtab.c +6 -10
index 3dd9b4924ae4f..b20e82bd253dc 100644
@@ -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;
 
Signature · 1 line
2.43.0
#1 lore raw
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [High] Using hlist_nulls_replace_rcu() violates the hlist_nulls invariant that reused elements must be…

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] Using hlist_nulls_replace_rcu() violates the hlist_nulls invariant that reused elements must be inserted at the head, leading to spurious lookup failures in preallocated and LRU maps. --

commit 152c68c8990ac2fd12423e6b3208030a31a5a41d
Author: Xuanqiang Luo <[email protected]>

bpf: Use hlist_nulls_replace_rcu() when updating htab elements

This patch modifies the BPF hash map update logic to use hlist_nulls_replace_rcu() instead of adding the new element to the head and deleting the old one.

Quoted 4 lines
kernel/bpf/hashtab.c +0 -0
index 3dd9b4924ae4f..b20e82bd253dc 100644

[ ... ]

kernel/bpf/hashtab.c static long htab_map_update_elem(struct bpf_map *map, void *key, void *value, · line 1250

Quoted 11 lines
kernel/bpf/hashtab.c +1 -5
@@ -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);

[Severity: High]
Does using hlist_nulls_replace_rcu() here violate the hlist_nulls lockless traversal invariants for reused elements?

For BPF preallocated and LRU hash maps, elements are recycled without an RCU grace period. The hlist_nulls algorithm relies on the invariant that such recycled elements must be inserted at the head of the list.

If a lockless reader is preempted while holding a reference to an element that is subsequently deleted and then reused as l_new, replacing l_old in the middle of the chain means l_new->next will point to l_old->next.

When the preempted reader resumes and follows the next pointer, could it skip all elements that were located before l_old in the bucket chain, potentially resulting in spurious lookup failures?

[ ... ]

kernel/bpf/hashtab.c static long htab_lru_map_update_elem(struct bpf_map *map, void *key, void *value · line 1322

Quoted 12 lines
kernel/bpf/hashtab.c +1 -5
@@ -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);

[Severity: High]
Would this suffer from the same lockless traversal issue mentioned above?

Since LRU maps heavily recycle elements without an RCU grace period, inserting a recycled element anywhere other than the head of the chain could cause concurrent readers to miss elements.

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
#2 lore raw
In reply to [email protected]
This looks like a bug fix that should include:
Quoted 11 lines

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.

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.

Quoted 14 lines
kernel/bpf/hashtab.c +0 -5
index 3dd9b4924ae4..b20e82bd253d 100644
@@ -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);

kernel/bpf/hashtab.c static long htab_map_update_elem(struct bpf_map *map, void *key, void *value, · line 1259

Quoted 10 lines
kernel/bpf/hashtab.c +3 -0
+		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

#3 lore raw
Quoted 64 lines · 在 2026/5/27 16:06, [email protected] 写道:
Quoted 11 lines

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.

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.

Quoted 14 lines
kernel/bpf/hashtab.c +0 -5
index 3dd9b4924ae4..b20e82bd253d 100644
@@ -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);

kernel/bpf/hashtab.c static long htab_map_update_elem(struct bpf_map *map, void *key, void *value, · line 1259

Quoted 10 lines
kernel/bpf/hashtab.c +3 -0
+		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?

Quoted 8 lines

[ ... ]

---
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.