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

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 for Android: free password hash cracker in your pocket

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

Message-ID: <c6f4cca2-9258-4dc9-8d4e-96ab7c587783@leemhuis.info>
Date: Sat, 29 Jun 2024 07:03:59 +0200
From: "Linux regression tracking (Thorsten Leemhuis)"
 <regressions@...mhuis.info>
To: "Rafael J. Wysocki" <rafael@...nel.org>
Cc: akpm@...ux-foundation.org, jserv@...s.ncku.edu.tw,
 linux-kernel@...r.kernel.org, lkml@....org, alexdeucher@...il.com,
 Julian Sikorski <belegdol@...il.com>,
 ACPI Devel Maling List <linux-acpi@...r.kernel.org>,
 Kuan-Wei Chiu <visitorckw@...il.com>,
 Linux regressions mailing list <regressions@...ts.linux.dev>
Subject: Re: [PATCH 2/2] lib/sort: Optimize heapsort with double-pop variation

On 28.06.24 19:10, Kuan-Wei Chiu wrote:
> On Fri, Jun 28, 2024 at 05:15:15PM +0200, Linux regression tracking (Thorsten Leemhuis) wrote:
>> On 20.06.24 17:36, Julian Sikorski wrote:
>>>
>>> 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.
> [...]
> 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.

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

> 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