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