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

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

[Nickolai Zeldovich]

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.

Fixes: 95d4b3450ebe ("lib/plist.c: add shortcut for plist_requeue()")
Cc: stable@vger.kernel.org
Cc: I Hsin Cheng <richard120310@gmail.com>
Cc: Ching-Chun (Jim) Huang <jserv@ccns.ncku.edu.tw>
Assisted-by: LLM
Signed-off-by: Nickolai Zeldovich <nickolai@csail.mit.edu>
---
 lib/plist.c | 27 ++++++++++++++++++++++++++-
 1 file changed, 26 insertions(+), 1 deletion(-)

diff --git a/lib/plist.c b/lib/plist.c
index a5bef38add43..20291872923a 100644
--- 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

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

[Andrew Morton]

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

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

[Nickolai Zeldovich]

On Sat, Oct 10, 2026 at 7:26 PM Andrew Morton <akpm@linux-foundation.org> wrote:
> 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.

This patch is equivalent; I don't see any reason to prefer my fix
(except for the test case that might be helpful in catching
regressions).

Thanks,

Nickolai.

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

[Andrew Morton]

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

> On Sat, Oct 10, 2026 at 7:26 PM Andrew Morton <akpm@linux-foundation.org> wrote:
> > 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.
> 
> This patch is equivalent; I don't see any reason to prefer my fix

Thanks.  Can I add your Reviewed-by:?

> (except for the test case that might be helpful in catching
> regressions).

I like test cases and I take patches ;)

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

[Nickolai Zeldovich]

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).  Not booted.

Assisted-by: LLM
Signed-off-by: Nickolai Zeldovich <nickolai@csail.mit.edu>
---
 lib/plist.c | 19 +++++++++++++++++++
 1 file changed, 19 insertions(+)

diff --git a/lib/plist.c b/lib/plist.c
index b0273533c04d..ac3f55dc49e5 100644
--- 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);
+	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.55.0

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

[Andrew Morton]

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.

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

[Nickolai Zeldovich]

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.

Add a deterministic case for the failing shape: A(1) B(2) C(2), requeue
B.  The expected result is A(1) C(2) B(2), with B at the end of the
list; the broken shortcut produced B(2) A(1) C(2).  Check it with a
WARN() rather than a BUG_ON(), and skip plist_test_check() when the
warning fires, since its BUG_ON()s would stop the boot on the misordered
list; the node_list and prio_list links of the result are still verified
by plist_test_check() when the order is right.

Boot-tested on QEMU virt with a riscv64 defconfig kernel plus
CONFIG_DEBUG_PLIST=y, built with LLVM=1.  With the fix applied the test
passes and the boot proceeds.  With the fix reverted the warning fires at
boot and the boot proceeds:

  [    0.864761] start plist test
  [    0.871849] ------------[ cut here ]------------
  [    0.871905] plist_requeue() put the node in front of the list
  [    0.872921] WARNING: lib/plist.c:295 at plist_test+0x33a/0x342, CPU#0: swapper/0/1
  ...
  [    0.885968] ---[ end trace 0000000000000000 ]---
  [    0.887060] end plist test

Assisted-by: LLM
Signed-off-by: Nickolai Zeldovich <nickolai@csail.mit.edu>
---
v2: per Andrew's review of v1,
    https://lore.kernel.org/lkml/20261010211804.2d8a5f6180c74b08e18ad48a@linux-foundation.org/
  - WARN() instead of BUG_ON(), and plist_test_check() is skipped when
    the warning fires, so a broken plist_requeue() no longer stops the
    boot at this test.
  - Boot-tested on QEMU virt, both with the queued fix (test passes)
    and without it (warning fires, boot continues).
  - Applies on top of "lib/plist: fix plist_requeue() corrupting order
    in the last bucket" (Adam Harshbarger).
v1: https://lore.kernel.org/lkml/20261011012245.765558-1-nickolai@csail.mit.edu/

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

diff --git a/lib/plist.c b/lib/plist.c
index b0273533c04d..9591c38e8ad6 100644
--- a/lib/plist.c
+++ b/lib/plist.c
@@ -283,6 +283,27 @@ 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.  On failure warn and skip
+	 * plist_test_check(), which would BUG_ON() the misordered list.
+	 */
+	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);
+	if (!WARN(plist_last(&test_head) != test_node + 1,
+		  "plist_requeue() put the node in front of the list\n"))
+		plist_test_check(3);
+	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.55.0

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

[Nickolai Zeldovich]

On Sun, Oct 11, 2026 at 12:18 AM Andrew Morton
<akpm@linux-foundation.org> wrote:
> On Sat, 10 Oct 2026 21:22:33 -0400 Nickolai Zeldovich <nickolai@csail.mit.edu> wrote:
> >  Not booted.
>
> err, it should be,  If this is wrong, we crash every kernel at boot.
>
> > +     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.

Fixed, boot-tested, and re-sent as a v2 patch; thanks for the feedback!

Nickolai.

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

[Nickolai Zeldovich]

On Sat, Oct 10, 2026 at 9:10 PM Andrew Morton <akpm@linux-foundation.org> wrote:
> On Sat, 10 Oct 2026 19:33:46 -0400 Nickolai Zeldovich <nickolai@csail.mit.edu> wrote:
> > On Sat, Oct 10, 2026 at 7:26 PM Andrew Morton <akpm@linux-foundation.org> wrote:
> > > 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.
> >
> > This patch is equivalent; I don't see any reason to prefer my fix
>
> Thanks.  Can I add your Reviewed-by:?

Sure, sounds good to me.

> > (except for the test case that might be helpful in catching
> > regressions).
>
> I like test cases and I take patches ;)

Sent just now.

Thanks,

Nickolai.