Skip to contentSkip to conversation

Add internal-only BPF per-CPU instruction

PATCH Applied Andrii Nakryiko 8 participants 26 messages Apr 2, 2024 – Apr 5, 2024

Subsystems (5)
x86 BPF BPF core bpftool +1 more subsystems
lore
Share & tools
lore

Andrii Nakryiko

author maintainer
#0 lore raw

v2 cover Add internal-only BPF per-CPU instruction

Add a new BPF instruction for resolving per-CPU memory addresses.

New instruction is a special form of BPF_ALU64 | BPF_MOV | BPF_DW, with insns->off set to BPF_ADDR_PERCPU (== -1). It resolves provided per-CPU offset to an absolute address where per-CPU data resides for "this" CPU.

This patch set implements support for it in x86-64 BPF JIT only.

Using the new instruction, we also implement inlining for three cases:
- bpf_get_smp_processor_id(), which allows to avoid unnecessary trivial function call, saving a bit of performance and also not polluting LBR records with unnecessary function call/return records;
- PERCPU_ARRAY's bpf_map_lookup_elem() is completely inlined, bringing its performance to implementing per-CPU data structures using global variables in BPF (which is an awesome improvement, see benchmarks below);
- PERCPU_HASH's bpf_map_lookup_elem() is partially inlined, just like the same for non-PERCPU HASH map; this still saves a bit of overhead.

To validate performance benefits, I hacked together a tiny benchmark doing only bpf_map_lookup_elem() and incrementing the value by 1 for PERCPU_ARRAY (arr-inc benchmark below) and PERCPU_HASH (hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar to PERCPU_ARRAY based on global variable array using bpf_get_smp_processor_id() to index array for current CPU (glob-arr-inc benchmark below).

BEFORE
======

glob-arr-inc   :  163.685 ± 0.092M/s
arr-inc        :  138.096 ± 0.160M/s
hash-inc       :   66.855 ± 0.123M/s

AFTER
=====

glob-arr-inc   :  173.921 ± 0.039M/s (+6%)
arr-inc        :  170.729 ± 0.210M/s (+23.7%)
hash-inc       :   68.673 ± 0.070M/s (+2.7%)

As can be seen, PERCPU_HASH gets a modest +2.7% improvement, while global array-based gets a nice +6% due to inlining of bpf_get_smp_processor_id().

But what's really important is that arr-inc benchmark basically catches up with glob-arr-inc, resulting in +23.7% improvement. This means that in practice it won't be necessary to avoid PERCPU_ARRAY anymore if performance is critical (e.g., high-frequent stats collection, which is often a practical use for PERCPU_ARRAY today).

v1->v2:
- use BPF_ALU64 | BPF_MOV instruction instead of LDX (Alexei);
- dropped the direct per-CPU memory read instruction, it can always be added

    back, if necessary;

- guarded bpf_get_smp_processor_id() behind x86-64 check (Alexei);
- switched all per-cpu addr casts to (unsigned long) to avoid sparse warnings.

Andrii Nakryiko (4):
bpf: add special internal-only MOV instruction to resolve per-CPU
addrs
bpf: inline bpf_get_smp_processor_id() helper
bpf: inline bpf_map_lookup_elem() for PERCPU_ARRAY maps
bpf: inline bpf_map_lookup_elem() helper for PERCPU_HASH map

 arch/x86/net/bpf_jit_comp.c | 16 ++++++++++++++++
 include/linux/filter.h      | 20 ++++++++++++++++++++
 kernel/bpf/arraymap.c       | 33 +++++++++++++++++++++++++++++++++
 kernel/bpf/core.c           |  5 +++++
 kernel/bpf/disasm.c         | 14 ++++++++++++++
 kernel/bpf/hashtab.c        | 21 +++++++++++++++++++++
 kernel/bpf/verifier.c       | 24 ++++++++++++++++++++++++
 7 files changed, 133 insertions(+)
Signature · 1 line
2.43.0
author maintainer
#1 lore raw

PATCH v2 1/4 bpf: add special internal-only MOV instruction to resolve per-CPU addrs

Add a new BPF instruction for resolving absolute addresses of per-CPU data from their per-CPU offsets. This instruction is internal-only and users are not allowed to use them directly. They will only be used for internal inlining optimizations for now between BPF verifier and BPF JITs.

We use a special BPF_MOV | BPF_ALU64 | BPF_X form with insn->off field set to BPF_ADDR_PERCPU = -1. I used negative offset value to distinguish them from positive ones used by user-exposed instructions.

Such instruction performs a resolution of a per-CPU offset stored in a register to a valid kernel address which can be dereferenced. It is useful in any use case where absolute address of a per-CPU data has to be resolved (e.g., in inlining bpf_map_lookup_elem()).

BPF disassembler is also taught to recognize them to support dumping final BPF assembly code (non-JIT'ed version).

Add arch-specific way for BPF JITs to mark support for this instructions.

This patch also adds support for these instructions in x86-64 BPF JIT.

---
 arch/x86/net/bpf_jit_comp.c | 16 ++++++++++++++++
 include/linux/filter.h      | 20 ++++++++++++++++++++
 kernel/bpf/core.c           |  5 +++++
 kernel/bpf/disasm.c         | 14 ++++++++++++++
 4 files changed, 55 insertions(+)
arch/x86/net/bpf_jit_comp.c +16 -0
index 3b639d6f2f54..af89dd117dce 100644
@@ -1382,6 +1382,17 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_image
 				maybe_emit_mod(&prog, AUX_REG, dst_reg, true);
 				EMIT3(0x0F, 0x44, add_2reg(0xC0, AUX_REG, dst_reg));
 				break;
+			} else if (insn_is_mov_percpu_addr(insn)) {
+				u32 off = (u32)(unsigned long)&this_cpu_off;
+
+				/* mov <dst>, <src> (if necessary) */
+				EMIT_mov(dst_reg, src_reg);
+
+				/* add <dst>, gs:[<off>] */
+				EMIT2(0x65, add_1mod(0x48, dst_reg));
+				EMIT3(0x03, add_1reg(0x04, dst_reg), 0x25);
+				EMIT(off, 4);
+				break;
 			}
 			fallthrough;
 		case BPF_ALU | BPF_MOV | BPF_X:
@@ -3365,6 +3376,11 @@ bool bpf_jit_supports_subprog_tailcalls(void)
 	return true;
 }
 
+bool bpf_jit_supports_percpu_insn(void)
+{
+	return true;
+}
+
 void bpf_jit_free(struct bpf_prog *prog)
 {
 	if (prog->jited) {
include/linux/filter.h +20 -0
index 44934b968b57..8bcfe6800400 100644
@@ -178,6 +178,25 @@ struct ctl_table_header;
 		.off   = 0,					\
 		.imm   = 0 })
 
+/* Special (internal-only) form of mov, used to resolve per-CPU addrs:
+ * dst_reg = src_reg + <percpu_base_off>
+ * BPF_ADDR_PERCPU is used as a special insn->off value.
+ */
+#define BPF_ADDR_PERCPU	(-1)
+
+#define BPF_MOV64_PERCPU_REG(DST, SRC)				\
+	((struct bpf_insn) {					\
+		.code  = BPF_ALU64 | BPF_MOV | BPF_X,		\
+		.dst_reg = DST,					\
+		.src_reg = SRC,					\
+		.off   = BPF_ADDR_PERCPU,			\
+		.imm   = 0 })
+
+static inline bool insn_is_mov_percpu_addr(const struct bpf_insn *insn)
+{
+	return insn->code == (BPF_ALU64 | BPF_MOV | BPF_X) && insn->off == BPF_ADDR_PERCPU;
+}
+
 /* Short form of mov, dst_reg = imm32 */
 
 #define BPF_MOV64_IMM(DST, IMM)					\
@@ -970,6 +989,7 @@ struct bpf_prog *bpf_int_jit_compile(struct bpf_prog *prog);
 void bpf_jit_compile(struct bpf_prog *prog);
 bool bpf_jit_needs_zext(void);
 bool bpf_jit_supports_subprog_tailcalls(void);
+bool bpf_jit_supports_percpu_insn(void);
 bool bpf_jit_supports_kfunc_call(void);
 bool bpf_jit_supports_far_kfunc_call(void);
 bool bpf_jit_supports_exceptions(void);
kernel/bpf/core.c +5 -0
index ab400cdd7d7a..a996fd8dd303 100644
@@ -2945,6 +2945,11 @@ bool __weak bpf_jit_supports_subprog_tailcalls(void)
 	return false;
 }
 
+bool __weak bpf_jit_supports_percpu_insn(void)
+{
+	return false;
+}
+
 bool __weak bpf_jit_supports_kfunc_call(void)
 {
 	return false;
kernel/bpf/disasm.c +14 -0
index bd2e2dd04740..309c4aa1b026 100644
@@ -172,6 +172,17 @@ static bool is_addr_space_cast(const struct bpf_insn *insn)
 		insn->off == BPF_ADDR_SPACE_CAST;
 }
 
