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

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [thread-next>] [day] [month] [year] [list]

Date: Mon, 1 Jul 2024 07:06:14 +0200
From: Greg KH <gregkh@...uxfoundation.org>
To: Kuan-Wei Chiu <visitorckw@...il.com>
Cc: rafael@...nel.org, lenb@...nel.org, mario.limonciello@....com,
	akpm@...ux-foundation.org, jserv@...s.ncku.edu.tw,
	alexdeucher@...il.com, belegdol@...il.com,
	regressions@...mhuis.info, linux-acpi@...r.kernel.org,
	regressions@...ts.linux.dev, linux-kernel@...r.kernel.org
Subject: Re: [PATCH v2] ACPI: processor_idle: Fix invalid comparison with
 insertion sort for latency

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@...il.com>
> Closes: https://lore.kernel.org/lkml/70674dc7-5586-4183-8953-8095567e73df@gmail.com/
> Signed-off-by: Kuan-Wei Chiu <visitorckw@...il.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