bpf: Omit inlined bounds checks for null elided map lookups
Subsystems (5)
cover bpf: Omit inlined bounds checks for null elided map lookups
This follows up the null elision patchset with a corresponding codegen change. When the lookup is known to be inbounds, the inlined lookup can skip the bounds check.
See final commit for the JIT diff.
Daniel Xu (3):
bpf: verifier: Store null elision decision in insn_aux_data
bpf: map: Thread null elision metadata to map_gen_lookup
bpf: arraymap: Skip boundscheck during inlining when possible
include/linux/bpf.h | 2 +- include/linux/bpf_verifier.h | 4 ++++ kernel/bpf/arraymap.c | 35 ++++++++++++++++++++++------------- kernel/bpf/hashtab.c | 14 ++++++++++---- kernel/bpf/verifier.c | 6 ++++-- net/xdp/xskmap.c | 4 +++- 6 files changed, 44 insertions(+), 21 deletions(-)
Signature · 1 line
2.47.1
PATCH 1/3 bpf: verifier: Store null elision decision in insn_aux_data
Save the null elision decision from verification so that it can be reused later during bpf_map_lookup_elem inlining. There's a generated jump that can be omitted if the null was elided.
--- include/linux/bpf_verifier.h | 4 ++++ kernel/bpf/verifier.c | 4 +++- 2 files changed, 7 insertions(+), 1 deletion(-)
include/linux/bpf_verifier.h +4 -0
@@ -515,6 +515,10 @@ struct bpf_map_ptr_state {struct bpf_map *map_ptr;bool poison;bool unpriv; +/* true if instruction is a bpf_map_lookup_elem() with statically +* known in-bounds key. +*/ +bool inbounds; };/* Possible states for alu_state member. */
kernel/bpf/verifier.c +3 -1
@@ -11265,8 +11265,10 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insnif (func_id == BPF_FUNC_map_lookup_elem &&can_elide_value_nullness (meta.map_ptr->map_type) && meta.const_map_key >=0 && - meta.const_map_key < meta.map_ptr->max_entries) + meta.const_map_key < meta.map_ptr->max_entries) { ret_flag &= ~PTR_MAYBE_NULL ; + env->insn_aux_data[insn_idx].map_ptr_state.inbounds = true; + } regs[BPF_REG_0 ].map_ptr = meta.map_ptr; regs[BPF_REG_0 ].map_uid = meta.map_uid;
Signature · 1 line
2.47.1
PATCH 2/3 bpf: map: Thread null elision metadata to map_gen_lookup
In reply to Daniel XuAdd an extra parameter to map_gen_lookup callback so that if the lookup is known to be inbounds, the bounds check can be omitted.
The next commit will take advantage of this new information.
--- include/linux/bpf.h | 2 +- kernel/bpf/arraymap.c | 11 ++++++++--- kernel/bpf/hashtab.c | 14 ++++++++++---- kernel/bpf/verifier.c | 2 +- net/xdp/xskmap.c | 4 +++- 5 files changed, 23 insertions(+), 10 deletions(-)
include/linux/bpf.h +1 -1
@@ -117,7 +117,7 @@ struct bpf_map_ops {* may manipulate it, exists. */ void (*map_fd_put_ptr)(struct bpf_map *map,void *ptr,bool need_defer); -int (*map_gen_lookup)(struct bpf_map *map,struct bpf_insn *insn_buf); +int (*map_gen_lookup)(struct bpf_map *map,struct bpf_insn *insn_buf,bool inbounds);u32 (*map_fd_sys_lookup_elem)(void *ptr);void (*map_seq_show_elem)(struct bpf_map *map,void *key,struct seq_file *m);
kernel/bpf/arraymap.c +8 -3
@@ -205,7 +205,9 @@ static int array_map_direct_value_meta(const struct bpf_map *map, u64 imm, }/* emit BPF instructions equivalent to C code of array_map_lookup_elem() */ -static int array_map_gen_lookup (struct bpf_map *map,struct bpf_insn *insn_buf) +static int array_map_gen_lookup (struct bpf_map *map, +struct bpf_insn *insn_buf, +bool inbounds) { struct bpf_array *array = container_of(map, struct bpf_array, map);struct bpf_insn *insn = insn_buf;
@@ -250,7 +252,9 @@ static void *percpu_array_map_lookup_elem(struct bpf_map *map, void *key) }/* 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) +static int percpu_array_map_gen_lookup (struct bpf_map *map, +struct bpf_insn *insn_buf, +bool inbounds) { struct bpf_array *array = container_of(map, struct bpf_array, map);struct bpf_insn *insn = insn_buf;
@@ -1392,7 +1396,8 @@ static void *array_of_map_lookup_elem(struct bpf_map *map, void *key) }static int array_of_map_gen_lookup (struct bpf_map *map, -struct bpf_insn *insn_buf) +struct bpf_insn *insn_buf, +bool inbounds) { struct bpf_array *array = container_of(map, struct bpf_array, map);u32 elem_size = array->elem_size;
kernel/bpf/hashtab.c +10 -4
@@ -720,7 +720,9 @@ static void *htab_map_lookup_elem(struct bpf_map *map, void *key)* bpf_prog * __htab_map_lookup_elem */ -static int htab_map_gen_lookup (struct bpf_map *map,struct bpf_insn *insn_buf) +static int htab_map_gen_lookup (struct bpf_map *map, +struct bpf_insn *insn_buf, +bool inbounds) {struct bpf_insn *insn = insn_buf;const int ret =BPF_REG_0 ;
@@ -760,7 +762,8 @@ static void *htab_lru_map_lookup_elem_sys(struct bpf_map *map, void *key) }static int htab_lru_map_gen_lookup (struct bpf_map *map, -struct bpf_insn *insn_buf) +struct bpf_insn *insn_buf, +bool inbounds) {struct bpf_insn *insn = insn_buf;const int ret =BPF_REG_0 ;
@@ -2342,7 +2345,9 @@ static void *htab_percpu_map_lookup_elem(struct bpf_map *map, void *key) }/* 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) +static int htab_percpu_map_gen_lookup (struct bpf_map *map, +struct bpf_insn *insn_buf, +bool inbounds) {struct bpf_insn *insn = insn_buf;
@@ -2626,7 +2631,8 @@ static void *htab_of_map_lookup_elem(struct bpf_map *map, void *key) }static int htab_of_map_gen_lookup (struct bpf_map *map, -struct bpf_insn *insn_buf) +struct bpf_insn *insn_buf, +bool inbounds) {struct bpf_insn *insn = insn_buf;const int ret =BPF_REG_0 ;
kernel/bpf/verifier.c +1 -1
@@ -21582,7 +21582,7 @@ static int do_misc_fixups(struct bpf_verifier_env *env) ops = map_ptr->ops;if (insn->imm == BPF_FUNC_map_lookup_elem && ops->map_gen_lookup) { - cnt = ops->map_gen_lookup (map_ptr, insn_buf); + cnt = ops->map_gen_lookup (map_ptr, insn_buf, aux->map_ptr_state.inbounds);if (cnt == -EOPNOTSUPP ) goto patch_map_ops_generic;if (cnt <=0 || cnt >=INSN_BUF_SIZE ) {
net/xdp/xskmap.c +3 -1
@@ -118,7 +118,9 @@ static int xsk_map_get_next_key(struct bpf_map *map, void *key, void *next_key)return 0 ; } -static int xsk_map_gen_lookup (struct bpf_map *map,struct bpf_insn *insn_buf) +static int xsk_map_gen_lookup (struct bpf_map *map, +struct bpf_insn *insn_buf, +bool inbounds) {const int ret =BPF_REG_0 , mp =BPF_REG_1 , index =BPF_REG_2 ;struct bpf_insn *insn = insn_buf;
Signature · 1 line
2.47.1
PATCH 3/3 bpf: arraymap: Skip boundscheck during inlining when possible
In reply to Daniel XuFor regular arraymaps and percpu arraymaps, if the lookup is known to be inbounds, the inlined bounds check can be omitted. One fewer jump puts less pressure on the branch predictor. While it probably won't affect real workloads much, we can basically get this for free. So might as well - free wins are nice.
JIT diff for regular arraymap (x86-64):
; val = bpf_map_lookup_elem(&map_array, &key);
- 22: movabsq $-131387164803072, %rdi
+ 22: movabsq $-131387246749696, %rdi
2c: addq $472, %rdi
33: movl (%rsi), %eax
- 36: cmpq $2, %rax
- 3a: jae 0x45
- 3c: imulq $48, %rax, %rax
- 40: addq %rdi, %rax
- 43: jmp 0x47
- 45: xorl %eax, %eax
- 47: movl $4, %edi
+ 36: imulq $48, %rax, %rax
+ 3a: addq %rdi, %rax
+ 3d: jmp 0x41
+ 3f: xorl %eax, %eax
+ 41: movl $4, %edi
JIT diff for percpu arraymap (x86-64):
; val = bpf_map_lookup_elem(&map_array_pcpu, &key);
- 22: movabsq $-131387183532032, %rdi
+ 22: movabsq $-131387273779200, %rdi
2c: addq $472, %rdi
33: movl (%rsi), %eax
- 36: cmpq $2, %rax
- 3a: jae 0x52
- 3c: shlq $3, %rax
- 40: addq %rdi, %rax
- 43: movq (%rax), %rax
- 47: addq %gs:170664, %rax
- 50: jmp 0x54
- 52: xorl %eax, %eax
- 54: movl $4, %edi
+ 36: shlq $3, %rax
+ 3a: addq %rdi, %rax
+ 3d: movq (%rax), %rax
+ 41: addq %gs:170664, %rax
+ 4a: jmp 0x4e
+ 4c: xorl %eax, %eax
+ 4e: movl $4, %edi
--- kernel/bpf/arraymap.c | 24 ++++++++++++++---------- 1 file changed, 14 insertions(+), 10 deletions(-)
kernel/bpf/arraymap.c +14 -10
@@ -221,11 +221,13 @@ static int array_map_gen_lookup(struct bpf_map *map, *insn++ =BPF_ALU64_IMM (BPF_ADD , map_ptr, offsetof(struct bpf_array , value)); *insn++ =BPF_LDX_MEM (BPF_W , ret, index,0 ); -if (!map->bypass_spec_v1) { - *insn++ =BPF_JMP_IMM (BPF_JGE , ret, map->max_entries,4 ); - *insn++ =BPF_ALU32_IMM (BPF_AND , ret, array->index_mask); - }else { - *insn++ =BPF_JMP_IMM (BPF_JGE , ret, map->max_entries,3 ); +if (!inbounds) { +if (!map->bypass_spec_v1) { + *insn++ =BPF_JMP_IMM (BPF_JGE , ret, map->max_entries,4 ); + *insn++ =BPF_ALU32_IMM (BPF_AND , ret, array->index_mask); + }else { + *insn++ =BPF_JMP_IMM (BPF_JGE , ret, map->max_entries,3 ); + } }if (is_power_of_2 (elem_size)) {
@@ -269,11 +271,13 @@ static int percpu_array_map_gen_lookup(struct bpf_map *map, *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 ); +if (!inbounds) { +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 );
Signature · 1 line
2.47.1
Eduard Zingerman
maintainerRe: [PATCH bpf-next 3/3] bpf: arraymap: Skip boundscheck during inlining when possible
On Mon, 2025-01-20 at 21:35 -0700, Daniel Xu wrote:
[...]
Hi Daniel,
Quoted 9 lines
kernel/bpf/arraymap.c +0
-5@@ -221,11 +221,13 @@ static int array_map_gen_lookup(struct bpf_map *map, *insn++ =BPF_ALU64_IMM (BPF_ADD , map_ptr, offsetof(struct bpf_array , value)); *insn++ =BPF_LDX_MEM (BPF_W , ret, index,0 ); -if (!map->bypass_spec_v1) { - *insn++ =BPF_JMP_IMM (BPF_JGE , ret, map->max_entries,4 ); - *insn++ =BPF_ALU32_IMM (BPF_AND , ret, array->index_mask); - }else { - *insn++ =BPF_JMP_IMM (BPF_JGE , ret, map->max_entries,3 );
kernel/bpf/arraymap.c static int array_map_gen_lookup(struct bpf_map *map, · line 233
Quoted 10 lines
kernel/bpf/arraymap.c +7
-0+if (!inbounds) { +if (!map->bypass_spec_v1) { + *insn++ =BPF_JMP_IMM (BPF_JGE , ret, map->max_entries,4 ); + *insn++ =BPF_ALU32_IMM (BPF_AND , ret, array->index_mask); + }else { + *insn++ =BPF_JMP_IMM (BPF_JGE , ret, map->max_entries,3 ); + } }if (is_power_of_2 (elem_size)) {
Note that below this hunk there is the following code:
*insn++ = BPF_JMP_IMM(BPF_JA, 0, 0, 1); *insn++ = BPF_MOV64_IMM(ret, 0); return insn - insn_buf;
This part becomes redundant after your change. E.g. here is jit listing for an_array_with_a_32bit_constant_0_no_nullness selftest:
JITED:
=============
func #0:
0: f3 0f 1e fa endbr64 4: 0f 1f 44 00 00 nopl (%rax,%rax) 9: 0f 1f 00 nopl (%rax) c: 55 pushq %rbp d: 48 89 e5 movq %rsp, %rbp 10: f3 0f 1e fa endbr64 14: 48 81 ec 08 00 00 00 subq $0x8, %rsp 1b: 31 ff xorl %edi, %edi 1d: 89 7d fc movl %edi, -0x4(%rbp) 20: 48 89 ee movq %rbp, %rsi 23: 48 83 c6 fc addq $-0x4, %rsi 27: 48 bf 00 70 58 06 81 88 ff ff movabsq $-0x777ef9a79000, %rdi 31: 48 81 c7 d8 01 00 00 addq $0x1d8, %rdi 38: 8b 46 00 movl (%rsi), %eax 3b: 48 6b c0 30 imulq $0x30, %rax, %rax 3f: 48 01 f8 addq %rdi, %rax 42: eb 02 jmp L0 // 44: 31 c0 xorl %eax, %eax // never executed 46: bf 04 00 00 00 L0: movl $0x4, %edi // 4b: 89 78 00 movl %edi, (%rax) 4e: b8 04 00 00 00 movl $0x4, %eax 53: c9 leave 54: e9 22 38 50 c3 jmp 0xffffffffc350387b
Also note that there are __arch_x86_64 and __jited tags for selftests. These allow to match against disassembly of the generated binary code. (See verifier_tailcall_jit.c for an example).
I think it would be good to add a test matching jited code for this feature.
[...]
Re: [PATCH bpf-next 1/3] bpf: verifier: Store null elision decision in insn_aux_data
In reply to Daniel XuQuoted 31 lines · Daniel Xu
Save the null elision decision from verification so that it can be reused later during
bpf_map_lookup_eleminlining. There's a generated jump that can be omitted if the null was elided.Signed-off-by Daniel Xu <[email protected]>--- include/linux/bpf_verifier.h | 4 ++++ kernel/bpf/verifier.c | 4 +++- 2 files changed, 7 insertions(+), 1 deletion(-)include/linux/bpf_verifier.h +4
-0@@ -515,6 +515,10 @@ struct bpf_map_ptr_state {struct bpf_map *map_ptr;bool poison;bool unpriv; +/* true if instruction is a bpf_map_lookup_elem() with statically +* known in-bounds key. +*/ +bool inbounds; };/* Possible states for alu_state member. */ kernel/bpf/verifier.c +0
-0
kernel/bpf/verifier.c static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn · line 11271
Quoted 8 lines
kernel/bpf/verifier.c +3
-1@@ -11265,8 +11265,10 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insnif (func_id == BPF_FUNC_map_lookup_elem &&can_elide_value_nullness (meta.map_ptr->map_type) && meta.const_map_key >=0 && - meta.const_map_key < meta.map_ptr->max_entries) + meta.const_map_key < meta.map_ptr->max_entries) { ret_flag &= ~PTR_MAYBE_NULL ; + env->insn_aux_data[insn_idx].map_ptr_state.inbounds = true; + }
I don't think it handles the case where the same call insn is used with const key and non-const/out-of-range. insn_aux_data will be sticky and incorrect.
pw-bot: cr
Re: [PATCH bpf-next 2/3] bpf: map: Thread null elision metadata to map_gen_lookup
In reply to Daniel XuQuoted 20 lines · Daniel Xu
Add an extra parameter to
map_gen_lookupcallback so that if the lookup is known to be inbounds, the bounds check can be omitted.The next commit will take advantage of this new information.
Signed-off-by Daniel Xu <[email protected]>--- include/linux/bpf.h | 2 +- kernel/bpf/arraymap.c | 11 ++++++++--- kernel/bpf/hashtab.c | 14 ++++++++++---- kernel/bpf/verifier.c | 2 +- net/xdp/xskmap.c | 4 +++- 5 files changed, 23 insertions(+), 10 deletions(-)include/linux/bpf.h +0
-0
include/linux/bpf.h struct bpf_map_ops { · line 120
Quoted 5 lines
include/linux/bpf.h +1
-1@@ -117,7 +117,7 @@ struct bpf_map_ops {* may manipulate it, exists. */ void (*map_fd_put_ptr)(struct bpf_map *map,void *ptr,bool need_defer); -int (*map_gen_lookup)(struct bpf_map *map,struct bpf_insn *insn_buf); +int (*map_gen_lookup)(struct bpf_map *map,struct bpf_insn *insn_buf,bool inbounds);
The next time around we'd need another bool and more churn. Let's use 'enum map_gen_flags flags' right away.
Also don't you want to pass an actual const_map_key since its already known?
And the whole array_map_gen_lookup will become single ld_imm64 insn.
Re: [PATCH bpf-next 3/3] bpf: arraymap: Skip boundscheck during inlining when possible
In reply to Daniel XuQuoted 67 lines · Daniel Xu
For regular arraymaps and percpu arraymaps, if the lookup is known to be inbounds, the inlined bounds check can be omitted. One fewer jump puts less pressure on the branch predictor. While it probably won't affect real workloads much, we can basically get this for free. So might as well - free wins are nice.
JIT diff for regular arraymap (x86-64):
; val =
bpf_map_lookup_elem(&map_array, &key);
- 22: movabsq $-131387164803072, %rdi
+ 22: movabsq $-131387246749696, %rdi
2c: addq $472, %rdi
33: movl (%rsi), %eax
- 36: cmpq $2, %rax
- 3a: jae0x45
- 3c: imulq $48, %rax, %rax
- 40: addq %rdi, %rax
- 43: jmp0x47
- 45: xorl %eax, %eax
- 47: movl $4, %edi
+ 36: imulq $48, %rax, %rax
+ 3a: addq %rdi, %rax
+ 3d: jmp0x41
+ 3f: xorl %eax, %eax
+ 41: movl $4, %ediJIT diff for percpu arraymap (x86-64):
; val =
bpf_map_lookup_elem(&map_array_pcpu, &key);
- 22: movabsq $-131387183532032, %rdi
+ 22: movabsq $-131387273779200, %rdi
2c: addq $472, %rdi
33: movl (%rsi), %eax
- 36: cmpq $2, %rax
- 3a: jae0x52
- 3c: shlq $3, %rax
- 40: addq %rdi, %rax
- 43: movq (%rax), %rax
- 47: addq %gs:170664, %rax
- 50: jmp0x54
- 52: xorl %eax, %eax
- 54: movl $4, %edi
+ 36: shlq $3, %rax
+ 3a: addq %rdi, %rax
+ 3d: movq (%rax), %rax
+ 41: addq %gs:170664, %rax
+ 4a: jmp0x4e
+ 4c: xorl %eax, %eax
+ 4e: movl $4, %ediSigned-off-by Daniel Xu <[email protected]>--- kernel/bpf/arraymap.c | 24 ++++++++++++++---------- 1 file changed, 14 insertions(+), 10 deletions(-)kernel/bpf/arraymap.c +0
-3@@ -221,11 +221,13 @@ static int array_map_gen_lookup(struct bpf_map *map, *insn++ =BPF_ALU64_IMM (BPF_ADD , map_ptr, offsetof(struct bpf_array , value)); *insn++ =BPF_LDX_MEM (BPF_W , ret, index,0 ); -if (!map->bypass_spec_v1) { - *insn++ =BPF_JMP_IMM (BPF_JGE , ret, map->max_entries,4 ); - *insn++ =BPF_ALU32_IMM (BPF_AND , ret, array->index_mask);
kernel/bpf/arraymap.c static int array_map_gen_lookup(struct bpf_map *map, · line 231
Quoted 10 lines
kernel/bpf/arraymap.c +7
-2- }else { - *insn++ =BPF_JMP_IMM (BPF_JGE , ret, map->max_entries,3 ); +if (!inbounds) { +if (!map->bypass_spec_v1) { + *insn++ =BPF_JMP_IMM (BPF_JGE , ret, map->max_entries,4 ); + *insn++ =BPF_ALU32_IMM (BPF_AND , ret, array->index_mask); + }else { + *insn++ =BPF_JMP_IMM (BPF_JGE , ret, map->max_entries,3 ); + } }
As stands this is not correct for !spec_v1.
Though the verifier confirmed that key is constant, it still goes via load and math,
so there is a risk of speculation out of bounds.
All that will be non-issue if the actual const_map_key is passed in and computed into single ld_imm64
(as suggested in the other email).
pw-bot: cr