excessive slowdown linking RISCV with --gc-sections

[nickdesaulniers]

Reported-by: Palmer Dabbelt palmer@dabbelt.com
via: https://lore.kernel.org/linux-riscv/mhng-57559277-afaa-4a85-a3ad-b9be6dba737f@palmer-ri-x1c9/

If I apply that patchset to mainline, then build allyesconfig, it seems to take hours to link the RISCV kernel.

$ ARCH=riscv LLVM=1 make -j128 vmlinux

$ perf record -e cycles ld.lld -melf64lriscv -z noexecstack -r -o vmlinux.o  --whole-archive vmlinux.a --no-whole-archive --start-group ./drivers/firmware/efi/libstub/lib.a --end-group
$ perf report --no-children --sort=dso,symbol
Overhead  Shared Object         Symbol
  61.64%  lld                   [.] lld::elf::LinkerScript::addOrphanSections()::$_0::operator()
  34.63%  lld                   [.] lld::elf::InputSectionBase::getLinkOrderDep
   3.00%  lld                   [.] lld::elf::SectionBase::getOutputSection
   0.05%  libc.so.6             [.] __strlen_avx2

@nathanchance suggested adding a patch on top:

diff --git a/init/Kconfig b/init/Kconfig
index 32c24950c4ce..25434cbd2a6e 100644
--- a/init/Kconfig
+++ b/init/Kconfig
@@ -1388,7 +1388,7 @@ config HAVE_LD_DEAD_CODE_DATA_ELIMINATION
 config LD_DEAD_CODE_DATA_ELIMINATION
 	bool "Dead code and data elimination (EXPERIMENTAL)"
 	depends on HAVE_LD_DEAD_CODE_DATA_ELIMINATION
-	depends on EXPERT
+	depends on EXPERT && !COMPILE_TEST
 	depends on $(cc-option,-ffunction-sections -fdata-sections)
 	depends on $(ld-option,--gc-sections)
 	help

or:

If you wanted to restrict it to just LD_IS_BFD in arch/riscv/Kconfig,
that would be fine with me too.

  select HAVE_LD_DEAD_CODE_DATA_ELIMINATION if LD_IS_BFD

cc @palmer-dabbelt @MaskRay @nathanchance

[palmer-dabbelt]

I'm fine taking the !COMPILE_TEST (or whatever keep this out of allyesconfig and randconfig and such). Having it as narrow as we can seems like the way to go, so if this is RISC-V and LLD only then I'm happy to take something specific to those (or whatever subset is slow).

[nickdesaulniers]

Sent: https://lore.kernel.org/linux-riscv/ZJXTwqZIkXLxXaSi@google.com/

[nickdesaulniers]

FWIW, just logging what the "orphan sections" are:

diff --git a/lld/ELF/LinkerScript.cpp b/lld/ELF/LinkerScript.cpp
index 777f1f2f85f9..958e926042fb 100644
--- a/lld/ELF/LinkerScript.cpp
+++ b/lld/ELF/LinkerScript.cpp
@@ -823,6 +823,7 @@ void LinkerScript::addOrphanSections() {
   auto add = [&](InputSectionBase *s) {
     if (s->isLive() && !s->parent) {
       orphanSections.push_back(s);
+      llvm::errs() << "XXX: " << s->name << "\n";
 
       StringRef name = getOutputSectionName(s);
       if (config->unique) {

produces a repeating spew of:

...
XXX: .text
XXX: .sdata
XXX: .text.squashfs_frag_lookup
XXX: __patchable_function_entries
XXX: .rela.text.squashfs_frag_lookup
XXX: .rela__patchable_function_entries
XXX: .text.squashfs_read_fragment_index_table
XXX: __patchable_function_entries
XXX: .rela.text.squashfs_read_fragment_index_table
XXX: .rela__patchable_function_entries
XXX: .comment
XXX: .llvm_addrsig
XXX: .text
XXX: .text.squashfs_get_id
XXX: __patchable_function_entries
XXX: .rela.text.squashfs_get_id
XXX: .rela__patchable_function_entries
XXX: .text.squashfs_read_id_index_table
XXX: __patchable_function_entries
XXX: .rela.text.squashfs_read_id_index_table
XXX: __jump_table
XXX: .rela__jump_table
XXX: .rela__patchable_function_entries
XXX: __dyndbg
XXX: .rela__dyndbg
XXX: .rodata.str1.1
XXX: .comment
XXX: .llvm_addrsig
XXX: .text
XXX: .text.squashfs_iget
XXX: __patchable_function_entries
XXX: .rela.text.squashfs_iget
XXX: __jump_table
XXX: .rela__jump_table
XXX: .rela__patchable_function_entries
XXX: .sdata
XXX: .text.squashfs_read_inode
XXX: __patchable_function_entries
XXX: .rela.text.squashfs_read_inode
XXX: .rodata.squashfs_read_inode
XXX: .rela.rodata.squashfs_read_inode
XXX: .rela__patchable_function_entries
XXX: __dyndbg
XXX: .rela__dyndbg
XXX: .rodata.str1.1
...

[nickdesaulniers]

arch/riscv/Kconfig
52:	select ARCH_WANT_LD_ORPHAN_WARN if !XIP_KERNEL

So we should be setting --orphan-handling=warn; we're not seeing any warnings, so I'm surprised we're spending so much time processing orphan sections. Perhaps the above list aren't orphans, and LLD is misdiagnosing them as such?

[palmer-dabbelt]

Sent: https://lore.kernel.org/linux-riscv/ZJXTwqZIkXLxXaSi@google.com/

Thanks. I'm trying to sort out some other issue in my staging tree so it might take a bit to get to, but I'll be working this weekend either way so it shouldn't be too long.

[nickdesaulniers]

(This might be related to lld not discarding locals by default as bfd does; -Wl,-X)