Skip to contentSkip to conversation

tracing filters with BPF

RFC PATCH Superseded Alexei Starovoitov 10 participants 65 messages Dec 3, 2013 – Dec 12, 2013

Subsystems (8)
Documentation x86 Library code BPF +4 more subsystems

v1 of 2 Superseded Latest is v2 →

lore
Share & tools
lore
#0 lore raw

cover tracing filters with BPF

Hi All,

the following set of patches adds BPF support to trace filters.

Trace filters can be written in C and allow safe read-only access to any kernel data structure. Like systemtap but with safety guaranteed by kernel.

The user can do:
cat bpf_program > /sys/kernel/debug/tracing/.../filter if tracing event is either static or dynamic via kprobe_events.

The filter program may look like:
void filter(struct bpf_context *ctx)

{
        char devname[4] = "eth5";
        struct net_device *dev;
        struct sk_buff *skb = 0;

        dev = (struct net_device *)ctx->regs.si;
        if (bpf_memcmp(dev->name, devname, 4) == 0) {
                char fmt[] = "skb %p dev %p eth5\n";
                bpf_trace_printk(fmt, skb, dev, 0, 0);
        }
}

The kernel will do static analysis of bpf program to make sure that it cannot crash the kernel (doesn't have loops, valid memory/register accesses, etc). Then kernel will map bpf instructions to x86 instructions and let it run in the place of trace filter.

To demonstrate performance I did a synthetic test:

        dev = init_net.loopback_dev;
        do_gettimeofday(&start_tv);
        for (i = 0; i < 1000000; i++) {
                struct sk_buff *skb;
                skb = netdev_alloc_skb(dev, 128);
                kfree_skb(skb);
        }
        do_gettimeofday(&end_tv);
        time = end_tv.tv_sec - start_tv.tv_sec;
        time *= USEC_PER_SEC;
        time += (long long)((long)end_tv.tv_usec - (long)start_tv.tv_usec);

        printk("1M skb alloc/free %lld (usecs)\n", time);

no tracing

[   33.450966] 1M skb alloc/free 145179 (usecs)

echo 1 > enable

[   97.186379] 1M skb alloc/free 240419 (usecs)

(tracing slows down kfree_skb() due to event_buffer_lock/buffer_unlock_commit)

echo 'name==eth5' > filter

[  139.644161] 1M skb alloc/free 302552 (usecs)

(running filter_match_preds() for every skb and discarding event_buffer is even slower)

cat bpf_prog > filter

[  171.150566] 1M skb alloc/free 199463 (usecs)

(JITed bpf program is safely checking dev->name == eth5 and discarding)

echo 0 > enable

[  258.073593] 1M skb alloc/free 144919 (usecs)

(tracing is disabled, performance is back to original)

The C program compiled into BPF and then JITed into x86 is faster than filter_match_preds() approach (199-145 msec vs 302-145 msec)

tracing+bpf is a tool for safe read-only access to variables without recompiling the kernel and without affecting running programs.

BPF filters can be written manually (see tools/bpf/trace/filter_ex1.c) or better compiled from restricted C via GCC or LLVM

Q: What is the difference between existing BPF and extended BPF? A:
Existing BPF insn from uapi/linux/filter.h
struct sock_filter {

        __u16   code;   /* Actual filter code */
        __u8    jt;     /* Jump true */
        __u8    jf;     /* Jump false */
        __u32   k;      /* Generic multiuse field */

};

Extended BPF insn from linux/bpf.h

struct bpf_insn {
        __u8    code;    /* opcode */
        __u8    a_reg:4; /* dest register*/
        __u8    x_reg:4; /* source register */
        __s16   off;     /* signed offset */
        __s32   imm;     /* signed immediate constant */
};

opcode encoding is the same between old BPF and extended BPF. Original BPF has two 32-bit registers.
Extended BPF has ten 64-bit registers.
That is the main difference.

Old BPF was using jt/jf fields for jump-insn only.
New BPF combines them into generic 'off' field for jump and non-jump insns. k==imm field has the same meaning.

Thanks

Alexei Starovoitov (5):
Extended BPF core framework
Extended BPF JIT for x86-64
Extended BPF (64-bit BPF) design document
use BPF in tracing filters
tracing filter examples in BPF

 Documentation/bpf_jit.txt            |  204 +++++++
 arch/x86/Kconfig                     |    1 +
 arch/x86/net/Makefile                |    1 +
 arch/x86/net/bpf64_jit_comp.c        |  625 ++++++++++++++++++++
 arch/x86/net/bpf_jit_comp.c          |   23 +-
 arch/x86/net/bpf_jit_comp.h          |   35 ++
 include/linux/bpf.h                  |  149 +++++
 include/linux/bpf_jit.h              |  129 +++++
 include/linux/ftrace_event.h         |    3 +
 include/trace/bpf_trace.h            |   27 +
 include/trace/ftrace.h               |   14 +
 kernel/Makefile                      |    1 +
 kernel/bpf_jit/Makefile              |    3 +
 kernel/bpf_jit/bpf_check.c           | 1054 ++++++++++++++++++++++++++++++++++
 kernel/bpf_jit/bpf_run.c             |  452 +++++++++++++++
 kernel/trace/Kconfig                 |    1 +
 kernel/trace/Makefile                |    1 +
 kernel/trace/bpf_trace_callbacks.c   |  191 ++++++
 kernel/trace/trace.c                 |    7 +
 kernel/trace/trace.h                 |   11 +-
 kernel/trace/trace_events.c          |    9 +-
 kernel/trace/trace_events_filter.c   |   61 +-
 kernel/trace/trace_kprobe.c          |    6 +
 lib/Kconfig.debug                    |   15 +
 tools/bpf/llvm/README.txt            |    6 +
 tools/bpf/trace/Makefile             |   34 ++
 tools/bpf/trace/README.txt           |   15 +
 tools/bpf/trace/filter_ex1.c         |   52 ++
 tools/bpf/trace/filter_ex1_orig.c    |   23 +
 tools/bpf/trace/filter_ex2.c         |   74 +++
 tools/bpf/trace/filter_ex2_orig.c    |   47 ++
 tools/bpf/trace/trace_filter_check.c |   82 +++
 32 files changed, 3332 insertions(+), 24 deletions(-)
 create mode 100644 Documentation/bpf_jit.txt
 create mode 100644 arch/x86/net/bpf64_jit_comp.c
 create mode 100644 arch/x86/net/bpf_jit_comp.h
 create mode 100644 include/linux/bpf.h
 create mode 100644 include/linux/bpf_jit.h
 create mode 100644 include/trace/bpf_trace.h
 create mode 100644 kernel/bpf_jit/Makefile
 create mode 100644 kernel/bpf_jit/bpf_check.c
 create mode 100644 kernel/bpf_jit/bpf_run.c
 create mode 100644 kernel/trace/bpf_trace_callbacks.c
 create mode 100644 tools/bpf/llvm/README.txt
 create mode 100644 tools/bpf/trace/Makefile
 create mode 100644 tools/bpf/trace/README.txt
 create mode 100644 tools/bpf/trace/filter_ex1.c
 create mode 100644 tools/bpf/trace/filter_ex1_orig.c
 create mode 100644 tools/bpf/trace/filter_ex2.c
 create mode 100644 tools/bpf/trace/filter_ex2_orig.c
 create mode 100644 tools/bpf/trace/trace_filter_check.c
Signature · 1 line
1.7.9.5
#1 lore raw

RFC PATCH 1/5 Extended BPF core framework

Extended BPF (or 64-bit BPF) is an instruction set to
create safe dynamically loadable filters that can call fixed set of kernel functions and take generic bpf_context as an input. BPF filter is a glue between kernel functions and bpf_context. Different kernel subsystems can define their own set of available functions and alter BPF machinery for specific use case.

include/linux/bpf.h - instruction set definition kernel/bpf_jit/bpf_check.c - code safety checker/static analyzer kernel/bpf_jit/bpf_run.c - emulator for archs without BPF64_JIT

Extended BPF instruction set is designed for efficient mapping to native instructions on 64-bit CPUs

---
 include/linux/bpf.h        |  149 +++++++
 include/linux/bpf_jit.h    |  129 ++++++
 kernel/Makefile            |    1 +
 kernel/bpf_jit/Makefile    |    3 +
 kernel/bpf_jit/bpf_check.c | 1054 ++++++++++++++++++++++++++++++++++++++++++++
 kernel/bpf_jit/bpf_run.c   |  452 +++++++++++++++++++
 lib/Kconfig.debug          |   15 +
 7 files changed, 1803 insertions(+)
 create mode 100644 include/linux/bpf.h
 create mode 100644 include/linux/bpf_jit.h
 create mode 100644 kernel/bpf_jit/Makefile
 create mode 100644 kernel/bpf_jit/bpf_check.c
 create mode 100644 kernel/bpf_jit/bpf_run.c
include/linux/bpf.h new file +149 -0
new file mode 100644
index 0000000..a7d3fb7
@@ -0,0 +1,149 @@
+/* 64-bit BPF is Copyright (c) 2011-2013, PLUMgrid, http://plumgrid.com */
+
+#ifndef __LINUX_BPF_H__
+#define __LINUX_BPF_H__
+
+#include <linux/types.h>
+
+struct bpf_insn {
+	__u8	code;    /* opcode */
+	__u8    a_reg:4; /* dest register*/
+	__u8    x_reg:4; /* source register */
+	__s16	off;     /* signed offset */
+	__s32	imm;     /* signed immediate constant */
+};
+
+struct bpf_table {
+	__u32   type;
+	__u32   key_size;
+	__u32   elem_size;
+	__u32   max_entries;
+	__u32   param1;         /* meaning is table-dependent */
+};
+
+enum bpf_table_type {
+	BPF_TABLE_HASH = 1,
+	BPF_TABLE_LPM
+};
+
+/* maximum number of insns and tables in a BPF program */
+#define MAX_BPF_INSNS 4096
+#define MAX_BPF_TABLES 64
+#define MAX_BPF_STRTAB_SIZE 1024
+
+/* pointer to bpf_context is the first and only argument to BPF program
+ * its definition is use-case specific */
+struct bpf_context;
+
+/* bpf_add|sub|...: a += x
+ *         bpf_mov: a = x
+ *       bpf_bswap: bswap a */
+#define BPF_INSN_ALU(op, a, x) \
+	(struct bpf_insn){BPF_ALU|BPF_OP(op)|BPF_X, a, x, 0, 0}
+
+/* bpf_add|sub|...: a += imm
+ *         bpf_mov: a = imm */
+#define BPF_INSN_ALU_IMM(op, a, imm) \
+	(struct bpf_insn){BPF_ALU|BPF_OP(op)|BPF_K, a, 0, 0, imm}
+
+/* a = *(uint *) (x + off) */
+#define BPF_INSN_LD(size, a, x, off) \
+	(struct bpf_insn){BPF_LDX|BPF_SIZE(size)|BPF_REL, a, x, off, 0}
+
+/* *(uint *) (a + off) = x */
+#define BPF_INSN_ST(size, a, off, x) \
+	(struct bpf_insn){BPF_STX|BPF_SIZE(size)|BPF_REL, a, x, off, 0}
+
+/* *(uint *) (a + off) = imm */
+#define BPF_INSN_ST_IMM(size, a, off, imm) \
+	(struct bpf_insn){BPF_ST|BPF_SIZE(size)|BPF_REL, a, 0, off, imm}
+
+/* lock *(uint *) (a + off) += x */
+#define BPF_INSN_XADD(size, a, off, x) \
+	(struct bpf_insn){BPF_STX|BPF_SIZE(size)|BPF_XADD, a, x, off, 0}
+
+/* if (a 'op' x) pc += off else fall through */
+#define BPF_INSN_JUMP(op, a, x, off) \
+	(struct bpf_insn){BPF_JMP|BPF_OP(op)|BPF_X, a, x, off, 0}
+
+/* if (a 'op' imm) pc += off else fall through */
+#define BPF_INSN_JUMP_IMM(op, a, imm, off) \
+	(struct bpf_insn){BPF_JMP|BPF_OP(op)|BPF_K, a, 0, off, imm}
+
+#define BPF_INSN_RET() \
+	(struct bpf_insn){BPF_RET|BPF_K, 0, 0, 0, 0}
+
+#define BPF_INSN_CALL(fn_code) \
+	(struct bpf_insn){BPF_JMP|BPF_CALL, 0, 0, 0, fn_code}
+
+/* Instruction classes */
+#define BPF_CLASS(code) ((code) & 0x07)
+#define         BPF_LD          0x00
+#define         BPF_LDX         0x01
+#define         BPF_ST          0x02
+#define         BPF_STX         0x03
+#define         BPF_ALU         0x04
+#define         BPF_JMP         0x05
+#define         BPF_RET         0x06
+
+/* ld/ldx fields */
+#define BPF_SIZE(code)  ((code) & 0x18)
+#define         BPF_W           0x00
+#define         BPF_H           0x08
+#define         BPF_B           0x10
+#define         BPF_DW          0x18
+#define BPF_MODE(code)  ((code) & 0xe0)
+#define         BPF_IMM         0x00
+#define         BPF_ABS         0x20
+#define         BPF_IND         0x40
+#define         BPF_MEM         0x60
+#define         BPF_LEN         0x80
+#define         BPF_MSH         0xa0
+#define         BPF_REL         0xc0
+#define         BPF_XADD        0xe0 /* exclusive add */
+
+/* alu/jmp fields */
+#define BPF_OP(code)    ((code) & 0xf0)
+#define         BPF_ADD         0x00
+#define         BPF_SUB         0x10
+#define         BPF_MUL         0x20
+#define         BPF_DIV         0x30
+#define         BPF_OR          0x40
+#define         BPF_AND         0x50
+#define         BPF_LSH         0x60
+#define         BPF_RSH         0x70 /* logical shift right */
+#define         BPF_NEG         0x80
+#define         BPF_MOD         0x90
+#define         BPF_XOR         0xa0
+#define         BPF_MOV         0xb0 /* mov reg to reg */
+#define         BPF_ARSH        0xc0 /* sign extending arithmetic shift right */
+#define         BPF_BSWAP32     0xd0 /* swap lower 4 bytes of 64-bit register */
+#define         BPF_BSWAP64     0xe0 /* swap all 8 bytes of 64-bit register */
+
+#define         BPF_JA          0x00
+#define         BPF_JEQ         0x10 /* jump == */
+#define         BPF_JGT         0x20 /* GT is unsigned '>', JA in x86 */
+#define         BPF_JGE         0x30 /* GE is unsigned '>=', JAE in x86 */
+#define         BPF_JSET        0x40
+#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_SRC(code)   ((code) & 0x08)
+#define         BPF_K           0x00
+#define         BPF_X           0x08
+
+/* 64-bit registers */
+#define         R0              0
+#define         R1              1
+#define         R2              2
+#define         R3              3
+#define         R4              4
+#define         R5              5
+#define         R6              6
+#define         R7              7
+#define         R8              8
+#define         R9              9
+#define         __fp__          10
+
+#endif /* __LINUX_BPF_H__ */
include/linux/bpf_jit.h new file +129 -0

129 lines not on this page · raw message

kernel/Makefile +1 -0
index bbaf7d5..68a974e 100644
@@ -83,6 +83,7 @@ obj-$(CONFIG_TRACING) += trace/
 obj-$(CONFIG_TRACE_CLOCK) += trace/
 obj-$(CONFIG_RING_BUFFER) += trace/
 obj-$(CONFIG_TRACEPOINTS) += trace/
+obj-$(CONFIG_BPF64) += bpf_jit/
 obj-$(CONFIG_IRQ_WORK) += irq_work.o
 obj-$(CONFIG_CPU_PM) += cpu_pm.o
 
kernel/bpf_jit/Makefile new file +3 -0
new file mode 100644
index 0000000..2e576f9
@@ -0,0 +1,3 @@
+obj-$(CONFIG_BPF64) += bpf_check.o
+obj-$(CONFIG_BPF64) += bpf_run.o
+
kernel/bpf_jit/bpf_check.c new file +1054 -0

1,054 lines not on this page · raw message

kernel/bpf_jit/bpf_run.c new file +452 -0

452 lines not on this page · raw message

lib/Kconfig.debug +15 -0
index 6982094..7b50774 100644
@@ -1591,3 +1591,18 @@ source "samples/Kconfig"
 
 source "lib/Kconfig.kgdb"
 
+# Used by archs to tell that they support 64-bit BPF JIT
+config HAVE_BPF64_JIT
+	bool
+
+config BPF64
+	bool "Enable 64-bit BPF instruction set support"
+	help
+	  Enable this option to support 64-bit BPF programs
+
+config BPF64_JIT
+	bool "Enable 64-bit BPF JIT compiler"
+	depends on BPF64 && HAVE_BPF64_JIT
+	help
+	  Enable Just-In-Time compiler for 64-bit BPF programs
+
Signature · 1 line
1.7.9.5
#2 lore raw

RFC PATCH 2/5 Extended BPF JIT for x86-64

In reply to Alexei Starovoitov

Just-In-Time compiler that maps 64-bit BPF instructions to x86-64 instructions.

Most BPF instructions have one to one mapping.

Every BPF register maps to one x86-64 register:
R0 -> rax
R1 -> rdi
R2 -> rsi
R3 -> rdx
R4 -> rcx
R5 -> r8
R6 -> rbx
R7 -> r13
R8 -> r14
R9 -> r15
FP -> rbp

BPF calling convention is defined as:
R0 - return value from in-kernel function
R1-R5 - arguments from BPF program to in-kernel function R6-R9 - callee saved registers that in-kernel function will preserve R10 - read-only frame pointer to access stack
so BPF calling convention maps directly to x86-64 calling convention.

Allowing zero-overhead calls between BPF filter and safe kernel functions

---
 arch/x86/Kconfig              |    1 +
 arch/x86/net/Makefile         |    1 +
 arch/x86/net/bpf64_jit_comp.c |  625 +++++++++++++++++++++++++++++++++++++++++
 arch/x86/net/bpf_jit_comp.c   |   23 +-
 arch/x86/net/bpf_jit_comp.h   |   35 +++
 5 files changed, 665 insertions(+), 20 deletions(-)
 create mode 100644 arch/x86/net/bpf64_jit_comp.c
 create mode 100644 arch/x86/net/bpf_jit_comp.h
arch/x86/Kconfig +1 -0
index c84cf90..44b0b11 100644
@@ -92,6 +92,7 @@ config X86
 	select GENERIC_CLOCKEVENTS_MIN_ADJUST
 	select IRQ_FORCED_THREADING
 	select HAVE_BPF_JIT if X86_64
+	select HAVE_BPF64_JIT if X86_64
 	select HAVE_ARCH_TRANSPARENT_HUGEPAGE
 	select CLKEVT_I8253
 	select ARCH_HAVE_NMI_SAFE_CMPXCHG
arch/x86/net/Makefile +1 -0
index 90568c3..c3bb7d5 100644
@@ -2,3 +2,4 @@
 # Arch-specific network modules
 #
 obj-$(CONFIG_BPF_JIT) += bpf_jit.o bpf_jit_comp.o
+obj-$(CONFIG_BPF64_JIT) += bpf64_jit_comp.o
arch/x86/net/bpf64_jit_comp.c new file +625 -0

625 lines not on this page · raw message

arch/x86/net/bpf_jit_comp.c +3 -20
index 26328e8..3c35f8d 100644
@@ -13,6 +13,7 @@
 #include <linux/filter.h>
 #include <linux/if_vlan.h>
 #include <linux/random.h>
+#include "bpf_jit_comp.h"
 
 /*
  * Conventions :
@@ -112,16 +113,6 @@ do {								\
 #define SEEN_XREG    2 /* ebx is used */
 #define SEEN_MEM     4 /* use mem[] for temporary storage */
 
-static inline void bpf_flush_icache(void *start, void *end)
-{
-	mm_segment_t old_fs = get_fs();
-
-	set_fs(KERNEL_DS);
-	smp_wmb();
-	flush_icache_range((unsigned long)start, (unsigned long)end);
-	set_fs(old_fs);
-}
-
 #define CHOOSE_LOAD_FUNC(K, func) \
 	((int)K < 0 ? ((int)K >= SKF_LL_OFF ? func##_negative_offset : func) : func##_positive_offset)
 
@@ -145,16 +136,8 @@ static int pkt_type_offset(void)
 	return -1;
 }
 
-struct bpf_binary_header {
-	unsigned int	pages;
-	/* Note : for security reasons, bpf code will follow a randomly
-	 * sized amount of int3 instructions
-	 */
-	u8		image[];
-};
-
-static struct bpf_binary_header *bpf_alloc_binary(unsigned int proglen,
-						  u8 **image_ptr)
+struct bpf_binary_header *bpf_alloc_binary(unsigned int proglen,
+					   u8 **image_ptr)
 {
 	unsigned int sz, hole;
 	struct bpf_binary_header *header;
arch/x86/net/bpf_jit_comp.h new file +35 -0
new file mode 100644
index 0000000..74ff45d
@@ -0,0 +1,35 @@
+/* bpf_jit_comp.h : BPF filter alloc/free routines
+ *
+ * This program is free software; you can redistribute it and/or
+ * modify it under the terms of the GNU General Public License
+ * as published by the Free Software Foundation; version 2
+ * of the License.
+ */
+#ifndef __BPF_JIT_COMP_H
+#define __BPF_JIT_COMP_H
+
+#include <linux/uaccess.h>
+#include <asm/cacheflush.h>
+
+struct bpf_binary_header {
+	unsigned int	pages;
+	/* Note : for security reasons, bpf code will follow a randomly
+	 * sized amount of int3 instructions
+	 */
+	u8		image[];
+};
+
+static inline void bpf_flush_icache(void *start, void *end)
+{
+	mm_segment_t old_fs = get_fs();
+
+	set_fs(KERNEL_DS);
+	smp_wmb();
+	flush_icache_range((unsigned long)start, (unsigned long)end);
+	set_fs(old_fs);
+}
+
+struct bpf_binary_header *bpf_alloc_binary(unsigned int proglen,
+					   u8 **image_ptr);
+
+#endif
Signature · 1 line
1.7.9.5
#3 lore raw

RFC PATCH 3/5 Extended BPF (64-bit BPF) design document

In reply to Alexei Starovoitov
---
 Documentation/bpf_jit.txt |  204 +++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 204 insertions(+)
 create mode 100644 Documentation/bpf_jit.txt
Documentation/bpf_jit.txt new file +204 -0
new file mode 100644
index 0000000..9c70f42
@@ -0,0 +1,204 @@
+Subject: extended BPF or 64-bit BPF
+
+Q: What is BPF?
+A: Safe dynamically loadable 32-bit program that can access skb->data via
+sk_load_byte/half/word calls or seccomp_data. Can be attached to sockets,
+to netfilter xtables, seccomp. In case of sockets/xtables input is skb.
+In case of seccomp input is struct seccomp_data.
+
+Q: What is extended BPF?
+A: Safe dynamically loadable 64-bit program that can call fixed set
+of kernel functions and takes generic bpf_context as an input.
+BPF program is a glue between kernel functions and bpf_context.
+Different kernel subsystems can define their own set of available functions
+and alter BPF machinery for specific use case.
+
+Example 1:
+when function set is {bpf_load_byte/half/word} and bpf_context=skb
+the extended BPF is equivalent to original BPF (w/o negative offset extensions),
+since any such extended BPF program will only be able to load data from skb
+and interpret it.
+
+Example 2:
+when function set is {empty} and bpf_context=seccomp_data,
+the extended BPF is equivalent to original seccomp BPF with simpler programs
+and can immediately take advantage of extended BPF-JIT.
+(original BPF-JIT doesn't work for seccomp)
+
+Example 3:
+when function set is {bpf_load_xxx + bpf_table_lookup} and bpf_context=skb
+the extended BPF can be used to implement network analytics in tcpdump.
+Like counting all tcp flows through the dev or filtering for specific
+set of IP addresses.
+
+Example 4:
+when function set is {load_xxx + table_lookup + trace_printk} and
+bpf_context=pt_regs, the extended BPF is used to implement systemtap-like
+tracing filters
+
+Extended Instruction Set was designed with these goals:
+- write programs in restricted C and compile into BPF with GCC/LLVM
+- just-in-time map to modern 64-bit CPU with minimal performance overhead
+  over two steps: C -> BPF -> native code
+- guarantee termination and safety of BPF program in kernel
+  with simple algorithm
+
+Writing filters in tcpdump syntax or in systemtap language is difficult.
+Same filter done in C is easier to understand.
+GCC/LLVM-bpf backend is optional.
+Extended BPF can be coded with macroses from bpf.h just like original BPF.
+
+Minimal performance overhead is achieved by having one to one mapping
+between BPF insns and native insns, and one to one mapping between BPF
+registers and native registers on 64-bit CPUs
+
+Extended BPF allows jump forward and backward for two reasons:
+to reduce branch mispredict penalty compiler moves cold basic blocks out of
+fall-through path and to reduce code duplication that would be unavoidable
+if only jump forward was available.
+To guarantee termination simple non-recursive depth-first-search verifies
+that there are no back-edges (no loops in the program), program is a DAG
+with root at the first insn, all branches end at the last RET insn and
+all instructions are reachable.
+(Original BPF actually allows unreachable insns, but that's a bug)
+
+Original BPF has two registers (A and X) and hidden frame pointer.
+Extended BPF has ten registers and read-only frame pointer.
+Since 64-bit CPUs are passing arguments to the functions via registers
+the number of args from BPF program to in-kernel function is restricted to 5
+and one register is used to accept return value from in-kernel function.
+x86_64 passes first 6 arguments in registers.
+aarch64/sparcv9/mips64 have 7-8 registers for arguments.
+x86_64 has 6 callee saved registers.
+aarch64/sparcv9/mips64 have 11 or more callee saved registers.
+
+Therefore extended BPF calling convention is defined as:
+R0 - return value from in-kernel function
+R1-R5 - arguments from BPF program to in-kernel function
+R6-R9 - callee saved registers that in-kernel function will preserve
+R10 - read-only frame pointer to access stack
+
+so that all BPF registers map one to one to HW registers on x86_64,aarch64,etc
+and BPF calling convention maps directly to ABIs used by kernel on 64-bit
+architectures.
+
+R0-R5 are scratch registers and BPF program needs spill/fill them if necessary
+across calls.
+Note that there is only one BPF program == one BPF function and it cannot call
+other BPF functions. It can only call predefined in-kernel functions.
+
+All BPF registers are 64-bit without subregs, which makes JITed x86 code
+less optimal, but matches sparc/mips architectures.
+Adding 32-bit subregs was considered, since JIT can map them to x86 and aarch64
+nicely, but read-modify-write overhead for sparc/mips is not worth the gains.
+
+Original BPF and extended BPF are two operand instructions, which helps
+to do one-to-one mapping between BPF insn and x86 insn during JIT.
+
+Extended BPF doesn't have pre-defined endianness not to favor one
+architecture vs another. Therefore bswap insn was introduced.
+Original BPF doesn't have such insn and does bswap as part of sk_load_word call
+which is often unnecessary if we want to compare the value with the constant.
+Restricted C code might be written differently depending on endianness
+and GCC/LLVM-bpf will take an endianness flag.
+
+32-bit architectures run 64-bit extended BPF programs via interpreter
+
+Q: Why extended BPF is 64-bit? Cannot we live with 32-bit?
+A: On 64-bit architectures, pointers are 64-bit and we want to pass 64-bit
+values in/out kernel functions, so 32-bit BPF registers would require to define
+register-pair ABI, there won't be a direct BPF register to HW register
+mapping and JIT would need to do combine/split/move operations for every
+register in and out of the function, which is complex, bug prone and slow.
+Another reason is counters. To use 64-bit counter BPF program would need to do
+a complex math. Again bug prone and not atomic.
+
+Q: Original BPF is safe, deterministic and kernel can easily prove that.
+   Does extended BPF keep these properties?
+A: Yes. The safety of the program is determined in two steps.
+First step does depth-first-search to disallow loops and other CFG validation.
+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 bpf_context
+and has type PTR_TO_CTX. If checker sees an insn that does R2=R1, then R2 has
+now type PTR_TO_CTX as well and can be used on right hand side of expression.
+If R1=PTR_TO_CTX and insn is R2=R1+1, then R2=INVALID_PTR and it is readable.
+If register was never written to, it's not readable.
+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.
+load/store instructions are allowed only with registers of valid types, which
+are PTR_TO_CTX, PTR_TO_TABLE, PTR_TO_STACK. They are bounds and alginment
+checked.
+
+bpf_context structure is generic. Its contents are defined by specific use case.
+For seccomp it can be seccomp_data and through get_context_access callback
+BPF checker is customized, so that BPF program can only access certain fields
+of bpf_context with specified size and alignment.
+For example, the following insn:
+  BPF_INSN_LD(BPF_W, R0, R6, 8)
+intends to load word from address R6 + 8 and store it into R0
+If R6=PTR_TO_CTX, then get_context_access callback should let the checker know
+that offset 8 of size 4 bytes can be accessed for reading, otherwise the checker
+will reject the program.
+If R6=PTR_TO_STACK, then access should be aligned and be within stack bounds,
+which are hard coded to [-480, 0]. In this example offset is 8, so it will fail
+verification.
+The checker will allow BPF program to read data from stack only after it wrote
+into it.
+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 via get_func_proto callback.
+For example:
+  u64 bpf_load_byte(struct bpf_context *ctx, u32 offset);
+function will have the following definition:
+  struct bpf_func_proto proto = {RET_INTEGER, PTR_TO_CTX};
+and BPF checker will verify that bpf_load_byte is always called with first
+argument being a valid pointer to bpf_context. After the call BPF register R0
+will be set to readable state, so that BPF program can access it.
+
+One of the useful functions that can be made available to BPF program
+are bpf_table_lookup/bpf_table_update.
+Using them a tracing filter can collect any type of statistics.
+
+Therefore extended BPF program consists of instructions and tables.
+From BPF program the table is identified by constant table_id
+and access to a table in C looks like:
+elem = bpf_table_lookup(ctx, table_id, key);
+
+BPF checker matches 'table_id' against known tables, verifies that 'key' points
+to stack and table->key_size bytes are initialized.
+From there on bpf_table_lookup() is a normal kernel function. It needs to do
+a lookup by whatever means and return either valid pointer to the element
+or NULL. BPF checker will verify that the program accesses the pointer only
+after comparing it to NULL. That's the meaning of PTR_TO_TABLE_CONDITIONAL and
+PTR_TO_TABLE register types in bpf_check.c
+
+If a kernel subsystem wants to use this BPF framework and decides to implement
+bpf_table_lookup, the checker will guarantee that argument 'ctx' is a valid
+pointer to bpf_context, 'table_id' is valid table_id and table->key_size bytes
+can be read from the pointer 'key'. It's up to implementation to decide how it
+wants to do the lookup and what is the key.
+
+Going back to the example BPF insn:
+  BPF_INSN_LD(BPF_W, R0, R6, 8)
+if R6=PTR_TO_TABLE, then offset and size of access must be within
+[0, table->elem_size] which is determined by constant table_id that was passed
+into bpf_table_lookup call prior to this insn.
+
+Just like original, extended BPF is limited to 4096 insns, which means that any
+program will terminate quickly and will call fixed number of kernel functions.
+Earlier implementation of the checker had a precise calculation of worst case
+number of insns, but it was removed to simplify the code, since the worst number
+is always less then number of insns in a program anyway (because it's a DAG).
+
+Since register/stack state tracking simulates execution of all insns in all
+possible branches, it will explode if not bounded. There are two bounds.
+verifier_state stack is limited to 1k, therefore BPF program cannot have
+more than 1k jump insns.
+Total number of insns to be analyzed is limited to 32k, which means that
+checker will either prove correctness or reject the program in few
+milliseconds on average x86 cpu. Valid programs take microseconds to verify.
+
Signature · 1 line
1.7.9.5
#4 lore raw

Re: [RFC PATCH tip 3/5] Extended BPF (64-bit BPF) design document

Documentation/bpf_jit.txt line 94

Quoted 6 lines · Alexei Starovoitov
Documentation/bpf_jit.txt new file +6 -0
+
+All BPF registers are 64-bit without subregs, which makes JITed x86 code
+less optimal, but matches sparc/mips architectures.
+Adding 32-bit subregs was considered, since JIT can map them to x86 and aarch64
+nicely, but read-modify-write overhead for sparc/mips is not worth the gains.
+

I find this tradeoff to be more than somewhat puzzling, given that x86 and ARM are by far the dominant tradeoffs, and it would make implementation on 32-bit CPUs cheaper if a lot of the operations are 32 bit.

Instead it seems like the niche architectures (which, realistically, SPARC and MIPS have become) ought to take the performance hit.

Perhaps you are simply misunderstanding the notion of subregisters. Neither x86 nor ARM64 leave the top 32 bits intact, so I don't see why SPARC/MIPS would do RMW either.

Documentation/bpf_jit.txt line 114

Quoted 8 lines
Documentation/bpf_jit.txt new file +8 -0
+Q: Why extended BPF is 64-bit? Cannot we live with 32-bit?
+A: On 64-bit architectures, pointers are 64-bit and we want to pass 64-bit
+values in/out kernel functions, so 32-bit BPF registers would require to define
+register-pair ABI, there won't be a direct BPF register to HW register
+mapping and JIT would need to do combine/split/move operations for every
+register in and out of the function, which is complex, bug prone and slow.
+Another reason is counters. To use 64-bit counter BPF program would need to do
+a complex math. Again bug prone and not atomic.

Having EBPF code manipulating pointers - or kernel memory - directly seems like a nonstarter. However, per your subsequent paragraph it sounds like pointers are a special type at which point it shouldn't matter at the EBPF level how many bytes it takes to represent it?

-hpa

#5 lore raw

Re: [RFC PATCH tip 3/5] Extended BPF (64-bit BPF) design document

Quoted 12 lines · H. Peter Anvin

Documentation/bpf_jit.txt line 94

Quoted 6 lines · Alexei Starovoitov
Documentation/bpf_jit.txt new file +6 -0
+
+All BPF registers are 64-bit without subregs, which makes JITed x86 code
+less optimal, but matches sparc/mips architectures.
+Adding 32-bit subregs was considered, since JIT can map them to x86 and aarch64
+nicely, but read-modify-write overhead for sparc/mips is not worth the gains.
+

I find this tradeoff to be more than somewhat puzzling, given that x86 and ARM are by far the dominant tradeoffs, and it would make implementation on 32-bit CPUs cheaper if a lot of the operations are 32 bit.

Quoted 6 lines

Instead it seems like the niche architectures (which, realistically, SPARC and MIPS have become) ought to take the performance hit.

Perhaps you are simply misunderstanding the notion of subregisters. Neither x86 nor ARM64 leave the top 32 bits intact, so I don't see why SPARC/MIPS would do RMW either.

32-bit reg write access on x86-64 is of course zero-extended. 16 and 8 bit are not.
If BPF isa to allow 32-bit subregs, it would need to allow int args to be passed in them
as well. I'm not sure yet that arm64 calling convention will match x86-64 in that sense.

Quoted 1 line

From compiler point of view if arg has int32 type and lives in 32-bit

subreg on 64-bit cpu,
the compiler has to access it with 32-bit subreg ops only. It cannot assume that it was zero extended by caller. So all ops on sparc/mips would have to use extra registers and do 64->32 masks.
Also 32-bit subreg doesn't help to look at int variables. In both cases it will be 32-bit load
then with subregs cmp eax and without it cmp rax after jit.
To increment atomic 32-bit counter in memory, they don't help either. They just don't give enough performance boost to justify complexity in encoding, analyzing and JITing. So I don't see a viable benefit of 32-bit subregs yet.

The above arguments apply to 64-bit CPUs with 64-bit registers with or without 32-bit subregs.

If you're talking about 32-bit CPUs it's completely different matter. If we want to support JIT on them we need 32-bit bpf isa (proposed BPF isa is 64-bit with no effort to make it JITable on 32-bit cpus) Which can reuse all of the same encoding and make all registers 32-bit. Compiler will produce different bpf code though.
It would know that it cannot load 64-bit value in one insn and will use register pairs and so on.
Like -m32 / -m64 switch for bpf backend.
Letting compiler generate 64-bit BPF isa and then try to JIT it to 32-bit cpu is feasible, but very painful. Such JIT will be too large to include in kernel.
Proposed JIT is short and simple because it maps all registers and instructions one to one.

So the big question, do we really care about lack of bpf jit on 32-bit cpus? Considering that ebpf still works on them, but via interpreter (see bpf_run.c)...
imo that is the same situation as we have today with old bpf.

Quoted 5 lines
Quoted 5 lines
Documentation/bpf_jit.txt new file +5 -0
+Q: Why extended BPF is 64-bit? Cannot we live with 32-bit?
+A: On 64-bit architectures, pointers are 64-bit and we want to pass 64-bit
+values in/out kernel functions, so 32-bit BPF registers would require to define
+register-pair ABI, there won't be a direct BPF register to HW register
+mapping and JIT would need to do combine/split/move operations for every
Quoted 8 lines

Documentation/bpf_jit.txt line 114

Quoted 3 lines
Documentation/bpf_jit.txt new file +3 -0
+register in and out of the function, which is complex, bug prone and slow.
+Another reason is counters. To use 64-bit counter BPF program would need to do
+a complex math. Again bug prone and not atomic.

Having EBPF code manipulating pointers - or kernel memory - directly seems like a nonstarter. However, per your subsequent paragraph it sounds like pointers are a special type at which point it shouldn't matter at the EBPF level how many bytes it takes to represent it?

bpf_check() will track every register through every insn.
If pointer is stored in the register, it will know what type
of pointer it is and will allow '*reg' operation only if pointer is valid. For example, upon entry into bpf program, register R1 will have type ptr_to_ctx. After JITing it means that 'rdi' has a valid pointer and it points to 'struct bpf_context'.
If bpf code has R1 = R1 + 1 insn, the checker will assign invalid_ptr type to R1 after this insn and memory access via R1 will be rejected by checker.

BPF program actually can manipulate kernel memory directly when checker guarantees that it is safe to do so :)

For example in tracing filters bpf_context access is restricted to:

static const struct bpf_context_access ctx_access[MAX_CTX_OFF] = {
        [offsetof(struct bpf_context, regs.di)] = {
                FIELD_SIZEOF(struct bpf_context, regs.di),
                BPF_READ
        },

meaning that bpf program can only do 8-byte load from 'rdi + 112' when rdi still has type ptr_to_ctx. (112 is offset of 'di' field within bpf_context)

Direct access making it so efficient and fast. After JITing bpf program is pretty to close to natively compiled code. C->bpf->x86 is quite close to C->x86. (talking about x86_64 of course)

Over course of development bpf_check() found several compiler bugs. I also tried all of sorts of ways to break bpf jail from inside of a bpf program, but so far checker catches everything I was able to throw at it.

btw, tools/bpf/trace/trace_filter_check.c is a user space program that links kernel/bpf_jit/bpf_check.o to make it easier to debug/understand how bpf_check() is working.
It's there to do the same check as kernel will do while loading, but doing it in userspace.
So it's faster to get an answer whether bpf filter is safe or not. Examples are in the same tools/bpf/trace/ dir.

Thank you so much for review! Really appreciate the feedback.

Regards,
Alexei

#6 lore raw

Re: [RFC PATCH tip 3/5] Extended BPF (64-bit BPF) design document

Quoted 6 lines · Alexei Starovoitov

[...]

Quoted 4 lines

Having EBPF code manipulating pointers - or kernel memory - directly seems like a nonstarter. However, per your subsequent paragraph it sounds like pointers are a special type at which point it shouldn't matter at the EBPF level how many bytes it takes to represent it?

Quoted 6 lines

bpf_check() will track every register through every insn.
If pointer is stored in the register, it will know what type of pointer it is and will allow '*reg' operation only if pointer is valid. [...]
BPF program actually can manipulate kernel memory directly when checker guarantees that it is safe to do so :)

It sounds like this sort of static analysis would have difficulty with situations such as:

- multiple levels of indirection

- conditionals (where it can't trace a unique data/type flow for all pointers)

- aliasing (same reason)

- the possibility of bad (or userspace?) pointers arriving as parameters from the underlying trace events

Quoted 6 lines

For example in tracing filters bpf_context access is restricted to:

static const struct bpf_context_access ctx_access[MAX_CTX_OFF] = {
        [offsetof(struct bpf_context, regs.di)] = {
                FIELD_SIZEOF(struct bpf_context, regs.di),
                BPF_READ
        },

Are such constraints to be hard-coded in the kernel?

Quoted 4 lines

Over course of development bpf_check() found several compiler bugs. I also tried all of sorts of ways to break bpf jail from inside of a bpf program, but so far checker catches everything I was able to throw at it.

(One can be sure that attackers will chew hard on this interface, should it become reasonably accessible to userspace, so good job starting to check carefully!)

- FChE

#7 lore raw

Re: [RFC PATCH tip 3/5] Extended BPF (64-bit BPF) design document

Quoted 16 lines · Frank Ch. Eigler
Quoted 6 lines · Alexei Starovoitov

[...]

Quoted 4 lines

Having EBPF code manipulating pointers - or kernel memory - directly seems like a nonstarter. However, per your subsequent paragraph it sounds like pointers are a special type at which point it shouldn't matter at the EBPF level how many bytes it takes to represent it?

Quoted 6 lines

bpf_check() will track every register through every insn.
If pointer is stored in the register, it will know what type of pointer it is and will allow '*reg' operation only if pointer is valid. [...]
BPF program actually can manipulate kernel memory directly when checker guarantees that it is safe to do so :)

Quoted 2 lines

It sounds like this sort of static analysis would have difficulty with situations such as:

yes. good points.
it's a simple analysis to have minimal # of lines in the kernel with the goal to cover the cases where performance matters. but the cases you mentioned are supported by bpf_load_pointer() in bpf_trace_callbacks.c

Quoted 1 line

- multiple levels of indirection

in tools/bpf/trace/filter_ex1_orig.c
when filter reads first argument of event it assumes it got 'skb' pointer. If it just type casts it and does 'skb->dev', this memory load will be rejected by bpf_check().
Instead it does bpf_load_pointer() which will bring the value if the pointer is not faulting.
It may be reading junk and subsequent bpf_memcmp(dev->name, "name") may be reading
something even more bogus.
But it won't crash the kernel and if filter applied to the correct event, the 'skb' pointer will be indeed 'struct sk_buff' and 'dev' will indeed be pointing to 'struct net_device' and 'dev->name' will be actual name.
It's possible to make first level of indirection faster by making static analyzer more complex,
but imo it's not worth it for one level.
It's possible to teach it for multi-level, but then analyzer will become too large and won't be suitable for kernel.

Quoted 1 line

- conditionals (where it can't trace a unique data/type flow for all pointers)

Some conditionals where performance matter are supported.
Like bpf_table_lookup() returns either valid pointer to table element or null. and bpf_check assigns pointer type as 'ptr_to_table_conditional' until bpf program does 'reg != null' and in the true branch the register changes type to 'ptr_to_table', so that bpf program can access table element for both read and write. See filter_ex2_orig.c
There 'leaf->packet_cnt' is a direct memory load from pointer that points to table element.

Quoted 1 line

- aliasing (same reason)

not sure what you mean here.

Quoted 2 lines

- the possibility of bad (or userspace?) pointers arriving as parameters from the underlying trace events

solved same way as case #1

Quoted 8 lines
Quoted 6 lines

For example in tracing filters bpf_context access is restricted to:

static const struct bpf_context_access ctx_access[MAX_CTX_OFF] = {
        [offsetof(struct bpf_context, regs.di)] = {
                FIELD_SIZEOF(struct bpf_context, regs.di),
                BPF_READ
        },

Are such constraints to be hard-coded in the kernel?

I'm hoping that BPF framework will be used by different kernel subsystems. In case of trace filters 'bpf_context' will be defined once and hard-coded within kernel.
So all tracing filters will have the same input interface.
For other subsystems bpf_context may mean something different with its own access rights.
So bpf filters that load fine as tracing filters will be rejected when loaded into other bpf subsystem.
Theoretically subsystem may define bpf_context dynamically. Like its own bpf_context for every trace event, but that's an overkill.

Quoted 8 lines
Quoted 4 lines

Over course of development bpf_check() found several compiler bugs. I also tried all of sorts of ways to break bpf jail from inside of a bpf program, but so far checker catches everything I was able to throw at it.

(One can be sure that attackers will chew hard on this interface, should it become reasonably accessible to userspace, so good job starting to check carefully!)

I think for quite some time root privileges would be needed to load these filters,
but eventually would be useful to let non-root users to insert them as well.

Thank you for feedback!

Regards,
Alexei

#8 lore raw

Re: [RFC PATCH tip 3/5] Extended BPF (64-bit BPF) design document

Quoted 2 lines · Alexei Starovoitov

It's possible to teach it for multi-level, but then analyzer will become too large and won't be suitable for kernel.

Btw., even if we want to start simple with most things, the above statement is not actually true in the broad sense: the constraint for the kernel is utility, not complexity.

We have various kinds of highly complex code in the kernel and can deal with it just fine. Throwing away useful ideas just because they seem too complex at first sight is almost always wrong.

Thanks,

Ingo

#9 lore raw

RFC PATCH 4/5 use BPF in tracing filters

In reply to Alexei Starovoitov

Such filters can be written in C and allow safe read-only access to any kernel data structure.
Like systemtap but with safety guaranteed by kernel.

The user can do:
cat bpf_program > /sys/kernel/debug/tracing/.../filter if tracing event is either static or dynamic via kprobe_events.

The program can be anything as long as bpf_check() can verify its safety. For example, the user can create kprobe_event on dst_discard() and use logically following code inside BPF filter:

      skb = (struct sk_buff *)ctx->regs.di;
      dev = bpf_load_pointer(&skb->dev);

to access 'struct net_device'
Since its prototype is 'int dst_discard(struct sk_buff *skb);' 'skb' pointer is in 'rdi' register on x86_64 bpf_load_pointer() will try to fetch 'dev' field of 'sk_buff' structure and will suppress page-fault if pointer is incorrect.

---
 include/linux/ftrace_event.h       |    3 +
 include/trace/bpf_trace.h          |   27 +++++
 include/trace/ftrace.h             |   14 +++
 kernel/trace/Kconfig               |    1 +
 kernel/trace/Makefile              |    1 +
 kernel/trace/bpf_trace_callbacks.c |  191 ++++++++++++++++++++++++++++++++++++
 kernel/trace/trace.c               |    7 ++
 kernel/trace/trace.h               |   11 ++-
 kernel/trace/trace_events.c        |    9 +-
 kernel/trace/trace_events_filter.c |   61 +++++++++++-
 kernel/trace/trace_kprobe.c        |    6 ++
 11 files changed, 327 insertions(+), 4 deletions(-)
 create mode 100644 include/trace/bpf_trace.h
 create mode 100644 kernel/trace/bpf_trace_callbacks.c
include/linux/ftrace_event.h +3 -0
index 8c9b7a1..8d4a7a3 100644
@@ -203,6 +203,7 @@ enum {
 	TRACE_EVENT_FL_IGNORE_ENABLE_BIT,
 	TRACE_EVENT_FL_WAS_ENABLED_BIT,
 	TRACE_EVENT_FL_USE_CALL_FILTER_BIT,
+	TRACE_EVENT_FL_BPF_BIT,
 };
 
 /*
@@ -223,6 +224,7 @@ enum {
 	TRACE_EVENT_FL_IGNORE_ENABLE	= (1 << TRACE_EVENT_FL_IGNORE_ENABLE_BIT),
 	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_BPF		= (1 << TRACE_EVENT_FL_BPF_BIT),
 };
 
 struct ftrace_event_call {
@@ -347,6 +349,7 @@ extern int filter_check_discard(struct ftrace_event_file *file, void *rec,
 extern int call_filter_check_discard(struct ftrace_event_call *call, void *rec,
 				     struct ring_buffer *buffer,
 				     struct ring_buffer_event *event);
+extern void filter_call_bpf(struct event_filter *filter, struct pt_regs *regs);
 
 enum {
 	FILTER_OTHER = 0,
include/trace/bpf_trace.h new file +27 -0
new file mode 100644
index 0000000..99d1e4b
@@ -0,0 +1,27 @@
+/* Copyright (c) 2011-2013 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
+
+#include <linux/ptrace.h>
+
+struct bpf_context {
+	struct pt_regs regs;
+};
+
+void *bpf_load_pointer(void *unsafe_ptr);
+long bpf_memcmp(void *unsafe_ptr, void *safe_ptr, long size);
+void bpf_dump_stack(struct bpf_context *ctx);
+void bpf_trace_printk(char *fmt, long fmt_size,
+		      long arg1, long arg2, long arg3);
+void *bpf_table_lookup(struct bpf_context *ctx, long table_id, const void *key);
+long bpf_table_update(struct bpf_context *ctx, long table_id, const void *key,
+		      const void *leaf);
+
+extern struct bpf_callbacks bpf_trace_cb;
+
+#endif /* _LINUX_KERNEL_BPF_TRACE_H */
include/trace/ftrace.h +14 -0
index 5c38606..4054393 100644
@@ -17,6 +17,7 @@
  */
 
 #include <linux/ftrace_event.h>
+#include <linux/kexec.h>
 
 /*
  * DECLARE_EVENT_CLASS can be used to add a generic function
@@ -526,6 +527,11 @@ static inline notrace int ftrace_get_offsets_##call(			\
 #undef DECLARE_EVENT_CLASS
 #define DECLARE_EVENT_CLASS(call, proto, args, tstruct, assign, print)	\
 									\
+static noinline __noclone notrace void					\
+ftrace_raw_event_save_regs_##call(struct pt_regs *__regs, proto)	\
+{									\
+	crash_setup_regs(__regs, NULL);					\
+}									\
 static notrace void							\
 ftrace_raw_event_##call(void *__data, proto)				\
 {									\
@@ -543,6 +549,14 @@ ftrace_raw_event_##call(void *__data, proto)				\
 		     &ftrace_file->flags))				\
 		return;							\
 									\
+	if (unlikely(ftrace_file->flags & FTRACE_EVENT_FL_FILTERED) &&	\
+	    unlikely(ftrace_file->event_call->flags & TRACE_EVENT_FL_BPF)) { \
+		struct pt_regs __regs;					\
+		ftrace_raw_event_save_regs_##call(&__regs, args);	\
+		filter_call_bpf(ftrace_file->filter, &__regs);		\
+		return;							\
+	}								\
+									\
 	local_save_flags(irq_flags);					\
 	pc = preempt_count();						\
 									\
kernel/trace/Kconfig +1 -0
index 015f85a..2809cd1 100644
@@ -80,6 +80,7 @@ config FTRACE_NMI_ENTER
 
 config EVENT_TRACING
 	select CONTEXT_SWITCH_TRACER
+	select BPF64
 	bool
 
 config CONTEXT_SWITCH_TRACER
kernel/trace/Makefile +1 -0
index d7e2068..fe90d85 100644
@@ -50,6 +50,7 @@ ifeq ($(CONFIG_PERF_EVENTS),y)
 obj-$(CONFIG_EVENT_TRACING) += trace_event_perf.o
 endif
 obj-$(CONFIG_EVENT_TRACING) += trace_events_filter.o
+obj-$(CONFIG_EVENT_TRACING) += bpf_trace_callbacks.o
 obj-$(CONFIG_KPROBE_EVENT) += trace_kprobe.o
 obj-$(CONFIG_TRACEPOINTS) += power-traces.o
 ifeq ($(CONFIG_PM_RUNTIME),y)
kernel/trace/bpf_trace_callbacks.c new file +191 -0

191 lines not on this page · raw message

kernel/trace/trace.c +7 -0
index 9d20cd9..c052936 100644
@@ -1758,6 +1758,13 @@ void __trace_stack(struct trace_array *tr, unsigned long flags, int skip,
 	__ftrace_trace_stack(tr->trace_buffer.buffer, flags, skip, pc, NULL);
 }
 
+void __trace_stack_regs(unsigned long flags, int skip, int pc,
+			struct pt_regs *regs)
+{
+	__ftrace_trace_stack(global_trace.trace_buffer.buffer, flags, skip,
+			     pc, regs);
+}
+
 /**
  * trace_dump_stack - record a stack back trace in the trace buffer
  * @skip: Number of functions to skip (helper handlers)
kernel/trace/trace.h +10 -1
index ea189e0..33d26aff 100644
@@ -616,6 +616,8 @@ void ftrace_trace_userstack(struct ring_buffer *buffer, unsigned long flags,
 
 void __trace_stack(struct trace_array *tr, unsigned long flags, int skip,
 		   int pc);
+void __trace_stack_regs(unsigned long flags, int skip, int pc,
+			struct pt_regs *regs);
 #else
 static inline void ftrace_trace_stack(struct ring_buffer *buffer,
 				      unsigned long flags, int skip, int pc)
@@ -637,6 +639,10 @@ static inline void __trace_stack(struct trace_array *tr, unsigned long flags,
 				 int skip, int pc)
 {
 }
+static inline void __trace_stack_regs(unsigned long flags, int skip, int pc,
+				      struct pt_regs *regs)
+{
+}
 #endif /* CONFIG_STACKTRACE */
 
 extern cycle_t ftrace_now(int cpu);
@@ -936,12 +942,15 @@ struct ftrace_event_field {
 	int			is_signed;
 };
 
+struct bpf_program;
+
 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_program	*prog;
 };
 
 struct event_subsystem {
@@ -1014,7 +1023,7 @@ filter_parse_regex(char *buff, int len, char **search, int *not);
 extern void print_event_filter(struct ftrace_event_file *file,
 			       struct trace_seq *s);
 extern int apply_event_filter(struct ftrace_event_file *file,
-			      char *filter_string);
+			      char *filter_string, int filter_len);
 extern int apply_subsystem_event_filter(struct ftrace_subsystem_dir *dir,
 					char *filter_string);
 extern void print_subsystem_event_filter(struct event_subsystem *system,
kernel/trace/trace_events.c +8 -1
index f919a2e..deed25f 100644
@@ -1041,9 +1041,16 @@ event_filter_write(struct file *filp, const char __user *ubuf, size_t cnt,
 	mutex_lock(&event_mutex);
 	file = event_file_data(filp);
 	if (file)
-		err = apply_event_filter(file, buf);
+		err = apply_event_filter(file, buf, cnt);
 	mutex_unlock(&event_mutex);
 
+	if (file->event_call->flags & TRACE_EVENT_FL_BPF)
+		/*
+		 * allocate per-cpu printk buffers, since BPF program
+		 * might be calling bpf_trace_printk
+		 */
+		trace_printk_init_buffers();
+
 	free_page((unsigned long) buf);
 	if (err < 0)
 		return err;
kernel/trace/trace_events_filter.c +59 -2

97 lines not on this page · raw message

kernel/trace/trace_kprobe.c +6 -0
index dae9541..e1a2187 100644
@@ -819,6 +819,12 @@ __kprobe_trace_func(struct trace_probe *tp, struct pt_regs *regs,
 	if (test_bit(FTRACE_EVENT_FL_SOFT_DISABLED_BIT, &ftrace_file->flags))
 		return;
 
+	if (unlikely(ftrace_file->flags & FTRACE_EVENT_FL_FILTERED) &&
+	    unlikely(ftrace_file->event_call->flags & TRACE_EVENT_FL_BPF)) {
+		filter_call_bpf(ftrace_file->filter, regs);
+		return;
+	}
+
 	local_save_flags(irq_flags);
 	pc = preempt_count();
 
Signature · 1 line
1.7.9.5
#10 lore raw

Re: [RFC PATCH tip 4/5] use BPF in tracing filters

Quoted 11 lines · Alexei Starovoitov

Such filters can be written in C and allow safe read-only access to any kernel data structure.
Like systemtap but with safety guaranteed by kernel.

The user can do:
cat bpf_program > /sys/kernel/debug/tracing/.../filter if tracing event is either static or dynamic via kprobe_events.

The program can be anything as long as bpf_check() can verify its safety. For example, the user can create kprobe_event on dst_discard() and use logically following code inside BPF filter:

Quoted 7 lines
      skb = (struct sk_buff *)ctx->regs.di;
      dev = bpf_load_pointer(&skb->dev);

to access 'struct net_device'
Since its prototype is 'int dst_discard(struct sk_buff *skb);' 'skb' pointer is in 'rdi' register on x86_64 bpf_load_pointer() will try to fetch 'dev' field of 'sk_buff' structure and will suppress page-fault if pointer is incorrect.

Hmm, I doubt it is a good way to integrate with ftrace. I prefer to use this for replacing current ftrace filter, fetch functions and actions. In that case, we can continue to use current interface but much faster to trace. Also, we can see what filter/arguments/actions are set on each event.

Thank you,

Signature · 4 lines
Masami HIRAMATSU
IT Management Research Dept. Linux Technology Center
Hitachi, Ltd., Yokohama Research Laboratory
E-mail: [email protected]
maintainer
#11 lore raw

Re: [RFC PATCH tip 4/5] use BPF in tracing filters

Quoted 20 lines · On Wed, 04 Dec 2013 09:48:44 +0900 Masami Hiramatsu…
Quoted 11 lines · Alexei Starovoitov

Such filters can be written in C and allow safe read-only access to any kernel data structure.
Like systemtap but with safety guaranteed by kernel.

The user can do:
cat bpf_program > /sys/kernel/debug/tracing/.../filter if tracing event is either static or dynamic via kprobe_events.

The program can be anything as long as bpf_check() can verify its safety. For example, the user can create kprobe_event on dst_discard() and use logically following code inside BPF filter:

Quoted 7 lines
      skb = (struct sk_buff *)ctx->regs.di;
      dev = bpf_load_pointer(&skb->dev);

to access 'struct net_device'
Since its prototype is 'int dst_discard(struct sk_buff *skb);' 'skb' pointer is in 'rdi' register on x86_64 bpf_load_pointer() will try to fetch 'dev' field of 'sk_buff' structure and will suppress page-fault if pointer is incorrect.

Quoted 2 lines

Hmm, I doubt it is a good way to integrate with ftrace. I prefer to use this for replacing current ftrace filter,

I'm not sure how we can do that. Especially since the bpf is very arch specific, and the current filters work for all archs.

Quoted 4 lines

fetch functions and actions. In that case, we can continue to use current interface but much faster to trace. Also, we can see what filter/arguments/actions are set on each event.

There's also the problem that the current filters work with the results of what is written to the buffer, not what is passed in by the trace point, as that isn't even displayed to the user.

For example, sched_switch gets passed struct task_struct *prev, and *next, from that we save prev_comm, prev_pid, prev_prio, prev_state, next_comm, next_prio and next_state. These are expressed to the user by the format file of the event:

	field:char prev_comm[32];	offset:16;
	size:16;	signed:1; field:pid_t prev_pid;
	offset:32;	size:4;	signed:1; field:int
	prev_prio;	offset:36;	size:4;	signed:1;
	field:long prev_state;	offset:40;	size:8;
	signed:1; field:char next_comm[32];	offset:48;
	size:16;	signed:1; field:pid_t next_pid;
	offset:64;	size:4;	signed:1; field:int
	next_prio;	offset:68;	size:4; signed:1;

And the filters can check "next_prio > 10" and what not. The bpf program needs to access next->prio. There's nothing that shows the user what is passed to the tracepoint, and from that, what structure member to use from there. The user would be required to look at the source code of the given kernel. A requirement not needed by the current implementation.

Also, there's results that can not be trivially converted. Taking a quick look at some TRACE_EVENT() structures, I found bcache_bio that has this:

        TP_fast_assign(
                __entry->dev            = bio->bi_bdev->bd_dev;
                __entry->sector         = bio->bi_sector;
                __entry->nr_sector      = bio->bi_size >> 9;
                blk_fill_rwbs(__entry->rwbs, bio->bi_rw, bio->bi_size);
        ),

Where the blk_fill_rwbs() updates the status of the entry->rwbs based on the bi_rw field. A filter must remain backward compatible to something like:

	rwbs == "w"  or rwbs =~ '*w*'

Now maybe we can make the filter code use some of the bpf if possible, but to get the result, it still needs to write to the ring buffer, and discard it if it is incorrect. Which will not make it any faster than the original trace, but perhaps faster than the trace + current filter.

The speed up that was shown was because we were processing the parameters of the trace point and not the result. That currently requires the user to have full access to the source of the kernel they are tracing.

-- Steve

#12 lore raw

Re: [RFC PATCH tip 4/5] use BPF in tracing filters

Quoted 23 lines · Steven Rostedt
Quoted 20 lines · On Wed, 04 Dec 2013 09:48:44 +0900 Masami Hiramatsu…
Quoted 18 lines · Alexei Starovoitov

Such filters can be written in C and allow safe read-only access to any kernel data structure.
Like systemtap but with safety guaranteed by kernel.

The user can do:
cat bpf_program > /sys/kernel/debug/tracing/.../filter if tracing event is either static or dynamic via kprobe_events.

The program can be anything as long as bpf_check() can verify its safety. For example, the user can create kprobe_event on dst_discard() and use logically following code inside BPF filter:

      skb = (struct sk_buff *)ctx->regs.di;
      dev = bpf_load_pointer(&skb->dev);

to access 'struct net_device'
Since its prototype is 'int dst_discard(struct sk_buff *skb);' 'skb' pointer is in 'rdi' register on x86_64 bpf_load_pointer() will try to fetch 'dev' field of 'sk_buff' structure and will suppress page-fault if pointer is incorrect.

Quoted 5 lines
Quoted 2 lines

Hmm, I doubt it is a good way to integrate with ftrace. I prefer to use this for replacing current ftrace filter,

I'm not sure how we can do that. Especially since the bpf is very arch specific, and the current filters work for all archs.

My idea is to use BPF for the arch specific optimization for ftrace filter. For the other arch, filter works with current code. So the ftrace holds filter_preds and compile it in BPF bytecode if possible.
And this backend optimization also can be done for fetch methods.

Quoted 8 lines
Quoted 4 lines

fetch functions and actions. In that case, we can continue to use current interface but much faster to trace. Also, we can see what filter/arguments/actions are set on each event.

There's also the problem that the current filters work with the results of what is written to the buffer, not what is passed in by the trace point, as that isn't even displayed to the user.

Agreed, so I've said I doubt this implementation is a good shape to integrate. Ktap style is better, since it just gets parameters from perf buffer entry (using event format).

Thank you,

Signature · 4 lines
Masami HIRAMATSU
IT Management Research Dept. Linux Technology Center
Hitachi, Ltd., Yokohama Research Laboratory
E-mail: [email protected]
#13 lore raw

Re: [RFC PATCH tip 4/5] use BPF in tracing filters

Quoted 9 lines · Masami Hiramatsu
Quoted 8 lines · Steven Rostedt
Quoted 4 lines · On Wed, 04 Dec 2013 09:48:44 +0900 Masami Hiramatsu…

fetch functions and actions. In that case, we can continue to use current interface but much faster to trace. Also, we can see what filter/arguments/actions are set on each event.

Quoted 7 lines
Quoted 3 lines

There's also the problem that the current filters work with the results of what is written to the buffer, not what is passed in by the trace point, as that isn't even displayed to the user.

Agreed, so I've said I doubt this implementation is a good shape to integrate. Ktap style is better, since it just gets parameters from perf buffer entry (using event format).

Are you saying always store all arguments into ring buffer and let filter run on it?
It's slower, but it's cleaner, because of human readable? since ktap arg1 matches first
argument of tracepoint is better than doing ctx->regs.di ? Sure. si->arg1 is easy to fix.
With si->arg1 tweak the bpf will become architecture independent. It will run through JIT on x86 and through interpreter everywhere else. but for kprobes user have to specify 'var=cpu_register' during probe creation… how is it better than doing the same in filter? I'm open to suggestions on how to improve the usability.

Thanks
Alexei

#14 lore raw

Re: [RFC PATCH tip 4/5] use BPF in tracing filters

Quoted 15 lines · Alexei Starovoitov
Quoted 13 lines · Masami Hiramatsu
Quoted 11 lines · Steven Rostedt
Quoted 4 lines · On Wed, 04 Dec 2013 09:48:44 +0900 Masami Hiramatsu…

fetch functions and actions. In that case, we can continue to use current interface but much faster to trace. Also, we can see what filter/arguments/actions are set on each event.

There's also the problem that the current filters work with the results of what is written to the buffer, not what is passed in by the trace point, as that isn't even displayed to the user.

Quoted 6 lines
Quoted 3 lines

Agreed, so I've said I doubt this implementation is a good shape to integrate. Ktap style is better, since it just gets parameters from perf buffer entry (using event format).

Are you saying always store all arguments into ring buffer and let filter run on it?

Yes, it is what ftrace does. I doubt your way fits all of the existing trace-event macros. However, I think just for dynamic events, you can integrating the argument fetching and filtering.

Quoted 8 lines

It's slower, but it's cleaner, because of human readable? since ktap arg1 matches first
argument of tracepoint is better than doing ctx->regs.di ? Sure. si->arg1 is easy to fix.
With si->arg1 tweak the bpf will become architecture independent. It will run through JIT on x86 and through interpreter everywhere else. but for kprobes user have to specify 'var=cpu_register' during probe creation… how is it better than doing the same in filter?

Haven't you used perf-probe yet? It already supports such kind of translation from kernel local variable name to registers, offsets, and dereference. :) And kprobe-events can parse such arguments into method chain. See Documentation/trace/kprobetrace.txt and tools/perf/Documentation/perf-probe.txt for more detail. Anyway, I'd like to use the bpf for re-implementing fetch method. :)

Thank you,

Signature · 4 lines
Masami HIRAMATSU
IT Management Research Dept. Linux Technology Center
Hitachi, Ltd., Yokohama Research Laboratory
E-mail: [email protected]
#15 lore raw

Re: [RFC PATCH tip 4/5] use BPF in tracing filters

Quoted 20 lines · Masami Hiramatsu
Quoted 19 lines · Alexei Starovoitov
Quoted 16 lines · Masami Hiramatsu
Quoted 11 lines · Steven Rostedt
Quoted 4 lines · On Wed, 04 Dec 2013 09:48:44 +0900 Masami Hiramatsu…

fetch functions and actions. In that case, we can continue to use current interface but much faster to trace. Also, we can see what filter/arguments/actions are set on each event.

There's also the problem that the current filters work with the results of what is written to the buffer, not what is passed in by the trace point, as that isn't even displayed to the user.

Agreed, so I've said I doubt this implementation is a good shape to integrate. Ktap style is better, since it just gets parameters from perf buffer entry (using event format).

Quoted 7 lines
Quoted 2 lines

Are you saying always store all arguments into ring buffer and let filter run on it?

Yes, it is what ftrace does. I doubt your way fits all of the existing trace-event macros. However, I think just for dynamic events, you can integrating the argument fetching and filtering.

Does this will affect the user interface of perf-probe argument fetching?

I mean if use bpf backend, do we must need gcc to compile bpf source for perf-probe argument fetching? as we known, current argument fetching is go through kprobe_events/uprobe_events debugfs file, and ktap is based on this behavior.

Thanks.

Jovi.

Quoted 25 lines
Quoted 8 lines

It's slower, but it's cleaner, because of human readable? since ktap arg1 matches first
argument of tracepoint is better than doing ctx->regs.di ? Sure. si->arg1 is easy to fix.
With si->arg1 tweak the bpf will become architecture independent. It will run through JIT on x86 and through interpreter everywhere else. but for kprobes user have to specify 'var=cpu_register' during probe creation… how is it better than doing the same in filter?

Haven't you used perf-probe yet? It already supports such kind of translation from kernel local variable name to registers, offsets, and dereference. :) And kprobe-events can parse such arguments into method chain. See Documentation/trace/kprobetrace.txt and tools/perf/Documentation/perf-probe.txt for more detail. Anyway, I'd like to use the bpf for re-implementing fetch method. :)

Thank you,

--
Masami HIRAMATSU
IT Management Research Dept. Linux Technology Center Hitachi, Ltd., Yokohama Research Laboratory
E-mail: [email protected]

#16 lore raw

Re: [RFC PATCH tip 4/5] use BPF in tracing filters

Quoted 29 lines · Jovi Zhangwei
Quoted 20 lines · Masami Hiramatsu
Quoted 19 lines · Alexei Starovoitov
Quoted 16 lines · Masami Hiramatsu
Quoted 11 lines · Steven Rostedt
Quoted 4 lines · On Wed, 04 Dec 2013 09:48:44 +0900 Masami Hiramatsu…

fetch functions and actions. In that case, we can continue to use current interface but much faster to trace. Also, we can see what filter/arguments/actions are set on each event.

There's also the problem that the current filters work with the results of what is written to the buffer, not what is passed in by the trace point, as that isn't even displayed to the user.

Agreed, so I've said I doubt this implementation is a good shape to integrate. Ktap style is better, since it just gets parameters from perf buffer entry (using event format).

Quoted 7 lines
Quoted 2 lines

Are you saying always store all arguments into ring buffer and let filter run on it?

Yes, it is what ftrace does. I doubt your way fits all of the existing trace-event macros. However, I think just for dynamic events, you can integrating the argument fetching and filtering.

Quoted 6 lines

Does this will affect the user interface of perf-probe argument fetching?

I mean if use bpf backend, do we must need gcc to compile bpf source for perf-probe argument fetching? as we known, current argument fetching is go through kprobe_events/uprobe_events debugfs file, and ktap is based on this behavior.

No, I don't want to do that. Feeding binary code into the kernel is not trusted nor controllable. I'd just like to see the code which optimizing current fetching/filtering methods, and that is possible.

Anyway, as far as I can see, there looks be two different models of tracing in our mind.

A) Fixed event based tracing: In this model, there are several fixed "events" which well defined with fixed arguments. tracer handles these events and only use limited arguments. It's like a packet stream processing. ftrace, perf etc. are used this model.

B) Flexible event-point tracing: In this model, each tracer(or even trace user) can freely define their own event, there will be some fixed tracing points defined, but arguments are defined by users. It's like a debugger's breakpoint debugging. systemtap, ktap etc. are used this model.

Of course, both have pros/cons, and can share some fundamental features. e.g. B model has a good flexibility and A model is easy to use for beginners.

I think we'd better not integrate these two, but find the better way to share each functionality.

Thank you,

Signature · 4 lines
Masami HIRAMATSU
IT Management Research Dept. Linux Technology Center
Hitachi, Ltd., Yokohama Research Laboratory
E-mail: [email protected]
#17 lore raw

Re: [RFC PATCH tip 4/5] use BPF in tracing filters

Quoted 9 lines · masami.hiramatsu.pt

[...]
Anyway, as far as I can see, there looks be two different models of tracing in our mind.

A) Fixed event based tracing: In this model, there are several fixed "events" which well defined with fixed arguments. tracer handles these events and only use limited arguments. It's like a packet stream processing. ftrace, perf etc. are used this model.

Quoted 4 lines

B) Flexible event-point tracing: In this model, each tracer(or even trace user) can freely define their own event, there will be some fixed tracing points defined, but arguments are defined by users. It's like a debugger's breakpoint debugging. systemtap, ktap etc. are used this model.

It may be more useful to think of it as a contrast along the hard-coded versus programmable axis. (perf, systemtap, and ktap can each reach to some extent across your "fixed" vs "flexible" line. Each has some dynamic and some static-tracepoint capability.)

Quoted 2 lines

e.g. B model has a good flexibility and A model is easy to use for beginners.

I don't think it's the model that dictates ease-of-use, but the quality of implementation, logistics, documentation, and examples.

- FChE

#18 lore raw

Re: [RFC PATCH tip 4/5] use BPF in tracing filters

Quoted 17 lines · Frank Ch. Eigler
Quoted 9 lines · masami.hiramatsu.pt

[...]
Anyway, as far as I can see, there looks be two different models of tracing in our mind.

A) Fixed event based tracing: In this model, there are several fixed "events" which well defined with fixed arguments. tracer handles these events and only use limited arguments. It's like a packet stream processing. ftrace, perf etc. are used this model.

Quoted 4 lines

B) Flexible event-point tracing: In this model, each tracer(or even trace user) can freely define their own event, there will be some fixed tracing points defined, but arguments are defined by users. It's like a debugger's breakpoint debugging. systemtap, ktap etc. are used this model.

Quoted 4 lines

It may be more useful to think of it as a contrast along the hard-coded versus programmable axis. (perf, systemtap, and ktap can each reach to some extent across your "fixed" vs "flexible" line. Each has some dynamic and some static-tracepoint capability.)

Oh, I meant that B is not tend to share the defined event among different tracing instances. Each instances defines new different dynamic events and gets memories and registers freely. OTOH, the Ftrace and LTT models are based on the fixed, shared and well defined events. Even if a new dynamic event is defined, it will be shared by every instances.

Quoted 6 lines
Quoted 3 lines

e.g. B model has a good flexibility and A model is easy to use for beginners.

I don't think it's the model that dictates ease-of-use, but the quality of implementation, logistics, documentation, and examples.

Of course, but it requires learning the new programming way. And also, we need to know about the target source code for setting up new events. I know that the systemtap provides many pre-defined probepoints. so, the systemtap may already have solved this kind of issue. ;)

Thank you,

Signature · 4 lines
Masami HIRAMATSU
IT Management Research Dept. Linux Technology Center
Hitachi, Ltd., Yokohama Research Laboratory
E-mail: [email protected]
#19 lore raw

RFC PATCH 5/5 tracing filter examples in BPF

In reply to Alexei Starovoitov

filter_ex1: filter that prints events for loobpack device only

$ cat filter_ex1.bpf > /sys/kernel/debug/tracing/events/net/netif_receive_skb/filter
$ echo 1 > /sys/kernel/debug/tracing/events/net/netif_receive_skb/enable
$ ping -c1 localhost
$ cat /sys/kernel/debug/tracing/trace_pip
            ping-5913  [003] ..s2  3779.285726: __netif_receive_skb_core: skb ffff880808e3a300 dev ffff88080bbf8000
            ping-5913  [003] ..s2  3779.285744: __netif_receive_skb_core: skb ffff880808e3a900 dev ffff88080bbf8000

To pre-check correctness of the filter do:

$ trace_filter_check filter_ex1.bpf
(final filter check always happens in kernel)

bpf/llvm - placeholder for LLVM-BPF backend

---
GCC-BPF backend is available on github
(since gcc plugin infrastructure doesn't allow for out-of-tree backends)

LLVM plugin infra is very flexible.
LLVM-BPF backend is reusing 'LLVM target independent code generator' and currently it's work in progress. It can be built out of LLVM tree. The user would need to 'apt-get install llvm-3.x-dev'
which will bring llvm headers and static libraries
and then compile BPF backend only.

Both compilers can compile C into BPF instruction set.

 tools/bpf/llvm/README.txt            |    6 +++
 tools/bpf/trace/Makefile             |   34 ++++++++++++++
 tools/bpf/trace/README.txt           |   15 +++++++
 tools/bpf/trace/filter_ex1.c         |   52 +++++++++++++++++++++
 tools/bpf/trace/filter_ex1_orig.c    |   23 ++++++++++
 tools/bpf/trace/filter_ex2.c         |   74 ++++++++++++++++++++++++++++++
 tools/bpf/trace/filter_ex2_orig.c    |   47 +++++++++++++++++++
 tools/bpf/trace/trace_filter_check.c |   82 ++++++++++++++++++++++++++++++++++
 8 files changed, 333 insertions(+)
 create mode 100644 tools/bpf/llvm/README.txt
 create mode 100644 tools/bpf/trace/Makefile
 create mode 100644 tools/bpf/trace/README.txt
 create mode 100644 tools/bpf/trace/filter_ex1.c
 create mode 100644 tools/bpf/trace/filter_ex1_orig.c
 create mode 100644 tools/bpf/trace/filter_ex2.c
 create mode 100644 tools/bpf/trace/filter_ex2_orig.c
 create mode 100644 tools/bpf/trace/trace_filter_check.c
tools/bpf/llvm/README.txt new file +6 -0
new file mode 100644
index 0000000..3ca3ece
@@ -0,0 +1,6 @@
+placeholder for LLVM BPF backend:
+lib/Target/BPF/*.cpp
+
+prerequisites:
+apt-get install llvm-3.[23]-dev
+
tools/bpf/trace/Makefile new file +34 -0
new file mode 100644
index 0000000..b63f974
@@ -0,0 +1,34 @@
+CC = gcc
+
+all: trace_filter_check filter_ex1.bpf filter_ex2.bpf
+
+srctree=../../..
+src-perf=../../perf
+
+CFLAGS += -I$(src-perf)/util/include
+CFLAGS += -I$(src-perf)/arch/$(ARCH)/include
+CFLAGS += -I$(srctree)/arch/$(ARCH)/include/uapi
+CFLAGS += -I$(srctree)/arch/$(ARCH)/include
+CFLAGS += -I$(srctree)/include/uapi
+CFLAGS += -I$(srctree)/include
+CFLAGS += -Wall -O2
+
+trace_filter_check: LDLIBS = -Wl,--unresolved-symbols=ignore-all
+trace_filter_check: trace_filter_check.o \
+	$(srctree)/kernel/bpf_jit/bpf_check.o \
+	$(srctree)/kernel/bpf_jit/bpf_run.o \
+	$(srctree)/kernel/trace/bpf_trace_callbacks.o
+
+filter_ex1: filter_ex1.o
+filter_ex1.bpf: filter_ex1
+	./filter_ex1 > filter_ex1.bpf
+	rm filter_ex1
+
+filter_ex2: filter_ex2.o
+filter_ex2.bpf: filter_ex2
+	./filter_ex2 > filter_ex2.bpf
+	rm filter_ex2
+
+clean:
+	rm -rf *.o *.bpf trace_filter_check filter_ex1 filter_ex2
+
tools/bpf/trace/README.txt new file +15 -0
new file mode 100644
index 0000000..7c1fcb9
@@ -0,0 +1,15 @@
+Tracing filter examples
+
+filter_ex1: tracing filter example that prints events for loobpack device only
+
+$ cat filter_ex1.bpf > /sys/kernel/debug/tracing/events/net/netif_receive_skb/filter
+$ echo 1 > /sys/kernel/debug/tracing/events/net/netif_receive_skb/enable
+$ ping -c1 localhost
+$ cat /sys/kernel/debug/tracing/trace_pip
+            ping-5913  [003] ..s2  3779.285726: __netif_receive_skb_core: skb ffff880808e3a300 dev ffff88080bbf8000
+            ping-5913  [003] ..s2  3779.285744: __netif_receive_skb_core: skb ffff880808e3a900 dev ffff88080bbf8000
+
+To pre-check correctness of the filter do:
+$ trace_filter_check filter_ex1.bpf
+(final filter check always happens in kernel)
+
tools/bpf/trace/filter_ex1.c new file +52 -0

52 lines not on this page · raw message

tools/bpf/trace/filter_ex1_orig.c new file +23 -0
new file mode 100644
index 0000000..e670a82
@@ -0,0 +1,23 @@
+/*
+ * tracing filter example
+ * if attached to /sys/kernel/debug/tracing/events/net/netif_receive_skb
+ * it will print events for loobpack device only
+ */
+#include <linux/skbuff.h>
+#include <linux/netdevice.h>
+#include <linux/bpf.h>
+#include <trace/bpf_trace.h>
+
+void filter(struct bpf_context *ctx)
+{
+	char devname[4] = "lo";
+	struct net_device *dev;
+	struct sk_buff *skb = 0;
+
+	skb = (struct sk_buff *)ctx->regs.si;
+	dev = bpf_load_pointer(&skb->dev);
+	if (bpf_memcmp(dev->name, devname, 2) == 0) {
+		char fmt[] = "skb %p dev %p \n";
+		bpf_trace_printk(fmt, sizeof(fmt), (long)skb, (long)dev, 0);
+	}
+}
tools/bpf/trace/filter_ex2.c new file +74 -0

74 lines not on this page · raw message

tools/bpf/trace/filter_ex2_orig.c new file +47 -0

47 lines not on this page · raw message

tools/bpf/trace/trace_filter_check.c new file +82 -0

82 lines not on this page · raw message

Signature · 1 line
1.7.9.5
maintainer
#20 lore raw

Re: [RFC PATCH tip 5/5] tracing filter examples in BPF

Quoted 2 lines · On Mon, 2 Dec 2013 20:28:50 -0800 Alexei Starovoitov <[email protected]> wrote:

GCC-BPF backend is available on github
(since gcc plugin infrastructure doesn't allow for out-of-tree backends)

Do you have a pointer to where this backend can be found? I've done a bit of digging around but seem to be unable to find it...

Thanks,

jon

#21 lore raw

Re: [RFC PATCH tip 5/5] tracing filter examples in BPF

Quoted 8 lines · Jonathan Corbet
Quoted 2 lines · On Mon, 2 Dec 2013 20:28:50 -0800 Alexei Starovoitov <[email protected]> wrote:

GCC-BPF backend is available on github
(since gcc plugin infrastructure doesn't allow for out-of-tree backends)

Do you have a pointer to where this backend can be found? I've done a bit of digging around but seem to be unable to find it…

here it is:
https://github.com/iovisor/bpf_gcc/commit/9e7223f8f09c822ecc6e18309e89a574a23dbf63

It's quite small comparing to normal backend:

 config.me                          |    3 +
 config.sub                         |   12 +-
 gcc/common/config/bpf/bpf-common.c |   39 ++
 gcc/config.gcc                     |   18 +
 gcc/config/bpf/bpf-modes.def       |   22 +
 gcc/config/bpf/bpf-protos.h        |   60 ++
 gcc/config/bpf/bpf.c               | 1063 ++++++++++++++++++++++++++++++++++++
 gcc/config/bpf/bpf.h               |  746 +++++++++++++++++++++++++
 gcc/config/bpf/bpf.md              |  895 ++++++++++++++++++++++++++++++
 gcc/config/bpf/linux.h             |   67 +++
 10 files changed, 2922 insertions(+), 3 deletions(-)

Instruction emission is in bpf.md in functions like:
(define_insn "adddi3"
[(set (match_operand:DI 0 "int_reg_operand" "=r, r") (plus:DI (match_operand:DI 1 "int_reg_operand" "0, 0")

    (match_operand:DI 2 "int_reg_or_const_operand" "r, K")))]

""
"@
BPF_INSN_ALU(BPF_ADD, %0, %2), // %0 += %2 BPF_INSN_ALU_IMM(BPF_ADD, %0, %2), // %0 += %2"
[(set_attr "type" "arith,arith") ])

So it takes C and emits BPF_* macros from include/linux/bpf.h tools/bpf/trace/ examples were generated by it.
Eventually it will be changed to emit binary hex directly, but macros are much easier to understand for now.

Thanks
Alexei

#22 lore raw
In reply to Alexei Starovoitov
Quoted 7 lines · Alexei Starovoitov

Hi All,

the following set of patches adds BPF support to trace filters.

Trace filters can be written in C and allow safe read-only access to any kernel data structure. Like systemtap but with safety guaranteed by kernel.

Very cool! (Added various other folks who might be interested in this to the Cc: list.)

I have one generic concern:

It would be important to make it easy to extract loaded BPF code from the kernel in source code equivalent form, which compiles to the same BPF code.

I.e. I think it would be fundamentally important to make sure that this is all within the kernel's license domain, to make it very clear there can be no 'binary only' BPF scripts.

By up-loading BPF into a kernel the person loading it agrees to make that code available to all users of that system who can access it, under the same license as the kernel's code (or under a more permissive license).

The last thing we want is people getting funny ideas and writing drivers in BPF and hiding the code or making license claims over it
...

I.e. we want to allow flexible plugins technologically, but make sure people who run into such a plugin can modify and improve it under the same license as they can modify and improve the kernel itself!

[ People can still 'hide' their sekrit plugins if they want to, by not
distributing them to anyone who'd redistribute it widely. ]

Quoted 46 lines

The user can do:
cat bpf_program > /sys/kernel/debug/tracing/.../filter if tracing event is either static or dynamic via kprobe_events.

The filter program may look like:
void filter(struct bpf_context *ctx)

{
        char devname[4] = "eth5";
        struct net_device *dev;
        struct sk_buff *skb = 0;

        dev = (struct net_device *)ctx->regs.si;
        if (bpf_memcmp(dev->name, devname, 4) == 0) {
                char fmt[] = "skb %p dev %p eth5\n";
                bpf_trace_printk(fmt, skb, dev, 0, 0);
        }
}

The kernel will do static analysis of bpf program to make sure that it cannot crash the kernel (doesn't have loops, valid memory/register accesses, etc). Then kernel will map bpf instructions to x86 instructions and let it run in the place of trace filter.

To demonstrate performance I did a synthetic test:

        dev = init_net.loopback_dev;
        do_gettimeofday(&start_tv);
        for (i = 0; i < 1000000; i++) {
                struct sk_buff *skb;
                skb = netdev_alloc_skb(dev, 128);
                kfree_skb(skb);
        }
        do_gettimeofday(&end_tv);
        time = end_tv.tv_sec - start_tv.tv_sec;
        time *= USEC_PER_SEC;
        time += (long long)((long)end_tv.tv_usec - (long)start_tv.tv_usec);

        printk("1M skb alloc/free %lld (usecs)\n", time);

no tracing

[   33.450966] 1M skb alloc/free 145179 (usecs)

echo 1 > enable

[   97.186379] 1M skb alloc/free 240419 (usecs)

(tracing slows down kfree_skb() due to event_buffer_lock/buffer_unlock_commit)

Quoted 8 lines

echo 'name==eth5' > filter

[  139.644161] 1M skb alloc/free 302552 (usecs)

(running filter_match_preds() for every skb and discarding event_buffer is even slower)

cat bpf_prog > filter

[  171.150566] 1M skb alloc/free 199463 (usecs)

(JITed bpf program is safely checking dev->name == eth5 and discarding)

So, to do the math:

tracing 'all' overhead: 95 nsecs per event
tracing 'eth5 + old filter' overhead: 157 nsecs per event
tracing 'eth5 + BPF filter' overhead: 54 nsecs per event

So via BPF and a fairly trivial filter, we are able to reduce tracing overhead for real - while old-style filters.

In addition to that we now also have arbitrary BPF scripts, full C programs (or written in any other language from which BPF bytecode can be generated) enabled.

Seems like a massive win-win scenario to me ;-)

Quoted 33 lines

echo 0 > enable

[  258.073593] 1M skb alloc/free 144919 (usecs)

(tracing is disabled, performance is back to original)

The C program compiled into BPF and then JITed into x86 is faster than filter_match_preds() approach (199-145 msec vs 302-145 msec)

tracing+bpf is a tool for safe read-only access to variables without recompiling the kernel and without affecting running programs.

BPF filters can be written manually (see tools/bpf/trace/filter_ex1.c) or better compiled from restricted C via GCC or LLVM

Q: What is the difference between existing BPF and extended BPF? A:
Existing BPF insn from uapi/linux/filter.h
struct sock_filter {

        __u16   code;   /* Actual filter code */
        __u8    jt;     /* Jump true */
        __u8    jf;     /* Jump false */
        __u32   k;      /* Generic multiuse field */

};

Extended BPF insn from linux/bpf.h

struct bpf_insn {
        __u8    code;    /* opcode */
        __u8    a_reg:4; /* dest register*/
        __u8    x_reg:4; /* source register */
        __s16   off;     /* signed offset */
        __s32   imm;     /* signed immediate constant */
};
Quoted 8 lines

opcode encoding is the same between old BPF and extended BPF. Original BPF has two 32-bit registers.
Extended BPF has ten 64-bit registers.
That is the main difference.

Old BPF was using jt/jf fields for jump-insn only.
New BPF combines them into generic 'off' field for jump and non-jump insns. k==imm field has the same meaning.

This only affects the internal JIT representation, not the BPF byte code, right?

Quoted 1 line
 32 files changed, 3332 insertions(+), 24 deletions(-)

Impressive!

I'm wondering, will the new nftable code in works make use of the BPF JIT as well, or is that a separate implementation?

Thanks,

Ingo

maintainer
#23 lore raw
Quoted 8 lines · On Tue, 3 Dec 2013 10:16:55 +0100 Ingo Molnar <[email protected]> wrote:

So, to do the math:

tracing 'all' overhead: 95 nsecs per event
tracing 'eth5 + old filter' overhead: 157 nsecs per event
tracing 'eth5 + BPF filter' overhead: 54 nsecs per event

So via BPF and a fairly trivial filter, we are able to reduce tracing overhead for real - while old-style filters.

Yep, seems that BPF can do what I wasn't able to do with the normal filters. Although, I haven't looked at the code yet, I'm assuming that the BPF works on the parameters passed into the trace event. The normal filters can only process the results of the trace (what's being recorded) not the parameters of the trace event itself. To get what's recorded, we need to write to the buffer first, and then we decided if we want to keep the event or not and discard the event from the buffer if we do not.

That method does not reduce overhead at all, and only adds to it, as Alexei's tests have shown. The purpose of the filter was not to reduce overhead, but to reduce filling the buffer with needless data.

It looks as if the BPF filter works on the parameters of the trace event and not what is written to the buffers (as they can be different). I've been looking for a way to do just that, and if this does accomplish it, I'll be very happy :-)

-- Steve

#24 lore raw
Quoted 22 lines · Steven Rostedt
Quoted 8 lines · On Tue, 3 Dec 2013 10:16:55 +0100 Ingo Molnar <[email protected]> wrote:

So, to do the math:

tracing 'all' overhead: 95 nsecs per event
tracing 'eth5 + old filter' overhead: 157 nsecs per event
tracing 'eth5 + BPF filter' overhead: 54 nsecs per event

So via BPF and a fairly trivial filter, we are able to reduce tracing overhead for real - while old-style filters.

Yep, seems that BPF can do what I wasn't able to do with the normal filters. Although, I haven't looked at the code yet, I'm assuming that the BPF works on the parameters passed into the trace event. The normal filters can only process the results of the trace (what's being recorded) not the parameters of the trace event itself. To get what's recorded, we need to write to the buffer first, and then we decided if we want to keep the event or not and discard the event from the buffer if we do not.

Quoted 3 lines

That method does not reduce overhead at all, and only adds to it, as Alexei's tests have shown. The purpose of the filter was not to reduce overhead, but to reduce filling the buffer with needless data.

Precisely.
Assumption is that filters will filter out majority of the events. So filter takes pt_regs as input, has to interpret them and call bpf_trace_printk
if it really wants to store something for the human to see. We can extend bpf trace filters to return true/false to indicate whether TP_printk-format
specified as part of the event should be printed as well, but imo that's unnecessary.
When I was using bpf filters to debug networking bits I didn't need that printk format of the event. I only used event as an entry point, filtering out things and printing different fields vs initial event. More like what developers do when they sprinkle trace_printk/dump_stack through the code while debugging.

the only inconvenience so far is to know how parameters are getting into registers.
on x86-64, arg1 is in rdi, arg2 is in rsi,... I want to improve that after first step is done.
In the proposed patches bpf_context == pt_regs at the event entry point. Would be cleaner to have struct {arg1,arg2,…} as bpf_context instead. But that needed more code and I wanted to keep the first patch to the minimum.

#25 lore raw
Quoted 42 lines · Alexei Starovoitov
Quoted 22 lines · Steven Rostedt
Quoted 8 lines · On Tue, 3 Dec 2013 10:16:55 +0100 Ingo Molnar <[email protected]> wrote:

So, to do the math:

tracing 'all' overhead: 95 nsecs per event
tracing 'eth5 + old filter' overhead: 157 nsecs per event
tracing 'eth5 + BPF filter' overhead: 54 nsecs per event

So via BPF and a fairly trivial filter, we are able to reduce tracing overhead for real - while old-style filters.

Yep, seems that BPF can do what I wasn't able to do with the normal filters. Although, I haven't looked at the code yet, I'm assuming that the BPF works on the parameters passed into the trace event. The normal filters can only process the results of the trace (what's being recorded) not the parameters of the trace event itself. To get what's recorded, we need to write to the buffer first, and then we decided if we want to keep the event or not and discard the event from the buffer if we do not.

Quoted 3 lines

That method does not reduce overhead at all, and only adds to it, as Alexei's tests have shown. The purpose of the filter was not to reduce overhead, but to reduce filling the buffer with needless data.

Precisely.
Assumption is that filters will filter out majority of the events. So filter takes pt_regs as input, has to interpret them and call bpf_trace_printk
if it really wants to store something for the human to see. We can extend bpf trace filters to return true/false to indicate whether TP_printk-format
specified as part of the event should be printed as well, but imo that's unnecessary.
When I was using bpf filters to debug networking bits I didn't need that printk format of the event. I only used event as an entry point, filtering out things and printing different fields vs initial event. More like what developers do when they sprinkle trace_printk/dump_stack through the code while debugging.

Quoted 4 lines

the only inconvenience so far is to know how parameters are getting into registers.
on x86-64, arg1 is in rdi, arg2 is in rsi,... I want to improve that after first step is done.

Actually, that part is done by the perf-probe and ftrace dynamic events (kernel/trace/trace_probe.c). I think this generic BPF is good for re-implementing fetch methods. :)

