Skip to content

Raise BPF program stack size to 2KiB

Kumar Kartikeya Dwivedi bpf 4 versions – Applied

Status from this message: This series was applied to bpf/bpf-next.git (master)

Get series with b4
b4 am [email protected]

Versions newest first · linked by author and title

  1. v4 Latest18 patches 1 replyApplied 18/18
  2. v318 patches 0 repliesSuperseded
  3. v218 patches 8 repliesSuperseded
Earlier versions · 1
VersionPostedPatchesRepliesStatus
v118 patches8 repliesSuperseded

Changes in v4 from the cover letter

Patches in v4 All 18 applied

#Subject and filesSizeRepliesApplied
1/18bpf: Add accessors for verifier stack slotsdrivers/net/ethernet/netronome/nfp/bpf/verifier.c include/linux/bpf_verifier.h kernel/bpf/backtrack.c +4 more+193 -1420 repliesApplied
2/18bpf: Widen the stack slot index in the jump historyinclude/linux/bpf_verifier.h+14 -70 repliesApplied
3/18bpf: Store linked registers in the jump history as an arrayinclude/linux/bpf_verifier.h kernel/bpf/backtrack.c kernel/bpf/states.c +1 more+62 -600 repliesApplied
4/18bpf: Track backtracking stack slots with bitmapsinclude/linux/bpf_verifier.h kernel/bpf/backtrack.c kernel/bpf/verifier.c+54 -390 repliesApplied
5/18bpf: Track scratched stack slots with a bitmapinclude/linux/bpf_verifier.h+8 -70 repliesApplied
6/18bpf: Treat unknown-size stack reads as reaching the frame topkernel/bpf/verifier.c+4 -30 repliesApplied
7/18bpf: Size liveness stack masks by the stack each frame usesinclude/linux/bpf_verifier.h kernel/bpf/liveness.c+340 -2090 repliesApplied
8/18bpf: Grow the verifier id scratch on demandinclude/linux/bpf_verifier.h kernel/bpf/states.c kernel/bpf/verifier.c+83 -401 replyApplied
9/18selftests/bpf: Cover the tail call caller stack depth limittools/testing/selftests/bpf/progs/verifier_tailcall.c+57 -00 repliesApplied
10/18selftests/bpf: Check that narrow stack stores define no slottools/testing/selftests/bpf/progs/verifier_live_stack.c+22 -00 repliesApplied
11/18selftests/bpf: Check liveness merge of masks with different widthstools/testing/selftests/bpf/progs/verifier_live_stack.c+51 -00 repliesApplied
12/18bpf: Size the per-frame verifier structures for a 2 KiB stackinclude/linux/bpf_verifier.h include/linux/filter.h kernel/bpf/liveness.c +1 more+39 -150 repliesApplied
13/18bpf: Bound program stack use by a per-program limitinclude/linux/bpf_verifier.h include/linux/filter.h kernel/bpf/core.c +3 more+102 -350 repliesApplied
14/18selftests/bpf: Add load conditions on the program stack limittools/testing/selftests/bpf/progs/bpf_misc.h tools/testing/selftests/bpf/test_loader.c tools/testing/selftests/bpf/testing_helpers.c +1 more+69 -00 repliesApplied
15/18selftests/bpf: Give the 512-byte stack boundary tests a 2 KiB twintools/testing/selftests/bpf/progs/async_stack_depth.c tools/testing/selftests/bpf/progs/struct_ops_private_stack_fail.c tools/testing/selftests/bpf/progs/test_global_func1.c +8 more+515 -450 repliesApplied
16/18bpf, x86: Allow programs 2 KiB of stackDocumentation/bpf/bpf_design_QA.rst arch/x86/net/bpf_jit_comp.c+19 -30 repliesApplied
17/18bpf, arm64: Allow programs 2 KiB of stackDocumentation/bpf/bpf_design_QA.rst arch/arm64/net/bpf_jit_comp.c+11 -50 repliesApplied
18/18selftests/bpf: Test the 2 KiB stack budgettools/testing/selftests/bpf/prog_tests/struct_ops_private_stack.c tools/testing/selftests/bpf/prog_tests/tailcalls.c tools/testing/selftests/bpf/prog_tests/verifier.c +4 more+636 -00 repliesApplied

Reviews trailers per patch

No Reviewed-by, Acked-by or Tested-by trailers for v4 yet.

Read the v4 thread

Cover letter [PATCH bpf-next v4 00/18] 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. The one nesting a program can force on itself, bpf_clone_redirect() to its own device, runs it up to ten frames deep, so a program calling that helper keeps 512 bytes.

Memory was measured as the peak kernel memory allocated during each BPF_PROG_LOAD, for all 5162 loadable selftest programs, against bpf-next at 24629aac43d2. "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.50%
    5027 programs under 1 MiB            -0.32%        -0.13%
     116 programs of 1-16 MiB            -0.58%        +0.26%
      19 programs of 16 MiB or more      -1.09%        -1.05%

