Skip to contentSkip to conversation

ALSA: hda: Fix headset detection failure due to unstable sort

PATCH In review Kuan-Wei Chiu 2 participants 2 messages Jan 28, 2025

Subsystems (2)
lore
Share & tools
lore
#0 lore raw

PATCH 1/1 ALSA: hda: Fix headset detection failure due to unstable sort

The auto_parser assumed sort() was stable, but the kernel's sort() uses heapsort, which has never been stable. After commit 0e02ca29a563 ("lib/sort: optimize heapsort with double-pop variation"), the order of equal elements changed, causing the headset to fail to work.

Fix the issue by recording the original order of elements before sorting and using it as a tiebreaker for equal elements in the comparison function.

Fixes b9030a005d58 ("ALSA: hda - Use standard sort function in hda_auto_parser.c")
---
 sound/pci/hda/hda_auto_parser.c | 8 +++++++-
 sound/pci/hda/hda_auto_parser.h | 1 +
 2 files changed, 8 insertions(+), 1 deletion(-)
sound/pci/hda/hda_auto_parser.c +7 -1
index 84393f4f429d..8923813ce424 100644
@@ -80,7 +80,11 @@ static int compare_input_type(const void *ap, const void *bp)
 
 	/* In case one has boost and the other one has not,
 	   pick the one with boost first. */
-	return (int)(b->has_boost_on_pin - a->has_boost_on_pin);
+	if (a->has_boost_on_pin != b->has_boost_on_pin)
+		return (int)(b->has_boost_on_pin - a->has_boost_on_pin);
+
+	/* Keep the original order */
+	return a->order - b->order;
 }
 
 /* Reorder the surround channels
@@ -400,6 +404,8 @@ int snd_hda_parse_pin_defcfg(struct hda_codec *codec,
 	reorder_outputs(cfg->speaker_outs, cfg->speaker_pins);
 
 	/* sort inputs in the order of AUTO_PIN_* type */
+	for (i = 0; i < cfg->num_inputs; i++)
+		cfg->inputs[i].order = i;
 	sort(cfg->inputs, cfg->num_inputs, sizeof(cfg->inputs[0]),
 	     compare_input_type, NULL);
 
sound/pci/hda/hda_auto_parser.h +1 -0
index 579b11beac71..87af3d8c02f7 100644
@@ -37,6 +37,7 @@ struct auto_pin_cfg_item {
 	unsigned int is_headset_mic:1;
 	unsigned int is_headphone_mic:1; /* Mic-only in headphone jack */
 	unsigned int has_boost_on_pin:1;
+	int order;
 };
 
 struct auto_pin_cfg;
Signature · 1 line
2.34.1
#1 lore raw
Quoted 10 lines · Kuan-Wei Chiu

The auto_parser assumed sort() was stable, but the kernel's sort() uses heapsort, which has never been stable. After commit 0e02ca29a563 ("lib/sort: optimize heapsort with double-pop variation"), the order of equal elements changed, causing the headset to fail to work.

Fix the issue by recording the original order of elements before sorting and using it as a tiebreaker for equal elements in the comparison function.

Quoted 6 lines
Fixes b9030a005d58 ("ALSA: hda - Use standard sort function in hda_auto_parser.c")

Applied now. Thanks.

Takashi