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);
On 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);
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 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!
linux-stable-mirror@lists.linaro.org
-
Julian Sikorski -
Kuan-Wei Chiu -
Mario Limonciello -
Rafael J. Wysocki