RFC: [ELF] Add --dwarf32-before-dwarf64 to place DWARF32 input sections before DWARF64

[MaskRay]

Summary

See https://lists.llvm.org/pipermail/llvm-dev/2020-November/146522.html
"[LLD] Support DWARF64, debug_info "sorting""

If a .debug_* output section S can be larger than 32-bit and its section
offset is referenced by a DWARF32 input section of itself or another .debug_* output section,
S may be subject to 32-bit relocation overflow. If we place such DWARF32
sections before DWARF64 sections, we can likely mitigate overflows.

Parsing DWARF is time consuming, breaks the "smart format, dumb linker" design goal of ELF,
and can get in the way if we eagerly free uncompressed buffers after OutputSection::writeTo.
So we use the relocation idea proposed by Igor Kudrin
https://lists.llvm.org/pipermail/llvm-dev/2020-November/146528.html

In practice, the first relocation of .debug_* is good indicator whether it is a
DWARF64 section, to list a few:

• .debug_info: the first relocation is a .debug_abbrev offset
• .debug_names references .debug_info: the first relocation is a .debug_info offset
• .debug_aranges references .debug_info: the first relocation is a .debug_info offset
• .debug_str_offsets references .debug_str: the first relocation is a .debug_str offset
• ...

This patch adds the partition code to finalizeInputSections so that it works
for both orphan sections and when an output section description for .debug_info
is used. In some sense --dwarf32-before-dwarf64 will behave like
--sort-section: it can affect input section order of a wildcard.

[MaskRay]

lld/ELF/OutputSections.cpp

170

This should be Rel. I'll add a mips64 test.

[jhenderson]

lld/ELF/Options.td

150–151

"place" sounds like the linker isn't allowed to place DWARF32 sections first, but this obviously isn't the behaviour, if users just so happen to place objects in the right order on the command-line. Perhaps "sort" makes it clearer?

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

1

Is there a particular reason this is using ppc rather than the more common X86?

24

Here and below, maybe worth replacing the area patched by relocations with {{.*}} to make the test more robust?

[ikudrin]

Well, this is a bit different from my original idea but is an overall good heuristic for many of the debug sections. It works for .debug_info, which is one of the biggest sections; it does not work for .debug_line, though, which is not that big as .debug_info, but potentially might become problematic in the (distant) future; it also does not work for .debug_abbrev, .debug_addr, .debug_ranges, and some others, which are usually not that big. However, the patch should be extended to support .debug_str, which can be even larger than .debug_info.

[avl]

Well, this is a bit different from my original idea but is an overall good heuristic for many of the debug sections. It works for .debug_info, which is one of the biggest sections; it does not work for .debug_line, though, which is not that big as .debug_info, but potentially might become problematic in the (distant) future; it also does not work for .debug_abbrev, .debug_addr, .debug_ranges, and some others, which are usually not that big. However, the patch should be extended to support .debug_str, which can be even larger than .debug_info.

Would it be useful if decision done for the debug_info section would also be applied to all other debug sections from the same object file?

[MaskRay]

In D91404#2393750, @avl wrote:

Well, this is a bit different from my original idea but is an overall good heuristic for many of the debug sections. It works for .debug_info, which is one of the biggest sections; it does not work for .debug_line, though, which is not that big as .debug_info, but potentially might become problematic in the (distant) future; it also does not work for .debug_abbrev, .debug_addr, .debug_ranges, and some others, which are usually not that big. However, the patch should be extended to support .debug_str, which can be even larger than .debug_info.

Would it be useful if decision done for the debug_info section would also be applied to all other debug sections from the same object file?

In D91404#2393718, @ikudrin wrote:

Well, this is a bit different from my original idea but is an overall good heuristic for many of the debug sections. It works for .debug_info, which is one of the biggest sections; it does not work for .debug_line, though, which is not that big as .debug_info, but potentially might become problematic in the (distant) future; it also does not work for .debug_abbrev, .debug_addr, .debug_ranges, and some others, which are usually not that big. However, the patch should be extended to support .debug_str, which can be even larger than .debug_info.

We either mark InputFile or InputSectionBase referenced by a 64-bit absolute relocation. I prefer InputBaseBase which is more direct (we have spare bits in SectionBase after keepUnique).

DWARF v4 .debug_str is referenced by .debug_info's non-first relocation. The InputSectionBase based referenced bit approach does not work. So maybe we have to use InputFile.

[ayermolo]

In D91404#2394228, @MaskRay wrote:

In D91404#2393750, @avl wrote:

Well, this is a bit different from my original idea but is an overall good heuristic for many of the debug sections. It works for .debug_info, which is one of the biggest sections; it does not work for .debug_line, though, which is not that big as .debug_info, but potentially might become problematic in the (distant) future; it also does not work for .debug_abbrev, .debug_addr, .debug_ranges, and some others, which are usually not that big. However, the patch should be extended to support .debug_str, which can be even larger than .debug_info.

Would it be useful if decision done for the debug_info section would also be applied to all other debug sections from the same object file?

In D91404#2393718, @ikudrin wrote:

