This is the mail archive of the
mailing list for the binutils project.
Re: Use stable sort for ld -r relocs
- From: Jiong Wang <jiong dot wang at arm dot com>
- To: Alan Modra <amodra at gmail dot com>
- Cc: "binutils\ at sourceware dot org" <binutils at sourceware dot org>
- Date: Wed, 16 Sep 2015 09:54:54 +0100
- Subject: Re: Use stable sort for ld -r relocs
- Authentication-results: sourceware.org; auth=none
- References: <20150826140258 dot GB24814 at bubble dot grove dot modra dot org> <n99si6fu8kw dot fsf at arm dot com> <20150916084631 dot GF7224 at bubble dot grove dot modra dot org>
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.
>> 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.
> 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.