[PATCH bpf-next v2 0/2] Ensure type tags are always ordered first in BTF

[PATCH bpf-next v2 0/2] Ensure type tags are always ordered first in BTF

[Kumar Kartikeya Dwivedi]

When iterating over modifiers, ensure that type tags can only occur at head of
the chain, and don't occur later, such that checking for them once in the start
tells us there are no more type tags in later modifiers. Clang already ensures
to emit such BTF, but user can craft their own BTF which violates such
assumptions if relied upon in the kernel.

Changelog:
----------
v1 -> v2
v1: https://lore.kernel.org/bpf/20220406004121.282699-1-memxor@gmail.com

 * Fix for bug pointed out by Yonghong
 * Update selftests to include Yonghong's example

Kumar Kartikeya Dwivedi (2):
  bpf: Ensure type tags precede modifiers in BTF
  selftests/bpf: Add tests for type tag order validation

 kernel/bpf/btf.c                             | 54 +++++++++++
 tools/testing/selftests/bpf/prog_tests/btf.c | 99 ++++++++++++++++++++
 2 files changed, 153 insertions(+)

-- 
2.35.1

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

[Kumar Kartikeya Dwivedi]

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 | 54 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 54 insertions(+)

diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 0918a39279f6..c015ccd1c741 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -4541,6 +4541,48 @@ 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;
+		u32 cur_id = i;
+
+		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 (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;
+		}
+		good_id = i;
+	}
+	return 0;
+}
+
 static struct btf *btf_parse(bpfptr_t btf_data, u32 btf_data_size,
 			     u32 log_level, char __user *log_ubuf, u32 log_size)
 {
@@ -4608,6 +4650,10 @@ static struct btf *btf_parse(bpfptr_t btf_data, u32 btf_data_size,
 	if (err)
 		goto errout;
 
+	err = btf_check_type_tags(env, btf, 1);
+	if (err)
+		goto errout;
+
 	if (log->level && bpf_verifier_log_full(log)) {
 		err = -ENOSPC;
 		goto errout;
@@ -4809,6 +4855,10 @@ struct btf *btf_parse_vmlinux(void)
 	if (err)
 		goto errout;
 
+	err = btf_check_type_tags(env, btf, 1);
+	if (err)
+		goto errout;
+
 	/* btf_parse_vmlinux() runs under bpf_verifier_lock */
 	bpf_ctx_convert.t = btf_type_by_id(btf, bpf_ctx_convert_btf_id[0]);
 
@@ -4894,6 +4944,10 @@ static struct btf *btf_parse_module(const char *module_name, const void *data, u
 	if (err)
 		goto errout;
 
+	err = btf_check_type_tags(env, btf, btf_nr_types(base_btf));
+	if (err)
+		goto errout;
+
 	btf_verifier_env_free(env);
 	refcount_set(&btf->refcnt, 1);
 	return btf;
-- 
2.35.1

[PATCH bpf-next v2 2/2] selftests/bpf: Add tests for type tag order validation

[Kumar Kartikeya Dwivedi]

Add a few test cases that ensure we catch cases of badly ordered type
tags in modifier chains.

Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 tools/testing/selftests/bpf/prog_tests/btf.c | 99 ++++++++++++++++++++
 1 file changed, 99 insertions(+)

diff --git a/tools/testing/selftests/bpf/prog_tests/btf.c b/tools/testing/selftests/bpf/prog_tests/btf.c
index 84aae639ddb5..ba5bde53d418 100644
--- a/tools/testing/selftests/bpf/prog_tests/btf.c
+++ b/tools/testing/selftests/bpf/prog_tests/btf.c
@@ -3973,6 +3973,105 @@ static struct btf_raw_test raw_tests[] = {
 	.value_type_id = 1,
 	.max_entries = 1,
 },
+{
+	.descr = "type_tag test #2, type tag order",
+	.raw_types = {
+		BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),	/* [1] */
+		BTF_CONST_ENC(3),				/* [2] */
+		BTF_TYPE_TAG_ENC(NAME_TBD, 1),			/* [3] */
+		BTF_END_RAW,
+	},
+	BTF_STR_SEC("\0tag"),
+	.map_type = BPF_MAP_TYPE_ARRAY,
+	.map_name = "tag_type_check_btf",
+	.key_size = sizeof(int),
+	.value_size = 4,
+	.key_type_id = 1,
+	.value_type_id = 1,
+	.max_entries = 1,
+	.btf_load_err = true,
+	.err_str = "Type tags don't precede modifiers",
+},
+{
+	.descr = "type_tag test #3, type tag order",
+	.raw_types = {
+		BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),	/* [1] */
+		BTF_TYPE_TAG_ENC(NAME_TBD, 3),			/* [2] */
+		BTF_CONST_ENC(4),				/* [3] */
+		BTF_TYPE_TAG_ENC(NAME_TBD, 1),			/* [4] */
+		BTF_END_RAW,
+	},
+	BTF_STR_SEC("\0tag\0tag"),
+	.map_type = BPF_MAP_TYPE_ARRAY,
+	.map_name = "tag_type_check_btf",
+	.key_size = sizeof(int),
+	.value_size = 4,
+	.key_type_id = 1,
+	.value_type_id = 1,
+	.max_entries = 1,
+	.btf_load_err = true,
+	.err_str = "Type tags don't precede modifiers",
+},
+{
+	.descr = "type_tag test #4, type tag order",
+	.raw_types = {
+		BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),	/* [1] */
+		BTF_TYPEDEF_ENC(NAME_TBD, 3),			/* [2] */
+		BTF_CONST_ENC(4),				/* [3] */
+		BTF_TYPE_TAG_ENC(NAME_TBD, 1),			/* [4] */
+		BTF_END_RAW,
+	},
+	BTF_STR_SEC("\0tag\0tag"),
+	.map_type = BPF_MAP_TYPE_ARRAY,
+	.map_name = "tag_type_check_btf",
+	.key_size = sizeof(int),
+	.value_size = 4,
+	.key_type_id = 1,
+	.value_type_id = 1,
+	.max_entries = 1,
+	.btf_load_err = true,
+	.err_str = "Type tags don't precede modifiers",
+},
+{
+	.descr = "type_tag test #5, type tag order",
+	.raw_types = {
+		BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),	/* [1] */
+		BTF_TYPE_TAG_ENC(NAME_TBD, 3),			/* [2] */
+		BTF_CONST_ENC(1),				/* [3] */
+		BTF_TYPE_TAG_ENC(NAME_TBD, 2),			/* [4] */
+		BTF_END_RAW,
+	},
+	BTF_STR_SEC("\0tag\0tag"),
+	.map_type = BPF_MAP_TYPE_ARRAY,
+	.map_name = "tag_type_check_btf",
+	.key_size = sizeof(int),
+	.value_size = 4,
+	.key_type_id = 1,
+	.value_type_id = 1,
+	.max_entries = 1,
+},
+{
+	.descr = "type_tag test #6, type tag order",
+	.raw_types = {
+		BTF_PTR_ENC(2),					/* [1] */
+		BTF_TYPE_TAG_ENC(NAME_TBD, 3),			/* [2] */
+		BTF_CONST_ENC(4),				/* [3] */
+		BTF_TYPE_INT_ENC(0, BTF_INT_SIGNED, 0, 32, 4),  /* [4] */
+		BTF_PTR_ENC(6),					/* [5] */
+		BTF_CONST_ENC(2),				/* [6] */
+		BTF_END_RAW,
+	},
+	BTF_STR_SEC("\0tag"),
+	.map_type = BPF_MAP_TYPE_ARRAY,
+	.map_name = "tag_type_check_btf",
+	.key_size = sizeof(int),
+	.value_size = 4,
+	.key_type_id = 1,
+	.value_type_id = 1,
+	.max_entries = 1,
+	.btf_load_err = true,
+	.err_str = "Type tags don't precede modifiers",
+},
 
 }; /* struct btf_raw_test raw_tests[] */
 
