[LLD][ELF] Make SHF_LINK_ORDER section ordering use InputSectionDescriptions

[peter.smith]

Summary

This change moves the SHF_LINK_ORDER processing forward and makes it run on InputSectionDescriptions::Sections rather than OutputSections.

• The .ARM.exidx sentinel section is added as an InputSection if there is at least one .ARM.exidx section present. It will be added to the linker script with the other .ARM.exidx sections.
• The sorting of the SHF_LINK_ORDER sections and writing of the sentinel section contents now accounts for the section not always guaranteed last.
• The sorting of the SHF_LINK_ORDER is moved to LinkerScript
• The fabricated linker script commands are moved as far forward as possible

This is a step towards removing the need for the late LinkerScript::synchronize() function. It cannot be removed completely until Thunks are inserted directly into InputSectionDescriptions.

The current implementation of fabricateDefaultCommands() is moved up as far it can be with its current implementation. To move it further up we would need to split out the parts that rely on the program headers.

[• rafael]

The sorting does have to be made at the linker script level, but why do you have to change when it is made? Can the call to Script->sortLinkOrder be just before

for (OutputSection *Sec : OutputSections)
  Sec->finalize<ELFT>();

[peter.smith]

This is no longer needed, it was implemented in D33500 and D33496.

ELF/LinkerScript.h

   void assignOffsets(OutputSectionCommand *Cmd);
   void placeOrphanSections();
   void processNonSectionCommands();
+  void sortLinkOrder();
   void synchronize();
+  void resetAddressState();
   void assignAddresses(std::vector<PhdrEntry> &Phdrs);
 
   void writeDataBytes(OutputSection *Sec, uint8_t *Buf);

ELF/LinkerScript.cpp

   return nullptr;
 }
 
+// Reset the members associated with address assigment to their initial values
+// this permits addressAssignment to be run again.
+void LinkerScript::resetAddressState() {
+  LMAOffset = 0;
+  CurOutSec = nullptr;
+  CurMemRegion = nullptr;
+  ThreadBssOffset = 0;
+  for (auto &MRI : Opt.MemoryRegions) {
+    MemoryRegion &MR = MRI.second;
+    MR.Offset = MR.Origin;
+  }
+}
+
 // This function assigns offsets to input sections and an output section
 // for a single sections command (e.g. ".text { *(.text); }").
 void LinkerScript::assignOffsets(OutputSectionCommand *Cmd) {

   }
 }
 
+static bool compareByFilePosition(InputSectionBase *A, InputSectionBase *B) {
+  // Synthetic doesn't have link order dependency, stable_sort will keep it last
+  if (A->kind() == InputSectionBase::Synthetic)
+    return false;
+  else if (B->kind() == InputSectionBase::Synthetic)
+    return true;
+  auto *LA = cast<InputSection>(A->getLinkOrderDep());
+  auto *LB = cast<InputSection>(B->getLinkOrderDep());
+  OutputSection *AOut = LA->OutSec;
+  OutputSection *BOut = LB->OutSec;
+  if (AOut != BOut)
+    return AOut->SectionIndex < BOut->SectionIndex;
+  return LA->OutSecOff < LB->OutSecOff;
+}
+
+// InputSections with the SHF_LINK_ORDER flag are sorted in the same relative
+// order as the InputSections
+void LinkerScript::sortLinkOrder() {
+  // We need at least a relative order of InputSections within an OutputSection
+  // these need not be precise.
+  for (BaseCommand *Base : Opt.Commands)
+    if (auto *Cmd = dyn_cast<OutputSectionCommand>(Base)) {
+      if (Config->Relocatable)
+        Cmd->Sec->assignOffsets();
+      else
+        assignOffsets(Cmd);
+    }
+
+  for (BaseCommand *Base : Opt.Commands) {
+    auto *Cmd = dyn_cast<OutputSectionCommand>(Base);
+    if (!Cmd || !(Cmd->Sec->Flags & SHF_LINK_ORDER) ||
+        Cmd->Sec->Sections.empty())
+      continue;
+
+    // Link order may be distributed across several InputSectionDescriptions
+    // but sort must consider them all at once.
+    std::vector<InputSectionBase **> ScriptSections;
+    std::vector<InputSection *> Sections;
+    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);
+          Sections.push_back(cast<InputSection>(IS));
+        }
+    }
+    std::sort(Sections.begin(), Sections.end(), compareByFilePosition);
+    for (int I = 0, N = Sections.size(); I < N; ++I)
+      *ScriptSections[I] = Sections[I];
+  }
+}
 // 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.
