Re: Use stable sort for ld -r relocs

[Jiong Wang <jiong dot wang at arm dot com>]

Alan Modra writes:

> On Tue, Sep 15, 2015 at 01:58:08PM +0100, Jiong Wang wrote:
>> 
>> 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.
>
> I'm tempted to leave the code as is.  I've long said that it is wrong
> for the kernel to use ld -r as a packaging system, and perhaps a
> really slow ld -r would finally force a change.  :)
>
> Anyway, reproduced.  The big slowdown happens with .debug_info, which
> has 4367968 relocs.  Quite a sizeable run of those is out of order due
> to not processing files in order.  (See how elf_link_input_bfd is
> called in elflink.c, and the testcase in pr17666.)

Thanks for the explanation and fix.

linking speed comes back now on my local machine after this.

Regards,
Jiong

>
> I'll commit the following after a bit more testing.
>
> 	PR 18867
> 	* elflink.c (elf_link_adjust_relocs): Modify insertion sort to
> 	insert a run.  Return status in case of malloc failure.
> 	Adjust callers.