Thank you,

Signature · 4 lines
Masami HIRAMATSU
IT Management Research Dept. Linux Technology Center
Hitachi, Ltd., Yokohama Research Laboratory
E-mail: [email protected]
#26 lore raw

Hi Masami,

Quoted 9 lines · Masami Hiramatsu
Quoted 4 lines · Alexei Starovoitov

the only inconvenience so far is to know how parameters are getting into registers.
on x86-64, arg1 is in rdi, arg2 is in rsi,... I want to improve that after first step is done.

Actually, that part is done by the perf-probe and ftrace dynamic events (kernel/trace/trace_probe.c). I think this generic BPF is good for re-implementing fetch methods. :)

For implementing patch method, it seems that it needs to access to user memory, stack and/or current (task_struct - for utask or vma later) from the BPF VM as well. Isn't it OK from the security perspective?

Anyway, I'll take a look at it later if I have time, but I want to get the existing/pending implementation merged first. :)

Thanks,
Namhyung

#27 lore raw
Quoted 9 lines · Namhyung Kim

Hi Masami,

Quoted 6 lines · Masami Hiramatsu
Quoted 4 lines · Alexei Starovoitov

the only inconvenience so far is to know how parameters are getting into registers.
on x86-64, arg1 is in rdi, arg2 is in rsi,... I want to improve that after first step is done.

