Skip to contentSkip to conversation

lib/list-test: add a test for the 'list' doubly linked list

PATCH Superseded David Gow 3 participants 8 messages Oct 7, 2019 – Oct 8, 2019

Subsystems (2)

v1 of 7 Superseded Latest is v7 →

lore
Share & tools
lore

David Gow

author
#0 lore raw

PATCH 1/1 lib/list-test: add a test for the 'list' doubly linked list

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

---
 lib/Kconfig.debug |  12 +
 lib/Makefile      |   3 +
 lib/list-test.c   | 711 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 726 insertions(+)
 create mode 100644 lib/list-test.c
lib/Kconfig.debug +12 -0
index a3017a5dadcd..60691c0aac3e 100644
@@ -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
lib/Makefile +3 -0
index bba1fd5485f7..309e174ee35d 100644
@@ -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
lib/list-test.c new file +711 -0

711 lines not on this page · raw message

Signature · 1 line
2.23.0.581.g78d2f28ef7-goog
Reviewed-by Tested-by on v1 1/1
#1 lore raw
Quoted 10 lines · 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

Others might feel differently than me, but I think this should go in the comment section (below the "---").

Quoted 1 line
Quoted 47 lines
---
 lib/Kconfig.debug |  12 +
 lib/Makefile      |   3 +
 lib/list-test.c   | 711 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 726 insertions(+)
 create mode 100644 lib/list-test.c
lib/Kconfig.debug +12 -0
index a3017a5dadcd..60691c0aac3e 100644
@@ -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
lib/Makefile +3 -0
index bba1fd5485f7..309e174ee35d 100644
@@ -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
lib/list-test.c new file +0 -0
new file mode 100644
index 000000000000..f333e8b0d9fe

lib/list-test.c line 1

Quoted 1 line
lib/list-test.c new file +1 -0
@@ -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 <[email protected]>
*/

lib/list-test.c line 9

Quoted 8 lines
lib/list-test.c new file +8 -0
+#include <kunit/test.h>
+
+#include <linux/list.h>
+
+struct list_test_struct {
+	int data;
+	struct list_head list;
+};

<snip>

Thanks!

#2 lore raw
In reply to David Gow
Quoted 67 lines · 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

---
 lib/Kconfig.debug |  12 +
 lib/Makefile      |   3 +
 lib/list-test.c   | 711 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 726 insertions(+)
 create mode 100644 lib/list-test.c
lib/Kconfig.debug +12 -0
index a3017a5dadcd..60691c0aac3e 100644
@@ -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
lib/Makefile +3 -0
index bba1fd5485f7..309e174ee35d 100644
@@ -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
lib/list-test.c new file +8 -0
new file mode 100644
index 000000000000..f333e8b0d9fe
@@ -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;

lib/list-test.c line 18

Quoted 10 lines
lib/list-test.c new file +10 -0
+};
+
+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. :)

