[ELF] Linkerscript: eliminate LayoutInputSection

[evgeny777]

Summary

Current implementation of LayoutInputSection relies on LLVM-style casting to InputSection<ELFT>, which is not a base class for it. The following statements will be successfully compiled and executed:

InputSection<ELFT> *I = ...;
LayoutInputSection<ELFT> *L = cast<LayoutInputSection<ELFT>>(I);

And the following one cannot compile:

LayoutInputSection<ELFT> *L = static_cast<LayoutInputSection<ELFT> *>(I);

This patch eliminates LayoutInputSection by saving pointer to preceding input section in SymbolAssignment class.

[grimar]

ELF/LinkerScript.cpp

341

I would reorder conditions to avoid nesting and ++ItCmd in multiple places:

auto AddSuccessors = [&](InputSectionData *D) {
  for (; I != Cmd->Commands.end(); ++I) {
    auto *AssignCmd = dyn_cast<SymbolAssignment>(I->get());
    if (!AssignCmd)
      continue;
    if (D != AssignCmd->GoesAfter)
      break;

    uintX_t Value = AssignCmd->Expression(Sec->getVA() + Off) - Sec->getVA();
    if (AssignCmd->Name == ".") {
      // Update to location counter means update to section size.
      Off = Value;
      Sec->setSize(Off);
      continue;
    }

    if (DefinedSynthetic<ELFT> *Sym =
            cast_or_null<DefinedSynthetic<ELFT>>(AssignCmd->Sym)) {
      Sym->Section = OutSec;
      Sym->Value = Value;
    }
  }
};

348

Asignment in argument ? May be better separate it ?

Off = Value;
Sec->setSize(Value);

[ruiu]

ELF/InputSection.h

34–37

Move this after public section.

46–48

Seems Compressed is also used by the garbage collector.

58–59

Now the "Base" class has a base class? I seems to me that it's too object-oriented-ish, but let's see how it works.

ELF/LinkerScript.cpp

212–213

reinterpret_cast<OutputSectionBase<ELFT> *>(-1ULL)?

338

It needs a comment.

[evgeny777]

ELF/InputSection.h

58–59

