[PATCH bpf-next v1 0/3] Fix acyclic ownership checks

[PATCH bpf-next v1 0/3] Fix acyclic ownership checks

[Kumar Kartikeya Dwivedi]

Bound and ensure acyclic ownership graphs for native data structures to
fix a bug reported by Nicholas. See commit logs and tests for details.

Kumar Kartikeya Dwivedi (3):
  bpf: Validate graph ownership with a bounded walk
  bpf: Bound local kptr ownership depth
  selftests/bpf: Check local object ownership depth

 kernel/bpf/btf.c                              | 134 +++++++-----
 .../selftests/bpf/prog_tests/linked_list.c    |   4 +-
 .../bpf/prog_tests/local_kptr_ownership.c     | 202 ++++++++++++++++++
 3 files changed, 290 insertions(+), 50 deletions(-)
 create mode 100644 tools/testing/selftests/bpf/prog_tests/local_kptr_ownership.c


base-commit: 3ccdb07813829ba9487273e75d1cb238cfa774c1
-- 
2.53.0

[PATCH bpf-next v1 1/3] bpf: Validate graph ownership with a bounded walk

[Kumar Kartikeya Dwivedi]

btf_check_and_fixup_fields() prevents graph ownership cycles with a
one-hop restriction: a type that contains both a graph root and node cannot
own another root type. This limits graph ownership chains to three types,
but also rejects longer acyclic relationships.

All struct metadata is available once field fixups finish. Move ownership
validation out of the per-record fixup helper and walk graph-root type
relationships directly at BTF load time. Reject cycles and chains deeper
than eight record-bearing types, which keeps recursive destruction bounded
while permitting safe acyclic layouts.

Keep the depth limit independent of MAX_CALL_FRAMES because graph teardown
can run beneath a BPF call chain. btf_check_and_fixup_fields() continues to
initialize graph_root.value_rec, including for the separately allocated map
record. The ownership relationship itself belongs to the immutable BTF and
therefore only needs validation once during BTF load.

Update the graph BTF tests to accept the two acyclic relationships that the
old approximation rejected.

Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 kernel/bpf/btf.c                              | 126 +++++++++++-------
 .../selftests/bpf/prog_tests/linked_list.c    |   4 +-
 2 files changed, 80 insertions(+), 50 deletions(-)

diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 9c2cab08bb79..2a458499a236 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -4269,13 +4269,10 @@ int btf_check_and_fixup_fields(const struct btf *btf, struct btf_record *rec)
 {
 	int i;
 
-	/* There are three types that signify ownership of some other type:
-	 *  kptr_ref, bpf_list_head, bpf_rb_root.
-	 * kptr_ref only supports storing kernel types, which can't store
-	 * references to program allocated local types.
-	 *
-	 * Hence we only need to ensure that bpf_{list_head,rb_root} ownership
-	 * does not form cycles.
+	/*
+	 * Check fields which require the complete BTF and initialize runtime
+	 * metadata. Ownership relationships are validated after every record has
+	 * been fixed up.
 	 */
 	if (IS_ERR_OR_NULL(rec) || !(rec->field_mask & (BPF_GRAPH_ROOT | BPF_UPTR)))
 		return 0;
@@ -4306,51 +4303,80 @@ int btf_check_and_fixup_fields(const struct btf *btf, struct btf_record *rec)
 		if (!meta)
 			return -EFAULT;
 		rec->fields[i].graph_root.value_rec = meta->record;
+	}
+	return 0;
+}
 
