[PATCH] Elf: Adjust compare_link_order for unstable qsort.

[Alan Modra]

On Wed, Dec 15, 2021 at 04:05:41PM -0700, Sandra Loosemore wrote:
> In a cross toolchain for nios2-elf target and x86_64-w64-mingw32 host using
> binutils 2.37, we observed a failure that didn't show up on x86_64-linux-gnu
> host:  testcase pr25490-5.s was failing with
> 
> C:\path\to\nios2-elf-ld.exe: looping in map_segments
> FAIL: __patchable_function_entries section 5
> 
> I tracked this down to the SHF_LINK_ORDER sorting added in commit
> b209b5a6b8a4433be961a0f016439f381de65bfc.  Having run into similar problems
> before, I know that the qsort implementation provided by Windows host is not
> a stable sort, and sure enough, that was what was going wrong here too.

This is a litte weird.  section->id, the current final fallback is
supposed to be unique.  So at first glance it should already be
stable.  Thing is, in this case we're comparing linked_to sections and
it is quite possible for the linked_to sections to be the same for
entries we are trying to sort.  (I had to check under gdb to see all
this..  My initial worry was that section id wasn't unique.)

(gdb) p ((struct bfd_elf_section_data*)os_info->isec[0].is->section->used_by_bfd)->linked_to
$3 = (asection *) 0x55555570b8d8
(gdb) p ((struct bfd_elf_section_data*)os_info->isec[1].is->section->used_by_bfd)->linked_to
$4 = (asection *) 0x55555570b8d8
(gdb) 

>  So
> I made the comparison function work harder to avoid returning 0; it's
> already falling back to using the idx field comparison at an earlier point
> in the function and I think that is exactly what we want to prevent the
> unstable qsort from flipping the order of entries that otherwise compare as
> equal.
> 
> OK for trunk?  Besides testing this in the aforementioned nios2
> cross-toolchain, I also checked that it worked OK on a native
> x86_64-linux-gnu trunk build.
> 
> -Sandra

> commit 4751ef713c65ca8765c9669db5b4320cc4697e1b
> Author: Sandra Loosemore <sandra@codesourcery.com>
> Date:   Wed Dec 15 14:36:36 2021 -0800
> 
>     Elf: Adjust compare_link_order for unstable qsort.
>     
>     2021-12-15  Sandra Loosemore  <sandra@codesourcery.com>
>     
>     	ld/
>     	* ldelfgen.c (compare_link_order): Explicitly keep original
>     	ordering instead of returning 0 if all else fails.
> 
> diff --git a/ld/ldelfgen.c b/ld/ldelfgen.c
> index c456d47..2a28827 100644
> --- a/ld/ldelfgen.c
> +++ b/ld/ldelfgen.c
> @@ -191,8 +191,14 @@ compare_link_order (const void *a, const void *b)
>      return -1;
>    else if (apos > bpos)
>      return 1;
> -
> -  return asec->id - bsec->id;
> +  else if (asec->id < bsec->id)
> +    return -1;
> +  else if (asec->id > bsec->id)
> +    return 1;
> +  else

Please remove all of the above id comparisons, replacing with the idx
comparison below.  OK with that change.

> +    /* Preserve existing ordering if all else fails; qsort may not be
> +       stable so do not just return 0 here.  */
> +    return ai->idx - bi->idx;
>  }
>  
>  /* Rearrange sections with SHF_LINK_ORDER into the same order as their


-- 
Alan Modra
Australia Development Lab, IBM