[LLD][ELF] Fix Thunks with placement restrictions and linker scripts

[peter.smith]

Summary

Apologies, now with Summary.

This change is a generalization of D30641 Fix Ordering of Mips LA25 Thunks when Linker Script used so that it works for range extension thunks as well.

This is the messiest change needed to support range extension thunks.

The first part makes it possible to assign addresses multiple times when using a linker script. All this requires us to do is to reset any state accumulated by the last call. The second part deals with the synchronization of OutputSection and LinkerScript data structures.

When a linker script SECTIONS command describes an OutputSection the code that writes out the InputSections contained in the OutputSection use OutputSection.Sections. However the address assignment for linker scripts uses the alternative representation of one or more InputSectionDescription commands to assign the addresses. This is necessary as linker scripts can do things like .text { *(.text.*) . = . +0x100 ; *(.text) } which can't be represented using OutputSection.Sections.

When we come to insert Thunks, the InputSectionDescription(s) and OutputSection.Sections have been synchronized so that the order of sections in InputSectionDescription(s) matches the OutputSection.Sections. If we add any Thunks we must add to both InputSectionDescription(s) and to OutputSections.Sections.

On the assumption that we still have the two representations we have a choice:
1.) Insert thunks into OutputSection.Sections and derive changes for InputSectionDescriptions(s) from it.
2.) Insert thunks into InputSectionDescription(s) and derive changes for OutputSection.Sections from it.

I've chosen the first option as it keeps the code to synchronize the OutputSections in LinkerScripts and doesn't need to use any knowledge of Thunks, the downside is that the synchronization is more complicated. The second option requires us to extract the InputSectionDescriptions from the LinkerScript, make a special case for OutputSections without a Linker Script, makes the efficient allocation of range thunks more complicated, but makes the synchronization simple.

The approach to the synchronization relies on the InputSectionDescription and OutputSection being synchronized prior to Thunks being created. As inserting Thunks never alters the order of non-Thunk sections we can recover the original mapping. The only difficult decision we have to make is if there is a ThunkSection between two InputSectionDescriptions, we must be careful to assign it to the InputSectionDescription that can support our desired OutSecOff.

I don't particularly like that we have to synchronize the representations, but I'm not sure if there is a much better way either. If the linker was driven entirely by InputSectionDescriptions, even without a linker script then no synchronization would be needed, this would be quite a substantial change though.

[peter.smith]

Rebasing patch on top of recent linkerscript refactoring.

[peter.smith]

I'm abandoning the range thunks implementation that inserts into OutputSections in favour of an implementation that inserts into InputSectionDescription.

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, OutputSection *Sec);
 
+  void resetAddressState();
+
   void switchTo(OutputSection *Sec);
   void flush();
   void output(InputSection *Sec);
   void process(BaseCommand &Base);
 
   OutputSection *Aether;
   bool ErrorOnMissingSection = false;
 
public:
   bool isDefined(StringRef S);
 
   std::vector<OutputSection *> *OutputSections;
   void addOrphanSections(OutputSectionFactory &Factory);
   void removeEmptyCommands();
   void adjustSectionsBeforeSorting();
   void adjustSectionsAfterSorting();
 
+  void syncWithOS(OutputSection* OS);
+
   std::vector<PhdrEntry> createPhdrs();
   bool ignoreInterpSection();
 
   uint32_t getFiller(StringRef Name);
   bool hasLMA(StringRef Name);
   bool shouldKeep(InputSectionBase *S);
   void assignOffsets(OutputSectionCommand *Cmd);
   void placeOrphanSections();

ELF/LinkerScript.cpp

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 = findSection(Cmd->Name, *OutputSections);
   if (!Sec)
     return;
 
   if (Cmd->AddrExpr && Sec->Flags & SHF_ALLOC)
if (Cmd->Phdrs.empty())
       Cmd->Phdrs = DefPhdrs;
     else
       DefPhdrs = Cmd->Phdrs;
   }
 
   removeEmptyCommands();
 }
 
