1 //===---- ELF_x86_64.cpp -JIT linker implementation for ELF/x86-64 ----===//
2 //
3 // Part of the LLVM Project, under the Apache License v2.0 with LLVM Exceptions.
4 // See https://llvm.org/LICENSE.txt for license information.
5 // SPDX-License-Identifier: Apache-2.0 WITH LLVM-exception
6 //
7 //===----------------------------------------------------------------------===//
8 //
9 // ELF/x86-64 jit-link implementation.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "llvm/ExecutionEngine/JITLink/ELF_x86_64.h"
14 #include "llvm/ExecutionEngine/JITLink/JITLink.h"
15 #include "llvm/ExecutionEngine/JITLink/x86_64.h"
16 #include "llvm/Object/ELFObjectFile.h"
17 #include "llvm/Support/Endian.h"
18 
19 #include "DefineExternalSectionStartAndEndSymbols.h"
20 #include "EHFrameSupportImpl.h"
21 #include "ELFLinkGraphBuilder.h"
22 #include "JITLinkGeneric.h"
23 #include "PerGraphGOTAndPLTStubsBuilder.h"
24 
25 #define DEBUG_TYPE "jitlink"
26 
27 using namespace llvm;
28 using namespace llvm::jitlink;
29 using namespace llvm::jitlink::ELF_x86_64_Edges;
30 
31 namespace {
32 
33 constexpr StringRef ELFGOTSectionName = "$__GOT";
34 constexpr StringRef ELFGOTSymbolName = "_GLOBAL_OFFSET_TABLE_";
35 
36 class PerGraphGOTAndPLTStubsBuilder_ELF_x86_64
37     : public PerGraphGOTAndPLTStubsBuilder<
38           PerGraphGOTAndPLTStubsBuilder_ELF_x86_64> {
39 public:
40   static const uint8_t NullGOTEntryContent[8];
41   static const uint8_t StubContent[6];
42 
43   using PerGraphGOTAndPLTStubsBuilder<
44       PerGraphGOTAndPLTStubsBuilder_ELF_x86_64>::PerGraphGOTAndPLTStubsBuilder;
45 
46   bool isGOTEdgeToFix(Edge &E) const {
47     if (E.getKind() == x86_64::Delta64FromGOT) {
48       // We need to make sure that the GOT section exists, but don't otherwise
49       // need to fix up this edge.
50       getGOTSection();
51       return false;
52     }
53     return E.getKind() == x86_64::RequestGOTAndTransformToDelta32 ||
54            E.getKind() == x86_64::RequestGOTAndTransformToDelta64 ||
55            E.getKind() ==
56                x86_64::RequestGOTAndTransformToPCRel32GOTLoadREXRelaxable ||
57            E.getKind() == x86_64::RequestGOTAndTransformToDelta64FromGOT ||
58            E.getKind() ==
59                x86_64::RequestGOTAndTransformToPCRel32GOTLoadRelaxable;
60   }
61 
62   Symbol &createGOTEntry(Symbol &Target) {
63     auto &GOTEntryBlock = G.createContentBlock(
64         getGOTSection(), getGOTEntryBlockContent(), 0, 8, 0);
65     GOTEntryBlock.addEdge(x86_64::Pointer64, 0, Target, 0);
66     return G.addAnonymousSymbol(GOTEntryBlock, 0, 8, false, false);
67   }
68 
69   void fixGOTEdge(Edge &E, Symbol &GOTEntry) {
70     // If this is a PCRel32GOT/PCRel64GOT then change it to an ordinary
71     // PCRel32/PCRel64. If it is a PCRel32GOTLoad then leave it as-is for now:
72     // We will use the kind to check for GOT optimization opportunities in the
73     // optimizeMachO_x86_64_GOTAndStubs pass below.
74     // If it's a GOT64 leave it as is.
75     switch (E.getKind()) {
76     case x86_64::RequestGOTAndTransformToPCRel32GOTLoadREXRelaxable:
77       E.setKind(x86_64::PCRel32GOTLoadREXRelaxable);
78       break;
79     case x86_64::RequestGOTAndTransformToPCRel32GOTLoadRelaxable:
80       E.setKind(x86_64::PCRel32GOTLoadRelaxable);
81       break;
82     case x86_64::RequestGOTAndTransformToDelta64:
83       E.setKind(x86_64::Delta64);
84       break;
85     case x86_64::RequestGOTAndTransformToDelta64FromGOT:
86       E.setKind(x86_64::Delta64FromGOT);
87       break;
88     case x86_64::RequestGOTAndTransformToDelta32:
89       E.setKind(x86_64::Delta32);
90       break;
91     default:
92       llvm_unreachable("Unexpected GOT edge kind");
93     }
94 
95     E.setTarget(GOTEntry);
96     // Leave the edge addend as-is.
97   }
98 
99   bool isExternalBranchEdge(Edge &E) {
100     return E.getKind() == x86_64::BranchPCRel32 && !E.getTarget().isDefined();
101   }
102 
103   Symbol &createPLTStub(Symbol &Target) {
104     auto &StubContentBlock =
105         G.createContentBlock(getStubsSection(), getStubBlockContent(), 0, 1, 0);
106     // Re-use GOT entries for stub targets.
107     auto &GOTEntrySymbol = getGOTEntry(Target);
108     StubContentBlock.addEdge(x86_64::Delta32, 2, GOTEntrySymbol, -4);
109     return G.addAnonymousSymbol(StubContentBlock, 0, 6, true, false);
110   }
111 
112   void fixPLTEdge(Edge &E, Symbol &Stub) {
113     assert(E.getKind() == x86_64::BranchPCRel32 && "Not a Branch32 edge?");
114 
115     // Set the edge kind to Branch32ToPtrJumpStubBypassable to enable it to be
116     // optimized when the target is in-range.
117     E.setKind(x86_64::BranchPCRel32ToPtrJumpStubBypassable);
118     E.setTarget(Stub);
119   }
120 
121 private:
122   Section &getGOTSection() const {
123     if (!GOTSection)
124       GOTSection = &G.createSection(ELFGOTSectionName, sys::Memory::MF_READ);
125     return *GOTSection;
126   }
127 
128   Section &getStubsSection() const {
129     if (!StubsSection) {
130       auto StubsProt = static_cast<sys::Memory::ProtectionFlags>(
131           sys::Memory::MF_READ | sys::Memory::MF_EXEC);
132       StubsSection = &G.createSection("$__STUBS", StubsProt);
133     }
134     return *StubsSection;
135   }
136 
137   ArrayRef<char> getGOTEntryBlockContent() {
138     return {reinterpret_cast<const char *>(NullGOTEntryContent),
139             sizeof(NullGOTEntryContent)};
140   }
141 
142   ArrayRef<char> getStubBlockContent() {
143     return {reinterpret_cast<const char *>(StubContent), sizeof(StubContent)};
144   }
145 
146   mutable Section *GOTSection = nullptr;
147   mutable Section *StubsSection = nullptr;
148 };
149 
150 } // namespace
151 
152 const uint8_t PerGraphGOTAndPLTStubsBuilder_ELF_x86_64::NullGOTEntryContent[8] =
153     {0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
154 const uint8_t PerGraphGOTAndPLTStubsBuilder_ELF_x86_64::StubContent[6] = {
155     0xFF, 0x25, 0x00, 0x00, 0x00, 0x00};
156 
157 static const char *getELFX86_64RelocName(uint32_t Type) {
158   switch (Type) {
159 #define ELF_RELOC(Name, Number)                                                \
160   case Number:                                                                 \
161     return #Name;
162 #include "llvm/BinaryFormat/ELFRelocs/x86_64.def"
163 #undef ELF_RELOC
164   }
165   return "Unrecognized ELF/x86-64 relocation type";
166 }
167 
168 namespace llvm {
169 namespace jitlink {
170 
171 // This should become a template as the ELFFile is so a lot of this could become
172 // generic
173 class ELFLinkGraphBuilder_x86_64 : public ELFLinkGraphBuilder<object::ELF64LE> {
174 private:
175 
176   static Expected<ELF_x86_64_Edges::ELFX86RelocationKind>
177   getRelocationKind(const uint32_t Type) {
178     switch (Type) {
179     case ELF::R_X86_64_PC32:
180       return ELF_x86_64_Edges::ELFX86RelocationKind::PCRel32;
181     case ELF::R_X86_64_PC64:
182     case ELF::R_X86_64_GOTPC64:
183       return ELF_x86_64_Edges::ELFX86RelocationKind::Delta64;
184     case ELF::R_X86_64_64:
185       return ELF_x86_64_Edges::ELFX86RelocationKind::Pointer64;
186     case ELF::R_X86_64_GOTPCREL:
187     case ELF::R_X86_64_GOTPCRELX:
188       return ELF_x86_64_Edges::ELFX86RelocationKind::PCRel32GOTLoad;
189     case ELF::R_X86_64_REX_GOTPCRELX:
190       return ELF_x86_64_Edges::ELFX86RelocationKind::PCRel32REXGOTLoad;
191     case ELF::R_X86_64_GOTPCREL64:
192       return ELF_x86_64_Edges::ELFX86RelocationKind::PCRel64GOT;
193     case ELF::R_X86_64_GOT64:
194       return ELF_x86_64_Edges::ELFX86RelocationKind::GOT64;
195     case ELF::R_X86_64_GOTOFF64:
196       return ELF_x86_64_Edges::ELFX86RelocationKind::GOTOFF64;
197     case ELF::R_X86_64_PLT32:
198       return ELF_x86_64_Edges::ELFX86RelocationKind::Branch32;
199     }
200     return make_error<JITLinkError>("Unsupported x86-64 relocation type " +
201                                     formatv("{0:d}: ", Type) +
202                                     getELFX86_64RelocName(Type));
203   }
204 
205   Error addRelocations() override {
206     LLVM_DEBUG(dbgs() << "Adding relocations\n");
207     // TODO a partern is forming of iterate some sections but only give me
208     // ones I am interested, i should abstract that concept some where
209     for (auto &SecRef : Sections) {
210       if (SecRef.sh_type != ELF::SHT_RELA && SecRef.sh_type != ELF::SHT_REL)
211         continue;
212       // TODO can the elf obj file do this for me?
213       if (SecRef.sh_type == ELF::SHT_REL)
214         return make_error<llvm::StringError>("Shouldn't have REL in x64",
215                                              llvm::inconvertibleErrorCode());
216 
217       auto RelSectName = Obj.getSectionName(SecRef);
218       if (!RelSectName)
219         return RelSectName.takeError();
220 
221       LLVM_DEBUG({
222         dbgs() << "Adding relocations from section " << *RelSectName << "\n";
223       });
224 
225       auto UpdateSection = Obj.getSection(SecRef.sh_info);
226       if (!UpdateSection)
227         return UpdateSection.takeError();
228 
229       auto UpdateSectionName = Obj.getSectionName(**UpdateSection);
230       if (!UpdateSectionName)
231         return UpdateSectionName.takeError();
232 
233       // Don't process relocations for debug sections.
234       if (isDwarfSection(*UpdateSectionName)) {
235         LLVM_DEBUG({
236           dbgs() << "  Target is dwarf section " << *UpdateSectionName
237                  << ". Skipping.\n";
238         });
239         continue;
240       } else
241         LLVM_DEBUG({
242           dbgs() << "  For target section " << *UpdateSectionName << "\n";
243         });
244 
245       auto JITSection = G->findSectionByName(*UpdateSectionName);
246       if (!JITSection)
247         return make_error<llvm::StringError>(
248             "Refencing a a section that wasn't added to graph" +
249                 *UpdateSectionName,
250             llvm::inconvertibleErrorCode());
251 
252       auto Relocations = Obj.relas(SecRef);
253       if (!Relocations)
254         return Relocations.takeError();
255 
256       for (const auto &Rela : *Relocations) {
257         auto Type = Rela.getType(false);
258 
259         LLVM_DEBUG({
260           dbgs() << "Relocation Type: " << Type << "\n"
261                  << "Name: " << Obj.getRelocationTypeName(Type) << "\n";
262         });
263         auto SymbolIndex = Rela.getSymbol(false);
264         auto Symbol = Obj.getRelocationSymbol(Rela, SymTabSec);
265         if (!Symbol)
266           return Symbol.takeError();
267 
268         auto BlockToFix = *(JITSection->blocks().begin());
269         auto *TargetSymbol = getGraphSymbol(SymbolIndex);
270 
271         if (!TargetSymbol) {
272           return make_error<llvm::StringError>(
273               "Could not find symbol at given index, did you add it to "
274               "JITSymbolTable? index: " +
275                   std::to_string(SymbolIndex) +
276                   ", shndx: " + std::to_string((*Symbol)->st_shndx) +
277                   " Size of table: " + std::to_string(GraphSymbols.size()),
278               llvm::inconvertibleErrorCode());
279         }
280         int64_t Addend = Rela.r_addend;
281         JITTargetAddress FixupAddress =
282             (*UpdateSection)->sh_addr + Rela.r_offset;
283 
284         LLVM_DEBUG({
285           dbgs() << "Processing relocation at "
286                  << format("0x%016" PRIx64, FixupAddress) << "\n";
287         });
288         auto ELFRelocKind = getRelocationKind(Type);
289         if (!ELFRelocKind)
290           return ELFRelocKind.takeError();
291 
292         Edge::Kind Kind = Edge::Invalid;
293         switch (*ELFRelocKind) {
294         case PCRel32:
295           Kind = x86_64::Delta32;
296           break;
297         case Delta64:
298           Kind = x86_64::Delta64;
299           break;
300         case Pointer64:
301           Kind = x86_64::Pointer64;
302           break;
303         case PCRel32GOTLoad: {
304           Kind = x86_64::RequestGOTAndTransformToPCRel32GOTLoadRelaxable;
305           Addend = 0;
306           break;
307         }
308         case PCRel32REXGOTLoad: {
309           Kind = x86_64::RequestGOTAndTransformToPCRel32GOTLoadREXRelaxable;
310           Addend = 0;
311           break;
312         }
313         case PCRel64GOT: {
314           Kind = x86_64::RequestGOTAndTransformToDelta64;
315           break;
316         }
317         case GOT64: {
318           Kind = x86_64::RequestGOTAndTransformToDelta64FromGOT;
319           break;
320         }
321         case GOTOFF64: {
322           Kind = x86_64::Delta64FromGOT;
323           break;
324         }
325         case Branch32: {
326           Kind = x86_64::BranchPCRel32;
327           Addend = 0;
328           break;
329         }
330         }
331 
332         LLVM_DEBUG({
333           Edge GE(Kind, FixupAddress - BlockToFix->getAddress(), *TargetSymbol,
334                   Addend);
335           printEdge(dbgs(), *BlockToFix, GE, getELFX86RelocationKindName(Kind));
336           dbgs() << "\n";
337         });
338         BlockToFix->addEdge(Kind, FixupAddress - BlockToFix->getAddress(),
339                             *TargetSymbol, Addend);
340       }
341     }
342     return Error::success();
343   }
344 
345 public:
346   ELFLinkGraphBuilder_x86_64(StringRef FileName,
347                              const object::ELFFile<object::ELF64LE> &Obj)
348       : ELFLinkGraphBuilder(Obj, Triple("x86_64-unknown-linux"), FileName,
349                             x86_64::getEdgeKindName) {}
350 };
351 
352 class ELFJITLinker_x86_64 : public JITLinker<ELFJITLinker_x86_64> {
353   friend class JITLinker<ELFJITLinker_x86_64>;
354 
355 public:
356   ELFJITLinker_x86_64(std::unique_ptr<JITLinkContext> Ctx,
357                       std::unique_ptr<LinkGraph> G,
358                       PassConfiguration PassConfig)
359       : JITLinker(std::move(Ctx), std::move(G), std::move(PassConfig)) {
360     getPassConfig().PostAllocationPasses.push_back(
361         [this](LinkGraph &G) { return getOrCreateGOTSymbol(G); });
362   }
363 
364 private:
365   Symbol *GOTSymbol = nullptr;
366 
367   Error getOrCreateGOTSymbol(LinkGraph &G) {
368     auto DefineExternalGOTSymbolIfPresent =
369         createDefineExternalSectionStartAndEndSymbolsPass(
370             [&](LinkGraph &LG, Symbol &Sym) -> SectionRangeSymbolDesc {
371               if (Sym.getName() == ELFGOTSymbolName)
372                 if (auto *GOTSection = G.findSectionByName(ELFGOTSectionName)) {
373                   GOTSymbol = &Sym;
374                   return {*GOTSection, true};
375                 }
376               return {};
377             });
378 
379     // Try to attach _GLOBAL_OFFSET_TABLE_ to the GOT if it's defined as an
380     // external.
381     if (auto Err = DefineExternalGOTSymbolIfPresent(G))
382       return Err;
383 
384     // If we succeeded then we're done.
385     if (GOTSymbol)
386       return Error::success();
387 
388     // Otherwise look for a GOT section: If it already has a start symbol we'll
389     // record it, otherwise we'll create our own.
390     // If there's a GOT section but we didn't find an external GOT symbol...
391     if (auto *GOTSection = G.findSectionByName(ELFGOTSectionName)) {
392 
393       // Check for an existing defined symbol.
394       for (auto *Sym : GOTSection->symbols())
395         if (Sym->getName() == ELFGOTSymbolName) {
396           GOTSymbol = Sym;
397           return Error::success();
398         }
399 
400       // If there's no defined symbol then create one.
401       SectionRange SR(*GOTSection);
402       if (SR.empty())
403         GOTSymbol = &G.addAbsoluteSymbol(ELFGOTSymbolName, 0, 0,
404                                          Linkage::Strong, Scope::Local, true);
405       else
406         GOTSymbol =
407             &G.addDefinedSymbol(*SR.getFirstBlock(), 0, ELFGOTSymbolName, 0,
408                                 Linkage::Strong, Scope::Local, false, true);
409     }
410 
411     return Error::success();
412   }
413 
414   Error applyFixup(LinkGraph &G, Block &B, const Edge &E) const {
415     return x86_64::applyFixup(G, B, E, GOTSymbol);
416   }
417 };
418 
419 Expected<std::unique_ptr<LinkGraph>>
420 createLinkGraphFromELFObject_x86_64(MemoryBufferRef ObjectBuffer) {
421   LLVM_DEBUG({
422     dbgs() << "Building jitlink graph for new input "
423            << ObjectBuffer.getBufferIdentifier() << "...\n";
424   });
425 
426   auto ELFObj = object::ObjectFile::createELFObjectFile(ObjectBuffer);
427   if (!ELFObj)
428     return ELFObj.takeError();
429 
430   auto &ELFObjFile = cast<object::ELFObjectFile<object::ELF64LE>>(**ELFObj);
431   return ELFLinkGraphBuilder_x86_64((*ELFObj)->getFileName(),
432                                     ELFObjFile.getELFFile())
433       .buildGraph();
434 }
435 
436 static SectionRangeSymbolDesc
437 identifyELFSectionStartAndEndSymbols(LinkGraph &G, Symbol &Sym) {
438   constexpr StringRef StartSymbolPrefix = "__start";
439   constexpr StringRef EndSymbolPrefix = "__end";
440 
441   auto SymName = Sym.getName();
442   if (SymName.startswith(StartSymbolPrefix)) {
443     if (auto *Sec =
444             G.findSectionByName(SymName.drop_front(StartSymbolPrefix.size())))
445       return {*Sec, true};
446   } else if (SymName.startswith(EndSymbolPrefix)) {
447     if (auto *Sec =
448             G.findSectionByName(SymName.drop_front(EndSymbolPrefix.size())))
449       return {*Sec, false};
450   }
451   return {};
452 }
453 
454 void link_ELF_x86_64(std::unique_ptr<LinkGraph> G,
455                      std::unique_ptr<JITLinkContext> Ctx) {
456   PassConfiguration Config;
457 
458   if (Ctx->shouldAddDefaultTargetPasses(G->getTargetTriple())) {
459 
460     Config.PrePrunePasses.push_back(EHFrameSplitter(".eh_frame"));
461     Config.PrePrunePasses.push_back(
462         EHFrameEdgeFixer(".eh_frame", x86_64::PointerSize, x86_64::Delta64,
463                          x86_64::Delta32, x86_64::NegDelta32));
464     Config.PrePrunePasses.push_back(EHFrameNullTerminator(".eh_frame"));
465 
466     // Construct a JITLinker and run the link function.
467     // Add a mark-live pass.
468     if (auto MarkLive = Ctx->getMarkLivePass(G->getTargetTriple()))
469       Config.PrePrunePasses.push_back(std::move(MarkLive));
470     else
471       Config.PrePrunePasses.push_back(markAllSymbolsLive);
472 
473     // Add an in-place GOT/Stubs pass.
474     Config.PostPrunePasses.push_back(
475         PerGraphGOTAndPLTStubsBuilder_ELF_x86_64::asPass);
476 
477     // Resolve any external section start / end symbols.
478     Config.PostAllocationPasses.push_back(
479         createDefineExternalSectionStartAndEndSymbolsPass(
480             identifyELFSectionStartAndEndSymbols));
481 
482     // Add GOT/Stubs optimizer pass.
483     Config.PreFixupPasses.push_back(x86_64::optimize_x86_64_GOTAndStubs);
484   }
485 
486   if (auto Err = Ctx->modifyPassConfig(*G, Config))
487     return Ctx->notifyFailed(std::move(Err));
488 
489   ELFJITLinker_x86_64::link(std::move(Ctx), std::move(G), std::move(Config));
490 }
491 const char *getELFX86RelocationKindName(Edge::Kind R) {
492   switch (R) {
493   case Branch32:
494     return "Branch32";
495   case Pointer64:
496     return "Pointer64";
497   case PCRel32:
498     return "PCRel32";
499   case PCRel32GOTLoad:
500     return "PCRel32GOTLoad";
501   case PCRel32REXGOTLoad:
502     return "PCRel32REXGOTLoad";
503   case PCRel64GOT:
504     return "PCRel64GOT";
505   case Delta64:
506     return "Delta64";
507   case GOT64:
508     return "GOT64";
509   case GOTOFF64:
510     return "GOTOFF64";
511   }
512   return getGenericEdgeKindName(static_cast<Edge::Kind>(R));
513 }
514 } // end namespace jitlink
515 } // end namespace llvm
516