* + lib-tests-add-kunit-tests-for-the-priority-sorted-list-plist.patch added to mm-nonmm-unstable branch
@ 2026-11-08 3:38 Andrew Morton
0 siblings, 0 replies; 2+ messages in thread
From: Andrew Morton @ 2026-11-08 3:38 UTC (permalink / raw)
To: mm-commits, visitorckw, tj, tglx, sakamo.ryota, pmladek, peterz,
pasha.tatashin, note351, nickolai, maarseveent, ljs, leitao,
kmehltretter, handyhandyman.adam, elver, ebiggers, dmantipov,
david, bp, andriy.shevchenko, 409411716, wuyuehong, akpm
The patch titled
Subject: lib/tests: add KUnit tests for the priority sorted list (plist)
has been added to the -mm mm-nonmm-unstable branch. Its filename is
lib-tests-add-kunit-tests-for-the-priority-sorted-list-plist.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/lib-tests-add-kunit-tests-for-the-priority-sorted-list-plist.patch
This patch will later appear in the mm-nonmm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via various
branches at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there most days
------------------------------------------------------
From: Yuehong Wu <wuyuehong@cmss.chinamobile.com>
Subject: lib/tests: add KUnit tests for the priority sorted list (plist)
Date: Sat, 07 Nov 2026 12:45:00 +0800
lib/plist.c has no KUnit coverage; its only test is the in-module
plist_test() under CONFIG_DEBUG_PLIST, which BUG_ON()s on the first
violation and does not report results in KTAP format. The
ordering-sensitive code paths have been changed three times since
mid-2024:
commit c8dab79f9eef ("lib/plist.c: avoid worst case scenario in
plist_add")
commit 95d4b3450ebe ("lib/plist.c: add shortcut for plist_requeue()")
commit 43c91b152243 ("lib/plist: fix plist_requeue() corrupting order
in the last bucket")
The first two are performance optimizations; the third one fixes a real
ordering bug. A deterministic case for that wrap-around now lives in the
CONFIG_DEBUG_PLIST self-test, which only runs when that debug option is
enabled by hand and stops at the first BUG_ON().
plist_kunit_requeue_last_bucket() covers the same shape here, and the
other cases pin down the ordering invariants the two optimizations rely
on. KUnit coverage makes such regressions visible wherever KUnit is
enabled, which CONFIG_DEBUG_PLIST is not.
Add lib/tests/plist_kunit.c, a KUnit suite that exercises plist_add(),
plist_del() and plist_requeue() and validates the invariants documented in
include/linux/plist.h after every operation:
- node_list stays sorted by ascending numeric priority (descending
priority order), and its prev links agree with its next links;
- exactly the first node of each bucket is linked on prio_list, the
ring's prev links agree with its next links, and the headless ring
visits the bucket heads in node_list order before wrapping back to
the first bucket (a single bucket degenerates to a self loop on the
first node).
The fixed cases cover bucket head handover on delete (first, middle and
last bucket), the plist_requeue() shortcut with and without a following
bucket, requeueing the head of the first and of the last bucket where the
ring wraps around, requeueing inside a single bucket, the INT_MIN/INT_MAX
extremes, and plist_first_entry()/plist_last_entry().
A deterministic pseudo-random add/del/requeue churn test mirrors the
in-module test, but draws priorities from a small range, so that
multi-node buckets actually occur with the 24 nodes it uses, and every
requeue in the loop moves a node (a requeue without a same-priority
successor is a no-op). The in-module test stays: it also carries the
plist_add() worst-case timing benchmark, and CONFIG_DEBUG_PLIST keeps
plist_check_head() in the fast path.
The suite is wired up as CONFIG_PLIST_KUNIT_TEST next to the other library
KUnit tests and is enabled by default with KUNIT_ALL_TESTS. lib/plist.c
is built into the kernel, so export plist_add(), plist_del() and
plist_requeue() for KUnit with EXPORT_SYMBOL_IF_KUNIT() and let the test
import EXPORTED_FOR_KUNIT_TESTING; that keeps the test tristate like the
other library KUnit tests.
The tests build both as a module and into the kernel. Built into the
kernel, with kunit.enable=1 kunit.filter_glob=plist*, all 18 tests pass
under QEMU/KVM. Reverting the last fix above makes three of them fail
(plist_kunit_requeue_basic, plist_kunit_requeue_last_bucket and
plist_kunit_random), all with the list coming out unsorted, so the suite
does catch the bug it was written for.
Link: https://lore.kernel.org/20261107-plist-kunit-v3-1-yuehongwu@cmss.chinamobile.com
Signed-off-by: Yuehong Wu <wuyuehong@cmss.chinamobile.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Breno Leitao <leitao@debian.org>
Cc: David Gow <david@davidgow.net>
Cc: Tejun Heo <tj@kernel.org>
Cc: Ryota Sakamoto <sakamo.ryota@gmail.com>
Cc: Karl Mehltretter <kmehltretter@gmail.com>
Cc: Marco Elver <elver@google.com>
Cc: Pasha Tatashin <pasha.tatashin@soleen.com>
Cc: Kir Chou <note351@hotmail.com>
Cc: Lorenzo Stoakes <ljs@kernel.org>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Kuan-Wei Chiu <visitorckw@gmail.com>
Cc: Petr Mladek <pmladek@suse.com>
Cc: Eric Biggers <ebiggers@kernel.org>
Cc: Guan-Chun Wu <409411716@gms.tku.edu.tw>
Cc: Andy Shevchenko <andriy.shevchenko@intel.com>
Cc: Dmitry Antipov <dmantipov@yandex.ru>
Cc: Thomas Maarseveen <maarseveent@gmail.com>
Cc: Nickolai Zeldovich <nickolai@csail.mit.edu>
Cc: Thomas Gleixner <tglx@kernel.org>
Cc: Adam Harshbarger <handyhandyman.adam@gmail.com>
---
lib/Kconfig.debug | 19 +
lib/plist.c | 4
lib/tests/Makefile | 1
lib/tests/plist_kunit.c | 719 ++++++++++++++++++++++++++++++++++++++
4 files changed, 743 insertions(+)
--- a/lib/Kconfig.debug~lib-tests-add-kunit-tests-for-the-priority-sorted-list-plist
+++ a/lib/Kconfig.debug
@@ -3065,6 +3065,25 @@ config MIN_HEAP_KUNIT_TEST
If unsure, say N
+config PLIST_KUNIT_TEST
+ tristate "KUnit test for priority sorted list (plist)" if !KUNIT_ALL_TESTS
+ depends on KUNIT
+ default KUNIT_ALL_TESTS
+ help
+ This builds the priority sorted list (plist) KUnit test suite.
+ It checks that plist_add(), plist_del() and plist_requeue()
+ maintain the ordering invariants of the two-level list, including
+ the priority bucket boundary cases.
+
+ KUnit tests run during boot and print their results in KTAP format.
+ Only useful for kernel developers running the KUnit test harness,
+ not for production builds.
+
+ 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 IS_SIGNED_TYPE_KUNIT_TEST
tristate "Test is_signed_type() macro" if !KUNIT_ALL_TESTS
depends on KUNIT
--- a/lib/plist.c~lib-tests-add-kunit-tests-for-the-priority-sorted-list-plist
+++ a/lib/plist.c
@@ -22,6 +22,7 @@
* information.
*/
+#include <kunit/visibility.h>
#include <linux/bug.h>
#include <linux/plist.h>
@@ -112,6 +113,7 @@ ins_node:
plist_check_head(head);
}
+EXPORT_SYMBOL_IF_KUNIT(plist_add);
/**
* plist_del - Remove a @node from plist.
@@ -141,6 +143,7 @@ void plist_del(struct plist_node *node,
plist_check_head(head);
}
+EXPORT_SYMBOL_IF_KUNIT(plist_del);
/**
* plist_requeue - Requeue @node at end of same-prio entries.
@@ -200,6 +203,7 @@ queue:
plist_check_head(head);
}
+EXPORT_SYMBOL_IF_KUNIT(plist_requeue);
#ifdef CONFIG_DEBUG_PLIST
#include <linux/sched.h>
--- a/lib/tests/Makefile~lib-tests-add-kunit-tests-for-the-priority-sorted-list-plist
+++ a/lib/tests/Makefile
@@ -43,6 +43,7 @@ obj-$(CONFIG_MEMCPY_KUNIT_TEST) += memcp
obj-$(CONFIG_MIN_HEAP_KUNIT_TEST) += min_heap_kunit.o
CFLAGS_overflow_kunit.o = $(call cc-disable-warning, tautological-constant-out-of-range-compare)
obj-$(CONFIG_OVERFLOW_KUNIT_TEST) += overflow_kunit.o
+obj-$(CONFIG_PLIST_KUNIT_TEST) += plist_kunit.o
obj-$(CONFIG_PRANDOM_KUNIT_TEST) += random32_kunit.o
obj-$(CONFIG_PRINTF_KUNIT_TEST) += printf_kunit.o
obj-$(CONFIG_RANDSTRUCT_KUNIT_TEST) += randstruct_kunit.o
diff --git a/lib/tests/plist_kunit.c a/lib/tests/plist_kunit.c
new file mode 100644
--- /dev/null
+++ a/lib/tests/plist_kunit.c
@@ -0,0 +1,719 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * KUnit tests for the priority sorted list (plist) structures.
+ *
+ * Checks that plist_add(), plist_del() and plist_requeue() maintain the
+ * ordering invariants documented in include/linux/plist.h, with extra
+ * attention to the priority bucket boundary cases of the prio_list ring.
+ */
+
+#include <kunit/test.h>
+
+#include <linux/limits.h>
+#include <linux/list.h>
+#include <linux/module.h>
+#include <linux/plist.h>
+
+/*
+ * Upper bound for the node_list walk, so a corrupted list fails instead
+ * of hanging the boot.
+ */
+#define PLIST_KUNIT_MAX_NODES 4096
+
+struct plist_kunit_item {
+ int id;
+ struct plist_node node;
+};
+
+/*
+ * Walk both the node_list and the prio_list ring and check the invariants
+ * of a plist:
+ *
+ * - node_list is sorted by ascending numeric priority (i.e. descending
+ * priority order), and its prev links agree with its next links;
+ * - exactly the first node of every priority bucket is linked on the
+ * prio_list ring, the ring's prev links agree with its next links, and
+ * the headless ring visits the bucket heads in node_list order before
+ * wrapping back to the first bucket;
+ * - when the list holds a single bucket the ring degenerates to a self
+ * loop on the first node, which list_empty() reports as empty.
+ *
+ * Same-priority FIFO order is not checked here, as it needs the expected
+ * sequence; the individual test cases assert it explicitly.
+ *
+ * Returns the number of nodes on the list.
+ */
+static int plist_kunit_verify(struct kunit *test, struct plist_head *head)
+{
+ struct plist_node *pos, *prev = NULL, *first, *ring, *next;
+ int nr_nodes = 0, nr_heads = 0, nr_ring = 0;
+
+ if (plist_head_empty(head)) {
+ /* Same predicate on the other half of the head node. */
+ KUNIT_ASSERT_PTR_EQ(test, head->node_list.prev,
+ &head->node_list);
+ return 0;
+ }
+
+ first = plist_first(head);
+
+ plist_for_each(pos, head) {
+ if (++nr_nodes > PLIST_KUNIT_MAX_NODES) {
+ KUNIT_FAIL(test, "node_list does not terminate");
+ return nr_nodes;
+ }
+
+ if (prev)
+ KUNIT_ASSERT_PTR_EQ(test, pos->node_list.prev,
+ &prev->node_list);
+ else
+ KUNIT_ASSERT_PTR_EQ(test, pos->node_list.prev,
+ &head->node_list);
+
+ if (prev) {
+ KUNIT_ASSERT_LE(test, prev->prio, pos->prio);
+ /*
+ * A node sharing its predecessor's priority is a
+ * bucket follower and must not be linked on the
+ * prio_list ring; a node starting a new bucket must.
+ */
+ if (prev->prio == pos->prio) {
+ KUNIT_ASSERT_TRUE(test,
+ list_empty(&pos->prio_list));
+ } else {
+ KUNIT_ASSERT_FALSE(test,
+ list_empty(&pos->prio_list));
+ nr_heads++;
+ }
+ } else {
+ nr_heads++;
+ }
+ prev = pos;
+ }
+
+ KUNIT_ASSERT_PTR_EQ(test, prev, plist_last(head));
+
+ if (nr_heads == 1) {
+ /* Single bucket: the ring is a self loop on the first node. */
+ KUNIT_ASSERT_TRUE(test, list_empty(&first->prio_list));
+ KUNIT_ASSERT_PTR_EQ(test, first->prio_list.prev,
+ &first->prio_list);
+ return nr_nodes;
+ }
+
+ KUNIT_ASSERT_FALSE(test, list_empty(&first->prio_list));
+
+ ring = first;
+ do {
+ if (++nr_ring > nr_heads) {
+ KUNIT_FAIL(test, "prio_list ring does not close");
+ return nr_nodes;
+ }
+ KUNIT_ASSERT_FALSE(test, list_empty(&ring->prio_list));
+ next = list_entry(ring->prio_list.next, struct plist_node,
+ prio_list);
+ KUNIT_ASSERT_PTR_EQ(test, next->prio_list.prev,
+ &ring->prio_list);
+ if (next != first)
+ KUNIT_ASSERT_LT(test, ring->prio, next->prio);
+ ring = next;
+ } while (ring != first);
+
+ KUNIT_ASSERT_EQ(test, nr_ring, nr_heads);
+
+ return nr_nodes;
+}
+
+static void plist_kunit_add_empty(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a;
+
+ plist_node_init(&a, 10);
+
+ KUNIT_EXPECT_TRUE(test, plist_head_empty(&head));
+ KUNIT_EXPECT_TRUE(test, plist_node_empty(&a));
+
+ plist_add(&a, &head);
+
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 1);
+ KUNIT_EXPECT_FALSE(test, plist_head_empty(&head));
+ KUNIT_EXPECT_FALSE(test, plist_node_empty(&a));
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &a);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &a);
+}
+
+static void plist_kunit_add_order(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node n[4];
+ int i;
+
+ plist_node_init(&n[0], 30);
+ plist_node_init(&n[1], 10);
+ plist_node_init(&n[2], 40);
+ plist_node_init(&n[3], 20);
+
+ /* Insert the nodes out of order. */
+ for (i = 0; i < ARRAY_SIZE(n); i++)
+ plist_add(&n[i], &head);
+
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 4);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &n[1]);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&n[1]), &n[3]);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&n[3]), &n[0]);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&n[0]), &n[2]);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &n[2]);
+}
+
+static void plist_kunit_add_duplicates(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c, d, e;
+
+ plist_node_init(&a, 5);
+ plist_node_init(&b, 5);
+ plist_node_init(&c, 9);
+ plist_node_init(&d, 5);
+ plist_node_init(&e, 7);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+ plist_add(&d, &head);
+ plist_add(&e, &head);
+
+ /* node_list: a(5), b(5), d(5), e(7), c(9) -- FIFO in a bucket. */
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 5);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &a);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &b);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&b), &d);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&d), &e);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &c);
+
+ /* Only the first node of each bucket leads the prio_list ring. */
+ KUNIT_EXPECT_FALSE(test, list_empty(&a.prio_list));
+ KUNIT_EXPECT_TRUE(test, list_empty(&b.prio_list));
+ KUNIT_EXPECT_TRUE(test, list_empty(&d.prio_list));
+ KUNIT_EXPECT_FALSE(test, list_empty(&e.prio_list));
+ KUNIT_EXPECT_FALSE(test, list_empty(&c.prio_list));
+
+ KUNIT_EXPECT_PTR_EQ(test, a.prio_list.next, &e.prio_list);
+ KUNIT_EXPECT_PTR_EQ(test, e.prio_list.next, &c.prio_list);
+ KUNIT_EXPECT_PTR_EQ(test, c.prio_list.next, &a.prio_list);
+}
+
+/*
+ * Adding ascending priorities makes every node the new last bucket, the
+ * case the reverse walk in plist_add() is meant to short-circuit.
+ */
+static void plist_kunit_add_ascending(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node n[16];
+ int i;
+
+ for (i = 0; i < ARRAY_SIZE(n); i++) {
+ plist_node_init(&n[i], i);
+ plist_add(&n[i], &head);
+ KUNIT_ASSERT_EQ(test, plist_kunit_verify(test, &head), i + 1);
+ }
+
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &n[0]);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &n[15]);
+}
+
+/* Adding descending priorities makes every node the new first bucket. */
+static void plist_kunit_add_descending(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node n[16];
+ int i;
+
+ for (i = 0; i < ARRAY_SIZE(n); i++) {
+ plist_node_init(&n[i], ARRAY_SIZE(n) - i);
+ plist_add(&n[i], &head);
+ KUNIT_ASSERT_EQ(test, plist_kunit_verify(test, &head), i + 1);
+ }
+
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &n[15]);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &n[0]);
+}
+
+static void plist_kunit_add_extremes(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c;
+
+ plist_node_init(&a, 0);
+ plist_node_init(&b, INT_MAX);
+ plist_node_init(&c, INT_MIN);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ /* INT_MIN is the highest priority, INT_MAX the lowest. */
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &c);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&c), &a);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &b);
+}
+
+static void plist_kunit_del_bucket_head(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c;
+
+ plist_node_init(&a, 1);
+ plist_node_init(&b, 1);
+ plist_node_init(&c, 2);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ /* Removing the bucket head hands prio_list over to the successor. */
+ plist_del(&a, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 2);
+ KUNIT_EXPECT_TRUE(test, plist_node_empty(&a));
+ KUNIT_EXPECT_FALSE(test, list_empty(&b.prio_list));
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &b);
+
+ /* Removing the last node of the last bucket empties the list. */
+ plist_del(&c, &head);
+ plist_del(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 0);
+ KUNIT_EXPECT_TRUE(test, plist_head_empty(&head));
+
+ /* A removed node can be added back. */
+ plist_add(&a, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 1);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &a);
+}
+
+static void plist_kunit_del_bucket_follower(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c;
+
+ plist_node_init(&a, 1);
+ plist_node_init(&b, 1);
+ plist_node_init(&c, 2);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ /* Removing a bucket follower must not disturb the prio_list ring. */
+ plist_del(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 2);
+ KUNIT_EXPECT_FALSE(test, list_empty(&a.prio_list));
+ KUNIT_EXPECT_FALSE(test, list_empty(&c.prio_list));
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &c);
+ KUNIT_EXPECT_PTR_EQ(test, a.prio_list.next, &c.prio_list);
+ KUNIT_EXPECT_PTR_EQ(test, c.prio_list.next, &a.prio_list);
+}
+
+static void plist_kunit_del_middle_bucket(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c;
+
+ plist_node_init(&a, 1);
+ plist_node_init(&b, 2);
+ plist_node_init(&c, 3);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ /* Removing the only node of a middle bucket splices the ring. */
+ plist_del(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 2);
+ KUNIT_EXPECT_TRUE(test, plist_node_empty(&b));
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &c);
+ KUNIT_EXPECT_PTR_EQ(test, a.prio_list.next, &c.prio_list);
+ KUNIT_EXPECT_PTR_EQ(test, c.prio_list.next, &a.prio_list);
+}
+
+/*
+ * Deleting the head of the last priority bucket: its follower takes over
+ * the prio_list entry, and the ring of bucket heads has to wrap round to
+ * the first bucket.
+ */
+static void plist_kunit_del_last_bucket_head(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c;
+
+ plist_node_init(&a, 1);
+ plist_node_init(&b, 2);
+ plist_node_init(&c, 2);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ plist_del(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 2);
+ KUNIT_EXPECT_TRUE(test, plist_node_empty(&b));
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &c);
+ KUNIT_EXPECT_FALSE(test, list_empty(&c.prio_list));
+ KUNIT_EXPECT_PTR_EQ(test, a.prio_list.next, &c.prio_list);
+ KUNIT_EXPECT_PTR_EQ(test, c.prio_list.next, &a.prio_list);
+}
+
+static void plist_kunit_requeue_basic(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c;
+
+ plist_node_init(&a, 1);
+ plist_node_init(&b, 2);
+ plist_node_init(&c, 2);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ /* A node whose successor has a different priority is left alone. */
+ plist_requeue(&a, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &a);
+
+ /* Requeueing moves a node after its same-priority peers. */
+ plist_requeue(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &c);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&c), &b);
+
+ /* Requeueing the last node of the list is a no-op. */
+ plist_requeue(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &b);
+
+ /* ...and the peers rotate back. */
+ plist_requeue(&c, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &b);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&b), &c);
+}
+
+/*
+ * The plist_requeue() shortcut: after plist_del() the node's same-priority
+ * successor took over the prio_list entry, so the node can be inserted
+ * directly before the next bucket instead of walking the node_list.
+ */
+static void plist_kunit_requeue_shortcut(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c, d;
+
+ plist_node_init(&a, 1);
+ plist_node_init(&b, 2);
+ plist_node_init(&c, 2);
+ plist_node_init(&d, 3);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+ plist_add(&d, &head);
+
+ plist_requeue(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 4);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &c);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&c), &b);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&b), &d);
+
+ /* The tail of its bucket has a different priority: no-op. */
+ plist_requeue(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 4);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&c), &b);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&b), &d);
+}
+
+/*
+ * Regression test for commit 43c91b152243 ("lib/plist: fix
+ * plist_requeue() corrupting order in the last bucket"): when the
+ * requeued node heads the last priority bucket, the prio_list ring of the
+ * bucket heads wraps round to the first bucket, and the node must end up
+ * at the very end of the list instead of jumping to its front.
+ */
+static void plist_kunit_requeue_last_bucket(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c, d, e;
+
+ plist_node_init(&a, 0);
+ plist_node_init(&b, 1);
+ plist_node_init(&c, 1);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ plist_requeue(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &a);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &c);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &b);
+
+ /* The same wrap with an intermediate bucket before the last one. */
+ plist_node_init(&d, 2);
+ plist_node_init(&e, 2);
+ plist_add(&d, &head);
+ plist_add(&e, &head);
+
+ plist_requeue(&d, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 5);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&b), &e);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &d);
+}
+
+/*
+ * Requeueing the head of the first priority bucket: its follower takes
+ * over the bucket, so the node moves behind it and the new first bucket
+ * has to be linked in the prio_list ring instead.
+ */
+static void plist_kunit_requeue_first_bucket_head(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c;
+
+ plist_node_init(&a, 1);
+ plist_node_init(&b, 1);
+ plist_node_init(&c, 2);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ plist_requeue(&a, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &b);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&b), &a);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &c);
+ KUNIT_EXPECT_TRUE(test, list_empty(&a.prio_list));
+ KUNIT_EXPECT_FALSE(test, list_empty(&b.prio_list));
+ KUNIT_EXPECT_PTR_EQ(test, b.prio_list.next, &c.prio_list);
+ KUNIT_EXPECT_PTR_EQ(test, c.prio_list.next, &b.prio_list);
+}
+
+static void plist_kunit_first_last_entry(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_kunit_item items[3];
+ struct plist_kunit_item *first, *last;
+ int i;
+
+ for (i = 0; i < ARRAY_SIZE(items); i++) {
+ items[i].id = i;
+ plist_node_init(&items[i].node, i + 1);
+ plist_add(&items[i].node, &head);
+ }
+
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+
+ first = plist_first_entry(&head, struct plist_kunit_item, node);
+ last = plist_last_entry(&head, struct plist_kunit_item, node);
+ KUNIT_EXPECT_EQ(test, first->id, 0);
+ KUNIT_EXPECT_EQ(test, last->id, 2);
+
+ KUNIT_EXPECT_EQ(test, plist_next(&items[0].node)->prio, 2);
+ KUNIT_EXPECT_EQ(test, plist_prev(&items[2].node)->prio, 2);
+}
+
+/*
+ * Deleting and requeueing the priority extremes, including handing the
+ * prio_list ring over when the INT_MIN bucket head goes away.
+ */
+static void plist_kunit_extremes_ops(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c;
+
+ plist_node_init(&a, 0);
+ plist_node_init(&b, INT_MAX);
+ plist_node_init(&c, INT_MIN);
+
+ plist_add(&c, &head);
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+
+ /* Deleting the INT_MIN head hands the ring over to the next bucket. */
+ plist_del(&c, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 2);
+ KUNIT_EXPECT_TRUE(test, plist_node_empty(&c));
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &a);
+
+ /* Requeueing the INT_MAX tail node is a no-op. */
+ plist_requeue(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 2);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &b);
+
+ /* Deleting the last bucket leaves a single-bucket list. */
+ plist_del(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 1);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &a);
+ KUNIT_EXPECT_TRUE(test, list_empty(&a.prio_list));
+}
+
+/*
+ * Deterministic pseudo-random add/del/requeue churn, mirroring the
+ * in-module test under CONFIG_DEBUG_PLIST but checking the invariants
+ * after every operation with KUnit assertions instead of BUG_ON().
+ *
+ * Priorities are drawn from a small range so that the list actually
+ * contains multi-node priority buckets, and the requeue step picks a node
+ * that has a same-priority successor -- only such a node moves, so every
+ * requeue in the loop is a real move and its result is checked.
+ */
+static void plist_kunit_random(struct kunit *test)
+{
+ struct plist_node nodes[24];
+ PLIST_HEAD(head);
+ unsigned int r = 12345;
+ int i, loop, nr_expect = 0, nr_requeued = 0;
+
+ for (i = 0; i < ARRAY_SIZE(nodes); i++)
+ plist_node_init(&nodes[i], 0);
+
+ for (loop = 0; loop < 1000; loop++) {
+ r = r * 193939u % 47629u;
+ i = r % ARRAY_SIZE(nodes);
+ if (plist_node_empty(&nodes[i])) {
+ r = r * 193939u % 47629u;
+ plist_node_init(&nodes[i], r % 8);
+ plist_add(&nodes[i], &head);
+ nr_expect++;
+ } else {
+ plist_del(&nodes[i], &head);
+ nr_expect--;
+ }
+
+ KUNIT_ASSERT_EQ(test, plist_kunit_verify(test, &head),
+ nr_expect);
+
+ for (i = 0; i < ARRAY_SIZE(nodes); i++) {
+ struct plist_node *next;
+
+ if (plist_node_empty(&nodes[i]) ||
+ &nodes[i] == plist_last(&head))
+ continue;
+ next = plist_next(&nodes[i]);
+ if (next->prio != nodes[i].prio)
+ continue;
+
+ plist_requeue(&nodes[i], &head);
+ nr_requeued++;
+
+ KUNIT_ASSERT_EQ(test,
+ plist_kunit_verify(test, &head),
+ nr_expect);
+ /* A requeued node is now the tail of its bucket. */
+ if (&nodes[i] != plist_last(&head))
+ KUNIT_EXPECT_NE(test, nodes[i].prio,
+ plist_next(&nodes[i])->prio);
+ break;
+ }
+ }
+
+ /* The requeue part of the churn must actually have run. */
+ KUNIT_EXPECT_GT(test, nr_requeued, 0);
+
+ for (i = 0; i < ARRAY_SIZE(nodes); i++) {
+ if (plist_node_empty(&nodes[i]))
+ continue;
+ plist_del(&nodes[i], &head);
+ nr_expect--;
+ KUNIT_ASSERT_EQ(test, plist_kunit_verify(test, &head),
+ nr_expect);
+ }
+
+ KUNIT_EXPECT_TRUE(test, plist_head_empty(&head));
+}
+
+/*
+ * Requeueing inside a single priority bucket exercises the degenerate
+ * prio_list ring (a self loop on the first node), and requeueing a bucket
+ * follower walks to the end of its bucket but not past the next one.
+ */
+static void plist_kunit_requeue_bucket_edges(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c, d, e;
+
+ plist_node_init(&a, 1);
+ plist_node_init(&b, 1);
+ plist_node_init(&c, 1);
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ /* Single bucket: the ring is a self loop on the first node. */
+ plist_requeue(&a, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &b);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&b), &c);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &a);
+ /*
+ * b heads the bucket now, but a single bucket never links onto
+ * the ring: after the handover in plist_del() the entry is a self
+ * loop, which list_empty() reports as empty.
+ */
+ KUNIT_EXPECT_TRUE(test, list_empty(&b.prio_list));
+
+ plist_requeue(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &c);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &b);
+
+ /* A follower requeue walks to the end of its bucket, not past it. */
+ plist_node_init(&d, 1);
+ plist_node_init(&e, 2);
+ plist_add(&d, &head);
+ plist_add(&e, &head);
+
+ plist_requeue(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 5);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&c), &a);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &d);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&d), &b);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&b), &e);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &e);
+}
+
+static struct kunit_case plist_kunit_test_cases[] = {
+ KUNIT_CASE(plist_kunit_add_empty),
+ KUNIT_CASE(plist_kunit_add_order),
+ KUNIT_CASE(plist_kunit_add_duplicates),
+ KUNIT_CASE(plist_kunit_add_ascending),
+ KUNIT_CASE(plist_kunit_add_descending),
+ KUNIT_CASE(plist_kunit_add_extremes),
+ KUNIT_CASE(plist_kunit_del_bucket_head),
+ KUNIT_CASE(plist_kunit_del_bucket_follower),
+ KUNIT_CASE(plist_kunit_del_middle_bucket),
+ KUNIT_CASE(plist_kunit_del_last_bucket_head),
+ KUNIT_CASE(plist_kunit_requeue_basic),
+ KUNIT_CASE(plist_kunit_requeue_shortcut),
+ KUNIT_CASE(plist_kunit_requeue_last_bucket),
+ KUNIT_CASE(plist_kunit_requeue_first_bucket_head),
+ KUNIT_CASE(plist_kunit_requeue_bucket_edges),
+ KUNIT_CASE(plist_kunit_first_last_entry),
+ KUNIT_CASE(plist_kunit_extremes_ops),
+ KUNIT_CASE(plist_kunit_random),
+ {}
+};
+
+static struct kunit_suite plist_kunit_test_suite = {
+ .name = "plist",
+ .test_cases = plist_kunit_test_cases,
+};
+
+kunit_test_suite(plist_kunit_test_suite);
+
+MODULE_IMPORT_NS("EXPORTED_FOR_KUNIT_TESTING");
+
+MODULE_DESCRIPTION("KUnit tests for the priority sorted list (plist)");
+MODULE_LICENSE("GPL");
_
Patches currently in -mm which might be from wuyuehong@cmss.chinamobile.com are
lib-tests-add-kunit-tests-for-the-priority-sorted-list-plist.patch
^ permalink raw reply [flat|nested] 2+ messages in thread* + lib-tests-add-kunit-tests-for-the-priority-sorted-list-plist.patch added to mm-nonmm-unstable branch
@ 2026-11-07 7:07 Andrew Morton
0 siblings, 0 replies; 2+ messages in thread
From: Andrew Morton @ 2026-11-07 7:07 UTC (permalink / raw)
To: mm-commits, visitorckw, tj, tglx, sakamo.ryota, pmladek, peterz,
pasha.tatashin, note351, nickolai, maarseveent, lkp, ljs, leitao,
kmehltretter, handyhandyman.adam, geert, elver, ebiggers,
dmantipov, david, bp, andriy.shevchenko, 409411716, wuyuehong,
akpm
The patch titled
Subject: lib/tests: add KUnit tests for the priority sorted list (plist)
has been added to the -mm mm-nonmm-unstable branch. Its filename is
lib-tests-add-kunit-tests-for-the-priority-sorted-list-plist.patch
This patch will shortly appear at
https://git.kernel.org/pub/scm/linux/kernel/git/akpm/25-new.git/tree/patches/lib-tests-add-kunit-tests-for-the-priority-sorted-list-plist.patch
This patch will later appear in the mm-nonmm-unstable branch at
git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
Before you just go and hit "reply", please:
a) Consider who else should be cc'ed
b) Prefer to cc a suitable mailing list as well
c) Ideally: find the original patch on the mailing list and do a
reply-to-all to that, adding suitable additional cc's
*** Remember to use Documentation/process/submit-checklist.rst when testing your code ***
The -mm tree is included into linux-next via various
branches at git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm
and is updated there most days
------------------------------------------------------
From: Yuehong Wu <wuyuehong@cmss.chinamobile.com>
Subject: lib/tests: add KUnit tests for the priority sorted list (plist)
Date: Sat, 07 Nov 2026 12:45:00 +0800
lib/plist.c has no KUnit coverage; its only test is the in-module
plist_test() under CONFIG_DEBUG_PLIST, which BUG_ON()s on the first
violation and does not report results in KTAP format. The
ordering-sensitive code paths have been changed three times since
mid-2024:
commit c8dab79f9eef ("lib/plist.c: avoid worst case scenario in
plist_add")
commit 95d4b3450ebe ("lib/plist.c: add shortcut for plist_requeue()")
commit 43c91b152243 ("lib/plist: fix plist_requeue() corrupting order
in the last bucket")
The first two are performance optimizations; the third one fixes a real
ordering bug. A deterministic case for that wrap-around now lives in the
CONFIG_DEBUG_PLIST self-test, which only runs when that debug option is
enabled by hand and stops at the first BUG_ON().
plist_kunit_requeue_last_bucket() covers the same shape here, and the
other cases pin down the ordering invariants the two optimizations rely
on. KUnit coverage makes such regressions visible wherever KUnit is
enabled, which CONFIG_DEBUG_PLIST is not.
Add lib/tests/plist_kunit.c, a KUnit suite that exercises plist_add(),
plist_del() and plist_requeue() and validates the invariants documented in
include/linux/plist.h after every operation:
- node_list stays sorted by ascending numeric priority (descending
priority order), and its prev links agree with its next links;
- exactly the first node of each bucket is linked on prio_list, the
ring's prev links agree with its next links, and the headless ring
visits the bucket heads in node_list order before wrapping back to
the first bucket (a single bucket degenerates to a self loop on the
first node).
The fixed cases cover bucket head handover on delete (first, middle and
last bucket), the plist_requeue() shortcut with and without a following
bucket, requeueing the head of the first and of the last bucket where the
ring wraps around, requeueing inside a single bucket, the INT_MIN/INT_MAX
extremes, and plist_first_entry()/plist_last_entry().
A deterministic pseudo-random add/del/requeue churn test mirrors the
in-module test, but draws priorities from a small range, so that
multi-node buckets actually occur with the 24 nodes it uses, and every
requeue in the loop moves a node (a requeue without a same-priority
successor is a no-op). The in-module test stays: it also carries the
plist_add() worst-case timing benchmark, and CONFIG_DEBUG_PLIST keeps
plist_check_head() in the fast path.
The suite is wired up as CONFIG_PLIST_KUNIT_TEST next to the other library
KUnit tests and is enabled by default with KUNIT_ALL_TESTS. lib/plist.c
is built into the kernel, so export plist_add(), plist_del() and
plist_requeue() for KUnit with EXPORT_SYMBOL_IF_KUNIT() and let the test
import EXPORTED_FOR_KUNIT_TESTING; that keeps the test tristate like the
other library KUnit tests.
The tests build both as a module and into the kernel. Built into the
kernel, with kunit.enable=1 kunit.filter_glob=plist*, all 18 tests pass
under QEMU/KVM. Reverting the last fix above makes three of them fail
(plist_kunit_requeue_basic, plist_kunit_requeue_last_bucket and
plist_kunit_random), all with the list coming out unsorted, so the suite
does catch the bug it was written for.
Link: https://lore.kernel.org/20261107-plist-kunit-v3-1-yuehongwu@cmss.chinamobile.com
Signed-off-by: Yuehong Wu <wuyuehong@cmss.chinamobile.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Reported-by: kernel test robot <lkp@intel.com>
Closes: https://lore.kernel.org/oe-kbuild-all/202611052109.GqbzRkv1-lkp@intel.com/
Suggested-by: Geert Uytterhoeven <geert@linux-m68k.org>
Cc: Peter Zijlstra <peterz@infradead.org>
Cc: Breno Leitao <leitao@debian.org>
Cc: David Gow <david@davidgow.net>
Cc: Tejun Heo <tj@kernel.org>
Cc: Ryota Sakamoto <sakamo.ryota@gmail.com>
Cc: Karl Mehltretter <kmehltretter@gmail.com>
Cc: Marco Elver <elver@google.com>
Cc: Pasha Tatashin <pasha.tatashin@soleen.com>
Cc: Kir Chou <note351@hotmail.com>
Cc: Lorenzo Stoakes <ljs@kernel.org>
Cc: Borislav Petkov <bp@alien8.de>
Cc: Kuan-Wei Chiu <visitorckw@gmail.com>
Cc: Petr Mladek <pmladek@suse.com>
Cc: Eric Biggers <ebiggers@kernel.org>
Cc: Guan-Chun Wu <409411716@gms.tku.edu.tw>
Cc: Andy Shevchenko <andriy.shevchenko@intel.com>
Cc: Dmitry Antipov <dmantipov@yandex.ru>
Cc: Thomas Maarseveen <maarseveent@gmail.com>
Cc: Nickolai Zeldovich <nickolai@csail.mit.edu>
Cc: Thomas Gleixner <tglx@kernel.org>
Cc: Adam Harshbarger <handyhandyman.adam@gmail.com>
---
lib/Kconfig.debug | 19 +
lib/plist.c | 4
lib/tests/Makefile | 1
lib/tests/plist_kunit.c | 719 ++++++++++++++++++++++++++++++++++++++
4 files changed, 743 insertions(+)
--- a/lib/Kconfig.debug~lib-tests-add-kunit-tests-for-the-priority-sorted-list-plist
+++ a/lib/Kconfig.debug
@@ -3078,6 +3078,25 @@ config MIN_HEAP_KUNIT_TEST
If unsure, say N
+config PLIST_KUNIT_TEST
+ tristate "KUnit test for priority sorted list (plist)" if !KUNIT_ALL_TESTS
+ depends on KUNIT
+ default KUNIT_ALL_TESTS
+ help
+ This builds the priority sorted list (plist) KUnit test suite.
+ It checks that plist_add(), plist_del() and plist_requeue()
+ maintain the ordering invariants of the two-level list, including
+ the priority bucket boundary cases.
+
+ KUnit tests run during boot and print their results in KTAP format.
+ Only useful for kernel developers running the KUnit test harness,
+ not for production builds.
+
+ 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 IS_SIGNED_TYPE_KUNIT_TEST
tristate "Test is_signed_type() macro" if !KUNIT_ALL_TESTS
depends on KUNIT
--- a/lib/plist.c~lib-tests-add-kunit-tests-for-the-priority-sorted-list-plist
+++ a/lib/plist.c
@@ -22,6 +22,7 @@
* information.
*/
+#include <kunit/visibility.h>
#include <linux/bug.h>
#include <linux/plist.h>
@@ -112,6 +113,7 @@ ins_node:
plist_check_head(head);
}
+EXPORT_SYMBOL_IF_KUNIT(plist_add);
/**
* plist_del - Remove a @node from plist.
@@ -141,6 +143,7 @@ void plist_del(struct plist_node *node,
plist_check_head(head);
}
+EXPORT_SYMBOL_IF_KUNIT(plist_del);
/**
* plist_requeue - Requeue @node at end of same-prio entries.
@@ -200,6 +203,7 @@ queue:
plist_check_head(head);
}
+EXPORT_SYMBOL_IF_KUNIT(plist_requeue);
#ifdef CONFIG_DEBUG_PLIST
#include <linux/sched.h>
--- a/lib/tests/Makefile~lib-tests-add-kunit-tests-for-the-priority-sorted-list-plist
+++ a/lib/tests/Makefile
@@ -43,6 +43,7 @@ obj-$(CONFIG_MEMCPY_KUNIT_TEST) += memcp
obj-$(CONFIG_MIN_HEAP_KUNIT_TEST) += min_heap_kunit.o
CFLAGS_overflow_kunit.o = $(call cc-disable-warning, tautological-constant-out-of-range-compare)
obj-$(CONFIG_OVERFLOW_KUNIT_TEST) += overflow_kunit.o
+obj-$(CONFIG_PLIST_KUNIT_TEST) += plist_kunit.o
obj-$(CONFIG_PRANDOM_KUNIT_TEST) += random32_kunit.o
obj-$(CONFIG_PRINTF_KUNIT_TEST) += printf_kunit.o
obj-$(CONFIG_RANDSTRUCT_KUNIT_TEST) += randstruct_kunit.o
diff --git a/lib/tests/plist_kunit.c a/lib/tests/plist_kunit.c
new file mode 100644
--- /dev/null
+++ a/lib/tests/plist_kunit.c
@@ -0,0 +1,719 @@
+// SPDX-License-Identifier: GPL-2.0-only
+/*
+ * KUnit tests for the priority sorted list (plist) structures.
+ *
+ * Checks that plist_add(), plist_del() and plist_requeue() maintain the
+ * ordering invariants documented in include/linux/plist.h, with extra
+ * attention to the priority bucket boundary cases of the prio_list ring.
+ */
+
+#include <kunit/test.h>
+
+#include <linux/limits.h>
+#include <linux/list.h>
+#include <linux/module.h>
+#include <linux/plist.h>
+
+/*
+ * Upper bound for the node_list walk, so a corrupted list fails instead
+ * of hanging the boot.
+ */
+#define PLIST_KUNIT_MAX_NODES 4096
+
+struct plist_kunit_item {
+ int id;
+ struct plist_node node;
+};
+
+/*
+ * Walk both the node_list and the prio_list ring and check the invariants
+ * of a plist:
+ *
+ * - node_list is sorted by ascending numeric priority (i.e. descending
+ * priority order), and its prev links agree with its next links;
+ * - exactly the first node of every priority bucket is linked on the
+ * prio_list ring, the ring's prev links agree with its next links, and
+ * the headless ring visits the bucket heads in node_list order before
+ * wrapping back to the first bucket;
+ * - when the list holds a single bucket the ring degenerates to a self
+ * loop on the first node, which list_empty() reports as empty.
+ *
+ * Same-priority FIFO order is not checked here, as it needs the expected
+ * sequence; the individual test cases assert it explicitly.
+ *
+ * Returns the number of nodes on the list.
+ */
+static int plist_kunit_verify(struct kunit *test, struct plist_head *head)
+{
+ struct plist_node *pos, *prev = NULL, *first, *ring, *next;
+ int nr_nodes = 0, nr_heads = 0, nr_ring = 0;
+
+ if (plist_head_empty(head)) {
+ /* Same predicate on the other half of the head node. */
+ KUNIT_ASSERT_PTR_EQ(test, head->node_list.prev,
+ &head->node_list);
+ return 0;
+ }
+
+ first = plist_first(head);
+
+ plist_for_each(pos, head) {
+ if (++nr_nodes > PLIST_KUNIT_MAX_NODES) {
+ KUNIT_FAIL(test, "node_list does not terminate");
+ return nr_nodes;
+ }
+
+ if (prev)
+ KUNIT_ASSERT_PTR_EQ(test, pos->node_list.prev,
+ &prev->node_list);
+ else
+ KUNIT_ASSERT_PTR_EQ(test, pos->node_list.prev,
+ &head->node_list);
+
+ if (prev) {
+ KUNIT_ASSERT_LE(test, prev->prio, pos->prio);
+ /*
+ * A node sharing its predecessor's priority is a
+ * bucket follower and must not be linked on the
+ * prio_list ring; a node starting a new bucket must.
+ */
+ if (prev->prio == pos->prio) {
+ KUNIT_ASSERT_TRUE(test,
+ list_empty(&pos->prio_list));
+ } else {
+ KUNIT_ASSERT_FALSE(test,
+ list_empty(&pos->prio_list));
+ nr_heads++;
+ }
+ } else {
+ nr_heads++;
+ }
+ prev = pos;
+ }
+
+ KUNIT_ASSERT_PTR_EQ(test, prev, plist_last(head));
+
+ if (nr_heads == 1) {
+ /* Single bucket: the ring is a self loop on the first node. */
+ KUNIT_ASSERT_TRUE(test, list_empty(&first->prio_list));
+ KUNIT_ASSERT_PTR_EQ(test, first->prio_list.prev,
+ &first->prio_list);
+ return nr_nodes;
+ }
+
+ KUNIT_ASSERT_FALSE(test, list_empty(&first->prio_list));
+
+ ring = first;
+ do {
+ if (++nr_ring > nr_heads) {
+ KUNIT_FAIL(test, "prio_list ring does not close");
+ return nr_nodes;
+ }
+ KUNIT_ASSERT_FALSE(test, list_empty(&ring->prio_list));
+ next = list_entry(ring->prio_list.next, struct plist_node,
+ prio_list);
+ KUNIT_ASSERT_PTR_EQ(test, next->prio_list.prev,
+ &ring->prio_list);
+ if (next != first)
+ KUNIT_ASSERT_LT(test, ring->prio, next->prio);
+ ring = next;
+ } while (ring != first);
+
+ KUNIT_ASSERT_EQ(test, nr_ring, nr_heads);
+
+ return nr_nodes;
+}
+
+static void plist_kunit_add_empty(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a;
+
+ plist_node_init(&a, 10);
+
+ KUNIT_EXPECT_TRUE(test, plist_head_empty(&head));
+ KUNIT_EXPECT_TRUE(test, plist_node_empty(&a));
+
+ plist_add(&a, &head);
+
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 1);
+ KUNIT_EXPECT_FALSE(test, plist_head_empty(&head));
+ KUNIT_EXPECT_FALSE(test, plist_node_empty(&a));
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &a);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &a);
+}
+
+static void plist_kunit_add_order(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node n[4];
+ int i;
+
+ plist_node_init(&n[0], 30);
+ plist_node_init(&n[1], 10);
+ plist_node_init(&n[2], 40);
+ plist_node_init(&n[3], 20);
+
+ /* Insert the nodes out of order. */
+ for (i = 0; i < ARRAY_SIZE(n); i++)
+ plist_add(&n[i], &head);
+
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 4);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &n[1]);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&n[1]), &n[3]);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&n[3]), &n[0]);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&n[0]), &n[2]);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &n[2]);
+}
+
+static void plist_kunit_add_duplicates(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c, d, e;
+
+ plist_node_init(&a, 5);
+ plist_node_init(&b, 5);
+ plist_node_init(&c, 9);
+ plist_node_init(&d, 5);
+ plist_node_init(&e, 7);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+ plist_add(&d, &head);
+ plist_add(&e, &head);
+
+ /* node_list: a(5), b(5), d(5), e(7), c(9) -- FIFO in a bucket. */
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 5);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &a);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &b);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&b), &d);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&d), &e);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &c);
+
+ /* Only the first node of each bucket leads the prio_list ring. */
+ KUNIT_EXPECT_FALSE(test, list_empty(&a.prio_list));
+ KUNIT_EXPECT_TRUE(test, list_empty(&b.prio_list));
+ KUNIT_EXPECT_TRUE(test, list_empty(&d.prio_list));
+ KUNIT_EXPECT_FALSE(test, list_empty(&e.prio_list));
+ KUNIT_EXPECT_FALSE(test, list_empty(&c.prio_list));
+
+ KUNIT_EXPECT_PTR_EQ(test, a.prio_list.next, &e.prio_list);
+ KUNIT_EXPECT_PTR_EQ(test, e.prio_list.next, &c.prio_list);
+ KUNIT_EXPECT_PTR_EQ(test, c.prio_list.next, &a.prio_list);
+}
+
+/*
+ * Adding ascending priorities makes every node the new last bucket, the
+ * case the reverse walk in plist_add() is meant to short-circuit.
+ */
+static void plist_kunit_add_ascending(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node n[16];
+ int i;
+
+ for (i = 0; i < ARRAY_SIZE(n); i++) {
+ plist_node_init(&n[i], i);
+ plist_add(&n[i], &head);
+ KUNIT_ASSERT_EQ(test, plist_kunit_verify(test, &head), i + 1);
+ }
+
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &n[0]);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &n[15]);
+}
+
+/* Adding descending priorities makes every node the new first bucket. */
+static void plist_kunit_add_descending(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node n[16];
+ int i;
+
+ for (i = 0; i < ARRAY_SIZE(n); i++) {
+ plist_node_init(&n[i], ARRAY_SIZE(n) - i);
+ plist_add(&n[i], &head);
+ KUNIT_ASSERT_EQ(test, plist_kunit_verify(test, &head), i + 1);
+ }
+
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &n[15]);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &n[0]);
+}
+
+static void plist_kunit_add_extremes(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c;
+
+ plist_node_init(&a, 0);
+ plist_node_init(&b, INT_MAX);
+ plist_node_init(&c, INT_MIN);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ /* INT_MIN is the highest priority, INT_MAX the lowest. */
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &c);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&c), &a);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &b);
+}
+
+static void plist_kunit_del_bucket_head(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c;
+
+ plist_node_init(&a, 1);
+ plist_node_init(&b, 1);
+ plist_node_init(&c, 2);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ /* Removing the bucket head hands prio_list over to the successor. */
+ plist_del(&a, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 2);
+ KUNIT_EXPECT_TRUE(test, plist_node_empty(&a));
+ KUNIT_EXPECT_FALSE(test, list_empty(&b.prio_list));
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &b);
+
+ /* Removing the last node of the last bucket empties the list. */
+ plist_del(&c, &head);
+ plist_del(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 0);
+ KUNIT_EXPECT_TRUE(test, plist_head_empty(&head));
+
+ /* A removed node can be added back. */
+ plist_add(&a, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 1);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &a);
+}
+
+static void plist_kunit_del_bucket_follower(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c;
+
+ plist_node_init(&a, 1);
+ plist_node_init(&b, 1);
+ plist_node_init(&c, 2);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ /* Removing a bucket follower must not disturb the prio_list ring. */
+ plist_del(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 2);
+ KUNIT_EXPECT_FALSE(test, list_empty(&a.prio_list));
+ KUNIT_EXPECT_FALSE(test, list_empty(&c.prio_list));
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &c);
+ KUNIT_EXPECT_PTR_EQ(test, a.prio_list.next, &c.prio_list);
+ KUNIT_EXPECT_PTR_EQ(test, c.prio_list.next, &a.prio_list);
+}
+
+static void plist_kunit_del_middle_bucket(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c;
+
+ plist_node_init(&a, 1);
+ plist_node_init(&b, 2);
+ plist_node_init(&c, 3);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ /* Removing the only node of a middle bucket splices the ring. */
+ plist_del(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 2);
+ KUNIT_EXPECT_TRUE(test, plist_node_empty(&b));
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &c);
+ KUNIT_EXPECT_PTR_EQ(test, a.prio_list.next, &c.prio_list);
+ KUNIT_EXPECT_PTR_EQ(test, c.prio_list.next, &a.prio_list);
+}
+
+/*
+ * Deleting the head of the last priority bucket: its follower takes over
+ * the prio_list entry, and the ring of bucket heads has to wrap round to
+ * the first bucket.
+ */
+static void plist_kunit_del_last_bucket_head(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c;
+
+ plist_node_init(&a, 1);
+ plist_node_init(&b, 2);
+ plist_node_init(&c, 2);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ plist_del(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 2);
+ KUNIT_EXPECT_TRUE(test, plist_node_empty(&b));
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &c);
+ KUNIT_EXPECT_FALSE(test, list_empty(&c.prio_list));
+ KUNIT_EXPECT_PTR_EQ(test, a.prio_list.next, &c.prio_list);
+ KUNIT_EXPECT_PTR_EQ(test, c.prio_list.next, &a.prio_list);
+}
+
+static void plist_kunit_requeue_basic(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c;
+
+ plist_node_init(&a, 1);
+ plist_node_init(&b, 2);
+ plist_node_init(&c, 2);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ /* A node whose successor has a different priority is left alone. */
+ plist_requeue(&a, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &a);
+
+ /* Requeueing moves a node after its same-priority peers. */
+ plist_requeue(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &c);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&c), &b);
+
+ /* Requeueing the last node of the list is a no-op. */
+ plist_requeue(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &b);
+
+ /* ...and the peers rotate back. */
+ plist_requeue(&c, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &b);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&b), &c);
+}
+
+/*
+ * The plist_requeue() shortcut: after plist_del() the node's same-priority
+ * successor took over the prio_list entry, so the node can be inserted
+ * directly before the next bucket instead of walking the node_list.
+ */
+static void plist_kunit_requeue_shortcut(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c, d;
+
+ plist_node_init(&a, 1);
+ plist_node_init(&b, 2);
+ plist_node_init(&c, 2);
+ plist_node_init(&d, 3);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+ plist_add(&d, &head);
+
+ plist_requeue(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 4);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &c);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&c), &b);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&b), &d);
+
+ /* The tail of its bucket has a different priority: no-op. */
+ plist_requeue(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 4);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&c), &b);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&b), &d);
+}
+
+/*
+ * Regression test for commit 43c91b152243 ("lib/plist: fix
+ * plist_requeue() corrupting order in the last bucket"): when the
+ * requeued node heads the last priority bucket, the prio_list ring of the
+ * bucket heads wraps round to the first bucket, and the node must end up
+ * at the very end of the list instead of jumping to its front.
+ */
+static void plist_kunit_requeue_last_bucket(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c, d, e;
+
+ plist_node_init(&a, 0);
+ plist_node_init(&b, 1);
+ plist_node_init(&c, 1);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ plist_requeue(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &a);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &c);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &b);
+
+ /* The same wrap with an intermediate bucket before the last one. */
+ plist_node_init(&d, 2);
+ plist_node_init(&e, 2);
+ plist_add(&d, &head);
+ plist_add(&e, &head);
+
+ plist_requeue(&d, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 5);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&b), &e);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &d);
+}
+
+/*
+ * Requeueing the head of the first priority bucket: its follower takes
+ * over the bucket, so the node moves behind it and the new first bucket
+ * has to be linked in the prio_list ring instead.
+ */
+static void plist_kunit_requeue_first_bucket_head(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c;
+
+ plist_node_init(&a, 1);
+ plist_node_init(&b, 1);
+ plist_node_init(&c, 2);
+
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ plist_requeue(&a, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &b);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&b), &a);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &c);
+ KUNIT_EXPECT_TRUE(test, list_empty(&a.prio_list));
+ KUNIT_EXPECT_FALSE(test, list_empty(&b.prio_list));
+ KUNIT_EXPECT_PTR_EQ(test, b.prio_list.next, &c.prio_list);
+ KUNIT_EXPECT_PTR_EQ(test, c.prio_list.next, &b.prio_list);
+}
+
+static void plist_kunit_first_last_entry(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_kunit_item items[3];
+ struct plist_kunit_item *first, *last;
+ int i;
+
+ for (i = 0; i < ARRAY_SIZE(items); i++) {
+ items[i].id = i;
+ plist_node_init(&items[i].node, i + 1);
+ plist_add(&items[i].node, &head);
+ }
+
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+
+ first = plist_first_entry(&head, struct plist_kunit_item, node);
+ last = plist_last_entry(&head, struct plist_kunit_item, node);
+ KUNIT_EXPECT_EQ(test, first->id, 0);
+ KUNIT_EXPECT_EQ(test, last->id, 2);
+
+ KUNIT_EXPECT_EQ(test, plist_next(&items[0].node)->prio, 2);
+ KUNIT_EXPECT_EQ(test, plist_prev(&items[2].node)->prio, 2);
+}
+
+/*
+ * Deleting and requeueing the priority extremes, including handing the
+ * prio_list ring over when the INT_MIN bucket head goes away.
+ */
+static void plist_kunit_extremes_ops(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c;
+
+ plist_node_init(&a, 0);
+ plist_node_init(&b, INT_MAX);
+ plist_node_init(&c, INT_MIN);
+
+ plist_add(&c, &head);
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+
+ /* Deleting the INT_MIN head hands the ring over to the next bucket. */
+ plist_del(&c, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 2);
+ KUNIT_EXPECT_TRUE(test, plist_node_empty(&c));
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &a);
+
+ /* Requeueing the INT_MAX tail node is a no-op. */
+ plist_requeue(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 2);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &b);
+
+ /* Deleting the last bucket leaves a single-bucket list. */
+ plist_del(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 1);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &a);
+ KUNIT_EXPECT_TRUE(test, list_empty(&a.prio_list));
+}
+
+/*
+ * Deterministic pseudo-random add/del/requeue churn, mirroring the
+ * in-module test under CONFIG_DEBUG_PLIST but checking the invariants
+ * after every operation with KUnit assertions instead of BUG_ON().
+ *
+ * Priorities are drawn from a small range so that the list actually
+ * contains multi-node priority buckets, and the requeue step picks a node
+ * that has a same-priority successor -- only such a node moves, so every
+ * requeue in the loop is a real move and its result is checked.
+ */
+static void plist_kunit_random(struct kunit *test)
+{
+ struct plist_node nodes[24];
+ PLIST_HEAD(head);
+ unsigned int r = 12345;
+ int i, loop, nr_expect = 0, nr_requeued = 0;
+
+ for (i = 0; i < ARRAY_SIZE(nodes); i++)
+ plist_node_init(&nodes[i], 0);
+
+ for (loop = 0; loop < 1000; loop++) {
+ r = r * 193939u % 47629u;
+ i = r % ARRAY_SIZE(nodes);
+ if (plist_node_empty(&nodes[i])) {
+ r = r * 193939u % 47629u;
+ plist_node_init(&nodes[i], r % 8);
+ plist_add(&nodes[i], &head);
+ nr_expect++;
+ } else {
+ plist_del(&nodes[i], &head);
+ nr_expect--;
+ }
+
+ KUNIT_ASSERT_EQ(test, plist_kunit_verify(test, &head),
+ nr_expect);
+
+ for (i = 0; i < ARRAY_SIZE(nodes); i++) {
+ struct plist_node *next;
+
+ if (plist_node_empty(&nodes[i]) ||
+ &nodes[i] == plist_last(&head))
+ continue;
+ next = plist_next(&nodes[i]);
+ if (next->prio != nodes[i].prio)
+ continue;
+
+ plist_requeue(&nodes[i], &head);
+ nr_requeued++;
+
+ KUNIT_ASSERT_EQ(test,
+ plist_kunit_verify(test, &head),
+ nr_expect);
+ /* A requeued node is now the tail of its bucket. */
+ if (&nodes[i] != plist_last(&head))
+ KUNIT_EXPECT_NE(test, nodes[i].prio,
+ plist_next(&nodes[i])->prio);
+ break;
+ }
+ }
+
+ /* The requeue part of the churn must actually have run. */
+ KUNIT_EXPECT_GT(test, nr_requeued, 0);
+
+ for (i = 0; i < ARRAY_SIZE(nodes); i++) {
+ if (plist_node_empty(&nodes[i]))
+ continue;
+ plist_del(&nodes[i], &head);
+ nr_expect--;
+ KUNIT_ASSERT_EQ(test, plist_kunit_verify(test, &head),
+ nr_expect);
+ }
+
+ KUNIT_EXPECT_TRUE(test, plist_head_empty(&head));
+}
+
+/*
+ * Requeueing inside a single priority bucket exercises the degenerate
+ * prio_list ring (a self loop on the first node), and requeueing a bucket
+ * follower walks to the end of its bucket but not past the next one.
+ */
+static void plist_kunit_requeue_bucket_edges(struct kunit *test)
+{
+ PLIST_HEAD(head);
+ struct plist_node a, b, c, d, e;
+
+ plist_node_init(&a, 1);
+ plist_node_init(&b, 1);
+ plist_node_init(&c, 1);
+ plist_add(&a, &head);
+ plist_add(&b, &head);
+ plist_add(&c, &head);
+
+ /* Single bucket: the ring is a self loop on the first node. */
+ plist_requeue(&a, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &b);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&b), &c);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &a);
+ /*
+ * b heads the bucket now, but a single bucket never links onto
+ * the ring: after the handover in plist_del() the entry is a self
+ * loop, which list_empty() reports as empty.
+ */
+ KUNIT_EXPECT_TRUE(test, list_empty(&b.prio_list));
+
+ plist_requeue(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 3);
+ KUNIT_EXPECT_PTR_EQ(test, plist_first(&head), &c);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &b);
+
+ /* A follower requeue walks to the end of its bucket, not past it. */
+ plist_node_init(&d, 1);
+ plist_node_init(&e, 2);
+ plist_add(&d, &head);
+ plist_add(&e, &head);
+
+ plist_requeue(&b, &head);
+ KUNIT_EXPECT_EQ(test, plist_kunit_verify(test, &head), 5);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&c), &a);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&a), &d);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&d), &b);
+ KUNIT_EXPECT_PTR_EQ(test, plist_next(&b), &e);
+ KUNIT_EXPECT_PTR_EQ(test, plist_last(&head), &e);
+}
+
+static struct kunit_case plist_kunit_test_cases[] = {
+ KUNIT_CASE(plist_kunit_add_empty),
+ KUNIT_CASE(plist_kunit_add_order),
+ KUNIT_CASE(plist_kunit_add_duplicates),
+ KUNIT_CASE(plist_kunit_add_ascending),
+ KUNIT_CASE(plist_kunit_add_descending),
+ KUNIT_CASE(plist_kunit_add_extremes),
+ KUNIT_CASE(plist_kunit_del_bucket_head),
+ KUNIT_CASE(plist_kunit_del_bucket_follower),
+ KUNIT_CASE(plist_kunit_del_middle_bucket),
+ KUNIT_CASE(plist_kunit_del_last_bucket_head),
+ KUNIT_CASE(plist_kunit_requeue_basic),
+ KUNIT_CASE(plist_kunit_requeue_shortcut),
+ KUNIT_CASE(plist_kunit_requeue_last_bucket),
+ KUNIT_CASE(plist_kunit_requeue_first_bucket_head),
+ KUNIT_CASE(plist_kunit_requeue_bucket_edges),
+ KUNIT_CASE(plist_kunit_first_last_entry),
+ KUNIT_CASE(plist_kunit_extremes_ops),
+ KUNIT_CASE(plist_kunit_random),
+ {}
+};
+
+static struct kunit_suite plist_kunit_test_suite = {
+ .name = "plist",
+ .test_cases = plist_kunit_test_cases,
+};
+
+kunit_test_suite(plist_kunit_test_suite);
+
+MODULE_IMPORT_NS("EXPORTED_FOR_KUNIT_TESTING");
+
+MODULE_DESCRIPTION("KUnit tests for the priority sorted list (plist)");
+MODULE_LICENSE("GPL");
_
Patches currently in -mm which might be from wuyuehong@cmss.chinamobile.com are
lib-tests-add-kunit-tests-for-the-priority-sorted-list-plist.patch
^ permalink raw reply [flat|nested] 2+ messages in thread
end of thread, other threads:[~2026-11-08 3:38 UTC | newest]
Thread overview: 2+ messages (download: mbox.gz follow: Atom feed
-- links below jump to the message on this page --
2026-11-08 3:38 + lib-tests-add-kunit-tests-for-the-priority-sorted-list-plist.patch added to mm-nonmm-unstable branch Andrew Morton
-- strict thread matches above, loose matches on Subject: below --
2026-11-07 7:07 Andrew Morton
This is an external index of several public inboxes,
see mirroring instructions on how to clone and mirror
all data and code used by this external index.