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

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

[Mani Tofigh]

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@columbia.edu>
---
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@mail.gmail.com/

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@columbia.edu>

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

[Mani Tofigh via B4 Relay]

From: Mani Tofigh <mt4022@columbia.edu>

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@columbia.edu>
---
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@mail.gmail.com/

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@columbia.edu>

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

[sashiko-bot]

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] bpf: livelock in rhtab_lookup_elem() when interrupting rhashtable_rehash_one()
--

commit b84a73a0b5e527ae59fe3ae2f05ee59cd4d31935
Author: Mani Tofigh <mt4022@columbia.edu>

bpf: Fail rhtab inserts and deletes with IRQs disabled

This commit rejects rhtab element deletions and new insertions with -EBUSY
when IRQs are disabled to prevent same-CPU deadlocks on rhashtable bucket bit
spinlocks. Lookups and updates of existing elements continue to run without
checking irqs_disabled().

> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> index 6e2115477cb9e..1a9f07b71bca2 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;

[Severity: High]
Can a BPF program running with IRQs disabled still livelock in
rhtab_lookup_elem() before reaching this check, or during
rhtab_map_lookup_elem() and rhtab_map_update_elem()?

Both rhtab_map_delete_elem() and rhtab_map_lookup_and_delete_elem() call
rhtab_lookup_elem() before calling rhtab_delete_elem(), and
rhtab_map_update_elem() also calls rhtab_lookup_elem() before checking
irqs_disabled():

kernel/bpf/hashtab.c:rhtab_map_delete_elem() {
	guard(rcu)();
	elem = rhtab_lookup_elem(map, key);
	if (!elem)
		return -ENOENT;

	return rhtab_delete_elem(rhtab, elem, NULL, 0);
}

During a resize in
rht_deferred_worker()->rhashtable_rehash_table()->rhashtable_rehash_chain()->rhashtable_rehash_one(),
the worker holds the old_tbl bucket bit lock with IRQs disabled and splices
the tail entry of the old_tbl bucket chain onto the head of the new_tbl
bucket chain before unlinking it from old_tbl:

lib/rhashtable.c:rhashtable_rehash_one() {
	...
	RCU_INIT_POINTER(entry->next, head);

	rht_assign_unlock(new_tbl, &new_tbl->buckets[new_hash], entry, flags);

	if (pprev)
		rcu_assign_pointer(*pprev, next);
	else
		/* Need to preserved the bit lock. */
		rht_assign_locked(bkt, next);
	...
}

Between RCU_INIT_POINTER(entry->next, head) and unlinking entry from old_tbl,
walking that bucket chain in old_tbl follows entry->next into new_tbl and
terminates at RHT_NULLS_MARKER(&new_tbl->buckets[new_hash]) instead of
RHT_NULLS_MARKER(bkt).

If an NMI or kprobe fires on the same CPU during this window (for example in
rht_assign_unlock()) and the BPF program calls rhtab_lookup_elem() for a key
in that old_tbl bucket that is not found in the chain, __rhashtable_lookup()
sees he != RHT_NULLS_MARKER(bkt) and retries in a loop:

include/linux/rhashtable.h:__rhashtable_lookup() {
	...
	do {
		rht_for_each_rcu_from(he, __rht_ptr_rcu(bkt, freq), tbl, hash) {
			if (params.obj_cmpfn ?
			    params.obj_cmpfn(&arg, rht_obj(ht, he)) :
			    rhashtable_compare(&arg, rht_obj(ht, he), params))
				continue;
			return he;
		}
		/* An object might have been moved to a different hash chain,
		 * while we walk along it - better check and retry.
		 */
	} while (he != RHT_NULLS_MARKER(bkt));
	...
}

Because rhashtable_rehash_one() is interrupted on the same CPU and cannot
finish unlinking entry from old_tbl, wouldn't __rhashtable_lookup() spin
forever here?

-- 
Sashiko AI review · https://sashiko.dev/#/patchset/20261103-bpf-rhtab-irqs-disabled-v1-1-9874d96a088c@columbia.edu?part=1

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

[bot+bpf-ci]

