[PATCH 0/4] Lib fixes for 7.3

[PATCH 0/4] Lib fixes for 7.3

[Liam R. Howlett (Google)]

Two bugs found by an LLM review, and one problem Lorenzo Stoakes
reported off list.

An RCU reader that restarts after its node dies can dereference NULL if
the tree was emptied, or holds a single entry in the root pointer.
Patch 1 fixes it and patch 2 adds a test.

rhashtable can deadlock when an insert in atomic context grows the
table: the rehash may call vmalloc(), which takes locks that are not
safe against interrupts.  Patch 3 keeps non-blocking callers on
kmalloc() or a nested table.

With CONFIG_DEBUG_MAPLE_TREE, MT_WARN_ON() and the other WARN macros
print the tree and call dump_stack() rather than WARN(), so syzbot never
sees them.  Patch 4 makes them WARN once per call site, after the dump,
and makes the BUG macros BUG() after theirs.

Chris Mason (1):
  rhashtable: fix vmalloc() deadlock in atomic rehash

Liam R. Howlett (Google) (3):
  maple_tree: Fix rcu reader NULL dereference after the tree is emptied
  maple_tree: Test emptying tree while RCU reading
  maple_tree: Update internal warning and bug_on code

 include/linux/maple_tree.h |  54 +++++++++-------
 lib/maple_tree.c           | 110 +++++++++++++++++++++++--------
 lib/rhashtable.c           |  18 +++++-
 lib/test_maple_tree.c      | 129 +++++++++++++++++++++++++++++++++++++
 4 files changed, 257 insertions(+), 54 deletions(-)

-- 
2.47.3

[PATCH 1/4] maple_tree: Fix rcu reader NULL dereference after the tree is emptied

[Liam R. Howlett (Google)]

RCU readers may hit a NULL dereference if the tree is emptied while the
walker is restarted from a dead node.  Avoid the NULL dereference by
checking for an emptied/pointer tree (0->ptr, 1-ULONG_MAX -> NULL) and
set the maple state limits correctly.

Initial fix was generated by LLM and sent by Chris Mason in private.

Cc: <stable@vger.kernel.org>
Fixes: fff4a58cc00b ("maple_tree: introduce mas_next_slot() interface")
Reported-by: Chris Mason <mason@kernel.org>
Signed-off-by: Liam R. Howlett (Google) <liam@infradead.org>
---
 lib/maple_tree.c | 110 +++++++++++++++++++++++++++++++++++------------
 1 file changed, 83 insertions(+), 27 deletions(-)

diff --git a/lib/maple_tree.c b/lib/maple_tree.c
index 0b0036c9f8489..22812ed49be5a 100644
--- a/lib/maple_tree.c
+++ b/lib/maple_tree.c
@@ -3891,14 +3891,54 @@ static __always_inline void mas_rewalk(struct ma_state *mas, unsigned long index
 		goto retry;
 }
 
-static __always_inline bool mas_rewalk_if_dead(struct ma_state *mas,
-		struct maple_node *node, const unsigned long index)
+/*
+ * mas_next_no_node() - Finish a next walk that restarted into a tree without
+ * nodes.
+ * @mas: The inactive maple state (ma_none or ma_root)
+ *
+ * The arrival here is either because there is a root value or nothing.  Either
+ * way, the next entry is nothing.  So set the limits and overwrite the status.
+ *
+ * Return: NULL
+ */
+static inline void *mas_next_no_node(struct ma_state *mas)
 {
-	if (unlikely(ma_dead_node(node))) {
-		mas_rewalk(mas, index);
-		return true;
+	if (mas_is_ptr(mas))
+		mas->index = 1;
+	else
+		mas->index = 0;
+
+	mas->last = ULONG_MAX;
+	mas->status = ma_none;
+	return NULL;
+}
+
+/*
+ * mas_prev_no_node() - Finish a prev walk that restarted into a tree without
+ * nodes.
+ * @mas: The inactive maple state (ma_none or ma_root)
+ * @min: The lowest index to return
+ *
+ * The arrival here is either because there is a root value or nothing.  With
+ * nothing, leave the limits mas_walk() sets for an empty tree.  A root value
+ * sits at 0, before the saved index: stop on it as mas_prev_setup() does.
+ *
+ * Return: The root entry if @min allows it, NULL otherwise.  A node if the
+ * root changed again since the walk; the caller restarts.
+ */
+static inline void *mas_prev_no_node(struct ma_state *mas, unsigned long min)
+{
+	mas->index = 0;
+	if (mas_is_none(mas)) {
+		mas->last = ULONG_MAX;
+		return NULL;
 	}
-	return false;
+
+	mas->last = 0;
+	if (min)
+		return NULL;
+
+	return mas_root(mas);
 }
 
 /*
@@ -4006,14 +4046,14 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty)
 	node = mas_mn(mas);
 	type = mte_node_type(mas->node);
 	pivots = ma_pivots(node, type);
-	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
-		goto retry;
+	if (unlikely(ma_dead_node(node)))
+		goto dead;
 
 	if (mas->min <= min) {
 		pivot = mas_safe_min(mas, pivots, mas->offset);
 
-		if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
-			goto retry;
+		if (unlikely(ma_dead_node(node)))
+			goto dead;
 
 		if (pivot <= min)
 			goto underflow;
@@ -4028,10 +4068,8 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty)
 		if (mas->index <= min)
 			goto underflow;
 
-		if (mas_prev_node(mas, min)) {
-			mas_rewalk(mas, save_point);
-			goto retry;
-		}
+		if (mas_prev_node(mas, min))
+			goto dead;
 
 		if (WARN_ON_ONCE(mas_is_underflow(mas)))
 			return NULL;
@@ -4045,8 +4083,8 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty)
 
 	slots = ma_slots(node, type);
 	entry = mas_slot(mas, slots, mas->offset);
-	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
-		goto retry;
+	if (unlikely(ma_dead_node(node)))
+		goto dead;
 
 	if (likely(entry))
 		return entry;
@@ -4063,6 +4101,17 @@ static void *mas_prev_slot(struct ma_state *mas, unsigned long min, bool empty)
 underflow:
 	mas->status = ma_underflow;
 	return NULL;
+
+dead:
+	mas_rewalk(mas, save_point);
+	if (likely(mas_is_active(mas)))
+		goto retry;
+
+	entry = mas_prev_no_node(mas, min);
+	if (unlikely(xa_is_node(entry))) /* The root changed again */
+		goto dead;
+
+	return entry;
 }
 
 /*
@@ -4176,8 +4225,8 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty)
 	node = mas_mn(mas);
 	type = mte_node_type(mas->node);
 	pivots = ma_pivots(node, type);
-	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
-		goto retry;
+	if (unlikely(ma_dead_node(node)))
+		goto dead;
 
 	if (mas->max >= max) {
 		if (likely(mas->offset < mas->end))
@@ -4185,8 +4234,8 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty)
 		else
 			pivot = mas->max;
 
-		if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
-			goto retry;
+		if (unlikely(ma_dead_node(node)))
+			goto dead;
 
 		if (pivot >= max) { /* Was at the limit, next will extend beyond */
 			mas->status = ma_overflow;
