Re: [PATCH v3] lib/tests: add KUnit tests for the priority sorted list (plist)

[Geert Uytterhoeven]

Hi Yuehong,

On Sat, 7 Nov 2026 at 05:43, Yuehong Wu <wuyuehong@xxxxxxxxxxxxxxxxxxxx> wrote:
> 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.

Thanks for the update!

> Reported-by: kernel test robot <lkp@xxxxxxxxx>
> Closes: https://lore.kernel.org/oe-kbuild-all/202611052109.GqbzRkv1-lkp@xxxxxxxxx/
> Suggested-by: Geert Uytterhoeven <geert@xxxxxxxxxxxxxx>

I don't think any of the above tags are appropriate: they are not
related to the reason for creating your patch patch, but merely review
comments raised on earlier versions of your patch.

Hence please drop them.

> Signed-off-by: Yuehong Wu <wuyuehong@xxxxxxxxxxxxxxxxxxxx>

Gr{oetje,eeting}s,

                        Geert

-- 
Geert Uytterhoeven -- There's lots of Linux beyond ia32 -- geert@xxxxxxxxxxxxxx

In personal conversations with technical people, I call myself a hacker. But
when I'm talking to journalists I just say "programmer" or something like that.
                                -- Linus Torvalds