A 32-bit fill from a wider spilled scalar has the same shape as a 32-bit mov from a wider source, and the relation was dropped rather than recorded:
r6 = ... /* full 64-bit unknown */ *(u64 *)(r10 - 8) = r6; /* slot linked to r6 */ r2 = *(u32 *)(r10 - 8); /* narrowing fill */ if w6 != 0 goto ... /* not taken: r6's low 32 bits are 0 */ if r2 == 0 goto ... /* not deduced today */ Record a low-32 link as the mov arm does. Stack slots are already first-class members of an ->id set, so sync_linked_regs() and the reconstruction helpers apply unchanged. A fill narrower than 32 bits has no expressible relation and still drops it. Which extension rebuilds the high half depends on the load, so check_stack_read() takes is_ldsx and sets BPF_REG_LINK_SEXT where that is known. check_mem_access() then keeps a sign-extending link across a 4-byte sign-extending load only: BPF_REG_LINK_SEXT means (s32)(base + delta) specifically, so an 8- or 16-bit ldsx is a relation the kind cannot express, the same way the ALU arm's subreg_link is gated on (insn->off >> 3) == 4. Costs. A bisect lands one clang regression here -- big_alloc2 2956 -> 3095 insns, 157 -> 165 states -- but it is not this patch alone: it takes both this and the preceding reverse-direction patch, and neither moves big_alloc2 by itself. The external corpus does move for this patch alone, no verdict changes, six programs verifying in more instructions: +1812 2470 -> 4282 test_file_open bpfjailer-lib-tests open +1765 59556 -> 61321 twfw_connect4 tupperware-agent twfw_sock +1765 59556 -> 61321 twfw_sendmsg4 same object +752 5874 -> 6626 layered_enqueue scx_layered 1.0.11.1 +252 2512 -> 2764 bpfj_exec_execve exec_enforce +252 2512 -> 2764 bpfj_exec_execveat same object +6598 over 25.2M, or +0.026%, and +218 states. The shape is the familiar one: a more precise recorded state has a smaller equivalence class and prunes against fewer predecessors. Signed-off-by: Vineet Gupta <[email protected]> --- v3: was v2 9/13. - renamed to the new encoding, and the fill inherits the slot's delta rather than resetting it, matching patch 6 - a sign-extending load keeps a link only if it is a 4-byte BPF_REG_LINK_SEXT. BPF_REG_LINK_ZEXT says the opposite of what the load just did, and an 8- or 16-bit ldsx is a relation the kind cannot express. - measured cost, which v2 did not report: six external programs verify in more instructions, +6598 aggregate (+0.026%), worst +1812 on test_file_open. No verdict changes. Attributed to this patch by building the patch-7 and patch-8 kernels separately. kernel/bpf/verifier.c | 60 +++++++++++++++++++++++++++++++++++-------- 1 file changed, 49 insertions(+), 11 deletions(-) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 6b26487d4549..feefa5733fd7 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -4223,7 +4223,8 @@ static void bpf_diag_stack_read_invalid(struct bpf_verifier_env *env, int off, i static int check_stack_read_fixed_off(struct bpf_verifier_env *env, /* func where src register points to */ struct bpf_func_state *reg_state, - int off, int size, int dst_regno) + int off, int size, int dst_regno, + bool is_ldsx) { struct bpf_verifier_state *vstate = env->cur_state; struct bpf_func_state *state = vstate->frame[vstate->curframe]; @@ -4258,22 +4259,52 @@ static int check_stack_read_fixed_off(struct bpf_verifier_env *env, if (size <= spill_size && bpf_stack_narrow_access_ok(off, size, spill_size)) { + bool narrowing = get_reg_width(reg) > size * BITS_PER_BYTE; + /* + * A narrowing fill keeps only the slot's low 32 bits, + * so record a low-32 link rather than dropping the + * relation, as a 32-bit mov from a wide source does. + * Which link kind depends on how the load fills the high + * half, hence is_ldsx. + */ + bool subreg_link = narrowing && size == 4; + if (dst_regno < 0) return 0; - if (env->bpf_capable && size == 4 && spill_size == 4 && - get_reg_width(reg) <= 32) + if (env->bpf_capable && size == 4 && + (subreg_link || (spill_size == 4 && !narrowing))) /* Ensure stack slot has an ID to build a relation * with the destination register on fill. */ assign_scalar_id_before_mov(env, reg); state->regs[dst_regno] = *reg; - /* Break the relation on a narrowing fill. - * coerce_reg_to_size will adjust the boundaries. + /* + * A fill that is not narrowing copies the slot's link + * kind verbatim, which a sign-extending load can + * contradict. check_mem_access() runs after this and + * drops any kind but BPF_REG_LINK_SEXT once it knows + * the extension was not a no-op. */ - if (get_reg_width(reg) > size * BITS_PER_BYTE) + if (subreg_link && reg->id) { + /* + * Keep the slot's delta: both + * (u32)(base + d) and (s32)(base + d) + * have low half base + d, so the fill + * inherits it rather than resetting it. + */ + state->regs[dst_regno].link_kind = + is_ldsx ? BPF_REG_LINK_SEXT : BPF_REG_LINK_ZEXT; + } else if (narrowing) { + /* + * Nothing to relate: either the slot has + * no id to share, or the fill is narrower + * than the 32 bits a link can describe. + * coerce_reg_to_size adjusts the bounds. + */ bpf_clear_scalar_id(&state->regs[dst_regno]); + } } else { int spill_cnt = 0, zero_cnt = 0; @@ -4439,7 +4470,7 @@ static int check_stack_read_var_off(struct bpf_verifier_env *env, struct bpf_reg */ static int check_stack_read(struct bpf_verifier_env *env, struct bpf_reg_state *reg, argno_t ptr_argno, int off, int size, - int dst_regno) + int dst_regno, bool is_ldsx) { struct bpf_func_state *state = bpf_func(env, reg); int err; @@ -4478,7 +4509,7 @@ static int check_stack_read(struct bpf_verifier_env *env, if (!var_off) { off += reg->var_off.value; err = check_stack_read_fixed_off(env, state, off, size, - dst_regno); + dst_regno, is_ldsx); } else { /* Variable offset stack reads need more conservative handling * than fixed offset ones. Note that dst_regno >= 0 on this @@ -7295,7 +7326,7 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, struct b if (t == BPF_READ) err = check_stack_read(env, reg, argno, off, size, - value_regno); + value_regno, is_ldsx); else err = check_stack_write(env, reg, off, size, value_regno, insn_idx); @@ -7392,13 +7423,20 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, struct b * Sign-extension can change the register value relative * to a scalar it is linked with by id (e.g. a zero- * extending fill of the same spilled stack slot), thus - * drop the shared id in that case. + * drop the shared id in that case. Only a 4-byte + * BPF_REG_LINK_SEXT link survives: it says the high + * half is this very sign-extension. BPF_REG_LINK_ZEXT + * says the opposite and would be a lie about the value + * just produced, and an 8- or 16-bit sign extension is + * a relation BPF_REG_LINK_SEXT cannot express at all -- + * it means (s32)(base + delta) specifically. */ bool no_sext = reg_umax(®s[value_regno]) < (1ULL << (size * BITS_PER_BYTE - 1)); coerce_reg_to_size_sx(®s[value_regno], size); - if (!no_sext) + if (!no_sext && + !(size == 4 && regs[value_regno].link_kind == BPF_REG_LINK_SEXT)) bpf_clear_scalar_id(®s[value_regno]); } } -- 2.53.0-Meta
