1 // SPDX-License-Identifier: GPL-2.0 2 /* Copyright (c) 2023 Meta Platforms, Inc. and affiliates. */ 3 4 #include <vmlinux.h> 5 #include <bpf/bpf_tracing.h> 6 #include <bpf/bpf_helpers.h> 7 #include <bpf/bpf_core_read.h> 8 #include "bpf_misc.h" 9 #include "bpf_experimental.h" 10 11 extern void bpf_rcu_read_lock(void) __ksym; 12 extern void bpf_rcu_read_unlock(void) __ksym; 13 14 struct node_data { 15 long key; 16 long list_data; 17 struct bpf_rb_node r; 18 struct bpf_list_node l; 19 struct bpf_refcount ref; 20 }; 21 22 struct map_value { 23 struct node_data __kptr *node; 24 }; 25 26 struct node_refcount_only { 27 long key; 28 struct bpf_refcount refcount; 29 }; 30 31 struct map_value_refcount_only { 32 struct node_refcount_only __kptr *node; 33 }; 34 35 struct { 36 __uint(type, BPF_MAP_TYPE_ARRAY); 37 __type(key, int); 38 __type(value, struct map_value); 39 __uint(max_entries, 2); 40 } stashed_nodes SEC(".maps"); 41 42 struct { 43 __uint(type, BPF_MAP_TYPE_ARRAY); 44 __type(key, int); 45 __type(value, struct map_value_refcount_only); 46 __uint(max_entries, 1); 47 } stashed_refcount_only SEC(".maps"); 48 49 struct node_acquire { 50 long key; 51 long data; 52 struct bpf_rb_node node; 53 struct bpf_refcount refcount; 54 }; 55 56 #define private(name) SEC(".bss." #name) __hidden __attribute__((aligned(8))) 57 private(A) struct bpf_spin_lock lock; 58 private(A) struct bpf_rb_root root __contains(node_data, r); 59 private(A) struct bpf_list_head head __contains(node_data, l); 60 61 private(B) struct bpf_spin_lock alock; 62 private(B) struct bpf_rb_root aroot __contains(node_acquire, node); 63 64 private(C) struct bpf_spin_lock block; 65 private(C) struct bpf_rb_root broot __contains(node_data, r); 66 67 static bool less(struct bpf_rb_node *node_a, const struct bpf_rb_node *node_b) 68 { 69 struct node_data *a; 70 struct node_data *b; 71 72 a = container_of(node_a, struct node_data, r); 73 b = container_of(node_b, struct node_data, r); 74 75 return a->key < b->key; 76 } 77 78 static bool less_a(struct bpf_rb_node *a, const struct bpf_rb_node *b) 79 { 80 struct node_acquire *node_a; 81 struct node_acquire *node_b; 82 83 node_a = container_of(a, struct node_acquire, node); 84 node_b = container_of(b, struct node_acquire, node); 85 86 return node_a->key < node_b->key; 87 } 88 89 static long __insert_in_tree_and_list(struct bpf_list_head *head, 90 struct bpf_rb_root *root, 91 struct bpf_spin_lock *lock) 92 { 93 struct node_data *n, *m; 94 95 n = bpf_obj_new(typeof(*n)); 96 if (!n) 97 return -1; 98 99 m = bpf_refcount_acquire(n); 100 m->key = 123; 101 m->list_data = 456; 102 103 bpf_spin_lock(lock); 104 if (bpf_rbtree_add(root, &n->r, less)) { 105 /* Failure to insert - unexpected */ 106 bpf_spin_unlock(lock); 107 bpf_obj_drop(m); 108 return -2; 109 } 110 bpf_spin_unlock(lock); 111 112 bpf_spin_lock(lock); 113 if (bpf_list_push_front(head, &m->l)) { 114 /* Failure to insert - unexpected */ 115 bpf_spin_unlock(lock); 116 return -3; 117 } 118 bpf_spin_unlock(lock); 119 return 0; 120 } 121 122 static long __stash_map_insert_tree(int idx, int val, struct bpf_rb_root *root, 123 struct bpf_spin_lock *lock) 124 { 125 struct map_value *mapval; 126 struct node_data *n, *m; 127 128 mapval = bpf_map_lookup_elem(&stashed_nodes, &idx); 129 if (!mapval) 130 return -1; 131 132 n = bpf_obj_new(typeof(*n)); 133 if (!n) 134 return -2; 135 136 n->key = val; 137 m = bpf_refcount_acquire(n); 138 139 n = bpf_kptr_xchg(&mapval->node, n); 140 if (n) { 141 bpf_obj_drop(n); 142 bpf_obj_drop(m); 143 return -3; 144 } 145 146 bpf_spin_lock(lock); 147 if (bpf_rbtree_add(root, &m->r, less)) { 148 /* Failure to insert - unexpected */ 149 bpf_spin_unlock(lock); 150 return -4; 151 } 152 bpf_spin_unlock(lock); 153 return 0; 154 } 155 156 static long __read_from_tree(struct bpf_rb_root *root, 157 struct bpf_spin_lock *lock, 158 bool remove_from_tree) 159 { 160 struct bpf_rb_node *rb; 161 struct node_data *n; 162 long res = -99; 163 164 bpf_spin_lock(lock); 165 166 rb = bpf_rbtree_first(root); 167 if (!rb) { 168 bpf_spin_unlock(lock); 169 return -1; 170 } 171 172 n = container_of(rb, struct node_data, r); 173 res = n->key; 174 175 if (!remove_from_tree) { 176 bpf_spin_unlock(lock); 177 return res; 178 } 179 180 rb = bpf_rbtree_remove(root, rb); 181 bpf_spin_unlock(lock); 182 if (!rb) 183 return -2; 184 n = container_of(rb, struct node_data, r); 185 bpf_obj_drop(n); 186 return res; 187 } 188 189 static long __read_from_list(struct bpf_list_head *head, 190 struct bpf_spin_lock *lock, 191 bool remove_from_list) 192 { 193 struct bpf_list_node *l; 194 struct node_data *n; 195 long res = -99; 196 197 bpf_spin_lock(lock); 198 199 l = bpf_list_pop_front(head); 200 if (!l) { 201 bpf_spin_unlock(lock); 202 return -1; 203 } 204 205 n = container_of(l, struct node_data, l); 206 res = n->list_data; 207 208 if (!remove_from_list) { 209 if (bpf_list_push_back(head, &n->l)) { 210 bpf_spin_unlock(lock); 211 return -2; 212 } 213 } 214 215 bpf_spin_unlock(lock); 216 217 if (remove_from_list) 218 bpf_obj_drop(n); 219 return res; 220 } 221 222 static long __read_from_unstash(int idx) 223 { 224 struct node_data *n = NULL; 225 struct map_value *mapval; 226 long val = -99; 227 228 mapval = bpf_map_lookup_elem(&stashed_nodes, &idx); 229 if (!mapval) 230 return -1; 231 232 n = bpf_kptr_xchg(&mapval->node, n); 233 if (!n) 234 return -2; 235 236 val = n->key; 237 bpf_obj_drop(n); 238 return val; 239 } 240 241 #define INSERT_READ_BOTH(rem_tree, rem_list, desc) \ 242 SEC("tc") \ 243 __description(desc) \ 244 __success __retval(579) \ 245 long insert_and_remove_tree_##rem_tree##_list_##rem_list(void *ctx) \ 246 { \ 247 long err, tree_data, list_data; \ 248 \ 249 err = __insert_in_tree_and_list(&head, &root, &lock); \ 250 if (err) \ 251 return err; \ 252 \ 253 err = __read_from_tree(&root, &lock, rem_tree); \ 254 if (err < 0) \ 255 return err; \ 256 else \ 257 tree_data = err; \ 258 \ 259 err = __read_from_list(&head, &lock, rem_list); \ 260 if (err < 0) \ 261 return err; \ 262 else \ 263 list_data = err; \ 264 \ 265 return tree_data + list_data; \ 266 } 267 268 /* After successful insert of struct node_data into both collections: 269 * - it should have refcount = 2 270 * - removing / not removing the node_data from a collection after 271 * reading should have no effect on ability to read / remove from 272 * the other collection 273 */ 274 INSERT_READ_BOTH(true, true, "insert_read_both: remove from tree + list"); 275 INSERT_READ_BOTH(false, false, "insert_read_both: remove from neither"); 276 INSERT_READ_BOTH(true, false, "insert_read_both: remove from tree"); 277 INSERT_READ_BOTH(false, true, "insert_read_both: remove from list"); 278 279 #undef INSERT_READ_BOTH 280 #define INSERT_READ_BOTH(rem_tree, rem_list, desc) \ 281 SEC("tc") \ 282 __description(desc) \ 283 __success __retval(579) \ 284 long insert_and_remove_lf_tree_##rem_tree##_list_##rem_list(void *ctx) \ 285 { \ 286 long err, tree_data, list_data; \ 287 \ 288 err = __insert_in_tree_and_list(&head, &root, &lock); \ 289 if (err) \ 290 return err; \ 291 \ 292 err = __read_from_list(&head, &lock, rem_list); \ 293 if (err < 0) \ 294 return err; \ 295 else \ 296 list_data = err; \ 297 \ 298 err = __read_from_tree(&root, &lock, rem_tree); \ 299 if (err < 0) \ 300 return err; \ 301 else \ 302 tree_data = err; \ 303 \ 304 return tree_data + list_data; \ 305 } 306 307 /* Similar to insert_read_both, but list data is read and possibly removed 308 * first 309 * 310 * Results should be no different than reading and possibly removing rbtree 311 * node first 312 */ 313 INSERT_READ_BOTH(true, true, "insert_read_both_list_first: remove from tree + list"); 314 INSERT_READ_BOTH(false, false, "insert_read_both_list_first: remove from neither"); 315 INSERT_READ_BOTH(true, false, "insert_read_both_list_first: remove from tree"); 316 INSERT_READ_BOTH(false, true, "insert_read_both_list_first: remove from list"); 317 318 #define INSERT_DOUBLE_READ_AND_DEL(read_fn, read_root, desc) \ 319 SEC("tc") \ 320 __description(desc) \ 321 __success __retval(-1) \ 322 long insert_double_##read_fn##_and_del_##read_root(void *ctx) \ 323 { \ 324 long err, list_data; \ 325 \ 326 err = __insert_in_tree_and_list(&head, &root, &lock); \ 327 if (err) \ 328 return err; \ 329 \ 330 err = read_fn(&read_root, &lock, true); \ 331 if (err < 0) \ 332 return err; \ 333 else \ 334 list_data = err; \ 335 \ 336 err = read_fn(&read_root, &lock, true); \ 337 if (err < 0) \ 338 return err; \ 339 \ 340 return err + list_data; \ 341 } 342 343 /* Insert into both tree and list, then try reading-and-removing from either twice 344 * 345 * The second read-and-remove should fail on read step since the node has 346 * already been removed 347 */ 348 INSERT_DOUBLE_READ_AND_DEL(__read_from_tree, root, "insert_double_del: 2x read-and-del from tree"); 349 INSERT_DOUBLE_READ_AND_DEL(__read_from_list, head, "insert_double_del: 2x read-and-del from list"); 350 351 #define INSERT_STASH_READ(rem_tree, desc) \ 352 SEC("tc") \ 353 __description(desc) \ 354 __success __retval(84) \ 355 long insert_rbtree_and_stash__del_tree_##rem_tree(void *ctx) \ 356 { \ 357 long err, tree_data, map_data; \ 358 \ 359 err = __stash_map_insert_tree(0, 42, &root, &lock); \ 360 if (err) \ 361 return err; \ 362 \ 363 err = __read_from_tree(&root, &lock, rem_tree); \ 364 if (err < 0) \ 365 return err; \ 366 else \ 367 tree_data = err; \ 368 \ 369 err = __read_from_unstash(0); \ 370 if (err < 0) \ 371 return err; \ 372 else \ 373 map_data = err; \ 374 \ 375 return tree_data + map_data; \ 376 } 377 378 /* Stash a refcounted node in map_val, insert same node into tree, then try 379 * reading data from tree then unstashed map_val, possibly removing from tree 380 * 381 * Removing from tree should have no effect on map_val kptr validity 382 */ 383 INSERT_STASH_READ(true, "insert_stash_read: remove from tree"); 384 INSERT_STASH_READ(false, "insert_stash_read: don't remove from tree"); 385 386 SEC("tc") 387 __description("list_empty_test: list empty before add, non-empty after add") 388 __success __retval(0) 389 int list_empty_test(void *ctx) 390 { 391 struct node_data *node_new; 392 393 bpf_spin_lock(&lock); 394 if (!bpf_list_empty(&head)) { 395 bpf_spin_unlock(&lock); 396 return -1; 397 } 398 bpf_spin_unlock(&lock); 399 400 node_new = bpf_obj_new(typeof(*node_new)); 401 if (!node_new) 402 return -2; 403 404 bpf_spin_lock(&lock); 405 bpf_list_push_front(&head, &node_new->l); 406 407 if (bpf_list_empty(&head)) { 408 bpf_spin_unlock(&lock); 409 return -3; 410 } 411 bpf_spin_unlock(&lock); 412 return 0; 413 } 414 415 static struct node_data *__add_in_list(struct bpf_list_head *head, 416 struct bpf_spin_lock *lock) 417 { 418 struct node_data *node_new, *node_ref; 419 420 node_new = bpf_obj_new(typeof(*node_new)); 421 if (!node_new) 422 return NULL; 423 424 node_ref = bpf_refcount_acquire(node_new); 425 426 bpf_spin_lock(lock); 427 bpf_list_push_front(head, &node_new->l); 428 bpf_spin_unlock(lock); 429 return node_ref; 430 } 431 432 SEC("tc") 433 __description("list_is_edge_test1: is_first on first node, is_last on last node") 434 __success __retval(0) 435 int list_is_edge_test1(void *ctx) 436 { 437 struct node_data *node_first, *node_last; 438 int err = 0; 439 440 node_last = __add_in_list(&head, &lock); 441 if (!node_last) 442 return -1; 443 444 node_first = __add_in_list(&head, &lock); 445 if (!node_first) { 446 bpf_obj_drop(node_last); 447 return -2; 448 } 449 450 bpf_spin_lock(&lock); 451 if (!bpf_list_is_first(&head, &node_first->l)) { 452 err = -3; 453 goto fail; 454 } 455 if (!bpf_list_is_last(&head, &node_last->l)) 456 err = -4; 457 458 fail: 459 bpf_spin_unlock(&lock); 460 bpf_obj_drop(node_first); 461 bpf_obj_drop(node_last); 462 return err; 463 } 464 465 SEC("tc") 466 __description("list_is_edge_test2: accept list_front/list_back return value") 467 __success __retval(0) 468 int list_is_edge_test2(void *ctx) 469 { 470 struct bpf_list_node *front, *back; 471 struct node_data *a, *b; 472 long err = 0; 473 474 a = __add_in_list(&head, &lock); 475 if (!a) 476 return -1; 477 478 b = __add_in_list(&head, &lock); 479 if (!b) { 480 bpf_obj_drop(a); 481 return -2; 482 } 483 484 bpf_spin_lock(&lock); 485 front = bpf_list_front(&head); 486 back = bpf_list_back(&head); 487 if (!front || !back) { 488 err = -3; 489 goto out_unlock; 490 } 491 492 if (!bpf_list_is_first(&head, front) || bpf_list_is_last(&head, front)) { 493 err = -4; 494 goto out_unlock; 495 } 496 497 if (!bpf_list_is_last(&head, back) || bpf_list_is_first(&head, back)) { 498 err = -5; 499 goto out_unlock; 500 } 501 502 out_unlock: 503 bpf_spin_unlock(&lock); 504 bpf_obj_drop(a); 505 bpf_obj_drop(b); 506 return err; 507 } 508 509 SEC("tc") 510 __description("list_is_edge_test3: single node is both first and last") 511 __success __retval(0) 512 int list_is_edge_test3(void *ctx) 513 { 514 struct node_data *tmp; 515 struct bpf_list_node *node; 516 long err = 0; 517 518 tmp = __add_in_list(&head, &lock); 519 if (!tmp) 520 return -1; 521 522 bpf_spin_lock(&lock); 523 node = bpf_list_front(&head); 524 if (!node) { 525 bpf_spin_unlock(&lock); 526 bpf_obj_drop(tmp); 527 return -2; 528 } 529 530 if (!bpf_list_is_first(&head, node) || !bpf_list_is_last(&head, node)) 531 err = -3; 532 bpf_spin_unlock(&lock); 533 534 bpf_obj_drop(tmp); 535 return err; 536 } 537 538 SEC("tc") 539 __description("list_del_test1: del returns removed nodes") 540 __success __retval(0) 541 int list_del_test1(void *ctx) 542 { 543 struct node_data *node_first, *node_last; 544 struct bpf_list_node *bpf_node_first, *bpf_node_last; 545 int err = 0; 546 547 node_last = __add_in_list(&head, &lock); 548 if (!node_last) 549 return -1; 550 551 node_first = __add_in_list(&head, &lock); 552 if (!node_first) { 553 bpf_obj_drop(node_last); 554 return -2; 555 } 556 557 bpf_spin_lock(&lock); 558 bpf_node_last = bpf_list_del(&head, &node_last->l); 559 bpf_node_first = bpf_list_del(&head, &node_first->l); 560 bpf_spin_unlock(&lock); 561 562 if (bpf_node_first) 563 bpf_obj_drop(container_of(bpf_node_first, struct node_data, l)); 564 else 565 err = -3; 566 567 if (bpf_node_last) 568 bpf_obj_drop(container_of(bpf_node_last, struct node_data, l)); 569 else 570 err = -4; 571 572 bpf_obj_drop(node_first); 573 bpf_obj_drop(node_last); 574 return err; 575 } 576 577 SEC("tc") 578 __description("list_del_test2: remove an arbitrary node from the list") 579 __success __retval(0) 580 int list_del_test2(void *ctx) 581 { 582 struct bpf_rb_node *rb; 583 struct bpf_list_node *l; 584 struct node_data *n; 585 long err; 586 587 err = __insert_in_tree_and_list(&head, &root, &lock); 588 if (err) 589 return err; 590 591 bpf_spin_lock(&lock); 592 rb = bpf_rbtree_first(&root); 593 if (!rb) { 594 bpf_spin_unlock(&lock); 595 return -4; 596 } 597 598 rb = bpf_rbtree_remove(&root, rb); 599 if (!rb) { 600 bpf_spin_unlock(&lock); 601 return -5; 602 } 603 604 n = container_of(rb, struct node_data, r); 605 l = bpf_list_del(&head, &n->l); 606 bpf_spin_unlock(&lock); 607 bpf_obj_drop(n); 608 if (!l) 609 return -6; 610 611 bpf_obj_drop(container_of(l, struct node_data, l)); 612 return 0; 613 } 614 615 SEC("tc") 616 __description("list_del_test3: list_del accepts list_front return value as node") 617 __success __retval(0) 618 int list_del_test3(void *ctx) 619 { 620 struct node_data *tmp; 621 struct bpf_list_node *bpf_node, *l; 622 long err = 0; 623 624 tmp = __add_in_list(&head, &lock); 625 if (!tmp) 626 return -1; 627 628 bpf_spin_lock(&lock); 629 bpf_node = bpf_list_front(&head); 630 if (!bpf_node) { 631 bpf_spin_unlock(&lock); 632 err = -2; 633 goto fail; 634 } 635 636 l = bpf_list_del(&head, bpf_node); 637 bpf_spin_unlock(&lock); 638 if (!l) { 639 err = -3; 640 goto fail; 641 } 642 643 bpf_obj_drop(container_of(l, struct node_data, l)); 644 bpf_obj_drop(tmp); 645 return 0; 646 647 fail: 648 bpf_obj_drop(tmp); 649 return err; 650 } 651 652 SEC("tc") 653 __description("list_add_test1: insert new node after prev") 654 __success __retval(0) 655 int list_add_test1(void *ctx) 656 { 657 struct node_data *node_first; 658 struct node_data *new_node; 659 long err = 0; 660 661 node_first = __add_in_list(&head, &lock); 662 if (!node_first) 663 return -1; 664 665 new_node = bpf_obj_new(typeof(*new_node)); 666 if (!new_node) { 667 err = -2; 668 goto fail; 669 } 670 671 bpf_spin_lock(&lock); 672 err = bpf_list_add(&head, &new_node->l, &node_first->l); 673 bpf_spin_unlock(&lock); 674 if (err) { 675 err = -3; 676 goto fail; 677 } 678 679 fail: 680 bpf_obj_drop(node_first); 681 return err; 682 } 683 684 SEC("tc") 685 __description("list_add_test2: list_add accepts list_front return value as prev") 686 __success __retval(0) 687 int list_add_test2(void *ctx) 688 { 689 struct node_data *new_node, *tmp; 690 struct bpf_list_node *bpf_node; 691 long err = 0; 692 693 tmp = __add_in_list(&head, &lock); 694 if (!tmp) 695 return -1; 696 697 new_node = bpf_obj_new(typeof(*new_node)); 698 if (!new_node) { 699 err = -2; 700 goto fail; 701 } 702 703 bpf_spin_lock(&lock); 704 bpf_node = bpf_list_front(&head); 705 if (!bpf_node) { 706 bpf_spin_unlock(&lock); 707 bpf_obj_drop(new_node); 708 err = -3; 709 goto fail; 710 } 711 712 err = bpf_list_add(&head, &new_node->l, bpf_node); 713 bpf_spin_unlock(&lock); 714 if (err) { 715 err = -4; 716 goto fail; 717 } 718 719 fail: 720 bpf_obj_drop(tmp); 721 return err; 722 } 723 724 struct uninit_head_val { 725 struct bpf_spin_lock lock; 726 struct bpf_list_head head __contains(node_data, l); 727 }; 728 729 struct { 730 __uint(type, BPF_MAP_TYPE_ARRAY); 731 __type(key, int); 732 __type(value, struct uninit_head_val); 733 __uint(max_entries, 1); 734 } uninit_head_map SEC(".maps"); 735 736 SEC("tc") 737 __description("list_push_back_uninit_head: push_back on 0-initialized list head") 738 __success __retval(0) 739 int list_push_back_uninit_head(void *ctx) 740 { 741 struct uninit_head_val *st; 742 struct node_data *node; 743 int ret = -1, key = 0; 744 745 st = bpf_map_lookup_elem(&uninit_head_map, &key); 746 if (!st) 747 return -1; 748 749 node = bpf_obj_new(typeof(*node)); 750 if (!node) 751 return -1; 752 753 bpf_spin_lock(&st->lock); 754 ret = bpf_list_push_back(&st->head, &node->l); 755 bpf_spin_unlock(&st->lock); 756 757 return ret; 758 } 759 760 SEC("?tc") 761 __failure __msg("bpf_spin_lock at off=32 must be held for bpf_list_head") 762 long list_del_without_lock_fail(void *ctx) 763 { 764 struct node_data *n; 765 struct bpf_list_node *l; 766 767 n = bpf_obj_new(typeof(*n)); 768 if (!n) 769 return -1; 770 771 /* Error case: delete list node without holding lock */ 772 l = bpf_list_del(&head, &n->l); 773 bpf_obj_drop(n); 774 if (!l) 775 return -2; 776 bpf_obj_drop(container_of(l, struct node_data, l)); 777 778 return 0; 779 } 780 781 SEC("?tc") 782 __failure __msg("bpf_spin_lock at off=32 must be held for bpf_list_head") 783 long list_add_without_lock_fail(void *ctx) 784 { 785 struct node_data *n, *prev; 786 long err; 787 788 n = bpf_obj_new(typeof(*n)); 789 if (!n) 790 return -1; 791 792 prev = bpf_obj_new(typeof(*prev)); 793 if (!prev) { 794 bpf_obj_drop(n); 795 return -1; 796 } 797 798 /* Error case: add list node without holding lock */ 799 err = bpf_list_add(&head, &n->l, &prev->l); 800 bpf_obj_drop(prev); 801 if (err) 802 return -2; 803 804 return 0; 805 } 806 807 SEC("tc") 808 __success 809 long rbtree_refcounted_node_ref_escapes(void *ctx) 810 { 811 struct node_acquire *n, *m; 812 813 n = bpf_obj_new(typeof(*n)); 814 if (!n) 815 return 1; 816 817 bpf_spin_lock(&alock); 818 bpf_rbtree_add(&aroot, &n->node, less_a); 819 m = bpf_refcount_acquire(n); 820 bpf_spin_unlock(&alock); 821 if (!m) 822 return 2; 823 824 m->key = 2; 825 bpf_obj_drop(m); 826 return 0; 827 } 828 829 SEC("tc") 830 __success 831 long rbtree_refcounted_node_ref_escapes_owning_input(void *ctx) 832 { 833 struct node_acquire *n, *m; 834 835 n = bpf_obj_new(typeof(*n)); 836 if (!n) 837 return 1; 838 839 m = bpf_refcount_acquire(n); 840 m->key = 2; 841 842 bpf_spin_lock(&alock); 843 bpf_rbtree_add(&aroot, &n->node, less_a); 844 bpf_spin_unlock(&alock); 845 846 bpf_obj_drop(m); 847 848 return 0; 849 } 850 851 SEC("tc") 852 __success 853 long refcount_acquire_owning_input_no_null_check(void *ctx) 854 { 855 struct node_refcount_only *n, *m; 856 857 n = bpf_obj_new(typeof(*n)); 858 if (!n) 859 return 1; 860 861 m = bpf_refcount_acquire(n); 862 bpf_obj_drop(m); 863 bpf_obj_drop(n); 864 865 return 0; 866 } 867 868 SEC("?syscall") 869 __success 870 long refcount_acquire_rcu_map_kptr_null_checked(void *ctx) 871 { 872 struct map_value_refcount_only *mapval; 873 struct node_refcount_only *n, *m; 874 int idx = 0; 875 876 mapval = bpf_map_lookup_elem(&stashed_refcount_only, &idx); 877 if (!mapval) 878 return 1; 879 880 bpf_rcu_read_lock(); 881 n = mapval->node; 882 if (!n) { 883 bpf_rcu_read_unlock(); 884 return 2; 885 } 886 m = bpf_refcount_acquire(n); 887 bpf_rcu_read_unlock(); 888 889 if (!m) 890 return 3; 891 bpf_obj_drop(m); 892 893 return 0; 894 } 895 896 static long __stash_map_empty_xchg(struct node_data *n, int idx) 897 { 898 struct map_value *mapval = bpf_map_lookup_elem(&stashed_nodes, &idx); 899 900 if (!mapval) { 901 bpf_obj_drop(n); 902 return 1; 903 } 904 n = bpf_kptr_xchg(&mapval->node, n); 905 if (n) { 906 bpf_obj_drop(n); 907 return 2; 908 } 909 return 0; 910 } 911 912 SEC("tc") 913 long rbtree_wrong_owner_remove_fail_a1(void *ctx) 914 { 915 struct node_data *n, *m; 916 917 n = bpf_obj_new(typeof(*n)); 918 if (!n) 919 return 1; 920 m = bpf_refcount_acquire(n); 921 922 if (__stash_map_empty_xchg(n, 0)) { 923 bpf_obj_drop(m); 924 return 2; 925 } 926 927 if (__stash_map_empty_xchg(m, 1)) 928 return 3; 929 930 return 0; 931 } 932 933 SEC("tc") 934 long rbtree_wrong_owner_remove_fail_b(void *ctx) 935 { 936 struct map_value *mapval; 937 struct node_data *n; 938 int idx = 0; 939 940 mapval = bpf_map_lookup_elem(&stashed_nodes, &idx); 941 if (!mapval) 942 return 1; 943 944 n = bpf_kptr_xchg(&mapval->node, NULL); 945 if (!n) 946 return 2; 947 948 bpf_spin_lock(&block); 949 950 bpf_rbtree_add(&broot, &n->r, less); 951 952 bpf_spin_unlock(&block); 953 return 0; 954 } 955 956 SEC("tc") 957 long rbtree_wrong_owner_remove_fail_a2(void *ctx) 958 { 959 struct map_value *mapval; 960 struct bpf_rb_node *res; 961 struct node_data *m; 962 int idx = 1; 963 964 mapval = bpf_map_lookup_elem(&stashed_nodes, &idx); 965 if (!mapval) 966 return 1; 967 968 m = bpf_kptr_xchg(&mapval->node, NULL); 969 if (!m) 970 return 2; 971 bpf_spin_lock(&lock); 972 973 /* make m non-owning ref */ 974 bpf_list_push_back(&head, &m->l); 975 res = bpf_rbtree_remove(&root, &m->r); 976 977 bpf_spin_unlock(&lock); 978 if (res) { 979 bpf_obj_drop(container_of(res, struct node_data, r)); 980 return 3; 981 } 982 return 0; 983 } 984 985 SEC("?fentry.s/" SYS_PREFIX "sys_getpgid") 986 __success 987 int BPF_PROG(rbtree_sleepable_rcu, 988 struct file *file, struct kobject *kobj, 989 struct bin_attribute *bin_attr, char *buf, loff_t off, size_t len) 990 { 991 struct bpf_rb_node *rb; 992 struct node_data *n, *m = NULL; 993 994 n = bpf_obj_new(typeof(*n)); 995 if (!n) 996 return 0; 997 998 bpf_rcu_read_lock(); 999 bpf_spin_lock(&lock); 1000 bpf_rbtree_add(&root, &n->r, less); 1001 rb = bpf_rbtree_first(&root); 1002 if (!rb) 1003 goto err_out; 1004 1005 rb = bpf_rbtree_remove(&root, rb); 1006 if (!rb) 1007 goto err_out; 1008 1009 m = container_of(rb, struct node_data, r); 1010 1011 err_out: 1012 bpf_spin_unlock(&lock); 1013 bpf_rcu_read_unlock(); 1014 if (m) 1015 bpf_obj_drop(m); 1016 return 0; 1017 } 1018 1019 SEC("?fentry.s/" SYS_PREFIX "sys_getpgid") 1020 __success 1021 int BPF_PROG(rbtree_sleepable_rcu_no_explicit_rcu_lock, 1022 struct file *file, struct kobject *kobj, 1023 struct bin_attribute *bin_attr, char *buf, loff_t off, size_t len) 1024 { 1025 struct bpf_rb_node *rb; 1026 struct node_data *n, *m = NULL; 1027 1028 n = bpf_obj_new(typeof(*n)); 1029 if (!n) 1030 return 0; 1031 1032 /* No explicit bpf_rcu_read_lock */ 1033 bpf_spin_lock(&lock); 1034 bpf_rbtree_add(&root, &n->r, less); 1035 rb = bpf_rbtree_first(&root); 1036 if (!rb) 1037 goto err_out; 1038 1039 rb = bpf_rbtree_remove(&root, rb); 1040 if (!rb) 1041 goto err_out; 1042 1043 m = container_of(rb, struct node_data, r); 1044 1045 err_out: 1046 bpf_spin_unlock(&lock); 1047 /* No explicit bpf_rcu_read_unlock */ 1048 if (m) 1049 bpf_obj_drop(m); 1050 return 0; 1051 } 1052 1053 private(kptr_ref) u64 ref; 1054 1055 static int probe_read_refcount(void) 1056 { 1057 u32 refcount; 1058 1059 bpf_probe_read_kernel(&refcount, sizeof(refcount), (void *) ref); 1060 return refcount; 1061 } 1062 1063 static int __insert_in_list(struct bpf_list_head *head, struct bpf_spin_lock *lock, 1064 struct node_data __kptr **node) 1065 { 1066 struct node_data *node_new, *node_ref, *node_old; 1067 1068 node_new = bpf_obj_new(typeof(*node_new)); 1069 if (!node_new) 1070 return -1; 1071 1072 node_ref = bpf_refcount_acquire(node_new); 1073 node_old = bpf_kptr_xchg(node, node_new); 1074 if (node_old) { 1075 bpf_obj_drop(node_old); 1076 bpf_obj_drop(node_ref); 1077 return -2; 1078 } 1079 1080 bpf_spin_lock(lock); 1081 bpf_list_push_front(head, &node_ref->l); 1082 ref = (u64)(void *) &node_ref->ref; 1083 bpf_spin_unlock(lock); 1084 return probe_read_refcount(); 1085 } 1086 1087 struct { 1088 __uint(type, BPF_MAP_TYPE_PERCPU_HASH); 1089 __type(key, int); 1090 __type(value, struct map_value); 1091 __uint(max_entries, 1); 1092 } percpu_hash SEC(".maps"); 1093 1094 SEC("tc") 1095 int percpu_hash_refcount_leak(void *ctx) 1096 { 1097 struct map_value *v; 1098 int key = 0; 1099 1100 v = bpf_map_lookup_percpu_elem(&percpu_hash, &key, 0); 1101 if (!v) 1102 return 0; 1103 1104 return __insert_in_list(&head, &lock, &v->node); 1105 } 1106 1107 SEC("syscall") 1108 int clear_percpu_hash_kptr(void *ctx) 1109 { 1110 struct node_data *n; 1111 struct map_value *v; 1112 int key = 0; 1113 1114 v = bpf_map_lookup_percpu_elem(&percpu_hash, &key, 0); 1115 if (!v) 1116 return 0; 1117 1118 n = bpf_kptr_xchg(&v->node, NULL); 1119 if (!n) 1120 return 0; 1121 bpf_obj_drop(n); 1122 return probe_read_refcount(); 1123 } 1124 1125 SEC("tc") 1126 int check_percpu_hash_refcount(void *ctx) 1127 { 1128 return probe_read_refcount(); 1129 } 1130 1131 char _license[] SEC("license") = "GPL"; 1132