* [PATCH v3 bpf 1/3] bpf: fix BTF verifier size resolution logic
2019-07-12 17:25 [PATCH v3 bpf 0/3] fix BTF verification size resolution Andrii Nakryiko
@ 2019-07-12 17:25 ` Andrii Nakryiko
2019-07-13 4:54 ` Martin Lau
2019-07-12 17:25 ` [PATCH v3 bpf 2/3] selftests/bpf: add trickier size resolution tests Andrii Nakryiko
` (3 subsequent siblings)
4 siblings, 1 reply; 7+ messages in thread
From: Andrii Nakryiko @ 2019-07-12 17:25 UTC (permalink / raw)
To: bpf, netdev, ast, daniel, yhs
Cc: andrii.nakryiko, kernel-team, Andrii Nakryiko, Martin KaFai Lau
BTF verifier has a size resolution bug which in some circumstances leads to
invalid size resolution for, e.g., TYPEDEF modifier. This happens if we have
[1] PTR -> [2] TYPEDEF -> [3] ARRAY, in which case due to being in pointer
context ARRAY size won't be resolved (because for pointer it doesn't matter, so
it's a sink in pointer context), but it will be permanently remembered as zero
for TYPEDEF and TYPEDEF will be marked as RESOLVED. Eventually ARRAY size will
be resolved correctly, but TYPEDEF resolved_size won't be updated anymore.
This, subsequently, will lead to erroneous map creation failure, if that
TYPEDEF is specified as either key or value, as key_size/value_size won't
correspond to resolved size of TYPEDEF (kernel will believe it's zero).
Note, that if BTF was ordered as [1] ARRAY <- [2] TYPEDEF <- [3] PTR, this
won't be a problem, as by the time we get to TYPEDEF, ARRAY's size is already
calculated and stored.
This bug manifests itself in rejecting BTF-defined maps that use array
typedef as a value type:
typedef int array_t[16];
struct {
__uint(type, BPF_MAP_TYPE_ARRAY);
__type(value, array_t); /* i.e., array_t *value; */
} test_map SEC(".maps");
The fix consists on not relying on modifier's resolved_size and instead using
modifier's resolved_id (type ID for "concrete" type to which modifier
eventually resolves) and doing size determination for that resolved type. This
allow to preserve existing "early DFS termination" logic for PTR or
STRUCT_OR_ARRAY contexts, but still do correct size determination for modifier
types.
Fixes: eb3f595dab40 ("bpf: btf: Validate type reference")
Cc: Martin KaFai Lau <kafai@fb.com>
Signed-off-by: Andrii Nakryiko <andriin@fb.com>
---
kernel/bpf/btf.c | 19 ++++++++++++-------
1 file changed, 12 insertions(+), 7 deletions(-)
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 546ebee39e2a..5fcc7a17eb5a 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -1073,11 +1073,18 @@ const struct btf_type *btf_type_id_size(const struct btf *btf,
!btf_type_is_var(size_type)))
return NULL;
- size = btf->resolved_sizes[size_type_id];
size_type_id = btf->resolved_ids[size_type_id];
size_type = btf_type_by_id(btf, size_type_id);
if (btf_type_nosize_or_null(size_type))
return NULL;
+ else if (btf_type_has_size(size_type))
+ size = size_type->size;
+ else if (btf_type_is_array(size_type))
+ size = btf->resolved_sizes[size_type_id];
+ else if (btf_type_is_ptr(size_type))
+ size = sizeof(void *);
+ else
+ return NULL;
}
*type_id = size_type_id;
@@ -1602,7 +1609,6 @@ static int btf_modifier_resolve(struct btf_verifier_env *env,
const struct btf_type *next_type;
u32 next_type_id = t->type;
struct btf *btf = env->btf;
- u32 next_type_size = 0;
next_type = btf_type_by_id(btf, next_type_id);
if (!next_type || btf_type_is_resolve_source_only(next_type)) {
@@ -1620,7 +1626,7 @@ static int btf_modifier_resolve(struct btf_verifier_env *env,
* save us a few type-following when we use it later (e.g. in
* pretty print).
*/
- if (!btf_type_id_size(btf, &next_type_id, &next_type_size)) {
+ if (!btf_type_id_size(btf, &next_type_id, NULL)) {
if (env_type_is_resolved(env, next_type_id))
next_type = btf_type_id_resolve(btf, &next_type_id);
@@ -1633,7 +1639,7 @@ static int btf_modifier_resolve(struct btf_verifier_env *env,
}
}
- env_stack_pop_resolved(env, next_type_id, next_type_size);
+ env_stack_pop_resolved(env, next_type_id, 0);
return 0;
}
@@ -1645,7 +1651,6 @@ static int btf_var_resolve(struct btf_verifier_env *env,
const struct btf_type *t = v->t;
u32 next_type_id = t->type;
struct btf *btf = env->btf;
- u32 next_type_size;
next_type = btf_type_by_id(btf, next_type_id);
if (!next_type || btf_type_is_resolve_source_only(next_type)) {
@@ -1675,12 +1680,12 @@ static int btf_var_resolve(struct btf_verifier_env *env,
* forward types or similar that would resolve to size of
* zero is allowed.
*/
- if (!btf_type_id_size(btf, &next_type_id, &next_type_size)) {
+ if (!btf_type_id_size(btf, &next_type_id, NULL)) {
btf_verifier_log_type(env, v->t, "Invalid type_id");
return -EINVAL;
}
- env_stack_pop_resolved(env, next_type_id, next_type_size);
+ env_stack_pop_resolved(env, next_type_id, 0);
return 0;
}
--
2.17.1
^ permalink raw reply related [flat|nested] 7+ messages in thread* Re: [PATCH v3 bpf 1/3] bpf: fix BTF verifier size resolution logic
2019-07-12 17:25 ` [PATCH v3 bpf 1/3] bpf: fix BTF verifier size resolution logic Andrii Nakryiko
@ 2019-07-13 4:54 ` Martin Lau
0 siblings, 0 replies; 7+ messages in thread
From: Martin Lau @ 2019-07-13 4:54 UTC (permalink / raw)
To: Andrii Nakryiko
Cc: bpf, netdev, Alexei Starovoitov, daniel, Yonghong Song,
andrii.nakryiko, Kernel Team
On Fri, Jul 12, 2019 at 10:25:55AM -0700, Andrii Nakryiko wrote:
> BTF verifier has a size resolution bug which in some circumstances leads to
> invalid size resolution for, e.g., TYPEDEF modifier. This happens if we have
> [1] PTR -> [2] TYPEDEF -> [3] ARRAY, in which case due to being in pointer
> context ARRAY size won't be resolved (because for pointer it doesn't matter, so
> it's a sink in pointer context), but it will be permanently remembered as zero
> for TYPEDEF and TYPEDEF will be marked as RESOLVED. Eventually ARRAY size will
> be resolved correctly, but TYPEDEF resolved_size won't be updated anymore.
> This, subsequently, will lead to erroneous map creation failure, if that
> TYPEDEF is specified as either key or value, as key_size/value_size won't
> correspond to resolved size of TYPEDEF (kernel will believe it's zero).
Thanks for the fix.
Acked-by: Martin KaFai Lau <kafai@fb.com>
^ permalink raw reply [flat|nested] 7+ messages in thread
* [PATCH v3 bpf 2/3] selftests/bpf: add trickier size resolution tests
2019-07-12 17:25 [PATCH v3 bpf 0/3] fix BTF verification size resolution Andrii Nakryiko
2019-07-12 17:25 ` [PATCH v3 bpf 1/3] bpf: fix BTF verifier size resolution logic Andrii Nakryiko
@ 2019-07-12 17:25 ` Andrii Nakryiko
2019-07-12 17:25 ` [PATCH v3 bpf 3/3] selftests/bpf: use typedef'ed arrays as map values Andrii Nakryiko
` (2 subsequent siblings)
4 siblings, 0 replies; 7+ messages in thread
From: Andrii Nakryiko @ 2019-07-12 17:25 UTC (permalink / raw)
To: bpf, netdev, ast, daniel, yhs
Cc: andrii.nakryiko, kernel-team, Andrii Nakryiko
Add more BTF tests, validating that size resolution logic is correct in
few trickier cases.
Signed-off-by: Andrii Nakryiko <andriin@fb.com>
---
tools/testing/selftests/bpf/test_btf.c | 88 ++++++++++++++++++++++++++
1 file changed, 88 insertions(+)
diff --git a/tools/testing/selftests/bpf/test_btf.c b/tools/testing/selftests/bpf/test_btf.c
index 8351cb5f4a20..3d617e806054 100644
--- a/tools/testing/selftests/bpf/test_btf.c
+++ b/tools/testing/selftests/bpf/test_btf.c
@@ -3417,6 +3417,94 @@ static struct btf_raw_test raw_tests[] = {
.value_type_id = 1,
.max_entries = 4,
},
+/*
+ * typedef int arr_t[16];
+ * struct s {
+ * arr_t *a;
+ * };
+ */
+{
+ .descr = "struct->ptr->typedef->array->int size resolution",
+ .raw_types = {
+ BTF_STRUCT_ENC(NAME_TBD, 1, 8), /* [1] */
+ BTF_MEMBER_ENC(NAME_TBD, 2, 0),
+ BTF_PTR_ENC(3), /* [2] */
+ BTF_TYPEDEF_ENC(NAME_TBD, 4), /* [3] */
+ BTF_TYPE_ARRAY_ENC(5, 5, 16), /* [4] */
+ BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [5] */
+ BTF_END_RAW,
+ },
+ BTF_STR_SEC("\0s\0a\0arr_t"),
+ .map_type = BPF_MAP_TYPE_ARRAY,
+ .map_name = "ptr_mod_chain_size_resolve_map",
+ .key_size = sizeof(int),
+ .value_size = sizeof(int) * 16,
+ .key_type_id = 5 /* int */,
+ .value_type_id = 3 /* arr_t */,
+ .max_entries = 4,
+},
+/*
+ * typedef int arr_t[16][8][4];
+ * struct s {
+ * arr_t *a;
+ * };
+ */
+{
+ .descr = "struct->ptr->typedef->multi-array->int size resolution",
+ .raw_types = {
+ BTF_STRUCT_ENC(NAME_TBD, 1, 8), /* [1] */
+ BTF_MEMBER_ENC(NAME_TBD, 2, 0),
+ BTF_PTR_ENC(3), /* [2] */
+ BTF_TYPEDEF_ENC(NAME_TBD, 4), /* [3] */
+ BTF_TYPE_ARRAY_ENC(5, 7, 16), /* [4] */
+ BTF_TYPE_ARRAY_ENC(6, 7, 8), /* [5] */
+ BTF_TYPE_ARRAY_ENC(7, 7, 4), /* [6] */
+ BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [7] */
+ BTF_END_RAW,
+ },
+ BTF_STR_SEC("\0s\0a\0arr_t"),
+ .map_type = BPF_MAP_TYPE_ARRAY,
+ .map_name = "multi_arr_size_resolve_map",
+ .key_size = sizeof(int),
+ .value_size = sizeof(int) * 16 * 8 * 4,
+ .key_type_id = 7 /* int */,
+ .value_type_id = 3 /* arr_t */,
+ .max_entries = 4,
+},
+/*
+ * typedef int int_t;
+ * typedef int_t arr3_t[4];
+ * typedef arr3_t arr2_t[8];
+ * typedef arr2_t arr1_t[16];
+ * struct s {
+ * arr1_t *a;
+ * };
+ */
+{
+ .descr = "typedef/multi-arr mix size resolution",
+ .raw_types = {
+ BTF_STRUCT_ENC(NAME_TBD, 1, 8), /* [1] */
+ BTF_MEMBER_ENC(NAME_TBD, 2, 0),
+ BTF_PTR_ENC(3), /* [2] */
+ BTF_TYPEDEF_ENC(NAME_TBD, 4), /* [3] */
+ BTF_TYPE_ARRAY_ENC(5, 10, 16), /* [4] */
+ BTF_TYPEDEF_ENC(NAME_TBD, 6), /* [5] */
+ BTF_TYPE_ARRAY_ENC(7, 10, 8), /* [6] */
+ BTF_TYPEDEF_ENC(NAME_TBD, 8), /* [7] */
+ BTF_TYPE_ARRAY_ENC(9, 10, 4), /* [8] */
+ BTF_TYPEDEF_ENC(NAME_TBD, 10), /* [9] */
+ BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4), /* [10] */
+ BTF_END_RAW,
+ },
+ BTF_STR_SEC("\0s\0a\0arr1_t\0arr2_t\0arr3_t\0int_t"),
+ .map_type = BPF_MAP_TYPE_ARRAY,
+ .map_name = "typedef_arra_mix_size_resolve_map",
+ .key_size = sizeof(int),
+ .value_size = sizeof(int) * 16 * 8 * 4,
+ .key_type_id = 10 /* int */,
+ .value_type_id = 3 /* arr_t */,
+ .max_entries = 4,
+},
}; /* struct btf_raw_test raw_tests[] */
--
2.17.1
^ permalink raw reply related [flat|nested] 7+ messages in thread* [PATCH v3 bpf 3/3] selftests/bpf: use typedef'ed arrays as map values
2019-07-12 17:25 [PATCH v3 bpf 0/3] fix BTF verification size resolution Andrii Nakryiko
2019-07-12 17:25 ` [PATCH v3 bpf 1/3] bpf: fix BTF verifier size resolution logic Andrii Nakryiko
2019-07-12 17:25 ` [PATCH v3 bpf 2/3] selftests/bpf: add trickier size resolution tests Andrii Nakryiko
@ 2019-07-12 17:25 ` Andrii Nakryiko
2019-07-12 18:47 ` [PATCH v3 bpf 0/3] fix BTF verification size resolution Yonghong Song
2019-07-15 22:18 ` Daniel Borkmann
4 siblings, 0 replies; 7+ messages in thread
From: Andrii Nakryiko @ 2019-07-12 17:25 UTC (permalink / raw)
To: bpf, netdev, ast, daniel, yhs
Cc: andrii.nakryiko, kernel-team, Andrii Nakryiko
Convert few tests that couldn't use typedef'ed arrays due to kernel bug.
Signed-off-by: Andrii Nakryiko <andriin@fb.com>
---
tools/testing/selftests/bpf/progs/test_get_stack_rawtp.c | 3 ++-
tools/testing/selftests/bpf/progs/test_stacktrace_build_id.c | 3 +--
tools/testing/selftests/bpf/progs/test_stacktrace_map.c | 2 +-
3 files changed, 4 insertions(+), 4 deletions(-)
diff --git a/tools/testing/selftests/bpf/progs/test_get_stack_rawtp.c b/tools/testing/selftests/bpf/progs/test_get_stack_rawtp.c
index d06b47a09097..33254b771384 100644
--- a/tools/testing/selftests/bpf/progs/test_get_stack_rawtp.c
+++ b/tools/testing/selftests/bpf/progs/test_get_stack_rawtp.c
@@ -47,11 +47,12 @@ struct {
* issue and avoid complicated C programming massaging.
* This is an acceptable workaround since there is one entry here.
*/
+typedef __u64 raw_stack_trace_t[2 * MAX_STACK_RAWTP];
struct {
__uint(type, BPF_MAP_TYPE_PERCPU_ARRAY);
__uint(max_entries, 1);
__type(key, __u32);
- __u64 (*value)[2 * MAX_STACK_RAWTP];
+ __type(value, raw_stack_trace_t);
} rawdata_map SEC(".maps");
SEC("tracepoint/raw_syscalls/sys_enter")
diff --git a/tools/testing/selftests/bpf/progs/test_stacktrace_build_id.c b/tools/testing/selftests/bpf/progs/test_stacktrace_build_id.c
index bbfc8337b6f0..f5638e26865d 100644
--- a/tools/testing/selftests/bpf/progs/test_stacktrace_build_id.c
+++ b/tools/testing/selftests/bpf/progs/test_stacktrace_build_id.c
@@ -36,8 +36,7 @@ struct {
__uint(type, BPF_MAP_TYPE_ARRAY);
__uint(max_entries, 128);
__type(key, __u32);
- /* there seems to be a bug in kernel not handling typedef properly */
- struct bpf_stack_build_id (*value)[PERF_MAX_STACK_DEPTH];
+ __type(value, stack_trace_t);
} stack_amap SEC(".maps");
/* taken from /sys/kernel/debug/tracing/events/random/urandom_read/format */
diff --git a/tools/testing/selftests/bpf/progs/test_stacktrace_map.c b/tools/testing/selftests/bpf/progs/test_stacktrace_map.c
index 803c15dc109d..fa0be3e10a10 100644
--- a/tools/testing/selftests/bpf/progs/test_stacktrace_map.c
+++ b/tools/testing/selftests/bpf/progs/test_stacktrace_map.c
@@ -35,7 +35,7 @@ struct {
__uint(type, BPF_MAP_TYPE_ARRAY);
__uint(max_entries, 16384);
__type(key, __u32);
- __u64 (*value)[PERF_MAX_STACK_DEPTH];
+ __type(value, stack_trace_t);
} stack_amap SEC(".maps");
/* taken from /sys/kernel/debug/tracing/events/sched/sched_switch/format */
--
2.17.1
^ permalink raw reply related [flat|nested] 7+ messages in thread* Re: [PATCH v3 bpf 0/3] fix BTF verification size resolution
2019-07-12 17:25 [PATCH v3 bpf 0/3] fix BTF verification size resolution Andrii Nakryiko
` (2 preceding siblings ...)
2019-07-12 17:25 ` [PATCH v3 bpf 3/3] selftests/bpf: use typedef'ed arrays as map values Andrii Nakryiko
@ 2019-07-12 18:47 ` Yonghong Song
2019-07-15 22:18 ` Daniel Borkmann
4 siblings, 0 replies; 7+ messages in thread
From: Yonghong Song @ 2019-07-12 18:47 UTC (permalink / raw)
To: Andrii Nakryiko, bpf, netdev, Alexei Starovoitov, daniel
Cc: andrii.nakryiko, Kernel Team
On 7/12/19 10:25 AM, Andrii Nakryiko wrote:
> BTF size resolution logic isn't always resolving type size correctly, leading
> to erroneous map creation failures due to value size mismatch.
>
> This patch set:
> 1. fixes the issue (patch #1);
> 2. adds tests for trickier cases (patch #2);
> 3. and converts few test cases utilizing BTF-defined maps, that previously
> couldn't use typedef'ed arrays due to kernel bug (patch #3).
>
> Andrii Nakryiko (3):
> bpf: fix BTF verifier size resolution logic
> selftests/bpf: add trickier size resolution tests
> selftests/bpf: use typedef'ed arrays as map values
Looks good to me. Ack for the whole series.
Acked-by: Yonghong Song <yhs@fb.com>
>
> kernel/bpf/btf.c | 19 ++--
> .../bpf/progs/test_get_stack_rawtp.c | 3 +-
> .../bpf/progs/test_stacktrace_build_id.c | 3 +-
> .../selftests/bpf/progs/test_stacktrace_map.c | 2 +-
> tools/testing/selftests/bpf/test_btf.c | 88 +++++++++++++++++++
> 5 files changed, 104 insertions(+), 11 deletions(-)
>
^ permalink raw reply [flat|nested] 7+ messages in thread* Re: [PATCH v3 bpf 0/3] fix BTF verification size resolution
2019-07-12 17:25 [PATCH v3 bpf 0/3] fix BTF verification size resolution Andrii Nakryiko
` (3 preceding siblings ...)
2019-07-12 18:47 ` [PATCH v3 bpf 0/3] fix BTF verification size resolution Yonghong Song
@ 2019-07-15 22:18 ` Daniel Borkmann
4 siblings, 0 replies; 7+ messages in thread
From: Daniel Borkmann @ 2019-07-15 22:18 UTC (permalink / raw)
To: Andrii Nakryiko, bpf, netdev, ast, yhs; +Cc: andrii.nakryiko, kernel-team
On 7/12/19 7:25 PM, Andrii Nakryiko wrote:
> BTF size resolution logic isn't always resolving type size correctly, leading
> to erroneous map creation failures due to value size mismatch.
>
> This patch set:
> 1. fixes the issue (patch #1);
> 2. adds tests for trickier cases (patch #2);
> 3. and converts few test cases utilizing BTF-defined maps, that previously
> couldn't use typedef'ed arrays due to kernel bug (patch #3).
>
> Andrii Nakryiko (3):
> bpf: fix BTF verifier size resolution logic
> selftests/bpf: add trickier size resolution tests
> selftests/bpf: use typedef'ed arrays as map values
>
> kernel/bpf/btf.c | 19 ++--
> .../bpf/progs/test_get_stack_rawtp.c | 3 +-
> .../bpf/progs/test_stacktrace_build_id.c | 3 +-
> .../selftests/bpf/progs/test_stacktrace_map.c | 2 +-
> tools/testing/selftests/bpf/test_btf.c | 88 +++++++++++++++++++
> 5 files changed, 104 insertions(+), 11 deletions(-)
>
Applied, thanks!
^ permalink raw reply [flat|nested] 7+ messages in thread