[LLD][ELF] Fix ordering of Mips LA25 Thunks when Linker Script used

[peter.smith]

Summary

For the Mips LA25 Thunks we want the Thunks to precede the target section. The existing code merges these thunks into OutputSections::Sections. This is not sufficient when linker scripts are used as the order of sections and the addresses assigned to them are determined by the InputSectionDescription in the LinkerScript, and thunks are generated after the InputSectionDescription contents have been generated.

This change merges the LA25 Thunks into the InputSectionDescription as well as the OutputSections so that the ordering of the Thunks is maintained. To do this we need to ask the script to calculate the offsets of the OutputSection as all the offsets for script controlled OutputSections are 0 at thunk creation time. We need to ask the script to calculate the offsets as there may be multiple InputSectionDescriptions with location expressions in between them.

The state is cleared at the start of the Linker Script address assignment as we will be running this function twice when Thunks are created.

I've gone for an implementation that merges the result of the createThunks() function into the InputSectionDescription. An alternative is to rewrite createThunks to work on ranges of InputSectionData and have createThunks ask the script for the InputSectionDescription ranges. I'm open to suggestions on how best to work out how scripts and thunks interact as range extension thunks will need to deal with location expressions.

I've based this on top of D30637.

[• rafael]

ELF/LinkerScript.cpp

555

This is similar to what will have to be done for range thunks, no?

691

This points out an annoyance with having the different representations of how we handle linker scripts and non linker script cases.

When we need to add a thunk, we have to figure out where it goes in both cases. For the non linker script case, it is just a list of input sections. For the linker script case it is the a list of commands. This will be particularly annoying for the range extension thunks.

I wonder if this can be simplified. The only thing that comes to mind is to have the non script case create a pseudo linker script when none is given. It would include only output section commands. If we can make creating and executing that script really fast, it should be possible to figure out where to insert thunks only once.

For this it would be critical that the commands are pre resolved, we should not be looking at section names if we don't have too.

[peter.smith]

Abandoning this revision in favour of D31656, which is more general and can handle range extension thunks.

ELF/LinkerScript.h

 class DefinedCommon;
 class ScriptParser;
 class SymbolBody;
 class InputSectionBase;
 class InputSection;
 class OutputSection;
 class OutputSectionFactory;
 class InputSectionBase;
-
+template <class ELFT> class ThunkSection;
 // This represents an expression in the linker script.
 // ScriptParser::readExpr reads an expression and returns an Expr.
 // Later, we evaluate the expression by calling the function
 // with the value of special context variable ".".
 struct Expr {
   std::function<uint64_t(uint64_t)> Val;
   std::function<bool()> IsAbsolute;
 
public:
   ~LinkerScript();
 
   void processCommands(OutputSectionFactory &Factory);
   void addOrphanSections(OutputSectionFactory &Factory);
   void removeEmptyCommands();
   void adjustSectionsBeforeSorting();
   void adjustSectionsAfterSorting();
 
+  void addInlineThunks(StringRef OSName, ArrayRef<ThunkSection<ELFT> *> Thunks);
   std::vector<PhdrEntry> createPhdrs();
   bool ignoreInterpSection();
 
   uint32_t getFiller(StringRef Name);
   void writeDataBytes(StringRef Name, uint8_t *Buf);
   bool hasLMA(StringRef Name);
   bool shouldKeep(InputSectionBase *S);
   void assignOffsets(OutputSectionCommand *Cmd);
private:
   // "ScriptConfig" is a bit too long, so define a short name for it.
   ScriptConfiguration &Opt = *ScriptConfig;
 
   std::vector<size_t> getPhdrIndices(StringRef SectionName);
   size_t getPhdrIndex(const Twine &Loc, StringRef PhdrName);
 
   MemoryRegion *findMemoryRegion(OutputSectionCommand *Cmd, OutputSection *Sec);
 
+  void resetAddressState();
+
   uintX_t Dot;
   std::function<uint64_t()> LMAOffset;
   OutputSection *CurOutSec = nullptr;
   MemoryRegion *CurMemRegion = nullptr;
   uintX_t ThreadBssOffset = 0;
   void switchTo(OutputSection *Sec);
   void flush();
   void output(InputSection *Sec);

ELF/LinkerScript.cpp

 #include "Memory.h"
 #include "OutputSections.h"
 #include "ScriptLexer.h"
 #include "Strings.h"
 #include "SymbolTable.h"
 #include "Symbols.h"
 #include "SyntheticSections.h"
 #include "Target.h"
+#include "Thunks.h"
 #include "Writer.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/SmallString.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/StringSwitch.h"
 #include "llvm/Support/Casting.h"
 #include "llvm/Support/ELF.h"
 #include "llvm/Support/Endian.h"
MemoryRegion *LinkerScript<ELFT>::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.
+template <class ELFT> void LinkerScript<ELFT>::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); }").
 template <class ELFT>
 void LinkerScript<ELFT>::assignOffsets(OutputSectionCommand *Cmd) {
   if (Cmd->LMAExpr) {
     uintX_t D = Dot;
     LMAOffset = [=] { return Cmd->LMAExpr(D) - D; };
   }
if (Cmd->Phdrs.empty())
       Cmd->Phdrs = DefPhdrs;
     else
       DefPhdrs = Cmd->Phdrs;
   }
 
   removeEmptyCommands();
 }
 
