[ELF] Add --dwarf32-before-dwarf64 to sort DWARF32 input sections before DWARF64

[ikudrin]

Summary

DWARF64 debug info is suitable for cases when a particular debug section can be larger than 4GiB so that DWARF32 data cannot reference the higher parts of it. An application is usually linked against third-party libraries, and, while a user can control the debug info format of their own files, it can be difficult to enforce the 64-bit format for all inputs. Furthermore, as items of libraries are typically included in the linking after the inputs which reference them, their debug information also tends to be placed in higher positions, heightening the probability to cause the said issue.

The patch adds a switch that can be used to reorder debug info in output sections so that DWARF64 data is placed after DWARF32.

To simplify the implementation, the heuristic is used that all debug info in a single input file is stored in the same format. As the first relocation in a .debug_info section points a record in .debug_abbrev and its type depends on the format, that helps to assume the format of the file where that section belongs.

The patch is based on D91404, where the format was tried to be detected per section. Unfortunately, there are debug sections the used approach does not work on.

There were discussions in various mailing lists concerning the best ways to tackle the issue. There was no final decision achieved.

• https://lists.llvm.org/pipermail/llvm-dev/2020-November/146522.html
• https://sourceware.org/pipermail/binutils/2020-November/114099.html
• https://groups.google.com/g/generic-abi/c/i2Xio-47QdQ/m/RLi53QfaBwAJ

The main advantage of the proposed solution is that it is short, simple, and compatible with existing standards and tools. It does not degrade the performance of the linker for everyone who does not need it, yet resolves the issue in practice for those who come across it.

[MaskRay]

I did not proceed with D91404 was because some replies in the generic-abi thread missed context and we have not entirely lost the possibility to use a section type to distinguish DWARF32/DWARF64. Personally I think how to make DWARF v4/v5 suitable could be a nice standard discussion, as v6 will have years to come.

(
I was frustrated to see that that we just concluded to a linker option without actively seeking for a proper binary format fix, even if Solaris folks could be against section type/flag.
In practice a lot of parties other than non-HPUX non-Solaris have converged on similar toolchains and we could proceed with a GNU flag, e.g.
https://sourceware.org/pipermail/binutils/2020-November/114191.html
)

[ikudrin]

There were so many ideas in the discussion that it looked like they not going to converge. The idea of waiting for v6 does not resolve the issue for existing standards, just postpones the possible solution for years with a yet unknown result. Adding new section names, flags, types, etc., might be promising at the first glance but requires updating lots of tools, including tools in different toolchains, which complicates achieving the result even further. That is why I feel it is necessary to illustrate my proposal with a complete patch, which is aimed to show that a simple, efficient, and standard-compliant solution is possible.

[probinson]

I've re-read a fair amount of the previous llvm-dev thread.
One goal of doing a patch like this was to collect some performance data; do we have that? In particular, performance data comparing link times with the option default-on versus default-off, so we can determine whether the difference is small enough that we should just do this processing unconditionally.

I'm also wondering whether it is reasonable to collect the is-32/64 characteristic of a section "along the way" during some other processing, rather than iterating over all input sections as a separate pass. It would have to be during or after the phase that attaches the reloc section to the input section of course.

lld/ELF/Driver.cpp

2417

Would a TimeTraceScope be helpful here? At least while gathering the initial performance data.

[ayermolo]

From what I remember the discussion went back and forth with no real conclusion. I might be miss remembering, so please correct me if I am wrong.
This patch can be a short/medium term bridge to a more comprehensive solution. If I am understanding it correctly it also deals with a problem of sections like .debug_loc.

[ikudrin]

In D96144#2548663, @probinson wrote:

I've re-read a fair amount of the previous llvm-dev thread.
One goal of doing a patch like this was to collect some performance data; do we have that? In particular, performance data comparing link times with the option default-on versus default-off, so we can determine whether the difference is small enough that we should just do this processing unconditionally.

As a modeling example, I took linking clang, where all LLVM libraries were in the DWARF32 format and clang libraries were DWARF64. The partitioning took about 5ms out of 8,950ms total link times. Such a ratio was expected; there are no time-greedy parts in the partitioning code. Are these the numbers you are asking for?

I'm also wondering whether it is reasonable to collect the is-32/64 characteristic of a section "along the way" during some other processing, rather than iterating over all input sections as a separate pass. It would have to be during or after the phase that attaches the reloc section to the input section of course.

That would require way more string comparisons to find .debug_info input sections in each input file, right? Contrary, this patch does just a few such comparisons over the output sections, assuming that the associated input sections are all of the expected kind.

