bpf: Size the per-frame verifier structures for a 2 KiB stack

The verifier keeps a few structures whose size follows the deepest
frame a program may have: the backtracking and scratched-slot bitmaps,
the jump history slot index and the clamp of the liveness masks. They
are all expressed through MAX_BPF_STACK_SLOTS, which derives from
MAX_BPF_STACK, the frame size of the interpreter.

Introduce MAX_BPF_STACK_JIT, the stack budget a program may get on a
JIT that can lay out frames of any size, and derive those structures
from it so that a frame may be as deep as that budget. Nothing grants
the budget yet, so no program verifies differently; the only visible
change is that the liveness log prints a whole-frame read up to the new
depth, so the three selftests matching such reads are updated.

The spill tracker of the liveness analysis keeps a table entry per
instruction and tracked slot, so it follows more than the 64 slots of a
MAX_BPF_STACK frame only while that table stays within what 64 slots
need for the largest program; a subprog of a million instructions keeps
64, one of a quarter million may track all 256. This bounds the table
at its old worst case of 640 MiB instead of letting a single deep store
push it past what kvmalloc() serves.

The backtracking and scratched-slot bitmaps grow from one to four
words per frame, a fixed few hundred bytes per verifier environment.
tmp_str_buf, which formats a frame's slot list for the log, grows from
320 to 1408 bytes so that all 256 slots still fit, and the log's line
buffer from 1 to 2 KiB so that a line built from it is not cut; the
environment stays within its 64 KiB allocation. The liveness masks are
only as wide as the stack a frame uses, so most frames cost the same as
before; a frame that is read as a whole, through a pointer of unknown
offset or by bpf_loop() with two callbacks, now carries masks of eight
words, 192 bytes per instruction per frame instead of 48. Measured over
the 5075 selftest programs, that is 0.2% of the total peak verifier
memory: strobemeta_bpf_loop and pyperf600_bpf_loop grow by 11% (1.2 MiB
and 0.6 MiB), a few dozen small programs by 40 to 100 KiB each,
everything else is unchanged. The next patch bounds such reads by the
program's budget, so this cost is only paid once a JIT grants it.

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

1 files changed, 15 insertions, 2 deletions

diff --git a/kernel/bpf/liveness.c b/kernel/bpf/liveness.c
index 1d83a4cf6ec5..25e95387e0e1 100644
--- a/kernel/bpf/liveness.c
+++ b/kernel/bpf/liveness.c
@@ -15,7 +15,7 @@
  * Half-slot 0 covers [fp-4, fp), half-slot 1 covers [fp-8, fp-4), and so on,
  * hence FRAME_HALF_SPIS - 1 is the deepest half-slot a frame can have.
  */
-#define FRAME_HALF_SPIS		(MAX_BPF_STACK / BPF_HALF_REG_SIZE)
+#define FRAME_HALF_SPIS		(MAX_BPF_STACK_JIT / BPF_HALF_REG_SIZE)
 #define FRAME_MAX_WORDS		BITS_TO_LONGS(FRAME_HALF_SPIS)
 
 /* Masks tracked for each instruction of a frame */
@@ -1022,6 +1022,19 @@ static void arg_padd(struct arg_track *at, s64 delta)
 }
 
 /*
+ * Slots the spill tracker may follow for a subprog of @len instructions
+ * without its per-instruction tables costing more than they could for the
+ * largest program while every frame stayed within MAX_BPF_STACK: as many
+ * entries as 64 slots need for BPF_COMPLEXITY_LIMIT_INSNS instructions.
+ */
+static u32 spill_slots_affordable(int len)
+{
+	u32 base = MAX_BPF_STACK / BPF_REG_SIZE;
+
+	return max_t(u32, base, base * BPF_COMPLEXITY_LIMIT_INSNS / len);
+}
+
+/*
  * Number of 8-byte spill slots to track for the instructions in [@start, @end):
  * the 64 slots of a MAX_BPF_STACK frame, which the tracker has always
  * followed, or the deepest 8-byte stack access made directly through R10 when
@@ -1793,7 +1806,7 @@ static int compute_subprog_args(struct bpf_verifier_env *env,
 	int end = env->subprog_info[subprog + 1].start;
 	int po_end = env->subprog_info[subprog + 1].postorder_start;
 	int len = end - start;
-	u32 nslots = subprog_spill_slots(env, start, end);
+	u32 nslots = min(subprog_spill_slots(env, start, end), spill_slots_affordable(len));
 	struct arg_track (*at_in)[MAX_AT_TRACK_REGS] = NULL;
 	struct arg_track at_out[MAX_AT_TRACK_REGS];
 	struct arg_track *at_stack_in = NULL;