Ensure that there can be no ownership cycles among different types by
way of having owning objects that can hold some other type as their
element. For instance, a map value can only hold local kptrs, but these
are allowed to have another bpf_list_head. To prevent unbounded
recursion while freeing resources, elements of bpf_list_head in local
kptrs can never have a bpf_list_head which are part of list in a map
value.
Also, to make runtime destruction easier, once btf_struct_metas is fully
populated, we can stash the metadata of the value type directly in the
metadata of the list_head fields, as that allows easier access to the
value type's layout to destruct it at runtime from the btf_field entry
of the list head itself.
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@xxxxxxxxx>
---
include/linux/bpf.h | 1 +
include/linux/btf.h | 1 +
kernel/bpf/btf.c | 71 ++++++++++++++++++++++++++++++++++++++++++++
kernel/bpf/syscall.c | 4 +++
4 files changed, 77 insertions(+)
diff --git a/include/linux/bpf.h b/include/linux/bpf.h
index 76548a9d57db..b2419752542a 100644
--- a/include/linux/bpf.h
+++ b/include/linux/bpf.h
@@ -192,6 +192,7 @@ struct btf_field_list_head {
struct btf *btf;
u32 value_btf_id;
u32 node_offset;
+ struct btf_type_fields *value_tab;
};
struct btf_field {
diff --git a/include/linux/btf.h b/include/linux/btf.h
index b63c88de3135..4492636c3571 100644
--- a/include/linux/btf.h
+++ b/include/linux/btf.h
@@ -179,6 +179,7 @@ int btf_find_timer(const struct btf *btf, const struct btf_type *t);
struct btf_type_fields *btf_parse_fields(const struct btf *btf,
const struct btf_type *t,
u32 field_mask, u32 value_size);
+int btf_check_and_fixup_fields(const struct btf *btf, struct btf_type_fields *tab);
struct btf_type_fields_off *btf_parse_fields_off(struct btf_type_fields *tab);
bool btf_type_is_void(const struct btf_type *t);
s32 btf_find_by_name_kind(const struct btf *btf, const char *name, u8 kind);
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index d6aeb0a4d4b7..c038ba873ba4 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -3730,6 +3730,67 @@ struct btf_type_fields *btf_parse_fields(const struct btf *btf,
return ERR_PTR(ret);
}
+int btf_check_and_fixup_fields(const struct btf *btf, struct btf_type_fields *tab)
+{
+ int i;
+
+ /* There are two owning types, kptr_ref and bpf_list_head. The former
+ * only supports storing kernel types, which can never store references
+ * to program allocated local types, atleast not yet. Hence we only need
+ * to ensure that bpf_list_head ownership does not form cycles.
+ */
+ if (IS_ERR_OR_NULL(tab) || !(tab->field_mask & BPF_LIST_HEAD))
+ return 0;
+ for (i = 0; i < tab->cnt; i++) {
+ struct btf_struct_meta *meta;
+ u32 btf_id;
+
+ if (!(tab->fields[i].type & BPF_LIST_HEAD))
+ continue;
+ btf_id = tab->fields[i].list_head.value_btf_id;
+ meta = btf_find_struct_meta(btf, btf_id);
+ if (!meta)
+ return -EFAULT;
+ tab->fields[i].list_head.value_tab = meta->fields_tab;
+
+ if (!(tab->field_mask & BPF_LIST_NODE))
+ continue;
+
+ /* We need to ensure ownership acyclicity among all types. The
+ * proper way to do it would be to topologically sort all BTF
+ * IDs based on the ownership edges, since there can be multiple
+ * bpf_list_head in a type. Instead, we use the following
+ * reasoning:
+ *
+ * - A type can only be owned by another type in user BTF if it
+ * has a bpf_list_node.
+ * - A type can only _own_ another type in user BTF if it has a
+ * bpf_list_head.
+ *
+ * We ensure that if a type has both bpf_list_head and
+ * bpf_list_node, its element types cannot be owning types.
+ *
+ * To ensure acyclicity:
+ *
+ * When A only has bpf_list_head, ownership chain can be:
+ * A -> B -> C
+ * Where:
+ * - B has both bpf_list_head and bpf_list_node.
+ * - C only has bpf_list_node.
+ *
+ * When A has both bpf_list_head and bpf_list_node, some other
+ * type already owns it in the BTF domain, hence it can not own
+ * another owning type through any of the bpf_list_head edges.
+ * A -> B
+ * Where:
+ * - B only has bpf_list_node.
+ */
+ if (meta->fields_tab->field_mask & BPF_LIST_HEAD)
+ return -ELOOP;
+ }
+ return 0;
+}
+
static int btf_type_fields_off_cmp(const void *_a, const void *_b, const void *priv)
{
const u32 a = *(const u32 *)_a;
@@ -5414,6 +5475,16 @@ static struct btf *btf_parse(bpfptr_t btf_data, u32 btf_data_size,
}
btf->struct_meta_tab = struct_meta_tab;
+ if (struct_meta_tab) {
+ int i;
+
+ for (i = 0; i < struct_meta_tab->cnt; i++) {
+ err = btf_check_and_fixup_fields(btf, struct_meta_tab->types[i].fields_tab);
+ if (err < 0)
+ goto errout_meta;
+ }
+ }
+
if (log->level && bpf_verifier_log_full(log)) {
err = -ENOSPC;
goto errout_meta;
diff --git a/kernel/bpf/syscall.c b/kernel/bpf/syscall.c
index c60bf641301d..c8e1bdcbc205 100644
--- a/kernel/bpf/syscall.c
+++ b/kernel/bpf/syscall.c
@@ -1043,6 +1043,10 @@ static int map_check_btf(struct bpf_map *map, const struct btf *btf,
}
}
+ ret = btf_check_and_fixup_fields(btf, map->fields_tab);
+ if (ret < 0)
+ goto free_map_tab;
+
if (map->ops->map_check_btf) {
ret = map->ops->map_check_btf(map, btf, key_type, value_type);
if (ret < 0)
--
2.34.1
