[PATCH] lib/plist: fix plist_requeue() corrupting order in the last bucket

[PATCH] lib/plist: fix plist_requeue() corrupting order in the last bucket

[Adam Harshbarger]

plist_requeue() is meant to move a node to the end of its own priority
run.  When the node heads the *last* priority bucket it is instead placed
at the head of the whole list, leaving the plist unsorted:

  built:      A(prio 0) B(prio 1) C(prio 1)
  requeue(B): B(prio 1) A(prio 0) C(prio 1)
  expected:   A(prio 0) C(prio 1) B(prio 1)

prio_list is a *headless* circular ring of the nodes that lead each
priority bucket.  The shortcut added by commit 95d4b3450ebe ("lib/plist.c:
add shortcut for plist_requeue()") takes

	iter = list_entry(iter->prio_list.next, struct plist_node,
			  prio_list);
	node_next = &iter->node_list;

which from the last bucket wraps round to the *first* bucket, so
node_next ends up pointing at the head of the list rather than at its
end.  The plist_for_each_continue() loop immediately below it computes
the correct answer (&head->node_list) for that case.

With any bucket after it the shortcut is correct, which is why this went
unnoticed: the benchmark in that commit measured elapsed time and never
checked the resulting order.

Keep the shortcut -- it is a real win -- but exclude the case where
iter's bucket is the last one, which is exactly when its ring successor
is the first bucket again.

Reachable from mm/swapfile.c, which rotates swap_avail_heads[] with
plist_requeue().  It takes three or more swap devices: at least two
distinct priorities, so that a later bucket exists for the ring to wrap
round from, and two or more devices sharing the lowest priority, so that
plist_requeue() does not return early.  One device per priority returns
early at the node->prio != iter->prio test.  A single priority is also
safe, but for a different reason worth stating: with one bucket no node
is ever linked onto prio_list at all -- plist_add() skips it for the
first node and for every node whose predecessor shares its priority --
so list_empty(&iter->prio_list) holds and the shortcut is never entered.

Tested by driving three implementations -- the pre-95d4b3450ebe code,
current mainline, and this patch -- through 1,084,492 identical random
add/del/requeue operations over 24 nodes and 1..5 distinct priorities,
comparing the resulting node_list node for node after every operation:

  variant             differs from pre-95d4b3450ebe  left list unsorted
  pre-95d4b3450ebe    -- (reference)                                  0
  mainline                                  289,297             276,660
  this patch                                      0                   0

Fixes: 95d4b3450ebe ("lib/plist.c: add shortcut for plist_requeue()")
Cc: stable@vger.kernel.org # v6.15+
Assisted-by: Claude:claude-opus-5
Signed-off-by: Adam Harshbarger <handyhandyman.adam@gmail.com>
---
The bug was found and this fix was written with the assistance of a large
language model, per Documentation/process/coding-assistants.rst.  The
Signed-off-by is mine and the DCO certification is mine.

What was and was not done, per that document's step 8:

  Verified: the bug reproduces against lib/plist.c taken from torvalds/master
  at the time of writing.  Three variants -- the pre-95d4b3450ebe code,
  current mainline, and this patch -- were driven through 1,084,492 identical
  random add/del/requeue operations over 24 nodes and 1..5 distinct
  priorities, comparing node_list node for node after every operation.  The
  patched variant matches the pre-shortcut reference exactly and never leaves
  the list unsorted.  checkpatch.pl --strict reports 0 errors, 0 warnings,
  0 checks.

  NOT done: this was verified in userspace only.  The patch has not been
  compiled into a kernel and has not been booted, and no swap configuration
  was exercised on real hardware -- the reachability argument via
  mm/swapfile.c is from reading the code, not from observing a stall.  If you
  would like the userspace reproducer it is available on request; it fetches
  lib/plist.c from your tree at run time and vendors nothing.

  An alternative patch reverting 95d4b3450ebe outright is available if you
  would prefer that for stable.

 lib/plist.c | 7 +++++++
 1 file changed, 7 insertions(+)

diff --git a/lib/plist.c b/lib/plist.c
index a5bef38..b027353 100644
--- a/lib/plist.c
+++ b/lib/plist.c
@@ -174,8 +174,15 @@ 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 headless ring, so from the LAST bucket ->next wraps
+	 * round to the first one; in that case node_next is the list head.
 	 */
 	if (!list_empty(&iter->prio_list)) {
+		struct plist_node *first = plist_first(head);
+
+		if (iter->prio_list.next == &first->prio_list)
+			goto queue;
 		iter = list_entry(iter->prio_list.next, struct plist_node,
 				  prio_list);
 		node_next = &iter->node_list;

Re: [PATCH] lib/plist: fix plist_requeue() corrupting order in the last bucket

[Andrew Morton]

On Thu,  3 Sep 2026 17:24:56 -0500 Adam Harshbarger <handyhandyman.adam@gmail.com> wrote:

> plist_requeue() is meant to move a node to the end of its own priority
> run.  When the node heads the *last* priority bucket it is instead placed
> at the head of the whole list, leaving the plist unsorted:
> 
> ...
>
> Reachable from mm/swapfile.c, which rotates swap_avail_heads[] with
> plist_requeue().  It takes three or more swap devices: at least two
> distinct priorities, so that a later bucket exists for the ring to wrap
> round from, and two or more devices sharing the lowest priority, so that
> plist_requeue() does not return early.  One device per priority returns
> early at the node->prio != iter->prio test.  A single priority is also
> safe, but for a different reason worth stating: with one bucket no node
> is ever linked onto prio_list at all -- plist_add() skips it for the
> first node and for every node whose predecessor shares its priority --
> so list_empty(&iter->prio_list) holds and the shortcut is never entered.
> 
> ...
>

Thanks.

> Fixes: 95d4b3450ebe ("lib/plist.c: add shortcut for plist_requeue()")
> Cc: stable@vger.kernel.org # v6.15+

Why the cc:stable?  A description of the userspace impact would help
people understand the need for backporting.  Please always include
such a description when fixing things.