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
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_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
184static 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
203static 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
222static 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
257static 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
275static 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
287static 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
299static 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
311static 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
324static 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
341static 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
365static 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
384static 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
412static 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
440static 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
465static 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
490static 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
517static 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
544static 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
552static 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
572static 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
585static 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
598static 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
614static 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
627static 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
640static 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
658static 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
676static 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
697static 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
717static 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
738static 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
759static 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
802static struct kunit_suite list_test_module = {
803 .name = "list-kunit-test",
804 .test_cases = list_test_cases,
805};
806
807struct hlist_test_struct {
808 int data;
809 struct hlist_node list;
810};
811
812static 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
840static 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 */
862static 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
883static 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
899static 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 */
920static 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() */
944static 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
959static 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
975static 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
989static 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
1005static 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
1014static 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
1027static 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
1046static 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
1066static 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
1089static 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
1120static 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
1148static 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
1175static 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
1197static struct kunit_suite hlist_test_module = {
1198 .name = "hlist",
1199 .test_cases = hlist_test_cases,
1200};
1201
1202kunit_test_suites(&list_test_module, &hlist_test_module);
1203
1204MODULE_LICENSE("GPL v2");