Adds absolute and pc relative relocation support for ELF/i386

[jain98]

Adds absolute and pc relative relocation support for ELF/i386

llvm/include/llvm/ExecutionEngine/JITLink/i386.h

 //=== i386.h - Generic JITLink i386 edge kinds, utilities -*- C++ -*-===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Generic utilities for graphs representing i386 objects.
 //
 //===----------------------------------------------------------------------===//
 
 #ifndef LLVM_EXECUTIONENGINE_JITLINK_I386_H
 #define LLVM_EXECUTIONENGINE_JITLINK_I386_H
 
 #include "llvm/ExecutionEngine/JITLink/JITLink.h"
+#include "llvm/ExecutionEngine/JITLink/TableManager.h"
 
-namespace llvm {
-namespace jitlink {
-namespace i386 {
-
+namespace llvm::jitlink::i386 {
 /// Represets i386 fixups
 enum EdgeKind_i386 : Edge::Kind {
 
   /// None
   None = Edge::FirstRelocation,
 
+  /// A plain 32-bit pointer value relocation.
+  ///
+  /// Fixup expression:
+  ///   Fixup <- Target + Addend : uint32
+  ///
+  /// Errors:
+  ///   - The target must reside in the low 32-bits of the address space,
+  ///     otherwise an out-of-range error will be returned.
+  ///
+  Pointer32,
+
+  /// A 32-bit PC-relative relocation.
+  ///
+  /// Represents a data/control flow instruction using PC-relative addressing
+  /// to a target.
+  ///
+  /// The fixup expression for this kind includes an implicit offset to account
+  /// for the PC (unlike the Delta edges) so that a PCRel32 with a target
+  /// T and addend zero is a call/branch to the start (offset zero) of T.
+  ///
+  /// Fixup expression:
+  ///   Fixup <- Target - (Fixup + 4) + Addend : int32
+  ///
+  /// Errors:
+  ///   - The result of the fixup expression must fit into an int32, otherwise
+  ///     an out-of-range error will be returned.
+  ///
+  PCRel32,
+
+  /// A plain 16-bit pointer value relocation.
+  ///
+  /// Fixup expression:
+  ///   Fixup <- Target + Addend : uint16
+  ///
+  /// Errors:
+  ///   - The target must reside in the low 16-bits of the address space,
+  ///     otherwise an out-of-range error will be returned.
+  ///
+  Pointer16,
+
+  /// A 16-bit PC-relative relocation.
+  ///
+  /// Represents a data/control flow instruction using PC-relative addressing
+  /// to a target.
+  ///
+  /// The fixup expression for this kind includes an implicit offset to account
+  /// for the PC (unlike the Delta edges) so that a PCRel16 with a target
+  /// T and addend zero is a call/branch to the start (offset zero) of T.
+  ///
+  /// Fixup expression:
+  ///   Fixup <- Target - (Fixup + 4) + Addend : int16
+  ///
+  /// Errors:
+  ///   - The result of the fixup expression must fit into an int16, otherwise
+  ///     an out-of-range error will be returned.
+  ///
+  PCRel16,
+
+  /// A 64-bit GOT delta.
+  ///
+  /// Delta from the global offset table to the target.
+  ///
+  /// Fixup expression:
+  ///   Fixup <- Target - GOTSymbol + Addend : int32
+  ///
+  /// Errors:
+  ///   - *ASSERTION* Failure to a null pointer GOTSymbol, which the GOT section
+  ///     symbol was not been defined.
+  Delta32FromGOT,
 };
 
 /// Returns a string name for the given i386 edge. For debugging purposes
 /// only
 const char *getEdgeKindName(Edge::Kind K);
 
-} // namespace i386
-} // namespace jitlink
-} // namespace llvm
+/// Returns true if the given uint32_t value is in range for a uint16_t.
+inline bool isInRangeForImmU16(uint32_t Value) {
+  return Value <= std::numeric_limits<uint16_t>::max();
+}
+
+/// Returns true if the given int32_t value is in range for an int16_t.
+inline bool isInRangeForImmS16(int32_t Value) {
+  return (Value >= std::numeric_limits<int16_t>::min() &&
+          Value <= std::numeric_limits<int16_t>::max());
+}
+
+/// Apply fixup expression for edge to block content.
+inline Error applyFixup(LinkGraph &G, Block &B, const Edge &E) {
+  using namespace i386;
+  using namespace llvm::support;
+
+  char *BlockWorkingMem = B.getAlreadyMutableContent().data();
+  char *FixupPtr = BlockWorkingMem + E.getOffset();
+  auto FixupAddress = B.getAddress() + E.getOffset();
+
+  switch (E.getKind()) {
+  case i386::None: {
+    break;
+  }
+
+  case i386::Pointer32: {
+    uint32_t Value = E.getTarget().getAddress().getValue() + E.getAddend();
+    *(ulittle32_t *)FixupPtr = Value;
+    break;
+  }
+
+  case i386::PCRel32: {
+    int32_t Value =
+        E.getTarget().getAddress() - (FixupAddress + 4) + E.getAddend();
+    *(little32_t *)FixupPtr = Value;
+    break;
+  }
+
+  case i386::Pointer16: {
+    uint32_t Value = E.getTarget().getAddress().getValue() + E.getAddend();
+    if (LLVM_LIKELY(isInRangeForImmU16(Value)))
+      *(ulittle16_t *)FixupPtr = Value;
+    else
+      return makeTargetOutOfRangeError(G, B, E);
+    break;
+  }
+
+  case i386::PCRel16: {
+    int32_t Value =
+        E.getTarget().getAddress() - (FixupAddress + 4) + E.getAddend();
+    if (LLVM_LIKELY(isInRangeForImmS16(Value)))
+      *(little16_t *)FixupPtr = Value;
+    else
+      return makeTargetOutOfRangeError(G, B, E);
+    break;
+  }
+
+  default:
+    return make_error<JITLinkError>(
+        "In graph " + G.getName() + ", section " + B.getSection().getName() +
+        "unsupported edge kind" + getEdgeKindName(E.getKind()));
+  }
+
+  return Error::success();
+}
+} // namespace llvm::jitlink::i386
 
 #endif // LLVM_EXECUTIONENGINE_JITLINK_I386_H
 No newline at end of file

