Skip to contentSkip to conversation

bpf: fix bug in x64 JIT

PATCH Applied Alexei Starovoitov 3 participants 7 messages Jul 31, 2019 – Aug 1, 2019

Subsystems (7)
lore
Share & tools
lore

Alexei Starovoitov

author maintainer
#0 lore raw

cover bpf: fix bug in x64 JIT

Fix bug in computation of the jump offset to 1st instruction in BPF JIT and add 2 tests.

Alexei Starovoitov (2):
bpf: fix x64 JIT code generation for jmp to 1st insn selftests/bpf: tests for jmp to 1st insn

 arch/x86/net/bpf_jit_comp.c                   |  7 +++--
 tools/testing/selftests/bpf/verifier/loops1.c | 28 +++++++++++++++++++
 2 files changed, 32 insertions(+), 3 deletions(-)
Signature · 1 line
2.20.0
author maintainer
#1 lore raw

PATCH 1/2 bpf: fix x64 JIT code generation for jmp to 1st insn

Introduction of bounded loops exposed old bug in x64 JIT. JIT maintains the array of offsets to the end of all instructions to compute jmp offsets.
addrs[0] - offset of the end of the 1st insn (that includes prologue). addrs[1] - offset of the end of the 2nd insn.
JIT didn't keep the offset of the beginning of the 1st insn, since classic BPF didn't have backward jumps and valid extended BPF couldn't have a branch to 1st insn, because it didn't allow loops. With bounded loops it's possible to construct a valid program that jumps backwards to the 1st insn.
Fix JIT by computing:
addrs[0] - offset of the end of prologue == start of the 1st insn. addrs[1] - offset of the end of 1st insn.

Reported-by [email protected]
Fixes 2589726d12a1 ("bpf: introduce bounded loops")
Fixes 0a14842f5a3c ("net: filter: Just In Time compiler for x86-64")
---
 arch/x86/net/bpf_jit_comp.c | 7 ++++---
 1 file changed, 4 insertions(+), 3 deletions(-)
arch/x86/net/bpf_jit_comp.c +4 -3
index eaaed5bfc4a4..a56c95805732 100644
@@ -390,8 +390,9 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
 
 	emit_prologue(&prog, bpf_prog->aux->stack_depth,
 		      bpf_prog_was_classic(bpf_prog));
+	addrs[0] = prog - temp;
 
