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