Skip to contentSkip to conversation

bpf, x86: Small optimization in comparing against imm0

PATCH Applied Daniel Borkmann 4 participants 6 messages Oct 2, 2019 – Oct 4, 2019

Subsystems (7)
lore
Share & tools
lore

Daniel Borkmann

author maintainer
#0 lore raw

PATCH 1/2 bpf, x86: Small optimization in comparing against imm0

Replace 'cmp reg, 0' with 'test reg, reg' for comparisons against zero. Saves 1 byte of instruction encoding per occurrence. The flag results of test 'reg, reg' are identical to 'cmp reg, 0' in all cases except for AF which we don't use/care about. In terms of macro-fusibility in combination with a subsequent conditional jump instruction, both have the same properties for the jumps used in the JIT translation. For example, same JITed Cilium program can shrink a bit from e.g. 12,455 to 12,317 bytes as tests with 0 are used quite frequently.

---
 arch/x86/net/bpf_jit_comp.c | 10 ++++++++++
 1 file changed, 10 insertions(+)
arch/x86/net/bpf_jit_comp.c +10 -0
index 991549a1c5f3..3ad2ba1ad855 100644
@@ -909,6 +909,16 @@ xadd:			if (is_imm8(insn->off))
 		case BPF_JMP32 | BPF_JSLT | BPF_K:
 		case BPF_JMP32 | BPF_JSGE | BPF_K:
 		case BPF_JMP32 | BPF_JSLE | BPF_K:
+			/* test dst_reg, dst_reg to save one extra byte */
+			if (imm32 == 0) {
+				if (BPF_CLASS(insn->code) == BPF_JMP)
+					EMIT1(add_2mod(0x48, dst_reg, dst_reg));
+				else if (is_ereg(dst_reg))
+					EMIT1(add_2mod(0x40, dst_reg, dst_reg));
+				EMIT2(0x85, add_2reg(0xC0, dst_reg, dst_reg));
+				goto emit_cond_jmp;
+			}
+
 			/* cmp dst_reg, imm8/32 */
 			if (BPF_CLASS(insn->code) == BPF_JMP)
 				EMIT1(add_1mod(0x48, dst_reg));
Signature · 1 line
2.17.1
author maintainer
#1 lore raw

PATCH 2/2 bpf: Add loop test case with 32 bit reg comparison against 0

Add a loop test with 32 bit register against 0 immediate:

  # ./test_verifier 631
  #631/p taken loop with back jump to 1st insn, 2 OK

Disassembly:

[...]
1b: test %edi,%edi
1d: jne 0x0000000000000014
[...]

Pretty much similar to prior "taken loop with back jump to 1st insn" test case just as jmp32 variant.

---
 tools/testing/selftests/bpf/verifier/loops1.c | 17 +++++++++++++++++
 1 file changed, 17 insertions(+)
tools/testing/selftests/bpf/verifier/loops1.c +17 -0
index 1fc4e61e9f9f..1af37187dc12 100644
@@ -187,3 +187,20 @@
 	.prog_type = BPF_PROG_TYPE_XDP,
 	.retval = 55,
 },
+{
+	"taken loop with back jump to 1st insn, 2",
+	.insns = {
+	BPF_MOV64_IMM(BPF_REG_1, 10),
+	BPF_MOV64_IMM(BPF_REG_2, 0),
+	BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 1, 0, 1),
+	BPF_EXIT_INSN(),
+	BPF_ALU64_REG(BPF_ADD, BPF_REG_2, BPF_REG_1),
+	BPF_ALU64_IMM(BPF_SUB, BPF_REG_1, 1),
+	BPF_JMP32_IMM(BPF_JNE, BPF_REG_1, 0, -3),
+	BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
+	BPF_EXIT_INSN(),
+	},
+	.result = ACCEPT,
+	.prog_type = BPF_PROG_TYPE_XDP,
+	.retval = 55,
+},
Signature · 1 line
2.17.1
Acked-by on v1 2/2
#2 lore raw

Re: [PATCH bpf-next 2/2] bpf: Add loop test case with 32 bit reg comparison against 0

Quoted 9 lines · Daniel Borkmann

Add a loop test with 32 bit register against 0 immediate:

  # ./test_verifier 631
  #631/p taken loop with back jump to 1st insn, 2 OK

Disassembly:

[...]

Quoted 8 lines
  1b:   test   %edi,%edi
  1d:   jne    0x0000000000000014

[...]

Pretty much similar to prior "taken loop with back jump to 1st insn" test case just as jmp32 variant.

Acked-by on v1 1/2
#3 lore raw
In reply to Daniel Borkmann
Quoted 11 lines · Daniel Borkmann

Replace 'cmp reg, 0' with 'test reg, reg' for comparisons against zero. Saves 1 byte of instruction encoding per occurrence. The flag results of test 'reg, reg' are identical to 'cmp reg, 0' in all cases except for AF which we don't use/care about. In terms of macro-fusibility in combination with a subsequent conditional jump instruction, both have the same properties for the jumps used in the JIT translation. For example, same JITed Cilium program can shrink a bit from e.g. 12,455 to 12,317 bytes as tests with 0 are used quite frequently.

Quoted 1 line
#4 lore raw
Quoted 12 lines · Song Liu
Quoted 11 lines · Daniel Borkmann

Replace 'cmp reg, 0' with 'test reg, reg' for comparisons against zero. Saves 1 byte of instruction encoding per occurrence. The flag results of test 'reg, reg' are identical to 'cmp reg, 0' in all cases except for AF which we don't use/care about. In terms of macro-fusibility in combination with a subsequent conditional jump instruction, both have the same properties for the jumps used in the JIT translation. For example, same JITed Cilium program can shrink a bit from e.g. 12,455 to 12,317 bytes as tests with 0 are used quite frequently.

Quoted 3 lines
Quoted 1 line

Bonus points for causing me to spend the morning remembering the differences between cmd, and, or, and test.

Also wonder if at some point we should clean up the jit a bit and add some defines/helpers for all the open coded opcodes and such.

#5 lore raw
Quoted 18 lines · John Fastabend
Quoted 12 lines · Song Liu
Quoted 11 lines · Daniel Borkmann

Replace 'cmp reg, 0' with 'test reg, reg' for comparisons against zero. Saves 1 byte of instruction encoding per occurrence. The flag results of test 'reg, reg' are identical to 'cmp reg, 0' in all cases except for AF which we don't use/care about. In terms of macro-fusibility in combination with a subsequent conditional jump instruction, both have the same properties for the jumps used in the JIT translation. For example, same JITed Cilium program can shrink a bit from e.g. 12,455 to 12,317 bytes as tests with 0 are used quite frequently.

Quoted 3 lines
Quoted 1 line
Quoted 7 lines

Bonus points for causing me to spend the morning remembering the differences between cmd, and, or, and test.

Also wonder if at some point we should clean up the jit a bit and add some defines/helpers for all the open coded opcodes and such.

Applied both. Thanks