Use stable sort for ld -r relocs

[Jiong Wang]

Alan Modra writes:

> A number of targets emit multiple relocs at a given r_offset, and
> depend on those relocs staying in their original order.  qsort doesn't
> satisfy this requirement, although it appears from my non-rigorous
> testing that glibc's msort.c implementation may in fact be stable.
>
> I made the mistake of backporting my PR 17666 fix to 2.25.1, thinking
> the code had enough time to settle on mainline, but for anyone with a
> system libc that provides an unstable qsort this will mean 2.25.1
> ld -r may be broken on some targets.
>
> 	PR 18867
> 	* elflink.c (cmp_ext32l_r_offset, cmp_ext32b_r_offset): Delete.
> 	(cmp_ext64l_r_offset, cmp_ext64b_r_offset): Delete.
> 	(ext32l_r_offset, ext32b_r_offset, ext64l_r_offset, ext64b_r_offset):
> 	New functions.
> 	(elf_link_adjust_relocs): Use an insertion sort to sort relocs.
>

Alan,

  After this patch, the linking speed becomes much slower when linking
  AArch64 kernel on x86 cross environment.


  Link time before your patch
  ===
  real	0m1.388s
  user	0m0.893s
  sys	0m0.267s

  after your patch
  ===
  real	3m17.189s
  user	3m16.476s
  sys	0m0.308s

  Below is the simple perf result on the hot functions.

    61.46%  ld-new  libc-2.19.so       [.] __memmove_ssse3_back
    32.24%  ld-new  ld-new             [.] ext64l_r_offset
    5.51%  ld-new  ld-new              [.] elf_link_adjust_relocs

  Could you please have a look at this?
  
  Thanks.

-- 
Regards,
Jiong