[LLD][ELF] Make SHF_LINK_ORDER sections orphans

[peter.smith]

Summary

I've separated this out from D32233 as it takes a different approach. Overall I think it is an improvement.

The reordering code for SHF_LINK_ORDER works on OutputSection::Sections if any of the InputSections are covered by an InputSectionDescription from a script then the Script->assignAddresses will take precedence and will likely produce an incorrect order.

To make Script->assignAddresses() pick up the order from the OutputSection we make clear all the InputSectionDescriptions::Sections() to make the InputSections orphans.

A theoretical drawback of this approach is that it will ruin any symbols defined by the linker script for the OutputSection. However I think this won't be a problem in practice. The default linker script in ld.bfd is

PROVIDE_HIDDEN (__exidx_start = .);
.ARM.exidx   : { *(.ARM.exidx* .gnu.linkonce.armexidx.*) }
PROVIDE_HIDDEN (__exidx_end = .);

Which won't be troubled by making the InputSections Orphans.

[ruiu]

I'm not sure if I completely understand this patch. Is this effectively the same as handling

.ARM.exidx { <something> }

as

.ARM.exidx {}

?

[peter.smith]

Yes that is what it is doing. If there are no InputSectionDescriptions in an OutputSection, the script falls back to flush() which just outputs any OutputSections::Sections() that have not already been output as part of an InputSection. By clearing the InputSectionDescriptions flush() picks up the ordering from OutputSections::finalize();

In the previous review D32355 I made sure that there was an equivalent of a single .ARM.exidx : { *(.ARM.exidx*) }, essentially putting all .ARM.exidx sections in a single InputSectionDescription.

From what Rafael says, if we want to remove flush() then this is definitely the wrong way to go, perhaps there is a way to make it less clunky to fabricate the linker script for the link order dependencies.

I suggest I abandon this and go back to D32355?

[peter.smith]

This has been superseded by D32612, abandoning as no longer required.

ELF/LinkerScript.h

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);
     }

ELF/OutputSections.cpp

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()) {
+    std::vector<std::vector<InputSectionBase *> *> InputRanges =
+          Script->inputSectionRanges(Name);
+    // Make the sections with link order dependencies orphans to prevent
+    // the script address assignment taking precedent.
+    for (std::vector<InputSectionBase *> *Range : InputRanges)
+      Range->clear();
     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,
     // all InputSections in the OutputSection have the same dependency.
     if (auto *D = this->Sections.front()->getLinkOrderDep())

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