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 12 struct list_test_struct { 13 int data; 14 struct list_head list; 15 }; 16 17 static void list_test_list_init(struct kunit *test) 18 { 19 /* Test the different ways of initialising a list. */ 20 struct list_head list1 = LIST_HEAD_INIT(list1); 21 struct list_head list2; 22 LIST_HEAD(list3); 23 struct list_head *list4; 24 struct list_head *list5; 25 26 INIT_LIST_HEAD(&list2); 27 28 list4 = kzalloc(sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL); 29 INIT_LIST_HEAD(list4); 30 31 list5 = kmalloc(sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL); 32 memset(list5, 0xFF, sizeof(*list5)); 33 INIT_LIST_HEAD(list5); 34 35 /* list_empty_careful() checks both next and prev. */ 36 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list1)); 37 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); 38 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list3)); 39 KUNIT_EXPECT_TRUE(test, list_empty_careful(list4)); 40 KUNIT_EXPECT_TRUE(test, list_empty_careful(list5)); 41 42 kfree(list4); 43 kfree(list5); 44 } 45 46 static void list_test_list_add(struct kunit *test) 47 { 48 struct list_head a, b; 49 LIST_HEAD(list); 50 51 list_add(&a, &list); 52 list_add(&b, &list); 53 54 /* should be [list] -> b -> a */ 55 KUNIT_EXPECT_PTR_EQ(test, list.next, &b); 56 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); 57 KUNIT_EXPECT_PTR_EQ(test, b.next, &a); 58 } 59 60 static void list_test_list_add_tail(struct kunit *test) 61 { 62 struct list_head a, b; 63 LIST_HEAD(list); 64 65 list_add_tail(&a, &list); 66 list_add_tail(&b, &list); 67 68 /* should be [list] -> a -> b */ 69 KUNIT_EXPECT_PTR_EQ(test, list.next, &a); 70 KUNIT_EXPECT_PTR_EQ(test, a.prev, &list); 71 KUNIT_EXPECT_PTR_EQ(test, a.next, &b); 72 } 73 74 static void list_test_list_del(struct kunit *test) 75 { 76 struct list_head a, b; 77 LIST_HEAD(list); 78 79 list_add_tail(&a, &list); 80 list_add_tail(&b, &list); 81 82 /* before: [list] -> a -> b */ 83 list_del(&a); 84 85 /* now: [list] -> b */ 86 KUNIT_EXPECT_PTR_EQ(test, list.next, &b); 87 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); 88 } 89 90 static void list_test_list_replace(struct kunit *test) 91 { 92 struct list_head a_old, a_new, b; 93 LIST_HEAD(list); 94 95 list_add_tail(&a_old, &list); 96 list_add_tail(&b, &list); 97 98 /* before: [list] -> a_old -> b */ 99 list_replace(&a_old, &a_new); 100 101 /* now: [list] -> a_new -> b */ 102 KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new); 103 KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new); 104 } 105 106 static void list_test_list_replace_init(struct kunit *test) 107 { 108 struct list_head a_old, a_new, b; 109 LIST_HEAD(list); 110 111 list_add_tail(&a_old, &list); 112 list_add_tail(&b, &list); 113 114 /* before: [list] -> a_old -> b */ 115 list_replace_init(&a_old, &a_new); 116 117 /* now: [list] -> a_new -> b */ 118 KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new); 119 KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new); 120 121 /* check a_old is empty (initialized) */ 122 KUNIT_EXPECT_TRUE(test, list_empty_careful(&a_old)); 123 } 124 125 static void list_test_list_swap(struct kunit *test) 126 { 127 struct list_head a, b; 128 LIST_HEAD(list); 129 130 list_add_tail(&a, &list); 131 list_add_tail(&b, &list); 132 133 /* before: [list] -> a -> b */ 134 list_swap(&a, &b); 135 136 /* after: [list] -> b -> a */ 137 KUNIT_EXPECT_PTR_EQ(test, &b, list.next); 138 KUNIT_EXPECT_PTR_EQ(test, &a, list.prev); 139 140 KUNIT_EXPECT_PTR_EQ(test, &a, b.next); 141 KUNIT_EXPECT_PTR_EQ(test, &list, b.prev); 142 143 KUNIT_EXPECT_PTR_EQ(test, &list, a.next); 144 KUNIT_EXPECT_PTR_EQ(test, &b, a.prev); 145 } 146 147 static void list_test_list_del_init(struct kunit *test) 148 { 149 struct list_head a, b; 150 LIST_HEAD(list); 151 152 list_add_tail(&a, &list); 153 list_add_tail(&b, &list); 154 155 /* before: [list] -> a -> b */ 156 list_del_init(&a); 157 /* after: [list] -> b, a initialised */ 158 159 KUNIT_EXPECT_PTR_EQ(test, list.next, &b); 160 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); 161 KUNIT_EXPECT_TRUE(test, list_empty_careful(&a)); 162 } 163 164 static void list_test_list_del_init_careful(struct kunit *test) 165 { 166 /* NOTE: This test only checks the behaviour of this function in 167 * isolation. It does not verify memory model guarantees. 168 */ 169 struct list_head a, b; 170 LIST_HEAD(list); 171 172 list_add_tail(&a, &list); 173 list_add_tail(&b, &list); 174 175 /* before: [list] -> a -> b */ 176 list_del_init_careful(&a); 177 /* after: [list] -> b, a initialised */ 178 179 KUNIT_EXPECT_PTR_EQ(test, list.next, &b); 180 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); 181 KUNIT_EXPECT_TRUE(test, list_empty_careful(&a)); 182 } 183 184 static void list_test_list_move(struct kunit *test) 185 { 186 struct list_head a, b; 187 LIST_HEAD(list1); 188 LIST_HEAD(list2); 189 190 list_add_tail(&a, &list1); 191 list_add_tail(&b, &list2); 192 193 /* before: [list1] -> a, [list2] -> b */ 194 list_move(&a, &list2); 195 /* after: [list1] empty, [list2] -> a -> b */ 196 197 KUNIT_EXPECT_TRUE(test, list_empty(&list1)); 198 199 KUNIT_EXPECT_PTR_EQ(test, &a, list2.next); 200 KUNIT_EXPECT_PTR_EQ(test, &b, a.next); 201 } 202 203 static void list_test_list_move_tail(struct kunit *test) 204 { 205 struct list_head a, b; 206 LIST_HEAD(list1); 207 LIST_HEAD(list2); 208 209 list_add_tail(&a, &list1); 210 list_add_tail(&b, &list2); 211 212 /* before: [list1] -> a, [list2] -> b */ 213 list_move_tail(&a, &list2); 214 /* after: [list1] empty, [list2] -> b -> a */ 215 216 KUNIT_EXPECT_TRUE(test, list_empty(&list1)); 217 218 KUNIT_EXPECT_PTR_EQ(test, &b, list2.next); 219 KUNIT_EXPECT_PTR_EQ(test, &a, b.next); 220 } 221 222 static void list_test_list_bulk_move_tail(struct kunit *test) 223 { 224 struct list_head a, b, c, d, x, y; 225 struct list_head *list1_values[] = { &x, &b, &c, &y }; 226 struct list_head *list2_values[] = { &a, &d }; 227 struct list_head *ptr; 228 LIST_HEAD(list1); 229 LIST_HEAD(list2); 230 int i = 0; 231 232 list_add_tail(&x, &list1); 233 list_add_tail(&y, &list1); 234 235 list_add_tail(&a, &list2); 236 list_add_tail(&b, &list2); 237 list_add_tail(&c, &list2); 238 list_add_tail(&d, &list2); 239 240 /* before: [list1] -> x -> y, [list2] -> a -> b -> c -> d */ 241 list_bulk_move_tail(&y, &b, &c); 242 /* after: [list1] -> x -> b -> c -> y, [list2] -> a -> d */ 243 244 list_for_each(ptr, &list1) { 245 KUNIT_EXPECT_PTR_EQ(test, ptr, list1_values[i]); 246 i++; 247 } 248 KUNIT_EXPECT_EQ(test, i, 4); 249 i = 0; 250 list_for_each(ptr, &list2) { 251 KUNIT_EXPECT_PTR_EQ(test, ptr, list2_values[i]); 252 i++; 253 } 254 KUNIT_EXPECT_EQ(test, i, 2); 255 } 256 257 static void list_test_list_is_head(struct kunit *test) 258 { 259 struct list_head a, b, c; 260 261 /* Two lists: [a] -> b, [c] */ 262 INIT_LIST_HEAD(&a); 263 INIT_LIST_HEAD(&c); 264 list_add_tail(&b, &a); 265 266 KUNIT_EXPECT_TRUE_MSG(test, list_is_head(&a, &a), 267 "Head element of same list"); 268 KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &b), 269 "Non-head element of same list"); 270 KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &c), 271 "Head element of different list"); 272 } 273 274 275 static void list_test_list_is_first(struct kunit *test) 276 { 277 struct list_head a, b; 278 LIST_HEAD(list); 279 280 list_add_tail(&a, &list); 281 list_add_tail(&b, &list); 282 283 KUNIT_EXPECT_TRUE(test, list_is_first(&a, &list)); 284 KUNIT_EXPECT_FALSE(test, list_is_first(&b, &list)); 285 } 286 287 static void list_test_list_is_last(struct kunit *test) 288 { 289 struct list_head a, b; 290 LIST_HEAD(list); 291 292 list_add_tail(&a, &list); 293 list_add_tail(&b, &list); 294 295 KUNIT_EXPECT_FALSE(test, list_is_last(&a, &list)); 296 KUNIT_EXPECT_TRUE(test, list_is_last(&b, &list)); 297 } 298 299 static void list_test_list_empty(struct kunit *test) 300 { 301 struct list_head a; 302 LIST_HEAD(list1); 303 LIST_HEAD(list2); 304 305 list_add_tail(&a, &list1); 306 307 KUNIT_EXPECT_FALSE(test, list_empty(&list1)); 308 KUNIT_EXPECT_TRUE(test, list_empty(&list2)); 309 } 310 311 static void list_test_list_empty_careful(struct kunit *test) 312 { 313 /* This test doesn't check correctness under concurrent access */ 314 struct list_head a; 315 LIST_HEAD(list1); 316 LIST_HEAD(list2); 317 318 list_add_tail(&a, &list1); 319 320 KUNIT_EXPECT_FALSE(test, list_empty_careful(&list1)); 321 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); 322 } 323 324 static void list_test_list_rotate_left(struct kunit *test) 325 { 326 struct list_head a, b; 327 LIST_HEAD(list); 328 329 list_add_tail(&a, &list); 330 list_add_tail(&b, &list); 331 332 /* before: [list] -> a -> b */ 333 list_rotate_left(&list); 334 /* after: [list] -> b -> a */ 335 336 KUNIT_EXPECT_PTR_EQ(test, list.next, &b); 337 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); 338 KUNIT_EXPECT_PTR_EQ(test, b.next, &a); 339 } 340 341 static void list_test_list_rotate_to_front(struct kunit *test) 342 { 343 struct list_head a, b, c, d; 344 struct list_head *list_values[] = { &c, &d, &a, &b }; 345 struct list_head *ptr; 346 LIST_HEAD(list); 347 int i = 0; 348 349 list_add_tail(&a, &list); 350 list_add_tail(&b, &list); 351 list_add_tail(&c, &list); 352 list_add_tail(&d, &list); 353 354 /* before: [list] -> a -> b -> c -> d */ 355 list_rotate_to_front(&c, &list); 356 /* after: [list] -> c -> d -> a -> b */ 357 358 list_for_each(ptr, &list) { 359 KUNIT_EXPECT_PTR_EQ(test, ptr, list_values[i]); 360 i++; 361 } 362 KUNIT_EXPECT_EQ(test, i, 4); 363 } 364 365 static void list_test_list_is_singular(struct kunit *test) 366 { 367 struct list_head a, b; 368 LIST_HEAD(list); 369 370 /* [list] empty */ 371 KUNIT_EXPECT_FALSE(test, list_is_singular(&list)); 372 373 list_add_tail(&a, &list); 374 375 /* [list] -> a */ 376 KUNIT_EXPECT_TRUE(test, list_is_singular(&list)); 377 378 list_add_tail(&b, &list); 379 380 /* [list] -> a -> b */ 381 KUNIT_EXPECT_FALSE(test, list_is_singular(&list)); 382 } 383 384 static void list_test_list_cut_position(struct kunit *test) 385 { 386 struct list_head entries[3], *cur; 387 LIST_HEAD(list1); 388 LIST_HEAD(list2); 389 int i = 0; 390 391 list_add_tail(&entries[0], &list1); 392 list_add_tail(&entries[1], &list1); 393 list_add_tail(&entries[2], &list1); 394 395 /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */ 396 list_cut_position(&list2, &list1, &entries[1]); 397 /* after: [list2] -> entries[0] -> entries[1], [list1] -> entries[2] */ 398 399 list_for_each(cur, &list2) { 400 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 401 i++; 402 } 403 404 KUNIT_EXPECT_EQ(test, i, 2); 405 406 list_for_each(cur, &list1) { 407 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 408 i++; 409 } 410 } 411 412 static void list_test_list_cut_before(struct kunit *test) 413 { 414 struct list_head entries[3], *cur; 415 LIST_HEAD(list1); 416 LIST_HEAD(list2); 417 int i = 0; 418 419 list_add_tail(&entries[0], &list1); 420 list_add_tail(&entries[1], &list1); 421 list_add_tail(&entries[2], &list1); 422 423 /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */ 424 list_cut_before(&list2, &list1, &entries[1]); 425 /* after: [list2] -> entries[0], [list1] -> entries[1] -> entries[2] */ 426 427 list_for_each(cur, &list2) { 428 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 429 i++; 430 } 431 432 KUNIT_EXPECT_EQ(test, i, 1); 433 434 list_for_each(cur, &list1) { 435 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 436 i++; 437 } 438 } 439 440 static void list_test_list_splice(struct kunit *test) 441 { 442 struct list_head entries[5], *cur; 443 LIST_HEAD(list1); 444 LIST_HEAD(list2); 445 int i = 0; 446 447 list_add_tail(&entries[0], &list1); 448 list_add_tail(&entries[1], &list1); 449 list_add_tail(&entries[2], &list2); 450 list_add_tail(&entries[3], &list2); 451 list_add_tail(&entries[4], &list1); 452 453 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ 454 list_splice(&list2, &entries[1]); 455 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */ 456 457 list_for_each(cur, &list1) { 458 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 459 i++; 460 } 461 462 KUNIT_EXPECT_EQ(test, i, 5); 463 } 464 465 static void list_test_list_splice_tail(struct kunit *test) 466 { 467 struct list_head entries[5], *cur; 468 LIST_HEAD(list1); 469 LIST_HEAD(list2); 470 int i = 0; 471 472 list_add_tail(&entries[0], &list1); 473 list_add_tail(&entries[1], &list1); 474 list_add_tail(&entries[2], &list2); 475 list_add_tail(&entries[3], &list2); 476 list_add_tail(&entries[4], &list1); 477 478 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ 479 list_splice_tail(&list2, &entries[4]); 480 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */ 481 482 list_for_each(cur, &list1) { 483 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 484 i++; 485 } 486 487 KUNIT_EXPECT_EQ(test, i, 5); 488 } 489 490 static void list_test_list_splice_init(struct kunit *test) 491 { 492 struct list_head entries[5], *cur; 493 LIST_HEAD(list1); 494 LIST_HEAD(list2); 495 int i = 0; 496 497 list_add_tail(&entries[0], &list1); 498 list_add_tail(&entries[1], &list1); 499 list_add_tail(&entries[2], &list2); 500 list_add_tail(&entries[3], &list2); 501 list_add_tail(&entries[4], &list1); 502 503 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ 504 list_splice_init(&list2, &entries[1]); 505 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */ 506 507 list_for_each(cur, &list1) { 508 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 509 i++; 510 } 511 512 KUNIT_EXPECT_EQ(test, i, 5); 513 514 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); 515 } 516 517 static void list_test_list_splice_tail_init(struct kunit *test) 518 { 519 struct list_head entries[5], *cur; 520 LIST_HEAD(list1); 521 LIST_HEAD(list2); 522 int i = 0; 523 524 list_add_tail(&entries[0], &list1); 525 list_add_tail(&entries[1], &list1); 526 list_add_tail(&entries[2], &list2); 527 list_add_tail(&entries[3], &list2); 528 list_add_tail(&entries[4], &list1); 529 530 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ 531 list_splice_tail_init(&list2, &entries[4]); 532 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */ 533 534 list_for_each(cur, &list1) { 535 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 536 i++; 537 } 538 539 KUNIT_EXPECT_EQ(test, i, 5); 540 541 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); 542 } 543 544 static void list_test_list_entry(struct kunit *test) 545 { 546 struct list_test_struct test_struct; 547 548 KUNIT_EXPECT_PTR_EQ(test, &test_struct, list_entry(&(test_struct.list), 549 struct list_test_struct, list)); 550 } 551 552 static void list_test_list_entry_is_head(struct kunit *test) 553 { 554 struct list_test_struct test_struct1, test_struct2, test_struct3; 555 556 INIT_LIST_HEAD(&test_struct1.list); 557 INIT_LIST_HEAD(&test_struct3.list); 558 559 list_add_tail(&test_struct2.list, &test_struct1.list); 560 561 KUNIT_EXPECT_TRUE_MSG(test, 562 list_entry_is_head((&test_struct1), &test_struct1.list, list), 563 "Head element of same list"); 564 KUNIT_EXPECT_FALSE_MSG(test, 565 list_entry_is_head((&test_struct2), &test_struct1.list, list), 566 "Non-head element of same list"); 567 KUNIT_EXPECT_FALSE_MSG(test, 568 list_entry_is_head((&test_struct3), &test_struct1.list, list), 569 "Head element of different list"); 570 } 571 572 static void list_test_list_first_entry(struct kunit *test) 573 { 574 struct list_test_struct test_struct1, test_struct2; 575 LIST_HEAD(list); 576 577 list_add_tail(&test_struct1.list, &list); 578 list_add_tail(&test_struct2.list, &list); 579 580 581 KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_first_entry(&list, 582 struct list_test_struct, list)); 583 } 584 585 static void list_test_list_last_entry(struct kunit *test) 586 { 587 struct list_test_struct test_struct1, test_struct2; 588 LIST_HEAD(list); 589 590 list_add_tail(&test_struct1.list, &list); 591 list_add_tail(&test_struct2.list, &list); 592 593 594 KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_last_entry(&list, 595 struct list_test_struct, list)); 596 } 597 598 static void list_test_list_first_entry_or_null(struct kunit *test) 599 { 600 struct list_test_struct test_struct1, test_struct2; 601 LIST_HEAD(list); 602 603 KUNIT_EXPECT_FALSE(test, list_first_entry_or_null(&list, 604 struct list_test_struct, list)); 605 606 list_add_tail(&test_struct1.list, &list); 607 list_add_tail(&test_struct2.list, &list); 608 609 KUNIT_EXPECT_PTR_EQ(test, &test_struct1, 610 list_first_entry_or_null(&list, 611 struct list_test_struct, list)); 612 } 613 614 static void list_test_list_next_entry(struct kunit *test) 615 { 616 struct list_test_struct test_struct1, test_struct2; 617 LIST_HEAD(list); 618 619 list_add_tail(&test_struct1.list, &list); 620 list_add_tail(&test_struct2.list, &list); 621 622 623 KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_next_entry(&test_struct1, 624 list)); 625 } 626 627 static void list_test_list_prev_entry(struct kunit *test) 628 { 629 struct list_test_struct test_struct1, test_struct2; 630 LIST_HEAD(list); 631 632 list_add_tail(&test_struct1.list, &list); 633 list_add_tail(&test_struct2.list, &list); 634 635 636 KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_prev_entry(&test_struct2, 637 list)); 638 } 639 640 static void list_test_list_for_each(struct kunit *test) 641 { 642 struct list_head entries[3], *cur; 643 LIST_HEAD(list); 644 int i = 0; 645 646 list_add_tail(&entries[0], &list); 647 list_add_tail(&entries[1], &list); 648 list_add_tail(&entries[2], &list); 649 650 list_for_each(cur, &list) { 651 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 652 i++; 653 } 654 655 KUNIT_EXPECT_EQ(test, i, 3); 656 } 657 658 static void list_test_list_for_each_prev(struct kunit *test) 659 { 660 struct list_head entries[3], *cur; 661 LIST_HEAD(list); 662 int i = 2; 663 664 list_add_tail(&entries[0], &list); 665 list_add_tail(&entries[1], &list); 666 list_add_tail(&entries[2], &list); 667 668 list_for_each_prev(cur, &list) { 669 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 670 i--; 671 } 672 673 KUNIT_EXPECT_EQ(test, i, -1); 674 } 675 676 static void list_test_list_for_each_safe(struct kunit *test) 677 { 678 struct list_head entries[3], *cur, *n; 679 LIST_HEAD(list); 680 int i = 0; 681 682 683 list_add_tail(&entries[0], &list); 684 list_add_tail(&entries[1], &list); 685 list_add_tail(&entries[2], &list); 686 687 list_for_each_safe(cur, n, &list) { 688 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 689 list_del(&entries[i]); 690 i++; 691 } 692 693 KUNIT_EXPECT_EQ(test, i, 3); 694 KUNIT_EXPECT_TRUE(test, list_empty(&list)); 695 } 696 697 static void list_test_list_for_each_prev_safe(struct kunit *test) 698 { 699 struct list_head entries[3], *cur, *n; 700 LIST_HEAD(list); 701 int i = 2; 702 703 list_add_tail(&entries[0], &list); 704 list_add_tail(&entries[1], &list); 705 list_add_tail(&entries[2], &list); 706 707 list_for_each_prev_safe(cur, n, &list) { 708 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 709 list_del(&entries[i]); 710 i--; 711 } 712 713 KUNIT_EXPECT_EQ(test, i, -1); 714 KUNIT_EXPECT_TRUE(test, list_empty(&list)); 715 } 716 717 static void list_test_list_for_each_entry(struct kunit *test) 718 { 719 struct list_test_struct entries[5], *cur; 720 LIST_HEAD(list); 721 int i = 0; 722 723 for (i = 0; i < 5; ++i) { 724 entries[i].data = i; 725 list_add_tail(&entries[i].list, &list); 726 } 727 728 i = 0; 729 730 list_for_each_entry(cur, &list, list) { 731 KUNIT_EXPECT_EQ(test, cur->data, i); 732 i++; 733 } 734 735 KUNIT_EXPECT_EQ(test, i, 5); 736 } 737 738 static void list_test_list_for_each_entry_reverse(struct kunit *test) 739 { 740 struct list_test_struct entries[5], *cur; 741 LIST_HEAD(list); 742 int i = 0; 743 744 for (i = 0; i < 5; ++i) { 745 entries[i].data = i; 746 list_add_tail(&entries[i].list, &list); 747 } 748 749 i = 4; 750 751 list_for_each_entry_reverse(cur, &list, list) { 752 KUNIT_EXPECT_EQ(test, cur->data, i); 753 i--; 754 } 755 756 KUNIT_EXPECT_EQ(test, i, -1); 757 } 758 759 static struct kunit_case list_test_cases[] = { 760 KUNIT_CASE(list_test_list_init), 761 KUNIT_CASE(list_test_list_add), 762 KUNIT_CASE(list_test_list_add_tail), 763 KUNIT_CASE(list_test_list_del), 764 KUNIT_CASE(list_test_list_replace), 765 KUNIT_CASE(list_test_list_replace_init), 766 KUNIT_CASE(list_test_list_swap), 767 KUNIT_CASE(list_test_list_del_init), 768 KUNIT_CASE(list_test_list_del_init_careful), 769 KUNIT_CASE(list_test_list_move), 770 KUNIT_CASE(list_test_list_move_tail), 771 KUNIT_CASE(list_test_list_bulk_move_tail), 772 KUNIT_CASE(list_test_list_is_head), 773 KUNIT_CASE(list_test_list_is_first), 774 KUNIT_CASE(list_test_list_is_last), 775 KUNIT_CASE(list_test_list_empty), 776 KUNIT_CASE(list_test_list_empty_careful), 777 KUNIT_CASE(list_test_list_rotate_left), 778 KUNIT_CASE(list_test_list_rotate_to_front), 779 KUNIT_CASE(list_test_list_is_singular), 780 KUNIT_CASE(list_test_list_cut_position), 781 KUNIT_CASE(list_test_list_cut_before), 782 KUNIT_CASE(list_test_list_splice), 783 KUNIT_CASE(list_test_list_splice_tail), 784 KUNIT_CASE(list_test_list_splice_init), 785 KUNIT_CASE(list_test_list_splice_tail_init), 786 KUNIT_CASE(list_test_list_entry), 787 KUNIT_CASE(list_test_list_entry_is_head), 788 KUNIT_CASE(list_test_list_first_entry), 789 KUNIT_CASE(list_test_list_last_entry), 790 KUNIT_CASE(list_test_list_first_entry_or_null), 791 KUNIT_CASE(list_test_list_next_entry), 792 KUNIT_CASE(list_test_list_prev_entry), 793 KUNIT_CASE(list_test_list_for_each), 794 KUNIT_CASE(list_test_list_for_each_prev), 795 KUNIT_CASE(list_test_list_for_each_safe), 796 KUNIT_CASE(list_test_list_for_each_prev_safe), 797 KUNIT_CASE(list_test_list_for_each_entry), 798 KUNIT_CASE(list_test_list_for_each_entry_reverse), 799 {}, 800 }; 801 802 static struct kunit_suite list_test_module = { 803 .name = "list-kunit-test", 804 .test_cases = list_test_cases, 805 }; 806 807 struct hlist_test_struct { 808 int data; 809 struct hlist_node list; 810 }; 811 812 static void hlist_test_init(struct kunit *test) 813 { 814 /* Test the different ways of initialising a list. */ 815 struct hlist_head list1 = HLIST_HEAD_INIT; 816 struct hlist_head list2; 817 HLIST_HEAD(list3); 818 struct hlist_head *list4; 819 struct hlist_head *list5; 820 821 INIT_HLIST_HEAD(&list2); 822 823 list4 = kzalloc(sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL); 824 INIT_HLIST_HEAD(list4); 825 826 list5 = kmalloc(sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL); 827 memset(list5, 0xFF, sizeof(*list5)); 828 INIT_HLIST_HEAD(list5); 829 830 KUNIT_EXPECT_TRUE(test, hlist_empty(&list1)); 831 KUNIT_EXPECT_TRUE(test, hlist_empty(&list2)); 832 KUNIT_EXPECT_TRUE(test, hlist_empty(&list3)); 833 KUNIT_EXPECT_TRUE(test, hlist_empty(list4)); 834 KUNIT_EXPECT_TRUE(test, hlist_empty(list5)); 835 836 kfree(list4); 837 kfree(list5); 838 } 839 840 static void hlist_test_unhashed(struct kunit *test) 841 { 842 struct hlist_node a; 843 HLIST_HEAD(list); 844 845 INIT_HLIST_NODE(&a); 846 847 /* is unhashed by default */ 848 KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a)); 849 850 hlist_add_head(&a, &list); 851 852 /* is hashed once added to list */ 853 KUNIT_EXPECT_FALSE(test, hlist_unhashed(&a)); 854 855 hlist_del_init(&a); 856 857 /* is again unhashed after del_init */ 858 KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a)); 859 } 860 861 /* Doesn't test concurrency guarantees */ 862 static void hlist_test_unhashed_lockless(struct kunit *test) 863 { 864 struct hlist_node a; 865 HLIST_HEAD(list); 866 867 INIT_HLIST_NODE(&a); 868 869 /* is unhashed by default */ 870 KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a)); 871 872 hlist_add_head(&a, &list); 873 874 /* is hashed once added to list */ 875 KUNIT_EXPECT_FALSE(test, hlist_unhashed_lockless(&a)); 876 877 hlist_del_init(&a); 878 879 /* is again unhashed after del_init */ 880 KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a)); 881 } 882 883 static void hlist_test_del(struct kunit *test) 884 { 885 struct hlist_node a, b; 886 HLIST_HEAD(list); 887 888 hlist_add_head(&a, &list); 889 hlist_add_behind(&b, &a); 890 891 /* before: [list] -> a -> b */ 892 hlist_del(&a); 893 894 /* now: [list] -> b */ 895 KUNIT_EXPECT_PTR_EQ(test, list.first, &b); 896 KUNIT_EXPECT_PTR_EQ(test, b.pprev, &list.first); 897 } 898 899 static void hlist_test_del_init(struct kunit *test) 900 { 901 struct hlist_node a, b; 902 HLIST_HEAD(list); 903 904 hlist_add_head(&a, &list); 905 hlist_add_behind(&b, &a); 906 907 /* before: [list] -> a -> b */ 908 hlist_del_init(&a); 909 910 /* now: [list] -> b */ 911 KUNIT_EXPECT_PTR_EQ(test, list.first, &b); 912 KUNIT_EXPECT_PTR_EQ(test, b.pprev, &list.first); 913 914 /* a is now initialised */ 915 KUNIT_EXPECT_PTR_EQ(test, a.next, NULL); 916 KUNIT_EXPECT_PTR_EQ(test, a.pprev, NULL); 917 } 918 919 /* Tests all three hlist_add_* functions */ 920 static void hlist_test_add(struct kunit *test) 921 { 922 struct hlist_node a, b, c, d; 923 HLIST_HEAD(list); 924 925 hlist_add_head(&a, &list); 926 hlist_add_head(&b, &list); 927 hlist_add_before(&c, &a); 928 hlist_add_behind(&d, &a); 929 930 /* should be [list] -> b -> c -> a -> d */ 931 KUNIT_EXPECT_PTR_EQ(test, list.first, &b); 932 933 KUNIT_EXPECT_PTR_EQ(test, c.pprev, &(b.next)); 934 KUNIT_EXPECT_PTR_EQ(test, b.next, &c); 935 936 KUNIT_EXPECT_PTR_EQ(test, a.pprev, &(c.next)); 937 KUNIT_EXPECT_PTR_EQ(test, c.next, &a); 938 939 KUNIT_EXPECT_PTR_EQ(test, d.pprev, &(a.next)); 940 KUNIT_EXPECT_PTR_EQ(test, a.next, &d); 941 } 942 943 /* Tests both hlist_fake() and hlist_add_fake() */ 944 static void hlist_test_fake(struct kunit *test) 945 { 946 struct hlist_node a; 947 948 INIT_HLIST_NODE(&a); 949 950 /* not fake after init */ 951 KUNIT_EXPECT_FALSE(test, hlist_fake(&a)); 952 953 hlist_add_fake(&a); 954 955 /* is now fake */ 956 KUNIT_EXPECT_TRUE(test, hlist_fake(&a)); 957 } 958 959 static void hlist_test_is_singular_node(struct kunit *test) 960 { 961 struct hlist_node a, b; 962 HLIST_HEAD(list); 963 964 INIT_HLIST_NODE(&a); 965 KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list)); 966 967 hlist_add_head(&a, &list); 968 KUNIT_EXPECT_TRUE(test, hlist_is_singular_node(&a, &list)); 969 970 hlist_add_head(&b, &list); 971 KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list)); 972 KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&b, &list)); 973 } 974 975 static void hlist_test_empty(struct kunit *test) 976 { 977 struct hlist_node a; 978 HLIST_HEAD(list); 979 980 /* list starts off empty */ 981 KUNIT_EXPECT_TRUE(test, hlist_empty(&list)); 982 983 hlist_add_head(&a, &list); 984 985 /* list is no longer empty */ 986 KUNIT_EXPECT_FALSE(test, hlist_empty(&list)); 987 } 988 989 static void hlist_test_move_list(struct kunit *test) 990 { 991 struct hlist_node a; 992 HLIST_HEAD(list1); 993 HLIST_HEAD(list2); 994 995 hlist_add_head(&a, &list1); 996 997 KUNIT_EXPECT_FALSE(test, hlist_empty(&list1)); 998 KUNIT_EXPECT_TRUE(test, hlist_empty(&list2)); 999 hlist_move_list(&list1, &list2); 1000 KUNIT_EXPECT_TRUE(test, hlist_empty(&list1)); 1001 KUNIT_EXPECT_FALSE(test, hlist_empty(&list2)); 1002 1003 } 1004 1005 static void hlist_test_entry(struct kunit *test) 1006 { 1007 struct hlist_test_struct test_struct; 1008 1009 KUNIT_EXPECT_PTR_EQ(test, &test_struct, 1010 hlist_entry(&(test_struct.list), 1011 struct hlist_test_struct, list)); 1012 } 1013 1014 static void hlist_test_entry_safe(struct kunit *test) 1015 { 1016 struct hlist_test_struct test_struct; 1017 1018 KUNIT_EXPECT_PTR_EQ(test, &test_struct, 1019 hlist_entry_safe(&(test_struct.list), 1020 struct hlist_test_struct, list)); 1021 1022 KUNIT_EXPECT_PTR_EQ(test, NULL, 1023 hlist_entry_safe((struct hlist_node *)NULL, 1024 struct hlist_test_struct, list)); 1025 } 1026 1027 static void hlist_test_for_each(struct kunit *test) 1028 { 1029 struct hlist_node entries[3], *cur; 1030 HLIST_HEAD(list); 1031 int i = 0; 1032 1033 hlist_add_head(&entries[0], &list); 1034 hlist_add_behind(&entries[1], &entries[0]); 1035 hlist_add_behind(&entries[2], &entries[1]); 1036 1037 hlist_for_each(cur, &list) { 1038 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 1039 i++; 1040 } 1041 1042 KUNIT_EXPECT_EQ(test, i, 3); 1043 } 1044 1045 1046 static void hlist_test_for_each_safe(struct kunit *test) 1047 { 1048 struct hlist_node entries[3], *cur, *n; 1049 HLIST_HEAD(list); 1050 int i = 0; 1051 1052 hlist_add_head(&entries[0], &list); 1053 hlist_add_behind(&entries[1], &entries[0]); 1054 hlist_add_behind(&entries[2], &entries[1]); 1055 1056 hlist_for_each_safe(cur, n, &list) { 1057 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); 1058 hlist_del(&entries[i]); 1059 i++; 1060 } 1061 1062 KUNIT_EXPECT_EQ(test, i, 3); 1063 KUNIT_EXPECT_TRUE(test, hlist_empty(&list)); 1064 } 1065 1066 static void hlist_test_for_each_entry(struct kunit *test) 1067 { 1068 struct hlist_test_struct entries[5], *cur; 1069 HLIST_HEAD(list); 1070 int i = 0; 1071 1072 entries[0].data = 0; 1073 hlist_add_head(&entries[0].list, &list); 1074 for (i = 1; i < 5; ++i) { 1075 entries[i].data = i; 1076 hlist_add_behind(&entries[i].list, &entries[i-1].list); 1077 } 1078 1079 i = 0; 1080 1081 hlist_for_each_entry(cur, &list, list) { 1082 KUNIT_EXPECT_EQ(test, cur->data, i); 1083 i++; 1084 } 1085 1086 KUNIT_EXPECT_EQ(test, i, 5); 1087 } 1088 1089 static void hlist_test_for_each_entry_continue(struct kunit *test) 1090 { 1091 struct hlist_test_struct entries[5], *cur; 1092 HLIST_HEAD(list); 1093 int i = 0; 1094 1095 entries[0].data = 0; 1096 hlist_add_head(&entries[0].list, &list); 1097 for (i = 1; i < 5; ++i) { 1098 entries[i].data = i; 1099 hlist_add_behind(&entries[i].list, &entries[i-1].list); 1100 } 1101 1102 /* We skip the first (zero-th) entry. */ 1103 i = 1; 1104 1105 cur = &entries[0]; 1106 hlist_for_each_entry_continue(cur, list) { 1107 KUNIT_EXPECT_EQ(test, cur->data, i); 1108 /* Stamp over the entry. */ 1109 cur->data = 42; 1110 i++; 1111 } 1112 1113 KUNIT_EXPECT_EQ(test, i, 5); 1114 /* The first entry was not visited. */ 1115 KUNIT_EXPECT_EQ(test, entries[0].data, 0); 1116 /* The second (and presumably others), were. */ 1117 KUNIT_EXPECT_EQ(test, entries[1].data, 42); 1118 } 1119 1120 static void hlist_test_for_each_entry_from(struct kunit *test) 1121 { 1122 struct hlist_test_struct entries[5], *cur; 1123 HLIST_HEAD(list); 1124 int i = 0; 1125 1126 entries[0].data = 0; 1127 hlist_add_head(&entries[0].list, &list); 1128 for (i = 1; i < 5; ++i) { 1129 entries[i].data = i; 1130 hlist_add_behind(&entries[i].list, &entries[i-1].list); 1131 } 1132 1133 i = 0; 1134 1135 cur = &entries[0]; 1136 hlist_for_each_entry_from(cur, list) { 1137 KUNIT_EXPECT_EQ(test, cur->data, i); 1138 /* Stamp over the entry. */ 1139 cur->data = 42; 1140 i++; 1141 } 1142 1143 KUNIT_EXPECT_EQ(test, i, 5); 1144 /* The first entry was visited. */ 1145 KUNIT_EXPECT_EQ(test, entries[0].data, 42); 1146 } 1147 1148 static void hlist_test_for_each_entry_safe(struct kunit *test) 1149 { 1150 struct hlist_test_struct entries[5], *cur; 1151 struct hlist_node *tmp_node; 1152 HLIST_HEAD(list); 1153 int i = 0; 1154 1155 entries[0].data = 0; 1156 hlist_add_head(&entries[0].list, &list); 1157 for (i = 1; i < 5; ++i) { 1158 entries[i].data = i; 1159 hlist_add_behind(&entries[i].list, &entries[i-1].list); 1160 } 1161 1162 i = 0; 1163 1164 hlist_for_each_entry_safe(cur, tmp_node, &list, list) { 1165 KUNIT_EXPECT_EQ(test, cur->data, i); 1166 hlist_del(&cur->list); 1167 i++; 1168 } 1169 1170 KUNIT_EXPECT_EQ(test, i, 5); 1171 KUNIT_EXPECT_TRUE(test, hlist_empty(&list)); 1172 } 1173 1174 1175 static struct kunit_case hlist_test_cases[] = { 1176 KUNIT_CASE(hlist_test_init), 1177 KUNIT_CASE(hlist_test_unhashed), 1178 KUNIT_CASE(hlist_test_unhashed_lockless), 1179 KUNIT_CASE(hlist_test_del), 1180 KUNIT_CASE(hlist_test_del_init), 1181 KUNIT_CASE(hlist_test_add), 1182 KUNIT_CASE(hlist_test_fake), 1183 KUNIT_CASE(hlist_test_is_singular_node), 1184 KUNIT_CASE(hlist_test_empty), 1185 KUNIT_CASE(hlist_test_move_list), 1186 KUNIT_CASE(hlist_test_entry), 1187 KUNIT_CASE(hlist_test_entry_safe), 1188 KUNIT_CASE(hlist_test_for_each), 1189 KUNIT_CASE(hlist_test_for_each_safe), 1190 KUNIT_CASE(hlist_test_for_each_entry), 1191 KUNIT_CASE(hlist_test_for_each_entry_continue), 1192 KUNIT_CASE(hlist_test_for_each_entry_from), 1193 KUNIT_CASE(hlist_test_for_each_entry_safe), 1194 {}, 1195 }; 1196 1197 static struct kunit_suite hlist_test_module = { 1198 .name = "hlist", 1199 .test_cases = hlist_test_cases, 1200 }; 1201 1202 kunit_test_suites(&list_test_module, &hlist_test_module); 1203 1204 MODULE_LICENSE("GPL v2"); 1205