Re: [PATCH] lib/plist: fix plist_requeue() shortcut inserting the node at the list head

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

On Fri,  9 Oct 2026 01:18:47 -0400 Nickolai Zeldovich <nickolai@csail.mit.edu> wrote:

> plist_requeue() moves a node to the end of its priority run.  Since commit
> 95d4b3450ebe ("lib/plist.c: add shortcut for plist_requeue()"), when the
> node was the head of its run it skips the scan of the remaining nodes of
> that run and takes node_next from the prio_list of the node's successor,
> which replaced it as the run head in plist_del():
> 
> 	iter = list_entry(iter->prio_list.next, struct plist_node, prio_list);
> 	node_next = &iter->node_list;
> 
> prio_list is a ring of the first nodes of each priority run, without a
> sentinel.  For every run but the last one, iter->prio_list.next is the
> head of the next run and the shortcut is correct.  For the last run it
> wraps around to the head of the FIRST run, and list_add_tail() then
> inserts the node in front of the whole list, ahead of nodes with a lower
> prio value.  The list is no longer sorted:
> 
> 	before requeue(B):  A(1) B(2) C(2)
> 	after  requeue(B):  B(2) A(1) C(2)
> 
> The condition is: at least two priority runs, the node is the first node
> of the last run, and it has a successor with the same priority.  A single
> run is unaffected, because a one-element prio_list ring is list_empty()
> and the slow path runs.
> 
> The only caller is swap_alloc_slow() in mm/swapfile.c, which requeues a
> swap device within its priority group.  With several swap devices on more
> than one priority level, where the lowest priority level has two or more
> devices, rotating the first device of that level moves it ahead of all
> higher-priority devices, so subsequent swap allocations go to a
> low-priority device first.
> 
> Only take the shortcut's node_next when the next ring entry really is a
> higher-priority run; otherwise append the node at the end of the list.
> 
> The CONFIG_DEBUG_PLIST self-test did not catch this because it only
> requeues nodes it has just added, which are always the last of their run,
> so plist_requeue() returns early every time.  Add a deterministic test
> case for the failing shape; plist_test_check() verifies the ordering and
> the prio_list ring after it.
> 
> The bug was found while attempting to prove plist_requeue() against a
> specification stating that the list stays sorted, in the MachCSL
> verification of the Linux kernel on RISC-V; the proof failed at this
> arm and the prover produced the counterexample above.  The fix and the
> test case were drafted with Claude Code (Claude Fable 5.1) and reviewed
> and tested by hand: the three functions were transcribed to a userspace
> harness that reproduces the misordering before the fix and the expected
> order after it, and lib/plist.o builds with CONFIG_DEBUG_PLIST=y.

Thanks.

I recently queued a fix for this problem from Alex:
	https://lore.kernel.org/20260903222456.1881786-1-handyhandyman.adam@gmail.com

The two patches are rather different.  Please review Alex's change and
and let us know of any alterations/improvements which you see.

> --- a/lib/plist.c
> +++ b/lib/plist.c
> @@ -174,11 +174,17 @@ void plist_requeue(struct plist_node *node, struct plist_head *head)
>  	/*
>  	 * After plist_del(), iter is the replacement of the node.  If the node
>  	 * was on prio_list, take shortcut to find node_next instead of looping.
> +	 *
> +	 * prio_list is a ring of the first nodes of each priority run, without
> +	 * a sentinel: if node's run is the last one, iter->prio_list.next wraps
> +	 * around to the first run, and node must be appended at the end of the
> +	 * list instead of being inserted in front of it.
>  	 */
>  	if (!list_empty(&iter->prio_list)) {
>  		iter = list_entry(iter->prio_list.next, struct plist_node,
>  				  prio_list);
> -		node_next = &iter->node_list;
> +		if (iter->prio > node->prio)
> +			node_next = &iter->node_list;
>  		goto queue;
>  	}
>  
> @@ -276,6 +282,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);
> +	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() */
> -- 
> 2.56.0