llvm/lib/ExecutionEngine/JITLink/MachOLinkGraphBuilder.cpp

   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 building code.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "MachOLinkGraphBuilder.h"
  14 #include <optional>
  15
  16 #define DEBUG_TYPE "jitlink"
  17
  18 static const char *CommonSectionName = "__common";
  19
  20 namespace llvm {
  21 namespace jitlink {
  22
  23 MachOLinkGraphBuilder::~MachOLinkGraphBuilder() = default;
  24
  25 Expected<std::unique_ptr<LinkGraph>> MachOLinkGraphBuilder::buildGraph() {
  26
  27   // We only operate on relocatable objects.
  28   if (!Obj.isRelocatableObject())
  29     return make_error<JITLinkError>("Object is not a relocatable MachO");
  30
  31   if (auto Err = createNormalizedSections())
  32     return std::move(Err);
  33
  34   if (auto Err = createNormalizedSymbols())
  35     return std::move(Err);
  36
  37   if (auto Err = graphifyRegularSymbols())
  38     return std::move(Err);
  39
  40   if (auto Err = graphifySectionsWithCustomParsers())
  41     return std::move(Err);
  42
  43   if (auto Err = addRelocations())
  44     return std::move(Err);
  45
  46   return std::move(G);
  47 }
  48
  49 MachOLinkGraphBuilder::MachOLinkGraphBuilder(
  50     const object::MachOObjectFile &Obj, Triple TT, SubtargetFeatures Features,
  51     LinkGraph::GetEdgeKindNameFunction GetEdgeKindName)
  52     : Obj(Obj),
  53       G(std::make_unique<LinkGraph>(std::string(Obj.getFileName()),
  54                                     std::move(TT), std::move(Features),
  55                                     getPointerSize(Obj), getEndianness(Obj),
  56                                     std::move(GetEdgeKindName))) {
  57   auto &MachHeader = Obj.getHeader64();
  58   SubsectionsViaSymbols = MachHeader.flags & MachO::MH_SUBSECTIONS_VIA_SYMBOLS;
  59 }
  60
  61 void MachOLinkGraphBuilder::addCustomSectionParser(
  62     StringRef SectionName, SectionParserFunction Parser) {
  63   assert(!CustomSectionParserFunctions.count(SectionName) &&
  64          "Custom parser for this section already exists");
  65   CustomSectionParserFunctions[SectionName] = std::move(Parser);
  66 }
  67
  68 Linkage MachOLinkGraphBuilder::getLinkage(uint16_t Desc) {
  69   if ((Desc & MachO::N_WEAK_DEF) || (Desc & MachO::N_WEAK_REF))
  70     return Linkage::Weak;
  71   return Linkage::Strong;
  72 }
  73
  74 Scope MachOLinkGraphBuilder::getScope(StringRef Name, uint8_t Type) {
  75   if (Type & MachO::N_EXT) {
  76     if ((Type & MachO::N_PEXT) || Name.starts_with("l"))
  77       return Scope::Hidden;
  78     else
  79       return Scope::Default;
  80   }
  81   return Scope::Local;
  82 }
  83
  84 bool MachOLinkGraphBuilder::isAltEntry(const NormalizedSymbol &NSym) {
  85   return NSym.Desc & MachO::N_ALT_ENTRY;
  86 }
  87
  88 bool MachOLinkGraphBuilder::isDebugSection(const NormalizedSection &NSec) {
  89   return (NSec.Flags & MachO::S_ATTR_DEBUG &&
  90           strcmp(NSec.SegName, "__DWARF") == 0);
  91 }
  92
  93 bool MachOLinkGraphBuilder::isZeroFillSection(const NormalizedSection &NSec) {
  94   switch (NSec.Flags & MachO::SECTION_TYPE) {
  95   case MachO::S_ZEROFILL:
  96   case MachO::S_GB_ZEROFILL:
  97   case MachO::S_THREAD_LOCAL_ZEROFILL:
  98     return true;
  99   default:
 100     return false;
 101   }
 102 }
 103
 104 unsigned
 105 MachOLinkGraphBuilder::getPointerSize(const object::MachOObjectFile &Obj) {
 106   return Obj.is64Bit() ? 8 : 4;
 107 }
 108
 109 llvm::endianness
 110 MachOLinkGraphBuilder::getEndianness(const object::MachOObjectFile &Obj) {
 111   return Obj.isLittleEndian() ? llvm::endianness::little
 112                               : llvm::endianness::big;
 113 }
 114
 115 Section &MachOLinkGraphBuilder::getCommonSection() {
 116   if (!CommonSection)
 117     CommonSection = &G->createSection(CommonSectionName,
 118                                       orc::MemProt::Read | orc::MemProt::Write);
 119   return *CommonSection;
 120 }
 121
 122 Error MachOLinkGraphBuilder::createNormalizedSections() {
 123   // Build normalized sections. Verifies that section data is in-range (for
 124   // sections with content) and that address ranges are non-overlapping.
 125
 126   LLVM_DEBUG(dbgs() << "Creating normalized sections...\n");
 127
 128   for (auto &SecRef : Obj.sections()) {
 129     NormalizedSection NSec;
 130     uint32_t DataOffset = 0;
 131
 132     auto SecIndex = Obj.getSectionIndex(SecRef.getRawDataRefImpl());
 133
 134     if (Obj.is64Bit()) {
 135       const MachO::section_64 &Sec64 =
 136           Obj.getSection64(SecRef.getRawDataRefImpl());
 137
 138       memcpy(&NSec.SectName, &Sec64.sectname, 16);
 139       NSec.SectName[16] = '\0';
 140       memcpy(&NSec.SegName, Sec64.segname, 16);
 141       NSec.SegName[16] = '\0';
 142
 143       NSec.Address = orc::ExecutorAddr(Sec64.addr);
 144       NSec.Size = Sec64.size;
 145       NSec.Alignment = 1ULL << Sec64.align;
 146       NSec.Flags = Sec64.flags;
 147       DataOffset = Sec64.offset;
 148     } else {
 149       const MachO::section &Sec32 = Obj.getSection(SecRef.getRawDataRefImpl());
 150
 151       memcpy(&NSec.SectName, &Sec32.sectname, 16);
 152       NSec.SectName[16] = '\0';
 153       memcpy(&NSec.SegName, Sec32.segname, 16);
 154       NSec.SegName[16] = '\0';
 155
 156       NSec.Address = orc::ExecutorAddr(Sec32.addr);
 157       NSec.Size = Sec32.size;
 158       NSec.Alignment = 1ULL << Sec32.align;
 159       NSec.Flags = Sec32.flags;
 160       DataOffset = Sec32.offset;
 161     }
 162
 163     LLVM_DEBUG({
 164       dbgs() << "  " << NSec.SegName << "," << NSec.SectName << ": "
 165              << formatv("{0:x16}", NSec.Address) << " -- "
 166              << formatv("{0:x16}", NSec.Address + NSec.Size)
 167              << ", align: " << NSec.Alignment << ", index: " << SecIndex
 168              << "\n";
 169     });
 170
 171     // Get the section data if any.
 172     if (!isZeroFillSection(NSec)) {
 173       if (DataOffset + NSec.Size > Obj.getData().size())
 174         return make_error<JITLinkError>(
 175             "Section data extends past end of file");
 176
 177       NSec.Data = Obj.getData().data() + DataOffset;
 178     }
 179
 180     // Get prot flags.
 181     // FIXME: Make sure this test is correct (it's probably missing cases
 182     // as-is).
 183     orc::MemProt Prot;
 184     if (NSec.Flags & MachO::S_ATTR_PURE_INSTRUCTIONS)
 185       Prot = orc::MemProt::Read | orc::MemProt::Exec;
 186     else
 187       Prot = orc::MemProt::Read | orc::MemProt::Write;
 188
 189     auto FullyQualifiedName =
 190         G->allocateContent(StringRef(NSec.SegName) + "," + NSec.SectName);
 191     NSec.GraphSection = &G->createSection(
 192         StringRef(FullyQualifiedName.data(), FullyQualifiedName.size()), Prot);
 193
 194     // TODO: Are there any other criteria for NoAlloc lifetime?
 195     if (NSec.Flags & MachO::S_ATTR_DEBUG)
 196       NSec.GraphSection->setMemLifetime(orc::MemLifetime::NoAlloc);
 197
 198     IndexToSection.insert(std::make_pair(SecIndex, std::move(NSec)));
 199   }
 200
 201   std::vector<NormalizedSection *> Sections;
 202   Sections.reserve(IndexToSection.size());
 203   for (auto &KV : IndexToSection)
 204     Sections.push_back(&KV.second);
 205
 206   // If we didn't end up creating any sections then bail out. The code below
 207   // assumes that we have at least one section.
 208   if (Sections.empty())
 209     return Error::success();
 210
 211   llvm::sort(Sections,
 212              [](const NormalizedSection *LHS, const NormalizedSection *RHS) {
 213                assert(LHS && RHS && "Null section?");
 214                if (LHS->Address != RHS->Address)
 215                  return LHS->Address < RHS->Address;
 216                return LHS->Size < RHS->Size;
 217              });
 218
 219   for (unsigned I = 0, E = Sections.size() - 1; I != E; ++I) {
 220     auto &Cur = *Sections[I];
 221     auto &Next = *Sections[I + 1];
 222     if (Next.Address < Cur.Address + Cur.Size)
 223       return make_error<JITLinkError>(
 224           "Address range for section " +
 225           formatv("\"{0}/{1}\" [ {2:x16} -- {3:x16} ] ", Cur.SegName,
 226                   Cur.SectName, Cur.Address, Cur.Address + Cur.Size) +
 227           "overlaps section \"" + Next.SegName + "/" + Next.SectName + "\"" +
 228           formatv("\"{0}/{1}\" [ {2:x16} -- {3:x16} ] ", Next.SegName,
 229                   Next.SectName, Next.Address, Next.Address + Next.Size));
 230   }
 231
 232   return Error::success();
 233 }
 234
 235 Error MachOLinkGraphBuilder::createNormalizedSymbols() {
 236   LLVM_DEBUG(dbgs() << "Creating normalized symbols...\n");
 237
 238   for (auto &SymRef : Obj.symbols()) {
 239
 240     unsigned SymbolIndex = Obj.getSymbolIndex(SymRef.getRawDataRefImpl());
 241     uint64_t Value;
 242     uint32_t NStrX;
 243     uint8_t Type;
 244     uint8_t Sect;
 245     uint16_t Desc;
 246
 247     if (Obj.is64Bit()) {
 248       const MachO::nlist_64 &NL64 =
 249           Obj.getSymbol64TableEntry(SymRef.getRawDataRefImpl());
 250       Value = NL64.n_value;
 251       NStrX = NL64.n_strx;
 252       Type = NL64.n_type;
 253       Sect = NL64.n_sect;
 254       Desc = NL64.n_desc;
 255     } else {
 256       const MachO::nlist &NL32 =
 257           Obj.getSymbolTableEntry(SymRef.getRawDataRefImpl());
 258       Value = NL32.n_value;
 259       NStrX = NL32.n_strx;
 260       Type = NL32.n_type;
 261       Sect = NL32.n_sect;
 262       Desc = NL32.n_desc;
 263     }
 264
 265     // Skip stabs.
 266     // FIXME: Are there other symbols we should be skipping?
 267     if (Type & MachO::N_STAB)
 268       continue;
 269
 270     std::optional<StringRef> Name;
 271     if (NStrX) {
 272       if (auto NameOrErr = SymRef.getName())
 273         Name = *NameOrErr;
 274       else
 275         return NameOrErr.takeError();
 276     } else if (Type & MachO::N_EXT)
 277       return make_error<JITLinkError>("Symbol at index " +
 278                                       formatv("{0}", SymbolIndex) +
 279                                       " has no name (string table index 0), "
 280                                       "but N_EXT bit is set");
 281
 282     LLVM_DEBUG({
 283       dbgs() << "  ";
 284       if (!Name)
 285         dbgs() << "<anonymous symbol>";
 286       else
 287         dbgs() << *Name;
 288       dbgs() << ": value = " << formatv("{0:x16}", Value)
 289              << ", type = " << formatv("{0:x2}", Type)
 290              << ", desc = " << formatv("{0:x4}", Desc) << ", sect = ";
 291       if (Sect)
 292         dbgs() << static_cast<unsigned>(Sect - 1);
 293       else
 294         dbgs() << "none";
 295       dbgs() << "\n";
 296     });
 297
 298     // If this symbol has a section, verify that the addresses line up.
 299     if (Sect != 0) {
 300       auto NSec = findSectionByIndex(Sect - 1);
 301       if (!NSec)
 302         return NSec.takeError();
 303
 304       if (orc::ExecutorAddr(Value) < NSec->Address ||
 305           orc::ExecutorAddr(Value) > NSec->Address + NSec->Size)
 306         return make_error<JITLinkError>("Address " + formatv("{0:x}", Value) +
 307                                         " for symbol " + *Name +
 308                                         " does not fall within section");
 309
 310       if (!NSec->GraphSection) {
 311         LLVM_DEBUG({
 312           dbgs() << "  Skipping: Symbol is in section " << NSec->SegName << "/"
 313                  << NSec->SectName
 314                  << " which has no associated graph section.\n";
 315         });
 316         continue;
 317       }
 318     }
 319
 320     IndexToSymbol[SymbolIndex] =
 321         &createNormalizedSymbol(*Name, Value, Type, Sect, Desc,
 322                                 getLinkage(Desc), getScope(*Name, Type));
 323   }
 324
 325   return Error::success();
 326 }
 327
 328 void MachOLinkGraphBuilder::addSectionStartSymAndBlock(
 329     unsigned SecIndex, Section &GraphSec, orc::ExecutorAddr Address,
 330     const char *Data, orc::ExecutorAddrDiff Size, uint32_t Alignment,
 331     bool IsLive) {
 332   Block &B =
 333       Data ? G->createContentBlock(GraphSec, ArrayRef<char>(Data, Size),
 334                                    Address, Alignment, 0)
 335            : G->createZeroFillBlock(GraphSec, Size, Address, Alignment, 0);
 336   auto &Sym = G->addAnonymousSymbol(B, 0, Size, false, IsLive);
 337   auto SecI = IndexToSection.find(SecIndex);
 338   assert(SecI != IndexToSection.end() && "SecIndex invalid");
 339   auto &NSec = SecI->second;
 340   assert(!NSec.CanonicalSymbols.count(Sym.getAddress()) &&
 341          "Anonymous block start symbol clashes with existing symbol address");
 342   NSec.CanonicalSymbols[Sym.getAddress()] = &Sym;
 343 }
 344
 345 Error MachOLinkGraphBuilder::graphifyRegularSymbols() {
 346
 347   LLVM_DEBUG(dbgs() << "Creating graph symbols...\n");
 348
 349   /// We only have 256 section indexes: Use a vector rather than a map.
 350   std::vector<std::vector<NormalizedSymbol *>> SecIndexToSymbols;
 351   SecIndexToSymbols.resize(256);
 352
 353   // Create commons, externs, and absolutes, and partition all other symbols by
 354   // section.
 355   for (auto &KV : IndexToSymbol) {
 356     auto &NSym = *KV.second;
 357
 358     switch (NSym.Type & MachO::N_TYPE) {
 359     case MachO::N_UNDF:
 360       if (NSym.Value) {
 361         if (!NSym.Name)
 362           return make_error<JITLinkError>("Anonymous common symbol at index " +
 363                                           Twine(KV.first));
 364         NSym.GraphSymbol = &G->addDefinedSymbol(
 365             G->createZeroFillBlock(getCommonSection(),
 366                                    orc::ExecutorAddrDiff(NSym.Value),
 367                                    orc::ExecutorAddr(),
 368                                    1ull << MachO::GET_COMM_ALIGN(NSym.Desc), 0),
 369             0, *NSym.Name, orc::ExecutorAddrDiff(NSym.Value), Linkage::Strong,
 370             NSym.S, false, NSym.Desc & MachO::N_NO_DEAD_STRIP);
 371       } else {
 372         if (!NSym.Name)
 373           return make_error<JITLinkError>("Anonymous external symbol at "
 374                                           "index " +
 375                                           Twine(KV.first));
 376         NSym.GraphSymbol = &G->addExternalSymbol(
 377             *NSym.Name, 0, (NSym.Desc & MachO::N_WEAK_REF) != 0);
 378       }
 379       break;
 380     case MachO::N_ABS:
 381       if (!NSym.Name)
 382         return make_error<JITLinkError>("Anonymous absolute symbol at index " +
 383                                         Twine(KV.first));
 384       NSym.GraphSymbol = &G->addAbsoluteSymbol(
 385           *NSym.Name, orc::ExecutorAddr(NSym.Value), 0, Linkage::Strong,
 386           getScope(*NSym.Name, NSym.Type), NSym.Desc & MachO::N_NO_DEAD_STRIP);
 387       break;
 388     case MachO::N_SECT:
 389       SecIndexToSymbols[NSym.Sect - 1].push_back(&NSym);
 390       break;
 391     case MachO::N_PBUD:
 392       return make_error<JITLinkError>(
 393           "Unupported N_PBUD symbol " +
 394           (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) +
 395           " at index " + Twine(KV.first));
 396     case MachO::N_INDR:
 397       return make_error<JITLinkError>(
 398           "Unupported N_INDR symbol " +
 399           (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) +
 400           " at index " + Twine(KV.first));
 401     default:
 402       return make_error<JITLinkError>(
 403           "Unrecognized symbol type " + Twine(NSym.Type & MachO::N_TYPE) +
 404           " for symbol " +
 405           (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) +
 406           " at index " + Twine(KV.first));
 407     }
 408   }
 409
 410   // Loop over sections performing regular graphification for those that
 411   // don't have custom parsers.
 412   for (auto &KV : IndexToSection) {
 413     auto SecIndex = KV.first;
 414     auto &NSec = KV.second;
 415
 416     if (!NSec.GraphSection) {
 417       LLVM_DEBUG({
 418         dbgs() << "  " << NSec.SegName << "/" << NSec.SectName
 419                << " has no graph section. Skipping.\n";
 420       });
 421       continue;
 422     }
 423
 424     // Skip sections with custom parsers.
 425     if (CustomSectionParserFunctions.count(NSec.GraphSection->getName())) {
 426       LLVM_DEBUG({
 427         dbgs() << "  Skipping section " << NSec.GraphSection->getName()
 428                << " as it has a custom parser.\n";
 429       });
 430       continue;
 431     } else if ((NSec.Flags & MachO::SECTION_TYPE) ==
 432                MachO::S_CSTRING_LITERALS) {
 433       if (auto Err = graphifyCStringSection(
 434               NSec, std::move(SecIndexToSymbols[SecIndex])))
 435         return Err;
 436       continue;
 437     } else
 438       LLVM_DEBUG({
 439         dbgs() << "  Graphifying regular section "
 440                << NSec.GraphSection->getName() << "...\n";
 441       });
 442
 443     bool SectionIsNoDeadStrip = NSec.Flags & MachO::S_ATTR_NO_DEAD_STRIP;
 444     bool SectionIsText = NSec.Flags & MachO::S_ATTR_PURE_INSTRUCTIONS;
 445
 446     auto &SecNSymStack = SecIndexToSymbols[SecIndex];
 447
 448     // If this section is non-empty but there are no symbols covering it then
 449     // create one block and anonymous symbol to cover the entire section.
 450     if (SecNSymStack.empty()) {
 451       if (NSec.Size > 0) {
 452         LLVM_DEBUG({
 453           dbgs() << "    Section non-empty, but contains no symbols. "
 454                     "Creating anonymous block to cover "
 455                  << formatv("{0:x16}", NSec.Address) << " -- "
 456                  << formatv("{0:x16}", NSec.Address + NSec.Size) << "\n";
 457         });
 458         addSectionStartSymAndBlock(SecIndex, *NSec.GraphSection, NSec.Address,
 459                                    NSec.Data, NSec.Size, NSec.Alignment,
 460                                    SectionIsNoDeadStrip);
 461       } else
 462         LLVM_DEBUG({
 463           dbgs() << "    Section empty and contains no symbols. Skipping.\n";
 464         });
 465       continue;
 466     }
 467
 468     // Sort the symbol stack in by address, alt-entry status, scope, and name.
 469     // We sort in reverse order so that symbols will be visited in the right
 470     // order when we pop off the stack below.
 471     llvm::sort(SecNSymStack, [](const NormalizedSymbol *LHS,
 472                                 const NormalizedSymbol *RHS) {
 473       if (LHS->Value != RHS->Value)
 474         return LHS->Value > RHS->Value;
 475       if (isAltEntry(*LHS) != isAltEntry(*RHS))
 476         return isAltEntry(*RHS);
 477       if (LHS->S != RHS->S)
 478         return static_cast<uint8_t>(LHS->S) < static_cast<uint8_t>(RHS->S);
 479       return LHS->Name < RHS->Name;
 480     });
 481
 482     // The first symbol in a section can not be an alt-entry symbol.
 483     if (!SecNSymStack.empty() && isAltEntry(*SecNSymStack.back()))
 484       return make_error<JITLinkError>(
 485           "First symbol in " + NSec.GraphSection->getName() + " is alt-entry");
 486
 487     // If the section is non-empty but there is no symbol covering the start
 488     // address then add an anonymous one.
 489     if (orc::ExecutorAddr(SecNSymStack.back()->Value) != NSec.Address) {
 490       auto AnonBlockSize =
 491           orc::ExecutorAddr(SecNSymStack.back()->Value) - NSec.Address;
 492       LLVM_DEBUG({
 493         dbgs() << "    Section start not covered by symbol. "
 494                << "Creating anonymous block to cover [ " << NSec.Address
 495                << " -- " << (NSec.Address + AnonBlockSize) << " ]\n";
 496       });
 497       addSectionStartSymAndBlock(SecIndex, *NSec.GraphSection, NSec.Address,
 498                                  NSec.Data, AnonBlockSize, NSec.Alignment,
 499                                  SectionIsNoDeadStrip);
 500     }
 501
 502     // Visit section symbols in order by popping off the reverse-sorted stack,
 503     // building graph symbols as we go.
 504     //
 505     // If MH_SUBSECTIONS_VIA_SYMBOLS is set we'll build a block for each
 506     // alt-entry chain.
 507     //
 508     // If MH_SUBSECTIONS_VIA_SYMBOLS is not set then we'll just build one block
 509     // for the whole section.
 510     while (!SecNSymStack.empty()) {
 511       SmallVector<NormalizedSymbol *, 8> BlockSyms;
 512
 513       // Get the symbols in this alt-entry chain, or the whole section (if
 514       // !SubsectionsViaSymbols).
 515       BlockSyms.push_back(SecNSymStack.back());
 516       SecNSymStack.pop_back();
 517       while (!SecNSymStack.empty() &&
 518              (isAltEntry(*SecNSymStack.back()) ||
 519               SecNSymStack.back()->Value == BlockSyms.back()->Value ||
 520              !SubsectionsViaSymbols)) {
 521         BlockSyms.push_back(SecNSymStack.back());
 522         SecNSymStack.pop_back();
 523       }
 524
 525       // BlockNSyms now contains the block symbols in reverse canonical order.
 526       auto BlockStart = orc::ExecutorAddr(BlockSyms.front()->Value);
 527       orc::ExecutorAddr BlockEnd =
 528           SecNSymStack.empty() ? NSec.Address + NSec.Size
 529                                : orc::ExecutorAddr(SecNSymStack.back()->Value);
 530       orc::ExecutorAddrDiff BlockOffset = BlockStart - NSec.Address;
 531       orc::ExecutorAddrDiff BlockSize = BlockEnd - BlockStart;
 532
 533       LLVM_DEBUG({
 534         dbgs() << "    Creating block for " << formatv("{0:x16}", BlockStart)
 535                << " -- " << formatv("{0:x16}", BlockEnd) << ": "
 536                << NSec.GraphSection->getName() << " + "
 537                << formatv("{0:x16}", BlockOffset) << " with "
 538                << BlockSyms.size() << " symbol(s)...\n";
 539       });
 540
 541       Block &B =
 542           NSec.Data
 543               ? G->createContentBlock(
 544                     *NSec.GraphSection,
 545                     ArrayRef<char>(NSec.Data + BlockOffset, BlockSize),
 546                     BlockStart, NSec.Alignment, BlockStart % NSec.Alignment)
 547               : G->createZeroFillBlock(*NSec.GraphSection, BlockSize,
 548                                        BlockStart, NSec.Alignment,
 549                                        BlockStart % NSec.Alignment);
 550
 551       std::optional<orc::ExecutorAddr> LastCanonicalAddr;
 552       auto SymEnd = BlockEnd;
 553       while (!BlockSyms.empty()) {
 554         auto &NSym = *BlockSyms.back();
 555         BlockSyms.pop_back();
 556
 557         bool SymLive =
 558             (NSym.Desc & MachO::N_NO_DEAD_STRIP) || SectionIsNoDeadStrip;
 559
 560         auto &Sym = createStandardGraphSymbol(
 561             NSym, B, SymEnd - orc::ExecutorAddr(NSym.Value), SectionIsText,
 562             SymLive, LastCanonicalAddr != orc::ExecutorAddr(NSym.Value));
 563
 564         if (LastCanonicalAddr != Sym.getAddress()) {
 565           if (LastCanonicalAddr)
 566             SymEnd = *LastCanonicalAddr;
 567           LastCanonicalAddr = Sym.getAddress();
 568         }
 569       }
 570     }
 571   }
 572
 573   return Error::success();
 574 }
 575
 576 Symbol &MachOLinkGraphBuilder::createStandardGraphSymbol(NormalizedSymbol &NSym,
 577                                                          Block &B, size_t Size,
 578                                                          bool IsText,
 579                                                          bool IsNoDeadStrip,
 580                                                          bool IsCanonical) {
 581
 582   LLVM_DEBUG({
 583     dbgs() << "      " << formatv("{0:x16}", NSym.Value) << " -- "
 584            << formatv("{0:x16}", NSym.Value + Size) << ": ";
 585     if (!NSym.Name)
 586       dbgs() << "<anonymous symbol>";
 587     else
 588       dbgs() << NSym.Name;
 589     if (IsText)
 590       dbgs() << " [text]";
 591     if (IsNoDeadStrip)
 592       dbgs() << " [no-dead-strip]";
 593     if (!IsCanonical)
 594       dbgs() << " [non-canonical]";
 595     dbgs() << "\n";
 596   });
 597
 598   auto SymOffset = orc::ExecutorAddr(NSym.Value) - B.getAddress();
 599   auto &Sym =
 600       NSym.Name
 601           ? G->addDefinedSymbol(B, SymOffset, *NSym.Name, Size, NSym.L, NSym.S,
 602                                 IsText, IsNoDeadStrip)
 603           : G->addAnonymousSymbol(B, SymOffset, Size, IsText, IsNoDeadStrip);
 604   NSym.GraphSymbol = &Sym;
 605
 606   if (IsCanonical)
 607     setCanonicalSymbol(getSectionByIndex(NSym.Sect - 1), Sym);
 608
 609   return Sym;
 610 }
 611
 612 Error MachOLinkGraphBuilder::graphifySectionsWithCustomParsers() {
 613   // Graphify special sections.
 614   for (auto &KV : IndexToSection) {
 615     auto &NSec = KV.second;
 616
 617     // Skip non-graph sections.
 618     if (!NSec.GraphSection)
 619       continue;
 620
 621     auto HI = CustomSectionParserFunctions.find(NSec.GraphSection->getName());
 622     if (HI != CustomSectionParserFunctions.end()) {
 623       auto &Parse = HI->second;
 624       if (auto Err = Parse(NSec))
 625         return Err;
 626     }
 627   }
 628
 629   return Error::success();
 630 }
 631
 632 Error MachOLinkGraphBuilder::graphifyCStringSection(
 633     NormalizedSection &NSec, std::vector<NormalizedSymbol *> NSyms) {
 634   assert(NSec.GraphSection && "C string literal section missing graph section");
 635   assert(NSec.Data && "C string literal section has no data");
 636
 637   LLVM_DEBUG({
 638     dbgs() << "  Graphifying C-string literal section "
 639            << NSec.GraphSection->getName() << "\n";
 640   });
 641
 642   if (NSec.Data[NSec.Size - 1] != '\0')
 643     return make_error<JITLinkError>("C string literal section " +
 644                                     NSec.GraphSection->getName() +
 645                                     " does not end with null terminator");
 646
 647   /// Sort into reverse order to use as a stack.
 648   llvm::sort(NSyms,
 649              [](const NormalizedSymbol *LHS, const NormalizedSymbol *RHS) {
 650                if (LHS->Value != RHS->Value)
 651                  return LHS->Value > RHS->Value;
 652                if (LHS->L != RHS->L)
 653                  return LHS->L > RHS->L;
 654                if (LHS->S != RHS->S)
 655                  return LHS->S > RHS->S;
 656                if (RHS->Name) {
 657                  if (!LHS->Name)
 658                    return true;
 659                  return *LHS->Name > *RHS->Name;
 660                }
 661                return false;
 662              });
 663
 664   bool SectionIsNoDeadStrip = NSec.Flags & MachO::S_ATTR_NO_DEAD_STRIP;
 665   bool SectionIsText = NSec.Flags & MachO::S_ATTR_PURE_INSTRUCTIONS;
 666   orc::ExecutorAddrDiff BlockStart = 0;
 667
 668   // Scan section for null characters.
 669   for (size_t I = 0; I != NSec.Size; ++I) {
 670     if (NSec.Data[I] == '\0') {
 671       size_t BlockSize = I + 1 - BlockStart;
 672       // Create a block for this null terminated string.
 673       auto &B = G->createContentBlock(*NSec.GraphSection,
 674                                       {NSec.Data + BlockStart, BlockSize},
 675                                       NSec.Address + BlockStart, NSec.Alignment,
 676                                       BlockStart % NSec.Alignment);
 677
 678       LLVM_DEBUG({
 679         dbgs() << "    Created block " << B.getRange()
 680                << ", align = " << B.getAlignment()
 681                << ", align-ofs = " << B.getAlignmentOffset() << " for \"";
 682         for (size_t J = 0; J != std::min(B.getSize(), size_t(16)); ++J)
 683           switch (B.getContent()[J]) {
 684           case '\0': break;
 685           case '\n': dbgs() << "\\n"; break;
 686           case '\t': dbgs() << "\\t"; break;
 687           default:   dbgs() << B.getContent()[J]; break;
 688           }
 689         if (B.getSize() > 16)
 690           dbgs() << "...";
 691         dbgs() << "\"\n";
 692       });
 693
 694       // If there's no symbol at the start of this block then create one.
 695       if (NSyms.empty() ||
 696           orc::ExecutorAddr(NSyms.back()->Value) != B.getAddress()) {
 697         auto &S = G->addAnonymousSymbol(B, 0, BlockSize, false, false);
 698         setCanonicalSymbol(NSec, S);
 699         LLVM_DEBUG({
 700           dbgs() << "      Adding symbol for c-string block " << B.getRange()
 701                  << ": <anonymous symbol> at offset 0\n";
 702         });
 703       }
 704
 705       // Process any remaining symbols that point into this block.
 706       auto LastCanonicalAddr = B.getAddress() + BlockSize;
 707       while (!NSyms.empty() && orc::ExecutorAddr(NSyms.back()->Value) <
 708                                    B.getAddress() + BlockSize) {
 709         auto &NSym = *NSyms.back();
 710         size_t SymSize = (B.getAddress() + BlockSize) -
 711                          orc::ExecutorAddr(NSyms.back()->Value);
 712         bool SymLive =
 713             (NSym.Desc & MachO::N_NO_DEAD_STRIP) || SectionIsNoDeadStrip;
 714
 715         bool IsCanonical = false;
 716         if (LastCanonicalAddr != orc::ExecutorAddr(NSym.Value)) {
 717           IsCanonical = true;
 718           LastCanonicalAddr = orc::ExecutorAddr(NSym.Value);
 719         }
 720
 721         auto &Sym = createStandardGraphSymbol(NSym, B, SymSize, SectionIsText,
 722                                               SymLive, IsCanonical);
 723         (void)Sym;
 724         LLVM_DEBUG({
 725           dbgs() << "      Adding symbol for c-string block " << B.getRange()
 726                  << ": "
 727                  << (Sym.hasName() ? Sym.getName() : "<anonymous symbol>")
 728                  << " at offset " << formatv("{0:x}", Sym.getOffset()) << "\n";
 729         });
 730
 731         NSyms.pop_back();
 732       }
 733
 734       BlockStart += BlockSize;
 735     }
 736   }
 737
 738   assert(llvm::all_of(NSec.GraphSection->blocks(),
 739                       [](Block *B) { return isCStringBlock(*B); }) &&
 740          "All blocks in section should hold single c-strings");
 741
 742   return Error::success();
 743 }
 744
 745 Error CompactUnwindSplitter::operator()(LinkGraph &G) {
 746   auto *CUSec = G.findSectionByName(CompactUnwindSectionName);
 747   if (!CUSec)
 748     return Error::success();
 749
 750   if (!G.getTargetTriple().isOSBinFormatMachO())
 751     return make_error<JITLinkError>(
 752         "Error linking " + G.getName() +
 753         ": compact unwind splitting not supported on non-macho target " +
 754         G.getTargetTriple().str());
 755
 756   unsigned CURecordSize = 0;
 757   unsigned PersonalityEdgeOffset = 0;
 758   unsigned LSDAEdgeOffset = 0;
 759   switch (G.getTargetTriple().getArch()) {
 760   case Triple::aarch64:
 761   case Triple::x86_64:
 762     // 64-bit compact-unwind record format:
 763     // Range start: 8 bytes.
 764     // Range size:  4 bytes.
 765     // CU encoding: 4 bytes.
 766     // Personality: 8 bytes.
 767     // LSDA:        8 bytes.
 768     CURecordSize = 32;
 769     PersonalityEdgeOffset = 16;
 770     LSDAEdgeOffset = 24;
 771     break;
 772   default:
 773     return make_error<JITLinkError>(
 774         "Error linking " + G.getName() +
 775         ": compact unwind splitting not supported on " +
 776         G.getTargetTriple().getArchName());
 777   }
 778
 779   std::vector<Block *> OriginalBlocks(CUSec->blocks().begin(),
 780                                       CUSec->blocks().end());
 781   LLVM_DEBUG({
 782     dbgs() << "In " << G.getName() << " splitting compact unwind section "
 783            << CompactUnwindSectionName << " containing "
 784            << OriginalBlocks.size() << " initial blocks...\n";
 785   });
 786
 787   while (!OriginalBlocks.empty()) {
 788     auto *B = OriginalBlocks.back();
 789     OriginalBlocks.pop_back();
 790
 791     if (B->getSize() == 0) {
 792       LLVM_DEBUG({
 793         dbgs() << "  Skipping empty block at "
 794                << formatv("{0:x16}", B->getAddress()) << "\n";
 795       });
 796       continue;
 797     }
 798
 799     LLVM_DEBUG({
 800       dbgs() << "  Splitting block at " << formatv("{0:x16}", B->getAddress())
 801              << " into " << (B->getSize() / CURecordSize)
 802              << " compact unwind record(s)\n";
 803     });
 804
 805     if (B->getSize() % CURecordSize)
 806       return make_error<JITLinkError>(
 807           "Error splitting compact unwind record in " + G.getName() +
 808           ": block at " + formatv("{0:x}", B->getAddress()) + " has size " +
 809           formatv("{0:x}", B->getSize()) +
 810           " (not a multiple of CU record size of " +
 811           formatv("{0:x}", CURecordSize) + ")");
 812
 813     unsigned NumBlocks = B->getSize() / CURecordSize;
 814     LinkGraph::SplitBlockCache C;
 815
 816     for (unsigned I = 0; I != NumBlocks; ++I) {
 817       auto &CURec = G.splitBlock(*B, CURecordSize, &C);
 818       bool AddedKeepAlive = false;
 819
 820       for (auto &E : CURec.edges()) {
 821         if (E.getOffset() == 0) {
 822           LLVM_DEBUG({
 823             dbgs() << "    Updating compact unwind record at "
 824                    << formatv("{0:x16}", CURec.getAddress()) << " to point to "
 825                    << (E.getTarget().hasName() ? E.getTarget().getName()
 826                                                : StringRef())
 827                    << " (at " << formatv("{0:x16}", E.getTarget().getAddress())
 828                    << ")\n";
 829           });
 830
 831           if (E.getTarget().isExternal())
 832             return make_error<JITLinkError>(
 833                 "Error adding keep-alive edge for compact unwind record at " +
 834                 formatv("{0:x}", CURec.getAddress()) + ": target " +
 835                 E.getTarget().getName() + " is an external symbol");
 836           auto &TgtBlock = E.getTarget().getBlock();
 837           auto &CURecSym =
 838               G.addAnonymousSymbol(CURec, 0, CURecordSize, false, false);
 839           TgtBlock.addEdge(Edge::KeepAlive, 0, CURecSym, 0);
 840           AddedKeepAlive = true;
 841         } else if (E.getOffset() != PersonalityEdgeOffset &&
 842                    E.getOffset() != LSDAEdgeOffset)
 843           return make_error<JITLinkError>("Unexpected edge at offset " +
 844                                           formatv("{0:x}", E.getOffset()) +
 845                                           " in compact unwind record at " +
 846                                           formatv("{0:x}", CURec.getAddress()));
 847       }
 848
 849       if (!AddedKeepAlive)
 850         return make_error<JITLinkError>(
 851             "Error adding keep-alive edge for compact unwind record at " +
 852             formatv("{0:x}", CURec.getAddress()) +
 853             ": no outgoing target edge at offset 0");
 854     }
 855   }
 856   return Error::success();
 857 }
 858
 859 } // end namespace jitlink
 860 } // end namespace llvm