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 an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.