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

[Yonghong Song <yhs@fb.com>]

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.

> +			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,
[...]