Skip to contentSkip to conversation

BPF syscall

RFC PATCH Superseded Alexei Starovoitov 6 participants 39 messages Aug 27, 2014

Subsystems (16)

v7 of 15 Superseded Latest is v15 →

lore
Share & tools
lore
#0 lore raw

v7 cover BPF syscall

Hi Ingo, David,

posting whole thing again as RFC to get feedback on syscall only. If syscall bpf(int cmd, union bpf_attr *attr, unsigned int size) is ok, I'll split them into small chunks as requested and will repost without RFC.

Right now please only review syscall API
patch 0003 introduces sys_bpf and first BPF_MAP_CREATE command patch 0005 adds four more commands to the same syscall patch 0007 adds BPF_PROG_LOAD command
patch 0010 extends BPF_PROG_LOAD command with 3 more attributes patch 0021 adds user space wrapper for BPF syscall patch 0023 uses these wrappers in verifier testsuite

Note that additions of commands and attributes kept this syscall backwards compatible from one patch to another.
I've decided not to bother with forward compatiblity for now. We can address it later the way perf_event_open did.

Please ignore other patches, since I cannot easily remove them without breaking compilation

btw, tested on x64/i386 and comiled tested on arm with NET-less config.

V6->V7:
- only BPF syscall interface changed from long+nlattr+a_lot_of_type_casts to single 'union bpf_attr'.
It pretty much removed all type casts in kernel and in user space that were there because of 'long' and because of 'nlattr'

Thanks for feedback. I think this version is definitely cleaner. As a side note I've addressed Cong's comment regarding commit log. Now it documents syscall itself instead of wrappers of syscall.

If anyone prefers to see patches in the browser, they are here:
https://git.kernel.org/cgit/linux/kernel/git/ast/bpf.git/log/?h=v7

Thanks!

Alexei Starovoitov (28):
net: filter: add "load 64-bit immediate" eBPF instruction
net: filter: split filter.h and expose eBPF to user space
bpf: introduce syscall(BPF, ...) and BPF maps
bpf: enable bpf syscall on x64 and i386
bpf: add lookup/update/delete/iterate methods to BPF maps
bpf: add hashtable type of BPF maps
bpf: expand BPF syscall with program load/unload
bpf: handle pseudo BPF_CALL insn
bpf: verifier (add docs)
bpf: verifier (add ability to receive verification log)
bpf: handle pseudo BPF_LD_IMM64 insn
bpf: verifier (add branch/goto checks)
bpf: verifier (add verifier core)
bpf: verifier (add state prunning optimization)
bpf: allow eBPF programs to use maps
bpf: split eBPF out of NET
tracing: allow eBPF programs to be attached to events
tracing: allow eBPF programs call printk()
tracing: allow eBPF programs to be attached to kprobe/kretprobe
tracing: allow eBPF programs to call ktime_get_ns() and get_current()
samples: bpf: add mini eBPF library to manipulate maps and programs
samples: bpf: example of tracing filters with eBPF
bpf: verifier test
bpf: llvm backend
samples: bpf: elf file loader
samples: bpf: eBPF example in C
samples: bpf: counting eBPF example in C
samples: bpf: IO latency analysis (iosnoop/heatmap)

 Documentation/networking/filter.txt                |  313 +++-
 arch/Kconfig                                       |    3 +
 arch/x86/net/bpf_jit_comp.c                        |   17 +
 arch/x86/syscalls/syscall_32.tbl                   |    1 +
 arch/x86/syscalls/syscall_64.tbl                   |    1 +
 fs/btrfs/super.c                                   |    3 +
 include/linux/bpf.h                                |  139 ++
 include/linux/filter.h                             |  303 +---
 include/linux/ftrace_event.h                       |    5 +
 include/linux/syscalls.h                           |    3 +-
 include/trace/bpf_trace.h                          |   23 +
 include/trace/ftrace.h                             |   25 +
 include/uapi/asm-generic/unistd.h                  |    4 +-
 include/uapi/linux/Kbuild                          |    1 +
 include/uapi/linux/bpf.h                           |  439 +++++
 kernel/Makefile                                    |    2 +-
 kernel/bpf/Makefile                                |    2 +-
 kernel/bpf/core.c                                  |   17 +
 kernel/bpf/hashtab.c                               |  365 ++++
 kernel/bpf/syscall.c                               |  645 +++++++
 kernel/bpf/verifier.c                              | 1910 ++++++++++++++++++++
 kernel/sys_ni.c                                    |    3 +
 kernel/trace/Kconfig                               |    1 +
 kernel/trace/Makefile                              |    1 +
 kernel/trace/bpf_trace.c                           |  264 +++
 kernel/trace/trace.h                               |    3 +
 kernel/trace/trace_events.c                        |   41 +-
 kernel/trace/trace_events_filter.c                 |   72 +-
 kernel/trace/trace_kprobe.c                        |   28 +
 kernel/trace/trace_syscalls.c                      |   32 +
 lib/test_bpf.c                                     |   21 +
 net/Kconfig                                        |    1 +
 net/core/filter.c                                  |    2 +
 samples/bpf/Makefile                               |   28 +
 samples/bpf/bpf_helpers.h                          |   27 +
 samples/bpf/bpf_load.c                             |  234 +++
 samples/bpf/bpf_load.h                             |   26 +
 samples/bpf/dropmon.c                              |  122 ++
 samples/bpf/ex1_kern.c                             |   27 +
 samples/bpf/ex1_user.c                             |   24 +
 samples/bpf/ex2_kern.c                             |   73 +
 samples/bpf/ex2_user.c                             |   94 +
 samples/bpf/ex3_kern.c                             |  104 ++
 samples/bpf/ex3_user.c                             |  149 ++
 samples/bpf/libbpf.c                               |   89 +
 samples/bpf/libbpf.h                               |   21 +
 samples/bpf/test_verifier.c                        |  599 ++++++
 tools/bpf/llvm/.gitignore                          |   54 +
 tools/bpf/llvm/LICENSE.TXT                         |   70 +
 tools/bpf/llvm/Makefile.rules                      |  641 +++++++
 tools/bpf/llvm/README.txt                          |   23 +
 tools/bpf/llvm/bld/Makefile                        |   27 +
 tools/bpf/llvm/bld/Makefile.common                 |   14 +
 tools/bpf/llvm/bld/Makefile.config                 |  124 ++
 .../llvm/bld/include/llvm/Config/AsmParsers.def    |    8 +
 .../llvm/bld/include/llvm/Config/AsmPrinters.def   |    9 +
 .../llvm/bld/include/llvm/Config/Disassemblers.def |    8 +
 tools/bpf/llvm/bld/include/llvm/Config/Targets.def |    9 +
 .../bpf/llvm/bld/include/llvm/Support/DataTypes.h  |   96 +
 tools/bpf/llvm/bld/lib/Makefile                    |   11 +
 .../llvm/bld/lib/Target/BPF/InstPrinter/Makefile   |   10 +
 .../llvm/bld/lib/Target/BPF/MCTargetDesc/Makefile  |   11 +
 tools/bpf/llvm/bld/lib/Target/BPF/Makefile         |   17 +
 .../llvm/bld/lib/Target/BPF/TargetInfo/Makefile    |   10 +
 tools/bpf/llvm/bld/lib/Target/Makefile             |   11 +
 tools/bpf/llvm/bld/tools/Makefile                  |   12 +
 tools/bpf/llvm/bld/tools/llc/Makefile              |   15 +
 tools/bpf/llvm/lib/Target/BPF/BPF.h                |   28 +
 tools/bpf/llvm/lib/Target/BPF/BPF.td               |   29 +
 tools/bpf/llvm/lib/Target/BPF/BPFAsmPrinter.cpp    |  100 +
 tools/bpf/llvm/lib/Target/BPF/BPFCallingConv.td    |   24 +
 tools/bpf/llvm/lib/Target/BPF/BPFFrameLowering.cpp |   36 +
 tools/bpf/llvm/lib/Target/BPF/BPFFrameLowering.h   |   35 +
 tools/bpf/llvm/lib/Target/BPF/BPFISelDAGToDAG.cpp  |  182 ++
 tools/bpf/llvm/lib/Target/BPF/BPFISelLowering.cpp  |  683 +++++++
 tools/bpf/llvm/lib/Target/BPF/BPFISelLowering.h    |  105 ++
 tools/bpf/llvm/lib/Target/BPF/BPFInstrFormats.td   |   29 +
 tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.cpp     |  162 ++
 tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.h       |   53 +
 tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.td      |  498 +++++
 tools/bpf/llvm/lib/Target/BPF/BPFMCInstLower.cpp   |   77 +
 tools/bpf/llvm/lib/Target/BPF/BPFMCInstLower.h     |   40 +
 tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.cpp  |  122 ++
 tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.h    |   65 +
 tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.td   |   39 +
 tools/bpf/llvm/lib/Target/BPF/BPFSubtarget.cpp     |   23 +
 tools/bpf/llvm/lib/Target/BPF/BPFSubtarget.h       |   33 +
 tools/bpf/llvm/lib/Target/BPF/BPFTargetMachine.cpp |   66 +
 tools/bpf/llvm/lib/Target/BPF/BPFTargetMachine.h   |   69 +
 .../lib/Target/BPF/InstPrinter/BPFInstPrinter.cpp  |   81 +
 .../lib/Target/BPF/InstPrinter/BPFInstPrinter.h    |   34 +
 .../lib/Target/BPF/MCTargetDesc/BPFAsmBackend.cpp  |   89 +
 .../llvm/lib/Target/BPF/MCTargetDesc/BPFBaseInfo.h |   33 +
 .../Target/BPF/MCTargetDesc/BPFELFObjectWriter.cpp |   56 +
 .../lib/Target/BPF/MCTargetDesc/BPFMCAsmInfo.h     |   34 +
 .../Target/BPF/MCTargetDesc/BPFMCCodeEmitter.cpp   |  167 ++
 .../Target/BPF/MCTargetDesc/BPFMCTargetDesc.cpp    |  115 ++
 .../lib/Target/BPF/MCTargetDesc/BPFMCTargetDesc.h  |   56 +
 .../lib/Target/BPF/TargetInfo/BPFTargetInfo.cpp    |   13 +
 tools/bpf/llvm/tools/llc/llc.cpp                   |  381 ++++
 100 files changed, 10742 insertions(+), 302 deletions(-)
 create mode 100644 include/linux/bpf.h
 create mode 100644 include/trace/bpf_trace.h
 create mode 100644 include/uapi/linux/bpf.h
 create mode 100644 kernel/bpf/hashtab.c
 create mode 100644 kernel/bpf/syscall.c
 create mode 100644 kernel/bpf/verifier.c
 create mode 100644 kernel/trace/bpf_trace.c
 create mode 100644 samples/bpf/Makefile
 create mode 100644 samples/bpf/bpf_helpers.h
 create mode 100644 samples/bpf/bpf_load.c
 create mode 100644 samples/bpf/bpf_load.h
 create mode 100644 samples/bpf/dropmon.c
 create mode 100644 samples/bpf/ex1_kern.c
 create mode 100644 samples/bpf/ex1_user.c
 create mode 100644 samples/bpf/ex2_kern.c
 create mode 100644 samples/bpf/ex2_user.c
 create mode 100644 samples/bpf/ex3_kern.c
 create mode 100644 samples/bpf/ex3_user.c
 create mode 100644 samples/bpf/libbpf.c
 create mode 100644 samples/bpf/libbpf.h
 create mode 100644 samples/bpf/test_verifier.c
 create mode 100644 tools/bpf/llvm/.gitignore
 create mode 100644 tools/bpf/llvm/LICENSE.TXT
 create mode 100644 tools/bpf/llvm/Makefile.rules
 create mode 100644 tools/bpf/llvm/README.txt
 create mode 100644 tools/bpf/llvm/bld/Makefile
 create mode 100644 tools/bpf/llvm/bld/Makefile.common
 create mode 100644 tools/bpf/llvm/bld/Makefile.config
 create mode 100644 tools/bpf/llvm/bld/include/llvm/Config/AsmParsers.def
 create mode 100644 tools/bpf/llvm/bld/include/llvm/Config/AsmPrinters.def
 create mode 100644 tools/bpf/llvm/bld/include/llvm/Config/Disassemblers.def
 create mode 100644 tools/bpf/llvm/bld/include/llvm/Config/Targets.def
 create mode 100644 tools/bpf/llvm/bld/include/llvm/Support/DataTypes.h
 create mode 100644 tools/bpf/llvm/bld/lib/Makefile
 create mode 100644 tools/bpf/llvm/bld/lib/Target/BPF/InstPrinter/Makefile
 create mode 100644 tools/bpf/llvm/bld/lib/Target/BPF/MCTargetDesc/Makefile
 create mode 100644 tools/bpf/llvm/bld/lib/Target/BPF/Makefile
 create mode 100644 tools/bpf/llvm/bld/lib/Target/BPF/TargetInfo/Makefile
 create mode 100644 tools/bpf/llvm/bld/lib/Target/Makefile
 create mode 100644 tools/bpf/llvm/bld/tools/Makefile
 create mode 100644 tools/bpf/llvm/bld/tools/llc/Makefile
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPF.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPF.td
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFAsmPrinter.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFCallingConv.td
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFFrameLowering.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFFrameLowering.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFISelDAGToDAG.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFISelLowering.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFISelLowering.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFInstrFormats.td
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.td
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFMCInstLower.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFMCInstLower.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.td
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFSubtarget.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFSubtarget.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFTargetMachine.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFTargetMachine.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/InstPrinter/BPFInstPrinter.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/InstPrinter/BPFInstPrinter.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFAsmBackend.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFBaseInfo.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFELFObjectWriter.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFMCAsmInfo.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFMCCodeEmitter.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFMCTargetDesc.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFMCTargetDesc.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/TargetInfo/BPFTargetInfo.cpp
 create mode 100644 tools/bpf/llvm/tools/llc/llc.cpp
Signature · 1 line
1.7.9.5
#1 lore raw

RFC PATCH v7 1/28 net: filter: add "load 64-bit immediate" eBPF instruction

add BPF_LD_IMM64 instruction to load 64-bit immediate value into a register. All previous instructions were 8-byte. This is first 16-byte instruction. Two consecutive 'struct bpf_insn' blocks are interpreted as single instruction:
insn[0].code = BPF_LD | BPF_DW | BPF_IMM
insn[0].dst_reg = destination register
insn[0].imm = lower 32-bit
insn[1].code = 0
insn[1].imm = upper 32-bit
All unused fields must be zero.

Classic BPF has similar instruction: BPF_LD | BPF_W | BPF_IMM which loads 32-bit immediate value into a register.

x64 JITs it as single 'movabsq %rax, imm64'
arm64 may JIT as sequence of four 'movk x0, #imm16, lsl #shift' insn

Note that old eBPF programs are binary compatible with new interpreter.

In the following patches this instruction is used to store eBPF map pointers:
BPF_LD_IMM64(R1, const_imm_map_ptr) BPF_CALL(BPF_FUNC_map_lookup_elem)
and verifier is introduced to check validity of the programs.

Later LLVM compiler is using this insn as generic load of 64-bit immediate constant and as a load of map pointer with relocation.

---
 Documentation/networking/filter.txt |    8 +++++++-
 arch/x86/net/bpf_jit_comp.c         |   17 +++++++++++++++++
 include/linux/filter.h              |   18 ++++++++++++++++++
 kernel/bpf/core.c                   |    5 +++++
 lib/test_bpf.c                      |   21 +++++++++++++++++++++
 5 files changed, 68 insertions(+), 1 deletion(-)
Documentation/networking/filter.txt +7 -1
index c48a9704bda8..81916ab5d96f 100644
@@ -951,7 +951,7 @@ Size modifier is one of ...
 
 Mode modifier is one of:
 
-  BPF_IMM  0x00  /* classic BPF only, reserved in eBPF */
+  BPF_IMM  0x00  /* used for 32-bit mov in classic BPF and 64-bit in eBPF */
   BPF_ABS  0x20
   BPF_IND  0x40
   BPF_MEM  0x60
@@ -995,6 +995,12 @@ BPF_XADD | BPF_DW | BPF_STX: lock xadd *(u64 *)(dst_reg + off16) += src_reg
 Where size is one of: BPF_B or BPF_H or BPF_W or BPF_DW. Note that 1 and
 2 byte atomic increments are not supported.
 
+eBPF has one 16-byte instruction: BPF_LD | BPF_DW | BPF_IMM which consists
+of two consecutive 'struct bpf_insn' 8-byte blocks and interpreted as single
+instruction that loads 64-bit immediate value into a dst_reg.
+Classic BPF has similar instruction: BPF_LD | BPF_W | BPF_IMM which loads
+32-bit immediate value into a register.
+
 Testing
 -------
 
arch/x86/net/bpf_jit_comp.c +17 -0
index b08a98c59530..98837147ee57 100644
@@ -393,6 +393,23 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image,
 			EMIT1_off32(add_1reg(0xB8, dst_reg), imm32);
 			break;
 
+		case BPF_LD | BPF_IMM | BPF_DW:
+			if (insn[1].code != 0 || insn[1].src_reg != 0 ||
+			    insn[1].dst_reg != 0 || insn[1].off != 0) {
+				/* verifier must catch invalid insns */
+				pr_err("invalid BPF_LD_IMM64 insn\n");
+				return -EINVAL;
+			}
+
+			/* movabsq %rax, imm64 */
+			EMIT2(add_1mod(0x48, dst_reg), add_1reg(0xB8, dst_reg));
+			EMIT(insn[0].imm, 4);
+			EMIT(insn[1].imm, 4);
+
+			insn++;
+			i++;
+			break;
+
 			/* dst %= src, dst /= src, dst %= imm32, dst /= imm32 */
 		case BPF_ALU | BPF_MOD | BPF_X:
 		case BPF_ALU | BPF_DIV | BPF_X:
include/linux/filter.h +18 -0
index a5227ab8ccb1..f3262b598262 100644
@@ -161,6 +161,24 @@ enum {
 		.off   = 0,					\
 		.imm   = IMM })
 
+/* BPF_LD_IMM64 macro encodes single 'load 64-bit immediate' insn */
+#define BPF_LD_IMM64(DST, IMM)					\
+	BPF_LD_IMM64_RAW(DST, 0, IMM)
+
+#define BPF_LD_IMM64_RAW(DST, SRC, IMM)				\
+	((struct bpf_insn) {					\
+		.code  = BPF_LD | BPF_DW | BPF_IMM,		\
+		.dst_reg = DST,					\
+		.src_reg = SRC,					\
+		.off   = 0,					\
+		.imm   = (__u32) (IMM) }),			\
+	((struct bpf_insn) {					\
+		.code  = 0, /* zero is reserved opcode */	\
+		.dst_reg = 0,					\
+		.src_reg = 0,					\
+		.off   = 0,					\
+		.imm   = ((__u64) (IMM)) >> 32 })
+
 /* Short form of mov based on type, BPF_X: dst_reg = src_reg, BPF_K: dst_reg = imm32 */
 
 #define BPF_MOV64_RAW(TYPE, DST, SRC, IMM)			\
kernel/bpf/core.c +5 -0
index 7f0dbcbb34af..0434c2170f2b 100644
@@ -180,6 +180,7 @@ static unsigned int __bpf_prog_run(void *ctx, const struct bpf_insn *insn)
 		[BPF_LD | BPF_IND | BPF_W] = &&LD_IND_W,
 		[BPF_LD | BPF_IND | BPF_H] = &&LD_IND_H,
 		[BPF_LD | BPF_IND | BPF_B] = &&LD_IND_B,
+		[BPF_LD | BPF_IMM | BPF_DW] = &&LD_IMM_DW,
 	};
 	void *ptr;
 	int off;
@@ -239,6 +240,10 @@ select_insn:
 	ALU64_MOV_K:
 		DST = IMM;
 		CONT;
+	LD_IMM_DW:
+		DST = (u64) (u32) insn[0].imm | ((u64) (u32) insn[1].imm) << 32;
+		insn++;
+		CONT;
 	ALU64_ARSH_X:
 		(*(s64 *) &DST) >>= SRC;
 		CONT;
lib/test_bpf.c +21 -0
index 8c66c6aace04..46ab1a7ef135 100644
@@ -1735,6 +1735,27 @@ static struct bpf_test tests[] = {
 		{ },
 		{ { 1, 0 } },
 	},
+	{
+		"load 64-bit immediate",
+		.u.insns_int = {
+			BPF_LD_IMM64(R1, 0x567800001234L),
+			BPF_MOV64_REG(R2, R1),
+			BPF_MOV64_REG(R3, R2),
+			BPF_ALU64_IMM(BPF_RSH, R2, 32),
+			BPF_ALU64_IMM(BPF_LSH, R3, 32),
+			BPF_ALU64_IMM(BPF_RSH, R3, 32),
+			BPF_ALU64_IMM(BPF_MOV, R0, 0),
+			BPF_JMP_IMM(BPF_JEQ, R2, 0x5678, 1),
+			BPF_EXIT_INSN(),
+			BPF_JMP_IMM(BPF_JEQ, R3, 0x1234, 1),
+			BPF_EXIT_INSN(),
+			BPF_ALU64_IMM(BPF_MOV, R0, 1),
+			BPF_EXIT_INSN(),
+		},
+		INTERNAL,
+		{ },
+		{ { 0, 1 } }
+	},
 };
 
 static struct net_device dev;
Signature · 1 line
1.7.9.5
#2 lore raw

RFC PATCH v7 2/28 net: filter: split filter.h and expose eBPF to user space

In reply to Alexei Starovoitov

eBPF can be used from user space.

uapi/linux/bpf.h: eBPF instruction set definition

linux/filter.h: the rest

This patch only moves macro definitions, but practically it freezes existing eBPF instruction set, though new instructions can still be added in the future.

These eBPF definitions cannot go into uapi/linux/filter.h, since the names may conflict with existing applications.

---
 include/linux/filter.h    |  312 +------------------------------------------
 include/uapi/linux/Kbuild |    1 +
 include/uapi/linux/bpf.h  |  321 +++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 323 insertions(+), 311 deletions(-)
 create mode 100644 include/uapi/linux/bpf.h
