[ELF][MIPS] Put local GOT entries accessed via a 16-bit index first

[atanasyan]

Summary

Some MIPS relocations used to access GOT entries are able to manipulate 16-bit index. The other ones like R_MIPS_CALL_HI16/LO16 can handle 32-bit indexes. 16-bit relocations are generated by default. The 32-bit relocations are generated by -mxgot flag passed to compiler. Usually these relocation are not mixed in the same code but files like crt*.o contain 16-bit relocations so even if all "user's" code compiled with -mxgot flag a few 16-bit relocations might come to the linking phase.

Now LLD does not differentiate local GOT entries accessed via a 16-bit and 32-bit indexes. That might lead to relocation's overflow if 16-bit entries are allocated to far from the beginning of the GOT.

The patch introduces new "part" of MIPS GOT dedicated to the local GOT entries accessed by 32-bit relocations. That allows to put local GOT entries accessed via a 16-bit index first and escape relocation's overflow.

[mgrang]

ELF/OutputSections.cpp

205 ↗

(On Diff #75319)

Fix indentation. It would be great if you could fix indentation of the next "else" too :)

[atanasyan]

ELF/OutputSections.cpp

205 ↗

(On Diff #75319)

Fix indentation. It would be great if you could fix indentation of the next "else" too

I'm sorry, but what is wrong with the current indentation? Brackets are on the same line with the else if statement, the code block is indented by two spaces.

[mgrang]

ELF/OutputSections.cpp

205 ↗

(On Diff #75319)

I thought the statements must be indented two spaces under the else-if too. But now that I see, it seems fine having the statements align with those under the preceding "if".

[ruiu]

LGTM, but could you add a comment about why we are putting got entries referred by 16-bit relocations before entries referred by 32-bit relocations?

lld/trunk/ELF/InputSection.cpp

static typename ELFT::uint getSymVA(uint32_t Type, typename ELFT::uint A,
   case R_GOT_OFF:
     return Body.getGotOffset<ELFT>() + A;
   case R_MIPS_GOT_LOCAL_PAGE:
     // 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_OFF:
+  case R_MIPS_GOT_OFF32:
     // In case of MIPS if a GOT relocation has non-zero addend this addend
     // should be applied to the GOT entry content not to the GOT entry offset.
     // That is why we use separate expression type.
     return Out<ELFT>::Got->getMipsGotOffset(Body, A);
   case R_MIPS_TLSGD:
     return Out<ELFT>::Got->getGlobalDynOffset(Body) +
            Out<ELFT>::Got->getMipsTlsOffset() - MipsGPOffset;
   case R_MIPS_TLSLD:

lld/trunk/ELF/OutputSections.h

private:
   // account addend for preemptible symbols because the corresponding
   // GOT entries should have one-to-one mapping with dynamic symbols table.
   // But we use the same container's types for both kind of GOT entries
   // to handle them uniformly.
   typedef std::pair<const SymbolBody *, uintX_t> MipsGotEntry;
   typedef std::vector<MipsGotEntry> MipsGotEntries;
   llvm::DenseMap<MipsGotEntry, size_t> MipsGotMap;
   MipsGotEntries MipsLocal;
+  MipsGotEntries MipsLocal32;
   MipsGotEntries MipsGlobal;
 
   // Write MIPS-specific parts of the GOT.
   void writeMipsGot(uint8_t *Buf);
 };
 
 template <class ELFT>
 class GotPltSection final : public OutputSectionBase<ELFT> {

lld/trunk/ELF/OutputSections.cpp

auto AddEntry = [&](SymbolBody &S, uintX_t A, MipsGotEntries &Items) {
     Items.emplace_back(&S, A);
     if (!A)
       S.GotIndex = NewIndex;
   };
   if (Sym.isPreemptible()) {
     // Ignore addends for preemptible symbols. They got single GOT entry anyway.
     AddEntry(Sym, 0, MipsGlobal);
     Sym.IsInGlobalMipsGot = true;
-  } else
+  } else if (Expr == R_MIPS_GOT_OFF32) {
+    AddEntry(Sym, Addend, MipsLocal32);
+    Sym.Is32BitMipsGot = true;
+  } else {
+    // Hold local GOT entries accessed via a 16-bit index separately.
+    // That allows to write them in the beginning of the GOT and keep
+    // their indexes as less as possible to escape relocation's overflow.
     AddEntry(Sym, Addend, MipsLocal);
   }
+}
 
 template <class ELFT> bool GotSection<ELFT>::addDynTlsEntry(SymbolBody &Sym) {
   if (Sym.GlobalDynIndex != -1U)
     return false;
   Sym.GlobalDynIndex = Entries.size();
   // Global Dynamic TLS entries take two GOT slots.
   Entries.push_back(nullptr);
   Entries.push_back(&Sym);

 typename GotSection<ELFT>::uintX_t
 GotSection<ELFT>::getMipsGotOffset(const SymbolBody &B, uintX_t Addend) const {
   // Calculate offset of the GOT entries block: TLS, global, local.
   uintX_t GotBlockOff;
   if (B.isTls())
     GotBlockOff = getMipsTlsOffset();
   else if (B.IsInGlobalMipsGot)
     GotBlockOff = getMipsLocalEntriesNum() * sizeof(uintX_t);
+  else if (B.Is32BitMipsGot)
+    GotBlockOff = (MipsPageEntries + MipsLocal.size()) * sizeof(uintX_t);
   else
     GotBlockOff = MipsPageEntries * sizeof(uintX_t);
   // Calculate index of the GOT entry in the block.
   uintX_t GotIndex;
   if (B.isInGot())
     GotIndex = B.GotIndex;
   else {
     auto It = MipsGotMap.find({&B, Addend});

 
 template <class ELFT>
 const SymbolBody *GotSection<ELFT>::getMipsFirstGlobalEntry() const {
   return MipsGlobal.empty() ? nullptr : MipsGlobal.front().first;
 }
 
 template <class ELFT>
 unsigned GotSection<ELFT>::getMipsLocalEntriesNum() const {
-  return MipsPageEntries + MipsLocal.size();
+  return MipsPageEntries + MipsLocal.size() + MipsLocal32.size();
 }
 
 template <class ELFT> void GotSection<ELFT>::finalize() {
   size_t EntriesNum = Entries.size();
   if (Config->EMachine == EM_MIPS) {
     // Take into account MIPS GOT header.
     // See comment in the GotSection::writeTo.
     MipsPageEntries += 2;
template <class ELFT> void GotSection<ELFT>::writeMipsGot(uint8_t *Buf) {
   auto AddEntry = [&](const MipsGotEntry &SA) {
     uint8_t *Entry = Buf;
     Buf += sizeof(uintX_t);
     const SymbolBody *Body = SA.first;
     uintX_t VA = Body->template getVA<ELFT>(SA.second);
     writeUint<ELFT>(Entry, VA);
   };
   std::for_each(std::begin(MipsLocal), std::end(MipsLocal), AddEntry);
+  std::for_each(std::begin(MipsLocal32), std::end(MipsLocal32), AddEntry);
   std::for_each(std::begin(MipsGlobal), std::end(MipsGlobal), AddEntry);
   // Initialize TLS-related GOT entries. If the entry has a corresponding
   // dynamic relocations, leave it initialized by zero. Write down adjusted
   // TLS symbol's values otherwise. To calculate the adjustments use offsets
   // for thread-local storage.
   // https://www.linux-mips.org/wiki/NPTL
   if (TlsIndexOff != -1U && !Config->Pic)
     writeUint<ELFT>(Buf + TlsIndexOff, 1);

lld/trunk/ELF/Relocations.h

enum RelExpr {
   R_GOTREL_FROM_END,
   R_GOT_FROM_END,
   R_GOT_OFF,
   R_GOT_PAGE_PC,
   R_GOT_PC,
   R_HINT,
   R_MIPS_GOT_LOCAL_PAGE,
   R_MIPS_GOT_OFF,
+  R_MIPS_GOT_OFF32,
   R_MIPS_TLSGD,
   R_MIPS_TLSLD,
   R_NEG_TLS,
   R_PAGE_PC,
   R_PC,
   R_PLT,
   R_PLT_PC,
   R_PLT_PAGE_PC,

lld/trunk/ELF/Relocations.cpp

 using namespace llvm::object;
 using namespace llvm::support::endian;
 
 namespace lld {
 namespace elf {
 
 static bool refersToGotEntry(RelExpr Expr) {
   return Expr == R_GOT || Expr == R_GOT_OFF || Expr == R_MIPS_GOT_LOCAL_PAGE ||
-         Expr == R_MIPS_GOT_OFF || Expr == R_MIPS_TLSGD ||
-         Expr == R_MIPS_TLSLD || Expr == R_GOT_PAGE_PC || Expr == R_GOT_PC ||
-         Expr == R_GOT_FROM_END || Expr == R_TLSGD || Expr == R_TLSGD_PC ||
-         Expr == R_TLSDESC || Expr == R_TLSDESC_PAGE;
+         Expr == R_MIPS_GOT_OFF || Expr == R_MIPS_GOT_OFF32 ||
+         Expr == R_MIPS_TLSGD || Expr == R_MIPS_TLSLD ||
+         Expr == R_GOT_PAGE_PC || Expr == R_GOT_PC || Expr == R_GOT_FROM_END ||
+         Expr == R_TLSGD || Expr == R_TLSGD_PC || Expr == R_TLSDESC ||
+         Expr == R_TLSDESC_PAGE;
 }
 
 static bool isPreemptible(const SymbolBody &Body, uint32_t Type) {
   // In case of MIPS GP-relative relocations always resolve to a definition
   // in a regular input file, ignoring the one-definition rule. So we,
   // for example, should not attempt to create a dynamic relocation even
   // if the target symbol is preemptible. There are two two MIPS GP-relative
   // relocations R_MIPS_GPREL16 and R_MIPS_GPREL32. But only R_MIPS_GPREL16
return Expr == R_PC || Expr == R_GOTREL || Expr == R_GOTREL_FROM_END ||
          Expr == R_THUNK_PLT_PC;
 }
 
 template <class ELFT>
 static bool isStaticLinkTimeConstant(RelExpr E, uint32_t Type,
                                      const SymbolBody &Body) {
   // These expressions always compute a constant
   if (E == R_SIZE || E == R_GOT_FROM_END || E == R_GOT_OFF ||
-      E == R_MIPS_GOT_LOCAL_PAGE || E == R_MIPS_GOT_OFF || E == R_MIPS_TLSGD ||
-      E == R_GOT_PAGE_PC || E == R_GOT_PC || E == R_PLT_PC ||
-      E == R_TLSGD_PC || E == R_TLSGD || E == R_PPC_PLT_OPD ||
-      E == R_TLSDESC_CALL || E == R_TLSDESC_PAGE || E == R_HINT ||
-      E == R_THUNK_PC || E == R_THUNK_PLT_PC)
+      E == R_MIPS_GOT_LOCAL_PAGE || E == R_MIPS_GOT_OFF ||
+      E == R_MIPS_GOT_OFF32 || E == R_MIPS_TLSGD || E == R_GOT_PAGE_PC ||
+      E == R_GOT_PC || E == R_PLT_PC || E == R_TLSGD_PC || E == R_TLSGD ||
+      E == R_PPC_PLT_OPD || E == R_TLSDESC_CALL || E == R_TLSDESC_PAGE ||
+      E == R_HINT || E == R_THUNK_PC || E == R_THUNK_PLT_PC)
     return true;
 
   // These never do, except if the entire file is position dependent or if
   // only the low bits are used.
   if (E == R_GOT || E == R_PLT || E == R_TLSDESC)
     return Target->usesOnlyLowPageBits(Type) || !Config->Pic;
 
   if (isPreemptible(Body, Type))

lld/trunk/ELF/Symbols.h

public:
   unsigned NeedsCopyOrPltAddr : 1;
 
   // True if this is a local symbol.
   unsigned IsLocal : 1;
 
   // True if this symbol has an entry in the global part of MIPS GOT.
   unsigned IsInGlobalMipsGot : 1;
 
+  // True if this symbol is referenced by 32-bit GOT relocations.
+  unsigned Is32BitMipsGot : 1;
+
   // The following fields have the same meaning as the ELF symbol attributes.
   uint8_t Type;    // symbol type
   uint8_t StOther; // st_other field value
 
   // The Type field may also have this value. It means that we have not yet seen
   // a non-Lazy symbol with this name, so we don't know what its type is. The
   // Type field is normally set to this value for Lazy symbols unless we saw a
   // weak undefined symbol first, in which case we need to remember the original

lld/trunk/ELF/Symbols.cpp

case SymbolBody::LazyObjectKind:
     return 0;
   }
   llvm_unreachable("invalid symbol kind");
 }
 
 SymbolBody::SymbolBody(Kind K, uint32_t NameOffset, uint8_t StOther,
                        uint8_t Type)
     : SymbolKind(K), NeedsCopyOrPltAddr(false), IsLocal(true),
-      IsInGlobalMipsGot(false), Type(Type), StOther(StOther),
-      NameOffset(NameOffset) {}
+      IsInGlobalMipsGot(false), Is32BitMipsGot(false), Type(Type),
+      StOther(StOther), NameOffset(NameOffset) {}
 
 SymbolBody::SymbolBody(Kind K, StringRef Name, uint8_t StOther, uint8_t Type)
     : SymbolKind(K), NeedsCopyOrPltAddr(false), IsLocal(false),
-      IsInGlobalMipsGot(false), Type(Type), StOther(StOther),
-      Name({Name.data(), Name.size()}) {}
+      IsInGlobalMipsGot(false), Is32BitMipsGot(false), Type(Type),
+      StOther(StOther), Name({Name.data(), Name.size()}) {}
 
 StringRef SymbolBody::getName() const {
   assert(!isLocal());
   return StringRef(Name.S, Name.Len);
 }
 
 // Returns true if a symbol can be replaced at load-time by a symbol
 // with the same name defined in other ELF executable or DSO.

lld/trunk/ELF/Target.cpp

RelExpr MipsTargetInfo<ELFT>::getRelExpr(uint32_t Type,
   case R_MIPS_PCHI16:
   case R_MIPS_PCLO16:
     return R_PC;
   case R_MIPS_GOT16:
     if (S.isLocal())
       return R_MIPS_GOT_LOCAL_PAGE;
   // fallthrough
   case R_MIPS_CALL16:
+  case R_MIPS_GOT_DISP:
+  case R_MIPS_TLS_GOTTPREL:
+    return R_MIPS_GOT_OFF;
   case R_MIPS_CALL_HI16:
   case R_MIPS_CALL_LO16:
-  case R_MIPS_GOT_DISP:
   case R_MIPS_GOT_HI16:
   case R_MIPS_GOT_LO16:
-  case R_MIPS_TLS_GOTTPREL:
-    return R_MIPS_GOT_OFF;
+    return R_MIPS_GOT_OFF32;
   case R_MIPS_GOT_PAGE:
     return R_MIPS_GOT_LOCAL_PAGE;
   case R_MIPS_TLS_GD:
     return R_MIPS_TLSGD;
   case R_MIPS_TLS_LDM:
     return R_MIPS_TLSLD;
   }
 }

lld/trunk/test/ELF/mips-xgot-order.s

+# Check that GOT entries accessed via 16-bit indexing are allocated
+# in the beginning of the GOT.
+
+# RUN: llvm-mc -filetype=obj -triple=mips-unknown-linux %s -o %t.o
+# RUN: ld.lld %t.o -o %t.exe
+# RUN: llvm-objdump -d -s -t %t.exe | FileCheck %s
+
+# REQUIRES: mips
+
+# CHECK:      Disassembly of section .text:
+# CHECK-NEXT: __start:
+# CHECK-NEXT:    20000:       3c 02 00 00     lui     $2, 0
+# CHECK-NEXT:    20004:       8c 42 80 20     lw      $2, -32736($2)
+# CHECK-NEXT:    20008:       3c 02 00 00     lui     $2, 0
+# CHECK-NEXT:    2000c:       8c 42 80 24     lw      $2, -32732($2)
+#
+# CHECK:      bar:
+# CHECK-NEXT:    20010:       8c 42 80 1c     lw      $2, -32740($2)
+# CHECK-NEXT:    20014:       8c 42 80 18     lw      $2, -32744($2)
+# CHECK-NEXT:    20018:       20 42 00 00     addi    $2, $2, 0
+
+# CHECK:      Contents of section .got:
+# CHECK-NEXT:  30000 00000000 80000000 00040000 00020010
+#                                      ^ %hi(loc)
+#                                               ^ %got(bar)
+# CHECK-NEXT:  30010 00020000 00040000
+#                    ^ %got_hi/lo(start)
+#                             ^ %got_hi/lo(loc)
+
+# CHECK: 00040000         .data           00000000 loc
+# CHECK: 00020000         .text           00000000 __start
+# CHECK: 00020010         .text           00000000 bar
+
+  .text
+  .global __start, bar
+__start:
+  lui   $2, %got_hi(__start)
+  lw    $2, %got_lo(__start)($2)
+  lui   $2, %got_hi(loc)
+  lw    $2, %got_lo(loc)($2)
+bar:
+  lw    $2, %got(bar)($2)
+  lw    $2, %got(loc)($2)
+  addi  $2, $2, %lo(loc)
+
+  .data
+loc:
+  .word 0