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/TableManager.h"
16 #include "llvm/ExecutionEngine/JITLink/x86_64.h"
17 #include "llvm/Object/ELFObjectFile.h"
18 #include "llvm/Support/Endian.h"
19 
20 #include "DefineExternalSectionStartAndEndSymbols.h"
21 #include "EHFrameSupportImpl.h"
22 #include "ELFLinkGraphBuilder.h"
23 #include "JITLinkGeneric.h"
24 #include "PerGraphGOTAndPLTStubsBuilder.h"
25 
26 #define DEBUG_TYPE "jitlink"
27 
28 using namespace llvm;
29 using namespace llvm::jitlink;
30 using namespace llvm::jitlink::ELF_x86_64_Edges;
31 
32 namespace {
33 
34 constexpr StringRef ELFGOTSectionName = "$__GOT";
35 constexpr StringRef ELFGOTSymbolName = "_GLOBAL_OFFSET_TABLE_";
36 constexpr StringRef ELFTLSInfoSectionName = "$__TLSINFO";
37 
38 class GOTTableManager_ELF_x86_64
39     : public TableManager<GOTTableManager_ELF_x86_64> {
40 public:
41   static const uint8_t NullGOTEntryContent[8];
42 
43   // Nice name for table
44   StringRef getTableName() { return "GOT"; }
45 
46   bool visitEdge(LinkGraph &G, Block *B, Edge &E) {
47     Edge::Kind KindToSet = Edge::Invalid;
48     switch (E.getKind()) {
49     case x86_64::Delta64FromGOT: {
50       // we need to make sure that the GOT section exists, but don't otherwise
51       // need to fix up this edge
52       getGOTSection(G);
53       return false;
54     }
55     case x86_64::RequestGOTAndTransformToPCRel32GOTLoadREXRelaxable:
56       KindToSet = x86_64::PCRel32GOTLoadREXRelaxable;
57       break;
58     case x86_64::RequestGOTAndTransformToPCRel32GOTLoadRelaxable:
59       KindToSet = x86_64::PCRel32GOTLoadRelaxable;
60       break;
61     case x86_64::RequestGOTAndTransformToDelta64:
62       KindToSet = x86_64::Delta64;
63       break;
64     case x86_64::RequestGOTAndTransformToDelta64FromGOT:
65       KindToSet = x86_64::Delta64FromGOT;
66       break;
67     case x86_64::RequestGOTAndTransformToDelta32:
68       KindToSet = x86_64::Delta32;
69       break;
70     default:
71       return false;
72     }
73     assert(KindToSet != Edge::Invalid &&
74            "Fell through switch, but no new kind to set");
75     LLVM_DEBUG({
76       dbgs() << "  Fixing " << G.getEdgeKindName(E.getKind()) << " edge at "
77              << formatv("{0:x}", B->getFixupAddress(E)) << " ("
78              << formatv("{0:x}", B->getAddress()) << " + "
79              << formatv("{0:x}", E.getOffset()) << ")\n";
80     });
81     E.setKind(KindToSet);
82     E.setTarget(getEntryForTarget(G, E.getTarget()));
83     return true;
84   }
85 
86   Symbol &createEntry(LinkGraph &G, Symbol &Target) {
87     auto &GOTEntryBlock = G.createContentBlock(
88         getGOTSection(G), getGOTEntryBlockContent(), 0, 8, 0);
89     GOTEntryBlock.addEdge(x86_64::Pointer64, 0, Target, 0);
90     return G.addAnonymousSymbol(GOTEntryBlock, 0, 8, false, false);
91   }
92 
93 private:
94   Section &getGOTSection(LinkGraph &G) {
95     if (!GOTSection)
96       GOTSection = &G.createSection(ELFGOTSectionName, MemProt::Read);
97     return *GOTSection;
98   }
99   ArrayRef<char> getGOTEntryBlockContent() const {
100     return {reinterpret_cast<const char *>(NullGOTEntryContent),
101             sizeof(NullGOTEntryContent)};
102   }
103   Section *GOTSection = nullptr;
104 };
105 const uint8_t GOTTableManager_ELF_x86_64::NullGOTEntryContent[8] = {
106     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00};
107 
108 class PLTTableManager_ELF_x86_64
109     : public TableManager<PLTTableManager_ELF_x86_64> {
110 public:
111   PLTTableManager_ELF_x86_64(GOTTableManager_ELF_x86_64 &GOTTable)
112       : GOTTable(GOTTable) {}
113 
114   StringRef getTableName() { return "PLT"; }
115 
116   static const uint8_t StubContent[6];
117   bool visitEdge(LinkGraph &G, Block *B, Edge &E) {
118     if (E.getKind() == x86_64::BranchPCRel32 && !E.getTarget().isDefined()) {
119       LLVM_DEBUG({
120         dbgs() << "  Fixing " << G.getEdgeKindName(E.getKind()) << " edge at "
121                << formatv("{0:x}", B->getFixupAddress(E)) << " ("
122                << formatv("{0:x}", B->getAddress()) << " + "
123                << formatv("{0:x}", E.getOffset()) << ")\n";
124       });
125       // Set the edge kind to Branch32ToPtrJumpStubBypassable to enable it to
126       // be optimized when the target is in-range.
127       E.setKind(x86_64::BranchPCRel32ToPtrJumpStubBypassable);
128       E.setTarget(getEntryForTarget(G, E.getTarget()));
129       return true;
130     }
131     return false;
132   }
133 
134   Symbol &createEntry(LinkGraph &G, Symbol &Target) {
135     auto &StubContentBlock = G.createContentBlock(
136         getStubsSection(G), getStubBlockContent(), 0, 1, 0);
137     // Re-use GOT entries for stub targets.
138     auto &GOTEntrySymbol = GOTTable.getEntryForTarget(G, Target);
139     StubContentBlock.addEdge(x86_64::Delta32, 2, GOTEntrySymbol, -4);
140     return G.addAnonymousSymbol(StubContentBlock, 0, 6, true, false);
141   }
142 
143 private:
144   Section &getStubsSection(LinkGraph &G) {
145     if (!StubsSection)
146       StubsSection =
147           &G.createSection("$__STUBS", MemProt::Read | MemProt::Exec);
148     return *StubsSection;
149   }
150 
151   ArrayRef<char> getStubBlockContent() {
152     return {reinterpret_cast<const char *>(StubContent), sizeof(StubContent)};
153   }
154 
155   Section *StubsSection = nullptr;
156   GOTTableManager_ELF_x86_64 &GOTTable;
157 };
158 const uint8_t PLTTableManager_ELF_x86_64::StubContent[6] = {0xFF, 0x25, 0x00,
159                                                             0x00, 0x00, 0x00};
160 
161 class TLSInfoTableManager_ELF_x86_64
162     : public TableManager<TLSInfoTableManager_ELF_x86_64> {
163 public:
164   static const uint8_t TLSInfoEntryContent[16];
165 
166   StringRef getTableName() { return "TLSInfo"; }
167 
168   bool visitEdge(LinkGraph &G, Block *B, Edge &E) {
169     if (E.getKind() == x86_64::RequestTLSDescInGOTAndTransformToDelta32) {
170       LLVM_DEBUG({
171         dbgs() << "  Fixing " << G.getEdgeKindName(E.getKind()) << " edge at "
172                << formatv("{0:x}", B->getFixupAddress(E)) << " ("
173                << formatv("{0:x}", B->getAddress()) << " + "
174                << formatv("{0:x}", E.getOffset()) << ")\n";
175       });
176       E.setKind(x86_64::Delta32);
177       E.setTarget(getEntryForTarget(G, E.getTarget()));
178       return true;
179     }
180     return false;
181   }
182 
183   Symbol &createEntry(LinkGraph &G, Symbol &Target) {
184     // the TLS Info entry's key value will be written by the fixTLVSectionByName
185     // pass, so create mutable content.
186     auto &TLSInfoEntry = G.createMutableContentBlock(
187         getTLSInfoSection(G), G.allocateContent(getTLSInfoEntryContent()), 0, 8,
188         0);
189     TLSInfoEntry.addEdge(x86_64::Pointer64, 8, Target, 0);
190     return G.addAnonymousSymbol(TLSInfoEntry, 0, 16, false, false);
191   }
192 
193 private:
194   Section &getTLSInfoSection(LinkGraph &G) {
195     if (!TLSInfoTable)
196       TLSInfoTable = &G.createSection(ELFTLSInfoSectionName, MemProt::Read);
197     return *TLSInfoTable;
198   }
199 
200   ArrayRef<char> getTLSInfoEntryContent() const {
201     return {reinterpret_cast<const char *>(TLSInfoEntryContent),
202             sizeof(TLSInfoEntryContent)};
203   }
204 
205   Section *TLSInfoTable = nullptr;
206 };
207 
208 const uint8_t TLSInfoTableManager_ELF_x86_64::TLSInfoEntryContent[16] = {
209     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, /*pthread key */
210     0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00  /*data address*/
211 };
212 
213 Error buildTables_ELF_x86_64(LinkGraph &G) {
214   LLVM_DEBUG(dbgs() << "Visiting edges in graph:\n");
215 
216   GOTTableManager_ELF_x86_64 GOT;
217   PLTTableManager_ELF_x86_64 PLT(GOT);
218   TLSInfoTableManager_ELF_x86_64 TLSInfo;
219   visitExistingEdges(G, GOT, PLT, TLSInfo);
220   return Error::success();
221 }
222 } // namespace
223 
224 static const char *getELFX86_64RelocName(uint32_t Type) {
225   switch (Type) {
226 #define ELF_RELOC(Name, Number)                                                \
227   case Number:                                                                 \
228     return #Name;
229 #include "llvm/BinaryFormat/ELFRelocs/x86_64.def"
230 #undef ELF_RELOC
231   }
232   return "Unrecognized ELF/x86-64 relocation type";
233 }
234 
235 namespace llvm {
236 namespace jitlink {
237 
238 // This should become a template as the ELFFile is so a lot of this could become
239 // generic
240 class ELFLinkGraphBuilder_x86_64 : public ELFLinkGraphBuilder<object::ELF64LE> {
241 private:
242   using ELFT = object::ELF64LE;
243 
244   static Expected<ELF_x86_64_Edges::ELFX86RelocationKind>
245   getRelocationKind(const uint32_t Type) {
246     switch (Type) {
247     case ELF::R_X86_64_32S:
248       return ELF_x86_64_Edges::ELFX86RelocationKind::Pointer32Signed;
249     case ELF::R_X86_64_PC32:
250       return ELF_x86_64_Edges::ELFX86RelocationKind::PCRel32;
251     case ELF::R_X86_64_PC64:
252     case ELF::R_X86_64_GOTPC64:
253       return ELF_x86_64_Edges::ELFX86RelocationKind::Delta64;
254     case ELF::R_X86_64_64:
255       return ELF_x86_64_Edges::ELFX86RelocationKind::Pointer64;
256     case ELF::R_X86_64_GOTPCREL:
257       return ELF_x86_64_Edges::ELFX86RelocationKind::PCRel32GOTLoad;
258     case ELF::R_X86_64_GOTPCRELX:
259       return ELF_x86_64_Edges::ELFX86RelocationKind::PCRel32GOTLoadRelaxable;
260     case ELF::R_X86_64_REX_GOTPCRELX:
261       return ELF_x86_64_Edges::ELFX86RelocationKind::PCRel32REXGOTLoadRelaxable;
262     case ELF::R_X86_64_GOTPCREL64:
263       return ELF_x86_64_Edges::ELFX86RelocationKind::PCRel64GOT;
264     case ELF::R_X86_64_GOT64:
265       return ELF_x86_64_Edges::ELFX86RelocationKind::GOT64;
266     case ELF::R_X86_64_GOTOFF64:
267       return ELF_x86_64_Edges::ELFX86RelocationKind::GOTOFF64;
268     case ELF::R_X86_64_PLT32:
269       return ELF_x86_64_Edges::ELFX86RelocationKind::Branch32;
270     case ELF::R_X86_64_TLSGD:
271       return ELF_x86_64_Edges::ELFX86RelocationKind::PCRel32TLV;
272     }
273     return make_error<JITLinkError>("Unsupported x86-64 relocation type " +
274                                     formatv("{0:d}: ", Type) +
275                                     getELFX86_64RelocName(Type));
276   }
277 
278   Error addRelocations() override {
279     LLVM_DEBUG(dbgs() << "Processing relocations:\n");
280 
281     using Base = ELFLinkGraphBuilder<ELFT>;
282     using Self = ELFLinkGraphBuilder_x86_64;
283     for (const auto &RelSect : Base::Sections) {
284       // Sanity check the section to read relocation entries from.
285       if (RelSect.sh_type == ELF::SHT_REL)
286         return make_error<StringError>(
287             "No SHT_REL in valid x64 ELF object files",
288             inconvertibleErrorCode());
289 
290       if (Error Err = Base::forEachRelocation(RelSect, this,
291                                               &Self::addSingleRelocation))
292         return Err;
293     }
294 
295     return Error::success();
296   }
297 
298   Error addSingleRelocation(const typename ELFT::Rela &Rel,
299                             const typename ELFT::Shdr &FixupSection,
300                             Section &GraphSection) {
301     using Base = ELFLinkGraphBuilder<ELFT>;
302 
303     uint32_t SymbolIndex = Rel.getSymbol(false);
304     auto ObjSymbol = Base::Obj.getRelocationSymbol(Rel, Base::SymTabSec);
305     if (!ObjSymbol)
306       return ObjSymbol.takeError();
307 
308     Symbol *GraphSymbol = Base::getGraphSymbol(SymbolIndex);
309     if (!GraphSymbol)
310       return make_error<StringError>(
311           formatv("Could not find symbol at given index, did you add it to "
312                   "JITSymbolTable? index: {0}, shndx: {1} Size of table: {2}",
313                   SymbolIndex, (*ObjSymbol)->st_shndx,
314                   Base::GraphSymbols.size()),
315           inconvertibleErrorCode());
316 
317     // Sanity check the relocation kind.
318     auto ELFRelocKind = getRelocationKind(Rel.getType(false));
319     if (!ELFRelocKind)
320       return ELFRelocKind.takeError();
321 
322     int64_t Addend = Rel.r_addend;
323     Edge::Kind Kind = Edge::Invalid;
324     switch (*ELFRelocKind) {
325     case PCRel32:
326       Kind = x86_64::Delta32;
327       break;
328     case Delta64:
329       Kind = x86_64::Delta64;
330       break;
331     case Pointer32Signed:
332       Kind = x86_64::Pointer32Signed;
333       break;
334     case Pointer64:
335       Kind = x86_64::Pointer64;
336       break;
337     case PCRel32GOTLoad: {
338       Kind = x86_64::RequestGOTAndTransformToDelta32;
339       break;
340     }
341     case PCRel32REXGOTLoadRelaxable: {
342       Kind = x86_64::RequestGOTAndTransformToPCRel32GOTLoadREXRelaxable;
343       Addend = 0;
344       break;
345     }
346     case PCRel32TLV: {
347       Kind = x86_64::RequestTLSDescInGOTAndTransformToDelta32;
348       break;
349     }
350     case PCRel32GOTLoadRelaxable: {
351       Kind = x86_64::RequestGOTAndTransformToPCRel32GOTLoadRelaxable;
352       Addend = 0;
353       break;
354     }
355     case PCRel64GOT: {
356       Kind = x86_64::RequestGOTAndTransformToDelta64;
357       break;
358     }
359     case GOT64: {
360       Kind = x86_64::RequestGOTAndTransformToDelta64FromGOT;
361       break;
362     }
363     case GOTOFF64: {
364       Kind = x86_64::Delta64FromGOT;
365       break;
366     }
367     case Branch32: {
368       Kind = x86_64::BranchPCRel32;
369       Addend = 0;
370       break;
371     }
372     }
373 
374     Block *BlockToFix = *(GraphSection.blocks().begin());
375     JITTargetAddress FixupAddress = FixupSection.sh_addr + Rel.r_offset;
376     Edge::OffsetT Offset = FixupAddress - BlockToFix->getAddress();
377     Edge GE(Kind, Offset, *GraphSymbol, Addend);
378     LLVM_DEBUG({
379       dbgs() << "    ";
380       printEdge(dbgs(), *BlockToFix, GE, getELFX86RelocationKindName(Kind));
381       dbgs() << "\n";
382     });
383 
384     BlockToFix->addEdge(std::move(GE));
385     return Error::success();
386   }
387 
388 public:
389   ELFLinkGraphBuilder_x86_64(StringRef FileName,
390                              const object::ELFFile<object::ELF64LE> &Obj)
391       : ELFLinkGraphBuilder(Obj, Triple("x86_64-unknown-linux"), FileName,
392                             x86_64::getEdgeKindName) {}
393 };
394 
395 class ELFJITLinker_x86_64 : public JITLinker<ELFJITLinker_x86_64> {
396   friend class JITLinker<ELFJITLinker_x86_64>;
397 
398 public:
399   ELFJITLinker_x86_64(std::unique_ptr<JITLinkContext> Ctx,
400                       std::unique_ptr<LinkGraph> G,
401                       PassConfiguration PassConfig)
402       : JITLinker(std::move(Ctx), std::move(G), std::move(PassConfig)) {
403     getPassConfig().PostAllocationPasses.push_back(
404         [this](LinkGraph &G) { return getOrCreateGOTSymbol(G); });
405   }
406 
407 private:
408   Symbol *GOTSymbol = nullptr;
409 
410   Error getOrCreateGOTSymbol(LinkGraph &G) {
411     auto DefineExternalGOTSymbolIfPresent =
412         createDefineExternalSectionStartAndEndSymbolsPass(
413             [&](LinkGraph &LG, Symbol &Sym) -> SectionRangeSymbolDesc {
414               if (Sym.getName() == ELFGOTSymbolName)
415                 if (auto *GOTSection = G.findSectionByName(ELFGOTSectionName)) {
416                   GOTSymbol = &Sym;
417                   return {*GOTSection, true};
418                 }
419               return {};
420             });
421 
422     // Try to attach _GLOBAL_OFFSET_TABLE_ to the GOT if it's defined as an
423     // external.
424     if (auto Err = DefineExternalGOTSymbolIfPresent(G))
425       return Err;
426 
427     // If we succeeded then we're done.
428     if (GOTSymbol)
429       return Error::success();
430 
431     // Otherwise look for a GOT section: If it already has a start symbol we'll
432     // record it, otherwise we'll create our own.
433     // If there's a GOT section but we didn't find an external GOT symbol...
434     if (auto *GOTSection = G.findSectionByName(ELFGOTSectionName)) {
435 
436       // Check for an existing defined symbol.
437       for (auto *Sym : GOTSection->symbols())
438         if (Sym->getName() == ELFGOTSymbolName) {
439           GOTSymbol = Sym;
440           return Error::success();
441         }
442 
443       // If there's no defined symbol then create one.
444       SectionRange SR(*GOTSection);
445       if (SR.empty())
446         GOTSymbol = &G.addAbsoluteSymbol(ELFGOTSymbolName, 0, 0,
447                                          Linkage::Strong, Scope::Local, true);
448       else
449         GOTSymbol =
450             &G.addDefinedSymbol(*SR.getFirstBlock(), 0, ELFGOTSymbolName, 0,
451                                 Linkage::Strong, Scope::Local, false, true);
452     }
453 
454     return Error::success();
455   }
456 
457   Error applyFixup(LinkGraph &G, Block &B, const Edge &E) const {
458     return x86_64::applyFixup(G, B, E, GOTSymbol);
459   }
460 };
461 
462 Expected<std::unique_ptr<LinkGraph>>
463 createLinkGraphFromELFObject_x86_64(MemoryBufferRef ObjectBuffer) {
464   LLVM_DEBUG({
465     dbgs() << "Building jitlink graph for new input "
466            << ObjectBuffer.getBufferIdentifier() << "...\n";
467   });
468 
469   auto ELFObj = object::ObjectFile::createELFObjectFile(ObjectBuffer);
470   if (!ELFObj)
471     return ELFObj.takeError();
472 
473   auto &ELFObjFile = cast<object::ELFObjectFile<object::ELF64LE>>(**ELFObj);
474   return ELFLinkGraphBuilder_x86_64((*ELFObj)->getFileName(),
475                                     ELFObjFile.getELFFile())
476       .buildGraph();
477 }
478 
479 static SectionRangeSymbolDesc
480 identifyELFSectionStartAndEndSymbols(LinkGraph &G, Symbol &Sym) {
481   constexpr StringRef StartSymbolPrefix = "__start";
482   constexpr StringRef EndSymbolPrefix = "__end";
483 
484   auto SymName = Sym.getName();
485   if (SymName.startswith(StartSymbolPrefix)) {
486     if (auto *Sec =
487             G.findSectionByName(SymName.drop_front(StartSymbolPrefix.size())))
488       return {*Sec, true};
489   } else if (SymName.startswith(EndSymbolPrefix)) {
490     if (auto *Sec =
491             G.findSectionByName(SymName.drop_front(EndSymbolPrefix.size())))
492       return {*Sec, false};
493   }
494   return {};
495 }
496 
497 void link_ELF_x86_64(std::unique_ptr<LinkGraph> G,
498                      std::unique_ptr<JITLinkContext> Ctx) {
499   PassConfiguration Config;
500 
501   if (Ctx->shouldAddDefaultTargetPasses(G->getTargetTriple())) {
502 
503     Config.PrePrunePasses.push_back(EHFrameSplitter(".eh_frame"));
504     Config.PrePrunePasses.push_back(
505         EHFrameEdgeFixer(".eh_frame", x86_64::PointerSize, x86_64::Delta64,
506                          x86_64::Delta32, x86_64::NegDelta32));
507     Config.PrePrunePasses.push_back(EHFrameNullTerminator(".eh_frame"));
508 
509     // Construct a JITLinker and run the link function.
510     // Add a mark-live pass.
511     if (auto MarkLive = Ctx->getMarkLivePass(G->getTargetTriple()))
512       Config.PrePrunePasses.push_back(std::move(MarkLive));
513     else
514       Config.PrePrunePasses.push_back(markAllSymbolsLive);
515 
516     // Add an in-place GOT/Stubs/TLSInfoEntry build pass.
517     Config.PostPrunePasses.push_back(buildTables_ELF_x86_64);
518 
519     // Resolve any external section start / end symbols.
520     Config.PostAllocationPasses.push_back(
521         createDefineExternalSectionStartAndEndSymbolsPass(
522             identifyELFSectionStartAndEndSymbols));
523 
524     // Add GOT/Stubs optimizer pass.
525     Config.PreFixupPasses.push_back(x86_64::optimize_x86_64_GOTAndStubs);
526   }
527 
528   if (auto Err = Ctx->modifyPassConfig(*G, Config))
529     return Ctx->notifyFailed(std::move(Err));
530 
531   ELFJITLinker_x86_64::link(std::move(Ctx), std::move(G), std::move(Config));
532 }
533 const char *getELFX86RelocationKindName(Edge::Kind R) {
534   switch (R) {
535   case Branch32:
536     return "Branch32";
537   case Pointer32Signed:
538     return "Pointer32Signed";
539   case Pointer64:
540     return "Pointer64";
541   case PCRel32:
542     return "PCRel32";
543   case PCRel32GOTLoad:
544     return "PCRel32GOTLoad";
545   case PCRel32GOTLoadRelaxable:
546     return "PCRel32GOTLoadRelaxable";
547   case PCRel32REXGOTLoadRelaxable:
548     return "PCRel32REXGOTLoad";
549   case PCRel64GOT:
550     return "PCRel64GOT";
551   case Delta64:
552     return "Delta64";
553   case GOT64:
554     return "GOT64";
555   case GOTOFF64:
556     return "GOTOFF64";
557   }
558   return getGenericEdgeKindName(static_cast<Edge::Kind>(R));
559 }
560 } // end namespace jitlink
561 } // end namespace llvm
562