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