Add BPF_J{LT,LE,SLT,SLE} instructions
Subsystems (21)
Daniel Borkmann
maintainerPATCH 1/9 bpf: add BPF_J{LT,LE,SLT,SLE} instructions
In reply to Daniel BorkmannCurrently, eBPF only understands BPF_JGT (>), BPF_JGE (>=), BPF_JSGT (s>), BPF_JSGE (s>=) instructions, this means that particularly *JLT/*JLE counterparts involving immediates need to be rewritten from e.g. X < [IMM] by swapping arguments into [IMM] > X, meaning the immediate first is required to be loaded into a register Y := [IMM], such that then we can compare with Y > X. Note that the destination operand is always required to be a register.
This has the downside of having unnecessarily increased register pressure, meaning complex program would need to spill other registers temporarily to stack in order to obtain an unused register for the [IMM]. Loading to registers will thus also affect state pruning since we need to account for that register use and potentially those registers that had to be spilled/filled again. As a consequence slightly more stack space might have been used due to spilling, and BPF programs are a bit longer due to extra code involving the register load and potentially required spills/fills.
Thus, add BPF_JLT (<), BPF_JLE (<=), BPF_JSLT (s<), BPF_JSLE (s<=) counterparts to the eBPF instruction set. Modifying LLVM to remove the NegateCC() workaround [1] and allowing it to also emit the new instructions resulted in cilium's BPF programs that are injected into the fast-path to have a reduced program length in the range of 2-3% (e.g. accumulated main and tail call sections from one of the object file reduced from 4864 to 4729 insns), reduced complexity in the range of 10-30% (e.g. accumulated sections reduced in one of the cases from 116432 to 88428 insns), and reduced stack usage in the range of 1-5% (e.g. accumulated sections from one of the object files reduced from 824 to 784b). The modification for LLVM [1] will be incorporated in a backwards compatible way.
[1] https://github.com/borkmann/llvm/tree/bpf-insns
--- Documentation/networking/filter.txt | 4 + include/uapi/linux/bpf.h | 5 + kernel/bpf/core.c | 60 ++++++ lib/test_bpf.c | 364 ++++++++++++++++++++++++++++++++++++ net/core/filter.c | 21 ++- tools/include/uapi/linux/bpf.h | 5 + 6 files changed, 455 insertions(+), 4 deletions(-)
Documentation/networking/filter.txt +4 -0
@@ -906,6 +906,10 @@ If BPF_CLASS(code) == BPF_JMP, BPF_OP(code) is one of: BPF_JSGE 0x70 /* eBPF only: signed '>=' */ BPF_CALL 0x80 /* eBPF only: function call */ BPF_EXIT 0x90 /* eBPF only: function return */ + BPF_JLT 0xa0 /* eBPF only: unsigned '<' */ + BPF_JLE 0xb0 /* eBPF only: unsigned '<=' */ + BPF_JSLT 0xc0 /* eBPF only: signed '<' */ + BPF_JSLE 0xd0 /* eBPF only: signed '<=' */ So BPF_ADD | BPF_X | BPF_ALU means 32-bit addition in both classic BPF and eBPF. There are only two registers in classic BPF, so it means A += X.
include/uapi/linux/bpf.h +5 -0
@@ -30,9 +30,14 @@#define BPF_FROM_LE BPF_TO_LE#define BPF_FROM_BE BPF_TO_BE +/* jmp encodings */ #define BPF_JNE 0x50/* jump != */ +#define BPF_JLT 0xa0/* LT is unsigned, '<' */ +#define BPF_JLE 0xb0/* LE is unsigned, '<=' */ #define BPF_JSGT 0x60/* SGT is signed '>', GT in x86 */ #define BPF_JSGE 0x70/* SGE is signed '>=', GE in x86 */ +#define BPF_JSLT 0xc0/* SLT is signed, '<' */ +#define BPF_JSLE 0xd0/* SLE is signed, '<=' */ #define BPF_CALL 0x80/* function call */ #define BPF_EXIT 0x90/* function return */
kernel/bpf/core.c +60 -0
105 lines not on this page · raw message
lib/test_bpf.c +364 -0
430 lines not on this page · raw message
net/core/filter.c +17 -4
@@ -514,14 +514,27 @@ static int bpf_convert_filter(struct sock_filter *prog, int len,break ; } -/* Convert JEQ into JNE when 'jump_true' is next insn. */ -if (fp->jt ==0 &&BPF_OP (fp->code) ==BPF_JEQ ) { - insn->code =BPF_JMP |BPF_JNE | bpf_src; +/* Convert some jumps when 'jump_true' is next insn. */ +if (fp->jt ==0 ) { +switch (BPF_OP (fp->code)) { +case BPF_JEQ : + insn->code =BPF_JMP |BPF_JNE | bpf_src; +break ; +case BPF_JGT : + insn->code =BPF_JMP |BPF_JLE | bpf_src; +break ; +case BPF_JGE : + insn->code =BPF_JMP |BPF_JLT | bpf_src; +break ; +default : + goto jmp_rest; + } + target = i + fp->jf +1 ;BPF_EMIT_JMP ;break ; } - +jmp_rest:/* Other jumps are mapped into two insns: Jxx and JA. */ target = i + fp->jt +1 ; insn->code =BPF_JMP |BPF_OP (fp->code) | bpf_src;
tools/include/uapi/linux/bpf.h +5 -0
@@ -30,9 +30,14 @@#define BPF_FROM_LE BPF_TO_LE#define BPF_FROM_BE BPF_TO_BE +/* jmp encodings */ #define BPF_JNE 0x50/* jump != */ +#define BPF_JLT 0xa0/* LT is unsigned, '<' */ +#define BPF_JLE 0xb0/* LE is unsigned, '<=' */ #define BPF_JSGT 0x60/* SGT is signed '>', GT in x86 */ #define BPF_JSGE 0x70/* SGE is signed '>=', GE in x86 */ +#define BPF_JSLT 0xc0/* SLT is signed, '<' */ +#define BPF_JSLE 0xd0/* SLE is signed, '<=' */ #define BPF_CALL 0x80/* function call */ #define BPF_EXIT 0x90/* function return */
Signature · 1 line
1.9.3
Daniel Borkmann
maintainerPATCH 2/9 bpf, x86: implement jiting of BPF_J{LT,LE,SLT,SLE}
In reply to Daniel BorkmannThis work implements jiting of BPF_J{LT,LE,SLT,SLE} instructions with BPF_X/BPF_K variants for the x86_64 eBPF JIT.
--- arch/x86/net/bpf_jit_comp.c | 26 ++++++++++++++++++++++++++ 1 file changed, 26 insertions(+)
arch/x86/net/bpf_jit_comp.c +26 -0
@@ -94,7 +94,9 @@ static int bpf_size_to_x86_bytes(int bpf_size)#define X86_JNE 0x75#define X86_JBE 0x76#define X86_JA 0x77 +#define X86_JL 0x7C#define X86_JGE 0x7D +#define X86_JLE 0x7E#define X86_JG 0x7Fstatic void bpf_flush_icache (void *start,void *end)
@@ -888,9 +890,13 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,case BPF_JMP |BPF_JEQ |BPF_X :case BPF_JMP |BPF_JNE |BPF_X :case BPF_JMP |BPF_JGT |BPF_X : +case BPF_JMP |BPF_JLT |BPF_X :case BPF_JMP |BPF_JGE |BPF_X : +case BPF_JMP |BPF_JLE |BPF_X :case BPF_JMP |BPF_JSGT |BPF_X : +case BPF_JMP |BPF_JSLT |BPF_X :case BPF_JMP |BPF_JSGE |BPF_X : +case BPF_JMP |BPF_JSLE |BPF_X :/* cmp dst_reg, src_reg */ EMIT3 (add_2mod (0x48 , dst_reg, src_reg),0x39 ,add_2reg (0xC0 , dst_reg, src_reg));
@@ -911,9 +917,13 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,case BPF_JMP |BPF_JEQ |BPF_K :case BPF_JMP |BPF_JNE |BPF_K :case BPF_JMP |BPF_JGT |BPF_K : +case BPF_JMP |BPF_JLT |BPF_K :case BPF_JMP |BPF_JGE |BPF_K : +case BPF_JMP |BPF_JLE |BPF_K :case BPF_JMP |BPF_JSGT |BPF_K : +case BPF_JMP |BPF_JSLT |BPF_K :case BPF_JMP |BPF_JSGE |BPF_K : +case BPF_JMP |BPF_JSLE |BPF_K :/* cmp dst_reg, imm8/32 */ EMIT1 (add_1mod (0x48 , dst_reg));
@@ -935,18 +945,34 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,/* GT is unsigned '>', JA in x86 */ jmp_cond =X86_JA ;break ; +case BPF_JLT : +/* LT is unsigned '<', JB in x86 */ + jmp_cond =X86_JB ; +break ;case BPF_JGE :/* GE is unsigned '>=', JAE in x86 */ jmp_cond =X86_JAE ;break ; +case BPF_JLE : +/* LE is unsigned '<=', JBE in x86 */ + jmp_cond =X86_JBE ; +break ;case BPF_JSGT :/* signed '>', GT in x86 */ jmp_cond =X86_JG ;break ; +case BPF_JSLT : +/* signed '<', LT in x86 */ + jmp_cond =X86_JL ; +break ;case BPF_JSGE :/* signed '>=', GE in x86 */ jmp_cond =X86_JGE ;break ; +case BPF_JSLE : +/* signed '<=', LE in x86 */ + jmp_cond =X86_JLE ; +break ;default :/* to silence gcc warning */ return -EFAULT ; }
Signature · 1 line
1.9.3
Daniel Borkmann
maintainerPATCH 3/9 bpf, arm64: implement jiting of BPF_J{LT,LE,SLT,SLE}
In reply to Daniel BorkmannThis work implements jiting of BPF_J{LT,LE,SLT,SLE} instructions with BPF_X/BPF_K variants for the arm64 eBPF JIT.
--- arch/arm64/net/bpf_jit.h | 4 ++++ arch/arm64/net/bpf_jit_comp.c | 20 ++++++++++++++++++++ 2 files changed, 24 insertions(+)
arch/arm64/net/bpf_jit.h +4 -0
@@ -44,8 +44,12 @@#define A64_COND_NE AARCH64_INSN_COND_NE/* != */ #define A64_COND_CS AARCH64_INSN_COND_CS/* unsigned >= */ #define A64_COND_HI AARCH64_INSN_COND_HI/* unsigned > */ +#define A64_COND_LS AARCH64_INSN_COND_LS/* unsigned <= */ +#define A64_COND_CC AARCH64_INSN_COND_CC/* unsigned < */ #define A64_COND_GE AARCH64_INSN_COND_GE/* signed >= */ #define A64_COND_GT AARCH64_INSN_COND_GT/* signed > */ +#define A64_COND_LE AARCH64_INSN_COND_LE/* signed <= */ +#define A64_COND_LT AARCH64_INSN_COND_LT/* signed < */ #define A64_B_ (cond, imm19) A64_COND_BRANCH(cond, (imm19) << 2)/* Unconditional branch (immediate) */
arch/arm64/net/bpf_jit_comp.c +20 -0
@@ -527,10 +527,14 @@ static int build_insn(const struct bpf_insn *insn, struct jit_ctx *ctx)/* IF (dst COND src) JUMP off */ case BPF_JMP |BPF_JEQ |BPF_X :case BPF_JMP |BPF_JGT |BPF_X : +case BPF_JMP |BPF_JLT |BPF_X :case BPF_JMP |BPF_JGE |BPF_X : +case BPF_JMP |BPF_JLE |BPF_X :case BPF_JMP |BPF_JNE |BPF_X :case BPF_JMP |BPF_JSGT |BPF_X : +case BPF_JMP |BPF_JSLT |BPF_X :case BPF_JMP |BPF_JSGE |BPF_X : +case BPF_JMP |BPF_JSLE |BPF_X :emit (A64_CMP (1 , dst, src), ctx); emit_cond_jmp: jmp_offset =bpf2a64_offset (i + off, i, ctx);
@@ -542,9 +546,15 @@ static int build_insn(const struct bpf_insn *insn, struct jit_ctx *ctx)case BPF_JGT : jmp_cond =A64_COND_HI ;break ; +case BPF_JLT : + jmp_cond =A64_COND_CC ; +break ;case BPF_JGE : jmp_cond =A64_COND_CS ;break ; +case BPF_JLE : + jmp_cond =A64_COND_LS ; +break ;case BPF_JSET :case BPF_JNE : jmp_cond =A64_COND_NE ;
@@ -552,9 +562,15 @@ static int build_insn(const struct bpf_insn *insn, struct jit_ctx *ctx)case BPF_JSGT : jmp_cond =A64_COND_GT ;break ; +case BPF_JSLT : + jmp_cond =A64_COND_LT ; +break ;case BPF_JSGE : jmp_cond =A64_COND_GE ;break ; +case BPF_JSLE : + jmp_cond =A64_COND_LE ; +break ;default :return -EFAULT ; }
@@ -566,10 +582,14 @@ static int build_insn(const struct bpf_insn *insn, struct jit_ctx *ctx)/* IF (dst COND imm) JUMP off */ case BPF_JMP |BPF_JEQ |BPF_K :case BPF_JMP |BPF_JGT |BPF_K : +case BPF_JMP |BPF_JLT |BPF_K :case BPF_JMP |BPF_JGE |BPF_K : +case BPF_JMP |BPF_JLE |BPF_K :case BPF_JMP |BPF_JNE |BPF_K :case BPF_JMP |BPF_JSGT |BPF_K : +case BPF_JMP |BPF_JSLT |BPF_K :case BPF_JMP |BPF_JSGE |BPF_K : +case BPF_JMP |BPF_JSLE |BPF_K :emit_a64_mov_i (1 , tmp, imm, ctx);emit (A64_CMP (1 , dst, tmp), ctx); goto emit_cond_jmp;
Signature · 1 line
1.9.3
Daniel Borkmann
maintainerPATCH 4/9 bpf, sparc64: implement jiting of BPF_J{LT,LE,SLT,SLE}
In reply to Daniel BorkmannThis work implements jiting of BPF_J{LT,LE,SLT,SLE} instructions with BPF_X/BPF_K variants for the sparc64 eBPF JIT.
--- arch/sparc/net/bpf_jit_comp_64.c | 34 ++++++++++++++++++++++++++++++++++ 1 file changed, 34 insertions(+)
arch/sparc/net/bpf_jit_comp_64.c +34 -0
@@ -128,6 +128,8 @@ static u32 WDISP10(u32 off)#define BA (BRANCH | CONDA)#define BG (BRANCH | CONDG) +#define BL (BRANCH | CONDL) +#define BLE (BRANCH | CONDLE)#define BGU (BRANCH | CONDGU)#define BLEU (BRANCH | CONDLEU)#define BGE (BRANCH | CONDGE)
@@ -715,9 +717,15 @@ static int emit_compare_and_branch(const u8 code, const u8 dst, u8 src,case BPF_JGT : br_opcode =BGU ;break ; +case BPF_JLT : + br_opcode =BLU ; +break ;case BPF_JGE : br_opcode =BGEU ;break ; +case BPF_JLE : + br_opcode =BLEU ; +break ;case BPF_JSET :case BPF_JNE : br_opcode =BNE ;
@@ -725,9 +733,15 @@ static int emit_compare_and_branch(const u8 code, const u8 dst, u8 src,case BPF_JSGT : br_opcode =BG ;break ; +case BPF_JSLT : + br_opcode =BL ; +break ;case BPF_JSGE : br_opcode =BGE ;break ; +case BPF_JSLE : + br_opcode =BLE ; +break ;default :/* Make sure we dont leak kernel information to the * user.
@@ -746,18 +760,30 @@ static int emit_compare_and_branch(const u8 code, const u8 dst, u8 src,case BPF_JGT : cbcond_opcode =CBCONDGU ;break ; +case BPF_JLT : + cbcond_opcode =CBCONDLU ; +break ;case BPF_JGE : cbcond_opcode =CBCONDGEU ;break ; +case BPF_JLE : + cbcond_opcode =CBCONDLEU ; +break ;case BPF_JNE : cbcond_opcode =CBCONDNE ;break ;case BPF_JSGT : cbcond_opcode =CBCONDG ;break ; +case BPF_JSLT : + cbcond_opcode =CBCONDL ; +break ;case BPF_JSGE : cbcond_opcode =CBCONDGE ;break ; +case BPF_JSLE : + cbcond_opcode =CBCONDLE ; +break ;default :/* Make sure we dont leak kernel information to the * user.
@@ -1176,10 +1202,14 @@ static int build_insn(const struct bpf_insn *insn, struct jit_ctx *ctx)/* IF (dst COND src) JUMP off */ case BPF_JMP |BPF_JEQ |BPF_X :case BPF_JMP |BPF_JGT |BPF_X : +case BPF_JMP |BPF_JLT |BPF_X :case BPF_JMP |BPF_JGE |BPF_X : +case BPF_JMP |BPF_JLE |BPF_X :case BPF_JMP |BPF_JNE |BPF_X :case BPF_JMP |BPF_JSGT |BPF_X : +case BPF_JMP |BPF_JSLT |BPF_X :case BPF_JMP |BPF_JSGE |BPF_X : +case BPF_JMP |BPF_JSLE |BPF_X :case BPF_JMP |BPF_JSET |BPF_X : {int err;
@@ -1191,10 +1221,14 @@ static int build_insn(const struct bpf_insn *insn, struct jit_ctx *ctx)/* IF (dst COND imm) JUMP off */ case BPF_JMP |BPF_JEQ |BPF_K :case BPF_JMP |BPF_JGT |BPF_K : +case BPF_JMP |BPF_JLT |BPF_K :case BPF_JMP |BPF_JGE |BPF_K : +case BPF_JMP |BPF_JLE |BPF_K :case BPF_JMP |BPF_JNE |BPF_K :case BPF_JMP |BPF_JSGT |BPF_K : +case BPF_JMP |BPF_JSLT |BPF_K :case BPF_JMP |BPF_JSGE |BPF_K : +case BPF_JMP |BPF_JSLE |BPF_K :case BPF_JMP |BPF_JSET |BPF_K : {int err;
Signature · 1 line
1.9.3
Daniel Borkmann
maintainerPATCH 5/9 bpf, s390x: implement jiting of BPF_J{LT,LE,SLT,SLE}
In reply to Daniel BorkmannThis work implements jiting of BPF_J{LT,LE,SLT,SLE} instructions with BPF_X/BPF_K variants for the s390x eBPF JIT.
--- arch/s390/net/bpf_jit_comp.c | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+)
arch/s390/net/bpf_jit_comp.c +24 -0
@@ -1093,15 +1093,27 @@ static noinline int bpf_jit_insn(struct bpf_jit *jit, struct bpf_prog *fp, int icase BPF_JMP |BPF_JSGT |BPF_K :/* ((s64) dst > (s64) imm) */ mask =0x2000 ;/* jh */ goto branch_ks; +case BPF_JMP |BPF_JSLT |BPF_K :/* ((s64) dst < (s64) imm) */ + mask =0x4000 ;/* jl */ + goto branch_ks;case BPF_JMP |BPF_JSGE |BPF_K :/* ((s64) dst >= (s64) imm) */ mask =0xa000 ;/* jhe */ goto branch_ks; +case BPF_JMP |BPF_JSLE |BPF_K :/* ((s64) dst <= (s64) imm) */ + mask =0xc000 ;/* jle */ + goto branch_ks;case BPF_JMP |BPF_JGT |BPF_K :/* (dst_reg > imm) */ mask =0x2000 ;/* jh */ goto branch_ku; +case BPF_JMP |BPF_JLT |BPF_K :/* (dst_reg < imm) */ + mask =0x4000 ;/* jl */ + goto branch_ku;case BPF_JMP |BPF_JGE |BPF_K :/* (dst_reg >= imm) */ mask =0xa000 ;/* jhe */ goto branch_ku; +case BPF_JMP |BPF_JLE |BPF_K :/* (dst_reg <= imm) */ + mask =0xc000 ;/* jle */ + goto branch_ku;case BPF_JMP |BPF_JNE |BPF_K :/* (dst_reg != imm) */ mask =0x7000 ;/* jne */ goto branch_ku;
@@ -1119,15 +1131,27 @@ static noinline int bpf_jit_insn(struct bpf_jit *jit, struct bpf_prog *fp, int icase BPF_JMP |BPF_JSGT |BPF_X :/* ((s64) dst > (s64) src) */ mask =0x2000 ;/* jh */ goto branch_xs; +case BPF_JMP |BPF_JSLT |BPF_X :/* ((s64) dst < (s64) src) */ + mask =0x4000 ;/* jl */ + goto branch_xs;case BPF_JMP |BPF_JSGE |BPF_X :/* ((s64) dst >= (s64) src) */ mask =0xa000 ;/* jhe */ goto branch_xs; +case BPF_JMP |BPF_JSLE |BPF_X :/* ((s64) dst <= (s64) src) */ + mask =0xc000 ;/* jle */ + goto branch_xs;case BPF_JMP |BPF_JGT |BPF_X :/* (dst > src) */ mask =0x2000 ;/* jh */ goto branch_xu; +case BPF_JMP |BPF_JLT |BPF_X :/* (dst < src) */ + mask =0x4000 ;/* jl */ + goto branch_xu;case BPF_JMP |BPF_JGE |BPF_X :/* (dst >= src) */ mask =0xa000 ;/* jhe */ goto branch_xu; +case BPF_JMP |BPF_JLE |BPF_X :/* (dst <= src) */ + mask =0xc000 ;/* jle */ + goto branch_xu;case BPF_JMP |BPF_JNE |BPF_X :/* (dst != src) */ mask =0x7000 ;/* jne */ goto branch_xu;
Signature · 1 line
1.9.3
Daniel Borkmann
maintainerPATCH 6/9 bpf, ppc64: implement jiting of BPF_J{LT,LE,SLT,SLE}
In reply to Daniel BorkmannThis work implements jiting of BPF_J{LT,LE,SLT,SLE} instructions with BPF_X/BPF_K variants for the ppc64 eBPF JIT.
--- arch/powerpc/net/bpf_jit.h | 1 + arch/powerpc/net/bpf_jit_comp64.c | 20 ++++++++++++++++++++ 2 files changed, 21 insertions(+)
arch/powerpc/net/bpf_jit.h +1 -0
@@ -263,6 +263,7 @@ static inline bool is_nearbranch(int offset)#define COND_EQ (CR0_EQ | COND_CMP_TRUE)#define COND_NE (CR0_EQ | COND_CMP_FALSE)#define COND_LT (CR0_LT | COND_CMP_TRUE) +#define COND_LE (CR0_GT | COND_CMP_FALSE)#endif
arch/powerpc/net/bpf_jit_comp64.c +20 -0
@@ -795,12 +795,24 @@ static int bpf_jit_build_body(struct bpf_prog *fp, u32 *image,case BPF_JMP |BPF_JSGT |BPF_X : true_cond =COND_GT ; goto cond_branch; +case BPF_JMP |BPF_JLT |BPF_K : +case BPF_JMP |BPF_JLT |BPF_X : +case BPF_JMP |BPF_JSLT |BPF_K : +case BPF_JMP |BPF_JSLT |BPF_X : + true_cond =COND_LT ; + goto cond_branch;case BPF_JMP |BPF_JGE |BPF_K :case BPF_JMP |BPF_JGE |BPF_X :case BPF_JMP |BPF_JSGE |BPF_K :case BPF_JMP |BPF_JSGE |BPF_X : true_cond =COND_GE ; goto cond_branch; +case BPF_JMP |BPF_JLE |BPF_K : +case BPF_JMP |BPF_JLE |BPF_X : +case BPF_JMP |BPF_JSLE |BPF_K : +case BPF_JMP |BPF_JSLE |BPF_X : + true_cond =COND_LE ; + goto cond_branch;case BPF_JMP |BPF_JEQ |BPF_K :case BPF_JMP |BPF_JEQ |BPF_X : true_cond =COND_EQ ;
@@ -817,14 +829,18 @@ static int bpf_jit_build_body(struct bpf_prog *fp, u32 *image, cond_branch:switch (code) {case BPF_JMP |BPF_JGT |BPF_X : +case BPF_JMP |BPF_JLT |BPF_X :case BPF_JMP |BPF_JGE |BPF_X : +case BPF_JMP |BPF_JLE |BPF_X :case BPF_JMP |BPF_JEQ |BPF_X :case BPF_JMP |BPF_JNE |BPF_X :/* unsigned comparison */ PPC_CMPLD (dst_reg, src_reg);break ;case BPF_JMP |BPF_JSGT |BPF_X : +case BPF_JMP |BPF_JSLT |BPF_X :case BPF_JMP |BPF_JSGE |BPF_X : +case BPF_JMP |BPF_JSLE |BPF_X :/* signed comparison */ PPC_CMPD (dst_reg, src_reg);break ;
@@ -834,7 +850,9 @@ static int bpf_jit_build_body(struct bpf_prog *fp, u32 *image,case BPF_JMP |BPF_JNE |BPF_K :case BPF_JMP |BPF_JEQ |BPF_K :case BPF_JMP |BPF_JGT |BPF_K : +case BPF_JMP |BPF_JLT |BPF_K :case BPF_JMP |BPF_JGE |BPF_K : +case BPF_JMP |BPF_JLE |BPF_K :/* * Need sign-extended load, so only positive * values can be used as imm in cmpldi
@@ -849,7 +867,9 @@ static int bpf_jit_build_body(struct bpf_prog *fp, u32 *image, }break ;case BPF_JMP |BPF_JSGT |BPF_K : +case BPF_JMP |BPF_JSLT |BPF_K :case BPF_JMP |BPF_JSGE |BPF_K : +case BPF_JMP |BPF_JSLE |BPF_K :/* * signed comparison, so any 16-bit value * can be used in cmpdi
Signature · 1 line
1.9.3
Daniel Borkmann
maintainerPATCH 7/9 bpf, nfp: implement jiting of BPF_J{LT,LE}
In reply to Daniel BorkmannThis work implements jiting of BPF_J{LT,LE} instructions with BPF_X/BPF_K variants for the nfp eBPF JIT. The two BPF_J{SLT,SLE} instructions have not been added yet given BPF_J{SGT,SGE} are not supported yet either.
--- drivers/net/ethernet/netronome/nfp/bpf/jit.c | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+)
drivers/net/ethernet/netronome/nfp/bpf/jit.c +24 -0
@@ -1238,6 +1238,16 @@ static int jge_imm(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)return wrp_cmp_imm (nfp_prog, meta,BR_BHS , true); } +static int jlt_imm (struct nfp_prog *nfp_prog,struct nfp_insn_meta *meta) +{ +return wrp_cmp_imm (nfp_prog, meta,BR_BHS , false); +} + +static int jle_imm (struct nfp_prog *nfp_prog,struct nfp_insn_meta *meta) +{ +return wrp_cmp_imm (nfp_prog, meta,BR_BLO , true); +} +static int jset_imm (struct nfp_prog *nfp_prog,struct nfp_insn_meta *meta) {const struct bpf_insn *insn = &meta->insn;
@@ -1325,6 +1335,16 @@ static int jge_reg(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta)return wrp_cmp_reg (nfp_prog, meta,BR_BHS , true); } +static int jlt_reg (struct nfp_prog *nfp_prog,struct nfp_insn_meta *meta) +{ +return wrp_cmp_reg (nfp_prog, meta,BR_BHS , false); +} + +static int jle_reg (struct nfp_prog *nfp_prog,struct nfp_insn_meta *meta) +{ +return wrp_cmp_reg (nfp_prog, meta,BR_BLO , true); +} +static int jset_reg (struct nfp_prog *nfp_prog,struct nfp_insn_meta *meta) {return wrp_test_reg (nfp_prog, meta,ALU_OP_AND ,BR_BNE );
@@ -1383,11 +1403,15 @@ static int goto_out(struct nfp_prog *nfp_prog, struct nfp_insn_meta *meta) [BPF_JMP | BPF_JEQ | BPF_K] = jeq_imm, [BPF_JMP | BPF_JGT | BPF_K] = jgt_imm, [BPF_JMP | BPF_JGE | BPF_K] = jge_imm, + [BPF_JMP | BPF_JLT | BPF_K] = jlt_imm, + [BPF_JMP | BPF_JLE | BPF_K] = jle_imm, [BPF_JMP | BPF_JSET | BPF_K] = jset_imm, [BPF_JMP | BPF_JNE | BPF_K] = jne_imm, [BPF_JMP | BPF_JEQ | BPF_X] = jeq_reg, [BPF_JMP | BPF_JGT | BPF_X] = jgt_reg, [BPF_JMP | BPF_JGE | BPF_X] = jge_reg, + [BPF_JMP | BPF_JLT | BPF_X] = jlt_reg, + [BPF_JMP | BPF_JLE | BPF_X] = jle_reg, [BPF_JMP | BPF_JSET | BPF_X] = jset_reg, [BPF_JMP | BPF_JNE | BPF_X] = jne_reg, [BPF_JMP | BPF_EXIT] = goto_out,
Signature · 1 line
1.9.3
Daniel Borkmann
maintainercover Add BPF_J{LT,LE,SLT,SLE} instructions
This set adds BPF_J{LT,LE,SLT,SLE} instructions to the BPF insn set, interpreter, JIT hardening code and all JITs are also updated to support the new instructions. Basic idea is to reduce register pressure by avoiding BPF_J{GT,GE,SGT,SGE} rewrites. Removing the workaround for the rewrites in LLVM, this can result in shorter BPF programs, less stack usage and less verification complexity. First patch provides some more details on rationale. The LLVM patch [1] will be integrated to LLVM upstream later in a backwards compatible manner.
Thanks a lot!
[1] https://github.com/borkmann/llvm/tree/bpf-insns
Daniel Borkmann (9):
bpf: add BPF_J{LT,LE,SLT,SLE} instructions
bpf, x86: implement jiting of BPF_J{LT,LE,SLT,SLE} bpf, arm64: implement jiting of BPF_J{LT,LE,SLT,SLE} bpf, sparc64: implement jiting of BPF_J{LT,LE,SLT,SLE} bpf, s390x: implement jiting of BPF_J{LT,LE,SLT,SLE} bpf, ppc64: implement jiting of BPF_J{LT,LE,SLT,SLE} bpf, nfp: implement jiting of BPF_J{LT,LE}
bpf: enable BPF_J{LT,LE,SLT,SLE} opcodes in verifier
bpf: add test cases for new BPF_J{LT,LE,SLT,SLE} instructions
Documentation/networking/filter.txt | 4 + arch/arm64/net/bpf_jit.h | 4 + arch/arm64/net/bpf_jit_comp.c | 20 ++ arch/powerpc/net/bpf_jit.h | 1 + arch/powerpc/net/bpf_jit_comp64.c | 20 ++ arch/s390/net/bpf_jit_comp.c | 24 ++ arch/sparc/net/bpf_jit_comp_64.c | 34 +++ arch/x86/net/bpf_jit_comp.c | 26 ++ drivers/net/ethernet/netronome/nfp/bpf/jit.c | 24 ++ include/uapi/linux/bpf.h | 5 + kernel/bpf/core.c | 60 +++++ kernel/bpf/verifier.c | 62 ++++- lib/test_bpf.c | 364 +++++++++++++++++++++++++++ net/core/filter.c | 21 +- tools/include/uapi/linux/bpf.h | 5 + tools/testing/selftests/bpf/test_verifier.c | 313 +++++++++++++++++++++++ 16 files changed, 979 insertions(+), 8 deletions(-)
Signature · 1 line
1.9.3
Daniel Borkmann
maintainerPATCH 8/9 bpf: enable BPF_J{LT,LE,SLT,SLE} opcodes in verifier
Enable the newly added jump opcodes, main parts are in two different areas, namely direct packet access and dynamic map value access. For the direct packet access, we now allow for the following two new patterns to match in order to trigger markings with find_good_pkt_pointers():
Variant 1 (access ok when taking the branch):
0: (61) r2 = *(u32 *)(r1 +76)
1: (61) r3 = *(u32 *)(r1 +80)
2: (bf) r0 = r2
3: (07) r0 += 8
4: (ad) if r0 < r3 goto pc+2 R0=pkt(id=0,off=8,r=0) R1=ctx R2=pkt(id=0,off=0,r=0) R3=pkt_end R10=fp
5: (b7) r0 = 0
6: (95) exit
from 4 to 7: R0=pkt(id=0,off=8,r=8) R1=ctx
R2=pkt(id=0,off=0,r=8) R3=pkt_end R10=fp
7: (71) r0 = *(u8 *)(r2 +0)
8: (05) goto pc-4
5: (b7) r0 = 0
6: (95) exit
processed 11 insns, stack depth 0
Variant 2 (access ok on fall-through):
0: (61) r2 = *(u32 *)(r1 +76)
1: (61) r3 = *(u32 *)(r1 +80)
2: (bf) r0 = r2
3: (07) r0 += 8
4: (bd) if r3 <= r0 goto pc+1 R0=pkt(id=0,off=8,r=8) R1=ctx R2=pkt(id=0,off=0,r=8) R3=pkt_end R10=fp
5: (71) r0 = *(u8 *)(r2 +0)
6: (b7) r0 = 1
7: (95) exit
from 4 to 6: R0=pkt(id=0,off=8,r=0) R1=ctx
R2=pkt(id=0,off=0,r=0) R3=pkt_end R10=fp
6: (b7) r0 = 1
7: (95) exit
processed 10 insns, stack depth 0
The above two basically just swap the branches where we need to handle an exception and allow packet access compared to the two already existing variants for find_good_pkt_pointers().
For the dynamic map value access, we add the new instructions to reg_set_min_max() and reg_set_min_max_inv() in order to learn bounds. Verifier test cases for both are added in a follow-up patch.
--- kernel/bpf/verifier.c | 62 +++++++++++++++++++++++++++++++++++++++++++++++---- 1 file changed, 58 insertions(+), 4 deletions(-)
kernel/bpf/verifier.c +58 -4
@@ -312,11 +312,15 @@ static void print_verifier_state(struct bpf_verifier_state *state) [BPF_JA >> 4] = "jmp", [BPF_JEQ >> 4] = "==", [BPF_JGT >> 4] = ">", + [BPF_JLT >> 4] = "<", [BPF_JGE >> 4] = ">=", + [BPF_JLE >> 4] = "<=", [BPF_JSET >> 4] = "&", [BPF_JNE >> 4] = "!=", [BPF_JSGT >> 4] = "s>", + [BPF_JSLT >> 4] = "s<", [BPF_JSGE >> 4] = "s>=", + [BPF_JSLE >> 4] = "s<=", [BPF_CALL >> 4] = "call", [BPF_EXIT >> 4] = "exit", };
@@ -2383,27 +2387,37 @@ static void find_good_pkt_pointers(struct bpf_verifier_state *state,*/ return ; -/* LLVM can generate two kind of checks: +/* LLVM can generate four kind of checks: * -* Type 1: +* Type 1/2: * * r2 = r3; * r2 += 8; * if (r2 > pkt_end) goto <handle exception> * <access okay> * +* r2 = r3; +* r2 += 8; +* if (r2 < pkt_end) goto <access okay> +* <handle exception> +* * Where: * r2 == dst_reg, pkt_end == src_reg * r2=pkt(id=n,off=8,r=0) * r3=pkt(id=n,off=0,r=0) * -* Type 2: +* Type 3/4: * * r2 = r3; * r2 += 8; * if (pkt_end >= r2) goto <access okay> * <handle exception> * +* r2 = r3; +* r2 += 8; +* if (pkt_end <= r2) goto <handle exception> +* <access okay> +* * Where: * pkt_end == dst_reg, r2 == src_reg * r2=pkt(id=n,off=8,r=0)
@@ -2471,6 +2485,14 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg, false_reg->smax_value =min_t (s64, false_reg->smax_value, val); true_reg->smin_value =max_t (s64, true_reg->smin_value, val +1 );break ; +case BPF_JLT : + false_reg->umin_value =max (false_reg->umin_value, val); + true_reg->umax_value =min (true_reg->umax_value, val -1 ); +break ; +case BPF_JSLT : + false_reg->smin_value =max_t (s64, false_reg->smin_value, val); + true_reg->smax_value =min_t (s64, true_reg->smax_value, val -1 ); +break ;case BPF_JGE : false_reg->umax_value =min (false_reg->umax_value, val -1 ); true_reg->umin_value =max (true_reg->umin_value, val);
@@ -2479,6 +2501,14 @@ static void reg_set_min_max(struct bpf_reg_state *true_reg, false_reg->smax_value =min_t (s64, false_reg->smax_value, val -1 ); true_reg->smin_value =max_t (s64, true_reg->smin_value, val);break ; +case BPF_JLE : + false_reg->umin_value =max (false_reg->umin_value, val +1 ); + true_reg->umax_value =min (true_reg->umax_value, val); +break ; +case BPF_JSLE : + false_reg->smin_value =max_t (s64, false_reg->smin_value, val +1 ); + true_reg->smax_value =min_t (s64, true_reg->smax_value, val); +break ;default :break ; }
@@ -2527,6 +2557,14 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg, true_reg->smax_value =min_t (s64, true_reg->smax_value, val -1 ); false_reg->smin_value =max_t (s64, false_reg->smin_value, val);break ; +case BPF_JLT : + true_reg->umin_value =max (true_reg->umin_value, val +1 ); + false_reg->umax_value =min (false_reg->umax_value, val); +break ; +case BPF_JSLT : + true_reg->smin_value =max_t (s64, true_reg->smin_value, val +1 ); + false_reg->smax_value =min_t (s64, false_reg->smax_value, val); +break ;case BPF_JGE : true_reg->umax_value =min (true_reg->umax_value, val); false_reg->umin_value =max (false_reg->umin_value, val +1 );
@@ -2535,6 +2573,14 @@ static void reg_set_min_max_inv(struct bpf_reg_state *true_reg, true_reg->smax_value =min_t (s64, true_reg->smax_value, val); false_reg->smin_value =max_t (s64, false_reg->smin_value, val +1 );break ; +case BPF_JLE : + true_reg->umin_value =max (true_reg->umin_value, val); + false_reg->umax_value =min (false_reg->umax_value, val -1 ); +break ; +case BPF_JSLE : + true_reg->smin_value =max_t (s64, true_reg->smin_value, val); + false_reg->smax_value =min_t (s64, false_reg->smax_value, val -1 ); +break ;default :break ; }
@@ -2659,7 +2705,7 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env,u8 opcode =BPF_OP (insn->code);int err; -if (opcode >BPF_EXIT ) { +if (opcode >BPF_JSLE ) {verbose ("invalid BPF_JMP opcode %x\n" , opcode);return -EINVAL ; }
@@ -2761,10 +2807,18 @@ static int check_cond_jmp_op(struct bpf_verifier_env *env, dst_reg->type == PTR_TO_PACKET && regs[insn->src_reg].type == PTR_TO_PACKET_END) {find_good_pkt_pointers (this_branch, dst_reg); + } else if (BPF_SRC(insn->code) == BPF_X && opcode == BPF_JLT && + dst_reg->type == PTR_TO_PACKET && + regs[insn->src_reg].type == PTR_TO_PACKET_END) { +find_good_pkt_pointers (other_branch, dst_reg); } else if (BPF_SRC(insn->code) == BPF_X && opcode == BPF_JGE && dst_reg->type == PTR_TO_PACKET_END && regs[insn->src_reg].type == PTR_TO_PACKET) {find_good_pkt_pointers (other_branch, ®s[insn->src_reg]); + } else if (BPF_SRC(insn->code) == BPF_X && opcode == BPF_JLE && + dst_reg->type == PTR_TO_PACKET_END && + regs[insn->src_reg].type == PTR_TO_PACKET) { +find_good_pkt_pointers (this_branch, ®s[insn->src_reg]); } else if (is_pointer_value(env, insn->dst_reg)) {verbose ("R%d pointer comparison prohibited\n" , insn->dst_reg);return -EACCES ;
Signature · 1 line
1.9.3
Daniel Borkmann
maintainerPATCH 9/9 bpf: add test cases for new BPF_J{LT,LE,SLT,SLE} instructions
In reply to Daniel BorkmannAdd test cases to the verifier selftest suite in order to verify that
i) direct packet access, and ii) dynamic map value access is working with the changes related to the new instructions.
--- tools/testing/selftests/bpf/test_verifier.c | 313 ++++++++++++++++++++++++++++ 1 file changed, 313 insertions(+)
tools/testing/selftests/bpf/test_verifier.c +313 -0
@@ -2830,6 +2830,79 @@ struct test_val { .result = ACCEPT, }, { + "direct packet access: test25 (marking on <, good access)", + .insns = { +BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_1 , + offsetof(struct __sk_buff , data)), +BPF_LDX_MEM (BPF_W ,BPF_REG_3 ,BPF_REG_1 , + offsetof(struct __sk_buff , data_end)), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_2 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_0 ,8 ), +BPF_JMP_REG (BPF_JLT ,BPF_REG_0 ,BPF_REG_3 ,2 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_EXIT_INSN (), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_2 ,0 ), + BPF_JMP_IMM(BPF_JA, 0, 0, -4), + }, + .result =ACCEPT , + .prog_type = BPF_PROG_TYPE_SCHED_CLS, + }, + { +"direct packet access: test26 (marking on <, bad access)" , + .insns = { +BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_1 , + offsetof(struct __sk_buff , data)), +BPF_LDX_MEM (BPF_W ,BPF_REG_3 ,BPF_REG_1 , + offsetof(struct __sk_buff , data_end)), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_2 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_0 ,8 ), +BPF_JMP_REG (BPF_JLT ,BPF_REG_0 ,BPF_REG_3 ,3 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_2 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_EXIT_INSN (), + BPF_JMP_IMM(BPF_JA, 0, 0, -3), + }, + .result =REJECT , + .errstr = "invalid access to packet", + .prog_type = BPF_PROG_TYPE_SCHED_CLS, + }, + { +"direct packet access: test27 (marking on <=, good access)" , + .insns = { +BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_1 , + offsetof(struct __sk_buff , data)), +BPF_LDX_MEM (BPF_W ,BPF_REG_3 ,BPF_REG_1 , + offsetof(struct __sk_buff , data_end)), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_2 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_0 ,8 ), +BPF_JMP_REG (BPF_JLE ,BPF_REG_3 ,BPF_REG_0 ,1 ), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_2 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), + BPF_EXIT_INSN(), + }, + .result =ACCEPT , + .prog_type = BPF_PROG_TYPE_SCHED_CLS, + }, + { +"direct packet access: test28 (marking on <=, bad access)" , + .insns = { +BPF_LDX_MEM (BPF_W ,BPF_REG_2 ,BPF_REG_1 , + offsetof(struct __sk_buff , data)), +BPF_LDX_MEM (BPF_W ,BPF_REG_3 ,BPF_REG_1 , + offsetof(struct __sk_buff , data_end)), +BPF_MOV64_REG (BPF_REG_0 ,BPF_REG_2 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_0 ,8 ), +BPF_JMP_REG (BPF_JLE ,BPF_REG_3 ,BPF_REG_0 ,2 ), +BPF_MOV64_IMM (BPF_REG_0 ,1 ), +BPF_EXIT_INSN (), +BPF_LDX_MEM (BPF_B ,BPF_REG_0 ,BPF_REG_2 ,0 ), + BPF_JMP_IMM(BPF_JA, 0, 0, -4), + }, + .result =REJECT , + .errstr = "invalid access to packet", + .prog_type = BPF_PROG_TYPE_SCHED_CLS, + }, + {"helper access to packet: test1, valid packet_ptr range" , .insns = { BPF_LDX_MEM(BPF_W, BPF_REG_2, BPF_REG_1,
@@ -4488,6 +4561,246 @@ struct test_val { .prog_type = BPF_PROG_TYPE_TRACEPOINT, }, { + "helper access to map: bounds check using <, good access", + .insns = { +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_ST_MEM (BPF_DW ,BPF_REG_2 ,0 ,0 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_EMIT_CALL (BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_3 ,BPF_REG_0 ,0 ), +BPF_JMP_IMM (BPF_JLT ,BPF_REG_3 ,32 ,2 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_EXIT_INSN (), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_3 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map2 = { 3 }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + }, + { +"helper access to map: bounds check using <, bad access" , + .insns = { +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_ST_MEM (BPF_DW ,BPF_REG_2 ,0 ,0 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_EMIT_CALL (BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_3 ,BPF_REG_0 ,0 ), +BPF_JMP_IMM (BPF_JLT ,BPF_REG_3 ,32 ,4 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_3 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_EXIT_INSN (), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map2 = { 3 }, + .result = REJECT, + .errstr = "R1 unbounded memory access", + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + }, + { +"helper access to map: bounds check using <=, good access" , + .insns = { +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_ST_MEM (BPF_DW ,BPF_REG_2 ,0 ,0 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_EMIT_CALL (BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_3 ,BPF_REG_0 ,0 ), +BPF_JMP_IMM (BPF_JLE ,BPF_REG_3 ,32 ,2 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_EXIT_INSN (), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_3 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map2 = { 3 }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + }, + { +"helper access to map: bounds check using <=, bad access" , + .insns = { +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_ST_MEM (BPF_DW ,BPF_REG_2 ,0 ,0 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_EMIT_CALL (BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_3 ,BPF_REG_0 ,0 ), +BPF_JMP_IMM (BPF_JLE ,BPF_REG_3 ,32 ,4 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_3 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_EXIT_INSN (), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map2 = { 3 }, + .result = REJECT, + .errstr = "R1 unbounded memory access", + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + }, + { +"helper access to map: bounds check using s<, good access" , + .insns = { +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_ST_MEM (BPF_DW ,BPF_REG_2 ,0 ,0 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_EMIT_CALL (BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_3 ,BPF_REG_0 ,0 ), +BPF_JMP_IMM (BPF_JSLT ,BPF_REG_3 ,32 ,2 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_EXIT_INSN (), +BPF_JMP_IMM (BPF_JSLT ,BPF_REG_3 ,0 ,-3 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_3 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map2 = { 3 }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + }, + { +"helper access to map: bounds check using s<, good access 2" , + .insns = { +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_ST_MEM (BPF_DW ,BPF_REG_2 ,0 ,0 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_EMIT_CALL (BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_3 ,BPF_REG_0 ,0 ), +BPF_JMP_IMM (BPF_JSLT ,BPF_REG_3 ,32 ,2 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_EXIT_INSN (), +BPF_JMP_IMM (BPF_JSLT ,BPF_REG_3 ,-3 ,-3 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_3 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map2 = { 3 }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + }, + { +"helper access to map: bounds check using s<, bad access" , + .insns = { +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_ST_MEM (BPF_DW ,BPF_REG_2 ,0 ,0 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_EMIT_CALL (BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_DW ,BPF_REG_3 ,BPF_REG_0 ,0 ), +BPF_JMP_IMM (BPF_JSLT ,BPF_REG_3 ,32 ,2 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_EXIT_INSN (), +BPF_JMP_IMM (BPF_JSLT ,BPF_REG_3 ,-3 ,-3 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_3 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map2 = { 3 }, + .result = REJECT, + .errstr = "R1 min value is negative", + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + }, + { +"helper access to map: bounds check using s<=, good access" , + .insns = { +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_ST_MEM (BPF_DW ,BPF_REG_2 ,0 ,0 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_EMIT_CALL (BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_3 ,BPF_REG_0 ,0 ), +BPF_JMP_IMM (BPF_JSLE ,BPF_REG_3 ,32 ,2 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_EXIT_INSN (), +BPF_JMP_IMM (BPF_JSLE ,BPF_REG_3 ,0 ,-3 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_3 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map2 = { 3 }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + }, + { +"helper access to map: bounds check using s<=, good access 2" , + .insns = { +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_ST_MEM (BPF_DW ,BPF_REG_2 ,0 ,0 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_EMIT_CALL (BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_W ,BPF_REG_3 ,BPF_REG_0 ,0 ), +BPF_JMP_IMM (BPF_JSLE ,BPF_REG_3 ,32 ,2 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_EXIT_INSN (), +BPF_JMP_IMM (BPF_JSLE ,BPF_REG_3 ,-3 ,-3 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_3 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map2 = { 3 }, + .result = ACCEPT, + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + }, + { +"helper access to map: bounds check using s<=, bad access" , + .insns = { +BPF_MOV64_REG (BPF_REG_2 ,BPF_REG_10 ), +BPF_ALU64_IMM (BPF_ADD ,BPF_REG_2 ,-8 ), +BPF_ST_MEM (BPF_DW ,BPF_REG_2 ,0 ,0 ), +BPF_LD_MAP_FD (BPF_REG_1 ,0 ), +BPF_EMIT_CALL (BPF_FUNC_map_lookup_elem), +BPF_JMP_IMM (BPF_JEQ ,BPF_REG_0 ,0 ,4 ), +BPF_MOV64_REG (BPF_REG_1 ,BPF_REG_0 ), +BPF_LDX_MEM (BPF_DW ,BPF_REG_3 ,BPF_REG_0 ,0 ), +BPF_JMP_IMM (BPF_JSLE ,BPF_REG_3 ,32 ,2 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), +BPF_EXIT_INSN (), +BPF_JMP_IMM (BPF_JSLE ,BPF_REG_3 ,-3 ,-3 ), +BPF_ALU64_REG (BPF_ADD ,BPF_REG_1 ,BPF_REG_3 ), +BPF_ST_MEM (BPF_B ,BPF_REG_1 ,0 ,0 ), +BPF_MOV64_IMM (BPF_REG_0 ,0 ), + BPF_EXIT_INSN(), + }, + .fixup_map2 = { 3 }, + .result = REJECT, + .errstr = "R1 min value is negative", + .prog_type = BPF_PROG_TYPE_TRACEPOINT, + }, + {"map element value is preserved across register spilling" , .insns = { BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
Signature · 1 line
1.9.3
David Miller
maintainerRe: [PATCH net-next 1/9] bpf: add BPF_J{LT,LE,SLT,SLE} instructions
In reply to Daniel BorkmannFrom: Daniel Borkmann <[email protected]>
Date: Wed, 9 Aug 2017 12:23:53 +0200
Quoted 1 line
How is this "backwards compatible"?
If someone takes a new LLVM and tries to load those programs into an older kernel they will be rejected.
There appears to be no effort to make things work cleanly in that situation at all.
Daniel Borkmann
maintainerRe: [PATCH net-next 1/9] bpf: add BPF_J{LT,LE,SLT,SLE} instructions
Quoted 5 lines · David Miller
From: Daniel Borkmann <[email protected]>
Date: Wed, 9 Aug 2017 12:23:53 +0200Quoted 1 line
Quoted 7 lines
How is this "backwards compatible"?
If someone takes a new LLVM and tries to load those programs into an older kernel they will be rejected.
There appears to be no effort to make things work cleanly in that situation at all.
No, that was just the patch I used for LLVM to enable the insns, so not the final one that will be submitted there officially where we have a switch to enable/disable this functionality.
Daniel Borkmann
maintainerRe: [PATCH net-next 1/9] bpf: add BPF_J{LT,LE,SLT,SLE} instructions
Quoted 11 lines · Daniel Borkmann
Quoted 10 lines · David Miller
From: Daniel Borkmann <[email protected]>
Date: Wed, 9 Aug 2017 12:23:53 +0200Quoted 1 line
How is this "backwards compatible"?
If someone takes a new LLVM and tries to load those programs into an older kernel they will be rejected.
Quoted 7 lines
Quoted 2 lines
There appears to be no effort to make things work cleanly in that situation at all.
No, that was just the patch I used for LLVM to enable the insns, so not the final one that will be submitted there officially where we have a switch to enable/disable this functionality.
(In other words the one I used for doing the measurements.)
David Miller
maintainerRe: [PATCH net-next 1/9] bpf: add BPF_J{LT,LE,SLT,SLE} instructions
In reply to Daniel BorkmannFrom: Daniel Borkmann <[email protected]>
Date: Wed, 09 Aug 2017 19:00:58 +0200
Quoted 11 lines · David Miller
Quoted 10 lines
From: Daniel Borkmann <[email protected]>
Date: Wed, 9 Aug 2017 12:23:53 +0200Quoted 1 line
How is this "backwards compatible"?
If someone takes a new LLVM and tries to load those programs into an older kernel they will be rejected.
Quoted 7 lines
Quoted 2 lines
There appears to be no effort to make things work cleanly in that situation at all.
No, that was just the patch I used for LLVM to enable the insns, so not the final one that will be submitted there officially where we have a switch to enable/disable this functionality.
So how does this switch work and how are people expected to use this switch? What is the default value and is it ever expected to change in the future?
Yeah this seems hella awesome to get cilium programs smaller and faster in a restricted environment where you control the running kernel and everything.
But from a review perspective one should be completely uninterested in that.
So, generally speaking how does this all pan out? I seriously doubt the wisdom of this. You'll have to convince me of the long term viability and whether we ever get to the point where everyone can benefit from this. :)
Daniel Borkmann
maintainerRe: [PATCH net-next 1/9] bpf: add BPF_J{LT,LE,SLT,SLE} instructions
Quoted 22 lines · David Miller
From: Daniel Borkmann <[email protected]>
Date: Wed, 09 Aug 2017 19:00:58 +0200Quoted 11 lines · David Miller
Quoted 10 lines
From: Daniel Borkmann <[email protected]>
Date: Wed, 9 Aug 2017 12:23:53 +0200Quoted 1 line
How is this "backwards compatible"?
If someone takes a new LLVM and tries to load those programs into an older kernel they will be rejected.
Quoted 7 lines
Quoted 2 lines
There appears to be no effort to make things work cleanly in that situation at all.
No, that was just the patch I used for LLVM to enable the insns, so not the final one that will be submitted there officially where we have a switch to enable/disable this functionality.
Quoted 7 lines
So how does this switch work and how are people expected to use this switch? What is the default value and is it ever expected to change in the future?
Yeah this seems hella awesome to get cilium programs smaller and faster in a restricted environment where you control the running kernel and everything.
For the case of cilium, we are not in control of the kernel, by the way, we run a few probes that are small BPF insns snippets that test the kernel for presence of certain features (e.g. helper, verifier, maps) and enable/disable them accordingly later in the code generation. On the user space side, we're indeed a bit more flexible and have no such restriction.
Plan is for LLVM as one of the frontends that generate byte code (ply, for example, can probe the kernel directly for its code generation) to have i) a target specific option to offer a possibility to explicitly enable the extension by the user (as we have with -m target specific extensions today for various cpu insns), and ii) have the kernel check for presence of the extensions and enable it transparently when the user selects more aggressive options such as -march=native in a bpf target context, so we can select the underlying features transparently. I should have made that more clear earlier, sorry about that.
Thanks,
Daniel
David Miller
maintainerRe: [PATCH net-next 1/9] bpf: add BPF_J{LT,LE,SLT,SLE} instructions
From: Daniel Borkmann <[email protected]>
Date: Wed, 09 Aug 2017 22:32:34 +0200
Quoted 7 lines
For the case of cilium, we are not in control of the kernel, by the way, we run a few probes that are small BPF insns snippets that test the kernel for presence of certain features (e.g. helper, verifier, maps) and enable/disable them accordingly later in the code generation. On the user space side, we're indeed a bit more flexible and have no such restriction.
Quoted 10 lines
Plan is for LLVM as one of the frontends that generate byte code (ply, for example, can probe the kernel directly for its code generation) to have i) a target specific option to offer a possibility to explicitly enable the extension by the user (as we have with -m target specific extensions today for various cpu insns), and ii) have the kernel check for presence of the extensions and enable it transparently when the user selects more aggressive options such as -march=native in a bpf target context, so we can select the underlying features transparently. I should have made that more clear earlier, sorry about that.
I think this explanation needs to be in either your header posting or the commit message of patch #1.
Thanks :)
Daniel Borkmann
maintainerRe: [PATCH net-next 1/9] bpf: add BPF_J{LT,LE,SLT,SLE} instructions
Quoted 21 lines · David Miller
From: Daniel Borkmann <[email protected]>
Date: Wed, 09 Aug 2017 22:32:34 +0200Quoted 7 lines
For the case of cilium, we are not in control of the kernel, by the way, we run a few probes that are small BPF insns snippets that test the kernel for presence of certain features (e.g. helper, verifier, maps) and enable/disable them accordingly later in the code generation. On the user space side, we're indeed a bit more flexible and have no such restriction.
Quoted 10 lines
Plan is for LLVM as one of the frontends that generate byte code (ply, for example, can probe the kernel directly for its code generation) to have i) a target specific option to offer a possibility to explicitly enable the extension by the user (as we have with -m target specific extensions today for various cpu insns), and ii) have the kernel check for presence of the extensions and enable it transparently when the user selects more aggressive options such as -march=native in a bpf target context, so we can select the underlying features transparently. I should have made that more clear earlier, sorry about that.
Quoted 4 lines
I think this explanation needs to be in either your header posting or the commit message of patch #1.
Thanks :)
Ok, sure, I'll do a v2 with that included. Thanks!