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(list: &list2);
28
29 list4 = kzalloc(size: sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL);
30 INIT_LIST_HEAD(list: list4);
31
32 list5 = kmalloc(size: sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL);
33 memset(list5, 0xFF, sizeof(*list5));
34 INIT_LIST_HEAD(list: 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(objp: list4);
44 kfree(objp: 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(new: &a, head: &list);
53 list_add(new: &b, head: &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(new: &a, head: &list);
67 list_add_tail(new: &b, head: &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(new: &a, head: &list);
81 list_add_tail(new: &b, head: &list);
82
83 /* before: [list] -> a -> b */
84 list_del(entry: &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(new: &a_old, head: &list);
97 list_add_tail(new: &b, head: &list);
98
99 /* before: [list] -> a_old -> b */
100 list_replace(old: &a_old, new: &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(new: &a_old, head: &list);
113 list_add_tail(new: &b, head: &list);
114
115 /* before: [list] -> a_old -> b */
116 list_replace_init(old: &a_old, new: &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(new: &a, head: &list);
132 list_add_tail(new: &b, head: &list);
133
134 /* before: [list] -> a -> b */
135 list_swap(entry1: &a, entry2: &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(new: &a, head: &list);
154 list_add_tail(new: &b, head: &list);
155
156 /* before: [list] -> a -> b */
157 list_del_init(entry: &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(new: &a, head: &list);
174 list_add_tail(new: &b, head: &list);
175
176 /* before: [list] -> a -> b */
177 list_del_init_careful(entry: &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(new: &a, head: &list1);
192 list_add_tail(new: &b, head: &list2);
193
194 /* before: [list1] -> a, [list2] -> b */
195 list_move(list: &a, head: &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(new: &a, head: &list1);
211 list_add_tail(new: &b, head: &list2);
212
213 /* before: [list1] -> a, [list2] -> b */
214 list_move_tail(list: &a, head: &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(new: &x, head: &list1);
234 list_add_tail(new: &y, head: &list1);
235
236 list_add_tail(new: &a, head: &list2);
237 list_add_tail(new: &b, head: &list2);
238 list_add_tail(new: &c, head: &list2);
239 list_add_tail(new: &d, head: &list2);
240
241 /* before: [list1] -> x -> y, [list2] -> a -> b -> c -> d */
242 list_bulk_move_tail(head: &y, first: &b, last: &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(list: &a);
264 INIT_LIST_HEAD(list: &c);
265 list_add_tail(new: &b, head: &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(new: &a, head: &list);
282 list_add_tail(new: &b, head: &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(new: &a, head: &list);
294 list_add_tail(new: &b, head: &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(new: &a, head: &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(new: &a, head: &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(new: &a, head: &list);
331 list_add_tail(new: &b, head: &list);
332
333 /* before: [list] -> a -> b */
334 list_rotate_left(head: &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(new: &a, head: &list);
351 list_add_tail(new: &b, head: &list);
352 list_add_tail(new: &c, head: &list);
353 list_add_tail(new: &d, head: &list);
354
355 /* before: [list] -> a -> b -> c -> d */
356 list_rotate_to_front(list: &c, head: &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(new: &a, head: &list);
375
376 /* [list] -> a */
377 KUNIT_EXPECT_TRUE(test, list_is_singular(&list));
378
379 list_add_tail(new: &b, head: &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(new: &entries[0], head: &list1);
393 list_add_tail(new: &entries[1], head: &list1);
394 list_add_tail(new: &entries[2], head: &list1);
395
396 /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */
397 list_cut_position(list: &list2, head: &list1, entry: &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(new: &entries[0], head: &list1);
421 list_add_tail(new: &entries[1], head: &list1);
422 list_add_tail(new: &entries[2], head: &list1);
423
424 /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */
425 list_cut_before(list: &list2, head: &list1, entry: &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(new: &entries[0], head: &list1);
449 list_add_tail(new: &entries[1], head: &list1);
450 list_add_tail(new: &entries[2], head: &list2);
451 list_add_tail(new: &entries[3], head: &list2);
452 list_add_tail(new: &entries[4], head: &list1);
453
454 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
455 list_splice(list: &list2, head: &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(new: &entries[0], head: &list1);
474 list_add_tail(new: &entries[1], head: &list1);
475 list_add_tail(new: &entries[2], head: &list2);
476 list_add_tail(new: &entries[3], head: &list2);
477 list_add_tail(new: &entries[4], head: &list1);
478
479 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
480 list_splice_tail(list: &list2, head: &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(new: &entries[0], head: &list1);
499 list_add_tail(new: &entries[1], head: &list1);
500 list_add_tail(new: &entries[2], head: &list2);
501 list_add_tail(new: &entries[3], head: &list2);
502 list_add_tail(new: &entries[4], head: &list1);
503
504 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
505 list_splice_init(list: &list2, head: &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(new: &entries[0], head: &list1);
526 list_add_tail(new: &entries[1], head: &list1);
527 list_add_tail(new: &entries[2], head: &list2);
528 list_add_tail(new: &entries[3], head: &list2);
529 list_add_tail(new: &entries[4], head: &list1);
530
531 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
532 list_splice_tail_init(list: &list2, head: &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(list: &test_struct1.list);
558 INIT_LIST_HEAD(list: &test_struct3.list);
559
560 list_add_tail(new: &test_struct2.list, head: &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(new: &test_struct1.list, head: &list);
579 list_add_tail(new: &test_struct2.list, head: &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(new: &test_struct1.list, head: &list);
592 list_add_tail(new: &test_struct2.list, head: &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(new: &test_struct1.list, head: &list);
608 list_add_tail(new: &test_struct2.list, head: &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(new: &test_struct1.list, head: &list);
621 list_add_tail(new: &test_struct2.list, head: &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(new: &test_struct1.list, head: &list);
634 list_add_tail(new: &test_struct2.list, head: &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(new: &entries[0], head: &list);
648 list_add_tail(new: &entries[1], head: &list);
649 list_add_tail(new: &entries[2], head: &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(new: &entries[0], head: &list);
666 list_add_tail(new: &entries[1], head: &list);
667 list_add_tail(new: &entries[2], head: &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(new: &entries[0], head: &list);
685 list_add_tail(new: &entries[1], head: &list);
686 list_add_tail(new: &entries[2], head: &list);
687
688 list_for_each_safe(cur, n, &list) {
689 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
690 list_del(entry: &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(new: &entries[0], head: &list);
705 list_add_tail(new: &entries[1], head: &list);
706 list_add_tail(new: &entries[2], head: &list);
707
708 list_for_each_prev_safe(cur, n, &list) {
709 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
710 list_del(entry: &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(new: &entries[i].list, head: &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(new: &entries[i].list, head: &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(size: sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL);
825 INIT_HLIST_HEAD(list4);
826
827 list5 = kmalloc(size: 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(objp: list4);
838 kfree(objp: 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(h: &a);
847
848 /* is unhashed by default */
849 KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a));
850
851 hlist_add_head(n: &a, h: &list);
852
853 /* is hashed once added to list */
854 KUNIT_EXPECT_FALSE(test, hlist_unhashed(&a));
855
856 hlist_del_init(n: &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(h: &a);
869
870 /* is unhashed by default */
871 KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a));
872
873 hlist_add_head(n: &a, h: &list);
874
875 /* is hashed once added to list */
876 KUNIT_EXPECT_FALSE(test, hlist_unhashed_lockless(&a));
877
878 hlist_del_init(n: &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(n: &a, h: &list);
890 hlist_add_behind(n: &b, prev: &a);
891
892 /* before: [list] -> a -> b */
893 hlist_del(n: &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(n: &a, h: &list);
906 hlist_add_behind(n: &b, prev: &a);
907
908 /* before: [list] -> a -> b */
909 hlist_del_init(n: &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(n: &a, h: &list);
927 hlist_add_head(n: &b, h: &list);
928 hlist_add_before(n: &c, next: &a);
929 hlist_add_behind(n: &d, prev: &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(h: &a);
950
951 /* not fake after init */
952 KUNIT_EXPECT_FALSE(test, hlist_fake(&a));
953
954 hlist_add_fake(n: &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(h: &a);
966 KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list));
967
968 hlist_add_head(n: &a, h: &list);
969 KUNIT_EXPECT_TRUE(test, hlist_is_singular_node(&a, &list));
970
971 hlist_add_head(n: &b, h: &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(n: &a, h: &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(n: &a, h: &list1);
997
998 KUNIT_EXPECT_FALSE(test, hlist_empty(&list1));
999 KUNIT_EXPECT_TRUE(test, hlist_empty(&list2));
1000 hlist_move_list(old: &list1, new: &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(n: &entries[0], h: &list);
1035 hlist_add_behind(n: &entries[1], prev: &entries[0]);
1036 hlist_add_behind(n: &entries[2], prev: &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(n: &entries[0], h: &list);
1054 hlist_add_behind(n: &entries[1], prev: &entries[0]);
1055 hlist_add_behind(n: &entries[2], prev: &entries[1]);
1056
1057 hlist_for_each_safe(cur, n, &list) {
1058 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
1059 hlist_del(n: &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(n: &entries[0].list, h: &list);
1075 for (i = 1; i < 5; ++i) {
1076 entries[i].data = i;
1077 hlist_add_behind(n: &entries[i].list, prev: &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(n: &entries[0].list, h: &list);
1098 for (i = 1; i < 5; ++i) {
1099 entries[i].data = i;
1100 hlist_add_behind(n: &entries[i].list, prev: &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(n: &entries[0].list, h: &list);
1129 for (i = 1; i < 5; ++i) {
1130 entries[i].data = i;
1131 hlist_add_behind(n: &entries[i].list, prev: &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(n: &entries[0].list, h: &list);
1158 for (i = 1; i < 5; ++i) {
1159 entries[i].data = i;
1160 hlist_add_behind(n: &entries[i].list, prev: &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(n: &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(k: &mylist, get: &check_node, NULL);
1233
1234 klist_add_tail(n: &a, k: &mylist);
1235 KUNIT_EXPECT_EQ(test, node_count, 1);
1236 KUNIT_EXPECT_PTR_EQ(test, last_node, &a);
1237
1238 klist_add_tail(n: &b, k: &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(k: &mylist, i: &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: &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(k: &mylist, get: &check_node, NULL);
1261
1262 klist_add_head(n: &a, k: &mylist);
1263 KUNIT_EXPECT_EQ(test, node_count, 1);
1264 KUNIT_EXPECT_PTR_EQ(test, last_node, &a);
1265
1266 klist_add_head(n: &b, k: &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(k: &mylist, i: &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: &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(k: &mylist, get: &check_node, NULL);
1289
1290 klist_add_head(n: &a, k: &mylist);
1291 klist_add_head(n: &b, k: &mylist);
1292
1293 klist_add_behind(n: &c, pos: &a);
1294 KUNIT_EXPECT_EQ(test, node_count, 3);
1295 KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
1296
1297 klist_add_behind(n: &d, pos: &b);
1298 KUNIT_EXPECT_EQ(test, node_count, 4);
1299 KUNIT_EXPECT_PTR_EQ(test, last_node, &d);
1300
1301 klist_iter_init(k: &mylist, i: &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: &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(k: &mylist, get: &check_node, NULL);
1322
1323 klist_add_head(n: &a, k: &mylist);
1324 klist_add_head(n: &b, k: &mylist);
1325 klist_add_before(n: &c, pos: &a);
1326 KUNIT_EXPECT_EQ(test, node_count, 3);
1327 KUNIT_EXPECT_PTR_EQ(test, last_node, &c);
1328
1329 klist_add_before(n: &d, pos: &b);
1330 KUNIT_EXPECT_EQ(test, node_count, 4);
1331 KUNIT_EXPECT_PTR_EQ(test, last_node, &d);
1332
1333 klist_iter_init(k: &mylist, i: &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: &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(k: &mylist, get: &check_node, put: &check_delete_node);
1358
1359 /* Add nodes a,b,c,d to the list*/
1360 klist_add_tail(n: &a, k: &mylist);
1361 klist_add_tail(n: &b, k: &mylist);
1362 klist_add_tail(n: &c, k: &mylist);
1363 klist_add_tail(n: &d, k: &mylist);
1364
1365 klist_iter_init(k: &mylist, i: &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(n: &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: &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(k: &mylist, get: &check_node, put: &check_delete_node);
1409
1410 /* Add nodes a,b,c,d to the list*/
1411 klist_add_tail(n: &a, k: &mylist);
1412 klist_add_tail(n: &b, k: &mylist);
1413 klist_add_tail(n: &c, k: &mylist);
1414 klist_add_tail(n: &d, k: &mylist);
1415 /* Delete node c*/
1416 klist_del(n: &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(k: &mylist, i: &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: &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(k: &mylist, get: &check_node, put: &check_delete_node);
1443
1444 /* Add nodes a,b,c,d to the list*/
1445 klist_add_tail(n: &a, k: &mylist);
1446 klist_add_tail(n: &b, k: &mylist);
1447 klist_add_tail(n: &c, k: &mylist);
1448 klist_add_tail(n: &d, k: &mylist);
1449 /* Delete node c*/
1450 klist_remove(n: &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(k: &mylist, i: &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: &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(k: &mylist, NULL, NULL);
1474
1475 KUNIT_EXPECT_FALSE(test, klist_node_attached(&a));
1476 klist_add_head(n: &a, k: &mylist);
1477 KUNIT_EXPECT_TRUE(test, klist_node_attached(&a));
1478 klist_del(n: &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");
1503

source code of linux/lib/list-test.c