From: Alexei Starovoitov A register is a cnum64 and a cnum32. scev.c does not compute with them: struct scev_value has the eight bounds umin .. s32_max and adds them by hand, with four checks for wrap-around. [-1, 0] + 1 is 'any number' as an unsigned range, and [0, 1] as a cnum. A later patch moves scev.c to cnum. These operations are missing or open coded: - cnum{32,64}_const(v). verifier.c has cnum{32,64}_from_urange(imm, imm) in three functions. - cnum{32,64}_sub(a, b). verifier.c has cnum{32,64}_add(a, cnum{32,64}_negate(b)) in three functions. - cnum64_zext32(), cnum64_sext32(). They move from scev.c to cnum.c. Convert the users. ___mark_reg_known() follows when it moves to struct scalar. Like add, negate and intersect the two extensions now give an empty range for an empty range. They gave [0, U32_MAX] and all of s64. Their user, linear_bounds(), has no empty range to pass. No other functional change. Suggested-by: Eduard Zingerman Signed-off-by: Alexei Starovoitov --- include/linux/cnum.h | 6 ++++++ kernel/bpf/cnum.c | 19 +++++++++++++++++++ kernel/bpf/cnum_defs.h | 11 +++++++++++ kernel/bpf/scev.c | 10 ---------- kernel/bpf/verifier.c | 12 ++++++------ 5 files changed, 42 insertions(+), 16 deletions(-) diff --git a/include/linux/cnum.h b/include/linux/cnum.h index 49160318adf9..bf514cc0a098 100644 --- a/include/linux/cnum.h +++ b/include/linux/cnum.h @@ -33,6 +33,7 @@ struct cnum32 { #define CNUM32_UNBOUNDED ((struct cnum32){ .base = 0, .size = U32_MAX }) #define CNUM32_EMPTY ((struct cnum32){ .base = U32_MAX, .size = U32_MAX }) +struct cnum32 cnum32_const(u32 v); struct cnum32 cnum32_from_urange(u32 min, u32 max); struct cnum32 cnum32_from_srange(s32 min, s32 max); u32 cnum32_umin(struct cnum32 cnum); @@ -49,6 +50,7 @@ bool cnum32_is_const(struct cnum32 cnum); bool cnum32_is_empty(struct cnum32 cnum); struct cnum32 cnum32_add(struct cnum32 a, struct cnum32 b); struct cnum32 cnum32_negate(struct cnum32 a); +struct cnum32 cnum32_sub(struct cnum32 a, struct cnum32 b); bool cnum32_is_subset(struct cnum32 outer, struct cnum32 inner); /* Same as cnum32 but for 64-bit ranges */ @@ -60,6 +62,7 @@ struct cnum64 { #define CNUM64_UNBOUNDED ((struct cnum64){ .base = 0, .size = U64_MAX }) #define CNUM64_EMPTY ((struct cnum64){ .base = U64_MAX, .size = U64_MAX }) +struct cnum64 cnum64_const(u64 v); struct cnum64 cnum64_from_urange(u64 min, u64 max); struct cnum64 cnum64_from_srange(s64 min, s64 max); u64 cnum64_umin(struct cnum64 cnum); @@ -76,9 +79,12 @@ bool cnum64_is_const(struct cnum64 cnum); bool cnum64_is_empty(struct cnum64 cnum); struct cnum64 cnum64_add(struct cnum64 a, struct cnum64 b); struct cnum64 cnum64_negate(struct cnum64 a); +struct cnum64 cnum64_sub(struct cnum64 a, struct cnum64 b); bool cnum64_is_subset(struct cnum64 outer, struct cnum64 inner); struct cnum32 cnum32_from_cnum64(struct cnum64 cnum); +struct cnum64 cnum64_zext32(struct cnum32 cnum); +struct cnum64 cnum64_sext32(struct cnum32 cnum); struct cnum64 cnum64_cnum32_intersect(struct cnum64 a, struct cnum32 b); struct cnum64 cnum64_intersect_linear(struct cnum64 in, u16 base, u16 step); diff --git a/kernel/bpf/cnum.c b/kernel/bpf/cnum.c index 8ec5187d7c75..21bb6411cfb8 100644 --- a/kernel/bpf/cnum.c +++ b/kernel/bpf/cnum.c @@ -23,6 +23,25 @@ struct cnum32 cnum32_from_cnum64(struct cnum64 cnum) return (struct cnum32){ .base = (u32)cnum.base, .size = cnum.size }; } +/* The zero extension of each value of 'cnum'. An arc that crosses U32_MAX/0 gives [0, U32_MAX]. */ +struct cnum64 cnum64_zext32(struct cnum32 cnum) +{ + if (cnum32_is_empty(cnum)) + return CNUM64_EMPTY; + return cnum64_from_urange(cnum32_umin(cnum), cnum32_umax(cnum)); +} + +/* + * The sign extension of each value of 'cnum'. + * An arc that crosses S32_MAX/S32_MIN gives [S32_MIN, S32_MAX]. + */ +struct cnum64 cnum64_sext32(struct cnum32 cnum) +{ + if (cnum32_is_empty(cnum)) + return CNUM64_EMPTY; + return cnum64_from_srange(cnum32_smin(cnum), cnum32_smax(cnum)); +} + /* * Suppose 'a' and 'b' are laid out as follows: * diff --git a/kernel/bpf/cnum_defs.h b/kernel/bpf/cnum_defs.h index 05b17a8b4814..56d0c6f555a8 100644 --- a/kernel/bpf/cnum_defs.h +++ b/kernel/bpf/cnum_defs.h @@ -20,6 +20,11 @@ #define EMPTY __PASTE(__PASTE(CNUM, T), _EMPTY) #define FN(name) __PASTE(__PASTE(cnum, T), __PASTE(_, name)) +struct cnum_t FN(const)(ut v) +{ + return (struct cnum_t){ .base = v, .size = 0 }; +} + struct cnum_t FN(from_urange)(ut min, ut max) { return (struct cnum_t){ .base = min, .size = (ut)max - min }; @@ -259,6 +264,12 @@ struct cnum_t FN(negate)(struct cnum_t a) return FN(normalize)((struct cnum_t){ -((ut)a.base + a.size), a.size }); } +/* { x - y : x in 'a', y in 'b' } */ +struct cnum_t FN(sub)(struct cnum_t a, struct cnum_t b) +{ + return FN(add)(a, FN(negate)(b)); +} + bool FN(is_empty)(struct cnum_t cnum) { return cnum.base == EMPTY.base && cnum.size == EMPTY.size; diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c index 8438313e7b4a..a477a3029baa 100644 --- a/kernel/bpf/scev.c +++ b/kernel/bpf/scev.c @@ -4453,16 +4453,6 @@ static struct bpf_reg_state *spill32_counter(struct scev *scev, struct bpf_func_ return scev_reg_for_spill32(st, r); } -static struct cnum64 cnum64_zext32(struct cnum32 r32) -{ - return cnum64_from_urange(cnum32_umin(r32), cnum32_umax(r32)); -} - -static struct cnum64 cnum64_sext32(struct cnum32 r32) -{ - return cnum64_from_srange(cnum32_smin(r32), cnum32_smax(r32)); -} - /* Compute the range an induction variable in `reg` spans over the loop. */ static void linear_bounds(struct bpf_reg_state *reg, u32 max_header_count, struct linear_coefs *coefs, struct bounds *out) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index c9c6b1367a0b..1f33e69b4aee 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -2020,7 +2020,7 @@ void bpf_mark_reg_known_scalar(struct bpf_reg_state *reg, u64 imm) static void __mark_reg32_known(struct bpf_reg_state *reg, u64 imm) { reg->var_off = tnum_const_subreg(reg->var_off, imm); - reg->r32 = cnum32_from_urange((u32)imm, (u32)imm); + reg->r32 = cnum32_const(imm); } /* Mark the 'variable offset' part of a register as zero. This should be @@ -6345,8 +6345,8 @@ static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size) reg->var_off = tnum_const((s32)u64_cval); u64_cval = reg->var_off.value; - reg->r64 = cnum64_from_urange(u64_cval, u64_cval); - reg->r32 = cnum32_from_urange((u32)u64_cval, (u32)u64_cval); + reg->r64 = cnum64_const(u64_cval); + reg->r32 = cnum32_const(u64_cval); return; } @@ -17077,7 +17077,7 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env, struct bpf_insn "Use addition from R10 to form stack addresses within the tracked stack frame."); return -EACCES; } - dst_reg->r64 = cnum64_add(ptr_reg->r64, cnum64_negate(off_reg->r64)); + dst_reg->r64 = cnum64_sub(ptr_reg->r64, off_reg->r64); dst_reg->var_off = tnum_sub(ptr_reg->var_off, off_reg->var_off); dst_reg->raw = ptr_reg->raw; if (reg_is_pkt_pointer(ptr_reg)) { @@ -17184,13 +17184,13 @@ static void scalar_min_max_add(struct bpf_reg_state *dst_reg, static void scalar32_min_max_sub(struct bpf_reg_state *dst_reg, struct bpf_reg_state *src_reg) { - dst_reg->r32 = cnum32_add(dst_reg->r32, cnum32_negate(src_reg->r32)); + dst_reg->r32 = cnum32_sub(dst_reg->r32, src_reg->r32); } static void scalar_min_max_sub(struct bpf_reg_state *dst_reg, struct bpf_reg_state *src_reg) { - dst_reg->r64 = cnum64_add(dst_reg->r64, cnum64_negate(src_reg->r64)); + dst_reg->r64 = cnum64_sub(dst_reg->r64, src_reg->r64); } static void scalar32_min_max_mul(struct bpf_reg_state *dst_reg, -- 2.55.0