From d7fd696c12605b1666e9a2051e2ac896af103bfe Mon Sep 17 00:00:00 2001 From: David Gow Date: Fri, 25 Feb 2022 10:52:46 +0800 Subject: list: test: Add test for list_del_init_careful() The list_del_init_careful() function was added[1] after the list KUnit test. Add a very basic test to cover it. Note that this test only covers the single-threaded behaviour (which matches list_del_init()), as is already the case with the test for list_empty_careful(). [1]: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=c6fe44d96fc1536af5b11cd859686453d1b7bfd1 Signed-off-by: David Gow Reviewed-by: Andy Shevchenko Signed-off-by: Shuah Khan --- lib/list-test.c | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) (limited to 'lib/list-test.c') diff --git a/lib/list-test.c b/lib/list-test.c index ee09505df16f..302b7382bff4 100644 --- a/lib/list-test.c +++ b/lib/list-test.c @@ -161,6 +161,26 @@ static void list_test_list_del_init(struct kunit *test) KUNIT_EXPECT_TRUE(test, list_empty_careful(&a)); } +static void list_test_list_del_init_careful(struct kunit *test) +{ + /* NOTE: This test only checks the behaviour of this function in + * isolation. It does not verify memory model guarantees. + */ + struct list_head a, b; + LIST_HEAD(list); + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + + /* before: [list] -> a -> b */ + list_del_init_careful(&a); + /* after: [list] -> b, a initialised */ + + KUNIT_EXPECT_PTR_EQ(test, list.next, &b); + KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); + KUNIT_EXPECT_TRUE(test, list_empty_careful(&a)); +} + static void list_test_list_move(struct kunit *test) { struct list_head a, b; @@ -707,6 +727,7 @@ static struct kunit_case list_test_cases[] = { KUNIT_CASE(list_test_list_replace_init), KUNIT_CASE(list_test_list_swap), KUNIT_CASE(list_test_list_del_init), + KUNIT_CASE(list_test_list_del_init_careful), KUNIT_CASE(list_test_list_move), KUNIT_CASE(list_test_list_move_tail), KUNIT_CASE(list_test_list_bulk_move_tail), -- cgit From 37dc573c0a547e1aed0c9abb480fab797bd3833f Mon Sep 17 00:00:00 2001 From: David Gow Date: Fri, 25 Feb 2022 10:52:48 +0800 Subject: list: test: Add a test for list_is_head() list_is_head() was added recently[1], and didn't have a KUnit test. The implementation is trivial, so it's not a particularly exciting test, but it'd be nice to get back to full coverage of the list functions. [1]: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/include/linux/list.h?id=0425473037db40d9e322631f2d4dc6ef51f97e88 Signed-off-by: David Gow Acked-by: Daniel Latypov Acked-by: Brendan Higgins Reviewed-by: Andy Shevchenko Signed-off-by: Shuah Khan --- lib/list-test.c | 19 +++++++++++++++++++ 1 file changed, 19 insertions(+) (limited to 'lib/list-test.c') diff --git a/lib/list-test.c b/lib/list-test.c index 302b7382bff4..3870ebfd84aa 100644 --- a/lib/list-test.c +++ b/lib/list-test.c @@ -254,6 +254,24 @@ static void list_test_list_bulk_move_tail(struct kunit *test) KUNIT_EXPECT_EQ(test, i, 2); } +static void list_test_list_is_head(struct kunit *test) +{ + struct list_head a, b, c; + + /* Two lists: [a] -> b, [c] */ + INIT_LIST_HEAD(&a); + INIT_LIST_HEAD(&c); + list_add_tail(&b, &a); + + KUNIT_EXPECT_TRUE_MSG(test, list_is_head(&a, &a), + "Head element of same list"); + KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &b), + "Non-head element of same list"); + KUNIT_EXPECT_FALSE_MSG(test, list_is_head(&a, &c), + "Head element of different list"); +} + + static void list_test_list_is_first(struct kunit *test) { struct list_head a, b; @@ -731,6 +749,7 @@ static struct kunit_case list_test_cases[] = { KUNIT_CASE(list_test_list_move), KUNIT_CASE(list_test_list_move_tail), KUNIT_CASE(list_test_list_bulk_move_tail), + KUNIT_CASE(list_test_list_is_head), KUNIT_CASE(list_test_list_is_first), KUNIT_CASE(list_test_list_is_last), KUNIT_CASE(list_test_list_empty), -- cgit From 5debe5bfa02c4c8922bd2d0f82c9c3a70bec8944 Mon Sep 17 00:00:00 2001 From: David Gow Date: Fri, 25 Feb 2022 10:52:49 +0800 Subject: list: test: Add a test for list_entry_is_head() The list_entry_is_head() macro was added[1] after the list KUnit tests, so wasn't tested. Add a new KUnit test to complete the set. [1]: https://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git/commit/?id=e130816164e244b692921de49771eeb28205152d Signed-off-by: David Gow Acked-by: Daniel Latypov Acked-by: Brendan Higgins Reviewed-by: Andy Shevchenko Signed-off-by: Shuah Khan --- lib/list-test.c | 21 +++++++++++++++++++++ 1 file changed, 21 insertions(+) (limited to 'lib/list-test.c') diff --git a/lib/list-test.c b/lib/list-test.c index 3870ebfd84aa..035ef6597640 100644 --- a/lib/list-test.c +++ b/lib/list-test.c @@ -549,6 +549,26 @@ static void list_test_list_entry(struct kunit *test) struct list_test_struct, list)); } +static void list_test_list_entry_is_head(struct kunit *test) +{ + struct list_test_struct test_struct1, test_struct2, test_struct3; + + INIT_LIST_HEAD(&test_struct1.list); + INIT_LIST_HEAD(&test_struct3.list); + + list_add_tail(&test_struct2.list, &test_struct1.list); + + KUNIT_EXPECT_TRUE_MSG(test, + list_entry_is_head((&test_struct1), &test_struct1.list, list), + "Head element of same list"); + KUNIT_EXPECT_FALSE_MSG(test, + list_entry_is_head((&test_struct2), &test_struct1.list, list), + "Non-head element of same list"); + KUNIT_EXPECT_FALSE_MSG(test, + list_entry_is_head((&test_struct3), &test_struct1.list, list), + "Head element of different list"); +} + static void list_test_list_first_entry(struct kunit *test) { struct list_test_struct test_struct1, test_struct2; @@ -764,6 +784,7 @@ static struct kunit_case list_test_cases[] = { KUNIT_CASE(list_test_list_splice_init), KUNIT_CASE(list_test_list_splice_tail_init), KUNIT_CASE(list_test_list_entry), + KUNIT_CASE(list_test_list_entry_is_head), KUNIT_CASE(list_test_list_first_entry), KUNIT_CASE(list_test_list_last_entry), KUNIT_CASE(list_test_list_first_entry_or_null), -- cgit From 1ff522b6ef4b40e7f46a9d8efe7554b2f3d36311 Mon Sep 17 00:00:00 2001 From: David Gow Date: Sat, 5 Mar 2022 15:40:20 +0800 Subject: list: test: Test the hlist structure Add KUnit tests to the hlist linked-list structure which is used by hashtables. This should give coverage of every function and macro in list.h, as well as (combined with the KUnit tests for the hash functions) get very close to having tests for the hashtable structure. The tests here mirror the existing list tests, and are found in a new suite titled 'hlist'. Signed-off-by: David Gow Reviewed-by: Brendan Higgins Signed-off-by: Shuah Khan --- lib/list-test.c | 397 +++++++++++++++++++++++++++++++++++++++++++++++++++++++- 1 file changed, 396 insertions(+), 1 deletion(-) (limited to 'lib/list-test.c') diff --git a/lib/list-test.c b/lib/list-test.c index 035ef6597640..d374cf5d1a57 100644 --- a/lib/list-test.c +++ b/lib/list-test.c @@ -804,6 +804,401 @@ static struct kunit_suite list_test_module = { .test_cases = list_test_cases, }; -kunit_test_suites(&list_test_module); +struct hlist_test_struct { + int data; + struct hlist_node list; +}; + +static void hlist_test_init(struct kunit *test) +{ + /* Test the different ways of initialising a list. */ + struct hlist_head list1 = HLIST_HEAD_INIT; + struct hlist_head list2; + HLIST_HEAD(list3); + struct hlist_head *list4; + struct hlist_head *list5; + + INIT_HLIST_HEAD(&list2); + + list4 = kzalloc(sizeof(*list4), GFP_KERNEL | __GFP_NOFAIL); + INIT_HLIST_HEAD(list4); + + list5 = kmalloc(sizeof(*list5), GFP_KERNEL | __GFP_NOFAIL); + memset(list5, 0xFF, sizeof(*list5)); + INIT_HLIST_HEAD(list5); + + KUNIT_EXPECT_TRUE(test, hlist_empty(&list1)); + KUNIT_EXPECT_TRUE(test, hlist_empty(&list2)); + KUNIT_EXPECT_TRUE(test, hlist_empty(&list3)); + KUNIT_EXPECT_TRUE(test, hlist_empty(list4)); + KUNIT_EXPECT_TRUE(test, hlist_empty(list5)); + + kfree(list4); + kfree(list5); +} + +static void hlist_test_unhashed(struct kunit *test) +{ + struct hlist_node a; + HLIST_HEAD(list); + + INIT_HLIST_NODE(&a); + + /* is unhashed by default */ + KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a)); + + hlist_add_head(&a, &list); + + /* is hashed once added to list */ + KUNIT_EXPECT_FALSE(test, hlist_unhashed(&a)); + + hlist_del_init(&a); + + /* is again unhashed after del_init */ + KUNIT_EXPECT_TRUE(test, hlist_unhashed(&a)); +} + +/* Doesn't test concurrency guarantees */ +static void hlist_test_unhashed_lockless(struct kunit *test) +{ + struct hlist_node a; + HLIST_HEAD(list); + + INIT_HLIST_NODE(&a); + + /* is unhashed by default */ + KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a)); + + hlist_add_head(&a, &list); + + /* is hashed once added to list */ + KUNIT_EXPECT_FALSE(test, hlist_unhashed_lockless(&a)); + + hlist_del_init(&a); + + /* is again unhashed after del_init */ + KUNIT_EXPECT_TRUE(test, hlist_unhashed_lockless(&a)); +} + +static void hlist_test_del(struct kunit *test) +{ + struct hlist_node a, b; + HLIST_HEAD(list); + + hlist_add_head(&a, &list); + hlist_add_behind(&b, &a); + + /* before: [list] -> a -> b */ + hlist_del(&a); + + /* now: [list] -> b */ + KUNIT_EXPECT_PTR_EQ(test, list.first, &b); + KUNIT_EXPECT_PTR_EQ(test, b.pprev, &list.first); +} + +static void hlist_test_del_init(struct kunit *test) +{ + struct hlist_node a, b; + HLIST_HEAD(list); + + hlist_add_head(&a, &list); + hlist_add_behind(&b, &a); + + /* before: [list] -> a -> b */ + hlist_del_init(&a); + + /* now: [list] -> b */ + KUNIT_EXPECT_PTR_EQ(test, list.first, &b); + KUNIT_EXPECT_PTR_EQ(test, b.pprev, &list.first); + + /* a is now initialised */ + KUNIT_EXPECT_PTR_EQ(test, a.next, NULL); + KUNIT_EXPECT_PTR_EQ(test, a.pprev, NULL); +} + +/* Tests all three hlist_add_* functions */ +static void hlist_test_add(struct kunit *test) +{ + struct hlist_node a, b, c, d; + HLIST_HEAD(list); + + hlist_add_head(&a, &list); + hlist_add_head(&b, &list); + hlist_add_before(&c, &a); + hlist_add_behind(&d, &a); + + /* should be [list] -> b -> c -> a -> d */ + KUNIT_EXPECT_PTR_EQ(test, list.first, &b); + + KUNIT_EXPECT_PTR_EQ(test, c.pprev, &(b.next)); + KUNIT_EXPECT_PTR_EQ(test, b.next, &c); + + KUNIT_EXPECT_PTR_EQ(test, a.pprev, &(c.next)); + KUNIT_EXPECT_PTR_EQ(test, c.next, &a); + + KUNIT_EXPECT_PTR_EQ(test, d.pprev, &(a.next)); + KUNIT_EXPECT_PTR_EQ(test, a.next, &d); +} + +/* Tests both hlist_fake() and hlist_add_fake() */ +static void hlist_test_fake(struct kunit *test) +{ + struct hlist_node a; + + INIT_HLIST_NODE(&a); + + /* not fake after init */ + KUNIT_EXPECT_FALSE(test, hlist_fake(&a)); + + hlist_add_fake(&a); + + /* is now fake */ + KUNIT_EXPECT_TRUE(test, hlist_fake(&a)); +} + +static void hlist_test_is_singular_node(struct kunit *test) +{ + struct hlist_node a, b; + HLIST_HEAD(list); + + INIT_HLIST_NODE(&a); + KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list)); + + hlist_add_head(&a, &list); + KUNIT_EXPECT_TRUE(test, hlist_is_singular_node(&a, &list)); + + hlist_add_head(&b, &list); + KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&a, &list)); + KUNIT_EXPECT_FALSE(test, hlist_is_singular_node(&b, &list)); +} + +static void hlist_test_empty(struct kunit *test) +{ + struct hlist_node a; + HLIST_HEAD(list); + + /* list starts off empty */ + KUNIT_EXPECT_TRUE(test, hlist_empty(&list)); + + hlist_add_head(&a, &list); + + /* list is no longer empty */ + KUNIT_EXPECT_FALSE(test, hlist_empty(&list)); +} + +static void hlist_test_move_list(struct kunit *test) +{ + struct hlist_node a; + HLIST_HEAD(list1); + HLIST_HEAD(list2); + + hlist_add_head(&a, &list1); + + KUNIT_EXPECT_FALSE(test, hlist_empty(&list1)); + KUNIT_EXPECT_TRUE(test, hlist_empty(&list2)); + hlist_move_list(&list1, &list2); + KUNIT_EXPECT_TRUE(test, hlist_empty(&list1)); + KUNIT_EXPECT_FALSE(test, hlist_empty(&list2)); + +} + +static void hlist_test_entry(struct kunit *test) +{ + struct hlist_test_struct test_struct; + + KUNIT_EXPECT_PTR_EQ(test, &test_struct, + hlist_entry(&(test_struct.list), + struct hlist_test_struct, list)); +} + +static void hlist_test_entry_safe(struct kunit *test) +{ + struct hlist_test_struct test_struct; + + KUNIT_EXPECT_PTR_EQ(test, &test_struct, + hlist_entry_safe(&(test_struct.list), + struct hlist_test_struct, list)); + + KUNIT_EXPECT_PTR_EQ(test, NULL, + hlist_entry_safe((struct hlist_node *)NULL, + struct hlist_test_struct, list)); +} + +static void hlist_test_for_each(struct kunit *test) +{ + struct hlist_node entries[3], *cur; + HLIST_HEAD(list); + int i = 0; + + hlist_add_head(&entries[0], &list); + hlist_add_behind(&entries[1], &entries[0]); + hlist_add_behind(&entries[2], &entries[1]); + + hlist_for_each(cur, &list) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 3); +} + + +static void hlist_test_for_each_safe(struct kunit *test) +{ + struct hlist_node entries[3], *cur, *n; + HLIST_HEAD(list); + int i = 0; + + hlist_add_head(&entries[0], &list); + hlist_add_behind(&entries[1], &entries[0]); + hlist_add_behind(&entries[2], &entries[1]); + + hlist_for_each_safe(cur, n, &list) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + hlist_del(&entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 3); + KUNIT_EXPECT_TRUE(test, hlist_empty(&list)); +} + +static void hlist_test_for_each_entry(struct kunit *test) +{ + struct hlist_test_struct entries[5], *cur; + HLIST_HEAD(list); + int i = 0; + + entries[0].data = 0; + hlist_add_head(&entries[0].list, &list); + for (i = 1; i < 5; ++i) { + entries[i].data = i; + hlist_add_behind(&entries[i].list, &entries[i-1].list); + } + + i = 0; + + hlist_for_each_entry(cur, &list, list) { + KUNIT_EXPECT_EQ(test, cur->data, i); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); +} + +static void hlist_test_for_each_entry_continue(struct kunit *test) +{ + struct hlist_test_struct entries[5], *cur; + HLIST_HEAD(list); + int i = 0; + + entries[0].data = 0; + hlist_add_head(&entries[0].list, &list); + for (i = 1; i < 5; ++i) { + entries[i].data = i; + hlist_add_behind(&entries[i].list, &entries[i-1].list); + } + + /* We skip the first (zero-th) entry. */ + i = 1; + + cur = &entries[0]; + hlist_for_each_entry_continue(cur, list) { + KUNIT_EXPECT_EQ(test, cur->data, i); + /* Stamp over the entry. */ + cur->data = 42; + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); + /* The first entry was not visited. */ + KUNIT_EXPECT_EQ(test, entries[0].data, 0); + /* The second (and presumably others), were. */ + KUNIT_EXPECT_EQ(test, entries[1].data, 42); +} + +static void hlist_test_for_each_entry_from(struct kunit *test) +{ + struct hlist_test_struct entries[5], *cur; + HLIST_HEAD(list); + int i = 0; + + entries[0].data = 0; + hlist_add_head(&entries[0].list, &list); + for (i = 1; i < 5; ++i) { + entries[i].data = i; + hlist_add_behind(&entries[i].list, &entries[i-1].list); + } + + i = 0; + + cur = &entries[0]; + hlist_for_each_entry_from(cur, list) { + KUNIT_EXPECT_EQ(test, cur->data, i); + /* Stamp over the entry. */ + cur->data = 42; + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); + /* The first entry was visited. */ + KUNIT_EXPECT_EQ(test, entries[0].data, 42); +} + +static void hlist_test_for_each_entry_safe(struct kunit *test) +{ + struct hlist_test_struct entries[5], *cur; + struct hlist_node *tmp_node; + HLIST_HEAD(list); + int i = 0; + + entries[0].data = 0; + hlist_add_head(&entries[0].list, &list); + for (i = 1; i < 5; ++i) { + entries[i].data = i; + hlist_add_behind(&entries[i].list, &entries[i-1].list); + } + + i = 0; + + hlist_for_each_entry_safe(cur, tmp_node, &list, list) { + KUNIT_EXPECT_EQ(test, cur->data, i); + hlist_del(&cur->list); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); + KUNIT_EXPECT_TRUE(test, hlist_empty(&list)); +} + + +static struct kunit_case hlist_test_cases[] = { + KUNIT_CASE(hlist_test_init), + KUNIT_CASE(hlist_test_unhashed), + KUNIT_CASE(hlist_test_unhashed_lockless), + KUNIT_CASE(hlist_test_del), + KUNIT_CASE(hlist_test_del_init), + KUNIT_CASE(hlist_test_add), + KUNIT_CASE(hlist_test_fake), + KUNIT_CASE(hlist_test_is_singular_node), + KUNIT_CASE(hlist_test_empty), + KUNIT_CASE(hlist_test_move_list), + KUNIT_CASE(hlist_test_entry), + KUNIT_CASE(hlist_test_entry_safe), + KUNIT_CASE(hlist_test_for_each), + KUNIT_CASE(hlist_test_for_each_safe), + KUNIT_CASE(hlist_test_for_each_entry), + KUNIT_CASE(hlist_test_for_each_entry_continue), + KUNIT_CASE(hlist_test_for_each_entry_from), + KUNIT_CASE(hlist_test_for_each_entry_safe), + {}, +}; + +static struct kunit_suite hlist_test_module = { + .name = "hlist", + .test_cases = hlist_test_cases, +}; + +kunit_test_suites(&list_test_module, &hlist_test_module); MODULE_LICENSE("GPL v2"); -- cgit