Quoted 7 lines
Quoted 3 lines

Actually, that part is done by the perf-probe and ftrace dynamic events (kernel/trace/trace_probe.c). I think this generic BPF is good for re-implementing fetch methods. :)

For implementing patch method, it seems that it needs to access to user memory, stack and/or current (task_struct - for utask or vma later) from the BPF VM as well. Isn't it OK from the security perspective?

Would you mean security or safety? :)
For safety, I think we can check the BPF binary doesn't break anything. Anyway, for fetch method, I think we have to make a generic syntax tree for the archs which don't support BPF, and BPF bytecode will be generated by the syntax tree. IOW, I'd like to use BPF just for optimizing memory address calculation.
For security, it is hard to check what is the sensitive information in the kernel, I think it should be restricted to root user a while.

Quoted 2 lines

Anyway, I'll take a look at it later if I have time, but I want to get the existing/pending implementation merged first. :)

Yes, of course ! :)

Thank you,

Signature · 4 lines
Masami HIRAMATSU
IT Management Research Dept. Linux Technology Center
Hitachi, Ltd., Yokohama Research Laboratory
E-mail: [email protected]
#28 lore raw
In reply to Ingo Molnar
Quoted 14 lines · Ingo Molnar

Very cool! (Added various other folks who might be interested in this to the Cc: list.)

