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