Skip to contentSkip to conversation

Raise BPF program stack size to 2KiB

PATCH Superseded Kumar Kartikeya Dwivedi 4 participants 34 messages Sep 23

Subsystems (9)
Documentation x86 Kselftest BPF +5 more subsystems

v1 of 4 Superseded Latest is v4 →

lore
Share & tools
lore

Kumar Kartikeya Dwivedi

author maintainer
#0 lore raw

cover Raise BPF program stack size to 2KiB

BPF programs get 512 bytes of stack. This series raises that to 2 KiB on x86-64 and arm64. The budget covers a whole call chain, or each frame on a private stack, and a single function may use all of it. The interpreter, offloaded programs and the other JITs keep 512 bytes.

The x86-64 and arm64 JITs do not depend on 512-byte frames: both encode frame sizes in wide enough immediates, and on both a tail call pops the caller's frame and lands in the target's prologue before the target sets up its own.

The verifier needs several changes, however. Its bookkeeping assumes at most 64 slots per frame: the jump history and linked register records carry 6-bit slot indexes, backtracking and the scratched-slot log keep one u64 per frame, the id map is sized for 64 slots per frame, and liveness keeps three fixed 128-bit masks per instruction per frame. Growing all of this fourfold would make every program pay for stack limits that most program will not exercise. Therefore, some dynamicity is needed without blowing verifier memory usage out of proportion.

The series first removes these assumptions without changing what verifies (patches 1-8). The liveness masks become bitmaps as wide as the stack a frame actually uses, and the id scratch grows on demand. It then adds a per-program budget, bpf_prog_stack_limit(): 2 KiB when the program is JITed, not offloaded, and the JIT reports bpf_jit_supports_large_stack() along with tail calls from subprograms, and 512 bytes otherwise. Finally, it turns the budget on for x86-64 and arm64.

Tail calls need no separate limit. A tail call pops the frame that makes it, and the frames its callers leave behind are still limited to 256 bytes by the existing rule for tail calls from subprograms. Only the final program's frame in a tail call chain grows, from 512 bytes to 2 KiB, so the chain's worst-case kernel stack use grows from about 8.5 KiB to about 10 KiB. The budget does not depend on privilege: an unprivileged program cannot call other BPF functions, so its tail calls leave no frame behind and its worst case is a single 2 KiB frame.

Memory was measured as the peak kernel memory allocated during each BPF_PROG_LOAD, for all 5075 loadable selftest programs, against bpf-next at 79dc258c9392. "Total" is the sum of the per-program peaks. Two runs of one kernel agree to 0.01% in total; a handful of small programs differ by one 64 KiB allocation between runs, and those one-off jumps are left out of the per-program rows.

patches 1-8 whole series

  total                                  -0.72%        -0.51%
    4940 programs under 1 MiB            -0.32%        -0.14%
     116 programs of 1-16 MiB            -0.58%        +0.23%
      19 programs of 16 MiB or more      -1.10%        -1.05%

median program 0.0% 0.0%
programs growing by more than 5% 7 56
largest increase +16% +19%
largest decrease -5.0% -5.0%

The savings come from liveness: a frame within 256 bytes needs 24 bytes of masks per instruction instead of 48. The largest are pyperf600 (-5.2 MiB, -2.0%), pyperf180 (-3.2 MiB, -2.8%), pyperf100 (-2.8 MiB, -3.1%) and test_verif_scale2 (-1.0 MiB, -5.0%).

The increases have two causes:

* history: the jump history entry grows from 16 to 20 bytes, which penalizes loop-heavy programs. This is already present in patches 1-8.
* masks: a frame read as a whole through a pointer of unknown offset keeps liveness masks as wide as the 2 KiB budget. This appears only once the budget is raised.

The largest absolute increases for the whole series (peak in MiB):

  program                                   before  after   MiB      %  cause
  loop1/nested_loops                          17.6   19.2  +1.5    +9%  history
  strobemeta_bpf_loop/on_event                10.5   11.8  +1.3   +12%  masks
  verifier_loops1/jumps_out_rather_than_in     4.4    5.1  +0.7   +16%  history
  pyperf600_bpf_loop/on_event                  5.6    6.3  +0.7   +12%  masks
  pyperf600_nounroll/on_event                 80.3   80.9  +0.6    +1%  history
  strobemeta_nounroll2/on_event               44.5   45.1  +0.6    +1%  both
  strobemeta/on_event                        201.8  202.4  +0.5  +0.3%  history
  test_tcp_custom_syncookie                   10.8   11.2  +0.4    +4%  masks
  strobemeta_nounroll1/on_event               20.9   21.3  +0.4    +2%  both
  linked_list/global_list_push_pop_multiple    5.0    5.4  +0.3    +6%  history

The largest relative increases are small programs whose frame is read as a whole, each growing by 50 to 110 KiB: verifier_bitfield_write +15 to 19%, test_tc_tunnel +13 to 15% and dynptr_success +12%.

In terms of verification time, the changes are within margin of error.

For more details, please see the individual commits.

Kumar Kartikeya Dwivedi (18):
bpf: Add accessors for verifier stack slots
bpf: Widen the stack slot index in the jump history
bpf: Store linked registers in the jump history as an array
bpf: Track backtracking stack slots with bitmaps
bpf: Track scratched stack slots with a bitmap
bpf: Treat unknown-size stack reads as reaching the frame top
bpf: Size liveness stack masks by the stack each frame uses
bpf: Grow the verifier id scratch on demand selftests/bpf: Cover the tail call caller stack depth limit selftests/bpf: Check that narrow stack stores define no slot selftests/bpf: Check liveness merge of masks with different widths
bpf: Size the per-frame verifier structures for a 2 KiB stack
bpf: Bound program stack use by a per-program limit selftests/bpf: Add load conditions on the program stack limit selftests/bpf: Give the 512-byte stack boundary tests a 2 KiB twin bpf, x86: Allow programs 2 KiB of stack
bpf, arm64: Allow programs 2 KiB of stack selftests/bpf: Test the 2 KiB stack budget

 Documentation/bpf/bpf_design_QA.rst           |  10 +-
 arch/arm64/net/bpf_jit_comp.c                 |   5 +
 arch/x86/net/bpf_jit_comp.c                   |  12 +
 include/linux/bpf_verifier.h                  | 191 ++++-----
 include/linux/filter.h                        |   6 +
 kernel/bpf/backtrack.c                        |  97 +++--
 kernel/bpf/core.c                             |  13 +
 kernel/bpf/diagnostics.c                      |   6 +-
 kernel/bpf/liveness.c                         | 362 +++++++++++------
 kernel/bpf/log.c                              |  13 +-
 kernel/bpf/states.c                           | 130 +++---
 kernel/bpf/verifier.c                         | 315 ++++++++-------
 .../bpf/prog_tests/struct_ops_private_stack.c |  31 ++
 .../selftests/bpf/prog_tests/tailcalls.c      |  42 ++
 .../selftests/bpf/prog_tests/verifier.c       |   2 +
 .../selftests/bpf/progs/async_stack_depth.c   |  75 ++++
 tools/testing/selftests/bpf/progs/bpf_misc.h  |   3 +
 .../bpf/progs/struct_ops_private_stack_fail.c |  47 ++-
 .../progs/struct_ops_private_stack_large.c    |  51 +++
 .../bpf/progs/tailcall_large_stack.c          |  62 +++
 .../selftests/bpf/progs/test_global_func1.c   |  65 +++
 .../bpf/progs/test_global_func_deep_stack.c   |  33 +-
 .../bpf/progs/verifier_large_stack.c          | 377 ++++++++++++++++++
 .../selftests/bpf/progs/verifier_live_stack.c |  79 +++-
 .../selftests/bpf/progs/verifier_raw_stack.c  |  21 +
 .../selftests/bpf/progs/verifier_stack_ptr.c  |  53 +++
 .../selftests/bpf/progs/verifier_tailcall.c   |  57 +++
 .../selftests/bpf/progs/verifier_var_off.c    |  32 ++
 tools/testing/selftests/bpf/test_loader.c     |  24 ++
 tools/testing/selftests/bpf/testing_helpers.c |  41 ++
 tools/testing/selftests/bpf/testing_helpers.h |   1 +
 tools/testing/selftests/bpf/verifier/calls.c  | 122 ++++--
 32 files changed, 1883 insertions(+), 495 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/progs/struct_ops_private_stack_large.c
 create mode 100644 tools/testing/selftests/bpf/progs/tailcall_large_stack.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_large_stack.c

base-commit: 91f8613d95ad8cd99d8baf094806d1ef98bc6380

Signature · 1 line
2.53.0
author maintainer
#1 lore raw

PATCH 1/18 bpf: Add accessors for verifier stack slots

The verifier indexes a frame's stack state directly through state->stack[spi] and computes the number of tracked slots as allocated_stack / BPF_REG_SIZE in every file that touches stack slots. Route all of these through two helpers, bpf_stack_slot() and bpf_stack_nr_slots(), so the layout of the per-frame stack state is visible in one place and can change without touching every user. Both take a const frame: the slot accessor returns the slot through the frame's stack pointer, so read-only code such as the state printer can use it without giving up its qualifiers. Functions that look up the same slot repeatedly now fetch it once.

No functional change.

---
 include/linux/bpf_verifier.h |  25 ++++--
 kernel/bpf/backtrack.c       |  14 +--
 kernel/bpf/diagnostics.c     |   6 +-
 kernel/bpf/log.c             |  13 +--
 kernel/bpf/states.c          |  84 +++++++++---------
 kernel/bpf/verifier.c        | 163 +++++++++++++++++++----------------
 6 files changed, 166 insertions(+), 139 deletions(-)
include/linux/bpf_verifier.h +20 -5
index 92f528c45605..36e0c6b97533 100644
@@ -529,12 +529,27 @@ struct bpf_verifier_state {
 	u32 may_goto_depth;
 };
 
+/* Number of BPF_REG_SIZE stack slots tracked for the frame so far. */
+static inline u32 bpf_stack_nr_slots(const struct bpf_func_state *frame)
+{
+	return frame->allocated_stack / BPF_REG_SIZE;
+}
+
+/*
+ * Stack slot @spi of @frame, covering bytes [fp - (spi + 1) * 8, fp - spi * 8).
+ * The caller must ensure spi < bpf_stack_nr_slots(frame), see grow_stack_state().
+ */
+static inline struct bpf_stack_state *bpf_stack_slot(const struct bpf_func_state *frame, u32 spi)
+{
+	return &frame->stack[spi];
+}
+
 static inline struct bpf_reg_state *
 bpf_get_spilled_reg(int slot, struct bpf_func_state *frame, u32 mask)
 {
-	if (slot < frame->allocated_stack / BPF_REG_SIZE &&
-	    (1 << frame->stack[slot].slot_type[BPF_REG_SIZE - 1]) & mask)
-		return &frame->stack[slot].spilled_ptr;
+	if (slot < bpf_stack_nr_slots(frame) &&
+	    (1 << bpf_stack_slot(frame, slot)->slot_type[BPF_REG_SIZE - 1]) & mask)
+		return &bpf_stack_slot(frame, slot)->spilled_ptr;
 	return NULL;
 }
 
@@ -550,7 +565,7 @@ bpf_get_spilled_stack_arg(int slot, struct bpf_func_state *frame)
 /* Iterate over 'frame', setting 'reg' to either NULL or a spilled register. */
 #define bpf_for_each_spilled_reg(iter, frame, reg, mask)			\
 	for (iter = 0, reg = bpf_get_spilled_reg(iter, frame, mask);		\
-	     iter < frame->allocated_stack / BPF_REG_SIZE;		\
+	     iter < bpf_stack_nr_slots(frame);				\
 	     iter++, reg = bpf_get_spilled_reg(iter, frame, mask))
 
 /* Iterate over 'frame', setting 'reg' to either NULL or a spilled stack arg. */
@@ -575,7 +590,7 @@ bpf_get_spilled_stack_arg(int slot, struct bpf_func_state *frame)
 			bpf_for_each_spilled_reg(___j, __state, __reg, __mask) { \
 				if (!__reg)                              \
 					continue;                        \
-				__stack = &__state->stack[___j];         \
+				__stack = bpf_stack_slot(__state, ___j); \
 				(void)(__expr);                          \
 			}                                                \
 			__stack = NULL;                                  \
kernel/bpf/backtrack.c +7 -7
index 507a366dffa4..4bec7b94796b 100644
@@ -707,10 +707,10 @@ void bpf_mark_all_scalars_precise(struct bpf_verifier_env *env,
 						i, j);
 				}
 			}
