1 //=--------- MachOLinkGraphBuilder.cpp - MachO LinkGraph builder ----------===// 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 MachO LinkGraph buliding code. 10 // 11 //===----------------------------------------------------------------------===// 12 13 #include "MachOLinkGraphBuilder.h" 14 15 #define DEBUG_TYPE "jitlink" 16 17 static const char *CommonSectionName = "__common"; 18 19 namespace llvm { 20 namespace jitlink { 21 22 MachOLinkGraphBuilder::~MachOLinkGraphBuilder() {} 23 24 Expected<std::unique_ptr<LinkGraph>> MachOLinkGraphBuilder::buildGraph() { 25 26 // Sanity check: we only operate on relocatable objects. 27 if (!Obj.isRelocatableObject()) 28 return make_error<JITLinkError>("Object is not a relocatable MachO"); 29 30 if (auto Err = createNormalizedSections()) 31 return std::move(Err); 32 33 if (auto Err = createNormalizedSymbols()) 34 return std::move(Err); 35 36 if (auto Err = graphifyRegularSymbols()) 37 return std::move(Err); 38 39 if (auto Err = graphifySectionsWithCustomParsers()) 40 return std::move(Err); 41 42 if (auto Err = addRelocations()) 43 return std::move(Err); 44 45 return std::move(G); 46 } 47 48 MachOLinkGraphBuilder::MachOLinkGraphBuilder(const object::MachOObjectFile &Obj) 49 : Obj(Obj), 50 G(std::make_unique<LinkGraph>(Obj.getFileName(), getPointerSize(Obj), 51 getEndianness(Obj))) {} 52 53 void MachOLinkGraphBuilder::addCustomSectionParser( 54 StringRef SectionName, SectionParserFunction Parser) { 55 assert(!CustomSectionParserFunctions.count(SectionName) && 56 "Custom parser for this section already exists"); 57 CustomSectionParserFunctions[SectionName] = std::move(Parser); 58 } 59 60 Linkage MachOLinkGraphBuilder::getLinkage(uint16_t Desc) { 61 if ((Desc & MachO::N_WEAK_DEF) || (Desc & MachO::N_WEAK_REF)) 62 return Linkage::Weak; 63 return Linkage::Strong; 64 } 65 66 Scope MachOLinkGraphBuilder::getScope(StringRef Name, uint8_t Type) { 67 if (Name.startswith("l")) 68 return Scope::Local; 69 if (Type & MachO::N_PEXT) 70 return Scope::Hidden; 71 if (Type & MachO::N_EXT) 72 return Scope::Default; 73 return Scope::Local; 74 } 75 76 bool MachOLinkGraphBuilder::isAltEntry(const NormalizedSymbol &NSym) { 77 return NSym.Desc & MachO::N_ALT_ENTRY; 78 } 79 80 unsigned 81 MachOLinkGraphBuilder::getPointerSize(const object::MachOObjectFile &Obj) { 82 return Obj.is64Bit() ? 8 : 4; 83 } 84 85 support::endianness 86 MachOLinkGraphBuilder::getEndianness(const object::MachOObjectFile &Obj) { 87 return Obj.isLittleEndian() ? support::little : support::big; 88 } 89 90 Section &MachOLinkGraphBuilder::getCommonSection() { 91 if (!CommonSection) { 92 auto Prot = static_cast<sys::Memory::ProtectionFlags>( 93 sys::Memory::MF_READ | sys::Memory::MF_WRITE); 94 CommonSection = &G->createSection(CommonSectionName, Prot); 95 } 96 return *CommonSection; 97 } 98 99 Error MachOLinkGraphBuilder::createNormalizedSections() { 100 // Build normalized sections. Verifies that section data is in-range (for 101 // sections with content) and that address ranges are non-overlapping. 102 103 LLVM_DEBUG(dbgs() << "Creating normalized sections...\n"); 104 105 for (auto &SecRef : Obj.sections()) { 106 NormalizedSection NSec; 107 uint32_t DataOffset = 0; 108 109 auto SecIndex = Obj.getSectionIndex(SecRef.getRawDataRefImpl()); 110 111 auto Name = SecRef.getName(); 112 if (!Name) 113 return Name.takeError(); 114 115 if (Obj.is64Bit()) { 116 const MachO::section_64 &Sec64 = 117 Obj.getSection64(SecRef.getRawDataRefImpl()); 118 119 NSec.Address = Sec64.addr; 120 NSec.Size = Sec64.size; 121 NSec.Alignment = 1ULL << Sec64.align; 122 NSec.Flags = Sec64.flags; 123 DataOffset = Sec64.offset; 124 } else { 125 const MachO::section &Sec32 = Obj.getSection(SecRef.getRawDataRefImpl()); 126 NSec.Address = Sec32.addr; 127 NSec.Size = Sec32.size; 128 NSec.Alignment = 1ULL << Sec32.align; 129 NSec.Flags = Sec32.flags; 130 DataOffset = Sec32.offset; 131 } 132 133 LLVM_DEBUG({ 134 dbgs() << " " << *Name << ": " << formatv("{0:x16}", NSec.Address) 135 << " -- " << formatv("{0:x16}", NSec.Address + NSec.Size) 136 << ", align: " << NSec.Alignment << ", index: " << SecIndex 137 << "\n"; 138 }); 139 140 // Get the section data if any. 141 { 142 unsigned SectionType = NSec.Flags & MachO::SECTION_TYPE; 143 if (SectionType != MachO::S_ZEROFILL && 144 SectionType != MachO::S_GB_ZEROFILL) { 145 146 if (DataOffset + NSec.Size > Obj.getData().size()) 147 return make_error<JITLinkError>( 148 "Section data extends past end of file"); 149 150 NSec.Data = Obj.getData().data() + DataOffset; 151 } 152 } 153 154 // Get prot flags. 155 // FIXME: Make sure this test is correct (it's probably missing cases 156 // as-is). 157 sys::Memory::ProtectionFlags Prot; 158 if (NSec.Flags & MachO::S_ATTR_PURE_INSTRUCTIONS) 159 Prot = static_cast<sys::Memory::ProtectionFlags>(sys::Memory::MF_READ | 160 sys::Memory::MF_EXEC); 161 else 162 Prot = static_cast<sys::Memory::ProtectionFlags>(sys::Memory::MF_READ | 163 sys::Memory::MF_WRITE); 164 165 NSec.GraphSection = &G->createSection(*Name, Prot); 166 IndexToSection.insert(std::make_pair(SecIndex, std::move(NSec))); 167 } 168 169 std::vector<NormalizedSection *> Sections; 170 Sections.reserve(IndexToSection.size()); 171 for (auto &KV : IndexToSection) 172 Sections.push_back(&KV.second); 173 174 // If we didn't end up creating any sections then bail out. The code below 175 // assumes that we have at least one section. 176 if (Sections.empty()) 177 return Error::success(); 178 179 llvm::sort(Sections, 180 [](const NormalizedSection *LHS, const NormalizedSection *RHS) { 181 assert(LHS && RHS && "Null section?"); 182 if (LHS->Address != RHS->Address) 183 return LHS->Address < RHS->Address; 184 return LHS->Size < RHS->Size; 185 }); 186 187 for (unsigned I = 0, E = Sections.size() - 1; I != E; ++I) { 188 auto &Cur = *Sections[I]; 189 auto &Next = *Sections[I + 1]; 190 if (Next.Address < Cur.Address + Cur.Size) 191 return make_error<JITLinkError>( 192 "Address range for section " + Cur.GraphSection->getName() + 193 formatv(" [ {0:x16} -- {1:x16} ] ", Cur.Address, 194 Cur.Address + Cur.Size) + 195 "overlaps " + 196 formatv(" [ {0:x16} -- {1:x16} ] ", Next.Address, 197 Next.Address + Next.Size)); 198 } 199 200 return Error::success(); 201 } 202 203 Error MachOLinkGraphBuilder::createNormalizedSymbols() { 204 LLVM_DEBUG(dbgs() << "Creating normalized symbols...\n"); 205 206 for (auto &SymRef : Obj.symbols()) { 207 208 unsigned SymbolIndex = Obj.getSymbolIndex(SymRef.getRawDataRefImpl()); 209 uint64_t Value; 210 uint32_t NStrX; 211 uint8_t Type; 212 uint8_t Sect; 213 uint16_t Desc; 214 215 if (Obj.is64Bit()) { 216 const MachO::nlist_64 &NL64 = 217 Obj.getSymbol64TableEntry(SymRef.getRawDataRefImpl()); 218 Value = NL64.n_value; 219 NStrX = NL64.n_strx; 220 Type = NL64.n_type; 221 Sect = NL64.n_sect; 222 Desc = NL64.n_desc; 223 } else { 224 const MachO::nlist &NL32 = 225 Obj.getSymbolTableEntry(SymRef.getRawDataRefImpl()); 226 Value = NL32.n_value; 227 NStrX = NL32.n_strx; 228 Type = NL32.n_type; 229 Sect = NL32.n_sect; 230 Desc = NL32.n_desc; 231 } 232 233 // Skip stabs. 234 // FIXME: Are there other symbols we should be skipping? 235 if (Type & MachO::N_STAB) 236 continue; 237 238 Optional<StringRef> Name; 239 if (NStrX) { 240 if (auto NameOrErr = SymRef.getName()) 241 Name = *NameOrErr; 242 else 243 return NameOrErr.takeError(); 244 } 245 246 LLVM_DEBUG({ 247 dbgs() << " "; 248 if (!Name) 249 dbgs() << "<anonymous symbol>"; 250 else 251 dbgs() << *Name; 252 dbgs() << ": value = " << formatv("{0:x16}", Value) 253 << ", type = " << formatv("{0:x2}", Type) 254 << ", desc = " << formatv("{0:x4}", Desc) << ", sect = "; 255 if (Sect) 256 dbgs() << static_cast<unsigned>(Sect - 1); 257 else 258 dbgs() << "none"; 259 dbgs() << "\n"; 260 }); 261 262 // If this symbol has a section, sanity check that the addresses line up. 263 NormalizedSection *NSec = nullptr; 264 if (Sect != 0) { 265 if (auto NSecOrErr = findSectionByIndex(Sect - 1)) 266 NSec = &*NSecOrErr; 267 else 268 return NSecOrErr.takeError(); 269 270 if (Value < NSec->Address || Value > NSec->Address + NSec->Size) 271 return make_error<JITLinkError>("Symbol address does not fall within " 272 "section"); 273 } 274 275 IndexToSymbol[SymbolIndex] = 276 &createNormalizedSymbol(*Name, Value, Type, Sect, Desc, 277 getLinkage(Type), getScope(*Name, Type)); 278 } 279 280 return Error::success(); 281 } 282 283 void MachOLinkGraphBuilder::addSectionStartSymAndBlock( 284 Section &GraphSec, uint64_t Address, const char *Data, uint64_t Size, 285 uint32_t Alignment, bool IsLive) { 286 Block &B = 287 Data ? G->createContentBlock(GraphSec, StringRef(Data, Size), Address, 288 Alignment, 0) 289 : G->createZeroFillBlock(GraphSec, Size, Address, Alignment, 0); 290 auto &Sym = G->addAnonymousSymbol(B, 0, Size, false, IsLive); 291 assert(!AddrToCanonicalSymbol.count(Sym.getAddress()) && 292 "Anonymous block start symbol clashes with existing symbol address"); 293 AddrToCanonicalSymbol[Sym.getAddress()] = &Sym; 294 } 295 296 Error MachOLinkGraphBuilder::graphifyRegularSymbols() { 297 298 LLVM_DEBUG(dbgs() << "Creating graph symbols...\n"); 299 300 /// We only have 256 section indexes: Use a vector rather than a map. 301 std::vector<std::vector<NormalizedSymbol *>> SecIndexToSymbols; 302 SecIndexToSymbols.resize(256); 303 304 // Create commons, externs, and absolutes, and partition all other symbols by 305 // section. 306 for (auto &KV : IndexToSymbol) { 307 auto &NSym = *KV.second; 308 309 switch (NSym.Type & MachO::N_TYPE) { 310 case MachO::N_UNDF: 311 if (NSym.Value) { 312 if (!NSym.Name) 313 return make_error<JITLinkError>("Anonymous common symbol at index " + 314 Twine(KV.first)); 315 NSym.GraphSymbol = &G->addCommonSymbol( 316 *NSym.Name, NSym.S, getCommonSection(), 0, NSym.Value, 317 1ull << MachO::GET_COMM_ALIGN(NSym.Desc), 318 NSym.Desc & MachO::N_NO_DEAD_STRIP); 319 } else { 320 if (!NSym.Name) 321 return make_error<JITLinkError>("Anonymous external symbol at " 322 "index " + 323 Twine(KV.first)); 324 NSym.GraphSymbol = &G->addExternalSymbol( 325 *NSym.Name, 0, 326 NSym.Desc & MachO::N_WEAK_REF ? Linkage::Weak : Linkage::Strong); 327 } 328 break; 329 case MachO::N_ABS: 330 if (!NSym.Name) 331 return make_error<JITLinkError>("Anonymous absolute symbol at index " + 332 Twine(KV.first)); 333 NSym.GraphSymbol = &G->addAbsoluteSymbol( 334 *NSym.Name, NSym.Value, 0, Linkage::Strong, Scope::Default, 335 NSym.Desc & MachO::N_NO_DEAD_STRIP); 336 break; 337 case MachO::N_SECT: 338 SecIndexToSymbols[NSym.Sect - 1].push_back(&NSym); 339 break; 340 case MachO::N_PBUD: 341 return make_error<JITLinkError>( 342 "Unupported N_PBUD symbol " + 343 (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) + 344 " at index " + Twine(KV.first)); 345 case MachO::N_INDR: 346 return make_error<JITLinkError>( 347 "Unupported N_INDR symbol " + 348 (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) + 349 " at index " + Twine(KV.first)); 350 default: 351 return make_error<JITLinkError>( 352 "Unrecognized symbol type " + Twine(NSym.Type & MachO::N_TYPE) + 353 " for symbol " + 354 (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) + 355 " at index " + Twine(KV.first)); 356 } 357 } 358 359 // Loop over sections performing regular graphification for those that 360 // don't have custom parsers. 361 for (auto &KV : IndexToSection) { 362 auto SecIndex = KV.first; 363 auto &NSec = KV.second; 364 365 // Skip sections with custom parsers. 366 if (CustomSectionParserFunctions.count(NSec.GraphSection->getName())) { 367 LLVM_DEBUG({ 368 dbgs() << " Skipping section " << NSec.GraphSection->getName() 369 << " as it has a custom parser.\n"; 370 }); 371 continue; 372 } else 373 LLVM_DEBUG({ 374 dbgs() << " Processing section " << NSec.GraphSection->getName() 375 << "...\n"; 376 }); 377 378 bool SectionIsNoDeadStrip = NSec.Flags & MachO::S_ATTR_NO_DEAD_STRIP; 379 bool SectionIsText = NSec.Flags & MachO::S_ATTR_PURE_INSTRUCTIONS; 380 381 auto &SecNSymStack = SecIndexToSymbols[SecIndex]; 382 383 // If this section is non-empty but there are no symbols covering it then 384 // create one block and anonymous symbol to cover the entire section. 385 if (SecNSymStack.empty()) { 386 if (NSec.Size > 0) { 387 LLVM_DEBUG({ 388 dbgs() << " Section non-empty, but contains no symbols. " 389 "Creating anonymous block to cover " 390 << formatv("{0:x16}", NSec.Address) << " -- " 391 << formatv("{0:x16}", NSec.Address + NSec.Size) << "\n"; 392 }); 393 addSectionStartSymAndBlock(*NSec.GraphSection, NSec.Address, NSec.Data, 394 NSec.Size, NSec.Alignment, 395 SectionIsNoDeadStrip); 396 } else 397 LLVM_DEBUG({ 398 dbgs() << " Section empty and contains no symbols. Skipping.\n"; 399 }); 400 continue; 401 } 402 403 // Sort the symbol stack in by address, alt-entry status, scope, and name. 404 // We sort in reverse order so that symbols will be visited in the right 405 // order when we pop off the stack below. 406 llvm::sort(SecNSymStack, [](const NormalizedSymbol *LHS, 407 const NormalizedSymbol *RHS) { 408 if (LHS->Value != RHS->Value) 409 return LHS->Value > RHS->Value; 410 if (isAltEntry(*LHS) != isAltEntry(*RHS)) 411 return isAltEntry(*RHS); 412 if (LHS->S != RHS->S) 413 return static_cast<uint8_t>(LHS->S) < static_cast<uint8_t>(RHS->S); 414 return LHS->Name < RHS->Name; 415 }); 416 417 // The first symbol in a section can not be an alt-entry symbol. 418 if (!SecNSymStack.empty() && isAltEntry(*SecNSymStack.back())) 419 return make_error<JITLinkError>( 420 "First symbol in " + NSec.GraphSection->getName() + " is alt-entry"); 421 422 // If the section is non-empty but there is no symbol covering the start 423 // address then add an anonymous one. 424 if (SecNSymStack.back()->Value != NSec.Address) { 425 auto AnonBlockSize = SecNSymStack.back()->Value - NSec.Address; 426 LLVM_DEBUG({ 427 dbgs() << " Section start not covered by symbol. " 428 << "Creating anonymous block to cover [ " 429 << formatv("{0:x16}", NSec.Address) << " -- " 430 << formatv("{0:x16}", NSec.Address + AnonBlockSize) << " ]\n"; 431 }); 432 addSectionStartSymAndBlock(*NSec.GraphSection, NSec.Address, NSec.Data, 433 AnonBlockSize, NSec.Alignment, 434 SectionIsNoDeadStrip); 435 } 436 437 // Visit section symbols in order by popping off the reverse-sorted stack, 438 // building blocks for each alt-entry chain and creating symbols as we go. 439 while (!SecNSymStack.empty()) { 440 SmallVector<NormalizedSymbol *, 8> BlockSyms; 441 442 BlockSyms.push_back(SecNSymStack.back()); 443 SecNSymStack.pop_back(); 444 while (!SecNSymStack.empty() && 445 (isAltEntry(*SecNSymStack.back()) || 446 SecNSymStack.back()->Value == BlockSyms.back()->Value)) { 447 BlockSyms.push_back(SecNSymStack.back()); 448 SecNSymStack.pop_back(); 449 } 450 451 // BlockNSyms now contains the block symbols in reverse canonical order. 452 JITTargetAddress BlockStart = BlockSyms.front()->Value; 453 JITTargetAddress BlockEnd = SecNSymStack.empty() 454 ? NSec.Address + NSec.Size 455 : SecNSymStack.back()->Value; 456 JITTargetAddress BlockOffset = BlockStart - NSec.Address; 457 JITTargetAddress BlockSize = BlockEnd - BlockStart; 458 459 LLVM_DEBUG({ 460 dbgs() << " Creating block for " << formatv("{0:x16}", BlockStart) 461 << " -- " << formatv("{0:x16}", BlockEnd) << ": " 462 << NSec.GraphSection->getName() << " + " 463 << formatv("{0:x16}", BlockOffset) << " with " 464 << BlockSyms.size() << " symbol(s)...\n"; 465 }); 466 467 Block &B = 468 NSec.Data 469 ? G->createContentBlock( 470 *NSec.GraphSection, 471 StringRef(NSec.Data + BlockOffset, BlockSize), BlockStart, 472 NSec.Alignment, BlockStart % NSec.Alignment) 473 : G->createZeroFillBlock(*NSec.GraphSection, BlockSize, 474 BlockStart, NSec.Alignment, 475 BlockStart % NSec.Alignment); 476 477 Optional<JITTargetAddress> LastCanonicalAddr; 478 JITTargetAddress SymEnd = BlockEnd; 479 while (!BlockSyms.empty()) { 480 auto &NSym = *BlockSyms.back(); 481 BlockSyms.pop_back(); 482 483 bool SymLive = 484 (NSym.Desc & MachO::N_NO_DEAD_STRIP) || SectionIsNoDeadStrip; 485 486 LLVM_DEBUG({ 487 dbgs() << " " << formatv("{0:x16}", NSym.Value) << " -- " 488 << formatv("{0:x16}", SymEnd) << ": "; 489 if (!NSym.Name) 490 dbgs() << "<anonymous symbol>"; 491 else 492 dbgs() << NSym.Name; 493 if (SymLive) 494 dbgs() << " [no-dead-strip]"; 495 if (LastCanonicalAddr == NSym.Value) 496 dbgs() << " [non-canonical]"; 497 dbgs() << "\n"; 498 }); 499 500 auto &Sym = 501 NSym.Name 502 ? G->addDefinedSymbol(B, NSym.Value - BlockStart, *NSym.Name, 503 SymEnd - NSym.Value, NSym.L, NSym.S, 504 SectionIsText, SymLive) 505 : G->addAnonymousSymbol(B, NSym.Value - BlockStart, 506 SymEnd - NSym.Value, SectionIsText, 507 SymLive); 508 NSym.GraphSymbol = &Sym; 509 if (LastCanonicalAddr != Sym.getAddress()) { 510 if (LastCanonicalAddr) 511 SymEnd = *LastCanonicalAddr; 512 LastCanonicalAddr = Sym.getAddress(); 513 setCanonicalSymbol(Sym); 514 } 515 } 516 } 517 } 518 519 return Error::success(); 520 } 521 522 Error MachOLinkGraphBuilder::graphifySectionsWithCustomParsers() { 523 // Graphify special sections. 524 for (auto &KV : IndexToSection) { 525 auto &NSec = KV.second; 526 527 auto HI = CustomSectionParserFunctions.find(NSec.GraphSection->getName()); 528 if (HI != CustomSectionParserFunctions.end()) { 529 auto &Parse = HI->second; 530 if (auto Err = Parse(NSec)) 531 return Err; 532 } 533 } 534 535 return Error::success(); 536 } 537 538 } // end namespace jitlink 539 } // end namespace llvm 540