1 //===--------- JITLinkGeneric.cpp - Generic JIT linker utilities ----------===//
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 // Generic JITLinker utility class.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #include "JITLinkGeneric.h"
14 
15 #include "llvm/Support/BinaryStreamReader.h"
16 #include "llvm/Support/MemoryBuffer.h"
17 
18 #define DEBUG_TYPE "jitlink"
19 
20 namespace llvm {
21 namespace jitlink {
22 
23 JITLinkerBase::~JITLinkerBase() {}
24 
25 void JITLinkerBase::linkPhase1(std::unique_ptr<JITLinkerBase> Self) {
26 
27   LLVM_DEBUG({
28     dbgs() << "Starting link phase 1 for graph " << G->getName() << "\n";
29   });
30 
31   // Prune and optimize the graph.
32   if (auto Err = runPasses(Passes.PrePrunePasses))
33     return Ctx->notifyFailed(std::move(Err));
34 
35   LLVM_DEBUG({
36     dbgs() << "Link graph \"" << G->getName() << "\" pre-pruning:\n";
37     dumpGraph(dbgs());
38   });
39 
40   prune(*G);
41 
42   LLVM_DEBUG({
43     dbgs() << "Link graph \"" << G->getName() << "\" post-pruning:\n";
44     dumpGraph(dbgs());
45   });
46 
47   // Run post-pruning passes.
48   if (auto Err = runPasses(Passes.PostPrunePasses))
49     return Ctx->notifyFailed(std::move(Err));
50 
51   // Sort blocks into segments.
52   auto Layout = layOutBlocks();
53 
54   // Allocate memory for segments.
55   if (auto Err = allocateSegments(Layout))
56     return Ctx->notifyFailed(std::move(Err));
57 
58   LLVM_DEBUG({
59     dbgs() << "Link graph \"" << G->getName()
60            << "\" before post-allocation passes:\n";
61     dumpGraph(dbgs());
62   });
63 
64   // Run post-allocation passes.
65   if (auto Err = runPasses(Passes.PostAllocationPasses))
66     return Ctx->notifyFailed(std::move(Err));
67 
68   // Notify client that the defined symbols have been assigned addresses.
69   LLVM_DEBUG(
70       { dbgs() << "Resolving symbols defined in " << G->getName() << "\n"; });
71 
72   if (auto Err = Ctx->notifyResolved(*G))
73     return Ctx->notifyFailed(std::move(Err));
74 
75   auto ExternalSymbols = getExternalSymbolNames();
76 
77   LLVM_DEBUG({
78     dbgs() << "Issuing lookup for external symbols for " << G->getName()
79            << " (may trigger materialization/linking of other graphs)...\n";
80   });
81 
82   // We're about to hand off ownership of ourself to the continuation. Grab a
83   // pointer to the context so that we can call it to initiate the lookup.
84   //
85   // FIXME: Once callee expressions are defined to be sequenced before argument
86   // expressions (c++17) we can simplify all this to:
87   //
88   // Ctx->lookup(std::move(UnresolvedExternals),
89   //             [Self=std::move(Self)](Expected<AsyncLookupResult> Result) {
90   //               Self->linkPhase2(std::move(Self), std::move(Result));
91   //             });
92   auto *TmpCtx = Ctx.get();
93   TmpCtx->lookup(std::move(ExternalSymbols),
94                  createLookupContinuation(
95                      [S = std::move(Self), L = std::move(Layout)](
96                          Expected<AsyncLookupResult> LookupResult) mutable {
97                        auto &TmpSelf = *S;
98                        TmpSelf.linkPhase2(std::move(S), std::move(LookupResult),
99                                           std::move(L));
100                      }));
101 }
102 
103 void JITLinkerBase::linkPhase2(std::unique_ptr<JITLinkerBase> Self,
104                                Expected<AsyncLookupResult> LR,
105                                SegmentLayoutMap Layout) {
106 
107   LLVM_DEBUG({
108     dbgs() << "Starting link phase 2 for graph " << G->getName() << "\n";
109   });
110 
111   // If the lookup failed, bail out.
112   if (!LR)
113     return deallocateAndBailOut(LR.takeError());
114 
115   // Assign addresses to external addressables.
116   applyLookupResult(*LR);
117 
118   // Copy block content to working memory.
119   copyBlockContentToWorkingMemory(Layout, *Alloc);
120 
121   LLVM_DEBUG({
122     dbgs() << "Link graph \"" << G->getName()
123            << "\" before pre-fixup passes:\n";
124     dumpGraph(dbgs());
125   });
126 
127   if (auto Err = runPasses(Passes.PreFixupPasses))
128     return deallocateAndBailOut(std::move(Err));
129 
130   LLVM_DEBUG({
131     dbgs() << "Link graph \"" << G->getName() << "\" before copy-and-fixup:\n";
132     dumpGraph(dbgs());
133   });
134 
135   // Fix up block content.
136   if (auto Err = fixUpBlocks(*G))
137     return deallocateAndBailOut(std::move(Err));
138 
139   LLVM_DEBUG({
140     dbgs() << "Link graph \"" << G->getName() << "\" after copy-and-fixup:\n";
141     dumpGraph(dbgs());
142   });
143 
144   if (auto Err = runPasses(Passes.PostFixupPasses))
145     return deallocateAndBailOut(std::move(Err));
146 
147   // FIXME: Use move capture once we have c++14.
148   auto *UnownedSelf = Self.release();
149   auto Phase3Continuation = [UnownedSelf](Error Err) {
150     std::unique_ptr<JITLinkerBase> Self(UnownedSelf);
151     UnownedSelf->linkPhase3(std::move(Self), std::move(Err));
152   };
153 
154   Alloc->finalizeAsync(std::move(Phase3Continuation));
155 }
156 
157 void JITLinkerBase::linkPhase3(std::unique_ptr<JITLinkerBase> Self, Error Err) {
158 
159   LLVM_DEBUG({
160     dbgs() << "Starting link phase 3 for graph " << G->getName() << "\n";
161   });
162 
163   if (Err)
164     return deallocateAndBailOut(std::move(Err));
165   Ctx->notifyFinalized(std::move(Alloc));
166 
167   LLVM_DEBUG({ dbgs() << "Link of graph " << G->getName() << " complete\n"; });
168 }
169 
170 Error JITLinkerBase::runPasses(LinkGraphPassList &Passes) {
171   for (auto &P : Passes)
172     if (auto Err = P(*G))
173       return Err;
174   return Error::success();
175 }
176 
177 JITLinkerBase::SegmentLayoutMap JITLinkerBase::layOutBlocks() {
178 
179   SegmentLayoutMap Layout;
180 
181   /// Partition blocks based on permissions and content vs. zero-fill.
182   for (auto *B : G->blocks()) {
183     auto &SegLists = Layout[B->getSection().getProtectionFlags()];
184     if (!B->isZeroFill())
185       SegLists.ContentBlocks.push_back(B);
186     else
187       SegLists.ZeroFillBlocks.push_back(B);
188   }
189 
190   /// Sort blocks within each list.
191   for (auto &KV : Layout) {
192 
193     auto CompareBlocks = [](const Block *LHS, const Block *RHS) {
194       // Sort by section, address and size
195       if (LHS->getSection().getOrdinal() != RHS->getSection().getOrdinal())
196         return LHS->getSection().getOrdinal() < RHS->getSection().getOrdinal();
197       if (LHS->getAddress() != RHS->getAddress())
198         return LHS->getAddress() < RHS->getAddress();
199       return LHS->getSize() < RHS->getSize();
200     };
201 
202     auto &SegLists = KV.second;
203     llvm::sort(SegLists.ContentBlocks, CompareBlocks);
204     llvm::sort(SegLists.ZeroFillBlocks, CompareBlocks);
205   }
206 
207   LLVM_DEBUG({
208     dbgs() << "Computed segment ordering:\n";
209     for (auto &KV : Layout) {
210       dbgs() << "  Segment "
211              << static_cast<sys::Memory::ProtectionFlags>(KV.first) << ":\n";
212       auto &SL = KV.second;
213       for (auto &SIEntry :
214            {std::make_pair(&SL.ContentBlocks, "content block"),
215             std::make_pair(&SL.ZeroFillBlocks, "zero-fill block")}) {
216         dbgs() << "    " << SIEntry.second << ":\n";
217         for (auto *B : *SIEntry.first)
218           dbgs() << "      " << *B << "\n";
219       }
220     }
221   });
222 
223   return Layout;
224 }
225 
226 Error JITLinkerBase::allocateSegments(const SegmentLayoutMap &Layout) {
227 
228   // Compute segment sizes and allocate memory.
229   LLVM_DEBUG(dbgs() << "JIT linker requesting: { ");
230   JITLinkMemoryManager::SegmentsRequestMap Segments;
231   for (auto &KV : Layout) {
232     auto &Prot = KV.first;
233     auto &SegLists = KV.second;
234 
235     uint64_t SegAlign = 1;
236 
237     // Calculate segment content size.
238     size_t SegContentSize = 0;
239     for (auto *B : SegLists.ContentBlocks) {
240       SegAlign = std::max(SegAlign, B->getAlignment());
241       SegContentSize = alignToBlock(SegContentSize, *B);
242       SegContentSize += B->getSize();
243     }
244 
245     uint64_t SegZeroFillStart = SegContentSize;
246     uint64_t SegZeroFillEnd = SegZeroFillStart;
247 
248     for (auto *B : SegLists.ZeroFillBlocks) {
249       SegAlign = std::max(SegAlign, B->getAlignment());
250       SegZeroFillEnd = alignToBlock(SegZeroFillEnd, *B);
251       SegZeroFillEnd += B->getSize();
252     }
253 
254     Segments[Prot] = {SegAlign, SegContentSize,
255                       SegZeroFillEnd - SegZeroFillStart};
256 
257     LLVM_DEBUG({
258       dbgs() << (&KV == &*Layout.begin() ? "" : "; ")
259              << static_cast<sys::Memory::ProtectionFlags>(Prot)
260              << ": alignment = " << SegAlign
261              << ", content size = " << SegContentSize
262              << ", zero-fill size = " << (SegZeroFillEnd - SegZeroFillStart);
263     });
264   }
265   LLVM_DEBUG(dbgs() << " }\n");
266 
267   if (auto AllocOrErr =
268           Ctx->getMemoryManager().allocate(Ctx->getJITLinkDylib(), Segments))
269     Alloc = std::move(*AllocOrErr);
270   else
271     return AllocOrErr.takeError();
272 
273   LLVM_DEBUG({
274     dbgs() << "JIT linker got memory (working -> target):\n";
275     for (auto &KV : Layout) {
276       auto Prot = static_cast<sys::Memory::ProtectionFlags>(KV.first);
277       dbgs() << "  " << Prot << ": "
278              << (const void *)Alloc->getWorkingMemory(Prot).data() << " -> "
279              << formatv("{0:x16}", Alloc->getTargetMemory(Prot)) << "\n";
280     }
281   });
282 
283   // Update block target addresses.
284   for (auto &KV : Layout) {
285     auto &Prot = KV.first;
286     auto &SL = KV.second;
287 
288     JITTargetAddress NextBlockAddr =
289         Alloc->getTargetMemory(static_cast<sys::Memory::ProtectionFlags>(Prot));
290 
291     for (auto *SIList : {&SL.ContentBlocks, &SL.ZeroFillBlocks})
292       for (auto *B : *SIList) {
293         NextBlockAddr = alignToBlock(NextBlockAddr, *B);
294         B->setAddress(NextBlockAddr);
295         NextBlockAddr += B->getSize();
296       }
297   }
298 
299   return Error::success();
300 }
301 
302 JITLinkContext::LookupMap JITLinkerBase::getExternalSymbolNames() const {
303   // Identify unresolved external symbols.
304   JITLinkContext::LookupMap UnresolvedExternals;
305   for (auto *Sym : G->external_symbols()) {
306     assert(Sym->getAddress() == 0 &&
307            "External has already been assigned an address");
308     assert(Sym->getName() != StringRef() && Sym->getName() != "" &&
309            "Externals must be named");
310     SymbolLookupFlags LookupFlags =
311         Sym->getLinkage() == Linkage::Weak
312             ? SymbolLookupFlags::WeaklyReferencedSymbol
313             : SymbolLookupFlags::RequiredSymbol;
314     UnresolvedExternals[Sym->getName()] = LookupFlags;
315   }
316   return UnresolvedExternals;
317 }
318 
319 void JITLinkerBase::applyLookupResult(AsyncLookupResult Result) {
320   for (auto *Sym : G->external_symbols()) {
321     assert(Sym->getOffset() == 0 &&
322            "External symbol is not at the start of its addressable block");
323     assert(Sym->getAddress() == 0 && "Symbol already resolved");
324     assert(!Sym->isDefined() && "Symbol being resolved is already defined");
325     auto ResultI = Result.find(Sym->getName());
326     if (ResultI != Result.end())
327       Sym->getAddressable().setAddress(ResultI->second.getAddress());
328     else
329       assert(Sym->getLinkage() == Linkage::Weak &&
330              "Failed to resolve non-weak reference");
331   }
332 
333   LLVM_DEBUG({
334     dbgs() << "Externals after applying lookup result:\n";
335     for (auto *Sym : G->external_symbols())
336       dbgs() << "  " << Sym->getName() << ": "
337              << formatv("{0:x16}", Sym->getAddress()) << "\n";
338   });
339 }
340 
341 void JITLinkerBase::copyBlockContentToWorkingMemory(
342     const SegmentLayoutMap &Layout, JITLinkMemoryManager::Allocation &Alloc) {
343 
344   LLVM_DEBUG(dbgs() << "Copying block content:\n");
345   for (auto &KV : Layout) {
346     auto &Prot = KV.first;
347     auto &SegLayout = KV.second;
348 
349     auto SegMem =
350         Alloc.getWorkingMemory(static_cast<sys::Memory::ProtectionFlags>(Prot));
351     char *LastBlockEnd = SegMem.data();
352     char *BlockDataPtr = LastBlockEnd;
353 
354     LLVM_DEBUG({
355       dbgs() << "  Processing segment "
356              << static_cast<sys::Memory::ProtectionFlags>(Prot) << " [ "
357              << (const void *)SegMem.data() << " .. "
358              << (const void *)((char *)SegMem.data() + SegMem.size())
359              << " ]\n    Processing content sections:\n";
360     });
361 
362     for (auto *B : SegLayout.ContentBlocks) {
363       LLVM_DEBUG(dbgs() << "    " << *B << ":\n");
364 
365       // Pad to alignment/alignment-offset.
366       BlockDataPtr = alignToBlock(BlockDataPtr, *B);
367 
368       LLVM_DEBUG({
369         dbgs() << "      Bumped block pointer to " << (const void *)BlockDataPtr
370                << " to meet block alignment " << B->getAlignment()
371                << " and alignment offset " << B->getAlignmentOffset() << "\n";
372       });
373 
374       // Zero pad up to alignment.
375       LLVM_DEBUG({
376         if (LastBlockEnd != BlockDataPtr)
377           dbgs() << "      Zero padding from " << (const void *)LastBlockEnd
378                  << " to " << (const void *)BlockDataPtr << "\n";
379       });
380 
381       while (LastBlockEnd != BlockDataPtr)
382         *LastBlockEnd++ = 0;
383 
384       // Copy initial block content.
385       LLVM_DEBUG({
386         dbgs() << "      Copying block " << *B << " content, "
387                << B->getContent().size() << " bytes, from "
388                << (const void *)B->getContent().data() << " to "
389                << (const void *)BlockDataPtr << "\n";
390       });
391       memcpy(BlockDataPtr, B->getContent().data(), B->getContent().size());
392 
393       // Point the block's content to the fixed up buffer.
394       B->setContent(StringRef(BlockDataPtr, B->getContent().size()));
395 
396       // Update block end pointer.
397       LastBlockEnd = BlockDataPtr + B->getContent().size();
398       BlockDataPtr = LastBlockEnd;
399     }
400 
401     // Zero pad the rest of the segment.
402     LLVM_DEBUG({
403       dbgs() << "    Zero padding end of segment from "
404              << (const void *)LastBlockEnd << " to "
405              << (const void *)((char *)SegMem.data() + SegMem.size()) << "\n";
406     });
407     while (LastBlockEnd != SegMem.data() + SegMem.size())
408       *LastBlockEnd++ = 0;
409   }
410 }
411 
412 void JITLinkerBase::deallocateAndBailOut(Error Err) {
413   assert(Err && "Should not be bailing out on success value");
414   assert(Alloc && "can not call deallocateAndBailOut before allocation");
415   Ctx->notifyFailed(joinErrors(std::move(Err), Alloc->deallocate()));
416 }
417 
418 void JITLinkerBase::dumpGraph(raw_ostream &OS) {
419   assert(G && "Graph is not set yet");
420   G->dump(dbgs(), [this](Edge::Kind K) { return getEdgeKindName(K); });
421 }
422 
423 void prune(LinkGraph &G) {
424   std::vector<Symbol *> Worklist;
425   DenseSet<Block *> VisitedBlocks;
426 
427   // Build the initial worklist from all symbols initially live.
428   for (auto *Sym : G.defined_symbols())
429     if (Sym->isLive())
430       Worklist.push_back(Sym);
431 
432   // Propagate live flags to all symbols reachable from the initial live set.
433   while (!Worklist.empty()) {
434     auto *Sym = Worklist.back();
435     Worklist.pop_back();
436 
437     auto &B = Sym->getBlock();
438 
439     // Skip addressables that we've visited before.
440     if (VisitedBlocks.count(&B))
441       continue;
442 
443     VisitedBlocks.insert(&B);
444 
445     for (auto &E : Sym->getBlock().edges()) {
446       // If the edge target is a defined symbol that is being newly marked live
447       // then add it to the worklist.
448       if (E.getTarget().isDefined() && !E.getTarget().isLive())
449         Worklist.push_back(&E.getTarget());
450 
451       // Mark the target live.
452       E.getTarget().setLive(true);
453     }
454   }
455 
456   // Collect all defined symbols to remove, then remove them.
457   {
458     LLVM_DEBUG(dbgs() << "Dead-stripping defined symbols:\n");
459     std::vector<Symbol *> SymbolsToRemove;
460     for (auto *Sym : G.defined_symbols())
461       if (!Sym->isLive())
462         SymbolsToRemove.push_back(Sym);
463     for (auto *Sym : SymbolsToRemove) {
464       LLVM_DEBUG(dbgs() << "  " << *Sym << "...\n");
465       G.removeDefinedSymbol(*Sym);
466     }
467   }
468 
469   // Delete any unused blocks.
470   {
471     LLVM_DEBUG(dbgs() << "Dead-stripping blocks:\n");
472     std::vector<Block *> BlocksToRemove;
473     for (auto *B : G.blocks())
474       if (!VisitedBlocks.count(B))
475         BlocksToRemove.push_back(B);
476     for (auto *B : BlocksToRemove) {
477       LLVM_DEBUG(dbgs() << "  " << *B << "...\n");
478       G.removeBlock(*B);
479     }
480   }
481 
482   // Collect all external symbols to remove, then remove them.
483   {
484     LLVM_DEBUG(dbgs() << "Removing unused external symbols:\n");
485     std::vector<Symbol *> SymbolsToRemove;
486     for (auto *Sym : G.external_symbols())
487       if (!Sym->isLive())
488         SymbolsToRemove.push_back(Sym);
489     for (auto *Sym : SymbolsToRemove) {
490       LLVM_DEBUG(dbgs() << "  " << *Sym << "...\n");
491       G.removeExternalSymbol(*Sym);
492     }
493   }
494 }
495 
496 } // end namespace jitlink
497 } // end namespace llvm
498