[PATCH bpf v2 1/2] bpf, x86: Fix signed division and modulo in the i386 JIT

[Nicholas Dudar]

RFC9669 defines SDIV and SMOD, encoded as DIV and MOD with an offset of
1, as signed division and modulo, which the interpreter implements. The
i386 JIT ignores the offset and emits an unsigned div for both, so for
ALU32 -1 s/ 2 returns 0x7fffffff instead of 0. A verifier-accepted
program can therefore use values outside the range proved by the
verifier.

Emit cdq and idiv when the offset is 1. The verifier has rejected or
patched out a zero divisor and INT_MIN s/ -1 before the JIT runs, so
idiv cannot trap. ALU64 DIV and MOD are still left to the interpreter.

On an unpatched i386 kernel, an SDIV and an SMOD test program each
passed a helper a length beyond the verifier's bound. Both stayed
within it after this change.

Found by manually comparing the signed DIV/MOD handling of the BPF
JITs.

On i386 under qemu, with test_progs built as a 32-bit binary from the
same tree:

  # ./test_progs -t verifier_movsx,verifier_sdiv,jit_insns \
    -d jit_insns_blinded,'verifier_movsx/*@unpriv' -w 600
  [...]
  #191/3   jit_insns/alu_imm:OK
  #191/4   jit_insns/alu_reg:OK
  #191/5   jit_insns/alu_imm_regs:OK
  #191/6   jit_insns/div_const:OK
  #191/7   jit_insns/alu_reg_pairs:OK
  #191/8   jit_insns/alu_edges:OK
  [...]
  #650     verifier_sdiv:OK (SKIP: 16/144)
  Summary: 1/167 PASSED, 16 SKIPPED, 2/11 FAILED

  # ./test_progs -t jit_insns_blinded -w 600
  [...]
  #192     jit_insns_blinded:OK
  Summary: 1/14 PASSED, 0 SKIPPED, 0/0 FAILED

Without this change, the six jit_insns subtests above, four of
jit_insns_blinded and 50 of verifier_sdiv fail. The 11 failures left
are the five MOVSX ones fixed by the next patch and six jit_insns
subtests that fail without the series as well.

Fixes: ec0e2da95f72 ("bpf: Support new signed div/mod instructions.")
Signed-off-by: Nicholas Dudar <main.kalliope@xxxxxxxxx>
---
 arch/x86/net/bpf_jit_comp32.c | 25 +++++++++++++++++--------
 1 file changed, 17 insertions(+), 8 deletions(-)

diff --git a/arch/x86/net/bpf_jit_comp32.c b/arch/x86/net/bpf_jit_comp32.c
index 852baf2e4db4..012161da3e82 100644
--- a/arch/x86/net/bpf_jit_comp32.c
+++ b/arch/x86/net/bpf_jit_comp32.c
@@ -432,11 +432,13 @@ static inline void emit_ia32_to_be_r64(const u8 dst[], s32 val,
  * ALU operation (32 bit)
  * dst = dst (div|mod) src
  */
-static inline void emit_ia32_div_mod_r(const u8 op, const u8 dst, const u8 src,
-				       bool dstk, bool sstk, u8 **pprog)
+static inline void emit_ia32_div_mod_r(const struct bpf_insn *insn, const u8 dst,
+				       const u8 src, bool dstk, bool sstk, u8 **pprog)
 {
 	u8 *prog = *pprog;
 	int cnt = 0;
+	const u8 op = BPF_OP(insn->code);
+	const bool is_signed = (insn->off == 1);
 
 	if (sstk)
 		/* mov ecx,dword ptr [ebp+off] */
@@ -454,10 +456,17 @@ static inline void emit_ia32_div_mod_r(const u8 op, const u8 dst, const u8 src,
 		/* mov eax,dst */
 		EMIT2(0x8B, add_2reg(0xC0, dst, IA32_EAX));
 
-	/* xor edx,edx */
-	EMIT2(0x31, add_2reg(0xC0, IA32_EDX, IA32_EDX));
-	/* div ecx */
-	EMIT2(0xF7, add_1reg(0xF0, IA32_ECX));
+	if (is_signed) {
+		/* cdq */
+		EMIT1(0x99);
+		/* idiv ecx */
+		EMIT2(0xF7, add_1reg(0xF8, IA32_ECX));
+	} else {
+		/* xor edx,edx */
+		EMIT2(0x31, add_2reg(0xC0, IA32_EDX, IA32_EDX));
+		/* div ecx */
+		EMIT2(0xF7, add_1reg(0xF0, IA32_ECX));
+	}
 
 	if (op == BPF_MOD) {
 		if (dstk)
@@ -1795,14 +1804,14 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
 		case BPF_ALU | BPF_MOD | BPF_X:
 			switch (BPF_SRC(code)) {
 			case BPF_X:
-				emit_ia32_div_mod_r(BPF_OP(code), dst_lo,
+				emit_ia32_div_mod_r(insn, dst_lo,
 						    src_lo, dstk, sstk, &prog);
 				break;
 			case BPF_K:
 				/* mov ecx,imm32*/
 				EMIT2_off32(0xC7, add_1reg(0xC0, IA32_ECX),
 					    imm32);
-				emit_ia32_div_mod_r(BPF_OP(code), dst_lo,
+				emit_ia32_div_mod_r(insn, dst_lo,
 						    IA32_ECX, dstk, false,
 						    &prog);
 				break;

-- 
2.53.0