+// Thunks are generated after sections are assigned to InputSectionDescriptions
+// as Mips LA25 Thunks precede their target section we must insert them in the
+// right place in the InputSectionDescription to make sure that the script
+// assigns the Thunk the correct address.
+template <class ELFT>
+void LinkerScript<ELFT>::addInlineThunks(
+    StringRef OSName, ArrayRef<ThunkSection<ELFT> *> Thunks) {
+  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 == OSName);
+        return false;
+      });
+  if (OutCmdPos == Opt.Commands.end())
+    // Script does not describe the Output Section
+    return;
+  auto *OutCmd = cast<OutputSectionCommand>(OutCmdPos->get());
+  // Step through the InputSectionDescriptions of this OutputSection and merge
+  // the Thunk into the correct position.
+  auto ThunkIter = Thunks.begin();
+  for (std::unique_ptr<BaseCommand> &Base : OutCmd->Commands) {
+    auto *Cmd = dyn_cast<InputSectionDescription>(Base.get());
+    if (!Cmd || Cmd->Sections.empty())
+      continue;
+
+    if (ThunkIter == Thunks.end())
+      // No more additions to InputSectionDescriptions needed.
+      break;
+
+    std::vector<InputSectionBase *> Tmp;
+    for (auto *ISD : Cmd->Sections) {
+      auto *IS = cast<InputSection>(ISD);
+      if (ThunkIter != Thunks.end() &&
+          (*ThunkIter)->getTargetInputSection() == IS) {
+        // At most one Thunk precedes a target section
+        Tmp.push_back(*ThunkIter);
+        (*ThunkIter)->Assigned = true;
+        ++ThunkIter;
+      }
+      Tmp.push_back(IS);
+    }
+    Cmd->Sections = std::move(Tmp);
+  }
+}
+
 // 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 (OutputSection *Sec : *OutputSections) {
 
     // Continue from where we found it.
     CmdIndex = (Pos - Opt.Commands.begin()) + 1;
   }
 }
 
 template <class ELFT>
 void LinkerScript<ELFT>::assignAddresses(std::vector<PhdrEntry> &Phdrs) {
+  Script<ELFT>::X->resetAddressState();
   // Assign addresses as instructed by linker script SECTIONS sub-commands.
   Dot = 0;
-
   // A symbol can be assigned before any section is mentioned in the linker
   // script. In an DSO, the symbol values are addresses, so the only important
   // section values are:
   // * SHN_UNDEF
   // * SHN_ABS
   // * Any value meaning a regular section.
   // To handle that, create a dummy aether section that fills the void before
   // the linker scripts switches to another section. It has an index of one

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"
 

 static void mergeThunks(OutputSection *OS,
                         std::vector<ThunkSection<ELFT> *> &Thunks) {
   // Order Thunks in ascending OutSecOff
   auto ThunkCmp = [](const ThunkSection<ELFT> *A, const ThunkSection<ELFT> *B) {
     return A->OutSecOff < B->OutSecOff;
   };
   std::stable_sort(Thunks.begin(), Thunks.end(), ThunkCmp);
 
+  // We need to insert the sections into the linker script input section
+  // commands for the correct output order
+  if (Config->EMachine == EM_MIPS && ScriptConfig->HasSections)
+    Script<ELFT>::X->addInlineThunks(OS->Name, Thunks);
+
   // Merge sorted vectors of Thunks and InputSections by OutSecOff
   std::vector<InputSection *> Tmp;
   Tmp.reserve(OS->Sections.size() + Thunks.size());
   auto MergeCmp = [](const InputSection *A, const InputSection *B) {
     // std::merge requires a strict weak ordering.
     if (A->OutSecOff < B->OutSecOff)
       return true;
     if (A->OutSecOff == B->OutSecOff)

ELF/Writer.cpp

Phdrs = Script<ELFT>::X->hasPhdrsCommands() ? Script<ELFT>::X->createPhdrs()
                                                 : createPhdrs();
     addPtArmExid(Phdrs);
     fixHeaders();
   }
 
   // Some architectures use small displacements for jump instructions.
   // It is linker's responsibility to create thunks containing long
   // jump instructions if jump targets are too far. Create thunks.
-  if (Target->NeedsThunks)
+  if (Target->NeedsThunks) {
+    if (ScriptConfig->HasSections)
+      // Assign addresses to sections so that Mips LA25 Thunks can be placed
+      // before the
+      Script<ELFT>::X->assignAddresses(Phdrs);
     createThunks<ELFT>(OutputSections);
-
+  }
   // 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>();
 
   // Dynamic section must be the last one in this list and dynamic
   // symbol table section (DynSymTab) must be the first one.

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