| Message ID | 20190711065307.2425636-2-andriin@fb.com |
|---|---|
| State | Changes Requested |
| Delegated to: | BPF Maintainers |
| Headers | show |
| Series | fix BTF verification size resolution | expand |
On 7/10/19 11:53 PM, 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). > > 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 | 14 ++++++++++---- > 1 file changed, 10 insertions(+), 4 deletions(-) > > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c > index cad09858a5f2..22fe8b155e51 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; Looks good to me. Not sure whether we need to do any adjustment for var kind or not. Maybe we can do similar change in btf_var_resolve() to btf_modifier_resolve()? But I do not think it impacts correctness similar to btf_modifier_resolve() below as you changed btf_type_id_size() implementation in the above. > } > > *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; > } >
On Thu, Jul 11, 2019 at 10:59 PM Yonghong Song <yhs@fb.com> wrote: > > > > On 7/10/19 11:53 PM, 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). > > > > 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 | 14 ++++++++++---- > > 1 file changed, 10 insertions(+), 4 deletions(-) > > > > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c > > index cad09858a5f2..22fe8b155e51 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; > > Looks good to me. Not sure whether we need to do any adjustment for > var kind or not. Maybe we can do similar change in btf_var_resolve() I don't think btf_var_resolve() needs any change. btf_var_resolve can't be referenced by modifier, so it doesn't have any problem. It's similar to array in that it's size will be determined correctly. But I think btf_type_id_size() doesn't handle var case correctly, I'll do + else if (btf_type_is_array(size_type) || btf_type_is_var(size_type)) + size = btf->resolved_sizes[size_type_id]; to fix that. > to btf_modifier_resolve()? But I do not think it impacts correctness > similar to btf_modifier_resolve() below as you changed > btf_type_id_size() implementation in the above. > > > } > > > > *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; > > } > >
On 7/12/19 8:36 AM, Andrii Nakryiko wrote: > On Thu, Jul 11, 2019 at 10:59 PM Yonghong Song <yhs@fb.com> wrote: >> >> >> >> On 7/10/19 11:53 PM, 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). >>> >>> 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 | 14 ++++++++++---- >>> 1 file changed, 10 insertions(+), 4 deletions(-) >>> >>> diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c >>> index cad09858a5f2..22fe8b155e51 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; >> >> Looks good to me. Not sure whether we need to do any adjustment for >> var kind or not. Maybe we can do similar change in btf_var_resolve() > > I don't think btf_var_resolve() needs any change. btf_var_resolve > can't be referenced by modifier, so it doesn't have any problem. It's > similar to array in that it's size will be determined correctly. Correct. With your previous patch, the resolved_sizes[..] for var type is not used, so that is why I suggest to just set it to 0. > > But I think btf_type_id_size() doesn't handle var case correctly, I'll do > > + else if (btf_type_is_array(size_type) || > btf_type_is_var(size_type)) > + size = btf->resolved_sizes[size_type_id]; This change should work too (to use btf->resolved_sizes[...]). > > to fix that. > >> to btf_modifier_resolve()? But I do not think it impacts correctness >> similar to btf_modifier_resolve() below as you changed >> btf_type_id_size() implementation in the above. >> >>> } >>> >>> *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; >>> } >>>
On Fri, Jul 12, 2019 at 8:47 AM Yonghong Song <yhs@fb.com> wrote: > > > > On 7/12/19 8:36 AM, Andrii Nakryiko wrote: > > On Thu, Jul 11, 2019 at 10:59 PM Yonghong Song <yhs@fb.com> wrote: > >> > >> > >> > >> On 7/10/19 11:53 PM, 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). > >>> > >>> 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 | 14 ++++++++++---- > >>> 1 file changed, 10 insertions(+), 4 deletions(-) > >>> > >>> diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c > >>> index cad09858a5f2..22fe8b155e51 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; > >> > >> Looks good to me. Not sure whether we need to do any adjustment for > >> var kind or not. Maybe we can do similar change in btf_var_resolve() > > > > I don't think btf_var_resolve() needs any change. btf_var_resolve > > can't be referenced by modifier, so it doesn't have any problem. It's > > similar to array in that it's size will be determined correctly. > > Correct. With your previous patch, the resolved_sizes[..] for var type > is not used, so that is why I suggest to just set it to 0. Ah, sorry, I misunderstood your initial suggestion. Yes, resolved_sizes for VAR is not used anymore, so yeah, I'll set it to zero. > > > > > But I think btf_type_id_size() doesn't handle var case correctly, I'll do > > > > + else if (btf_type_is_array(size_type) || > > btf_type_is_var(size_type)) > > + size = btf->resolved_sizes[size_type_id]; > > This change should work too (to use btf->resolved_sizes[...]). Reading code again, VAR's size is handled similar to modifier's size, so I won't change btf_type_id_size(). Posting v3 soon. > > > > > to fix that. > > > >> to btf_modifier_resolve()? But I do not think it impacts correctness > >> similar to btf_modifier_resolve() below as you changed > >> btf_type_id_size() implementation in the above. > >> > >>> } > >>> > >>> *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; > >>> } > >>>
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c index cad09858a5f2..22fe8b155e51 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; }
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 | 14 ++++++++++---- 1 file changed, 10 insertions(+), 4 deletions(-)