+/* Special (internal-only) form of mov, used to resolve per-CPU addrs:
+ * dst_reg = src_reg + <percpu_base_off>
+ * BPF_ADDR_PERCPU is used as a special insn->off value.
+ */
+#define BPF_ADDR_PERCPU	(-1)
+
+static inline bool is_mov_percpu_addr(const struct bpf_insn *insn)
+{
+	return insn->code == (BPF_ALU64 | BPF_MOV | BPF_X) && insn->off == BPF_ADDR_PERCPU;
+}
+
 void print_bpf_insn(const struct bpf_insn_cbs *cbs,
 		    const struct bpf_insn *insn,
 		    bool allow_ptr_leaks)
@@ -194,6 +205,9 @@ void print_bpf_insn(const struct bpf_insn_cbs *cbs,
 			verbose(cbs->private_data, "(%02x) r%d = addr_space_cast(r%d, %d, %d)\n",
 				insn->code, insn->dst_reg,
 				insn->src_reg, ((u32)insn->imm) >> 16, (u16)insn->imm);
+		} else if (is_mov_percpu_addr(insn)) {
+			verbose(cbs->private_data, "(%02x) r%d = &(void __percpu *)(r%d)\n",
+				insn->code, insn->dst_reg, insn->src_reg);
 		} else if (BPF_SRC(insn->code) == BPF_X) {
 			verbose(cbs->private_data, "(%02x) %c%d %s %s%c%d\n",
 				insn->code, class == BPF_ALU ? 'w' : 'r',
Signature · 1 line
2.43.0
reviewer Acked-by on v2 1/4
#2 lore raw

RE: [PATCH v2 bpf-next 1/4] bpf: add special internal-only MOV instruction to resolve per-CPU addrs

Quoted 21 lines · Andrii Nakryiko

Add a new BPF instruction for resolving absolute addresses of per-CPU data from their per-CPU offsets. This instruction is internal-only and users are not allowed to use them directly. They will only be used for internal inlining optimizations for now between BPF verifier and BPF JITs.

We use a special BPF_MOV | BPF_ALU64 | BPF_X form with insn->off field set to BPF_ADDR_PERCPU = -1. I used negative offset value to distinguish them from positive ones used by user-exposed instructions.

Such instruction performs a resolution of a per-CPU offset stored in a register to a valid kernel address which can be dereferenced. It is useful in any use case where absolute address of a per-CPU data has to be resolved (e.g., in inlining bpf_map_lookup_elem()).

BPF disassembler is also taught to recognize them to support dumping final BPF assembly code (non-JIT'ed version).

Add arch-specific way for BPF JITs to mark support for this instructions.

This patch also adds support for these instructions in x86-64 BPF JIT.

Quoted 7 lines
---
 arch/x86/net/bpf_jit_comp.c | 16 ++++++++++++++++
 include/linux/filter.h      | 20 ++++++++++++++++++++
 kernel/bpf/core.c           |  5 +++++
 kernel/bpf/disasm.c         | 14 ++++++++++++++
 4 files changed, 55 insertions(+)

LGTM

#3 lore raw

Re: [PATCH v2 bpf-next 1/4] bpf: add special internal-only MOV instruction to resolve per-CPU addrs

In reply to Andrii Nakryiko
kernel test robot noticed the following build errors:

Hi Andrii,

kernel test robot noticed the following build errors:

[auto build test ERROR on bpf-next/master]

url:    https://github.com/intel-lab-lkp/linux/commits/Andrii-Nakryiko/bpf-add-special-internal-only-MOV-instruction-to-resolve-per-CPU-addrs/20240402-101450
base:   https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
patch link:    https://lore.kernel.org/r/20240402021307.1012571-2-andrii%40kernel.org
patch subject: [PATCH v2 bpf-next 1/4] bpf: add special internal-only MOV instruction to resolve per-CPU addrs
config: x86_64-randconfig-006-20240404 (https://download.01.org/0day-ci/archive/20240404/[email protected]/config)
compiler: gcc-10 (Ubuntu 10.5.0-1ubuntu1) 10.5.0
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20240404/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All errors (new ones prefixed by >>):

ld: arch/x86/net/bpf_jit_comp.o: in function `emit_code':

>> arch/x86/net/bpf_jit_comp.c:31:(.text+0xf2c3): undefined reference to `this_cpu_off'

vim +31 arch/x86/net/bpf_jit_comp.c

f18b03fabaa9b7 Kumar Kartikeya Dwivedi 2023-09-13  23  
5cccc702fd54e5 Joe Perches             2014-12-04  24  static u8 *emit_code(u8 *ptr, u32 bytes, unsigned int len)
0a14842f5a3c0e Eric Dumazet            2011-04-20  25  {
0a14842f5a3c0e Eric Dumazet            2011-04-20  26  	if (len == 1)
0a14842f5a3c0e Eric Dumazet            2011-04-20  27  		*ptr = bytes;
0a14842f5a3c0e Eric Dumazet            2011-04-20  28  	else if (len == 2)
0a14842f5a3c0e Eric Dumazet            2011-04-20  29  		*(u16 *)ptr = bytes;
0a14842f5a3c0e Eric Dumazet            2011-04-20  30  	else {
0a14842f5a3c0e Eric Dumazet            2011-04-20 @31  		*(u32 *)ptr = bytes;
0a14842f5a3c0e Eric Dumazet            2011-04-20  32  		barrier();
0a14842f5a3c0e Eric Dumazet            2011-04-20  33  	}
0a14842f5a3c0e Eric Dumazet            2011-04-20  34  	return ptr + len;
0a14842f5a3c0e Eric Dumazet            2011-04-20  35  }
0a14842f5a3c0e Eric Dumazet            2011-04-20  36  
Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
#4 lore raw

Re: [PATCH v2 bpf-next 1/4] bpf: add special internal-only MOV instruction to resolve per-CPU addrs

In reply to Andrii Nakryiko
kernel test robot noticed the following build errors:

Hi Andrii,

kernel test robot noticed the following build errors:

[auto build test ERROR on bpf-next/master]

url:    https://github.com/intel-lab-lkp/linux/commits/Andrii-Nakryiko/bpf-add-special-internal-only-MOV-instruction-to-resolve-per-CPU-addrs/20240402-101450
base:   https://git.kernel.org/pub/scm/linux/kernel/git/bpf/bpf-next.git master
patch link:    https://lore.kernel.org/r/20240402021307.1012571-2-andrii%40kernel.org
patch subject: [PATCH v2 bpf-next 1/4] bpf: add special internal-only MOV instruction to resolve per-CPU addrs
config: x86_64-randconfig-001-20240404 (https://download.01.org/0day-ci/archive/20240404/[email protected]/config)
compiler: clang version 17.0.6 (https://github.com/llvm/llvm-project 6009708b4367171ccdbf4b5905cb6a803753fe18)
reproduce (this is a W=1 build): (https://download.01.org/0day-ci/archive/20240404/[email protected]/reproduce)

If you fix the issue in a separate patch/commit (i.e. not just a new version of the same patch/commit), kindly add following tags
| Reported-by: kernel test robot <[email protected]>
| Closes: https://lore.kernel.org/oe-kbuild-all/[email protected]/

All errors (new ones prefixed by >>):

>> ld.lld: error: undefined symbol: this_cpu_off
   >>> referenced by bpf_jit_comp.c:31 (arch/x86/net/bpf_jit_comp.c:31)
   >>>               arch/x86/net/bpf_jit_comp.o:(do_jit) in archive vmlinux.a
Signature · 2 lines
0-DAY CI Kernel Test Service
https://github.com/intel/lkp-tests/wiki
author maintainer
#5 lore raw

PATCH v2 2/4 bpf: inline bpf_get_smp_processor_id() helper

In reply to Andrii Nakryiko

If BPF JIT supports per-CPU MOV instruction, inline bpf_get_smp_processor_id() to eliminate unnecessary function calls.

---
 kernel/bpf/verifier.c | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)
kernel/bpf/verifier.c +24 -0
index edb650667f44..af0274b090bb 100644
@@ -20072,6 +20072,30 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
 			goto next_insn;
 		}
 
+#ifdef CONFIG_X86_64
+		/* Implement bpf_get_smp_processor_id() inline. */
+		if (insn->imm == BPF_FUNC_get_smp_processor_id &&
+		    prog->jit_requested && bpf_jit_supports_percpu_insn()) {
+			/* BPF_FUNC_get_smp_processor_id inlining is an
+			 * optimization, so if pcpu_hot.cpu_number is ever
+			 * changed in some incompatible and hard to support
+			 * way, it's fine to back out this inlining logic
+			 */
+			insn_buf[0] = BPF_MOV32_IMM(BPF_REG_0, (u32)(unsigned long)&pcpu_hot.cpu_number);
+			insn_buf[1] = BPF_MOV64_PERCPU_REG(BPF_REG_0, BPF_REG_0);
+			insn_buf[2] = BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_0, 0);
+			cnt = 3;
+
+			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
+			if (!new_prog)
+				return -ENOMEM;
+
+			delta    += cnt - 1;
+			env->prog = prog = new_prog;
+			insn      = new_prog->insnsi + i + delta;
+			goto next_insn;
+		}
+#endif
 		/* Implement bpf_get_func_arg inline. */
 		if (prog_type == BPF_PROG_TYPE_TRACING &&
 		    insn->imm == BPF_FUNC_get_func_arg) {
Signature · 1 line
2.43.0
reviewer Acked-by on v2 2/4
#6 lore raw

RE: [PATCH v2 bpf-next 2/4] bpf: inline bpf_get_smp_processor_id() helper

Quoted 47 lines · Andrii Nakryiko

If BPF JIT supports per-CPU MOV instruction, inline bpf_get_smp_processor_id() to eliminate unnecessary function calls.

---
 kernel/bpf/verifier.c | 24 ++++++++++++++++++++++++
 1 file changed, 24 insertions(+)
kernel/bpf/verifier.c +24 -0
index edb650667f44..af0274b090bb 100644
@@ -20072,6 +20072,30 @@ static int do_misc_fixups(struct bpf_verifier_env *env)
 			goto next_insn;
 		}
 
+#ifdef CONFIG_X86_64
+		/* Implement bpf_get_smp_processor_id() inline. */
+		if (insn->imm == BPF_FUNC_get_smp_processor_id &&
+		    prog->jit_requested && bpf_jit_supports_percpu_insn()) {
+			/* BPF_FUNC_get_smp_processor_id inlining is an
+			 * optimization, so if pcpu_hot.cpu_number is ever
+			 * changed in some incompatible and hard to support
+			 * way, it's fine to back out this inlining logic
+			 */
+			insn_buf[0] = BPF_MOV32_IMM(BPF_REG_0, (u32)(unsigned long)&pcpu_hot.cpu_number);
+			insn_buf[1] = BPF_MOV64_PERCPU_REG(BPF_REG_0, BPF_REG_0);
+			insn_buf[2] = BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_0, 0);
+			cnt = 3;
+
+			new_prog = bpf_patch_insn_data(env, i + delta, insn_buf, cnt);
+			if (!new_prog)
+				return -ENOMEM;
+
+			delta    += cnt - 1;
+			env->prog = prog = new_prog;
+			insn      = new_prog->insnsi + i + delta;
+			goto next_insn;
+		}
+#endif
 		/* Implement bpf_get_func_arg inline. */
 		if (prog_type == BPF_PROG_TYPE_TRACING &&
 		    insn->imm == BPF_FUNC_get_func_arg) {
Signature · 1 line
2.43.0
author maintainer
#7 lore raw

PATCH v2 3/4 bpf: inline bpf_map_lookup_elem() for PERCPU_ARRAY maps

In reply to Andrii Nakryiko

Using new per-CPU BPF instruction implement inlining for per-CPU ARRAY map lookup helper, if BPF JIT support is present.

---
 kernel/bpf/arraymap.c | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)
kernel/bpf/arraymap.c +33 -0
index 13358675ff2e..8c1e6d7654bb 100644
@@ -246,6 +246,38 @@ static void *percpu_array_map_lookup_elem(struct bpf_map *map, void *key)
 	return this_cpu_ptr(array->pptrs[index & array->index_mask]);
 }
 
+/* emit BPF instructions equivalent to C code of percpu_array_map_lookup_elem() */
+static int percpu_array_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)
+{
+	struct bpf_array *array = container_of(map, struct bpf_array, map);
+	struct bpf_insn *insn = insn_buf;
+
+	if (!bpf_jit_supports_percpu_insn())
+		return -EOPNOTSUPP;
+
+	if (map->map_flags & BPF_F_INNER_MAP)
+		return -EOPNOTSUPP;
+
+	BUILD_BUG_ON(offsetof(struct bpf_array, map) != 0);
+	*insn++ = BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, offsetof(struct bpf_array, pptrs));
+
+	*insn++ = BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_2, 0);
+	if (!map->bypass_spec_v1) {
+		*insn++ = BPF_JMP_IMM(BPF_JGE, BPF_REG_0, map->max_entries, 6);
+		*insn++ = BPF_ALU32_IMM(BPF_AND, BPF_REG_0, array->index_mask);
+	} else {
+		*insn++ = BPF_JMP_IMM(BPF_JGE, BPF_REG_0, map->max_entries, 5);
+	}
+
+	*insn++ = BPF_ALU64_IMM(BPF_LSH, BPF_REG_0, 3);
+	*insn++ = BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1);
+	*insn++ = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0);
+	*insn++ = BPF_MOV64_PERCPU_REG(BPF_REG_0, BPF_REG_0);
+	*insn++ = BPF_JMP_IMM(BPF_JA, 0, 0, 1);
+	*insn++ = BPF_MOV64_IMM(BPF_REG_0, 0);
+	return insn - insn_buf;
+}
+
 static void *percpu_array_map_lookup_percpu_elem(struct bpf_map *map, void *key, u32 cpu)
 {
 	struct bpf_array *array = container_of(map, struct bpf_array, map);
@@ -776,6 +808,7 @@ const struct bpf_map_ops percpu_array_map_ops = {
 	.map_free = array_map_free,
 	.map_get_next_key = array_map_get_next_key,
 	.map_lookup_elem = percpu_array_map_lookup_elem,
+	.map_gen_lookup = percpu_array_map_gen_lookup,
 	.map_update_elem = array_map_update_elem,
 	.map_delete_elem = array_map_delete_elem,
 	.map_lookup_percpu_elem = percpu_array_map_lookup_percpu_elem,
Signature · 1 line
2.43.0
reviewer Acked-by on v2 3/4
#8 lore raw

RE: [PATCH v2 bpf-next 3/4] bpf: inline bpf_map_lookup_elem() for PERCPU_ARRAY maps

Quoted 13 lines · Andrii Nakryiko

Using new per-CPU BPF instruction implement inlining for per-CPU ARRAY map lookup helper, if BPF JIT support is present.

---
 kernel/bpf/arraymap.c | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)
kernel/bpf/arraymap.c +0 -0
index 13358675ff2e..8c1e6d7654bb 100644

kernel/bpf/arraymap.c static void *percpu_array_map_lookup_elem(struct bpf_map *map, void *key) · line 253

Quoted 8 lines
kernel/bpf/arraymap.c +5 -0
@@ -246,6 +246,38 @@ static void *percpu_array_map_lookup_elem(struct bpf_map *map, void *key)
 	return this_cpu_ptr(array->pptrs[index & array->index_mask]);
 }
 
