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