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
20namespace llvm {
21namespace jitlink {
22
23JITLinkerBase::~JITLinkerBase() {}
24
25void JITLinkerBase::linkPhase1(std::unique_ptr<JITLinkerBase> Self) {
26
27  // Build the link graph.
28  if (auto GraphOrErr = buildGraph(Ctx->getObjectBuffer()))
29    G = std::move(*GraphOrErr);
30  else
31    return Ctx->notifyFailed(GraphOrErr.takeError());
32  assert(G && "Graph should have been created by buildGraph above");
33
34  // Prune and optimize the graph.
35  if (auto Err = runPasses(Passes.PrePrunePasses))
36    return Ctx->notifyFailed(std::move(Err));
37
38  LLVM_DEBUG({
39    dbgs() << "Link graph \"" << G->getName() << "\" pre-pruning:\n";
40    dumpGraph(dbgs());
41  });
42
43  prune(*G);
44
45  LLVM_DEBUG({
46    dbgs() << "Link graph \"" << G->getName() << "\" post-pruning:\n";
47    dumpGraph(dbgs());
48  });
49
50  // Run post-pruning passes.
51  if (auto Err = runPasses(Passes.PostPrunePasses))
52    return Ctx->notifyFailed(std::move(Err));
53
54  // Sort blocks into segments.
55  auto Layout = layOutBlocks();
56
57  // Allocate memory for segments.
58  if (auto Err = allocateSegments(Layout))
59    return Ctx->notifyFailed(std::move(Err));
60
61  // Notify client that the defined symbols have been assigned addresses.
62  Ctx->notifyResolved(*G);
63
64  auto ExternalSymbols = getExternalSymbolNames();
65
66  // We're about to hand off ownership of ourself to the continuation. Grab a
67  // pointer to the context so that we can call it to initiate the lookup.
68  //
69  // FIXME: Once callee expressions are defined to be sequenced before argument
70  // expressions (c++17) we can simplify all this to:
71  //
72  // Ctx->lookup(std::move(UnresolvedExternals),
73  //             [Self=std::move(Self)](Expected<AsyncLookupResult> Result) {
74  //               Self->linkPhase2(std::move(Self), std::move(Result));
75  //             });
76  auto *TmpCtx = Ctx.get();
77  TmpCtx->lookup(std::move(ExternalSymbols),
78                 createLookupContinuation(
79                     [S = std::move(Self), L = std::move(Layout)](
80                         Expected<AsyncLookupResult> LookupResult) mutable {
81                       auto &TmpSelf = *S;
82                       TmpSelf.linkPhase2(std::move(S), std::move(LookupResult),
83                                          std::move(L));
84                     }));
85}
86
87void JITLinkerBase::linkPhase2(std::unique_ptr<JITLinkerBase> Self,
88                               Expected<AsyncLookupResult> LR,
89                               SegmentLayoutMap Layout) {
90  // If the lookup failed, bail out.
91  if (!LR)
92    return deallocateAndBailOut(LR.takeError());
93
94  // Assign addresses to external addressables.
95  applyLookupResult(*LR);
96
97  LLVM_DEBUG({
98    dbgs() << "Link graph \"" << G->getName() << "\" before copy-and-fixup:\n";
99    dumpGraph(dbgs());
100  });
101
102  // Copy block content to working memory and fix up.
103  if (auto Err = copyAndFixUpBlocks(Layout, *Alloc))
104    return deallocateAndBailOut(std::move(Err));
105
106  LLVM_DEBUG({
107    dbgs() << "Link graph \"" << G->getName() << "\" after copy-and-fixup:\n";
108    dumpGraph(dbgs());
109  });
110
111  if (auto Err = runPasses(Passes.PostFixupPasses))
112    return deallocateAndBailOut(std::move(Err));
113
114  // FIXME: Use move capture once we have c++14.
115  auto *UnownedSelf = Self.release();
116  auto Phase3Continuation = [UnownedSelf](Error Err) {
117    std::unique_ptr<JITLinkerBase> Self(UnownedSelf);
118    UnownedSelf->linkPhase3(std::move(Self), std::move(Err));
119  };
120
121  Alloc->finalizeAsync(std::move(Phase3Continuation));
122}
123
124void JITLinkerBase::linkPhase3(std::unique_ptr<JITLinkerBase> Self, Error Err) {
125  if (Err)
126    return deallocateAndBailOut(std::move(Err));
127  Ctx->notifyFinalized(std::move(Alloc));
128}
129
130Error JITLinkerBase::runPasses(LinkGraphPassList &Passes) {
131  for (auto &P : Passes)
132    if (auto Err = P(*G))
133      return Err;
134  return Error::success();
135}
136
137JITLinkerBase::SegmentLayoutMap JITLinkerBase::layOutBlocks() {
138
139  SegmentLayoutMap Layout;
140
141  /// Partition blocks based on permissions and content vs. zero-fill.
142  for (auto *B : G->blocks()) {
143    auto &SegLists = Layout[B->getSection().getProtectionFlags()];
144    if (!B->isZeroFill())
145      SegLists.ContentBlocks.push_back(B);
146    else
147      SegLists.ZeroFillBlocks.push_back(B);
148  }
149
150  /// Sort blocks within each list.
151  for (auto &KV : Layout) {
152
153    auto CompareBlocks = [](const Block *LHS, const Block *RHS) {
154      // Sort by section, address and size
155      if (LHS->getSection().getOrdinal() != RHS->getSection().getOrdinal())
156        return LHS->getSection().getOrdinal() < RHS->getSection().getOrdinal();
157      if (LHS->getAddress() != RHS->getAddress())
158        return LHS->getAddress() < RHS->getAddress();
159      return LHS->getSize() < RHS->getSize();
160    };
161
162    auto &SegLists = KV.second;
163    llvm::sort(SegLists.ContentBlocks, CompareBlocks);
164    llvm::sort(SegLists.ZeroFillBlocks, CompareBlocks);
165  }
166
167  LLVM_DEBUG({
168    dbgs() << "Segment ordering:\n";
169    for (auto &KV : Layout) {
170      dbgs() << "  Segment "
171             << static_cast<sys::Memory::ProtectionFlags>(KV.first) << ":\n";
172      auto &SL = KV.second;
173      for (auto &SIEntry :
174           {std::make_pair(&SL.ContentBlocks, "content block"),
175            std::make_pair(&SL.ZeroFillBlocks, "zero-fill block")}) {
176        dbgs() << "    " << SIEntry.second << ":\n";
177        for (auto *B : *SIEntry.first)
178          dbgs() << "      " << *B << "\n";
179      }
180    }
181  });
182
183  return Layout;
184}
185
186Error JITLinkerBase::allocateSegments(const SegmentLayoutMap &Layout) {
187
188  // Compute segment sizes and allocate memory.
189  LLVM_DEBUG(dbgs() << "JIT linker requesting: { ");
190  JITLinkMemoryManager::SegmentsRequestMap Segments;
191  for (auto &KV : Layout) {
192    auto &Prot = KV.first;
193    auto &SegLists = KV.second;
194
195    uint64_t SegAlign = 1;
196
197    // Calculate segment content size.
198    size_t SegContentSize = 0;
199    for (auto *B : SegLists.ContentBlocks) {
200      SegAlign = std::max(SegAlign, B->getAlignment());
201      SegContentSize = alignToBlock(SegContentSize, *B);
202      SegContentSize += B->getSize();
203    }
204
205    uint64_t SegZeroFillStart = SegContentSize;
206    uint64_t SegZeroFillEnd = SegZeroFillStart;
207
208    for (auto *B : SegLists.ZeroFillBlocks) {
209      SegAlign = std::max(SegAlign, B->getAlignment());
210      SegZeroFillEnd = alignToBlock(SegZeroFillEnd, *B);
211      SegZeroFillEnd += B->getSize();
212    }
213
214    Segments[Prot] = {SegAlign, SegContentSize,
215                      SegZeroFillEnd - SegZeroFillStart};
216
217    LLVM_DEBUG({
218      dbgs() << (&KV == &*Layout.begin() ? "" : "; ")
219             << static_cast<sys::Memory::ProtectionFlags>(Prot)
220             << ": alignment = " << SegAlign
221             << ", content size = " << SegContentSize
222             << ", zero-fill size = " << (SegZeroFillEnd - SegZeroFillStart);
223    });
224  }
225  LLVM_DEBUG(dbgs() << " }\n");
226
227  if (auto AllocOrErr = Ctx->getMemoryManager().allocate(Segments))
228    Alloc = std::move(*AllocOrErr);
229  else
230    return AllocOrErr.takeError();
231
232  LLVM_DEBUG({
233    dbgs() << "JIT linker got working memory:\n";
234    for (auto &KV : Layout) {
235      auto Prot = static_cast<sys::Memory::ProtectionFlags>(KV.first);
236      dbgs() << "  " << Prot << ": "
237             << (const void *)Alloc->getWorkingMemory(Prot).data() << "\n";
238    }
239  });
240
241  // Update block target addresses.
242  for (auto &KV : Layout) {
243    auto &Prot = KV.first;
244    auto &SL = KV.second;
245
246    JITTargetAddress NextBlockAddr =
247        Alloc->getTargetMemory(static_cast<sys::Memory::ProtectionFlags>(Prot));
248
249    for (auto *SIList : {&SL.ContentBlocks, &SL.ZeroFillBlocks})
250      for (auto *B : *SIList) {
251        NextBlockAddr = alignToBlock(NextBlockAddr, *B);
252        B->setAddress(NextBlockAddr);
253        NextBlockAddr += B->getSize();
254      }
255  }
256
257  return Error::success();
258}
259
260JITLinkContext::LookupMap JITLinkerBase::getExternalSymbolNames() const {
261  // Identify unresolved external symbols.
262  JITLinkContext::LookupMap UnresolvedExternals;
263  for (auto *Sym : G->external_symbols()) {
264    assert(Sym->getAddress() == 0 &&
265           "External has already been assigned an address");
266    assert(Sym->getName() != StringRef() && Sym->getName() != "" &&
267           "Externals must be named");
268    SymbolLookupFlags LookupFlags =
269        Sym->getLinkage() == Linkage::Weak
270            ? SymbolLookupFlags::WeaklyReferencedSymbol
271            : SymbolLookupFlags::RequiredSymbol;
272    UnresolvedExternals[Sym->getName()] = LookupFlags;
273  }
274  return UnresolvedExternals;
275}
276
277void JITLinkerBase::applyLookupResult(AsyncLookupResult Result) {
278  for (auto *Sym : G->external_symbols()) {
279    assert(Sym->getOffset() == 0 &&
280           "External symbol is not at the start of its addressable block");
281    assert(Sym->getAddress() == 0 && "Symbol already resolved");
282    assert(!Sym->isDefined() && "Symbol being resolved is already defined");
283    auto ResultI = Result.find(Sym->getName());
284    if (ResultI != Result.end())
285      Sym->getAddressable().setAddress(ResultI->second.getAddress());
286    else
287      assert(Sym->getLinkage() == Linkage::Weak &&
288             "Failed to resolve non-weak reference");
289  }
290
291  LLVM_DEBUG({
292    dbgs() << "Externals after applying lookup result:\n";
293    for (auto *Sym : G->external_symbols())
294      dbgs() << "  " << Sym->getName() << ": "
295             << formatv("{0:x16}", Sym->getAddress()) << "\n";
296  });
297  assert(llvm::all_of(G->external_symbols(),
298                      [](Symbol *Sym) {
299                        return Sym->getAddress() != 0 ||
300                               Sym->getLinkage() == Linkage::Weak;
301                      }) &&
302         "All strong external symbols should have been resolved by now");
303}
304
305void JITLinkerBase::deallocateAndBailOut(Error Err) {
306  assert(Err && "Should not be bailing out on success value");
307  assert(Alloc && "can not call deallocateAndBailOut before allocation");
308  Ctx->notifyFailed(joinErrors(std::move(Err), Alloc->deallocate()));
309}
310
311void JITLinkerBase::dumpGraph(raw_ostream &OS) {
312  assert(G && "Graph is not set yet");
313  G->dump(dbgs(), [this](Edge::Kind K) { return getEdgeKindName(K); });
314}
315
316void prune(LinkGraph &G) {
317  std::vector<Symbol *> Worklist;
318  DenseSet<Block *> VisitedBlocks;
319
320  // Build the initial worklist from all symbols initially live.
321  for (auto *Sym : G.defined_symbols())
322    if (Sym->isLive())
323      Worklist.push_back(Sym);
324
325  // Propagate live flags to all symbols reachable from the initial live set.
326  while (!Worklist.empty()) {
327    auto *Sym = Worklist.back();
328    Worklist.pop_back();
329
330    auto &B = Sym->getBlock();
331
332    // Skip addressables that we've visited before.
333    if (VisitedBlocks.count(&B))
334      continue;
335
336    VisitedBlocks.insert(&B);
337
338    for (auto &E : Sym->getBlock().edges()) {
339      if (E.getTarget().isDefined() && !E.getTarget().isLive()) {
340        E.getTarget().setLive(true);
341        Worklist.push_back(&E.getTarget());
342      }
343    }
344  }
345
346  // Collect all the symbols to remove, then remove them.
347  {
348    LLVM_DEBUG(dbgs() << "Dead-stripping symbols:\n");
349    std::vector<Symbol *> SymbolsToRemove;
350    for (auto *Sym : G.defined_symbols())
351      if (!Sym->isLive())
352        SymbolsToRemove.push_back(Sym);
353    for (auto *Sym : SymbolsToRemove) {
354      LLVM_DEBUG(dbgs() << "  " << *Sym << "...\n");
355      G.removeDefinedSymbol(*Sym);
356    }
357  }
358
359  // Delete any unused blocks.
360  {
361    LLVM_DEBUG(dbgs() << "Dead-stripping blocks:\n");
362    std::vector<Block *> BlocksToRemove;
363    for (auto *B : G.blocks())
364      if (!VisitedBlocks.count(B))
365        BlocksToRemove.push_back(B);
366    for (auto *B : BlocksToRemove) {
367      LLVM_DEBUG(dbgs() << "  " << *B << "...\n");
368      G.removeBlock(*B);
369    }
370  }
371}
372
373} // end namespace jitlink
374} // end namespace llvm
375