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