-- 
2.35.1

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

[Yonghong Song]

On 4/18/22 3:47 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>

Ack with a nit below.

Acked-by: Yonghong Song <yhs@fb.com>

> ---
>   kernel/bpf/btf.c | 54 ++++++++++++++++++++++++++++++++++++++++++++++++
>   1 file changed, 54 insertions(+)
> 
> diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
> index 0918a39279f6..c015ccd1c741 100644
> --- a/kernel/bpf/btf.c
> +++ b/kernel/bpf/btf.c
> @@ -4541,6 +4541,48 @@ 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;
> +		u32 cur_id = i;
> +
> +		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 (cur_id <= good_id)
> +				break;
> +			/* Move to next type */
> +			cur_id = t->type;
> +			t = btf_type_by_id(btf, t->type);

t->type can be replaced with cur_id.

> +			if (!t)
> +				return -EINVAL;
> +		}
> +		good_id = i;
> +	}
> +	return 0;
> +}
> +
[...]

Re: [PATCH bpf-next v2 2/2] selftests/bpf: Add tests for type tag order validation

[Yonghong Song]

On 4/18/22 3:47 PM, Kumar Kartikeya Dwivedi wrote:
> Add a few test cases that ensure we catch cases of badly ordered type
> tags in modifier chains.
> 
> Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>

Acked-by: Yonghong Song <yhs@fb.com>