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