bpf: Don't use percpu_counter for the htab element count in NMI
PATCH 1/1 bpf: Don't use percpu_counter for the htab element count in NMI
BPF programs attached to perf events run in NMI and can update a non-preallocated hash map. For large maps the element count is a percpu_counter, whose slow path takes fbc->lock with raw_spin_lock_irqsave(). That does not exclude NMIs, so an NMI that interrupts a holder of the lock and then updates the same map spins on it forever:
WARNING: inconsistent lock state
inconsistent {INITIAL USE} -> {IN-NMI} usage. kstress/261 [HC2[2]:SC0[0]:HE0:SE1] takes:
(key#5){....}-{2:2}, at: _raw_spin_lock_irqsave+0x18/0x30 {INITIAL USE} state was registered at:
percpu_counter_add_batch+0xd8/0x160
alloc_htab_elem+0x408/0x480
htab_map_update_elem+0x1e8/0x6a0is_map_full() is affected too, as __percpu_counter_compare() falls back to percpu_counter_sum(), which takes the same lock.
Count the elements added or removed in NMI in htab->count, which is otherwise unused for such maps, and add it to the percpu_counter where that is read. In NMI is_map_full() only reads the percpu_counter, so the limit is approximate by up to PERCPU_COUNTER_BATCH * num_online_cpus() there.
--- kernel/bpf/hashtab.c | 26 ++++++++++++++++++++------ 1 file changed, 20 insertions(+), 6 deletions(-)
kernel/bpf/hashtab.c +20 -6
@@ -95,7 +95,8 @@ struct bpf_htab { };struct htab_elem *__percpu *extra_elems;/* number of elements in non-preallocated hashtable are kept -* in either pcount or count +* in either pcount or count; with pcount, those added or removed +* in NMI are in count, see is_map_full() */ struct percpu_counter pcount;atomic_t count;
@@ -1160,11 +1161,23 @@ static void htab_put_fd_value(struct bpf_htab *htab, struct htab_elem *l) } } +/* +* With use_percpu_counter the elements added or removed in NMI are counted in +* @count, as percpu_counter takes a spinlock that the NMI could have +* interrupted the holder of. +*/ static bool is_map_full (struct bpf_htab *htab) { -if (htab->use_percpu_counter) -return __percpu_counter_compare (&htab->pcount, htab->map.max_entries, +if (htab->use_percpu_counter) { +/* percpu_counter_sum() takes that lock, so only read it in NMI */ +if (in_nmi ()) +return percpu_counter_read (&htab->pcount) + +atomic_read (&htab->count) >= htab->map.max_entries; +return __percpu_counter_compare (&htab->pcount, + (s64 )htab->map.max_entries - +atomic_read (&htab->count),PERCPU_COUNTER_BATCH ) >=0 ; + }return atomic_read (&htab->count) >= htab->map.max_entries; }
@@ -1172,7 +1185,7 @@ static void inc_elem_count(struct bpf_htab *htab) {bpf_map_inc_elem_count (&htab->map); -if (htab->use_percpu_counter) +if (htab->use_percpu_counter && !in_nmi ())percpu_counter_add_batch (&htab->pcount,1 ,PERCPU_COUNTER_BATCH );else atomic_inc (&htab->count);
@@ -1182,7 +1195,7 @@ static void dec_elem_count(struct bpf_htab *htab) {bpf_map_dec_elem_count (&htab->map); -if (htab->use_percpu_counter) +if (htab->use_percpu_counter && !in_nmi ())percpu_counter_add_batch (&htab->pcount,-1 ,PERCPU_COUNTER_BATCH );else atomic_dec (&htab->count);
@@ -2578,7 +2591,8 @@ static u64 htab_map_mem_usage(const struct bpf_map *map)#define LLIST_NODE_SZ sizeof(struct llist_node) num_entries = htab->use_percpu_counter ? -percpu_counter_sum (&htab->pcount) : +percpu_counter_sum (&htab->pcount) + +atomic_read (&htab->count) :atomic_read (&htab->count); usage += (htab->elem_size +LLIST_NODE_SZ ) * num_entries;if (percpu) {
base-commit: b71326388a8a24674846c1d8d3b6dd831d9843a9
Signature · 1 line
2.53.0-Meta
[email protected]
AI reviewThank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [High] bpf: 32-bit atomic_t htab->count overflow with 64-bit percpu_counter --
Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [High] bpf: 32-bit atomic_t htab->count overflow with 64-bit percpu_counter --
commit 9bfb61b87bddde697a9661d8440f11f7f1dcd019
Author: Puranjay Mohan <[email protected]>
bpf: Don't use percpu_counter for the htab element count in NMI
This patch avoids deadlocking on the percpu_counter spinlock in NMI context by routing NMI element count updates for non-preallocated hash maps into htab->count instead of htab->pcount, and combining the two counters in is_map_full() and htab_map_mem_usage().
Quoted 59 lines
kernel/bpf/hashtab.c +18
-5@@ -95,7 +95,8 @@ struct bpf_htab { };struct htab_elem *__percpu *extra_elems;/* number of elements in non-preallocated hashtable are kept -* in either pcount or count +* in either pcount or count; with pcount, those added or removed +* in NMI are in count, see is_map_full() */ struct percpu_counter pcount;atomic_t count;@@ -1160,11 +1161,23 @@ static void htab_put_fd_value(struct bpf_htab *htab, struct htab_elem *l) } } +/* +* With use_percpu_counter the elements added or removed in NMI are counted in +* @count, as percpu_counter takes a spinlock that the NMI could have +* interrupted the holder of. +*/ static bool is_map_full (struct bpf_htab *htab) { -if (htab->use_percpu_counter) -return __percpu_counter_compare (&htab->pcount, htab->map.max_entries, +if (htab->use_percpu_counter) { +/* percpu_counter_sum() takes that lock, so only read it in NMI */ +if (in_nmi ()) +return percpu_counter_read (&htab->pcount) + +atomic_read (&htab->count) >= htab->map.max_entries; +return __percpu_counter_compare (&htab->pcount, + (s64 )htab->map.max_entries - +atomic_read (&htab->count),PERCPU_COUNTER_BATCH ) >=0 ; + }return atomic_read (&htab->count) >= htab->map.max_entries; }@@ -1172,7 +1185,7 @@ static void inc_elem_count(struct bpf_htab *htab) {bpf_map_inc_elem_count (&htab->map); -if (htab->use_percpu_counter) +if (htab->use_percpu_counter && !in_nmi ())percpu_counter_add_batch (&htab->pcount,1 ,PERCPU_COUNTER_BATCH );else atomic_inc (&htab->count);@@ -1182,7 +1195,7 @@ static void dec_elem_count(struct bpf_htab *htab) {bpf_map_dec_elem_count (&htab->map); -if (htab->use_percpu_counter) +if (htab->use_percpu_counter && !in_nmi ())percpu_counter_add_batch (&htab->pcount,-1 ,PERCPU_COUNTER_BATCH );else atomic_dec (&htab->count);
kernel/bpf/hashtab.c static u64 htab_map_mem_usage(const struct bpf_map *map) · line 2598
Quoted 9 lines
kernel/bpf/hashtab.c +2
-1@@ -2578,7 +2591,8 @@ static u64 htab_map_mem_usage(const struct bpf_map *map)#define LLIST_NODE_SZ sizeof(struct llist_node) num_entries = htab->use_percpu_counter ? -percpu_counter_sum (&htab->pcount) : +percpu_counter_sum (&htab->pcount) + +atomic_read (&htab->count) :atomic_read (&htab->count); usage += (htab->elem_size +LLIST_NODE_SZ ) * num_entries;if (percpu) {
[Severity: High]
Can htab->count overflow or underflow when elements are inserted in NMI context and deleted outside NMI context (or vice versa)?
When htab->use_percpu_counter is enabled, inc_elem_count() and dec_elem_count() choose between htab->pcount and htab->count based on in_nmi() at the time of each operation, and htab->count is never folded into htab->pcount.
If a perf_event BPF program running in NMI inserts elements via htab_map_update_elem() -> alloc_htab_elem() -> inc_elem_count() (which calls atomic_inc(&htab->count)) and userspace or a non-NMI BPF program later deletes those elements via free_htab_elem() -> dec_elem_count() (which calls percpu_counter_add_batch(&htab->pcount, -1, ...)), the two counters diverge without bound over the lifetime of the map.
Because htab->pcount is a 64-bit signed counter (s64) while htab->count is a 32-bit signed atomic_t, after 2^31 net cross-context insert/delete cycles, htab->count wraps between INT_MAX and INT_MIN while htab->pcount continues counting in 64-bit arithmetic.
When atomic_read(&htab->count) is sign-extended to s64 and combined with htab->pcount in is_map_full() and htab_map_mem_usage(), wrapping htab->count shifts the computed occupancy by +/- 2^32. That either disables the max_entries limit in is_map_full() and underflows num_entries in htab_map_mem_usage(), or causes is_map_full() to permanently return true (-E2BIG) even when the map is empty.
Should htab->count be atomic64_t (or folded into htab->pcount in the non-NMI paths via atomic_xchg(&htab->count, 0)) so the two counters cannot wrap at different widths?
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=1
Quoted 48 lines · Puranjay Mohan
BPF programs attached to perf events run in NMI and can update a non-preallocated hash map. For large maps the element count is a
percpu_counter, whose slow path takesfbc->lockwithraw_spin_lock_irqsave(). That does not exclude NMIs, so an NMI that interrupts a holder of the lock and then updates the same map spins on it forever:WARNING: inconsistent lock state
inconsistent {INITIAL USE} -> {IN-NMI} usage. kstress/261 [HC2[2]:SC0[0]:HE0:SE1] takes:
(key#5){....}-{2:2}, at:_raw_spin_lock_irqsave+0x18/0x30{INITIAL USE} state was registered at:percpu_counter_add_batch+0xd8/0x160 alloc_htab_elem+0x408/0x480 htab_map_update_elem+0x1e8/0x6a0
is_map_full()is affected too, as__percpu_counter_compare()falls back topercpu_counter_sum(), which takes the same lock.Count the elements added or removed in NMI in
htab->count, which is otherwise unused for such maps, and add it to thepercpu_counterwhere that is read. In NMIis_map_full()only reads thepercpu_counter, so the limit is approximate by up toPERCPU_COUNTER_BATCH*num_online_cpus()there.Fixes 86fe28f7692d ("bpf: Optimize element count in non-preallocated hash map.")Signed-off-by Puranjay Mohan <[email protected]>--- kernel/bpf/hashtab.c | 26 ++++++++++++++++++++------ 1 file changed, 20 insertions(+), 6 deletions(-)kernel/bpf/hashtab.c +2
-1@@ -95,7 +95,8 @@ struct bpf_htab { };struct htab_elem *__percpu *extra_elems;/* number of elements in non-preallocated hashtable are kept -* in either pcount or count +* in either pcount or count; with pcount, those added or removed +* in NMI are in count, see is_map_full() */ struct percpu_counter pcount;atomic_t count;@@ -1160,11 +1161,23 @@ static void htab_put_fd_value(struct bpf_htab *htab, struct htab_elem *l) } }
kernel/bpf/hashtab.c static void htab_put_fd_value(struct bpf_htab *htab, struct htab_elem *l) · line 1166
Quoted 10 lines
kernel/bpf/hashtab.c +5
-2+/* +* With use_percpu_counter the elements added or removed in NMI are counted in +* @count, as percpu_counter takes a spinlock that the NMI could have +* interrupted the holder of. +*/ static bool is_map_full (struct bpf_htab *htab) { -if (htab->use_percpu_counter) - return __percpu_counter_compare(&htab->pcount, htab->map.max_entries,
To protect bucket locks in rhashtable from re-entrance from NMI we use bpf_disable_instrumentation()/bpf_enable_instrumentation(), will it work here? It looks like a more common solution for hashtab.
Quoted 43 lines
kernel/bpf/hashtab.c +13
-3+if (htab->use_percpu_counter) { +/* percpu_counter_sum() takes that lock, so only read it in NMI */ +if (in_nmi ()) +return percpu_counter_read (&htab->pcount) + +atomic_read (&htab->count) >= htab->map.max_entries; +return __percpu_counter_compare (&htab->pcount, + (s64 )htab->map.max_entries - +atomic_read (&htab->count),PERCPU_COUNTER_BATCH ) >=0 ; + }return atomic_read (&htab->count) >= htab->map.max_entries; }@@ -1172,7 +1185,7 @@ static void inc_elem_count(struct bpf_htab *htab) {bpf_map_inc_elem_count (&htab->map); -if (htab->use_percpu_counter) +if (htab->use_percpu_counter && !in_nmi ())percpu_counter_add_batch (&htab->pcount,1 ,PERCPU_COUNTER_BATCH );else atomic_inc (&htab->count);@@ -1182,7 +1195,7 @@ static void dec_elem_count(struct bpf_htab *htab) {bpf_map_dec_elem_count (&htab->map); -if (htab->use_percpu_counter) +if (htab->use_percpu_counter && !in_nmi ())percpu_counter_add_batch (&htab->pcount,-1 ,PERCPU_COUNTER_BATCH );else atomic_dec (&htab->count);@@ -2578,7 +2591,8 @@ static u64 htab_map_mem_usage(const struct bpf_map *map)#define LLIST_NODE_SZ sizeof(struct llist_node) num_entries = htab->use_percpu_counter ? -percpu_counter_sum (&htab->pcount) : +percpu_counter_sum (&htab->pcount) + +atomic_read (&htab->count) :atomic_read (&htab->count); usage += (htab->elem_size +LLIST_NODE_SZ ) * num_entries;if (percpu) {base-commit:
b71326388a8a24674846c1d8d3b6dd831d9843a9
Quoted 5 lines · Puranjay Mohan
Count the elements added or removed in NMI in
htab->count, which is otherwise unused for such maps, and add it to thepercpu_counterwhere that is read. In NMIis_map_full()only reads thepercpu_counter, so the limit is approximate by up toPERCPU_COUNTER_BATCH*num_online_cpus()there.
Not only NMI. queued_spin_lock_slowpath() calls trace_contention_end() with the lock already held. When percpu_counter_add_batch() contends on fbc->lock, a tp_btf/contention_end prog that updates the same map sees the same this_cpu counter, goes to the slow path too and spins on fbc->lock that its own cpu holds. in_nmi() is false there.
can we drop percpu_counter from htab instead ? map.elem_count is already a lockless per-cpu count of the same elements. htab->count can follow it in steps of the batch and is_map_full() can sum elem_count when it gets close to max_entries. That is exact in NMI as well. Then no need for pcount, in_nmi() checks and adding up two counters.
Something like this (compile tested only):
include/linux/bpf.h +2 -0
@@ -3041,6 +3041,8 @@ static inline void bpf_map_dec_elem_count(struct bpf_map *map)this_cpu_dec (*map->elem_count); } +s64 bpf_map_sum_elem_count (const struct bpf_map *map); +extern int sysctl_unprivileged_bpf_disabled;bool bpf_token_capable (const struct bpf_token *token,int cap);
kernel/bpf/hashtab.c +26 -38
120 lines not on this page · raw message
pw-bot: cr