[ELF] Implement infrastructure for thunk code creation

[atanasyan]

Summary

Some targets might require creation of thunks. For example, MIPS targets require stubs to call PIC code from non-PIC one. The patch implements infrastructure for thunk code creation and provides support for MIPS LA25 stubs. Any MIPS PIC code function is invoked with its address in register $t9. So if we have a branch instruction from non-PIC code to the PIC one we cannot make the jump directly and need to create a small stub to save the target function address.
See page 3-38 ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf

• In relocation scanning phase we ask target about thunk creation necessity by calling TagetInfo::needsThunk method. The InputSection class maintains list of Symbols requires thunk creation.

• Reassigning offsets performed for each input sections after relocation scanning complete because position of each section might change due thunk creation.

• The patch introduces new dedicated value for DefinedSynthetic symbols DefinedSynthetic::SectionEnd. Synthetic symbol with that value always points to the end of the corresponding output section. That allows to escape updating synthetic symbols if output sections sizes changes after relocation scanning due thunk creation.

• In the InputSection::writeTo method we write thunks after corresponding input section. Each thunk is written by calling TargetInfo::writeThunk method.

• The patch supports the only type of thunk code for each target. For now, it is enough.

[ruiu]

I'm still reading this patch, but does it work for all cases? When you want to create a thunk for a short-range jump instruction, you want to locate that thunk within the range of the instruction. Output sections can be large. Putting thunks at end of each output section will work?

[atanasyan]

In D17934#369150, @ruiu wrote:

I'm still reading this patch, but does it work for all cases? When you want to create a thunk for a short-range jump instruction, you want to locate that thunk within the range of the instruction. Output sections can be large. Putting thunks at end of each output section will work?

I had a solution which puts stubs in the beginning of the corresponding input section. In that case the risk to get too long jump is smaller. But this solution seemed to me over-complicated a bit. Let me think again till tomorrow. Maybe I revert that solution.

[ruiu]

This is just an idea and I'm not suggesting that that is better, but you
can scan a list of input sections and insert stub sections to the list,
instead of appending stub sections to input/output sections.

[atanasyan]

Write thunks before corresponding InputSection's to reduce risk of getting too long jump.

[ruiu]

ELF/OutputSections.cpp

806 ↗

