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
12 struct list_test_struct {
13 int data;
14 struct list_head list;
15 };
16
list_test_list_init(struct kunit * test)17 static void list_test_list_init(struct kunit *test)
18 {
19 /* Test the different ways of initialising a list. */
20 struct list_head list1 = LIST_HEAD_INIT(list1);
21 struct list_head list2;
22 LIST_HEAD(list3);
23 struct list_head *list4;
24 struct list_head *list5;
25
26 INIT_LIST_HEAD(&list2);
27
28 list4 = kzalloc(sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL);
29 INIT_LIST_HEAD(list4);
30
31 list5 = kmalloc(sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL);
32 memset(list5, 0xFF, sizeof(*list5));
33 INIT_LIST_HEAD(list5);
34
35 /* list_empty_careful() checks both next and prev. */
36 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list1));
37 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
38 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list3));
39 KUNIT_EXPECT_TRUE(test, list_empty_careful(list4));
40 KUNIT_EXPECT_TRUE(test, list_empty_careful(list5));
41
42 kfree(list4);
43 kfree(list5);
44 }
45
list_test_list_add(struct kunit * test)46 static void list_test_list_add(struct kunit *test)
47 {
48 struct list_head a, b;
49 LIST_HEAD(list);
50
51 list_add(&a, &list);
52 list_add(&b, &list);
53
54 /* should be [list] -> b -> a */
55 KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
56 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
57 KUNIT_EXPECT_PTR_EQ(test, b.next, &a);
58 }
59
list_test_list_add_tail(struct kunit * test)60 static void list_test_list_add_tail(struct kunit *test)
61 {
62 struct list_head a, b;
63 LIST_HEAD(list);
64
65 list_add_tail(&a, &list);
66 list_add_tail(&b, &list);
67
68 /* should be [list] -> a -> b */
69 KUNIT_EXPECT_PTR_EQ(test, list.next, &a);
70 KUNIT_EXPECT_PTR_EQ(test, a.prev, &list);
71 KUNIT_EXPECT_PTR_EQ(test, a.next, &b);
72 }
73
list_test_list_del(struct kunit * test)74 static void list_test_list_del(struct kunit *test)
75 {
76 struct list_head a, b;
77 LIST_HEAD(list);
78
79 list_add_tail(&a, &list);
80 list_add_tail(&b, &list);
81
82 /* before: [list] -> a -> b */
83 list_del(&a);
84
85 /* now: [list] -> b */
86 KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
87 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
88 }
89
list_test_list_replace(struct kunit * test)90 static void list_test_list_replace(struct kunit *test)
91 {
92 struct list_head a_old, a_new, b;
93 LIST_HEAD(list);
94
95 list_add_tail(&a_old, &list);
96 list_add_tail(&b, &list);
97
98 /* before: [list] -> a_old -> b */
99 list_replace(&a_old, &a_new);
100
101 /* now: [list] -> a_new -> b */
102 KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new);
103 KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new);
104 }
105
list_test_list_replace_init(struct kunit * test)106 static void list_test_list_replace_init(struct kunit *test)
107 {
108 struct list_head a_old, a_new, b;
109 LIST_HEAD(list);
110
111 list_add_tail(&a_old, &list);
112 list_add_tail(&b, &list);
113
114 /* before: [list] -> a_old -> b */
115 list_replace_init(&a_old, &a_new);
116
117 /* now: [list] -> a_new -> b */
118 KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new);
119 KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new);
120
121 /* check a_old is empty (initialized) */
122 KUNIT_EXPECT_TRUE(test, list_empty_careful(&a_old));
123 }
124
list_test_list_swap(struct kunit * test)125 static void list_test_list_swap(struct kunit *test)
126 {
127 struct list_head a, b;
128 LIST_HEAD(list);
129
130 list_add_tail(&a, &list);
131 list_add_tail(&b, &list);
132
133 /* before: [list] -> a -> b */
134 list_swap(&a, &b);
135
136 /* after: [list] -> b -> a */
137 KUNIT_EXPECT_PTR_EQ(test, &b, list.next);
138 KUNIT_EXPECT_PTR_EQ(test, &a, list.prev);
139
140 KUNIT_EXPECT_PTR_EQ(test, &a, b.next);
141 KUNIT_EXPECT_PTR_EQ(test, &list, b.prev);
142
143 KUNIT_EXPECT_PTR_EQ(test, &list, a.next);
144 KUNIT_EXPECT_PTR_EQ(test, &b, a.prev);
145 }
146
list_test_list_del_init(struct kunit * test)147 static void list_test_list_del_init(struct kunit *test)
148 {
149 struct list_head a, b;
150 LIST_HEAD(list);
151
152 list_add_tail(&a, &list);
153 list_add_tail(&b, &list);
154
155 /* before: [list] -> a -> b */
156 list_del_init(&a);
157 /* after: [list] -> b, a initialised */
158
159 KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
160 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
161 KUNIT_EXPECT_TRUE(test, list_empty_careful(&a));
162 }
163
list_test_list_del_init_careful(struct kunit * test)164 static void list_test_list_del_init_careful(struct kunit *test)
165 {
166 /* NOTE: This test only checks the behaviour of this function in
167 * isolation. It does not verify memory model guarantees.
168 */
169 struct list_head a, b;
170 LIST_HEAD(list);
171
172 list_add_tail(&a, &list);
173 list_add_tail(&b, &list);
174
175 /* before: [list] -> a -> b */
176 list_del_init_careful(&a);
177 /* after: [list] -> b, a initialised */
178
179 KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
180 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
181 KUNIT_EXPECT_TRUE(test, list_empty_careful(&a));
182 }
183
list_test_list_move(struct kunit * test)184 static void list_test_list_move(struct kunit *test)
185 {
186 struct list_head a, b;
187 LIST_HEAD(list1);
188 LIST_HEAD(list2);
189
190 list_add_tail(&a, &list1);
191 list_add_tail(&b, &list2);
192
193 /* before: [list1] -> a, [list2] -> b */
194 list_move(&a, &list2);
195 /* after: [list1] empty, [list2] -> a -> b */
196
197 KUNIT_EXPECT_TRUE(test, list_empty(&list1));
198
199 KUNIT_EXPECT_PTR_EQ(test, &a, list2.next);
200 KUNIT_EXPECT_PTR_EQ(test, &b, a.next);
201 }
202
list_test_list_move_tail(struct kunit * test)203 static void list_test_list_move_tail(struct kunit *test)
204 {
205 struct list_head a, b;
206 LIST_HEAD(list1);
207 LIST_HEAD(list2);
208
209 list_add_tail(&a, &list1);
210 list_add_tail(&b, &list2);
211
212 /* before: [list1] -> a, [list2] -> b */
213 list_move_tail(&a, &list2);
214 /* after: [list1] empty, [list2] -> b -> a */
215
216 KUNIT_EXPECT_TRUE(test, list_empty(&list1));
217
218 KUNIT_EXPECT_PTR_EQ(test, &b, list2.next);
219 KUNIT_EXPECT_PTR_EQ(test, &a, b.next);
220 }
221
list_test_list_bulk_move_tail(struct kunit * test)222 static void list_test_list_bulk_move_tail(struct kunit *test)
223 {
224 struct list_head a, b, c, d, x, y;
225 struct list_head *list1_values[] = { &x, &b, &c, &y };
226 struct list_head *list2_values[] = { &a, &d };
227 struct list_head *ptr;
228 LIST_HEAD(list1);
229 LIST_HEAD(list2);
230 int i = 0;
231
232 list_add_tail(&x, &list1);
233 list_add_tail(&y, &list1);
234
235 list_add_tail(&a, &list2);
236 list_add_tail(&b, &list2);
237 list_add_tail(&c, &list2);
238 list_add_tail(&d, &list2);
239
240 /* before: [list1] -> x -> y, [list2] -> a -> b -> c -> d */
241 list_bulk_move_tail(&y, &b, &c);
242 /* after: [list1] -> x -> b -> c -> y, [list2] -> a -> d */
243
244 list_for_each(ptr, &list1) {
245 KUNIT_EXPECT_PTR_EQ(test, ptr, list1_values[i]);
246 i++;
247 }
248 KUNIT_EXPECT_EQ(test, i, 4);
249 i = 0;
250 list_for_each(ptr, &list2) {
251 KUNIT_EXPECT_PTR_EQ(test, ptr, list2_values[i]);
252 i++;
253 }
254 KUNIT_EXPECT_EQ(test, i, 2);
255 }
256
list_test_list_is_head(struct kunit * test)257 static void list_test_list_is_head(struct kunit *test)
258 {
259 struct list_head a, b, c;
260
261 /* Two lists: [a] -> b, [c] */
262 INIT_LIST_HEAD(&a);
263 INIT_LIST_HEAD(&c);
264 list_add_tail(&b, &a);
265
266 KUNIT_EXPECT_TRUE_MSG(test, list_is_head(&a, &a),
267 "Head element of same list");
268 KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &b),
269 "Non-head element of same list");
270 KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &c),
271 "Head element of different list");
272 }
273
274
list_test_list_is_first(struct kunit * test)275 static void list_test_list_is_first(struct kunit *test)
276 {
277 struct list_head a, b;
278 LIST_HEAD(list);
279
280 list_add_tail(&a, &list);
281 list_add_tail(&b, &list);
282
283 KUNIT_EXPECT_TRUE(test, list_is_first(&a, &list));
284 KUNIT_EXPECT_FALSE(test, list_is_first(&b, &list));
285 }
286
list_test_list_is_last(struct kunit * test)287 static void list_test_list_is_last(struct kunit *test)
288 {
289 struct list_head a, b;
290 LIST_HEAD(list);
291
292 list_add_tail(&a, &list);
293 list_add_tail(&b, &list);
294
295 KUNIT_EXPECT_FALSE(test, list_is_last(&a, &list));
296 KUNIT_EXPECT_TRUE(test, list_is_last(&b, &list));
297 }
298
list_test_list_empty(struct kunit * test)299 static void list_test_list_empty(struct kunit *test)
300 {
301 struct list_head a;
302 LIST_HEAD(list1);
303 LIST_HEAD(list2);
304
305 list_add_tail(&a, &list1);
306
307 KUNIT_EXPECT_FALSE(test, list_empty(&list1));
308 KUNIT_EXPECT_TRUE(test, list_empty(&list2));
309 }
310
list_test_list_empty_careful(struct kunit * test)311 static void list_test_list_empty_careful(struct kunit *test)
312 {
313 /* This test doesn't check correctness under concurrent access */
314 struct list_head a;
315 LIST_HEAD(list1);
316 LIST_HEAD(list2);
317
318 list_add_tail(&a, &list1);
319
320 KUNIT_EXPECT_FALSE(test, list_empty_careful(&list1));
321 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
322 }
323
list_test_list_rotate_left(struct kunit * test)324 static void list_test_list_rotate_left(struct kunit *test)
325 {
326 struct list_head a, b;
327 LIST_HEAD(list);
328
329 list_add_tail(&a, &list);
330 list_add_tail(&b, &list);
331
332 /* before: [list] -> a -> b */
333 list_rotate_left(&list);
334 /* after: [list] -> b -> a */
335
336 KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
337 KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
338 KUNIT_EXPECT_PTR_EQ(test, b.next, &a);
339 }
340
list_test_list_rotate_to_front(struct kunit * test)341 static void list_test_list_rotate_to_front(struct kunit *test)
342 {
343 struct list_head a, b, c, d;
344 struct list_head *list_values[] = { &c, &d, &a, &b };
345 struct list_head *ptr;
346 LIST_HEAD(list);
347 int i = 0;
348
349 list_add_tail(&a, &list);
350 list_add_tail(&b, &list);
351 list_add_tail(&c, &list);
352 list_add_tail(&d, &list);
353
354 /* before: [list] -> a -> b -> c -> d */
355 list_rotate_to_front(&c, &list);
356 /* after: [list] -> c -> d -> a -> b */
357
358 list_for_each(ptr, &list) {
359 KUNIT_EXPECT_PTR_EQ(test, ptr, list_values[i]);
360 i++;
361 }
362 KUNIT_EXPECT_EQ(test, i, 4);
363 }
364
list_test_list_is_singular(struct kunit * test)365 static void list_test_list_is_singular(struct kunit *test)
366 {
367 struct list_head a, b;
368 LIST_HEAD(list);
369
370 /* [list] empty */
371 KUNIT_EXPECT_FALSE(test, list_is_singular(&list));
372
373 list_add_tail(&a, &list);
374
375 /* [list] -> a */
376 KUNIT_EXPECT_TRUE(test, list_is_singular(&list));
377
378 list_add_tail(&b, &list);
379
380 /* [list] -> a -> b */
381 KUNIT_EXPECT_FALSE(test, list_is_singular(&list));
382 }
383
list_test_list_cut_position(struct kunit * test)384 static void list_test_list_cut_position(struct kunit *test)
385 {
386 struct list_head entries[3], *cur;
387 LIST_HEAD(list1);
388 LIST_HEAD(list2);
389 int i = 0;
390
391 list_add_tail(&entries[0], &list1);
392 list_add_tail(&entries[1], &list1);
393 list_add_tail(&entries[2], &list1);
394
395 /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */
396 list_cut_position(&list2, &list1, &entries[1]);
397 /* after: [list2] -> entries[0] -> entries[1], [list1] -> entries[2] */
398
399 list_for_each(cur, &list2) {
400 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
401 i++;
402 }
403
404 KUNIT_EXPECT_EQ(test, i, 2);
405
406 list_for_each(cur, &list1) {
407 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
408 i++;
409 }
410 }
411
list_test_list_cut_before(struct kunit * test)412 static void list_test_list_cut_before(struct kunit *test)
413 {
414 struct list_head entries[3], *cur;
415 LIST_HEAD(list1);
416 LIST_HEAD(list2);
417 int i = 0;
418
419 list_add_tail(&entries[0], &list1);
420 list_add_tail(&entries[1], &list1);
421 list_add_tail(&entries[2], &list1);
422
423 /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */
424 list_cut_before(&list2, &list1, &entries[1]);
425 /* after: [list2] -> entries[0], [list1] -> entries[1] -> entries[2] */
426
427 list_for_each(cur, &list2) {
428 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
429 i++;
430 }
431
432 KUNIT_EXPECT_EQ(test, i, 1);
433
434 list_for_each(cur, &list1) {
435 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
436 i++;
437 }
438 }
439
list_test_list_splice(struct kunit * test)440 static void list_test_list_splice(struct kunit *test)
441 {
442 struct list_head entries[5], *cur;
443 LIST_HEAD(list1);
444 LIST_HEAD(list2);
445 int i = 0;
446
447 list_add_tail(&entries[0], &list1);
448 list_add_tail(&entries[1], &list1);
449 list_add_tail(&entries[2], &list2);
450 list_add_tail(&entries[3], &list2);
451 list_add_tail(&entries[4], &list1);
452
453 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
454 list_splice(&list2, &entries[1]);
455 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */
456
457 list_for_each(cur, &list1) {
458 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
459 i++;
460 }
461
462 KUNIT_EXPECT_EQ(test, i, 5);
463 }
464
list_test_list_splice_tail(struct kunit * test)465 static void list_test_list_splice_tail(struct kunit *test)
466 {
467 struct list_head entries[5], *cur;
468 LIST_HEAD(list1);
469 LIST_HEAD(list2);
470 int i = 0;
471
472 list_add_tail(&entries[0], &list1);
473 list_add_tail(&entries[1], &list1);
474 list_add_tail(&entries[2], &list2);
475 list_add_tail(&entries[3], &list2);
476 list_add_tail(&entries[4], &list1);
477
478 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
479 list_splice_tail(&list2, &entries[4]);
480 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */
481
482 list_for_each(cur, &list1) {
483 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
484 i++;
485 }
486
487 KUNIT_EXPECT_EQ(test, i, 5);
488 }
489
list_test_list_splice_init(struct kunit * test)490 static void list_test_list_splice_init(struct kunit *test)
491 {
492 struct list_head entries[5], *cur;
493 LIST_HEAD(list1);
494 LIST_HEAD(list2);
495 int i = 0;
496
497 list_add_tail(&entries[0], &list1);
498 list_add_tail(&entries[1], &list1);
499 list_add_tail(&entries[2], &list2);
500 list_add_tail(&entries[3], &list2);
501 list_add_tail(&entries[4], &list1);
502
503 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
504 list_splice_init(&list2, &entries[1]);
505 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */
506
507 list_for_each(cur, &list1) {
508 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
509 i++;
510 }
511
512 KUNIT_EXPECT_EQ(test, i, 5);
513
514 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
515 }
516
list_test_list_splice_tail_init(struct kunit * test)517 static void list_test_list_splice_tail_init(struct kunit *test)
518 {
519 struct list_head entries[5], *cur;
520 LIST_HEAD(list1);
521 LIST_HEAD(list2);
522 int i = 0;
523
524 list_add_tail(&entries[0], &list1);
525 list_add_tail(&entries[1], &list1);
526 list_add_tail(&entries[2], &list2);
527 list_add_tail(&entries[3], &list2);
528 list_add_tail(&entries[4], &list1);
529
530 /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
531 list_splice_tail_init(&list2, &entries[4]);
532 /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */
533
534 list_for_each(cur, &list1) {
535 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
536 i++;
537 }
538
539 KUNIT_EXPECT_EQ(test, i, 5);
540
541 KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
542 }
543
list_test_list_entry(struct kunit * test)544 static void list_test_list_entry(struct kunit *test)
545 {
546 struct list_test_struct test_struct;
547
548 KUNIT_EXPECT_PTR_EQ(test, &test_struct, list_entry(&(test_struct.list),
549 struct list_test_struct, list));
550 }
551
list_test_list_entry_is_head(struct kunit * test)552 static void list_test_list_entry_is_head(struct kunit *test)
553 {
554 struct list_test_struct test_struct1, test_struct2, test_struct3;
555
556 INIT_LIST_HEAD(&test_struct1.list);
557 INIT_LIST_HEAD(&test_struct3.list);
558
559 list_add_tail(&test_struct2.list, &test_struct1.list);
560
561 KUNIT_EXPECT_TRUE_MSG(test,
562 list_entry_is_head((&test_struct1), &test_struct1.list, list),
563 "Head element of same list");
564 KUNIT_EXPECT_FALSE_MSG(test,
565 list_entry_is_head((&test_struct2), &test_struct1.list, list),
566 "Non-head element of same list");
567 KUNIT_EXPECT_FALSE_MSG(test,
568 list_entry_is_head((&test_struct3), &test_struct1.list, list),
569 "Head element of different list");
570 }
571
list_test_list_first_entry(struct kunit * test)572 static void list_test_list_first_entry(struct kunit *test)
573 {
574 struct list_test_struct test_struct1, test_struct2;
575 LIST_HEAD(list);
576
577 list_add_tail(&test_struct1.list, &list);
578 list_add_tail(&test_struct2.list, &list);
579
580
581 KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_first_entry(&list,
582 struct list_test_struct, list));
583 }
584
list_test_list_last_entry(struct kunit * test)585 static void list_test_list_last_entry(struct kunit *test)
586 {
587 struct list_test_struct test_struct1, test_struct2;
588 LIST_HEAD(list);
589
590 list_add_tail(&test_struct1.list, &list);
591 list_add_tail(&test_struct2.list, &list);
592
593
594 KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_last_entry(&list,
595 struct list_test_struct, list));
596 }
597
list_test_list_first_entry_or_null(struct kunit * test)598 static void list_test_list_first_entry_or_null(struct kunit *test)
599 {
600 struct list_test_struct test_struct1, test_struct2;
601 LIST_HEAD(list);
602
603 KUNIT_EXPECT_FALSE(test, list_first_entry_or_null(&list,
604 struct list_test_struct, list));
605
606 list_add_tail(&test_struct1.list, &list);
607 list_add_tail(&test_struct2.list, &list);
608
609 KUNIT_EXPECT_PTR_EQ(test, &test_struct1,
610 list_first_entry_or_null(&list,
611 struct list_test_struct, list));
612 }
613
list_test_list_next_entry(struct kunit * test)614 static void list_test_list_next_entry(struct kunit *test)
615 {
616 struct list_test_struct test_struct1, test_struct2;
617 LIST_HEAD(list);
618
619 list_add_tail(&test_struct1.list, &list);
620 list_add_tail(&test_struct2.list, &list);
621
622
623 KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_next_entry(&test_struct1,
624 list));
625 }
626
list_test_list_prev_entry(struct kunit * test)627 static void list_test_list_prev_entry(struct kunit *test)
628 {
629 struct list_test_struct test_struct1, test_struct2;
630 LIST_HEAD(list);
631
632 list_add_tail(&test_struct1.list, &list);
633 list_add_tail(&test_struct2.list, &list);
634
635
636 KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_prev_entry(&test_struct2,
637 list));
638 }
639
list_test_list_for_each(struct kunit * test)640 static void list_test_list_for_each(struct kunit *test)
641 {
642 struct list_head entries[3], *cur;
643 LIST_HEAD(list);
644 int i = 0;
645
646 list_add_tail(&entries[0], &list);
647 list_add_tail(&entries[1], &list);
648 list_add_tail(&entries[2], &list);
649
650 list_for_each(cur, &list) {
651 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
652 i++;
653 }
654
655 KUNIT_EXPECT_EQ(test, i, 3);
656 }
657
list_test_list_for_each_prev(struct kunit * test)658 static void list_test_list_for_each_prev(struct kunit *test)
659 {
660 struct list_head entries[3], *cur;
661 LIST_HEAD(list);
662 int i = 2;
663
664 list_add_tail(&entries[0], &list);
665 list_add_tail(&entries[1], &list);
666 list_add_tail(&entries[2], &list);
667
668 list_for_each_prev(cur, &list) {
669 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
670 i--;
671 }
672
673 KUNIT_EXPECT_EQ(test, i, -1);
674 }
675
list_test_list_for_each_safe(struct kunit * test)676 static void list_test_list_for_each_safe(struct kunit *test)
677 {
678 struct list_head entries[3], *cur, *n;
679 LIST_HEAD(list);
680 int i = 0;
681
682
683 list_add_tail(&entries[0], &list);
684 list_add_tail(&entries[1], &list);
685 list_add_tail(&entries[2], &list);
686
687 list_for_each_safe(cur, n, &list) {
688 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
689 list_del(&entries[i]);
690 i++;
691 }
692
693 KUNIT_EXPECT_EQ(test, i, 3);
694 KUNIT_EXPECT_TRUE(test, list_empty(&list));
695 }
696
list_test_list_for_each_prev_safe(struct kunit * test)697 static void list_test_list_for_each_prev_safe(struct kunit *test)
698 {
699 struct list_head entries[3], *cur, *n;
700 LIST_HEAD(list);
701 int i = 2;
702
703 list_add_tail(&entries[0], &list);
704 list_add_tail(&entries[1], &list);
705 list_add_tail(&entries[2], &list);
706
707 list_for_each_prev_safe(cur, n, &list) {
708 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
709 list_del(&entries[i]);
710 i--;
711 }
712
713 KUNIT_EXPECT_EQ(test, i, -1);
714 KUNIT_EXPECT_TRUE(test, list_empty(&list));
715 }
716
list_test_list_for_each_entry(struct kunit * test)717 static void list_test_list_for_each_entry(struct kunit *test)
718 {
719 struct list_test_struct entries[5], *cur;
720 LIST_HEAD(list);
721 int i = 0;
722
723 for (i = 0; i < 5; ++i) {
724 entries[i].data = i;
725 list_add_tail(&entries[i].list, &list);
726 }
727
728 i = 0;
729
730 list_for_each_entry(cur, &list, list) {
731 KUNIT_EXPECT_EQ(test, cur->data, i);
732 i++;
733 }
734
735 KUNIT_EXPECT_EQ(test, i, 5);
736 }
737
list_test_list_for_each_entry_reverse(struct kunit * test)738 static void list_test_list_for_each_entry_reverse(struct kunit *test)
739 {
740 struct list_test_struct entries[5], *cur;
741 LIST_HEAD(list);
742 int i = 0;
743
744 for (i = 0; i < 5; ++i) {
745 entries[i].data = i;
746 list_add_tail(&entries[i].list, &list);
747 }
748
749 i = 4;
750
751 list_for_each_entry_reverse(cur, &list, list) {
752 KUNIT_EXPECT_EQ(test, cur->data, i);
753 i--;
754 }
755
756 KUNIT_EXPECT_EQ(test, i, -1);
757 }
758
759 static struct kunit_case list_test_cases[] = {
760 KUNIT_CASE(list_test_list_init),
761 KUNIT_CASE(list_test_list_add),
762 KUNIT_CASE(list_test_list_add_tail),
763 KUNIT_CASE(list_test_list_del),
764 KUNIT_CASE(list_test_list_replace),
765 KUNIT_CASE(list_test_list_replace_init),
766 KUNIT_CASE(list_test_list_swap),
767 KUNIT_CASE(list_test_list_del_init),
768 KUNIT_CASE(list_test_list_del_init_careful),
769 KUNIT_CASE(list_test_list_move),
770 KUNIT_CASE(list_test_list_move_tail),
771 KUNIT_CASE(list_test_list_bulk_move_tail),
772 KUNIT_CASE(list_test_list_is_head),
773 KUNIT_CASE(list_test_list_is_first),
774 KUNIT_CASE(list_test_list_is_last),
775 KUNIT_CASE(list_test_list_empty),
776 KUNIT_CASE(list_test_list_empty_careful),
777 KUNIT_CASE(list_test_list_rotate_left),
778 KUNIT_CASE(list_test_list_rotate_to_front),
779 KUNIT_CASE(list_test_list_is_singular),
780 KUNIT_CASE(list_test_list_cut_position),
781 KUNIT_CASE(list_test_list_cut_before),
782 KUNIT_CASE(list_test_list_splice),
783 KUNIT_CASE(list_test_list_splice_tail),
784 KUNIT_CASE(list_test_list_splice_init),
785 KUNIT_CASE(list_test_list_splice_tail_init),
786 KUNIT_CASE(list_test_list_entry),
787 KUNIT_CASE(list_test_list_entry_is_head),
788 KUNIT_CASE(list_test_list_first_entry),
789 KUNIT_CASE(list_test_list_last_entry),
790 KUNIT_CASE(list_test_list_first_entry_or_null),
791 KUNIT_CASE(list_test_list_next_entry),
792 KUNIT_CASE(list_test_list_prev_entry),
793 KUNIT_CASE(list_test_list_for_each),
794 KUNIT_CASE(list_test_list_for_each_prev),
795 KUNIT_CASE(list_test_list_for_each_safe),
796 KUNIT_CASE(list_test_list_for_each_prev_safe),
797 KUNIT_CASE(list_test_list_for_each_entry),
798 KUNIT_CASE(list_test_list_for_each_entry_reverse),
799 {},
800 };
801
802 static struct kunit_suite list_test_module = {
803 .name = "list-kunit-test",
804 .test_cases = list_test_cases,
805 };
806
807 struct hlist_test_struct {
808 int data;
809 struct hlist_node list;
810 };
811
hlist_test_init(struct kunit * test)812 static void hlist_test_init(struct kunit *test)
813 {
814 /* Test the different ways of initialising a list. */
815 struct hlist_head list1 = HLIST_HEAD_INIT;
816 struct hlist_head list2;
817 HLIST_HEAD(list3);
818 struct hlist_head *list4;
819 struct hlist_head *list5;
820
821 INIT_HLIST_HEAD(&list2);
822
823 list4 = kzalloc(sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL);
824 INIT_HLIST_HEAD(list4);
825
826 list5 = kmalloc(sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL);
827 memset(list5, 0xFF, sizeof(*list5));
828 INIT_HLIST_HEAD(list5);
829
830 KUNIT_EXPECT_TRUE(test, hlist_empty(&list1));
831 KUNIT_EXPECT_TRUE(test, hlist_empty(&list2));
832 KUNIT_EXPECT_TRUE(test, hlist_empty(&list3));
833 KUNIT_EXPECT_TRUE(test, hlist_empty(list4));
834 KUNIT_EXPECT_TRUE(test, hlist_empty(list5));
835
836 kfree(list4);
837 kfree(list5);
838 }
839
hlist_test_unhashed(struct kunit * test)840 static void hlist_test_unhashed(struct kunit *test)
841 {
842 struct hlist_node a;
843 HLIST_HEAD(list);
844
845 INIT_HLIST_NODE(&a);
846
847 /* is unhashed by default */
848 KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a));
849
850 hlist_add_head(&a, &list);
851
852 /* is hashed once added to list */
853 KUNIT_EXPECT_FALSE(test, hlist_unhashed(&a));
854
855 hlist_del_init(&a);
856
857 /* is again unhashed after del_init */
858 KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a));
859 }
860
861 /* Doesn't test concurrency guarantees */
hlist_test_unhashed_lockless(struct kunit * test)862 static void hlist_test_unhashed_lockless(struct kunit *test)
863 {
864 struct hlist_node a;
865 HLIST_HEAD(list);
866
867 INIT_HLIST_NODE(&a);
868
869 /* is unhashed by default */
870 KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a));
871
872 hlist_add_head(&a, &list);
873
874 /* is hashed once added to list */
875 KUNIT_EXPECT_FALSE(test, hlist_unhashed_lockless(&a));
876
877 hlist_del_init(&a);
878
879 /* is again unhashed after del_init */
880 KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a));
881 }
882
hlist_test_del(struct kunit * test)883 static void hlist_test_del(struct kunit *test)
884 {
885 struct hlist_node a, b;
886 HLIST_HEAD(list);
887
888 hlist_add_head(&a, &list);
889 hlist_add_behind(&b, &a);
890
891 /* before: [list] -> a -> b */
892 hlist_del(&a);
893
894 /* now: [list] -> b */
895 KUNIT_EXPECT_PTR_EQ(test, list.first, &b);
896 KUNIT_EXPECT_PTR_EQ(test, b.pprev, &list.first);
897 }
898
hlist_test_del_init(struct kunit * test)899 static void hlist_test_del_init(struct kunit *test)
900 {
901 struct hlist_node a, b;
902 HLIST_HEAD(list);
903
904 hlist_add_head(&a, &list);
905 hlist_add_behind(&b, &a);
906
907 /* before: [list] -> a -> b */
908 hlist_del_init(&a);
909
910 /* now: [list] -> b */
911 KUNIT_EXPECT_PTR_EQ(test, list.first, &b);
912 KUNIT_EXPECT_PTR_EQ(test, b.pprev, &list.first);
913
914 /* a is now initialised */
915 KUNIT_EXPECT_PTR_EQ(test, a.next, NULL);
916 KUNIT_EXPECT_PTR_EQ(test, a.pprev, NULL);
917 }
918
919 /* Tests all three hlist_add_* functions */
hlist_test_add(struct kunit * test)920 static void hlist_test_add(struct kunit *test)
921 {
922 struct hlist_node a, b, c, d;
923 HLIST_HEAD(list);
924
925 hlist_add_head(&a, &list);
926 hlist_add_head(&b, &list);
927 hlist_add_before(&c, &a);
928 hlist_add_behind(&d, &a);
929
930 /* should be [list] -> b -> c -> a -> d */
931 KUNIT_EXPECT_PTR_EQ(test, list.first, &b);
932
933 KUNIT_EXPECT_PTR_EQ(test, c.pprev, &(b.next));
934 KUNIT_EXPECT_PTR_EQ(test, b.next, &c);
935
936 KUNIT_EXPECT_PTR_EQ(test, a.pprev, &(c.next));
937 KUNIT_EXPECT_PTR_EQ(test, c.next, &a);
938
939 KUNIT_EXPECT_PTR_EQ(test, d.pprev, &(a.next));
940 KUNIT_EXPECT_PTR_EQ(test, a.next, &d);
941 }
942
943 /* Tests both hlist_fake() and hlist_add_fake() */
hlist_test_fake(struct kunit * test)944 static void hlist_test_fake(struct kunit *test)
945 {
946 struct hlist_node a;
947
948 INIT_HLIST_NODE(&a);
949
950 /* not fake after init */
951 KUNIT_EXPECT_FALSE(test, hlist_fake(&a));
952
953 hlist_add_fake(&a);
954
955 /* is now fake */
956 KUNIT_EXPECT_TRUE(test, hlist_fake(&a));
957 }
958
hlist_test_is_singular_node(struct kunit * test)959 static void hlist_test_is_singular_node(struct kunit *test)
960 {
961 struct hlist_node a, b;
962 HLIST_HEAD(list);
963
964 INIT_HLIST_NODE(&a);
965 KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list));
966
967 hlist_add_head(&a, &list);
968 KUNIT_EXPECT_TRUE(test, hlist_is_singular_node(&a, &list));
969
970 hlist_add_head(&b, &list);
971 KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list));
972 KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&b, &list));
973 }
974
hlist_test_empty(struct kunit * test)975 static void hlist_test_empty(struct kunit *test)
976 {
977 struct hlist_node a;
978 HLIST_HEAD(list);
979
980 /* list starts off empty */
981 KUNIT_EXPECT_TRUE(test, hlist_empty(&list));
982
983 hlist_add_head(&a, &list);
984
985 /* list is no longer empty */
986 KUNIT_EXPECT_FALSE(test, hlist_empty(&list));
987 }
988
hlist_test_move_list(struct kunit * test)989 static void hlist_test_move_list(struct kunit *test)
990 {
991 struct hlist_node a;
992 HLIST_HEAD(list1);
993 HLIST_HEAD(list2);
994
995 hlist_add_head(&a, &list1);
996
997 KUNIT_EXPECT_FALSE(test, hlist_empty(&list1));
998 KUNIT_EXPECT_TRUE(test, hlist_empty(&list2));
999 hlist_move_list(&list1, &list2);
1000 KUNIT_EXPECT_TRUE(test, hlist_empty(&list1));
1001 KUNIT_EXPECT_FALSE(test, hlist_empty(&list2));
1002
1003 }
1004
hlist_test_entry(struct kunit * test)1005 static void hlist_test_entry(struct kunit *test)
1006 {
1007 struct hlist_test_struct test_struct;
1008
1009 KUNIT_EXPECT_PTR_EQ(test, &test_struct,
1010 hlist_entry(&(test_struct.list),
1011 struct hlist_test_struct, list));
1012 }
1013
hlist_test_entry_safe(struct kunit * test)1014 static void hlist_test_entry_safe(struct kunit *test)
1015 {
1016 struct hlist_test_struct test_struct;
1017
1018 KUNIT_EXPECT_PTR_EQ(test, &test_struct,
1019 hlist_entry_safe(&(test_struct.list),
1020 struct hlist_test_struct, list));
1021
1022 KUNIT_EXPECT_PTR_EQ(test, NULL,
1023 hlist_entry_safe((struct hlist_node *)NULL,
1024 struct hlist_test_struct, list));
1025 }
1026
hlist_test_for_each(struct kunit * test)1027 static void hlist_test_for_each(struct kunit *test)
1028 {
1029 struct hlist_node entries[3], *cur;
1030 HLIST_HEAD(list);
1031 int i = 0;
1032
1033 hlist_add_head(&entries[0], &list);
1034 hlist_add_behind(&entries[1], &entries[0]);
1035 hlist_add_behind(&entries[2], &entries[1]);
1036
1037 hlist_for_each(cur, &list) {
1038 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
1039 i++;
1040 }
1041
1042 KUNIT_EXPECT_EQ(test, i, 3);
1043 }
1044
1045
hlist_test_for_each_safe(struct kunit * test)1046 static void hlist_test_for_each_safe(struct kunit *test)
1047 {
1048 struct hlist_node entries[3], *cur, *n;
1049 HLIST_HEAD(list);
1050 int i = 0;
1051
1052 hlist_add_head(&entries[0], &list);
1053 hlist_add_behind(&entries[1], &entries[0]);
1054 hlist_add_behind(&entries[2], &entries[1]);
1055
1056 hlist_for_each_safe(cur, n, &list) {
1057 KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
1058 hlist_del(&entries[i]);
1059 i++;
1060 }
1061
1062 KUNIT_EXPECT_EQ(test, i, 3);
1063 KUNIT_EXPECT_TRUE(test, hlist_empty(&list));
1064 }
1065
hlist_test_for_each_entry(struct kunit * test)1066 static void hlist_test_for_each_entry(struct kunit *test)
1067 {
1068 struct hlist_test_struct entries[5], *cur;
1069 HLIST_HEAD(list);
1070 int i = 0;
1071
1072 entries[0].data = 0;
1073 hlist_add_head(&entries[0].list, &list);
1074 for (i = 1; i < 5; ++i) {
1075 entries[i].data = i;
1076 hlist_add_behind(&entries[i].list, &entries[i-1].list);
1077 }
1078
1079 i = 0;
1080
1081 hlist_for_each_entry(cur, &list, list) {
1082 KUNIT_EXPECT_EQ(test, cur->data, i);
1083 i++;
1084 }
1085
1086 KUNIT_EXPECT_EQ(test, i, 5);
1087 }
1088
hlist_test_for_each_entry_continue(struct kunit * test)1089 static void hlist_test_for_each_entry_continue(struct kunit *test)
1090 {
1091 struct hlist_test_struct entries[5], *cur;
1092 HLIST_HEAD(list);
1093 int i = 0;
1094
1095 entries[0].data = 0;
1096 hlist_add_head(&entries[0].list, &list);
1097 for (i = 1; i < 5; ++i) {
1098 entries[i].data = i;
1099 hlist_add_behind(&entries[i].list, &entries[i-1].list);
1100 }
1101
1102 /* We skip the first (zero-th) entry. */
1103 i = 1;
1104
1105 cur = &entries[0];
1106 hlist_for_each_entry_continue(cur, list) {
1107 KUNIT_EXPECT_EQ(test, cur->data, i);
1108 /* Stamp over the entry. */
1109 cur->data = 42;
1110 i++;
1111 }
1112
1113 KUNIT_EXPECT_EQ(test, i, 5);
1114 /* The first entry was not visited. */
1115 KUNIT_EXPECT_EQ(test, entries[0].data, 0);
1116 /* The second (and presumably others), were. */
1117 KUNIT_EXPECT_EQ(test, entries[1].data, 42);
1118 }
1119
hlist_test_for_each_entry_from(struct kunit * test)1120 static void hlist_test_for_each_entry_from(struct kunit *test)
1121 {
1122 struct hlist_test_struct entries[5], *cur;
1123 HLIST_HEAD(list);
1124 int i = 0;
1125
1126 entries[0].data = 0;
1127 hlist_add_head(&entries[0].list, &list);
1128 for (i = 1; i < 5; ++i) {
1129 entries[i].data = i;
1130 hlist_add_behind(&entries[i].list, &entries[i-1].list);
1131 }
1132
1133 i = 0;
1134
1135 cur = &entries[0];
1136 hlist_for_each_entry_from(cur, list) {
1137 KUNIT_EXPECT_EQ(test, cur->data, i);
1138 /* Stamp over the entry. */
1139 cur->data = 42;
1140 i++;
1141 }
1142
1143 KUNIT_EXPECT_EQ(test, i, 5);
1144 /* The first entry was visited. */
1145 KUNIT_EXPECT_EQ(test, entries[0].data, 42);
1146 }
1147
hlist_test_for_each_entry_safe(struct kunit * test)1148 static void hlist_test_for_each_entry_safe(struct kunit *test)
1149 {
1150 struct hlist_test_struct entries[5], *cur;
1151 struct hlist_node *tmp_node;
1152 HLIST_HEAD(list);
1153 int i = 0;
1154
1155 entries[0].data = 0;
1156 hlist_add_head(&entries[0].list, &list);
1157 for (i = 1; i < 5; ++i) {
1158 entries[i].data = i;
1159 hlist_add_behind(&entries[i].list, &entries[i-1].list);
1160 }
1161
1162 i = 0;
1163
1164 hlist_for_each_entry_safe(cur, tmp_node, &list, list) {
1165 KUNIT_EXPECT_EQ(test, cur->data, i);
1166 hlist_del(&cur->list);
1167 i++;
1168 }
1169
1170 KUNIT_EXPECT_EQ(test, i, 5);
1171 KUNIT_EXPECT_TRUE(test, hlist_empty(&list));
1172 }
1173
1174
1175 static struct kunit_case hlist_test_cases[] = {
1176 KUNIT_CASE(hlist_test_init),
1177 KUNIT_CASE(hlist_test_unhashed),
1178 KUNIT_CASE(hlist_test_unhashed_lockless),
1179 KUNIT_CASE(hlist_test_del),
1180 KUNIT_CASE(hlist_test_del_init),
1181 KUNIT_CASE(hlist_test_add),
1182 KUNIT_CASE(hlist_test_fake),
1183 KUNIT_CASE(hlist_test_is_singular_node),
1184 KUNIT_CASE(hlist_test_empty),
1185 KUNIT_CASE(hlist_test_move_list),
1186 KUNIT_CASE(hlist_test_entry),
1187 KUNIT_CASE(hlist_test_entry_safe),
1188 KUNIT_CASE(hlist_test_for_each),
1189 KUNIT_CASE(hlist_test_for_each_safe),
1190 KUNIT_CASE(hlist_test_for_each_entry),
1191 KUNIT_CASE(hlist_test_for_each_entry_continue),
1192 KUNIT_CASE(hlist_test_for_each_entry_from),
1193 KUNIT_CASE(hlist_test_for_each_entry_safe),
1194 {},
1195 };
1196
1197 static struct kunit_suite hlist_test_module = {
1198 .name = "hlist",
1199 .test_cases = hlist_test_cases,
1200 };
1201
1202 kunit_test_suites(&list_test_module, &hlist_test_module);
1203
1204 MODULE_LICENSE("GPL v2");
1205