[PATCH linux-kselftest/test v2] lib/list-test: add a test for the 'list' doubly linked list

[PATCH linux-kselftest/test v2] lib/list-test: add a test for the 'list' doubly linked list

[David Gow]

Add a KUnit test for the kernel doubly linked list implementation in
include/linux/list.h

Each test case (list_test_x) is focused on testing the behaviour of the
list function/macro 'x'. None of the tests pass invalid lists to these
macros, and so should behave identically with DEBUG_LIST enabled and
disabled.

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).

Signed-off-by: David Gow <davidgow@google.com>
---
Addressed the various comments on v1. The biggest change is the renaming
of all of the testcases from the form x_test to list_test_x. I'm not
super happy with how that looks (not the least because it ends up with
'list' twice), but it is more consistent with the proc/sysctl tests.


 MAINTAINERS       |   5 +
 lib/Kconfig.debug |  12 +
 lib/Makefile      |   3 +
 lib/list-test.c   | 738 ++++++++++++++++++++++++++++++++++++++++++++++
 4 files changed, 758 insertions(+)
 create mode 100644 lib/list-test.c

diff --git a/MAINTAINERS b/MAINTAINERS
index 7ef985e01457..9ccabdb25a26 100644
--- a/MAINTAINERS
+++ b/MAINTAINERS
@@ -9504,6 +9504,11 @@ F:	Documentation/misc-devices/lis3lv02d.rst
 F:	drivers/misc/lis3lv02d/
 F:	drivers/platform/x86/hp_accel.c
 
