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

332

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

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

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_SYMTAB_SHNDX:
       break;
     case SHT_STRTAB:
     case SHT_NULL:
       break;
     default:
       Sections[I] = createInputSection(Sec, SectionStringTable);
     }
 
+    InputSectionBase<ELFT> *Base = Sections[I];
+    if (Sec.sh_flags & SHF_ASSOCIATED &&
+        (!Base || !isa<InputSection<ELFT>>(Base)))
+      error("SHF_ASSOCIATED only supported with regular sections " +
+            toString(Base));
+
     // .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];
+      IS->DependentSections.push_back(Base);
     }
   }
 }
 
 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_ASSOCIATED) {
+      forEachSuccessor<ELFT>(
+          cast<InputSection<ELFT>>(*Sec), [=](ResolvedReloc<ELFT> R) {
+            // We only consider references from SHF_ASSOCIATED to regular
+            // sections. This allows it to refer to, for example, a string table
+            // and still be gced.
+            if (auto *S = dyn_cast<InputSection<ELFT>>(R.Sec))
+              S->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});
   }

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

+# REQUIRES: x86
+
+# RUN: llvm-mc -filetype=obj -triple=x86_64-pc-linux %s -o %t
+# RUN: not ld.lld --gc-sections -shared %t -o %t2 2>&1 | FileCheck %s
+
+# CHECK: error: SHF_ASSOCIATED only supported with regular sections {{.*}}{{/|\\}}gc-sections-invert-edge-error.s.tmp:(foo1)
+
+.section foo1,"aoM",@progbits,8
+.quad 0

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 .merge
+# CHECK-NEXT:    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 .merge, "aM", @progbits, 8
+.quad 0
+
+.section foo1,"ao"
+.quad .bar1 - .
+.quad .merge
+
+.section foo2,"ao"
+.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 'o' and it maps to SHF_ASSOCIATIVE.
+
 Target Specific Behaviour
 =========================
 
 Windows on ARM
 --------------
 
 Stack Probe Emission
 ^^^^^^^^^^^^^^^^^^^^

llvm/include/llvm/Support/ELF.h

enum : unsigned {
   SHF_GROUP = 0x200U,
 
   // This section holds Thread-Local Storage.
   SHF_TLS = 0x400U,
 
   // Identifies a section containing compressed data.
   SHF_COMPRESSED = 0x800U,
 
+  // Relocations from this section should not keep the destination alive. It is
+  // the destination that should keep this section alive.
+  // FIXME: Tentative value.
+  SHF_ASSOCIATED = 0x1000U,
+
   // This section is excluded from the final executable or shared library.
   SHF_EXCLUDE = 0x80000000U,
 
   // Start of target-specific flags.
 
   /// XCORE_SHF_CP_SECTION - All sections with the "c" flag are grouped
   /// together by the linker to form the constant pool and the cp register is
   /// set to the start of the constant pool by the boot code.

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 'o':
+      flags |= ELF::SHF_ASSOCIATED;
+      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,"ao"
+// CHECK:      Section {
+// CHECK:        Name: .shf_link_order
+// CHECK-NEXT:   Type: SHT_PROGBITS
+// CHECK-NEXT:   Flags [
+// CHECK-NEXT:     SHF_ALLOC
+// CHECK-NEXT:     SHF_ASSOCIATED
+// CHECK-NEXT:   ]
+// CHECK-NEXT:   Address:
+// CHECK-NEXT:   Offset: 0x40
+// CHECK-NEXT:   Size: 0
+// CHECK-NEXT:   Link: 0

llvm/tools/llvm-readobj/ELFDumper.cpp

static const EnumEntry<unsigned> ElfSectionFlags[] = {
   ENUM_ENT(SHF_INFO_LINK,        "I"),
   ENUM_ENT(SHF_LINK_ORDER,       "L"),
   ENUM_ENT(SHF_OS_NONCONFORMING, "o"),
   ENUM_ENT(SHF_GROUP,            "G"),
   ENUM_ENT(SHF_TLS,              "T"),
   ENUM_ENT(SHF_MASKOS,           "o"),
   ENUM_ENT(SHF_MASKPROC,         "p"),
   ENUM_ENT_1(SHF_COMPRESSED),
+  ENUM_ENT_1(SHF_ASSOCIATED),
 };
 
 static const EnumEntry<unsigned> ElfXCoreSectionFlags[] = {
   LLVM_READOBJ_ENUM_ENT(ELF, XCORE_SHF_CP_SECTION),
   LLVM_READOBJ_ENUM_ENT(ELF, XCORE_SHF_DP_SECTION)
 };
 
 static const EnumEntry<unsigned> ElfAMDGPUSectionFlags[] = {