* [PATCH bpf-next 1/3] bpf: verifier: Store null elision decision in insn_aux_data
2025-01-21 4:35 [PATCH bpf-next 0/3] bpf: Omit inlined bounds checks for null elided map lookups Daniel Xu
@ 2025-01-21 4:35 ` Daniel Xu
2025-01-23 0:23 ` Alexei Starovoitov
2025-01-21 4:35 ` [PATCH bpf-next 2/3] bpf: map: Thread null elision metadata to map_gen_lookup Daniel Xu
2025-01-21 4:35 ` [PATCH bpf-next 3/3] bpf: arraymap: Skip boundscheck during inlining when possible Daniel Xu
2 siblings, 1 reply; 8+ messages in thread
From: Daniel Xu @ 2025-01-21 4:35 UTC (permalink / raw)
To: daniel, ast, andrii
Cc: john.fastabend, martin.lau, eddyz87, song, yonghong.song, kpsingh,
sdf, haoluo, jolsa, bpf, linux-kernel
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.
Signed-off-by: Daniel Xu <dxu@dxuuu.xyz>
---
include/linux/bpf_verifier.h | 4 ++++
kernel/bpf/verifier.c | 4 +++-
2 files changed, 7 insertions(+), 1 deletion(-)
diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
index 32c23f2a3086..1bcd6d66e546 100644
--- a/include/linux/bpf_verifier.h
+++ b/include/linux/bpf_verifier.h
@@ -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. */
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 74525392714e..e83145c2260d 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -11265,8 +11265,10 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
if (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;
--
2.47.1
^ permalink raw reply related [flat|nested] 8+ messages in thread* Re: [PATCH bpf-next 1/3] bpf: verifier: Store null elision decision in insn_aux_data
2025-01-21 4:35 ` [PATCH bpf-next 1/3] bpf: verifier: Store null elision decision in insn_aux_data Daniel Xu
@ 2025-01-23 0:23 ` Alexei Starovoitov
0 siblings, 0 replies; 8+ messages in thread
From: Alexei Starovoitov @ 2025-01-23 0:23 UTC (permalink / raw)
To: Daniel Xu
Cc: Daniel Borkmann, Alexei Starovoitov, Andrii Nakryiko,
John Fastabend, Martin KaFai Lau, Eddy Z, Song Liu, Yonghong Song,
KP Singh, Stanislav Fomichev, Hao Luo, Jiri Olsa, bpf, LKML
On Mon, Jan 20, 2025 at 8:35 PM Daniel Xu <dxu@dxuuu.xyz> wrote:
>
> 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.
>
> Signed-off-by: Daniel Xu <dxu@dxuuu.xyz>
> ---
> include/linux/bpf_verifier.h | 4 ++++
> kernel/bpf/verifier.c | 4 +++-
> 2 files changed, 7 insertions(+), 1 deletion(-)
>
> diff --git a/include/linux/bpf_verifier.h b/include/linux/bpf_verifier.h
> index 32c23f2a3086..1bcd6d66e546 100644
> --- a/include/linux/bpf_verifier.h
> +++ b/include/linux/bpf_verifier.h
> @@ -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. */
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 74525392714e..e83145c2260d 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -11265,8 +11265,10 @@ static int check_helper_call(struct bpf_verifier_env *env, struct bpf_insn *insn
> if (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
^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH bpf-next 2/3] bpf: map: Thread null elision metadata to map_gen_lookup
2025-01-21 4:35 [PATCH bpf-next 0/3] bpf: Omit inlined bounds checks for null elided map lookups Daniel Xu
2025-01-21 4:35 ` [PATCH bpf-next 1/3] bpf: verifier: Store null elision decision in insn_aux_data Daniel Xu
@ 2025-01-21 4:35 ` Daniel Xu
2025-01-23 0:29 ` Alexei Starovoitov
2025-01-21 4:35 ` [PATCH bpf-next 3/3] bpf: arraymap: Skip boundscheck during inlining when possible Daniel Xu
2 siblings, 1 reply; 8+ messages in thread
From: Daniel Xu @ 2025-01-21 4:35 UTC (permalink / raw)
To: pabeni, kuba, hawk, maciej.fijalkowski, ast, edumazet, daniel,
davem, bjorn, john.fastabend, magnus.karlsson, andrii
Cc: martin.lau, eddyz87, song, yonghong.song, kpsingh, sdf, haoluo,
jolsa, jonathan.lemon, horms, bpf, linux-kernel, netdev
Add 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.
Signed-off-by: Daniel Xu <dxu@dxuuu.xyz>
---
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(-)
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index feda0ce90f5a..da8b420095c9 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -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);
diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
index eb28c0f219ee..8dbdceeead95 100644
--- a/kernel/bpf/arraymap.c
+++ b/kernel/bpf/arraymap.c
@@ -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;
diff --git a/kernel/bpf/hashtab.c b/kernel/bpf/hashtab.c
index 4a9eeb7aef85..103cdab85977 100644
--- a/kernel/bpf/hashtab.c
+++ b/kernel/bpf/hashtab.c
@@ -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;
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e83145c2260d..2ed2fd3c42f2 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -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) {
diff --git a/net/xdp/xskmap.c b/net/xdp/xskmap.c
index afa457506274..78579583b0a1 100644
--- a/net/xdp/xskmap.c
+++ b/net/xdp/xskmap.c
@@ -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;
--
2.47.1
^ permalink raw reply related [flat|nested] 8+ messages in thread* Re: [PATCH bpf-next 2/3] bpf: map: Thread null elision metadata to map_gen_lookup
2025-01-21 4:35 ` [PATCH bpf-next 2/3] bpf: map: Thread null elision metadata to map_gen_lookup Daniel Xu
@ 2025-01-23 0:29 ` Alexei Starovoitov
0 siblings, 0 replies; 8+ messages in thread
From: Alexei Starovoitov @ 2025-01-23 0:29 UTC (permalink / raw)
To: Daniel Xu
Cc: Paolo Abeni, Jakub Kicinski, Jesper Dangaard Brouer,
Fijalkowski, Maciej, Alexei Starovoitov, Eric Dumazet,
Daniel Borkmann, David S. Miller, Björn Töpel,
John Fastabend, Karlsson, Magnus, Andrii Nakryiko,
Martin KaFai Lau, Eddy Z, Song Liu, Yonghong Song, KP Singh,
Stanislav Fomichev, Hao Luo, Jiri Olsa, Jonathan Lemon,
Simon Horman, bpf, LKML, Network Development
On Mon, Jan 20, 2025 at 8:35 PM Daniel Xu <dxu@dxuuu.xyz> wrote:
>
> Add 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.
>
> Signed-off-by: Daniel Xu <dxu@dxuuu.xyz>
> ---
> 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(-)
>
> diff --git a/include/linux/bpf.h b/include/linux/bpf.h
> index feda0ce90f5a..da8b420095c9 100644
> --- a/include/linux/bpf.h
> +++ b/include/linux/bpf.h
> @@ -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.
^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH bpf-next 3/3] bpf: arraymap: Skip boundscheck during inlining when possible
2025-01-21 4:35 [PATCH bpf-next 0/3] bpf: Omit inlined bounds checks for null elided map lookups Daniel Xu
2025-01-21 4:35 ` [PATCH bpf-next 1/3] bpf: verifier: Store null elision decision in insn_aux_data Daniel Xu
2025-01-21 4:35 ` [PATCH bpf-next 2/3] bpf: map: Thread null elision metadata to map_gen_lookup Daniel Xu
@ 2025-01-21 4:35 ` Daniel Xu
2025-01-23 0:15 ` Eduard Zingerman
2025-01-23 0:33 ` Alexei Starovoitov
2 siblings, 2 replies; 8+ messages in thread
From: Daniel Xu @ 2025-01-21 4:35 UTC (permalink / raw)
To: daniel, ast, andrii
Cc: martin.lau, eddyz87, song, yonghong.song, john.fastabend, kpsingh,
sdf, haoluo, jolsa, bpf, linux-kernel
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: 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
Signed-off-by: Daniel Xu <dxu@dxuuu.xyz>
---
kernel/bpf/arraymap.c | 24 ++++++++++++++----------
1 file changed, 14 insertions(+), 10 deletions(-)
diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
index 8dbdceeead95..7385104dc0d0 100644
--- a/kernel/bpf/arraymap.c
+++ b/kernel/bpf/arraymap.c
@@ -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);
--
2.47.1
^ permalink raw reply related [flat|nested] 8+ messages in thread* Re: [PATCH bpf-next 3/3] bpf: arraymap: Skip boundscheck during inlining when possible
2025-01-21 4:35 ` [PATCH bpf-next 3/3] bpf: arraymap: Skip boundscheck during inlining when possible Daniel Xu
@ 2025-01-23 0:15 ` Eduard Zingerman
2025-01-23 0:33 ` Alexei Starovoitov
1 sibling, 0 replies; 8+ messages in thread
From: Eduard Zingerman @ 2025-01-23 0:15 UTC (permalink / raw)
To: Daniel Xu, daniel, ast, andrii
Cc: martin.lau, song, yonghong.song, john.fastabend, kpsingh, sdf,
haoluo, jolsa, bpf, linux-kernel
On Mon, 2025-01-20 at 21:35 -0700, Daniel Xu wrote:
[...]
Hi Daniel,
> @@ -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)) {
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.
[...]
^ permalink raw reply [flat|nested] 8+ messages in thread* Re: [PATCH bpf-next 3/3] bpf: arraymap: Skip boundscheck during inlining when possible
2025-01-21 4:35 ` [PATCH bpf-next 3/3] bpf: arraymap: Skip boundscheck during inlining when possible Daniel Xu
2025-01-23 0:15 ` Eduard Zingerman
@ 2025-01-23 0:33 ` Alexei Starovoitov
1 sibling, 0 replies; 8+ messages in thread
From: Alexei Starovoitov @ 2025-01-23 0:33 UTC (permalink / raw)
To: Daniel Xu
Cc: Daniel Borkmann, Alexei Starovoitov, Andrii Nakryiko,
Martin KaFai Lau, Eddy Z, Song Liu, Yonghong Song, John Fastabend,
KP Singh, Stanislav Fomichev, Hao Luo, Jiri Olsa, bpf, LKML
On Mon, Jan 20, 2025 at 8:35 PM Daniel Xu <dxu@dxuuu.xyz> wrote:
>
> 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: 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
>
> Signed-off-by: Daniel Xu <dxu@dxuuu.xyz>
> ---
> kernel/bpf/arraymap.c | 24 ++++++++++++++----------
> 1 file changed, 14 insertions(+), 10 deletions(-)
>
> diff --git a/kernel/bpf/arraymap.c b/kernel/bpf/arraymap.c
> index 8dbdceeead95..7385104dc0d0 100644
> --- a/kernel/bpf/arraymap.c
> +++ b/kernel/bpf/arraymap.c
> @@ -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);
> + }
> }
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
^ permalink raw reply [flat|nested] 8+ messages in thread