The zero-extending mov records that dst shares src's low 32 bits. A 32-bit sign extension shares them too -- it keeps the low half and fills the high half from bit 31 -- so the same link applies, with a different rule for rebuilding the high bits:
r6 = ... /* full 64-bit unknown */ r7 = (s32)r6 /* 32-bit sign-extending mov */ if w6 == -1 goto ... /* taken: r6's low 32 bits are all ones */ ... /* r7 is -1, not deduced today */ Add SUBREG_SEXT alongside SUBREG_ZEXT, and sext_32_to_64() alongside zext_32_to_64() to drive the reconstruction. Both work from the base's 32-bit range, which is what a 32-bit compare narrows. coerce_reg_to_size_sx() cannot serve here: it reads smin/smax, which straddle after such a compare and collapse to the full field range. tnum_sext() is the counterpart to tnum_cast(). Unlike a tnum_range() over the new bounds it keeps the known low bits. The enum has room for the third value, so bpf_reg_state stays 80 bytes. Unlike the zero-extending arm, a self-mov can form a link here, but only when src is already linked: r0 = (s32)r0 is how a sign-extended int return lands. On an unlinked register there is nothing to link to, and minting an id would leave the register describing itself. Signed-off-by: Vineet Gupta <[email protected]> --- v2: was RFC 5/6. - no forward declaration (Eduard) - src renamed known_reg (Eduard) - sext_32_to_64() and tnum_sext() rather than reusing coerce_reg_to_size_sx(); the sync path needs the base's 32-bit range, see the cover letter - tnum_sext() keeps the known low bits a tnum_range() would drop (Eduard) - a self-mov links only when src already has an id, narrower than the RFC include/linux/bpf_verifier.h | 1 + include/linux/tnum.h | 3 +++ kernel/bpf/log.c | 2 ++ kernel/bpf/tnum.c | 15 ++++++++++++ kernel/bpf/verifier.c | 47 +++++++++++++++++++++++++++++++++--- 5 files changed, 65 insertions(+), 3 deletions(-) diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index f1b01059c5da..920c9490ecc8 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -53,6 +53,7 @@ enum bpf_add_const { enum bpf_subreg { SUBREG_NONE = 0, SUBREG_ZEXT, /* high bits are zero (32-bit zero-extending mov) */ + SUBREG_SEXT, /* high bits repeat bit 31 (32-bit sign-extending mov) */ }; struct bpf_reg_state { diff --git a/include/linux/tnum.h b/include/linux/tnum.h index ca2cfec8de08..866803de5841 100644 --- a/include/linux/tnum.h +++ b/include/linux/tnum.h @@ -63,6 +63,9 @@ struct tnum tnum_union(struct tnum t1, struct tnum t2); /* Return @a with all but the lowest @size bytes cleared */ struct tnum tnum_cast(struct tnum a, u8 size); +/* Return the lowest @size bytes of @a sign-extended to 64 bits */ +struct tnum tnum_sext(struct tnum a, u8 size); + /* Swap the bytes of a tnum */ struct tnum tnum_bswap16(struct tnum a); struct tnum tnum_bswap32(struct tnum a); diff --git a/kernel/bpf/log.c b/kernel/bpf/log.c index 4047cfb0a698..b67bbd4d57f4 100644 --- a/kernel/bpf/log.c +++ b/kernel/bpf/log.c @@ -656,6 +656,8 @@ static void print_reg_state(struct bpf_verifier_env *env, verbose(env, "%+d", reg->delta); if (reg->subreg == SUBREG_ZEXT) verbose(env, ".lo32"); + else if (reg->subreg == SUBREG_SEXT) + verbose(env, ".lo32sx"); if (reg->parent_id) verbose_a("parent_id=%d", reg->parent_id); if (type_is_non_owning_ref(reg->type)) diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c index ec9c310cf5d7..e1dc57afd3d3 100644 --- a/kernel/bpf/tnum.c +++ b/kernel/bpf/tnum.c @@ -200,6 +200,21 @@ struct tnum tnum_cast(struct tnum a, u8 size) return a; } +struct tnum tnum_sext(struct tnum a, u8 size) +{ + u8 shift = 64 - size * 8; + + /* + * Shifting the field up to the top and back down arithmetically + * replicates its sign bit through the high half. Applying that to the + * mask as well carries over whether the sign was known: an unknown + * sign bit leaves every high bit unknown. + */ + a = tnum_cast(a, size); + return TNUM((s64)(a.value << shift) >> shift, + (s64)(a.mask << shift) >> shift); +} + bool tnum_is_aligned(struct tnum a, u64 size) { if (!size) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index eb093194e2a3..308ff53232f0 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -5708,6 +5708,16 @@ static void zext_32_to_64(struct bpf_reg_state *reg) reg_set_urange64(reg, reg_u32_min(reg), reg_u32_max(reg)); } +/* + * The sign-extending counterpart. Signed bounds carry over directly because + * sign extension is monotonic over the signed 32-bit range. + */ +static void sext_32_to_64(struct bpf_reg_state *reg) +{ + reg->var_off = tnum_sext(reg->var_off, 4); + reg_set_srange64(reg, reg_s32_min(reg), reg_s32_max(reg)); +} + /* truncate register to smaller size (in bytes) * must be called with size < BPF_REG_SIZE */ @@ -16248,12 +16258,23 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) return -EACCES; } else if (src_reg->type == SCALAR_VALUE) { bool no_sext; + /* + * A 32-bit sign extension keeps the low 32 + * bits, so record a low-32 link as the + * zero-extending mov does. A self-mov + * qualifies only if src is already linked. + */ + bool subreg_link = (insn->off >> 3) == 4 && + (src_reg != dst_reg || + src_reg->id); no_sext = reg_umax(src_reg) < (1ULL << (insn->off - 1)); - if (no_sext) + if (no_sext || subreg_link) assign_scalar_id_before_mov(env, src_reg); *dst_reg = *src_reg; - if (!no_sext) + if (!no_sext && subreg_link && src_reg->id) + dst_reg->subreg = SUBREG_SEXT; + else if (!no_sext) clear_scalar_id(dst_reg); coerce_reg_to_size_sx(dst_reg, insn->off >> 3); } else { @@ -17165,6 +17186,23 @@ static void reconstruct_zext32(struct bpf_reg_state *reg, reg_bounds_sync(reg); } +/* + * The sign-extending counterpart. Note this drives off the base's 32-bit + * range, not coerce_reg_to_size_sx(): after a 32-bit compare it is the low + * half that has been narrowed, and the 64-bit bounds still describe the + * base's high bits, which are not ours. + */ +static void reconstruct_sext32(struct bpf_reg_state *reg, + struct bpf_reg_state *known_reg) +{ + enum bpf_subreg subreg = reg->subreg; + + *reg = *known_reg; + reg->subreg = subreg; + sext_32_to_64(reg); + reg_bounds_sync(reg); +} + /* For all R in linked_regs, copy known_reg range into R * if R->id == known_reg->id. */ @@ -17192,7 +17230,10 @@ static void sync_linked_regs(struct bpf_verifier_env *env, struct bpf_verifier_s if (reg->subreg) { if (reg->add_const || known_reg->add_const) continue; - reconstruct_zext32(reg, known_reg); + if (reg->subreg == SUBREG_ZEXT) + reconstruct_zext32(reg, known_reg); + else + reconstruct_sext32(reg, known_reg); if (e->is_reg) mark_reg_scratched(env, e->regno); else -- 2.53.0-Meta
