[ELF] Use tombstone values for discarded symbols in relocatable output

[ikudrin]

Summary

This extends D81784. Sections can be discarded when linking a relocatable output. Before the patch, LLD did not update the content of debug sections and only replaced the corresponding relocations with R_*_NONE, which could break the debug information.

[MaskRay]

InputSection::relocateNonAlloc takes significant time in the --time-trace metric Write sections.

Now a relocatable link runs both relocateNonAllocForRelocatable and relocateNonAlloc, making it slower. -r performance is less important than executable/shared, so I think if there is no better choice (readability/performance trade-off) paying the cost if fine, but I wonder whether we can do something better.

Unrelated to this patch, I have the question whether we can make relocateNonAlloc faster for executable/shared.

lld/ELF/InputSection.cpp

944

Maybe it's time to swap then and else.

[MaskRay]

lld/test/ELF/debug-dead-reloc-relocatable.s

6

Use .o for relocatable object files.

[ikudrin]

• Add .o in the test
• Swap then and else branches in InputSection::relocateNonAlloc()

In D116946#3233496, @MaskRay wrote:

Now a relocatable link runs both relocateNonAllocForRelocatable and relocateNonAlloc, making it slower. -r performance is less important than executable/shared, so I think if there is no better choice (readability/performance trade-off) paying the cost if fine, but I wonder whether we can do something better.

As copyRelocations() already detects the case, it could store some information for relocateNonAllocForRelocatable() so that the latter apply tombstone values. But that looked more complicated than the taken way, and I agree with you that the performance of -r is not that important to sacrifice readability.

Unrelated to this patch, I have the question whether we can make relocateNonAlloc faster for executable/shared.

As for now, I do not see obvious ways to improve.

[MaskRay]

Sacrificing the performance for -r seems fine.

lld/ELF/InputSection.cpp

1002–1003

This needs a comment with something like: for a relocatable link, call relocateNonAlloc to rewrite applicable locations with the tombstone value.

lld/test/ELF/debug-dead-reloc-relocatable.s

8

Super nit: llvm-readelf -r -x .debug_ranges or llvm-objdump -r -s -j .debug_ranges

[ikudrin]

• Add comments
• Dump only required information in the test

[MaskRay]

LGTM.

lld/ELF/InputSection.cpp

for (const RelTy &rel : rels) {
     if (!RelTy::IsRela)
       addend += target.getImplicitAddend(bufLoc, type);
 
     Symbol &sym = getFile<ELFT>()->getRelocTargetSym(rel);
     RelExpr expr = target.getRelExpr(type, sym, bufLoc);
     if (expr == R_NONE)
       continue;
 
-    if (expr == R_SIZE) {
-      target.relocateNoSym(bufLoc, type,
-                           SignExtend64<bits>(sym.getSize() + addend));
-      continue;
-    }
-
-    // R_ABS/R_DTPREL and some other relocations can be used from non-SHF_ALLOC
-    // sections.
-    if (expr != R_ABS && expr != R_DTPREL && expr != R_GOTPLTREL &&
-        expr != R_RISCV_ADD) {
-      std::string msg = getLocation<ELFT>(offset) +
-                        ": has non-ABS relocation " + toString(type) +
-                        " against symbol '" + toString(sym) + "'";
-      if (expr != R_PC && expr != R_ARM_PCA) {
-        error(msg);
-        return;
-      }
-
-      // If the control reaches here, we found a PC-relative relocation in a
-      // non-ALLOC section. Since non-ALLOC section is not loaded into memory
-      // at runtime, the notion of PC-relative doesn't make sense here. So,
-      // this is a usage error. However, GNU linkers historically accept such
-      // relocations without any errors and relocate them as if they were at
-      // address 0. For bug-compatibilty, we accept them with warnings. We
-      // know Steel Bank Common Lisp as of 2018 have this bug.
-      warn(msg);
-      target.relocateNoSym(
-          bufLoc, type,
-          SignExtend64<bits>(sym.getVA(addend - offset - outSecOff)));
-      continue;
-    }
-
     if (tombstone ||
         (isDebug && (type == target.symbolicRel || expr == R_DTPREL))) {
       // Resolve relocations in .debug_* referencing (discarded symbols or ICF
       // folded section symbols) to a tombstone value. Resolving to addend is
       // unsatisfactory because the result address range may collide with a
       // valid range of low address, or leave multiple CUs claiming ownership of
       // the same range of code, which may confuse consumers.
       //
if (tombstone ||
       if (!sym.getOutputSection() || (ds && ds->folded && !isDebugLine)) {
         // If -z dead-reloc-in-nonalloc= is specified, respect it.
         const uint64_t value = tombstone ? SignExtend64<bits>(*tombstone)
                                          : (isDebugLocOrRanges ? 1 : 0);
         target.relocateNoSym(bufLoc, type, value);
         continue;
       }
     }
+
+    // For a relocatable link, only tombstone values are applied.
+    if (config->relocatable)
+      continue;
+
+    if (expr == R_SIZE) {
+      target.relocateNoSym(bufLoc, type,
+                           SignExtend64<bits>(sym.getSize() + addend));
+      continue;
+    }
+
+    // R_ABS/R_DTPREL and some other relocations can be used from non-SHF_ALLOC
+    // sections.
+    if (expr == R_ABS || expr == R_DTPREL || expr == R_GOTPLTREL ||
+        expr == R_RISCV_ADD) {
       target.relocateNoSym(bufLoc, type, SignExtend64<bits>(sym.getVA(addend)));
+      continue;
+    }
+
+    std::string msg = getLocation<ELFT>(offset) + ": has non-ABS relocation " +
+                      toString(type) + " against symbol '" + toString(sym) +
+                      "'";
+    if (expr != R_PC && expr != R_ARM_PCA) {
+      error(msg);
+      return;
+    }
+
+    // If the control reaches here, we found a PC-relative relocation in a
+    // non-ALLOC section. Since non-ALLOC section is not loaded into memory
+    // at runtime, the notion of PC-relative doesn't make sense here. So,
+    // this is a usage error. However, GNU linkers historically accept such
+    // relocations without any errors and relocate them as if they were at
+    // address 0. For bug-compatibilty, we accept them with warnings. We
+    // know Steel Bank Common Lisp as of 2018 have this bug.
+    warn(msg);
+    target.relocateNoSym(
+        bufLoc, type,
+        SignExtend64<bits>(sym.getVA(addend - offset - outSecOff)));
   }
 }
 
 // This is used when '-r' is given.
 // For REL targets, InputSection::copyRelocations() may store artificial
 // relocations aimed to update addends. They are handled in relocateAlloc()
 // for allocatable sections, and this function does the same for
 // non-allocatable sections, such as sections with debug information.
