bpf: Fix LRU NMI/tracepoint re-entry deadlock
Subsystems (4)
v2 cover bpf: Fix LRU NMI/tracepoint re-entry deadlock
This series fixes AA-deadlocks where NMI and tracepoint BPF programs re-enter the per-CPU or global LRU lock already held on the same CPU (syzbot c69a0a2c816716f1e0d5, 18b26edb69b2e19f3b33).
Patch 1 converts every LRU lock site to rqspinlock_t and adds explicit recovery for some failures so no node leaks.
Patch 2 refreshes Documentation/bpf/map_lru_hash_update.dot to show the new rqspinlock failure exits and recovery routes.
Patch 3 introduces a stress test.
---
Changes in v2:
- Patch 1: __bpf_lru_node_move_in() now clears pending_free only when moving to the FREE list.
- Patch 3: address sashiko's feedback.
- Link to v1: https://patch.msgid.link/[email protected]
---
Mykyta Yatsenko (3):
bpf: Fix NMI/tracepoint re-entry deadlock on lru locks Documentation/bpf: Refresh map_lru_hash_update.dot for rqspinlock selftests/bpf: Stress LRU rqspinlock recovery paths
Documentation/bpf/map_lru_hash_update.dot | 44 +++- kernel/bpf/bpf_lru_list.c | 165 ++++++++------ kernel/bpf/bpf_lru_list.h | 25 ++- .../selftests/bpf/prog_tests/lru_lock_nmi.c | 243 +++++++++++++++++++++ tools/testing/selftests/bpf/progs/lru_lock_nmi.c | 33 +++ 5 files changed, 437 insertions(+), 73 deletions(-)
---
base-commit: 245da8192c073820390f7fa1cc1e834b32119bce
change-id: 20260519-lru_map_spin-8e20dabbf460
Best regards,
Signature · 1 line
Mykyta Yatsenko <[email protected]>
RFC PATCH v2 1/3 bpf: Fix NMI/tracepoint re-entry deadlock on lru locks
From: Mykyta Yatsenko <[email protected]>
NMI and tracepoint BPF programs can re-enter the per-CPU or global LRU lock that bpf_lru_pop_free()/push_free() already hold on the same CPU, AA-deadlocking. Lockdep reports "inconsistent {INITIAL USE} -> {IN-NMI}" on &l->lock (syzbot c69a0a2c816716f1e0d5) and "possible recursive locking detected" on &loc_l->lock (syzbot 18b26edb69b2e19f3b33).
Prior trylock and rqspinlock based fixes (see links) were nacked because compromised on reliability.
This patch converts every LRU lock site to rqspinlock_t and adds a recovery path for some failure windows to avoid node leaks.
Failure recovery:
- *_pop_free top-level: return NULL; prealloc_lru_pop() already treats that as no-free-element (-ENOMEM).
- Cross-CPU steal: skip the victim's locked loc_l, try next CPU.
- Post-steal local lock fail: publish stolen node to lockless per-CPU free_llist; next pop on this CPU picks it up.
- push_free fail: mark node pending_free=1. __local_list_flush(), __local_list_pop_pending() reclaim the node from pending_list. __bpf_lru_list_shrink_inactive() reclaims the node from inactive list. Nodes from active list are reclaimed by __bpf_lru_list_shrink() or after __bpf_lru_list_rotate_active() demotes it to the inactive.
--- kernel/bpf/bpf_lru_list.c | 165 ++++++++++++++++++++++++++++------------------ kernel/bpf/bpf_lru_list.h | 25 +++++-- 2 files changed, 119 insertions(+), 71 deletions(-)
kernel/bpf/bpf_lru_list.c +100 -65
@@ -13,23 +13,8 @@#define PERCPU_FREE_TARGET (4)#define PERCPU_NR_SCANS PERCPU_FREE_TARGET -/* Helpers to get the local list index */ -#define LOCAL_LIST_IDX (t) ((t) - BPF_LOCAL_LIST_T_OFFSET) -#define LOCAL_FREE_LIST_IDX LOCAL_LIST_IDX(BPF_LRU_LOCAL_LIST_T_FREE) -#define LOCAL_PENDING_LIST_IDX LOCAL_LIST_IDX(BPF_LRU_LOCAL_LIST_T_PENDING)#define IS_LOCAL_LIST_TYPE (t) ((t) >= BPF_LOCAL_LIST_T_OFFSET) -/* Local list helpers */ -static struct list_head *local_free_list (struct bpf_lru_locallist *loc_l) -{ -return &loc_l->lists[LOCAL_FREE_LIST_IDX ]; -} - -static struct list_head *local_pending_list (struct bpf_lru_locallist *loc_l) -{ -return &loc_l->lists[LOCAL_PENDING_LIST_IDX ]; -} -/* bpf_lru_node helpers */ static bool bpf_lru_node_is_ref (const struct bpf_lru_node *node) {
@@ -72,6 +57,7 @@ static void __bpf_lru_node_move_to_free(struct bpf_lru_list *l,bpf_lru_list_count_dec (l, node->type); node->type = tgt_free_type; +WRITE_ONCE (node->pending_free,0 );list_move (&node->list, free_list); }
@@ -87,6 +73,9 @@ static void __bpf_lru_node_move_in(struct bpf_lru_list *l,bpf_lru_list_count_inc (l, tgt_type); node->type = tgt_type;bpf_lru_node_clear_ref (node); +/* Reset pending_free only when moving to the free list */ +if (tgt_type ==BPF_LRU_LIST_T_FREE ) +WRITE_ONCE (node->pending_free,0 );list_move (&node->list, &l->lists[tgt_type]); }
@@ -212,9 +201,11 @@ __bpf_lru_list_shrink_inactive(struct bpf_lru *lru,unsigned int i =0 ;list_for_each_entry_safe_reverse (node, tmp_node, inactive, list) { -if (bpf_lru_node_is_ref (node)) { +if (bpf_lru_node_is_ref (node) && + !READ_ONCE (node->pending_free)) {__bpf_lru_node_move (l, node,BPF_LRU_LIST_T_ACTIVE ); - }else if (lru->del_from_htab (lru->del_arg, node)) { + }else if (READ_ONCE (node->pending_free) || + lru->del_from_htab (lru->del_arg, node)) {__bpf_lru_node_move_to_free (l, node, free_list, tgt_free_type);if (++nshrinked == tgt_nshrink)
@@ -273,7 +264,8 @@ static unsigned int __bpf_lru_list_shrink(struct bpf_lru *lru,list_for_each_entry_safe_reverse (node, tmp_node, force_shrink_list, list) { -if (lru->del_from_htab (lru->del_arg, node)) { +if (READ_ONCE (node->pending_free) || + lru->del_from_htab (lru->del_arg, node)) {__bpf_lru_node_move_to_free (l, node, free_list, tgt_free_type);return 1 ;
@@ -290,8 +282,10 @@ static void __local_list_flush(struct bpf_lru_list *l,struct bpf_lru_node *node, *tmp_node;list_for_each_entry_safe_reverse (node, tmp_node, -local_pending_list (loc_l), list) { -if (bpf_lru_node_is_ref (node)) + &loc_l->pending_list, list) { +if (READ_ONCE (node->pending_free)) +__bpf_lru_node_move_in (l, node,BPF_LRU_LIST_T_FREE ); +else if (bpf_lru_node_is_ref (node))__bpf_lru_node_move_in (l, node,BPF_LRU_LIST_T_ACTIVE );else __bpf_lru_node_move_in(l, node,
@@ -307,9 +301,12 @@ static void bpf_lru_list_push_free(struct bpf_lru_list *l,if (WARN_ON_ONCE (IS_LOCAL_LIST_TYPE (node->type)))return ; -raw_spin_lock_irqsave (&l->lock, flags); +if (raw_res_spin_lock_irqsave (&l->lock, flags)) { +WRITE_ONCE (node->pending_free,1 ); +return ; + }__bpf_lru_node_move (l, node,BPF_LRU_LIST_T_FREE ); -raw_spin_unlock_irqrestore (&l->lock, flags); +raw_res_spin_unlock_irqrestore (&l->lock, flags); } static void bpf_lru_list_pop_free_to_local(struct bpf_lru *lru,
@@ -318,8 +315,10 @@ static void bpf_lru_list_pop_free_to_local(struct bpf_lru *lru,struct bpf_lru_list *l = &lru->common_lru.lru_list;struct bpf_lru_node *node, *tmp_node;unsigned int nfree =0 ; +LIST_HEAD (tmp_free); -raw_spin_lock (&l->lock); +if (raw_res_spin_lock (&l->lock)) +return ;__local_list_flush (l, loc_l);
@@ -327,7 +326,7 @@ static void bpf_lru_list_pop_free_to_local(struct bpf_lru *lru,list_for_each_entry_safe (node, tmp_node, &l->lists[BPF_LRU_LIST_T_FREE ], list) { -__bpf_lru_node_move_to_free (l, node,local_free_list (loc_l), +__bpf_lru_node_move_to_free (l, node, &tmp_free,BPF_LRU_LOCAL_LIST_T_FREE );if (++nfree == lru->target_free)break ;
@@ -335,10 +334,19 @@ static void bpf_lru_list_pop_free_to_local(struct bpf_lru *lru,if (nfree < lru->target_free)__bpf_lru_list_shrink (lru, l, lru->target_free - nfree, -local_free_list (loc_l), + &tmp_free,BPF_LRU_LOCAL_LIST_T_FREE ); -raw_spin_unlock (&l->lock); +raw_res_spin_unlock (&l->lock); + +/* +* Transfer the harvested nodes from the temporary list_head into +* the lockless per-CPU free llist. +*/ +list_for_each_entry_safe (node, tmp_node, &tmp_free, list) { +list_del (&node->list); +llist_add (&node->llist, &loc_l->free_llist); + } } static void __local_list_add_pending(struct bpf_lru *lru,
@@ -350,22 +358,21 @@ static void __local_list_add_pending(struct bpf_lru *lru, *(u32 *)((void *)node + lru->hash_offset) = hash; node->cpu = cpu; node->type =BPF_LRU_LOCAL_LIST_T_PENDING ; +WRITE_ONCE (node->pending_free,0 );bpf_lru_node_clear_ref (node); -list_add (&node->list,local_pending_list (loc_l)); +list_add (&node->list, &loc_l->pending_list); }static struct bpf_lru_node *__local_list_pop_free (struct bpf_lru_locallist *loc_l) { -struct bpf_lru_node *node; +struct llist_node *llnode; - node =list_first_entry_or_null (local_free_list (loc_l), - struct bpf_lru_node, - list); -if (node) -list_del (&node->list); + llnode =llist_del_first (&loc_l->free_llist); +if (!llnode) +return NULL ; -return node; + return container_of(llnode, struct bpf_lru_node, llist); } static struct bpf_lru_node *
@@ -376,10 +383,10 @@ __local_list_pop_pending(struct bpf_lru *lru, struct bpf_lru_locallist *loc_l) ignore_ref:/* Get from the tail (i.e. older element) of the pending list. */ -list_for_each_entry_reverse (node,local_pending_list (loc_l), - list) { +list_for_each_entry_reverse (node, &loc_l->pending_list, list) {if ((!bpf_lru_node_is_ref (node) || force) && - lru->del_from_htab (lru->del_arg, node)) { + (READ_ONCE (node->pending_free) || + lru->del_from_htab (lru->del_arg, node))) {list_del (&node->list);return node; }
@@ -404,7 +411,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_res_spin_lock_irqsave (&l->lock, flags)) +return NULL ;__bpf_lru_list_rotate (lru, l);
@@ -420,7 +428,7 @@ static struct bpf_lru_node *bpf_percpu_lru_pop_free(struct bpf_lru *lru,__bpf_lru_node_move (l, node,BPF_LRU_LIST_T_INACTIVE ); } -raw_spin_unlock_irqrestore (&l->lock, flags); +raw_res_spin_unlock_irqrestore (&l->lock, flags);return node; }
@@ -437,7 +445,8 @@ 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_res_spin_lock_irqsave (&loc_l->lock, flags)) +return NULL ; node =__local_list_pop_free (loc_l);if (!node) {
@@ -448,17 +457,22 @@ static struct bpf_lru_node *bpf_common_lru_pop_free(struct bpf_lru *lru,if (node)__local_list_add_pending (lru, loc_l, cpu, node, hash); -raw_spin_unlock_irqrestore (&loc_l->lock, flags); +raw_res_spin_unlock_irqrestore (&loc_l->lock, flags);if (node)return node; -/* No free nodes found from the local free list and +/* +* No free nodes found from the local free list and * the global LRU list. * * Steal from the local free/pending list of the * current CPU and remote CPU in RR. It starts * with the loc_l->next_steal CPU. +* +* Acquire the victim's lock before touching either list. On +* acquisition failure (rqspinlock AA or timeout) skip the victim +* and try the next CPU. */ first_steal = loc_l->next_steal;
@@ -466,24 +480,36 @@ static struct bpf_lru_node *bpf_common_lru_pop_free(struct bpf_lru *lru,do { steal_loc_l =per_cpu_ptr (clru->local_list, steal); -raw_spin_lock_irqsave (&steal_loc_l->lock, flags); - - node =__local_list_pop_free (steal_loc_l); -if (!node) - node =__local_list_pop_pending (lru, steal_loc_l); - -raw_spin_unlock_irqrestore (&steal_loc_l->lock, flags); +if (!raw_res_spin_lock_irqsave (&steal_loc_l->lock, flags)) { + node =__local_list_pop_free (steal_loc_l); +if (!node) + node =__local_list_pop_pending (lru, steal_loc_l); +raw_res_spin_unlock_irqrestore (&steal_loc_l->lock, flags); + } steal =cpumask_next_wrap (steal, cpu_possible_mask); }while (!node && steal != first_steal); loc_l->next_steal = steal; -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); +if (!node) +return NULL ; + +if (raw_res_spin_lock_irqsave (&loc_l->lock, flags)) { +/* +* The local pending lock can't be acquired (rqspinlock AA +* or timeout). Return the stolen node to the per-CPU +* free_llist instead of orphaning it; the next pop_free on +* this CPU will pick it up. +*/ + node->type =BPF_LRU_LOCAL_LIST_T_FREE ; +bpf_lru_node_clear_ref (node); +WRITE_ONCE (node->pending_free,0 ); +llist_add (&node->llist, &loc_l->free_llist); +return NULL ; } +__local_list_add_pending (lru, loc_l, cpu, node, hash); +raw_res_spin_unlock_irqrestore (&loc_l->lock, flags);return node; }
@@ -511,18 +537,24 @@ static void bpf_common_lru_push_free(struct bpf_lru *lru, loc_l =per_cpu_ptr (lru->common_lru.local_list, node->cpu); -raw_spin_lock_irqsave (&loc_l->lock, flags); +if (raw_res_spin_lock_irqsave (&loc_l->lock, flags)) { +WRITE_ONCE (node->pending_free,1 ); +return ; + }if (unlikely (node->type !=BPF_LRU_LOCAL_LIST_T_PENDING )) { -raw_spin_unlock_irqrestore (&loc_l->lock, flags); +raw_res_spin_unlock_irqrestore (&loc_l->lock, + flags); goto check_lru_list; } node->type =BPF_LRU_LOCAL_LIST_T_FREE ;bpf_lru_node_clear_ref (node); -list_move (&node->list,local_free_list (loc_l)); +list_del (&node->list); + +raw_res_spin_unlock_irqrestore (&loc_l->lock, flags); -raw_spin_unlock_irqrestore (&loc_l->lock, flags); +llist_add (&node->llist, &loc_l->free_llist);return ; }
@@ -538,11 +570,14 @@ static void bpf_percpu_lru_push_free(struct bpf_lru *lru, l =per_cpu_ptr (lru->percpu_lru, node->cpu); -raw_spin_lock_irqsave (&l->lock, flags); +if (raw_res_spin_lock_irqsave (&l->lock, flags)) { +WRITE_ONCE (node->pending_free,1 ); +return ; + }__bpf_lru_node_move (l, node,BPF_LRU_LIST_T_FREE ); -raw_spin_unlock_irqrestore (&l->lock, flags); +raw_res_spin_unlock_irqrestore (&l->lock, flags); }void bpf_lru_push_free (struct bpf_lru *lru,struct bpf_lru_node *node)
@@ -565,6 +600,7 @@ static void bpf_common_lru_populate(struct bpf_lru *lru, void *buf, node = (struct bpf_lru_node *)(buf + node_offset); node->type =BPF_LRU_LIST_T_FREE ; + node->pending_free =0 ;bpf_lru_node_clear_ref (node);list_add (&node->list, &l->lists[BPF_LRU_LIST_T_FREE ]); buf += elem_size;
@@ -594,6 +630,7 @@ static void bpf_percpu_lru_populate(struct bpf_lru *lru, void *buf, node = (struct bpf_lru_node *)(buf + node_offset); node->cpu = cpu; node->type =BPF_LRU_LIST_T_FREE ; + node->pending_free =0 ;bpf_lru_node_clear_ref (node);list_add (&node->list, &l->lists[BPF_LRU_LIST_T_FREE ]); i++;
@@ -618,14 +655,12 @@ void bpf_lru_populate(struct bpf_lru *lru, void *buf, u32 node_offset,static void bpf_lru_locallist_init (struct bpf_lru_locallist *loc_l,int cpu) { -int i; - -for (i =0 ; i <NR_BPF_LRU_LOCAL_LIST_T ; i++) -INIT_LIST_HEAD (&loc_l->lists[i]); +INIT_LIST_HEAD (&loc_l->pending_list); +init_llist_head (&loc_l->free_llist); loc_l->next_steal = cpu; -raw_spin_lock_init (&loc_l->lock); +raw_res_spin_lock_init (&loc_l->lock); }static void bpf_lru_list_init (struct bpf_lru_list *l)
@@ -640,7 +675,7 @@ static void bpf_lru_list_init(struct bpf_lru_list *l) l->next_inactive_rotation = &l->lists[BPF_LRU_LIST_T_INACTIVE ]; -raw_spin_lock_init (&l->lock); +raw_res_spin_lock_init (&l->lock); } int bpf_lru_init(struct bpf_lru *lru, bool percpu, u32 hash_offset,
kernel/bpf/bpf_lru_list.h +19 -6
@@ -6,11 +6,11 @@#include <linux/cache.h> #include <linux/list.h> -#include <linux/spinlock_types.h> +#include <linux/llist.h> +#include <asm/rqspinlock.h> #define NR_BPF_LRU_LIST_T (3)#define NR_BPF_LRU_LIST_COUNT (2) -#define NR_BPF_LRU_LOCAL_LIST_T (2)#define BPF_LOCAL_LIST_T_OFFSET NR_BPF_LRU_LIST_Tenum bpf_lru_list_type {
@@ -22,10 +22,22 @@ enum bpf_lru_list_type { };struct bpf_lru_node { -struct list_head list; +/* +* A node is in at most one list at a time. The free path on the +* per-CPU locallist uses an llist, so share storage via a union. +*/ +union { +struct list_head list; +struct llist_node llist; + };u16 cpu;u8 type;u8 ref; +/* +* Marks nodes whose *_push_free() lock acquire failed; reclaimed +* by flush/shrink which honor the flag instead of del_from_htab(). +*/ +u8 pending_free; };struct bpf_lru_list {
@@ -34,13 +46,14 @@ struct bpf_lru_list {/* The next inactive list rotation starts from here */ struct list_head *next_inactive_rotation; -raw_spinlock_t lock____cacheline_aligned_in_smp ; +rqspinlock_t lock____cacheline_aligned_in_smp ; };struct bpf_lru_locallist { -struct list_head lists[NR_BPF_LRU_LOCAL_LIST_T ]; +struct list_head pending_list; +struct llist_head free_llist;u16 next_steal; -raw_spinlock_t lock; +rqspinlock_t lock; };struct bpf_common_lru {
Signature · 1 line
2.53.0-Meta
Re: [PATCH RFC bpf-next v2 1/3] bpf: Fix NMI/tracepoint re-entry deadlock on lru locks
Quoted 15 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
NMI and tracepoint BPF programs can re-enter the per-CPU or global LRU lock that bpf_lru_pop_free()/push_free() already hold on the same CPU, AA-deadlocking. Lockdep reports "inconsistent {INITIAL USE} -> {IN-NMI}" on
&l->lock(syzbotc69a0a2c816716f1e0d5) and "possible recursive locking detected" on&loc_l->lock(syzbot18b26edb69b2e19f3b33).Prior trylock and rqspinlock based fixes (see links) were nacked because compromised on reliability.
This patch converts every LRU lock site to
rqspinlock_tand adds a recovery path for some failure windows to avoid node leaks.
Quoted 6 lines
Failure recovery:
-
*_pop_freetop-level: return NULL;prealloc_lru_pop()already treats that as no-free-element (-ENOMEM).- Cross-CPU steal: skip the victim's locked
loc_l, try next CPU.
These two make sense.
Quoted 8 lines
- Post-steal local lock fail: publish stolen node to lockless per-CPU
free_llist; next pop on this CPU picks it up.-
push_freefail: mark node pending_free=1.__local_list_flush(),__local_list_pop_pending()reclaim the node frompending_list.__bpf_lru_list_shrink_inactive()reclaims the node from inactive list. Nodes from active list are reclaimed by__bpf_lru_list_shrink()or after__bpf_lru_list_rotate_active()demotes it to the inactive.
Here I'm getting lost. Feels like either mechanism free_llist or pending_free trick should do it.
I don't understand why both are necessary.
Overall it makes sense, but I looked at this lru logic long ago, so please repost without RFC and let AI find issues.
kernel/bpf/bpf_lru_list.c static void bpf_lru_list_pop_free_to_local(struct bpf_lru *lru, · line 321
Quoted 9 lines
kernel/bpf/bpf_lru_list.c +3
-1@@ -318,8 +315,10 @@ static void bpf_lru_list_pop_free_to_local(struct bpf_lru *lru,struct bpf_lru_list *l = &lru->common_lru.lru_list;struct bpf_lru_node *node, *tmp_node;unsigned int nfree =0 ; +LIST_HEAD (tmp_free); -raw_spin_lock (&l->lock); +if (raw_res_spin_lock (&l->lock)) +return ;
just return? I'm missing something.
Re: [PATCH RFC bpf-next v2 1/3] bpf: Fix NMI/tracepoint re-entry deadlock on lru locks
Quoted 34 lines · Alexei Starovoitov
Quoted 15 lines · Mykyta Yatsenko
From: Mykyta Yatsenko <[email protected]>
NMI and tracepoint BPF programs can re-enter the per-CPU or global LRU lock that bpf_lru_pop_free()/push_free() already hold on the same CPU, AA-deadlocking. Lockdep reports "inconsistent {INITIAL USE} -> {IN-NMI}" on
&l->lock(syzbotc69a0a2c816716f1e0d5) and "possible recursive locking detected" on&loc_l->lock(syzbot18b26edb69b2e19f3b33).Prior trylock and rqspinlock based fixes (see links) were nacked because compromised on reliability.
This patch converts every LRU lock site to
rqspinlock_tand adds a recovery path for some failure windows to avoid node leaks.Quoted 6 lines
Failure recovery:
-
*_pop_freetop-level: return NULL;prealloc_lru_pop()already treats that as no-free-element (-ENOMEM).- Cross-CPU steal: skip the victim's locked
loc_l, try next CPU.These two make sense.
Quoted 8 lines
- Post-steal local lock fail: publish stolen node to lockless per-CPU
free_llist; next pop on this CPU picks it up.-
push_freefail: mark node pending_free=1.__local_list_flush(),__local_list_pop_pending()reclaim the node frompending_list.__bpf_lru_list_shrink_inactive()reclaims the node from inactive list. Nodes from active list are reclaimed by__bpf_lru_list_shrink()or after__bpf_lru_list_rotate_active()demotes it to the inactive.
Quoted 4 lines
Here I'm getting lost. Feels like either mechanism
free_llistorpending_freetrick should do it.
I don't understand why both are necessary.
The free_llist change was introduced mainly for the steal path:
the node has been detached from the victim's list, but we can't attach it to our own pending list because reacquiring
our loc_l->lock failed. We stash it on the lockless free_llist - otherwise it'd leak.
pending_free is used when the node should be freed but we can't detach it (failed l->lock), so it's marked pending_free and other code paths do the deferred detach under the lock.
Quoted 9 lines
Overall it makes sense, but I looked at this lru logic long ago, so please repost without RFC and let AI find issues.
Quoted 6 lines
kernel/bpf/bpf_lru_list.c +1
-0@@ -318,8 +315,10 @@ static void bpf_lru_list_pop_free_to_local(struct bpf_lru *lru,struct bpf_lru_list *l = &lru->common_lru.lru_list;struct bpf_lru_node *node, *tmp_node;unsigned int nfree =0 ; +LIST_HEAD (tmp_free);
Quoted 6 lines
kernel/bpf/bpf_lru_list.c static void bpf_lru_list_pop_free_to_local(struct bpf_lru *lru, · line 321
Quoted 3 lines
kernel/bpf/bpf_lru_list.c +2
-1-raw_spin_lock (&l->lock); +if (raw_res_spin_lock (&l->lock)) +return ;just return? I'm missing something.
No nodes have been moved yet at this point, so failing the lock leaks nothing. The caller (bpf_common_lru_pop_free()) continues with __local_list_pop_free() (which should return NULL), and then falls through to the cross-CPU steal path.
RFC PATCH v2 2/3 Documentation/bpf: Refresh map_lru_hash_update.dot for rqspinlock
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Reflect the rqspinlock conversion and orphan-recovery paths added in the previous commit:
- All LRU locks are rqspinlock_t; any acquire can fail (AA or timeout). A shared "rqspinlock acquire failed" terminal collapses to the existing -ENOMEM exit. Dashed arrows from each acquire site mark the failure paths.
- The per-CPU local freelist is now lockless (free_llist).
- Post-steal: re-acquiring loc_l->lock to insert the stolen node into the local pending list can fail; on failure the node is published to free_llist instead of being orphaned, and the call returns -ENOMEM.
- Steal-loop victim lock failure is silent: skip the victim and try the next CPU.
--- Documentation/bpf/map_lru_hash_update.dot | 44 +++++++++++++++++++++++++++++-- 1 file changed, 42 insertions(+), 2 deletions(-)
Documentation/bpf/map_lru_hash_update.dot +42 -2
@@ -21,10 +21,18 @@ digraph { // names that initiate the corresponding logic in kernel/bpf/bpf_lru_list.c. // Number suffixes and errno suffixes handle subsections of the corresponding // logic in the function as of the writing of this dot. + // + // All LRU locks are rqspinlock_t. Every acquire can fail (AA self-deadlock + // or contention timeout); on failure the corresponding helper returns NULL + // and the caller propagates -ENOMEM. The "rqspinlock acquire failed" + // terminal below is reached via the dashed arrows from each acquire site. + + rqspinlock_failed [shape=rectangle, + label="Any LRU rqspinlock\nacquire fails\n(AA or timeout)"] // cf. __local_list_pop_free() / bpf_percpu_lru_pop_free() local_freelist_check [shape=diamond,fillcolor=1, - label="Local freelist\nnode available?"]; + label="Local freelist\nnode available?\n(lockless free_llist)"]; use_local_node [shape=rectangle, label="Use node owned\nby this CPU"]
@@ -82,6 +90,15 @@ digraph { // fn__local_list_pop_pending() } + // Post-steal: re-acquire local loc_l->lock to insert the stolen node into + // the local pending list. If the acquire fails, the stolen node is published + // to the lockless local free_llist so the next pop on this CPU picks it up + // instead of orphaning it. + post_steal_lock [shape=diamond,fillcolor=1, + label="Acquire local\nloc_l->lock\nto add pending"] + post_steal_to_free_llist [shape=rectangle, + label="Publish stolen node to\nlocal free_llist (lockless)"] + fn_bpf_lru_list_pop_free_to_local2 [shape=rectangle, label="Use node that was\nnot recently referenced"] local_freelist_check4 [shape=rectangle,
@@ -97,10 +114,19 @@ digraph { fn_htab_lru_map_update_elem_ENOENT [shape=oval,label="return -ENOENT"] begin -> local_freelist_check + // The initial per-CPU lock (loc_l->lock for common, l->lock for percpu) is + // acquired before the local freelist check; rqspinlock failure here exits + // directly to -ENOMEM (no recovery needed: nothing was removed yet). + local_freelist_check -> rqspinlock_failed [style=dashed, + xlabel="acquire fails"] local_freelist_check -> use_local_node [xlabel="Y"] local_freelist_check -> common_lru_check [xlabel="N"] common_lru_check -> fn_bpf_lru_list_pop_free_to_local [xlabel="Y"] common_lru_check -> fn___bpf_lru_list_shrink_inactive [xlabel="N"] + // Global lru_list lock acquire failure in pop_free_to_local: skip refill, + // fall through to the steal path. Not ENOMEM by itself. + fn_bpf_lru_list_pop_free_to_local -> common_lru_check2 [style=dashed, + xlabel="global lru_lock\nacquire fails"] fn_bpf_lru_list_pop_free_to_local -> fn___bpf_lru_node_move_to_free fn___bpf_lru_node_move_to_free -> fn_bpf_lru_list_pop_free_to_local2 [xlabel="Y"]
@@ -120,13 +146,27 @@ digraph { local_freelist_check6 -> local_freelist_check7 local_freelist_check7 -> fn_htab_lru_map_update_elem - fn_htab_lru_map_update_elem -> fn_htab_lru_map_update_elem3 [xlabel = "Y"] + // Steal-loop victim lock failure is silent: treat as "no node found here" + // and continue to next CPU; same edge as the existing "N" path. + local_freelist_check5 -> fn_htab_lru_map_update_elem2 [style=dashed, + xlabel="victim's lock\nfails: skip"] + // After a successful steal, re-acquire the local loc_l->lock. On failure + // the stolen node is published to free_llist (recovered, not orphaned) + // and the update returns -ENOMEM. + fn_htab_lru_map_update_elem -> post_steal_lock [xlabel = "Y"] + post_steal_lock -> fn_htab_lru_map_update_elem3 [xlabel = "OK"] + post_steal_lock -> post_steal_to_free_llist [style=dashed, + xlabel="loc_l->lock\nacquire fails"] + post_steal_to_free_llist -> fn_htab_lru_map_update_elem_ENOMEM fn_htab_lru_map_update_elem -> fn_htab_lru_map_update_elem2 [xlabel = "N"] fn_htab_lru_map_update_elem2 -> fn_htab_lru_map_update_elem_ENOMEM [xlabel = "Y"] fn_htab_lru_map_update_elem2 -> local_freelist_check5 [xlabel = "N"] fn_htab_lru_map_update_elem3 -> fn_htab_lru_map_update_elem4 + // Shared rqspinlock-failure terminal collapses to the same -ENOMEM exit. + rqspinlock_failed -> fn_htab_lru_map_update_elem_ENOMEM + use_local_node -> fn_htab_lru_map_update_elem4 fn_bpf_lru_list_pop_free_to_local2 -> fn_htab_lru_map_update_elem4 local_freelist_check4 -> fn_htab_lru_map_update_elem4
Signature · 1 line
2.53.0-Meta
RFC PATCH v2 3/3 selftests/bpf: Stress LRU rqspinlock recovery paths
In reply to Mykyta YatsenkoFrom: Mykyta Yatsenko <[email protected]>
Introduces stress test for bpf_lru_list that exercises lock-failures and orphan-recovery, added by the LRU rqspinlock conversion.
Runs three subtests: common LRU, per-CPU LRU lists (BPF_F_NO_COMMON_LRU), and per-CPU LRU map. Each pins one userspace hammer per CPU and attaches the perf_event NMI BPF prog (update+delete mix) on every online CPU. Pre-fix, lockdep fires the "INITIAL USE -> IN-NMI" splat during stress.
After stress test, drain_then_verify_capacity() drains every key and refills the lru map.
A stranded node on any CPU's pool would have forced eviction of a just-inserted key on that CPU, surfacing here as a missing lookup.
Marked serial_ because per-CPU pinning and high-rate HW perf events would perturb parallel tests.
--- .../selftests/bpf/prog_tests/lru_lock_nmi.c | 243 +++++++++++++++++++++ tools/testing/selftests/bpf/progs/lru_lock_nmi.c | 33 +++ 2 files changed, 276 insertions(+)
tools/testing/selftests/bpf/prog_tests/lru_lock_nmi.c new file +243 -0
@@ -0,0 +1,243 @@ +// SPDX-License-Identifier: GPL-2.0 +/* +* Stress every LRU lock-failure and orphan-recovery. +* perf_event NMI BPF on every online CPU does +* update+delete on a small LRU map; userspace threads on every CPU do +* the same from syscall context. +*/ +#define _GNU_SOURCE +#include <pthread.h> +#include <sched.h> +#include <sys/syscall.h> +#include <linux/perf_event.h> +#include <test_progs.h> +#include "testing_helpers.h" +#include "lru_lock_nmi.skel.h" + +#define MAP_ENTRIES 64 +#define KEY_RANGE (MAP_ENTRIES * 2) +#define STRESS_NS (500 * 1000 * 1000ULL) + +struct hammer_arg { +int map_fd; +int cpu; +__u64 deadline_ns; +}; + +struct refill_arg { +int map_fd; +int cpu; +int per_cpu_quota; +int update_errors; +}; + +/* +* Pin the calling thread to @cpu. Uses dynamically-allocated CPU sets so +* we stay correct on hosts with @cpu >= CPU_SETSIZE (default 1024). +*/ +static int pin_to_cpu (int cpu) +{ +cpu_set_t *cs; +size_t cs_size; +int err; + + cs =CPU_ALLOC (cpu +1 ); +if (!cs) +return -ENOMEM ; + cs_size =CPU_ALLOC_SIZE (cpu +1 ); + +CPU_ZERO_S (cs_size, cs); +CPU_SET_S (cpu, cs_size, cs); + err =pthread_setaffinity_np (pthread_self (), cs_size, cs); +CPU_FREE (cs); +return err; +} + +static void *hammer_thread (void *p) +{ +struct hammer_arg *a = p; +int nr_possible_cpus =libbpf_num_possible_cpus (); +__u64 val[nr_possible_cpus]; +unsigned int seed; +__u32 key; + +memset (val,0 ,sizeof (val)); +pin_to_cpu (a->cpu); + + seed = (unsigned int )a->cpu ^ (unsigned int )(uintptr_t )pthread_self (); + +while (get_time_ns () < a->deadline_ns) { +bool do_update =rand_r (&seed) &1 ; + + key =rand_r (&seed) %KEY_RANGE ; +if (do_update) +bpf_map_update_elem (a->map_fd, &key, val,BPF_ANY ); +else +bpf_map_delete_elem (a->map_fd, &key); + } +return NULL ; +} + +static void *refill_thread (void *p) +{ +struct refill_arg *a = p; +int nr_possible_cpus =libbpf_num_possible_cpus (); +__u64 val[nr_possible_cpus]; +__u32 start, end, key; + +memset (val,0 ,sizeof (val)); +pin_to_cpu (a->cpu); + + start = (__u32 )a->cpu * (__u32 )a->per_cpu_quota; + end = start + (__u32 )a->per_cpu_quota; +for (key = start; key < end; key++) +if (bpf_map_update_elem (a->map_fd, &key, val,BPF_ANY )) + a->update_errors++; +return NULL ; +} + +/* +* Drain the map, then refill it with each CPU inserting only its own +* quota of keys. +* After refill, lookup every key we inserted - a stranded node on any +* CPU's pool would have forced eviction. +*/ +static int drain_then_verify_capacity (int map_fd,int nr_cpus) +{ +int per_cpu_quota =MAP_ENTRIES / nr_cpus; +int total = per_cpu_quota * nr_cpus; +int nr_possible_cpus =libbpf_num_possible_cpus (); +pthread_t threads[nr_cpus]; +struct refill_arg args[nr_cpus]; +__u64 val[nr_possible_cpus]; +int i, hits =0 , nthreads =0 ; +__u32 key; + +memset (val,0 ,sizeof (val)); + +for (key =0 ; key <KEY_RANGE ; key++) +bpf_map_delete_elem (map_fd, &key); + +for (i =0 ; i < nr_cpus; i++) { + args[i] = (struct refill_arg ){ + .map_fd = map_fd, + .cpu = i, + .per_cpu_quota = per_cpu_quota, + }; +if (pthread_create (&threads[nthreads],NULL , refill_thread, &args[i]) ==0 ) + nthreads++; + } +for (i =0 ; i < nthreads; i++) +pthread_join (threads[i],NULL ); + +for (i =0 ; i < nr_cpus; i++) +if (args[i].update_errors) +return -ENOMEM ; + +for (key =0 ; key < (__u32 )total; key++) +if (bpf_map_lookup_elem (map_fd, &key, val) ==0 ) + hits++; + +return hits == total ?0 : -EIO ; +} + +static void run_variant (enum bpf_map_type type,__u32 map_flags,const char *name) +{ +struct perf_event_attr attr = { + .size =sizeof (attr), + .type =PERF_TYPE_HARDWARE , + .config =PERF_COUNT_HW_CPU_CYCLES , + .freq =1 , + }; +int nr_cpus, max_cpus =64 ; +struct bpf_link *links[max_cpus]; +pthread_t threads[max_cpus]; +struct hammer_arg args[max_cpus]; +struct lru_lock_nmi *skel =NULL ; +int map_fd, i, err, nr_threads =0 , pmu_fd =-1 ; +__u64 deadline; + + nr_cpus =libbpf_num_possible_cpus (); +if (!ASSERT_GT (nr_cpus,0 ,"num_cpus" )) +return ; + +if (nr_cpus > max_cpus) + nr_cpus = max_cpus; + +if (!test__start_subtest (name)) +return ; + +memset (links,0 ,sizeof (links)); + skel =lru_lock_nmi__open (); +if (!ASSERT_OK_PTR (skel,"skel_open" )) + goto cleanup; + + err =bpf_map__set_type (skel->maps.lru_map, type); +if (!ASSERT_OK (err,"set_type" )) + goto cleanup; + err =bpf_map__set_map_flags (skel->maps.lru_map, map_flags); +if (!ASSERT_OK (err,"set_flags" )) + goto cleanup; + err =bpf_map__set_max_entries (skel->maps.lru_map,MAP_ENTRIES ); +if (!ASSERT_OK (err,"set_max_entries" )) + goto cleanup; + + err =lru_lock_nmi__load (skel); +if (!ASSERT_OK (err,"skel_load" )) + goto cleanup; + + skel->bss->hits =0 ; + map_fd =bpf_map__fd (skel->maps.lru_map); + attr.sample_freq =read_perf_max_sample_freq (); + +for (i =0 ; i < nr_cpus; i++) { + pmu_fd =syscall (__NR_perf_event_open, &attr,-1 , i,-1 ,0 ); +if (pmu_fd <0 ) { +if (i ==0 && + (errno ==ENOENT || errno ==EOPNOTSUPP )) { +test__skip (); + goto cleanup; + } +continue ; + } +/* libbpf takes ownership of pfd on success */ + links[i] =bpf_program__attach_perf_event (skel->progs.oncpu, pmu_fd); +if (!links[i]) +close (pmu_fd); + } + + deadline =get_time_ns () +STRESS_NS ; +for (i =0 ; i < nr_cpus; i++) { + args[i].map_fd = map_fd; + args[i].cpu = i; + args[i].deadline_ns = deadline; +if (pthread_create (&threads[nr_threads],NULL , hammer_thread, &args[i]) ==0 ) + nr_threads++; + } +for (i =0 ; i < nr_threads; i++) +pthread_join (threads[i],NULL ); + +for (i =0 ; i < nr_cpus; i++) { +if (links[i]) { +bpf_link__destroy (links[i]); + links[i] =NULL ; + } + } + +ASSERT_GT (skel->bss->hits,0 ,"nmi_bpf_ran" ); +ASSERT_OK (drain_then_verify_capacity (map_fd, nr_cpus),"drain_then_verify_capacity" ); + +cleanup: +for (i =0 ; i < nr_cpus; i++) { +if (links[i]) +bpf_link__destroy (links[i]); + } +lru_lock_nmi__destroy (skel); +} + +void serial_test_lru_lock_nmi (void ) +{ +run_variant (BPF_MAP_TYPE_LRU_HASH ,0 ,"common_lru" ); +run_variant (BPF_MAP_TYPE_LRU_HASH ,BPF_F_NO_COMMON_LRU ,"no_common_lru" ); +run_variant (BPF_MAP_TYPE_LRU_PERCPU_HASH ,0 ,"percpu_lru" ); +}
tools/testing/selftests/bpf/progs/lru_lock_nmi.c new file +33 -0
@@ -0,0 +1,33 @@ +// SPDX-License-Identifier: GPL-2.0 +#include <vmlinux.h> +#include <bpf/bpf_helpers.h> + +struct { + __uint(type, BPF_MAP_TYPE_LRU_HASH); + __uint(max_entries, 64); + __type(key, __u32); + __type(value, __u64); +} lru_map SEC(".maps"); + +int hits; + +SEC("perf_event") +int oncpu (void *ctx) +{ +/* +* Key range deliberately wider than max_entries to force LRU +* eviction on every other update. +*/ +__u32 key =bpf_get_prandom_u32 () %128 ; +bool do_update =bpf_get_prandom_u32 () &1 ; +__u64 val =1 ; + +if (do_update) +bpf_map_update_elem (&lru_map, &key, &val,BPF_ANY ); +else +bpf_map_delete_elem (&lru_map, &key); +__sync_fetch_and_add (&hits,1 ); +return 0 ; +} + +char _license[] SEC("license") = "GPL";
Signature · 1 line
2.53.0-Meta