[RuntimeDyldELF] Improve GOT support

[loladiro]

Summary

This is the first in a series of patches to eventually add support for TLS relocations to RuntimeDyld. This patch resolves an issue in the current GOT handling, where GOT entries would be reused between object files, which leads to the same situation that necessitates the GOT in the first place, i.e. that the 32-bit offset can not cover all of the address space. Thus this patch makes the GOT object-file-local.
Unfortunately, this still isn't quite enough, because the MemoryManager does not yet guarantee that sections are allocated sufficiently close to each other, even if they belong to the same object file. To address this concern, this patch also adds a small API abstraction on top of the GOT allocation mechanism that will allow (temporarily, until the MemoryManager is improved) using the stub mechanism instead of allocating a different section. The actual switch from separate section to stub mechanism will be part of a follow-on commit, so that it can be easily reverted independently at the appropriate time.

[lhames]

Hi Keno,

This sounds great. Sorry for the delay in review - I'm hoping to get to
them very soon (i.e. in a day or two).

Cheers,
Lang.

[lhames]

lib/ExecutionEngine/RuntimeDyld/RuntimeDyldELF.cpp

255–258 ↗

(On Diff #23195)

Would it be better to zero out the GOT entry when it's reserved so that you don't need to special-case the placeholder logic here?

270–273 ↗

(On Diff #23195)

Ditto here.

[loladiro]

lib/ExecutionEngine/RuntimeDyld/RuntimeDyldELF.cpp

255–258 ↗

(On Diff #23195)

No, that doesn't work because the placeholder pull values out of the original (unrelocated) object file, which does not have the stub. The better direction to go is to encode everything that's needed into the Addend, but that's a separate and more invasive change.

[lhames]

lib/ExecutionEngine/RuntimeDyld/RuntimeDyldELF.cpp

255–258 ↗

(On Diff #23195)

Ahh, of course. This is another good argument for getting rid of our reliance on the original file.

Given this, your existing scheme looks good to me.

llvm/trunk/lib/ExecutionEngine/RuntimeDyld/RuntimeDyld.cpp

if (Name.size() == 0) {
                SymInfo.getOffset();
       }
 
       // FIXME: Implement error handling that doesn't kill the host program!
       if (!Addr)
         report_fatal_error("Program used external function '" + Name +
                            "' which could not be resolved!");
 
-      updateGOTEntries(Name, Addr);
       DEBUG(dbgs() << "Resolving relocations Name: " << Name << "\t"
                    << format("0x%lx", Addr) << "\n");
       // This list may have been updated when we called getSymbolAddress, so
       // don't change this code to get the list earlier.
       RelocationList &Relocs = i->second;
       resolveRelocationList(Relocs, Addr);
     }
 

llvm/trunk/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldCheckerImpl.h

 #include <set>
 
 namespace llvm {
 
 class RuntimeDyldCheckerImpl {
   friend class RuntimeDyldChecker;
   friend class RuntimeDyldImpl;
   friend class RuntimeDyldCheckerExprEval;
+  friend class RuntimeDyldELF;
 
 public:
   RuntimeDyldCheckerImpl(RuntimeDyld &RTDyld, MCDisassembler *Disassembler,
                          MCInstPrinter *InstPrinter,
                          llvm::raw_ostream &ErrStream);
 
   bool check(StringRef CheckExpr) const;
   bool checkAllRulesInBuffer(StringRef RulePrefix, MemoryBuffer *MemBuf) const;

llvm/trunk/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldELF.h

class RuntimeDyldELF : public RuntimeDyldImpl {
 
   void findPPC64TOCSection(const ObjectFile &Obj,
                            ObjSectionToIDMap &LocalSections,
                            RelocationValueRef &Rel);
   void findOPDEntrySection(const ObjectFile &Obj,
                            ObjSectionToIDMap &LocalSections,
                            RelocationValueRef &Rel);
 
-  uint64_t findGOTEntry(uint64_t LoadAddr, uint64_t Offset);
   size_t getGOTEntrySize();
 
-  void updateGOTEntries(StringRef Name, uint64_t Addr) override;
+  SectionEntry &getSection(unsigned SectionID) { return Sections[SectionID]; }
 
-  // Relocation entries for symbols whose position-independent offset is
-  // updated in a global offset table.
-  typedef SmallVector<RelocationValueRef, 2> GOTRelocations;
-  GOTRelocations GOTEntries; // List of entries requiring finalization.
-  SmallVector<std::pair<SID, GOTRelocations>, 8> GOTs; // Allocated tables.
+  // Allocate no GOT entries for use in the given section.
+  uint64_t allocateGOTEntries(unsigned SectionID, unsigned no);
+
+  // Resolve the relvative address of GOTOffset in Section ID and place
+  // it at the given Offset
+  void resolveGOTOffsetRelocation(unsigned SectionID, uint64_t Offset,
+                                  uint64_t GOTOffset);
+
+  // For a GOT entry referenced from SectionID, compute a relocation entry
+  // that will place the final resolved value in the GOT slot
+  RelocationEntry computeGOTOffsetRE(unsigned SectionID,
+                                     uint64_t GOTOffset,
+                                     uint64_t SymbolOffset,
+                                     unsigned Type);
+
+  // The tentative ID for the GOT section
+  unsigned GOTSectionID;
+
+  // Records the current number of allocated slots in the GOT
+  // (This would be equivalent to GOTEntries.size() were it not for relocations
+  // that consume more than one slot)
+  unsigned CurrentGOTIndex;
 
   // When a module is loaded we save the SectionID of the EH frame section
   // in a table until we receive a request to register all unregistered
   // EH frame sections with the memory manager.
   SmallVector<SID, 2> UnregisteredEHFrameSections;
   SmallVector<SID, 2> RegisteredEHFrameSections;
 
 public:

llvm/trunk/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldELF.cpp

 //===-- RuntimeDyldELF.cpp - Run-time dynamic linker for MC-JIT -*- C++ -*-===//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
 //
 // Implementation of ELF support for the MC-JIT runtime dynamic linker.
 //
 //===----------------------------------------------------------------------===//
 
 #include "RuntimeDyldELF.h"
+#include "RuntimeDyldCheckerImpl.h"
 #include "llvm/ADT/IntervalMap.h"
 #include "llvm/ADT/STLExtras.h"
 #include "llvm/ADT/StringRef.h"
 #include "llvm/ADT/Triple.h"
 #include "llvm/MC/MCStreamer.h"
 #include "llvm/Object/ELFObjectFile.h"
 #include "llvm/Object/ObjectFile.h"
 #include "llvm/Support/ELF.h"

 }
 
 } // namespace
 
 namespace llvm {
 
 RuntimeDyldELF::RuntimeDyldELF(RuntimeDyld::MemoryManager &MemMgr,
                                RuntimeDyld::SymbolResolver &Resolver)
-    : RuntimeDyldImpl(MemMgr, Resolver) {}
+    : RuntimeDyldImpl(MemMgr, Resolver), GOTSectionID(0), CurrentGOTIndex(0) {}
 RuntimeDyldELF::~RuntimeDyldELF() {}
 
 void RuntimeDyldELF::registerEHFrames() {
   for (int i = 0, e = UnregisteredEHFrameSections.size(); i != e; ++i) {
     SID EHFrameSID = UnregisteredEHFrameSections[i];
     uint8_t *EHFrameAddr = Sections[EHFrameSID].Address;
     uint64_t EHFrameLoadAddr = Sections[EHFrameSID].LoadAddress;
     size_t EHFrameSize = Sections[EHFrameSID].Size;
assert((Type == ELF::R_X86_64_32 && (Value <= UINT32_MAX)) ||
            (Type == ELF::R_X86_64_32S &&
             ((int64_t)Value <= INT32_MAX && (int64_t)Value >= INT32_MIN)));
     uint32_t TruncatedAddr = (Value & 0xFFFFFFFF);
     support::ulittle32_t::ref(Section.Address + Offset) = TruncatedAddr;
     DEBUG(dbgs() << "Writing " << format("%p", TruncatedAddr) << " at "
                  << format("%p\n", Section.Address + Offset));
     break;
   }
-  case ELF::R_X86_64_GOTPCREL: {
-    // findGOTEntry returns the 'G + GOT' part of the relocation calculation
-    // based on the load/target address of the GOT (not the current/local addr).
-    uint64_t GOTAddr = findGOTEntry(Value, SymOffset);
-    uint64_t FinalAddress = Section.LoadAddress + Offset;
-    // The processRelocationRef method combines the symbol offset and the addend
-    // and in most cases that's what we want.  For this relocation type, we need
-    // the raw addend, so we subtract the symbol offset to get it.
-    int64_t RealOffset = GOTAddr + Addend - SymOffset - FinalAddress;
-    assert(RealOffset <= INT32_MAX && RealOffset >= INT32_MIN);
-    int32_t TruncOffset = (RealOffset & 0xFFFFFFFF);
-    support::ulittle32_t::ref(Section.Address + Offset) = TruncOffset;
-    break;
-  }
   case ELF::R_X86_64_PC32: {
     // Get the placeholder value from the generated object since
     // a previous relocation attempt may have overwritten the loaded version
     support::ulittle32_t::ref Placeholder(
         (void *)(Section.ObjAddress + Offset));
     uint64_t FinalAddress = Section.LoadAddress + Offset;
-    int64_t RealOffset = Placeholder + Value + Addend - FinalAddress;
+    int64_t RealOffset = Value + Addend - FinalAddress;
+    // Don't add the placeholder if this is a stub
+    if (Offset < Section.Size)
+      RealOffset += Placeholder;
     assert(RealOffset <= INT32_MAX && RealOffset >= INT32_MIN);
     int32_t TruncOffset = (RealOffset & 0xFFFFFFFF);
     support::ulittle32_t::ref(Section.Address + Offset) = TruncOffset;
     break;
   }
   case ELF::R_X86_64_PC64: {
     // Get the placeholder value from the generated object since
     // a previous relocation attempt may have overwritten the loaded version
     support::ulittle64_t::ref Placeholder(
         (void *)(Section.ObjAddress + Offset));
     uint64_t FinalAddress = Section.LoadAddress + Offset;
-    support::ulittle64_t::ref(Section.Address + Offset) =
-        Placeholder + Value + Addend - FinalAddress;
+    int64_t RealOffset = Value + Addend - FinalAddress;
+    if (Offset < Section.Size)
+      RealOffset += Placeholder;
+    support::ulittle64_t::ref(Section.Address + Offset) = RealOffset;
     break;
   }
   }
 }
 
 void RuntimeDyldELF::resolveX86Relocation(const SectionEntry &Section,
                                           uint64_t Offset, uint32_t Value,
                                           uint32_t Type, int32_t Addend) {
if (Value.SymbolName) {
         uintptr_t BaseAddress = uintptr_t(Section.Address);
         uintptr_t StubAlignment = getStubAlignment();
         StubAddress = (BaseAddress + Section.StubOffset + StubAlignment - 1) &
                       -StubAlignment;
         unsigned StubOffset = StubAddress - BaseAddress;
         Stubs[Value] = StubOffset;
         createStubFunction((uint8_t *)StubAddress);
 
-        // Create a GOT entry for the external function.
-        GOTEntries.push_back(Value);
-
-        // Make our stub function a relative call to the GOT entry.
-        RelocationEntry RE(SectionID, StubOffset + 2, ELF::R_X86_64_GOTPCREL,
-                           -4);
-        addRelocationForSymbol(RE, Value.SymbolName);
-
         // Bump our stub offset counter
         Section.StubOffset = StubOffset + getMaxStubSize();
+
+        // Allocate a GOT Entry
+        uint64_t GOTOffset = allocateGOTEntries(SectionID, 1);
+
+        // The load of the GOT address has an addend of -4
+        resolveGOTOffsetRelocation(SectionID, StubOffset + 2, GOTOffset - 4);
+
+        // Fill in the value of the symbol we're targeting into the GOT
+        addRelocationForSymbol(computeGOTOffsetRE(SectionID,GOTOffset,0,ELF::R_X86_64_64),
+            Value.SymbolName);
       }
 
       // Make the target call a call into the stub table.
       resolveRelocation(Section, Offset, StubAddress, ELF::R_X86_64_PC32,
                         Addend);
     } else {
       RelocationEntry RE(SectionID, Offset, ELF::R_X86_64_PC32, Value.Addend,
                          Value.Offset);
       addRelocationForSection(RE, Value.SectionID);
     }
+  } else if (Arch == Triple::x86_64 && RelType == ELF::R_X86_64_GOTPCREL) {
+    uint64_t GOTOffset = allocateGOTEntries(SectionID, 1);
+    resolveGOTOffsetRelocation(SectionID, Offset, GOTOffset + Addend);
+
+    // Fill in the value of the symbol we're targeting into the GOT
+    RelocationEntry RE = computeGOTOffsetRE(SectionID, GOTOffset, Value.Offset, ELF::R_X86_64_64);
+    if (Value.SymbolName)
+      addRelocationForSymbol(RE, Value.SymbolName);
+    else
+      addRelocationForSection(RE, Value.SectionID);
   } else {
-    if (Arch == Triple::x86_64 && RelType == ELF::R_X86_64_GOTPCREL) {
-      GOTEntries.push_back(Value);
-    }
     RelocationEntry RE(SectionID, Offset, RelType, Value.Addend, Value.Offset);
     if (Value.SymbolName)
       addRelocationForSymbol(RE, Value.SymbolName);
     else
       addRelocationForSection(RE, Value.SectionID);
   }
   return ++RelI;
 }
 
-void RuntimeDyldELF::updateGOTEntries(StringRef Name, uint64_t Addr) {
-
-  SmallVectorImpl<std::pair<SID, GOTRelocations>>::iterator it;
-  SmallVectorImpl<std::pair<SID, GOTRelocations>>::iterator end = GOTs.end();
-
-  for (it = GOTs.begin(); it != end; ++it) {
-    GOTRelocations &GOTEntries = it->second;
-    for (int i = 0, e = GOTEntries.size(); i != e; ++i) {
-      if (GOTEntries[i].SymbolName != nullptr &&
-          GOTEntries[i].SymbolName == Name) {
-        GOTEntries[i].Offset = Addr;
-      }
-    }
-  }
-}
-
 size_t RuntimeDyldELF::getGOTEntrySize() {
   // We don't use the GOT in all of these cases, but it's essentially free
   // to put them all here.
   size_t Result = 0;
   switch (Arch) {
   case Triple::x86_64:
   case Triple::aarch64:
   case Triple::aarch64_be:
case Triple::mipsel:
     Result = sizeof(uint32_t);
     break;
   default:
     llvm_unreachable("Unsupported CPU type!");
   }
   return Result;
 }
 
-uint64_t RuntimeDyldELF::findGOTEntry(uint64_t LoadAddress, uint64_t Offset) {
-
-  const size_t GOTEntrySize = getGOTEntrySize();
-
-  SmallVectorImpl<std::pair<SID, GOTRelocations>>::const_iterator it;
-  SmallVectorImpl<std::pair<SID, GOTRelocations>>::const_iterator end =
-      GOTs.end();
-
-  int GOTIndex = -1;
-  for (it = GOTs.begin(); it != end; ++it) {
-    SID GOTSectionID = it->first;
-    const GOTRelocations &GOTEntries = it->second;
-
-    // Find the matching entry in our vector.
-    uint64_t SymbolOffset = 0;
-    for (int i = 0, e = GOTEntries.size(); i != e; ++i) {
-      if (!GOTEntries[i].SymbolName) {
-        if (getSectionLoadAddress(GOTEntries[i].SectionID) == LoadAddress &&
-            GOTEntries[i].Offset == Offset) {
-          GOTIndex = i;
-          SymbolOffset = GOTEntries[i].Offset;
-          break;
-        }
-      } else {
-        // GOT entries for external symbols use the addend as the address when
-        // the external symbol has been resolved.
-        if (GOTEntries[i].Offset == LoadAddress) {
-          GOTIndex = i;
-          // Don't use the Addend here.  The relocation handler will use it.
-          break;
-        }
-      }
-    }
-
-    if (GOTIndex != -1) {
-      if (GOTEntrySize == sizeof(uint64_t)) {
-        uint64_t *LocalGOTAddr = (uint64_t *)getSectionAddress(GOTSectionID);
-        // Fill in this entry with the address of the symbol being referenced.
-        LocalGOTAddr[GOTIndex] = LoadAddress + SymbolOffset;
-      } else {
-        uint32_t *LocalGOTAddr = (uint32_t *)getSectionAddress(GOTSectionID);
-        // Fill in this entry with the address of the symbol being referenced.
-        LocalGOTAddr[GOTIndex] = (uint32_t)(LoadAddress + SymbolOffset);
-      }
-
-      // Calculate the load address of this entry
-      return getSectionLoadAddress(GOTSectionID) + (GOTIndex * GOTEntrySize);
-    }
-  }
-
-  assert(GOTIndex != -1 && "Unable to find requested GOT entry.");
-  return 0;
+uint64_t RuntimeDyldELF::allocateGOTEntries(unsigned SectionID, unsigned no)
+{
+  (void)SectionID; // The GOT Section is the same for all section in the object file
+  if (GOTSectionID == 0) {
+    GOTSectionID = Sections.size();
+    // Reserve a section id. We'll allocate the section later
+    // once we know the total size
+    Sections.push_back(SectionEntry(".got", 0, 0, 0));
+  }
+  uint64_t StartOffset = CurrentGOTIndex * getGOTEntrySize();
+  CurrentGOTIndex += no;
+  return StartOffset;
+}
+
+void RuntimeDyldELF::resolveGOTOffsetRelocation(unsigned SectionID, uint64_t Offset, uint64_t GOTOffset)
+{
+  // Fill in the relative address of the GOT Entry into the stub
+  RelocationEntry GOTRE(SectionID, Offset, ELF::R_X86_64_PC32, GOTOffset);
+  addRelocationForSection(GOTRE, GOTSectionID);
+}
+
+RelocationEntry RuntimeDyldELF::computeGOTOffsetRE(unsigned SectionID, uint64_t GOTOffset, uint64_t SymbolOffset,
+                                                   uint32_t Type)
+{
+  (void)SectionID; // The GOT Section is the same for all section in the object file
+  return RelocationEntry(GOTSectionID, GOTOffset, Type, SymbolOffset);
 }
 
 void RuntimeDyldELF::finalizeLoad(const ObjectFile &Obj,
                                   ObjSectionToIDMap &SectionMap) {
   // If necessary, allocate the global offset table
-  size_t numGOTEntries = GOTEntries.size();
-  if (numGOTEntries != 0) {
+  if (GOTSectionID != 0) {
     // Allocate memory for the section
-    unsigned SectionID = Sections.size();
-    size_t TotalSize = numGOTEntries * getGOTEntrySize();
+    size_t TotalSize = CurrentGOTIndex * getGOTEntrySize();
     uint8_t *Addr = MemMgr.allocateDataSection(TotalSize, getGOTEntrySize(),
-                                               SectionID, ".got", false);
+                                                GOTSectionID, ".got", false);
     if (!Addr)
       report_fatal_error("Unable to allocate memory for GOT!");
 
-    GOTs.push_back(std::make_pair(SectionID, GOTEntries));
-    Sections.push_back(SectionEntry(".got", Addr, TotalSize, 0));
+    Sections[GOTSectionID] = SectionEntry(".got", Addr, TotalSize, 0);
+
+    if (Checker)
+      Checker->registerSection(Obj.getFileName(), GOTSectionID);
+
     // For now, initialize all GOT entries to zero.  We'll fill them in as
     // needed when GOT-based relocations are applied.
     memset(Addr, 0, TotalSize);
   }
 
   // Look for and record the EH frame section.
   ObjSectionToIDMap::iterator i, e;
   for (i = SectionMap.begin(), e = SectionMap.end(); i != e; ++i) {
     const SectionRef &Section = i->first;
     StringRef Name;
     Section.getName(Name);
     if (Name == ".eh_frame") {
       UnregisteredEHFrameSections.push_back(i->second);
       break;
     }
   }
+
+  GOTSectionID = 0;
+  CurrentGOTIndex = 0;
 }
 
 bool RuntimeDyldELF::isCompatibleFile(const object::ObjectFile &Obj) const {
   return Obj.isELF();
 }
 
 } // namespace llvm

llvm/trunk/lib/ExecutionEngine/RuntimeDyld/RuntimeDyldImpl.h

#define RTDYLD_INVALID_SECTION_ID ((SID)(-1))
   virtual relocation_iterator
   processRelocationRef(unsigned SectionID, relocation_iterator RelI,
                        const ObjectFile &Obj, ObjSectionToIDMap &ObjSectionToID,
                        StubMap &Stubs) = 0;
 
   /// \brief Resolve relocations to external symbols.
   void resolveExternalSymbols();
 
-  /// \brief Update GOT entries for external symbols.
-  // The base class does nothing.  ELF overrides this.
-  virtual void updateGOTEntries(StringRef Name, uint64_t Addr) {}
-
   // \brief Compute an upper bound of the memory that is required to load all
   // sections
   void computeTotalAllocSize(const ObjectFile &Obj, uint64_t &CodeSize,
                              uint64_t &DataSizeRO, uint64_t &DataSizeRW);
 
   // \brief Compute the stub buffer size required for a section
   unsigned computeSectionStubBufSize(const ObjectFile &Obj,
                                      const SectionRef &Section);

llvm/trunk/test/ExecutionEngine/MCJIT/cross-module-sm-pic-a.ll

 ; RUN: %lli -extra-module=%p/Inputs/cross-module-b.ll -relocation-model=pic -code-model=small %s > /dev/null
+; RUN: %lli -mtriple=x86_64-pc-linux -extra-module=%p/Inputs/cross-module-b.ll -relocation-model=pic -code-model=small %s > /dev/null
 ; XFAIL: mips, i686, i386
 
 declare i32 @FB()
 
 define i32 @FA() {
   ret i32 0
 }
 
 define i32 @main() {
   %r = call i32 @FB( )   ; <i32> [#uses=1]
   ret i32 %r
 }
 

llvm/trunk/test/ExecutionEngine/RuntimeDyld/X86/ELF_x64-64_PIC_relocations.s

+# RUN: llvm-mc -triple=x86_64-pc-linux -relocation-model=pic -filetype=obj -o %T/test_ELF1_x86-64.o %s
+# RUN: llvm-mc -triple=x86_64-pc-linux -relocation-model=pic -filetype=obj -o %T/test_ELF2_x86-64.o %s
+# RUN: llc -mtriple=x86_64-pc-linux -relocation-model=pic -filetype=obj -o %T/test_ELF_ExternalGlobal_x86-64.o %S/Inputs/ExternalGlobal.ll
+# RUN: llvm-rtdyld -triple=x86_64-pc-linux -verify %T/test_ELF1_x86-64.o  %T/test_ELF_ExternalGlobal_x86-64.o
+# Test that we can load this code twice at memory locations more than 2GB apart
+# RUN: llvm-rtdyld -triple=x86_64-pc-linux -verify -map-section test_ELF1_x86-64.o,.got=0x10000 -map-section test_ELF2_x86-64.o,.text=0x100000000 -map-section test_ELF2_x86-64.o,.got=0x100010000 %T/test_ELF1_x86-64.o %T/test_ELF2_x86-64.o %T/test_ELF_ExternalGlobal_x86-64.o
+
+# Assembly obtained by compiling the following and adding checks:
+# @G = external global i8*
+#
+# define i8* @foo() {
+#    %ret = load i8** @G
+#    ret i32 %ret
+# }
+#
+
+#
+  .text
+  .file "ELF_x64-64_PIC_relocations.ll"
+  .align  16, 0x90
+  .type foo,@function
+foo:                                    # @foo
+# BB#0:
+  movq  G@GOTPCREL(%rip), %rax
+  movl  (%rax), %eax
+  retq
+.Ltmp0:
+  .size foo, .Ltmp0-foo
+
+
+  .section  ".note.GNU-stack","",@progbits

llvm/trunk/test/ExecutionEngine/RuntimeDyld/X86/Inputs/ExternalGlobal.ll

+@F = global i8 0
+@G = global i8* @F