Fully precise gc handling of __start and __stop symbols

[• rafael]

Summary

This puts us at parity with bfd, which could already gc this case.

I noticed the sections not being gced when linking a modified freebsd kernel. A section that was not gced and not mentioned in the linker script would end up breaking the expected layout. Since fixing the gc is relatively simple and an improvement, that seems better than trying to hack the orphan placement code.

There are 173 input section in the entire link whose names are valid C identifiers, so a std::vector is probably better than a multimap.

[ruiu]

ELF/MarkLive.cpp

69

Can you .reset() this at beginning of markLive() so that markLive is safe to run more than once.

Maybe DenseSet instead of a vector? It is a set of strings, so a set seems more natural.

[• rafael]

Use a DenseMap and clear it.

Not that this has to be a map to a std::vector since it has to include multiple sections. If we hit an undefined reference to __start_foo, we have to mark live all sections named foo.

[ruiu]

ELF/MarkLive.cpp

253

Can you simplify resolveReloc if you add two entries ("__start_" + Sec->Name and "__end_" + Sec->Name) for one section?

[• rafael]

Simplify by mapping from symbol name to section.

[ruiu]

LGTM

[• espindola]

297049

ELF/MarkLive.cpp

 // defined in this file visits all reachable sections to set their Live
 // bits. Writer will then ignore sections whose Live bits are off, so that
 // such sections are not included into output.
 //
 //===----------------------------------------------------------------------===//
 
 #include "InputSection.h"
 #include "LinkerScript.h"
+#include "Memory.h"
 #include "OutputSections.h"
 #include "Strings.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "Target.h"
 #include "Writer.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/Object/ELF.h"

 }
 
 template <class ELFT>
 static typename ELFT::uint getAddend(InputSectionBase &Sec,
                                      const typename ELFT::Rela &Rel) {
   return Rel.r_addend;
 }
 
+// There are normally few input sections whose names are valid C
+// identifiers, so we just store a std::vector instead of a multimap.
+static DenseMap<StringRef, std::vector<InputSectionBase *>> CNamedSections;
+
 template <class ELFT, class RelT>
 static void resolveReloc(InputSectionBase &Sec, RelT &Rel,
                          std::function<void(ResolvedReloc)> Fn) {
   SymbolBody &B = Sec.getFile<ELFT>()->getRelocTargetSym(Rel);
-  auto *D = dyn_cast<DefinedRegular>(&B);
-  if (!D || !D->Section)
+  if (auto *D = dyn_cast<DefinedRegular>(&B)) {
+    if (!D->Section)
       return;
     typename ELFT::uint Offset = D->Value;
     if (D->isSection())
       Offset += getAddend<ELFT>(Sec, Rel);
     Fn({D->Section->Repl, Offset});
+  } else if (auto *U = dyn_cast<Undefined>(&B)) {
+    for (InputSectionBase *Sec : CNamedSections.lookup(U->getName()))
+      Fn({Sec, 0});
+  }
 }
 
 // Calls Fn for each section that Sec refers to via relocations.
 template <class ELFT>
 static void forEachSuccessor(InputSection &Sec,
                              std::function<void(ResolvedReloc)> Fn) {
   if (Sec.AreRelocsRela) {
     for (const typename ELFT::Rela &Rel : Sec.template relas<ELFT>())
template <class ELFT> static bool isReserved(InputSectionBase *Sec) {
   }
 }
 
 // This is the main function of the garbage collector.
 // Starting from GC-root sections, this function visits all reachable
 // sections to set their "Live" bits.
 template <class ELFT> void elf::markLive() {
   SmallVector<InputSection *, 256> Q;
+  CNamedSections.clear();
 
   auto Enqueue = [&](ResolvedReloc R) {
     // Skip over discarded sections. This in theory shouldn't happen, because
     // the ELF spec doesn't allow a relocation to point to a deduplicated
     // COMDAT section directly. Unfortunately this happens in practice (e.g.
     // .eh_frame) so we need to add a check.
     if (R.Sec == &InputSection::Discarded)
       return;
template <class ELFT> void elf::markLive() {
 
   // Add GC root symbols.
   MarkSymbol(Symtab<ELFT>::X->find(Config->Entry));
   MarkSymbol(Symtab<ELFT>::X->find(Config->Init));
   MarkSymbol(Symtab<ELFT>::X->find(Config->Fini));
   for (StringRef S : Config->Undefined)
     MarkSymbol(Symtab<ELFT>::X->find(S));
 
-  // Remember which __start_* or __stop_* symbols are used so that we don't gc
-  // those sections.
-  DenseSet<StringRef> UsedStartStopNames;
-
   // Preserve externally-visible symbols if the symbols defined by this
   // file can interrupt other ELF file's symbols at runtime.
-  for (const Symbol *S : Symtab<ELFT>::X->getSymbols()) {
-    if (auto *U = dyn_cast_or_null<Undefined>(S->body())) {
-      StringRef Name = U->getName();
-      for (StringRef Prefix : {"__start_", "__stop_"})
-        if (Name.startswith(Prefix))
-          UsedStartStopNames.insert(Name.substr(Prefix.size()));
-    } else if (S->includeInDynsym()) {
+  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 *Sec : InputSections) {
     // .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<ELFT>(Sec) || Script<ELFT>::X->shouldKeep(Sec) ||
-        UsedStartStopNames.count(Sec->Name))
+    if (isReserved<ELFT>(Sec) || Script<ELFT>::X->shouldKeep(Sec))
       Enqueue({Sec, 0});
+    else if (isValidCIdentifier(Sec->Name)) {
+      CNamedSections[Saver.save("__start_" + Sec->Name)].push_back(Sec);
+      CNamedSections[Saver.save("__end_" + Sec->Name)].push_back(Sec);
+    }
   }
 
   // Mark all reachable sections.
   while (!Q.empty())
     forEachSuccessor<ELFT>(*Q.pop_back_val(), Enqueue);
 }
 
 template void elf::markLive<ELF32LE>();
 template void elf::markLive<ELF32BE>();
 template void elf::markLive<ELF64LE>();
 template void elf::markLive<ELF64BE>();

test/ELF/linkerscript/sections-gc2.s

# CHECK-NEXT:    .strtab
         .global _start
 _start:
         .quad __start_used_in_reloc
 
         .section unused,"a"
         .quad 0
 
         .section used_in_script,"a"
-        .quad 0
+        .quad __start_used_in_script
 
         .section used_in_reloc,"a"
         .quad 0