+/* emit BPF instructions equivalent to C code of percpu_array_map_lookup_elem() */
+static int percpu_array_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)
+{
+	struct bpf_array *array = container_of(map, struct bpf_array, map);
+	struct bpf_insn *insn = insn_buf;

Nit, If you wanted to be consistent with array_*_map_gen_lookup,

	const int ret = BPF_REG_0;
	const int map_ptr = BPF_REG_1;
	const int index = BPF_REG_2;

But, I think its easier to read as is.

Quoted 31 lines
kernel/bpf/arraymap.c +27 -0
+
+	if (!bpf_jit_supports_percpu_insn())
+		return -EOPNOTSUPP;
+
+	if (map->map_flags & BPF_F_INNER_MAP)
+		return -EOPNOTSUPP;
+
+	BUILD_BUG_ON(offsetof(struct bpf_array, map) != 0);
+	*insn++ = BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, offsetof(struct bpf_array, pptrs));
+
+	*insn++ = BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_2, 0);
+	if (!map->bypass_spec_v1) {
+		*insn++ = BPF_JMP_IMM(BPF_JGE, BPF_REG_0, map->max_entries, 6);
+		*insn++ = BPF_ALU32_IMM(BPF_AND, BPF_REG_0, array->index_mask);
+	} else {
+		*insn++ = BPF_JMP_IMM(BPF_JGE, BPF_REG_0, map->max_entries, 5);
+	}
+
+	*insn++ = BPF_ALU64_IMM(BPF_LSH, BPF_REG_0, 3);
+	*insn++ = BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1);
+	*insn++ = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0);
+	*insn++ = BPF_MOV64_PERCPU_REG(BPF_REG_0, BPF_REG_0);
+	*insn++ = BPF_JMP_IMM(BPF_JA, 0, 0, 1);
+	*insn++ = BPF_MOV64_IMM(BPF_REG_0, 0);
+	return insn - insn_buf;
+}
+
 static void *percpu_array_map_lookup_percpu_elem(struct bpf_map *map, void *key, u32 cpu)
 {
 	struct bpf_array *array = container_of(map, struct bpf_array, map);

kernel/bpf/arraymap.c const struct bpf_map_ops percpu_array_map_ops = { · line 814

Quoted 7 lines
kernel/bpf/arraymap.c +1 -0
@@ -776,6 +808,7 @@ const struct bpf_map_ops percpu_array_map_ops = {
 	.map_free = array_map_free,
 	.map_get_next_key = array_map_get_next_key,
 	.map_lookup_elem = percpu_array_map_lookup_elem,
+	.map_gen_lookup = percpu_array_map_gen_lookup,
 	.map_update_elem = array_map_update_elem,
 	.map_delete_elem = array_map_delete_elem,
 	.map_lookup_percpu_elem = percpu_array_map_lookup_percpu_elem,
#9 lore raw

Re: [PATCH v2 bpf-next 3/4] bpf: inline bpf_map_lookup_elem() for PERCPU_ARRAY maps

Quoted 18 lines · John Fastabend
Quoted 16 lines · Andrii Nakryiko

Using new per-CPU BPF instruction implement inlining for per-CPU ARRAY map lookup helper, if BPF JIT support is present.

---
 kernel/bpf/arraymap.c | 33 +++++++++++++++++++++++++++++++++
 1 file changed, 33 insertions(+)
kernel/bpf/arraymap.c +0 -0
index 13358675ff2e..8c1e6d7654bb 100644
@@ -246,6 +246,38 @@ static void *percpu_array_map_lookup_elem(struct bpf_map *map, void *key)
      return this_cpu_ptr(array->pptrs[index & array->index_mask]);
 }
 
Quoted 8 lines

kernel/bpf/arraymap.c static void *percpu_array_map_lookup_elem(struct bpf_map *map, void *key) · line 253

Quoted 5 lines
kernel/bpf/arraymap.c +5 -0
+/* emit BPF instructions equivalent to C code of percpu_array_map_lookup_elem() */
+static int percpu_array_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)
+{
+     struct bpf_array *array = container_of(map, struct bpf_array, map);
+     struct bpf_insn *insn = insn_buf;

Nit, If you wanted to be consistent with array_*_map_gen_lookup,

I didn't in this case, I found these "aliases" more confusing than helpful.

Quoted 6 lines
        const int ret = BPF_REG_0;
        const int map_ptr = BPF_REG_1;
        const int index = BPF_REG_2;

But, I think its easier to read as is.

Yep, that's what I thought as well.

Quoted 40 lines
Quoted 31 lines
kernel/bpf/arraymap.c +27 -0
+
+     if (!bpf_jit_supports_percpu_insn())
+             return -EOPNOTSUPP;
+
+     if (map->map_flags & BPF_F_INNER_MAP)
+             return -EOPNOTSUPP;
+
+     BUILD_BUG_ON(offsetof(struct bpf_array, map) != 0);
+     *insn++ = BPF_ALU64_IMM(BPF_ADD, BPF_REG_1, offsetof(struct bpf_array, pptrs));
+
+     *insn++ = BPF_LDX_MEM(BPF_W, BPF_REG_0, BPF_REG_2, 0);
+     if (!map->bypass_spec_v1) {
+             *insn++ = BPF_JMP_IMM(BPF_JGE, BPF_REG_0, map->max_entries, 6);
+             *insn++ = BPF_ALU32_IMM(BPF_AND, BPF_REG_0, array->index_mask);
+     } else {
+             *insn++ = BPF_JMP_IMM(BPF_JGE, BPF_REG_0, map->max_entries, 5);
+     }
+
+     *insn++ = BPF_ALU64_IMM(BPF_LSH, BPF_REG_0, 3);
+     *insn++ = BPF_ALU64_REG(BPF_ADD, BPF_REG_0, BPF_REG_1);
+     *insn++ = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0);
+     *insn++ = BPF_MOV64_PERCPU_REG(BPF_REG_0, BPF_REG_0);
+     *insn++ = BPF_JMP_IMM(BPF_JA, 0, 0, 1);
+     *insn++ = BPF_MOV64_IMM(BPF_REG_0, 0);
+     return insn - insn_buf;
+}
+
 static void *percpu_array_map_lookup_percpu_elem(struct bpf_map *map, void *key, u32 cpu)
 {
      struct bpf_array *array = container_of(map, struct bpf_array, map);

kernel/bpf/arraymap.c const struct bpf_map_ops percpu_array_map_ops = { · line 814

Quoted 7 lines
kernel/bpf/arraymap.c +1 -0
@@ -776,6 +808,7 @@ const struct bpf_map_ops percpu_array_map_ops = {
      .map_free = array_map_free,
      .map_get_next_key = array_map_get_next_key,
      .map_lookup_elem = percpu_array_map_lookup_elem,
+     .map_gen_lookup = percpu_array_map_gen_lookup,
      .map_update_elem = array_map_update_elem,
      .map_delete_elem = array_map_delete_elem,
      .map_lookup_percpu_elem = percpu_array_map_lookup_percpu_elem,
author maintainer
#10 lore raw

PATCH v2 4/4 bpf: inline bpf_map_lookup_elem() helper for PERCPU_HASH map

In reply to Andrii Nakryiko

Using new per-CPU BPF instruction, partially inline bpf_map_lookup_elem() helper for per-CPU hashmap BPF map. Just like for normal HASH map, we still generate a call into __htab_map_lookup_elem(), but after that we resolve per-CPU element address using a new instruction, saving on extra functions calls.

---
 kernel/bpf/hashtab.c | 21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)
kernel/bpf/hashtab.c +21 -0
index e81059faae63..83a9a74260e9 100644
@@ -2308,6 +2308,26 @@ static void *htab_percpu_map_lookup_elem(struct bpf_map *map, void *key)
 		return NULL;
 }
 
+/* inline bpf_map_lookup_elem() call for per-CPU hashmap */
+static int htab_percpu_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)
+{
+	struct bpf_insn *insn = insn_buf;
+
+	if (!bpf_jit_supports_percpu_insn())
+		return -EOPNOTSUPP;
+
+	BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem,
+		     (void *(*)(struct bpf_map *map, void *key))NULL));
+	*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
+	*insn++ = BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 3);
+	*insn++ = BPF_ALU64_IMM(BPF_ADD, BPF_REG_0,
+				offsetof(struct htab_elem, key) + map->key_size);
+	*insn++ = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0);
+	*insn++ = BPF_MOV64_PERCPU_REG(BPF_REG_0, BPF_REG_0);
+
+	return insn - insn_buf;
+}
+
 static void *htab_percpu_map_lookup_percpu_elem(struct bpf_map *map, void *key, u32 cpu)
 {
 	struct htab_elem *l;
@@ -2436,6 +2456,7 @@ const struct bpf_map_ops htab_percpu_map_ops = {
 	.map_free = htab_map_free,
 	.map_get_next_key = htab_map_get_next_key,
 	.map_lookup_elem = htab_percpu_map_lookup_elem,
+	.map_gen_lookup = htab_percpu_map_gen_lookup,
 	.map_lookup_and_delete_elem = htab_percpu_map_lookup_and_delete_elem,
 	.map_update_elem = htab_percpu_map_update_elem,
 	.map_delete_elem = htab_map_delete_elem,
Signature · 1 line
2.43.0
reviewer Acked-by on v2 4/4
#11 lore raw

RE: [PATCH v2 bpf-next 4/4] bpf: inline bpf_map_lookup_elem() helper for PERCPU_HASH map

Quoted 43 lines · Andrii Nakryiko

Using new per-CPU BPF instruction, partially inline bpf_map_lookup_elem() helper for per-CPU hashmap BPF map. Just like for normal HASH map, we still generate a call into __htab_map_lookup_elem(), but after that we resolve per-CPU element address using a new instruction, saving on extra functions calls.

---
 kernel/bpf/hashtab.c | 21 +++++++++++++++++++++
 1 file changed, 21 insertions(+)
kernel/bpf/hashtab.c +20 -0
index e81059faae63..83a9a74260e9 100644
@@ -2308,6 +2308,26 @@ static void *htab_percpu_map_lookup_elem(struct bpf_map *map, void *key)
 		return NULL;
 }
 
+/* inline bpf_map_lookup_elem() call for per-CPU hashmap */
+static int htab_percpu_map_gen_lookup(struct bpf_map *map, struct bpf_insn *insn_buf)
+{
+	struct bpf_insn *insn = insn_buf;
+
+	if (!bpf_jit_supports_percpu_insn())
+		return -EOPNOTSUPP;
+
+	BUILD_BUG_ON(!__same_type(&__htab_map_lookup_elem,
+		     (void *(*)(struct bpf_map *map, void *key))NULL));
+	*insn++ = BPF_EMIT_CALL(__htab_map_lookup_elem);
+	*insn++ = BPF_JMP_IMM(BPF_JEQ, BPF_REG_0, 0, 3);
+	*insn++ = BPF_ALU64_IMM(BPF_ADD, BPF_REG_0,
+				offsetof(struct htab_elem, key) + map->key_size);
+	*insn++ = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0);
+	*insn++ = BPF_MOV64_PERCPU_REG(BPF_REG_0, BPF_REG_0);
+
+	return insn - insn_buf;
+}
+
 static void *htab_percpu_map_lookup_percpu_elem(struct bpf_map *map, void *key, u32 cpu)
 {
 	struct htab_elem *l;

kernel/bpf/hashtab.c const struct bpf_map_ops htab_percpu_map_ops = { · line 2462

Quoted 7 lines
kernel/bpf/hashtab.c +1 -0
@@ -2436,6 +2456,7 @@ const struct bpf_map_ops htab_percpu_map_ops = {
 	.map_free = htab_map_free,
 	.map_get_next_key = htab_map_get_next_key,
 	.map_lookup_elem = htab_percpu_map_lookup_elem,
+	.map_gen_lookup = htab_percpu_map_gen_lookup,
 	.map_lookup_and_delete_elem = htab_percpu_map_lookup_and_delete_elem,
 	.map_update_elem = htab_percpu_map_update_elem,
 	.map_delete_elem = htab_map_delete_elem,

Thanks I'll test on Tetragon as well to see if we can see some perf improvement we have a few per cpu maps int here as well.

#12 lore raw
In reply to Andrii Nakryiko
Quoted 37 lines · Andrii Nakryiko

Add a new BPF instruction for resolving per-CPU memory addresses.

New instruction is a special form of BPF_ALU64 | BPF_MOV | BPF_DW, with insns->off set to BPF_ADDR_PERCPU (== -1). It resolves provided per-CPU offset to an absolute address where per-CPU data resides for "this" CPU.

This patch set implements support for it in x86-64 BPF JIT only.

Using the new instruction, we also implement inlining for three cases:
- bpf_get_smp_processor_id(), which allows to avoid unnecessary trivial function call, saving a bit of performance and also not polluting LBR records with unnecessary function call/return records;
- PERCPU_ARRAY's bpf_map_lookup_elem() is completely inlined, bringing its performance to implementing per-CPU data structures using global variables in BPF (which is an awesome improvement, see benchmarks below);
- PERCPU_HASH's bpf_map_lookup_elem() is partially inlined, just like the same for non-PERCPU HASH map; this still saves a bit of overhead.

To validate performance benefits, I hacked together a tiny benchmark doing only bpf_map_lookup_elem() and incrementing the value by 1 for PERCPU_ARRAY (arr-inc benchmark below) and PERCPU_HASH (hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar to PERCPU_ARRAY based on global variable array using bpf_get_smp_processor_id() to index array for current CPU (glob-arr-inc benchmark below).

BEFORE
======

glob-arr-inc   :  163.685 ± 0.092M/s
arr-inc        :  138.096 ± 0.160M/s
hash-inc       :   66.855 ± 0.123M/s

AFTER
=====

glob-arr-inc   :  173.921 ± 0.039M/s (+6%)
arr-inc        :  170.729 ± 0.210M/s (+23.7%)
hash-inc       :   68.673 ± 0.070M/s (+2.7%)
Quoted 8 lines

As can be seen, PERCPU_HASH gets a modest +2.7% improvement, while global array-based gets a nice +6% due to inlining of bpf_get_smp_processor_id().

But what's really important is that arr-inc benchmark basically catches up with glob-arr-inc, resulting in +23.7% improvement. This means that in practice it won't be necessary to avoid PERCPU_ARRAY anymore if performance is critical (e.g., high-frequent stats collection, which is often a practical use for PERCPU_ARRAY today).

Out of curiousity did we consider exposing this instruction outside internal inlining? It seems it would help compiler some to not believe its doing a function call.

We could do some runtime rewrites to find the address for global vars for example.

FWIW I don't think one should block this necessarily perhaps as follow up? Or at least worth considering if I didn't miss some reason its not plausible.

Quoted 29 lines

v1->v2:
- use BPF_ALU64 | BPF_MOV instruction instead of LDX (Alexei);
- dropped the direct per-CPU memory read instruction, it can always be added

    back, if necessary;

- guarded bpf_get_smp_processor_id() behind x86-64 check (Alexei);
- switched all per-cpu addr casts to (unsigned long) to avoid sparse warnings.

Andrii Nakryiko (4):
bpf: add special internal-only MOV instruction to resolve per-CPU
addrs
bpf: inline bpf_get_smp_processor_id() helper
bpf: inline bpf_map_lookup_elem() for PERCPU_ARRAY maps
bpf: inline bpf_map_lookup_elem() helper for PERCPU_HASH map

 arch/x86/net/bpf_jit_comp.c | 16 ++++++++++++++++
 include/linux/filter.h      | 20 ++++++++++++++++++++
 kernel/bpf/arraymap.c       | 33 +++++++++++++++++++++++++++++++++
 kernel/bpf/core.c           |  5 +++++
 kernel/bpf/disasm.c         | 14 ++++++++++++++
 kernel/bpf/hashtab.c        | 21 +++++++++++++++++++++
 kernel/bpf/verifier.c       | 24 ++++++++++++++++++++++++
 7 files changed, 133 insertions(+)
Signature · 1 line
2.43.0
#13 lore raw
Quoted 48 lines · John Fastabend
Quoted 37 lines · Andrii Nakryiko

Add a new BPF instruction for resolving per-CPU memory addresses.

New instruction is a special form of BPF_ALU64 | BPF_MOV | BPF_DW, with insns->off set to BPF_ADDR_PERCPU (== -1). It resolves provided per-CPU offset to an absolute address where per-CPU data resides for "this" CPU.

This patch set implements support for it in x86-64 BPF JIT only.

Using the new instruction, we also implement inlining for three cases:
- bpf_get_smp_processor_id(), which allows to avoid unnecessary trivial function call, saving a bit of performance and also not polluting LBR records with unnecessary function call/return records;
- PERCPU_ARRAY's bpf_map_lookup_elem() is completely inlined, bringing its performance to implementing per-CPU data structures using global variables in BPF (which is an awesome improvement, see benchmarks below);
- PERCPU_HASH's bpf_map_lookup_elem() is partially inlined, just like the same for non-PERCPU HASH map; this still saves a bit of overhead.

To validate performance benefits, I hacked together a tiny benchmark doing only bpf_map_lookup_elem() and incrementing the value by 1 for PERCPU_ARRAY (arr-inc benchmark below) and PERCPU_HASH (hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar to PERCPU_ARRAY based on global variable array using bpf_get_smp_processor_id() to index array for current CPU (glob-arr-inc benchmark below).

BEFORE
======

glob-arr-inc   :  163.685 ± 0.092M/s
arr-inc        :  138.096 ± 0.160M/s
hash-inc       :   66.855 ± 0.123M/s

AFTER
=====

glob-arr-inc   :  173.921 ± 0.039M/s (+6%)
arr-inc        :  170.729 ± 0.210M/s (+23.7%)
hash-inc       :   68.673 ± 0.070M/s (+2.7%)
Quoted 8 lines

As can be seen, PERCPU_HASH gets a modest +2.7% improvement, while global array-based gets a nice +6% due to inlining of bpf_get_smp_processor_id().

But what's really important is that arr-inc benchmark basically catches up with glob-arr-inc, resulting in +23.7% improvement. This means that in practice it won't be necessary to avoid PERCPU_ARRAY anymore if performance is critical (e.g., high-frequent stats collection, which is often a practical use for PERCPU_ARRAY today).

Quoted 3 lines

Out of curiousity did we consider exposing this instruction outside internal inlining? It seems it would help compiler some to not believe its doing a function call.

We decided to start as internal-only to try it out and get inlining benefits, without being stuck in a longer discussion to define the exact user-visible semantics, guarantees, etc. Given this instruction calculates memory addresses that are meant to be dereferenced directly, we'd need to be careful to make sure all the safety aspects are carefully considered.

Though you reminded me that we should probably also implement inlining of bpf_this_cpu_ptr() and maybe even bpf_per_cpu_ptr() (I'll need to double-check how arbitrary CPU address is calculated). Maybe as a follow up.

Quoted 7 lines

We could do some runtime rewrites to find the address for global vars for example.

FWIW I don't think one should block this necessarily perhaps as follow up? Or at least worth considering if I didn't miss some reason its not plausible.

No blocker in principle, but certainly we'd need to be more careful if we expose the instruction to users.

Quoted 32 lines
Quoted 30 lines

v1->v2:
- use BPF_ALU64 | BPF_MOV instruction instead of LDX (Alexei);
- dropped the direct per-CPU memory read instruction, it can always be added

    back, if necessary;

- guarded bpf_get_smp_processor_id() behind x86-64 check (Alexei);
- switched all per-cpu addr casts to (unsigned long) to avoid sparse warnings.

Andrii Nakryiko (4):
bpf: add special internal-only MOV instruction to resolve per-CPU
addrs
bpf: inline bpf_get_smp_processor_id() helper
bpf: inline bpf_map_lookup_elem() for PERCPU_ARRAY maps
bpf: inline bpf_map_lookup_elem() helper for PERCPU_HASH map

 arch/x86/net/bpf_jit_comp.c | 16 ++++++++++++++++
 include/linux/filter.h      | 20 ++++++++++++++++++++
 kernel/bpf/arraymap.c       | 33 +++++++++++++++++++++++++++++++++
 kernel/bpf/core.c           |  5 +++++
 kernel/bpf/disasm.c         | 14 ++++++++++++++
 kernel/bpf/hashtab.c        | 21 +++++++++++++++++++++
 kernel/bpf/verifier.c       | 24 ++++++++++++++++++++++++
 7 files changed, 133 insertions(+)

--
2.43.0

reviewer Reviewed-by Tested-by
#14 lore raw
Quoted 69 lines · Andrii Nakryiko
Quoted 48 lines · John Fastabend
Quoted 37 lines · Andrii Nakryiko

Add a new BPF instruction for resolving per-CPU memory addresses.

New instruction is a special form of BPF_ALU64 | BPF_MOV | BPF_DW, with insns->off set to BPF_ADDR_PERCPU (== -1). It resolves provided per-CPU offset to an absolute address where per-CPU data resides for "this" CPU.

This patch set implements support for it in x86-64 BPF JIT only.

Using the new instruction, we also implement inlining for three cases:
- bpf_get_smp_processor_id(), which allows to avoid unnecessary trivial function call, saving a bit of performance and also not polluting LBR records with unnecessary function call/return records;
- PERCPU_ARRAY's bpf_map_lookup_elem() is completely inlined, bringing its performance to implementing per-CPU data structures using global variables in BPF (which is an awesome improvement, see benchmarks below);
- PERCPU_HASH's bpf_map_lookup_elem() is partially inlined, just like the same for non-PERCPU HASH map; this still saves a bit of overhead.

To validate performance benefits, I hacked together a tiny benchmark doing only bpf_map_lookup_elem() and incrementing the value by 1 for PERCPU_ARRAY (arr-inc benchmark below) and PERCPU_HASH (hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar to PERCPU_ARRAY based on global variable array using bpf_get_smp_processor_id() to index array for current CPU (glob-arr-inc benchmark below).

BEFORE
======

glob-arr-inc   :  163.685 ± 0.092M/s
arr-inc        :  138.096 ± 0.160M/s
hash-inc       :   66.855 ± 0.123M/s

AFTER
=====

glob-arr-inc   :  173.921 ± 0.039M/s (+6%)
arr-inc        :  170.729 ± 0.210M/s (+23.7%)
hash-inc       :   68.673 ± 0.070M/s (+2.7%)
Quoted 8 lines

As can be seen, PERCPU_HASH gets a modest +2.7% improvement, while global array-based gets a nice +6% due to inlining of bpf_get_smp_processor_id().

But what's really important is that arr-inc benchmark basically catches up with glob-arr-inc, resulting in +23.7% improvement. This means that in practice it won't be necessary to avoid PERCPU_ARRAY anymore if performance is critical (e.g., high-frequent stats collection, which is often a practical use for PERCPU_ARRAY today).

Quoted 3 lines

Out of curiousity did we consider exposing this instruction outside internal inlining? It seems it would help compiler some to not believe its doing a function call.

We decided to start as internal-only to try it out and get inlining benefits, without being stuck in a longer discussion to define the exact user-visible semantics, guarantees, etc. Given this instruction calculates memory addresses that are meant to be dereferenced directly, we'd need to be careful to make sure all the safety aspects are carefully considered.

Though you reminded me that we should probably also implement inlining of bpf_this_cpu_ptr() and maybe even bpf_per_cpu_ptr() (I'll need to double-check how arbitrary CPU address is calculated). Maybe as a follow up.

Quoted 4 lines

We could do some runtime rewrites to find the address for global vars for example.

Quoted 6 lines
Quoted 3 lines

FWIW I don't think one should block this necessarily perhaps as follow up? Or at least worth considering if I didn't miss some reason its not plausible.

No blocker in principle, but certainly we'd need to be more careful if we expose the instruction to users.

All sounds good that was my understanding as well.

I see it got merged but for what its worth I went through and ran some of this and rest of patches lgtm,

Quoted 33 lines
Quoted 33 lines
Quoted 31 lines

v1->v2:
- use BPF_ALU64 | BPF_MOV instruction instead of LDX (Alexei);
- dropped the direct per-CPU memory read instruction, it can always be added

    back, if necessary;

- guarded bpf_get_smp_processor_id() behind x86-64 check (Alexei);
- switched all per-cpu addr casts to (unsigned long) to avoid sparse warnings.

Andrii Nakryiko (4):
bpf: add special internal-only MOV instruction to resolve per-CPU
addrs
bpf: inline bpf_get_smp_processor_id() helper
bpf: inline bpf_map_lookup_elem() for PERCPU_ARRAY maps
bpf: inline bpf_map_lookup_elem() helper for PERCPU_HASH map

 arch/x86/net/bpf_jit_comp.c | 16 ++++++++++++++++
 include/linux/filter.h      | 20 ++++++++++++++++++++
 kernel/bpf/arraymap.c       | 33 +++++++++++++++++++++++++++++++++
 kernel/bpf/core.c           |  5 +++++
 kernel/bpf/disasm.c         | 14 ++++++++++++++
 kernel/bpf/hashtab.c        | 21 +++++++++++++++++++++
 kernel/bpf/verifier.c       | 24 ++++++++++++++++++++++++
 7 files changed, 133 insertions(+)

--
2.43.0

#15 lore raw
In reply to Andrii Nakryiko
This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Hello:

This series was applied to bpf/bpf-next.git (master) by Alexei Starovoitov <[email protected]>:

Quoted 9 lines · On Mon, 1 Apr 2024 19:13:01 -0700 you wrote:

Add a new BPF instruction for resolving per-CPU memory addresses.

New instruction is a special form of BPF_ALU64 | BPF_MOV | BPF_DW, with insns->off set to BPF_ADDR_PERCPU (== -1). It resolves provided per-CPU offset to an absolute address where per-CPU data resides for "this" CPU.

This patch set implements support for it in x86-64 BPF JIT only.

[...]

Here is the summary with links:
- [v2,bpf-next,1/4] bpf: add special internal-only MOV instruction to resolve per-CPU addrs

    https://git.kernel.org/bpf/bpf-next/c/7bdbf7446305
  - [v2,bpf-next,2/4] bpf: inline bpf_get_smp_processor_id() helper
    https://git.kernel.org/bpf/bpf-next/c/1ae6921009e5
  - [v2,bpf-next,3/4] bpf: inline bpf_map_lookup_elem() for PERCPU_ARRAY maps
    https://git.kernel.org/bpf/bpf-next/c/db69718b8efa
  - [v2,bpf-next,4/4] bpf: inline bpf_map_lookup_elem() helper for PERCPU_HASH map
    https://git.kernel.org/bpf/bpf-next/c/0b56e637f705

You are awesome, thank you!

Signature · 2 lines
Deet-doot-dot, I am a bot.
https://korg.docs.kernel.org/patchwork/pwbot.html
#16 lore raw
In reply to Andrii Nakryiko
Quoted 6 lines · Andrii Nakryiko

Add a new BPF instruction for resolving per-CPU memory addresses.

New instruction is a special form of BPF_ALU64 | BPF_MOV | BPF_DW, with insns->off set to BPF_ADDR_PERCPU (== -1). It resolves provided per-CPU offset to an absolute address where per-CPU data resides for "this" CPU.

Fixed the typo s/BPF_DW/BPF_X/ while applying.

I'm still a bit worried that there is no BUILD_BUG_ON for 32-bit archs while both array and htab perpu gen_lookup assume sizeof(void*) == 8 in few places:
htab:

        *insn++ = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0);

array:

        *insn++ = BPF_ALU64_IMM(BPF_LSH, BPF_REG_0, 3);
        *insn++ = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0);

Worth following up or I'm overthinking this?

#17 lore raw
Quoted 10 lines · Alexei Starovoitov
Quoted 6 lines · Andrii Nakryiko

Add a new BPF instruction for resolving per-CPU memory addresses.

New instruction is a special form of BPF_ALU64 | BPF_MOV | BPF_DW, with insns->off set to BPF_ADDR_PERCPU (== -1). It resolves provided per-CPU offset to an absolute address where per-CPU data resides for "this" CPU.

Fixed the typo s/BPF_DW/BPF_X/ while applying.

Oops, thanks!

Quoted 2 lines

I'm still a bit worried that there is no BUILD_BUG_ON

BUILD_BUG_ON is problematic, because those gen_lookup callbacks are compiled on 32-bit arches just fine (just not used). I'm totally fine adding extra checks as a follow up. Let's just agree on some consistent approach her?

See [0] for the verifier check I mentioned. I can

a) add #ifdef guards around all current gen_lookup callbacks to only build them on 64-bit arches

or

b) add runtime checks inside get_lookup to return -EOPNOTSUPP if architecture isn't 64-bit.

I don't particularly care which one, I care that it's done for all callbacks if we are doing this. Please let me know your preference.

[0] https://github.com/torvalds/linux/blob/master/kernel/bpf/verifier.c#L19942-L19946

Quoted 9 lines

for 32-bit archs while both array and htab perpu gen_lookup assume sizeof(void*) == 8 in few places:
htab:

        *insn++ = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0);

array:

        *insn++ = BPF_ALU64_IMM(BPF_LSH, BPF_REG_0, 3);
        *insn++ = BPF_LDX_MEM(BPF_DW, BPF_REG_0, BPF_REG_0, 0);

Worth following up or I'm overthinking this?

I don't know, maybe? :) See above.

#18 lore raw
Quoted 31 lines · Andrii Nakryiko
Quoted 10 lines · Alexei Starovoitov
Quoted 6 lines · Andrii Nakryiko

Add a new BPF instruction for resolving per-CPU memory addresses.

New instruction is a special form of BPF_ALU64 | BPF_MOV | BPF_DW, with insns->off set to BPF_ADDR_PERCPU (== -1). It resolves provided per-CPU offset to an absolute address where per-CPU data resides for "this" CPU.

Fixed the typo s/BPF_DW/BPF_X/ while applying.

Oops, thanks!

Quoted 2 lines

I'm still a bit worried that there is no BUILD_BUG_ON

BUILD_BUG_ON is problematic, because those gen_lookup callbacks are compiled on 32-bit arches just fine (just not used). I'm totally fine adding extra checks as a follow up. Let's just agree on some consistent approach her?

See [0] for the verifier check I mentioned. I can

a) add #ifdef guards around all current gen_lookup callbacks to only build them on 64-bit arches

or

Quoted 7 lines

b) add runtime checks inside get_lookup to return -EOPNOTSUPP if architecture isn't 64-bit.

I don't particularly care which one, I care that it's done for all callbacks if we are doing this. Please let me know your preference.

[0] https://github.com/torvalds/linux/blob/master/kernel/bpf/verifier.c#L19942-L19946

Ahh. BITS_PER_LONG == 64 check is for a different reason, but that works. It won't be lifted any time soon,
so not worried any more about that assumption inside gen_lookup. Let's keep things as-is.

#19 lore raw
In reply to Andrii Nakryiko
Quoted 71 lines · Andrii Nakryiko

Add a new BPF instruction for resolving per-CPU memory addresses.

New instruction is a special form of BPF_ALU64 | BPF_MOV | BPF_DW, with insns->off set to BPF_ADDR_PERCPU (== -1). It resolves provided per-CPU offset to an absolute address where per-CPU data resides for "this" CPU.

This patch set implements support for it in x86-64 BPF JIT only.

Using the new instruction, we also implement inlining for three cases:
- bpf_get_smp_processor_id(), which allows to avoid unnecessary trivial function call, saving a bit of performance and also not polluting LBR records with unnecessary function call/return records;
- PERCPU_ARRAY's bpf_map_lookup_elem() is completely inlined, bringing its performance to implementing per-CPU data structures using global variables in BPF (which is an awesome improvement, see benchmarks below);
- PERCPU_HASH's bpf_map_lookup_elem() is partially inlined, just like the same for non-PERCPU HASH map; this still saves a bit of overhead.

To validate performance benefits, I hacked together a tiny benchmark doing only bpf_map_lookup_elem() and incrementing the value by 1 for PERCPU_ARRAY (arr-inc benchmark below) and PERCPU_HASH (hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar to PERCPU_ARRAY based on global variable array using bpf_get_smp_processor_id() to index array for current CPU (glob-arr-inc benchmark below).

BEFORE
======

glob-arr-inc   :  163.685 ± 0.092M/s
arr-inc        :  138.096 ± 0.160M/s
hash-inc       :   66.855 ± 0.123M/s

AFTER
=====

glob-arr-inc   :  173.921 ± 0.039M/s (+6%)
arr-inc        :  170.729 ± 0.210M/s (+23.7%)
hash-inc       :   68.673 ± 0.070M/s (+2.7%)

As can be seen, PERCPU_HASH gets a modest +2.7% improvement, while global array-based gets a nice +6% due to inlining of bpf_get_smp_processor_id().

But what's really important is that arr-inc benchmark basically catches up with glob-arr-inc, resulting in +23.7% improvement. This means that in practice it won't be necessary to avoid PERCPU_ARRAY anymore if performance is critical (e.g., high-frequent stats collection, which is often a practical use for PERCPU_ARRAY today).

v1->v2:
- use BPF_ALU64 | BPF_MOV instruction instead of LDX (Alexei);
- dropped the direct per-CPU memory read instruction, it can always be added

    back, if necessary;

- guarded bpf_get_smp_processor_id() behind x86-64 check (Alexei);
- switched all per-cpu addr casts to (unsigned long) to avoid sparse warnings.

Andrii Nakryiko (4):
bpf: add special internal-only MOV instruction to resolve per-CPU
addrs
bpf: inline bpf_get_smp_processor_id() helper
bpf: inline bpf_map_lookup_elem() for PERCPU_ARRAY maps
bpf: inline bpf_map_lookup_elem() helper for PERCPU_HASH map

 arch/x86/net/bpf_jit_comp.c | 16 ++++++++++++++++
 include/linux/filter.h      | 20 ++++++++++++++++++++
 kernel/bpf/arraymap.c       | 33 +++++++++++++++++++++++++++++++++
 kernel/bpf/core.c           |  5 +++++
 kernel/bpf/disasm.c         | 14 ++++++++++++++
 kernel/bpf/hashtab.c        | 21 +++++++++++++++++++++
 kernel/bpf/verifier.c       | 24 ++++++++++++++++++++++++
 7 files changed, 133 insertions(+)
Quoted 3 lines

--
2.43.0

Puranjay, Pu,

Is this something you guys can help implement for ARM64 and RISC-V architectures as well? I'm lacking the knowledge of the specifics of this architecture to be able to do this by myself, but it is a nice improvement for BPF applications, so it would be nice to get wide architecture support.

Thank you!

#20 lore raw
Quoted 79 lines · Andrii Nakryiko
Quoted 71 lines · Andrii Nakryiko

Add a new BPF instruction for resolving per-CPU memory addresses.

New instruction is a special form of BPF_ALU64 | BPF_MOV | BPF_DW, with insns->off set to BPF_ADDR_PERCPU (== -1). It resolves provided per-CPU offset to an absolute address where per-CPU data resides for "this" CPU.

This patch set implements support for it in x86-64 BPF JIT only.

Using the new instruction, we also implement inlining for three cases:
- bpf_get_smp_processor_id(), which allows to avoid unnecessary trivial function call, saving a bit of performance and also not polluting LBR records with unnecessary function call/return records;
- PERCPU_ARRAY's bpf_map_lookup_elem() is completely inlined, bringing its performance to implementing per-CPU data structures using global variables in BPF (which is an awesome improvement, see benchmarks below);
- PERCPU_HASH's bpf_map_lookup_elem() is partially inlined, just like the same for non-PERCPU HASH map; this still saves a bit of overhead.

To validate performance benefits, I hacked together a tiny benchmark doing only bpf_map_lookup_elem() and incrementing the value by 1 for PERCPU_ARRAY (arr-inc benchmark below) and PERCPU_HASH (hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar to PERCPU_ARRAY based on global variable array using bpf_get_smp_processor_id() to index array for current CPU (glob-arr-inc benchmark below).

BEFORE
======

glob-arr-inc   :  163.685 ± 0.092M/s
arr-inc        :  138.096 ± 0.160M/s
hash-inc       :   66.855 ± 0.123M/s

AFTER
=====

glob-arr-inc   :  173.921 ± 0.039M/s (+6%)
arr-inc        :  170.729 ± 0.210M/s (+23.7%)
hash-inc       :   68.673 ± 0.070M/s (+2.7%)

As can be seen, PERCPU_HASH gets a modest +2.7% improvement, while global array-based gets a nice +6% due to inlining of bpf_get_smp_processor_id().

But what's really important is that arr-inc benchmark basically catches up with glob-arr-inc, resulting in +23.7% improvement. This means that in practice it won't be necessary to avoid PERCPU_ARRAY anymore if performance is critical (e.g., high-frequent stats collection, which is often a practical use for PERCPU_ARRAY today).

v1->v2:
- use BPF_ALU64 | BPF_MOV instruction instead of LDX (Alexei);
- dropped the direct per-CPU memory read instruction, it can always be added

    back, if necessary;

- guarded bpf_get_smp_processor_id() behind x86-64 check (Alexei);
- switched all per-cpu addr casts to (unsigned long) to avoid sparse warnings.

Andrii Nakryiko (4):
bpf: add special internal-only MOV instruction to resolve per-CPU
addrs
bpf: inline bpf_get_smp_processor_id() helper
bpf: inline bpf_map_lookup_elem() for PERCPU_ARRAY maps
bpf: inline bpf_map_lookup_elem() helper for PERCPU_HASH map

 arch/x86/net/bpf_jit_comp.c | 16 ++++++++++++++++
 include/linux/filter.h      | 20 ++++++++++++++++++++
 kernel/bpf/arraymap.c       | 33 +++++++++++++++++++++++++++++++++
 kernel/bpf/core.c           |  5 +++++
 kernel/bpf/disasm.c         | 14 ++++++++++++++
 kernel/bpf/hashtab.c        | 21 +++++++++++++++++++++
 kernel/bpf/verifier.c       | 24 ++++++++++++++++++++++++
 7 files changed, 133 insertions(+)
Quoted 3 lines

--
2.43.0

Puranjay, Pu,

Quoted 7 lines

Is this something you guys can help implement for ARM64 and RISC-V architectures as well? I'm lacking the knowledge of the specifics of this architecture to be able to do this by myself, but it is a nice improvement for BPF applications, so it would be nice to get wide architecture support.

Thank you!

I have already started implementing this on ARM64,

Pu, can you do it for RISC-V? If you don't have cycles then I could do it after finishing ARM64.

Thanks,
Puranjay

#21 lore raw
Quoted 88 lines · Puranjay Mohan
Quoted 85 lines · Andrii Nakryiko
Quoted 71 lines · Andrii Nakryiko

Add a new BPF instruction for resolving per-CPU memory addresses.

New instruction is a special form of BPF_ALU64 | BPF_MOV | BPF_DW, with insns->off set to BPF_ADDR_PERCPU (== -1). It resolves provided per-CPU offset to an absolute address where per-CPU data resides for "this" CPU.

This patch set implements support for it in x86-64 BPF JIT only.

Using the new instruction, we also implement inlining for three cases:
- bpf_get_smp_processor_id(), which allows to avoid unnecessary trivial function call, saving a bit of performance and also not polluting LBR records with unnecessary function call/return records;
- PERCPU_ARRAY's bpf_map_lookup_elem() is completely inlined, bringing its performance to implementing per-CPU data structures using global variables in BPF (which is an awesome improvement, see benchmarks below);
- PERCPU_HASH's bpf_map_lookup_elem() is partially inlined, just like the same for non-PERCPU HASH map; this still saves a bit of overhead.

To validate performance benefits, I hacked together a tiny benchmark doing only bpf_map_lookup_elem() and incrementing the value by 1 for PERCPU_ARRAY (arr-inc benchmark below) and PERCPU_HASH (hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar to PERCPU_ARRAY based on global variable array using bpf_get_smp_processor_id() to index array for current CPU (glob-arr-inc benchmark below).

BEFORE
======

glob-arr-inc   :  163.685 ± 0.092M/s
arr-inc        :  138.096 ± 0.160M/s
hash-inc       :   66.855 ± 0.123M/s

AFTER
=====

glob-arr-inc   :  173.921 ± 0.039M/s (+6%)
arr-inc        :  170.729 ± 0.210M/s (+23.7%)
hash-inc       :   68.673 ± 0.070M/s (+2.7%)

As can be seen, PERCPU_HASH gets a modest +2.7% improvement, while global array-based gets a nice +6% due to inlining of bpf_get_smp_processor_id().

But what's really important is that arr-inc benchmark basically catches up with glob-arr-inc, resulting in +23.7% improvement. This means that in practice it won't be necessary to avoid PERCPU_ARRAY anymore if performance is critical (e.g., high-frequent stats collection, which is often a practical use for PERCPU_ARRAY today).

v1->v2:
- use BPF_ALU64 | BPF_MOV instruction instead of LDX (Alexei);
- dropped the direct per-CPU memory read instruction, it can always be added

    back, if necessary;

- guarded bpf_get_smp_processor_id() behind x86-64 check (Alexei);
- switched all per-cpu addr casts to (unsigned long) to avoid sparse warnings.

Andrii Nakryiko (4):
bpf: add special internal-only MOV instruction to resolve per-CPU
addrs
bpf: inline bpf_get_smp_processor_id() helper
bpf: inline bpf_map_lookup_elem() for PERCPU_ARRAY maps
bpf: inline bpf_map_lookup_elem() helper for PERCPU_HASH map

 arch/x86/net/bpf_jit_comp.c | 16 ++++++++++++++++
 include/linux/filter.h      | 20 ++++++++++++++++++++
 kernel/bpf/arraymap.c       | 33 +++++++++++++++++++++++++++++++++
 kernel/bpf/core.c           |  5 +++++
 kernel/bpf/disasm.c         | 14 ++++++++++++++
 kernel/bpf/hashtab.c        | 21 +++++++++++++++++++++
 kernel/bpf/verifier.c       | 24 ++++++++++++++++++++++++
 7 files changed, 133 insertions(+)
Quoted 3 lines

--
2.43.0

Puranjay, Pu,

Is this something you guys can help implement for ARM64 and RISC-V architectures as well? I'm lacking the knowledge of the specifics of this architecture to be able to do this by myself, but it is a nice improvement for BPF applications, so it would be nice to get wide architecture support.

Quoted 3 lines
Quoted 1 line

Thank you!

I have already started implementing this on ARM64,

Awesome, thanks!

Quoted 6 lines

Pu, can you do it for RISC-V? If you don't have cycles then I could do it after finishing ARM64.

Thanks,
Puranjay

#22 lore raw
In reply to Puranjay Mohan
Quoted 5 lines

I have already started implementing this on ARM64,

Pu, can you do it for RISC-V? If you don't have cycles then I could do it after finishing ARM64.

I ended up doing it for both ARM64 and RISC-V. But I don't see as high performance improvement as we see in x86.
Maybe, I missed something. Please see:

ARM64: https://lore.kernel.org/bpf/[email protected]/
RISC-V: https://lore.kernel.org/bpf/[email protected]/

Thanks,
Puranjay

#24 lore raw
In reply to Andrii Nakryiko

Hi Andrii,

Quoted 21 lines · Andrii Nakryiko
Quoted 19 lines · Andrii Nakryiko

Add a new BPF instruction for resolving per-CPU memory addresses.

New instruction is a special form of BPF_ALU64 | BPF_MOV | BPF_DW, with insns->off set to BPF_ADDR_PERCPU (== -1). It resolves provided per-CPU offset to an absolute address where per-CPU data resides for "this" CPU.

This patch set implements support for it in x86-64 BPF JIT only.

Using the new instruction, we also implement inlining for three cases:
- bpf_get_smp_processor_id(), which allows to avoid unnecessary trivial function call, saving a bit of performance and also not polluting LBR records with unnecessary function call/return records;
- PERCPU_ARRAY's bpf_map_lookup_elem() is completely inlined, bringing its performance to implementing per-CPU data structures using global variables in BPF (which is an awesome improvement, see benchmarks below);
- PERCPU_HASH's bpf_map_lookup_elem() is partially inlined, just like the same for non-PERCPU HASH map; this still saves a bit of overhead.

Quoted 6 lines
Quoted 6 lines

To validate performance benefits, I hacked together a tiny benchmark doing only bpf_map_lookup_elem() and incrementing the value by 1 for PERCPU_ARRAY (arr-inc benchmark below) and PERCPU_HASH (hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar to PERCPU_ARRAY based on global variable array using bpf_get_smp_processor_id() to index array for current CPU (glob-arr-inc benchmark below).

Can you share the code for these benchmarks? I want to use the same to compare the performance
on ARM64.

Thanks,
Puranjay

#25 lore raw
Quoted 33 lines · Puranjay Mohan

Hi Andrii,

Quoted 21 lines · Andrii Nakryiko
Quoted 19 lines · Andrii Nakryiko

Add a new BPF instruction for resolving per-CPU memory addresses.

New instruction is a special form of BPF_ALU64 | BPF_MOV | BPF_DW, with insns->off set to BPF_ADDR_PERCPU (== -1). It resolves provided per-CPU offset to an absolute address where per-CPU data resides for "this" CPU.

This patch set implements support for it in x86-64 BPF JIT only.

Using the new instruction, we also implement inlining for three cases:
- bpf_get_smp_processor_id(), which allows to avoid unnecessary trivial function call, saving a bit of performance and also not polluting LBR records with unnecessary function call/return records;
- PERCPU_ARRAY's bpf_map_lookup_elem() is completely inlined, bringing its performance to implementing per-CPU data structures using global variables in BPF (which is an awesome improvement, see benchmarks below);
- PERCPU_HASH's bpf_map_lookup_elem() is partially inlined, just like the same for non-PERCPU HASH map; this still saves a bit of overhead.

Quoted 6 lines
Quoted 6 lines

To validate performance benefits, I hacked together a tiny benchmark doing only bpf_map_lookup_elem() and incrementing the value by 1 for PERCPU_ARRAY (arr-inc benchmark below) and PERCPU_HASH (hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar to PERCPU_ARRAY based on global variable array using bpf_get_smp_processor_id() to index array for current CPU (glob-arr-inc benchmark below).

Quoted 4 lines

Can you share the code for these benchmarks? I want to use the same to compare the performance
on ARM64.

Sure, see [0]. You can run:

$ ./benchs/run_bench_trigger.sh glob-arr-inc arr-inc hash-inc

from tools/testing/selftest/bpf directory to get something like

$ ./benchs/run_bench_trigger.sh glob-arr-inc arr-inc hash-inc
glob-arr-inc   :  243.196 ± 7.879M/s
arr-inc        :  218.139 ± 4.407M/s
hash-inc       :   97.727 ± 3.643M/s

[0] https://github.com/anakryiko/linux/commit/8dec900975ef1a0308a7862154735549d6b66f64

Quoted 2 lines

Thanks,
Puranjay