[LLD][ELF] User linkerscript InputSectionDescription for .ARM.exidx dependency order

[peter.smith]

Summary

InputSections with a SHF_LINK_ORDER dependency must be ordered in the same order as the InputSections that they have a dependency on. This ordering is done late in the link when the OutputSection containing a SHF_LINK_ORDER dependency is finalized. The reordering needs to handle these cases:

• No linker script SECTIONS command describing OutputSection
• Linker script that fully describes OutputSection with no orphans
• Linker script that partially describes OutputSection with orphans

At present we sort the OutputSection::Sections vector which will be fully or partially ignored if a linker script fully or partially describes the .ARM.exidx OutputSection. This is analogous to the insertion of thunks directly into OutputSection::Sections.

Building upon D32223:

This change:

• introduces a function inputSectionRanges() to obtain just the InputSectionDescriptions from an OutputSection.
• Inserts the .ARM.exidx sentinel into an InputSectionDescription
• Moves the fabricateInputSectionDescriptions before the call to OutputSection::finalize(), we need to do at least one call to Script->assignAddresses() to assign each InputSection its OutSecOff.
• Added a function to clear the state that accumulates with each call to assignAddresses() so that we can call it more than once.
• Consolidates the InputSectionDescriptions for .ARM.exidx into one as we need to sort the entire table. We can get multiple InputSectionDescriptions when something like

.ARM.exidx { *(.ARM.exidx) }

which will get orphans of the form .ARM.exidx.suffix.

• Sort the InputSectionDescription using the same criteria as before.
• Adds a test case that would previously fail as the later call to Script->assignAddresses() would ignore the sorting done to OutputSection::Sections().

[ruiu]

I'm not totally sure if this is towards a right direction. We used to be sorting .ARM.exidx in a direct way -- we had code to directly look at .ARM.exidx input sections and sort them, but now we are creating intermediate data that is to be interpreted by the linker script processor. This seems more intricate way to do a fairly straightforward thing, which is just to sort input sections. Do you think there's a more direct way of doing it?

[peter.smith]

I can think of some options, although each has their own trade-off. Apologies for the length of the answer.

To restate what I think the requirements are:

1. All of the .ARM.exidx* sections need to be placed contiguously in one "table".
2. The order of the .ARM.exidx* sections needs to match the order of the code sections that the .ARM.exidx sections have a link order dependency to.

For non-linker script links, or linker script links where .ARM.exidx sections are all orphans we use the naming rules to ensure that there is a single .ARM.exidx OutputSection containing all the .ARM.exidx* InputSections, that takes care of requirement 1.
For linker script links where .ARM.exidx sections are not orphans we are somewhat reliant on the user to get the pattern right to satisfy 1.) The best pattern is .ARM.exidx : { *(.ARM.exidx*) }, but .ARM.exidx : { *(.ARM.exidx) } without the trailing * will work as the .ARM.exidx.foo sections will be orphans.

At the moment if all .ARM.exidx sections are orphans or there is no linker script we can sort the OutputSections::Sections directly to satisfy 2.)
If any of the .ARM.exidx sections are covered by a linker script, our current Output::Sections sort will be ignored by the Script->assignAddresses() and we are likely to not satisfy 2.)

With this in mind, I think the options are:
1.) Do not include .ARM.exidx sections in any InputSectionDescription::Section, they will always be added as orphans, this will either mean some special case code in LinkerScripts to not add the sections, or some code to go in and remove them from the InputSectionDescriptions prior to final address assignment. This would allow the existing direct sorting approach to work as the script's handling of orphans would just work.
2.) Do what I originally proposed for RangeThunks and synchronize/rewrite the output of sorting OutputSection::Sections with the InputSectionDescriptions. I think that this is just a different way of implementing option 1.) but putting the special case code after, rather than before.
3.) The option above, which is to work entirely in InputSectionDescription::Section. This doesn't require quite so much special case code in LinkerScripts for .ARM.exidx, but it does mean that the sorting code has to cope with linker scripts that have multiple InputSectionDescriptions due to orphans or just users writing something like .ARM.exidx : { *(.ARM.exidx) *(.ARM.exidx.foo*) }.

I think that option 1 could end up being simpler overall. I'm going to be at a conference for the rest of the week, but if I can't get something finished today I'll do so early next week.

[peter.smith]

I've created D32485 for an alternative implementation that just makes the link order sections orphans. I think that this ends up being a bit simpler overall.

[peter.smith]

Abandoning this revision in favour of D33239.

ELF/LinkerScript.h