I have one generic concern:

It would be important to make it easy to extract loaded BPF code from the kernel in source code equivalent form, which compiles to the same BPF code.

I.e. I think it would be fundamentally important to make sure that this is all within the kernel's license domain, to make it very clear there can be no 'binary only' BPF scripts.

Quoted 7 lines

By up-loading BPF into a kernel the person loading it agrees to make that code available to all users of that system who can access it, under the same license as the kernel's code (or under a more permissive license).

The last thing we want is people getting funny ideas and writing drivers in BPF and hiding the code or making license claims over it

all makes sense.
In case of kernel modules all export_symbols are accessible and module has to have kernel compatible license. Same licensing terms apply to anything else that interacts with kernel functions.
In case of BPF the list of accessible functions is tiny, so it's much easier to enforce specific limited use case.
For tracing filters it's just bpf_load_xx/trace_printk/dump_stack. Even if someone has funny ideas they cannot be brought to life, since drivers need a lot more than this set of functions and BPF checker will reject any attempts to call something outside of this tiny list. imo the same applies to existing BPF as well. Meaning that tcpdump filter string and seccomp filters, if distributed, has to have their source code available.

Quoted 3 lines

I.e. we want to allow flexible plugins technologically, but make sure people who run into such a plugin can modify and improve it under the same license as they can modify and improve the kernel itself!

