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

[Nickolai Zeldovich <nickolai@csail.mit.edu>]

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