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: Windows password security audit tool. GUI, reports in PDF.

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

Message-ID: <Z4euvhAXAiZXCObx@visitorckw-System-Product-Name>
Date: Wed, 15 Jan 2025 20:49:02 +0800
From: Kuan-Wei Chiu <visitorckw@...il.com>
To: Luke Jones <luke@...nes.dev>
Cc: Julian Sikorski <belegdol@...il.com>, akpm@...ux-foundation.org,
	jserv@...s.ncku.edu.tw, linux-kernel@...r.kernel.org, lkml@....org,
	alexdeucher@...il.com, perex@...ex.cz, tiwai@...e.com,
	linux-sound@...r.kernel.org, chuang@...nycu.edu.tw,
	hui.wang@...onical.com
Subject: Re: [PATCH 2/2] lib/sort: Optimize heapsort with double-pop variation

(+Cc sound developers)

Hi Luke,

On Wed, Jan 15, 2025 at 04:27:52PM +1300, Luke Jones wrote:
> On Thu, 2024-06-20 at 17:36 +0200, Julian Sikorski wrote:
> > 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

diff --git a/sound/pci/hda/hda_auto_parser.c b/sound/pci/hda/hda_auto_parser.c
index 84393f4f429d..5502ec09b584 100644
--- a/sound/pci/hda/hda_auto_parser.c
+++ b/sound/pci/hda/hda_auto_parser.c
@@ -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)