lib/list-test.c

   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");