llvm/lib/ExecutionEngine/JITLink/ELFLinkGraphBuilder.h

protected:
 
   Expected<std::pair<Linkage, Scope>>
   getSymbolLinkageAndScope(const typename ELFT::Sym &Sym, StringRef Name);
 
   Error prepare();
   Error graphifySections();
   Error graphifySymbols();
 
-  /// Traverse all matching relocation records in the given section. The handler
-  /// function Func should be callable with this signature:
+  /// Traverse all matching ELFT::Rela relocation records in the given section.
+  /// The handler function Func should be callable with this signature:
   ///   Error(const typename ELFT::Rela &,
   ///         const typename ELFT::Shdr &, Section &)
   ///
-  template <typename RelocHandlerFunction>
-  Error forEachRelocation(const typename ELFT::Shdr &RelSect,
-                          RelocHandlerFunction &&Func,
+  template <typename RelocHandlerMethod>
+  Error forEachRelaRelocation(const typename ELFT::Shdr &RelSect,
+                          RelocHandlerMethod &&Func,
                           bool ProcessDebugSections = false);
 
-  /// Traverse all matching relocation records in the given section. Convenience
-  /// wrapper to allow passing a member function for the handler.
+  /// Traverse all matching ELFT::Rel relocation records in the given section.
+  /// The handler function Func should be callable with this signature:
+  ///   Error(const typename ELFT::Rel &,
+  ///         const typename ELFT::Shdr &, Section &)
+  ///
+  template <typename RelocHandlerMethod>
+  Error forEachRelRelocation(const typename ELFT::Shdr &RelSect,
+                          RelocHandlerMethod &&Func,
+                          bool ProcessDebugSections = false);
+
+  /// Traverse all matching rela relocation records in the given section. 
+  /// Convenience wrapper to allow passing a member function for the handler.
+  ///
+  template <typename ClassT, typename RelocHandlerMethod>
+  Error forEachRelaRelocation(const typename ELFT::Shdr &RelSect, ClassT *Instance,
+                          RelocHandlerMethod &&Method,
+                          bool ProcessDebugSections = false) {
+    return forEachRelaRelocation(
+        RelSect,
+        [Instance, Method](const auto &Rel, const auto &Target, auto &GS) {
+          return (Instance->*Method)(Rel, Target, GS);
+        },
+        ProcessDebugSections);
+  }
+
+  /// Traverse all matching rel relocation records in the given section. 
+  /// Convenience wrapper to allow passing a member function for the handler.
   ///
   template <typename ClassT, typename RelocHandlerMethod>
-  Error forEachRelocation(const typename ELFT::Shdr &RelSect, ClassT *Instance,
+  Error forEachRelRelocation(const typename ELFT::Shdr &RelSect, ClassT *Instance,
                           RelocHandlerMethod &&Method,
                           bool ProcessDebugSections = false) {
-    return forEachRelocation(
+    return forEachRelRelocation(
         RelSect,
         [Instance, Method](const auto &Rel, const auto &Target, auto &GS) {
           return (Instance->*Method)(Rel, Target, GS);
         },
         ProcessDebugSections);
   }
 
   const ELFFile &Obj;
if (Sym.isDefined() &&
       });
     }
   }
 
   return Error::success();
 }
 
 template <typename ELFT>
