Add internal-only BPF per-CPU instruction
Andrii Nakryiko
maintainerv2 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
Andrii Nakryiko
maintainerPATCH 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
@@ -1382,6 +1382,17 @@ static int do_jit(struct bpf_prog *bpf_prog, int *addrs, u8 *image, u8 *rw_imagemaybe_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
@@ -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
@@ -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
@@ -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
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_Xform withinsn->offfield set toBPF_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
Signed-off-by Andrii Nakryiko <[email protected]>--- 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
kernel test robot
build botRe: [PATCH v2 bpf-next 1/4] bpf: add special internal-only MOV instruction to resolve per-CPU addrs
In reply to Andrii Nakryikokernel 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
kernel test robot
build botRe: [PATCH v2 bpf-next 1/4] bpf: add special internal-only MOV instruction to resolve per-CPU addrs
In reply to Andrii Nakryikokernel 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
Andrii Nakryiko
maintainerPATCH v2 2/4 bpf: inline bpf_get_smp_processor_id() helper
In reply to Andrii NakryikoIf 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
@@ -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
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.Signed-off-by Andrii Nakryiko <[email protected]>--- kernel/bpf/verifier.c | 24 ++++++++++++++++++++++++ 1 file changed, 24 insertions(+)kernel/bpf/verifier.c +24
-0@@ -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
Andrii Nakryiko
maintainerPATCH v2 3/4 bpf: inline bpf_map_lookup_elem() for PERCPU_ARRAY maps
In reply to Andrii NakryikoUsing 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
@@ -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
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.
Signed-off-by Andrii Nakryiko <[email protected]>--- kernel/bpf/arraymap.c | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+)kernel/bpf/arraymap.c +0
-0
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,
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.
Signed-off-by Andrii Nakryiko <[email protected]>--- kernel/bpf/arraymap.c | 33 +++++++++++++++++++++++++++++++++ 1 file changed, 33 insertions(+)kernel/bpf/arraymap.c +0
-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]); }
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,Acked-by John Fastabend <[email protected]>
Andrii Nakryiko
maintainerPATCH v2 4/4 bpf: inline bpf_map_lookup_elem() helper for PERCPU_HASH map
In reply to Andrii NakryikoUsing 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
@@ -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
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.Signed-off-by Andrii Nakryiko <[email protected]>--- kernel/bpf/hashtab.c | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+)kernel/bpf/hashtab.c +20
-0@@ -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.
John Fastabend
reviewerQuoted 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, withinsns->offset toBPF_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'sbpf_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'sbpf_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 forPERCPU_ARRAY(arr-inc benchmark below) andPERCPU_HASH(hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar toPERCPU_ARRAYbased on global variable array usingbpf_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/sAFTER
=====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_HASHgets a modest +2.7% improvement, while global array-based gets a nice +6% due to inlining ofbpf_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_ARRAYanymore if performance is critical (e.g., high-frequent stats collection, which is often a practical use forPERCPU_ARRAYtoday).
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:
- useBPF_ALU64|BPF_MOVinstruction instead of LDX (Alexei);
- dropped the direct per-CPU memory read instruction, it can always be addedback, 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: inlinebpf_get_smp_processor_id()helper
bpf: inlinebpf_map_lookup_elem()forPERCPU_ARRAYmaps
bpf: inlinebpf_map_lookup_elem()helper forPERCPU_HASHmaparch/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
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, withinsns->offset toBPF_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'sbpf_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'sbpf_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 forPERCPU_ARRAY(arr-inc benchmark below) andPERCPU_HASH(hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar toPERCPU_ARRAYbased on global variable array usingbpf_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/sAFTER
=====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_HASHgets a modest +2.7% improvement, while global array-based gets a nice +6% due to inlining ofbpf_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_ARRAYanymore if performance is critical (e.g., high-frequent stats collection, which is often a practical use forPERCPU_ARRAYtoday).
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:
- useBPF_ALU64|BPF_MOVinstruction instead of LDX (Alexei);
- dropped the direct per-CPU memory read instruction, it can always be addedback, 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: inlinebpf_get_smp_processor_id()helper
bpf: inlinebpf_map_lookup_elem()forPERCPU_ARRAYmaps
bpf: inlinebpf_map_lookup_elem()helper forPERCPU_HASHmaparch/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
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, withinsns->offset toBPF_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'sbpf_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'sbpf_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 forPERCPU_ARRAY(arr-inc benchmark below) andPERCPU_HASH(hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar toPERCPU_ARRAYbased on global variable array usingbpf_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/sAFTER
=====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_HASHgets a modest +2.7% improvement, while global array-based gets a nice +6% due to inlining ofbpf_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_ARRAYanymore if performance is critical (e.g., high-frequent stats collection, which is often a practical use forPERCPU_ARRAYtoday).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 evenbpf_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:
- useBPF_ALU64|BPF_MOVinstruction instead of LDX (Alexei);
- dropped the direct per-CPU memory read instruction, it can always be addedback, 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: inlinebpf_get_smp_processor_id()helper
bpf: inlinebpf_map_lookup_elem()forPERCPU_ARRAYmaps
bpf: inlinebpf_map_lookup_elem()helper forPERCPU_HASHmaparch/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
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, withinsns->offset toBPF_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
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, withinsns->offset toBPF_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?
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, withinsns->offset toBPF_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_lookupassumesizeof(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.
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, withinsns->offset toBPF_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_ONis problematic, because thosegen_lookupcallbacks 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_lookupcallbacks to only build them on 64-bit archesor
Quoted 7 lines
b) add runtime checks inside
get_lookupto return-EOPNOTSUPPif 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.
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, withinsns->offset toBPF_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'sbpf_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'sbpf_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 forPERCPU_ARRAY(arr-inc benchmark below) andPERCPU_HASH(hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar toPERCPU_ARRAYbased on global variable array usingbpf_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/sAFTER
=====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_HASHgets a modest +2.7% improvement, while global array-based gets a nice +6% due to inlining ofbpf_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_ARRAYanymore if performance is critical (e.g., high-frequent stats collection, which is often a practical use forPERCPU_ARRAYtoday).
v1->v2:
- useBPF_ALU64|BPF_MOVinstruction instead of LDX (Alexei);
- dropped the direct per-CPU memory read instruction, it can always be addedback, 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: inlinebpf_get_smp_processor_id()helper
bpf: inlinebpf_map_lookup_elem()forPERCPU_ARRAYmaps
bpf: inlinebpf_map_lookup_elem()helper forPERCPU_HASHmaparch/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!
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, withinsns->offset toBPF_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'sbpf_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'sbpf_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 forPERCPU_ARRAY(arr-inc benchmark below) andPERCPU_HASH(hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar toPERCPU_ARRAYbased on global variable array usingbpf_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/sAFTER
=====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_HASHgets a modest +2.7% improvement, while global array-based gets a nice +6% due to inlining ofbpf_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_ARRAYanymore if performance is critical (e.g., high-frequent stats collection, which is often a practical use forPERCPU_ARRAYtoday).
v1->v2:
- useBPF_ALU64|BPF_MOVinstruction instead of LDX (Alexei);
- dropped the direct per-CPU memory read instruction, it can always be addedback, 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: inlinebpf_get_smp_processor_id()helper
bpf: inlinebpf_map_lookup_elem()forPERCPU_ARRAYmaps
bpf: inlinebpf_map_lookup_elem()helper forPERCPU_HASHmaparch/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.0Puranjay, 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
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, withinsns->offset toBPF_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'sbpf_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'sbpf_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 forPERCPU_ARRAY(arr-inc benchmark below) andPERCPU_HASH(hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar toPERCPU_ARRAYbased on global variable array usingbpf_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/sAFTER
=====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_HASHgets a modest +2.7% improvement, while global array-based gets a nice +6% due to inlining ofbpf_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_ARRAYanymore if performance is critical (e.g., high-frequent stats collection, which is often a practical use forPERCPU_ARRAYtoday).
v1->v2:
- useBPF_ALU64|BPF_MOVinstruction instead of LDX (Alexei);
- dropped the direct per-CPU memory read instruction, it can always be addedback, 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: inlinebpf_get_smp_processor_id()helper
bpf: inlinebpf_map_lookup_elem()forPERCPU_ARRAYmaps
bpf: inlinebpf_map_lookup_elem()helper forPERCPU_HASHmaparch/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.0Puranjay, 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
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
Nice work! Puranjay. I am on festival holiday.
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, withinsns->offset toBPF_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'sbpf_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'sbpf_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 forPERCPU_ARRAY(arr-inc benchmark below) andPERCPU_HASH(hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar toPERCPU_ARRAYbased on global variable array usingbpf_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
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, withinsns->offset toBPF_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'sbpf_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'sbpf_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 forPERCPU_ARRAY(arr-inc benchmark below) andPERCPU_HASH(hash-inc benchmark below) maps. To establish a baseline, I also implemented logic similar toPERCPU_ARRAYbased on global variable array usingbpf_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