Skip to contentSkip to conversation

lib/sort: Optimize the number of swaps and comparisons

PATCH Applied Kuan-Wei Chiu 7 participants 21 messages Jan 13, 2024 – Jan 15, 2025

Subsystems (5)
lore
Share & tools
lore
#0 lore raw

cover lib/sort: Optimize the number of swaps and comparisons

Hello,

This patch series aims to optimize the heapsort algorithm, specifically targeting a reduction in the number of swaps and comparisons required.

Thanks,
Kuan-Wei Chiu

Kuan-Wei Chiu (2):
lib/sort: Optimize heapsort for equal elements in sift-down path lib/sort: Optimize heapsort with double-pop variation

 lib/sort.c | 20 +++++++++++++++-----
 1 file changed, 15 insertions(+), 5 deletions(-)
Signature · 1 line
2.25.1
#1 lore raw

PATCH 1/2 lib/sort: Optimize heapsort for equal elements in sift-down path

Currently, when searching for the sift-down path and encountering equal elements, the algorithm chooses the left child. However, considering that the height of the right subtree may be one less than that of the left subtree, selecting the right child in such cases can potentially reduce the number of comparisons and swaps.

For instance, when sorting an array of 10,000 identical elements, the current implementation requires 247,209 comparisons. With this patch, the number of comparisons can be reduced to 227,241.

---
 lib/sort.c | 2 +-
 1 file changed, 1 insertion(+), 1 deletion(-)
lib/sort.c +1 -1
index b399bf10d675..fe4efd4a1410 100644
@@ -262,7 +262,7 @@ void sort_r(void *base, size_t num, size_t size,
 		 * average, 3/4 worst-case.)
 		 */
 		for (b = a; c = 2*b + size, (d = c + size) < n;)
-			b = do_cmp(base + c, base + d, cmp_func, priv) >= 0 ? c : d;
+			b = do_cmp(base + c, base + d, cmp_func, priv) > 0 ? c : d;
 		if (d == n)	/* Special case last leaf with no sibling */
 			b = c;
 
Signature · 1 line
2.25.1
#2 lore raw

PATCH 2/2 lib/sort: Optimize heapsort with double-pop variation

In reply to Kuan-Wei Chiu

Instead of popping only the maximum element from the heap during each iteration, we now pop the two largest elements at once. Although this introduces an additional comparison to determine the second largest element, it enables a reduction in the height of the tree by one during the heapify operations starting from root's left/right child. This reduction in tree height by one leads to a decrease of one comparison and one swap.

This optimization results in saving approximately 0.5 * n swaps without increasing the number of comparisons. Additionally, the heap size during heapify is now one less than the original size, offering a chance for further reduction in comparisons and swaps.

---

The following experimental data is based on the array generated using get_random_u32().

| N     | swaps (old) | swaps (new) | comparisons (old) | comparisons (new) |
|-------|-------------|-------------|-------------------|-------------------|
| 1000  | 9054        | 8569        | 10328             | 10320             |
| 2000  | 20137       | 19182       | 22634             | 22587             |
| 3000  | 32062       | 30623       | 35833             | 35752             |
| 4000  | 44274       | 42282       | 49332             | 49306             |
| 5000  | 57195       | 54676       | 63300             | 63294             |
| 6000  | 70205       | 67202       | 77599             | 77557             |
| 7000  | 83276       | 79831       | 92113             | 92032             |
| 8000  | 96630       | 92678       | 106635            | 106617            |
| 9000  | 110349      | 105883      | 121505            | 121404            |
| 10000 | 124165      | 119202      | 136628            | 136617            |
 lib/sort.c | 18 ++++++++++++++----
 1 file changed, 14 insertions(+), 4 deletions(-)
