On Mon, Sep 16, 2024 at 8:51 PM Artur Alves <arturacb@xxxxxxxxx> 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@xxxxxxxxx>
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@xxxxxxxxxx>
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_TESTS
> + depends on KUNIT
> + default KUNIT_ALL_TESTS
> + help
> + This option builds the llist (lock-less list) KUnit test suite.
> + It tests the API and basic functionality of the macros and
> + functions 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@xxxxxxxxx>
> + */
> +
> +#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 llist
> + KUNIT_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@xxxxxxxxxxxxxxxx.
> To view this discussion on the web visit https://groups.google.com/d/msgid/kunit-dev/20240917005116.304090-2-arturacb%40gmail.com.