@@ -4208,10 +4257,8 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty)
 			return NULL;
 		}
 
-		if (mas_next_node(mas, node, max)) {
-			mas_rewalk(mas, save_point);
-			goto retry;
-		}
+		if (mas_next_node(mas, node, max))
+			goto dead;
 
 		if (WARN_ON_ONCE(mas_is_overflow(mas)))
 			return NULL;
@@ -4226,8 +4273,8 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty)
 
 	slots = ma_slots(node, type);
 	entry = mt_slot(mas->tree, slots, mas->offset);
-	if (unlikely(mas_rewalk_if_dead(mas, node, save_point)))
-		goto retry;
+	if (unlikely(ma_dead_node(node)))
+		goto dead;
 
 	if (entry)
 		return entry;
@@ -4244,6 +4291,13 @@ static void *mas_next_slot(struct ma_state *mas, unsigned long max, bool empty)
 	}
 
 	return entry;
+
+dead:
+	mas_rewalk(mas, save_point);
+	if (likely(mas_is_active(mas)))
+		goto retry;
+
+	return mas_next_no_node(mas);
 }
 
 /*
@@ -5450,7 +5504,9 @@ void *mas_find(struct ma_state *mas, unsigned long max)
 	/* Retries on dead nodes handled by mas_next_slot */
 	entry = mas_next_slot(mas, max, false);
 	/* Ignore overflow */
-	mas->status = ma_active;
+	if (mas_is_overflow(mas))
+		mas->status = ma_active;
+
 	return entry;
 }
 EXPORT_SYMBOL_GPL(mas_find);
-- 
2.47.3

[PATCH 2/4] maple_tree: Test emptying tree while RCU reading

[Liam R. Howlett (Google)]

Add a test case for the rcu reader being restarted by emptying the tree.

Signed-off-by: Liam R. Howlett (Google) <liam@infradead.org>
---
 lib/test_maple_tree.c | 129 ++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 129 insertions(+)

diff --git a/lib/test_maple_tree.c b/lib/test_maple_tree.c
index fb40e193a3cb7..894f5893e1be2 100644
--- a/lib/test_maple_tree.c
+++ b/lib/test_maple_tree.c
@@ -3740,6 +3740,134 @@ static noinline void __init check_range64_in_rcu(struct maple_tree *mt)
 	rcu_barrier();
 }
 
+/*
+ * A reader that restarts after its leaf died may find a tree without nodes:
+ * emptied, or emptied and then given a single entry at 0.  Each case starts
+ * from a tree with nodes, built by check_seq().  The stores run while the
+ * reader holds rcu_read_lock, so they use GFP_ATOMIC.
+ */
+static noinline void __init check_restart_no_node(struct maple_tree *mt)
+{
+	void *ptr = xa_mk_value(1234);
+	void *entry;
+	MA_STATE(mas, mt, 0, 0);
+
+	MT_BUG_ON(mt, !mtree_empty(mt));
+	mt_set_non_kernel(99999);
+
+	/* find: the tree is emptied */
+	mt_init_flags(mt, MT_FLAGS_USE_RCU);
+	check_seq(mt, 100, false);
+	rcu_read_lock();
+	mas_set(&mas, 0);
+	entry = mas_find(&mas, ULONG_MAX);
+	MT_BUG_ON(mt, entry != xa_mk_value(0));
+	MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC));
+	entry = mas_find(&mas, ULONG_MAX);
+	MT_BUG_ON(mt, entry != NULL);
+	MT_BUG_ON(mt, mas.status != ma_none);
+	MT_BUG_ON(mt, mas.index != 0);
+	MT_BUG_ON(mt, mas.last != ULONG_MAX);
+	entry = mas_find(&mas, ULONG_MAX);
+	MT_BUG_ON(mt, entry != NULL);
+	MT_BUG_ON(mt, mas.status != ma_none);
+	rcu_read_unlock();
+	mtree_destroy(mt);
+	rcu_barrier();
+
+	/* next: the tree is emptied */
+	mt_init_flags(mt, MT_FLAGS_USE_RCU);
+	check_seq(mt, 100, false);
+	rcu_read_lock();
+	mas_set(&mas, 0);
+	entry = mas_find(&mas, ULONG_MAX);
+	MT_BUG_ON(mt, entry != xa_mk_value(0));
+	MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC));
+	entry = mas_next(&mas, ULONG_MAX);
+	MT_BUG_ON(mt, entry != NULL);
+	MT_BUG_ON(mt, mas.status != ma_none);
+	MT_BUG_ON(mt, mas.index != 0);
+	MT_BUG_ON(mt, mas.last != ULONG_MAX);
+	rcu_read_unlock();
+	mtree_destroy(mt);
+	rcu_barrier();
+
+	/* find: the tree is emptied, then holds one entry at 0 */
+	mt_init_flags(mt, MT_FLAGS_USE_RCU);
+	check_seq(mt, 100, false);
+	rcu_read_lock();
+	mas_set(&mas, 0);
+	entry = mas_find(&mas, ULONG_MAX);
+	MT_BUG_ON(mt, entry != xa_mk_value(0));
+	MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC));
+	MT_BUG_ON(mt, mtree_store(mt, 0, ptr, GFP_ATOMIC));
+	entry = mas_find(&mas, ULONG_MAX);
+	MT_BUG_ON(mt, entry != NULL);
+	MT_BUG_ON(mt, mas.status != ma_none);
+	MT_BUG_ON(mt, mas.index != 1);
+	MT_BUG_ON(mt, mas.last != ULONG_MAX);
+	rcu_read_unlock();
+	mtree_destroy(mt);
+	rcu_barrier();
+
+	/* find_rev: the tree is emptied */
+	mt_init_flags(mt, MT_FLAGS_USE_RCU);
+	check_seq(mt, 100, false);
+	rcu_read_lock();
+	mas_set(&mas, ULONG_MAX);
+	entry = mas_find_rev(&mas, 0);
+	MT_BUG_ON(mt, entry != xa_mk_value(100));
+	MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC));
+	entry = mas_find_rev(&mas, 0);
+	MT_BUG_ON(mt, entry != NULL);
+	MT_BUG_ON(mt, mas.status != ma_none);
+	MT_BUG_ON(mt, mas.index != 0);
+	MT_BUG_ON(mt, mas.last != ULONG_MAX);
+	entry = mas_find_rev(&mas, 0);
+	MT_BUG_ON(mt, entry != NULL);
+	MT_BUG_ON(mt, mas.status != ma_none);
+	rcu_read_unlock();
+	mtree_destroy(mt);
+	rcu_barrier();
+
+	/* prev: the tree is emptied, then holds one entry at 0 */
+	mt_init_flags(mt, MT_FLAGS_USE_RCU);
+	check_seq(mt, 100, false);
+	rcu_read_lock();
+	mas_set(&mas, ULONG_MAX);
+	entry = mas_find_rev(&mas, 0);
+	MT_BUG_ON(mt, entry != xa_mk_value(100));
+	MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC));
+	MT_BUG_ON(mt, mtree_store(mt, 0, ptr, GFP_ATOMIC));
+	entry = mas_prev(&mas, 0);
+	MT_BUG_ON(mt, entry != ptr);
+	MT_BUG_ON(mt, mas.status != ma_root);
+	MT_BUG_ON(mt, mas.index != 0);
+	MT_BUG_ON(mt, mas.last != 0);
+	rcu_read_unlock();
+	mtree_destroy(mt);
+	rcu_barrier();
+
+	/* find_rev: the entry at 0 is below the minimum */
+	mt_init_flags(mt, MT_FLAGS_USE_RCU);
+	check_seq(mt, 100, false);
+	rcu_read_lock();
+	mas_set(&mas, ULONG_MAX);
+	entry = mas_find_rev(&mas, 1);
+	MT_BUG_ON(mt, entry != xa_mk_value(100));
+	MT_BUG_ON(mt, mtree_store_range(mt, 0, ULONG_MAX, NULL, GFP_ATOMIC));
+	MT_BUG_ON(mt, mtree_store(mt, 0, ptr, GFP_ATOMIC));
+	entry = mas_find_rev(&mas, 1);
+	MT_BUG_ON(mt, entry != NULL);
+	MT_BUG_ON(mt, mas.status != ma_root);
+	MT_BUG_ON(mt, mas.index != 0);
+	MT_BUG_ON(mt, mas.last != 0);
+	rcu_read_unlock();
+	mtree_destroy(mt);
+	rcu_barrier();
+	mt_set_non_kernel(0);
+}
+
 static DEFINE_MTREE(tree);
 static int __init maple_tree_seed(void)
 {
@@ -4031,6 +4159,7 @@ static int __init maple_tree_seed(void)
 
 	check_range64_in_rcu(&tree);
 
+	check_restart_no_node(&tree);
 
 #if defined(BENCH)
 skip:
-- 
2.47.3

[PATCH 3/4] maple_tree: Update internal warning and bug_on code

[Liam R. Howlett (Google)]

When CONFIG_DEBUG_MAPLE_TREE is set, call the WARN_ON_ONCE() after the
custom information is dumped about the tree.  Without using the kernel's
WARN_ON calls, syzbot will not catch issues detected by this code.

Update the non-debug code to call WARN_ON_ONCE() as well.

Cc: <stable@vger.kernel.org>
Reported-by: Lorenzo Stoakes <ljs@kernel.org>
Fixes: bf857ddd21d0b ("maple_tree: move debug check to __mas_set_range()")
Signed-off-by: Liam R. Howlett (Google) <liam@infradead.org>
---
 include/linux/maple_tree.h | 54 +++++++++++++++++++++-----------------
 1 file changed, 30 insertions(+), 24 deletions(-)

diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
index e30e57f5f3df9..0f96f1f19eb95 100644
--- a/include/linux/maple_tree.h
+++ b/include/linux/maple_tree.h
@@ -680,7 +680,7 @@ void mt_cache_shrink(void);
 		pr_info("Pass: %u Run:%u\n",				\
 			atomic_read(&maple_tree_tests_passed),		\
 			atomic_read(&maple_tree_tests_run));		\
-		dump_stack();						\
+		BUG_ON(1);						\
 	} else {							\
 		atomic_inc(&maple_tree_tests_passed);			\
 	}								\
