This is the mail archive of the mailing list for the binutils project.

Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]
Other format: [Raw text]

Re: Use stable sort for ld -r relocs

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.


  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       [.] __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?


Index Nav: [Date Index] [Subject Index] [Author Index] [Thread Index]
Message Nav: [Date Prev] [Date Next] [Thread Prev] [Thread Next]