Re: [PATCH] lib/plist: add a plist_test case for plist_requeue() on the last priority bucket

[Andrew Morton <akpm@linux-foundation.org>]

On Sat, 10 Oct 2026 21:22:33 -0400 Nickolai Zeldovich <nickolai@csail.mit.edu> wrote:

> The plist_requeue() shortcut inserted the node at the head of the list
> when the node was the first of the last priority bucket and had a
> successor of the same priority, with an earlier bucket present (fixed
> by "lib/plist: fix plist_requeue() corrupting order in the last
> bucket").  The CONFIG_DEBUG_PLIST self-test did not catch it: it only
> requeues nodes it has just added, which are always the last of their
> bucket, so plist_requeue() returned early every time, and
> plist_test_check() only verifies the links, not that the shortcut's
> insertion point is correct.
> 
> Add a deterministic case for the failing shape: A(1) B(2) C(2), requeue
> B.  plist_test_check() verifies the node_list and prio_list links and
> the ordering, and the new BUG_ON() checks that B ended up at the end of
> the list rather than in front of A.
> 
> Before the fix the case produces B(2) A(1) C(2) and the BUG_ON() fires;
> with the fix it produces A(1) C(2) B(2).  Verified with the three
> functions transcribed to a userspace harness driving this exact case
> against mainline (fails), the queued fix (passes) and the alternative
> fix I had posted (passes); lib/plist.o builds with CONFIG_DEBUG_PLIST=y
> (LLVM=1 ARCH=riscv).

Thanks.

>  Not booted.

err, it should be,  If this is wrong, we crash every kernel at boot.

> --- a/lib/plist.c
> +++ b/lib/plist.c
> @@ -283,6 +283,25 @@ static int  __init plist_test(void)
>  		plist_test_check(nr_expect);
>  	}
>  
> +	/*
> +	 * Requeue a node which is the first of the last priority run and has
> +	 * a successor of the same priority, with an earlier run present: the
> +	 * shortcut in plist_requeue() must append it at the end of the list,
> +	 * not in front of the first run.  The random test above never
> +	 * exercises this, since it only requeues nodes it has just added,
> +	 * which are always the last of their run.
> +	 */
> +	plist_head_init(&test_head);
> +	for (i = 0; i < 3; i++) {
> +		plist_node_init(test_node + i, i ? 2 : 1);
> +		plist_add(test_node + i, &test_head);
> +	}
> +	plist_test_requeue(test_node + 1);
> +	plist_test_check(3);
> +	BUG_ON(plist_last(&test_head) != test_node + 1);

No, let's not add a BUG_ON for some selftest.  Emit a loud warning and
proceed.  If it triggers, someone will report it.

> +	for (i = 0; i < 3; i++)
> +		plist_del(test_node + i, &test_head);
> +
>  	printk(KERN_DEBUG "end plist test\n");
>  
>  	/* Worst case test for plist_add() */

This goes in my for-7.4-rcX pile, so no hurry at all.