-		/* We need to set value_rec for all root types, but no need
-		 * to check ownership cycle for a type unless it's also a
-		 * node type.
-		 */
-		if (!(rec->field_mask & BPF_GRAPH_NODE))
+static int btf_owned_type_idx(const struct btf *btf, struct btf_struct_metas *tab,
+			      const struct btf_field *field)
+{
+	struct btf_struct_meta *meta;
+	u32 btf_id;
+
+	if (!(field->type & BPF_GRAPH_ROOT))
+		return -ENOENT;
+	btf_id = field->graph_root.value_btf_id;
+	meta = btf_find_struct_meta(btf, btf_id);
+	if (!meta)
+		return -EFAULT;
+	return meta - tab->types;
+}
+
+/*
+ * Each graph ownership edge adds kernel frames through
+ * bpf_obj_free_fields() and __bpf_obj_drop_impl(). Keep the bound
+ * deliberately small because object destruction can itself run below a BPF
+ * call chain.
+ */
+#define BTF_MAX_OWNERSHIP_DEPTH 8
+
+static int btf_ownership_depth(const struct btf *btf,
+			       struct btf_struct_metas *tab, u8 *depth,
+			       int idx, int depth_left)
+{
+	const struct btf_record *rec = tab->types[idx].record;
+	int i, ret, max_depth = 0;
+
+	if (!depth_left)
+		return -ELOOP;
+	if (depth[idx])
+		goto done;
+
+	for (i = 0; i < rec->cnt; i++) {
+		ret = btf_owned_type_idx(btf, tab, &rec->fields[i]);
+		if (ret == -ENOENT)
 			continue;
+		if (ret < 0)
+			return ret;
+		ret = btf_ownership_depth(btf, tab, depth, ret, depth_left - 1);
+		if (ret < 0)
+			return ret;
+		max_depth = max(max_depth, ret);
+	}
+	depth[idx] = max_depth + 1;
+done:
+	return depth[idx] > depth_left ? -ELOOP : depth[idx];
+}
 
-		/* 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,rb_node} in a type. Instead, we use the
-		 * following resaoning:
-		 *
-		 * - A type can only be owned by another type in user BTF if it
-		 *   has a bpf_{list,rb}_node. Let's call these node types.
-		 * - A type can only _own_ another type in user BTF if it has a
-		 *   bpf_{list_head,rb_root}. Let's call these root types.
-		 *
-		 * We ensure that if a type is both a root and node, its
-		 * element types cannot be root types.
-		 *
-		 * To ensure acyclicity:
-		 *
-		 * When A is an root type but not a node, its ownership
-		 * chain can be:
-		 *	A -> B -> C
-		 * Where:
-		 * - A is an root, e.g. has bpf_rb_root.
-		 * - B is both a root and node, e.g. has bpf_rb_node and
-		 *   bpf_list_head.
-		 * - C is only an root, e.g. has bpf_list_node
-		 *
-		 * When A is both a root and node, some other type already
-		 * owns it in the BTF domain, hence it can not own
-		 * another root type through any of the ownership edges.
-		 *	A -> B
-		 * Where:
-		 * - A is both an root and node.
-		 * - B is only an node.
-		 */
-		if (meta->record->field_mask & BPF_GRAPH_ROOT)
-			return -ELOOP;
+static int btf_check_ownership_depth(const struct btf *btf,
+				     struct btf_struct_metas *tab)
+{
+	u8 *depth;
+	int i, ret = 0;
+
+	depth = kvcalloc(tab->cnt, sizeof(*depth), GFP_KERNEL | __GFP_NOWARN);
+	if (!depth)
+		return -ENOMEM;
+
+	for (i = 0; i < tab->cnt; i++) {
+		ret = btf_ownership_depth(btf, tab, depth, i,
+					  BTF_MAX_OWNERSHIP_DEPTH);
+		if (ret < 0)
+			break;
+		ret = 0;
 	}
-	return 0;
+	kvfree(depth);
+	return ret;
 }
 
 static void __btf_struct_show(const struct btf *btf, const struct btf_type *t,
@@ -6045,6 +6071,10 @@ static struct btf *btf_parse(const union bpf_attr *attr, bpfptr_t uattr,
 			if (err < 0)
 				goto errout_meta;
 		}
+
+		err = btf_check_ownership_depth(btf, struct_meta_tab);
+		if (err < 0)
+			goto errout_meta;
 	}
 
 	err = bpf_log_attr_finalize(attr_log, &env->log);
