lib/ExecutionEngine/JITLink/MachOAtomGraphBuilder.cpp

   1 //=--------- MachOAtomGraphBuilder.cpp - MachO AtomGraph 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 AtomGraph buliding code.
  10 //
  11 //===----------------------------------------------------------------------===//
  12
  13 #include "MachOAtomGraphBuilder.h"
  14
  15 #define DEBUG_TYPE "jitlink"
  16
  17 namespace llvm {
  18 namespace jitlink {
  19
  20 MachOAtomGraphBuilder::~MachOAtomGraphBuilder() {}
  21
  22 Expected<std::unique_ptr<AtomGraph>> MachOAtomGraphBuilder::buildGraph() {
  23   if (auto Err = parseSections())
  24     return std::move(Err);
  25
  26   if (auto Err = addAtoms())
  27     return std::move(Err);
  28
  29   if (auto Err = addRelocations())
  30     return std::move(Err);
  31
  32   return std::move(G);
  33 }
  34
  35 MachOAtomGraphBuilder::MachOAtomGraphBuilder(const object::MachOObjectFile &Obj)
  36     : Obj(Obj),
  37       G(llvm::make_unique<AtomGraph>(Obj.getFileName(), getPointerSize(Obj),
  38                                      getEndianness(Obj))) {}
  39
  40 void MachOAtomGraphBuilder::addCustomAtomizer(StringRef SectionName,
  41                                               CustomAtomizeFunction Atomizer) {
  42   assert(!CustomAtomizeFunctions.count(SectionName) &&
  43          "Custom atomizer for this section already exists");
  44   CustomAtomizeFunctions[SectionName] = std::move(Atomizer);
  45 }
  46
  47 bool MachOAtomGraphBuilder::areLayoutLocked(const Atom &A, const Atom &B) {
  48   // If these atoms are the same then they're trivially "locked".
  49   if (&A == &B)
  50     return true;
  51
  52   // If A and B are different, check whether either is undefined. (in which
  53   // case they are not locked).
  54   if (!A.isDefined() || !B.isDefined())
  55     return false;
  56
  57   // A and B are different, but they're both defined atoms. We need to check
  58   // whether they're part of the same alt_entry chain.
  59   auto &DA = static_cast<const DefinedAtom &>(A);
  60   auto &DB = static_cast<const DefinedAtom &>(B);
  61
  62   auto AStartItr = AltEntryStarts.find(&DA);
  63   if (AStartItr == AltEntryStarts.end()) // If A is not in a chain bail out.
  64     return false;
  65
  66   auto BStartItr = AltEntryStarts.find(&DB);
  67   if (BStartItr == AltEntryStarts.end()) // If B is not in a chain bail out.
  68     return false;
  69
  70   // A and B are layout locked if they're in the same chain.
  71   return AStartItr->second == BStartItr->second;
  72 }
  73
  74 unsigned
  75 MachOAtomGraphBuilder::getPointerSize(const object::MachOObjectFile &Obj) {
  76   return Obj.is64Bit() ? 8 : 4;
  77 }
  78
  79 support::endianness
  80 MachOAtomGraphBuilder::getEndianness(const object::MachOObjectFile &Obj) {
  81   return Obj.isLittleEndian() ? support::little : support::big;
  82 }
  83
  84 MachOAtomGraphBuilder::MachOSection &MachOAtomGraphBuilder::getCommonSection() {
  85   if (!CommonSymbolsSection) {
  86     auto Prot = static_cast<sys::Memory::ProtectionFlags>(
  87         sys::Memory::MF_READ | sys::Memory::MF_WRITE);
  88     auto &GenericSection = G->createSection("<common>", 1, Prot, true);
  89     CommonSymbolsSection = MachOSection(GenericSection);
  90   }
  91   return *CommonSymbolsSection;
  92 }
  93
  94 Error MachOAtomGraphBuilder::parseSections() {
  95   for (auto &SecRef : Obj.sections()) {
  96     assert((SecRef.getAlignment() <= std::numeric_limits<uint32_t>::max()) &&
  97            "Section alignment does not fit in 32 bits");
  98
  99     StringRef Name;
 100     if (auto EC = SecRef.getName(Name))
 101       return errorCodeToError(EC);
 102
 103     unsigned SectionIndex = SecRef.getIndex() + 1;
 104
 105     uint32_t Align = SecRef.getAlignment();
 106     if (!isPowerOf2_32(Align))
 107       return make_error<JITLinkError>("Section " + Name +
 108                                       " has non-power-of-2 "
 109                                       "alignment");
 110
 111     // FIXME: Get real section permissions
 112     // How, exactly, on MachO?
 113     sys::Memory::ProtectionFlags Prot;
 114     if (SecRef.isText())
 115       Prot = static_cast<sys::Memory::ProtectionFlags>(sys::Memory::MF_READ |
 116                                                        sys::Memory::MF_EXEC);
 117     else
 118       Prot = static_cast<sys::Memory::ProtectionFlags>(sys::Memory::MF_READ |
 119                                                        sys::Memory::MF_WRITE);
 120
 121     auto &GenericSection = G->createSection(Name, Align, Prot, SecRef.isBSS());
 122
 123     LLVM_DEBUG({
 124       dbgs() << "Adding section " << Name << ": "
 125              << format("0x%016" PRIx64, SecRef.getAddress())
 126              << ", align: " << SecRef.getAlignment() << "\n";
 127     });
 128
 129     assert(!Sections.count(SectionIndex) && "Section index already in use");
 130
 131     auto &MachOSec =
 132         Sections
 133             .try_emplace(SectionIndex, GenericSection, SecRef.getAddress(),
 134                          SecRef.getAlignment())
 135             .first->second;
 136
 137     if (!SecRef.isVirtual()) {
 138       // If this section has content then record it.
 139       Expected<StringRef> Content = SecRef.getContents();
 140       if (!Content)
 141         return Content.takeError();
 142       if (Content->size() != SecRef.getSize())
 143         return make_error<JITLinkError>("Section content size does not match "
 144                                         "declared size for " +
 145                                         Name);
 146       MachOSec.setContent(*Content);
 147     } else {
 148       // If this is a zero-fill section then just record the size.
 149       MachOSec.setZeroFill(SecRef.getSize());
 150     }
 151
 152     uint32_t SectionFlags =
 153         Obj.is64Bit() ? Obj.getSection64(SecRef.getRawDataRefImpl()).flags
 154                       : Obj.getSection(SecRef.getRawDataRefImpl()).flags;
 155
 156     MachOSec.setNoDeadStrip(SectionFlags & MachO::S_ATTR_NO_DEAD_STRIP);
 157   }
 158
 159   return Error::success();
 160 }
 161
 162 // Adds atoms with identified start addresses (but not lengths) for all named
 163 // atoms.
 164 // Also, for every section that contains named atoms, but does not have an
 165 // atom at offset zero of that section, constructs an anonymous atom covering
 166 // that range.
 167 Error MachOAtomGraphBuilder::addNonCustomAtoms() {
 168   using AddrToAtomMap = std::map<JITTargetAddress, DefinedAtom *>;
 169   DenseMap<MachOSection *, AddrToAtomMap> SecToAtoms;
 170
 171   DenseMap<MachOSection *, unsigned> FirstOrdinal;
 172   std::vector<DefinedAtom *> AltEntryAtoms;
 173
 174   DenseSet<StringRef> ProcessedSymbols; // Used to check for duplicate defs.
 175
 176   for (auto SymI = Obj.symbol_begin(), SymE = Obj.symbol_end(); SymI != SymE;
 177        ++SymI) {
 178     object::SymbolRef Sym(SymI->getRawDataRefImpl(), &Obj);
 179
 180     auto Name = Sym.getName();
 181     if (!Name)
 182       return Name.takeError();
 183
 184     // Bail out on duplicate definitions: There should never be more than one
 185     // definition for a symbol in a given object file.
 186     if (ProcessedSymbols.count(*Name))
 187       return make_error<JITLinkError>("Duplicate definition within object: " +
 188                                       *Name);
 189     else
 190       ProcessedSymbols.insert(*Name);
 191
 192     auto Addr = Sym.getAddress();
 193     if (!Addr)
 194       return Addr.takeError();
 195
 196     auto SymType = Sym.getType();
 197     if (!SymType)
 198       return SymType.takeError();
 199
 200     auto Flags = Sym.getFlags();
 201
 202     if (Flags & object::SymbolRef::SF_Undefined) {
 203       LLVM_DEBUG(dbgs() << "Adding undef atom \"" << *Name << "\"\n");
 204       G->addExternalAtom(*Name);
 205       continue;
 206     } else if (Flags & object::SymbolRef::SF_Absolute) {
 207       LLVM_DEBUG(dbgs() << "Adding absolute \"" << *Name << "\" addr: "
 208                         << format("0x%016" PRIx64, *Addr) << "\n");
 209       auto &A = G->addAbsoluteAtom(*Name, *Addr);
 210       A.setGlobal(Flags & object::SymbolRef::SF_Global);
 211       A.setExported(Flags & object::SymbolRef::SF_Exported);
 212       A.setWeak(Flags & object::SymbolRef::SF_Weak);
 213       continue;
 214     } else if (Flags & object::SymbolRef::SF_Common) {
 215       LLVM_DEBUG({
 216         dbgs() << "Adding common \"" << *Name
 217                << "\" addr: " << format("0x%016" PRIx64, *Addr) << "\n";
 218       });
 219       auto &A =
 220           G->addCommonAtom(getCommonSection().getGenericSection(), *Name, *Addr,
 221                            std::max(Sym.getAlignment(), 1U),
 222                            Obj.getCommonSymbolSize(Sym.getRawDataRefImpl()));
 223       A.setGlobal(Flags & object::SymbolRef::SF_Global);
 224       A.setExported(Flags & object::SymbolRef::SF_Exported);
 225       continue;
 226     }
 227
 228     LLVM_DEBUG(dbgs() << "Adding defined atom \"" << *Name << "\"\n");
 229
 230     // This atom is neither undefined nor absolute, so it must be defined in
 231     // this object. Get its section index.
 232     auto SecItr = Sym.getSection();
 233     if (!SecItr)
 234       return SecItr.takeError();
 235
 236     uint64_t SectionIndex = (*SecItr)->getIndex() + 1;
 237
 238     LLVM_DEBUG(dbgs() << "  to section index " << SectionIndex << "\n");
 239
 240     auto SecByIndexItr = Sections.find(SectionIndex);
 241     if (SecByIndexItr == Sections.end())
 242       return make_error<JITLinkError>("Unrecognized section index in macho");
 243
 244     auto &Sec = SecByIndexItr->second;
 245
 246     auto &DA = G->addDefinedAtom(Sec.getGenericSection(), *Name, *Addr,
 247                                  std::max(Sym.getAlignment(), 1U));
 248
 249     DA.setGlobal(Flags & object::SymbolRef::SF_Global);
 250     DA.setExported(Flags & object::SymbolRef::SF_Exported);
 251     DA.setWeak(Flags & object::SymbolRef::SF_Weak);
 252
 253     DA.setCallable(*SymType & object::SymbolRef::ST_Function);
 254
 255     // Check NDesc flags.
 256     {
 257       uint16_t NDesc = 0;
 258       if (Obj.is64Bit())
 259         NDesc = Obj.getSymbol64TableEntry(SymI->getRawDataRefImpl()).n_desc;
 260       else
 261         NDesc = Obj.getSymbolTableEntry(SymI->getRawDataRefImpl()).n_desc;
 262
 263       // Record atom for alt-entry post-processing (where the layout-next
 264       // constraints will be added).
 265       if (NDesc & MachO::N_ALT_ENTRY)
 266         AltEntryAtoms.push_back(&DA);
 267
 268       // If this atom has a no-dead-strip attr attached then mark it live.
 269       if (NDesc & MachO::N_NO_DEAD_STRIP)
 270         DA.setLive(true);
 271     }
 272
 273     LLVM_DEBUG({
 274       dbgs() << "  Added " << *Name
 275              << " addr: " << format("0x%016" PRIx64, *Addr)
 276              << ", align: " << DA.getAlignment()
 277              << ", section: " << Sec.getGenericSection().getName() << "\n";
 278     });
 279
 280     auto &SecAtoms = SecToAtoms[&Sec];
 281     SecAtoms[DA.getAddress() - Sec.getAddress()] = &DA;
 282   }
 283
 284   // Add anonymous atoms.
 285   for (auto &KV : Sections) {
 286     auto &S = KV.second;
 287
 288     // Skip empty sections.
 289     if (S.empty())
 290       continue;
 291
 292     // Skip sections with custom handling.
 293     if (CustomAtomizeFunctions.count(S.getName()))
 294       continue;
 295
 296     auto SAI = SecToAtoms.find(&S);
 297
 298     // If S is not in the SecToAtoms map then it contained no named atom. Add
 299     // one anonymous atom to cover the whole section.
 300     if (SAI == SecToAtoms.end()) {
 301       SecToAtoms[&S][0] = &G->addAnonymousAtom(
 302           S.getGenericSection(), S.getAddress(), S.getAlignment());
 303       continue;
 304     }
 305
 306     // Otherwise, check whether this section had an atom covering offset zero.
 307     // If not, add one.
 308     auto &SecAtoms = SAI->second;
 309     if (!SecAtoms.count(0))
 310       SecAtoms[0] = &G->addAnonymousAtom(S.getGenericSection(), S.getAddress(),
 311                                          S.getAlignment());
 312   }
 313
 314   LLVM_DEBUG(dbgs() << "MachOGraphBuilder setting atom content\n");
 315
 316   // Set atom contents and any section-based flags.
 317   for (auto &KV : SecToAtoms) {
 318     auto &S = *KV.first;
 319     auto &SecAtoms = KV.second;
 320
 321     // Iterate the atoms in reverse order and set up their contents.
 322     JITTargetAddress LastAtomAddr = S.getSize();
 323     for (auto I = SecAtoms.rbegin(), E = SecAtoms.rend(); I != E; ++I) {
 324       auto Offset = I->first;
 325       auto &A = *I->second;
 326       LLVM_DEBUG({
 327         dbgs() << "  " << A << " to [ " << S.getAddress() + Offset << " .. "
 328                << S.getAddress() + LastAtomAddr << " ]\n";
 329       });
 330
 331       if (S.isZeroFill())
 332         A.setZeroFill(LastAtomAddr - Offset);
 333       else
 334         A.setContent(S.getContent().substr(Offset, LastAtomAddr - Offset));
 335
 336       // If the section has no-dead-strip set then mark the atom as live.
 337       if (S.isNoDeadStrip())
 338         A.setLive(true);
 339
 340       LastAtomAddr = Offset;
 341     }
 342   }
 343
 344   LLVM_DEBUG(dbgs() << "Adding alt-entry starts\n");
 345
 346   // Sort alt-entry atoms by address in ascending order.
 347   llvm::sort(AltEntryAtoms.begin(), AltEntryAtoms.end(),
 348              [](const DefinedAtom *LHS, const DefinedAtom *RHS) {
 349                return LHS->getAddress() < RHS->getAddress();
 350              });
 351
 352   // Process alt-entry atoms in address order to build the table of alt-entry
 353   // atoms to alt-entry chain starts.
 354   for (auto *DA : AltEntryAtoms) {
 355     assert(!AltEntryStarts.count(DA) && "Duplicate entry in AltEntryStarts");
 356
 357     // DA is an alt-entry atom. Look for the predecessor atom that it is locked
 358     // to, bailing out if we do not find one.
 359     auto AltEntryPred = G->findAtomByAddress(DA->getAddress() - 1);
 360     if (!AltEntryPred)
 361       return AltEntryPred.takeError();
 362
 363     // Add a LayoutNext edge from the predecessor to this atom.
 364     AltEntryPred->setLayoutNext(*DA);
 365
 366     // Check to see whether the predecessor itself is an alt-entry atom.
 367     auto AltEntryStartItr = AltEntryStarts.find(&*AltEntryPred);
 368     if (AltEntryStartItr != AltEntryStarts.end()) {
 369       // If the predecessor was an alt-entry atom then re-use its value.
 370       LLVM_DEBUG({
 371         dbgs() << "  " << *DA << " -> " << *AltEntryStartItr->second
 372                << " (based on existing entry for " << *AltEntryPred << ")\n";
 373       });
 374       AltEntryStarts[DA] = AltEntryStartItr->second;
 375     } else {
 376       // If the predecessor does not have an entry then add an entry for this
 377       // atom (i.e. the alt_entry atom) and a self-reference entry for the
 378       /// predecessory atom that is the start of this chain.
 379       LLVM_DEBUG({
 380         dbgs() << "  " << *AltEntryPred << " -> " << *AltEntryPred << "\n"
 381                << "  " << *DA << " -> " << *AltEntryPred << "\n";
 382       });
 383       AltEntryStarts[&*AltEntryPred] = &*AltEntryPred;
 384       AltEntryStarts[DA] = &*AltEntryPred;
 385     }
 386   }
 387
 388   return Error::success();
 389 }
 390
 391 Error MachOAtomGraphBuilder::addAtoms() {
 392   // Add all named atoms.
 393   if (auto Err = addNonCustomAtoms())
 394     return Err;
 395
 396   // Process special sections.
 397   for (auto &KV : Sections) {
 398     auto &S = KV.second;
 399     auto HI = CustomAtomizeFunctions.find(S.getGenericSection().getName());
 400     if (HI != CustomAtomizeFunctions.end()) {
 401       auto &Atomize = HI->second;
 402       if (auto Err = Atomize(S))
 403         return Err;
 404     }
 405   }
 406
 407   return Error::success();
 408 }
 409
 410 } // end namespace jitlink
 411 } // end namespace llvm