wow. I guess if the whole thing takes off, we would need an in-kernel directory to store upstreamed bpf filters as well :)

Quoted 11 lines
Quoted 8 lines

opcode encoding is the same between old BPF and extended BPF. Original BPF has two 32-bit registers.
Extended BPF has ten 64-bit registers.
That is the main difference.

Old BPF was using jt/jf fields for jump-insn only.
New BPF combines them into generic 'off' field for jump and non-jump insns. k==imm field has the same meaning.

This only affects the internal JIT representation, not the BPF byte code, right?

that is the ebpf vs bpf code difference. JIT doesn't keep another representation.
Just converts it to x86

Quoted 6 lines
Quoted 1 line
 32 files changed, 3332 insertions(+), 24 deletions(-)

Impressive!

I'm wondering, will the new nftable code in works make use of the BPF JIT as well, or is that a separate implementation?

nft is much higher level state machine customized for specific nftable use case. imo iptables/nftable rules can be compiled into extended bpf.
One needs to define bpf_context and set of functions to do packet lookup via bpf_callbacks...
but let's do it one step at a a time.

Thanks
Alexei

#29 lore raw
Quoted 24 lines · Alexei Starovoitov
Quoted 14 lines · Ingo Molnar

Very cool! (Added various other folks who might be interested in this to the Cc: list.)

I have one generic concern:

It would be important to make it easy to extract loaded BPF code from the kernel in source code equivalent form, which compiles to the same BPF code.

I.e. I think it would be fundamentally important to make sure that this is all within the kernel's license domain, to make it very clear there can be no 'binary only' BPF scripts.

Quoted 8 lines

By up-loading BPF into a kernel the person loading it agrees to make that code available to all users of that system who can access it, under the same license as the kernel's code (or under a more permissive license).

The last thing we want is people getting funny ideas and writing drivers in BPF and hiding the code or making license claims over it

Quoted 12 lines

all makes sense. In case of kernel modules all export_symbols are accessible and module has to have kernel compatible license. Same licensing terms apply to anything else that interacts with kernel functions. In case of BPF the list of accessible functions is tiny, so it's much easier to enforce specific limited use case. For tracing filters it's just bpf_load_xx/trace_printk/dump_stack. Even if someone has funny ideas they cannot be brought to life, since drivers need a lot more than this set of functions and BPF checker will reject any attempts to call something outside of this tiny list. imo the same applies to existing BPF as well. Meaning that tcpdump filter string and seccomp filters, if distributed, has to have their source code available.

I mean more than that, I mean the licensing of BFP filters a user can find on his own system's kernel should be very clear: by the act of loading a BFP script into the kernel the user doing the 'upload' gives permission for it to be redistributed on kernel-compatible license terms.

The easiest way to achieve that is to make sure that all loaded BFP scripts are 'registered' and are dumpable, viewable and reusable. That's good for debugging and it's good for transparency.

This means a minimal BFP decoder will have to be in the kernel as well, but that's OK, we actually have several x86 instruction decoder in the kernel already, so there's no complexity threshold.

Quoted 7 lines
Quoted 4 lines

I.e. we want to allow flexible plugins technologically, but make sure people who run into such a plugin can modify and improve it under the same license as they can modify and improve the kernel itself!

wow. I guess if the whole thing takes off, we would need an in-kernel directory to store upstreamed bpf filters as well :)

I see no reason why not, but more importantly all currently loaded BFP scripts should be dumpable, displayable and reusable in a kernel license compatible fashion.

Thanks,

Ingo

#30 lore raw
Quoted 46 lines · Ingo Molnar
Quoted 24 lines · Alexei Starovoitov
Quoted 14 lines · Ingo Molnar

Very cool! (Added various other folks who might be interested in this to the Cc: list.)

I have one generic concern:

It would be important to make it easy to extract loaded BPF code from the kernel in source code equivalent form, which compiles to the same BPF code.

I.e. I think it would be fundamentally important to make sure that this is all within the kernel's license domain, to make it very clear there can be no 'binary only' BPF scripts.

Quoted 8 lines

By up-loading BPF into a kernel the person loading it agrees to make that code available to all users of that system who can access it, under the same license as the kernel's code (or under a more permissive license).

