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

[Liam R. Howlett (Google)]

From: Chris Mason <mason@xxxxxxxxxx>

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@xxxxxxxxxxxxxxx>
Fixes: c6307674ed82 ("mm: kvmalloc: add non-blocking support for vmalloc")
Assisted-by: LLM
Signed-off-by: Chris Mason <mason@xxxxxxxxxx>
Signed-off-by: David Hildenbrand (Arm) <david@xxxxxxxxxx>
Signed-off-by: Liam R. Howlett (Google) <liam@xxxxxxxxxxxxx>
---
 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