[-- Attachment #1: Type: text/plain, Size: 3657 bytes --]

> bpf: Fail rhtab inserts and deletes with IRQs disabled

TL;DR: The irqs_disabled() check in rhtab delete and insert may return -EBUSY
for every IRQs-off caller, such as sched_switch or perf programs, not just
re-entry, breaking previously working users; the commit message's claim about
other hash maps is also questioned.

> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> --- 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();

Does this irqs_disabled() check detect re-entry, or does it reject every
delete made from any context that runs with IRQs off?

Most of those contexts do not hold a bucket lock.  For example, a tp_btf
program on sched_switch runs after __schedule() has called
local_irq_disable() and taken the rq lock:

  __schedule()
    trace_sched_switch()
      bpf program
        bpf_map_delete_elem()
          rhtab_map_delete_elem()
            rhtab_delete_elem()
              irqs_disabled() -> -EBUSY

The same applies to sched_wakeup and irq_handler_entry tracepoints,
perf_event programs (which run from the PMU NMI or hrtimer hardirq),
fentry/kprobe on functions that run with IRQs off, sched_ext callbacks
under the rq lock, and code between bpf_local_irq_save() and
bpf_local_irq_restore().

The verifier has no program type restriction for BPF_MAP_TYPE_RHASH, and
these calls succeeded before this patch.  Would a guard that fires only on
actual re-entry, such as a per-CPU or per-map marker set around the
rhashtable locked sections, or a bounded trylock on the bucket lock, avoid
the deadlock without breaking these users?

The commit message says -EBUSY is returned "like the other hash maps do on
re-entry".  Is that accurate?  htab_lock_bucket() uses
raw_res_spin_lock_irqsave() and fails with -EDEADLK or -ETIMEDOUT only when
rqspinlock detects a deadlock or timeout, not merely because IRQs are
disabled.

Also, 46730ee6e884 ("rhashtable: Use irq work for shrinking") moved the
shrink kick to irq_work so that it may be called in NMI context.  With this
check, __rhashtable_remove_fast_one() can no longer reach that
irq_work_queue() call from NMI or with IRQs disabled via this map.

[ ... ]

> @@ -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;
> +

The same question applies here: this makes every insert of a new key fail
with -EBUSY from any IRQs-off context, whether or not a bucket lock is held
by the current CPU.

[ ... ]


---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/41698986159

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

[Mykyta Yatsenko]

On 11/3/26 6:46 PM, Mani Tofigh via B4 Relay wrote:
> From: Mani Tofigh <mt4022@columbia.edu>
> 
> 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@columbia.edu>
> ---
> 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@mail.gmail.com/
> 
> Reproducer: https://github.com/manitofigh/files/blob/main/linux-repros/rhashlock.c

Thanks for the patch. Looks good, currently we rely on bpf_disable_instrumentation()
to protect bucket lock from re-entrance, but it's not called by the rehash, which takes
the bucket lock.
bots highlighted another problem - potential infinite loop in the lookup. I think
it's a separate issue, that needs another fix, as we probably want to keep at least
lookup in all contexts.

Acked-by: Mykyta Yatsenko <yatsenko@meta.com>
> ---
>  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@columbia.edu>

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

[Alexei Starovoitov]

On Tue, Nov 03, 2026 at 10:46 AM Mani Tofigh via B4 Relay <devnull+mt4022.columbia.edu@kernel.org> wrote:
> 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

The other hash maps fail on re-entry only. rqspinlock detects it.
This check fails every insert and delete with irqs disabled.
That's perf_event progs, kprobes via int3, sched_switch and
sched_wakeup tracepoints, sched_ext ops under rq lock.
imo it's not worth breaking all of them for a rare deadlock.

> 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.

It was my suggestion, sorry. It's too broad.
v4 of rhash picked bpf_disable_instrumentation() to keep these callers:
https://lore.kernel.org/bpf/20260513-rhash-v4-0-dd3d541ccb0b@meta.com/

Only a caller with irqs disabled can run inside the locked section of
this cpu. Lets trylock the bucket in that case and spin otherwise.

  caller with irqs disabled    today      this patch   trylock
  -------------------------    --------   ----------   -------
  bucket is not locked         works      -EBUSY       works
  locked by another cpu        spins      -EBUSY       -EBUSY
  locked by this cpu           deadlock   -EBUSY       -EBUSY

Then no need for bpf_disable_instrumentation() in rhtab.
params.trylock_irqsoff is a compile time constant in the fast path,
like insecure_elasticity. The other rhashtable users pay nothing.

The diff leaves one more bug: rhashtable_insert_rehash() calls
kvmalloc(GFP_ATOMIC). That's not ok in NMI.

Something like this (compile tested only):

diff --git a/include/linux/rhashtable-types.h b/include/linux/rhashtable-types.h
index 3576b8f..a5c4e69 100644
--- a/include/linux/rhashtable-types.h
+++ b/include/linux/rhashtable-types.h
@@ -52,6 +52,8 @@ typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg,
  * @min_size: Minimum size while shrinking
  * @insecure_elasticity: Set to true to disable chain length checks
  * @automatic_shrinking: Enable automatic shrinking of tables
+ * @trylock_irqsoff: With irqs disabled insert and remove don't spin on
+ *		     the bucket lock and return -EBUSY
  * @hashfn: Hash function (default: jhash2 if !(key_len % 4), or jhash)
  * @obj_hashfn: Function to hash object
  * @obj_cmpfn: Function to compare key with object
@@ -65,6 +67,7 @@ struct rhashtable_params {
 	u16			min_size;
 	bool			insecure_elasticity;
 	bool			automatic_shrinking;
+	bool			trylock_irqsoff;
 	rht_hashfn_t		hashfn;
 	rht_obj_hashfn_t	obj_hashfn;
 	rht_obj_cmpfn_t		obj_cmpfn;
diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 70dac92..ba2c594 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -339,6 +339,33 @@ static inline unsigned long rht_lock(struct bucket_table *tbl,
 	return rht_lock_nested(tbl, bkt, 0);
 }

+/*
+ * The bucket lock is held with irqs disabled. A caller with irqs disabled
+ * may run inside the locked section of this cpu (NMI, kprobe, tracepoint).
+ * It cannot spin.
+ */
+static inline bool rht_lock_or_busy(struct bucket_table *tbl,
+				    struct rhash_lock_head __rcu **bkt,
+				    const struct rhashtable_params params,
+				    unsigned long *flags)
+	__cond_acquires(true, __bitlock(0, bkt))
+{
+	if (!params.trylock_irqsoff || !irqs_disabled()) {
+		*flags = rht_lock(tbl, bkt);
+		return true;
+	}
+	/* bit_spin_trylock() always succeeds on UP */
+	if (!IS_ENABLED(CONFIG_SMP))
+		return false;
+	local_irq_save(*flags);
+	if (!bit_spin_trylock(0, (unsigned long *)bkt)) {
+		local_irq_restore(*flags);
+		return false;
+	}
+	lock_acquire_exclusive(&tbl->dep_map, 0, 1, NULL, _THIS_IP_);
+	return true;
+}
+
 static inline void rht_unlock(struct bucket_table *tbl,
 			      struct rhash_lock_head __rcu **bkt,
 			      unsigned long flags)
@@ -785,7 +812,9 @@ static __always_inline void *__rhashtable_insert_fast(
 	if (!bkt)
 		goto out;
 	pprev = NULL;
-	flags = rht_lock(tbl, bkt);
+	data = ERR_PTR(-EBUSY);
+	if (!rht_lock_or_busy(tbl, bkt, params, &flags))
+		goto out;

 	if (unlikely(rcu_access_pointer(tbl->future_tbl))) {
 slow_path:
@@ -1066,7 +1095,8 @@ static __always_inline int __rhashtable_remove_fast_one(
 	if (!bkt)
 		return -ENOENT;
 	pprev = NULL;
-	flags = rht_lock(tbl, bkt);
+	if (!rht_lock_or_busy(tbl, bkt, params, &flags))
+		return -EBUSY;

 	rht_for_each_from(he, rht_ptr(bkt, tbl, hash), tbl, hash) {
 		struct rhlist_head *list;
@@ -1149,6 +1179,7 @@ static __always_inline int __rhashtable_remove_fast(
 	 */
 	while ((err = __rhashtable_remove_fast_one(ht, tbl, obj, params,
 						   rhlist)) &&
+	       err != -EBUSY &&
 	       (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
 		;

diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 6e21154..edc7572 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -2983,6 +2983,7 @@ struct bpf_rhtab {
 static const struct rhashtable_params rhtab_params = {
 	.head_offset = offsetof(struct rhtab_elem, node),
 	.key_offset  = offsetof(struct rhtab_elem, data),
+	.trylock_irqsoff = true,
 };

 static inline void *rhtab_elem_value(struct rhtab_elem *l, u32 key_size)
@@ -3011,6 +3012,7 @@ static const struct rhashtable_params rhtab_params_long = {
 	.head_offset = offsetof(struct rhtab_elem, node),
 	.key_offset  = offsetof(struct rhtab_elem, data),
 	.key_len     = sizeof(long),
+	.trylock_irqsoff = true,
 	.hashfn      = rhtab_hashfn_long,
 	.obj_cmpfn   = rhtab_key_cmp_long,
 };
@@ -3143,21 +3145,11 @@ 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.
-	 */
-	bpf_disable_instrumentation();
-
 	if (rhtab->map.key_size == sizeof(long))
 		err = rhashtable_remove_fast(&rhtab->ht, &elem->node, rhtab_params_long);
 	else
 		err = rhashtable_remove_fast(&rhtab->ht, &elem->node, rhtab_params);

-	bpf_enable_instrumentation();
-
 	if (err)
 		return err;

@@ -3268,16 +3260,11 @@ 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))
 		tmp = rhashtable_lookup_get_insert_fast(&rhtab->ht, &elem->node, rhtab_params_long);
 	else
 		tmp = rhashtable_lookup_get_insert_fast(&rhtab->ht, &elem->node, rhtab_params);

-	bpf_enable_instrumentation();
-
 	if (tmp) {
 		bpf_mem_cache_free(&rhtab->ma, elem);
 		if (IS_ERR(tmp))
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 500c45c..2dc13f0 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -650,7 +650,8 @@ static void *rhashtable_try_insert(struct rhashtable *ht, const void *key,
 		} else {
 			bool inserted;

-			flags = rht_lock(tbl, bkt);
+			if (!rht_lock_or_busy(tbl, bkt, ht->p, &flags))
+				return ERR_PTR(-EBUSY);
 			data = rhashtable_lookup_one(ht, bkt, tbl,
 						     hash, key, obj);
 			new_tbl = rhashtable_insert_one(ht, bkt, tbl,

Pls add the reproducer as a selftest in patch 2 and cc Herbert Xu
on respin.

pw-bot: cr

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

[Mykyta Yatsenko]

On 11/4/26 12:35 AM, Alexei Starovoitov wrote:
> On Tue, Nov 03, 2026 at 10:46 AM Mani Tofigh via B4 Relay <devnull+mt4022.columbia.edu@kernel.org> wrote:
>> 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
> 
> The other hash maps fail on re-entry only. rqspinlock detects it.
> This check fails every insert and delete with irqs disabled.
> That's perf_event progs, kprobes via int3, sched_switch and
> sched_wakeup tracepoints, sched_ext ops under rq lock.
> imo it's not worth breaking all of them for a rare deadlock.
> 
>> 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.
> 
> It was my suggestion, sorry. It's too broad.
> v4 of rhash picked bpf_disable_instrumentation() to keep these callers:
> https://lore.kernel.org/bpf/20260513-rhash-v4-0-dd3d541ccb0b@meta.com/
> 
> Only a caller with irqs disabled can run inside the locked section of
> this cpu. Lets trylock the bucket in that case and spin otherwise.
> 
>   caller with irqs disabled    today      this patch   trylock
>   -------------------------    --------   ----------   -------
>   bucket is not locked         works      -EBUSY       works
>   locked by another cpu        spins      -EBUSY       -EBUSY
>   locked by this cpu           deadlock   -EBUSY       -EBUSY
> 
> Then no need for bpf_disable_instrumentation() in rhtab.
> params.trylock_irqsoff is a compile time constant in the fast path,
> like insecure_elasticity. The other rhashtable users pay nothing.
> 
> The diff leaves one more bug: rhashtable_insert_rehash() calls
> kvmalloc(GFP_ATOMIC). That's not ok in NMI.
> 
> Something like this (compile tested only):
> 
> diff --git a/include/linux/rhashtable-types.h b/include/linux/rhashtable-types.h
> index 3576b8f..a5c4e69 100644
> --- a/include/linux/rhashtable-types.h
> +++ b/include/linux/rhashtable-types.h
> @@ -52,6 +52,8 @@ typedef int (*rht_obj_cmpfn_t)(struct rhashtable_compare_arg *arg,
>   * @min_size: Minimum size while shrinking
>   * @insecure_elasticity: Set to true to disable chain length checks
>   * @automatic_shrinking: Enable automatic shrinking of tables
> + * @trylock_irqsoff: With irqs disabled insert and remove don't spin on
> + *		     the bucket lock and return -EBUSY
>   * @hashfn: Hash function (default: jhash2 if !(key_len % 4), or jhash)
>   * @obj_hashfn: Function to hash object
>   * @obj_cmpfn: Function to compare key with object
> @@ -65,6 +67,7 @@ struct rhashtable_params {
>  	u16			min_size;
>  	bool			insecure_elasticity;
>  	bool			automatic_shrinking;
> +	bool			trylock_irqsoff;
>  	rht_hashfn_t		hashfn;
>  	rht_obj_hashfn_t	obj_hashfn;
>  	rht_obj_cmpfn_t		obj_cmpfn;
> diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
> index 70dac92..ba2c594 100644
> --- a/include/linux/rhashtable.h
> +++ b/include/linux/rhashtable.h
> @@ -339,6 +339,33 @@ static inline unsigned long rht_lock(struct bucket_table *tbl,
>  	return rht_lock_nested(tbl, bkt, 0);
>  }
> 
> +/*
> + * The bucket lock is held with irqs disabled. A caller with irqs disabled
> + * may run inside the locked section of this cpu (NMI, kprobe, tracepoint).
> + * It cannot spin.
> + */
> +static inline bool rht_lock_or_busy(struct bucket_table *tbl,
> +				    struct rhash_lock_head __rcu **bkt,
> +				    const struct rhashtable_params params,
> +				    unsigned long *flags)
> +	__cond_acquires(true, __bitlock(0, bkt))
> +{
> +	if (!params.trylock_irqsoff || !irqs_disabled()) {
> +		*flags = rht_lock(tbl, bkt);
> +		return true;
> +	}
> +	/* bit_spin_trylock() always succeeds on UP */
> +	if (!IS_ENABLED(CONFIG_SMP))
> +		return false;
> +	local_irq_save(*flags);
> +	if (!bit_spin_trylock(0, (unsigned long *)bkt)) {
> +		local_irq_restore(*flags);
> +		return false;
> +	}
> +	lock_acquire_exclusive(&tbl->dep_map, 0, 1, NULL, _THIS_IP_);
> +	return true;
> +}
> +
>  static inline void rht_unlock(struct bucket_table *tbl,
>  			      struct rhash_lock_head __rcu **bkt,
>  			      unsigned long flags)
> @@ -785,7 +812,9 @@ static __always_inline void *__rhashtable_insert_fast(
>  	if (!bkt)
>  		goto out;
>  	pprev = NULL;
> -	flags = rht_lock(tbl, bkt);
> +	data = ERR_PTR(-EBUSY);
> +	if (!rht_lock_or_busy(tbl, bkt, params, &flags))
> +		goto out;
> 
>  	if (unlikely(rcu_access_pointer(tbl->future_tbl))) {
>  slow_path:
> @@ -1066,7 +1095,8 @@ static __always_inline int __rhashtable_remove_fast_one(
>  	if (!bkt)
>  		return -ENOENT;
>  	pprev = NULL;
> -	flags = rht_lock(tbl, bkt);
> +	if (!rht_lock_or_busy(tbl, bkt, params, &flags))
> +		return -EBUSY;
> 
>  	rht_for_each_from(he, rht_ptr(bkt, tbl, hash), tbl, hash) {
>  		struct rhlist_head *list;
> @@ -1149,6 +1179,7 @@ static __always_inline int __rhashtable_remove_fast(
>  	 */
>  	while ((err = __rhashtable_remove_fast_one(ht, tbl, obj, params,
>  						   rhlist)) &&
> +	       err != -EBUSY &&
>  	       (tbl = rht_dereference_rcu(tbl->future_tbl, ht)))
>  		;
> 
> diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
> index 6e21154..edc7572 100644
> --- a/kernel/bpf/hashtab.c
> +++ b/kernel/bpf/hashtab.c
> @@ -2983,6 +2983,7 @@ struct bpf_rhtab {
>  static const struct rhashtable_params rhtab_params = {
>  	.head_offset = offsetof(struct rhtab_elem, node),
>  	.key_offset  = offsetof(struct rhtab_elem, data),
> +	.trylock_irqsoff = true,
>  };
> 
>  static inline void *rhtab_elem_value(struct rhtab_elem *l, u32 key_size)
> @@ -3011,6 +3012,7 @@ static const struct rhashtable_params rhtab_params_long = {
>  	.head_offset = offsetof(struct rhtab_elem, node),
>  	.key_offset  = offsetof(struct rhtab_elem, data),
>  	.key_len     = sizeof(long),
> +	.trylock_irqsoff = true,
>  	.hashfn      = rhtab_hashfn_long,
>  	.obj_cmpfn   = rhtab_key_cmp_long,
>  };
> @@ -3143,21 +3145,11 @@ 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.
> -	 */
> -	bpf_disable_instrumentation();
> -
>  	if (rhtab->map.key_size == sizeof(long))
>  		err = rhashtable_remove_fast(&rhtab->ht, &elem->node, rhtab_params_long);
>  	else
>  		err = rhashtable_remove_fast(&rhtab->ht, &elem->node, rhtab_params);
> 
> -	bpf_enable_instrumentation();
> -
>  	if (err)
>  		return err;
> 
> @@ -3268,16 +3260,11 @@ 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))
>  		tmp = rhashtable_lookup_get_insert_fast(&rhtab->ht, &elem->node, rhtab_params_long);
>  	else
>  		tmp = rhashtable_lookup_get_insert_fast(&rhtab->ht, &elem->node, rhtab_params);
> 
> -	bpf_enable_instrumentation();
> -
>  	if (tmp) {
>  		bpf_mem_cache_free(&rhtab->ma, elem);
>  		if (IS_ERR(tmp))
> diff --git a/lib/rhashtable.c b/lib/rhashtable.c
> index 500c45c..2dc13f0 100644
> --- a/lib/rhashtable.c
> +++ b/lib/rhashtable.c
> @@ -650,7 +650,8 @@ static void *rhashtable_try_insert(struct rhashtable *ht, const void *key,
>  		} else {
>  			bool inserted;
> 
> -			flags = rht_lock(tbl, bkt);
> +			if (!rht_lock_or_busy(tbl, bkt, ht->p, &flags))
> +				return ERR_PTR(-EBUSY);
>  			data = rhashtable_lookup_one(ht, bkt, tbl,
>  						     hash, key, obj);
>  			new_tbl = rhashtable_insert_one(ht, bkt, tbl,
> 
> Pls add the reproducer as a selftest in patch 2 and cc Herbert Xu
> on respin.
> 

The lookup infinite loop issue that bots reported looks real too,
we can use the parameter that Alexei added in the lookup as well to 
mitigate it for the price of possibly not finding the element that is
in the hashtable:

diff --git a/include/linux/rhashtable.h b/include/linux/rhashtable.h
index 70dac9214617..6eefdcfa5112 100644
--- a/include/linux/rhashtable.h
+++ b/include/linux/rhashtable.h
@@ -612,6 +612,18 @@ static __always_inline int rhashtable_compare(struct rhashtable_compare_arg *arg
                      params.key_len ? : ht->p.key_len);
 }

+/*
+ * The rehash links the last entry of a chain into the future table, then
+ * unlinks it from the chain. A walk between these two steps ends in the new
+ * chain and must retry. A caller with IRQs disabled can interrupt the rehash
+ * on this CPU, then the retry never ends. Such a caller does not retry, it
+ * finds the moved entries in the future table.
+ */
+static __always_inline bool rht_lookup_retry(const struct rhashtable_params params)
+{
+       return !params.trylock_irqsoff || !irqs_disabled();
+}
+
 /* Internal function, do not use. */
 static __always_inline struct rhash_head *__rhashtable_lookup(
        struct rhashtable *ht, const void *key,
@@ -644,7 +656,7 @@ static __always_inline struct rhash_head *__rhashtable_lookup(
                /* An object might have been moved to a different hash chain,
                 * while we walk along it - better check and retry.
                 */
-       } while (he != RHT_NULLS_MARKER(bkt));
+       } while (he != RHT_NULLS_MARKER(bkt) && rht_lookup_retry(params));

        /* Ensure we see any new tables. */
        smp_rmb();
diff --git a/lib/rhashtable.c b/lib/rhashtable.c
index 500c45cd1304..08eef1e2990f 100644
--- a/lib/rhashtable.c
+++ b/lib/rhashtable.c
@@ -274,7 +274,12 @@ static int rhashtable_rehash_one(struct rhashtable *ht,

        head = rht_ptr(new_tbl->buckets + new_hash, new_tbl, new_hash);

-       RCU_INIT_POINTER(entry->next, head);
+       /*
+        * A lookup that does not retry can walk into new_tbl through this
+        * pointer. Release it, so that the lookup then sees new_tbl in the
+        * future_tbl list.
+        */
+       rcu_assign_pointer(entry->next, head);

        rht_assign_unlock(new_tbl, &new_tbl->buckets[new_hash], entry, flags);
> pw-bot: cr