[PATCH] symbols: ensure sorting by value yields reproducible outcome

[PATCH] symbols: ensure sorting by value yields reproducible outcome

[Jan Beulich]

qsort() implementations have freedom towards actions taken when two items
compare equal. The latest with the introduction of fake "end" symbols,
inconsistent sorting between the 1st and 2nd run can lead to extra "end"
symbols in one of the runs, making the resulting symbol table partly
unusable. (Note in particular that --warn-dup or --error-dup are passed
only on the 2nd run, and only for xen.syms, and that option has the effect
of doing a name sort ahead of doing the address sort. I.e. the inputs to
the 2nd qsort() are pretty different between the 1st and 2nd runs.)

Make the result stable by using original order to break ties.

Fixes: d3b637fba31b ("symbols: arrange to know where functions end")
Reported-by: Roger Pau Monné <roger.pau@citrix.com>
Signed-off-by: Jan Beulich <jbeulich@suse.com>
---
I can't exclude the unreliable sorting could have other bad effects, in
which case some much older commit would likely need referencing by Fixes:.

--- a/xen/tools/symbols.c
+++ b/xen/tools/symbols.c
@@ -40,6 +40,7 @@ struct sym_entry {
 	unsigned long long addr;
 	unsigned long size;
 	unsigned int len;
+	unsigned int orig_idx;
 	unsigned char *sym;
 	char *orig_symbol;
 	unsigned int addr_idx;
@@ -247,6 +248,9 @@ static void read_map(FILE *in)
 				exit (1);
 			}
 		}
+
+		table[table_cnt].orig_idx = table_cnt;
+
 		if (read_symbol(in, &table[table_cnt]) == 0)
 			table_cnt++;
 	}
@@ -639,7 +643,11 @@ static int compare_value(const void *p1,
 		return -1;
 	if (isupper(*sym2->sym))
 		return +1;
-	return 0;
+
+	/* Explicitly request "keep original order" otherwise. */
+	if (sym1->orig_idx < sym2->orig_idx)
+		return -1;
+	return sym1->orig_idx > sym2->orig_idx;
 }
 
 static int compare_name(const void *p1, const void *p2)

Re: [PATCH] symbols: ensure sorting by value yields reproducible outcome

[Roger Pau Monné]

On Wed, Jan 21, 2026 at 04:24:43PM +0100, Jan Beulich wrote:
> qsort() implementations have freedom towards actions taken when two items
> compare equal. The latest with the introduction of fake "end" symbols,
> inconsistent sorting between the 1st and 2nd run can lead to extra "end"
> symbols in one of the runs, making the resulting symbol table partly
> unusable. (Note in particular that --warn-dup or --error-dup are passed
> only on the 2nd run, and only for xen.syms, and that option has the effect
> of doing a name sort ahead of doing the address sort. I.e. the inputs to
> the 2nd qsort() are pretty different between the 1st and 2nd runs.)
> 
> Make the result stable by using original order to break ties.
> 
> Fixes: d3b637fba31b ("symbols: arrange to know where functions end")
> Reported-by: Roger Pau Monné <roger.pau@citrix.com>
> Signed-off-by: Jan Beulich <jbeulich@suse.com>

Reviewed-by: Roger Pau Monné <roger.pau@citrix.com>

> ---
> I can't exclude the unreliable sorting could have other bad effects, in
> which case some much older commit would likely need referencing by Fixes:.

Lacking a more clear indicator I'm fine to use the current Fixes
reference.

Thanks, Roger.