124 lines · c
1// SPDX-License-Identifier: GPL-2.0-only2#include <kunit/test.h>3 4#include <linux/kernel.h>5#include <linux/list_sort.h>6#include <linux/list.h>7#include <linux/module.h>8#include <linux/printk.h>9#include <linux/slab.h>10#include <linux/random.h>11 12/*13 * The pattern of set bits in the list length determines which cases14 * are hit in list_sort().15 */16#define TEST_LIST_LEN (512+128+2) /* not including head */17 18#define TEST_POISON1 0xDEADBEEF19#define TEST_POISON2 0xA324354C20 21struct debug_el {22 unsigned int poison1;23 struct list_head list;24 unsigned int poison2;25 int value;26 unsigned int serial;27};28 29static void check(struct kunit *test, struct debug_el *ela, struct debug_el *elb)30{31 struct debug_el **elts = test->priv;32 33 KUNIT_EXPECT_LT_MSG(test, ela->serial, (unsigned int)TEST_LIST_LEN, "incorrect serial");34 KUNIT_EXPECT_LT_MSG(test, elb->serial, (unsigned int)TEST_LIST_LEN, "incorrect serial");35 36 KUNIT_EXPECT_PTR_EQ_MSG(test, elts[ela->serial], ela, "phantom element");37 KUNIT_EXPECT_PTR_EQ_MSG(test, elts[elb->serial], elb, "phantom element");38 39 KUNIT_EXPECT_EQ_MSG(test, ela->poison1, TEST_POISON1, "bad poison");40 KUNIT_EXPECT_EQ_MSG(test, ela->poison2, TEST_POISON2, "bad poison");41 42 KUNIT_EXPECT_EQ_MSG(test, elb->poison1, TEST_POISON1, "bad poison");43 KUNIT_EXPECT_EQ_MSG(test, elb->poison2, TEST_POISON2, "bad poison");44}45 46/* `priv` is the test pointer so check() can fail the test if the list is invalid. */47static int cmp(void *priv, const struct list_head *a, const struct list_head *b)48{49 struct debug_el *ela, *elb;50 51 ela = container_of(a, struct debug_el, list);52 elb = container_of(b, struct debug_el, list);53 54 check(priv, ela, elb);55 return ela->value - elb->value;56}57 58static void list_sort_test(struct kunit *test)59{60 int i, count = 1;61 struct debug_el *el, **elts;62 struct list_head *cur;63 LIST_HEAD(head);64 65 elts = kunit_kcalloc(test, TEST_LIST_LEN, sizeof(*elts), GFP_KERNEL);66 KUNIT_ASSERT_NOT_ERR_OR_NULL(test, elts);67 test->priv = elts;68 69 for (i = 0; i < TEST_LIST_LEN; i++) {70 el = kunit_kmalloc(test, sizeof(*el), GFP_KERNEL);71 KUNIT_ASSERT_NOT_ERR_OR_NULL(test, el);72 73 /* force some equivalencies */74 el->value = get_random_u32_below(TEST_LIST_LEN / 3);75 el->serial = i;76 el->poison1 = TEST_POISON1;77 el->poison2 = TEST_POISON2;78 elts[i] = el;79 list_add_tail(&el->list, &head);80 }81 82 list_sort(test, &head, cmp);83 84 for (cur = head.next; cur->next != &head; cur = cur->next) {85 struct debug_el *el1;86 int cmp_result;87 88 KUNIT_ASSERT_PTR_EQ_MSG(test, cur->next->prev, cur,89 "list is corrupted");90 91 cmp_result = cmp(test, cur, cur->next);92 KUNIT_ASSERT_LE_MSG(test, cmp_result, 0, "list is not sorted");93 94 el = container_of(cur, struct debug_el, list);95 el1 = container_of(cur->next, struct debug_el, list);96 if (cmp_result == 0) {97 KUNIT_ASSERT_LE_MSG(test, el->serial, el1->serial,98 "order of equivalent elements not preserved");99 }100 101 check(test, el, el1);102 count++;103 }104 KUNIT_EXPECT_PTR_EQ_MSG(test, head.prev, cur, "list is corrupted");105 106 KUNIT_EXPECT_EQ_MSG(test, count, TEST_LIST_LEN,107 "list length changed after sorting!");108}109 110static struct kunit_case list_sort_cases[] = {111 KUNIT_CASE(list_sort_test),112 {}113};114 115static struct kunit_suite list_sort_suite = {116 .name = "list_sort",117 .test_cases = list_sort_cases,118};119 120kunit_test_suites(&list_sort_suite);121 122MODULE_DESCRIPTION("list_sort() KUnit test suite");123MODULE_LICENSE("GPL");124