[LLD][ELF] Account for range thunk that has drifted out of range

[peter.smith]

Summary

Adding range extension thunks to an OutputSection alters some InputSection VAs, including the VAs of the thunks themselves. In rare cases a call to a thunk that was valid on pass N, is not valid in some later pass N + K. We account for this by detecting if a caller can't reach the thunk, reseting the relocation to the original and recreating the Thunk.

[peter.smith]

Rebased to take account of changes in D31654

[peter.smith]

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

ELF/Relocations.h

public:
   bool createThunks(ArrayRef<OutputSection *> OutputSections);
 
 private:
   void mergeThunks();
   void createInitialThunkSections(ArrayRef<OutputSection *> OutputSections);
   ThunkSection *getOSThunkSec(OutputSection *OS, InputSection *IS,
                               uint32_t Type, uint64_t Src);
   ThunkSection *getISThunkSec(InputSection *IS, OutputSection *OS);
-  std::pair<Thunk *, bool> getThunk(SymbolBody &Body, uint32_t Type,
+  std::pair<Thunk *, bool> getThunk(SymbolBody *Body, uint32_t Type,
                                     uint64_t SrcAddr);
+  Thunk *getThunkAtSymbol(SymbolBody *Body);
   ThunkSection *addThunkSection(OutputSection *OS, uint64_t Off);
 
   uint32_t Pass = 0;
   // Record all the available Thunks for a Symbol
   llvm::DenseMap<SymbolBody *, std::vector<Thunk *>> ThunkedSymbols;
   // Find a Thunk from the Thunks symbol definition, we can use this to find
   // the Thunk from a relocation to the Thunks symbol definition.
   llvm::DenseMap<SymbolBody *, Thunk *> Thunks;

ELF/Relocations.cpp

if (TS)
     return TS;
   auto *TOS = cast<OutputSection>(IS->OutSec);
   TS = addThunkSection(TOS, IS->OutSecOff);
   ThunkedSections[IS] = TS;
   return TS;
 }
 
 template <class ELFT>
