summaryrefslogtreecommitdiff
path: root/kernel/bpf/join.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 scalar_add() and four more operations on struct scalarAlexei Starovoitov
The sum of two values is written six times. Four copies are in verifier.c: adjust_scalar_min_max_vals(), adjust_ptr_min_max_vals(), add_scalar_to_reg() and recompute_ptr() add the step, the ranges and var_off line by line. Two are in scev.c, which has no register to pass to verifier.c's helpers: scev_value_add() adds ranges and knows nothing of var_off and step, bpf_clamp_scev_regs() adds r64 and the step. Make the operations that scev.c needs take a struct scalar. Each of them is code that verifier.c has, none is a second copy: - scalar_add() replaces the four copies in verifier.c. scalar_min_max_add() and scalar32_min_max_add() go. The sum of a pointer and a scalar takes no 32-bit range from its operands: adjust_ptr_min_max_vals() and recompute_ptr() forget r32 of the pointer first, reg_bounds_sync() derives it from r64, as before. - scalar_set_const() was ___mark_reg_known(). add_scalar_to_reg() makes a constant with it, and no register of 80 bytes. - scalar_set_unknown() was bpf_reg_forget_range(). - scalar_zext32() was zext_32_to_64(). It calls cnum64_zext32(): an empty r32 gives an empty r64, it gave [0, U32_MAX]. Such a register is a violation that reg_bounds_sanity_check() reports either way. - scalar_union() was bpf_reg_union_range(). None of them calls reg_bounds_sync(): the callers do, where they did. No other functional change. Suggested-by: Eduard Zingerman <eddyz87@gmail.com> Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261112000836.3138846-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: Remove scalar ids from the join of statesAlexei Starovoitov
Removal of dead code, as in regsafe(). Scalars have no ids any more. No prog is verified differently. Two states are joined in two passes. The first one records which id of one state goes with which id of the other: jid_note(). The second one computes the registers. A scalar kept its id only if the pair was good: the registers that share the id in one state share it in the other one, with the same BPF_ADD_CONST and delta, see scalar_link_consistent(). A link that one state did not have was dropped. Now the join of two scalars is the join of their ranges. Remove scalar_link_consistent() and the scalars from jid_note() and jid_good(). All other callers of jid_note() pass true for 'consistent': the parameter goes. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261111164557.2659679-27-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: Make the state after a call from the caller's state and an exit stateAlexei Starovoitov
match_one() of scx_layered runs in three nested bpf_for() loops and calls a static subprog, get_pid_nr_ns(): scoped_guard(rcu) { ... nspid = get_pid_nr_ns(p_pid, pid_ns); It is verified for the states at its first insn, not for each chain of calls. One exit state is the result for all calls that wait: 2: call f --- { r1=scalar } ---> +---------------------+ 7: call f --- { r1=scalar } ---> | f: verified 1 time | 3: ... <-- { r0=[0,7] } ----- | | 8: ... <-- { r0=[0,7] } ----- +---------------------+ That works only if calls that differ in ids give the same entry state. Here the callers hold three iterators, and each bpf_iter_num_new() has a new id. What is held is a part of the entry state: it decides what the subprog may do. In the subprog the id of refs[i] of the caller becomes a name, BPF_INHERITED_ID + i. A name stands for one object of the caller. Thus check_ids() and the join do not rename it: it is equal only to itself. If a call with something held keeps the frames of the callers instead, layered_runnable takes 5219 insns, not 4459, and recursion has no end. core::fmt of Rust is recursive, and progs format a message while they hold a reference. 27 progs of the schedulers of rust-bpf fail: "the call stack of 33 frames is too deep". bpf_flow_return() makes the state after the call: - r0, and r2 of a pair, come from the exit state. r1-r5 and the outgoing stack arguments are not set. - What is held is what the caller held and what the subprog took. The names become the ids of the caller again. - All other ids get new values for each call. If not, two calls in sequence return the same object. Selftest test_spin_lock, lock_static_subprog_unlock(): bpf_spin_lock(&lockA); ret = static_subprog_unlock(ctx); An exit state does not tell what a release does to the caller. Thus the frame counts what it holds without interruption since its entry. If that is less than the caller held, the function returns 1, and the call is verified again with the frames of the caller. Also: rcu_read_lock, preempt_lock. The same if it changed the packet through a function that is its argument. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261107033758.1547725-17-alexei.starovoitov@gmail.com
10 daysbpf: Add join of verifier statesAlexei Starovoitov
central_dispatch() of tools/sched_ext/scx_central.bpf.c: bpf_for(cpu, 0, nr_cpu_ids) { ... if (dispatch_to_cpu(cpu)) *gimme = false; } ... dispatch_to_cpu(central_cpu); To verify dispatch_to_cpu() one time, not for each call, the states of the two calls must meet at its first insn. Numbers, like cpu, can be joined. But at one call the iterator of bpf_for() is held, at the other nothing. One state cannot stand for the two: the code after the return destroys the iterator for one of them only. A state is more than registers and slots. Add the second half of join.c and build it. bpf_states_join() joins two states at one insn, frame by frame. There is no join, and the caller keeps the two states, when one of these differs: frames number, subprog, callsite, kind of callback locks, RCU, preempt the counts, the lock references number and types. The ids must pair one to one held since the entry entry_refs, entry_rcu_locks, entry_preempt_locks loop stack the loops, the state that entered them, the count, the iteration if iterations are kept apart flags speculative, sleepable, unwound, ... - A register, its spill and the reference have one id. Thus the pairs of ids are collected over all frames and references first, and the join is made in a second pass. - Only live registers count, and the caller removes dead stack slots with bpf_clean_verifier_state(). What is dead does not prevent a join. - A subprog that is verified without its callers has what they hold in its state, as above. entry_* tell how much of it is still held. - Such a subprog has its incoming stack arguments in the slots for outgoing ones, until it has loaded them. The two kinds are not joined. quicksort(right, scratch, limit, pivot_ref, is_less) of Rust's core is recursive and takes 7 words: bpfland_init of rust-bpf fails without it. bpf_states_join() examines each result with the comparison that pruning uses: the join must cover state a and state b. If it does not, that is a verifier bug and the prog is rejected, not loaded. The fields that join.c compares come with this patch. Nothing sets them, nothing calls the join. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261107033758.1547725-6-alexei.starovoitov@gmail.com
10 daysbpf: Add join of registers and stack slotsAlexei Starovoitov
ipv6_hdrlen_offset() of Cilium skips extension headers, unrolled: for (i = 0; i < IPV6_MAX_HEADERS; i++) { int hdrlen = ipv6_skip_exthdr(ctx, &newnh, l3_off + len); ... 8, (opthdr->hdrlen + 2) << 2 or (opthdr->hdrlen + 1) << 3 len += hdrlen; } The verifier follows each path. Three lengths for each header: the insn behind this loop is verified 76 times, and each time the rest of the prog follows, where more paths fork. tail_nodeport_nat_ingress_ipv6 of bpf_xdp, as of May 2026, has 4095 insns, the verifier processes 182050. Add the join of two states: one state that covers the two. Here hdrlen is [8, 2048]. A caller that replaces two states with their join verifies the code that follows one time. This prog: 3 times in place of 76, 7932 insns. This is the first half of join.c: ids, registers, stack slots. Only numbers are joined: scalars, and the variable offsets of pointers. A join loses information. Where the prog needs it there is no join, and the caller keeps the two states: - map value + 8 and map value + 16: two fields, not a range scx_rusty: create_save_cpumask(&kptr) for three kptrs in .data "R1 doesn't have constant offset. kptr has to be at the constant offset" - packet pointers that are checked up to different ends Cilium: l4_csum_replace(ctx, l4_off + csum->offset, ..) "invalid access to packet": 206 progs of bpf_xdp in 37 builds of Cilium - a scalar and a pointer, pointers to two objects: of no use to a prog Each path makes its own ids. An id in the join stands for a pair: the id in state a and the id in state b. The pairs must be one to one, as in check_ids(). If not, a scalar loses its id, and a pointer has no join. - 'bpf_for(i, 0, 10) sum += i;' of iters_num: each bpf_iter_num_next() returns a pointer with a new id. If ids had to be equal, the main pass says "more than 1024 states that cannot be joined at insn 16". - scx_pandemonium: 'if (.. && (u32)src_cpu < MAX_CPUS) pair_warm_ns[..]' tests r5 and indexes with its copy in fp-88. Paths meet between copy and test. A join without ids: "R3 unbounded memory access". With 'widen', at a loop head, a scalar that grew is widened. If each iteration adds a constant to it, it becomes an unknown scalar of 64 or 32 bits at once: scev_compute_linear_regs() sets linear_regs, linear32_regs of struct bpf_loop for that. So does sum of bpf_for() above: it is a register plus or minus something (expr_is_sum()), and no jump of the loop depends on it (tested_regs). 0, [0, S32_MAX], [0, U32_MAX], unknown are 4 passes through the body, this is 2: 59 -> 43 insns. If a jump depends on the sum the stops stay. A pointer whose offset grew has no join: no later comparison gives it a bound. Signed-off-by: Alexei Starovoitov <ast@kernel.org> Link: https://patch.msgid.link/20261107033758.1547725-5-alexei.starovoitov@gmail.com