bpf: Avoid deadlock using trylock when popping LRU free nodes
Subsystems (3)
cover bpf: Avoid deadlock using trylock when popping LRU free nodes
Switch the free-node pop paths to raw_spin_trylock*() so callers don't block on contended LRU locks. This is a narrower change than Menglong's approach [1], which aimed to eliminate the deadlock entirely.
The trylock-based approach avoids deadlocks in long-lived critical sections, while still allowing locking in short-lived ones. Although it does not completely eliminate the possibility of deadlock, it significantly reduces the likelihood in practice.
LRU-related deadlocks have been observed multiple times, including:
- [syzbot] [bpf?] possible deadlock in bpf_lru_push_free (2) [2]
- Re: [PATCH bpf v3 0/4] bpf: Free special fields when update hash and local storage maps [3]
- Raw log of CI failure [4]
BTW, this series also factors out the bpf_lru_node_set_hash() helper, along with a comment describing the required ordering and locking constraints.
Links:
[1] https://lore.kernel.org/bpf/[email protected]/
[2] https://lore.kernel.org/bpf/[email protected]/
[3] https://lore.kernel.org/bpf/CAEf4BzbTJCUx0D=zjx6+5m5iiGhwLzaP94hnw36ZMDHAf4-U_w@mail.gmail.com/
[4] https://github.com/kernel-patches/bpf/actions/runs/20943173932/job/60181505085
Leon Hwang (3):
bpf: Factor out bpf_lru_node_set_hash() helper
bpf: Avoid deadlock using trylock when popping LRU free nodes selftests/bpf: Allow -ENOMEM on LRU map updates
kernel/bpf/bpf_lru_list.c | 35 ++++++++++++++----- .../bpf/map_tests/map_percpu_stats.c | 3 +- 2 files changed, 28 insertions(+), 10 deletions(-)
--
2.52.0
PATCH 1/3 bpf: Factor out bpf_lru_node_set_hash() helper
The hash field is not used directly by the LRU list itself; it is consumed by the 'del_from_htab' callback when removing entries from the hash map.
The hash initialization must be performed under the LRU lock to avoid a race where a popped LRU node is evicted and deleted from the hash map with an uninitialized hash value, if defer the hash setting to hashtab.c::prealloc_lru_pop().
Factor out a dedicated bpf_lru_node_set_hash() helper and document this requirement to make the ordering and locking constraints explicit.
--- kernel/bpf/bpf_lru_list.c | 18 ++++++++++++++++-- 1 file changed, 16 insertions(+), 2 deletions(-)
kernel/bpf/bpf_lru_list.c +16 -2
@@ -341,13 +341,27 @@ static void bpf_lru_list_pop_free_to_local(struct bpf_lru *lru,raw_spin_unlock (&l->lock); } +/* +* The hash field is consumed by the 'del_from_htab' callback rather than +* the LRU list itself. Initialize it while holding the LRU lock to avoid +* a race where a popped LRU node is evicted and removed from the hash map +* with an uninitialized hash value, if defer the hash setting to +* hashtab.c::prealloc_lru_pop(). +*/ +static void bpf_lru_node_set_hash (struct bpf_lru *lru, +struct bpf_lru_node *node, +u32 hash) +{ + *(u32 *)((void *)node + lru->hash_offset) = hash; +} +static void __local_list_add_pending (struct bpf_lru *lru,struct bpf_lru_locallist *loc_l,int cpu,struct bpf_lru_node *node,u32 hash) { - *(u32 *)((void *)node + lru->hash_offset) = hash; +bpf_lru_node_set_hash (lru, node, hash); node->cpu = cpu; node->type =BPF_LRU_LOCAL_LIST_T_PENDING ;bpf_lru_node_clear_ref (node);
@@ -415,7 +429,7 @@ static struct bpf_lru_node *bpf_percpu_lru_pop_free(struct bpf_lru *lru,if (!list_empty (free_list)) { node = list_first_entry(free_list, struct bpf_lru_node, list); - *(u32 *)((void *)node + lru->hash_offset) = hash; +bpf_lru_node_set_hash (lru, node, hash);bpf_lru_node_clear_ref (node);__bpf_lru_node_move (l, node,BPF_LRU_LIST_T_INACTIVE ); }
Signature · 1 line
2.52.0
PATCH 2/3 bpf: Avoid deadlock using trylock when popping LRU free nodes
In reply to Leon HwangSwitch the free-node pop paths to raw_spin_trylock*() to avoid blocking on contended LRU locks.
If the global or per-CPU LRU lock is unavailable, refuse to refill the local free list and return NULL instead. This allows callers to back off safely rather than blocking or re-entering the same lock context.
This change avoids lockdep warnings and potential deadlocks caused by re-entrant LRU lock acquisition from NMI context, as shown below:
[ 418.260323] bpf_testmod: oh no, recursing into test_1, recursion_misses 1
[ 424.982207] ================================
[ 424.982216] WARNING: inconsistent lock state
[ 424.982223] inconsistent {INITIAL USE} -> {IN-NMI} usage.
[ 424.982314] *** DEADLOCK ***[...]
--- kernel/bpf/bpf_lru_list.c | 17 ++++++++++------- 1 file changed, 10 insertions(+), 7 deletions(-)
kernel/bpf/bpf_lru_list.c +10 -7
@@ -312,14 +312,15 @@ static void bpf_lru_list_push_free(struct bpf_lru_list *l,raw_spin_unlock_irqrestore (&l->lock, flags); } -static void bpf_lru_list_pop_free_to_local (struct bpf_lru *lru, +static bool bpf_lru_list_pop_free_to_local (struct bpf_lru *lru,struct bpf_lru_locallist *loc_l) {struct bpf_lru_list *l = &lru->common_lru.lru_list;struct bpf_lru_node *node, *tmp_node;unsigned int nfree =0 ; -raw_spin_lock (&l->lock); +if (!raw_spin_trylock (&l->lock)) +return false;__local_list_flush (l, loc_l);
@@ -339,6 +340,8 @@ static void bpf_lru_list_pop_free_to_local(struct bpf_lru *lru, BPF_LRU_LOCAL_LIST_T_FREE);raw_spin_unlock (&l->lock); + +return true; }/*
@@ -418,7 +421,8 @@ static struct bpf_lru_node *bpf_percpu_lru_pop_free(struct bpf_lru *lru, l =per_cpu_ptr (lru->percpu_lru, cpu); -raw_spin_lock_irqsave (&l->lock, flags); +if (!raw_spin_trylock_irqsave (&l->lock, flags)) +return NULL ;__bpf_lru_list_rotate (lru, l);
@@ -451,13 +455,12 @@ static struct bpf_lru_node *bpf_common_lru_pop_free(struct bpf_lru *lru, loc_l =per_cpu_ptr (clru->local_list, cpu); -raw_spin_lock_irqsave (&loc_l->lock, flags); +if (!raw_spin_trylock_irqsave (&loc_l->lock, flags)) +return NULL ; node =__local_list_pop_free (loc_l); -if (!node) { -bpf_lru_list_pop_free_to_local (lru, loc_l); +if (!node &&bpf_lru_list_pop_free_to_local (lru, loc_l)) node =__local_list_pop_free (loc_l); - }if (node)__local_list_add_pending (lru, loc_l, cpu, node, hash);
Signature · 1 line
2.52.0
[email protected]
AI reviewThe trylock conversion here looks correct, but what about the steal path that follows later in bpf_common_lru_pop_free()? Looking at the existing code (not shown in this diff), the steal loop still…
Quoted 4 lines
kernel/bpf/bpf_lru_list.c +0
-0
[ ... ]
Quoted 7 lines
kernel/bpf/bpf_lru_list.c +2
-1@@ -451,13 +455,12 @@ static struct bpf_lru_node *bpf_common_lru_pop_free(struct bpf_lru *lru, loc_l =per_cpu_ptr (clru->local_list, cpu); -raw_spin_lock_irqsave (&loc_l->lock, flags); +if (!raw_spin_trylock_irqsave (&loc_l->lock, flags)) +return NULL ;
kernel/bpf/bpf_lru_list.c static struct bpf_lru_node *bpf_common_lru_pop_free(struct bpf_lru *lru, · line 466
Quoted 10 lines
kernel/bpf/bpf_lru_list.c +1
-3node =__local_list_pop_free (loc_l); -if (!node) { -bpf_lru_list_pop_free_to_local (lru, loc_l); +if (!node &&bpf_lru_list_pop_free_to_local (lru, loc_l)) node =__local_list_pop_free (loc_l); - }if (node)__local_list_add_pending (lru, loc_l, cpu, node, hash);
The trylock conversion here looks correct, but what about the steal path that follows later in bpf_common_lru_pop_free()? Looking at the existing code (not shown in this diff), the steal loop still uses unconditional raw_spin_lock_irqsave():
do {
steal_loc_l = per_cpu_ptr(clru->local_list, steal);
raw_spin_lock_irqsave(&steal_loc_l->lock, flags);
...
} while (...);If the goal is to avoid NMI-context deadlocks when acquiring LRU locks, can the same deadlock scenario occur when NMI interrupts during the steal loop and the NMI handler tries to acquire the same steal_loc_l->lock?
Similarly, after a successful steal, there is another unconditional lock:
if (node) {
raw_spin_lock_irqsave(&loc_l->lock, flags);
__local_list_add_pending(lru, loc_l, cpu, node, hash);
raw_spin_unlock_irqrestore(&loc_l->lock, flags);
}Should these also use trylock to maintain consistency with the stated goal of avoiding NMI-context deadlocks?
---
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/21147913717
Quoted 43 lines · On 20/1/26 02:46, [email protected] wrote:
Quoted 4 lines
kernel/bpf/bpf_lru_list.c +0
-0[ ... ]
Quoted 7 lines
kernel/bpf/bpf_lru_list.c +2
-1@@ -451,13 +455,12 @@ static struct bpf_lru_node *bpf_common_lru_pop_free(struct bpf_lru *lru, loc_l =per_cpu_ptr (clru->local_list, cpu); -raw_spin_lock_irqsave (&loc_l->lock, flags); +if (!raw_spin_trylock_irqsave (&loc_l->lock, flags)) +return NULL ;kernel/bpf/bpf_lru_list.c static struct bpf_lru_node *bpf_common_lru_pop_free(struct bpf_lru *lru, · line 466
Quoted 10 lines
kernel/bpf/bpf_lru_list.c +1
-3node =__local_list_pop_free (loc_l); -if (!node) { -bpf_lru_list_pop_free_to_local (lru, loc_l); +if (!node &&bpf_lru_list_pop_free_to_local (lru, loc_l)) node =__local_list_pop_free (loc_l); - }if (node)__local_list_add_pending (lru, loc_l, cpu, node, hash);The trylock conversion here looks correct, but what about the steal path that follows later in
bpf_common_lru_pop_free()? Looking at the existing code (not shown in this diff), the steal loop still uses unconditionalraw_spin_lock_irqsave():do { steal_loc_l = per_cpu_ptr(clru->local_list, steal); raw_spin_lock_irqsave(&steal_loc_l->lock, flags); ... } while (...);If the goal is to avoid NMI-context deadlocks when acquiring LRU locks, can the same deadlock scenario occur when NMI interrupts during the steal loop and the NMI handler tries to acquire the same
steal_loc_l->lock?Similarly, after a successful steal, there is another unconditional lock:
Quoted 9 lines
if (node) { raw_spin_lock_irqsave(&loc_l->lock, flags); __local_list_add_pending(lru, loc_l, cpu, node, hash); raw_spin_unlock_irqrestore(&loc_l->lock, flags); }Should these also use trylock to maintain consistency with the stated goal of avoiding NMI-context deadlocks?
This patch is not intended to eliminate all possible deadlock scenarios. Its goal is to avoid deadlocks caused by long-lived critical sections in the free-node pop paths, where lock contention can persist and lead to re-entrant lock acquisition from NMI context.
The steal path and the post-steal update are both short-lived critical sections. They do not exhibit the same contention characteristics and have not been observed to trigger the reported deadlock scenarios. Converting these paths to trylock would add complexity without clear benefit, and is therefore unnecessary for the stated goal of this change.
Thanks,
Leon
Quoted 6 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/21147913717
Quoted 62 lines · Leon Hwang
Quoted 43 lines · On 20/1/26 02:46, [email protected] wrote:
Quoted 4 lines
kernel/bpf/bpf_lru_list.c +0
-0[ ... ]
Quoted 7 lines
kernel/bpf/bpf_lru_list.c +2
-1@@ -451,13 +455,12 @@ static struct bpf_lru_node *bpf_common_lru_pop_free(struct bpf_lru *lru, loc_l =per_cpu_ptr (clru->local_list, cpu); -raw_spin_lock_irqsave (&loc_l->lock, flags); +if (!raw_spin_trylock_irqsave (&loc_l->lock, flags)) +return NULL ;kernel/bpf/bpf_lru_list.c static struct bpf_lru_node *bpf_common_lru_pop_free(struct bpf_lru *lru, · line 466
Quoted 10 lines
kernel/bpf/bpf_lru_list.c +1
-3node =__local_list_pop_free (loc_l); -if (!node) { -bpf_lru_list_pop_free_to_local (lru, loc_l); +if (!node &&bpf_lru_list_pop_free_to_local (lru, loc_l)) node =__local_list_pop_free (loc_l); - }if (node)__local_list_add_pending (lru, loc_l, cpu, node, hash);The trylock conversion here looks correct, but what about the steal path that follows later in
bpf_common_lru_pop_free()? Looking at the existing code (not shown in this diff), the steal loop still uses unconditionalraw_spin_lock_irqsave():do { steal_loc_l = per_cpu_ptr(clru->local_list, steal); raw_spin_lock_irqsave(&steal_loc_l->lock, flags); ... } while (...);If the goal is to avoid NMI-context deadlocks when acquiring LRU locks, can the same deadlock scenario occur when NMI interrupts during the steal loop and the NMI handler tries to acquire the same
steal_loc_l->lock?Similarly, after a successful steal, there is another unconditional lock:
Quoted 9 lines
if (node) { raw_spin_lock_irqsave(&loc_l->lock, flags); __local_list_add_pending(lru, loc_l, cpu, node, hash); raw_spin_unlock_irqrestore(&loc_l->lock, flags); }Should these also use trylock to maintain consistency with the stated goal of avoiding NMI-context deadlocks?
This patch is not intended to eliminate all possible deadlock scenarios. Its goal is to avoid deadlocks caused by long-lived critical sections in the free-node pop paths, where lock contention can persist and lead to re-entrant lock acquisition from NMI context.
Quoted 5 lines
The steal path and the post-steal update are both short-lived critical sections. They do not exhibit the same contention characteristics and have not been observed to trigger the reported deadlock scenarios. Converting these paths to trylock would add complexity without clear benefit, and is therefore unnecessary for the stated goal of this change.
AI is correct. Either everything needs to be converted or none. Adding trylock in a few places because syzbot found them is not fixing anything. Just silencing one (or a few?) syzbot reports.
As I said in the other email, trylock is not an option.
rqspinlock is the only true way of addressing potential deadlocks. If it's too hard, then leave it as-is. Do not hack things half way.
Quoted 69 lines · Alexei Starovoitov
Quoted 62 lines · Leon Hwang
Quoted 43 lines · On 20/1/26 02:46, [email protected] wrote:
Quoted 4 lines
kernel/bpf/bpf_lru_list.c +0
-0[ ... ]
Quoted 7 lines
kernel/bpf/bpf_lru_list.c +2
-1@@ -451,13 +455,12 @@ static struct bpf_lru_node *bpf_common_lru_pop_free(struct bpf_lru *lru, loc_l =per_cpu_ptr (clru->local_list, cpu); -raw_spin_lock_irqsave (&loc_l->lock, flags); +if (!raw_spin_trylock_irqsave (&loc_l->lock, flags)) +return NULL ;kernel/bpf/bpf_lru_list.c static struct bpf_lru_node *bpf_common_lru_pop_free(struct bpf_lru *lru, · line 466
Quoted 10 lines
kernel/bpf/bpf_lru_list.c +1
-3node =__local_list_pop_free (loc_l); -if (!node) { -bpf_lru_list_pop_free_to_local (lru, loc_l); +if (!node &&bpf_lru_list_pop_free_to_local (lru, loc_l)) node =__local_list_pop_free (loc_l); - }if (node)__local_list_add_pending (lru, loc_l, cpu, node, hash);The trylock conversion here looks correct, but what about the steal path that follows later in
bpf_common_lru_pop_free()? Looking at the existing code (not shown in this diff), the steal loop still uses unconditionalraw_spin_lock_irqsave():do { steal_loc_l = per_cpu_ptr(clru->local_list, steal); raw_spin_lock_irqsave(&steal_loc_l->lock, flags); ... } while (...);If the goal is to avoid NMI-context deadlocks when acquiring LRU locks, can the same deadlock scenario occur when NMI interrupts during the steal loop and the NMI handler tries to acquire the same
steal_loc_l->lock?Similarly, after a successful steal, there is another unconditional lock:
Quoted 9 lines
if (node) { raw_spin_lock_irqsave(&loc_l->lock, flags); __local_list_add_pending(lru, loc_l, cpu, node, hash); raw_spin_unlock_irqrestore(&loc_l->lock, flags); }Should these also use trylock to maintain consistency with the stated goal of avoiding NMI-context deadlocks?
This patch is not intended to eliminate all possible deadlock scenarios. Its goal is to avoid deadlocks caused by long-lived critical sections in the free-node pop paths, where lock contention can persist and lead to re-entrant lock acquisition from NMI context.
Quoted 5 lines
The steal path and the post-steal update are both short-lived critical sections. They do not exhibit the same contention characteristics and have not been observed to trigger the reported deadlock scenarios. Converting these paths to trylock would add complexity without clear benefit, and is therefore unnecessary for the stated goal of this change.
Quoted 6 lines
AI is correct. Either everything needs to be converted or none. Adding trylock in a few places because syzbot found them is not fixing anything. Just silencing one (or a few?) syzbot reports.
As I said in the other email, trylock is not an option.
rqspinlock is the only true way of addressing potential deadlocks. If it's too hard, then leave it as-is. Do not hack things half way.
Understood.
Leave it as-is.
Thanks,
Leon
Daniel Borkmann
maintainerQuoted 15 lines · Leon Hwang
Switch the free-node pop paths to raw_spin_trylock*() to avoid blocking on contended LRU locks.
If the global or per-CPU LRU lock is unavailable, refuse to refill the local free list and return NULL instead. This allows callers to back off safely rather than blocking or re-entering the same lock context.
This change avoids lockdep warnings and potential deadlocks caused by re-entrant LRU lock acquisition from NMI context, as shown below:
[ 418.260323] bpf_testmod: oh no, recursing into test_1, recursion_misses 1 [ 424.982207] ================================ [ 424.982216] WARNING: inconsistent lock state [ 424.982223] inconsistent {INITIAL USE} -> {IN-NMI} usage. [ 424.982314] *** DEADLOCK ***
Quoted 6 lines
[...]
Signed-off-by Leon Hwang <[email protected]>--- kernel/bpf/bpf_lru_list.c | 17 ++++++++++------- 1 file changed, 10 insertions(+), 7 deletions(-)
Documentation/bpf/map_lru_hash_update.dot needs update?
Quoted 10 lines
kernel/bpf/bpf_lru_list.c +1
-1@@ -312,14 +312,15 @@ static void bpf_lru_list_push_free(struct bpf_lru_list *l,raw_spin_unlock_irqrestore (&l->lock, flags); } -static void bpf_lru_list_pop_free_to_local(struct bpf_lru *lru, +static bool bpf_lru_list_pop_free_to_local(struct bpf_lru *lru,
kernel/bpf/bpf_lru_list.c static void bpf_lru_list_push_free(struct bpf_lru_list *l, · line 324
Quoted 10 lines
kernel/bpf/bpf_lru_list.c +2
-1struct bpf_lru_locallist *loc_l) {struct bpf_lru_list *l = &lru->common_lru.lru_list;struct bpf_lru_node *node, *tmp_node;unsigned int nfree =0 ; -raw_spin_lock (&l->lock); +if (!raw_spin_trylock (&l->lock)) +return false;
Could you provide some more analysis, and the effect this has on real-world programs? Presumably they'll unexpectedly encounter a lot more frequent -ENOMEM as an error on bpf_map_update_elem even though memory might be available just that locks are contended?
Also, have you considered rqspinlock as a potential candidate to discover deadlocks?
Quoted 19 lines · Daniel Borkmann
Quoted 18 lines · Leon Hwang
Switch the free-node pop paths to raw_spin_trylock*() to avoid blocking on contended LRU locks.
If the global or per-CPU LRU lock is unavailable, refuse to refill the local free list and return NULL instead. This allows callers to back off safely rather than blocking or re-entering the same lock context.
This change avoids lockdep warnings and potential deadlocks caused by re-entrant LRU lock acquisition from NMI context, as shown below:
[ 418.260323]
bpf_testmod: oh no, recursing intotest_1,recursion_misses1
[ 424.982207] ================================
[ 424.982216] WARNING: inconsistent lock state
[ 424.982223] inconsistent {INITIAL USE} -> {IN-NMI} usage. [ 424.982314] *** DEADLOCK ***
[...]
Quoted 7 lines
Quoted 4 lines
Signed-off-by Leon Hwang <[email protected]>---
kernel/bpf/bpf_lru_list.c| 17 ++++++++++-------1 file changed, 10 insertions(+), 7 deletions(-)
Documentation/bpf/map_lru_hash_update.dotneeds update?
Yes, it needs update.
Quoted 25 lines
Quoted 18 lines
kernel/bpf/bpf_lru_list.c +3
-0@@ -312,14 +312,15 @@ static void bpf_lru_list_push_free(structbpf_lru_list *l, raw_spin_unlock_irqrestore(&l->lock, flags); } -static void bpf_lru_list_pop_free_to_local(struct bpf_lru *lru, +static bool bpf_lru_list_pop_free_to_local (struct bpf_lru *lru, struct bpf_lru_locallist *loc_l) { struct bpf_lru_list *l = &lru->common_lru.lru_list; struct bpf_lru_node *node, *tmp_node; unsigned int nfree = 0; - raw_spin_lock(&l->lock); + if (!raw_spin_trylock(&l->lock)) + return false;Quoted 1 line
Could you provide some more analysis, and the effect this has on real-world programs? Presumably they'll unexpectedly encounter a lot more frequent
-ENOMEMas an error onbpf_map_update_elemeven though memory might be available just that locks are contended?
Quoted 2 lines
Also, have you considered rqspinlock as a potential candidate to discover deadlocks?
Thanks for the questions.
While I haven’t encountered this issue in production systems myself, the deadlock has been observed repeatedly in practice, including the cases shown in the cover letter. It can also be reproduced reliably when running the LRU tests locally, so this is a real and recurring problem.
I agree that returning -ENOMEM when locks are contended is not ideal. Using -EBUSY would better reflect the situation where memory is available but forward progress is temporarily blocked by lock contention. I can update the patch accordingly.
Regarding rqspinlock: as mentioned in the cover letter, Menglong previously explored using rqspinlock to address these deadlocks but was unable to arrive at a complete solution. After further off-list discussion, we agreed that using trylock is a more practical approach here. In most observed cases, the lock contention leading to deadlock occurs in bpf_common_lru_pop_free(), and trylock allows callers to back off safely rather than risking re-entrancy and deadlock.
Thanks,
Leon
Quoted 73 lines · Leon Hwang
Quoted 19 lines · Daniel Borkmann
Quoted 18 lines · Leon Hwang
Switch the free-node pop paths to raw_spin_trylock*() to avoid blocking on contended LRU locks.
If the global or per-CPU LRU lock is unavailable, refuse to refill the local free list and return NULL instead. This allows callers to back off safely rather than blocking or re-entering the same lock context.
This change avoids lockdep warnings and potential deadlocks caused by re-entrant LRU lock acquisition from NMI context, as shown below:
[ 418.260323] bpf_testmod: oh no, recursing into test_1, recursion_misses 1 [ 424.982207] ================================ [ 424.982216] WARNING: inconsistent lock state [ 424.982223] inconsistent {INITIAL USE} -> {IN-NMI} usage. [ 424.982314] *** DEADLOCK ***[...]
Quoted 7 lines
Quoted 4 lines
Signed-off-by Leon Hwang <[email protected]>--- kernel/bpf/bpf_lru_list.c | 17 ++++++++++------- 1 file changed, 10 insertions(+), 7 deletions(-)
Documentation/bpf/map_lru_hash_update.dotneeds update?Yes, it needs update.
Quoted 25 lines
Quoted 9 lines
kernel/bpf/bpf_lru_list.c +0
-0@@ -312,14 +312,15 @@ static void bpf_lru_list_push_free(struct bpf_lru_list *l,raw_spin_unlock_irqrestore (&l->lock, flags); } -static void bpf_lru_list_pop_free_to_local(struct bpf_lru *lru,kernel/bpf/bpf_lru_list.c static void bpf_lru_list_push_free(struct · line 325
Quoted 10 lines
kernel/bpf/bpf_lru_list.c +3
-0+static bool bpf_lru_list_pop_free_to_local (struct bpf_lru *lru,struct bpf_lru_locallist *loc_l) {struct bpf_lru_list *l = &lru->common_lru.lru_list;struct bpf_lru_node *node, *tmp_node;unsigned int nfree =0 ; -raw_spin_lock (&l->lock); +if (!raw_spin_trylock (&l->lock)) +return false;Could you provide some more analysis, and the effect this has on real-world programs? Presumably they'll unexpectedly encounter a lot more frequent
-ENOMEMas an error onbpf_map_update_elemeven though memory might be available just that locks are contended?Quoted 2 lines
Also, have you considered rqspinlock as a potential candidate to discover deadlocks?
Thanks for the questions.
While I haven’t encountered this issue in production systems myself, the deadlock has been observed repeatedly in practice, including the cases shown in the cover letter. It can also be reproduced reliably when running the LRU tests locally, so this is a real and recurring problem.
I agree that returning
-ENOMEMwhen locks are contended is not ideal. Using-EBUSYwould better reflect the situation where memory is available but forward progress is temporarily blocked by lock contention. I can update the patch accordingly.
Quoted 7 lines
Regarding rqspinlock: as mentioned in the cover letter, Menglong previously explored using rqspinlock to address these deadlocks but was unable to arrive at a complete solution. After further off-list discussion, we agreed that using trylock is a more practical approach here. In most observed cases, the lock contention leading to deadlock occurs in
bpf_common_lru_pop_free(), and trylock allows callers to back off safely rather than risking re-entrancy and deadlock.
Sorry, trylock is not an option here.
We are not going to sacrifice LRU map reliability for the sake of syzbot.
PATCH 3/3 selftests/bpf: Allow -ENOMEM on LRU map updates
In reply to Leon HwangLRU hash map updates may legitimately return -ENOMEM. Relax the percpu stats selftest to accept that error for LRU map types so it matches the map's expected behavior.
--- tools/testing/selftests/bpf/map_tests/map_percpu_stats.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-)
tools/testing/selftests/bpf/map_tests/map_percpu_stats.c +2 -1
@@ -188,7 +188,8 @@ static void *patch_map_thread(void *arg) 40, retry_for_nomem_fn); else ret =bpf_map_update_elem (opts->map_fd, &i, val_ptr,0 ); -CHECK (ret <0 ,"bpf_map_update_elem" ,"key=%d error: %s\n" , i,strerror (errno)); +CHECK (ret <0 && (!is_lru (opts->map_type) || ret != -ENOMEM ), +"bpf_map_update_elem" ,"key=%d error: %s\n" , i,strerror (errno));if (opts->map_type ==BPF_MAP_TYPE_HASH_OF_MAPS )close (val);
Signature · 1 line
2.52.0