@@ -696,7 +696,7 @@ void mt_cache_shrink(void);
 		pr_info("Pass: %u Run:%u\n",				\
 			atomic_read(&maple_tree_tests_passed),		\
 			atomic_read(&maple_tree_tests_run));		\
-		dump_stack();						\
+		BUG_ON(1);						\
 	} else {							\
 		atomic_inc(&maple_tree_tests_passed);			\
 	}								\
@@ -713,62 +713,68 @@ void mt_cache_shrink(void);
 		pr_info("Pass: %u Run:%u\n",				\
 			atomic_read(&maple_tree_tests_passed),		\
 			atomic_read(&maple_tree_tests_run));		\
-		dump_stack();						\
+		BUG_ON(1);						\
 	} else {							\
 		atomic_inc(&maple_tree_tests_passed);			\
 	}								\
 } while (0)
 
 #define MT_WARN_ON(__tree, __x)  ({					\
+	static bool __warned;						\
 	int ret = !!(__x);						\
 	atomic_inc(&maple_tree_tests_run);				\
-	if (ret) {							\
-		pr_info("WARN at %s:%d (%u)\n",				\
-		__func__, __LINE__, __x);				\
+	if (!ret) {							\
+		atomic_inc(&maple_tree_tests_passed);			\
+	} else if (!__warned) {						\
+		__warned = true;					\
+		pr_info("WARN at %s:%d\n",				\
+		__func__, __LINE__);					\
 		mt_dump(__tree, mt_dump_hex);				\
 		pr_info("Pass: %u Run:%u\n",				\
 			atomic_read(&maple_tree_tests_passed),		\
 			atomic_read(&maple_tree_tests_run));		\
-		dump_stack();						\
-	} else {							\
-		atomic_inc(&maple_tree_tests_passed);			\
+		WARN_ON(1);						\
 	}								\
 	unlikely(ret);							\
 })
 
 #define MAS_WARN_ON(__mas, __x) ({					\
+	static bool __warned;						\
 	int ret = !!(__x);						\
 	atomic_inc(&maple_tree_tests_run);				\
-	if (ret) {							\
-		pr_info("WARN at %s:%d (%u)\n",				\
-		__func__, __LINE__, __x);				\
+	if (!ret) {							\
+		atomic_inc(&maple_tree_tests_passed);			\
+	} else if (!__warned) {						\
+		__warned = true;					\
+		pr_info("WARN at %s:%d\n",				\
+		__func__, __LINE__);					\
 		mas_dump(__mas);					\
 		mt_dump((__mas)->tree, mt_dump_hex);			\
 		pr_info("Pass: %u Run:%u\n",				\
 			atomic_read(&maple_tree_tests_passed),		\
 			atomic_read(&maple_tree_tests_run));		\
-		dump_stack();						\
-	} else {							\
-		atomic_inc(&maple_tree_tests_passed);			\
+		WARN_ON(1);						\
 	}								\
 	unlikely(ret);							\
 })
 
 #define MAS_WR_WARN_ON(__wrmas, __x) ({					\