diff --git a/tools/testing/selftests/bpf/prog_tests/linked_list.c b/tools/testing/selftests/bpf/prog_tests/linked_list.c
index c3d133c6a00d..52fabbee3dd5 100644
--- a/tools/testing/selftests/bpf/prog_tests/linked_list.c
+++ b/tools/testing/selftests/bpf/prog_tests/linked_list.c
@@ -714,7 +714,7 @@ static void test_btf(void)
 			break;
 
 		err = btf__load_into_kernel(btf);
-		ASSERT_EQ(err, -ELOOP, "check btf");
+		ASSERT_EQ(err, 0, "check btf");
 		btf__free(btf);
 		break;
 	}
@@ -773,7 +773,7 @@ static void test_btf(void)
 			break;
 
 		err = btf__load_into_kernel(btf);
-		ASSERT_EQ(err, -ELOOP, "check btf");
+		ASSERT_EQ(err, 0, "check btf");
 		btf__free(btf);
 		break;
 	}
-- 
2.53.0

[PATCH bpf-next v1 2/3] bpf: Bound local kptr ownership depth

[Kumar Kartikeya Dwivedi]

Program BTF records can own other program-allocated objects through local
referenced kptrs. Releasing such an object follows the kptr through
bpf_obj_free_fields() and __bpf_obj_drop_impl().

The ownership graph walk only follows list and rbtree roots because
referenced kptrs originally supported kernel types with registered
destructors. Support for exchanging program-allocated objects into local
kptrs invalidated that assumption. A self-referential local kptr lets a
CAP_BPF user build an arbitrarily deep object chain, and dropping its head
can exhaust the kernel stack and panic the kernel. A sufficiently long
acyclic chain has the same problem.

Extend the bounded ownership walk to program-local referenced kptrs. A
pointee without special fields is absent from the struct metadata table and
adds only a final non-recursing drop.

Also include local percpu kptrs even though bpf_percpu_obj_new() currently
rejects types with special-field metadata. Rejecting unsafe ownership graphs
now keeps the depth invariant intact if that restriction is relaxed later.
Kernel-BTF kptrs remain outside the walk because they do not recurse through
program BTF records.

Fixes: b0966c724584 ("bpf: Support bpf_kptr_xchg into local kptr")
Reported-by: Nicholas Carlini <npc@anthropic.com>
Suggested-by: Nicholas Carlini <npc@anthropic.com>
Signed-off-by: Kumar Kartikeya Dwivedi <memxor@gmail.com>
---
 kernel/bpf/btf.c | 22 +++++++++++++++-------
 1 file changed, 15 insertions(+), 7 deletions(-)

diff --git a/kernel/bpf/btf.c b/kernel/bpf/btf.c
index 2a458499a236..3c508ebb2438 100644
--- a/kernel/bpf/btf.c
+++ b/kernel/bpf/btf.c
@@ -4313,20 +4313,28 @@ static int btf_owned_type_idx(const struct btf *btf, struct btf_struct_metas *ta
 	struct btf_struct_meta *meta;
 	u32 btf_id;
 
-	if (!(field->type & BPF_GRAPH_ROOT))
+	if (field->type & BPF_GRAPH_ROOT) {
+		btf_id = field->graph_root.value_btf_id;
+	} else if (field->type == BPF_KPTR_REF || field->type == BPF_KPTR_PERCPU) {
+		if (btf_is_kernel(field->kptr.btf))
+			return -ENOENT;
+		btf_id = field->kptr.btf_id;
+	} else {
 		return -ENOENT;
-	btf_id = field->graph_root.value_btf_id;
+	}
+
 	meta = btf_find_struct_meta(btf, btf_id);
 	if (!meta)
-		return -EFAULT;
+		return field->type & BPF_GRAPH_ROOT ? -EFAULT : -ENOENT;
 	return meta - tab->types;
 }
 
 /*
- * Each graph ownership edge adds kernel frames through
- * bpf_obj_free_fields() and __bpf_obj_drop_impl(). Keep the bound
- * deliberately small because object destruction can itself run below a BPF
- * call chain.
+ * Each ownership edge adds kernel frames through bpf_obj_free_fields() and
+ * __bpf_obj_drop_impl(). Keep the bound deliberately small because object
+ * destruction can itself run below a BPF call chain. A final pointee without
+ * special fields is not present in the struct metadata table and adds only a
+ * non-recursing drop.
  */
 #define BTF_MAX_OWNERSHIP_DEPTH 8
 
