[PATCH bpf] bpf: Fail rhtab inserts and deletes with IRQs disabled

[Mani Tofigh via B4 Relay]

From: Mani Tofigh <mt4022@xxxxxxxxxxxx>

A BPF program can spin forever on a resizable hash map's bucket lock
that its own CPU already holds.  Inserts and deletes take the
rhashtable bucket lock, a bit spinlock that can't detect re-entry.  The
resize worker calls the hash function with that lock held, so a kprobe
program on the hash function that deletes a key of the same bucket
never gets the lock:

  rht_deferred_worker()
    rht_lock(old_tbl, bkt)
    rhashtable_jhash2()
      kprobe program
        bpf_map_delete_elem()
          rht_lock(old_tbl, bkt)
            /* spins with IRQs disabled */

  [   29.890449] rcu: INFO: rcu_preempt detected stalls on CPUs/tasks:
  ...
  [   29.906964] NMI backtrace for cpu 0
  [   29.906977] CPU: 0 UID: 0 PID: 9 Comm: kworker/0:0 Tainted: G        W            7.3.0-17087-gd865f2677c44 #1 PREEMPT
  [   29.907021] Workqueue: events rht_deferred_worker
  [   29.907041] RIP: 0010:rhtab_delete_elem+0x15f9/0x1c80
  ...
  [   29.907139] Call Trace:
  [   29.907145]  <TASK>
  [   29.907193]  rhtab_map_delete_elem+0x61/0x120
  [   29.907208]  bpf_prog_12e9295082de5b34+0xa0/0xee
  [   29.907231]  trace_call_bpf+0x2ca/0x930
  [   29.907334]  kprobe_perf_func+0x106/0x700
  [   29.907381]  aggr_pre_handler+0x8f/0x110
  [   29.907403]  kprobe_int3_handler+0x335/0x750
  [   29.907433]  do_int3+0xd/0x50
  [   29.907445]  exc_int3+0x165/0x340
  [   29.907467]  asm_exc_int3+0x39/0x40
  [   29.907477] RIP: 0010:rhashtable_jhash2+0x5/0x360
  ...

A program in NMI over any holder of a bucket lock can do the same.

A bucket lock is only ever held with IRQs disabled, so return -EBUSY
from deletes and from inserts of new keys when IRQs are already
disabled, like the other hash maps do on re-entry.  Lookups and updates
of existing keys don't take the lock and still work.  With the fix, the
delete fails with -EBUSY and the resize finishes.

This bug was identified and confirmed with the help of a deterministic
hypervisor currently under development.  The C reproducer below however
hits it within about 1s.

Fixes: 16b4d3e2fb24 ("bpf: Implement resizable hashmap basic functions")
Signed-off-by: Mani Tofigh <mt4022@xxxxxxxxxxxx>
---
This is the check Alexei suggested on the RFC of the series [1].  It also
stops perf_event and other programs that run with IRQs disabled from
inserting or deleting keys.  I can turn the reproducer into a selftest
if that helps.

[1] https://lore.kernel.org/all/CAADnVQKvp2tnQSWW4Kh3ofGLvaEYJ47kyZeNUscAH_DShw8XHw@xxxxxxxxxxxxxx/

Reproducer: https://github.com/manitofigh/files/blob/main/linux-repros/rhashlock.c
---
 kernel/bpf/hashtab.c | 16 +++++++++++-----
 1 file changed, 11 insertions(+), 5 deletions(-)

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 6e2115477cb9..1a9f07b71bca 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -3144,11 +3144,14 @@ static int rhtab_delete_elem(struct bpf_rhtab *rhtab, struct rhtab_elem *elem, v
 	int err;
 
 	/*
-	 * disable_instrumentation() mitigates the deadlock for programs running in NMI context.
-	 * rhashtable locks bucket with local_irq_save(). Only NMI programs may reenter
-	 * rhashtable code, bpf_disable_instrumentation() disables programs running in NMI, except
-	 * raw tracepoints, which we don't have in rhashtable.
+	 * rhashtable takes its bucket bit locks with IRQs disabled and can't
+	 * detect re-entry. With IRQs already disabled this CPU may already
+	 * hold one, e.g., in NMI or in a program attached inside the resize
+	 * worker's locked section.
 	 */
+	if (irqs_disabled())
+		return -EBUSY;
+
 	bpf_disable_instrumentation();
 
 	if (rhtab->map.key_size == sizeof(long))
@@ -3261,6 +3264,10 @@ static long rhtab_map_update_elem(struct bpf_map *map, void *key, void *value, u
 	if (atomic_read(&rhtab->ht.nelems) >= map->max_entries)
 		return -E2BIG;
 
+	/* see rhtab_delete_elem() */
+	if (irqs_disabled())
+		return -EBUSY;
+
 	elem = bpf_mem_cache_alloc(&rhtab->ma);
 	if (!elem)
 		return -ENOMEM;
@@ -3268,7 +3275,6 @@ static long rhtab_map_update_elem(struct bpf_map *map, void *key, void *value, u
 	memcpy(elem->data, key, map->key_size);
 	copy_map_value(map, rhtab_elem_value(elem, map->key_size), value);
 
-	/* Prevent deadlock for NMI programs attempting to take bucket lock */
 	bpf_disable_instrumentation();
 
 	if (map->key_size == sizeof(long))

---
base-commit: 05441d697f7f9a927264f4058cbbc6a03dfcac9d
change-id: 20261103-bpf-rhtab-irqs-disabled-c4646c9e0fe2

Best regards,
--  
Mani Tofigh <mt4022@xxxxxxxxxxxx>