+	static bool __warned;						\
 	int ret = !!(__x);						\
 	atomic_inc(&maple_tree_tests_run);				\
-	if (ret) {							\
-		pr_info("WARN at %s:%d (%u)\n",				\
-		__func__, __LINE__, __x);				\
+	if (!ret) {							\
+		atomic_inc(&maple_tree_tests_passed);			\
+	} else if (!__warned) {						\
+		__warned = true;					\
+		pr_info("WARN at %s:%d\n",				\
+		__func__, __LINE__);					\
 		mas_wr_dump(__wrmas);					\
 		mas_dump((__wrmas)->mas);				\
 		mt_dump((__wrmas)->mas->tree, mt_dump_hex);		\
 		pr_info("Pass: %u Run:%u\n",				\
 			atomic_read(&maple_tree_tests_passed),		\
 			atomic_read(&maple_tree_tests_run));		\
-		dump_stack();						\
-	} else {							\
-		atomic_inc(&maple_tree_tests_passed);			\
+		WARN_ON(1);						\
 	}								\
 	unlikely(ret);							\
 })
@@ -776,9 +782,9 @@ void mt_cache_shrink(void);
 #define MT_BUG_ON(__tree, __x)		BUG_ON(__x)
 #define MAS_BUG_ON(__mas, __x)		BUG_ON(__x)
 #define MAS_WR_BUG_ON(__mas, __x)	BUG_ON(__x)
-#define MT_WARN_ON(__tree, __x)		WARN_ON(__x)
-#define MAS_WARN_ON(__mas, __x)		WARN_ON(__x)
-#define MAS_WR_WARN_ON(__mas, __x)	WARN_ON(__x)
+#define MT_WARN_ON(__tree, __x)		WARN_ON_ONCE(__x)
+#define MAS_WARN_ON(__mas, __x)		WARN_ON_ONCE(__x)
+#define MAS_WR_WARN_ON(__mas, __x)	WARN_ON_ONCE(__x)
 #endif /* CONFIG_DEBUG_MAPLE_TREE */
 
 /**
-- 
2.47.3

[PATCH 4/4] rhashtable: fix vmalloc() deadlock in atomic rehash

[Liam R. Howlett (Google)]

From: Chris Mason <mason@kernel.org>

An unprivileged user can deadlock two CPUs by filling the forwarding
database (FDB) of a bridge in their own network namespace. A peer that
floods a bridge port with frames from new source addresses can fill the
FDB too. The flood alone was never seen to cause a deadlock. Together
with local tasks that call vmalloc() in a loop on the CPU that receives
the frames, it can deadlock that CPU. Other CPUs that call vmalloc() or
vfree() after that can hang too.

The FDB holds the MAC addresses that the bridge knows. It is an
rhashtable, a hash table that grows as it fills.

An rhashtable normally grows from a worker. If an insert finds the table
too full before the worker has run, rhashtable_insert_rehash() allocates
the larger table immediately, with GFP_ATOMIC, in the context of the
insert. bucket_table_alloc() uses kvmalloc() for that.

kvmalloc() tries kmalloc() first. Since v6.19, if kmalloc() fails, it
falls back to vmalloc() for non-blocking GFP flags too, and kmalloc()
always fails above KMALLOC_MAX_SIZE.

vmalloc() and vfree() take their spinlocks with bottom halves enabled.
Such a lock must not be taken in a softirq, or while holding a lock that
a softirq takes. In the bridge, an insert that falls back to vmalloc()
breaks the second rule: the bridge inserts into its FDB under
br->hash_lock, and its receive softirq takes br->hash_lock as well.

Below, one CPU adds an FDB entry for an RTM_NEWNEIGH netlink request,
while another CPU is inside vmalloc() or vfree():

    RTM_NEWNEIGH                      vmalloc() or vfree()
    ============                      ====================
    spin_lock_bh(&br->hash_lock)
                                      spin_lock(&vn->busy.lock)
    rhashtable_insert_rehash()
      kvmalloc(GFP_ATOMIC)
        vmalloc()
          spin_lock(&vn->busy.lock)
            waits for the other CPU
                                      softirq: a frame for the bridge
                                        spin_lock(&br->hash_lock)
                                          waits for RTM_NEWNEIGH

The receive softirq also inserts into the FDB itself: on a learning
port, br_fdb_update() adds the source address of a frame if the FDB does
not have it yet. If that insert falls back to vmalloc(), it breaks the
first rule. The CPU then deadlocks with itself if the softirq has
interrupted a task that holds the same vmalloc lock.

Reproduced on x86-64 under emulation, with three things going on at the
same time:

- RTM_NEWNEIGH requests filled an FDB past 262,144 entries, where the
  next table is too large for kmalloc() on x86-64.
- Frames arrived on a veth port.
- Tasks called vmalloc() in a loop.

Two CPUs ended up spinning on each other's lock.

The softirq path was reproduced too, on x86-64 under emulation and with
RPS set by root. Repeated floods of 280,000 source addresses on a veth
port, while tasks called vmalloc() in a loop on the CPU that received
the frames, ended in a soft lockup in alloc_vmap_area() in 6 of 6 boots.
Without these tasks, on a kernel with no debug options, none of 33
floods reached vmalloc().

Fix this by calling kmalloc() instead of kvmalloc() in
bucket_table_alloc() if the GFP flags do not allow blocking.

Known gaps:
- By code inspection, bpf_iter_tcp_realloc_batch() and the dm-bufio
  clients that set no_sleep also call a non-blocking vmalloc() under
  spin_lock_bh(), and can still deadlock in the same way. The later
  commit "mm/vmalloc: fix deadlock in softirq and BH-off callers" fixes
  them.
- If kmalloc() fails, the atomic rehash falls back to a nested table, as
  before v6.19. A nested table is built from single pages, so it needs
  no large allocation. An insert then fails in two cases. If the nested
  table cannot get a page, the insert fails with -ENOMEM or -EBUSY. If
  the new table has 512 buckets, that is too few for a nested table, and
  the insert fails with -ENOMEM.
- A lookup in a nested table follows up to three more pointers until the
  worker has rehashed once more.

Changes from the LLM patch:

Dropped the __GFP_NOWARN from the kmalloc_noprof() when
gfpflags_allow_blocking() is false since the only non-blocking caller
already sets the flag.

Tried to make the alloc_hooks_tag() multi-line call more readable
(whitespace changes only).

Cc: <stable@vger.kernel.org>
Fixes: c6307674ed82 ("mm: kvmalloc: add non-blocking support for vmalloc")
Assisted-by: LLM
Signed-off-by: Chris Mason <mason@kernel.org>
Signed-off-by: David Hildenbrand (Arm) <david@kernel.org>
Signed-off-by: Liam R. Howlett (Google) <liam@infradead.org>
---
 lib/rhashtable.c | 18 +++++++++++++++---
 1 file changed, 15 insertions(+), 3 deletions(-)

diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 6362896e4f099..f8ec85bc6e8af 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -193,9 +193,21 @@ static struct bucket_table *bucket_table_alloc(struct rhashtable *ht,
 	int i;
 	static struct lock_class_key __key;
 
-	tbl = alloc_hooks_tag(ht->alloc_tag,
-			kvmalloc_node_align_noprof(struct_size(tbl, buckets, nbuckets),
-					     1, gfp|__GFP_ZERO, NUMA_NO_NODE));
+	/*
+	 * vmalloc() takes locks that are not safe against interrupts, and the
+	 * emergency rehash runs in whatever context the insert runs in. So a
+	 * caller that cannot block gets slab memory, or else a nested table.
+	 */
+	if (gfpflags_allow_blocking(gfp))
+		tbl = alloc_hooks_tag(ht->alloc_tag,
+				      kvmalloc_node_align_noprof(
+					struct_size(tbl, buckets, nbuckets),
+					1, gfp | __GFP_ZERO, NUMA_NO_NODE));
+	else
+		tbl = alloc_hooks_tag(ht->alloc_tag,
+				      kmalloc_noprof(
+					struct_size(tbl, buckets, nbuckets),
+					gfp | __GFP_ZERO));
 
 	size = nbuckets;
 