Well, this is a bit different from my original idea but is an overall good heuristic for many of the debug sections. It works for .debug_info, which is one of the biggest sections; it does not work for .debug_line, though, which is not that big as .debug_info, but potentially might become problematic in the (distant) future; it also does not work for .debug_abbrev, .debug_addr, .debug_ranges, and some others, which are usually not that big. However, the patch should be extended to support .debug_str, which can be even larger than .debug_info.

We either mark InputFile or InputSectionBase referenced by a 64-bit absolute relocation. I prefer InputBaseBase which is more direct (we have spare bits in SectionBase after keepUnique).

DWARF v4 .debug_str is referenced by .debug_info's non-first relocation. The InputSectionBase based referenced bit approach does not work. So maybe we have to use InputFile.

If I understand this correctly if we store some kind of DWARF64 flag in InputFile, we can still use firstReloc approach.
The assumption is that all the input sections within the file will have the same DWARF pointer width.
Otherwise we have to scan all the relocs and mark corresponding sections where Symbol is pointing as DWARF64.
Correct?

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);

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",
+    "DWARF32 sections before DWARF64 sections",
+    "Do not place 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/ELF/OutputSections.cpp

void OutputSection::commitSection(InputSection *isec) {
 
   // If this section contains a table of fixed-size entries, sh_entsize
   // holds the element size. If it contains elements of different size we
   // set sh_entsize to 0.
   if (entsize != isec->entsize)
     entsize = 0;
 }
 