+// Thunks are added to an OutputSection after InputSections are assigned to
+// InputSectionDescriptions. We need to resynchronize the OS->Sections and the
+// InputSectionDescriptions so that the Thunks are assigned the correct address
+//
+// The non-Thunk InputSections in OutputSection must match the order and
+// OutSecOff of their counterparts in the InputSectionDescriptions.
+void LinkerScript::syncWithOS(OutputSection *OS) {
+  // Find Commands associated with this OS
+  auto OutCmdPos = std::find_if(
+      Opt.Commands.begin(), Opt.Commands.end(),
+      [=](const std::unique_ptr<BaseCommand> &Cmd) {
+        if (auto *OSCmd = dyn_cast<OutputSectionCommand>(Cmd.get()))
+          return (OSCmd->Name == OS->Name);
+        return false;
+      });
+  if (OutCmdPos == Opt.Commands.end())
+    // LinkerScript does not describe the OS, no sync to do
+    return;
+
+  auto *OutCmd = cast<OutputSectionCommand>(OutCmdPos->get());
+
+  // To synchonize an InputSectionDescription we find the OutSecOff of the first
+  // InputSection in the next InputSectionDescription. We then transfer over
+  // all InputSections from OS->Section with a lower OutSecOff. This makes sure
+  // that Thunks added after the last InputSection in an InputSectionDescription
+  // get assigned to that the InputSectionDescription.
+  // ordered OS->Sections.
+
+  auto FindNextISDCmd =
+      [](std::vector<std::unique_ptr<BaseCommand>>::iterator Begin,
+         std::vector<std::unique_ptr<BaseCommand>>::iterator End) {
+        for (auto CmdIter = Begin; CmdIter != End; ++CmdIter) {
+          auto *Cmd = dyn_cast<InputSectionDescription>((*CmdIter).get());
+          if (Cmd && !Cmd->Sections.empty())
+            return CmdIter;
+        }
+        return End;
+      };
+  // Range to copy from OS->Sections
+  auto ISFromOSIter = OS->Sections.begin();
+  auto ISFromOSEnd = OS->Sections.end();
+
+  auto CmdIterEnd = OutCmd->Commands.end();
+  auto CmdIter = FindNextISDCmd(OutCmd->Commands.begin(), CmdIterEnd);
+
+  while (CmdIter != CmdIterEnd) {
+    auto *Cmd = cast<InputSectionDescription>((*CmdIter).get());
+    auto NextCmdIter = FindNextISDCmd(CmdIter, CmdIterEnd);
+    if (NextCmdIter == CmdIterEnd)
+      // No more InputSection descriptions, limit is remaining InputSections
+      ISFromOSEnd = OS->Sections.end();
+    else {
+      // Limit is first InputSection with OutSecOff >= the OutSecOff the first
+      // InputSection from the next InputSectionDescription
+      auto *NextCmd = cast<InputSectionDescription>((*NextCmdIter).get());
+      auto NextIS = cast<InputSection>(NextCmd->Sections.front());
+      ISFromOSEnd = std::find_if(ISFromOSIter, OS->Sections.end(),
+                                 [NextIS](InputSection *IS) {
+                                   return IS->OutSecOff >= NextIS->OutSecOff;
+                                 });
+    }
+    // Copy range from OS->Sections to InputSectionDescription
+    std::vector<InputSectionBase *> Tmp;
+    for (; ISFromOSIter != ISFromOSEnd; ++ISFromOSIter)
+      Tmp.push_back(*ISFromOSIter);
+    Cmd->Sections = std::move(Tmp);
+    CmdIter = NextCmdIter;
+  }
+}
+
 // When placing orphan sections, we want to place them after symbol assignments
 // so that an orphan after
 //   begin_foo = .;
 //   foo : { *(foo) }
 //   end_foo = .;
 // doesn't break the intended meaning of the begin/end symbols.
 // We don't want to go over sections since Writer<ELFT>::sortSections is the
 // one in charge of deciding the order of the sections.
