Re: Use stable sort for ld -r relocs

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

Jiong Wang writes:

> 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?

Reproduce steps::

Kernel source
===
git clone git://git.kernel.org/pub/scm/linux/kernel/git/torvalds/linux.git

Toolchain binary
===
wget http://releases.linaro.org/15.06/components/toolchain/binaries/4.8/aarch64-linux-gnu/gcc-linaro-4.8-2015.06-x86_64_aarch64-linux-gnu.tar.xz

Build
===
export PATH=LINARO_BINARY_BIN:$PATH
cd linux
make ARCH=arm64 CROSS_COMPILE=aarch64-linux-gnu- defconfig
make ARCH=arm64 CROSS_COMPILE=aarch64-linux-gnu- Image -j10

the final linking command should be:

ld-new -EL -r -o vmlinux.o arch/arm64/kernel/head.o init/built-in.o
--start-group usr/built-in.o arch/arm64/kernel/built-in.o
arch/arm64/mm/built-in.o arch/arm64/net/built-in.o
arch/arm64/kvm/built-in.o arch/arm64/crypto/built-in.o
./drivers/firmware/efi/libstub/lib.a kernel/built-in.o certs/built-in.o
mm/built-in.o fs/built-in.o ipc/built-in.o security/built-in.o
crypto/built-in.o block/built-in.o arch/arm64/lib/lib.a lib/lib.a
arch/arm64/lib/built-in.o lib/built-in.o drivers/built-in.o
sound/built-in.o firmware/built-in.o net/built-in.o --end-group

(or you can get it by "rm vmlinux", and then redo the last step with "V=1"
  make ARCH=arm64 CROSS_COMPILE=aarch64-linux-gnu- Image -j10 V=1)

-- 
Regards,
Jiong