Quoted 459 lines
lib/list-test.c new file +459 -0
+
+	/* 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++;

lib/list-test.c line 487

Quoted 10 lines
lib/list-test.c new file +10 -0
+	}
+
+	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?

lib/list-test.c line 495

Quoted 8 lines
lib/list-test.c new file +8 -0
+
+	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?

lib/list-test.c line 507

Quoted 12 lines
lib/list-test.c new file +12 -0
+
+	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?

lib/list-test.c line 519

Quoted 12 lines
lib/list-test.c new file +12 -0
+
+	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?

lib/list-test.c line 532

Quoted 13 lines
lib/list-test.c new file +13 -0
+
+	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.

lib/list-test.c line 544

Quoted 12 lines
lib/list-test.c new file +12 -0
+
+	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.

Quoted 32 lines
lib/list-test.c new file +32 -0
+
+	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;
+

lib/list-test.c line 586

Quoted 10 lines
lib/list-test.c new file +10 -0
+	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.

Quoted 10 lines
lib/list-test.c new file +10 -0
+}
+
+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);

lib/list-test.c line 606

Quoted 10 lines
lib/list-test.c new file +10 -0
+	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.

Quoted 7 lines
lib/list-test.c new file +7 -0
+}
+
+static void list_for_each_prev_safe_test(struct kunit *test)
+{
+	struct list_head entries[3], *cur, *n;
+	LIST_HEAD(list);
+	int i = 2;

lib/list-test.c line 623

Quoted 10 lines
lib/list-test.c new file +10 -0
+
+	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.

Quoted 30 lines
lib/list-test.c new file +30 -0
+
+	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) {

lib/list-test.c line 663

Quoted 10 lines
lib/list-test.c new file +10 -0
+		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.

Quoted 51 lines
lib/list-test.c new file +48 -0
+}
+
+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);
Signature · 1 line
2.23.0.581.g78d2f28ef7-goog

Thanks for working on this! I'm excited to see some core API unit tests! :)

Signature · 1 line
Kees Cook
#4 lore raw
In reply to David Gow

lib/Kconfig.debug config SYSCTL_KUNIT_TEST · line 1965

Quoted 2 lines · David Gow
lib/Kconfig.debug +2 -0
+config LIST_TEST
+	bool "KUnit Test for Kernel Linked-list stuctures"

I missed this the first time through: typo of "structures"

Signature · 1 line
Kees Cook
#5 lore raw
In reply to David Gow
Quoted 11 lines · 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

Quoted 7 lines
---
 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!

#6 lore raw
Quoted 20 lines · Brendan Higgins
Quoted 11 lines · 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

Quoted 7 lines
---
 lib/Kconfig.debug |  12 +
 lib/Makefile      |   3 +
 lib/list-test.c   | 711 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 726 insertions(+)
 create mode 100644 lib/list-test.c
Quoted 2 lines

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?

Signature · 1 line
Kees Cook
#7 lore raw
Quoted 25 lines · Kees Cook
Quoted 20 lines · Brendan Higgins
Quoted 11 lines · 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

Quoted 7 lines
---
 lib/Kconfig.debug |  12 +
 lib/Makefile      |   3 +
 lib/list-test.c   | 711 ++++++++++++++++++++++++++++++++++++++++++++++
 3 files changed, 726 insertions(+)
 create mode 100644 lib/list-test.c
Quoted 2 lines

Also, I think it might be good to make a MAINTAINERs entry for this test.

Quoted 6 lines

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

Quoted 3 lines

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.

Quoted 5 lines

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!

author
#3 lore raw
In reply to Kees Cook

On Mon, Oct 7, 2019 at 6:03 PM Kees Cook <[email protected]> wrote:
(...)

Quoted 30 lines

lib/list-test.c line 18

Quoted 9 lines
lib/list-test.c new file +9 -0
+
+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);
Quoted 2 lines

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.

Quoted 7 lines

lib/list-test.c line 487

Quoted 3 lines
lib/list-test.c new file +3 -0
+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.

Quoted 11 lines

lib/list-test.c line 495

Quoted 8 lines
lib/list-test.c new file +8 -0
+
+     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.

Quoted 31 lines
Quoted 31 lines
lib/list-test.c new file +31 -0
+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--;
Quoted 9 lines

lib/list-test.c line 586

Quoted 3 lines
lib/list-test.c new file +3 -0
+     }
+
+     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.

Quoted 14 lines
Quoted 14 lines
lib/list-test.c new file +14 -0
+}
+
+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) {
Quoted 9 lines

lib/list-test.c line 606

Quoted 6 lines
lib/list-test.c new file +6 -0
+             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.

Quoted 11 lines
Quoted 11 lines
lib/list-test.c new file +11 -0
+}
+
+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);
Quoted 9 lines

lib/list-test.c line 623

Quoted 6 lines
lib/list-test.c new file +6 -0
+
+     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.

Quoted 40 lines
Quoted 26 lines
lib/list-test.c new file +26 -0
+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) {

lib/list-test.c line 663

Quoted 10 lines
lib/list-test.c new file +10 -0
+             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?

Quoted 5 lines

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