bpf: Use hlist_nulls_replace_rcu() when updating htab elements
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
@@ -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 *valueif (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
[email protected]
AI reviewThank 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
[ ... ]
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 *valueif (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
[email protected]
AI reviewThis looks like a bug fix that should include:
Quoted 11 lines
bpf: Use
hlist_nulls_replace_rcu()when updating htab elementsWhen updating an existing element, the current code does
hlist_nulls_add_head_rcu()followed byhlist_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 <[email protected]>
This looks like a bug fix that should include:
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@@ -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
Quoted 64 lines · 在 2026/5/27 16:06, [email protected] 写道:
Quoted 11 lines
bpf: Use
hlist_nulls_replace_rcu()when updating htab elementsWhen updating an existing element, the current code does
hlist_nulls_add_head_rcu()followed byhlist_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 <[email protected]>This looks like a bug fix that should include:
Fixes 4fe8435909fd ("bpf: convert htab map to hlist_nulls")The bug was introduced by commit
4fe8435909fdwhich added thehlist_nulls_add_head_rcu()followed byhlist_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@@ -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.mdCI 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.