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