1 // SPDX-License-Identifier: GPL-2.0
2 /* Copyright (c) 2026 Meta Platforms, Inc. and affiliates. */
3
4 #include <bpf/btf.h>
5 #include <linux/btf.h>
6 #include <test_progs.h>
7
8 #define SPIN_LOCK 2
9 #define LIST_HEAD 3
10 #define LIST_NODE 4
11 /* Keep in sync with BTF_MAX_OWNERSHIP_DEPTH. */
12 #define MAX_OWNERSHIP_DEPTH 8
13
init_btf(void)14 static struct btf *init_btf(void)
15 {
16 struct btf *btf;
17 int id;
18
19 btf = btf__new_empty();
20 if (!ASSERT_OK_PTR(btf, "btf__new_empty"))
21 return NULL;
22 id = btf__add_int(btf, "int", 4, BTF_INT_SIGNED);
23 if (!ASSERT_EQ(id, 1, "btf__add_int"))
24 goto err_out;
25 id = btf__add_struct(btf, "bpf_spin_lock", 4);
26 if (!ASSERT_EQ(id, SPIN_LOCK, "btf__add_struct bpf_spin_lock"))
27 goto err_out;
28 id = btf__add_struct(btf, "bpf_list_head", 16);
29 if (!ASSERT_EQ(id, LIST_HEAD, "btf__add_struct bpf_list_head"))
30 goto err_out;
31 id = btf__add_struct(btf, "bpf_list_node", 24);
32 if (!ASSERT_EQ(id, LIST_NODE, "btf__add_struct bpf_list_node"))
33 goto err_out;
34 return btf;
35
36 err_out:
37 btf__free(btf);
38 return NULL;
39 }
40
add_local_kptr(struct btf * btf,int pointee_id,const char * tag)41 static int add_local_kptr(struct btf *btf, int pointee_id, const char *tag)
42 {
43 int id;
44
45 id = btf__add_type_tag(btf, tag, pointee_id);
46 if (!ASSERT_GT(id, 0, "btf__add_type_tag"))
47 return id;
48 id = btf__add_ptr(btf, id);
49 ASSERT_GT(id, 0, "btf__add_ptr");
50 return id;
51 }
52
test_self_cycle(const char * tag,int expected_err)53 static void test_self_cycle(const char *tag, int expected_err)
54 {
55 struct btf *btf;
56 int id, err;
57
58 btf = init_btf();
59 if (!ASSERT_OK_PTR(btf, "init_btf"))
60 return;
61 id = add_local_kptr(btf, 7, tag);
62 if (id <= 0)
63 goto out;
64 id = btf__add_struct(btf, "self_cycle", 8);
65 if (!ASSERT_EQ(id, 7, "btf__add_struct self_cycle"))
66 goto out;
67 err = btf__add_field(btf, "next", 6, 0, 0);
68 if (!ASSERT_OK(err, "btf__add_field self_cycle::next"))
69 goto out;
70
71 err = btf__load_into_kernel(btf);
72 ASSERT_EQ(err, expected_err, "check btf");
73 out:
74 btf__free(btf);
75 }
76
test_aba_cycle(void)77 static void test_aba_cycle(void)
78 {
79 struct btf *btf;
80 int id, err;
81
82 btf = init_btf();
83 if (!ASSERT_OK_PTR(btf, "init_btf"))
84 return;
85 id = add_local_kptr(btf, 10, "kptr");
86 if (id <= 0)
87 goto out;
88 id = add_local_kptr(btf, 9, "kptr");
89 if (id <= 0)
90 goto out;
91 id = btf__add_struct(btf, "cycle_a", 8);
92 if (!ASSERT_EQ(id, 9, "btf__add_struct cycle_a"))
93 goto out;
94 err = btf__add_field(btf, "b", 6, 0, 0);
95 if (!ASSERT_OK(err, "btf__add_field cycle_a::b"))
96 goto out;
97 id = btf__add_struct(btf, "cycle_b", 8);
98 if (!ASSERT_EQ(id, 10, "btf__add_struct cycle_b"))
99 goto out;
100 err = btf__add_field(btf, "a", 8, 0, 0);
101 if (!ASSERT_OK(err, "btf__add_field cycle_b::a"))
102 goto out;
103
104 err = btf__load_into_kernel(btf);
105 ASSERT_EQ(err, -ELOOP, "check btf");
106 out:
107 btf__free(btf);
108 }
109
test_mixed_cycle(void)110 static void test_mixed_cycle(void)
111 {
112 struct btf *btf;
113 int id, err;
114
115 btf = init_btf();
116 if (!ASSERT_OK_PTR(btf, "init_btf"))
117 return;
118 id = add_local_kptr(btf, 7, "kptr");
119 if (id <= 0)
120 goto out;
121 id = btf__add_struct(btf, "mixed_owner", 20);
122 if (!ASSERT_EQ(id, 7, "btf__add_struct mixed_owner"))
123 goto out;
124 err = btf__add_field(btf, "root", LIST_HEAD, 0, 0);
125 if (!ASSERT_OK(err, "btf__add_field mixed_owner::root"))
126 goto out;
127 err = btf__add_field(btf, "lock", SPIN_LOCK, 128, 0);
128 if (!ASSERT_OK(err, "btf__add_field mixed_owner::lock"))
129 goto out;
130 id = btf__add_decl_tag(btf, "contains:mixed_node:node", 7, 0);
131 if (!ASSERT_EQ(id, 8, "btf__add_decl_tag mixed_owner"))
132 goto out;
133 id = btf__add_struct(btf, "mixed_node", 32);
134 if (!ASSERT_EQ(id, 9, "btf__add_struct mixed_node"))
135 goto out;
136 err = btf__add_field(btf, "node", LIST_NODE, 0, 0);
137 if (!ASSERT_OK(err, "btf__add_field mixed_node::node"))
138 goto out;
139 err = btf__add_field(btf, "owner", 6, 192, 0);
140 if (!ASSERT_OK(err, "btf__add_field mixed_node::owner"))
141 goto out;
142
143 err = btf__load_into_kernel(btf);
144 ASSERT_EQ(err, -ELOOP, "check btf");
145 out:
146 btf__free(btf);
147 }
148
test_acyclic_depth(int depth,bool child_first,bool shared_suffix,int expected_err)149 static void test_acyclic_depth(int depth, bool child_first, bool shared_suffix, int expected_err)
150 {
151 int ptr_id[MAX_OWNERSHIP_DEPTH + 1];
152 int first_struct_id;
153 struct btf *btf;
154 int id, err, i, n, pointee_id;
155
156 btf = init_btf();
157 if (!ASSERT_OK_PTR(btf, "init_btf"))
158 return;
159 first_struct_id = 5 + 2 * depth;
160 for (i = 0; i < depth; i++) {
161 if (i == depth - 1)
162 pointee_id = first_struct_id + depth;
163 else
164 pointee_id = first_struct_id + (child_first ? depth - 2 - i : i + 1);
165 ptr_id[i] = add_local_kptr(btf, pointee_id, "kptr");
166 if (ptr_id[i] <= 0)
167 goto out;
168 }
169 for (n = 0; n < depth; n++) {
170 char name[32];
171 int offset = 0;
172
173 i = child_first ? depth - 1 - n : n;
174 snprintf(name, sizeof(name), "owner_%d", i);
175 id = btf__add_struct(btf, name, shared_suffix && !i ? 16 : 8);
176 if (!ASSERT_EQ(id, first_struct_id + n, "btf__add_struct owner"))
177 goto out;
178 if (shared_suffix && !i) {
179 /*
180 * Visit the shared suffix through the shorter path before
181 * reaching it again with less remaining depth.
182 */
183 err = btf__add_field(btf, "suffix", ptr_id[1], 0, 0);
184 if (!ASSERT_OK(err, "btf__add_field owner::suffix"))
185 goto out;
186 offset = 64;
187 }
188 err = btf__add_field(btf, "next", ptr_id[i], offset, 0);
189 if (!ASSERT_OK(err, "btf__add_field owner::next"))
190 goto out;
191 }
192 id = btf__add_struct(btf, "plain_leaf", 4);
193 if (!ASSERT_EQ(id, first_struct_id + depth, "btf__add_struct plain_leaf"))
194 goto out;
195
196 err = btf__load_into_kernel(btf);
197 ASSERT_EQ(err, expected_err, "check btf");
198 out:
199 btf__free(btf);
200 }
201
test_graph_depth(bool rbtree,int depth,int expected_err)202 static void test_graph_depth(bool rbtree, int depth, int expected_err)
203 {
204 int root_type = LIST_HEAD, node_type = LIST_NODE, node_size = 24;
205 int id, err, i, lock_off, root_off, size;
206 struct btf *btf;
207
208 btf = init_btf();
209 if (!ASSERT_OK_PTR(btf, "init_btf"))
210 return;
211 if (rbtree) {
212 root_type = btf__add_struct(btf, "bpf_rb_root", 16);
213 if (!ASSERT_GT(root_type, 0, "btf__add_struct bpf_rb_root"))
214 goto out;
215 node_type = btf__add_struct(btf, "bpf_rb_node", 32);
216 if (!ASSERT_GT(node_type, 0, "btf__add_struct bpf_rb_node"))
217 goto out;
218 node_size = 32;
219 }
220
221 for (i = 0; i < depth; i++) {
222 char name[32], tag[64];
223
224 lock_off = i ? node_size : 0;
225 root_off = lock_off + 8;
226 size = i == depth - 1 ? node_size : root_off + 16;
227 snprintf(name, sizeof(name), "graph_owner_%d", i);
228 id = btf__add_struct(btf, name, size);
229 if (!ASSERT_GT(id, 0, "btf__add_struct graph_owner"))
230 goto out;
231 if (i) {
232 err = btf__add_field(btf, "node", node_type, 0, 0);
233 if (!ASSERT_OK(err, "btf__add_field graph_owner::node"))
234 goto out;
235 }
236 if (i == depth - 1)
237 continue;
238 err = btf__add_field(btf, "lock", SPIN_LOCK, lock_off * 8, 0);
239 if (!ASSERT_OK(err, "btf__add_field graph_owner::lock"))
240 goto out;
241 err = btf__add_field(btf, "root", root_type, root_off * 8, 0);
242 if (!ASSERT_OK(err, "btf__add_field graph_owner::root"))
243 goto out;
244 snprintf(tag, sizeof(tag), "contains:graph_owner_%d:node", i + 1);
245 err = btf__add_decl_tag(btf, tag, id, i ? 2 : 1);
246 if (!ASSERT_GT(err, 0, "btf__add_decl_tag graph_owner"))
247 goto out;
248 }
249
250 err = btf__load_into_kernel(btf);
251 ASSERT_EQ(err, expected_err, "check btf");
252 out:
253 btf__free(btf);
254 }
255
test_local_kptr_ownership(void)256 void test_local_kptr_ownership(void)
257 {
258 if (test__start_subtest("self_cycle"))
259 test_self_cycle("kptr", -ELOOP);
260 if (test__start_subtest("untrusted_self_cycle"))
261 test_self_cycle("kptr_untrusted", 0);
262 if (test__start_subtest("percpu_self_cycle"))
263 test_self_cycle("percpu_kptr", -ELOOP);
264 if (test__start_subtest("ABA_cycle"))
265 test_aba_cycle();
266 if (test__start_subtest("mixed_graph_root_cycle"))
267 test_mixed_cycle();
268 if (test__start_subtest("max_acyclic"))
269 test_acyclic_depth(MAX_OWNERSHIP_DEPTH, false, false, 0);
270 if (test__start_subtest("too_deep_acyclic"))
271 test_acyclic_depth(MAX_OWNERSHIP_DEPTH + 1, false, false, -ELOOP);
272 if (test__start_subtest("max_acyclic_child_first"))
273 test_acyclic_depth(MAX_OWNERSHIP_DEPTH, true, false, 0);
274 if (test__start_subtest("too_deep_acyclic_child_first"))
275 test_acyclic_depth(MAX_OWNERSHIP_DEPTH + 1, true, false, -ELOOP);
276 if (test__start_subtest("max_acyclic_shared_suffix"))
277 test_acyclic_depth(MAX_OWNERSHIP_DEPTH, false, true, 0);
278 if (test__start_subtest("too_deep_acyclic_shared_suffix"))
279 test_acyclic_depth(MAX_OWNERSHIP_DEPTH + 1, false, true, -ELOOP);
280 if (test__start_subtest("list_three_types"))
281 test_graph_depth(false, 3, 0);
282 if (test__start_subtest("list_four_types"))
283 test_graph_depth(false, 4, 0);
284 if (test__start_subtest("list_max_depth"))
285 test_graph_depth(false, MAX_OWNERSHIP_DEPTH, 0);
286 if (test__start_subtest("list_too_deep"))
287 test_graph_depth(false, MAX_OWNERSHIP_DEPTH + 1, -ELOOP);
288 if (test__start_subtest("rbtree_three_types"))
289 test_graph_depth(true, 3, 0);
290 if (test__start_subtest("rbtree_four_types"))
291 test_graph_depth(true, 4, 0);
292 if (test__start_subtest("rbtree_max_depth"))
293 test_graph_depth(true, MAX_OWNERSHIP_DEPTH, 0);
294 if (test__start_subtest("rbtree_too_deep"))
295 test_graph_depth(true, MAX_OWNERSHIP_DEPTH + 1, -ELOOP);
296 }
297