Skip to contentSkip to conversation

bpf: Drop percpu_counter from the htab element count

PATCH Applied Puranjay Mohan 4 participants 4 messages Oct 21 – Oct 30

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

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/0x6a0

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

Fixes 86fe28f7692d ("bpf: Optimize element count in non-preallocated hash map.")

---

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
index 580f89c450b55..dc805e095fe86 100644
@@ -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
#1 lore raw
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 1 line

bpf: Drop percpu_counter from 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
index bf78e09f4d51..6e2115477cb9 100644

[ ... ]

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() needs htab->max_entries - cur_number_of_elems to be more than
+ * batch * nr_cpu_ids for the percpu counter to be faster than atomic_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
+ * and is_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
- * between percpu_counter and atomic_t.
+ * between the percpu counter and atomic_t. The batch has to be a power of 2. */
#define PERCPU_COUNTER_BATCH 32

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 -5
 static 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

#2 lore raw
Quoted 152 lines · On Wed, Oct 21, 2026 at 8:23 PM <[email protected]> wrote:
Quoted 2 lines

bpf: Drop percpu_counter from 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
index bf78e09f4d51..6e2115477cb9 100644

[ ... ]

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() needs htab->max_entries - cur_number_of_elems to be more than
+ * batch * nr_cpu_ids for the percpu counter to be faster than atomic_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
+ * and is_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
- * between percpu_counter and atomic_t.
+ * between the percpu counter and atomic_t. The batch has to be a power of 2. */
#define PERCPU_COUNTER_BATCH 32

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

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

#3 lore raw
In reply to Puranjay Mohan
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 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:

[...]

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