[ikudrin]

Ping. What should be done to proceed with this?

lld/ELF/Config.h

struct Configuration {
   bool checkSections;
   bool compressDebugSections;
   bool cref;
   std::vector<std::pair<llvm::GlobPattern, uint64_t>> deadRelocInNonAlloc;
   bool defineCommon;
   bool demangle = true;
   bool dependentLibraries;
   bool disableVerify;
+  bool dwarf32BeforeDwarf64;
   bool ehFrameHdr;
   bool emitLLVM;
   bool emitRelocs;
   bool enableNewDtags;
   bool executeOnly;
   bool exportDynamic;
   bool fixCortexA53Errata843419;
   bool fixCortexA8;

lld/ELF/Driver.cpp

if (config->relocatable) {
     if (config->icf != ICFLevel::None)
       error("-r and --icf may not be used together");
     if (config->pie)
       error("-r and -pie may not be used together");
     if (config->exportDynamic)
       error("-r and --export-dynamic may not be used together");
   }
 
+  if (config->dwarf32BeforeDwarf64 && !config->is64)
+    error("--dwarf32-before-dwarf64 is only supported on 64-bit targets");
+
   if (config->executeOnly) {
     if (config->emachine != EM_AARCH64)
       error("-execute-only is only supported on AArch64 targets");
 
     if (config->singleRoRx && !script->hasSectionsCommand)
       error("-execute-only and -no-rosegment cannot be used together");
   }
 
config->callGraphProfileSort = args.hasFlag(
       OPT_call_graph_profile_sort, OPT_no_call_graph_profile_sort, true);
   config->enableNewDtags =
       args.hasFlag(OPT_enable_new_dtags, OPT_disable_new_dtags, true);
   config->entry = args.getLastArgValue(OPT_entry);
 
