| Age | Commit message (Collapse) | Author |
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|
|
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
|