Commit b7a0d65d80a0 ("bpf, testing: Workaround a verifier failure
for test_progs") worked around a verifier failure where the
register is copied to another later refined register, but the
original register is used after refinement. Another similar example is
https://lore.kernel.org/netdev/871019a0-71f8-c26d-0ae8-c7fd8c8867fc@xxxxxx/
LLVM commit https://reviews.llvm.org/D72787 added a phase
to adjust optimization such that the original register is
directly refined and used later. Another issue exposed by
the llvm is verifier cannot handle the following code:
call bpf_strtoul
if w0 s< 1 then ...
if w0 s> 7 then ...
... use w0 ...
Unfortunately, the verifier is not able to handle the above
code well and will reject it.
call bpf_strtoul
R0_w=inv(id=0) R8=invP0
if w0 s< 0x1 goto pc-22
R0_w=inv(id=0) R8=invP0
if w0 s> 0x7 goto pc-23
R0=inv(id=0) R8=invP0
w0 += w8
R0_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R8=invP0
After "w0 += w8", we got a very conservative R0 value, which
later on caused verifier rejection.
This patch added two register states, s32_min_value and s32_max_value,
to bpf_reg_state. These two states capture the signed 32bit
min/max values refined due to 32bit signed sle/slt/sge/sgt comparisons.
1. whenever refined s32_min_value, s32_max_value is captured, reg->var_off
will be refined if possible.
2. For any ALU32 operation where the dst_reg will have upper 32bit cleared,
if s32_min_value >= 0 and s32_max_value has been narrowed due to previous
signed compare operation, the dst_reg as an input can ignore upper 32bit values,
this may produce better output dst_reg value range.
3. s32_min_value and s32_max_value is reset if the corresponding register
is redefined.
The following shows the new register states for the above example.
call bpf_strtoul
R0_w=inv(id=0) R8=invP0
if w0 s< 0x1 goto pc-22
R0_w=inv(id=0,smax_value=9223372034707292159,umax_value=18446744071562067967,
s32_min_value=1,var_off=(0x0; 0xffffffff7fffffff))
R8=invP0
if w0 s> 0x7 goto pc-23
R0=inv(id=0,smax_value=9223372032559808519,umax_value=18446744069414584327,
s32_min_value=1,s32_max_value=7,var_off=(0x0; 0xffffffff00000007))
R8=invP0
w0 += w8
R0_w=inv(id=0,umax_value=7,var_off=(0x0; 0x7)) R8=invP0
With the above LLVM patch and this commit, the original
workaround in Commit b7a0d65d80a0 is not needed any more.
Signed-off-by: Yonghong Song <yhs@xxxxxx>
---
include/linux/bpf_verifier.h | 2 +
kernel/bpf/verifier.c | 73 +++++++++++++++++++++++++++++++-----
2 files changed, 65 insertions(+), 10 deletions(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 5406e6e96585..d5694308466d 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -123,6 +123,8 @@ struct bpf_reg_state {
s64 smax_value; /* maximum possible (s64)value */
u64 umin_value; /* minimum possible (u64)value */
u64 umax_value; /* maximum possible (u64)value */
+ s32 s32_min_value; /* minimum possible (s32)value */
+ s32 s32_max_value; /* maximum possible (s32)value */
/* parentage chain for liveness checking */
struct bpf_reg_state *parent;
/* Inside the callee two registers can be both PTR_TO_STACK like
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 1cc945daa9c8..c5d6835c38db 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -543,6 +543,14 @@ static void print_verifier_state(struct bpf_verifier_env *env,
if (reg->umax_value != U64_MAX)
verbose(env, ",umax_value=%llu",
(unsigned long long)reg->umax_value);
+ if (reg->s32_min_value != reg->umin_value &&
+ reg->s32_min_value != S32_MIN)
+ verbose(env, ",s32_min_value=%d",
+ (int)reg->s32_min_value);
+ if (reg->s32_max_value != reg->umax_value &&
+ reg->s32_max_value != S32_MAX)
+ verbose(env, ",s32_max_value=%d",
+ (int)reg->s32_max_value);
if (!tnum_is_unknown(reg->var_off)) {
char tn_buf[48];
@@ -923,6 +931,10 @@ static void __mark_reg_known(struct bpf_reg_state *reg, u64 imm)
reg->smax_value = (s64)imm;
reg->umin_value = imm;
reg->umax_value = imm;
+
+ /* no need to be precise, just reset s32_{min,max}_value */
+ reg->s32_min_value = S32_MIN;
+ reg->s32_max_value = S32_MAX;
}
/* Mark the 'variable offset' part of a register as zero. This should be
@@ -1043,6 +1055,12 @@ static void __reg_bound_offset32(struct bpf_reg_state *reg)
struct tnum hi32 = tnum_lshift(tnum_rshift(reg->var_off, 32), 32);
reg->var_off = tnum_or(hi32, tnum_intersect(lo32, range));
+
+ /* further refine based on s32 min/max values */
+ range = tnum_range(reg->s32_min_value, reg->s32_max_value);
+ lo32 = tnum_cast(reg->var_off, 4);
+ hi32 = tnum_lshift(tnum_rshift(reg->var_off, 32), 32);
+ reg->var_off = tnum_or(hi32, tnum_intersect(lo32, range));
}
/* Reset the min/max bounds of a register */
@@ -1052,6 +1070,8 @@ static void __mark_reg_unbounded(struct bpf_reg_state *reg)
reg->smax_value = S64_MAX;
reg->umin_value = 0;
reg->umax_value = U64_MAX;
+ reg->s32_min_value = S32_MIN;
+ reg->s32_max_value = S32_MAX;
}
/* Mark a register as having a completely unknown (scalar) value. */
@@ -2788,7 +2808,8 @@ static int check_tp_buffer_access(struct bpf_verifier_env *env,
/* truncate register to smaller size (in bytes)
* must be called with size < BPF_REG_SIZE
*/
-static void coerce_reg_to_size(struct bpf_reg_state *reg, int size)
+static void coerce_reg_to_size(struct bpf_reg_state *reg, int size,
+ bool ignore_upper_value)
{
u64 mask;
@@ -2797,7 +2818,8 @@ static void coerce_reg_to_size(struct bpf_reg_state *reg, int size)
/* fix arithmetic bounds */
mask = ((u64)1 << (size * 8)) - 1;
- if ((reg->umin_value & ~mask) == (reg->umax_value & ~mask)) {
+ if (ignore_upper_value ||
+ (reg->umin_value & ~mask) == (reg->umax_value & ~mask)) {
reg->umin_value &= mask;
reg->umax_value &= mask;
} else {
@@ -3066,7 +3088,7 @@ static int check_mem_access(struct bpf_verifier_env *env, int insn_idx, u32 regn
if (!err && size < BPF_REG_SIZE && value_regno >= 0 && t == BPF_READ &&
regs[value_regno].type == SCALAR_VALUE) {
/* b/h/w load zero-extends, mark upper bits as known 0 */
- coerce_reg_to_size(®s[value_regno], size);
+ coerce_reg_to_size(®s[value_regno], size, false);
}
return err;
}
@@ -4859,10 +4881,20 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
* LSB, so it isn't sufficient to only truncate the output to
* 32 bits.
*/
- coerce_reg_to_size(dst_reg, 4);
- coerce_reg_to_size(&src_reg, 4);
+ /* The upper 32bit value can be ignored in coerce_reg_to_size()
+ * for dst_reg if we had a narrower range for 32bit subregister
+ * based on previous tests.
+ */
+ bool ignore_upper_value = dst_reg->s32_min_value >= 0 &&
+ dst_reg->s32_max_value < S32_MAX;
+ coerce_reg_to_size(dst_reg, 4, ignore_upper_value);
+ coerce_reg_to_size(&src_reg, 4, false);
}
+ /* reset dst_reg s32_{min,max}_value */
+ dst_reg->s32_min_value = S32_MIN;
+ dst_reg->s32_max_value = S32_MAX;
+
smin_val = src_reg.smin_value;
smax_val = src_reg.smax_value;
umin_val = src_reg.umin_value;
@@ -5114,7 +5146,7 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env,
if (BPF_CLASS(insn->code) != BPF_ALU64) {
/* 32-bit ALU ops are (32,32)->32 */
- coerce_reg_to_size(dst_reg, 4);
+ coerce_reg_to_size(dst_reg, 4, false);
}
__reg_deduce_bounds(dst_reg);
@@ -5267,6 +5299,7 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
if (BPF_SRC(insn->code) == BPF_X) {
struct bpf_reg_state *src_reg = regs + insn->src_reg;
struct bpf_reg_state *dst_reg = regs + insn->dst_reg;
+ bool ignore_upper_value;
if (BPF_CLASS(insn->code) == BPF_ALU64) {
/* case: R1 = R2
@@ -5290,8 +5323,14 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
mark_reg_unknown(env, regs,
insn->dst_reg);
}
- coerce_reg_to_size(dst_reg, 4);
+
+ ignore_upper_value = dst_reg->s32_min_value >= 0 &&
+ dst_reg->s32_max_value < S32_MAX;
+ coerce_reg_to_size(dst_reg, 4, ignore_upper_value);
}
+
+ dst_reg->s32_min_value = S32_MIN;
+ dst_reg->s32_max_value = S32_MAX;
} else {
/* case: R = imm
* remember the value we stored into this reg
@@ -5482,7 +5521,7 @@ static int is_branch_taken(struct bpf_reg_state *reg, u64 val, u8 opcode,
* could truncate high bits and update umin/umax according to
* information of low bits.
*/
- coerce_reg_to_size(reg, 4);
+ coerce_reg_to_size(reg, 4, false);
/* smin/smax need special handling. For example, after coerce,
* if smin_value is 0x00000000ffffffffLL, the value is -1 when
* used as operand to JMP32. It is a negative number from s32's
@@ -5673,6 +5712,13 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg,
s64 false_smax = opcode == BPF_JSGT ? sval : sval - 1;
s64 true_smin = opcode == BPF_JSGT ? sval + 1 : sval;
+ if (is_jmp32 && false_smax > S32_MIN && true_smin < S32_MAX) {
+ false_reg->s32_max_value =
+ min(false_reg->s32_max_value, (s32)false_smax);
+ true_reg->s32_min_value =
+ max(true_reg->s32_min_value, (s32)true_smin);
+ }
+
/* If the full s64 was not sign-extended from s32 then don't
* deduct further info.
*/
@@ -5702,6 +5748,13 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg,
s64 false_smin = opcode == BPF_JSLT ? sval : sval + 1;
s64 true_smax = opcode == BPF_JSLT ? sval - 1 : sval;
+ if (is_jmp32 && false_smin < S32_MAX && true_smax > S32_MIN) {
+ false_reg->s32_min_value =
+ max(false_reg->s32_min_value, (s32)false_smin);
+ true_reg->s32_max_value =
+ min(true_reg->s32_max_value, (s32)true_smax);
+ }
+
if (is_jmp32 && !cmp_val_with_extended_s64(sval, false_reg))
break;
false_reg->smin_value = max(false_reg->smin_value, false_smin);
@@ -6174,8 +6227,8 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,
dst_lo = &lo_reg0;
src_lo = &lo_reg1;
- coerce_reg_to_size(dst_lo, 4);
- coerce_reg_to_size(src_lo, 4);
+ coerce_reg_to_size(dst_lo, 4, false);
+ coerce_reg_to_size(src_lo, 4, false);
if (dst_reg->type == SCALAR_VALUE &&
src_reg->type == SCALAR_VALUE) {
--
2.17.1
