Skip to contentSkip to conversation

bpf,x64: implement jump padding in jit

PATCH RESEND Superseded Gary Lin 2 participants 6 messages Jan 7, 2021 – Jan 11, 2021

Subsystems (8)

v2 of 4 Superseded Latest is v4 →

lore
Share & tools
lore

Gary Lin

author
#0 lore raw

v2 cover bpf,x64: implement jump padding in jit

This patch series implements jump padding to x64 jit to cover some corner cases that used to consume more than 20 passes and caused failure.

v2:
- Simplify the sample code in the commit description and provide the jit code
- Check the expected padding bytes with WARN_ONCE
- Move the 'padded' flag to 'struct x64_jit_data'
- Remove the EXPECTED_FAIL flag from bpf_fill_maxinsns11() in test_bpf
- Add 2 verifier tests

Gary Lin (3):
bpf,x64: pad NOPs to make images converge more easily
test_bpf: remove EXPECTED_FAIL flag from bpf_fill_maxinsns11 selftests/bpf: Add verifier test for x64 jit jump padding

 arch/x86/net/bpf_jit_comp.c                 | 86 +++++++++++++++------
 lib/test_bpf.c                              |  7 +-
 tools/testing/selftests/bpf/test_verifier.c | 43 +++++++++++
 tools/testing/selftests/bpf/verifier/jit.c  | 16 ++++
 4 files changed, 122 insertions(+), 30 deletions(-)
Signature · 1 line
2.29.2
author
#1 lore raw

PATCH RESEND v2 1/3 bpf,x64: pad NOPs to make images converge more easily

The x64 bpf jit expects bpf images converge within the given passes, but it could fail to do so with some corner cases. For example:

      l0:     ja 40
      l1:     ja 40

        [... repeated ja 40 ]

      l39:    ja 40
      l40:    ret #0

This bpf program contains 40 "ja 40" instructions which are effectively NOPs and designed to be replaced with valid code dynamically. Ideally, bpf jit should optimize those "ja 40" instructions out when translating the bpf instructions into x64 machine code. However, do_jit() can only remove one "ja 40" for offset==0 on each pass, so it requires at least 40 runs to eliminate those JMPs and exceeds the current limit of passes(20). In the end, the program got rejected when BPF_JIT_ALWAYS_ON is set even though it's legit as a classic socket filter.

To make bpf images more likely converge within 20 passes, this commit pads some instructions with NOPs in the last 5 passes:

1. conditional jumps
A possible size variance comes from the adoption of imm8 JMP. If the offset is imm8, we calculate the size difference of this BPF instruction between the previous and the current pass and fill the gap with NOPs. To avoid the recalculation of jump offset, those NOPs are inserted before the JMP code, so we have to subtract the 2 bytes of imm8 JMP when calculating the NOP number.

2. BPF_JA
There are two conditions for BPF_JA.
a.) nop jumps
If this instruction is not optimized out in the previous pass, instead of removing it, we insert the equivalent size of NOPs.
b.) label jumps
Similar to condition jumps, we prepend NOPs right before the JMP code.

To make the code concise, emit_nops() is modified to use the signed len and return the number of inserted NOPs.

For bpf-to-bpf, the 'padded' flag is introduced to 'struct x64_jit_data' so that bpf_int_jit_compile() could know whether the program is padded in the previous run or not.

After applying this patch, the corner case was loaded with the following jit code:

flen=45 proglen=77 pass=17 image=ffffffffc03367d4 from=jump pid=10097 JIT code: 00000000: 0f 1f 44 00 00 55 48 89 e5 53 41 55 31 c0 45 31 JIT code: 00000010: ed 48 89 fb eb 30 eb 2e eb 2c eb 2a eb 28 eb 26 JIT code: 00000020: eb 24 eb 22 eb 20 eb 1e eb 1c eb 1a eb 18 eb 16 JIT code: 00000030: eb 14 eb 12 eb 10 eb 0e eb 0c eb 0a eb 08 eb 06 JIT code: 00000040: eb 04 eb 02 66 90 31 c0 41 5d 5b c9 c3

0: 0f 1f 44 00 00 nop DWORD PTR [rax+rax*1+0x0]
5: 55 push rbp
6: 48 89 e5 mov rbp,rsp
9: 53 push rbx
a: 41 55 push r13
c: 31 c0 xor eax,eax
e: 45 31 ed xor r13d,r13d
11: 48 89 fb mov rbx,rdi
14: eb 30 jmp 0x46
16: eb 2e jmp 0x46
...
3e: eb 06 jmp 0x46
40: eb 04 jmp 0x46
42: eb 02 jmp 0x46
44: 66 90 xchg ax,ax
46: 31 c0 xor eax,eax
48: 41 5d pop r13
4a: 5b pop rbx
4b: c9 leave
4c: c3 ret

At the 16th pass, 15 jumps were already optimized out, and one jump was replaced with NOPs at 44 and the image converged at the 17th pass.

v2:
- Simplify the sample code in the description and provide the jit code
- Check the expected padding bytes with WARN_ONCE
- Move the 'padded' flag to 'struct x64_jit_data'

