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

[sashiko-bot@kernel.org]

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