-std::pair<Thunk *, bool> ThunkCreator<ELFT>::getThunk(SymbolBody &Body,
+std::pair<Thunk *, bool> ThunkCreator<ELFT>::getThunk(SymbolBody *Body,
                                                       uint32_t Type,
                                                       uint64_t SrcAddr) {
   Thunk *T = nullptr;
-  auto Res = ThunkedSymbols.insert({&Body, std::vector<Thunk *>()});
+  auto Res = ThunkedSymbols.insert({Body, std::vector<Thunk *>()});
   if (Res.second == false) {
     // Check existing Thunks for Body to see if they can be reused
     for (Thunk *ET : Res.first->second)
       if (ET->compatibleWith(Type) &&
           Target->inBranchRange(Type, SrcAddr, ET->ThunkSym->getVA())) {
         T = ET;
         return std::make_pair(T, Res.second);
       }
   }
   // No existing compatible Thunk in range, create a new one
-  T = addThunk<ELFT>(Type, Body);
+  T = addThunk<ELFT>(Type, *Body);
   Res.first->second.push_back(T);
   return std::make_pair(T, true);
 }
 
+// Given a relocation to a symbol, check to see if that symbol is an existing
+// Thunk and if it is return it.
+template <class ELFT>
+Thunk *ThunkCreator<ELFT>::getThunkAtSymbol(SymbolBody *Sym) {
+  auto Res = Thunks.find(Sym);
+  if (Res != Thunks.end())
+    return Res->second;
+  return nullptr;
+}
+
 // Make a new ThunkSection at offset Off and it to the persistent and per pass
 // records per OutputSection.
 template <class ELFT>
 ThunkSection *ThunkCreator<ELFT>::addThunkSection(OutputSection *OS,
                                                   uint64_t Off) {
   auto *TS = make<ThunkSection>(OS, Off);
   ThunkSections[OS].push_back(TS);
   NewThunkSections[OS].push_back(TS);
bool ThunkCreator<ELFT>::createThunks(
   // ThunkSections back into the OutputSection as ThunkSections are not always
   // inserted into the same OutputSection as the caller.
   for (OutputSection *OS : OutputSections) {
     for (InputSection *IS : OS->Sections) {
       if (dyn_cast<ThunkSection>(IS) != nullptr)
         // Do not create Thunks for relocations from Thunks
         continue;
       for (Relocation &Rel : IS->Relocations) {
-        SymbolBody &Body = *Rel.Sym;
         uint64_t SrcAddr = OS->Addr + IS->OutSecOff + Rel.Offset;
-        // If this Relocation is using a Thunk, use it.
-        if (Thunks.find(&Body) != Thunks.end())
+
+        // If this Relocation is using a Thunk, use it if it hasn't gone out
+        // of range. If it has we revert back to the original Target.
+        if (Thunk *ET = getThunkAtSymbol(Rel.Sym)) {
+          if (Target->inBranchRange(Rel.Type, SrcAddr, Rel.Sym->getVA()))
             continue;
-        if (Target->needsThunk(Rel.Expr, Rel.Type, IS->File, SrcAddr, Body)) {
+          Rel.Sym = &ET->Destination;
+          if (Rel.Sym->isInPlt())
+            Rel.Expr = toPlt(Rel.Expr);
+        }
+
+        if (Target->needsThunk(Rel.Expr, Rel.Type, IS->File, SrcAddr,
+                               *Rel.Sym)) {
           Thunk *T;
           bool IsNew;
-          std::tie(T, IsNew) = getThunk(Body, Rel.Type, SrcAddr);
+          std::tie(T, IsNew) = getThunk(Rel.Sym, Rel.Type, SrcAddr);
           if (IsNew) {
             AddressesChanged = true;
             // Find or create a ThunkSection for the new Thunk
             ThunkSection *TS;
             if (auto *TIS = T->getTargetInputSection())
               TS = getISThunkSec(TIS, OS);
             else
               TS = getOSThunkSec(OS, IS, Rel.Type, SrcAddr);

ELF/Thunks.h

 // after executing transfers control to the callee. Typical uses of Thunks
 // include transferring control from non-pi to pi and changing state on
 // targets like ARM.
 //
 // Thunks can be created for DefinedRegular, Shared and Undefined Symbols.
 // Thunks are assigned to synthetic ThunkSections
 class Thunk {
 public:
-  Thunk(const SymbolBody &Destination);
+  Thunk(SymbolBody &Destination);
   virtual ~Thunk();
 
   virtual uint32_t size() const { return 0; }
   virtual void writeTo(uint8_t *Buf, ThunkSection &IS) const {}
 
   // All Thunks must define at least one symbol ThunkSym so that we can
   // redirect relocations to it.
   virtual void addSymbols(ThunkSection &IS) {}
 
   // Some Thunks must be placed immediately before their Target as they elide
   // a branch and fall through to the first Symbol in the Target.
   virtual InputSection *getTargetInputSection() const { return nullptr; }
 
   // To reuse a Thunk the caller as identified by the RelocType must be
   // compatible with it.
   virtual bool compatibleWith(uint32_t RelocType) const { return true; }
 
   // The alignment requirement for this Thunk, defaults to the size of the
   // typical code section alignment.
-  const SymbolBody &Destination;
+  SymbolBody &Destination;
   SymbolBody *ThunkSym;
   uint64_t Offset;
   uint32_t alignment = 4;
 };
 
 // For a Relocation to symbol S create a Thunk to be added to a synthetic
 // ThunkSection. At present there are implementations for ARM and Mips Thunks.
 template <class ELFT> Thunk *addThunk(uint32_t RelocType, SymbolBody &S);
 
 } // namespace elf
 } // namespace lld
 
 #endif

ELF/Thunks.cpp

 namespace elf {
 
 namespace {
 
 // Specific ARM Thunk implementations. The naming convention is:
 // Source State, TargetState, Target Requirement, ABS or PI, Range
 template <class ELFT> class ARMV7ABSLongThunk final : public Thunk {
 public:
-  ARMV7ABSLongThunk(const SymbolBody &Dest) : Thunk(Dest) {}
+  ARMV7ABSLongThunk(SymbolBody &Dest) : Thunk(Dest) {}
 
   uint32_t size() const override { return 12; }
   void writeTo(uint8_t *Buf, ThunkSection &IS) const override;
   void addSymbols(ThunkSection &IS) override;
   bool compatibleWith(uint32_t RelocType) const override;
 };
 
 template <class ELFT> class ARMV7PILongThunk final : public Thunk {
 public:
-  ARMV7PILongThunk(const SymbolBody &Dest) : Thunk(Dest) {}
+  ARMV7PILongThunk(SymbolBody &Dest) : Thunk(Dest) {}
 
   uint32_t size() const override { return 16; }
   void writeTo(uint8_t *Buf, ThunkSection &IS) const override;
   void addSymbols(ThunkSection &IS) override;
   bool compatibleWith(uint32_t RelocType) const override;
 };
 
 template <class ELFT> class ThumbV7ABSLongThunk final : public Thunk {
 public:
-  ThumbV7ABSLongThunk(const SymbolBody &Dest) : Thunk(Dest) {
-    this->alignment = 2;
-  }
+  ThumbV7ABSLongThunk(SymbolBody &Dest) : Thunk(Dest) { this->alignment = 2; }
 
   uint32_t size() const override { return 10; }
   void writeTo(uint8_t *Buf, ThunkSection &IS) const override;
   void addSymbols(ThunkSection &IS) override;
   bool compatibleWith(uint32_t RelocType) const override;
 };
 
 template <class ELFT> class ThumbV7PILongThunk final : public Thunk {
 public:
-  ThumbV7PILongThunk(const SymbolBody &Dest) : Thunk(Dest) {
-    this->alignment = 2;
-  }
+  ThumbV7PILongThunk(SymbolBody &Dest) : Thunk(Dest) { this->alignment = 2; }
 
   uint32_t size() const override { return 12; }
   void writeTo(uint8_t *Buf, ThunkSection &IS) const override;
   void addSymbols(ThunkSection &IS) override;
   bool compatibleWith(uint32_t RelocType) const override;
 };
 
 // MIPS LA25 thunk
 template <class ELFT> class MipsThunk final : public Thunk {
 public:
-  MipsThunk(const SymbolBody &Dest) : Thunk(Dest) {}
+  MipsThunk(SymbolBody &Dest) : Thunk(Dest) {}
 
   uint32_t size() const override { return 16; }
   void writeTo(uint8_t *Buf, ThunkSection &IS) const override;
   void addSymbols(ThunkSection &IS) override;
   InputSection *getTargetInputSection() const override;
 };
 
 } // end anonymous namespace

 }
 
 template <class ELFT>
 InputSection *MipsThunk<ELFT>::getTargetInputSection() const {
   auto *DR = dyn_cast<DefinedRegular>(&this->Destination);
   return dyn_cast<InputSection>(DR->Section);
 }
 
-Thunk::Thunk(const SymbolBody &D) : Destination(D), Offset(0) {}
+Thunk::Thunk(SymbolBody &D) : Destination(D), Offset(0) {}
 
 Thunk::~Thunk() = default;
 
 // Creates a thunk for Thumb-ARM interworking.
 template <class ELFT> static Thunk *addThunkArm(uint32_t Reloc, SymbolBody &S) {
   // ARM relocations need ARM to Thumb interworking Thunks.
   // Thumb relocations need Thumb to ARM relocations.
   // Use position independent Thunks if we require position independent code.