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 #include "EHFrameSupportImpl.h" 15 16 #include "llvm/Support/BinaryStreamReader.h" 17 #include "llvm/Support/MemoryBuffer.h" 18 19 #define DEBUG_TYPE "jitlink" 20 21 namespace llvm { 22 namespace jitlink { 23 24 JITLinkerBase::~JITLinkerBase() {} 25 26 void JITLinkerBase::linkPhase1(std::unique_ptr<JITLinkerBase> Self) { 27 28 // Build the atom graph. 29 if (auto GraphOrErr = buildGraph(Ctx->getObjectBuffer())) 30 G = std::move(*GraphOrErr); 31 else 32 return Ctx->notifyFailed(GraphOrErr.takeError()); 33 assert(G && "Graph should have been created by buildGraph above"); 34 35 // Prune and optimize the graph. 36 if (auto Err = runPasses(Passes.PrePrunePasses, *G)) 37 return Ctx->notifyFailed(std::move(Err)); 38 39 LLVM_DEBUG({ 40 dbgs() << "Atom graph \"" << G->getName() << "\" pre-pruning:\n"; 41 dumpGraph(dbgs()); 42 }); 43 44 prune(*G); 45 46 LLVM_DEBUG({ 47 dbgs() << "Atom graph \"" << G->getName() << "\" post-pruning:\n"; 48 dumpGraph(dbgs()); 49 }); 50 51 // Run post-pruning passes. 52 if (auto Err = runPasses(Passes.PostPrunePasses, *G)) 53 return Ctx->notifyFailed(std::move(Err)); 54 55 // Sort atoms into segments. 56 layOutAtoms(); 57 58 // Allocate memory for segments. 59 if (auto Err = allocateSegments(Layout)) 60 return Ctx->notifyFailed(std::move(Err)); 61 62 // Notify client that the defined atoms have been assigned addresses. 63 Ctx->notifyResolved(*G); 64 65 auto ExternalSymbols = getExternalSymbolNames(); 66 67 // We're about to hand off ownership of ourself to the continuation. Grab a 68 // pointer to the context so that we can call it to initiate the lookup. 69 // 70 // FIXME: Once callee expressions are defined to be sequenced before argument 71 // expressions (c++17) we can simplify all this to: 72 // 73 // Ctx->lookup(std::move(UnresolvedExternals), 74 // [Self=std::move(Self)](Expected<AsyncLookupResult> Result) { 75 // Self->linkPhase2(std::move(Self), std::move(Result)); 76 // }); 77 // 78 // FIXME: Use move capture once we have c++14. 79 auto *TmpCtx = Ctx.get(); 80 auto *UnownedSelf = Self.release(); 81 auto Phase2Continuation = 82 [UnownedSelf](Expected<AsyncLookupResult> LookupResult) { 83 std::unique_ptr<JITLinkerBase> Self(UnownedSelf); 84 UnownedSelf->linkPhase2(std::move(Self), std::move(LookupResult)); 85 }; 86 TmpCtx->lookup(std::move(ExternalSymbols), std::move(Phase2Continuation)); 87 } 88 89 void JITLinkerBase::linkPhase2(std::unique_ptr<JITLinkerBase> Self, 90 Expected<AsyncLookupResult> LR) { 91 // If the lookup failed, bail out. 92 if (!LR) 93 return deallocateAndBailOut(LR.takeError()); 94 95 // Assign addresses to external atoms. 96 applyLookupResult(*LR); 97 98 LLVM_DEBUG({ 99 dbgs() << "Atom graph \"" << G->getName() << "\" before copy-and-fixup:\n"; 100 dumpGraph(dbgs()); 101 }); 102 103 // Copy atom content to working memory and fix up. 104 if (auto Err = copyAndFixUpAllAtoms(Layout, *Alloc)) 105 return deallocateAndBailOut(std::move(Err)); 106 107 LLVM_DEBUG({ 108 dbgs() << "Atom graph \"" << G->getName() << "\" after copy-and-fixup:\n"; 109 dumpGraph(dbgs()); 110 }); 111 112 if (auto Err = runPasses(Passes.PostFixupPasses, *G)) 113 return deallocateAndBailOut(std::move(Err)); 114 115 // FIXME: Use move capture once we have c++14. 116 auto *UnownedSelf = Self.release(); 117 auto Phase3Continuation = [UnownedSelf](Error Err) { 118 std::unique_ptr<JITLinkerBase> Self(UnownedSelf); 119 UnownedSelf->linkPhase3(std::move(Self), std::move(Err)); 120 }; 121 122 Alloc->finalizeAsync(std::move(Phase3Continuation)); 123 } 124 125 void JITLinkerBase::linkPhase3(std::unique_ptr<JITLinkerBase> Self, Error Err) { 126 if (Err) 127 return deallocateAndBailOut(std::move(Err)); 128 Ctx->notifyFinalized(std::move(Alloc)); 129 } 130 131 Error JITLinkerBase::runPasses(AtomGraphPassList &Passes, AtomGraph &G) { 132 for (auto &P : Passes) 133 if (auto Err = P(G)) 134 return Err; 135 return Error::success(); 136 } 137 138 void JITLinkerBase::layOutAtoms() { 139 // Group sections by protections, and whether or not they're zero-fill. 140 for (auto &S : G->sections()) { 141 142 // Skip empty sections. 143 if (S.atoms_empty()) 144 continue; 145 146 auto &SL = Layout[S.getProtectionFlags()]; 147 if (S.isZeroFill()) 148 SL.ZeroFillSections.push_back(SegmentLayout::SectionLayout(S)); 149 else 150 SL.ContentSections.push_back(SegmentLayout::SectionLayout(S)); 151 } 152 153 // Sort sections within the layout by ordinal. 154 { 155 auto CompareByOrdinal = [](const SegmentLayout::SectionLayout &LHS, 156 const SegmentLayout::SectionLayout &RHS) { 157 return LHS.S->getSectionOrdinal() < RHS.S->getSectionOrdinal(); 158 }; 159 for (auto &KV : Layout) { 160 auto &SL = KV.second; 161 llvm::sort(SL.ContentSections, CompareByOrdinal); 162 llvm::sort(SL.ZeroFillSections, CompareByOrdinal); 163 } 164 } 165 166 // Add atoms to the sections. 167 for (auto &KV : Layout) { 168 auto &SL = KV.second; 169 for (auto *SIList : {&SL.ContentSections, &SL.ZeroFillSections}) { 170 for (auto &SI : *SIList) { 171 // First build the set of layout-heads (i.e. "heads" of layout-next 172 // chains) by copying the section atoms, then eliminating any that 173 // appear as layout-next targets. 174 DenseSet<DefinedAtom *> LayoutHeads; 175 for (auto *DA : SI.S->atoms()) 176 LayoutHeads.insert(DA); 177 178 for (auto *DA : SI.S->atoms()) 179 if (DA->hasLayoutNext()) 180 LayoutHeads.erase(&DA->getLayoutNext()); 181 182 // Next, sort the layout heads by address order. 183 std::vector<DefinedAtom *> OrderedLayoutHeads; 184 OrderedLayoutHeads.reserve(LayoutHeads.size()); 185 for (auto *DA : LayoutHeads) 186 OrderedLayoutHeads.push_back(DA); 187 188 // Now sort the list of layout heads by address. 189 llvm::sort(OrderedLayoutHeads, 190 [](const DefinedAtom *LHS, const DefinedAtom *RHS) { 191 return LHS->getAddress() < RHS->getAddress(); 192 }); 193 194 // Now populate the SI.Atoms field by appending each of the chains. 195 for (auto *DA : OrderedLayoutHeads) { 196 SI.Atoms.push_back(DA); 197 while (DA->hasLayoutNext()) { 198 auto &Next = DA->getLayoutNext(); 199 SI.Atoms.push_back(&Next); 200 DA = &Next; 201 } 202 } 203 } 204 } 205 } 206 207 LLVM_DEBUG({ 208 dbgs() << "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.ContentSections, "content sections"), 215 std::make_pair(&SL.ZeroFillSections, "zero-fill sections")}) { 216 auto &SIList = *SIEntry.first; 217 dbgs() << " " << SIEntry.second << ":\n"; 218 for (auto &SI : SIList) { 219 dbgs() << " " << SI.S->getName() << ":\n"; 220 for (auto *DA : SI.Atoms) 221 dbgs() << " " << *DA << "\n"; 222 } 223 } 224 } 225 }); 226 } 227 228 Error JITLinkerBase::allocateSegments(const SegmentLayoutMap &Layout) { 229 230 // Compute segment sizes and allocate memory. 231 LLVM_DEBUG(dbgs() << "JIT linker requesting: { "); 232 JITLinkMemoryManager::SegmentsRequestMap Segments; 233 for (auto &KV : Layout) { 234 auto &Prot = KV.first; 235 auto &SegLayout = KV.second; 236 237 // Calculate segment content size. 238 size_t SegContentSize = 0; 239 for (auto &SI : SegLayout.ContentSections) { 240 assert(!SI.S->atoms_empty() && "Sections in layout must not be empty"); 241 assert(!SI.Atoms.empty() && "Section layouts must not be empty"); 242 243 // Bump to section alignment before processing atoms. 244 SegContentSize = alignTo(SegContentSize, SI.S->getAlignment()); 245 246 for (auto *DA : SI.Atoms) { 247 SegContentSize = alignTo(SegContentSize, DA->getAlignment()); 248 SegContentSize += DA->getSize(); 249 } 250 } 251 252 // Get segment content alignment. 253 unsigned SegContentAlign = 1; 254 if (!SegLayout.ContentSections.empty()) { 255 auto &FirstContentSection = SegLayout.ContentSections.front(); 256 SegContentAlign = 257 std::max(FirstContentSection.S->getAlignment(), 258 FirstContentSection.Atoms.front()->getAlignment()); 259 } 260 261 // Calculate segment zero-fill size. 262 uint64_t SegZeroFillSize = 0; 263 for (auto &SI : SegLayout.ZeroFillSections) { 264 assert(!SI.S->atoms_empty() && "Sections in layout must not be empty"); 265 assert(!SI.Atoms.empty() && "Section layouts must not be empty"); 266 267 // Bump to section alignment before processing atoms. 268 SegZeroFillSize = alignTo(SegZeroFillSize, SI.S->getAlignment()); 269 270 for (auto *DA : SI.Atoms) { 271 SegZeroFillSize = alignTo(SegZeroFillSize, DA->getAlignment()); 272 SegZeroFillSize += DA->getSize(); 273 } 274 } 275 276 // Calculate segment zero-fill alignment. 277 uint32_t SegZeroFillAlign = 1; 278 279 if (!SegLayout.ZeroFillSections.empty()) { 280 auto &FirstZeroFillSection = SegLayout.ZeroFillSections.front(); 281 SegZeroFillAlign = 282 std::max(FirstZeroFillSection.S->getAlignment(), 283 FirstZeroFillSection.Atoms.front()->getAlignment()); 284 } 285 286 if (SegContentSize == 0) 287 SegContentAlign = SegZeroFillAlign; 288 289 if (SegContentAlign % SegZeroFillAlign != 0) 290 return make_error<JITLinkError>("First content atom alignment does not " 291 "accommodate first zero-fill atom " 292 "alignment"); 293 294 Segments[Prot] = {SegContentSize, SegContentAlign, SegZeroFillSize, 295 SegZeroFillAlign}; 296 297 LLVM_DEBUG({ 298 dbgs() << (&KV == &*Layout.begin() ? "" : "; ") 299 << static_cast<sys::Memory::ProtectionFlags>(Prot) << ": " 300 << SegContentSize << " content bytes (alignment " 301 << SegContentAlign << ") + " << SegZeroFillSize 302 << " zero-fill bytes (alignment " << SegZeroFillAlign << ")"; 303 }); 304 } 305 LLVM_DEBUG(dbgs() << " }\n"); 306 307 if (auto AllocOrErr = Ctx->getMemoryManager().allocate(Segments)) 308 Alloc = std::move(*AllocOrErr); 309 else 310 return AllocOrErr.takeError(); 311 312 LLVM_DEBUG({ 313 dbgs() << "JIT linker got working memory:\n"; 314 for (auto &KV : Layout) { 315 auto Prot = static_cast<sys::Memory::ProtectionFlags>(KV.first); 316 dbgs() << " " << Prot << ": " 317 << (const void *)Alloc->getWorkingMemory(Prot).data() << "\n"; 318 } 319 }); 320 321 // Update atom target addresses. 322 for (auto &KV : Layout) { 323 auto &Prot = KV.first; 324 auto &SL = KV.second; 325 326 JITTargetAddress AtomTargetAddr = 327 Alloc->getTargetMemory(static_cast<sys::Memory::ProtectionFlags>(Prot)); 328 329 for (auto *SIList : {&SL.ContentSections, &SL.ZeroFillSections}) 330 for (auto &SI : *SIList) { 331 AtomTargetAddr = alignTo(AtomTargetAddr, SI.S->getAlignment()); 332 for (auto *DA : SI.Atoms) { 333 AtomTargetAddr = alignTo(AtomTargetAddr, DA->getAlignment()); 334 DA->setAddress(AtomTargetAddr); 335 AtomTargetAddr += DA->getSize(); 336 } 337 } 338 } 339 340 return Error::success(); 341 } 342 343 DenseSet<StringRef> JITLinkerBase::getExternalSymbolNames() const { 344 // Identify unresolved external atoms. 345 DenseSet<StringRef> UnresolvedExternals; 346 for (auto *DA : G->external_atoms()) { 347 assert(DA->getAddress() == 0 && 348 "External has already been assigned an address"); 349 assert(DA->getName() != StringRef() && DA->getName() != "" && 350 "Externals must be named"); 351 UnresolvedExternals.insert(DA->getName()); 352 } 353 return UnresolvedExternals; 354 } 355 356 void JITLinkerBase::applyLookupResult(AsyncLookupResult Result) { 357 for (auto &KV : Result) { 358 Atom &A = G->getAtomByName(KV.first); 359 assert(A.getAddress() == 0 && "Atom already resolved"); 360 A.setAddress(KV.second.getAddress()); 361 } 362 363 LLVM_DEBUG({ 364 dbgs() << "Externals after applying lookup result:\n"; 365 for (auto *A : G->external_atoms()) 366 dbgs() << " " << A->getName() << ": " 367 << formatv("{0:x16}", A->getAddress()) << "\n"; 368 }); 369 assert(llvm::all_of(G->external_atoms(), 370 [](Atom *A) { return A->getAddress() != 0; }) && 371 "All atoms should have been resolved by this point"); 372 } 373 374 void JITLinkerBase::deallocateAndBailOut(Error Err) { 375 assert(Err && "Should not be bailing out on success value"); 376 assert(Alloc && "can not call deallocateAndBailOut before allocation"); 377 Ctx->notifyFailed(joinErrors(std::move(Err), Alloc->deallocate())); 378 } 379 380 void JITLinkerBase::dumpGraph(raw_ostream &OS) { 381 assert(G && "Graph is not set yet"); 382 G->dump(dbgs(), [this](Edge::Kind K) { return getEdgeKindName(K); }); 383 } 384 385 void prune(AtomGraph &G) { 386 std::vector<DefinedAtom *> Worklist; 387 DenseMap<DefinedAtom *, std::vector<Edge *>> EdgesToUpdate; 388 389 // Build the initial worklist from all atoms initially live. 390 for (auto *DA : G.defined_atoms()) { 391 if (!DA->isLive() || DA->shouldDiscard()) 392 continue; 393 394 for (auto &E : DA->edges()) { 395 if (!E.getTarget().isDefined()) 396 continue; 397 398 auto &EDT = static_cast<DefinedAtom &>(E.getTarget()); 399 400 if (EDT.shouldDiscard()) 401 EdgesToUpdate[&EDT].push_back(&E); 402 else if (E.isKeepAlive() && !EDT.isLive()) 403 Worklist.push_back(&EDT); 404 } 405 } 406 407 // Propagate live flags to all atoms reachable from the initial live set. 408 while (!Worklist.empty()) { 409 DefinedAtom &NextLive = *Worklist.back(); 410 Worklist.pop_back(); 411 412 assert(!NextLive.shouldDiscard() && 413 "should-discard nodes should never make it into the worklist"); 414 415 // If this atom has already been marked as live, or is marked to be 416 // discarded, then skip it. 417 if (NextLive.isLive()) 418 continue; 419 420 // Otherwise set it as live and add any non-live atoms that it points to 421 // to the worklist. 422 NextLive.setLive(true); 423 424 for (auto &E : NextLive.edges()) { 425 if (!E.getTarget().isDefined()) 426 continue; 427 428 auto &EDT = static_cast<DefinedAtom &>(E.getTarget()); 429 430 if (EDT.shouldDiscard()) 431 EdgesToUpdate[&EDT].push_back(&E); 432 else if (E.isKeepAlive() && !EDT.isLive()) 433 Worklist.push_back(&EDT); 434 } 435 } 436 437 // Collect atoms to remove, then remove them from the graph. 438 std::vector<DefinedAtom *> AtomsToRemove; 439 for (auto *DA : G.defined_atoms()) 440 if (DA->shouldDiscard() || !DA->isLive()) 441 AtomsToRemove.push_back(DA); 442 443 LLVM_DEBUG(dbgs() << "Pruning atoms:\n"); 444 for (auto *DA : AtomsToRemove) { 445 LLVM_DEBUG(dbgs() << " " << *DA << "... "); 446 447 // Check whether we need to replace this atom with an external atom. 448 // 449 // We replace if all of the following hold: 450 // (1) The atom is marked should-discard, 451 // (2) it has live edges (i.e. edges from live atoms) pointing to it. 452 // 453 // Otherwise we simply delete the atom. 454 455 G.removeDefinedAtom(*DA); 456 457 auto EdgesToUpdateItr = EdgesToUpdate.find(DA); 458 if (EdgesToUpdateItr != EdgesToUpdate.end()) { 459 auto &ExternalReplacement = G.addExternalAtom(DA->getName()); 460 for (auto *EdgeToUpdate : EdgesToUpdateItr->second) 461 EdgeToUpdate->setTarget(ExternalReplacement); 462 LLVM_DEBUG(dbgs() << "replaced with " << ExternalReplacement << "\n"); 463 } else 464 LLVM_DEBUG(dbgs() << "deleted\n"); 465 } 466 467 // Finally, discard any absolute symbols that were marked should-discard. 468 { 469 std::vector<Atom *> AbsoluteAtomsToRemove; 470 for (auto *A : G.absolute_atoms()) 471 if (A->shouldDiscard() || A->isLive()) 472 AbsoluteAtomsToRemove.push_back(A); 473 for (auto *A : AbsoluteAtomsToRemove) 474 G.removeAbsoluteAtom(*A); 475 } 476 } 477 478 } // end namespace jitlink 479 } // end namespace llvm 480