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
13 struct list_test_struct {
14 int data;
15 struct list_head list;
16 };
17
18 static 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
47 static 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
61 static 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
75 static 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
91 static 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
107 static 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
126 static 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
148 static 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
165 static 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
185 static 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
204 static 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
223 static 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
258 static 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
276 static 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
288 static 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
300 static 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
312 static 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
325 static 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
342 static 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
366 static 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
385 static 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
413 static 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
441 static 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
466 static 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
491 static 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
518 static 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
545 static 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
553 static 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
573 static 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
586 static 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
599 static 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
615 static 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
628 static 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
641 static 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
659 static 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
677 static 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
698 static 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
718 static 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
739 static 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
760 static 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
803 static struct kunit_suite list_test_module = {
804 .name = "list-kunit-test",
805 .test_cases = list_test_cases,
806 };
807
808 struct hlist_test_struct {
809 int data;
810 struct hlist_node list;
811 };
812
813 static 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
841 static 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 */
863 static 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
884 static 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
900 static 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 */
921 static 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() */
945 static 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
960 static 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
976 static 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
990 static 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
1006 static 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
1015 static 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
1028 static 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
1047 static 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
1067 static 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
1090 static 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
1121 static 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
1149 static 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
1176 static 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
1198 static struct kunit_suite hlist_test_module = {
1199 .name = "hlist",
1200 .test_cases = hlist_test_cases,
1201 };
1202
1203
1204 static int node_count;
1205 static struct klist_node *last_node;
1206
1207 static void check_node(struct klist_node *node_ptr)
1208 {
1209 node_count++;
1210 last_node = node_ptr;
1211 }
1212
1213 static void check_delete_node(struct klist_node *node_ptr)
1214 {
1215 node_count--;
1216 last_node = node_ptr;
1217 }
1218
1219 static void klist_test_add_tail(struct kunit *test)
1220 {
1221 struct klist_node a, b;
1222 struct klist mylist;
1223 struct klist_iter i;
1224
1225 node_count = 0;
1226 klist_init(&mylist, &check_node, NULL);
1227
1228 klist_add_tail(&a, &mylist);
1229 KUNIT_EXPECT_EQ(test, node_count, 1);
1230 KUNIT_EXPECT_PTR_EQ(test, last_node, &a);
1231
1232 klist_add_tail(&b, &mylist);
1233 KUNIT_EXPECT_EQ(test, node_count, 2);
1234 KUNIT_EXPECT_PTR_EQ(test, last_node, &b);
1235
1236 /* should be [list] -> a -> b */
1237 klist_iter_init(&mylist, &i);
1238
1239 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
1240 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
1241 KUNIT_EXPECT_NULL(test, klist_next(&i));
1242
1243 klist_iter_exit(&i);
1244
1245 }
1246
1247 static void klist_test_add_head(struct kunit *test)
1248 {
1249 struct klist_node a, b;
1250 struct klist mylist;
1251 struct klist_iter i;
1252
1253 node_count = 0;
1254 klist_init(&mylist, &check_node, NULL);
1255
1256 klist_add_head(&a, &mylist);
1257 KUNIT_EXPECT_EQ(test, node_count, 1);
1258 KUNIT_EXPECT_PTR_EQ(test, last_node, &a);
1259
1260 klist_add_head(&b, &mylist);
1261 KUNIT_EXPECT_EQ(test, node_count, 2);
1262 KUNIT_EXPECT_PTR_EQ(test, last_node, &b);
1263
1264 /* should be [list] -> b -> a */
1265 klist_iter_init(&mylist, &i);
1266
1267 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
1268 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
1269 KUNIT_EXPECT_NULL(test, klist_next(&i));
1270
1271 klist_iter_exit(&i);
1272
1273 }
1274
1275 static void klist_test_add_behind(struct kunit *test)
1276 {
1277 struct klist_node a, b, c, d;
1278 struct klist mylist;
1279 struct klist_iter i;
1280
1281 node_count = 0;
1282 klist_init(&mylist, &check_node, NULL);
1283
1284 klist_add_head(&a, &mylist);
1285 klist_add_head(&b, &mylist);
1286
1287 klist_add_behind(&c, &a);
1288 KUNIT_EXPECT_EQ(test, node_count, 3);
1289 KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
1290
1291 klist_add_behind(&d, &b);
1292 KUNIT_EXPECT_EQ(test, node_count, 4);
1293 KUNIT_EXPECT_PTR_EQ(test, last_node, &d);
1294
1295 klist_iter_init(&mylist, &i);
1296
1297 /* should be [list] -> b -> d -> a -> c*/
1298 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
1299 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d);
1300 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
1301 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c);
1302 KUNIT_EXPECT_NULL(test, klist_next(&i));
1303
1304 klist_iter_exit(&i);
1305
1306 }
1307
1308 static void klist_test_add_before(struct kunit *test)
1309 {
1310 struct klist_node a, b, c, d;
1311 struct klist mylist;
1312 struct klist_iter i;
1313
1314 node_count = 0;
1315 klist_init(&mylist, &check_node, NULL);
1316
1317 klist_add_head(&a, &mylist);
1318 klist_add_head(&b, &mylist);
1319 klist_add_before(&c, &a);
1320 KUNIT_EXPECT_EQ(test, node_count, 3);
1321 KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
1322
1323 klist_add_before(&d, &b);
1324 KUNIT_EXPECT_EQ(test, node_count, 4);
1325 KUNIT_EXPECT_PTR_EQ(test, last_node, &d);
1326
1327 klist_iter_init(&mylist, &i);
1328
1329 /* should be [list] -> b -> d -> a -> c*/
1330 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d);
1331 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
1332 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c);
1333 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
1334 KUNIT_EXPECT_NULL(test, klist_next(&i));
1335
1336 klist_iter_exit(&i);
1337
1338 }
1339
1340 /*
1341 * Verify that klist_del() delays the deletion of a node until there
1342 * are no other references to it
1343 */
1344 static void klist_test_del_refcount_greater_than_zero(struct kunit *test)
1345 {
1346 struct klist_node a, b, c, d;
1347 struct klist mylist;
1348 struct klist_iter i;
1349
1350 node_count = 0;
1351 klist_init(&mylist, &check_node, &check_delete_node);
1352
1353 /* Add nodes a,b,c,d to the list*/
1354 klist_add_tail(&a, &mylist);
1355 klist_add_tail(&b, &mylist);
1356 klist_add_tail(&c, &mylist);
1357 klist_add_tail(&d, &mylist);
1358
1359 klist_iter_init(&mylist, &i);
1360
1361 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
1362 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
1363 /* Advance the iterator to point to node c*/
1364 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &c);
1365
1366 /* Try to delete node c while there is a reference to it*/
1367 klist_del(&c);
1368
1369 /*
1370 * Verify that node c is still attached to the list even after being
1371 * deleted. Since the iterator still points to c, the reference count is not
1372 * decreased to 0
1373 */
1374 KUNIT_EXPECT_TRUE(test, klist_node_attached(&c));
1375
1376 /* Check that node c has not been removed yet*/
1377 KUNIT_EXPECT_EQ(test, node_count, 4);
1378 KUNIT_EXPECT_PTR_EQ(test, last_node, &d);
1379
1380 klist_iter_exit(&i);
1381
1382 /*
1383 * Since the iterator is no longer pointing to node c, node c is removed
1384 * from the list
1385 */
1386 KUNIT_EXPECT_EQ(test, node_count, 3);
1387 KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
1388
1389 }
1390
1391 /*
1392 * Verify that klist_del() deletes a node immediately when there are no
1393 * other references to it.
1394 */
1395 static void klist_test_del_refcount_zero(struct kunit *test)
1396 {
1397 struct klist_node a, b, c, d;
1398 struct klist mylist;
1399 struct klist_iter i;
1400
1401 node_count = 0;
1402 klist_init(&mylist, &check_node, &check_delete_node);
1403
1404 /* Add nodes a,b,c,d to the list*/
1405 klist_add_tail(&a, &mylist);
1406 klist_add_tail(&b, &mylist);
1407 klist_add_tail(&c, &mylist);
1408 klist_add_tail(&d, &mylist);
1409 /* Delete node c*/
1410 klist_del(&c);
1411
1412 /* Check that node c is deleted from the list*/
1413 KUNIT_EXPECT_EQ(test, node_count, 3);
1414 KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
1415
1416 /* Should be [list] -> a -> b -> d*/
1417 klist_iter_init(&mylist, &i);
1418
1419 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
1420 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
1421 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d);
1422 KUNIT_EXPECT_NULL(test, klist_next(&i));
1423
1424 klist_iter_exit(&i);
1425
1426 }
1427
1428 static void klist_test_remove(struct kunit *test)
1429 {
1430 /* This test doesn't check correctness under concurrent access */
1431 struct klist_node a, b, c, d;
1432 struct klist mylist;
1433 struct klist_iter i;
1434
1435 node_count = 0;
1436 klist_init(&mylist, &check_node, &check_delete_node);
1437
1438 /* Add nodes a,b,c,d to the list*/
1439 klist_add_tail(&a, &mylist);
1440 klist_add_tail(&b, &mylist);
1441 klist_add_tail(&c, &mylist);
1442 klist_add_tail(&d, &mylist);
1443 /* Delete node c*/
1444 klist_remove(&c);
1445
1446 /* Check the nodes in the list*/
1447 KUNIT_EXPECT_EQ(test, node_count, 3);
1448 KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
1449
1450 /* should be [list] -> a -> b -> d*/
1451 klist_iter_init(&mylist, &i);
1452
1453 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &a);
1454 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &b);
1455 KUNIT_EXPECT_PTR_EQ(test, klist_next(&i), &d);
1456 KUNIT_EXPECT_NULL(test, klist_next(&i));
1457
1458 klist_iter_exit(&i);
1459
1460 }
1461
1462 static void klist_test_node_attached(struct kunit *test)
1463 {
1464 struct klist_node a = {};
1465 struct klist mylist;
1466
1467 klist_init(&mylist, NULL, NULL);
1468
1469 KUNIT_EXPECT_FALSE(test, klist_node_attached(&a));
1470 klist_add_head(&a, &mylist);
1471 KUNIT_EXPECT_TRUE(test, klist_node_attached(&a));
1472 klist_del(&a);
1473 KUNIT_EXPECT_FALSE(test, klist_node_attached(&a));
1474
1475 }
1476
1477 static struct kunit_case klist_test_cases[] = {
1478 KUNIT_CASE(klist_test_add_tail),
1479 KUNIT_CASE(klist_test_add_head),
1480 KUNIT_CASE(klist_test_add_behind),
1481 KUNIT_CASE(klist_test_add_before),
1482 KUNIT_CASE(klist_test_del_refcount_greater_than_zero),
1483 KUNIT_CASE(klist_test_del_refcount_zero),
1484 KUNIT_CASE(klist_test_remove),
1485 KUNIT_CASE(klist_test_node_attached),
1486 {},
1487 };
1488
1489 static struct kunit_suite klist_test_module = {
1490 .name = "klist",
1491 .test_cases = klist_test_cases,
1492 };
1493
1494 kunit_test_suites(&list_test_module, &hlist_test_module, &klist_test_module);
1495
1496 MODULE_DESCRIPTION("KUnit test for the Kernel Linked-list structures");
1497 MODULE_LICENSE("GPL v2");
1498
Linux® is a registered trademark of Linus Torvalds in the United States and other countries.
TOMOYO® is a registered trademark of NTT DATA CORPORATION.