Skip to contentSkip to conversation

bpf: Fix LRU NMI/tracepoint re-entry deadlock

PATCH Applied Mykyta Yatsenko 3 participants 6 messages Jun 7 – Jun 8

Subsystems (4)
lore
Share & tools
lore
#0 lore raw

v3 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 v3:
- Removed RFC tag
- Link to v2: https://patch.msgid.link/[email protected]

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]>
#1 lore raw

PATCH v3 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
index e7a2fc60523f..5ed7cb4b98c0 100644
@@ -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
index fe2661a58ea9..8d0ee61622af 100644
@@ -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_T
 
 enum 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
#2 lore raw

Re: [PATCH bpf-next v3 1/3] bpf: Fix NMI/tracepoint re-entry deadlock on lru locks

Quoted 32 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 (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.

Quoted 10 lines

Applied.
I couldn't believe that sashiko and claude didn't find anything. Even a small nit. I even went to read sashiko reasoning. The list of concerns was quite short. Maybe it's budgeting the tokens :) Anyway it looks good to a human too.

#3 lore raw

PATCH v3 2/3 Documentation/bpf: Refresh map_lru_hash_update.dot for rqspinlock

In reply to Mykyta Yatsenko

From: 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
index ab10058f5b79..412bc8b3b57e 100644
@@ -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
#4 lore raw

PATCH v3 3/3 selftests/bpf: Stress LRU rqspinlock recovery paths

In reply to Mykyta Yatsenko

From: 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
new file mode 100644
index 000000000000..60666a9ba41f
@@ -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
new file mode 100644
index 000000000000..c0692cd54237
@@ -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
#5 lore raw
In reply to Mykyta Yatsenko
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Hello:

This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Quoted 8 lines · On Sun, 07 Jun 2026 13:30:40 -0700 you wrote:

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.

[...]

Here is the summary with links:
- [bpf-next,v3,1/3] bpf: Fix NMI/tracepoint re-entry deadlock on lru locks

    https://git.kernel.org/bpf/bpf-next/c/89edbdfc5d03
  - [bpf-next,v3,2/3] Documentation/bpf: Refresh map_lru_hash_update.dot for rqspinlock
    https://git.kernel.org/bpf/bpf-next/c/8f6802d26d96
  - [bpf-next,v3,3/3] selftests/bpf: Stress LRU rqspinlock recovery paths
    https://git.kernel.org/bpf/bpf-next/c/6e1e4a9d60ed

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html