Re: [PATCH bpf-next v2 03/15] bpf: Support new sign-extension mov insns

Yonghong Song <yhs@xxxxxxxx> · Tue, 18 Jul 2023 18:17:10 -0700

On 7/16/23 6:41 PM, Eduard Zingerman wrote:
On Wed, 2023-07-12 at 23:07 -0700, Yonghong Song wrote:
Add interpreter/jit support for new sign-extension mov insns.
The original 'MOV' insn is extended to support signed version
for both ALU and ALU64 operations. For ALU mode,
the insn->off value of 8 or 16 indicates sign-extension
from 8- or 16-bit value to 32-bit value. For ALU64 mode,
the insn->off value of 8/16/32 indicates sign-extension
from 8-, 16- or 32-bit value to 64-bit value.

Signed-off-by: Yonghong Song <yhs@xxxxxx>
---
  arch/x86/net/bpf_jit_comp.c |  43 ++++++++++-
  kernel/bpf/core.c           |  28 ++++++-
  kernel/bpf/verifier.c       | 150 +++++++++++++++++++++++++++++-------
  3 files changed, 190 insertions(+), 31 deletions(-)

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index addeea95f397..a740a1a6e71d 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -701,6 +701,38 @@ static void emit_mov_reg(u8 **pprog, bool is64, u32 dst_reg, u32 src_reg)
  	*pprog = prog;
  }
  
