Remove LinkerScript::flush

[• rafael]

Summary

This patch replaces flush with a last ditch attempt at synchronizing the section list with the linker script "AST".

The synchronization in a bit of a hack and should in time be avoided by creating the AST earlier so that modifications can be made directly to it instead of modifying the section list and synchronizing it back.

This is the main step for fixing https://bugs.llvm.org/show_bug.cgi?id=32816. With this in place I think the only missing thing would be to have processCommands assign section indexes as dummy offsets so that the sort in OutputSection::finalize works.

With this LinkerScript::assignAddresses becomes much simpler, which should help with the thunk work.

[ruiu]

LGTM. I think this is towards a right direction.

ELF/LinkerScript.cpp

818

This needs a comment.

[peter.smith]

This looks good to me too.

One thing I observed when writing the code in the initial Thunks submission to insert the Thunks back into the InputSectionDescriptions was that the order of OutputSections::Sections should match the order of InputSectionDescription::Sections (on the assumption that any additional Sections added to OutputSections::Sections were added on the end). If I'm correct I think you may be able to:

• Extract the last InputSectionBase from the last InputSectionDescription
• Find this section in OutputSection::Sections
• From the next section to the end of OutputSection::Sections should be your missing sections.

I may have missed something though.

Looking forward we'll need to make some changes to OutputSections::finalize(), if there are orphan link-order sections (the sentinel .ARM.exidx) for example they will get added to a new InputSectionDescription. The current sort of link order sections will only work on a single InputSectionDescription. When I get back to the office on Tuesday I'll rebase D32233, and my Thunks patches on top of this.

[• espindola]

301745

ELF/LinkerScript.h

protected:
   createInputSectionList(OutputSectionCommand &Cmd);
 
   std::vector<size_t> getPhdrIndices(StringRef SectionName);
   size_t getPhdrIndex(const Twine &Loc, StringRef PhdrName);
 
   MemoryRegion *findMemoryRegion(OutputSectionCommand *Cmd);
 
   void switchTo(OutputSection *Sec);
-  void flush();
   void output(InputSection *Sec);
   void process(BaseCommand &Base);
 
   OutputSection *Aether;
   bool ErrorOnMissingSection = false;
 
   uint64_t Dot;
   uint64_t ThreadBssOffset = 0;
 
   std::function<uint64_t()> LMAOffset;
   OutputSection *CurOutSec = nullptr;
   MemoryRegion *CurMemRegion = nullptr;
 
-  llvm::DenseSet<OutputSection *> AlreadyOutputOS;
-  llvm::DenseSet<InputSectionBase *> AlreadyOutputIS;
-
 public:
   bool hasPhdrsCommands() { return !Opt.PhdrsCommands.empty(); }
   uint64_t getDot() { return Dot; }
   OutputSection *getOutputSection(const Twine &Loc, StringRef S);
   uint64_t getOutputSectionSize(StringRef S);
   void discard(ArrayRef<InputSectionBase *> V);
 
   ExprValue getSymbolValue(const Twine &Loc, StringRef S);
public:
   bool ignoreInterpSection();
 
   llvm::Optional<uint32_t> getFiller(StringRef Name);
   bool hasLMA(StringRef Name);
   bool shouldKeep(InputSectionBase *S);
   void assignOffsets(OutputSectionCommand *Cmd);
   void placeOrphanSections();
   void processNonSectionCommands();
+  void synchronize();
   void assignAddresses(std::vector<PhdrEntry> &Phdrs);
   int getSectionIndex(StringRef Name);
 
   void writeDataBytes(StringRef Name, uint8_t *Buf);
   void addSymbol(SymbolAssignment *Cmd);
   void processCommands(OutputSectionFactory &Factory);
 
   // Parsed linker script configurations are set to this struct.

ELF/LinkerScript.cpp

if (!S->Live || S->OutSec)
       continue;
     StringRef Name = getOutputSectionName(S->Name);
     auto I = std::find_if(
         Opt.Commands.begin(), Opt.Commands.end(), [&](BaseCommand *Base) {
           if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base))
             return Cmd->Name == Name;
           return false;
         });