-			for (j = 0; j < func->allocated_stack / BPF_REG_SIZE; j++) {
-				if (!bpf_is_spilled_reg(&func->stack[j]))
+			for (j = 0; j < bpf_stack_nr_slots(func); j++) {
+				if (!bpf_is_spilled_reg(bpf_stack_slot(func, j)))
 					continue;
-				reg = &func->stack[j].spilled_ptr;
+				reg = &bpf_stack_slot(func, j)->spilled_ptr;
 				if (reg->type != SCALAR_VALUE || reg->precise)
 					continue;
 				reg->precise = true;
@@ -946,16 +946,16 @@ 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) {
-				if (verifier_bug_if(i >= func->allocated_stack / BPF_REG_SIZE,
+				if (verifier_bug_if(i >= bpf_stack_nr_slots(func),
 						    env, "stack slot %d, total slots %d",
-						    i, func->allocated_stack / BPF_REG_SIZE))
+						    i, bpf_stack_nr_slots(func)))
 					return -EFAULT;
 
-				if (!bpf_is_spilled_scalar_reg(&func->stack[i])) {
+				if (!bpf_is_spilled_scalar_reg(bpf_stack_slot(func, i))) {
 					bt_clear_frame_slot(bt, fr, i);
 					continue;
 				}
-				reg = &func->stack[i].spilled_ptr;
+				reg = &bpf_stack_slot(func, i)->spilled_ptr;
 				if (reg->precise) {
 					bt_clear_frame_slot(bt, fr, i);
 				} else {
kernel/bpf/diagnostics.c +3 -3
index 5ecfa86ed49f..a8ed6130c137 100644
@@ -1600,9 +1600,9 @@ static struct bpf_reg_state *target_to_reg(struct bpf_verifier_env *env,
 			return NULL;
 		return &state->stack_arg_regs[target->stack_arg];
 	case BPF_DIAG_MOD_TARGET_STACK_SLOT:
-		if (target->spi >= state->allocated_stack / BPF_REG_SIZE)
+		if (target->spi >= bpf_stack_nr_slots(state))
 			return NULL;
-		return &state->stack[target->spi].spilled_ptr;
+		return &bpf_stack_slot(state, target->spi)->spilled_ptr;
 	default:
 		return NULL;
 	}
@@ -1618,7 +1618,7 @@ static bool reg_to_target(struct bpf_verifier_env *env, const struct bpf_reg_sta
 	for (frame = 0; frame <= vstate->curframe; frame++) {
 		struct bpf_func_state *state = vstate->frame[frame];
 		unsigned long start, end;
-		u32 nslots = state->allocated_stack / BPF_REG_SIZE;
+		u32 nslots = bpf_stack_nr_slots(state);
 		int spi;
 
 		start = (unsigned long)state->regs;
kernel/bpf/log.c +7 -6
index fb032dfdc0de..d850a7863d2e 100644
@@ -716,7 +716,8 @@ void print_verifier_state(struct bpf_verifier_env *env, const struct bpf_verifie
 		verbose(env, "=");
 		print_reg_state(env, state, reg);
 	}
-	for (i = 0; i < state->allocated_stack / BPF_REG_SIZE; i++) {
+	for (i = 0; i < bpf_stack_nr_slots(state); i++) {
+		struct bpf_stack_state *slot = bpf_stack_slot(state, i);
 		char types_buf[BPF_REG_SIZE + 1];
 		const char *sep = "";
 		bool valid = false;
@@ -727,7 +728,7 @@ void print_verifier_state(struct bpf_verifier_env *env, const struct bpf_verifie
 			continue;
 
 		for (j = 0; j < BPF_REG_SIZE; j++) {
-			slot_type = state->stack[i].slot_type[j];
+			slot_type = slot->slot_type[j];
 			if (slot_type != STACK_INVALID && slot_type != STACK_POISON)
 				valid = true;
 			types_buf[j] = slot_type_char[slot_type];
@@ -736,12 +737,12 @@ void print_verifier_state(struct bpf_verifier_env *env, const struct bpf_verifie
 		if (!valid)
 			continue;
 
-		reg = &state->stack[i].spilled_ptr;
-		switch (state->stack[i].slot_type[BPF_REG_SIZE - 1]) {
+		reg = &slot->spilled_ptr;
+		switch (slot->slot_type[BPF_REG_SIZE - 1]) {
 		case STACK_SPILL:
 			/* print MISC/ZERO/INVALID slots above subreg spill */
 			for (j = 0; j < BPF_REG_SIZE; j++)
-				if (state->stack[i].slot_type[j] == STACK_SPILL)
+				if (slot->slot_type[j] == STACK_SPILL)
 					break;
 			types_buf[j] = '\0';
 
@@ -751,7 +752,7 @@ void print_verifier_state(struct bpf_verifier_env *env, const struct bpf_verifie
 		case STACK_DYNPTR:
 			/* skip to main dynptr slot */
 			i += BPF_DYNPTR_NR_SLOTS - 1;
-			reg = &state->stack[i].spilled_ptr;
+			reg = &bpf_stack_slot(state, i)->spilled_ptr;
 
 			verbose(env, " fp%d", (-i - 1) * BPF_REG_SIZE);
 			verbose(env, "=dynptr_%s(", dynptr_type_str(reg->dynptr.type));
kernel/bpf/states.c +42 -42

221 lines not on this page · raw message

kernel/bpf/verifier.c +87 -76

472 lines not on this page · raw message

Signature · 1 line
2.53.0
#2 lore raw

Re: [PATCH bpf-next v1 01/18] bpf: Add accessors for verifier stack slots

The commit message makes two universal claims that the tree does not back up after this patch.
Quoted 13 lines

bpf: Add accessors for verifier stack slots

The verifier indexes a frame's stack state directly through state->stack[spi] and computes the number of tracked slots as allocated_stack / BPF_REG_SIZE in every file that touches stack slots. Route all of these through two helpers, bpf_stack_slot() and bpf_stack_nr_slots(), so the layout of the per-frame stack state is visible in one place and can change without touching every user. Both take a const frame: the slot accessor returns the slot through the frame's stack pointer, so read-only code such as the state printer can use it without giving up its qualifiers. Functions that look up the same slot repeatedly now fetch it once.

Quoted 3 lines

No functional change.

The commit message makes two universal claims that the tree does not back up after this patch.

1) "Route all of these through two helpers ... so the layout of the per-frame stack state is visible in one place and can change without touching every user."

At least two users of struct bpf_func_state::stack still depend on the raw layout:

drivers/net/ethernet/netronome/nfp/bpf/verifier.c:nfp_bpf_map_update_value_ok():

    state = env->cur_state->frame[reg3->frameno];
    ...
    soff = -(off + i) - 1;
    stack_entry = &state->stack[soff / BPF_REG_SIZE];

This is the exact state->stack[spi] indexing the message says was removed. It was not converted.

kernel/bpf/diagnostics.c:reg_to_target(), which this patch edits (the nslots line), still does raw pointer arithmetic that assumes stack is a flat array:

    start = (unsigned long)state->stack;
    end = (unsigned long)(state->stack + nslots);
    ...
    spi = ((const char *)reg - (const char *)state->stack) /
          sizeof(*state->stack);

If bpf_stack_slot() ever stops being &frame->stack[spi], both sites will silently compute wrong slots. So the stated goal (the layout can change without touching every user) does not hold yet.

Nothing later in 277f2757dee8..7757cddf610a changes the helpers, the layout, or the nfp code, so this is not a runtime bug in the series. It is an incomplete conversion, or a message that needs narrowing.

2) "Functions that look up the same slot repeatedly now fetch it once."

Several converted functions still call the accessor twice for the same index:

bpf_get_spilled_reg():

    (1 << bpf_stack_slot(frame, slot)->slot_type[BPF_REG_SIZE - 1]) & mask)
    return &bpf_stack_slot(frame, slot)->spilled_ptr;

bpf_mark_all_scalars_precise():

    if (!bpf_is_spilled_reg(bpf_stack_slot(func, j)))
    reg = &bpf_stack_slot(func, j)->spilled_ptr;

bpf_mark_chain_precision():

    if (!bpf_is_spilled_scalar_reg(bpf_stack_slot(func, i))) {
    reg = &bpf_stack_slot(func, i)->spilled_ptr;

The same pattern appears in states.c (propagate_precision, iter_active_depths_differ, mark_all_scalars_imprecise) and verifier.c (check_stack_write_var_off, get_constant_map_key, collect_linked_regs, widen_imprecise_scalars). Only some functions, such as print_verifier_state(), were changed to fetch once.

Should nfp_bpf_map_update_value_ok() be converted to bpf_stack_slot(), and reg_to_target() given a note or helper for its address-range check? Otherwise the changelog could be narrowed to match what the patch actually does.

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/35909853278

author maintainer
#3 lore raw

Re: [PATCH bpf-next v1 01/18] bpf: Add accessors for verifier stack slots

Quoted 27 lines · bot+bpf-ci
Quoted 13 lines

bpf: Add accessors for verifier stack slots

The verifier indexes a frame's stack state directly through state->stack[spi] and computes the number of tracked slots as allocated_stack / BPF_REG_SIZE in every file that touches stack slots. Route all of these through two helpers, bpf_stack_slot() and bpf_stack_nr_slots(), so the layout of the per-frame stack state is visible in one place and can change without touching every user. Both take a const frame: the slot accessor returns the slot through the frame's stack pointer, so read-only code such as the state printer can use it without giving up its qualifiers. Functions that look up the same slot repeatedly now fetch it once.

Quoted 3 lines

No functional change.

The commit message makes two universal claims that the tree does not back up after this patch.

1) "Route all of these through two helpers ... so the layout of the per-frame stack state is visible in one place and can change without touching every user."

At least two users of struct bpf_func_state::stack still depend on the raw layout:

Quoted 7 lines

drivers/net/ethernet/netronome/nfp/bpf/verifier.c:nfp_bpf_map_update_value_ok():

    state = env->cur_state->frame[reg3->frameno];
    ...
    soff = -(off + i) - 1;
    stack_entry = &state->stack[soff / BPF_REG_SIZE];

This is correct, will fix.

Quoted 12 lines

This is the exact state->stack[spi] indexing the message says was removed. It was not converted.

kernel/bpf/diagnostics.c:reg_to_target(), which this patch edits (the nslots line), still does raw pointer arithmetic that assumes stack is a flat array:

    start = (unsigned long)state->stack;
    end = (unsigned long)(state->stack + nslots);
    ...
    spi = ((const char *)reg - (const char *)state->stack) /
          sizeof(*state->stack);
Quoted 8 lines

If bpf_stack_slot() ever stops being &frame->stack[spi], both sites will silently compute wrong slots. So the stated goal (the layout can change without touching every user) does not hold yet.

Nothing later in 277f2757dee8..7757cddf610a changes the helpers, the layout, or the nfp code, so this is not a runtime bug in the series. It is an incomplete conversion, or a message that needs narrowing.

Yep, also needs fixing.

Quoted 17 lines

2) "Functions that look up the same slot repeatedly now fetch it once."

Several converted functions still call the accessor twice for the same index:

bpf_get_spilled_reg():

    (1 << bpf_stack_slot(frame, slot)->slot_type[BPF_REG_SIZE - 1]) & mask)
    return &bpf_stack_slot(frame, slot)->spilled_ptr;

bpf_mark_all_scalars_precise():

    if (!bpf_is_spilled_reg(bpf_stack_slot(func, j)))
    reg = &bpf_stack_slot(func, j)->spilled_ptr;

bpf_mark_chain_precision():

Quoted 9 lines
    if (!bpf_is_spilled_scalar_reg(bpf_stack_slot(func, i))) {
    reg = &bpf_stack_slot(func, i)->spilled_ptr;

The same pattern appears in states.c (propagate_precision, iter_active_depths_differ, mark_all_scalars_imprecise) and verifier.c (check_stack_write_var_off, get_constant_map_key, collect_linked_regs, widen_imprecise_scalars). Only some functions, such as print_verifier_state(), were changed to fetch once.

This is less serious, but will fix.

Quoted 11 lines

Should nfp_bpf_map_update_value_ok() be converted to bpf_stack_slot(), and reg_to_target() given a note or helper for its address-range check? Otherwise the changelog could be narrowed to match what the patch actually does.

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/35909853278

author maintainer
#4 lore raw

PATCH 2/18 bpf: Widen the stack slot index in the jump history

In reply to Kumar Kartikeya Dwivedi

Jump history entries record the stack slot touched by a spill or fill in a 6-bit field, which only fits the 64 slots of a 512-byte frame and is pinned to that size by a static_assert on MAX_BPF_STACK. Move the flags into the first word and give the slot index 12 bits of the second word instead, so the entry stays 16 bytes while frames of up to 32 KiB can be recorded.

Introduce MAX_BPF_STACK_SLOTS for the number of 8-byte slots a frame can have and use it for the static_assert and for BPF_ID_MAP_SIZE, so the verifier expresses per-frame capacity through one constant.

No functional change.

---
 include/linux/bpf_verifier.h | 21 ++++++++++++++-------
 1 file changed, 14 insertions(+), 7 deletions(-)
include/linux/bpf_verifier.h +14 -7
index 36e0c6b97533..b1c0f981fe68 100644
@@ -242,6 +242,14 @@ enum bpf_stack_slot_type {
 
 #define BPF_REG_SIZE 8	/* size of eBPF register in bytes */
 
+/*
+ * Largest number of BPF_REG_SIZE stack slots a single frame can have. A frame
+ * may use any part of the MAX_BPF_STACK budget; check_max_stack_depth()
+ * enforces the bound on the combined depth of frames sharing the kernel stack
+ * and on each frame using a private stack.
+ */
+#define MAX_BPF_STACK_SLOTS	(MAX_BPF_STACK / BPF_REG_SIZE)
+
 /* 4-byte stack slot granularity for liveness analysis */
 #define BPF_HALF_REG_SIZE	4
 #define STACK_SLOT_SZ		4
@@ -424,12 +432,11 @@ struct bpf_jmp_history_entry {
 	/* insn idx can't be bigger than 1 million */
 	u32 idx : 20;
 	u32 frame : 4;	/* stack access frame number */
-	u32 spi : 6;	/* stack slot index (0..63) */
-	u32 : 2;
-	u32 prev_idx : 20;
 	/* special INSN_F_xxx flags */
 	u32 flags : 4;
-	u32 : 8;
+	u32 : 4;
+	u32 prev_idx : 20;
+	u32 spi : 12;	/* stack slot index */
 	/*
 	 * additional registers that need precision tracking when this
 	 * jump is backtracked, vector of five 11-bit records
@@ -438,12 +445,12 @@ struct bpf_jmp_history_entry {
 };
 
 static_assert(MAX_CALL_FRAMES <= (1 << 4));
-static_assert(MAX_BPF_STACK / 8 <= (1 << 6));
+static_assert(MAX_BPF_STACK_SLOTS <= (1 << 12));
 
 /* Maximum number of bpf_reg_state objects that can exist at once */
 #define MAX_STACK_ARG_SLOTS (MAX_BPF_FUNC_ARGS - MAX_BPF_FUNC_REG_ARGS)
-#define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK / BPF_REG_SIZE + \
-			  MAX_STACK_ARG_SLOTS) * MAX_CALL_FRAMES)
+#define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK_SLOTS + MAX_STACK_ARG_SLOTS) * \
+			 MAX_CALL_FRAMES)
 struct bpf_verifier_state {
 	/* call stack tracking */
 	struct bpf_func_state *frame[MAX_CALL_FRAMES];
Signature · 1 line
2.53.0
author maintainer
#5 lore raw

PATCH 3/18 bpf: Store linked registers in the jump history as an array

In reply to Kumar Kartikeya Dwivedi

Linked scalar registers are recorded in the jump history packed into a u64 as five 11-bit entries, each naming a frame and a register or stack slot. The 6-bit slot field covers exactly the 64 slots of a 512-byte frame, so a spilled scalar in a deeper slot could not be linked and larger frames were ruled out by construction.

Store the linked registers as an array of five u16 entries plus a count instead, each entry holding the frame number, a register-or-slot bit and an 11-bit register or slot index, which covers frames of up to 16 KiB. Callers that record no linked registers pass NULL.

The history entry grows from 16 to 20 bytes, and the history is the one verifier structure whose size follows the number of instructions a loop iterates over rather than the state count. Measured over the 5075 selftest programs, peak verifier memory is unchanged for all but the loop-heavy ones, which grow by 8 to 16%: loop1/nested_loops from 17.6 to 19.2 MiB, verifier_loops1/jumps_out_rather_than_in from 4.4 to 5.1 MiB, strobemeta by 0.3% and pyperf600_nounroll by 0.8%. Verdicts, processed instructions and state counts stay the same everywhere.

No functional change.

---
 include/linux/bpf_verifier.h | 16 +++++--
 kernel/bpf/backtrack.c       | 18 +++++---
 kernel/bpf/states.c          |  2 +-
 kernel/bpf/verifier.c        | 86 ++++++++++++++++--------------------
 4 files changed, 62 insertions(+), 60 deletions(-)
include/linux/bpf_verifier.h +12 -4
index b1c0f981fe68..77cda3b3a3e9 100644
@@ -428,6 +428,9 @@ enum {
 	INSN_F_STACK_ARG_ACCESS = BIT(3),
 };
 
+/* Registers linked to one jump condition that a history entry can record */
+#define BPF_LINKED_REGS_MAX	5
+
 struct bpf_jmp_history_entry {
 	/* insn idx can't be bigger than 1 million */
 	u32 idx : 20;
@@ -438,10 +441,14 @@ struct bpf_jmp_history_entry {
 	u32 prev_idx : 20;
 	u32 spi : 12;	/* stack slot index */
 	/*
-	 * additional registers that need precision tracking when this
-	 * jump is backtracked, vector of five 11-bit records
+	 * Scalar registers and spilled scalars linked to the condition of
+	 * this jump, which need precision tracking together when the jump is
+	 * backtracked. Each is packed as 4 bits of frame number, one bit
+	 * telling a register from a stack slot and 11 bits of register or
+	 * slot index, see linked_regs_pack().
 	 */
-	u64 linked_regs;
+	u16 linked_regs[BPF_LINKED_REGS_MAX];
+	u8 linked_regs_cnt;
 };
 
 static_assert(MAX_CALL_FRAMES <= (1 << 4));
@@ -1249,7 +1256,8 @@ struct list_head *bpf_explored_state(struct bpf_verifier_env *env, int idx);
 void bpf_free_verifier_state(struct bpf_verifier_state *state, bool free_self);
 void bpf_free_backedges(struct bpf_scc_visit *visit);
 int bpf_push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_state *cur,
-			 int insn_flags, int spi, int frame, u64 linked_regs);
+			 int insn_flags, int spi, int frame, const u16 *linked_regs,
+			 u8 linked_regs_cnt);
 void bpf_bt_sync_linked_regs(struct backtrack_state *bt, struct bpf_jmp_history_entry *hist);
 void bpf_mark_reg_not_init(const struct bpf_verifier_env *env,
 			   struct bpf_reg_state *reg);
kernel/bpf/backtrack.c +12 -6
index 4bec7b94796b..6733d4078930 100644
@@ -9,7 +9,8 @@
 
 /* for any branch, call, exit record the history of jmps in the given state */
 int bpf_push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_state *cur,
-			 int insn_flags, int spi, int frame, u64 linked_regs)
+			 int insn_flags, int spi, int frame, const u16 *linked_regs,
+			 u8 linked_regs_cnt)
 {
 	u32 cnt = cur->jmp_history_cnt;
 	struct bpf_jmp_history_entry *p;
@@ -27,10 +28,13 @@ int bpf_push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_state
 		env->cur_hist_ent->flags |= insn_flags;
 		env->cur_hist_ent->spi = spi;
 		env->cur_hist_ent->frame = frame;
-		verifier_bug_if(env->cur_hist_ent->linked_regs != 0, env,
-				"insn history: insn_idx %d linked_regs: %#llx",
-				env->insn_idx, env->cur_hist_ent->linked_regs);
-		env->cur_hist_ent->linked_regs = linked_regs;
+		verifier_bug_if(env->cur_hist_ent->linked_regs_cnt != 0, env,
+				"insn history: insn_idx %d has %u linked regs",
+				env->insn_idx, env->cur_hist_ent->linked_regs_cnt);
+		if (linked_regs_cnt)
+			memcpy(env->cur_hist_ent->linked_regs, linked_regs,
+			       linked_regs_cnt * sizeof(*linked_regs));
+		env->cur_hist_ent->linked_regs_cnt = linked_regs_cnt;
 		return 0;
 	}
 
@@ -47,7 +51,9 @@ int bpf_push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_state
 	p->flags = insn_flags;
 	p->spi = spi;
 	p->frame = frame;
-	p->linked_regs = linked_regs;
+	if (linked_regs_cnt)
+		memcpy(p->linked_regs, linked_regs, linked_regs_cnt * sizeof(*linked_regs));
+	p->linked_regs_cnt = linked_regs_cnt;
 	cur->jmp_history_cnt = cnt;
 	env->cur_hist_ent = p;
 
kernel/bpf/states.c +1 -1
index 38795cf35247..e84f37d724d5 100644
@@ -1410,7 +1410,7 @@ int bpf_is_state_visited(struct bpf_verifier_env *env, int insn_idx)
 			 */
 			err = 0;
 			if (bpf_is_jmp_point(env, env->insn_idx))
-				err = bpf_push_jmp_history(env, cur, 0, 0, 0, 0);
+				err = bpf_push_jmp_history(env, cur, 0, 0, 0, NULL, 0);
 			err = err ? : propagate_precision(env, &sl->state, cur, NULL);
 			if (err)
 				return err;
kernel/bpf/verifier.c +37 -49

170 lines not on this page · raw message

Signature · 1 line
2.53.0
author maintainer
#6 lore raw

PATCH 4/18 bpf: Track backtracking stack slots with bitmaps

In reply to Kumar Kartikeya Dwivedi

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.

---
 include/linux/bpf_verifier.h | 13 +++-----
 kernel/bpf/backtrack.c       | 65 ++++++++++++++++++++++--------------
 kernel/bpf/verifier.c        | 15 ++++++---
 3 files changed, 54 insertions(+), 39 deletions(-)
include/linux/bpf_verifier.h +4 -9
index 77cda3b3a3e9..905a081d4b62 100644
@@ -879,7 +879,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];
 };
 
@@ -1317,12 +1317,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)
@@ -1337,7 +1332,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);
@@ -1531,7 +1526,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. */
kernel/bpf/backtrack.c +40 -25

133 lines not on this page · raw message

kernel/bpf/verifier.c +10 -5
index fa80f95105fb..a66f1688407c 100644
@@ -3864,10 +3864,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;
@@ -3880,7 +3879,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;
 		}
@@ -3891,8 +3890,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 {
Signature · 1 line
2.53.0
author maintainer
#7 lore raw

PATCH 5/18 bpf: Track scratched stack slots with a bitmap

In reply to Kumar Kartikeya Dwivedi

The set of stack slots touched since the verifier state was last printed lives in a u64, so the log could only ever mark the first 64 slots of a frame as scratched. Make it a bitmap sized by MAX_BPF_STACK_SLOTS and go through the bitmap helpers for setting, testing, clearing and filling it.

No functional change.

---
 include/linux/bpf_verifier.h | 15 ++++++++-------
 1 file changed, 8 insertions(+), 7 deletions(-)
include/linux/bpf_verifier.h +8 -7
index 905a081d4b62..354463a74292 100644
@@ -1057,7 +1057,7 @@ struct bpf_verifier_env {
 	 */
 	u32 scratched_regs;
 	/* Same as scratched_regs but for stack slots */
-	u64 scratched_stack_slots;
+	DECLARE_BITMAP(scratched_stack_slots, MAX_BPF_STACK_SLOTS);
 	u64 prev_log_pos, prev_insn_print_pos;
 	/* buffer used to temporary hold constants as scalar registers */
 	struct bpf_reg_state fake_reg[1];
@@ -1463,7 +1463,7 @@ static inline void mark_reg_scratched(struct bpf_verifier_env *env, u32 regno)
 
 static inline void mark_stack_slot_scratched(struct bpf_verifier_env *env, u32 spi)
 {
-	env->scratched_stack_slots |= 1ULL << spi;
+	__set_bit(spi, env->scratched_stack_slots);
 }
 
 static inline bool reg_scratched(const struct bpf_verifier_env *env, u32 regno)
@@ -1471,27 +1471,28 @@ static inline bool reg_scratched(const struct bpf_verifier_env *env, u32 regno)
 	return (env->scratched_regs >> regno) & 1;
 }
 
-static inline bool stack_slot_scratched(const struct bpf_verifier_env *env, u64 regno)
+static inline bool stack_slot_scratched(const struct bpf_verifier_env *env, u32 spi)
 {
-	return (env->scratched_stack_slots >> regno) & 1;
+	return test_bit(spi, env->scratched_stack_slots);
 }
 
 static inline bool verifier_state_scratched(const struct bpf_verifier_env *env)
 {
-	return env->scratched_regs || env->scratched_stack_slots;
+	return env->scratched_regs ||
+	       !bitmap_empty(env->scratched_stack_slots, MAX_BPF_STACK_SLOTS);
 }
 
 static inline void mark_verifier_state_clean(struct bpf_verifier_env *env)
 {
 	env->scratched_regs = 0U;
-	env->scratched_stack_slots = 0ULL;
+	bitmap_zero(env->scratched_stack_slots, MAX_BPF_STACK_SLOTS);
 }
 
 /* Used for printing the entire verifier state. */
 static inline void mark_verifier_state_scratched(struct bpf_verifier_env *env)
 {
 	env->scratched_regs = ~0U;
-	env->scratched_stack_slots = ~0ULL;
+	bitmap_fill(env->scratched_stack_slots, MAX_BPF_STACK_SLOTS);
 }
 
 static inline bool bpf_stack_narrow_access_ok(int off, int fill_size, int spill_size)
Signature · 1 line
2.53.0
author maintainer
#8 lore raw

PATCH 6/18 bpf: Treat unknown-size stack reads as reaching the frame top

In reply to Kumar Kartikeya Dwivedi

When the size of a helper or kfunc memory argument is not a constant on the path, the stack liveness analysis is told the call reads MAX_BPF_STACK bytes starting at the pointer's offset. Clipped at the top of the frame this covers everything from the offset upwards, which is the intent, but only as long as no frame is deeper than MAX_BPF_STACK bytes.

Return the "unknown" marker instead, which the liveness analysis already turns into a read of every slot between the offset and the frame top, independent of how deep the frame is.

No functional change.

---
 kernel/bpf/verifier.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)
kernel/bpf/verifier.c +4 -3
index a66f1688407c..d8f43f3a8991 100644
@@ -13894,11 +13894,11 @@ s64 bpf_helper_stack_access_bytes(struct bpf_verifier_env *env, struct bpf_insn
 			}
 			/*
 			 * Size arg is const on each path but differs across merged
-			 * paths. MAX_BPF_STACK is a safe upper bound for reads.
+			 * paths. Reads may extend anywhere up to the frame top.
 			 */
 			if (full_write)
 				return 0;
-			return MAX_BPF_STACK;
+			return S64_MIN;
 		}
 		return S64_MIN;
 	case ARG_PTR_TO_DYNPTR:
@@ -13984,7 +13984,8 @@ s64 bpf_kfunc_stack_access_bytes(struct bpf_verifier_env *env, struct bpf_insn *
 			size = (s64)aux->const_reg_vals[size_reg];
 			goto out;
 		}
-		return MAX_BPF_STACK;
+		/* Unknown size: the read may extend anywhere up to the frame top. */
+		return S64_MIN;
 	}
 
 	/* fixed-size pointed-to type: resolve via BTF */