+static void emit_movsx_reg(u8 **pprog, int num_bits, bool is64, u32 dst_reg,
+			   u32 src_reg)
+{
+	u8 *prog = *pprog;
+
+	if (is64) {
+		/* movs[b,w,l]q dst, src */
+		if (num_bits == 8)
+			EMIT4(add_2mod(0x48, src_reg, dst_reg), 0x0f, 0xbe,
+			      add_2reg(0xC0, src_reg, dst_reg));
+		else if (num_bits == 16)
+			EMIT4(add_2mod(0x48, src_reg, dst_reg), 0x0f, 0xbf,
+			      add_2reg(0xC0, src_reg, dst_reg));
+		else if (num_bits == 32)
+			EMIT3(add_2mod(0x48, src_reg, dst_reg), 0x63,
+			      add_2reg(0xC0, src_reg, dst_reg));
+	} else {
+		/* movs[b,w]l dst, src */
+		if (num_bits == 8) {
+			EMIT4(add_2mod(0x40, src_reg, dst_reg), 0x0f, 0xbe,
+			      add_2reg(0xC0, src_reg, dst_reg));

Nit: As far as I understand 4-126 Vol. 2B of [1]
      the 0x40 prefix (REX prefix) is optional here
      (same as implemented below for num_bits == 16).

I think 0x40 prefix at least neededif register is from R8 - R15?
I use this website to do asm/disasm experiments and did
try various combinations with first 8 and later 8 registers
and it seems correct results are generated.



[1] https://cdrdv2.intel.com/v1/dl/getContent/671200


+		} else if (num_bits == 16) {
+			if (is_ereg(dst_reg) || is_ereg(src_reg))
+				EMIT1(add_2mod(0x40, src_reg, dst_reg));
+			EMIT3(add_2mod(0x0f, src_reg, dst_reg), 0xbf,

Nit: Basing on the same manual I don't understand why
      add_2mod(0x0f, src_reg, dst_reg) is used, '0xf' should suffice
      (but I tried it both ways and it works...).

From the above online assembler website.

But I will check the doc to see whether it can be simplified.


+			      add_2reg(0xC0, src_reg, dst_reg));
+		}
+	}
+
+	*pprog = prog;
+}
+
  /* Emit the suffix (ModR/M etc) for addressing *(ptr_reg + off) and val_reg */
  static void emit_insn_suffix(u8 **pprog, u32 ptr_reg, u32 val_reg, int off)
  {
@@ -1051,9 +1083,14 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
  
  		case BPF_ALU64 | BPF_MOV | BPF_X:
  		case BPF_ALU | BPF_MOV | BPF_X:
-			emit_mov_reg(&prog,
-				     BPF_CLASS(insn->code) == BPF_ALU64,
-				     dst_reg, src_reg);
+			if (insn->off == 0)
+				emit_mov_reg(&prog,
+					     BPF_CLASS(insn->code) == BPF_ALU64,
+					     dst_reg, src_reg);
+			else
+				emit_movsx_reg(&prog, insn->off,
+					       BPF_CLASS(insn->code) == BPF_ALU64,
+					       dst_reg, src_reg);
  			break;
  
  			/* neg dst */
diff --git a/kernel/bpf/core.c b/kernel/bpf/core.c
index 8a1cc658789e..fe648a158c9e 100644
--- a/kernel/bpf/core.c
+++ b/kernel/bpf/core.c
@@ -61,6 +61,7 @@
  #define AX	regs[BPF_REG_AX]
  #define ARG1	regs[BPF_REG_ARG1]
  #define CTX	regs[BPF_REG_CTX]
+#define OFF	insn->off
  #define IMM	insn->imm
  
[...]
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index fbe4ca72d4c1..5fee9f24cb5e 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -3421,7 +3421,7 @@ static int backtrack_insn(struct bpf_verifier_env *env, int idx, int subseq_idx,
  			return 0;
  		if (opcode == BPF_MOV) {
  			if (BPF_SRC(insn->code) == BPF_X) {
-				/* dreg = sreg
+				/* dreg = sreg or dreg = (s8, s16, s32)sreg
  				 * dreg needs precision after this insn
  				 * sreg needs precision before this insn
  				 */
@@ -5866,6 +5866,64 @@ static void coerce_reg_to_size_sx(struct bpf_reg_state *reg, int size)
  	set_sext64_default_val(reg, size);
  }
  
+static void set_sext32_default_val(struct bpf_reg_state *reg, int size)
+{
+	if (size == 1) {
+		reg->s32_min_value = S8_MIN;
+		reg->s32_max_value = S8_MAX;
+	} else {
+		/* size == 2 */
+		reg->s32_min_value = S16_MIN;
+		reg->s32_max_value = S16_MAX;
+	}
+	reg->u32_min_value = 0;
+	reg->u32_max_value = U32_MAX;
+}
+
+static void coerce_subreg_to_size_sx(struct bpf_reg_state *reg, int size)
+{
+	s32 init_s32_max, init_s32_min, s32_max, s32_min;
+	u32 top_smax_value, top_smin_value;
+	u32 num_bits = size * 8;
+
+	top_smax_value = ((u32)reg->s32_max_value >> num_bits) << num_bits;
+	top_smin_value = ((u32)reg->s32_min_value >> num_bits) << num_bits;
+
+	if (top_smax_value != top_smin_value)
+		goto out;
+
+	/* find the s32_min and s32_min after sign extension */
+	if (size == 1) {
+		init_s32_max = (s8)reg->s32_max_value;
+		init_s32_min = (s8)reg->s32_min_value;
+	} else {
+		/* size == 2 */
+		init_s32_max = (s16)reg->s32_max_value;
+		init_s32_min = (s16)reg->s32_min_value;
+	}
+	s32_max = max(init_s32_max, init_s32_min);
+	s32_min = min(init_s32_max, init_s32_min);
+
+	if (s32_min >= 0 && s32_max >= 0) {
+		reg->s32_min_value = s32_min;
+		reg->s32_max_value = s32_max;
+		reg->u32_min_value = 0;
+		reg->u32_max_value = U32_MAX;
+		return;
+	}
+
+	if (s32_min < 0 && s32_max < 0) {
+		reg->s32_min_value = s32_min;
+		reg->s32_max_value = s32_max;
+		reg->u32_min_value = (u32)s32_max;
+		reg->u32_max_value = (u32)s32_min;
+		return;
+	}
+
+out:
+	set_sext32_default_val(reg, size);
+}
+
  static bool bpf_map_is_rdonly(const struct bpf_map *map)
  {
  	/* A map is considered read-only if the following condition are true:
@@ -13003,11 +13061,23 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
  	} else if (opcode == BPF_MOV) {
  
  		if (BPF_SRC(insn->code) == BPF_X) {
-			if (insn->imm != 0 || insn->off != 0) {
+			if (insn->imm != 0) {
  				verbose(env, "BPF_MOV uses reserved fields\n");
  				return -EINVAL;
  			}
  
+			if (BPF_CLASS(insn->code) == BPF_ALU) {
+				if (insn->off != 0 && insn->off != 8 && insn->off != 16) {
+					verbose(env, "BPF_MOV uses reserved fields\n");
+					return -EINVAL;
+				}
+			} else {
+				if (insn->off != 0 && insn->off != 8 && insn->off != 16 && insn->off != 32) {
+					verbose(env, "BPF_MOV uses reserved fields\n");
+					return -EINVAL;
+				}
+			}
+
  			/* check src operand */
  			err = check_reg_arg(env, insn->src_reg, SRC_OP);
  			if (err)
@@ -13031,18 +13101,32 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
  				       !tnum_is_const(src_reg->var_off);
  
  			if (BPF_CLASS(insn->code) == BPF_ALU64) {
-				/* case: R1 = R2
-				 * copy register state to dest reg
-				 */
-				if (need_id)
-					/* Assign src and dst registers the same ID
-					 * that will be used by find_equal_scalars()
-					 * to propagate min/max range.
+				if (insn->off == 0) {
+					/* case: R1 = R2
+					 * copy register state to dest reg
  					 */
-					src_reg->id = ++env->id_gen;
-				copy_register_state(dst_reg, src_reg);
-				dst_reg->live |= REG_LIVE_WRITTEN;
-				dst_reg->subreg_def = DEF_NOT_SUBREG;
+					if (need_id)
+						/* Assign src and dst registers the same ID
+						 * that will be used by find_equal_scalars()
+						 * to propagate min/max range.
+						 */
+						src_reg->id = ++env->id_gen;
+					copy_register_state(dst_reg, src_reg);
+					dst_reg->live |= REG_LIVE_WRITTEN;
+					dst_reg->subreg_def = DEF_NOT_SUBREG;
+				} else {
+					/* case: R1 = (s8, s16 s32)R2 */
+					bool no_sext = src_reg->umax_value < (1ULL << (insn->off - 1));
+
+					if (no_sext && need_id)
+						src_reg->id = ++env->id_gen;
+					copy_register_state(dst_reg, src_reg);
+					if (!no_sext)
+						dst_reg->id = 0;
+					coerce_reg_to_size_sx(dst_reg, insn->off >> 3);
+					dst_reg->live |= REG_LIVE_WRITTEN;
+					dst_reg->subreg_def = DEF_NOT_SUBREG;
+				}
  			} else {
  				/* R1 = (u32) R2 */
  				if (is_pointer_value(env, insn->src_reg)) {
@@ -13051,19 +13135,33 @@ static int check_alu_op(struct bpf_verifier_env *env, struct bpf_insn *insn)
  						insn->src_reg);
  					return -EACCES;
  				} else if (src_reg->type == SCALAR_VALUE) {
-					bool is_src_reg_u32 = src_reg->umax_value <= U32_MAX;
-
-					if (is_src_reg_u32 && need_id)
-						src_reg->id = ++env->id_gen;
-					copy_register_state(dst_reg, src_reg);
-					/* Make sure ID is cleared if src_reg is not in u32 range otherwise
-					 * dst_reg min/max could be incorrectly
-					 * propagated into src_reg by find_equal_scalars()
-					 */
-					if (!is_src_reg_u32)
-						dst_reg->id = 0;
-					dst_reg->live |= REG_LIVE_WRITTEN;
-					dst_reg->subreg_def = env->insn_idx + 1;
+					if (insn->off == 0) {
+						bool is_src_reg_u32 = src_reg->umax_value <= U32_MAX;
+
+						if (is_src_reg_u32 && need_id)
+							src_reg->id = ++env->id_gen;
+						copy_register_state(dst_reg, src_reg);
+						/* Make sure ID is cleared if src_reg is not in u32 range otherwise
+						 * dst_reg min/max could be incorrectly
+						 * propagated into src_reg by find_equal_scalars()
+						 */
+						if (!is_src_reg_u32)
+							dst_reg->id = 0;
+						dst_reg->live |= REG_LIVE_WRITTEN;
+						dst_reg->subreg_def = env->insn_idx + 1;
+					} else {
+						/* case: W1 = (s8, s16)W2 */
+						bool no_sext = src_reg->umax_value < (1ULL << (insn->off - 1));
+
+						if (no_sext && need_id)
+							src_reg->id = ++env->id_gen;
+						copy_register_state(dst_reg, src_reg);
+						if (!no_sext)
+							dst_reg->id = 0;
+						dst_reg->live |= REG_LIVE_WRITTEN;
+						dst_reg->subreg_def = env->insn_idx + 1;
+						coerce_subreg_to_size_sx(dst_reg, insn->off >> 3);

I tried the following test program:

{
  "testtesttest",
  .insns = {
  BPF_MOV64_IMM(BPF_REG_7, 0xffff),
  {
  .code = BPF_ALU | BPF_MOV | BPF_X,
  .dst_reg = BPF_REG_0,
  .src_reg = BPF_REG_7,
  .off = 16,
  .imm = 0,
  },
  BPF_ALU64_IMM(BPF_RSH, BPF_REG_0, 1),
  BPF_EXIT_INSN(),
  },
  .result = ACCEPT,
  .retval = 0,
},

And it produces verification log as below:

  0: R1=ctx(off=0,imm=0) R10=fp0
  0: (b7) r7 = 65535    ; R7_w=P65535
  1: (bc) w0 = w7       ; R0_w=P65535 R7_w=P65535
  2: (77) r0 >>= 1      ; R0_w=P32767
  3: (95) exit
  ...
  FAIL retval 2147483647 != 0 (run 1/1)

Note that verifier considers R0 to be 0x7FFF at 3,
while actual value during execution is 0x7FFF'FFFF.

This is a verifier issue. Will fix.


+					}
  				} else {
  					mark_reg_unknown(env, regs,
  							 insn->dst_reg);