protected:
   std::vector<InputSectionBase *>
   createInputSectionList(OutputSectionCommand &Cmd);
 
   std::vector<size_t> getPhdrIndices(StringRef SectionName);
   size_t getPhdrIndex(const Twine &Loc, StringRef PhdrName);
 
   MemoryRegion *findMemoryRegion(OutputSectionCommand *Cmd);
 
+  void resetAddressState();
+
   void switchTo(OutputSection *Sec);
   void flush();
   void output(InputSection *Sec);
   void process(BaseCommand &Base);
 
   OutputSection *Aether;
   bool ErrorOnMissingSection = false;
 
public:
   uint64_t getOutputSectionSize(StringRef S);
   void discard(ArrayRef<InputSectionBase *> V);
 
   ExprValue getSymbolValue(const Twine &Loc, StringRef S);
   bool isDefined(StringRef S);
 
   std::vector<OutputSection *> *OutputSections;
   void fabricateDefaultCommands(bool AllocateHeader);
+  std::vector<std::vector<InputSectionBase *> *>
+  inputSectionRanges(StringRef S);
   void addOrphanSections(OutputSectionFactory &Factory);
   void removeEmptyCommands();
   void adjustSectionsBeforeSorting();
   void adjustSectionsAfterSorting();
 
   std::vector<PhdrEntry> createPhdrs();
   bool ignoreInterpSection();
 

ELF/LinkerScript.cpp

if (Sec->Sections.size()) {
       }
     }
   }
   // SECTIONS commands run before other non SECTIONS commands
   Commands.insert(Commands.end(), Opt.Commands.begin(), Opt.Commands.end());
   Opt.Commands = std::move(Commands);
 }
 
+// For an OutputSection S, return the InputSectionDescriptions that are
+// associated with S. The intention is that callers can iterate over
+// InputSectionDescription::Sections and insert sections such as Thunks.
+std::vector<std::vector<InputSectionBase *> *>
+LinkerScript::inputSectionRanges(StringRef S) {
+  std::vector<std::vector<InputSectionBase *> *> Ranges;
+  auto OutCmdPos = std::find_if(
+      Opt.Commands.begin(), Opt.Commands.end(), [=](BaseCommand *Cmd) {
+        if (auto *OSCmd = dyn_cast<OutputSectionCommand>(Cmd))
+          return (OSCmd->Name == S);
+        return false;
+      });
+  if (OutCmdPos == Opt.Commands.end())
+    return Ranges;
+  auto *OutCmd = cast<OutputSectionCommand>(*OutCmdPos);
+  for (auto *BaseCmd : OutCmd->Commands) {
+    if (auto *ISD = dyn_cast<InputSectionDescription>(BaseCmd))
+      Ranges.push_back(&ISD->Sections);
+  }
+  return Ranges;
+}
+
 // Add sections that didn't match any sections command.
 void LinkerScript::addOrphanSections(OutputSectionFactory &Factory) {
   std::map<OutputSection *, std::vector<InputSectionBase *>> Orphanage;
   for (InputSectionBase *S : InputSections)
     if (S->Live && !S->OutSec) {
       Factory.addInputSec(S, getOutputSectionName(S->Name));
       Orphanage[S->OutSec].push_back(S);
     }
 
   // For each OutputSection that already has an OutputSectionCmd, add an
   // InputSectionDescription at the end for the OrphanSections. This matches
   // GNU ld behavior for scripts such as .text : { *(.text) SYM = .; } the
   // orphan sections such as .text.suffix are added after the symbol assignment
   for (auto &KV : Orphanage) {
     OutputSection *OS = KV.first;
     auto Pos = std::find_if(Opt.Commands.begin(), Opt.Commands.end(),
                             [&](BaseCommand *Base) {
                               auto *Cmd = dyn_cast<OutputSectionCommand>(Base);
                               return Cmd && Cmd->Name == OS->Name;
                             });
     if (Pos == Opt.Commands.end())
       // A new OutputSection, we handle this case in placeOrphanSections()
       continue;
     auto *OSCmd = cast<OutputSectionCommand>(*Pos);
-    if (KV.second.front()->Name.startswith(".ARM.exidx"))
-      // .ARM.exidx sections must be handled in one InputSectionDescription
-      // FIXME: OutputSections still sorts the OutputSection::Sections so we
-      // can give the wrong answer when the order of the input objects does
-      // not match the address assignment.
-      continue;
-
     auto *ISD = make<InputSectionDescription>("");
     OSCmd->Commands.push_back(ISD);
     ISD->Sections = std::move(KV.second);
   }
 }
 
 static bool isTbss(OutputSection *Sec) {
   return (Sec->Flags & SHF_TLS) && Sec->Type == SHT_NOBITS;
MemoryRegion *LinkerScript::findMemoryRegion(OutputSectionCommand *Cmd) {
   }
 
   // Otherwise, no suitable region was found.
   if (Sec->Flags & SHF_ALLOC)
     error("no memory region specified for section '" + Sec->Name + "'");
   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;
+  }
+  AlreadyOutputOS.clear();
+  AlreadyOutputIS.clear();
+}
+
 // 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) {
   OutputSection *Sec = Cmd->Sec;
   if (!Sec)
     return;
 
   if (Cmd->AddrExpr && (Sec->Flags & SHF_ALLOC))
