From: Alexei Starovoitov A removal: sync_linked_regs(), the code that scalar ids exist for, goes. The ids themselves go in later patches. Precision is lost where only a state knows that two scalars are linked: across frames, and on one of several paths. One selftest has to change. After a conditional jump sync_linked_regs() copies the range of the tested register, plus delta, to all scalars with its id. refine_linked_regs() does that job without ids. It 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. There is no limit of 5 registers, and a second '+=' does not drop the link. Both run at every jump, sync_linked_regs() first. Remove it, collect_linked_regs() and struct linked_regs. Scalar ids are still assigned, no jump reads them. Precision that is lost: - Linked registers belong to the frame of the jump. Scalar ids also linked registers and stack slots of the callers. A subprog that tests its argument refined the register that the caller keeps. A field of a struct on the stack of the caller that a subprog loads, tests and loads again was refined in the slot. - That two arguments hold the same value is known at the callsite, not in the subprog. The selftest "regalloc in callee" passes the same value in r1 and r2 and is rejected now. Its 'r2 = r0' before the call becomes 'r2 = r1' in the callee. - 'r2 = r1' on one of two paths to a jump. A link holds on every path, so r2 is not linked. The id worked until the state of that path was joined with the other one. The first iteration of a loop is such a path. - refine_linked_regs() runs for loaders with CAP_BPF, sync_linked_regs() ran for everybody. No other prog of the selftests, Cilium, sched_ext, katran, bpfjailer and of the programs in Rust changes its verdict. Precision that is gained: sync_linked_regs() overwrites ranges, refine_linked_regs() intersects them. With n in [0, 19] and 'u64 ent[16]' clang emits for 'n = n > 4 ? n - 4 : 0; e->ent[n] = 1;': 10: w2 = w6 11: w2 += -4 14: if w2 > w6 goto pc+1 If the jump is not taken w2 did not wrap: it is at most 19. r2 and r6 have the same id, so sync_linked_regs() overwrites r2 with r6 - 4 modulo 2^32, which can be 0xfffffffc: R0 unbounded memory access, make sure to bounds check any such access With refine_linked_regs() alone r2 is in [0, 15] and the prog loads. The selftest linked_regs_too_many_regs sees all six registers refined. Signed-off-by: Alexei Starovoitov --- kernel/bpf/verifier.c | 161 ------------------ .../bpf/progs/verifier_array_access.c | 2 +- .../selftests/bpf/progs/verifier_regalloc.c | 2 +- .../selftests/bpf/progs/verifier_scalar_ids.c | 13 +- 4 files changed, 5 insertions(+), 173 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 970211dfe38c..103e83cd23ef 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -3578,30 +3578,6 @@ static void mark_non_stack_access(struct bpf_verifier_env *env, int idx) env->insn_aux_data[idx].non_stack_access = true; } -#define LINKED_REGS_MAX 5 - -struct linked_reg { - u8 frameno; - union { - u16 spi; - u16 regno; - }; - bool is_reg; -}; - -struct linked_regs { - int cnt; - struct linked_reg entries[LINKED_REGS_MAX]; -}; - -static struct linked_reg *linked_regs_push(struct linked_regs *s) -{ - if (s->cnt < LINKED_REGS_MAX) - return &s->entries[s->cnt++]; - - return NULL; -} - const char *bpf_disasm_kfunc_name(void *data, const struct bpf_insn *insn) { const struct btf_type *func; @@ -19629,119 +19605,6 @@ static bool try_match_pkt_pointers(const struct bpf_insn *insn, return true; } -static void __collect_linked_regs(struct linked_regs *reg_set, struct bpf_reg_state *reg, - u32 id, u32 frameno, u32 spi_or_reg, bool is_reg) -{ - struct linked_reg *e; - - if (reg->type != SCALAR_VALUE || (reg->id & ~BPF_ADD_CONST) != id) - return; - - e = linked_regs_push(reg_set); - if (e) { - e->frameno = frameno; - e->is_reg = is_reg; - e->regno = spi_or_reg; - } else { - clear_scalar_id(reg); - } -} - -/* For all R being scalar registers or spilled scalar registers - * in verifier state, save R in linked_regs if R->id == id. - * If there are too many Rs sharing same id, reset id for leftover Rs. - */ -static void collect_linked_regs(struct bpf_verifier_env *env, - struct bpf_verifier_state *vstate, - u32 id, - struct linked_regs *linked_regs) -{ - struct bpf_insn_aux_data *aux = env->insn_aux_data; - struct bpf_func_state *func; - struct bpf_reg_state *reg; - u16 live_regs; - int i, j; - - id = id & ~BPF_ADD_CONST; - for (i = vstate->curframe; i >= 0; i--) { - live_regs = aux[bpf_frame_insn_idx(vstate, i)].live_regs_before; - func = vstate->frame[i]; - for (j = 0; j < BPF_REG_FP; j++) { - if (!(live_regs & BIT(j))) - continue; - reg = &func->regs[j]; - __collect_linked_regs(linked_regs, reg, id, i, j, true); - } - for (j = 0; j < bpf_stack_nr_slots(func); j++) { - struct bpf_stack_state *ss = bpf_stack_slot(func, j); - - if (!bpf_is_spilled_reg(ss)) - continue; - reg = &ss->spilled_ptr; - __collect_linked_regs(linked_regs, reg, id, i, j, false); - } - } -} - -/* For all R in linked_regs, copy known_reg range into R - * if R->id == known_reg->id. - */ -static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_state *vstate, - struct bpf_reg_state *known_reg, struct linked_regs *linked_regs) -{ - struct bpf_reg_state fake_reg; - struct bpf_reg_state *reg; - struct linked_reg *e; - int i; - - for (i = 0; i < linked_regs->cnt; ++i) { - e = &linked_regs->entries[i]; - reg = e->is_reg ? &vstate->frame[e->frameno]->regs[e->regno] - : &bpf_stack_slot(vstate->frame[e->frameno], e->spi)->spilled_ptr; - if (reg->type != SCALAR_VALUE || reg == known_reg) - continue; - if ((reg->id & ~BPF_ADD_CONST) != (known_reg->id & ~BPF_ADD_CONST)) - continue; - /* - * Skip mixed 32/64-bit links: the delta relationship doesn't - * hold across different ALU widths. - */ - if (((reg->id ^ known_reg->id) & BPF_ADD_CONST) == BPF_ADD_CONST) - continue; - if ((!(reg->id & BPF_ADD_CONST) && !(known_reg->id & BPF_ADD_CONST)) || - reg->delta == known_reg->delta) { - *reg = *known_reg; - } else { - s32 saved_off = reg->delta; - u32 saved_id = reg->id; - - fake_reg.type = SCALAR_VALUE; - __mark_reg_known(&fake_reg, (s64)reg->delta - (s64)known_reg->delta); - - /* reg = known_reg; reg += delta */ - *reg = *known_reg; - /* - * Must preserve off and id, otherwise another sync_linked_regs() - * will be incorrect. - */ - reg->delta = saved_off; - reg->id = saved_id; - - scalar_step_add(reg, reg, &fake_reg); - scalar32_min_max_add(reg, &fake_reg); - scalar_min_max_add(reg, &fake_reg); - reg->var_off = tnum_add(reg->var_off, fake_reg.var_off); - if ((reg->id | known_reg->id) & BPF_ADD_CONST32) - zext_32_to_64(reg); - reg_bounds_sync(reg); - } - if (e->is_reg) - mark_reg_scratched(env, e->regno); - else - mark_stack_slot_scratched(env, e->spi); - } -} - /* a == b (mod 2^N) implies a == b if both fit in uN or both fit in sN. N is @bits. */ static bool regs_fit_in_bits(const struct bpf_reg_state *a, const struct bpf_reg_state *b, u32 bits) @@ -19886,7 +19749,6 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env, struct bpf_reg_state *regs = this_branch->frame[this_branch->curframe]->regs; struct bpf_reg_state *dst_reg, *other_branch_regs, *src_reg = NULL; struct bpf_reg_state *eq_branch_regs; - struct linked_regs linked_regs = {}; u8 opcode = BPF_OP(insn->code); bool is_jmp32; int pred = -1; @@ -19955,16 +19817,6 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env, __mark_reg_known(src_reg, insn->imm); } - /* - * Collect the linked registers before env->{true,false}_reg{1,2} setup, - * otherwise ids dropped by collect_linked_regs() would be resurrected - * when env->{true,false}_reg{1,2} are copied back. - */ - if (BPF_SRC(insn->code) == BPF_X && src_reg->type == SCALAR_VALUE && src_reg->id) - collect_linked_regs(env, this_branch, src_reg->id, &linked_regs); - if (dst_reg->type == SCALAR_VALUE && dst_reg->id) - collect_linked_regs(env, this_branch, dst_reg->id, &linked_regs); - is_jmp32 = BPF_CLASS(insn->code) == BPF_JMP32; env->false_reg1 = *dst_reg; env->false_reg2 = *src_reg; @@ -20018,19 +19870,6 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env, if (BPF_SRC(insn->code) == BPF_X) other_branch_regs[insn->src_reg] = env->true_reg2; - if (BPF_SRC(insn->code) == BPF_X && - src_reg->type == SCALAR_VALUE && src_reg->id && - !WARN_ON_ONCE(src_reg->id != other_branch_regs[insn->src_reg].id)) { - sync_linked_regs(env, this_branch, src_reg, &linked_regs); - sync_linked_regs(env, other_branch, &other_branch_regs[insn->src_reg], - &linked_regs); - } - if (dst_reg->type == SCALAR_VALUE && dst_reg->id && - !WARN_ON_ONCE(dst_reg->id != other_branch_regs[insn->dst_reg].id)) { - sync_linked_regs(env, this_branch, dst_reg, &linked_regs); - sync_linked_regs(env, other_branch, &other_branch_regs[insn->dst_reg], - &linked_regs); - } if (env->bpf_capable) { if (BPF_SRC(insn->code) == BPF_X) { refine_linked_regs(env, this_branch, *insn_idx, insn->src_reg); diff --git a/tools/testing/selftests/bpf/progs/verifier_array_access.c b/tools/testing/selftests/bpf/progs/verifier_array_access.c index 7f98822889ca..29bed1e496af 100644 --- a/tools/testing/selftests/bpf/progs/verifier_array_access.c +++ b/tools/testing/selftests/bpf/progs/verifier_array_access.c @@ -762,7 +762,7 @@ l0_%=: *(u32*)(r10 - 8) = r6; \ : __clobber_all); } -/* The slot has the id of r6, so the compare sets the range of the slot too */ +/* The slot holds the low 32 bits of r6, so the compare refines the slot too */ SEC("socket") __description("valid map access into an array using a key that is compared after the spill") __success __retval(0) diff --git a/tools/testing/selftests/bpf/progs/verifier_regalloc.c b/tools/testing/selftests/bpf/progs/verifier_regalloc.c index ee5ddea87c91..cf26617b6ba1 100644 --- a/tools/testing/selftests/bpf/progs/verifier_regalloc.c +++ b/tools/testing/selftests/bpf/progs/verifier_regalloc.c @@ -303,7 +303,6 @@ __naked void regalloc_in_callee(void) r7 = r0; \ call %[bpf_get_prandom_u32]; \ r1 = r0; \ - r2 = r0; \ r3 = r7; \ call regalloc_in_callee__1; \ l0_%=: exit; \ @@ -318,6 +317,7 @@ static __naked __noinline __attribute__((used)) void regalloc_in_callee__1(void) { asm volatile (" \ + r2 = r1; \ if r1 s> 20 goto l0_%=; \ if r2 s< 0 goto l0_%=; \ r3 += r1; \ diff --git a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c index 819d0a1a6886..e22120e5858f 100644 --- a/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c +++ b/tools/testing/selftests/bpf/progs/verifier_scalar_ids.c @@ -285,13 +285,8 @@ __naked void precision_two_ids(void) SEC("socket") __success __log_level(2) -/* - * check that r5 is unlinked after 'if', collect_linked_regs() can't tie - * more than 5 registers for a single insn and the register compared by - * the jump is not exempt from that. The jump refines the copies all the same. - */ -__msg("7: (25) if r5 > 0x7 goto pc+0 ; R0=" LINKED("1", 7, 0x7) " R1=" LINKED("1", 7, 0x7) " R2=" LINKED("1", 7, 0x7) " R3=" LINKED("1", 7, 0x7) " R4=" LINKED("1", 7, 0x7) " R5=scalar(smin=") -__msg("12: (bf) r5 = r5 ; R5=scalar(id=2") +/* there is no limit of 5 registers for a single insn */ +__msg("7: (25) if r5 > 0x7 goto pc+0 ; R0=" LINKED("1", 7, 0x7) " R1=" LINKED("1", 7, 0x7) " R2=" LINKED("1", 7, 0x7) " R3=" LINKED("1", 7, 0x7) " R4=" LINKED("1", 7, 0x7) " R5=" LINKED("1", 7, 0x7)) __naked void linked_regs_too_many_regs(void) { asm volatile ( @@ -304,14 +299,12 @@ __naked void linked_regs_too_many_regs(void) "r3 = r0;" "r4 = r0;" "r5 = r0;" - /* r{0-4} fill the record, r5 does not fit and is unlinked */ "if r5 > 7 goto +0;" - /* keep r{1-4} live */ + /* keep r{1-5} live */ "r1 = r1;" "r2 = r2;" "r3 = r3;" "r4 = r4;" - /* make r5 appear in the log */ "r5 = r5;" "r7 = r10;" "r7 += r0;" -- 2.55.0