-    if (I == Opt.Commands.end())
+    if (I == Opt.Commands.end()) {
       Factory.addInputSec(S, Name);
-    else
-      Factory.addInputSec(S, Name, cast<OutputSectionCommand>(*I)->Sec);
+    } else {
+      auto *Cmd = cast<OutputSectionCommand>(*I);
+      Factory.addInputSec(S, Name, Cmd->Sec);
+      auto *ISD = make<InputSectionDescription>("");
+      ISD->Sections.push_back(S);
+      Cmd->Commands.push_back(ISD);
+    }
   }
 }
 
 static bool isTbss(OutputSection *Sec) {
   return (Sec->Flags & SHF_TLS) && Sec->Type == SHT_NOBITS;
 }
 
 void LinkerScript::output(InputSection *S) {
-  if (!AlreadyOutputIS.insert(S).second)
-    return;
   bool IsTbss = isTbss(CurOutSec);
 
   uint64_t Pos = IsTbss ? Dot + ThreadBssOffset : Dot;
   Pos = alignTo(Pos, S->Alignment);
   S->OutSecOff = Pos - CurOutSec->Addr;
   Pos += S->getSize();
 
   // Update output section size after adding each section. This is so that
void LinkerScript::output(InputSection *S) {
   }
 
   if (IsTbss)
     ThreadBssOffset = Pos - Dot;
   else
     Dot = Pos;
 }
 
-void LinkerScript::flush() {
-  assert(CurOutSec);
-  if (!AlreadyOutputOS.insert(CurOutSec).second)
-    return;
-  for (InputSection *I : CurOutSec->Sections)
-    output(I);
-}
-
 void LinkerScript::switchTo(OutputSection *Sec) {
   if (CurOutSec == Sec)
     return;
-  if (AlreadyOutputOS.count(Sec))
-    return;
 
   CurOutSec = Sec;
 
   Dot = alignTo(Dot, CurOutSec->Alignment);
   CurOutSec->Addr = isTbss(CurOutSec) ? Dot + ThreadBssOffset : Dot;
 
   // If neither AT nor AT> is specified for an allocatable section, the linker
   // will set the LMA such that the difference between VMA and LMA for the
for (InputSectionBase *Sec : Cmd.Sections) {
     // going be empty or not other than actually running linker scripts.)
     // We need to ignore remains of empty sections.
     if (auto *S = dyn_cast<SyntheticSection>(Sec))
       if (S->empty())
         continue;
 
     if (!Sec->Live)
       continue;
-    assert(CurOutSec == Sec->OutSec || AlreadyOutputOS.count(Sec->OutSec));
+    assert(CurOutSec == Sec->OutSec);
     output(cast<InputSection>(Sec));
   }
 }
 
 // This function searches for a memory region to place the given output
 // section in. If found, a pointer to the appropriate memory region is
 // returned. Otherwise, a nullptr is returned.
 MemoryRegion *LinkerScript::findMemoryRegion(OutputSectionCommand *Cmd) {
if (Cmd->LMAExpr) {
     LMAOffset = [=] { return Cmd->LMAExpr().getValue() - D; };
   }
 
   CurMemRegion = Cmd->MemRegion;
   if (CurMemRegion)
     Dot = CurMemRegion->Offset;
   switchTo(Sec);
 
-  // flush() may add orphan sections, so the order of flush() and
-  // symbol assignments is important. We want to call flush() first so
-  // that symbols pointing the end of the current section points to
-  // the location after orphan sections.
-  auto Mid =
-      std::find_if(Cmd->Commands.rbegin(), Cmd->Commands.rend(),
-                   [](BaseCommand *Cmd) { return !isa<SymbolAssignment>(Cmd); })
-          .base();
-  for (auto I = Cmd->Commands.begin(); I != Mid; ++I)
-    process(**I);
-  flush();
-  for (auto I = Mid, E = Cmd->Commands.end(); I != E; ++I)
-    process(**I);
+  for (BaseCommand *Cmd : Cmd->Commands)
+    process(*Cmd);
 }
 
 void LinkerScript::removeEmptyCommands() {
   // It is common practice to use very generic linker scripts. So for any
   // given run some of the output sections in the script will be empty.
   // We could create corresponding empty output sections, but that would
   // clutter the output.
   // We instead remove trivially empty sections. The bfd linker seems even
for (OutputSection *Sec : *OutputSections) {
     }
 
     auto Pos = std::find_if(CmdIter, E, [&](BaseCommand *Base) {
       auto *Cmd = dyn_cast<OutputSectionCommand>(Base);
       return Cmd && Cmd->Name == Name;
     });
     if (Pos == E) {
       auto *Cmd = make<OutputSectionCommand>(Name);
-      Cmd->Sec = Sec;
       Opt.Commands.insert(CmdIter, Cmd);
       ++CmdIndex;
+
+      Cmd->Sec = Sec;
+      auto *ISD = make<InputSectionDescription>("");
+      for (InputSection *IS : Sec->Sections)
+        ISD->Sections.push_back(IS);
+      Cmd->Commands.push_back(ISD);
+
       continue;
     }
 
     // Continue from where we found it.
     CmdIndex = (Pos - Opt.Commands.begin()) + 1;
   }
 }
 
 void LinkerScript::processNonSectionCommands() {
   for (BaseCommand *Base : Opt.Commands) {
     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base))
       assignSymbol(Cmd, false);
     else if (auto *Cmd = dyn_cast<AssertCommand>(Base))
       Cmd->Expression();
   }
 }
 