lib/sort.c +14 -4
index fe4efd4a1410..a0509088f82a 100644
@@ -215,6 +215,7 @@ void sort_r(void *base, size_t num, size_t size,
 	/* pre-scale counters for performance */
 	size_t n = num * size, a = (num/2) * size;
 	const unsigned int lsbit = size & -size;  /* Used to find parent */
+	size_t shift = 0;
 
 	if (!a)		/* num < 2 || size == 0 */
 		return;
@@ -242,12 +243,21 @@ void sort_r(void *base, size_t num, size_t size,
 	for (;;) {
 		size_t b, c, d;
 
-		if (a)			/* Building heap: sift down --a */
-			a -= size;
-		else if (n -= size)	/* Sorting: Extract root to --n */
+		if (a)			/* Building heap: sift down a */
+			a -= size << shift;
+		else if (n > 3 * size) { /* Sorting: Extract two largest elements */
+			n -= size;
 			do_swap(base, base + n, size, swap_func, priv);
-		else			/* Sort complete */
+			shift = do_cmp(base + size, base + 2 * size, cmp_func, priv) <= 0;
+			a = size << shift;
+			n -= size;
+			do_swap(base + a, base + n, size, swap_func, priv);
+		} else if (n > size) {	/* Sorting: Extract root */
+			n -= size;
+			do_swap(base, base + n, size, swap_func, priv);
+		} else	{		/* Sort complete */
 			break;
+		}
 
 		/*
 		 * Sift element at "a" down into heap.  This is the
Signature · 1 line
2.25.1
#3 lore raw

Re: [PATCH 2/2] lib/sort: Optimize heapsort with double-pop variation

Hello,

it appears that this patch has caused suspend-to-idle regression:

https://gitlab.freedesktop.org/drm/amd/-/issues/3436

In brief, my laptop fails to suspend completely with the following error in the log:

Jun 18 12:42:20 kernel: amd_pmc AMDI0005:00: Last suspend didn't reach deepest state

Power consumption remains high enough that my battery has already unexpectedly drained twice before I noticed something was off.
I am not entirely sure how changes to sorting function can influence suspend, but it is what it is. 6.9.5 as shipped by Fedora 40 exhibits the issue, 6.9.5 as shipped by Fedora with the patch reverted does not.

Best regards,
Juliam

#4 lore raw

Re: [PATCH 2/2] lib/sort: Optimize heapsort with double-pop variation

Quoted 8 lines · Julian Sikorski

Hello,

it appears that this patch has caused suspend-to-idle regression:

https://gitlab.freedesktop.org/drm/amd/-/issues/3436

In brief, my laptop fails to suspend completely with the following error in the log:

Quoted 8 lines
Jun 18 12:42:20 kernel: amd_pmc AMDI0005:00: Last suspend didn't reach deepest state

Power consumption remains high enough that my battery has already unexpectedly drained twice before I noticed something was off.
I am not entirely sure how changes to sorting function can influence suspend, but it is what it is. 6.9.5 as shipped by Fedora 40 exhibits the issue, 6.9.5 as shipped by Fedora with the patch reverted does not.

Best regards,
Juliam

+regressions M/L

#regzbot ^introduced: 0e02ca29a563
#regzbot from: Kuan-Wei Chiu <[email protected]> #regzbot monitor: https://gitlab.freedesktop.org/drm/amd/-/issues/3436

#5 lore raw

Re: [PATCH 2/2] lib/sort: Optimize heapsort with double-pop variation

In reply to Julian Sikorski
Quoted 8 lines · Julian Sikorski

it appears that this patch has caused suspend-to-idle regression:

https://gitlab.freedesktop.org/drm/amd/-/issues/3436

In brief, my laptop fails to suspend completely with the following error in the log:

Quoted 8 lines
Jun 18 12:42:20 kernel: amd_pmc AMDI0005:00: Last suspend didn't reach

deepest state

Power consumption remains high enough that my battery has already unexpectedly drained twice before I noticed something was off. I am not entirely sure how changes to sorting function can influence suspend, but it is what it is. 6.9.5 as shipped by Fedora 40 exhibits the issue, 6.9.5 as shipped by Fedora with the patch reverted does not.

Andrew, could you maybe help out here or point us in the direction of somewhat that might be able to help? I'm asking, as from a quick search on lore it seems Kuan-Wei Chiu has not posted anything since nearly four weeks and thus also did not reply to Julian's regression report.

Ciao, Thorsten (wearing his 'the Linux kernel's regression tracker' hat) --
Everything you wanna know about Linux kernel regression tracking:
https://linux-regtracking.leemhuis.info/about/#tldr
If I did something stupid, please tell me, as explained on that page.

#regzbot poke

#6 lore raw

Re: [PATCH 2/2] lib/sort: Optimize heapsort with double-pop variation

Quoted 23 lines · Linux regression tracking (Thorsten Leemhuis)
Quoted 8 lines · Julian Sikorski

it appears that this patch has caused suspend-to-idle regression:

https://gitlab.freedesktop.org/drm/amd/-/issues/3436

In brief, my laptop fails to suspend completely with the following error in the log:

Quoted 8 lines
Jun 18 12:42:20 kernel: amd_pmc AMDI0005:00: Last suspend didn't reach

deepest state

Power consumption remains high enough that my battery has already unexpectedly drained twice before I noticed something was off. I am not entirely sure how changes to sorting function can influence suspend, but it is what it is. 6.9.5 as shipped by Fedora 40 exhibits the issue, 6.9.5 as shipped by Fedora with the patch reverted does not.

Andrew, could you maybe help out here or point us in the direction of somewhat that might be able to help? I'm asking, as from a quick search on lore it seems Kuan-Wei Chiu has not posted anything since nearly four weeks and thus also did not reply to Julian's regression report.

Quoted 7 lines

Ciao, Thorsten (wearing his 'the Linux kernel's regression tracker' hat) --
Everything you wanna know about Linux kernel regression tracking:
https://linux-regtracking.leemhuis.info/about/#tldr
If I did something stupid, please tell me, as explained on that page.

#regzbot poke

Sorry for the late reply.

I apologize for the regression caused by the patch. I am not familiar with the power management domain. I would guess there might be some side effects in the compare or swap functions that I was not aware of.

While reviewing the sort calls that could potentially cause the error, I noticed that the compare function used in the sort call within drivers/acpi/processor_idle.c might not satisfy the transitive relation. Although I'm not sure if this is the root cause of the problem, specifically, if there are two valid acpi_processor_cx elements A and B, and an invalid element C, there could be a scenario where A < B but simultaneously A = C and B = C. However, if I understand correctly, this issue should have existed before this patch but might not have been triggered previously. My patch might have exposed this issue by changing the order of comparisons and swaps.

Regards,
Kuan-Wei

#7 lore raw

Re: [PATCH 2/2] lib/sort: Optimize heapsort with double-pop variation

Quoted 23 lines · Kuan-Wei Chiu
Quoted 9 lines · Linux regression tracking (Thorsten Leemhuis)
Quoted 8 lines · Julian Sikorski

it appears that this patch has caused suspend-to-idle regression:

https://gitlab.freedesktop.org/drm/amd/-/issues/3436

In brief, my laptop fails to suspend completely with the following error in the log:

Quoted 8 lines
Quoted 8 lines
Jun 18 12:42:20 kernel: amd_pmc AMDI0005:00: Last suspend didn't reach

deepest state

Power consumption remains high enough that my battery has already unexpectedly drained twice before I noticed something was off. I am not entirely sure how changes to sorting function can influence suspend, but it is what it is. 6.9.5 as shipped by Fedora 40 exhibits the issue, 6.9.5 as shipped by Fedora with the patch reverted does not.

[...]
I apologize for the regression caused by the patch. I am not familiar with the power management domain. I would guess there might be some side effects in the compare or swap functions that I was not aware of.

Quoted 7 lines

While reviewing the sort calls that could potentially cause the error, I noticed that the compare function used in the sort call within drivers/acpi/processor_idle.c might not satisfy the transitive relation. Although I'm not sure if this is the root cause of the problem, specifically, if there are two valid acpi_processor_cx elements A and B, and an invalid element C, there could be a scenario where A < B but simultaneously A = C and B = C.

Let's bring in Rafael, he might be able to help us out here.

Quoted 4 lines

However, if I
understand correctly, this issue should have existed before this patch but might not have been triggered previously. My patch might have exposed this issue by changing the order of comparisons and swaps.

Yeah, these things happen. But when it comes to the Linux kernel's "no regressions" rule that does not matter much; what matters more is which change exposed the problem.

Ciao, Thorsten

#8 lore raw

PATCH 1/1 ACPI: processor_idle: Fix invalid comparison with insertion sort for latency

The acpi_cst_latency_cmp comparison function currently used for sorting C-state latencies does not satisfy transitivity, causing incorrect sorting results. Specifically, if there are two valid acpi_processor_cx elements A and B and one invalid element C, it may occur that A < B, A = C, and B = C. Sorting algorithms assume that if A < B and A = C, then C < B, leading to incorrect ordering.

Given the small size of the array (<=8), we replace the library sort function with a simple insertion sort that properly ignores invalid elements and sorts valid ones based on latency. This change ensures correct ordering of the C-state latencies.

Fixes 65ea8f2c6e23 ("ACPI: processor idle: Fix up C-state latency if not ordered")

---
I do not have the appropriate AMD hardware to reproduce this issue and test the patch. However, if the aforementioned reason is indeed the source of the problem, I believe this patch might help.

 drivers/acpi/processor_idle.c | 33 ++++++++++++---------------------
 1 file changed, 12 insertions(+), 21 deletions(-)
drivers/acpi/processor_idle.c +12 -21
index bd6a7857ce05..d58a7c64d80b 100644
@@ -386,25 +386,19 @@ static void acpi_processor_power_verify_c3(struct acpi_processor *pr,
 	acpi_write_bit_register(ACPI_BITREG_BUS_MASTER_RLD, 1);
 }
 
-static int acpi_cst_latency_cmp(const void *a, const void *b)
+static void acpi_cst_latency_sort(struct acpi_processor_cx *arr, size_t length)
 {
-	const struct acpi_processor_cx *x = a, *y = b;
+	int i, j, k;
 
-	if (!(x->valid && y->valid))
-		return 0;
-	if (x->latency > y->latency)
-		return 1;
-	if (x->latency < y->latency)
-		return -1;
-	return 0;
-}
-static void acpi_cst_latency_swap(void *a, void *b, int n)
-{
-	struct acpi_processor_cx *x = a, *y = b;
-
-	if (!(x->valid && y->valid))
-		return;
-	swap(x->latency, y->latency);
+	for (i = 1; i < length; i++) {
+		for (j = i - 1, k = i; j >= 0; j--) {
+			if (!arr[j].valid)
+				continue;
+			if (arr[j].latency > arr[k].latency)
+				swap(arr[j].latency, arr[k].latency);
+			k = j;
+		}
+	}
 }
 
 static int acpi_processor_power_verify(struct acpi_processor *pr)
@@ -449,10 +443,7 @@ static int acpi_processor_power_verify(struct acpi_processor *pr)
 
 	if (buggy_latency) {
 		pr_notice("FW issue: working around C-state latencies out of order\n");
-		sort(&pr->power.states[1], max_cstate,
-		     sizeof(struct acpi_processor_cx),
-		     acpi_cst_latency_cmp,
-		     acpi_cst_latency_swap);
+		acpi_cst_latency_sort(&pr->power.states[1], max_cstate);
 	}
 
 	lapic_timer_propagate_broadcast(pr);
Signature · 1 line
2.34.1
#9 lore raw

Re: [PATCH] ACPI: processor_idle: Fix invalid comparison with insertion sort for latency

+ [email protected]

Quoted 80 lines · Kuan-Wei Chiu

The acpi_cst_latency_cmp comparison function currently used for sorting C-state latencies does not satisfy transitivity, causing incorrect sorting results. Specifically, if there are two valid acpi_processor_cx elements A and B and one invalid element C, it may occur that A < B, A = C, and B = C. Sorting algorithms assume that if A < B and A = C, then C < B, leading to incorrect ordering.

Given the small size of the array (<=8), we replace the library sort function with a simple insertion sort that properly ignores invalid elements and sorts valid ones based on latency. This change ensures correct ordering of the C-state latencies.

Fixes 65ea8f2c6e23 ("ACPI: processor idle: Fix up C-state latency if not ordered")

---
I do not have the appropriate AMD hardware to reproduce this issue and test the patch. However, if the aforementioned reason is indeed the source of the problem, I believe this patch might help.

 drivers/acpi/processor_idle.c | 33 ++++++++++++---------------------
 1 file changed, 12 insertions(+), 21 deletions(-)
drivers/acpi/processor_idle.c +12 -21
index bd6a7857ce05..d58a7c64d80b 100644
@@ -386,25 +386,19 @@ static void acpi_processor_power_verify_c3(struct acpi_processor *pr,
 	acpi_write_bit_register(ACPI_BITREG_BUS_MASTER_RLD, 1);
 }
 
-static int acpi_cst_latency_cmp(const void *a, const void *b)
+static void acpi_cst_latency_sort(struct acpi_processor_cx *arr, size_t length)
 {
-	const struct acpi_processor_cx *x = a, *y = b;
+	int i, j, k;
 
-	if (!(x->valid && y->valid))
-		return 0;
-	if (x->latency > y->latency)
-		return 1;
-	if (x->latency < y->latency)
-		return -1;
-	return 0;
-}
-static void acpi_cst_latency_swap(void *a, void *b, int n)
-{
-	struct acpi_processor_cx *x = a, *y = b;
-
-	if (!(x->valid && y->valid))
-		return;
-	swap(x->latency, y->latency);
+	for (i = 1; i < length; i++) {
+		for (j = i - 1, k = i; j >= 0; j--) {
+			if (!arr[j].valid)
+				continue;
+			if (arr[j].latency > arr[k].latency)
+				swap(arr[j].latency, arr[k].latency);
+			k = j;
+		}
+	}
 }
 
 static int acpi_processor_power_verify(struct acpi_processor *pr)
@@ -449,10 +443,7 @@ static int acpi_processor_power_verify(struct acpi_processor *pr)
 
 	if (buggy_latency) {
 		pr_notice("FW issue: working around C-state latencies out of order\n");
-		sort(&pr->power.states[1], max_cstate,
-		     sizeof(struct acpi_processor_cx),
-		     acpi_cst_latency_cmp,
-		     acpi_cst_latency_swap);
+		acpi_cst_latency_sort(&pr->power.states[1], max_cstate);
 	}
 
 	lapic_timer_propagate_broadcast(pr);
Signature · 1 line
2.34.1
#10 lore raw

PATCH v2 1/1 ACPI: processor_idle: Fix invalid comparison with insertion sort for latency

The acpi_cst_latency_cmp comparison function currently used for sorting C-state latencies does not satisfy transitivity, causing incorrect sorting results. Specifically, if there are two valid acpi_processor_cx elements A and B and one invalid element C, it may occur that A < B, A = C, and B = C. Sorting algorithms assume that if A < B and A = C, then C < B, leading to incorrect ordering.

Given the small size of the array (<=8), we replace the library sort function with a simple insertion sort that properly ignores invalid elements and sorts valid ones based on latency. This change ensures correct ordering of the C-state latencies.

Fixes 65ea8f2c6e23 ("ACPI: processor idle: Fix up C-state latency if not ordered")

---
v1 -> v2:
- Avoid swapping if arr[i] is an invalid element.

I do not have the appropriate AMD hardware to reproduce this issue and test the patch. However, if the aforementioned reason is indeed the source of the problem, I believe this patch might help.

 drivers/acpi/processor_idle.c | 35 ++++++++++++++---------------------
 1 file changed, 14 insertions(+), 21 deletions(-)
drivers/acpi/processor_idle.c +14 -21
index bd6a7857ce05..813c718b9108 100644
@@ -386,25 +386,21 @@ static void acpi_processor_power_verify_c3(struct acpi_processor *pr,
 	acpi_write_bit_register(ACPI_BITREG_BUS_MASTER_RLD, 1);
 }
 
-static int acpi_cst_latency_cmp(const void *a, const void *b)
+static void acpi_cst_latency_sort(struct acpi_processor_cx *arr, size_t length)
 {
-	const struct acpi_processor_cx *x = a, *y = b;
+	int i, j, k;
 
-	if (!(x->valid && y->valid))
-		return 0;
-	if (x->latency > y->latency)
-		return 1;
-	if (x->latency < y->latency)
-		return -1;
-	return 0;
-}
-static void acpi_cst_latency_swap(void *a, void *b, int n)
-{
-	struct acpi_processor_cx *x = a, *y = b;
-
-	if (!(x->valid && y->valid))
-		return;
-	swap(x->latency, y->latency);
+	for (i = 1; i < length; i++) {
+		if (!arr[i].valid)
+			continue;
+		for (j = i - 1, k = i; j >= 0; j--) {
+			if (!arr[j].valid)
+				continue;
+			if (arr[j].latency > arr[k].latency)
+				swap(arr[j].latency, arr[k].latency);
+			k = j;
+		}
+	}
 }
 
 static int acpi_processor_power_verify(struct acpi_processor *pr)
@@ -449,10 +445,7 @@ static int acpi_processor_power_verify(struct acpi_processor *pr)
 
 	if (buggy_latency) {
 		pr_notice("FW issue: working around C-state latencies out of order\n");
-		sort(&pr->power.states[1], max_cstate,
-		     sizeof(struct acpi_processor_cx),
-		     acpi_cst_latency_cmp,
-		     acpi_cst_latency_swap);
+		acpi_cst_latency_sort(&pr->power.states[1], max_cstate);
 	}
 
 	lapic_timer_propagate_broadcast(pr);
Signature · 1 line
2.34.1
maintainer
#11 lore raw

Re: [PATCH v2] ACPI: processor_idle: Fix invalid comparison with insertion sort for latency

Quoted 86 lines · Kuan-Wei Chiu

The acpi_cst_latency_cmp comparison function currently used for sorting C-state latencies does not satisfy transitivity, causing incorrect sorting results. Specifically, if there are two valid acpi_processor_cx elements A and B and one invalid element C, it may occur that A < B, A = C, and B = C. Sorting algorithms assume that if A < B and A = C, then C < B, leading to incorrect ordering.

Given the small size of the array (<=8), we replace the library sort function with a simple insertion sort that properly ignores invalid elements and sorts valid ones based on latency. This change ensures correct ordering of the C-state latencies.

Fixes 65ea8f2c6e23 ("ACPI: processor idle: Fix up C-state latency if not ordered")

---
v1 -> v2:
- Avoid swapping if arr[i] is an invalid element.

I do not have the appropriate AMD hardware to reproduce this issue and test the patch. However, if the aforementioned reason is indeed the source of the problem, I believe this patch might help.

 drivers/acpi/processor_idle.c | 35 ++++++++++++++---------------------
 1 file changed, 14 insertions(+), 21 deletions(-)
drivers/acpi/processor_idle.c +14 -21
index bd6a7857ce05..813c718b9108 100644
@@ -386,25 +386,21 @@ static void acpi_processor_power_verify_c3(struct acpi_processor *pr,
 	acpi_write_bit_register(ACPI_BITREG_BUS_MASTER_RLD, 1);
 }
 
-static int acpi_cst_latency_cmp(const void *a, const void *b)
+static void acpi_cst_latency_sort(struct acpi_processor_cx *arr, size_t length)
 {
-	const struct acpi_processor_cx *x = a, *y = b;
+	int i, j, k;
 
-	if (!(x->valid && y->valid))
-		return 0;
-	if (x->latency > y->latency)
-		return 1;
-	if (x->latency < y->latency)
-		return -1;
-	return 0;
-}
-static void acpi_cst_latency_swap(void *a, void *b, int n)
-{
-	struct acpi_processor_cx *x = a, *y = b;
-
-	if (!(x->valid && y->valid))
-		return;
-	swap(x->latency, y->latency);
+	for (i = 1; i < length; i++) {
+		if (!arr[i].valid)
+			continue;
+		for (j = i - 1, k = i; j >= 0; j--) {
+			if (!arr[j].valid)
+				continue;
+			if (arr[j].latency > arr[k].latency)
+				swap(arr[j].latency, arr[k].latency);
+			k = j;
+		}
+	}
 }
 
 static int acpi_processor_power_verify(struct acpi_processor *pr)
@@ -449,10 +445,7 @@ static int acpi_processor_power_verify(struct acpi_processor *pr)
 
 	if (buggy_latency) {
 		pr_notice("FW issue: working around C-state latencies out of order\n");
-		sort(&pr->power.states[1], max_cstate,
-		     sizeof(struct acpi_processor_cx),
-		     acpi_cst_latency_cmp,
-		     acpi_cst_latency_swap);
+		acpi_cst_latency_sort(&pr->power.states[1], max_cstate);
 	}
 
 	lapic_timer_propagate_broadcast(pr);
Signature · 1 line
2.34.1

Hi,

This is the friendly patch-bot of Greg Kroah-Hartman. You have sent him a patch that has triggered this response. He used to manually respond to these common problems, but in order to save his sanity (he kept writing the same thing over and over, yet to different people), I was created. Hopefully you will not take offence and will fix the problem in your patch and resubmit it so that it can be accepted into the Linux kernel tree.

You are receiving this message because of the following common error(s) as indicated below:

- You have marked a patch with a "Fixes:" tag for a commit that is in an older released kernel, yet you do not have a cc: stable line in the signed-off-by area at all, which means that the patch will not be applied to any older kernel releases. To properly fix this, please follow the documented rules in the Documentation/process/stable-kernel-rules.rst file for how to resolve this.

If you wish to discuss this problem further, or you have questions about how to resolve this issue, please feel free to respond to this email and Greg will reply once he has dug out from the pending patches received from other developers.

thanks,

greg k-h's patch email bot

#12 lore raw

Re: [PATCH v2] ACPI: processor_idle: Fix invalid comparison with insertion sort for latency

In reply to Kuan-Wei Chiu
Quoted 16 lines · Kuan-Wei Chiu

The acpi_cst_latency_cmp comparison function currently used for sorting C-state latencies does not satisfy transitivity, causing incorrect sorting results. Specifically, if there are two valid acpi_processor_cx elements A and B and one invalid element C, it may occur that A < B, A = C, and B = C. Sorting algorithms assume that if A < B and A = C, then C < B, leading to incorrect ordering.

Given the small size of the array (<=8), we replace the library sort function with a simple insertion sort that properly ignores invalid elements and sorts valid ones based on latency. This change ensures correct ordering of the C-state latencies.

Fixes 65ea8f2c6e23 ("ACPI: processor idle: Fix up C-state latency if not ordered")
Quoted 6 lines

---
v1 -> v2:
- Avoid swapping if arr[i] is an invalid element.

I do not have the appropriate AMD hardware to reproduce this issue and test the patch.

Even if you had hardware, the behavior stems from a BIOS bug with the _CST entries. I know it's been fixed in the BIOS on most platforms in that era, but if I recall correctly from a few years back Julian's system was EoL already.

Quoted 2 lines

However, if the aforementioned reason is indeed the source of the problem, I believe this patch might help.

Thanks!

Assuming this patch works for Julian, I believe you can also drop the #include <linux/sort.h>

from this file as well.

I do think this should be cc to @stable too in that case.

Quoted 59 lines
  drivers/acpi/processor_idle.c | 35 ++++++++++++++---------------------
  1 file changed, 14 insertions(+), 21 deletions(-)
drivers/acpi/processor_idle.c +14 -21
index bd6a7857ce05..813c718b9108 100644
@@ -386,25 +386,21 @@ static void acpi_processor_power_verify_c3(struct acpi_processor *pr,
  	acpi_write_bit_register(ACPI_BITREG_BUS_MASTER_RLD, 1);
  }
 
-static int acpi_cst_latency_cmp(const void *a, const void *b)
+static void acpi_cst_latency_sort(struct acpi_processor_cx *arr, size_t length)
  {
-	const struct acpi_processor_cx *x = a, *y = b;
+	int i, j, k;
 
-	if (!(x->valid && y->valid))
-		return 0;
-	if (x->latency > y->latency)
-		return 1;
-	if (x->latency < y->latency)
-		return -1;
-	return 0;
-}
-static void acpi_cst_latency_swap(void *a, void *b, int n)
-{
-	struct acpi_processor_cx *x = a, *y = b;
-
-	if (!(x->valid && y->valid))
-		return;
-	swap(x->latency, y->latency);
+	for (i = 1; i < length; i++) {
+		if (!arr[i].valid)
+			continue;
+		for (j = i - 1, k = i; j >= 0; j--) {
+			if (!arr[j].valid)
+				continue;
+			if (arr[j].latency > arr[k].latency)
+				swap(arr[j].latency, arr[k].latency);
+			k = j;
+		}
+	}
  }
 
  static int acpi_processor_power_verify(struct acpi_processor *pr)
@@ -449,10 +445,7 @@ static int acpi_processor_power_verify(struct acpi_processor *pr)
 
  	if (buggy_latency) {
  		pr_notice("FW issue: working around C-state latencies out of order\n");
-		sort(&pr->power.states[1], max_cstate,
-		     sizeof(struct acpi_processor_cx),
-		     acpi_cst_latency_cmp,
-		     acpi_cst_latency_swap);
+		acpi_cst_latency_sort(&pr->power.states[1], max_cstate);
  	}
 
  	lapic_timer_propagate_broadcast(pr);
#13 lore raw

PATCH v3 1/1 ACPI: processor_idle: Fix invalid comparison with insertion sort for latency

The acpi_cst_latency_cmp comparison function currently used for sorting C-state latencies does not satisfy transitivity, causing incorrect sorting results. Specifically, if there are two valid acpi_processor_cx elements A and B and one invalid element C, it may occur that A < B, A = C, and B = C. Sorting algorithms assume that if A < B and A = C, then C < B, leading to incorrect ordering.

Given the small size of the array (<=8), we replace the library sort function with a simple insertion sort that properly ignores invalid elements and sorts valid ones based on latency. This change ensures correct ordering of the C-state latencies.

Fixes 65ea8f2c6e23 ("ACPI: processor idle: Fix up C-state latency if not ordered")

---
v2 -> v3:
- Remove #include <linux/sort.h>
- Cc @stable

Note: I only performed a build test and a simple unit test to ensure
the latency of valid elements is correctly sorted in the randomly
generated data.

 drivers/acpi/processor_idle.c | 36 ++++++++++++++---------------------
 1 file changed, 14 insertions(+), 22 deletions(-)
drivers/acpi/processor_idle.c +14 -22
index bd6a7857ce05..17cc81340b4b 100644
@@ -16,7 +16,6 @@
 #include <linux/acpi.h>
 #include <linux/dmi.h>
 #include <linux/sched.h>       /* need_resched() */
-#include <linux/sort.h>
 #include <linux/tick.h>
 #include <linux/cpuidle.h>
 #include <linux/cpu.h>
@@ -386,25 +385,21 @@ static void acpi_processor_power_verify_c3(struct acpi_processor *pr,
 	acpi_write_bit_register(ACPI_BITREG_BUS_MASTER_RLD, 1);
 }
 
-static int acpi_cst_latency_cmp(const void *a, const void *b)
+static void acpi_cst_latency_sort(struct acpi_processor_cx *arr, size_t length)
 {
-	const struct acpi_processor_cx *x = a, *y = b;
+	int i, j, k;
 
-	if (!(x->valid && y->valid))
-		return 0;
-	if (x->latency > y->latency)
-		return 1;
-	if (x->latency < y->latency)
-		return -1;
-	return 0;
-}
-static void acpi_cst_latency_swap(void *a, void *b, int n)
-{
-	struct acpi_processor_cx *x = a, *y = b;
-
-	if (!(x->valid && y->valid))
-		return;
-	swap(x->latency, y->latency);
+	for (i = 1; i < length; i++) {
+		if (!arr[i].valid)
+			continue;
+		for (j = i - 1, k = i; j >= 0; j--) {
+			if (!arr[j].valid)
+				continue;
+			if (arr[j].latency > arr[k].latency)
+				swap(arr[j].latency, arr[k].latency);
+			k = j;
+		}
+	}
 }
 
 static int acpi_processor_power_verify(struct acpi_processor *pr)
@@ -449,10 +444,7 @@ static int acpi_processor_power_verify(struct acpi_processor *pr)
 
 	if (buggy_latency) {
 		pr_notice("FW issue: working around C-state latencies out of order\n");
-		sort(&pr->power.states[1], max_cstate,
-		     sizeof(struct acpi_processor_cx),
-		     acpi_cst_latency_cmp,
-		     acpi_cst_latency_swap);
+		acpi_cst_latency_sort(&pr->power.states[1], max_cstate);
 	}
 
 	lapic_timer_propagate_broadcast(pr);
Signature · 1 line
2.34.1
#14 lore raw

Re: [PATCH v3] ACPI: processor_idle: Fix invalid comparison with insertion sort for latency

Quoted 43 lines · Kuan-Wei Chiu

The acpi_cst_latency_cmp comparison function currently used for sorting C-state latencies does not satisfy transitivity, causing incorrect sorting results. Specifically, if there are two valid acpi_processor_cx elements A and B and one invalid element C, it may occur that A < B, A = C, and B = C. Sorting algorithms assume that if A < B and A = C, then C < B, leading to incorrect ordering.

Given the small size of the array (<=8), we replace the library sort function with a simple insertion sort that properly ignores invalid elements and sorts valid ones based on latency. This change ensures correct ordering of the C-state latencies.

Fixes 65ea8f2c6e23 ("ACPI: processor idle: Fix up C-state latency if not ordered")

---
v2 -> v3:
- Remove #include <linux/sort.h>
- Cc @stable

Note: I only performed a build test and a simple unit test to ensure
the latency of valid elements is correctly sorted in the randomly
generated data.

 drivers/acpi/processor_idle.c | 36 ++++++++++++++---------------------
 1 file changed, 14 insertions(+), 22 deletions(-)
drivers/acpi/processor_idle.c +0 -1
index bd6a7857ce05..17cc81340b4b 100644
@@ -16,7 +16,6 @@
 #include <linux/acpi.h>
 #include <linux/dmi.h>
 #include <linux/sched.h>       /* need_resched() */
-#include <linux/sort.h>
 #include <linux/tick.h>
 #include <linux/cpuidle.h>
 #include <linux/cpu.h>

drivers/acpi/processor_idle.c static void acpi_processor_power_verify_c3(struct acpi_processor *pr, · line 388

Quoted 5 lines
drivers/acpi/processor_idle.c +1 -1
@@ -386,25 +385,21 @@ static void acpi_processor_power_verify_c3(struct acpi_processor *pr,
        acpi_write_bit_register(ACPI_BITREG_BUS_MASTER_RLD, 1);
 }
 
-static int acpi_cst_latency_cmp(const void *a, const void *b)
+static void acpi_cst_latency_sort(struct acpi_processor_cx *arr, size_t length)

s/arr/states/ please.

Quoted 12 lines
drivers/acpi/processor_idle.c +1 -9
 {
-       const struct acpi_processor_cx *x = a, *y = b;
+       int i, j, k;
 
-       if (!(x->valid && y->valid))
-               return 0;
-       if (x->latency > y->latency)
-               return 1;
-       if (x->latency < y->latency)
-               return -1;
-       return 0;
-}

drivers/acpi/processor_idle.c static void acpi_processor_power_verify_c3(struct acpi_processor *pr, · line 394

Quoted 10 lines
drivers/acpi/processor_idle.c +3 -7
-static void acpi_cst_latency_swap(void *a, void *b, int n)
-{
-       struct acpi_processor_cx *x = a, *y = b;
-
-       if (!(x->valid && y->valid))
-               return;
-       swap(x->latency, y->latency);
+       for (i = 1; i < length; i++) {
+               if (!arr[i].valid)
+                       continue;

Please add an empty line here (and analogously below).

drivers/acpi/processor_idle.c static void acpi_processor_power_verify_c3(struct acpi_processor *pr, · line 399

Quoted 5 lines
drivers/acpi/processor_idle.c +5 -0
+               for (j = i - 1, k = i; j >= 0; j--) {
+                       if (!arr[j].valid)
+                               continue;
+                       if (arr[j].latency > arr[k].latency)
+                               swap(arr[j].latency, arr[k].latency);

And here.

Quoted 19 lines
drivers/acpi/processor_idle.c +4 -5
+                       k = j;
+               }
+       }
 }
 
 static int acpi_processor_power_verify(struct acpi_processor *pr)
@@ -449,10 +444,7 @@ static int acpi_processor_power_verify(struct acpi_processor *pr)
 
        if (buggy_latency) {
                pr_notice("FW issue: working around C-state latencies out of order\n");
-               sort(&pr->power.states[1], max_cstate,
-                    sizeof(struct acpi_processor_cx),
-                    acpi_cst_latency_cmp,
-                    acpi_cst_latency_swap);
+               acpi_cst_latency_sort(&pr->power.states[1], max_cstate);
        }
 
        lapic_timer_propagate_broadcast(pr);
--
#15 lore raw

PATCH v4 1/1 ACPI: processor_idle: Fix invalid comparison with insertion sort for latency

The acpi_cst_latency_cmp comparison function currently used for sorting C-state latencies does not satisfy transitivity, causing incorrect sorting results. Specifically, if there are two valid acpi_processor_cx elements A and B and one invalid element C, it may occur that A < B, A = C, and B = C. Sorting algorithms assume that if A < B and A = C, then C < B, leading to incorrect ordering.

Given the small size of the array (<=8), we replace the library sort function with a simple insertion sort that properly ignores invalid elements and sorts valid ones based on latency. This change ensures correct ordering of the C-state latencies.

Fixes 65ea8f2c6e23 ("ACPI: processor idle: Fix up C-state latency if not ordered")

---
v3 -> v4:
- Rename the parameter 'arr' to 'states'.
- Add empty lines to enhance readability.

Note: I only performed a build test and a simple unit test to ensure
the latency of valid elements is correctly sorted in the randomly generated data.

 drivers/acpi/processor_idle.c | 37 +++++++++++++++--------------------
 1 file changed, 16 insertions(+), 21 deletions(-)
drivers/acpi/processor_idle.c +16 -21
index bd6a7857ce05..831fa4a12159 100644
@@ -16,7 +16,6 @@
 #include <linux/acpi.h>
 #include <linux/dmi.h>
 #include <linux/sched.h>       /* need_resched() */
-#include <linux/sort.h>
 #include <linux/tick.h>
 #include <linux/cpuidle.h>
 #include <linux/cpu.h>
@@ -386,25 +385,24 @@ static void acpi_processor_power_verify_c3(struct acpi_processor *pr,
 	acpi_write_bit_register(ACPI_BITREG_BUS_MASTER_RLD, 1);
 }
 
-static int acpi_cst_latency_cmp(const void *a, const void *b)
+static void acpi_cst_latency_sort(struct acpi_processor_cx *states, size_t length)
 {
-	const struct acpi_processor_cx *x = a, *y = b;
+	int i, j, k;
 
-	if (!(x->valid && y->valid))
-		return 0;
-	if (x->latency > y->latency)
-		return 1;
-	if (x->latency < y->latency)
-		return -1;
-	return 0;
-}
-static void acpi_cst_latency_swap(void *a, void *b, int n)
-{
-	struct acpi_processor_cx *x = a, *y = b;
+	for (i = 1; i < length; i++) {
+		if (!states[i].valid)
+			continue;
 
-	if (!(x->valid && y->valid))
-		return;
-	swap(x->latency, y->latency);
+		for (j = i - 1, k = i; j >= 0; j--) {
+			if (!states[j].valid)
+				continue;
+
+			if (states[j].latency > states[k].latency)
+				swap(states[j].latency, states[k].latency);
+
+			k = j;
+		}
+	}
 }
 
 static int acpi_processor_power_verify(struct acpi_processor *pr)
@@ -449,10 +447,7 @@ static int acpi_processor_power_verify(struct acpi_processor *pr)
 
 	if (buggy_latency) {
 		pr_notice("FW issue: working around C-state latencies out of order\n");
-		sort(&pr->power.states[1], max_cstate,
-		     sizeof(struct acpi_processor_cx),
-		     acpi_cst_latency_cmp,
-		     acpi_cst_latency_swap);
+		acpi_cst_latency_sort(&pr->power.states[1], max_cstate);
 	}
 
 	lapic_timer_propagate_broadcast(pr);
Signature · 1 line
2.34.1
Tested-by on v4 1/1
#16 lore raw

Re: [PATCH v4] ACPI: processor_idle: Fix invalid comparison with insertion sort for latency

Am 01.07.24 um 22:56 schrieb Kuan-Wei Chiu:

Quoted 17 lines

The acpi_cst_latency_cmp comparison function currently used for sorting C-state latencies does not satisfy transitivity, causing incorrect sorting results. Specifically, if there are two valid acpi_processor_cx elements A and B and one invalid element C, it may occur that A < B, A = C, and B = C. Sorting algorithms assume that if A < B and A = C, then C < B, leading to incorrect ordering.

Given the small size of the array (<=8), we replace the library sort function with a simple insertion sort that properly ignores invalid elements and sorts valid ones based on latency. This change ensures correct ordering of the C-state latencies.

Fixes 65ea8f2c6e23 ("ACPI: processor idle: Fix up C-state latency if not ordered")
Quoted 9 lines

---
v3 -> v4:
- Rename the parameter 'arr' to 'states'.
- Add empty lines to enhance readability.

Note: I only performed a build test and a simple unit test to ensure
the latency of valid elements is correctly sorted in the randomly generated data.

Hello,

thanks for the patch. I have tested this applied on top of Fedora 6.9.7 kernel on my Asus laptop and the message about suspend not reaching the deepest state is gone. Thank you. I wonder whether this will also fix random S3 suspend issues I have been seeing on my 5600x since 6.9 kernel too. I will definitely try.

Best regards,
Julian

Quoted 68 lines
  drivers/acpi/processor_idle.c | 37 +++++++++++++++--------------------
  1 file changed, 16 insertions(+), 21 deletions(-)
drivers/acpi/processor_idle.c +16 -21
index bd6a7857ce05..831fa4a12159 100644
@@ -16,7 +16,6 @@
  #include <linux/acpi.h>
  #include <linux/dmi.h>
  #include <linux/sched.h>       /* need_resched() */
-#include <linux/sort.h>
  #include <linux/tick.h>
  #include <linux/cpuidle.h>
  #include <linux/cpu.h>
@@ -386,25 +385,24 @@ static void acpi_processor_power_verify_c3(struct acpi_processor *pr,
  	acpi_write_bit_register(ACPI_BITREG_BUS_MASTER_RLD, 1);
  }
 
-static int acpi_cst_latency_cmp(const void *a, const void *b)
+static void acpi_cst_latency_sort(struct acpi_processor_cx *states, size_t length)
  {
-	const struct acpi_processor_cx *x = a, *y = b;
+	int i, j, k;
 
-	if (!(x->valid && y->valid))
-		return 0;
-	if (x->latency > y->latency)
-		return 1;
-	if (x->latency < y->latency)
-		return -1;
-	return 0;
-}
-static void acpi_cst_latency_swap(void *a, void *b, int n)
-{
-	struct acpi_processor_cx *x = a, *y = b;
+	for (i = 1; i < length; i++) {
+		if (!states[i].valid)
+			continue;
 
-	if (!(x->valid && y->valid))
-		return;
-	swap(x->latency, y->latency);
+		for (j = i - 1, k = i; j >= 0; j--) {
+			if (!states[j].valid)
+				continue;
+
+			if (states[j].latency > states[k].latency)
+				swap(states[j].latency, states[k].latency);
+
+			k = j;
+		}
+	}
  }
 
  static int acpi_processor_power_verify(struct acpi_processor *pr)
@@ -449,10 +447,7 @@ static int acpi_processor_power_verify(struct acpi_processor *pr)
 
  	if (buggy_latency) {
  		pr_notice("FW issue: working around C-state latencies out of order\n");
-		sort(&pr->power.states[1], max_cstate,
-		     sizeof(struct acpi_processor_cx),
-		     acpi_cst_latency_cmp,
-		     acpi_cst_latency_swap);
+		acpi_cst_latency_sort(&pr->power.states[1], max_cstate);
  	}
 
  	lapic_timer_propagate_broadcast(pr);
#17 lore raw

Re: [PATCH v4] ACPI: processor_idle: Fix invalid comparison with insertion sort for latency

Quoted 23 lines · Julian Sikorski

Am 01.07.24 um 22:56 schrieb Kuan-Wei Chiu:

Quoted 22 lines

The acpi_cst_latency_cmp comparison function currently used for sorting C-state latencies does not satisfy transitivity, causing incorrect sorting results. Specifically, if there are two valid acpi_processor_cx elements A and B and one invalid element C, it may occur that A < B, A = C, and B = C. Sorting algorithms assume that if A < B and A = C, then C < B, leading to incorrect ordering.

Given the small size of the array (<=8), we replace the library sort function with a simple insertion sort that properly ignores invalid elements and sorts valid ones based on latency. This change ensures correct ordering of the C-state latencies.

Fixes 65ea8f2c6e23 ("ACPI: processor idle: Fix up C-state latency if not ordered")

---
v3 -> v4:
- Rename the parameter 'arr' to 'states'.
- Add empty lines to enhance readability.

Quoted 8 lines
Quoted 4 lines

Note: I only performed a build test and a simple unit test to ensure the latency of valid elements is correctly sorted in the randomly generated data.

Hello,

thanks for the patch. I have tested this applied on top of Fedora 6.9.7 kernel on my Asus laptop and the message about suspend not reaching the deepest state is gone. Thank you.

That's great news.

Quoted 1 line

I wonder whether this will also fix random S3 suspend issues I have been seeing on my 5600x since 6.9 kernel too. I will definitely try.

Does your 5600x also sort C states? You'll see message in the logs. If so yes it could help. If not; you probably will need to bisect that separately.

Quoted 72 lines

Best regards,
Julian

Quoted 65 lines

  drivers/acpi/processor_idle.c | 37 +++++++++++++++--------------------

  1 file changed, 16 insertions(+), 21 deletions(-)
drivers/acpi/processor_idle.c +16 -21
index bd6a7857ce05..831fa4a12159 100644
@@ -16,7 +16,6 @@
   #include <linux/acpi.h>
   #include <linux/dmi.h>
   #include <linux/sched.h>       /* need_resched() */
-#include <linux/sort.h>
   #include <linux/tick.h>
   #include <linux/cpuidle.h>
   #include <linux/cpu.h>
@@ -386,25 +385,24 @@ static void 
 acpi_processor_power_verify_c3(struct acpi_processor *pr,
       acpi_write_bit_register(ACPI_BITREG_BUS_MASTER_RLD, 1);
   }
-static int acpi_cst_latency_cmp(const void *a, const void *b)
+static void acpi_cst_latency_sort(struct acpi_processor_cx *states, 
 size_t length)
   {
-    const struct acpi_processor_cx *x = a, *y = b;
+    int i, j, k;
-    if (!(x->valid && y->valid))
-        return 0;
-    if (x->latency > y->latency)
-        return 1;
-    if (x->latency < y->latency)
-        return -1;
-    return 0;
-}
-static void acpi_cst_latency_swap(void *a, void *b, int n)
-{
-    struct acpi_processor_cx *x = a, *y = b;
+    for (i = 1; i < length; i++) {
+        if (!states[i].valid)
+            continue;
-    if (!(x->valid && y->valid))
-        return;
-    swap(x->latency, y->latency);
+        for (j = i - 1, k = i; j >= 0; j--) {
+            if (!states[j].valid)
+                continue;
+
+            if (states[j].latency > states[k].latency)
+                swap(states[j].latency, states[k].latency);
+
+            k = j;
+        }
+    }
   }
   static int acpi_processor_power_verify(struct acpi_processor *pr)
@@ -449,10 +447,7 @@ static int acpi_processor_power_verify(struct 
 acpi_processor *pr)
       if (buggy_latency) {
           pr_notice("FW issue: working around C-state latencies out of order\n");
-        sort(&pr->power.states[1], max_cstate,
-             sizeof(struct acpi_processor_cx),
-             acpi_cst_latency_cmp,
-             acpi_cst_latency_swap);
+        acpi_cst_latency_sort(&pr->power.states[1], max_cstate);
       }
       lapic_timer_propagate_broadcast(pr);
maintainer Applied
#18 lore raw

Re: [PATCH v4] ACPI: processor_idle: Fix invalid comparison with insertion sort for latency

In reply to Kuan-Wei Chiu
Quoted 86 lines · Kuan-Wei Chiu

The acpi_cst_latency_cmp comparison function currently used for sorting C-state latencies does not satisfy transitivity, causing incorrect sorting results. Specifically, if there are two valid acpi_processor_cx elements A and B and one invalid element C, it may occur that A < B, A = C, and B = C. Sorting algorithms assume that if A < B and A = C, then C < B, leading to incorrect ordering.

Given the small size of the array (<=8), we replace the library sort function with a simple insertion sort that properly ignores invalid elements and sorts valid ones based on latency. This change ensures correct ordering of the C-state latencies.

Fixes 65ea8f2c6e23 ("ACPI: processor idle: Fix up C-state latency if not ordered")

---
v3 -> v4:
- Rename the parameter 'arr' to 'states'.
- Add empty lines to enhance readability.

Note: I only performed a build test and a simple unit test to ensure
the latency of valid elements is correctly sorted in the randomly generated data.

 drivers/acpi/processor_idle.c | 37 +++++++++++++++--------------------
 1 file changed, 16 insertions(+), 21 deletions(-)
drivers/acpi/processor_idle.c +15 -17
index bd6a7857ce05..831fa4a12159 100644
@@ -16,7 +16,6 @@
 #include <linux/acpi.h>
 #include <linux/dmi.h>
 #include <linux/sched.h>       /* need_resched() */
-#include <linux/sort.h>
 #include <linux/tick.h>
 #include <linux/cpuidle.h>
 #include <linux/cpu.h>
@@ -386,25 +385,24 @@ static void acpi_processor_power_verify_c3(struct acpi_processor *pr,
        acpi_write_bit_register(ACPI_BITREG_BUS_MASTER_RLD, 1);
 }
 
-static int acpi_cst_latency_cmp(const void *a, const void *b)
+static void acpi_cst_latency_sort(struct acpi_processor_cx *states, size_t length)
 {
-       const struct acpi_processor_cx *x = a, *y = b;
+       int i, j, k;
 
-       if (!(x->valid && y->valid))
-               return 0;
-       if (x->latency > y->latency)
-               return 1;
-       if (x->latency < y->latency)
-               return -1;
-       return 0;
-}
-static void acpi_cst_latency_swap(void *a, void *b, int n)
-{
-       struct acpi_processor_cx *x = a, *y = b;
+       for (i = 1; i < length; i++) {
+               if (!states[i].valid)
+                       continue;
 
-       if (!(x->valid && y->valid))
-               return;
-       swap(x->latency, y->latency);
+               for (j = i - 1, k = i; j >= 0; j--) {
+                       if (!states[j].valid)
+                               continue;
+
+                       if (states[j].latency > states[k].latency)
+                               swap(states[j].latency, states[k].latency);
+
+                       k = j;
+               }
+       }
 }
 
 static int acpi_processor_power_verify(struct acpi_processor *pr)
@@ -449,10 +447,7 @@ static int acpi_processor_power_verify(struct acpi_processor *pr)
 
        if (buggy_latency) {

drivers/acpi/processor_idle.c static int acpi_processor_power_verify(struct acpi_processor *pr)

Quoted 10 lines
drivers/acpi/processor_idle.c +1 -5
                pr_notice("FW issue: working around C-state latencies out of order\n");
-               sort(&pr->power.states[1], max_cstate,
-                    sizeof(struct acpi_processor_cx),
-                    acpi_cst_latency_cmp,
-                    acpi_cst_latency_swap);
+               acpi_cst_latency_sort(&pr->power.states[1], max_cstate);
        }
 
        lapic_timer_propagate_broadcast(pr);
--

Applied as 6.10-rc material, thanks!

#20 lore raw

Re: [PATCH 2/2] lib/sort: Optimize heapsort with double-pop variation

(+Cc sound developers)

Hi Luke,

Quoted 11 lines · Luke Jones
Quoted 6 lines · Julian Sikorski

Hello,

it appears that this patch has caused suspend-to-idle regression:

https://gitlab.freedesktop.org/drm/amd/-/issues/3436

Another regression from this has been reported here
https://bugzilla.kernel.org/show_bug.cgi?id=219158

Thank you for reporting this regression!

From a quick look, this seems to be caused by yet another broken compare function. In sound/pci/hda/hda_auto_parser.c, the compare_input_type() function can lead to sorting issues when both is_headset_mic and is_headphone_mic are true for a and b. This can result in a situation where both a < b and b < a hold true, violating the antisymmetry and transitivity required by sort().

Additionally, the comments about "swap" and "don't swap" seem to make incorrect assumptions about how sort() works. Regardless of this optimization patch, sort() may swap a and b without comparing them.

Could you help test the following code? If it works, I'll submit it as an official patch.

Regards,
Kuan-Wei

sound/pci/hda/hda_auto_parser.c +2 -0
index 84393f4f429d..5502ec09b584 100644
@@ -73,6 +73,8 @@ static int compare_input_type(const void *ap, const void *bp)
 		return (int)(a->type - b->type);
 
 	/* If has both hs_mic and hp_mic, pick the hs_mic ahead of hp_mic. */
+	if (a->is_headset_mic && b->is_headset_mic && a->is_headphone_mic && b->is_headphone_mic)
+		return (int)(b->has_boost_on_pin - a->has_boost_on_pin);
 	if (a->is_headset_mic && b->is_headphone_mic)
 		return -1; /* don't swap */
 	else if (a->is_headphone_mic && b->is_headset_mic)