include/linux/filter.h +1 -311
index f3262b598262..f04793474d16 100644
@@ -9,322 +9,12 @@
 #include <linux/skbuff.h>
 #include <linux/workqueue.h>
 #include <uapi/linux/filter.h>
-
-/* Internally used and optimized filter representation with extended
- * instruction set based on top of classic BPF.
- */
-
-/* instruction classes */
-#define BPF_ALU64	0x07	/* alu mode in double word width */
-
-/* ld/ldx fields */
-#define BPF_DW		0x18	/* double word */
-#define BPF_XADD	0xc0	/* exclusive add */
-
-/* alu/jmp fields */
-#define BPF_MOV		0xb0	/* mov reg to reg */
-#define BPF_ARSH	0xc0	/* sign extending arithmetic shift right */
-
-/* change endianness of a register */
-#define BPF_END		0xd0	/* flags for endianness conversion: */
-#define BPF_TO_LE	0x00	/* convert to little-endian */
-#define BPF_TO_BE	0x08	/* convert to big-endian */
-#define BPF_FROM_LE	BPF_TO_LE
-#define BPF_FROM_BE	BPF_TO_BE
-
-#define BPF_JNE		0x50	/* jump != */
-#define BPF_JSGT	0x60	/* SGT is signed '>', GT in x86 */
-#define BPF_JSGE	0x70	/* SGE is signed '>=', GE in x86 */
-#define BPF_CALL	0x80	/* function call */
-#define BPF_EXIT	0x90	/* function return */
-
-/* Register numbers */
-enum {
-	BPF_REG_0 = 0,
-	BPF_REG_1,
-	BPF_REG_2,
-	BPF_REG_3,
-	BPF_REG_4,
-	BPF_REG_5,
-	BPF_REG_6,
-	BPF_REG_7,
-	BPF_REG_8,
-	BPF_REG_9,
-	BPF_REG_10,
-	__MAX_BPF_REG,
-};
-
-/* BPF has 10 general purpose 64-bit registers and stack frame. */
-#define MAX_BPF_REG	__MAX_BPF_REG
-
-/* ArgX, context and stack frame pointer register positions. Note,
- * Arg1, Arg2, Arg3, etc are used as argument mappings of function
- * calls in BPF_CALL instruction.
- */
-#define BPF_REG_ARG1	BPF_REG_1
-#define BPF_REG_ARG2	BPF_REG_2
-#define BPF_REG_ARG3	BPF_REG_3
-#define BPF_REG_ARG4	BPF_REG_4
-#define BPF_REG_ARG5	BPF_REG_5
-#define BPF_REG_CTX	BPF_REG_6
-#define BPF_REG_FP	BPF_REG_10
-
-/* Additional register mappings for converted user programs. */
-#define BPF_REG_A	BPF_REG_0
-#define BPF_REG_X	BPF_REG_7
-#define BPF_REG_TMP	BPF_REG_8
-
-/* BPF program can access up to 512 bytes of stack space. */
-#define MAX_BPF_STACK	512
-
-/* Helper macros for filter block array initializers. */
-
-/* ALU ops on registers, bpf_add|sub|...: dst_reg += src_reg */
-
-#define BPF_ALU64_REG(OP, DST, SRC)				\
-	((struct bpf_insn) {					\
-		.code  = BPF_ALU64 | BPF_OP(OP) | BPF_X,	\
-		.dst_reg = DST,					\
-		.src_reg = SRC,					\
-		.off   = 0,					\
-		.imm   = 0 })
-
-#define BPF_ALU32_REG(OP, DST, SRC)				\
-	((struct bpf_insn) {					\
-		.code  = BPF_ALU | BPF_OP(OP) | BPF_X,		\
-		.dst_reg = DST,					\
-		.src_reg = SRC,					\
-		.off   = 0,					\
-		.imm   = 0 })
-
-/* ALU ops on immediates, bpf_add|sub|...: dst_reg += imm32 */
-
-#define BPF_ALU64_IMM(OP, DST, IMM)				\
-	((struct bpf_insn) {					\
-		.code  = BPF_ALU64 | BPF_OP(OP) | BPF_K,	\
-		.dst_reg = DST,					\
-		.src_reg = 0,					\
-		.off   = 0,					\
-		.imm   = IMM })
-
-#define BPF_ALU32_IMM(OP, DST, IMM)				\
-	((struct bpf_insn) {					\
-		.code  = BPF_ALU | BPF_OP(OP) | BPF_K,		\
-		.dst_reg = DST,					\
-		.src_reg = 0,					\
-		.off   = 0,					\
-		.imm   = IMM })
-
-/* Endianess conversion, cpu_to_{l,b}e(), {l,b}e_to_cpu() */
-
-#define BPF_ENDIAN(TYPE, DST, LEN)				\
-	((struct bpf_insn) {					\
-		.code  = BPF_ALU | BPF_END | BPF_SRC(TYPE),	\
-		.dst_reg = DST,					\
-		.src_reg = 0,					\
-		.off   = 0,					\
-		.imm   = LEN })
-
-/* Short form of mov, dst_reg = src_reg */
-
-#define BPF_MOV64_REG(DST, SRC)					\
-	((struct bpf_insn) {					\
-		.code  = BPF_ALU64 | BPF_MOV | BPF_X,		\
-		.dst_reg = DST,					\
-		.src_reg = SRC,					\
-		.off   = 0,					\
-		.imm   = 0 })
-
-#define BPF_MOV32_REG(DST, SRC)					\
-	((struct bpf_insn) {					\
-		.code  = BPF_ALU | BPF_MOV | BPF_X,		\
-		.dst_reg = DST,					\
-		.src_reg = SRC,					\
-		.off   = 0,					\
-		.imm   = 0 })
-
-/* Short form of mov, dst_reg = imm32 */
-
-#define BPF_MOV64_IMM(DST, IMM)					\
-	((struct bpf_insn) {					\
-		.code  = BPF_ALU64 | BPF_MOV | BPF_K,		\
-		.dst_reg = DST,					\
-		.src_reg = 0,					\
-		.off   = 0,					\
-		.imm   = IMM })
-
-#define BPF_MOV32_IMM(DST, IMM)					\
-	((struct bpf_insn) {					\
-		.code  = BPF_ALU | BPF_MOV | BPF_K,		\
-		.dst_reg = DST,					\
-		.src_reg = 0,					\
-		.off   = 0,					\
-		.imm   = IMM })
-
-/* BPF_LD_IMM64 macro encodes single 'load 64-bit immediate' insn */
-#define BPF_LD_IMM64(DST, IMM)					\
-	BPF_LD_IMM64_RAW(DST, 0, IMM)
-
-#define BPF_LD_IMM64_RAW(DST, SRC, IMM)				\
-	((struct bpf_insn) {					\
-		.code  = BPF_LD | BPF_DW | BPF_IMM,		\
-		.dst_reg = DST,					\
-		.src_reg = SRC,					\
-		.off   = 0,					\
-		.imm   = (__u32) (IMM) }),			\
-	((struct bpf_insn) {					\
-		.code  = 0, /* zero is reserved opcode */	\
-		.dst_reg = 0,					\
-		.src_reg = 0,					\
-		.off   = 0,					\
-		.imm   = ((__u64) (IMM)) >> 32 })
-
-/* Short form of mov based on type, BPF_X: dst_reg = src_reg, BPF_K: dst_reg = imm32 */
-
-#define BPF_MOV64_RAW(TYPE, DST, SRC, IMM)			\
-	((struct bpf_insn) {					\
-		.code  = BPF_ALU64 | BPF_MOV | BPF_SRC(TYPE),	\
-		.dst_reg = DST,					\
-		.src_reg = SRC,					\
-		.off   = 0,					\
-		.imm   = IMM })
-
-#define BPF_MOV32_RAW(TYPE, DST, SRC, IMM)			\
-	((struct bpf_insn) {					\
-		.code  = BPF_ALU | BPF_MOV | BPF_SRC(TYPE),	\
-		.dst_reg = DST,					\
-		.src_reg = SRC,					\
-		.off   = 0,					\
-		.imm   = IMM })
-
-/* Direct packet access, R0 = *(uint *) (skb->data + imm32) */
-
-#define BPF_LD_ABS(SIZE, IMM)					\
-	((struct bpf_insn) {					\
-		.code  = BPF_LD | BPF_SIZE(SIZE) | BPF_ABS,	\
-		.dst_reg = 0,					\
-		.src_reg = 0,					\
-		.off   = 0,					\
-		.imm   = IMM })
-
-/* Indirect packet access, R0 = *(uint *) (skb->data + src_reg + imm32) */
-
-#define BPF_LD_IND(SIZE, SRC, IMM)				\
-	((struct bpf_insn) {					\
-		.code  = BPF_LD | BPF_SIZE(SIZE) | BPF_IND,	\
-		.dst_reg = 0,					\
-		.src_reg = SRC,					\
-		.off   = 0,					\
-		.imm   = IMM })
-
-/* Memory load, dst_reg = *(uint *) (src_reg + off16) */
-
-#define BPF_LDX_MEM(SIZE, DST, SRC, OFF)			\
-	((struct bpf_insn) {					\
-		.code  = BPF_LDX | BPF_SIZE(SIZE) | BPF_MEM,	\
-		.dst_reg = DST,					\
-		.src_reg = SRC,					\
-		.off   = OFF,					\
-		.imm   = 0 })
-
-/* Memory store, *(uint *) (dst_reg + off16) = src_reg */
-
-#define BPF_STX_MEM(SIZE, DST, SRC, OFF)			\
-	((struct bpf_insn) {					\
-		.code  = BPF_STX | BPF_SIZE(SIZE) | BPF_MEM,	\
-		.dst_reg = DST,					\
-		.src_reg = SRC,					\
-		.off   = OFF,					\
-		.imm   = 0 })
-
-/* Memory store, *(uint *) (dst_reg + off16) = imm32 */
-
-#define BPF_ST_MEM(SIZE, DST, OFF, IMM)				\
-	((struct bpf_insn) {					\
-		.code  = BPF_ST | BPF_SIZE(SIZE) | BPF_MEM,	\
-		.dst_reg = DST,					\
-		.src_reg = 0,					\
-		.off   = OFF,					\
-		.imm   = IMM })
-
-/* Conditional jumps against registers, if (dst_reg 'op' src_reg) goto pc + off16 */
-
-#define BPF_JMP_REG(OP, DST, SRC, OFF)				\
-	((struct bpf_insn) {					\
-		.code  = BPF_JMP | BPF_OP(OP) | BPF_X,		\
-		.dst_reg = DST,					\
-		.src_reg = SRC,					\
-		.off   = OFF,					\
-		.imm   = 0 })
-
-/* Conditional jumps against immediates, if (dst_reg 'op' imm32) goto pc + off16 */
-
-#define BPF_JMP_IMM(OP, DST, IMM, OFF)				\
-	((struct bpf_insn) {					\
-		.code  = BPF_JMP | BPF_OP(OP) | BPF_K,		\
-		.dst_reg = DST,					\
-		.src_reg = 0,					\
-		.off   = OFF,					\
-		.imm   = IMM })
-
-/* Function call */
-
-#define BPF_EMIT_CALL(FUNC)					\
-	((struct bpf_insn) {					\
-		.code  = BPF_JMP | BPF_CALL,			\
-		.dst_reg = 0,					\
-		.src_reg = 0,					\
-		.off   = 0,					\
-		.imm   = ((FUNC) - __bpf_call_base) })
-
-/* Raw code statement block */
-
-#define BPF_RAW_INSN(CODE, DST, SRC, OFF, IMM)			\
-	((struct bpf_insn) {					\
-		.code  = CODE,					\
-		.dst_reg = DST,					\
-		.src_reg = SRC,					\
-		.off   = OFF,					\
-		.imm   = IMM })
-
-/* Program exit */
-
-#define BPF_EXIT_INSN()						\
-	((struct bpf_insn) {					\
-		.code  = BPF_JMP | BPF_EXIT,			\
-		.dst_reg = 0,					\
-		.src_reg = 0,					\
-		.off   = 0,					\
-		.imm   = 0 })
-
-#define bytes_to_bpf_size(bytes)				\
-({								\
-	int bpf_size = -EINVAL;					\
-								\
-	if (bytes == sizeof(u8))				\
-		bpf_size = BPF_B;				\
-	else if (bytes == sizeof(u16))				\
-		bpf_size = BPF_H;				\
-	else if (bytes == sizeof(u32))				\
-		bpf_size = BPF_W;				\
-	else if (bytes == sizeof(u64))				\
-		bpf_size = BPF_DW;				\
-								\
-	bpf_size;						\
-})
+#include <uapi/linux/bpf.h>
 
 /* Macro to invoke filter function. */
 #define SK_RUN_FILTER(filter, ctx) \
 	(*filter->prog->bpf_func)(ctx, filter->prog->insnsi)
 