median program 0.0% 0.0%
programs growing by more than 5% 11 59
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
  bpf_iter_tasks/dump_task_sleepable           8.2    8.6  +0.4    +5%  both
  test_tcp_custom_syncookie                   10.8   11.2  +0.4    +4%  masks
  strobemeta_nounroll1/on_event               20.9   21.3  +0.4    +2%  both

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%.

No selftest program uses more than 512 bytes, so a few were rebuilt with a 1 KiB local array handed only to an empty asm statement and -mllvm -bpf-stack-size=2048, which puts every spill below fp-1024 while the verifier never touches the array. They verify with the states and instructions of their unpadded twins; what grows is the verifier state, which carries 88 bytes per stack slot up to the deepest one touched:

  program             slots    insns          states       peak MiB
  pyperf600           37/165   258028/258030  16635/16635  208/905
  strobemeta          61/189   164241/164243  4719/4719    202/870
  test_cls_redirect   22/150   59764/59766    3893/3893    7/186
  test_verif_scale2   3/131    779692/779694  3048/3048    12/169

(unpadded/padded; the two extra instructions are the asm barrier).

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

For more details, please see the individual commits.

Changelog:
----------
v3 -> v4
v3: https://lore.kernel.org/bpf/[email protected]

* Rebase on bpf-next.

v2 -> v3
v2: https://lore.kernel.org/bpf/[email protected]

* Keep the 512-byte budget for a program that calls bpf_clone_redirect():
redirecting to its own device runs it again on top of its own frame, ten frames deep before the datapath's recursion limit drops the packet, which the kernel stack cannot take at 2 KiB per frame. Test both redirect helpers. (BPF CI)
* Cap the liveness spill tracker's per-instruction table at what 64 slots need for the largest program, and bound it by the program's budget, so that a deep store in a huge subprog cannot push one allocation past what kvmalloc() serves. (Alexei, BPF CI)
* Keep every scalar id when the id set cannot record one, instead of clearing ids whose count is incomplete. (BPF CI)
* Say in mark_stack_read_all() that verifier states never hold slots past the budget, rather than that accepted programs never widen past it. (BPF CI)
* Drop the unused use_stack_304() from verifier_callx_rodata.c. (BPF CI)

v1 -> v2
v1: https://lore.kernel.org/bpf/[email protected]

* Rebase on bpf-next. Rewrite the new callx stack depth tests, which expect 608 bytes of stack to be rejected, to use call chains deeper than 2 KiB, so that they are rejected under both budgets.
* Size the liveness spill tracker by the deepest 8-byte access a subprog makes directly through R10 when that reaches past the 64 slots of a 512-byte frame, so that a pointer spilled below fp-512 keeps its identity when filled; add a test, and report programs that spill that deep in the cover letter. (Alexei)
* Return -ENOMEM from the iterator destroy path when the id stack cannot grow, and keep warning about any other release_reference() failure. (Sashiko)
* Read 248 instead of 264 bytes into the frame in the liveness merge test, so the precise pass is narrower than a 512-byte whole-frame read on 64-bit and the widening is exercised everywhere. (Sashiko)
* Convert the nfp offload driver's stack slot indexing to bpf_stack_slot(), note the address-based lookup in reg_to_target(), fetch each slot once in the functions the message names, and narrow the accessor patch's message accordingly. (BPF CI)
* Raise the verifier log's line buffer to 2 KiB so that a full 256-slot stack mask fits in one line. (BPF CI)
* Say in the stack size Q&A that the interpreter's 512 bytes apply per frame and to programs verified for it. (BPF CI)

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           |  11 +-
 arch/arm64/net/bpf_jit_comp.c                 |   5 +
 arch/x86/net/bpf_jit_comp.c                   |  12 +
 .../net/ethernet/netronome/nfp/bpf/verifier.c |   2 +-
 include/linux/bpf_verifier.h                  | 205 +++----
 include/linux/filter.h                        |   6 +
 kernel/bpf/backtrack.c                        | 101 ++--
 kernel/bpf/core.c                             |  13 +
 kernel/bpf/diagnostics.c                      |  11 +-
 kernel/bpf/liveness.c                         | 531 ++++++++++++------
 kernel/bpf/log.c                              |  13 +-
 kernel/bpf/states.c                           | 136 +++--
 kernel/bpf/verifier.c                         | 376 +++++++------
 .../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 +-
 .../selftests/bpf/progs/verifier_callx.c      |  61 +-
 .../bpf/progs/verifier_callx_rodata.c         |  47 +-
 .../bpf/progs/verifier_large_stack.c          | 425 ++++++++++++++
 .../selftests/bpf/progs/verifier_live_stack.c | 104 +++-
 .../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 +++-
 35 files changed, 2245 insertions(+), 576 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: 44e4e52c11d97a9076c611270e52c6965e3255ee

Signature · 1 line
2.53.0