bpf: Drop percpu_counter from the htab element count
PATCH v2 1/1 bpf: Drop percpu_counter from the htab element count
The element count of a large non-preallocated hash map is a percpu_counter, whose slow path takes fbc->lock with raw_spin_lock_irqsave(). That is not safe against BPF programs that run while the lock is held or contended: NMI programs and, as queued_spin_lock_slowpath() calls trace_contention_end() with the lock already held, programs attached to the contention_end tracepoint. If such a program updates the same map it spins on the lock its own CPU holds:
WARNING: possible recursive locking detected cend/250 is trying to acquire lock:
(key#5){....}-{2:2}, at: _raw_spin_lock_irqsave+0x18/0x30 but task is already holding lock:
(key#5){....}-{2:2}, at: _raw_spin_lock_irqsave+0x18/0x30
percpu_counter_add_batch+0xd8/0x160
alloc_htab_elem+0x408/0x480
htab_map_update_elem+0x1e8/0x6a0
bpf_prog_7a29a1ae68aedf07_cend+0x14c/0x1f8
__bpf_trace_contention_end+0x14/0x20
queued_spin_lock_slowpath+0x2e8/0x468
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.
map.elem_count already is a lockless per-cpu count of the same elements. Make htab->count follow it in steps of PERCPU_COUNTER_BATCH and let is_map_full() sum elem_count once count is within nr_cpu_ids * batch of max_entries. Each cpu's elem_count is ahead of count by less than the batch, so that is exact, in NMI as well.
---
v1: https://lore.kernel.org/all/[email protected]/
Changes in v2:
- Drop percpu_counter and make htab->count follow map.elem_count instead, which also covers contention_end programs (Alexei)
--- include/linux/bpf.h | 2 ++ kernel/bpf/hashtab.c | 64 ++++++++++++++++++-------------------------- 2 files changed, 28 insertions(+), 38 deletions(-)
include/linux/bpf.h +2 -0
@@ -3042,6 +3042,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
base-commit: b116ac6087541d3d98031e786adbe9c733cd6df3
Signature · 1 line
2.53.0-Meta
[email protected]
AI reviewTL;DR: - On 32-bit kernels, torn s64 elem_count reads or NMI races may make is_map_full() wrong: spurious -E2BIG, or inserts past max_entries - Two comment-style nits
Quoted 1 line
bpf: Drop
percpu_counterfrom the htab element count
TL;DR:
- On 32-bit kernels, torn s64 elem_count reads or NMI races may make is_map_full() wrong: spurious -E2BIG, or inserts past max_entries
- Two comment-style nits
Quoted 4 lines
kernel/bpf/hashtab.c +0
-0
[ ... ]
Quoted 4 lines
kernel/bpf/hashtab.c +0
-0@@ -94,10 +94,10 @@ struct bpf_htab {struct bpf_lru lru; };struct htab_elem *__percpu *extra_elems;
kernel/bpf/hashtab.c struct bpf_htab { · line 103
Quoted 10 lines
kernel/bpf/hashtab.c +3
-3-/* number of elements in non-preallocated hashtable are kept -* in either pcount or count +/* number of elements in non-preallocated hashtable. With +* use_percpu_counter it only follows map.elem_count in steps of +* PERCPU_COUNTER_BATCH, see is_map_full() */ -struct percpu_counter pcount;atomic_t count;bool use_percpu_counter;bool has_hash;
this isn't a bug, but this multi-line comment still has text on the opening /* line. Since the comment is being rewritten anyway, could the /* go on its own line, as is preferred under kernel/bpf/?
[ ... ]
Quoted 1 line
kernel/bpf/hashtab.c +0
-0@@ -739,29 +739,20 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)
[ ... ]
Quoted 5 lines
+/*
is_map_full()needshtab->max_entries-cur_number_of_elemsto be more than
+ * batch *nr_cpu_idsfor the percpu counter to be faster thanatomic_t. In
+ * practice the average bpf hash map size is 10k. With batch count of 32 a 10k
+ * hash map on a system with 64 cpus can be filled up to 80%:
* 10k - 8k > 32 _batch_ * 64 _cpus_
Quoted 8 lines
- * and
__percpu_counter_compare()will still be fast. At that point hash map
+ * andis_map_full()will still be fast. At that point hash map
* collisions will dominate its performance anyway. Assume that hash map filled
* to 50+% isn't going to be O(1) and use the following formula to choose
- * betweenpercpu_counterandatomic_t.
+ * between the percpu counter andatomic_t. The batch has to be a power of 2. */
#definePERCPU_COUNTER_BATCH32
this isn't a bug, but the same applies to the rewritten comment above PERCPU_COUNTER_BATCH, which also starts its text on the opening /* line. Could it use the /* on its own line style as well?
[ ... ]
Quoted 6 lines
kernel/bpf/hashtab.c +0
-2@@ -1162,30 +1151,33 @@ static void htab_put_fd_value(struct bpf_htab *htab, struct htab_elem *l)static bool is_map_full (struct bpf_htab *htab) { -if (htab->use_percpu_counter) - return __percpu_counter_compare(&htab->pcount, htab->map.max_entries,
kernel/bpf/hashtab.c static void htab_put_fd_value(struct bpf_htab *htab, struct htab_elem *l) · line 1161
Quoted 10 lines
kernel/bpf/hashtab.c +7
-2- PERCPU_COUNTER_BATCH) >= 0; -return atomic_read (&htab->count) >= htab->map.max_entries; +s64 count =atomic_read (&htab->count); + +/* each cpu's elem_count is ahead of count by less than the batch */ +if (htab->use_percpu_counter && + count + nr_cpu_ids *PERCPU_COUNTER_BATCH >= htab->map.max_entries) + count =bpf_map_sum_elem_count (&htab->map); +return count >= htab->map.max_entries; }
Can a torn read of the per-cpu s64 elem_count on 32-bit kernels make is_map_full() return the wrong answer here?
bpf_map_sum_elem_count() does READ_ONCE(*pcount) on each s64, which on 32-bit is split into two 32-bit loads (see include/asm-generic/rwonce.h). A per-cpu elem_count crosses zero regularly, since an element is often freed on a different CPU from the one that allocated it.
A 0 -> -1 update rewrites both halves:
0x00000000_00000000 -> 0xffffffff_ffffffff
If another CPU in htab_map_update_elem() -> alloc_htab_elem() -> is_map_full() reads the counter in the middle of that update, it can see 0x00000000_ffffffff (+4294967295). Then "count >= htab->map.max_entries" is true and alloc_htab_elem() returns -E2BIG for a map that is not full.
A -1 -> 0 update can read as -4294967296, which lets an insert go past max_entries.
The old slow path was percpu_counter_sum(), which reads s32 per-cpu counters and fbc->count under fbc->lock. Near max_entries fbc->count is a large positive value, so a torn read could not affect that decision. Before this patch, torn elem_count reads only affected the iterator statistics.
Quoted 18 lines
kernel/bpf/hashtab.c +4
-5static void inc_elem_count (struct bpf_htab *htab) { -bpf_map_inc_elem_count (&htab->map); +s64 cnt =this_cpu_inc_return (*htab->map.elem_count); -if (htab->use_percpu_counter) -percpu_counter_add_batch (&htab->pcount,1 ,PERCPU_COUNTER_BATCH ); -else +if (!htab->use_percpu_counter)atomic_inc (&htab->count); +else if (!(cnt & (PERCPU_COUNTER_BATCH -1 ))) +atomic_add (PERCPU_COUNTER_BATCH , &htab->count); }static void dec_elem_count (struct bpf_htab *htab) { -bpf_map_dec_elem_count (&htab->map);
kernel/bpf/hashtab.c static void htab_put_fd_value(struct bpf_htab *htab, struct htab_elem *l) · line 1181
Quoted 10 lines
kernel/bpf/hashtab.c +4
-3+s64 cnt =this_cpu_dec_return (*htab->map.elem_count); -if (htab->use_percpu_counter) -percpu_counter_add_batch (&htab->pcount,-1 ,PERCPU_COUNTER_BATCH ); -else +if (!htab->use_percpu_counter)atomic_dec (&htab->count); +else if (!((cnt +1 ) & (PERCPU_COUNTER_BATCH -1 ))) +atomic_sub (PERCPU_COUNTER_BATCH , &htab->count); }
The same concern applies to inc_elem_count() and dec_elem_count(). this_cpu_inc_return() on the s64 per-cpu elem_count uses this_cpu_add_return_8, which x86 only defines under CONFIG_X86_64. Elsewhere it falls back to this_cpu_generic_add_return(), a raw_local_irq_save() read-modify-write that an NMI can interrupt.
On x86-32, if an NMI perf_event program updates another bucket of the same map in that window, it can see the same return value as the interrupted context. If that value is a multiple of PERCPU_COUNTER_BATCH, both contexts run:
atomic_add(PERCPU_COUNTER_BATCH, &htab->count);
(or both run atomic_sub() on the dec side). htab->count then stays 32 off from the sum of 32 * floor(elem_count / 32) permanently, and the error grows over time.
That breaks the "each cpu's elem_count is ahead of count by less than the batch" invariant that the fast path in is_map_full() relies on. A downward drift lets the fast path return false while the map is already full.
The old x86-32 fast path used this_cpu_try_cmpxchg() on s32 counters (HAVE_CMPXCHG_LOCAL), which an NMI cannot split.
This seems to contradict the commit message statement "so that is exact, in NMI as well" for 32-bit kernels. Should the batched elem_count scheme be limited to configurations with native 64-bit per-cpu ops, or should the summing side handle torn values?
---
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/39658415298
Quoted 152 lines · On Wed, Oct 21, 2026 at 8:23 PM <[email protected]> wrote:
Quoted 2 lines
bpf: Drop
percpu_counterfrom the htab element countTL;DR:
- On 32-bit kernels, torn s64elem_countreads or NMI races may makeis_map_full()wrong: spurious-E2BIG, or inserts pastmax_entries
- Two comment-style nitsQuoted 4 lines
kernel/bpf/hashtab.c +0
-0[ ... ]
Quoted 4 lines
kernel/bpf/hashtab.c +0
-0@@ -94,10 +94,10 @@ struct bpf_htab {struct bpf_lru lru; };struct htab_elem *__percpu *extra_elems;kernel/bpf/hashtab.c struct bpf_htab { · line 103
Quoted 10 lines
kernel/bpf/hashtab.c +3
-3-/* number of elements in non-preallocated hashtable are kept -* in either pcount or count +/* number of elements in non-preallocated hashtable. With +* use_percpu_counter it only follows map.elem_count in steps of +* PERCPU_COUNTER_BATCH, see is_map_full() */ -struct percpu_counter pcount;atomic_t count;bool use_percpu_counter;bool has_hash;this isn't a bug, but this multi-line comment still has text on the opening /* line. Since the comment is being rewritten anyway, could the /* go on its own line, as is preferred under
kernel/bpf/?[ ... ]
Quoted 1 line
kernel/bpf/hashtab.c +0
-0@@ -739,29 +739,20 @@ static struct bpf_map *htab_map_alloc(union bpf_attr *attr)[ ... ]
Quoted 5 lines
+/*
is_map_full()needshtab->max_entries-cur_number_of_elemsto be more than
+ * batch *nr_cpu_idsfor the percpu counter to be faster thanatomic_t. In
+ * practice the average bpf hash map size is 10k. With batch count of 32 a 10k
+ * hash map on a system with 64 cpus can be filled up to 80%:
* 10k - 8k > 32 _batch_ * 64 _cpus_Quoted 8 lines
- * and
__percpu_counter_compare()will still be fast. At that point hash map
+ * andis_map_full()will still be fast. At that point hash map
* collisions will dominate its performance anyway. Assume that hash map filled
* to 50+% isn't going to be O(1) and use the following formula to choose
- * betweenpercpu_counterandatomic_t.
+ * between the percpu counter andatomic_t. The batch has to be a power of 2. */
#definePERCPU_COUNTER_BATCH32this isn't a bug, but the same applies to the rewritten comment above
PERCPU_COUNTER_BATCH, which also starts its text on the opening /* line. Could it use the /* on its own line style as well?[ ... ]
Quoted 6 lines
kernel/bpf/hashtab.c +0
-2@@ -1162,30 +1151,33 @@ static void htab_put_fd_value(struct bpf_htab *htab, struct htab_elem *l)static bool is_map_full (struct bpf_htab *htab) { -if (htab->use_percpu_counter) - return __percpu_counter_compare(&htab->pcount, htab->map.max_entries,kernel/bpf/hashtab.c static void htab_put_fd_value(struct bpf_htab *htab, struct htab_elem *l) · line 1161
Quoted 10 lines
kernel/bpf/hashtab.c +7
-2- PERCPU_COUNTER_BATCH) >= 0; -return atomic_read (&htab->count) >= htab->map.max_entries; +s64 count =atomic_read (&htab->count); + +/* each cpu's elem_count is ahead of count by less than the batch */ +if (htab->use_percpu_counter && + count + nr_cpu_ids *PERCPU_COUNTER_BATCH >= htab->map.max_entries) + count =bpf_map_sum_elem_count (&htab->map); +return count >= htab->map.max_entries; }Can a torn read of the per-cpu s64
elem_counton 32-bit kernels makeis_map_full()return the wrong answer here?
bpf_map_sum_elem_count()doesREAD_ONCE(*pcount)on each s64, which on 32-bit is split into two 32-bit loads (seeinclude/asm-generic/rwonce.h). A per-cpuelem_countcrosses zero regularly, since an element is often freed on a different CPU from the one that allocated it.A 0 -> -1 update rewrites both halves:
0x00000000_00000000 -> 0xffffffff_ffffffffIf another CPU in
htab_map_update_elem()->alloc_htab_elem()->is_map_full()reads the counter in the middle of that update, it can see 0x00000000_ffffffff (+4294967295). Then "count >=htab->map.max_entries" is true andalloc_htab_elem()returns-E2BIGfor a map that is not full.A -1 -> 0 update can read as -4294967296, which lets an insert go past
max_entries.The old slow path was
percpu_counter_sum(), which reads s32 per-cpu counters andfbc->countunderfbc->lock. Nearmax_entriesfbc->countis a large positive value, so a torn read could not affect that decision. Before this patch, tornelem_countreads only affected the iterator statistics.Quoted 18 lines
kernel/bpf/hashtab.c +4
-5static void inc_elem_count (struct bpf_htab *htab) { -bpf_map_inc_elem_count (&htab->map); +s64 cnt =this_cpu_inc_return (*htab->map.elem_count); -if (htab->use_percpu_counter) -percpu_counter_add_batch (&htab->pcount,1 ,PERCPU_COUNTER_BATCH ); -else +if (!htab->use_percpu_counter)atomic_inc (&htab->count); +else if (!(cnt & (PERCPU_COUNTER_BATCH -1 ))) +atomic_add (PERCPU_COUNTER_BATCH , &htab->count); }static void dec_elem_count (struct bpf_htab *htab) { -bpf_map_dec_elem_count (&htab->map);kernel/bpf/hashtab.c static void htab_put_fd_value(struct bpf_htab *htab, struct htab_elem *l) · line 1181
Quoted 10 lines
kernel/bpf/hashtab.c +4
-3+s64 cnt =this_cpu_dec_return (*htab->map.elem_count); -if (htab->use_percpu_counter) -percpu_counter_add_batch (&htab->pcount,-1 ,PERCPU_COUNTER_BATCH ); -else +if (!htab->use_percpu_counter)atomic_dec (&htab->count); +else if (!((cnt +1 ) & (PERCPU_COUNTER_BATCH -1 ))) +atomic_sub (PERCPU_COUNTER_BATCH , &htab->count); }The same concern applies to
inc_elem_count()anddec_elem_count().this_cpu_inc_return()on the s64 per-cpuelem_countusesthis_cpu_add_return_8, which x86 only defines underCONFIG_X86_64. Elsewhere it falls back tothis_cpu_generic_add_return(), araw_local_irq_save()read-modify-write that an NMI can interrupt.On x86-32, if an NMI
perf_eventprogram updates another bucket of the same map in that window, it can see the same return value as the interrupted context. If that value is a multiple ofPERCPU_COUNTER_BATCH, both contexts run:atomic_add(PERCPU_COUNTER_BATCH, &htab->count);(or both run
atomic_sub()on the dec side).htab->countthen stays 32 off from the sum of 32 *floor(elem_count / 32)permanently, and the error grows over time.That breaks the "each cpu's
elem_countis ahead of count by less than the batch" invariant that the fast path inis_map_full()relies on. A downward drift lets the fast path return false while the map is already full.
Quoted 7 lines
The old x86-32 fast path used
this_cpu_try_cmpxchg()on s32 counters (HAVE_CMPXCHG_LOCAL), which an NMI cannot split.This seems to contradict the commit message statement "so that is exact, in NMI as well" for 32-bit kernels. Should the batched
elem_countscheme be limited to configurations with native 64-bit per-cpu ops, or should the summing side handle torn values?
We don't really care about 32-bit kernels in this code path, so I will not do any change to this unless someone else really thinks it is necessary.
This patch was applied to bpf/bpf.git (master) by Alexei Starovoitov <[email protected]>:
Hello:
This patch was applied to bpf/bpf.git (master)
by Alexei Starovoitov <[email protected]>:
Quoted 9 lines · On Wed, 21 Oct 2026 11:51:16 -0700 you wrote:
The element count of a large non-preallocated hash map is a
percpu_counter, whose slow path takesfbc->lockwithraw_spin_lock_irqsave(). That is not safe against BPF programs that run while the lock is held or contended: NMI programs and, asqueued_spin_lock_slowpath()callstrace_contention_end()with the lock already held, programs attached to thecontention_endtracepoint. If such a program updates the same map it spins on the lock its own CPU holds:[...]
Here is the summary with links:
- [bpf-next,v2] bpf: Drop percpu_counter from the htab element count
https://git.kernel.org/bpf/bpf/c/1cd28b5354ab
You are awesome, thank you!
Signature · 2 lines
Deet-doot-dot, I am a bot. https://korg.docs.kernel.org/patchwork/pwbot.html