drivers/acpi/processor_idle.c | 35 ++++++++++++++--------------------- 1 file changed, 14 insertions(+), 21 deletions(-)
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")
Reported-by: Julian Sikorski <belegdol@gmail.com>
Closes: https://lore.kernel.org/lkml/70674dc7-5586-4183-8953-8095567e73df@gmail.com/
Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
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(-)
diff --git a/drivers/acpi/processor_idle.c b/drivers/acpi/processor_idle.c
index bd6a7857ce05..813c718b9108 100644
--- a/drivers/acpi/processor_idle.c
+++ b/drivers/acpi/processor_idle.c
@@ -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);
--
2.34.1On 6/30/2024 23:42, Kuan-Wei Chiu wrote:
> 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")
> Reported-by: Julian Sikorski <belegdol@gmail.com>
> Closes: https://lore.kernel.org/lkml/70674dc7-5586-4183-8953-8095567e73df@gmail.com/
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> ---
> 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.
> 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.
>
> drivers/acpi/processor_idle.c | 35 ++++++++++++++---------------------
> 1 file changed, 14 insertions(+), 21 deletions(-)
>
> diff --git a/drivers/acpi/processor_idle.c b/drivers/acpi/processor_idle.c
> index bd6a7857ce05..813c718b9108 100644
> --- a/drivers/acpi/processor_idle.c
> +++ b/drivers/acpi/processor_idle.c
> @@ -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);
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")
Cc: stable@vger.kernel.org
Reported-by: Julian Sikorski <belegdol@gmail.com>
Closes: https://lore.kernel.org/lkml/70674dc7-5586-4183-8953-8095567e73df@gmail.com/
Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
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(-)
diff --git a/drivers/acpi/processor_idle.c b/drivers/acpi/processor_idle.c
index bd6a7857ce05..17cc81340b4b 100644
--- a/drivers/acpi/processor_idle.c
+++ b/drivers/acpi/processor_idle.c
@@ -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);
--
2.34.1On Mon, Jul 1, 2024 at 6:10 PM Kuan-Wei Chiu <visitorckw@gmail.com> wrote:
>
> 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")
> Cc: stable@vger.kernel.org
> Reported-by: Julian Sikorski <belegdol@gmail.com>
> Closes: https://lore.kernel.org/lkml/70674dc7-5586-4183-8953-8095567e73df@gmail.com/
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> ---
> 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(-)
>
> diff --git a/drivers/acpi/processor_idle.c b/drivers/acpi/processor_idle.c
> index bd6a7857ce05..17cc81340b4b 100644
> --- a/drivers/acpi/processor_idle.c
> +++ b/drivers/acpi/processor_idle.c
> @@ -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)
s/arr/states/ please.
> {
> - 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;
Please add an empty line here (and analogously below).
> + 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.
> + 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);
> --
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")
Cc: stable@vger.kernel.org
Reported-by: Julian Sikorski <belegdol@gmail.com>
Closes: https://lore.kernel.org/lkml/70674dc7-5586-4183-8953-8095567e73df@gmail.com/
Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
---
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(-)
diff --git a/drivers/acpi/processor_idle.c b/drivers/acpi/processor_idle.c
index bd6a7857ce05..831fa4a12159 100644
--- a/drivers/acpi/processor_idle.c
+++ b/drivers/acpi/processor_idle.c
@@ -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);
--
2.34.1On Mon, Jul 1, 2024 at 10:56 PM Kuan-Wei Chiu <visitorckw@gmail.com> wrote:
>
> 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")
> Cc: stable@vger.kernel.org
> Reported-by: Julian Sikorski <belegdol@gmail.com>
> Closes: https://lore.kernel.org/lkml/70674dc7-5586-4183-8953-8095567e73df@gmail.com/
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> ---
> 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(-)
>
> diff --git a/drivers/acpi/processor_idle.c b/drivers/acpi/processor_idle.c
> index bd6a7857ce05..831fa4a12159 100644
> --- a/drivers/acpi/processor_idle.c
> +++ b/drivers/acpi/processor_idle.c
> @@ -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);
> --
Applied as 6.10-rc material, thanks!
Am 01.07.24 um 22:56 schrieb 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")
> Cc: stable@vger.kernel.org
> Reported-by: Julian Sikorski <belegdol@gmail.com>
> Closes: https://lore.kernel.org/lkml/70674dc7-5586-4183-8953-8095567e73df@gmail.com/
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> ---
> 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
Tested-by: Julian Sikorski <belegdol@gmail.com>
> drivers/acpi/processor_idle.c | 37 +++++++++++++++--------------------
> 1 file changed, 16 insertions(+), 21 deletions(-)
>
> diff --git a/drivers/acpi/processor_idle.c b/drivers/acpi/processor_idle.c
> index bd6a7857ce05..831fa4a12159 100644
> --- a/drivers/acpi/processor_idle.c
> +++ b/drivers/acpi/processor_idle.c
> @@ -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);
On 7/2/2024 2:28, Julian Sikorski wrote:
> Am 01.07.24 um 22:56 schrieb 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")
>> Cc: stable@vger.kernel.org
>> Reported-by: Julian Sikorski <belegdol@gmail.com>
>> Closes:
>> https://lore.kernel.org/lkml/70674dc7-5586-4183-8953-8095567e73df@gmail.com/
>> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
>> ---
>> 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.
That's great news.
> 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.
>
> Best regards,
> Julian
>
> Tested-by: Julian Sikorski <belegdol@gmail.com>
>
>> drivers/acpi/processor_idle.c | 37 +++++++++++++++--------------------
>> 1 file changed, 16 insertions(+), 21 deletions(-)
>>
>> diff --git a/drivers/acpi/processor_idle.c
>> b/drivers/acpi/processor_idle.c
>> index bd6a7857ce05..831fa4a12159 100644
>> --- a/drivers/acpi/processor_idle.c
>> +++ b/drivers/acpi/processor_idle.c
>> @@ -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);
>
On Mon, Jul 01, 2024 at 12:42:32PM +0800, Kuan-Wei Chiu wrote:
> 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")
> Reported-by: Julian Sikorski <belegdol@gmail.com>
> Closes: https://lore.kernel.org/lkml/70674dc7-5586-4183-8953-8095567e73df@gmail.com/
> Signed-off-by: Kuan-Wei Chiu <visitorckw@gmail.com>
> ---
> 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(-)
>
> diff --git a/drivers/acpi/processor_idle.c b/drivers/acpi/processor_idle.c
> index bd6a7857ce05..813c718b9108 100644
> --- a/drivers/acpi/processor_idle.c
> +++ b/drivers/acpi/processor_idle.c
> @@ -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);
> --
> 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
© 2016 - 2025 Red Hat, Inc.