Merge tag 'kvm-s390-next-5.19-2' of git://git.kernel.org/pub/scm/linux/kernel/git...
[platform/kernel/linux-starfive.git] / lib / list-test.c
1 // SPDX-License-Identifier: GPL-2.0
2 /*
3  * KUnit test for the Kernel Linked-list structures.
4  *
5  * Copyright (C) 2019, Google LLC.
6  * Author: David Gow <davidgow@google.com>
7  */
8 #include <kunit/test.h>
9
10 #include <linux/list.h>
11
12 struct list_test_struct {
13         int data;
14         struct list_head list;
15 };
16
17 static 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
46 static 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
60 static 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
74 static 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
90 static 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
106 static 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
125 static 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
147 static 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
164 static void list_test_list_del_init_careful(struct kunit *test)
165 {
166         /* NOTE: This test only checks the behaviour of this function in
167          * isolation. It does not verify memory model guarantees.
168          */
169         struct list_head a, b;
170         LIST_HEAD(list);
171
172         list_add_tail(&a, &list);
173         list_add_tail(&b, &list);
174
175         /* before: [list] -> a -> b */
176         list_del_init_careful(&a);
177         /* after: [list] -> b, a initialised */
178
179         KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
180         KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
181         KUNIT_EXPECT_TRUE(test, list_empty_careful(&a));
182 }
183
184 static void list_test_list_move(struct kunit *test)
185 {
186         struct list_head a, b;
187         LIST_HEAD(list1);
188         LIST_HEAD(list2);
189
190         list_add_tail(&a, &list1);
191         list_add_tail(&b, &list2);
192
193         /* before: [list1] -> a, [list2] -> b */
194         list_move(&a, &list2);
195         /* after: [list1] empty, [list2] -> a -> b */
196
197         KUNIT_EXPECT_TRUE(test, list_empty(&list1));
198
199         KUNIT_EXPECT_PTR_EQ(test, &a, list2.next);
200         KUNIT_EXPECT_PTR_EQ(test, &b, a.next);
201 }
202
203 static void list_test_list_move_tail(struct kunit *test)
204 {
205         struct list_head a, b;
206         LIST_HEAD(list1);
207         LIST_HEAD(list2);
208
209         list_add_tail(&a, &list1);
210         list_add_tail(&b, &list2);
211
212         /* before: [list1] -> a, [list2] -> b */
213         list_move_tail(&a, &list2);
214         /* after: [list1] empty, [list2] -> b -> a */
215
216         KUNIT_EXPECT_TRUE(test, list_empty(&list1));
217
218         KUNIT_EXPECT_PTR_EQ(test, &b, list2.next);
219         KUNIT_EXPECT_PTR_EQ(test, &a, b.next);
220 }
221
222 static void list_test_list_bulk_move_tail(struct kunit *test)
223 {
224         struct list_head a, b, c, d, x, y;
225         struct list_head *list1_values[] = { &x, &b, &c, &y };
226         struct list_head *list2_values[] = { &a, &d };
227         struct list_head *ptr;
228         LIST_HEAD(list1);
229         LIST_HEAD(list2);
230         int i = 0;
231
232         list_add_tail(&x, &list1);
233         list_add_tail(&y, &list1);
234
235         list_add_tail(&a, &list2);
236         list_add_tail(&b, &list2);
237         list_add_tail(&c, &list2);
238         list_add_tail(&d, &list2);
239
240         /* before: [list1] -> x -> y, [list2] -> a -> b -> c -> d */
241         list_bulk_move_tail(&y, &b, &c);
242         /* after: [list1] -> x -> b -> c -> y, [list2] -> a -> d */
243
244         list_for_each(ptr, &list1) {
245                 KUNIT_EXPECT_PTR_EQ(test, ptr, list1_values[i]);
246                 i++;
247         }
248         KUNIT_EXPECT_EQ(test, i, 4);
249         i = 0;
250         list_for_each(ptr, &list2) {
251                 KUNIT_EXPECT_PTR_EQ(test, ptr, list2_values[i]);
252                 i++;
253         }
254         KUNIT_EXPECT_EQ(test, i, 2);
255 }
256
257 static void list_test_list_is_head(struct kunit *test)
258 {
259         struct list_head a, b, c;
260
261         /* Two lists: [a] -> b, [c] */
262         INIT_LIST_HEAD(&a);
263         INIT_LIST_HEAD(&c);
264         list_add_tail(&b, &a);
265
266         KUNIT_EXPECT_TRUE_MSG(test, list_is_head(&a, &a),
267                 "Head element of same list");
268         KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &b),
269                 "Non-head element of same list");
270         KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &c),
271                 "Head element of different list");
272 }
273
274
275 static void list_test_list_is_first(struct kunit *test)
276 {
277         struct list_head a, b;
278         LIST_HEAD(list);
279
280         list_add_tail(&a, &list);
281         list_add_tail(&b, &list);
282
283         KUNIT_EXPECT_TRUE(test, list_is_first(&a, &list));
284         KUNIT_EXPECT_FALSE(test, list_is_first(&b, &list));
285 }
286
287 static void list_test_list_is_last(struct kunit *test)
288 {
289         struct list_head a, b;
290         LIST_HEAD(list);
291
292         list_add_tail(&a, &list);
293         list_add_tail(&b, &list);
294
295         KUNIT_EXPECT_FALSE(test, list_is_last(&a, &list));
296         KUNIT_EXPECT_TRUE(test, list_is_last(&b, &list));
297 }
298
299 static void list_test_list_empty(struct kunit *test)
300 {
301         struct list_head a;
302         LIST_HEAD(list1);
303         LIST_HEAD(list2);
304
305         list_add_tail(&a, &list1);
306
307         KUNIT_EXPECT_FALSE(test, list_empty(&list1));
308         KUNIT_EXPECT_TRUE(test, list_empty(&list2));
309 }
310
311 static void list_test_list_empty_careful(struct kunit *test)
312 {
313         /* This test doesn't check correctness under concurrent access */
314         struct list_head a;
315         LIST_HEAD(list1);
316         LIST_HEAD(list2);
317
318         list_add_tail(&a, &list1);
319
320         KUNIT_EXPECT_FALSE(test, list_empty_careful(&list1));
321         KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
322 }
323
324 static void list_test_list_rotate_left(struct kunit *test)
325 {
326         struct list_head a, b;
327         LIST_HEAD(list);
328
329         list_add_tail(&a, &list);
330         list_add_tail(&b, &list);
331
332         /* before: [list] -> a -> b */
333         list_rotate_left(&list);
334         /* after: [list] -> b -> a */
335
336         KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
337         KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
338         KUNIT_EXPECT_PTR_EQ(test, b.next, &a);
339 }
340
341 static void list_test_list_rotate_to_front(struct kunit *test)
342 {
343         struct list_head a, b, c, d;
344         struct list_head *list_values[] = { &c, &d, &a, &b };
345         struct list_head *ptr;
346         LIST_HEAD(list);
347         int i = 0;
348
349         list_add_tail(&a, &list);
350         list_add_tail(&b, &list);
351         list_add_tail(&c, &list);
352         list_add_tail(&d, &list);
353
354         /* before: [list] -> a -> b -> c -> d */
355         list_rotate_to_front(&c, &list);
356         /* after: [list] -> c -> d -> a -> b */
357
358         list_for_each(ptr, &list) {
359                 KUNIT_EXPECT_PTR_EQ(test, ptr, list_values[i]);
360                 i++;
361         }
362         KUNIT_EXPECT_EQ(test, i, 4);
363 }
364
365 static void list_test_list_is_singular(struct kunit *test)
366 {
367         struct list_head a, b;
368         LIST_HEAD(list);
369
370         /* [list] empty */
371         KUNIT_EXPECT_FALSE(test, list_is_singular(&list));
372
373         list_add_tail(&a, &list);
374
375         /* [list] -> a */
376         KUNIT_EXPECT_TRUE(test, list_is_singular(&list));
377
378         list_add_tail(&b, &list);
379
380         /* [list] -> a -> b */
381         KUNIT_EXPECT_FALSE(test, list_is_singular(&list));
382 }
383
384 static void list_test_list_cut_position(struct kunit *test)
385 {
386         struct list_head entries[3], *cur;
387         LIST_HEAD(list1);
388         LIST_HEAD(list2);
389         int i = 0;
390
391         list_add_tail(&entries[0], &list1);
392         list_add_tail(&entries[1], &list1);
393         list_add_tail(&entries[2], &list1);
394
395         /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */
396         list_cut_position(&list2, &list1, &entries[1]);
397         /* after: [list2] -> entries[0] -> entries[1], [list1] -> entries[2] */
398
399         list_for_each(cur, &list2) {
400                 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
401                 i++;
402         }
403
404         KUNIT_EXPECT_EQ(test, i, 2);
405
406         list_for_each(cur, &list1) {
407                 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
408                 i++;
409         }
410 }
411
412 static void list_test_list_cut_before(struct kunit *test)
413 {
414         struct list_head entries[3], *cur;
415         LIST_HEAD(list1);
416         LIST_HEAD(list2);
417         int i = 0;
418
419         list_add_tail(&entries[0], &list1);
420         list_add_tail(&entries[1], &list1);
421         list_add_tail(&entries[2], &list1);
422
423         /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */
424         list_cut_before(&list2, &list1, &entries[1]);
425         /* after: [list2] -> entries[0], [list1] -> entries[1] -> entries[2] */
426
427         list_for_each(cur, &list2) {
428                 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
429                 i++;
430         }
431
432         KUNIT_EXPECT_EQ(test, i, 1);
433
434         list_for_each(cur, &list1) {
435                 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
436                 i++;
437         }
438 }
439
440 static void list_test_list_splice(struct kunit *test)
441 {
442         struct list_head entries[5], *cur;
443         LIST_HEAD(list1);
444         LIST_HEAD(list2);
445         int i = 0;
446
447         list_add_tail(&entries[0], &list1);
448         list_add_tail(&entries[1], &list1);
449         list_add_tail(&entries[2], &list2);
450         list_add_tail(&entries[3], &list2);
451         list_add_tail(&entries[4], &list1);
452
453         /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
454         list_splice(&list2, &entries[1]);
455         /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */
456
457         list_for_each(cur, &list1) {
458                 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
459                 i++;
460         }
461
462         KUNIT_EXPECT_EQ(test, i, 5);
463 }
464
465 static void list_test_list_splice_tail(struct kunit *test)
466 {
467         struct list_head entries[5], *cur;
468         LIST_HEAD(list1);
469         LIST_HEAD(list2);
470         int i = 0;
471
472         list_add_tail(&entries[0], &list1);
473         list_add_tail(&entries[1], &list1);
474         list_add_tail(&entries[2], &list2);
475         list_add_tail(&entries[3], &list2);
476         list_add_tail(&entries[4], &list1);
477
478         /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
479         list_splice_tail(&list2, &entries[4]);
480         /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */
481
482         list_for_each(cur, &list1) {
483                 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
484                 i++;
485         }
486
487         KUNIT_EXPECT_EQ(test, i, 5);
488 }
489
490 static void list_test_list_splice_init(struct kunit *test)
491 {
492         struct list_head entries[5], *cur;
493         LIST_HEAD(list1);
494         LIST_HEAD(list2);
495         int i = 0;
496
497         list_add_tail(&entries[0], &list1);
498         list_add_tail(&entries[1], &list1);
499         list_add_tail(&entries[2], &list2);
500         list_add_tail(&entries[3], &list2);
501         list_add_tail(&entries[4], &list1);
502
503         /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
504         list_splice_init(&list2, &entries[1]);
505         /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */
506
507         list_for_each(cur, &list1) {
508                 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
509                 i++;
510         }
511
512         KUNIT_EXPECT_EQ(test, i, 5);
513
514         KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
515 }
516
517 static void list_test_list_splice_tail_init(struct kunit *test)
518 {
519         struct list_head entries[5], *cur;
520         LIST_HEAD(list1);
521         LIST_HEAD(list2);
522         int i = 0;
523
524         list_add_tail(&entries[0], &list1);
525         list_add_tail(&entries[1], &list1);
526         list_add_tail(&entries[2], &list2);
527         list_add_tail(&entries[3], &list2);
528         list_add_tail(&entries[4], &list1);
529
530         /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
531         list_splice_tail_init(&list2, &entries[4]);
532         /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */
533
534         list_for_each(cur, &list1) {
535                 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
536                 i++;
537         }
538
539         KUNIT_EXPECT_EQ(test, i, 5);
540
541         KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
542 }
543
544 static void list_test_list_entry(struct kunit *test)
545 {
546         struct list_test_struct test_struct;
547
548         KUNIT_EXPECT_PTR_EQ(test, &test_struct, list_entry(&(test_struct.list),
549                                 struct list_test_struct, list));
550 }
551
552 static void list_test_list_entry_is_head(struct kunit *test)
553 {
554         struct list_test_struct test_struct1, test_struct2, test_struct3;
555
556         INIT_LIST_HEAD(&test_struct1.list);
557         INIT_LIST_HEAD(&test_struct3.list);
558
559         list_add_tail(&test_struct2.list, &test_struct1.list);
560
561         KUNIT_EXPECT_TRUE_MSG(test,
562                 list_entry_is_head((&test_struct1), &test_struct1.list, list),
563                 "Head element of same list");
564         KUNIT_EXPECT_FALSE_MSG(test,
565                 list_entry_is_head((&test_struct2), &test_struct1.list, list),
566                 "Non-head element of same list");
567         KUNIT_EXPECT_FALSE_MSG(test,
568                 list_entry_is_head((&test_struct3), &test_struct1.list, list),
569                 "Head element of different list");
570 }
571
572 static void list_test_list_first_entry(struct kunit *test)
573 {
574         struct list_test_struct test_struct1, test_struct2;
575         LIST_HEAD(list);
576
577         list_add_tail(&test_struct1.list, &list);
578         list_add_tail(&test_struct2.list, &list);
579
580
581         KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_first_entry(&list,
582                                 struct list_test_struct, list));
583 }
584
585 static void list_test_list_last_entry(struct kunit *test)
586 {
587         struct list_test_struct test_struct1, test_struct2;
588         LIST_HEAD(list);
589
590         list_add_tail(&test_struct1.list, &list);
591         list_add_tail(&test_struct2.list, &list);
592
593
594         KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_last_entry(&list,
595                                 struct list_test_struct, list));
596 }
597
598 static void list_test_list_first_entry_or_null(struct kunit *test)
599 {
600         struct list_test_struct test_struct1, test_struct2;
601         LIST_HEAD(list);
602
603         KUNIT_EXPECT_FALSE(test, list_first_entry_or_null(&list,
604                                 struct list_test_struct, list));
605
606         list_add_tail(&test_struct1.list, &list);
607         list_add_tail(&test_struct2.list, &list);
608
609         KUNIT_EXPECT_PTR_EQ(test, &test_struct1,
610                         list_first_entry_or_null(&list,
611                                 struct list_test_struct, list));
612 }
613
614 static void list_test_list_next_entry(struct kunit *test)
615 {
616         struct list_test_struct test_struct1, test_struct2;
617         LIST_HEAD(list);
618
619         list_add_tail(&test_struct1.list, &list);
620         list_add_tail(&test_struct2.list, &list);
621
622
623         KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_next_entry(&test_struct1,
624                                 list));
625 }
626
627 static void list_test_list_prev_entry(struct kunit *test)
628 {
629         struct list_test_struct test_struct1, test_struct2;
630         LIST_HEAD(list);
631
632         list_add_tail(&test_struct1.list, &list);
633         list_add_tail(&test_struct2.list, &list);
634
635
636         KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_prev_entry(&test_struct2,
637                                 list));
638 }
639
640 static void list_test_list_for_each(struct kunit *test)
641 {
642         struct list_head entries[3], *cur;
643         LIST_HEAD(list);
644         int i = 0;
645
646         list_add_tail(&entries[0], &list);
647         list_add_tail(&entries[1], &list);
648         list_add_tail(&entries[2], &list);
649
650         list_for_each(cur, &list) {
651                 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
652                 i++;
653         }
654
655         KUNIT_EXPECT_EQ(test, i, 3);
656 }
657
658 static void list_test_list_for_each_prev(struct kunit *test)
659 {
660         struct list_head entries[3], *cur;
661         LIST_HEAD(list);
662         int i = 2;
663
664         list_add_tail(&entries[0], &list);
665         list_add_tail(&entries[1], &list);
666         list_add_tail(&entries[2], &list);
667
668         list_for_each_prev(cur, &list) {
669                 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
670                 i--;
671         }
672
673         KUNIT_EXPECT_EQ(test, i, -1);
674 }
675
676 static void list_test_list_for_each_safe(struct kunit *test)
677 {
678         struct list_head entries[3], *cur, *n;
679         LIST_HEAD(list);
680         int i = 0;
681
682
683         list_add_tail(&entries[0], &list);
684         list_add_tail(&entries[1], &list);
685         list_add_tail(&entries[2], &list);
686
687         list_for_each_safe(cur, n, &list) {
688                 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
689                 list_del(&entries[i]);
690                 i++;
691         }
692
693         KUNIT_EXPECT_EQ(test, i, 3);
694         KUNIT_EXPECT_TRUE(test, list_empty(&list));
695 }
696
697 static void list_test_list_for_each_prev_safe(struct kunit *test)
698 {
699         struct list_head entries[3], *cur, *n;
700         LIST_HEAD(list);
701         int i = 2;
702
703         list_add_tail(&entries[0], &list);
704         list_add_tail(&entries[1], &list);
705         list_add_tail(&entries[2], &list);
706
707         list_for_each_prev_safe(cur, n, &list) {
708                 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
709                 list_del(&entries[i]);
710                 i--;
711         }
712
713         KUNIT_EXPECT_EQ(test, i, -1);
714         KUNIT_EXPECT_TRUE(test, list_empty(&list));
715 }
716
717 static void list_test_list_for_each_entry(struct kunit *test)
718 {
719         struct list_test_struct entries[5], *cur;
720         LIST_HEAD(list);
721         int i = 0;
722
723         for (i = 0; i < 5; ++i) {
724                 entries[i].data = i;
725                 list_add_tail(&entries[i].list, &list);
726         }
727
728         i = 0;
729
730         list_for_each_entry(cur, &list, list) {
731                 KUNIT_EXPECT_EQ(test, cur->data, i);
732                 i++;
733         }
734
735         KUNIT_EXPECT_EQ(test, i, 5);
736 }
737
738 static void list_test_list_for_each_entry_reverse(struct kunit *test)
739 {
740         struct list_test_struct entries[5], *cur;
741         LIST_HEAD(list);
742         int i = 0;
743
744         for (i = 0; i < 5; ++i) {
745                 entries[i].data = i;
746                 list_add_tail(&entries[i].list, &list);
747         }
748
749         i = 4;
750
751         list_for_each_entry_reverse(cur, &list, list) {
752                 KUNIT_EXPECT_EQ(test, cur->data, i);
753                 i--;
754         }
755
756         KUNIT_EXPECT_EQ(test, i, -1);
757 }
758
759 static struct kunit_case list_test_cases[] = {
760         KUNIT_CASE(list_test_list_init),
761         KUNIT_CASE(list_test_list_add),
762         KUNIT_CASE(list_test_list_add_tail),
763         KUNIT_CASE(list_test_list_del),
764         KUNIT_CASE(list_test_list_replace),
765         KUNIT_CASE(list_test_list_replace_init),
766         KUNIT_CASE(list_test_list_swap),
767         KUNIT_CASE(list_test_list_del_init),
768         KUNIT_CASE(list_test_list_del_init_careful),
769         KUNIT_CASE(list_test_list_move),
770         KUNIT_CASE(list_test_list_move_tail),
771         KUNIT_CASE(list_test_list_bulk_move_tail),
772         KUNIT_CASE(list_test_list_is_head),
773         KUNIT_CASE(list_test_list_is_first),
774         KUNIT_CASE(list_test_list_is_last),
775         KUNIT_CASE(list_test_list_empty),
776         KUNIT_CASE(list_test_list_empty_careful),
777         KUNIT_CASE(list_test_list_rotate_left),
778         KUNIT_CASE(list_test_list_rotate_to_front),
779         KUNIT_CASE(list_test_list_is_singular),
780         KUNIT_CASE(list_test_list_cut_position),
781         KUNIT_CASE(list_test_list_cut_before),
782         KUNIT_CASE(list_test_list_splice),
783         KUNIT_CASE(list_test_list_splice_tail),
784         KUNIT_CASE(list_test_list_splice_init),
785         KUNIT_CASE(list_test_list_splice_tail_init),
786         KUNIT_CASE(list_test_list_entry),
787         KUNIT_CASE(list_test_list_entry_is_head),
788         KUNIT_CASE(list_test_list_first_entry),
789         KUNIT_CASE(list_test_list_last_entry),
790         KUNIT_CASE(list_test_list_first_entry_or_null),
791         KUNIT_CASE(list_test_list_next_entry),
792         KUNIT_CASE(list_test_list_prev_entry),
793         KUNIT_CASE(list_test_list_for_each),
794         KUNIT_CASE(list_test_list_for_each_prev),
795         KUNIT_CASE(list_test_list_for_each_safe),
796         KUNIT_CASE(list_test_list_for_each_prev_safe),
797         KUNIT_CASE(list_test_list_for_each_entry),
798         KUNIT_CASE(list_test_list_for_each_entry_reverse),
799         {},
800 };
801
802 static struct kunit_suite list_test_module = {
803         .name = "list-kunit-test",
804         .test_cases = list_test_cases,
805 };
806
807 struct hlist_test_struct {
808         int data;
809         struct hlist_node list;
810 };
811
812 static void hlist_test_init(struct kunit *test)
813 {
814         /* Test the different ways of initialising a list. */
815         struct hlist_head list1 = HLIST_HEAD_INIT;
816         struct hlist_head list2;
817         HLIST_HEAD(list3);
818         struct hlist_head *list4;
819         struct hlist_head *list5;
820
821         INIT_HLIST_HEAD(&list2);
822
823         list4 = kzalloc(sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL);
824         INIT_HLIST_HEAD(list4);
825
826         list5 = kmalloc(sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL);
827         memset(list5, 0xFF, sizeof(*list5));
828         INIT_HLIST_HEAD(list5);
829
830         KUNIT_EXPECT_TRUE(test, hlist_empty(&list1));
831         KUNIT_EXPECT_TRUE(test, hlist_empty(&list2));
832         KUNIT_EXPECT_TRUE(test, hlist_empty(&list3));
833         KUNIT_EXPECT_TRUE(test, hlist_empty(list4));
834         KUNIT_EXPECT_TRUE(test, hlist_empty(list5));
835
836         kfree(list4);
837         kfree(list5);
838 }
839
840 static void hlist_test_unhashed(struct kunit *test)
841 {
842         struct hlist_node a;
843         HLIST_HEAD(list);
844
845         INIT_HLIST_NODE(&a);
846
847         /* is unhashed by default */
848         KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a));
849
850         hlist_add_head(&a, &list);
851
852         /* is hashed once added to list */
853         KUNIT_EXPECT_FALSE(test, hlist_unhashed(&a));
854
855         hlist_del_init(&a);
856
857         /* is again unhashed after del_init */
858         KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a));
859 }
860
861 /* Doesn't test concurrency guarantees */
862 static void hlist_test_unhashed_lockless(struct kunit *test)
863 {
864         struct hlist_node a;
865         HLIST_HEAD(list);
866
867         INIT_HLIST_NODE(&a);
868
869         /* is unhashed by default */
870         KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a));
871
872         hlist_add_head(&a, &list);
873
874         /* is hashed once added to list */
875         KUNIT_EXPECT_FALSE(test, hlist_unhashed_lockless(&a));
876
877         hlist_del_init(&a);
878
879         /* is again unhashed after del_init */
880         KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a));
881 }
882
883 static void hlist_test_del(struct kunit *test)
884 {
885         struct hlist_node a, b;
886         HLIST_HEAD(list);
887
888         hlist_add_head(&a, &list);
889         hlist_add_behind(&b, &a);
890
891         /* before: [list] -> a -> b */
892         hlist_del(&a);
893
894         /* now: [list] -> b */
895         KUNIT_EXPECT_PTR_EQ(test, list.first, &b);
896         KUNIT_EXPECT_PTR_EQ(test, b.pprev, &list.first);
897 }
898
899 static void hlist_test_del_init(struct kunit *test)
900 {
901         struct hlist_node a, b;
902         HLIST_HEAD(list);
903
904         hlist_add_head(&a, &list);
905         hlist_add_behind(&b, &a);
906
907         /* before: [list] -> a -> b */
908         hlist_del_init(&a);
909
910         /* now: [list] -> b */
911         KUNIT_EXPECT_PTR_EQ(test, list.first, &b);
912         KUNIT_EXPECT_PTR_EQ(test, b.pprev, &list.first);
913
914         /* a is now initialised */
915         KUNIT_EXPECT_PTR_EQ(test, a.next, NULL);
916         KUNIT_EXPECT_PTR_EQ(test, a.pprev, NULL);
917 }
918
919 /* Tests all three hlist_add_* functions */
920 static void hlist_test_add(struct kunit *test)
921 {
922         struct hlist_node a, b, c, d;
923         HLIST_HEAD(list);
924
925         hlist_add_head(&a, &list);
926         hlist_add_head(&b, &list);
927         hlist_add_before(&c, &a);
928         hlist_add_behind(&d, &a);
929
930         /* should be [list] -> b -> c -> a -> d */
931         KUNIT_EXPECT_PTR_EQ(test, list.first, &b);
932
933         KUNIT_EXPECT_PTR_EQ(test, c.pprev, &(b.next));
934         KUNIT_EXPECT_PTR_EQ(test, b.next, &c);
935
936         KUNIT_EXPECT_PTR_EQ(test, a.pprev, &(c.next));
937         KUNIT_EXPECT_PTR_EQ(test, c.next, &a);
938
939         KUNIT_EXPECT_PTR_EQ(test, d.pprev, &(a.next));
940         KUNIT_EXPECT_PTR_EQ(test, a.next, &d);
941 }
942
943 /* Tests both hlist_fake() and hlist_add_fake() */
944 static void hlist_test_fake(struct kunit *test)
945 {
946         struct hlist_node a;
947
948         INIT_HLIST_NODE(&a);
949
950         /* not fake after init */
951         KUNIT_EXPECT_FALSE(test, hlist_fake(&a));
952
953         hlist_add_fake(&a);
954
955         /* is now fake */
956         KUNIT_EXPECT_TRUE(test, hlist_fake(&a));
957 }
958
959 static void hlist_test_is_singular_node(struct kunit *test)
960 {
961         struct hlist_node a, b;
962         HLIST_HEAD(list);
963
964         INIT_HLIST_NODE(&a);
965         KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list));
966
967         hlist_add_head(&a, &list);
968         KUNIT_EXPECT_TRUE(test, hlist_is_singular_node(&a, &list));
969
970         hlist_add_head(&b, &list);
971         KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list));
972         KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&b, &list));
973 }
974
975 static void hlist_test_empty(struct kunit *test)
976 {
977         struct hlist_node a;
978         HLIST_HEAD(list);
979
980         /* list starts off empty */
981         KUNIT_EXPECT_TRUE(test, hlist_empty(&list));
982
983         hlist_add_head(&a, &list);
984
985         /* list is no longer empty */
986         KUNIT_EXPECT_FALSE(test, hlist_empty(&list));
987 }
988
989 static void hlist_test_move_list(struct kunit *test)
990 {
991         struct hlist_node a;
992         HLIST_HEAD(list1);
993         HLIST_HEAD(list2);
994
995         hlist_add_head(&a, &list1);
996
997         KUNIT_EXPECT_FALSE(test, hlist_empty(&list1));
998         KUNIT_EXPECT_TRUE(test, hlist_empty(&list2));
999         hlist_move_list(&list1, &list2);
1000         KUNIT_EXPECT_TRUE(test, hlist_empty(&list1));
1001         KUNIT_EXPECT_FALSE(test, hlist_empty(&list2));
1002
1003 }
1004
1005 static void hlist_test_entry(struct kunit *test)
1006 {
1007         struct hlist_test_struct test_struct;
1008
1009         KUNIT_EXPECT_PTR_EQ(test, &test_struct,
1010                             hlist_entry(&(test_struct.list),
1011                                 struct hlist_test_struct, list));
1012 }
1013
1014 static void hlist_test_entry_safe(struct kunit *test)
1015 {
1016         struct hlist_test_struct test_struct;
1017
1018         KUNIT_EXPECT_PTR_EQ(test, &test_struct,
1019                             hlist_entry_safe(&(test_struct.list),
1020                                 struct hlist_test_struct, list));
1021
1022         KUNIT_EXPECT_PTR_EQ(test, NULL,
1023                             hlist_entry_safe((struct hlist_node *)NULL,
1024                                 struct hlist_test_struct, list));
1025 }
1026
1027 static void hlist_test_for_each(struct kunit *test)
1028 {
1029         struct hlist_node entries[3], *cur;
1030         HLIST_HEAD(list);
1031         int i = 0;
1032
1033         hlist_add_head(&entries[0], &list);
1034         hlist_add_behind(&entries[1], &entries[0]);
1035         hlist_add_behind(&entries[2], &entries[1]);
1036
1037         hlist_for_each(cur, &list) {
1038                 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
1039                 i++;
1040         }
1041
1042         KUNIT_EXPECT_EQ(test, i, 3);
1043 }
1044
1045
1046 static void hlist_test_for_each_safe(struct kunit *test)
1047 {
1048         struct hlist_node entries[3], *cur, *n;
1049         HLIST_HEAD(list);
1050         int i = 0;
1051
1052         hlist_add_head(&entries[0], &list);
1053         hlist_add_behind(&entries[1], &entries[0]);
1054         hlist_add_behind(&entries[2], &entries[1]);
1055
1056         hlist_for_each_safe(cur, n, &list) {
1057                 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
1058                 hlist_del(&entries[i]);
1059                 i++;
1060         }
1061
1062         KUNIT_EXPECT_EQ(test, i, 3);
1063         KUNIT_EXPECT_TRUE(test, hlist_empty(&list));
1064 }
1065
1066 static void hlist_test_for_each_entry(struct kunit *test)
1067 {
1068         struct hlist_test_struct entries[5], *cur;
1069         HLIST_HEAD(list);
1070         int i = 0;
1071
1072         entries[0].data = 0;
1073         hlist_add_head(&entries[0].list, &list);
1074         for (i = 1; i < 5; ++i) {
1075                 entries[i].data = i;
1076                 hlist_add_behind(&entries[i].list, &entries[i-1].list);
1077         }
1078
1079         i = 0;
1080
1081         hlist_for_each_entry(cur, &list, list) {
1082                 KUNIT_EXPECT_EQ(test, cur->data, i);
1083                 i++;
1084         }
1085
1086         KUNIT_EXPECT_EQ(test, i, 5);
1087 }
1088
1089 static void hlist_test_for_each_entry_continue(struct kunit *test)
1090 {
1091         struct hlist_test_struct entries[5], *cur;
1092         HLIST_HEAD(list);
1093         int i = 0;
1094
1095         entries[0].data = 0;
1096         hlist_add_head(&entries[0].list, &list);
1097         for (i = 1; i < 5; ++i) {
1098                 entries[i].data = i;
1099                 hlist_add_behind(&entries[i].list, &entries[i-1].list);
1100         }
1101
1102         /* We skip the first (zero-th) entry. */
1103         i = 1;
1104
1105         cur = &entries[0];
1106         hlist_for_each_entry_continue(cur, list) {
1107                 KUNIT_EXPECT_EQ(test, cur->data, i);
1108                 /* Stamp over the entry. */
1109                 cur->data = 42;
1110                 i++;
1111         }
1112
1113         KUNIT_EXPECT_EQ(test, i, 5);
1114         /* The first entry was not visited. */
1115         KUNIT_EXPECT_EQ(test, entries[0].data, 0);
1116         /* The second (and presumably others), were. */
1117         KUNIT_EXPECT_EQ(test, entries[1].data, 42);
1118 }
1119
1120 static void hlist_test_for_each_entry_from(struct kunit *test)
1121 {
1122         struct hlist_test_struct entries[5], *cur;
1123         HLIST_HEAD(list);
1124         int i = 0;
1125
1126         entries[0].data = 0;
1127         hlist_add_head(&entries[0].list, &list);
1128         for (i = 1; i < 5; ++i) {
1129                 entries[i].data = i;
1130                 hlist_add_behind(&entries[i].list, &entries[i-1].list);
1131         }
1132
1133         i = 0;
1134
1135         cur = &entries[0];
1136         hlist_for_each_entry_from(cur, list) {
1137                 KUNIT_EXPECT_EQ(test, cur->data, i);
1138                 /* Stamp over the entry. */
1139                 cur->data = 42;
1140                 i++;
1141         }
1142
1143         KUNIT_EXPECT_EQ(test, i, 5);
1144         /* The first entry was visited. */
1145         KUNIT_EXPECT_EQ(test, entries[0].data, 42);
1146 }
1147
1148 static void hlist_test_for_each_entry_safe(struct kunit *test)
1149 {
1150         struct hlist_test_struct entries[5], *cur;
1151         struct hlist_node *tmp_node;
1152         HLIST_HEAD(list);
1153         int i = 0;
1154
1155         entries[0].data = 0;
1156         hlist_add_head(&entries[0].list, &list);
1157         for (i = 1; i < 5; ++i) {
1158                 entries[i].data = i;
1159                 hlist_add_behind(&entries[i].list, &entries[i-1].list);
1160         }
1161
1162         i = 0;
1163
1164         hlist_for_each_entry_safe(cur, tmp_node, &list, list) {
1165                 KUNIT_EXPECT_EQ(test, cur->data, i);
1166                 hlist_del(&cur->list);
1167                 i++;
1168         }
1169
1170         KUNIT_EXPECT_EQ(test, i, 5);
1171         KUNIT_EXPECT_TRUE(test, hlist_empty(&list));
1172 }
1173
1174
1175 static struct kunit_case hlist_test_cases[] = {
1176         KUNIT_CASE(hlist_test_init),
1177         KUNIT_CASE(hlist_test_unhashed),
1178         KUNIT_CASE(hlist_test_unhashed_lockless),
1179         KUNIT_CASE(hlist_test_del),
1180         KUNIT_CASE(hlist_test_del_init),
1181         KUNIT_CASE(hlist_test_add),
1182         KUNIT_CASE(hlist_test_fake),
1183         KUNIT_CASE(hlist_test_is_singular_node),
1184         KUNIT_CASE(hlist_test_empty),
1185         KUNIT_CASE(hlist_test_move_list),
1186         KUNIT_CASE(hlist_test_entry),
1187         KUNIT_CASE(hlist_test_entry_safe),
1188         KUNIT_CASE(hlist_test_for_each),
1189         KUNIT_CASE(hlist_test_for_each_safe),
1190         KUNIT_CASE(hlist_test_for_each_entry),
1191         KUNIT_CASE(hlist_test_for_each_entry_continue),
1192         KUNIT_CASE(hlist_test_for_each_entry_from),
1193         KUNIT_CASE(hlist_test_for_each_entry_safe),
1194         {},
1195 };
1196
1197 static struct kunit_suite hlist_test_module = {
1198         .name = "hlist",
1199         .test_cases = hlist_test_cases,
1200 };
1201
1202 kunit_test_suites(&list_test_module, &hlist_test_module);
1203
1204 MODULE_LICENSE("GPL v2");