[ELF][MIPS] Handle GOT entries for all non-local symbols uniformly

[atanasyan]

Summary

The patch assigns 'kind' to each GOT entry. Now they are MipsLocal, MipsGlobal and Regular. That allows to create entries for all non-local symbols and handle them uniformly. From the other side we have to sort GOT entries before writing .got section accordingly to their types.

The main motivations for this patch is preparation for support MIPS TLS relocations. It might sound like a joke but for GOT entries related to TLS relocations MIPS ABI uses almost regular approach with creation of dynamic relocations for each GOT enty etc. But we need to separate these 'regular' TLS related entries from MIPS specific local/global parts of GOT. ABI declare simple solution - all TLS related entries allocated at the end of GOT after local/global parts. To support these scheme, we anyway have to differentiate and sort GOT entries.

[zatrazz]

ELF/OutputSections.h

141

On my TLS descriptor patch [1], after some discussion I changed the approach of using a vector of vectors to just define the required vectors instead (one for each type). I think using a vector for each type simplifies the code, since it won't require sorting in the finalize method.

[1] http://reviews.llvm.org/D18960

[atanasyan]

ELF/OutputSections.h

141

My motivation was to touch non-MIPS code as little as possible. In that case single vector is a good approach. But if MIPS is not the only architecture requires GOT entries "types" I would be happy to escape GOT sorting.

What is the state of your patch?

[zatrazz]

ELF/OutputSections.h

141

SImilar to your patch my motivation is to enable current supported TLS but for aarch64. The patch does not really touch any aarch64 specifics bits (I plan to send another patch after this is reviewed), and the ideia is to make possible to use this TLS descriptor code not only to support aarch64, but all architectures that have TLS dsecriptor abi (arm, i386, x86_64, and aarch64).

I got some initial reviews, but currently it requires a thoughtfully one.

[atanasyan]

ELF/OutputSections.h

141

I was thinking about using multiple vectors to hold different entries in the GotSection class. In the MIPS case that approach simplifies the finalize method because we do not have to sort the entries. But it makes methods which calculate various GOT indexes really messy. In case of MIPS we need at least three containers: for local entries, for global entries, and for TLS related entries.

[atanasyan]

• Rebased

[• rafael]

So, with the multiple vector solution, the index computation would still be simple for the non mips case, no? We would still have just

Sym.GotIndex = Entries.size();

Only inside the mips specific code would we have to look at MipsLocal and MipsGlobal entries.

Would you mind giving that a try?

ELF/InputSection.h