+template <class ELFT>
+static void
+partitionDwarf32AndDwarf64Aux(std::vector<InputSection *> &sections) {
+  auto notDWARF64 = [](const InputSection *sec) {
+    if (sec->numRelocations == 0)
+      return true;
+    if (sec->areRelocsRela) {
+      auto &r = *static_cast<const typename ELFT::Rela *>(sec->firstRelocation);
+      return r.getType(config->isMips64EL) != target->symbolicRel;
+    } else {
+      auto &r = *static_cast<const typename ELFT::Rela *>(sec->firstRelocation);
+      return r.getType(config->isMips64EL) != target->symbolicRel;
+    }
+  };
+  std::stable_partition(sections.begin(), sections.end(), notDWARF64);
+}
+
+static void partitionDwarf32AndDwarf64(std::vector<InputSection *> &sections) {
+  switch (config->ekind) {
+  case ELF64LEKind:
+    return partitionDwarf32AndDwarf64Aux<ELF64LE>(sections);
+  case ELF64BEKind:
+    return partitionDwarf32AndDwarf64Aux<ELF64BE>(sections);
+  default:
+    llvm_unreachable("32-bit is unsupported");
+  }
+}
+
 // This function scans over the InputSectionBase list sectionBases to create
 // InputSectionDescription::sections.
 //
 // It removes MergeInputSections from the input section array and adds
 // new synthetic sections at the location of the first input section
 // that it replaces. It then finalizes each synthetic section in order
 // to compute an output offset for each piece of each input section.
 void OutputSection::finalizeInputSections() {
for (BaseCommand *base : sectionCommands) {
 
     // sectionBases should not be used from this point onwards. Clear it to
     // catch misuses.
     cmd->sectionBases.clear();
 
     // Some input sections may be removed from the list after ICF.
     for (InputSection *s : cmd->sections)
       commitSection(s);
+
+    if (config->dwarf32BeforeDwarf64 && (flags & SHF_ALLOC) == 0 &&
+        name.startswith(".debug_"))
+      partitionDwarf32AndDwarf64(cmd->sections);
   }
   for (auto *ms : mergeSections)
     ms->finalizeContents();
 }
 
 static void sortByOrder(MutableArrayRef<InputSection *> in,
                         llvm::function_ref<int(InputSectionBase *s)> order) {
   std::vector<std::pair<int, InputSection *>> v;

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

+# REQUIRES: ppc
+## 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=ppc64le %t/asm -o %tle.o
+
+## By default sections are combined in input order.
+# RUN: ld.lld %tle.o -o %tle
+# RUN: llvm-objdump -s %tle | FileCheck %s --check-prefix=LE
+# RUN: ld.lld --dwarf32-before-dwarf64 --no-dwarf32-before-dwarf64 %tle.o -o %tle
+# RUN: llvm-objdump -s %tle | FileCheck %s --check-prefix=LE
+
+## --dwarf32-before-dwarf64 orders DWARF32 before DWARF64.
+# RUN: ld.lld --dwarf32-before-dwarf64 %tle.o -o %tle
+# RUN: llvm-objdump -s %tle | FileCheck %s --check-prefix=LE-SORT
+
+## Test big-endian.
+# RUN: llvm-mc -filetype=obj -triple=ppc64 %t/asm -o %tbe.o
+# RUN: ld.lld --dwarf32-before-dwarf64 %tbe.o -o %tbe
+# RUN: llvm-objdump -s %tbe | FileCheck %s --check-prefix=BE-SORT
+
+# LE:      Contents of section .debug_info:
+# LE-NEXT:  0000 01000000 00000000 00000000 58010110
+# LE-NEXT:  0010 00000000 02000000 00000000 00000000
+# LE-NEXT:  0020 58010110 00000000 03000000 04000000
+# LE-NEXT:  0030 00000000 58010110 00000000
+## .debug_info offsets of unique,1 and unique,3: 0x0 and 0x28.
+# LE:      Contents of section .debug_aranges:
+# LE-NEXT:  0000 00000000 00000000 28000000
+# LE:      Contents of section .nondebug:
+# LE-NEXT:  0000 01000000 00000000 00000000 02000000
+# LE-NEXT:  0010 00000000
+
+# LE-SORT:      Contents of section .debug_info:
+# LE-SORT-NEXT:  0000 03000000 04000000 00000000 58010110
+# LE-SORT-NEXT:  0010 00000000 01000000 00000000 00000000
+# LE-SORT-NEXT:  0020 58010110 00000000 02000000 00000000
+# LE-SORT-NEXT:  0030 00000000 58010110 00000000
+
+## .debug_info offsets of unique,3 and unique,1: 0x0 and 0x14.
+# LE-SORT:      Contents of section .debug_aranges:
+# LE-SORT-NEXT:  0000 00000000 14000000 00000000
+## Non-debug sections
+# LE-SORT:      Contents of section .nondebug:
+# LE-SORT-NEXT:  0000 01000000 14000000 00000000 02000000
+# LE-SORT-NEXT:  0010 14000000
+
+# BE-SORT:      Contents of section .debug_info:
+# BE-SORT-NEXT:  0000 00000003 00000004 00000000 00000000
+# BE-SORT-NEXT:  0010 10010158 00000001 00000000 00000000
+# BE-SORT-NEXT:  0020 00000000 10010158 00000002 00000000
+# BE-SORT-NEXT:  0030 00000000 00000000 10010158
+
+
+## --dwarf32-before-dwarf64 applies to the input section description *(.debug_info).
+## This effectively makes DWARF32/DWARF64 a more significant key than
+## (SORT*,--sort-section,input order) in the conceptual radix sort.
+# RUN: ld.lld --dwarf32-before-dwarf64 -T %t/lds --allow-multiple-definition %tle.o %tle.o -o %tscript
+# RUN: llvm-objdump -s %tscript | FileCheck %s --check-prefix=SCRIPT
+
+# SCRIPT:      Contents of section .debug_info:
+# SCRIPT-NEXT:  0000 03000000 04000000 00000000 00000000
+# SCRIPT-NEXT:  0010 00000000 03000000 04000000 00000000
+# SCRIPT-NEXT:  0020 04000000 00000000 01000000 00000000
+# SCRIPT-NEXT:  0030 00000000 00000000 00000000 02000000
+# SCRIPT-NEXT:  0040 00000000 00000000 00000000 00000000
+# SCRIPT-NEXT:  0050 01000000 00000000 00000000 04000000
+# SCRIPT-NEXT:  0060 00000000 02000000 00000000 00000000
+# SCRIPT-NEXT:  0070 04000000 00000000
+
+# RUN: llvm-mc -filetype=obj -triple=ppc /dev/null -o %t32.o
+# RUN: not ld.lld --dwarf32-before-dwarf64 %t32.o -o /dev/null 2>&1 | FileCheck %s --check-prefix=32BIT
+
+# 32BIT: error: --dwarf32-before-dwarf64 is only supported on 64-bit targets
+
+#--- asm
+.globl _start
+_start:
+  blr
+
+.section .debug_abbrev
+
+## We use fake contents for simplicity. In practice, the first relocation being
+## the 64-bit absolute relocation type is a good indicator of DWARF64. Subsequent
+## relocations may have text section references which are always 64-bit, so they
+## cannot be used.
+
+## For these .debug_info sections, the first relocations of unique,1 and unique,2
+## are 64-bit absolute relocations and we consider them DWARF64.
+.section .debug_info,"",@progbits,unique,1
+.Lcu_begin1:
+  .long 1
+  .quad .debug_abbrev
+  .quad .text
+.section .debug_info,"",@progbits,unique,2
+  .long 2
+  .quad .debug_abbrev
+  .quad .text
+## No relocation, arbitrarily treated as a DWARF32.
+.section .debug_info,"",@progbits,unique,3
+.Lcu_begin3:
+  .long 3
+.section .debug_info,"",@progbits,unique,4
+  .long 4
+  .long .debug_abbrev
+  .quad .text
+
+## Test an arbitrary different .debug_*.
+.section .debug_aranges,"",@progbits,unique,1
+  .quad .Lcu_begin1
+.section .debug_aranges,"",@progbits,unique,3
+  .long .Lcu_begin3
+
+## Test that non-.debug_* sections are not ordered.
+.section .nondebug,"",@progbits,unique,1
+  .long 1
+  .quad .Lcu_begin1
+.section .nondebug,"",@progbits,unique,2
+  .long 2
+  .long .Lcu_begin1
+
+#--- lds
+SECTIONS {
+  .debug_info 0 : { *(.debug_info) }
+}