-- 
2.47.3

Re: [PATCH 3/4] maple_tree: Update internal warning and bug_on code

[Lorenzo Stoakes (ARM)]

ma
 On Wed, Oct 28, 2026 at 11:42:17AM -0400, Liam R. Howlett (Google) wrote:
> When CONFIG_DEBUG_MAPLE_TREE is set, call the WARN_ON_ONCE() after the
> custom information is dumped about the tree.  Without using the kernel's
> WARN_ON calls, syzbot will not catch issues detected by this code.

Mega nit but commit message doesn't mention the BUG_ON() bits :)

>
> Update the non-debug code to call WARN_ON_ONCE() as well.
>
> Cc: <stable@vger.kernel.org>
> Reported-by: Lorenzo Stoakes <ljs@kernel.org>
> Fixes: bf857ddd21d0b ("maple_tree: move debug check to __mas_set_range()")

LLM overlord says bf857ddd21d0b only moved it, and f0a1f866aba1 actually
implemented it.

> Signed-off-by: Liam R. Howlett (Google) <liam@infradead.org>

Looks sensible to me from kernel perspective, but LLM overlord tells me this
changes the userland tests from asserting on dump_stack() to just printing
something out on WARN_ON().

(BUG_ON() is OK, it asserts already).

However we really do need this for the kernel so CONFIG_DEBUG_MAPLE_TREE
triggers syzbot and such, so maybe the userland bit can be a follow-up?

On that basis:

Reviewed-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>

Or... maybe just respin with something actually, can fix it by updating the
shared maple tree testing header to make warn do something like this
(schlopped, apologies):

diff --git a/tools/testing/shared/maple-shared.h b/tools/testing/shared/maple-shared.h
index 2a1e9a8594a2..112052e7201f 100644
--- a/tools/testing/shared/maple-shared.h
+++ b/tools/testing/shared/maple-shared.h
@@ -10,6 +10,30 @@
 #include <time.h>
 #include "linux/init.h"

+/*
+ * The tools/include/asm/bug.h WARN*() family only prints a message and
+ * carries on.  Nothing in the maple tree or VMA tests expects a warning, so
+ * treat one as a failure and abort at the site.
+ */
+#undef WARN
+#undef WARN_ON
+#undef WARN_ON_ONCE
+#undef WARN_ONCE
+
+#define WARN(condition, format...) ({					\
+	int __ret_warn_on = !!(condition);				\
+	if (unlikely(__ret_warn_on)) {					\
+		fprintf(stderr, "WARN at %s:%d: ", __FILE__, __LINE__);	\
+		fprintf(stderr, format);				\
+		abort();						\
+	}								\
+	unlikely(__ret_warn_on);					\
+})
+
+#define WARN_ON(condition)	WARN(condition, "%s\n", #condition)
+#define WARN_ON_ONCE(condition)	WARN_ON(condition)
+#define WARN_ONCE(condition, format...)	WARN(condition, format)

