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