)]}' { "log": [ { "commit": "bd75869299f1d4ff6e9f45117cce28f8badee1cd", "tree": "356accf0764a37e137d1f0e5da110a0916d06288", "parents": [ "a0a0c785cbcaa72bb03c205eb61e5b0960b80ac2", "a9fee553d3db7d2ad923a6f89d592cef9e3b4652" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:17 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:17 2026 +0000" }, "message": "Merge branch \u0027bpf-various-arm64-bpf-jit-improvements\u0027\n\nDaniel Borkmann says:\n\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\nbpf: Various arm64 BPF JIT improvements\n\nThis series changes the arm64 BPF JIT to emit shorter and faster native\ncode for the instruction patterns that LLVM-compiled programs hit in the\nreal world. Every change stays within the lowering of a single BPF\ninstruction. This is a similar effort as done recently for x86-64 BPF\nJIT [0].\n\nOn arm64 under vmtest.sh (qemu TCG), test_verifier, test_maps, jit_insns\nand jit_insns_blinded pass in full, and test_progs and its cpuv4 and\nno_alu32 flavors only fail tests that fail without the series as well\nor only under TCG. The encodings were checked against Arm\u0027s machine-readable\nA64 ISA XML: every A64_* macro and directly called encoder, run with\nboundary and invalid operands (39028 cases), gives the encoding and\nfields the Arm ARM expects or AARCH64_BREAK_FAULT for what it cannot\nencode.\n\nTo see what the series does to code that is actually deployed, the BPF\nobjects of Cilium (c3fbffb08183), Tetragon (31e646a5ed0c, the variants\nfor kernels from 6.1 on), Katran (623234e1814b) and the sched_ext\nschedulers (scx at a40cb6115e68) were built with clang 20 for arm64, and\nevery program of them that loads (338, another 25 fail on both kernels)\nwas loaded with veristat in the arm64 VM of vmtest.sh, on a kernel\nbefore and one after this series. The size is jited_prog_len, the cycles\nand uops are those of the llvm-mca 20 models of the Neoverse N1\n(Graviton2, Ampere Altra), N2 (Cobalt 100), V1 (Graviton3) and V2\n(Graviton4, Grace, Axion) over the JITed images as straight-line code,\nwithout the helper calls, which llvm-mca cannot model, and the LSE\natomics, which the models have no scheduling information for. This is a\nstatic model without the path taken, branch prediction or cache misses,\nbut both sides get the same program, so the delta is what the series\nrewrote. All numbers are averaged over two boots of each kernel, as a\nmap address with a zero 16-bit halfword takes one move less.\n\nProject Progs Size N1 cycles N2 cycles V1 cycles V2 cycles N1 uOps N2 uOps V1 uOps V2 uOps\n---------- ----- ------- --------- --------- --------- --------- ------- ------- ------- -------\ncilium 160 -3.31% -7.36% -11.26% -6.86% -9.35% -3.52% -3.94% -3.53% -3.53%\nkatran 5 -6.41% -7.53% -9.07% -8.57% -0.36% -6.35% -8.44% -6.39% -6.38%\nscx 99 -5.95% -7.63% -6.60% -7.11% -5.43% -5.91% -4.79% -6.06% -6.02%\ntetragon 74 -4.23% -5.83% -5.92% -6.30% -3.31% -4.46% -4.63% -4.51% -4.50%\nall 338 -3.88% -6.88% -9.01% -6.71% -6.91% -4.08% -4.30% -4.11% -4.10%\n\nCilium gains the most cycles from its 355 divisions by NSEC_PER_SEC in\n81 programs, which come from the monotonic clock helper that conntrack,\nNAT and the load balancer run for every entry: all four models put a\n64-bit udiv at 20 cycles against 11 to 13 for the magic number sequence,\nand the N2 and V2 models do not pipeline the divider at all. The\nschedulers have 14 divisions in 7 programs, mostly by 100 and 1000000.\nThe rest of the cycles and most of the uops come from the branches:\n12711 compares against zero and their branch become a cbz or cbnz, and\n2961 sign and bit tests a tbz or tbnz, a uop and a cycle each. Then 979\nloads and stores take the unscaled form, 505 xors with all ones become a\nmvn, 482 stores of zero take the zero register, 187 tail calls lose six\ninstructions each, and 98 multiplications become an add or sub with a\nshifted register. Katran stays flat on V2, whose model dispatches 16\nwide.\n\nFor a feel of the native code, the tail call of Katran\u0027s xdp_root\nprogram, from the bounds checks to the test of the program slot.\n\nBefore:\n\n 3c: 5280088a mov w10, #68\n 40: b86a682a ldr w10, [x1, x10]\n 44: 2a0203e2 mov w2, w2\n 48: 6b0a005f cmp w2, w10\n 4c: 54000222 b.hs #68\n 50: 5280042a mov w10, #33\n 54: f940034c ldr x12, [x26]\n 58: eb0a019f cmp x12, x10\n 5c: 540001a2 b.hs #52\n 60: 9100058c add x12, x12, #1\n 64: 5280440a mov w10, #544\n 68: 8b0a002a add x10, x1, x10\n 6c: d37df04b lsl x11, x2, #3\n 70: f86b694b ldr x11, [x10, x11]\n 74: b40000eb cbz x11, #28\n\nAfter:\n\n 3c: b940442a ldr w10, [x1, #68]\n 40: 6b0a005f cmp w2, w10\n 44: 540001a2 b.hs #52\n 48: f940034c ldr x12, [x26]\n 4c: f100859f cmp x12, #33\n 50: 54000142 b.hs #40\n 54: 9100058c add x12, x12, #1\n 58: 9108802a add x10, x1, #544\n 5c: f862594b ldr x11, [x10, w2, uxtw #3]\n 60: b40000cb cbz x11, #24\n\nOf the 338 programs, 303 get smaller, and 284, 270, 277 and 225 faster\non N1, N2, V1 and V2. The best cases:\n\n Impact Largest decrease Largest relative decrease\n --------- -------------------------------------------------- ------------------------------------\n size generic_usdt_filter_arg 27388 \u003e 26256 -4.13% pandemonium_enable 280 \u003e 224 -20.00%\n N1 cycles tail_handle_ipv6 922 \u003e 807 -12.52% flash_select_cpu 74 \u003e 53 -28.38%\n N2 cycles tail_handle_ipv6 760 \u003e 605 -20.39% flash_enqueue 179 \u003e 98 -45.25%\n V1 cycles tail_handle_ipv4 542 \u003e 471 -13.10% flash_select_cpu 66 \u003e 41 -37.88%\n V2 cycles tail_handle_ipv6_from_netdev 441 \u003e 339 -23.13% flash_enqueue 147 \u003e 67 -54.42%\n\nThe largest gains in cycles are in Cilium\u0027s bpf_lxc.o and bpf_host.o,\nwhose programs above hold 7 to 11 of the divisions by NSEC_PER_SEC each,\nand in Tetragon\u0027s generic_usdt_filter_arg for size, which turns 243 of\nits 961 conditional branches into a cbz, cbnz, tbz or tbnz. The scx_flash\nprograms gain the most relative to their length, from their divisions by\n100.\n\nNo project gets bigger or slower on any model. The worst cases per\nprogram, which for the cycles are the same in every pairing of a boot\nbefore with one after the series:\n\n Impact Worse Largest increase Largest relative increase\n --------- ----- ------------------------------------------- ---------------------------------\n size 3 flash_select_cpu 616 \u003e 640 +3.90% the same\n N1 cycles 1 rusty_set_weight 42 \u003e 43 +2.38% the same\n N2 cycles 1 rusty_set_weight 37 \u003e 38 +2.70% the same\n V1 cycles 2 rusty_stopping 92 \u003e 94 +2.17% rusty_set_weight 37 \u003e 38 +2.70%\n V2 cycles 10 tail_nodeport_nat_egress_ipv4 295 \u003e 301 +2.03% mitosis_dump_task 49 \u003e 52 +6.12%\n\nOf the three programs that grow, flash_select_cpu and flash_enqueue of\nscx_flash do so by 24 and 16 bytes for their divisions by 100, and\ntail_drop_notify of Cilium\u0027s bpf_xdp only in one pairing of boots. None\nof the 12 programs that some model rates slower has more instructions;\ntheir changes are compares and branches that became a cbz or cbnz, which\nthe model then issues in another order. The uops grow in 3 programs, 4\non N2, by at most 2.86%.\n\nThe rewrites on their own, in llvm-mca for one instance of each sequence\nas the JIT emits it, in a single pass with the pipeline fill included.\nAn arena access at an immediate offset keeps its cycles, the add of the\noffset now off the path of the offset register, at a uop more on N2.\n\n cycles, uops N1 N2 V1 V2\n r2 /\u003d 1000000000 25\u003e13 3\u003e7 25\u003e11 3\u003e7 25\u003e11 3\u003e7 25\u003e11 3\u003e7\n r3 /\u003d 100 24\u003e13 2\u003e7 24\u003e11 2\u003e7 24\u003e11 2\u003e7 24\u003e11 2\u003e7\n if r6 \u003d\u003d 0 goto 5\u003e4 2\u003e1 5\u003e4 2\u003e1 5\u003e4 2\u003e1 5\u003e4 2\u003e1\n if w0 s\u003c 0 goto 5\u003e4 2\u003e1 5\u003e4 2\u003e1 5\u003e4 2\u003e1 5\u003e4 2\u003e1\n w2 \u003d *(u32 *)(r8 + 6) 8\u003e7 2\u003e1 8\u003e7 3\u003e1 8\u003e7 2\u003e1 8\u003e7 2\u003e1\n arena r0 \u003d *(u64 *)(r9 + 0) 8\u003e7 2\u003e1 8\u003e7 2\u003e2 8\u003e7 2\u003e1 8\u003e7 2\u003e1\n *(u64 *)(r1 + 0) \u003d 0 5\u003e4 3\u003e2 5\u003e4 3\u003e2 5\u003e4 3\u003e2 4\u003e4 3\u003e2\n w1 ^\u003d -1 5\u003e4 2\u003e1 5\u003e4 2\u003e1 5\u003e4 2\u003e1 5\u003e4 2\u003e1\n r0 *\u003d 24 8\u003e5 2\u003e2 6\u003e5 2\u003e2 6\u003e5 2\u003e2 6\u003e5 2\u003e2\n w1 *\u003d 65537 7\u003e5 3\u003e1 7\u003e5 3\u003e1 7\u003e5 3\u003e1 7\u003e5 3\u003e1\n if w2 \u003e 0xffff goto 6\u003e5 3\u003e2 6\u003e5 3\u003e2 6\u003e5 3\u003e2 6\u003e5 3\u003e2\n tail call slot of w3 9\u003e8 4\u003e2 9\u003e8 5\u003e3 9\u003e8 4\u003e2 9\u003e8 4\u003e2\n\nThanks,\nDaniel\n\nv2 -\u003e v3:\n - Divide by constants in the verifier via UHMUL/SHMUL, replacing v2 07\n and 15 and x86\u0027s emit_div_const() (Alexei)\n - x86 now keeps a div for smod and for umod by divisors that need the\n add sequence or a dividend shift\n - tbz/tbnz decided once from the pass 1 offsets, dropping extra_pass,\n max_idx and the new multi-func bound (Alexei)\n - New fix: measure branches back from the branch itself; the sizing\n pass failed conditional branches back to targets ~1MB into the image\n - int shift after the extend in the register offset encoder instead of\n the scaled flag (Alexei)\n - Dropped the A64_LDR*()/A64_STR*() macros left unused (Alexei), and\n the already unused A64_BL, A64_BTI_C and A64_LDR32LIT\n - Encoders reject what they cannot encode as given: bad extends, ADR\n beyond 4GB, STXR/LDP/STP overlaps and branch counts that wrap\n - Rebased onto the PROBE_MEM user address filter and BPF_REG_ARENA_SP\n - Kernel comment style, shorter comments and commit messages (sashiko,\n bpf ci bot)\n - New verifier_div_const test; jit_insns adds a far branch back, the\n PROBE_MEM filter offsets, the tbz/tbnz reach, jset and sign jumps\nv1 -\u003e v2:\n - Share the divisor selection with x86 via bpf_magic_div() in the core\n instead of copying it into the arm64 JIT (Alexei)\n - tailcall: ldr x11, [x10, w2, uxtw #3] in place of ubfiz + ldr, with\n a scaled flag in the register offset encoder (Xu)\n - tbz/tbnz decided once in pass 2 from the sizing pass offsets, no\n repeated sizing passes (Alexei)\n - Dropped the 24-bit immediate split which was 4 bytes for a cycle\n of latency (Alexei)\n - Arena acquire/release test insns built with __imm_insn() (bpf ci bot)\n\n [0] https://lore.kernel.org/bpf/20261013171230.523677-1-daniel@iogearbox.net/\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n\nLink: https://patch.msgid.link/cover.1794165614.git.daniel@iogearbox.net\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\n" }, { "commit": "a9fee553d3db7d2ad923a6f89d592cef9e3b4652", "tree": "356accf0764a37e137d1f0e5da110a0916d06288", "parents": [ "099c2e03f9a025071721edad9c5b7c8e1b028c21" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:50 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:17 2026 +0000" }, "message": "selftests/bpf: Extend the JIT instruction tests for arm64 encodings\n\nCover the sequences that the arm64 JIT now emits: compares, bit tests,\nconstant arithmetic, immediates, sign jumps across the short branch\nreach (also with a subprog call in between), arena and PROBE_MEM\naddresses, and the tail call. The tests check the results, so they\napply to every JIT.\n\nfar_back_jump puts loops behind 52500 helper calls. In the arm64 sizing\npass this places them more than 1MB into the image, where a branch back\nused to fail the JIT.\n\nThe arena atomics are only guarded at build time. On an arm64 CPU\nwithout LSE, the kernel rejects them at load time, as the ll/sc atomics\nhave no arena support yet, so their subtests fail there on purpose.\n\n # PLATFORM\u003daarch64 CROSS_COMPILE\u003daarch64-linux-gnu- ./vmtest.sh -- ./test_progs -t jit_insns\n [...]\n #200/1 jit_insns/arena_zero_off:OK\n #200/2 jit_insns/cast_to_user:OK\n #200/3 jit_insns/arena_offsets:OK\n #200/4 jit_insns/arena_offsets_ldsx:OK\n #200/5 jit_insns/arena_offsets_atomics:OK\n #200/6 jit_insns/arena_acq_rel:OK\n #200/7 jit_insns/alu_imm:OK\n #200/8 jit_insns/alu_reg:OK\n #200/9 jit_insns/alu_imm_regs:OK\n #200/10 jit_insns/div_const:OK\n #200/11 jit_insns/alu_reg_pairs:OK\n #200/12 jit_insns/alu_edges:OK\n #200/13 jit_insns/shifts:OK\n #200/14 jit_insns/shift_counts:OK\n #200/15 jit_insns/atomics:OK\n #200/16 jit_insns/atomic_reg_pairs:OK\n #200/17 jit_insns/xadd_chain:OK\n #200/18 jit_insns/ld_imm64:OK\n #200/19 jit_insns/jmp_imm:OK\n #200/20 jit_insns/jmp_reg:OK\n #200/21 jit_insns/jmp_reg_pairs:OK\n #200/22 jit_insns/jmp_edges:OK\n #200/23 jit_insns/staggered_jumps:OK\n #200/24 jit_insns/max_jmp:OK\n #200/25 jit_insns/sign_jumps:OK\n #200/26 jit_insns/convergence:OK\n #200/27 jit_insns/same_len_not_converged:OK\n #200/28 jit_insns/far_back_jump:OK\n #200/29 jit_insns/calls:OK\n #200/30 jit_insns/helper_calls:OK\n #200/31 jit_insns/tail_call:OK\n #200/32 jit_insns/ldst_zero_off:OK\n #200/33 jit_insns/ldst_offsets:OK\n #200/34 jit_insns/acq_rel:OK\n #200/35 jit_insns/atomic_ptr_operand:OK\n #200/36 jit_insns/movsx:OK\n #200/37 jit_insns/jset_imm:OK\n #200/38 jit_insns/cmp_imm:OK\n #200/39 jit_insns/alu_consts:OK\n #200/40 jit_insns/bswap:OK\n #200/41 jit_insns/probe_mem:OK\n #200 jit_insns:OK\n #201/1 jit_insns_blinded/alu_imm:OK\n #201/2 jit_insns_blinded/alu_imm_regs:OK\n #201/3 jit_insns_blinded/alu_edges:OK\n #201/4 jit_insns_blinded/div_const:OK\n #201/5 jit_insns_blinded/shifts:OK\n #201/6 jit_insns_blinded/xadd_chain:OK\n #201/7 jit_insns_blinded/ld_imm64:OK\n #201/8 jit_insns_blinded/jmp_imm:OK\n #201/9 jit_insns_blinded/jmp_edges:OK\n #201/10 jit_insns_blinded/ldst_zero_off:OK\n #201/11 jit_insns_blinded/ldst_offsets:OK\n #201/12 jit_insns_blinded/jset_imm:OK\n #201/13 jit_insns_blinded/cmp_imm:OK\n #201/14 jit_insns_blinded/alu_consts:OK\n #201 jit_insns_blinded:OK\n Summary: 2/55 PASSED, 0 SKIPPED, 0/0 FAILED\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/f16feeec21ead88b0459d967f976fad4f60b750b.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "099c2e03f9a025071721edad9c5b7c8e1b028c21", "tree": "a10429e339deb87f71db1d014732a895e5b69d58", "parents": [ "75e665d4892b285ea28535c9145ae2e7f46c2cc5" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:49 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:17 2026 +0000" }, "message": "selftests/bpf: Test the verifier\u0027s division by constants\n\nOn the JITs that support UHMUL and SHMUL, check the uhmul and shmul\nsequences that the verifier rewrites 64-bit divisions by a constant\ninto, one test per sequence shape, and the modulos that keep the\ndivision. The results of the rewritten sequences are checked by\njit_insns\u0027 div_const.\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/0317dbcd31c9a13584bafe9583885abadfab5579.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "75e665d4892b285ea28535c9145ae2e7f46c2cc5", "tree": "a358072df69b5bd55e29b72b24c8ce83f3f17f82", "parents": [ "c9c277f5e08fe37780c7b130135c0295cf7c979f" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:48 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:17 2026 +0000" }, "message": "selftests/bpf: Let the arm64 private stack check skip the BTI pad\n\nWith CONFIG_ARM64_BTI_KERNEL, which is the default with clang before\n21, the JIT emits a BTI J landing pad between the tail call counter\nsetup and the push of the callee-saved registers. The arm64\nexpectations of the \"Private stack, exception in main prog\" test want\nthe push right after the setup, so the test fails:\n\n WRONG LINE SUBSTR: \u0027\tstp\tx19, x20, [sp, #-0x10]!\u0027\n expecting match at line 9, actual match is at line 10\n\nLet the expectation skip lines between the two, as other tests in the\nsame file already do.\n\nFixes: e9f545d0d336 (\"selftests/bpf: Enable private stack tests for arm64\")\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/2df53a485118780853c7fc01d475590e46241073.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "c9c277f5e08fe37780c7b130135c0295cf7c979f", "tree": "93466649a543a5a4ca978ee2d27fccad1fd259c5", "parents": [ "abf5971d572c98a58f284c1f36b397f1f10d75b7" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:47 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:17 2026 +0000" }, "message": "bpf, arm64: Multiply by constants with shifts, adds and subs\n\nLLVM leaves a multiplication by a constant other than a power of two as\nis, and the JIT emitted it as a mov of the constant and a mul of two to\nfour cycles.\n\nFor constants of the form 2^n, 2^n + 1 or 2^n - 1, optionally negated\nor multiplied by 2^m, emit at most two shifts, adds or subs instead.\nOnly sequences of at most two cycles are used, so they are never slower\nthan the mul.\n\nA multiplication by 0 becomes a mov, by -1 a neg, and by 1 nothing\nbeyond the zero extension of the 32-bit variant.\n\nBefore/after for r1 *\u003d 3, r1 *\u003d 7 and r1 *\u003d 24:\n\n d280006a mov x10, #0x3\n 9b0a7c00 mul x0, x0, x10\n 8b000400 add x0, x0, x0, lsl #1\n\n d28000ea mov x10, #0x7\n 9b0a7c00 mul x0, x0, x10\n d37df00a lsl x10, x0, #3\n cb000140 sub x0, x10, x0\n\n d280030a mov x10, #0x18\n 9b0a7c00 mul x0, x0, x10\n 8b000400 add x0, x0, x0, lsl #1\n d37df000 lsl x0, x0, #3\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/58268de43cde336b82eaf7ac27b26cea7bcf299c.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "abf5971d572c98a58f284c1f36b397f1f10d75b7", "tree": "1892e6d883b54efddb0547806311fada481880ea", "parents": [ "4835c45b11d24f4197c1d56b1077559c243ecb05" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:46 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:17 2026 +0000" }, "message": "bpf, arm64: Use cbz, cbnz, tbz and tbnz for zero, sign and bit tests\n\nA compare against zero for equality, a sign test and a single-bit test\neach took a cmp or tst followed by a b.cond. CBZ/CBNZ and TBZ/TBNZ do\neach in one instruction. That saves code size and a decode slot, and\nalso a uop on cores that do not fuse the pair. Null checks and sign\ntests are the most frequent compares in BPF programs.\n\nTBZ and TBNZ only reach +/-8K instructions, so a test uses them only\nwhen its target is within reach in the sizing pass. The sizing pass has\nthe longest layout of all passes, the extra pass included, so the\ntarget then stays in reach. The decisions are kept in a bitmap.\n\nBefore/after for if r0 \u003d\u003d 0 goto ..., if w0 s\u003c 0 goto ... and\nif r1 \u0026 0x8 goto ...:\n\n f100011f cmp x8, #0x0\n 54000040 b.eq ...\n b4000048 cbz x8, ...\n\n 7100011f cmp w8, #0x0\n 5400004b b.lt ...\n 37f80048 tbnz w8, #0x1f, ...\n\n f27d001f tst x0, #0x8\n 54000041 b.ne ...\n 37180040 tbnz w0, #0x3, ...\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/bcb6146505f3ae677d92b73da5f44ebc77dc43f5.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "4835c45b11d24f4197c1d56b1077559c243ecb05", "tree": "c5080d75f820627cdd075b2afab5eec12e196512", "parents": [ "7dd5500c2c4f763ca29341f2aeeb82e0c972b3bf" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:45 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:17 2026 +0000" }, "message": "bpf, arm64: Use mov or mvn for AND, OR and XOR with all ones\n\nThe logical immediate forms cannot encode all ones, so AND, OR and XOR\nwith -1 moved the constant into a temporary first. The XOR is common,\nas LLVM lowers every bitwise NOT to r ^\u003d -1.\n\nEmit an mvn for the XOR and a mov of -1 for the OR. For the AND, emit a\n32-bit mov to zero extend the 32-bit variant, and nothing for the\n64-bit one.\n\nBefore/after for w1 \u0026\u003d -1 and w1 ^\u003d -1:\n\n 1280000a mov w10, #0xffffffff\n 0a0a0000 and w0, w0, w10\n 2a0003e0 mov w0, w0\n\n 1280000a mov w10, #0xffffffff\n 4a0a0000 eor w0, w0, w10\n 2a2003e0 mvn w0, w0\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/16fd55629bcb969a47506d1c2722df2807a1af17.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "7dd5500c2c4f763ca29341f2aeeb82e0c972b3bf", "tree": "98d03daa12208aff657112739576844cb32bbcad", "parents": [ "e79c67bce1a20d1ade084b15f706cd88fc56676b" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:44 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "bpf, arm64: Shorten the tail call sequence\n\nThe tail call sequence moved the offsets of max_entries, ptrs and\nbpf_func, and the tail call limit, into a temporary first, although\nthey all fit the immediate forms. It also zero extended and shifted the\nindex in separate instructions before the load. Use the immediate forms\nand a register offset load with UXTW #3 instead.\n\nThat saves six instructions per tail call. A64_LDR64() loses its last\nuser and is removed.\n\nBefore/after for the checks and the lookup of a tail call:\n\n 5280088a mov w10, #0x44\n b86a682a ldr w10, [x1, x10]\n 2a0203e2 mov w2, w2\n 6b0a005f cmp w2, w10\n 54000282 b.hs ...\n 5280042a mov w10, #0x21\n f940034c ldr x12, [x26]\n eb0a019f cmp x12, x10\n 54000202 b.hs ...\n 9100058c add x12, x12, #0x1\n 5280440a mov w10, #0x220\n 8b0a002a add x10, x1, x10\n d37df04b lsl x11, x2, #3\n f86b694b ldr x11, [x10, x11]\n b400014b cbz x11, ...\n\n b940442a ldr w10, [x1, #68]\n 6b0a005f cmp w2, w10\n 54000202 b.hs ...\n f940034c ldr x12, [x26]\n f100859f cmp x12, #0x21\n 540001a2 b.hs ...\n 9100058c add x12, x12, #0x1\n 9108802a add x10, x1, #0x220\n f862594b ldr x11, [x10, w2, uxtw #3]\n b400012b cbz x11, ...\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/5f7973c448f56ec92f8984076ada417ca06615d5.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "e79c67bce1a20d1ade084b15f706cd88fc56676b", "tree": "1a9277f01dfe794274087d1122280d9bccc58a8b", "parents": [ "a33de9a3bba39ca6fa334b6c10c84f0262506077" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:43 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "bpf, arm64: Materialize immediates with fewer instructions\n\nA 32-bit immediate with a zero or all-ones low half often took two\nmoves where a single shifted movz or movn does. A bitmask immediate,\n32 or 64 bits, took two or more moves where a single orr does.\n\nA 64-bit immediate with a repeated 16-bit chunk now takes one orr of\nthat chunk replicated, if that is a bitmask immediate, plus a movk for\neach other chunk. The verifier\u0027s magic numbers for dividing by 3, 5, 15\nand 17 have that form.\n\nBefore/after for w1 \u003d 0x10000, r1 \u003d 0x7fffffff, r1 \u003d 0xffffffff00000000 ll\nand r1 \u003d 0xcccccccccccccccd ll:\n\n 52800000 mov w0, #0x0\n 72a00020 movk w0, #0x1, lsl #16\n 52a00020 mov w0, #0x10000\n\n d29fffe0 mov x0, #0xffff\n f2afffe0 movk x0, #0x7fff, lsl #16\n b2407be0 mov x0, #0x7fffffff\n\n d2ffffe0 mov x0, #0xffff000000000000\n f2dfffe0 movk x0, #0xffff, lsl #32\n b2607fe0 mov x0, #0xffffffff00000000\n\n d2f99980 mov x0, #0xcccc000000000000\n f2d99980 movk x0, #0xcccc, lsl #32\n f2b99980 movk x0, #0xcccc, lsl #16\n f29999a0 movk x0, #0xcccd\n b202e7e0 mov x0, #0xcccccccccccccccc\n f29999a0 movk x0, #0xcccd\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/0da11680b3d4524536f633f2e33d847f7db7035d.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "a33de9a3bba39ca6fa334b6c10c84f0262506077", "tree": "a8973d96d8f8e037f44427c7669b2479abcf71d9", "parents": [ "07d4e6947e374fe463d70c7a2eb868c5508ed819" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:42 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "bpf, arm64: Adjust compares with unencodable immediates by one\n\ncmp and cmn take a 12-bit immediate, optionally shifted left by 12.\nLLVM turns x \u003c\u003d C into x \u003c C + 1 and x \u003e\u003d C into x \u003e C - 1, so a\ncompare against a power of two reaches the JIT as one against a power\nof two plus one, or against a mask. Those often do not encode and\nneeded a mov.\n\nWhen the immediate does not encode but its neighbour C - 1 or C + 1\ndoes, compare against the neighbour and adjust the condition. This\ncovers \u003c, \u003c\u003d, \u003e and \u003e\u003d, both signed and unsigned.\n\nBefore/after for if r1 \u003c 4097 goto ... and if r1 \u003e 65535 goto ...:\n\n d282002a mov x10, #0x1001\n eb0a001f cmp x0, x10\n 54000043 b.lo ...\n f140041f cmp x0, #0x1, lsl #12\n 54000049 b.ls ...\n\n d29fffea mov x10, #0xffff\n eb0a001f cmp x0, x10\n 54000048 b.hi ...\n f140401f cmp x0, #0x10, lsl #12\n 54000042 b.hs ...\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/087e9606132fb246b8e05b65ccaf67a524e7fecc.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "07d4e6947e374fe463d70c7a2eb868c5508ed819", "tree": "e5a1a702cf77b640aae19389cf38b7bd3ce0f7a4", "parents": [ "e4939b2a54b9c04abc00f3d745ad739aa00c453c" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:41 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "bpf, arm64: Zero extend the arena offset in register offset accesses\n\nAn arena access added the 32-bit arena offset register to the arena\nbase with a 64-bit add. That relies on the verifier to keep the upper\n32 bits zero, and any slip there would let the access escape the 4GB\narena.\n\nUse the register offset form with UXTW instead. It zero extends the\noffset as part of the access, which keeps the access within the arena\nand its guard pages. Without an immediate offset, this saves the add.\nWith one, the add moves to the base, and an offset that does not fit\nthe add immediate needs an extra mov.\n\nThe atomics and load-acquire/store-release have no register offset\nform. For them, add the arena offset to the base with UXTW instead.\n\nUpdate the arm64 expectations of the Arena LDSX Disasm test in\nverifier_ldsx to the new form.\n\nBefore/after for r0 \u003d *(u64 *)(r1 + 0) and r0 \u003d *(u64 *)(r1 + 8) in the\narena:\n\n 8b1c000b add x11, x0, x28\n f9400168 ldr x8, [x11]\n f8604b88 ldr x8, [x28, w0, uxtw]\n\n 8b1c000b add x11, x0, x28\n f9400568 ldr x8, [x11, #8]\n 9100238b add x11, x28, #0x8\n f8604968 ldr x8, [x11, w0, uxtw]\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/ac8f9bf5349238dc16ff7ee4214286f5e5d33d6d.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "e4939b2a54b9c04abc00f3d745ad739aa00c453c", "tree": "7d281df332a5588e98fb2f6f02fe17274caacdba", "parents": [ "6b3c7bde476f5d3c4cd96a2f778c6c9dda7d8c3b" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:40 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "bpf, arm64: Store zero immediates from the zero register\n\nA store of an immediate first moves it into a temporary, even when it\nis zero. Store a zero from xzr instead, which saves the mov. Zero\nstores are common: with cpu v4, LLVM emits runs of them to clear the\nstack slots of the structs and arrays that BPF programs pass to\nhelpers.\n\nBefore/after for *(u64 *)(r10 - 8) \u003d 0 with 16 bytes of stack:\n\n d280000a mov x10, #0x0\n f90007ea str x10, [sp, #8]\n f90007ff str xzr, [sp, #8]\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/2a41c66d3f9b162b32cf038f8d65ad5ea4b300b7.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "6b3c7bde476f5d3c4cd96a2f778c6c9dda7d8c3b", "tree": "6708e43e1d3f8c085816d928c2a9335f4433caca", "parents": [ "1bb1bc5be527b297d50817152a1532d80a8ccacd" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:39 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "bpf, arm64: Use the unscaled forms for negative and unaligned offsets\n\nA load or store with a negative offset, or with one that is not a\nmultiple of the access size, needed a mov of the offset and the\nregister offset form. LDUR and STUR take a signed 9-bit byte offset at\nthe same latency. Use them for offsets from -256 to 255, which covers,\nfor example, packet fields behind the Ethernet header.\n\nBefore/after for r0 \u003d *(u32 *)(r1 + 26) and r0 \u003d *(u64 *)(r1 - 16):\n\n d280034a mov x10, #0x1a\n b86a6808 ldr w8, [x0, x10]\n b841a008 ldur w8, [x0, #26]\n\n 928001ea mov x10, #0xfffffffffffffff0\n f86a6808 ldr x8, [x0, x10]\n f85f0008 ldur x8, [x0, #-16]\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/8d6e8c8259aa677feef2b0103939d15b9f53fa0b.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "1bb1bc5be527b297d50817152a1532d80a8ccacd", "tree": "aa000192a0ec9afdde50f63cdeb7f145982d9b67", "parents": [ "ffebe8b3e369792b48e4032003e311dee6d1e3d2" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:38 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "bpf, arm64: Consolidate the load and store emission into a helper\n\nThe BPF_LDX, BPF_ST and BPF_STX cases each repeat the frame pointer\nadjustment and the switch over the access size. Move that into a new\nemit_ldst() helper, and remove the A64_LDR*() and A64_STR*() macros\nthat lose their last user. The emitted code is unchanged.\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/b713e8dcb8cf050002ecdf42efb18fd441f2e275.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "ffebe8b3e369792b48e4032003e311dee6d1e3d2", "tree": "4ca065567c2c9b6fa8393937fcd73385b2519828", "parents": [ "1fdba03c72cb5baf03b05d243d746f143bed2bda" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:37 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "bpf: Divide by constants via uhmul and shmul in the verifier\n\nLLVM has no high-half multiply to strength-reduce 64-bit divisions by a\nconstant, so they reach the kernel as BPF_DIV and BPF_MOD with BPF_K.\nOn arm64, that is a udiv or sdiv of 5 to 20 cycles.\n\nRewrite them in bpf_do_misc_fixups() into a uhmul or shmul by the magic\nnumber, for the JITs that support UHMUL and SHMUL. This replaces\nemit_div_const() in the x86 JIT.\n\nWith AX as the only scratch register, smod keeps the division, and so\ndoes umod when the divisor needs the add sequence or a dividend shift.\nThe division is also kept for a divisor of 1, an unsigned divisor above\n2^63, and for blinded or offloaded programs.\n\nPowers of two are not special-cased, as LLVM already emits shifts for\nthem. The sequences were checked in user space against C division\nacross the imm32 range.\n\nLike other rewrites that grow a program, this one can leave a jump at\nthe edge of its range over such a division unpatchable. So jit_insns\u0027\nmax_jmp now divides by -7, which stays a division.\n\nBefore/after on x86 for r1 /\u003d 1000. r1 %\u003d 1000 is back to a div, as\n1000 needs the add sequence or a dividend shift:\n\n 50 pushq %rax\n 52 pushq %rdx\n 48 89 f8 movq %rdi,%rax\n 48 c1 e8 03 shrq $0x3,%rax\n 49 bb cf f7 53 e3 a5 9b c4 20 movabsq $0x20c49ba5e353f7cf,%r11\n 49 f7 e3 mulq %r11\n 48 c1 ea 04 shrq $0x4,%rdx\n 48 89 d7 movq %rdx,%rdi\n 5a popq %rdx\n 58 popq %rax\n\n 48 c1 ef 03 shrq $0x3,%rdi\n 49 ba cf f7 53 e3 a5 9b c4 20 movabsq $0x20c49ba5e353f7cf,%r10\n 4d 89 d3 movq %r10,%r11\n 50 pushq %rax\n 52 pushq %rdx\n 48 89 f8 movq %rdi,%rax\n 49 f7 e3 mulq %r11\n 48 89 d7 movq %rdx,%rdi\n 5a popq %rdx\n 58 popq %rax\n 48 c1 ef 04 shrq $0x4,%rdi\n\nSuggested-by: Alexei Starovoitov \u003calexei.starovoitov@gmail.com\u003e\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/b733e9e689b13a03b83577f9e40712ec10dc01bb.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "1fdba03c72cb5baf03b05d243d746f143bed2bda", "tree": "c88828dea277cb2aeefbcbf6f3a8ca5e04085251", "parents": [ "592f36e960d02546ae15f620fba1f065a00aa207" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:36 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "arm64, insn: Add the LDUR/STUR and TBZ/TBNZ encodings\n\nAdd the encodings that the BPF JIT needs for its shorter sequences:\n\n - LDUR, STUR and LDURS{B,H,W}: loads and stores with a signed 9-bit\n byte offset, for the negative and unaligned offsets that the scaled\n forms cannot encode.\n - TBZ and TBNZ: test a single bit and branch, within +/-32KB.\n - Extend and shift parameters for the register offset loads and\n stores, in the same order as the extended register add and sub\n take them. They allow UXTW of a 32-bit offset register, and\n scaling the offset by the access size. UXTX gives the plain 64-bit\n register form as before.\n - A check that UMULH and SMULH use the 64-bit variant with Ra set to\n the zero register, as their encoding requires.\n\nThe JIT is the only user of the register offset encoder. It passes UXTX\nwithout a shift, so its loads and stores stay the same, except for the\nsign extending ones: their template had SXTX, which does the same for a\n64-bit offset register, and they now get UXTX like the others.\n\nLike the scaled and register offset forms, the unscaled sign extending\nloads reject the 64-bit size, which would encode PRFUM.\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/3409c201739a30aee9edb358b7efa9dbb6ee4b02.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "592f36e960d02546ae15f620fba1f065a00aa207", "tree": "2ac9f6100e8d0809a4c50e9fb41a6e8bcf3ee8a4", "parents": [ "d860f6254d60996f4b140f1bc9858a0a26b22379" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:35 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "bpf, arm64: Widen the branch offsets before scaling them to bytes\n\nThe branch macros shift their instruction count left by 2 as an int. A\ncount of magnitude 2^29 or more overflows, possibly into range, and\nyields a valid branch to the wrong place instead of AARCH64_BREAK_FAULT.\nNo caller gets near that, but widen the count to a long before scaling\nit, so that the encoders range check the full offset.\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/820ffb112d7268f86be14f414f3c32090cc7b028.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "d860f6254d60996f4b140f1bc9858a0a26b22379", "tree": "38596e5889cecdbdd6d7563740302464aa4f458a", "parents": [ "1963ac21c7c23d9d9a95007cf661588cb2d37c3f" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:34 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "arm64, insn: Reject invalid and unpredictable operands in the encoders\n\nA few encoders return a valid instruction for operands the instruction\ncannot take, instead of AARCH64_BREAK_FAULT:\n\n - The extended register add and sub put any @extend into the 3-bit\n option field, so -1 becomes SXTX and 8 becomes UXTB.\n - ADR truncates its offset to 32 bits before the range check, so an\n offset beyond 4GB can wrap into range.\n - STXR and STLXR accept a status register equal to the data or base\n register, LDP equal target registers, and pre- and post-index LDP\n and STP a target register equal to the base. The Arm ARM makes all\n of these CONSTRAINED UNPREDICTABLE.\n\nReject them. No caller passes such operands, so this only keeps a\nfuture caller from silently emitting a wrong or unpredictable\ninstruction.\n\nAlso print the size, not the type, when the immediate offset load and\nstore encoder rejects a size.\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/a039fe7efc077061852c80b14b6ebcc81cdef75d.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "1963ac21c7c23d9d9a95007cf661588cb2d37c3f", "tree": "267cce2d7375d8b663c2aa8ff1dc2743febaca55", "parents": [ "207aac32085d15fa4f38d836e0b06c81dcc35f67" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:33 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "bpf, arm64: Measure backward branches from the branch itself\n\nbpf2a64_offset() takes the position of a branch from the offset of the\nnext BPF instruction, which the current pass has not set yet:\n\n - In the sizing pass that offset is still 0, so a branch back gets\n the target\u0027s instruction index plus one as its offset. This exceeds\n the imm19 maximum of 2^18 - 1 instructions once the target is at\n index 2^18 - 1 or later, i.e. 4 bytes short of 1MB into the image,\n and check_imm19() fails the program.\n - In the second pass it still holds the value from the first pass,\n so a branch back is overestimated by however much the code in\n front of it shrank.\n\nFor a branch back, take ctx-\u003eidx instead, which is the position of the\nbranch in every pass.\n\nFixes: 2589726d12a1 (\"bpf: introduce bounded loops\")\nFixes: ddbe9ec55039 (\"bpf, arm64: Jit BPF_CALL to direct call when possible\")\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/88f0520fdea7ffdf1ccdc2d5867272b95e6d4c1f.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "207aac32085d15fa4f38d836e0b06c81dcc35f67", "tree": "6b638509d1a60d15d0e07fc03a11cbf71884c571", "parents": [ "182afb043e7ec19ab347674a90eacca3c7491c84" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:32 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "bpf, arm64: Keep the ll/sc atomics address apart from the old value\n\nWith a zero offset, the ll/sc fetching atomics use dst_reg directly as\nthe address. They load the old value into src_reg, or into r0 for\ncmpxchg, and then store through dst_reg. If that register is dst_reg\nitself, the load overwrites the address, and the store then uses the\nold value as its address. The verifier rejects such programs, but the\nJIT should not rely on that.\n\nCopy the address into a temporary when the register receiving the old\nvalue is the address register. The LSE forms are not affected.\n\nBefore/after for r1 \u003d atomic_fetch_add((u64 *)(r1 + 0), r1) without LSE:\n\n aa0003e9 mov x9, x0\n c85f7c00 ldxr x0, [x0]\n 8b09000b add x11, x0, x9\n c80cfc0b stlxr w12, x11, [x0]\n 35ffffac cbnz w12, ...\n d5033bbf dmb ish\n\n aa0003ea mov x10, x0\n aa0003e9 mov x9, x0\n c85f7d40 ldxr x0, [x10]\n 8b09000b add x11, x0, x9\n c80cfd4b stlxr w12, x11, [x10]\n 35ffffac cbnz w12, ...\n d5033bbf dmb ish\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/48822456403635c57d6cd67e115f28473dac62ad.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "182afb043e7ec19ab347674a90eacca3c7491c84", "tree": "3564b3ae68375a681d28ecdd401425d967e8343f", "parents": [ "6a5b148dac530aa7be71f28d404578860765b3f7" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:31 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "arm64, insn: Reject sign extending loads of 64 bits\n\nWith the 64-bit size, the encoding of LDRSB, LDRSH and LDRSW becomes\nPRFM. So when asked for a 64-bit sign extending load, the load and\nstore encoders returned a prefetch instead of failing. The BPF JIT\nnever asks for one, as BPF_MEMSX has no BPF_DW form, but return\nAARCH64_BREAK_FAULT as for other invalid operands.\n\nBefore/after for a 64-bit sign extending load from x1 + 8 into x0:\n\n f9800420 prfm pldl1keep, [x1, #8]\n d4202000 brk #0x100\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/c3b4128577d93ae25be8800db562d4bbcaa76a9f.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "6a5b148dac530aa7be71f28d404578860765b3f7", "tree": "dd3c62d3e82e2019ebf12123b685fc09d1d624c0", "parents": [ "346ea1557fd7d8404c41bf591d850437cfe72461" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:30 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "bpf, arm64: Emit ISB SY in the speculation barriers\n\nThe Spectre-BHB loop in the epilogue and BPF_NOSPEC on CPUs without\nFEAT_SB both end in an ISB. The JIT takes its encoding from the\ninstruction matcher\u0027s template, which leaves CRm as 0. The Arm ARM\nlists that encoding as reserved.\n\nEmit ISB SY instead, with CRm set to 0b1111. This is also what the\nassembler emits for the kernel\u0027s own isb().\n\nBefore/after:\n\n d50330df isb #0\n d5033fdf isb\n\nFixes: 0dfefc2ea2f2 (\"arm64: bpf: Add BHB mitigation to the epilogue for cBPF programs\")\nFixes: dff883d9e93a (\"bpf, arm64, powerpc: Change nospec to include v1 barrier\")\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nTested-by: Luis Gerhorst \u003cluis.gerhorst@fau.de\u003e\nLink: https://patch.msgid.link/55381dc4324aa5ee8a9ae73f9d61211e4681dba0.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "346ea1557fd7d8404c41bf591d850437cfe72461", "tree": "2383cb5478a2dcebcf31dcc0b6a461945ce3cc07", "parents": [ "0ff09166d3d2d900b4b53f28fa2800c045117dfa" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:29 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "bpf, arm64: Free the private stack when a pass over the image fails\n\nWhen a pass over the image fails, including the extra pass of a\nsubprog, the image is freed but ro_header is left set. The exit path\nthen skips freeing the private stack. It stays allocated behind\npriv_stack_ptr, and bpf_jit_free() does not free it either, as the\nprogram is not marked as JITed.\n\nClear ro_header and header once the image is freed, so that the exit\npath frees the private stack as it does for failures before the image\nwas allocated. The x86 JIT does the same with its image pointer.\n\nFixes: 6c17a882d380 (\"bpf, arm64: JIT support for private stack\")\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/bf4b96af4ba852c6ffd9c7db91ac0f0cb047116f.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "0ff09166d3d2d900b4b53f28fa2800c045117dfa", "tree": "215435fc7a59aecdf3722446f82364599d1d906b", "parents": [ "0931830cc31204dfc2a37b84f2019caef1bcd0f0" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:28 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "bpf, arm64: Free the offset table of a subprog in bpf_jit_free\n\nWhen jit_subprogs() fails after some subprogs were already JITed, it\nfrees them through bpf_jit_free(). That frees jit_data, but not the\noffset table that jit_data keeps for the extra pass, so every such\nfailure leaks the table.\n\nFree the offset table there as well, as the x86, riscv and LoongArch\nJITs do.\n\nFixes: db496944fdaa (\"bpf: arm64: add JIT support for multi-function programs\")\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/b507119f0ce8088f51fbfee5387efd7e3d483908.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "0931830cc31204dfc2a37b84f2019caef1bcd0f0", "tree": "90e94bdacd16a34ee0c5332919f60576e2b0fc8f", "parents": [ "a0a0c785cbcaa72bb03c205eb61e5b0960b80ac2" ], "author": { "name": "Daniel Borkmann", "email": "daniel@iogearbox.net", "time": "Sun Nov 08 20:26:27 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Mon Nov 09 00:57:16 2026 +0000" }, "message": "bpf, arm64: Remove unused A64_BL, A64_BTI_C and A64_LDR32LIT\n\nA64_BL() and A64_LDR32LIT() never had a user. A64_BTI_C lost its last\nuser when commit a3f25d614bc7 (\"bpf, arm64: Fix BTI type used for\nfreplace attached functions\") made the prologue emit BTI JC. Remove\nthem.\n\nSigned-off-by: Daniel Borkmann \u003cdaniel@iogearbox.net\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/797791cc4e63fee4c1642c04bb568a69d7dfadc5.1794165614.git.daniel@iogearbox.net\n" }, { "commit": "a0a0c785cbcaa72bb03c205eb61e5b0960b80ac2", "tree": "644402952b9a355f8a1760c4ad22fdf9a2bc1696", "parents": [ "96cb0d6e71880bda07fc48f6de322608f266f55b" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sun Nov 08 16:37:10 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sun Nov 08 18:41:40 2026 +0000" }, "message": "selftests/bpf: Don\u0027t include \u003clinux/ptrace.h\u003e in BPF progs\n\nBPF CI cannot build the selftests on aarch64 since its image has new\nkernel headers:\n\n CLNG-BPF [test_progs] freplace_attach_probe.bpf.o\n In file included from progs/freplace_attach_probe.c:4:\n In file included from /usr/include/linux/ptrace.h:188:\n /usr/include/aarch64-linux-gnu/asm/ptrace.h:96:2: error: unknown type name \u0027__u128\u0027\n 96 | __u128 vregs[32];\n\nCommit d4bf9e08d412 (\"arm64: uapi: Use __u128 instead of __uint128_t in\nUAPI headers\") made asm/ptrace.h use the type of uapi/linux/types.h.\nBPF progs are built with -Itools/include/uapi, so their \u003clinux/types.h\u003e\nis the copy in tools, which doesn\u0027t have it.\n\nEight files in progs/ include \u003clinux/ptrace.h\u003e, and 20 progs are built\nfrom them: pyperf*, strobemeta*, plain_c_strobemeta_bpf_loop,\nfreplace_attach_probe, test_core_extern, test_perf_branches,\ntest_perf_buffer, test_rdonly_maps. None of them looks into struct\npt_regs or uses a PT_REGS_*() macro. At most it is the type that the\nargument of the prog points to, and bpf_helper_defs.h declares it.\n\nDrop the include. freplace_attach_probe.c replaces a function that takes\na struct pt_regs *, and the kernel wants a pointer to a struct there, not\nto a forward declaration. It takes the type from vmlinux.h.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261108163710.1881321-1-alexei.starovoitov@gmail.com\n" }, { "commit": "96cb0d6e71880bda07fc48f6de322608f266f55b", "tree": "c89a2b3777ca428a233af2ec018a6f2c9c565137", "parents": [ "1f56fd122f47dff50579567ee2522007e1763e11", "35fca41d5746797260fdea2fe14032f73bfc013f" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sun Nov 08 16:13:13 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sun Nov 08 16:13:14 2026 +0000" }, "message": "Merge branch \u0027bpf-one-basic-block-and-the-way-to-it-in-the-level-1-log\u0027\n\nAlexei Starovoitov says:\n\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\nbpf: One basic block and the way to it in the level 1 log\n\nFrom: Alexei Starovoitov \u003cast@kernel.org\u003e\n\nAt log level 1 the verifier prints each insn when it verifies it. It used\nto follow one path at a time. push_stack() noted the end of the log when\nit put a branch aside, and pop_stack() moved the log back there when it\ntook the branch. So the log was the path from the first insn to the\ncurrent one: never larger than the longest path, and for a rejected prog\nthe path to the error.\n\nSince commit 2d0b457611c0 (\"Merge branch\n\u0027bpf-a-verifier-that-joins-states\u0027\") there are no paths. Basic blocks are\nverified in the order of the control flow graph, and the states that get\nto a block are joined. pop_stack() is gone, push_stack() notes nothing,\nand nothing else moves the log back while a function is verified. The log\nholds every block that was verified, each time it was verified.\n\nTwo things broke:\n\n- The log of a large prog is many times larger, 15 to 35 times for the\n three below. The text is dropped when the prog is safe, but the buffer\n has to hold the log at its largest. Valid progs of Cilium, katran and\n scx that are loaded the way bpf(2) shows it, with log_level 1 and\n a static buffer, get -ENOSPC with 64K.\n- The log of a rejected prog is not the path to the error. It has all\n blocks, both arms of each branch, in the order in which they were\n verified.\n\n1 Two helpers for the log: take its end out, append it later.\n2 The level 1 log holds one basic block at a time. When a block is\n rejected the way to it is printed in front of it, from the edges that\n the states at joins came by. Nothing is verified twice. A prog that\n loads pays two stores per state.\n\nlog_true_size at level 1 one path all blocks this series\n bpf_lxc/tail_ipv4_ct_egress 51434 774446 7652\n bpf_host/cil_to_netdev 101212 1789015 9778\n katran/balancer_ingress 103567 3668559 22603\n progs with -ENOSPC at 64K 2841 5503 45\n the builds of a prog as one 435 1018 23\n\nLevel 2 is not changed.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n\nLink: https://patch.msgid.link/20261108053937.4134138-1-alexei.starovoitov@gmail.com\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\n" }, { "commit": "35fca41d5746797260fdea2fe14032f73bfc013f", "tree": "c89a2b3777ca428a233af2ec018a6f2c9c565137", "parents": [ "ffb7ea52c7af34307315260a60cd920d4c731755" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sun Nov 08 05:39:37 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sun Nov 08 16:13:13 2026 +0000" }, "message": "bpf: Keep one basic block in the level 1 log and print the way to it\n\nbpf(2) shows how to load a prog: .log_level \u003d 1 and a static buffer.\nCilium\u0027s bpf_lxc/tail_ipv4_ct_egress loaded that way with 64K. Now it gets\n-ENOSPC, like 2097 progs of the selftests, Cilium, scx, katran, bpfjailer\nand Rust crates.\n\nAt level 1 each insn is printed when it is verified. The verifier used to\nfollow one path at a time. At a conditional jump push_stack() put the\nother branch aside and noted the end of the log. When the path was done\npop_stack() took the branch and moved the log back:\n\n push_stack(): elem-\u003elog_pos \u003d env-\u003elog.end_pos;\n pop_stack(): bpf_vlog_reset(\u0026env-\u003elog, head-\u003elog_pos);\n\nSo the log was the path from the first insn to the current one. It never\ngot larger than the longest path, and when a prog was rejected it was the\npath to the error.\n\nNow there are no paths. Basic blocks are verified in the order of the\ncontrol flow graph, and the states that get to a block are joined. What\npush_stack() puts aside goes to the block that it is for. pop_stack() and\nlog_pos are gone, and nothing else moves the log back while a function is\nverified. Each block adds its text each time it is verified: 4057 insns\nand 774446 bytes for tail_ipv4_ct_egress, whose longest path had 51434.\n\nThe text is dropped when the prog turns out to be safe. That doesn\u0027t help:\nbpf_vlog_finalize() compares the buffer with len_max, the largest size\nthat the log ever had. And the log of a rejected prog is not the path to\nthe error any more. It has all blocks, both arms of each branch, in the\norder in which they were verified.\n\nThe old log cannot come back as it was. The state at the start of a block\nis the join of all that got there: no path leads to it.\n\nMove the log back in front of each basic block, so that it holds one block\nat a time. When a block is rejected print the way to it from what the\nverifier holds at that time. It keeps the states where ways meet. Such a\nstate knows the edge that it came by, after a join the edge that changed\nit last: the edge that brought the bad value. There may be several states\nat an insn, so a state gets a u32 that tells which kept state it comes\nfrom. A block in between has one predecessor. The block that fails is in\nthe log already: stash it, print the way, append it. Nothing is verified\ntwice.\n\n if (skb-\u003emark \u003d\u003d 1) i \u003d skb-\u003elen \u0026 63;\n else if (skb-\u003emark \u003d\u003d 2) i \u003d skb-\u003epriority;\n else i \u003d 7;\n if (skb-\u003eprotocol \u003d\u003d 8) v[0] \u003d 1;\n return v[i];\n\n from -1 to 0: R1\u003dctx() R10\u003dfp0\n ...\n 10: (16) if w2 \u003d\u003d 0x2 goto pc+5\n ; i \u003d skb-\u003epriority; @ pick.bpf.c:22\n 16: (61) r1 \u003d *(u32 *)(r6 +32)\n from 16 to 17: R0\u003dmap_value(map\u003dm,ks\u003d4,vs\u003d64) R1\u003dscalar(smin\u003d0,smax\u003d..\n ; if (skb-\u003eprotocol \u003d\u003d 8) @ pick.bpf.c:25\n 17: (61) r2 \u003d *(u32 *)(r6 +16)\n 18: (56) if w2 !\u003d 0x8 goto pc+2\n 21: R0\u003dmap_value(map\u003dm,ks\u003d4,vs\u003d64) R1\u003dscalar(smin\u003d0,smax\u003dumax\u003d0xfff..\n ; return v[i]; @ pick.bpf.c:27\n 21: (0f) r0 +\u003d r1 ; R0\u003dmap_value(map\u003dm,ks\u003d4,vs\u003d64,smin\u003d..\n 22: (71) r7 \u003d *(u8 *)(r0 +0)\n R0 unbounded memory access, make sure to bounds check any such access\n\nA block is on the way once, so the way goes around a loop once. Where\na block would come again the way goes on from its dominator: all that gets\ninto the loop goes through it. The earlier rounds are left out, what is in\nfront of the loop is not. A function that is verified in the frames of its\ncaller is on the way once too, for its last call. Its dominators end at\nits first insn, so the way begins where the call before that one returns.\n\nA signal ends the print. A round that do_check_all() drops gets no way, so\nbpf_flow_loops_lost_bound() can be asked twice now. Level 1 doesn\u0027t show\nthe states behind the insns of the way and the bodies of subprogs that are\nverified on their own. Level 2 has them. It is not changed, and six tests\nthat look at such a state get __log_level(2), with the five others that\ncome out of the same macros.\n\nlog_true_size at level 1 one path all blocks this patch\n bpf_lxc/tail_ipv4_ct_egress 51434 774446 7652\n bpf_host/cil_to_netdev 101212 1789015 9778\n katran/balancer_ingress 103567 3668559 22603\n progs with -ENOSPC at 64K 2841 5503 45\n the builds of a prog as one 435 1018 23\n\nA prog that loads pays two stores of a u32 per state: ftrace sees no call\nof bpf_flow_print_way(). The longest way, 713 lines, takes 0.4 ms.\n\nFixes: 5395aa9bbeb5 (\"bpf: Verify programs as a fixpoint over the control flow graph\")\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261108053937.4134138-3-alexei.starovoitov@gmail.com\n" }, { "commit": "ffb7ea52c7af34307315260a60cd920d4c731755", "tree": "5842f351b481b72677ed805d17fbb468f4b5b13c", "parents": [ "1f56fd122f47dff50579567ee2522007e1763e11" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sun Nov 08 05:39:36 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sun Nov 08 16:13:13 2026 +0000" }, "message": "bpf: Take the end of the verifier log out and append it later\n\nWhen a prog is rejected the log ends with the basic block that fails and\nthe message. How the verifier got to that block can be told only then,\nand a reader wants it in front of the block:\n\n the way to the block printed last\n the block, the message printed first\n\nThe block is not going to be verified again to print it again. The kernel\nhas no copy of the text either: the log is in the buffer of the user.\n\nbpf_vlog_stash() reads back what was written since a position and moves\nthe log back to it. bpf_vlog_unstash() appends that text to what was\nwritten in between.\n\nA buffer that is too small holds a part of the text: a rolling one has\nlost the start, a fixed one the end. There may be no buffer at all. What\nis not there is counted. So log_true_size, -ENOSPC and the bytes in the\nbuffer are those of a log that was written in the final order, whatever\nthe size of the buffer.\n\nThe stash is never larger than the buffer, which may have 1G. When memory\nis short the allocation has to fail and not to call the OOM killer:\n__GFP_RETRY_MAYFAIL. The log is left as it is then.\n\nThe text is not looked at. If another thread has changed it the caller\ngets these bytes back, cut at a zero byte.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261108053937.4134138-2-alexei.starovoitov@gmail.com\n" }, { "commit": "1f56fd122f47dff50579567ee2522007e1763e11", "tree": "3564ffa67254081c3dc4721ab05bc92a57ded78e", "parents": [ "3fba1a6cf43a594980c024562adf5b1591c713bb" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 17:58:19 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 19:44:47 2026 +0000" }, "message": "selftests/bpf: Test short loops that carry what they load\n\nA loop of 4 iterations loads a number and sets a flag if the number is a\nvalid index. The next iteration tests the flag only. Another loop takes the\nindex of the next iteration from a table in .rodata. Both load if the loop\nis walked. Each has a twin that reads past the end of the map value.\n\nA loop that fills a stack slot with what it loads is not walked if the slot\nis only copied later: 17 insns for 40 iterations.\n\nThe two tests of a first iteration that is kept apart get 100000\niterations. 10 are walked now.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107175819.3707050-2-alexei.starovoitov@gmail.com\n" }, { "commit": "3fba1a6cf43a594980c024562adf5b1591c713bb", "tree": "bb5db85b06c2f3f4bde02ae3e3f2fd6a935c7055", "parents": [ "dfc18dfc0da79d44d50c39c9916cdcb1942c9184" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 17:58:18 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 19:44:47 2026 +0000" }, "message": "bpf: Walk a short loop for what it loads if something looks at it\n\n for (i \u003d 0; i \u003c 64; i++) {\n if (have)\n sum +\u003d t-\u003epid;\n t \u003d v-\u003etask; /* __kptr: a task or NULL */\n have \u003d t \u0026\u0026 t-\u003eprio \u003e 100;\n }\n\nt is loaded anew in each iteration. The first iteration of such a loop is\nverified on its own, and the states that return to the loop head stand for\nthe other iterations. There have becomes [0, 1], also next to t \u003d\u003d NULL:\n\n R2 invalid mem access \u0027scalar\u0027\n\n for (i \u003d 0; i \u003c 64; i++) {\n sum +\u003d a[cur]; /* u8 a[16] */\n cur \u003d order[i]; /* static const u8 order[64] */\n }\n\ncur is order[0] after the first iteration and a byte after the next one:\n\n R4 unbounded memory access, make sure to bounds check any such access\n\nBoth load if the verifier goes through the iterations one by one: have goes\nwith t, each order[i] is a constant. It did so before the first iteration\nwas kept apart, and it still does for what a call returns.\n\nDo the same for what is loaded and then looked at: t is the base of a load,\ncur is an offset. A stack slot that the loop fills and that is only copied\nlater is no reason for a walk. test_rbtree_remove_many_noalloc() of\nlibarena is walked again: 22060 -\u003e 27699 insns.\n\nFixes: df9b13a441c9 (\"bpf: Keep the first iteration of a counted loop apart\")\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107175819.3707050-1-alexei.starovoitov@gmail.com\n" }, { "commit": "dfc18dfc0da79d44d50c39c9916cdcb1942c9184", "tree": "cf00a74b5bc94e76c485588791dcc322315e6d18", "parents": [ "fd875e35a25e73514b2f89f51bbb7c6baace3d7d" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 17:50:06 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 19:40:48 2026 +0000" }, "message": "bpf: Don\u0027t attach to a subprog that is called in a recursion\n\nsum_to() of verifier_budget.c calls itself:\n\n sum_to: if r1 !\u003d 0 goto 1f; r0 \u003d 0; exit;\n 1: r6 \u003d r1; r1 +\u003d -1; call sum_to; r0 +\u003d r6; exit;\n\nIt goes on while r10 is in the upper half of the kernel stack. The lower\nhalf is for what it calls. check_max_stack_depth() looks at that chain of\ncalls when the prog is loaded. It cannot look at what is attached to\na subprog of the chain later. For that reason an extension cannot replace\nsuch a subprog.\n\nfentry and fexit progs can still be attached to it. The trampoline and the\nprog run below r10 of a subprog that passed its check. The frames of a\ntracing prog are in its private stack, but not all of them: not when it has\ntail calls or uses R12, not the frames of subprogs with stack arguments on\nx86-64, not the frames below 64 bytes. Such a prog takes up to 9K of the\nkernel stack, and nothing left room for it.\n\nRefuse them like extensions, with one message for all:\n\n Cannot attach to sum_to, which is called in a recursion\n\nThe main prog is never called in a recursion. fentry and fexit progs\nattach to it as before.\n\nFixes: eaea73907052 (\"bpf: Allow recursive subprogs\")\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107175006.3591773-1-alexei.starovoitov@gmail.com\n" }, { "commit": "fd875e35a25e73514b2f89f51bbb7c6baace3d7d", "tree": "97cdde66b2d901cf768e11ce7e8ab4d42799c4eb", "parents": [ "2d0b457611c06304138754a05e0873cc18acfb7e", "d877bd038cc6d09fcf1746bbc031bb2bc0ba8a02" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 18:09:24 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 18:09:24 2026 +0000" }, "message": "Merge branch \u0027bpf-fixes-for-the-verifier-that-joins-states\u0027\n\nAlexei Starovoitov says:\n\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\nbpf: Fixes for the verifier that joins states\n\nFrom: Alexei Starovoitov \u003cast@kernel.org\u003e\n\nFixes for commit 2d0b457611c0 (\"Merge branch\n\u0027bpf-a-verifier-that-joins-states\u0027\"), from review and from BPF CI.\n\n1-2 A number that wraps in front of the jump that counts a loop gets\n a wrong residue behind the jump. The verifier then checks numbers\n that the register never has.\n3-4 Two of the new tests fail in BPF CI: one with GCC BPF, one on s390x.\n5-7 The same kind, no job shows it today: a message with GCC, a target of\n fentry that is not in BTF, five tests with an arena that run at the\n same time under KASAN.\n8-9 Valid progs that throw one of several error codes are rejected.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n\nLink: https://patch.msgid.link/20261107170306.2831028-1-alexei.starovoitov@gmail.com\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\n" }, { "commit": "d877bd038cc6d09fcf1746bbc031bb2bc0ba8a02", "tree": "97cdde66b2d901cf768e11ce7e8ab4d42799c4eb", "parents": [ "ed10b8a49c398cf0e1223954f5c4d5a6801b5923" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 17:03:06 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 18:09:24 2026 +0000" }, "message": "selftests/bpf: Test a flag that goes with the cookie of bpf_throw()\n\n if (err \u003d\u003d -EPERM || err \u003d\u003d -EACCES)\n bpf_throw(err);\n\nAn LSM prog, no exception callback. The compiler keeps the condition in a\nflag. Two jumps are between the place where the paths meet and the test of\nthe flag. That is too far for the rule that keeps 0 and 1 of a flag apart.\nIn the second prog the flag goes with the number that the prog must not\nreturn.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107170306.2831028-10-alexei.starovoitov@gmail.com\n" }, { "commit": "ed10b8a49c398cf0e1223954f5c4d5a6801b5923", "tree": "d1a42e373f314b75e4b39ff1c6be26599220978d", "parents": [ "b992d6ed753166721cf089a7e98be563d1ca5123" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 17:03:05 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 18:09:24 2026 +0000" }, "message": "bpf: A join must leave the cookie of bpf_throw() alone\n\nAn LSM prog without an exception callback:\n\n err \u003d policy(file); /* 1: no rule, 2: audit, 0, -EPERM, -EACCES */\n count(a); count(b); count(c);\n if (err \u003d\u003d -EPERM || err \u003d\u003d -EACCES)\n bpf_throw(err);\n return 0;\n\nThe compiler decides the \u0027if\u0027 where err is set, and keeps a flag. All\npaths meet, then the flag is tested. In the join err is [-13, 2]:\n\n At program exit the register R1 has .. should have been in [-4095, 0]\n\nThe prog is valid, and it loaded when the verifier followed each path. It\nhas the shape of cil_sock4_connect() of Cilium, with bpf_throw() in place\nof bpf_set_retval().\n\nWithout an exception callback the prog returns the cookie. Thus\ncheck_kfunc_call() compares r1 of bpf_throw() with the range of the prog\ntype, like r0 at exit. That check is not in check_func_arg() either. Add r1\nto bpf_call_checked_arg_regs() by hand, like r1 of bpf_set_retval(). States\nin which the flag and the cookie differ are not joined then.\n\nThe same table tells whether something looks at a number that a short loop\ncounts. This prog loads too:\n\n for (i \u003d 0; i \u003c 3; i++)\n if (hit(i))\n n++;\n bpf_throw(n); /* cgroup_skb/egress takes [0, 3] */\n\nFixes: af6bda3802af (\"bpf: Tell which arguments of a call a join must leave alone\")\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107170306.2831028-9-alexei.starovoitov@gmail.com\n" }, { "commit": "b992d6ed753166721cf089a7e98be563d1ca5123", "tree": "0209a24f3b9254064b34cb1402ced6d758cd3db2", "parents": [ "57c57a40807ad74d7e48833597a52d7e37d5252a" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 17:03:04 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 18:09:24 2026 +0000" }, "message": "selftests/bpf: Run the plain C tests with an arena serially\n\nCommit a14f9ba080c1 (\"selftests/bpf: Run arena tests serially\") made\narena_htab, arena_list, arena_strsearch and the other arena tests serial.\nWith KASAN every arena takes 512 MB of shadow memory while it lives, and\nseveral arenas at a time exhaust the memory of a small CI VM.\n\nThe plain C forms of these tests make the same arenas. Their names are next\nto each other, so test_progs -j gives them to its workers at the same time.\nIn a KASAN VM with 4 cpus and 5G\n\n ./test_progs -j -t plain_c\n\nleaves 0.4G of memory available at its lowest point. Make the five tests\nwhose prog file has an arena map serial: 2.4G stay available.\n\nplain_c_arena_race has no arena. It stays parallel.\n\nFixes: b5ae07f77d27 (\"selftests/bpf: Test progs without bpf_for(), zero, can_loop and such\")\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107170306.2831028-8-alexei.starovoitov@gmail.com\n" }, { "commit": "57c57a40807ad74d7e48833597a52d7e37d5252a", "tree": "07646b2920e34c71cced959775959d972dee5ef3", "parents": [ "98cc0b224608c95781303a2000b8ca371fe57efc" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 17:03:03 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 18:09:24 2026 +0000" }, "message": "selftests/bpf: Skip plain_c_arena_race without zap_vma_range() in BTF\n\nplain_c_arena_race has the fentry prog of arena_race.c. libbpf looks for\nits target, zap_vma_range(), in the BTF of vmlinux. When the function is\nnot there the load fails:\n\n failed to find kernel BTF type ID of \u0027zap_vma_range\u0027: -ESRCH\n\nprog_tests/arena_race.c skips the subtests that need the prog in this\ncase. Do the same for the plain C form. The kernels of BPF CI have the\nfunction: no job fails today.\n\nFixes: b5ae07f77d27 (\"selftests/bpf: Test progs without bpf_for(), zero, can_loop and such\")\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107170306.2831028-7-alexei.starovoitov@gmail.com\n" }, { "commit": "98cc0b224608c95781303a2000b8ca371fe57efc", "tree": "799c8fdc716fc8fbce9c0e61a45a22b2c464d3bf", "parents": [ "f567c4b7af1822751bc1793bd31d4c1e1c323c79" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 17:03:02 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 18:09:24 2026 +0000" }, "message": "selftests/bpf: Expect GCC\u0027s first error in test_alloc_double_release\n\ntest_alloc_double_release has two errors: it releases the cpumask twice\nand it does not check create_cpumask() for NULL. The test expects the\nmessage for the first one:\n\n R1 type\u003dscalar expected\u003dptr_, trusted_ptr_, rcu_ptr_\n\nGCC gives the path with NULL its own copy of the two calls. The verifier\ngets there first and says:\n\n Possibly NULL pointer passed to trusted R1\n\nThe prog is rejected with both compilers. Expect GCC\u0027s message with GCC.\n\nFixes: dd43eeaf99eb (\"selftests/bpf: Adjust tests to new verdicts, messages and order\")\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107170306.2831028-6-alexei.starovoitov@gmail.com\n" }, { "commit": "f567c4b7af1822751bc1793bd31d4c1e1c323c79", "tree": "ed8b5bf4f5c955f83e463f3b52ed951ac95eed9d", "parents": [ "ce4b64ed8b2256b44433c3773ecbef1a463a2474" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 17:03:01 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 18:09:23 2026 +0000" }, "message": "selftests/bpf: Skip plain_c_test_wakeup_source without the kfuncs\n\nThe s390x jobs of BPF CI fail in:\n\n plain_c_test_wakeup_source/iterate_wakeupsources\n\nThe prog calls bpf_wakeup_sources_get_head(), _read_lock() and\n_read_unlock(). They are in drivers/base/power/wakeup.c, which is built\nwith CONFIG_PM_SLEEP. s390 has no suspend and no hibernation, so its kernel\ndoes not have the kfuncs and the load fails:\n\n libbpf: extern (func ksym) \u0027bpf_wakeup_sources_get_head\u0027: not found in kernel or module BTFs\n\nprog_tests/wakeup_source.c skips when bpf_wakeup_sources_get_head() is not\nin the BTF of vmlinux. Do the same for the plain C form of its prog.\n\nFixes: b5ae07f77d27 (\"selftests/bpf: Test progs without bpf_for(), zero, can_loop and such\")\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107170306.2831028-5-alexei.starovoitov@gmail.com\n" }, { "commit": "ce4b64ed8b2256b44433c3773ecbef1a463a2474", "tree": "dc0aefa2af08dbe287e69980e1fe922a1c5c5aac", "parents": [ "589b23cbc6c6a310b0f6c5ba866412e397fe85d8" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 17:03:00 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 18:09:23 2026 +0000" }, "message": "selftests/bpf: Skip the stack walker of verifier_loop_latch with GCC\n\nThe GCC BPF jobs of BPF CI fail in:\n\n verifier_loop_latch/latch: frames of a stack walker\n\nThe test is about the outer loop: \u0027if (frames \u003d\u003d 8) break;\u0027 counts it, so\nout[idx + j] stays within the 256 words of the value. GCC unrolls the\ninner loop\n\n for (j \u003d 0; j \u003c n; j++)\n out[idx + j] \u003d b + c + d + e;\n\nby 8, walks \u0027out\u0027 with a pointer and ends the loop with \u0027if r9 !\u003d r5\u0027,\nwhere both registers point into the map value. The verifier finds no\ncount for that and says:\n\n invalid access to map value, value_size\u003d2048 off\u003d2048 size\u003d8\n\nSkip the prog with GCC, as plain_c_verifier_loop_as_is.c does for the\nsame reason. The prog with nine frames is rejected with both compilers:\nit stays.\n\nFixes: d0a8c63bfc66 (\"selftests/bpf: Test loops that are counted, walked or widened\")\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107170306.2831028-4-alexei.starovoitov@gmail.com\n" }, { "commit": "589b23cbc6c6a310b0f6c5ba866412e397fe85d8", "tree": "32c978adc7e5fcdff4105898fb44ecfe0f87da82", "parents": [ "914dd83543fce6dbe3603be7825aad8d70cea23d" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 17:02:59 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 18:09:23 2026 +0000" }, "message": "selftests/bpf: Test a number that wraps in front of the jump that counts\n\nA number goes up by 3. In front of the jump that counts the loop it moves\nover S64_MAX in one pair of progs and by S64_MAX in the other. The store\nbehind the jump takes it as an index. In the progs that have to be rejected\nthe store is one byte behind the value at run time.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107170306.2831028-3-alexei.starovoitov@gmail.com\n" }, { "commit": "914dd83543fce6dbe3603be7825aad8d70cea23d", "tree": "0f27fc341c46263574f72e86979e79fcbf322103", "parents": [ "2d0b457611c06304138754a05e0873cc18acfb7e" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 17:02:58 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 18:09:23 2026 +0000" }, "message": "bpf: Leave a number alone that wraps in front of the jump that counts\n\n\tfor (i \u003d 0, n \u003d first; ; i++, n -\u003d 97) {\n\t\tn +\u003d 100;\n\t\tif (i \u003d\u003d 2)\n\t\t\tbreak;\n\t\tuse(n);\n\t}\n\nn is linear at the jump that counts: \u0027first + 100 + 3 * k\u0027. Behind the jump\nbpf_clamp_scev_regs() gives it the range of one iteration less. When first\nis a constant it gets the step 3 and the residue \u0027(first + 100) mod 3\u0027 too.\nWhen first + 100 goes over S64_MAX the signed value is 2^64 less. 2^64 is\nnot a multiple of 3, so the residue is another one. reg_bounds_sync()\nrounds the range to numbers that n never is and drops the numbers that it\nis. What takes n as an index is checked for the wrong numbers.\n\nscalar_step_add() drops the step of a sum that can wrap. Set no range at\nall in this case. The register keeps what the state has. That went through\nscalar_step_add(), and it has the low bits of n, which bpf_set_reg_range()\nforgets.\n\n\u0027bounds.base + moved\u0027 can overflow s64 when n itself doesn\u0027t wrap. Add the\nresidues, as scalar_step_add() does.\n\nFixes: a00c8eafb381 (\"bpf: A loop is one iteration shorter behind the jump that counts it\")\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107170306.2831028-2-alexei.starovoitov@gmail.com\n" }, { "commit": "2d0b457611c06304138754a05e0873cc18acfb7e", "tree": "b2cee612f0c67460402e872fa237c5aeb54242a1", "parents": [ "ad6472e01a5f5e8968a2fbe7623c84368b6a95e3", "b5ae07f77d27b51666fb9fa2bcc7b810f2e3e66e" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:55 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:55 2026 +0000" }, "message": "Merge branch \u0027bpf-a-verifier-that-joins-states\u0027\n\nAlexei Starovoitov says:\n\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\nbpf: A verifier that joins states\n\nFrom: Alexei Starovoitov \u003cast@kernel.org\u003e\n\nThe verifier follows each path of a prog, and each branch can double the\nnumber of paths. The work grows with the paths, not with the prog:\n insns processed today this series\n rust-bpf scx_beerland/beerland_init_task 1000001 * 16430\n rust-bpf scx_qmap/qmap_init_cids 131088 * 196\n scx scx_eevdf/eevdf_dispatch 350041 15322\n Cilium bpf_host/cil_to_netdev, Oct 2026 64658 7538\n * \"BPF program is too large\", \"The sequence of 8193 jumps is too complex\"\n\nAuthors cut their progs until they fit. Nobody can cut core, alloc and the\ncrates of Rust: of the 653 progs of https://github.com/4ast/rust-bpf 187\nload today, 170 hit one of these limits, 164 get \"infinite loop detected\"\nand 122 \"recursive call\". Now 648 load, and the corpora of C progs below\nlose none. For rust-bpf both kernels have 4 kfuncs on top, see Numbers.\n\nLoops in BPF progs are written for the verifier, not for the reader:\n\n bpf_qdisc_fifo.c bpf_for(i, 0, sch-\u003eq.qlen) {\n arena_htab.c for (i \u003d zero; i \u003c 100000 \u0026\u0026 can_loop; i++) {\n rbtree_search_kptr.c while (rb_n \u0026\u0026 can_loop) {\n tailcall_bpf2bpf2.c barrier_var(ret); return ret;\n\nNow plain C loads: \u0027for (i \u003d 0; i \u003c 100000; i++)\u0027, \u0027while (rb_n)\u0027. The last\npatch has 34 progs of the selftests without these macros. bpf-next rejects\nall of them, five in some flavours of test_progs only.\n\nThe idea\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\nDo not follow paths. Where paths meet, join their states: r1\u003d1 and r1\u003d5\ngive r1\u003d[1,5]. Repeat until no state changes. States stay apart only if\nthey have no join, or if a later check depends on the difference.\n loops counted by scalar evolution: one state covers all iterations\n walked: a state per iteration, while constants decide an exit\n all other loops: join at the head, widen, add may_goto\n subprogs A static subprog is verified for the states at its entry, not\n for each chain of calls. Recursion is the same, with widening.\n run time may_goto limits the time of loops and of recursion. r10 limits\n the depth: it must be in the upper half of its kernel stack.\n\nWhat users see\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n - The limits of 1M processed insns and 8192 jumps are gone. The limits are\n on states, for a prog of N insns: 1024 at an insn, 16 * N + 4096 at\n a time, 256 * N + 64K in all.\n - \"infinite loop detected\" is gone: the verifier adds may_goto. A loop\n that has no exit gets \"loop at insn N never exits\".\n - A loop is counted by a jump in the middle of its body, by a jump that\n sets a flag, by a copy of the counter.\n - may_goto is also added to 5 progs of the table below that load today:\n loop1, loop2, loop5, tcp_autolowat_enqueue_rcvq (GCC), chaos_enqueue\n (as of v2).\n - Recursion is allowed on x86-64 and arm64. Patch 22 lists the exceptions.\n - All added may_goto of an invocation share its time slice of 250 ms. Then\n the prog returns 0. A subprog that cannot unwind, or a frame that holds\n a lock or a reference, leaves the loop. If the code behind the loop\n reads what only the loop sets, the subprog returns 0. The stderr stream\n has the cause.\n - A subprog that returns void can have a tail call or LD_ABS. LLVM 23\n makes \u0027void\u0027 of an \u0027int\u0027 that no caller reads.\n - With CAP_PERFMON a part of a pointer can be spilled, and 32-bit add to\n a pointer and ops on two pointers make a number. With it \"invalid size\n of register spill\" and \"32-bit pointer arithmetic prohibited\" are gone.\n - A join loses the relation between scalars. This is rejected now:\n if (c) { i \u003d 3; n \u003d 4; } else { i \u003d 7; n \u003d 8; }\n x \u003d arr[n - i]; n - i is [-3, 5]\n - A cgroup_skb prog whose r0 can be 2 or 3 attaches to egress only. That\n holds for a range too: \u0027return 1\u0027 and \u0027return 2\u0027 are joined to [1, 2].\n - The log has no \"mark_precise:\", \"N: safe\", \"depth\u003d\" and no scc column.\n Level 2 shows \"from 13 to 9: within\", \"joined\" or \"widened\" where states\n meet. The statistics line keeps its format: \"limit 0\", \"mark_read 0\".\n - BPF_F_TEST_STATE_FREQ is accepted and has no effect.\n\nNumbers\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\nThe tables are those of v2. A: bpf-next 8424858a5de0. B: the series, the\nsame objects. The selftests that the series adds or changes are not\ncounted. None of them is lost. v4 against v3 on these corpora and rust-bpf:\nno prog is lost, insns +0.8%, states +1.0%, mem -0.9%.\n\nCorpus Progs Lost Gained Insns States Mem Time\n--------------------- ----- ---- ------ ----- ------ ---- ----\nselftests 3043 0 1 -63% +120% -18% -27%\nselftests, no_alu32 2905 0 1 -66% +86% -27% -34%\nselftests, cpuv4 2914 0 1 -64% +96% -27% -32%\nselftests, bpf_gcc 2733 0 5 -69% +96% -16% -24%\n37 builds of Cilium 5189 0 0 -75% +11% -6% -31%\nsched-ext/scx 495 0 0 -89% -34% -66% -67%\nscx, as BPF CI has it 428 0 0 -85% -22% -38% -39%\ntools/sched_ext 240 0 0 -69% +37% +3% -11%\npublic progs of Meta 511 0 0 -85% -35% -55% -48%\nall 18458 0 8 -74% +10% -19% -36%\n\nProgs load in A and in B. The per cent compare sums over these progs:\n75.1M -\u003e 19.2M processed insns, 61 -\u003e 39 s. Mem is mem_peak of veristat.\nTime is the best of 3 runs on kernels without debug options. B counts each\nstate that arrives at a basic block as a state, A only those that it saves.\nGained: loop3 in the 4 builds, 4 progs that A rejects only in GCC\u0027s code.\nOf the progs that take 1000 insns or more in B, two take over 5% more than\nin A. loop5, 82 -\u003e 4182: a walk up to its limit of 4096 insns, then a join.\nres_spin_lock_test_held_lock_max, 2356 -\u003e 4088: states that hold different\nnumbers of locks have no join.\n\nrust-bpf Progs load in A load in B B: insns time\n16 schedulers 225 52 225 1.6M 1.9 s\ncrates 428 135 423 8.3M 9.4 s\nThe insns are those of v4, like the four rows at the top of this letter.\nFor rust-bpf A and B have the kfuncs of patches 30-31 of [1] on top. They\nare in no series now. No released compiler emits the code of rust-bpf.\n\nHow to read the series\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\nStart with patch 7, the overview. Then 4-5, 13-14, 15, 17 and 19.\n 1-2 what is added to a prog: may_goto, the checks of recursion\n 3-5 union and widening of a range, join.c: the join of two states\n 6-10 data structures of flow.c, passes ahead of the main pass: order of\n the insns, places for may_goto, what later checks depend on\n 11-14 the sets of states, iterations, what is not joined, the merge\n 15-18 how states move: edges, calls and exits, loops, added edges\n 19 the switch. The check of one insn against one state is the same.\n 20-22 more counted loops, static subprogs on their own, recursion\n 23-26 removal of pruning, precision tracking and SCCs: 3382 lines\n 27-28 callx: a pointer to one of a set of functions, live registers\n 29-31 loops that are too long for a walk: the first iteration, what\n a call returns, where the jumps of the loop stop a number\n 32-34 more loops with a count: a jump in the middle of the body,\n a copy of the counter\n 35-37 rules of today\u0027s verifier that plain C runs into: subprogs that\n return void, parts of pointers, 32-bit add to a pointer\n 38-46 selftests: 38-39 adjust tests, 40-46 add tests\nEach patch builds. Patches 1-18 add the code that patch 19 switches to.\nSome selftests fail from patch 19 to 38.\n\nFollow-ups\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n - Documentation/bpf/verifier.rst: the algorithm, with examples.\n - Liveness: no spilled pointer is kept for reads that see only its bytes.\n - No second pass over the prog when a loop gets may_goto late: half of the\n insns for rust-bpf.\n - bpf_prog_info tells that an invocation of the prog was cut short.\n\nv3 -\u003e v4\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n - What comes around a loop, or back from the callback of bpf_loop(), is\n widened only with the state that it comes from. v3 took all states at\n the head: after \u0027ret \u003d 0; if (..) { denied++; ret \u003d -EPERM; }\u0027 in front\n of bpf_for() it widened ret, and rejected \u0027return ret\u0027 of an LSM prog\n (Eduard). The rule of flow_merge() on constant offsets of pointers in\n a loop is gone (patches 14, 15, 17, 19).\n - A jump in the middle of the body counts a loop, also when four other\n exits are nearer to the back edge. Ranges are one iteration shorter\n behind it. v3 rejected an index that is carried through bpf_for() and\n that only the count of such a jump bounds (Eduard, patches 32-33).\n - \u0027while (buf[i++] \u0026\u0026 i \u003c N)\u0027 is counted: its exit tests a copy of the\n counter (Eduard, patch 34).\n - A counted loop joins and widens what has no closed form. v3 forgot it if\n the loop was too long for a walk: \u0027if (n \u003c 8) v[n++] \u003d 0;\u0027 in two loops\n of 100 iterations was rejected with \u0027for\u0027 and loaded with bpf_for()\n (patch 20).\n - The exits of a loop by way of a flag are found in one pass against the\n edges. v3 searched from each edge, 4096 insns per back edge: with 30 ifs\n in front of \u0027while (more)\u0027 the loop lost its count (patch 18).\n - may_goto at the head of a loop leaves the subprog if the code behind the\n loop reads what only the loop sets: glob_match() of arena_strsearch\n needs no cond_break (patch 19).\n - Widening: a sum that no jump of the loop depends on becomes an unknown\n scalar in two passes, not in five. A bound that leaves a fixed stop and\n 32 bits is not tried at S64_MAX (patches 3, 4).\n - Patches 35-37 are new, with their tests in 45: what plain C runs into in\n today\u0027s verifier.\n - Patch 46 is new: 34 progs of the selftests in plain C that bpf-next\n rejects, five in some flavours of test_progs only.\n - Patches 29-35 of v3 are folded into the patches that add the code that\n they change: 3, 9, 14, 15, 19 and 21. 36-38 of v3 are 29-31.\n - Rebased to bpf-next 3e1821848412.\n\nv2 -\u003e v3\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n - A scalar argument of a static subprog loses delta together with its id.\n v2 kept delta, took wrong bounds in the callee and let an access out of\n bounds load (sashiko).\n - A loop with calls is walked for two iterations. v2 widened it at once\n and rejected strobemeta.h with two maps or two strings.\n - The frame of a recursive subprog grows before the stack of a chain of\n calls is checked, not after (bpf-ci, sashiko).\n - A loop that ends when a flag is false is counted by the jump that clears\n the flag, also when code stands between that jump and the test. States\n with 0 and 1 in a flag are not joined in front of its test.\n - Patches 29-38 of v3 are new. Each loads code that bpf-next loads and v2\n rejects: casts, the context in a struct, r0 at a dead exit (bpf-ci,\n sashiko), a register that only a loop sets (bpf-ci), loops that count\n down in bytes, loop-carried values in long loops, and numbers that only\n a jump of the loop stops (Ihor).\n\nv1 -\u003e v2\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\nv1 is part 3 of [1]. Its patches for the verifier of today and the time\nslice of may_goto are in bpf-next.\n - Recursion: may_goto and r10, no per-cpu counters of bytes and calls.\n - flow.c comes in 9 patches and join.c in 2. In v1 each was one patch.\n - No public prog of Meta is lost (Ihor): widening goes to fixed stops, and\n constants that are added to a pointer to the packet are not joined.\n - A state is compared only with the states of a related shape (Ihor).\n - bpf_iter_*_next() stops a loop only if the iterator was created before\n the loop (Ihor). A loop with two entries is walked.\n - Offloaded progs get neither may_goto nor recursion (Ihor).\n - The failures of v1 in BPF CI (s390x, arm64, gcc) are fixed.\n\n[1] https://lore.kernel.org/bpf/20261026025943.404450-1-alexei.starovoitov@gmail.com/\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n\nLink: https://patch.msgid.link/20261107033758.1547725-1-alexei.starovoitov@gmail.com\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\n" }, { "commit": "b5ae07f77d27b51666fb9fa2bcc7b810f2e3e66e", "tree": "b2cee612f0c67460402e872fa237c5aeb54242a1", "parents": [ "d13baed274e6a2224c34908bea81bb4c08b955b2" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:54 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "selftests/bpf: Test progs without bpf_for(), zero, can_loop and such\n\nLoops in BPF progs are written for the verifier, not for the reader:\n\n bpf_qdisc_fifo.c bpf_for(i, 0, sch-\u003eq.qlen) {\n arena_htab.c for (i \u003d zero; i \u003c 100000 \u0026\u0026 can_loop; i++) {\n rbtree_search_kptr.c while (rb_n \u0026\u0026 can_loop) {\n tailcall_bpf2bpf2.c barrier_var(ret); return ret;\n\nprogs/plain_c_X.c has progs of progs/X.c in plain C, with the maps,\nglobals, functions and headers that they use:\n\n bpf_for(i, a, b) for (i \u003d a; i \u003c b; i++)\n bpf_repeat(n) for (int i \u003d 0; i \u003c n; i++)\n i \u003d zero i \u003d 0\n cond \u0026\u0026 can_loop cond\n while (can_loop) while (1)\n barrier_var(x); cond_break; removed\n static __always_inline static\n\nOnly progs that bpf-next rejects in this form are taken. It says:\n\n 12 The sequence of 8193 jumps is too complex\n 7 infinite loop detected\n 6 BPF program is too large. Processed 1000001 insn\n 6 tail_call / LD_ABS is only allowed in functions that return \u0027int\u0027\n 3 invalid size of register spill\n\nbpf-next rejects all 34, five of them in some flavours of test_progs only.\nWith this series they load.\n\nRUN_TESTS() loads each prog, and runs it where the result is known.\narena_list, bpf_ma_ttrace and dynptr_success have short drivers.\nNothing bounds a walk of a list or a tree: the verifier adds may_goto.\nFive functions of xdp_lb_bench.c become subprogs, two with stack args.\nThree progs are unsafe with and without the macros: they keep __failure\nand __msg(). With GCC 11 of the 34 are skipped: __skip() says why.\npyperf600_bpf_loop and loop_takes_reference_once are still rejected in\nplain C: left out.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-47-alexei.starovoitov@gmail.com\n" }, { "commit": "d13baed274e6a2224c34908bea81bb4c08b955b2", "tree": "9c32d8b3f47cbc2282d2de7b615b49b2501b0075", "parents": [ "d14f973f1559634f646e3d3eeedaa68f13b17f34" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:53 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "selftests/bpf: Test pointers that become numbers and subprogs that return void\n\nThree patches let an insn pass that was refused. The prog is rejected where\nit uses the result for more than it is.\n\n\"bpf: Allow tail calls and LD_ABS in subprogs that return void\":\nverifier_tailcall.c, verifier_ld_ind.c. A subprog that returns void has\na tail call: it loads. Its caller counts on the 1 that the subprog leaves\nin r0 when the tail call is not taken: rejected, r0 is what the other prog\nreturns. The same for LD_ABS, which returns 0 when it fails. A subprog that\nreturns a pointer is refused with the message of check_btf_func().\n\n\"bpf: A part of a pointer that is spilled is a number\":\nverifier_spill_fill.c. 4 bytes of ctx are spilled and filled: a number with\nCAP_PERFMON, \u0027invalid size of register spill\u0027 without. Both halves are\nspilled and filled as one: the value is that of ctx, a load through it is\nrejected. ctx is spilled, then 4 bytes of ctx are stored over the spill:\nthe slot has the same bytes as before and is not a spilled pointer any\nmore.\n\n\"bpf: 32-bit add to a pointer and pointer op pointer make a number\":\nverifier_value_illegal_alu.c. \u0027w0 +\u003d 1\u0027 on a pointer to a map value loads\nwith CAP_PERFMON and is refused without. \u0027r1 \u003d r10; r1 |\u003d r10\u0027 has the\nvalue of r10: a store through it is rejected.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-46-alexei.starovoitov@gmail.com\n" }, { "commit": "d14f973f1559634f646e3d3eeedaa68f13b17f34", "tree": "e2e748c36abc9fd746558049a790e3794f2fcc77", "parents": [ "bab5cb94006e0a6fdb69be92537e97a47b4fca25" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:52 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "selftests/bpf: Test callx of one of a set of functions\n\n\u0027ops[i](x)\u0027 in C, and each \u0027{}\u0027 of a format string in Rust, is a load from\na table of functions at a variable offset, and callx. The load gives one\nregister that points to one of N functions.\n\n [S] \"bpf: Track a pointer to one of a set of functions\"\n [L] \"bpf: callx reads what the subprogs whose address is taken read\"\n\n file, test the rule that it pins\n ----------------------------- ------------------------------------------\n verifier_callx_rodata.c, callx_rodata_..\n one_of_two [S] The log has R2\u003dfunc(one_of\u003d2). callx\n calls the function that the index selects.\n callback_one_of_two [S] bpf_loop() gets the register: each\n function is verified as the callback.\n one_of_two_at_loop_head [S] callx is the head of a loop. The prog\n is unsafe in the fourth iteration with one\n of the two functions: rejected.\n verifier_callx_many.c, callx_rodata_..\n 400_functions [S] 3 states that have no join get to the\n load: 3 states at an insn. One state for\n each function is 1200, the limit is 1024.\n 4400_sets [S] More than 4096 sets: rejected.\n verifier_stack_arg.c\n callx_one_of_two_not_written [S] The caller does not store the stack\n arguments that both functions take:\n rejected.\n verifier_callx.c\n callx_reads_declared_args [L] r2 is live at callx: the callee does\n not read it, but its BTF declares it.\n\none_of_two, 400_functions and 4400_sets fail without [S], and\ncallx_reads_declared_args fails without [L]. The other three tests pass in\nboth cases. They examine the places where a set becomes one function.\n\nlibbpf adds the functions of a table to each prog of the object that has\ncallx. Thus the 400 functions are in a file of their own.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-45-alexei.starovoitov@gmail.com\n" }, { "commit": "bab5cb94006e0a6fdb69be92537e97a47b4fca25", "tree": "a73cd580b96e2424c6f17ffdf9f0bc49240df4f9", "parents": [ "d0a8c63bfc66b62e53918ce00192d09b1251335f" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:51 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "selftests/bpf: Test progs that run out of budget\n\nThe verifier does not prove that a prog ends. It adds may_goto to each loop\nthat it cannot bound, and a check to the entry of each recursive subprog.\nA prog is out of budget when may_goto times out or the check fails. No\nother test gets there: a mistake in the added code rejects nothing, it\nlocks up a cpu, or the prog goes on along an edge that nobody verified.\nLoad and run such progs. Each invocation must return, and the return value\nshows where the prog went on.\n\n [G] \"bpf: Add may_goto to the loops that the verifier marks\"\n [P] \"bpf: Order the insns, find what stops a loop and where may_goto\n can go\"\n [F] \"bpf: Verify programs as a fixpoint over the control flow graph\"\n [R] \"bpf: Limit depth and time of recursive subprogs at run time\",\n \"bpf: Allow recursive subprogs\"\n\n the prog out of budget\n ---------------------------------------------- -------------------------\n a loop, the prog holds nothing [G] the prog ends\n the same, the last exit is dead code [F] the prog ends\n a loop under a lock [G] the loop exits\n the same, the code after it needs p !\u003d NULL [G] reject\n a loop in a subprog [G] the loop exits\n the same, the call has unwind_goto [G] the subprog unwinds\n a landing pad does not release a lock [G] reject\n all registers are live at the added may_goto [G] none of them changes\n a loop has no exit, a nest of 17 loops [F] [P] reject\n may_goto of the prog does not leave the loop, [P] may_goto at the head,\n a jump to itself, a loop with two entries the prog ends\n may_goto at the head, in a subprog, the code [F] the subprog returns 0\n behind the loop reads what only the loop sets\n an iterator does not stop the loop around it [F] the prog ends\n recursion is too deep, no unwind_goto [R] the subprog returns 0\n the kernel stack where such a recursion ends [R] a half of it is free\n recursion is too deep, calls have unwind_goto [R] the landing pad runs\n recursion is not deep, but makes 2^60 calls [R] the prog returns\n recursion through bpf_loop(), or in a loop [R] the prog returns\n recursion through a global subprog and a table [R] reject\n a timer callback arms itself again [R] no recursion\n\nThe edge of an added may_goto is an edge of the prog. 10 more progs are\nunsafe only on this edge: a caller that counts on what only the loop sets,\na bound of the next loop, a loop that is counted for one state or call and\ngets may_goto for a different one ([P], [F]). They must be rejected.\n\nverifier_budget.c is serial, like timed_may_goto: its progs spin for 250 ms\nin an RCU read-side critical section, one after the other. It takes 5 sec.\nverifier_callx.c gets a test of packet pointers after callx of an argument.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-44-alexei.starovoitov@gmail.com\n" }, { "commit": "d0a8c63bfc66b62e53918ce00192d09b1251335f", "tree": "bb6b1d379c568b2f692d6e4d97b3d58252872276", "parents": [ "489b946f5f6a09d2d6f81584881a4cface95019e" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:50 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "selftests/bpf: Test loops that are counted, walked or widened\n\nThe verifier has three methods for a loop:\n - Counted: scalar evolution gives the number of iterations and a range for\n each register that has a closed form. The loop gets no may_goto.\n - Walked: iteration by iteration, with the real values.\n - Widened: what returns to the head is joined with the state that it comes\n from. A bound that grows moves to a fixed stop, until nothing changes.\nThe wrong method rejects a valid prog or costs thousands of insns. A wrong\nstate at the head loads an unsafe prog.\n\n [W] \"bpf: Add union and widening of the range of a register\"\n [J] \"bpf: Add join of registers and stack slots\"\n [A] \"bpf: Find the registers and stack slots that later checks depend on\"\n [E] \"bpf: Merge the state that arrives into the set at an insn\"\n [M] \"bpf: Move states along edges, into loops and subprogs and out of\n them\"\n [L] \"bpf: Enter and leave loops in the main pass, build flow.c\"\n [C] \"bpf: Keep the count of a loop when a register has no closed form\"\n [G] \"bpf: Tell the passes over the graph where an added may_goto goes\"\n [1] \"bpf: Keep the first iteration of a counted loop apart\"\n [R] \"bpf: What a call returns in each iteration is like what the loop\n loads\"\n [T] \"bpf: Find where the jumps of a loop stop a number\"\n [B] \"bpf: A loop is one iteration shorter behind the jump that counts it\"\n [P] \"bpf: Give the places of a back edge to the jumps that count\"\n [Y] \"bpf: Count a loop whose exit tests a copy of the counter\"\n\n verifier_.. the loop the verifier must\n ----------------- --------------------------- -------------------------\n loop_need.c is counted, \u0027x \u003d x * 3 + 1\u0027 [C] walk it if a jump, an\n has no closed form access or a call ahead\n depends on x ([A]), else\n widen x\n is too long for a walk, [1] verify the first\n \u0027idx \u003d table[idx]\u0027, iteration on its own\n \u0027x \u003d rnd() \u0026 15\u0027 [R] the same\n loop_as_is.c is not counted [M] join the state that\n ends a walk with a state\n of this walk only\n or bpf_loop(): two states [E] join what comes back\n get there, with 0 and 8 with the state that it\n comes from\n \u0027if (..) n--\u0027, from 3 [W] stop n at 0\n \u0027sum +\u003d x\u0027, no jump depends [J] forget sum at once:\n on sum, in 64 and 32 bits two passes\n a jump compares sum with [J] stop sum at S32_MAX\n a register\n \u0027if (sum \u003d\u003d 77)\u0027 [W] not try S64_MAX after\n U32_MAX\n the largest of numbers [W] keep the lower bound\n \u0027off -\u003d 4\u0027 until off is -4 [W] keep the step of 4\n \u0027if (n \u003c 8) a[n++] \u003d j\u0027, [T] stop n at 8, off at\n \u0027off +\u003d l\u0027 below 8000 7999\n is counted, too long for [C] stop n at 8, add no\n a walk, \u0027if (n \u003c 8) n++\u0027 may_goto\n loop_walk.c has two entries (bpfjailer) [L] walk it to its end\n each iteration decides [L] go on with the walk\n a jump that leaves the loop\n \u0027while (rnd()) n++\u0027 [L] give up at once\n has two iterations, a flag [L] walk both\n for a counter, and a call\n only a flag that went both [L] give up\n ways decides its jump\n 32 states enter, each needs [L] count the insns of\n a walk of 300 insns each walk, not of all\n is too long for a walk [L] not try it again\n loop_latch.c ends when a flag is false: [G] count it by the jump\n \u0027more \u003d ++i \u003c N \u0026\u0026 cond\u0027, that clears the flag\n 20 insns, a jump or calls\n in front of \u0027while (more)\u0027\n the same with 40 jumps, an [G] count it\n error code or a size\n from that jump a path leads [G] not count it\n to another back edge, or\n into a nested loop\n the flag is a constant only [G] not count it\n without an added may_goto\n a load changes the flag, [G] not count it\n 101 of 64 - 127 goes on\n a store behind the jump [B] one iteration less\n that counts for the pointer\n that jump leaves by way of [B] not shorten the range\n a flag, or on both edges\n five statuses of calls are [P] count it, by way of\n nearer to the back edge a flag too\n \u0027while (buf[i++] \u0026\u0026 i \u003c N)\u0027 [Y] count it if the two\n tests a copy of i are equal at the entry\n value_ptr_arith.c \u0027p \u003d \u0026v[p-\u003enext]\u0027 [J] keep [0, 31] next to\n 0: it covers the rest\n \u0027p +\u003d 1\u0027 [J] reject\n scev.c takes a reference in each [L] reject, or load\n iteration, or in one\n iterating_ bpf_loop() is the head of [L] verify the callback\n callbacks.c a walked loop in the last iteration too\n\nIn most tests the number is an index after the loop, where no jump limits\nit: its range at the head decides.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-43-alexei.starovoitov@gmail.com\n" }, { "commit": "489b946f5f6a09d2d6f81584881a4cface95019e", "tree": "f33f0710dcc4b9ef704eb47899f2315d5ae6ab1e", "parents": [ "8292b648ae995b59b9daf51c68aa14f62da25050" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:49 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "selftests/bpf: Test static subprogs that are verified on their own\n\nThe verifier followed each call into the subprog, with the frames of the\ncallers in the state. Now it verifies most static subprogs for the states\nat their first insn, without these frames. A call waits, and each exit\nstate goes to all calls that wait for this entry state. What can go wrong:\na call does not get a result that is its own, or the subprog changes what\na caller holds and the caller does not see it.\n\n [E] \"bpf: Add the sets of states at an insn and the entries of functions\"\n [M] \"bpf: Move states along edges, into loops and subprogs and out of\n them\"\n [B] \"bpf: Make the state after a call from the caller\u0027s state and an\n exit state\"\n [O] \"bpf: Verify static subprogs on their own\"\n\n verifier_.. the case pins\n ------------------ ---------------------------------------------- ----\n calls_in_a_row.c 20 calls pass kind 3, one call passes kind 1: [E]\n the 20 entry states are joined, the one stays\n \u0027x \u003d inc(x); x \u003d inc(x);\u0027 loads and returns 2 [M]\n 3 entry states meet in the subprog in 2 steps: [E]\n the exit state is for all 3 calls, if they [B]\n wait together or come one after the other\n The argument is r6 + 10, linked to r6 of the [O]\n caller: the 10 is not for the subprog\u0027s links\n subprog_callers.c The subprog gives up the lock or the RCU [O]\n section of its caller and takes it again.\n 3 calls wait when the verifier finds it out.\n It is called, and it is a timer callback too. [O]\n Recursive subprogs change packet data or [O]\n a tree in the callback of bpf_rbtree_add().\n Ids at the return: an inner map from each of [B]\n 2 calls, a reference 2 calls down, too many ids.\n Two calls pass packet pointers whose offsets [O]\n have different ranges.\n The subprog loads data_end itself and checks [O]\n the packet pointer of its caller.\n struct_ops_ The subprog reads an argument with __ref from [O]\n refcounted_subprog ctx while the prog holds the reference.\n stack_arg.c The stack arguments that a subprog got are not [O]\n the ones that it passes on. A subprog does the\n NULL check of a stack argument for its caller.\n A stack argument is linked in the same way. [O]\n\n15 of the 25 progs are unsafe and must be rejected: only one call gets\na number that is out of bounds, only the code after one call uses what the\nsubprog took away.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-42-alexei.starovoitov@gmail.com\n" }, { "commit": "8292b648ae995b59b9daf51c68aa14f62da25050", "tree": "f0efd049cac50f206977be622f238acfe2a776ae", "parents": [ "dd43eeaf99eb2e021d2321709f831eb7602ea435" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:48 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "selftests/bpf: Test states that are not joined\n\n ret \u003d lookup(\u0026p); /* ret \u003d -ENOENT and p is not set, or */\n if (ret \u003c 0) /* ret \u003d 0 and p is set */\n goto drop;\n use(p);\n\nWhen the compiler inlines lookup(), the two states meet in front of the\njump. A verifier that follows paths keeps them apart and loads the prog.\nTheir join, ret \u003d [-2, 0], gets to use(p) without p. Thus the verifier does\nnot join states when a check ahead can depend on the difference. Each test\nhas one such difference, in the form that a real prog has.\n\n [J] \"bpf: Add join of registers and stack slots\"\n [K] \"bpf: Find the registers that hold a number or a pointer to arena\"\n [A] \"bpf: Find the registers and stack slots that later checks depend on\"\n [N] \"bpf: Decide which states are not joined\"\n [M] \"bpf: Merge the state that arrives into the set at an insn\"\n [F] \"bpf: Verify programs as a fixpoint over the control flow graph\"\n\n verifier_.. the two states differ in as in\n -------------- ----------------------------------------- --------------\n jumps_ahead.c [N] a number that a jump ahead tests, the Cilium,\n ranges have a gap: -155 and 0 profiler,\n [N] two such numbers that go together test_seg6_loop\n [N] a register that only one state sets\n [N] 0 or not 0, in one of two slots xdp_synproxy\n [N] a flag, 0 and 1, that a jump in this\n block or the next one tests\n [M] a register that only a loop sets\n ptr_off.c [A] a constant that is added to a pointer\n [J] how much of the packet is checked\n [K] the offset of one of two fields behind\n bpf_core_cast(), bpf_cast_to_kern_ctx()\n [K] 20 or 40 bytes of a packet whose test_cls_\n context was in a struct redirect\n var_off.c [A] a constant offset in the stack\n mem_size_reg.c [A] a size that a helper or a kfunc must\n know\n\nStates that stay multiply. The verifier must join what no check can tell\napart: -134 and -135 ([N]), NULL or not in an array that a loop reads\n(bpfjailer), an offset in a map value that has only numbers ([K]). 20 flags\nand 12 offsets give 2^20 and 2^12 states: the rules apply only while less\nthan half of each limit on states is used ([N]). 4 calls that each return\none of 33 numbers give 33^4: bpf_flow_exit() widens an exit state that was\njoined 16 times.\n\n[F]: maybe_fork_scalars() makes -1 and 0 of [-1, 0]. The state with 0 must\nnot go back to an insn where [-1, 0] covers it (verifier_bounds.c). 1 and 2\nare joined at exit: a prog that can return 2 must not attach to ingress\n(cgroup_skb_egress_ret.c).\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-41-alexei.starovoitov@gmail.com\n" }, { "commit": "dd43eeaf99eb2e021d2321709f831eb7602ea435", "tree": "9853b39303e6cdefcccaeb016b97d8ce10b38597", "parents": [ "7e363442447f6469152062fec257ac260633237c" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:47 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "selftests/bpf: Adjust tests to new verdicts, messages and order\n\nWithout this patch 143 subtests of test_progs and 3 tests of test_verifier\nfail. No prog that loaded is rejected. 25 progs that were rejected load.\n\n [F] \"bpf: Verify programs as a fixpoint over the control flow graph\"\n [O] \"bpf: Verify static subprogs on their own\"\n [R] \"bpf: Allow recursive subprogs\"\n\n before now\n ------------------------------ -----------------------------------------\n \"infinite loop detected\", [F] 19 progs load, most run and return 0:\n \"too large\", \"8193 jumps\" 8 iter_remake_*, loop3.bpf.o, .. One\n state covers all iterations, and may_goto\n stops the loop.\n the same, the loop has no exit [F] \"loop at insn N never exits\": 6 progs\n \"recursive call from\", [R] 6 progs load: callx_*_recursion,\n \"frames is too deep\" bounded_recursion, .. It needs the JIT:\n __arch_x86_64, __arch_arm64.\n \"header_count is [0..3]\", then [F] \"[0..5]\": two bounds are joined in\n \"[0..5]\" front of a counted loop.\n the fall-through is verified flow_compute_order(): the target of\n first a jump is. Swap the branches, or expect\n the other one of two errors.\n \"0: R1\u003dctx() R10\u003dfp0\" [F] \"0: R10\u003dfp0\": only what is live\n scc column, \"depth\u003d\", gone, \"(limit 0)\": the patches that\n \"(limit 1000000)\" remove the old pass\n r1 is an argument [O] only if the callee reads it\n\nThe last row: the callees in verifier_live_stack.c and _liveness_exp.c read\nthe pointer that they get. unsafe_on_2nd_iter also wrote 8 bytes to\n\u0027char buf[4]\u0027, and the verifier finds that error first: the buffer gets\n8 bytes. bpf_loop_iter_limit_nested compares two sums with their maximum:\nthe verifier knows their range, not the set of their values.\n\nNew tests of [R] stand next to the old tests of the same limits. What it\nrejects: test_global_func3.c, verifier_tailcall.c,\n\"calls: a timer callback calls the main prog\", \"arena stack: the kernel\nframe of a recursion counts in the depth of the stack\". What runs:\n\"arena stack: recursion ends in the stack\", and\ncallx_no_recursion_after_all, which gets no check at run time.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-40-alexei.starovoitov@gmail.com\n" }, { "commit": "7e363442447f6469152062fec257ac260633237c", "tree": "0042268364e2eb90184a7f12abe6b023b5625d3c", "parents": [ "4a3a9c2d6896f96c5de37d48844342a41a1c22b4" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:46 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "selftests/bpf: Adjust tests to log lines that are gone\n\nWithout this patch 114 subtests of test_progs and 4 tests of test_verifier\nfail. Their progs get the old verdict, but the tests match lines of the\nverifier log that the kernel does not print any more. Keep the progs. Match\nthe line of the new log that shows the same fact.\n\n [P] \"bpf: Remove precision tracking\"\n [V] \"bpf: Remove is_state_visited(), bpf_compute_scc() and iter.depth\"\n [F] \"bpf: Verify programs as a fixpoint over the control flow graph\"\n\n the tests matched they match now\n ----------------------- ------------------------------------------------\n [P] \"mark_precise: ..\", The value of the scalar where the prog uses it:\n 462 lines \"R2\u003d-8\".\n [V] \"N: safe\", 23 lines \"from M to N: within\". If no state covers the\n other one: \"joined\", and the join.\n [F] \"id\u003d1\" of a scalar, No id: the verifier clears an id that only one\n 12 lines live register has.\n\nThe first row is verifier_precision.c, _subprog_precision.c, _spill_fill.c,\n_scalar_ids.c, stack_arg_precision.c and verifier/precise.c. The second row\nis verifier_bounds_step.c, _search_pruning.c, _live_stack.c: the tests of\nregsafe(), stacksafe() and range_within(). The target of a jump is verified\nbefore the fall-through. Thus the tests in which the first of two states\nmust cover the second one swap their branches.\n\nThree verdicts change. short_loop1 was \"too large\". Now one state at the\nloop head covers all iterations, and it loads. 2 unprivileged progs of\nverifier_value_ptr_arith.c load: r1 \u003d [0, 3] and r1 \u003d [0, 7] are joined in\nfront of \u0027r1 +\u003d r0\u0027, and the insn gets one limit for its mask. 8 progs are\nrejected as before, with a different message. BPF_F_TEST_STATE_FREQ has no\neffect. Remove it from the tests that change.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-39-alexei.starovoitov@gmail.com\n" }, { "commit": "4a3a9c2d6896f96c5de37d48844342a41a1c22b4", "tree": "ac254cda3faa94634f216290ad614f1a2a0236b2", "parents": [ "50ea1f0797de0138169208ef7ab0bb9ab0e75c8c" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:45 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "bpf: 32-bit add to a pointer and pointer op pointer make a number\n\nxdp_synproxy_kern.c:\n\n /* Without volatile the verifier throws this error:\n * R9 32-bit pointer arithmetic prohibited\n */\n volatile u64 old_len \u003d data_end - data;\n\n if (bpf_skb_change_tail(ctx, old_len + TCP_MAXLEN - hdr-\u003etcp_len, 0))\n\ntest_tcp_custom_syncookie.c has the same comment. The argument is a u32,\nso the compiler adds in 32 bits and in the order that it likes,\ndata_end - (data + tcp_len) + 60:\n\n 151: w9 +\u003d w6 ; R9\u003dpkt()\n 152: w8 -\u003d w9 ; R8\u003dpkt_end()\n 153: w8 +\u003d 60\n\nexhandler_kern.c had \u0027if (!work \u0026\u0026 !func)\u0027 with two pointers, which is\n\u0027r2 |\u003d r1\u0027: \u0027R2 pointer |\u003d pointer prohibited\u0027. Commit 44df171a10f8\n(\"selftests/bpf: Workaround a verifier issue for test exhandler\") wrote\nit in another way. The C code wants a number in both cases.\n\nCommit 72c0681c0e75 (\"bpf: Allow bitwise ops, shifts and mul/div on\npointers with CAP_PERFMON\") made a number of the result of every op on\na pointer and a number but +\u003d and -\u003d. 32-bit -\u003d and pointer -\u003d pointer\nhave always made one. That leaves 32-bit +\u003d and the other ops on two\npointers. Do the same for them: the result is an unknown number. The\nprog is rejected where it uses the number as a pointer:\n\n w0 +\u003d 0 ; R0\u003dmap_value -\u003e scalar\n *(u64 *)(r0 + 0) \u003d r1 ; R0 invalid mem access \u0027scalar\u0027\n\n64-bit +\u003d and -\u003d of a pointer and a number keep the pointer, as before.\nNothing changes without CAP_PERFMON.\n\nThree tests go through the result of such an op: they are rejected by\nthe next insn. \u0027unpriv: add pointer to pointer\u0027 and\nverifier_scev/ptr_map_value_alu32_latch do nothing with it: they load.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-38-alexei.starovoitov@gmail.com\n" }, { "commit": "50ea1f0797de0138169208ef7ab0bb9ab0e75c8c", "tree": "55609ffe6bbc1dd6db91ffc7e11afad6adafbc9c", "parents": [ "1dcc217fefba82046e1060a28146a457db867205" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:44 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "bpf: A part of a pointer that is spilled is a number\n\nxdp-\u003edata is a u32 in C and a pointer to the packet for the verifier.\ntest_dynptr_copy_xdp_overlap() of dynptr_success.c makes a length of it:\n\n void *data_end \u003d (void *)(long)xdp-\u003edata_end;\n void *data \u003d (void *)(long)xdp-\u003edata;\n __u32 off \u003d data_end - data - 1000;\n\n if (fill_xdp(\u0026ptr, off, 1300)) ...\n err \u003d bpf_dynptr_copy(\u0026ptr, off + 100, \u0026ptr, off, 1200);\n if (check_xdp(\u0026ptr, off + 100, 1200, off)) ...\n\nfill_xdp() and check_xdp() are inlined loops. With plain\n\u0027for (i \u003d 0; i \u003c n; i++)\u0027 in place of their bpf_for() no register is left\nfor off. The compiler keeps the u32 that it loaded on the stack and\nsubtracts once more behind the first loop:\n\n 0: r7 \u003d *(u32 *)(r1 +0) ; R7\u003dpkt(r\u003d0)\n 8: *(u32 *)(r10 -48) \u003d r7\n invalid size of register spill\n\nNo loop is looked at. The three test_dynptr_copy_xdp_overlap*() progs are\nrejected like that, with clang 18 and with today\u0027s clang.\n\nWith CAP_PERFMON the prog may see the value of a pointer. It can store\n4 bytes of it into a map value, or shift it, and has a number. The stack\nis the only place that refuses. Treat the store like a store of any\nother data: the bytes are STACK_MISC, what was spilled in the slot is\ngone. Whatever is filled from the slot is a number, also when it has the\nvalue of the pointer:\n\n *(u32 *)(r10 - 8) \u003d r1\n r1 \u003e\u003e\u003d 32\n *(u32 *)(r10 - 4) \u003d r1\n r0 \u003d *(u64 *)(r10 - 8)\n r0 \u003d *(u32 *)(r0 + 0) ; R0 invalid mem access \u0027scalar\u0027\n\nNothing changes without CAP_PERFMON.\n\ndynptr/slice_buf_narrow_spill stores 4 bytes of a slice into the buffer\nof the slice. It is rejected by the next insn, which reads through the\nslice. Update the expected message.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-37-alexei.starovoitov@gmail.com\n" }, { "commit": "1dcc217fefba82046e1060a28146a457db867205", "tree": "8b328c57369f46c0f047e51ef4979bf5ee70f88d", "parents": [ "ab5fa7281144eba84e38f4a2978514afe8bbb353" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:43 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "bpf: Allow tail calls and LD_ABS in subprogs that return void\n\n static __noinline int subprog_tail(struct __sk_buff *skb)\n {\n bpf_tail_call_static(skb, \u0026jmp_table, 0);\n return 0;\n }\n\nLLVM 23 writes the signature that a function has after optimization\ninto BTF. The callers know the constant, nobody reads r0, the function\nreturns \u0027void\u0027 there, and the prog is rejected before the first insn is\nlooked at:\n\n tail_call is only allowed in functions that return \u0027int\u0027.\n\nCommit be1d838b88e4 (\"selftests/bpf: Keep int return type for tailcall\nsubprogs\") hides the constant from the compiler with barrier_var() and\n__sink(). Without them 6 progs of tailcall_bpf2bpf2.c,\ntailcall_bpf2bpf_hierarchy[123].c, tailcall_callback.c and\ntracing_stack_arg_tailcall_tgt.c are rejected. Everybody else who has\na tail call in a subprog has to find the same trick.\n\nThe rule is from commit 09b28d76eac4 (\"bpf: Add abnormal return\nchecks.\"). A tail call that is taken and LD_ABS that fails return to\nthe caller with a number in r0. The verifier did not look at that\nreturn, so the type of the function had to promise a number.\nNow it does look: check_helper_call() goes back to the caller with an\nunknown r0, check_ld_abs() with 0, and r0 is not set behind the call of\na global function that returns void. A caller that reads r0 is checked\nwith what is there:\n\n call void_subprog_tail_call ; r0 \u003d 1 if the tail call is not taken\n if r0 \u003d\u003d 1 goto +1\n r0 \u003d r9 ; R9 !read_ok\n\nSo let \u0027void\u0027 through. A function that returns a pointer or a struct is\nrefused as before.\n\nTwo tests of verifier_ld_ind pin the rule for void. They load now.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-36-alexei.starovoitov@gmail.com\n" }, { "commit": "ab5fa7281144eba84e38f4a2978514afe8bbb353", "tree": "ff2ab5e789c23c760ec452ea67d0b5cc1311e398", "parents": [ "95ff2abedf64159d1b92bd1bd05bdf2eb024c0c5" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:42 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "bpf: Count a loop whose exit tests a copy of the counter\n\n\tu32 i \u003d 0;\n\twhile (buf[i++] \u0026\u0026 i \u003c 1023)\n\t\t;\n\treturn buf[i];\n\nclang keeps what i was before the increment in a second register. The\njump and the load use that one:\n\n\tl: r1 +\u003d 1\n\t if r2 \u003e 1021 goto out\n\t r2 +\u003d r0\n\t w3 \u003d *(u8 *)(r2 + 0)\n\t r2 \u003d r1\n\t if w3 !\u003d 0 goto l\n\tout: r0 +\u003d r1\n\nScalar evolution has (linear r1 1) for r1 and nothing for r2, which is\nmade from another register: the loop has no count. No jump tests r1, so\nwidening has no stop for it:\n math between map_value pointer and register with unbounded min value\n\nAn iteration leaves the same number in r1 and r2. If they are equal when\nthe loop is entered as well, one constant or one id, r2 is a copy of r1\nat the header in every iteration, and what is known about r1 is known\nabout r2: (copy r2 (linear r1 1)). The jump counts the loop, 1023\niterations, and both registers get their range from the count. They also\nget one id, like after \u0027r2 \u003d r1\u0027: what the jump says about r2 bounds r1.\n\nThat is true at the header. Behind the jump that counts, where ranges are\none iteration shorter, r1 has moved on: r2 gets its range, and no id. A\nregister that took the value of r2 on the way, \u0027r4 \u003d r2\u0027, gets nothing:\nwhat r4 was when the loop was entered has nothing to do with it.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-35-alexei.starovoitov@gmail.com\n" }, { "commit": "95ff2abedf64159d1b92bd1bd05bdf2eb024c0c5", "tree": "d1531561747141f6871625648cde995553fe6503", "parents": [ "a00c8eafb3816994fd63c6ffe934edc9ffa1cb58" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:41 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "bpf: Give the places of a back edge to the jumps that count\n\nA stack walker reads a few words per frame, leaves the loop when a read\nfails, and appends up to 32 words per frame:\n\n\tbpf_for(i, 0, 100) {\n\t\tif (frames \u003d\u003d 8)\n\t\t\tbreak;\n\t\tif (READ(a) || READ(b) || READ(c) || READ(d) || READ(e))\n\t\t\tbreak;\n\t\tn \u003d 32 - (a \u0026 1);\n\t\tfor (j \u003d 0; j \u003c n; j++)\n\t\t\tout[idx + j] \u003d b + c + d + e;\n\t\tidx +\u003d n;\n\t\tframes++;\n\t}\n\n\u0027R1 unbounded memory access\u0027: only \u0027frames \u003d\u003d 8\u0027 limits idx, and nothing\nlooks at that jump. A back edge has four places for the jumps that leave\nthe loop and dominate it. The nearest ones take them: the NULL test of\nbpf_iter_num_next() and three statuses. None of them counts.\n\nScalar evolution knows which jumps test a counter. Collect the jumps again\nwhen it is done and pass over the others. The latch keeps its place. The\nsearch ends at the head of the loop, as for a loop with less than four such\njumps. Every jump that is kept tells iterations in which the back edge is\nnot taken, so any choice is sound.\n\nThe loop has 9 iterations at most. idx has no closed form, so they are\nlooked at one by one: idx is 0, [31, 32], [62, 64] .. [217, 224].\npyperf.h with STACK_MAX_LEN 250 and UNROLL_COUNT 8 leaves its loops from\nthe second of 8 copies of the body: 59713 -\u003e 2877 insns.\n\nA jump can leave the loop by way of a flag. These jumps are known before\nscalar evolution starts, so mark_latches() asks for the SCEV of each.\n do { ..; more \u003d ++i \u003c 256 \u0026\u0026 v-\u003ein[i \u0026 63];\n if (READ(a) || READ(b) || READ(c)) break; } while (more);\nThe four places went to jumps that are nearer to the back edge:\n\"R1 unbounded memory access\", 12562 insns on bpf-next. Now 63.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-34-alexei.starovoitov@gmail.com\n" }, { "commit": "a00c8eafb3816994fd63c6ffe934edc9ffa1cb58", "tree": "4c5e3bf4f11af4efe07c2ea8809677b8ec691120", "parents": [ "e2b83f4db687914822654cbe3d17171ba30dfac9" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:40 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "bpf: A loop is one iteration shorter behind the jump that counts it\n\n\t#pragma clang loop unroll_count(3)\n\tfor (i \u003d 0; i \u003c 250; i++) {\n\t\tif (!bpf_get_prandom_u32())\n\t\t\tbreak;\n\t\tout[i] \u003d bpf_get_prandom_u32();\n\t}\n\nis rejected with\n\u0027invalid access to map value, value_size\u003d1000 off\u003d1000 size\u003d4\u0027.\n250 is 83 * 3 + 1. The compiler makes a loop of three copies of the body\nand leaves it behind the first copy in iteration 84:\n\n\tl: ...; *(u32 *)(r6 - 4) \u003d w0;\n\t if r7 \u003d\u003d 251 goto out;\n\t ...; *(u32 *)(r6 + 0) \u003d w0;\n\t ...; *(u32 *)(r6 + 4) \u003d w0;\n\t r6 +\u003d 12; r7 +\u003d 3; goto l;\n\nThe loop is counted. At its head r6 gets the offsets of all 84 iterations:\n4 to 1000. The jump narrows r7, which it tests. It says nothing about r6:\nthe two stores behind it are checked with an offset that they never see.\n\nA state that goes on in the loop behind the jump that counts is not in the\nlast iteration. Give the range of one iteration less to what is linear at\nthe jump: r6 is 4 to 988. Only for a jump that leaves the loop itself. An\nedge that leaves by way of a flag stays in the loop for a while, with the\nlast iteration: no shorter range behind a jump that has such an edge.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-33-alexei.starovoitov@gmail.com\n" }, { "commit": "e2b83f4db687914822654cbe3d17171ba30dfac9", "tree": "41b9a6c9de599fcc9001861653f068b140454d5c", "parents": [ "89557ca1fc86916b426f1c1fcfe0178ca5e2ee99" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:39 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "bpf: Find where the jumps of a loop stop a number\n\n bpf_for(i, 0, 100)\n bpf_for(j, 0, 100)\n if (n \u003c 8)\n v-\u003ea[n++] \u003d j;\n return v-\u003ea[n];\n\n while (off \u003c 8000) { l \u003d v-\u003ebig[off]; if (!l) break; off +\u003d l; }\n\nn and off grow by what the data say, so there is no formula for them.\nWidening moves the bound that grows to a fixed stop: 0, S32_MAX, U32_MAX or\nS64_MAX. n is [0, S32_MAX] at the loop head. The jump limits it in the\nloop, nothing limits it after the loop. clang tests off at the end of the\nloop, so nothing limits it at the load. Both loaded before states were\njoined:\n\n R6 unbounded memory access, make sure to bounds check any such access\n\nThe jumps of the loop tell where the bound stops. Examine one iteration\nbefore the main pass, from the head to the back edges, and write what is in\na register or a stack slot as \u0027root + constant\u0027. A root is the value at the\nhead, or a value that the iteration makes. A jump that compares \u0027root + c\u0027\nwith a constant limits the root on each edge that stays in the loop. What\nreturns to the head is \u0027root + c\u0027 again, and the limits give a stop: 8 and\n7999 here. bpf_reg_widen_range() takes the nearest of all stops.\n\nA stop is a guess. What returns to the head next is compared with the\nwidened state as always. A wrong stop costs one more pass through the loop.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-32-alexei.starovoitov@gmail.com\n" }, { "commit": "89557ca1fc86916b426f1c1fcfe0178ca5e2ee99", "tree": "cf5a18439003ef13de0d5104e2d78794b8ff9833", "parents": [ "df9b13a441c9bc33e79f9dab0ff404b362fbc2a1" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:38 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "bpf: What a call returns in each iteration is like what the loop loads\n\n for (i \u003d 0; i \u003c 20000; i++) {\n sum +\u003d a[x];\n x \u003d bpf_get_prandom_u32() \u0026 15;\n }\n\nx is loop-carried: an iteration uses what the iteration before made. The\nloop is counted, and too long to go through its iterations one by one.\nScalar evolution knows nothing about r0 after a call, so x is widened at\nthe loop head. The prog loaded before states were joined:\n\n R0 unbounded memory access, make sure to bounds check any such access\n\nA value that the loop loads from memory in each iteration is handled: the\nfirst iteration is verified on its own, and tells what the value is in the\nothers. What a call returns is made anew in each iteration in the same way.\n\nGive r0 after a call the expression that a load gets, with a parameter that\ntells the two apart. A call can return NULL in one iteration and set a flag\nwith it, so a loop that is short enough is still walked first.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-31-alexei.starovoitov@gmail.com\n" }, { "commit": "df9b13a441c9bc33e79f9dab0ff404b362fbc2a1", "tree": "45ad4ffeea79f260af5d7d6801c6fd0bbae02eab", "parents": [ "6d4131627eae0d22e53961b3866df5b37b61a602" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:37 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:54 2026 +0000" }, "message": "bpf: Keep the first iteration of a counted loop apart\n\n idx \u003d 0;\n for (i \u003d 0; i \u003c 100000; i++)\n idx \u003d table[idx]; /* u8 table[256] */\n\nScalar evolution has the count and no formula for idx. If something looks\nat such a register, like the load here, the verifier goes through the\niterations one by one. 100000 iterations are too many for that. Then what\nreturns to the loop head is joined with the 0 and widened: the bound that\ngrew goes to a fixed stop, and a prog that loaded before is rejected:\n\n R0 unbounded memory access, make sure to bounds check any such access\n\nBut nothing that idx is made from is what a register had at the loop head.\nIt is a byte in each iteration. Only the first one differs: it has the 0\nfrom the entry.\n\nVerify the first iteration with the state that enters the loop. The state\nthat returns to the loop head has idx in [0, 255]. Give its induction\nvariables the ranges that follow from the count, as at the entry. It stands\nfor all other iterations. What returns next must be within it, otherwise\nthe two are joined like at each loop head. The loop takes 12 insns.\n\nexpr_is_fresh() finds the registers, bpf_loop_iters.fresh_regs has them,\nloop_stack_entry.first marks a state that is in the first iteration.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-30-alexei.starovoitov@gmail.com\n" }, { "commit": "6d4131627eae0d22e53961b3866df5b37b61a602", "tree": "a1eb987bd5652b945d928c89a62c3136bd4e0d89", "parents": [ "edcafaec625627c9358506828bcf33e31195cc0c" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:36 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:53 2026 +0000" }, "message": "bpf: Callx reads what the subprogs whose address is taken read\n\ncore::fmt::write() is in each Rust prog that prints. It reads the options\nof a \u0027{}\u0027 and calls the fmt() function of the argument through a pointer:\n\n if n \u0026 8 !\u003d 0 { arg_index \u003d ...(template.cast_array().read()); }\n if n \u0026 16 !\u003d 0 { opt.width \u003d args.add(opt.width)...as_u16(); }\n if n \u0026 32 !\u003d 0 { opt.precision \u003d args.add(opt.precision)...as_u16(); }\n args.add(arg_index).as_ref().fmt(\u0026mut Formatter::new(output, opt))?;\n\nThe last line is callx with two arguments, r1 and r2. The pass that finds\nthe live registers does not know the callee: callx counts as a read of\nr1-r5. What the branches leave in r4 and r5 stays live:\n\n w4 \u0026\u003d 16\n if w4 \u003d\u003d 0 goto +4 ; r4 \u003d 0\n r3 \u003c\u003c\u003d 4\n r4 \u003d *(u64 *)(r10 - 24) ; r4 \u003d args, a pointer to arena\n ...\n callx r3\n\nr4 is 0 or a pointer, r5 is a byte or a pointer. A number and a pointer\nhave no join: 4 states go to callx in the first pass over the loop, 2 in\neach later pass, where 1 is enough. A subprog with callx in it also seems\nto take 5 arguments: what its callers leave in r3-r5 is a part of its entry\nstate, and it is verified again for each such leftover.\n\ncallx calls only a static subprog whose address the prog takes: with\nld_imm64, or in a table in a read-only map. mark_recursive_subprogs() has\nthis set. Store it in addr_taken of bpf_subprog_info. The passes in flow.c\nthat look through callx ahead of the main pass read the bit already.\nNothing set it so far: they took no subprog for a target of callx.\n\n insn the registers of r1-r5 that it reads\n -------------------------- ---------------------------------------------\n call of a static subprog f live at the first insn of f, as before\n callx, before all\n callx, this patch live at the first insn of a subprog that has\n addr_taken, or declared in its BTF\n\nbpf_compute_live_registers() finds both in one loop, until nothing changes.\nzext_dst comes from the same result, thus check_func_callx_one() reports\na verifier bug if the callee has no addr_taken.\n\nbpfland_stopping of scx_bpfland.rs: -13 % insns, -19 % states. 99 of the\n225 progs of the schedulers of rust-bpf change: -5 % insns, -9 % states.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-29-alexei.starovoitov@gmail.com\n" }, { "commit": "edcafaec625627c9358506828bcf33e31195cc0c", "tree": "c7a4e1e42f8b0b83654073724fb872a47719d808", "parents": [ "b7bf79dd6f1e6bdc35c13be5baf88aaa38477372" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:35 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:53 2026 +0000" }, "message": "bpf: Track a pointer to one of a set of functions\n\nEach \u0027{}\u0027 of a format string in Rust ends in core::fmt::write(), which\ncalls the fmt() function of the argument through a pointer:\n\n ArgumentType::Placeholder { formatter, value, .. } \u003d\u003e formatter(value, f)\n\nrust-bpf compiles it to a load from the table of all fmt() functions of the\nobject, and callx. k2_text.o of its corpus, with serde_json, uuid, semver,\nryu and regex-automata, has 245. At the load the verifier goes on with one\nfunction and makes a state for each of the other 244. 3 states get to the\nload: 732 states that differ only in r3 meet at the next insn. The limit is\n1024. Each more type with Display or Debug adds 3 states, and 100 more\ntypes give \"more than 1024 states that cannot be joined at insn N\".\n\n if r2 \u003c 244 goto +1\n r2 \u003d 244\n r2 \u003c\u003c\u003d 3\n r2 +\u003d r3 ; the table, in a read-only map\n r3 \u003d *(u64 *)(r2 + 8)\n ...\n callx r3\n\nDo not split the state at the load. r3 is a pointer to one of a set of\nfunctions until an insn must know the function.\n\n r3 \u003d *(u64 *)(r2 + 8) r3 \u003d *(u64 *)(r2 + 8)\n / | \\ |\n r3\u003df1 r3\u003df2 ... r3\u003dfN r3 \u003d one of f1 .. fN\n | | | |\n callx r3 callx r3 callx r3 callx r3\n | | | / | \\\n f1 f2 fN f1 f2 ... fN\n\nThe register holds the number of the set, and equal sets have the same\nnumber. Thus the code that compares and joins registers does not change.\nThe log shows R3\u003dfunc(one_of\u003d245).\n\ncallx verifies each function of the set, as before. For a function that is\nverified on its own, a copy of the state of the caller waits for its exit\nstates. The copy is not a state at an insn. Other functions, and a helper\nor a kfunc that gets the pointer as a callback, get one state for each\nfunction. uuid_semver of k2_text.o: 732 -\u003e 257 states at an insn and\n-19 % insns.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-28-alexei.starovoitov@gmail.com\n" }, { "commit": "b7bf79dd6f1e6bdc35c13be5baf88aaa38477372", "tree": "e74f9b815c8f0ade30b04c09457ca5c4274c5f54", "parents": [ "8ecf70baad8b32dbe91bb5638a75c768743a294e" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:34 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:53 2026 +0000" }, "message": "bpf: Update comments about paths, pruning and explored states\n\nAbout 30 comments in verifier.c, states.c and bpf_verifier.h describe\na verifier that explores all paths of a prog and prunes a path against\nexplored states. The reader of regsafe() or stacksafe() learns from them\nthat the old state \"already passed validation\" and that the function\nreturns false \"to continue verification of this path\". Nothing of it is\ntrue since the main pass is a fixpoint over the control flow graph.\n\nSay what the code does now. States meet at the start of a basic block. The\nverifier drops a state when a state that is already there covers it: if the\nprog is fine with the old state, it is fine with the current one. Otherwise\nit joins the two states or keeps both.\n\nThe largest change is above process_iter_next_call(). 60 lines explain how\na loop with an open-coded iterator converges: exact comparison, the depth\nof the iteration, widening of scalars that are not precise. Such a loop is\na loop like any other now: what comes back to its head is joined with what\nis there until nothing changes.\n\nNo functional changes.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-27-alexei.starovoitov@gmail.com\n" }, { "commit": "8ecf70baad8b32dbe91bb5638a75c768743a294e", "tree": "f6ba58cc172f4ca274b00fde0ef71b2424f27236", "parents": [ "9f644d937dcf1bf550a6e6e27898d87c3ee87351" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:33 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:53 2026 +0000" }, "message": "bpf: Remove prune points, levels of state comparison and pop_stack()\n\nThe old main pass followed each path of a prog depth first and compared\nstates at selected insns to prune paths. flow.c goes from basic block to\nbasic block. Three more parts of the old pass have no user.\n\n removed task in the old pass what does it now\n ------------------- ------------------------- -------------------------\n prune_point, Select the insns at which States meet at the start\n jmp_point, the pass saves and of each basic block.\n force_checkpoint, compares states.\n is_iter_next\n enum exact_level Select one of three ways bpf_state_subsumes() has\n to compare states. one way, the way of\n RANGE_WITHIN.\n pop_stack() Get the next state when flow_drain() empties the\n a path ends. stack after each insn.\n\nNOT_EXACT ignored scalars without a precision mark, and the marks are gone.\nEXACT accepted only identical states, for \"infinite loop detected\", which\nis gone too. What RANGE_WITHIN did stays: the range of each live scalar of\nthe new state is within its range in the old state.\n\npush_stack() stays. The code that verifies an insn uses it to make a second\nstate, for example for the other branch of a jump. flow_drain() gives these\nstates to flow.c.\n\nWhat user space sees:\n - The statistics line shows \"processed %d insns (limit 1000000)\". The\n verifier limits the number of states, not of processed insns, and\n BPF_COMPLEXITY_LIMIT_INSNS is only the maximum length of a prog.\n veristat and other tools parse the line. Keep the format, print 0.\n - The report of a register that is not readable said\n \"R1 has never been initialized on this path\". It needs the history of\n the whole path, and the verifier has that of the current basic block.\n The report says that the register may never have been initialized, or\n that an earlier operation may have invalidated it.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-26-alexei.starovoitov@gmail.com\n" }, { "commit": "9f644d937dcf1bf550a6e6e27898d87c3ee87351", "tree": "7fdad0f6ee8169c5d4b4b0edece531eae864fc76", "parents": [ "6771f70a473328efcd57b8dc79acbb1c44b29078" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:32 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:53 2026 +0000" }, "message": "bpf: Remove precision tracking\n\nPrecision tracking is a part of pruning. The verifier followed each path\nand stopped a path when a state that it saw before at the same insn covered\nthe current state. To stop more paths, the comparison ignored a scalar\nunless a later check depended on its value. To find these scalars, the\nverifier went back from each check through the history of the path and\nmarked them as precise.\n\nThe verifier does not prune paths any more. It joins the states that meet\nat the start of a basic block, and the join covers both:\n\n r1\u003d0 and r1\u003d1 meet pruning join\n ---------------------- --------------------------- ---------------\n a check depends on r1 r1 is precise, verify r1\u003d[0,1]\n verify the two states\n no check depends on r1 drop the second state verify r1\u003d[0,1]\n\nEach later check sees the full range of r1. Thus the verifier does not have\nto find out afterwards which scalars a check depends on, and nothing reads\nthe marks.\n\nOne task of the marks is left. Some checks need a constant, for example the\nsize for bpf_ringbuf_reserve(), and the join of two constants is a range.\nflow_compute_need_const() finds the registers and stack slots that go into\nsuch checks, one time, before the main pass. States that differ in them are\nnot joined.\n\nRemove the \u0027precise\u0027 bit, backtrack.c, jmp_history, the parent link of\na state and the marks that scalar evolution asks for: 1650 lines. With the\nbit gone, __mark_reg_unknown() and bpf_mark_reg_unknown_imprecise() are one\nfunction, bpf_mark_reg_unknown(). __mark_reg_const_zero() does not need\nenv, and BPF_REGMASK_ARGS has no user.\n\nWhat user space sees:\n - The log has no \"mark_precise:\" lines and no \u0027P\u0027 in \"R0\u003dPscalar()\".\n - Nothing sets longest_mark_read_walk. veristat and other tools parse the\n statistics line, thus it continues to show \"mark_read 0\".\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-25-alexei.starovoitov@gmail.com\n" }, { "commit": "6771f70a473328efcd57b8dc79acbb1c44b29078", "tree": "9294a43ef0c047f2cbc7e708e506d38a2eb0063c", "parents": [ "eaea7390705214182957c2a51b7fbe9776433238" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:31 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:53 2026 +0000" }, "message": "bpf: Remove is_state_visited(), bpf_compute_scc() and iter.depth\n\nis_state_visited() is the pruning of a verifier that follows each path of\na prog. It saves states at selected insns and stops a path when a saved\nstate covers the current state. The main pass is in flow.c now. Each insn\nthat starts a basic block has a set of states, and a state that arrives is\ndropped, joined or added. Nothing calls is_state_visited().\n\nRemove it, and all that exists only for it: 1550 lines.\n\n removed task in the old pass what does it now\n -------------------------- ----------------------- --------------------\n explored_states, free_list Hold the saved states. The sets of states\n in flow.c.\n branches, dfs_depth, Tell when all paths No paths. The pass\n equal_state from a state are ends when no set has\n explored. a new state.\n bpf_compute_scc(), SCC Bring precision marks The marks are not\n visits, backedges over the back edges of used. loop_header\n a loop. tells the loops.\n states_maybe_looping(), Reject a path that The verifier adds\n iter.depth comes back in the same may_goto to a loop\n state. that it cannot\n bound.\n widen_imprecise_scalars(), Make a loop with an A loop that is not\n callback_unroll_depth, iterator, a callback or counted is walked,\n may_goto_depth may_goto converge. or widened at its\n head.\n bpf_split_cur_state() Save the state that flow.c keeps the\n enters a counted loop. states that enter.\n\nWhat user space sees:\n - BPF_F_TEST_STATE_FREQ told is_state_visited() to save a state each time.\n The flag is UAPI and selftests set it. The kernel accepts it as before,\n and it has no effect.\n - The \"Program dump\" of log level 2 has no scc column.\n - The log does not print \"depth\u003d\" for an iterator.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-24-alexei.starovoitov@gmail.com\n" }, { "commit": "eaea7390705214182957c2a51b7fbe9776433238", "tree": "b1f95e7d1e0d3157abb3f5bda56859cdb0c9bb90", "parents": [ "8fd58560b71e97ec625b8032e3798de0fd2b2e46" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:30 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:53 2026 +0000" }, "message": "bpf: Allow recursive subprogs\n\n candidates.sort_unstable_by(|a, b| b.0.cmp(\u0026a.0)); scx_rusty.rs\n\nquicksort() of the core library calls itself, and rusty_tick is rejected:\n\"recursive call from quicksort\u003c..\u003e() to quicksort\u003c..\u003e()\". The same for\nprogs that drop a list, a tree or an Arc of a parent, that use BTreeMap,\nserde_json or regex-automata: 100 of the 225 progs of the schedulers of\nrust-bpf and 100 of its 437 tests have a subprog that gets to itself.\nA verifier that follows each chain of calls has no choice: there is no\nlast chain.\n\n depth(n) { return n ? (depth(n - 1) + 1) \u0026 255 : 0; }\n\nThe main pass verifies a static subprog for its entry states, and a call\nwaits for the exit states. A call of a subprog that is in progress waits\nlike each other call. The first insn of a recursive subprog is like a loop\nhead: the entry states are joined with widening. So are the exit states.\n\n main prog: call depth entry state { r1\u003d5 }\n v\n +--\u003e first insn of depth() join with widening: { r1\u003d[0,5] }\n | ...\n +--- call depth(n - 1) entry state { r1\u003d[0,4] }, the call waits\n ^\n exit of depth() goes to all calls that wait\n\nHow deep the calls go and how many there are is not known. Thus each\nsubprog on a cycle of the call graph gets the checks of\n\"bpf: Limit depth and time of recursive subprogs at run time\". When a check\nfails the subprog returns 0. This is a new edge, and\ncheck_recursion_guard() verifies it.\nlinux-notes.rst says \u0027recursive calls are limited at run time\u0027 now.\n\nmark_recursive_subprogs() finds the cycles before the main pass: callx can\ncall each subprog whose address is taken, a helper calls its callback. The\nmain pass finds what callx calls. A mark that it does not confirm is\ndropped, and the subprog gets no check.\n\nStill rejected: a call of the main prog; recursion in an extension, in an\noffloaded prog, with a tail call, LD_ABS or bpf_clone_redirect(), in\na kprobe prog, or in a prog that gets a private stack without a request,\nlike raw_tp and fentry progs; an extension of a subprog that is called in\na recursion; a pointer to the stack as an argument of a call between\nrecursive subprogs. In the static limit on the stack of a chain of calls\na recursion counts as one frame, the last one.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-23-alexei.starovoitov@gmail.com\n" }, { "commit": "8fd58560b71e97ec625b8032e3798de0fd2b2e46", "tree": "4c20339945f0eae0da1823617447ac9c44d08259", "parents": [ "9b202a8c7722dd10bacfdf50dbdb146f53f55b3a" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:29 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:53 2026 +0000" }, "message": "bpf: Verify static subprogs on their own\n\nSelftest test_verif_scale1, 90 times in a row, jhash() is static noinline:\n ptr \u003d data + i;\n if (ptr + nh_off \u003e data_end)\n break;\n ctx-\u003etc_index \u003d jhash(ptr, nh_off, ctx-\u003ecb[0] + i++);\nThe verifier verifies a static subprog in the frames of its callers. States\nwith different frames have no join: each insn of jhash() has a state for\neach way to it: \"more than 1024 states that cannot be joined at insn 903\".\nIn Rust each function of core and alloc is a static subprog: 30 tests of\nrust-bpf are rejected too.\n\nVerify a static subprog for the states at its first insn. The entry state\nhas one frame, with the arguments and nothing of the callers. It arrives at\nthe first insn like each state at an insn: dropped, joined or added. The\ncall waits. Each exit state goes to all calls that wait for this entry.\n\n 2: call f --- { r1\u003dscalar } ---\u003e +---------------------+\n 7: call f --- { r1\u003dscalar } ---\u003e | f: verified 1 time |\n 3: ... \u003c-- { r0\u003d[0,7] } ----- | |\n 8: ... \u003c-- { r0\u003d[0,7] } ----- +---------------------+\n\ntest_verif_scale1: 50765 insns, today 530362.\n\nThe entry state has what a check asks the frames of the callers for: the\nreferences and locks that they hold, sleepable, rcu callback.\ninherited_id() gives what is held a name, an id that depends only on its\nposition, from 2^29: calls that differ only in ids share an entry. 27 progs\nof the schedulers of rust-bpf call core::fmt while they hold a reference.\nAll other ids stay below 2^28: \"too many ids\". A scalar argument loses its\nid and its delta. The frames of the callers stay, func_is_on_its_own(), if\n - an argument is a pointer to the stack or a dynptr: it is their memory,\n - an argument is a pointer with the id of something that is not held: the\n id of its NULL check, or of a variable offset into the packet,\n - an argument can be NULL or is the end of the packet: the subprog does\n a check for the caller. So does a subprog that loads data_end itself:\n \u0027bool has(ctx, p, n) { return p + n \u003c\u003d (void *)(long)ctx-\u003edata_end; }\u0027.\n On its own it leaves \u0027if (has(ctx, p, 14)) x \u003d p[13];\u0027 without a range,\n - it gets the context of a struct_ops prog that holds a reference: an\n argument with __ref is found by its id, not by a name. Otherwise:\n \"invalid bpf_context access off\u003d8. Reference may already be released\",\n - the subprog is a callback, changes packet data, has a tail call or\n LD_ABS, or releases what the caller holds.\nBPF_LOG_STATS adds its insns to each caller: verifier_subprog_insn_stats.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-22-alexei.starovoitov@gmail.com\n" }, { "commit": "9b202a8c7722dd10bacfdf50dbdb146f53f55b3a", "tree": "c747c11fc350484d42820d1c847d100ebaac1b0c", "parents": [ "5395aa9bbeb56900a3225c04eff6c2e0578a495c" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:28 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:53 2026 +0000" }, "message": "bpf: Keep the count of a loop when a register has no closed form\n\nSelftest pyperf600_nounroll, a profiler that reads the stack of Python:\n for (int i \u003d 0; i \u003c STACK_MAX_LEN; ++i) { /* 600 */\n if (!frame_ptr || !get_frame_data(..., \u0026frame, \u0026sym))\n break;\n ...\n event-\u003estack[i] \u003d *symbol_id;\n frame_ptr \u003d frame.f_back;\n }\ni is an induction variable: 600 iterations, i \u003d [0, 599]. get_frame_data()\nfills frame and sym, which are on the stack, in each iteration. These slots\nhave no closed form, \"can\u0027t widen *fp-64, expr is ?\", and scalar evolution\ngives no count for the full loop. Then i is not known either. The main pass\ngoes through the 600 iterations, 153987 insns, and adds a may_goto without\nneed. pyperf600, the same loop unrolled 150 times, and strobemeta are\nrejected: \"math between map_value pointer and register with unbounded ..\"\nSo are res_spin_lock_test_held_lock_max and scx_lavd/lavd_dispatch.\n\nLet the count decide what it knows about: induction variables get their\nrange from it, and the loop needs no may_goto. bpf_compute_loop_iters()\nreports the registers and slots without a closed form in forget_regs, and\nbpf_flow_loop_enter() selects a method:\n\n1. No check depends on the value, bpf_flow_is_needed(): the bytes of sym,\n a hash, a checksum. It stays what it is when the loop is entered. What\n comes back to the head is joined with it and widened, as in a loop\n without a count. pyperf600_nounroll: 1281 insns, no may_goto.\n\n2. A check depends on it. Selftest strobemeta_nounroll1:\n for (int i \u003d 0; i \u003c STROBE_MAX_STRS; ++i) /* 25 */\n payload_off \u003d read_str_var(cfg, i, .., data, payload_off);\n read_str_var() reads a string to \u0026data-\u003epayload[off] and returns off or\n off + len. payload_off is loop-carried, but the step is not a constant:\n \"(any r8 (+ r8 ?))\". Walk the loop: each iteration has its own state,\n with [0, i] in it. The count tells where the walk ends. The limit is\n 100000 insns. 17 progs of the selftests (strobemeta, profiler2,\n linked_list, xdp_synproxy) and scx_lavd/lavd_dispatch need it. A pointer\n and a slot that does not hold one full register always count as needed.\n\n3. The walk is too long: as in 1. Widening moves only the bound that grows:\n for (i \u003d 0; i \u003c 100; i++) for (j \u003d 0; j \u003c 100; j++) {\n if (*(volatile __u64 *)v \u003d\u003d 1) continue;\n if (n \u003c 8) v[n++] \u003d 0; } /* long n */\n n is [0, S32_MAX] at the head. As an unknown scalar: \"math between ..\".\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-21-alexei.starovoitov@gmail.com\n" }, { "commit": "5395aa9bbeb56900a3225c04eff6c2e0578a495c", "tree": "c2a6d4bb03b9483ed0f7e368a51ec059549a6741", "parents": [ "51bfd6314dccfa4b9ead061c80dfab51bd77aaea" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:27 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:53 2026 +0000" }, "message": "bpf: Verify programs as a fixpoint over the control flow graph\n\n for i in 0..n { v.push(i * i); }\nTest vec_push_pop of rust-bpf: \"The sequence of 8193 jumps is too complex.\"\nThe verifier follows each path from the first insn to exit, and each branch\ncan double the number of paths. 123 tests of rust-bpf hit this limit or\n1M insns. C progs are cut until they fit.\n\nDo not follow paths. Where two paths meet, make one state that covers both,\na join: r1\u003d1 and r1\u003d5 give r1\u003d[1,5]. What is safe for the join is safe for\nboth. Repeat until no state changes. The work depends on the size of the\nprog, not on the number of paths: 1761 insns with this patch, and 120 of\nthe 123 load. do_check() takes the next new state from flow.c and checks\none basic block. The check of an insn is the same.\n\nWhat user space sees:\n - The limits of 1M processed insns and 8192 jumps are gone, from\n bpf_design_QA.rst too. flow.c limits states, for a prog of N insns:\n 1024 at an insn \"more than 1024 states that cannot be joined\"\n 16 * N + 4096 at a time, 256 * N + 64K in all \"too many states\"\n - \"infinite loop detected\" is gone: 111 of the 225 progs of the schedulers\n of rust-bpf. A fixpoint shows that each iteration is safe, not that the\n loop ends:\n counted, or walked to its end nothing is added\n each iteration has may_goto or bpf_iter_*_next() nothing is added\n no exit rejected\n all other loops may_goto\n - An added may_goto is a new edge. check_loop_guard() verifies it. It goes\n to \u0027r0 \u003d 0; exit\u0027: the probe loop of hashbrown exits only with a bucket,\n and the code after the loop uses it: \"R6 invalid mem access \u0027scalar\u0027\".\n Until these insns are added the last exit stands for them. With GCC that\n can be dead code, \u0027if (debug) return ..\u0027: r0 is marked as live there.\n If the frame holds more than at its entry, or is a subprog that cannot\n unwind, may_goto goes to the exit of the loop: the prog releases there\n what it holds. From the head of a loop that is no edge of the prog. In\n glob_match() of arena_strsearch without cond_break only the body sets\n r0 for the \u0027exit\u0027 behind the loop: \"R0 !read_ok\". A subprog that holds\n nothing is left with \u0027r0 \u003d 0; exit\u0027 then. Its caller is verified with 0.\n - A walk goes on while each iteration decides a jump that leaves the loop.\n A jump that is decided only because states are kept apart by a flag does\n not count: it repeats the jump that set the flag, which went both ways.\n lexical_numbers of rust-bpf: 41610 insns, 98980 if it counts.\n - 1 and 2 are joined at exit, and a test for \u0027r0 is 2 or 3\u0027 misses [1, 2].\n Thus a cgroup_skb prog whose r0 can be 2 or 3 attaches to egress only.\n - Static subprogs and recursion are as before. Pruning, jmp_history and\n precision marks are only disabled here.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-20-alexei.starovoitov@gmail.com\n" }, { "commit": "51bfd6314dccfa4b9ead061c80dfab51bd77aaea", "tree": "ae935b7049d53ece454df24fba5cf5f2d566fe6f", "parents": [ "a784eb58f12b1a20afa3412d04faa290b79c82c3" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:26 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:53 2026 +0000" }, "message": "bpf: Tell the passes over the graph where an added may_goto goes\n\nA spin lock in Rust, test atomic_spin_lock of rust-bpf:\n\n for _ in 0..n {\n while lock.compare_exchange_weak(...).is_err() { spin_loop(); }\n data +\u003d 1; lock.store(false, Release);\n }\n\nThe compiler makes one loop with two back edges. No jump that leaves the\nloop is in each iteration. Today: \"infinite loop detected at insn 41\". The\nonly place for may_goto that each iteration passes is the head. Its target\nis an exit of all loops around it. 142 of the 225 progs of the schedulers\nof rust-bpf have such a loop. The prog has no edge from the head to the\nexit. The main pass verifies the state that goes there, but it relies on\npasses that see only the control flow graph:\n\n bpf_compute_const_regs() r7 \u003d\u003d \u0026ro on all edges to the exit, \u0026rw at the\n head. \u0027for (i \u003d 0; i \u003c *r7; i++)\u0027 behind the\n exit gets its count from ro.\n compute_subprog_args() The same with fp-8, fp-16: a store through r7.\n live registers What the loop sets on each path to the exit is\n dead at the head: a read behind it is rejected.\n\nThus call bpf_flow_place_guards() directly after the loops are known. No\nconstant is known at the target. compute_subprog_args() joins what it knows\nat the head into the target. What is live at the target is live at the\nhead, may_goto or not: r1 in compute_live_registers/may_goto.\n\n do { ..; more \u003d ++i \u003c 256 \u0026\u0026 v-\u003ein[i \u0026 63]; 10 insns; } while (more);\nclang keeps the flag: \u0027if w6 \u003e 255\u0027 sets it and stays in the loop. Today\u0027s\nbpf_edge_leaves_loop() loses it at \u0027w1 \u0026\u003d 1\u0027: no count, 15611 insns, and\n\"R7 unbounded memory access\" with one state for all iterations. Ask once,\nfor all edges: with which number in which register is the loop sure to be\nleft from this insn on? bpf_compute_leave_conds() goes against the edges:\n\n if w1 !\u003d 0 goto head w1 is 0 does not go to the head\n w1 \u0026\u003d 1 w1 is even what the insn turns into 0\n l: .. w1 is even nothing writes w1\n w1 \u003d 1 never 1 is not even\n\nAn edge leaves the loop if the constants at its jump meet the condition at\nits target: w1 is 0 at \u0027if w6 \u003e 255 goto l\u0027. 86 insns. Each insn has one\nturn. A condition is a set of numbers per register. const_fold.c tells what\nan insn makes of a number. Its constants must know the added edges.\nA nested loop is not entered: may_goto there goes where a jump of that loop\ngoes, whatever the constants say.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-19-alexei.starovoitov@gmail.com\n" }, { "commit": "a784eb58f12b1a20afa3412d04faa290b79c82c3", "tree": "7511c73b00567de473002f0c33a6173f3931b13b", "parents": [ "8875170bb1d2bd5bc36ed58d520a6e82764081a6" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:25 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:53 2026 +0000" }, "message": "bpf: Enter and leave loops in the main pass, build flow.c\n\nThe main pass joins the states that meet at an insn. At the head of a loop\nwith a join alone real progs are rejected. bpf_flow_loop_enter() has three\nmethods for a state that enters a loop, and tries them in this order:\n1. Count. scx_lavd/lavd_dispatch:\n for (int j \u003d 0; j \u003c LAVD_CPDOM_MAX_NR; j++) {\n ...\n cpdom_id \u003d get_neighbor_id(cpdomc, i, j);\nScalar evolution finds at most 128 iterations. The state gets j \u003d [0, 127]\nand covers all of them: one pass through the body, no may_goto, as today.\n\n2. Walk: each iteration has its own state. Selftest netif_receive_skb:\n for (i \u003d 0; i \u003c len; i++) {\n delta \u003d s1[i] - s2[i];\n if (delta || s1[i] \u003d\u003d 0 || s2[i] \u003d\u003d 0)\n break;\nThe compiler tests \u0027i - 9 \u003c 247\u0027, unsigned: no count. After a join i is\nunknown: \"math between map_value pointer and register with unbounded ..\"\nIn a walk i is a constant and decides its test.\nflow_try_walk() starts a walk. It goes on while each iteration but the\nfirst decides a jump that leaves the loop, for at most 4096 insns, or two\niterations of a longer loop. A loop with calls gets two iterations: its\nsize says nothing about the subprogs that it calls. strobemeta.h with\nNO_UNROLL, SUBPROGS and two maps:\n for (int i \u003d 0; i \u003c STROBE_MAX_MAPS; ++i)\n payload_off \u003d read_map_var(cfg, i, ..., data, payload_off);\nThe compiler makes a flag of i: no count. Only a walk bounds payload_off.\nA loop with two entries is walked whatever its jumps do. bpfjailer:\n for (int i \u003d BPFJ_MAX_POD_PER_PID - 1; i \u003e\u003d 0; --i) {\n if (i \u003e\u003d num_pods)\n continue;\nThe compiler copies the test in front of the loop and jumps into its\nmiddle. Scalar evolution says \"unsupported loop: irreducible\". With a join\n14 progs get a may_goto in a loop of 8 iterations.\n\n3. Join, widen, add may_goto. Test hash_fnv_bytes of rust-bpf:\n for b in bytes {\n h \u003d (h ^ *b as u64).wrapping_mul(0x100000001b3);\nThe length is unknown and h differs in each iteration. Today that is\n\"BPF program is too large. Processed 1000001 insn\". Now the walk ends in\nthe second iteration, flow.c widens h to an unknown scalar, and the state\nthat returns next is covered: 160 insns. That shows that each iteration is\nsafe, not that the loop ends. Thus the loop gets a may_goto. If there is\nno place for one: \"loop at insn N never exits\".\n\nbpf_flow_loop_leave() removes the loops that an edge leaves. flow.c and\nthe two functions call each other, so flow.o is built from here on, and\ndo_check() does not use it yet. A loop that leaks a reference in each\niteration has no fixpoint: check_refs_taken_in_loop() rejects a state that\nreturns to the head with a reference that no register and no slot holds.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-18-alexei.starovoitov@gmail.com\n" }, { "commit": "8875170bb1d2bd5bc36ed58d520a6e82764081a6", "tree": "78844cf1a7e6ed1620bed162f6d3e6c0e84daa9f", "parents": [ "19d27a501a52daa96fa9c9433f430adc26010eb3" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:24 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:53 2026 +0000" }, "message": "bpf: Make the state after a call from the caller\u0027s state and an exit state\n\nmatch_one() of scx_layered runs in three nested bpf_for() loops and calls\na static subprog, get_pid_nr_ns():\n\n scoped_guard(rcu) { ... nspid \u003d get_pid_nr_ns(p_pid, pid_ns);\n\nIt is verified for the states at its first insn, not for each chain of\ncalls. One exit state is the result for all calls that wait:\n\n 2: call f --- { r1\u003dscalar } ---\u003e +---------------------+\n 7: call f --- { r1\u003dscalar } ---\u003e | f: verified 1 time |\n 3: ... \u003c-- { r0\u003d[0,7] } ----- | |\n 8: ... \u003c-- { r0\u003d[0,7] } ----- +---------------------+\n\nThat works only if calls that differ in ids give the same entry state. Here\nthe callers hold three iterators, and each bpf_iter_num_new() has a new id.\nWhat is held is a part of the entry state: it decides what the subprog may\ndo. In the subprog the id of refs[i] of the caller becomes a name,\nBPF_INHERITED_ID + i. A name stands for one object of the caller. Thus\ncheck_ids() and the join do not rename it: it is equal only to itself.\n\nIf a call with something held keeps the frames of the callers instead,\nlayered_runnable takes 5219 insns, not 4459, and recursion has no end.\ncore::fmt of Rust is recursive, and progs format a message while they hold\na reference. 27 progs of the schedulers of rust-bpf fail:\n\"the call stack of 33 frames is too deep\".\n\nbpf_flow_return() makes the state after the call:\n - r0, and r2 of a pair, come from the exit state. r1-r5 and the outgoing\n stack arguments are not set.\n - What is held is what the caller held and what the subprog took. The\n names become the ids of the caller again.\n - All other ids get new values for each call. If not, two calls in\n sequence return the same object.\n\nSelftest test_spin_lock, lock_static_subprog_unlock():\n\n bpf_spin_lock(\u0026lockA);\n ret \u003d static_subprog_unlock(ctx);\n\nAn exit state does not tell what a release does to the caller. Thus the\nframe counts what it holds without interruption since its entry. If that is\nless than the caller held, the function returns 1, and the call is verified\nagain with the frames of the caller. Also: rcu_read_lock, preempt_lock. The\nsame if it changed the packet through a function that is its argument.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-17-alexei.starovoitov@gmail.com\n" }, { "commit": "19d27a501a52daa96fa9c9433f430adc26010eb3", "tree": "d18d2b345a495a283d73c1bea6dca9a3b5c0110d", "parents": [ "9b56d2e47f3ad9314cf263c419d7540fd0e2893f" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:23 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:53 2026 +0000" }, "message": "bpf: Move states along edges, into loops and subprogs and out of them\n\nSelftest test_verif_scale1 has these lines 90 times. jhash() is static:\n\n ptr \u003d data + i;\n if (ptr + nh_off \u003e data_end) break;\n ctx-\u003etc_index \u003d jhash(ptr, nh_off, ctx-\u003ecb[0] + i++);\n\nThe 90th call is reached with i \u003d 0 .. 89, in 90 states. All calls: 4095.\njhash() sees one of 90 pointers. If a state in jhash() has the frames of\nits callers, as today, states of different calls have no join:\n\"more than 1024 states that cannot be joined at insn 903\". Thus a state in\na static subprog has one frame, and the caller\u0027s state waits at the call:\n\n bpf_flow_call() saves the caller. The entry state goes to the set at\n the first insn of the subprog, like any state.\n bpf_flow_exit() a state at exit goes to all calls that wait for its\n entry state. The exit states are a set too.\n\nWhen the merge drops or joins an entry state, its calls wait for the state\nthat took its place, and flow_do_united() gives them its exit states. 4005\nof the 4095 calls end so: 50765 insns, today 530362. Else the limit stops\nthis test, 100 progs of the schedulers of rust-bpf and 124 of its tests.\n\nThe exit states of an entry are joined like the states at an insn, and the\njoins must end. Thus an exit state that was joined more than 16 times is\nwidened. The entry and the exits of a recursive subprog are widened at\nonce.\n\nLoops. Scalar evolution derives the count and the ranges of a loop from the\nstate that enters it. Thus the states that enter are a set of their own.\nA copy of each new one, with these ranges, goes to the set at the head.\nWhen a walk ends before the loop does, one state stands for the rest:\nflow_end_walk() joins, with widening, the state that came back to the head\nand the state one iteration before. They differ in what the loop changes.\nThere is no join if the iteration set a register for the first time, or\nchanged a constant that becomes an offset of the stack or of a pointer.\n\nbpf_flow_deliver() sends a state along an edge, bpf_flow_next() gives the\nnext new state. A state that gets to bpf_loop() gets its number there: what\nthe callback comes back with is widened with the state that it comes from.\nAn added may_goto is an edge that the prog does not have:\nbpf_flow_guard_edge() sends a state along it only if the loop has may_goto\nby now. Else it drops the state and notes that. If the loop gets may_goto\nlater, the prog is verified again.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-16-alexei.starovoitov@gmail.com\n" }, { "commit": "9b56d2e47f3ad9314cf263c419d7540fd0e2893f", "tree": "b9045f96ab839e22bb2d2e6e7ba62c13b2da10af", "parents": [ "773b03804ab1e0b2bfa0fac7d1b8562c168d14be" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:22 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:53 2026 +0000" }, "message": "bpf: Merge the state that arrives into the set at an insn\n\nscx_flow, flow_dispatch() is a row of blocks like this one:\n if (nq0 \u003e 0) {\n node_moved \u003d flow_move_one_hint(node_dsq, cpu, \u0026visits, nq0);\n if (node_moved \u003e left)\n node_moved \u003d left;\n left -\u003d node_moved;\n }\nEach way through a block leaves other ranges in left, visits, node_moved.\nNo check behind the block depends on the way. Today\u0027s verifier follows all\npaths: 70716 insns for a prog of 1117. With one state where the ways meet\nit takes 3127. flow_merge() puts a state S into the set at an insn:\n\n a state of the set covers S ? ------ yes --\u003e drop S\n | no\n S covers a state T of the set ? ---- yes --\u003e drop T\n |\n S has a join with a state T, ------- yes --\u003e drop T, S \u003d join(S, T),\n and no rule refuses it ? start again\n | no\n add S to the set: it is new, the verifier goes on from it\n\nA state is dropped only if a state of the set covers it. Thus the verified\nstates cover each execution of the prog.\n\nS can come around a cycle: to the head of a loop, to the first insn of\na recursive subprog, from a callback to its helper. There a bound can grow\nby one step each time: i\u003d[0,1], [0,2], ... Thus the join is a widening: it\ngives up the bound that grew. S and T differ in what the cycle changes, so\nthe rules that refuse a join are off. These stay on:\n - A constant that becomes a stack offset: bt_print() of scx has\n \u0027stack[depth++] \u003d ind + 1\u0027 and \u0027ind \u003d stack[depth]\u0027 in bpf_for().\n - A live register that only S has set. In clang 18\u0027s code of\n \u0027bpf_for(..) { if (..) continue; last \u003d rnd(); found \u003d true; }\u0027 and\n \u0027if (found) use(last);\u0027 the join has no \u0027last\u0027: \"R7 !read_ok\".\n - The calls of the callback of bpf_loop(N \u003c\u003d 8). What other callbacks come\n back with is joined 4 times, then widened.\nAll that holds only if S comes from T:\n ret \u003d 0; if (file-\u003ef_flags \u0026 O_TRUNC) { denied++; ret \u003d -EPERM; }\n bpf_for(i, 0, 100) { sum +\u003d a[i]; } total \u003d sum; return ret;\nTwo states enter the loop. Next to -EPERM the 0 that comes around looks\nlike a number that grew, and an LSM prog is rejected:\n\"R0 has smin\u003d0 smax\u003d4294967295 should have been in [-4095, 0]\".\nThus a state that enters a loop, or gets to bpf_loop(), has a number, and\nso has what becomes of it. S is widened with a T of its number only.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-15-alexei.starovoitov@gmail.com\n" }, { "commit": "773b03804ab1e0b2bfa0fac7d1b8562c168d14be", "tree": "c09fec9392e4536fc93de92c4f8d9022d4288fff", "parents": [ "6a32047087036bb27b770e9bc89d7c3fa2edf96a" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:21 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:52 2026 +0000" }, "message": "bpf: Decide which states are not joined\n\nCilium, nat.h, in tail_handle_snat_fwd_ipv4:\n\n if (ret \u003c 0) ..; to_sport \u003d state-\u003eto_sport;\n\n(ret\u003d-155, state\u003dmap_value_or_null) and (ret\u003d0, state\u003dmap_value) meet in\nfront of that. Numbers always have a join. But ret\u003d[-155, 0] with\nmap_value_or_null has ret\u003d0 without state, as no path has. It passes the\njump: \"R3 invalid mem access \u0027map_value_or_null\u0027\".\n\nA join must not make up what a later check can see. A number is tested if\na later jump compares it with a constant, or the verifier checks its range\nat a call or at exit. States that have a join stay apart if they differ in:\n\n - A tested number, and the ranges leave a gap: -155 and 0, not 0 and 1.\n 113 progs of Cilium, profiler3 and test_seg6_loop without alu32.\n - Two tested numbers, each without a common value: (err \u003e\u003d 0, ret\u003d0) and\n (err \u003c 0, ret\u003dDROP). The join has err \u003c 0 with ret\u003d0.\n - A flag, 0 and 1, that a jump in this basic block or the next one tests:\n \u0027ok \u003d i \u003c 64 \u0026\u0026 v-\u003ein[i] \u003d\u003d 2; if (v-\u003ex \u003d\u003d 7) v-\u003en++;\n if (ok) v-\u003ew[i] \u003d 1;\u0027\n clang keeps ok in a register. (ok\u003d0, i\u003e63), (ok\u003d1, i\u003c\u003d63), (ok\u003d0, i\u003c\u003d63)\n meet. The join has ok\u003d1 with i\u003e63: \"R0 unbounded memory access\".\n - A register that only one of them sets. scx_layered/layered_runnable:\n \u0027scoped_guard(rcu) { if (...) return result; nsid \u003d ...; }\u0027 meets at the\n unlock with a flag of the compiler, then reads nsid: \"R7 !read_ok\".\n - Two tested numbers, (0, x) and (y, 0). xdp_synproxy_kern and\n test_tcp_custom_syncookie: \u0027if (hdr-\u003eipv4) ... else if (hdr-\u003eipv6) ...\u0027\n after the packet changed: \"R1 type\u003dscalar expected\u003dfp, pkt, ...\".\n - A constant that becomes a stack offset. bt_print(), 5 selftests of scx:\n \u0027if (... || depth \u003e\u003d BT_MAXLVL_PRINT) return 0; ind \u003d stack[depth];\u0027\n A copy of depth is tested: \"invalid variable-offset read from stack\".\n - A constant that is added to a pointer. katran/tcdecapinfo, 20 or 40 in\n \u0027if (data + hdr_len + inner_ip_offset \u003e data_end)\u0027. With [20, 40] the\n jump says nothing about data + hdr_len: \"invalid access to packet\".\n - A constant that a kfunc or helper must know. One call is made of\n \u0027c ? bpf_rdonly_cast(0, id) : bpf_rdonly_cast(0, 0)\u0027 in\n mem_rdonly_untrusted/mixed_mem_type: \"R2 must be a known constant\".\n - The number of calls of the callback of bpf_loop(N, ...), N \u003c\u003d 8:\n \u0027bpf_loop(1, cb, \u0026ctx, 0); return choice_arr[ctx.i];\u0027 in\n verifier_iterating_callbacks: \"invalid access to map value\".\n\nThe rules only refuse joins: no unsafe prog loads because of them. They\ncost states: the first one 10 % of Cilium\u0027s insns, K flags 2^K states. Thus\nmost hold only while each limit is less than half used: flow_has_room().\n\nThe shape of a state is a filter in front of all that: hashes of its calls\nand loops, of what it holds, of the places, objects and constant offsets of\nits pointers. The load of test_cls_redirect_subprogs, 301 states at an\ninsn, takes three times as long without the shape.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-14-alexei.starovoitov@gmail.com\n" }, { "commit": "6a32047087036bb27b770e9bc89d7c3fa2edf96a", "tree": "8327b61d6f70549983c63e10bfc5e4d5a8cac241", "parents": [ "8468842a89502620fa3f4ce4c1010094f68b04a3" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:20 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:52 2026 +0000" }, "message": "bpf: Compare states of different iterations of a loop\n\nSelftest loop1, nested_loops():\n\n for (j \u003d 0; j \u003c 300; j++)\n for (i \u003d 0; i \u003c j; i++) {\n ...\n sum +\u003d i * m;\n }\n\nScalar evolution counts both loops, but has no closed form for sum, and the\nverifier checks sum: it is the return value. It walks such a loop: it\nverifies the iterations one by one, each with its own values, as it does\ntoday. A join of j\u003d5 and j\u003d6 ends that. Thus a state has the number of its\niteration in each loop that is walked, and flow_trips_behind() tells the\nmerge, the code that puts a state into a set, which states not to join.\nBut then the states of all iterations stay in the sets, up to the limit:\n\n more than 1024 states that cannot be joined at insn 10\n\nA walk only goes forward: what follows a state of iteration N is of\niteration N or later. flow_earlier_trip() finds the states that are two or\nmore iterations behind, and the merge frees them. nested_loops() then has\n21 states at a time and takes 9954 insns (today: 5505 and 316200).\nlavd_init and qmap_init of rust-bpf fail in the same way.\n\nCrate spin, Mutex::lock():\n\n while self.is_locked() { R::relax(); }\n\nNo iteration changes what the verifier sees: each ends in the state of the\none before, with a larger number. Thus in a walk of a loop without a count\na state of an earlier iteration can cover a later one. flow_trips_near():\nthe merge drops a state that a state of its own iteration or of the two\nbefore it covers. If only states of one iteration are compared, 164 of the\n225 progs of the schedulers of rust-bpf take more insns, 9 % in sum.\n\nThe drop closes a cycle: the earlier state leads to the later one and now\nstands for it. \"No state returns to the head, so the loop ends at run time\"\ndoes not hold any more. Thus flow_cycle_closed() gives the loop a may_goto.\nIt does nothing if the loop is counted, or if may_goto or bpf_iter_*_next()\nstops each iteration. It rejects a loop that has no place for may_goto.\n\nflow_within() is \u0027covers\u0027 for the merge: the comparison of pruning, also of\nthe states that entered each counted loop: its ranges come from them.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-13-alexei.starovoitov@gmail.com\n" }, { "commit": "8468842a89502620fa3f4ce4c1010094f68b04a3", "tree": "c988bcb9626603ca65c7e4e9a1c5c67bbdddd136", "parents": [ "a8bfc00bacb47a57f2a284ac2f80f196dacac1ee" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:19 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:52 2026 +0000" }, "message": "bpf: Add the sets of states at an insn and the entries of functions\n\nSelftest test_verif_scale1 has these lines 90 times. jhash() is static:\n\n ptr \u003d data + i;\n if (ptr + nh_off \u003e data_end) break;\n ctx-\u003etc_index \u003d jhash(ptr, nh_off, ctx-\u003ecb[0] + i++);\n\nToday the verifier verifies jhash() again for each state at each call:\n530362 insns. The main pass verifies a static subprog for the states at its\nfirst insn, and the call waits for the states at the exits. Each call that\nwaits makes an entry. Its number is in the entry state and in all states\nthat come from it. 4095 states arrive at the 90 calls. At the first insn of\njhash() a state of a different call covers 4005 of them. Then each exit\nstate is for the calls of the two:\n\n call A --\u003e entry 1 --+\n +--\u003e one set: calls { A, B }, exit states\n call B --\u003e entry 2 --+\n\nThus the entries are disjoint sets, with union and find: 50765 insns. If\nthey stay apart, the main pass hits its limit of states at an insn:\n\"more than 1024 states that cannot be joined at insn 903\". The same for\npandemonium_enqueue of scx_pandemonium and 100 of the 225 progs of the\nschedulers of rust-bpf.\n\nAll new states are in one tree. flow_set_pending() gives them an order:\n 1. Callers are before the subprogs that they call: all calls get to\n a subprog before it is verified.\n 2. Then the position of the call in each frame, then of the insn. Thus\n a callee that keeps the frames of its callers, like a callback, is\n complete before the code after the call.\n 3. A walk verifies a loop iteration by iteration, as today. An iteration\n is complete before the next one:\n\n for (int i \u003d 0; i \u003c MAX_AFFINITY_CANDIDATES; i++) {\n if (*val \u003e\u003d nr_cpu_ids) continue;\n if (++checked \u003e\u003d affinity_search_online) break;\n\n\u0027continue\u0027 is a back edge in the middle of the loop. By position alone it\nruns ahead through all iterations, and each is done again when the rest of\nthe one before it arrives: pandemonium_select_cpu, 130073 insns, not 26758.\n\nbpf_flow_prepare() marks the insns where a state goes into a set, and those\nwhere a second state can arrive. Only there the set keeps a state that the\nverifier used: to keep them all doubles the peak of states of Cilium, scx.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-12-alexei.starovoitov@gmail.com\n" }, { "commit": "a8bfc00bacb47a57f2a284ac2f80f196dacac1ee", "tree": "4560b6a9658db64303c6d9e4c6c2f738eaa7fb10", "parents": [ "0c5ce25870572abc3f954eb88411013562de7b66" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:18 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:52 2026 +0000" }, "message": "bpf: Find the registers and stack slots that later checks depend on\n\nThe join of two constants is not a constant, and some checks need one. The\ntwo states meet before the insn that checks. Thus the verifier must know,\nwhere they meet, that a later check depends on a register or a stack slot.\nA table per kind of check, FLOW_NEED_*, tells the rules that refuse a join:\n\nARG an argument that must be a constant\n if (x) return bpf_rdonly_cast(0, ID); return bpf_rdonly_cast(0, 0);\n The compiler makes one call of it: \"R2 must be a known constant\" in\n selftest mem_rdonly_untrusted/mixed_mem_type.\nSTACK_OFF an add to a pointer to the stack\n if (... || depth \u003e\u003d BT_MAXLVL_PRINT) return 0; ind \u003d stack[depth];\n The compiler tests one copy of depth and adds another. bt_print() of scx:\n \"invalid variable-offset read from stack R3\"\nPTR_OFF an add to a pointer to the packet, the context, a kernel object,\n a map value that is read-only or has a timer, a lock, a pointer\n if (data + hdr_len + inner_ip_offset \u003e data_end) return TC_ACT_UNSPEC;\n inner_protocol \u003d inner_iph-\u003eprotocol;\n With [20, 40] as the offset the test tells nothing about data + hdr_len:\n \"invalid access to packet, off\u003d48 size\u003d1\" in katran/tcdecapinfo.\nJUMP a jump that compares with a constant, an argument or a return\n value that the verifier compares with a range\n if (ret \u003c 0) ..; to_sport \u003d state-\u003eto_sport;\n ret is a negative constant where state can be NULL. As a part of a range\n it passes the test: \"R3 invalid mem access \u0027map_value_or_null\u0027\" in\n tail_handle_snat_fwd_ipv4 of Cilium.\n\nThree more tables are only for bpf_flow_is_needed(): does a check depend\non a value that a counted loop changes and that has no closed form? If not,\nthe value is widened at the loop head, and the verifier has no reason to\nwalk the iterations one by one:\n\n for (int i \u003d 0; i \u003c STACK_MAX_LEN; ++i) {\n if (!frame_ptr || !get_frame_data(frame_ptr, pidData, \u0026frame, \u0026sym))\n\nEach iteration fills the 24 stack slots of sym anew, and no check looks at\nthem. pyperf600_nounroll takes 1281 insns, 154K with a walk of all 600.\n\nVALUE_OFF PTR_OFF, STACK_OFF, and an offset in each other map value\nBASE the address of a load or a store\nJUMP_ALU JUMP, and the values that the tested value is calculated from\n\nflow_compute_need_const() goes backward through the control flow graph\nuntil nothing changes, like the calculation of live registers. A use that\nit misses can reject a valid prog. It cannot accept an unsafe prog.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-11-alexei.starovoitov@gmail.com\n" }, { "commit": "0c5ce25870572abc3f954eb88411013562de7b66", "tree": "f6d332936dfe9c280c7c9e3498471487247ee386", "parents": [ "9075b1169d6b9c7c016c3cef266a54b630d5f7b5" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:17 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:52 2026 +0000" }, "message": "bpf: Find the registers that hold a number or a pointer to arena\n\nThe allocator of tools/sched_ext/scx_sdt.bpf.c looks for a free slot:\n\n if ((word \u0026 0xffffffff) \u003d\u003d 0) { num +\u003d 32; word \u003e\u003e\u003d 32; }\n if ((word \u0026 0xffff) \u003d\u003d 0) { num +\u003d 16; word \u003e\u003e\u003d 16; }\n ... six times, this is ffs()\n return (i * 64) + ffs(freeslots);\n\nThe main pass joins the two states behind each \u0027if\u0027: num is [0, 32], then\n[0, 48]. It must not join two constants that the prog adds to a pointer to\nthe packet, the context or a kernel object: these need the exact offset.\nThe states meet before the add, and there the add is only \u0027r0 +\u003d r3\u0027. If r0\ncan be such a pointer, num stays a constant and each \u0027if\u0027 doubles the\nstates: up to 256 at an insn, not 2. sdt_init_task: 4897 insns, not 666.\n\nbpf_flow_compute_kinds() goes forward through the control flow graph,\nbefore the main pass. It finds the registers, stack slots and stack\narguments that hold, on each path to an insn:\n - plain_regs: a scalar, or a pointer to arena: it may point anywhere,\n - value_regs: that, or a pointer to a map value that has only scalars and\n is not read-only: only the lowest and the highest offset count,\n - the context: a load through it can give a pointer to the packet.\n\n ALU op other than 64-bit add, sub, mov scalar, addr_space_cast too\n 64-bit add, sub what both operands are\n load through a scalar or a map value scalar\n load through ctx, or of less than 8 bytes is_valid_access() tells\n spill and fill through r10, r11 what the prog stored\n helper, kfunc from the prototype\n static subprog true at all calls, all exits\n global subprog, callback, target of callx only the context\n\ntest_cls_redirect.c has the context in a struct. In a subprog c-\u003eskb comes\nfrom the stack of the caller: nothing is known about it.\n data \u003d c-\u003eskb-\u003edata; if (data + (v6 ? 40 : 20) \u003e end) return 0;\nSo 4 bytes at the offset of data can be a pointer. Else 20 and 40 are\njoined: \"invalid access to packet\". loads_pkt_end notes a subprog that\nloads data_end, for the main pass. void * from a kfunc is a scalar, but not\nwith KF_RET_NULL and not from bpf_rdonly_cast(), bpf_cast_to_kern_ctx().\n p \u003d bpf_core_cast(t, struct task_struct); x \u003d z ? p-\u003epid : p-\u003etgid;\nis one \u0027r0 +\u003d r1\u0027 with 1856 or 1860. Joined:\n\"invalid variable offset access into struct task_struct\".\n\nThe result only selects the states that the main pass does not join:\na mistake rejects a valid prog or makes more states. No unsafe prog loads.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-10-alexei.starovoitov@gmail.com\n" }, { "commit": "9075b1169d6b9c7c016c3cef266a54b630d5f7b5", "tree": "492e26338a0e788df50c69eeef1f87ad15b1ae33", "parents": [ "0c30e60b214c1c308c6c198f7fd7dfbe2dc8ce72" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:16 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:52 2026 +0000" }, "message": "bpf: Order the insns, find what stops a loop and where may_goto can go\n\nA fixpoint shows that each iteration of a loop is safe, not that it ends:\n\n do { i++; sum +\u003d PT_REGS_RC(ctx); } while (i \u003c 0x100000000ULL);\n\nToday selftest loop3 hits the limit of 1M insns. The main pass widens i and\nis done, so the verifier has to add a may_goto. That is an edge that the\nprog does not have. Its place decides which progs load:\n\n1. None, if each iteration executes a may_goto that leaves the loop, or\nbpf_iter_*_next() of an iterator that was created before the loop.\n\n bpf_repeat(1000000) {\n map_val \u003d bpf_map_lookup_elem(\u0026hash_map, \u0026key);\n if (map_val) { found \u003d true; break; }\n }\n if (found) *map_val \u003d 123;\n\nAn added may_goto goes where \u0027break\u0027 goes, without the test. Selftest\niters/iter_tricky_but_fine: \"R6 invalid mem access \u0027map_value_or_null\u0027\".\nlayered_init of scx_layered and mitosis_init of scx_mitosis fail alike.\n\n2. In front of a conditional jump that leaves the loop, to its target: the\nprog gets there with the same registers and stack. One jump of the loop\nitself, bpf_insn_leaves_loop(), that each iteration goes through is enough:\nthe \u0027while\u0027 of loop3. Else each back edge gets one: a may_goto at the head\nskips the body, and the first exit can read what the body sets.\n\n3. At the head, if a back edge has none. The compiler makes one loop of\n\n while self.locked.compare_exchange(0, 1, Acquire, Relaxed).is_err() {\n while self.locked.load(Relaxed) !\u003d 0 { core::hint::spin_loop(); }\n }\n\nand the inner back edge has none. Without this place the main pass says\n\"loop at insn 127 never exits\" for 142 of the 225 progs of the schedulers\nof rust-bpf. This edge can skip what stops an outer loop: it leaves all.\n\nThe added insn executes in each state. Thus a loop has it for all states or\nfor none. The main pass can find out late: it first goes through loop3\niteration by iteration, as today, and gives up. Then the pass is repeated.\n\nThe main pass takes the blocks that have a new state in the order of\nflow_compute_order(): reverse post order, but a loop stays together. Else\nthe code behind a \u0027break\u0027 is verified before the loop is done, then again.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-9-alexei.starovoitov@gmail.com\n" }, { "commit": "0c30e60b214c1c308c6c198f7fd7dfbe2dc8ce72", "tree": "d320c6165c18f99b164a09639e96ced9b8d495a6", "parents": [ "af6bda3802aff62d5d2f413820b5157d08b7a767" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:15 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:52 2026 +0000" }, "message": "bpf: Add the data structures of the main pass over the control flow graph\n\nThe verifier follows each path of a prog from the entry to exit. It ends a\npath early only where an earlier path left a state that covers the current\none. A live value that differs from path to path defeats that. Then the\nwork grows with the number of paths, not with the size of the prog:\n\n for b in bytes { h \u003d (h ^ *b as u64).wrapping_mul(0x100000001b3); }\n\nIn this FNV hash h is a new number in each iteration, so no state covers\nthe next one. Branches that set different values do the same to C code.\n\n insns processed today this series\n rust-bpf hash_fnv_bytes 1000001 * 160\n rust-bpf scx_qmap/qmap_init_cids 131088 * 196\n selftests test_verif_scale3/balancer_ingress 821107 57155\n scx scx_eevdf/eevdf_dispatch 350041 15322\n Cilium bpf_host/cil_to_netdev, Oct 2026 64658 7538\n * \"BPF program is too large\", \"The sequence of 8193 jumps is too complex\"\n\nflow.c is a new main pass: a data-flow analysis over the control flow\ngraph that runs to a fixpoint. Where two paths meet, it joins their states\ninto one state that covers both: r1\u003d1 and r1\u003d5 give r1\u003d[1,5]. At the head\nof a loop it widens what grows: h becomes an unknown scalar, and one more\npass over the body ends the loop. A join can lose a fact that a later check\ndepends on. Thus a basic block has a set of states, not one state:\n\n a state arrives at a basic block the verifier\n a state of the set covers it drops it\n it has a join with a state of the set replaces that state with the join\n all other cases adds it to the set\n\nThe verifier verifies a block with each new state of its set and sends the\nresults to the successors of the block. The pass ends when no set has a new\nstate. The check of one insn does not change.\n\nAdd the head comment, the limits and the data structures:\n\n struct flow_state a state in a set, or the state of a call that waits\n struct flow_set the states at one insn\n struct flow_entry the calls that wait for a subprog, its exit states\n struct flow_need what the checks after an insn depend on\n\nThe limits are on states and grow with the prog. For a prog of N insns:\n1024 at an insn, 16 * N + 4096 at a time, 256 * N + 64K in all.\nNothing builds flow.c until its last function is there.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-8-alexei.starovoitov@gmail.com\n" }, { "commit": "af6bda3802aff62d5d2f413820b5157d08b7a767", "tree": "c48dd906e7babe380d0d19f6276b7a3a6fd7df55", "parents": [ "ff30ca620432fe6900b3d695ff4ab7efbd8a8089" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:14 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:52 2026 +0000" }, "message": "bpf: Tell which arguments of a call a join must leave alone\n\nget_some_addr() of the selftest mem_rdonly_untrusted:\n\n if (bpf_get_prandom_u32())\n return bpf_rdonly_cast(0, bpf_core_type_id_kernel(struct sock));\n else\n return bpf_rdonly_cast(0, 0);\n\nThe compiler makes one call of the two, with r2 \u003d 0 or the type id. The\npaths meet in front of the call, and a join makes a range of two constants:\n\n R2 must be a known constant\n\ncil_sock4_connect() and cil_sock4_sendmsg() of Cilium\u0027s bpf_sock:\n\n if (err \u003d\u003d -EHOSTUNREACH || err \u003d\u003d -ENOMEM) {\n try_set_retval(err);\n\nThe compiler decides the \u0027if\u0027 where err is set, and keeps a flag. All\npaths meet, then the flag is tested. In the join err is [-113, 1]:\n\n At bpf_set_retval the register R1 has .. should have been in [-4095, 0]\n\nThe progs are valid. A pass that joins states must know, ahead of a call,\nwhich registers it must not join.\n\nantistall_set() of scx_layered:\n\n bpf_for_each(scx_dsq, __p, dsq_id, 0) {\n\nbpf_iter_scx_dsq_next() ends this loop: it needs no may_goto. The pass that\nfinds the places for may_goto must know that, before the main pass sets\nis_iter_next in insn_aux_data. With may_goto in each such loop layered_init\nand mitosis_init are rejected on the added edge, and the schedulers in\ntools/sched_ext take 48 % more insns.\n\n bpf_call_const_arg_regs() a helper or a kfunc takes only a known\n constant in these registers\n bpf_call_checked_arg_regs() it compares them with a range: sizes of\n memory, the argument of bpf_set_retval()\n bpf_insn_is_iter_next() the call is bpf_iter_*_next()\n\nThe first two go by the types of the arguments in struct bpf_func_proto,\nlike check_func_arg(), for r1 - r5. bpf_set_retval() is checked elsewhere\nand is added by hand. Nothing calls the three in this patch.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-7-alexei.starovoitov@gmail.com\n" }, { "commit": "ff30ca620432fe6900b3d695ff4ab7efbd8a8089", "tree": "35a8cf5af126fada1ff4ede2c5c39f42d2fe237e", "parents": [ "47388a4c175e4b1528c69cfee9f68663aa217887" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:13 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:52 2026 +0000" }, "message": "bpf: Add join of verifier states\n\ncentral_dispatch() of tools/sched_ext/scx_central.bpf.c:\n\n bpf_for(cpu, 0, nr_cpu_ids) {\n ...\n if (dispatch_to_cpu(cpu))\n *gimme \u003d false;\n }\n ...\n dispatch_to_cpu(central_cpu);\n\nTo verify dispatch_to_cpu() one time, not for each call, the states of the\ntwo calls must meet at its first insn. Numbers, like cpu, can be joined.\nBut at one call the iterator of bpf_for() is held, at the other nothing.\nOne state cannot stand for the two: the code after the return destroys the\niterator for one of them only. A state is more than registers and slots.\n\nAdd the second half of join.c and build it. bpf_states_join() joins two\nstates at one insn, frame by frame. There is no join, and the caller keeps\nthe two states, when one of these differs:\n\n frames number, subprog, callsite, kind of callback\n locks, RCU, preempt the counts, the lock\n references number and types. The ids must pair one to one\n held since the entry entry_refs, entry_rcu_locks, entry_preempt_locks\n loop stack the loops, the state that entered them, the count,\n the iteration if iterations are kept apart\n flags speculative, sleepable, unwound, ...\n\n - A register, its spill and the reference have one id. Thus the pairs of\n ids are collected over all frames and references first, and the join\n is made in a second pass.\n - Only live registers count, and the caller removes dead stack slots with\n bpf_clean_verifier_state(). What is dead does not prevent a join.\n - A subprog that is verified without its callers has what they hold in\n its state, as above. entry_* tell how much of it is still held.\n - Such a subprog has its incoming stack arguments in the slots for\n outgoing ones, until it has loaded them. The two kinds are not joined.\n quicksort(right, scratch, limit, pivot_ref, is_less) of Rust\u0027s core is\n recursive and takes 7 words: bpfland_init of rust-bpf fails without it.\n\nbpf_states_join() examines each result with the comparison that pruning\nuses: the join must cover state a and state b. If it does not, that is a\nverifier bug and the prog is rejected, not loaded. The fields that join.c\ncompares come with this patch. Nothing sets them, nothing calls the join.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-6-alexei.starovoitov@gmail.com\n" }, { "commit": "47388a4c175e4b1528c69cfee9f68663aa217887", "tree": "7a8953dcea01c8d106f2d0ceb44517eccab895ed", "parents": [ "ff3712ef1106c70ec88da6391da958d4e9d4d622" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:12 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:52 2026 +0000" }, "message": "bpf: Add join of registers and stack slots\n\nipv6_hdrlen_offset() of Cilium skips extension headers, unrolled:\n\n for (i \u003d 0; i \u003c IPV6_MAX_HEADERS; i++) {\n int hdrlen \u003d ipv6_skip_exthdr(ctx, \u0026newnh, l3_off + len);\n ... 8, (opthdr-\u003ehdrlen + 2) \u003c\u003c 2 or (opthdr-\u003ehdrlen + 1) \u003c\u003c 3\n len +\u003d hdrlen;\n }\n\nThe verifier follows each path. Three lengths for each header: the insn\nbehind this loop is verified 76 times, and each time the rest of the prog\nfollows, where more paths fork. tail_nodeport_nat_ingress_ipv6 of bpf_xdp,\nas of May 2026, has 4095 insns, the verifier processes 182050.\n\nAdd the join of two states: one state that covers the two. Here hdrlen is\n[8, 2048]. A caller that replaces two states with their join verifies the\ncode that follows one time. This prog: 3 times in place of 76, 7932 insns.\nThis is the first half of join.c: ids, registers, stack slots.\n\nOnly numbers are joined: scalars, and the variable offsets of pointers. A\njoin loses information. Where the prog needs it there is no join, and the\ncaller keeps the two states:\n - map value + 8 and map value + 16: two fields, not a range\n scx_rusty: create_save_cpumask(\u0026kptr) for three kptrs in .data\n \"R1 doesn\u0027t have constant offset. kptr has to be at the constant offset\"\n - packet pointers that are checked up to different ends\n Cilium: l4_csum_replace(ctx, l4_off + csum-\u003eoffset, ..)\n \"invalid access to packet\": 206 progs of bpf_xdp in 37 builds of Cilium\n - a scalar and a pointer, pointers to two objects: of no use to a prog\n\nEach path makes its own ids. An id in the join stands for a pair: the id\nin state a and the id in state b. The pairs must be one to one, as in\ncheck_ids(). If not, a scalar loses its id, and a pointer has no join.\n - \u0027bpf_for(i, 0, 10) sum +\u003d i;\u0027 of iters_num: each bpf_iter_num_next()\n returns a pointer with a new id. If ids had to be equal, the main pass\n says \"more than 1024 states that cannot be joined at insn 16\".\n - scx_pandemonium: \u0027if (.. \u0026\u0026 (u32)src_cpu \u003c MAX_CPUS) pair_warm_ns[..]\u0027\n tests r5 and indexes with its copy in fp-88. Paths meet between copy\n and test. A join without ids: \"R3 unbounded memory access\".\n\nWith \u0027widen\u0027, at a loop head, a scalar that grew is widened. If each\niteration adds a constant to it, it becomes an unknown scalar of 64 or 32\nbits at once: scev_compute_linear_regs() sets linear_regs, linear32_regs of\nstruct bpf_loop for that. So does sum of bpf_for() above: it is a register\nplus or minus something (expr_is_sum()), and no jump of the loop depends on\nit (tested_regs). 0, [0, S32_MAX], [0, U32_MAX], unknown are 4 passes\nthrough the body, this is 2: 59 -\u003e 43 insns. If a jump depends on the sum\nthe stops stay. A pointer whose offset grew has no join: no later\ncomparison gives it a bound.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-5-alexei.starovoitov@gmail.com\n" }, { "commit": "ff3712ef1106c70ec88da6391da958d4e9d4d622", "tree": "e1879701e32367b365ddfb0d4c4404e63df8a195", "parents": [ "7b7dc9c6e8e94f086a2c3ccf01692879e37aca93" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:11 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:52 2026 +0000" }, "message": "bpf: Add union and widening of the range of a register\n\nformat_cgrp_path() of scx_layered, prog layered_runnable:\n\n u32 len \u003d 0;\n bpf_for(level, 1, max_level + 1) {\n if (level \u003e 1 \u0026\u0026 len \u003c MAX_PATH - 1)\n path[len++] \u003d \u0027/\u0027;\n ...\n len +\u003d ret - 1;\n }\n\nThe verifier follows each path, and its work grows with the number of\npaths. To make it grow with the size of the prog, the states that meet at\nan insn must become one state. Then the loop head has one state for all\niterations. len in it is the union of what arrives: 0 from above, more\nafter each pass through the loop, and the passes do not end. Widening ends\nthem: the bound that moved is put far out at once, and the jumps in the\nloop make the range small again. The compiler tests len in 32 bits:\n\n len at the head after \u0027if w7 \u003e 0xffe\u0027 path[len++] \u003d \u0027/\u0027\n [0, S64_MAX] [0, 0x7fffffff00000ffe] R2 unbounded memory access\n [0, U32_MAX] [0, 4094] ok\n\nA 32-bit compare cannot bring back what widening to 64 bits threw away.\nThus bpf_reg_widen_range() moves a bound to the nearest of a few stops: 0,\nS32_MAX, U32_MAX, S64_MAX above it, 0, S32_MIN, S64_MIN below. A stop is\na guess, and a guess that fails costs one more pass. No jump holds sum in\n\u0027sum +\u003d a[i]; if (sum \u003d\u003d 77) ..\u0027. After S32_MAX it can still have 32 bits:\nU32_MAX holds it. A bound that was at S32_MAX, U32_MAX or S32_MIN and\nleaves 32 bits gets no other stop: [0, S64_MAX] wraps in the next pass. The\nnumber is unknown: btree_set_ops of rust-bpf, 251722 -\u003e 230969 insns.\n\nrusty_dispatch of rust-bpf: \u0027r9 +\u003d 1; if r9 \u003c r8 goto\u0027 with r8 from memory.\n2, [2, S32_MAX], [2, U32_MAX], unknown: 4 passes. Scalar evolution knows\nthat each iteration adds a constant to r9: @linear. Such a number goes on\nuntil it wraps. It is unknown at once, or [0, U32_MAX] if it is computed in\n32 bits: 2 passes, 788 -\u003e 536 insns.\n\nbpf_reg_union_range() is the union, without the reg_bounds_sync() of\nbpf_reg_union(): an input is not always in sync. It keeps the step of\na number. clang counts \u0027for (i \u003d n; i \u003e\u003d 0; i--) sum +\u003d a[i];\u0027 in bytes:\n\u0027r2 +\u003d -4; if r2 !\u003d -4 goto\u0027. n is a range, so \u0027!\u003d\u0027 gives no count. r2\nstops at -4 only because it is a multiple of 4. a + s * k and b + t * k are\nboth of the form a + gcd(s, t, a - b) * k. A step gives way to one of its\ndivisors only: it needs no widening. Nothing calls this code yet.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-4-alexei.starovoitov@gmail.com\n" }, { "commit": "7b7dc9c6e8e94f086a2c3ccf01692879e37aca93", "tree": "b1d26383bb227cd7f784df36e06302d3aa9d3174", "parents": [ "8ed7285ee07534fae63041dcce69686ef96b16b8" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:10 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:52 2026 +0000" }, "message": "bpf: Limit depth and time of recursive subprogs at run time\n\nRust recurses where C has a loop. scx_flatcg.rs of rust-bpf has\n\n struct CgrpCtx { parent: Option\u003cArc\u003cCgrpCtx\u003e\u003e, ... }\n\nThe drop of the last Arc of a cgroup drops the Arc of its parent:\nArc::drop_slow() calls itself, and 8 of the 15 progs are rejected:\n\"recursive call from drop_slow\u003c..\u003e() to drop_slow\u003c..\u003e()\". quicksort() under\nsort_unstable_by() in scx_rusty.rs, BTreeMap, serde_json and regex-automata\nrecurse too: 100 of the 225 progs of the schedulers of rust-bpf, 100 of its\n437 tests. The verifier cannot know how deep the calls go, or how many\nthere are.\n\nLimit both at run time. Each subprog on a cycle of the call graph starts\nwith two checks:\n\n entry: may_goto bail limits the time\n if (r10 is in the upper half of the stack) limits the depth\n goto body\n bpf_prog_report_recursion()\n bail: r0 \u003d 0; exit\n body: ...\n\nBoth are needed. The depth does not limit the time:\n\n int fib(int n) { return n \u003c 2 ? n : fib(n - 1) + fib(n - 2); }\n\nfib(90) is never deeper than 90 frames and makes 10^19 calls. There is no\nloop in it, so no may_goto of a loop bounds it. The cycle is in the call\ngraph, and it goes through the first insn of fib(). With may_goto there\nfib(90) ends after 250 ms, the time slice that the loops and recursions of\nan invocation share. The time does not limit the depth:\n\u0027int f(int n) { return f(n + 1) + 1; }\u0027 is out of stack in less than 1 ms.\n\nr10 is an address in the kernel stack that the prog runs on. Thus the check\nsees all that is in this stack, not only the frames of this prog, without\nper-cpu state. On arm64 a stack is aligned to its size: one bit of r10\ntells the half. On x86-64 r10 is compared with the tops of the task stack\nand the irq stack. In any other stack, like in an NMI that interrupts the\nkernel, the check fails. Other archs get no recursion. The stack in arena\nhas no check: the verifier makes the frame in the kernel stack so large\nthat a half of that stack is full before the stack in arena. It does so in\ncheck_call_depth(): the limit on the stack of a chain of calls has to see\nthe frames that the JIT gets.\n\nNo subprog is marked as recursive yet. A call runs 12 more insns on x86-64\n(17 on the irq stack), 8 on arm64: +0.2 to +0.5 nsec on x86-64.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-3-alexei.starovoitov@gmail.com\n" }, { "commit": "8ed7285ee07534fae63041dcce69686ef96b16b8", "tree": "f86224c8c552176bbd5eda500391c127c37bb6f6", "parents": [ "ad6472e01a5f5e8968a2fbe7623c84368b6a95e3" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 03:37:09 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Sat Nov 07 04:56:52 2026 +0000" }, "message": "bpf: Add may_goto to the loops that the verifier marks\n\nSpinLock::lock() of rust-bpf (scx_common.rs), here in central_enqueue:\n\n while self.locked.compare_exchange(0, 1, Acquire, Relaxed).is_err() {\n while self.locked.load(Relaxed) !\u003d 0 { core::hint::spin_loop(); }\n }\n\n infinite loop detected at insn 127\n\n111 of the 225 progs of the schedulers of rust-bpf get this message. Memory\ndecides when the loop ends: no analysis finds a bound. The same holds for\na lookup in a BTreeMap. C has bpf_for(), can_loop, bpf_loop(). Nobody can\nput them into core and alloc.\n\nWith one state for all iterations the verifier can still show that each of\nthem is safe. Then the kernel must stop the loop at run time. may_goto does\nthat: after 250 ms it jumps to its target. That jump is a new edge in the\nprog, and must be verified. One target for all loops is not possible:\n\n lock(), see above pick_idle_cpu_in() of scx_p2dq.rs\n Not to the exit of the loop: let cores \u003d core.then(..::idle_smt);\n the caller goes on as if it cpus.filter(..).find(..)\n had the lock. Unwind instead: Not out of the function: the code\n after the loop releases the cpumask.\n may_goto L\n insn may_goto T\n ... if ... goto T\n last insn of the subprog\n L: r0 \u003d 0\n unwind_exit, main prog: exit T is outside of the loop\n\nThus the main pass selects the edge for each loop, verifies it, and\nrecords it in insn_aux_data. bpf_insert_loop_guards() adds the insns after\nthe main pass. No code sets loop_guard in this patch: no prog changes.\n - unwind_exit is for a subprog whose callers have cleanup code for it\n (bail_unwinds): their destructors run, the code after the call does not.\n - The inner loop of lock() goes around without a jump that leaves. Then\n may_goto is at the loop head (guard_at_header): 142 of the 225 progs.\n - may_goto has a 16-bit offset. If L is more than 2048 insns away it gets\n \u0027r0 \u003d 0; exit\u0027 of its own, and one more jump in each iteration.\n\nProgs without such a loop get the same code. 174 of the 225 progs have one.\nAn added may_goto costs what a may_goto of the prog costs. It is 10 insns,\n14 if no register is dead: thus it gets the live registers of the insn that\nfollows it. That, and one L per subprog, not per loop: 6 % less jited code.\n\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261107033758.1547725-2-alexei.starovoitov@gmail.com\n" }, { "commit": "ad6472e01a5f5e8968a2fbe7623c84368b6a95e3", "tree": "3216c9cfc5a7cd0beedf659301350925518b22cb", "parents": [ "9736b748ee82a5159bb5b5c45a5c7ed77e8b4a98" ], "author": { "name": "Ihor Solodrai", "email": "ihor.solodrai@linux.dev", "time": "Fri Nov 06 12:57:30 2026 -0700" }, "committer": { "name": "Andrii Nakryiko", "email": "andrii@kernel.org", "time": "Fri Nov 06 16:38:19 2026 -0800" }, "message": "bpftool: Replace the type tag override table with two checks\n\nbtf_c_annotate_type_tags() looks each type tag up in a table of\noverrides. The table holds two fixed cases, the \"address_space(1)\"\nstring of older kernel BTF and the plain \"arena\" tag, and is not\nexpected to grow.\n\nCheck for the two tags directly and drop the table.\n\nNo functional change.\n\nSuggested-by: Andrii Nakryiko \u003candrii@kernel.org\u003e\nSigned-off-by: Ihor Solodrai \u003cihor.solodrai@linux.dev\u003e\nSigned-off-by: Andrii Nakryiko \u003candrii@kernel.org\u003e\nLink: https://lore.kernel.org/bpf/CAEf4BzbpVnoqKnGAVKYRffraPpPWjnNFF2oFAnXmBkqd2V6vmg@mail.gmail.com/\nLink: https://lore.kernel.org/bpf/20261106195730.2623973-3-ihor.solodrai@linux.dev\n" }, { "commit": "9736b748ee82a5159bb5b5c45a5c7ed77e8b4a98", "tree": "328d4ca3805ff25253743a00820ec64f7258c2bc", "parents": [ "2210e69db7217bca218693fde5ed45bcbe8ff519" ], "author": { "name": "Ihor Solodrai", "email": "ihor.solodrai@linux.dev", "time": "Fri Nov 06 12:57:29 2026 -0700" }, "committer": { "name": "Andrii Nakryiko", "email": "andrii@kernel.org", "time": "Fri Nov 06 16:38:19 2026 -0800" }, "message": "libbpf: Drop btf_dump details from the BTF docs\n\nbtf.rst describes the BTF format, but commit fbafb695c5d2 (\"libbpf: Let\ndecl tags override how btf_dump renders type tags\") and\ncommit 79dcfd3e36a7 (\"libbpf, bpftool, resolve_btfids: Dump kflagged\nBTF tags as is\") added to it how btf_dump prints kflagged tags and decl\ntags on type tags. The comments of btf__add_type_attr() and\nbtf__add_decl_attr() also prescribe what the string must contain,\nthough it is arbitrary text that depends on the use case.\n\nDescribe kflagged tags only as arbitrary annotations in both places.\nKeep a short note on the type tag override in btf_dump.c, whose comment\npointed to btf.rst.\n\nSuggested-by: Andrii Nakryiko \u003candrii@kernel.org\u003e\nSigned-off-by: Ihor Solodrai \u003cihor.solodrai@linux.dev\u003e\nSigned-off-by: Andrii Nakryiko \u003candrii@kernel.org\u003e\nLink: https://lore.kernel.org/bpf/CAEf4BzYqq-o8SRTWyO\u003dJ6gBnSkZa\u003dQYuEiBNuBEVndVsVYcExg@mail.gmail.com/\nLink: https://lore.kernel.org/bpf/20261106195730.2623973-2-ihor.solodrai@linux.dev\n" }, { "commit": "2210e69db7217bca218693fde5ed45bcbe8ff519", "tree": "295351feb295262e5c26a29abdac8c69db575ed4", "parents": [ "3e18218484126afb9da722080659c038cb2256ab" ], "author": { "name": "Ihor Solodrai", "email": "ihor.solodrai@linux.dev", "time": "Fri Nov 06 12:57:28 2026 -0700" }, "committer": { "name": "Andrii Nakryiko", "email": "andrii@kernel.org", "time": "Fri Nov 06 16:38:18 2026 -0800" }, "message": "Revert \"libbpf: Fix use-after-free in btf__add_type\"\n\nThis reverts commit 9abe2c42ecab6c86b54838d2d645ca2e10204606.\n\nThe commit made btf_rewrite_str() make every base of the destination\nmodifiable before taking a pointer to the source string, because\nlooking the string up in a base made it modifiable and freed its raw\ndata. Since commit efeb5ab5753d (\"libbpf: Look up BTF strings without\nmaking BTF modifiable\"), the lookup leaves the raw data in place, so\nthe pointer stays valid.\n\nMaking a base modifiable fails for BTF with unknown header-extension\nbytes. With the loop in place, btf__add_type() and btf__add_btf() into\na split over such a base fail with -EOPNOTSUPP, and so does bpftool\nwhen it merges module BTFs over it:\n\n $ bpftool -B base.btf btf dump file mod1.btf file mod2.btf format raw\n Error: failed to merge BTF from mod1.btf: Operation not supported\n\nSuggested-by: BPF CI bot \u003cbot+bpf-ci@kernel.org\u003e\nSigned-off-by: Ihor Solodrai \u003cihor.solodrai@linux.dev\u003e\nSigned-off-by: Andrii Nakryiko \u003candrii@kernel.org\u003e\nLink: https://lore.kernel.org/bpf/e0df4fa9e17514c79de41ee9fd2eb610d43a95741fb994db160b35fd488f054a@mail.kernel.org/\nLink: https://lore.kernel.org/bpf/20261106195730.2623973-1-ihor.solodrai@linux.dev\n" }, { "commit": "3e18218484126afb9da722080659c038cb2256ab", "tree": "5624a7d63f6d88d38358213aec69f3be9afa7140", "parents": [ "fd4cf5e9d154cee3a2a0d6a1a71f122c9f1660f1", "0eaeda0d2075fc7c55c55dc9b5311566aa6f193e" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Fri Nov 06 17:40:58 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Fri Nov 06 17:40:58 2026 +0000" }, "message": "Merge branch \u0027bpf-disable-private-stacks-for-uprobe-programs\u0027\n\nJiri Olsa says:\n\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\nbpf: Disable private stacks for uprobe programs\n\nhi,\nuprobe programs can be preempted and re-entered on the same CPU. Since\nthe private stack is shared per program and CPU, a nested invocation can\noverwrite the preempted invocation\u0027s stack.\n\nThis patch disables private stacks for KPROBE programs except kprobe multi\nand kprobe-session programs, identified by the BPF_TRACE_KPROBE_MULTI and\nBPF_TRACE_KPROBE_SESSION attach types. Standard kprobes lack an attach type,\nand uprobes use different attach types or none, so they run without private\nstacks.\n\nIt also rejects multi and session programs through the perf-event attach\npath, which lacks their required run context and could allow a uprobe to\nreach a private-stack tail-call target [1].\n\nthanks,\njirka\n\nv1: https://lore.kernel.org/bpf/20261103093400.112178-1-jolsa@kernel.org/\n\nv2 changes:\n- drop the BPF_TRACE_UPROBE attach type and fail perf event kprobe\n attach for kprobe-multi/uprobe-multi [Alexei]\n\n[1] https://lore.kernel.org/bpf/aus-b8Lo2oCw_cGd@krava/\n---\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n\nLink: https://patch.msgid.link/20261106164043.546879-1-jolsa@kernel.org\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\n" }, { "commit": "0eaeda0d2075fc7c55c55dc9b5311566aa6f193e", "tree": "5624a7d63f6d88d38358213aec69f3be9afa7140", "parents": [ "6a6beb501ee74e8cfdd6f620f0a1d1f97cae245e" ], "author": { "name": "Jiri Olsa", "email": "jolsa@kernel.org", "time": "Fri Nov 06 17:40:43 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Fri Nov 06 17:40:58 2026 +0000" }, "message": "bpf: Disable private stacks for untagged kprobe programs\n\nUprobe programs can be preempted and re-entered on the same CPU. Since\nthe private stack is shared per program and CPU, another invocation can\noverwrite the preempted invocation\u0027s stack.\n\nPrograms without a multi or session attach type may be standard kprobes\nor uprobes. Disable private stacks for them, and retain private stacks\nonly for kprobe multi and session programs, which have attach types that\nidentify them as kprobes.\n\nUpdate verifier tests that rely on private stacks to use kprobe.multi,\nand add coverage that untagged kprobe and uprobe programs do not use\nprivate stacks.\n\nSigned-off-by: Jiri Olsa \u003cjolsa@kernel.org\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261106164043.546879-3-jolsa@kernel.org\n" }, { "commit": "6a6beb501ee74e8cfdd6f620f0a1d1f97cae245e", "tree": "55df40bd6b33b41235e34443b2a7381f39cf7d29", "parents": [ "fd4cf5e9d154cee3a2a0d6a1a71f122c9f1660f1" ], "author": { "name": "Jiri Olsa", "email": "jolsa@kernel.org", "time": "Fri Nov 06 17:40:42 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Fri Nov 06 17:40:58 2026 +0000" }, "message": "bpf: Reject multi kprobe programs in perf event attach\n\nPERF_EVENT_IOC_SET_BPF allows attaching multi and session kprobe or\nuprobe programs through the standard perf event path. These programs\nrequire attach-specific run context, which this path does not provide.\nAttaching them can also let a uprobe reach a private-stack program\nthrough a tail call.\n\nReject multi and session programs in __perf_event_set_bpf_prog().\nKeep the existing sleepable-program check for standard kprobe and\nuprobe programs.\n\nSuggested-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nSigned-off-by: Jiri Olsa \u003cjolsa@kernel.org\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261106164043.546879-2-jolsa@kernel.org\n" }, { "commit": "fd4cf5e9d154cee3a2a0d6a1a71f122c9f1660f1", "tree": "e474c7a188a799085b10b27139e8b9263f1dd9a0", "parents": [ "87eddc739d20b466881e4c5cdd2ddf465a5debfd", "5b1e4e8b466480ee93093b5fc2763d7c00dfb1a6" ], "author": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Fri Nov 06 02:41:25 2026 +0000" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Fri Nov 06 02:41:25 2026 +0000" }, "message": "Merge branch \u0027bpf-add-user-memory-kfuncs\u0027\n\nJiri Olsa says:\n\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\nbpf: Add user memory kfuncs\n\nhi,\nBPF programs have no supported interface for creating or removing private\nanonymous mappings in the current task. This limits use cases that need normal\nor executable memory in a live process, such as replacing a function or\nchanging environment variables.\n\nAlthough bpf_probe_write_user() can write to user memory, it disables page\nfaults during the copy and therefore cannot handle memory that needs to be\nfaulted in.\n\nThis series adds three sleepable kfuncs for those operations:\n\n - bpf_user_anon_mmap(len, prot) creates a private anonymous mapping in the\n current task and returns its address. The requested protections can include\n execute permission.\n\n - bpf_copy_to_user(dst, src, len, flags) copies data into the current task’s\n address space, handles page faults, and reports copy errors.\n\n - bpf_user_munmap(addr, len) removes a mapping.\n\nTogether, the kfuncs provide a small interface for allocating, populating,\nand removing memory:\n\n addr \u003d bpf_user_anon_mmap(len, prot);\n ret \u003d bpf_copy_to_user((void *)addr, src, len, flags);\n bpf_user_munmap(addr, len);\n\nThis interface lets a BPF program perform the operations in the current task’s\naddress space without changing bpf_probe_write_user()’s fault behavior or\nintroducing a separate mapping abstraction.\n\nthanks,\njirka\n\nrfc: https://lore.kernel.org/bpf/20261021195759.119421-1-jolsa@kernel.org/\nv1: https://lore.kernel.org/bpf/20261029212551.56964-1-jolsa@kernel.org/\nv2: https://lore.kernel.org/bpf/20261103075916.100050-1-jolsa@kernel.org/\n\nv3 changes:\n- use Alexei\u0027s change for checking the const [Aleexi]\n- drop ia32 support/hack for vm_mmap [Alexei]\n- remove leftover srcptr suffix in kfunc declaration\n- drop extra verifier test for non-sleepable kprobe\n\nv2 changes:\n- infer read-only from constness of a pointer instead of srcptr\n argument suffix [Andrii]\n- rename bpf_user_mmap to bpf_user_anon_mmap [Andrii]\n- use arch_validate_prot to validate prot argument in mmap\n- add the x86 compat mmap workaround\n- assorted small changes\n\nv1 changes:\n- follow vm_mmap/vm_munmap design suggested by Alexei\n- allow user space write only to current process, because we don\u0027t\n have remote task use case and it simplifies security checks\n- many changes in tests\n---\n\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\u003d\n\nLink: https://patch.msgid.link/20261105102343.311331-1-jolsa@kernel.org\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\n" }, { "commit": "5b1e4e8b466480ee93093b5fc2763d7c00dfb1a6", "tree": "e474c7a188a799085b10b27139e8b9263f1dd9a0", "parents": [ "4058fb465383d29f60a99e4db6b827073466a3a7" ], "author": { "name": "Jiri Olsa", "email": "jolsa@kernel.org", "time": "Thu Nov 05 11:23:42 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Fri Nov 06 02:41:24 2026 +0000" }, "message": "selftests/bpf: Test user memory kfunc errors\n\nTest invalid copy arguments, zero-length mapping operations, partial copy\nfaults, and copying to read-only mappings. Verify that a failed unmap\nleaves the mapping intact, and that non-sleepable programs and programs\nwithout CAP_SYS_ADMIN cannot call bpf_user_anon_mmap.\n\nSigned-off-by: Jiri Olsa \u003cjolsa@kernel.org\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261105102343.311331-9-jolsa@kernel.org\n" }, { "commit": "4058fb465383d29f60a99e4db6b827073466a3a7", "tree": "f8604b5e3b66b67ed50a1aca1fe164aad889791d", "parents": [ "2c9e3611035aacc9c3526b96bfd20161abc5ec91" ], "author": { "name": "Jiri Olsa", "email": "jolsa@kernel.org", "time": "Thu Nov 05 11:23:41 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Fri Nov 06 02:41:24 2026 +0000" }, "message": "selftests/bpf: Test bpf_copy_to_user kfunc\n\nTest that bpf_copy_to_user can fault in a paged-out page and write to a\nread-only mapping. Also verify that a partial copy crossing into an unmapped\npage returns -EFAULT while leaving the copied byte in place.\n\nSigned-off-by: Jiri Olsa \u003cjolsa@kernel.org\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261105102343.311331-8-jolsa@kernel.org\n" }, { "commit": "2c9e3611035aacc9c3526b96bfd20161abc5ec91", "tree": "f50ebefac64bd6bbba4d57ea3805bc1a08bf957a", "parents": [ "3c670f43767adf70d3c54abac811b883bbe11cc4" ], "author": { "name": "Jiri Olsa", "email": "jolsa@kernel.org", "time": "Thu Nov 05 11:23:40 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Fri Nov 06 02:41:24 2026 +0000" }, "message": "selftests/bpf: Test user memory page exec\n\nUse bpf_copy_to_user from a uprobe to write architecture-specific\ninstructions into user memory, then execute them on x86-64 and arm64.\n\nTest execution from a mapping created with read and execute permissions,\nand from individual pages made executable with mprotect.\n\nSigned-off-by: Jiri Olsa \u003cjolsa@kernel.org\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261105102343.311331-7-jolsa@kernel.org\n" }, { "commit": "3c670f43767adf70d3c54abac811b883bbe11cc4", "tree": "01c62bcf378d1fcf8bfff4b23b069d2e740e10ba", "parents": [ "2af3f3c9be70543e2b9911acc1dce9b5a6dd0cf7" ], "author": { "name": "Jiri Olsa", "email": "jolsa@kernel.org", "time": "Thu Nov 05 11:23:39 2026 +0100" }, "committer": { "name": "Alexei Starovoitov", "email": "ast@kernel.org", "time": "Fri Nov 06 02:41:24 2026 +0000" }, "message": "selftests/bpf: Test user memory mmap kfuncs\n\nAdd BPF selftests for bpf_user_anon_mmap and bpf_user_munmap from\na sleepable uprobe. Check that created mappings have the requested\npermissions and that unmapped addresses are no longer mapped.\n\nSigned-off-by: Jiri Olsa \u003cjolsa@kernel.org\u003e\nSigned-off-by: Alexei Starovoitov \u003cast@kernel.org\u003e\nLink: https://patch.msgid.link/20261105102343.311331-6-jolsa@kernel.org\n" } ], "next": "2af3f3c9be70543e2b9911acc1dce9b5a6dd0cf7" }