linux-kernel - Re: [PATCH] [RFC, DO NOT APPLY] vmlinux.lds: revert link speed regression

lists.openwall.net		lists / announce owl-users owl-dev john-users john-dev passwdqc-users yescrypt popa3d-users / oss-security kernel-hardening musl sabotage tlsify passwords / crypt-dev xvendor / Bugtraq Full-Disclosure linux-kernel linux-netdev linux-ext4 linux-hardening linux-cve-announce PHC
Open Source and information security mailing list archives

Hash Suite: Windows password security audit tool. GUI, reports in PDF.

[<prev] [next>] [<thread-prev] [day] [month] [year] [list]

Message-ID: <CAF1bQ=Q+FLu=RYT5tVT0Nrre72w-_sgXMw=sr0MBXhgudbJn4w@mail.gmail.com>
Date: Wed, 22 Jan 2025 14:37:36 -0800
From: Rong Xu <xur@...gle.com>
To: Arnd Bergmann <arnd@...db.de>
Cc: Arnd Bergmann <arnd@...nel.org>, linux-kbuild@...r.kernel.org, 
	Masahiro Yamada <masahiroy@...nel.org>, linux-kernel@...r.kernel.org, 
	regressions@...ts.linux.dev, Han Shen <shenhan@...gle.com>, 
	Nathan Chancellor <nathan@...nel.org>, Kees Cook <kees@...nel.org>, Jann Horn <jannh@...gle.com>, 
	Ard Biesheuvel <ardb@...nel.org>, Linux-Arch <linux-arch@...r.kernel.org>
Subject: Re: [PATCH] [RFC, DO NOT APPLY] vmlinux.lds: revert link speed regression

On Wed, Jan 22, 2025 at 12:30 PM Arnd Bergmann <arnd@...db.de> wrote:
>
> On Wed, Jan 22, 2025, at 19:47, Rong Xu wrote:
> > On Tue, Jan 21, 2025 at 1:18 PM Arnd Bergmann <arnd@...db.de> wrote:
> >>
> >> On Tue, Jan 21, 2025, at 18:45, Rong Xu wrote:
> >> > On Mon, Jan 20, 2025 at 1:29 PM Arnd Bergmann <arnd@...nel.org> 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@...kk.co.jp>
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