On Mon, Sep 16, 2024 at 8:51 PM Artur Alves arturacb@gmail.com wrote:
Add KUnit tests for the llist data structure. They test the vast majority of methods and macros defined in include/linux/llist.h.
These are inspired by the existing tests for the 'list' doubly linked in lib/list-test.c. Each test case (llist_test_x) tests the behaviour of the llist function/macro 'x'.
Signed-off-by: Artur Alves arturacb@gmail.com
Hello!
Sorry for the delay in getting back to you. We have been busy with LPC. This looks good to me!
I just have one comment left: the patch to add the lib/tests directory hasn't landed in the kselftest/kunit branch so this patch doesn't apply cleanly. Since we are planning on taking this patch through that branch, could you switch the files to be lib/Makefile and lib/llist_kunit.c for now. And we can move them in the great migration later.
But otherwise, Reviewed-by: Rae Moar rmoar@google.com
Thanks! Rae
lib/Kconfig.debug | 11 ++ lib/tests/Makefile | 1 + lib/tests/llist_kunit.c | 358 ++++++++++++++++++++++++++++++++++++++++ 3 files changed, 370 insertions(+) create mode 100644 lib/tests/llist_kunit.c
diff --git a/lib/Kconfig.debug b/lib/Kconfig.debug index b5696659f027..f6bd98f8ce2b 100644 --- a/lib/Kconfig.debug +++ b/lib/Kconfig.debug @@ -2813,6 +2813,17 @@ config USERCOPY_KUNIT_TEST on the copy_to/from_user infrastructure, making sure basic user/kernel boundary testing is working.
+config LLIST_KUNIT_TEST
tristate "KUnit tests for lib/llist" if !KUNIT_ALL_TESTSdepends on KUNITdefault KUNIT_ALL_TESTShelpThis option builds the llist (lock-less list) KUnit test suite.It tests the API and basic functionality of the macros andfunctions defined in <linux/llist.h>.If unsure, say N.config TEST_UDELAY tristate "udelay test driver" help diff --git a/lib/tests/Makefile b/lib/tests/Makefile index c6a14cc8663e..8d7c40a73110 100644 --- a/lib/tests/Makefile +++ b/lib/tests/Makefile @@ -34,4 +34,5 @@ CFLAGS_stackinit_kunit.o += $(call cc-disable-warning, switch-unreachable) obj-$(CONFIG_STACKINIT_KUNIT_TEST) += stackinit_kunit.o obj-$(CONFIG_STRING_KUNIT_TEST) += string_kunit.o obj-$(CONFIG_STRING_HELPERS_KUNIT_TEST) += string_helpers_kunit.o +obj-$(CONFIG_LLIST_KUNIT_TEST) += llist_kunit.o
diff --git a/lib/tests/llist_kunit.c b/lib/tests/llist_kunit.c new file mode 100644 index 000000000000..817bb2948697 --- /dev/null +++ b/lib/tests/llist_kunit.c @@ -0,0 +1,358 @@ +// SPDX-License-Identifier: GPL-2.0 +/*
- KUnit test for the Kernel lock-less linked-list structure.
- Author: Artur Alves arturacb@gmail.com
- */
+#include <kunit/test.h> +#include <linux/llist.h>
+#define ENTRIES_SIZE 3
+struct llist_test_struct {
int data;struct llist_node node;+};
+static void llist_test_init_llist(struct kunit *test) +{
/* test if the llist is correctly initialized */struct llist_head llist1 = LLIST_HEAD_INIT(llist1);LLIST_HEAD(llist2);struct llist_head llist3, *llist4, *llist5;KUNIT_EXPECT_TRUE(test, llist_empty(&llist1));KUNIT_EXPECT_TRUE(test, llist_empty(&llist2));init_llist_head(&llist3);KUNIT_EXPECT_TRUE(test, llist_empty(&llist3));llist4 = kzalloc(sizeof(*llist4), GFP_KERNEL | __GFP_NOFAIL);init_llist_head(llist4);KUNIT_EXPECT_TRUE(test, llist_empty(llist4));kfree(llist4);llist5 = kmalloc(sizeof(*llist5), GFP_KERNEL | __GFP_NOFAIL);memset(llist5, 0xFF, sizeof(*llist5));init_llist_head(llist5);KUNIT_EXPECT_TRUE(test, llist_empty(llist5));kfree(llist5);+}
+static void llist_test_init_llist_node(struct kunit *test) +{
struct llist_node a;init_llist_node(&a);KUNIT_EXPECT_PTR_EQ(test, a.next, &a);+}
+static void llist_test_llist_entry(struct kunit *test) +{
struct llist_test_struct test_struct, *aux;struct llist_node *llist = &test_struct.node;aux = llist_entry(llist, struct llist_test_struct, node);KUNIT_EXPECT_PTR_EQ(test, &test_struct, aux);+}
+static void llist_test_add(struct kunit *test) +{
struct llist_node a, b;LLIST_HEAD(llist);init_llist_node(&a);init_llist_node(&b);/* The first assertion must be true, given that llist is empty */KUNIT_EXPECT_TRUE(test, llist_add(&a, &llist));KUNIT_EXPECT_FALSE(test, llist_add(&b, &llist));/* Should be [List] -> b -> a */KUNIT_EXPECT_PTR_EQ(test, llist.first, &b);KUNIT_EXPECT_PTR_EQ(test, b.next, &a);+}
+static void llist_test_add_batch(struct kunit *test) +{
struct llist_node a, b, c;LLIST_HEAD(llist);LLIST_HEAD(llist2);init_llist_node(&a);init_llist_node(&b);init_llist_node(&c);llist_add(&a, &llist2);llist_add(&b, &llist2);llist_add(&c, &llist2);/* This assertion must be true, given that llist is empty */KUNIT_EXPECT_TRUE(test, llist_add_batch(&c, &a, &llist));/* should be [List] -> c -> b -> a */KUNIT_EXPECT_PTR_EQ(test, llist.first, &c);KUNIT_EXPECT_PTR_EQ(test, c.next, &b);KUNIT_EXPECT_PTR_EQ(test, b.next, &a);+}
+static void llist_test_llist_next(struct kunit *test) +{
struct llist_node a, b;LLIST_HEAD(llist);init_llist_node(&a);init_llist_node(&b);llist_add(&a, &llist);llist_add(&b, &llist);/* should be [List] -> b -> a */KUNIT_EXPECT_PTR_EQ(test, llist_next(&b), &a);KUNIT_EXPECT_NULL(test, llist_next(&a));+}
+static void llist_test_empty_llist(struct kunit *test) +{
struct llist_head llist = LLIST_HEAD_INIT(llist);struct llist_node a;KUNIT_EXPECT_TRUE(test, llist_empty(&llist));llist_add(&a, &llist);KUNIT_EXPECT_FALSE(test, llist_empty(&llist));+}
+static void llist_test_llist_on_list(struct kunit *test) +{
struct llist_node a, b;LLIST_HEAD(llist);init_llist_node(&a);init_llist_node(&b);llist_add(&a, &llist);/* should be [List] -> a */KUNIT_EXPECT_TRUE(test, llist_on_list(&a));KUNIT_EXPECT_FALSE(test, llist_on_list(&b));+}
+static void llist_test_del_first(struct kunit *test) +{
struct llist_node a, b, *c;LLIST_HEAD(llist);llist_add(&a, &llist);llist_add(&b, &llist);/* before: [List] -> b -> a */c = llist_del_first(&llist);/* should be [List] -> a */KUNIT_EXPECT_PTR_EQ(test, llist.first, &a);/* del must return a pointer to llist_node b* the returned pointer must be marked on list*/KUNIT_EXPECT_PTR_EQ(test, c, &b);KUNIT_EXPECT_TRUE(test, llist_on_list(c));+}
+static void llist_test_del_first_init(struct kunit *test) +{
struct llist_node a, *b;LLIST_HEAD(llist);llist_add(&a, &llist);b = llist_del_first_init(&llist);/* should be [List] */KUNIT_EXPECT_TRUE(test, llist_empty(&llist));/* the returned pointer must be marked out of the list */KUNIT_EXPECT_FALSE(test, llist_on_list(b));+}
+static void llist_test_del_first_this(struct kunit *test) +{
struct llist_node a, b;LLIST_HEAD(llist);llist_add(&a, &llist);llist_add(&b, &llist);llist_del_first_this(&llist, &a);/* before: [List] -> b -> a */// should remove only if is the first node in the llistKUNIT_EXPECT_FALSE(test, llist_del_first_this(&llist, &a));KUNIT_EXPECT_TRUE(test, llist_del_first_this(&llist, &b));/* should be [List] -> a */KUNIT_EXPECT_PTR_EQ(test, llist.first, &a);+}
+static void llist_test_del_all(struct kunit *test) +{
struct llist_node a, b;LLIST_HEAD(llist);LLIST_HEAD(empty_llist);llist_add(&a, &llist);llist_add(&b, &llist);/* deleting from a empty llist should return NULL */KUNIT_EXPECT_NULL(test, llist_del_all(&empty_llist));llist_del_all(&llist);KUNIT_EXPECT_TRUE(test, llist_empty(&llist));+}
+static void llist_test_for_each(struct kunit *test) +{
struct llist_node entries[ENTRIES_SIZE] = { 0 };struct llist_node *pos, *deleted_nodes;LLIST_HEAD(llist);int i = 0, j = 0;for (int i = ENTRIES_SIZE - 1; i >= 0; i--)llist_add(&entries[i], &llist);/* before [List] -> entries[0] -> ... -> entries[ENTRIES_SIZE - 1] */llist_for_each(pos, llist.first) {KUNIT_EXPECT_PTR_EQ(test, pos, &entries[i++]);}KUNIT_EXPECT_EQ(test, ENTRIES_SIZE, i);/* traversing deleted nodes */deleted_nodes = llist_del_all(&llist);llist_for_each(pos, deleted_nodes) {KUNIT_EXPECT_PTR_EQ(test, pos, &entries[j++]);}KUNIT_EXPECT_EQ(test, ENTRIES_SIZE, j);+}
+static void llist_test_safe_for_each(struct kunit *test) +{
struct llist_node entries[ENTRIES_SIZE];struct llist_node *pos, *n;LLIST_HEAD(llist);int i = 0;for (int i = ENTRIES_SIZE - 1; i >= 0; i--)llist_add(&entries[i], &llist);llist_for_each_safe(pos, n, llist.first) {KUNIT_EXPECT_PTR_EQ(test, pos, &entries[i++]);llist_del_first(&llist);}KUNIT_EXPECT_EQ(test, ENTRIES_SIZE, i);KUNIT_EXPECT_TRUE(test, llist_empty(&llist));+}
+static void llist_test_entry_for_each(struct kunit *test) +{
struct llist_test_struct entries[ENTRIES_SIZE], *pos;LLIST_HEAD(llist);int i = 0;for (int i = ENTRIES_SIZE - 1; i >= 0; --i) {entries[i].data = i;llist_add(&entries[i].node, &llist);}i = 0;llist_for_each_entry(pos, llist.first, node) {KUNIT_EXPECT_EQ(test, pos->data, i);i++;}KUNIT_EXPECT_EQ(test, ENTRIES_SIZE, i);+}
+static void llist_test_entry_safe_for_each(struct kunit *test) +{
struct llist_test_struct entries[ENTRIES_SIZE], *pos, *n;LLIST_HEAD(llist);int i = 0;for (int i = ENTRIES_SIZE - 1; i >= 0; --i) {entries[i].data = i;llist_add(&entries[i].node, &llist);}i = 0;llist_for_each_entry_safe(pos, n, llist.first, node) {KUNIT_EXPECT_EQ(test, pos->data, i++);llist_del_first(&llist);}KUNIT_EXPECT_EQ(test, ENTRIES_SIZE, i);KUNIT_EXPECT_TRUE(test, llist_empty(&llist));+}
+static void llist_test_reverse_order(struct kunit *test) +{
struct llist_node entries[ENTRIES_SIZE], *pos, *reversed_llist;LLIST_HEAD(llist);int i = 0;for (int i = 0; i < ENTRIES_SIZE; i++)llist_add(&entries[i], &llist);/* before [List] -> entries[2] -> entries[1] -> entries[0] */reversed_llist = llist_reverse_order(llist_del_first(&llist));/* should be [List] -> entries[0] -> entries[1] -> entries[2] */llist_for_each(pos, reversed_llist) {KUNIT_EXPECT_PTR_EQ(test, pos, &entries[i++]);}KUNIT_EXPECT_EQ(test, ENTRIES_SIZE, i);+}
+static struct kunit_case llist_test_cases[] = {
KUNIT_CASE(llist_test_init_llist),KUNIT_CASE(llist_test_init_llist_node),KUNIT_CASE(llist_test_llist_entry),KUNIT_CASE(llist_test_add),KUNIT_CASE(llist_test_add_batch),KUNIT_CASE(llist_test_llist_next),KUNIT_CASE(llist_test_empty_llist),KUNIT_CASE(llist_test_llist_on_list),KUNIT_CASE(llist_test_del_first),KUNIT_CASE(llist_test_del_first_init),KUNIT_CASE(llist_test_del_first_this),KUNIT_CASE(llist_test_del_all),KUNIT_CASE(llist_test_for_each),KUNIT_CASE(llist_test_safe_for_each),KUNIT_CASE(llist_test_entry_for_each),KUNIT_CASE(llist_test_entry_safe_for_each),KUNIT_CASE(llist_test_reverse_order),{}+};
+static struct kunit_suite llist_test_suite = {
.name = "llist",.test_cases = llist_test_cases,+};
+kunit_test_suite(llist_test_suite);
+MODULE_LICENSE("GPL");
+MODULE_DESCRIPTION("KUnit tests for the llist data structure.");
2.46.0
-- You received this message because you are subscribed to the Google Groups "KUnit Development" group. To unsubscribe from this group and stop receiving emails from it, send an email to kunit-dev+unsubscribe@googlegroups.com. To view this discussion on the web visit https://groups.google.com/d/msgid/kunit-dev/20240917005116.304090-2-arturacb....