| Message ID | 20191007213633.92565-1-davidgow@google.com (mailing list archive) |
|---|---|
| State | New |
| Headers | show |
| Series | lib/list-test: add a test for the 'list' doubly linked list | expand |
On Mon, Oct 07, 2019 at 02:36:33PM -0700, David Gow wrote: > This change adds a KUnit test for the kernel doubly linked list > implementation in include/linux/list.h > > Note that, at present, it only tests the list_ types (not the > singly-linked hlist_), and does not yet test all of the > list_for_each_entry* macros (and some related things like > list_prepare_entry). > > This change depends on KUnit, so should be merged via the 'test' branch: > https://git.kernel.org/pub/scm/linux/kernel/git/shuah/linux-kselftest.git/log/?h=test Others might feel differently than me, but I think this should go in the comment section (below the "---"). > Signed-off-by: David Gow <davidgow@google.com> Reviewed-by: Brendan Higgins <brendanhiggins@google.com> Tested-by: Brendan Higgins <brendanhiggins@google.com> > --- > lib/Kconfig.debug | 12 + > lib/Makefile | 3 + > lib/list-test.c | 711 ++++++++++++++++++++++++++++++++++++++++++++++ > 3 files changed, 726 insertions(+) > create mode 100644 lib/list-test.c > > diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug > index a3017a5dadcd..60691c0aac3e 100644 > --- a/lib/Kconfig.debug > +++ b/lib/Kconfig.debug > @@ -1961,6 +1961,18 @@ config SYSCTL_KUNIT_TEST > > If unsure, say N. > > +config LIST_TEST > + bool "KUnit Test for Kernel Linked-list stuctures" > + depends on KUNIT > + help > + This builds the linked list unit test, which runs on boot. > + It tests that the API and basic functionality of the list_head type > + and associated macros. > + For more information on KUnit and unit tests in general please refer > + to the KUnit documentation in Documentation/dev-tools/kunit/. > + > + If unsure, say N. > + > config TEST_UDELAY > tristate "udelay test driver" > help > diff --git a/lib/Makefile b/lib/Makefile > index bba1fd5485f7..309e174ee35d 100644 > --- a/lib/Makefile > +++ b/lib/Makefile > @@ -292,3 +292,6 @@ obj-$(CONFIG_GENERIC_LIB_MULDI3) += muldi3.o > obj-$(CONFIG_GENERIC_LIB_CMPDI2) += cmpdi2.o > obj-$(CONFIG_GENERIC_LIB_UCMPDI2) += ucmpdi2.o > obj-$(CONFIG_OBJAGG) += objagg.o > + > +# KUnit tests > +obj-$(CONFIG_LIST_TEST) += list-test.o > diff --git a/lib/list-test.c b/lib/list-test.c > new file mode 100644 > index 000000000000..f333e8b0d9fe > --- /dev/null > +++ b/lib/list-test.c > @@ -0,0 +1,711 @@ > +// SPDX-License-Identifier: GPL-2.0 Might also want to add a bit more of a description here. Even if it is just something like "KUnit test for the doubly linked list data structure." Also: /* * <Insert description here.> * * Copyright (C) 2019, Google LLC. * Author: David Gow <davidgow@google.com> */ > +#include <kunit/test.h> > + > +#include <linux/list.h> > + > +struct list_test_struct { > + int data; > + struct list_head list; > +}; <snip> Thanks!
On Mon, Oct 07, 2019 at 02:36:33PM -0700, David Gow wrote: > This change adds a KUnit test for the kernel doubly linked list > implementation in include/linux/list.h > > Note that, at present, it only tests the list_ types (not the > singly-linked hlist_), and does not yet test all of the > list_for_each_entry* macros (and some related things like > list_prepare_entry). > > This change depends on KUnit, so should be merged via the 'test' branch: > https://git.kernel.org/pub/scm/linux/kernel/git/shuah/linux-kselftest.git/log/?h=test > > Signed-off-by: David Gow <davidgow@google.com> > --- > lib/Kconfig.debug | 12 + > lib/Makefile | 3 + > lib/list-test.c | 711 ++++++++++++++++++++++++++++++++++++++++++++++ > 3 files changed, 726 insertions(+) > create mode 100644 lib/list-test.c > > diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug > index a3017a5dadcd..60691c0aac3e 100644 > --- a/lib/Kconfig.debug > +++ b/lib/Kconfig.debug > @@ -1961,6 +1961,18 @@ config SYSCTL_KUNIT_TEST > > If unsure, say N. > > +config LIST_TEST > + bool "KUnit Test for Kernel Linked-list stuctures" > + depends on KUNIT > + help > + This builds the linked list unit test, which runs on boot. > + It tests that the API and basic functionality of the list_head type > + and associated macros. > + For more information on KUnit and unit tests in general please refer > + to the KUnit documentation in Documentation/dev-tools/kunit/. > + > + If unsure, say N. > + > config TEST_UDELAY > tristate "udelay test driver" > help > diff --git a/lib/Makefile b/lib/Makefile > index bba1fd5485f7..309e174ee35d 100644 > --- a/lib/Makefile > +++ b/lib/Makefile > @@ -292,3 +292,6 @@ obj-$(CONFIG_GENERIC_LIB_MULDI3) += muldi3.o > obj-$(CONFIG_GENERIC_LIB_CMPDI2) += cmpdi2.o > obj-$(CONFIG_GENERIC_LIB_UCMPDI2) += ucmpdi2.o > obj-$(CONFIG_OBJAGG) += objagg.o > + > +# KUnit tests > +obj-$(CONFIG_LIST_TEST) += list-test.o > diff --git a/lib/list-test.c b/lib/list-test.c > new file mode 100644 > index 000000000000..f333e8b0d9fe > --- /dev/null > +++ b/lib/list-test.c > @@ -0,0 +1,711 @@ > +// SPDX-License-Identifier: GPL-2.0 > +#include <kunit/test.h> > + > +#include <linux/list.h> > + > +struct list_test_struct { > + int data; > + struct list_head list; > +}; > + > +static void list_init_test(struct kunit *test) > +{ > + /* Test the different ways of initialising a list. */ > + struct list_head list1 = LIST_HEAD_INIT(list1); > + struct list_head list2; > + LIST_HEAD(list3); > + > + INIT_LIST_HEAD(&list2); Can you also add different storage locations and initial contents tests? For example: struct list_head *list4; struct list_head *list5; list4 = kzalloc(sizeof(*list4)); INIT_LIST_HEAD(list4); list5 = kmalloc(sizeof(*list5)); memset(list4, 0xff, sizeof(*list5)); INIT_LIST_HEAD(list5); KUNIT_EXPECT_TRUE(test, list_empty_careful(&list4)); KUNIT_EXPECT_TRUE(test, list_empty_careful(&list5)); kfree(list4); kfree(list5); Then we know it's not an accident that INIT_LIST_HEAD() works when both all-zeros and all-0xFF initial contents are there. :) > + > + /* list_empty_careful() checks both next and prev. */ > + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list1)); > + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); > + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list3)); > +} > + > +static void list_add_test(struct kunit *test) > +{ > + struct list_head a, b; > + LIST_HEAD(list); > + > + list_add(&a, &list); > + list_add(&b, &list); > + > + /* should be [list] -> b -> a */ > + KUNIT_EXPECT_PTR_EQ(test, list.next, &b); > + KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); > + KUNIT_EXPECT_PTR_EQ(test, b.next, &a); > +} > + > +static void list_add_tail_test(struct kunit *test) > +{ > + struct list_head a, b; > + LIST_HEAD(list); > + > + list_add_tail(&a, &list); > + list_add_tail(&b, &list); > + > + /* should be [list] -> a -> b */ > + KUNIT_EXPECT_PTR_EQ(test, list.next, &a); > + KUNIT_EXPECT_PTR_EQ(test, a.prev, &list); > + KUNIT_EXPECT_PTR_EQ(test, a.next, &b); > +} > + > +static void list_del_test(struct kunit *test) > +{ > + struct list_head a, b; > + LIST_HEAD(list); > + > + list_add_tail(&a, &list); > + list_add_tail(&b, &list); > + > + /* before: [list] -> a -> b */ > + list_del(&a); > + > + /* now: [list] -> b */ > + KUNIT_EXPECT_PTR_EQ(test, list.next, &b); > + KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); > +} > + > +static void list_replace_test(struct kunit *test) > +{ > + struct list_head a_old, a_new, b; > + LIST_HEAD(list); > + > + list_add_tail(&a_old, &list); > + list_add_tail(&b, &list); > + > + /* before: [list] -> a_old -> b */ > + list_replace(&a_old, &a_new); > + > + /* now: [list] -> a_new -> b */ > + KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new); > + KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new); > +} > + > +static void list_replace_init_test(struct kunit *test) > +{ > + struct list_head a_old, a_new, b; > + LIST_HEAD(list); > + > + list_add_tail(&a_old, &list); > + list_add_tail(&b, &list); > + > + /* before: [list] -> a_old -> b */ > + list_replace_init(&a_old, &a_new); > + > + /* now: [list] -> a_new -> b */ > + KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new); > + KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new); > + > + /* check a_old is empty (initialized) */ > + KUNIT_EXPECT_TRUE(test, list_empty_careful(&a_old)); > +} > + > +static void list_swap_test(struct kunit *test) > +{ > + struct list_head a, b; > + LIST_HEAD(list); > + > + list_add_tail(&a, &list); > + list_add_tail(&b, &list); > + > + /* before: [list] -> a -> b */ > + list_swap(&a, &b); > + > + /* after: [list] -> b -> a */ > + KUNIT_EXPECT_PTR_EQ(test, &b, list.next); > + KUNIT_EXPECT_PTR_EQ(test, &a, list.prev); > + > + KUNIT_EXPECT_PTR_EQ(test, &a, b.next); > + KUNIT_EXPECT_PTR_EQ(test, &list, b.prev); > + > + KUNIT_EXPECT_PTR_EQ(test, &list, a.next); > + KUNIT_EXPECT_PTR_EQ(test, &b, a.prev); > +} > + > +static void list_del_init_test(struct kunit *test) > +{ > + 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(&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_move_test(struct kunit *test) > +{ > + struct list_head a, b; > + LIST_HEAD(list1); > + LIST_HEAD(list2); > + > + list_add_tail(&a, &list1); > + list_add_tail(&b, &list2); > + > + /* before: [list1] -> a, [list2] -> b */ > + list_move(&a, &list2); > + /* after: [list1] empty, [list2] -> a -> b */ > + > + KUNIT_EXPECT_TRUE(test, list_empty(&list1)); > + > + KUNIT_EXPECT_PTR_EQ(test, &a, list2.next); > + KUNIT_EXPECT_PTR_EQ(test, &b, a.next); > +} > + > +static void list_move_tail_test(struct kunit *test) > +{ > + struct list_head a, b; > + LIST_HEAD(list1); > + LIST_HEAD(list2); > + > + list_add_tail(&a, &list1); > + list_add_tail(&b, &list2); > + > + /* before: [list1] -> a, [list2] -> b */ > + list_move_tail(&a, &list2); > + /* after: [list1] empty, [list2] -> b -> a */ > + > + KUNIT_EXPECT_TRUE(test, list_empty(&list1)); > + > + KUNIT_EXPECT_PTR_EQ(test, &b, list2.next); > + KUNIT_EXPECT_PTR_EQ(test, &a, b.next); > +} > + > +static void list_bulk_move_tail_test(struct kunit *test) > +{ > + struct list_head a, b, c, d, x, y; > + struct list_head *list1_values[] = { &x, &b, &c, &y }; > + struct list_head *list2_values[] = { &a, &d }; > + struct list_head *ptr; > + LIST_HEAD(list1); > + LIST_HEAD(list2); > + int i = 0; > + > + list_add_tail(&x, &list1); > + list_add_tail(&y, &list1); > + > + list_add_tail(&a, &list2); > + list_add_tail(&b, &list2); > + list_add_tail(&c, &list2); > + list_add_tail(&d, &list2); > + > + /* before: [list1] -> x -> y, [list2] -> a -> b -> c -> d */ > + list_bulk_move_tail(&y, &b, &c); > + /* after: [list1] -> x -> b -> c -> y, [list2] -> a -> d */ > + > + list_for_each(ptr, &list1) { > + KUNIT_EXPECT_PTR_EQ(test, ptr, list1_values[i]); > + i++; > + } > + KUNIT_EXPECT_EQ(test, i, 4); > + i = 0; > + list_for_each(ptr, &list2) { > + KUNIT_EXPECT_PTR_EQ(test, ptr, list2_values[i]); > + i++; > + } > + KUNIT_EXPECT_EQ(test, i, 2); > +} > + > +static void list_is_first_test(struct kunit *test) > +{ > + struct list_head a, b; > + LIST_HEAD(list); > + > + list_add_tail(&a, &list); > + list_add_tail(&b, &list); > + > + KUNIT_EXPECT_TRUE(test, list_is_first(&a, &list)); > + KUNIT_EXPECT_FALSE(test, list_is_first(&b, &list)); > +} > + > +static void list_is_last_test(struct kunit *test) > +{ > + struct list_head a, b; > + LIST_HEAD(list); > + > + list_add_tail(&a, &list); > + list_add_tail(&b, &list); > + > + KUNIT_EXPECT_FALSE(test, list_is_last(&a, &list)); > + KUNIT_EXPECT_TRUE(test, list_is_last(&b, &list)); > +} > + > +static void list_empty_test(struct kunit *test) > +{ > + struct list_head a; > + LIST_HEAD(list1); > + LIST_HEAD(list2); > + > + list_add_tail(&a, &list1); > + > + KUNIT_EXPECT_FALSE(test, list_empty(&list1)); > + KUNIT_EXPECT_TRUE(test, list_empty(&list2)); > +} > + > +static void list_empty_careful_test(struct kunit *test) > +{ > + struct list_head a; > + LIST_HEAD(list1); > + LIST_HEAD(list2); > + > + list_add_tail(&a, &list1); > + > + KUNIT_EXPECT_FALSE(test, list_empty_careful(&list1)); > + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); > +} > + > +static void list_rotate_left_test(struct kunit *test) > +{ > + struct list_head a, b; > + LIST_HEAD(list); > + > + list_add_tail(&a, &list); > + list_add_tail(&b, &list); > + > + /* before: [list] -> a -> b */ > + list_rotate_left(&list); > + /* after: [list] -> b -> a */ > + > + KUNIT_EXPECT_PTR_EQ(test, list.next, &b); > + KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); > + KUNIT_EXPECT_PTR_EQ(test, b.next, &a); > +} > + > +static void list_rotate_to_front_test(struct kunit *test) > +{ > + struct list_head a, b, c, d; > + struct list_head *list_values[] = { &c, &d, &a, &b }; > + struct list_head *ptr; > + LIST_HEAD(list); > + int i = 0; > + > + list_add_tail(&a, &list); > + list_add_tail(&b, &list); > + list_add_tail(&c, &list); > + list_add_tail(&d, &list); > + > + /* before: [list] -> a -> b -> c -> d */ > + list_rotate_to_front(&c, &list); > + /* after: [list] -> c -> d -> a -> b */ > + > + list_for_each(ptr, &list) { > + KUNIT_EXPECT_PTR_EQ(test, ptr, list_values[i]); > + i++; > + } > + KUNIT_EXPECT_EQ(test, i, 4); > +} > + > +static void list_is_singular_test(struct kunit *test) > +{ > + struct list_head a, b; > + LIST_HEAD(list); > + > + /* [list] empty */ > + KUNIT_EXPECT_FALSE(test, list_is_singular(&list)); > + > + list_add_tail(&a, &list); > + > + /* [list] -> a */ > + KUNIT_EXPECT_TRUE(test, list_is_singular(&list)); > + > + list_add_tail(&b, &list); > + > + /* [list] -> a -> b */ > + KUNIT_EXPECT_FALSE(test, list_is_singular(&list)); > +} > + > +static void list_cut_position_test(struct kunit *test) > +{ > + struct list_head entries[3], *cur; > + LIST_HEAD(list1); > + LIST_HEAD(list2); > + int i = 0; > + > + list_add_tail(&entries[0], &list1); > + list_add_tail(&entries[1], &list1); > + list_add_tail(&entries[2], &list1); > + > + /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */ > + list_cut_position(&list2, &list1, &entries[1]); > + /* after: [list2] -> entries[0] -> entries[1], [list1] -> entries[2] */ > + > + list_for_each(cur, &list2) { > + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); > + i++; > + } > + > + KUNIT_EXPECT_EQ(test, i, 2); > + > + list_for_each(cur, &list1) { > + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); > + i++; > + } > +} > + > +static void list_cut_before_test(struct kunit *test) > +{ > + struct list_head entries[3], *cur; > + LIST_HEAD(list1); > + LIST_HEAD(list2); > + int i = 0; > + > + list_add_tail(&entries[0], &list1); > + list_add_tail(&entries[1], &list1); > + list_add_tail(&entries[2], &list1); > + > + /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */ > + list_cut_before(&list2, &list1, &entries[1]); > + /* after: [list2] -> entries[0], [list1] -> entries[1] -> entries[2] */ > + > + list_for_each(cur, &list2) { > + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); > + i++; > + } > + > + KUNIT_EXPECT_EQ(test, i, 1); > + > + list_for_each(cur, &list1) { > + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); > + i++; > + } > +} > + > +static void list_splice_test(struct kunit *test) > +{ > + struct list_head entries[5], *cur; > + LIST_HEAD(list1); > + LIST_HEAD(list2); > + int i = 0; > + > + list_add_tail(&entries[0], &list1); > + list_add_tail(&entries[1], &list1); > + list_add_tail(&entries[2], &list2); > + list_add_tail(&entries[3], &list2); > + list_add_tail(&entries[4], &list1); > + > + /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ > + list_splice(&list2, &entries[1]); > + /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */ > + > + list_for_each(cur, &list1) { > + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); > + i++; > + } > + > + KUNIT_EXPECT_EQ(test, i, 5); > +} > + > +static void list_splice_tail_test(struct kunit *test) > +{ > + struct list_head entries[5], *cur; > + LIST_HEAD(list1); > + LIST_HEAD(list2); > + int i = 0; > + > + list_add_tail(&entries[0], &list1); > + list_add_tail(&entries[1], &list1); > + list_add_tail(&entries[2], &list2); > + list_add_tail(&entries[3], &list2); > + list_add_tail(&entries[4], &list1); > + > + /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ > + list_splice_tail(&list2, &entries[4]); > + /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */ > + > + list_for_each(cur, &list1) { > + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); > + i++; > + } > + > + KUNIT_EXPECT_EQ(test, i, 5); > +} > + > +static void list_splice_init_test(struct kunit *test) > +{ > + struct list_head entries[5], *cur; > + LIST_HEAD(list1); > + LIST_HEAD(list2); > + int i = 0; > + > + list_add_tail(&entries[0], &list1); > + list_add_tail(&entries[1], &list1); > + list_add_tail(&entries[2], &list2); > + list_add_tail(&entries[3], &list2); > + list_add_tail(&entries[4], &list1); > + > + /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ > + list_splice_init(&list2, &entries[1]); > + /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */ > + > + list_for_each(cur, &list1) { > + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); > + i++; > + } > + > + KUNIT_EXPECT_EQ(test, i, 5); > + > + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); > +} > + > +static void list_splice_tail_init_test(struct kunit *test) > +{ > + struct list_head entries[5], *cur; > + LIST_HEAD(list1); > + LIST_HEAD(list2); > + int i = 0; > + > + list_add_tail(&entries[0], &list1); > + list_add_tail(&entries[1], &list1); > + list_add_tail(&entries[2], &list2); > + list_add_tail(&entries[3], &list2); > + list_add_tail(&entries[4], &list1); > + > + /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ > + list_splice_tail_init(&list2, &entries[4]); > + /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */ > + > + list_for_each(cur, &list1) { > + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); > + i++; > + } > + > + KUNIT_EXPECT_EQ(test, i, 5); > + > + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); > +} > + > +static void list_entry_test(struct kunit *test) > +{ > + struct list_test_struct test_struct; I guess this is not a missing initialization here because this is just testing the container_of() wrapper macro? > + > + KUNIT_EXPECT_PTR_EQ(test, &test_struct, list_entry(&(test_struct.list), struct list_test_struct, list)); > +} > + > +static void list_first_entry_test(struct kunit *test) > +{ > + struct list_test_struct test_struct1, test_struct2; > + static LIST_HEAD(list); This is this static? > + > + list_add_tail(&test_struct1.list, &list); > + list_add_tail(&test_struct2.list, &list); > + > + > + KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_first_entry(&list, struct list_test_struct, list)); > +} > + > +static void list_last_entry_test(struct kunit *test) > +{ > + struct list_test_struct test_struct1, test_struct2; > + static LIST_HEAD(list); Same, and why aren't these combined into one test? > + > + list_add_tail(&test_struct1.list, &list); > + list_add_tail(&test_struct2.list, &list); > + > + > + KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_last_entry(&list, struct list_test_struct, list)); > +} > + > +static void list_first_entry_or_null_test(struct kunit *test) > +{ > + struct list_test_struct test_struct1, test_struct2; > + static LIST_HEAD(list); static why? > + > + KUNIT_EXPECT_FALSE(test, list_first_entry_or_null(&list, struct list_test_struct, list)); > + > + list_add_tail(&test_struct1.list, &list); > + list_add_tail(&test_struct2.list, &list); > + > + KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_first_entry_or_null(&list, struct list_test_struct, list)); > +} > + > +static void list_next_entry_test(struct kunit *test) > +{ > + struct list_test_struct test_struct1, test_struct2; > + static LIST_HEAD(list); Same. > + > + list_add_tail(&test_struct1.list, &list); > + list_add_tail(&test_struct2.list, &list); > + > + > + KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_next_entry(&test_struct1, list)); > +} > + > +static void list_prev_entry_test(struct kunit *test) > +{ > + struct list_test_struct test_struct1, test_struct2; > + static LIST_HEAD(list); Same. > + > + list_add_tail(&test_struct1.list, &list); > + list_add_tail(&test_struct2.list, &list); > + > + > + KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_prev_entry(&test_struct2, list)); > +} > + > +static void list_for_each_test(struct kunit *test) > +{ > + struct list_head entries[3], *cur; > + LIST_HEAD(list); > + int i = 0; > + > + list_add_tail(&entries[0], &list); > + list_add_tail(&entries[1], &list); > + list_add_tail(&entries[2], &list); > + > + list_for_each(cur, &list) { > + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); > + i++; > + } > + > + KUNIT_EXPECT_EQ(test, i, 3); > +} > + > +static void list_for_each_prev_test(struct kunit *test) > +{ > + struct list_head entries[3], *cur; > + LIST_HEAD(list); > + int i = 2; > + > + list_add_tail(&entries[0], &list); > + list_add_tail(&entries[1], &list); > + list_add_tail(&entries[2], &list); > + > + list_for_each_prev(cur, &list) { > + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); > + i--; > + } > + > + KUNIT_EXPECT_EQ(test, i, -1); Both of these tests test that the list contained the correct number of entries, not that anything about ordering was established. I would load values into these with the list_test_struct and test that the counting matches the expected ordering. > +} > + > +static void list_for_each_safe_test(struct kunit *test) > +{ > + struct list_head entries[3], *cur, *n; > + LIST_HEAD(list); > + int i = 0; > + > + > + list_add_tail(&entries[0], &list); > + list_add_tail(&entries[1], &list); > + list_add_tail(&entries[2], &list); > + > + list_for_each_safe(cur, n, &list) { > + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); > + list_del(&entries[i]); > + i++; > + } > + > + KUNIT_EXPECT_EQ(test, i, 3); I would expect an is_empty() test here too. > +} > + > +static void list_for_each_prev_safe_test(struct kunit *test) > +{ > + struct list_head entries[3], *cur, *n; > + LIST_HEAD(list); > + int i = 2; > + > + list_add_tail(&entries[0], &list); > + list_add_tail(&entries[1], &list); > + list_add_tail(&entries[2], &list); > + > + list_for_each_prev_safe(cur, n, &list) { > + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); > + list_del(&entries[i]); > + i--; > + } Same thing here. > + > + KUNIT_EXPECT_EQ(test, i, -1); > +} > + > +static void list_for_each_entry_test(struct kunit *test) > +{ > + struct list_test_struct entries[5], *cur; > + static LIST_HEAD(list); > + int i = 0; > + > + for (i = 0; i < 5; ++i) { > + entries[i].data = i; > + list_add_tail(&entries[i].list, &list); > + } > + > + i = 0; > + > + list_for_each_entry(cur, &list, list) { > + KUNIT_EXPECT_EQ(test, cur->data, i); > + i++; > + } > +} > + > +static void list_for_each_entry_reverse_test(struct kunit *test) > +{ > + struct list_test_struct entries[5], *cur; > + static LIST_HEAD(list); > + int i = 0; > + > + for (i = 0; i < 5; ++i) { > + entries[i].data = i; > + list_add_tail(&entries[i].list, &list); > + } > + > + i = 4; > + > + list_for_each_entry_reverse(cur, &list, list) { > + KUNIT_EXPECT_EQ(test, cur->data, i); > + i--; > + } Oh! Here is the data test. Why keep these separate? You could combine the counting tests with these? One thing to consider adding is a short comment above each test to clarify the test intention. While these are relatively simple tests, it could clarify things like "only testing counts here" or "similar to test_foo(), this adds in ordering verification", etc. > +} > + > +static struct kunit_case list_test_cases[] = { > + KUNIT_CASE(list_init_test), > + KUNIT_CASE(list_add_test), > + KUNIT_CASE(list_add_tail_test), > + KUNIT_CASE(list_del_test), > + KUNIT_CASE(list_replace_test), > + KUNIT_CASE(list_replace_init_test), > + KUNIT_CASE(list_swap_test), > + KUNIT_CASE(list_del_init_test), > + KUNIT_CASE(list_move_test), > + KUNIT_CASE(list_move_tail_test), > + KUNIT_CASE(list_bulk_move_tail_test), > + KUNIT_CASE(list_is_first_test), > + KUNIT_CASE(list_is_last_test), > + KUNIT_CASE(list_empty_test), > + KUNIT_CASE(list_empty_careful_test), > + KUNIT_CASE(list_rotate_left_test), > + KUNIT_CASE(list_rotate_to_front_test), > + KUNIT_CASE(list_is_singular_test), > + KUNIT_CASE(list_cut_position_test), > + KUNIT_CASE(list_cut_before_test), > + KUNIT_CASE(list_splice_test), > + KUNIT_CASE(list_splice_tail_test), > + KUNIT_CASE(list_splice_init_test), > + KUNIT_CASE(list_splice_tail_init_test), > + KUNIT_CASE(list_entry_test), > + KUNIT_CASE(list_first_entry_test), > + KUNIT_CASE(list_last_entry_test), > + KUNIT_CASE(list_first_entry_or_null_test), > + KUNIT_CASE(list_next_entry_test), > + KUNIT_CASE(list_prev_entry_test), > + KUNIT_CASE(list_for_each_test), > + KUNIT_CASE(list_for_each_prev_test), > + KUNIT_CASE(list_for_each_safe_test), > + KUNIT_CASE(list_for_each_prev_safe_test), > + KUNIT_CASE(list_for_each_entry_test), > + KUNIT_CASE(list_for_each_entry_reverse_test), > + {}, > +}; > + > +static struct kunit_suite list_test_module = { > + .name = "list-test", > + .test_cases = list_test_cases, > +}; > + > +kunit_test_suite(list_test_module); > -- > 2.23.0.581.g78d2f28ef7-goog > Thanks for working on this! I'm excited to see some core API unit tests! :)
On Mon, Oct 07, 2019 at 02:36:33PM -0700, David Gow wrote: > +config LIST_TEST > + bool "KUnit Test for Kernel Linked-list stuctures" I missed this the first time through: typo of "structures"
On Mon, Oct 07, 2019 at 02:36:33PM -0700, David Gow wrote: > This change adds a KUnit test for the kernel doubly linked list > implementation in include/linux/list.h > > Note that, at present, it only tests the list_ types (not the > singly-linked hlist_), and does not yet test all of the > list_for_each_entry* macros (and some related things like > list_prepare_entry). > > This change depends on KUnit, so should be merged via the 'test' branch: > https://git.kernel.org/pub/scm/linux/kernel/git/shuah/linux-kselftest.git/log/?h=test > > Signed-off-by: David Gow <davidgow@google.com> > --- > lib/Kconfig.debug | 12 + > lib/Makefile | 3 + > lib/list-test.c | 711 ++++++++++++++++++++++++++++++++++++++++++++++ > 3 files changed, 726 insertions(+) > create mode 100644 lib/list-test.c Also, I think it might be good to make a MAINTAINERs entry for this test. Cheers!
On Tue, Oct 08, 2019 at 10:48:37AM -0700, Brendan Higgins wrote: > On Mon, Oct 07, 2019 at 02:36:33PM -0700, David Gow wrote: > > This change adds a KUnit test for the kernel doubly linked list > > implementation in include/linux/list.h > > > > Note that, at present, it only tests the list_ types (not the > > singly-linked hlist_), and does not yet test all of the > > list_for_each_entry* macros (and some related things like > > list_prepare_entry). > > > > This change depends on KUnit, so should be merged via the 'test' branch: > > https://git.kernel.org/pub/scm/linux/kernel/git/shuah/linux-kselftest.git/log/?h=test > > > > Signed-off-by: David Gow <davidgow@google.com> > > --- > > lib/Kconfig.debug | 12 + > > lib/Makefile | 3 + > > lib/list-test.c | 711 ++++++++++++++++++++++++++++++++++++++++++++++ > > 3 files changed, 726 insertions(+) > > create mode 100644 lib/list-test.c > > Also, I think it might be good to make a MAINTAINERs entry for this > test. Another thought, though maybe this is already covered and I missed the "best practices" notes on naming conventions. As the "one-off" tests are already named "foo_test.c" it seems like KUnit tests should be named distinctly. Should this be lib/kunit-list.c, lib/list-kunit.c, or something else? For internal naming of structs and tests, should things be named "kunit_foo"? Examples here would be kunit_list_struct and kunit_list_test_... When testing other stuff, should only exposed interfaces be tested? Many things have their API exposed via registration of a static structure of function pointers to static functions. What's the proposed best way to get at that? Should the KUnit tests is IN the .c file that declares all the static functions?
On Tue, Oct 8, 2019 at 11:15 AM Kees Cook <keescook@chromium.org> wrote: > > On Tue, Oct 08, 2019 at 10:48:37AM -0700, Brendan Higgins wrote: > > On Mon, Oct 07, 2019 at 02:36:33PM -0700, David Gow wrote: > > > This change adds a KUnit test for the kernel doubly linked list > > > implementation in include/linux/list.h > > > > > > Note that, at present, it only tests the list_ types (not the > > > singly-linked hlist_), and does not yet test all of the > > > list_for_each_entry* macros (and some related things like > > > list_prepare_entry). > > > > > > This change depends on KUnit, so should be merged via the 'test' branch: > > > https://git.kernel.org/pub/scm/linux/kernel/git/shuah/linux-kselftest.git/log/?h=test > > > > > > Signed-off-by: David Gow <davidgow@google.com> > > > --- > > > lib/Kconfig.debug | 12 + > > > lib/Makefile | 3 + > > > lib/list-test.c | 711 ++++++++++++++++++++++++++++++++++++++++++++++ > > > 3 files changed, 726 insertions(+) > > > create mode 100644 lib/list-test.c > > > > Also, I think it might be good to make a MAINTAINERs entry for this > > test. > > Another thought, though maybe this is already covered and I missed the > "best practices" notes on naming conventions. > > As the "one-off" tests are already named "foo_test.c" it seems like > KUnit tests should be named distinctly. Should this be lib/kunit-list.c, > lib/list-kunit.c, or something else? So we already had a discussion on this here: https://patchwork.kernel.org/patch/10925861/ (Sounds like I should have probably documented that :-)) However, I am sympathetic to your argument. I was thinking that it might be good to make get_maintainer suggest CC'ing kunit-dev@ and linux-kselftest@ for all new tests and this would be hard with the *-test.c naming scheme. If we are going to change it, now is probably the time to do it :-) > For internal naming of structs and tests, should things be > named "kunit_foo"? Examples here would be kunit_list_struct and > kunit_list_test_... I had generally been following the pattern: foo.c struct foo_bar {}; int foo_baz() {} foo-test.c struct foo_test_buzz {}; void foo_test_does_foo_baz_buzz(struct kunit *test) {} However, now that you point that out I am realizing there is a bunch of stuff here that is not consistent with that (whoops, sorry for not catching that earlier, David). Nevertheless, I think the list_test_struct is fine and conforms to the pattern. > When testing other stuff, should only exposed interfaces be tested? > Many things have their API exposed via registration of a static structure > of function pointers to static functions. What's the proposed best way > to get at that? Should the KUnit tests is IN the .c file that declares > all the static functions? Yeah, that is a good point, but I don't think entirely relevant to this code review. Fundamentally it boils down to figuring out what your API is, and coming up with a way to expose it. For drivers, that means finding a way to give KUnit access to the generated driver objects, in some cases it means using more dependency injection, in other cases it may mean making something that is static, not static. I know those answers sound pretty unsatisfying, and I have some features planned which alleviate some of those issues, but I think the most important thing is making examples of how to deal with some of the broad cases, getting agreement on them, documenting them, finding exceptions and iterating. Nevertheless, if you want to start enumerating cases and proposed solutions, I would be more than happy to have that conversation now, but we might want to fork the discussion. Cheers!
On Mon, Oct 7, 2019 at 6:03 PM Kees Cook <keescook@chromium.org> wrote: (...) > > + > > +static void list_init_test(struct kunit *test) > > +{ > > + /* Test the different ways of initialising a list. */ > > + struct list_head list1 = LIST_HEAD_INIT(list1); > > + struct list_head list2; > > + LIST_HEAD(list3); > > + > > + INIT_LIST_HEAD(&list2); > > Can you also add different storage locations and initial contents tests? > For example: > > struct list_head *list4; > struct list_head *list5; > > list4 = kzalloc(sizeof(*list4)); > INIT_LIST_HEAD(list4); > > list5 = kmalloc(sizeof(*list5)); > memset(list4, 0xff, sizeof(*list5)); > INIT_LIST_HEAD(list5); > > > KUNIT_EXPECT_TRUE(test, list_empty_careful(&list4)); > KUNIT_EXPECT_TRUE(test, list_empty_careful(&list5)); > > kfree(list4); > kfree(list5); > > Then we know it's not an accident that INIT_LIST_HEAD() works when both > all-zeros and all-0xFF initial contents are there. :) Will do. > > +static void list_entry_test(struct kunit *test) > > +{ > > + struct list_test_struct test_struct; > > I guess this is not a missing initialization here because this is just > testing the container_of() wrapper macro? > Yeah: we shouldn't be doing any memory accesses here, just the pointer manipulation, so it shouldn't matter. I can add a comment pointing this out, or just initialise it anyway. > > + > > + KUNIT_EXPECT_PTR_EQ(test, &test_struct, list_entry(&(test_struct.list), struct list_test_struct, list)); > > +} > > + > > +static void list_first_entry_test(struct kunit *test) > > +{ > > + struct list_test_struct test_struct1, test_struct2; > > + static LIST_HEAD(list); > > This is this static? > Oops, this doesn't need to be static. I'll fix this (and the others) for the next version. > > +static void list_for_each_test(struct kunit *test) > > +{ > > + struct list_head entries[3], *cur; > > + LIST_HEAD(list); > > + int i = 0; > > + > > + list_add_tail(&entries[0], &list); > > + list_add_tail(&entries[1], &list); > > + list_add_tail(&entries[2], &list); > > + > > + list_for_each(cur, &list) { > > + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); > > + i++; > > + } > > + > > + KUNIT_EXPECT_EQ(test, i, 3); > > +} > > + > > +static void list_for_each_prev_test(struct kunit *test) > > +{ > > + struct list_head entries[3], *cur; > > + LIST_HEAD(list); > > + int i = 2; > > + > > + list_add_tail(&entries[0], &list); > > + list_add_tail(&entries[1], &list); > > + list_add_tail(&entries[2], &list); > > + > > + list_for_each_prev(cur, &list) { > > + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); > > + i--; > > + } > > + > > + KUNIT_EXPECT_EQ(test, i, -1); > > Both of these tests test that the list contained the correct number of > entries, not that anything about ordering was established. I would load > values into these with the list_test_struct and test that the counting > matches the expected ordering. > These tests do check the order of the entries (the order of the list should match the order of the entries array, and KUNIT_EXPECT_PTR_EQ() is verifying that the entries[i] is correct). It would be possible to actually use list_test_struct like with the list_for_each_entry tests, but since list_for_each just returns the list_head, it didn't seem useful, so long as the list_head pointers match. > > +} > > + > > +static void list_for_each_safe_test(struct kunit *test) > > +{ > > + struct list_head entries[3], *cur, *n; > > + LIST_HEAD(list); > > + int i = 0; > > + > > + > > + list_add_tail(&entries[0], &list); > > + list_add_tail(&entries[1], &list); > > + list_add_tail(&entries[2], &list); > > + > > + list_for_each_safe(cur, n, &list) { > > + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); > > + list_del(&entries[i]); > > + i++; > > + } > > + > > + KUNIT_EXPECT_EQ(test, i, 3); > > I would expect an is_empty() test here too. > Will do. > > +} > > + > > +static void list_for_each_prev_safe_test(struct kunit *test) > > +{ > > + struct list_head entries[3], *cur, *n; > > + LIST_HEAD(list); > > + int i = 2; > > + > > + list_add_tail(&entries[0], &list); > > + list_add_tail(&entries[1], &list); > > + list_add_tail(&entries[2], &list); > > + > > + list_for_each_prev_safe(cur, n, &list) { > > + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); > > + list_del(&entries[i]); > > + i--; > > + } > > Same thing here. > Will do. > > +static void list_for_each_entry_test(struct kunit *test) > > +{ > > + struct list_test_struct entries[5], *cur; > > + static LIST_HEAD(list); > > + int i = 0; > > + > > + for (i = 0; i < 5; ++i) { > > + entries[i].data = i; > > + list_add_tail(&entries[i].list, &list); > > + } > > + > > + i = 0; > > + > > + list_for_each_entry(cur, &list, list) { > > + KUNIT_EXPECT_EQ(test, cur->data, i); > > + i++; > > + } > > +} > > + > > +static void list_for_each_entry_reverse_test(struct kunit *test) > > +{ > > + struct list_test_struct entries[5], *cur; > > + static LIST_HEAD(list); > > + int i = 0; > > + > > + for (i = 0; i < 5; ++i) { > > + entries[i].data = i; > > + list_add_tail(&entries[i].list, &list); > > + } > > + > > + i = 4; > > + > > + list_for_each_entry_reverse(cur, &list, list) { > > + KUNIT_EXPECT_EQ(test, cur->data, i); > > + i--; > > + } > > Oh! Here is the data test. Why keep these separate? You could combine > the counting tests with these? > > One thing to consider adding is a short comment above each test to > clarify the test intention. While these are relatively simple tests, it > could clarify things like "only testing counts here" or "similar to > test_foo(), this adds in ordering verification", etc. > The idea here was to have a separate test for each function/macro being tested. This hopefully should make it easier to narrow down where test failures are. In this case, the tests using list_test_struct are here because list_for_each_entry() does the implicit container_of(), so testing it properly requires the test struct. As above, the list_for_each() tests do actually check the order, so it's probably worth adding a check for the count to these tests, too. There are definitely a few places where extra comments make sense. In general, for these tests at least, the purpose of each test is to test the function/macro it's named after, ideally reasonably thoroughly. My feeling is that, given that, it's more useful to call out explicitly if something obvious isn't tested (such as the list_empty_careful_test(), perhaps, which doesn't verify concurrent access from multiple threads). Cheers, -- David
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index a3017a5dadcd..60691c0aac3e 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -1961,6 +1961,18 @@ config SYSCTL_KUNIT_TEST If unsure, say N. +config LIST_TEST + bool "KUnit Test for Kernel Linked-list stuctures" + depends on KUNIT + help + This builds the linked list unit test, which runs on boot. + It tests that the API and basic functionality of the list_head type + and associated macros. + For more information on KUnit and unit tests in general please refer + to the KUnit documentation in Documentation/dev-tools/kunit/. + + If unsure, say N. + config TEST_UDELAY tristate "udelay test driver" help diff --git a/lib/Makefile b/lib/Makefile index bba1fd5485f7..309e174ee35d 100644 --- a/lib/Makefile +++ b/lib/Makefile @@ -292,3 +292,6 @@ obj-$(CONFIG_GENERIC_LIB_MULDI3) += muldi3.o obj-$(CONFIG_GENERIC_LIB_CMPDI2) += cmpdi2.o obj-$(CONFIG_GENERIC_LIB_UCMPDI2) += ucmpdi2.o obj-$(CONFIG_OBJAGG) += objagg.o + +# KUnit tests +obj-$(CONFIG_LIST_TEST) += list-test.o diff --git a/lib/list-test.c b/lib/list-test.c new file mode 100644 index 000000000000..f333e8b0d9fe --- /dev/null +++ b/lib/list-test.c @@ -0,0 +1,711 @@ +// SPDX-License-Identifier: GPL-2.0 +#include <kunit/test.h> + +#include <linux/list.h> + +struct list_test_struct { + int data; + struct list_head list; +}; + +static void list_init_test(struct kunit *test) +{ + /* Test the different ways of initialising a list. */ + struct list_head list1 = LIST_HEAD_INIT(list1); + struct list_head list2; + LIST_HEAD(list3); + + INIT_LIST_HEAD(&list2); + + /* list_empty_careful() checks both next and prev. */ + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list1)); + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list3)); +} + +static void list_add_test(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + list_add(&a, &list); + list_add(&b, &list); + + /* should be [list] -> b -> a */ + KUNIT_EXPECT_PTR_EQ(test, list.next, &b); + KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); + KUNIT_EXPECT_PTR_EQ(test, b.next, &a); +} + +static void list_add_tail_test(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + + /* should be [list] -> a -> b */ + KUNIT_EXPECT_PTR_EQ(test, list.next, &a); + KUNIT_EXPECT_PTR_EQ(test, a.prev, &list); + KUNIT_EXPECT_PTR_EQ(test, a.next, &b); +} + +static void list_del_test(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + + /* before: [list] -> a -> b */ + list_del(&a); + + /* now: [list] -> b */ + KUNIT_EXPECT_PTR_EQ(test, list.next, &b); + KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); +} + +static void list_replace_test(struct kunit *test) +{ + struct list_head a_old, a_new, b; + LIST_HEAD(list); + + list_add_tail(&a_old, &list); + list_add_tail(&b, &list); + + /* before: [list] -> a_old -> b */ + list_replace(&a_old, &a_new); + + /* now: [list] -> a_new -> b */ + KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new); + KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new); +} + +static void list_replace_init_test(struct kunit *test) +{ + struct list_head a_old, a_new, b; + LIST_HEAD(list); + + list_add_tail(&a_old, &list); + list_add_tail(&b, &list); + + /* before: [list] -> a_old -> b */ + list_replace_init(&a_old, &a_new); + + /* now: [list] -> a_new -> b */ + KUNIT_EXPECT_PTR_EQ(test, list.next, &a_new); + KUNIT_EXPECT_PTR_EQ(test, b.prev, &a_new); + + /* check a_old is empty (initialized) */ + KUNIT_EXPECT_TRUE(test, list_empty_careful(&a_old)); +} + +static void list_swap_test(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + + /* before: [list] -> a -> b */ + list_swap(&a, &b); + + /* after: [list] -> b -> a */ + KUNIT_EXPECT_PTR_EQ(test, &b, list.next); + KUNIT_EXPECT_PTR_EQ(test, &a, list.prev); + + KUNIT_EXPECT_PTR_EQ(test, &a, b.next); + KUNIT_EXPECT_PTR_EQ(test, &list, b.prev); + + KUNIT_EXPECT_PTR_EQ(test, &list, a.next); + KUNIT_EXPECT_PTR_EQ(test, &b, a.prev); +} + +static void list_del_init_test(struct kunit *test) +{ + 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(&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_move_test(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list1); + LIST_HEAD(list2); + + list_add_tail(&a, &list1); + list_add_tail(&b, &list2); + + /* before: [list1] -> a, [list2] -> b */ + list_move(&a, &list2); + /* after: [list1] empty, [list2] -> a -> b */ + + KUNIT_EXPECT_TRUE(test, list_empty(&list1)); + + KUNIT_EXPECT_PTR_EQ(test, &a, list2.next); + KUNIT_EXPECT_PTR_EQ(test, &b, a.next); +} + +static void list_move_tail_test(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list1); + LIST_HEAD(list2); + + list_add_tail(&a, &list1); + list_add_tail(&b, &list2); + + /* before: [list1] -> a, [list2] -> b */ + list_move_tail(&a, &list2); + /* after: [list1] empty, [list2] -> b -> a */ + + KUNIT_EXPECT_TRUE(test, list_empty(&list1)); + + KUNIT_EXPECT_PTR_EQ(test, &b, list2.next); + KUNIT_EXPECT_PTR_EQ(test, &a, b.next); +} + +static void list_bulk_move_tail_test(struct kunit *test) +{ + struct list_head a, b, c, d, x, y; + struct list_head *list1_values[] = { &x, &b, &c, &y }; + struct list_head *list2_values[] = { &a, &d }; + struct list_head *ptr; + LIST_HEAD(list1); + LIST_HEAD(list2); + int i = 0; + + list_add_tail(&x, &list1); + list_add_tail(&y, &list1); + + list_add_tail(&a, &list2); + list_add_tail(&b, &list2); + list_add_tail(&c, &list2); + list_add_tail(&d, &list2); + + /* before: [list1] -> x -> y, [list2] -> a -> b -> c -> d */ + list_bulk_move_tail(&y, &b, &c); + /* after: [list1] -> x -> b -> c -> y, [list2] -> a -> d */ + + list_for_each(ptr, &list1) { + KUNIT_EXPECT_PTR_EQ(test, ptr, list1_values[i]); + i++; + } + KUNIT_EXPECT_EQ(test, i, 4); + i = 0; + list_for_each(ptr, &list2) { + KUNIT_EXPECT_PTR_EQ(test, ptr, list2_values[i]); + i++; + } + KUNIT_EXPECT_EQ(test, i, 2); +} + +static void list_is_first_test(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + + KUNIT_EXPECT_TRUE(test, list_is_first(&a, &list)); + KUNIT_EXPECT_FALSE(test, list_is_first(&b, &list)); +} + +static void list_is_last_test(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + + KUNIT_EXPECT_FALSE(test, list_is_last(&a, &list)); + KUNIT_EXPECT_TRUE(test, list_is_last(&b, &list)); +} + +static void list_empty_test(struct kunit *test) +{ + struct list_head a; + LIST_HEAD(list1); + LIST_HEAD(list2); + + list_add_tail(&a, &list1); + + KUNIT_EXPECT_FALSE(test, list_empty(&list1)); + KUNIT_EXPECT_TRUE(test, list_empty(&list2)); +} + +static void list_empty_careful_test(struct kunit *test) +{ + struct list_head a; + LIST_HEAD(list1); + LIST_HEAD(list2); + + list_add_tail(&a, &list1); + + KUNIT_EXPECT_FALSE(test, list_empty_careful(&list1)); + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); +} + +static void list_rotate_left_test(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + + /* before: [list] -> a -> b */ + list_rotate_left(&list); + /* after: [list] -> b -> a */ + + KUNIT_EXPECT_PTR_EQ(test, list.next, &b); + KUNIT_EXPECT_PTR_EQ(test, b.prev, &list); + KUNIT_EXPECT_PTR_EQ(test, b.next, &a); +} + +static void list_rotate_to_front_test(struct kunit *test) +{ + struct list_head a, b, c, d; + struct list_head *list_values[] = { &c, &d, &a, &b }; + struct list_head *ptr; + LIST_HEAD(list); + int i = 0; + + list_add_tail(&a, &list); + list_add_tail(&b, &list); + list_add_tail(&c, &list); + list_add_tail(&d, &list); + + /* before: [list] -> a -> b -> c -> d */ + list_rotate_to_front(&c, &list); + /* after: [list] -> c -> d -> a -> b */ + + list_for_each(ptr, &list) { + KUNIT_EXPECT_PTR_EQ(test, ptr, list_values[i]); + i++; + } + KUNIT_EXPECT_EQ(test, i, 4); +} + +static void list_is_singular_test(struct kunit *test) +{ + struct list_head a, b; + LIST_HEAD(list); + + /* [list] empty */ + KUNIT_EXPECT_FALSE(test, list_is_singular(&list)); + + list_add_tail(&a, &list); + + /* [list] -> a */ + KUNIT_EXPECT_TRUE(test, list_is_singular(&list)); + + list_add_tail(&b, &list); + + /* [list] -> a -> b */ + KUNIT_EXPECT_FALSE(test, list_is_singular(&list)); +} + +static void list_cut_position_test(struct kunit *test) +{ + struct list_head entries[3], *cur; + LIST_HEAD(list1); + LIST_HEAD(list2); + int i = 0; + + list_add_tail(&entries[0], &list1); + list_add_tail(&entries[1], &list1); + list_add_tail(&entries[2], &list1); + + /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */ + list_cut_position(&list2, &list1, &entries[1]); + /* after: [list2] -> entries[0] -> entries[1], [list1] -> entries[2] */ + + list_for_each(cur, &list2) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 2); + + list_for_each(cur, &list1) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } +} + +static void list_cut_before_test(struct kunit *test) +{ + struct list_head entries[3], *cur; + LIST_HEAD(list1); + LIST_HEAD(list2); + int i = 0; + + list_add_tail(&entries[0], &list1); + list_add_tail(&entries[1], &list1); + list_add_tail(&entries[2], &list1); + + /* before: [list1] -> entries[0] -> entries[1] -> entries[2] */ + list_cut_before(&list2, &list1, &entries[1]); + /* after: [list2] -> entries[0], [list1] -> entries[1] -> entries[2] */ + + list_for_each(cur, &list2) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 1); + + list_for_each(cur, &list1) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } +} + +static void list_splice_test(struct kunit *test) +{ + struct list_head entries[5], *cur; + LIST_HEAD(list1); + LIST_HEAD(list2); + int i = 0; + + list_add_tail(&entries[0], &list1); + list_add_tail(&entries[1], &list1); + list_add_tail(&entries[2], &list2); + list_add_tail(&entries[3], &list2); + list_add_tail(&entries[4], &list1); + + /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ + list_splice(&list2, &entries[1]); + /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */ + + list_for_each(cur, &list1) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); +} + +static void list_splice_tail_test(struct kunit *test) +{ + struct list_head entries[5], *cur; + LIST_HEAD(list1); + LIST_HEAD(list2); + int i = 0; + + list_add_tail(&entries[0], &list1); + list_add_tail(&entries[1], &list1); + list_add_tail(&entries[2], &list2); + list_add_tail(&entries[3], &list2); + list_add_tail(&entries[4], &list1); + + /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ + list_splice_tail(&list2, &entries[4]); + /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] uninit */ + + list_for_each(cur, &list1) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); +} + +static void list_splice_init_test(struct kunit *test) +{ + struct list_head entries[5], *cur; + LIST_HEAD(list1); + LIST_HEAD(list2); + int i = 0; + + list_add_tail(&entries[0], &list1); + list_add_tail(&entries[1], &list1); + list_add_tail(&entries[2], &list2); + list_add_tail(&entries[3], &list2); + list_add_tail(&entries[4], &list1); + + /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ + list_splice_init(&list2, &entries[1]); + /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */ + + list_for_each(cur, &list1) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); + + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); +} + +static void list_splice_tail_init_test(struct kunit *test) +{ + struct list_head entries[5], *cur; + LIST_HEAD(list1); + LIST_HEAD(list2); + int i = 0; + + list_add_tail(&entries[0], &list1); + list_add_tail(&entries[1], &list1); + list_add_tail(&entries[2], &list2); + list_add_tail(&entries[3], &list2); + list_add_tail(&entries[4], &list1); + + /* before: [list1]->e[0]->e[1]->e[4], [list2]->e[2]->e[3] */ + list_splice_tail_init(&list2, &entries[4]); + /* after: [list1]->e[0]->e[1]->e[2]->e[3]->e[4], [list2] empty */ + + list_for_each(cur, &list1) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 5); + + KUNIT_EXPECT_TRUE(test, list_empty_careful(&list2)); +} + +static void list_entry_test(struct kunit *test) +{ + struct list_test_struct test_struct; + + KUNIT_EXPECT_PTR_EQ(test, &test_struct, list_entry(&(test_struct.list), struct list_test_struct, list)); +} + +static void list_first_entry_test(struct kunit *test) +{ + struct list_test_struct test_struct1, test_struct2; + static LIST_HEAD(list); + + list_add_tail(&test_struct1.list, &list); + list_add_tail(&test_struct2.list, &list); + + + KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_first_entry(&list, struct list_test_struct, list)); +} + +static void list_last_entry_test(struct kunit *test) +{ + struct list_test_struct test_struct1, test_struct2; + static LIST_HEAD(list); + + list_add_tail(&test_struct1.list, &list); + list_add_tail(&test_struct2.list, &list); + + + KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_last_entry(&list, struct list_test_struct, list)); +} + +static void list_first_entry_or_null_test(struct kunit *test) +{ + struct list_test_struct test_struct1, test_struct2; + static LIST_HEAD(list); + + KUNIT_EXPECT_FALSE(test, list_first_entry_or_null(&list, struct list_test_struct, list)); + + list_add_tail(&test_struct1.list, &list); + list_add_tail(&test_struct2.list, &list); + + KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_first_entry_or_null(&list, struct list_test_struct, list)); +} + +static void list_next_entry_test(struct kunit *test) +{ + struct list_test_struct test_struct1, test_struct2; + static LIST_HEAD(list); + + list_add_tail(&test_struct1.list, &list); + list_add_tail(&test_struct2.list, &list); + + + KUNIT_EXPECT_PTR_EQ(test, &test_struct2, list_next_entry(&test_struct1, list)); +} + +static void list_prev_entry_test(struct kunit *test) +{ + struct list_test_struct test_struct1, test_struct2; + static LIST_HEAD(list); + + list_add_tail(&test_struct1.list, &list); + list_add_tail(&test_struct2.list, &list); + + + KUNIT_EXPECT_PTR_EQ(test, &test_struct1, list_prev_entry(&test_struct2, list)); +} + +static void list_for_each_test(struct kunit *test) +{ + struct list_head entries[3], *cur; + LIST_HEAD(list); + int i = 0; + + list_add_tail(&entries[0], &list); + list_add_tail(&entries[1], &list); + list_add_tail(&entries[2], &list); + + list_for_each(cur, &list) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 3); +} + +static void list_for_each_prev_test(struct kunit *test) +{ + struct list_head entries[3], *cur; + LIST_HEAD(list); + int i = 2; + + list_add_tail(&entries[0], &list); + list_add_tail(&entries[1], &list); + list_add_tail(&entries[2], &list); + + list_for_each_prev(cur, &list) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + i--; + } + + KUNIT_EXPECT_EQ(test, i, -1); +} + +static void list_for_each_safe_test(struct kunit *test) +{ + struct list_head entries[3], *cur, *n; + LIST_HEAD(list); + int i = 0; + + + list_add_tail(&entries[0], &list); + list_add_tail(&entries[1], &list); + list_add_tail(&entries[2], &list); + + list_for_each_safe(cur, n, &list) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + list_del(&entries[i]); + i++; + } + + KUNIT_EXPECT_EQ(test, i, 3); +} + +static void list_for_each_prev_safe_test(struct kunit *test) +{ + struct list_head entries[3], *cur, *n; + LIST_HEAD(list); + int i = 2; + + list_add_tail(&entries[0], &list); + list_add_tail(&entries[1], &list); + list_add_tail(&entries[2], &list); + + list_for_each_prev_safe(cur, n, &list) { + KUNIT_EXPECT_PTR_EQ(test, cur, &entries[i]); + list_del(&entries[i]); + i--; + } + + KUNIT_EXPECT_EQ(test, i, -1); +} + +static void list_for_each_entry_test(struct kunit *test) +{ + struct list_test_struct entries[5], *cur; + static LIST_HEAD(list); + int i = 0; + + for (i = 0; i < 5; ++i) { + entries[i].data = i; + list_add_tail(&entries[i].list, &list); + } + + i = 0; + + list_for_each_entry(cur, &list, list) { + KUNIT_EXPECT_EQ(test, cur->data, i); + i++; + } +} + +static void list_for_each_entry_reverse_test(struct kunit *test) +{ + struct list_test_struct entries[5], *cur; + static LIST_HEAD(list); + int i = 0; + + for (i = 0; i < 5; ++i) { + entries[i].data = i; + list_add_tail(&entries[i].list, &list); + } + + i = 4; + + list_for_each_entry_reverse(cur, &list, list) { + KUNIT_EXPECT_EQ(test, cur->data, i); + i--; + } +} + +static struct kunit_case list_test_cases[] = { + KUNIT_CASE(list_init_test), + KUNIT_CASE(list_add_test), + KUNIT_CASE(list_add_tail_test), + KUNIT_CASE(list_del_test), + KUNIT_CASE(list_replace_test), + KUNIT_CASE(list_replace_init_test), + KUNIT_CASE(list_swap_test), + KUNIT_CASE(list_del_init_test), + KUNIT_CASE(list_move_test), + KUNIT_CASE(list_move_tail_test), + KUNIT_CASE(list_bulk_move_tail_test), + KUNIT_CASE(list_is_first_test), + KUNIT_CASE(list_is_last_test), + KUNIT_CASE(list_empty_test), + KUNIT_CASE(list_empty_careful_test), + KUNIT_CASE(list_rotate_left_test), + KUNIT_CASE(list_rotate_to_front_test), + KUNIT_CASE(list_is_singular_test), + KUNIT_CASE(list_cut_position_test), + KUNIT_CASE(list_cut_before_test), + KUNIT_CASE(list_splice_test), + KUNIT_CASE(list_splice_tail_test), + KUNIT_CASE(list_splice_init_test), + KUNIT_CASE(list_splice_tail_init_test), + KUNIT_CASE(list_entry_test), + KUNIT_CASE(list_first_entry_test), + KUNIT_CASE(list_last_entry_test), + KUNIT_CASE(list_first_entry_or_null_test), + KUNIT_CASE(list_next_entry_test), + KUNIT_CASE(list_prev_entry_test), + KUNIT_CASE(list_for_each_test), + KUNIT_CASE(list_for_each_prev_test), + KUNIT_CASE(list_for_each_safe_test), + KUNIT_CASE(list_for_each_prev_safe_test), + KUNIT_CASE(list_for_each_entry_test), + KUNIT_CASE(list_for_each_entry_reverse_test), + {}, +}; + +static struct kunit_suite list_test_module = { + .name = "list-test", + .test_cases = list_test_cases, +}; + +kunit_test_suite(list_test_module);
This change adds a KUnit test for the kernel doubly linked list implementation in include/linux/list.h Note that, at present, it only tests the list_ types (not the singly-linked hlist_), and does not yet test all of the list_for_each_entry* macros (and some related things like list_prepare_entry). This change depends on KUnit, so should be merged via the 'test' branch: https://git.kernel.org/pub/scm/linux/kernel/git/shuah/linux-kselftest.git/log/?h=test Signed-off-by: David Gow <davidgow@google.com> --- lib/Kconfig.debug | 12 + lib/Makefile | 3 + lib/list-test.c | 711 ++++++++++++++++++++++++++++++++++++++++++++++ 3 files changed, 726 insertions(+) create mode 100644 lib/list-test.c