   errorHandler().errorHandlingScript =
       args.getLastArgValue(OPT_error_handling_script);
 
+  config->dwarf32BeforeDwarf64 = args.hasFlag(
+      OPT_dwarf32_before_dwarf64, OPT_no_dwarf32_before_dwarf64, false);
   config->executeOnly =
       args.hasFlag(OPT_execute_only, OPT_no_execute_only, false);
   config->exportDynamic =
       args.hasFlag(OPT_export_dynamic, OPT_no_export_dynamic, false);
   config->filterList = args::getStrings(args, OPT_filter);
   config->fini = args.getLastArgValue(OPT_fini, "_fini");
   config->fixCortexA53Errata843419 = args.hasArg(OPT_fix_cortex_a53_843419) &&
                                      !args.hasArg(OPT_relocatable);
template <class ELFT> static uint32_t getAndFeatures() {
 
   // Force enable Shadow Stack.
   if (config->zShstk)
     ret |= GNU_PROPERTY_X86_FEATURE_1_SHSTK;
 
   return ret;
 }
 
+template <class ELFT> static bool isDwarf64SectionAux(InputSectionBase *sec) {
+  if (sec->areRelocsRela) {
+    auto &r = sec->relas<ELFT>().front();
+    return r.getType(config->isMips64EL) == target->symbolicRel;
+  } else {
+    auto &r = sec->rels<ELFT>().front();
+    return r.getType(config->isMips64EL) == target->symbolicRel;
+  }
+}
+
+static bool isDwarf64Section(InputSectionBase *sec) {
+  if (sec->numRelocations == 0)
+    return false;
+  switch (config->ekind) {
+  case ELF64LEKind:
+    return isDwarf64SectionAux<ELF64LE>(sec);
+  case ELF64BEKind:
+    return isDwarf64SectionAux<ELF64BE>(sec);
+  default:
+    llvm_unreachable("32-bit is unsupported");
+  }
+}
+
+static void partitionDwarf32AndDwarf64() {
+  if (!config->dwarf32BeforeDwarf64)
+    return;
+
+  // Find input files with DWARF64 debug info.
+  // The heuristic is that the whole debugging information in the file uses the
+  // same format, DWARF32 or DWARF64. The first relocation in a .debug_info
+  // section points to the corresponding record in .debug_abbrev and is
+  // different for DWARF32 and DWARF64, so it can be used to assume the format.
+  DenseSet<InputFile *> dwarf64Files;
+  bool dwarf32FileFound = false;
+  for (BaseCommand *base : script->sectionCommands) {
+    auto *sec = dyn_cast<OutputSection>(base);
+    if (!sec || (sec->flags & SHF_ALLOC) || sec->name != ".debug_info")
+      continue;
+    for (BaseCommand *base : sec->sectionCommands) {
+      auto *cmd = dyn_cast<InputSectionDescription>(base);
+      if (!cmd)
+        continue;
+      for (InputSectionBase *s : cmd->sectionBases) {
+        if (isDwarf64Section(s))
+          dwarf64Files.insert(s->file);
+        else
+          dwarf32FileFound = true;
+      }
+    }
+  }
+  if (dwarf64Files.empty() || !dwarf32FileFound)
+    return;
+
+  // Partition output debug sections so that input sections from files which
+  // assumed to be DWARF64 come after others. We suppose that the linker script
+  // descriptions for output debug sections are not overcomplicated and
+  // partitioning sections within input section descriptions is enough.
+  for (BaseCommand *base : script->sectionCommands) {
+    auto *sec = dyn_cast<OutputSection>(base);
+    if (!sec || (sec->flags & SHF_ALLOC) || !sec->name.startswith(".debug_"))
+      continue;
+    for (BaseCommand *base : sec->sectionCommands) {
+      auto *cmd = dyn_cast<InputSectionDescription>(base);
+      if (!cmd)
+        continue;
+      std::stable_partition(cmd->sectionBases.begin(), cmd->sectionBases.end(),
+                            [&](const InputSectionBase *sec) {
+                              return !dwarf64Files.contains(sec->file);
+                            });
+    }
+  }
+}
+
 // Do actual linking. Note that when this function is called,
 // all linker scripts have already been parsed.
 template <class ELFT> void LinkerDriver::link(opt::InputArgList &args) {
   llvm::TimeTraceScope timeScope("Link", StringRef("LinkerDriver::Link"));
   // If a -hash-style option was not given, set to a default value,
   // which varies depending on the target.
   if (!args.hasArg(OPT_hash_style)) {
     if (config->emachine == EM_MIPS)
if (!config->relocatable)
 
     // Linker scripts control how input sections are assigned to output
     // sections. Input sections that were not handled by scripts are called
     // "orphans", and they are assigned to output sections by the default rule.
     // Process that.
     script->addOrphanSections();
   }
 
+  partitionDwarf32AndDwarf64();
+
   {
     llvm::TimeTraceScope timeScope("Merge/finalize input sections");
 
     // Migrate InputSectionDescription::sectionBases to sections. This includes
     // merging MergeInputSections into a single MergeSyntheticSection. From this
     // point onwards InputSectionDescription::sections should be used instead of
     // sectionBases.
     for (BaseCommand *base : script->sectionCommands)

lld/ELF/Options.td

 def discard_all: F<"discard-all">, HelpText<"Delete all local symbols">;
 
 def discard_locals: F<"discard-locals">,
   HelpText<"Delete temporary local symbols">;
 
 def discard_none: F<"discard-none">,
   HelpText<"Keep all symbols in the symbol table">;
 
+defm dwarf32_before_dwarf64: BB<"dwarf32-before-dwarf64",
+    "Sort DWARF32 sections before DWARF64 sections",
+    "Do not sort DWARF32 sections before DWARF64 sections (default)">;
+
 defm dynamic_linker: Eq<"dynamic-linker", "Which dynamic linker to use">;
 
 defm dynamic_list : Eq<"dynamic-list",
    "Read a list of dynamic symbols. (executable) Put matched non-local defined"
    "symbols to the dynamic symbol table. (shared object) References to matched"
    "non-local STV_DEFAULT symbols shouldn't be bound to definitions within the "
    "shared object. Implies -Bsymbolic but does not set DF_SYMBOLIC">,
    MetaVarName<"<file>">;

lld/test/ELF/dwarf32-before-dwarf64.s

+# REQUIRES: x86
+## Test --dwarf32-before-dwarf64 can order DWARF32 input sections before DWARF64
+## input sections to mitigate out-of-range relocations from DWARF32 input sections.
+
+# RUN: split-file %s %t
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %t/dw32 -o %t32.o
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %t/dw64 -o %t64.o
+
+## By default sections are combined in input order.
+# RUN: ld.lld %t32.o %t64.o --section-start .text=0x100000 -o %tout
+# RUN: llvm-objdump -s -t %tout | FileCheck %s --check-prefixes=CHECK,3264
+# RUN: ld.lld %t64.o %t32.o --section-start .text=0x100000 -o %tout
+# RUN: llvm-objdump -s -t %tout | FileCheck %s --check-prefixes=CHECK,6432
+
+## --dwarf32-before-dwarf64 orders DWARF32 before DWARF64.
+# RUN: ld.lld --dwarf32-before-dwarf64 %t32.o %t64.o --section-start .text=0x100000 -o %tout
+# RUN: llvm-objdump -s -t %tout | FileCheck %s --check-prefixes=CHECK,3264
+# RUN: ld.lld --dwarf32-before-dwarf64 %t64.o %t32.o --section-start .text=0x100000 -o %tout
+# RUN: llvm-objdump -s -t %tout | FileCheck %s --check-prefixes=CHECK,SORT6432
+
+## --no-dwarf32-before-dwarf64 restores the default order.
+# RUN: ld.lld --dwarf32-before-dwarf64 --no-dwarf32-before-dwarf64 %t64.o %t32.o --section-start .text=0x100000 -o %tout
+# RUN: llvm-objdump -s -t %tout | FileCheck %s --check-prefixes=CHECK,6432
+
+## The feature works the same way if debug info sections are defined by a script.
+# RUN: ld.lld --dwarf32-before-dwarf64 -T %t/lds %t64.o %t32.o --section-start .text=0x100000 -o %tout
+# RUN: llvm-objdump -s -t %tout | FileCheck %s --check-prefixes=CHECK,SORT6432
+
+## The order in an executable section follows the input and is not affected
+## by the switch.
+# CHECK:         SYMBOL TABLE:
+# 3264-NEXT:     0000000000100000 {{.*}} _start
+# 3264-NEXT:     0000000000100004 {{.*}} foo
+# 6432-NEXT:     0000000000100000 {{.*}} foo
+# 6432-NEXT:     0000000000100004 {{.*}} _start
+# SORT6432-NEXT: 0000000000100000 {{.*}} foo
+# SORT6432-NEXT: 0000000000100004 {{.*}} _start
+
+## All debug sections in one input file are reckoned to have the same format,
+## DWARF32 or DWARF64, depending on the corresponding .debug_info section.
+# CHECK:        Contents of section .debug_abbrev:
+# 3264-NEXT:     0000 2040
+# 6432-NEXT:     0000 4020
+# SORT6432-NEXT: 0000 2040
+# CHECK:        Contents of section .debug_info:
+# 3264-NEXT:     0000 20000000 00000000 00001000 00000000
+# 3264-NEXT:     0010 40000000 01000000 00000000 04001000
+# 3264-NEXT:     0020 00000000
+# 6432-NEXT:     0000 40000000 00000000 00000000 00001000
+# 6432-NEXT:     0010 00000000 20000000 01000000 04001000
+# 6432-NEXT:     0020 00000000
+# SORT3264-NEXT: 0000 20000000 00000000 04001000 00000000
+# SORT3264-NEXT: 0010 40000000 01000000 00000000 00001000
+# SORT3264-NEXT: 0020 00000000
+
+## Non-debug non-allocatable sections are not sorted by the flag and follow
+## the input order.
+# CHECK:        Contents of section .nondebug:
+# 3264-NEXT:     0000 2040
+# 6432-NEXT:     0000 4020
+# SORT6432-NEXT: 0000 4020
+
+## The flag cannot be used on 32-bit targets.
+# RUN: llvm-mc -filetype=obj -triple=i386 /dev/null -o %t.o
+# RUN: not ld.lld --dwarf32-before-dwarf64 %t.o -o /dev/null 2>&1 | \
+# RUN:   FileCheck %s --check-prefix=32BIT
+
+# 32BIT: error: --dwarf32-before-dwarf64 is only supported on 64-bit targets
+
+#--- dw32
+.globl _start
+_start:
+  nop
+
+## The linker does not analyze the content of debug sections, at least in
+## the scenarios of this test, so we have some fictious values here to help
+## distinguish fake DWARF32 sections from DWARF64 ones.
+.section .debug_abbrev
+  .byte 32
+
+## The first relocation in a .debug_info section points to a corresponding
+## record in .debug_abbrev. It is 32-bit for DWARF32 and 64-bit for DWARF64,
+## so it is used to assess the actual format of the debugging information of
+## the file.
+.section .debug_info,"",@progbits
+  .long 32
+  .long .debug_abbrev
+  .quad _start
+
+.section .nondebug,"",@progbits
+  .byte 32
+
+#--- dw64
+.globl foo
+foo:
+  nop
+
+.section .debug_abbrev
+  .byte 64
+
+.section .debug_info,"",@progbits
+  .long 64
+  .quad .debug_abbrev
+  .quad foo
+
+.section .nondebug,"",@progbits
+  .byte 64
+
+#--- lds
+SECTIONS {
+  .debug_abbrev : { *(.debug_abbrev) }
+  .debug_info : { *(.debug_info) }
+  .nondebug : { *(.nondebug) }
+}