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