The last thing we want is people getting funny ideas and writing drivers in BPF and hiding the code or making license claims over it

Quoted 12 lines

all makes sense. In case of kernel modules all export_symbols are accessible and module has to have kernel compatible license. Same licensing terms apply to anything else that interacts with kernel functions. In case of BPF the list of accessible functions is tiny, so it's much easier to enforce specific limited use case. For tracing filters it's just bpf_load_xx/trace_printk/dump_stack. Even if someone has funny ideas they cannot be brought to life, since drivers need a lot more than this set of functions and BPF checker will reject any attempts to call something outside of this tiny list. imo the same applies to existing BPF as well. Meaning that tcpdump filter string and seccomp filters, if distributed, has to have their source code available.

I mean more than that, I mean the licensing of BFP filters a user can find on his own system's kernel should be very clear: by the act of loading a BFP script into the kernel the user doing the 'upload' gives permission for it to be redistributed on kernel-compatible license terms.

Quoted 7 lines

The easiest way to achieve that is to make sure that all loaded BFP scripts are 'registered' and are dumpable, viewable and reusable. That's good for debugging and it's good for transparency.

This means a minimal BFP decoder will have to be in the kernel as well, but that's OK, we actually have several x86 instruction decoder in the kernel already, so there's no complexity threshold.

sure. there is pr_info_bpf_insn() in bpf_run.c that dumps bpf insn in human readable format.
I'll hook it up to trace_seq, so that "cat /sys/kernel/debug/.../filter" will dump it.

Also I'm thinking to add 'license_string' section to bpf binary format and call license_is_gpl_compatible() on it during load.
If false, then just reject it…. not even messing with taint flags... That would be way stronger indication of bpf licensing terms than what we have for .ko

Quoted 6 lines
Quoted 2 lines

wow. I guess if the whole thing takes off, we would need an in-kernel directory to store upstreamed bpf filters as well :)

I see no reason why not, but more importantly all currently loaded BFP scripts should be dumpable, displayable and reusable in a kernel license compatible fashion.

ok. will add global bpf list as well (was hesitating to do something like this because of central lock)
and something in debugfs that dumps bodies of all currently loaded filters.

Will that solve the concern?

Thanks
Alexei

#31 lore raw
Quoted 20 lines · Alexei Starovoitov
Quoted 6 lines

I mean more than that, I mean the licensing of BFP filters a user can find on his own system's kernel should be very clear: by the act of loading a BFP script into the kernel the user doing the 'upload' gives permission for it to be redistributed on kernel-compatible license terms.

Quoted 8 lines

The easiest way to achieve that is to make sure that all loaded BFP scripts are 'registered' and are dumpable, viewable and reusable. That's good for debugging and it's good for transparency.

This means a minimal BFP decoder will have to be in the kernel as well, but that's OK, we actually have several x86 instruction decoder in the kernel already, so there's no complexity threshold.

sure. there is pr_info_bpf_insn() in bpf_run.c that dumps bpf insn in human readable format.
I'll hook it up to trace_seq, so that "cat /sys/kernel/debug/.../filter" will dump it.

Quoted 5 lines

Also I'm thinking to add 'license_string' section to bpf binary format and call license_is_gpl_compatible() on it during load.
If false, then just reject it…. not even messing with taint flags... That would be way stronger indication of bpf licensing terms than what we have for .ko

But will BFP tools generate such gpl-compatible license tags by default? If yes then this might work, combined with the facility below. If not then it's just a nuisance to users.

Also, 'tainting' is a non-issue here, as we don't want the kernel to load license-incompatible scripts at all. This should be made clear in the design of the facility and the tooling itself.

Quoted 9 lines
Quoted 6 lines
Quoted 2 lines

wow. I guess if the whole thing takes off, we would need an in-kernel directory to store upstreamed bpf filters as well :)

I see no reason why not, but more importantly all currently loaded BFP scripts should be dumpable, displayable and reusable in a kernel license compatible fashion.

ok. will add global bpf list as well (was hesitating to do something like this because of central lock)

A lock + list is no big issue here I think, we do such central lookup locks all the time. If it ever becomes measurable it can be made scalable via numerous techniques.

Quoted 4 lines

and something in debugfs that dumps bodies of all currently loaded filters.

Will that solve the concern?

My concern would be solved by adding a facility to always be able to dump source code as well, i.e. trivially transform it to C or so, so that people can review it - or just edit it on the fly, recompile and reinsert? Most BFP scripts ought to be pretty simple.

(For example the most common way to load OpenGL shaders is to load the GLSL source code and that source code can be queried after insertion as well, so this is not an unusual model for small plugin-alike scriptlets.)

Thanks,

Ingo

#32 lore raw
Quoted 10 lines · Ingo Molnar
Quoted 6 lines

Also I'm thinking to add 'license_string' section to bpf binary format and call license_is_gpl_compatible() on it during load.
If false, then just reject it…. not even messing with taint flags... That would be way stronger indication of bpf licensing terms than what we have for .ko

But will BFP tools generate such gpl-compatible license tags by default? If yes then this might work, combined with the facility below. If not then it's just a nuisance to users.

yes. similar to existing .ko module_license() tag. see below.

Quoted 4 lines

My concern would be solved by adding a facility to always be able to dump source code as well, i.e. trivially transform it to C or so, so that people can review it - or just edit it on the fly, recompile and reinsert? Most BFP scripts ought to be pretty simple.

C code has '#include' in them, so without storing fully preprocessed code it will not be equivalent. but then true source will be gigantic. Can be zipped, but that sounds like an overkill.
Also we might want other languages with their own dependent includes. Sure, we can have a section in bpf binary that has the source, but it's not enforceable. Kernel cannot know that it's an actual source. gcc/llvm will produce different bpf code out of the same source. the source is in C or in language X, etc.
Doesn't seem that including some form of source will help
with enforcing the license.

imo requiring module_license("gpl"); line in C code and equivalent string in all other languages that want to translate to bpf would be stronger indication of licensing terms.
then compiler would have to include that string into 'license_string' section and kernel can actually enforce it.

#33 lore raw
In reply to Alexei Starovoitov
Quoted 10 lines · Alexei Starovoitov

Hi All,

the following set of patches adds BPF support to trace filters.

Trace filters can be written in C and allow safe read-only access to any kernel data structure. Like systemtap but with safety guaranteed by kernel.

The user can do:
cat bpf_program > /sys/kernel/debug/tracing/.../filter if tracing event is either static or dynamic via kprobe_events.

Oh, thank you for this great work! :D

Quoted 49 lines

The filter program may look like:
void filter(struct bpf_context *ctx)

{
        char devname[4] = "eth5";
        struct net_device *dev;
        struct sk_buff *skb = 0;

        dev = (struct net_device *)ctx->regs.si;
        if (bpf_memcmp(dev->name, devname, 4) == 0) {
                char fmt[] = "skb %p dev %p eth5\n";
                bpf_trace_printk(fmt, skb, dev, 0, 0);
        }
}

The kernel will do static analysis of bpf program to make sure that it cannot crash the kernel (doesn't have loops, valid memory/register accesses, etc). Then kernel will map bpf instructions to x86 instructions and let it run in the place of trace filter.

To demonstrate performance I did a synthetic test:

        dev = init_net.loopback_dev;
        do_gettimeofday(&start_tv);
        for (i = 0; i < 1000000; i++) {
                struct sk_buff *skb;
                skb = netdev_alloc_skb(dev, 128);
                kfree_skb(skb);
        }
        do_gettimeofday(&end_tv);
        time = end_tv.tv_sec - start_tv.tv_sec;
        time *= USEC_PER_SEC;
        time += (long long)((long)end_tv.tv_usec - (long)start_tv.tv_usec);

        printk("1M skb alloc/free %lld (usecs)\n", time);

no tracing

[   33.450966] 1M skb alloc/free 145179 (usecs)

echo 1 > enable

[   97.186379] 1M skb alloc/free 240419 (usecs)

(tracing slows down kfree_skb() due to event_buffer_lock/buffer_unlock_commit)

echo 'name==eth5' > filter

[  139.644161] 1M skb alloc/free 302552 (usecs)

(running filter_match_preds() for every skb and discarding event_buffer is even slower)

cat bpf_prog > filter

[  171.150566] 1M skb alloc/free 199463 (usecs)
Quoted 8 lines

(JITed bpf program is safely checking dev->name == eth5 and discarding)

echo 0 > enable

[  258.073593] 1M skb alloc/free 144919 (usecs)

(tracing is disabled, performance is back to original)

The C program compiled into BPF and then JITed into x86 is faster than filter_match_preds() approach (199-145 msec vs 302-145 msec)

Great! :)

Quoted 2 lines

tracing+bpf is a tool for safe read-only access to variables without recompiling the kernel and without affecting running programs.

Hmm, this feature and trace-event trigger actions can give us powerful on-the-fly scripting functionality...

Quoted 22 lines

BPF filters can be written manually (see tools/bpf/trace/filter_ex1.c) or better compiled from restricted C via GCC or LLVM

Q: What is the difference between existing BPF and extended BPF? A:
Existing BPF insn from uapi/linux/filter.h
struct sock_filter {

        __u16   code;   /* Actual filter code */
        __u8    jt;     /* Jump true */
        __u8    jf;     /* Jump false */
        __u32   k;      /* Generic multiuse field */

};

Extended BPF insn from linux/bpf.h

struct bpf_insn {
        __u8    code;    /* opcode */
        __u8    a_reg:4; /* dest register*/
        __u8    x_reg:4; /* source register */
        __s16   off;     /* signed offset */
        __s32   imm;     /* signed immediate constant */
};
Quoted 8 lines

opcode encoding is the same between old BPF and extended BPF. Original BPF has two 32-bit registers.
Extended BPF has ten 64-bit registers.
That is the main difference.

Old BPF was using jt/jf fields for jump-insn only.
New BPF combines them into generic 'off' field for jump and non-jump insns. k==imm field has the same meaning.

Looks very interesting. :)

Thank you!

Signature · 4 lines
Masami HIRAMATSU
IT Management Research Dept. Linux Technology Center
Hitachi, Ltd., Yokohama Research Laboratory
E-mail: [email protected]
#34 lore raw
In reply to Alexei Starovoitov

Alexei Starovoitov <[email protected]> writes:

Can you do some performance comparison compared to e.g. ktap? How much faster is it?

While it sounds interesting, I would strongly advise to make this capability only available to root. Traditionally lots of complex byte code languages which were designed to be "safe" and verifiable weren't really. e.g. i managed to crash things with "safe" systemtap multiple times. And we all know what happened to Java.

So the likelyhood of this having some hole somewhere (either in the byte code or in some library function) is high.

-Andi

#35 lore raw
Quoted 4 lines · Andi Kleen

Alexei Starovoitov <[email protected]> writes:

Can you do some performance comparison compared to e.g. ktap? How much faster is it?

imo the most interesting ktap scripts (like kmalloc-top.kp) need tables and timers.
tables are almost ready for prime time, but timers I prefer to keep out of kernel.
I would like bpf filter to fill tables with interesting data in kernel up to predefined limit
and periodically read and clear the tables from userspace. This way I will be able to do nettop.stp, iotop.stp like programs. So I'm still thinking what should be clean kernel/user interface for bpf-defined tables.
Format of keys and elements of the table is defined within bpf program. During load of bpf program, the tables are allocated and bpf program can now lookup/update into them. At the same time corresponding userspace program can read tables of this particular bpf program over netlink.
Creating its own debugfs files for every filter feels too slow and feature limited, since files are all or nothing interface. Netlink access to bpf tables feels cleaner. Userspace will use libmnl to access them. Other ideas?

In the mean time I'll do some simple
trace probe:xx { print }
performance test…

Quoted 8 lines

While it sounds interesting, I would strongly advise to make this capability only available to root. Traditionally lots of complex byte code languages which were designed to be "safe" and verifiable weren't really. e.g. i managed to crash things with "safe" systemtap multiple times. And we all know what happened to Java.

So the likelyhood of this having some hole somewhere (either in the byte code or in some library function) is high.

Tracing filters are for root only today and should stay this way. As far as safety of bpf… hard to argue systemtap point ;) Though existing bpf is generally accepted to be safe. extended bpf needs time to prove itself.

#36 lore raw
Quoted 4 lines · Andi Kleen
Quoted 3 lines

Can you do some performance comparison compared to e.g. ktap? How much faster is it?

Did simple ktap test with 1M alloc_skb/kfree_skb toy test from earlier email:

trace skb:kfree_skb {
        if (arg2 == 0x100) {
                printf("%x %x\n", arg1, arg2)
        }
}

1M skb alloc/free 350315 (usecs)

baseline without any tracing:
1M skb alloc/free 145400 (usecs)

then equivalent bpf test:
void filter(struct bpf_context *ctx)

{
        void *loc = (void *)ctx->regs.dx;
        if (loc == 0x100) {
                struct sk_buff *skb = (struct sk_buff *)ctx->regs.si;
                char fmt[] = "skb %p loc %p\n";
                bpf_trace_printk(fmt, sizeof(fmt), (long)skb, (long)loc, 0);
        }
}

1M skb alloc/free 183214 (usecs)

so with one 'if' condition the difference ktap vs bpf is 350-145 vs 183-145

obviously ktap is an interpreter, so it's not really fair.

To make it really unfair I did:

trace skb:kfree_skb {
        if (arg2 == 0x100 || arg2 == 0x200 || arg2 == 0x300 || arg2 == 0x400 ||
            arg2 == 0x500 || arg2 == 0x600 || arg2 == 0x700 || arg2 == 0x800 ||
            arg2 == 0x900 || arg2 == 0x1000) {
                printf("%x %x\n", arg1, arg2)
        }
}

1M skb alloc/free 484280 (usecs)

and corresponding bpf:
void filter(struct bpf_context *ctx)

{
        void *loc = (void *)ctx->regs.dx;
        if (loc == 0x100 || loc == 0x200 || loc == 0x300 || loc == 0x400 ||
            loc == 0x500 || loc == 0x600 || loc == 0x700 || loc == 0x800 ||
            loc == 0x900 || loc == 0x1000) {
                struct sk_buff *skb = (struct sk_buff *)ctx->regs.si;
                char fmt[] = "skb %p loc %p\n";
                bpf_trace_printk(fmt, sizeof(fmt), (long)skb, (long)loc, 0);
        }
}

1M skb alloc/free 185660 (usecs)

the difference is bigger now: 484-145 vs 185-145

9 extra 'if' conditions for bpf is almost nothing, since they translate into 18 new x86 instructions after JITing, but for interpreter it's obviously costly.

Why 0x100 instead of 0x1? To make sure that compiler doesn't optimize them into < >
Otherwise it's really really unfair.

ktap is a nice tool. Great job Jovi!
I noticed that it doesn't always clear created kprobes after run and I see a bunch of .../tracing/events/ktap_kprobes_xxx, but that's a minor thing.

Thanks
Alexei

#37 lore raw
Quoted 33 lines · Alexei Starovoitov
Quoted 4 lines · Andi Kleen
Quoted 3 lines

Can you do some performance comparison compared to e.g. ktap? How much faster is it?

Did simple ktap test with 1M alloc_skb/kfree_skb toy test from earlier email:

trace skb:kfree_skb {
        if (arg2 == 0x100) {
                printf("%x %x\n", arg1, arg2)
        }
}

1M skb alloc/free 350315 (usecs)

baseline without any tracing:
1M skb alloc/free 145400 (usecs)

then equivalent bpf test:
void filter(struct bpf_context *ctx)

{
        void *loc = (void *)ctx->regs.dx;
        if (loc == 0x100) {
                struct sk_buff *skb = (struct sk_buff *)ctx->regs.si;
                char fmt[] = "skb %p loc %p\n";
                bpf_trace_printk(fmt, sizeof(fmt), (long)skb, (long)loc, 0);
        }
}

1M skb alloc/free 183214 (usecs)

so with one 'if' condition the difference ktap vs bpf is 350-145 vs 183-145

obviously ktap is an interpreter, so it's not really fair.

To make it really unfair I did:

Quoted 8 lines
trace skb:kfree_skb {
        if (arg2 == 0x100 || arg2 == 0x200 || arg2 == 0x300 || arg2 == 0x400 ||
            arg2 == 0x500 || arg2 == 0x600 || arg2 == 0x700 || arg2 == 0x800 ||
            arg2 == 0x900 || arg2 == 0x1000) {
                printf("%x %x\n", arg1, arg2)
        }
}

1M skb alloc/free 484280 (usecs)

Real life scripts, for examples the ones related to network protocol analysis will often have such patterns in them, so I don't think this measurement is particularly unfair.

Thanks,

Ingo

maintainer
#38 lore raw
Quoted 14 lines · On Thu, 5 Dec 2013 11:41:13 +0100 Ingo Molnar <[email protected]> wrote:
Quoted 5 lines

so with one 'if' condition the difference ktap vs bpf is 350-145 vs 183-145

obviously ktap is an interpreter, so it's not really fair.

To make it really unfair I did:

Quoted 8 lines
trace skb:kfree_skb {
        if (arg2 == 0x100 || arg2 == 0x200 || arg2 == 0x300 || arg2 == 0x400 ||
            arg2 == 0x500 || arg2 == 0x600 || arg2 == 0x700 || arg2 == 0x800 ||
            arg2 == 0x900 || arg2 == 0x1000) {
                printf("%x %x\n", arg1, arg2)
        }
}

1M skb alloc/free 484280 (usecs)

Quoted 3 lines

Real life scripts, for examples the ones related to network protocol analysis will often have such patterns in them, so I don't think this measurement is particularly unfair.

I agree. As the size of the if statement grows, the filter logic gets lineally expensive, but the bpf filter does not.

I know that it would be great to have the bpf filter run before recording of the tracepoint, but as that becomes quite awkward for a user interface, because it requires intimate knowledge of the kernel source, this speed up on the filter itself may be worth while to have it happen after the recording of the buffer. When it happens after the record, then the bpf has direct access to the event entry and its fields as described by the trace event format files.

-- Steve

#39 lore raw
Quoted 8 lines · Steven Rostedt

I know that it would be great to have the bpf filter run before recording of the tracepoint, but as that becomes quite awkward for a user interface, because it requires intimate knowledge of the kernel source, this speed up on the filter itself may be worth while to have it happen after the recording of the buffer. When it happens after the record, then the bpf has direct access to the event entry and its fields as described by the trace event format files.

I don't understand that 'awkward' part yet. What do you mean by 'knowledge of the kernel'? By accessing pt_regs structure? Something else ?
Can we try fixing the interface first before compromising on performance?

maintainer
#40 lore raw
Quoted 10 lines · On Thu, 5 Dec 2013 14:36:58 -0800 Alexei Starovoitov <[email protected]> wrote:
Quoted 8 lines · Steven Rostedt

I know that it would be great to have the bpf filter run before recording of the tracepoint, but as that becomes quite awkward for a user interface, because it requires intimate knowledge of the kernel source, this speed up on the filter itself may be worth while to have it happen after the recording of the buffer. When it happens after the record, then the bpf has direct access to the event entry and its fields as described by the trace event format files.

Quoted 3 lines

I don't understand that 'awkward' part yet. What do you mean by 'knowledge of the kernel'? By accessing pt_regs structure? Something else ?
Can we try fixing the interface first before compromising on performance?

Let me ask you this. If you do not have the source of the kernel on hand, can you use BPF to filter the sched_switch tracepoint on prev pid?

The current filter interface allows you to filter with just what the running kernel provides. No need for debug info from the vmlinux or anything else.

pt_regs is not that useful without having something to translate what that means.

I'm fine if it becomes a requirement to have a vmlinux built with DEBUG_INFO to use BPF and have a tool like perf to translate the filters. But it that must not replace what the current filters do now. That is, it can be an add on, but not a replacement.

-- Steve

#41 lore raw
Quoted 17 lines · Steven Rostedt
Quoted 10 lines · On Thu, 5 Dec 2013 14:36:58 -0800 Alexei Starovoitov <[email protected]> wrote:
Quoted 8 lines · Steven Rostedt

I know that it would be great to have the bpf filter run before recording of the tracepoint, but as that becomes quite awkward for a user interface, because it requires intimate knowledge of the kernel source, this speed up on the filter itself may be worth while to have it happen after the recording of the buffer. When it happens after the record, then the bpf has direct access to the event entry and its fields as described by the trace event format files.

