* [PATCH bpf-next 1/3] bpf: verifier: Do not extract constant map keys for irrelevant maps
2025-02-01 19:58 [PATCH bpf-next 0/3] bpf: Some fixes for nullness elision Daniel Xu
@ 2025-02-01 19:58 ` Daniel Xu
2025-02-03 18:45 ` Eduard Zingerman
2025-02-01 19:58 ` [PATCH bpf-next 2/3] bpf: selftests: Test constant key extraction on " Daniel Xu
2025-02-01 19:58 ` [PATCH bpf-next 3/3] bpf: verifier: Disambiguate get_constant_map_key() errors Daniel Xu
2 siblings, 1 reply; 8+ messages in thread
From: Daniel Xu @ 2025-02-01 19:58 UTC (permalink / raw)
To: daniel, andrii, ast
Cc: john.fastabend, martin.lau, eddyz87, song, yonghong.song, kpsingh,
sdf, haoluo, jolsa, bpf, linux-kernel, mhartmay, iii
Previously, we were trying to extract constant map keys for all
bpf_map_lookup_elem(), regardless of map type. This is an issue if the
map has a u64 key and the value is very high, as it can be interpreted
as a negative signed value. This in turn is treated as an error value by
check_func_arg() which causes a valid program to be incorrectly
rejected.
Fix by only extracting constant map keys for relevant maps. See next
commit for an example via selftest.
Reported-by: Marc Hartmayer <mhartmay@linux.ibm.com>
Reported-by: Ilya Leoshkevich <iii@linux.ibm.com>
Tested-by: Marc Hartmayer <mhartmay@linux.ibm.com>
Signed-off-by: Daniel Xu <dxu@dxuuu.xyz>
---
kernel/bpf/verifier.c | 10 +++++++---
1 file changed, 7 insertions(+), 3 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 9971c03adfd5..e9176a5ce215 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9206,6 +9206,8 @@ static s64 get_constant_map_key(struct bpf_verifier_env *env,
return reg->var_off.value;
}
+static bool can_elide_value_nullness(enum bpf_map_type type);
+
static int check_func_arg(struct bpf_verifier_env *env, u32 arg,
struct bpf_call_arg_meta *meta,
const struct bpf_func_proto *fn,
@@ -9354,9 +9356,11 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 arg,
err = check_helper_mem_access(env, regno, key_size, BPF_READ, false, NULL);
if (err)
return err;
- meta->const_map_key = get_constant_map_key(env, reg, key_size);
- if (meta->const_map_key < 0 && meta->const_map_key != -EOPNOTSUPP)
- return meta->const_map_key;
+ if (can_elide_value_nullness(meta->map_ptr->map_type)) {
+ meta->const_map_key = get_constant_map_key(env, reg, key_size);
+ if (meta->const_map_key < 0 && meta->const_map_key != -EOPNOTSUPP)
+ return meta->const_map_key;
+ }
break;
case ARG_PTR_TO_MAP_VALUE:
if (type_may_be_null(arg_type) && register_is_null(reg))
--
2.47.1
^ permalink raw reply related [flat|nested] 8+ messages in thread* Re: [PATCH bpf-next 1/3] bpf: verifier: Do not extract constant map keys for irrelevant maps
2025-02-01 19:58 ` [PATCH bpf-next 1/3] bpf: verifier: Do not extract constant map keys for irrelevant maps Daniel Xu
@ 2025-02-03 18:45 ` Eduard Zingerman
2025-02-04 9:09 ` Daniel Xu
0 siblings, 1 reply; 8+ messages in thread
From: Eduard Zingerman @ 2025-02-03 18:45 UTC (permalink / raw)
To: Daniel Xu, daniel, andrii, ast
Cc: john.fastabend, martin.lau, song, yonghong.song, kpsingh, sdf,
haoluo, jolsa, bpf, linux-kernel, mhartmay, iii
On Sat, 2025-02-01 at 12:58 -0700, Daniel Xu wrote:
> Previously, we were trying to extract constant map keys for all
> bpf_map_lookup_elem(), regardless of map type. This is an issue if the
> map has a u64 key and the value is very high, as it can be interpreted
> as a negative signed value. This in turn is treated as an error value by
> check_func_arg() which causes a valid program to be incorrectly
> rejected.
>
> Fix by only extracting constant map keys for relevant maps. See next
> commit for an example via selftest.
>
> Reported-by: Marc Hartmayer <mhartmay@linux.ibm.com>
> Reported-by: Ilya Leoshkevich <iii@linux.ibm.com>
> Tested-by: Marc Hartmayer <mhartmay@linux.ibm.com>
> Signed-off-by: Daniel Xu <dxu@dxuuu.xyz>
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Nit:
would be good if commit message said something along the lines:
... the fix works because nullness elision is only allowed for
{PERCPU_}ARRAY maps, and keys for these are within u32 range ...
> ---
> kernel/bpf/verifier.c | 10 +++++++---
> 1 file changed, 7 insertions(+), 3 deletions(-)
>
> diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
> index 9971c03adfd5..e9176a5ce215 100644
> --- a/kernel/bpf/verifier.c
> +++ b/kernel/bpf/verifier.c
> @@ -9206,6 +9206,8 @@ static s64 get_constant_map_key(struct bpf_verifier_env *env,
> return reg->var_off.value;
> }
>
> +static bool can_elide_value_nullness(enum bpf_map_type type);
> +
> static int check_func_arg(struct bpf_verifier_env *env, u32 arg,
> struct bpf_call_arg_meta *meta,
> const struct bpf_func_proto *fn,
> @@ -9354,9 +9356,11 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 arg,
> err = check_helper_mem_access(env, regno, key_size, BPF_READ, false, NULL);
> if (err)
> return err;
> - meta->const_map_key = get_constant_map_key(env, reg, key_size);
> - if (meta->const_map_key < 0 && meta->const_map_key != -EOPNOTSUPP)
> - return meta->const_map_key;
> + if (can_elide_value_nullness(meta->map_ptr->map_type)) {
> + meta->const_map_key = get_constant_map_key(env, reg, key_size);
> + if (meta->const_map_key < 0 && meta->const_map_key != -EOPNOTSUPP)
> + return meta->const_map_key;
> + }
> break;
> case ARG_PTR_TO_MAP_VALUE:
> if (type_may_be_null(arg_type) && register_is_null(reg))
^ permalink raw reply [flat|nested] 8+ messages in thread* Re: [PATCH bpf-next 1/3] bpf: verifier: Do not extract constant map keys for irrelevant maps
2025-02-03 18:45 ` Eduard Zingerman
@ 2025-02-04 9:09 ` Daniel Xu
0 siblings, 0 replies; 8+ messages in thread
From: Daniel Xu @ 2025-02-04 9:09 UTC (permalink / raw)
To: Eduard Zingerman
Cc: daniel, andrii, ast, john.fastabend, martin.lau, song,
yonghong.song, kpsingh, sdf, haoluo, jolsa, bpf, linux-kernel,
mhartmay, iii
On Mon, Feb 03, 2025 at 10:45:35AM -0800, Eduard Zingerman wrote:
> On Sat, 2025-02-01 at 12:58 -0700, Daniel Xu wrote:
> > Previously, we were trying to extract constant map keys for all
> > bpf_map_lookup_elem(), regardless of map type. This is an issue if the
> > map has a u64 key and the value is very high, as it can be interpreted
> > as a negative signed value. This in turn is treated as an error value by
> > check_func_arg() which causes a valid program to be incorrectly
> > rejected.
> >
> > Fix by only extracting constant map keys for relevant maps. See next
> > commit for an example via selftest.
> >
> > Reported-by: Marc Hartmayer <mhartmay@linux.ibm.com>
> > Reported-by: Ilya Leoshkevich <iii@linux.ibm.com>
> > Tested-by: Marc Hartmayer <mhartmay@linux.ibm.com>
> > Signed-off-by: Daniel Xu <dxu@dxuuu.xyz>
>
> Acked-by: Eduard Zingerman <eddyz87@gmail.com>
>
> Nit:
> would be good if commit message said something along the lines:
> ... the fix works because nullness elision is only allowed for
> {PERCPU_}ARRAY maps, and keys for these are within u32 range ...
Ack. I can respin if necessary. Otherwise, here's the edited commit msg:
bpf: verifier: Do not extract constant map keys for irrelevant maps
Previously, we were trying to extract constant map keys for all
bpf_map_lookup_elem(), regardless of map type. This is an issue if the
map has a u64 key and the value is very high, as it can be interpreted
as a negative signed value. This in turn is treated as an error value by
check_func_arg() which causes a valid program to be incorrectly
rejected.
Fix by only extracting constant map keys for relevant maps. This fix
works because nullness elision is only allowed for {PERCPU_}ARRAY maps,
and keys for these are within u32 range. See next commit for an example
via selftest.
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
Reported-by: Marc Hartmayer <mhartmay@linux.ibm.com>
Reported-by: Ilya Leoshkevich <iii@linux.ibm.com>
Tested-by: Marc Hartmayer <mhartmay@linux.ibm.com>
^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH bpf-next 2/3] bpf: selftests: Test constant key extraction on irrelevant maps
2025-02-01 19:58 [PATCH bpf-next 0/3] bpf: Some fixes for nullness elision Daniel Xu
2025-02-01 19:58 ` [PATCH bpf-next 1/3] bpf: verifier: Do not extract constant map keys for irrelevant maps Daniel Xu
@ 2025-02-01 19:58 ` Daniel Xu
2025-02-03 18:48 ` Eduard Zingerman
2025-02-01 19:58 ` [PATCH bpf-next 3/3] bpf: verifier: Disambiguate get_constant_map_key() errors Daniel Xu
2 siblings, 1 reply; 8+ messages in thread
From: Daniel Xu @ 2025-02-01 19:58 UTC (permalink / raw)
To: daniel, eddyz87, shuah, andrii, ast
Cc: mykolal, martin.lau, song, yonghong.song, john.fastabend, kpsingh,
sdf, haoluo, jolsa, bpf, linux-kselftest, linux-kernel, mhartmay,
iii
Test that very high constant map keys are not interpreted as an error
value by the verifier. This would previously fail.
Signed-off-by: Daniel Xu <dxu@dxuuu.xyz>
---
.../selftests/bpf/progs/verifier_array_access.c | 15 +++++++++++++++
1 file changed, 15 insertions(+)
diff --git a/tools/testing/selftests/bpf/progs/verifier_array_access.c b/tools/testing/selftests/bpf/progs/verifier_array_access.c
index 29eb9568633f..0a187ff725cc 100644
--- a/tools/testing/selftests/bpf/progs/verifier_array_access.c
+++ b/tools/testing/selftests/bpf/progs/verifier_array_access.c
@@ -713,4 +713,19 @@ unsigned int non_stack_key_lookup(void)
return val->index;
}
+SEC("socket")
+__description("doesn't reject UINT64_MAX as s64 for irrelevant maps")
+__success __retval(42)
+unsigned int doesnt_reject_irrelevant_maps(void)
+{
+ __u64 key = 0xFFFFFFFFFFFFFFFF;
+ struct test_val *val;
+
+ val = bpf_map_lookup_elem(&map_hash_48b, &key);
+ if (val)
+ return val->index;
+
+ return 42;
+}
+
char _license[] SEC("license") = "GPL";
--
2.47.1
^ permalink raw reply related [flat|nested] 8+ messages in thread* Re: [PATCH bpf-next 2/3] bpf: selftests: Test constant key extraction on irrelevant maps
2025-02-01 19:58 ` [PATCH bpf-next 2/3] bpf: selftests: Test constant key extraction on " Daniel Xu
@ 2025-02-03 18:48 ` Eduard Zingerman
0 siblings, 0 replies; 8+ messages in thread
From: Eduard Zingerman @ 2025-02-03 18:48 UTC (permalink / raw)
To: Daniel Xu, daniel, shuah, andrii, ast
Cc: mykolal, martin.lau, song, yonghong.song, john.fastabend, kpsingh,
sdf, haoluo, jolsa, bpf, linux-kselftest, linux-kernel, mhartmay,
iii
On Sat, 2025-02-01 at 12:58 -0700, Daniel Xu wrote:
> Test that very high constant map keys are not interpreted as an error
> value by the verifier. This would previously fail.
>
> Signed-off-by: Daniel Xu <dxu@dxuuu.xyz>
> ---
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
[...]
^ permalink raw reply [flat|nested] 8+ messages in thread
* [PATCH bpf-next 3/3] bpf: verifier: Disambiguate get_constant_map_key() errors
2025-02-01 19:58 [PATCH bpf-next 0/3] bpf: Some fixes for nullness elision Daniel Xu
2025-02-01 19:58 ` [PATCH bpf-next 1/3] bpf: verifier: Do not extract constant map keys for irrelevant maps Daniel Xu
2025-02-01 19:58 ` [PATCH bpf-next 2/3] bpf: selftests: Test constant key extraction on " Daniel Xu
@ 2025-02-01 19:58 ` Daniel Xu
2025-02-03 18:49 ` Eduard Zingerman
2 siblings, 1 reply; 8+ messages in thread
From: Daniel Xu @ 2025-02-01 19:58 UTC (permalink / raw)
To: daniel, andrii, ast
Cc: john.fastabend, martin.lau, eddyz87, song, yonghong.song, kpsingh,
sdf, haoluo, jolsa, bpf, linux-kernel, mhartmay, iii
Refactor get_constant_map_key() to disambiguate the constant key
value from potential error values. In the case that the key is
negative, it could be confused for an error.
It's not currently an issue, as the verifier seems to track s32 spills
as u32. So even if the program wrongly uses a negative value for an
arraymap key, the verifier just thinks it's an impossibly high value
which gets correctly discarded.
Refactor anyways to make things cleaner and prevent potential future
issues.
Signed-off-by: Daniel Xu <dxu@dxuuu.xyz>
---
kernel/bpf/verifier.c | 25 +++++++++++++++++--------
1 file changed, 17 insertions(+), 8 deletions(-)
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index e9176a5ce215..98354d781678 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -9149,10 +9149,11 @@ static int check_reg_const_str(struct bpf_verifier_env *env,
return 0;
}
-/* Returns constant key value if possible, else negative error */
-static s64 get_constant_map_key(struct bpf_verifier_env *env,
+/* Returns constant key value in `value` if possible, else negative error */
+static int get_constant_map_key(struct bpf_verifier_env *env,
struct bpf_reg_state *key,
- u32 key_size)
+ u32 key_size,
+ s64 *value)
{
struct bpf_func_state *state = func(env, key);
struct bpf_reg_state *reg;
@@ -9179,8 +9180,10 @@ static s64 get_constant_map_key(struct bpf_verifier_env *env,
/* First handle precisely tracked STACK_ZERO */
for (i = off; i >= 0 && stype[i] == STACK_ZERO; i--)
zero_size++;
- if (zero_size >= key_size)
+ if (zero_size >= key_size) {
+ *value = 0;
return 0;
+ }
/* Check that stack contains a scalar spill of expected size */
if (!is_spilled_scalar_reg(&state->stack[spi]))
@@ -9203,7 +9206,8 @@ static s64 get_constant_map_key(struct bpf_verifier_env *env,
if (err < 0)
return err;
- return reg->var_off.value;
+ *value = reg->var_off.value;
+ return 0;
}
static bool can_elide_value_nullness(enum bpf_map_type type);
@@ -9357,9 +9361,14 @@ static int check_func_arg(struct bpf_verifier_env *env, u32 arg,
if (err)
return err;
if (can_elide_value_nullness(meta->map_ptr->map_type)) {
- meta->const_map_key = get_constant_map_key(env, reg, key_size);
- if (meta->const_map_key < 0 && meta->const_map_key != -EOPNOTSUPP)
- return meta->const_map_key;
+ err = get_constant_map_key(env, reg, key_size, &meta->const_map_key);
+ if (err < 0) {
+ meta->const_map_key = -1;
+ if (err == -EOPNOTSUPP)
+ err = 0;
+ else
+ return err;
+ }
}
break;
case ARG_PTR_TO_MAP_VALUE:
--
2.47.1
^ permalink raw reply related [flat|nested] 8+ messages in thread* Re: [PATCH bpf-next 3/3] bpf: verifier: Disambiguate get_constant_map_key() errors
2025-02-01 19:58 ` [PATCH bpf-next 3/3] bpf: verifier: Disambiguate get_constant_map_key() errors Daniel Xu
@ 2025-02-03 18:49 ` Eduard Zingerman
0 siblings, 0 replies; 8+ messages in thread
From: Eduard Zingerman @ 2025-02-03 18:49 UTC (permalink / raw)
To: Daniel Xu, daniel, andrii, ast
Cc: john.fastabend, martin.lau, song, yonghong.song, kpsingh, sdf,
haoluo, jolsa, bpf, linux-kernel, mhartmay, iii
On Sat, 2025-02-01 at 12:58 -0700, Daniel Xu wrote:
> Refactor get_constant_map_key() to disambiguate the constant key
> value from potential error values. In the case that the key is
> negative, it could be confused for an error.
>
> It's not currently an issue, as the verifier seems to track s32 spills
> as u32. So even if the program wrongly uses a negative value for an
> arraymap key, the verifier just thinks it's an impossibly high value
> which gets correctly discarded.
>
> Refactor anyways to make things cleaner and prevent potential future
> issues.
>
> Signed-off-by: Daniel Xu <dxu@dxuuu.xyz>
> ---
Acked-by: Eduard Zingerman <eddyz87@gmail.com>
[...]
^ permalink raw reply [flat|nested] 8+ messages in thread