[PATCH bpf-next v4 0/6] Introduce the BPF dispatcher

[PATCH bpf-next v4 0/6] Introduce the BPF dispatcher

[Björn Töpel]

Overview
========

This is the 5th iteration of the series that introduces the BPF
dispatcher, which is a mechanism to avoid indirect calls.

The BPF dispatcher is a multi-way branch code generator, targeted for
BPF programs. E.g. when an XDP program is executed via the
bpf_prog_run_xdp(), it is invoked via an indirect call. With
retpolines enabled, the indirect call has a substantial performance
impact. The dispatcher is a mechanism that transform indirect calls to
direct calls, and therefore avoids the retpoline. The dispatcher is
generated using the BPF JIT, and relies on text poking provided by
bpf_arch_text_poke().

The dispatcher hijacks a trampoline function it via the __fentry__ nop
of the trampoline. One dispatcher instance currently supports up to 48
dispatch points. This can be extended in the future.

In this series, only one dispatcher instance is supported, and the
only user is XDP. The dispatcher is updated when an XDP program is
attached/detached to/from a netdev. An alternative to this could have
been to update the dispatcher at program load point, but as there are
usually more XDP programs loaded than attached, so the latter was
picked.

The XDP dispatcher is always enabled, if available, because it helps
even when retpolines are disabled. Please refer to the "Performance"
section below.

The first patch refactors the image allocation from the BPF trampoline
code. Patch two introduces the dispatcher, and patch three adds a
dispatcher for XDP, and wires up the XDP control-/ fast-path. Patch
four adds the dispatcher to BPF_TEST_RUN. Patch five adds a simple
selftest, and the last adds alignment to jump targets.