Unfortunately SymbolAssignment is not (and shouldn't be) template class.
Also I think that moving data which doesn't depend on template parameter ELFT to the base non-template class should slightly reduce image size.

[evgeny777]

Addressed review comments + simplified InputSectionData.

[• rafael]

ELF/LinkerScript.cpp

353

Is this correctly handling the case of

. = . + 4
foo = .

That is, the virtual address of a symbol is not immediately after a inputsection?

[evgeny777]

Yeah. See lines 294-295 in LinkerScript.cpp. Also, please take a look at linkerscript-symbols-synthetic.s

[• rafael]

LGTM.

I think the code can be simplified further (I am experimenting with it), but this is a step in the right direction.

Thanks!

ELF/InputSection.h

46

Move the "Usef for garbage collection" comment to the same line as Live or add a newline after it.

[ruiu]

ELF/InputSection.h

33

Please write a comment for this class. It should describe why we need this class (because we want to have a base class which is not a template class).

46

Yup. That's what I meant.

ELF/LinkerScript.cpp

209

Needs a comment. What are you trying to do with this loop?

318

Thank you for the comment. I think I now understand what it does.

[evgeny777]

Rebased and addressed review comments

[ruiu]

LGTM with this change.

ELF/LinkerScript.cpp

214–217

Setting -1 to the pointer to record whether an input section is added or not is an unintended use of the pointer and pretty confusing. Please use a DenseSet to uniquefy.

[evgeny777]

ELF/LinkerScript.cpp

214–217

This will cause growth of memory consumption and slightly slow down things. May be using some fake output section is better?

OutputSectionBase<ELFT> FakeSec;
for (InputSectionBase<ELFT> *S : V)
      if (!S->OutSec) {
         Ret.push_back(S);
         S->OutSec = &FakeSec;
      }

[ruiu]

ELF/LinkerScript.cpp

214–217

That also has a prolonged side effect -- the assigned pointers will be visible from outside after returning from this function even though they are not valid pointers. That confuses readers as to why we needed to assign pointers. I was actually wondering. I don't think this is a performance critical path (linker scripts are not that fast anyways). So I'd use a map.

ELF/InputSection.h

 
 template <class ELFT> class ICF;
 template <class ELFT> class DefinedRegular;
 template <class ELFT> class DefinedCommon;
 template <class ELFT> class ObjectFile;
 template <class ELFT> class OutputSection;
 template <class ELFT> class OutputSectionBase;
 
+// We need non-template input section class to store symbol layout
+// in linker script parser structures, where we do not have ELFT
+// template parameter. For each scripted output section symbol we
+// store pointer to preceding InputSectionData object or nullptr,
+// if symbol should be placed at the very beginning of the output
+// section
+class InputSectionData {
+public:
+  enum Kind { Regular, EHFrame, Merge, MipsReginfo, MipsOptions, MipsAbiFlags };
+
+  // The garbage collector sets sections' Live bits.
+  // If GC is disabled, all sections are considered live by default.
+  InputSectionData(Kind SectionKind, bool Compressed, bool Live)
+      : SectionKind(SectionKind), Live(Live), Compressed(Compressed) {}
+
+  Kind SectionKind;
+  uint32_t Alignment;
+  // Used for garbage collection.
+  bool Live;
+
+  bool Compressed;
+  // If a section is compressed, this vector has uncompressed section data.
+  SmallVector<char, 0> Uncompressed;
+};
+
 // This corresponds to a section of an input file.
-template <class ELFT> class InputSectionBase {
+template <class ELFT> class InputSectionBase : public InputSectionData {
 protected:
   typedef typename ELFT::Chdr Elf_Chdr;
   typedef typename ELFT::Rel Elf_Rel;
   typedef typename ELFT::Rela Elf_Rela;
   typedef typename ELFT::Shdr Elf_Shdr;
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::uint uintX_t;
   const Elf_Shdr *Header;
 
   // The file this section is from.
   ObjectFile<ELFT> *File;
 
-  // If a section is compressed, this vector has uncompressed section data.
-  SmallVector<char, 0> Uncompressed;
-
 public:
-  enum Kind {
-    Regular,
-    EHFrame,
-    Merge,
-    MipsReginfo,
-    MipsOptions,
-    MipsAbiFlags,
-    Layout
-  };
-  Kind SectionKind;
-
-  InputSectionBase() : Repl(this) {}
+  InputSectionBase() : InputSectionData(Regular, false, false), Repl(this) {}
 
   InputSectionBase(ObjectFile<ELFT> *File, const Elf_Shdr *Header,
                    Kind SectionKind);
   OutputSectionBase<ELFT> *OutSec = nullptr;
-  uint32_t Alignment;
-
-  // Used for garbage collection.
-  bool Live;
 
   // This pointer points to the "real" instance of this instance.
   // Usually Repl == this. However, if ICF merges two sections,
   // Repl pointer of one section points to another section. So,
   // if you need to get a pointer to this instance, do not use
   // this but instead this->Repl.
   InputSectionBase<ELFT> *Repl;
 
public:
   uintX_t getOffset(uintX_t Offset) const;
 
   ArrayRef<uint8_t> getSectionData() const;
 
   void uncompress();
 
   void relocate(uint8_t *Buf, uint8_t *BufEnd);
   std::vector<Relocation<ELFT>> Relocations;
-
-  bool Compressed;
 };
 
 template <class ELFT> InputSectionBase<ELFT> InputSectionBase<ELFT>::Discarded;
 
 // SectionPiece represents a piece of splittable section contents.
 struct SectionPiece {
   SectionPiece(size_t Off, ArrayRef<uint8_t> Data)
       : InputOff(Off), Data((const uint8_t *)Data.data()), Size(Data.size()),

ELF/InputSection.cpp

 using namespace llvm::object;
 using namespace llvm::support::endian;
 
 using namespace lld;
 using namespace lld::elf;
 
 template <class ELFT>
 InputSectionBase<ELFT>::InputSectionBase(elf::ObjectFile<ELFT> *File,
-                                         const Elf_Shdr *Header,
-                                         Kind SectionKind)
-    : Header(Header), File(File), SectionKind(SectionKind), Repl(this),
-      Compressed(Header->sh_flags & SHF_COMPRESSED) {
-  // The garbage collector sets sections' Live bits.
-  // If GC is disabled, all sections are considered live by default.
-  Live = !Config->GcSections;
-
+                                         const Elf_Shdr *Hdr, Kind SectionKind)
+    : InputSectionData(SectionKind, Hdr->sh_flags & SHF_COMPRESSED,
+                       !Config->GcSections),
+      Header(Hdr), File(File), Repl(this) {
   // The ELF spec states that a value of 0 means the section has
   // no alignment constraits.
   Alignment = std::max<uintX_t>(Header->sh_addralign, 1);
 }
 
 template <class ELFT> size_t InputSectionBase<ELFT>::getSize() const {
   if (auto *D = dyn_cast<InputSection<ELFT>>(this))
     if (D->getThunksSize() > 0)

 template <class SectionT> static std::string getName(SectionT *Sec) {
   return (Sec->getFile()->getName() + "(" + Sec->getSectionName() + ")").str();
 }
 
 template <class ELFT>
 typename ELFT::uint InputSectionBase<ELFT>::getOffset(uintX_t Offset) const {
   switch (SectionKind) {
   case Regular:
-  case Layout:
     return cast<InputSection<ELFT>>(this)->OutSecOff + Offset;
   case EHFrame:
     // The file crtbeginT.o has relocations pointing to the start of an empty
     // .eh_frame that is known to be the first in the link. It does that to
     // identify the start of the output .eh_frame.
     return Offset;
   case Merge:
     return cast<MergeInputSection<ELFT>>(this)->getOffset(Offset);

 
 template <class ELFT>
 InputSection<ELFT>::InputSection(elf::ObjectFile<ELFT> *F,
                                  const Elf_Shdr *Header)
     : InputSectionBase<ELFT>(F, Header, Base::Regular) {}
 
 template <class ELFT>
 bool InputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
-  return S->SectionKind == Base::Regular || S->SectionKind == Base::Layout;
+  return S->SectionKind == Base::Regular;
 }
 
 template <class ELFT>
 InputSectionBase<ELFT> *InputSection<ELFT>::getRelocatedSection() {
   assert(this->Header->sh_type == SHT_RELA || this->Header->sh_type == SHT_REL);
   ArrayRef<InputSectionBase<ELFT> *> Sections = this->File->getSections();
   return Sections[this->Header->sh_info];
 }

ELF/LinkerScript.h

 namespace lld {
 namespace elf {
 class ScriptParser;
 class SymbolBody;
 template <class ELFT> class InputSectionBase;
 template <class ELFT> class OutputSectionBase;
 template <class ELFT> class OutputSectionFactory;
 template <class ELFT> class DefinedCommon;
-template <class ELFT> class LayoutInputSection;
+class InputSectionData;
 
 typedef std::function<uint64_t(uint64_t)> Expr;
 
 // Parses a linker script. Calling this function updates
 // Config and ScriptConfig.
 void readLinkerScript(MemoryBufferRef MB);
 
 // This enum is used to implement linker script SECTIONS command.
struct SymbolAssignment : BaseCommand {
   SymbolBody *Sym = nullptr;
 
   // The RHS of an expression.
   Expr Expression;
 
   // Command attributes for PROVIDE, HIDDEN and PROVIDE_HIDDEN.
   bool Provide = false;
   bool Hidden = false;
+  InputSectionData *GoesAfter = nullptr;
 };
 
 // Linker scripts allow additional constraints to be put on ouput sections.
 // An output section will only be created if all of its input sections are
 // read-only
 // or all of its input sections are read-write by using the keyword ONLY_IF_RO
 // and ONLY_IF_RW respectively.
 enum class ConstraintKind { NoConstraint, ReadOnly, ReadWrite };
private:
 
   // "ScriptConfig" is a bit too long, so define a short name for it.
   ScriptConfiguration &Opt = *ScriptConfig;
 
   int getSectionIndex(StringRef Name);
   std::vector<size_t> getPhdrIndices(StringRef SectionName);
   size_t getPhdrIndex(StringRef PhdrName);
 
-  llvm::SpecificBumpPtrAllocator<LayoutInputSection<ELFT>> LAlloc;
-
   uintX_t Dot;
 };
 
 // Variable template is a C++14 feature, so we can't template
 // a global variable. Use a struct to workaround.
 template <class ELFT> struct Script { static LinkerScript<ELFT> *X; };
 template <class ELFT> LinkerScript<ELFT> *Script<ELFT>::X;
 
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/LinkerScript.cpp

LinkerScript<ELFT>::getInputSections(const InputSectionDescription *I) {
   }
 
   if (llvm::find(Patterns, "COMMON") != Patterns.end())
     Ret.push_back(CommonInputSection<ELFT>::X);
 
   return Ret;
 }
 
-// You can define new symbols using linker scripts. For example,
-// ".text { abc.o(.text); foo = .; def.o(.text); }" defines symbol
-// foo just after abc.o's text section contents. This class is to
-// handle such symbol definitions.
-//
-// In order to handle scripts like the above one, we want to
-// keep symbol definitions in output sections. Because output sections
-// can contain only input sections, we wrap symbol definitions
-// with dummy input sections. This class serves that purpose.
-template <class ELFT>
-class elf::LayoutInputSection : public InputSectionBase<ELFT> {
-public:
-  explicit LayoutInputSection(SymbolAssignment *Cmd);
-  static bool classof(const InputSectionBase<ELFT> *S);
-  SymbolAssignment *Cmd;
-
-private:
-  typename ELFT::Shdr Hdr;
-};
-
-template <class ELFT>
-static InputSectionBase<ELFT> *
-getNonLayoutSection(std::vector<InputSectionBase<ELFT> *> &Vec) {
-  for (InputSectionBase<ELFT> *S : Vec)
-    if (!isa<LayoutInputSection<ELFT>>(S))
-      return S;
-  return nullptr;
-}
-
-template <class T> static T *zero(T *Val) {
-  memset(Val, 0, sizeof(*Val));
-  return Val;
-}
-
-template <class ELFT>
-LayoutInputSection<ELFT>::LayoutInputSection(SymbolAssignment *Cmd)
-    : InputSectionBase<ELFT>(nullptr, zero(&Hdr),
-                             InputSectionBase<ELFT>::Layout),
-      Cmd(Cmd) {
-  this->Live = true;
-  Hdr.sh_type = SHT_NOBITS;
-}
-
-template <class ELFT>
-bool LayoutInputSection<ELFT>::classof(const InputSectionBase<ELFT> *S) {
-  return S->SectionKind == InputSectionBase<ELFT>::Layout;
-}
-
 template <class ELFT>
 static bool compareName(InputSectionBase<ELFT> *A, InputSectionBase<ELFT> *B) {
   return A->getSectionName() < B->getSectionName();
 }
 
 template <class ELFT>
 static bool compareAlignment(InputSectionBase<ELFT> *A,
                              InputSectionBase<ELFT> *B) {

 std::vector<InputSectionBase<ELFT> *>
 LinkerScript<ELFT>::createInputSectionList(OutputSectionCommand &OutCmd) {
   std::vector<InputSectionBase<ELFT> *> Ret;
 
   for (const std::unique_ptr<BaseCommand> &Base : OutCmd.Commands) {
     if (auto *OutCmd = dyn_cast<SymbolAssignment>(Base.get())) {
       if (shouldDefine<ELFT>(OutCmd))
         addSynthetic<ELFT>(OutCmd);
-      Ret.push_back(new (LAlloc.Allocate()) LayoutInputSection<ELFT>(OutCmd));
+      OutCmd->GoesAfter = Ret.empty() ? nullptr : Ret.back();
       continue;
     }
 
     auto *Cmd = cast<InputSectionDescription>(Base.get());
     std::vector<InputSectionBase<ELFT> *> V = getInputSections(Cmd);
     if (!matchConstraints<ELFT>(V, OutCmd.Constraint))
       continue;
     if (Cmd->SortInner)
       std::stable_sort(V.begin(), V.end(), getComparator<ELFT>(Cmd->SortInner));
     if (Cmd->SortOuter)
       std::stable_sort(V.begin(), V.end(), getComparator<ELFT>(Cmd->SortOuter));
-    Ret.insert(Ret.end(), V.begin(), V.end());
+
+    // Add all input sections corresponding to rule 'Cmd' to
+    // resulting vector. We do not add duplicate input section,
+    // using 'OutSec' field to detect is section has already been
+    // added.
+    for (InputSectionBase<ELFT> *S : V)
+      if (S->OutSec == nullptr) {
+        Ret.push_back(S);
+        S->OutSec = reinterpret_cast<OutputSectionBase<ELFT> *>(-1ULL);
+      }
   }
   return Ret;
 }
 
 template <class ELFT>
 void LinkerScript<ELFT>::createSections(OutputSectionFactory<ELFT> &Factory) {
   for (const std::unique_ptr<BaseCommand> &Base1 : Opt.Commands) {
     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base1.get())) {
       if (shouldDefine<ELFT>(Cmd))
         addRegular<ELFT>(Cmd);
       continue;
     }
 
     if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base1.get())) {
       if (Cmd->Name == "/DISCARD/") {
         discard(*Cmd);
         continue;
       }
 
       std::vector<InputSectionBase<ELFT> *> V = createInputSectionList(*Cmd);
-      InputSectionBase<ELFT> *Head = getNonLayoutSection<ELFT>(V);
-      if (!Head)
+      if (V.empty())
         continue;
 
       OutputSectionBase<ELFT> *OutSec;
       bool IsNew;
-      std::tie(OutSec, IsNew) = Factory.create(Head, Cmd->Name);
+      std::tie(OutSec, IsNew) = Factory.create(V.front(), Cmd->Name);
       if (IsNew)
         OutputSections->push_back(OutSec);
 
       uint32_t Subalign = Cmd->SubalignExpr ? Cmd->SubalignExpr(0) : 0;
       for (InputSectionBase<ELFT> *Sec : V) {
         if (Subalign)
           Sec->Alignment = Subalign;
-        if (!Sec->OutSec)
-          OutSec->addSection(Sec);
       }
     }
   }
 
   // Add orphan sections.
   for (const std::unique_ptr<ObjectFile<ELFT>> &F :
        Symtab<ELFT>::X->getObjectFiles()) {
     for (InputSectionBase<ELFT> *S : F->getSections()) {
void assignOffsets(OutputSectionCommand *Cmd, OutputSectionBase<ELFT> *Sec) {
   auto *OutSec = dyn_cast<OutputSection<ELFT>>(Sec);
   if (!OutSec) {
     Sec->assignOffsets();
     // This section is not regular output section. However linker script may
     // have defined start/end symbols for it. This case is handled below.
     addStartEndSymbols(Cmd, Sec);
     return;
   }
-
   typedef typename ELFT::uint uintX_t;
   uintX_t Off = 0;
+  auto ItCmd = Cmd->Commands.begin();
 
-  for (InputSection<ELFT> *I : OutSec->Sections) {
-    if (auto *L = dyn_cast<LayoutInputSection<ELFT>>(I)) {
-      uintX_t Value = L->Cmd->Expression(Sec->getVA() + Off) - Sec->getVA();
-      if (L->Cmd->Name == ".") {
+  // Assigns values to all symbols following the given
+  // input section 'D' in output section 'Sec'. When symbols
+  // are in the beginning of output section the value of 'D'
+  // is nullptr.
+  auto AssignSuccessors = [&](InputSectionData *D) {
+    for (; ItCmd != Cmd->Commands.end(); ++ItCmd) {
+      auto *AssignCmd = dyn_cast<SymbolAssignment>(ItCmd->get());
+      if (!AssignCmd)
+        continue;
+      if (D != AssignCmd->GoesAfter)
+        break;
+
+      uintX_t Value = AssignCmd->Expression(Sec->getVA() + Off) - Sec->getVA();
+      if (AssignCmd->Name == ".") {
+        // Update to location counter means update to section size.
         Off = Value;
-      } else if (auto *Sym =
-                     cast_or_null<DefinedSynthetic<ELFT>>(L->Cmd->Sym)) {
-        // shouldDefine could have returned false, so we need to check Sym,
-        // for non-null value.
+        Sec->setSize(Off);
+        continue;
+      }
+
+      if (DefinedSynthetic<ELFT> *Sym =
+              cast_or_null<DefinedSynthetic<ELFT>>(AssignCmd->Sym)) {
         Sym->Section = OutSec;
         Sym->Value = Value;
       }
-    } else {
-      Off = alignTo(Off, I->Alignment);
-      I->OutSecOff = Off;
-      Off += I->getSize();
-    }
+    }
+  };
+
+  AssignSuccessors(nullptr);
+  for (InputSection<ELFT> *I : OutSec->Sections) {
     // Update section size inside for-loop, so that SIZEOF
     // works correctly in the case below:
     // .foo { *(.aaa) a = SIZEOF(.foo); *(.bbb) }
     Sec->setSize(Off);
+    // Add symbols following current input section.
+    AssignSuccessors(I);
   }
 }
 
 template <class ELFT>
 static OutputSectionBase<ELFT> *
 findSection(OutputSectionCommand &Cmd,
             ArrayRef<OutputSectionBase<ELFT> *> Sections) {
   for (OutputSectionBase<ELFT> *Sec : Sections) {

ELF/OutputSections.cpp

case InputSectionBase<ELFT>::MipsReginfo:
     Sec = new MipsReginfoOutputSection<ELFT>();
     break;
   case InputSectionBase<ELFT>::MipsOptions:
     Sec = new MipsOptionsOutputSection<ELFT>();
     break;
   case InputSectionBase<ELFT>::MipsAbiFlags:
     Sec = new MipsAbiFlagsOutputSection<ELFT>();
     break;
-  case InputSectionBase<ELFT>::Layout:
-    llvm_unreachable("Invalid section type");
   }
   Out<ELFT>::Pool.emplace_back(Sec);
   return {Sec, true};
 }
 
 template <class ELFT>
 SectionKey<ELFT::Is64Bits>
 OutputSectionFactory<ELFT>::createKey(InputSectionBase<ELFT> *C,