[merged mm-nonmm-stable] lib-plist-fix-plist_requeue-corrupting-order-in-the-last-bucket.patch removed from -mm tree

[merged mm-nonmm-stable] lib-plist-fix-plist_requeue-corrupting-order-in-the-last-bucket.patch removed from -mm tree

[Andrew Morton]

The quilt patch titled
     Subject: lib/plist: fix plist_requeue() corrupting order in the last bucket
has been removed from the -mm tree.  Its filename was
     lib-plist-fix-plist_requeue-corrupting-order-in-the-last-bucket.patch

This patch was dropped because it was merged into the mm-nonmm-stable branch
of git://git.kernel.org/pub/scm/linux/kernel/git/akpm/mm

------------------------------------------------------
From: Adam Harshbarger <handyhandyman.adam@gmail.com>
Subject: lib/plist: fix plist_requeue() corrupting order in the last bucket
Date: Thu, 3 Sep 2026 17:24:56 -0500

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

Link: https://lore.kernel.org/20260903222456.1881786-1-handyhandyman.adam@gmail.com
Fixes: 95d4b3450ebe ("lib/plist.c: add shortcut for plist_requeue()")
Signed-off-by: Adam Harshbarger <handyhandyman.adam@gmail.com>
Signed-off-by: Andrew Morton <akpm@linux-foundation.org>
Assisted-by: Claude:claude-opus-5
Cc: I Hsin Cheng <richard120310@gmail.com>
Cc: <stable@vger.kernel.org> # v6.15+
---

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

--- a/lib/plist.c~lib-plist-fix-plist_requeue-corrupting-order-in-the-last-bucket
+++ a/lib/plist.c
@@ -174,8 +174,15 @@ void plist_requeue(struct plist_node *no
 	/*
 	 * 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;
_

Patches currently in -mm which might be from handyhandyman.adam@gmail.com are