(On Diff #50131)

Using a hash table feels a bit tricky. Can you add a pointer to SymbolBody to point to a thunk?

ELF/Target.cpp

1687 ↗

(On Diff #50131)

Needs a comment.

1721 ↗

(On Diff #50131)

Please run clang-format-diff.

1733 ↗

(On Diff #50131)

We have using namespace llvm::ELF.

1735 ↗

(On Diff #50131)

We usually name an object of type Elf_Sym ElfSym. In this case, the return type of RHS is still our own symbol type, so I'd name differently, say just Sym, D, Defined or something like that.

1739–1745 ↗

(On Diff #50131)

This can be

return (ElfSym->Section->getFile()->getObj().getHeader()->e_flags & EF_MIPS_PIC) ||
       (ElfSym->Sym.st_other & STO_MIPS_MIPS16) == STO_MIPS_PIC;

ELF/Writer.cpp

346–352 ↗

(On Diff #50131)

I don't like to add new code to this function because this function is overloaded. Particularly, when this code will be executed is not very obvious because if a condition above is true and it reaches a continue, this code will be skipped. Will this code be skipped for all correct cases?

Can you create a new loop over relocations and move this code there?

1050–1051 ↗

(On Diff #50131)

This seems a bit odd.

If we always reassign offsets, then we don't want to reassign offsets at all. Instead, we want to assign offsets right here only once.

1068–1072 ↗

(On Diff #50131)

I don't understand what this is supposed to do?

1183 ↗

(On Diff #50131)

What is this change for?

[atanasyan]

ELF/OutputSections.cpp

806 ↗

(On Diff #50131)

I need a link between input section and corresponding set of thunks to put the thunks in the right place during a "write" phase. I can add pointer to ThunkChunk to the InputSectionBase class. That will allow to remove this DenseMap. Is it acceptable to you?

ELF/Target.cpp

1687 ↗

(On Diff #50131)

Will do

1721 ↗

(On Diff #50131)

OK

1733 ↗

(On Diff #50131)

OK

1735 ↗

(On Diff #50131)

OK

1739–1745 ↗

(On Diff #50131)

OK

ELF/Writer.cpp

346–352 ↗

(On Diff #50131)

OK. I will try to do so.

1050–1051 ↗

(On Diff #50131)

You are right. The assignOffsets is better name.

1068–1072 ↗

(On Diff #50131)

This and the next change are related. Now we add synthetic symbols pointing to beginning and end of output sections before relocation scanning phase. In this patch output section size might change during the relocation scanning. So synthetic symbols point to the end of sections need to be updated. There is a couple of possible solutions:

• Add synthetic symbols after the relocation scanning. Not sure that this does not affect something in relocation scanning phase.
• Use special value DefinedSynthetic<ELFT>::End to mark symbol that need to point to the end of sections. Update such symbols with the correct value later.

In this patch I use the second solution. Do you think it is safe to add synthetic symbols after the relocation scanning?

[ruiu]

ELF/OutputSections.cpp

806 ↗

(On Diff #50131)

I think that instead of attaching a chunk to an InputSection, we may be able to define a new type of (synthesized) InputSection for a thunk. Then we can keep OutputSection to have a flat list of InputSections instead of InputSections + their attachment. It may be cleaner approach IMO.

In that design, we can make a symbol have a pointer to a thunk input section. getThunkVA() returns the VA of the thunk input section, so it just have to call getVA on the thunk section.

What do you think? I'm not sure if this is really cleaner, but I'd think it's worth to try.

ELF/Writer.cpp

1068–1072 ↗

(On Diff #50131)

OK. So if we keep the output section to have a flat list of input sections instead of input sections + their chunks, the size of the output section wouldn't change during relocation scanning phase, right?

[atanasyan]

ELF/OutputSections.cpp

806 ↗

(On Diff #50131)

Now the root of input section hierarchy InputSectionBase class is tightly related to ELF input section. Its constructor requires reference to ObjectFile and Elf_Shdr. If we want to introduce something like SyntheticInputSection which is unrelated to and file and ELF header we have to create new root base class and inherit SyntheticInputSection and InputSectionBase. One more problem is that OutputSection::Sections container contains pointers to InputSection objects and it is not clear how to mix InputSection and SyntheticInputSection in the same container.

ELF/Writer.cpp

1068–1072 ↗

(On Diff #50131)

Before the scanning phase we know nothing about thunks. During the scanning we either add chunks to OutputSections or create synthetic input sections and add them to OutputSections too. In any case the size will change.

[atanasyan]

Fixed minor issues found on review. The open questions are updating synthetic symbols values and necessity to introduce new SyntheticInputSction class.

[atanasyan]

Rebased the patch.

[ruiu]

This looks still a bit too intrusive. The code to handles thunks appears too many places.

Maybe we should handle thunks as a separate output section? Then we don't need to add addThunk to the regular output section class and we don't have to update the code to calculate section size and offsets.

[atanasyan]

In D17934#374020, @ruiu wrote:

This looks still a bit too intrusive. The code to handles thunks appears too many places.

Maybe we should handle thunks as a separate output section? Then we don't need to add addThunk to the regular output section class and we don't have to update the code to calculate section size and offsets.

I see some problems here:

• We can get a really long out-of-range jumps. I remember that my initial solution had the same problem but it was my mistake.
• The output section should have a name. Putting all thunks into the separate output section is in fact ABI extension because we have to choose dedicated unique name for such section. Moreover if somebody have a linker script to put output sections in exact places (common case for embedded software developers), it will be surprise that he or she have to handle one more unusual output section.
• There is optimization used by bfd and gold linkers - if input section contains the only function and we need to create a thunk for it, we can place the thunk in the beginning of the section and use just two assembly instructions to save the function address into the $25 registers and do not use additional jump instructions at all. My patch does not implement this optimization yet but moving all thunks into the separate output section make such optimization impossible at all.

I think the less intrusive solution is to concentrate the thunk handling in the InputSection class. We can add a vector of SymbolBody pointers right to this class. In that case only InputSection and TargetInfo descendant will know about synthetic code.

BTW MIPS is not the only target uses thunks. AFAIK ARM has concept of veneer.

[atanasyan]

• Isolated almost all thunk handling code in the InputSection class
• Reduced number of auxiliary classes, containers etc

[atanasyan]

Ping?

[atanasyan]

Ping?

[atanasyan]

Rebase the patch.

[ruiu]

I'm sorry that I missed this one. Taking a look now.

[ruiu]

ELF/InputSection.cpp

42–45 ↗

(On Diff #52145)

I feel like this is slightly more readable.

if (auto *D = dyn_cast<InputSection<ELFT>>(this))
  if (D->getThunksSize() > 0)
    return D->getThunkOff() + D->getThunksSize();
return Header->sh_size;

121 ↗

(On Diff #52145)

Is the thunk need to be aligned? If so, does it have the same alignment as the original section?

317 ↗

(On Diff #52145)

This needs a comment.

359 ↗

(On Diff #52145)

This needs a comment, saying that a section may have attached data that needs to be written after the section, and that data is usually a thunk to jump to a location that is too far to fit in a short jump instruction.

ELF/InputSection.h

172 ↗

(On Diff #52145)

I'd also mention that you can ignore this if you are interested only in x86/x86-64.

190 ↗

(On Diff #52145)

TinyPtrVector is probably better as I expect this is empty in most cases.

ELF/Target.cpp

1749 ↗

(On Diff #52145)

It is probably better to just say that "see MipsTargetInfo::writeThunk for details" instead of copying the comment.

ELF/Writer.cpp

483–495 ↗

(On Diff #52145)

Please make this a separate function and call only for platforms that need thunks.

[atanasyan]

• Use TinyPtrVector to store in the InputSection class pointers to SymbolBody which requires thunk creation.
• Create separate Writer::scanRelocsForThunks method for scanning relocations
• Remove thunks alignment. We do not need to do that.
• Simplify InputSectionBase::getSize
• Fix some comments

[ruiu]

LGTM with a nit. I think it is now simple enough to submit. Thanks!

ELF/Writer.cpp

316 ↗

(On Diff #52211)

Invert the condition and use continue.

[atanasyan]

Thanks for review.

lld/trunk/ELF/InputSection.h

public:
   // This pointer points to the "real" instance of this instance.
   // Usually Repl == this. However, if ICF merges two sections,
   // Repl pointer of one section points to another section. So,
   // if you need to get a pointer to this instance, do not use
   // this but instead this->Repl.
   InputSectionBase<ELFT> *Repl;
 
   // Returns the size of this section (even if this is a common or BSS.)
-  size_t getSize() const { return Header->sh_size; }
+  size_t getSize() const;
 
   static InputSectionBase<ELFT> *Discarded;
 
   StringRef getSectionName() const;
   const Elf_Shdr *getSectionHdr() const { return Header; }
   ObjectFile<ELFT> *getFile() const { return File; }
   uintX_t getOffset(const Elf_Sym &Sym);
 
public:
   // The offset from beginning of the output sections this section was assigned
   // to. The writer sets a value.
   uint64_t OutSecOff = 0;
 
   static bool classof(const InputSectionBase<ELFT> *S);
 
   InputSectionBase<ELFT> *getRelocatedSection();
 
+  // Register thunk related to the symbol. When the section is written
+  // to a mmap'ed file, target is requested to write an actual thunk code.
+  // Now thunks is supported for MIPS target only.
+  void addThunk(SymbolBody &Body);
+
+  // The offset of synthetic thunk code from beginning of this section.
+  uint64_t getThunkOff() const;
+
+  // Size of chunk with thunks code.
+  uint64_t getThunksSize() const;
+
 private:
   template <class RelTy>
   void copyRelocations(uint8_t *Buf, llvm::iterator_range<const RelTy *> Rels);
 
   // Called by ICF to merge two input sections.
   void replace(InputSection<ELFT> *Other);
 
   // Used by ICF.
   uint64_t GroupId = 0;
+
+  llvm::TinyPtrVector<const SymbolBody *> Thunks;
 };
 
 // MIPS .reginfo section provides information on the registers used by the code
 // in the object file. Linker should collect this information and write a single
 // .reginfo section in the output file. The output section contains a union of
 // used registers masks taken from input .reginfo sections and final value
 // of the `_gp` symbol.  For details: Chapter 4 / "Register Information" at
 // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf

lld/trunk/ELF/InputSection.cpp

InputSectionBase<ELFT>::InputSectionBase(elf::ObjectFile<ELFT> *File,
   // If GC is disabled, all sections are considered live by default.
   Live = !Config->GcSections;
 
   // The ELF spec states that a value of 0 means the section has
   // no alignment constraits.
   Align = std::max<uintX_t>(Header->sh_addralign, 1);
 }
 
+template <class ELFT> size_t InputSectionBase<ELFT>::getSize() const {
+  if (auto *D = dyn_cast<InputSection<ELFT>>(this))
+    if (D->getThunksSize() > 0)
+      return D->getThunkOff() + D->getThunksSize();
+  return Header->sh_size;
+}
+
 template <class ELFT> StringRef InputSectionBase<ELFT>::getSectionName() const {
   return check(File->getObj().getSectionName(this->Header));
 }
 
 template <class ELFT>
 ArrayRef<uint8_t> InputSectionBase<ELFT>::getSectionData() const {
   return check(this->File->getObj().getSectionContents(this->Header));
 }

 
 template <class ELFT>
 InputSectionBase<ELFT> *InputSection<ELFT>::getRelocatedSection() {
   assert(this->Header->sh_type == SHT_RELA || this->Header->sh_type == SHT_REL);
   ArrayRef<InputSectionBase<ELFT> *> Sections = this->File->getSections();
   return Sections[this->Header->sh_info];
 }
 
+template <class ELFT> void InputSection<ELFT>::addThunk(SymbolBody &Body) {
+  Body.ThunkIndex = Thunks.size();
+  Thunks.push_back(&Body);
+}
+
+template <class ELFT> uint64_t InputSection<ELFT>::getThunkOff() const {
+  return this->Header->sh_size;
+}
+
+template <class ELFT> uint64_t InputSection<ELFT>::getThunksSize() const {
+  return Thunks.size() * Target->ThunkSize;
+}
+
 // This is used for -r. We can't use memcpy to copy relocations because we need
 // to update symbol table offset and section index for each relocation. So we
 // copy relocations one by one.
 template <class ELFT>
 template <class RelTy>
 void InputSection<ELFT>::copyRelocations(uint8_t *Buf,
                                          iterator_range<const RelTy *> Rels) {
   InputSectionBase<ELFT> *RelocatedSection = getRelocatedSection();
if (Target->needsPlt(Type, Body)) {
       if (Body.IsTls)
         Type = Target->getTlsGotRel(Type);
     } else if (Target->isSizeRel(Type) && Body.isPreemptible()) {
       // A SIZE relocation is supposed to set a symbol size, but if a symbol
       // can be preempted, the size at runtime may be different than link time.
       // If that's the case, we leave the field alone rather than filling it
       // with a possibly incorrect value.
       continue;
+    } else if (Target->needsThunk(Type, *this->getFile(), Body)) {
+      // Get address of a thunk code related to the symbol.
+      SymVA = Body.getThunkVA<ELFT>();
     } else if (Config->EMachine == EM_MIPS) {
       SymVA = adjustMipsSymVA<ELFT>(Type, *File, Body, AddrLoc, SymVA);
     } else if (!Target->needsCopyRel<ELFT>(Type, Body) &&
                Body.isPreemptible()) {
       continue;
     }
     if (Target->isSizeRel(Type))
       SymVA = Body.getSize<ELFT>() + A;
template <class ELFT> void InputSection<ELFT>::writeTo(uint8_t *Buf) {
   // Iterate over all relocation sections that apply to this section.
   uint8_t *BufEnd = Buf + OutSecOff + Data.size();
   for (const Elf_Shdr *RelSec : this->RelocSections) {
     if (RelSec->sh_type == SHT_RELA)
       this->relocate(Buf, BufEnd, EObj.relas(RelSec));
     else
       this->relocate(Buf, BufEnd, EObj.rels(RelSec));
   }
+
+  // The section might have a data/code generated by the linker and need
+  // to be written after the section. Usually these are thunks - small piece
+  // of code used to jump between "incompatible" functions like PIC and non-PIC
+  // or if the jump target too far and its address does not fit to the short
+  // jump istruction.
+  if (!Thunks.empty()) {
+    Buf += OutSecOff + getThunkOff();
+    for (const SymbolBody *S : Thunks) {
+      Target->writeThunk(Buf, S->getVA<ELFT>());
+      Buf += Target->ThunkSize;
+    }
+  }
 }
 
 template <class ELFT>
 void InputSection<ELFT>::replace(InputSection<ELFT> *Other) {
   this->Align = std::max(this->Align, Other->Align);
   Other->Repl = this->Repl;
   Other->Live = false;
 }

lld/trunk/ELF/OutputSections.h

void updateAlign(uintX_t Align) {
     if (Align > Header.sh_addralign)
       Header.sh_addralign = Align;
   }
 
   // If true, this section will be page aligned on disk.
   // Typically the first section of each PT_LOAD segment has this flag.
   bool PageAlign = false;
 
+  virtual void assignOffsets() {}
   virtual void finalize() {}
   virtual void writeTo(uint8_t *Buf) {}
   virtual ~OutputSectionBase() = default;
 
 protected:
   StringRef Name;
   Elf_Shdr Header;
 };
public:
   typedef typename ELFT::Rel Elf_Rel;
   typedef typename ELFT::Rela Elf_Rela;
   typedef typename ELFT::uint uintX_t;
   OutputSection(StringRef Name, uint32_t Type, uintX_t Flags);
   void addSection(InputSectionBase<ELFT> *C) override;
   void sortInitFini();
   void sortCtorsDtors();
   void writeTo(uint8_t *Buf) override;
+  void assignOffsets() override;
   void finalize() override;
 
 private:
-  void reassignOffsets();
   std::vector<InputSection<ELFT> *> Sections;
 };
 
 template <class ELFT>
 class MergeOutputSection final : public OutputSectionBase<ELFT> {
   typedef typename ELFT::uint uintX_t;
 
   bool shouldTailMerge() const;

lld/trunk/ELF/OutputSections.cpp

 
 template <class ELFT>
 void OutputSection<ELFT>::addSection(InputSectionBase<ELFT> *C) {
   assert(C->Live);
   auto *S = cast<InputSection<ELFT>>(C);
   Sections.push_back(S);
   S->OutSec = this;
   this->updateAlign(S->Align);
-
-  uintX_t Off = this->Header.sh_size;
-  Off = alignTo(Off, S->Align);
-  S->OutSecOff = Off;
-  Off += S->getSize();
-  this->Header.sh_size = Off;
 }
 
 // If an input string is in the form of "foo.N" where N is a number,
 // return N. Otherwise, returns 65536, which is one greater than the
 // lowest priority.
 static int getPriority(StringRef S) {
   size_t Pos = S.rfind('.');
   if (Pos == StringRef::npos)
     return 65536;
   int V;
   if (S.substr(Pos + 1).getAsInteger(10, V))
     return 65536;
   return V;
 }
 
 // This function is called after we sort input sections
-// to update their offsets.
-template <class ELFT> void OutputSection<ELFT>::reassignOffsets() {
+// and scan relocations to setup sections' offsets.
+template <class ELFT> void OutputSection<ELFT>::assignOffsets() {
   uintX_t Off = 0;
   for (InputSection<ELFT> *S : Sections) {
     Off = alignTo(Off, S->Align);
     S->OutSecOff = Off;
     Off += S->getSize();
   }
   this->Header.sh_size = Off;
 }
template <class ELFT> void OutputSection<ELFT>::sortInitFini() {
 
   std::vector<Pair> V;
   for (InputSection<ELFT> *S : Sections)
     V.push_back({getPriority(S->getSectionName()), S});
   std::stable_sort(V.begin(), V.end(), Comp);
   Sections.clear();
   for (Pair &P : V)
     Sections.push_back(P.second);
-  reassignOffsets();
 }
 
 // Returns true if S matches /Filename.?\.o$/.
 static bool isCrtBeginEnd(StringRef S, StringRef Filename) {
   if (!S.endswith(".o"))
     return false;
   S = S.drop_back(2);
   if (S.endswith(Filename))
static bool compCtors(const InputSection<ELFT> *A,
   return X < Y;
 }
 
 // Sorts input sections by the special rules for .ctors and .dtors.
 // Unfortunately, the rules are different from the one for .{init,fini}_array.
 // Read the comment above.
 template <class ELFT> void OutputSection<ELFT>::sortCtorsDtors() {
   std::stable_sort(Sections.begin(), Sections.end(), compCtors<ELFT>);
-  reassignOffsets();
 }
 
 static void fill(uint8_t *Buf, size_t Size, ArrayRef<uint8_t> A) {
   size_t I = 0;
   for (; I + A.size() < Size; I += A.size())
     memcpy(Buf + I, A.data(), A.size());
   memcpy(Buf + I, A.data(), Size - I);
 }

lld/trunk/ELF/Symbols.h

public:
 
   uint8_t getVisibility() const { return Visibility; }
 
   unsigned DynsymIndex = 0;
   uint32_t GlobalDynIndex = -1;
   uint32_t GotIndex = -1;
   uint32_t GotPltIndex = -1;
   uint32_t PltIndex = -1;
+  uint32_t ThunkIndex = -1;
   bool hasGlobalDynIndex() { return GlobalDynIndex != uint32_t(-1); }
   bool isInGot() const { return GotIndex != -1U; }
   bool isInPlt() const { return PltIndex != -1U; }
+  bool hasThunk() const { return ThunkIndex != -1U; }
 
   void setUsedInRegularObj() { IsUsedInRegularObj = true; }
 
   template <class ELFT>
   typename ELFT::uint getVA(typename ELFT::uint Addend = 0) const;
 
   template <class ELFT> typename ELFT::uint getGotVA() const;
   template <class ELFT> typename ELFT::uint getGotPltVA() const;
   template <class ELFT> typename ELFT::uint getPltVA() const;
+  template <class ELFT> typename ELFT::uint getThunkVA() const;
   template <class ELFT> typename ELFT::uint getSize() const;
 
   // A SymbolBody has a backreference to a Symbol. Originally they are
   // doubly-linked. A backreference will never change. But the pointer
   // in the Symbol may be mutated by the resolver. If you have a
   // pointer P to a SymbolBody and are not sure whether the resolver
   // has chosen the object among other objects having the same name,
   // you can access P->Backref->Body to get the resolver's result.
public:
   typedef typename ELFT::uint uintX_t;
   DefinedSynthetic(StringRef N, uintX_t Value, OutputSectionBase<ELFT> &Section,
                    uint8_t Visibility);
 
   static bool classof(const SymbolBody *S) {
     return S->kind() == SymbolBody::DefinedSyntheticKind;
   }
 
+  // Special value designates that the symbol 'points'
+  // to the end of the section.
+  static const uintX_t SectionEnd = uintX_t(-1);
+
   uintX_t Value;
   const OutputSectionBase<ELFT> &Section;
 };
 
 // Undefined symbol.
 class Undefined : public SymbolBody {
   typedef SymbolBody::Kind Kind;
   bool CanKeepUndefined;

lld/trunk/ELF/Symbols.cpp

 static typename ELFT::uint getSymVA(const SymbolBody &Body,
                                     typename ELFT::uint &Addend) {
   typedef typename ELFT::Sym Elf_Sym;
   typedef typename ELFT::uint uintX_t;
 
   switch (Body.kind()) {
   case SymbolBody::DefinedSyntheticKind: {
     auto &D = cast<DefinedSynthetic<ELFT>>(Body);
+    if (D.Value == DefinedSynthetic<ELFT>::SectionEnd)
+      return D.Section.getVA() + D.Section.getSize();
     return D.Section.getVA() + D.Value;
   }
   case SymbolBody::DefinedRegularKind: {
     auto &D = cast<DefinedRegular<ELFT>>(Body);
     InputSectionBase<ELFT> *SC = D.Section;
 
     // This is an absolute symbol.
     if (!SC)
template <class ELFT> typename ELFT::uint SymbolBody::getGotPltVA() const {
   return Out<ELFT>::GotPlt->getVA() + GotPltIndex * sizeof(typename ELFT::uint);
 }
 
 template <class ELFT> typename ELFT::uint SymbolBody::getPltVA() const {
   return Out<ELFT>::Plt->getVA() + Target->PltZeroSize +
          PltIndex * Target->PltEntrySize;
 }
 
+template <class ELFT> typename ELFT::uint SymbolBody::getThunkVA() const {
+  auto *D = cast<DefinedRegular<ELFT>>(this);
+  auto *S = cast<InputSection<ELFT>>(D->Section);
+  return S->OutSec->getVA() + S->OutSecOff + S->getThunkOff() +
+         ThunkIndex * Target->ThunkSize;
+}
+
 template <class ELFT> typename ELFT::uint SymbolBody::getSize() const {
   if (auto *B = dyn_cast<DefinedElf<ELFT>>(this))
     return B->Sym.st_size;
   return 0;
 }
 
 static uint8_t getMinVisibility(uint8_t VA, uint8_t VB) {
   if (VA == STV_DEFAULT)

 template uint64_t SymbolBody::template getPltVA<ELF64LE>() const;
 template uint64_t SymbolBody::template getPltVA<ELF64BE>() const;
 
 template uint32_t SymbolBody::template getSize<ELF32LE>() const;
 template uint32_t SymbolBody::template getSize<ELF32BE>() const;
 template uint64_t SymbolBody::template getSize<ELF64LE>() const;
 template uint64_t SymbolBody::template getSize<ELF64BE>() const;
 
+template uint32_t SymbolBody::template getThunkVA<ELF32LE>() const;
+template uint32_t SymbolBody::template getThunkVA<ELF32BE>() const;
+template uint64_t SymbolBody::template getThunkVA<ELF64LE>() const;
+template uint64_t SymbolBody::template getThunkVA<ELF64BE>() const;
+
 template int SymbolBody::compare<ELF32LE>(SymbolBody *Other);
 template int SymbolBody::compare<ELF32BE>(SymbolBody *Other);
 template int SymbolBody::compare<ELF64LE>(SymbolBody *Other);
 template int SymbolBody::compare<ELF64BE>(SymbolBody *Other);
 
 template class elf::UndefinedElf<ELF32LE>;
 template class elf::UndefinedElf<ELF32BE>;
 template class elf::UndefinedElf<ELF64LE>;
 template class elf::UndefinedElf<ELF64BE>;
 
 template class elf::DefinedSynthetic<ELF32LE>;
 template class elf::DefinedSynthetic<ELF32BE>;
 template class elf::DefinedSynthetic<ELF64LE>;
 template class elf::DefinedSynthetic<ELF64BE>;

lld/trunk/ELF/Target.h

 
 #include "llvm/ADT/StringRef.h"
 #include "llvm/Object/ELF.h"
 
 #include <memory>
 
 namespace lld {
 namespace elf {
+class InputFile;
 class SymbolBody;
 
 class TargetInfo {
 public:
   uint64_t getVAStart() const;
   virtual bool isTlsInitialExecRel(uint32_t Type) const;
   virtual bool pointsToLocalDynamicGotEntry(uint32_t Type) const;
   virtual bool isTlsLocalDynamicRel(uint32_t Type) const;
public:
   virtual bool isSizeRel(uint32_t Type) const;
   virtual bool needsDynRelative(uint32_t Type) const { return false; }
   virtual bool needsGot(uint32_t Type, const SymbolBody &S) const;
   virtual bool refersToGotEntry(uint32_t Type) const;
 
   enum PltNeed { Plt_No, Plt_Explicit, Plt_Implicit };
   PltNeed needsPlt(uint32_t Type, const SymbolBody &S) const;
 
+  virtual bool needsThunk(uint32_t Type, const InputFile &File,
+                          const SymbolBody &S) const;
+
+  virtual void writeThunk(uint8_t *Buf, uint64_t S) const {}
+
   virtual void relocateOne(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type,
                            uint64_t P, uint64_t SA) const = 0;
   virtual bool isGotRelative(uint32_t Type) const;
   bool canRelaxTls(uint32_t Type, const SymbolBody *S) const;
   template <class ELFT>
   bool needsCopyRel(uint32_t Type, const SymbolBody &S) const;
   size_t relaxTls(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type, uint64_t P,
                   uint64_t SA, const SymbolBody &S) const;
public:
   uint32_t IRelativeRel;
   uint32_t TlsGotRel = 0;
   uint32_t TlsModuleIndexRel;
   uint32_t TlsOffsetRel;
   unsigned PltEntrySize = 8;
   unsigned PltZeroSize = 0;
   unsigned GotHeaderEntriesNum = 0;
   unsigned GotPltHeaderEntriesNum = 3;
+  uint32_t ThunkSize = 0;
   bool UseLazyBinding = false;
 
 private:
   virtual bool needsCopyRelImpl(uint32_t Type) const;
   virtual bool needsPltImpl(uint32_t Type) const;
 
   virtual size_t relaxTlsGdToIe(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type,
                                 uint64_t P, uint64_t SA) const;

lld/trunk/ELF/Target.cpp

 //
 // Refer the ELF spec for the single letter varaibles, S, A or P, used
 // in this file. SA is S+A.
 //
 //===----------------------------------------------------------------------===//
 
 #include "Target.h"
 #include "Error.h"
+#include "InputFiles.h"
 #include "OutputSections.h"
 #include "Symbols.h"
 
 #include "llvm/ADT/ArrayRef.h"
 #include "llvm/Object/ELF.h"
 #include "llvm/Support/Endian.h"
 #include "llvm/Support/ELF.h"
 
public:
   MipsTargetInfo();
   uint64_t getImplicitAddend(uint8_t *Buf, uint32_t Type) const override;
   uint32_t getDynRel(uint32_t Type) const override;
   void writeGotPlt(uint8_t *Buf, uint64_t Plt) const override;
   void writePltZero(uint8_t *Buf) const override;
   void writePlt(uint8_t *Buf, uint64_t GotEntryAddr, uint64_t PltEntryAddr,
                 int32_t Index, unsigned RelOff) const override;
   void writeGotHeader(uint8_t *Buf) const override;
+  void writeThunk(uint8_t *Buf, uint64_t S) const override;
   bool needsCopyRelImpl(uint32_t Type) const override;
   bool needsGot(uint32_t Type, const SymbolBody &S) const override;
   bool needsPltImpl(uint32_t Type) const override;
+  bool needsThunk(uint32_t Type, const InputFile &File,
+                  const SymbolBody &S) const override;
   void relocateOne(uint8_t *Loc, uint8_t *BufEnd, uint32_t Type, uint64_t P,
                    uint64_t SA) const override;
   bool isHintRel(uint32_t Type) const override;
   bool isRelRelative(uint32_t Type) const override;
   bool refersToGotEntry(uint32_t Type) const override;
 };
 } // anonymous namespace
 
TargetInfo::PltNeed TargetInfo::needsPlt(uint32_t Type,
   // R_386_JMP_SLOT, etc).
   if (S.isShared())
     if (!Config->Pic && S.IsFunc && !refersToGotEntry(Type))
       return Plt_Implicit;
 
   return Plt_No;
 }
 
+bool TargetInfo::needsThunk(uint32_t Type, const InputFile &File,
+                            const SymbolBody &S) const {
+  return false;
+}
+
 bool TargetInfo::isTlsInitialExecRel(uint32_t Type) const { return false; }
 
 bool TargetInfo::pointsToLocalDynamicGotEntry(uint32_t Type) const {
   return false;
 }
 
 bool TargetInfo::isTlsLocalDynamicRel(uint32_t Type) const { return false; }
 

 }
 
 template <class ELFT> MipsTargetInfo<ELFT>::MipsTargetInfo() {
   GotHeaderEntriesNum = 2;
   GotPltHeaderEntriesNum = 2;
   PageSize = 65536;
   PltEntrySize = 16;
   PltZeroSize = 32;
+  ThunkSize = 16;
   UseLazyBinding = true;
   CopyRel = R_MIPS_COPY;
   PltRel = R_MIPS_JUMP_SLOT;
   RelativeRel = R_MIPS_REL32;
 }
 
 template <class ELFT>
 uint32_t MipsTargetInfo<ELFT>::getDynRel(uint32_t Type) const {
void MipsTargetInfo<ELFT>::writePlt(uint8_t *Buf, uint64_t GotEntryAddr,
   write32<E>(Buf + 8, 0x03200008);  // jr    $25
   write32<E>(Buf + 12, 0x25f80000); // addiu $24, $15, %lo(.got.plt entry)
   writeMipsHi16<E>(Buf, GotEntryAddr);
   writeMipsLo16<E>(Buf + 4, GotEntryAddr);
   writeMipsLo16<E>(Buf + 12, GotEntryAddr);
 }
 
 template <class ELFT>
+void MipsTargetInfo<ELFT>::writeThunk(uint8_t *Buf, uint64_t S) const {
+  // Write MIPS LA25 thunk code to call PIC function from the non-PIC one.
+  // See MipsTargetInfo::writeThunk for details.
+  const endianness E = ELFT::TargetEndianness;
+  write32<E>(Buf, 0x3c190000);      // lui   $25, %hi(func)
+  write32<E>(Buf + 4, 0x08000000);  // j     func
+  write32<E>(Buf + 8, 0x27390000);  // addiu $25, $25, %lo(func)
+  write32<E>(Buf + 12, 0x00000000); // nop
+  writeMipsHi16<E>(Buf, S);
+  write32<E>(Buf + 4, 0x08000000 | (S >> 2));
+  writeMipsLo16<E>(Buf + 8, S);
+}
+
+template <class ELFT>
 bool MipsTargetInfo<ELFT>::needsCopyRelImpl(uint32_t Type) const {
   return !isRelRelative(Type);
 }
 
 template <class ELFT>
 bool MipsTargetInfo<ELFT>::needsGot(uint32_t Type, const SymbolBody &S) const {
   return needsPlt(Type, S) || refersToGotEntry(Type);
 }
 
 template <class ELFT>
 bool MipsTargetInfo<ELFT>::refersToGotEntry(uint32_t Type) const {
   return Type == R_MIPS_GOT16 || Type == R_MIPS_CALL16;
 }
 
 template <class ELFT>
 bool MipsTargetInfo<ELFT>::needsPltImpl(uint32_t Type) const {
   return Type == R_MIPS_26;
 }
 
 template <class ELFT>
+bool MipsTargetInfo<ELFT>::needsThunk(uint32_t Type, const InputFile &File,
+                                      const SymbolBody &S) const {
+  // Any MIPS PIC code function is invoked with its address in register $t9.
+  // So if we have a branch instruction from non-PIC code to the PIC one
+  // we cannot make the jump directly and need to create a small stubs
+  // to save the target function address.
+  // See page 3-38 ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
+  if (Type != R_MIPS_26)
+    return false;
+  auto *F = dyn_cast<ELFFileBase<ELFT>>(&File);
+  if (!F)
+    return false;
+  // If current file has PIC code, LA25 stub is not required.
+  if (F->getObj().getHeader()->e_flags & EF_MIPS_PIC)
+    return false;
+  auto *D = dyn_cast<DefinedRegular<ELFT>>(&S);
+  if (!D || !D->Section)
+    return false;
+  // LA25 is required if target file has PIC code
+  // or target symbol is a PIC symbol.
+  return (D->Section->getFile()->getObj().getHeader()->e_flags & EF_MIPS_PIC) ||
+         (D->Sym.st_other & STO_MIPS_MIPS16) == STO_MIPS_PIC;
+}
+
+template <class ELFT>
 uint64_t MipsTargetInfo<ELFT>::getImplicitAddend(uint8_t *Buf,
                                                  uint32_t Type) const {
   const endianness E = ELFT::TargetEndianness;
   switch (Type) {
   default:
     return 0;
   case R_MIPS_32:
   case R_MIPS_GPREL32:

lld/trunk/ELF/Writer.cpp

private:
   bool isDiscarded(InputSectionBase<ELFT> *IS) const;
   StringRef getOutputSectionName(InputSectionBase<ELFT> *S) const;
   bool needsInterpSection() const {
     return !Symtab.getSharedFiles().empty() && !Config->DynamicLinker.empty();
   }
   bool isOutputDynamic() const {
     return !Symtab.getSharedFiles().empty() || Config->Pic;
   }
+  template <class RelTy>
+  void scanRelocsForThunks(const elf::ObjectFile<ELFT> &File,
+                           iterator_range<const RelTy *> Rels);
 
   void ensureBss();
   void addCommonSymbols(std::vector<DefinedCommon *> &Syms);
   void addCopyRelSymbols(std::vector<SharedSymbol<ELFT> *> &Syms);
 
   std::unique_ptr<llvm::FileOutputBuffer> Buffer;
 
   BumpPtrAllocator Alloc;
if (Target->isTlsGlobalDynamicRel(Type)) {
     Out<ELFT>::Got->addEntry(Body);
     Out<ELFT>::RelaDyn->addReloc(
         {Target->TlsGotRel, DynamicReloc<ELFT>::Off_Got, false, &Body});
     return 2;
   }
   return 0;
 }
 
+// Some targets might require creation of thunks for relocations. Now we
+// support only MIPS which requires LA25 thunk to call PIC code from non-PIC
+// one. Scan relocations to find each one requires thunk.
+template <class ELFT>
+template <class RelTy>
+void Writer<ELFT>::scanRelocsForThunks(const elf::ObjectFile<ELFT> &File,
+                                       iterator_range<const RelTy *> Rels) {
+  for (const RelTy &RI : Rels) {
+    uint32_t Type = RI.getType(Config->Mips64EL);
+    uint32_t SymIndex = RI.getSymbol(Config->Mips64EL);
+    SymbolBody &Body = File.getSymbolBody(SymIndex).repl();
+    if (Body.hasThunk() || !Target->needsThunk(Type, File, Body))
+      continue;
+    auto *D = cast<DefinedRegular<ELFT>>(&Body);
+    auto *S = cast<InputSection<ELFT>>(D->Section);
+    S->addThunk(Body);
+  }
+}
+
 // The reason we have to do this early scan is as follows
 // * To mmap the output file, we need to know the size
 // * For that, we need to know how many dynamic relocs we will have.
 // It might be possible to avoid this by outputting the file with write:
 // * Write the allocated output sections, computing addresses.
 // * Apply relocations, recording which ones require a dynamic reloc.
 // * Write the dynamic relocations.
 // * Write the rest of the file.
if (Config->EMachine == EM_PPC64 && RI.getType(false) == R_PPC64_TOC) {
       Out<ELFT>::RelaDyn->addReloc({R_PPC64_RELATIVE, &C, RI.r_offset, false,
                                     nullptr,
                                     (uintX_t)getPPC64TocBase() + Addend});
       continue;
     }
     Out<ELFT>::RelaDyn->addReloc(
         {Target->RelativeRel, &C, RI.r_offset, true, &Body, Addend});
   }
+
+  // Scan relocations for necessary thunks.
+  if (Config->EMachine == EM_MIPS)
+    scanRelocsForThunks(File, Rels);
 }
 
 template <class ELFT> void Writer<ELFT>::scanRelocs(InputSection<ELFT> &C) {
   if (C.getSectionHdr()->sh_flags & SHF_ALLOC)
     for (const Elf_Shdr *RelSec : C.RelocSections)
       scanRelocs(C, *RelSec);
 }
 
for (InputSectionBase<ELFT> *C : F->getSections()) {
       if (auto *S = dyn_cast<InputSection<ELFT>>(C))
         scanRelocs(*S);
       else if (auto *S = dyn_cast<EHInputSection<ELFT>>(C))
         if (S->RelocSection)
           scanRelocs(*S, *S->RelocSection);
     }
   }
 
+  for (OutputSectionBase<ELFT> *Sec : getSections())
+    Sec->assignOffsets();
+
   // Now that we have defined all possible symbols including linker-
   // synthesized ones. Visit all symbols to give the finishing touches.
   std::vector<DefinedCommon *> CommonSymbols;
   std::vector<SharedSymbol<ELFT> *> CopyRelSymbols;
   for (auto &P : Symtab.getSymbols()) {
     SymbolBody *Body = P.second->Body;
     if (auto *U = dyn_cast<Undefined>(Body))
       if (!U->isWeak() && !U->canKeepUndefined())

 
 // 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,
                     OutputSectionBase<ELFT> *OS) {
     if (OS) {
       Symtab.addSynthetic(Start, *OS, 0, STV_DEFAULT);
-      Symtab.addSynthetic(End, *OS, OS->getSize(), STV_DEFAULT);
+      Symtab.addSynthetic(End, *OS, DefinedSynthetic<ELFT>::SectionEnd,
+                          STV_DEFAULT);
     } else {
       Symtab.addIgnored(Start);
       Symtab.addIgnored(End);
     }
   };
 
   Define("__preinit_array_start", "__preinit_array_end",
          Out<ELFT>::Dynamic->PreInitArraySec);
void Writer<ELFT>::addStartStopSymbols(OutputSectionBase<ELFT> *Sec) {
   StringSaver Saver(Alloc);
   StringRef Start = Saver.save("__start_" + S);
   StringRef Stop = Saver.save("__stop_" + S);
   if (SymbolBody *B = Symtab.find(Start))
     if (B->isUndefined())
       Symtab.addSynthetic(Start, *Sec, 0, STV_DEFAULT);
   if (SymbolBody *B = Symtab.find(Stop))
     if (B->isUndefined())
-      Symtab.addSynthetic(Stop, *Sec, Sec->getSize(), STV_DEFAULT);
+      Symtab.addSynthetic(Stop, *Sec, DefinedSynthetic<ELFT>::SectionEnd,
+                          STV_DEFAULT);
 }
 
 template <class ELFT> static bool needsPtLoad(OutputSectionBase<ELFT> *Sec) {
   if (!(Sec->getFlags() & SHF_ALLOC))
     return false;
 
   // Don't allocate VA space for TLS NOBITS sections. The PT_TLS PHDR is
   // responsible for allocating space for them, not the PT_LOAD that

lld/trunk/test/ELF/Inputs/mips-pic.s

+  .option pic2
+
+  .section .text.1,"ax",@progbits
+  .align 4
+  .globl foo1a
+  .type foo1a, @function
+foo1a:
+  nop
+  .globl foo1b
+  .type foo1b, @function
+foo1b:
+  nop
+
+  .section .text.2,"ax",@progbits
+  .align 4
+  .globl foo2
+  .type foo2, @function
+foo2:
+  nop

lld/trunk/test/ELF/mips-npic-call-pic.s

+# Check LA25 stubs creation. This stub code is necessary when
+# non-PIC code calls PIC function.
+
+# 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 %t-npic.o %t-pic.o -o %t.exe
+# RUN: llvm-objdump -d %t.exe | FileCheck %s
+
+# REQUIRES: mips
+
+# CHECK:     Disassembly of section .text:
+# CHECK-NEXT: __start:
+# CHECK-NEXT:    20000:       0c 00 80 0a     jal     131112
+#                                                     ^-- 0x20030 .pic.foo1a
+# CHECK-NEXT:    20004:       00 00 00 00     nop
+# CHECK-NEXT:    20008:       0c 00 80 15     jal     131156
+#                                                     ^-- 0x20060 .pic.foo2
+# CHECK-NEXT:    2000c:       00 00 00 00     nop
+# CHECK-NEXT:    20010:       0c 00 80 0e     jal     131128
+#                                                     ^-- 0x20040 .pic.foo1b
+# CHECK-NEXT:    20014:       00 00 00 00     nop
+# CHECK-NEXT:    20018:       0c 00 80 15     jal     131156
+#                                                     ^-- 0x20060 .pic.foo2
+# 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-NEXT:    20028:       3c 19 00 02     lui     $25, 2
+# CHECK-NEXT:    2002c:       08 00 80 08     j       131104 <foo1a>
+# CHECK-NEXT:    20030:       27 39 00 20     addiu   $25, $25, 32
+# CHECK-NEXT:    20034:       00 00 00 00     nop
+# CHECK-NEXT:    20038:       3c 19 00 02     lui     $25, 2
+# CHECK-NEXT:    2003c:       08 00 80 09     j       131108 <foo1b>
+# CHECK-NEXT:    20040:       27 39 00 24     addiu   $25, $25, 36
+# 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:      foo2:
+# CHECK-NEXT:    20050:       00 00 00 00     nop
+#
+# CHECK-NEXT:    20054:       3c 19 00 02     lui     $25, 2
+# CHECK-NEXT:    20058:       08 00 80 14     j       131152 <foo2>
+# CHECK-NEXT:    2005c:       27 39 00 50     addiu   $25, $25, 80
+# CHECK-NEXT:    20060:       00 00 00 00     nop
+
+  .text
+  .globl __start
+__start:
+  jal foo1a
+  jal foo2
+  jal foo1b
+  jal foo2