* [PATCH net-next v3 0/4] arm64 BPF JIT updates
@ 2016-06-09 4:18 Zi Shen Lim
2016-06-09 4:18 ` [PATCH net-next v3 1/4] bpf: fix missing header inclusion Zi Shen Lim
` (4 more replies)
0 siblings, 5 replies; 6+ messages in thread
From: Zi Shen Lim @ 2016-06-09 4:18 UTC (permalink / raw)
To: linux-arm-kernel
Updates for arm64 eBPF JIT.
The main addition here is implementation of bpf_tail_call.
#1: Fix missing header inclusion in linux/bpf.h.
#2: Add bpf_tail_call for arm64.
#3,4: Optimizations to reduce instruction count for jitted code.
Changes since v2:
- None. Resubmit per David Miller.
Changes since v1:
- Added patch #1 to address build error due to missing header inclusion
in linux/bpf.h. (Thanks to suggestion and ack by Daniel Borkmann)
Ordered it ahead of bpf_tail_call patch #2 so build error is not
triggered.
Zi Shen Lim (4):
bpf: fix missing header inclusion
arm64: bpf: implement bpf_tail_call() helper
arm64: bpf: optimize JMP_CALL
arm64: bpf: optimize LD_ABS, LD_IND
arch/arm64/net/bpf_jit.h | 3 +-
arch/arm64/net/bpf_jit_comp.c | 111 ++++++++++++++++++++++++++++++++++++------
include/linux/bpf.h | 1 +
3 files changed, 99 insertions(+), 16 deletions(-)
--
1.9.1
^ permalink raw reply [flat|nested] 6+ messages in thread* [PATCH net-next v3 1/4] bpf: fix missing header inclusion 2016-06-09 4:18 [PATCH net-next v3 0/4] arm64 BPF JIT updates Zi Shen Lim @ 2016-06-09 4:18 ` Zi Shen Lim 2016-06-09 4:18 ` [PATCH net-next v3 2/4] arm64: bpf: implement bpf_tail_call() helper Zi Shen Lim ` (3 subsequent siblings) 4 siblings, 0 replies; 6+ messages in thread From: Zi Shen Lim @ 2016-06-09 4:18 UTC (permalink / raw) To: linux-arm-kernel Commit 0fc174dea545 ("ebpf: make internal bpf API independent of CONFIG_BPF_SYSCALL ifdefs") introduced usage of ERR_PTR() in bpf_prog_get(), however did not include linux/err.h. Without this patch, when compiling arm64 BPF without CONFIG_BPF_SYSCALL: ... In file included from arch/arm64/net/bpf_jit_comp.c:21:0: include/linux/bpf.h: In function 'bpf_prog_get': include/linux/bpf.h:235:9: error: implicit declaration of function 'ERR_PTR' [-Werror=implicit-function-declaration] return ERR_PTR(-EOPNOTSUPP); ^ include/linux/bpf.h:235:9: warning: return makes pointer from integer without a cast [-Wint-conversion] In file included from include/linux/rwsem.h:17:0, from include/linux/mm_types.h:10, from include/linux/sched.h:27, from arch/arm64/include/asm/compat.h:25, from arch/arm64/include/asm/stat.h:23, from include/linux/stat.h:5, from include/linux/compat.h:12, from include/linux/filter.h:10, from arch/arm64/net/bpf_jit_comp.c:22: include/linux/err.h: At top level: include/linux/err.h:23:35: error: conflicting types for 'ERR_PTR' static inline void * __must_check ERR_PTR(long error) ^ In file included from arch/arm64/net/bpf_jit_comp.c:21:0: include/linux/bpf.h:235:9: note: previous implicit declaration of 'ERR_PTR' was here return ERR_PTR(-EOPNOTSUPP); ^ ... Fixes: 0fc174dea545 ("ebpf: make internal bpf API independent of CONFIG_BPF_SYSCALL ifdefs") Suggested-by: Daniel Borkmann <daniel@iogearbox.net> Signed-off-by: Zi Shen Lim <zlim.lnx@gmail.com> Acked-by: Daniel Borkmann <daniel@iogearbox.net> --- include/linux/bpf.h | 1 + 1 file changed, 1 insertion(+) diff --git a/include/linux/bpf.h b/include/linux/bpf.h index 8ee27b8..1bcae82 100644 --- a/include/linux/bpf.h +++ b/include/linux/bpf.h @@ -11,6 +11,7 @@ #include <linux/workqueue.h> #include <linux/file.h> #include <linux/percpu.h> +#include <linux/err.h> struct bpf_map; -- 1.9.1 ^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH net-next v3 2/4] arm64: bpf: implement bpf_tail_call() helper 2016-06-09 4:18 [PATCH net-next v3 0/4] arm64 BPF JIT updates Zi Shen Lim 2016-06-09 4:18 ` [PATCH net-next v3 1/4] bpf: fix missing header inclusion Zi Shen Lim @ 2016-06-09 4:18 ` Zi Shen Lim 2016-06-09 4:18 ` [PATCH net-next v3 3/4] arm64: bpf: optimize JMP_CALL Zi Shen Lim ` (2 subsequent siblings) 4 siblings, 0 replies; 6+ messages in thread From: Zi Shen Lim @ 2016-06-09 4:18 UTC (permalink / raw) To: linux-arm-kernel Add support for JMP_CALL_X (tail call) introduced by commit 04fd61ab36ec ("bpf: allow bpf programs to tail-call other bpf programs"). bpf_tail_call() arguments: ctx - context pointer passed to next program array - pointer to map which type is BPF_MAP_TYPE_PROG_ARRAY index - index inside array that selects specific program to run In this implementation arm64 JIT jumps into callee program after prologue, so callee program reuses the same stack. For tail_call_cnt, we use the callee-saved R26 (which was already saved/restored but previously unused by JIT). With this patch a tail call generates the following code on arm64: if (index >= array->map.max_entries) goto out; 34: mov x10, #0x10 // #16 38: ldr w10, [x1,x10] 3c: cmp w2, w10 40: b.ge 0x0000000000000074 if (tail_call_cnt > MAX_TAIL_CALL_CNT) goto out; tail_call_cnt++; 44: mov x10, #0x20 // #32 48: cmp x26, x10 4c: b.gt 0x0000000000000074 50: add x26, x26, #0x1 prog = array->ptrs[index]; if (prog == NULL) goto out; 54: mov x10, #0x68 // #104 58: ldr x10, [x1,x10] 5c: ldr x11, [x10,x2] 60: cbz x11, 0x0000000000000074 goto *(prog->bpf_func + prologue_size); 64: mov x10, #0x20 // #32 68: ldr x10, [x11,x10] 6c: add x10, x10, #0x20 70: br x10 74: Signed-off-by: Zi Shen Lim <zlim.lnx@gmail.com> --- arch/arm64/net/bpf_jit.h | 3 +- arch/arm64/net/bpf_jit_comp.c | 105 ++++++++++++++++++++++++++++++++++++++---- 2 files changed, 98 insertions(+), 10 deletions(-) diff --git a/arch/arm64/net/bpf_jit.h b/arch/arm64/net/bpf_jit.h index aee5637..7c16e54 100644 --- a/arch/arm64/net/bpf_jit.h +++ b/arch/arm64/net/bpf_jit.h @@ -1,7 +1,7 @@ /* * BPF JIT compiler for ARM64 * - * Copyright (C) 2014-2015 Zi Shen Lim <zlim.lnx@gmail.com> + * Copyright (C) 2014-2016 Zi Shen Lim <zlim.lnx@gmail.com> * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License version 2 as @@ -55,6 +55,7 @@ #define A64_BL(imm26) A64_BRANCH((imm26) << 2, LINK) /* Unconditional branch (register) */ +#define A64_BR(Rn) aarch64_insn_gen_branch_reg(Rn, AARCH64_INSN_BRANCH_NOLINK) #define A64_BLR(Rn) aarch64_insn_gen_branch_reg(Rn, AARCH64_INSN_BRANCH_LINK) #define A64_RET(Rn) aarch64_insn_gen_branch_reg(Rn, AARCH64_INSN_BRANCH_RETURN) diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c index 49ba37e..51abc97 100644 --- a/arch/arm64/net/bpf_jit_comp.c +++ b/arch/arm64/net/bpf_jit_comp.c @@ -18,6 +18,7 @@ #define pr_fmt(fmt) "bpf_jit: " fmt +#include <linux/bpf.h> #include <linux/filter.h> #include <linux/printk.h> #include <linux/skbuff.h> @@ -33,6 +34,7 @@ int bpf_jit_enable __read_mostly; #define TMP_REG_1 (MAX_BPF_JIT_REG + 0) #define TMP_REG_2 (MAX_BPF_JIT_REG + 1) +#define TCALL_CNT (MAX_BPF_JIT_REG + 2) /* Map BPF registers to A64 registers */ static const int bpf2a64[] = { @@ -54,6 +56,8 @@ static const int bpf2a64[] = { /* temporary registers for internal BPF JIT */ [TMP_REG_1] = A64_R(10), [TMP_REG_2] = A64_R(11), + /* tail_call_cnt */ + [TCALL_CNT] = A64_R(26), /* temporary register for blinding constants */ [BPF_REG_AX] = A64_R(9), }; @@ -146,13 +150,18 @@ static inline int epilogue_offset(const struct jit_ctx *ctx) #define STACK_SIZE STACK_ALIGN(_STACK_SIZE) -static void build_prologue(struct jit_ctx *ctx) +#define PROLOGUE_OFFSET 8 + +static int build_prologue(struct jit_ctx *ctx) { const u8 r6 = bpf2a64[BPF_REG_6]; const u8 r7 = bpf2a64[BPF_REG_7]; const u8 r8 = bpf2a64[BPF_REG_8]; const u8 r9 = bpf2a64[BPF_REG_9]; const u8 fp = bpf2a64[BPF_REG_FP]; + const u8 tcc = bpf2a64[TCALL_CNT]; + const int idx0 = ctx->idx; + int cur_offset; /* * BPF prog stack layout @@ -162,8 +171,6 @@ static void build_prologue(struct jit_ctx *ctx) * |FP/LR| * current A64_FP => -16:+-----+ * | ... | callee saved registers - * +-----+ - * | | x25/x26 * BPF fp register => -64:+-----+ <= (BPF_FP) * | | * | ... | BPF prog stack @@ -183,18 +190,90 @@ static void build_prologue(struct jit_ctx *ctx) emit(A64_PUSH(A64_FP, A64_LR, A64_SP), ctx); emit(A64_MOV(1, A64_FP, A64_SP), ctx); - /* Save callee-saved register */ + /* Save callee-saved registers */ emit(A64_PUSH(r6, r7, A64_SP), ctx); emit(A64_PUSH(r8, r9, A64_SP), ctx); + emit(A64_PUSH(fp, tcc, A64_SP), ctx); - /* Save fp (x25) and x26. SP requires 16 bytes alignment */ - emit(A64_PUSH(fp, A64_R(26), A64_SP), ctx); - - /* Set up BPF prog stack base register (x25) */ + /* Set up BPF prog stack base register */ emit(A64_MOV(1, fp, A64_SP), ctx); + /* Initialize tail_call_cnt */ + emit(A64_MOVZ(1, tcc, 0, 0), ctx); + /* Set up function call stack */ emit(A64_SUB_I(1, A64_SP, A64_SP, STACK_SIZE), ctx); + + cur_offset = ctx->idx - idx0; + if (cur_offset != PROLOGUE_OFFSET) { + pr_err_once("PROLOGUE_OFFSET = %d, expected %d!\n", + cur_offset, PROLOGUE_OFFSET); + return -1; + } + return 0; +} + +static int out_offset = -1; /* initialized on the first pass of build_body() */ +static int emit_bpf_tail_call(struct jit_ctx *ctx) +{ + /* bpf_tail_call(void *prog_ctx, struct bpf_array *array, u64 index) */ + const u8 r2 = bpf2a64[BPF_REG_2]; + const u8 r3 = bpf2a64[BPF_REG_3]; + + const u8 tmp = bpf2a64[TMP_REG_1]; + const u8 prg = bpf2a64[TMP_REG_2]; + const u8 tcc = bpf2a64[TCALL_CNT]; + const int idx0 = ctx->idx; +#define cur_offset (ctx->idx - idx0) +#define jmp_offset (out_offset - (cur_offset)) + size_t off; + + /* if (index >= array->map.max_entries) + * goto out; + */ + off = offsetof(struct bpf_array, map.max_entries); + emit_a64_mov_i64(tmp, off, ctx); + emit(A64_LDR32(tmp, r2, tmp), ctx); + emit(A64_CMP(0, r3, tmp), ctx); + emit(A64_B_(A64_COND_GE, jmp_offset), ctx); + + /* if (tail_call_cnt > MAX_TAIL_CALL_CNT) + * goto out; + * tail_call_cnt++; + */ + emit_a64_mov_i64(tmp, MAX_TAIL_CALL_CNT, ctx); + emit(A64_CMP(1, tcc, tmp), ctx); + emit(A64_B_(A64_COND_GT, jmp_offset), ctx); + emit(A64_ADD_I(1, tcc, tcc, 1), ctx); + + /* prog = array->ptrs[index]; + * if (prog == NULL) + * goto out; + */ + off = offsetof(struct bpf_array, ptrs); + emit_a64_mov_i64(tmp, off, ctx); + emit(A64_LDR64(tmp, r2, tmp), ctx); + emit(A64_LDR64(prg, tmp, r3), ctx); + emit(A64_CBZ(1, prg, jmp_offset), ctx); + + /* goto *(prog->bpf_func + prologue_size); */ + off = offsetof(struct bpf_prog, bpf_func); + emit_a64_mov_i64(tmp, off, ctx); + emit(A64_LDR64(tmp, prg, tmp), ctx); + emit(A64_ADD_I(1, tmp, tmp, sizeof(u32) * PROLOGUE_OFFSET), ctx); + emit(A64_BR(tmp), ctx); + + /* out: */ + if (out_offset == -1) + out_offset = cur_offset; + if (cur_offset != out_offset) { + pr_err_once("tail_call out_offset = %d, expected %d!\n", + cur_offset, out_offset); + return -1; + } + return 0; +#undef cur_offset +#undef jmp_offset } static void build_epilogue(struct jit_ctx *ctx) @@ -506,6 +585,11 @@ emit_cond_jmp: emit(A64_POP(A64_FP, A64_LR, A64_SP), ctx); break; } + /* tail call */ + case BPF_JMP | BPF_CALL | BPF_X: + if (emit_bpf_tail_call(ctx)) + return -EFAULT; + break; /* function return */ case BPF_JMP | BPF_EXIT: /* Optimization: when last instruction is EXIT, @@ -780,7 +864,10 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog) goto out_off; } - build_prologue(&ctx); + if (build_prologue(&ctx)) { + prog = orig_prog; + goto out_off; + } ctx.epilogue_offset = ctx.idx; build_epilogue(&ctx); -- 1.9.1 ^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH net-next v3 3/4] arm64: bpf: optimize JMP_CALL 2016-06-09 4:18 [PATCH net-next v3 0/4] arm64 BPF JIT updates Zi Shen Lim 2016-06-09 4:18 ` [PATCH net-next v3 1/4] bpf: fix missing header inclusion Zi Shen Lim 2016-06-09 4:18 ` [PATCH net-next v3 2/4] arm64: bpf: implement bpf_tail_call() helper Zi Shen Lim @ 2016-06-09 4:18 ` Zi Shen Lim 2016-06-09 4:18 ` [PATCH net-next v3 4/4] arm64: bpf: optimize LD_ABS, LD_IND Zi Shen Lim 2016-06-11 6:12 ` [PATCH net-next v3 0/4] arm64 BPF JIT updates David Miller 4 siblings, 0 replies; 6+ messages in thread From: Zi Shen Lim @ 2016-06-09 4:18 UTC (permalink / raw) To: linux-arm-kernel Remove superfluous stack frame, saving us 3 instructions for every JMP_CALL. Signed-off-by: Zi Shen Lim <zlim.lnx@gmail.com> --- arch/arm64/net/bpf_jit_comp.c | 3 --- 1 file changed, 3 deletions(-) diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c index 51abc97..7ae304e 100644 --- a/arch/arm64/net/bpf_jit_comp.c +++ b/arch/arm64/net/bpf_jit_comp.c @@ -578,11 +578,8 @@ emit_cond_jmp: const u64 func = (u64)__bpf_call_base + imm; emit_a64_mov_i64(tmp, func, ctx); - emit(A64_PUSH(A64_FP, A64_LR, A64_SP), ctx); - emit(A64_MOV(1, A64_FP, A64_SP), ctx); emit(A64_BLR(tmp), ctx); emit(A64_MOV(1, r0, A64_R(0)), ctx); - emit(A64_POP(A64_FP, A64_LR, A64_SP), ctx); break; } /* tail call */ -- 1.9.1 ^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH net-next v3 4/4] arm64: bpf: optimize LD_ABS, LD_IND 2016-06-09 4:18 [PATCH net-next v3 0/4] arm64 BPF JIT updates Zi Shen Lim ` (2 preceding siblings ...) 2016-06-09 4:18 ` [PATCH net-next v3 3/4] arm64: bpf: optimize JMP_CALL Zi Shen Lim @ 2016-06-09 4:18 ` Zi Shen Lim 2016-06-11 6:12 ` [PATCH net-next v3 0/4] arm64 BPF JIT updates David Miller 4 siblings, 0 replies; 6+ messages in thread From: Zi Shen Lim @ 2016-06-09 4:18 UTC (permalink / raw) To: linux-arm-kernel Remove superfluous stack frame, saving us 3 instructions for every LD_ABS or LD_IND. Signed-off-by: Zi Shen Lim <zlim.lnx@gmail.com> --- arch/arm64/net/bpf_jit_comp.c | 3 --- 1 file changed, 3 deletions(-) diff --git a/arch/arm64/net/bpf_jit_comp.c b/arch/arm64/net/bpf_jit_comp.c index 7ae304e..b2fc97a 100644 --- a/arch/arm64/net/bpf_jit_comp.c +++ b/arch/arm64/net/bpf_jit_comp.c @@ -731,11 +731,8 @@ emit_cond_jmp: emit_a64_mov_i64(r3, size, ctx); emit(A64_SUB_I(1, r4, fp, STACK_SIZE), ctx); emit_a64_mov_i64(r5, (unsigned long)bpf_load_pointer, ctx); - emit(A64_PUSH(A64_FP, A64_LR, A64_SP), ctx); - emit(A64_MOV(1, A64_FP, A64_SP), ctx); emit(A64_BLR(r5), ctx); emit(A64_MOV(1, r0, A64_R(0)), ctx); - emit(A64_POP(A64_FP, A64_LR, A64_SP), ctx); jmp_offset = epilogue_offset(ctx); check_imm19(jmp_offset); -- 1.9.1 ^ permalink raw reply related [flat|nested] 6+ messages in thread
* [PATCH net-next v3 0/4] arm64 BPF JIT updates 2016-06-09 4:18 [PATCH net-next v3 0/4] arm64 BPF JIT updates Zi Shen Lim ` (3 preceding siblings ...) 2016-06-09 4:18 ` [PATCH net-next v3 4/4] arm64: bpf: optimize LD_ABS, LD_IND Zi Shen Lim @ 2016-06-11 6:12 ` David Miller 4 siblings, 0 replies; 6+ messages in thread From: David Miller @ 2016-06-11 6:12 UTC (permalink / raw) To: linux-arm-kernel From: Zi Shen Lim <zlim.lnx@gmail.com> Date: Wed, 8 Jun 2016 21:18:46 -0700 > Updates for arm64 eBPF JIT. Series applied to net-next, thanks. ^ permalink raw reply [flat|nested] 6+ messages in thread
end of thread, other threads:[~2016-06-11 6:12 UTC | newest] Thread overview: 6+ messages (download: mbox.gz follow: Atom feed -- links below jump to the message on this page -- 2016-06-09 4:18 [PATCH net-next v3 0/4] arm64 BPF JIT updates Zi Shen Lim 2016-06-09 4:18 ` [PATCH net-next v3 1/4] bpf: fix missing header inclusion Zi Shen Lim 2016-06-09 4:18 ` [PATCH net-next v3 2/4] arm64: bpf: implement bpf_tail_call() helper Zi Shen Lim 2016-06-09 4:18 ` [PATCH net-next v3 3/4] arm64: bpf: optimize JMP_CALL Zi Shen Lim 2016-06-09 4:18 ` [PATCH net-next v3 4/4] arm64: bpf: optimize LD_ABS, LD_IND Zi Shen Lim 2016-06-11 6:12 ` [PATCH net-next v3 0/4] arm64 BPF JIT updates David Miller
This is a public inbox, see mirroring instructions for how to clone and mirror all data and code used for this inbox; as well as URLs for NNTP newsgroup(s).