1 // SPDX-License-Identifier: GPL-2.0 2 /* 3 * KUnit test for the Kernel Linked-list structures. 4 * 5 * Copyright (C) 2019, Google LLC. 6 * Author: David Gow <davidgow@google.com> 7 */ 8 #include <kunit/test.h> 9 10 #include <linux/list.h> 11 #include <linux/klist.h> 12 13 struct list_test_struct { 14 int data; 15 struct list_head list; 16 }; 17 18 static void list_test_list_init(struct kunit *test) 19 { 20 /* Test the different ways of initialising a list. */ 21 struct list_head list1 = LIST_HEAD_INIT(list1); 22 struct list_head list2; 23 LIST_HEAD(list3); 24 struct list_head *list4; 25 struct list_head *list5; 26 27 INIT_LIST_HEAD(&list2); 28 29 list4 = kzalloc(sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL); 30 INIT_LIST_HEAD(list4); 31 32 list5 = kmalloc(sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL); 33 memset(list5, 0xFF, sizeof(*list5)); 34 INIT_LIST_HEAD(list5); 35 36 /* list_empty_careful() checks both next and prev. */ 37 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list1)); 38 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); 39 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list3)); 40 KUNIT_EXPECT_TRUE(test, list_empty_careful(list4)); 41 KUNIT_EXPECT_TRUE(test, list_empty_careful(list5)); 42 43 kfree(list4); 44 kfree(list5); 45 } 46 47 static void list_test_list_add(struct kunit *test) 48 { 49 struct list_head a, b; 50 LIST_HEAD(list); 51 52 list_add(&a, &list); 53 list_add(&b, &list); 54 55 /* should be [list] -> b -> a */ 56 KUNIT_EXPECT_PTR_EQ(test, list.next, &b); 57 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); 58 KUNIT_EXPECT_PTR_EQ(test, b.next, &a); 59 } 60 61 static void list_test_list_add_tail(struct kunit *test) 62 { 63 struct list_head a, b; 64 LIST_HEAD(list); 65 66 list_add_tail(&a, &list); 67 list_add_tail(&b, &list); 68 69 /* should be [list] -> a -> b */ 70 KUNIT_EXPECT_PTR_EQ(test, list.next, &a); 71 KUNIT_EXPECT_PTR_EQ(test, a.prev, &list); 72 KUNIT_EXPECT_PTR_EQ(test, a.next, &b); 73 } 74 75 static void list_test_list_del(struct kunit *test) 76 { 77 struct list_head a, b; 78 LIST_HEAD(list); 79 80 list_add_tail(&a, &list); 81 list_add_tail(&b, &list); 82 83 /* before: [list] -> a -> b */ 84 list_del(&a); 85 86 /* now: [list] -> b */ 87 KUNIT_EXPECT_PTR_EQ(test, list.next, &b); 88 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); 89 } 90 91 static void list_test_list_replace(struct kunit *test) 92 { 93 struct list_head a_old, a_new, b; 94 LIST_HEAD(list); 95 96 list_add_tail(&a_old, &list); 97 list_add_tail(&b, &list); 98 99 /* before: [list] -> a_old -> b */ 100 list_replace(&a_old, &a_new); 101 102 /* now: [list] -> a_new -> b */ 103 KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new); 104 KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new); 105 } 106 107 static void list_test_list_replace_init(struct kunit *test) 108 { 109 struct list_head a_old, a_new, b; 110 LIST_HEAD(list); 111 112 list_add_tail(&a_old, &list); 113 list_add_tail(&b, &list); 114 115 /* before: [list] -> a_old -> b */ 116 list_replace_init(&a_old, &a_new); 117 118 /* now: [list] -> a_new -> b */ 119 KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new); 120 KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new); 121 122 /* check a_old is empty (initialized) */ 123 KUNIT_EXPECT_TRUE(test, list_empty_careful(&a_old)); 124 } 125 126 static void list_test_list_swap(struct kunit *test) 127 { 128 struct list_head a, b; 129 LIST_HEAD(list); 130 131 list_add_tail(&a, &list); 132 list_add_tail(&b, &list); 133 134 /* before: [list] -> a -> b */ 135 list_swap(&a, &b); 136 137 /* after: [list] -> b -> a */ 138 KUNIT_EXPECT_PTR_EQ(test, &b, list.next); 139 KUNIT_EXPECT_PTR_EQ(test, &a, list.prev); 140 141 KUNIT_EXPECT_PTR_EQ(test, &a, b.next); 142 KUNIT_EXPECT_PTR_EQ(test, &list, b.prev); 143 144 KUNIT_EXPECT_PTR_EQ(test, &list, a.next); 145 KUNIT_EXPECT_PTR_EQ(test, &b, a.prev); 146 } 147 148 static void list_test_list_del_init(struct kunit *test) 149 { 150 struct list_head a, b; 151 LIST_HEAD(list); 152 153 list_add_tail(&a, &list); 154 list_add_tail(&b, &list); 155 156 /* before: [list] -> a -> b */ 157 list_del_init(&a); 158 /* after: [list] -> b, a initialised */ 159 160 KUNIT_EXPECT_PTR_EQ(test, list.next, &b); 161 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); 162 KUNIT_EXPECT_TRUE(test, list_empty_careful(&a)); 163 } 164 165 static void list_test_list_del_init_careful(struct kunit *test) 166 { 167 /* NOTE: This test only checks the behaviour of this function in 168 * isolation. It does not verify memory model guarantees. 169 */ 170 struct list_head a, b; 171 LIST_HEAD(list); 172 173 list_add_tail(&a, &list); 174 list_add_tail(&b, &list); 175 176 /* before: [list] -> a -> b */ 177 list_del_init_careful(&a); 178 /* after: [list] -> b, a initialised */ 179 180 KUNIT_EXPECT_PTR_EQ(test, list.next, &b); 181 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); 182 KUNIT_EXPECT_TRUE(test, list_empty_careful(&a)); 183 } 184 185 static void list_test_list_move(struct kunit *test) 186 { 187 struct list_head a, b; 188 LIST_HEAD(list1); 189 LIST_HEAD(list2); 190 191 list_add_tail(&a, &list1); 192 list_add_tail(&b, &list2); 193 194 /* before: [list1] -> a, [list2] -> b */ 195 list_move(&a, &list2); 196 /* after: [list1] empty, [list2] -> a -> b */ 197 198 KUNIT_EXPECT_TRUE(test, list_empty(&list1)); 199 200 KUNIT_EXPECT_PTR_EQ(test, &a, list2.next); 201 KUNIT_EXPECT_PTR_EQ(test, &b, a.next); 202 } 203 204 static void list_test_list_move_tail(struct kunit *test) 205 { 206 struct list_head a, b; 207 LIST_HEAD(list1); 208 LIST_HEAD(list2); 209 210 list_add_tail(&a, &list1); 211 list_add_tail(&b, &list2); 212 213 /* before: [list1] -> a, [list2] -> b */ 214 list_move_tail(&a, &list2); 215 /* after: [list1] empty, [list2] -> b -> a */ 216 217 KUNIT_EXPECT_TRUE(test, list_empty(&list1)); 218 219 KUNIT_EXPECT_PTR_EQ(test, &b, list2.next); 220 KUNIT_EXPECT_PTR_EQ(test, &a, b.next); 221 } 222 223 static void list_test_list_bulk_move_tail(struct kunit *test) 224 { 225 struct list_head a, b, c, d, x, y; 226 struct list_head *list1_values[] = { &x, &b, &c, &y }; 227 struct list_head *list2_values[] = { &a, &d }; 228 struct list_head *ptr; 229 LIST_HEAD(list1); 230 LIST_HEAD(list2); 231 int i = 0; 232 233 list_add_tail(&x, &list1); 234 list_add_tail(&y, &list1); 235 236 list_add_tail(&a, &list2); 237 list_add_tail(&b, &list2); 238 list_add_tail(&c, &list2); 239 list_add_tail(&d, &list2); 240 241 /* before: [list1] -> x -> y, [list2] -> a -> b -> c -> d */ 242 list_bulk_move_tail(&y, &b, &c); 243 /* after: [list1] -> x -> b -> c -> y, [list2] -> a -> d */ 244 245 list_for_each(ptr, &list1) { 246 KUNIT_EXPECT_PTR_EQ(test, ptr, list1_values[i]); 247 i++; 248 } 249 KUNIT_EXPECT_EQ(test, i, 4); 250 i = 0; 251 list_for_each(ptr, &list2) { 252 KUNIT_EXPECT_PTR_EQ(test, ptr, list2_values[i]); 253 i++; 254 } 255 KUNIT_EXPECT_EQ(test, i, 2); 256 } 257 258 static void list_test_list_is_head(struct kunit *test) 259 { 260 struct list_head a, b, c; 261 262 /* Two lists: [a] -> b, [c] */ 263 INIT_LIST_HEAD(&a); 264 INIT_LIST_HEAD(&c); 265 list_add_tail(&b, &a); 266 267 KUNIT_EXPECT_TRUE_MSG(test, list_is_head(&a, &a), 268 "Head element of same list"); 269 KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &b), 270 "Non-head element of same list"); 271 KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &c), 272 "Head element of different list"); 273 } 274 275 276 static void list_test_list_is_first(struct kunit *test) 277 { 278 struct list_head a, b; 279 LIST_HEAD(list); 280 281 list_add_tail(&a, &list); 282 list_add_tail(&b, &list); 283 284 KUNIT_EXPECT_TRUE(test, list_is_first(&a, &list)); 285 KUNIT_EXPECT_FALSE(test, list_is_first(&b, &list)); 286 } 287 288 static void list_test_list_is_last(struct kunit *test) 289 { 290 struct list_head a, b; 291 LIST_HEAD(list); 292 293 list_add_tail(&a, &list); 294 list_add_tail(&b, &list); 295 296 KUNIT_EXPECT_FALSE(test, list_is_last(&a, &list)); 297 KUNIT_EXPECT_TRUE(test, list_is_last(&b, &list)); 298 } 299 300 static void list_test_list_empty(struct kunit *test) 301 { 302 struct list_head a; 303 LIST_HEAD(list1); 304 LIST_HEAD(list2); 305 306 list_add_tail(&a, &list1); 307 308 KUNIT_EXPECT_FALSE(test, list_empty(&list1)); 309 KUNIT_EXPECT_TRUE(test, list_empty(&list2)); 310 } 311 312 static void list_test_list_empty_careful(struct kunit *test) 313 { 314 /* This test doesn't check correctness under concurrent access */ 315 struct list_head a; 316 LIST_HEAD(list1); 317 LIST_HEAD(list2); 318 319 list_add_tail(&a, &list1); 320 321 KUNIT_EXPECT_FALSE(test, list_empty_careful(&list1)); 322 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); 323 } 324 325 static void list_test_list_rotate_left(struct kunit *test) 326 { 327 struct list_head a, b; 328 LIST_HEAD(list); 329 330 list_add_tail(&a, &list); 331 list_add_tail(&b, &list); 332 333 /* before: [list] -> a -> b */ 334 list_rotate_left(&list); 335 /* after: [list] -> b -> a */ 336 337 KUNIT_EXPECT_PTR_EQ(test, list.next, &b); 338 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); 339 KUNIT_EXPECT_PTR_EQ(test, b.next, &a); 340 } 341 342 static void list_test_list_rotate_to_front(struct kunit *test) 343 { 344 struct list_head a, b, c, d; 345 struct list_head *list_values[] = { &c, &d, &a, &b }; 346 struct list_head *ptr; 347 LIST_HEAD(list); 348 int i = 0; 349 350 list_add_tail(&a, &list); 351 list_add_tail(&b, &list); 352 list_add_tail(&c, &list); 353 list_add_tail(&d, &list); 354 355 /* before: [list] -> a -> b -> c -> d */ 356 list_rotate_to_front(&c, &list); 357 /* after: [list] -> c -> d -> a -> b */ 358 359 list_for_each(ptr, &list) { 360 KUNIT_EXPECT_PTR_EQ(test, ptr, list_values[i]); 361 i++; 362 } 363 KUNIT_EXPECT_EQ(test, i, 4); 364 } 365 366 static void list_test_list_is_singular(struct kunit *test) 367 { 368 struct list_head a, b; 369 LIST_HEAD(list); 370 371 /* [list] empty */ 372 KUNIT_EXPECT_FALSE(test, list_is_singular(&list)); 373 374 list_add_tail(&a, &list); 375 376 /* [list] -> a */ 377 KUNIT_EXPECT_TRUE(test, list_is_singular(&list)); 378 379 list_add_tail(&b, &list); 380 381 /* [list] -> a -> b */ 382 KUNIT_EXPECT_FALSE(test, list_is_singular(&list)); 383 } 384 385 static void list_test_list_cut_position(struct kunit *test) 386 { 387 struct list_head entries[3], *cur; 388 LIST_HEAD(list1); 389 LIST_HEAD(list2); 390 int i = 0; 391 392 list_add_tail(&entries[0], &list1); 393 list_add_tail(&entries[1], &list1); 394 list_add_tail(&entries[2], &list1); 395 396 /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */ 397 list_cut_position(&list2, &list1, &entries[1]); 398 /* after: [list2] -> entries[0] -> entries[1], [list1] -> entries[2] */ 399 400 list_for_each(cur, &list2) { 401 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 402 i++; 403 } 404 405 KUNIT_EXPECT_EQ(test, i, 2); 406 407 list_for_each(cur, &list1) { 408 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 409 i++; 410 } 411 } 412 413 static void list_test_list_cut_before(struct kunit *test) 414 { 415 struct list_head entries[3], *cur; 416 LIST_HEAD(list1); 417 LIST_HEAD(list2); 418 int i = 0; 419 420 list_add_tail(&entries[0], &list1); 421 list_add_tail(&entries[1], &list1); 422 list_add_tail(&entries[2], &list1); 423 424 /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */ 425 list_cut_before(&list2, &list1, &entries[1]); 426 /* after: [list2] -> entries[0], [list1] -> entries[1] -> entries[2] */ 427 428 list_for_each(cur, &list2) { 429 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 430 i++; 431 } 432 433 KUNIT_EXPECT_EQ(test, i, 1); 434 435 list_for_each(cur, &list1) { 436 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 437 i++; 438 } 439 } 440 441 static void list_test_list_splice(struct kunit *test) 442 { 443 struct list_head entries[5], *cur; 444 LIST_HEAD(list1); 445 LIST_HEAD(list2); 446 int i = 0; 447 448 list_add_tail(&entries[0], &list1); 449 list_add_tail(&entries[1], &list1); 450 list_add_tail(&entries[2], &list2); 451 list_add_tail(&entries[3], &list2); 452 list_add_tail(&entries[4], &list1); 453 454 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ 455 list_splice(&list2, &entries[1]); 456 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */ 457 458 list_for_each(cur, &list1) { 459 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 460 i++; 461 } 462 463 KUNIT_EXPECT_EQ(test, i, 5); 464 } 465 466 static void list_test_list_splice_tail(struct kunit *test) 467 { 468 struct list_head entries[5], *cur; 469 LIST_HEAD(list1); 470 LIST_HEAD(list2); 471 int i = 0; 472 473 list_add_tail(&entries[0], &list1); 474 list_add_tail(&entries[1], &list1); 475 list_add_tail(&entries[2], &list2); 476 list_add_tail(&entries[3], &list2); 477 list_add_tail(&entries[4], &list1); 478 479 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ 480 list_splice_tail(&list2, &entries[4]); 481 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */ 482 483 list_for_each(cur, &list1) { 484 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 485 i++; 486 } 487 488 KUNIT_EXPECT_EQ(test, i, 5); 489 } 490 491 static void list_test_list_splice_init(struct kunit *test) 492 { 493 struct list_head entries[5], *cur; 494 LIST_HEAD(list1); 495 LIST_HEAD(list2); 496 int i = 0; 497 498 list_add_tail(&entries[0], &list1); 499 list_add_tail(&entries[1], &list1); 500 list_add_tail(&entries[2], &list2); 501 list_add_tail(&entries[3], &list2); 502 list_add_tail(&entries[4], &list1); 503 504 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ 505 list_splice_init(&list2, &entries[1]); 506 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */ 507 508 list_for_each(cur, &list1) { 509 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 510 i++; 511 } 512 513 KUNIT_EXPECT_EQ(test, i, 5); 514 515 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); 516 } 517 518 static void list_test_list_splice_tail_init(struct kunit *test) 519 { 520 struct list_head entries[5], *cur; 521 LIST_HEAD(list1); 522 LIST_HEAD(list2); 523 int i = 0; 524 525 list_add_tail(&entries[0], &list1); 526 list_add_tail(&entries[1], &list1); 527 list_add_tail(&entries[2], &list2); 528 list_add_tail(&entries[3], &list2); 529 list_add_tail(&entries[4], &list1); 530 531 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ 532 list_splice_tail_init(&list2, &entries[4]); 533 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */ 534 535 list_for_each(cur, &list1) { 536 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 537 i++; 538 } 539 540 KUNIT_EXPECT_EQ(test, i, 5); 541 542 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); 543 } 544 545 static void list_test_list_entry(struct kunit *test) 546 { 547 struct list_test_struct test_struct; 548 549 KUNIT_EXPECT_PTR_EQ(test, &test_struct, list_entry(&(test_struct.list), 550 struct list_test_struct, list)); 551 } 552 553 static void list_test_list_entry_is_head(struct kunit *test) 554 { 555 struct list_test_struct test_struct1, test_struct2, test_struct3; 556 557 INIT_LIST_HEAD(&test_struct1.list); 558 INIT_LIST_HEAD(&test_struct3.list); 559 560 list_add_tail(&test_struct2.list, &test_struct1.list); 561 562 KUNIT_EXPECT_TRUE_MSG(test, 563 list_entry_is_head((&test_struct1), &test_struct1.list, list), 564 "Head element of same list"); 565 KUNIT_EXPECT_FALSE_MSG(test, 566 list_entry_is_head((&test_struct2), &test_struct1.list, list), 567 "Non-head element of same list"); 568 KUNIT_EXPECT_FALSE_MSG(test, 569 list_entry_is_head((&test_struct3), &test_struct1.list, list), 570 "Head element of different list"); 571 } 572 573 static void list_test_list_first_entry(struct kunit *test) 574 { 575 struct list_test_struct test_struct1, test_struct2; 576 LIST_HEAD(list); 577 578 list_add_tail(&test_struct1.list, &list); 579 list_add_tail(&test_struct2.list, &list); 580 581 582 KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_first_entry(&list, 583 struct list_test_struct, list)); 584 } 585 586 static void list_test_list_last_entry(struct kunit *test) 587 { 588 struct list_test_struct test_struct1, test_struct2; 589 LIST_HEAD(list); 590 591 list_add_tail(&test_struct1.list, &list); 592 list_add_tail(&test_struct2.list, &list); 593 594 595 KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_last_entry(&list, 596 struct list_test_struct, list)); 597 } 598 599 static void list_test_list_first_entry_or_null(struct kunit *test) 600 { 601 struct list_test_struct test_struct1, test_struct2; 602 LIST_HEAD(list); 603 604 KUNIT_EXPECT_FALSE(test, list_first_entry_or_null(&list, 605 struct list_test_struct, list)); 606 607 list_add_tail(&test_struct1.list, &list); 608 list_add_tail(&test_struct2.list, &list); 609 610 KUNIT_EXPECT_PTR_EQ(test, &test_struct1, 611 list_first_entry_or_null(&list, 612 struct list_test_struct, list)); 613 } 614 615 static void list_test_list_next_entry(struct kunit *test) 616 { 617 struct list_test_struct test_struct1, test_struct2; 618 LIST_HEAD(list); 619 620 list_add_tail(&test_struct1.list, &list); 621 list_add_tail(&test_struct2.list, &list); 622 623 624 KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_next_entry(&test_struct1, 625 list)); 626 } 627 628 static void list_test_list_prev_entry(struct kunit *test) 629 { 630 struct list_test_struct test_struct1, test_struct2; 631 LIST_HEAD(list); 632 633 list_add_tail(&test_struct1.list, &list); 634 list_add_tail(&test_struct2.list, &list); 635 636 637 KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_prev_entry(&test_struct2, 638 list)); 639 } 640 641 static void list_test_list_for_each(struct kunit *test) 642 { 643 struct list_head entries[3], *cur; 644 LIST_HEAD(list); 645 int i = 0; 646 647 list_add_tail(&entries[0], &list); 648 list_add_tail(&entries[1], &list); 649 list_add_tail(&entries[2], &list); 650 651 list_for_each(cur, &list) { 652 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 653 i++; 654 } 655 656 KUNIT_EXPECT_EQ(test, i, 3); 657 } 658 659 static void list_test_list_for_each_prev(struct kunit *test) 660 { 661 struct list_head entries[3], *cur; 662 LIST_HEAD(list); 663 int i = 2; 664 665 list_add_tail(&entries[0], &list); 666 list_add_tail(&entries[1], &list); 667 list_add_tail(&entries[2], &list); 668 669 list_for_each_prev(cur, &list) { 670 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 671 i--; 672 } 673 674 KUNIT_EXPECT_EQ(test, i, -1); 675 } 676 677 static void list_test_list_for_each_safe(struct kunit *test) 678 { 679 struct list_head entries[3], *cur, *n; 680 LIST_HEAD(list); 681 int i = 0; 682 683 684 list_add_tail(&entries[0], &list); 685 list_add_tail(&entries[1], &list); 686 list_add_tail(&entries[2], &list); 687 688 list_for_each_safe(cur, n, &list) { 689 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 690 list_del(&entries[i]); 691 i++; 692 } 693 694 KUNIT_EXPECT_EQ(test, i, 3); 695 KUNIT_EXPECT_TRUE(test, list_empty(&list)); 696 } 697 698 static void list_test_list_for_each_prev_safe(struct kunit *test) 699 { 700 struct list_head entries[3], *cur, *n; 701 LIST_HEAD(list); 702 int i = 2; 703 704 list_add_tail(&entries[0], &list); 705 list_add_tail(&entries[1], &list); 706 list_add_tail(&entries[2], &list); 707 708 list_for_each_prev_safe(cur, n, &list) { 709 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 710 list_del(&entries[i]); 711 i--; 712 } 713 714 KUNIT_EXPECT_EQ(test, i, -1); 715 KUNIT_EXPECT_TRUE(test, list_empty(&list)); 716 } 717 718 static void list_test_list_for_each_entry(struct kunit *test) 719 { 720 struct list_test_struct entries[5], *cur; 721 LIST_HEAD(list); 722 int i = 0; 723 724 for (i = 0; i < 5; ++i) { 725 entries[i].data = i; 726 list_add_tail(&entries[i].list, &list); 727 } 728 729 i = 0; 730 731 list_for_each_entry(cur, &list, list) { 732 KUNIT_EXPECT_EQ(test, cur->data, i); 733 i++; 734 } 735 736 KUNIT_EXPECT_EQ(test, i, 5); 737 } 738 739 static void list_test_list_for_each_entry_reverse(struct kunit *test) 740 { 741 struct list_test_struct entries[5], *cur; 742 LIST_HEAD(list); 743 int i = 0; 744 745 for (i = 0; i < 5; ++i) { 746 entries[i].data = i; 747 list_add_tail(&entries[i].list, &list); 748 } 749 750 i = 4; 751 752 list_for_each_entry_reverse(cur, &list, list) { 753 KUNIT_EXPECT_EQ(test, cur->data, i); 754 i--; 755 } 756 757 KUNIT_EXPECT_EQ(test, i, -1); 758 } 759 760 static struct kunit_case list_test_cases[] = { 761 KUNIT_CASE(list_test_list_init), 762 KUNIT_CASE(list_test_list_add), 763 KUNIT_CASE(list_test_list_add_tail), 764 KUNIT_CASE(list_test_list_del), 765 KUNIT_CASE(list_test_list_replace), 766 KUNIT_CASE(list_test_list_replace_init), 767 KUNIT_CASE(list_test_list_swap), 768 KUNIT_CASE(list_test_list_del_init), 769 KUNIT_CASE(list_test_list_del_init_careful), 770 KUNIT_CASE(list_test_list_move), 771 KUNIT_CASE(list_test_list_move_tail), 772 KUNIT_CASE(list_test_list_bulk_move_tail), 773 KUNIT_CASE(list_test_list_is_head), 774 KUNIT_CASE(list_test_list_is_first), 775 KUNIT_CASE(list_test_list_is_last), 776 KUNIT_CASE(list_test_list_empty), 777 KUNIT_CASE(list_test_list_empty_careful), 778 KUNIT_CASE(list_test_list_rotate_left), 779 KUNIT_CASE(list_test_list_rotate_to_front), 780 KUNIT_CASE(list_test_list_is_singular), 781 KUNIT_CASE(list_test_list_cut_position), 782 KUNIT_CASE(list_test_list_cut_before), 783 KUNIT_CASE(list_test_list_splice), 784 KUNIT_CASE(list_test_list_splice_tail), 785 KUNIT_CASE(list_test_list_splice_init), 786 KUNIT_CASE(list_test_list_splice_tail_init), 787 KUNIT_CASE(list_test_list_entry), 788 KUNIT_CASE(list_test_list_entry_is_head), 789 KUNIT_CASE(list_test_list_first_entry), 790 KUNIT_CASE(list_test_list_last_entry), 791 KUNIT_CASE(list_test_list_first_entry_or_null), 792 KUNIT_CASE(list_test_list_next_entry), 793 KUNIT_CASE(list_test_list_prev_entry), 794 KUNIT_CASE(list_test_list_for_each), 795 KUNIT_CASE(list_test_list_for_each_prev), 796 KUNIT_CASE(list_test_list_for_each_safe), 797 KUNIT_CASE(list_test_list_for_each_prev_safe), 798 KUNIT_CASE(list_test_list_for_each_entry), 799 KUNIT_CASE(list_test_list_for_each_entry_reverse), 800 {}, 801 }; 802 803 static struct kunit_suite list_test_module = { 804 .name = "list-kunit-test", 805 .test_cases = list_test_cases, 806 }; 807 808 struct hlist_test_struct { 809 int data; 810 struct hlist_node list; 811 }; 812 813 static void hlist_test_init(struct kunit *test) 814 { 815 /* Test the different ways of initialising a list. */ 816 struct hlist_head list1 = HLIST_HEAD_INIT; 817 struct hlist_head list2; 818 HLIST_HEAD(list3); 819 struct hlist_head *list4; 820 struct hlist_head *list5; 821 822 INIT_HLIST_HEAD(&list2); 823 824 list4 = kzalloc(sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL); 825 INIT_HLIST_HEAD(list4); 826 827 list5 = kmalloc(sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL); 828 memset(list5, 0xFF, sizeof(*list5)); 829 INIT_HLIST_HEAD(list5); 830 831 KUNIT_EXPECT_TRUE(test, hlist_empty(&list1)); 832 KUNIT_EXPECT_TRUE(test, hlist_empty(&list2)); 833 KUNIT_EXPECT_TRUE(test, hlist_empty(&list3)); 834 KUNIT_EXPECT_TRUE(test, hlist_empty(list4)); 835 KUNIT_EXPECT_TRUE(test, hlist_empty(list5)); 836 837 kfree(list4); 838 kfree(list5); 839 } 840 841 static void hlist_test_unhashed(struct kunit *test) 842 { 843 struct hlist_node a; 844 HLIST_HEAD(list); 845 846 INIT_HLIST_NODE(&a); 847 848 /* is unhashed by default */ 849 KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a)); 850 851 hlist_add_head(&a, &list); 852 853 /* is hashed once added to list */ 854 KUNIT_EXPECT_FALSE(test, hlist_unhashed(&a)); 855 856 hlist_del_init(&a); 857 858 /* is again unhashed after del_init */ 859 KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a)); 860 } 861 862 /* Doesn't test concurrency guarantees */ 863 static void hlist_test_unhashed_lockless(struct kunit *test) 864 { 865 struct hlist_node a; 866 HLIST_HEAD(list); 867 868 INIT_HLIST_NODE(&a); 869 870 /* is unhashed by default */ 871 KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a)); 872 873 hlist_add_head(&a, &list); 874 875 /* is hashed once added to list */ 876 KUNIT_EXPECT_FALSE(test, hlist_unhashed_lockless(&a)); 877 878 hlist_del_init(&a); 879 880 /* is again unhashed after del_init */ 881 KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a)); 882 } 883 884 static void hlist_test_del(struct kunit *test) 885 { 886 struct hlist_node a, b; 887 HLIST_HEAD(list); 888 889 hlist_add_head(&a, &list); 890 hlist_add_behind(&b, &a); 891 892 /* before: [list] -> a -> b */ 893 hlist_del(&a); 894 895 /* now: [list] -> b */ 896 KUNIT_EXPECT_PTR_EQ(test, list.first, &b); 897 KUNIT_EXPECT_PTR_EQ(test, b.pprev, &list.first); 898 } 899 900 static void hlist_test_del_init(struct kunit *test) 901 { 902 struct hlist_node a, b; 903 HLIST_HEAD(list); 904 905 hlist_add_head(&a, &list); 906 hlist_add_behind(&b, &a); 907 908 /* before: [list] -> a -> b */ 909 hlist_del_init(&a); 910 911 /* now: [list] -> b */ 912 KUNIT_EXPECT_PTR_EQ(test, list.first, &b); 913 KUNIT_EXPECT_PTR_EQ(test, b.pprev, &list.first); 914 915 /* a is now initialised */ 916 KUNIT_EXPECT_PTR_EQ(test, a.next, NULL); 917 KUNIT_EXPECT_PTR_EQ(test, a.pprev, NULL); 918 } 919 920 /* Tests all three hlist_add_* functions */ 921 static void hlist_test_add(struct kunit *test) 922 { 923 struct hlist_node a, b, c, d; 924 HLIST_HEAD(list); 925 926 hlist_add_head(&a, &list); 927 hlist_add_head(&b, &list); 928 hlist_add_before(&c, &a); 929 hlist_add_behind(&d, &a); 930 931 /* should be [list] -> b -> c -> a -> d */ 932 KUNIT_EXPECT_PTR_EQ(test, list.first, &b); 933 934 KUNIT_EXPECT_PTR_EQ(test, c.pprev, &(b.next)); 935 KUNIT_EXPECT_PTR_EQ(test, b.next, &c); 936 937 KUNIT_EXPECT_PTR_EQ(test, a.pprev, &(c.next)); 938 KUNIT_EXPECT_PTR_EQ(test, c.next, &a); 939 940 KUNIT_EXPECT_PTR_EQ(test, d.pprev, &(a.next)); 941 KUNIT_EXPECT_PTR_EQ(test, a.next, &d); 942 } 943 944 /* Tests both hlist_fake() and hlist_add_fake() */ 945 static void hlist_test_fake(struct kunit *test) 946 { 947 struct hlist_node a; 948 949 INIT_HLIST_NODE(&a); 950 951 /* not fake after init */ 952 KUNIT_EXPECT_FALSE(test, hlist_fake(&a)); 953 954 hlist_add_fake(&a); 955 956 /* is now fake */ 957 KUNIT_EXPECT_TRUE(test, hlist_fake(&a)); 958 } 959 960 static void hlist_test_is_singular_node(struct kunit *test) 961 { 962 struct hlist_node a, b; 963 HLIST_HEAD(list); 964 965 INIT_HLIST_NODE(&a); 966 KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list)); 967 968 hlist_add_head(&a, &list); 969 KUNIT_EXPECT_TRUE(test, hlist_is_singular_node(&a, &list)); 970 971 hlist_add_head(&b, &list); 972 KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list)); 973 KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&b, &list)); 974 } 975 976 static void hlist_test_empty(struct kunit *test) 977 { 978 struct hlist_node a; 979 HLIST_HEAD(list); 980 981 /* list starts off empty */ 982 KUNIT_EXPECT_TRUE(test, hlist_empty(&list)); 983 984 hlist_add_head(&a, &list); 985 986 /* list is no longer empty */ 987 KUNIT_EXPECT_FALSE(test, hlist_empty(&list)); 988 } 989 990 static void hlist_test_move_list(struct kunit *test) 991 { 992 struct hlist_node a; 993 HLIST_HEAD(list1); 994 HLIST_HEAD(list2); 995 996 hlist_add_head(&a, &list1); 997 998 KUNIT_EXPECT_FALSE(test, hlist_empty(&list1)); 999 KUNIT_EXPECT_TRUE(test, hlist_empty(&list2)); 1000 hlist_move_list(&list1, &list2); 1001 KUNIT_EXPECT_TRUE(test, hlist_empty(&list1)); 1002 KUNIT_EXPECT_FALSE(test, hlist_empty(&list2)); 1003 1004 } 1005 1006 static void hlist_test_entry(struct kunit *test) 1007 { 1008 struct hlist_test_struct test_struct; 1009 1010 KUNIT_EXPECT_PTR_EQ(test, &test_struct, 1011 hlist_entry(&(test_struct.list), 1012 struct hlist_test_struct, list)); 1013 } 1014 1015 static void hlist_test_entry_safe(struct kunit *test) 1016 { 1017 struct hlist_test_struct test_struct; 1018 1019 KUNIT_EXPECT_PTR_EQ(test, &test_struct, 1020 hlist_entry_safe(&(test_struct.list), 1021 struct hlist_test_struct, list)); 1022 1023 KUNIT_EXPECT_PTR_EQ(test, NULL, 1024 hlist_entry_safe((struct hlist_node *)NULL, 1025 struct hlist_test_struct, list)); 1026 } 1027 1028 static void hlist_test_for_each(struct kunit *test) 1029 { 1030 struct hlist_node entries[3], *cur; 1031 HLIST_HEAD(list); 1032 int i = 0; 1033 1034 hlist_add_head(&entries[0], &list); 1035 hlist_add_behind(&entries[1], &entries[0]); 1036 hlist_add_behind(&entries[2], &entries[1]); 1037 1038 hlist_for_each(cur, &list) { 1039 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 1040 i++; 1041 } 1042 1043 KUNIT_EXPECT_EQ(test, i, 3); 1044 } 1045 1046 1047 static void hlist_test_for_each_safe(struct kunit *test) 1048 { 1049 struct hlist_node entries[3], *cur, *n; 1050 HLIST_HEAD(list); 1051 int i = 0; 1052 1053 hlist_add_head(&entries[0], &list); 1054 hlist_add_behind(&entries[1], &entries[0]); 1055 hlist_add_behind(&entries[2], &entries[1]); 1056 1057 hlist_for_each_safe(cur, n, &list) { 1058 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 1059 hlist_del(&entries[i]); 1060 i++; 1061 } 1062 1063 KUNIT_EXPECT_EQ(test, i, 3); 1064 KUNIT_EXPECT_TRUE(test, hlist_empty(&list)); 1065 } 1066 1067 static void hlist_test_for_each_entry(struct kunit *test) 1068 { 1069 struct hlist_test_struct entries[5], *cur; 1070 HLIST_HEAD(list); 1071 int i = 0; 1072 1073 entries[0].data = 0; 1074 hlist_add_head(&entries[0].list, &list); 1075 for (i = 1; i < 5; ++i) { 1076 entries[i].data = i; 1077 hlist_add_behind(&entries[i].list, &entries[i-1].list); 1078 } 1079 1080 i = 0; 1081 1082 hlist_for_each_entry(cur, &list, list) { 1083 KUNIT_EXPECT_EQ(test, cur->data, i); 1084 i++; 1085 } 1086 1087 KUNIT_EXPECT_EQ(test, i, 5); 1088 } 1089 1090 static void hlist_test_for_each_entry_continue(struct kunit *test) 1091 { 1092 struct hlist_test_struct entries[5], *cur; 1093 HLIST_HEAD(list); 1094 int i = 0; 1095 1096 entries[0].data = 0; 1097 hlist_add_head(&entries[0].list, &list); 1098 for (i = 1; i < 5; ++i) { 1099 entries[i].data = i; 1100 hlist_add_behind(&entries[i].list, &entries[i-1].list); 1101 } 1102 1103 /* We skip the first (zero-th) entry. */ 1104 i = 1; 1105 1106 cur = &entries[0]; 1107 hlist_for_each_entry_continue(cur, list) { 1108 KUNIT_EXPECT_EQ(test, cur->data, i); 1109 /* Stamp over the entry. */ 1110 cur->data = 42; 1111 i++; 1112 } 1113 1114 KUNIT_EXPECT_EQ(test, i, 5); 1115 /* The first entry was not visited. */ 1116 KUNIT_EXPECT_EQ(test, entries[0].data, 0); 1117 /* The second (and presumably others), were. */ 1118 KUNIT_EXPECT_EQ(test, entries[1].data, 42); 1119 } 1120 1121 static void hlist_test_for_each_entry_from(struct kunit *test) 1122 { 1123 struct hlist_test_struct entries[5], *cur; 1124 HLIST_HEAD(list); 1125 int i = 0; 1126 1127 entries[0].data = 0; 1128 hlist_add_head(&entries[0].list, &list); 1129 for (i = 1; i < 5; ++i) { 1130 entries[i].data = i; 1131 hlist_add_behind(&entries[i].list, &entries[i-1].list); 1132 } 1133 1134 i = 0; 1135 1136 cur = &entries[0]; 1137 hlist_for_each_entry_from(cur, list) { 1138 KUNIT_EXPECT_EQ(test, cur->data, i); 1139 /* Stamp over the entry. */ 1140 cur->data = 42; 1141 i++; 1142 } 1143 1144 KUNIT_EXPECT_EQ(test, i, 5); 1145 /* The first entry was visited. */ 1146 KUNIT_EXPECT_EQ(test, entries[0].data, 42); 1147 } 1148 1149 static void hlist_test_for_each_entry_safe(struct kunit *test) 1150 { 1151 struct hlist_test_struct entries[5], *cur; 1152 struct hlist_node *tmp_node; 1153 HLIST_HEAD(list); 1154 int i = 0; 1155 1156 entries[0].data = 0; 1157 hlist_add_head(&entries[0].list, &list); 1158 for (i = 1; i < 5; ++i) { 1159 entries[i].data = i; 1160 hlist_add_behind(&entries[i].list, &entries[i-1].list); 1161 } 1162 1163 i = 0; 1164 1165 hlist_for_each_entry_safe(cur, tmp_node, &list, list) { 1166 KUNIT_EXPECT_EQ(test, cur->data, i); 1167 hlist_del(&cur->list); 1168 i++; 1169 } 1170 1171 KUNIT_EXPECT_EQ(test, i, 5); 1172 KUNIT_EXPECT_TRUE(test, hlist_empty(&list)); 1173 } 1174 1175 1176 static struct kunit_case hlist_test_cases[] = { 1177 KUNIT_CASE(hlist_test_init), 1178 KUNIT_CASE(hlist_test_unhashed), 1179 KUNIT_CASE(hlist_test_unhashed_lockless), 1180 KUNIT_CASE(hlist_test_del), 1181 KUNIT_CASE(hlist_test_del_init), 1182 KUNIT_CASE(hlist_test_add), 1183 KUNIT_CASE(hlist_test_fake), 1184 KUNIT_CASE(hlist_test_is_singular_node), 1185 KUNIT_CASE(hlist_test_empty), 1186 KUNIT_CASE(hlist_test_move_list), 1187 KUNIT_CASE(hlist_test_entry), 1188 KUNIT_CASE(hlist_test_entry_safe), 1189 KUNIT_CASE(hlist_test_for_each), 1190 KUNIT_CASE(hlist_test_for_each_safe), 1191 KUNIT_CASE(hlist_test_for_each_entry), 1192 KUNIT_CASE(hlist_test_for_each_entry_continue), 1193 KUNIT_CASE(hlist_test_for_each_entry_from), 1194 KUNIT_CASE(hlist_test_for_each_entry_safe), 1195 {}, 1196 }; 1197 1198 static struct kunit_suite hlist_test_module = { 1199 .name = "hlist", 1200 .test_cases = hlist_test_cases, 1201 }; 1202 1203 1204 struct klist_test_struct { 1205 int data; 1206 struct klist klist; 1207 struct klist_node klist_node; 1208 }; 1209 1210 static int node_count; 1211 static struct klist_node *last_node; 1212 1213 static void check_node(struct klist_node *node_ptr) 1214 { 1215 node_count++; 1216 last_node = node_ptr; 1217 } 1218 1219 static void check_delete_node(struct klist_node *node_ptr) 1220 { 1221 node_count--; 1222 last_node = node_ptr; 1223 } 1224 1225 static void klist_test_add_tail(struct kunit *test) 1226 { 1227 struct klist_node a, b; 1228 struct klist mylist; 1229 struct klist_iter i; 1230 1231 node_count = 0; 1232 klist_init(&mylist, &check_node, NULL); 1233 1234 klist_add_tail(&a, &mylist); 1235 KUNIT_EXPECT_EQ(test, node_count, 1); 1236 KUNIT_EXPECT_PTR_EQ(test, last_node, &a); 1237 1238 klist_add_tail(&b, &mylist); 1239 KUNIT_EXPECT_EQ(test, node_count, 2); 1240 KUNIT_EXPECT_PTR_EQ(test, last_node, &b); 1241 1242 /* should be [list] -> a -> b */ 1243 klist_iter_init(&mylist, &i); 1244 1245 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a); 1246 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b); 1247 KUNIT_EXPECT_NULL(test, klist_next(&i)); 1248 1249 klist_iter_exit(&i); 1250 1251 } 1252 1253 static void klist_test_add_head(struct kunit *test) 1254 { 1255 struct klist_node a, b; 1256 struct klist mylist; 1257 struct klist_iter i; 1258 1259 node_count = 0; 1260 klist_init(&mylist, &check_node, NULL); 1261 1262 klist_add_head(&a, &mylist); 1263 KUNIT_EXPECT_EQ(test, node_count, 1); 1264 KUNIT_EXPECT_PTR_EQ(test, last_node, &a); 1265 1266 klist_add_head(&b, &mylist); 1267 KUNIT_EXPECT_EQ(test, node_count, 2); 1268 KUNIT_EXPECT_PTR_EQ(test, last_node, &b); 1269 1270 /* should be [list] -> b -> a */ 1271 klist_iter_init(&mylist, &i); 1272 1273 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b); 1274 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a); 1275 KUNIT_EXPECT_NULL(test, klist_next(&i)); 1276 1277 klist_iter_exit(&i); 1278 1279 } 1280 1281 static void klist_test_add_behind(struct kunit *test) 1282 { 1283 struct klist_node a, b, c, d; 1284 struct klist mylist; 1285 struct klist_iter i; 1286 1287 node_count = 0; 1288 klist_init(&mylist, &check_node, NULL); 1289 1290 klist_add_head(&a, &mylist); 1291 klist_add_head(&b, &mylist); 1292 1293 klist_add_behind(&c, &a); 1294 KUNIT_EXPECT_EQ(test, node_count, 3); 1295 KUNIT_EXPECT_PTR_EQ(test, last_node, &c); 1296 1297 klist_add_behind(&d, &b); 1298 KUNIT_EXPECT_EQ(test, node_count, 4); 1299 KUNIT_EXPECT_PTR_EQ(test, last_node, &d); 1300 1301 klist_iter_init(&mylist, &i); 1302 1303 /* should be [list] -> b -> d -> a -> c*/ 1304 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b); 1305 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d); 1306 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a); 1307 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c); 1308 KUNIT_EXPECT_NULL(test, klist_next(&i)); 1309 1310 klist_iter_exit(&i); 1311 1312 } 1313 1314 static void klist_test_add_before(struct kunit *test) 1315 { 1316 struct klist_node a, b, c, d; 1317 struct klist mylist; 1318 struct klist_iter i; 1319 1320 node_count = 0; 1321 klist_init(&mylist, &check_node, NULL); 1322 1323 klist_add_head(&a, &mylist); 1324 klist_add_head(&b, &mylist); 1325 klist_add_before(&c, &a); 1326 KUNIT_EXPECT_EQ(test, node_count, 3); 1327 KUNIT_EXPECT_PTR_EQ(test, last_node, &c); 1328 1329 klist_add_before(&d, &b); 1330 KUNIT_EXPECT_EQ(test, node_count, 4); 1331 KUNIT_EXPECT_PTR_EQ(test, last_node, &d); 1332 1333 klist_iter_init(&mylist, &i); 1334 1335 /* should be [list] -> b -> d -> a -> c*/ 1336 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d); 1337 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b); 1338 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c); 1339 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a); 1340 KUNIT_EXPECT_NULL(test, klist_next(&i)); 1341 1342 klist_iter_exit(&i); 1343 1344 } 1345 1346 /* 1347 * Verify that klist_del() delays the deletion of a node until there 1348 * are no other references to it 1349 */ 1350 static void klist_test_del_refcount_greater_than_zero(struct kunit *test) 1351 { 1352 struct klist_node a, b, c, d; 1353 struct klist mylist; 1354 struct klist_iter i; 1355 1356 node_count = 0; 1357 klist_init(&mylist, &check_node, &check_delete_node); 1358 1359 /* Add nodes a,b,c,d to the list*/ 1360 klist_add_tail(&a, &mylist); 1361 klist_add_tail(&b, &mylist); 1362 klist_add_tail(&c, &mylist); 1363 klist_add_tail(&d, &mylist); 1364 1365 klist_iter_init(&mylist, &i); 1366 1367 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a); 1368 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b); 1369 /* Advance the iterator to point to node c*/ 1370 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c); 1371 1372 /* Try to delete node c while there is a reference to it*/ 1373 klist_del(&c); 1374 1375 /* 1376 * Verify that node c is still attached to the list even after being 1377 * deleted. Since the iterator still points to c, the reference count is not 1378 * decreased to 0 1379 */ 1380 KUNIT_EXPECT_TRUE(test, klist_node_attached(&c)); 1381 1382 /* Check that node c has not been removed yet*/ 1383 KUNIT_EXPECT_EQ(test, node_count, 4); 1384 KUNIT_EXPECT_PTR_EQ(test, last_node, &d); 1385 1386 klist_iter_exit(&i); 1387 1388 /* 1389 * Since the iterator is no longer pointing to node c, node c is removed 1390 * from the list 1391 */ 1392 KUNIT_EXPECT_EQ(test, node_count, 3); 1393 KUNIT_EXPECT_PTR_EQ(test, last_node, &c); 1394 1395 } 1396 1397 /* 1398 * Verify that klist_del() deletes a node immediately when there are no 1399 * other references to it. 1400 */ 1401 static void klist_test_del_refcount_zero(struct kunit *test) 1402 { 1403 struct klist_node a, b, c, d; 1404 struct klist mylist; 1405 struct klist_iter i; 1406 1407 node_count = 0; 1408 klist_init(&mylist, &check_node, &check_delete_node); 1409 1410 /* Add nodes a,b,c,d to the list*/ 1411 klist_add_tail(&a, &mylist); 1412 klist_add_tail(&b, &mylist); 1413 klist_add_tail(&c, &mylist); 1414 klist_add_tail(&d, &mylist); 1415 /* Delete node c*/ 1416 klist_del(&c); 1417 1418 /* Check that node c is deleted from the list*/ 1419 KUNIT_EXPECT_EQ(test, node_count, 3); 1420 KUNIT_EXPECT_PTR_EQ(test, last_node, &c); 1421 1422 /* Should be [list] -> a -> b -> d*/ 1423 klist_iter_init(&mylist, &i); 1424 1425 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a); 1426 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b); 1427 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d); 1428 KUNIT_EXPECT_NULL(test, klist_next(&i)); 1429 1430 klist_iter_exit(&i); 1431 1432 } 1433 1434 static void klist_test_remove(struct kunit *test) 1435 { 1436 /* This test doesn't check correctness under concurrent access */ 1437 struct klist_node a, b, c, d; 1438 struct klist mylist; 1439 struct klist_iter i; 1440 1441 node_count = 0; 1442 klist_init(&mylist, &check_node, &check_delete_node); 1443 1444 /* Add nodes a,b,c,d to the list*/ 1445 klist_add_tail(&a, &mylist); 1446 klist_add_tail(&b, &mylist); 1447 klist_add_tail(&c, &mylist); 1448 klist_add_tail(&d, &mylist); 1449 /* Delete node c*/ 1450 klist_remove(&c); 1451 1452 /* Check the nodes in the list*/ 1453 KUNIT_EXPECT_EQ(test, node_count, 3); 1454 KUNIT_EXPECT_PTR_EQ(test, last_node, &c); 1455 1456 /* should be [list] -> a -> b -> d*/ 1457 klist_iter_init(&mylist, &i); 1458 1459 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a); 1460 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b); 1461 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d); 1462 KUNIT_EXPECT_NULL(test, klist_next(&i)); 1463 1464 klist_iter_exit(&i); 1465 1466 } 1467 1468 static void klist_test_node_attached(struct kunit *test) 1469 { 1470 struct klist_node a = {}; 1471 struct klist mylist; 1472 1473 klist_init(&mylist, NULL, NULL); 1474 1475 KUNIT_EXPECT_FALSE(test, klist_node_attached(&a)); 1476 klist_add_head(&a, &mylist); 1477 KUNIT_EXPECT_TRUE(test, klist_node_attached(&a)); 1478 klist_del(&a); 1479 KUNIT_EXPECT_FALSE(test, klist_node_attached(&a)); 1480 1481 } 1482 1483 static struct kunit_case klist_test_cases[] = { 1484 KUNIT_CASE(klist_test_add_tail), 1485 KUNIT_CASE(klist_test_add_head), 1486 KUNIT_CASE(klist_test_add_behind), 1487 KUNIT_CASE(klist_test_add_before), 1488 KUNIT_CASE(klist_test_del_refcount_greater_than_zero), 1489 KUNIT_CASE(klist_test_del_refcount_zero), 1490 KUNIT_CASE(klist_test_remove), 1491 KUNIT_CASE(klist_test_node_attached), 1492 {}, 1493 }; 1494 1495 static struct kunit_suite klist_test_module = { 1496 .name = "klist", 1497 .test_cases = klist_test_cases, 1498 }; 1499 1500 kunit_test_suites(&list_test_module, &hlist_test_module, &klist_test_module); 1501 1502 MODULE_LICENSE("GPL v2"); 1503