[PATCH RFC bpf-next v1 19/32] bpf: Support bpf_list_head in local kptrs

From: Kumar Kartikeya Dwivedi <memxor@gmail.com>
To: bpf@vger.kernel.org
Cc: Alexei Starovoitov <ast@kernel.org>,
	Andrii Nakryiko <andrii@kernel.org>,
	Daniel Borkmann <daniel@iogearbox.net>,
	Dave Marchevsky <davemarchevsky@fb.com>,
	Delyan Kratunov <delyank@fb.com>
Subject: [PATCH RFC bpf-next v1 19/32] bpf: Support bpf_list_head in local kptrs
Date: Sun,  4 Sep 2022 22:41:32 +0200	[thread overview]
Message-ID: <20220904204145.3089-20-memxor@gmail.com> (raw)
In-Reply-To: <20220904204145.3089-1-memxor@gmail.com>

To support map-in-map style use case, allow embedding a bpf_list_head
inside a allocated kptr representing local type. Now, this is a field
that will actually need explicit action while destructing the object,
i.e. popping off all the nodes owned by the bpf_list_head and then
freeing each one of them. Hence, the destruction state needs tracking
when we are in the phase, and we also need to reject freeing when the
embedded list_head is not destructed.

For now, needs_destruction is false. Future patch will flip it to true
once adding items to such list_head is supported.

Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 include/linux/btf.h                           |  8 ++
 kernel/bpf/btf.c                              | 89 ++++++++++++++++---
 kernel/bpf/helpers.c                          |  8 ++
 kernel/bpf/verifier.c                         |  4 +
 .../testing/selftests/bpf/bpf_experimental.h  |  9 ++
 5 files changed, 106 insertions(+), 12 deletions(-)

diff --git a/include/linux/btf.h b/include/linux/btf.h
index d99cad21e6d9..42c7f0283887 100644
--- a/include/linux/btf.h
+++ b/include/linux/btf.h
@@ -437,6 +437,8 @@ int btf_local_type_has_bpf_list_node(const struct btf *btf,
 				     const struct btf_type *t, u32 *offsetp);
 int btf_local_type_has_bpf_spin_lock(const struct btf *btf,
 				     const struct btf_type *t, u32 *offsetp);
+int btf_local_type_has_bpf_list_head(const struct btf *btf,
+				     const struct btf_type *t, u32 *offsetp);
 bool btf_local_type_has_special_fields(const struct btf *btf,
 				       const struct btf_type *t);
 #else