if ((flags & SHF_EXECINSTR) && LLVM_UNLIKELY(getFile<ELFT>()->splitStack))
     adjustSplitStackFunctionPrologues<ELFT>(buf, bufEnd);
 
   if (flags & SHF_ALLOC) {
     relocateAlloc(buf, bufEnd);
     return;
   }
 
   auto *sec = cast<InputSection>(this);
-  if (config->relocatable) {
+  if (config->relocatable)
     relocateNonAllocForRelocatable(sec, buf);
-  } else {
-    const RelsOrRelas<ELFT> rels = sec->template relsOrRelas<ELFT>();
-    if (rels.areRelocsRel())
-      sec->relocateNonAlloc<ELFT>(buf, rels.rels);
-    else
-      sec->relocateNonAlloc<ELFT>(buf, rels.relas);
-  }
-}
+  // For a relocatable link, also call relocateNonAlloc() to rewrite applicable
+  // locations with tombstone values.
 
 void InputSectionBase::relocateAlloc(uint8_t *buf, uint8_t *bufEnd) {
   assert(flags & SHF_ALLOC);
   const unsigned bits = config->wordsize * 8;
   const TargetInfo &target = *elf::target;
   uint64_t lastPPCRelaxedRelocOff = UINT64_C(-1);
   AArch64Relaxer aarch64relaxer(relocations);
   for (size_t i = 0, size = relocations.size(); i != size; ++i) {

lld/test/ELF/debug-dead-reloc-relocatable.s

+# REQUIRES: x86
+## Test we resolve symbolic relocations in .debug_* sections to a tombstone
+## value if the referenced symbol is discarded when linking a relocatable object.
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64 %s -o %t1.o
+# RUN: ld.lld -r %t1.o %t1.o -o %t2.o
+# RUN: llvm-readelf -r -x .debug_ranges %t2.o | FileCheck %s
+
+## Relocations for a discarded section are changed to *_NONE.
+# CHECK:      Relocation section '.rela.debug_ranges' at offset [[#%#x,]] contains 4 entries:
+# CHECK-NEXT:     Offset          Info        Type       Symbol's Value  Symbol's Name + Addend
+# CHECK-NEXT: 0000000000000000  [[#%x,]] R_X86_64_64    0000000000000000 .text.foo + 0
+# CHECK-NEXT: 0000000000000008  [[#%x,]] R_X86_64_64    0000000000000000 .text.foo + 1
+# CHECK-NEXT: 0000000000000020  [[#%x,]] R_X86_64_NONE
+# CHECK-NEXT: 0000000000000028  [[#%x,]] R_X86_64_NONE
+
+## References to a discarded section are changed to tombstone values.
+# CHECK:      Hex dump of section '.debug_ranges':
+# CHECK-NEXT: 0x00000000 00000000 00000000 00000000 00000000
+# CHECK-NEXT: 0x00000010 00000000 00000000 00000000 00000000
+# CHECK-NEXT: 0x00000020 01000000 00000000 01000000 00000000
+# CHECK-NEXT: 0x00000030 00000000 00000000 00000000 00000000
+
+.weak foo
+
+  .section .text.foo,"axG",@progbits,foo,comdat
+.Lfoo:
+foo:
+  ret
+.Lfoo_end:
+
+  .section .debug_ranges,"",@progbits
+  .quad .Lfoo
+  .quad .Lfoo_end
+  .quad 0
+  .quad 0