---
 arch/x86/net/bpf_jit_comp.c | 86 ++++++++++++++++++++++++++-----------
 1 file changed, 62 insertions(+), 24 deletions(-)
arch/x86/net/bpf_jit_comp.c +62 -24
index 796506dcfc42..9ecc1fd72b67 100644
@@ -789,8 +789,31 @@ static void detect_reg_usage(struct bpf_insn *insn, int insn_cnt,
 	}
 }
 
+static int emit_nops(u8 **pprog, int len)
+{
+	u8 *prog = *pprog;
+	int i, noplen, cnt = 0;
+
+	while (len > 0) {
+		noplen = len;
+
+		if (noplen > ASM_NOP_MAX)
+			noplen = ASM_NOP_MAX;
+
+		for (i = 0; i < noplen; i++)
+			EMIT1(ideal_nops[noplen][i]);
+		len -= noplen;
+	}
+
+	*pprog = prog;
+
+	return cnt;
+}
+
+#define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))
+
 static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
-		  int oldproglen, struct jit_context *ctx)
+		  int oldproglen, struct jit_context *ctx, bool jmp_padding)
 {
 	bool tail_call_reachable = bpf_prog->aux->tail_call_reachable;
 	struct bpf_insn *insn = bpf_prog->insnsi;
@@ -824,6 +847,7 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
 		u8 jmp_cond;
 		int ilen;
 		u8 *func;
+		int nops;
 
 		switch (insn->code) {
 			/* ALU */
@@ -1409,6 +1433,13 @@ xadd:			if (is_imm8(insn->off))
 			}
 			jmp_offset = addrs[i + insn->off] - addrs[i];
 			if (is_imm8(jmp_offset)) {
+				if (jmp_padding) {
+					nops = INSN_SZ_DIFF - 2;
+					WARN_ONCE((nops != 0 && nops != 4),
+						  "unexpected cond_jmp padding: %d bytes\n",
+						  nops);
+					cnt += emit_nops(&prog, nops);
+				}
 				EMIT2(jmp_cond, jmp_offset);
 			} else if (is_simm32(jmp_offset)) {
 				EMIT2_off32(0x0F, jmp_cond + 0x10, jmp_offset);
@@ -1431,11 +1462,29 @@ xadd:			if (is_imm8(insn->off))
 			else
 				jmp_offset = addrs[i + insn->off] - addrs[i];
 
-			if (!jmp_offset)
-				/* Optimize out nop jumps */
+			if (!jmp_offset) {
+				/*
+				 * If jmp_padding is enabled, the extra nops will
+				 * be inserted. Otherwise, optimize out nop jumps.
+				 */
+				if (jmp_padding) {
+					nops = INSN_SZ_DIFF;
+					WARN_ONCE((nops != 0 && nops != 2 && nops != 5),
+						  "unexpected nop jump padding: %d bytes\n",
+						  nops);
+					cnt += emit_nops(&prog, nops);
+				}
 				break;
+			}
 emit_jmp:
 			if (is_imm8(jmp_offset)) {
+				if (jmp_padding) {
+					nops = INSN_SZ_DIFF - 2;
+					WARN_ONCE((nops != 0 && nops != 3),
+						  "unexpected jump padding: %d bytes\n",
+						  nops);
+					cnt += emit_nops(&prog, INSN_SZ_DIFF - 2);
+				}
 				EMIT2(0xEB, jmp_offset);
 			} else if (is_simm32(jmp_offset)) {
 				EMIT1_off32(0xE9, jmp_offset);
@@ -1578,26 +1627,6 @@ static int invoke_bpf_prog(const struct btf_func_model *m, u8 **pprog,
 	return 0;
 }
 
-static void emit_nops(u8 **pprog, unsigned int len)
-{
-	unsigned int i, noplen;
-	u8 *prog = *pprog;
-	int cnt = 0;
-
-	while (len > 0) {
-		noplen = len;
-
-		if (noplen > ASM_NOP_MAX)
-			noplen = ASM_NOP_MAX;
-
-		for (i = 0; i < noplen; i++)
-			EMIT1(ideal_nops[noplen][i]);
-		len -= noplen;
-	}
-
-	*pprog = prog;
-}
-
 static void emit_align(u8 **pprog, u32 align)
 {
 	u8 *target, *prog = *pprog;
@@ -1970,8 +1999,12 @@ struct x64_jit_data {
 	u8 *image;
 	int proglen;
 	struct jit_context ctx;
+	bool padded;
 };
 
+#define MAX_PASSES 20
+#define PADDING_PASSES (MAX_PASSES - 5)
+
 struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
 {
 	struct bpf_binary_header *header = NULL;
@@ -1981,6 +2014,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
 	struct jit_context ctx = {};
 	bool tmp_blinded = false;
 	bool extra_pass = false;
+	bool padding = false;
 	u8 *image = NULL;
 	int *addrs;
 	int pass;
@@ -2010,6 +2044,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
 		}
 		prog->aux->jit_data = jit_data;
 	}
+	padding = jit_data->padded;
 	addrs = jit_data->addrs;
 	if (addrs) {
 		ctx = jit_data->ctx;
@@ -2043,7 +2078,9 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
 	 * pass to emit the final image.
 	 */
 	for (pass = 0; pass < 20 || image; pass++) {
-		proglen = do_jit(prog, addrs, image, oldproglen, &ctx);
+		if (!padding && pass >= PADDING_PASSES)
+			padding = true;
+		proglen = do_jit(prog, addrs, image, oldproglen, &ctx, padding);
 		if (proglen <= 0) {
 out_image:
 			image = NULL;
@@ -2097,6 +2134,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
 			jit_data->proglen = proglen;
 			jit_data->image = image;
 			jit_data->header = header;
+			jit_data->padded = padding;
 		}
 		prog->bpf_func = (void *)image;
 		prog->jited = 1;
Signature · 1 line
2.29.2
maintainer
#2 lore raw

Re: [PATCH RESEND v2 1/3] bpf,x64: pad NOPs to make images converge more easily

Quoted 137 lines · Gary Lin

The x64 bpf jit expects bpf images converge within the given passes, but it could fail to do so with some corner cases. For example:

       l0:     ja 40
       l1:     ja 40

         [... repeated ja 40 ]

       l39:    ja 40
       l40:    ret #0

This bpf program contains 40 "ja 40" instructions which are effectively NOPs and designed to be replaced with valid code dynamically. Ideally, bpf jit should optimize those "ja 40" instructions out when translating the bpf instructions into x64 machine code. However, do_jit() can only remove one "ja 40" for offset==0 on each pass, so it requires at least 40 runs to eliminate those JMPs and exceeds the current limit of passes(20). In the end, the program got rejected when BPF_JIT_ALWAYS_ON is set even though it's legit as a classic socket filter.

To make bpf images more likely converge within 20 passes, this commit pads some instructions with NOPs in the last 5 passes:

1. conditional jumps
A possible size variance comes from the adoption of imm8 JMP. If the offset is imm8, we calculate the size difference of this BPF instruction between the previous and the current pass and fill the gap with NOPs. To avoid the recalculation of jump offset, those NOPs are inserted before the JMP code, so we have to subtract the 2 bytes of imm8 JMP when calculating the NOP number.

2. BPF_JA
There are two conditions for BPF_JA.
a.) nop jumps
If this instruction is not optimized out in the previous pass, instead of removing it, we insert the equivalent size of NOPs.
b.) label jumps
Similar to condition jumps, we prepend NOPs right before the JMP code.

To make the code concise, emit_nops() is modified to use the signed len and return the number of inserted NOPs.

For bpf-to-bpf, the 'padded' flag is introduced to 'struct x64_jit_data' so that bpf_int_jit_compile() could know whether the program is padded in the previous run or not.

After applying this patch, the corner case was loaded with the following jit code:

flen=45 proglen=77 pass=17 image=ffffffffc03367d4 from=jump pid=10097 JIT code: 00000000: 0f 1f 44 00 00 55 48 89 e5 53 41 55 31 c0 45 31 JIT code: 00000010: ed 48 89 fb eb 30 eb 2e eb 2c eb 2a eb 28 eb 26 JIT code: 00000020: eb 24 eb 22 eb 20 eb 1e eb 1c eb 1a eb 18 eb 16 JIT code: 00000030: eb 14 eb 12 eb 10 eb 0e eb 0c eb 0a eb 08 eb 06 JIT code: 00000040: eb 04 eb 02 66 90 31 c0 41 5d 5b c9 c3

0: 0f 1f 44 00 00 nop DWORD PTR [rax+rax*1+0x0]
5: 55 push rbp
6: 48 89 e5 mov rbp,rsp
9: 53 push rbx
a: 41 55 push r13
c: 31 c0 xor eax,eax
e: 45 31 ed xor r13d,r13d
11: 48 89 fb mov rbx,rdi
14: eb 30 jmp 0x46
16: eb 2e jmp 0x46
...
3e: eb 06 jmp 0x46
40: eb 04 jmp 0x46
42: eb 02 jmp 0x46
44: 66 90 xchg ax,ax
46: 31 c0 xor eax,eax
48: 41 5d pop r13
4a: 5b pop rbx
4b: c9 leave
4c: c3 ret

At the 16th pass, 15 jumps were already optimized out, and one jump was replaced with NOPs at 44 and the image converged at the 17th pass.

v2:
- Simplify the sample code in the description and provide the jit code
- Check the expected padding bytes with WARN_ONCE
- Move the 'padded' flag to 'struct x64_jit_data'

---
  arch/x86/net/bpf_jit_comp.c | 86 ++++++++++++++++++++++++++-----------
  1 file changed, 62 insertions(+), 24 deletions(-)
arch/x86/net/bpf_jit_comp.c +25 -1
index 796506dcfc42..9ecc1fd72b67 100644
@@ -789,8 +789,31 @@ static void detect_reg_usage(struct bpf_insn *insn, int insn_cnt,
  	}
  }
 
+static int emit_nops(u8 **pprog, int len)
+{
+	u8 *prog = *pprog;
+	int i, noplen, cnt = 0;
+
+	while (len > 0) {
+		noplen = len;
+
+		if (noplen > ASM_NOP_MAX)
+			noplen = ASM_NOP_MAX;
+
+		for (i = 0; i < noplen; i++)
+			EMIT1(ideal_nops[noplen][i]);
+		len -= noplen;
+	}
+
+	*pprog = prog;
+
+	return cnt;
+}
+
+#define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))
+
  static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
-		  int oldproglen, struct jit_context *ctx)
+		  int oldproglen, struct jit_context *ctx, bool jmp_padding)
  {
  	bool tail_call_reachable = bpf_prog->aux->tail_call_reachable;
  	struct bpf_insn *insn = bpf_prog->insnsi;
@@ -824,6 +847,7 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
  		u8 jmp_cond;
  		int ilen;
  		u8 *func;
+		int nops;
 
  		switch (insn->code) {
  			/* ALU */

arch/x86/net/bpf_jit_comp.c xadd: if (is_imm8(insn->off)) · line 1440

Quoted 8 lines
arch/x86/net/bpf_jit_comp.c +5 -0
@@ -1409,6 +1433,13 @@ xadd:			if (is_imm8(insn->off))
  			}
  			jmp_offset = addrs[i + insn->off] - addrs[i];
  			if (is_imm8(jmp_offset)) {
+				if (jmp_padding) {
+					nops = INSN_SZ_DIFF - 2;
+					WARN_ONCE((nops != 0 && nops != 4),
+						  "unexpected cond_jmp padding: %d bytes\n",
+						  nops);

Instead of all the new WARN_ONCE() occurrences, I'd rather prefer if we do a pr_err() and reject the JITing with an error (see also the 'jmp gen bug' one).

Some folks might panic their kernel on warning, but with an error we would recover just fine by simply aborting JITing process.

Quoted 94 lines
arch/x86/net/bpf_jit_comp.c +28 -22
+					cnt += emit_nops(&prog, nops);
+				}
  				EMIT2(jmp_cond, jmp_offset);
  			} else if (is_simm32(jmp_offset)) {
  				EMIT2_off32(0x0F, jmp_cond + 0x10, jmp_offset);
@@ -1431,11 +1462,29 @@ xadd:			if (is_imm8(insn->off))
  			else
  				jmp_offset = addrs[i + insn->off] - addrs[i];
 
-			if (!jmp_offset)
-				/* Optimize out nop jumps */
+			if (!jmp_offset) {
+				/*
+				 * If jmp_padding is enabled, the extra nops will
+				 * be inserted. Otherwise, optimize out nop jumps.
+				 */
+				if (jmp_padding) {
+					nops = INSN_SZ_DIFF;
+					WARN_ONCE((nops != 0 && nops != 2 && nops != 5),
+						  "unexpected nop jump padding: %d bytes\n",
+						  nops);
+					cnt += emit_nops(&prog, nops);
+				}
  				break;
+			}
  emit_jmp:
  			if (is_imm8(jmp_offset)) {
+				if (jmp_padding) {
+					nops = INSN_SZ_DIFF - 2;
+					WARN_ONCE((nops != 0 && nops != 3),
+						  "unexpected jump padding: %d bytes\n",
+						  nops);
+					cnt += emit_nops(&prog, INSN_SZ_DIFF - 2);
+				}
  				EMIT2(0xEB, jmp_offset);
  			} else if (is_simm32(jmp_offset)) {
  				EMIT1_off32(0xE9, jmp_offset);
@@ -1578,26 +1627,6 @@ static int invoke_bpf_prog(const struct btf_func_model *m, u8 **pprog,
  	return 0;
  }
 
-static void emit_nops(u8 **pprog, unsigned int len)
-{
-	unsigned int i, noplen;
-	u8 *prog = *pprog;
-	int cnt = 0;
-
-	while (len > 0) {
-		noplen = len;
-
-		if (noplen > ASM_NOP_MAX)
-			noplen = ASM_NOP_MAX;
-
-		for (i = 0; i < noplen; i++)
-			EMIT1(ideal_nops[noplen][i]);
-		len -= noplen;
-	}
-
-	*pprog = prog;
-}
-
  static void emit_align(u8 **pprog, u32 align)
  {
  	u8 *target, *prog = *pprog;
@@ -1970,8 +1999,12 @@ struct x64_jit_data {
  	u8 *image;
  	int proglen;
  	struct jit_context ctx;
+	bool padded;
  };
 
+#define MAX_PASSES 20
+#define PADDING_PASSES (MAX_PASSES - 5)
+
  struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
  {
  	struct bpf_binary_header *header = NULL;
@@ -1981,6 +2014,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
  	struct jit_context ctx = {};
  	bool tmp_blinded = false;
  	bool extra_pass = false;
+	bool padding = false;
  	u8 *image = NULL;
  	int *addrs;
  	int pass;
@@ -2010,6 +2044,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
  		}
  		prog->aux->jit_data = jit_data;
  	}
+	padding = jit_data->padded;
  	addrs = jit_data->addrs;
  	if (addrs) {
  		ctx = jit_data->ctx;

arch/x86/net/bpf_jit_comp.c struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog) · line 2080

Quoted 3 lines
arch/x86/net/bpf_jit_comp.c +0 -0
@@ -2043,7 +2078,9 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
  	 * pass to emit the final image.
  	 */
  	for (pass = 0; pass < 20 || image; pass++) {

Nit: s/20/MAX_PASSES/ given we have the define now.

arch/x86/net/bpf_jit_comp.c struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog) · line 2081

Quoted 2 lines
arch/x86/net/bpf_jit_comp.c +1 -1
-		proglen = do_jit(prog, addrs, image, oldproglen, &ctx);
+		if (!padding && pass >= PADDING_PASSES)

Shouldn't this rather guard on !extra_pass instead of dragging this info via jit_data->padded?

What is the rationale for the latter when JIT is called again for subprog to fill in relative call locations?

Quoted 14 lines
arch/x86/net/bpf_jit_comp.c +3 -0
+			padding = true;
+		proglen = do_jit(prog, addrs, image, oldproglen, &ctx, padding);
  		if (proglen <= 0) {
  out_image:
  			image = NULL;
@@ -2097,6 +2134,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
  			jit_data->proglen = proglen;
  			jit_data->image = image;
  			jit_data->header = header;
+			jit_data->padded = padding;
  		}
  		prog->bpf_func = (void *)image;
  		prog->jited = 1;
author
#3 lore raw

Re: [PATCH RESEND v2 1/3] bpf,x64: pad NOPs to make images converge more easily

Quoted 148 lines · Daniel Borkmann
Quoted 135 lines · Gary Lin

The x64 bpf jit expects bpf images converge within the given passes, but it could fail to do so with some corner cases. For example:

       l0:     ja 40
       l1:     ja 40

         [... repeated ja 40 ]

       l39:    ja 40
       l40:    ret #0

This bpf program contains 40 "ja 40" instructions which are effectively NOPs and designed to be replaced with valid code dynamically. Ideally, bpf jit should optimize those "ja 40" instructions out when translating the bpf instructions into x64 machine code. However, do_jit() can only remove one "ja 40" for offset==0 on each pass, so it requires at least 40 runs to eliminate those JMPs and exceeds the current limit of passes(20). In the end, the program got rejected when BPF_JIT_ALWAYS_ON is set even though it's legit as a classic socket filter.

To make bpf images more likely converge within 20 passes, this commit pads some instructions with NOPs in the last 5 passes:

1. conditional jumps
A possible size variance comes from the adoption of imm8 JMP. If the offset is imm8, we calculate the size difference of this BPF instruction between the previous and the current pass and fill the gap with NOPs. To avoid the recalculation of jump offset, those NOPs are inserted before the JMP code, so we have to subtract the 2 bytes of imm8 JMP when calculating the NOP number.

2. BPF_JA
There are two conditions for BPF_JA.
a.) nop jumps
If this instruction is not optimized out in the previous pass, instead of removing it, we insert the equivalent size of NOPs.
b.) label jumps
Similar to condition jumps, we prepend NOPs right before the JMP code.

To make the code concise, emit_nops() is modified to use the signed len and return the number of inserted NOPs.

For bpf-to-bpf, the 'padded' flag is introduced to 'struct x64_jit_data' so that bpf_int_jit_compile() could know whether the program is padded in the previous run or not.

After applying this patch, the corner case was loaded with the following jit code:

flen=45 proglen=77 pass=17 image=ffffffffc03367d4 from=jump pid=10097 JIT code: 00000000: 0f 1f 44 00 00 55 48 89 e5 53 41 55 31 c0 45 31 JIT code: 00000010: ed 48 89 fb eb 30 eb 2e eb 2c eb 2a eb 28 eb 26 JIT code: 00000020: eb 24 eb 22 eb 20 eb 1e eb 1c eb 1a eb 18 eb 16 JIT code: 00000030: eb 14 eb 12 eb 10 eb 0e eb 0c eb 0a eb 08 eb 06 JIT code: 00000040: eb 04 eb 02 66 90 31 c0 41 5d 5b c9 c3

0: 0f 1f 44 00 00 nop DWORD PTR [rax+rax*1+0x0]
5: 55 push rbp
6: 48 89 e5 mov rbp,rsp
9: 53 push rbx
a: 41 55 push r13
c: 31 c0 xor eax,eax
e: 45 31 ed xor r13d,r13d
11: 48 89 fb mov rbx,rdi
14: eb 30 jmp 0x46
16: eb 2e jmp 0x46
...
3e: eb 06 jmp 0x46
40: eb 04 jmp 0x46
42: eb 02 jmp 0x46
44: 66 90 xchg ax,ax
46: 31 c0 xor eax,eax
48: 41 5d pop r13
4a: 5b pop rbx
4b: c9 leave
4c: c3 ret

At the 16th pass, 15 jumps were already optimized out, and one jump was replaced with NOPs at 44 and the image converged at the 17th pass.

v2:
- Simplify the sample code in the description and provide the jit code
- Check the expected padding bytes with WARN_ONCE
- Move the 'padded' flag to 'struct x64_jit_data'

---
  arch/x86/net/bpf_jit_comp.c | 86 ++++++++++++++++++++++++++-----------
  1 file changed, 62 insertions(+), 24 deletions(-)
arch/x86/net/bpf_jit_comp.c +25 -1
index 796506dcfc42..9ecc1fd72b67 100644
@@ -789,8 +789,31 @@ static void detect_reg_usage(struct bpf_insn *insn, int insn_cnt,
  	}
  }
