From: Alexei Starovoitov A fix of the representation, for the patches that take two registers with the same expression for the same value. Today two insns that compute distinct values get the same expression: r5 >>= r4; w5 = w5 (zext32 (>> r5 r4)) w5 >>= w4 (zext32 (>> r5 r4)) The second one shifts the low 32 bits of r5, by r4 & 31. Nothing goes wrong so far: the code that analyzes loops does not look into a shift or a division. cubic_root() of bpf_cubic.c is going to depend on it: shift = (a >> (b * 3)); if (shift >= 64) return 0; x = ((__u32)(((__u32)v[shift] + 10) << b)) >> 6; GCC tests one register and uses another one as the index: r5 >>= r4 w2 = w5 if w5 > 0x3f goto .. r4 = v ll r4 += r2 The prog loads because r5 fits in u32 in the state: 'w2 = w5' assigns one scalar id to r2 and r5, so the jump bounds both. Without scalar ids it is going to load because r5 is (>> a b) and r2 is (zext32 (>> a b)), which is r5 truncated to 32 bits. An ALU32 insn is (zext32 (op a b)) with the 64-bit expressions of its operands. That is exact for + - * | & ^ and for the value that << shifts: the low 32 bits of the result depend on the low 32 bits of the operands only. It is not exact for a right shift, a division, a modulo and a shift amount. Zero or sign extend these operands, mask the shift amount: w5 >>= w4 (zext32 (>> (zext32 r5) (& r4 31))) w5 s>>= 3 (zext32 (s>> (sext32 r5) 3)) w5 /= w4 (zext32 (/ (zext32 r5) (zext32 r4))) w5 s%= w4 (zext32 (s% (sext32 r5) (sext32 r4))) Every expression is a 64-bit operation now. (>> x 32) shifts by 32. Before the patch it could also be 'w1 >>= w2' with 32 in w2, which shifts by 0. Signed-off-by: Alexei Starovoitov --- kernel/bpf/scev.c | 46 +++++++++++++++---- .../selftests/bpf/progs/verifier_scev.c | 26 +++++------ 2 files changed, 51 insertions(+), 21 deletions(-) diff --git a/kernel/bpf/scev.c b/kernel/bpf/scev.c index 4187ce955be9..1cb4bc7c0f96 100644 --- a/kernel/bpf/scev.c +++ b/kernel/bpf/scev.c @@ -686,6 +686,38 @@ static int maybe_load_fp(struct scev *scev, struct env *e, struct bpf_insn *insn return replace_reg(scev, e, insn->dst_reg, id); } +/* + * The low 32 bits of a + b depend on the low 32 bits of a and b only: 'w1 += w2' is + * (zext32 (+ a b)). That doesn't hold for a right shift and for a division. Their operands are zero + * or sign extended and a shift amount is masked, so that every expression is a 64-bit operation. + */ +static void alu32_operands(struct scev *scev, u32 op, int *a, int *b) +{ + s64 imm = 0; + bool imm_b = *b >= 0 && is_imm(scev, *b, &imm); + + switch (op) { + case BPF_RSH: + case BPF_ARSH: + *a = expr1(scev, op == BPF_RSH ? ZEXT32 : SEXT32, *a); + fallthrough; + case BPF_LSH: + *b = imm_b ? imm_expr(scev, imm & 31) : + expr2(scev, BPF_AND, *b, imm_expr(scev, 31)); + break; + case BPF_DIV: + case BPF_MOD: + *a = expr1(scev, ZEXT32, *a); + *b = imm_b ? imm_expr(scev, (u32)imm) : expr1(scev, ZEXT32, *b); + break; + case SDIV: + case SMOD: + *a = expr1(scev, SEXT32, *a); + *b = imm_b ? imm_expr(scev, (s32)imm) : expr1(scev, SEXT32, *b); + break; + } +} + static int transfer(struct bpf_verifier_env *env, struct env *e, int idx) { const bool little_endian = htons(0x3412) == 0x1234; @@ -700,7 +732,7 @@ static int transfer(struct bpf_verifier_env *env, struct env *e, int idx) u32 src = insn->src_reg; u32 op, sext, l, r; bool need_bswap; - int i, id; + int i, id, a; s64 imm; /* reg2expr[12] is a stack slot, not r12 */ @@ -764,19 +796,17 @@ static int transfer(struct bpf_verifier_env *env, struct env *e, int idx) else goto mark_dst_unknown; - /* - * 'r1 <<= 32; r1 >>= 32' is (u32)r1 for cpu v1 and v2. Only here both - * shifts are known to be 64-bit ones: the result of a 32-bit shift is - * (zext32 ...), and (>> x 32) is 'w1 >>= w2' with 32 in w2 as well, - * which shifts by 0. - */ + /* 'r1 <<= 32; r1 >>= 32' is (u32)r1 for cpu v1 and v2 */ if (class == BPF_ALU64 && op == BPF_RSH && id >= 0 && is_imm(scev, id, &imm) && imm == 32 && is_binop(scev, BPF_LSH, reg2expr[dst], &l, &r) && is_imm(scev, r, &imm) && imm == 32) return replace_reg(scev, e, dst, expr1(scev, ZEXT32, l)); - id = expr2(scev, op, reg2expr[dst], id); + a = reg2expr[dst]; + if (class == BPF_ALU) + alu32_operands(scev, op, &a, &id); + id = expr2(scev, op, a, id); if (class == BPF_ALU) id = expr1(scev, ZEXT32, id); diff --git a/tools/testing/selftests/bpf/progs/verifier_scev.c b/tools/testing/selftests/bpf/progs/verifier_scev.c index 5c9c832fbbe0..f2a53fe5f6ad 100644 --- a/tools/testing/selftests/bpf/progs/verifier_scev.c +++ b/tools/testing/selftests/bpf/progs/verifier_scev.c @@ -334,20 +334,20 @@ __msg("w1 *= 2 {{.*}}; r1 r6 -> (zext32 (* r6 2))") __msg("w1 *= w7 {{.*}}; r1 r6 -> (zext32 (* r6 r7))") __msg("r1 /= 2 {{.*}}; r1 r6 -> (/ r6 2)") __msg("r1 /= r7 {{.*}}; r1 r6 -> (/ r6 r7)") -__msg("w1 /= 2 {{.*}}; r1 r6 -> (zext32 (/ r6 2))") -__msg("w1 /= w7 {{.*}}; r1 r6 -> (zext32 (/ r6 r7))") +__msg("w1 /= 2 {{.*}}; r1 r6 -> (zext32 (/ (zext32 r6) 2))") +__msg("w1 /= w7 {{.*}}; r1 r6 -> (zext32 (/ (zext32 r6) (zext32 r7)))") __msg("r1 s/= 2 {{.*}}; r1 r6 -> (s/ r6 2)") __msg("r1 s/= r7 {{.*}}; r1 r6 -> (s/ r6 r7)") -__msg("w1 s/= 2 {{.*}}; r1 r6 -> (zext32 (s/ r6 2))") -__msg("w1 s/= w7 {{.*}}; r1 r6 -> (zext32 (s/ r6 r7))") +__msg("w1 s/= 2 {{.*}}; r1 r6 -> (zext32 (s/ (sext32 r6) 2))") +__msg("w1 s/= w7 {{.*}}; r1 r6 -> (zext32 (s/ (sext32 r6) (sext32 r7)))") __msg("r1 %= 2 {{.*}}; r1 r6 -> (% r6 2)") __msg("r1 %= r7 {{.*}}; r1 r6 -> (% r6 r7)") -__msg("w1 %= 2 {{.*}}; r1 r6 -> (zext32 (% r6 2))") -__msg("w1 %= w7 {{.*}}; r1 r6 -> (zext32 (% r6 r7))") +__msg("w1 %= 2 {{.*}}; r1 r6 -> (zext32 (% (zext32 r6) 2))") +__msg("w1 %= w7 {{.*}}; r1 r6 -> (zext32 (% (zext32 r6) (zext32 r7)))") __msg("r1 s%= 2 {{.*}}; r1 r6 -> (s% r6 2)") __msg("r1 s%= r7 {{.*}}; r1 r6 -> (s% r6 r7)") -__msg("w1 s%= 2 {{.*}}; r1 r6 -> (zext32 (s% r6 2))") -__msg("w1 s%= w7 {{.*}}; r1 r6 -> (zext32 (s% r6 r7))") +__msg("w1 s%= 2 {{.*}}; r1 r6 -> (zext32 (s% (sext32 r6) 2))") +__msg("w1 s%= w7 {{.*}}; r1 r6 -> (zext32 (s% (sext32 r6) (sext32 r7)))") __msg("r1 |= 2 {{.*}}; r1 r6 -> (| r6 2)") __msg("r1 |= r7 {{.*}}; r1 r6 -> (| r6 r7)") __msg("w1 |= 2 {{.*}}; r1 r6 -> (zext32 (| r6 2))") @@ -363,15 +363,15 @@ __msg("w1 ^= w7 {{.*}}; r1 r6 -> (zext32 (^ r6 r7))") __msg("r1 <<= 2 {{.*}}; r1 r6 -> (<< r6 2)") __msg("r1 <<= r7 {{.*}}; r1 r6 -> (<< r6 r7)") __msg("w1 <<= 2 {{.*}}; r1 r6 -> (zext32 (<< r6 2))") -__msg("w1 <<= w7 {{.*}}; r1 r6 -> (zext32 (<< r6 r7))") +__msg("w1 <<= w7 {{.*}}; r1 r6 -> (zext32 (<< r6 (& r7 31)))") __msg("r1 >>= 2 {{.*}}; r1 r6 -> (>> r6 2)") __msg("r1 >>= r7 {{.*}}; r1 r6 -> (>> r6 r7)") -__msg("w1 >>= 2 {{.*}}; r1 r6 -> (zext32 (>> r6 2))") -__msg("w1 >>= w7 {{.*}}; r1 r6 -> (zext32 (>> r6 r7))") +__msg("w1 >>= 2 {{.*}}; r1 r6 -> (zext32 (>> (zext32 r6) 2))") +__msg("w1 >>= w7 {{.*}}; r1 r6 -> (zext32 (>> (zext32 r6) (& r7 31)))") __msg("r1 s>>= 2 {{.*}}; r1 r6 -> (s>> r6 2)") __msg("r1 s>>= r7 {{.*}}; r1 r6 -> (s>> r6 r7)") -__msg("w1 s>>= 2 {{.*}}; r1 r6 -> (zext32 (s>> r6 2))") -__msg("w1 s>>= w7 {{.*}}; r1 r6 -> (zext32 (s>> r6 r7))") +__msg("w1 s>>= 2 {{.*}}; r1 r6 -> (zext32 (s>> (sext32 r6) 2))") +__msg("w1 s>>= w7 {{.*}}; r1 r6 -> (zext32 (s>> (sext32 r6) (& r7 31)))") __msg("r1 = -r1 {{.*}}; r1 r6 -> (- r6)") __msg("w1 = -w1 {{.*}}; r1 r6 -> (zext32 (- r6))") __msg("r1 = 42 {{.*}}; r1 r6 -> 42") -- 2.55.0