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 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                return LHS->Address < RHS->Address;
 183              });
 184
 185   for (unsigned I = 0, E = Sections.size() - 1; I != E; ++I) {
 186     auto &Cur = *Sections[I];
 187     auto &Next = *Sections[I + 1];
 188     if (Next.Address < Cur.Address + Cur.Size)
 189       return make_error<JITLinkError>(
 190           "Address range for section " + Cur.GraphSection->getName() +
 191           formatv(" [ {0:x16} -- {1:x16} ] ", Cur.Address,
 192                   Cur.Address + Cur.Size) +
 193           "overlaps " +
 194           formatv(" [ {0:x16} -- {1:x16} ] ", Next.Address,
 195                   Next.Address + Next.Size));
 196   }
 197
 198   return Error::success();
 199 }
 200
 201 Error MachOLinkGraphBuilder::createNormalizedSymbols() {
 202   LLVM_DEBUG(dbgs() << "Creating normalized symbols...\n");
 203
 204   for (auto &SymRef : Obj.symbols()) {
 205
 206     unsigned SymbolIndex = Obj.getSymbolIndex(SymRef.getRawDataRefImpl());
 207     uint64_t Value;
 208     uint32_t NStrX;
 209     uint8_t Type;
 210     uint8_t Sect;
 211     uint16_t Desc;
 212
 213     if (Obj.is64Bit()) {
 214       const MachO::nlist_64 &NL64 =
 215           Obj.getSymbol64TableEntry(SymRef.getRawDataRefImpl());
 216       Value = NL64.n_value;
 217       NStrX = NL64.n_strx;
 218       Type = NL64.n_type;
 219       Sect = NL64.n_sect;
 220       Desc = NL64.n_desc;
 221     } else {
 222       const MachO::nlist &NL32 =
 223           Obj.getSymbolTableEntry(SymRef.getRawDataRefImpl());
 224       Value = NL32.n_value;
 225       NStrX = NL32.n_strx;
 226       Type = NL32.n_type;
 227       Sect = NL32.n_sect;
 228       Desc = NL32.n_desc;
 229     }
 230
 231     // Skip stabs.
 232     // FIXME: Are there other symbols we should be skipping?
 233     if (Type & MachO::N_STAB)
 234       continue;
 235
 236     Optional<StringRef> Name;
 237     if (NStrX) {
 238       if (auto NameOrErr = SymRef.getName())
 239         Name = *NameOrErr;
 240       else
 241         return NameOrErr.takeError();
 242     }
 243
 244     LLVM_DEBUG({
 245       dbgs() << "  ";
 246       if (!Name)
 247         dbgs() << "<anonymous symbol>";
 248       else
 249         dbgs() << *Name;
 250       dbgs() << ": value = " << formatv("{0:x16}", Value)
 251              << ", type = " << formatv("{0:x2}", Type)
 252              << ", desc = " << formatv("{0:x4}", Desc) << ", sect = ";
 253       if (Sect)
 254         dbgs() << static_cast<unsigned>(Sect - 1);
 255       else
 256         dbgs() << "none";
 257       dbgs() << "\n";
 258     });
 259
 260     // If this symbol has a section, sanity check that the addresses line up.
 261     NormalizedSection *NSec = nullptr;
 262     if (Sect != 0) {
 263       if (auto NSecOrErr = findSectionByIndex(Sect - 1))
 264         NSec = &*NSecOrErr;
 265       else
 266         return NSecOrErr.takeError();
 267
 268       if (Value < NSec->Address || Value > NSec->Address + NSec->Size)
 269         return make_error<JITLinkError>("Symbol address does not fall within "
 270                                         "section");
 271     }
 272
 273     IndexToSymbol[SymbolIndex] =
 274         &createNormalizedSymbol(*Name, Value, Type, Sect, Desc,
 275                                 getLinkage(Type), getScope(*Name, Type));
 276   }
 277
 278   return Error::success();
 279 }
 280
 281 void MachOLinkGraphBuilder::addSectionStartSymAndBlock(
 282     Section &GraphSec, uint64_t Address, const char *Data, uint64_t Size,
 283     uint32_t Alignment, bool IsLive) {
 284   Block &B =
 285       Data ? G->createContentBlock(GraphSec, StringRef(Data, Size), Address,
 286                                    Alignment, 0)
 287            : G->createZeroFillBlock(GraphSec, Size, Address, Alignment, 0);
 288   auto &Sym = G->addAnonymousSymbol(B, 0, Size, false, IsLive);
 289   assert(!AddrToCanonicalSymbol.count(Sym.getAddress()) &&
 290          "Anonymous block start symbol clashes with existing symbol address");
 291   AddrToCanonicalSymbol[Sym.getAddress()] = &Sym;
 292 }
 293
 294 Error MachOLinkGraphBuilder::graphifyRegularSymbols() {
 295
 296   LLVM_DEBUG(dbgs() << "Creating graph symbols...\n");
 297
 298   /// We only have 256 section indexes: Use a vector rather than a map.
 299   std::vector<std::vector<NormalizedSymbol *>> SecIndexToSymbols;
 300   SecIndexToSymbols.resize(256);
 301
 302   // Create commons, externs, and absolutes, and partition all other symbols by
 303   // section.
 304   for (auto &KV : IndexToSymbol) {
 305     auto &NSym = *KV.second;
 306
 307     switch (NSym.Type & MachO::N_TYPE) {
 308     case MachO::N_UNDF:
 309       if (NSym.Value) {
 310         if (!NSym.Name)
 311           return make_error<JITLinkError>("Anonymous common symbol at index " +
 312                                           Twine(KV.first));
 313         NSym.GraphSymbol = &G->addCommonSymbol(
 314             *NSym.Name, NSym.S, getCommonSection(), NSym.Value, 0,
 315             1ull << MachO::GET_COMM_ALIGN(NSym.Desc),
 316             NSym.Desc & MachO::N_NO_DEAD_STRIP);
 317       } else {
 318         if (!NSym.Name)
 319           return make_error<JITLinkError>("Anonymous external symbol at "
 320                                           "index " +
 321                                           Twine(KV.first));
 322         NSym.GraphSymbol = &G->addExternalSymbol(*NSym.Name, 0);
 323       }
 324       break;
 325     case MachO::N_ABS:
 326       if (!NSym.Name)
 327         return make_error<JITLinkError>("Anonymous absolute symbol at index " +
 328                                         Twine(KV.first));
 329       NSym.GraphSymbol = &G->addAbsoluteSymbol(
 330           *NSym.Name, NSym.Value, 0, Linkage::Strong, Scope::Default,
 331           NSym.Desc & MachO::N_NO_DEAD_STRIP);
 332       break;
 333     case MachO::N_SECT:
 334       SecIndexToSymbols[NSym.Sect - 1].push_back(&NSym);
 335       break;
 336     case MachO::N_PBUD:
 337       return make_error<JITLinkError>(
 338           "Unupported N_PBUD symbol " +
 339           (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) +
 340           " at index " + Twine(KV.first));
 341     case MachO::N_INDR:
 342       return make_error<JITLinkError>(
 343           "Unupported N_INDR symbol " +
 344           (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) +
 345           " at index " + Twine(KV.first));
 346     default:
 347       return make_error<JITLinkError>(
 348           "Unrecognized symbol type " + Twine(NSym.Type & MachO::N_TYPE) +
 349           " for symbol " +
 350           (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) +
 351           " at index " + Twine(KV.first));
 352     }
 353   }
 354
 355   // Loop over sections performing regular graphification for those that
 356   // don't have custom parsers.
 357   for (auto &KV : IndexToSection) {
 358     auto SecIndex = KV.first;
 359     auto &NSec = KV.second;
 360
 361     // Skip sections with custom parsers.
 362     if (CustomSectionParserFunctions.count(NSec.GraphSection->getName())) {
 363       LLVM_DEBUG({
 364         dbgs() << "  Skipping section " << NSec.GraphSection->getName()
 365                << " as it has a custom parser.\n";
 366       });
 367       continue;
 368     } else
 369       LLVM_DEBUG({
 370         dbgs() << "  Processing section " << NSec.GraphSection->getName()
 371                << "...\n";
 372       });
 373
 374     bool SectionIsNoDeadStrip = NSec.Flags & MachO::S_ATTR_NO_DEAD_STRIP;
 375     bool SectionIsText = NSec.Flags & MachO::S_ATTR_PURE_INSTRUCTIONS;
 376
 377     auto &SecNSymStack = SecIndexToSymbols[SecIndex];
 378
 379     // If this section is non-empty but there are no symbols covering it then
 380     // create one block and anonymous symbol to cover the entire section.
 381     if (SecNSymStack.empty()) {
 382       if (NSec.Size > 0) {
 383         LLVM_DEBUG({
 384           dbgs() << "    Section non-empty, but contains no symbols. "
 385                     "Creating anonymous block to cover "
 386                  << formatv("{0:x16}", NSec.Address) << " -- "
 387                  << formatv("{0:x16}", NSec.Address + NSec.Size) << "\n";
 388         });
 389         addSectionStartSymAndBlock(*NSec.GraphSection, NSec.Address, NSec.Data,
 390                                    NSec.Size, NSec.Alignment,
 391                                    SectionIsNoDeadStrip);
 392       } else
 393         LLVM_DEBUG({
 394           dbgs() << "    Section empty and contains no symbols. Skipping.\n";
 395         });
 396       continue;
 397     }
 398
 399     // Sort the symbol stack in by address, alt-entry status, scope, and name.
 400     // We sort in reverse order so that symbols will be visited in the right
 401     // order when we pop off the stack below.
 402     llvm::sort(SecNSymStack, [](const NormalizedSymbol *LHS,
 403                                 const NormalizedSymbol *RHS) {
 404       if (LHS->Value != RHS->Value)
 405         return LHS->Value > RHS->Value;
 406       if (isAltEntry(*LHS) != isAltEntry(*RHS))
 407         return isAltEntry(*RHS);
 408       if (LHS->S != RHS->S)
 409         return static_cast<uint8_t>(LHS->S) < static_cast<uint8_t>(RHS->S);
 410       return LHS->Name < RHS->Name;
 411     });
 412
 413     // The first symbol in a section can not be an alt-entry symbol.
 414     if (!SecNSymStack.empty() && isAltEntry(*SecNSymStack.back()))
 415       return make_error<JITLinkError>(
 416           "First symbol in " + NSec.GraphSection->getName() + " is alt-entry");
 417
 418     // If the section is non-empty but there is no symbol covering the start
 419     // address then add an anonymous one.
 420     if (SecNSymStack.back()->Value != NSec.Address) {
 421       auto AnonBlockSize = SecNSymStack.back()->Value - NSec.Address;
 422       LLVM_DEBUG({
 423         dbgs() << "    Section start not covered by symbol. "
 424                << "Creating anonymous block to cover [ "
 425                << formatv("{0:x16}", NSec.Address) << " -- "
 426                << formatv("{0:x16}", NSec.Address + AnonBlockSize) << " ]\n";
 427       });
 428       addSectionStartSymAndBlock(*NSec.GraphSection, NSec.Address, NSec.Data,
 429                                  AnonBlockSize, NSec.Alignment,
 430                                  SectionIsNoDeadStrip);
 431     }
 432
 433     // Visit section symbols in order by popping off the reverse-sorted stack,
 434     // building blocks for each alt-entry chain and creating symbols as we go.
 435     while (!SecNSymStack.empty()) {
 436       SmallVector<NormalizedSymbol *, 8> BlockSyms;
 437
 438       BlockSyms.push_back(SecNSymStack.back());
 439       SecNSymStack.pop_back();
 440       while (!SecNSymStack.empty() &&
 441              (isAltEntry(*SecNSymStack.back()) ||
 442               SecNSymStack.back()->Value == BlockSyms.back()->Value)) {
 443         BlockSyms.push_back(SecNSymStack.back());
 444         SecNSymStack.pop_back();
 445       }
 446
 447       // BlockNSyms now contains the block symbols in reverse canonical order.
 448       JITTargetAddress BlockStart = BlockSyms.front()->Value;
 449       JITTargetAddress BlockEnd = SecNSymStack.empty()
 450                                       ? NSec.Address + NSec.Size
 451                                       : SecNSymStack.back()->Value;
 452       JITTargetAddress BlockOffset = BlockStart - NSec.Address;
 453       JITTargetAddress BlockSize = BlockEnd - BlockStart;
 454
 455       LLVM_DEBUG({
 456         dbgs() << "    Creating block for " << formatv("{0:x16}", BlockStart)
 457                << " -- " << formatv("{0:x16}", BlockEnd) << ": "
 458                << NSec.GraphSection->getName() << " + "
 459                << formatv("{0:x16}", BlockOffset) << " with "
 460                << BlockSyms.size() << " symbol(s)...\n";
 461       });
 462
 463       Block &B =
 464           NSec.Data
 465               ? G->createContentBlock(
 466                     *NSec.GraphSection,
 467                     StringRef(NSec.Data + BlockOffset, BlockSize), BlockStart,
 468                     NSec.Alignment, BlockStart % NSec.Alignment)
 469               : G->createZeroFillBlock(*NSec.GraphSection, BlockSize,
 470                                        BlockStart, NSec.Alignment,
 471                                        BlockStart % NSec.Alignment);
 472
 473       Optional<JITTargetAddress> LastCanonicalAddr;
 474       JITTargetAddress SymEnd = BlockEnd;
 475       while (!BlockSyms.empty()) {
 476         auto &NSym = *BlockSyms.back();
 477         BlockSyms.pop_back();
 478
 479         bool SymLive =
 480             (NSym.Desc & MachO::N_NO_DEAD_STRIP) || SectionIsNoDeadStrip;
 481
 482         LLVM_DEBUG({
 483           dbgs() << "      " << formatv("{0:x16}", NSym.Value) << " -- "
 484                  << formatv("{0:x16}", SymEnd) << ": ";
 485           if (!NSym.Name)
 486             dbgs() << "<anonymous symbol>";
 487           else
 488             dbgs() << NSym.Name;
 489           if (SymLive)
 490             dbgs() << " [no-dead-strip]";
 491           if (LastCanonicalAddr == NSym.Value)
 492             dbgs() << " [non-canonical]";
 493           dbgs() << "\n";
 494         });
 495
 496         auto &Sym =
 497             NSym.Name
 498                 ? G->addDefinedSymbol(B, NSym.Value - BlockStart, *NSym.Name,
 499                                       SymEnd - NSym.Value, NSym.L, NSym.S,
 500                                       SectionIsText, SymLive)
 501                 : G->addAnonymousSymbol(B, NSym.Value - BlockStart,
 502                                         SymEnd - NSym.Value, SectionIsText,
 503                                         SymLive);
 504         NSym.GraphSymbol = &Sym;
 505         if (LastCanonicalAddr != Sym.getAddress()) {
 506           if (LastCanonicalAddr)
 507             SymEnd = *LastCanonicalAddr;
 508           LastCanonicalAddr = Sym.getAddress();
 509           setCanonicalSymbol(Sym);
 510         }
 511       }
 512     }
 513   }
 514
 515   return Error::success();
 516 }
 517
 518 Error MachOLinkGraphBuilder::graphifySectionsWithCustomParsers() {
 519   // Graphify special sections.
 520   for (auto &KV : IndexToSection) {
 521     auto &NSec = KV.second;
 522
 523     auto HI = CustomSectionParserFunctions.find(NSec.GraphSection->getName());
 524     if (HI != CustomSectionParserFunctions.end()) {
 525       auto &Parse = HI->second;
 526       if (auto Err = Parse(NSec))
 527         return Err;
 528     }
 529   }
 530
 531   return Error::success();
 532 }
 533
 534 } // end namespace jitlink
 535 } // end namespace llvm