+static int emit_nops(u8 **pprog, int len)
+{
+	u8 *prog = *pprog;
+	int i, noplen, cnt = 0;
+
+	while (len > 0) {
+		noplen = len;
+
+		if (noplen > ASM_NOP_MAX)
+			noplen = ASM_NOP_MAX;
+
+		for (i = 0; i < noplen; i++)
+			EMIT1(ideal_nops[noplen][i]);
+		len -= noplen;
+	}
+
+	*pprog = prog;
+
+	return cnt;
+}
+
+#define INSN_SZ_DIFF (((addrs[i] - addrs[i - 1]) - (prog - temp)))
+
  static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
-		  int oldproglen, struct jit_context *ctx)
+		  int oldproglen, struct jit_context *ctx, bool jmp_padding)
  {
  	bool tail_call_reachable = bpf_prog->aux->tail_call_reachable;
  	struct bpf_insn *insn = bpf_prog->insnsi;
@@ -824,6 +847,7 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
  		u8 jmp_cond;
  		int ilen;
  		u8 *func;
+		int nops;
  		switch (insn->code) {
  			/* ALU */

arch/x86/net/bpf_jit_comp.c xadd: if (is_imm8(insn->off)) · line 1440

Quoted 8 lines
arch/x86/net/bpf_jit_comp.c +5 -0
@@ -1409,6 +1433,13 @@ xadd:			if (is_imm8(insn->off))
  			}
  			jmp_offset = addrs[i + insn->off] - addrs[i];
  			if (is_imm8(jmp_offset)) {
+				if (jmp_padding) {
+					nops = INSN_SZ_DIFF - 2;
+					WARN_ONCE((nops != 0 && nops != 4),
+						  "unexpected cond_jmp padding: %d bytes\n",
+						  nops);

Instead of all the new WARN_ONCE() occurrences, I'd rather prefer if we do a pr_err() and reject the JITing with an error (see also the 'jmp gen bug' one).

Quoted 3 lines

Some folks might panic their kernel on warning, but with an error we would recover just fine by simply aborting JITing process.

Ok, will replace WARN_ONCE() with pr_err() and "return -EFAULT;"

Quoted 88 lines
Quoted 88 lines
arch/x86/net/bpf_jit_comp.c +28 -22
+					cnt += emit_nops(&prog, nops);
+				}
  				EMIT2(jmp_cond, jmp_offset);
  			} else if (is_simm32(jmp_offset)) {
  				EMIT2_off32(0x0F, jmp_cond + 0x10, jmp_offset);
@@ -1431,11 +1462,29 @@ xadd:			if (is_imm8(insn->off))
  			else
  				jmp_offset = addrs[i + insn->off] - addrs[i];
-			if (!jmp_offset)
-				/* Optimize out nop jumps */
+			if (!jmp_offset) {
+				/*
+				 * If jmp_padding is enabled, the extra nops will
+				 * be inserted. Otherwise, optimize out nop jumps.
+				 */
+				if (jmp_padding) {
+					nops = INSN_SZ_DIFF;
+					WARN_ONCE((nops != 0 && nops != 2 && nops != 5),
+						  "unexpected nop jump padding: %d bytes\n",
+						  nops);
+					cnt += emit_nops(&prog, nops);
+				}
  				break;
+			}
  emit_jmp:
  			if (is_imm8(jmp_offset)) {
+				if (jmp_padding) {
+					nops = INSN_SZ_DIFF - 2;
+					WARN_ONCE((nops != 0 && nops != 3),
+						  "unexpected jump padding: %d bytes\n",
+						  nops);
+					cnt += emit_nops(&prog, INSN_SZ_DIFF - 2);
+				}
  				EMIT2(0xEB, jmp_offset);
  			} else if (is_simm32(jmp_offset)) {
  				EMIT1_off32(0xE9, jmp_offset);
@@ -1578,26 +1627,6 @@ static int invoke_bpf_prog(const struct btf_func_model *m, u8 **pprog,
  	return 0;
  }
-static void emit_nops(u8 **pprog, unsigned int len)
-{
-	unsigned int i, noplen;
-	u8 *prog = *pprog;
-	int cnt = 0;
-
-	while (len > 0) {
-		noplen = len;
-
-		if (noplen > ASM_NOP_MAX)
-			noplen = ASM_NOP_MAX;
-
-		for (i = 0; i < noplen; i++)
-			EMIT1(ideal_nops[noplen][i]);
-		len -= noplen;
-	}
-
-	*pprog = prog;
-}
-
  static void emit_align(u8 **pprog, u32 align)
  {
  	u8 *target, *prog = *pprog;
@@ -1970,8 +1999,12 @@ struct x64_jit_data {
  	u8 *image;
  	int proglen;
  	struct jit_context ctx;
+	bool padded;
  };
+#define MAX_PASSES 20
+#define PADDING_PASSES (MAX_PASSES - 5)
+
  struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
  {
  	struct bpf_binary_header *header = NULL;
@@ -1981,6 +2014,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
  	struct jit_context ctx = {};
  	bool tmp_blinded = false;
  	bool extra_pass = false;
+	bool padding = false;
  	u8 *image = NULL;
  	int *addrs;
  	int pass;
@@ -2010,6 +2044,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
  		}
  		prog->aux->jit_data = jit_data;
  	}
+	padding = jit_data->padded;
  	addrs = jit_data->addrs;
Quoted 9 lines

arch/x86/net/bpf_jit_comp.c struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog) · line 2080

Quoted 6 lines
arch/x86/net/bpf_jit_comp.c +0 -0
  	if (addrs) {
  		ctx = jit_data->ctx;
@@ -2043,7 +2078,9 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
  	 * pass to emit the final image.
  	 */
  	for (pass = 0; pass < 20 || image; pass++) {

Nit: s/20/MAX_PASSES/ given we have the define now.

Will fix it in v3.

Quoted 8 lines

arch/x86/net/bpf_jit_comp.c struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog) · line 2081

Quoted 2 lines
arch/x86/net/bpf_jit_comp.c +1 -1
-		proglen = do_jit(prog, addrs, image, oldproglen, &ctx);
+		if (!padding && pass >= PADDING_PASSES)

Shouldn't this rather guard on !extra_pass instead of dragging this info via jit_data->padded?

What is the rationale for the latter when JIT is called again for subprog to fill in relative call locations?

Hmmmm, my thinking was that we only enable padding for those programs which are already padded before. But, you're right. For the programs converging without padding, enabling padding won't change the final image, so it's safe to always set "padding" to true for the extra pass.

Will remove the "padded" flag in v3.

Thanks,

Gary Lin

Quoted 15 lines
Quoted 14 lines
arch/x86/net/bpf_jit_comp.c +3 -0
+			padding = true;
+		proglen = do_jit(prog, addrs, image, oldproglen, &ctx, padding);
  		if (proglen <= 0) {
  out_image:
  			image = NULL;
@@ -2097,6 +2134,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
  			jit_data->proglen = proglen;
  			jit_data->image = image;
  			jit_data->header = header;
+			jit_data->padded = padding;
  		}
  		prog->bpf_func = (void *)image;
  		prog->jited = 1;
author
#4 lore raw

PATCH RESEND v2 2/3 test_bpf: remove EXPECTED_FAIL flag from bpf_fill_maxinsns11

In reply to Gary Lin

With NOPs padding, x64 jit now can handle the jump cases like bpf_fill_maxinsns11().

---
 lib/test_bpf.c | 7 +------
 1 file changed, 1 insertion(+), 6 deletions(-)
lib/test_bpf.c +1 -6
index ca7d635bccd9..272a9fd143ab 100644
@@ -345,7 +345,7 @@ static int __bpf_fill_ja(struct bpf_test *self, unsigned int len,
 
 static int bpf_fill_maxinsns11(struct bpf_test *self)
 {
-	/* Hits 70 passes on x86_64, so cannot get JITed there. */
+	/* Hits 70 passes on x86_64 and triggers NOPs padding. */
 	return __bpf_fill_ja(self, BPF_MAXINSNS, 68);
 }
 
@@ -5318,15 +5318,10 @@ static struct bpf_test tests[] = {
 	{
 		"BPF_MAXINSNS: Jump, gap, jump, ...",
 		{ },
-#if defined(CONFIG_BPF_JIT_ALWAYS_ON) && defined(CONFIG_X86)
-		CLASSIC | FLAG_NO_DATA | FLAG_EXPECTED_FAIL,
-#else
 		CLASSIC | FLAG_NO_DATA,
-#endif
 		{ },
 		{ { 0, 0xababcbac } },
 		.fill_helper = bpf_fill_maxinsns11,
-		.expected_errcode = -ENOTSUPP,
 	},
 	{
 		"BPF_MAXINSNS: jump over MSH",
Signature · 1 line
2.29.2
author
#5 lore raw

PATCH RESEND v2 3/3 selftests/bpf: Add verifier test for x64 jit jump padding

In reply to Gary Lin

There are two tests added into verifier's jit tests to trigger x64 jit jump padding. The first test can be represented as the following assembly code:

      1: bpf_call bpf_get_prandom_u32
      2: if r0 == 0 goto pc+128
      3: if r0 == 1 goto pc+128
         ...
    129: if r0 == 127 goto pc+128
    130: goto pc+128
    131: goto pc+127
         ...
    256: goto pc+1
    257: goto pc+0
    258: r0 = 1
    259: ret

We first store a random number to r0 and add the corresponding conditional jumps (2~129) to make verifier believe that those jump instructions from 130 to 257 are reachable. When the program is sent to x64 jit, it starts to optimize out the NOP jumps backwards from 257. Since there are 128 such jumps, the program easily reaches 15 passes and triggers jump padding.

Here is the x64 jit code of the first test:

      0:    0f 1f 44 00 00          nop    DWORD PTR [rax+rax*1+0x0]
      5:    66 90                   xchg   ax,ax
      7:    55                      push   rbp
      8:    48 89 e5                mov    rbp,rsp
      b:    e8 4c 90 75 e3          call   0xffffffffe375905c
     10:    48 83 f8 01             cmp    rax,0x1
     14:    0f 84 fe 04 00 00       je     0x518
     1a:    48 83 f8 02             cmp    rax,0x2
     1e:    0f 84 f9 04 00 00       je     0x51d
      ...
     f6:    48 83 f8 18             cmp    rax,0x18
     fa:    0f 84 8b 04 00 00       je     0x58b
    100:    48 83 f8 19             cmp    rax,0x19
    104:    0f 84 86 04 00 00       je     0x590
    10a:    48 83 f8 1a             cmp    rax,0x1a
    10e:    0f 84 81 04 00 00       je     0x595
      ...
    500:    0f 84 83 01 00 00       je     0x689
    506:    48 81 f8 80 00 00 00    cmp    rax,0x80
    50d:    0f 84 76 01 00 00       je     0x689
    513:    e9 71 01 00 00          jmp    0x689
    518:    e9 6c 01 00 00          jmp    0x689
      ...
    5fe:    e9 86 00 00 00          jmp    0x689
    603:    e9 81 00 00 00          jmp    0x689
    608:    0f 1f 00                nop    DWORD PTR [rax]
    60b:    eb 7c                   jmp    0x689
    60d:    eb 7a                   jmp    0x689
      ...
    683:    eb 04                   jmp    0x689
    685:    eb 02                   jmp    0x689
    687:    66 90                   xchg   ax,ax
    689:    b8 01 00 00 00          mov    eax,0x1
    68e:    c9                      leave
    68f:    c3                      ret

As expected, a 3 bytes NOPs is inserted at 608 due to the transition from imm32 jmp to imm8 jmp. A 2 bytes NOPs is also inserted at 687 to replace a NOP jump.

The second test is to invoke the first test as a subprog to test bpf2bpf. Per the system log, there was one more jit happened with only one pass and the same jit code was produced.

---
 tools/testing/selftests/bpf/test_verifier.c | 43 +++++++++++++++++++++
 tools/testing/selftests/bpf/verifier/jit.c  | 16 ++++++++
 2 files changed, 59 insertions(+)
tools/testing/selftests/bpf/test_verifier.c +43 -0
index 9be395d9dc64..0671e88bc15d 100644
@@ -296,6 +296,49 @@ static void bpf_fill_scale(struct bpf_test *self)
 	}
 }
 
+static int bpf_fill_torturous_jumps_insn(struct bpf_insn *insn)
+{
+	unsigned int len = 259, hlen = 128;
+	int i;
+
+	insn[0] = BPF_EMIT_CALL(BPF_FUNC_get_prandom_u32);
+	for (i = 1; i <= hlen; i++) {
+		insn[i]        = BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, i, hlen);
+		insn[i + hlen] = BPF_JMP_A(hlen - i);
+	}
+	insn[len - 2] = BPF_MOV64_IMM(BPF_REG_0, 1);
+	insn[len - 1] = BPF_EXIT_INSN();
+
+	return len;
+}
+
+static void bpf_fill_torturous_jumps(struct bpf_test *self)
+{
+	struct bpf_insn *insn = self->fill_insns;
+	int i = 0;
+
+	switch (self->retval) {
+	case 1:
+		self->prog_len = bpf_fill_torturous_jumps_insn(insn);
+		return;
+	case 2:
+		/* main */
+		insn[i++] = BPF_RAW_INSN(BPF_JMP|BPF_CALL, 0, 1, 0, 3);
+		insn[i++] = BPF_ST_MEM(BPF_B, BPF_REG_10, -32, 0);
+		insn[i++] = BPF_MOV64_IMM(BPF_REG_0, 2);
+		insn[i++] = BPF_EXIT_INSN();
+
+		/* subprog */
+		i += bpf_fill_torturous_jumps_insn(insn + i);
+
+		self->prog_len = i;
+		return;
+	default:
+		self->prog_len = 0;
+		break;
+	}
+}
+
 /* BPF_SK_LOOKUP contains 13 instructions, if you need to fix up maps */
 #define BPF_SK_LOOKUP(func)						\
 	/* struct bpf_sock_tuple tuple = {} */				\
tools/testing/selftests/bpf/verifier/jit.c +16 -0
index c33adf344fae..b7653a334497 100644
@@ -105,3 +105,19 @@
 	.result = ACCEPT,
 	.retval = 2,
 },
+{
+	"jit: torturous jumps",
+	.insns = { },
+	.fill_helper = bpf_fill_torturous_jumps,
+	.prog_type = BPF_PROG_TYPE_SCHED_CLS,
+	.result = ACCEPT,
+	.retval = 1,
+},
+{
+	"jit: torturous jumps in subprog",
+	.insns = { },
+	.fill_helper = bpf_fill_torturous_jumps,
+	.prog_type = BPF_PROG_TYPE_SCHED_CLS,
+	.result = ACCEPT,
+	.retval = 2,
+},
Signature · 1 line
2.29.2