enum RelExpr {
   R_ABS,
   R_GOT,
   R_GOTONLY_PC,
   R_GOTREL,
   R_GOT_OFF,
   R_GOT_FROM_END,
   R_GOT_PAGE_PC,
   R_GOT_PC,
-  R_MIPS_GOT,
   R_MIPS_GOT_LOCAL,
   R_NEG_TLS,
   R_PAGE_PC,
   R_PC,
   R_PLT,
   R_PLT_PC,
   R_PPC_OPD,
   R_PPC_PLT_OPD,
   R_PPC_TOC,
   R_RELAX_TLS_GD_TO_IE,
   R_RELAX_TLS_GD_TO_IE_PC,
   R_RELAX_TLS_GD_TO_LE,
   R_RELAX_TLS_IE_TO_LE,
   R_RELAX_TLS_LD_TO_LE,
   R_SIZE,
   R_THUNK,
   R_TLS,
   R_TLSGD,
   R_TLSGD_PC,
   R_TLSLD,
   R_TLSLD_PC
 };
 
 inline bool refersToGotEntry(RelExpr Expr) {
-  return Expr == R_GOT || Expr == R_GOT_OFF || Expr == R_MIPS_GOT ||
-         Expr == R_MIPS_GOT_LOCAL || Expr == R_GOT_PAGE_PC ||
-         Expr == R_GOT_PC || Expr == R_GOT_FROM_END || Expr == R_TLSGD ||
-         Expr == R_TLSGD_PC;
+  return Expr == R_GOT || Expr == R_GOT_OFF || Expr == R_MIPS_GOT_LOCAL ||
+         Expr == R_GOT_PAGE_PC || Expr == R_GOT_PC || Expr == R_GOT_FROM_END ||
+         Expr == R_TLSGD || Expr == R_TLSGD_PC;
 }
 
 struct Relocation {
   RelExpr Expr;
   uint32_t Type;
   uint64_t Offset;
   uint64_t Addend;
   SymbolBody *Sym;

ELF/InputSection.cpp

case R_RELAX_TLS_LD_TO_LE:
     return Body.getVA<ELFT>(A);
   case R_GOT_OFF:
     return Body.getGotOffset<ELFT>() + A;
   case R_MIPS_GOT_LOCAL:
     // If relocation against MIPS local symbol requires GOT entry, this entry
     // should be initialized by 'page address'. This address is high 16-bits
     // of sum the symbol's value and the addend.
     return Out<ELFT>::Got->getMipsLocalPageOffset(Body.getVA<ELFT>(A));
-  case R_MIPS_GOT:
-    // For non-local symbols GOT entries should contain their full
-    // addresses. But if such symbol cannot be preempted, we do not
-    // have to put them into the "global" part of GOT and use dynamic
-    // linker to determine their actual addresses. That is why we
-    // create GOT entries for them in the "local" part of GOT.
-    return Out<ELFT>::Got->getMipsLocalEntryOffset(Body.getVA<ELFT>(A));
   case R_PPC_OPD: {
     uint64_t SymVA = Body.getVA<ELFT>(A);
     // If we have an undefined weak symbol, we might get here with a symbol
     // address of zero. That could overflow, but the code must be unreachable,
     // so don't bother doing anything at all.
     if (!SymVA)
       return 0;
     if (Out<ELF64BE>::Opd) {

ELF/OutputSections.h

 
 public:
   GotSection();
   void finalize() override;
   void writeTo(uint8_t *Buf) override;
   void addEntry(SymbolBody &Sym);
   bool addDynTlsEntry(SymbolBody &Sym);
   bool addTlsIndex();
-  bool empty() const { return MipsLocalEntries == 0 && Entries.empty(); }
-  uintX_t getMipsLocalEntryOffset(uintX_t EntryValue);
+  bool empty() const { return Entries.empty(); }
   uintX_t getMipsLocalPageOffset(uintX_t Addr);
   uintX_t getGlobalDynAddr(const SymbolBody &B) const;
   uintX_t getGlobalDynOffset(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;
 
   uintX_t getTlsIndexVA() { return Base::getVA() + TlsIndexOff; }
   uint32_t getTlsIndexOff() { return TlsIndexOff; }
 
 private:
-  std::vector<const SymbolBody *> Entries;
+  enum EntryKind {
+    MipsLocal,
+    MipsGlobal,
+    Regular,
+  };
+  std::vector<std::pair<EntryKind, SymbolBody *>> Entries;
   uint32_t TlsIndexOff = -1;
   uint32_t MipsLocalEntries = 0;
+  const SymbolBody *MipsFirstGlobalSym = nullptr;
   // Output sections referenced by MIPS GOT relocations.
   llvm::SmallPtrSet<const OutputSectionBase<ELFT> *, 10> MipsOutSections;
   llvm::DenseMap<uintX_t, size_t> MipsLocalGotPos;
 };
 
 template <class ELFT>
 class GotPltSection final : public OutputSectionBase<ELFT> {
   typedef typename ELFT::uint uintX_t;

ELF/OutputSections.cpp

if (Config->EMachine == EM_MIPS) {
     if (Sym.isLocal()) {
       // At this point we do not know final symbol value so to reduce number
       // of allocated GOT entries do the following trick. Save all output
       // sections referenced by GOT relocations. Then later in the `finalize`
       // method calculate number of "pages" required to cover all saved output
       // section and allocate appropriate number of GOT entries.
       auto *OutSec = cast<DefinedRegular<ELFT>>(&Sym)->Section->OutSec;
       MipsOutSections.insert(OutSec);
-      return;
+    } else {
+      Sym.GotIndex = Entries.size();
+      Entries.push_back(
+          std::make_pair(Sym.isPreemptible() ? MipsGlobal : MipsLocal, &Sym));
     }
-    if (!Sym.isPreemptible()) {
-      // In case of non-local symbols require an entry in the local part
-      // of MIPS GOT, we set GotIndex to 1 just to accent that this symbol
-      // has the GOT entry and escape creation more redundant GOT entries.
-      // FIXME (simon): We can try to store such symbols in the `Entries`
-      // container. But in that case we have to sort out that container
-      // and update GotIndex assigned to symbols.
-      Sym.GotIndex = 1;
-      ++MipsLocalEntries;
-      return;
-    }
-  }
   Sym.GotIndex = Entries.size();
-  Entries.push_back(&Sym);
+  Entries.push_back(std::make_pair(Regular, &Sym));
 }
 
 template <class ELFT> bool GotSection<ELFT>::addDynTlsEntry(SymbolBody &Sym) {
   if (Sym.hasGlobalDynIndex())
     return false;
   Sym.GlobalDynIndex = Entries.size();
   // Global Dynamic TLS entries take two GOT slots.
-  Entries.push_back(&Sym);
-  Entries.push_back(nullptr);
+  Entries.push_back(std::make_pair(Regular, &Sym));
+  Entries.push_back(std::make_pair(Regular, nullptr));
   return true;
 }
 
 // Reserves TLS entries for a TLS module ID and a TLS block offset.
 // In total it takes two GOT slots.
 template <class ELFT> bool GotSection<ELFT>::addTlsIndex() {
   if (TlsIndexOff != uint32_t(-1))
     return false;
   TlsIndexOff = Entries.size() * sizeof(uintX_t);
-  Entries.push_back(nullptr);
-  Entries.push_back(nullptr);
+  Entries.push_back(std::make_pair(Regular, nullptr));
+  Entries.push_back(std::make_pair(Regular, nullptr));
   return true;
 }
 
 template <class ELFT>
 typename GotSection<ELFT>::uintX_t
 GotSection<ELFT>::getMipsLocalPageOffset(uintX_t EntryValue) {
   // Initialize the entry by the %hi(EntryValue) expression
   // but without right-shifting.
-  return getMipsLocalEntryOffset((EntryValue + 0x8000) & ~0xffff);
-}
-
-template <class ELFT>
-typename GotSection<ELFT>::uintX_t
-GotSection<ELFT>::getMipsLocalEntryOffset(uintX_t EntryValue) {
+  EntryValue = (EntryValue + 0x8000) & ~0xffff;
   // Take into account MIPS GOT header.
   // See comment in the GotSection::writeTo.
   size_t NewIndex = MipsLocalGotPos.size() + 2;
   auto P = MipsLocalGotPos.insert(std::make_pair(EntryValue, NewIndex));
   assert(!P.second || MipsLocalGotPos.size() <= MipsLocalEntries);
   return P.first->second * sizeof(uintX_t) - MipsGPOffset;
 }
 
 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>
 typename GotSection<ELFT>::uintX_t
 GotSection<ELFT>::getGlobalDynOffset(const SymbolBody &B) const {
   return B.GlobalDynIndex * sizeof(uintX_t);
 }
 
 template <class ELFT>
 const SymbolBody *GotSection<ELFT>::getMipsFirstGlobalEntry() const {
-  return Entries.empty() ? nullptr : Entries.front();
+  return MipsFirstGlobalSym;
 }
 
 template <class ELFT>
 unsigned GotSection<ELFT>::getMipsLocalEntriesNum() const {
   return MipsLocalEntries;
 }
 
 template <class ELFT> void GotSection<ELFT>::finalize() {
-  if (Config->EMachine == EM_MIPS)
+  if (Config->EMachine == EM_MIPS) {
     // Take into account MIPS GOT header.
     // See comment in the GotSection::writeTo.
-    MipsLocalEntries += 2;
-  for (const OutputSectionBase<ELFT> *OutSec : MipsOutSections) {
+    size_t PageEntries = 2;
+    for (const OutputSectionBase<ELFT> *OutSec : MipsOutSections)
       // Calculate an upper bound of MIPS GOT entries required to store page
       // addresses of local symbols. We assume the worst case - each 64kb
       // page of the output section has at least one GOT relocation against it.
       // Add 0x8000 to the section's size because the page address stored
       // in the GOT entry is calculated as (value + 0x8000) & ~0xffff.
-    MipsLocalEntries += (OutSec->getSize() + 0x8000 + 0xfffe) / 0xffff;
+      PageEntries += (OutSec->getSize() + 0x8000 + 0xfffe) / 0xffff;
+    Entries.insert(Entries.begin(), PageEntries,
+                   std::make_pair(MipsLocal, nullptr));
+    // Sort GOT entries by type: local entries, global entries.
+    // Use stable sort to keep order of global entries because
+    // we have sorted dynamic symbol table using this order already.
+    std::stable_sort(std::begin(Entries), std::end(Entries),
+                     [](const std::pair<EntryKind, SymbolBody *> &A,
+                        const std::pair<EntryKind, SymbolBody *> &B) {
+                       return A.first < B.first;
+                     });
+    for (size_t I = 0, E = Entries.size(); I < E; ++I) {
+      EntryKind Kind = Entries[I].first;
+      SymbolBody *Sym = Entries[I].second;
+      if (Kind == MipsLocal)
+        ++MipsLocalEntries;
+      if (Kind == MipsGlobal && !MipsFirstGlobalSym)
+        MipsFirstGlobalSym = Sym;
+      if (Sym) {
+        Sym->GotIndex = I;
+      }
     }
-  this->Header.sh_size = (MipsLocalEntries + Entries.size()) * sizeof(uintX_t);
+  }
+  this->Header.sh_size = Entries.size() * sizeof(uintX_t);
 }
 
 template <class ELFT> void GotSection<ELFT>::writeTo(uint8_t *Buf) {
   if (Config->EMachine == EM_MIPS) {
     // Set the MSB of the second GOT slot. This is not required by any
     // MIPS ABI documentation, though.
     //
     // There is a comment in glibc saying that "The MSB of got[1] of a
if (Config->EMachine == EM_MIPS) {
     // if we had to do this.
     auto *P = reinterpret_cast<typename ELFT::Off *>(Buf);
     P[1] = uintX_t(1) << (ELFT::Is64Bits ? 63 : 31);
   }
   for (std::pair<uintX_t, size_t> &L : MipsLocalGotPos) {
     uint8_t *Entry = Buf + L.second * sizeof(uintX_t);
     write<uintX_t, ELFT::TargetEndianness, sizeof(uintX_t)>(Entry, L.first);
   }
-  Buf += MipsLocalEntries * sizeof(uintX_t);
-  for (const SymbolBody *B : Entries) {
+  for (const auto &E : Entries) {
+    const SymbolBody *B = E.second;
     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:
     // ftp://www.linux-mips.org/pub/linux/mips/doc/ABI/mipsabi.pdf

ELF/Symbols.cpp

typename ELFT::uint SymbolBody::getVA(typename ELFT::uint Addend) const {
   return OutVA + Addend;
 }
 
 template <class ELFT> typename ELFT::uint SymbolBody::getGotVA() const {
   return Out<ELFT>::Got->getVA() + getGotOffset<ELFT>();
 }
 
 template <class ELFT> typename ELFT::uint SymbolBody::getGotOffset() const {
-  return (Out<ELFT>::Got->getMipsLocalEntriesNum() + GotIndex) *
-         sizeof(typename ELFT::uint);
+  return GotIndex * sizeof(typename ELFT::uint);
 }
 
 template <class ELFT> typename ELFT::uint SymbolBody::getGotPltVA() const {
   return Out<ELFT>::GotPlt->getVA() + getGotPltOffset<ELFT>();
 }
 
 template <class ELFT> typename ELFT::uint SymbolBody::getGotPltOffset() const {
   return GotPltIndex * sizeof(typename ELFT::uint);

ELF/Target.cpp

RelExpr MipsTargetInfo<ELFT>::getRelExpr(uint32_t Type,
   case R_MIPS_PC26_S2:
   case R_MIPS_PCHI16:
   case R_MIPS_PCLO16:
     return R_PC;
   case R_MIPS_GOT16:
   case R_MIPS_CALL16:
     if (S.isLocal())
       return R_MIPS_GOT_LOCAL;
-    if (!S.isPreemptible())
-      return R_MIPS_GOT;
     return R_GOT_OFF;
   }
 }
 
 template <class ELFT>
 uint32_t MipsTargetInfo<ELFT>::getDynRel(uint32_t Type) const {
   if (Type == R_MIPS_32 || Type == R_MIPS_64)
     return R_MIPS_REL32;

test/ELF/mips-got16.s

 # CHECK-NEXT:    10000:       8f 88 80 18     lw      $8, -32744($gp)
 # CHECK-NEXT:    10004:       21 08 00 2c     addi    $8, $8, 44
 # CHECK-NEXT:    10008:       8f 88 80 1c     lw      $8, -32740($gp)
 # CHECK-NEXT:    1000c:       21 08 90 00     addi    $8, $8, -28672
 # CHECK-NEXT:    10010:       8f 88 80 20     lw      $8, -32736($gp)
 # CHECK-NEXT:    10014:       21 08 90 04     addi    $8, $8, -28668
 # CHECK-NEXT:    10018:       8f 88 80 20     lw      $8, -32736($gp)
 # CHECK-NEXT:    1001c:       21 08 10 04     addi    $8, $8, 4100
-# CHECK-NEXT:    10020:       8f 88 80 24     lw      $8, -32732($gp)
+# CHECK-NEXT:    10020:       8f 88 80 28     lw      $8, -32728($gp)
 # CHECK-NEXT:    10024:       21 08 10 08     addi    $8, $8, 4104
 # CHECK-NEXT:    10028:       8f 88 80 2c     lw      $8, -32724($gp)
 #
 # CHECK: SYMBOL TABLE:
 # CHECK: 0001002c         .text           00000000 $LC0
 # CHECK: 00039000         .data           00000000 $LC1
 # CHECK: 00051008         .data           00000000 .hidden bar
 # CHECK: 00000000         *UND*           00000000 foo

 # GOT-NEXT:       Access: -32736
 # GOT-NEXT:       Initial: 0x50000
 #                          ^-- (0x39000 + 0x10004 + 0x8000) & ~0xffff
 #                          ^-- (0x39000 + 0x18004 + 0x8000) & ~0xffff
 # GOT-NEXT:     }
 # GOT-NEXT:     Entry {
 # GOT-NEXT:       Address: 0x20014
 # GOT-NEXT:       Access: -32732
-# GOT-NEXT:       Initial: 0x51008
-#                          ^-- 'bar' address
+# GOT-NEXT:       Initial: 0x0
+#                          ^-- redundant unused entry
 # GOT-NEXT:     }
 # GOT-NEXT:     Entry {
 # GOT-NEXT:       Address: 0x20018
 # GOT-NEXT:       Access: -32728
-# GOT-NEXT:       Initial: 0x0
-#                          ^-- redundant unused entry
+# GOT-NEXT:       Initial: 0x51008
+#                          ^-- 'bar' address
 # GOT-NEXT:     }
 # GOT-NEXT:   ]
 # GOT-NEXT:   Global entries [
 # GOT-NEXT:     Entry {
 # GOT-NEXT:       Address: 0x2001C
 # GOT-NEXT:       Access: -32724
 # GOT-NEXT:       Initial: 0x0
 # GOT-NEXT:       Value: 0x0