-template <typename RelocHandlerFunction>
-Error ELFLinkGraphBuilder<ELFT>::forEachRelocation(
-    const typename ELFT::Shdr &RelSect, RelocHandlerFunction &&Func,
+template <typename RelocHandlerMethod>
+Error ELFLinkGraphBuilder<ELFT>::forEachRelaRelocation(
+    const typename ELFT::Shdr &RelSect, RelocHandlerMethod &&Func,
     bool ProcessDebugSections) {
-
   // Only look into sections that store relocation entries.
-  if (RelSect.sh_type != ELF::SHT_RELA && RelSect.sh_type != ELF::SHT_REL)
+  if (RelSect.sh_type != ELF::SHT_RELA)
     return Error::success();
 
   // sh_info contains the section header index of the target (FixupSection),
   // which is the section to which all relocations in RelSect apply.
   auto FixupSection = Obj.getSection(RelSect.sh_info);
   if (!FixupSection)
     return FixupSection.takeError();
 
Error ELFLinkGraphBuilder<ELFT>::forEachRelaRelocation(
   for (const typename ELFT::Rela &R : *RelEntries)
     if (Error Err = Func(R, **FixupSection, *BlockToFix))
       return Err;
 
   LLVM_DEBUG(dbgs() << "\n");
   return Error::success();
 }
 
+template <typename ELFT>
+template <typename RelocHandlerMethod>
+Error ELFLinkGraphBuilder<ELFT>::forEachRelRelocation(
+    const typename ELFT::Shdr &RelSect, RelocHandlerMethod &&Func,
+    bool ProcessDebugSections) {
+  // Only look into sections that store relocation entries.
+  if (RelSect.sh_type != ELF::SHT_REL)
+    return Error::success();
+
+  // sh_info contains the section header index of the target (FixupSection),
+  // which is the section to which all relocations in RelSect apply.
+  auto FixupSection = Obj.getSection(RelSect.sh_info);
+  if (!FixupSection)
+    return FixupSection.takeError();
+
+  // Target sections have names in valid ELF object files.
+  Expected<StringRef> Name = Obj.getSectionName(**FixupSection);
+  if (!Name)
+    return Name.takeError();
+  LLVM_DEBUG(dbgs() << "  " << *Name << ":\n");
+
+  // Consider skipping these relocations.
+  if (!ProcessDebugSections && isDwarfSection(*Name)) {
+    LLVM_DEBUG(dbgs() << "    skipped (dwarf section)\n\n");
+    return Error::success();
+  }
+
+  // Lookup the link-graph node corresponding to the target section name.
+  auto *BlockToFix = getGraphBlock(RelSect.sh_info);
+  if (!BlockToFix)
+    return make_error<StringError>(
+        "Refencing a section that wasn't added to the graph: " + *Name,
+        inconvertibleErrorCode());
+
+  auto RelEntries = Obj.rels(RelSect);
+  if (!RelEntries)
+    return RelEntries.takeError();
+
+  // Let the callee process relocation entries one by one.
+  for (const typename ELFT::Rel &R : *RelEntries)
+    if (Error Err = Func(R, **FixupSection, *BlockToFix))
+      return Err;
+
+  LLVM_DEBUG(dbgs() << "\n");
+  return Error::success();
+}
+
 } // end namespace jitlink
 } // end namespace llvm
 
 #undef DEBUG_TYPE
 
 #endif // LIB_EXECUTIONENGINE_JITLINK_ELFLINKGRAPHBUILDER_H