Signature · 1 line
2.53.0
author maintainer
#9 lore raw

PATCH 7/18 bpf: Size liveness stack masks by the stack each frame uses

In reply to Kumar Kartikeya Dwivedi

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.

---
 include/linux/bpf_verifier.h |  46 -----
 kernel/bpf/liveness.c        | 345 ++++++++++++++++++++++++-----------
 2 files changed, 238 insertions(+), 153 deletions(-)
include/linux/bpf_verifier.h +0 -46
index 354463a74292..0f348ce81fe2 100644
@@ -253,52 +253,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) | \
kernel/bpf/liveness.c +238 -107

537 lines not on this page · raw message

Signature · 1 line
2.53.0
author maintainer
#10 lore raw

PATCH 8/18 bpf: Grow the verifier id scratch on demand

In reply to Kumar Kartikeya Dwivedi

The id map used to compare the ids of two states, which also serves as the id stack of release_reference() and as the id set of bpf_clear_singular_ids(), is a fixed array embedded in struct bpf_verifier_env and sized for the most registers and stack slots a state can possibly hold: 1312 entries, 10 KiB, for 512-byte frames, and four times that once frames may reach 2 KiB, which pushes the env allocation from 64 KiB to 128 KiB for every program verified. States compare a few dozen ids in practice.

Turn the map and the set into arrays grown on demand, starting at 64 entries and doubling, and free them with the env. A map that cannot grow treats the states as different, an id set that cannot grow keeps the id, and the id stack reports -ENOMEM, so an allocation failure is never unsafe. This removes the last structure whose size scaled with the stack bound and shrinks the env by 10 KiB.

---
 include/linux/bpf_verifier.h | 29 ++++++++++++++----------
 kernel/bpf/states.c          | 44 +++++++++++++++++++++++++-----------
 kernel/bpf/verifier.c        | 20 +++++++++-------
 3 files changed, 60 insertions(+), 33 deletions(-)
include/linux/bpf_verifier.h +17 -12
index 0f348ce81fe2..d8cafd3d74aa 100644
@@ -408,10 +408,7 @@ struct bpf_jmp_history_entry {
 static_assert(MAX_CALL_FRAMES <= (1 << 4));
 static_assert(MAX_BPF_STACK_SLOTS <= (1 << 12));
 
-/* Maximum number of bpf_reg_state objects that can exist at once */
 #define MAX_STACK_ARG_SLOTS (MAX_BPF_FUNC_ARGS - MAX_BPF_FUNC_REG_ARGS)
-#define BPF_ID_MAP_SIZE ((MAX_BPF_REG + MAX_BPF_STACK_SLOTS + MAX_STACK_ARG_SLOTS) * \
-			 MAX_CALL_FRAMES)
 struct bpf_verifier_state {
 	/* call stack tracking */
 	struct bpf_func_state *frame[MAX_CALL_FRAMES];
@@ -842,18 +839,27 @@ struct bpf_id_pair {
 	u32 cur;
 };
 
+/*
+ * Scratch map from the ids of one verifier state to those of another, also
+ * used as a stack of ids. Grown on demand by bpf_id_scratch_reserve().
+ */
 struct bpf_idmap {
 	u32 tmp_id_gen;
 	u32 cnt;
-	struct bpf_id_pair map[BPF_ID_MAP_SIZE];
+	u32 cap;
+	struct bpf_id_pair *map;
 };
 
+struct bpf_idset_entry {
+	u32 id;
+	u32 cnt;
+};
+
+/* Scratch set of ids with a use count each, grown on demand */
 struct bpf_idset {
 	u32 num_ids;
-	struct {
-		u32 id;
-		u32 cnt;
-	} entries[BPF_ID_MAP_SIZE];
+	u32 cap;
+	struct bpf_idset_entry *entries;
 };
 
 /* see verifier.c:compute_scc_callchain() */
@@ -948,10 +954,8 @@ struct bpf_verifier_env {
 	struct bpf_subprog_info subprog_info[BPF_MAX_SUBPROGS + 2]; /* max + 2 for the fake and exception subprogs */
 	/* subprog indices sorted in topological order: leaves first, callers last */
 	int subprog_topo_order[BPF_MAX_SUBPROGS + 2];
-	union {
-		struct bpf_idmap idmap_scratch;
-		struct bpf_idset idset_scratch;
-	};
+	struct bpf_idmap idmap_scratch;
+	struct bpf_idset idset_scratch;
 	struct {
 		int *insn_state;
 		int *insn_stack;
@@ -1209,6 +1213,7 @@ int bpf_copy_verifier_state(struct bpf_verifier_state *dst_state,
 struct list_head *bpf_explored_state(struct bpf_verifier_env *env, int idx);
 void bpf_free_verifier_state(struct bpf_verifier_state *state, bool free_self);
 void bpf_free_backedges(struct bpf_scc_visit *visit);
+bool bpf_id_scratch_reserve(void **arr, u32 *cap, u32 cnt, size_t elem_size);
 int bpf_push_jmp_history(struct bpf_verifier_env *env, struct bpf_verifier_state *cur,
 			 int insn_flags, int spi, int frame, const u16 *linked_regs,
 			 u8 linked_regs_cnt);
kernel/bpf/states.c +31 -13

58 lines not on this page · raw message

kernel/bpf/verifier.c +12 -8
index d8f43f3a8991..8641f1a8d017 100644
@@ -10136,8 +10136,9 @@ static int idstack_push(struct bpf_idmap *idmap, u32 id)
 		if (idmap->map[i].old == id)
 			return 0;
 
-	if (WARN_ON_ONCE(idmap->cnt >= BPF_ID_MAP_SIZE))
-		return -EFAULT;
+	if (!bpf_id_scratch_reserve((void **)&idmap->map, &idmap->cap, idmap->cnt,
+				    sizeof(*idmap->map)))
+		return -ENOMEM;
 
 	idmap->map[idmap->cnt++].old = id;
 	return 0;
@@ -18438,12 +18439,13 @@ static void idset_cnt_inc(struct bpf_idset *idset, u32 id)
 			return;
 		}
 	}
-	/* New id */
-	if (idset->num_ids < BPF_ID_MAP_SIZE) {
-		idset->entries[idset->num_ids].id = id;
-		idset->entries[idset->num_ids].cnt = 1;
-		idset->num_ids++;
-	}
+	/* New id; one that cannot be recorded counts as shared and is kept */
+	if (!bpf_id_scratch_reserve((void **)&idset->entries, &idset->cap, idset->num_ids,
+				    sizeof(*idset->entries)))
+		return;
+	idset->entries[idset->num_ids].id = id;
+	idset->entries[idset->num_ids].cnt = 1;
+	idset->num_ids++;
 }
 
 /* Find id in idset and return its count, or 0 if not found */
@@ -22003,6 +22005,8 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr,
 	kvfree(env->scc_info);
 	kvfree(env->succ);
 	kvfree(env->gotox_tmp_buf);
+	kfree(env->idmap_scratch.map);
+	kfree(env->idset_scratch.entries);
 	bpf_diag_free(env);
 	kvfree(env);
 	return ret;
Signature · 1 line
2.53.0
#11 lore raw

Re: [PATCH bpf-next v1 08/18] bpf: Grow the verifier id scratch on demand

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [Medium] bpf: OOM in release_reference() triggers WARN_ON_ONCE and is improperly ignored in…

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] bpf: OOM in release_reference() triggers WARN_ON_ONCE and is improperly ignored in unmark_stack_slots_iter() --

commit bdefbd593b54c82f98de0288f1f6f5e793ee9fbb
Author: Kumar Kartikeya Dwivedi <[email protected]>

bpf: Grow the verifier id scratch on demand

The id map used to compare the ids of two states, which also serves as the id stack of release_reference() and as the id set of bpf_clear_singular_ids(), is a fixed array embedded in struct bpf_verifier_env and sized for the most registers and stack slots a state can possibly hold. Turn the map and the set into arrays grown on demand, starting at 64 entries and doubling, and free them with the env.

kernel/bpf/verifier.c static int idstack_push(struct bpf_idmap *idmap, u32 id) · line 10141

Quoted 13 lines
kernel/bpf/verifier.c +3 -2
index d8f43f3a89912..8641f1a8d017d 100644
@@ -10136,8 +10136,9 @@ static int idstack_push(struct bpf_idmap *idmap, u32 id)
 		if (idmap->map[i].old == id)
 			return 0;
 
-	if (WARN_ON_ONCE(idmap->cnt >= BPF_ID_MAP_SIZE))
-		return -EFAULT;
+	if (!bpf_id_scratch_reserve((void **)&idmap->map, &idmap->cap, idmap->cnt,
+				    sizeof(*idmap->map)))
+		return -ENOMEM;

[Severity: Medium]
With this change, idstack_push() can return -ENOMEM on a normal allocation failure, which propagates up through release_reference().

However, in kernel/bpf/verifier.c:unmark_stack_slots_iter(), we have:

	for (i = 0; i < nr_slots; i++) {
		struct bpf_stack_state *slot = bpf_stack_slot(state, spi - i);
		struct bpf_reg_state *st = &slot->spilled_ptr;

		if (i == 0)
			WARN_ON_ONCE(release_reference(env, st->id));

Does this mean a simple -ENOMEM during verification will trigger this WARN_ON_ONCE splat? Since release_reference() can now legitimately fail under memory pressure, should this warning be removed, and should the -ENOMEM error be properly propagated here instead of discarded?

Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=8
author maintainer
#12 lore raw

Re: [PATCH bpf-next v1 08/18] bpf: Grow the verifier id scratch on demand

Quoted 43 lines · sashiko-bot

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Medium] bpf: OOM in release_reference() triggers WARN_ON_ONCE and is improperly ignored in unmark_stack_slots_iter() --

commit bdefbd593b54c82f98de0288f1f6f5e793ee9fbb
Author: Kumar Kartikeya Dwivedi <[email protected]>

bpf: Grow the verifier id scratch on demand

The id map used to compare the ids of two states, which also serves as the id stack of release_reference() and as the id set of bpf_clear_singular_ids(), is a fixed array embedded in struct bpf_verifier_env and sized for the most registers and stack slots a state can possibly hold. Turn the map and the set into arrays grown on demand, starting at 64 entries and doubling, and free them with the env.

kernel/bpf/verifier.c static int idstack_push(struct bpf_idmap *idmap, u32 id) · line 10141

Quoted 13 lines
kernel/bpf/verifier.c +3 -2
index d8f43f3a89912..8641f1a8d017d 100644
@@ -10136,8 +10136,9 @@ static int idstack_push(struct bpf_idmap *idmap, u32 id)
 		if (idmap->map[i].old == id)
 			return 0;
 
-	if (WARN_ON_ONCE(idmap->cnt >= BPF_ID_MAP_SIZE))
-		return -EFAULT;
+	if (!bpf_id_scratch_reserve((void **)&idmap->map, &idmap->cap, idmap->cnt,
+				    sizeof(*idmap->map)))
+		return -ENOMEM;

[Severity: Medium]
With this change, idstack_push() can return -ENOMEM on a normal allocation failure, which propagates up through release_reference().

However, in kernel/bpf/verifier.c:unmark_stack_slots_iter(), we have:

	for (i = 0; i < nr_slots; i++) {
		struct bpf_stack_state *slot = bpf_stack_slot(state, spi - i);
		struct bpf_reg_state *st = &slot->spilled_ptr;

		if (i == 0)
			WARN_ON_ONCE(release_reference(env, st->id));
Quoted 4 lines

Does this mean a simple -ENOMEM during verification will trigger this WARN_ON_ONCE splat? Since release_reference() can now legitimately fail under memory pressure, should this warning be removed, and should the -ENOMEM error be properly propagated here instead of discarded?

This one is legit, probably needs more graceful handling.

author maintainer
#13 lore raw

PATCH 9/18 selftests/bpf: Cover the tail call caller stack depth limit

In reply to Kumar Kartikeya Dwivedi

A tail call from a subprog only unwinds that subprog's frame, so the verifier refuses tail calls once the frames of the callers add up to 256 bytes or more. Nothing exercised that rule. Add a pair of tests with a caller using 240 and 256 bytes of stack respectively, the latter expecting the "tail_calls are not allowed when call stack of previous frames is 256 bytes" rejection.

---
 .../selftests/bpf/progs/verifier_tailcall.c   | 57 +++++++++++++++++++
 1 file changed, 57 insertions(+)
tools/testing/selftests/bpf/progs/verifier_tailcall.c +57 -0
index b4acce60fb9b..51687da97225 100644
@@ -28,4 +28,61 @@ __naked void invalid_map_for_tail_call(void)
 	: __clobber_all);
 }
 
+struct {
+	__uint(type, BPF_MAP_TYPE_PROG_ARRAY);
+	__uint(max_entries, 1);
+	__uint(key_size, sizeof(__u32));
+	__uint(value_size, sizeof(__u32));
+} jmp_table SEC(".maps");
+
+__used __naked
+static int subprog_tail_call(void)
+{
+	asm volatile ("			\
+	r2 = %[jmp_table] ll;		\
+	r3 = 0;				\
+	call %[bpf_tail_call];		\
+	r0 = 0;				\
+	exit;				\
+"	:
+	: __imm(bpf_tail_call),
+	  __imm_addr(jmp_table)
+	: __clobber_all);
+}
+
+/*
+ * A tail call unwinds only the frame of the subprog doing it, so the
+ * frames of its callers stay on the stack. With up to 33 tail calls in
+ * a chain the verifier caps the stack those frames may add up to at
+ * 256 bytes.
+ */
+SEC("tc")
+__description("tail call from subprog with 240 bytes of caller stack")
+__success
+__naked void tail_call_caller_stack_ok(void)
+{
+	asm volatile ("			\
+	r2 = 42;			\
+	*(u64 *)(r10 - 240) = r2;	\
+	call subprog_tail_call;		\
+	r0 = 0;				\
+	exit;				\
+"	::: __clobber_all);
+}
+
+SEC("tc")
+__description("tail call from subprog with 256 bytes of caller stack")
+__failure
+__msg("tail_calls are not allowed when call stack of previous frames is 256 bytes. Too large")
+__naked void tail_call_caller_stack_too_large(void)
+{
+	asm volatile ("			\
+	r2 = 42;			\
+	*(u64 *)(r10 - 256) = r2;	\
+	call subprog_tail_call;		\
+	r0 = 0;				\
+	exit;				\
+"	::: __clobber_all);
+}
+
 char _license[] SEC("license") = "GPL";
Signature · 1 line
2.53.0
author maintainer
#14 lore raw

PATCH 10/18 selftests/bpf: Check that narrow stack stores define no slot

In reply to Kumar Kartikeya Dwivedi

The stack liveness analysis records a store as a "def" only for the 4-byte half-slots it covers completely, so a one or two byte store near the top of the frame must not define anything. Add a test that reads fp-8, stores one byte at fp-1 and two bytes at fp-4, and reads fp-8 again, expecting no def mark on either store and the second read to still use fp-8.

---
 .../selftests/bpf/progs/verifier_live_stack.c | 22 +++++++++++++++++++
 1 file changed, 22 insertions(+)
tools/testing/selftests/bpf/progs/verifier_live_stack.c +22 -0
index 7a1a0670f851..f8758eb62dac 100644
@@ -2839,3 +2839,25 @@ static __used __naked void imprecise_dst_spill_join_sub(void)
 	:: __imm(bpf_get_prandom_u32)
 	: __clobber_all);
 }
+
+/*
+ * A store that does not fully cover a 4-byte half-slot defines nothing, so a
+ * narrow store at the top of the frame must not turn any slot into a "def",
+ * least of all every slot of the frame: the earlier data at fp-8 stays live.
+ */
+SEC("socket")
+__log_level(2)
+__msg("0: (79) r0 = *(u64 *)(r10 -8)        ; use: fp0-8")
+__msg("1: (73) *(u8 *)(r10 -1) = r0{{$}}")
+__msg("2: (6b) *(u16 *)(r10 -4) = r0{{$}}")
+__msg("3: (79) r0 = *(u64 *)(r10 -8)        ; use: fp0-8")
+__naked void narrow_store_defines_nothing(void)
+{
+	asm volatile (
+	"r0 = *(u64 *)(r10 - 8);"
+	"*(u8 *)(r10 - 1) = r0;"
+	"*(u16 *)(r10 - 4) = r0;"
+	"r0 = *(u64 *)(r10 - 8);"
+	"exit;"
+	::: __clobber_all);
+}
Signature · 1 line
2.53.0
author maintainer
#15 lore raw

PATCH 11/18 selftests/bpf: Check liveness merge of masks with different widths

In reply to Kumar Kartikeya Dwivedi

The liveness masks of a function instance are as wide as the deepest half-slot the instance was seen to access. When the same instance is analyzed again through another call site, the new pass may have settled on a different width, and merge_instances() has to widen the original before combining the two. Add a test where the first pass of a callee reads through a pointer 264 bytes into the main frame and the second one through a pointer of unknown offset, a whole-frame read at the maximum width, and check that the merged result keeps the whole-frame read.

---
 .../selftests/bpf/progs/verifier_live_stack.c | 49 +++++++++++++++++++
 1 file changed, 49 insertions(+)
tools/testing/selftests/bpf/progs/verifier_live_stack.c +49 -0
index f8758eb62dac..a94365decd5f 100644
@@ -2861,3 +2861,52 @@ __naked void narrow_store_defines_nothing(void)
 	"exit;"
 	::: __clobber_all);
 }
