Loading...
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
12struct list_test_struct {
13 int data;
14 struct list_head list;
15};
16
17static void list_test_list_init(struct kunit *test)
18{
19 /* Test the different ways of initialising a list. */
20 struct list_head list1 = LIST_HEAD_INIT(list1);
21 struct list_head list2;
22 LIST_HEAD(list3);
23 struct list_head *list4;
24 struct list_head *list5;
25
26 INIT_LIST_HEAD(&list2);
27
28 list4 = kzalloc(sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL);
29 INIT_LIST_HEAD(list4);
30
31 list5 = kmalloc(sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL);
32 memset(list5, 0xFF, sizeof(*list5));
33 INIT_LIST_HEAD(list5);
34
35 /* list_empty_careful() checks both next and prev. */
36 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list1));
37 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
38 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list3));
39 KUNIT_EXPECT_TRUE(test, list_empty_careful(list4));
40 KUNIT_EXPECT_TRUE(test, list_empty_careful(list5));
41
42 kfree(list4);
43 kfree(list5);
44}
45
46static void list_test_list_add(struct kunit *test)
47{
48 struct list_head a, b;
49 LIST_HEAD(list);
50
51 list_add(&a, &list);
52 list_add(&b, &list);
53
54 /* should be [list] -> b -> a */
55 KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
56 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
57 KUNIT_EXPECT_PTR_EQ(test, b.next, &a);
58}
59
60static void list_test_list_add_tail(struct kunit *test)
61{
62 struct list_head a, b;
63 LIST_HEAD(list);
64
65 list_add_tail(&a, &list);
66 list_add_tail(&b, &list);
67
68 /* should be [list] -> a -> b */
69 KUNIT_EXPECT_PTR_EQ(test, list.next, &a);
70 KUNIT_EXPECT_PTR_EQ(test, a.prev, &list);
71 KUNIT_EXPECT_PTR_EQ(test, a.next, &b);
72}
73
74static void list_test_list_del(struct kunit *test)
75{
76 struct list_head a, b;
77 LIST_HEAD(list);
78
79 list_add_tail(&a, &list);
80 list_add_tail(&b, &list);
81
82 /* before: [list] -> a -> b */
83 list_del(&a);
84
85 /* now: [list] -> b */
86 KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
87 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
88}
89
90static void list_test_list_replace(struct kunit *test)
91{
92 struct list_head a_old, a_new, b;
93 LIST_HEAD(list);
94
95 list_add_tail(&a_old, &list);
96 list_add_tail(&b, &list);
97
98 /* before: [list] -> a_old -> b */
99 list_replace(&a_old, &a_new);
100
101 /* now: [list] -> a_new -> b */
102 KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new);
103 KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new);
104}
105
106static void list_test_list_replace_init(struct kunit *test)
107{
108 struct list_head a_old, a_new, b;
109 LIST_HEAD(list);
110
111 list_add_tail(&a_old, &list);
112 list_add_tail(&b, &list);
113
114 /* before: [list] -> a_old -> b */
115 list_replace_init(&a_old, &a_new);
116
117 /* now: [list] -> a_new -> b */
118 KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new);
119 KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new);
120
121 /* check a_old is empty (initialized) */
122 KUNIT_EXPECT_TRUE(test, list_empty_careful(&a_old));
123}
124
125static void list_test_list_swap(struct kunit *test)
126{
127 struct list_head a, b;
128 LIST_HEAD(list);
129
130 list_add_tail(&a, &list);
131 list_add_tail(&b, &list);
132
133 /* before: [list] -> a -> b */
134 list_swap(&a, &b);
135
136 /* after: [list] -> b -> a */
137 KUNIT_EXPECT_PTR_EQ(test, &b, list.next);
138 KUNIT_EXPECT_PTR_EQ(test, &a, list.prev);
139
140 KUNIT_EXPECT_PTR_EQ(test, &a, b.next);
141 KUNIT_EXPECT_PTR_EQ(test, &list, b.prev);
142
143 KUNIT_EXPECT_PTR_EQ(test, &list, a.next);
144 KUNIT_EXPECT_PTR_EQ(test, &b, a.prev);
145}
146
147static void list_test_list_del_init(struct kunit *test)
148{
149 struct list_head a, b;
150 LIST_HEAD(list);
151
152 list_add_tail(&a, &list);
153 list_add_tail(&b, &list);
154
155 /* before: [list] -> a -> b */
156 list_del_init(&a);
157 /* after: [list] -> b, a initialised */
158
159 KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
160 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
161 KUNIT_EXPECT_TRUE(test, list_empty_careful(&a));
162}
163
164static void list_test_list_move(struct kunit *test)
165{
166 struct list_head a, b;
167 LIST_HEAD(list1);
168 LIST_HEAD(list2);
169
170 list_add_tail(&a, &list1);
171 list_add_tail(&b, &list2);
172
173 /* before: [list1] -> a, [list2] -> b */
174 list_move(&a, &list2);
175 /* after: [list1] empty, [list2] -> a -> b */
176
177 KUNIT_EXPECT_TRUE(test, list_empty(&list1));
178
179 KUNIT_EXPECT_PTR_EQ(test, &a, list2.next);
180 KUNIT_EXPECT_PTR_EQ(test, &b, a.next);
181}
182
183static void list_test_list_move_tail(struct kunit *test)
184{
185 struct list_head a, b;
186 LIST_HEAD(list1);
187 LIST_HEAD(list2);
188
189 list_add_tail(&a, &list1);
190 list_add_tail(&b, &list2);
191
192 /* before: [list1] -> a, [list2] -> b */
193 list_move_tail(&a, &list2);
194 /* after: [list1] empty, [list2] -> b -> a */
195
196 KUNIT_EXPECT_TRUE(test, list_empty(&list1));
197
198 KUNIT_EXPECT_PTR_EQ(test, &b, list2.next);
199 KUNIT_EXPECT_PTR_EQ(test, &a, b.next);
200}
201
202static void list_test_list_bulk_move_tail(struct kunit *test)
203{
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;
208 LIST_HEAD(list1);
209 LIST_HEAD(list2);
210 int i = 0;
211
212 list_add_tail(&x, &list1);
213 list_add_tail(&y, &list1);
214
215 list_add_tail(&a, &list2);
216 list_add_tail(&b, &list2);
217 list_add_tail(&c, &list2);
218 list_add_tail(&d, &list2);
219
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 */
223
224 list_for_each(ptr, &list1) {
225 KUNIT_EXPECT_PTR_EQ(test, ptr, list1_values[i]);
226 i++;
227 }
228 KUNIT_EXPECT_EQ(test, i, 4);
229 i = 0;
230 list_for_each(ptr, &list2) {
231 KUNIT_EXPECT_PTR_EQ(test, ptr, list2_values[i]);
232 i++;
233 }
234 KUNIT_EXPECT_EQ(test, i, 2);
235}
236
237static void list_test_list_is_first(struct kunit *test)
238{
239 struct list_head a, b;
240 LIST_HEAD(list);
241
242 list_add_tail(&a, &list);
243 list_add_tail(&b, &list);
244
245 KUNIT_EXPECT_TRUE(test, list_is_first(&a, &list));
246 KUNIT_EXPECT_FALSE(test, list_is_first(&b, &list));
247}
248
249static void list_test_list_is_last(struct kunit *test)
250{
251 struct list_head a, b;
252 LIST_HEAD(list);
253
254 list_add_tail(&a, &list);
255 list_add_tail(&b, &list);
256
257 KUNIT_EXPECT_FALSE(test, list_is_last(&a, &list));
258 KUNIT_EXPECT_TRUE(test, list_is_last(&b, &list));
259}
260
261static void list_test_list_empty(struct kunit *test)
262{
263 struct list_head a;
264 LIST_HEAD(list1);
265 LIST_HEAD(list2);
266
267 list_add_tail(&a, &list1);
268
269 KUNIT_EXPECT_FALSE(test, list_empty(&list1));
270 KUNIT_EXPECT_TRUE(test, list_empty(&list2));
271}
272
273static void list_test_list_empty_careful(struct kunit *test)
274{
275 /* This test doesn't check correctness under concurrent access */
276 struct list_head a;
277 LIST_HEAD(list1);
278 LIST_HEAD(list2);
279
280 list_add_tail(&a, &list1);
281
282 KUNIT_EXPECT_FALSE(test, list_empty_careful(&list1));
283 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
284}
285
286static void list_test_list_rotate_left(struct kunit *test)
287{
288 struct list_head a, b;
289 LIST_HEAD(list);
290
291 list_add_tail(&a, &list);
292 list_add_tail(&b, &list);
293
294 /* before: [list] -> a -> b */
295 list_rotate_left(&list);
296 /* after: [list] -> b -> a */
297
298 KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
299 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
300 KUNIT_EXPECT_PTR_EQ(test, b.next, &a);
301}
302
303static void list_test_list_rotate_to_front(struct kunit *test)
304{
305 struct list_head a, b, c, d;
306 struct list_head *list_values[] = { &c, &d, &a, &b };
307 struct list_head *ptr;
308 LIST_HEAD(list);
309 int i = 0;
310
311 list_add_tail(&a, &list);
312 list_add_tail(&b, &list);
313 list_add_tail(&c, &list);
314 list_add_tail(&d, &list);
315
316 /* before: [list] -> a -> b -> c -> d */
317 list_rotate_to_front(&c, &list);
318 /* after: [list] -> c -> d -> a -> b */
319
320 list_for_each(ptr, &list) {
321 KUNIT_EXPECT_PTR_EQ(test, ptr, list_values[i]);
322 i++;
323 }
324 KUNIT_EXPECT_EQ(test, i, 4);
325}
326
327static void list_test_list_is_singular(struct kunit *test)
328{
329 struct list_head a, b;
330 LIST_HEAD(list);
331
332 /* [list] empty */
333 KUNIT_EXPECT_FALSE(test, list_is_singular(&list));
334
335 list_add_tail(&a, &list);
336
337 /* [list] -> a */
338 KUNIT_EXPECT_TRUE(test, list_is_singular(&list));
339
340 list_add_tail(&b, &list);
341
342 /* [list] -> a -> b */
343 KUNIT_EXPECT_FALSE(test, list_is_singular(&list));
344}
345
346static void list_test_list_cut_position(struct kunit *test)
347{
348 struct list_head entries[3], *cur;
349 LIST_HEAD(list1);
350 LIST_HEAD(list2);
351 int i = 0;
352
353 list_add_tail(&entries[0], &list1);
354 list_add_tail(&entries[1], &list1);
355 list_add_tail(&entries[2], &list1);
356
357 /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */
358 list_cut_position(&list2, &list1, &entries[1]);
359 /* after: [list2] -> entries[0] -> entries[1], [list1] -> entries[2] */
360
361 list_for_each(cur, &list2) {
362 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
363 i++;
364 }
365
366 KUNIT_EXPECT_EQ(test, i, 2);
367
368 list_for_each(cur, &list1) {
369 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
370 i++;
371 }
372}
373
374static void list_test_list_cut_before(struct kunit *test)
375{
376 struct list_head entries[3], *cur;
377 LIST_HEAD(list1);
378 LIST_HEAD(list2);
379 int i = 0;
380
381 list_add_tail(&entries[0], &list1);
382 list_add_tail(&entries[1], &list1);
383 list_add_tail(&entries[2], &list1);
384
385 /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */
386 list_cut_before(&list2, &list1, &entries[1]);
387 /* after: [list2] -> entries[0], [list1] -> entries[1] -> entries[2] */
388
389 list_for_each(cur, &list2) {
390 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
391 i++;
392 }
393
394 KUNIT_EXPECT_EQ(test, i, 1);
395
396 list_for_each(cur, &list1) {
397 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
398 i++;
399 }
400}
401
402static void list_test_list_splice(struct kunit *test)
403{
404 struct list_head entries[5], *cur;
405 LIST_HEAD(list1);
406 LIST_HEAD(list2);
407 int i = 0;
408
409 list_add_tail(&entries[0], &list1);
410 list_add_tail(&entries[1], &list1);
411 list_add_tail(&entries[2], &list2);
412 list_add_tail(&entries[3], &list2);
413 list_add_tail(&entries[4], &list1);
414
415 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
416 list_splice(&list2, &entries[1]);
417 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */
418
419 list_for_each(cur, &list1) {
420 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
421 i++;
422 }
423
424 KUNIT_EXPECT_EQ(test, i, 5);
425}
426
427static void list_test_list_splice_tail(struct kunit *test)
428{
429 struct list_head entries[5], *cur;
430 LIST_HEAD(list1);
431 LIST_HEAD(list2);
432 int i = 0;
433
434 list_add_tail(&entries[0], &list1);
435 list_add_tail(&entries[1], &list1);
436 list_add_tail(&entries[2], &list2);
437 list_add_tail(&entries[3], &list2);
438 list_add_tail(&entries[4], &list1);
439
440 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
441 list_splice_tail(&list2, &entries[4]);
442 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */
443
444 list_for_each(cur, &list1) {
445 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
446 i++;
447 }
448
449 KUNIT_EXPECT_EQ(test, i, 5);
450}
451
452static void list_test_list_splice_init(struct kunit *test)
453{
454 struct list_head entries[5], *cur;
455 LIST_HEAD(list1);
456 LIST_HEAD(list2);
457 int i = 0;
458
459 list_add_tail(&entries[0], &list1);
460 list_add_tail(&entries[1], &list1);
461 list_add_tail(&entries[2], &list2);
462 list_add_tail(&entries[3], &list2);
463 list_add_tail(&entries[4], &list1);
464
465 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
466 list_splice_init(&list2, &entries[1]);
467 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */
468
469 list_for_each(cur, &list1) {
470 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
471 i++;
472 }
473
474 KUNIT_EXPECT_EQ(test, i, 5);
475
476 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
477}
478
479static void list_test_list_splice_tail_init(struct kunit *test)
480{
481 struct list_head entries[5], *cur;
482 LIST_HEAD(list1);
483 LIST_HEAD(list2);
484 int i = 0;
485
486 list_add_tail(&entries[0], &list1);
487 list_add_tail(&entries[1], &list1);
488 list_add_tail(&entries[2], &list2);
489 list_add_tail(&entries[3], &list2);
490 list_add_tail(&entries[4], &list1);
491
492 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
493 list_splice_tail_init(&list2, &entries[4]);
494 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */
495
496 list_for_each(cur, &list1) {
497 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
498 i++;
499 }
500
501 KUNIT_EXPECT_EQ(test, i, 5);
502
503 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
504}
505
506static void list_test_list_entry(struct kunit *test)
507{
508 struct list_test_struct test_struct;
509
510 KUNIT_EXPECT_PTR_EQ(test, &test_struct, list_entry(&(test_struct.list),
511 struct list_test_struct, list));
512}
513
514static void list_test_list_first_entry(struct kunit *test)
515{
516 struct list_test_struct test_struct1, test_struct2;
517 LIST_HEAD(list);
518
519 list_add_tail(&test_struct1.list, &list);
520 list_add_tail(&test_struct2.list, &list);
521
522
523 KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_first_entry(&list,
524 struct list_test_struct, list));
525}
526
527static void list_test_list_last_entry(struct kunit *test)
528{
529 struct list_test_struct test_struct1, test_struct2;
530 LIST_HEAD(list);
531
532 list_add_tail(&test_struct1.list, &list);
533 list_add_tail(&test_struct2.list, &list);
534
535
536 KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_last_entry(&list,
537 struct list_test_struct, list));
538}
539
540static void list_test_list_first_entry_or_null(struct kunit *test)
541{
542 struct list_test_struct test_struct1, test_struct2;
543 LIST_HEAD(list);
544
545 KUNIT_EXPECT_FALSE(test, list_first_entry_or_null(&list,
546 struct list_test_struct, list));
547
548 list_add_tail(&test_struct1.list, &list);
549 list_add_tail(&test_struct2.list, &list);
550
551 KUNIT_EXPECT_PTR_EQ(test, &test_struct1,
552 list_first_entry_or_null(&list,
553 struct list_test_struct, list));
554}
555
556static void list_test_list_next_entry(struct kunit *test)
557{
558 struct list_test_struct test_struct1, test_struct2;
559 LIST_HEAD(list);
560
561 list_add_tail(&test_struct1.list, &list);
562 list_add_tail(&test_struct2.list, &list);
563
564
565 KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_next_entry(&test_struct1,
566 list));
567}
568
569static void list_test_list_prev_entry(struct kunit *test)
570{
571 struct list_test_struct test_struct1, test_struct2;
572 LIST_HEAD(list);
573
574 list_add_tail(&test_struct1.list, &list);
575 list_add_tail(&test_struct2.list, &list);
576
577
578 KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_prev_entry(&test_struct2,
579 list));
580}
581
582static void list_test_list_for_each(struct kunit *test)
583{
584 struct list_head entries[3], *cur;
585 LIST_HEAD(list);
586 int i = 0;
587
588 list_add_tail(&entries[0], &list);
589 list_add_tail(&entries[1], &list);
590 list_add_tail(&entries[2], &list);
591
592 list_for_each(cur, &list) {
593 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
594 i++;
595 }
596
597 KUNIT_EXPECT_EQ(test, i, 3);
598}
599
600static void list_test_list_for_each_prev(struct kunit *test)
601{
602 struct list_head entries[3], *cur;
603 LIST_HEAD(list);
604 int i = 2;
605
606 list_add_tail(&entries[0], &list);
607 list_add_tail(&entries[1], &list);
608 list_add_tail(&entries[2], &list);
609
610 list_for_each_prev(cur, &list) {
611 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
612 i--;
613 }
614
615 KUNIT_EXPECT_EQ(test, i, -1);
616}
617
618static void list_test_list_for_each_safe(struct kunit *test)
619{
620 struct list_head entries[3], *cur, *n;
621 LIST_HEAD(list);
622 int i = 0;
623
624
625 list_add_tail(&entries[0], &list);
626 list_add_tail(&entries[1], &list);
627 list_add_tail(&entries[2], &list);
628
629 list_for_each_safe(cur, n, &list) {
630 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
631 list_del(&entries[i]);
632 i++;
633 }
634
635 KUNIT_EXPECT_EQ(test, i, 3);
636 KUNIT_EXPECT_TRUE(test, list_empty(&list));
637}
638
639static void list_test_list_for_each_prev_safe(struct kunit *test)
640{
641 struct list_head entries[3], *cur, *n;
642 LIST_HEAD(list);
643 int i = 2;
644
645 list_add_tail(&entries[0], &list);
646 list_add_tail(&entries[1], &list);
647 list_add_tail(&entries[2], &list);
648
649 list_for_each_prev_safe(cur, n, &list) {
650 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
651 list_del(&entries[i]);
652 i--;
653 }
654
655 KUNIT_EXPECT_EQ(test, i, -1);
656 KUNIT_EXPECT_TRUE(test, list_empty(&list));
657}
658
659static void list_test_list_for_each_entry(struct kunit *test)
660{
661 struct list_test_struct entries[5], *cur;
662 LIST_HEAD(list);
663 int i = 0;
664
665 for (i = 0; i < 5; ++i) {
666 entries[i].data = i;
667 list_add_tail(&entries[i].list, &list);
668 }
669
670 i = 0;
671
672 list_for_each_entry(cur, &list, list) {
673 KUNIT_EXPECT_EQ(test, cur->data, i);
674 i++;
675 }
676
677 KUNIT_EXPECT_EQ(test, i, 5);
678}
679
680static void list_test_list_for_each_entry_reverse(struct kunit *test)
681{
682 struct list_test_struct entries[5], *cur;
683 LIST_HEAD(list);
684 int i = 0;
685
686 for (i = 0; i < 5; ++i) {
687 entries[i].data = i;
688 list_add_tail(&entries[i].list, &list);
689 }
690
691 i = 4;
692
693 list_for_each_entry_reverse(cur, &list, list) {
694 KUNIT_EXPECT_EQ(test, cur->data, i);
695 i--;
696 }
697
698 KUNIT_EXPECT_EQ(test, i, -1);
699}
700
701static struct kunit_case list_test_cases[] = {
702 KUNIT_CASE(list_test_list_init),
703 KUNIT_CASE(list_test_list_add),
704 KUNIT_CASE(list_test_list_add_tail),
705 KUNIT_CASE(list_test_list_del),
706 KUNIT_CASE(list_test_list_replace),
707 KUNIT_CASE(list_test_list_replace_init),
708 KUNIT_CASE(list_test_list_swap),
709 KUNIT_CASE(list_test_list_del_init),
710 KUNIT_CASE(list_test_list_move),
711 KUNIT_CASE(list_test_list_move_tail),
712 KUNIT_CASE(list_test_list_bulk_move_tail),
713 KUNIT_CASE(list_test_list_is_first),
714 KUNIT_CASE(list_test_list_is_last),
715 KUNIT_CASE(list_test_list_empty),
716 KUNIT_CASE(list_test_list_empty_careful),
717 KUNIT_CASE(list_test_list_rotate_left),
718 KUNIT_CASE(list_test_list_rotate_to_front),
719 KUNIT_CASE(list_test_list_is_singular),
720 KUNIT_CASE(list_test_list_cut_position),
721 KUNIT_CASE(list_test_list_cut_before),
722 KUNIT_CASE(list_test_list_splice),
723 KUNIT_CASE(list_test_list_splice_tail),
724 KUNIT_CASE(list_test_list_splice_init),
725 KUNIT_CASE(list_test_list_splice_tail_init),
726 KUNIT_CASE(list_test_list_entry),
727 KUNIT_CASE(list_test_list_first_entry),
728 KUNIT_CASE(list_test_list_last_entry),
729 KUNIT_CASE(list_test_list_first_entry_or_null),
730 KUNIT_CASE(list_test_list_next_entry),
731 KUNIT_CASE(list_test_list_prev_entry),
732 KUNIT_CASE(list_test_list_for_each),
733 KUNIT_CASE(list_test_list_for_each_prev),
734 KUNIT_CASE(list_test_list_for_each_safe),
735 KUNIT_CASE(list_test_list_for_each_prev_safe),
736 KUNIT_CASE(list_test_list_for_each_entry),
737 KUNIT_CASE(list_test_list_for_each_entry_reverse),
738 {},
739};
740
741static struct kunit_suite list_test_module = {
742 .name = "list-kunit-test",
743 .test_cases = list_test_cases,
744};
745
746kunit_test_suites(&list_test_module);
747
748MODULE_LICENSE("GPL v2");
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
13struct list_test_struct {
14 int data;
15 struct list_head list;
16};
17
18static 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
47static 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
61static 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
75static 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
91static 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
109static 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
130static 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
152static 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
169static 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
189static 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
208static 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
227static 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
262static 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
280static 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
292static 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
304static 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
316static 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
329static 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
346static 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
370static 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
389static 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
419static 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
449static 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
474static 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
499static 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
526static 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
553static 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
561static 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
581static 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
594static 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
607static 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
623static 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
636static 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
649static 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
667static 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
685static 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
706static 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
726static 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
747static 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
768static 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
811static struct kunit_suite list_test_module = {
812 .name = "list-kunit-test",
813 .test_cases = list_test_cases,
814};
815
816struct hlist_test_struct {
817 int data;
818 struct hlist_node list;
819};
820
821static 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
849static 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 */
871static 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
892static 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
908static 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 */
929static 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() */
953static 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
968static 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
984static 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
998static 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
1014static 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
1023static 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
1036static 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
1055static 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
1075static 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
1098static 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
1129static 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
1157static 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
1184static 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
1206static struct kunit_suite hlist_test_module = {
1207 .name = "hlist",
1208 .test_cases = hlist_test_cases,
1209};
1210
1211
1212static int node_count;
1213static struct klist_node *last_node;
1214
1215static void check_node(struct klist_node *node_ptr)
1216{
1217 node_count++;
1218 last_node = node_ptr;
1219}
1220
1221static void check_delete_node(struct klist_node *node_ptr)
1222{
1223 node_count--;
1224 last_node = node_ptr;
1225}
1226
1227static 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
1255static 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
1283static 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
1316static 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 */
1352static 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 */
1403static 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
1436static 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
1470static 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
1485static 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
1497static struct kunit_suite klist_test_module = {
1498 .name = "klist",
1499 .test_cases = klist_test_cases,
1500};
1501
1502kunit_test_suites(&list_test_module, &hlist_test_module, &klist_test_module);
1503
1504MODULE_DESCRIPTION("KUnit test for the Kernel Linked-list structures");
1505MODULE_LICENSE("GPL v2");