Back to home page

OSCL-LXR
 
 

     

0001 // SPDX-License-Identifier: GPL-2.0
0002 /*
0003  * KUnit test for the Kernel Linked-list structures.
0004  *
0005  * Copyright (C) 2019, Google LLC.
0006  * Author: David Gow <davidgow@google.com>
0007  */
0008 #include <kunit/test.h>
0009 
0010 #include <linux/list.h>
0011 
0012 struct list_test_struct {
0013     int data;
0014     struct list_head list;
0015 };
0016 
0017 static void list_test_list_init(struct kunit *test)
0018 {
0019     /* Test the different ways of initialising a list. */
0020     struct list_head list1 = LIST_HEAD_INIT(list1);
0021     struct list_head list2;
0022     LIST_HEAD(list3);
0023     struct list_head *list4;
0024     struct list_head *list5;
0025 
0026     INIT_LIST_HEAD(&list2);
0027 
0028     list4 = kzalloc(sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL);
0029     INIT_LIST_HEAD(list4);
0030 
0031     list5 = kmalloc(sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL);
0032     memset(list5, 0xFF, sizeof(*list5));
0033     INIT_LIST_HEAD(list5);
0034 
0035     /* list_empty_careful() checks both next and prev. */
0036     KUNIT_EXPECT_TRUE(test, list_empty_careful(&list1));
0037     KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
0038     KUNIT_EXPECT_TRUE(test, list_empty_careful(&list3));
0039     KUNIT_EXPECT_TRUE(test, list_empty_careful(list4));
0040     KUNIT_EXPECT_TRUE(test, list_empty_careful(list5));
0041 
0042     kfree(list4);
0043     kfree(list5);
0044 }
0045 
0046 static void list_test_list_add(struct kunit *test)
0047 {
0048     struct list_head a, b;
0049     LIST_HEAD(list);
0050 
0051     list_add(&a, &list);
0052     list_add(&b, &list);
0053 
0054     /* should be [list] -> b -> a */
0055     KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
0056     KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
0057     KUNIT_EXPECT_PTR_EQ(test, b.next, &a);
0058 }
0059 
0060 static void list_test_list_add_tail(struct kunit *test)
0061 {
0062     struct list_head a, b;
0063     LIST_HEAD(list);
0064 
0065     list_add_tail(&a, &list);
0066     list_add_tail(&b, &list);
0067 
0068     /* should be [list] -> a -> b */
0069     KUNIT_EXPECT_PTR_EQ(test, list.next, &a);
0070     KUNIT_EXPECT_PTR_EQ(test, a.prev, &list);
0071     KUNIT_EXPECT_PTR_EQ(test, a.next, &b);
0072 }
0073 
0074 static void list_test_list_del(struct kunit *test)
0075 {
0076     struct list_head a, b;
0077     LIST_HEAD(list);
0078 
0079     list_add_tail(&a, &list);
0080     list_add_tail(&b, &list);
0081 
0082     /* before: [list] -> a -> b */
0083     list_del(&a);
0084 
0085     /* now: [list] -> b */
0086     KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
0087     KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
0088 }
0089 
0090 static void list_test_list_replace(struct kunit *test)
0091 {
0092     struct list_head a_old, a_new, b;
0093     LIST_HEAD(list);
0094 
0095     list_add_tail(&a_old, &list);
0096     list_add_tail(&b, &list);
0097 
0098     /* before: [list] -> a_old -> b */
0099     list_replace(&a_old, &a_new);
0100 
0101     /* now: [list] -> a_new -> b */
0102     KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new);
0103     KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new);
0104 }
0105 
0106 static void list_test_list_replace_init(struct kunit *test)
0107 {
0108     struct list_head a_old, a_new, b;
0109     LIST_HEAD(list);
0110 
0111     list_add_tail(&a_old, &list);
0112     list_add_tail(&b, &list);
0113 
0114     /* before: [list] -> a_old -> b */
0115     list_replace_init(&a_old, &a_new);
0116 
0117     /* now: [list] -> a_new -> b */
0118     KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new);
0119     KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new);
0120 
0121     /* check a_old is empty (initialized) */
0122     KUNIT_EXPECT_TRUE(test, list_empty_careful(&a_old));
0123 }
0124 
0125 static void list_test_list_swap(struct kunit *test)
0126 {
0127     struct list_head a, b;
0128     LIST_HEAD(list);
0129 
0130     list_add_tail(&a, &list);
0131     list_add_tail(&b, &list);
0132 
0133     /* before: [list] -> a -> b */
0134     list_swap(&a, &b);
0135 
0136     /* after: [list] -> b -> a */
0137     KUNIT_EXPECT_PTR_EQ(test, &b, list.next);
0138     KUNIT_EXPECT_PTR_EQ(test, &a, list.prev);
0139 
0140     KUNIT_EXPECT_PTR_EQ(test, &a, b.next);
0141     KUNIT_EXPECT_PTR_EQ(test, &list, b.prev);
0142 
0143     KUNIT_EXPECT_PTR_EQ(test, &list, a.next);
0144     KUNIT_EXPECT_PTR_EQ(test, &b, a.prev);
0145 }
0146 
0147 static void list_test_list_del_init(struct kunit *test)
0148 {
0149     struct list_head a, b;
0150     LIST_HEAD(list);
0151 
0152     list_add_tail(&a, &list);
0153     list_add_tail(&b, &list);
0154 
0155     /* before: [list] -> a -> b */
0156     list_del_init(&a);
0157     /* after: [list] -> b, a initialised */
0158 
0159     KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
0160     KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
0161     KUNIT_EXPECT_TRUE(test, list_empty_careful(&a));
0162 }
0163 
0164 static void list_test_list_del_init_careful(struct kunit *test)
0165 {
0166     /* NOTE: This test only checks the behaviour of this function in
0167      * isolation. It does not verify memory model guarantees.
0168      */
0169     struct list_head a, b;
0170     LIST_HEAD(list);
0171 
0172     list_add_tail(&a, &list);
0173     list_add_tail(&b, &list);
0174 
0175     /* before: [list] -> a -> b */
0176     list_del_init_careful(&a);
0177     /* after: [list] -> b, a initialised */
0178 
0179     KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
0180     KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
0181     KUNIT_EXPECT_TRUE(test, list_empty_careful(&a));
0182 }
0183 
0184 static void list_test_list_move(struct kunit *test)
0185 {
0186     struct list_head a, b;
0187     LIST_HEAD(list1);
0188     LIST_HEAD(list2);
0189 
0190     list_add_tail(&a, &list1);
0191     list_add_tail(&b, &list2);
0192 
0193     /* before: [list1] -> a, [list2] -> b */
0194     list_move(&a, &list2);
0195     /* after: [list1] empty, [list2] -> a -> b */
0196 
0197     KUNIT_EXPECT_TRUE(test, list_empty(&list1));
0198 
0199     KUNIT_EXPECT_PTR_EQ(test, &a, list2.next);
0200     KUNIT_EXPECT_PTR_EQ(test, &b, a.next);
0201 }
0202 
0203 static void list_test_list_move_tail(struct kunit *test)
0204 {
0205     struct list_head a, b;
0206     LIST_HEAD(list1);
0207     LIST_HEAD(list2);
0208 
0209     list_add_tail(&a, &list1);
0210     list_add_tail(&b, &list2);
0211 
0212     /* before: [list1] -> a, [list2] -> b */
0213     list_move_tail(&a, &list2);
0214     /* after: [list1] empty, [list2] -> b -> a */
0215 
0216     KUNIT_EXPECT_TRUE(test, list_empty(&list1));
0217 
0218     KUNIT_EXPECT_PTR_EQ(test, &b, list2.next);
0219     KUNIT_EXPECT_PTR_EQ(test, &a, b.next);
0220 }
0221 
0222 static void list_test_list_bulk_move_tail(struct kunit *test)
0223 {
0224     struct list_head a, b, c, d, x, y;
0225     struct list_head *list1_values[] = { &x, &b, &c, &y };
0226     struct list_head *list2_values[] = { &a, &d };
0227     struct list_head *ptr;
0228     LIST_HEAD(list1);
0229     LIST_HEAD(list2);
0230     int i = 0;
0231 
0232     list_add_tail(&x, &list1);
0233     list_add_tail(&y, &list1);
0234 
0235     list_add_tail(&a, &list2);
0236     list_add_tail(&b, &list2);
0237     list_add_tail(&c, &list2);
0238     list_add_tail(&d, &list2);
0239 
0240     /* before: [list1] -> x -> y, [list2] -> a -> b -> c -> d */
0241     list_bulk_move_tail(&y, &b, &c);
0242     /* after: [list1] -> x -> b -> c -> y, [list2] -> a -> d */
0243 
0244     list_for_each(ptr, &list1) {
0245         KUNIT_EXPECT_PTR_EQ(test, ptr, list1_values[i]);
0246         i++;
0247     }
0248     KUNIT_EXPECT_EQ(test, i, 4);
0249     i = 0;
0250     list_for_each(ptr, &list2) {
0251         KUNIT_EXPECT_PTR_EQ(test, ptr, list2_values[i]);
0252         i++;
0253     }
0254     KUNIT_EXPECT_EQ(test, i, 2);
0255 }
0256 
0257 static void list_test_list_is_head(struct kunit *test)
0258 {
0259     struct list_head a, b, c;
0260 
0261     /* Two lists: [a] -> b, [c] */
0262     INIT_LIST_HEAD(&a);
0263     INIT_LIST_HEAD(&c);
0264     list_add_tail(&b, &a);
0265 
0266     KUNIT_EXPECT_TRUE_MSG(test, list_is_head(&a, &a),
0267         "Head element of same list");
0268     KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &b),
0269         "Non-head element of same list");
0270     KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &c),
0271         "Head element of different list");
0272 }
0273 
0274 
0275 static void list_test_list_is_first(struct kunit *test)
0276 {
0277     struct list_head a, b;
0278     LIST_HEAD(list);
0279 
0280     list_add_tail(&a, &list);
0281     list_add_tail(&b, &list);
0282 
0283     KUNIT_EXPECT_TRUE(test, list_is_first(&a, &list));
0284     KUNIT_EXPECT_FALSE(test, list_is_first(&b, &list));
0285 }
0286 
0287 static void list_test_list_is_last(struct kunit *test)
0288 {
0289     struct list_head a, b;
0290     LIST_HEAD(list);
0291 
0292     list_add_tail(&a, &list);
0293     list_add_tail(&b, &list);
0294 
0295     KUNIT_EXPECT_FALSE(test, list_is_last(&a, &list));
0296     KUNIT_EXPECT_TRUE(test, list_is_last(&b, &list));
0297 }
0298 
0299 static void list_test_list_empty(struct kunit *test)
0300 {
0301     struct list_head a;
0302     LIST_HEAD(list1);
0303     LIST_HEAD(list2);
0304 
0305     list_add_tail(&a, &list1);
0306 
0307     KUNIT_EXPECT_FALSE(test, list_empty(&list1));
0308     KUNIT_EXPECT_TRUE(test, list_empty(&list2));
0309 }
0310 
0311 static void list_test_list_empty_careful(struct kunit *test)
0312 {
0313     /* This test doesn't check correctness under concurrent access */
0314     struct list_head a;
0315     LIST_HEAD(list1);
0316     LIST_HEAD(list2);
0317 
0318     list_add_tail(&a, &list1);
0319 
0320     KUNIT_EXPECT_FALSE(test, list_empty_careful(&list1));
0321     KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
0322 }
0323 
0324 static void list_test_list_rotate_left(struct kunit *test)
0325 {
0326     struct list_head a, b;
0327     LIST_HEAD(list);
0328 
0329     list_add_tail(&a, &list);
0330     list_add_tail(&b, &list);
0331 
0332     /* before: [list] -> a -> b */
0333     list_rotate_left(&list);
0334     /* after: [list] -> b -> a */
0335 
0336     KUNIT_EXPECT_PTR_EQ(test, list.next, &b);
0337     KUNIT_EXPECT_PTR_EQ(test, b.prev, &list);
0338     KUNIT_EXPECT_PTR_EQ(test, b.next, &a);
0339 }
0340 
0341 static void list_test_list_rotate_to_front(struct kunit *test)
0342 {
0343     struct list_head a, b, c, d;
0344     struct list_head *list_values[] = { &c, &d, &a, &b };
0345     struct list_head *ptr;
0346     LIST_HEAD(list);
0347     int i = 0;
0348 
0349     list_add_tail(&a, &list);
0350     list_add_tail(&b, &list);
0351     list_add_tail(&c, &list);
0352     list_add_tail(&d, &list);
0353 
0354     /* before: [list] -> a -> b -> c -> d */
0355     list_rotate_to_front(&c, &list);
0356     /* after: [list] -> c -> d -> a -> b */
0357 
0358     list_for_each(ptr, &list) {
0359         KUNIT_EXPECT_PTR_EQ(test, ptr, list_values[i]);
0360         i++;
0361     }
0362     KUNIT_EXPECT_EQ(test, i, 4);
0363 }
0364 
0365 static void list_test_list_is_singular(struct kunit *test)
0366 {
0367     struct list_head a, b;
0368     LIST_HEAD(list);
0369 
0370     /* [list] empty */
0371     KUNIT_EXPECT_FALSE(test, list_is_singular(&list));
0372 
0373     list_add_tail(&a, &list);
0374 
0375     /* [list] -> a */
0376     KUNIT_EXPECT_TRUE(test, list_is_singular(&list));
0377 
0378     list_add_tail(&b, &list);
0379 
0380     /* [list] -> a -> b */
0381     KUNIT_EXPECT_FALSE(test, list_is_singular(&list));
0382 }
0383 
0384 static void list_test_list_cut_position(struct kunit *test)
0385 {
0386     struct list_head entries[3], *cur;
0387     LIST_HEAD(list1);
0388     LIST_HEAD(list2);
0389     int i = 0;
0390 
0391     list_add_tail(&entries[0], &list1);
0392     list_add_tail(&entries[1], &list1);
0393     list_add_tail(&entries[2], &list1);
0394 
0395     /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */
0396     list_cut_position(&list2, &list1, &entries[1]);
0397     /* after: [list2] -> entries[0] -> entries[1], [list1] -> entries[2] */
0398 
0399     list_for_each(cur, &list2) {
0400         KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
0401         i++;
0402     }
0403 
0404     KUNIT_EXPECT_EQ(test, i, 2);
0405 
0406     list_for_each(cur, &list1) {
0407         KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
0408         i++;
0409     }
0410 }
0411 
0412 static void list_test_list_cut_before(struct kunit *test)
0413 {
0414     struct list_head entries[3], *cur;
0415     LIST_HEAD(list1);
0416     LIST_HEAD(list2);
0417     int i = 0;
0418 
0419     list_add_tail(&entries[0], &list1);
0420     list_add_tail(&entries[1], &list1);
0421     list_add_tail(&entries[2], &list1);
0422 
0423     /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */
0424     list_cut_before(&list2, &list1, &entries[1]);
0425     /* after: [list2] -> entries[0], [list1] -> entries[1] -> entries[2] */
0426 
0427     list_for_each(cur, &list2) {
0428         KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
0429         i++;
0430     }
0431 
0432     KUNIT_EXPECT_EQ(test, i, 1);
0433 
0434     list_for_each(cur, &list1) {
0435         KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
0436         i++;
0437     }
0438 }
0439 
0440 static void list_test_list_splice(struct kunit *test)
0441 {
0442     struct list_head entries[5], *cur;
0443     LIST_HEAD(list1);
0444     LIST_HEAD(list2);
0445     int i = 0;
0446 
0447     list_add_tail(&entries[0], &list1);
0448     list_add_tail(&entries[1], &list1);
0449     list_add_tail(&entries[2], &list2);
0450     list_add_tail(&entries[3], &list2);
0451     list_add_tail(&entries[4], &list1);
0452 
0453     /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
0454     list_splice(&list2, &entries[1]);
0455     /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */
0456 
0457     list_for_each(cur, &list1) {
0458         KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
0459         i++;
0460     }
0461 
0462     KUNIT_EXPECT_EQ(test, i, 5);
0463 }
0464 
0465 static void list_test_list_splice_tail(struct kunit *test)
0466 {
0467     struct list_head entries[5], *cur;
0468     LIST_HEAD(list1);
0469     LIST_HEAD(list2);
0470     int i = 0;
0471 
0472     list_add_tail(&entries[0], &list1);
0473     list_add_tail(&entries[1], &list1);
0474     list_add_tail(&entries[2], &list2);
0475     list_add_tail(&entries[3], &list2);
0476     list_add_tail(&entries[4], &list1);
0477 
0478     /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
0479     list_splice_tail(&list2, &entries[4]);
0480     /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */
0481 
0482     list_for_each(cur, &list1) {
0483         KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
0484         i++;
0485     }
0486 
0487     KUNIT_EXPECT_EQ(test, i, 5);
0488 }
0489 
0490 static void list_test_list_splice_init(struct kunit *test)
0491 {
0492     struct list_head entries[5], *cur;
0493     LIST_HEAD(list1);
0494     LIST_HEAD(list2);
0495     int i = 0;
0496 
0497     list_add_tail(&entries[0], &list1);
0498     list_add_tail(&entries[1], &list1);
0499     list_add_tail(&entries[2], &list2);
0500     list_add_tail(&entries[3], &list2);
0501     list_add_tail(&entries[4], &list1);
0502 
0503     /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
0504     list_splice_init(&list2, &entries[1]);
0505     /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */
0506 
0507     list_for_each(cur, &list1) {
0508         KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
0509         i++;
0510     }
0511 
0512     KUNIT_EXPECT_EQ(test, i, 5);
0513 
0514     KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
0515 }
0516 
0517 static void list_test_list_splice_tail_init(struct kunit *test)
0518 {
0519     struct list_head entries[5], *cur;
0520     LIST_HEAD(list1);
0521     LIST_HEAD(list2);
0522     int i = 0;
0523 
0524     list_add_tail(&entries[0], &list1);
0525     list_add_tail(&entries[1], &list1);
0526     list_add_tail(&entries[2], &list2);
0527     list_add_tail(&entries[3], &list2);
0528     list_add_tail(&entries[4], &list1);
0529 
0530     /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */
0531     list_splice_tail_init(&list2, &entries[4]);
0532     /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */
0533 
0534     list_for_each(cur, &list1) {
0535         KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
0536         i++;
0537     }
0538 
0539     KUNIT_EXPECT_EQ(test, i, 5);
0540 
0541     KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2));
0542 }
0543 
0544 static void list_test_list_entry(struct kunit *test)
0545 {
0546     struct list_test_struct test_struct;
0547 
0548     KUNIT_EXPECT_PTR_EQ(test, &test_struct, list_entry(&(test_struct.list),
0549                 struct list_test_struct, list));
0550 }
0551 
0552 static void list_test_list_entry_is_head(struct kunit *test)
0553 {
0554     struct list_test_struct test_struct1, test_struct2, test_struct3;
0555 
0556     INIT_LIST_HEAD(&test_struct1.list);
0557     INIT_LIST_HEAD(&test_struct3.list);
0558 
0559     list_add_tail(&test_struct2.list, &test_struct1.list);
0560 
0561     KUNIT_EXPECT_TRUE_MSG(test,
0562         list_entry_is_head((&test_struct1), &test_struct1.list, list),
0563         "Head element of same list");
0564     KUNIT_EXPECT_FALSE_MSG(test,
0565         list_entry_is_head((&test_struct2), &test_struct1.list, list),
0566         "Non-head element of same list");
0567     KUNIT_EXPECT_FALSE_MSG(test,
0568         list_entry_is_head((&test_struct3), &test_struct1.list, list),
0569         "Head element of different list");
0570 }
0571 
0572 static void list_test_list_first_entry(struct kunit *test)
0573 {
0574     struct list_test_struct test_struct1, test_struct2;
0575     LIST_HEAD(list);
0576 
0577     list_add_tail(&test_struct1.list, &list);
0578     list_add_tail(&test_struct2.list, &list);
0579 
0580 
0581     KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_first_entry(&list,
0582                 struct list_test_struct, list));
0583 }
0584 
0585 static void list_test_list_last_entry(struct kunit *test)
0586 {
0587     struct list_test_struct test_struct1, test_struct2;
0588     LIST_HEAD(list);
0589 
0590     list_add_tail(&test_struct1.list, &list);
0591     list_add_tail(&test_struct2.list, &list);
0592 
0593 
0594     KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_last_entry(&list,
0595                 struct list_test_struct, list));
0596 }
0597 
0598 static void list_test_list_first_entry_or_null(struct kunit *test)
0599 {
0600     struct list_test_struct test_struct1, test_struct2;
0601     LIST_HEAD(list);
0602 
0603     KUNIT_EXPECT_FALSE(test, list_first_entry_or_null(&list,
0604                 struct list_test_struct, list));
0605 
0606     list_add_tail(&test_struct1.list, &list);
0607     list_add_tail(&test_struct2.list, &list);
0608 
0609     KUNIT_EXPECT_PTR_EQ(test, &test_struct1,
0610             list_first_entry_or_null(&list,
0611                 struct list_test_struct, list));
0612 }
0613 
0614 static void list_test_list_next_entry(struct kunit *test)
0615 {
0616     struct list_test_struct test_struct1, test_struct2;
0617     LIST_HEAD(list);
0618 
0619     list_add_tail(&test_struct1.list, &list);
0620     list_add_tail(&test_struct2.list, &list);
0621 
0622 
0623     KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_next_entry(&test_struct1,
0624                 list));
0625 }
0626 
0627 static void list_test_list_prev_entry(struct kunit *test)
0628 {
0629     struct list_test_struct test_struct1, test_struct2;
0630     LIST_HEAD(list);
0631 
0632     list_add_tail(&test_struct1.list, &list);
0633     list_add_tail(&test_struct2.list, &list);
0634 
0635 
0636     KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_prev_entry(&test_struct2,
0637                 list));
0638 }
0639 
0640 static void list_test_list_for_each(struct kunit *test)
0641 {
0642     struct list_head entries[3], *cur;
0643     LIST_HEAD(list);
0644     int i = 0;
0645 
0646     list_add_tail(&entries[0], &list);
0647     list_add_tail(&entries[1], &list);
0648     list_add_tail(&entries[2], &list);
0649 
0650     list_for_each(cur, &list) {
0651         KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
0652         i++;
0653     }
0654 
0655     KUNIT_EXPECT_EQ(test, i, 3);
0656 }
0657 
0658 static void list_test_list_for_each_prev(struct kunit *test)
0659 {
0660     struct list_head entries[3], *cur;
0661     LIST_HEAD(list);
0662     int i = 2;
0663 
0664     list_add_tail(&entries[0], &list);
0665     list_add_tail(&entries[1], &list);
0666     list_add_tail(&entries[2], &list);
0667 
0668     list_for_each_prev(cur, &list) {
0669         KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
0670         i--;
0671     }
0672 
0673     KUNIT_EXPECT_EQ(test, i, -1);
0674 }
0675 
0676 static void list_test_list_for_each_safe(struct kunit *test)
0677 {
0678     struct list_head entries[3], *cur, *n;
0679     LIST_HEAD(list);
0680     int i = 0;
0681 
0682 
0683     list_add_tail(&entries[0], &list);
0684     list_add_tail(&entries[1], &list);
0685     list_add_tail(&entries[2], &list);
0686 
0687     list_for_each_safe(cur, n, &list) {
0688         KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
0689         list_del(&entries[i]);
0690         i++;
0691     }
0692 
0693     KUNIT_EXPECT_EQ(test, i, 3);
0694     KUNIT_EXPECT_TRUE(test, list_empty(&list));
0695 }
0696 
0697 static void list_test_list_for_each_prev_safe(struct kunit *test)
0698 {
0699     struct list_head entries[3], *cur, *n;
0700     LIST_HEAD(list);
0701     int i = 2;
0702 
0703     list_add_tail(&entries[0], &list);
0704     list_add_tail(&entries[1], &list);
0705     list_add_tail(&entries[2], &list);
0706 
0707     list_for_each_prev_safe(cur, n, &list) {
0708         KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
0709         list_del(&entries[i]);
0710         i--;
0711     }
0712 
0713     KUNIT_EXPECT_EQ(test, i, -1);
0714     KUNIT_EXPECT_TRUE(test, list_empty(&list));
0715 }
0716 
0717 static void list_test_list_for_each_entry(struct kunit *test)
0718 {
0719     struct list_test_struct entries[5], *cur;
0720     LIST_HEAD(list);
0721     int i = 0;
0722 
0723     for (i = 0; i < 5; ++i) {
0724         entries[i].data = i;
0725         list_add_tail(&entries[i].list, &list);
0726     }
0727 
0728     i = 0;
0729 
0730     list_for_each_entry(cur, &list, list) {
0731         KUNIT_EXPECT_EQ(test, cur->data, i);
0732         i++;
0733     }
0734 
0735     KUNIT_EXPECT_EQ(test, i, 5);
0736 }
0737 
0738 static void list_test_list_for_each_entry_reverse(struct kunit *test)
0739 {
0740     struct list_test_struct entries[5], *cur;
0741     LIST_HEAD(list);
0742     int i = 0;
0743 
0744     for (i = 0; i < 5; ++i) {
0745         entries[i].data = i;
0746         list_add_tail(&entries[i].list, &list);
0747     }
0748 
0749     i = 4;
0750 
0751     list_for_each_entry_reverse(cur, &list, list) {
0752         KUNIT_EXPECT_EQ(test, cur->data, i);
0753         i--;
0754     }
0755 
0756     KUNIT_EXPECT_EQ(test, i, -1);
0757 }
0758 
0759 static struct kunit_case list_test_cases[] = {
0760     KUNIT_CASE(list_test_list_init),
0761     KUNIT_CASE(list_test_list_add),
0762     KUNIT_CASE(list_test_list_add_tail),
0763     KUNIT_CASE(list_test_list_del),
0764     KUNIT_CASE(list_test_list_replace),
0765     KUNIT_CASE(list_test_list_replace_init),
0766     KUNIT_CASE(list_test_list_swap),
0767     KUNIT_CASE(list_test_list_del_init),
0768     KUNIT_CASE(list_test_list_del_init_careful),
0769     KUNIT_CASE(list_test_list_move),
0770     KUNIT_CASE(list_test_list_move_tail),
0771     KUNIT_CASE(list_test_list_bulk_move_tail),
0772     KUNIT_CASE(list_test_list_is_head),
0773     KUNIT_CASE(list_test_list_is_first),
0774     KUNIT_CASE(list_test_list_is_last),
0775     KUNIT_CASE(list_test_list_empty),
0776     KUNIT_CASE(list_test_list_empty_careful),
0777     KUNIT_CASE(list_test_list_rotate_left),
0778     KUNIT_CASE(list_test_list_rotate_to_front),
0779     KUNIT_CASE(list_test_list_is_singular),
0780     KUNIT_CASE(list_test_list_cut_position),
0781     KUNIT_CASE(list_test_list_cut_before),
0782     KUNIT_CASE(list_test_list_splice),
0783     KUNIT_CASE(list_test_list_splice_tail),
0784     KUNIT_CASE(list_test_list_splice_init),
0785     KUNIT_CASE(list_test_list_splice_tail_init),
0786     KUNIT_CASE(list_test_list_entry),
0787     KUNIT_CASE(list_test_list_entry_is_head),
0788     KUNIT_CASE(list_test_list_first_entry),
0789     KUNIT_CASE(list_test_list_last_entry),
0790     KUNIT_CASE(list_test_list_first_entry_or_null),
0791     KUNIT_CASE(list_test_list_next_entry),
0792     KUNIT_CASE(list_test_list_prev_entry),
0793     KUNIT_CASE(list_test_list_for_each),
0794     KUNIT_CASE(list_test_list_for_each_prev),
0795     KUNIT_CASE(list_test_list_for_each_safe),
0796     KUNIT_CASE(list_test_list_for_each_prev_safe),
0797     KUNIT_CASE(list_test_list_for_each_entry),
0798     KUNIT_CASE(list_test_list_for_each_entry_reverse),
0799     {},
0800 };
0801 
0802 static struct kunit_suite list_test_module = {
0803     .name = "list-kunit-test",
0804     .test_cases = list_test_cases,
0805 };
0806 
0807 struct hlist_test_struct {
0808     int data;
0809     struct hlist_node list;
0810 };
0811 
0812 static void hlist_test_init(struct kunit *test)
0813 {
0814     /* Test the different ways of initialising a list. */
0815     struct hlist_head list1 = HLIST_HEAD_INIT;
0816     struct hlist_head list2;
0817     HLIST_HEAD(list3);
0818     struct hlist_head *list4;
0819     struct hlist_head *list5;
0820 
0821     INIT_HLIST_HEAD(&list2);
0822 
0823     list4 = kzalloc(sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL);
0824     INIT_HLIST_HEAD(list4);
0825 
0826     list5 = kmalloc(sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL);
0827     memset(list5, 0xFF, sizeof(*list5));
0828     INIT_HLIST_HEAD(list5);
0829 
0830     KUNIT_EXPECT_TRUE(test, hlist_empty(&list1));
0831     KUNIT_EXPECT_TRUE(test, hlist_empty(&list2));
0832     KUNIT_EXPECT_TRUE(test, hlist_empty(&list3));
0833     KUNIT_EXPECT_TRUE(test, hlist_empty(list4));
0834     KUNIT_EXPECT_TRUE(test, hlist_empty(list5));
0835 
0836     kfree(list4);
0837     kfree(list5);
0838 }
0839 
0840 static void hlist_test_unhashed(struct kunit *test)
0841 {
0842     struct hlist_node a;
0843     HLIST_HEAD(list);
0844 
0845     INIT_HLIST_NODE(&a);
0846 
0847     /* is unhashed by default */
0848     KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a));
0849 
0850     hlist_add_head(&a, &list);
0851 
0852     /* is hashed once added to list */
0853     KUNIT_EXPECT_FALSE(test, hlist_unhashed(&a));
0854 
0855     hlist_del_init(&a);
0856 
0857     /* is again unhashed after del_init */
0858     KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a));
0859 }
0860 
0861 /* Doesn't test concurrency guarantees */
0862 static void hlist_test_unhashed_lockless(struct kunit *test)
0863 {
0864     struct hlist_node a;
0865     HLIST_HEAD(list);
0866 
0867     INIT_HLIST_NODE(&a);
0868 
0869     /* is unhashed by default */
0870     KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a));
0871 
0872     hlist_add_head(&a, &list);
0873 
0874     /* is hashed once added to list */
0875     KUNIT_EXPECT_FALSE(test, hlist_unhashed_lockless(&a));
0876 
0877     hlist_del_init(&a);
0878 
0879     /* is again unhashed after del_init */
0880     KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a));
0881 }
0882 
0883 static void hlist_test_del(struct kunit *test)
0884 {
0885     struct hlist_node a, b;
0886     HLIST_HEAD(list);
0887 
0888     hlist_add_head(&a, &list);
0889     hlist_add_behind(&b, &a);
0890 
0891     /* before: [list] -> a -> b */
0892     hlist_del(&a);
0893 
0894     /* now: [list] -> b */
0895     KUNIT_EXPECT_PTR_EQ(test, list.first, &b);
0896     KUNIT_EXPECT_PTR_EQ(test, b.pprev, &list.first);
0897 }
0898 
0899 static void hlist_test_del_init(struct kunit *test)
0900 {
0901     struct hlist_node a, b;
0902     HLIST_HEAD(list);
0903 
0904     hlist_add_head(&a, &list);
0905     hlist_add_behind(&b, &a);
0906 
0907     /* before: [list] -> a -> b */
0908     hlist_del_init(&a);
0909 
0910     /* now: [list] -> b */
0911     KUNIT_EXPECT_PTR_EQ(test, list.first, &b);
0912     KUNIT_EXPECT_PTR_EQ(test, b.pprev, &list.first);
0913 
0914     /* a is now initialised */
0915     KUNIT_EXPECT_PTR_EQ(test, a.next, NULL);
0916     KUNIT_EXPECT_PTR_EQ(test, a.pprev, NULL);
0917 }
0918 
0919 /* Tests all three hlist_add_* functions */
0920 static void hlist_test_add(struct kunit *test)
0921 {
0922     struct hlist_node a, b, c, d;
0923     HLIST_HEAD(list);
0924 
0925     hlist_add_head(&a, &list);
0926     hlist_add_head(&b, &list);
0927     hlist_add_before(&c, &a);
0928     hlist_add_behind(&d, &a);
0929 
0930     /* should be [list] -> b -> c -> a -> d */
0931     KUNIT_EXPECT_PTR_EQ(test, list.first, &b);
0932 
0933     KUNIT_EXPECT_PTR_EQ(test, c.pprev, &(b.next));
0934     KUNIT_EXPECT_PTR_EQ(test, b.next, &c);
0935 
0936     KUNIT_EXPECT_PTR_EQ(test, a.pprev, &(c.next));
0937     KUNIT_EXPECT_PTR_EQ(test, c.next, &a);
0938 
0939     KUNIT_EXPECT_PTR_EQ(test, d.pprev, &(a.next));
0940     KUNIT_EXPECT_PTR_EQ(test, a.next, &d);
0941 }
0942 
0943 /* Tests both hlist_fake() and hlist_add_fake() */
0944 static void hlist_test_fake(struct kunit *test)
0945 {
0946     struct hlist_node a;
0947 
0948     INIT_HLIST_NODE(&a);
0949 
0950     /* not fake after init */
0951     KUNIT_EXPECT_FALSE(test, hlist_fake(&a));
0952 
0953     hlist_add_fake(&a);
0954 
0955     /* is now fake */
0956     KUNIT_EXPECT_TRUE(test, hlist_fake(&a));
0957 }
0958 
0959 static void hlist_test_is_singular_node(struct kunit *test)
0960 {
0961     struct hlist_node a, b;
0962     HLIST_HEAD(list);
0963 
0964     INIT_HLIST_NODE(&a);
0965     KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list));
0966 
0967     hlist_add_head(&a, &list);
0968     KUNIT_EXPECT_TRUE(test, hlist_is_singular_node(&a, &list));
0969 
0970     hlist_add_head(&b, &list);
0971     KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list));
0972     KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&b, &list));
0973 }
0974 
0975 static void hlist_test_empty(struct kunit *test)
0976 {
0977     struct hlist_node a;
0978     HLIST_HEAD(list);
0979 
0980     /* list starts off empty */
0981     KUNIT_EXPECT_TRUE(test, hlist_empty(&list));
0982 
0983     hlist_add_head(&a, &list);
0984 
0985     /* list is no longer empty */
0986     KUNIT_EXPECT_FALSE(test, hlist_empty(&list));
0987 }
0988 
0989 static void hlist_test_move_list(struct kunit *test)
0990 {
0991     struct hlist_node a;
0992     HLIST_HEAD(list1);
0993     HLIST_HEAD(list2);
0994 
0995     hlist_add_head(&a, &list1);
0996 
0997     KUNIT_EXPECT_FALSE(test, hlist_empty(&list1));
0998     KUNIT_EXPECT_TRUE(test, hlist_empty(&list2));
0999     hlist_move_list(&list1, &list2);
1000     KUNIT_EXPECT_TRUE(test, hlist_empty(&list1));
1001     KUNIT_EXPECT_FALSE(test, hlist_empty(&list2));
1002 
1003 }
1004 
1005 static void hlist_test_entry(struct kunit *test)
1006 {
1007     struct hlist_test_struct test_struct;
1008 
1009     KUNIT_EXPECT_PTR_EQ(test, &test_struct,
1010                 hlist_entry(&(test_struct.list),
1011                 struct hlist_test_struct, list));
1012 }
1013 
1014 static void hlist_test_entry_safe(struct kunit *test)
1015 {
1016     struct hlist_test_struct test_struct;
1017 
1018     KUNIT_EXPECT_PTR_EQ(test, &test_struct,
1019                 hlist_entry_safe(&(test_struct.list),
1020                 struct hlist_test_struct, list));
1021 
1022     KUNIT_EXPECT_PTR_EQ(test, NULL,
1023                 hlist_entry_safe((struct hlist_node *)NULL,
1024                 struct hlist_test_struct, list));
1025 }
1026 
1027 static void hlist_test_for_each(struct kunit *test)
1028 {
1029     struct hlist_node entries[3], *cur;
1030     HLIST_HEAD(list);
1031     int i = 0;
1032 
1033     hlist_add_head(&entries[0], &list);
1034     hlist_add_behind(&entries[1], &entries[0]);
1035     hlist_add_behind(&entries[2], &entries[1]);
1036 
1037     hlist_for_each(cur, &list) {
1038         KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
1039         i++;
1040     }
1041 
1042     KUNIT_EXPECT_EQ(test, i, 3);
1043 }
1044 
1045 
1046 static void hlist_test_for_each_safe(struct kunit *test)
1047 {
1048     struct hlist_node entries[3], *cur, *n;
1049     HLIST_HEAD(list);
1050     int i = 0;
1051 
1052     hlist_add_head(&entries[0], &list);
1053     hlist_add_behind(&entries[1], &entries[0]);
1054     hlist_add_behind(&entries[2], &entries[1]);
1055 
1056     hlist_for_each_safe(cur, n, &list) {
1057         KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]);
1058         hlist_del(&entries[i]);
1059         i++;
1060     }
1061 
1062     KUNIT_EXPECT_EQ(test, i, 3);
1063     KUNIT_EXPECT_TRUE(test, hlist_empty(&list));
1064 }
1065 
1066 static void hlist_test_for_each_entry(struct kunit *test)
1067 {
1068     struct hlist_test_struct entries[5], *cur;
1069     HLIST_HEAD(list);
1070     int i = 0;
1071 
1072     entries[0].data = 0;
1073     hlist_add_head(&entries[0].list, &list);
1074     for (i = 1; i < 5; ++i) {
1075         entries[i].data = i;
1076         hlist_add_behind(&entries[i].list, &entries[i-1].list);
1077     }
1078 
1079     i = 0;
1080 
1081     hlist_for_each_entry(cur, &list, list) {
1082         KUNIT_EXPECT_EQ(test, cur->data, i);
1083         i++;
1084     }
1085 
1086     KUNIT_EXPECT_EQ(test, i, 5);
1087 }
1088 
1089 static void hlist_test_for_each_entry_continue(struct kunit *test)
1090 {
1091     struct hlist_test_struct entries[5], *cur;
1092     HLIST_HEAD(list);
1093     int i = 0;
1094 
1095     entries[0].data = 0;
1096     hlist_add_head(&entries[0].list, &list);
1097     for (i = 1; i < 5; ++i) {
1098         entries[i].data = i;
1099         hlist_add_behind(&entries[i].list, &entries[i-1].list);
1100     }
1101 
1102     /* We skip the first (zero-th) entry. */
1103     i = 1;
1104 
1105     cur = &entries[0];
1106     hlist_for_each_entry_continue(cur, list) {
1107         KUNIT_EXPECT_EQ(test, cur->data, i);
1108         /* Stamp over the entry. */
1109         cur->data = 42;
1110         i++;
1111     }
1112 
1113     KUNIT_EXPECT_EQ(test, i, 5);
1114     /* The first entry was not visited. */
1115     KUNIT_EXPECT_EQ(test, entries[0].data, 0);
1116     /* The second (and presumably others), were. */
1117     KUNIT_EXPECT_EQ(test, entries[1].data, 42);
1118 }
1119 
1120 static void hlist_test_for_each_entry_from(struct kunit *test)
1121 {
1122     struct hlist_test_struct entries[5], *cur;
1123     HLIST_HEAD(list);
1124     int i = 0;
1125 
1126     entries[0].data = 0;
1127     hlist_add_head(&entries[0].list, &list);
1128     for (i = 1; i < 5; ++i) {
1129         entries[i].data = i;
1130         hlist_add_behind(&entries[i].list, &entries[i-1].list);
1131     }
1132 
1133     i = 0;
1134 
1135     cur = &entries[0];
1136     hlist_for_each_entry_from(cur, list) {
1137         KUNIT_EXPECT_EQ(test, cur->data, i);
1138         /* Stamp over the entry. */
1139         cur->data = 42;
1140         i++;
1141     }
1142 
1143     KUNIT_EXPECT_EQ(test, i, 5);
1144     /* The first entry was visited. */
1145     KUNIT_EXPECT_EQ(test, entries[0].data, 42);
1146 }
1147 
1148 static void hlist_test_for_each_entry_safe(struct kunit *test)
1149 {
1150     struct hlist_test_struct entries[5], *cur;
1151     struct hlist_node *tmp_node;
1152     HLIST_HEAD(list);
1153     int i = 0;
1154 
1155     entries[0].data = 0;
1156     hlist_add_head(&entries[0].list, &list);
1157     for (i = 1; i < 5; ++i) {
1158         entries[i].data = i;
1159         hlist_add_behind(&entries[i].list, &entries[i-1].list);
1160     }
1161 
1162     i = 0;
1163 
1164     hlist_for_each_entry_safe(cur, tmp_node, &list, list) {
1165         KUNIT_EXPECT_EQ(test, cur->data, i);
1166         hlist_del(&cur->list);
1167         i++;
1168     }
1169 
1170     KUNIT_EXPECT_EQ(test, i, 5);
1171     KUNIT_EXPECT_TRUE(test, hlist_empty(&list));
1172 }
1173 
1174 
1175 static struct kunit_case hlist_test_cases[] = {
1176     KUNIT_CASE(hlist_test_init),
1177     KUNIT_CASE(hlist_test_unhashed),
1178     KUNIT_CASE(hlist_test_unhashed_lockless),
1179     KUNIT_CASE(hlist_test_del),
1180     KUNIT_CASE(hlist_test_del_init),
1181     KUNIT_CASE(hlist_test_add),
1182     KUNIT_CASE(hlist_test_fake),
1183     KUNIT_CASE(hlist_test_is_singular_node),
1184     KUNIT_CASE(hlist_test_empty),
1185     KUNIT_CASE(hlist_test_move_list),
1186     KUNIT_CASE(hlist_test_entry),
1187     KUNIT_CASE(hlist_test_entry_safe),
1188     KUNIT_CASE(hlist_test_for_each),
1189     KUNIT_CASE(hlist_test_for_each_safe),
1190     KUNIT_CASE(hlist_test_for_each_entry),
1191     KUNIT_CASE(hlist_test_for_each_entry_continue),
1192     KUNIT_CASE(hlist_test_for_each_entry_from),
1193     KUNIT_CASE(hlist_test_for_each_entry_safe),
1194     {},
1195 };
1196 
1197 static struct kunit_suite hlist_test_module = {
1198     .name = "hlist",
1199     .test_cases = hlist_test_cases,
1200 };
1201 
1202 kunit_test_suites(&list_test_module, &hlist_test_module);
1203 
1204 MODULE_LICENSE("GPL v2");
[ Source navigation ] [ Diff markup ] [ Identifier search ] [ general search ]

This page was automatically generated by the 2.1.0 LXR engine.

The LXR team
Valid CSS 2.1! Valid HTML 4.01!