-	for (i = 0; i < insn_cnt; i++, insn++) {
+	for (i = 1; i <= insn_cnt; i++, insn++) {
 		const s32 imm32 = insn->imm;
 		u32 dst_reg = insn->dst_reg;
 		u32 src_reg = insn->src_reg;
@@ -1105,7 +1106,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
 		extra_pass = true;
 		goto skip_init_addrs;
 	}
-	addrs = kmalloc_array(prog->len, sizeof(*addrs), GFP_KERNEL);
+	addrs = kmalloc_array(prog->len + 1, sizeof(*addrs), GFP_KERNEL);
 	if (!addrs) {
 		prog = orig_prog;
 		goto out_addrs;
@@ -1115,7 +1116,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
 	 * Before first pass, make a rough estimation of addrs[]
 	 * each BPF instruction is translated to less than 64 bytes
 	 */
-	for (proglen = 0, i = 0; i < prog->len; i++) {
+	for (proglen = 0, i = 0; i <= prog->len; i++) {
 		proglen += 64;
 		addrs[i] = proglen;
 	}
Signature · 1 line
2.20.0
Acked-by on v1 1/2
#2 lore raw

Re: [PATCH bpf 1/2] bpf: fix x64 JIT code generation for jmp to 1st insn

Quoted 18 lines · Alexei Starovoitov

Introduction of bounded loops exposed old bug in x64 JIT. JIT maintains the array of offsets to the end of all instructions to compute jmp offsets.
addrs[0] - offset of the end of the 1st insn (that includes prologue). addrs[1] - offset of the end of the 2nd insn.
JIT didn't keep the offset of the beginning of the 1st insn, since classic BPF didn't have backward jumps and valid extended BPF couldn't have a branch to 1st insn, because it didn't allow loops. With bounded loops it's possible to construct a valid program that jumps backwards to the 1st insn.
Fix JIT by computing:
addrs[0] - offset of the end of prologue == start of the 1st insn. addrs[1] - offset of the end of 1st insn.

Quoted 4 lines
Reported-by [email protected]
Fixes 2589726d12a1 ("bpf: introduce bounded loops")
Fixes 0a14842f5a3c ("net: filter: Just In Time compiler for x86-64")

Do we need similar fix for x86_32?

Thanks,
Song

Quoted 40 lines

---
arch/x86/net/bpf_jit_comp.c | 7 ++++---

1 file changed, 4 insertions(+), 3 deletions(-)
arch/x86/net/bpf_jit_comp.c +4 -3
index eaaed5bfc4a4..a56c95805732 100644
@@ -390,8 +390,9 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
 
 	emit_prologue(&prog, bpf_prog->aux->stack_depth,
 		      bpf_prog_was_classic(bpf_prog));
+	addrs[0] = prog - temp;
 
-	for (i = 0; i < insn_cnt; i++, insn++) {
+	for (i = 1; i <= insn_cnt; i++, insn++) {
 		const s32 imm32 = insn->imm;
 		u32 dst_reg = insn->dst_reg;
 		u32 src_reg = insn->src_reg;
@@ -1105,7 +1106,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
 		extra_pass = true;
 		goto skip_init_addrs;
 	}
-	addrs = kmalloc_array(prog->len, sizeof(*addrs), GFP_KERNEL);
+	addrs = kmalloc_array(prog->len + 1, sizeof(*addrs), GFP_KERNEL);
 	if (!addrs) {
 		prog = orig_prog;
 		goto out_addrs;
@@ -1115,7 +1116,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog)
 	 * Before first pass, make a rough estimation of addrs[]
 	 * each BPF instruction is translated to less than 64 bytes
 	 */
-	for (proglen = 0, i = 0; i < prog->len; i++) {
+	for (proglen = 0, i = 0; i <= prog->len; i++) {
 		proglen += 64;
 		addrs[i] = proglen;
 	}
Signature · 1 line
2.20.0
#3 lore raw

Re: [PATCH bpf 1/2] bpf: fix x64 JIT code generation for jmp to 1st insn

Quoted 19 lines · Song Liu
Quoted 19 lines · Alexei Starovoitov

Introduction of bounded loops exposed old bug in x64 JIT. JIT maintains the array of offsets to the end of all instructions to compute jmp offsets.
addrs[0] - offset of the end of the 1st insn (that includes prologue). addrs[1] - offset of the end of the 2nd insn.
JIT didn't keep the offset of the beginning of the 1st insn, since classic BPF didn't have backward jumps and valid extended BPF couldn't have a branch to 1st insn, because it didn't allow loops. With bounded loops it's possible to construct a valid program that jumps backwards to the 1st insn.
Fix JIT by computing:
addrs[0] - offset of the end of prologue == start of the 1st insn. addrs[1] - offset of the end of 1st insn.

Quoted 8 lines
Quoted 4 lines
Reported-by [email protected]
Fixes 2589726d12a1 ("bpf: introduce bounded loops")
Fixes 0a14842f5a3c ("net: filter: Just In Time compiler for x86-64")

Do we need similar fix for x86_32?

Right. x86_32 would need similar fix.

Applied to bpf tree.

#4 lore raw

Re: [PATCH bpf 1/2] bpf: fix x64 JIT code generation for jmp to 1st insn

Quoted 26 lines · Alexei Starovoitov
Quoted 24 lines · Song Liu
Quoted 23 lines · Alexei Starovoitov

Introduction of bounded loops exposed old bug in x64 JIT. JIT maintains the array of offsets to the end of all instructions to compute jmp offsets.
addrs[0] - offset of the end of the 1st insn (that includes prologue). addrs[1] - offset of the end of the 2nd insn.
JIT didn't keep the offset of the beginning of the 1st insn, since classic BPF didn't have backward jumps and valid extended BPF couldn't have a branch to 1st insn, because it didn't allow loops. With bounded loops it's possible to construct a valid program that jumps backwards to the 1st insn.
Fix JIT by computing:
addrs[0] - offset of the end of prologue == start of the 1st insn. addrs[1] - offset of the end of 1st insn.

Reported-by [email protected]
Fixes 2589726d12a1 ("bpf: introduce bounded loops")
Fixes 0a14842f5a3c ("net: filter: Just In Time compiler for x86-64")
Quoted 7 lines
Quoted 3 lines

Do we need similar fix for x86_32?

Right. x86_32 would need similar fix.

Applied to bpf tree.

Yonghong noticed that it subtly changes jited linfo. Surprisingly perf annotated output for source code in jited bpf progs looks exactly the same for several large bpf progs that I've looked at. This to be investigated later.

I've applied the fix:

arch/x86/net/bpf_jit_comp.c +0 -0
index a56c95805732..991549a1c5f3 100644
@@ -1181,7 +1181,7 @@ struct bpf_prog *bpf_int_jit_compile(struct

bpf_prog *prog)

        if (!image || !prog->is_func || extra_pass) {
                if (image)
-                       bpf_prog_fill_jited_linfo(prog, addrs);
+                       bpf_prog_fill_jited_linfo(prog, addrs + 1);
 out_addrs:
                kfree(addrs);
                kfree(jit_data);

and re-pushed bpf tree.
The new commit is here:
https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf.git/commit/?id=7c2e988f400e83501e0a3568250780609b7c8263

Thanks Yonghong!

For bpf-next we need to figure out how to make test_btf more robust. We can probably check first few insns for specific jited offsets, but I don't yet see how to make it work for all archs. And it will be annoying to keep it working with every change to jit.

author maintainer
#5 lore raw

PATCH 2/2 selftests/bpf: tests for jmp to 1st insn

In reply to Alexei Starovoitov

Add 2 tests that check JIT code generation to jumps to 1st insn. 1st test is similar to syzbot reproducer.
The backwards branch is never taken at runtime.
2nd test has branch to 1st insn that executes.
The test is written as two bpf functions, since it's not possible to construct valid single bpf program that jumps to 1st insn.

---
 tools/testing/selftests/bpf/verifier/loops1.c | 28 +++++++++++++++++++
 1 file changed, 28 insertions(+)
tools/testing/selftests/bpf/verifier/loops1.c +28 -0
index 5e980a5ab69d..1fc4e61e9f9f 100644
@@ -159,3 +159,31 @@
 	.errstr = "loop detected",
 	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
 },
+{
+	"not-taken loop with back jump to 1st insn",
+	.insns = {
+	BPF_MOV64_IMM(BPF_REG_0, 123),
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 4, -2),
+	BPF_EXIT_INSN(),
+	},
+	.result = ACCEPT,
+	.prog_type = BPF_PROG_TYPE_XDP,
+	.retval = 123,
+},
+{
+	"taken loop with back jump to 1st insn",
+	.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_JMP_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.20.0
Acked-by on v1 2/2
#6 lore raw

Re: [PATCH bpf 2/2] selftests/bpf: tests for jmp to 1st insn

Quoted 12 lines · Alexei Starovoitov

Add 2 tests that check JIT code generation to jumps to 1st insn. 1st test is similar to syzbot reproducer.
The backwards branch is never taken at runtime.
2nd test has branch to 1st insn that executes.
The test is written as two bpf functions, since it's not possible to construct valid single bpf program that jumps to 1st insn.

Quoted 43 lines

---
tools/testing/selftests/bpf/verifier/loops1.c | 28 +++++++++++++++++++

1 file changed, 28 insertions(+)
tools/testing/selftests/bpf/verifier/loops1.c +28 -0
index 5e980a5ab69d..1fc4e61e9f9f 100644
@@ -159,3 +159,31 @@
 	.errstr = "loop detected",
 	.prog_type = BPF_PROG_TYPE_TRACEPOINT,
 },
+{
+	"not-taken loop with back jump to 1st insn",
+	.insns = {
+	BPF_MOV64_IMM(BPF_REG_0, 123),
+	BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 4, -2),
+	BPF_EXIT_INSN(),
+	},
+	.result = ACCEPT,
+	.prog_type = BPF_PROG_TYPE_XDP,
+	.retval = 123,
+},
+{
+	"taken loop with back jump to 1st insn",
+	.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_JMP_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.20.0