Skip to contentSkip to conversation

Ensure type tags are always ordered first in BTF

PATCH Superseded Kumar Kartikeya Dwivedi 3 participants 7 messages Apr 6, 2022 – Apr 18, 2022

Subsystems (3)

v1 of 3 Superseded Latest is v3 →

lore
Share & tools
lore

Kumar Kartikeya Dwivedi

author maintainer
#0 lore raw

cover Ensure type tags are always ordered first in BTF

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.

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                             | 51 +++++++++++++
 tools/testing/selftests/bpf/prog_tests/btf.c | 77 ++++++++++++++++++++
 2 files changed, 128 insertions(+)
Signature · 1 line
2.35.1
author maintainer
#1 lore raw

PATCH 1/2 bpf: Ensure type tags precede modifiers in BTF

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.

---
 kernel/bpf/btf.c | 51 ++++++++++++++++++++++++++++++++++++++++++++++++
 1 file changed, 51 insertions(+)
kernel/bpf/btf.c +51 -0
index 0918a39279f6..4a73f5b8127e 100644
@@ -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;
+			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 +4647,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 +4852,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 +4941,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;
Signature · 1 line
2.35.1
#2 lore raw

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

Quoted 53 lines · 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.

---
  kernel/bpf/btf.c | 51 ++++++++++++++++++++++++++++++++++++++++++++++++
  1 file changed, 51 insertions(+)
kernel/bpf/btf.c +20 -0
index 0918a39279f6..4a73f5b8127e 100644
@@ -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)) {

kernel/bpf/btf.c static int btf_parse_hdr(struct btf_verifier_env *env) · line 4573

Quoted 10 lines
kernel/bpf/btf.c +10 -0
+			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.

Quoted 10 lines
kernel/bpf/btf.c +9 -0
+			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,

[...]

author maintainer
#3 lore raw

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

Quoted 79 lines · Yonghong Song
Quoted 52 lines · 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.

---
  kernel/bpf/btf.c | 51 ++++++++++++++++++++++++++++++++++++++++++++++++
  1 file changed, 51 insertions(+)
kernel/bpf/btf.c +20 -0
index 0918a39279f6..4a73f5b8127e 100644
@@ -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)) {

kernel/bpf/btf.c static int btf_parse_hdr(struct btf_verifier_env *env) · line 4572

Quoted 10 lines
kernel/bpf/btf.c +10 -0
+			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

Quoted 4 lines

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:

kernel/bpf/btf.c +4 -1
index 4a73f5b8127e..c015ccd1c741 100644
@@ -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.

Quoted 11 lines
Quoted 10 lines
kernel/bpf/btf.c +9 -0
+			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

#4 lore raw

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

Quoted 126 lines · Kumar Kartikeya Dwivedi
Quoted 79 lines · Yonghong Song
Quoted 52 lines · 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.

---
   kernel/bpf/btf.c | 51 ++++++++++++++++++++++++++++++++++++++++++++++++
   1 file changed, 51 insertions(+)
kernel/bpf/btf.c +20 -0
index 0918a39279f6..4a73f5b8127e 100644
@@ -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)) {

kernel/bpf/btf.c static int btf_parse_hdr(struct btf_verifier_env *env) · line 4572

Quoted 10 lines
kernel/bpf/btf.c +10 -0
+			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
Quoted 4 lines

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:

kernel/bpf/btf.c +4 -2
index 4a73f5b8127e..c015ccd1c741 100644
@@ -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;
 
--
Quoted 2 lines

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.

[...]

author maintainer
#5 lore raw

PATCH 2/2 selftests/bpf: Add tests for type tag order validation

In reply to Kumar Kartikeya Dwivedi

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

---
 tools/testing/selftests/bpf/prog_tests/btf.c | 77 ++++++++++++++++++++
 1 file changed, 77 insertions(+)
tools/testing/selftests/bpf/prog_tests/btf.c +77 -0
index ec823561b912..fc18f0936925 100644
@@ -3974,6 +3974,83 @@ 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,
+},
 
 }; /* struct btf_raw_test raw_tests[] */
 
Signature · 1 line
2.35.1
#6 lore raw
In reply to Kumar Kartikeya Dwivedi
Quoted 11 lines · 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.

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

Quoted 7 lines
 kernel/bpf/btf.c                             | 51 +++++++++++++
 tools/testing/selftests/bpf/prog_tests/btf.c | 77 ++++++++++++++++++++
 2 files changed, 128 insertions(+)

--
2.35.1

Yonghong, can you please take a look?