-- 
2.53.0

[PATCH bpf-next v1 3/3] selftests/bpf: Check local object ownership depth

[Kumar Kartikeya Dwivedi]

Build raw program BTF records to exercise local object ownership without
constructing a runtime chain deep enough to threaten the kernel stack.

Cover referenced-kptr and percpu-kptr self-cycles, a two-type cycle, and a
cycle mixing a graph root with a referenced kptr. Also pin the accepted
depth boundary with a terminal plain object. A kernel without the ownership
graph check accepts every cycle and the over-limit chain, while the fix
rejects them with -ELOOP.

Although bpf_percpu_obj_new() currently rejects types with special fields,
require the percpu cycle to fail at BTF load so future support cannot bypass
the ownership bound. Keep a positive control for a non-owning kptr, which
remains outside the ownership graph.

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

diff --git a/tools/testing/selftests/bpf/prog_tests/local_kptr_ownership.c b/tools/testing/selftests/bpf/prog_tests/local_kptr_ownership.c
new file mode 100644
index 000000000000..83674155e3b7
--- /dev/null
+++ b/tools/testing/selftests/bpf/prog_tests/local_kptr_ownership.c
@@ -0,0 +1,202 @@
+// SPDX-License-Identifier: GPL-2.0
+/* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */
+
+#include <bpf/btf.h>
+#include <linux/btf.h>
+#include <test_progs.h>
+
+#define SPIN_LOCK 2
+#define LIST_HEAD 3
+#define LIST_NODE 4
+/* Keep in sync with BTF_MAX_OWNERSHIP_DEPTH. */
+#define MAX_OWNERSHIP_DEPTH 8
+
+static struct btf *init_btf(void)
+{
+	struct btf *btf;
+	int id;
+
+	btf = btf__new_empty();
+	if (!ASSERT_OK_PTR(btf, "btf__new_empty"))
+		return NULL;
+	id = btf__add_int(btf, "int", 4, BTF_INT_SIGNED);
+	if (!ASSERT_EQ(id, 1, "btf__add_int"))
+		goto err_out;
+	id = btf__add_struct(btf, "bpf_spin_lock", 4);
+	if (!ASSERT_EQ(id, SPIN_LOCK, "btf__add_struct bpf_spin_lock"))
+		goto err_out;
+	id = btf__add_struct(btf, "bpf_list_head", 16);
+	if (!ASSERT_EQ(id, LIST_HEAD, "btf__add_struct bpf_list_head"))
+		goto err_out;
+	id = btf__add_struct(btf, "bpf_list_node", 24);
+	if (!ASSERT_EQ(id, LIST_NODE, "btf__add_struct bpf_list_node"))
+		goto err_out;
+	return btf;
+
+err_out:
+	btf__free(btf);
+	return NULL;
+}
+
+static int add_local_kptr(struct btf *btf, int pointee_id, const char *tag)
+{
+	int id;
+
+	id = btf__add_type_tag(btf, tag, pointee_id);
+	if (!ASSERT_GT(id, 0, "btf__add_type_tag"))
+		return id;
+	id = btf__add_ptr(btf, id);
+	ASSERT_GT(id, 0, "btf__add_ptr");
+	return id;
+}
+
+static void test_self_cycle(const char *tag, int expected_err)
+{
+	struct btf *btf;
+	int id, err;
+
+	btf = init_btf();
+	if (!ASSERT_OK_PTR(btf, "init_btf"))
+		return;
+	id = add_local_kptr(btf, 7, tag);
+	if (id <= 0)
+		goto out;
+	id = btf__add_struct(btf, "self_cycle", 8);
+	if (!ASSERT_EQ(id, 7, "btf__add_struct self_cycle"))
+		goto out;
+	err = btf__add_field(btf, "next", 6, 0, 0);
+	if (!ASSERT_OK(err, "btf__add_field self_cycle::next"))
+		goto out;
+
+	err = btf__load_into_kernel(btf);
+	ASSERT_EQ(err, expected_err, "check btf");
+out:
+	btf__free(btf);
+}
+
+static void test_aba_cycle(void)
+{
+	struct btf *btf;
+	int id, err;
+
+	btf = init_btf();
+	if (!ASSERT_OK_PTR(btf, "init_btf"))
+		return;
+	id = add_local_kptr(btf, 10, "kptr");
+	if (id <= 0)
+		goto out;
+	id = add_local_kptr(btf, 9, "kptr");
+	if (id <= 0)
+		goto out;
+	id = btf__add_struct(btf, "cycle_a", 8);
+	if (!ASSERT_EQ(id, 9, "btf__add_struct cycle_a"))
+		goto out;
+	err = btf__add_field(btf, "b", 6, 0, 0);
+	if (!ASSERT_OK(err, "btf__add_field cycle_a::b"))
+		goto out;
+	id = btf__add_struct(btf, "cycle_b", 8);
+	if (!ASSERT_EQ(id, 10, "btf__add_struct cycle_b"))
+		goto out;
+	err = btf__add_field(btf, "a", 8, 0, 0);
+	if (!ASSERT_OK(err, "btf__add_field cycle_b::a"))
+		goto out;
+
+	err = btf__load_into_kernel(btf);
+	ASSERT_EQ(err, -ELOOP, "check btf");
+out:
+	btf__free(btf);
+}
+
+static void test_mixed_cycle(void)
+{
+	struct btf *btf;
+	int id, err;
+
+	btf = init_btf();
+	if (!ASSERT_OK_PTR(btf, "init_btf"))
+		return;
+	id = add_local_kptr(btf, 7, "kptr");
+	if (id <= 0)
+		goto out;
+	id = btf__add_struct(btf, "mixed_owner", 20);
+	if (!ASSERT_EQ(id, 7, "btf__add_struct mixed_owner"))
+		goto out;
+	err = btf__add_field(btf, "root", LIST_HEAD, 0, 0);
+	if (!ASSERT_OK(err, "btf__add_field mixed_owner::root"))
+		goto out;
+	err = btf__add_field(btf, "lock", SPIN_LOCK, 128, 0);
+	if (!ASSERT_OK(err, "btf__add_field mixed_owner::lock"))
+		goto out;
+	id = btf__add_decl_tag(btf, "contains:mixed_node:node", 7, 0);
+	if (!ASSERT_EQ(id, 8, "btf__add_decl_tag mixed_owner"))
+		goto out;
+	id = btf__add_struct(btf, "mixed_node", 32);
+	if (!ASSERT_EQ(id, 9, "btf__add_struct mixed_node"))
+		goto out;
+	err = btf__add_field(btf, "node", LIST_NODE, 0, 0);
+	if (!ASSERT_OK(err, "btf__add_field mixed_node::node"))
+		goto out;
+	err = btf__add_field(btf, "owner", 6, 192, 0);
+	if (!ASSERT_OK(err, "btf__add_field mixed_node::owner"))
+		goto out;
+
+	err = btf__load_into_kernel(btf);
+	ASSERT_EQ(err, -ELOOP, "check btf");
+out:
+	btf__free(btf);
+}
+
+static void test_acyclic_depth(int depth, int expected_err)
+{
+	int ptr_id[MAX_OWNERSHIP_DEPTH + 1];
+	int first_struct_id;
+	struct btf *btf;
+	int id, err, i;
+
+	btf = init_btf();
+	if (!ASSERT_OK_PTR(btf, "init_btf"))
+		return;
+	first_struct_id = 5 + 2 * depth;
+	for (i = 0; i < depth; i++) {
+		ptr_id[i] = add_local_kptr(btf, first_struct_id + i + 1, "kptr");
+		if (ptr_id[i] <= 0)
+			goto out;
+	}
+	for (i = 0; i < depth; i++) {
+		char name[16];
+
+		snprintf(name, sizeof(name), "owner_%d", i);
+		id = btf__add_struct(btf, name, 8);
+		if (!ASSERT_EQ(id, first_struct_id + i, "btf__add_struct owner"))
+			goto out;
+		err = btf__add_field(btf, "next", ptr_id[i], 0, 0);
+		if (!ASSERT_OK(err, "btf__add_field owner::next"))
+			goto out;
+	}
+	id = btf__add_struct(btf, "plain_leaf", 4);
+	if (!ASSERT_EQ(id, first_struct_id + depth, "btf__add_struct plain_leaf"))
+		goto out;
+
+	err = btf__load_into_kernel(btf);
+	ASSERT_EQ(err, expected_err, "check btf");
+out:
+	btf__free(btf);
+}
+
+void test_local_kptr_ownership(void)
+{
+	if (test__start_subtest("self_cycle"))
+		test_self_cycle("kptr", -ELOOP);
+	if (test__start_subtest("untrusted_self_cycle"))
+		test_self_cycle("kptr_untrusted", 0);
+	if (test__start_subtest("percpu_self_cycle"))
+		test_self_cycle("percpu_kptr", -ELOOP);
+	if (test__start_subtest("ABA_cycle"))
+		test_aba_cycle();
+	if (test__start_subtest("mixed_graph_root_cycle"))
+		test_mixed_cycle();
+	if (test__start_subtest("max_acyclic"))
+		test_acyclic_depth(MAX_OWNERSHIP_DEPTH, 0);
+	if (test__start_subtest("too_deep_acyclic"))
+		test_acyclic_depth(MAX_OWNERSHIP_DEPTH + 1, -ELOOP);
+}
-- 
2.53.0