Quoted 3 lines

I don't understand that 'awkward' part yet. What do you mean by 'knowledge of the kernel'? By accessing pt_regs structure? Something else ?
Can we try fixing the interface first before compromising on performance?

Quoted 6 lines

Let me ask you this. If you do not have the source of the kernel on hand, can you use BPF to filter the sched_switch tracepoint on prev pid?

The current filter interface allows you to filter with just what the running kernel provides. No need for debug info from the vmlinux or anything else.

Understood and agreed. For the users that are satisfied with amount of info that single trace_event provides (like sched_switch) there is probably little reason to do complex filtering. Either they're fine with all the events or will
just filter based on pid only.

Quoted 4 lines

I'm fine if it becomes a requirement to have a vmlinux built with DEBUG_INFO to use BPF and have a tool like perf to translate the filters. But it that must not replace what the current filters do now. That is, it can be an add on, but not a replacement.

Of course. tracing filters via bpf is an additional tool for kernel debugging. bpf by itself has use cases beyond tracing.

#42 lore raw
Quoted 7 lines · Alexei Starovoitov
Quoted 4 lines

I'm fine if it becomes a requirement to have a vmlinux built with DEBUG_INFO to use BPF and have a tool like perf to translate the filters. But it that must not replace what the current filters do now. That is, it can be an add on, but not a replacement.

Of course. tracing filters via bpf is an additional tool for kernel debugging. bpf by itself has use cases beyond tracing.

Well, Steve has a point: forcing DEBUG_INFO is a big showstopper for most people.

Would it be possible to make BFP filters recognize exposed details like the current filters do, without depending on the vmlinux?

Thanks,

Ingo

#43 lore raw
Quoted 8 lines · Ingo Molnar
Quoted 5 lines · Alexei Starovoitov
Quoted 4 lines

I'm fine if it becomes a requirement to have a vmlinux built with DEBUG_INFO to use BPF and have a tool like perf to translate the filters. But it that must not replace what the current filters do now. That is, it can be an add on, but not a replacement.

Quoted 5 lines
Quoted 2 lines

Of course. tracing filters via bpf is an additional tool for kernel debugging. bpf by itself has use cases beyond tracing.

Well, Steve has a point: forcing DEBUG_INFO is a big showstopper for most people.

there is a misunderstanding here.
I was saying 'of course' to 'not replace current filter infra'.

bpf does not depend on debug info.
That's the key difference between 'perf probe' approach and bpf filters.

Masami is right that what I was trying to achieve with bpf filters is similar to 'perf probe': insert a dynamic probe anywhere in the kernel, walk pointers, data structures, print interesting stuff.

'perf probe' does it via scanning vmlinux with debug info. bpf filters don't need it.
tools/bpf/trace/*_orig.c examples only depend on linux headers in /lib/modules/../build/include/
Today bpf compiler struct layout is the same as x86_64.

Tomorrow bpf compiler will have flags to adjust endianness, pointer size, etc of the front-end. Similar to -m32/-m64 and -m*-endian flags.
Neat part is that I don't need to do any work, just enable it properly in the bpf backend. From gcc/llvm point of view, bpf is yet another 'hw' architecture that compiler is emitting code for.
So when C code of filter_ex1_orig.c does 'skb->dev', compiler determines field offset by looking at /lib/modules/.../include/skbuff.h whereas for 'perf probe' 'skb->dev' means walk debug info.

Something like: cc1 -mlayout_x86_64 filter.c will produce bpf code that walks all data structures in the same way x86_64 does it.
Even if the user makes a mistake and uses -mlayout_aarch64, it won't crash. Note that all -m* flags will be in one compiler. It won't grow any bigger because of that. All of it already supported by C front-ends. It may sound complex, but really very little code for the bpf backend.

I didn't look inside systemtap/ktap enough to say how much they're relying on presence of debug info to make a comparison.

I see two main use cases for bpf tracing filters: debugging live kernel and collecting stats. Same tricks that [sk]tap do with their maps. Or may be some of the stats that 'perf record' collects in userspace can be collected by bpf filter in kernel and stored into generic bpf table?

Quoted 2 lines

Would it be possible to make BFP filters recognize exposed details like the current filters do, without depending on the vmlinux?

Well, if you say that presence of linux headers is also too much to ask, I can hook bpf after probes stored all the args.

This way current simple filter syntax can move to userspace. 'arg1==x || arg2!=y' can be parsed by userspace, bpf code generated and fed into kernel. It will be faster than walk_pred_tree(), but if we cannot remove 2k lines from trace_events_filter.c because of backward compatibility, extra performance becomes the only reason to have two different implementations.

Another use case is to optimize fetch sequences of dynamic probes as Masami suggested, but backward compatibility requirement would preserve to ways of doing it as well.

imo the current hook of bpf into tracing is more compelling, but let me think more about reusing data stored in the ring buffer.

Thanks
Alexei

#44 lore raw
Quoted 31 lines · Alexei Starovoitov
Quoted 8 lines · Ingo Molnar
Quoted 5 lines · Alexei Starovoitov
Quoted 4 lines

I'm fine if it becomes a requirement to have a vmlinux built with DEBUG_INFO to use BPF and have a tool like perf to translate the filters. But it that must not replace what the current filters do now. That is, it can be an add on, but not a replacement.

Quoted 5 lines
Quoted 2 lines

Of course. tracing filters via bpf is an additional tool for kernel debugging. bpf by itself has use cases beyond tracing.

Well, Steve has a point: forcing DEBUG_INFO is a big showstopper for most people.

there is a misunderstanding here.
I was saying 'of course' to 'not replace current filter infra'.

bpf does not depend on debug info.
That's the key difference between 'perf probe' approach and bpf filters.

Masami is right that what I was trying to achieve with bpf filters is similar to 'perf probe': insert a dynamic probe anywhere in the kernel, walk pointers, data structures, print interesting stuff.

'perf probe' does it via scanning vmlinux with debug info. bpf filters don't need it.
tools/bpf/trace/*_orig.c examples only depend on linux headers in /lib/modules/../build/include/
Today bpf compiler struct layout is the same as x86_64.

Quoted 8 lines

Tomorrow bpf compiler will have flags to adjust endianness, pointer size, etc of the front-end. Similar to -m32/-m64 and -m*-endian flags.
Neat part is that I don't need to do any work, just enable it properly in the bpf backend. From gcc/llvm point of view, bpf is yet another 'hw' architecture that compiler is emitting code for.
So when C code of filter_ex1_orig.c does 'skb->dev', compiler determines field offset by looking at /lib/modules/.../include/skbuff.h whereas for 'perf probe' 'skb->dev' means walk debug info.

Right, the offset of the data structure can get from the header etc.

However, how would the bpf get the register or stack assignment of skb itself? In the tracepoint macro, it will be able to get it from function parameters (it needs a trick, like jprobe does). I doubt you can do that on kprobes/uprobes without any debuginfo support. :(

And is it possible to trace a field in a data structure which is defined locally in somewhere.c ? :) (maybe it's just a corner case)

Quoted 28 lines

Something like: cc1 -mlayout_x86_64 filter.c will produce bpf code that walks all data structures in the same way x86_64 does it.
Even if the user makes a mistake and uses -mlayout_aarch64, it won't crash. Note that all -m* flags will be in one compiler. It won't grow any bigger because of that. All of it already supported by C front-ends. It may sound complex, but really very little code for the bpf backend.

I didn't look inside systemtap/ktap enough to say how much they're relying on presence of debug info to make a comparison.

I see two main use cases for bpf tracing filters: debugging live kernel and collecting stats. Same tricks that [sk]tap do with their maps. Or may be some of the stats that 'perf record' collects in userspace can be collected by bpf filter in kernel and stored into generic bpf table?

Quoted 2 lines

Would it be possible to make BFP filters recognize exposed details like the current filters do, without depending on the vmlinux?

Well, if you say that presence of linux headers is also too much to ask, I can hook bpf after probes stored all the args.

This way current simple filter syntax can move to userspace. 'arg1==x || arg2!=y' can be parsed by userspace, bpf code generated and fed into kernel. It will be faster than walk_pred_tree(), but if we cannot remove 2k lines from trace_events_filter.c because of backward compatibility, extra performance becomes the only reason to have two different implementations.

Quoted 3 lines

Another use case is to optimize fetch sequences of dynamic probes as Masami suggested, but backward compatibility requirement would preserve to ways of doing it as well.

The backward compatibility issue is only for the interface, but not for the implementation, I think. :) The fetch method and filter pred do already parse the argument into a syntax tree. IMHO, bpf can optimize that tree to just a simple opcode stream.

Thank you,

Signature · 4 lines
Masami HIRAMATSU
IT Management Research Dept. Linux Technology Center
Hitachi, Ltd., Yokohama Research Laboratory
E-mail: [email protected]
#45 lore raw
Quoted 41 lines · Masami Hiramatsu
Quoted 31 lines · Alexei Starovoitov
Quoted 8 lines · Ingo Molnar
Quoted 5 lines · Alexei Starovoitov
Quoted 4 lines

I'm fine if it becomes a requirement to have a vmlinux built with DEBUG_INFO to use BPF and have a tool like perf to translate the filters. But it that must not replace what the current filters do now. That is, it can be an add on, but not a replacement.

Quoted 5 lines
Quoted 2 lines

Of course. tracing filters via bpf is an additional tool for kernel debugging. bpf by itself has use cases beyond tracing.

Well, Steve has a point: forcing DEBUG_INFO is a big showstopper for most people.

there is a misunderstanding here.
I was saying 'of course' to 'not replace current filter infra'.

bpf does not depend on debug info.
That's the key difference between 'perf probe' approach and bpf filters.

Masami is right that what I was trying to achieve with bpf filters is similar to 'perf probe': insert a dynamic probe anywhere in the kernel, walk pointers, data structures, print interesting stuff.

'perf probe' does it via scanning vmlinux with debug info. bpf filters don't need it.
tools/bpf/trace/*_orig.c examples only depend on linux headers in /lib/modules/../build/include/
Today bpf compiler struct layout is the same as x86_64.

Quoted 8 lines

Tomorrow bpf compiler will have flags to adjust endianness, pointer size, etc of the front-end. Similar to -m32/-m64 and -m*-endian flags.
Neat part is that I don't need to do any work, just enable it properly in the bpf backend. From gcc/llvm point of view, bpf is yet another 'hw' architecture that compiler is emitting code for.
So when C code of filter_ex1_orig.c does 'skb->dev', compiler determines field offset by looking at /lib/modules/.../include/skbuff.h whereas for 'perf probe' 'skb->dev' means walk debug info.

Quoted 7 lines

Right, the offset of the data structure can get from the header etc.

However, how would the bpf get the register or stack assignment of skb itself? In the tracepoint macro, it will be able to get it from function parameters (it needs a trick, like jprobe does). I doubt you can do that on kprobes/uprobes without any debuginfo support. :(

the 4/5 diff actually shows how it's working ;)
for kprobes it works at the function entry, since arguments are still in the registers
and walks the pointers further down.
It cannot do func+line_number as perf-probe does, of course.
for tracepoints it's the same trick: call no-inline func with traceprobe args and call inlined crash_setup_regs() that stores the regs.

Of course, there are limitations. Like 7th func argument goes into stack and requires
more work to get out. If struct is not defined in .h, it would need to be redefined in filter.c
Corner cases as you said.
Today user of bpf filter needs to know that arg1 goes into %rdi and so on. that is easy to cleanup.

Quoted 8 lines
Quoted 3 lines

Another use case is to optimize fetch sequences of dynamic probes as Masami suggested, but backward compatibility requirement would preserve to ways of doing it as well.

The backward compatibility issue is only for the interface, but not for the implementation, I think. :) The fetch method and filter pred do already parse the argument into a syntax tree. IMHO, bpf can optimize that tree to just a simple opcode stream.

ahh. yes. that's doable.

Thanks
Alexei

#46 lore raw
In reply to Alexei Starovoitov
Quoted 8 lines · ast
Quoted 1 line

[...]

Did simple ktap test with 1M alloc_skb/kfree_skb toy test from earlier email:

trace skb:kfree_skb {
        if (arg2 == 0x100) {
                printf("%x %x\n", arg1, arg2)
        }
}

[...]

For reference, you might try putting systemtap into the performance comparison matrix too:

# stap -e 'probe kernel.trace("kfree_skb") { 
              if ($location == 0x100 /* || $location == 0x200 etc. */ ) {
                 printf("%x %x\n", $skb, $location)
              }
           }'

- FChE

#47 lore raw
Quoted 12 lines · Frank Ch. Eigler
Quoted 8 lines · ast
Quoted 1 line

[...]

Did simple ktap test with 1M alloc_skb/kfree_skb toy test from earlier email:

trace skb:kfree_skb {
        if (arg2 == 0x100) {
                printf("%x %x\n", arg1, arg2)
        }
}

[...]

Quoted 8 lines

For reference, you might try putting systemtap into the performance comparison matrix too:

# stap -e 'probe kernel.trace("kfree_skb") {
              if ($location == 0x100 /* || $location == 0x200 etc. */ ) {
                 printf("%x %x\n", $skb, $location)
              }
           }'

stap with one 'if': 1M skb alloc/free 200696 (usecs) stap with 10 'if': 1M skb alloc/free 202135 (usecs)

so systemtap entry overhead is a bit higher than bpf and extra if-s show the same progression as expected.

#48 lore raw
In reply to Alexei Starovoitov
Quoted 3 lines

1M skb alloc/free 185660 (usecs)

the difference is bigger now: 484-145 vs 185-145

Thanks for the data.

This is a obvious improvement, but imho not big enough to be extremely compelling (< cost 1-2 cache misses, no orders of magnitude improvements that would justify a lot of code)

One larger problem I have with your patchkit is where exactly it fits with the user base.

In my experience there are roughly two groups of trace users:
kernel hackers and users. The kernel hackers want something convenient and fast, but for anything complicated or performance critical they can always hack the kernel to include custom instrumentation.

Your code requires a compiler, so from my perspective it wouldn't be a lot easier or faster to use than just changing the code directly and recompile.

The users want something simple too that shields them from having to learn all the internals. They don't want to recompile. As far as I can tell your code is a bit too low level for that, and the requirement for the compiler may also scare them.

Where exactly does it fit?

-Andi

#49 lore raw
Quoted 7 lines · Andi Kleen

In my experience there are roughly two groups of trace users:
kernel hackers and users. The kernel hackers want something convenient and fast, but for anything complicated or performance critical they can always hack the kernel to include custom instrumentation.

Not to mention that in that case we might as well -- since we need a compiler anyway -- generate the machine code in user space; the JIT solution really only is useful if it can provide something that we can't do otherwise, e.g. enable it in secure boot environments.

-hpa

#50 lore raw
Quoted 5 lines · H. Peter Anvin

Not to mention that in that case we might as well -- since we need a compiler anyway -- generate the machine code in user space; the JIT solution really only is useful if it can provide something that we can't do otherwise, e.g. enable it in secure boot environments.

I can see there may be some setups which don't have a compiler (e.g. I know some people don't use systemtap because of that) But this needs a custom gcc install too as far as I understand.

-Andi

Signature · 1 line
[email protected] -- Speaking for myself only
#51 lore raw
Quoted 11 lines · Andi Kleen
Quoted 5 lines · H. Peter Anvin

Not to mention that in that case we might as well -- since we need a compiler anyway -- generate the machine code in user space; the JIT solution really only is useful if it can provide something that we can't do otherwise, e.g. enable it in secure boot environments.

I can see there may be some setups which don't have a compiler (e.g. I know some people don't use systemtap because of that) But this needs a custom gcc install too as far as I understand.

Yes... but no compiler and secure boot tend to go together, or at least will in the future.

-hpa

#52 lore raw
Quoted 6 lines · hpa
Quoted 3 lines

I can see there may be some setups which don't have a compiler (e.g. I know some people don't use systemtap because of that) But this needs a custom gcc install too as far as I understand.

Yes... but no compiler and secure boot tend to go together, or at least will in the future.

(Maybe not: we're already experimenting with support for secureboot in systemtap.)

- FChE

#53 lore raw
In reply to Andi Kleen
Quoted 5 lines · Andi Kleen
Quoted 1 line

the difference is bigger now: 484-145 vs 185-145

This is a obvious improvement, but imho not big enough to be extremely compelling (< cost 1-2 cache misses, no orders of magnitude improvements that would justify a lot of code)

hmm. we're comparing against ktap here…
which has 5x more kernel code and 8x slower in this test...

Quoted 10 lines

Your code requires a compiler, so from my perspective it wouldn't be a lot easier or faster to use than just changing the code directly and recompile.

The users want something simple too that shields them from having to learn all the internals. They don't want to recompile. As far as I can tell your code is a bit too low level for that, and the requirement for the compiler may also scare them.

Where exactly does it fit?

the goal is to have llvm compiler next to perf, wrapped in a user friendly way.

compiling small filter vs recompiling full kernel… inserting into live kernel vs rebooting … not sure how you're saying it's equivalent.

In my kernel debugging experience current tools (tracing, systemtap) were rarely enough.
I always had to add my own printks through the code, recompile and reboot. Often just to see that it's not the place where I want to print things or it's too verbose.
Then I would adjust printks, recompile and reboot again.
That was slow and tedious, since I would be crashing things from time to time just because skb doesn't always have a valid dev or I made a typo. For debugging I do really need something quick and dirty that lets me add my own printk
of whatever structs I want anywhere in the kernel without crashing it. That's exactly what bpf tracing filters do.

#54 lore raw
Quoted 27 lines · Alexei Starovoitov
Quoted 5 lines · Andi Kleen
Quoted 1 line

the difference is bigger now: 484-145 vs 185-145

This is a obvious improvement, but imho not big enough to be extremely compelling (< cost 1-2 cache misses, no orders of magnitude improvements that would justify a lot of code)

hmm. we're comparing against ktap here…
which has 5x more kernel code and 8x slower in this test...

Quoted 10 lines

Your code requires a compiler, so from my perspective it wouldn't be a lot easier or faster to use than just changing the code directly and recompile.

The users want something simple too that shields them from having to learn all the internals. They don't want to recompile. As far as I can tell your code is a bit too low level for that, and the requirement for the compiler may also scare them.

Where exactly does it fit?

the goal is to have llvm compiler next to perf, wrapped in a user friendly way.

compiling small filter vs recompiling full kernel… inserting into live kernel vs rebooting … not sure how you're saying it's equivalent.

Quoted 12 lines

In my kernel debugging experience current tools (tracing, systemtap) were rarely enough.
I always had to add my own printks through the code, recompile and reboot. Often just to see that it's not the place where I want to print things or it's too verbose.
Then I would adjust printks, recompile and reboot again.
That was slow and tedious, since I would be crashing things from time to time just because skb doesn't always have a valid dev or I made a typo. For debugging I do really need something quick and dirty that lets me add my own printk
of whatever structs I want anywhere in the kernel without crashing it. That's exactly what bpf tracing filters do.

I recommend you to use perf-probe. That will give you an easy solution. :)

Thank you,

Signature · 4 lines
Masami HIRAMATSU
IT Management Research Dept. Linux Technology Center
Hitachi, Ltd., Yokohama Research Laboratory
E-mail: [email protected]
#55 lore raw
Quoted 41 lines · Masami Hiramatsu
Quoted 27 lines · Alexei Starovoitov
Quoted 5 lines · Andi Kleen
Quoted 1 line

the difference is bigger now: 484-145 vs 185-145

This is a obvious improvement, but imho not big enough to be extremely compelling (< cost 1-2 cache misses, no orders of magnitude improvements that would justify a lot of code)

hmm. we're comparing against ktap here…
which has 5x more kernel code and 8x slower in this test...

Quoted 10 lines

Your code requires a compiler, so from my perspective it wouldn't be a lot easier or faster to use than just changing the code directly and recompile.

The users want something simple too that shields them from having to learn all the internals. They don't want to recompile. As far as I can tell your code is a bit too low level for that, and the requirement for the compiler may also scare them.

Where exactly does it fit?

the goal is to have llvm compiler next to perf, wrapped in a user friendly way.

compiling small filter vs recompiling full kernel… inserting into live kernel vs rebooting … not sure how you're saying it's equivalent.

Quoted 12 lines