+// list. This is needed to account for last minute changes, like adding thunks
 //
 // FIXME: We should instead create the "AST" earlier and the above changes would
 // be done directly in the "AST".

 void LinkerScript::synchronize() {
   for (BaseCommand *Base : Opt.Commands) {
     auto *Cmd = dyn_cast<OutputSectionCommand>(Base);
-    if (!Cmd)
+    if (!Cmd || (Cmd->Sec->Flags & SHF_LINK_ORDER))
       continue;
     ArrayRef<InputSection *> Sections = Cmd->Sec->Sections;
     std::vector<InputSectionBase **> ScriptSections;

 void LinkerScript::assignAddresses(std::vector<PhdrEntry> &Phdrs) {
   // Assign addresses as instructed by linker script SECTIONS sub-commands.
   Dot = 0;
+  resetAddressState();
   ErrorOnMissingSection = true;
   switchTo(Aether);
 

ELF/OutputSections.cpp

                   /*Link*/ 0),
       SectionIndex(INT_MAX) {}
 
-static bool compareByFilePosition(InputSection *A, InputSection *B) {
-  // Synthetic doesn't have link order dependecy, stable_sort will keep it last
-  if (A->kind() == InputSectionBase::Synthetic ||
-      B->kind() == InputSectionBase::Synthetic)
-    return false;
-  auto *LA = cast<InputSection>(A->getLinkOrderDep());
-  auto *LB = cast<InputSection>(B->getLinkOrderDep());
-  OutputSection *AOut = LA->OutSec;
-  OutputSection *BOut = LB->OutSec;
-  if (AOut != BOut)
-    return AOut->SectionIndex < BOut->SectionIndex;
-  return LA->OutSecOff < LB->OutSecOff;
-}
-
 // Compress section contents if this section contains debug info.
 template <class ELFT> void OutputSection::maybeCompress() {
   typedef typename ELFT::Chdr Elf_Chdr;

 
 template <class ELFT> void OutputSection::finalize() {
   if ((this->Flags & SHF_LINK_ORDER) && !this->Sections.empty()) {
-    std::sort(Sections.begin(), Sections.end(), compareByFilePosition);
-    assignOffsets();
-
     // We must preserve the link order dependency of sections with the
     // SHF_LINK_ORDER flag. The dependency is indicated by the sh_link field. We
     // need to translate the InputSection sh_link to the OutputSection sh_link,

ELF/SyntheticSections.cpp

 // This section will have been sorted last in the .ARM.exidx table.
 // This table entry will have the form:
 // | PREL31 upper bound of code that has exception tables | EXIDX_CANTUNWIND |
+// The sentinel must have the PREL31 value of an address higher than any
+// address described by any other table entry.
 void ARMExidxSentinelSection::writeTo(uint8_t *Buf) {
-  // Get the InputSection before us, we are by definition last
-  auto RI = cast<OutputSection>(this->OutSec)->Sections.rbegin();
-  InputSection *LE = *(++RI);
-  InputSection *LC = cast<InputSection>(LE->getLinkOrderDep());
-  uint64_t S = LC->OutSec->Addr + LC->getOffset(LC->getSize());
-  uint64_t P = this->getVA();
+  uint64_t S = 0;
+  uint64_t P = getVA();
+  for (auto *IS : OutSec->Sections)
+    if (IS->kind() != InputSectionBase::Synthetic) {
+      InputSection *LS = cast<InputSection>(IS->getLinkOrderDep());
+      S = std::max(S, LS->OutSec->Addr + LS->getOffset(LS->getSize()));
+    }
   Target->relocateOne(Buf, R_ARM_PREL31, S - P);
   write32le(Buf + 4, 0x1);
 }

ELF/Writer.cpp

   // Create linker-synthesized sections such as .got or .plt.
   // Such sections are of type input section.
   createSyntheticSections();
+  addPredefinedSections();
   combineMergableSections();
 
   if (!Config->Relocatable)

   if (Config->Relocatable) {
     assignFileOffsets();
   } else {
-    if (!Script->Opt.HasSections) {
-      fixSectionAlignments();
-      Script->fabricateDefaultCommands();
-    }
     Script->synchronize();
     Script->assignAddresses(Phdrs);
 

   if (ErrorCount)
     return;
 
-  // So far we have added sections from input object files.
-  // This function adds linker-created Out::* sections.
-  addPredefinedSections();
   removeUnusedSyntheticSections(OutputSections);
 
   sortSections();

     Out::ProgramHeaders->Size = sizeof(Elf_Phdr) * Phdrs.size();
   }
 
+  if (!Script->Opt.HasSections) {
+    fixSectionAlignments();
+    Script->fabricateDefaultCommands();
+  }
+  Script->sortLinkOrder();
+
   // Dynamic section must be the last one in this list and dynamic
   // symbol table section (DynSymTab) must be the first one.
   applySynthetic({InX::DynSymTab,    InX::Bss,           InX::BssRelRo,

 template <class ELFT> void Writer<ELFT>::addPredefinedSections() {
   // ARM ABI requires .ARM.exidx to be terminated by some piece of data.
   // We have the terminater synthetic section class. Add that at the end.
-  auto *OS = dyn_cast_or_null<OutputSection>(findSection(".ARM.exidx"));
-  if (OS && !OS->Sections.empty() && !Config->Relocatable)
-    OS->addSection(make<ARMExidxSentinelSection>());
+  if (Config->EMachine == EM_ARM && !Config->Relocatable &&
+      std::find_if(InputSections.begin(), InputSections.end(),
+                   [](InputSectionBase *S) {
+                     return S->Name.startswith(".ARM.exidx");
+                   }) != InputSections.end())
+    InputSections.push_back(make<ARMExidxSentinelSection>());
 }
 
 // The linker is expected to define SECNAME_start and SECNAME_end