+// Do a last effort at synchronizing the linker script "AST" and the section
+// list. This is needed to account for last minute changes, like adding a
+// .ARM.exidx terminator and sorting SHF_LINK_ORDER sections.
+//
+// FIXME: We should instead create the "AST" earlier and the above changes would
+// be done directly in the "AST".
+//
+// This can only handle new sections being added and sections being reordered.
+void LinkerScript::synchronize() {
+  for (BaseCommand *Base : Opt.Commands) {
+    auto *Cmd = dyn_cast<OutputSectionCommand>(Base);
+    if (!Cmd)
+      continue;
+    ArrayRef<InputSection *> Sections = Cmd->Sec->Sections;
+    std::vector<InputSectionBase **> ScriptSections;
+    for (BaseCommand *Base : Cmd->Commands) {
+      auto *ISD = dyn_cast<InputSectionDescription>(Base);
+      if (!ISD)
+        continue;
+      for (InputSectionBase *&IS : ISD->Sections)
+        if (IS->Live)
+          ScriptSections.push_back(&IS);
+    }
+    std::vector<InputSectionBase *> Missing;
+    for (InputSection *IS : Sections)
+      if (std::find_if(ScriptSections.begin(), ScriptSections.end(),
+                       [=](InputSectionBase **Base) { return *Base == IS; }) ==
+          ScriptSections.end())
+        Missing.push_back(IS);
+    if (!Missing.empty()) {
+      auto ISD = make<InputSectionDescription>("");
+      ISD->Sections = Missing;
+      Cmd->Commands.push_back(ISD);
+      for (InputSectionBase *&IS : ISD->Sections)
+        if (IS->Live)
+          ScriptSections.push_back(&IS);
+    }
+    assert(ScriptSections.size() == Sections.size());
+    for (int I = 0, N = Sections.size(); I < N; ++I)
+      *ScriptSections[I] = Sections[I];
+  }
+}
+
 void LinkerScript::assignAddresses(std::vector<PhdrEntry> &Phdrs) {
   // Assign addresses as instructed by linker script SECTIONS sub-commands.
   Dot = 0;
   ErrorOnMissingSection = true;
   switchTo(Aether);
 
   for (BaseCommand *Base : Opt.Commands) {
     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {

ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::run() {
 
   if (Config->Relocatable) {
     assignFileOffsets();
   } else {
     if (!Script->Opt.HasSections) {
       fixSectionAlignments();
       Script->fabricateDefaultCommands(Config->MaxPageSize);
     }
+    Script->synchronize();
     Script->assignAddresses(Phdrs);
 
     // Remove empty PT_LOAD to avoid causing the dynamic linker to try to mmap a
     // 0 sized region. This has to be done late since only after assignAddresses
     // we know the size of the sections.
     removeEmptyPTLoad();
 
     if (!Config->OFormatBinary)
for (InputSectionBase *S : llvm::reverse(InputSections)) {
     SyntheticSection *SS = dyn_cast<SyntheticSection>(S);
     if (!SS)
       return;
     if (!SS->empty() || !SS->OutSec)
       continue;
 
     SS->OutSec->Sections.erase(std::find(SS->OutSec->Sections.begin(),
                                          SS->OutSec->Sections.end(), SS));
+    SS->Live = false;
     // If there are no other sections in the output section, remove it from the
     // output.
     if (SS->OutSec->Sections.empty())
       V.erase(std::find(V.begin(), V.end(), SS->OutSec));
   }
 }
 
 // Create output section objects and add them to OutputSections.