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