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