@@ -489,6 +491,12 @@ static inline int btf_local_type_has_bpf_spin_lock(const struct btf *btf,
 {
 	return -ENOENT;
 }
+static inline int btf_local_type_has_bpf_list_head(const struct btf *btf,
+					           const struct btf_type *t,
+					           u32 *offsetp)
+{
+	return -ENOENT;
+}
 static inline bool btf_local_type_has_special_fields(const struct btf *btf,
 						     const struct btf_type *t)
 {
diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 63193c324898..c8d4513cc73e 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -3185,7 +3185,8 @@ enum btf_field_type {
 	BTF_FIELD_SPIN_LOCK,
 	BTF_FIELD_TIMER,
 	BTF_FIELD_KPTR,
-	BTF_FIELD_LIST_HEAD,
+	BTF_FIELD_LIST_HEAD_MAP,
+	BTF_FIELD_LIST_HEAD_KPTR,
 	BTF_FIELD_LIST_NODE,
 };
 
@@ -3204,6 +3205,7 @@ struct btf_field_info {
 		struct {
 			u32 value_type_id;
 			const char *node_name;
+			enum btf_field_type type;
 		} list_head;
 	};
 };
@@ -3282,9 +3284,11 @@ static const char *btf_find_decl_tag_value(const struct btf *btf,
 	return NULL;
 }
 
-static int btf_find_list_head(const struct btf *btf, const struct btf_type *pt,
-			      int comp_idx, const struct btf_type *t,
-			      u32 off, int sz, struct btf_field_info *info)
+static int btf_find_list_head(const struct btf *btf,
+			      enum btf_field_type field_type,
+			      const struct btf_type *pt, int comp_idx,
+			      const struct btf_type *t, u32 off, int sz,
+			      struct btf_field_info *info)
 {
 	const char *value_type;
 	const char *list_node;
@@ -3316,6 +3320,7 @@ static int btf_find_list_head(const struct btf *btf, const struct btf_type *pt,
 	info->off = off;
 	info->list_head.value_type_id = id;
 	info->list_head.node_name = list_node;
+	info->list_head.type = field_type;
 	return BTF_FIELD_FOUND;
 }
 
@@ -3361,8 +3366,9 @@ static int btf_find_struct_field(const struct btf *btf, const struct btf_type *t
 			if (ret < 0)
 				return ret;
 			break;
-		case BTF_FIELD_LIST_HEAD:
-			ret = btf_find_list_head(btf, t, i, member_type, off, sz,
+		case BTF_FIELD_LIST_HEAD_MAP:
+		case BTF_FIELD_LIST_HEAD_KPTR:
+			ret = btf_find_list_head(btf, field_type, t, i, member_type, off, sz,
 						 idx < info_cnt ? &info[idx] : &tmp);
 			if (ret < 0)
 				return ret;
@@ -3420,8 +3426,9 @@ static int btf_find_datasec_var(const struct btf *btf, const struct btf_type *t,
 			if (ret < 0)
 				return ret;
 			break;
-		case BTF_FIELD_LIST_HEAD:
-			ret = btf_find_list_head(btf, var, -1, var_type, off, sz,
+		case BTF_FIELD_LIST_HEAD_MAP:
+		case BTF_FIELD_LIST_HEAD_KPTR:
+			ret = btf_find_list_head(btf, field_type, var, -1, var_type, off, sz,
 						 idx < info_cnt ? &info[idx] : &tmp);
 			if (ret < 0)
 				return ret;
@@ -3462,7 +3469,8 @@ static int btf_find_field(const struct btf *btf, const struct btf_type *t,
 		sz = sizeof(u64);
 		align = 8;
 		break;
-	case BTF_FIELD_LIST_HEAD:
+	case BTF_FIELD_LIST_HEAD_MAP:
+	case BTF_FIELD_LIST_HEAD_KPTR:
 		name = "bpf_list_head";
 		sz = sizeof(struct bpf_list_head);
 		align = __alignof__(struct bpf_list_head);
@@ -3615,13 +3623,53 @@ struct bpf_map_value_off *btf_parse_kptrs(const struct btf *btf,
 	return ERR_PTR(ret);
 }
 
+static bool list_head_value_ok(const struct btf *btf, const struct btf_type *pt,
+			       const struct btf_type *vt,
+			       enum btf_field_type type)
+{
+	struct btf_field_info info;
+	int ret;
+
+	/* This is the value type of either map or kptr list_head. For map
+	 * list_head, we allow the value_type to have another bpf_list_head, but
+	 * for kptr list_head, we cannot allow another level of list_head.
+	 *
+	 * Also, in the map case, we must catch the case where the value_type's
+	 * list_head encodes the map_value as its own value_type.
+	 *
+	 * Essentially, we want only two levels for map, one level for kptr, and
+	 * no cycles at all in the type graph.
+	 */
+	WARN_ON_ONCE(btf_is_kernel(btf) || !__btf_type_is_struct(vt));
+	ret = btf_find_field(btf, vt, type, "kernel", &info, 1);
+	if (ret < 0)
+		return false;
+	/* For map or kptr, if value doesn't have list_head, it's ok! */
+	if (!ret)
+		return true;
+	if (ret) {
+		/* For kptr, we don't allow list_head in the value type. */
+		if (type == BTF_FIELD_LIST_HEAD_KPTR)
+			return false;
+		/* The map's list_head's value has another list head. We now
+		 * need to ensure it doesn't refer to map value type itself,
+		 * creating a cycle.
+		 */
+		vt = btf_type_by_id(btf, info.list_head.value_type_id);
+		if (vt == pt)
+			return false;
+	}
+	return true;
+}
+
 struct bpf_map_value_off *btf_parse_list_heads(struct btf *btf, const struct btf_type *t)
 {
 	struct btf_field_info info_arr[BPF_MAP_VALUE_OFF_MAX];
 	struct bpf_map_value_off *tab;
+	const struct btf_type *pt = t;
 	int ret, i, nr_off;
 
-	ret = btf_find_field(btf, t, BTF_FIELD_LIST_HEAD, NULL, info_arr, ARRAY_SIZE(info_arr));
+	ret = btf_find_field(btf, t, BTF_FIELD_LIST_HEAD_MAP, NULL, info_arr, ARRAY_SIZE(info_arr));
 	if (ret < 0)
 		return ERR_PTR(ret);
 	if (!ret)
@@ -3644,6 +3692,8 @@ struct bpf_map_value_off *btf_parse_list_heads(struct btf *btf, const struct btf
 		 * verify its type.
 		 */
 		ret = -EINVAL;
+		if (!list_head_value_ok(btf, pt, t, BTF_FIELD_LIST_HEAD_MAP))
+			goto end;
 		for_each_member(j, t, member) {
 			if (strcmp(info_arr[i].list_head.node_name, __btf_name_by_offset(btf, member->name_off)))
 				continue;
@@ -5937,12 +5987,19 @@ static int btf_find_local_type_field(const struct btf *btf,
 	int ret;
 
 	/* These are invariants that must hold if this is a local type */
-	WARN_ON_ONCE(btf_is_kernel(btf) || !__btf_type_is_struct(t));
+	WARN_ON_ONCE(btf_is_kernel(btf) || !__btf_type_is_struct(t) || type == BTF_FIELD_LIST_HEAD_MAP);
 	ret = btf_find_field(btf, t, type, "kernel", &info, 1);
 	if (ret < 0)
 		return ret;
 	if (!ret)
 		return 0;
+	/* A validation step needs to be done for bpf_list_head in local kptrs */
+	if (type == BTF_FIELD_LIST_HEAD_KPTR) {
+		const struct btf_type *vt = btf_type_by_id(btf, info.list_head.value_type_id);
+
+		if (!list_head_value_ok(btf, t, vt, type))
+			return -EINVAL;
+	}
 	if (offsetp)
 		*offsetp = info.off;
 	return ret;
@@ -5960,10 +6017,17 @@ int btf_local_type_has_bpf_spin_lock(const struct btf *btf,
 	return btf_find_local_type_field(btf, t, BTF_FIELD_SPIN_LOCK, offsetp);
 }
 
+int btf_local_type_has_bpf_list_head(const struct btf *btf,
+				     const struct btf_type *t, u32 *offsetp)
+{
+	return btf_find_local_type_field(btf, t, BTF_FIELD_LIST_HEAD_KPTR, offsetp);
+}
+
 bool btf_local_type_has_special_fields(const struct btf *btf, const struct btf_type *t)
 {
 	return btf_local_type_has_bpf_list_node(btf, t, NULL) == 1 ||
-	       btf_local_type_has_bpf_spin_lock(btf, t, NULL) == 1;
+	       btf_local_type_has_bpf_spin_lock(btf, t, NULL) == 1 ||
+	       btf_local_type_has_bpf_list_head(btf, t, NULL) == 1;
 }
 
 int btf_struct_access(struct bpf_verifier_log *log, const struct btf *btf,
@@ -5993,6 +6057,7 @@ int btf_struct_access(struct bpf_verifier_log *log, const struct btf *btf,
 	}
 		PREVENT_DIRECT_WRITE(bpf_list_node);
 		PREVENT_DIRECT_WRITE(bpf_spin_lock);
+		PREVENT_DIRECT_WRITE(bpf_list_head);
 
 #undef PREVENT_DIRECT_WRITE
 		err = 0;
diff --git a/kernel/bpf/helpers.c b/kernel/bpf/helpers.c
index 94a23a544aee..8eee0793c7f1 100644
--- a/kernel/bpf/helpers.c
+++ b/kernel/bpf/helpers.c
@@ -1724,6 +1724,13 @@ void bpf_spin_lock_init(struct bpf_spin_lock *lock__clkptr)
 	memset(lock__clkptr, 0, sizeof(*lock__clkptr));
 }
 
+void bpf_list_head_init(struct bpf_list_head *head__clkptr)
+{
+	BUILD_BUG_ON(sizeof(struct bpf_list_head) != sizeof(struct list_head));
+	BUILD_BUG_ON(__alignof__(struct bpf_list_head) != __alignof__(struct list_head));
+	INIT_LIST_HEAD((struct list_head *)head__clkptr);
+}
+
 __diag_pop();
 
 BTF_SET8_START(tracing_btf_ids)
@@ -1733,6 +1740,7 @@ BTF_ID_FLAGS(func, crash_kexec, KF_DESTRUCTIVE)
 BTF_ID_FLAGS(func, bpf_kptr_alloc, KF_ACQUIRE | KF_RET_NULL | __KF_RET_DYN_BTF)
 BTF_ID_FLAGS(func, bpf_list_node_init)
 BTF_ID_FLAGS(func, bpf_spin_lock_init)
+BTF_ID_FLAGS(func, bpf_list_head_init)
 BTF_SET8_END(tracing_btf_ids)
 
 static const struct btf_kfunc_id_set tracing_kfunc_set = {
diff --git a/kernel/bpf/verifier.c b/kernel/bpf/verifier.c
index 130a4f0550f5..a5aa5de4b246 100644
--- a/kernel/bpf/verifier.c
+++ b/kernel/bpf/verifier.c
@@ -7811,12 +7811,14 @@ BTF_ID_LIST(special_kfuncs)
 BTF_ID(func, bpf_kptr_alloc)
 BTF_ID(func, bpf_list_node_init)
 BTF_ID(func, bpf_spin_lock_init)
+BTF_ID(func, bpf_list_head_init)
 BTF_ID(struct, btf) /* empty entry */
 
 enum bpf_special_kfuncs {
 	KF_SPECIAL_bpf_kptr_alloc,
 	KF_SPECIAL_bpf_list_node_init,
 	KF_SPECIAL_bpf_spin_lock_init,
+	KF_SPECIAL_bpf_list_head_init,
 	KF_SPECIAL_bpf_empty,
 	KF_SPECIAL_MAX = KF_SPECIAL_bpf_empty,
 };
@@ -7984,6 +7986,7 @@ struct local_type_field {
 	enum {
 		FIELD_bpf_list_node,
 		FIELD_bpf_spin_lock,
+		FIELD_bpf_list_head,
 		FIELD_MAX,
 	} type;
 	enum bpf_special_kfuncs ctor_kfunc;
@@ -8030,6 +8033,7 @@ static int find_local_type_fields(const struct btf *btf, u32 btf_id, struct loca
 
 	FILL_LOCAL_TYPE_FIELD(bpf_list_node, bpf_list_node_init, bpf_empty, false);
 	FILL_LOCAL_TYPE_FIELD(bpf_spin_lock, bpf_spin_lock_init, bpf_empty, false);
+	FILL_LOCAL_TYPE_FIELD(bpf_list_head, bpf_list_head_init, bpf_empty, false);
 
 #undef FILL_LOCAL_TYPE_FIELD
 
diff --git a/tools/testing/selftests/bpf/bpf_experimental.h b/tools/testing/selftests/bpf/bpf_experimental.h
index 8b1cdfb2f6bc..f0b6e92c6908 100644
--- a/tools/testing/selftests/bpf/bpf_experimental.h
+++ b/tools/testing/selftests/bpf/bpf_experimental.h
@@ -50,4 +50,13 @@ void bpf_list_node_init(struct bpf_list_node *node) __ksym;
  */
 void bpf_spin_lock_init(struct bpf_spin_lock *node) __ksym;
 
+/* Description
+ *	Initialize bpf_list_head field in a local kptr. This kfunc has
+ *	constructor semantics, and thus can only be called on a local kptr in
+ *	'constructing' phase.
+ * Returns
+ *	Void.
+ */
+void bpf_list_head_init(struct bpf_list_head *node) __ksym;
+
 #endif
-- 
2.34.1

