summaryrefslogtreecommitdiff
path: root/kernel/bpf/flow.c
AgeCommit message (Collapse)Author
4 daysbpf: Make the operations on a scalar take struct scalarAlexei Starovoitov
Datadog's socket__http2_headers_parser computes p = h + (n & 255) * 20 and compares n with 2 afterwards. The jump refines n. The range of p follows from its expression: an and, a multiplication, an addition. Scalar evolution knows the expression and is going to evaluate it with the transfer functions of the main pass. The values in between are in no register. scalar_add(), scalar_union() and a few more functions take a struct scalar. The others read and write the same five members and take a struct bpf_reg_state. Code that has a value and no register makes up a register of 80 bytes: BPF_NEG copies its operand to env->fake_reg[0], adjust_scalar_min_max_vals() gets a copy of the source register, refine_linked_regs() copies a register to add a constant. Make 61 more functions take a struct scalar: reg_bounds_sync() with its callees, the checks of the invariants, the casts, all ALU operations, the widening, the refinement by a jump. In them, and in the switch of adjust_scalar_min_max_vals(), which calls the ALU operations: struct bpf_reg_state * struct scalar * reg_smin(reg) cnum64_smin(s->r64) reg_set_srange64(reg, a, b) s->r64 = cnum64_from_srange(a, b) scalar_of(reg) s reg, dst_reg, src_reg s, dst, src reg1, reg2 a, b 'reg' in the function's name 'scalar' and the same for the other 7 getters and 3 setters. The names are those of scalar_add() and scalar_zext32(). bpf_reg_widen_range() becomes scalar_widen(). What is only read becomes const. A caller with a register passes scalar_of(reg). reg_bounds_sync() is called 15 times with a register and reg_is_empty() 8 times: the two stay, as one line each. reg_step_reset() was such a line. 3 of its 21 calls still have a register, so it goes. What is not a substitution: - An and, or, xor that gives a constant and BPF_NEG call __mark_reg_known(). It clears the ids and the union and calls scalar_set_const(). They call scalar_set_const() now: their register is a SCALAR_VALUE, there is nothing to clear. - regs_refine_cond_op() and BPF_UHMUL, BPF_SHMUL in the switch call is_reg_const(), which tests the type. Both callers of the first pass scalars only, the operands of the switch are scalars. scalar_is_const() is the rest of is_reg_const(). - BPF_NEG keeps its operand in a struct scalar on the stack. The source operand of adjust_scalar_min_max_vals(), still passed by value, and of maybe_fork_scalars() is a struct scalar. is_scalar_branch_taken() keeps its registers: it ends in simulate_both_branches_taken(), which refines four registers of env and not the arguments. reg_bounds_sanity_check() and range_within() are only called with a register. No functional change. Suggested-by: Eduard Zingerman <eddyz87@gmail.com> Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261112155337.1040699-5-alexei.starovoitov@gmail.com
5 daysbpf: Add struct scalarAlexei Starovoitov
What the verifier knows about a value is five members of struct bpf_reg_state: var_off, r64, r32, base and step. Code that computes with values and has no register for them copies some of the five, or makes up a register. scev.c has struct scev_value and struct bounds, each with its own addition. verifier.c fills in fake registers of 80 bytes to add a constant. Give the five members a type. struct scalar is the reduced product of known bits, a range, a range of the low 32 bits and a congruence. It is an anonymous member of struct bpf_reg_state: reg->r64 stays reg->r64 and no user changes. scalar_of(reg) points to it. The five members have 44 bytes, a struct of them has 48. Where they are now it would grow a register from 80 to 88 bytes and put 4 bytes of padding into what regsafe() compares with memcmp(). So id takes the place of 'u32 unused' and the scalar is the last member: 0 type 0 type 4 unused 4 id 8 union, 16 bytes 8 union, 16 bytes 24 var_off .. step 24 parent_id 68 id 28 map_uid 72 parent_id 32 struct scalar 76 map_uid 76 padding 80 80 11 lines depend on the old order: they compare, hash or clear a register up to offsetof(struct bpf_reg_state, var_off) or up to its id. Now they name what they mean. reg_fixed_part_equal() and reg_value_equal() move from join.c to the header, range_equal() of join.c is scalar_equal(). refine_live_branch() compares whole registers with memcmp(), which would read the padding. It calls reg_value_equal() now. flow_shape_ptr() hashes the type, the union and the scalar one after the other. Its hash values change. They are only compared with each other. The union is named by its member raw: two unsigned long, half of the union on a 32-bit kernel. They become u64, and a static_assert() says that raw ends where the union ends. No functional change. Suggested-by: Eduard Zingerman <eddyz87@gmail.com> Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261112000836.3138846-4-alexei.starovoitov@gmail.com
5 daysbpf: Stop assigning ids to scalarsAlexei Starovoitov
A removal. Nothing learns anything about a prog from a scalar id any more. The code that is left only maintains the ids. Stop assigning them. No verdict changes, the number of states goes down. r2 = r1 r1 and r2 get id 7 r2 += 4 id 7 | BPF_ADD_CONST64, delta 4 *(u64 *)(r10 - 8) = r1 fp-8 has id 7 if r1 > 100 goto .. all three were refined A scalar id in a state said that scalars hold the same value, or differ by delta. Each insn that moves or changes a scalar had to assign, keep or clear it. regsafe() and the join of states had to map the ids of one state to those of the other. What does that job now: - After a conditional jump refine_linked_regs() refines the linked registers of the jump: the live registers and stack slots that are a tested register + a constant on every path to the jump. Scalar evolution computes them before the main pass. - Memory behind a pointer is a linked register too: the stack slot of a caller that the tested register was loaded from is refined. - Scalar evolution compares expressions to find a copy of an induction variable: const_diff_at_header(). - flow_join_makes_up() recognizes copies of a scalar by their ranges. Remove assign_scalar_id_before_mov(), BPF_ADD_CONST and delta in adjust_reg_min_max_vals(), the ids that a spill and a fill keep or clear, the callers of clear_scalar_id(), bpf_clear_singular_ids() and its caller. get_reg_width() has no user left. The ids of pointers, references, dynptrs and iterators stay. States that differed in scalar ids only are one state now. veristat over the selftests, Cilium, sched_ext, katran, bpfjailer and programs in Rust: 2.3 % fewer insns and 3.7 % fewer states, in Rust 5.3 % and 6.3 %. No verdict changes. The kernel spends 0.7 % fewer instructions on loading the C programs and 4.9 % fewer on those in Rust. Tests that change: - Log lines that pin 'id=' of a scalar lose it. The id of a packet pointer is smaller: ids are assigned less often. - two_old_ids_one_cur_id maps the scalar ids of two states: removed. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261111164557.2659679-25-alexei.starovoitov@gmail.com
5 daysbpf: Recognize copies of a scalar by their ranges in flow_join_makes_up()Alexei Starovoitov
A prerequisite of the removal of scalar ids. flow_join_makes_up() is the last code that learns something about the prog from them: which registers and stack slots hold copies of a scalar. Recognize the copies by their ranges. The function is a heuristic that decides which states are joined. So this patch is about the number of states. Soundness does not depend on it. err = update(); ret = err < 0 ? DROP : 0; .. if (err < 0) goto out; .. if (ret < 0) .. The states (err >= 0, ret = 0) and (err < 0, ret = DROP) get to a join point before the jumps. Their join loses the correlation of err and ret: it has err < 0 with ret = 0. So two states stay apart if two scalars that later jumps test each have disjoint ranges in the two states, as err and ret do. Copies of a scalar are treated as one scalar there. A jump that tests one of them refines the others, so their join makes up nothing, and compilers keep a value in a register and in stack slots at the same time. Copies are recognized by their id, in one of the two states: if (one && (!id || id != (ra->id & ~BPF_ADD_CONST))) return true; If every copy is a scalar of its own, too many states stay apart. The init prog of a sched_ext scheduler in Rust goes from 36 to 512 states at one insn and takes twice as long to load. At 512 flow_has_room() is false, and states are joined by force. Copies have the same range and tnum, in each of the two states. Treat scalars with that property as copies. Two scalars that are not copies can have it too. Then two states are joined that stayed apart. veristat over the selftests, Cilium, sched_ext, katran, bpfjailer and programs in Rust: no verdict changes, 199 of 32913 progs move, by 0.01 % of the insns in all. The scheduler stays at 36 states. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261111164557.2659679-24-alexei.starovoitov@gmail.com
8 daysbpf: Keep one basic block in the level 1 log and print the way to itAlexei Starovoitov
bpf(2) shows how to load a prog: .log_level = 1 and a static buffer. Cilium's bpf_lxc/tail_ipv4_ct_egress loaded that way with 64K. Now it gets -ENOSPC, like 2097 progs of the selftests, Cilium, scx, katran, bpfjailer and Rust crates. At level 1 each insn is printed when it is verified. The verifier used to follow one path at a time. At a conditional jump push_stack() put the other branch aside and noted the end of the log. When the path was done pop_stack() took the branch and moved the log back: push_stack(): elem->log_pos = env->log.end_pos; pop_stack(): bpf_vlog_reset(&env->log, head->log_pos); So the log was the path from the first insn to the current one. It never got larger than the longest path, and when a prog was rejected it was the path to the error. Now there are no paths. Basic blocks are verified in the order of the control flow graph, and the states that get to a block are joined. What push_stack() puts aside goes to the block that it is for. pop_stack() and log_pos are gone, and nothing else moves the log back while a function is verified. Each block adds its text each time it is verified: 4057 insns and 774446 bytes for tail_ipv4_ct_egress, whose longest path had 51434. The text is dropped when the prog turns out to be safe. That doesn't help: bpf_vlog_finalize() compares the buffer with len_max, the largest size that the log ever had. And the log of a rejected prog is not the path to the error any more. It has all blocks, both arms of each branch, in the order in which they were verified. The old log cannot come back as it was. The state at the start of a block is the join of all that got there: no path leads to it. Move the log back in front of each basic block, so that it holds one block at a time. When a block is rejected print the way to it from what the verifier holds at that time. It keeps the states where ways meet. Such a state knows the edge that it came by, after a join the edge that changed it last: the edge that brought the bad value. There may be several states at an insn, so a state gets a u32 that tells which kept state it comes from. A block in between has one predecessor. The block that fails is in the log already: stash it, print the way, append it. Nothing is verified twice. if (skb->mark == 1) i = skb->len & 63; else if (skb->mark == 2) i = skb->priority; else i = 7; if (skb->protocol == 8) v[0] = 1; return v[i]; from -1 to 0: R1=ctx() R10=fp0 ... 10: (16) if w2 == 0x2 goto pc+5 ; i = skb->priority; @ pick.bpf.c:22 16: (61) r1 = *(u32 *)(r6 +32) from 16 to 17: R0=map_value(map=m,ks=4,vs=64) R1=scalar(smin=0,smax=.. ; if (skb->protocol == 8) @ pick.bpf.c:25 17: (61) r2 = *(u32 *)(r6 +16) 18: (56) if w2 != 0x8 goto pc+2 21: R0=map_value(map=m,ks=4,vs=64) R1=scalar(smin=0,smax=umax=0xfff.. ; return v[i]; @ pick.bpf.c:27 21: (0f) r0 += r1 ; R0=map_value(map=m,ks=4,vs=64,smin=.. 22: (71) r7 = *(u8 *)(r0 +0) R0 unbounded memory access, make sure to bounds check any such access A block is on the way once, so the way goes around a loop once. Where a block would come again the way goes on from its dominator: all that gets into the loop goes through it. The earlier rounds are left out, what is in front of the loop is not. A function that is verified in the frames of its caller is on the way once too, for its last call. Its dominators end at its first insn, so the way begins where the call before that one returns. A signal ends the print. A round that do_check_all() drops gets no way, so bpf_flow_loops_lost_bound() can be asked twice now. Level 1 doesn't show the states behind the insns of the way and the bodies of subprogs that are verified on their own. Level 2 has them. It is not changed, and six tests that look at such a state get __log_level(2), with the five others that come out of the same macros. log_true_size at level 1 one path all blocks this patch bpf_lxc/tail_ipv4_ct_egress 51434 774446 7652 bpf_host/cil_to_netdev 101212 1789015 9778 katran/balancer_ingress 103567 3668559 22603 progs with -ENOSPC at 64K 2841 5503 45 the builds of a prog as one 435 1018 23 A prog that loads pays two stores of a u32 per state: ftrace sees no call of bpf_flow_print_way(). The longest way, 713 lines, takes 0.4 ms. Fixes: 5395aa9bbeb5 ("bpf: Verify programs as a fixpoint over the control flow graph") Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261108053937.4134138-3-alexei.starovoitov@gmail.com
9 daysbpf: A join must leave the cookie of bpf_throw() aloneAlexei Starovoitov
An LSM prog without an exception callback: err = policy(file); /* 1: no rule, 2: audit, 0, -EPERM, -EACCES */ count(a); count(b); count(c); if (err == -EPERM || err == -EACCES) bpf_throw(err); return 0; The compiler decides the 'if' where err is set, and keeps a flag. All paths meet, then the flag is tested. In the join err is [-13, 2]: At program exit the register R1 has .. should have been in [-4095, 0] The prog is valid, and it loaded when the verifier followed each path. It has the shape of cil_sock4_connect() of Cilium, with bpf_throw() in place of bpf_set_retval(). Without an exception callback the prog returns the cookie. Thus check_kfunc_call() compares r1 of bpf_throw() with the range of the prog type, like r0 at exit. That check is not in check_func_arg() either. Add r1 to bpf_call_checked_arg_regs() by hand, like r1 of bpf_set_retval(). States in which the flag and the cookie differ are not joined then. The same table tells whether something looks at a number that a short loop counts. This prog loads too: for (i = 0; i < 3; i++) if (hit(i)) n++; bpf_throw(n); /* cgroup_skb/egress takes [0, 3] */ Fixes: af6bda3802af ("bpf: Tell which arguments of a call a join must leave alone") Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261107170306.2831028-9-alexei.starovoitov@gmail.com
10 daysbpf: Find where the jumps of a loop stop a numberAlexei Starovoitov
bpf_for(i, 0, 100) bpf_for(j, 0, 100) if (n < 8) v->a[n++] = j; return v->a[n]; while (off < 8000) { l = v->big[off]; if (!l) break; off += l; } n and off grow by what the data say, so there is no formula for them. Widening moves the bound that grows to a fixed stop: 0, S32_MAX, U32_MAX or S64_MAX. n is [0, S32_MAX] at the loop head. The jump limits it in the loop, nothing limits it after the loop. clang tests off at the end of the loop, so nothing limits it at the load. Both loaded before states were joined: R6 unbounded memory access, make sure to bounds check any such access The jumps of the loop tell where the bound stops. Examine one iteration before the main pass, from the head to the back edges, and write what is in a register or a stack slot as 'root + constant'. A root is the value at the head, or a value that the iteration makes. A jump that compares 'root + c' with a constant limits the root on each edge that stays in the loop. What returns to the head is 'root + c' again, and the limits give a stop: 8 and 7999 here. bpf_reg_widen_range() takes the nearest of all stops. A stop is a guess. What returns to the head next is compared with the widened state as always. A wrong stop costs one more pass through the loop. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261107033758.1547725-32-alexei.starovoitov@gmail.com
10 daysbpf: Keep the first iteration of a counted loop apartAlexei Starovoitov
idx = 0; for (i = 0; i < 100000; i++) idx = table[idx]; /* u8 table[256] */ Scalar evolution has the count and no formula for idx. If something looks at such a register, like the load here, the verifier goes through the iterations one by one. 100000 iterations are too many for that. Then what returns to the loop head is joined with the 0 and widened: the bound that grew goes to a fixed stop, and a prog that loaded before is rejected: R0 unbounded memory access, make sure to bounds check any such access But nothing that idx is made from is what a register had at the loop head. It is a byte in each iteration. Only the first one differs: it has the 0 from the entry. Verify the first iteration with the state that enters the loop. The state that returns to the loop head has idx in [0, 255]. Give its induction variables the ranges that follow from the count, as at the entry. It stands for all other iterations. What returns next must be within it, otherwise the two are joined like at each loop head. The loop takes 12 insns. expr_is_fresh() finds the registers, bpf_loop_iters.fresh_regs has them, loop_stack_entry.first marks a state that is in the first iteration. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261107033758.1547725-30-alexei.starovoitov@gmail.com
10 daysbpf: Verify programs as a fixpoint over the control flow graphAlexei Starovoitov
for i in 0..n { v.push(i * i); } Test vec_push_pop of rust-bpf: "The sequence of 8193 jumps is too complex." The verifier follows each path from the first insn to exit, and each branch can double the number of paths. 123 tests of rust-bpf hit this limit or 1M insns. C progs are cut until they fit. Do not follow paths. Where two paths meet, make one state that covers both, a join: r1=1 and r1=5 give r1=[1,5]. What is safe for the join is safe for both. Repeat until no state changes. The work depends on the size of the prog, not on the number of paths: 1761 insns with this patch, and 120 of the 123 load. do_check() takes the next new state from flow.c and checks one basic block. The check of an insn is the same. What user space sees: - The limits of 1M processed insns and 8192 jumps are gone, from bpf_design_QA.rst too. flow.c limits states, for a prog of N insns: 1024 at an insn "more than 1024 states that cannot be joined" 16 * N + 4096 at a time, 256 * N + 64K in all "too many states" - "infinite loop detected" is gone: 111 of the 225 progs of the schedulers of rust-bpf. A fixpoint shows that each iteration is safe, not that the loop ends: counted, or walked to its end nothing is added each iteration has may_goto or bpf_iter_*_next() nothing is added no exit rejected all other loops may_goto - An added may_goto is a new edge. check_loop_guard() verifies it. It goes to 'r0 = 0; exit': the probe loop of hashbrown exits only with a bucket, and the code after the loop uses it: "R6 invalid mem access 'scalar'". Until these insns are added the last exit stands for them. With GCC that can be dead code, 'if (debug) return ..': r0 is marked as live there. If the frame holds more than at its entry, or is a subprog that cannot unwind, may_goto goes to the exit of the loop: the prog releases there what it holds. From the head of a loop that is no edge of the prog. In glob_match() of arena_strsearch without cond_break only the body sets r0 for the 'exit' behind the loop: "R0 !read_ok". A subprog that holds nothing is left with 'r0 = 0; exit' then. Its caller is verified with 0. - A walk goes on while each iteration decides a jump that leaves the loop. A jump that is decided only because states are kept apart by a flag does not count: it repeats the jump that set the flag, which went both ways. lexical_numbers of rust-bpf: 41610 insns, 98980 if it counts. - 1 and 2 are joined at exit, and a test for 'r0 is 2 or 3' misses [1, 2]. Thus a cgroup_skb prog whose r0 can be 2 or 3 attaches to egress only. - Static subprogs and recursion are as before. Pruning, jmp_history and precision marks are only disabled here. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261107033758.1547725-20-alexei.starovoitov@gmail.com
10 daysbpf: Move states along edges, into loops and subprogs and out of themAlexei Starovoitov
Selftest test_verif_scale1 has these lines 90 times. jhash() is static: ptr = data + i; if (ptr + nh_off > data_end) break; ctx->tc_index = jhash(ptr, nh_off, ctx->cb[0] + i++); The 90th call is reached with i = 0 .. 89, in 90 states. All calls: 4095. jhash() sees one of 90 pointers. If a state in jhash() has the frames of its callers, as today, states of different calls have no join: "more than 1024 states that cannot be joined at insn 903". Thus a state in a static subprog has one frame, and the caller's state waits at the call: bpf_flow_call() saves the caller. The entry state goes to the set at the first insn of the subprog, like any state. bpf_flow_exit() a state at exit goes to all calls that wait for its entry state. The exit states are a set too. When the merge drops or joins an entry state, its calls wait for the state that took its place, and flow_do_united() gives them its exit states. 4005 of the 4095 calls end so: 50765 insns, today 530362. Else the limit stops this test, 100 progs of the schedulers of rust-bpf and 124 of its tests. The exit states of an entry are joined like the states at an insn, and the joins must end. Thus an exit state that was joined more than 16 times is widened. The entry and the exits of a recursive subprog are widened at once. Loops. Scalar evolution derives the count and the ranges of a loop from the state that enters it. Thus the states that enter are a set of their own. A copy of each new one, with these ranges, goes to the set at the head. When a walk ends before the loop does, one state stands for the rest: flow_end_walk() joins, with widening, the state that came back to the head and the state one iteration before. They differ in what the loop changes. There is no join if the iteration set a register for the first time, or changed a constant that becomes an offset of the stack or of a pointer. bpf_flow_deliver() sends a state along an edge, bpf_flow_next() gives the next new state. A state that gets to bpf_loop() gets its number there: what the callback comes back with is widened with the state that it comes from. An added may_goto is an edge that the prog does not have: bpf_flow_guard_edge() sends a state along it only if the loop has may_goto by now. Else it drops the state and notes that. If the loop gets may_goto later, the prog is verified again. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261107033758.1547725-16-alexei.starovoitov@gmail.com
10 daysbpf: Merge the state that arrives into the set at an insnAlexei Starovoitov
scx_flow, flow_dispatch() is a row of blocks like this one: if (nq0 > 0) { node_moved = flow_move_one_hint(node_dsq, cpu, &visits, nq0); if (node_moved > left) node_moved = left; left -= node_moved; } Each way through a block leaves other ranges in left, visits, node_moved. No check behind the block depends on the way. Today's verifier follows all paths: 70716 insns for a prog of 1117. With one state where the ways meet it takes 3127. flow_merge() puts a state S into the set at an insn: a state of the set covers S ? ------ yes --> drop S | no S covers a state T of the set ? ---- yes --> drop T | S has a join with a state T, ------- yes --> drop T, S = join(S, T), and no rule refuses it ? start again | no add S to the set: it is new, the verifier goes on from it A state is dropped only if a state of the set covers it. Thus the verified states cover each execution of the prog. S can come around a cycle: to the head of a loop, to the first insn of a recursive subprog, from a callback to its helper. There a bound can grow by one step each time: i=[0,1], [0,2], ... Thus the join is a widening: it gives up the bound that grew. S and T differ in what the cycle changes, so the rules that refuse a join are off. These stay on: - A constant that becomes a stack offset: bt_print() of scx has 'stack[depth++] = ind + 1' and 'ind = stack[depth]' in bpf_for(). - A live register that only S has set. In clang 18's code of 'bpf_for(..) { if (..) continue; last = rnd(); found = true; }' and 'if (found) use(last);' the join has no 'last': "R7 !read_ok". - The calls of the callback of bpf_loop(N <= 8). What other callbacks come back with is joined 4 times, then widened. All that holds only if S comes from T: ret = 0; if (file->f_flags & O_TRUNC) { denied++; ret = -EPERM; } bpf_for(i, 0, 100) { sum += a[i]; } total = sum; return ret; Two states enter the loop. Next to -EPERM the 0 that comes around looks like a number that grew, and an LSM prog is rejected: "R0 has smin=0 smax=4294967295 should have been in [-4095, 0]". Thus a state that enters a loop, or gets to bpf_loop(), has a number, and so has what becomes of it. S is widened with a T of its number only. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261107033758.1547725-15-alexei.starovoitov@gmail.com
10 daysbpf: Decide which states are not joinedAlexei Starovoitov
Cilium, nat.h, in tail_handle_snat_fwd_ipv4: if (ret < 0) ..; to_sport = state->to_sport; (ret=-155, state=map_value_or_null) and (ret=0, state=map_value) meet in front of that. Numbers always have a join. But ret=[-155, 0] with map_value_or_null has ret=0 without state, as no path has. It passes the jump: "R3 invalid mem access 'map_value_or_null'". A join must not make up what a later check can see. A number is tested if a later jump compares it with a constant, or the verifier checks its range at a call or at exit. States that have a join stay apart if they differ in: - A tested number, and the ranges leave a gap: -155 and 0, not 0 and 1. 113 progs of Cilium, profiler3 and test_seg6_loop without alu32. - Two tested numbers, each without a common value: (err >= 0, ret=0) and (err < 0, ret=DROP). The join has err < 0 with ret=0. - A flag, 0 and 1, that a jump in this basic block or the next one tests: 'ok = i < 64 && v->in[i] == 2; if (v->x == 7) v->n++; if (ok) v->w[i] = 1;' clang keeps ok in a register. (ok=0, i>63), (ok=1, i<=63), (ok=0, i<=63) meet. The join has ok=1 with i>63: "R0 unbounded memory access". - A register that only one of them sets. scx_layered/layered_runnable: 'scoped_guard(rcu) { if (...) return result; nsid = ...; }' meets at the unlock with a flag of the compiler, then reads nsid: "R7 !read_ok". - Two tested numbers, (0, x) and (y, 0). xdp_synproxy_kern and test_tcp_custom_syncookie: 'if (hdr->ipv4) ... else if (hdr->ipv6) ...' after the packet changed: "R1 type=scalar expected=fp, pkt, ...". - A constant that becomes a stack offset. bt_print(), 5 selftests of scx: 'if (... || depth >= BT_MAXLVL_PRINT) return 0; ind = stack[depth];' A copy of depth is tested: "invalid variable-offset read from stack". - A constant that is added to a pointer. katran/tcdecapinfo, 20 or 40 in 'if (data + hdr_len + inner_ip_offset > data_end)'. With [20, 40] the jump says nothing about data + hdr_len: "invalid access to packet". - A constant that a kfunc or helper must know. One call is made of 'c ? bpf_rdonly_cast(0, id) : bpf_rdonly_cast(0, 0)' in mem_rdonly_untrusted/mixed_mem_type: "R2 must be a known constant". - The number of calls of the callback of bpf_loop(N, ...), N <= 8: 'bpf_loop(1, cb, &ctx, 0); return choice_arr[ctx.i];' in verifier_iterating_callbacks: "invalid access to map value". The rules only refuse joins: no unsafe prog loads because of them. They cost states: the first one 10 % of Cilium's insns, K flags 2^K states. Thus most hold only while each limit is less than half used: flow_has_room(). The shape of a state is a filter in front of all that: hashes of its calls and loops, of what it holds, of the places, objects and constant offsets of its pointers. The load of test_cls_redirect_subprogs, 301 states at an insn, takes three times as long without the shape. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261107033758.1547725-14-alexei.starovoitov@gmail.com
10 daysbpf: Compare states of different iterations of a loopAlexei Starovoitov
Selftest loop1, nested_loops(): for (j = 0; j < 300; j++) for (i = 0; i < j; i++) { ... sum += i * m; } Scalar evolution counts both loops, but has no closed form for sum, and the verifier checks sum: it is the return value. It walks such a loop: it verifies the iterations one by one, each with its own values, as it does today. A join of j=5 and j=6 ends that. Thus a state has the number of its iteration in each loop that is walked, and flow_trips_behind() tells the merge, the code that puts a state into a set, which states not to join. But then the states of all iterations stay in the sets, up to the limit: more than 1024 states that cannot be joined at insn 10 A walk only goes forward: what follows a state of iteration N is of iteration N or later. flow_earlier_trip() finds the states that are two or more iterations behind, and the merge frees them. nested_loops() then has 21 states at a time and takes 9954 insns (today: 5505 and 316200). lavd_init and qmap_init of rust-bpf fail in the same way. Crate spin, Mutex::lock(): while self.is_locked() { R::relax(); } No iteration changes what the verifier sees: each ends in the state of the one before, with a larger number. Thus in a walk of a loop without a count a state of an earlier iteration can cover a later one. flow_trips_near(): the merge drops a state that a state of its own iteration or of the two before it covers. If only states of one iteration are compared, 164 of the 225 progs of the schedulers of rust-bpf take more insns, 9 % in sum. The drop closes a cycle: the earlier state leads to the later one and now stands for it. "No state returns to the head, so the loop ends at run time" does not hold any more. Thus flow_cycle_closed() gives the loop a may_goto. It does nothing if the loop is counted, or if may_goto or bpf_iter_*_next() stops each iteration. It rejects a loop that has no place for may_goto. flow_within() is 'covers' for the merge: the comparison of pruning, also of the states that entered each counted loop: its ranges come from them. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261107033758.1547725-13-alexei.starovoitov@gmail.com
10 daysbpf: Add the sets of states at an insn and the entries of functionsAlexei Starovoitov
Selftest test_verif_scale1 has these lines 90 times. jhash() is static: ptr = data + i; if (ptr + nh_off > data_end) break; ctx->tc_index = jhash(ptr, nh_off, ctx->cb[0] + i++); Today the verifier verifies jhash() again for each state at each call: 530362 insns. The main pass verifies a static subprog for the states at its first insn, and the call waits for the states at the exits. Each call that waits makes an entry. Its number is in the entry state and in all states that come from it. 4095 states arrive at the 90 calls. At the first insn of jhash() a state of a different call covers 4005 of them. Then each exit state is for the calls of the two: call A --> entry 1 --+ +--> one set: calls { A, B }, exit states call B --> entry 2 --+ Thus the entries are disjoint sets, with union and find: 50765 insns. If they stay apart, the main pass hits its limit of states at an insn: "more than 1024 states that cannot be joined at insn 903". The same for pandemonium_enqueue of scx_pandemonium and 100 of the 225 progs of the schedulers of rust-bpf. All new states are in one tree. flow_set_pending() gives them an order: 1. Callers are before the subprogs that they call: all calls get to a subprog before it is verified. 2. Then the position of the call in each frame, then of the insn. Thus a callee that keeps the frames of its callers, like a callback, is complete before the code after the call. 3. A walk verifies a loop iteration by iteration, as today. An iteration is complete before the next one: for (int i = 0; i < MAX_AFFINITY_CANDIDATES; i++) { if (*val >= nr_cpu_ids) continue; if (++checked >= affinity_search_online) break; 'continue' is a back edge in the middle of the loop. By position alone it runs ahead through all iterations, and each is done again when the rest of the one before it arrives: pandemonium_select_cpu, 130073 insns, not 26758. bpf_flow_prepare() marks the insns where a state goes into a set, and those where a second state can arrive. Only there the set keeps a state that the verifier used: to keep them all doubles the peak of states of Cilium, scx. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261107033758.1547725-12-alexei.starovoitov@gmail.com
10 daysbpf: Find the registers and stack slots that later checks depend onAlexei Starovoitov
The join of two constants is not a constant, and some checks need one. The two states meet before the insn that checks. Thus the verifier must know, where they meet, that a later check depends on a register or a stack slot. A table per kind of check, FLOW_NEED_*, tells the rules that refuse a join: ARG an argument that must be a constant if (x) return bpf_rdonly_cast(0, ID); return bpf_rdonly_cast(0, 0); The compiler makes one call of it: "R2 must be a known constant" in selftest mem_rdonly_untrusted/mixed_mem_type. STACK_OFF an add to a pointer to the stack if (... || depth >= BT_MAXLVL_PRINT) return 0; ind = stack[depth]; The compiler tests one copy of depth and adds another. bt_print() of scx: "invalid variable-offset read from stack R3" PTR_OFF an add to a pointer to the packet, the context, a kernel object, a map value that is read-only or has a timer, a lock, a pointer if (data + hdr_len + inner_ip_offset > data_end) return TC_ACT_UNSPEC; inner_protocol = inner_iph->protocol; With [20, 40] as the offset the test tells nothing about data + hdr_len: "invalid access to packet, off=48 size=1" in katran/tcdecapinfo. JUMP a jump that compares with a constant, an argument or a return value that the verifier compares with a range if (ret < 0) ..; to_sport = state->to_sport; ret is a negative constant where state can be NULL. As a part of a range it passes the test: "R3 invalid mem access 'map_value_or_null'" in tail_handle_snat_fwd_ipv4 of Cilium. Three more tables are only for bpf_flow_is_needed(): does a check depend on a value that a counted loop changes and that has no closed form? If not, the value is widened at the loop head, and the verifier has no reason to walk the iterations one by one: for (int i = 0; i < STACK_MAX_LEN; ++i) { if (!frame_ptr || !get_frame_data(frame_ptr, pidData, &frame, &sym)) Each iteration fills the 24 stack slots of sym anew, and no check looks at them. pyperf600_nounroll takes 1281 insns, 154K with a walk of all 600. VALUE_OFF PTR_OFF, STACK_OFF, and an offset in each other map value BASE the address of a load or a store JUMP_ALU JUMP, and the values that the tested value is calculated from flow_compute_need_const() goes backward through the control flow graph until nothing changes, like the calculation of live registers. A use that it misses can reject a valid prog. It cannot accept an unsafe prog. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261107033758.1547725-11-alexei.starovoitov@gmail.com
10 daysbpf: Find the registers that hold a number or a pointer to arenaAlexei Starovoitov
The allocator of tools/sched_ext/scx_sdt.bpf.c looks for a free slot: if ((word & 0xffffffff) == 0) { num += 32; word >>= 32; } if ((word & 0xffff) == 0) { num += 16; word >>= 16; } ... six times, this is ffs() return (i * 64) + ffs(freeslots); The main pass joins the two states behind each 'if': num is [0, 32], then [0, 48]. It must not join two constants that the prog adds to a pointer to the packet, the context or a kernel object: these need the exact offset. The states meet before the add, and there the add is only 'r0 += r3'. If r0 can be such a pointer, num stays a constant and each 'if' doubles the states: up to 256 at an insn, not 2. sdt_init_task: 4897 insns, not 666. bpf_flow_compute_kinds() goes forward through the control flow graph, before the main pass. It finds the registers, stack slots and stack arguments that hold, on each path to an insn: - plain_regs: a scalar, or a pointer to arena: it may point anywhere, - value_regs: that, or a pointer to a map value that has only scalars and is not read-only: only the lowest and the highest offset count, - the context: a load through it can give a pointer to the packet. ALU op other than 64-bit add, sub, mov scalar, addr_space_cast too 64-bit add, sub what both operands are load through a scalar or a map value scalar load through ctx, or of less than 8 bytes is_valid_access() tells spill and fill through r10, r11 what the prog stored helper, kfunc from the prototype static subprog true at all calls, all exits global subprog, callback, target of callx only the context test_cls_redirect.c has the context in a struct. In a subprog c->skb comes from the stack of the caller: nothing is known about it. data = c->skb->data; if (data + (v6 ? 40 : 20) > end) return 0; So 4 bytes at the offset of data can be a pointer. Else 20 and 40 are joined: "invalid access to packet". loads_pkt_end notes a subprog that loads data_end, for the main pass. void * from a kfunc is a scalar, but not with KF_RET_NULL and not from bpf_rdonly_cast(), bpf_cast_to_kern_ctx(). p = bpf_core_cast(t, struct task_struct); x = z ? p->pid : p->tgid; is one 'r0 += r1' with 1856 or 1860. Joined: "invalid variable offset access into struct task_struct". The result only selects the states that the main pass does not join: a mistake rejects a valid prog or makes more states. No unsafe prog loads. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261107033758.1547725-10-alexei.starovoitov@gmail.com
10 daysbpf: Order the insns, find what stops a loop and where may_goto can goAlexei Starovoitov
A fixpoint shows that each iteration of a loop is safe, not that it ends: do { i++; sum += PT_REGS_RC(ctx); } while (i < 0x100000000ULL); Today selftest loop3 hits the limit of 1M insns. The main pass widens i and is done, so the verifier has to add a may_goto. That is an edge that the prog does not have. Its place decides which progs load: 1. None, if each iteration executes a may_goto that leaves the loop, or bpf_iter_*_next() of an iterator that was created before the loop. bpf_repeat(1000000) { map_val = bpf_map_lookup_elem(&hash_map, &key); if (map_val) { found = true; break; } } if (found) *map_val = 123; An added may_goto goes where 'break' goes, without the test. Selftest iters/iter_tricky_but_fine: "R6 invalid mem access 'map_value_or_null'". layered_init of scx_layered and mitosis_init of scx_mitosis fail alike. 2. In front of a conditional jump that leaves the loop, to its target: the prog gets there with the same registers and stack. One jump of the loop itself, bpf_insn_leaves_loop(), that each iteration goes through is enough: the 'while' of loop3. Else each back edge gets one: a may_goto at the head skips the body, and the first exit can read what the body sets. 3. At the head, if a back edge has none. The compiler makes one loop of while self.locked.compare_exchange(0, 1, Acquire, Relaxed).is_err() { while self.locked.load(Relaxed) != 0 { core::hint::spin_loop(); } } and the inner back edge has none. Without this place the main pass says "loop at insn 127 never exits" for 142 of the 225 progs of the schedulers of rust-bpf. This edge can skip what stops an outer loop: it leaves all. The added insn executes in each state. Thus a loop has it for all states or for none. The main pass can find out late: it first goes through loop3 iteration by iteration, as today, and gives up. Then the pass is repeated. The main pass takes the blocks that have a new state in the order of flow_compute_order(): reverse post order, but a loop stays together. Else the code behind a 'break' is verified before the loop is done, then again. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261107033758.1547725-9-alexei.starovoitov@gmail.com
10 daysbpf: Add the data structures of the main pass over the control flow graphAlexei Starovoitov
The verifier follows each path of a prog from the entry to exit. It ends a path early only where an earlier path left a state that covers the current one. A live value that differs from path to path defeats that. Then the work grows with the number of paths, not with the size of the prog: for b in bytes { h = (h ^ *b as u64).wrapping_mul(0x100000001b3); } In this FNV hash h is a new number in each iteration, so no state covers the next one. Branches that set different values do the same to C code. insns processed today this series rust-bpf hash_fnv_bytes 1000001 * 160 rust-bpf scx_qmap/qmap_init_cids 131088 * 196 selftests test_verif_scale3/balancer_ingress 821107 57155 scx scx_eevdf/eevdf_dispatch 350041 15322 Cilium bpf_host/cil_to_netdev, Oct 2026 64658 7538 * "BPF program is too large", "The sequence of 8193 jumps is too complex" flow.c is a new main pass: a data-flow analysis over the control flow graph that runs to a fixpoint. Where two paths meet, it joins their states into one state that covers both: r1=1 and r1=5 give r1=[1,5]. At the head of a loop it widens what grows: h becomes an unknown scalar, and one more pass over the body ends the loop. A join can lose a fact that a later check depends on. Thus a basic block has a set of states, not one state: a state arrives at a basic block the verifier a state of the set covers it drops it it has a join with a state of the set replaces that state with the join all other cases adds it to the set The verifier verifies a block with each new state of its set and sends the results to the successors of the block. The pass ends when no set has a new state. The check of one insn does not change. Add the head comment, the limits and the data structures: struct flow_state a state in a set, or the state of a call that waits struct flow_set the states at one insn struct flow_entry the calls that wait for a subprog, its exit states struct flow_need what the checks after an insn depend on The limits are on states and grow with the prog. For a prog of N insns: 1024 at an insn, 16 * N + 4096 at a time, 256 * N + 64K in all. Nothing builds flow.c until its last function is there. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261107033758.1547725-8-alexei.starovoitov@gmail.com