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 | |
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(list: &list2); |
28 | |
29 | list4 = kzalloc(size: sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL); |
30 | INIT_LIST_HEAD(list: list4); |
31 | |
32 | list5 = kmalloc(size: sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL); |
33 | memset(list5, 0xFF, sizeof(*list5)); |
34 | INIT_LIST_HEAD(list: 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(objp: list4); |
44 | kfree(objp: list5); |
45 | } |
46 | |
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(new: &a, head: &list); |
53 | list_add(new: &b, head: &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 | |
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(new: &a, head: &list); |
67 | list_add_tail(new: &b, head: &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 | |
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(new: &a, head: &list); |
81 | list_add_tail(new: &b, head: &list); |
82 | |
83 | /* before: [list] -> a -> b */ |
84 | list_del(entry: &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 | |
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(new: &a_old, head: &list); |
97 | list_add_tail(new: &b, head: &list); |
98 | |
99 | /* before: [list] -> a_old -> b */ |
100 | list_replace(old: &a_old, new: &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 | |
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(new: &a_old, head: &list); |
113 | list_add_tail(new: &b, head: &list); |
114 | |
115 | /* before: [list] -> a_old -> b */ |
116 | list_replace_init(old: &a_old, new: &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 | |
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(new: &a, head: &list); |
132 | list_add_tail(new: &b, head: &list); |
133 | |
134 | /* before: [list] -> a -> b */ |
135 | list_swap(entry1: &a, entry2: &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 | |
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(new: &a, head: &list); |
154 | list_add_tail(new: &b, head: &list); |
155 | |
156 | /* before: [list] -> a -> b */ |
157 | list_del_init(entry: &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 | |
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(new: &a, head: &list); |
174 | list_add_tail(new: &b, head: &list); |
175 | |
176 | /* before: [list] -> a -> b */ |
177 | list_del_init_careful(entry: &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 | |
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(new: &a, head: &list1); |
192 | list_add_tail(new: &b, head: &list2); |
193 | |
194 | /* before: [list1] -> a, [list2] -> b */ |
195 | list_move(list: &a, head: &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 | |
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(new: &a, head: &list1); |
211 | list_add_tail(new: &b, head: &list2); |
212 | |
213 | /* before: [list1] -> a, [list2] -> b */ |
214 | list_move_tail(list: &a, head: &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 | |
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(new: &x, head: &list1); |
234 | list_add_tail(new: &y, head: &list1); |
235 | |
236 | list_add_tail(new: &a, head: &list2); |
237 | list_add_tail(new: &b, head: &list2); |
238 | list_add_tail(new: &c, head: &list2); |
239 | list_add_tail(new: &d, head: &list2); |
240 | |
241 | /* before: [list1] -> x -> y, [list2] -> a -> b -> c -> d */ |
242 | list_bulk_move_tail(head: &y, first: &b, last: &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 | |
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(list: &a); |
264 | INIT_LIST_HEAD(list: &c); |
265 | list_add_tail(new: &b, head: &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 | |
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(new: &a, head: &list); |
282 | list_add_tail(new: &b, head: &list); |
283 | |
284 | KUNIT_EXPECT_TRUE(test, list_is_first(&a, &list)); |
285 | KUNIT_EXPECT_FALSE(test, list_is_first(&b, &list)); |
286 | } |
287 | |
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(new: &a, head: &list); |
294 | list_add_tail(new: &b, head: &list); |
295 | |
296 | KUNIT_EXPECT_FALSE(test, list_is_last(&a, &list)); |
297 | KUNIT_EXPECT_TRUE(test, list_is_last(&b, &list)); |
298 | } |
299 | |
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(new: &a, head: &list1); |
307 | |
308 | KUNIT_EXPECT_FALSE(test, list_empty(&list1)); |
309 | KUNIT_EXPECT_TRUE(test, list_empty(&list2)); |
310 | } |
311 | |
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(new: &a, head: &list1); |
320 | |
321 | KUNIT_EXPECT_FALSE(test, list_empty_careful(&list1)); |
322 | KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); |
323 | } |
324 | |
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(new: &a, head: &list); |
331 | list_add_tail(new: &b, head: &list); |
332 | |
333 | /* before: [list] -> a -> b */ |
334 | list_rotate_left(head: &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 | |
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(new: &a, head: &list); |
351 | list_add_tail(new: &b, head: &list); |
352 | list_add_tail(new: &c, head: &list); |
353 | list_add_tail(new: &d, head: &list); |
354 | |
355 | /* before: [list] -> a -> b -> c -> d */ |
356 | list_rotate_to_front(list: &c, head: &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 | |
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(new: &a, head: &list); |
375 | |
376 | /* [list] -> a */ |
377 | KUNIT_EXPECT_TRUE(test, list_is_singular(&list)); |
378 | |
379 | list_add_tail(new: &b, head: &list); |
380 | |
381 | /* [list] -> a -> b */ |
382 | KUNIT_EXPECT_FALSE(test, list_is_singular(&list)); |
383 | } |
384 | |
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(new: &entries[0], head: &list1); |
393 | list_add_tail(new: &entries[1], head: &list1); |
394 | list_add_tail(new: &entries[2], head: &list1); |
395 | |
396 | /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */ |
397 | list_cut_position(list: &list2, head: &list1, entry: &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 | |
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(new: &entries[0], head: &list1); |
421 | list_add_tail(new: &entries[1], head: &list1); |
422 | list_add_tail(new: &entries[2], head: &list1); |
423 | |
424 | /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */ |
425 | list_cut_before(list: &list2, head: &list1, entry: &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 | |
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(new: &entries[0], head: &list1); |
449 | list_add_tail(new: &entries[1], head: &list1); |
450 | list_add_tail(new: &entries[2], head: &list2); |
451 | list_add_tail(new: &entries[3], head: &list2); |
452 | list_add_tail(new: &entries[4], head: &list1); |
453 | |
454 | /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ |
455 | list_splice(list: &list2, head: &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 | |
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(new: &entries[0], head: &list1); |
474 | list_add_tail(new: &entries[1], head: &list1); |
475 | list_add_tail(new: &entries[2], head: &list2); |
476 | list_add_tail(new: &entries[3], head: &list2); |
477 | list_add_tail(new: &entries[4], head: &list1); |
478 | |
479 | /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ |
480 | list_splice_tail(list: &list2, head: &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 | |
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(new: &entries[0], head: &list1); |
499 | list_add_tail(new: &entries[1], head: &list1); |
500 | list_add_tail(new: &entries[2], head: &list2); |
501 | list_add_tail(new: &entries[3], head: &list2); |
502 | list_add_tail(new: &entries[4], head: &list1); |
503 | |
504 | /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ |
505 | list_splice_init(list: &list2, head: &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 | |
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(new: &entries[0], head: &list1); |
526 | list_add_tail(new: &entries[1], head: &list1); |
527 | list_add_tail(new: &entries[2], head: &list2); |
528 | list_add_tail(new: &entries[3], head: &list2); |
529 | list_add_tail(new: &entries[4], head: &list1); |
530 | |
531 | /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ |
532 | list_splice_tail_init(list: &list2, head: &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 | |
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 | |
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(list: &test_struct1.list); |
558 | INIT_LIST_HEAD(list: &test_struct3.list); |
559 | |
560 | list_add_tail(new: &test_struct2.list, head: &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 | |
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(new: &test_struct1.list, head: &list); |
579 | list_add_tail(new: &test_struct2.list, head: &list); |
580 | |
581 | |
582 | KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_first_entry(&list, |
583 | struct list_test_struct, list)); |
584 | } |
585 | |
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(new: &test_struct1.list, head: &list); |
592 | list_add_tail(new: &test_struct2.list, head: &list); |
593 | |
594 | |
595 | KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_last_entry(&list, |
596 | struct list_test_struct, list)); |
597 | } |
598 | |
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(new: &test_struct1.list, head: &list); |
608 | list_add_tail(new: &test_struct2.list, head: &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 | |
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(new: &test_struct1.list, head: &list); |
621 | list_add_tail(new: &test_struct2.list, head: &list); |
622 | |
623 | |
624 | KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_next_entry(&test_struct1, |
625 | list)); |
626 | } |
627 | |
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(new: &test_struct1.list, head: &list); |
634 | list_add_tail(new: &test_struct2.list, head: &list); |
635 | |
636 | |
637 | KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_prev_entry(&test_struct2, |
638 | list)); |
639 | } |
640 | |
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(new: &entries[0], head: &list); |
648 | list_add_tail(new: &entries[1], head: &list); |
649 | list_add_tail(new: &entries[2], head: &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 | |
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(new: &entries[0], head: &list); |
666 | list_add_tail(new: &entries[1], head: &list); |
667 | list_add_tail(new: &entries[2], head: &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 | |
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(new: &entries[0], head: &list); |
685 | list_add_tail(new: &entries[1], head: &list); |
686 | list_add_tail(new: &entries[2], head: &list); |
687 | |
688 | list_for_each_safe(cur, n, &list) { |
689 | KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); |
690 | list_del(entry: &entries[i]); |
691 | i++; |
692 | } |
693 | |
694 | KUNIT_EXPECT_EQ(test, i, 3); |
695 | KUNIT_EXPECT_TRUE(test, list_empty(&list)); |
696 | } |
697 | |
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(new: &entries[0], head: &list); |
705 | list_add_tail(new: &entries[1], head: &list); |
706 | list_add_tail(new: &entries[2], head: &list); |
707 | |
708 | list_for_each_prev_safe(cur, n, &list) { |
709 | KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); |
710 | list_del(entry: &entries[i]); |
711 | i--; |
712 | } |
713 | |
714 | KUNIT_EXPECT_EQ(test, i, -1); |
715 | KUNIT_EXPECT_TRUE(test, list_empty(&list)); |
716 | } |
717 | |
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(new: &entries[i].list, head: &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 | |
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(new: &entries[i].list, head: &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 | |
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(size: sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL); |
825 | INIT_HLIST_HEAD(list4); |
826 | |
827 | list5 = kmalloc(size: 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(objp: list4); |
838 | kfree(objp: list5); |
839 | } |
840 | |
841 | static void hlist_test_unhashed(struct kunit *test) |
842 | { |
843 | struct hlist_node a; |
844 | HLIST_HEAD(list); |
845 | |
846 | INIT_HLIST_NODE(h: &a); |
847 | |
848 | /* is unhashed by default */ |
849 | KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a)); |
850 | |
851 | hlist_add_head(n: &a, h: &list); |
852 | |
853 | /* is hashed once added to list */ |
854 | KUNIT_EXPECT_FALSE(test, hlist_unhashed(&a)); |
855 | |
856 | hlist_del_init(n: &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 */ |
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(h: &a); |
869 | |
870 | /* is unhashed by default */ |
871 | KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a)); |
872 | |
873 | hlist_add_head(n: &a, h: &list); |
874 | |
875 | /* is hashed once added to list */ |
876 | KUNIT_EXPECT_FALSE(test, hlist_unhashed_lockless(&a)); |
877 | |
878 | hlist_del_init(n: &a); |
879 | |
880 | /* is again unhashed after del_init */ |
881 | KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a)); |
882 | } |
883 | |
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(n: &a, h: &list); |
890 | hlist_add_behind(n: &b, prev: &a); |
891 | |
892 | /* before: [list] -> a -> b */ |
893 | hlist_del(n: &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 | |
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(n: &a, h: &list); |
906 | hlist_add_behind(n: &b, prev: &a); |
907 | |
908 | /* before: [list] -> a -> b */ |
909 | hlist_del_init(n: &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 */ |
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(n: &a, h: &list); |
927 | hlist_add_head(n: &b, h: &list); |
928 | hlist_add_before(n: &c, next: &a); |
929 | hlist_add_behind(n: &d, prev: &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() */ |
945 | static void hlist_test_fake(struct kunit *test) |
946 | { |
947 | struct hlist_node a; |
948 | |
949 | INIT_HLIST_NODE(h: &a); |
950 | |
951 | /* not fake after init */ |
952 | KUNIT_EXPECT_FALSE(test, hlist_fake(&a)); |
953 | |
954 | hlist_add_fake(n: &a); |
955 | |
956 | /* is now fake */ |
957 | KUNIT_EXPECT_TRUE(test, hlist_fake(&a)); |
958 | } |
959 | |
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(h: &a); |
966 | KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list)); |
967 | |
968 | hlist_add_head(n: &a, h: &list); |
969 | KUNIT_EXPECT_TRUE(test, hlist_is_singular_node(&a, &list)); |
970 | |
971 | hlist_add_head(n: &b, h: &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 | |
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(n: &a, h: &list); |
985 | |
986 | /* list is no longer empty */ |
987 | KUNIT_EXPECT_FALSE(test, hlist_empty(&list)); |
988 | } |
989 | |
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(n: &a, h: &list1); |
997 | |
998 | KUNIT_EXPECT_FALSE(test, hlist_empty(&list1)); |
999 | KUNIT_EXPECT_TRUE(test, hlist_empty(&list2)); |
1000 | hlist_move_list(old: &list1, new: &list2); |
1001 | KUNIT_EXPECT_TRUE(test, hlist_empty(&list1)); |
1002 | KUNIT_EXPECT_FALSE(test, hlist_empty(&list2)); |
1003 | |
1004 | } |
1005 | |
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 | |
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 | |
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(n: &entries[0], h: &list); |
1035 | hlist_add_behind(n: &entries[1], prev: &entries[0]); |
1036 | hlist_add_behind(n: &entries[2], prev: &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 | |
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(n: &entries[0], h: &list); |
1054 | hlist_add_behind(n: &entries[1], prev: &entries[0]); |
1055 | hlist_add_behind(n: &entries[2], prev: &entries[1]); |
1056 | |
1057 | hlist_for_each_safe(cur, n, &list) { |
1058 | KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); |
1059 | hlist_del(n: &entries[i]); |
1060 | i++; |
1061 | } |
1062 | |
1063 | KUNIT_EXPECT_EQ(test, i, 3); |
1064 | KUNIT_EXPECT_TRUE(test, hlist_empty(&list)); |
1065 | } |
1066 | |
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(n: &entries[0].list, h: &list); |
1075 | for (i = 1; i < 5; ++i) { |
1076 | entries[i].data = i; |
1077 | hlist_add_behind(n: &entries[i].list, prev: &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 | |
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(n: &entries[0].list, h: &list); |
1098 | for (i = 1; i < 5; ++i) { |
1099 | entries[i].data = i; |
1100 | hlist_add_behind(n: &entries[i].list, prev: &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 | |
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(n: &entries[0].list, h: &list); |
1129 | for (i = 1; i < 5; ++i) { |
1130 | entries[i].data = i; |
1131 | hlist_add_behind(n: &entries[i].list, prev: &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 | |
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(n: &entries[0].list, h: &list); |
1158 | for (i = 1; i < 5; ++i) { |
1159 | entries[i].data = i; |
1160 | hlist_add_behind(n: &entries[i].list, prev: &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(n: &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 | |
1213 | static void check_node(struct klist_node *node_ptr) |
1214 | { |
1215 | node_count++; |
1216 | last_node = node_ptr; |
1217 | } |
1218 | |
1219 | static void check_delete_node(struct klist_node *node_ptr) |
1220 | { |
1221 | node_count--; |
1222 | last_node = node_ptr; |
1223 | } |
1224 | |
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(k: &mylist, get: &check_node, NULL); |
1233 | |
1234 | klist_add_tail(n: &a, k: &mylist); |
1235 | KUNIT_EXPECT_EQ(test, node_count, 1); |
1236 | KUNIT_EXPECT_PTR_EQ(test, last_node, &a); |
1237 | |
1238 | klist_add_tail(n: &b, k: &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(k: &mylist, i: &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: &i); |
1250 | |
1251 | } |
1252 | |
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(k: &mylist, get: &check_node, NULL); |
1261 | |
1262 | klist_add_head(n: &a, k: &mylist); |
1263 | KUNIT_EXPECT_EQ(test, node_count, 1); |
1264 | KUNIT_EXPECT_PTR_EQ(test, last_node, &a); |
1265 | |
1266 | klist_add_head(n: &b, k: &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(k: &mylist, i: &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: &i); |
1278 | |
1279 | } |
1280 | |
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(k: &mylist, get: &check_node, NULL); |
1289 | |
1290 | klist_add_head(n: &a, k: &mylist); |
1291 | klist_add_head(n: &b, k: &mylist); |
1292 | |
1293 | klist_add_behind(n: &c, pos: &a); |
1294 | KUNIT_EXPECT_EQ(test, node_count, 3); |
1295 | KUNIT_EXPECT_PTR_EQ(test, last_node, &c); |
1296 | |
1297 | klist_add_behind(n: &d, pos: &b); |
1298 | KUNIT_EXPECT_EQ(test, node_count, 4); |
1299 | KUNIT_EXPECT_PTR_EQ(test, last_node, &d); |
1300 | |
1301 | klist_iter_init(k: &mylist, i: &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: &i); |
1311 | |
1312 | } |
1313 | |
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(k: &mylist, get: &check_node, NULL); |
1322 | |
1323 | klist_add_head(n: &a, k: &mylist); |
1324 | klist_add_head(n: &b, k: &mylist); |
1325 | klist_add_before(n: &c, pos: &a); |
1326 | KUNIT_EXPECT_EQ(test, node_count, 3); |
1327 | KUNIT_EXPECT_PTR_EQ(test, last_node, &c); |
1328 | |
1329 | klist_add_before(n: &d, pos: &b); |
1330 | KUNIT_EXPECT_EQ(test, node_count, 4); |
1331 | KUNIT_EXPECT_PTR_EQ(test, last_node, &d); |
1332 | |
1333 | klist_iter_init(k: &mylist, i: &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: &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 | */ |
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(k: &mylist, get: &check_node, put: &check_delete_node); |
1358 | |
1359 | /* Add nodes a,b,c,d to the list*/ |
1360 | klist_add_tail(n: &a, k: &mylist); |
1361 | klist_add_tail(n: &b, k: &mylist); |
1362 | klist_add_tail(n: &c, k: &mylist); |
1363 | klist_add_tail(n: &d, k: &mylist); |
1364 | |
1365 | klist_iter_init(k: &mylist, i: &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(n: &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: &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 | */ |
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(k: &mylist, get: &check_node, put: &check_delete_node); |
1409 | |
1410 | /* Add nodes a,b,c,d to the list*/ |
1411 | klist_add_tail(n: &a, k: &mylist); |
1412 | klist_add_tail(n: &b, k: &mylist); |
1413 | klist_add_tail(n: &c, k: &mylist); |
1414 | klist_add_tail(n: &d, k: &mylist); |
1415 | /* Delete node c*/ |
1416 | klist_del(n: &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(k: &mylist, i: &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: &i); |
1431 | |
1432 | } |
1433 | |
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(k: &mylist, get: &check_node, put: &check_delete_node); |
1443 | |
1444 | /* Add nodes a,b,c,d to the list*/ |
1445 | klist_add_tail(n: &a, k: &mylist); |
1446 | klist_add_tail(n: &b, k: &mylist); |
1447 | klist_add_tail(n: &c, k: &mylist); |
1448 | klist_add_tail(n: &d, k: &mylist); |
1449 | /* Delete node c*/ |
1450 | klist_remove(n: &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(k: &mylist, i: &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: &i); |
1465 | |
1466 | } |
1467 | |
1468 | static void klist_test_node_attached(struct kunit *test) |
1469 | { |
1470 | struct klist_node a = {}; |
1471 | struct klist mylist; |
1472 | |
1473 | klist_init(k: &mylist, NULL, NULL); |
1474 | |
1475 | KUNIT_EXPECT_FALSE(test, klist_node_attached(&a)); |
1476 | klist_add_head(n: &a, k: &mylist); |
1477 | KUNIT_EXPECT_TRUE(test, klist_node_attached(&a)); |
1478 | klist_del(n: &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 | |