1 // SPDX-License-Identifier: GPL-2.0 2 /* Copyright (c) 2026 KylinSoft Corporation. */ 3 4 #include <vmlinux.h> 5 #include <bpf/bpf_helpers.h> 6 #include "bpf_misc.h" 7 #include "bpf_experimental.h" 8 9 #define NR_NODES 16 10 11 struct node_data { 12 int data; 13 }; 14 15 struct tree_node { 16 struct bpf_rb_node node; 17 u64 key; 18 struct node_data __kptr * node_data; 19 }; 20 21 struct tree_node_ref { 22 struct bpf_refcount ref; 23 struct bpf_rb_node node; 24 u64 key; 25 struct node_data __kptr * node_data; 26 }; 27 28 #define private(name) SEC(".data." #name) __hidden __aligned(8) 29 30 private(A) struct bpf_rb_root root __contains(tree_node, node); 31 private(A) struct bpf_spin_lock lock; 32 33 private(B) struct bpf_rb_root root_r __contains(tree_node_ref, node); 34 private(B) struct bpf_spin_lock lock_r; 35 36 static bool less(struct bpf_rb_node *a, const struct bpf_rb_node *b) 37 { 38 struct tree_node *node_a, *node_b; 39 40 node_a = container_of(a, struct tree_node, node); 41 node_b = container_of(b, struct tree_node, node); 42 43 return node_a->key < node_b->key; 44 } 45 46 SEC("syscall") 47 __retval(0) 48 long rbtree_search_kptr(void *ctx) 49 { 50 struct tree_node *tnode; 51 struct bpf_rb_node *rb_n; 52 struct node_data __kptr * node_data; 53 int lookup_key = NR_NODES / 2; 54 int lookup_data = NR_NODES / 2; 55 int i, data, ret = 0; 56 57 for (i = 0; i < NR_NODES && can_loop; i++) { 58 tnode = bpf_obj_new(typeof(*tnode)); 59 if (!tnode) 60 return __LINE__; 61 62 node_data = bpf_obj_new(typeof(*node_data)); 63 if (!node_data) { 64 bpf_obj_drop(tnode); 65 return __LINE__; 66 } 67 68 tnode->key = i; 69 node_data->data = i; 70 71 node_data = bpf_kptr_xchg(&tnode->node_data, node_data); 72 if (node_data) 73 bpf_obj_drop(node_data); 74 75 bpf_spin_lock(&lock); 76 bpf_rbtree_add(&root, &tnode->node, less); 77 bpf_spin_unlock(&lock); 78 } 79 80 bpf_spin_lock(&lock); 81 rb_n = bpf_rbtree_root(&root); 82 while (rb_n && can_loop) { 83 tnode = container_of(rb_n, struct tree_node, node); 84 node_data = bpf_kptr_xchg(&tnode->node_data, NULL); 85 if (!node_data) { 86 ret = __LINE__; 87 goto fail; 88 } 89 90 data = node_data->data; 91 node_data = bpf_kptr_xchg(&tnode->node_data, node_data); 92 if (node_data) { 93 bpf_spin_unlock(&lock); 94 bpf_obj_drop(node_data); 95 return __LINE__; 96 } 97 98 if (lookup_key == tnode->key) { 99 if (data == lookup_data) 100 break; 101 102 ret = __LINE__; 103 goto fail; 104 } 105 106 if (lookup_key < tnode->key) 107 rb_n = bpf_rbtree_left(&root, rb_n); 108 else 109 rb_n = bpf_rbtree_right(&root, rb_n); 110 } 111 bpf_spin_unlock(&lock); 112 113 while (can_loop) { 114 bpf_spin_lock(&lock); 115 rb_n = bpf_rbtree_first(&root); 116 if (!rb_n) { 117 bpf_spin_unlock(&lock); 118 return 0; 119 } 120 121 rb_n = bpf_rbtree_remove(&root, rb_n); 122 if (!rb_n) { 123 ret = __LINE__; 124 goto fail; 125 } 126 bpf_spin_unlock(&lock); 127 128 tnode = container_of(rb_n, struct tree_node, node); 129 130 node_data = bpf_kptr_xchg(&tnode->node_data, NULL); 131 if (node_data) 132 bpf_obj_drop(node_data); 133 134 bpf_obj_drop(tnode); 135 } 136 137 return 0; 138 fail: 139 bpf_spin_unlock(&lock); 140 return ret; 141 } 142 143 static bool less_r(struct bpf_rb_node *a, const struct bpf_rb_node *b) 144 { 145 struct tree_node_ref *node_a, *node_b; 146 147 node_a = container_of(a, struct tree_node_ref, node); 148 node_b = container_of(b, struct tree_node_ref, node); 149 150 return node_a->key < node_b->key; 151 } 152 153 SEC("syscall") 154 __retval(0) 155 long rbtree_search_kptr_ref(void *ctx) 156 { 157 struct tree_node_ref *tnode_r, *tnode_m; 158 struct bpf_rb_node *rb_n; 159 struct node_data __kptr * node_data; 160 int lookup_key = NR_NODES / 2; 161 int lookup_data = NR_NODES / 2; 162 int i, data, ret = 0; 163 164 for (i = 0; i < NR_NODES && can_loop; i++) { 165 tnode_r = bpf_obj_new(typeof(*tnode_r)); 166 if (!tnode_r) 167 return __LINE__; 168 169 node_data = bpf_obj_new(typeof(*node_data)); 170 if (!node_data) { 171 bpf_obj_drop(tnode_r); 172 return __LINE__; 173 } 174 175 tnode_r->key = i; 176 node_data->data = i; 177 178 node_data = bpf_kptr_xchg(&tnode_r->node_data, node_data); 179 if (node_data) 180 bpf_obj_drop(node_data); 181 182 /* Unused reference */ 183 tnode_m = bpf_refcount_acquire(tnode_r); 184 if (!tnode_m) 185 return __LINE__; 186 187 bpf_spin_lock(&lock_r); 188 bpf_rbtree_add(&root_r, &tnode_r->node, less_r); 189 bpf_spin_unlock(&lock_r); 190 191 bpf_obj_drop(tnode_m); 192 } 193 194 bpf_spin_lock(&lock_r); 195 rb_n = bpf_rbtree_root(&root_r); 196 while (rb_n && can_loop) { 197 tnode_r = container_of(rb_n, struct tree_node_ref, node); 198 node_data = bpf_kptr_xchg(&tnode_r->node_data, NULL); 199 if (!node_data) { 200 ret = __LINE__; 201 goto fail; 202 } 203 204 data = node_data->data; 205 node_data = bpf_kptr_xchg(&tnode_r->node_data, node_data); 206 if (node_data) { 207 bpf_spin_unlock(&lock_r); 208 bpf_obj_drop(node_data); 209 return __LINE__; 210 } 211 212 if (lookup_key == tnode_r->key) { 213 if (data == lookup_data) 214 break; 215 216 ret = __LINE__; 217 goto fail; 218 } 219 220 if (lookup_key < tnode_r->key) 221 rb_n = bpf_rbtree_left(&root_r, rb_n); 222 else 223 rb_n = bpf_rbtree_right(&root_r, rb_n); 224 } 225 bpf_spin_unlock(&lock_r); 226 227 while (can_loop) { 228 bpf_spin_lock(&lock_r); 229 rb_n = bpf_rbtree_first(&root_r); 230 if (!rb_n) { 231 bpf_spin_unlock(&lock_r); 232 return 0; 233 } 234 235 rb_n = bpf_rbtree_remove(&root_r, rb_n); 236 if (!rb_n) { 237 ret = __LINE__; 238 goto fail; 239 } 240 bpf_spin_unlock(&lock_r); 241 242 tnode_r = container_of(rb_n, struct tree_node_ref, node); 243 244 node_data = bpf_kptr_xchg(&tnode_r->node_data, NULL); 245 if (node_data) 246 bpf_obj_drop(node_data); 247 248 bpf_obj_drop(tnode_r); 249 } 250 251 return 0; 252 fail: 253 bpf_spin_unlock(&lock_r); 254 return ret; 255 } 256 257 SEC("syscall") 258 __failure __msg("R1 type=scalar expected=map_value, ptr_, ptr_") 259 long non_own_ref_kptr_xchg_no_lock(void *ctx) 260 { 261 struct tree_node *tnode; 262 struct bpf_rb_node *rb_n; 263 struct node_data __kptr * node_data; 264 int data; 265 266 bpf_spin_lock(&lock); 267 rb_n = bpf_rbtree_first(&root); 268 if (!rb_n) { 269 bpf_spin_unlock(&lock); 270 return __LINE__; 271 } 272 bpf_spin_unlock(&lock); 273 274 tnode = container_of(rb_n, struct tree_node, node); 275 node_data = bpf_kptr_xchg(&tnode->node_data, NULL); 276 if (!node_data) 277 return __LINE__; 278 279 data = node_data->data; 280 if (data < 0) 281 return __LINE__; 282 283 node_data = bpf_kptr_xchg(&tnode->node_data, node_data); 284 if (node_data) 285 return __LINE__; 286 287 return 0; 288 } 289 290 char _license[] SEC("license") = "GPL"; 291