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

[Yonghong Song <yhs@fb.com>]

On 4/18/22 1:31 PM, Kumar Kartikeya Dwivedi wrote:
> 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.

I checked and it looks good to me. Right, it would be great if an 
selftest is added for this pattern.

[...]