1 // SPDX-License-Identifier: GPL-2.0
3 * KUnit test for the Kernel Linked-list structures.
5 * Copyright (C) 2019, Google LLC.
6 * Author: David Gow <davidgow@google.com>
8 #include <kunit/test.h>
10 #include <linux/list.h>
12 struct list_test_struct {
14 struct list_head list;
17 static void list_test_list_init(struct kunit *test)
19 /* Test the different ways of initialising a list. */
20 struct list_head list1 = LIST_HEAD_INIT(list1);
21 struct list_head list2;
23 struct list_head *list4;
24 struct list_head *list5;
26 INIT_LIST_HEAD(&list2);
28 list4 = kzalloc(sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL);
29 INIT_LIST_HEAD(list4);
31 list5 = kmalloc(sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL);
32 memset(list5, 0xFF, sizeof(*list5));
33 INIT_LIST_HEAD(list5);
35 /* list_empty_careful() checks both next and prev. */
36 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list1));
37 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
38 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list3));
39 KUNIT_EXPECT_TRUE(test, list_empty_careful(list4));
40 KUNIT_EXPECT_TRUE(test, list_empty_careful(list5));
46 static void list_test_list_add(struct kunit *test)
48 struct list_head a, b;
54 /* should be [list] -> b -> a */
55 KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
56 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
57 KUNIT_EXPECT_PTR_EQ(test, b.next, &a);
60 static void list_test_list_add_tail(struct kunit *test)
62 struct list_head a, b;
65 list_add_tail(&a, &list);
66 list_add_tail(&b, &list);
68 /* should be [list] -> a -> b */
69 KUNIT_EXPECT_PTR_EQ(test, list.next, &a);
70 KUNIT_EXPECT_PTR_EQ(test, a.prev, &list);
71 KUNIT_EXPECT_PTR_EQ(test, a.next, &b);
74 static void list_test_list_del(struct kunit *test)
76 struct list_head a, b;
79 list_add_tail(&a, &list);
80 list_add_tail(&b, &list);
82 /* before: [list] -> a -> b */
85 /* now: [list] -> b */
86 KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
87 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
90 static void list_test_list_replace(struct kunit *test)
92 struct list_head a_old, a_new, b;
95 list_add_tail(&a_old, &list);
96 list_add_tail(&b, &list);
98 /* before: [list] -> a_old -> b */
99 list_replace(&a_old, &a_new);
101 /* now: [list] -> a_new -> b */
102 KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new);
103 KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new);
106 static void list_test_list_replace_init(struct kunit *test)
108 struct list_head a_old, a_new, b;
111 list_add_tail(&a_old, &list);
112 list_add_tail(&b, &list);
114 /* before: [list] -> a_old -> b */
115 list_replace_init(&a_old, &a_new);
117 /* now: [list] -> a_new -> b */
118 KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new);
119 KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new);
121 /* check a_old is empty (initialized) */
122 KUNIT_EXPECT_TRUE(test, list_empty_careful(&a_old));
125 static void list_test_list_swap(struct kunit *test)
127 struct list_head a, b;
130 list_add_tail(&a, &list);
131 list_add_tail(&b, &list);
133 /* before: [list] -> a -> b */
136 /* after: [list] -> b -> a */
137 KUNIT_EXPECT_PTR_EQ(test, &b, list.next);
138 KUNIT_EXPECT_PTR_EQ(test, &a, list.prev);
140 KUNIT_EXPECT_PTR_EQ(test, &a, b.next);
141 KUNIT_EXPECT_PTR_EQ(test, &list, b.prev);
143 KUNIT_EXPECT_PTR_EQ(test, &list, a.next);
144 KUNIT_EXPECT_PTR_EQ(test, &b, a.prev);
147 static void list_test_list_del_init(struct kunit *test)
149 struct list_head a, b;
152 list_add_tail(&a, &list);
153 list_add_tail(&b, &list);
155 /* before: [list] -> a -> b */
157 /* after: [list] -> b, a initialised */
159 KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
160 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
161 KUNIT_EXPECT_TRUE(test, list_empty_careful(&a));
164 static void list_test_list_move(struct kunit *test)
166 struct list_head a, b;
170 list_add_tail(&a, &list1);
171 list_add_tail(&b, &list2);
173 /* before: [list1] -> a, [list2] -> b */
174 list_move(&a, &list2);
175 /* after: [list1] empty, [list2] -> a -> b */
177 KUNIT_EXPECT_TRUE(test, list_empty(&list1));
179 KUNIT_EXPECT_PTR_EQ(test, &a, list2.next);
180 KUNIT_EXPECT_PTR_EQ(test, &b, a.next);
183 static void list_test_list_move_tail(struct kunit *test)
185 struct list_head a, b;
189 list_add_tail(&a, &list1);
190 list_add_tail(&b, &list2);
192 /* before: [list1] -> a, [list2] -> b */
193 list_move_tail(&a, &list2);
194 /* after: [list1] empty, [list2] -> b -> a */
196 KUNIT_EXPECT_TRUE(test, list_empty(&list1));
198 KUNIT_EXPECT_PTR_EQ(test, &b, list2.next);
199 KUNIT_EXPECT_PTR_EQ(test, &a, b.next);
202 static void list_test_list_bulk_move_tail(struct kunit *test)
204 struct list_head a, b, c, d, x, y;
205 struct list_head *list1_values[] = { &x, &b, &c, &y };
206 struct list_head *list2_values[] = { &a, &d };
207 struct list_head *ptr;
212 list_add_tail(&x, &list1);
213 list_add_tail(&y, &list1);
215 list_add_tail(&a, &list2);
216 list_add_tail(&b, &list2);
217 list_add_tail(&c, &list2);
218 list_add_tail(&d, &list2);
220 /* before: [list1] -> x -> y, [list2] -> a -> b -> c -> d */
221 list_bulk_move_tail(&y, &b, &c);
222 /* after: [list1] -> x -> b -> c -> y, [list2] -> a -> d */
224 list_for_each(ptr, &list1) {
225 KUNIT_EXPECT_PTR_EQ(test, ptr, list1_values[i]);
228 KUNIT_EXPECT_EQ(test, i, 4);
230 list_for_each(ptr, &list2) {
231 KUNIT_EXPECT_PTR_EQ(test, ptr, list2_values[i]);
234 KUNIT_EXPECT_EQ(test, i, 2);
237 static void list_test_list_is_head(struct kunit *test)
239 struct list_head a, b, c;
241 /* Two lists: [a] -> b, [c] */
244 list_add_tail(&b, &a);
246 KUNIT_EXPECT_TRUE_MSG(test, list_is_head(&a, &a),
247 "Head element of same list");
248 KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &b),
249 "Non-head element of same list");
250 KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &c),
251 "Head element of different list");
255 static void list_test_list_is_first(struct kunit *test)
257 struct list_head a, b;
260 list_add_tail(&a, &list);
261 list_add_tail(&b, &list);
263 KUNIT_EXPECT_TRUE(test, list_is_first(&a, &list));
264 KUNIT_EXPECT_FALSE(test, list_is_first(&b, &list));
267 static void list_test_list_is_last(struct kunit *test)
269 struct list_head a, b;
272 list_add_tail(&a, &list);
273 list_add_tail(&b, &list);
275 KUNIT_EXPECT_FALSE(test, list_is_last(&a, &list));
276 KUNIT_EXPECT_TRUE(test, list_is_last(&b, &list));
279 static void list_test_list_empty(struct kunit *test)
285 list_add_tail(&a, &list1);
287 KUNIT_EXPECT_FALSE(test, list_empty(&list1));
288 KUNIT_EXPECT_TRUE(test, list_empty(&list2));
291 static void list_test_list_empty_careful(struct kunit *test)
293 /* This test doesn't check correctness under concurrent access */
298 list_add_tail(&a, &list1);
300 KUNIT_EXPECT_FALSE(test, list_empty_careful(&list1));
301 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
304 static void list_test_list_rotate_left(struct kunit *test)
306 struct list_head a, b;
309 list_add_tail(&a, &list);
310 list_add_tail(&b, &list);
312 /* before: [list] -> a -> b */
313 list_rotate_left(&list);
314 /* after: [list] -> b -> a */
316 KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
317 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
318 KUNIT_EXPECT_PTR_EQ(test, b.next, &a);
321 static void list_test_list_rotate_to_front(struct kunit *test)
323 struct list_head a, b, c, d;
324 struct list_head *list_values[] = { &c, &d, &a, &b };
325 struct list_head *ptr;
329 list_add_tail(&a, &list);
330 list_add_tail(&b, &list);
331 list_add_tail(&c, &list);
332 list_add_tail(&d, &list);
334 /* before: [list] -> a -> b -> c -> d */
335 list_rotate_to_front(&c, &list);
336 /* after: [list] -> c -> d -> a -> b */
338 list_for_each(ptr, &list) {
339 KUNIT_EXPECT_PTR_EQ(test, ptr, list_values[i]);
342 KUNIT_EXPECT_EQ(test, i, 4);
345 static void list_test_list_is_singular(struct kunit *test)
347 struct list_head a, b;
351 KUNIT_EXPECT_FALSE(test, list_is_singular(&list));
353 list_add_tail(&a, &list);
356 KUNIT_EXPECT_TRUE(test, list_is_singular(&list));
358 list_add_tail(&b, &list);
360 /* [list] -> a -> b */
361 KUNIT_EXPECT_FALSE(test, list_is_singular(&list));
364 static void list_test_list_cut_position(struct kunit *test)
366 struct list_head entries[3], *cur;
371 list_add_tail(&entries[0], &list1);
372 list_add_tail(&entries[1], &list1);
373 list_add_tail(&entries[2], &list1);
375 /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */
376 list_cut_position(&list2, &list1, &entries[1]);
377 /* after: [list2] -> entries[0] -> entries[1], [list1] -> entries[2] */
379 list_for_each(cur, &list2) {
380 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
384 KUNIT_EXPECT_EQ(test, i, 2);
386 list_for_each(cur, &list1) {
387 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
392 static void list_test_list_cut_before(struct kunit *test)
394 struct list_head entries[3], *cur;
399 list_add_tail(&entries[0], &list1);
400 list_add_tail(&entries[1], &list1);
401 list_add_tail(&entries[2], &list1);
403 /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */
404 list_cut_before(&list2, &list1, &entries[1]);
405 /* after: [list2] -> entries[0], [list1] -> entries[1] -> entries[2] */
407 list_for_each(cur, &list2) {
408 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
412 KUNIT_EXPECT_EQ(test, i, 1);
414 list_for_each(cur, &list1) {
415 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
420 static void list_test_list_splice(struct kunit *test)
422 struct list_head entries[5], *cur;
427 list_add_tail(&entries[0], &list1);
428 list_add_tail(&entries[1], &list1);
429 list_add_tail(&entries[2], &list2);
430 list_add_tail(&entries[3], &list2);
431 list_add_tail(&entries[4], &list1);
433 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
434 list_splice(&list2, &entries[1]);
435 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */
437 list_for_each(cur, &list1) {
438 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
442 KUNIT_EXPECT_EQ(test, i, 5);
445 static void list_test_list_splice_tail(struct kunit *test)
447 struct list_head entries[5], *cur;
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);
458 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
459 list_splice_tail(&list2, &entries[4]);
460 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */
462 list_for_each(cur, &list1) {
463 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
467 KUNIT_EXPECT_EQ(test, i, 5);
470 static void list_test_list_splice_init(struct kunit *test)
472 struct list_head entries[5], *cur;
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);
483 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
484 list_splice_init(&list2, &entries[1]);
485 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */
487 list_for_each(cur, &list1) {
488 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
492 KUNIT_EXPECT_EQ(test, i, 5);
494 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
497 static void list_test_list_splice_tail_init(struct kunit *test)
499 struct list_head entries[5], *cur;
504 list_add_tail(&entries[0], &list1);
505 list_add_tail(&entries[1], &list1);
506 list_add_tail(&entries[2], &list2);
507 list_add_tail(&entries[3], &list2);
508 list_add_tail(&entries[4], &list1);
510 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
511 list_splice_tail_init(&list2, &entries[4]);
512 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */
514 list_for_each(cur, &list1) {
515 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
519 KUNIT_EXPECT_EQ(test, i, 5);
521 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
524 static void list_test_list_entry(struct kunit *test)
526 struct list_test_struct test_struct;
528 KUNIT_EXPECT_PTR_EQ(test, &test_struct, list_entry(&(test_struct.list),
529 struct list_test_struct, list));
532 static void list_test_list_first_entry(struct kunit *test)
534 struct list_test_struct test_struct1, test_struct2;
537 list_add_tail(&test_struct1.list, &list);
538 list_add_tail(&test_struct2.list, &list);
541 KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_first_entry(&list,
542 struct list_test_struct, list));
545 static void list_test_list_last_entry(struct kunit *test)
547 struct list_test_struct test_struct1, test_struct2;
550 list_add_tail(&test_struct1.list, &list);
551 list_add_tail(&test_struct2.list, &list);
554 KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_last_entry(&list,
555 struct list_test_struct, list));
558 static void list_test_list_first_entry_or_null(struct kunit *test)
560 struct list_test_struct test_struct1, test_struct2;
563 KUNIT_EXPECT_FALSE(test, list_first_entry_or_null(&list,
564 struct list_test_struct, list));
566 list_add_tail(&test_struct1.list, &list);
567 list_add_tail(&test_struct2.list, &list);
569 KUNIT_EXPECT_PTR_EQ(test, &test_struct1,
570 list_first_entry_or_null(&list,
571 struct list_test_struct, list));
574 static void list_test_list_next_entry(struct kunit *test)
576 struct list_test_struct test_struct1, test_struct2;
579 list_add_tail(&test_struct1.list, &list);
580 list_add_tail(&test_struct2.list, &list);
583 KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_next_entry(&test_struct1,
587 static void list_test_list_prev_entry(struct kunit *test)
589 struct list_test_struct test_struct1, test_struct2;
592 list_add_tail(&test_struct1.list, &list);
593 list_add_tail(&test_struct2.list, &list);
596 KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_prev_entry(&test_struct2,
600 static void list_test_list_for_each(struct kunit *test)
602 struct list_head entries[3], *cur;
606 list_add_tail(&entries[0], &list);
607 list_add_tail(&entries[1], &list);
608 list_add_tail(&entries[2], &list);
610 list_for_each(cur, &list) {
611 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
615 KUNIT_EXPECT_EQ(test, i, 3);
618 static void list_test_list_for_each_prev(struct kunit *test)
620 struct list_head entries[3], *cur;
624 list_add_tail(&entries[0], &list);
625 list_add_tail(&entries[1], &list);
626 list_add_tail(&entries[2], &list);
628 list_for_each_prev(cur, &list) {
629 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
633 KUNIT_EXPECT_EQ(test, i, -1);
636 static void list_test_list_for_each_safe(struct kunit *test)
638 struct list_head entries[3], *cur, *n;
643 list_add_tail(&entries[0], &list);
644 list_add_tail(&entries[1], &list);
645 list_add_tail(&entries[2], &list);
647 list_for_each_safe(cur, n, &list) {
648 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
649 list_del(&entries[i]);
653 KUNIT_EXPECT_EQ(test, i, 3);
654 KUNIT_EXPECT_TRUE(test, list_empty(&list));
657 static void list_test_list_for_each_prev_safe(struct kunit *test)
659 struct list_head entries[3], *cur, *n;
663 list_add_tail(&entries[0], &list);
664 list_add_tail(&entries[1], &list);
665 list_add_tail(&entries[2], &list);
667 list_for_each_prev_safe(cur, n, &list) {
668 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
669 list_del(&entries[i]);
673 KUNIT_EXPECT_EQ(test, i, -1);
674 KUNIT_EXPECT_TRUE(test, list_empty(&list));
677 static void list_test_list_for_each_entry(struct kunit *test)
679 struct list_test_struct entries[5], *cur;
683 for (i = 0; i < 5; ++i) {
685 list_add_tail(&entries[i].list, &list);
690 list_for_each_entry(cur, &list, list) {
691 KUNIT_EXPECT_EQ(test, cur->data, i);
695 KUNIT_EXPECT_EQ(test, i, 5);
698 static void list_test_list_for_each_entry_reverse(struct kunit *test)
700 struct list_test_struct entries[5], *cur;
704 for (i = 0; i < 5; ++i) {
706 list_add_tail(&entries[i].list, &list);
711 list_for_each_entry_reverse(cur, &list, list) {
712 KUNIT_EXPECT_EQ(test, cur->data, i);
716 KUNIT_EXPECT_EQ(test, i, -1);
719 static struct kunit_case list_test_cases[] = {
720 KUNIT_CASE(list_test_list_init),
721 KUNIT_CASE(list_test_list_add),
722 KUNIT_CASE(list_test_list_add_tail),
723 KUNIT_CASE(list_test_list_del),
724 KUNIT_CASE(list_test_list_replace),
725 KUNIT_CASE(list_test_list_replace_init),
726 KUNIT_CASE(list_test_list_swap),
727 KUNIT_CASE(list_test_list_del_init),
728 KUNIT_CASE(list_test_list_move),
729 KUNIT_CASE(list_test_list_move_tail),
730 KUNIT_CASE(list_test_list_bulk_move_tail),
731 KUNIT_CASE(list_test_list_is_head),
732 KUNIT_CASE(list_test_list_is_first),
733 KUNIT_CASE(list_test_list_is_last),
734 KUNIT_CASE(list_test_list_empty),
735 KUNIT_CASE(list_test_list_empty_careful),
736 KUNIT_CASE(list_test_list_rotate_left),
737 KUNIT_CASE(list_test_list_rotate_to_front),
738 KUNIT_CASE(list_test_list_is_singular),
739 KUNIT_CASE(list_test_list_cut_position),
740 KUNIT_CASE(list_test_list_cut_before),
741 KUNIT_CASE(list_test_list_splice),
742 KUNIT_CASE(list_test_list_splice_tail),
743 KUNIT_CASE(list_test_list_splice_init),
744 KUNIT_CASE(list_test_list_splice_tail_init),
745 KUNIT_CASE(list_test_list_entry),
746 KUNIT_CASE(list_test_list_first_entry),
747 KUNIT_CASE(list_test_list_last_entry),
748 KUNIT_CASE(list_test_list_first_entry_or_null),
749 KUNIT_CASE(list_test_list_next_entry),
750 KUNIT_CASE(list_test_list_prev_entry),
751 KUNIT_CASE(list_test_list_for_each),
752 KUNIT_CASE(list_test_list_for_each_prev),
753 KUNIT_CASE(list_test_list_for_each_safe),
754 KUNIT_CASE(list_test_list_for_each_prev_safe),
755 KUNIT_CASE(list_test_list_for_each_entry),
756 KUNIT_CASE(list_test_list_for_each_entry_reverse),
760 static struct kunit_suite list_test_module = {
761 .name = "list-kunit-test",
762 .test_cases = list_test_cases,
765 kunit_test_suites(&list_test_module);
767 MODULE_LICENSE("GPL v2");