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}
106
107static void list_test_list_replace_init(struct kunit *test)
108{
109 struct list_head a_old, a_new, b;
110 LIST_HEAD(list);
111
112 list_add_tail(&a_old, &list);
113 list_add_tail(&b, &list);
114
115 /* before: [list] -> a_old -> b */
116 list_replace_init(&a_old, &a_new);
117
118 /* now: [list] -> a_new -> b */
119 KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new);
120 KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new);
121
122 /* check a_old is empty (initialized) */
123 KUNIT_EXPECT_TRUE(test, list_empty_careful(&a_old));
124}
125
126static void list_test_list_swap(struct kunit *test)
127{
128 struct list_head a, b;
129 LIST_HEAD(list);
130
131 list_add_tail(&a, &list);
132 list_add_tail(&b, &list);
133
134 /* before: [list] -> a -> b */
135 list_swap(&a, &b);
136
137 /* after: [list] -> b -> a */
138 KUNIT_EXPECT_PTR_EQ(test, &b, list.next);
139 KUNIT_EXPECT_PTR_EQ(test, &a, list.prev);
140
141 KUNIT_EXPECT_PTR_EQ(test, &a, b.next);
142 KUNIT_EXPECT_PTR_EQ(test, &list, b.prev);
143
144 KUNIT_EXPECT_PTR_EQ(test, &list, a.next);
145 KUNIT_EXPECT_PTR_EQ(test, &b, a.prev);
146}
147
148static void list_test_list_del_init(struct kunit *test)
149{
150 struct list_head a, b;
151 LIST_HEAD(list);
152
153 list_add_tail(&a, &list);
154 list_add_tail(&b, &list);
155
156 /* before: [list] -> a -> b */
157 list_del_init(&a);
158 /* after: [list] -> b, a initialised */
159
160 KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
161 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
162 KUNIT_EXPECT_TRUE(test, list_empty_careful(&a));
163}
164
165static void list_test_list_del_init_careful(struct kunit *test)
166{
167 /* NOTE: This test only checks the behaviour of this function in
168 * isolation. It does not verify memory model guarantees.
169 */
170 struct list_head a, b;
171 LIST_HEAD(list);
172
173 list_add_tail(&a, &list);
174 list_add_tail(&b, &list);
175
176 /* before: [list] -> a -> b */
177 list_del_init_careful(&a);
178 /* after: [list] -> b, a initialised */
179
180 KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
181 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
182 KUNIT_EXPECT_TRUE(test, list_empty_careful(&a));
183}
184
185static void list_test_list_move(struct kunit *test)
186{
187 struct list_head a, b;
188 LIST_HEAD(list1);
189 LIST_HEAD(list2);
190
191 list_add_tail(&a, &list1);
192 list_add_tail(&b, &list2);
193
194 /* before: [list1] -> a, [list2] -> b */
195 list_move(&a, &list2);
196 /* after: [list1] empty, [list2] -> a -> b */
197
198 KUNIT_EXPECT_TRUE(test, list_empty(&list1));
199
200 KUNIT_EXPECT_PTR_EQ(test, &a, list2.next);
201 KUNIT_EXPECT_PTR_EQ(test, &b, a.next);
202}
203
204static void list_test_list_move_tail(struct kunit *test)
205{
206 struct list_head a, b;
207 LIST_HEAD(list1);
208 LIST_HEAD(list2);
209
210 list_add_tail(&a, &list1);
211 list_add_tail(&b, &list2);
212
213 /* before: [list1] -> a, [list2] -> b */
214 list_move_tail(&a, &list2);
215 /* after: [list1] empty, [list2] -> b -> a */
216
217 KUNIT_EXPECT_TRUE(test, list_empty(&list1));
218
219 KUNIT_EXPECT_PTR_EQ(test, &b, list2.next);
220 KUNIT_EXPECT_PTR_EQ(test, &a, b.next);
221}
222
223static void list_test_list_bulk_move_tail(struct kunit *test)
224{
225 struct list_head a, b, c, d, x, y;
226 struct list_head *list1_values[] = { &x, &b, &c, &y };
227 struct list_head *list2_values[] = { &a, &d };
228 struct list_head *ptr;
229 LIST_HEAD(list1);
230 LIST_HEAD(list2);
231 int i = 0;
232
233 list_add_tail(&x, &list1);
234 list_add_tail(&y, &list1);
235
236 list_add_tail(&a, &list2);
237 list_add_tail(&b, &list2);
238 list_add_tail(&c, &list2);
239 list_add_tail(&d, &list2);
240
241 /* before: [list1] -> x -> y, [list2] -> a -> b -> c -> d */
242 list_bulk_move_tail(&y, &b, &c);
243 /* after: [list1] -> x -> b -> c -> y, [list2] -> a -> d */
244
245 list_for_each(ptr, &list1) {
246 KUNIT_EXPECT_PTR_EQ(test, ptr, list1_values[i]);
247 i++;
248 }
249 KUNIT_EXPECT_EQ(test, i, 4);
250 i = 0;
251 list_for_each(ptr, &list2) {
252 KUNIT_EXPECT_PTR_EQ(test, ptr, list2_values[i]);
253 i++;
254 }
255 KUNIT_EXPECT_EQ(test, i, 2);
256}
257
258static void list_test_list_is_head(struct kunit *test)
259{
260 struct list_head a, b, c;
261
262 /* Two lists: [a] -> b, [c] */
263 INIT_LIST_HEAD(&a);
264 INIT_LIST_HEAD(&c);
265 list_add_tail(&b, &a);
266
267 KUNIT_EXPECT_TRUE_MSG(test, list_is_head(&a, &a),
268 "Head element of same list");
269 KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &b),
270 "Non-head element of same list");
271 KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &c),
272 "Head element of different list");
273}
274
275
276static void list_test_list_is_first(struct kunit *test)
277{
278 struct list_head a, b;
279 LIST_HEAD(list);
280
281 list_add_tail(&a, &list);
282 list_add_tail(&b, &list);
283
284 KUNIT_EXPECT_TRUE(test, list_is_first(&a, &list));
285 KUNIT_EXPECT_FALSE(test, list_is_first(&b, &list));
286}
287
288static void list_test_list_is_last(struct kunit *test)
289{
290 struct list_head a, b;
291 LIST_HEAD(list);
292
293 list_add_tail(&a, &list);
294 list_add_tail(&b, &list);
295
296 KUNIT_EXPECT_FALSE(test, list_is_last(&a, &list));
297 KUNIT_EXPECT_TRUE(test, list_is_last(&b, &list));
298}
299
300static void list_test_list_empty(struct kunit *test)
301{
302 struct list_head a;
303 LIST_HEAD(list1);
304 LIST_HEAD(list2);
305
306 list_add_tail(&a, &list1);
307
308 KUNIT_EXPECT_FALSE(test, list_empty(&list1));
309 KUNIT_EXPECT_TRUE(test, list_empty(&list2));
310}
311
312static void list_test_list_empty_careful(struct kunit *test)
313{
314 /* This test doesn't check correctness under concurrent access */
315 struct list_head a;
316 LIST_HEAD(list1);
317 LIST_HEAD(list2);
318
319 list_add_tail(&a, &list1);
320
321 KUNIT_EXPECT_FALSE(test, list_empty_careful(&list1));
322 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
323}
324
325static void list_test_list_rotate_left(struct kunit *test)
326{
327 struct list_head a, b;
328 LIST_HEAD(list);
329
330 list_add_tail(&a, &list);
331 list_add_tail(&b, &list);
332
333 /* before: [list] -> a -> b */
334 list_rotate_left(&list);
335 /* after: [list] -> b -> a */
336
337 KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
338 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
339 KUNIT_EXPECT_PTR_EQ(test, b.next, &a);
340}
341
342static void list_test_list_rotate_to_front(struct kunit *test)
343{
344 struct list_head a, b, c, d;
345 struct list_head *list_values[] = { &c, &d, &a, &b };
346 struct list_head *ptr;
347 LIST_HEAD(list);
348 int i = 0;
349
350 list_add_tail(&a, &list);
351 list_add_tail(&b, &list);
352 list_add_tail(&c, &list);
353 list_add_tail(&d, &list);
354
355 /* before: [list] -> a -> b -> c -> d */
356 list_rotate_to_front(&c, &list);
357 /* after: [list] -> c -> d -> a -> b */
358
359 list_for_each(ptr, &list) {
360 KUNIT_EXPECT_PTR_EQ(test, ptr, list_values[i]);
361 i++;
362 }
363 KUNIT_EXPECT_EQ(test, i, 4);
364}
365
366static void list_test_list_is_singular(struct kunit *test)
367{
368 struct list_head a, b;
369 LIST_HEAD(list);
370
371 /* [list] empty */
372 KUNIT_EXPECT_FALSE(test, list_is_singular(&list));
373
374 list_add_tail(&a, &list);
375
376 /* [list] -> a */
377 KUNIT_EXPECT_TRUE(test, list_is_singular(&list));
378
379 list_add_tail(&b, &list);
380
381 /* [list] -> a -> b */
382 KUNIT_EXPECT_FALSE(test, list_is_singular(&list));
383}
384
385static void list_test_list_cut_position(struct kunit *test)
386{
387 struct list_head entries[3], *cur;
388 LIST_HEAD(list1);
389 LIST_HEAD(list2);
390 int i = 0;
391
392 list_add_tail(&entries[0], &list1);
393 list_add_tail(&entries[1], &list1);
394 list_add_tail(&entries[2], &list1);
395
396 /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */
397 list_cut_position(&list2, &list1, &entries[1]);
398 /* after: [list2] -> entries[0] -> entries[1], [list1] -> entries[2] */
399
400 list_for_each(cur, &list2) {
401 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
402 i++;
403 }
404
405 KUNIT_EXPECT_EQ(test, i, 2);
406
407 list_for_each(cur, &list1) {
408 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
409 i++;
410 }
411}
412
413static void list_test_list_cut_before(struct kunit *test)
414{
415 struct list_head entries[3], *cur;
416 LIST_HEAD(list1);
417 LIST_HEAD(list2);
418 int i = 0;
419
420 list_add_tail(&entries[0], &list1);
421 list_add_tail(&entries[1], &list1);
422 list_add_tail(&entries[2], &list1);
423
424 /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */
425 list_cut_before(&list2, &list1, &entries[1]);
426 /* after: [list2] -> entries[0], [list1] -> entries[1] -> entries[2] */
427
428 list_for_each(cur, &list2) {
429 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
430 i++;
431 }
432
433 KUNIT_EXPECT_EQ(test, i, 1);
434
435 list_for_each(cur, &list1) {
436 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
437 i++;
438 }
439}
440
441static void list_test_list_splice(struct kunit *test)
442{
443 struct list_head entries[5], *cur;
444 LIST_HEAD(list1);
445 LIST_HEAD(list2);
446 int i = 0;
447
448 list_add_tail(&entries[0], &list1);
449 list_add_tail(&entries[1], &list1);
450 list_add_tail(&entries[2], &list2);
451 list_add_tail(&entries[3], &list2);
452 list_add_tail(&entries[4], &list1);
453
454 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
455 list_splice(&list2, &entries[1]);
456 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */
457
458 list_for_each(cur, &list1) {
459 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
460 i++;
461 }
462
463 KUNIT_EXPECT_EQ(test, i, 5);
464}
465
466static void list_test_list_splice_tail(struct kunit *test)
467{
468 struct list_head entries[5], *cur;
469 LIST_HEAD(list1);
470 LIST_HEAD(list2);
471 int i = 0;
472
473 list_add_tail(&entries[0], &list1);
474 list_add_tail(&entries[1], &list1);
475 list_add_tail(&entries[2], &list2);
476 list_add_tail(&entries[3], &list2);
477 list_add_tail(&entries[4], &list1);
478
479 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
480 list_splice_tail(&list2, &entries[4]);
481 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */
482
483 list_for_each(cur, &list1) {
484 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
485 i++;
486 }
487
488 KUNIT_EXPECT_EQ(test, i, 5);
489}
490
491static void list_test_list_splice_init(struct kunit *test)
492{
493 struct list_head entries[5], *cur;
494 LIST_HEAD(list1);
495 LIST_HEAD(list2);
496 int i = 0;
497
498 list_add_tail(&entries[0], &list1);
499 list_add_tail(&entries[1], &list1);
500 list_add_tail(&entries[2], &list2);
501 list_add_tail(&entries[3], &list2);
502 list_add_tail(&entries[4], &list1);
503
504 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
505 list_splice_init(&list2, &entries[1]);
506 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */
507
508 list_for_each(cur, &list1) {
509 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
510 i++;
511 }
512
513 KUNIT_EXPECT_EQ(test, i, 5);
514
515 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
516}
517
518static void list_test_list_splice_tail_init(struct kunit *test)
519{
520 struct list_head entries[5], *cur;
521 LIST_HEAD(list1);
522 LIST_HEAD(list2);
523 int i = 0;
524
525 list_add_tail(&entries[0], &list1);
526 list_add_tail(&entries[1], &list1);
527 list_add_tail(&entries[2], &list2);
528 list_add_tail(&entries[3], &list2);
529 list_add_tail(&entries[4], &list1);
530
531 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
532 list_splice_tail_init(&list2, &entries[4]);
533 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */
534
535 list_for_each(cur, &list1) {
536 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
537 i++;
538 }
539
540 KUNIT_EXPECT_EQ(test, i, 5);
541
542 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
543}
544
545static void list_test_list_entry(struct kunit *test)
546{
547 struct list_test_struct test_struct;
548
549 KUNIT_EXPECT_PTR_EQ(test, &test_struct, list_entry(&(test_struct.list),
550 struct list_test_struct, list));
551}
552
553static void list_test_list_entry_is_head(struct kunit *test)
554{
555 struct list_test_struct test_struct1, test_struct2, test_struct3;
556
557 INIT_LIST_HEAD(&test_struct1.list);
558 INIT_LIST_HEAD(&test_struct3.list);
559
560 list_add_tail(&test_struct2.list, &test_struct1.list);
561
562 KUNIT_EXPECT_TRUE_MSG(test,
563 list_entry_is_head((&test_struct1), &test_struct1.list, list),
564 "Head element of same list");
565 KUNIT_EXPECT_FALSE_MSG(test,
566 list_entry_is_head((&test_struct2), &test_struct1.list, list),
567 "Non-head element of same list");
568 KUNIT_EXPECT_FALSE_MSG(test,
569 list_entry_is_head((&test_struct3), &test_struct1.list, list),
570 "Head element of different list");
571}
572
573static void list_test_list_first_entry(struct kunit *test)
574{
575 struct list_test_struct test_struct1, test_struct2;
576 LIST_HEAD(list);
577
578 list_add_tail(&test_struct1.list, &list);
579 list_add_tail(&test_struct2.list, &list);
580
581
582 KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_first_entry(&list,
583 struct list_test_struct, list));
584}
585
586static void list_test_list_last_entry(struct kunit *test)
587{
588 struct list_test_struct test_struct1, test_struct2;
589 LIST_HEAD(list);
590
591 list_add_tail(&test_struct1.list, &list);
592 list_add_tail(&test_struct2.list, &list);
593
594
595 KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_last_entry(&list,
596 struct list_test_struct, list));
597}
598
599static void list_test_list_first_entry_or_null(struct kunit *test)
600{
601 struct list_test_struct test_struct1, test_struct2;
602 LIST_HEAD(list);
603
604 KUNIT_EXPECT_FALSE(test, list_first_entry_or_null(&list,
605 struct list_test_struct, list));
606
607 list_add_tail(&test_struct1.list, &list);
608 list_add_tail(&test_struct2.list, &list);
609
610 KUNIT_EXPECT_PTR_EQ(test, &test_struct1,
611 list_first_entry_or_null(&list,
612 struct list_test_struct, list));
613}
614
615static void list_test_list_next_entry(struct kunit *test)
616{
617 struct list_test_struct test_struct1, test_struct2;
618 LIST_HEAD(list);
619
620 list_add_tail(&test_struct1.list, &list);
621 list_add_tail(&test_struct2.list, &list);
622
623
624 KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_next_entry(&test_struct1,
625 list));
626}
627
628static void list_test_list_prev_entry(struct kunit *test)
629{
630 struct list_test_struct test_struct1, test_struct2;
631 LIST_HEAD(list);
632
633 list_add_tail(&test_struct1.list, &list);
634 list_add_tail(&test_struct2.list, &list);
635
636
637 KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_prev_entry(&test_struct2,
638 list));
639}
640
641static void list_test_list_for_each(struct kunit *test)
642{
643 struct list_head entries[3], *cur;
644 LIST_HEAD(list);
645 int i = 0;
646
647 list_add_tail(&entries[0], &list);
648 list_add_tail(&entries[1], &list);
649 list_add_tail(&entries[2], &list);
650
651 list_for_each(cur, &list) {
652 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
653 i++;
654 }
655
656 KUNIT_EXPECT_EQ(test, i, 3);
657}
658
659static void list_test_list_for_each_prev(struct kunit *test)
660{
661 struct list_head entries[3], *cur;
662 LIST_HEAD(list);
663 int i = 2;
664
665 list_add_tail(&entries[0], &list);
666 list_add_tail(&entries[1], &list);
667 list_add_tail(&entries[2], &list);
668
669 list_for_each_prev(cur, &list) {
670 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
671 i--;
672 }
673
674 KUNIT_EXPECT_EQ(test, i, -1);
675}
676
677static void list_test_list_for_each_safe(struct kunit *test)
678{
679 struct list_head entries[3], *cur, *n;
680 LIST_HEAD(list);
681 int i = 0;
682
683
684 list_add_tail(&entries[0], &list);
685 list_add_tail(&entries[1], &list);
686 list_add_tail(&entries[2], &list);
687
688 list_for_each_safe(cur, n, &list) {
689 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
690 list_del(&entries[i]);
691 i++;
692 }
693
694 KUNIT_EXPECT_EQ(test, i, 3);
695 KUNIT_EXPECT_TRUE(test, list_empty(&list));
696}
697
698static void list_test_list_for_each_prev_safe(struct kunit *test)
699{
700 struct list_head entries[3], *cur, *n;
701 LIST_HEAD(list);
702 int i = 2;
703
704 list_add_tail(&entries[0], &list);
705 list_add_tail(&entries[1], &list);
706 list_add_tail(&entries[2], &list);
707
708 list_for_each_prev_safe(cur, n, &list) {
709 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
710 list_del(&entries[i]);
711 i--;
712 }
713
714 KUNIT_EXPECT_EQ(test, i, -1);
715 KUNIT_EXPECT_TRUE(test, list_empty(&list));
716}
717
718static void list_test_list_for_each_entry(struct kunit *test)
719{
720 struct list_test_struct entries[5], *cur;
721 LIST_HEAD(list);
722 int i = 0;
723
724 for (i = 0; i < 5; ++i) {
725 entries[i].data = i;
726 list_add_tail(&entries[i].list, &list);
727 }
728
729 i = 0;
730
731 list_for_each_entry(cur, &list, list) {
732 KUNIT_EXPECT_EQ(test, cur->data, i);
733 i++;
734 }
735
736 KUNIT_EXPECT_EQ(test, i, 5);
737}
738
739static void list_test_list_for_each_entry_reverse(struct kunit *test)
740{
741 struct list_test_struct entries[5], *cur;
742 LIST_HEAD(list);
743 int i = 0;
744
745 for (i = 0; i < 5; ++i) {
746 entries[i].data = i;
747 list_add_tail(&entries[i].list, &list);
748 }
749
750 i = 4;
751
752 list_for_each_entry_reverse(cur, &list, list) {
753 KUNIT_EXPECT_EQ(test, cur->data, i);
754 i--;
755 }
756
757 KUNIT_EXPECT_EQ(test, i, -1);
758}
759
760static struct kunit_case list_test_cases[] = {
761 KUNIT_CASE(list_test_list_init),
762 KUNIT_CASE(list_test_list_add),
763 KUNIT_CASE(list_test_list_add_tail),
764 KUNIT_CASE(list_test_list_del),
765 KUNIT_CASE(list_test_list_replace),
766 KUNIT_CASE(list_test_list_replace_init),
767 KUNIT_CASE(list_test_list_swap),
768 KUNIT_CASE(list_test_list_del_init),
769 KUNIT_CASE(list_test_list_del_init_careful),
770 KUNIT_CASE(list_test_list_move),
771 KUNIT_CASE(list_test_list_move_tail),
772 KUNIT_CASE(list_test_list_bulk_move_tail),
773 KUNIT_CASE(list_test_list_is_head),
774 KUNIT_CASE(list_test_list_is_first),
775 KUNIT_CASE(list_test_list_is_last),
776 KUNIT_CASE(list_test_list_empty),
777 KUNIT_CASE(list_test_list_empty_careful),
778 KUNIT_CASE(list_test_list_rotate_left),
779 KUNIT_CASE(list_test_list_rotate_to_front),
780 KUNIT_CASE(list_test_list_is_singular),
781 KUNIT_CASE(list_test_list_cut_position),
782 KUNIT_CASE(list_test_list_cut_before),
783 KUNIT_CASE(list_test_list_splice),
784 KUNIT_CASE(list_test_list_splice_tail),
785 KUNIT_CASE(list_test_list_splice_init),
786 KUNIT_CASE(list_test_list_splice_tail_init),
787 KUNIT_CASE(list_test_list_entry),
788 KUNIT_CASE(list_test_list_entry_is_head),
789 KUNIT_CASE(list_test_list_first_entry),
790 KUNIT_CASE(list_test_list_last_entry),
791 KUNIT_CASE(list_test_list_first_entry_or_null),
792 KUNIT_CASE(list_test_list_next_entry),
793 KUNIT_CASE(list_test_list_prev_entry),
794 KUNIT_CASE(list_test_list_for_each),
795 KUNIT_CASE(list_test_list_for_each_prev),
796 KUNIT_CASE(list_test_list_for_each_safe),
797 KUNIT_CASE(list_test_list_for_each_prev_safe),
798 KUNIT_CASE(list_test_list_for_each_entry),
799 KUNIT_CASE(list_test_list_for_each_entry_reverse),
800 {},
801};
802
803static struct kunit_suite list_test_module = {
804 .name = "list-kunit-test",
805 .test_cases = list_test_cases,
806};
807
808struct hlist_test_struct {
809 int data;
810 struct hlist_node list;
811};
812
813static void hlist_test_init(struct kunit *test)
814{
815 /* Test the different ways of initialising a list. */
816 struct hlist_head list1 = HLIST_HEAD_INIT;
817 struct hlist_head list2;
818 HLIST_HEAD(list3);
819 struct hlist_head *list4;
820 struct hlist_head *list5;
821
822 INIT_HLIST_HEAD(&list2);
823
824 list4 = kzalloc(sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL);
825 INIT_HLIST_HEAD(list4);
826
827 list5 = kmalloc(sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL);
828 memset(list5, 0xFF, sizeof(*list5));
829 INIT_HLIST_HEAD(list5);
830
831 KUNIT_EXPECT_TRUE(test, hlist_empty(&list1));
832 KUNIT_EXPECT_TRUE(test, hlist_empty(&list2));
833 KUNIT_EXPECT_TRUE(test, hlist_empty(&list3));
834 KUNIT_EXPECT_TRUE(test, hlist_empty(list4));
835 KUNIT_EXPECT_TRUE(test, hlist_empty(list5));
836
837 kfree(list4);
838 kfree(list5);
839}
840
841static void hlist_test_unhashed(struct kunit *test)
842{
843 struct hlist_node a;
844 HLIST_HEAD(list);
845
846 INIT_HLIST_NODE(&a);
847
848 /* is unhashed by default */
849 KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a));
850
851 hlist_add_head(&a, &list);
852
853 /* is hashed once added to list */
854 KUNIT_EXPECT_FALSE(test, hlist_unhashed(&a));
855
856 hlist_del_init(&a);
857
858 /* is again unhashed after del_init */
859 KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a));
860}
861
862/* Doesn't test concurrency guarantees */
863static void hlist_test_unhashed_lockless(struct kunit *test)
864{
865 struct hlist_node a;
866 HLIST_HEAD(list);
867
868 INIT_HLIST_NODE(&a);
869
870 /* is unhashed by default */
871 KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a));
872
873 hlist_add_head(&a, &list);
874
875 /* is hashed once added to list */
876 KUNIT_EXPECT_FALSE(test, hlist_unhashed_lockless(&a));
877
878 hlist_del_init(&a);
879
880 /* is again unhashed after del_init */
881 KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a));
882}
883
884static void hlist_test_del(struct kunit *test)
885{
886 struct hlist_node a, b;
887 HLIST_HEAD(list);
888
889 hlist_add_head(&a, &list);
890 hlist_add_behind(&b, &a);
891
892 /* before: [list] -> a -> b */
893 hlist_del(&a);
894
895 /* now: [list] -> b */
896 KUNIT_EXPECT_PTR_EQ(test, list.first, &b);
897 KUNIT_EXPECT_PTR_EQ(test, b.pprev, &list.first);
898}
899
900static void hlist_test_del_init(struct kunit *test)
901{
902 struct hlist_node a, b;
903 HLIST_HEAD(list);
904
905 hlist_add_head(&a, &list);
906 hlist_add_behind(&b, &a);
907
908 /* before: [list] -> a -> b */
909 hlist_del_init(&a);
910
911 /* now: [list] -> b */
912 KUNIT_EXPECT_PTR_EQ(test, list.first, &b);
913 KUNIT_EXPECT_PTR_EQ(test, b.pprev, &list.first);
914
915 /* a is now initialised */
916 KUNIT_EXPECT_PTR_EQ(test, a.next, NULL);
917 KUNIT_EXPECT_PTR_EQ(test, a.pprev, NULL);
918}
919
920/* Tests all three hlist_add_* functions */
921static void hlist_test_add(struct kunit *test)
922{
923 struct hlist_node a, b, c, d;
924 HLIST_HEAD(list);
925
926 hlist_add_head(&a, &list);
927 hlist_add_head(&b, &list);
928 hlist_add_before(&c, &a);
929 hlist_add_behind(&d, &a);
930
931 /* should be [list] -> b -> c -> a -> d */
932 KUNIT_EXPECT_PTR_EQ(test, list.first, &b);
933
934 KUNIT_EXPECT_PTR_EQ(test, c.pprev, &(b.next));
935 KUNIT_EXPECT_PTR_EQ(test, b.next, &c);
936
937 KUNIT_EXPECT_PTR_EQ(test, a.pprev, &(c.next));
938 KUNIT_EXPECT_PTR_EQ(test, c.next, &a);
939
940 KUNIT_EXPECT_PTR_EQ(test, d.pprev, &(a.next));
941 KUNIT_EXPECT_PTR_EQ(test, a.next, &d);
942}
943
944/* Tests both hlist_fake() and hlist_add_fake() */
945static void hlist_test_fake(struct kunit *test)
946{
947 struct hlist_node a;
948
949 INIT_HLIST_NODE(&a);
950
951 /* not fake after init */
952 KUNIT_EXPECT_FALSE(test, hlist_fake(&a));
953
954 hlist_add_fake(&a);
955
956 /* is now fake */
957 KUNIT_EXPECT_TRUE(test, hlist_fake(&a));
958}
959
960static void hlist_test_is_singular_node(struct kunit *test)
961{
962 struct hlist_node a, b;
963 HLIST_HEAD(list);
964
965 INIT_HLIST_NODE(&a);
966 KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list));
967
968 hlist_add_head(&a, &list);
969 KUNIT_EXPECT_TRUE(test, hlist_is_singular_node(&a, &list));
970
971 hlist_add_head(&b, &list);
972 KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list));
973 KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&b, &list));
974}
975
976static void hlist_test_empty(struct kunit *test)
977{
978 struct hlist_node a;
979 HLIST_HEAD(list);
980
981 /* list starts off empty */
982 KUNIT_EXPECT_TRUE(test, hlist_empty(&list));
983
984 hlist_add_head(&a, &list);
985
986 /* list is no longer empty */
987 KUNIT_EXPECT_FALSE(test, hlist_empty(&list));
988}
989
990static void hlist_test_move_list(struct kunit *test)
991{
992 struct hlist_node a;
993 HLIST_HEAD(list1);
994 HLIST_HEAD(list2);
995
996 hlist_add_head(&a, &list1);
997
998 KUNIT_EXPECT_FALSE(test, hlist_empty(&list1));
999 KUNIT_EXPECT_TRUE(test, hlist_empty(&list2));
1000 hlist_move_list(&list1, &list2);
1001 KUNIT_EXPECT_TRUE(test, hlist_empty(&list1));
1002 KUNIT_EXPECT_FALSE(test, hlist_empty(&list2));
1003
1004}
1005
1006static void hlist_test_entry(struct kunit *test)
1007{
1008 struct hlist_test_struct test_struct;
1009
1010 KUNIT_EXPECT_PTR_EQ(test, &test_struct,
1011 hlist_entry(&(test_struct.list),
1012 struct hlist_test_struct, list));
1013}
1014
1015static void hlist_test_entry_safe(struct kunit *test)
1016{
1017 struct hlist_test_struct test_struct;
1018
1019 KUNIT_EXPECT_PTR_EQ(test, &test_struct,
1020 hlist_entry_safe(&(test_struct.list),
1021 struct hlist_test_struct, list));
1022
1023 KUNIT_EXPECT_PTR_EQ(test, NULL,
1024 hlist_entry_safe((struct hlist_node *)NULL,
1025 struct hlist_test_struct, list));
1026}
1027
1028static void hlist_test_for_each(struct kunit *test)
1029{
1030 struct hlist_node entries[3], *cur;
1031 HLIST_HEAD(list);
1032 int i = 0;
1033
1034 hlist_add_head(&entries[0], &list);
1035 hlist_add_behind(&entries[1], &entries[0]);
1036 hlist_add_behind(&entries[2], &entries[1]);
1037
1038 hlist_for_each(cur, &list) {
1039 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
1040 i++;
1041 }
1042
1043 KUNIT_EXPECT_EQ(test, i, 3);
1044}
1045
1046
1047static void hlist_test_for_each_safe(struct kunit *test)
1048{
1049 struct hlist_node entries[3], *cur, *n;
1050 HLIST_HEAD(list);
1051 int i = 0;
1052
1053 hlist_add_head(&entries[0], &list);
1054 hlist_add_behind(&entries[1], &entries[0]);
1055 hlist_add_behind(&entries[2], &entries[1]);
1056
1057 hlist_for_each_safe(cur, n, &list) {
1058 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
1059 hlist_del(&entries[i]);
1060 i++;
1061 }
1062
1063 KUNIT_EXPECT_EQ(test, i, 3);
1064 KUNIT_EXPECT_TRUE(test, hlist_empty(&list));
1065}
1066
1067static void hlist_test_for_each_entry(struct kunit *test)
1068{
1069 struct hlist_test_struct entries[5], *cur;
1070 HLIST_HEAD(list);
1071 int i = 0;
1072
1073 entries[0].data = 0;
1074 hlist_add_head(&entries[0].list, &list);
1075 for (i = 1; i < 5; ++i) {
1076 entries[i].data = i;
1077 hlist_add_behind(&entries[i].list, &entries[i-1].list);
1078 }
1079
1080 i = 0;
1081
1082 hlist_for_each_entry(cur, &list, list) {
1083 KUNIT_EXPECT_EQ(test, cur->data, i);
1084 i++;
1085 }
1086
1087 KUNIT_EXPECT_EQ(test, i, 5);
1088}
1089
1090static void hlist_test_for_each_entry_continue(struct kunit *test)
1091{
1092 struct hlist_test_struct entries[5], *cur;
1093 HLIST_HEAD(list);
1094 int i = 0;
1095
1096 entries[0].data = 0;
1097 hlist_add_head(&entries[0].list, &list);
1098 for (i = 1; i < 5; ++i) {
1099 entries[i].data = i;
1100 hlist_add_behind(&entries[i].list, &entries[i-1].list);
1101 }
1102
1103 /* We skip the first (zero-th) entry. */
1104 i = 1;
1105
1106 cur = &entries[0];
1107 hlist_for_each_entry_continue(cur, list) {
1108 KUNIT_EXPECT_EQ(test, cur->data, i);
1109 /* Stamp over the entry. */
1110 cur->data = 42;
1111 i++;
1112 }
1113
1114 KUNIT_EXPECT_EQ(test, i, 5);
1115 /* The first entry was not visited. */
1116 KUNIT_EXPECT_EQ(test, entries[0].data, 0);
1117 /* The second (and presumably others), were. */
1118 KUNIT_EXPECT_EQ(test, entries[1].data, 42);
1119}
1120
1121static void hlist_test_for_each_entry_from(struct kunit *test)
1122{
1123 struct hlist_test_struct entries[5], *cur;
1124 HLIST_HEAD(list);
1125 int i = 0;
1126
1127 entries[0].data = 0;
1128 hlist_add_head(&entries[0].list, &list);
1129 for (i = 1; i < 5; ++i) {
1130 entries[i].data = i;
1131 hlist_add_behind(&entries[i].list, &entries[i-1].list);
1132 }
1133
1134 i = 0;
1135
1136 cur = &entries[0];
1137 hlist_for_each_entry_from(cur, list) {
1138 KUNIT_EXPECT_EQ(test, cur->data, i);
1139 /* Stamp over the entry. */
1140 cur->data = 42;
1141 i++;
1142 }
1143
1144 KUNIT_EXPECT_EQ(test, i, 5);
1145 /* The first entry was visited. */
1146 KUNIT_EXPECT_EQ(test, entries[0].data, 42);
1147}
1148
1149static void hlist_test_for_each_entry_safe(struct kunit *test)
1150{
1151 struct hlist_test_struct entries[5], *cur;
1152 struct hlist_node *tmp_node;
1153 HLIST_HEAD(list);
1154 int i = 0;
1155
1156 entries[0].data = 0;
1157 hlist_add_head(&entries[0].list, &list);
1158 for (i = 1; i < 5; ++i) {
1159 entries[i].data = i;
1160 hlist_add_behind(&entries[i].list, &entries[i-1].list);
1161 }
1162
1163 i = 0;
1164
1165 hlist_for_each_entry_safe(cur, tmp_node, &list, list) {
1166 KUNIT_EXPECT_EQ(test, cur->data, i);
1167 hlist_del(&cur->list);
1168 i++;
1169 }
1170
1171 KUNIT_EXPECT_EQ(test, i, 5);
1172 KUNIT_EXPECT_TRUE(test, hlist_empty(&list));
1173}
1174
1175
1176static struct kunit_case hlist_test_cases[] = {
1177 KUNIT_CASE(hlist_test_init),
1178 KUNIT_CASE(hlist_test_unhashed),
1179 KUNIT_CASE(hlist_test_unhashed_lockless),
1180 KUNIT_CASE(hlist_test_del),
1181 KUNIT_CASE(hlist_test_del_init),
1182 KUNIT_CASE(hlist_test_add),
1183 KUNIT_CASE(hlist_test_fake),
1184 KUNIT_CASE(hlist_test_is_singular_node),
1185 KUNIT_CASE(hlist_test_empty),
1186 KUNIT_CASE(hlist_test_move_list),
1187 KUNIT_CASE(hlist_test_entry),
1188 KUNIT_CASE(hlist_test_entry_safe),
1189 KUNIT_CASE(hlist_test_for_each),
1190 KUNIT_CASE(hlist_test_for_each_safe),
1191 KUNIT_CASE(hlist_test_for_each_entry),
1192 KUNIT_CASE(hlist_test_for_each_entry_continue),
1193 KUNIT_CASE(hlist_test_for_each_entry_from),
1194 KUNIT_CASE(hlist_test_for_each_entry_safe),
1195 {},
1196};
1197
1198static struct kunit_suite hlist_test_module = {
1199 .name = "hlist",
1200 .test_cases = hlist_test_cases,
1201};
1202
1203
1204struct klist_test_struct {
1205 int data;
1206 struct klist klist;
1207 struct klist_node klist_node;
1208};
1209
1210static int node_count;
1211static struct klist_node *last_node;
1212
1213static void check_node(struct klist_node *node_ptr)
1214{
1215 node_count++;
1216 last_node = node_ptr;
1217}
1218
1219static void check_delete_node(struct klist_node *node_ptr)
1220{
1221 node_count--;
1222 last_node = node_ptr;
1223}
1224
1225static void klist_test_add_tail(struct kunit *test)
1226{
1227 struct klist_node a, b;
1228 struct klist mylist;
1229 struct klist_iter i;
1230
1231 node_count = 0;
1232 klist_init(&mylist, &check_node, NULL);
1233
1234 klist_add_tail(&a, &mylist);
1235 KUNIT_EXPECT_EQ(test, node_count, 1);
1236 KUNIT_EXPECT_PTR_EQ(test, last_node, &a);
1237
1238 klist_add_tail(&b, &mylist);
1239 KUNIT_EXPECT_EQ(test, node_count, 2);
1240 KUNIT_EXPECT_PTR_EQ(test, last_node, &b);
1241
1242 /* should be [list] -> a -> b */
1243 klist_iter_init(&mylist, &i);
1244
1245 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
1246 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
1247 KUNIT_EXPECT_NULL(test, klist_next(&i));
1248
1249 klist_iter_exit(&i);
1250
1251}
1252
1253static void klist_test_add_head(struct kunit *test)
1254{
1255 struct klist_node a, b;
1256 struct klist mylist;
1257 struct klist_iter i;
1258
1259 node_count = 0;
1260 klist_init(&mylist, &check_node, NULL);
1261
1262 klist_add_head(&a, &mylist);
1263 KUNIT_EXPECT_EQ(test, node_count, 1);
1264 KUNIT_EXPECT_PTR_EQ(test, last_node, &a);
1265
1266 klist_add_head(&b, &mylist);
1267 KUNIT_EXPECT_EQ(test, node_count, 2);
1268 KUNIT_EXPECT_PTR_EQ(test, last_node, &b);
1269
1270 /* should be [list] -> b -> a */
1271 klist_iter_init(&mylist, &i);
1272
1273 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
1274 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
1275 KUNIT_EXPECT_NULL(test, klist_next(&i));
1276
1277 klist_iter_exit(&i);
1278
1279}
1280
1281static void klist_test_add_behind(struct kunit *test)
1282{
1283 struct klist_node a, b, c, d;
1284 struct klist mylist;
1285 struct klist_iter i;
1286
1287 node_count = 0;
1288 klist_init(&mylist, &check_node, NULL);
1289
1290 klist_add_head(&a, &mylist);
1291 klist_add_head(&b, &mylist);
1292
1293 klist_add_behind(&c, &a);
1294 KUNIT_EXPECT_EQ(test, node_count, 3);
1295 KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
1296
1297 klist_add_behind(&d, &b);
1298 KUNIT_EXPECT_EQ(test, node_count, 4);
1299 KUNIT_EXPECT_PTR_EQ(test, last_node, &d);
1300
1301 klist_iter_init(&mylist, &i);
1302
1303 /* should be [list] -> b -> d -> a -> c*/
1304 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
1305 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d);
1306 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
1307 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c);
1308 KUNIT_EXPECT_NULL(test, klist_next(&i));
1309
1310 klist_iter_exit(&i);
1311
1312}
1313
1314static void klist_test_add_before(struct kunit *test)
1315{
1316 struct klist_node a, b, c, d;
1317 struct klist mylist;
1318 struct klist_iter i;
1319
1320 node_count = 0;
1321 klist_init(&mylist, &check_node, NULL);
1322
1323 klist_add_head(&a, &mylist);
1324 klist_add_head(&b, &mylist);
1325 klist_add_before(&c, &a);
1326 KUNIT_EXPECT_EQ(test, node_count, 3);
1327 KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
1328
1329 klist_add_before(&d, &b);
1330 KUNIT_EXPECT_EQ(test, node_count, 4);
1331 KUNIT_EXPECT_PTR_EQ(test, last_node, &d);
1332
1333 klist_iter_init(&mylist, &i);
1334
1335 /* should be [list] -> b -> d -> a -> c*/
1336 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d);
1337 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
1338 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c);
1339 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
1340 KUNIT_EXPECT_NULL(test, klist_next(&i));
1341
1342 klist_iter_exit(&i);
1343
1344}
1345
1346/*
1347 * Verify that klist_del() delays the deletion of a node until there
1348 * are no other references to it
1349 */
1350static void klist_test_del_refcount_greater_than_zero(struct kunit *test)
1351{
1352 struct klist_node a, b, c, d;
1353 struct klist mylist;
1354 struct klist_iter i;
1355
1356 node_count = 0;
1357 klist_init(&mylist, &check_node, &check_delete_node);
1358
1359 /* Add nodes a,b,c,d to the list*/
1360 klist_add_tail(&a, &mylist);
1361 klist_add_tail(&b, &mylist);
1362 klist_add_tail(&c, &mylist);
1363 klist_add_tail(&d, &mylist);
1364
1365 klist_iter_init(&mylist, &i);
1366
1367 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
1368 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
1369 /* Advance the iterator to point to node c*/
1370 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c);
1371
1372 /* Try to delete node c while there is a reference to it*/
1373 klist_del(&c);
1374
1375 /*
1376 * Verify that node c is still attached to the list even after being
1377 * deleted. Since the iterator still points to c, the reference count is not
1378 * decreased to 0
1379 */
1380 KUNIT_EXPECT_TRUE(test, klist_node_attached(&c));
1381
1382 /* Check that node c has not been removed yet*/
1383 KUNIT_EXPECT_EQ(test, node_count, 4);
1384 KUNIT_EXPECT_PTR_EQ(test, last_node, &d);
1385
1386 klist_iter_exit(&i);
1387
1388 /*
1389 * Since the iterator is no longer pointing to node c, node c is removed
1390 * from the list
1391 */
1392 KUNIT_EXPECT_EQ(test, node_count, 3);
1393 KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
1394
1395}
1396
1397/*
1398 * Verify that klist_del() deletes a node immediately when there are no
1399 * other references to it.
1400 */
1401static void klist_test_del_refcount_zero(struct kunit *test)
1402{
1403 struct klist_node a, b, c, d;
1404 struct klist mylist;
1405 struct klist_iter i;
1406
1407 node_count = 0;
1408 klist_init(&mylist, &check_node, &check_delete_node);
1409
1410 /* Add nodes a,b,c,d to the list*/
1411 klist_add_tail(&a, &mylist);
1412 klist_add_tail(&b, &mylist);
1413 klist_add_tail(&c, &mylist);
1414 klist_add_tail(&d, &mylist);
1415 /* Delete node c*/
1416 klist_del(&c);
1417
1418 /* Check that node c is deleted from the list*/
1419 KUNIT_EXPECT_EQ(test, node_count, 3);
1420 KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
1421
1422 /* Should be [list] -> a -> b -> d*/
1423 klist_iter_init(&mylist, &i);
1424
1425 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
1426 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
1427 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d);
1428 KUNIT_EXPECT_NULL(test, klist_next(&i));
1429
1430 klist_iter_exit(&i);
1431
1432}
1433
1434static void klist_test_remove(struct kunit *test)
1435{
1436 /* This test doesn't check correctness under concurrent access */
1437 struct klist_node a, b, c, d;
1438 struct klist mylist;
1439 struct klist_iter i;
1440
1441 node_count = 0;
1442 klist_init(&mylist, &check_node, &check_delete_node);
1443
1444 /* Add nodes a,b,c,d to the list*/
1445 klist_add_tail(&a, &mylist);
1446 klist_add_tail(&b, &mylist);
1447 klist_add_tail(&c, &mylist);
1448 klist_add_tail(&d, &mylist);
1449 /* Delete node c*/
1450 klist_remove(&c);
1451
1452 /* Check the nodes in the list*/
1453 KUNIT_EXPECT_EQ(test, node_count, 3);
1454 KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
1455
1456 /* should be [list] -> a -> b -> d*/
1457 klist_iter_init(&mylist, &i);
1458
1459 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
1460 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
1461 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d);
1462 KUNIT_EXPECT_NULL(test, klist_next(&i));
1463
1464 klist_iter_exit(&i);
1465
1466}
1467
1468static void klist_test_node_attached(struct kunit *test)
1469{
1470 struct klist_node a = {};
1471 struct klist mylist;
1472
1473 klist_init(&mylist, NULL, NULL);
1474
1475 KUNIT_EXPECT_FALSE(test, klist_node_attached(&a));
1476 klist_add_head(&a, &mylist);
1477 KUNIT_EXPECT_TRUE(test, klist_node_attached(&a));
1478 klist_del(&a);
1479 KUNIT_EXPECT_FALSE(test, klist_node_attached(&a));
1480
1481}
1482
1483static struct kunit_case klist_test_cases[] = {
1484 KUNIT_CASE(klist_test_add_tail),
1485 KUNIT_CASE(klist_test_add_head),
1486 KUNIT_CASE(klist_test_add_behind),
1487 KUNIT_CASE(klist_test_add_before),
1488 KUNIT_CASE(klist_test_del_refcount_greater_than_zero),
1489 KUNIT_CASE(klist_test_del_refcount_zero),
1490 KUNIT_CASE(klist_test_remove),
1491 KUNIT_CASE(klist_test_node_attached),
1492 {},
1493};
1494
1495static struct kunit_suite klist_test_module = {
1496 .name = "klist",
1497 .test_cases = klist_test_cases,
1498};
1499
1500kunit_test_suites(&list_test_module, &hlist_test_module, &klist_test_module);
1501
1502MODULE_LICENSE("GPL v2");