-struct bpf_insn {
-	__u8	code;		/* opcode */
-	__u8	dst_reg:4;	/* dest register */
-	__u8	src_reg:4;	/* source register */
-	__s16	off;		/* signed offset */
-	__s32	imm;		/* signed immediate constant */
-};
-
 #ifdef CONFIG_COMPAT
 /* A struct sock_filter is architecture independent. */
 struct compat_sock_fprog {
include/uapi/linux/Kbuild +1 -0
index 24e9033f8b3f..fb3f7b675229 100644
@@ -67,6 +67,7 @@ header-y += bfs_fs.h
 header-y += binfmts.h
 header-y += blkpg.h
 header-y += blktrace_api.h
+header-y += bpf.h
 header-y += bpqether.h
 header-y += bsg.h
 header-y += btrfs.h
include/uapi/linux/bpf.h new file +321 -0

321 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#3 lore raw

RFC PATCH v7 3/28 bpf: introduce syscall(BPF, ...) and BPF maps

In reply to Alexei Starovoitov

BPF syscall is a demux for different BPF releated commands.

'maps' is a generic storage of different types for sharing data between kernel and userspace.

The maps can be created from user space via BPF syscall:
- create a map with given type and attributes
fd = bpf(BPF_MAP_CREATE, union bpf_attr *attr, u32 size) returns fd or negative error

- close(fd) deletes the map

Next patch allows userspace programs to populate/read maps that eBPF programs are concurrently updating.

maps can have different types: hash, bloom filter, radix-tree, etc.

The map is defined by:
. type
. max number of elements
. key size in bytes
. value size in bytes

This patch establishes core infrastructure for BPF maps. Next patches implement lookup/update and hashtable type. More map types can be added in the future.

syscall is using 'union bpf_attr' to be backwards compatible with future extensions. Different syscall commands will use different attributes.

---
 Documentation/networking/filter.txt |   75 +++++++++++++++++
 include/linux/bpf.h                 |   41 ++++++++++
 include/uapi/linux/bpf.h            |   24 ++++++
 kernel/bpf/Makefile                 |    2 +-
 kernel/bpf/syscall.c                |  151 +++++++++++++++++++++++++++++++++++
 5 files changed, 292 insertions(+), 1 deletion(-)
 create mode 100644 include/linux/bpf.h
 create mode 100644 kernel/bpf/syscall.c
Documentation/networking/filter.txt +75 -0
index 81916ab5d96f..30c142b58936 100644
@@ -1001,6 +1001,81 @@ instruction that loads 64-bit immediate value into a dst_reg.
 Classic BPF has similar instruction: BPF_LD | BPF_W | BPF_IMM which loads
 32-bit immediate value into a register.
 
+eBPF maps
+---------
+'maps' is a generic storage of different types for sharing data between kernel
+and userspace.
+
+The maps are accessed from user space via BPF syscall, which has commands:
+- create a map with given type and attributes
+  map_fd = bpf(BPF_MAP_CREATE, union bpf_attr *attr, u32 size)
+  using attr->map_type, attr->key_size, attr->value_size, attr->max_entries
+  returns process-local file descriptor or negative error
+
+- lookup key in a given map
+  err = bpf(BPF_MAP_LOOKUP_ELEM, union bpf_attr *attr, u32 size)
+  using attr->map_fd, attr->key, attr->value
+  returns zero and stores found elem into value or negative error
+
+- create or update key/value pair in a given map
+  err = bpf(BPF_MAP_UPDATE_ELEM, union bpf_attr *attr, u32 size)
+  using attr->map_fd, attr->key, attr->value
+  returns zero or negative error
+
+- find and delete element by key in a given map
+  err = bpf(BPF_MAP_DELETE_ELEM, union bpf_attr *attr, u32 size)
+  using attr->map_fd, attr->key
+
+- to delete map: close(fd)
+  Exiting process will delete maps automatically
+
+userspace programs uses this API to create/populate/read maps that eBPF programs
+are concurrently updating.
+
+maps can have different types: hash, array, bloom filter, radix-tree, etc.
+
+The map is defined by:
+  . type
+  . max number of elements
+  . key size in bytes
+  . value size in bytes
+
+The maps are accesible from eBPF program with API:
+  void * bpf_map_lookup_elem(map_fd, void *key);
+  int bpf_map_update_elem(map_fd, void *key, void *value);
+  int bpf_map_delete_elem(map_fd, void *key);
+
+The kernel replaces process-local map_fd with kernel internal map pointer,
+while loading eBPF program.
+
+If eBPF verifier is configured to recognize extra calls in the program
+bpf_map_lookup_elem() and bpf_map_update_elem() then access to maps looks like:
+  ...
+  ptr_to_value = bpf_map_lookup_elem(map_fd, key)
+  access memory range [ptr_to_value, ptr_to_value + value_size_in_bytes)
+  ...
+  prepare key2 and value2 on stack of key_size and value_size
+  err = bpf_map_update_elem(map_fd, key2, value2)
+  ...
+
+eBPF program cannot create or delete maps
+(such calls will be unknown to verifier)
+
+During program loading the refcnt of used maps is incremented, so they don't get
+deleted while program is running
+
+bpf_map_update_elem() can fail if maximum number of elements reached.
+if key2 already exists, bpf_map_update_elem() replaces it with value2 atomically
+
+bpf_map_lookup_elem() returns NULL or ptr_to_value, so program must do
+if (ptr_to_value != NULL) check before accessing it.
+NULL means that element with given 'key' was not found.
+
+The verifier will check that the program accesses map elements within specified
+size. It will not let programs pass junk values to bpf_map_*_elem() functions,
+so these functions (implemented in C inside kernel) can safely access
+the pointers in all cases.
+
 Testing
 -------
 
include/linux/bpf.h new file +41 -0

41 lines not on this page · raw message

include/uapi/linux/bpf.h +24 -0
index 45a09b46c578..51dc51c898c6 100644
@@ -318,4 +318,28 @@ struct bpf_insn {
 	__s32	imm;		/* signed immediate constant */
 };
 
+/* BPF syscall commands */
+enum bpf_cmd {
+	/* create a map with given type and attributes
+	 * fd = bpf(BPF_MAP_CREATE, union bpf_attr *, u32 size)
+	 * returns fd or negative error
+	 * map is deleted when fd is closed
+	 */
+	BPF_MAP_CREATE,
+};
+
+enum bpf_map_type {
+	BPF_MAP_TYPE_UNSPEC,
+};
+
+union bpf_attr {
+	struct { /* anonymous struct used by BPF_MAP_CREATE command */
+		enum bpf_map_type map_type;
+		__u32	key_size;	/* size of key in bytes */
+		__u32	value_size;	/* size of value in bytes */
+		__u32	max_entries;	/* max number of entries in a map */
+#define BPF_MAP_CREATE_LAST_FIELD max_entries
+	};
+};
+
 #endif /* _UAPI__LINUX_BPF_H__ */
kernel/bpf/Makefile +1 -1
index 6a71145e2769..e9f7334ed07a 100644
@@ -1 +1 @@
-obj-y := core.o
+obj-y := core.o syscall.o
kernel/bpf/syscall.c new file +151 -0

151 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#4 lore raw

RFC PATCH v7 4/28 bpf: enable bpf syscall on x64 and i386

In reply to Alexei Starovoitov

done as separate commit to ease conflict resolution

---
 arch/x86/syscalls/syscall_32.tbl  |    1 +
 arch/x86/syscalls/syscall_64.tbl  |    1 +
 include/linux/syscalls.h          |    3 ++-
 include/uapi/asm-generic/unistd.h |    4 +++-
 kernel/sys_ni.c                   |    3 +++
 5 files changed, 10 insertions(+), 2 deletions(-)
arch/x86/syscalls/syscall_32.tbl +1 -0
index 028b78168d85..9fe1b5d002f0 100644
@@ -363,3 +363,4 @@
 354	i386	seccomp			sys_seccomp
 355	i386	getrandom		sys_getrandom
 356	i386	memfd_create		sys_memfd_create
+357	i386	bpf			sys_bpf
arch/x86/syscalls/syscall_64.tbl +1 -0
index 35dd922727b9..281150b539a2 100644
@@ -327,6 +327,7 @@
 318	common	getrandom		sys_getrandom
 319	common	memfd_create		sys_memfd_create
 320	common	kexec_file_load		sys_kexec_file_load
+321	common	bpf			sys_bpf
 
 #
 # x32-specific system call numbers start at 512 to avoid cache impact
include/linux/syscalls.h +2 -1
index 0f86d85a9ce4..bda9b81357cc 100644
@@ -65,6 +65,7 @@ struct old_linux_dirent;
 struct perf_event_attr;
 struct file_handle;
 struct sigaltstack;
+union bpf_attr;
 
 #include <linux/types.h>
 #include <linux/aio_abi.h>
@@ -875,5 +876,5 @@ asmlinkage long sys_seccomp(unsigned int op, unsigned int flags,
 			    const char __user *uargs);
 asmlinkage long sys_getrandom(char __user *buf, size_t count,
 			      unsigned int flags);
-
+asmlinkage long sys_bpf(int cmd, union bpf_attr *attr, unsigned int size);
 #endif
include/uapi/asm-generic/unistd.h +3 -1
index 11d11bc5c78f..22749c134117 100644
@@ -705,9 +705,11 @@ __SYSCALL(__NR_seccomp, sys_seccomp)
 __SYSCALL(__NR_getrandom, sys_getrandom)
 #define __NR_memfd_create 279
 __SYSCALL(__NR_memfd_create, sys_memfd_create)
+#define __NR_bpf 280
+__SYSCALL(__NR_bpf, sys_bpf)
 
 #undef __NR_syscalls
-#define __NR_syscalls 280
+#define __NR_syscalls 281
 
 /*
  * All syscalls below here should go away really,
kernel/sys_ni.c +3 -0
index 391d4ddb6f4b..b4b5083f5f5e 100644
@@ -218,3 +218,6 @@ cond_syscall(sys_kcmp);
 
 /* operate on Secure Computing state */
 cond_syscall(sys_seccomp);
+
+/* access BPF programs and maps */
+cond_syscall(sys_bpf);
Signature · 1 line
1.7.9.5
#5 lore raw

RFC PATCH v7 5/28 bpf: add lookup/update/delete/iterate methods to BPF maps

In reply to Alexei Starovoitov

'maps' is a generic storage of different types for sharing data between kernel and userspace.

The maps are accessed from user space via BPF syscall, which has commands:

- create a map with given type and attributes
fd = bpf(BPF_MAP_CREATE, union bpf_attr *attr, u32 size) returns fd or negative error

- lookup key in a given map referenced by fd
err = bpf(BPF_MAP_LOOKUP_ELEM, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key, attr->value
returns zero and stores found elem into value or negative error

- create or update key/value pair in a given map
err = bpf(BPF_MAP_UPDATE_ELEM, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key, attr->value
returns zero or negative error

- find and delete element by key in a given map
err = bpf(BPF_MAP_DELETE_ELEM, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key

- iterate map elements (based on input key return next_key) err = bpf(BPF_MAP_GET_NEXT_KEY, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key, attr->next_key

- close(fd) deletes the map

---
 include/linux/bpf.h      |    8 ++
 include/uapi/linux/bpf.h |   42 +++++++++
 kernel/bpf/syscall.c     |  219 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 269 insertions(+)
include/linux/bpf.h +8 -0
index 48014a71f0fe..2887f3f9da59 100644
@@ -9,6 +9,7 @@
 
 #include <uapi/linux/bpf.h>
 #include <linux/workqueue.h>
+#include <linux/file.h>
 
 struct bpf_map;
 
@@ -17,6 +18,12 @@ struct bpf_map_ops {
 	/* funcs callable from userspace (via syscall) */
 	struct bpf_map *(*map_alloc)(union bpf_attr *attr);
 	void (*map_free)(struct bpf_map *);
+	int (*map_get_next_key)(struct bpf_map *map, void *key, void *next_key);
+
+	/* funcs callable from userspace and from eBPF programs */
+	void *(*map_lookup_elem)(struct bpf_map *map, void *key);
+	int (*map_update_elem)(struct bpf_map *map, void *key, void *value);
+	int (*map_delete_elem)(struct bpf_map *map, void *key);
 };
 
 struct bpf_map {
@@ -37,5 +44,6 @@ struct bpf_map_type_list {
 
 void bpf_register_map_type(struct bpf_map_type_list *tl);
 void bpf_map_put(struct bpf_map *map);
+struct bpf_map *bpf_map_get(struct fd f);
 
 #endif /* _LINUX_BPF_H */
include/uapi/linux/bpf.h +42 -0

54 lines not on this page · raw message

kernel/bpf/syscall.c +219 -0

237 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#6 lore raw

RFC PATCH v7 6/28 bpf: add hashtable type of BPF maps

In reply to Alexei Starovoitov

add new map type BPF_MAP_TYPE_HASH and its implementation

- key/value are opaque range of bytes

- user space provides 3 configuration attributes via BPF syscall:
key_size, value_size, max_entries

- if value_size == 0, the map is used as a set

- map_update_elem() must fail to insert new element when max_entries limit is reached

- map takes care of allocating/freeing key/value pairs

- update/lookup/delete methods may be called from eBPF program attached to kprobes, so use spin_lock_irqsave() mechanism for concurrent updates

- optimized for speed of lookup() which can be called multiple times from eBPF program which itself is triggered by high volume of events

- in the future JIT compiler may recognize lookup() call and optimize it further, since key_size is constant for life of eBPF program

---
 include/uapi/linux/bpf.h |    1 +
 kernel/bpf/Makefile      |    2 +-
 kernel/bpf/hashtab.c     |  365 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 367 insertions(+), 1 deletion(-)
 create mode 100644 kernel/bpf/hashtab.c
include/uapi/linux/bpf.h +1 -0
index 1602de6423b5..ad0a5a495ec3 100644
@@ -359,6 +359,7 @@ enum bpf_cmd {
 
 enum bpf_map_type {
 	BPF_MAP_TYPE_UNSPEC,
+	BPF_MAP_TYPE_HASH,
 };
 
 union bpf_attr {
kernel/bpf/Makefile +1 -1
index e9f7334ed07a..558e12712ebc 100644
@@ -1 +1 @@
-obj-y := core.o syscall.o
+obj-y := core.o syscall.o hashtab.o
kernel/bpf/hashtab.c new file +365 -0

365 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#7 lore raw

RFC PATCH v7 7/28 bpf: expand BPF syscall with program load/unload

In reply to Alexei Starovoitov

eBPF programs are safe run-to-completion functions with load/unload methods from userspace similar to kernel modules.

User space API:

- load eBPF program
fd = bpf(BPF_PROG_LOAD, union bpf_attr *attr, u32 size)

where 'attr' is

  struct {
      enum bpf_prog_type prog_type;
      __u32 insn_cnt;
      struct bpf_insn __user *insns;
      const char __user *license;

};
insns - array of eBPF instructions
license - must be GPL compatible to call helper functions marked gpl_only

- unload eBPF program
close(fd)

User space tests and examples follow in the later patches

---
 include/linux/bpf.h      |   36 ++++++++++
 include/linux/filter.h   |    9 ++-
 include/uapi/linux/bpf.h |   27 ++++++++
 kernel/bpf/syscall.c     |  170 ++++++++++++++++++++++++++++++++++++++++++++++
 net/core/filter.c        |    2 +
 5 files changed, 242 insertions(+), 2 deletions(-)
include/linux/bpf.h +36 -0
index 2887f3f9da59..8ea6f9923ff2 100644
@@ -46,4 +46,40 @@ void bpf_register_map_type(struct bpf_map_type_list *tl);
 void bpf_map_put(struct bpf_map *map);
 struct bpf_map *bpf_map_get(struct fd f);
 
+/* eBPF function prototype used by verifier to allow BPF_CALLs from eBPF programs
+ * to in-kernel helper functions and for adjusting imm32 field in BPF_CALL
+ * instructions after verifying
+ */
+struct bpf_func_proto {
+	u64 (*func)(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5);
+	bool gpl_only;
+};
+
+struct bpf_verifier_ops {
+	/* return eBPF function prototype for verification */
+	const struct bpf_func_proto *(*get_func_proto)(enum bpf_func_id func_id);
+};
+
+struct bpf_prog_type_list {
+	struct list_head list_node;
+	struct bpf_verifier_ops *ops;
+	enum bpf_prog_type type;
+};
+
+void bpf_register_prog_type(struct bpf_prog_type_list *tl);
+
+struct bpf_prog_info {
+	atomic_t refcnt;
+	bool is_gpl_compatible;
+	enum bpf_prog_type prog_type;
+	struct bpf_verifier_ops *ops;
+	struct bpf_map **used_maps;
+	u32 used_map_cnt;
+};
+
+struct bpf_prog;
+
+void bpf_prog_put(struct bpf_prog *prog);
+struct bpf_prog *bpf_prog_get(u32 ufd);
+
 #endif /* _LINUX_BPF_H */
include/linux/filter.h +7 -2
index f04793474d16..f06913b29861 100644
@@ -31,11 +31,16 @@ struct sock_fprog_kern {
 struct sk_buff;
 struct sock;
 struct seccomp_data;
+struct bpf_prog_info;
 
 struct bpf_prog {
 	u32			jited:1,	/* Is our filter JIT'ed? */
-				len:31;		/* Number of filter blocks */
-	struct sock_fprog_kern	*orig_prog;	/* Original BPF program */
+				has_info:1,	/* whether 'info' is valid */
+				len:30;		/* Number of filter blocks */
+	union {
+		struct sock_fprog_kern	*orig_prog;	/* Original BPF program */
+		struct bpf_prog_info	*info;
+	};
 	unsigned int		(*bpf_func)(const struct sk_buff *skb,
 					    const struct bpf_insn *filter);
 	union {
include/uapi/linux/bpf.h +27 -0
index ad0a5a495ec3..ac272bd7a884 100644
@@ -355,6 +355,13 @@ enum bpf_cmd {
 	 * returns zero and stores next key or negative error
 	 */
 	BPF_MAP_GET_NEXT_KEY,
+
+	/* verify and load eBPF program
+	 * prog_fd = bpf(BPF_PROG_LOAD, union bpf_attr *attr, u32 size)
+	 * Using attr->prog_type, attr->insns, attr->license
+	 * returns fd or negative error
+	 */
+	BPF_PROG_LOAD,
 };
 
 enum bpf_map_type {
@@ -362,6 +369,10 @@ enum bpf_map_type {
 	BPF_MAP_TYPE_HASH,
 };
 
+enum bpf_prog_type {
+	BPF_PROG_TYPE_UNSPEC,
+};
+
 union bpf_attr {
 	struct { /* anonymous struct used by BPF_MAP_CREATE command */
 		enum bpf_map_type map_type;
@@ -383,6 +394,22 @@ union bpf_attr {
 #define BPF_MAP_DELETE_ELEM_LAST_FIELD key
 #define BPF_MAP_GET_NEXT_KEY_LAST_FIELD next_key
 	};
+
+	struct { /* anonymous struct used by BPF_PROG_LOAD command */
+		enum bpf_prog_type prog_type;
+		__u32 insn_cnt;
+		const struct bpf_insn __user *insns;
+		const char __user *license;
+#define	BPF_PROG_LOAD_LAST_FIELD license
+	};
+};
+
+/* integer value in 'imm' field of BPF_CALL instruction selects which helper
+ * function eBPF program intends to call
+ */
+enum bpf_func_id {
+	BPF_FUNC_unspec,
+	__BPF_FUNC_MAX_ID,
 };
 
 #endif /* _UAPI__LINUX_BPF_H__ */
kernel/bpf/syscall.c +170 -0

188 lines not on this page · raw message

net/core/filter.c +2 -0
index d814b8a89d0f..ed15874a9beb 100644
@@ -835,6 +835,7 @@ static void bpf_release_orig_filter(struct bpf_prog *fp)
 {
 	struct sock_fprog_kern *fprog = fp->orig_prog;
 
+	BUG_ON(fp->has_info);
 	if (fprog) {
 		kfree(fprog->filter);
 		kfree(fprog);
@@ -973,6 +974,7 @@ static struct bpf_prog *bpf_prepare_filter(struct bpf_prog *fp)
 
 	fp->bpf_func = NULL;
 	fp->jited = 0;
+	fp->has_info = 0;
 
 	err = bpf_check_classic(fp->insns, fp->len);
 	if (err) {
Signature · 1 line
1.7.9.5
#8 lore raw

RFC PATCH v7 8/28 bpf: handle pseudo BPF_CALL insn

In reply to Alexei Starovoitov

in native eBPF programs userspace is using pseudo BPF_CALL instructions which encode one of 'enum bpf_func_id' inside insn->imm field. Verifier checks that program using correct function arguments to given func_id. If all checks passed, kernel needs to fixup BPF_CALL->imm fields by replacing func_id with in-kernel function pointer.
eBPF interpreter just calls the function.

In-kernel eBPF users continue to use generic BPF_CALL.

---
 kernel/bpf/syscall.c |   37 +++++++++++++++++++++++++++++++++++++
 1 file changed, 37 insertions(+)
kernel/bpf/syscall.c +37 -0
index c316f7c28895..9dbf7bd42ccf 100644
@@ -339,6 +339,40 @@ void bpf_register_prog_type(struct bpf_prog_type_list *tl)
 	list_add(&tl->list_node, &bpf_prog_types);
 }
 
+/* fixup insn->imm field of bpf_call instructions:
+ * if (insn->imm == BPF_FUNC_map_lookup_elem)
+ *      insn->imm = bpf_map_lookup_elem - __bpf_call_base;
+ * else if (insn->imm == BPF_FUNC_map_update_elem)
+ *      insn->imm = bpf_map_update_elem - __bpf_call_base;
+ * else ...
+ *
+ * this function is called after eBPF program passed verification
+ */
+static void fixup_bpf_calls(struct bpf_prog *prog)
+{
+	const struct bpf_func_proto *fn;
+	int i;
+
+	for (i = 0; i < prog->len; i++) {
+		struct bpf_insn *insn = &prog->insnsi[i];
+
+		if (insn->code == (BPF_JMP | BPF_CALL)) {
+			/* we reach here when program has bpf_call instructions
+			 * and it passed bpf_check(), means that
+			 * ops->get_func_proto must have been supplied, check it
+			 */
+			BUG_ON(!prog->info->ops->get_func_proto);
+
+			fn = prog->info->ops->get_func_proto(insn->imm);
+			/* all functions that have prototype and verifier allowed
+			 * programs to call them, must be real in-kernel functions
+			 */
+			BUG_ON(!fn->func);
+			insn->imm = fn->func - __bpf_call_base;
+		}
+	}
+}
+
 /* drop refcnt on maps used by eBPF program and free auxilary data */
 static void free_bpf_prog_info(struct bpf_prog_info *info)
 {
@@ -465,6 +499,9 @@ static int bpf_prog_load(union bpf_attr *attr)
 	if (err < 0)
 		goto free_prog_info;
 
+	/* fixup BPF_CALL->imm field */
+	fixup_bpf_calls(prog);
+
 	/* eBPF program is ready to be JITed */
 	bpf_prog_select_runtime(prog);
 
Signature · 1 line
1.7.9.5
#9 lore raw

RFC PATCH v7 9/28 bpf: verifier (add docs)

In reply to Alexei Starovoitov

this patch adds all of eBPF verfier documentation and empty bpf_check()

The end goal for the verifier is to statically check safety of the program.

Verifier will catch:
- loops
- out of range jumps
- unreachable instructions
- invalid instructions
- uninitialized register access
- uninitialized stack access
- misaligned stack access
- out of range stack access
- invalid calling convention

More details in Documentation/networking/filter.txt

---
 Documentation/networking/filter.txt |  230 +++++++++++++++++++++++++++++++++++
 include/linux/bpf.h                 |    2 +
 kernel/bpf/Makefile                 |    2 +-
 kernel/bpf/syscall.c                |    2 +-
 kernel/bpf/verifier.c               |  152 +++++++++++++++++++++++
 5 files changed, 386 insertions(+), 2 deletions(-)
 create mode 100644 kernel/bpf/verifier.c
Documentation/networking/filter.txt +230 -0
index 30c142b58936..713e71f9f5dd 100644
@@ -1001,6 +1001,105 @@ instruction that loads 64-bit immediate value into a dst_reg.
 Classic BPF has similar instruction: BPF_LD | BPF_W | BPF_IMM which loads
 32-bit immediate value into a register.
 
+eBPF verifier
+-------------
+The safety of the eBPF program is determined in two steps.
+
+First step does DAG check to disallow loops and other CFG validation.
+In particular it will detect programs that have unreachable instructions.
+(though classic BPF checker allows them)
+
+Second step starts from the first insn and descends all possible paths.
+It simulates execution of every insn and observes the state change of
+registers and stack.
+
+At the start of the program the register R1 contains a pointer to context
+and has type PTR_TO_CTX.
+If verifier sees an insn that does R2=R1, then R2 has now type
+PTR_TO_CTX as well and can be used on the right hand side of expression.
+If R1=PTR_TO_CTX and insn is R2=R1+R1, then R2=UNKNOWN_VALUE,
+since addition of two valid pointers makes invalid pointer.
+(In 'secure' mode verifier will reject any type of pointer arithmetic to make
+sure that kernel addresses don't leak to unprivileged users)
+
+If register was never written to, it's not readable:
+  bpf_mov R0 = R2
+  bpf_exit
+will be rejected, since R2 is unreadable at the start of the program.
+
+After kernel function call, R1-R5 are reset to unreadable and
+R0 has a return type of the function.
+
+Since R6-R9 are callee saved, their state is preserved across the call.
+  bpf_mov R6 = 1
+  bpf_call foo
+  bpf_mov R0 = R6
+  bpf_exit
+is a correct program. If there was R1 instead of R6, it would have
+been rejected.
+
+Classic BPF register X is mapped to eBPF register R7 inside sk_convert_filter(),
+so that its state is preserved across calls.
+
+load/store instructions are allowed only with registers of valid types, which
+are PTR_TO_CTX, PTR_TO_MAP, FRAME_PTR. They are bounds and alignment checked.
+For example:
+ bpf_mov R1 = 1
+ bpf_mov R2 = 2
+ bpf_xadd *(u32 *)(R1 + 3) += R2
+ bpf_exit
+will be rejected, since R1 doesn't have a valid pointer type at the time of
+execution of instruction bpf_xadd.
+
+At the start R1 contains pointer to ctx and R1 type is PTR_TO_CTX.
+ctx is generic. verifier is configured to known what context is for particular
+class of bpf programs. For example, context == skb (for socket filters) and
+ctx == seccomp_data for seccomp filters.
+A callback is used to customize verifier to restrict eBPF program access to only
+certain fields within ctx structure with specified size and alignment.
+
+For example, the following insn:
+  bpf_ld R0 = *(u32 *)(R6 + 8)
+intends to load a word from address R6 + 8 and store it into R0
+If R6=PTR_TO_CTX, via is_valid_access() callback the verifier will know
+that offset 8 of size 4 bytes can be accessed for reading, otherwise
+the verifier will reject the program.
+If R6=FRAME_PTR, then access should be aligned and be within
+stack bounds, which are [-MAX_BPF_STACK, 0). In this example offset is 8,
+so it will fail verification, since it's out of bounds.
+
+The verifier will allow eBPF program to read data from stack only after
+it wrote into it.
+Classic BPF verifier does similar check with M[0-15] memory slots.
+For example:
+  bpf_ld R0 = *(u32 *)(R10 - 4)
+  bpf_exit
+is invalid program.
+Though R10 is correct read-only register and has type FRAME_PTR
+and R10 - 4 is within stack bounds, there were no stores into that location.
+
+Pointer register spill/fill is tracked as well, since four (R6-R9)
+callee saved registers may not be enough for some programs.
+
+Allowed function calls are customized with bpf_verifier_ops->get_func_proto()
+The eBPF verifier will check that registers match argument constraints.
+After the call register R0 will be set to return type of the function.
+
+Function calls is a main mechanism to extend functionality of eBPF programs.
+Socket filters may let programs to call one set of functions, whereas tracing
+filters may allow completely different set.
+
+If a function made accessible to eBPF program, it needs to be thought through
+from security point of view. The verifier will guarantee that the function is
+called with valid arguments.
+
+seccomp vs socket filters have different security restrictions for classic BPF.
+Seccomp solves this by two stage verifier: classic BPF verifier is followed
+by seccomp verifier. In case of eBPF one configurable verifier is shared for
+all use cases.
+
+See details of eBPF verifier in kernel/bpf/verifier.c
+
 eBPF maps
 ---------
 'maps' is a generic storage of different types for sharing data between kernel
@@ -1076,6 +1175,137 @@ size. It will not let programs pass junk values to bpf_map_*_elem() functions,
 so these functions (implemented in C inside kernel) can safely access
 the pointers in all cases.
 
+Understanding eBPF verifier messages
+------------------------------------
+
+The following are few examples of invalid eBPF programs and verifier error
+messages as seen in the log:
+
+Program with unreachable instructions:
+static struct bpf_insn prog[] = {
+  BPF_EXIT_INSN(),
+  BPF_EXIT_INSN(),
+};
+Error:
+  unreachable insn 1
+
+Program that reads uninitialized register:
+  BPF_MOV64_REG(BPF_REG_0, BPF_REG_2),
+  BPF_EXIT_INSN(),
+Error:
+  0: (bf) r0 = r2
+  R2 !read_ok
+
+Program that doesn't initialize R0 before exiting:
+  BPF_MOV64_REG(BPF_REG_2, BPF_REG_1),
+  BPF_EXIT_INSN(),
+Error:
+  0: (bf) r2 = r1
+  1: (95) exit
+  R0 !read_ok
+
+Program that accesses stack out of bounds:
+  BPF_ST_MEM(BPF_DW, BPF_REG_10, 8, 0),
+  BPF_EXIT_INSN(),
+Error:
+  0: (7a) *(u64 *)(r10 +8) = 0
+  invalid stack off=8 size=8
+
+Program that doesn't initialize stack before passing its address into function:
+  BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+  BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+  BPF_LD_MAP_FD(BPF_REG_1, 0),
+  BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+  BPF_EXIT_INSN(),
+Error:
+  0: (bf) r2 = r10
+  1: (07) r2 += -8
+  2: (b7) r1 = 0x0
+  3: (85) call 1
+  invalid indirect read from stack off -8+0 size 8
+
+Program that uses invalid map_fd=0 while calling to map_lookup_elem() function:
+  BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+  BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+  BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+  BPF_LD_MAP_FD(BPF_REG_1, 0),
+  BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+  BPF_EXIT_INSN(),
+Error:
+  0: (7a) *(u64 *)(r10 -8) = 0
+  1: (bf) r2 = r10
+  2: (07) r2 += -8
+  3: (b7) r1 = 0x0
+  4: (85) call 1
+  fd 0 is not pointing to valid bpf_map
+
+Program that doesn't check return value of map_lookup_elem() before accessing
+map element:
+  BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+  BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+  BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+  BPF_LD_MAP_FD(BPF_REG_1, 0),
+  BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+  BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
+  BPF_EXIT_INSN(),
+Error:
+  0: (7a) *(u64 *)(r10 -8) = 0
+  1: (bf) r2 = r10
+  2: (07) r2 += -8
+  3: (b7) r1 = 0x0
+  4: (85) call 1
+  5: (7a) *(u64 *)(r0 +0) = 0
+  R0 invalid mem access 'map_value_or_null'
+
+Program that correctly checks map_lookup_elem() returned value for NULL, but
+accesses the memory with incorrect alignment:
+  BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+  BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+  BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+  BPF_LD_MAP_FD(BPF_REG_1, 0),
+  BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+  BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 1),
+  BPF_ST_MEM(BPF_DW, BPF_REG_0, 4, 0),
+  BPF_EXIT_INSN(),
+Error:
+  0: (7a) *(u64 *)(r10 -8) = 0
+  1: (bf) r2 = r10
+  2: (07) r2 += -8
+  3: (b7) r1 = 1
+  4: (85) call 1
+  5: (15) if r0 == 0x0 goto pc+1
+   R0=map_ptr R10=fp
+  6: (7a) *(u64 *)(r0 +4) = 0
+  misaligned access off 4 size 8
+
+Program that correctly checks map_lookup_elem() returned value for NULL and
+accesses memory with correct alignment in one side of 'if' branch, but fails
+to do so in the other side of 'if' branch:
+  BPF_ST_MEM(BPF_DW, BPF_REG_10, -8, 0),
+  BPF_MOV64_REG(BPF_REG_2, BPF_REG_10),
+  BPF_ALU64_IMM(BPF_ADD, BPF_REG_2, -8),
+  BPF_LD_MAP_FD(BPF_REG_1, 0),
+  BPF_RAW_INSN(BPF_JMP | BPF_CALL, 0, 0, 0, BPF_FUNC_map_lookup_elem),
+  BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 2),
+  BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 0),
+  BPF_EXIT_INSN(),
+  BPF_ST_MEM(BPF_DW, BPF_REG_0, 0, 1),
+  BPF_EXIT_INSN(),
+Error:
+  0: (7a) *(u64 *)(r10 -8) = 0
+  1: (bf) r2 = r10
+  2: (07) r2 += -8
+  3: (b7) r1 = 1
+  4: (85) call 1
+  5: (15) if r0 == 0x0 goto pc+2
+   R0=map_ptr R10=fp
+  6: (7a) *(u64 *)(r0 +0) = 0
+  7: (95) exit
+
+  from 5 to 8: R0=imm0 R10=fp
+  8: (7a) *(u64 *)(r0 +0) = 1
+  R0 invalid mem access 'imm'
+
 Testing
 -------
 
include/linux/bpf.h +2 -0
index 8ea6f9923ff2..490551e17c15 100644
@@ -81,5 +81,7 @@ struct bpf_prog;
 
 void bpf_prog_put(struct bpf_prog *prog);
 struct bpf_prog *bpf_prog_get(u32 ufd);
+/* verify correctness of eBPF program */
+int bpf_check(struct bpf_prog *fp, union bpf_attr *attr);
 
 #endif /* _LINUX_BPF_H */
kernel/bpf/Makefile +1 -1
index 558e12712ebc..95a9035e0f29 100644
@@ -1 +1 @@
-obj-y := core.o syscall.o hashtab.o
+obj-y := core.o syscall.o hashtab.o verifier.o
kernel/bpf/syscall.c +1 -1
index 9dbf7bd42ccf..8f11d1549cfc 100644
@@ -494,7 +494,7 @@ static int bpf_prog_load(union bpf_attr *attr)
 		goto free_prog_info;
 
 	/* run eBPF verifier */
-	/* err = bpf_check(prog, tb); */
+	err = bpf_check(prog, attr);
 
 	if (err < 0)
 		goto free_prog_info;
kernel/bpf/verifier.c new file +152 -0

152 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#10 lore raw

RFC PATCH v7 10/28 bpf: verifier (add ability to receive verification log)

In reply to Alexei Starovoitov

add optional attributes for BPF_PROG_LOAD syscall:

struct {
	...
	__u32 log_level;	/* verbosity level of eBPF verifier */
	__u32 log_size;		/* size of user buffer */
	void __user *log_buf;	/* user supplied buffer */
};

In such case the verifier will return its verification log in the user supplied buffer which can be used by humans to analyze why verifier rejected given program

---
 include/uapi/linux/bpf.h |    5 +-
 kernel/bpf/verifier.c    |  235 ++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 239 insertions(+), 1 deletion(-)
include/uapi/linux/bpf.h +4 -1
index ac272bd7a884..a6fa0416f2bd 100644
@@ -400,7 +400,10 @@ union bpf_attr {
 		__u32 insn_cnt;
 		const struct bpf_insn __user *insns;
 		const char __user *license;
-#define	BPF_PROG_LOAD_LAST_FIELD license
+		__u32 log_level;	/* verbosity level of eBPF verifier */
+		__u32 log_size;		/* size of user buffer */
+		void __user *log_buf;	/* user supplied buffer */
+#define	BPF_PROG_LOAD_LAST_FIELD log_buf
 	};
 };
 
kernel/bpf/verifier.c +235 -0

244 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#11 lore raw

RFC PATCH v7 11/28 bpf: handle pseudo BPF_LD_IMM64 insn

In reply to Alexei Starovoitov

eBPF programs passed from userspace are using pseudo BPF_LD_IMM64 instructions to refer to process-local map_fd. Scan the program for such instructions and if FDs are valid, convert them to 'struct bpf_map' pointers which will be used by verifier to check access to maps in bpf_map_lookup/update() calls. If program passes verifier, convert pseudo BPF_LD_IMM64 into generic by dropping BPF_PSEUDO_MAP_FD flag.

Note that eBPF interpreter is generic and knows nothing about pseudo insns.

---
 include/uapi/linux/bpf.h |    6 ++
 kernel/bpf/verifier.c    |  147 ++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 153 insertions(+)
include/uapi/linux/bpf.h +6 -0
index a6fa0416f2bd..04aaaef0daa7 100644
@@ -176,6 +176,12 @@ enum {
 		.off   = 0,					\
 		.imm   = ((__u64) (IMM)) >> 32 })
 
+#define BPF_PSEUDO_MAP_FD	1
+
+/* pseudo BPF_LD_IMM64 insn used to refer to process-local map_fd */
+#define BPF_LD_MAP_FD(DST, MAP_FD)				\
+	BPF_LD_IMM64_RAW(DST, BPF_PSEUDO_MAP_FD, MAP_FD)
+
 /* Short form of mov based on type, BPF_X: dst_reg = src_reg, BPF_K: dst_reg = imm32 */
 
 #define BPF_MOV64_RAW(TYPE, DST, SRC, IMM)			\
kernel/bpf/verifier.c +147 -0

188 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#12 lore raw

RFC PATCH v7 12/28 bpf: verifier (add branch/goto checks)

In reply to Alexei Starovoitov

check that control flow graph of eBPF program is a directed acyclic graph

check_cfg() does:
- detect loops
- detect unreachable instructions
- check that program terminates with BPF_EXIT insn
- check that all branches are within program boundary

---
 kernel/bpf/verifier.c |  183 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 183 insertions(+)
kernel/bpf/verifier.c +183 -0
index 73811d69e7be..7365a190cbd6 100644
@@ -332,6 +332,185 @@ static struct bpf_map *ld_imm64_to_map_ptr(struct bpf_insn *insn)
 	return (struct bpf_map *) (unsigned long) imm64;
 }
 
+/* non-recursive DFS pseudo code
+ * 1  procedure DFS-iterative(G,v):
+ * 2      label v as discovered
+ * 3      let S be a stack
+ * 4      S.push(v)
+ * 5      while S is not empty
+ * 6            t <- S.pop()
+ * 7            if t is what we're looking for:
+ * 8                return t
+ * 9            for all edges e in G.adjacentEdges(t) do
+ * 10               if edge e is already labelled
+ * 11                   continue with the next edge
+ * 12               w <- G.adjacentVertex(t,e)
+ * 13               if vertex w is not discovered and not explored
+ * 14                   label e as tree-edge
+ * 15                   label w as discovered
+ * 16                   S.push(w)
+ * 17                   continue at 5
+ * 18               else if vertex w is discovered
+ * 19                   label e as back-edge
+ * 20               else
+ * 21                   // vertex w is explored
+ * 22                   label e as forward- or cross-edge
+ * 23           label t as explored
+ * 24           S.pop()
+ *
+ * convention:
+ * 0x10 - discovered
+ * 0x11 - discovered and fall-through edge labelled
+ * 0x12 - discovered and fall-through and branch edges labelled
+ * 0x20 - explored
+ */
+
+enum {
+	DISCOVERED = 0x10,
+	EXPLORED = 0x20,
+	FALLTHROUGH = 1,
+	BRANCH = 2,
+};
+
+#define PUSH_INT(I) \
+	do { \
+		if (cur_stack >= insn_cnt) { \
+			ret = -E2BIG; \
+			goto free_st; \
+		} \
+		stack[cur_stack++] = I; \
+	} while (0)
+
+#define PEEK_INT() \
+	({ \
+		int _ret; \
+		if (cur_stack == 0) \
+			_ret = -1; \
+		else \
+			_ret = stack[cur_stack - 1]; \
+		_ret; \
+	 })
+
+#define POP_INT() \
+	({ \
+		int _ret; \
+		if (cur_stack == 0) \
+			_ret = -1; \
+		else \
+			_ret = stack[--cur_stack]; \
+		_ret; \
+	 })
+
+#define PUSH_INSN(T, W, E) \
+	do { \
+		int w = W; \
+		if (E == FALLTHROUGH && st[T] >= (DISCOVERED | FALLTHROUGH)) \
+			break; \
+		if (E == BRANCH && st[T] >= (DISCOVERED | BRANCH)) \
+			break; \
+		if (w < 0 || w >= insn_cnt) { \
+			verbose("jump out of range from insn %d to %d\n", T, w); \
+			ret = -EINVAL; \
+			goto free_st; \
+		} \
+		if (st[w] == 0) { \
+			/* tree-edge */ \
+			st[T] = DISCOVERED | E; \
+			st[w] = DISCOVERED; \
+			PUSH_INT(w); \
+			goto peek_stack; \
+		} else if ((st[w] & 0xF0) == DISCOVERED) { \
+			verbose("back-edge from insn %d to %d\n", T, w); \
+			ret = -EINVAL; \
+			goto free_st; \
+		} else if (st[w] == EXPLORED) { \
+			/* forward- or cross-edge */ \
+			st[T] = DISCOVERED | E; \
+		} else { \
+			verbose("insn state internal bug\n"); \
+			ret = -EFAULT; \
+			goto free_st; \
+		} \
+	} while (0)
+
+/* non-recursive depth-first-search to detect loops in BPF program
+ * loop == back-edge in directed graph
+ */
+static int check_cfg(struct verifier_env *env)
+{
+	struct bpf_insn *insns = env->prog->insnsi;
+	int insn_cnt = env->prog->len;
+	int cur_stack = 0;
+	int *stack;
+	int ret = 0;
+	int *st;
+	int i, t;
+
+	st = kzalloc(sizeof(int) * insn_cnt, GFP_KERNEL);
+	if (!st)
+		return -ENOMEM;
+
+	stack = kzalloc(sizeof(int) * insn_cnt, GFP_KERNEL);
+	if (!stack) {
+		kfree(st);
+		return -ENOMEM;
+	}
+
+	st[0] = DISCOVERED; /* mark 1st insn as discovered */
+	PUSH_INT(0);
+
+peek_stack:
+	while ((t = PEEK_INT()) != -1) {
+		if (BPF_CLASS(insns[t].code) == BPF_JMP) {
+			u8 opcode = BPF_OP(insns[t].code);
+
+			if (opcode == BPF_EXIT) {
+				goto mark_explored;
+			} else if (opcode == BPF_CALL) {
+				PUSH_INSN(t, t + 1, FALLTHROUGH);
+			} else if (opcode == BPF_JA) {
+				if (BPF_SRC(insns[t].code) != BPF_K) {
+					ret = -EINVAL;
+					goto free_st;
+				}
+				/* unconditional jump with single edge */
+				PUSH_INSN(t, t + insns[t].off + 1, FALLTHROUGH);
+			} else {
+				/* conditional jump with two edges */
+				PUSH_INSN(t, t + 1, FALLTHROUGH);
+				PUSH_INSN(t, t + insns[t].off + 1, BRANCH);
+			}
+		} else {
+			/* all other non-branch instructions with single
+			 * fall-through edge
+			 */
+			PUSH_INSN(t, t + 1, FALLTHROUGH);
+		}
+
+mark_explored:
+		st[t] = EXPLORED;
+		if (POP_INT() == -1) {
+			verbose("pop_int internal bug\n");
+			ret = -EFAULT;
+			goto free_st;
+		}
+	}
+
+
+	for (i = 0; i < insn_cnt; i++) {
+		if (st[i] != EXPLORED) {
+			verbose("unreachable insn %d\n", i);
+			ret = -EINVAL;
+			goto free_st;
+		}
+	}
+
+free_st:
+	kfree(st);
+	kfree(stack);
+	return ret;
+}
+
 /* look for pseudo eBPF instructions that access map FDs and
  * replace them with actual map pointers
  */
@@ -481,6 +660,10 @@ int bpf_check(struct bpf_prog *prog, union bpf_attr *attr)
 	if (ret < 0)
 		goto skip_full_check;
 
+	ret = check_cfg(env);
+	if (ret < 0)
+		goto skip_full_check;
+
 	/* ret = do_check(env); */
 
 skip_full_check:
Signature · 1 line
1.7.9.5
#13 lore raw

RFC PATCH v7 13/28 bpf: verifier (add verifier core)

In reply to Alexei Starovoitov

This patch adds verifier core which simulates execution of every insn and records the state of registers and program stack. Every branch instruction seen during simulation is pushed into state stack. When verifier reaches BPF_EXIT, it pops the state from the stack and continues until it reaches BPF_EXIT again. For program:
1: bpf_mov r1, xxx
2: if (r1 == 0) goto 5
3: bpf_mov r0, 1
4: goto 6
5: bpf_mov r0, 2
6: bpf_exit
The verifier will walk insns: 1, 2, 3, 4, 6
then it will pop the state recorded at insn#2 and will continue: 5, 6

This way it walks all possible paths through the program and checks all possible values of registers. While doing so, it checks for:
- invalid instructions
- uninitialized register access
- uninitialized stack access
- misaligned stack access
- out of range stack access
- invalid calling convention
- BPF_LD_ABS|IND instructions are only used in socket filters
- instruction encoding is not using reserved fields

Kernel subsystem configures the verifier with two callbacks:

- bool (*is_valid_access)(int off, int size, enum bpf_access_type type); that provides information to the verifer which fields of 'ctx' are accessible (remember 'ctx' is the first argument to eBPF program)

- const struct bpf_func_proto *(*get_func_proto)(enum bpf_func_id func_id); returns argument constraints of kernel helper functions that eBPF program may call, so that verifier can checks that R1-R5 types match the prototype

More details in Documentation/networking/filter.txt and in kernel/bpf/verifier.c

---
 include/linux/bpf.h      |   47 ++
 include/uapi/linux/bpf.h |    1 +
 kernel/bpf/verifier.c    | 1061 +++++++++++++++++++++++++++++++++++++++++++++-
 3 files changed, 1108 insertions(+), 1 deletion(-)
include/linux/bpf.h +47 -0
index 490551e17c15..ad1bda7ece35 100644
@@ -46,6 +46,31 @@ void bpf_register_map_type(struct bpf_map_type_list *tl);
 void bpf_map_put(struct bpf_map *map);
 struct bpf_map *bpf_map_get(struct fd f);
 
+/* function argument constraints */
+enum bpf_arg_type {
+	ARG_ANYTHING = 0,	/* any argument is ok */
+
+	/* the following constraints used to prototype
+	 * bpf_map_lookup/update/delete_elem() functions
+	 */
+	ARG_CONST_MAP_PTR,	/* const argument used as pointer to bpf_map */
+	ARG_PTR_TO_MAP_KEY,	/* pointer to stack used as map key */
+	ARG_PTR_TO_MAP_VALUE,	/* pointer to stack used as map value */
+
+	/* the following constraints used to prototype bpf_memcmp() and other
+	 * functions that access data on eBPF program stack
+	 */
+	ARG_PTR_TO_STACK,	/* any pointer to eBPF program stack */
+	ARG_CONST_STACK_SIZE,	/* number of bytes accessed from stack */
+};
+
+/* type of values returned from helper functions */
+enum bpf_return_type {
+	RET_INTEGER,			/* function returns integer */
+	RET_VOID,			/* function doesn't return anything */
+	RET_PTR_TO_MAP_VALUE_OR_NULL,	/* returns a pointer to map elem value or NULL */
+};
+
 /* eBPF function prototype used by verifier to allow BPF_CALLs from eBPF programs
  * to in-kernel helper functions and for adjusting imm32 field in BPF_CALL
  * instructions after verifying
@@ -53,11 +78,33 @@ struct bpf_map *bpf_map_get(struct fd f);
 struct bpf_func_proto {
 	u64 (*func)(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5);
 	bool gpl_only;
+	enum bpf_return_type ret_type;
+	enum bpf_arg_type arg1_type;
+	enum bpf_arg_type arg2_type;
+	enum bpf_arg_type arg3_type;
+	enum bpf_arg_type arg4_type;
+	enum bpf_arg_type arg5_type;
+};
+
+/* bpf_context is intentionally undefined structure. Pointer to bpf_context is
+ * the first argument to eBPF programs.
+ * For socket filters: 'struct bpf_context *' == 'struct sk_buff *'
+ */
+struct bpf_context;
+
+enum bpf_access_type {
+	BPF_READ = 1,
+	BPF_WRITE = 2
 };
 
 struct bpf_verifier_ops {
 	/* return eBPF function prototype for verification */
 	const struct bpf_func_proto *(*get_func_proto)(enum bpf_func_id func_id);
+
+	/* return true if 'size' wide access at offset 'off' within bpf_context
+	 * with 'type' (read or write) is allowed
+	 */
+	bool (*is_valid_access)(int off, int size, enum bpf_access_type type);
 };
 
 struct bpf_prog_type_list {
include/uapi/linux/bpf.h +1 -0
index 04aaaef0daa7..dee7a2469b8d 100644
@@ -377,6 +377,7 @@ enum bpf_map_type {
 
 enum bpf_prog_type {
 	BPF_PROG_TYPE_UNSPEC,
+	BPF_PROG_TYPE_SOCKET_FILTER,
 };
 
 union bpf_attr {
kernel/bpf/verifier.c +1060 -1

1,105 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#14 lore raw

RFC PATCH v7 14/28 bpf: verifier (add state prunning optimization)

In reply to Alexei Starovoitov

since verifier walks all possible paths it's important to recognize equivalent verifier states to speed up verification.

If one of the old states is more strict than the current state, it means the current state doesn't need to be explored further, since verifier already concluded that more strict state leads to valid bpf_exit.

---
 kernel/bpf/verifier.c |  134 +++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 134 insertions(+)
kernel/bpf/verifier.c +134 -0
index eb19f753d4d7..4d183040ab64 100644
@@ -220,6 +220,7 @@ struct verifier_env {
 	struct verifier_stack_elem *head; /* stack of verifier states to be processed */
 	int stack_size;			/* number of states to be processed */
 	struct verifier_state cur_state; /* current verifier state */
+	struct verifier_state_list **branch_landing; /* search prunning optimization */
 	struct bpf_map *used_maps[MAX_USED_MAPS]; /* array of map's used by eBPF program */
 	u32 used_map_cnt;		/* number of used maps */
 };
@@ -1256,6 +1257,8 @@ enum {
 	BRANCH = 2,
 };
 
+#define STATE_END ((struct verifier_state_list *) -1L)
+
 #define PUSH_INT(I) \
 	do { \
 		if (cur_stack >= insn_cnt) { \
@@ -1297,6 +1300,9 @@ enum {
 			ret = -EINVAL; \
 			goto free_st; \
 		} \
+		if (E == BRANCH) \
+			/* mark branch target for state pruning */ \
+			env->branch_landing[w] = STATE_END; \
 		if (st[w] == 0) { \
 			/* tree-edge */ \
 			st[T] = DISCOVERED | E; \
@@ -1364,6 +1370,10 @@ peek_stack:
 				PUSH_INSN(t, t + 1, FALLTHROUGH);
 				PUSH_INSN(t, t + insns[t].off + 1, BRANCH);
 			}
+			/* tell verifier to check for equivalent verifier states
+			 * after every call and jump
+			 */
+			env->branch_landing[t + 1] = STATE_END;
 		} else {
 			/* all other non-branch instructions with single
 			 * fall-through edge
@@ -1395,6 +1405,88 @@ free_st:
 	return ret;
 }
 
+/* compare two verifier states
+ *
+ * all states stored in state_list are known to be valid, since
+ * verifier reached 'bpf_exit' instruction through them
+ *
+ * this function is called when verifier exploring different branches of
+ * execution popped from the state stack. If it sees an old state that has
+ * more strict register state and more strict stack state then this execution
+ * branch doesn't need to be explored further, since verifier already
+ * concluded that more strict state leads to valid finish.
+ *
+ * Therefore two states are equivalent if register state is more conservative
+ * and explored stack state is more conservative than the current one.
+ * Example:
+ *       explored                   current
+ * (slot1=INV slot2=MISC) == (slot1=MISC slot2=MISC)
+ * (slot1=MISC slot2=MISC) != (slot1=INV slot2=MISC)
+ *
+ * In other words if current stack state (one being explored) has more
+ * valid slots than old one that already passed validation, it means
+ * the verifier can stop exploring and conclude that current state is valid too
+ *
+ * Similarly with registers. If explored state has register type as invalid
+ * whereas register type in current state is meaningful, it means that
+ * the current state will reach 'bpf_exit' instruction safely
+ */
+static bool states_equal(struct verifier_state *old, struct verifier_state *cur)
+{
+	int i;
+
+	for (i = 0; i < MAX_BPF_REG; i++) {
+		if (memcmp(&old->regs[i], &cur->regs[i],
+			   sizeof(old->regs[0])) != 0) {
+			if (old->regs[i].type == NOT_INIT ||
+			    old->regs[i].type == UNKNOWN_VALUE)
+				continue;
+			return false;
+		}
+	}
+
+	for (i = 0; i < MAX_BPF_STACK; i++) {
+		if (memcmp(&old->stack[i], &cur->stack[i],
+			   sizeof(old->stack[0])) != 0) {
+			if (old->stack[i].stype == STACK_INVALID)
+				continue;
+			return false;
+		}
+	}
+	return true;
+}
+
+static int is_state_visited(struct verifier_env *env, int insn_idx)
+{
+	struct verifier_state_list *new_sl;
+	struct verifier_state_list *sl;
+
+	sl = env->branch_landing[insn_idx];
+	if (!sl)
+		/* no branch jump to this insn, ignore it */
+		return 0;
+
+	while (sl != STATE_END) {
+		if (states_equal(&sl->state, &env->cur_state))
+			/* reached equivalent register/stack state,
+			 * prune the search
+			 */
+			return 1;
+		sl = sl->next;
+	}
+	new_sl = kmalloc(sizeof(struct verifier_state_list), GFP_KERNEL);
+
+	if (!new_sl)
+		/* ignore ENOMEM, it doesn't affect correctness */
+		return 0;
+
+	/* add new state to the head of linked list */
+	memcpy(&new_sl->state, &env->cur_state, sizeof(env->cur_state));
+	new_sl->next = env->branch_landing[insn_idx];
+	env->branch_landing[insn_idx] = new_sl;
+	return 0;
+}
+
 static int do_check(struct verifier_env *env)
 {
 	struct verifier_state *state = &env->cur_state;
@@ -1426,6 +1518,17 @@ static int do_check(struct verifier_env *env)
 			return -E2BIG;
 		}
 
+		if (is_state_visited(env, insn_idx)) {
+			if (log_level) {
+				if (do_print_state)
+					verbose("\nfrom %d to %d: safe\n",
+						prev_insn_idx, insn_idx);
+				else
+					verbose("%d: safe\n", insn_idx);
+			}
+			goto process_bpf_exit;
+		}
+
 		if (log_level && do_print_state) {
 			verbose("\nfrom %d to %d:", prev_insn_idx, insn_idx);
 			print_verifier_state(env);
@@ -1536,6 +1639,7 @@ static int do_check(struct verifier_env *env)
 				 * something into it earlier
 				 */
 				_(check_reg_arg(regs, BPF_REG_0, SRC_OP));
+process_bpf_exit:
 				insn_idx = pop_stack(env, &prev_insn_idx);
 				if (insn_idx < 0) {
 					break;
@@ -1670,6 +1774,28 @@ static void convert_pseudo_ld_imm64(struct verifier_env *env)
 			insn->src_reg = 0;
 }
 
+static void free_states(struct verifier_env *env)
+{
+	struct verifier_state_list *sl, *sln;
+	int i;
+
+	if (!env->branch_landing)
+		return;
+
+	for (i = 0; i < env->prog->len; i++) {
+		sl = env->branch_landing[i];
+
+		if (sl)
+			while (sl != STATE_END) {
+				sln = sl->next;
+				kfree(sl);
+				sl = sln;
+			}
+	}
+
+	kfree(env->branch_landing);
+}
+
 int bpf_check(struct bpf_prog *prog, union bpf_attr *attr)
 {
 	void __user *log_ubuf = NULL;
@@ -1718,6 +1844,13 @@ int bpf_check(struct bpf_prog *prog, union bpf_attr *attr)
 	if (ret < 0)
 		goto skip_full_check;
 
+	env->branch_landing = kcalloc(prog->len,
+				      sizeof(struct verifier_state_list *),
+				      GFP_KERNEL);
+	ret = -ENOMEM;
+	if (!env->branch_landing)
+		goto skip_full_check;
+
 	ret = check_cfg(env);
 	if (ret < 0)
 		goto skip_full_check;
@@ -1726,6 +1859,7 @@ int bpf_check(struct bpf_prog *prog, union bpf_attr *attr)
 
 skip_full_check:
 	while (pop_stack(env, NULL) >= 0);
+	free_states(env);
 
 	if (log_level && log_len >= log_size - 1) {
 		BUG_ON(log_len >= log_size);
Signature · 1 line
1.7.9.5
#15 lore raw

RFC PATCH v7 15/28 bpf: allow eBPF programs to use maps

In reply to Alexei Starovoitov

expose bpf_map_lookup_elem(), bpf_map_update_elem(), bpf_map_delete_elem() map accessors to eBPF programs

---
 include/linux/bpf.h      |    5 ++++
 include/uapi/linux/bpf.h |    3 ++
 kernel/bpf/syscall.c     |   68 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 76 insertions(+)
include/linux/bpf.h +5 -0
index ad1bda7ece35..14e23bb10b2d 100644
@@ -131,4 +131,9 @@ struct bpf_prog *bpf_prog_get(u32 ufd);
 /* verify correctness of eBPF program */
 int bpf_check(struct bpf_prog *fp, union bpf_attr *attr);
 
+/* in-kernel helper functions called from eBPF programs */
+u64 bpf_map_lookup_elem(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5);
+u64 bpf_map_update_elem(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5);
+u64 bpf_map_delete_elem(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5);
+
 #endif /* _LINUX_BPF_H */
include/uapi/linux/bpf.h +3 -0
index dee7a2469b8d..f87b501b2e1b 100644
@@ -419,6 +419,9 @@ union bpf_attr {
  */
 enum bpf_func_id {
 	BPF_FUNC_unspec,
+	BPF_FUNC_map_lookup_elem, /* void *map_lookup_elem(&map, &key) */
+	BPF_FUNC_map_update_elem, /* int map_update_elem(&map, &key, &value) */
+	BPF_FUNC_map_delete_elem, /* int map_delete_elem(&map, &key) */
 	__BPF_FUNC_MAX_ID,
 };
 
kernel/bpf/syscall.c +68 -0

71 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#16 lore raw

RFC PATCH v7 16/28 bpf: split eBPF out of NET

In reply to Alexei Starovoitov

let eBPF have its own CONFIG_BPF, so that tracing and other subsystems don't need to depend on all of NET

---
 arch/Kconfig      |    3 +++
 kernel/Makefile   |    2 +-
 kernel/bpf/core.c |   12 ++++++++++++
 net/Kconfig       |    1 +
 4 files changed, 17 insertions(+), 1 deletion(-)
arch/Kconfig +3 -0
index 0eae9df35b88..80a72f6f6b60 100644
@@ -333,6 +333,9 @@ config SECCOMP_FILTER
 
 	  See Documentation/prctl/seccomp_filter.txt for details.
 
+config BPF
+	boolean
+
 config HAVE_CC_STACKPROTECTOR
 	bool
 	help
kernel/Makefile +1 -1
index dc5c77544fd6..17ea6d4a9a24 100644
@@ -86,7 +86,7 @@ obj-$(CONFIG_RING_BUFFER) += trace/
 obj-$(CONFIG_TRACEPOINTS) += trace/
 obj-$(CONFIG_IRQ_WORK) += irq_work.o
 obj-$(CONFIG_CPU_PM) += cpu_pm.o
-obj-$(CONFIG_NET) += bpf/
+obj-$(CONFIG_BPF) += bpf/
 
 obj-$(CONFIG_PERF_EVENTS) += events/
 
kernel/bpf/core.c +12 -0
index 0434c2170f2b..c17ba0ef3dcf 100644
@@ -537,3 +537,15 @@ void bpf_prog_free(struct bpf_prog *fp)
 	bpf_jit_free(fp);
 }
 EXPORT_SYMBOL_GPL(bpf_prog_free);
+
+/* To emulate LD_ABS/LD_IND instructions __sk_run_filter() may call
+ * skb_copy_bits(), so provide a weak definition for it in NET-less config.
+ * seccomp_check_filter() verifies that seccomp filters are not using
+ * LD_ABS/LD_IND instructions. Other BPF users (like tracing filters)
+ * must not use these instructions unless ctx==skb
+ */
+int __weak skb_copy_bits(const struct sk_buff *skb, int offset, void *to,
+			 int len)
+{
+	return -EFAULT;
+}
net/Kconfig +1 -0
index 4051fdfa4367..9a99e16d6f28 100644
@@ -6,6 +6,7 @@ menuconfig NET
 	bool "Networking support"
 	select NLATTR
 	select GENERIC_NET_UTILS
+	select BPF
 	---help---
 	  Unless you really know what you are doing, you should say Y here.
 	  The reason is that some programs need kernel networking support even
Signature · 1 line
1.7.9.5
#17 lore raw

RFC PATCH v7 17/28 tracing: allow eBPF programs to be attached to events

In reply to Alexei Starovoitov

User interface:
fd = open("/sys/kernel/debug/tracing/__event__/filter")

write(fd, "bpf_123")

where 123 is process local FD associated with eBPF program previously loaded. __event__ is static tracepoint event or syscall.
(kprobe support is in next patch)
Once program is successfully attached to tracepoint event, the tracepoint will be auto-enabled

close(fd)
auto-disables tracepoint event and detaches eBPF program from it

eBPF programs can call in-kernel helper functions to:
- lookup/update/delete elements in maps
- memcmp
- dump_stack
- fetch_ptr/u64/u32/u16/u8 values from unsafe address via probe_kernel_read(), so that eBPF program can walk any kernel data structures

---
 fs/btrfs/super.c                   |    3 +
 include/linux/ftrace_event.h       |    5 +
 include/trace/bpf_trace.h          |   23 +++++
 include/trace/ftrace.h             |   25 +++++
 include/uapi/linux/bpf.h           |    8 ++
 kernel/trace/Kconfig               |    1 +
 kernel/trace/Makefile              |    1 +
 kernel/trace/bpf_trace.c           |  183 ++++++++++++++++++++++++++++++++++++
 kernel/trace/trace.h               |    3 +
 kernel/trace/trace_events.c        |   41 +++++++-
 kernel/trace/trace_events_filter.c |   72 +++++++++++++-
 kernel/trace/trace_syscalls.c      |   32 +++++++
 12 files changed, 395 insertions(+), 2 deletions(-)
 create mode 100644 include/trace/bpf_trace.h
 create mode 100644 kernel/trace/bpf_trace.c
fs/btrfs/super.c +3 -0
index c4124de4435b..274d20752e07 100644
@@ -61,6 +61,9 @@
 #include "tests/btrfs-tests.h"
 
 #define CREATE_TRACE_POINTS
+/* dummy definition to make compiler happy */
+struct __btrfs_workqueue {
+};
 #include <trace/events/btrfs.h>
 
 static const struct super_operations btrfs_super_ops;
include/linux/ftrace_event.h +5 -0
index 28672e87e910..10602bfa07fe 100644
@@ -237,6 +237,7 @@ enum {
 	TRACE_EVENT_FL_WAS_ENABLED_BIT,
 	TRACE_EVENT_FL_USE_CALL_FILTER_BIT,
 	TRACE_EVENT_FL_TRACEPOINT_BIT,
+	TRACE_EVENT_FL_BPF_BIT,
 };
 
 /*
@@ -259,6 +260,7 @@ enum {
 	TRACE_EVENT_FL_WAS_ENABLED	= (1 << TRACE_EVENT_FL_WAS_ENABLED_BIT),
 	TRACE_EVENT_FL_USE_CALL_FILTER	= (1 << TRACE_EVENT_FL_USE_CALL_FILTER_BIT),
 	TRACE_EVENT_FL_TRACEPOINT	= (1 << TRACE_EVENT_FL_TRACEPOINT_BIT),
+	TRACE_EVENT_FL_BPF		= (1 << TRACE_EVENT_FL_BPF_BIT),
 };
 
 struct ftrace_event_call {
@@ -533,6 +535,9 @@ event_trigger_unlock_commit_regs(struct ftrace_event_file *file,
 		event_triggers_post_call(file, tt);
 }
 
+struct bpf_context;
+void trace_filter_call_bpf(struct event_filter *filter, struct bpf_context *ctx);
+
 enum {
 	FILTER_OTHER = 0,
 	FILTER_STATIC_STRING,
include/trace/bpf_trace.h new file +23 -0
new file mode 100644
index 000000000000..6074cc917800
@@ -0,0 +1,23 @@
+/* Copyright (c) 2011-2014 PLUMgrid, http://plumgrid.com
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of version 2 of the GNU General Public
+ * License as published by the Free Software Foundation.
+ */
+#ifndef _LINUX_KERNEL_BPF_TRACE_H
+#define _LINUX_KERNEL_BPF_TRACE_H
+
+/* For tracing filters save first six arguments of tracepoint events.
+ * argN fields match one to one to arguments passed to tracepoint events.
+ */
+struct bpf_context {
+	u64 arg1;
+	u64 arg2;
+	u64 arg3;
+	u64 arg4;
+	u64 arg5;
+	u64 arg6;
+	u64 ret;
+};
+
+#endif /* _LINUX_KERNEL_BPF_TRACE_H */
include/trace/ftrace.h +25 -0
index 26b4f2e13275..4c7d59bdc24a 100644
@@ -17,6 +17,7 @@
  */
 
 #include <linux/ftrace_event.h>
+#include <trace/bpf_trace.h>
 
 /*
  * DECLARE_EVENT_CLASS can be used to add a generic function
@@ -619,6 +620,20 @@ static inline notrace int ftrace_get_offsets_##call(			\
 #undef __perf_task
 #define __perf_task(t)	(t)
 
+/* cast any interger or pointer type to u64 without warnings */
+#define __CAST_TO_U64(expr) \
+	 __builtin_choose_expr(sizeof(long) < sizeof(expr), \
+			       (u64) (expr - ((typeof(expr))0)), \
+			       (u64) (long) expr)
+
+#define __BPF_CAST1(a,...) __CAST_TO_U64(a)
+#define __BPF_CAST2(a,...) __CAST_TO_U64(a), __BPF_CAST1(__VA_ARGS__)
+#define __BPF_CAST3(a,...) __CAST_TO_U64(a), __BPF_CAST2(__VA_ARGS__)
+#define __BPF_CAST4(a,...) __CAST_TO_U64(a), __BPF_CAST3(__VA_ARGS__)
+#define __BPF_CAST5(a,...) __CAST_TO_U64(a), __BPF_CAST4(__VA_ARGS__)
+#define __BPF_CAST6(a,...) __CAST_TO_U64(a), __BPF_CAST5(__VA_ARGS__)
+#define __BPF_CAST(a,...)  __CAST_TO_U64(a), __BPF_CAST6(__VA_ARGS__)
+
 #undef DECLARE_EVENT_CLASS
 #define DECLARE_EVENT_CLASS(call, proto, args, tstruct, assign, print)	\
 									\
@@ -634,6 +649,16 @@ ftrace_raw_event_##call(void *__data, proto)				\
 	if (ftrace_trigger_soft_disabled(ftrace_file))			\
 		return;							\
 									\
+	if (unlikely(ftrace_file->flags & FTRACE_EVENT_FL_FILTERED) &&	\
+	    unlikely(ftrace_file->event_call->flags & TRACE_EVENT_FL_BPF)) { \
+		struct bpf_context __ctx = ((struct bpf_context) {	\
+				__BPF_CAST(args, 0, 0, 0, 0, 0, 0)	\
+			});						\
+									\
+		trace_filter_call_bpf(ftrace_file->filter, &__ctx);	\
+		return;							\
+	}								\
+									\
 	__data_size = ftrace_get_offsets_##call(&__data_offsets, args); \
 									\
 	entry = ftrace_event_buffer_reserve(&fbuffer, ftrace_file,	\
include/uapi/linux/bpf.h +8 -0
index f87b501b2e1b..55adff33083e 100644
@@ -378,6 +378,7 @@ enum bpf_map_type {
 enum bpf_prog_type {
 	BPF_PROG_TYPE_UNSPEC,
 	BPF_PROG_TYPE_SOCKET_FILTER,
+	BPF_PROG_TYPE_TRACING_FILTER,
 };
 
 union bpf_attr {
@@ -422,6 +423,13 @@ enum bpf_func_id {
 	BPF_FUNC_map_lookup_elem, /* void *map_lookup_elem(&map, &key) */
 	BPF_FUNC_map_update_elem, /* int map_update_elem(&map, &key, &value) */
 	BPF_FUNC_map_delete_elem, /* int map_delete_elem(&map, &key) */
+	BPF_FUNC_fetch_ptr,       /* void *bpf_fetch_ptr(void *unsafe_ptr) */
+	BPF_FUNC_fetch_u64,       /* u64 bpf_fetch_u64(void *unsafe_ptr) */
+	BPF_FUNC_fetch_u32,       /* u32 bpf_fetch_u32(void *unsafe_ptr) */
+	BPF_FUNC_fetch_u16,       /* u16 bpf_fetch_u16(void *unsafe_ptr) */
+	BPF_FUNC_fetch_u8,        /* u8 bpf_fetch_u8(void *unsafe_ptr) */
+	BPF_FUNC_memcmp,          /* int bpf_memcmp(void *unsafe_ptr, void *safe_ptr, int size) */
+	BPF_FUNC_dump_stack,      /* void bpf_dump_stack(void) */
 	__BPF_FUNC_MAX_ID,
 };
 
kernel/trace/Kconfig +1 -0
index a5da09c899dd..038424e54443 100644
@@ -75,6 +75,7 @@ config FTRACE_NMI_ENTER
 
 config EVENT_TRACING
 	select CONTEXT_SWITCH_TRACER
+	select BPF
 	bool
 
 config CONTEXT_SWITCH_TRACER
kernel/trace/Makefile +1 -0
index 67d6369ddf83..fe897168a19e 100644
@@ -53,6 +53,7 @@ obj-$(CONFIG_EVENT_TRACING) += trace_event_perf.o
 endif
 obj-$(CONFIG_EVENT_TRACING) += trace_events_filter.o
 obj-$(CONFIG_EVENT_TRACING) += trace_events_trigger.o
+obj-$(CONFIG_EVENT_TRACING) += bpf_trace.o
 obj-$(CONFIG_KPROBE_EVENT) += trace_kprobe.o
 obj-$(CONFIG_TRACEPOINTS) += power-traces.o
 ifeq ($(CONFIG_PM_RUNTIME),y)
kernel/trace/bpf_trace.c new file +183 -0

183 lines not on this page · raw message

kernel/trace/trace.h +3 -0
index 385391fb1d3b..f0b7caa71b9d 100644
@@ -986,12 +986,15 @@ struct ftrace_event_field {
 	int			is_signed;
 };
 
+struct bpf_prog;
+
 struct event_filter {
 	int			n_preds;	/* Number assigned */
 	int			a_preds;	/* allocated */
 	struct filter_pred	*preds;
 	struct filter_pred	*root;
 	char			*filter_string;
+	struct bpf_prog		*prog;
 };
 
 struct event_subsystem {
kernel/trace/trace_events.c +40 -1

62 lines not on this page · raw message

kernel/trace/trace_events_filter.c +71 -1

102 lines not on this page · raw message

kernel/trace/trace_syscalls.c +32 -0
index 759d5e004517..7a3d0623763f 100644
@@ -7,6 +7,7 @@
 #include <linux/ftrace.h>
 #include <linux/perf_event.h>
 #include <asm/syscall.h>
+#include <trace/bpf_trace.h>
 
 #include "trace_output.h"
 #include "trace.h"
@@ -299,6 +300,21 @@ static int __init syscall_exit_define_fields(struct ftrace_event_call *call)
 	return ret;
 }
 
+static void populate_bpf_ctx(struct bpf_context *ctx, struct pt_regs *regs)
+{
+	struct task_struct *task = current;
+	unsigned long args[6];
+
+	syscall_get_arguments(task, regs, 0, 6, args);
+	ctx->arg1 = args[0];
+	ctx->arg2 = args[1];
+	ctx->arg3 = args[2];
+	ctx->arg4 = args[3];
+	ctx->arg5 = args[4];
+	ctx->arg6 = args[5];
+	ctx->ret = syscall_get_return_value(task, regs);
+}
+
 static void ftrace_syscall_enter(void *data, struct pt_regs *regs, long id)
 {
 	struct trace_array *tr = data;
@@ -328,6 +344,14 @@ static void ftrace_syscall_enter(void *data, struct pt_regs *regs, long id)
 	if (!sys_data)
 		return;
 
+	if (ftrace_file->event_call->flags & TRACE_EVENT_FL_BPF) {
+		struct bpf_context ctx;
+
+		populate_bpf_ctx(&ctx, regs);
+		trace_filter_call_bpf(ftrace_file->filter, &ctx);
+		return;
+	}
+
 	size = sizeof(*entry) + sizeof(unsigned long) * sys_data->nb_args;
 
 	local_save_flags(irq_flags);
@@ -375,6 +399,14 @@ static void ftrace_syscall_exit(void *data, struct pt_regs *regs, long ret)
 	if (!sys_data)
 		return;
 
+	if (ftrace_file->event_call->flags & TRACE_EVENT_FL_BPF) {
+		struct bpf_context ctx;
+
+		populate_bpf_ctx(&ctx, regs);
+		trace_filter_call_bpf(ftrace_file->filter, &ctx);
+		return;
+	}
+
 	local_save_flags(irq_flags);
 	pc = preempt_count();
 
Signature · 1 line
1.7.9.5
#18 lore raw

RFC PATCH v7 18/28 tracing: allow eBPF programs call printk()

In reply to Alexei Starovoitov

limited printk() with %d %u %x %p modifiers only

---
 include/uapi/linux/bpf.h |    1 +
 kernel/trace/bpf_trace.c |   61 ++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 62 insertions(+)
include/uapi/linux/bpf.h +1 -0
index 55adff33083e..1ec3d293d14e 100644
@@ -430,6 +430,7 @@ enum bpf_func_id {
 	BPF_FUNC_fetch_u8,        /* u8 bpf_fetch_u8(void *unsafe_ptr) */
 	BPF_FUNC_memcmp,          /* int bpf_memcmp(void *unsafe_ptr, void *safe_ptr, int size) */
 	BPF_FUNC_dump_stack,      /* void bpf_dump_stack(void) */
+	BPF_FUNC_printk,          /* int bpf_printk(const char *fmt, int fmt_size, ...) */
 	__BPF_FUNC_MAX_ID,
 };
 
kernel/trace/bpf_trace.c +61 -0

73 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#19 lore raw

RFC PATCH v7 19/28 tracing: allow eBPF programs to be attached to kprobe/kretprobe

In reply to Alexei Starovoitov
---
 kernel/trace/trace_kprobe.c |   28 ++++++++++++++++++++++++++++
 1 file changed, 28 insertions(+)
kernel/trace/trace_kprobe.c +28 -0
index 282f6e4e5539..b6db92207c99 100644
@@ -19,6 +19,7 @@
 
 #include <linux/module.h>
 #include <linux/uaccess.h>
+#include <trace/bpf_trace.h>
 
 #include "trace_probe.h"
 
@@ -930,6 +931,22 @@ __kprobe_trace_func(struct trace_kprobe *tk, struct pt_regs *regs,
 	if (ftrace_trigger_soft_disabled(ftrace_file))
 		return;
 
+	if (call->flags & TRACE_EVENT_FL_BPF) {
+		struct bpf_context ctx = {};
+		unsigned long args[3];
+		/* get first 3 arguments of the function. x64 syscall ABI uses
+		 * the same 3 registers as x64 calling convention.
+		 * todo: implement it cleanly via arch specific
+		 * regs_get_argument_nth() helper
+		 */
+		syscall_get_arguments(current, regs, 0, 3, args);
+		ctx.arg1 = args[0];
+		ctx.arg2 = args[1];
+		ctx.arg3 = args[2];
+		trace_filter_call_bpf(ftrace_file->filter, &ctx);
+		return;
+	}
+
 	local_save_flags(irq_flags);
 	pc = preempt_count();
 
@@ -978,6 +995,17 @@ __kretprobe_trace_func(struct trace_kprobe *tk, struct kretprobe_instance *ri,
 	if (ftrace_trigger_soft_disabled(ftrace_file))
 		return;
 
+	if (call->flags & TRACE_EVENT_FL_BPF) {
+		struct bpf_context ctx = {};
+		/* assume that register used to return a value from syscall is
+		 * the same as register used to return a value from a function
+		 * todo: provide arch specific helper
+		 */
+		ctx.ret = syscall_get_return_value(current, regs);
+		trace_filter_call_bpf(ftrace_file->filter, &ctx);
+		return;
+	}
+
 	local_save_flags(irq_flags);
 	pc = preempt_count();
 
Signature · 1 line
1.7.9.5
#20 lore raw

RFC PATCH v7 20/28 tracing: allow eBPF programs to call ktime_get_ns() and get_current()

In reply to Alexei Starovoitov
---
 include/uapi/linux/bpf.h |    2 ++
 kernel/trace/bpf_trace.c |   20 ++++++++++++++++++++
 2 files changed, 22 insertions(+)
include/uapi/linux/bpf.h +2 -0
index 1ec3d293d14e..e14e147c8899 100644
@@ -431,6 +431,8 @@ enum bpf_func_id {
 	BPF_FUNC_memcmp,          /* int bpf_memcmp(void *unsafe_ptr, void *safe_ptr, int size) */
 	BPF_FUNC_dump_stack,      /* void bpf_dump_stack(void) */
 	BPF_FUNC_printk,          /* int bpf_printk(const char *fmt, int fmt_size, ...) */
+	BPF_FUNC_ktime_get_ns,    /* u64 bpf_ktime_get_ns(void) */
+	BPF_FUNC_get_current,     /* struct task_struct *bpf_get_current(void) */
 	__BPF_FUNC_MAX_ID,
 };
 
kernel/trace/bpf_trace.c +20 -0
index ff98be5a24d6..a98e13e1131b 100644
@@ -114,6 +114,16 @@ static u64 bpf_printk(u64 r1, u64 fmt_size, u64 r3, u64 r4, u64 r5)
 			      mod_l[2] ? r5 : (u32) r5);
 }
 
+static u64 bpf_ktime_get_ns(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5)
+{
+	return ktime_get_ns();
+}
+
+static u64 bpf_get_current(u64 r1, u64 r2, u64 r3, u64 r4, u64 r5)
+{
+	return (u64) (long) current;
+}
+
 static struct bpf_func_proto tracing_filter_funcs[] = {
 #define FETCH(SIZE)				\
 	[BPF_FUNC_fetch_##SIZE] = {		\
@@ -169,6 +179,16 @@ static struct bpf_func_proto tracing_filter_funcs[] = {
 		.arg1_type = ARG_CONST_MAP_PTR,
 		.arg2_type = ARG_PTR_TO_MAP_KEY,
 	},
+	[BPF_FUNC_ktime_get_ns] = {
+		.func = bpf_ktime_get_ns,
+		.gpl_only = true,
+		.ret_type = RET_INTEGER,
+	},
+	[BPF_FUNC_get_current] = {
+		.func = bpf_get_current,
+		.gpl_only = true,
+		.ret_type = RET_INTEGER,
+	},
 };
 
 static const struct bpf_func_proto *tracing_filter_func_proto(enum bpf_func_id func_id)
Signature · 1 line
1.7.9.5
#21 lore raw

RFC PATCH v7 21/28 samples: bpf: add mini eBPF library to manipulate maps and programs

In reply to Alexei Starovoitov

the library includes a trivial set of BPF syscall wrappers:

int bpf_create_map(int key_size, int value_size, int max_entries);

int bpf_update_elem(int fd, void *key, void *value);

int bpf_lookup_elem(int fd, void *key, void *value);

int bpf_delete_elem(int fd, void *key);

int bpf_get_next_key(int fd, void *key, void *next_key);

int bpf_prog_load(enum bpf_prog_type prog_type,

		  const struct sock_filter_int *insns, int insn_len,
		  const char *license);

bpf_prog_load() stores verifier log into global bpf_log_buf[] array

---
 samples/bpf/libbpf.c |   89 ++++++++++++++++++++++++++++++++++++++++++++++++++
 samples/bpf/libbpf.h |   21 ++++++++++++
 2 files changed, 110 insertions(+)
 create mode 100644 samples/bpf/libbpf.c
 create mode 100644 samples/bpf/libbpf.h
samples/bpf/libbpf.c new file +89 -0
new file mode 100644
index 000000000000..cae0c734274c
@@ -0,0 +1,89 @@
+/* eBPF mini library */
+#include <stdlib.h>
+#include <stdio.h>
+#include <linux/unistd.h>
+#include <unistd.h>
+#include <string.h>
+#include <linux/netlink.h>
+#include <linux/bpf.h>
+#include <errno.h>
+#include "libbpf.h"
+
+int bpf_create_map(enum bpf_map_type map_type, int key_size, int value_size,
+		   int max_entries)
+{
+	union bpf_attr attr = {
+		.map_type = map_type,
+		.key_size = key_size,
+		.value_size = value_size,
+		.max_entries = max_entries
+	};
+
+	return syscall(__NR_bpf, BPF_MAP_CREATE, &attr, sizeof(attr));
+}
+
+int bpf_update_elem(int fd, void *key, void *value)
+{
+	union bpf_attr attr = {
+		.map_fd = fd,
+		.key = key,
+		.value = value,
+	};
+
+	return syscall(__NR_bpf, BPF_MAP_UPDATE_ELEM, &attr, sizeof(attr));
+}
+
+int bpf_lookup_elem(int fd, void *key, void *value)
+{
+	union bpf_attr attr = {
+		.map_fd = fd,
+		.key = key,
+		.value = value,
+	};
+
+	return syscall(__NR_bpf, BPF_MAP_LOOKUP_ELEM, &attr, sizeof(attr));
+}
+
+int bpf_delete_elem(int fd, void *key)
+{
+	union bpf_attr attr = {
+		.map_fd = fd,
+		.key = key,
+	};
+
+	return syscall(__NR_bpf, BPF_MAP_DELETE_ELEM, &attr, sizeof(attr));
+}
+
+int bpf_get_next_key(int fd, void *key, void *next_key)
+{
+	union bpf_attr attr = {
+		.map_fd = fd,
+		.key = key,
+		.next_key = next_key,
+	};
+
+	return syscall(__NR_bpf, BPF_MAP_GET_NEXT_KEY, &attr, sizeof(attr));
+}
+
+#define ROUND_UP(x, n) (((x) + (n) - 1u) & ~((n) - 1u))
+
+char bpf_log_buf[LOG_BUF_SIZE];
+
+int bpf_prog_load(enum bpf_prog_type prog_type,
+		  const struct bpf_insn *insns, int prog_len,
+		  const char *license)
+{
+	union bpf_attr attr = {
+		.prog_type = prog_type,
+		.insns = insns,
+		.insn_cnt = prog_len / sizeof(struct bpf_insn),
+		.license = license,
+		.log_buf = bpf_log_buf,
+		.log_size = LOG_BUF_SIZE,
+		.log_level = 1,
+	};
+
+	bpf_log_buf[0] = 0;
+
+	return syscall(__NR_bpf, BPF_PROG_LOAD, &attr, sizeof(attr));
+}
samples/bpf/libbpf.h new file +21 -0
new file mode 100644
index 000000000000..b19e39794291
@@ -0,0 +1,21 @@
+/* eBPF mini library */
+#ifndef __LIBBPF_H
+#define __LIBBPF_H
+
+struct bpf_insn;
+
+int bpf_create_map(enum bpf_map_type map_type, int key_size, int value_size,
+		   int max_entries);
+int bpf_update_elem(int fd, void *key, void *value);
+int bpf_lookup_elem(int fd, void *key, void *value);
+int bpf_delete_elem(int fd, void *key);
+int bpf_get_next_key(int fd, void *key, void *next_key);
+
+int bpf_prog_load(enum bpf_prog_type prog_type,
+		  const struct bpf_insn *insns, int insn_len,
+		  const char *license);
+
+#define LOG_BUF_SIZE 8192
+extern char bpf_log_buf[LOG_BUF_SIZE];
+
+#endif
Signature · 1 line
1.7.9.5
#22 lore raw

RFC PATCH v7 22/28 samples: bpf: example of tracing filters with eBPF

In reply to Alexei Starovoitov

simple packet drop monitor:
- in-kernel eBPF program attaches to kfree_skb() event and records number of packet drops at given location
- userspace iterates over the map every second and prints stats

---
 samples/bpf/Makefile  |   12 +++++
 samples/bpf/dropmon.c |  122 +++++++++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 134 insertions(+)
 create mode 100644 samples/bpf/Makefile
 create mode 100644 samples/bpf/dropmon.c
samples/bpf/Makefile new file +12 -0
new file mode 100644
index 000000000000..8dfbacaef9ba
@@ -0,0 +1,12 @@
+# kbuild trick to avoid linker error. Can be omitted if a module is built.
+obj- := dummy.o
+
+# List of programs to build
+hostprogs-y := dropmon
+
+dropmon-objs := dropmon.o libbpf.o
+
+# Tell kbuild to always build the programs
+always := $(hostprogs-y)
+
+HOSTCFLAGS += -I$(objtree)/usr/include
samples/bpf/dropmon.c new file +122 -0

122 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#23 lore raw

RFC PATCH v7 23/28 bpf: verifier test

In reply to Alexei Starovoitov

verifier testsuite from user space. Tests valid and invalid programs and expects predefined error log messages from kernel.
42 tests so far.

$ sudo ./test_verifier
 #0 add+sub+mul OK
 #1 dropmon OK
 #2 dropmon with non-looping jump back OK
 #3 unreachable OK
 ...
 #40 access memory with incorrect alignment OK
 #41 sometimes access memory with incorrect alignment OK
---
 samples/bpf/Makefile        |    3 +-
 samples/bpf/test_verifier.c |  599 +++++++++++++++++++++++++++++++++++++++++++
 2 files changed, 601 insertions(+), 1 deletion(-)
 create mode 100644 samples/bpf/test_verifier.c
samples/bpf/Makefile +2 -1
index 8dfbacaef9ba..7264ba51d496 100644
@@ -2,9 +2,10 @@
 obj- := dummy.o
 
 # List of programs to build
-hostprogs-y := dropmon
+hostprogs-y := dropmon test_verifier
 
 dropmon-objs := dropmon.o libbpf.o
+test_verifier-objs := test_verifier.o libbpf.o
 
 # Tell kbuild to always build the programs
 always := $(hostprogs-y)
samples/bpf/test_verifier.c new file +599 -0

599 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#24 lore raw

RFC PATCH v7 24/28 bpf: llvm backend

In reply to Alexei Starovoitov

llvm backend that generated eBPF and emits either
binary ELF or human readable eBPF assembler

---
 tools/bpf/llvm/.gitignore                          |   54 ++
 tools/bpf/llvm/LICENSE.TXT                         |   70 ++
 tools/bpf/llvm/Makefile.rules                      |  641 ++++++++++++++++++
 tools/bpf/llvm/README.txt                          |   23 +
 tools/bpf/llvm/bld/Makefile                        |   27 +
 tools/bpf/llvm/bld/Makefile.common                 |   14 +
 tools/bpf/llvm/bld/Makefile.config                 |  124 ++++
 .../llvm/bld/include/llvm/Config/AsmParsers.def    |    8 +
 .../llvm/bld/include/llvm/Config/AsmPrinters.def   |    9 +
 .../llvm/bld/include/llvm/Config/Disassemblers.def |    8 +
 tools/bpf/llvm/bld/include/llvm/Config/Targets.def |    9 +
 .../bpf/llvm/bld/include/llvm/Support/DataTypes.h  |   96 +++
 tools/bpf/llvm/bld/lib/Makefile                    |   11 +
 .../llvm/bld/lib/Target/BPF/InstPrinter/Makefile   |   10 +
 .../llvm/bld/lib/Target/BPF/MCTargetDesc/Makefile  |   11 +
 tools/bpf/llvm/bld/lib/Target/BPF/Makefile         |   17 +
 .../llvm/bld/lib/Target/BPF/TargetInfo/Makefile    |   10 +
 tools/bpf/llvm/bld/lib/Target/Makefile             |   11 +
 tools/bpf/llvm/bld/tools/Makefile                  |   12 +
 tools/bpf/llvm/bld/tools/llc/Makefile              |   15 +
 tools/bpf/llvm/lib/Target/BPF/BPF.h                |   28 +
 tools/bpf/llvm/lib/Target/BPF/BPF.td               |   29 +
 tools/bpf/llvm/lib/Target/BPF/BPFAsmPrinter.cpp    |  100 +++
 tools/bpf/llvm/lib/Target/BPF/BPFCallingConv.td    |   24 +
 tools/bpf/llvm/lib/Target/BPF/BPFFrameLowering.cpp |   36 ++
 tools/bpf/llvm/lib/Target/BPF/BPFFrameLowering.h   |   35 +
 tools/bpf/llvm/lib/Target/BPF/BPFISelDAGToDAG.cpp  |  182 ++++++
 tools/bpf/llvm/lib/Target/BPF/BPFISelLowering.cpp  |  683 ++++++++++++++++++++
 tools/bpf/llvm/lib/Target/BPF/BPFISelLowering.h    |  105 +++
 tools/bpf/llvm/lib/Target/BPF/BPFInstrFormats.td   |   29 +
 tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.cpp     |  162 +++++
 tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.h       |   53 ++
 tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.td      |  498 ++++++++++++++
 tools/bpf/llvm/lib/Target/BPF/BPFMCInstLower.cpp   |   77 +++
 tools/bpf/llvm/lib/Target/BPF/BPFMCInstLower.h     |   40 ++
 tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.cpp  |  122 ++++
 tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.h    |   65 ++
 tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.td   |   39 ++
 tools/bpf/llvm/lib/Target/BPF/BPFSubtarget.cpp     |   23 +
 tools/bpf/llvm/lib/Target/BPF/BPFSubtarget.h       |   33 +
 tools/bpf/llvm/lib/Target/BPF/BPFTargetMachine.cpp |   66 ++
 tools/bpf/llvm/lib/Target/BPF/BPFTargetMachine.h   |   69 ++
 .../lib/Target/BPF/InstPrinter/BPFInstPrinter.cpp  |   81 +++
 .../lib/Target/BPF/InstPrinter/BPFInstPrinter.h    |   34 +
 .../lib/Target/BPF/MCTargetDesc/BPFAsmBackend.cpp  |   89 +++
 .../llvm/lib/Target/BPF/MCTargetDesc/BPFBaseInfo.h |   33 +
 .../Target/BPF/MCTargetDesc/BPFELFObjectWriter.cpp |   56 ++
 .../lib/Target/BPF/MCTargetDesc/BPFMCAsmInfo.h     |   34 +
 .../Target/BPF/MCTargetDesc/BPFMCCodeEmitter.cpp   |  167 +++++
 .../Target/BPF/MCTargetDesc/BPFMCTargetDesc.cpp    |  115 ++++
 .../lib/Target/BPF/MCTargetDesc/BPFMCTargetDesc.h  |   56 ++
 .../lib/Target/BPF/TargetInfo/BPFTargetInfo.cpp    |   13 +
 tools/bpf/llvm/tools/llc/llc.cpp                   |  381 +++++++++++
 53 files changed, 4737 insertions(+)
 create mode 100644 tools/bpf/llvm/.gitignore
 create mode 100644 tools/bpf/llvm/LICENSE.TXT
 create mode 100644 tools/bpf/llvm/Makefile.rules
 create mode 100644 tools/bpf/llvm/README.txt
 create mode 100644 tools/bpf/llvm/bld/Makefile
 create mode 100644 tools/bpf/llvm/bld/Makefile.common
 create mode 100644 tools/bpf/llvm/bld/Makefile.config
 create mode 100644 tools/bpf/llvm/bld/include/llvm/Config/AsmParsers.def
 create mode 100644 tools/bpf/llvm/bld/include/llvm/Config/AsmPrinters.def
 create mode 100644 tools/bpf/llvm/bld/include/llvm/Config/Disassemblers.def
 create mode 100644 tools/bpf/llvm/bld/include/llvm/Config/Targets.def
 create mode 100644 tools/bpf/llvm/bld/include/llvm/Support/DataTypes.h
 create mode 100644 tools/bpf/llvm/bld/lib/Makefile
 create mode 100644 tools/bpf/llvm/bld/lib/Target/BPF/InstPrinter/Makefile
 create mode 100644 tools/bpf/llvm/bld/lib/Target/BPF/MCTargetDesc/Makefile
 create mode 100644 tools/bpf/llvm/bld/lib/Target/BPF/Makefile
 create mode 100644 tools/bpf/llvm/bld/lib/Target/BPF/TargetInfo/Makefile
 create mode 100644 tools/bpf/llvm/bld/lib/Target/Makefile
 create mode 100644 tools/bpf/llvm/bld/tools/Makefile
 create mode 100644 tools/bpf/llvm/bld/tools/llc/Makefile
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPF.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPF.td
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFAsmPrinter.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFCallingConv.td
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFFrameLowering.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFFrameLowering.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFISelDAGToDAG.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFISelLowering.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFISelLowering.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFInstrFormats.td
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.td
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFMCInstLower.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFMCInstLower.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.td
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFSubtarget.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFSubtarget.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFTargetMachine.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/BPFTargetMachine.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/InstPrinter/BPFInstPrinter.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/InstPrinter/BPFInstPrinter.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFAsmBackend.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFBaseInfo.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFELFObjectWriter.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFMCAsmInfo.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFMCCodeEmitter.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFMCTargetDesc.cpp
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFMCTargetDesc.h
 create mode 100644 tools/bpf/llvm/lib/Target/BPF/TargetInfo/BPFTargetInfo.cpp
 create mode 100644 tools/bpf/llvm/tools/llc/llc.cpp
tools/bpf/llvm/.gitignore new file +54 -0
new file mode 100644
index 000000000000..7d6c5117e9a3
@@ -0,0 +1,54 @@
+#==============================================================================#
+# This file specifies intentionally untracked files that git should ignore.
+# See: http://www.kernel.org/pub/software/scm/git/docs/gitignore.html
+#
+# This file is intentionally different from the output of `git svn show-ignore`,
+# as most of those are useless.
+#==============================================================================#
+
+#==============================================================================#
+# File extensions to be ignored anywhere in the tree.
+#==============================================================================#
+# Temp files created by most text editors.
+*~
+# Merge files created by git.
+*.orig
+# Byte compiled python modules.
+*.pyc
+# vim swap files
+.*.swp
+*.inc
+Debug+Asserts
+Release+Asserts
+
+#==============================================================================#
+# Explicit files to ignore (only matches one).
+#==============================================================================#
+.cproject
+.gitusers
+.project
+autom4te.cache
+cscope.files
+cscope.out
+autoconf/aclocal.m4
+autoconf/autom4te.cache
+compile_commands.json
+
+#==============================================================================#
+# Directories to ignore (do not add trailing '/'s, they skip symlinks).
+#==============================================================================#
+# External projects that are tracked independently.
+projects/*
+!projects/sample
+!projects/CMakeLists.txt
+!projects/Makefile
+# Clang, which is tracked independently.
+tools/clang
+# LLDB, which is tracked independently.
+tools/lldb
+# lld, which is tracked independently.
+tools/lld
+# Sphinx build tree, if building in-source dir.
+docs/_build
+# build directory
+build
tools/bpf/llvm/LICENSE.TXT new file +70 -0

70 lines not on this page · raw message

tools/bpf/llvm/Makefile.rules new file +641 -0

641 lines not on this page · raw message

tools/bpf/llvm/README.txt new file +23 -0
new file mode 100644
index 000000000000..971207b33ff7
@@ -0,0 +1,23 @@
+LLVM BPF backend:
+lib/Target/BPF/*.cpp
+
+Links with LLVM 3.2, 3.3 and 3.4
+
+prerequisites:
+apt-get install clang llvm-3.[234]-dev
+
+To build:
+$cd bld
+$make
+if 'llvm-config-3.2' is not found in PATH, build with:
+$make -j4 LLVM_CONFIG=/path_to/llvm-config
+
+To run:
+$clang -O2 -emit-llvm -c file.c -o -|./bld/Debug+Asserts/bin/llc -o file.o
+
+'clang' - is unmodified clang used to build x86 code
+'llc' - llvm bit-code to BPF compiler
+file.o - BPF binary image, see include/uapi/linux/bpf.h
+
+$clang -O2 -emit-llvm -c file.c -o -|llc -filetype=asm -o file.s
+will emit human readable BPF assembler instead.
tools/bpf/llvm/bld/Makefile new file +27 -0
new file mode 100644
index 000000000000..7ac0938906f6
@@ -0,0 +1,27 @@
+#===- ./Makefile -------------------------------------------*- Makefile -*--===#
+#
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+
+ifndef LLVM_CONFIG
+LLVM_CONFIG := llvm-config-3.2
+export LLVM_CONFIG
+endif
+
+LEVEL := .
+
+DIRS := lib tools
+
+include $(LEVEL)/Makefile.config
+
+# Include the main makefile machinery.
+include $(LLVM_SRC_ROOT)/Makefile.rules
+
+# NOTE: This needs to remain as the last target definition in this file so
+# that it gets executed last.
+all::
+	$(Echo) '*****' Completed $(BuildMode) Build
+
+# declare all targets at this level to be serial:
+.NOTPARALLEL:
+
tools/bpf/llvm/bld/Makefile.common new file +14 -0
new file mode 100644
index 000000000000..624f7d3096a5
@@ -0,0 +1,14 @@
+#===-- Makefile.common - Common make rules for LLVM --------*- Makefile -*--===#
+#
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+
+# Configuration file to set paths specific to local installation of LLVM
+ifndef LLVM_OBJ_ROOT
+include $(LEVEL)/Makefile.config
+else
+include $(LLVM_OBJ_ROOT)/Makefile.config
+endif
+
+# Include all of the build rules used for making LLVM
+include $(LLVM_SRC_ROOT)/Makefile.rules
tools/bpf/llvm/bld/Makefile.config new file +124 -0

124 lines not on this page · raw message

tools/bpf/llvm/bld/include/llvm/Config/AsmParsers.def new file +8 -0
new file mode 100644
index 000000000000..9efd8f45526c
@@ -0,0 +1,8 @@
+/*===- llvm/Config/AsmParsers.def - LLVM Assembly Parsers -------*- C++ -*-===*\
+|* This file is distributed under the University of Illinois Open Source      *|
+|* License. See LICENSE.TXT for details.                                      *|
+\*===----------------------------------------------------------------------===*/
+#ifndef LLVM_ASM_PARSER
+#  error Please define the macro LLVM_ASM_PARSER(TargetName)
+#endif
+#undef LLVM_ASM_PARSER
tools/bpf/llvm/bld/include/llvm/Config/AsmPrinters.def new file +9 -0
new file mode 100644
index 000000000000..f212afa62b37
@@ -0,0 +1,9 @@
+/*===- llvm/Config/AsmPrinters.def - LLVM Assembly Printers -----*- C++ -*-===*\
+|* This file is distributed under the University of Illinois Open Source      *|
+|* License. See LICENSE.TXT for details.                                      *|
+\*===----------------------------------------------------------------------===*/
+#ifndef LLVM_ASM_PRINTER
+#  error Please define the macro LLVM_ASM_PRINTER(TargetName)
+#endif
+LLVM_ASM_PRINTER(BPF) 
+#undef LLVM_ASM_PRINTER
tools/bpf/llvm/bld/include/llvm/Config/Disassemblers.def new file +8 -0
new file mode 100644
index 000000000000..527473fb24e5
@@ -0,0 +1,8 @@
+/*===- llvm/Config/Disassemblers.def - LLVM Assembly Parsers ----*- C++ -*-===*\
+|* This file is distributed under the University of Illinois Open Source      *|
+|* License. See LICENSE.TXT for details.                                      *|
+\*===----------------------------------------------------------------------===*/
+#ifndef LLVM_DISASSEMBLER
+#  error Please define the macro LLVM_DISASSEMBLER(TargetName)
+#endif
+#undef LLVM_DISASSEMBLER
tools/bpf/llvm/bld/include/llvm/Config/Targets.def new file +9 -0
new file mode 100644
index 000000000000..cb2852cb19cf
@@ -0,0 +1,9 @@
+/*===- llvm/Config/Targets.def - LLVM Target Architectures ------*- C++ -*-===*\
+|* This file is distributed under the University of Illinois Open Source      *|
+|* License. See LICENSE.TXT for details.                                      *|
+\*===----------------------------------------------------------------------===*/
+#ifndef LLVM_TARGET
+#  error Please define the macro LLVM_TARGET(TargetName)
+#endif
+LLVM_TARGET(BPF) 
+#undef LLVM_TARGET
tools/bpf/llvm/bld/include/llvm/Support/DataTypes.h new file +96 -0

96 lines not on this page · raw message

tools/bpf/llvm/bld/lib/Makefile new file +11 -0
new file mode 100644
index 000000000000..5c7e219ad9bf
@@ -0,0 +1,11 @@
+##===- lib/Makefile ----------------------------------------*- Makefile -*-===##
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+LEVEL = ..
+
+include $(LEVEL)/Makefile.config
+
+PARALLEL_DIRS := Target
+
+include $(LEVEL)/Makefile.common
+
tools/bpf/llvm/bld/lib/Target/BPF/InstPrinter/Makefile new file +10 -0
new file mode 100644
index 000000000000..d9a4522d4320
@@ -0,0 +1,10 @@
+##===- lib/Target/BPF/InstPrinter/Makefile ----------------*- Makefile -*-===##
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+LEVEL = ../../../..
+LIBRARYNAME = LLVMBPFAsmPrinter
+
+# Hack: we need to include 'main' BPF target directory to grab private headers
+CPP.Flags += -I$(PROJ_OBJ_DIR)/.. -I$(PROJ_SRC_DIR)/..
+
+include $(LEVEL)/Makefile.common
tools/bpf/llvm/bld/lib/Target/BPF/MCTargetDesc/Makefile new file +11 -0
new file mode 100644
index 000000000000..5f2e2090d449
@@ -0,0 +1,11 @@
+##===- lib/Target/BPF/TargetDesc/Makefile ----------------*- Makefile -*-===##
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+
+LEVEL = ../../../..
+LIBRARYNAME = LLVMBPFDesc
+
+# Hack: we need to include 'main' target directory to grab private headers
+CPP.Flags += -I$(PROJ_OBJ_DIR)/.. -I$(PROJ_SRC_DIR)/..
+
+include $(LEVEL)/Makefile.common
tools/bpf/llvm/bld/lib/Target/BPF/Makefile new file +17 -0
new file mode 100644
index 000000000000..14dea1a3851b
@@ -0,0 +1,17 @@
+##===- lib/Target/BPF/Makefile ---------------------------*- Makefile -*-===##
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+
+LEVEL = ../../..
+LIBRARYNAME = LLVMBPFCodeGen
+TARGET = BPF
+
+# Make sure that tblgen is run, first thing.
+BUILT_SOURCES = BPFGenRegisterInfo.inc BPFGenInstrInfo.inc \
+		BPFGenAsmWriter.inc BPFGenAsmMatcher.inc BPFGenDAGISel.inc \
+		BPFGenMCCodeEmitter.inc BPFGenSubtargetInfo.inc BPFGenCallingConv.inc
+
+DIRS = InstPrinter TargetInfo MCTargetDesc
+
+include $(LEVEL)/Makefile.common
+
tools/bpf/llvm/bld/lib/Target/BPF/TargetInfo/Makefile new file +10 -0
new file mode 100644
index 000000000000..fdf9056d37f6
@@ -0,0 +1,10 @@
+##===- lib/Target/BPF/TargetInfo/Makefile ----------------*- Makefile -*-===##
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+LEVEL = ../../../..
+LIBRARYNAME = LLVMBPFInfo
+
+# Hack: we need to include 'main' target directory to grab private headers
+CPPFLAGS = -I$(PROJ_OBJ_DIR)/.. -I$(PROJ_SRC_DIR)/..
+
+include $(LEVEL)/Makefile.common
tools/bpf/llvm/bld/lib/Target/Makefile new file +11 -0
new file mode 100644
index 000000000000..06e518533407
@@ -0,0 +1,11 @@
+#===- lib/Target/Makefile ----------------------------------*- Makefile -*-===##
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+
+LEVEL = ../..
+
+include $(LEVEL)/Makefile.config
+
+PARALLEL_DIRS := $(TARGETS_TO_BUILD)
+
+include $(LLVM_SRC_ROOT)/Makefile.rules
tools/bpf/llvm/bld/tools/Makefile new file +12 -0
new file mode 100644
index 000000000000..6613681389d5
@@ -0,0 +1,12 @@
+##===- tools/Makefile --------------------------------------*- Makefile -*-===##
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+
+LEVEL := ..
+
+include $(LEVEL)/Makefile.config
+
+DIRS :=
+PARALLEL_DIRS := llc
+
+include $(LEVEL)/Makefile.common
tools/bpf/llvm/bld/tools/llc/Makefile new file +15 -0
new file mode 100644
index 000000000000..499feb0ac113
@@ -0,0 +1,15 @@
+#===- tools/llc/Makefile -----------------------------------*- Makefile -*-===##
+# This file is distributed under the University of Illinois Open Source
+# License. See LICENSE.TXT for details.
+
+LEVEL := ../..
+TOOLNAME := llc
+ifneq (,$(filter $(shell $(LLVM_CONFIG) --version),3.3 3.4))
+LINK_COMPONENTS := asmparser asmprinter codegen bitreader core mc selectiondag support target irreader
+else
+LINK_COMPONENTS := asmparser asmprinter codegen bitreader core mc selectiondag support target
+endif
+USEDLIBS := LLVMBPFCodeGen.a LLVMBPFDesc.a LLVMBPFInfo.a LLVMBPFAsmPrinter.a
+
+include $(LEVEL)/Makefile.common
+
tools/bpf/llvm/lib/Target/BPF/BPF.h new file +28 -0
new file mode 100644
index 000000000000..53fe49a9c4ea
@@ -0,0 +1,28 @@
+//===-- BPF.h - Top-level interface for BPF representation ----*- C++ -*-===//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+
+#ifndef TARGET_BPF_H
+#define TARGET_BPF_H
+#include "llvm/Config/config.h"
+#undef LLVM_NATIVE_TARGET
+#undef LLVM_NATIVE_ASMPRINTER
+#undef LLVM_NATIVE_ASMPARSER
+#undef LLVM_NATIVE_DISASSEMBLER
+#include "MCTargetDesc/BPFBaseInfo.h"
+#include "MCTargetDesc/BPFMCTargetDesc.h"
+#include "llvm/Target/TargetMachine.h"
+
+namespace llvm {
+class FunctionPass;
+class TargetMachine;
+class BPFTargetMachine;
+
+/// createBPFISelDag - This pass converts a legalized DAG into a
+/// BPF-specific DAG, ready for instruction scheduling.
+FunctionPass *createBPFISelDag(BPFTargetMachine &TM);
+
+extern Target TheBPFTarget;
+}
+
+#endif
tools/bpf/llvm/lib/Target/BPF/BPF.td new file +29 -0
new file mode 100644
index 000000000000..867c7f8134de
@@ -0,0 +1,29 @@
+//===- BPF.td - Describe the BPF Target Machine --------*- tablegen -*-===//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+
+// Target-independent interfaces which we are implementing
+include "llvm/Target/Target.td"
+
+// BPF Subtarget features.
+include "BPFRegisterInfo.td"
+include "BPFCallingConv.td"
+include "BPFInstrInfo.td"
+
+def BPFInstrInfo : InstrInfo;
+
+class Proc<string Name, list<SubtargetFeature> Features>
+ : Processor<Name, NoItineraries, Features>;
+
+def : Proc<"generic", []>;
+
+def BPFInstPrinter : AsmWriter {
+  string AsmWriterClassName  = "InstPrinter";
+  bit isMCAsmWriter = 1;
+}
+
+// Declare the target which we are implementing
+def BPF : Target {
+  let InstructionSet = BPFInstrInfo;
+  let AssemblyWriters = [BPFInstPrinter];
+}
tools/bpf/llvm/lib/Target/BPF/BPFAsmPrinter.cpp new file +100 -0

100 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/BPFCallingConv.td new file +24 -0
new file mode 100644
index 000000000000..27c327e5f5e9
@@ -0,0 +1,24 @@
+//===- BPFCallingConv.td - Calling Conventions BPF -------*- tablegen -*-===//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+// This describes the calling conventions for the BPF architectures.
+
+// BPF 64-bit C return-value convention.
+def RetCC_BPF64 : CallingConv<[
+  CCIfType<[i64], CCAssignToReg<[R0]>>
+]>;
+
+// BPF 64-bit C Calling convention.
+def CC_BPF64 : CallingConv<[
+  // Promote i8/i16/i32 args to i64
+  CCIfType<[i8, i16, i32], CCPromoteToType<i64>>,
+
+  // All arguments get passed in integer registers if there is space.
+  CCIfType<[i64], CCAssignToReg<[R1, R2, R3, R4, R5]>>,
+
+  // Alternatively, they are assigned to the stack in 8-byte aligned units.
+  CCAssignToStack<8, 8>
+]>;
+
+def CSR: CalleeSavedRegs<(add R6, R7, R8, R9, R10)>;
tools/bpf/llvm/lib/Target/BPF/BPFFrameLowering.cpp new file +36 -0
new file mode 100644
index 000000000000..b263b5fd0494
@@ -0,0 +1,36 @@
+//===-- BPFFrameLowering.cpp - BPF Frame Information --------------------===//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+//
+// This file contains the BPF implementation of TargetFrameLowering class.
+
+#include "BPFFrameLowering.h"
+#include "BPFInstrInfo.h"
+#include "llvm/CodeGen/MachineFrameInfo.h"
+#include "llvm/CodeGen/MachineFunction.h"
+#include "llvm/CodeGen/MachineInstrBuilder.h"
+#include "llvm/CodeGen/MachineRegisterInfo.h"
+
+using namespace llvm;
+
+bool BPFFrameLowering::hasFP(const MachineFunction &MF) const {
+  return true;
+}
+
+void BPFFrameLowering::emitPrologue(MachineFunction &MF) const {
+}
+
+void BPFFrameLowering::emitEpilogue(MachineFunction &MF,
+                                    MachineBasicBlock &MBB) const {
+}
+
+void BPFFrameLowering::
+processFunctionBeforeCalleeSavedScan(MachineFunction &MF,
+                                     RegScavenger *RS) const {
+  MachineRegisterInfo& MRI = MF.getRegInfo();
+
+  MRI.setPhysRegUnused(BPF::R6);
+  MRI.setPhysRegUnused(BPF::R7);
+  MRI.setPhysRegUnused(BPF::R8);
+  MRI.setPhysRegUnused(BPF::R9);
+}
tools/bpf/llvm/lib/Target/BPF/BPFFrameLowering.h new file +35 -0
new file mode 100644
index 000000000000..3e3d9adb8dc9
@@ -0,0 +1,35 @@
+//===-- BPFFrameLowering.h - Define frame lowering for BPF ---*- C++ -*--===//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+
+#ifndef BPF_FRAMEINFO_H
+#define BPF_FRAMEINFO_H
+
+#include "BPF.h"
+#include "BPFSubtarget.h"
+#include "llvm/Target/TargetFrameLowering.h"
+
+namespace llvm {
+class BPFSubtarget;
+
+class BPFFrameLowering : public TargetFrameLowering {
+public:
+  explicit BPFFrameLowering(const BPFSubtarget &sti)
+    : TargetFrameLowering(TargetFrameLowering::StackGrowsDown, 8, 0) {
+  }
+
+  void emitPrologue(MachineFunction &MF) const;
+  void emitEpilogue(MachineFunction &MF, MachineBasicBlock &MBB) const;
+
+  bool hasFP(const MachineFunction &MF) const;
+  virtual void processFunctionBeforeCalleeSavedScan(MachineFunction &MF,
+                                                    RegScavenger *RS) const;
+
+  // llvm 3.3 defines it here
+  void eliminateCallFramePseudoInstr(MachineFunction &MF, MachineBasicBlock &MBB,
+                                     MachineBasicBlock::iterator MI) const {
+    MBB.erase(MI);
+  }
+};
+}
+#endif
tools/bpf/llvm/lib/Target/BPF/BPFISelDAGToDAG.cpp new file +182 -0

182 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/BPFISelLowering.cpp new file +683 -0

683 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/BPFISelLowering.h new file +105 -0

105 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/BPFInstrFormats.td new file +29 -0
new file mode 100644
index 000000000000..122ff19e8562
@@ -0,0 +1,29 @@
+//===- BPFInstrFormats.td - BPF Instruction Formats ----*- tablegen -*-===//
+// This file is distributed under the University of Illinois Open Source
+// License. See LICENSE.TXT for details.
+
+class InstBPF<dag outs, dag ins, string asmstr, list<dag> pattern>
+  : Instruction {
+  field bits<64> Inst;
+  field bits<64> SoftFail = 0;
+  let Size = 8;
+
+  let Namespace = "BPF";
+  let DecoderNamespace = "BPF";
+
+  bits<3> bpfClass;
+  let Inst{58-56} = bpfClass;
+
+  dag OutOperandList = outs;
+  dag InOperandList = ins;
+  let AsmString = asmstr;
+  let Pattern = pattern;
+}
+
+// Pseudo instructions
+class Pseudo<dag outs, dag ins, string asmstr, list<dag> pattern>
+  : InstBPF<outs, ins, asmstr, pattern> {
+  let Inst{63-0} = 0;
+  let isPseudo = 1;
+}
+
tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.cpp new file +162 -0

162 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.h new file +53 -0

53 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/BPFInstrInfo.td new file +498 -0

354 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/BPFMCInstLower.cpp new file +77 -0

77 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/BPFMCInstLower.h new file +40 -0
new file mode 100644
index 000000000000..aaff0c3e8a68

Lines of this file are not shown. View the raw message.

tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.cpp new file +122 -0

122 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.h new file +65 -0

65 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/BPFRegisterInfo.td new file +39 -0
new file mode 100644
index 000000000000..fac081788be1

Lines of this file are not shown. View the raw message.

tools/bpf/llvm/lib/Target/BPF/BPFSubtarget.cpp new file +23 -0
new file mode 100644
index 000000000000..6e98f6d1a514

Lines of this file are not shown. View the raw message.

tools/bpf/llvm/lib/Target/BPF/BPFSubtarget.h new file +33 -0
new file mode 100644
index 000000000000..cd5d8759c20f

Lines of this file are not shown. View the raw message.

tools/bpf/llvm/lib/Target/BPF/BPFTargetMachine.cpp new file +66 -0

66 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/BPFTargetMachine.h new file +69 -0

69 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/InstPrinter/BPFInstPrinter.cpp new file +81 -0

81 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/InstPrinter/BPFInstPrinter.h new file +34 -0
new file mode 100644
index 000000000000..77dd30dca040

Lines of this file are not shown. View the raw message.

tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFAsmBackend.cpp new file +89 -0

89 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFBaseInfo.h new file +33 -0
new file mode 100644
index 000000000000..9d03073668da

Lines of this file are not shown. View the raw message.

tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFELFObjectWriter.cpp new file +56 -0

56 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFMCAsmInfo.h new file +34 -0
new file mode 100644
index 000000000000..99132ee9230c

Lines of this file are not shown. View the raw message.

tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFMCCodeEmitter.cpp new file +167 -0

167 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFMCTargetDesc.cpp new file +115 -0

115 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/MCTargetDesc/BPFMCTargetDesc.h new file +56 -0

56 lines not on this page · raw message

tools/bpf/llvm/lib/Target/BPF/TargetInfo/BPFTargetInfo.cpp new file +13 -0
new file mode 100644
index 000000000000..4d16305e2b86

Lines of this file are not shown. View the raw message.

tools/bpf/llvm/tools/llc/llc.cpp new file +381 -0

381 lines not on this page · raw message

The rest of this diff is not shown. View the raw message.

Signature · 1 line
1.7.9.5

Part of the diff is not shown here. View the raw message.

#25 lore raw

RFC PATCH v7 25/28 samples: bpf: elf file loader

In reply to Alexei Starovoitov

simple .o parser and loader using BPF syscall.
.o is a standard ELF generated by LLVM backend

It parses elf file compiled by llvm .c->.o
- parses 'maps' section and creates maps via BPF syscall
- parses 'license' section and passes it to syscall
- parses elf relocations for BPF maps and adjusts BPF_LD_IMM64 insns by storing map_fd into insn->imm and marking such insns as BPF_PSEUDO_MAP_FD
- loads eBPF program via BPF syscall
- attaches program FD to tracepoint events

One ELF file can contain multiple BPF programs attached to multiple tracepoint events

int load_bpf_file(char *path);

bpf_helpers.h is a set of in-kernel helper functions available to eBPF programs

---
 samples/bpf/bpf_helpers.h |   27 ++++++
 samples/bpf/bpf_load.c    |  234 +++++++++++++++++++++++++++++++++++++++++++++
 samples/bpf/bpf_load.h    |   26 +++++
 3 files changed, 287 insertions(+)
 create mode 100644 samples/bpf/bpf_helpers.h
 create mode 100644 samples/bpf/bpf_load.c
 create mode 100644 samples/bpf/bpf_load.h
samples/bpf/bpf_helpers.h new file +27 -0
new file mode 100644
index 000000000000..08752fad472d
@@ -0,0 +1,27 @@
+#ifndef __BPF_HELPERS_H
+#define __BPF_HELPERS_H
+
+#define SEC(NAME) __attribute__((section(NAME), used))
+
+static void *(*bpf_fetch_ptr)(void *unsafe_ptr) = (void *) BPF_FUNC_fetch_ptr;
+static unsigned long long (*bpf_fetch_u64)(void *unsafe_ptr) = (void *) BPF_FUNC_fetch_u64;
+static unsigned int (*bpf_fetch_u32)(void *unsafe_ptr) = (void *) BPF_FUNC_fetch_u32;
+static unsigned short (*bpf_fetch_u16)(void *unsafe_ptr) = (void *) BPF_FUNC_fetch_u16;
+static unsigned char (*bpf_fetch_u8)(void *unsafe_ptr) = (void *) BPF_FUNC_fetch_u8;
+static int (*bpf_printk)(const char *fmt, int fmt_size, ...) = (void *) BPF_FUNC_printk;
+static int (*bpf_memcmp)(void *unsafe_ptr, void *safe_ptr, int size) = (void *) BPF_FUNC_memcmp;
+static void *(*bpf_map_lookup_elem)(void *map, void *key) = (void*) BPF_FUNC_map_lookup_elem;
+static int (*bpf_map_update_elem)(void *map, void *key, void *value) = (void*) BPF_FUNC_map_update_elem;
+static int (*bpf_map_delete_elem)(void *map, void *key) = (void *) BPF_FUNC_map_delete_elem;
+static void (*bpf_dump_stack)(void) = (void *) BPF_FUNC_dump_stack;
+static unsigned long long (*bpf_ktime_get_ns)(void) = (void *) BPF_FUNC_ktime_get_ns;
+static void *(*bpf_get_current)(void) = (void *) BPF_FUNC_get_current;
+
+struct bpf_map_def {
+	int type;
+	int key_size;
+	int value_size;
+	int max_entries;
+};
+
+#endif
samples/bpf/bpf_load.c new file +234 -0

234 lines not on this page · raw message

samples/bpf/bpf_load.h new file +26 -0
new file mode 100644
index 000000000000..209190d793ff
@@ -0,0 +1,26 @@
+#ifndef __BPF_LOAD_H
+#define __BPF_LOAD_H
+
+#define MAX_MAPS 64
+
+extern int map_fd[MAX_MAPS];
+
+/* parses elf file compiled by llvm .c->.o
+ * . parses 'maps' section and creates maps via BPF syscall
+ * . parses 'license' section and passes it to syscall
+ * . parses elf relocations for BPF maps and adjusts BPF_LD_IMM64 insns by
+ *   storing map_fd into insn->imm and marking such insns as BPF_PSEUDO_MAP_FD
+ * . loads eBPF program via BPF syscall
+ * . attaches program FD to tracepoint events
+ *
+ * One ELF file can contain multiple BPF programs attached to multiple
+ * tracepoint events
+ *
+ * returns zero on success
+ */
+int load_bpf_file(char *path);
+
+/* forever reads /sys/.../trace_pipe */
+void read_trace_pipe(void);
+
+#endif
Signature · 1 line
1.7.9.5
#26 lore raw

RFC PATCH v7 26/28 samples: bpf: eBPF example in C

In reply to Alexei Starovoitov

ex1_kern.c - C program which will be compiled into eBPF to filter netif_receive_skb events on skb->dev->name == "lo"

ex1_user.c - corresponding user space component that forever reads /sys/.../trace_pipe

Usage:

$ sudo ex1

should see:
writing bpf-4 -> /sys/kernel/debug/tracing/events/net/netif_receive_skb/filter
ping-25476 [001] ..s3 5639.718218: __netif_receive_skb_core: skb 4d51700 dev b9e6000 ping-25476 [001] ..s3 5639.718262: __netif_receive_skb_core: skb 4d51400 dev b9e6000

ping-25476 [002] ..s3 5640.716233: __netif_receive_skb_core: skb 5d06500 dev b9e6000 ping-25476 [002] ..s3 5640.716272: __netif_receive_skb_core: skb 5d06300 dev b9e6000

Ctrl-C at any time, kernel will auto cleanup

---
 samples/bpf/Makefile   |   15 +++++++++++++--
 samples/bpf/ex1_kern.c |   27 +++++++++++++++++++++++++++
 samples/bpf/ex1_user.c |   24 ++++++++++++++++++++++++
 3 files changed, 64 insertions(+), 2 deletions(-)
 create mode 100644 samples/bpf/ex1_kern.c
 create mode 100644 samples/bpf/ex1_user.c
samples/bpf/Makefile +13 -2
index 7264ba51d496..7ce9e6b0d3d0 100644
@@ -2,12 +2,23 @@
 obj- := dummy.o
 
 # List of programs to build
-hostprogs-y := dropmon test_verifier
+hostprogs-y := dropmon test_verifier ex1
 
 dropmon-objs := dropmon.o libbpf.o
 test_verifier-objs := test_verifier.o libbpf.o
+ex1-objs := bpf_load.o libbpf.o ex1_user.o
 
 # Tell kbuild to always build the programs
-always := $(hostprogs-y)
+always := $(hostprogs-y) ex1_kern.o
 
 HOSTCFLAGS += -I$(objtree)/usr/include
+
+HOSTCFLAGS_bpf_load.o += -I$(objtree)/usr/include -Wno-unused-variable
+HOSTLOADLIBES_ex1 += -lelf
+
+LLC=$(srctree)/tools/bpf/llvm/bld/Debug+Asserts/bin/llc
+
+%.o: %.c
+	clang $(NOSTDINC_FLAGS) $(LINUXINCLUDE) $(EXTRA_CFLAGS) \
+		-D__KERNEL__ -Wno-unused-value -Wno-pointer-sign \
+		-O2 -emit-llvm -c $< -o -| $(LLC) -o $@
samples/bpf/ex1_kern.c new file +27 -0
new file mode 100644
index 000000000000..05a06cccaadb
@@ -0,0 +1,27 @@
+#include <linux/skbuff.h>
+#include <linux/netdevice.h>
+#include <uapi/linux/bpf.h>
+#include <trace/bpf_trace.h>
+#include "bpf_helpers.h"
+
+SEC("events/net/netif_receive_skb")
+int bpf_prog1(struct bpf_context *ctx)
+{
+	/*
+	 * attaches to /sys/kernel/debug/tracing/events/net/netif_receive_skb
+	 * prints events for loobpack device only
+	 */
+	char devname[] = "lo";
+	struct net_device *dev;
+	struct sk_buff *skb = 0;
+
+	skb = (struct sk_buff *) ctx->arg1;
+	dev = bpf_fetch_ptr(&skb->dev);
+	if (bpf_memcmp(dev->name, devname, 2) == 0) {
+		char fmt[] = "skb %x dev %x\n";
+		bpf_printk(fmt, sizeof(fmt), skb, dev);
+	}
+	return 0;
+}
+
+char license[] SEC("license") = "GPL";
samples/bpf/ex1_user.c new file +24 -0
new file mode 100644
index 000000000000..e85c1b483f57
@@ -0,0 +1,24 @@
+#include <stdio.h>
+#include <linux/bpf.h>
+#include "libbpf.h"
+#include "bpf_load.h"
+
+int main(int ac, char **argv)
+{
+	FILE *f;
+	char filename[256];
+
+	snprintf(filename, sizeof(filename), "%s_kern.o", argv[0]);
+
+	if (load_bpf_file(filename)) {
+		printf("%s", bpf_log_buf);
+		return 1;
+	}
+
+	f = popen("ping -c5 localhost", "r");
+	(void) f;
+
+	read_trace_pipe();
+
+	return 0;
+}
Signature · 1 line
1.7.9.5
#27 lore raw

RFC PATCH v7 27/28 samples: bpf: counting eBPF example in C

In reply to Alexei Starovoitov

this example has two probes in C that use two different maps.

1st probe is the similar to dropmon.c. It attaches to kfree_skb tracepoint and count number of packet drops at different locations

2nd probe attaches to kprobe/sys_write and computes a histogram of different write sizes

Usage:

$ sudo ex2

Should see:
writing bpf-5 -> /sys/kernel/debug/tracing/events/skb/kfree_skb/filter writing bpf-8 -> /sys/kernel/debug/tracing/events/kprobes/sys_write/filter location 0xffffffff816efc67 count 1

location 0xffffffff815d8030 count 1
location 0xffffffff816efc67 count 3

location 0xffffffff815d8030 count 4
location 0xffffffff816efc67 count 9

           syscall write() stats
     byte_size       : count     distribution
       1 -> 1        : 3141     |****                                  |
       2 -> 3        : 2        |                                      |
       4 -> 7        : 14       |                                      |
       8 -> 15       : 3268     |*****                                 |
      16 -> 31       : 732      |                                      |
      32 -> 63       : 20042    |************************************* |
      64 -> 127      : 12154    |**********************                |
     128 -> 255      : 2215     |***                                   |
     256 -> 511      : 9        |                                      |
     512 -> 1023     : 0        |                                      |
    1024 -> 2047     : 1        |                                      |

Ctrl-C at any time. Kernel will auto cleanup maps and programs

---
 samples/bpf/Makefile   |    6 ++--
 samples/bpf/ex2_kern.c |   73 +++++++++++++++++++++++++++++++++++++
 samples/bpf/ex2_user.c |   94 ++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 171 insertions(+), 2 deletions(-)
 create mode 100644 samples/bpf/ex2_kern.c
 create mode 100644 samples/bpf/ex2_user.c
samples/bpf/Makefile +4 -2
index 7ce9e6b0d3d0..d2de86188925 100644
@@ -2,19 +2,21 @@
 obj- := dummy.o
 
 # List of programs to build
-hostprogs-y := dropmon test_verifier ex1
+hostprogs-y := dropmon test_verifier ex1 ex2
 
 dropmon-objs := dropmon.o libbpf.o
 test_verifier-objs := test_verifier.o libbpf.o
 ex1-objs := bpf_load.o libbpf.o ex1_user.o
+ex2-objs := bpf_load.o libbpf.o ex2_user.o
 
 # Tell kbuild to always build the programs
-always := $(hostprogs-y) ex1_kern.o
+always := $(hostprogs-y) ex1_kern.o ex2_kern.o
 
 HOSTCFLAGS += -I$(objtree)/usr/include
 
 HOSTCFLAGS_bpf_load.o += -I$(objtree)/usr/include -Wno-unused-variable
 HOSTLOADLIBES_ex1 += -lelf
+HOSTLOADLIBES_ex2 += -lelf
 
 LLC=$(srctree)/tools/bpf/llvm/bld/Debug+Asserts/bin/llc
 
samples/bpf/ex2_kern.c new file +73 -0

73 lines not on this page · raw message

samples/bpf/ex2_user.c new file +94 -0

94 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#28 lore raw

RFC PATCH v7 28/28 samples: bpf: IO latency analysis (iosnoop/heatmap)

In reply to Alexei Starovoitov

eBPF C program attaches to block_rq_issue/block_rq_complete events to calculate IO latency. Then it waits for the first 100 events to compute average latency and uses range [0 .. ave_lat * 2] to record histogram of events in this latency range.
User space reads this histogram map every 2 seconds and prints it as a 'heatmap' using gray shades of text terminal. Black spaces have many events and white spaces have very few events. Left most space is the smallest latency, right most space is the largest latency in the range.
If kernel sees too many events that fall out of histogram range, user space adjusts the range up, so heatmap for next 2 seconds will be more accurate.

Usage:

$ sudo ./ex3
and do 'sudo dd if=/dev/sda of=/dev/null' in other terminal.
Observe IO latencies and how different activity (like 'make kernel') affects it.

Similar experiments can be done for network transmit latencies, syscalls, etc

---
 samples/bpf/Makefile   |    6 +-
 samples/bpf/ex3_kern.c |  104 +++++++++++++++++++++++++++++++++
 samples/bpf/ex3_user.c |  149 ++++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 257 insertions(+), 2 deletions(-)
 create mode 100644 samples/bpf/ex3_kern.c
 create mode 100644 samples/bpf/ex3_user.c
samples/bpf/Makefile +4 -2
index d2de86188925..9e7a9bc2194d 100644
@@ -2,21 +2,23 @@
 obj- := dummy.o
 
 # List of programs to build
-hostprogs-y := dropmon test_verifier ex1 ex2
+hostprogs-y := dropmon test_verifier ex1 ex2 ex3
 
 dropmon-objs := dropmon.o libbpf.o
 test_verifier-objs := test_verifier.o libbpf.o
 ex1-objs := bpf_load.o libbpf.o ex1_user.o
 ex2-objs := bpf_load.o libbpf.o ex2_user.o
+ex3-objs := bpf_load.o libbpf.o ex3_user.o
 
 # Tell kbuild to always build the programs
-always := $(hostprogs-y) ex1_kern.o ex2_kern.o
+always := $(hostprogs-y) ex1_kern.o ex2_kern.o ex3_kern.o
 
 HOSTCFLAGS += -I$(objtree)/usr/include
 
 HOSTCFLAGS_bpf_load.o += -I$(objtree)/usr/include -Wno-unused-variable
 HOSTLOADLIBES_ex1 += -lelf
 HOSTLOADLIBES_ex2 += -lelf
+HOSTLOADLIBES_ex3 += -lelf
 
 LLC=$(srctree)/tools/bpf/llvm/bld/Debug+Asserts/bin/llc
 
samples/bpf/ex3_kern.c new file +104 -0

104 lines not on this page · raw message

samples/bpf/ex3_user.c new file +149 -0

149 lines not on this page · raw message

Signature · 1 line
1.7.9.5
#29 lore raw
In reply to Alexei Starovoitov
Quoted 6 lines · Alexei Starovoitov

Hi Ingo, David,

posting whole thing again as RFC to get feedback on syscall only. If syscall bpf(int cmd, union bpf_attr *attr, unsigned int size) is ok, I'll split them into small chunks as requested and will repost without RFC.

IMO it's much easier to review a syscall if we just look at a specification of what it does. The code is, in some sense, secondary.

--Andy

#30 lore raw
Quoted 10 lines · Andy Lutomirski
Quoted 6 lines · Alexei Starovoitov

Hi Ingo, David,

posting whole thing again as RFC to get feedback on syscall only. If syscall bpf(int cmd, union bpf_attr *attr, unsigned int size) is ok, I'll split them into small chunks as requested and will repost without RFC.

IMO it's much easier to review a syscall if we just look at a specification of what it does. The code is, in some sense, secondary.

'specification of what it does'... hmm, you mean beyond what's there in commit logs and in Documentation/networking/filter.txt ? Aren't samples at the end give an idea on 'what it does'? I'm happy to add 'specification', I just don't understand yet what it suppose to talk about beyond what's already written.
I understand that the patches are missing explanation on 'why' the syscall is being added, but I don't think it's what you're asking...

#31 lore raw
Quoted 12 lines · Alexei Starovoitov
Quoted 10 lines · Andy Lutomirski
Quoted 6 lines · Alexei Starovoitov

Hi Ingo, David,

posting whole thing again as RFC to get feedback on syscall only. If syscall bpf(int cmd, union bpf_attr *attr, unsigned int size) is ok, I'll split them into small chunks as requested and will repost without RFC.

IMO it's much easier to review a syscall if we just look at a specification of what it does. The code is, in some sense, secondary.

Quoted 7 lines

'specification of what it does'... hmm, you mean beyond what's there in commit logs and in Documentation/networking/filter.txt ? Aren't samples at the end give an idea on 'what it does'? I'm happy to add 'specification', I just don't understand yet what it suppose to talk about beyond what's already written.
I understand that the patches are missing explanation on 'why' the syscall is being added, but I don't think it's what you're asking...

I mean a hopefully short document that defines what the syscall does. It should be precise enough that one could, in principle, implement the syscall just by reading the document and that one could use the syscall just by reading the document.

Given that there's a whole instruction set to go with it, it may end up being moderately complicated or saying things like "see this other thing for a description of the instruction set" and "there are some extensible sets of functions you can call with it".

--Andy

Signature · 2 lines
Andy Lutomirski
AMA Capital Management, LLC
#32 lore raw
Quoted 26 lines · Andy Lutomirski
Quoted 12 lines · Alexei Starovoitov
Quoted 10 lines · Andy Lutomirski
Quoted 6 lines · Alexei Starovoitov

Hi Ingo, David,

posting whole thing again as RFC to get feedback on syscall only. If syscall bpf(int cmd, union bpf_attr *attr, unsigned int size) is ok, I'll split them into small chunks as requested and will repost without RFC.

IMO it's much easier to review a syscall if we just look at a specification of what it does. The code is, in some sense, secondary.

Quoted 7 lines

'specification of what it does'... hmm, you mean beyond what's there in commit logs and in Documentation/networking/filter.txt ? Aren't samples at the end give an idea on 'what it does'? I'm happy to add 'specification', I just don't understand yet what it suppose to talk about beyond what's already written.
I understand that the patches are missing explanation on 'why' the syscall is being added, but I don't think it's what you're asking...

I mean a hopefully short document that defines what the syscall does. It should be precise enough that one could, in principle, implement the syscall just by reading the document and that one could use the syscall just by reading the document.

Quoted 4 lines

Given that there's a whole instruction set to go with it, it may end up being moderately complicated or saying things like "see this other thing for a description of the instruction set" and "there are some extensible sets of functions you can call with it".

I'm still lost.

Here is the quote from Documentation/networking/filter.txt
"
'maps' is a generic storage of different types for sharing data between kernel and userspace.

The maps are accessed from user space via BPF syscall,
which has commands:
- create a map with given type and attributes
map_fd = bpf(BPF_MAP_CREATE, union bpf_attr *attr, u32 size) using attr->map_type, attr->key_size, attr->value_size, attr->max_entries returns process-local file descriptor or negative error

- lookup key in a given map
err = bpf(BPF_MAP_LOOKUP_ELEM, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key, attr->value
returns zero and stores found elem into value or negative error

- create or update key/value pair in a given map
err = bpf(BPF_MAP_UPDATE_ELEM, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key, attr->value
returns zero or negative error

- find and delete element by key in a given map
err = bpf(BPF_MAP_DELETE_ELEM, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key

- to delete map: close(fd)
Exiting process will delete maps automatically

userspace programs uses this API to create/populate/read maps that eBPF programs are concurrently updating. "
and more in commit log:
"
- load eBPF program
fd = bpf(BPF_PROG_LOAD, union bpf_attr *attr, u32 size)

where 'attr' is

  struct {
      enum bpf_prog_type prog_type;
      __u32 insn_cnt;
      struct bpf_insn __user *insns;
      const char __user *license;

};
insns - array of eBPF instructions
license - must be GPL compatible to call helper functions marked gpl_only

- unload eBPF program
close(fd)
"

Isn't it short and describes what it does? Do you want me to describe what eBPF program can do?

#33 lore raw
Quoted 81 lines · Alexei Starovoitov
Quoted 26 lines · Andy Lutomirski
Quoted 12 lines · Alexei Starovoitov
Quoted 10 lines · Andy Lutomirski
Quoted 6 lines · Alexei Starovoitov

Hi Ingo, David,

posting whole thing again as RFC to get feedback on syscall only. If syscall bpf(int cmd, union bpf_attr *attr, unsigned int size) is ok, I'll split them into small chunks as requested and will repost without RFC.

IMO it's much easier to review a syscall if we just look at a specification of what it does. The code is, in some sense, secondary.

Quoted 7 lines

'specification of what it does'... hmm, you mean beyond what's there in commit logs and in Documentation/networking/filter.txt ? Aren't samples at the end give an idea on 'what it does'? I'm happy to add 'specification', I just don't understand yet what it suppose to talk about beyond what's already written.
I understand that the patches are missing explanation on 'why' the syscall is being added, but I don't think it's what you're asking...

I mean a hopefully short document that defines what the syscall does. It should be precise enough that one could, in principle, implement the syscall just by reading the document and that one could use the syscall just by reading the document.

Quoted 4 lines

Given that there's a whole instruction set to go with it, it may end up being moderately complicated or saying things like "see this other thing for a description of the instruction set" and "there are some extensible sets of functions you can call with it".

I'm still lost.

Here is the quote from Documentation/networking/filter.txt
"
'maps' is a generic storage of different types for sharing data between kernel and userspace.

The maps are accessed from user space via BPF syscall,
which has commands:
- create a map with given type and attributes
map_fd = bpf(BPF_MAP_CREATE, union bpf_attr *attr, u32 size) using attr->map_type, attr->key_size, attr->value_size, attr->max_entries returns process-local file descriptor or negative error

- lookup key in a given map
err = bpf(BPF_MAP_LOOKUP_ELEM, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key, attr->value
returns zero and stores found elem into value or negative error

- create or update key/value pair in a given map
err = bpf(BPF_MAP_UPDATE_ELEM, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key, attr->value
returns zero or negative error

- find and delete element by key in a given map
err = bpf(BPF_MAP_DELETE_ELEM, union bpf_attr *attr, u32 size) using attr->map_fd, attr->key

- to delete map: close(fd)
Exiting process will delete maps automatically

userspace programs uses this API to create/populate/read maps that eBPF programs are concurrently updating. "
and more in commit log:
"
- load eBPF program
fd = bpf(BPF_PROG_LOAD, union bpf_attr *attr, u32 size)

where 'attr' is

  struct {
      enum bpf_prog_type prog_type;
      __u32 insn_cnt;
      struct bpf_insn __user *insns;
      const char __user *license;

};
insns - array of eBPF instructions
license - must be GPL compatible to call helper functions marked gpl_only

Quoted 6 lines

- unload eBPF program
close(fd)
"

Isn't it short and describes what it does? Do you want me to describe what eBPF program can do?

The problem is that everyone needs to dig around a very long patch series to find it. Since you're asking for a review of a syscall, it would be nice to have everything needed to review whether the syscall is a good idea in its present form in one place and to keep the amount of email under control.

--Andy

Signature · 2 lines
Andy Lutomirski
AMA Capital Management, LLC
#35 lore raw
Quoted 4 lines · Stephen Hemminger

Something in man page format similar to FreeBSD man page:
http://www.freebsd.org/cgi/man.cgi?bpf(4)

would be more readable and reviewable.

I think at some point, we could perhaps do a section 7 page with a general overview of the engine and where it can be applied, and let the syscall page partially refer to it so that it doesn't get too long. So far, we tried to squeeze everything into Documentation/networking/filter.txt, and that itself is quite long already.

maintainer
#37 lore raw
In reply to Alexei Starovoitov

From: Alexei Starovoitov <ast-uqk4Ao+rVK5Wk0Htik3J/[email protected]>
Date: Tue, 26 Aug 2014 19:29:14 -0700

Quoted 2 lines

posting whole thing again as RFC to get feedback on syscall only. If syscall bpf(int cmd, union bpf_attr *attr, unsigned int size) is ok,

I'm personally not reviewing such a large patch series, sorry.

You need to submit smaller sets if you want to get reasonable review of your changes and ideas.

#38 lore raw
Quoted 4 lines

I'm personally not reviewing such a large patch series, sorry.

You need to submit smaller sets if you want to get reasonable review of your changes and ideas.

Hello. As well, this clogs up the mailing boxes of other people who have no interest in the patch set.

Thank you,
Steven Stewart-Gallus