linux-kernel.vger.kernel.org archive mirror
 help / color / mirror / Atom feed
* [PATCH] lib/list-test: add a test for the 'list' doubly linked list
@ 2019-10-07 21:36 David Gow
  2019-10-07 21:58 ` Brendan Higgins
                   ` (3 more replies)
  0 siblings, 4 replies; 8+ messages in thread
From: David Gow @ 2019-10-07 21:36 UTC (permalink / raw)
  To: shuah, brendanhiggins, akpm, keescook
  Cc: linux-kselftest, kunit-dev, linux-kernel, David Gow

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);
+
+	/* 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);
-- 
2.23.0.581.g78d2f28ef7-goog


^ permalink raw reply related	[flat|nested] 8+ messages in thread

* Re: [PATCH] lib/list-test: add a test for the 'list' doubly linked list
  2019-10-07 21:36 [PATCH] lib/list-test: add a test for the 'list' doubly linked list David Gow
@ 2019-10-07 21:58 ` Brendan Higgins
  2019-10-08  1:03 ` Kees Cook
                   ` (2 subsequent siblings)
  3 siblings, 0 replies; 8+ messages in thread
From: Brendan Higgins @ 2019-10-07 21:58 UTC (permalink / raw)
  To: David Gow; +Cc: shuah, akpm, keescook, linux-kselftest, kunit-dev, linux-kernel

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!

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] lib/list-test: add a test for the 'list' doubly linked list
  2019-10-07 21:36 [PATCH] lib/list-test: add a test for the 'list' doubly linked list David Gow
  2019-10-07 21:58 ` Brendan Higgins
@ 2019-10-08  1:03 ` Kees Cook
  2019-10-08 23:30   ` David Gow
  2019-10-08  3:29 ` Kees Cook
  2019-10-08 17:48 ` Brendan Higgins
  3 siblings, 1 reply; 8+ messages in thread
From: Kees Cook @ 2019-10-08  1:03 UTC (permalink / raw)
  To: David Gow
  Cc: shuah, brendanhiggins, akpm, linux-kselftest, kunit-dev, linux-kernel

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!
:)

-- 
Kees Cook

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] lib/list-test: add a test for the 'list' doubly linked list
  2019-10-07 21:36 [PATCH] lib/list-test: add a test for the 'list' doubly linked list David Gow
  2019-10-07 21:58 ` Brendan Higgins
  2019-10-08  1:03 ` Kees Cook
@ 2019-10-08  3:29 ` Kees Cook
  2019-10-08 17:48 ` Brendan Higgins
  3 siblings, 0 replies; 8+ messages in thread
From: Kees Cook @ 2019-10-08  3:29 UTC (permalink / raw)
  To: David Gow
  Cc: shuah, brendanhiggins, akpm, linux-kselftest, kunit-dev, linux-kernel

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"

-- 
Kees Cook

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] lib/list-test: add a test for the 'list' doubly linked list
  2019-10-07 21:36 [PATCH] lib/list-test: add a test for the 'list' doubly linked list David Gow
                   ` (2 preceding siblings ...)
  2019-10-08  3:29 ` Kees Cook
@ 2019-10-08 17:48 ` Brendan Higgins
  2019-10-08 18:15   ` Kees Cook
  3 siblings, 1 reply; 8+ messages in thread
From: Brendan Higgins @ 2019-10-08 17:48 UTC (permalink / raw)
  To: David Gow; +Cc: shuah, akpm, keescook, linux-kselftest, kunit-dev, linux-kernel

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!

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] lib/list-test: add a test for the 'list' doubly linked list
  2019-10-08 17:48 ` Brendan Higgins
@ 2019-10-08 18:15   ` Kees Cook
  2019-10-08 22:59     ` Brendan Higgins
  0 siblings, 1 reply; 8+ messages in thread
From: Kees Cook @ 2019-10-08 18:15 UTC (permalink / raw)
  To: Brendan Higgins
  Cc: David Gow, shuah, akpm, linux-kselftest, kunit-dev, linux-kernel

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?

-- 
Kees Cook

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] lib/list-test: add a test for the 'list' doubly linked list
  2019-10-08 18:15   ` Kees Cook
@ 2019-10-08 22:59     ` Brendan Higgins
  0 siblings, 0 replies; 8+ messages in thread
From: Brendan Higgins @ 2019-10-08 22:59 UTC (permalink / raw)
  To: Kees Cook
  Cc: David Gow, shuah, Andrew Morton,
	open list:KERNEL SELFTEST FRAMEWORK, kunit-dev,
	Linux Kernel Mailing List

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!

^ permalink raw reply	[flat|nested] 8+ messages in thread

* Re: [PATCH] lib/list-test: add a test for the 'list' doubly linked list
  2019-10-08  1:03 ` Kees Cook
@ 2019-10-08 23:30   ` David Gow
  0 siblings, 0 replies; 8+ messages in thread
From: David Gow @ 2019-10-08 23:30 UTC (permalink / raw)
  To: Kees Cook
  Cc: Shuah Khan, Brendan Higgins, akpm,
	open list:KERNEL SELFTEST FRAMEWORK, kunit-dev, linux-kernel

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

^ permalink raw reply	[flat|nested] 8+ messages in thread

end of thread, other threads:[~2019-10-08 23:31 UTC | newest]

Thread overview: 8+ messages (download: mbox.gz / follow: Atom feed)
-- links below jump to the message on this page --
2019-10-07 21:36 [PATCH] lib/list-test: add a test for the 'list' doubly linked list David Gow
2019-10-07 21:58 ` Brendan Higgins
2019-10-08  1:03 ` Kees Cook
2019-10-08 23:30   ` David Gow
2019-10-08  3:29 ` Kees Cook
2019-10-08 17:48 ` Brendan Higgins
2019-10-08 18:15   ` Kees Cook
2019-10-08 22:59     ` Brendan Higgins

This is a public inbox, see mirroring instructions
for how to clone and mirror all data and code used for this inbox;
as well as URLs for NNTP newsgroup(s).