+LIST UNIT TEST
+M:	David Gow <davidgow@google.com>
+S:	Maintained
+F:	lib/list-test.c
+
 LIVE PATCHING
 M:	Josh Poimboeuf <jpoimboe@redhat.com>
 M:	Jiri Kosina <jikos@kernel.org>
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
index a3017a5dadcd..7b648141ff52 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 structures"
+	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..52522ba83a68
--- /dev/null
+++ b/lib/list-test.c
@@ -0,0 +1,738 @@
+// SPDX-License-Identifier: GPL-2.0
+/*
+ * KUnit test for the Kernel Linked-list structures.
+ *
+ * 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;
+};
+
+static void list_test_list_init(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);
+	struct list_head *list4;
+	struct list_head *list5;
+
+	INIT_LIST_HEAD(&list2);
+
+	list4 = kzalloc(sizeof(*list4), 0);
+	INIT_LIST_HEAD(list4);
+
+	list5 = kmalloc(sizeof(*list5), 0);
+	memset(list5, 0xFF, sizeof(*list5));
+	INIT_LIST_HEAD(list5);
+
+	/* 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));
+	KUNIT_EXPECT_TRUE(test, list_empty_careful(list4));
+	KUNIT_EXPECT_TRUE(test, list_empty_careful(list5));
+
+	kfree(list4);
+	kfree(list5);
+}
+
+static void list_test_list_add(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_test_list_add_tail(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_test_list_del(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_test_list_replace(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_test_list_replace_init(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_test_list_swap(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_test_list_del_init(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_test_list_move(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_test_list_move_tail(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_test_list_bulk_move_tail(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_test_list_is_first(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_test_list_is_last(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_test_list_empty(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_test_list_empty_careful(struct kunit *test)
+{
+	/* This test doesn't check correctness under concurrent access */
+	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_test_list_rotate_left(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_test_list_rotate_to_front(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_test_list_is_singular(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_test_list_cut_position(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_test_list_cut_before(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_test_list_splice(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_test_list_splice_tail(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_test_list_splice_init(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_test_list_splice_tail_init(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_test_list_entry(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_test_list_first_entry(struct kunit *test)
+{
+	struct list_test_struct test_struct1, test_struct2;
+	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_test_list_last_entry(struct kunit *test)
+{
+	struct list_test_struct test_struct1, test_struct2;
+	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_test_list_first_entry_or_null(struct kunit *test)
+{
+	struct list_test_struct test_struct1, test_struct2;
+	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_test_list_next_entry(struct kunit *test)
+{
+	struct list_test_struct test_struct1, test_struct2;
+	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_test_list_prev_entry(struct kunit *test)
+{
+	struct list_test_struct test_struct1, test_struct2;
+	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_test_list_for_each(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_test_list_for_each_prev(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_test_list_for_each_safe(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);
+	KUNIT_EXPECT_TRUE(test, list_empty(&list));
+}
+
+static void list_test_list_for_each_prev_safe(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);
+	KUNIT_EXPECT_TRUE(test, list_empty(&list));
+}
+
+static void list_test_list_for_each_entry(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++;
+	}
+	
+	KUNIT_EXPECT_EQ(test, i, 5);
+}
+
+static void list_test_list_for_each_entry_reverse(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--;
+	}
+	
+	KUNIT_EXPECT_EQ(test, i, -1);
+}
+
+static struct kunit_case list_test_cases[] = {
+	KUNIT_CASE(list_test_list_init),
+	KUNIT_CASE(list_test_list_add),
+	KUNIT_CASE(list_test_list_add_tail),
+	KUNIT_CASE(list_test_list_del),
+	KUNIT_CASE(list_test_list_replace),
+	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_move),
+	KUNIT_CASE(list_test_list_move_tail),
+	KUNIT_CASE(list_test_list_bulk_move_tail),
+	KUNIT_CASE(list_test_list_is_first),
+	KUNIT_CASE(list_test_list_is_last),
+	KUNIT_CASE(list_test_list_empty),
+	KUNIT_CASE(list_test_list_empty_careful),
+	KUNIT_CASE(list_test_list_rotate_left),
+	KUNIT_CASE(list_test_list_rotate_to_front),
+	KUNIT_CASE(list_test_list_is_singular),
+	KUNIT_CASE(list_test_list_cut_position),
+	KUNIT_CASE(list_test_list_cut_before),
+	KUNIT_CASE(list_test_list_splice),
+	KUNIT_CASE(list_test_list_splice_tail),
+	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_first_entry),
+	KUNIT_CASE(list_test_list_last_entry),
+	KUNIT_CASE(list_test_list_first_entry_or_null),
+	KUNIT_CASE(list_test_list_next_entry),
+	KUNIT_CASE(list_test_list_prev_entry),
+	KUNIT_CASE(list_test_list_for_each),
+	KUNIT_CASE(list_test_list_for_each_prev),
+	KUNIT_CASE(list_test_list_for_each_safe),
+	KUNIT_CASE(list_test_list_for_each_prev_safe),
+	KUNIT_CASE(list_test_list_for_each_entry),
+	KUNIT_CASE(list_test_list_for_each_entry_reverse),
+	{},
+};
+
+static struct kunit_suite list_test_module = {
+	.name = "list-test",
+	.test_cases = list_test_cases,
+};
+
+kunit_test_suite(list_test_module);
-- 
2.23.0.700.g56cf767bdb-goog

Re: [PATCH linux-kselftest/test v2] lib/list-test: add a test for the 'list' doubly linked list

[Andrew Morton]

On Thu, 10 Oct 2019 11:56:31 -0700 David Gow <davidgow@google.com> wrote:

> Add a KUnit test for the kernel doubly linked list implementation in
> include/linux/list.h
> 
> Each test case (list_test_x) is focused on testing the behaviour of the
> list function/macro 'x'. None of the tests pass invalid lists to these
> macros, and so should behave identically with DEBUG_LIST enabled and
> disabled.
> 
> 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).

<looks at kunit>

Given that everything runs at late_initcall time, shouldn't everything
be __init, __initdata etc so all the code and data doesn't hang around
for ever?

Re: [PATCH linux-kselftest/test v2] lib/list-test: add a test for the 'list' doubly linked list

[Andrew Morton]

On Thu, 10 Oct 2019 11:56:31 -0700 David Gow <davidgow@google.com> wrote:

> Add a KUnit test for the kernel doubly linked list implementation in
> include/linux/list.h
> 
> Each test case (list_test_x) is focused on testing the behaviour of the
> list function/macro 'x'. None of the tests pass invalid lists to these
> macros, and so should behave identically with DEBUG_LIST enabled and
> disabled.
> 
> 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).
> 
> ...
>
>  MAINTAINERS       |   5 +
>  lib/Kconfig.debug |  12 +
>  lib/Makefile      |   3 +
>  lib/list-test.c   | 738 ++++++++++++++++++++++++++++++++++++++++++++++

Should this be lib/kunit/list-test.c?

Re: [PATCH linux-kselftest/test v2] lib/list-test: add a test for the 'list' doubly linked list

[David Gow]

[-- Attachment #1: Type: text/plain, Size: 1805 bytes --]

On Fri, Oct 11, 2019 at 2:05 PM Andrew Morton <akpm@linux-foundation.org> wrote:
>
> <looks at kunit>
>
> Given that everything runs at late_initcall time, shouldn't everything
> be __init, __initdata etc so all the code and data doesn't hang around
> for ever?
>

That's an interesting point. We haven't done this for KUnit tests to
date, and there is certainly a possibility down the line that we may
want to be able to run these tests in other circumstances. (There's
some work being done to allow KUnit and KUnit tests to be built as
modules here: https://lkml.org/lkml/2019/10/8/628 for example.) Maybe
it'd be worth having macros which wrap __init/__initdata etc as a way
of futureproofing tests against such a change?

Either way, I suspect this is something that should probably be
considered for KUnit as a whole, rather than on a test-by-test basis.

On Fri, Oct 11, 2019 at 2:06 PM Andrew Morton <akpm@linux-foundation.org> wrote:
>
> On Thu, 10 Oct 2019 11:56:31 -0700 David Gow <davidgow@google.com> wrote:
>
> > Reply-To: 20191007213633.92565-1-davidgow@google.com
>
> That's a bit irksome.  Deliberate?

Whoops, this was supposed to be In-Reply-To. Please ignore it.


On Fri, Oct 11, 2019 at 2:07 PM Andrew Morton <akpm@linux-foundation.org> wrote:
>
> On Thu, 10 Oct 2019 11:56:31 -0700 David Gow <davidgow@google.com> wrote:
> >  lib/list-test.c   | 738 ++++++++++++++++++++++++++++++++++++++++++++++
>
> Should this be lib/kunit/list-test.c?
>

The idea here was to have KUnit tests co-located with the code being
tested, but with the linked-list code contained to a header, lib/
seemed the best place to put it, being alongside list_debug.c and
similar.
lib/kunit just contains the implementation for the KUnit framework
itself (and tests which test that framework).

Cheers,
-- David

[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 4847 bytes --]

Re: [PATCH linux-kselftest/test v2] lib/list-test: add a test for the 'list' doubly linked list

[Andrew Morton]

On Fri, 11 Oct 2019 14:37:25 -0700 David Gow <davidgow@google.com> wrote:

> On Fri, Oct 11, 2019 at 2:05 PM Andrew Morton <akpm@linux-foundation.org> wrote:
> >
> > <looks at kunit>
> >
> > Given that everything runs at late_initcall time, shouldn't everything
> > be __init, __initdata etc so all the code and data doesn't hang around
> > for ever?
> >
> 
> That's an interesting point. We haven't done this for KUnit tests to
> date, and there is certainly a possibility down the line that we may
> want to be able to run these tests in other circumstances. (There's
> some work being done to allow KUnit and KUnit tests to be built as
> modules here: https://lkml.org/lkml/2019/10/8/628 for example.) Maybe
> it'd be worth having macros which wrap __init/__initdata etc as a way
> of futureproofing tests against such a change?
> 
> Either way, I suspect this is something that should probably be
> considered for KUnit as a whole, rather than on a test-by-test basis.

Sure, a new set of macros for this makes sense.  Can be retrofitted any
time.

There might be a way of loading all of list_test.o into a discardable
section at link time instead of sprinkling annotation all over the .c
code.

Re: [PATCH linux-kselftest/test v2] lib/list-test: add a test for the 'list' doubly linked list

[Brendan Higgins]

On Fri, Oct 11, 2019 at 2:55 PM Andrew Morton <akpm@linux-foundation.org> wrote:
>
> On Fri, 11 Oct 2019 14:37:25 -0700 David Gow <davidgow@google.com> wrote:
>
> > On Fri, Oct 11, 2019 at 2:05 PM Andrew Morton <akpm@linux-foundation.org> wrote:
> > >
> > > <looks at kunit>
> > >
> > > Given that everything runs at late_initcall time, shouldn't everything
> > > be __init, __initdata etc so all the code and data doesn't hang around
> > > for ever?
> > >
> >
> > That's an interesting point. We haven't done this for KUnit tests to
> > date, and there is certainly a possibility down the line that we may
> > want to be able to run these tests in other circumstances. (There's
> > some work being done to allow KUnit and KUnit tests to be built as
> > modules here: https://lkml.org/lkml/2019/10/8/628 for example.) Maybe
> > it'd be worth having macros which wrap __init/__initdata etc as a way
> > of futureproofing tests against such a change?
> >
> > Either way, I suspect this is something that should probably be
> > considered for KUnit as a whole, rather than on a test-by-test basis.
>
> Sure, a new set of macros for this makes sense.  Can be retrofitted any
> time.
>
> There might be a way of loading all of list_test.o into a discardable
> section at link time instead of sprinkling annotation all over the .c
> code.

I created a bug to track this here:
https://bugzilla.kernel.org/show_bug.cgi?id=205217

Re: [PATCH linux-kselftest/test v2] lib/list-test: add a test for the 'list' doubly linked list

[David Gow]

[-- Attachment #1: Type: text/plain, Size: 2217 bytes --]

Hi all,

Thanks, Andrew, for the review and for adding this to the -mm tree --
having some soak time in -next has been helpful and picked up at least
one bug.

Since KUnit is not yet in Linus' branch, though, it probably makes
sense to put this test into the linux-kselftest/test branch, so that
there aren't any chances of the list test getting in without the KUnit
infrastructure. Ultimately, once KUnit is upstream, this shouldn't be
an issue, but it is probably easier to consolidate things for now.
Does that sound sensible?

In any case, I plan to send a v3 patch out shortly which addresses
some memory allocation warnings (caught by Dan Carpenter, thanks!). I
could always do that as a separate bugfix patch if people preferred,
though, but if this switches to the linux-kselftest/test branch, I
feel we might as well get it right in the original patch.

Cheers,
-- David




On Fri, Oct 11, 2019 at 2:55 PM Andrew Morton <akpm@linux-foundation.org> wrote:
>
> On Fri, 11 Oct 2019 14:37:25 -0700 David Gow <davidgow@google.com> wrote:
>
> > On Fri, Oct 11, 2019 at 2:05 PM Andrew Morton <akpm@linux-foundation.org> wrote:
> > >
> > > <looks at kunit>
> > >
> > > Given that everything runs at late_initcall time, shouldn't everything
> > > be __init, __initdata etc so all the code and data doesn't hang around
> > > for ever?
> > >
> >
> > That's an interesting point. We haven't done this for KUnit tests to
> > date, and there is certainly a possibility down the line that we may
> > want to be able to run these tests in other circumstances. (There's
> > some work being done to allow KUnit and KUnit tests to be built as
> > modules here: https://lkml.org/lkml/2019/10/8/628 for example.) Maybe
> > it'd be worth having macros which wrap __init/__initdata etc as a way
> > of futureproofing tests against such a change?
> >
> > Either way, I suspect this is something that should probably be
> > considered for KUnit as a whole, rather than on a test-by-test basis.
>
> Sure, a new set of macros for this makes sense.  Can be retrofitted any
> time.
>
> There might be a way of loading all of list_test.o into a discardable
> section at link time instead of sprinkling annotation all over the .c
> code.

[-- Attachment #2: S/MIME Cryptographic Signature --]
[-- Type: application/pkcs7-signature, Size: 3854 bytes --]

Re: [PATCH linux-kselftest/test v2] lib/list-test: add a test for the 'list' doubly linked list

[Andrew Morton]

On Wed, 16 Oct 2019 14:48:59 -0700 David Gow <davidgow@google.com> wrote:

> Since KUnit is not yet in Linus' branch, though, it probably makes
> sense to put this test into the linux-kselftest/test branch, so that
> there aren't any chances of the list test getting in without the KUnit
> infrastructure. Ultimately, once KUnit is upstream, this shouldn't be
> an issue, but it is probably easier to consolidate things for now.
> Does that sound sensible?

Well, whatever.  I have a note that it's dependent on kunit.

Re: [PATCH linux-kselftest/test v2] lib/list-test: add a test for the 'list' doubly linked list

[shuah]

Hi David,

On 10/10/19 12:56 PM, David Gow wrote:
> Add a KUnit test for the kernel doubly linked list implementation in
> include/linux/list.h
> 
> Each test case (list_test_x) is focused on testing the behaviour of the
> list function/macro 'x'. None of the tests pass invalid lists to these
> macros, and so should behave identically with DEBUG_LIST enabled and
> disabled.
> 
> 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).
> 
> Signed-off-by: David Gow <davidgow@google.com>
> ---
> Addressed the various comments on v1. The biggest change is the renaming
> of all of the testcases from the form x_test to list_test_x. I'm not
> super happy with how that looks (not the least because it ends up with
> 'list' twice), but it is more consistent with the proc/sysctl tests.
> 
> 

I am sorry for commenting on this late. I have a comment on the config
option naming.

>   MAINTAINERS       |   5 +
>   lib/Kconfig.debug |  12 +
>   lib/Makefile      |   3 +
>   lib/list-test.c   | 738 ++++++++++++++++++++++++++++++++++++++++++++++
>   4 files changed, 758 insertions(+)
>   create mode 100644 lib/list-test.c
> 
> diff --git a/MAINTAINERS b/MAINTAINERS
> index 7ef985e01457..9ccabdb25a26 100644
> --- a/MAINTAINERS
> +++ b/MAINTAINERS
> @@ -9504,6 +9504,11 @@ F:	Documentation/misc-devices/lis3lv02d.rst
>   F:	drivers/misc/lis3lv02d/
>   F:	drivers/platform/x86/hp_accel.c
>   
> +LIST UNIT TEST
> +M:	David Gow <davidgow@google.com>
> +S:	Maintained
> +F:	lib/list-test.c
> +
>   LIVE PATCHING
>   M:	Josh Poimboeuf <jpoimboe@redhat.com>
>   M:	Jiri Kosina <jikos@kernel.org>
> diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug
> index a3017a5dadcd..7b648141ff52 100644
> --- a/lib/Kconfig.debug
> +++ b/lib/Kconfig.debug
> @@ -1961,6 +1961,18 @@ config SYSCTL_KUNIT_TEST
>   
>   	  If unsure, say N.
>   
> +config LIST_TEST

It is a good idea to have KUNIT in the naming and it is consistent
with the ext4 test naming which is CONFIG_EXT4_KUNIT_TESTS

> +	bool "KUnit Test for Kernel Linked-list structures"
> +	depends on KUNIT
> +	help
> +	  This builds the linked list unit test, which runs on boot.

What happens if this fails - does the system boot. Please capture this
information here as well as in the commit log. I also would like to
wording similar to the what ext4 test - definitely the part about
"not for inclusion into a production build."

"KUnit tests run during boot and output the results to the debug log
in TAP format (http://testanything.org/). Only useful for kernel devs
running KUnit test harness and are not for inclusion into a production
build."


> +	  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..52522ba83a68
> --- /dev/null
> +++ b/lib/list-test.c
> @@ -0,0 +1,738 @@
> +// SPDX-License-Identifier: GPL-2.0
> +/*
> + * KUnit test for the Kernel Linked-list structures.
> + *
> + * 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;
> +};
> +
> +static void list_test_list_init(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);
> +	struct list_head *list4;
> +	struct list_head *list5;
> +
> +	INIT_LIST_HEAD(&list2);
> +
> +	list4 = kzalloc(sizeof(*list4), 0);
> +	INIT_LIST_HEAD(list4);
> +
> +	list5 = kmalloc(sizeof(*list5), 0);
> +	memset(list5, 0xFF, sizeof(*list5));
> +	INIT_LIST_HEAD(list5);
> +
> +	/* 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));
> +	KUNIT_EXPECT_TRUE(test, list_empty_careful(list4));
> +	KUNIT_EXPECT_TRUE(test, list_empty_careful(list5));
> +
> +	kfree(list4);
> +	kfree(list5);
> +}
> +
> +static void list_test_list_add(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_test_list_add_tail(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_test_list_del(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_test_list_replace(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_test_list_replace_init(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_test_list_swap(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_test_list_del_init(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_test_list_move(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_test_list_move_tail(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_test_list_bulk_move_tail(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_test_list_is_first(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_test_list_is_last(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_test_list_empty(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_test_list_empty_careful(struct kunit *test)
> +{
> +	/* This test doesn't check correctness under concurrent access */
> +	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_test_list_rotate_left(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_test_list_rotate_to_front(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_test_list_is_singular(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_test_list_cut_position(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_test_list_cut_before(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_test_list_splice(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_test_list_splice_tail(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_test_list_splice_init(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_test_list_splice_tail_init(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_test_list_entry(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_test_list_first_entry(struct kunit *test)
> +{
> +	struct list_test_struct test_struct1, test_struct2;
> +	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_test_list_last_entry(struct kunit *test)
> +{
> +	struct list_test_struct test_struct1, test_struct2;
> +	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_test_list_first_entry_or_null(struct kunit *test)
> +{
> +	struct list_test_struct test_struct1, test_struct2;
> +	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_test_list_next_entry(struct kunit *test)
> +{
> +	struct list_test_struct test_struct1, test_struct2;
> +	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_test_list_prev_entry(struct kunit *test)
> +{
> +	struct list_test_struct test_struct1, test_struct2;
> +	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_test_list_for_each(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_test_list_for_each_prev(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_test_list_for_each_safe(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);
> +	KUNIT_EXPECT_TRUE(test, list_empty(&list));
> +}
> +
> +static void list_test_list_for_each_prev_safe(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);
> +	KUNIT_EXPECT_TRUE(test, list_empty(&list));
> +}
> +
> +static void list_test_list_for_each_entry(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++;
> +	}
> +	
> +	KUNIT_EXPECT_EQ(test, i, 5);
> +}
> +
> +static void list_test_list_for_each_entry_reverse(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--;
> +	}
> +	
> +	KUNIT_EXPECT_EQ(test, i, -1);
> +}
> +
> +static struct kunit_case list_test_cases[] = {
> +	KUNIT_CASE(list_test_list_init),
> +	KUNIT_CASE(list_test_list_add),
> +	KUNIT_CASE(list_test_list_add_tail),
> +	KUNIT_CASE(list_test_list_del),
> +	KUNIT_CASE(list_test_list_replace),
> +	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_move),
> +	KUNIT_CASE(list_test_list_move_tail),
> +	KUNIT_CASE(list_test_list_bulk_move_tail),
> +	KUNIT_CASE(list_test_list_is_first),
> +	KUNIT_CASE(list_test_list_is_last),
> +	KUNIT_CASE(list_test_list_empty),
> +	KUNIT_CASE(list_test_list_empty_careful),
> +	KUNIT_CASE(list_test_list_rotate_left),
> +	KUNIT_CASE(list_test_list_rotate_to_front),
> +	KUNIT_CASE(list_test_list_is_singular),
> +	KUNIT_CASE(list_test_list_cut_position),
> +	KUNIT_CASE(list_test_list_cut_before),
> +	KUNIT_CASE(list_test_list_splice),
> +	KUNIT_CASE(list_test_list_splice_tail),
> +	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_first_entry),
> +	KUNIT_CASE(list_test_list_last_entry),
> +	KUNIT_CASE(list_test_list_first_entry_or_null),
> +	KUNIT_CASE(list_test_list_next_entry),
> +	KUNIT_CASE(list_test_list_prev_entry),
> +	KUNIT_CASE(list_test_list_for_each),
> +	KUNIT_CASE(list_test_list_for_each_prev),
> +	KUNIT_CASE(list_test_list_for_each_safe),
> +	KUNIT_CASE(list_test_list_for_each_prev_safe),
> +	KUNIT_CASE(list_test_list_for_each_entry),
> +	KUNIT_CASE(list_test_list_for_each_entry_reverse),
> +	{},
> +};
> +
> +static struct kunit_suite list_test_module = {
> +	.name = "list-test",

Please use kunit in the name here.

> +	.test_cases = list_test_cases,
> +};
> +
> +kunit_test_suite(list_test_module);
> 

thanks,
-- Shuah

Re: [PATCH linux-kselftest/test v2] lib/list-test: add a test for the 'list' doubly linked list

[shuah]

On 10/16/19 6:32 PM, Andrew Morton wrote:
> On Wed, 16 Oct 2019 14:48:59 -0700 David Gow <davidgow@google.com> wrote:
> 
>> Since KUnit is not yet in Linus' branch, though, it probably makes
>> sense to put this test into the linux-kselftest/test branch, so that
>> there aren't any chances of the list test getting in without the KUnit
>> infrastructure. Ultimately, once KUnit is upstream, this shouldn't be
>> an issue, but it is probably easier to consolidate things for now.
>> Does that sound sensible?
> 
> Well, whatever.  I have a note that it's dependent on kunit.
> 
David and Andrew,

I have a few comments on CONFIG naming to be consistent with the other
kunit ext4 test and a couple of other comments that would requite v3.

I would like to bundle these in the pull request with KUnit framework.
Hope that is okay with you.

thanks,
-- Shuah