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