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