From f1174f77b50c94eecaa658fdc56fa69b421de4b8 Mon Sep 17 00:00:00 2001 From: Edward Cree Date: Mon, 7 Aug 2017 15:26:19 +0100 Subject: bpf/verifier: rework value tracking Unifies adjusted and unadjusted register value types (e.g. FRAME_POINTER is now just a PTR_TO_STACK with zero offset). Tracks value alignment by means of tracking known & unknown bits. This also replaces the 'reg->imm' (leading zero bits) calculations for (what were) UNKNOWN_VALUEs. If pointer leaks are allowed, and adjust_ptr_min_max_vals returns -EACCES, treat the pointer as an unknown scalar and try again, because we might be able to conclude something about the result (e.g. pointer & 0x40 is either 0 or 0x40). Verifier hooks in the netronome/nfp driver were changed to match the new data structures. Signed-off-by: Edward Cree Signed-off-by: David S. Miller --- include/linux/bpf.h | 34 +++++++------------ include/linux/bpf_verifier.h | 34 +++++++++++-------- include/linux/tnum.h | 79 ++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 112 insertions(+), 35 deletions(-) create mode 100644 include/linux/tnum.h (limited to 'include/linux') diff --git a/include/linux/bpf.h b/include/linux/bpf.h index 6353c7474dba..39229c455cba 100644 --- a/include/linux/bpf.h +++ b/include/linux/bpf.h @@ -117,35 +117,25 @@ enum bpf_access_type { }; /* types of values stored in eBPF registers */ +/* Pointer types represent: + * pointer + * pointer + imm + * pointer + (u16) var + * pointer + (u16) var + imm + * if (range > 0) then [ptr, ptr + range - off) is safe to access + * if (id > 0) means that some 'var' was added + * if (off > 0) means that 'imm' was added + */ enum bpf_reg_type { NOT_INIT = 0, /* nothing was written into register */ - UNKNOWN_VALUE, /* reg doesn't contain a valid pointer */ + SCALAR_VALUE, /* reg doesn't contain a valid pointer */ PTR_TO_CTX, /* reg points to bpf_context */ CONST_PTR_TO_MAP, /* reg points to struct bpf_map */ PTR_TO_MAP_VALUE, /* reg points to map element value */ PTR_TO_MAP_VALUE_OR_NULL,/* points to map elem value or NULL */ - FRAME_PTR, /* reg == frame_pointer */ - PTR_TO_STACK, /* reg == frame_pointer + imm */ - CONST_IMM, /* constant integer value */ - - /* PTR_TO_PACKET represents: - * skb->data - * skb->data + imm - * skb->data + (u16) var - * skb->data + (u16) var + imm - * if (range > 0) then [ptr, ptr + range - off) is safe to access - * if (id > 0) means that some 'var' was added - * if (off > 0) menas that 'imm' was added - */ - PTR_TO_PACKET, + PTR_TO_STACK, /* reg == frame_pointer + offset */ + PTR_TO_PACKET, /* reg points to skb->data */ PTR_TO_PACKET_END, /* skb->data + headlen */ - - /* PTR_TO_MAP_VALUE_ADJ is used for doing pointer math inside of a map - * elem value. We only allow this if we can statically verify that - * access from this register are going to fall within the size of the - * map element. - */ - PTR_TO_MAP_VALUE_ADJ, }; struct bpf_prog; diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 8e5d31f6faef..85936fa92d12 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -9,6 +9,7 @@ #include /* for enum bpf_reg_type */ #include /* for MAX_BPF_STACK */ +#include /* Just some arbitrary values so we can safely do math without overflowing and * are obviously wrong for any sort of memory access. @@ -19,30 +20,37 @@ struct bpf_reg_state { enum bpf_reg_type type; union { - /* valid when type == CONST_IMM | PTR_TO_STACK | UNKNOWN_VALUE */ - s64 imm; - - /* valid when type == PTR_TO_PACKET* */ - struct { - u16 off; - u16 range; - }; + /* valid when type == PTR_TO_PACKET */ + u16 range; /* valid when type == CONST_PTR_TO_MAP | PTR_TO_MAP_VALUE | * PTR_TO_MAP_VALUE_OR_NULL */ struct bpf_map *map_ptr; }; + /* Fixed part of pointer offset, pointer types only */ + s32 off; + /* For PTR_TO_PACKET, used to find other pointers with the same variable + * offset, so they can share range knowledge. + * For PTR_TO_MAP_VALUE_OR_NULL this is used to share which map value we + * came from, when one is tested for != NULL. + */ u32 id; + /* These three fields must be last. See states_equal() */ + /* For scalar types (SCALAR_VALUE), this represents our knowledge of + * the actual value. + * For pointer types, this represents the variable part of the offset + * from the pointed-to object, and is shared with all bpf_reg_states + * with the same id as us. + */ + struct tnum var_off; /* Used to determine if any memory access using this register will - * result in a bad access. These two fields must be last. - * See states_equal() + * result in a bad access. + * These refer to the same value as var_off, not necessarily the actual + * contents of the register. */ s64 min_value; u64 max_value; - u32 min_align; - u32 aux_off; - u32 aux_off_align; bool value_from_signed; }; diff --git a/include/linux/tnum.h b/include/linux/tnum.h new file mode 100644 index 000000000000..a0b07bf1842b --- /dev/null +++ b/include/linux/tnum.h @@ -0,0 +1,79 @@ +/* tnum: tracked (or tristate) numbers + * + * A tnum tracks knowledge about the bits of a value. Each bit can be either + * known (0 or 1), or unknown (x). Arithmetic operations on tnums will + * propagate the unknown bits such that the tnum result represents all the + * possible results for possible values of the operands. + */ +#include + +struct tnum { + u64 value; + u64 mask; +}; + +/* Constructors */ +/* Represent a known constant as a tnum. */ +struct tnum tnum_const(u64 value); +/* A completely unknown value */ +extern const struct tnum tnum_unknown; + +/* Arithmetic and logical ops */ +/* Shift a tnum left (by a fixed shift) */ +struct tnum tnum_lshift(struct tnum a, u8 shift); +/* Shift a tnum right (by a fixed shift) */ +struct tnum tnum_rshift(struct tnum a, u8 shift); +/* Add two tnums, return @a + @b */ +struct tnum tnum_add(struct tnum a, struct tnum b); +/* Subtract two tnums, return @a - @b */ +struct tnum tnum_sub(struct tnum a, struct tnum b); +/* Bitwise-AND, return @a & @b */ +struct tnum tnum_and(struct tnum a, struct tnum b); +/* Bitwise-OR, return @a | @b */ +struct tnum tnum_or(struct tnum a, struct tnum b); +/* Bitwise-XOR, return @a ^ @b */ +struct tnum tnum_xor(struct tnum a, struct tnum b); +/* Multiply two tnums, return @a * @b */ +struct tnum tnum_mul(struct tnum a, struct tnum b); + +/* Return a tnum representing numbers satisfying both @a and @b */ +struct tnum tnum_intersect(struct tnum a, struct tnum b); + +/* Return @a with all but the lowest @size bytes cleared */ +struct tnum tnum_cast(struct tnum a, u8 size); + +/* Returns true if @a is a known constant */ +static inline bool tnum_is_const(struct tnum a) +{ + return !a.mask; +} + +/* Returns true if @a == tnum_const(@b) */ +static inline bool tnum_equals_const(struct tnum a, u64 b) +{ + return tnum_is_const(a) && a.value == b; +} + +/* Returns true if @a is completely unknown */ +static inline bool tnum_is_unknown(struct tnum a) +{ + return !~a.mask; +} + +/* Returns true if @a is known to be a multiple of @size. + * @size must be a power of two. + */ +bool tnum_is_aligned(struct tnum a, u64 size); + +/* Returns true if @b represents a subset of @a. */ +bool tnum_in(struct tnum a, struct tnum b); + +/* Formatting functions. These have snprintf-like semantics: they will write + * up to @size bytes (including the terminating NUL byte), and return the number + * of bytes (excluding the terminating NUL) which would have been written had + * sufficient space been available. (Thus tnum_sbin always returns 64.) + */ +/* Format a tnum as a pair of hex numbers (value; mask) */ +int tnum_strn(char *str, size_t size, struct tnum a); +/* Format a tnum as tristate binary expansion */ +int tnum_sbin(char *str, size_t size, struct tnum a); -- cgit v1.2.3 From b03c9f9fdc37dab81ea04d5dacdc5995d4c224c2 Mon Sep 17 00:00:00 2001 From: Edward Cree Date: Mon, 7 Aug 2017 15:26:36 +0100 Subject: bpf/verifier: track signed and unsigned min/max values Allows us to, sometimes, combine information from a signed check of one bound and an unsigned check of the other. We now track the full range of possible values, rather than restricting ourselves to [0, 1<<30) and considering anything beyond that as unknown. While this is probably not necessary, it makes the code more straightforward and symmetrical between signed and unsigned bounds. Signed-off-by: Edward Cree Signed-off-by: David S. Miller --- include/linux/bpf_verifier.h | 23 +- include/linux/tnum.h | 2 + kernel/bpf/tnum.c | 16 + kernel/bpf/verifier.c | 737 +++++++++++++++++++++++++------------------ 4 files changed, 461 insertions(+), 317 deletions(-) (limited to 'include/linux') diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h index 85936fa92d12..c61c3033522e 100644 --- a/include/linux/bpf_verifier.h +++ b/include/linux/bpf_verifier.h @@ -11,11 +11,15 @@ #include /* for MAX_BPF_STACK */ #include - /* Just some arbitrary values so we can safely do math without overflowing and - * are obviously wrong for any sort of memory access. - */ -#define BPF_REGISTER_MAX_RANGE (1024 * 1024 * 1024) -#define BPF_REGISTER_MIN_RANGE -1 +/* Maximum variable offset umax_value permitted when resolving memory accesses. + * In practice this is far bigger than any realistic pointer offset; this limit + * ensures that umax_value + (int)off + (int)size cannot overflow a u64. + */ +#define BPF_MAX_VAR_OFF (1ULL << 31) +/* Maximum variable size permitted for ARG_CONST_SIZE[_OR_ZERO]. This ensures + * that converting umax_value to int cannot overflow. + */ +#define BPF_MAX_VAR_SIZ INT_MAX struct bpf_reg_state { enum bpf_reg_type type; @@ -36,7 +40,7 @@ struct bpf_reg_state { * came from, when one is tested for != NULL. */ u32 id; - /* These three fields must be last. See states_equal() */ + /* These five fields must be last. See states_equal() */ /* For scalar types (SCALAR_VALUE), this represents our knowledge of * the actual value. * For pointer types, this represents the variable part of the offset @@ -49,9 +53,10 @@ struct bpf_reg_state { * These refer to the same value as var_off, not necessarily the actual * contents of the register. */ - s64 min_value; - u64 max_value; - bool value_from_signed; + s64 smin_value; /* minimum possible (s64)value */ + s64 smax_value; /* maximum possible (s64)value */ + u64 umin_value; /* minimum possible (u64)value */ + u64 umax_value; /* maximum possible (u64)value */ }; enum bpf_stack_slot_type { diff --git a/include/linux/tnum.h b/include/linux/tnum.h index a0b07bf1842b..0d2d3da46139 100644 --- a/include/linux/tnum.h +++ b/include/linux/tnum.h @@ -17,6 +17,8 @@ struct tnum { struct tnum tnum_const(u64 value); /* A completely unknown value */ extern const struct tnum tnum_unknown; +/* A value that's unknown except that @min <= value <= @max */ +struct tnum tnum_range(u64 min, u64 max); /* Arithmetic and logical ops */ /* Shift a tnum left (by a fixed shift) */ diff --git a/kernel/bpf/tnum.c b/kernel/bpf/tnum.c index 92eeeb1974a2..1f4bf68c12db 100644 --- a/kernel/bpf/tnum.c +++ b/kernel/bpf/tnum.c @@ -17,6 +17,22 @@ struct tnum tnum_const(u64 value) return TNUM(value, 0); } +struct tnum tnum_range(u64 min, u64 max) +{ + u64 chi = min ^ max, delta; + u8 bits = fls64(chi); + + /* special case, needed because 1ULL << 64 is undefined */ + if (bits > 63) + return tnum_unknown; + /* e.g. if chi = 4, bits = 3, delta = (1<<3) - 1 = 7. + * if chi = 0, bits = 0, delta = (1<<0) - 1 = 0, so we return + * constant min (since min == max). + */ + delta = (1ULL << bits) - 1; + return TNUM(min & ~delta, delta); +} + struct tnum tnum_lshift(struct tnum a, u8 shift) { return TNUM(a.value << shift, a.mask << shift); diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index c3f88b466c30..7557800bf7a7 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -234,12 +234,20 @@ static void print_verifier_state(struct bpf_verifier_state *state) verbose(",ks=%d,vs=%d", reg->map_ptr->key_size, reg->map_ptr->value_size); - if (reg->min_value != BPF_REGISTER_MIN_RANGE) - verbose(",min_value=%lld", - (long long)reg->min_value); - if (reg->max_value != BPF_REGISTER_MAX_RANGE) - verbose(",max_value=%llu", - (unsigned long long)reg->max_value); + if (reg->smin_value != reg->umin_value && + reg->smin_value != S64_MIN) + verbose(",smin_value=%lld", + (long long)reg->smin_value); + if (reg->smax_value != reg->umax_value && + reg->smax_value != S64_MAX) + verbose(",smax_value=%lld", + (long long)reg->smax_value); + if (reg->umin_value != 0) + verbose(",umin_value=%llu", + (unsigned long long)reg->umin_value); + if (reg->umax_value != U64_MAX) + verbose(",umax_value=%llu", + (unsigned long long)reg->umax_value); if (!tnum_is_unknown(reg->var_off)) { char tn_buf[48]; @@ -466,14 +474,25 @@ static const int caller_saved[CALLER_SAVED_REGS] = { static void __mark_reg_not_init(struct bpf_reg_state *reg); +/* Mark the unknown part of a register (variable offset or scalar value) as + * known to have the value @imm. + */ +static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm) +{ + reg->id = 0; + reg->var_off = tnum_const(imm); + reg->smin_value = (s64)imm; + reg->smax_value = (s64)imm; + reg->umin_value = imm; + reg->umax_value = imm; +} + /* Mark the 'variable offset' part of a register as zero. This should be * used only on registers holding a pointer type. */ static void __mark_reg_known_zero(struct bpf_reg_state *reg) { - reg->var_off = tnum_const(0); - reg->min_value = 0; - reg->max_value = 0; + __mark_reg_known(reg, 0); } static void mark_reg_known_zero(struct bpf_reg_state *regs, u32 regno) @@ -488,6 +507,72 @@ static void mark_reg_known_zero(struct bpf_reg_state *regs, u32 regno) __mark_reg_known_zero(regs + regno); } +/* Attempts to improve min/max values based on var_off information */ +static void __update_reg_bounds(struct bpf_reg_state *reg) +{ + /* min signed is max(sign bit) | min(other bits) */ + reg->smin_value = max_t(s64, reg->smin_value, + reg->var_off.value | (reg->var_off.mask & S64_MIN)); + /* max signed is min(sign bit) | max(other bits) */ + reg->smax_value = min_t(s64, reg->smax_value, + reg->var_off.value | (reg->var_off.mask & S64_MAX)); + reg->umin_value = max(reg->umin_value, reg->var_off.value); + reg->umax_value = min(reg->umax_value, + reg->var_off.value | reg->var_off.mask); +} + +/* Uses signed min/max values to inform unsigned, and vice-versa */ +static void __reg_deduce_bounds(struct bpf_reg_state *reg) +{ + /* Learn sign from signed bounds. + * If we cannot cross the sign boundary, then signed and unsigned bounds + * are the same, so combine. This works even in the negative case, e.g. + * -3 s<= x s<= -1 implies 0xf...fd u<= x u<= 0xf...ff. + */ + if (reg->smin_value >= 0 || reg->smax_value < 0) { + reg->smin_value = reg->umin_value = max_t(u64, reg->smin_value, + reg->umin_value); + reg->smax_value = reg->umax_value = min_t(u64, reg->smax_value, + reg->umax_value); + return; + } + /* Learn sign from unsigned bounds. Signed bounds cross the sign + * boundary, so we must be careful. + */ + if ((s64)reg->umax_value >= 0) { + /* Positive. We can't learn anything from the smin, but smax + * is positive, hence safe. + */ + reg->smin_value = reg->umin_value; + reg->smax_value = reg->umax_value = min_t(u64, reg->smax_value, + reg->umax_value); + } else if ((s64)reg->umin_value < 0) { + /* Negative. We can't learn anything from the smax, but smin + * is negative, hence safe. + */ + reg->smin_value = reg->umin_value = max_t(u64, reg->smin_value, + reg->umin_value); + reg->smax_value = reg->umax_value; + } +} + +/* Attempts to improve var_off based on unsigned min/max information */ +static void __reg_bound_offset(struct bpf_reg_state *reg) +{ + reg->var_off = tnum_intersect(reg->var_off, + tnum_range(reg->umin_value, + reg->umax_value)); +} + +/* Reset the min/max bounds of a register */ +static void __mark_reg_unbounded(struct bpf_reg_state *reg) +{ + reg->smin_value = S64_MIN; + reg->smax_value = S64_MAX; + reg->umin_value = 0; + reg->umax_value = U64_MAX; +} + /* Mark a register as having a completely unknown (scalar) value. */ static void __mark_reg_unknown(struct bpf_reg_state *reg) { @@ -495,8 +580,7 @@ static void __mark_reg_unknown(struct bpf_reg_state *reg) reg->id = 0; reg->off = 0; reg->var_off = tnum_unknown; - reg->min_value = BPF_REGISTER_MIN_RANGE; - reg->max_value = BPF_REGISTER_MAX_RANGE; + __mark_reg_unbounded(reg); } static void mark_reg_unknown(struct bpf_reg_state *regs, u32 regno) @@ -545,13 +629,6 @@ static void init_reg_state(struct bpf_reg_state *regs) mark_reg_known_zero(regs, BPF_REG_1); } -static void reset_reg_range_values(struct bpf_reg_state *regs, u32 regno) -{ - regs[regno].min_value = BPF_REGISTER_MIN_RANGE; - regs[regno].max_value = BPF_REGISTER_MAX_RANGE; - regs[regno].value_from_signed = false; -} - enum reg_arg_type { SRC_OP, /* register is used as source operand */ DST_OP, /* register is used as destination operand */ @@ -716,26 +793,27 @@ static int check_map_access(struct bpf_verifier_env *env, u32 regno, * index'es we need to make sure that whatever we use * will have a set floor within our range. */ - if (reg->min_value < 0) { + if (reg->smin_value < 0) { verbose("R%d min value is negative, either use unsigned index or do a if (index >=0) check.\n", regno); return -EACCES; } - err = __check_map_access(env, regno, reg->min_value + off, size); + err = __check_map_access(env, regno, reg->smin_value + off, size); if (err) { verbose("R%d min value is outside of the array range\n", regno); return err; } - /* If we haven't set a max value then we need to bail - * since we can't be sure we won't do bad things. + /* If we haven't set a max value then we need to bail since we can't be + * sure we won't do bad things. + * If reg->umax_value + off could overflow, treat that as unbounded too. */ - if (reg->max_value == BPF_REGISTER_MAX_RANGE) { + if (reg->umax_value >= BPF_MAX_VAR_OFF) { verbose("R%d unbounded memory access, make sure to bounds check any array access into a map\n", regno); return -EACCES; } - err = __check_map_access(env, regno, reg->max_value + off, size); + err = __check_map_access(env, regno, reg->umax_value + off, size); if (err) verbose("R%d max value is outside of the array range\n", regno); return err; @@ -797,7 +875,7 @@ static int check_packet_access(struct bpf_verifier_env *env, u32 regno, int off, /* We don't allow negative numbers, because we aren't tracking enough * detail to prove they're safe. */ - if (reg->min_value < 0) { + if (reg->smin_value < 0) { verbose("R%d min value is negative, either use unsigned index or do a if (index >=0) check.\n", regno); return -EACCES; @@ -1070,12 +1148,7 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn /* b/h/w load zero-extends, mark upper bits as known 0 */ state->regs[value_regno].var_off = tnum_cast( state->regs[value_regno].var_off, size); - /* sign bit is known zero, so we can bound the value */ - state->regs[value_regno].min_value = 0; - state->regs[value_regno].max_value = min_t(u64, - state->regs[value_regno].var_off.value | - state->regs[value_regno].var_off.mask, - BPF_REGISTER_MAX_RANGE); + __update_reg_bounds(&state->regs[value_regno]); } return err; } @@ -1333,13 +1406,13 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 regno, */ meta = NULL; - if (reg->min_value < 0) { + if (reg->smin_value < 0) { verbose("R%d min value is negative, either use unsigned or 'var &= const'\n", regno); return -EACCES; } - if (reg->min_value == 0) { + if (reg->umin_value == 0) { err = check_helper_mem_access(env, regno - 1, 0, zero_size_allowed, meta); @@ -1347,13 +1420,13 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 regno, return err; } - if (reg->max_value == BPF_REGISTER_MAX_RANGE) { + if (reg->umax_value >= BPF_MAX_VAR_SIZ) { verbose("R%d unbounded memory access, use 'var &= const' or 'if (var < const)'\n", regno); return -EACCES; } err = check_helper_mem_access(env, regno - 1, - reg->max_value, + reg->umax_value, zero_size_allowed, meta); } @@ -1600,33 +1673,35 @@ static int check_call(struct bpf_verifier_env *env, int func_id, int insn_idx) return 0; } -static void check_reg_overflow(struct bpf_reg_state *reg) -{ - if (reg->max_value > BPF_REGISTER_MAX_RANGE) - reg->max_value = BPF_REGISTER_MAX_RANGE; - if (reg->min_value < BPF_REGISTER_MIN_RANGE || - reg->min_value > BPF_REGISTER_MAX_RANGE) - reg->min_value = BPF_REGISTER_MIN_RANGE; -} - static void coerce_reg_to_32(struct bpf_reg_state *reg) { - /* 32-bit values can't be negative as an s64 */ - if (reg->min_value < 0) - reg->min_value = 0; /* clear high 32 bits */ reg->var_off = tnum_cast(reg->var_off, 4); - /* Did value become known? Then update bounds */ - if (tnum_is_const(reg->var_off)) { - if ((s64)reg->var_off.value > BPF_REGISTER_MIN_RANGE) - reg->min_value = reg->var_off.value; - if (reg->var_off.value < BPF_REGISTER_MAX_RANGE) - reg->max_value = reg->var_off.value; - } + /* Update bounds */ + __update_reg_bounds(reg); +} + +static bool signed_add_overflows(s64 a, s64 b) +{ + /* Do the add in u64, where overflow is well-defined */ + s64 res = (s64)((u64)a + (u64)b); + + if (b < 0) + return res > a; + return res < a; +} + +static bool signed_sub_overflows(s64 a, s64 b) +{ + /* Do the sub in u64, where overflow is well-defined */ + s64 res = (s64)((u64)a - (u64)b); + + if (b < 0) + return res < a; + return res > a; } /* Handles arithmetic on a pointer and a scalar: computes new min/max and var_off. - * Caller must check_reg_overflow all argument regs beforehand. * Caller should also handle BPF_MOV case separately. * If we return -EACCES, caller may want to try again treating pointer as a * scalar. So we only emit a diagnostic if !env->allow_ptr_leaks. @@ -1638,16 +1713,23 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env, { struct bpf_reg_state *regs = env->cur_state.regs, *dst_reg; bool known = tnum_is_const(off_reg->var_off); - s64 min_val = off_reg->min_value; - u64 max_val = off_reg->max_value; + s64 smin_val = off_reg->smin_value, smax_val = off_reg->smax_value, + smin_ptr = ptr_reg->smin_value, smax_ptr = ptr_reg->smax_value; + u64 umin_val = off_reg->umin_value, umax_val = off_reg->umax_value, + umin_ptr = ptr_reg->umin_value, umax_ptr = ptr_reg->umax_value; u8 opcode = BPF_OP(insn->code); u32 dst = insn->dst_reg; dst_reg = ®s[dst]; - if (WARN_ON_ONCE(known && (min_val != max_val))) { + if (WARN_ON_ONCE(known && (smin_val != smax_val))) { + print_verifier_state(&env->cur_state); + verbose("verifier internal error: known but bad sbounds\n"); + return -EINVAL; + } + if (WARN_ON_ONCE(known && (umin_val != umax_val))) { print_verifier_state(&env->cur_state); - verbose("verifier internal error\n"); + verbose("verifier internal error: known but bad ubounds\n"); return -EINVAL; } @@ -1689,22 +1771,18 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env, /* We can take a fixed offset as long as it doesn't overflow * the s32 'off' field */ - if (known && (ptr_reg->off + min_val == - (s64)(s32)(ptr_reg->off + min_val))) { + if (known && (ptr_reg->off + smin_val == + (s64)(s32)(ptr_reg->off + smin_val))) { /* pointer += K. Accumulate it into fixed offset */ - dst_reg->min_value = ptr_reg->min_value; - dst_reg->max_value = ptr_reg->max_value; + dst_reg->smin_value = smin_ptr; + dst_reg->smax_value = smax_ptr; + dst_reg->umin_value = umin_ptr; + dst_reg->umax_value = umax_ptr; dst_reg->var_off = ptr_reg->var_off; - dst_reg->off = ptr_reg->off + min_val; + dst_reg->off = ptr_reg->off + smin_val; dst_reg->range = ptr_reg->range; break; } - if (max_val == BPF_REGISTER_MAX_RANGE) { - if (!env->allow_ptr_leaks) - verbose("R%d tried to add unbounded value to pointer\n", - dst); - return -EACCES; - } /* A new variable offset is created. Note that off_reg->off * == 0, since it's a scalar. * dst_reg gets the pointer type and since some positive @@ -1714,12 +1792,22 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env, * added into the variable offset, and we copy the fixed offset * from ptr_reg. */ - if (min_val <= BPF_REGISTER_MIN_RANGE) - dst_reg->min_value = BPF_REGISTER_MIN_RANGE; - if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE) - dst_reg->min_value += min_val; - if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE) - dst_reg->max_value += max_val; + if (signed_add_overflows(smin_ptr, smin_val) || + signed_add_overflows(smax_ptr, smax_val)) { + dst_reg->smin_value = S64_MIN; + dst_reg->smax_value = S64_MAX; + } else { + dst_reg->smin_value = smin_ptr + smin_val; + dst_reg->smax_value = smax_ptr + smax_val; + } + if (umin_ptr + umin_val < umin_ptr || + umax_ptr + umax_val < umax_ptr) { + dst_reg->umin_value = 0; + dst_reg->umax_value = U64_MAX; + } else { + dst_reg->umin_value = umin_ptr + umin_val; + dst_reg->umax_value = umax_ptr + umax_val; + } dst_reg->var_off = tnum_add(ptr_reg->var_off, off_reg->var_off); dst_reg->off = ptr_reg->off; if (ptr_reg->type == PTR_TO_PACKET) { @@ -1746,43 +1834,46 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env, dst); return -EACCES; } - if (known && (ptr_reg->off - min_val == - (s64)(s32)(ptr_reg->off - min_val))) { + if (known && (ptr_reg->off - smin_val == + (s64)(s32)(ptr_reg->off - smin_val))) { /* pointer -= K. Subtract it from fixed offset */ - dst_reg->min_value = ptr_reg->min_value; - dst_reg->max_value = ptr_reg->max_value; + dst_reg->smin_value = smin_ptr; + dst_reg->smax_value = smax_ptr; + dst_reg->umin_value = umin_ptr; + dst_reg->umax_value = umax_ptr; dst_reg->var_off = ptr_reg->var_off; dst_reg->id = ptr_reg->id; - dst_reg->off = ptr_reg->off - min_val; + dst_reg->off = ptr_reg->off - smin_val; dst_reg->range = ptr_reg->range; break; } - /* Subtracting a negative value will just confuse everything. - * This can happen if off_reg is an immediate. - */ - if ((s64)max_val < 0) { - if (!env->allow_ptr_leaks) - verbose("R%d tried to subtract negative max_val %lld from pointer\n", - dst, (s64)max_val); - return -EACCES; - } /* A new variable offset is created. If the subtrahend is known * nonnegative, then any reg->range we had before is still good. */ - if (max_val >= BPF_REGISTER_MAX_RANGE) - dst_reg->min_value = BPF_REGISTER_MIN_RANGE; - if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE) - dst_reg->min_value -= max_val; - if (min_val <= BPF_REGISTER_MIN_RANGE) - dst_reg->max_value = BPF_REGISTER_MAX_RANGE; - if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE) - dst_reg->max_value -= min_val; + if (signed_sub_overflows(smin_ptr, smax_val) || + signed_sub_overflows(smax_ptr, smin_val)) { + /* Overflow possible, we know nothing */ + dst_reg->smin_value = S64_MIN; + dst_reg->smax_value = S64_MAX; + } else { + dst_reg->smin_value = smin_ptr - smax_val; + dst_reg->smax_value = smax_ptr - smin_val; + } + if (umin_ptr < umax_val) { + /* Overflow possible, we know nothing */ + dst_reg->umin_value = 0; + dst_reg->umax_value = U64_MAX; + } else { + /* Cannot overflow (as long as bounds are consistent) */ + dst_reg->umin_value = umin_ptr - umax_val; + dst_reg->umax_value = umax_ptr - umin_val; + } dst_reg->var_off = tnum_sub(ptr_reg->var_off, off_reg->var_off); dst_reg->off = ptr_reg->off; if (ptr_reg->type == PTR_TO_PACKET) { dst_reg->id = ++env->id_gen; /* something was added to pkt_ptr, set range to zero */ - if (min_val < 0) + if (smin_val < 0) dst_reg->range = 0; } break; @@ -1805,7 +1896,9 @@ static int adjust_ptr_min_max_vals(struct bpf_verifier_env *env, return -EACCES; } - check_reg_overflow(dst_reg); + __update_reg_bounds(dst_reg); + __reg_deduce_bounds(dst_reg); + __reg_bound_offset(dst_reg); return 0; } @@ -1815,157 +1908,217 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, struct bpf_reg_state src_reg) { struct bpf_reg_state *regs = env->cur_state.regs; - s64 min_val = BPF_REGISTER_MIN_RANGE; - u64 max_val = BPF_REGISTER_MAX_RANGE; u8 opcode = BPF_OP(insn->code); bool src_known, dst_known; + s64 smin_val, smax_val; + u64 umin_val, umax_val; if (BPF_CLASS(insn->code) != BPF_ALU64) { /* 32-bit ALU ops are (32,32)->64 */ coerce_reg_to_32(dst_reg); coerce_reg_to_32(&src_reg); } - min_val = src_reg.min_value; - max_val = src_reg.max_value; + smin_val = src_reg.smin_value; + smax_val = src_reg.smax_value; + umin_val = src_reg.umin_value; + umax_val = src_reg.umax_value; src_known = tnum_is_const(src_reg.var_off); dst_known = tnum_is_const(dst_reg->var_off); switch (opcode) { case BPF_ADD: - if (min_val == BPF_REGISTER_MIN_RANGE) - dst_reg->min_value = BPF_REGISTER_MIN_RANGE; - if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE) - dst_reg->min_value += min_val; - /* if max_val is MAX_RANGE, this will saturate dst->max */ - if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE) - dst_reg->max_value += max_val; + if (signed_add_overflows(dst_reg->smin_value, smin_val) || + signed_add_overflows(dst_reg->smax_value, smax_val)) { + dst_reg->smin_value = S64_MIN; + dst_reg->smax_value = S64_MAX; + } else { + dst_reg->smin_value += smin_val; + dst_reg->smax_value += smax_val; + } + if (dst_reg->umin_value + umin_val < umin_val || + dst_reg->umax_value + umax_val < umax_val) { + dst_reg->umin_value = 0; + dst_reg->umax_value = U64_MAX; + } else { + dst_reg->umin_value += umin_val; + dst_reg->umax_value += umax_val; + } dst_reg->var_off = tnum_add(dst_reg->var_off, src_reg.var_off); break; case BPF_SUB: - if (max_val == BPF_REGISTER_MAX_RANGE) - dst_reg->min_value = BPF_REGISTER_MIN_RANGE; - if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE) - dst_reg->min_value -= max_val; - if (min_val == BPF_REGISTER_MIN_RANGE) - dst_reg->max_value = BPF_REGISTER_MAX_RANGE; - if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE) - dst_reg->max_value -= min_val; + if (signed_sub_overflows(dst_reg->smin_value, smax_val) || + signed_sub_overflows(dst_reg->smax_value, smin_val)) { + /* Overflow possible, we know nothing */ + dst_reg->smin_value = S64_MIN; + dst_reg->smax_value = S64_MAX; + } else { + dst_reg->smin_value -= smax_val; + dst_reg->smax_value -= smin_val; + } + if (dst_reg->umin_value < umax_val) { + /* Overflow possible, we know nothing */ + dst_reg->umin_value = 0; + dst_reg->umax_value = U64_MAX; + } else { + /* Cannot overflow (as long as bounds are consistent) */ + dst_reg->umin_value -= umax_val; + dst_reg->umax_value -= umin_val; + } dst_reg->var_off = tnum_sub(dst_reg->var_off, src_reg.var_off); break; case BPF_MUL: - if (min_val < 0 || dst_reg->min_value < 0) { + dst_reg->var_off = tnum_mul(dst_reg->var_off, src_reg.var_off); + if (smin_val < 0 || dst_reg->smin_value < 0) { /* Ain't nobody got time to multiply that sign */ - __mark_reg_unknown(dst_reg); + __mark_reg_unbounded(dst_reg); + __update_reg_bounds(dst_reg); break; } - dst_reg->min_value *= min_val; - /* if max_val is MAX_RANGE, this will saturate dst->max. - * We know MAX_RANGE ** 2 won't overflow a u64, because - * MAX_RANGE itself fits in a u32. + /* Both values are positive, so we can work with unsigned and + * copy the result to signed (unless it exceeds S64_MAX). */ - BUILD_BUG_ON(BPF_REGISTER_MAX_RANGE > (u32)-1); - if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE) - dst_reg->max_value *= max_val; - dst_reg->var_off = tnum_mul(dst_reg->var_off, src_reg.var_off); + if (umax_val > U32_MAX || dst_reg->umax_value > U32_MAX) { + /* Potential overflow, we know nothing */ + __mark_reg_unbounded(dst_reg); + /* (except what we can learn from the var_off) */ + __update_reg_bounds(dst_reg); + break; + } + dst_reg->umin_value *= umin_val; + dst_reg->umax_value *= umax_val; + if (dst_reg->umax_value > S64_MAX) { + /* Overflow possible, we know nothing */ + dst_reg->smin_value = S64_MIN; + dst_reg->smax_value = S64_MAX; + } else { + dst_reg->smin_value = dst_reg->umin_value; + dst_reg->smax_value = dst_reg->umax_value; + } break; case BPF_AND: if (src_known && dst_known) { - u64 value = dst_reg->var_off.value & src_reg.var_off.value; - - dst_reg->var_off = tnum_const(value); - dst_reg->min_value = dst_reg->max_value = min_t(u64, - value, BPF_REGISTER_MAX_RANGE); + __mark_reg_known(dst_reg, dst_reg->var_off.value & + src_reg.var_off.value); break; } - /* Lose min_value when AND'ing negative numbers, ain't nobody - * got time for that. Otherwise we get our minimum from the - * var_off, since that's inherently bitwise. - * Our maximum is the minimum of the operands' maxima. + /* We get our minimum from the var_off, since that's inherently + * bitwise. Our maximum is the minimum of the operands' maxima. */ dst_reg->var_off = tnum_and(dst_reg->var_off, src_reg.var_off); - if (min_val < 0 && dst_reg->min_value < 0) - dst_reg->min_value = BPF_REGISTER_MIN_RANGE; - else - dst_reg->min_value = dst_reg->var_off.value; - dst_reg->max_value = min(dst_reg->max_value, max_val); + dst_reg->umin_value = dst_reg->var_off.value; + dst_reg->umax_value = min(dst_reg->umax_value, umax_val); + if (dst_reg->smin_value < 0 || smin_val < 0) { + /* Lose signed bounds when ANDing negative numbers, + * ain't nobody got time for that. + */ + dst_reg->smin_value = S64_MIN; + dst_reg->smax_value = S64_MAX; + } else { + /* ANDing two positives gives a positive, so safe to + * cast result into s64. + */ + dst_reg->smin_value = dst_reg->umin_value; + dst_reg->smax_value = dst_reg->umax_value; + } + /* We may learn something more from the var_off */ + __update_reg_bounds(dst_reg); break; case BPF_OR: if (src_known && dst_known) { - u64 value = dst_reg->var_off.value | src_reg.var_off.value; - - dst_reg->var_off = tnum_const(value); - dst_reg->min_value = dst_reg->max_value = min_t(u64, - value, BPF_REGISTER_MAX_RANGE); + __mark_reg_known(dst_reg, dst_reg->var_off.value | + src_reg.var_off.value); break; } - /* Lose ranges when OR'ing negative numbers, ain't nobody got - * time for that. Otherwise we get our maximum from the var_off, - * and our minimum is the maximum of the operands' minima. + /* We get our maximum from the var_off, and our minimum is the + * maximum of the operands' minima */ dst_reg->var_off = tnum_or(dst_reg->var_off, src_reg.var_off); - if (min_val < 0 || dst_reg->min_value < 0) { - dst_reg->min_value = BPF_REGISTER_MIN_RANGE; - dst_reg->max_value = BPF_REGISTER_MAX_RANGE; + dst_reg->umin_value = max(dst_reg->umin_value, umin_val); + dst_reg->umax_value = dst_reg->var_off.value | + dst_reg->var_off.mask; + if (dst_reg->smin_value < 0 || smin_val < 0) { + /* Lose signed bounds when ORing negative numbers, + * ain't nobody got time for that. + */ + dst_reg->smin_value = S64_MIN; + dst_reg->smax_value = S64_MAX; } else { - dst_reg->min_value = max(dst_reg->min_value, min_val); - dst_reg->max_value = dst_reg->var_off.value | dst_reg->var_off.mask; + /* ORing two positives gives a positive, so safe to + * cast result into s64. + */ + dst_reg->smin_value = dst_reg->umin_value; + dst_reg->smax_value = dst_reg->umax_value; } + /* We may learn something more from the var_off */ + __update_reg_bounds(dst_reg); break; case BPF_LSH: - if (min_val < 0) { - /* LSH by a negative number is undefined */ + if (umax_val > 63) { + /* Shifts greater than 63 are undefined. This includes + * shifts by a negative number. + */ mark_reg_unknown(regs, insn->dst_reg); break; } - /* Gotta have special overflow logic here, if we're shifting - * more than MAX_RANGE then just assume we have an invalid - * range. + /* We lose all sign bit information (except what we can pick + * up from var_off) */ - if (min_val > ilog2(BPF_REGISTER_MAX_RANGE)) { - dst_reg->min_value = BPF_REGISTER_MIN_RANGE; - dst_reg->var_off = tnum_unknown; + dst_reg->smin_value = S64_MIN; + dst_reg->smax_value = S64_MAX; + /* If we might shift our top bit out, then we know nothing */ + if (dst_reg->umax_value > 1ULL << (63 - umax_val)) { + dst_reg->umin_value = 0; + dst_reg->umax_value = U64_MAX; } else { - if (dst_reg->min_value != BPF_REGISTER_MIN_RANGE) - dst_reg->min_value <<= min_val; - if (src_known) - dst_reg->var_off = tnum_lshift(dst_reg->var_off, min_val); - else - dst_reg->var_off = tnum_lshift(tnum_unknown, min_val); + dst_reg->umin_value <<= umin_val; + dst_reg->umax_value <<= umax_val; } - if (max_val > ilog2(BPF_REGISTER_MAX_RANGE)) - dst_reg->max_value = BPF_REGISTER_MAX_RANGE; - else if (dst_reg->max_value != BPF_REGISTER_MAX_RANGE) - dst_reg->max_value <<= max_val; + if (src_known) + dst_reg->var_off = tnum_lshift(dst_reg->var_off, umin_val); + else + dst_reg->var_off = tnum_lshift(tnum_unknown, umin_val); + /* We may learn something more from the var_off */ + __update_reg_bounds(dst_reg); break; case BPF_RSH: - if (min_val < 0) { - /* RSH by a negative number is undefined */ + if (umax_val > 63) { + /* Shifts greater than 63 are undefined. This includes + * shifts by a negative number. + */ mark_reg_unknown(regs, insn->dst_reg); break; } /* BPF_RSH is an unsigned shift, so make the appropriate casts */ - if (dst_reg->min_value < 0) { - if (min_val) + if (dst_reg->smin_value < 0) { + if (umin_val) { /* Sign bit will be cleared */ - dst_reg->min_value = 0; + dst_reg->smin_value = 0; + } else { + /* Lost sign bit information */ + dst_reg->smin_value = S64_MIN; + dst_reg->smax_value = S64_MAX; + } } else { - dst_reg->min_value = - (u64)(dst_reg->min_value) >> min_val; + dst_reg->smin_value = + (u64)(dst_reg->smin_value) >> umax_val; } if (src_known) - dst_reg->var_off = tnum_rshift(dst_reg->var_off, min_val); + dst_reg->var_off = tnum_rshift(dst_reg->var_off, + umin_val); else - dst_reg->var_off = tnum_rshift(tnum_unknown, min_val); - if (dst_reg->max_value == BPF_REGISTER_MAX_RANGE) - dst_reg->max_value = ~0; - dst_reg->max_value >>= max_val; + dst_reg->var_off = tnum_rshift(tnum_unknown, umin_val); + dst_reg->umin_value >>= umax_val; + dst_reg->umax_value >>= umin_val; + /* We may learn something more from the var_off */ + __update_reg_bounds(dst_reg); break; default: mark_reg_unknown(regs, insn->dst_reg); break; } - check_reg_overflow(dst_reg); + __reg_deduce_bounds(dst_reg); + __reg_bound_offset(dst_reg); return 0; } @@ -1981,14 +2134,11 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, int rc; dst_reg = ®s[insn->dst_reg]; - check_reg_overflow(dst_reg); src_reg = NULL; if (dst_reg->type != SCALAR_VALUE) ptr_reg = dst_reg; if (BPF_SRC(insn->code) == BPF_X) { src_reg = ®s[insn->src_reg]; - check_reg_overflow(src_reg); - if (src_reg->type != SCALAR_VALUE) { if (dst_reg->type != SCALAR_VALUE) { /* Combining two pointers by any ALU op yields @@ -2035,11 +2185,8 @@ static int adjust_reg_min_max_vals(struct bpf_verifier_env *env, * need to be able to read from this state. */ off_reg.type = SCALAR_VALUE; - off_reg.var_off = tnum_const(insn->imm); - off_reg.min_value = insn->imm; - off_reg.max_value = insn->imm; + __mark_reg_known(&off_reg, insn->imm); src_reg = &off_reg; - check_reg_overflow(src_reg); if (ptr_reg) { /* pointer += K */ rc = adjust_ptr_min_max_vals(env, insn, ptr_reg, src_reg); @@ -2144,22 +2291,17 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn) return -EACCES; } mark_reg_unknown(regs, insn->dst_reg); - /* high 32 bits are known zero. But this is - * still out of range for max_value, so leave - * that. - */ + /* high 32 bits are known zero. */ regs[insn->dst_reg].var_off = tnum_cast( regs[insn->dst_reg].var_off, 4); + __update_reg_bounds(®s[insn->dst_reg]); } } else { /* case: R = imm * remember the value we stored into this reg */ regs[insn->dst_reg].type = SCALAR_VALUE; - regs[insn->dst_reg].var_off = tnum_const(insn->imm); - regs[insn->dst_reg].max_value = insn->imm; - regs[insn->dst_reg].min_value = insn->imm; - regs[insn->dst_reg].id = 0; + __mark_reg_known(regs + insn->dst_reg, insn->imm); } } else if (opcode > BPF_END) { @@ -2226,8 +2368,8 @@ static void find_good_pkt_pointers(struct bpf_verifier_state *state, /* This doesn't give us any range */ return; - if (dst_reg->max_value > MAX_PACKET_OFF || - dst_reg->max_value + dst_reg->off > MAX_PACKET_OFF) + if (dst_reg->umax_value > MAX_PACKET_OFF || + dst_reg->umax_value + dst_reg->off > MAX_PACKET_OFF) /* Risk of overflow. For instance, ptr + (1<<63) may be less * than pkt_end, but that's because it's also less than pkt. */ @@ -2291,8 +2433,6 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg, struct bpf_reg_state *false_reg, u64 val, u8 opcode) { - bool value_from_signed = true; - /* If the dst_reg is a pointer, we can't learn anything about its * variable offset from the compare (unless src_reg were a pointer into * the same object, but we don't bother with that. @@ -2307,62 +2447,45 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg, /* If this is false then we know nothing Jon Snow, but if it is * true then we know for sure. */ - true_reg->max_value = true_reg->min_value = val; - true_reg->var_off = tnum_const(val); + __mark_reg_known(true_reg, val); break; case BPF_JNE: /* If this is true we know nothing Jon Snow, but if it is false * we know the value for sure; */ - false_reg->max_value = false_reg->min_value = val; - false_reg->var_off = tnum_const(val); + __mark_reg_known(false_reg, val); break; case BPF_JGT: - value_from_signed = false; - /* fallthrough */ + false_reg->umax_value = min(false_reg->umax_value, val); + true_reg->umin_value = max(true_reg->umin_value, val + 1); + break; case BPF_JSGT: - if (true_reg->value_from_signed != value_from_signed) - reset_reg_range_values(true_reg, 0); - if (false_reg->value_from_signed != value_from_signed) - reset_reg_range_values(false_reg, 0); - if (opcode == BPF_JGT) { - /* Unsigned comparison, the minimum value is 0. */ - false_reg->min_value = 0; - } - /* If this is false then we know the maximum val is val, - * otherwise we know the min val is val+1. - */ - false_reg->max_value = val; - false_reg->value_from_signed = value_from_signed; - true_reg->min_value = val + 1; - true_reg->value_from_signed = value_from_signed; + false_reg->smax_value = min_t(s64, false_reg->smax_value, val); + true_reg->smin_value = max_t(s64, true_reg->smin_value, val + 1); break; case BPF_JGE: - value_from_signed = false; - /* fallthrough */ + false_reg->umax_value = min(false_reg->umax_value, val - 1); + true_reg->umin_value = max(true_reg->umin_value, val); + break; case BPF_JSGE: - if (true_reg->value_from_signed != value_from_signed) - reset_reg_range_values(true_reg, 0); - if (false_reg->value_from_signed != value_from_signed) - reset_reg_range_values(false_reg, 0); - if (opcode == BPF_JGE) { - /* Unsigned comparison, the minimum value is 0. */ - false_reg->min_value = 0; - } - /* If this is false then we know the maximum value is val - 1, - * otherwise we know the mimimum value is val. - */ - false_reg->max_value = val - 1; - false_reg->value_from_signed = value_from_signed; - true_reg->min_value = val; - true_reg->value_from_signed = value_from_signed; + false_reg->smax_value = min_t(s64, false_reg->smax_value, val - 1); + true_reg->smin_value = max_t(s64, true_reg->smin_value, val); break; default: break; } - check_reg_overflow(false_reg); - check_reg_overflow(true_reg); + __reg_deduce_bounds(false_reg); + __reg_deduce_bounds(true_reg); + /* We might have learned some bits from the bounds. */ + __reg_bound_offset(false_reg); + __reg_bound_offset(true_reg); + /* Intersecting with the old var_off might have improved our bounds + * slightly. e.g. if umax was 0x7f...f and var_off was (0; 0xf...fc), + * then new var_off is (0; 0x7f...fc) which improves our umax. + */ + __update_reg_bounds(false_reg); + __update_reg_bounds(true_reg); } /* Same as above, but for the case that dst_reg holds a constant and src_reg is @@ -2372,8 +2495,6 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg, struct bpf_reg_state *false_reg, u64 val, u8 opcode) { - bool value_from_signed = true; - if (__is_pointer_value(false, false_reg)) return; @@ -2382,77 +2503,76 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg, /* If this is false then we know nothing Jon Snow, but if it is * true then we know for sure. */ - true_reg->max_value = true_reg->min_value = val; - true_reg->var_off = tnum_const(val); + __mark_reg_known(true_reg, val); break; case BPF_JNE: /* If this is true we know nothing Jon Snow, but if it is false * we know the value for sure; */ - false_reg->max_value = false_reg->min_value = val; - false_reg->var_off = tnum_const(val); + __mark_reg_known(false_reg, val); break; case BPF_JGT: - value_from_signed = false; - /* fallthrough */ + true_reg->umax_value = min(true_reg->umax_value, val - 1); + false_reg->umin_value = max(false_reg->umin_value, val); + break; case BPF_JSGT: - if (true_reg->value_from_signed != value_from_signed) - reset_reg_range_values(true_reg, 0); - if (false_reg->value_from_signed != value_from_signed) - reset_reg_range_values(false_reg, 0); - if (opcode == BPF_JGT) { - /* Unsigned comparison, the minimum value is 0. */ - true_reg->min_value = 0; - } - /* - * If this is false, then the val is <= the register, if it is - * true the register <= to the val. - */ - false_reg->min_value = val; - false_reg->value_from_signed = value_from_signed; - true_reg->max_value = val - 1; - true_reg->value_from_signed = value_from_signed; + true_reg->smax_value = min_t(s64, true_reg->smax_value, val - 1); + false_reg->smin_value = max_t(s64, false_reg->smin_value, val); break; case BPF_JGE: - value_from_signed = false; - /* fallthrough */ + true_reg->umax_value = min(true_reg->umax_value, val); + false_reg->umin_value = max(false_reg->umin_value, val + 1); + break; case BPF_JSGE: - if (true_reg->value_from_signed != value_from_signed) - reset_reg_range_values(true_reg, 0); - if (false_reg->value_from_signed != value_from_signed) - reset_reg_range_values(false_reg, 0); - if (opcode == BPF_JGE) { - /* Unsigned comparison, the minimum value is 0. */ - true_reg->min_value = 0; - } - /* If this is false then constant < register, if it is true then - * the register < constant. - */ - false_reg->min_value = val + 1; - false_reg->value_from_signed = value_from_signed; - true_reg->max_value = val; - true_reg->value_from_signed = value_from_signed; + true_reg->smax_value = min_t(s64, true_reg->smax_value, val); + false_reg->smin_value = max_t(s64, false_reg->smin_value, val + 1); break; default: break; } - check_reg_overflow(false_reg); - check_reg_overflow(true_reg); + __reg_deduce_bounds(false_reg); + __reg_deduce_bounds(true_reg); + /* We might have learned some bits from the bounds. */ + __reg_bound_offset(false_reg); + __reg_bound_offset(true_reg); + /* Intersecting with the old var_off might have improved our bounds + * slightly. e.g. if umax was 0x7f...f and var_off was (0; 0xf...fc), + * then new var_off is (0; 0x7f...fc) which improves our umax. + */ + __update_reg_bounds(false_reg); + __update_reg_bounds(true_reg); } /* Regs are known to be equal, so intersect their min/max/var_off */ static void __reg_combine_min_max(struct bpf_reg_state *src_reg, struct bpf_reg_state *dst_reg) { - src_reg->min_value = dst_reg->min_value = max(src_reg->min_value, - dst_reg->min_value); - src_reg->max_value = dst_reg->max_value = min(src_reg->max_value, - dst_reg->max_value); + src_reg->umin_value = dst_reg->umin_value = max(src_reg->umin_value, + dst_reg->umin_value); + src_reg->umax_value = dst_reg->umax_value = min(src_reg->umax_value, + dst_reg->umax_value); + src_reg->smin_value = dst_reg->smin_value = max(src_reg->smin_value, + dst_reg->smin_value); + src_reg->smax_value = dst_reg->smax_value = min(src_reg->smax_value, + dst_reg->smax_value); src_reg->var_off = dst_reg->var_off = tnum_intersect(src_reg->var_off, dst_reg->var_off); - check_reg_overflow(src_reg); - check_reg_overflow(dst_reg); + /* We might have learned new bounds from the var_off. */ + __update_reg_bounds(src_reg); + __update_reg_bounds(dst_reg); + /* We might have learned something about the sign bit. */ + __reg_deduce_bounds(src_reg); + __reg_deduce_bounds(dst_reg); + /* We might have learned some bits from the bounds. */ + __reg_bound_offset(src_reg); + __reg_bound_offset(dst_reg); + /* Intersecting with the old var_off might have improved our bounds + * slightly. e.g. if umax was 0x7f...f and var_off was (0; 0xf...fc), + * then new var_off is (0; 0x7f...fc) which improves our umax. + */ + __update_reg_bounds(src_reg); + __update_reg_bounds(dst_reg); } static void reg_combine_min_max(struct bpf_reg_state *true_src, @@ -2467,6 +2587,7 @@ static void reg_combine_min_max(struct bpf_reg_state *true_src, break; case BPF_JNE: __reg_combine_min_max(false_src, false_dst); + break; } } @@ -2480,11 +2601,11 @@ static void mark_map_reg(struct bpf_reg_state *regs, u32 regno, u32 id, * have been known-zero, because we don't allow pointer * arithmetic on pointers that might be NULL. */ - if (WARN_ON_ONCE(reg->min_value || reg->max_value || - reg->var_off.value || reg->var_off.mask || + if (WARN_ON_ONCE(reg->smin_value || reg->smax_value || + !tnum_equals_const(reg->var_off, 0) || reg->off)) { - reg->min_value = reg->max_value = reg->off = 0; - reg->var_off = tnum_const(0); + __mark_reg_known_zero(reg); + reg->off = 0; } if (is_null) { reg->type = SCALAR_VALUE; @@ -2676,11 +2797,7 @@ static int check_ld_imm(struct bpf_verifier_env *env, struct bpf_insn *insn) u64 imm = ((u64)(insn + 1)->imm << 32) | (u32)insn->imm; regs[insn->dst_reg].type = SCALAR_VALUE; - regs[insn->dst_reg].min_value = imm; - regs[insn->dst_reg].max_value = imm; - check_reg_overflow(®s[insn->dst_reg]); - regs[insn->dst_reg].var_off = tnum_const(imm); - regs[insn->dst_reg].id = 0; + __mark_reg_known(®s[insn->dst_reg], imm); return 0; } @@ -2968,8 +3085,10 @@ err_free: static bool range_within(struct bpf_reg_state *old, struct bpf_reg_state *cur) { - return old->min_value <= cur->min_value && - old->max_value >= cur->max_value; + return old->umin_value <= cur->umin_value && + old->umax_value >= cur->umax_value && + old->smin_value <= cur->smin_value && + old->smax_value >= cur->smax_value; } /* Maximum number of register states that can exist at once */ @@ -3032,8 +3151,10 @@ static bool regsafe(struct bpf_reg_state *rold, * equal, because we can't know anything about the * scalar value of the pointer in the new value. */ - return rold->min_value == BPF_REGISTER_MIN_RANGE && - rold->max_value == BPF_REGISTER_MAX_RANGE && + return rold->umin_value == 0 && + rold->umax_value == U64_MAX && + rold->smin_value == S64_MIN && + rold->smax_value == S64_MAX && tnum_is_unknown(rold->var_off); } case PTR_TO_MAP_VALUE: -- cgit v1.2.3