for (const std::unique_ptr<BaseCommand> &Base : Opt.Commands) {
     else if (auto *Cmd = dyn_cast<AssertCommand>(Base.get()))
       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 (const std::unique_ptr<BaseCommand> &Base : Opt.Commands) {
     if (auto *Cmd = dyn_cast<SymbolAssignment>(Base.get())) {
       assignSymbol(Cmd);
       continue;
     }

ELF/Relocations.cpp

 // because it doesn't know about the output file nor the output file buffer.
 // It instead stores Relocation objects to InputSection's Relocations
 // vector to let it apply later in InputSection::writeTo.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Relocations.h"
 #include "Config.h"
+#include "LinkerScript.h"
 #include "Memory.h"
 #include "OutputSections.h"
 #include "Strings.h"
 #include "SymbolTable.h"
 #include "SyntheticSections.h"
 #include "Target.h"
 #include "Thunks.h"
 
if (A->OutSecOff == B->OutSecOff)
       if (auto *TA = dyn_cast<ThunkSection>(A))
         if (TA && TA->getTargetInputSection() == B)
           return true;
     return false;
   };
   std::merge(OS->Sections.begin(), OS->Sections.end(), Thunks.begin(),
              Thunks.end(), std::back_inserter(Tmp), MergeCmp);
   OS->Sections = std::move(Tmp);
+
+  // We need to insert the sections into the linker script input section
+  // commands for the correct output order
+  if (Script->Opt.HasSections)
+    Script->syncWithOS(OS);
   OS->assignOffsets();
 }
 
 template <class ELFT>
 ThunkSection *ThunkCreator<ELFT>::getOSThunkSec(ThunkSection *&TS,
                                                 OutputSection *OS) {
   if (TS == nullptr) {
     uint32_t Off = 0;

ELF/Writer.cpp

template <class ELFT> void Writer<ELFT>::finalizeSections() {
   // jump instructions if jump targets are too far. Create thunks.
   if (Target->NeedsThunks) {
     // FIXME: only ARM Interworking and Mips LA25 Thunks are implemented,
     // these
     // do not require address information. To support range extension Thunks
     // 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
+    auto AddressesForThunks = [&]() {
+      if (Script->Opt.HasSections)
+        Script->assignAddresses(Phdrs);
+      else if (!Config->Relocatable) {
+        fixSectionAlignments();
+        assignAddresses();
+      }
+    };
+    AddressesForThunks();
     ThunkCreator<ELFT> TC;
     if (TC.createThunks(OutputSections))
       applySynthetic({In<ELFT>::MipsGot},
                      [](SyntheticSection *SS) { SS->updateAllocSize(); });
   }
   // Fill other section headers. The dynamic table is finalized
   // at the end because some tags like RELSZ depend on result
   // of finalizing other sections.

test/ELF/mips-npic-call-pic-script.s

+# REQUIRES: mips
+# Check LA25 stubs creation. This stub code is necessary when
+# non-PIC code calls PIC function.
+# RUN: echo "SECTIONS { .out 0x20000 : { *(.text.*) . = . + 0x100 ;  *(.text) }  }" > %t1.script
+# RUN: llvm-mc -filetype=obj -triple=mips-unknown-linux \
+# RUN:   %p/Inputs/mips-fpic.s -o %t-fpic.o
+# RUN: llvm-mc -filetype=obj -triple=mips-unknown-linux \
+# RUN:   %p/Inputs/mips-fnpic.s -o %t-fnpic.o
+# RUN: ld.lld -r %t-fpic.o %t-fnpic.o -o %t-sto-pic.o
+# RUN: llvm-mc -filetype=obj -triple=mips-unknown-linux \
+# RUN:   %p/Inputs/mips-pic.s -o %t-pic.o
+# RUN: llvm-mc -filetype=obj -triple=mips-unknown-linux %s -o %t-npic.o
+# RUN: ld.lld --script %t1.script %t-npic.o %t-pic.o %t-sto-pic.o -o %t.exe --Map=m.txt
+# RUN: llvm-objdump -d %t.exe | FileCheck %s
+
+# CHECK: Disassembly of section .out:
+# CHECK-NEXT: __LA25Thunk_foo1a:
+# CHECK-NEXT:    20000:       3c 19 00 02     lui     $25, 2
+# CHECK-NEXT:    20004:       08 00 80 08     j       131104 <foo1a>
+# CHECK-NEXT:    20008:       27 39 00 20     addiu   $25, $25, 32
+# CHECK-NEXT:    2000c:       00 00 00 00     nop
+# CHECK: __LA25Thunk_foo1b:
+# CHECK-NEXT:    20010:       3c 19 00 02     lui     $25, 2
+# CHECK-NEXT:    20014:       08 00 80 09     j       131108 <foo1b>
+# CHECK-NEXT:    20018:       27 39 00 24     addiu   $25, $25, 36
+# CHECK-NEXT:    2001c:       00 00 00 00     nop
+# CHECK: foo1a:
+# CHECK-NEXT:    20020:       00 00 00 00     nop
+# CHECK: foo1b:
+# CHECK-NEXT:    20024:       00 00 00 00     nop
+# CHECK: __LA25Thunk_foo2:
+# CHECK-NEXT:    20028:       3c 19 00 02     lui     $25, 2
+# CHECK-NEXT:    2002c:       08 00 80 10     j       131136 <foo2>
+# CHECK-NEXT:    20030:       27 39 00 40     addiu   $25, $25, 64
+# CHECK-NEXT:    20034:       00 00 00 00     nop
+# CHECK-NEXT:    20038:       00 00 00 00     nop
+# CHECK-NEXT:    2003c:       00 00 00 00     nop
+# CHECK: foo2:
+# CHECK-NEXT:    20040:       00 00 00 00     nop
+# CHECK-NEXT:    20044:       00 00 00 00     nop
+# CHECK-NEXT:    20048:       00 00 00 00     nop
+# CHECK-NEXT:    2004c:       00 00 00 00     nop
+# CHECK-NEXT:    20050:       00 00 00 00     nop
+# CHECK-NEXT:    20054:       00 00 00 00     nop
+# CHECK-NEXT:    20058:       00 00 00 00     nop
+# CHECK-NEXT:    2005c:       00 00 00 00     nop
+# CHECK-NEXT:    20060:       00 00 00 00     nop
+# CHECK-NEXT:    20064:       00 00 00 00     nop
+# CHECK-NEXT:    20068:       00 00 00 00     nop
+# CHECK-NEXT:    2006c:       00 00 00 00     nop
+# CHECK-NEXT:    20070:       00 00 00 00     nop
+# CHECK-NEXT:    20074:       00 00 00 00     nop
+# CHECK-NEXT:    20078:       00 00 00 00     nop
+# CHECK-NEXT:    2007c:       00 00 00 00     nop
+# CHECK-NEXT:    20080:       00 00 00 00     nop
+# CHECK-NEXT:    20084:       00 00 00 00     nop
+# CHECK-NEXT:    20088:       00 00 00 00     nop
+# CHECK-NEXT:    2008c:       00 00 00 00     nop
+# CHECK-NEXT:    20090:       00 00 00 00     nop
+# CHECK-NEXT:    20094:       00 00 00 00     nop
+# CHECK-NEXT:    20098:       00 00 00 00     nop
+# CHECK-NEXT:    2009c:       00 00 00 00     nop
+# CHECK-NEXT:    200a0:       00 00 00 00     nop
+# CHECK-NEXT:    200a4:       00 00 00 00     nop
+# CHECK-NEXT:    200a8:       00 00 00 00     nop
+# CHECK-NEXT:    200ac:       00 00 00 00     nop
+# CHECK-NEXT:    200b0:       00 00 00 00     nop
+# CHECK-NEXT:    200b4:       00 00 00 00     nop
+# CHECK-NEXT:    200b8:       00 00 00 00     nop
+# CHECK-NEXT:    200bc:       00 00 00 00     nop
+# CHECK-NEXT:    200c0:       00 00 00 00     nop
+# CHECK-NEXT:    200c4:       00 00 00 00     nop
+# CHECK-NEXT:    200c8:       00 00 00 00     nop
+# CHECK-NEXT:    200cc:       00 00 00 00     nop
+# CHECK-NEXT:    200d0:       00 00 00 00     nop
+# CHECK-NEXT:    200d4:       00 00 00 00     nop
+# CHECK-NEXT:    200d8:       00 00 00 00     nop
+# CHECK-NEXT:    200dc:       00 00 00 00     nop
+# CHECK-NEXT:    200e0:       00 00 00 00     nop
+# CHECK-NEXT:    200e4:       00 00 00 00     nop
+# CHECK-NEXT:    200e8:       00 00 00 00     nop
+# CHECK-NEXT:    200ec:       00 00 00 00     nop
+# CHECK-NEXT:    200f0:       00 00 00 00     nop
+# CHECK-NEXT:    200f4:       00 00 00 00     nop
+# CHECK-NEXT:    200f8:       00 00 00 00     nop
+# CHECK-NEXT:    200fc:       00 00 00 00     nop
+# CHECK-NEXT:    20100:       00 00 00 00     nop
+# CHECK-NEXT:    20104:       00 00 00 00     nop
+# CHECK-NEXT:    20108:       00 00 00 00     nop
+# CHECK-NEXT:    2010c:       00 00 00 00     nop
+# CHECK-NEXT:    20110:       00 00 00 00     nop
+# CHECK-NEXT:    20114:       00 00 00 00     nop
+# CHECK-NEXT:    20118:       00 00 00 00     nop
+# CHECK-NEXT:    2011c:       00 00 00 00     nop
+# CHECK-NEXT:    20120:       00 00 00 00     nop
+# CHECK-NEXT:    20124:       00 00 00 00     nop
+# CHECK-NEXT:    20128:       00 00 00 00     nop
+# CHECK-NEXT:    2012c:       00 00 00 00     nop
+# CHECK-NEXT:    20130:       00 00 00 00     nop
+# CHECK-NEXT:    20134:       00 00 00 00     nop
+# CHECK-NEXT:    20138:       00 00 00 00     nop
+# CHECK-NEXT:    2013c:       00 00 00 00     nop
+# CHECK-NEXT:    20140:       00 00 00 00     nop
+# CHECK-NEXT:    20144:       00 00 00 00     nop
+# CHECK-NEXT:    20148:       00 00 00 00     nop
+# CHECK-NEXT:    2014c:       00 00 00 00     nop
+# CHECK: __start:
+# CHECK-NEXT:    20150:       0c 00 80 00     jal     131072 <__LA25Thunk_foo1a>
+# CHECK-NEXT:    20154:       00 00 00 00     nop
+# CHECK-NEXT:    20158:       0c 00 80 0a     jal     131112 <__LA25Thunk_foo2>
+# CHECK-NEXT:    2015c:       00 00 00 00     nop
+# CHECK-NEXT:    20160:       0c 00 80 04     jal     131088 <__LA25Thunk_foo1b>
+# CHECK-NEXT:    20164:       00 00 00 00     nop
+# CHECK-NEXT:    20168:       0c 00 80 0a     jal     131112 <__LA25Thunk_foo2>
+# CHECK-NEXT:    2016c:       00 00 00 00     nop
+# CHECK-NEXT:    20170:       0c 00 80 60     jal     131456 <__LA25Thunk_fpic>
+# CHECK-NEXT:    20174:       00 00 00 00     nop
+# CHECK-NEXT:    20178:       0c 00 80 68     jal     131488 <fnpic>
+# CHECK-NEXT:    2017c:       00 00 00 00     nop
+# CHECK: __LA25Thunk_fpic:
+# CHECK-NEXT:    20180:       3c 19 00 02     lui     $25, 2
+# CHECK-NEXT:    20184:       08 00 80 64     j       131472 <fpic>
+# CHECK-NEXT:    20188:       27 39 01 90     addiu   $25, $25, 400
+# CHECK-NEXT:    2018c:       00 00 00 00     nop
+# CHECK: fpic:
+# CHECK-NEXT:    20190:       00 00 00 00     nop
+# CHECK-NEXT:    20194:       00 00 00 00     nop
+# CHECK-NEXT:    20198:       00 00 00 00     nop
+# CHECK-NEXT:    2019c:       00 00 00 00     nop
+# CHECK: fnpic:
+# CHECK-NEXT:    201a0:       00 00 00 00     nop
+
+  .text
+  .globl __start
+__start:
+  jal foo1a
+  jal foo2
+  jal foo1b
+  jal foo2
+  jal fpic
+  jal fnpic