On Wed, Jan 22, 2025 at 12:30 PM Arnd Bergmann <arnd@xxxxxxxx> wrote: > > On Wed, Jan 22, 2025, at 19:47, Rong Xu wrote: > > On Tue, Jan 21, 2025 at 1:18 PM Arnd Bergmann <arnd@xxxxxxxx> wrote: > >> > >> On Tue, Jan 21, 2025, at 18:45, Rong Xu wrote: > >> > On Mon, Jan 20, 2025 at 1:29 PM Arnd Bergmann <arnd@xxxxxxxxxx> wrote: > >> > > >> > Yes. The order could be conditional. As a matter of fact, the first > >> > version was conditional. > >> > I changed it based on the reviewer comments to reduce conditions for > >> > more maintainable code. > >> > I would like to work from the ld.bfd side to see if we can fix the problem. > >> > >> Makes sense. At least once we understand what makes the linker so slow > >> and fix future versions, it should also be possible to come up with > >> a more effective workaround for the existing linkers that suffer from it. > > > > @Arnd: Can you send me the instructions to reproduce this regression? > > My report had linked to the config that I saw originally: > > >> > Link: https://pastebin.com/raw/sWpbkapL (config) > > This is for a x86_64 build, and I used 'make savedefconfig' to > simplify it, so you have to copy it to arch/x86/configs/test_defconfig > and run 'make test_defconfig' to get the full file back. > > I have also uploaded a reproducer to > https://drive.google.com/file/d/14xWdD_S51XBgV6kOajLvdtOef7tQTZQq/view?usp=sharing > but it's fairly large. The reproducer is from ld.lld --reproduce=, but > you can simply unpack it and do > > x86_64-linux-gnu-ld.bfd -m elf_x86_64 -z noexecstack --emit-relocs --discard-none -z max-page-size=0x200000 --gc-sections --build-id=sha1 --orphan-handling warn --script home/arnd/arm-soc/build/x86/0xA8B23FFD_defconfig/arch/x86/kernel/vmlinux.lds --strip-debug -o .tmp_vmlinux1 --whole-archive home/arnd/arm-soc/build/x86/0xA8B23FFD_defconfig/vmlinux.a home/arnd/arm-soc/build/x86/0xA8B23FFD_defconfig/init/version-timestamp.o --no-whole-archive --start-group home/arnd/arm-soc/build/x86/0xA8B23FFD_defconfig/lib/lib.a home/arnd/arm-soc/build/x86/0xA8B23FFD_defconfig/arch/x86/lib/lib.a --end-group home/arnd/arm-soc/build/x86/0xA8B23FFD_defconfig/.tmp_vmlinux0.kallsyms.o > > Arnd Thanks Arnd. I can reproduce the issue with your files. The slowdown was caused by the following change in elflink.c: commit fba1ac87dcb76e61f270d236f1e7c8aaec80f9c4 Author: Tomoaki Kawada <kawada@xxxxxxxxxxx> Date: Thu Jun 16 09:54:30 2022 +0000 Fix the sorting algorithm for reloc entries The optimized insertion sort algorithm in `elf_link_adjust_relocs` incorrectly assembled "runs" from unsorted entries and inserted them to an already-sorted prefix, breaking the loop invariants of insertion sort. This commit updates the run assembly loop to break upon encountering a non-monotonic change in the sort key. I haven't looked closely into this. The fix is most likely valid. But the code might not be efficient. -Rong
