On 2/4/20 11:55 AM, John Fastabend wrote:
Alexei Starovoitov wrote:
On Fri, Jan 31, 2020 at 9:16 AM John Fastabend <john.fastabend@xxxxxxxxx> wrote:
Also don't mind to build pseudo instruction here for signed extension
but its not clear to me why we are getting different instruction
selections? Its not clear to me why sext is being chosen in your case?
Sign extension has to be there if jmp64 is used.
So the difference is due to -mcpu=v2 vs -mcpu=v3
v2 does alu32, but not jmp32
v3 does both.
By default selftests are using -mcpu=probe which
detects v2/v3 depending on running kernel.
llc -mattr=dwarfris -march=bpf -mcpu=v3 -mattr=+alu32
; usize = bpf_get_stack(ctx, raw_data, max_len, BPF_F_USER_STACK);
48: bf 61 00 00 00 00 00 00 r1 = r6
49: bf 72 00 00 00 00 00 00 r2 = r7
50: b4 03 00 00 20 03 00 00 w3 = 800
51: b7 04 00 00 00 01 00 00 r4 = 256
52: 85 00 00 00 43 00 00 00 call 67
53: bc 08 00 00 00 00 00 00 w8 = w0
; if (usize < 0)
54: c6 08 16 00 00 00 00 00 if w8 s< 0 goto +22 <LBB0_6>
; ksize = bpf_get_stack(ctx, raw_data + usize, max_len - usize, 0);
55: 1c 89 00 00 00 00 00 00 w9 -= w8
56: bc 81 00 00 00 00 00 00 w1 = w8
57: 67 01 00 00 20 00 00 00 r1 <<= 32
58: 77 01 00 00 20 00 00 00 r1 >>= 32
59: bf 72 00 00 00 00 00 00 r2 = r7
60: 0f 12 00 00 00 00 00 00 r2 += r1
61: bf 61 00 00 00 00 00 00 r1 = r6
62: bc 93 00 00 00 00 00 00 w3 = w9
63: b7 04 00 00 00 00 00 00 r4 = 0
64: 85 00 00 00 43 00 00 00 call 67
; if (ksize < 0)
65: c6 00 0b 00 00 00 00 00 if w0 s< 0 goto +11 <LBB0_6>
llc -mattr=dwarfris -march=bpf -mcpu=v2 -mattr=+alu32
; usize = bpf_get_stack(ctx, raw_data, max_len, BPF_F_USER_STACK);
48: bf 61 00 00 00 00 00 00 r1 = r6
49: bf 72 00 00 00 00 00 00 r2 = r7
50: b4 03 00 00 20 03 00 00 w3 = 800
51: b7 04 00 00 00 01 00 00 r4 = 256
52: 85 00 00 00 43 00 00 00 call 67
53: bc 08 00 00 00 00 00 00 w8 = w0
; if (usize < 0)
54: bc 81 00 00 00 00 00 00 w1 = w8
55: 67 01 00 00 20 00 00 00 r1 <<= 32
56: c7 01 00 00 20 00 00 00 r1 s>>= 32
57: c5 01 19 00 00 00 00 00 if r1 s< 0 goto +25 <LBB0_6>
; ksize = bpf_get_stack(ctx, raw_data + usize, max_len - usize, 0);
58: 1c 89 00 00 00 00 00 00 w9 -= w8
59: bc 81 00 00 00 00 00 00 w1 = w8
60: 67 01 00 00 20 00 00 00 r1 <<= 32
61: 77 01 00 00 20 00 00 00 r1 >>= 32
62: bf 72 00 00 00 00 00 00 r2 = r7
63: 0f 12 00 00 00 00 00 00 r2 += r1
64: bf 61 00 00 00 00 00 00 r1 = r6
65: bc 93 00 00 00 00 00 00 w3 = w9
66: b7 04 00 00 00 00 00 00 r4 = 0
67: 85 00 00 00 43 00 00 00 call 67
; if (ksize < 0)
68: bc 01 00 00 00 00 00 00 w1 = w0
69: 67 01 00 00 20 00 00 00 r1 <<= 32
70: c7 01 00 00 20 00 00 00 r1 s>>= 32
71: c5 01 0b 00 00 00 00 00 if r1 s< 0 goto +11 <LBB0_6>
zext is there both cases and it will be optimized with your llvm patch.
So please send it. Don't delay :)
LLVM patch here, https://urldefense.proofpoint.com/v2/url?u=https-3A__reviews.llvm.org_D73985&d=DwICaQ&c=5VD0RTtNlTh3ycd41b3MUw&r=DA8e1B5r073vIqRrFz7MRA&m=VnK0SKxGnw_yzWjaO-cZFrmlZB9p86L4me-mWE_vDto&s=jwDJuAEdJ23HVcvIILvkfxvTNSe_cgHQFn_MpXssfXc&e=
With updated LLVM I can pass selftests with above fix and additional patch
below to get tighter bounds on 32bit registers. So going forward I think
we need to review and assuming it looks good commit above llvm patch and
then go forward with this series.
Thanks. The llvm patch looks sane, but after applying the patch, I hit
several selftest failures. For example, strobemeta_nounroll1.o.
The following is a brief analysis of the verifier state:
184:
R0=inv(id=0,smax_value=9223372032559808513,umax_value=18446744069414584321,var_off=(0x0;
0xffffffff00000001))
R7=inv0
184: (bc) w7 = w0
185:
R0=inv(id=0,smax_value=9223372032559808513,umax_value=18446744069414584321,var_off=(0x0;
0xffffffff00000001))
R7_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0x1))
185: (67) r7 <<= 32
186:
R0=inv(id=0,smax_value=9223372032559808513,umax_value=18446744069414584321,var_off=(0x0;
0xffffffff00000001))
R7_w=inv(id=0,umax_value=4294967296,var_off=(0x0; 0x100000000))
186: (77) r7 >>= 32
187:
R0=inv(id=0,smax_value=9223372032559808513,umax_value=18446744069414584321,var_off=(0x0;
0xffffffff00000001))
R7_w=inv(id=0,umax_value=1,var_off=(0x0; 0x1))
You can see after left and right shift, we got a better R7 umax_value=1.
Without the left and right shift, eventually verifier complains.
Can we make uname_value=1 at insn 'w7 = w0'?
Currently, we cannot do this due to the logic in coerce_reg_to_size().
It looks correct to me to ignore the top mask as we know the upper 32bit
will be discarded.
I have implemented in my previous patch to deal with signed compares.
The following is the patch to fix this particular issue:
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 1cc945daa9c8..5aa2adad18c9 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2788,7 +2788,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_mask)
{
u64 mask;
@@ -2797,7 +2798,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_mask ||
+ (reg->umin_value & ~mask) == (reg->umax_value & ~mask)) {
reg->umin_value &= mask;
reg->umax_value &= mask;
} else {
@@ -3066,7 +3068,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,8 +4861,8 @@ 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);
+ coerce_reg_to_size(dst_reg, 4, false);
+ coerce_reg_to_size(&src_reg, 4, false);
}
smin_val = src_reg.smin_value;
@@ -5114,7 +5116,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);
@@ -5290,7 +5292,7 @@ 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);
+ coerce_reg_to_size(dst_reg, 4, true);
}
} else {
/* case: R = imm
@@ -5482,7 +5484,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
@@ -6174,8 +6176,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) {
With the above patch, there is still one more issue in test_seg6_loop.o,
which is related to llvm code generation, w.r.t. our strange 32bit
packet begin and packet end.
The following patch is generated:
2: (61) r1 = *(u32 *)(r6 +76)
3: R1_w=pkt(id=0,off=0,r=0,imm=0) R2_w=pkt_end(id=0,off=0,imm=0)
R6_w=ctx(id=0,off=0,imm=0) R10=fp0
; cursor = (void *)(long)skb->data;
3: (bc) w8 = w1
4: R1_w=pkt(id=0,off=0,r=0,imm=0) R2_w=pkt_end(id=0,off=0,imm=0)
R6_w=ctx(id=0,off=0,imm=0)
R8_w=inv(id=0,umax_value=4294967295,var_off=(0x0; 0xffffffff)) R10=fp0
; if ((void *)ipver + sizeof(*ipver) > data_end)
4: (bf) r3 = r8
In the above r1 is packet pointer and after the assignment, it becomes a
scalar and will lead later verification failure.
Without the patch, we generates:
1: R1=ctx(id=0,off=0,imm=0) R6_w=ctx(id=0,off=0,imm=0) R10=fp0
; data_end = (void *)(long)skb->data_end;
1: (61) r1 = *(u32 *)(r6 +80)
2: R1_w=pkt_end(id=0,off=0,imm=0) R6_w=ctx(id=0,off=0,imm=0) R10=fp0
; cursor = (void *)(long)skb->data;
2: (61) r8 = *(u32 *)(r6 +76)
3: R1_w=pkt_end(id=0,off=0,imm=0) R6_w=ctx(id=0,off=0,imm=0)
R8_w=pkt(id=0,off=0,r=0,imm=0) R10=fp0
; if ((void *)ipver + sizeof(*ipver) > data_end)
3: (bf) r2 = r8
4: R1_w=pkt_end(id=0,off=0,imm=0) R2_w=pkt(id=0,off=0,r=0,imm=0)
R6_w=ctx(id=0,off=0,imm=0) R8_w=pkt(id=0,off=0,r=0,imm=0) R10=fp0
4: (07) r2 += 1
5: R1_w=pkt_end(id=0,off=0,imm=0) R2_w=pkt(id=0,off=1,r=0,imm=0)
R6_w=ctx(id=0,off=0,imm=0) R8_w=pkt(id=0,off=0,r=0,imm=0) R10=fp0
r2 keeps as a packet pointer, so we don't have issues later.
Not sure how we could fix this in llvm as llvm does not really have idea
the above w1 in w8 = w1 is a packet pointer.
---
bpf: coerce reg use tighter max bound if possible
When we do a coerce_reg_to_size we lose possibly valid upper bounds in
the case where, (a) smax is non-negative and (b) smax is less than max
value in new reg size. If both (a) and (b) are satisfied we can keep
the smax bound. (a) is required to ensure we do not remove upper sign
bit. And (b) is required to ensure previously set bits are contained
inside the new reg bits.
Signed-off-by: John Fastabend <john.fastabend@xxxxxxxxx>
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 1cc945d..e5349d6 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -2805,7 +2805,8 @@ static void coerce_reg_to_size(struct bpf_reg_state *reg, int size)
reg->umax_value = mask;
}
reg->smin_value = reg->umin_value;
- reg->smax_value = reg->umax_value;
+ if (reg->smax_value < 0 || reg->smax_value > reg->umax_value)
+ reg->smax_value = reg->umax_value;
}
static bool bpf_map_is_rdonly(const struct bpf_map *map)