for (BaseCommand *Base : Opt.Commands) {
     else if (auto *Cmd = dyn_cast<AssertCommand>(Base))
       Cmd->Expression();
   }
 }
 
 void LinkerScript::assignAddresses(std::vector<PhdrEntry> &Phdrs) {
   // Assign addresses as instructed by linker script SECTIONS sub-commands.
   Dot = 0;
+  resetAddressState();
   ErrorOnMissingSection = true;
   switchTo(Aether);
 
   for (BaseCommand *Base : Opt.Commands) {
     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base)) {
       assignSymbol(Cmd, false);
       continue;
     }

ELF/OutputSections.cpp

void OutputSection::writeHeaderTo(typename ELFT::Shdr *Shdr) {
   Shdr->sh_name = ShName;
 }
 
 OutputSection::OutputSection(StringRef Name, uint32_t Type, uint64_t Flags)
     : SectionBase(Output, Name, Flags, /*Entsize*/ 0, /*Alignment*/ 1, Type,
                   /*Info*/ 0,
                   /*Link*/ 0) {}
 
-static bool compareByFilePosition(InputSection *A, InputSection *B) {
+static bool compareByFilePosition(InputSectionBase *A, InputSectionBase *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;
template <class ELFT> void OutputSection::maybeCompress() {
 
   // Update section headers.
   Size = sizeof(Elf_Chdr) + CompressedData.size();
   Flags |= SHF_COMPRESSED;
 }
 
 template <class ELFT> void OutputSection::finalize() {
   if ((this->Flags & SHF_LINK_ORDER) && !this->Sections.empty()) {
+    if (Config->Relocatable) {
       std::sort(Sections.begin(), Sections.end(), compareByFilePosition);
       assignOffsets();
-
+    } else {
+      std::vector<std::vector<InputSectionBase *> *> InputRanges =
+          Script->inputSectionRanges(Name);
+      auto &FirstRange = *InputRanges.front();
+      if (InputRanges.size() > 1) {
+        // We must sort over a single InputSectionRange to produce a contiguous
+        // table, account for scripts with *(.ARM.exidx) instead of
+        // *(.ARM.exidx*)
+        // Move all the Sections into a the first range.
+        auto Iter = InputRanges.begin();
+        auto End = InputRanges.end();
+        for (++Iter; Iter != End; ++Iter) {
+          auto *Range = *Iter;
+          FirstRange.insert(FirstRange.begin(), Range->begin(), Range->end());
+          Range->clear();
+        }
+      }
+      std::sort(FirstRange.begin(), FirstRange.end(), compareByFilePosition);
+    }
     // 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,
     // all InputSections in the OutputSection have the same dependency.
     if (auto *D = this->Sections.front()->getLinkOrderDep())
       this->Link = D->OutSec->SectionIndex;
   }
 

ELF/SyntheticSections.cpp

: SyntheticSection(SHF_ALLOC | SHF_LINK_ORDER, SHT_ARM_EXIDX,
                        Config->Wordsize, ".ARM.exidx") {}
 
 // Write a terminating sentinel entry to the end of the .ARM.exidx table.
 // 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 |
 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);
+  std::vector<std::vector<InputSectionBase *> *> InputRanges =
+      Script->inputSectionRanges(this->OutSec->Name);
+  auto RI = InputRanges.front()->rbegin();
+  InputSection *LE = cast<InputSection>(*(++RI));
   InputSection *LC = cast<InputSection>(LE->getLinkOrderDep());
   uint64_t S = LC->OutSec->Addr + LC->getOffset(LC->getSize());
   uint64_t P = this->getVA();
   Target->relocateOne(Buf, R_ARM_PREL31, S - P);
   write32le(Buf + 4, 0x1);
 }
 
 ThunkSection::ThunkSection(OutputSection *OS, uint64_t Off)

ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::run() {
   // finalizeSections does that.
   finalizeSections();
   if (ErrorCount)
     return;
 
   if (Config->Relocatable) {
     assignFileOffsets();
   } else {
-    if (!Script->Opt.HasSections) {
-      fixSectionAlignments();
-      Script->fabricateDefaultCommands(Config->MaxPageSize);
-    }
     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)
if (Target->NeedsThunks) {
     // we need to assign addresses so that we can tell if jump instructions
     // are out of range. This will need to turn into a loop that converges
     // when no more Thunks are added
     ThunkCreator<ELFT> TC;
     if (TC.createThunks(OutputSections))
       applySynthetic({In<ELFT>::MipsGot},
                      [](SyntheticSection *SS) { SS->updateAllocSize(); });
   }
+
+  // The OutputSection finalize below reorders the ARM.exidx sections
+  // using fabricated script commands. For now we must be placed after
+  // createThunks() as that still inserts into OutputSections::Sections.
+  if (!Script->Opt.HasSections) {
+    fixSectionAlignments();
+    Script->fabricateDefaultCommands(Config->MaxPageSize);
+  }
+  if (Config->EMachine == EM_ARM && !Config->Relocatable)
+    Script->assignAddresses(Phdrs);
+
   // Fill other section headers. The dynamic table is finalized
   // at the end because some tags like RELSZ depend on result
   // of finalizing other sections.
   for (OutputSection *Sec : OutputSections)
     Sec->finalize<ELFT>();
 
   // If -compressed-debug-sections is specified, we need to compress
   // .debug_* sections. Do it right now because it changes the size of
   // output sections.
   parallelForEach(OutputSections.begin(), OutputSections.end(),
                   [](OutputSection *S) { S->maybeCompress<ELFT>(); });
 
   // createThunks may have added local symbols to the static symbol table
   applySynthetic({In<ELFT>::SymTab, In<ELFT>::ShStrTab, In<ELFT>::StrTab},
                  [](SyntheticSection *SS) { SS->postThunkContents(); });
 }
 
 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 (!OS || OS->Sections.empty() || Config->Relocatable)
+    return;
+  auto *Sentinel = make<ARMExidxSentinelSection>();
+  OS->addSection(Sentinel);
+  // If the script has a section pattern matching .ARM.exidx we will need
+  // to add the Sentinel to the InputSectionDescription. In the non-script
+  // case fabricateDefaultCommands() will add it for us.
+  if (Script->Opt.HasSections) {
+    std::vector<std::vector<InputSectionBase *> *> InputRanges =
+        Script->inputSectionRanges(OS->Name);
+    if (!InputRanges.empty())
+      InputRanges.front()->push_back(Sentinel);
+  }
 }
 
 // The linker is expected to define SECNAME_start and SECNAME_end
 // symbols for a few sections. This function defines them.
 template <class ELFT> void Writer<ELFT>::addStartEndSymbols() {
   auto Define = [&](StringRef Start, StringRef End, OutputSection *OS) {
     // These symbols resolve to the image base if the section does not exist.
     // A special value -1 indicates end of the section.

test/ELF/arm-exidx-script.s

+// REQUIRES: arm
+// RUN: llvm-mc -filetype=obj -triple=armv7a-none-linux-gnueabi %s -o %t
+// RUN: llvm-mc -filetype=obj -triple=armv7a-none-linux-gnueabi %S/Inputs/arm-exidx-cantunwind.s -o %tcantunwind
+// RUN: echo "SECTIONS { \
+// RUN:          .ARM.exidx 0x11000 : { *(.ARM.exidx*) } \
+// RUN:          .func : { *(.func*) } \
+// RUN:          .text : { *(.text*) } } " > %t.script
+// RUN: ld.lld --script %t.script %t %tcantunwind -o %t2 2>&1
+// RUN: llvm-objdump -s -triple=armv7a-none-linux-gnueabi %t2 | FileCheck %s
+// Check that a linker script that describes .ARM.exidx sections orders the
+// .ARM.exidx sections in ascending order of their link order dependencies.
+ .syntax unified
+ .text
+ .global _start
+_start:
+ .fnstart
+ bx lr
+ .cantunwind
+.fnend
+// Check ascending order of first word of each 2 word entry
+// [PREL31 to target, unwind info]
+// 11000 + 38 = 11038, 11008 + 34 = 1103c ... 11030 + 20 = 11050
+// CHECK:       11000 38000000 01000000 34000000 01000000
+// CHECK-NEXT:  11010 30000000 01000000 2c000000 01000000
+// CHECK-NEXT:  11020 28000000 01000000 24000000 01000000
+// CHECK-NEXT:  11030 20000000 01000000
+// CHECK-NEXT: Contents of section .func:
+// CHECK-NEXT:  11038 1eff2fe1 1eff2fe1 1eff2fe1
+// CHECK-NEXT: Contents of section .text:
+// CHECK-NEXT:  11044 1eff2fe1 1eff2fe1 1eff2fe1