On 4/22/18 5:16 PM, Alexei Starovoitov wrote:
On Fri, Apr 20, 2018 at 03:18:37PM -0700, Yonghong Song wrote:When helpers like bpf_get_stack returns an int value and later on used for arithmetic computation, the LSH and ARSH operations are often required to get proper sign extension into 64-bit. For example, without this patch: 54: R0=inv(id=0,umax_value=800) 54: (bf) r8 = r0 55: R0=inv(id=0,umax_value=800) R8_w=inv(id=0,umax_value=800) 55: (67) r8 <<= 32 56: R8_w=inv(id=0,umax_value=3435973836800,var_off=(0x0; 0x3ff00000000)) 56: (c7) r8 s>>= 32 57: R8=inv(id=0) With this patch: 54: R0=inv(id=0,umax_value=800) 54: (bf) r8 = r0 55: R0=inv(id=0,umax_value=800) R8_w=inv(id=0,umax_value=800) 55: (67) r8 <<= 32 56: R8_w=inv(id=0,umax_value=3435973836800,var_off=(0x0; 0x3ff00000000)) 56: (c7) r8 s>>= 32 57: R8=inv(id=0, umax_value=800,var_off=(0x0; 0x3ff)) With better range of "R8", later on when "R8" is added to other register, e.g., a map pointer or scalar-value register, the better register range can be derived and verifier failure may be avoided. In our later example, ...... usize = bpf_get_stack(ctx, raw_data, max_len, BPF_F_USER_STACK); if (usize < 0) return 0; ksize = bpf_get_stack(ctx, raw_data + usize, max_len - usize, 0); ...... Without improving ARSH value range tracking, the register representing "max_len - usize" will have smin_value equal to S64_MIN and will be rejected by verifier. Signed-off-by: Yonghong Song <y...@fb.com> --- kernel/bpf/verifier.c | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+) diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c index 3c8bb92..01c215d 100644 --- a/kernel/bpf/verifier.c +++ b/kernel/bpf/verifier.c @@ -2975,6 +2975,32 @@ static int adjust_scalar_min_max_vals(struct bpf_verifier_env *env, /* We may learn something more from the var_off */ __update_reg_bounds(dst_reg); break; + case BPF_ARSH: + if (umax_val >= insn_bitness) { + /* Shifts greater than 31 or 63 are undefined. + * This includes shifts by a negative number. + */ + mark_reg_unknown(env, regs, insn->dst_reg); + break; + } + if (dst_reg->smin_value < 0) + dst_reg->smin_value >>= umin_val; + else + dst_reg->smin_value >>= umax_val; + if (dst_reg->smax_value < 0) + dst_reg->smax_value >>= umax_val; + else + dst_reg->smax_value >>= umin_val; + if (src_known) + dst_reg->var_off = tnum_rshift(dst_reg->var_off, + umin_val); + else + 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);I'm struggling to understand how these bounds are computed. Could you add examples in the comments?
Okay, let me try to add some comments for better understanding.
In particular if dst_reg is unknown (tnum.mask == -1) the above tnum_rshift() will clear upper bits and will make it 64-bit positive, but that doesn't seem correct. What am I missing?
Considering this is arith shift, we probably should just have dst_reg->var_off = tnum_unknown to be conservative. I could miss something here as well. Let me try to write more detailed explanation, hopefully to cover all corner cases.
