Skip to contentSkip to conversation

bpf: Don't use percpu_counter for the htab element count in NMI

PATCH In review Puranjay Mohan 4 participants 4 messages Oct 20

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

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

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

Fixes 86fe28f7692d ("bpf: Optimize element count in non-preallocated hash map.")
---
 kernel/bpf/hashtab.c | 26 ++++++++++++++++++++------
 1 file changed, 20 insertions(+), 6 deletions(-)
kernel/bpf/hashtab.c +20 -6
index bf78e09f4d518..7a27479c46dc5 100644
@@ -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
#1 lore raw
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 --

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
index bf78e09f4d518..7a27479c46dc5 100644
@@ -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
#2 lore raw
In reply to Puranjay Mohan
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 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/0x6a0

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

Fixes 86fe28f7692d ("bpf: Optimize element count in non-preallocated hash map.")
---
 kernel/bpf/hashtab.c | 26 ++++++++++++++++++++------
 1 file changed, 20 insertions(+), 6 deletions(-)
kernel/bpf/hashtab.c +2 -1
index bf78e09f4d518..7a27479c46dc5 100644
@@ -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

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

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
index 7750df9..b298b89 100644
@@ -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