BPF inline improvements
Subsystems (4)
Daniel Borkmann
maintainerPATCH 1/2 bpf: improve htab inlining for future 32 bit jits
In reply to Daniel BorkmannLets future proof htab lookup inlining, commit 9015d2f59535 ("bpf:
inline htab_map_lookup_elem()") was making the assumption that a direct call emission to __htab_map_lookup_elem() will always work out for JITs. This is currently true since all JITs we have are for 64 bit archs, but in case of 32 bit JITs like upcoming arm32, we get a NULL pointer dereference when executing the call to __htab_map_lookup_elem() since passed arguments are of a different size (unsigned long vs. u64 for pointers) than what we do out of BPF. Thus, lets do a proper BPF_CALL_2() declaration such that we don't need to make any such assumptions.
--- kernel/bpf/hashtab.c | 10 ++++++++-- 1 file changed, 8 insertions(+), 2 deletions(-)
kernel/bpf/hashtab.c +8 -2
@@ -437,7 +437,8 @@ static struct htab_elem *lookup_nulls_elem_raw(struct hlist_nulls_head *head,* The return value is adjusted by BPF instructions * in htab_map_gen_lookup(). */ -static void *__htab_map_lookup_elem (struct bpf_map *map,void *key) +static __always_inline void *__htab_map_lookup_elem(struct bpf_map *map, +void *key) { struct bpf_htab *htab = container_of(map, struct bpf_htab, map);struct hlist_nulls_head *head;
@@ -479,12 +480,17 @@ static void *htab_map_lookup_elem(struct bpf_map *map, void *key)* bpf_prog * __htab_map_lookup_elem */ +BPF_CALL_2(bpf_htab_lookup_helper, struct bpf_map *, map, void *, key) +{ +return (unsigned long )__htab_map_lookup_elem (map, key); +} +static u32 htab_map_gen_lookup (struct bpf_map *map,struct bpf_insn *insn_buf) {struct bpf_insn *insn = insn_buf;const int ret =BPF_REG_0 ; - *insn++ =BPF_EMIT_CALL ((u64 (*)(u64 ,u64 ,u64 ,u64 ,u64 ))__htab_map_lookup_elem); + *insn++ =BPF_EMIT_CALL (bpf_htab_lookup_helper); *insn++ =BPF_JMP_IMM (BPF_JEQ , ret,0 ,1 ); *insn++ = BPF_ALU64_IMM(BPF_ADD, ret, offsetof(struct htab_elem, key) +
Signature · 1 line
1.9.3
Daniel Borkmann
maintainercover BPF inline improvements
First one makes htab inlining more robust wrt future jits and second one inlines map in map lookups through map_gen_lookup() callback.
Thanks!
Daniel Borkmann (2):
bpf: improve htab inlining for future 32 bit jits
bpf: inline map in map lookup functions for array and htab
kernel/bpf/arraymap.c | 26 ++++++++++++++++++++++++++ kernel/bpf/hashtab.c | 27 +++++++++++++++++++++++++-- 2 files changed, 51 insertions(+), 2 deletions(-)
Signature · 1 line
1.9.3
Daniel Borkmann
maintainerPATCH 2/2 bpf: inline map in map lookup functions for array and htab
Avoid two successive functions calls for the map in map lookup, first is the bpf_map_lookup_elem() helper call, and second the callback via map->ops->map_lookup_elem() to get to the map in map implementation. Implementation inlines array and htab flavor for map in map lookups.
--- kernel/bpf/arraymap.c | 26 ++++++++++++++++++++++++++ kernel/bpf/hashtab.c | 17 +++++++++++++++++ 2 files changed, 43 insertions(+)
kernel/bpf/arraymap.c +26 -0
@@ -603,6 +603,31 @@ static void *array_of_map_lookup_elem(struct bpf_map *map, void *key)return READ_ONCE (*inner_map); } +static u32 array_of_map_gen_lookup (struct bpf_map *map, +struct bpf_insn *insn_buf) +{ +u32 elem_size =round_up (map->value_size,8 ); +struct bpf_insn *insn = insn_buf; +const int ret =BPF_REG_0 ; +const int map_ptr =BPF_REG_1 ; +const int index =BPF_REG_2 ; + + *insn++ =BPF_ALU64_IMM (BPF_ADD , map_ptr, offsetof(struct bpf_array , value)); + *insn++ =BPF_LDX_MEM (BPF_W , ret, index,0 ); + *insn++ =BPF_JMP_IMM (BPF_JGE , ret, map->max_entries,5 ); +if (is_power_of_2 (elem_size)) + *insn++ =BPF_ALU64_IMM (BPF_LSH , ret,ilog2 (elem_size)); +else + *insn++ =BPF_ALU64_IMM (BPF_MUL , ret, elem_size); + *insn++ =BPF_ALU64_REG (BPF_ADD , ret, map_ptr); + *insn++ =BPF_LDX_MEM (BPF_DW , ret, ret,0 ); + *insn++ =BPF_JMP_IMM (BPF_JEQ , ret,0 ,1 ); + *insn++ =BPF_JMP_IMM (BPF_JA ,0 ,0 ,1 ); + *insn++ =BPF_MOV64_IMM (ret,0 ); + +return insn - insn_buf; +} +const struct bpf_map_ops array_of_maps_map_ops = { .map_alloc = array_of_map_alloc, .map_free = array_of_map_free,
@@ -612,4 +637,5 @@ static void *array_of_map_lookup_elem(struct bpf_map *map, void *key) .map_fd_get_ptr = bpf_map_fd_get_ptr, .map_fd_put_ptr = bpf_map_fd_put_ptr, .map_fd_sys_lookup_elem = bpf_map_fd_sys_lookup_elem, + .map_gen_lookup = array_of_map_gen_lookup, };
kernel/bpf/hashtab.c +17 -0
@@ -1317,6 +1317,22 @@ static void *htab_of_map_lookup_elem(struct bpf_map *map, void *key)return READ_ONCE (*inner_map); } +static u32 htab_of_map_gen_lookup (struct bpf_map *map, +struct bpf_insn *insn_buf) +{ +struct bpf_insn *insn = insn_buf; +const int ret =BPF_REG_0 ; + + *insn++ =BPF_EMIT_CALL (bpf_htab_lookup_helper); + *insn++ =BPF_JMP_IMM (BPF_JEQ , ret,0 ,2 ); + *insn++ =BPF_ALU64_IMM (BPF_ADD , ret, + offsetof(struct htab_elem , key) + +round_up (map->key_size,8 )); + *insn++ =BPF_LDX_MEM (BPF_DW , ret, ret,0 ); + +return insn - insn_buf; +} +static void htab_of_map_free (struct bpf_map *map) {bpf_map_meta_free (map->inner_map_meta);
@@ -1332,4 +1348,5 @@ static void htab_of_map_free(struct bpf_map *map) .map_fd_get_ptr = bpf_map_fd_get_ptr, .map_fd_put_ptr = bpf_map_fd_put_ptr, .map_fd_sys_lookup_elem = bpf_map_fd_sys_lookup_elem, + .map_gen_lookup = htab_of_map_gen_lookup, };
Signature · 1 line
1.9.3
Re: [PATCH net-next 1/2] bpf: improve htab inlining for future 32 bit jits
In reply to Daniel BorkmannQuoted 11 lines · Daniel Borkmann
Lets future proof htab lookup inlining, commit
9015d2f59535("bpf:
inlinehtab_map_lookup_elem()") was making the assumption that a direct call emission to__htab_map_lookup_elem()will always work out for JITs. This is currently true since all JITs we have are for 64 bit archs, but in case of 32 bit JITs like upcoming arm32, we get a NULL pointer dereference when executing the call to__htab_map_lookup_elem()since passed arguments are of a different size (unsigned long vs. u64 for pointers) than what we do out of BPF. Thus, lets do a properBPF_CALL_2()declaration such that we don't need to make any such assumptions.
Quoted 2 lines
Reported-by Shubham Bansal <[email protected]>Signed-off-by Daniel Borkmann <[email protected]>
assuming on 64-bit archs the should be no perf difference and only increase in .text, since __htab_map_lookup_elem is now force inlined into a bunch of places?
I guess that's ok, but kinda sux for 64-bit archs to pay such penalty because of 32-bit archs.
May be drop always_inline and do such thing conditionally on 32-bit archs only?
what's the increase in .text?
any difference seen in map_perf_test?
Re: [PATCH net-next 2/2] bpf: inline map in map lookup functions for array and htab
In reply to Daniel BorkmannQuoted 6 lines · Daniel Borkmann
Avoid two successive functions calls for the map in map lookup, first is the
bpf_map_lookup_elem()helper call, and second the callback viamap->ops->map_lookup_elem()to get to the map in map implementation. Implementation inlines array and htab flavor for map in map lookups.Signed-off-by Daniel Borkmann <[email protected]>
lgtm
thanks for adding this optimization.
Daniel Borkmann
maintainerRe: [PATCH net-next 1/2] bpf: improve htab inlining for future 32 bit jits
In reply to Alexei StarovoitovQuoted 12 lines · Alexei Starovoitov
Quoted 11 lines · Daniel Borkmann
Lets future proof htab lookup inlining, commit
9015d2f59535("bpf:
inlinehtab_map_lookup_elem()") was making the assumption that a direct call emission to__htab_map_lookup_elem()will always work out for JITs. This is currently true since all JITs we have are for 64 bit archs, but in case of 32 bit JITs like upcoming arm32, we get a NULL pointer dereference when executing the call to__htab_map_lookup_elem()since passed arguments are of a different size (unsigned long vs. u64 for pointers) than what we do out of BPF. Thus, lets do a properBPF_CALL_2()declaration such that we don't need to make any such assumptions.
Quoted 8 lines
Quoted 2 lines
Reported-by Shubham Bansal <[email protected]>Signed-off-by Daniel Borkmann <[email protected]>assuming on 64-bit archs the should be no perf difference and only increase in .text, since
__htab_map_lookup_elemis now force inlined into a bunch of places?
I guess that's ok, but kinda sux for 64-bit archs to pay such penalty because of 32-bit archs.
Yeah true, text bumps from 11k to 13k, doesn't pay off.
Quoted 2 lines
May be drop
always_inlineand do such thing conditionally on 32-bit archs only?
I will guard with this instead:
kernel/bpf/verifier.c +5 -1
@@ -4160,7 +4160,11 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env)continue ; } -if (ebpf_jit_enabled () && insn->imm == BPF_FUNC_map_lookup_elem) { +/* BPF_EMIT_CALL() assumptions in some of the map_gen_lookup +* handlers are currently limited to 64 bit only. +*/ +if (ebpf_jit_enabled () &&BITS_PER_LONG ==64 && + insn->imm == BPF_FUNC_map_lookup_elem) { map_ptr = env->insn_aux_data[i + delta].map_ptr;if (map_ptr ==BPF_MAP_PTR_POISON || !map_ptr->ops->map_gen_lookup)
Re: [PATCH net-next 1/2] bpf: improve htab inlining for future 32 bit jits
Quoted 42 lines · Daniel Borkmann
Quoted 12 lines · Alexei Starovoitov
Quoted 11 lines · Daniel Borkmann
Lets future proof htab lookup inlining, commit
9015d2f59535("bpf:
inlinehtab_map_lookup_elem()") was making the assumption that a direct call emission to__htab_map_lookup_elem()will always work out for JITs. This is currently true since all JITs we have are for 64 bit archs, but in case of 32 bit JITs like upcoming arm32, we get a NULL pointer dereference when executing the call to__htab_map_lookup_elem()since passed arguments are of a different size (unsigned long vs. u64 for pointers) than what we do out of BPF. Thus, lets do a properBPF_CALL_2()declaration such that we don't need to make any such assumptions.Quoted 8 lines
Quoted 2 lines
Reported-by Shubham Bansal <[email protected]>Signed-off-by Daniel Borkmann <[email protected]>assuming on 64-bit archs the should be no perf difference and only increase in .text, since
__htab_map_lookup_elemis now force inlined into a bunch of places?
I guess that's ok, but kinda sux for 64-bit archs to pay such penalty because of 32-bit archs.Yeah true, text bumps from 11k to 13k, doesn't pay off.
Quoted 2 lines
May be drop
always_inlineand do such thing conditionally on 32-bit archs only?I will guard with this instead:
kernel/bpf/verifier.c +1
-1@@ -4160,7 +4160,11 @@ static int fixup_bpf_calls(struct bpf_verifier_env *env) continue; } -if (ebpf_jit_enabled () && insn->imm == BPF_FUNC_map_lookup_elem) { +/* BPF_EMIT_CALL() assumptions in some of the
map_gen_lookup
kernel/bpf/verifier.c static int fixup_bpf_calls(struct bpf_verifier_env *env) · line 4170
Quoted 7 lines
kernel/bpf/verifier.c +4
-0+* handlers are currently limited to 64 bit only. +*/ +if (ebpf_jit_enabled () &&BITS_PER_LONG ==64 && + insn->imm == BPF_FUNC_map_lookup_elem) { map_ptr = env->insn_aux_data[i + delta].map_ptr;if (map_ptr ==BPF_MAP_PTR_POISON || !map_ptr->ops->map_gen_lookup)
sure. looks good to me for now. We probably need to first measure the perf gains out of inlining on 32-bit arm to go next step. Thanks!