Re: [PATCH bpf-next v1 1/3] bpf: Validate graph ownership with a bounded walk

[Alexei Starovoitov]

On Sat Sep 5, 2026 at 2:07 AM PDT, Kumar Kartikeya Dwivedi wrote:
> btf_check_and_fixup_fields() prevents graph ownership cycles with a
> one-hop restriction: a type that contains both a graph root and node cannot
> own another root type. This limits graph ownership chains to three types,
> but also rejects longer acyclic relationships.
>
> All struct metadata is available once field fixups finish. Move ownership
> validation out of the per-record fixup helper and walk graph-root type
> relationships directly at BTF load time. Reject cycles and chains deeper
> than eight record-bearing types, which keeps recursive destruction bounded
> while permitting safe acyclic layouts.
>
> Keep the depth limit independent of MAX_CALL_FRAMES because graph teardown
> can run beneath a BPF call chain. btf_check_and_fixup_fields() continues to
> initialize graph_root.value_rec, including for the separately allocated map
> record. The ownership relationship itself belongs to the immutable BTF and
> therefore only needs validation once during BTF load.
>
> Update the graph BTF tests to accept the two acyclic relationships that the
> old approximation rejected.

Are you saying old approximation was not correct?
Pls explain how it missed it.

Probably better to merge patch 1 and 2. I don't see why they're split like that
and patch 2 immediately fixes patch 1.

pw-bot: cr