llvm/lib/ExecutionEngine/JITLink/ELF_aarch64.cpp

private:
   }
 
   Error addRelocations() override {
     LLVM_DEBUG(dbgs() << "Processing relocations:\n");
 
     using Base = ELFLinkGraphBuilder<ELFT>;
     using Self = ELFLinkGraphBuilder_aarch64<ELFT>;
     for (const auto &RelSect : Base::Sections)
-      if (Error Err = Base::forEachRelocation(RelSect, this,
+      if (Error Err = Base::forEachRelaRelocation(RelSect, this,
                                               &Self::addSingleRelocation))
         return Err;
 
     return Error::success();
   }
 
   Error addSingleRelocation(const typename ELFT::Rela &Rel,
                             const typename ELFT::Shdr &FixupSect,

llvm/lib/ExecutionEngine/JITLink/ELF_i386.cpp

 #include "llvm/ExecutionEngine/JITLink/i386.h"
 #include "llvm/Object/ELFObjectFile.h"
 
 #define DEBUG_TYPE "jitlink"
 
 using namespace llvm;
 using namespace llvm::jitlink;
 
-namespace llvm {
-namespace jitlink {
+namespace llvm::jitlink {
 
 class ELFJITLinker_i386 : public JITLinker<ELFJITLinker_i386> {
   friend class JITLinker<ELFJITLinker_i386>;
 
 public:
   ELFJITLinker_i386(std::unique_ptr<JITLinkContext> Ctx,
                     std::unique_ptr<LinkGraph> G, PassConfiguration PassConfig)
       : JITLinker(std::move(Ctx), std::move(G), std::move(PassConfig)) {}
 
 private:
   Error applyFixup(LinkGraph &G, Block &B, const Edge &E) const {
-    using namespace i386;
-    using namespace llvm::support;
-
-    switch (E.getKind()) {
-    case i386::None: {
-      break;
-    }
-    }
-    return Error::success();
+    return i386::applyFixup(G, B, E);
   }
 };
 
 template <typename ELFT>
 class ELFLinkGraphBuilder_i386 : public ELFLinkGraphBuilder<ELFT> {
 private:
   static Expected<i386::EdgeKind_i386> getRelocationKind(const uint32_t Type) {
     using namespace i386;
     switch (Type) {
     case ELF::R_386_NONE:
       return EdgeKind_i386::None;
+    case ELF::R_386_32:
+      return EdgeKind_i386::Pointer32;
+    case ELF::R_386_PC32:
+      return EdgeKind_i386::PCRel32;
+    case ELF::R_386_16:
+      return EdgeKind_i386::Pointer16;
+    case ELF::R_386_PC16:
+      return EdgeKind_i386::PCRel16;
+    case ELF::R_386_GOTPC:
+      return EdgeKind_i386::Delta32FromGOT;
     }
 
     return make_error<JITLinkError>("Unsupported i386 relocation:" +
                                     formatv("{0:d}", Type));
   }
 
   Error addRelocations() override {
     LLVM_DEBUG(dbgs() << "Adding relocations\n");
+    using Base = ELFLinkGraphBuilder<ELFT>;
+    using Self = ELFLinkGraphBuilder_i386;
+
+    for (const auto &RelSect : Base::Sections) {
+      // Validate the section to read relocation entries from.
+      if (RelSect.sh_type == ELF::SHT_RELA)
+        return make_error<StringError>(
+            "No SHT_RELA in valid i386 ELF object files",
+            inconvertibleErrorCode());
+
+      if (Error Err = Base::forEachRelRelocation(RelSect, this,
+                                                 &Self::addSingleRelocation))
+        return Err;
+    }
+
+    return Error::success();
+  }
+
+  Error addSingleRelocation(const typename ELFT::Rel &Rel,
+                            const typename ELFT::Shdr &FixupSection,
+                            Block &BlockToFix) {
+    using Base = ELFLinkGraphBuilder<ELFT>;
+
+    uint32_t SymbolIndex = Rel.getSymbol(false);
+    auto ObjSymbol = Base::Obj.getRelocationSymbol(Rel, Base::SymTabSec);
+    if (!ObjSymbol)
+      return ObjSymbol.takeError();
+
+    Symbol *GraphSymbol = Base::getGraphSymbol(SymbolIndex);
+    if (!GraphSymbol)
+      return make_error<StringError>(
+          formatv("Could not find symbol at given index, did you add it to "
+                  "JITSymbolTable? index: {0}, shndx: {1} Size of table: {2}",
+                  SymbolIndex, (*ObjSymbol)->st_shndx,
+                  Base::GraphSymbols.size()),
+          inconvertibleErrorCode());
+
+    Expected<i386::EdgeKind_i386> Kind = getRelocationKind(Rel.getType(false));
+    if (!Kind)
+      return Kind.takeError();
+
+    // TODO: Add a reason for why we're ignoring adding an edge
+    // for a GOT relative relocation
+    if (*Kind == i386::EdgeKind_i386::Delta32FromGOT)
+      return Error::success();
+
+    int64_t Addend = 0;
+
+    auto FixupAddress = orc::ExecutorAddr(FixupSection.sh_addr) + Rel.r_offset;
+    Edge::OffsetT Offset = FixupAddress - BlockToFix.getAddress();
+    Edge GE(*Kind, Offset, *GraphSymbol, Addend);
+    LLVM_DEBUG({
+      dbgs() << "    ";
+      printEdge(dbgs(), BlockToFix, GE, i386::getEdgeKindName(*Kind));
+      dbgs() << "\n";
+    });
+
+    BlockToFix.addEdge(std::move(GE));
+
     return Error::success();
   }
 
 public:
   ELFLinkGraphBuilder_i386(StringRef FileName, const object::ELFFile<ELFT> &Obj,
                            const Triple T)
       : ELFLinkGraphBuilder<ELFT>(Obj, std::move(T), FileName,
                                   i386::getEdgeKindName) {}
else
       Config.PrePrunePasses.push_back(markAllSymbolsLive);
   }
   if (auto Err = Ctx->modifyPassConfig(*G, Config))
     return Ctx->notifyFailed(std::move(Err));
 
   ELFJITLinker_i386::link(std::move(Ctx), std::move(G), std::move(Config));
 }
 
-} // namespace jitlink
-} // namespace llvm
+} // namespace llvm::jitlink
 

llvm/lib/ExecutionEngine/JITLink/ELF_riscv.cpp

private:
   }
 
   Error addRelocations() override {
     LLVM_DEBUG(dbgs() << "Processing relocations:\n");
 
     using Base = ELFLinkGraphBuilder<ELFT>;
     using Self = ELFLinkGraphBuilder_riscv<ELFT>;
     for (const auto &RelSect : Base::Sections)
-      if (Error Err = Base::forEachRelocation(RelSect, this,
+      if (Error Err = Base::forEachRelaRelocation(RelSect, this,
                                               &Self::addSingleRelocation))
         return Err;
 
     return Error::success();
   }
 
   Error addSingleRelocation(const typename ELFT::Rela &Rel,
                             const typename ELFT::Shdr &FixupSect,

llvm/lib/ExecutionEngine/JITLink/ELF_x86_64.cpp

Error addRelocations() override {
     using Self = ELFLinkGraphBuilder_x86_64;
     for (const auto &RelSect : Base::Sections) {
       // Validate the section to read relocation entries from.
       if (RelSect.sh_type == ELF::SHT_REL)
         return make_error<StringError>(
             "No SHT_REL in valid x64 ELF object files",
             inconvertibleErrorCode());
 
-      if (Error Err = Base::forEachRelocation(RelSect, this,
+      if (Error Err = Base::forEachRelaRelocation(RelSect, this,
                                               &Self::addSingleRelocation))
         return Err;
     }
 
     return Error::success();
   }
 
   Error addSingleRelocation(const typename ELFT::Rela &Rel,

llvm/lib/ExecutionEngine/JITLink/i386.cpp

 //===---- i386.cpp - Generic JITLink i386 edge kinds, utilities -----===//
 //
 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
 // See https://llvm.org/LICENSE.txt for license information.
 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
 //
 //===----------------------------------------------------------------------===//
 //
 // Generic utilities for graphs representing i386 objects.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/ExecutionEngine/JITLink/i386.h"
 
 #define DEBUG_TYPE "jitlink"
 
-namespace llvm {
-namespace jitlink {
-namespace i386 {
+namespace llvm::jitlink::i386 {
 
 const char *getEdgeKindName(Edge::Kind K) {
   switch (K) {
   case None:
     return "None";
+  case Pointer32:
+    return "Pointer32";
+  case PCRel32:
+    return "PCRel32";
+  case Pointer16:
+    return "Pointer16";
+  case PCRel16:
+    return "PCRel16";
   }
   return getGenericEdgeKindName(K);
 }
-} // namespace i386
-} // namespace jitlink
-} // namespace llvm
+} // namespace llvm::jitlink::i386
 

llvm/test/ExecutionEngine/JITLink/i386/ELF_i386_absolute_relocations_32.s

+# RUN: llvm-mc -triple=i386-unknown-linux-gnu -filetype=obj -o %t.o %s
+# RUN: llvm-jitlink -noexec %t.o
+
+        .text
+        .globl  main
+        .p2align        4
+        .type   main,@function
+main:
+    pushl   %ebp
+    movl    %esp, %ebp
+    pushl   %eax
+    movl    $0, -4(%ebp)
+    movl    a, %eax
+    addl    $4, %esp
+    popl    %ebp
+    retl
+
+        .size   main, .-main
+
+        .data
+        .p2align        2
+        .type   a,@object
+a:
+        .long   42
+        .size   a, 4
 No newline at end of file

llvm/test/ExecutionEngine/JITLink/i386/ELF_i386_pc_relative_relocations_32.s

+# RUN: llvm-mc -triple=i386-unknown-linux-gnu -filetype=obj -o %t.o %s
+# RUN: llvm-jitlink -noexec %t.o
+
+        .text
+        .section        .text.main
+        .globl  main
+        .p2align        4
+        .type   main,@function
+main:
+    pushl   %ebp
+    movl    %esp, %ebp
+    subl    $8, %esp
+    movl    $0, -4(%ebp)
+    calll   foo
+    addl    $8, %esp
+    popl    %ebp
+    retl
+
+        .size   main, .-main
+
+        .section        .text.foo
+        .p2align        4
+        .type   foo,@function
+foo:
+    pushl   %ebp
+    movl    %esp, %ebp
+    movl    $42, %eax
+    popl    %ebp
+    retl
+
+    .size       foo, .-foo
 No newline at end of file