RFC: Generalize inverted gc dependencies

[• espindola]

Summary

I am mostly interested in checking that this is sufficient to implement the asan use case. If it does I will benchmark this to see if I have to move the std::vector out or not.

[ruiu]

lld/ELF/InputFiles.cpp

325

Does this mean that there is a section with SHF_LINK_ORDER bit but with a null sh_link? It seems like a broken object file to me.

lld/ELF/MarkLive.cpp

238–244

Why do you need this code? It seems you initializes DependentSections in InputFiles.

[eugenis]

lld/ELF/MarkLive.cpp

241

This does not have to be an InputSection.
I see it crashing on .rodata.str1.1 which is a MergeInputSection.

[eugenis]

A bigger problem is current LLD crashing on SHF_LINK_ORDER with zero sh_link, and ld.bfd complaining about that with warning messages. This means we can not safely create such sections in the compiler.

Add SHF_ASSOCIATED?

[• rafael]

Add and use SHF_ASSOCIATIVE. If this works for asan I will try to get the value added to the spec.

[silvas]

Small nit.

llvm/include/llvm/Support/ELF.h

749 ↗

(On Diff #84606)

Explain the semantics. There is currently no spec reference to look up.

[eugenis]

Thank you, this looks and works great!

My earlier comment still needs to be addressed though, casts to InputSection must be replaced with dyn_cast<> with null checks.

[• rafael]

Fix review comments.

If everyone is OK with this I will reply to the generic-abi.

[pcc]

The design of this feature looks good to me, thanks.

lld/ELF/InputFiles.cpp

322

I think it's fine to have this restriction, but aren't we still crashing on associated sections with relocations referring to merge sections?

[ruiu]

Looks good, but are you going to submit this?

[• rafael]

Fix crash.

I will now go back to the generic-abi thread.

[eugenis]

llvm/include/llvm/Support/ELF.h

752 ↗

(On Diff #84865)

this is conflicting with XCORE_SHF_DP_SECTION a few lines below, which is printed in assembly as "d" flag instead of "o"

lld/ELF/InputFiles.cpp

case SHT_NULL:
       break;
     default:
       Sections[I] = createInputSection(Sec, SectionStringTable);
     }
 
     // .ARM.exidx sections have a reverse dependency on the InputSection they
     // have a SHF_LINK_ORDER dependency, this is identified by the sh_link.
     if (Sec.sh_flags & SHF_LINK_ORDER) {
       if (Sec.sh_link >= Sections.size())
         fatal(toString(this) + ": invalid sh_link index: " +
               Twine(Sec.sh_link));
-      auto *IS = cast<InputSection<ELFT>>(Sections[Sec.sh_link]);
-      IS->DependentSection = Sections[I];
+      if (uint32_t Link = Sec.sh_link) {
+        auto *IS = cast<InputSection<ELFT>>(Sections[Link]);
+        IS->DependentSections.push_back(Sections[I]);
+      }
     }
   }
 }
 
 template <class ELFT>
 InputSectionBase<ELFT> *
 elf::ObjectFile<ELFT>::getRelocTarget(const Elf_Shdr &Sec) {
   uint32_t Idx = Sec.sh_info;

lld/ELF/InputSection.h

public:
   // Write this section to a mmap'ed file, assuming Buf is pointing to
   // beginning of the output section.
   void writeTo(uint8_t *Buf);
 
   // The offset from beginning of the output sections this section was assigned
   // to. The writer sets a value.
   uint64_t OutSecOff = 0;
 
-  // InputSection that is dependent on us (reverse dependency for GC)
-  InputSectionBase<ELFT> *DependentSection = nullptr;
+  // InputSections that are dependent on us (reverse dependency for GC)
+  std::vector<InputSectionBase<ELFT> *> DependentSections;
 
   static bool classof(const InputSectionData *S);
 
   InputSectionBase<ELFT> *getRelocatedSection();
 
   // Register thunk related to the symbol. When the section is written
   // to a mmap'ed file, target is requested to write an actual thunk code.
   // Now thunks is supported for MIPS and ARM target only.

lld/ELF/MarkLive.cpp

static void forEachSuccessor(InputSection<ELFT> &Sec,
                              std::function<void(ResolvedReloc<ELFT>)> Fn) {
   if (Sec.AreRelocsRela) {
     for (const typename ELFT::Rela &Rel : Sec.relas())
       Fn(resolveReloc(Sec, Rel));
   } else {
     for (const typename ELFT::Rel &Rel : Sec.rels())
       Fn(resolveReloc(Sec, Rel));
   }
-  if (Sec.DependentSection)
-    Fn({Sec.DependentSection, 0});
+  for (InputSectionBase<ELFT> *D : Sec.DependentSections)
+    Fn({D, 0});
 }
 
 // The .eh_frame section is an unfortunate special case.
 // The section is divided in CIEs and FDEs and the relocations it can have are
 // * CIEs can refer to a personality function.
 // * FDEs can refer to a LSDA
 // * FDEs refer to the function they contain information about
 // The last kind of relocation cannot keep the referred section alive, or they
template <class ELFT> void elf::markLive() {
   // file can interrupt other ELF file's symbols at runtime.
   for (const Symbol *S : Symtab<ELFT>::X->getSymbols())
     if (S->includeInDynsym())
       MarkSymbol(S->body());
 
   // Preserve special sections and those which are specified in linker
   // script KEEP command.
   for (InputSectionBase<ELFT> *Sec : Symtab<ELFT>::X->Sections) {
+    if (Sec->Flags & SHF_LINK_ORDER) {
+      forEachSuccessor<ELFT>(
+          cast<InputSection<ELFT>>(*Sec), [=](ResolvedReloc<ELFT> R) {
+            cast<InputSection<ELFT>>(R.Sec)->DependentSections.push_back(Sec);
+          });
+      continue;
+    }
+
     // .eh_frame is always marked as live now, but also it can reference to
     // sections that contain personality. We preserve all non-text sections
     // referred by .eh_frame here.
     if (auto *EH = dyn_cast_or_null<EhInputSection<ELFT>>(Sec))
       scanEhFrameSection<ELFT>(*EH, Enqueue);
     if (isReserved(Sec) || Script<ELFT>::X->shouldKeep(Sec))
       Enqueue({Sec, 0});
   }
 
   // Mark all reachable sections.
-  while (!Q.empty())
-    forEachSuccessor<ELFT>(*Q.pop_back_val(), Enqueue);
+  while (!Q.empty()) {
+    InputSection<ELFT> &Sec = *Q.pop_back_val();
+    forEachSuccessor<ELFT>(Sec, Enqueue);
+  }
 }
 
 template void elf::markLive<ELF32LE>();
 template void elf::markLive<ELF32BE>();
 template void elf::markLive<ELF64LE>();
 template void elf::markLive<ELF64BE>();

lld/test/ELF/gc-sections-invert-edge.s

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t
+# RUN: ld.lld --gc-sections %t -o %t2
+# RUN: llvm-objdump -section-headers %t2 | FileCheck  %s
+
+# CHECK:      1 foo1
+# CHECK-NEXT:   .bar1
+# CHECK-NEXT:   .text
+# CHECK-NEXT:   .comment
+# CHECK-NEXT:   .symtab
+# CHECK-NEXT:   .shstrtab
+# CHECK-NEXT:   .strtab
+
+.global _start
+_start:
+.quad .bar1  - .
+
+.section foo1,"al"
+.quad .bar1 - .
+
+.section foo2,"al"
+.quad .bar2 - .
+
+.section .bar1,"a"
+.quad 0
+.section .bar2,"a"
+.quad 0
+

llvm/docs/Extensions.rst

.. code-block:: gas
 
   .section  .text,"ax",@progbits,unique,2
         nop
 
 
 The unique number is not present in the resulting object at all. It is just used
 in the assembler to differentiate the sections.
 
+The section flags can include an 'l' and it maps to SHF_LINK_ORDER.
+
 Target Specific Behaviour
 =========================
 
 Windows on ARM
 --------------
 
 Stack Probe Emission
 ^^^^^^^^^^^^^^^^^^^^

llvm/lib/MC/MCParser/ELFAsmParser.cpp

case 'd':
       flags |= ELF::XCORE_SHF_DP_SECTION;
       break;
     case 'y':
       flags |= ELF::SHF_ARM_PURECODE;
       break;
     case 'G':
       flags |= ELF::SHF_GROUP;
       break;
+    case 'l':
+      flags |= ELF::SHF_LINK_ORDER;
+      break;
     case '?':
       *UseLastGroup = true;
       break;
     default:
       return -1U;
     }
   }
 

llvm/test/MC/ELF/section.s

 // Test that we handle the strings like gas
 .section bar-"foo"
 .section "foo"
 
 // CHECK:        Section {
 // CHECK:          Name: bar-"foo"
 // CHECK:        Section {
 // CHECK:          Name: foo
+
+// Test SHF_LINK_ORDER
+
+.section .shf_link_order,"al"
+// CHECK:      Section {
+// CHECK:        Name: .shf_link_order
+// CHECK-NEXT:   Type: SHT_PROGBITS
+// CHECK-NEXT:   Flags [
+// CHECK-NEXT:     SHF_ALLOC
+// CHECK-NEXT:     SHF_LINK_ORDER
+// CHECK-NEXT:   ]
+// CHECK-NEXT:   Address:
+// CHECK-NEXT:   Offset: 0x40
+// CHECK-NEXT:   Size: 0
+// CHECK-NEXT:   Link: 0