bpf: Size liveness stack masks by the stack each frame uses

Stack liveness tracks three masks of 4-byte stack slots - may_read,
must_write and live_before - for every instruction of every frame of
every function instance. Each mask used to be a fixed 128-bit spis_t,
wide enough for the deepest frame MAX_BPF_STACK allows, so an
instruction paid 48 bytes per frame no matter how little stack the frame
actually touched. These per instruction arrays are the largest liveness
allocation: a 40k instruction program spends ~2 MiB on each frame array.
Sizing them for a larger stack budget would multiply that cost for every
program, while most frames use a fraction of the budget.

Replace the fixed masks with a variable width bitmap array per
(instance, frame). struct frame_masks holds the width shared by all of
its masks in @words plus a flat unsigned long array, where mask @kind of
the instruction at relative index @i lives at
&bits[(i * FM_MASK_CNT + kind) * words]. An array starts at the width
the first recorded half-slot needs (minimum one word, that is 256 bytes
of stack with 64-bit words) and is reallocated into a wider stride once
a deeper half-slot shows up. Only the marking functions widen an array,
and they all run during the static analysis before do_check(), so no
verification time path can move one.

The marking API now takes an inclusive half-slot range, which is what
record_stack_access_off() computed anyway, and clamps the upper end to
the deepest half-slot a frame can have. An access below the stack bound
is rejected by the main verifier pass later; liveness only has to stay
inside the masks. A range that covers no whole half-slot, as a byte
store at fp-1 produces, marks nothing.

A "read everything" mark, used for calls that are neither helpers nor
kfuncs and for pointers whose offset or frame identity was lost, widens
the array to the maximum width and sets every bit: recorded at a
narrower width it would lose the half-slots a later widening adds, and
no write can cancel it as no write covers the whole frame. A half-slot
past the width of the masks was never read by the frame and is never
live.

merge_instances() may see a different width on each side, so it widens
dst to cover src and counts a word only dst has as zero on the src
side, which unions into may_read as a no-op and intersects must_write
to empty, never claiming a write that did not happen.

The rest is mechanical: update_insn() propagates live_before word by
word over the array's width (all instructions of one array share it,
hence so do an instruction's successors), is_live_before() answers
false past the width, and the use:/def: log printing iterates up to the
width.

Liveness results are unchanged. A half-slot only ever gets a bit from a
recorded access and recording one widens the array to cover it, so every
bit the fixed masks could hold still fits. Frames whose deepest recorded
half-slot fits in a single word now cost 24 bytes per instruction per
frame instead of 48.

The spill tracker that feeds the analysis had the same limit built in: it
followed 64 slots, fp-8 to fp-512, per subprog, and a fill from a deeper
slot returned an imprecise pointer, so every later access through it
counted as a read of the whole stack of every frame. Let it follow the
deepest 8-byte access a subprog makes directly through R10 when that
reaches past those 64 slots, which is how spills and fills are compiled,
and keep the count with the per-callsite snapshot a callee uses to fill
from its caller's frame. Programs within 512 bytes are tracked exactly as
before; a program spilling deeper stays precise.

Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
Signed-off-by: Alexei Starovoitov <ast@kernel.org>
Link: https://patch.msgid.link/20260924165740.2146806-8-memxor@gmail.com

1 files changed, 2 insertions, 48 deletions

diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index e64cfb3fe675..d3c31105a3ac 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -254,52 +254,6 @@ enum bpf_stack_slot_type {
 /* 4-byte stack slot granularity for liveness analysis */
 #define BPF_HALF_REG_SIZE	4
 #define STACK_SLOT_SZ		4
-#define STACK_SLOTS		(MAX_BPF_STACK / BPF_HALF_REG_SIZE)	/* 128 */
-
-typedef struct {
-	u64 v[2];
-} spis_t;
-
-#define SPIS_ZERO	((spis_t){})
-#define SPIS_ALL	((spis_t){{ U64_MAX, U64_MAX }})
-
-static inline bool spis_is_zero(spis_t s)
-{
-	return s.v[0] == 0 && s.v[1] == 0;
-}
-
-static inline bool spis_equal(spis_t a, spis_t b)
-{
-	return a.v[0] == b.v[0] && a.v[1] == b.v[1];
-}
-
-static inline spis_t spis_or(spis_t a, spis_t b)
-{
-	return (spis_t){{ a.v[0] | b.v[0], a.v[1] | b.v[1] }};
-}
-
-static inline spis_t spis_and(spis_t a, spis_t b)
-{
-	return (spis_t){{ a.v[0] & b.v[0], a.v[1] & b.v[1] }};
-}
-
-static inline spis_t spis_not(spis_t s)
-{
-	return (spis_t){{ ~s.v[0], ~s.v[1] }};
-}
-
-static inline bool spis_test_bit(spis_t s, u32 slot)
-{
-	return s.v[slot / 64] & BIT_ULL(slot % 64);
-}
-
-static inline void spis_or_range(spis_t *mask, u32 lo, u32 hi)
-{
-	u32 w;
-
-	for (w = lo; w <= hi && w < STACK_SLOTS; w++)
-		mask->v[w / 64] |= BIT_ULL(w % 64);
-}
 
 #define BPF_REGMASK_ARGS ((1 << BPF_REG_1) | (1 << BPF_REG_2) | \
 			  (1 << BPF_REG_3) | (1 << BPF_REG_4) | \
@@ -1047,8 +1001,8 @@ struct bpf_verifier_env {
 	} cfg;
 	struct backtrack_state bt;
 	struct bpf_jmp_history_entry *cur_hist_ent;
-	/* Per-callsite copy of parent's converged at_stack_in for cross-frame fills. */
-	struct arg_track **callsite_at_stack;
+	/* Per-callsite snapshot of the parent's tracked spill slots for cross-frame fills. */
+	struct spill_snapshot **callsite_at_stack;
 	u32 pass_cnt; /* number of times do_check() was called */
 	u32 subprog_cnt;
 	/* number of instructions analyzed by the verifier */