I have rebased the series on commit e7096c131e51 ("net: WireGuard
secure network tunnel").

Generated code, x86-64
======================

The dispatcher currently has a maximum of 48 entries, where one entry
is a unique BPF program. Multiple users of a dispatcher instance using
the same BPF program will share that entry.

The program/slot lookup is performed by a binary search, O(log
n). Let's have a look at the generated code.

The trampoline function has the following signature:

  unsigned int tramp(const void *xdp_ctx,
                     const struct bpf_insn *insnsi,
                     unsigned int (*bpf_func)(const void *,
                                              const struct bpf_insn *))

On Intel x86-64 this means that rdx will contain the bpf_func. To,
make it easier to read, I've let the BPF programs have the following
range: 0xffffffffffffffff (-1) to 0xfffffffffffffff0
(-16). 0xffffffff81c00f10 is the retpoline thunk, in this case
__x86_indirect_thunk_rdx. If retpolines are disabled the thunk will be
a regular indirect call.

The minimal dispatcher will then look like this:

ffffffffc0002000: cmp    rdx,0xffffffffffffffff
ffffffffc0002007: je     0xffffffffffffffff ; -1
ffffffffc000200d: jmp    0xffffffff81c00f10

A 16 entry dispatcher looks like this:

ffffffffc0020000: cmp    rdx,0xfffffffffffffff7 ; -9
ffffffffc0020007: jg     0xffffffffc0020130
ffffffffc002000d: cmp    rdx,0xfffffffffffffff3 ; -13
ffffffffc0020014: jg     0xffffffffc00200a0
ffffffffc002001a: cmp    rdx,0xfffffffffffffff1 ; -15
ffffffffc0020021: jg     0xffffffffc0020060
ffffffffc0020023: cmp    rdx,0xfffffffffffffff0 ; -16
ffffffffc002002a: jg     0xffffffffc0020040
ffffffffc002002c: cmp    rdx,0xfffffffffffffff0 ; -16
ffffffffc0020033: je     0xfffffffffffffff0 ; -16
ffffffffc0020039: jmp    0xffffffff81c00f10
ffffffffc002003e: xchg   ax,ax
ffffffffc0020040: cmp    rdx,0xfffffffffffffff1 ; -15
ffffffffc0020047: je     0xfffffffffffffff1 ; -15
ffffffffc002004d: jmp    0xffffffff81c00f10
ffffffffc0020052: nop    DWORD PTR [rax+rax*1+0x0]
ffffffffc002005a: nop    WORD PTR [rax+rax*1+0x0]
ffffffffc0020060: cmp    rdx,0xfffffffffffffff2 ; -14
ffffffffc0020067: jg     0xffffffffc0020080
ffffffffc0020069: cmp    rdx,0xfffffffffffffff2 ; -14
ffffffffc0020070: je     0xfffffffffffffff2 ; -14
ffffffffc0020076: jmp    0xffffffff81c00f10
ffffffffc002007b: nop    DWORD PTR [rax+rax*1+0x0]
ffffffffc0020080: cmp    rdx,0xfffffffffffffff3 ; -13
ffffffffc0020087: je     0xfffffffffffffff3 ; -13
ffffffffc002008d: jmp    0xffffffff81c00f10
ffffffffc0020092: nop    DWORD PTR [rax+rax*1+0x0]
ffffffffc002009a: nop    WORD PTR [rax+rax*1+0x0]
ffffffffc00200a0: cmp    rdx,0xfffffffffffffff5 ; -11
ffffffffc00200a7: jg     0xffffffffc00200f0
ffffffffc00200a9: cmp    rdx,0xfffffffffffffff4 ; -12
ffffffffc00200b0: jg     0xffffffffc00200d0
ffffffffc00200b2: cmp    rdx,0xfffffffffffffff4 ; -12
ffffffffc00200b9: je     0xfffffffffffffff4 ; -12
ffffffffc00200bf: jmp    0xffffffff81c00f10
ffffffffc00200c4: nop    DWORD PTR [rax+rax*1+0x0]
ffffffffc00200cc: nop    DWORD PTR [rax+0x0]
ffffffffc00200d0: cmp    rdx,0xfffffffffffffff5 ; -11
ffffffffc00200d7: je     0xfffffffffffffff5 ; -11
ffffffffc00200dd: jmp    0xffffffff81c00f10
ffffffffc00200e2: nop    DWORD PTR [rax+rax*1+0x0]
ffffffffc00200ea: nop    WORD PTR [rax+rax*1+0x0]
ffffffffc00200f0: cmp    rdx,0xfffffffffffffff6 ; -10
ffffffffc00200f7: jg     0xffffffffc0020110
ffffffffc00200f9: cmp    rdx,0xfffffffffffffff6 ; -10
ffffffffc0020100: je     0xfffffffffffffff6 ; -10
ffffffffc0020106: jmp    0xffffffff81c00f10
ffffffffc002010b: nop    DWORD PTR [rax+rax*1+0x0]
ffffffffc0020110: cmp    rdx,0xfffffffffffffff7 ; -9
ffffffffc0020117: je     0xfffffffffffffff7 ; -9
ffffffffc002011d: jmp    0xffffffff81c00f10
ffffffffc0020122: nop    DWORD PTR [rax+rax*1+0x0]
ffffffffc002012a: nop    WORD PTR [rax+rax*1+0x0]
ffffffffc0020130: cmp    rdx,0xfffffffffffffffb ; -5
ffffffffc0020137: jg     0xffffffffc00201d0
ffffffffc002013d: cmp    rdx,0xfffffffffffffff9 ; -7
ffffffffc0020144: jg     0xffffffffc0020190
ffffffffc0020146: cmp    rdx,0xfffffffffffffff8 ; -8
ffffffffc002014d: jg     0xffffffffc0020170
ffffffffc002014f: cmp    rdx,0xfffffffffffffff8 ; -8
ffffffffc0020156: je     0xfffffffffffffff8 ; -8
ffffffffc002015c: jmp    0xffffffff81c00f10
ffffffffc0020161: nop    DWORD PTR [rax+rax*1+0x0]
ffffffffc0020169: nop    DWORD PTR [rax+0x0]
ffffffffc0020170: cmp    rdx,0xfffffffffffffff9 ; -7
ffffffffc0020177: je     0xfffffffffffffff9 ; -7
ffffffffc002017d: jmp    0xffffffff81c00f10
ffffffffc0020182: nop    DWORD PTR [rax+rax*1+0x0]
ffffffffc002018a: nop    WORD PTR [rax+rax*1+0x0]
ffffffffc0020190: cmp    rdx,0xfffffffffffffffa ; -6
ffffffffc0020197: jg     0xffffffffc00201b0
ffffffffc0020199: cmp    rdx,0xfffffffffffffffa ; -6
ffffffffc00201a0: je     0xfffffffffffffffa ; -6
ffffffffc00201a6: jmp    0xffffffff81c00f10
ffffffffc00201ab: nop    DWORD PTR [rax+rax*1+0x0]
ffffffffc00201b0: cmp    rdx,0xfffffffffffffffb ; -5
ffffffffc00201b7: je     0xfffffffffffffffb ; -5
ffffffffc00201bd: jmp    0xffffffff81c00f10
ffffffffc00201c2: nop    DWORD PTR [rax+rax*1+0x0]
ffffffffc00201ca: nop    WORD PTR [rax+rax*1+0x0]
ffffffffc00201d0: cmp    rdx,0xfffffffffffffffd ; -3
ffffffffc00201d7: jg     0xffffffffc0020220
ffffffffc00201d9: cmp    rdx,0xfffffffffffffffc ; -4
ffffffffc00201e0: jg     0xffffffffc0020200
ffffffffc00201e2: cmp    rdx,0xfffffffffffffffc ; -4
ffffffffc00201e9: je     0xfffffffffffffffc ; -4
ffffffffc00201ef: jmp    0xffffffff81c00f10
ffffffffc00201f4: nop    DWORD PTR [rax+rax*1+0x0]
ffffffffc00201fc: nop    DWORD PTR [rax+0x0]
ffffffffc0020200: cmp    rdx,0xfffffffffffffffd ; -3
ffffffffc0020207: je     0xfffffffffffffffd ; -3
ffffffffc002020d: jmp    0xffffffff81c00f10
ffffffffc0020212: nop    DWORD PTR [rax+rax*1+0x0]
ffffffffc002021a: nop    WORD PTR [rax+rax*1+0x0]
ffffffffc0020220: cmp    rdx,0xfffffffffffffffe ; -2
ffffffffc0020227: jg     0xffffffffc0020240
ffffffffc0020229: cmp    rdx,0xfffffffffffffffe ; -2
ffffffffc0020230: je     0xfffffffffffffffe ; -2
ffffffffc0020236: jmp    0xffffffff81c00f10
ffffffffc002023b: nop    DWORD PTR [rax+rax*1+0x0]
ffffffffc0020240: cmp    rdx,0xffffffffffffffff ; -1
ffffffffc0020247: je     0xffffffffffffffff ; -1
ffffffffc002024d: jmp    0xffffffff81c00f10

The nops are there to align jump targets to 16 B.

Performance
===========

The tests were performed using the xdp_rxq_info sample program with
the following command-line:

1. XDP_DRV:
  # xdp_rxq_info --dev eth0 --action XDP_DROP
2. XDP_SKB:
  # xdp_rxq_info --dev eth0 -S --action XDP_DROP
3. xdp-perf, from selftests/bpf:
  # test_progs -v -t xdp_perf


Run with mitigations=auto
-------------------------

Baseline:
1. 21.7 Mpps (21736190)
2. 3.8 Mpps   (3837582)
3. 15 ns

Dispatcher:
1. 30.2 Mpps (30176320)
2. 4.0 Mpps   (4015579)
3. 5 ns      

Dispatcher (full; walk all entries, and fallback):
1. 22.0 Mpps (21986704)
2. 3.8 Mpps   (3831298)
3. 17 ns     

Run with mitigations=off
------------------------

Baseline:
1. 29.9 Mpps (29875135)
2. 4.1 Mpps   (4100179)
3. 4 ns

Dispatcher:
1. 30.4 Mpps (30439241)
2. 4.1 Mpps   (4109350)
1. 4 ns

Dispatcher (full; walk all entries, and fallback):
1. 28.9 Mpps (28903269)
2. 4.1 Mpps   (4080078)
3. 5 ns      

xdp-perf runs, aliged vs non-aligned jump targets
-------------------------------------------------

In this test dispatchers of different sizes, with and without jump
target alignment, were exercised. As outlined above the function
lookup is performed via binary search. This means that depending on
the pointer value of the function, it can reside in the upper or lower
part of the search table. The performed tests were:

1. aligned, mititations=auto, function entry < other entries
2. aligned, mititations=auto, function entry > other entries
3. non-aligned, mititations=auto, function entry < other entries
4. non-aligned, mititations=auto, function entry > other entries
5. aligned, mititations=off, function entry < other entries
6. aligned, mititations=off, function entry > other entries
7. non-aligned, mititations=off, function entry < other entries
8. non-aligned, mititations=off, function entry > other entries

The micro benchmarks showed that alignment of jump target has some
positive impact.

A reply to this cover letter will contain complete data for all runs.

Multiple xdp-perf baseline with mitigations=auto
------------------------------------------------

 Performance counter stats for './test_progs -v -t xdp_perf' (1024 runs):

             16.69 msec task-clock                #    0.984 CPUs utilized            ( +-  0.08% )
                 2      context-switches          #    0.123 K/sec                    ( +-  1.11% )
                 0      cpu-migrations            #    0.000 K/sec                    ( +- 70.68% )
                97      page-faults               #    0.006 M/sec                    ( +-  0.05% )
        49,254,635      cycles                    #    2.951 GHz                      ( +-  0.09% )  (12.28%)
        42,138,558      instructions              #    0.86  insn per cycle           ( +-  0.02% )  (36.15%)
         7,315,291      branches                  #  438.300 M/sec                    ( +-  0.01% )  (59.43%)
         1,011,201      branch-misses             #   13.82% of all branches          ( +-  0.01% )  (83.31%)
        15,440,788      L1-dcache-loads           #  925.143 M/sec                    ( +-  0.00% )  (99.40%)
            39,067      L1-dcache-load-misses     #    0.25% of all L1-dcache hits    ( +-  0.04% )
             6,531      LLC-loads                 #    0.391 M/sec                    ( +-  0.05% )
               442      LLC-load-misses           #    6.76% of all LL-cache hits     ( +-  0.77% )
   <not supported>      L1-icache-loads                                             
            57,964      L1-icache-load-misses                                         ( +-  0.06% )
        15,442,496      dTLB-loads                #  925.246 M/sec                    ( +-  0.00% )
               514      dTLB-load-misses          #    0.00% of all dTLB cache hits   ( +-  0.73% )  (40.57%)
               130      iTLB-loads                #    0.008 M/sec                    ( +-  2.75% )  (16.69%)
     <not counted>      iTLB-load-misses                                              ( +-  8.71% )  (0.60%)
   <not supported>      L1-dcache-prefetches                                        
   <not supported>      L1-dcache-prefetch-misses                                   

         0.0169558 +- 0.0000127 seconds time elapsed  ( +-  0.07% )

Multiple xdp-perf dispatcher with mitigations=auto
--------------------------------------------------

Note that this includes generating the dispatcher.

 Performance counter stats for './test_progs -v -t xdp_perf' (1024 runs):

              4.80 msec task-clock                #    0.953 CPUs utilized            ( +-  0.06% )
                 1      context-switches          #    0.258 K/sec                    ( +-  1.57% )
                 0      cpu-migrations            #    0.000 K/sec                  
                97      page-faults               #    0.020 M/sec                    ( +-  0.05% )
        14,185,861      cycles                    #    2.955 GHz                      ( +-  0.17% )  (50.49%)
        45,691,935      instructions              #    3.22  insn per cycle           ( +-  0.01% )  (99.19%)
         8,346,008      branches                  # 1738.709 M/sec                    ( +-  0.00% )
            13,046      branch-misses             #    0.16% of all branches          ( +-  0.10% )
        15,443,735      L1-dcache-loads           # 3217.365 M/sec                    ( +-  0.00% )
            39,585      L1-dcache-load-misses     #    0.26% of all L1-dcache hits    ( +-  0.05% )
             7,138      LLC-loads                 #    1.487 M/sec                    ( +-  0.06% )
               671      LLC-load-misses           #    9.40% of all LL-cache hits     ( +-  0.73% )
   <not supported>      L1-icache-loads                                             
            56,213      L1-icache-load-misses                                         ( +-  0.08% )
        15,443,735      dTLB-loads                # 3217.365 M/sec                    ( +-  0.00% )
     <not counted>      dTLB-load-misses                                              (0.00%)
     <not counted>      iTLB-loads                                                    (0.00%)
     <not counted>      iTLB-load-misses                                              (0.00%)
   <not supported>      L1-dcache-prefetches                                        
   <not supported>      L1-dcache-prefetch-misses                                   

        0.00503705 +- 0.00000546 seconds time elapsed  ( +-  0.11% )


Revisions
=========

v3->v4: [1] 
  * Moved away from doing dispatcher lookup based on the trampoline
    function, to a model where the dispatcher instance is explicitly
    passed to the bpf_dispatcher_change_prog() (Alexei)

v2->v3: [2]
  * Removed xdp_call, and instead make the dispatcher available to all
    XDP users via bpf_prog_run_xdp() and dev_xdp_install(). (Toke)
  * Always enable the dispatcher, if available (Alexei)
  * Reuse BPF trampoline image allocator (Alexei)
  * Make sure the dispatcher is exercised in selftests (Alexei)
  * Only allow one dispatcher, and wire it to XDP

v1->v2: [3]
  * Fixed i386 build warning (kbuild robot)
  * Made bpf_dispatcher_lookup() static (kbuild robot)
  * Make sure xdp_call.h is only enabled for builtins
  * Add xdp_call() to ixgbe, mlx4, and mlx5

RFC->v1: [4]
  * Improved error handling (Edward and Andrii)
  * Explicit cleanup (Andrii)
  * Use 32B with sext cmp (Alexei)
  * Align jump targets to 16B (Alexei)
  * 4 to 16 entries (Toke)
  * Added stats to xdp_call_run()

[1] https://lore.kernel.org/bpf/20191209135522.16576-1-bjorn.topel@gmail.com/
[2] https://lore.kernel.org/bpf/20191123071226.6501-1-bjorn.topel@gmail.com/
[3] https://lore.kernel.org/bpf/20191119160757.27714-1-bjorn.topel@gmail.com/
[4] https://lore.kernel.org/bpf/20191113204737.31623-1-bjorn.topel@gmail.com/

Björn Töpel (6):
  bpf: move trampoline JIT image allocation to a function
  bpf: introduce BPF dispatcher
  bpf, xdp: start using the BPF dispatcher for XDP
  bpf: start using the BPF dispatcher in BPF_TEST_RUN
  selftests: bpf: add xdp_perf test
  bpf, x86: align dispatcher branch targets to 16B

 arch/x86/net/bpf_jit_comp.c                   | 150 +++++++++++++++++
 include/linux/bpf.h                           |  72 ++++++++
 include/linux/filter.h                        |  40 +++--
 kernel/bpf/Makefile                           |   1 +
 kernel/bpf/dispatcher.c                       | 159 ++++++++++++++++++
 kernel/bpf/syscall.c                          |  26 ++-
 kernel/bpf/trampoline.c                       |  24 ++-
 net/bpf/test_run.c                            |  15 +-
 net/core/dev.c                                |  19 ++-
 net/core/filter.c                             |   8 +
 .../selftests/bpf/prog_tests/xdp_perf.c       |  25 +++
 11 files changed, 502 insertions(+), 37 deletions(-)
 create mode 100644 kernel/bpf/dispatcher.c
 create mode 100644 tools/testing/selftests/bpf/prog_tests/xdp_perf.c

-- 
2.20.1

[PATCH bpf-next v4 1/6] bpf: move trampoline JIT image allocation to a function

[Björn Töpel]

From: Björn Töpel <bjorn.topel@intel.com>

Refactor the image allocation in the BPF trampoline code into a
separate function, so it can be shared with the BPF dispatcher in
upcoming commits.

Signed-off-by: Björn Töpel <bjorn.topel@intel.com>
---
 include/linux/bpf.h     |  1 +
 kernel/bpf/trampoline.c | 24 +++++++++++++++++-------
 2 files changed, 18 insertions(+), 7 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 35903f148be5..5d744828b399 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -475,6 +475,7 @@ struct bpf_trampoline *bpf_trampoline_lookup(u64 key);
 int bpf_trampoline_link_prog(struct bpf_prog *prog);
 int bpf_trampoline_unlink_prog(struct bpf_prog *prog);
 void bpf_trampoline_put(struct bpf_trampoline *tr);
+void *bpf_jit_alloc_exec_page(void);
 #else
 static inline struct bpf_trampoline *bpf_trampoline_lookup(u64 key)
 {
diff --git a/kernel/bpf/trampoline.c b/kernel/bpf/trampoline.c
index 7e89f1f49d77..5ee301ddbd00 100644
--- a/kernel/bpf/trampoline.c
+++ b/kernel/bpf/trampoline.c
@@ -13,6 +13,22 @@ static struct hlist_head trampoline_table[TRAMPOLINE_TABLE_SIZE];
 /* serializes access to trampoline_table */
 static DEFINE_MUTEX(trampoline_mutex);
 
+void *bpf_jit_alloc_exec_page(void)
+{
+	void *image;
+
+	image = bpf_jit_alloc_exec(PAGE_SIZE);
+	if (!image)
+		return NULL;
+
+	set_vm_flush_reset_perms(image);
+	/* Keep image as writeable. The alternative is to keep flipping ro/rw
+	 * everytime new program is attached or detached.
+	 */
+	set_memory_x((long)image, 1);
+	return image;
+}
+
 struct bpf_trampoline *bpf_trampoline_lookup(u64 key)
 {
 	struct bpf_trampoline *tr;
@@ -33,7 +49,7 @@ struct bpf_trampoline *bpf_trampoline_lookup(u64 key)
 		goto out;
 
 	/* is_root was checked earlier. No need for bpf_jit_charge_modmem() */
-	image = bpf_jit_alloc_exec(PAGE_SIZE);
+	image = bpf_jit_alloc_exec_page();
 	if (!image) {
 		kfree(tr);
 		tr = NULL;
@@ -47,12 +63,6 @@ struct bpf_trampoline *bpf_trampoline_lookup(u64 key)
 	mutex_init(&tr->mutex);
 	for (i = 0; i < BPF_TRAMP_MAX; i++)
 		INIT_HLIST_HEAD(&tr->progs_hlist[i]);
-
-	set_vm_flush_reset_perms(image);
-	/* Keep image as writeable. The alternative is to keep flipping ro/rw
-	 * everytime new program is attached or detached.
-	 */
-	set_memory_x((long)image, 1);
 	tr->image = image;
 out:
 	mutex_unlock(&trampoline_mutex);
-- 
2.20.1

[PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Björn Töpel]

From: Björn Töpel <bjorn.topel@intel.com>

The BPF dispatcher is a multi-way branch code generator, mainly
targeted for XDP programs. When an XDP program is executed via the
bpf_prog_run_xdp(), it is invoked via an indirect call. The indirect
call has a substantial performance impact, when retpolines are
enabled. The dispatcher transform indirect calls to direct calls, and
therefore avoids the retpoline. The dispatcher is generated using the
BPF JIT, and relies on text poking provided by bpf_arch_text_poke().

The dispatcher hijacks a trampoline function it via the __fentry__ nop
of the trampoline. One dispatcher instance currently supports up to 64
dispatch points. A user creates a dispatcher with its corresponding
trampoline with the DEFINE_BPF_DISPATCHER macro.

Signed-off-by: Björn Töpel <bjorn.topel@intel.com>
---
 arch/x86/net/bpf_jit_comp.c | 122 +++++++++++++++++++++++++++
 include/linux/bpf.h         |  56 +++++++++++++
 kernel/bpf/Makefile         |   1 +
 kernel/bpf/dispatcher.c     | 159 ++++++++++++++++++++++++++++++++++++
 4 files changed, 338 insertions(+)
 create mode 100644 kernel/bpf/dispatcher.c

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index b8be18427277..3ce7ad41bd6f 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -10,10 +10,12 @@
 #include <linux/if_vlan.h>
 #include <linux/bpf.h>
 #include <linux/memory.h>
+#include <linux/sort.h>
 #include <asm/extable.h>
 #include <asm/set_memory.h>
 #include <asm/nospec-branch.h>
 #include <asm/text-patching.h>
+#include <asm/asm-prototypes.h>
 
 static u8 *emit_code(u8 *ptr, u32 bytes, unsigned int len)
 {
@@ -1530,6 +1532,126 @@ int arch_prepare_bpf_trampoline(void *image, struct btf_func_model *m, u32 flags
 	return 0;
 }
 
+static int emit_cond_near_jump(u8 **pprog, void *func, void *ip, u8 jmp_cond)
+{
+	u8 *prog = *pprog;
+	int cnt = 0;
+	s64 offset;
+
+	offset = func - (ip + 2 + 4);
+	if (!is_simm32(offset)) {
+		pr_err("Target %p is out of range\n", func);
+		return -EINVAL;
+	}
+	EMIT2_off32(0x0F, jmp_cond + 0x10, offset);
+	*pprog = prog;
+	return 0;
+}
+
+static int emit_fallback_jump(u8 **pprog)
+{
+	u8 *prog = *pprog;
+	int err = 0;
+
+#ifdef CONFIG_RETPOLINE
+	/* Note that this assumes the the compiler uses external
+	 * thunks for indirect calls. Both clang and GCC use the same
+	 * naming convention for external thunks.
+	 */
+	err = emit_jump(&prog, __x86_indirect_thunk_rdx, prog);
+#else
+	int cnt = 0;
+
+	EMIT2(0xFF, 0xE2);	/* jmp rdx */
+#endif
+	*pprog = prog;
+	return err;
+}
+
+static int emit_bpf_dispatcher(u8 **pprog, int a, int b, s64 *progs)
+{
+	int pivot, err, jg_bytes = 1, cnt = 0;
+	u8 *jg_reloc, *prog = *pprog;
+	s64 jg_offset;
+
+	if (a == b) {
+		/* Leaf node of recursion, i.e. not a range of indices
+		 * anymore.
+		 */
+		EMIT1(add_1mod(0x48, BPF_REG_3));	/* cmp rdx,func */
+		if (!is_simm32(progs[a]))
+			return -1;
+		EMIT2_off32(0x81, add_1reg(0xF8, BPF_REG_3),
+			    progs[a]);
+		err = emit_cond_near_jump(&prog,	/* je func */
+					  (void *)progs[a], prog,
+					  X86_JE);
+		if (err)
+			return err;
+
+		err = emit_fallback_jump(&prog);	/* jmp thunk/indirect */
+		if (err)
+			return err;
+
+		*pprog = prog;
+		return 0;
+	}
+
+	/* Not a leaf node, so we pivot, and recursively descend into
+	 * the lower and upper ranges.
+	 */
+	pivot = (b - a) / 2;
+	EMIT1(add_1mod(0x48, BPF_REG_3));		/* cmp rdx,func */
+	if (!is_simm32(progs[a + pivot]))
+		return -1;
+	EMIT2_off32(0x81, add_1reg(0xF8, BPF_REG_3), progs[a + pivot]);
+
+	if (pivot > 2) {				/* jg upper_part */
+		/* Require near jump. */
+		jg_bytes = 4;
+		EMIT2_off32(0x0F, X86_JG + 0x10, 0);
+	} else {
+		EMIT2(X86_JG, 0);
+	}
+	jg_reloc = prog;
+
+	err = emit_bpf_dispatcher(&prog, a, a + pivot,	/* emit lower_part */
+				  progs);
+	if (err)
+		return err;
+
+	jg_offset = prog - jg_reloc;
+	emit_code(jg_reloc - jg_bytes, jg_offset, jg_bytes);
+
+	err = emit_bpf_dispatcher(&prog, a + pivot + 1,	/* emit upper_part */
+				  b, progs);
+	if (err)
+		return err;
+
+	*pprog = prog;
+	return 0;
+}
+
+static int cmp_ips(const void *a, const void *b)
+{
+	const s64 *ipa = a;
+	const s64 *ipb = b;
+
+	if (*ipa > *ipb)
+		return 1;
+	if (*ipa < *ipb)
+		return -1;
+	return 0;
+}
+
+int arch_prepare_bpf_dispatcher(void *image, s64 *funcs, int num_funcs)
+{
+	u8 *prog = image;
+
+	sort(funcs, num_funcs, sizeof(funcs[0]), cmp_ips, NULL);
+	return emit_bpf_dispatcher(&prog, 0, num_funcs - 1, funcs);
+}
+
 struct x64_jit_data {
 	struct bpf_binary_header *header;
 	int *addrs;
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 5d744828b399..e6a9d74d4e30 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -470,12 +470,61 @@ struct bpf_trampoline {
 	void *image;
 	u64 selector;
 };
+
+#define BPF_DISPATCHER_MAX 64 /* Fits in 2048B */
+
+struct bpf_dispatcher_prog {
+	struct bpf_prog *prog;
+	refcount_t users;
+};
+
+struct bpf_dispatcher {
+	/* dispatcher mutex */
+	struct mutex mutex;
+	void *func;
+	struct bpf_dispatcher_prog progs[BPF_DISPATCHER_MAX];
+	int num_progs;
+	void *image;
+	u32 image_off;
+};
+
 #ifdef CONFIG_BPF_JIT
 struct bpf_trampoline *bpf_trampoline_lookup(u64 key);
 int bpf_trampoline_link_prog(struct bpf_prog *prog);
 int bpf_trampoline_unlink_prog(struct bpf_prog *prog);
 void bpf_trampoline_put(struct bpf_trampoline *tr);
 void *bpf_jit_alloc_exec_page(void);
+#define BPF_DISPATCHER_INIT(name) {			\
+	.mutex = __MUTEX_INITIALIZER(name.mutex),	\
+	.func = &name##func,				\
+	.progs = {},					\
+	.num_progs = 0,					\
+	.image = NULL,					\
+	.image_off = 0					\
+}
+
+#define DEFINE_BPF_DISPATCHER(name)					\
+	unsigned int name##func(					\
+		const void *xdp_ctx,					\
+		const struct bpf_insn *insnsi,				\
+		unsigned int (*bpf_func)(const void *,			\
+					 const struct bpf_insn *))	\
+	{								\
+		return bpf_func(xdp_ctx, insnsi);			\
+	}								\
+	EXPORT_SYMBOL(name##func);			\
+	struct bpf_dispatcher name = BPF_DISPATCHER_INIT(name);
+#define DECLARE_BPF_DISPATCHER(name)					\
+	unsigned int name##func(					\
+		const void *xdp_ctx,					\
+		const struct bpf_insn *insnsi,				\
+		unsigned int (*bpf_func)(const void *,			\
+					 const struct bpf_insn *));	\
+	extern struct bpf_dispatcher name;
+#define BPF_DISPATCHER_FUNC(name) name##func
+#define BPF_DISPATCHER_PTR(name) (&name)
+void bpf_dispatcher_change_prog(struct bpf_dispatcher *d, struct bpf_prog *from,
+				struct bpf_prog *to);
 #else
 static inline struct bpf_trampoline *bpf_trampoline_lookup(u64 key)
 {
@@ -490,6 +539,13 @@ static inline int bpf_trampoline_unlink_prog(struct bpf_prog *prog)
 	return -ENOTSUPP;
 }
 static inline void bpf_trampoline_put(struct bpf_trampoline *tr) {}
+#define DEFINE_BPF_DISPATCHER(name)
+#define DECLARE_BPF_DISPATCHER(name)
+#define BPF_DISPATCHER_FUNC(name) bpf_dispatcher_nopfunc
+#define BPF_DISPATCHER_PTR(name) NULL
+static inline void bpf_dispatcher_change_prog(struct bpf_dispatcher *d,
+					      struct bpf_prog *from,
+					      struct bpf_prog *to) {}
 #endif
 
 struct bpf_func_info_aux {
diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
index 3f671bf617e8..d4f330351f87 100644
--- a/kernel/bpf/Makefile
+++ b/kernel/bpf/Makefile
@@ -8,6 +8,7 @@ obj-$(CONFIG_BPF_SYSCALL) += local_storage.o queue_stack_maps.o
 obj-$(CONFIG_BPF_SYSCALL) += disasm.o
 obj-$(CONFIG_BPF_JIT) += trampoline.o
 obj-$(CONFIG_BPF_SYSCALL) += btf.o
+obj-$(CONFIG_BPF_JIT) += dispatcher.o
 ifeq ($(CONFIG_NET),y)
 obj-$(CONFIG_BPF_SYSCALL) += devmap.o
 obj-$(CONFIG_BPF_SYSCALL) += cpumap.o
diff --git a/kernel/bpf/dispatcher.c b/kernel/bpf/dispatcher.c
new file mode 100644
index 000000000000..a4690460d815
--- /dev/null
+++ b/kernel/bpf/dispatcher.c
@@ -0,0 +1,159 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/* Copyright(c) 2019 Intel Corporation. */
+
+#include <linux/hash.h>
+#include <linux/bpf.h>
+#include <linux/filter.h>
+
+/* The BPF dispatcher is a multiway branch code generator. The
+ * dispatcher is a mechanism to avoid the performance penalty of an
+ * indirect call, which is expensive when retpolines are enabled. A
+ * dispatch client registers a BPF program into the dispatcher, and if
+ * there is available room in the dispatcher a direct call to the BPF
+ * program will be generated. All calls to the BPF programs called via
+ * the dispatcher will then be a direct call, instead of an
+ * indirect. The dispatcher hijacks a trampoline function it via the
+ * __fentry__ of the trampoline. The trampoline function has the
+ * following signature:
+ *
+ * unsigned int trampoline(const void *xdp_ctx,
+ *                         const struct bpf_insn *insnsi,
+ *                         unsigned int (*bpf_func)(const void *,
+ *                                                  const struct bpf_insn *));
+ */
+
+static struct bpf_dispatcher_prog *bpf_dispatcher_find_prog(
+	struct bpf_dispatcher *d, struct bpf_prog *prog)
+{
+	int i;
+
+	for (i = 0; i < BPF_DISPATCHER_MAX; i++) {
+		if (prog == d->progs[i].prog)
+			return &d->progs[i];
+	}
+	return NULL;
+}
+
+static struct bpf_dispatcher_prog *bpf_dispatcher_find_free(
+	struct bpf_dispatcher *d)
+{
+	return bpf_dispatcher_find_prog(d, NULL);
+}
+
+static bool bpf_dispatcher_add_prog(struct bpf_dispatcher *d,
+				    struct bpf_prog *prog)
+{
+	struct bpf_dispatcher_prog *entry;
+
+	if (!prog)
+		return false;
+
+	entry = bpf_dispatcher_find_prog(d, prog);
+	if (entry) {
+		refcount_inc(&entry->users);
+		return false;
+	}
+
+	entry = bpf_dispatcher_find_free(d);
+	if (!entry)
+		return false;
+
+	bpf_prog_inc(prog);
+	entry->prog = prog;
+	refcount_set(&entry->users, 1);
+	d->num_progs++;
+	return true;
+}
+
+static bool bpf_dispatcher_remove_prog(struct bpf_dispatcher *d,
+				       struct bpf_prog *prog)
+{
+	struct bpf_dispatcher_prog *entry;
+
+	if (!prog)
+		return false;
+
+	entry = bpf_dispatcher_find_prog(d, prog);
+	if (!entry)
+		return false;
+
+	if (refcount_dec_and_test(&entry->users)) {
+		entry->prog = NULL;
+		bpf_prog_put(prog);
+		d->num_progs--;
+		return true;
+	}
+	return false;
+}
+
+int __weak arch_prepare_bpf_dispatcher(void *image, s64 *funcs, int num_funcs)
+{
+	return -ENOTSUPP;
+}
+
+static int bpf_dispatcher_prepare(struct bpf_dispatcher *d, void *image)
+{
+	s64 ips[BPF_DISPATCHER_MAX] = {}, *ipsp = &ips[0];
+	int i;
+
+	for (i = 0; i < BPF_DISPATCHER_MAX; i++) {
+		if (d->progs[i].prog)
+			*ipsp++ = (s64)(uintptr_t)d->progs[i].prog->bpf_func;
+	}
+	return arch_prepare_bpf_dispatcher(image, &ips[0], d->num_progs);
+}
+
+static void bpf_dispatcher_update(struct bpf_dispatcher *d, int prev_num_progs)
+{
+	void *old, *new;
+	u32 noff;
+	int err;
+
+	if (!prev_num_progs) {
+		old = NULL;
+		noff = 0;
+	} else {
+		old = d->image + d->image_off;
+		noff = d->image_off ^ (PAGE_SIZE / 2);
+	}
+
+	new = d->num_progs ? d->image + noff : NULL;
+	if (new) {
+		if (bpf_dispatcher_prepare(d, new))
+			return;
+	}
+
+	err = bpf_arch_text_poke(d->func, BPF_MOD_JUMP, old, new);
+	if (err || !new)
+		return;
+
+	d->image_off = noff;
+}
+
+void bpf_dispatcher_change_prog(struct bpf_dispatcher *d, struct bpf_prog *from,
+				struct bpf_prog *to)
+{
+	bool changed = false;
+	int prev_num_progs;
+
+	if (from == to)
+		return;
+
+	mutex_lock(&d->mutex);
+	if (!d->image) {
+		d->image = bpf_jit_alloc_exec_page();
+		if (!d->image)
+			goto out;
+	}
+
+	prev_num_progs = d->num_progs;
+	changed |= bpf_dispatcher_remove_prog(d, from);
+	changed |= bpf_dispatcher_add_prog(d, to);
+
+	if (!changed)
+		goto out;
+
+	bpf_dispatcher_update(d, prev_num_progs);
+out:
+	mutex_unlock(&d->mutex);
+}
-- 
2.20.1

[PATCH bpf-next v4 3/6] bpf, xdp: start using the BPF dispatcher for XDP

[Björn Töpel]

From: Björn Töpel <bjorn.topel@intel.com>

This commit adds a BPF dispatcher for XDP. The dispatcher is updated
from the XDP control-path, dev_xdp_install(), and used when an XDP
program is run via bpf_prog_run_xdp().

Signed-off-by: Björn Töpel <bjorn.topel@intel.com>
---
 include/linux/bpf.h    | 15 +++++++++++++++
 include/linux/filter.h | 40 ++++++++++++++++++++++++----------------
 kernel/bpf/syscall.c   | 26 ++++++++++++++++++--------
 net/core/dev.c         | 19 ++++++++++++++++++-
 net/core/filter.c      |  8 ++++++++
 5 files changed, 83 insertions(+), 25 deletions(-)

diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index e6a9d74d4e30..ed32b5d901a1 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -488,6 +488,14 @@ struct bpf_dispatcher {
 	u32 image_off;
 };
 
+static __always_inline unsigned int bpf_dispatcher_nopfunc(
+	const void *ctx,
+	const struct bpf_insn *insnsi,
+	unsigned int (*bpf_func)(const void *,
+				 const struct bpf_insn *))
+{
+	return bpf_func(ctx, insnsi);
+}
 #ifdef CONFIG_BPF_JIT
 struct bpf_trampoline *bpf_trampoline_lookup(u64 key);
 int bpf_trampoline_link_prog(struct bpf_prog *prog);
@@ -997,6 +1005,8 @@ int btf_distill_func_proto(struct bpf_verifier_log *log,
 
 int btf_check_func_arg_match(struct bpf_verifier_env *env, int subprog);
 
+struct bpf_prog *bpf_prog_by_id(u32 id);
+
 #else /* !CONFIG_BPF_SYSCALL */
 static inline struct bpf_prog *bpf_prog_get(u32 ufd)
 {
@@ -1128,6 +1138,11 @@ static inline int bpf_prog_test_run_flow_dissector(struct bpf_prog *prog,
 static inline void bpf_map_put(struct bpf_map *map)
 {
 }
+
+static inline struct bpf_prog *bpf_prog_by_id(u32 id)
+{
+	return ERR_PTR(-ENOTSUPP);
+}
 #endif /* CONFIG_BPF_SYSCALL */
 
 static inline struct bpf_prog *bpf_prog_get_type(u32 ufd,
diff --git a/include/linux/filter.h b/include/linux/filter.h
index a141cb07e76a..37ac7025031d 100644
--- a/include/linux/filter.h
+++ b/include/linux/filter.h
@@ -559,23 +559,26 @@ struct sk_filter {
 
 DECLARE_STATIC_KEY_FALSE(bpf_stats_enabled_key);
 
-#define BPF_PROG_RUN(prog, ctx)	({				\
-	u32 ret;						\
-	cant_sleep();						\
-	if (static_branch_unlikely(&bpf_stats_enabled_key)) {	\
-		struct bpf_prog_stats *stats;			\
-		u64 start = sched_clock();			\
-		ret = (*(prog)->bpf_func)(ctx, (prog)->insnsi);	\
-		stats = this_cpu_ptr(prog->aux->stats);		\
-		u64_stats_update_begin(&stats->syncp);		\
-		stats->cnt++;					\
-		stats->nsecs += sched_clock() - start;		\
-		u64_stats_update_end(&stats->syncp);		\
-	} else {						\
-		ret = (*(prog)->bpf_func)(ctx, (prog)->insnsi);	\
-	}							\
+#define __BPF_PROG_RUN(prog, ctx, dfunc)	({			\
+	u32 ret;							\
+	cant_sleep();							\
+	if (static_branch_unlikely(&bpf_stats_enabled_key)) {		\
+		struct bpf_prog_stats *stats;				\
+		u64 start = sched_clock();				\
+		ret = dfunc(ctx, (prog)->insnsi, (prog)->bpf_func);	\
+		stats = this_cpu_ptr(prog->aux->stats);			\
+		u64_stats_update_begin(&stats->syncp);			\
+		stats->cnt++;						\
+		stats->nsecs += sched_clock() - start;			\
+		u64_stats_update_end(&stats->syncp);			\
+	} else {							\
+		ret = dfunc(ctx, (prog)->insnsi, (prog)->bpf_func);	\
+	}								\
 	ret; })
 
+#define BPF_PROG_RUN(prog, ctx) __BPF_PROG_RUN(prog, ctx,		\
+					       bpf_dispatcher_nopfunc)
+
 #define BPF_SKB_CB_LEN QDISC_CB_PRIV_LEN
 
 struct bpf_skb_data_end {
@@ -699,6 +702,8 @@ static inline u32 bpf_prog_run_clear_cb(const struct bpf_prog *prog,
 	return res;
 }
 
+DECLARE_BPF_DISPATCHER(bpf_dispatcher_xdp)
+
 static __always_inline u32 bpf_prog_run_xdp(const struct bpf_prog *prog,
 					    struct xdp_buff *xdp)
 {
@@ -708,9 +713,12 @@ static __always_inline u32 bpf_prog_run_xdp(const struct bpf_prog *prog,
 	 * already takes rcu_read_lock() when fetching the program, so
 	 * it's not necessary here anymore.
 	 */
-	return BPF_PROG_RUN(prog, xdp);
+	return __BPF_PROG_RUN(prog, xdp,
+			      BPF_DISPATCHER_FUNC(bpf_dispatcher_xdp));
 }
 
+void bpf_prog_change_xdp(struct bpf_prog *prev_prog, struct bpf_prog *prog);
+
 static inline u32 bpf_prog_insn_size(const struct bpf_prog *prog)
 {
 	return prog->len * sizeof(struct bpf_insn);
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index e3461ec59570..1a67d468637b 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -2305,17 +2305,12 @@ static int bpf_obj_get_next_id(const union bpf_attr *attr,
 
 #define BPF_PROG_GET_FD_BY_ID_LAST_FIELD prog_id
 
-static int bpf_prog_get_fd_by_id(const union bpf_attr *attr)
+struct bpf_prog *bpf_prog_by_id(u32 id)
 {
 	struct bpf_prog *prog;
-	u32 id = attr->prog_id;
-	int fd;
-
-	if (CHECK_ATTR(BPF_PROG_GET_FD_BY_ID))
-		return -EINVAL;
 
-	if (!capable(CAP_SYS_ADMIN))
-		return -EPERM;
+	if (!id)
+		return ERR_PTR(-ENOENT);
 
 	spin_lock_bh(&prog_idr_lock);
 	prog = idr_find(&prog_idr, id);
@@ -2324,7 +2319,22 @@ static int bpf_prog_get_fd_by_id(const union bpf_attr *attr)
 	else
 		prog = ERR_PTR(-ENOENT);
 	spin_unlock_bh(&prog_idr_lock);
+	return prog;
+}
+
+static int bpf_prog_get_fd_by_id(const union bpf_attr *attr)
+{
+	struct bpf_prog *prog;
+	u32 id = attr->prog_id;
+	int fd;
+
+	if (CHECK_ATTR(BPF_PROG_GET_FD_BY_ID))
+		return -EINVAL;
+
+	if (!capable(CAP_SYS_ADMIN))
+		return -EPERM;
 
+	prog = bpf_prog_by_id(id);
 	if (IS_ERR(prog))
 		return PTR_ERR(prog);
 
diff --git a/net/core/dev.c b/net/core/dev.c
index 2c277b8aba38..255d3cf35360 100644
--- a/net/core/dev.c
+++ b/net/core/dev.c
@@ -8542,7 +8542,17 @@ static int dev_xdp_install(struct net_device *dev, bpf_op_t bpf_op,
 			   struct netlink_ext_ack *extack, u32 flags,
 			   struct bpf_prog *prog)
 {
+	bool non_hw = !(flags & XDP_FLAGS_HW_MODE);
+	struct bpf_prog *prev_prog = NULL;
 	struct netdev_bpf xdp;
+	int err;
+
+	if (non_hw) {
+		prev_prog = bpf_prog_by_id(__dev_xdp_query(dev, bpf_op,
+							   XDP_QUERY_PROG));
+		if (IS_ERR(prev_prog))
+			prev_prog = NULL;
+	}
 
 	memset(&xdp, 0, sizeof(xdp));
 	if (flags & XDP_FLAGS_HW_MODE)
@@ -8553,7 +8563,14 @@ static int dev_xdp_install(struct net_device *dev, bpf_op_t bpf_op,
 	xdp.flags = flags;
 	xdp.prog = prog;
 
-	return bpf_op(dev, &xdp);
+	err = bpf_op(dev, &xdp);
+	if (!err && non_hw)
+		bpf_prog_change_xdp(prev_prog, prog);
+
+	if (prev_prog)
+		bpf_prog_put(prev_prog);
+
+	return err;
 }
 
 static void dev_xdp_uninstall(struct net_device *dev)
diff --git a/net/core/filter.c b/net/core/filter.c
index f1e703eed3d2..a411f7835dee 100644
--- a/net/core/filter.c
+++ b/net/core/filter.c
@@ -8940,3 +8940,11 @@ const struct bpf_verifier_ops sk_reuseport_verifier_ops = {
 const struct bpf_prog_ops sk_reuseport_prog_ops = {
 };
 #endif /* CONFIG_INET */
+
+DEFINE_BPF_DISPATCHER(bpf_dispatcher_xdp)
+
+void bpf_prog_change_xdp(struct bpf_prog *prev_prog, struct bpf_prog *prog)
+{
+	bpf_dispatcher_change_prog(BPF_DISPATCHER_PTR(bpf_dispatcher_xdp),
+				   prev_prog, prog);
+}
-- 
2.20.1

[PATCH bpf-next v4 4/6] bpf: start using the BPF dispatcher in BPF_TEST_RUN

[Björn Töpel]

From: Björn Töpel <bjorn.topel@intel.com>

In order to properly exercise the BPF dispatcher, this commit adds BPF
dispatcher usage to BPF_TEST_RUN when executing XDP programs.

Signed-off-by: Björn Töpel <bjorn.topel@intel.com>
---
 net/bpf/test_run.c | 15 ++++++++++-----
 1 file changed, 10 insertions(+), 5 deletions(-)

diff --git a/net/bpf/test_run.c b/net/bpf/test_run.c
index 915c2d6f7fb9..400f473c2541 100644
--- a/net/bpf/test_run.c
+++ b/net/bpf/test_run.c
@@ -15,7 +15,7 @@
 #include <trace/events/bpf_test_run.h>
 
 static int bpf_test_run(struct bpf_prog *prog, void *ctx, u32 repeat,
-			u32 *retval, u32 *time)
+			u32 *retval, u32 *time, bool xdp)
 {
 	struct bpf_cgroup_storage *storage[MAX_BPF_CGROUP_STORAGE_TYPE] = { NULL };
 	enum bpf_cgroup_storage_type stype;
@@ -41,7 +41,11 @@ static int bpf_test_run(struct bpf_prog *prog, void *ctx, u32 repeat,
 	time_start = ktime_get_ns();
 	for (i = 0; i < repeat; i++) {
 		bpf_cgroup_storage_set(storage);
-		*retval = BPF_PROG_RUN(prog, ctx);
+
+		if (xdp)
+			*retval = bpf_prog_run_xdp(prog, ctx);
+		else
+			*retval = BPF_PROG_RUN(prog, ctx);
 
 		if (signal_pending(current)) {
 			ret = -EINTR;
@@ -359,7 +363,7 @@ int bpf_prog_test_run_skb(struct bpf_prog *prog, const union bpf_attr *kattr,
 	ret = convert___skb_to_skb(skb, ctx);
 	if (ret)
 		goto out;
-	ret = bpf_test_run(prog, skb, repeat, &retval, &duration);
+	ret = bpf_test_run(prog, skb, repeat, &retval, &duration, false);
 	if (ret)
 		goto out;
 	if (!is_l2) {
@@ -416,8 +420,8 @@ int bpf_prog_test_run_xdp(struct bpf_prog *prog, const union bpf_attr *kattr,
 
 	rxqueue = __netif_get_rx_queue(current->nsproxy->net_ns->loopback_dev, 0);
 	xdp.rxq = &rxqueue->xdp_rxq;
-
-	ret = bpf_test_run(prog, &xdp, repeat, &retval, &duration);
+	bpf_prog_change_xdp(NULL, prog);
+	ret = bpf_test_run(prog, &xdp, repeat, &retval, &duration, true);
 	if (ret)
 		goto out;
 	if (xdp.data != data + XDP_PACKET_HEADROOM + NET_IP_ALIGN ||
@@ -425,6 +429,7 @@ int bpf_prog_test_run_xdp(struct bpf_prog *prog, const union bpf_attr *kattr,
 		size = xdp.data_end - xdp.data;
 	ret = bpf_test_finish(kattr, uattr, xdp.data, size, retval, duration);
 out:
+	bpf_prog_change_xdp(prog, NULL);
 	kfree(data);
 	return ret;
 }
-- 
2.20.1

[PATCH bpf-next v4 5/6] selftests: bpf: add xdp_perf test

[Björn Töpel]

From: Björn Töpel <bjorn.topel@intel.com>

The xdp_perf is a dummy XDP test, only used to measure the the cost of
jumping into a naive XDP program one million times.

To build and run the program:
  $ cd tools/testing/selftests/bpf
  $ make
  $ ./test_progs -v -t xdp_perf

Signed-off-by: Björn Töpel <bjorn.topel@intel.com>
---
 .../selftests/bpf/prog_tests/xdp_perf.c       | 25 +++++++++++++++++++
 1 file changed, 25 insertions(+)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/xdp_perf.c

diff --git a/tools/testing/selftests/bpf/prog_tests/xdp_perf.c b/tools/testing/selftests/bpf/prog_tests/xdp_perf.c
new file mode 100644
index 000000000000..7185bee16fe4
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/xdp_perf.c
@@ -0,0 +1,25 @@
+// SPDX-License-Identifier: GPL-2.0
+#include <test_progs.h>
+
+void test_xdp_perf(void)
+{
+	const char *file = "./xdp_dummy.o";
+	__u32 duration, retval, size;
+	struct bpf_object *obj;
+	char in[128], out[128];
+	int err, prog_fd;
+
+	err = bpf_prog_load(file, BPF_PROG_TYPE_XDP, &obj, &prog_fd);
+	if (CHECK_FAIL(err))
+		return;
+
+	err = bpf_prog_test_run(prog_fd, 1000000, &in[0], 128,
+				out, &size, &retval, &duration);
+
+	CHECK(err || retval != XDP_PASS || size != 128,
+	      "xdp-perf",
+	      "err %d errno %d retval %d size %d\n",
+	      err, errno, retval, size);
+
+	bpf_object__close(obj);
+}
-- 
2.20.1

[PATCH bpf-next v4 6/6] bpf, x86: align dispatcher branch targets to 16B

[Björn Töpel]

From: Björn Töpel <bjorn.topel@intel.com>

From Intel 64 and IA-32 Architectures Optimization Reference Manual,
3.4.1.4 Code Alignment, Assembly/Compiler Coding Rule 11: All branch
targets should be 16-byte aligned.

This commits aligns branch targets according to the Intel manual.

The nops used to align branch targets make the dispatcher larger, and
therefore the number of supported dispatch points/programs are
descreased from 64 to 48.

Signed-off-by: Björn Töpel <bjorn.topel@intel.com>
---
 arch/x86/net/bpf_jit_comp.c | 30 +++++++++++++++++++++++++++++-
 include/linux/bpf.h         |  2 +-
 2 files changed, 30 insertions(+), 2 deletions(-)

diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
index 3ce7ad41bd6f..4c8a2d1f8470 100644
--- a/arch/x86/net/bpf_jit_comp.c
+++ b/arch/x86/net/bpf_jit_comp.c
@@ -1548,6 +1548,26 @@ static int emit_cond_near_jump(u8 **pprog, void *func, void *ip, u8 jmp_cond)
 	return 0;
 }
 
+static void emit_nops(u8 **pprog, unsigned int len)
+{
+	unsigned int i, noplen;
+	u8 *prog = *pprog;
+	int cnt = 0;
+
+	while (len > 0) {
+		noplen = len;
+
+		if (noplen > ASM_NOP_MAX)
+			noplen = ASM_NOP_MAX;
+
+		for (i = 0; i < noplen; i++)
+			EMIT1(ideal_nops[noplen][i]);
+		len -= noplen;
+	}
+
+	*pprog = prog;
+}
+
 static int emit_fallback_jump(u8 **pprog)
 {
 	u8 *prog = *pprog;
@@ -1570,8 +1590,8 @@ static int emit_fallback_jump(u8 **pprog)
 
 static int emit_bpf_dispatcher(u8 **pprog, int a, int b, s64 *progs)
 {
+	u8 *jg_reloc, *jg_target, *prog = *pprog;
 	int pivot, err, jg_bytes = 1, cnt = 0;
-	u8 *jg_reloc, *prog = *pprog;
 	s64 jg_offset;
 
 	if (a == b) {
@@ -1620,6 +1640,14 @@ static int emit_bpf_dispatcher(u8 **pprog, int a, int b, s64 *progs)
 	if (err)
 		return err;
 
+	/* From Intel 64 and IA-32 Architectures Optimization
+	 * Reference Manual, 3.4.1.4 Code Alignment, Assembly/Compiler
+	 * Coding Rule 11: All branch targets should be 16-byte
+	 * aligned.
+	 */
+	jg_target = PTR_ALIGN(prog, 16);
+	if (jg_target != prog)
+		emit_nops(&prog, jg_target - prog);
 	jg_offset = prog - jg_reloc;
 	emit_code(jg_reloc - jg_bytes, jg_offset, jg_bytes);
 
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index ed32b5d901a1..026892e55ca2 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -471,7 +471,7 @@ struct bpf_trampoline {
 	u64 selector;
 };
 
-#define BPF_DISPATCHER_MAX 64 /* Fits in 2048B */
+#define BPF_DISPATCHER_MAX 48 /* Fits in 2048B */
 
 struct bpf_dispatcher_prog {
 	struct bpf_prog *prog;
-- 
2.20.1

Re: [PATCH bpf-next v4 0/6] Introduce the BPF dispatcher

[Björn Töpel]

On Wed, 11 Dec 2019 at 13:30, Björn Töpel <bjorn.topel@gmail.com> wrote:
>
[...]
>
> xdp-perf runs, aliged vs non-aligned jump targets
> -------------------------------------------------
>
> In this test dispatchers of different sizes, with and without jump
> target alignment, were exercised. As outlined above the function
> lookup is performed via binary search. This means that depending on
> the pointer value of the function, it can reside in the upper or lower
> part of the search table. The performed tests were:
>
> 1. aligned, mititations=auto, function entry < other entries
> 2. aligned, mititations=auto, function entry > other entries
> 3. non-aligned, mititations=auto, function entry < other entries
> 4. non-aligned, mititations=auto, function entry > other entries
> 5. aligned, mititations=off, function entry < other entries
> 6. aligned, mititations=off, function entry > other entries
> 7. non-aligned, mititations=off, function entry < other entries
> 8. non-aligned, mititations=off, function entry > other entries
>
> The micro benchmarks showed that alignment of jump target has some
> positive impact.
>
> A reply to this cover letter will contain complete data for all runs.
>

Please find all the output of "xdp-perf runs, aliged vs non-aligned
jump targets" below.

To see the alignment impact, compare
align_opneg_auto.txt/nonalign_opneg_auto.txt and
align_opneg_auto.txt/nonalign_opneg_auto.txt.


Björn

align_op1_auto.txt
# aligned jump targets, mitigations=auto, prog->bpf_func < other entries
# column 1: number entries in dispatcher
# column 2: size of dispatcher
# column 3: runtime average 1000000 XDP calls (xdp_perf)
1 18 4
2 50 4
3 98 5
4 130 4
5 162 4
6 210 4
7 258 4
8 290 4
9 322 4
10 354 4
11 402 4
12 450 5
13 482 4
14 530 4
15 562 4
16 594 4
17 642 4
18 674 4
19 706 5
20 738 4
21 786 4
22 834 4
23 882 4
24 930 4
25 962 4
26 994 4
27 1042 4
28 1090 4
29 1122 4
30 1154 4
31 1186 4
32 1218 4
33 1266 5
34 1314 5
35 1346 5
36 1378 5
37 1410 5
38 1442 5
39 1474 5
40 1506 5
41 1554 5
42 1602 5
43 1650 5
44 1698 5
45 1746 5
46 1794 5
47 1842 5
48 1890 5
49 1890 17
align_op1_off.txt
# aligned jump targets, mitigations=off, prog->bpf_func < other entries
# column 1: number entries in dispatcher
# column 2: size of dispatcher
# column 3: runtime average 1000000 XDP calls (xdp_perf)
1 18 4
2 50 4
3 98 4
4 130 4
5 162 4
6 210 4
7 258 4
8 290 4
9 322 4
10 354 4
11 402 4
12 450 4
13 482 4
14 530 4
15 562 4
16 594 4
17 642 4
18 674 4
19 706 4
20 738 4
21 786 4
22 834 4
23 882 4
24 930 4
25 962 4
26 994 4
27 1042 5
28 1090 4
29 1122 4
30 1154 4
31 1186 4
32 1218 4
33 1266 5
34 1314 5
35 1346 5
36 1378 5
37 1410 5
38 1442 5
39 1474 5
40 1506 5
41 1554 5
42 1602 5
43 1650 5
44 1698 5
45 1746 5
46 1794 5
47 1842 5
48 1890 5
49 1890 5
align_opneg_auto.txt
# aligned jump targets, mitigations=auto, prog->bpf_func > other entries
# column 1: number entries in dispatcher
# column 2: size of dispatcher
# column 3: runtime average 1000000 XDP calls (xdp_perf)
1 18 4
2 50 4
3 98 4
4 130 4
5 162 4
6 210 4
7 258 4
8 290 5
9 322 5
10 354 5
11 402 5
12 450 5
13 482 5
14 530 5
15 562 5
16 594 5
17 642 5
18 674 5
19 706 5
20 738 5
21 786 5
22 834 5
23 882 5
24 930 5
25 962 5
26 994 5
27 1042 5
28 1090 5
29 1122 5
30 1154 5
31 1186 5
32 1218 5
33 1266 5
34 1314 5
35 1346 5
36 1378 5
37 1410 6
38 1442 5
39 1474 5
40 1506 5
41 1554 5
42 1602 5
43 1650 5
44 1698 5
45 1746 6
46 1794 5
47 1842 5
48 1890 5
49 1890 17
align_opneg_off.txt
# aligned jump targets, mitigations=off, prog->bpf_func > other entries
# column 1: number entries in dispatcher
# column 2: size of dispatcher
# column 3: runtime average 1000000 XDP calls (xdp_perf)
1 18 4
2 50 4
3 98 4
4 130 4
5 162 4
6 210 4
7 258 4
8 290 5
9 322 5
10 354 5
11 402 5
12 450 5
13 482 5
14 530 5
15 562 5
16 594 5
17 642 5
18 674 5
19 706 5
20 738 5
21 786 5
22 834 5
23 882 5
24 930 5
25 962 5
26 994 5
27 1042 5
28 1090 5
29 1122 5
30 1154 5
31 1186 5
32 1218 5
33 1266 5
34 1314 5
35 1346 5
36 1378 5
37 1410 5
38 1442 5
39 1474 5
40 1506 5
41 1554 5
42 1602 5
43 1650 5
44 1698 5
45 1746 5
46 1794 5
47 1842 5
48 1890 5
49 1890 5
mail.txt
align_op1_auto.txt
# aligned jump targets, mitigations=auto, prog->bpf_func < other entries
# column 1: number entries in dispatcher
# column 2: size of dispatcher
# column 3: runtime average 1000000 XDP calls (xdp_perf)
1 18 4
2 50 4
3 98 5
4 130 4
5 162 4
6 210 4
7 258 4
8 290 4
9 322 4
10 354 4
11 402 4
12 450 5
13 482 4
14 530 4
15 562 4
16 594 4
17 642 4
18 674 4
19 706 5
20 738 4
21 786 4
22 834 4
23 882 4
24 930 4
25 962 4
26 994 4
27 1042 4
28 1090 4
29 1122 4
30 1154 4
31 1186 4
32 1218 4
33 1266 5
34 1314 5
35 1346 5
36 1378 5
37 1410 5
38 1442 5
39 1474 5
40 1506 5
41 1554 5
42 1602 5
43 1650 5
44 1698 5
45 1746 5
46 1794 5
47 1842 5
48 1890 5
49 1890 17
align_op1_off.txt
# aligned jump targets, mitigations=off, prog->bpf_func < other entries
# column 1: number entries in dispatcher
# column 2: size of dispatcher
# column 3: runtime average 1000000 XDP calls (xdp_perf)
1 18 4
2 50 4
3 98 4
4 130 4
5 162 4
6 210 4
7 258 4
8 290 4
9 322 4
10 354 4
11 402 4
12 450 4
13 482 4
14 530 4
15 562 4
16 594 4
17 642 4
18 674 4
19 706 4
20 738 4
21 786 4
22 834 4
23 882 4
24 930 4
25 962 4
26 994 4
27 1042 5
28 1090 4
29 1122 4
30 1154 4
31 1186 4
32 1218 4
33 1266 5
34 1314 5
35 1346 5
36 1378 5
37 1410 5
38 1442 5
39 1474 5
40 1506 5
41 1554 5
42 1602 5
43 1650 5
44 1698 5
45 1746 5
46 1794 5
47 1842 5
48 1890 5
49 1890 5
align_opneg_auto.txt
# aligned jump targets, mitigations=auto, prog->bpf_func > other entries
# column 1: number entries in dispatcher
# column 2: size of dispatcher
# column 3: runtime average 1000000 XDP calls (xdp_perf)
1 18 4
2 50 4
3 98 4
4 130 4
5 162 4
6 210 4
7 258 4
8 290 5
9 322 5
10 354 5
11 402 5
12 450 5
13 482 5
14 530 5
15 562 5
16 594 5
17 642 5
18 674 5
19 706 5
20 738 5
21 786 5
22 834 5
23 882 5
24 930 5
25 962 5
26 994 5
27 1042 5
28 1090 5
29 1122 5
30 1154 5
31 1186 5
32 1218 5
33 1266 5
34 1314 5
35 1346 5
36 1378 5
37 1410 6
38 1442 5
39 1474 5
40 1506 5
41 1554 5
42 1602 5
43 1650 5
44 1698 5
45 1746 6
46 1794 5
47 1842 5
48 1890 5
49 1890 17
align_opneg_off.txt
# aligned jump targets, mitigations=off, prog->bpf_func > other entries
# column 1: number entries in dispatcher
# column 2: size of dispatcher
# column 3: runtime average 1000000 XDP calls (xdp_perf)
1 18 4
2 50 4
3 98 4
4 130 4
5 162 4
6 210 4
7 258 4
8 290 5
9 322 5
10 354 5
11 402 5
12 450 5
13 482 5
14 530 5
15 562 5
16 594 5
17 642 5
18 674 5
19 706 5
20 738 5
21 786 5
22 834 5
23 882 5
24 930 5
25 962 5
26 994 5
27 1042 5
28 1090 5
29 1122 5
30 1154 5
31 1186 5
32 1218 5
33 1266 5
34 1314 5
35 1346 5
36 1378 5
37 1410 5
38 1442 5
39 1474 5
40 1506 5
41 1554 5
42 1602 5
43 1650 5
44 1698 5
45 1746 5
46 1794 5
47 1842 5
48 1890 5
49 1890 5
mail.txt
nonalign_op1_auto.txt
# non-aligned jump targets, mitigations=auto, prog->bpf_func < other entries
# column 1: number entries in dispatcher
# column 2: size of dispatcher
# column 3: runtime average 1000000 XDP calls (xdp_perf)
1 18 4
2 45 4
3 72 4
4 99 4
5 126 4
6 153 4
7 184 4
8 211 4
9 238 4
10 265 4
11 292 4
12 319 4
13 350 4
14 381 4
15 408 4
16 435 4
17 462 4
18 489 4
19 516 4
20 543 4
21 570 4
22 597 4
23 624 4
24 651 4
25 682 5
26 713 4
27 744 4
28 775 4
29 802 4
30 829 4
31 856 4
32 883 4
33 910 5
34 937 5
35 964 5
36 991 5
37 1018 5
38 1045 5
39 1072 5
40 1099 5
41 1126 5
42 1153 5
43 1180 5
44 1207 5
45 1234 5
46 1261 5
47 1288 5
48 1315 5
49 1346 5
50 1377 5
51 1408 5
52 1439 5
53 1470 5
54 1501 5
55 1532 5
56 1563 5
57 1590 5
58 1617 5
59 1644 5
60 1671 5
61 1698 5
62 1725 5
63 1752 5
64 1779 5
65 1779 17
nonalign_op1_off.txt
# non-aligned jump targets, mitigations=off, prog->bpf_func < other entries
# column 1: number entries in dispatcher
# column 2: size of dispatcher
# column 3: runtime average 1000000 XDP calls (xdp_perf)
1 18 4
2 45 4
3 72 4
4 99 4
5 126 4
6 153 4
7 184 4
8 211 4
9 238 4
10 265 4
11 292 4
12 319 4
13 350 4
14 381 4
15 408 4
16 435 4
17 462 4
18 489 4
19 516 4
20 543 4
21 570 5
22 597 5
23 624 4
24 651 4
25 682 4
26 713 4
27 744 5
28 775 4
29 802 4
30 829 4
31 856 4
32 883 4
33 910 5
34 937 5
35 964 5
36 991 5
37 1018 5
38 1045 5
39 1072 5
40 1099 5
41 1126 5
42 1153 5
43 1180 5
44 1207 5
45 1234 5
46 1261 5
47 1288 5
48 1315 5
49 1346 5
50 1377 5
51 1408 5
52 1439 5
53 1470 5
54 1501 5
55 1532 5
56 1563 5
57 1590 5
58 1617 5
59 1644 5
60 1671 5
61 1698 5
62 1725 5
63 1752 5
64 1779 5
65 1779 5
nonalign_opneg_auto.txt
# non-aligned jump targets, mitigations=auto, prog->bpf_func > other entries
# column 1: number entries in dispatcher
# column 2: size of dispatcher
# column 3: runtime average 1000000 XDP calls (xdp_perf)
1 18 4
2 45 4
3 72 4
4 99 4
5 126 4
6 153 4
7 184 5
8 211 5
9 238 5
10 265 5
11 292 5
12 319 5
13 350 5
14 381 5
15 408 5
16 435 5
17 462 6
18 489 6
19 516 6
20 543 6
21 570 5
22 597 5
23 624 6
24 651 5
25 682 5
26 713 5
27 744 5
28 775 6
29 802 5
30 829 5
31 856 5
32 883 5
33 910 6
34 937 6
35 964 6
36 991 7
37 1018 5
38 1045 5
39 1072 6
40 1099 6
41 1126 6
42 1153 6
43 1180 6
44 1207 5
45 1234 5
46 1261 6
47 1288 6
48 1315 6
49 1346 6
50 1377 7
51 1408 6
52 1439 6
53 1470 6
54 1501 6
55 1532 5
56 1563 5
57 1590 6
58 1617 6
59 1644 6
60 1671 6
61 1698 6
62 1725 5
63 1752 5
64 1779 6
65 1779 17
nonalign_opneg_off.txt
# non-aligned jump targets, mitigations=off, prog->bpf_func > other entries
# column 1: number entries in dispatcher
# column 2: size of dispatcher
# column 3: runtime average 1000000 XDP calls (xdp_perf)
1 18 4
2 45 4
3 72 4
4 99 4
5 126 4
6 153 4
7 184 4
8 211 5
9 238 5
10 265 5
11 292 5
12 319 5
13 350 5
14 381 5
15 408 5
16 435 5
17 462 6
18 489 6
19 516 6
20 543 6
21 570 6
22 597 6
23 624 5
24 651 5
25 682 5
26 713 5
27 744 6
28 775 6
29 802 5
30 829 5
31 856 5
32 883 5
33 910 6
34 937 6
35 964 6
36 991 6
37 1018 5
38 1045 5
39 1072 6
40 1099 6
41 1126 6
42 1153 5
43 1180 6
44 1207 5
45 1234 5
46 1261 7
47 1288 6
48 1315 6
49 1346 6
50 1377 7
51 1408 7
52 1439 6
53 1470 6
54 1501 6
55 1532 6
56 1563 5
57 1590 6
58 1617 6
59 1644 6
60 1671 6
61 1698 5
62 1725 5
63 1752 5
64 1779 6
65 1779 6
nonalign_op1_auto.txt
# non-aligned jump targets, mitigations=auto, prog->bpf_func < other entries
# column 1: number entries in dispatcher
# column 2: size of dispatcher
# column 3: runtime average 1000000 XDP calls (xdp_perf)
1 18 4
2 45 4
3 72 4
4 99 4
5 126 4
6 153 4
7 184 4
8 211 4
9 238 4
10 265 4
11 292 4
12 319 4
13 350 4
14 381 4
15 408 4
16 435 4
17 462 4
18 489 4
19 516 4
20 543 4
21 570 4
22 597 4
23 624 4
24 651 4
25 682 5
26 713 4
27 744 4
28 775 4
29 802 4
30 829 4
31 856 4
32 883 4
33 910 5
34 937 5
35 964 5
36 991 5
37 1018 5
38 1045 5
39 1072 5
40 1099 5
41 1126 5
42 1153 5
43 1180 5
44 1207 5
45 1234 5
46 1261 5
47 1288 5
48 1315 5
49 1346 5
50 1377 5
51 1408 5
52 1439 5
53 1470 5
54 1501 5
55 1532 5
56 1563 5
57 1590 5
58 1617 5
59 1644 5
60 1671 5
61 1698 5
62 1725 5
63 1752 5
64 1779 5
65 1779 17
nonalign_op1_off.txt
# non-aligned jump targets, mitigations=off, prog->bpf_func < other entries
# column 1: number entries in dispatcher
# column 2: size of dispatcher
# column 3: runtime average 1000000 XDP calls (xdp_perf)
1 18 4
2 45 4
3 72 4
4 99 4
5 126 4
6 153 4
7 184 4
8 211 4
9 238 4
10 265 4
11 292 4
12 319 4
13 350 4
14 381 4
15 408 4
16 435 4
17 462 4
18 489 4
19 516 4
20 543 4
21 570 5
22 597 5
23 624 4
24 651 4
25 682 4
26 713 4
27 744 5
28 775 4
29 802 4
30 829 4
31 856 4
32 883 4
33 910 5
34 937 5
35 964 5
36 991 5
37 1018 5
38 1045 5
39 1072 5
40 1099 5
41 1126 5
42 1153 5
43 1180 5
44 1207 5
45 1234 5
46 1261 5
47 1288 5
48 1315 5
49 1346 5
50 1377 5
51 1408 5
52 1439 5
53 1470 5
54 1501 5
55 1532 5
56 1563 5
57 1590 5
58 1617 5
59 1644 5
60 1671 5
61 1698 5
62 1725 5
63 1752 5
64 1779 5
65 1779 5
nonalign_opneg_auto.txt
# non-aligned jump targets, mitigations=auto, prog->bpf_func > other entries
# column 1: number entries in dispatcher
# column 2: size of dispatcher
# column 3: runtime average 1000000 XDP calls (xdp_perf)
1 18 4
2 45 4
3 72 4
4 99 4
5 126 4
6 153 4
7 184 5
8 211 5
9 238 5
10 265 5
11 292 5
12 319 5
13 350 5
14 381 5
15 408 5
16 435 5
17 462 6
18 489 6
19 516 6
20 543 6
21 570 5
22 597 5
23 624 6
24 651 5
25 682 5
26 713 5
27 744 5
28 775 6
29 802 5
30 829 5
31 856 5
32 883 5
33 910 6
34 937 6
35 964 6
36 991 7
37 1018 5
38 1045 5
39 1072 6
40 1099 6
41 1126 6
42 1153 6
43 1180 6
44 1207 5
45 1234 5
46 1261 6
47 1288 6
48 1315 6
49 1346 6
50 1377 7
51 1408 6
52 1439 6
53 1470 6
54 1501 6
55 1532 5
56 1563 5
57 1590 6
58 1617 6
59 1644 6
60 1671 6
61 1698 6
62 1725 5
63 1752 5
64 1779 6
65 1779 17
nonalign_opneg_off.txt
# non-aligned jump targets, mitigations=off, prog->bpf_func > other entries
# column 1: number entries in dispatcher
# column 2: size of dispatcher
# column 3: runtime average 1000000 XDP calls (xdp_perf)
1 18 4
2 45 4
3 72 4
4 99 4
5 126 4
6 153 4
7 184 4
8 211 5
9 238 5
10 265 5
11 292 5
12 319 5
13 350 5
14 381 5
15 408 5
16 435 5
17 462 6
18 489 6
19 516 6
20 543 6
21 570 6
22 597 6
23 624 5
24 651 5
25 682 5
26 713 5
27 744 6
28 775 6
29 802 5
30 829 5
31 856 5
32 883 5
33 910 6
34 937 6
35 964 6
36 991 6
37 1018 5
38 1045 5
39 1072 6
40 1099 6
41 1126 6
42 1153 5
43 1180 6
44 1207 5
45 1234 5
46 1261 7
47 1288 6
48 1315 6
49 1346 6
50 1377 7
51 1408 7
52 1439 6
53 1470 6
54 1501 6
55 1532 6
56 1563 5
57 1590 6
58 1617 6
59 1644 6
60 1671 6
61 1698 5
62 1725 5
63 1752 5
64 1779 6
65 1779 6

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Toke Høiland-Jørgensen]

[...]
> +/* The BPF dispatcher is a multiway branch code generator. The
> + * dispatcher is a mechanism to avoid the performance penalty of an
> + * indirect call, which is expensive when retpolines are enabled. A
> + * dispatch client registers a BPF program into the dispatcher, and if
> + * there is available room in the dispatcher a direct call to the BPF
> + * program will be generated. All calls to the BPF programs called via
> + * the dispatcher will then be a direct call, instead of an
> + * indirect. The dispatcher hijacks a trampoline function it via the
> + * __fentry__ of the trampoline. The trampoline function has the
> + * following signature:
> + *
> + * unsigned int trampoline(const void *xdp_ctx,
> + *                         const struct bpf_insn *insnsi,
> + *                         unsigned int (*bpf_func)(const void *,
> + *                                                  const struct bpf_insn *));
> + */

Nit: s/xdp_ctx/ctx/

-Toke

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Alexei Starovoitov]

On Wed, Dec 11, 2019 at 01:30:13PM +0100, Björn Töpel wrote:
> +
> +#define DEFINE_BPF_DISPATCHER(name)					\
> +	unsigned int name##func(					\
> +		const void *xdp_ctx,					\
> +		const struct bpf_insn *insnsi,				\
> +		unsigned int (*bpf_func)(const void *,			\
> +					 const struct bpf_insn *))	\
> +	{								\
> +		return bpf_func(xdp_ctx, insnsi);			\
> +	}								\
> +	EXPORT_SYMBOL(name##func);			\
> +	struct bpf_dispatcher name = BPF_DISPATCHER_INIT(name);

The dispatcher function is a normal function. EXPORT_SYMBOL doesn't make it
'noinline'. struct bpf_dispatcher takes a pointer to it and that address is
used for text_poke.

In patch 3 __BPF_PROG_RUN calls dfunc() from two places.
What stops compiler from inlining it? Or partially inlining it in one
or the other place?

I guess it works, because your compiler didn't inline it?
Could you share how asm looks for bpf_prog_run_xdp()
(where __BPF_PROG_RUN is called) and asm for name##func() ?

I hope my guess that compiler didn't inline it is correct. Then extra noinline
will not hurt and that's the only thing needed to avoid the issue.

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Björn Töpel]

On Fri, 13 Dec 2019 at 06:30, Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Wed, Dec 11, 2019 at 01:30:13PM +0100, Björn Töpel wrote:
> > +
> > +#define DEFINE_BPF_DISPATCHER(name)                                  \
> > +     unsigned int name##func(                                        \
> > +             const void *xdp_ctx,                                    \
> > +             const struct bpf_insn *insnsi,                          \
> > +             unsigned int (*bpf_func)(const void *,                  \
> > +                                      const struct bpf_insn *))      \
> > +     {                                                               \
> > +             return bpf_func(xdp_ctx, insnsi);                       \
> > +     }                                                               \
> > +     EXPORT_SYMBOL(name##func);                      \
> > +     struct bpf_dispatcher name = BPF_DISPATCHER_INIT(name);
>
> The dispatcher function is a normal function. EXPORT_SYMBOL doesn't make it
> 'noinline'. struct bpf_dispatcher takes a pointer to it and that address is
> used for text_poke.
>
> In patch 3 __BPF_PROG_RUN calls dfunc() from two places.
> What stops compiler from inlining it? Or partially inlining it in one
> or the other place?
>

Good catch. No inlining for the XDP dispatcher is possible, since the
trampoline function is in a different compilation unit (filter.o),
than the users of bpf_prog_run_xdp(). Turning on LTO, this would no
longer be true. So, *not* having it marked as noinline is a bug.

> I guess it works, because your compiler didn't inline it?
> Could you share how asm looks for bpf_prog_run_xdp()
> (where __BPF_PROG_RUN is called) and asm for name##func() ?
>

Sure! bpf_prog_run_xdp() is always inlined, so let's look at:
net/bpf/test_run.c:bpf_test_run:

        if (xdp)
            *retval = bpf_prog_run_xdp(prog, ctx);
        else
            *retval = BPF_PROG_RUN(prog, ctx);

translates to:

   0xffffffff8199f522 <+162>:   nopl   0x0(%rax,%rax,1)
./include/linux/filter.h:
716             return __BPF_PROG_RUN(prog, xdp,
   0xffffffff8199f527 <+167>:   mov    0x30(%rbp),%rdx
   0xffffffff8199f52b <+171>:   mov    %r14,%rsi
   0xffffffff8199f52e <+174>:   mov    %r13,%rdi
   0xffffffff8199f531 <+177>:   callq  0xffffffff819586d0
<bpf_dispatcher_xdpfunc>
   0xffffffff8199f536 <+182>:   mov    %eax,%ecx

net/bpf/test_run.c:
48                              *retval = BPF_PROG_RUN(prog, ctx);
   0xffffffff8199f538 <+184>:   mov    (%rsp),%rax
   0xffffffff8199f53c <+188>:   mov    %ecx,(%rax)
...
net/bpf/test_run.c:
45                      if (xdp)
   0xffffffff8199f582 <+258>:   test   %r15b,%r15b
   0xffffffff8199f585 <+261>:   jne    0xffffffff8199f522 <bpf_test_run+162>
   0xffffffff8199f587 <+263>:   nopl   0x0(%rax,%rax,1)

./include/linux/bpf.h:
497             return bpf_func(ctx, insnsi);
   0xffffffff8199f58c <+268>:   mov    0x30(%rbp),%rax
   0xffffffff8199f590 <+272>:   mov    %r14,%rsi
   0xffffffff8199f593 <+275>:   mov    %r13,%rdi
   0xffffffff8199f596 <+278>:   callq  0xffffffff81e00eb0
<__x86_indirect_thunk_rax>
   0xffffffff8199f59b <+283>:   mov    %eax,%ecx
   0xffffffff8199f59d <+285>:   jmp    0xffffffff8199f538 <bpf_test_run+184>

The "dfunc":

net/core/filter.c:
8944    DEFINE_BPF_DISPATCHER(bpf_dispatcher_xdp)
   0xffffffff819586d0 <+0>:     callq  0xffffffff81c01680 <__fentry__>
   0xffffffff819586d5 <+5>:     jmpq   0xffffffff81e00f10
<__x86_indirect_thunk_rdx>


> I hope my guess that compiler didn't inline it is correct. Then extra noinline
> will not hurt and that's the only thing needed to avoid the issue.
>

I'd say it's broken not marking it as noinline, and I was lucky. It
would break if other BPF entrypoints that are being called from
filter.o would appear. I'll wait for more comments, and respin a v5
after the weekend.


Thanks,
Björn

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Björn Töpel]

On Wed, 11 Dec 2019 at 14:26, Toke Høiland-Jørgensen <toke@redhat.com> wrote:
>
> [...]
> > +/* The BPF dispatcher is a multiway branch code generator. The
> > + * dispatcher is a mechanism to avoid the performance penalty of an
> > + * indirect call, which is expensive when retpolines are enabled. A
> > + * dispatch client registers a BPF program into the dispatcher, and if
> > + * there is available room in the dispatcher a direct call to the BPF
> > + * program will be generated. All calls to the BPF programs called via
> > + * the dispatcher will then be a direct call, instead of an
> > + * indirect. The dispatcher hijacks a trampoline function it via the
> > + * __fentry__ of the trampoline. The trampoline function has the
> > + * following signature:
> > + *
> > + * unsigned int trampoline(const void *xdp_ctx,
> > + *                         const struct bpf_insn *insnsi,
> > + *                         unsigned int (*bpf_func)(const void *,
> > + *                                                  const struct bpf_insn *));
> > + */
>
> Nit: s/xdp_ctx/ctx/
>

Thanks! Same type-o in the DEFINE/DECLARE macros. Will fix in v5.


Björn


> -Toke
>

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Alexei Starovoitov]

On Fri, Dec 13, 2019 at 08:51:47AM +0100, Björn Töpel wrote:
> 
> > I hope my guess that compiler didn't inline it is correct. Then extra noinline
> > will not hurt and that's the only thing needed to avoid the issue.
> >
> 
> I'd say it's broken not marking it as noinline, and I was lucky. It
> would break if other BPF entrypoints that are being called from
> filter.o would appear. I'll wait for more comments, and respin a v5
> after the weekend.

Also noticed that EXPORT_SYMBOL for dispatch function is not necessary atm.
Please drop it. It can be added later when need arises.

With that please respin right away. No need to wait till Monday.
My general approach on accepting patches is "perfect is the enemy of the good".
It's better to land patches sooner if architecture and api looks good.
Details and minor bugs can be worked out step by step.

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Björn Töpel]

On Fri, 13 Dec 2019 at 16:04, Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Fri, Dec 13, 2019 at 08:51:47AM +0100, Björn Töpel wrote:
> >
> > > I hope my guess that compiler didn't inline it is correct. Then extra noinline
> > > will not hurt and that's the only thing needed to avoid the issue.
> > >
> >
> > I'd say it's broken not marking it as noinline, and I was lucky. It
> > would break if other BPF entrypoints that are being called from
> > filter.o would appear. I'll wait for more comments, and respin a v5
> > after the weekend.
>
> Also noticed that EXPORT_SYMBOL for dispatch function is not necessary atm.
> Please drop it. It can be added later when need arises.
>

It's needed for module builds, so I cannot drop it!

> With that please respin right away. No need to wait till Monday.
> My general approach on accepting patches is "perfect is the enemy of the good".
> It's better to land patches sooner if architecture and api looks good.
> Details and minor bugs can be worked out step by step.
>

Ok! Will respin right away!

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Alexei Starovoitov]

On Fri, Dec 13, 2019 at 7:49 AM Björn Töpel <bjorn.topel@gmail.com> wrote:
>
> On Fri, 13 Dec 2019 at 16:04, Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Fri, Dec 13, 2019 at 08:51:47AM +0100, Björn Töpel wrote:
> > >
> > > > I hope my guess that compiler didn't inline it is correct. Then extra noinline
> > > > will not hurt and that's the only thing needed to avoid the issue.
> > > >
> > >
> > > I'd say it's broken not marking it as noinline, and I was lucky. It
> > > would break if other BPF entrypoints that are being called from
> > > filter.o would appear. I'll wait for more comments, and respin a v5
> > > after the weekend.
> >
> > Also noticed that EXPORT_SYMBOL for dispatch function is not necessary atm.
> > Please drop it. It can be added later when need arises.
> >
>
> It's needed for module builds, so I cannot drop it!

Not following. Which module it's used out of?

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Björn Töpel]

On Fri, 13 Dec 2019 at 16:52, Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Fri, Dec 13, 2019 at 7:49 AM Björn Töpel <bjorn.topel@gmail.com> wrote:
> >
> > On Fri, 13 Dec 2019 at 16:04, Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> > >
> > > On Fri, Dec 13, 2019 at 08:51:47AM +0100, Björn Töpel wrote:
> > > >
> > > > > I hope my guess that compiler didn't inline it is correct. Then extra noinline
> > > > > will not hurt and that's the only thing needed to avoid the issue.
> > > > >
> > > >
> > > > I'd say it's broken not marking it as noinline, and I was lucky. It
> > > > would break if other BPF entrypoints that are being called from
> > > > filter.o would appear. I'll wait for more comments, and respin a v5
> > > > after the weekend.
> > >
> > > Also noticed that EXPORT_SYMBOL for dispatch function is not necessary atm.
> > > Please drop it. It can be added later when need arises.
> > >
> >
> > It's needed for module builds, so I cannot drop it!
>
> Not following. Which module it's used out of?

The trampoline is referenced from bpf_prog_run_xdp(), which is
inlined. Without EXPORT, the symbol is not visible for the module. So,
if, say i40e, is built as a module, you'll get a linker error.

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Alexei Starovoitov]

On Fri, Dec 13, 2019 at 7:59 AM Björn Töpel <bjorn.topel@gmail.com> wrote:
>
> On Fri, 13 Dec 2019 at 16:52, Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Fri, Dec 13, 2019 at 7:49 AM Björn Töpel <bjorn.topel@gmail.com> wrote:
> > >
> > > On Fri, 13 Dec 2019 at 16:04, Alexei Starovoitov
> > > <alexei.starovoitov@gmail.com> wrote:
> > > >
> > > > On Fri, Dec 13, 2019 at 08:51:47AM +0100, Björn Töpel wrote:
> > > > >
> > > > > > I hope my guess that compiler didn't inline it is correct. Then extra noinline
> > > > > > will not hurt and that's the only thing needed to avoid the issue.
> > > > > >
> > > > >
> > > > > I'd say it's broken not marking it as noinline, and I was lucky. It
> > > > > would break if other BPF entrypoints that are being called from
> > > > > filter.o would appear. I'll wait for more comments, and respin a v5
> > > > > after the weekend.
> > > >
> > > > Also noticed that EXPORT_SYMBOL for dispatch function is not necessary atm.
> > > > Please drop it. It can be added later when need arises.
> > > >
> > >
> > > It's needed for module builds, so I cannot drop it!
> >
> > Not following. Which module it's used out of?
>
> The trampoline is referenced from bpf_prog_run_xdp(), which is
> inlined. Without EXPORT, the symbol is not visible for the module. So,
> if, say i40e, is built as a module, you'll get a linker error.

I'm still not following. i40e is not using this dispatch logic any more.

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Björn Töpel]

On Fri, 13 Dec 2019 at 17:03, Alexei Starovoitov
<alexei.starovoitov@gmail.com> wrote:
>
> On Fri, Dec 13, 2019 at 7:59 AM Björn Töpel <bjorn.topel@gmail.com> wrote:
> >
> > On Fri, 13 Dec 2019 at 16:52, Alexei Starovoitov
> > <alexei.starovoitov@gmail.com> wrote:
> > >
> > > On Fri, Dec 13, 2019 at 7:49 AM Björn Töpel <bjorn.topel@gmail.com> wrote:
> > > >
> > > > On Fri, 13 Dec 2019 at 16:04, Alexei Starovoitov
> > > > <alexei.starovoitov@gmail.com> wrote:
> > > > >
> > > > > On Fri, Dec 13, 2019 at 08:51:47AM +0100, Björn Töpel wrote:
> > > > > >
> > > > > > > I hope my guess that compiler didn't inline it is correct. Then extra noinline
> > > > > > > will not hurt and that's the only thing needed to avoid the issue.
> > > > > > >
> > > > > >
> > > > > > I'd say it's broken not marking it as noinline, and I was lucky. It
> > > > > > would break if other BPF entrypoints that are being called from
> > > > > > filter.o would appear. I'll wait for more comments, and respin a v5
> > > > > > after the weekend.
> > > > >
> > > > > Also noticed that EXPORT_SYMBOL for dispatch function is not necessary atm.
> > > > > Please drop it. It can be added later when need arises.
> > > > >
> > > >
> > > > It's needed for module builds, so I cannot drop it!
> > >
> > > Not following. Which module it's used out of?
> >
> > The trampoline is referenced from bpf_prog_run_xdp(), which is
> > inlined. Without EXPORT, the symbol is not visible for the module. So,
> > if, say i40e, is built as a module, you'll get a linker error.
>
> I'm still not following. i40e is not using this dispatch logic any more.

Hmm, *all* XDP users uses it, but indirectly via bpf_prog_run_xdp().
All drivers that execute an XDP program, does that via the
bpf_prog_run_xdp(), say, i40e_txrx.c and i40e_xsk.c.
bpf_prog_run_xdp() is inlined and expaned to __BPF_PROG_RUN(), which
calls into the dispatcher trampoline.

$ nm drivers/net/ethernet/intel/i40e/i40e_xsk.o|grep xdpfunc
                 U bpf_dispatcher_xdpfunc

Makes sense?

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Alexei Starovoitov]

On Fri, Dec 13, 2019 at 05:09:46PM +0100, Björn Töpel wrote:
> On Fri, 13 Dec 2019 at 17:03, Alexei Starovoitov
> <alexei.starovoitov@gmail.com> wrote:
> >
> > On Fri, Dec 13, 2019 at 7:59 AM Björn Töpel <bjorn.topel@gmail.com> wrote:
> > >
> > > On Fri, 13 Dec 2019 at 16:52, Alexei Starovoitov
> > > <alexei.starovoitov@gmail.com> wrote:
> > > >
> > > > On Fri, Dec 13, 2019 at 7:49 AM Björn Töpel <bjorn.topel@gmail.com> wrote:
> > > > >
> > > > > On Fri, 13 Dec 2019 at 16:04, Alexei Starovoitov
> > > > > <alexei.starovoitov@gmail.com> wrote:
> > > > > >
> > > > > > On Fri, Dec 13, 2019 at 08:51:47AM +0100, Björn Töpel wrote:
> > > > > > >
> > > > > > > > I hope my guess that compiler didn't inline it is correct. Then extra noinline
> > > > > > > > will not hurt and that's the only thing needed to avoid the issue.
> > > > > > > >
> > > > > > >
> > > > > > > I'd say it's broken not marking it as noinline, and I was lucky. It
> > > > > > > would break if other BPF entrypoints that are being called from
> > > > > > > filter.o would appear. I'll wait for more comments, and respin a v5
> > > > > > > after the weekend.
> > > > > >
> > > > > > Also noticed that EXPORT_SYMBOL for dispatch function is not necessary atm.
> > > > > > Please drop it. It can be added later when need arises.
> > > > > >
> > > > >
> > > > > It's needed for module builds, so I cannot drop it!
> > > >
> > > > Not following. Which module it's used out of?
> > >
> > > The trampoline is referenced from bpf_prog_run_xdp(), which is
> > > inlined. Without EXPORT, the symbol is not visible for the module. So,
> > > if, say i40e, is built as a module, you'll get a linker error.
> >
> > I'm still not following. i40e is not using this dispatch logic any more.
> 
> Hmm, *all* XDP users uses it, but indirectly via bpf_prog_run_xdp().
> All drivers that execute an XDP program, does that via the
> bpf_prog_run_xdp(), say, i40e_txrx.c and i40e_xsk.c.
> bpf_prog_run_xdp() is inlined and expaned to __BPF_PROG_RUN(), which
> calls into the dispatcher trampoline.
> 
> $ nm drivers/net/ethernet/intel/i40e/i40e_xsk.o|grep xdpfunc
>                  U bpf_dispatcher_xdpfunc
> 
> Makes sense?

ahh. got it. bpf_prog_run_xdp() is static inline in .h

Thank you for explaining!

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Steven Rostedt]

On Wed, 11 Dec 2019 13:30:13 +0100
Björn Töpel <bjorn.topel@gmail.com> wrote:

> From: Björn Töpel <bjorn.topel@intel.com>
> 
> The BPF dispatcher is a multi-way branch code generator, mainly
> targeted for XDP programs. When an XDP program is executed via the
> bpf_prog_run_xdp(), it is invoked via an indirect call. The indirect
> call has a substantial performance impact, when retpolines are
> enabled. The dispatcher transform indirect calls to direct calls, and
> therefore avoids the retpoline. The dispatcher is generated using the
> BPF JIT, and relies on text poking provided by bpf_arch_text_poke().
> 
> The dispatcher hijacks a trampoline function it via the __fentry__ nop

Why was the ftrace maintainers not Cc'd on this patch?  I would have NACKED
it. Hell, it wasn't even sent to LKML! This was BPF being sneaky in
updating major infrastructure of the Linux kernel without letting the
stakeholders of this change know about it.

For some reason, the BPF folks think they own the entire kernel!

When I heard that ftrace was broken by BPF I thought it was something
unique they were doing, but unfortunately, I didn't investigate what they
were doing at the time.

Then they started sending me patches to hide fentry locations from ftrace.
And even telling me that fentry != ftrace

   https://lore.kernel.org/all/CAADnVQJTT7h3MniVqdBEU=eLwvJhEKNLSjbUAK4sOrhN=zggCQ@mail.gmail.com/
	
Even though fentry was created for ftrace

   https://lore.kernel.org/lkml/1258720459.22249.1018.camel@gandalf.stny.rr.com/

and all the work with fentry was for the ftrace infrastructure. Ftrace
takes a lot of care for security and use cases for other users (like
live kernel patching). But BPF has the NIH syndrome, and likes to own
everything and recreate the wheel so that they have full control.

> of the trampoline. One dispatcher instance currently supports up to 64
> dispatch points. A user creates a dispatcher with its corresponding
> trampoline with the DEFINE_BPF_DISPATCHER macro.

Anyway, this patch just looks like a re-implementation of static_calls:

   https://lore.kernel.org/all/20200818135735.948368560@infradead.org/

Maybe if the BPF folks communicated to a wider audience, they would not
need to constantly recreate the wheel.

-- Steve


> 
> Signed-off-by: Björn Töpel <bjorn.topel@intel.com>
> ---
>  arch/x86/net/bpf_jit_comp.c | 122 +++++++++++++++++++++++++++
>  include/linux/bpf.h         |  56 +++++++++++++
>  kernel/bpf/Makefile         |   1 +
>  kernel/bpf/dispatcher.c     | 159 ++++++++++++++++++++++++++++++++++++
>  4 files changed, 338 insertions(+)
>  create mode 100644 kernel/bpf/dispatcher.c
> 
> diff --git a/arch/x86/net/bpf_jit_comp.c b/arch/x86/net/bpf_jit_comp.c
> index b8be18427277..3ce7ad41bd6f 100644
> --- a/arch/x86/net/bpf_jit_comp.c
> +++ b/arch/x86/net/bpf_jit_comp.c
> @@ -10,10 +10,12 @@
>  #include <linux/if_vlan.h>
>  #include <linux/bpf.h>
>  #include <linux/memory.h>
> +#include <linux/sort.h>
>  #include <asm/extable.h>
>  #include <asm/set_memory.h>
>  #include <asm/nospec-branch.h>
>  #include <asm/text-patching.h>
> +#include <asm/asm-prototypes.h>
>  
>  static u8 *emit_code(u8 *ptr, u32 bytes, unsigned int len)
>  {
> @@ -1530,6 +1532,126 @@ int arch_prepare_bpf_trampoline(void *image, struct btf_func_model *m, u32 flags
>  	return 0;
>  }
>  
> +static int emit_cond_near_jump(u8 **pprog, void *func, void *ip, u8 jmp_cond)
> +{
> +	u8 *prog = *pprog;
> +	int cnt = 0;
> +	s64 offset;
> +
> +	offset = func - (ip + 2 + 4);
> +	if (!is_simm32(offset)) {
> +		pr_err("Target %p is out of range\n", func);
> +		return -EINVAL;
> +	}
> +	EMIT2_off32(0x0F, jmp_cond + 0x10, offset);
> +	*pprog = prog;
> +	return 0;
> +}
> +
> +static int emit_fallback_jump(u8 **pprog)
> +{
> +	u8 *prog = *pprog;
> +	int err = 0;
> +
> +#ifdef CONFIG_RETPOLINE
> +	/* Note that this assumes the the compiler uses external
> +	 * thunks for indirect calls. Both clang and GCC use the same
> +	 * naming convention for external thunks.
> +	 */
> +	err = emit_jump(&prog, __x86_indirect_thunk_rdx, prog);
> +#else
> +	int cnt = 0;
> +
> +	EMIT2(0xFF, 0xE2);	/* jmp rdx */
> +#endif
> +	*pprog = prog;
> +	return err;
> +}
> +
> +static int emit_bpf_dispatcher(u8 **pprog, int a, int b, s64 *progs)
> +{
> +	int pivot, err, jg_bytes = 1, cnt = 0;
> +	u8 *jg_reloc, *prog = *pprog;
> +	s64 jg_offset;
> +
> +	if (a == b) {
> +		/* Leaf node of recursion, i.e. not a range of indices
> +		 * anymore.
> +		 */
> +		EMIT1(add_1mod(0x48, BPF_REG_3));	/* cmp rdx,func */
> +		if (!is_simm32(progs[a]))
> +			return -1;
> +		EMIT2_off32(0x81, add_1reg(0xF8, BPF_REG_3),
> +			    progs[a]);
> +		err = emit_cond_near_jump(&prog,	/* je func */
> +					  (void *)progs[a], prog,
> +					  X86_JE);
> +		if (err)
> +			return err;
> +
> +		err = emit_fallback_jump(&prog);	/* jmp thunk/indirect */
> +		if (err)
> +			return err;
> +
> +		*pprog = prog;
> +		return 0;
> +	}
> +
> +	/* Not a leaf node, so we pivot, and recursively descend into
> +	 * the lower and upper ranges.
> +	 */
> +	pivot = (b - a) / 2;
> +	EMIT1(add_1mod(0x48, BPF_REG_3));		/* cmp rdx,func */
> +	if (!is_simm32(progs[a + pivot]))
> +		return -1;
> +	EMIT2_off32(0x81, add_1reg(0xF8, BPF_REG_3), progs[a + pivot]);
> +
> +	if (pivot > 2) {				/* jg upper_part */
> +		/* Require near jump. */
> +		jg_bytes = 4;
> +		EMIT2_off32(0x0F, X86_JG + 0x10, 0);
> +	} else {
> +		EMIT2(X86_JG, 0);
> +	}
> +	jg_reloc = prog;
> +
> +	err = emit_bpf_dispatcher(&prog, a, a + pivot,	/* emit lower_part */
> +				  progs);
> +	if (err)
> +		return err;
> +
> +	jg_offset = prog - jg_reloc;
> +	emit_code(jg_reloc - jg_bytes, jg_offset, jg_bytes);
> +
> +	err = emit_bpf_dispatcher(&prog, a + pivot + 1,	/* emit upper_part */
> +				  b, progs);
> +	if (err)
> +		return err;
> +
> +	*pprog = prog;
> +	return 0;
> +}
> +
> +static int cmp_ips(const void *a, const void *b)
> +{
> +	const s64 *ipa = a;
> +	const s64 *ipb = b;
> +
> +	if (*ipa > *ipb)
> +		return 1;
> +	if (*ipa < *ipb)
> +		return -1;
> +	return 0;
> +}
> +
> +int arch_prepare_bpf_dispatcher(void *image, s64 *funcs, int num_funcs)
> +{
> +	u8 *prog = image;
> +
> +	sort(funcs, num_funcs, sizeof(funcs[0]), cmp_ips, NULL);
> +	return emit_bpf_dispatcher(&prog, 0, num_funcs - 1, funcs);
> +}
> +
>  struct x64_jit_data {
>  	struct bpf_binary_header *header;
>  	int *addrs;
> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> index 5d744828b399..e6a9d74d4e30 100644
> --- a/include/linux/bpf.h
> +++ b/include/linux/bpf.h
> @@ -470,12 +470,61 @@ struct bpf_trampoline {
>  	void *image;
>  	u64 selector;
>  };
> +
> +#define BPF_DISPATCHER_MAX 64 /* Fits in 2048B */
> +
> +struct bpf_dispatcher_prog {
> +	struct bpf_prog *prog;
> +	refcount_t users;
> +};
> +
> +struct bpf_dispatcher {
> +	/* dispatcher mutex */
> +	struct mutex mutex;
> +	void *func;
> +	struct bpf_dispatcher_prog progs[BPF_DISPATCHER_MAX];
> +	int num_progs;
> +	void *image;
> +	u32 image_off;
> +};
> +
>  #ifdef CONFIG_BPF_JIT
>  struct bpf_trampoline *bpf_trampoline_lookup(u64 key);
>  int bpf_trampoline_link_prog(struct bpf_prog *prog);
>  int bpf_trampoline_unlink_prog(struct bpf_prog *prog);
>  void bpf_trampoline_put(struct bpf_trampoline *tr);
>  void *bpf_jit_alloc_exec_page(void);
> +#define BPF_DISPATCHER_INIT(name) {			\
> +	.mutex = __MUTEX_INITIALIZER(name.mutex),	\
> +	.func = &name##func,				\
> +	.progs = {},					\
> +	.num_progs = 0,					\
> +	.image = NULL,					\
> +	.image_off = 0					\
> +}
> +
> +#define DEFINE_BPF_DISPATCHER(name)					\
> +	unsigned int name##func(					\
> +		const void *xdp_ctx,					\
> +		const struct bpf_insn *insnsi,				\
> +		unsigned int (*bpf_func)(const void *,			\
> +					 const struct bpf_insn *))	\
> +	{								\
> +		return bpf_func(xdp_ctx, insnsi);			\
> +	}								\
> +	EXPORT_SYMBOL(name##func);			\
> +	struct bpf_dispatcher name = BPF_DISPATCHER_INIT(name);
> +#define DECLARE_BPF_DISPATCHER(name)					\
> +	unsigned int name##func(					\
> +		const void *xdp_ctx,					\
> +		const struct bpf_insn *insnsi,				\
> +		unsigned int (*bpf_func)(const void *,			\
> +					 const struct bpf_insn *));	\
> +	extern struct bpf_dispatcher name;
> +#define BPF_DISPATCHER_FUNC(name) name##func
> +#define BPF_DISPATCHER_PTR(name) (&name)
> +void bpf_dispatcher_change_prog(struct bpf_dispatcher *d, struct bpf_prog *from,
> +				struct bpf_prog *to);
>  #else
>  static inline struct bpf_trampoline *bpf_trampoline_lookup(u64 key)
>  {
> @@ -490,6 +539,13 @@ static inline int bpf_trampoline_unlink_prog(struct bpf_prog *prog)
>  	return -ENOTSUPP;
>  }
>  static inline void bpf_trampoline_put(struct bpf_trampoline *tr) {}
> +#define DEFINE_BPF_DISPATCHER(name)
> +#define DECLARE_BPF_DISPATCHER(name)
> +#define BPF_DISPATCHER_FUNC(name) bpf_dispatcher_nopfunc
> +#define BPF_DISPATCHER_PTR(name) NULL
> +static inline void bpf_dispatcher_change_prog(struct bpf_dispatcher *d,
> +					      struct bpf_prog *from,
> +					      struct bpf_prog *to) {}
>  #endif
>  
>  struct bpf_func_info_aux {
> diff --git a/kernel/bpf/Makefile b/kernel/bpf/Makefile
> index 3f671bf617e8..d4f330351f87 100644
> --- a/kernel/bpf/Makefile
> +++ b/kernel/bpf/Makefile
> @@ -8,6 +8,7 @@ obj-$(CONFIG_BPF_SYSCALL) += local_storage.o queue_stack_maps.o
>  obj-$(CONFIG_BPF_SYSCALL) += disasm.o
>  obj-$(CONFIG_BPF_JIT) += trampoline.o
>  obj-$(CONFIG_BPF_SYSCALL) += btf.o
> +obj-$(CONFIG_BPF_JIT) += dispatcher.o
>  ifeq ($(CONFIG_NET),y)
>  obj-$(CONFIG_BPF_SYSCALL) += devmap.o
>  obj-$(CONFIG_BPF_SYSCALL) += cpumap.o
> diff --git a/kernel/bpf/dispatcher.c b/kernel/bpf/dispatcher.c
> new file mode 100644
> index 000000000000..a4690460d815
> --- /dev/null
> +++ b/kernel/bpf/dispatcher.c
> @@ -0,0 +1,159 @@
> +// SPDX-License-Identifier: GPL-2.0-only
> +/* Copyright(c) 2019 Intel Corporation. */
> +
> +#include <linux/hash.h>
> +#include <linux/bpf.h>
> +#include <linux/filter.h>
> +
> +/* The BPF dispatcher is a multiway branch code generator. The
> + * dispatcher is a mechanism to avoid the performance penalty of an
> + * indirect call, which is expensive when retpolines are enabled. A
> + * dispatch client registers a BPF program into the dispatcher, and if
> + * there is available room in the dispatcher a direct call to the BPF
> + * program will be generated. All calls to the BPF programs called via
> + * the dispatcher will then be a direct call, instead of an
> + * indirect. The dispatcher hijacks a trampoline function it via the
> + * __fentry__ of the trampoline. The trampoline function has the
> + * following signature:
> + *
> + * unsigned int trampoline(const void *xdp_ctx,
> + *                         const struct bpf_insn *insnsi,
> + *                         unsigned int (*bpf_func)(const void *,
> + *                                                  const struct bpf_insn *));
> + */
> +
> +static struct bpf_dispatcher_prog *bpf_dispatcher_find_prog(
> +	struct bpf_dispatcher *d, struct bpf_prog *prog)
> +{
> +	int i;
> +
> +	for (i = 0; i < BPF_DISPATCHER_MAX; i++) {
> +		if (prog == d->progs[i].prog)
> +			return &d->progs[i];
> +	}
> +	return NULL;
> +}
> +
> +static struct bpf_dispatcher_prog *bpf_dispatcher_find_free(
> +	struct bpf_dispatcher *d)
> +{
> +	return bpf_dispatcher_find_prog(d, NULL);
> +}
> +
> +static bool bpf_dispatcher_add_prog(struct bpf_dispatcher *d,
> +				    struct bpf_prog *prog)
> +{
> +	struct bpf_dispatcher_prog *entry;
> +
> +	if (!prog)
> +		return false;
> +
> +	entry = bpf_dispatcher_find_prog(d, prog);
> +	if (entry) {
> +		refcount_inc(&entry->users);
> +		return false;
> +	}
> +
> +	entry = bpf_dispatcher_find_free(d);
> +	if (!entry)
> +		return false;
> +
> +	bpf_prog_inc(prog);
> +	entry->prog = prog;
> +	refcount_set(&entry->users, 1);
> +	d->num_progs++;
> +	return true;
> +}
> +
> +static bool bpf_dispatcher_remove_prog(struct bpf_dispatcher *d,
> +				       struct bpf_prog *prog)
> +{
> +	struct bpf_dispatcher_prog *entry;
> +
> +	if (!prog)
> +		return false;
> +
> +	entry = bpf_dispatcher_find_prog(d, prog);
> +	if (!entry)
> +		return false;
> +
> +	if (refcount_dec_and_test(&entry->users)) {
> +		entry->prog = NULL;
> +		bpf_prog_put(prog);
> +		d->num_progs--;
> +		return true;
> +	}
> +	return false;
> +}
> +
> +int __weak arch_prepare_bpf_dispatcher(void *image, s64 *funcs, int num_funcs)
> +{
> +	return -ENOTSUPP;
> +}
> +
> +static int bpf_dispatcher_prepare(struct bpf_dispatcher *d, void *image)
> +{
> +	s64 ips[BPF_DISPATCHER_MAX] = {}, *ipsp = &ips[0];
> +	int i;
> +
> +	for (i = 0; i < BPF_DISPATCHER_MAX; i++) {
> +		if (d->progs[i].prog)
> +			*ipsp++ = (s64)(uintptr_t)d->progs[i].prog->bpf_func;
> +	}
> +	return arch_prepare_bpf_dispatcher(image, &ips[0], d->num_progs);
> +}
> +
> +static void bpf_dispatcher_update(struct bpf_dispatcher *d, int prev_num_progs)
> +{
> +	void *old, *new;
> +	u32 noff;
> +	int err;
> +
> +	if (!prev_num_progs) {
> +		old = NULL;
> +		noff = 0;
> +	} else {
> +		old = d->image + d->image_off;
> +		noff = d->image_off ^ (PAGE_SIZE / 2);
> +	}
> +
> +	new = d->num_progs ? d->image + noff : NULL;
> +	if (new) {
> +		if (bpf_dispatcher_prepare(d, new))
> +			return;
> +	}
> +
> +	err = bpf_arch_text_poke(d->func, BPF_MOD_JUMP, old, new);
> +	if (err || !new)
> +		return;
> +
> +	d->image_off = noff;
> +}
> +
> +void bpf_dispatcher_change_prog(struct bpf_dispatcher *d, struct bpf_prog *from,
> +				struct bpf_prog *to)
> +{
> +	bool changed = false;
> +	int prev_num_progs;
> +
> +	if (from == to)
> +		return;
> +
> +	mutex_lock(&d->mutex);
> +	if (!d->image) {
> +		d->image = bpf_jit_alloc_exec_page();
> +		if (!d->image)
> +			goto out;
> +	}
> +
> +	prev_num_progs = d->num_progs;
> +	changed |= bpf_dispatcher_remove_prog(d, from);
> +	changed |= bpf_dispatcher_add_prog(d, to);
> +
> +	if (!changed)
> +		goto out;
> +
> +	bpf_dispatcher_update(d, prev_num_progs);
> +out:
> +	mutex_unlock(&d->mutex);
> +}

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Alexei Starovoitov]

On Mon, Aug 15, 2022 at 7:13 AM Steven Rostedt <rostedt@goodmis.org> wrote:
>
> On Wed, 11 Dec 2019 13:30:13 +0100
> Björn Töpel <bjorn.topel@gmail.com> wrote:
>
> > From: Björn Töpel <bjorn.topel@intel.com>
> >
> > The BPF dispatcher is a multi-way branch code generator, mainly
> > targeted for XDP programs. When an XDP program is executed via the
> > bpf_prog_run_xdp(), it is invoked via an indirect call. The indirect
> > call has a substantial performance impact, when retpolines are
> > enabled. The dispatcher transform indirect calls to direct calls, and
> > therefore avoids the retpoline. The dispatcher is generated using the
> > BPF JIT, and relies on text poking provided by bpf_arch_text_poke().
> >
> > The dispatcher hijacks a trampoline function it via the __fentry__ nop
>
> Why was the ftrace maintainers not Cc'd on this patch?  I would have NACKED
> it. Hell, it wasn't even sent to LKML! This was BPF being sneaky in
> updating major infrastructure of the Linux kernel without letting the
> stakeholders of this change know about it.
>
> For some reason, the BPF folks think they own the entire kernel!
>
> When I heard that ftrace was broken by BPF I thought it was something
> unique they were doing, but unfortunately, I didn't investigate what they
> were doing at the time.

ftrace is still broken and refusing to accept the fact doesn't make it
non-broken.

> Then they started sending me patches to hide fentry locations from ftrace.
> And even telling me that fentry != ftrace

It sounds that you've invented nop5 and kernel's ability
to replace nop5 with a jump or call.
ftrace should really stop trying to own all of the kernel text rewrites.
It's in the way. Like this case.

>    https://lore.kernel.org/all/CAADnVQJTT7h3MniVqdBEU=eLwvJhEKNLSjbUAK4sOrhN=zggCQ@mail.gmail.com/
>
> Even though fentry was created for ftrace
>
>    https://lore.kernel.org/lkml/1258720459.22249.1018.camel@gandalf.stny.rr.com/
>
> and all the work with fentry was for the ftrace infrastructure. Ftrace
> takes a lot of care for security and use cases for other users (like
> live kernel patching). But BPF has the NIH syndrome, and likes to own
> everything and recreate the wheel so that they have full control.
>
> > of the trampoline. One dispatcher instance currently supports up to 64
> > dispatch points. A user creates a dispatcher with its corresponding
> > trampoline with the DEFINE_BPF_DISPATCHER macro.
>
> Anyway, this patch just looks like a re-implementation of static_calls:

It was implemented long before static_calls made it to the kernel
and it's different. Please do your home work.

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Peter Zijlstra]

On Mon, Aug 15, 2022 at 07:31:23AM -0700, Alexei Starovoitov wrote:
> On Mon, Aug 15, 2022 at 7:13 AM Steven Rostedt <rostedt@goodmis.org> wrote:
> >
> > On Wed, 11 Dec 2019 13:30:13 +0100
> > Björn Töpel <bjorn.topel@gmail.com> wrote:
> >
> > > From: Björn Töpel <bjorn.topel@intel.com>
> > >
> > > The BPF dispatcher is a multi-way branch code generator, mainly
> > > targeted for XDP programs. When an XDP program is executed via the
> > > bpf_prog_run_xdp(), it is invoked via an indirect call. The indirect
> > > call has a substantial performance impact, when retpolines are
> > > enabled. The dispatcher transform indirect calls to direct calls, and
> > > therefore avoids the retpoline. The dispatcher is generated using the
> > > BPF JIT, and relies on text poking provided by bpf_arch_text_poke().
> > >
> > > The dispatcher hijacks a trampoline function it via the __fentry__ nop
> >
> > Why was the ftrace maintainers not Cc'd on this patch?  I would have NACKED
> > it. Hell, it wasn't even sent to LKML! This was BPF being sneaky in
> > updating major infrastructure of the Linux kernel without letting the
> > stakeholders of this change know about it.
> >
> > For some reason, the BPF folks think they own the entire kernel!
> >
> > When I heard that ftrace was broken by BPF I thought it was something
> > unique they were doing, but unfortunately, I didn't investigate what they
> > were doing at the time.
> 
> ftrace is still broken and refusing to accept the fact doesn't make it
> non-broken.

Alexei, stop this. The 'call __fentry__' sites are owned by ftrace.
Always have been. If BPF somehow thinks it can use them without telling
ftrace then it's BPF that's broken.

> > Then they started sending me patches to hide fentry locations from ftrace.
> > And even telling me that fentry != ftrace
> 
> It sounds that you've invented nop5 and kernel's ability
> to replace nop5 with a jump or call.

Ftrace has introduced the mcount/fentry patching into the kernel and has
always owned it for those sites. There is a lot of other text writing
not owned by ftrace. But the fentry sites are ftrace's.

Ftrace was also the one that got us the text_poke_bp() infrastructure
and got it reviewed by the CPU vendors.

Since then we've grown static_branch and static_call, they have their
own patch sites and do no interfere with ftrace.

> ftrace should really stop trying to own all of the kernel text rewrites.
> It's in the way. Like this case.

It doesn't. It hasn't. But it *does* own the fentry sites.

> It was implemented long before static_calls made it to the kernel
> and it's different.

It wasn't long before. Yes it landed a few months prior to the
static_call work, but the whole static_call thing was in progress for a
long long time.

Anyway, yes it is different. But it's still very much broken. You simply
cannot step on __fentry__ sites like that.

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Steven Rostedt]

On Mon, 15 Aug 2022 07:31:23 -0700
Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote:
> >
> > When I heard that ftrace was broken by BPF I thought it was something
> > unique they were doing, but unfortunately, I didn't investigate what they
> > were doing at the time.  
> 
> ftrace is still broken and refusing to accept the fact doesn't make it
> non-broken.

I extended Jiri's patch to make it work again.

> 
> > Then they started sending me patches to hide fentry locations from ftrace.
> > And even telling me that fentry != ftrace  
> 
> It sounds that you've invented nop5 and kernel's ability
> to replace nop5 with a jump or call.

Actually I did invent it.

   https://lore.kernel.org/lkml/20080210072109.GR4100@elte.hu/


I'm the one that introduced the code to convert mcount into the 5 byte nop,
and did the research and development to make it work at run time. I had one
hiccup along the way that caused the e1000e network card breakage.

The "daemon" approach was horrible, and then I created the recordmcount.pl
perl script to accomplish the same thing at compile time.

> ftrace should really stop trying to own all of the kernel text rewrites.
> It's in the way. Like this case.

It's not trying to own all modifications (static_calls is not ftrace). But
the code at the start of functions with fentry does belong to it.

> 
> >    https://lore.kernel.org/all/CAADnVQJTT7h3MniVqdBEU=eLwvJhEKNLSjbUAK4sOrhN=zggCQ@mail.gmail.com/
> >
> > Even though fentry was created for ftrace
> >
> >    https://lore.kernel.org/lkml/1258720459.22249.1018.camel@gandalf.stny.rr.com/
> >
> > and all the work with fentry was for the ftrace infrastructure. Ftrace
> > takes a lot of care for security and use cases for other users (like
> > live kernel patching). But BPF has the NIH syndrome, and likes to own
> > everything and recreate the wheel so that they have full control.
> >  
> > > of the trampoline. One dispatcher instance currently supports up to 64
> > > dispatch points. A user creates a dispatcher with its corresponding
> > > trampoline with the DEFINE_BPF_DISPATCHER macro.  
> >
> > Anyway, this patch just looks like a re-implementation of static_calls:  
> 
> It was implemented long before static_calls made it to the kernel
> and it's different. Please do your home work.

Long before? This code made it into the kernel in Dec 2019. Yes static calls
finally made it into the kernel in 2020, but it was first introduced in
October 2018:

  https://lore.kernel.org/all/20181006015110.653946300@goodmis.org/

If you had Cc'd us on this patch, we could have collaborated and come up
with something that would have worked for you.

It took time to get in because we don't just push our features in, we make
sure that they are generic and work for others, and is secure and robust.

I sent a proof of concept, Josh took over, Linus had issues, and finally
Peter pushed it through the gate. It's a long process, but we don't break
others code while doing it!

-- Steve

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Alexei Starovoitov]

On Mon, Aug 15, 2022 at 8:16 AM Steven Rostedt <rostedt@goodmis.org> wrote:
>
> On Mon, 15 Aug 2022 07:31:23 -0700
> Alexei Starovoitov <alexei.starovoitov@gmail.com> wrote:
> > >
> > > When I heard that ftrace was broken by BPF I thought it was something
> > > unique they were doing, but unfortunately, I didn't investigate what they
> > > were doing at the time.
> >
> > ftrace is still broken and refusing to accept the fact doesn't make it
> > non-broken.
>
> I extended Jiri's patch to make it work again.
>
> >
> > > Then they started sending me patches to hide fentry locations from ftrace.
> > > And even telling me that fentry != ftrace
> >
> > It sounds that you've invented nop5 and kernel's ability
> > to replace nop5 with a jump or call.
>
> Actually I did invent it.
>
>    https://lore.kernel.org/lkml/20080210072109.GR4100@elte.hu/
>
>
> I'm the one that introduced the code to convert mcount into the 5 byte nop,
> and did the research and development to make it work at run time. I had one
> hiccup along the way that caused the e1000e network card breakage.
>
> The "daemon" approach was horrible, and then I created the recordmcount.pl
> perl script to accomplish the same thing at compile time.
>
> > ftrace should really stop trying to own all of the kernel text rewrites.
> > It's in the way. Like this case.
>
> It's not trying to own all modifications (static_calls is not ftrace). But
> the code at the start of functions with fentry does belong to it.
>
> >
> > >    https://lore.kernel.org/all/CAADnVQJTT7h3MniVqdBEU=eLwvJhEKNLSjbUAK4sOrhN=zggCQ@mail.gmail.com/
> > >
> > > Even though fentry was created for ftrace
> > >
> > >    https://lore.kernel.org/lkml/1258720459.22249.1018.camel@gandalf.stny.rr.com/
> > >
> > > and all the work with fentry was for the ftrace infrastructure. Ftrace
> > > takes a lot of care for security and use cases for other users (like
> > > live kernel patching). But BPF has the NIH syndrome, and likes to own
> > > everything and recreate the wheel so that they have full control.
> > >
> > > > of the trampoline. One dispatcher instance currently supports up to 64
> > > > dispatch points. A user creates a dispatcher with its corresponding
> > > > trampoline with the DEFINE_BPF_DISPATCHER macro.
> > >
> > > Anyway, this patch just looks like a re-implementation of static_calls:
> >
> > It was implemented long before static_calls made it to the kernel
> > and it's different. Please do your home work.
>
> Long before? This code made it into the kernel in Dec 2019. Yes static calls
> finally made it into the kernel in 2020, but it was first introduced in
> October 2018:
>
>   https://lore.kernel.org/all/20181006015110.653946300@goodmis.org/
>
> If you had Cc'd us on this patch, we could have collaborated and come up
> with something that would have worked for you.
>
> It took time to get in because we don't just push our features in, we make
> sure that they are generic and work for others, and is secure and robust.
>
> I sent a proof of concept, Josh took over, Linus had issues, and finally
> Peter pushed it through the gate. It's a long process, but we don't break
> others code while doing it!

Replied in the other thread. Let's stick to one thread please.

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Steven Rostedt]

On Mon, 15 Aug 2022 11:16:58 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:

> Actually I did invent it.
> 
>    https://lore.kernel.org/lkml/20080210072109.GR4100@elte.hu/

And the next patch replaced the jmps with nops. We kept this as separate
patches for debugging reasons.

 commit dfa60aba04dae78 ("ftrace: use nops instead of jmp")

-- Steve

Re: [PATCH bpf-next v4 2/6] bpf: introduce BPF dispatcher

[Steven Rostedt]

On Mon, 15 Aug 2022 11:16:58 -0400
Steven Rostedt <rostedt@goodmis.org> wrote:

> > It sounds that you've invented nop5 and kernel's ability
> > to replace nop5 with a jump or call.  
> 
> Actually I did invent it.
> 
>    https://lore.kernel.org/lkml/20080210072109.GR4100@elte.hu/
> 
> 
> I'm the one that introduced the code to convert mcount into the 5 byte nop,
> and did the research and development to make it work at run time. I had one
> hiccup along the way that caused the e1000e network card breakage.
> 
> The "daemon" approach was horrible, and then I created the recordmcount.pl
> perl script to accomplish the same thing at compile time.

I guess you were not paying attention to my talk at the Kernel Recipes I
invited you to in 2019. The talk I gave was the history of how fentry came
about.

  https://kernel-recipes.org/en/2019/talks/ftrace-where-modifying-a-running-kernel-all-started/

 ;-)

-- Steve