From: Kumar Kartikeya Dwivedi <memxor@gmail.com>
To: bpf@vger.kernel.org
Cc: Alexei Starovoitov <ast@kernel.org>,
Andrii Nakryiko <andrii@kernel.org>,
Daniel Borkmann <daniel@iogearbox.net>,
Eduard Zingerman <eddyz87@gmail.com>,
Emil Tsalapatis <emil@etsalapatis.com>, Tejun Heo <tj@kernel.org>,
kkd@meta.com, kernel-team@meta.com
Subject: [PATCH bpf-next v2 04/18] bpf: Track backtracking stack slots with bitmaps
Date: Thu, 24 Sep 2026 10:25:40 +0200 [thread overview]
Message-ID: <20260924082607.2695649-5-memxor@gmail.com> (raw)
In-Reply-To: <20260924082607.2695649-1-memxor@gmail.com>
Precision backtracking keeps the stack slots that still need a precise
mark in one u64 per frame, which ties it to frames of at most 64 slots.
Turn the per-frame masks into bitmaps sized by MAX_BPF_STACK_SLOTS and
use the bitmap helpers for setting, clearing, testing and iterating
them. The formatting helper takes a bitmap and the leftover-slot bug
reports print the formatted slot list instead of a hex mask.
mark_reg_stack_read() collected zero spills in a u64 of its own before
handing it to the backtracker; it now counts them and revisits the
range to mark each slot, which drops the only remaining mask-typed
entry point.
No functional change.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
include/linux/bpf_verifier.h | 13 +++-----
kernel/bpf/backtrack.c | 65 ++++++++++++++++++++++--------------
kernel/bpf/verifier.c | 15 ++++++---
3 files changed, 54 insertions(+), 39 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 1d80f7a4f26d..4b69737e1d42 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -898,7 +898,7 @@ struct backtrack_state {
struct bpf_verifier_env *env;
u32 frame;
u32 reg_masks[MAX_CALL_FRAMES];
- u64 stack_masks[MAX_CALL_FRAMES];
+ unsigned long stack_masks[MAX_CALL_FRAMES][BITS_TO_LONGS(MAX_BPF_STACK_SLOTS)];
u8 stack_arg_masks[MAX_CALL_FRAMES];
};
@@ -1356,12 +1356,7 @@ static inline void bpf_bt_set_frame_reg(struct backtrack_state *bt, u32 frame, u
static inline void bpf_bt_set_frame_slot(struct backtrack_state *bt, u32 frame, u32 slot)
{
- bt->stack_masks[frame] |= 1ull << slot;
-}
-
-static inline void bpf_bt_set_frame_slot_mask(struct backtrack_state *bt, u32 frame, u64 mask)
-{
- bt->stack_masks[frame] |= mask;
+ __set_bit(slot, bt->stack_masks[frame]);
}
static inline void bt_set_frame_stack_arg_slot(struct backtrack_state *bt, u32 frame, u32 slot)
@@ -1376,7 +1371,7 @@ static inline bool bt_is_frame_reg_set(struct backtrack_state *bt, u32 frame, u3
static inline bool bt_is_frame_slot_set(struct backtrack_state *bt, u32 frame, u32 slot)
{
- return bt->stack_masks[frame] & (1ull << slot);
+ return test_bit(slot, bt->stack_masks[frame]);
}
bool bpf_map_is_rdonly(const struct bpf_map *map);
@@ -1577,7 +1572,7 @@ struct bpf_subprog_info *bpf_find_containing_subprog(struct bpf_verifier_env *en
const char *bpf_subprog_name(const struct bpf_verifier_env *env, int subprog);
int bpf_jmp_offset(struct bpf_insn *insn);
struct bpf_iarray *bpf_insn_successors(struct bpf_verifier_env *env, u32 idx);
-void bpf_fmt_stack_mask(char *buf, ssize_t buf_sz, u64 stack_mask);
+void bpf_fmt_stack_mask(char *buf, ssize_t buf_sz, const unsigned long *stack_mask);
bool bpf_subprog_is_global(const struct bpf_verifier_env *env, int subprog);
/* Kinds of member a by-value struct or union may be composed of. */
diff --git a/kernel/bpf/backtrack.c b/kernel/bpf/backtrack.c
index 06630acd0d1f..0e38b9575328 100644
--- a/kernel/bpf/backtrack.c
+++ b/kernel/bpf/backtrack.c
@@ -129,13 +129,26 @@ static inline void bt_reset(struct backtrack_state *bt)
bt->env = env;
}
-static inline u32 bt_empty(struct backtrack_state *bt)
+static inline bool bt_frame_stack_empty(struct backtrack_state *bt, u32 frame)
{
- u64 mask = 0;
+ return bitmap_empty(bt->stack_masks[frame], MAX_BPF_STACK_SLOTS);
+}
+
+static inline bool bt_stack_empty(struct backtrack_state *bt)
+{
+ return bt_frame_stack_empty(bt, bt->frame);
+}
+
+static inline bool bt_empty(struct backtrack_state *bt)
+{
+ u32 mask = 0;
int i;
- for (i = 0; i <= bt->frame; i++)
- mask |= bt->reg_masks[i] | bt->stack_masks[i] | bt->stack_arg_masks[i];
+ for (i = 0; i <= bt->frame; i++) {
+ mask |= bt->reg_masks[i] | bt->stack_arg_masks[i];
+ if (!bt_frame_stack_empty(bt, i))
+ return false;
+ }
return mask == 0;
}
@@ -187,7 +200,7 @@ static inline void bt_clear_reg(struct backtrack_state *bt, u32 reg)
static inline void bt_clear_frame_slot(struct backtrack_state *bt, u32 frame, u32 slot)
{
- bt->stack_masks[frame] &= ~(1ull << slot);
+ __clear_bit(slot, bt->stack_masks[frame]);
}
static inline u32 bt_frame_reg_mask(struct backtrack_state *bt, u32 frame)
@@ -200,14 +213,14 @@ static inline u32 bt_reg_mask(struct backtrack_state *bt)
return bt->reg_masks[bt->frame];
}
-static inline u64 bt_frame_stack_mask(struct backtrack_state *bt, u32 frame)
+static inline unsigned long *bt_frame_stack_mask(struct backtrack_state *bt, u32 frame)
{
return bt->stack_masks[frame];
}
-static inline u64 bt_stack_mask(struct backtrack_state *bt)
+static inline unsigned long *bt_stack_mask(struct backtrack_state *bt)
{
- return bt->stack_masks[bt->frame];
+ return bt_frame_stack_mask(bt, bt->frame);
}
static inline u8 bt_stack_arg_mask(struct backtrack_state *bt)
@@ -239,17 +252,16 @@ static void fmt_reg_mask(char *buf, ssize_t buf_sz, u32 reg_mask)
break;
}
}
-/* format stack slots bitmask, e.g., "-8,-24,-40" for 0x15 mask */
-void bpf_fmt_stack_mask(char *buf, ssize_t buf_sz, u64 stack_mask)
+
+/* format stack slots bitmask, e.g., "-8,-24,-40" for slots 0, 2 and 4 */
+void bpf_fmt_stack_mask(char *buf, ssize_t buf_sz, const unsigned long *stack_mask)
{
- DECLARE_BITMAP(mask, 64);
bool first = true;
int i, n;
buf[0] = '\0';
- bitmap_from_u64(mask, stack_mask);
- for_each_set_bit(i, mask, 64) {
+ for_each_set_bit(i, stack_mask, MAX_BPF_STACK_SLOTS) {
n = snprintf(buf, buf_sz, "%s%d", first ? "" : ",", -(i + 1) * 8);
first = false;
buf += n;
@@ -461,10 +473,11 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
/* we are now tracking register spills correctly,
* so any instance of leftover slots is a bug
*/
- if (bt_stack_mask(bt) != 0) {
- verifier_bug(env,
- "static subprog leftover stack slots %llx",
- bt_stack_mask(bt));
+ if (!bt_stack_empty(bt)) {
+ bpf_fmt_stack_mask(env->tmp_str_buf, TMP_STR_BUF_LEN,
+ bt_stack_mask(bt));
+ verifier_bug(env, "static subprog leftover stack slots %s",
+ env->tmp_str_buf);
return -EFAULT;
}
/* propagate r1-r5 to the caller */
@@ -497,9 +510,11 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
bt_reg_mask(bt));
return -EFAULT;
}
- if (bt_stack_mask(bt) != 0) {
- verifier_bug(env, "callback leftover stack slots %llx",
- bt_stack_mask(bt));
+ if (!bt_stack_empty(bt)) {
+ bpf_fmt_stack_mask(env->tmp_str_buf, TMP_STR_BUF_LEN,
+ bt_stack_mask(bt));
+ verifier_bug(env, "callback leftover stack slots %s",
+ env->tmp_str_buf);
return -EFAULT;
}
/* clear r1-r5 in callback subprog's mask */
@@ -881,7 +896,7 @@ int bpf_mark_chain_precision(struct bpf_verifier_env *env,
if (st->curframe == 0 &&
st->frame[0]->subprogno > 0 &&
st->frame[0]->callsite == BPF_MAIN_FUNC &&
- bt_stack_mask(bt) == 0 &&
+ bt_stack_empty(bt) &&
(bt_reg_mask(bt) & ~BPF_REGMASK_ARGS) == 0) {
bitmap_from_u64(mask, bt_reg_mask(bt));
for_each_set_bit(i, mask, 32) {
@@ -895,8 +910,9 @@ int bpf_mark_chain_precision(struct bpf_verifier_env *env,
return 0;
}
- verifier_bug(env, "backtracking func entry subprog %d reg_mask %x stack_mask %llx",
- st->frame[0]->subprogno, bt_reg_mask(bt), bt_stack_mask(bt));
+ bpf_fmt_stack_mask(env->tmp_str_buf, TMP_STR_BUF_LEN, bt_stack_mask(bt));
+ verifier_bug(env, "backtracking func entry subprog %d reg_mask %x stack_mask %s",
+ st->frame[0]->subprogno, bt_reg_mask(bt), env->tmp_str_buf);
return -EFAULT;
}
@@ -957,8 +973,7 @@ int bpf_mark_chain_precision(struct bpf_verifier_env *env,
}
}
- bitmap_from_u64(mask, bt_frame_stack_mask(bt, fr));
- for_each_set_bit(i, mask, 64) {
+ for_each_set_bit(i, bt_frame_stack_mask(bt, fr), MAX_BPF_STACK_SLOTS) {
if (verifier_bug_if(i >= bpf_stack_nr_slots(func),
env, "stack slot %d, total slots %d",
i, bpf_stack_nr_slots(func)))
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 4ce187002333..6e2db8e5de2a 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3931,10 +3931,9 @@ static int mark_reg_stack_read(struct bpf_verifier_env *env,
{
struct bpf_verifier_state *vstate = env->cur_state;
struct bpf_func_state *state = vstate->frame[vstate->curframe];
- u64 zero_spill_mask = 0;
int i, slot, spi;
u8 *stype;
- int zeros = 0;
+ int zeros = 0, zero_spills = 0;
for (i = min_off; i < max_off; i++) {
slot = -i - 1;
@@ -3947,7 +3946,7 @@ static int mark_reg_stack_read(struct bpf_verifier_env *env,
}
if (stype[slot % BPF_REG_SIZE] == STACK_SPILL &&
bpf_register_is_null(&bpf_stack_slot(ptr_state, spi)->spilled_ptr)) {
- zero_spill_mask |= 1ull << spi;
+ zero_spills++;
zeros++;
continue;
}
@@ -3958,8 +3957,14 @@ static int mark_reg_stack_read(struct bpf_verifier_env *env,
* so the whole register == const_zero.
*/
__mark_reg_const_zero(env, &state->regs[dst_regno]);
- if (zero_spill_mask) {
- bpf_bt_set_frame_slot_mask(&env->bt, ptr_state->frameno, zero_spill_mask);
+ if (zero_spills) {
+ for (i = min_off; i < max_off; i++) {
+ slot = -i - 1;
+ spi = slot / BPF_REG_SIZE;
+ stype = bpf_stack_slot(ptr_state, spi)->slot_type;
+ if (stype[slot % BPF_REG_SIZE] == STACK_SPILL)
+ bpf_bt_set_frame_slot(&env->bt, ptr_state->frameno, spi);
+ }
return mark_chain_precision_batch(env, env->cur_state);
}
} else {
--
2.53.0
next prev parent reply other threads:[~2026-09-24 8:26 UTC|newest]
Thread overview: 34+ messages / expand[flat|nested] mbox.gz Atom feed top
2026-09-24 8:25 [PATCH bpf-next v2 00/18] Raise BPF program stack size to 2KiB Kumar Kartikeya Dwivedi
2026-09-24 8:25 ` [PATCH bpf-next v2 01/18] bpf: Add accessors for verifier stack slots Kumar Kartikeya Dwivedi
2026-09-24 8:25 ` [PATCH bpf-next v2 02/18] bpf: Widen the stack slot index in the jump history Kumar Kartikeya Dwivedi
2026-09-24 8:25 ` [PATCH bpf-next v2 03/18] bpf: Store linked registers in the jump history as an array Kumar Kartikeya Dwivedi
2026-09-24 8:25 ` Kumar Kartikeya Dwivedi [this message]
2026-09-24 8:25 ` [PATCH bpf-next v2 05/18] bpf: Track scratched stack slots with a bitmap Kumar Kartikeya Dwivedi
2026-09-24 8:25 ` [PATCH bpf-next v2 06/18] bpf: Treat unknown-size stack reads as reaching the frame top Kumar Kartikeya Dwivedi
2026-09-24 8:25 ` [PATCH bpf-next v2 07/18] bpf: Size liveness stack masks by the stack each frame uses Kumar Kartikeya Dwivedi
2026-09-24 15:12 ` Alexei Starovoitov
2026-09-24 8:25 ` [PATCH bpf-next v2 08/18] bpf: Grow the verifier id scratch on demand Kumar Kartikeya Dwivedi
2026-09-24 9:13 ` bot+bpf-ci
2026-09-24 9:55 ` Kumar Kartikeya Dwivedi
2026-09-24 8:25 ` [PATCH bpf-next v2 09/18] selftests/bpf: Cover the tail call caller stack depth limit Kumar Kartikeya Dwivedi
2026-09-24 8:25 ` [PATCH bpf-next v2 10/18] selftests/bpf: Check that narrow stack stores define no slot Kumar Kartikeya Dwivedi
2026-09-24 8:25 ` [PATCH bpf-next v2 11/18] selftests/bpf: Check liveness merge of masks with different widths Kumar Kartikeya Dwivedi
2026-09-24 8:25 ` [PATCH bpf-next v2 12/18] bpf: Size the per-frame verifier structures for a 2 KiB stack Kumar Kartikeya Dwivedi
2026-09-24 9:13 ` bot+bpf-ci
2026-09-24 9:56 ` Kumar Kartikeya Dwivedi
2026-09-24 8:25 ` [PATCH bpf-next v2 13/18] bpf: Bound program stack use by a per-program limit Kumar Kartikeya Dwivedi
2026-09-24 9:13 ` bot+bpf-ci
2026-09-24 9:56 ` Kumar Kartikeya Dwivedi
2026-09-24 8:25 ` [PATCH bpf-next v2 14/18] selftests/bpf: Add load conditions on the program stack limit Kumar Kartikeya Dwivedi
2026-09-24 8:25 ` [PATCH bpf-next v2 15/18] selftests/bpf: Give the 512-byte stack boundary tests a 2 KiB twin Kumar Kartikeya Dwivedi
2026-09-24 9:13 ` bot+bpf-ci
2026-09-24 9:56 ` Kumar Kartikeya Dwivedi
2026-09-24 8:25 ` [PATCH bpf-next v2 16/18] bpf, x86: Allow programs 2 KiB of stack Kumar Kartikeya Dwivedi
2026-09-24 9:13 ` bot+bpf-ci
2026-09-24 9:57 ` Kumar Kartikeya Dwivedi
2026-09-24 8:25 ` [PATCH bpf-next v2 17/18] bpf, arm64: " Kumar Kartikeya Dwivedi
2026-09-24 9:00 ` bot+bpf-ci
2026-09-24 9:57 ` Kumar Kartikeya Dwivedi
2026-09-24 8:25 ` [PATCH bpf-next v2 18/18] selftests/bpf: Test the 2 KiB stack budget Kumar Kartikeya Dwivedi
2026-09-24 9:13 ` bot+bpf-ci
2026-09-24 9:58 ` Kumar Kartikeya Dwivedi
Reply instructions:
You may reply publicly to this message via plain-text email
using any one of the following methods:
* Save the following mbox file, import it into your mail client,
and reply-to-all from there: mbox
Avoid top-posting and favor interleaved quoting:
https://en.wikipedia.org/wiki/Posting_style#Interleaved_style
* Reply using the --to, --cc, and --in-reply-to
switches of git-send-email(1):
git send-email \
--in-reply-to=20260924082607.2695649-5-memxor@gmail.com \
--to=memxor@gmail.com \
--cc=andrii@kernel.org \
--cc=ast@kernel.org \
--cc=bpf@vger.kernel.org \
--cc=daniel@iogearbox.net \
--cc=eddyz87@gmail.com \
--cc=emil@etsalapatis.com \
--cc=kernel-team@meta.com \
--cc=kkd@meta.com \
--cc=tj@kernel.org \
/path/to/YOUR_REPLY
https://kernel.org/pub/software/scm/git/docs/git-send-email.html
* If your mail client supports setting the In-Reply-To header
via mailto: links, try the mailto: link
Be sure your reply has a Subject: header at the top and a blank line
before the message body.
This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox