Re: [PATCH bpf-next v1 1/2] bpf: Ensure type tags precede modifiers in BTF

[Kumar Kartikeya Dwivedi <memxor@gmail.com>]

On Tue, Apr 19, 2022 at 01:23:32AM IST, Yonghong Song wrote:
>
>
> On 4/5/22 5:41 PM, Kumar Kartikeya Dwivedi wrote:
> > It is guaranteed that for modifiers, clang always places type tags
> > before other modifiers, and then the base type. We would like to rely on
> > this guarantee inside the kernel to make it simple to parse type tags
> > from BTF.
> >
> > However, a user would be allowed to construct a BTF without such
> > guarantees. Hence, add a pass to check that in modifier chains, type
> > tags only occur at the head of the chain, and then don't occur later in
> > the chain.
> >
> > If we see a type tag, we can have one or more type tags preceding other
> > modifiers that then never have another type tag. If we see other
> > modifiers, all modifiers following them should never be a type tag.
> >
> > Instead of having to walk chains we verified previously, we can remember
> > the last good modifier type ID which headed a good chain. At that point,
> > we must have verified all other chains headed by type IDs less than it.
> > This makes the verification process less costly, and it becomes a simple
> > O(n) pass.
> >
> > Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
> > ---
> >   kernel/bpf/btf.c | 51 ++++++++++++++++++++++++++++++++++++++++++++++++
> >   1 file changed, 51 insertions(+)
> >
> > diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> > index 0918a39279f6..4a73f5b8127e 100644
> > --- a/kernel/bpf/btf.c
> > +++ b/kernel/bpf/btf.c
> > @@ -4541,6 +4541,45 @@ static int btf_parse_hdr(struct btf_verifier_env *env)
> >   	return 0;
> >   }
> > +static int btf_check_type_tags(struct btf_verifier_env *env,
> > +			       struct btf *btf, int start_id)
> > +{
> > +	int i, n, good_id = start_id - 1;
> > +	bool in_tags;
> > +
> > +	n = btf_nr_types(btf);
> > +	for (i = start_id; i < n; i++) {
> > +		const struct btf_type *t;
> > +
> > +		t = btf_type_by_id(btf, i);
> > +		if (!t)
> > +			return -EINVAL;
> > +		if (!btf_type_is_modifier(t))
> > +			continue;
> > +
> > +		cond_resched();
> > +
> > +		in_tags = btf_type_is_type_tag(t);
> > +		while (btf_type_is_modifier(t)) {
> > +			if (btf_type_is_type_tag(t)) {
> > +				if (!in_tags) {
> > +					btf_verifier_log(env, "Type tags don't precede modifiers");
> > +					return -EINVAL;
> > +				}
> > +			} else if (in_tags) {
> > +				in_tags = false;
> > +			}
> > +			if (t->type <= good_id)
> > +				break;
>
> General approach looks good. Currently verifier does assume type_tag
> immediately following ptr type and before all other modifiers we do
> need to ensure
>
> I think we may have an issue here though. Suppose we have the
> following types
>    1 ptr -> 2
>    2 tag -> 3
>    3 const -> 4
>    4 int
>    5 ptr -> 6
>    6 const -> 2
>
> In this particular case, when processing modifier 6, we
> have in_tags is false, but t->type (2) <= good_id (5).
> But this is illegal as we have ptr-> const -> tag -> const -> int.
>

Thanks a lot for catching the bug.

So when we have set a non-zero good_id, we know two things:
If good_id is a type tag, it will be followed by one or more type tag modifiers
and then only non type tag modifiers, else it will only be a series of non type
tag modifiers.

When comparing next type ID (t->type) with good_id, we need to see if it is a
type_tag and compare against in_tags to ensure it can be part of current chain.
So this t->type check needs to be changed to be against current type ID, and
should happen in next loop iteration after in_tags has been checked against 't'.

The following change should fix this:

diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 4a73f5b8127e..c015ccd1c741 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -4550,6 +4550,7 @@ static int btf_check_type_tags(struct btf_verifier_env *env,
        n = btf_nr_types(btf);
        for (i = start_id; i < n; i++) {
                const struct btf_type *t;
+               u32 cur_id = i;

                t = btf_type_by_id(btf, i);
                if (!t)
@@ -4569,8 +4570,10 @@ static int btf_check_type_tags(struct btf_verifier_env *env,
                        } else if (in_tags) {
                                in_tags = false;
                        }
-                       if (t->type <= good_id)
+                       if (cur_id <= good_id)
                                break;
+                       /* Move to next type */
+                       cur_id = t->type;
                        t = btf_type_by_id(btf, t->type);
                        if (!t)
                                return -EINVAL;

--

If it looks good, I can respin with your example added as another test in
selftests.

> > +			t = btf_type_by_id(btf, t->type);
> > +			if (!t)
> > +				return -EINVAL;
> > +		}
> > +		good_id = i;
> > +	}
> > +	return 0;
> > +}
> > +
> >   static struct btf *btf_parse(bpfptr_t btf_data, u32 btf_data_size,
> [...]

--
Kartikeya