1 //===------------- JITLink.cpp - Core Run-time JIT linker APIs ------------===//
2 //
3 //                     The LLVM Compiler Infrastructure
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #include "llvm/ExecutionEngine/JITLink/JITLink.h"
11 
12 #include "llvm/BinaryFormat/Magic.h"
13 #include "llvm/ExecutionEngine/JITLink/ELF.h"
14 #include "llvm/ExecutionEngine/JITLink/MachO.h"
15 #include "llvm/Support/Format.h"
16 #include "llvm/Support/ManagedStatic.h"
17 #include "llvm/Support/MemoryBuffer.h"
18 #include "llvm/Support/raw_ostream.h"
19 
20 using namespace llvm;
21 using namespace llvm::object;
22 
23 #define DEBUG_TYPE "jitlink"
24 
25 namespace {
26 
27 enum JITLinkErrorCode { GenericJITLinkError = 1 };
28 
29 // FIXME: This class is only here to support the transition to llvm::Error. It
30 // will be removed once this transition is complete. Clients should prefer to
31 // deal with the Error value directly, rather than converting to error_code.
32 class JITLinkerErrorCategory : public std::error_category {
33 public:
34   const char *name() const noexcept override { return "runtimedyld"; }
35 
36   std::string message(int Condition) const override {
37     switch (static_cast<JITLinkErrorCode>(Condition)) {
38     case GenericJITLinkError:
39       return "Generic JITLink error";
40     }
41     llvm_unreachable("Unrecognized JITLinkErrorCode");
42   }
43 };
44 
45 static ManagedStatic<JITLinkerErrorCategory> JITLinkerErrorCategory;
46 
47 } // namespace
48 
49 namespace llvm {
50 namespace jitlink {
51 
52 char JITLinkError::ID = 0;
53 
54 void JITLinkError::log(raw_ostream &OS) const { OS << ErrMsg; }
55 
56 std::error_code JITLinkError::convertToErrorCode() const {
57   return std::error_code(GenericJITLinkError, *JITLinkerErrorCategory);
58 }
59 
60 const char *getGenericEdgeKindName(Edge::Kind K) {
61   switch (K) {
62   case Edge::Invalid:
63     return "INVALID RELOCATION";
64   case Edge::KeepAlive:
65     return "Keep-Alive";
66   default:
67     return "<Unrecognized edge kind>";
68   }
69 }
70 
71 const char *getLinkageName(Linkage L) {
72   switch (L) {
73   case Linkage::Strong:
74     return "strong";
75   case Linkage::Weak:
76     return "weak";
77   }
78   llvm_unreachable("Unrecognized llvm.jitlink.Linkage enum");
79 }
80 
81 const char *getScopeName(Scope S) {
82   switch (S) {
83   case Scope::Default:
84     return "default";
85   case Scope::Hidden:
86     return "hidden";
87   case Scope::Local:
88     return "local";
89   }
90   llvm_unreachable("Unrecognized llvm.jitlink.Scope enum");
91 }
92 
93 raw_ostream &operator<<(raw_ostream &OS, const Block &B) {
94   return OS << formatv("{0:x16}", B.getAddress()) << " -- "
95             << formatv("{0:x8}", B.getAddress() + B.getSize()) << ": "
96             << "size = " << formatv("{0:x8}", B.getSize()) << ", "
97             << (B.isZeroFill() ? "zero-fill" : "content")
98             << ", align = " << B.getAlignment()
99             << ", align-ofs = " << B.getAlignmentOffset()
100             << ", section = " << B.getSection().getName();
101 }
102 
103 raw_ostream &operator<<(raw_ostream &OS, const Symbol &Sym) {
104   OS << formatv("{0:x16}", Sym.getAddress()) << " ("
105      << (Sym.isDefined() ? "block" : "addressable") << " + "
106      << formatv("{0:x8}", Sym.getOffset())
107      << "): size: " << formatv("{0:x8}", Sym.getSize())
108      << ", linkage: " << formatv("{0:6}", getLinkageName(Sym.getLinkage()))
109      << ", scope: " << formatv("{0:8}", getScopeName(Sym.getScope())) << ", "
110      << (Sym.isLive() ? "live" : "dead") << "  -   "
111      << (Sym.hasName() ? Sym.getName() : "<anonymous symbol>");
112   return OS;
113 }
114 
115 void printEdge(raw_ostream &OS, const Block &B, const Edge &E,
116                StringRef EdgeKindName) {
117   OS << "edge@" << formatv("{0:x16}", B.getAddress() + E.getOffset()) << ": "
118      << formatv("{0:x16}", B.getAddress()) << " + "
119      << formatv("{0:x}", E.getOffset()) << " -- " << EdgeKindName << " -> ";
120 
121   auto &TargetSym = E.getTarget();
122   if (TargetSym.hasName())
123     OS << TargetSym.getName();
124   else {
125     auto &TargetBlock = TargetSym.getBlock();
126     auto &TargetSec = TargetBlock.getSection();
127     JITTargetAddress SecAddress = ~JITTargetAddress(0);
128     for (auto *B : TargetSec.blocks())
129       if (B->getAddress() < SecAddress)
130         SecAddress = B->getAddress();
131 
132     JITTargetAddress SecDelta = TargetSym.getAddress() - SecAddress;
133     OS << formatv("{0:x16}", TargetSym.getAddress()) << " (section "
134        << TargetSec.getName();
135     if (SecDelta)
136       OS << " + " << formatv("{0:x}", SecDelta);
137     OS << " / block " << formatv("{0:x16}", TargetBlock.getAddress());
138     if (TargetSym.getOffset())
139       OS << " + " << formatv("{0:x}", TargetSym.getOffset());
140     OS << ")";
141   }
142 
143   if (E.getAddend() != 0)
144     OS << " + " << E.getAddend();
145 }
146 
147 Section::~Section() {
148   for (auto *Sym : Symbols)
149     Sym->~Symbol();
150   for (auto *B : Blocks)
151     B->~Block();
152 }
153 
154 Block &LinkGraph::splitBlock(Block &B, size_t SplitIndex,
155                              SplitBlockCache *Cache) {
156 
157   assert(SplitIndex > 0 && "splitBlock can not be called with SplitIndex == 0");
158 
159   // If the split point covers all of B then just return B.
160   if (SplitIndex == B.getSize())
161     return B;
162 
163   assert(SplitIndex < B.getSize() && "SplitIndex out of range");
164 
165   // Create the new block covering [ 0, SplitIndex ).
166   auto &NewBlock =
167       B.isZeroFill()
168           ? createZeroFillBlock(B.getSection(), SplitIndex, B.getAddress(),
169                                 B.getAlignment(), B.getAlignmentOffset())
170           : createContentBlock(
171                 B.getSection(), B.getContent().slice(0, SplitIndex),
172                 B.getAddress(), B.getAlignment(), B.getAlignmentOffset());
173 
174   // Modify B to cover [ SplitIndex, B.size() ).
175   B.setAddress(B.getAddress() + SplitIndex);
176   B.setContent(B.getContent().slice(SplitIndex));
177   B.setAlignmentOffset((B.getAlignmentOffset() + SplitIndex) %
178                        B.getAlignment());
179 
180   // Handle edge transfer/update.
181   {
182     // Copy edges to NewBlock (recording their iterators so that we can remove
183     // them from B), and update of Edges remaining on B.
184     std::vector<Block::edge_iterator> EdgesToRemove;
185     for (auto I = B.edges().begin(); I != B.edges().end();) {
186       if (I->getOffset() < SplitIndex) {
187         NewBlock.addEdge(*I);
188         I = B.removeEdge(I);
189       } else {
190         I->setOffset(I->getOffset() - SplitIndex);
191         ++I;
192       }
193     }
194   }
195 
196   // Handle symbol transfer/update.
197   {
198     // Initialize the symbols cache if necessary.
199     SplitBlockCache LocalBlockSymbolsCache;
200     if (!Cache)
201       Cache = &LocalBlockSymbolsCache;
202     if (*Cache == None) {
203       *Cache = SplitBlockCache::value_type();
204       for (auto *Sym : B.getSection().symbols())
205         if (&Sym->getBlock() == &B)
206           (*Cache)->push_back(Sym);
207 
208       llvm::sort(**Cache, [](const Symbol *LHS, const Symbol *RHS) {
209         return LHS->getOffset() > RHS->getOffset();
210       });
211     }
212     auto &BlockSymbols = **Cache;
213 
214     // Transfer all symbols with offset less than SplitIndex to NewBlock.
215     while (!BlockSymbols.empty() &&
216            BlockSymbols.back()->getOffset() < SplitIndex) {
217       BlockSymbols.back()->setBlock(NewBlock);
218       BlockSymbols.pop_back();
219     }
220 
221     // Update offsets for all remaining symbols in B.
222     for (auto *Sym : BlockSymbols)
223       Sym->setOffset(Sym->getOffset() - SplitIndex);
224   }
225 
226   return NewBlock;
227 }
228 
229 void LinkGraph::dump(raw_ostream &OS) {
230   DenseMap<Block *, std::vector<Symbol *>> BlockSymbols;
231 
232   // Map from blocks to the symbols pointing at them.
233   for (auto *Sym : defined_symbols())
234     BlockSymbols[&Sym->getBlock()].push_back(Sym);
235 
236   // For each block, sort its symbols by something approximating
237   // relevance.
238   for (auto &KV : BlockSymbols)
239     llvm::sort(KV.second, [](const Symbol *LHS, const Symbol *RHS) {
240       if (LHS->getOffset() != RHS->getOffset())
241         return LHS->getOffset() < RHS->getOffset();
242       if (LHS->getLinkage() != RHS->getLinkage())
243         return LHS->getLinkage() < RHS->getLinkage();
244       if (LHS->getScope() != RHS->getScope())
245         return LHS->getScope() < RHS->getScope();
246       if (LHS->hasName()) {
247         if (!RHS->hasName())
248           return true;
249         return LHS->getName() < RHS->getName();
250       }
251       return false;
252     });
253 
254   for (auto &Sec : sections()) {
255     OS << "section " << Sec.getName() << ":\n\n";
256 
257     std::vector<Block *> SortedBlocks;
258     llvm::copy(Sec.blocks(), std::back_inserter(SortedBlocks));
259     llvm::sort(SortedBlocks, [](const Block *LHS, const Block *RHS) {
260       return LHS->getAddress() < RHS->getAddress();
261     });
262 
263     for (auto *B : SortedBlocks) {
264       OS << "  block " << formatv("{0:x16}", B->getAddress())
265          << " size = " << formatv("{0:x8}", B->getSize())
266          << ", align = " << B->getAlignment()
267          << ", alignment-offset = " << B->getAlignmentOffset();
268       if (B->isZeroFill())
269         OS << ", zero-fill";
270       OS << "\n";
271 
272       auto BlockSymsI = BlockSymbols.find(B);
273       if (BlockSymsI != BlockSymbols.end()) {
274         OS << "    symbols:\n";
275         auto &Syms = BlockSymsI->second;
276         for (auto *Sym : Syms)
277           OS << "      " << *Sym << "\n";
278       } else
279         OS << "    no symbols\n";
280 
281       if (!B->edges_empty()) {
282         OS << "    edges:\n";
283         std::vector<Edge> SortedEdges;
284         llvm::copy(B->edges(), std::back_inserter(SortedEdges));
285         llvm::sort(SortedEdges, [](const Edge &LHS, const Edge &RHS) {
286           return LHS.getOffset() < RHS.getOffset();
287         });
288         for (auto &E : SortedEdges) {
289           OS << "      " << formatv("{0:x16}", B->getFixupAddress(E))
290              << " (block + " << formatv("{0:x8}", E.getOffset())
291              << "), addend = ";
292           if (E.getAddend() >= 0)
293             OS << formatv("+{0:x8}", E.getAddend());
294           else
295             OS << formatv("-{0:x8}", -E.getAddend());
296           OS << ", kind = " << getEdgeKindName(E.getKind()) << ", target = ";
297           if (E.getTarget().hasName())
298             OS << E.getTarget().getName();
299           else
300             OS << "addressable@"
301                << formatv("{0:x16}", E.getTarget().getAddress()) << "+"
302                << formatv("{0:x8}", E.getTarget().getOffset());
303           OS << "\n";
304         }
305       } else
306         OS << "    no edges\n";
307       OS << "\n";
308     }
309   }
310 
311   OS << "Absolute symbols:\n";
312   if (!llvm::empty(absolute_symbols())) {
313     for (auto *Sym : absolute_symbols())
314       OS << "  " << format("0x%016" PRIx64, Sym->getAddress()) << ": " << *Sym
315          << "\n";
316   } else
317     OS << "  none\n";
318 
319   OS << "\nExternal symbols:\n";
320   if (!llvm::empty(external_symbols())) {
321     for (auto *Sym : external_symbols())
322       OS << "  " << format("0x%016" PRIx64, Sym->getAddress()) << ": " << *Sym
323          << "\n";
324   } else
325     OS << "  none\n";
326 }
327 
328 raw_ostream &operator<<(raw_ostream &OS, const SymbolLookupFlags &LF) {
329   switch (LF) {
330   case SymbolLookupFlags::RequiredSymbol:
331     return OS << "RequiredSymbol";
332   case SymbolLookupFlags::WeaklyReferencedSymbol:
333     return OS << "WeaklyReferencedSymbol";
334   }
335   llvm_unreachable("Unrecognized lookup flags");
336 }
337 
338 void JITLinkAsyncLookupContinuation::anchor() {}
339 
340 JITLinkContext::~JITLinkContext() {}
341 
342 bool JITLinkContext::shouldAddDefaultTargetPasses(const Triple &TT) const {
343   return true;
344 }
345 
346 LinkGraphPassFunction JITLinkContext::getMarkLivePass(const Triple &TT) const {
347   return LinkGraphPassFunction();
348 }
349 
350 Error JITLinkContext::modifyPassConfig(LinkGraph &G,
351                                        PassConfiguration &Config) {
352   return Error::success();
353 }
354 
355 Error markAllSymbolsLive(LinkGraph &G) {
356   for (auto *Sym : G.defined_symbols())
357     Sym->setLive(true);
358   return Error::success();
359 }
360 
361 Error makeTargetOutOfRangeError(const LinkGraph &G, const Block &B,
362                                 const Edge &E) {
363   std::string ErrMsg;
364   {
365     raw_string_ostream ErrStream(ErrMsg);
366     Section &Sec = B.getSection();
367     ErrStream << "In graph " << G.getName() << ", section " << Sec.getName()
368               << ": relocation target ";
369     if (E.getTarget().hasName())
370       ErrStream << "\"" << E.getTarget().getName() << "\" ";
371     ErrStream << "at address " << formatv("{0:x}", E.getTarget().getAddress());
372     ErrStream << " is out of range of " << G.getEdgeKindName(E.getKind())
373               << " fixup at " << formatv("{0:x}", B.getFixupAddress(E)) << " (";
374 
375     Symbol *BestSymbolForBlock = nullptr;
376     for (auto *Sym : Sec.symbols())
377       if (&Sym->getBlock() == &B && Sym->hasName() && Sym->getOffset() == 0 &&
378           (!BestSymbolForBlock ||
379            Sym->getScope() < BestSymbolForBlock->getScope() ||
380            Sym->getLinkage() < BestSymbolForBlock->getLinkage()))
381         BestSymbolForBlock = Sym;
382 
383     if (BestSymbolForBlock)
384       ErrStream << BestSymbolForBlock->getName() << ", ";
385     else
386       ErrStream << "<anonymous block> @ ";
387 
388     ErrStream << formatv("{0:x}", B.getAddress()) << " + "
389               << formatv("{0:x}", E.getOffset()) << ")";
390   }
391   return make_error<JITLinkError>(std::move(ErrMsg));
392 }
393 
394 Expected<std::unique_ptr<LinkGraph>>
395 createLinkGraphFromObject(MemoryBufferRef ObjectBuffer) {
396   auto Magic = identify_magic(ObjectBuffer.getBuffer());
397   switch (Magic) {
398   case file_magic::macho_object:
399     return createLinkGraphFromMachOObject(ObjectBuffer);
400   case file_magic::elf_relocatable:
401     return createLinkGraphFromELFObject(ObjectBuffer);
402   default:
403     return make_error<JITLinkError>("Unsupported file format");
404   };
405 }
406 
407 void link(std::unique_ptr<LinkGraph> G, std::unique_ptr<JITLinkContext> Ctx) {
408   switch (G->getTargetTriple().getObjectFormat()) {
409   case Triple::MachO:
410     return link_MachO(std::move(G), std::move(Ctx));
411   case Triple::ELF:
412     return link_ELF(std::move(G), std::move(Ctx));
413   default:
414     Ctx->notifyFailed(make_error<JITLinkError>("Unsupported object format"));
415   };
416 }
417 
418 } // end namespace jitlink
419 } // end namespace llvm
420