+
+/*
+ * The same callee instance is analyzed twice: the call sites are visited in
+ * postorder, so the second one goes first with a precise pointer 264 bytes
+ * into the main frame, and the first one then passes a pointer of unknown
+ * offset, which reads the whole frame. The masks of the two passes differ in
+ * width; merging the second into the first must keep the whole-frame read.
+ */
+SEC("socket")
+__log_level(2)
+__msg("stack use/def subprog#{{[0-9]+}} merge_read_all_callee (d2,cs{{[0-9]+}}):")
+__msg("(79) r0 = *(u64 *)(r1 +0){{.*}}; use: fp0-8..-512")
+__naked void merge_keeps_whole_frame_read(void)
+{
+	asm volatile (
+	"r1 = 0;"
+	"*(u64 *)(r10 - 8) = r1;"
+	"*(u64 *)(r10 - 16) = r1;"
+	"*(u64 *)(r10 - 264) = r1;"
+	"call %[bpf_get_prandom_u32];"
+	"r0 &= 8;"
+	"r1 = r10;"
+	"r1 += -16;"
+	"r1 += r0;"
+	"call merge_read_all_mid;"
+	"r1 = r10;"
+	"r1 += -264;"
+	"call merge_read_all_mid;"
+	"r0 = 0;"
+	"exit;"
+	:: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
+
+static __used __naked void merge_read_all_mid(void)
+{
+	asm volatile (
+	"call merge_read_all_callee;"
+	"exit;"
+	::: __clobber_all);
+}
+
+static __used __naked void merge_read_all_callee(void)
+{
+	asm volatile (
+	"r0 = *(u64 *)(r1 + 0);"
+	"exit;"
+	::: __clobber_all);
+}
Signature · 1 line
2.53.0
#16 lore raw

Re: [PATCH bpf-next v1 11/18] selftests/bpf: Check liveness merge of masks with different widths

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider: - [Low] bpf: merge_keeps_whole_frame_read test is vacuous on some 64-bit archs --

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Low] bpf: merge_keeps_whole_frame_read test is vacuous on some 64-bit archs --

commit 1299c778ee1ba2ffa8d447fa3ce55a6d2aec24cd
Author: Kumar Kartikeya Dwivedi <[email protected]>

selftests/bpf: Check liveness merge of masks with different widths

This commit adds a selftest to verify that merge_instances() correctly widens liveness masks of different widths when a function instance is analyzed through different call sites.

Quoted 5 lines
tools/testing/selftests/bpf/progs/verifier_live_stack.c +0 -0
index f8758eb62dac5..a94365decd5f1 100644
@@ -2861,3 +2861,52 @@ __naked void narrow_store_defines_nothing(void)

[ ... ]

tools/testing/selftests/bpf/progs/verifier_live_stack.c __naked void narrow_store_defines_nothing(void) · line 2882

Quoted 11 lines
tools/testing/selftests/bpf/progs/verifier_live_stack.c +11 -0
+SEC("socket")
+__log_level(2)
+__msg("stack use/def subprog#{{[0-9]+}} merge_read_all_callee (d2,cs{{[0-9]+}}):")
+__msg("(79) r0 = *(u64 *)(r1 +0){{.*}}; use: fp0-8..-512")
+__naked void merge_keeps_whole_frame_read(void)
+{
+	asm volatile (
+	"r1 = 0;"
+	"*(u64 *)(r10 - 8) = r1;"
+	"*(u64 *)(r10 - 16) = r1;"
+	"*(u64 *)(r10 - 264) = r1;"

[Severity: Low]
Is this test effectively vacuous on 64-bit architectures with a 512-byte stack limit?

The precise 8-byte read at offset -264 touches half-slot 66. This means the mask requires 66 bits, which on a 64-bit architecture occupies 2 words.

The second pass performs an unknown-offset read, forcing a whole-frame mask. For a 512-byte stack limit, this covers 128 half-slots (128 bits), which also occupies 2 words.

Because both masks occupy 2 words, the actual widening logic in widen_frame_masks() is silently skipped, missing the intended test coverage.

While later patches in this series might raise the stack limit for some architectures, the test remains mathematically vacuous on 64-bit architectures that retain the 512-byte limit (e.g., RISC-V, s390x, or when JIT is off).

Would changing the precise read to an offset <= 256 (e.g., -248) correctly produce a 1-word mask and test the intended logic universally?

Quoted 14 lines
tools/testing/selftests/bpf/progs/verifier_live_stack.c +14 -0
+	"call %[bpf_get_prandom_u32];"
+	"r0 &= 8;"
+	"r1 = r10;"
+	"r1 += -16;"
+	"r1 += r0;"
+	"call merge_read_all_mid;"
+	"r1 = r10;"
+	"r1 += -264;"
+	"call merge_read_all_mid;"
+	"r0 = 0;"
+	"exit;"
+	:: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
Signature · 1 line
Sashiko AI review · https://sashiko.dev/#/patchset/[email protected]?part=11
author maintainer
#17 lore raw

Re: [PATCH bpf-next v1 11/18] selftests/bpf: Check liveness merge of masks with different widths

Quoted 47 lines · sashiko-bot

Thank you for your contribution! Sashiko AI review found 1 potential issue(s) to consider:
- [Low] bpf: merge_keeps_whole_frame_read test is vacuous on some 64-bit archs --

commit 1299c778ee1ba2ffa8d447fa3ce55a6d2aec24cd
Author: Kumar Kartikeya Dwivedi <[email protected]>

selftests/bpf: Check liveness merge of masks with different widths

This commit adds a selftest to verify that merge_instances() correctly widens liveness masks of different widths when a function instance is analyzed through different call sites.

Quoted 5 lines
tools/testing/selftests/bpf/progs/verifier_live_stack.c +0 -0
index f8758eb62dac5..a94365decd5f1 100644
@@ -2861,3 +2861,52 @@ __naked void narrow_store_defines_nothing(void)

[ ... ]

tools/testing/selftests/bpf/progs/verifier_live_stack.c __naked void narrow_store_defines_nothing(void) · line 2882

Quoted 11 lines
tools/testing/selftests/bpf/progs/verifier_live_stack.c +11 -0
+SEC("socket")
+__log_level(2)
+__msg("stack use/def subprog#{{[0-9]+}} merge_read_all_callee (d2,cs{{[0-9]+}}):")
+__msg("(79) r0 = *(u64 *)(r1 +0){{.*}}; use: fp0-8..-512")
+__naked void merge_keeps_whole_frame_read(void)
+{
+	asm volatile (
+	"r1 = 0;"
+	"*(u64 *)(r10 - 8) = r1;"
+	"*(u64 *)(r10 - 16) = r1;"
+	"*(u64 *)(r10 - 264) = r1;"

[Severity: Low]
Is this test effectively vacuous on 64-bit architectures with a 512-byte stack limit?

The precise 8-byte read at offset -264 touches half-slot 66. This means the mask requires 66 bits, which on a 64-bit architecture occupies 2 words.

The second pass performs an unknown-offset read, forcing a whole-frame mask. For a 512-byte stack limit, this covers 128 half-slots (128 bits), which also occupies 2 words.

Because both masks occupy 2 words, the actual widening logic in widen_frame_masks() is silently skipped, missing the intended test coverage.

Quoted 7 lines

While later patches in this series might raise the stack limit for some architectures, the test remains mathematically vacuous on 64-bit architectures that retain the 512-byte limit (e.g., RISC-V, s390x, or when JIT is off).

Would changing the precise read to an offset <= 256 (e.g., -248) correctly produce a 1-word mask and test the intended logic universally?

Plausible, will investigate.

Quoted 14 lines
Quoted 14 lines
tools/testing/selftests/bpf/progs/verifier_live_stack.c +14 -0
+	"call %[bpf_get_prandom_u32];"
+	"r0 &= 8;"
+	"r1 = r10;"
+	"r1 += -16;"
+	"r1 += r0;"
+	"call merge_read_all_mid;"
+	"r1 = r10;"
+	"r1 += -264;"
+	"call merge_read_all_mid;"
+	"r0 = 0;"
+	"exit;"
+	:: __imm(bpf_get_prandom_u32)
+	: __clobber_all);
+}
author maintainer
#18 lore raw

PATCH 12/18 bpf: Size the per-frame verifier structures for a 2 KiB stack

In reply to Kumar Kartikeya Dwivedi

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 backtracking and scratched-slot bitmaps grow from one to four words per frame, a fixed few hundred bytes per verifier environment, and 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; 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.

---
 include/linux/bpf_verifier.h                  | 20 ++++++++++---------
 include/linux/filter.h                        |  5 +++++
 kernel/bpf/liveness.c                         |  2 +-
 .../selftests/bpf/progs/verifier_live_stack.c |  6 +++---
 4 files changed, 20 insertions(+), 13 deletions(-)
include/linux/bpf_verifier.h +11 -9
index d8cafd3d74aa..11fa9f1f087c 100644
@@ -19,11 +19,12 @@
  * that converting umax_value to int cannot overflow.
  */
 #define BPF_MAX_VAR_SIZ	(1 << 29)
-/* size of tmp_str_buf in bpf_verifier.
- * we need at least 306 bytes to fit full stack mask representation
- * (in the "-8,-16,...,-512" form)
+/*
+ * size of tmp_str_buf in bpf_verifier.
+ * we need at least 1399 bytes to fit full stack mask representation
+ * (in the "-8,-16,...,-2048" form)
  */
-#define TMP_STR_BUF_LEN 320
+#define TMP_STR_BUF_LEN 1408
 /* Patch buffer size */
 #define INSN_BUF_SIZE 32
 
@@ -243,12 +244,13 @@ enum bpf_stack_slot_type {
 #define BPF_REG_SIZE 8	/* size of eBPF register in bytes */
 
 /*
- * Largest number of BPF_REG_SIZE stack slots a single frame can have. A frame
- * may use any part of the MAX_BPF_STACK budget; check_max_stack_depth()
- * enforces the bound on the combined depth of frames sharing the kernel stack
- * and on each frame using a private stack.
+ * Largest number of BPF_REG_SIZE stack slots a single frame can have, sized
+ * for the largest stack budget any JIT supports. A frame may use any part of
+ * its program's budget; check_max_stack_depth() enforces the budget on the
+ * combined depth of frames sharing the kernel stack and on each frame using
+ * a private stack.
  */
-#define MAX_BPF_STACK_SLOTS	(MAX_BPF_STACK / BPF_REG_SIZE)
+#define MAX_BPF_STACK_SLOTS	(MAX_BPF_STACK_JIT / BPF_REG_SIZE)
 
 /* 4-byte stack slot granularity for liveness analysis */
 #define BPF_HALF_REG_SIZE	4
include/linux/filter.h +5 -0
index 422284b4fa96..5688bc647df6 100644
@@ -98,6 +98,11 @@ struct ctl_table_header;
 
 /* BPF program can access up to 512 bytes of stack space. */
 #define MAX_BPF_STACK	512
+/*
+ * Stack budget of a program on a JIT that lays out frames of that size.
+ * The interpreter and JITs without such support keep MAX_BPF_STACK.
+ */
+#define MAX_BPF_STACK_JIT	2048
 
 /* Helper macros for filter block array initializers. */
 
kernel/bpf/liveness.c +1 -1
index 07eb84ae0b7f..f83254d41043 100644
@@ -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 */
tools/testing/selftests/bpf/progs/verifier_live_stack.c +3 -3
index a94365decd5f..ec27cb40dbef 100644
@@ -1953,7 +1953,7 @@ static __used __naked void fwd_parent_key_to_helper(void)
 SEC("socket")
 __log_level(2)
 __success
-__msg("call bpf_map_update_elem{{.*}}; use: fp1-8..-512 fp0-8")
+__msg("call bpf_map_update_elem{{.*}}; use: fp1-8..-2048 fp0-8")
 __naked void helper_arg_fallback_keeps_scanning(void)
 {
 	asm volatile (
@@ -2267,7 +2267,7 @@ static __used __naked void merge_leaf_read(void)
 SEC("socket")
 __log_level(2)
 __success
-__msg("call bpf_loop#181            ; use: fp2-8..-512 fp1-8..-512 fp0-8..-512")
+__msg("call bpf_loop#181            ; use: fp2-8..-2048 fp1-8..-2048 fp0-8..-2048")
 __naked void bpf_loop_two_callbacks(void)
 {
 	asm volatile (
@@ -2872,7 +2872,7 @@ __naked void narrow_store_defines_nothing(void)
 SEC("socket")
 __log_level(2)
 __msg("stack use/def subprog#{{[0-9]+}} merge_read_all_callee (d2,cs{{[0-9]+}}):")
-__msg("(79) r0 = *(u64 *)(r1 +0){{.*}}; use: fp0-8..-512")
+__msg("(79) r0 = *(u64 *)(r1 +0){{.*}}; use: fp0-8..-2048")
 __naked void merge_keeps_whole_frame_read(void)
 {
 	asm volatile (
Signature · 1 line
2.53.0
#19 lore raw

Re: [PATCH bpf-next v1 12/18] bpf: Size the per-frame verifier structures for a 2 KiB stack

TMP_STR_BUF_LEN is raised to 1408 so that bpf_fmt_stack_mask() can render all 256 slots. The commit message says the buffer grows "so that all 256 slots still fit". But every place that consumes…
Quoted 8 lines
include/linux/bpf_verifier.h +0 -0
index d8cafd3d74aa..11fa9f1f087c 100644
@@ -19,11 +19,12 @@
  * that converting umax_value to int cannot overflow.
  */
 #define BPF_MAX_VAR_SIZ	(1 << 29)

include/linux/bpf_verifier.h line 27

Quoted 10 lines
include/linux/bpf_verifier.h +5 -4
-/* size of tmp_str_buf in bpf_verifier.
- * we need at least 306 bytes to fit full stack mask representation
- * (in the "-8,-16,...,-512" form)
+/*
+ * size of tmp_str_buf in bpf_verifier.
+ * we need at least 1399 bytes to fit full stack mask representation
+ * (in the "-8,-16,...,-2048" form)
  */
-#define TMP_STR_BUF_LEN 320
+#define TMP_STR_BUF_LEN 1408

TMP_STR_BUF_LEN is raised to 1408 so that bpf_fmt_stack_mask() can render all 256 slots. The commit message says the buffer grows "so that all 256 slots still fit". But every place that consumes env->tmp_str_buf prints it through verbose() -> bpf_verifier_vlog(), which formats into a fixed kbuf:

kernel/bpf/log.c:bpf_verifier_vlog() {
    n = vscnprintf(log->kbuf, BPF_VERIFIER_TMP_LOG_SIZE, fmt, args);
}

BPF_VERIFIER_TMP_LOG_SIZE is still 1024 (include/linux/bpf_verifier.h). The precision backtracking log lines are:

kernel/bpf/backtrack.c: {
    verbose(env, "stack=%s before ", env->tmp_str_buf);
    verbose(env, "stack=%s: ", env->tmp_str_buf);
}

With a full 256-slot mask, the "stack=%s before " line is 1412 bytes and is silently cut at 1023 characters. The remaining slots and the trailing " before " / ": " separator are lost, so the next log fragment runs into the truncated mask.

The mask alone goes over the kbuf limit once roughly 168 or more slots are set. The larger tmp_str_buf therefore does not deliver the complete log line the comment and commit message promise. The extra 1 KiB only helps up to the 1023-character kbuf limit.

This commit only resizes the structures; the verifier still caps the stack at 512 bytes here. The problem becomes reachable later in the same series, in d1a4a32c6444 ("bpf, x86: Allow programs 2 KiB of stack") and 5782325bd60a ("bpf, arm64: Allow programs 2 KiB of stack"), which let bpf_jit_supports_large_stack() programs use more than 64 slots. No later commit in 00a8442f56e5..7757cddf610a changes BPF_VERIFIER_TMP_LOG_SIZE or the print sites.

The impact is limited to log readability (no memory-safety or verification-result impact), but selftests or tools that parse the stack= mask from level-2 logs will see incomplete data.

Should BPF_VERIFIER_TMP_LOG_SIZE be raised to at least TMP_STR_BUF_LEN plus a small prefix, or should the mask be emitted in pieces with several verbose() calls?

Quoted 9 lines
include/linux/bpf_verifier.h +0 -2
 /* Patch buffer size */
 #define INSN_BUF_SIZE 32
 
@@ -243,12 +244,13 @@ enum bpf_stack_slot_type {
 #define BPF_REG_SIZE 8	/* size of eBPF register in bytes */
 
 /*
- * Largest number of BPF_REG_SIZE stack slots a single frame can have. A frame
- * may use any part of the MAX_BPF_STACK budget; check_max_stack_depth()

include/linux/bpf_verifier.h enum bpf_stack_slot_type { · line 253

Quoted 10 lines
include/linux/bpf_verifier.h +6 -3
- * enforces the bound on the combined depth of frames sharing the kernel stack
- * and on each frame using a private stack.
+ * Largest number of BPF_REG_SIZE stack slots a single frame can have, sized
+ * for the largest stack budget any JIT supports. A frame may use any part of
+ * its program's budget; check_max_stack_depth() enforces the budget on the
+ * combined depth of frames sharing the kernel stack and on each frame using
+ * a private stack.
  */
-#define MAX_BPF_STACK_SLOTS	(MAX_BPF_STACK / BPF_REG_SIZE)
+#define MAX_BPF_STACK_SLOTS	(MAX_BPF_STACK_JIT / BPF_REG_SIZE)

[ ... ]

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/35909853278

author maintainer
#20 lore raw

Re: [PATCH bpf-next v1 12/18] bpf: Size the per-frame verifier structures for a 2 KiB stack

Quoted 24 lines · bot+bpf-ci
Quoted 8 lines
include/linux/bpf_verifier.h +0 -0
index d8cafd3d74aa..11fa9f1f087c 100644
@@ -19,11 +19,12 @@
  * that converting umax_value to int cannot overflow.
  */
 #define BPF_MAX_VAR_SIZ	(1 << 29)

include/linux/bpf_verifier.h line 27

Quoted 10 lines
include/linux/bpf_verifier.h +5 -4
-/* size of tmp_str_buf in bpf_verifier.
- * we need at least 306 bytes to fit full stack mask representation
- * (in the "-8,-16,...,-512" form)
+/*
+ * size of tmp_str_buf in bpf_verifier.
+ * we need at least 1399 bytes to fit full stack mask representation
+ * (in the "-8,-16,...,-2048" form)
  */
-#define TMP_STR_BUF_LEN 320
+#define TMP_STR_BUF_LEN 1408

TMP_STR_BUF_LEN is raised to 1408 so that bpf_fmt_stack_mask() can render all 256 slots. The commit message says the buffer grows "so that all 256 slots still fit". But every place that consumes env->tmp_str_buf prints it through verbose() -> bpf_verifier_vlog(), which formats into a fixed kbuf:

Quoted 7 lines
kernel/bpf/log.c:bpf_verifier_vlog() {
    n = vscnprintf(log->kbuf, BPF_VERIFIER_TMP_LOG_SIZE, fmt, args);
}

BPF_VERIFIER_TMP_LOG_SIZE is still 1024 (include/linux/bpf_verifier.h). The precision backtracking log lines are:

I will bump the size.

Quoted 59 lines
kernel/bpf/backtrack.c: {
    verbose(env, "stack=%s before ", env->tmp_str_buf);
    verbose(env, "stack=%s: ", env->tmp_str_buf);
}

With a full 256-slot mask, the "stack=%s before " line is 1412 bytes and is silently cut at 1023 characters. The remaining slots and the trailing " before " / ": " separator are lost, so the next log fragment runs into the truncated mask.

The mask alone goes over the kbuf limit once roughly 168 or more slots are set. The larger tmp_str_buf therefore does not deliver the complete log line the comment and commit message promise. The extra 1 KiB only helps up to the 1023-character kbuf limit.

This commit only resizes the structures; the verifier still caps the stack at 512 bytes here. The problem becomes reachable later in the same series, in d1a4a32c6444 ("bpf, x86: Allow programs 2 KiB of stack") and 5782325bd60a ("bpf, arm64: Allow programs 2 KiB of stack"), which let bpf_jit_supports_large_stack() programs use more than 64 slots. No later commit in 00a8442f56e5..7757cddf610a changes BPF_VERIFIER_TMP_LOG_SIZE or the print sites.

The impact is limited to log readability (no memory-safety or verification-result impact), but selftests or tools that parse the stack= mask from level-2 logs will see incomplete data.

Should BPF_VERIFIER_TMP_LOG_SIZE be raised to at least TMP_STR_BUF_LEN plus a small prefix, or should the mask be emitted in pieces with several verbose() calls?

Quoted 9 lines
include/linux/bpf_verifier.h +0 -2
 /* Patch buffer size */
 #define INSN_BUF_SIZE 32
 
@@ -243,12 +244,13 @@ enum bpf_stack_slot_type {
 #define BPF_REG_SIZE 8	/* size of eBPF register in bytes */
 
 /*
- * Largest number of BPF_REG_SIZE stack slots a single frame can have. A frame
- * may use any part of the MAX_BPF_STACK budget; check_max_stack_depth()

include/linux/bpf_verifier.h enum bpf_stack_slot_type { · line 253

Quoted 10 lines
include/linux/bpf_verifier.h +6 -3
- * enforces the bound on the combined depth of frames sharing the kernel stack
- * and on each frame using a private stack.
+ * Largest number of BPF_REG_SIZE stack slots a single frame can have, sized
+ * for the largest stack budget any JIT supports. A frame may use any part of
+ * its program's budget; check_max_stack_depth() enforces the budget on the
+ * combined depth of frames sharing the kernel stack and on each frame using
+ * a private stack.
  */
-#define MAX_BPF_STACK_SLOTS	(MAX_BPF_STACK / BPF_REG_SIZE)
+#define MAX_BPF_STACK_SLOTS	(MAX_BPF_STACK_JIT / BPF_REG_SIZE)

[ ... ]

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/35909853278

#21 lore raw

Re: [PATCH bpf-next v1 12/18] bpf: Size the per-frame verifier structures for a 2 KiB stack

In reply to Kumar Kartikeya Dwivedi

kernel/bpf/liveness.c line 18

Quoted 2 lines · Kumar Kartikeya Dwivedi
kernel/bpf/liveness.c +1 -1
-#define FRAME_HALF_SPIS		(MAX_BPF_STACK / BPF_HALF_REG_SIZE)
+#define FRAME_HALF_SPIS		(MAX_BPF_STACK_JIT / BPF_HALF_REG_SIZE)

MAX_ARG_SPILL_SLOTS in liveness.c is still 64. fp_off_to_slot() returns -1 for anything below fp-512, so
r6 = *(u64 *)(r10 - 520)
makes r6 ARG_IMPRECISE in fill_from_stack() no matter what was spilled there. The next load or store through r6 goes to record_imprecise() and marks the whole stack of every frame as read. A prog that keeps spills below fp-512 gets no help from liveness and all of its frames carry 8 word masks.

The numbers in the cover letter are for selftests that fit in 512. Pls share veristat numbers for progs that use more than that.

author maintainer
#22 lore raw

PATCH 13/18 bpf: Bound program stack use by a per-program limit

In reply to Kumar Kartikeya Dwivedi

The verifier checks every stack access and the combined depth of a call chain against MAX_BPF_STACK, which is also the frame size of the interpreter and the frame that JITs without subprogram tail call support set up for tail-call targets. A JIT that lays out frames of any size and lets a tail-called program set up its own frame does not need that limit; it only needs the verifier to bound how much stack a program uses in total.

Add bpf_jit_supports_large_stack() for a JIT to claim that, and give each program its budget through bpf_prog_stack_limit(): MAX_BPF_STACK_JIT when the JIT is requested, the program is not offloaded and the JIT supports large stacks as well as tail calls from subprograms, MAX_BPF_STACK otherwise. The latter is what lets a tail-called program set up its own frame: without it, do_misc_fixups() gives every program with tail calls a MAX_BPF_STACK frame, which a deeper frame verified against the larger budget would overrun. The verifier keeps the budget in env->stack_limit and uses it for the bounds of fixed and variable offset stack accesses, for unprivileged stack pointer arithmetic and its speculation limit, and for the combined and private stack depth checks. A frame may use any part of its program's budget. The interpreter paths keep MAX_BPF_STACK: a program whose main frame is deeper falls back to the JIT-required path of bpf_prog_select_runtime() and one with deeper subprogram frames is rejected when patching calls for the interpreter. The extra stack that may_goto and the timed may_goto instrumentation add below a frame is, as before, not counted against the budget of a JITed program and rejected past MAX_BPF_STACK for an interpreted one.

Stack liveness treats a read through a pointer of unknown offset, or a call passing a frame pointer to a subprogram, as reaching the whole frame, and widens the masks of that frame to the deepest half-slot such a read can cover. Bound that by the program's budget too: no access past it is accepted, so a program kept at MAX_BPF_STACK carries masks of two words for such frames, as before, instead of the eight that MAX_BPF_STACK_JIT needs. The three selftests matching a whole-frame read in the liveness log accept either depth.

The capability is a boolean and the budget a single constant, in the style of the other bpf_jit_supports_*() queries, rather than a per JIT
size: the budget is meant to be the same everywhere it is raised, so that programs verify identically across those architectures.

No JIT declares support yet, so every program keeps its 512-byte budget.

---
 include/linux/bpf_verifier.h                  | 20 ++++++++++
 include/linux/filter.h                        |  1 +
 kernel/bpf/core.c                             | 13 +++++++
 kernel/bpf/liveness.c                         | 39 +++++++++++--------
 kernel/bpf/verifier.c                         | 24 +++++++-----
 .../selftests/bpf/progs/verifier_live_stack.c |  6 +--
 6 files changed, 73 insertions(+), 30 deletions(-)
include/linux/bpf_verifier.h +20 -0
index 11fa9f1f087c..a5d493b3876f 100644
@@ -982,6 +982,8 @@ struct bpf_verifier_env {
 	u32 prev_jmps_processed, jmps_processed;
 	/* maximum combined stack depth */
 	u32 max_stack_depth;
+	/* stack budget of the program, see bpf_prog_stack_limit() */
+	u32 stack_limit;
 	/* total verification time */
 	u64 verification_time;
 	/* maximum number of verifier states kept in 'branching' instructions */
@@ -1235,6 +1237,24 @@ static inline int bpf_get_spi(s32 off)
 	return (-off - 1) / BPF_REG_SIZE;
 }
 
+/*
+ * Stack a program may use in total: combined over the frames of a call
+ * chain on the kernel stack, or per frame on a private stack. Any single
+ * frame may reach that deep. Only a JIT that lays out such frames may go
+ * beyond MAX_BPF_STACK, the interpreter's frame size, and only one whose
+ * tail calls let the target set up its own frame: without subprogram
+ * tail calls, do_misc_fixups() gives every program with tail calls a
+ * MAX_BPF_STACK frame, which a deeper frame would overrun.
+ */
+static inline u32 bpf_prog_stack_limit(const struct bpf_prog *prog)
+{
+	/* an offloaded program never runs on the host JIT, whatever it supports */
+	if (prog->jit_requested && !bpf_prog_is_offloaded(prog->aux) &&
+	    bpf_jit_supports_large_stack() && bpf_jit_supports_subprog_tailcalls())
+		return MAX_BPF_STACK_JIT;
+	return MAX_BPF_STACK;
+}
+
 static inline struct bpf_func_state *bpf_func(struct bpf_verifier_env *env,
 					      const struct bpf_reg_state *reg)
 {
include/linux/filter.h +1 -0
index 5688bc647df6..cdd16bdd4dfb 100644
@@ -1251,6 +1251,7 @@ bool bpf_jit_supports_ptr_xchg(void);
 bool bpf_jit_supports_arena(void);
 bool bpf_jit_supports_insn(struct bpf_insn *insn, bool in_arena);
 bool bpf_jit_supports_private_stack(void);
+bool bpf_jit_supports_large_stack(void);
 bool bpf_jit_supports_timed_may_goto(void);
 bool bpf_jit_supports_fsession(void);
 
kernel/bpf/core.c +13 -0
index 227211166dcc..fbb2d8a840ef 100644
@@ -3471,6 +3471,19 @@ bool __weak bpf_jit_supports_private_stack(void)
 	return false;
 }
 
+/*
+ * Return TRUE if the JIT lays out frames of up to MAX_BPF_STACK_JIT bytes.
+ * Its prologue, epilogue and tail call sequences must encode such frame
+ * sizes and a private stack must be sized from the program's depth. The
+ * budget is only granted alongside bpf_jit_supports_subprog_tailcalls(),
+ * whose tail calls land before the target sets up its own frame; see
+ * bpf_prog_stack_limit().
+ */
+bool __weak bpf_jit_supports_large_stack(void)
+{
+	return false;
+}
+
 void __weak arch_bpf_stack_walk(bool (*consume_fn)(void *cookie, u64 ip, u64 sp, u64 bp), void *cookie)
 {
 }
kernel/bpf/liveness.c +22 -17
index f83254d41043..f9beef6695c4 100644
@@ -36,9 +36,9 @@ enum {
  * relative index @i is at &bits[(i * FM_MASK_CNT + kind) * words]. A
  * half-slot at or past @words * BITS_PER_LONG is never read by this frame,
  * hence never live. An instruction that may read the whole frame, such as a
- * call passing a frame pointer to another subprog, widens the array to
- * FRAME_MAX_WORDS, so that the read cannot lose half-slots to a later
- * widening.
+ * call passing a frame pointer to another subprog, widens the array to the
+ * program's stack budget, the deepest an accepted program can reach, so
+ * that the read cannot lose half-slots to a later widening.
  */
 struct frame_masks {
 	u32 words;
@@ -264,12 +264,16 @@ static int mark_stack_write(struct func_instance *instance, u32 frame, u32 insn_
 
 /*
  * Mark every half-slot of @frame as possibly read by @insn_idx. This widens
- * the masks to the maximum width: a full read recorded at a narrower width
- * would leave the bits added by a later widening clear and lose part of it.
+ * the masks to the program's stack budget: a full read recorded at a narrower
+ * width would leave the bits added by a later widening clear and lose part of
+ * it, and an access past the budget is rejected by the main pass later, so no
+ * widening of an accepted program goes further.
  */
-static int mark_stack_read_all(struct func_instance *instance, u32 frame, u32 insn_idx)
+static int mark_stack_read_all(struct bpf_verifier_env *env, struct func_instance *instance,
+			       u32 frame, u32 insn_idx)
 {
-	return mark_stack_read(instance, frame, insn_idx, 0, FRAME_HALF_SPIS - 1);
+	return mark_stack_read(instance, frame, insn_idx, 0,
+			       env->stack_limit / BPF_HALF_REG_SIZE - 1);
 }
 
 /* Accumulate @src, a mask @src_words wide, into may_read of @frame at @insn_idx */
@@ -1384,7 +1388,7 @@ static int record_stack_access_off(struct func_instance *instance, s64 fp_off,
  * 'arg' is FP-derived argument to helper/kfunc or load/store that
  * reads (positive) or writes (negative) 'access_bytes' into 'use' or 'def'.
  */
-static int record_stack_access(struct func_instance *instance,
+static int record_stack_access(struct bpf_verifier_env *env, struct func_instance *instance,
 			       const struct arg_track *arg,
 			       s64 access_bytes, u32 frame, u32 insn_idx)
 {
@@ -1394,7 +1398,7 @@ static int record_stack_access(struct func_instance *instance,
 		return 0;
 	if (arg->off_cnt == 0) {
 		if (access_bytes > 0 || access_bytes == S64_MIN)
-			return mark_stack_read_all(instance, frame, insn_idx);
+			return mark_stack_read_all(env, instance, frame, insn_idx);
 		return 0;
 	}
 	if (access_bytes != S64_MIN && access_bytes < 0 && arg->off_cnt != 1)
@@ -1413,7 +1417,8 @@ static int record_stack_access(struct func_instance *instance,
  * When a pointer is ARG_IMPRECISE, conservatively mark every frame in
  * the bitmask as fully used.
  */
-static int record_imprecise(struct func_instance *instance, u32 mask, u32 insn_idx)
+static int record_imprecise(struct bpf_verifier_env *env, struct func_instance *instance,
+			    u32 mask, u32 insn_idx)
 {
 	int depth = instance->depth;
 	int f, err;
@@ -1422,7 +1427,7 @@ static int record_imprecise(struct func_instance *instance, u32 mask, u32 insn_i
 		if (!(mask & 1))
 			continue;
 		if (f <= depth) {
-			err = mark_stack_read_all(instance, f, insn_idx);
+			err = mark_stack_read_all(env, instance, f, insn_idx);
 			if (err)
 				return err;
 		}
@@ -1491,9 +1496,9 @@ static int record_load_store_access(struct bpf_verifier_env *env,
 	}
 
 	if (ptr->frame >= 0 && ptr->frame <= depth)
-		return record_stack_access(instance, ptr, sz, ptr->frame, insn_idx);
+		return record_stack_access(env, instance, ptr, sz, ptr->frame, insn_idx);
 	if (ptr->frame == ARG_IMPRECISE)
-		return record_imprecise(instance, ptr->mask, insn_idx);
+		return record_imprecise(env, instance, ptr->mask, insn_idx);
 	/* ARG_NONE: not derived from any frame pointer, skip */
 	return 0;
 }
@@ -1518,7 +1523,7 @@ static int record_arg_access(struct bpf_verifier_env *env,
 		bytes = bpf_kfunc_stack_access_bytes(env, insn, arg_idx, insn_idx);
 	} else {
 		for (int f = 0; f <= depth; f++) {
-			err = mark_stack_read_all(instance, f, insn_idx);
+			err = mark_stack_read_all(env, instance, f, insn_idx);
 			if (err)
 				return err;
 		}
@@ -1528,9 +1533,9 @@ static int record_arg_access(struct bpf_verifier_env *env,
 		return 0;
 
 	if (frame >= 0 && frame <= depth)
-		err = record_stack_access(instance, at, bytes, frame, insn_idx);
+		err = record_stack_access(env, instance, at, bytes, frame, insn_idx);
 	else if (frame == ARG_IMPRECISE)
-		err = record_imprecise(instance, at->mask, insn_idx);
+		err = record_imprecise(env, instance, at->mask, insn_idx);
 	return err;
 }
 
@@ -2040,7 +2045,7 @@ static int analyze_subprog(struct bpf_verifier_env *env,
 				if (info[subprog].at_in[j][caller_reg].frame == ARG_NONE)
 					continue;
 				for (int f = 0; f <= depth; f++) {
-					err = mark_stack_read_all(instance, f, idx);
+					err = mark_stack_read_all(env, instance, f, idx);
 					if (err)
 						goto out_free;
 				}
kernel/bpf/verifier.c +14 -10
index 8641f1a8d017..9bd7f9b3a67c 100644
@@ -3595,7 +3595,8 @@ static int check_stack_write_fixed_off(struct bpf_verifier_env *env,
 	int hist_spi = spi, hist_frame = state->frameno;
 	struct bpf_stack_state *ss = bpf_stack_slot(state, spi);
 
-	/* caller checked that off % size == 0 and -MAX_BPF_STACK <= off < 0,
+	/*
+	 * caller checked that off % size == 0 and -env->stack_limit <= off < 0,
 	 * so it's aligned access and [off, off + size) are within stack limits
 	 */
 	if (!env->allow_ptr_leaks &&
@@ -5448,7 +5449,7 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
 	if (subprog[idx].priv_stack_mode == PRIV_STACK_ADAPTIVE) {
 		if (subprog_depth > env->max_stack_depth)
 			env->max_stack_depth = subprog_depth;
-		if (subprog_depth > MAX_BPF_STACK) {
+		if (subprog_depth > env->stack_limit) {
 			verbose(env, "stack size of subprog %d is %d. Too large\n",
 				idx, subprog_depth);
 			return -EACCES;
@@ -5457,7 +5458,7 @@ static int check_max_stack_depth_subprog(struct bpf_verifier_env *env, int idx,
 		depth += subprog_depth;
 		if (depth > env->max_stack_depth)
 			env->max_stack_depth = depth;
-		if (depth > MAX_BPF_STACK) {
+		if (depth > env->stack_limit) {
 			total = 0;
 			for (tmp = idx; tmp >= 0; tmp = dinfo[tmp].caller)
 				total++;
@@ -6308,10 +6309,11 @@ static int check_ptr_to_map_access(struct bpf_verifier_env *env,
 	return 0;
 }
 
-/* Check that the stack access at the given offset is within bounds. The
+/*
+ * Check that the stack access at the given offset is within bounds. The
  * maximum valid offset is -1.
  *
- * The minimum valid offset is -MAX_BPF_STACK for writes, and
+ * The minimum valid offset is -env->stack_limit for writes, and
  * -state->allocated_stack for reads.
  */
 static int check_stack_slot_within_bounds(struct bpf_verifier_env *env,
@@ -6322,7 +6324,7 @@ static int check_stack_slot_within_bounds(struct bpf_verifier_env *env,
 	int min_valid_off;
 
 	if (t == BPF_WRITE || env->allow_uninit_stack)
-		min_valid_off = -MAX_BPF_STACK;
+		min_valid_off = -(int)env->stack_limit;
 	else
 		min_valid_off = -state->allocated_stack;
 
@@ -14728,7 +14730,8 @@ enum {
 	REASON_STACK	= -5,
 };
 
-static int retrieve_ptr_limit(const struct bpf_reg_state *ptr_reg,
+static int retrieve_ptr_limit(const struct bpf_verifier_env *env,
+			      const struct bpf_reg_state *ptr_reg,
 			      u32 *alu_limit, bool mask_to_left)
 {
 	u32 max = 0, ptr_limit = 0;
@@ -14740,7 +14743,7 @@ static int retrieve_ptr_limit(const struct bpf_reg_state *ptr_reg,
 		 * offset where we would need to deal with min/max bounds is
 		 * currently prohibited for unprivileged.
 		 */
-		max = MAX_BPF_STACK + mask_to_left;
+		max = env->stack_limit + mask_to_left;
 		ptr_limit = -ptr_reg->var_off.value;
 		break;
 	case PTR_TO_MAP_VALUE:
@@ -14860,7 +14863,7 @@ static int sanitize_ptr_alu(struct bpf_verifier_env *env,
 				     (opcode == BPF_SUB && !off_is_neg);
 	}
 
-	err = retrieve_ptr_limit(ptr_reg, &alu_limit, info->mask_to_left);
+	err = retrieve_ptr_limit(env, ptr_reg, &alu_limit, info->mask_to_left);
 	if (err < 0)
 		return err;
 
@@ -14990,7 +14993,7 @@ static int check_stack_access_for_ptr_arithmetic(
 		return -EACCES;
 	}
 
-	if (off >= 0 || off < -MAX_BPF_STACK) {
+	if (off >= 0 || off < -(int)env->stack_limit) {
 		verbose(env, "R%d stack pointer arithmetic goes out of range, "
 			"prohibited for !root; off=%d\n", regno, off);
 		return -EACCES;
@@ -21693,6 +21696,7 @@ int bpf_check(struct bpf_prog **prog, union bpf_attr *attr, bpfptr_t uattr,
 	env->bt.env = env;
 	env->prog = *prog;
 	env->ops = bpf_verifier_ops[env->prog->type];
+	env->stack_limit = bpf_prog_stack_limit(env->prog);
 
 	env->allow_ptr_leaks = bpf_allow_ptr_leaks(env->prog->aux->token);
 	env->allow_uninit_stack = bpf_allow_uninit_stack(env->prog->aux->token);
tools/testing/selftests/bpf/progs/verifier_live_stack.c +3 -3
index ec27cb40dbef..dec2230f32aa 100644
@@ -1953,7 +1953,7 @@ static __used __naked void fwd_parent_key_to_helper(void)
 SEC("socket")
 __log_level(2)
 __success
-__msg("call bpf_map_update_elem{{.*}}; use: fp1-8..-2048 fp0-8")
+__msg("call bpf_map_update_elem{{.*}}; use: fp1-8..-{{(512|2048)}} fp0-8")
 __naked void helper_arg_fallback_keeps_scanning(void)
 {
 	asm volatile (
@@ -2267,7 +2267,7 @@ static __used __naked void merge_leaf_read(void)
 SEC("socket")
 __log_level(2)
 __success
-__msg("call bpf_loop#181            ; use: fp2-8..-2048 fp1-8..-2048 fp0-8..-2048")
+__msg("call bpf_loop#181            ; use: fp2-8..-{{(512|2048)}} fp1-8..-{{(512|2048)}} fp0-8..-{{(512|2048)}}")
 __naked void bpf_loop_two_callbacks(void)
 {
 	asm volatile (
@@ -2872,7 +2872,7 @@ __naked void narrow_store_defines_nothing(void)
 SEC("socket")
 __log_level(2)
 __msg("stack use/def subprog#{{[0-9]+}} merge_read_all_callee (d2,cs{{[0-9]+}}):")
-__msg("(79) r0 = *(u64 *)(r1 +0){{.*}}; use: fp0-8..-2048")
+__msg("(79) r0 = *(u64 *)(r1 +0){{.*}}; use: fp0-8..-{{(512|2048)}}")
 __naked void merge_keeps_whole_frame_read(void)
 {
 	asm volatile (
Signature · 1 line
2.53.0
author maintainer
#23 lore raw

PATCH 14/18 selftests/bpf: Add load conditions on the program stack limit

In reply to Kumar Kartikeya Dwivedi

The stack a program may use will depend on the JIT: 2 KiB where the JIT declares support for large stacks, 512 bytes elsewhere and for interpreted programs. Tests that probe the limit therefore need to know which one is in force. Add __load_if_large_stack() and __load_if_no_large_stack() to test_loader, analogous to the JIT load conditions, backed by a one-time probe that loads a program storing at fp-2048. The probe caches only the verifier's verdict on that store: a load that fails for another reason, such as a missing capability, is reported and probed again on the next call.

---
 tools/testing/selftests/bpf/progs/bpf_misc.h  |  3 ++
 tools/testing/selftests/bpf/test_loader.c     | 24 +++++++++++
 tools/testing/selftests/bpf/testing_helpers.c | 41 +++++++++++++++++++
 tools/testing/selftests/bpf/testing_helpers.h |  1 +
 4 files changed, 69 insertions(+)
tools/testing/selftests/bpf/progs/bpf_misc.h +3 -0
index 2ced1d751ace..f3dbc3b59bff 100644
@@ -175,6 +175,9 @@
 #define __prepare_priv		__test_tag("test_prepare_priv")
 #define __load_if_JITed()	__test_tag("load_mode=jited")
 #define __load_if_no_JITed()	__test_tag("load_mode=no_jited")
+/* Whether programs may use more than 512 bytes of stack on this kernel and JIT */
+#define __load_if_large_stack()		__test_tag("stack_mode=large")
+#define __load_if_no_large_stack()	__test_tag("stack_mode=small")
 #define __stderr(msg)		__test_tag("test_expect_stderr=" msg)
 #define __stderr_unpriv(msg)	__test_tag("test_expect_stderr_unpriv=" msg)
 #define __stdout(msg)		__test_tag("test_expect_stdout=" msg)
tools/testing/selftests/bpf/test_loader.c +24 -0
index a6e3fcc1079c..25eeb1c1248b 100644
@@ -45,6 +45,11 @@ enum load_mode {
 	NO_JITED	= 1 << 1,
 };
 
+enum stack_mode {
+	LARGE_STACK	= 1 << 0,
+	SMALL_STACK	= 1 << 1,
+};
+
 struct test_subspec {
 	char *name;
 	char *description;
@@ -70,6 +75,7 @@ struct test_spec {
 	int mode_mask;
 	int arch_mask;
 	int load_mask;
+	int stack_mask;
 	int linear_sz;
 	const char *skip_reason;
 	bool prepare_priv;
@@ -425,6 +431,7 @@ static int parse_test_spec(struct test_loader *tester,
 	int err = 0;
 	u32 arch_mask = 0;
 	u32 load_mask = 0;
+	u32 stack_mask = 0;
 	struct btf *btf;
 	enum arch arch;
 
@@ -620,6 +627,16 @@ static int parse_test_spec(struct test_loader *tester,
 				err = -EINVAL;
 				goto cleanup;
 			}
+		} else if ((val = str_has_pfx(s, "stack_mode="))) {
+			if (strcmp(val, "large") == 0) {
+				stack_mask = LARGE_STACK;
+			} else if (strcmp(val, "small") == 0) {
+				stack_mask = SMALL_STACK;
+			} else {
+				PRINT_FAIL("bad stack spec: '%s'", val);
+				err = -EINVAL;
+				goto cleanup;
+			}
 		} else if ((msg = str_has_pfx(s, "test_expect_stderr="))) {
 			err = push_disasm_msg(msg, &stderr_on_next_line,
 					      &spec->priv.stderr);
@@ -659,6 +676,7 @@ static int parse_test_spec(struct test_loader *tester,
 
 	spec->arch_mask = arch_mask ?: -1;
 	spec->load_mask = load_mask ?: (JITED | NO_JITED);
+	spec->stack_mask = stack_mask ?: (LARGE_STACK | SMALL_STACK);
 
 	if (spec->mode_mask == 0)
 		spec->mode_mask = PRIV;
@@ -1331,6 +1349,7 @@ void run_subtest(struct test_loader *tester,
 {
 	struct test_subspec *subspec = unpriv ? &spec->unpriv : &spec->priv;
 	int current_runtime = is_jit_enabled() ? JITED : NO_JITED;
+	int current_stack = is_large_stack_supported() ? LARGE_STACK : SMALL_STACK;
 	struct bpf_program *tprog = NULL, *tprog_iter;
 	struct bpf_link *link, *links[32] = {};
 	struct test_spec *spec_iter;
@@ -1360,6 +1379,11 @@ void run_subtest(struct test_loader *tester,
 		return;
 	}
 
+	if ((current_stack & spec->stack_mask) == 0) {
+		test__skip();
+		return;
+	}
+
 	if (unpriv) {
 		if (!can_execute_unpriv(tester, spec)) {
 			test__skip();
tools/testing/selftests/bpf/testing_helpers.c +41 -0

47 lines not on this page · raw message

tools/testing/selftests/bpf/testing_helpers.h +1 -0
index 1c58a2f08b64..f1505108e26a 100644
@@ -59,6 +59,7 @@ struct bpf_insn;
 int get_xlated_program(int fd_prog, struct bpf_insn **buf, __u32 *cnt);
 int testing_prog_flags(void);
 bool is_jit_enabled(void);
+bool is_large_stack_supported(void);
 int stack_mprotect(void);
 
 /* Runs diff(1) on mismatch */
Signature · 1 line
2.53.0
#24 lore raw

Re: [PATCH bpf-next v1 14/18] selftests/bpf: Add load conditions on the program stack limit

A subsystem pattern flags this as potentially concerning: the new stack-limit load condition skips the subtest with a bare test__skip() that prints no reason. When a user sees a verifier_large_stack…
Quoted 18 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +3 -0
index 2ced1d751ace..f3dbc3b59bff 100644
@@ -175,6 +175,9 @@
 #define __prepare_priv		__test_tag("test_prepare_priv")
 #define __load_if_JITed()	__test_tag("load_mode=jited")
 #define __load_if_no_JITed()	__test_tag("load_mode=no_jited")
+/* Whether programs may use more than 512 bytes of stack on this kernel and JIT */
+#define __load_if_large_stack()		__test_tag("stack_mode=large")
+#define __load_if_no_large_stack()	__test_tag("stack_mode=small")
 #define __stderr(msg)		__test_tag("test_expect_stderr=" msg)
 #define __stderr_unpriv(msg)	__test_tag("test_expect_stderr_unpriv=" msg)
 #define __stdout(msg)		__test_tag("test_expect_stdout=" msg)
tools/testing/selftests/bpf/test_loader.c +0 -0
index a6e3fcc1079c..25eeb1c1248b 100644

[ ... ]

Quoted 8 lines
tools/testing/selftests/bpf/test_loader.c +1 -0
@@ -1331,6 +1349,7 @@ void run_subtest(struct test_loader *tester,
 {
 	struct test_subspec *subspec = unpriv ? &spec->unpriv : &spec->priv;
 	int current_runtime = is_jit_enabled() ? JITED : NO_JITED;
+	int current_stack = is_large_stack_supported() ? LARGE_STACK : SMALL_STACK;
 	struct bpf_program *tprog = NULL, *tprog_iter;
 	struct bpf_link *link, *links[32] = {};
 	struct test_spec *spec_iter;

[ ... ]

tools/testing/selftests/bpf/test_loader.c void run_subtest(struct test_loader *tester, · line 1386

Quoted 9 lines
tools/testing/selftests/bpf/test_loader.c +5 -0
@@ -1360,6 +1379,11 @@ void run_subtest(struct test_loader *tester,
 		return;
 	}
 
+	if ((current_stack & spec->stack_mask) == 0) {
+		test__skip();
+		return;
+	}
+

A subsystem pattern flags this as potentially concerning: the new stack-limit load condition skips the subtest with a bare test__skip() that prints no reason. When a user sees a verifier_large_stack or verifier_stack_ptr subtest reported as SKIP, they get no hint whether it was skipped because is_large_stack_supported() found the 2 KiB budget missing or present.

This matters more because the probe can also fall back to "assuming 512 bytes" when it fails for an unrelated reason. That fallback message goes to stderr before test__start_subtest_with_desc() runs, so it is not attached to the subtest that gets skipped.

Does the skip need a message like the existing skip_reason and jited-disassembly skips in run_subtest do? Or is it acceptable for these stack-mode skips to match the arch_mask and load_mask pattern right above this check, which also skip without a message?

Quoted 39 lines
tools/testing/selftests/bpf/testing_helpers.c +31 -0
index d1d60451c5bc..47fe61a1ebff 100644
@@ -517,6 +517,47 @@ bool is_jit_enabled(void)
 	return enabled;
 }
 
+/*
+ * Whether the kernel accepts a program using more than 512 bytes of stack,
+ * which depends on the JIT in use. Probed once with a program that stores
+ * at the 2 KiB depth. Only the verifier's verdict on that store is cached:
+ * a load that fails for another reason, such as a missing capability, is
+ * reported and probed again on the next call.
+ */
+bool is_large_stack_supported(void)
+{
+	static int supported = -1;
+	struct bpf_insn insns[] = {
+		BPF_ST_MEM(BPF_DW, BPF_REG_10, -2048, 0),
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	char log[1024] = {};
+	LIBBPF_OPTS(bpf_prog_load_opts, opts,
+		.log_buf = log,
+		.log_size = sizeof(log),
+		.log_level = 1,
+	);
+	int fd;
+
+	if (supported >= 0)
+		return supported;
+
+	fd = bpf_prog_load(BPF_PROG_TYPE_SOCKET_FILTER, NULL, "GPL", insns, ARRAY_SIZE(insns),
+			   &opts);
+	if (fd >= 0) {
+		close(fd);
+		supported = 1;

tools/testing/selftests/bpf/testing_helpers.c bool is_jit_enabled(void) · line 560

Quoted 10 lines
tools/testing/selftests/bpf/testing_helpers.c +10 -0
+	} else if (strstr(log, "invalid write to stack")) {
+		supported = 0;
+	} else {
+		fprintf(stderr, "%s: probe failed with errno %d, assuming 512 bytes:\n%s",
+			__func__, errno, log);
+		return false;
+	}
+	return supported;
+}
+

[ ... ]

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/35909853278

author maintainer
#25 lore raw

Re: [PATCH bpf-next v1 14/18] selftests/bpf: Add load conditions on the program stack limit

Quoted 54 lines · bot+bpf-ci
Quoted 18 lines
tools/testing/selftests/bpf/progs/bpf_misc.h +3 -0
index 2ced1d751ace..f3dbc3b59bff 100644
@@ -175,6 +175,9 @@
 #define __prepare_priv		__test_tag("test_prepare_priv")
 #define __load_if_JITed()	__test_tag("load_mode=jited")
 #define __load_if_no_JITed()	__test_tag("load_mode=no_jited")
+/* Whether programs may use more than 512 bytes of stack on this kernel and JIT */
+#define __load_if_large_stack()		__test_tag("stack_mode=large")
+#define __load_if_no_large_stack()	__test_tag("stack_mode=small")
 #define __stderr(msg)		__test_tag("test_expect_stderr=" msg)
 #define __stderr_unpriv(msg)	__test_tag("test_expect_stderr_unpriv=" msg)
 #define __stdout(msg)		__test_tag("test_expect_stdout=" msg)
tools/testing/selftests/bpf/test_loader.c +0 -0
index a6e3fcc1079c..25eeb1c1248b 100644

[ ... ]

Quoted 8 lines
tools/testing/selftests/bpf/test_loader.c +1 -0
@@ -1331,6 +1349,7 @@ void run_subtest(struct test_loader *tester,
 {
 	struct test_subspec *subspec = unpriv ? &spec->unpriv : &spec->priv;
 	int current_runtime = is_jit_enabled() ? JITED : NO_JITED;
+	int current_stack = is_large_stack_supported() ? LARGE_STACK : SMALL_STACK;
 	struct bpf_program *tprog = NULL, *tprog_iter;
 	struct bpf_link *link, *links[32] = {};
 	struct test_spec *spec_iter;

[ ... ]

tools/testing/selftests/bpf/test_loader.c void run_subtest(struct test_loader *tester, · line 1386

Quoted 9 lines
tools/testing/selftests/bpf/test_loader.c +5 -0
@@ -1360,6 +1379,11 @@ void run_subtest(struct test_loader *tester,
 		return;
 	}
 
+	if ((current_stack & spec->stack_mask) == 0) {
+		test__skip();
+		return;
+	}
+

A subsystem pattern flags this as potentially concerning: the new stack-limit load condition skips the subtest with a bare test__skip() that prints no reason. When a user sees a verifier_large_stack or verifier_stack_ptr subtest reported as SKIP, they get no hint whether it was skipped because is_large_stack_supported() found the 2 KiB budget missing or present.

This matters more because the probe can also fall back to "assuming 512 bytes" when it fails for an unrelated reason. That fallback message goes to stderr before test__start_subtest_with_desc() runs, so it is not attached to the subtest that gets skipped.

Quoted 5 lines

Does the skip need a message like the existing skip_reason and jited-disassembly skips in run_subtest do? Or is it acceptable for these stack-mode skips to match the arch_mask and load_mask pattern right above this check, which also skip without a message?

Won't fix.

Quoted 58 lines
Quoted 39 lines
tools/testing/selftests/bpf/testing_helpers.c +31 -0
index d1d60451c5bc..47fe61a1ebff 100644
@@ -517,6 +517,47 @@ bool is_jit_enabled(void)
 	return enabled;
 }
 
+/*
+ * Whether the kernel accepts a program using more than 512 bytes of stack,
+ * which depends on the JIT in use. Probed once with a program that stores
+ * at the 2 KiB depth. Only the verifier's verdict on that store is cached:
+ * a load that fails for another reason, such as a missing capability, is
+ * reported and probed again on the next call.
+ */
+bool is_large_stack_supported(void)
+{
+	static int supported = -1;
+	struct bpf_insn insns[] = {
+		BPF_ST_MEM(BPF_DW, BPF_REG_10, -2048, 0),
+		BPF_MOV64_IMM(BPF_REG_0, 0),
+		BPF_EXIT_INSN(),
+	};
+	char log[1024] = {};
+	LIBBPF_OPTS(bpf_prog_load_opts, opts,
+		.log_buf = log,
+		.log_size = sizeof(log),
+		.log_level = 1,
+	);
+	int fd;
+
+	if (supported >= 0)
+		return supported;
+
+	fd = bpf_prog_load(BPF_PROG_TYPE_SOCKET_FILTER, NULL, "GPL", insns, ARRAY_SIZE(insns),
+			   &opts);
+	if (fd >= 0) {
+		close(fd);
+		supported = 1;

tools/testing/selftests/bpf/testing_helpers.c bool is_jit_enabled(void) · line 560

Quoted 10 lines
tools/testing/selftests/bpf/testing_helpers.c +10 -0
+	} else if (strstr(log, "invalid write to stack")) {
+		supported = 0;
+	} else {
+		fprintf(stderr, "%s: probe failed with errno %d, assuming 512 bytes:\n%s",
+			__func__, errno, log);
+		return false;
+	}
+	return supported;
+}
+

[ ... ]

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/35909853278

author maintainer
#26 lore raw

PATCH 15/18 selftests/bpf: Give the 512-byte stack boundary tests a 2 KiB twin

In reply to Kumar Kartikeya Dwivedi

A number of tests pin the 512-byte stack limit: accesses just past it, call chains that add up to more than it, private stack frames and async callbacks that exceed it. Once a JIT raises the budget to 2 KiB those programs load, so mark them __load_if_no_large_stack() and add a counterpart at the 2 KiB boundary under __load_if_large_stack(), so that each kernel runs the pair that matches its budget. The combined-depth tests that were built from frames of a few hundred bytes now chain five 480-byte frames, which exceeds both budgets and keeps them valid on every architecture; the number of frames reported in the error then differs, so those messages match any count. The C tests are limited to 512 bytes per function by the compiler, hence the chains.

No kernel grants the larger budget yet, so the 512-byte tests still run everywhere and the 2 KiB twins are skipped.

---
 .../selftests/bpf/progs/async_stack_depth.c   |  75 +++++++++++
 .../bpf/progs/struct_ops_private_stack_fail.c |  47 ++++++-
 .../selftests/bpf/progs/test_global_func1.c   |  65 ++++++++++
 .../bpf/progs/test_global_func_deep_stack.c   |  33 ++++-
 .../selftests/bpf/progs/verifier_live_stack.c |   4 +-
 .../selftests/bpf/progs/verifier_raw_stack.c  |  21 +++
 .../selftests/bpf/progs/verifier_stack_ptr.c  |  53 ++++++++
 .../selftests/bpf/progs/verifier_var_off.c    |  32 +++++
 tools/testing/selftests/bpf/verifier/calls.c  | 122 ++++++++++++++----
 9 files changed, 421 insertions(+), 31 deletions(-)
tools/testing/selftests/bpf/progs/async_stack_depth.c +75 -0
index 36734683acbd..9cd874a90b39 100644
@@ -29,7 +29,49 @@ static int bad_timer_cb(void *map, int *key, struct bpf_timer *timer)
 	return buf[255] + timer_cb(NULL, NULL, NULL);
 }
 
+/*
+ * The same shapes scaled to the 2 KiB budget of JITs with large stacks. The
+ * compiler caps a single function at 512 bytes, so the depth comes from a
+ * chain of 480-byte frames.
+ */
+__attribute__((noinline))
+static int timer_cb_large_0(void *map, int *key, struct bpf_timer *timer)
+{
+	volatile char buf[480] = {};
+	return buf[69];
+}
+
+__attribute__((noinline))
+static int timer_cb_large_1(void *map, int *key, struct bpf_timer *timer)
+{
+	volatile char buf[480] = {};
+	return buf[69] + timer_cb_large_0(map, key, timer);
+}
+
+__attribute__((noinline))
+static int timer_cb_large_2(void *map, int *key, struct bpf_timer *timer)
+{
+	volatile char buf[480] = {};
+	return buf[69] + timer_cb_large_1(map, key, timer);
+}
+
+__attribute__((noinline))
+static int timer_cb_large_3(void *map, int *key, struct bpf_timer *timer)
+{
+	volatile char buf[480] = {};
+	return buf[69] + timer_cb_large_2(map, key, timer);
+}
+
+/* 5 * 480 = 2400 bytes on its own */
+__attribute__((noinline))
+static int bad_timer_cb_large(void *map, int *key, struct bpf_timer *timer)
+{
+	volatile char buf[480] = {};
+	return buf[255] + timer_cb_large_3(map, key, timer);
+}
+
 SEC("tc")
+__load_if_no_large_stack()
 __failure __msg("combined stack size of 2 calls is")
 int pseudo_call_check(struct __sk_buff *ctx)
 {
@@ -44,7 +86,25 @@ int pseudo_call_check(struct __sk_buff *ctx)
 	return bpf_timer_set_callback(&elem->timer, timer_cb) + buf[0];
 }
 
+/* main plus the four frames under timer_cb_large_3: 2400 bytes */
 SEC("tc")
+__load_if_large_stack()
+__failure __msg("combined stack size of 5 calls is")
+int pseudo_call_check_large(struct __sk_buff *ctx)
+{
+	struct hmap_elem *elem;
+	volatile char buf[480] = {};
+
+	elem = bpf_map_lookup_elem(&hmap, &(int){0});
+	if (!elem)
+		return 0;
+
+	timer_cb_large_3(NULL, NULL, NULL);
+	return bpf_timer_set_callback(&elem->timer, timer_cb_large_3) + buf[0];
+}
+
+SEC("tc")
+__load_if_no_large_stack()
 __failure __msg("combined stack size of 2 calls is")
 int async_call_root_check(struct __sk_buff *ctx)
 {
@@ -58,4 +118,19 @@ int async_call_root_check(struct __sk_buff *ctx)
 	return bpf_timer_set_callback(&elem->timer, bad_timer_cb) + buf[0];
 }
 
+SEC("tc")
+__load_if_large_stack()
+__failure __msg("combined stack size of 5 calls is")
+int async_call_root_check_large(struct __sk_buff *ctx)
+{
+	struct hmap_elem *elem;
+	volatile char buf[480] = {};
+
+	elem = bpf_map_lookup_elem(&hmap, &(int){0});
+	if (!elem)
+		return 0;
+
+	return bpf_timer_set_callback(&elem->timer, bad_timer_cb_large) + buf[0];
+}
+
 char _license[] SEC("license") = "GPL";
tools/testing/selftests/bpf/progs/struct_ops_private_stack_fail.c +44 -3

67 lines not on this page · raw message

tools/testing/selftests/bpf/progs/test_global_func1.c +65 -0

73 lines not on this page · raw message

tools/testing/selftests/bpf/progs/test_global_func_deep_stack.c +32 -1
index 1b634b543b62..edb8a223a3cb 100644
@@ -67,12 +67,30 @@ int XCAT(f, n)(unsigned long a)                  \
 #define F_31 F_30       FN(31, 30)
 #define F_32 F_31       FN(32, 31)
 
+/* Same, with a 480-byte frame, to exceed the 2 KiB budget of large stacks. */
+#define FNB(n, prev) \
+__attribute__((noinline))                        \
+int XCAT(f, n)(unsigned long a)                  \
+{                                                \
+	volatile char buf[480] = {};             \
+	volatile long b = XCAT(f, prev)(a - 1);  \
+	if (!b)                                  \
+		return 0;                        \
+	return b + buf[479] + 1;                 \
+}
+
+#define F_33 F_32       FNB(33, 32)
+#define F_34 F_33       FNB(34, 33)
+#define F_35 F_34       FNB(35, 34)
+#define F_36 F_35       FNB(36, 35)
+#define F_37 F_36       FNB(37, 36)
+
 #define CAT2(a, b) a ## b
 #define XCAT2(a, b) CAT2(a, b)
 
 #define F(n) XCAT2(F_, n)
 
-F(32)
+F(37)
 
 /* Ensure that even 32 levels deep, the function verifies. */
 SEC("syscall")
@@ -88,8 +106,21 @@ int global_func_deep_stack_success(struct __sk_buff *skb)
  * the size.
  */
 SEC("syscall")
+__load_if_no_large_stack()
 __failure __msg("combined stack size of 34 calls")
 int global_func_deep_stack_fail(struct __sk_buff *skb)
 {
 	return f32(123);
 }
+
+/*
+ * Five 480-byte frames on top of the chain: 5 * 480 + 33 * 16 = 2928 bytes,
+ * more than the 2 KiB budget of JITs with large stacks, and more than 512
+ * bytes after the second frame everywhere else.
+ */
+SEC("syscall")
+__failure __msg("combined stack size of {{[0-9]+}} calls")
+int global_func_deep_stack_fail_large(struct __sk_buff *skb)
+{
+	return f37(123);
+}
tools/testing/selftests/bpf/progs/verifier_live_stack.c +2 -2
index dec2230f32aa..7be813f06a5a 100644
@@ -318,7 +318,7 @@ struct {
 } map_array SEC(".maps");
 
 SEC("socket")
-__failure __msg("invalid read from stack R2 off=-1024 size=8")
+__failure __msg("invalid read from stack R2 off=-4096 size=8")
 __flag(BPF_F_TEST_STATE_FREQ)
 __naked unsigned long caller_stack_write_tail_call(void)
 {
@@ -329,7 +329,7 @@ __naked unsigned long caller_stack_write_tail_call(void)
         "if r0 != 42 goto 1f;"
         "goto 2f;"
   "1:"
-        "*(u64 *)(r10 - 8) = -1024;"
+        "*(u64 *)(r10 - 8) = -4096;"
   "2:"
         "r1 = r6;"
         "r2 = r10;"
tools/testing/selftests/bpf/progs/verifier_raw_stack.c +21 -0
index 9f0f48ecb421..0fe631411b9c 100644
@@ -240,6 +240,7 @@ __naked void load_bytes_spilled_regs_data(void)
 
 SEC("tc")
 __description("raw_stack: skb_load_bytes, invalid access 1")
+__load_if_no_large_stack()
 __failure __msg("invalid write to stack R3 off=-513 size=8")
 __naked void load_bytes_invalid_access_1(void)
 {
@@ -257,6 +258,26 @@ __naked void load_bytes_invalid_access_1(void)
 	: __clobber_all);
 }
 
+SEC("tc")
+__description("raw_stack: skb_load_bytes, invalid access 1, large stack")
+__load_if_large_stack()
+__failure __msg("invalid write to stack R3 off=-2049 size=8")
+__naked void load_bytes_invalid_access_1_large(void)
+{
+	asm volatile ("					\
+	r2 = 4;						\
+	r6 = r10;					\
+	r6 += -2049;					\
+	r3 = r6;					\
+	r4 = 8;						\
+	call %[bpf_skb_load_bytes];			\
+	r0 = *(u64*)(r6 + 0);				\
+	exit;						\
+"	:
+	: __imm(bpf_skb_load_bytes)
+	: __clobber_all);
+}
+
 SEC("tc")
 __description("raw_stack: skb_load_bytes, invalid access 2")
 __failure __msg("invalid write to stack R3 off=-1 size=8")
tools/testing/selftests/bpf/progs/verifier_stack_ptr.c +53 -0

85 lines not on this page · raw message

tools/testing/selftests/bpf/progs/verifier_var_off.c +32 -0
index a63e33675091..399884911ea5 100644
@@ -406,6 +406,7 @@ __naked void zero_sized_access_max_out_of_bound(void)
 
 SEC("lwt_in")
 __description("indirect variable-offset stack access, min out of bound")
+__load_if_no_large_stack()
 __failure __msg("invalid variable-offset read from stack R2")
 __naked void access_min_out_of_bound(void)
 {
@@ -433,6 +434,37 @@ __naked void access_min_out_of_bound(void)
 	: __clobber_all);
 }
 
+SEC("lwt_in")
+__description("indirect variable-offset stack access, min out of bound, large stack")
+__load_if_large_stack()
+__failure __msg("invalid variable-offset read from stack R2")
+__naked void access_min_out_of_bound_large(void)
+{
+	asm volatile ("					\
+	/* Fill the top 8 bytes of the stack */		\
+	r2 = 0;						\
+	*(u64*)(r10 - 8) = r2;				\
+	/* Get an unknown value */			\
+	r2 = *(u32*)(r1 + 0);				\
+	/* Make it small and 4-byte aligned */		\
+	r2 &= 4;					\
+	r2 -= 2052;					\
+	/*						\
+	 * add it to fp.  We now have either fp-2052 or fp-2048, but\
+	 * we don't know which				\
+	 */						\
+	r2 += r10;					\
+	/* dereference it indirectly */			\
+	r1 = %[map_hash_8b] ll;				\
+	call %[bpf_map_lookup_elem];			\
+	r0 = 0;						\
+	exit;						\
+"	:
+	: __imm(bpf_map_lookup_elem),
+	  __imm_addr(map_hash_8b)
+	: __clobber_all);
+}
+
 SEC("cgroup/skb")
 __description("indirect variable-offset stack access, min_off < min_initialized")
 __success
tools/testing/selftests/bpf/verifier/calls.c +97 -25

200 lines not on this page · raw message

Signature · 1 line
2.53.0
author maintainer
#27 lore raw

PATCH 16/18 bpf, x86: Allow programs 2 KiB of stack

In reply to Kumar Kartikeya Dwivedi

The x86-64 JIT encodes frame sizes as 32-bit immediates in its prologue, epilogue and tail call sequences, a tail call pops the frame of the program making it and lands in the target's prologue before the target allocates its own frame, and private stacks are allocated from each program's depth, so nothing in it depends on frames staying within 512 bytes. Report bpf_jit_supports_large_stack(), which raises the budget of JITed programs to MAX_BPF_STACK_JIT: 2 KiB combined over a call chain, or per frame on a private stack, with no separate limit on a single frame. Interpreted programs keep 512 bytes.

The worst case kernel stack use of a chain of tail calls grows
accordingly: the callers of a tail call may still leave at most 256 bytes on the stack, so 33 programs can accumulate 8 KiB of dead frames below the last one, which may now use 2 KiB instead of 512 bytes, for a little over 10 KiB in total on a 16 KiB kernel stack. The per-cpu memory behind a private stack grows in proportion to the frames a program asks for, up to 2 KiB plus guards per frame.

The budget does not depend on the privileges of the loader: an unprivileged program cannot call other BPF functions, so a tail call from one leaves no frame behind and its worst case is a single 2 KiB frame. Programs nested through helpers or attach points, such as a tracing program entered from a helper of a networking program, are not accounted against each other before or after this change; each level of nesting may now add up to 1.5 KiB more.

The verifier state of a frame grows with the stack it uses, up to four times as many stack slots as before; the allocation is on demand, so only programs using deep frames pay for them.

---
 Documentation/bpf/bpf_design_QA.rst | 10 +++++++---
 arch/x86/net/bpf_jit_comp.c         | 12 ++++++++++++
 2 files changed, 19 insertions(+), 3 deletions(-)
Documentation/bpf/bpf_design_QA.rst +7 -3
index eb19c945f4d5..be5fc4ac00d6 100644
@@ -221,9 +221,13 @@ newer kernels. BPF programs need to change accordingly when this happens.
 
 Q: How much stack space a BPF program uses?
 -------------------------------------------
-A: Currently all program types are limited to 512 bytes of stack
-space, but the verifier computes the actual amount of stack used
-and both interpreter and most JITed code consume necessary amount.
+A: A program may use up to 2 KiB of stack, combined over its call
+chain, when the JIT of the architecture reports support for large
+stacks (currently x86-64); a single function may use all of it, and
+every frame of a program running on a private stack gets the whole
+amount. Elsewhere, and whenever the interpreter is used, the limit is
+512 bytes. The verifier computes the actual amount of stack used and
+both interpreter and most JITed code consume necessary amount.
 
 Q: Can BPF be offloaded to HW?
 ------------------------------
arch/x86/net/bpf_jit_comp.c +12 -0
index d4a980140b48..d6998c909754 100644
@@ -4452,6 +4452,18 @@ bool bpf_jit_supports_subprog_tailcalls(void)
 	return true;
 }
 
+/*
+ * Frame sizes are 32-bit immediates in the prologue, epilogue and tail call
+ * sequences, a tail call pops the caller's frame and lands in the target's
+ * prologue before the target allocates its own, and private stacks are
+ * allocated from the program's own depth, so MAX_BPF_STACK_JIT frames need
+ * nothing special.
+ */
+bool bpf_jit_supports_large_stack(void)
+{
+	return true;
+}
+
 bool bpf_jit_supports_percpu_insn(void)
 {
 	return true;
Signature · 1 line
2.53.0
#28 lore raw

Re: [PATCH bpf-next v1 16/18] bpf, x86: Allow programs 2 KiB of stack

Is the interpreter limit stated correctly here? The text says "whenever the interpreter is used, the limit is 512 bytes" in a paragraph where 2 KiB is defined as combined over the call chain.
Quoted 8 lines
Documentation/bpf/bpf_design_QA.rst +0 -0
index eb19c945f4d5..be5fc4ac00d6 100644
@@ -221,9 +221,13 @@ newer kernels. BPF programs need to change accordingly when this happens.
 
 Q: How much stack space a BPF program uses?
 -------------------------------------------

Documentation/bpf/bpf_design_QA.rst newer kernels. BPF programs need to change accordingly when this happens. · line 230

Quoted 10 lines
Documentation/bpf/bpf_design_QA.rst +7 -3
-A: Currently all program types are limited to 512 bytes of stack
-space, but the verifier computes the actual amount of stack used
-and both interpreter and most JITed code consume necessary amount.
+A: A program may use up to 2 KiB of stack, combined over its call
+chain, when the JIT of the architecture reports support for large
+stacks (currently x86-64); a single function may use all of it, and
+every frame of a program running on a private stack gets the whole
+amount. Elsewhere, and whenever the interpreter is used, the limit is
+512 bytes. The verifier computes the actual amount of stack used and
+both interpreter and most JITed code consume necessary amount.

Is the interpreter limit stated correctly here? The text says "whenever the interpreter is used, the limit is 512 bytes" in a paragraph where 2 KiB is defined as combined over the call chain.

When bpf_jit_supports_large_stack() returns true, a program with jit_requested set is verified against MAX_BPF_STACK_JIT (2048) in bpf_check() via env->stack_limit = bpf_prog_stack_limit(env->prog), and check_max_stack_depth_subprog() bounds the combined depth of the call chain by that limit.

If JIT compilation then fails with anything other than -EFAULT (for example, a subprogram not being jited returns -ENOTSUPP in bpf_jit_subprogs(), or an allocation failure during blinding occurs) and CONFIG_BPF_JIT_ALWAYS_ON is not set, bpf_jit_subprogs() restores the instructions, clears prog->jit_requested, and bpf_fixup_call_args() falls back to the interpreter. The interpreter checks on that path are per frame in bpf_patch_call_args():

    int bpf_patch_call_args(struct bpf_insn *insn, u32 stack_depth)
    {
        stack_depth = max_t(u32, stack_depth, 1);
        /* Prevent out-of-bounds read to interpreters_args */
        if (stack_depth > MAX_BPF_STACK)
            return -EINVAL;

and bpf_prog_select_interpreter() for the main frame.

A chain of four subprograms each using 512 bytes (2048 combined) would be accepted by the verifier and run in the interpreter, whereas before this patch the combined chain was capped at 512. Each interpreter frame has its own stack array, so this is not an out-of-bounds access. Should the text clarify that the interpreter's 512 byte limit applies per function, or should the fallback path reject a chain whose combined depth exceeds MAX_BPF_STACK?

[ ... ]

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/35909853278

author maintainer
#29 lore raw

Re: [PATCH bpf-next v1 16/18] bpf, x86: Allow programs 2 KiB of stack

Quoted 46 lines · bot+bpf-ci
Quoted 8 lines
Documentation/bpf/bpf_design_QA.rst +0 -0
index eb19c945f4d5..be5fc4ac00d6 100644
@@ -221,9 +221,13 @@ newer kernels. BPF programs need to change accordingly when this happens.
 
 Q: How much stack space a BPF program uses?
 -------------------------------------------

Documentation/bpf/bpf_design_QA.rst newer kernels. BPF programs need to change accordingly when this happens. · line 230

Quoted 10 lines
Documentation/bpf/bpf_design_QA.rst +7 -3
-A: Currently all program types are limited to 512 bytes of stack
-space, but the verifier computes the actual amount of stack used
-and both interpreter and most JITed code consume necessary amount.
+A: A program may use up to 2 KiB of stack, combined over its call
+chain, when the JIT of the architecture reports support for large
+stacks (currently x86-64); a single function may use all of it, and
+every frame of a program running on a private stack gets the whole
+amount. Elsewhere, and whenever the interpreter is used, the limit is
+512 bytes. The verifier computes the actual amount of stack used and
+both interpreter and most JITed code consume necessary amount.

Is the interpreter limit stated correctly here? The text says "whenever the interpreter is used, the limit is 512 bytes" in a paragraph where 2 KiB is defined as combined over the call chain.

When bpf_jit_supports_large_stack() returns true, a program with jit_requested set is verified against MAX_BPF_STACK_JIT (2048) in bpf_check() via env->stack_limit = bpf_prog_stack_limit(env->prog), and check_max_stack_depth_subprog() bounds the combined depth of the call chain by that limit.

If JIT compilation then fails with anything other than -EFAULT (for example, a subprogram not being jited returns -ENOTSUPP in bpf_jit_subprogs(), or an allocation failure during blinding occurs) and CONFIG_BPF_JIT_ALWAYS_ON is not set, bpf_jit_subprogs() restores the instructions, clears prog->jit_requested, and bpf_fixup_call_args() falls back to the interpreter. The interpreter checks on that path are per frame in bpf_patch_call_args():

    int bpf_patch_call_args(struct bpf_insn *insn, u32 stack_depth)
    {
        stack_depth = max_t(u32, stack_depth, 1);
        /* Prevent out-of-bounds read to interpreters_args */
        if (stack_depth > MAX_BPF_STACK)
            return -EINVAL;

and bpf_prog_select_interpreter() for the main frame.

Quoted 8 lines

A chain of four subprograms each using 512 bytes (2048 combined) would be accepted by the verifier and run in the interpreter, whereas before this patch the combined chain was capped at 512. Each interpreter frame has its own stack array, so this is not an out-of-bounds access. Should the text clarify that the interpreter's 512 byte limit applies per function, or should the fallback path reject a chain whose combined depth exceeds MAX_BPF_STACK?

It is indeed slightly confusnig, will reword.

Quoted 8 lines

[ ... ]

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/35909853278

author maintainer
#30 lore raw

PATCH 17/18 bpf, arm64: Allow programs 2 KiB of stack

In reply to Kumar Kartikeya Dwivedi

The arm64 JIT sets up a frame with an add/sub immediate, which encodes up to 4 KiB directly, addresses the BPF stack relative to SP or the private stack pointer with offsets that fall back to a scratch register when they do not fit the load/store immediate, and a tail call pops the current frame and lands in the target's prologue before the target sets up its own. The exception callback reuses the frame record of the main program and does not depend on its size. Report bpf_jit_supports_large_stack() to give JITed programs the same 2 KiB budget as on x86-64.

Tested on an emulated arm64 guest with programs loaded and run through the raw bpf() syscall: a 2 KiB frame, a 2 KiB frame with may_goto, a chain of four 512-byte frames, and a tail call from a program with a 2 KiB frame into another one; a 2056-byte frame and five 512-byte frames are rejected. The selftest suite was not run on arm64.

---
 Documentation/bpf/bpf_design_QA.rst | 10 +++++-----
 arch/arm64/net/bpf_jit_comp.c       |  5 +++++
 2 files changed, 10 insertions(+), 5 deletions(-)
Documentation/bpf/bpf_design_QA.rst +5 -5
index be5fc4ac00d6..f4e4a7f4f9fd 100644
@@ -223,11 +223,11 @@ Q: How much stack space a BPF program uses?
 -------------------------------------------
 A: A program may use up to 2 KiB of stack, combined over its call
 chain, when the JIT of the architecture reports support for large
-stacks (currently x86-64); a single function may use all of it, and
-every frame of a program running on a private stack gets the whole
-amount. Elsewhere, and whenever the interpreter is used, the limit is
-512 bytes. The verifier computes the actual amount of stack used and
-both interpreter and most JITed code consume necessary amount.
+stacks (currently x86-64 and arm64); a single function may use all of
+it, and every frame of a program running on a private stack gets the
+whole amount. Elsewhere, and whenever the interpreter is used, the
+limit is 512 bytes. The verifier computes the actual amount of stack
+used and both interpreter and most JITed code consume necessary amount.
 
 Q: Can BPF be offloaded to HW?
 ------------------------------
arch/arm64/net/bpf_jit_comp.c +5 -0
index 6c04fee46876..d92d7754578a 100644
@@ -2485,6 +2485,11 @@ bool bpf_jit_supports_subprog_tailcalls(void)
 	return true;
 }
 
+bool bpf_jit_supports_large_stack(void)
+{
+	return true;
+}
+
 static void invoke_bpf_prog(struct jit_ctx *ctx, struct bpf_tramp_node *node,
 			    int bargs_off, int retval_off, int run_ctx_off,
 			    bool save_ret)
Signature · 1 line
2.53.0
author maintainer
#31 lore raw

PATCH 18/18 selftests/bpf: Test the 2 KiB stack budget

In reply to Kumar Kartikeya Dwivedi

Add tests for the stack budget of JITs with large stack support: a single 2 KiB frame, with and without may_goto, four 512-byte frames that fit the budget and five that do not, a 512-byte frame calling a 1536-byte static subprog, global subprog or bpf_loop() callback and the same with eight bytes too many, variable offset writes reaching exactly the budget and past it, a tail call made from a 1 KiB frame, and two 2 KiB frames on a private stack, where each frame gets the whole budget. A program with a 2 KiB frame is checked to be rejected wherever the budget is 512 bytes.

Two tests run such programs: a tail call made from a subprog with a 1536-byte frame under a 240-byte caller into a program with a 2 KiB frame, and a struct_ops program on a private stack calling a subprog when both frames are 2 KiB.

---
 .../bpf/prog_tests/struct_ops_private_stack.c |  31 ++
 .../selftests/bpf/prog_tests/tailcalls.c      |  42 ++
 .../selftests/bpf/prog_tests/verifier.c       |   2 +
 .../progs/struct_ops_private_stack_large.c    |  51 +++
 .../bpf/progs/tailcall_large_stack.c          |  62 +++
 .../bpf/progs/verifier_large_stack.c          | 377 ++++++++++++++++++
 6 files changed, 565 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/progs/struct_ops_private_stack_large.c
 create mode 100644 tools/testing/selftests/bpf/progs/tailcall_large_stack.c
 create mode 100644 tools/testing/selftests/bpf/progs/verifier_large_stack.c
tools/testing/selftests/bpf/prog_tests/struct_ops_private_stack.c +31 -0
index 98db9bafa44b..2b3ec2b79091 100644
@@ -4,6 +4,7 @@
 #include "struct_ops_private_stack.skel.h"
 #include "struct_ops_private_stack_fail.skel.h"
 #include "struct_ops_private_stack_recur.skel.h"
+#include "struct_ops_private_stack_large.skel.h"
 
 #if defined(__x86_64__) || defined(__aarch64__) || defined(__powerpc64__)
 static void test_private_stack(void)
@@ -78,6 +79,34 @@ static void test_private_stack_recur(void)
 	struct_ops_private_stack_recur__destroy(skel);
 }
 
+/* Two frames of 2 KiB each on the private stack */
+static void test_private_stack_large(void)
+{
+	struct struct_ops_private_stack_large *skel;
+	struct bpf_link *link;
+
+	if (!is_large_stack_supported()) {
+		test__skip();
+		return;
+	}
+
+	skel = struct_ops_private_stack_large__open_and_load();
+	if (!ASSERT_OK_PTR(skel, "struct_ops_private_stack_large__open_and_load"))
+		return;
+
+	link = bpf_map__attach_struct_ops(skel->maps.testmod_1);
+	if (!ASSERT_OK_PTR(link, "attach_struct_ops"))
+		goto cleanup;
+
+	ASSERT_OK(trigger_module_test_read(256), "trigger_read");
+
+	ASSERT_EQ(skel->bss->val, 100 + 30 + 12, "val");
+
+	bpf_link__destroy(link);
+cleanup:
+	struct_ops_private_stack_large__destroy(skel);
+}
+
 static void __test_struct_ops_private_stack(void)
 {
 	if (test__start_subtest("private_stack"))
@@ -86,6 +115,8 @@ static void __test_struct_ops_private_stack(void)
 		test_private_stack_fail();
 	if (test__start_subtest("private_stack_recur"))
 		test_private_stack_recur();
+	if (test__start_subtest("private_stack_large"))
+		test_private_stack_large();
 }
 #else
 static void __test_struct_ops_private_stack(void)
tools/testing/selftests/bpf/prog_tests/tailcalls.c +42 -0

58 lines not on this page · raw message

tools/testing/selftests/bpf/prog_tests/verifier.c +2 -0
index 4f1e1c1cd5ab..ced8a2f1c89c 100644
@@ -59,6 +59,7 @@
 #include "verifier_kfunc_uninit.skel.h"
 #include "verifier_kfunc_uninit_multi.skel.h"
 #include "verifier_ld_ind.skel.h"
+#include "verifier_large_stack.skel.h"
 #include "verifier_ldsx.skel.h"
 #include "verifier_leak_ptr.skel.h"
 #include "verifier_linked_scalars.skel.h"
@@ -229,6 +230,7 @@ void test_verifier_kfunc_uninit(void)         { RUN_TESTS(verifier_kfunc_uninit)
 void test_verifier_kfunc_uninit_multi(void)   { RUN_TESTS(verifier_kfunc_uninit_multi); }
 void test_verifier_load_acquire(void)         { RUN(verifier_load_acquire); }
 void test_verifier_ld_ind(void)               { RUN(verifier_ld_ind); }
+void test_verifier_large_stack(void)          { RUN(verifier_large_stack); }
 void test_verifier_ldsx(void)                  { RUN(verifier_ldsx); }
 void test_verifier_leak_ptr(void)             { RUN(verifier_leak_ptr); }
 void test_verifier_linked_scalars(void)       { RUN(verifier_linked_scalars); }
tools/testing/selftests/bpf/progs/struct_ops_private_stack_large.c new file +51 -0

51 lines not on this page · raw message

tools/testing/selftests/bpf/progs/tailcall_large_stack.c new file +62 -0

62 lines not on this page · raw message

tools/testing/selftests/bpf/progs/verifier_large_stack.c new file +377 -0

377 lines not on this page · raw message

Signature · 1 line
2.53.0
#32 lore raw

Re: [PATCH bpf-next v1 18/18] selftests/bpf: Test the 2 KiB stack budget

A subsystem pattern flags this as potentially concerning: The BPF selftests guide recommends always including a reason string in the skip message so future debuggers know why the test was skipped.…
Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/struct_ops_private_stack.c +0 -0
index 98db9bafa44b..2b3ec2b79091 100644

[ ... ]

Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/struct_ops_private_stack.c +0 -0
@@ -78,6 +79,34 @@ static void test_private_stack_recur(void)
 	struct_ops_private_stack_recur__destroy(skel);
 }
 

tools/testing/selftests/bpf/prog_tests/struct_ops_private_stack.c static void test_private_stack_recur(void) · line 91

Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/struct_ops_private_stack.c +10 -0
+/* Two frames of 2 KiB each on the private stack */
+static void test_private_stack_large(void)
+{
+	struct struct_ops_private_stack_large *skel;
+	struct bpf_link *link;
+
+	if (!is_large_stack_supported()) {
+		test__skip();
+		return;
+	}

A subsystem pattern flags this as potentially concerning: The BPF selftests guide recommends always including a reason string in the skip message so future debuggers know why the test was skipped. When the probe gets a clean "invalid write to stack" rejection, is_large_stack_supported() prints nothing, and the subtest shows only SKIP with no indication that the reason is missing large stack support.

The test_loader's run_subtest() prints a reason (printf("%s:SKIP: %s\n", __func__, spec->skip_reason)) before calling test__skip(), but here the skip is silent. On the other hand, a bare test__skip() with no printf is the most common idiom in prog_tests (about 90 of 149 call sites follow this pattern, and the #else branch of this same file does the same). Could this include a skip reason, or is silent skipping acceptable BPF selftest convention?

[ ... ]

Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/tailcalls.c +0 -0
index c5c9d6c359bb..c5e3f198ca7f 100644

[ ... ]

Quoted 15 lines
tools/testing/selftests/bpf/prog_tests/tailcalls.c +11 -0
@@ -1953,6 +1954,45 @@ static void test_tailcall_bpf2bpf_fexit_links(void)
 	tailcall_bpf2bpf2__destroy(skel_tc);
 }
 
+/*
+ * test_tailcall_large_stack runs a tail call made from a subprog with a 1536
+ * byte frame, under a 240-byte caller, into a program with a 2 KiB frame:
+ *
+ * entry (240) --call-> subprog_tail (1536) --tailcall-> classifier_0 (2048)
+ */
+static void test_tailcall_large_stack(void)
+{
+	struct tailcall_large_stack *skel;
+	int err, prog_fd, map_fd, key = 0;
+	char buff[128] = {};

tools/testing/selftests/bpf/prog_tests/tailcalls.c static void test_tailcall_bpf2bpf_fexit_links(void) · line 1977

Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/tailcalls.c +10 -0
+	LIBBPF_OPTS(bpf_test_run_opts, topts,
+		    .data_in = buff,
+		    .data_size_in = sizeof(buff),
+		    .repeat = 1,
+	);
+
+	if (!is_large_stack_supported()) {
+		test__skip();
+		return;
+	}

The same pattern appears here: when is_large_stack_supported() returns false, test__skip() is called with no reason string. Could this also benefit from a skip message?

[ ... ]

Quoted 7 lines
tools/testing/selftests/bpf/progs/verifier_large_stack.c new file +1 -0
new file mode 100644
index 000000000000..2d4c81a3f0cb
@@ -0,0 +1,377 @@
+// SPDX-License-Identifier: GPL-2.0

tools/testing/selftests/bpf/progs/verifier_large_stack.c line 11

Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_large_stack.c new file +10 -0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+/*
+ * Programs may use MAX_BPF_STACK_JIT (2 KiB) of stack on JITs that support
+ * large stacks, combined over a call chain, with no separate limit on a
+ * single frame. Interpreted programs and other JITs keep 512 bytes.
+ */

A subsystem pattern flags this as potentially concerning: Several tests in this new file appear to be 2 KiB versions of tests that already exist elsewhere in the same directory.

For instance, frame_2048_with_may_goto is the same program as stack_check_size_512_with_may_goto_jit in verifier_stack_ptr.c (r1 = r10; r1 += -512; r0 = 42; *(u32*)(r1 + 0) = r0; may_goto ...; exit), with only -512 changed to -2048 and __load_if_JITed() changed to __load_if_large_stack().

Similarly, single_frame_2048 / single_frame_2048_no_large_stack check the single-frame boundary that verifier_stack_ptr.c already covers with stack_check_size_gt_512 and the new stack_check_size_gt_2048 (fp-2056).

The var_off_write_to_2048/2056 tests check variable-offset stack bounds, which verifier_var_off.c already covers (it gained access_min_out_of_bound_large in the earlier patch in this series).

The private_stack_two_frames test follows verifier_private_stack.c's "Private stack, subtree > MAX_BPF_STACK" test, including the same __log_level(4) "stack depth max" / "subprog N (...) stack" messages.

The BPF selftests guide asks whether variants like these belong as new cases in the existing files instead of a new file, especially since the earlier patch in this series (2d0faaadf6a8) already places its 2 KiB versions next to the originals.

On the other hand, this new file does group tests for the 2 KiB stack feature, and several behaviors (four 512-byte frames that fit, a tail call from a 1 KiB frame, 1536-byte global subprogs and callbacks) cannot occur under the 512-byte budget, so they have no existing counterpart. Adding one verifier_<feature>.c file per feature is also common in BPF selftests (verifier_private_stack.c is an example). Could you clarify whether the overlap cases should be integrated into existing files, or is a new file the intended organization here?

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/35909853278

author maintainer
#33 lore raw

Re: [PATCH bpf-next v1 18/18] selftests/bpf: Test the 2 KiB stack budget

Quoted 29 lines · bot+bpf-ci
Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/struct_ops_private_stack.c +0 -0
index 98db9bafa44b..2b3ec2b79091 100644

[ ... ]

Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/struct_ops_private_stack.c +0 -0
@@ -78,6 +79,34 @@ static void test_private_stack_recur(void)
 	struct_ops_private_stack_recur__destroy(skel);
 }
 

tools/testing/selftests/bpf/prog_tests/struct_ops_private_stack.c static void test_private_stack_recur(void) · line 91

Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/struct_ops_private_stack.c +10 -0
+/* Two frames of 2 KiB each on the private stack */
+static void test_private_stack_large(void)
+{
+	struct struct_ops_private_stack_large *skel;
+	struct bpf_link *link;
+
+	if (!is_large_stack_supported()) {
+		test__skip();
+		return;
+	}

A subsystem pattern flags this as potentially concerning: The BPF selftests guide recommends always including a reason string in the skip message so future debuggers know why the test was skipped. When the probe gets a clean "invalid write to stack" rejection, is_large_stack_supported() prints nothing, and the subtest shows only SKIP with no indication that the reason is missing large stack support.

Quoted 8 lines

The test_loader's run_subtest() prints a reason (printf("%s:SKIP: %s\n", __func__, spec->skip_reason)) before calling test__skip(), but here the skip is silent. On the other hand, a bare test__skip() with no printf is the most common idiom in prog_tests (about 90 of 149 call sites follow this pattern, and the #else branch of this same file does the same). Could this include a skip reason, or is silent skipping acceptable BPF selftest convention?

Won't fix.

Quoted 86 lines

[ ... ]

Quoted 4 lines
tools/testing/selftests/bpf/prog_tests/tailcalls.c +0 -0
index c5c9d6c359bb..c5e3f198ca7f 100644

[ ... ]

Quoted 15 lines
tools/testing/selftests/bpf/prog_tests/tailcalls.c +11 -0
@@ -1953,6 +1954,45 @@ static void test_tailcall_bpf2bpf_fexit_links(void)
 	tailcall_bpf2bpf2__destroy(skel_tc);
 }
 
+/*
+ * test_tailcall_large_stack runs a tail call made from a subprog with a 1536
+ * byte frame, under a 240-byte caller, into a program with a 2 KiB frame:
+ *
+ * entry (240) --call-> subprog_tail (1536) --tailcall-> classifier_0 (2048)
+ */
+static void test_tailcall_large_stack(void)
+{
+	struct tailcall_large_stack *skel;
+	int err, prog_fd, map_fd, key = 0;
+	char buff[128] = {};

tools/testing/selftests/bpf/prog_tests/tailcalls.c static void test_tailcall_bpf2bpf_fexit_links(void) · line 1977

Quoted 10 lines
tools/testing/selftests/bpf/prog_tests/tailcalls.c +10 -0
+	LIBBPF_OPTS(bpf_test_run_opts, topts,
+		    .data_in = buff,
+		    .data_size_in = sizeof(buff),
+		    .repeat = 1,
+	);
+
+	if (!is_large_stack_supported()) {
+		test__skip();
+		return;
+	}

The same pattern appears here: when is_large_stack_supported() returns false, test__skip() is called with no reason string. Could this also benefit from a skip message?

[ ... ]

Quoted 7 lines
tools/testing/selftests/bpf/progs/verifier_large_stack.c new file +1 -0
new file mode 100644
index 000000000000..2d4c81a3f0cb
@@ -0,0 +1,377 @@
+// SPDX-License-Identifier: GPL-2.0

tools/testing/selftests/bpf/progs/verifier_large_stack.c line 11

Quoted 10 lines
tools/testing/selftests/bpf/progs/verifier_large_stack.c new file +10 -0
+
+#include <linux/bpf.h>
+#include <bpf/bpf_helpers.h>
+#include "bpf_misc.h"
+
+/*
+ * Programs may use MAX_BPF_STACK_JIT (2 KiB) of stack on JITs that support
+ * large stacks, combined over a call chain, with no separate limit on a
+ * single frame. Interpreted programs and other JITs keep 512 bytes.
+ */

A subsystem pattern flags this as potentially concerning: Several tests in this new file appear to be 2 KiB versions of tests that already exist elsewhere in the same directory.

For instance, frame_2048_with_may_goto is the same program as stack_check_size_512_with_may_goto_jit in verifier_stack_ptr.c (r1 = r10; r1 += -512; r0 = 42; *(u32*)(r1 + 0) = r0; may_goto ...; exit), with only -512 changed to -2048 and __load_if_JITed() changed to __load_if_large_stack().

Similarly, single_frame_2048 / single_frame_2048_no_large_stack check the single-frame boundary that verifier_stack_ptr.c already covers with stack_check_size_gt_512 and the new stack_check_size_gt_2048 (fp-2056).

The var_off_write_to_2048/2056 tests check variable-offset stack bounds, which verifier_var_off.c already covers (it gained access_min_out_of_bound_large in the earlier patch in this series).

The private_stack_two_frames test follows verifier_private_stack.c's "Private stack, subtree > MAX_BPF_STACK" test, including the same __log_level(4) "stack depth max" / "subprog N (...) stack" messages.

The BPF selftests guide asks whether variants like these belong as new cases in the existing files instead of a new file, especially since the earlier patch in this series (2d0faaadf6a8) already places its 2 KiB versions next to the originals.

Quoted 10 lines

On the other hand, this new file does group tests for the 2 KiB stack feature, and several behaviors (four 512-byte frames that fit, a tail call from a 1 KiB frame, 1536-byte global subprogs and callbacks) cannot occur under the 512-byte budget, so they have no existing counterpart. Adding one verifier_<feature>.c file per feature is also common in BPF selftests (verifier_private_stack.c is an example). Could you clarify whether the overlap cases should be integrated into existing files, or is a new file the intended organization here?

I think it is fine as is.

Quoted 5 lines

---
AI reviewed your patch. Please fix the bug or email reply why it's not a bug.
See: https://github.com/kernel-patches/vmtest/blob/master/ci/claude/README.md

CI run summary: https://github.com/kernel-patches/bpf/actions/runs/35909853278