[ELF][MIPS] Initial support of MIPS local GOT entries

[atanasyan]

Summary

Some MIPS relocation (for now R_MIPS_GOT16) requires creation of GOT entries for symbol not included in the dynamic symbol table. They are local symbols and non-local symbols with 'local' visibility. Local GOT entries occupy continuous block between GOT header and regular GOT entries.

The patch adds initial support for handling local GOT entries. The main problem is allocating local GOT entries for local symbols. Such entries should be initialized by high 16-bit of the symbol value. In ideal world there should be no duplicated entries with the same values. But at the moment of the Writer::scanRelocs call we do not know a value of the symbol. In this patch we create new local GOT entry for each relocation against local symbol, though we can exhaust GOT quickly. That needs to be optimized later. When we calculate relocation we know a final symbol value and request local GOT entry index. To do that we maintain map between addresses and local GOT entry indexes. If we start to calculate relocations in parallel we will have to serialize access to this map.

[ruiu]

ELF/OutputSections.cpp

125 ↗

(On Diff #45287)

What is 0x8000?

154–156 ↗

(On Diff #45287)

This code seems a bit tricky, and I also don't like the idea to look up a table for MIPS local symbols.

How about this? We don't need to assign an index in the GOT to Sym->GotIndex() in addEntry. Instead, we can do that in GotSection::finalize(). We can also change addMipsLocalEntry(SymbolBody *) to just add a given SymbolBody to some vector (say, MipsEntries). In finalize(). we assign GotIndex to all symbols in MipsEntries first and then to all symbols in Entries.

[atanasyan]

ELF/OutputSections.cpp

125 ↗

(On Diff #45287)

In fact this is a %hi() expression without right-shifting. Like mipsHigh or applyPPCHa().

154–156 ↗

(On Diff #45287)

It is unclear how to deal with local symbols which does not have a corresponding SymbolBody.

Now MipsLocalEntries holds number of entries reserved for local GOT entries. Some of these entries are for non-local symbols with SymbolBody and we can keep them in MipsEntries. But other ones are for local symbols, i.e. section + offset in fact.

[ruiu]

ELF/OutputSections.cpp

125 ↗

(On Diff #45287)

Please add a comment to describe that.

154–156 ↗

(On Diff #45287)

Ah, I often forgot the fact that we did not create SymbolBody for a local symbol. This is probably a bold suggestion, but for the sake of discussion, what if we create SymbolBodies for local symbols? How much will it increase link time (I'm not requesting to do that in this patch, though)? That would increase link time, but if it is small, then that may make sense because that would simplify some code a lot.

[atanasyan]

ELF/OutputSections.cpp

154–156 ↗

(On Diff #45287)

It is a good idea but let's postpone it a bit. I'm going to optimize local GOT entries allocation to reduce number of such entries. To do that I will need to handle local symbols in a more complicated way than just counting GOT16 relocations against them. Maybe in that case SymbolBody for local symbol becomes mandatory.

[ruiu]

ELF/OutputSections.cpp

125 ↗

(On Diff #45287)

Is this done? Maybe you forgot to upload the latest patch?

[atanasyan]

• Add comment to explain 'magical' expression

[ruiu]

LGTM assuming that we are not going to keep MipsLocalGotPos indefinitely. We need to simplify this in future.

ELF/InputSection.cpp

224 ↗

(On Diff #45433)

Typo: oif

lld/trunk/ELF/InputSection.cpp

if (Target->isTlsOptimized(Type, Body)) {
       continue;
     }
 
     // Handle relocations for local symbols -- they never get
     // resolved so we don't allocate a SymbolBody.
     uintX_t A = getAddend<ELFT>(RI);
     if (!Body) {
       uintX_t SymVA = getLocalRelTarget(*File, RI, A);
-      // We need to adjust SymVA value in case of R_MIPS_GPREL16/32 relocations
-      // because they use the following expression to calculate the relocation's
-      // result for local symbol: S + A + GP0 - G.
-      if (Config->EMachine == EM_MIPS &&
-          (Type == R_MIPS_GPREL16 || Type == R_MIPS_GPREL32))
+      if (Config->EMachine == EM_MIPS) {
+        if (Type == R_MIPS_GPREL16 || Type == R_MIPS_GPREL32)
+          // We need to adjust SymVA value in case of R_MIPS_GPREL16/32
+          // relocations because they use the following expression to calculate
+          // the relocation's result for local symbol: S + A + GP0 - G.
           SymVA += File->getMipsGp0();
+        else if (Type == R_MIPS_GOT16)
+          // R_MIPS_GOT16 relocation against local symbol requires index of
+          // a local GOT entry which contains page address corresponds
+          // to the symbol address.
+          SymVA = Out<ELFT>::Got->getMipsLocalPageAddr(SymVA);
+      }
       Target->relocateOne(BufLoc, BufEnd, Type, AddrLoc, SymVA, 0,
                           findMipsPairedReloc(Buf, SymIndex, Type, NextRelocs));
       continue;
     }
 
     if (Target->isTlsGlobalDynamicReloc(Type) &&
         !Target->isTlsOptimized(Type, Body)) {
       Target->relocateOne(BufLoc, BufEnd, Type, AddrLoc,
                           Out<ELFT>::Got->getGlobalDynAddr(*Body) +
                               getAddend<ELFT>(RI));
       continue;
     }
 
     uintX_t SymVA = getSymVA<ELFT>(*Body);
     if (Target->relocNeedsPlt(Type, *Body)) {
       SymVA = Out<ELFT>::Plt->getEntryAddr(*Body);
     } else if (Target->relocNeedsGot(Type, *Body)) {
+      if (Config->EMachine == EM_MIPS && needsMipsLocalGot(Type, Body))
+        // Under some conditions relocations against non-local symbols require
+        // entries in the local part of MIPS GOT. In that case we need an entry
+        // initialized by full address of the symbol.
+        SymVA = Out<ELFT>::Got->getMipsLocalFullAddr(*Body);
+      else
         SymVA = Out<ELFT>::Got->getEntryAddr(*Body);
       if (Body->isTls())
         Type = Target->getTlsGotReloc(Type);
     } else if (!Target->needsCopyRel(Type, *Body) &&
                isa<SharedSymbol<ELFT>>(*Body)) {
       continue;
     } else if (Target->isTlsDynReloc(Type, *Body)) {
       continue;
     } else if (Target->isSizeReloc(Type) && canBePreempted(Body, false)) {

lld/trunk/ELF/OutputSections.h

template <class ELFT> class GotSection final : public OutputSectionBase<ELFT> {
   typedef OutputSectionBase<ELFT> Base;
   typedef typename Base::uintX_t uintX_t;
 
 public:
   GotSection();
   void finalize() override;
   void writeTo(uint8_t *Buf) override;
   void addEntry(SymbolBody *Sym);
+  void addMipsLocalEntry();
   bool addDynTlsEntry(SymbolBody *Sym);
   bool addCurrentModuleTlsIndex();
-  bool empty() const { return Entries.empty(); }
+  bool empty() const { return MipsLocalEntries == 0 && Entries.empty(); }
   uintX_t getEntryAddr(const SymbolBody &B) const;
+  uintX_t getMipsLocalFullAddr(const SymbolBody &B);
+  uintX_t getMipsLocalPageAddr(uintX_t Addr);
   uintX_t getGlobalDynAddr(const SymbolBody &B) const;
   uintX_t getNumEntries() const { return Entries.size(); }
 
   // Returns the symbol which corresponds to the first entry of the global part
   // of GOT on MIPS platform. It is required to fill up MIPS-specific dynamic
   // table properties.
   // Returns nullptr if the global part is empty.
   const SymbolBody *getMipsFirstGlobalEntry() const;
 
   // Returns the number of entries in the local part of GOT including
   // the number of reserved entries. This method is MIPS-specific.
   unsigned getMipsLocalEntriesNum() const;
 
   uint32_t getLocalTlsIndexVA() { return Base::getVA() + LocalTlsIndexOff; }
 
 private:
   std::vector<const SymbolBody *> Entries;
   uint32_t LocalTlsIndexOff = -1;
+  uint32_t MipsLocalEntries = 0;
+  llvm::DenseMap<uintX_t, size_t> MipsLocalGotPos;
+
+  uintX_t getMipsLocalEntryAddr(uintX_t EntryValue);
 };
 
 template <class ELFT>
 class GotPltSection final : public OutputSectionBase<ELFT> {
   typedef typename llvm::object::ELFFile<ELFT>::uintX_t uintX_t;
 
 public:
   GotPltSection();

lld/trunk/ELF/OutputSections.cpp

 GotSection<ELFT>::GotSection()
     : OutputSectionBase<ELFT>(".got", SHT_PROGBITS, SHF_ALLOC | SHF_WRITE) {
   if (Config->EMachine == EM_MIPS)
     this->Header.sh_flags |= SHF_MIPS_GPREL;
   this->Header.sh_addralign = sizeof(uintX_t);
 }
 
 template <class ELFT> void GotSection<ELFT>::addEntry(SymbolBody *Sym) {
-  Sym->GotIndex = Target->getGotHeaderEntriesNum() + Entries.size();
+  Sym->GotIndex = Entries.size();
   Entries.push_back(Sym);
 }
 
+template <class ELFT> void GotSection<ELFT>::addMipsLocalEntry() {
+  ++MipsLocalEntries;
+}
+
 template <class ELFT> bool GotSection<ELFT>::addDynTlsEntry(SymbolBody *Sym) {
   if (Sym->hasGlobalDynIndex())
     return false;
   Sym->GlobalDynIndex = Target->getGotHeaderEntriesNum() + Entries.size();
   // Global Dynamic TLS entries take two GOT slots.
   Entries.push_back(Sym);
   Entries.push_back(nullptr);
   return true;
 }
 
 template <class ELFT> bool GotSection<ELFT>::addCurrentModuleTlsIndex() {
   if (LocalTlsIndexOff != uint32_t(-1))
     return false;
   Entries.push_back(nullptr);
   Entries.push_back(nullptr);
   LocalTlsIndexOff = (Entries.size() - 2) * sizeof(uintX_t);
   return true;
 }
 
 template <class ELFT>
 typename GotSection<ELFT>::uintX_t
 GotSection<ELFT>::getEntryAddr(const SymbolBody &B) const {
-  return this->getVA() + B.GotIndex * sizeof(uintX_t);
+  return this->getVA() +
+         (Target->getGotHeaderEntriesNum() + MipsLocalEntries + B.GotIndex) *
+             sizeof(uintX_t);
+}
+
+template <class ELFT>
+typename GotSection<ELFT>::uintX_t
+GotSection<ELFT>::getMipsLocalFullAddr(const SymbolBody &B) {
+  return getMipsLocalEntryAddr(getSymVA<ELFT>(B));
+}
+
+template <class ELFT>
+typename GotSection<ELFT>::uintX_t
+GotSection<ELFT>::getMipsLocalPageAddr(uintX_t EntryValue) {
+  // Initialize the entry by the %hi(EntryValue) expression
+  // but without right-shifting.
+  return getMipsLocalEntryAddr((EntryValue + 0x8000) & ~0xffff);
+}
+
+template <class ELFT>
+typename GotSection<ELFT>::uintX_t
+GotSection<ELFT>::getMipsLocalEntryAddr(uintX_t EntryValue) {
+  size_t NewIndex = Target->getGotHeaderEntriesNum() + MipsLocalGotPos.size();
+  auto P = MipsLocalGotPos.insert(std::make_pair(EntryValue, NewIndex));
+  assert(!P.second || MipsLocalGotPos.size() <= MipsLocalEntries);
+  return this->getVA() + P.first->second * sizeof(uintX_t);
 }
 
 template <class ELFT>
 typename GotSection<ELFT>::uintX_t
 GotSection<ELFT>::getGlobalDynAddr(const SymbolBody &B) const {
   return this->getVA() + B.GlobalDynIndex * sizeof(uintX_t);
 }
 
 template <class ELFT>
 const SymbolBody *GotSection<ELFT>::getMipsFirstGlobalEntry() const {
   return Entries.empty() ? nullptr : Entries.front();
 }
 
 template <class ELFT>
 unsigned GotSection<ELFT>::getMipsLocalEntriesNum() const {
-  // TODO: Update when the support of GOT entries for local symbols is added.
-  return Target->getGotHeaderEntriesNum();
+  return Target->getGotHeaderEntriesNum() + MipsLocalEntries;
 }
 
 template <class ELFT> void GotSection<ELFT>::finalize() {
   this->Header.sh_size =
-      (Target->getGotHeaderEntriesNum() + Entries.size()) * sizeof(uintX_t);
+      (Target->getGotHeaderEntriesNum() + MipsLocalEntries + Entries.size()) *
+      sizeof(uintX_t);
 }
 
 template <class ELFT> void GotSection<ELFT>::writeTo(uint8_t *Buf) {
   Target->writeGotHeaderEntries(Buf);
+  for (const auto &L : MipsLocalGotPos) {
+    uint8_t *Entry = Buf + L.second * sizeof(uintX_t);
+    write<uintX_t, ELFT::TargetEndianness, sizeof(uintX_t)>(Entry, L.first);
+  }
   Buf += Target->getGotHeaderEntriesNum() * sizeof(uintX_t);
+  Buf += MipsLocalEntries * sizeof(uintX_t);
   for (const SymbolBody *B : Entries) {
     uint8_t *Entry = Buf;
     Buf += sizeof(uintX_t);
     if (!B)
       continue;
     // MIPS has special rules to fill up GOT entries.
     // See "Global Offset Table" in Chapter 5 in the following document
     // for detailed description:

lld/trunk/ELF/Target.h

protected:
   bool LazyRelocations = false;
 };
 
 uint64_t getPPC64TocBase();
 
 template <class ELFT>
 typename llvm::object::ELFFile<ELFT>::uintX_t getMipsGpAddr();
 
+// Returns true if the relocation requires entry in the local part of GOT.
+bool needsMipsLocalGot(uint32_t Type, SymbolBody *Body);
+
 template <class ELFT> bool isGnuIFunc(const SymbolBody &S);
 
 extern std::unique_ptr<TargetInfo> Target;
 TargetInfo *createTarget();
 }
 }
 
 #endif

lld/trunk/ELF/Target.cpp

 // the value for the symbol.
 template <class ELFT> typename ELFFile<ELFT>::uintX_t getMipsGpAddr() {
   unsigned GPOffset = 0x7ff0;
   if (uint64_t V = Out<ELFT>::Got->getVA())
     return V + GPOffset;
   return 0;
 }
 
+bool needsMipsLocalGot(uint32_t Type, SymbolBody *Body) {
+  // The R_MIPS_GOT16 relocation requires creation of entry in the local part
+  // of GOT if its target is a local symbol or non-local symbol with 'local'
+  // visibility.
+  if (Type != R_MIPS_GOT16)
+    return false;
+  if (!Body)
+    return true;
+  uint8_t V = Body->getVisibility();
+  if (V != STV_DEFAULT && V != STV_PROTECTED)
+    return true;
+  return !Config->Shared;
+}
+
 template uint32_t getMipsGpAddr<ELF32LE>();
 template uint32_t getMipsGpAddr<ELF32BE>();
 template uint64_t getMipsGpAddr<ELF64LE>();
 template uint64_t getMipsGpAddr<ELF64BE>();
 }
 }

lld/trunk/ELF/Writer.cpp

for (const RelType &RI : Rels) {
     if (Target->relocNeedsDynRelative(Type)) {
       RelType *Rel = new (Alloc) RelType;
       Rel->setSymbolAndType(0, Target->getRelativeReloc(), Config->Mips64EL);
       Rel->r_offset = RI.r_offset;
       Out<ELFT>::RelaDyn->addReloc({&C, Rel});
     }
 
     bool NeedsGot = false;
+    bool NeedsMipsLocalGot = false;
     bool NeedsPlt = false;
-    if (Body) {
+    if (Config->EMachine == EM_MIPS && needsMipsLocalGot(Type, Body)) {
+      NeedsMipsLocalGot = true;
+      // FIXME (simon): Do not add so many redundant entries.
+      Out<ELFT>::Got->addMipsLocalEntry();
+    } else if (Body) {
       if (auto *E = dyn_cast<SharedSymbol<ELFT>>(Body)) {
         if (E->NeedsCopy)
           continue;
         if (Target->needsCopyRel(Type, *Body))
           E->NeedsCopy = true;
       }
       NeedsPlt = Target->relocNeedsPlt(Type, *Body);
       if (NeedsPlt) {
for (const RelType &RI : Rels) {
     // symbol, although local symbols normally do not require PLT entries.
     if (Body && isGnuIFunc<ELFT>(*Body)) {
       Body->setUsedInDynamicReloc();
       Out<ELFT>::RelaPlt->addReloc({&C, &RI});
       continue;
     }
 
     if (Config->EMachine == EM_MIPS) {
-      if (NeedsGot) {
+      if (Type == R_MIPS_LO16)
+        // Ignore R_MIPS_LO16 relocation. If it is a pair for R_MIPS_GOT16 we
+        // already completed all required action (GOT entry allocation) when
+        // handle R_MIPS_GOT16a. If it is a pair for R_MIPS_HI16 against
+        // _gp_disp it does not require dynamic relocation. If its a pair for
+        // R_MIPS_HI16 against a regular symbol it does not require dynamic
+        // relocation too because that case is possible for executable file
+        // linking only.
+        continue;
+      if (NeedsGot || NeedsMipsLocalGot) {
         // MIPS ABI has special rules to process GOT entries
         // and doesn't require relocation entries for them.
         // See "Global Offset Table" in Chapter 5 in the following document
         // for detailed description:
         // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf
+        if (NeedsGot)
           Body->setUsedInDynamicReloc();
         continue;
       }
       if (Body == Config->MipsGpDisp)
         // MIPS _gp_disp designates offset between start of function and gp
         // pointer into GOT therefore any relocations against it do not require
         // dynamic relocation.
         continue;
     }

lld/trunk/test/ELF/mips-got16.s

+# Check R_MIPS_GOT16 relocation calculation.
+
+# RUN: llvm-mc -filetype=obj -triple=mips-unknown-linux %s -o %t.o
+# RUN: ld.lld %t.o -shared -o %t.so
+# RUN: llvm-objdump -d -t %t.so | FileCheck %s
+# RUN: llvm-readobj -r -mips-plt-got %t.so | FileCheck -check-prefix=GOT %s
+
+# REQUIRES: mips
+
+# CHECK:      Disassembly of section .text:
+# CHECK-NEXT: __start:
+# CHECK-NEXT:    10000:       8f 88 80 18     lw      $8, -32744($gp)
+# CHECK-NEXT:    10004:       21 08 00 1c     addi    $8, $8, 28
+# CHECK-NEXT:    10008:       8f 88 80 1c     lw      $8, -32740($gp)
+# CHECK-NEXT:    1000c:       21 08 00 00     addi    $8, $8, 0
+# CHECK-NEXT:    10010:       8f 88 80 20     lw      $8, -32736($gp)
+# CHECK-NEXT:    10014:       21 08 00 04     addi    $8, $8, 4
+# CHECK-NEXT:    10018:       8f 88 80 24     lw      $8, -32732($gp)
+#
+# CHECK: SYMBOL TABLE:
+# CHECK: 0001001c         .text           00000000 $LC0
+# CHECK: 00030000         .data           00000000 $LC1
+# CHECK: 00030004         .data           00000000 .hidden bar
+# CHECK: 00000000         *UND*           00000000 foo
+
+# GOT:      Relocations [
+# GOT-NEXT: ]
+
+# GOT:      Primary GOT {
+# GOT-NEXT:   Canonical gp value: 0x27FF0
+# GOT-NEXT:   Reserved entries [
+# GOT-NEXT:     Entry {
+# GOT-NEXT:       Address: 0x20000
+# GOT-NEXT:       Access: -32752
+# GOT-NEXT:       Initial: 0x0
+# GOT-NEXT:       Purpose: Lazy resolver
+# GOT-NEXT:     }
+# GOT-NEXT:     Entry {
+# GOT-NEXT:       Address: 0x20004
+# GOT-NEXT:       Access: -32748
+# GOT-NEXT:       Initial: 0x80000000
+# GOT-NEXT:       Purpose: Module pointer (GNU extension)
+# GOT-NEXT:     }
+# GOT-NEXT:   ]
+# GOT-NEXT:   Local entries [
+# GOT-NEXT:     Entry {
+# GOT-NEXT:       Address: 0x20008
+# GOT-NEXT:       Access: -32744
+# GOT-NEXT:       Initial: 0x10000
+# GOT-NEXT:     }
+# GOT-NEXT:     Entry {
+# GOT-NEXT:       Address: 0x2000C
+# GOT-NEXT:       Access: -32740
+# GOT-NEXT:       Initial: 0x30000
+# GOT-NEXT:     }
+# GOT-NEXT:     Entry {
+# GOT-NEXT:       Address: 0x20010
+# GOT-NEXT:       Access: -32736
+# GOT-NEXT:       Initial: 0x30004
+# GOT-NEXT:     }
+# GOT-NEXT:   ]
+# GOT-NEXT:   Global entries [
+# GOT-NEXT:     Entry {
+# GOT-NEXT:       Address: 0x20014
+# GOT-NEXT:       Access: -32732
+# GOT-NEXT:       Initial: 0x0
+# GOT-NEXT:       Value: 0x0
+# GOT-NEXT:       Type: None
+# GOT-NEXT:       Section: Undefined
+# GOT-NEXT:       Name: foo@
+# GOT-NEXT:     }
+# GOT-NEXT:   ]
+# GOT-NEXT:   Number of TLS and multi-GOT entries: 0
+# GOT-NEXT: }
+
+  .text
+  .globl  __start
+__start:
+  lw      $t0,%got($LC0)($gp)
+  addi    $t0,$t0,%lo($LC0)
+  lw      $t0,%got($LC1)($gp)
+  addi    $t0,$t0,%lo($LC1)
+  lw      $t0,%got(bar)($gp)
+  addi    $t0,$t0,%lo(bar)
+  lw      $t0,%got(foo)($gp)
+$LC0:
+  nop
+
+  .data
+$LC1:
+  .word 0
+.global bar
+.hidden bar
+bar:
+  .word 0