> ---
>  include/linux/maple_tree.h | 54 +++++++++++++++++++++-----------------
>  1 file changed, 30 insertions(+), 24 deletions(-)
>
> diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> index e30e57f5f3df9..0f96f1f19eb95 100644
> --- a/include/linux/maple_tree.h
> +++ b/include/linux/maple_tree.h
> @@ -680,7 +680,7 @@ void mt_cache_shrink(void);
>  		pr_info("Pass: %u Run:%u\n",				\
>  			atomic_read(&maple_tree_tests_passed),		\
>  			atomic_read(&maple_tree_tests_run));		\
> -		dump_stack();						\
> +		BUG_ON(1);						\
>  	} else {							\
>  		atomic_inc(&maple_tree_tests_passed);			\
>  	}								\
> @@ -696,7 +696,7 @@ void mt_cache_shrink(void);
>  		pr_info("Pass: %u Run:%u\n",				\
>  			atomic_read(&maple_tree_tests_passed),		\
>  			atomic_read(&maple_tree_tests_run));		\
> -		dump_stack();						\
> +		BUG_ON(1);						\
>  	} else {							\
>  		atomic_inc(&maple_tree_tests_passed);			\
>  	}								\
> @@ -713,62 +713,68 @@ void mt_cache_shrink(void);
>  		pr_info("Pass: %u Run:%u\n",				\
>  			atomic_read(&maple_tree_tests_passed),		\
>  			atomic_read(&maple_tree_tests_run));		\
> -		dump_stack();						\
> +		BUG_ON(1);						\
>  	} else {							\
>  		atomic_inc(&maple_tree_tests_passed);			\
>  	}								\
>  } while (0)
>
>  #define MT_WARN_ON(__tree, __x)  ({					\
> +	static bool __warned;						\
>  	int ret = !!(__x);						\
>  	atomic_inc(&maple_tree_tests_run);				\
> -	if (ret) {							\
> -		pr_info("WARN at %s:%d (%u)\n",				\
> -		__func__, __LINE__, __x);				\
> +	if (!ret) {							\
> +		atomic_inc(&maple_tree_tests_passed);			\
> +	} else if (!__warned) {						\
> +		__warned = true;					\
> +		pr_info("WARN at %s:%d\n",				\
> +		__func__, __LINE__);					\
>  		mt_dump(__tree, mt_dump_hex);				\
>  		pr_info("Pass: %u Run:%u\n",				\
>  			atomic_read(&maple_tree_tests_passed),		\
>  			atomic_read(&maple_tree_tests_run));		\
> -		dump_stack();						\
> -	} else {							\
> -		atomic_inc(&maple_tree_tests_passed);			\
> +		WARN_ON(1);						\
>  	}								\
>  	unlikely(ret);							\
>  })
>
>  #define MAS_WARN_ON(__mas, __x) ({					\
> +	static bool __warned;						\
>  	int ret = !!(__x);						\
>  	atomic_inc(&maple_tree_tests_run);				\
> -	if (ret) {							\
> -		pr_info("WARN at %s:%d (%u)\n",				\
> -		__func__, __LINE__, __x);				\
> +	if (!ret) {							\
> +		atomic_inc(&maple_tree_tests_passed);			\
> +	} else if (!__warned) {						\
> +		__warned = true;					\
> +		pr_info("WARN at %s:%d\n",				\
> +		__func__, __LINE__);					\
>  		mas_dump(__mas);					\
>  		mt_dump((__mas)->tree, mt_dump_hex);			\
>  		pr_info("Pass: %u Run:%u\n",				\
>  			atomic_read(&maple_tree_tests_passed),		\
>  			atomic_read(&maple_tree_tests_run));		\
> -		dump_stack();						\
> -	} else {							\
> -		atomic_inc(&maple_tree_tests_passed);			\
> +		WARN_ON(1);						\
>  	}								\
>  	unlikely(ret);							\
>  })
>
>  #define MAS_WR_WARN_ON(__wrmas, __x) ({					\
> +	static bool __warned;						\
>  	int ret = !!(__x);						\
>  	atomic_inc(&maple_tree_tests_run);				\
> -	if (ret) {							\
> -		pr_info("WARN at %s:%d (%u)\n",				\
> -		__func__, __LINE__, __x);				\
> +	if (!ret) {							\
> +		atomic_inc(&maple_tree_tests_passed);			\
> +	} else if (!__warned) {						\
> +		__warned = true;					\
> +		pr_info("WARN at %s:%d\n",				\
> +		__func__, __LINE__);					\
>  		mas_wr_dump(__wrmas);					\
>  		mas_dump((__wrmas)->mas);				\
>  		mt_dump((__wrmas)->mas->tree, mt_dump_hex);		\
>  		pr_info("Pass: %u Run:%u\n",				\
>  			atomic_read(&maple_tree_tests_passed),		\
>  			atomic_read(&maple_tree_tests_run));		\
> -		dump_stack();						\
> -	} else {							\
> -		atomic_inc(&maple_tree_tests_passed);			\
> +		WARN_ON(1);						\
>  	}								\
>  	unlikely(ret);							\
>  })
> @@ -776,9 +782,9 @@ void mt_cache_shrink(void);
>  #define MT_BUG_ON(__tree, __x)		BUG_ON(__x)
>  #define MAS_BUG_ON(__mas, __x)		BUG_ON(__x)
>  #define MAS_WR_BUG_ON(__mas, __x)	BUG_ON(__x)
> -#define MT_WARN_ON(__tree, __x)		WARN_ON(__x)
> -#define MAS_WARN_ON(__mas, __x)		WARN_ON(__x)
> -#define MAS_WR_WARN_ON(__mas, __x)	WARN_ON(__x)
> +#define MT_WARN_ON(__tree, __x)		WARN_ON_ONCE(__x)
> +#define MAS_WARN_ON(__mas, __x)		WARN_ON_ONCE(__x)
> +#define MAS_WR_WARN_ON(__mas, __x)	WARN_ON_ONCE(__x)
>  #endif /* CONFIG_DEBUG_MAPLE_TREE */
>
>  /**
> --
> 2.47.3
>

--
Cheers, Lorenzo

Re: [PATCH 3/4] maple_tree: Update internal warning and bug_on code

[Liam R. Howlett (Google)]

On 26/10/28 05:54PM, Lorenzo Stoakes (ARM) wrote:
> ma
>  On Wed, Oct 28, 2026 at 11:42:17AM -0400, Liam R. Howlett (Google) wrote:
> > When CONFIG_DEBUG_MAPLE_TREE is set, call the WARN_ON_ONCE() after the
> > custom information is dumped about the tree.  Without using the kernel's
> > WARN_ON calls, syzbot will not catch issues detected by this code.
> 
> Mega nit but commit message doesn't mention the BUG_ON() bits :)
> 
> >
> > Update the non-debug code to call WARN_ON_ONCE() as well.
> >
> > Cc: <stable@vger.kernel.org>
> > Reported-by: Lorenzo Stoakes <ljs@kernel.org>
> > Fixes: bf857ddd21d0b ("maple_tree: move debug check to __mas_set_range()")
> 
> LLM overlord says bf857ddd21d0b only moved it, and f0a1f866aba1 actually
> implemented it.
> 
> > Signed-off-by: Liam R. Howlett (Google) <liam@infradead.org>
> 
> Looks sensible to me from kernel perspective, but LLM overlord tells me this
> changes the userland tests from asserting on dump_stack() to just printing
> something out on WARN_ON().
> 
> (BUG_ON() is OK, it asserts already).
> 
> However we really do need this for the kernel so CONFIG_DEBUG_MAPLE_TREE
> triggers syzbot and such, so maybe the userland bit can be a follow-up?

Wow, so any WARN() before... I'm trying not to think about it.

The change below is good to be squashed into the fix I sent.  It also
makes vma warnings fatal - which should also happen.

Andrew, can you take care of this or would you rather a respin?


> 
> On that basis:
> 
> Reviewed-by: Lorenzo Stoakes (ARM) <ljs@kernel.org>
> 
> Or... maybe just respin with something actually, can fix it by updating the
> shared maple tree testing header to make warn do something like this
> (schlopped, apologies):
> 
> diff --git a/tools/testing/shared/maple-shared.h b/tools/testing/shared/maple-shared.h
> index 2a1e9a8594a2..112052e7201f 100644
> --- a/tools/testing/shared/maple-shared.h
> +++ b/tools/testing/shared/maple-shared.h
> @@ -10,6 +10,30 @@
>  #include <time.h>
>  #include "linux/init.h"
> 
> +/*
> + * The tools/include/asm/bug.h WARN*() family only prints a message and
> + * carries on.  Nothing in the maple tree or VMA tests expects a warning, so
> + * treat one as a failure and abort at the site.
> + */
> +#undef WARN
> +#undef WARN_ON
> +#undef WARN_ON_ONCE
> +#undef WARN_ONCE
> +
> +#define WARN(condition, format...) ({					\
> +	int __ret_warn_on = !!(condition);				\
> +	if (unlikely(__ret_warn_on)) {					\
> +		fprintf(stderr, "WARN at %s:%d: ", __FILE__, __LINE__);	\
> +		fprintf(stderr, format);				\
> +		abort();						\
> +	}								\
> +	unlikely(__ret_warn_on);					\
> +})
> +
> +#define WARN_ON(condition)	WARN(condition, "%s\n", #condition)
> +#define WARN_ON_ONCE(condition)	WARN_ON(condition)
> +#define WARN_ONCE(condition, format...)	WARN(condition, format)
> 
> > ---
> >  include/linux/maple_tree.h | 54 +++++++++++++++++++++-----------------
> >  1 file changed, 30 insertions(+), 24 deletions(-)
> >
> > diff --git a/include/linux/maple_tree.h b/include/linux/maple_tree.h
> > index e30e57f5f3df9..0f96f1f19eb95 100644
> > --- a/include/linux/maple_tree.h
> > +++ b/include/linux/maple_tree.h
> > @@ -680,7 +680,7 @@ void mt_cache_shrink(void);
> >  		pr_info("Pass: %u Run:%u\n",				\
> >  			atomic_read(&maple_tree_tests_passed),		\
> >  			atomic_read(&maple_tree_tests_run));		\
> > -		dump_stack();						\
> > +		BUG_ON(1);						\
> >  	} else {							\
> >  		atomic_inc(&maple_tree_tests_passed);			\
> >  	}								\
> > @@ -696,7 +696,7 @@ void mt_cache_shrink(void);
> >  		pr_info("Pass: %u Run:%u\n",				\
> >  			atomic_read(&maple_tree_tests_passed),		\
> >  			atomic_read(&maple_tree_tests_run));		\
> > -		dump_stack();						\
> > +		BUG_ON(1);						\
> >  	} else {							\
> >  		atomic_inc(&maple_tree_tests_passed);			\
> >  	}								\
> > @@ -713,62 +713,68 @@ void mt_cache_shrink(void);
> >  		pr_info("Pass: %u Run:%u\n",				\
> >  			atomic_read(&maple_tree_tests_passed),		\
> >  			atomic_read(&maple_tree_tests_run));		\
> > -		dump_stack();						\
> > +		BUG_ON(1);						\
> >  	} else {							\
> >  		atomic_inc(&maple_tree_tests_passed);			\
> >  	}								\
> >  } while (0)
> >
> >  #define MT_WARN_ON(__tree, __x)  ({					\
> > +	static bool __warned;						\
> >  	int ret = !!(__x);						\
> >  	atomic_inc(&maple_tree_tests_run);				\
> > -	if (ret) {							\
> > -		pr_info("WARN at %s:%d (%u)\n",				\
> > -		__func__, __LINE__, __x);				\
> > +	if (!ret) {							\
> > +		atomic_inc(&maple_tree_tests_passed);			\
> > +	} else if (!__warned) {						\
> > +		__warned = true;					\
> > +		pr_info("WARN at %s:%d\n",				\
> > +		__func__, __LINE__);					\
> >  		mt_dump(__tree, mt_dump_hex);				\
> >  		pr_info("Pass: %u Run:%u\n",				\
> >  			atomic_read(&maple_tree_tests_passed),		\
> >  			atomic_read(&maple_tree_tests_run));		\
> > -		dump_stack();						\
> > -	} else {							\
> > -		atomic_inc(&maple_tree_tests_passed);			\
> > +		WARN_ON(1);						\
> >  	}								\
> >  	unlikely(ret);							\
> >  })
> >
> >  #define MAS_WARN_ON(__mas, __x) ({					\
> > +	static bool __warned;						\
> >  	int ret = !!(__x);						\
> >  	atomic_inc(&maple_tree_tests_run);				\
> > -	if (ret) {							\
> > -		pr_info("WARN at %s:%d (%u)\n",				\
> > -		__func__, __LINE__, __x);				\
> > +	if (!ret) {							\
> > +		atomic_inc(&maple_tree_tests_passed);			\
> > +	} else if (!__warned) {						\
> > +		__warned = true;					\
> > +		pr_info("WARN at %s:%d\n",				\
> > +		__func__, __LINE__);					\
> >  		mas_dump(__mas);					\
> >  		mt_dump((__mas)->tree, mt_dump_hex);			\
> >  		pr_info("Pass: %u Run:%u\n",				\
> >  			atomic_read(&maple_tree_tests_passed),		\
> >  			atomic_read(&maple_tree_tests_run));		\
> > -		dump_stack();						\
> > -	} else {							\
> > -		atomic_inc(&maple_tree_tests_passed);			\
> > +		WARN_ON(1);						\
> >  	}								\
> >  	unlikely(ret);							\
> >  })
> >
> >  #define MAS_WR_WARN_ON(__wrmas, __x) ({					\
> > +	static bool __warned;						\
> >  	int ret = !!(__x);						\
> >  	atomic_inc(&maple_tree_tests_run);				\
> > -	if (ret) {							\
> > -		pr_info("WARN at %s:%d (%u)\n",				\
> > -		__func__, __LINE__, __x);				\
> > +	if (!ret) {							\
> > +		atomic_inc(&maple_tree_tests_passed);			\
> > +	} else if (!__warned) {						\
> > +		__warned = true;					\
> > +		pr_info("WARN at %s:%d\n",				\
> > +		__func__, __LINE__);					\
> >  		mas_wr_dump(__wrmas);					\
> >  		mas_dump((__wrmas)->mas);				\
> >  		mt_dump((__wrmas)->mas->tree, mt_dump_hex);		\
> >  		pr_info("Pass: %u Run:%u\n",				\
> >  			atomic_read(&maple_tree_tests_passed),		\
> >  			atomic_read(&maple_tree_tests_run));		\
> > -		dump_stack();						\
> > -	} else {							\
> > -		atomic_inc(&maple_tree_tests_passed);			\
> > +		WARN_ON(1);						\
> >  	}								\
> >  	unlikely(ret);							\
> >  })
> > @@ -776,9 +782,9 @@ void mt_cache_shrink(void);
> >  #define MT_BUG_ON(__tree, __x)		BUG_ON(__x)
> >  #define MAS_BUG_ON(__mas, __x)		BUG_ON(__x)
> >  #define MAS_WR_BUG_ON(__mas, __x)	BUG_ON(__x)
> > -#define MT_WARN_ON(__tree, __x)		WARN_ON(__x)
> > -#define MAS_WARN_ON(__mas, __x)		WARN_ON(__x)
> > -#define MAS_WR_WARN_ON(__mas, __x)	WARN_ON(__x)
> > +#define MT_WARN_ON(__tree, __x)		WARN_ON_ONCE(__x)
> > +#define MAS_WARN_ON(__mas, __x)		WARN_ON_ONCE(__x)
> > +#define MAS_WR_WARN_ON(__mas, __x)	WARN_ON_ONCE(__x)
> >  #endif /* CONFIG_DEBUG_MAPLE_TREE */
> >
> >  /**
> > --
> > 2.47.3
> >
> 
> --
> Cheers, Lorenzo

Re: [PATCH 4/4] rhashtable: fix vmalloc() deadlock in atomic rehash

[Herbert Xu]

On Wed, Oct 28, 2026 at 11:42:18AM -0400, Liam R. Howlett (Google) wrote:
>
> Below, one CPU adds an FDB entry for an RTM_NEWNEIGH netlink request,
> while another CPU is inside vmalloc() or vfree():
> 
>     RTM_NEWNEIGH                      vmalloc() or vfree()
>     ============                      ====================
>     spin_lock_bh(&br->hash_lock)
>                                       spin_lock(&vn->busy.lock)
>     rhashtable_insert_rehash()
>       kvmalloc(GFP_ATOMIC)
>         vmalloc()
>           spin_lock(&vn->busy.lock)
>             waits for the other CPU
>                                       softirq: a frame for the bridge
>                                         spin_lock(&br->hash_lock)
>                                           waits for RTM_NEWNEIGH

I think this is a fundamental bug in the kvmalloc non-blocking
support patch.  How can it be used at all if it is susceptible
to such dead-locks?

And if you can't use it safely why don't we just get rid of the
broken kvmalloc non-block path and have it always go to kmalloc
like it did before?
 
> Fixes: c6307674ed82 ("mm: kvmalloc: add non-blocking support for vmalloc")

BTW, rhashtable patches should be sent to linux-crypto.

Thanks,
-- 
Email: Herbert Xu <herbert@gondor.apana.org.au>
Home Page: http://gondor.apana.org.au/~herbert/
PGP Key: http://gondor.apana.org.au/~herbert/pubkey.txt

Re: [PATCH 4/4] rhashtable: fix vmalloc() deadlock in atomic rehash

[Uladzislau Rezki]

On Thu, Oct 29, 2026 at 10:16:36AM +0800, Herbert Xu wrote:
> On Wed, Oct 28, 2026 at 11:42:18AM -0400, Liam R. Howlett (Google) wrote:
> >
> > Below, one CPU adds an FDB entry for an RTM_NEWNEIGH netlink request,
> > while another CPU is inside vmalloc() or vfree():
> > 
> >     RTM_NEWNEIGH                      vmalloc() or vfree()
> >     ============                      ====================
> >     spin_lock_bh(&br->hash_lock)
> >                                       spin_lock(&vn->busy.lock)
> >     rhashtable_insert_rehash()
> >       kvmalloc(GFP_ATOMIC)
> >         vmalloc()
> >           spin_lock(&vn->busy.lock)
> >             waits for the other CPU
> >                                       softirq: a frame for the bridge
> >                                         spin_lock(&br->hash_lock)
> >                                           waits for RTM_NEWNEIGH
> 
> I think this is a fundamental bug in the kvmalloc non-blocking
> support patch.  How can it be used at all if it is susceptible
> to such dead-locks?
> 
> And if you can't use it safely why don't we just get rid of the
> broken kvmalloc non-block path and have it always go to kmalloc
> like it did before?
>  
If we have a look at this as we did not have vmalloc() here:


     RTM_NEWNEIGH                      foo() or ...
     ============                      ====================
     lock_bh(&br->hash_lock)
                                       foo()
                                        lock(B)
     rhashtable_insert_rehash()
         foo()
           lock(B)
             waits for the other CPU
                                       softirq: a frame for the bridge
                                         lock(&br->hash_lock)
                                           waits for RTM_NEWNEIGH

Same issue?

I have a question:

GFP_ATOMIC/GFP_NOWAIT guarantee they do not sleep. Do they guarantee
not hitting ABBA dead-locks or they are not interrupted?

--
Uladzislau Rezki

Re: [PATCH 4/4] rhashtable: fix vmalloc() deadlock in atomic rehash

[Liam R. Howlett (Google)]

Sorry for missing the ML in my initial email, I missed it from
get_maintainers.  I should have really clued in with such a small cc
list ;)

On 26/10/29 11:08AM, Uladzislau Rezki wrote:
> On Thu, Oct 29, 2026 at 10:16:36AM +0800, Herbert Xu wrote:
> > On Wed, Oct 28, 2026 at 11:42:18AM -0400, Liam R. Howlett (Google) wrote:
> > >
> > > Below, one CPU adds an FDB entry for an RTM_NEWNEIGH netlink request,
> > > while another CPU is inside vmalloc() or vfree():
> > > 
> > >     RTM_NEWNEIGH                      vmalloc() or vfree()
> > >     ============                      ====================
> > >     spin_lock_bh(&br->hash_lock)
> > >                                       spin_lock(&vn->busy.lock)
> > >     rhashtable_insert_rehash()
> > >       kvmalloc(GFP_ATOMIC)
> > >         vmalloc()
> > >           spin_lock(&vn->busy.lock)
> > >             waits for the other CPU
> > >                                       softirq: a frame for the bridge
> > >                                         spin_lock(&br->hash_lock)
> > >                                           waits for RTM_NEWNEIGH
> > 
> > I think this is a fundamental bug in the kvmalloc non-blocking
> > support patch.  How can it be used at all if it is susceptible
> > to such dead-locks?
> > 
> > And if you can't use it safely why don't we just get rid of the
> > broken kvmalloc non-block path and have it always go to kmalloc
> > like it did before?
> >  
> If we have a look at this as we did not have vmalloc() here:
> 
> 
>      RTM_NEWNEIGH                      foo() or ...
>      ============                      ====================
>      lock_bh(&br->hash_lock)
>                                        foo()
>                                         lock(B)
>      rhashtable_insert_rehash()
>          foo()
>            lock(B)
>              waits for the other CPU
>                                        softirq: a frame for the bridge
>                                          lock(&br->hash_lock)
>                                            waits for RTM_NEWNEIGH
> 
> Same issue?

Looks like it to me.

> 
> I have a question:
> 
> GFP_ATOMIC/GFP_NOWAIT guarantee they do not sleep. Do they guarantee
> not hitting ABBA dead-locks or they are not interrupted?

GFP_ATOMIC and GFP_NOWAIT can be interrupted.  It's more about not
waiting for reclaim (kswapd might still run) and GFP_ATOMIC might dip
into reserves.

The issue is that kvmalloc() now falls back to vmalloc() for
non-blocking flags (I am restating this to make sure I'm not missing
something here, please correct me).

So this changes what is called internal to rhastable so it doesn't reach
vmalloc(), like before, if the caller cannot block - they go to
kmalloc() with the old fall back.

I *think* the question is if the change should be here in the caller,
internal to mm, or a new call to opt-in.

Considering this is the only kvmalloc() caller that forwards
non-blocking gfp from BH lock + softirq context, I think that it makes
sense to do it in the caller.

Given where we are in the release, this fixes a real issue that can
happen so maybe we take this now and settle the general handling later?

Thanks,
Liam