In my kernel debugging experience current tools (tracing, systemtap) were rarely enough.
I always had to add my own printks through the code, recompile and reboot. Often just to see that it's not the place where I want to print things or it's too verbose.
Then I would adjust printks, recompile and reboot again.
That was slow and tedious, since I would be crashing things from time to time just because skb doesn't always have a valid dev or I made a typo. For debugging I do really need something quick and dirty that lets me add my own printk
of whatever structs I want anywhere in the kernel without crashing it. That's exactly what bpf tracing filters do.

Quoted 1 line

I recommend you to use perf-probe. That will give you an easy solution. :)

it is indeed very cool.
Thanks!

#56 lore raw
In reply to Andi Kleen
Quoted 11 lines · Andi Kleen
Quoted 5 lines · H. Peter Anvin

Not to mention that in that case we might as well -- since we need a compiler anyway -- generate the machine code in user space; the JIT solution really only is useful if it can provide something that we can't do otherwise, e.g. enable it in secure boot environments.

I can see there may be some setups which don't have a compiler (e.g. I know some people don't use systemtap because of that) But this needs a custom gcc install too as far as I understand.

If it's depend on gcc, then it's look like Systemtap. There have big inconvenient for embedded environment and many production system to install gcc.
(not sure if it need kernel compilation environment as well)

It seems the event filter is binding to specific event, it's not possible to trace many events in a cooperation style, look Systemtap and ktap samples, many event handler need to cooperate, the simplest example is record syscall execution time(duration of exit - entry).

If this design is intentional, then I would think it's target for speed up current kernel tracing filter.(but need extra usespace filter compiler)

And I guess bpf filter still need to take mind on usespace tracing :), if it want to be a complete and integrated tracing solution. (use a separated userspace compiler or translator to resolve symbol)

Thanks

Jovi

#57 lore raw
In reply to Andi Kleen
Quoted 10 lines · Andi Kleen
Quoted 5 lines · H. Peter Anvin

Not to mention that in that case we might as well -- since we need a compiler anyway -- generate the machine code in user space; the JIT solution really only is useful if it can provide something that we can't do otherwise, e.g. enable it in secure boot environments.

I can see there may be some setups which don't have a compiler (e.g. I know some people don't use systemtap because of that) But this needs a custom gcc install too as far as I understand.

fyi custom gcc is a single 13M binary. It doesn't depend on any include files or any libraries.
and can be easily packaged together with perf... even for embedded environment.

#58 lore raw
Quoted 8 lines · Alexei Starovoitov
Quoted 7 lines · Andi Kleen
Quoted 5 lines · H. Peter Anvin

Not to mention that in that case we might as well -- since we need a compiler anyway -- generate the machine code in user space; the JIT solution really only is useful if it can provide something that we can't do otherwise, e.g. enable it in secure boot environments.

Quoted 7 lines
Quoted 3 lines

I can see there may be some setups which don't have a compiler (e.g. I know some people don't use systemtap because of that) But this needs a custom gcc install too as far as I understand.

fyi custom gcc is a single 13M binary. It doesn't depend on any include files or any libraries.
and can be easily packaged together with perf... even for embedded environment.

Hmm, 13M binary is big IMO, perf is just 5M after compiled in my system, I'm not sure embed a custom gcc into perf is a good idea. (and need to compile that custom gcc every time when build perf ?)

IMO gcc size is not all/main reason of why embedded system didn't install it, I saw many many production embedded system, no one install gcc, also gdb, etc. I would never expect Android will install gcc in some day, I also will really surprise if telcom-vender deliver Linux board with gcc installed to customers.

Another question is: does the custom gcc of bpf-filter need kernel header file for compilation? if it need, then this issue is more bigger than gcc size for embedded system.(same problem like Systemtap)

Thanks,

Jovi.

#59 lore raw
In reply to Alexei Starovoitov

Hi Alexei,

Quoted 54 lines · Alexei Starovoitov
Quoted 4 lines · Andi Kleen
Quoted 3 lines

Can you do some performance comparison compared to e.g. ktap? How much faster is it?

Did simple ktap test with 1M alloc_skb/kfree_skb toy test from earlier email:

trace skb:kfree_skb {
        if (arg2 == 0x100) {
                printf("%x %x\n", arg1, arg2)
        }
}

1M skb alloc/free 350315 (usecs)

baseline without any tracing:
1M skb alloc/free 145400 (usecs)

then equivalent bpf test:
void filter(struct bpf_context *ctx)

{
        void *loc = (void *)ctx->regs.dx;
        if (loc == 0x100) {
                struct sk_buff *skb = (struct sk_buff *)ctx->regs.si;
                char fmt[] = "skb %p loc %p\n";
                bpf_trace_printk(fmt, sizeof(fmt), (long)skb, (long)loc, 0);
        }
}

1M skb alloc/free 183214 (usecs)

so with one 'if' condition the difference ktap vs bpf is 350-145 vs 183-145

obviously ktap is an interpreter, so it's not really fair.

To make it really unfair I did:

trace skb:kfree_skb {
        if (arg2 == 0x100 || arg2 == 0x200 || arg2 == 0x300 || arg2 == 0x400 ||
            arg2 == 0x500 || arg2 == 0x600 || arg2 == 0x700 || arg2 == 0x800 ||
            arg2 == 0x900 || arg2 == 0x1000) {
                printf("%x %x\n", arg1, arg2)
        }
}

1M skb alloc/free 484280 (usecs)

and corresponding bpf:
void filter(struct bpf_context *ctx)

{
        void *loc = (void *)ctx->regs.dx;
        if (loc == 0x100 || loc == 0x200 || loc == 0x300 || loc == 0x400 ||
            loc == 0x500 || loc == 0x600 || loc == 0x700 || loc == 0x800 ||
            loc == 0x900 || loc == 0x1000) {
                struct sk_buff *skb = (struct sk_buff *)ctx->regs.si;
                char fmt[] = "skb %p loc %p\n";
                bpf_trace_printk(fmt, sizeof(fmt), (long)skb, (long)loc, 0);
        }
}
Quoted 4 lines

1M skb alloc/free 185660 (usecs)

the difference is bigger now: 484-145 vs 185-145

There have big differences for compare arg2(in ktap) with direct register access(ctx->regs.dx).

The current argument fetching(arg2 in above testcase) implementation in ktap is very inefficient, see ktap/interpreter/lib_kdebug.c:kp_event_getarg. The only way to speedup is kernel tracing code change, let external tracing module access event field not through list lookup. This work is not started yet. :)

Of course, I'm not saying this argument fetching issue is the performance root cause compared with bpf and Systemtap, the bytecode executing speed wouldn't compare with raw machine code.
(There have a plan to use JIT in ktap core, like luajit project, but it need some
time to work on)

#60 lore raw
Quoted 61 lines · Jovi Zhangwei

Hi Alexei,

Quoted 54 lines · Alexei Starovoitov
Quoted 4 lines · Andi Kleen
Quoted 3 lines

Can you do some performance comparison compared to e.g. ktap? How much faster is it?

Did simple ktap test with 1M alloc_skb/kfree_skb toy test from earlier email:

trace skb:kfree_skb {
        if (arg2 == 0x100) {
                printf("%x %x\n", arg1, arg2)
        }
}

1M skb alloc/free 350315 (usecs)

baseline without any tracing:
1M skb alloc/free 145400 (usecs)

then equivalent bpf test:
void filter(struct bpf_context *ctx)

{
        void *loc = (void *)ctx->regs.dx;
        if (loc == 0x100) {
                struct sk_buff *skb = (struct sk_buff *)ctx->regs.si;
                char fmt[] = "skb %p loc %p\n";
                bpf_trace_printk(fmt, sizeof(fmt), (long)skb, (long)loc, 0);
        }
}

1M skb alloc/free 183214 (usecs)

so with one 'if' condition the difference ktap vs bpf is 350-145 vs 183-145

obviously ktap is an interpreter, so it's not really fair.

To make it really unfair I did:

trace skb:kfree_skb {
        if (arg2 == 0x100 || arg2 == 0x200 || arg2 == 0x300 || arg2 == 0x400 ||
            arg2 == 0x500 || arg2 == 0x600 || arg2 == 0x700 || arg2 == 0x800 ||
            arg2 == 0x900 || arg2 == 0x1000) {
                printf("%x %x\n", arg1, arg2)
        }
}

1M skb alloc/free 484280 (usecs)

and corresponding bpf:
void filter(struct bpf_context *ctx)

{
        void *loc = (void *)ctx->regs.dx;
        if (loc == 0x100 || loc == 0x200 || loc == 0x300 || loc == 0x400 ||
            loc == 0x500 || loc == 0x600 || loc == 0x700 || loc == 0x800 ||
            loc == 0x900 || loc == 0x1000) {
                struct sk_buff *skb = (struct sk_buff *)ctx->regs.si;
                char fmt[] = "skb %p loc %p\n";
                bpf_trace_printk(fmt, sizeof(fmt), (long)skb, (long)loc, 0);
        }
}
Quoted 4 lines

1M skb alloc/free 185660 (usecs)

the difference is bigger now: 484-145 vs 185-145

Quoted 8 lines

There have big differences for compare arg2(in ktap) with direct register access(ctx->regs.dx).

The current argument fetching(arg2 in above testcase) implementation in ktap is very inefficient, see ktap/interpreter/lib_kdebug.c:kp_event_getarg. The only way to speedup is kernel tracing code change, let external tracing module access event field not through list lookup. This work is not started yet. :)

I'm not sure why you can't access it directly from ftrace-event buffer. There is just a packed data structure and it is exposed via debugfs. You can decode it and can get an offset/size by using libtraceevent.

Thank you,

Signature · 4 lines
Masami HIRAMATSU
IT Management Research Dept. Linux Technology Center
Hitachi, Ltd., Yokohama Research Laboratory
E-mail: [email protected]
#61 lore raw
Quoted 71 lines · Masami Hiramatsu
Quoted 61 lines · Jovi Zhangwei

Hi Alexei,

Quoted 54 lines · Alexei Starovoitov
Quoted 4 lines · Andi Kleen
Quoted 3 lines

Can you do some performance comparison compared to e.g. ktap? How much faster is it?

Did simple ktap test with 1M alloc_skb/kfree_skb toy test from earlier email:

trace skb:kfree_skb {
        if (arg2 == 0x100) {
                printf("%x %x\n", arg1, arg2)
        }
}

1M skb alloc/free 350315 (usecs)

baseline without any tracing:
1M skb alloc/free 145400 (usecs)

then equivalent bpf test:
void filter(struct bpf_context *ctx)

{
        void *loc = (void *)ctx->regs.dx;
        if (loc == 0x100) {
                struct sk_buff *skb = (struct sk_buff *)ctx->regs.si;
                char fmt[] = "skb %p loc %p\n";
                bpf_trace_printk(fmt, sizeof(fmt), (long)skb, (long)loc, 0);
        }
}

1M skb alloc/free 183214 (usecs)

so with one 'if' condition the difference ktap vs bpf is 350-145 vs 183-145

obviously ktap is an interpreter, so it's not really fair.

To make it really unfair I did:

trace skb:kfree_skb {
        if (arg2 == 0x100 || arg2 == 0x200 || arg2 == 0x300 || arg2 == 0x400 ||
            arg2 == 0x500 || arg2 == 0x600 || arg2 == 0x700 || arg2 == 0x800 ||
            arg2 == 0x900 || arg2 == 0x1000) {
                printf("%x %x\n", arg1, arg2)
        }
}

1M skb alloc/free 484280 (usecs)

and corresponding bpf:
void filter(struct bpf_context *ctx)

{
        void *loc = (void *)ctx->regs.dx;
        if (loc == 0x100 || loc == 0x200 || loc == 0x300 || loc == 0x400 ||
            loc == 0x500 || loc == 0x600 || loc == 0x700 || loc == 0x800 ||
            loc == 0x900 || loc == 0x1000) {
                struct sk_buff *skb = (struct sk_buff *)ctx->regs.si;
                char fmt[] = "skb %p loc %p\n";
                bpf_trace_printk(fmt, sizeof(fmt), (long)skb, (long)loc, 0);
        }
}
Quoted 4 lines

1M skb alloc/free 185660 (usecs)

the difference is bigger now: 484-145 vs 185-145

Quoted 8 lines

There have big differences for compare arg2(in ktap) with direct register access(ctx->regs.dx).

The current argument fetching(arg2 in above testcase) implementation in ktap is very inefficient, see ktap/interpreter/lib_kdebug.c:kp_event_getarg. The only way to speedup is kernel tracing code change, let external tracing module access event field not through list lookup. This work is not started yet. :)

Quoted 4 lines

I'm not sure why you can't access it directly from ftrace-event buffer. There is just a packed data structure and it is exposed via debugfs. You can decode it and can get an offset/size by using libtraceevent.

Then it means there need pass the event field info into kernel through trunk, it looks strange because the kernel structure is the source of event field info, it's like loop-back, and need to engage with libtraceevent in userspace. (the side effect is it will make compilation slow, and consume more memory, sometimes it will process 20K events in one script, like 'trace probe:big_dso:*')

So "the only way" which I said is wrong, your approach indeed is another way. I just think maybe use array instead of list for event fields would be more efficient if list is not must needed. we can check it more in future.

Thanks.

Jovi.

#62 lore raw
Quoted 73 lines · Jovi Zhangwei
Quoted 71 lines · Masami Hiramatsu
Quoted 69 lines · Jovi Zhangwei

Hi Alexei,

Quoted 54 lines · Alexei Starovoitov
Quoted 4 lines · Andi Kleen
Quoted 3 lines

Can you do some performance comparison compared to e.g. ktap? How much faster is it?

Did simple ktap test with 1M alloc_skb/kfree_skb toy test from earlier email:

trace skb:kfree_skb {
        if (arg2 == 0x100) {
                printf("%x %x\n", arg1, arg2)
        }
}

1M skb alloc/free 350315 (usecs)

baseline without any tracing:
1M skb alloc/free 145400 (usecs)

then equivalent bpf test:
void filter(struct bpf_context *ctx)

{
        void *loc = (void *)ctx->regs.dx;
        if (loc == 0x100) {
                struct sk_buff *skb = (struct sk_buff *)ctx->regs.si;
                char fmt[] = "skb %p loc %p\n";
                bpf_trace_printk(fmt, sizeof(fmt), (long)skb, (long)loc, 0);
        }
}

1M skb alloc/free 183214 (usecs)

so with one 'if' condition the difference ktap vs bpf is 350-145 vs 183-145

obviously ktap is an interpreter, so it's not really fair.

To make it really unfair I did:

trace skb:kfree_skb {
        if (arg2 == 0x100 || arg2 == 0x200 || arg2 == 0x300 || arg2 == 0x400 ||
            arg2 == 0x500 || arg2 == 0x600 || arg2 == 0x700 || arg2 == 0x800 ||
            arg2 == 0x900 || arg2 == 0x1000) {
                printf("%x %x\n", arg1, arg2)
        }
}

1M skb alloc/free 484280 (usecs)

and corresponding bpf:
void filter(struct bpf_context *ctx)

{
        void *loc = (void *)ctx->regs.dx;
        if (loc == 0x100 || loc == 0x200 || loc == 0x300 || loc == 0x400 ||
            loc == 0x500 || loc == 0x600 || loc == 0x700 || loc == 0x800 ||
            loc == 0x900 || loc == 0x1000) {
                struct sk_buff *skb = (struct sk_buff *)ctx->regs.si;
                char fmt[] = "skb %p loc %p\n";
                bpf_trace_printk(fmt, sizeof(fmt), (long)skb, (long)loc, 0);
        }
}
Quoted 4 lines

1M skb alloc/free 185660 (usecs)

the difference is bigger now: 484-145 vs 185-145

There have big differences for compare arg2(in ktap) with direct register access(ctx->regs.dx).

The current argument fetching(arg2 in above testcase) implementation in ktap is very inefficient, see ktap/interpreter/lib_kdebug.c:kp_event_getarg. The only way to speedup is kernel tracing code change, let external tracing module access event field not through list lookup. This work is not started yet. :)

Quoted 7 lines
Quoted 4 lines

I'm not sure why you can't access it directly from ftrace-event buffer. There is just a packed data structure and it is exposed via debugfs. You can decode it and can get an offset/size by using libtraceevent.

Then it means there need pass the event field info into kernel through trunk, it looks strange because the kernel structure is the source of event field info, it's like loop-back, and need to engage with libtraceevent in userspace.

No, the static traceevents have its own kernel data structure, but the dynamic events don't. They expose the data format (offset/type) via debugfs, but do not define new data structure.
So, I meant the script is enough to take an offset and a method casting to corresponding size.

Quoted 3 lines

(the side effect is it will make compilation slow, and consume more memory, sometimes it will process 20K events in one script, like 'trace probe:big_dso:*')

I doubt it, since you just need to get formats only for the events what the script using.

Quoted 3 lines

So "the only way" which I said is wrong, your approach indeed is another way. I just think maybe use array instead of list for event fields would be more efficient if list is not must needed. we can check it more in future.

Ah, perhaps, I misunderstood ktap implementation. Does it define dynamic events right before loading a bytecode? In that case, I recommend you to change a loader to adjust the bytecode after defining event to tune the offset information, which fits to the target event format.

e.g.
1) compile a bytecode with dummy offsets
2) define new additional dynamic events
3) get the field offset information from the events
4) modify the bytecode to replace offsets with correct one on memory
5) load the bytecode

Thank you,

Signature · 4 lines
Masami HIRAMATSU
IT Management Research Dept. Linux Technology Center
Hitachi, Ltd., Yokohama Research Laboratory
E-mail: [email protected]
#63 lore raw
In reply to Alexei Starovoitov
Quoted 33 lines · Alexei Starovoitov
Quoted 4 lines · Andi Kleen
Quoted 3 lines

Can you do some performance comparison compared to e.g. ktap? How much faster is it?

Did simple ktap test with 1M alloc_skb/kfree_skb toy test from earlier email:

trace skb:kfree_skb {
        if (arg2 == 0x100) {
                printf("%x %x\n", arg1, arg2)
        }
}

1M skb alloc/free 350315 (usecs)

baseline without any tracing:
1M skb alloc/free 145400 (usecs)

then equivalent bpf test:
void filter(struct bpf_context *ctx)

{
        void *loc = (void *)ctx->regs.dx;
        if (loc == 0x100) {
                struct sk_buff *skb = (struct sk_buff *)ctx->regs.si;
                char fmt[] = "skb %p loc %p\n";
                bpf_trace_printk(fmt, sizeof(fmt), (long)skb, (long)loc, 0);
        }
}

1M skb alloc/free 183214 (usecs)

so with one 'if' condition the difference ktap vs bpf is 350-145 vs 183-145

obviously ktap is an interpreter, so it's not really fair.

To make it really unfair I did:

Quoted 9 lines
trace skb:kfree_skb {
        if (arg2 == 0x100 || arg2 == 0x200 || arg2 == 0x300 || arg2 == 0x400 ||
            arg2 == 0x500 || arg2 == 0x600 || arg2 == 0x700 || arg2 == 0x800 ||
            arg2 == 0x900 || arg2 == 0x1000) {
                printf("%x %x\n", arg1, arg2)
        }
}

1M skb alloc/free 484280 (usecs)

I've lost my mind for a while. :)

If bpf only focus on filter, then it's not good to compare with ktap like that, since
ktap can easily make use on current kernel filter, you should use below script:

trace skb:kfree_skb /location == 0x100 || location == 0x200 || .../ {
    printf("%x %x\n", arg1, arg2)
}

As ktap is a user of current simple kernel tracing filter, I fully agree with Steven,
"it can be an add on, but not a replacement."

Thanks,

Jovi

#64 lore raw
In reply to Andi Kleen
Quoted 5 lines · Andi Kleen

[...] While it sounds interesting, I would strongly advise to make this capability only available to root. Traditionally lots of complex byte code languages which were designed to be "safe" and verifiable weren't really. e.g. i managed to crash things with "safe" systemtap multiple times. [...]

Note that systemtap has never been a byte code language, that avenue being considered lkml-futile at the time, but instead pure C. Its safety comes from a mix of compiled-in checks (which you can inspect via "stap -p3") and script-to-C translation checks (which are self-explanatory). Its risks come from bugs in the checks (quite rare), problems in the runtime library (rare), and problems in underlying kernel facilities (rare or frequent - consider kprobes).

Quoted 2 lines

So the likelyhood of this having some hole somewhere (either in the byte code or in some library function) is high.

Very true!

- FChE