contrib/llvm-project/lld/lib/ReaderWriter/MachO/LayoutPass.cpp

   1 //===-- ReaderWriter/MachO/LayoutPass.cpp - Layout atoms ------------------===//
   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 #include "LayoutPass.h"
  10 #include "lld/Core/Instrumentation.h"
  11 #include "lld/Core/PassManager.h"
  12 #include "lld/ReaderWriter/MachOLinkingContext.h"
  13 #include "llvm/ADT/STLExtras.h"
  14 #include "llvm/ADT/Twine.h"
  15 #include "llvm/Support/Debug.h"
  16 #include "llvm/Support/Parallel.h"
  17 #include <algorithm>
  18 #include <set>
  19 #include <utility>
  20
  21 using namespace lld;
  22
  23 #define DEBUG_TYPE "LayoutPass"
  24
  25 namespace lld {
  26 namespace mach_o {
  27
  28 static bool compareAtoms(const LayoutPass::SortKey &,
  29                          const LayoutPass::SortKey &,
  30                          LayoutPass::SortOverride customSorter);
  31
  32 #ifndef NDEBUG
  33 // Return "reason (leftval, rightval)"
  34 static std::string formatReason(StringRef reason, int leftVal, int rightVal) {
  35   return (Twine(reason) + " (" + Twine(leftVal) + ", " + Twine(rightVal) + ")")
  36       .str();
  37 }
  38
  39 // Less-than relationship of two atoms must be transitive, which is, if a < b
  40 // and b < c, a < c must be true. This function checks the transitivity by
  41 // checking the sort results.
  42 static void checkTransitivity(std::vector<LayoutPass::SortKey> &vec,
  43                               LayoutPass::SortOverride customSorter) {
  44   for (auto i = vec.begin(), e = vec.end(); (i + 1) != e; ++i) {
  45     for (auto j = i + 1; j != e; ++j) {
  46       assert(compareAtoms(*i, *j, customSorter));
  47       assert(!compareAtoms(*j, *i, customSorter));
  48     }
  49   }
  50 }
  51
  52 // Helper functions to check follow-on graph.
  53 typedef llvm::DenseMap<const DefinedAtom *, const DefinedAtom *> AtomToAtomT;
  54
  55 static std::string atomToDebugString(const Atom *atom) {
  56   const DefinedAtom *definedAtom = dyn_cast<DefinedAtom>(atom);
  57   std::string str;
  58   llvm::raw_string_ostream s(str);
  59   if (definedAtom->name().empty())
  60     s << "<anonymous " << definedAtom << ">";
  61   else
  62     s << definedAtom->name();
  63   s << " in ";
  64   if (definedAtom->customSectionName().empty())
  65     s << "<anonymous>";
  66   else
  67     s << definedAtom->customSectionName();
  68   s.flush();
  69   return str;
  70 }
  71
  72 static void showCycleDetectedError(const Registry &registry,
  73                                    AtomToAtomT &followOnNexts,
  74                                    const DefinedAtom *atom) {
  75   const DefinedAtom *start = atom;
  76   llvm::dbgs() << "There's a cycle in a follow-on chain!\n";
  77   do {
  78     llvm::dbgs() << "  " << atomToDebugString(atom) << "\n";
  79     for (const Reference *ref : *atom) {
  80       StringRef kindValStr;
  81       if (!registry.referenceKindToString(ref->kindNamespace(), ref->kindArch(),
  82                                           ref->kindValue(), kindValStr)) {
  83         kindValStr = "<unknown>";
  84       }
  85       llvm::dbgs() << "    " << kindValStr
  86                    << ": " << atomToDebugString(ref->target()) << "\n";
  87     }
  88     atom = followOnNexts[atom];
  89   } while (atom != start);
  90   llvm::report_fatal_error("Cycle detected");
  91 }
  92
  93 /// Exit if there's a cycle in a followon chain reachable from the
  94 /// given root atom. Uses the tortoise and hare algorithm to detect a
  95 /// cycle.
  96 static void checkNoCycleInFollowonChain(const Registry &registry,
  97                                         AtomToAtomT &followOnNexts,
  98                                         const DefinedAtom *root) {
  99   const DefinedAtom *tortoise = root;
 100   const DefinedAtom *hare = followOnNexts[root];
 101   while (true) {
 102     if (!tortoise || !hare)
 103       return;
 104     if (tortoise == hare)
 105       showCycleDetectedError(registry, followOnNexts, tortoise);
 106     tortoise = followOnNexts[tortoise];
 107     hare = followOnNexts[followOnNexts[hare]];
 108   }
 109 }
 110
 111 static void checkReachabilityFromRoot(AtomToAtomT &followOnRoots,
 112                                       const DefinedAtom *atom) {
 113   if (!atom) return;
 114   auto i = followOnRoots.find(atom);
 115   if (i == followOnRoots.end()) {
 116     llvm_unreachable(((Twine("Atom <") + atomToDebugString(atom) +
 117                        "> has no follow-on root!"))
 118                          .str()
 119                          .c_str());
 120   }
 121   const DefinedAtom *ap = i->second;
 122   while (true) {
 123     const DefinedAtom *next = followOnRoots[ap];
 124     if (!next) {
 125       llvm_unreachable((Twine("Atom <" + atomToDebugString(atom) +
 126                               "> is not reachable from its root!"))
 127                            .str()
 128                            .c_str());
 129     }
 130     if (next == ap)
 131       return;
 132     ap = next;
 133   }
 134 }
 135
 136 static void printDefinedAtoms(const File::AtomRange<DefinedAtom> &atomRange) {
 137   for (const DefinedAtom *atom : atomRange) {
 138     llvm::dbgs() << "  file=" << atom->file().path()
 139                  << ", name=" << atom->name()
 140                  << ", size=" << atom->size()
 141                  << ", type=" << atom->contentType()
 142                  << ", ordinal=" << atom->ordinal()
 143                  << "\n";
 144   }
 145 }
 146
 147 /// Verify that the followon chain is sane. Should not be called in
 148 /// release binary.
 149 void LayoutPass::checkFollowonChain(const File::AtomRange<DefinedAtom> &range) {
 150   ScopedTask task(getDefaultDomain(), "LayoutPass::checkFollowonChain");
 151
 152   // Verify that there's no cycle in follow-on chain.
 153   std::set<const DefinedAtom *> roots;
 154   for (const auto &ai : _followOnRoots)
 155     roots.insert(ai.second);
 156   for (const DefinedAtom *root : roots)
 157     checkNoCycleInFollowonChain(_registry, _followOnNexts, root);
 158
 159   // Verify that all the atoms in followOnNexts have references to
 160   // their roots.
 161   for (const auto &ai : _followOnNexts) {
 162     checkReachabilityFromRoot(_followOnRoots, ai.first);
 163     checkReachabilityFromRoot(_followOnRoots, ai.second);
 164   }
 165 }
 166 #endif // #ifndef NDEBUG
 167
 168 /// The function compares atoms by sorting atoms in the following order
 169 /// a) Sorts atoms by their ordinal overrides (layout-after/ingroup)
 170 /// b) Sorts atoms by their permissions
 171 /// c) Sorts atoms by their content
 172 /// d) Sorts atoms by custom sorter
 173 /// e) Sorts atoms on how they appear using File Ordinality
 174 /// f) Sorts atoms on how they appear within the File
 175 static bool compareAtomsSub(const LayoutPass::SortKey &lc,
 176                             const LayoutPass::SortKey &rc,
 177                             LayoutPass::SortOverride customSorter,
 178                             std::string &reason) {
 179   const DefinedAtom *left = lc._atom.get();
 180   const DefinedAtom *right = rc._atom.get();
 181   if (left == right) {
 182     reason = "same";
 183     return false;
 184   }
 185
 186   // Find the root of the chain if it is a part of a follow-on chain.
 187   const DefinedAtom *leftRoot = lc._root;
 188   const DefinedAtom *rightRoot = rc._root;
 189
 190   // Sort atoms by their ordinal overrides only if they fall in the same
 191   // chain.
 192   if (leftRoot == rightRoot) {
 193     LLVM_DEBUG(reason = formatReason("override", lc._override, rc._override));
 194     return lc._override < rc._override;
 195   }
 196
 197   // Sort same permissions together.
 198   DefinedAtom::ContentPermissions leftPerms = leftRoot->permissions();
 199   DefinedAtom::ContentPermissions rightPerms = rightRoot->permissions();
 200
 201   if (leftPerms != rightPerms) {
 202     LLVM_DEBUG(
 203         reason = formatReason("contentPerms", (int)leftPerms, (int)rightPerms));
 204     return leftPerms < rightPerms;
 205   }
 206
 207   // Sort same content types together.
 208   DefinedAtom::ContentType leftType = leftRoot->contentType();
 209   DefinedAtom::ContentType rightType = rightRoot->contentType();
 210
 211   if (leftType != rightType) {
 212     LLVM_DEBUG(reason =
 213                    formatReason("contentType", (int)leftType, (int)rightType));
 214     return leftType < rightType;
 215   }
 216
 217   // Use custom sorter if supplied.
 218   if (customSorter) {
 219     bool leftBeforeRight;
 220     if (customSorter(leftRoot, rightRoot, leftBeforeRight))
 221       return leftBeforeRight;
 222   }
 223
 224   // Sort by .o order.
 225   const File *leftFile = &leftRoot->file();
 226   const File *rightFile = &rightRoot->file();
 227
 228   if (leftFile != rightFile) {
 229     LLVM_DEBUG(reason = formatReason(".o order", (int)leftFile->ordinal(),
 230                                      (int)rightFile->ordinal()));
 231     return leftFile->ordinal() < rightFile->ordinal();
 232   }
 233
 234   // Sort by atom order with .o file.
 235   uint64_t leftOrdinal = leftRoot->ordinal();
 236   uint64_t rightOrdinal = rightRoot->ordinal();
 237
 238   if (leftOrdinal != rightOrdinal) {
 239     LLVM_DEBUG(reason = formatReason("ordinal", (int)leftRoot->ordinal(),
 240                                      (int)rightRoot->ordinal()));
 241     return leftOrdinal < rightOrdinal;
 242   }
 243
 244   llvm::errs() << "Unordered: <" << left->name() << "> <"
 245                << right->name() << ">\n";
 246   llvm_unreachable("Atoms with Same Ordinal!");
 247 }
 248
 249 static bool compareAtoms(const LayoutPass::SortKey &lc,
 250                          const LayoutPass::SortKey &rc,
 251                          LayoutPass::SortOverride customSorter) {
 252   std::string reason;
 253   bool result = compareAtomsSub(lc, rc, customSorter, reason);
 254   LLVM_DEBUG({
 255     StringRef comp = result ? "<" : ">=";
 256     llvm::dbgs() << "Layout: '" << lc._atom.get()->name()
 257                  << "' " << comp << " '"
 258                  << rc._atom.get()->name() << "' (" << reason << ")\n";
 259   });
 260   return result;
 261 }
 262
 263 LayoutPass::LayoutPass(const Registry &registry, SortOverride sorter)
 264     : _registry(registry), _customSorter(std::move(sorter)) {}
 265
 266 // Returns the atom immediately followed by the given atom in the followon
 267 // chain.
 268 const DefinedAtom *LayoutPass::findAtomFollowedBy(
 269     const DefinedAtom *targetAtom) {
 270   // Start from the beginning of the chain and follow the chain until
 271   // we find the targetChain.
 272   const DefinedAtom *atom = _followOnRoots[targetAtom];
 273   while (true) {
 274     const DefinedAtom *prevAtom = atom;
 275     AtomToAtomT::iterator targetFollowOnAtomsIter = _followOnNexts.find(atom);
 276     // The target atom must be in the chain of its root.
 277     assert(targetFollowOnAtomsIter != _followOnNexts.end());
 278     atom = targetFollowOnAtomsIter->second;
 279     if (atom == targetAtom)
 280       return prevAtom;
 281   }
 282 }
 283
 284 // Check if all the atoms followed by the given target atom are of size zero.
 285 // When this method is called, an atom being added is not of size zero and
 286 // will be added to the head of the followon chain. All the atoms between the
 287 // atom and the targetAtom (specified by layout-after) need to be of size zero
 288 // in this case. Otherwise the desired layout is impossible.
 289 bool LayoutPass::checkAllPrevAtomsZeroSize(const DefinedAtom *targetAtom) {
 290   const DefinedAtom *atom = _followOnRoots[targetAtom];
 291   while (true) {
 292     if (atom == targetAtom)
 293       return true;
 294     if (atom->size() != 0)
 295       // TODO: print warning that an impossible layout is being desired by the
 296       // user.
 297       return false;
 298     AtomToAtomT::iterator targetFollowOnAtomsIter = _followOnNexts.find(atom);
 299     // The target atom must be in the chain of its root.
 300     assert(targetFollowOnAtomsIter != _followOnNexts.end());
 301     atom = targetFollowOnAtomsIter->second;
 302   }
 303 }
 304
 305 // Set the root of all atoms in targetAtom's chain to the given root.
 306 void LayoutPass::setChainRoot(const DefinedAtom *targetAtom,
 307                               const DefinedAtom *root) {
 308   // Walk through the followon chain and override each node's root.
 309   while (true) {
 310     _followOnRoots[targetAtom] = root;
 311     AtomToAtomT::iterator targetFollowOnAtomsIter =
 312         _followOnNexts.find(targetAtom);
 313     if (targetFollowOnAtomsIter == _followOnNexts.end())
 314       return;
 315     targetAtom = targetFollowOnAtomsIter->second;
 316   }
 317 }
 318
 319 /// This pass builds the followon tables described by two DenseMaps
 320 /// followOnRoots and followonNexts.
 321 /// The followOnRoots map contains a mapping of a DefinedAtom to its root
 322 /// The followOnNexts map contains a mapping of what DefinedAtom follows the
 323 /// current Atom
 324 /// The algorithm follows a very simple approach
 325 /// a) If the atom is first seen, then make that as the root atom
 326 /// b) The targetAtom which this Atom contains, has the root thats set to the
 327 ///    root of the current atom
 328 /// c) If the targetAtom is part of a different tree and the root of the
 329 ///    targetAtom is itself, Chain all the atoms that are contained in the tree
 330 ///    to the current Tree
 331 /// d) If the targetAtom is part of a different chain and the root of the
 332 ///    targetAtom until the targetAtom has all atoms of size 0, then chain the
 333 ///    targetAtoms and its tree to the current chain
 334 void LayoutPass::buildFollowOnTable(const File::AtomRange<DefinedAtom> &range) {
 335   ScopedTask task(getDefaultDomain(), "LayoutPass::buildFollowOnTable");
 336   // Set the initial size of the followon and the followonNext hash to the
 337   // number of atoms that we have.
 338   _followOnRoots.reserve(range.size());
 339   _followOnNexts.reserve(range.size());
 340   for (const DefinedAtom *ai : range) {
 341     for (const Reference *r : *ai) {
 342       if (r->kindNamespace() != lld::Reference::KindNamespace::all ||
 343           r->kindValue() != lld::Reference::kindLayoutAfter)
 344         continue;
 345       const DefinedAtom *targetAtom = dyn_cast<DefinedAtom>(r->target());
 346       _followOnNexts[ai] = targetAtom;
 347
 348       // If we find a followon for the first time, let's make that atom as the
 349       // root atom.
 350       if (_followOnRoots.count(ai) == 0)
 351         _followOnRoots[ai] = ai;
 352
 353       auto iter = _followOnRoots.find(targetAtom);
 354       if (iter == _followOnRoots.end()) {
 355         // If the targetAtom is not a root of any chain, let's make the root of
 356         // the targetAtom to the root of the current chain.
 357
 358         // The expression m[i] = m[j] where m is a DenseMap and i != j is not
 359         // safe. m[j] returns a reference, which would be invalidated when a
 360         // rehashing occurs. If rehashing occurs to make room for m[i], m[j]
 361         // becomes invalid, and that invalid reference would be used as the RHS
 362         // value of the expression.
 363         // Copy the value to workaround.
 364         const DefinedAtom *tmp = _followOnRoots[ai];
 365         _followOnRoots[targetAtom] = tmp;
 366         continue;
 367       }
 368       if (iter->second == targetAtom) {
 369         // If the targetAtom is the root of a chain, the chain becomes part of
 370         // the current chain. Rewrite the subchain's root to the current
 371         // chain's root.
 372         setChainRoot(targetAtom, _followOnRoots[ai]);
 373         continue;
 374       }
 375       // The targetAtom is already a part of a chain. If the current atom is
 376       // of size zero, we can insert it in the middle of the chain just
 377       // before the target atom, while not breaking other atom's followon
 378       // relationships. If it's not, we can only insert the current atom at
 379       // the beginning of the chain. All the atoms followed by the target
 380       // atom must be of size zero in that case to satisfy the followon
 381       // relationships.
 382       size_t currentAtomSize = ai->size();
 383       if (currentAtomSize == 0) {
 384         const DefinedAtom *targetPrevAtom = findAtomFollowedBy(targetAtom);
 385         _followOnNexts[targetPrevAtom] = ai;
 386         const DefinedAtom *tmp = _followOnRoots[targetPrevAtom];
 387         _followOnRoots[ai] = tmp;
 388         continue;
 389       }
 390       if (!checkAllPrevAtomsZeroSize(targetAtom))
 391         break;
 392       _followOnNexts[ai] = _followOnRoots[targetAtom];
 393       setChainRoot(_followOnRoots[targetAtom], _followOnRoots[ai]);
 394     }
 395   }
 396 }
 397
 398 /// Build an ordinal override map by traversing the followon chain, and
 399 /// assigning ordinals to each atom, if the atoms have their ordinals
 400 /// already assigned skip the atom and move to the next. This is the
 401 /// main map thats used to sort the atoms while comparing two atoms together
 402 void
 403 LayoutPass::buildOrdinalOverrideMap(const File::AtomRange<DefinedAtom> &range) {
 404   ScopedTask task(getDefaultDomain(), "LayoutPass::buildOrdinalOverrideMap");
 405   uint64_t index = 0;
 406   for (const DefinedAtom *ai : range) {
 407     const DefinedAtom *atom = ai;
 408     if (_ordinalOverrideMap.find(atom) != _ordinalOverrideMap.end())
 409       continue;
 410     AtomToAtomT::iterator start = _followOnRoots.find(atom);
 411     if (start == _followOnRoots.end())
 412       continue;
 413     for (const DefinedAtom *nextAtom = start->second; nextAtom;
 414          nextAtom = _followOnNexts[nextAtom]) {
 415       AtomToOrdinalT::iterator pos = _ordinalOverrideMap.find(nextAtom);
 416       if (pos == _ordinalOverrideMap.end())
 417         _ordinalOverrideMap[nextAtom] = index++;
 418     }
 419   }
 420 }
 421
 422 std::vector<LayoutPass::SortKey>
 423 LayoutPass::decorate(File::AtomRange<DefinedAtom> &atomRange) const {
 424   std::vector<SortKey> ret;
 425   for (OwningAtomPtr<DefinedAtom> &atom : atomRange.owning_ptrs()) {
 426     auto ri = _followOnRoots.find(atom.get());
 427     auto oi = _ordinalOverrideMap.find(atom.get());
 428     const auto *root = (ri == _followOnRoots.end()) ? atom.get() : ri->second;
 429     uint64_t override = (oi == _ordinalOverrideMap.end()) ? 0 : oi->second;
 430     ret.push_back(SortKey(std::move(atom), root, override));
 431   }
 432   return ret;
 433 }
 434
 435 void LayoutPass::undecorate(File::AtomRange<DefinedAtom> &atomRange,
 436                             std::vector<SortKey> &keys) const {
 437   size_t i = 0;
 438   for (SortKey &k : keys)
 439     atomRange[i++] = std::move(k._atom);
 440 }
 441
 442 /// Perform the actual pass
 443 llvm::Error LayoutPass::perform(SimpleFile &mergedFile) {
 444   LLVM_DEBUG(llvm::dbgs() << "******** Laying out atoms:\n");
 445   // sort the atoms
 446   ScopedTask task(getDefaultDomain(), "LayoutPass");
 447   File::AtomRange<DefinedAtom> atomRange = mergedFile.defined();
 448
 449   // Build follow on tables
 450   buildFollowOnTable(atomRange);
 451
 452   // Check the structure of followon graph if running in debug mode.
 453   LLVM_DEBUG(checkFollowonChain(atomRange));
 454
 455   // Build override maps
 456   buildOrdinalOverrideMap(atomRange);
 457
 458   LLVM_DEBUG({
 459     llvm::dbgs() << "unsorted atoms:\n";
 460     printDefinedAtoms(atomRange);
 461   });
 462
 463   std::vector<LayoutPass::SortKey> vec = decorate(atomRange);
 464   sort(llvm::parallel::par, vec.begin(), vec.end(),
 465        [&](const LayoutPass::SortKey &l, const LayoutPass::SortKey &r) -> bool {
 466          return compareAtoms(l, r, _customSorter);
 467        });
 468   LLVM_DEBUG(checkTransitivity(vec, _customSorter));
 469   undecorate(atomRange, vec);
 470
 471   LLVM_DEBUG({
 472     llvm::dbgs() << "sorted atoms:\n";
 473     printDefinedAtoms(atomRange);
 474   });
 475
 476   LLVM_DEBUG(llvm::dbgs() << "******** Finished laying out atoms\n");
 477   return llvm::Error::success();
 478 }
 479
 480 void addLayoutPass(PassManager &pm, const MachOLinkingContext &ctx) {
 481   pm.add(llvm::make_unique<LayoutPass>(
 482       ctx.registry(), [&](const DefinedAtom * left, const DefinedAtom * right,
 483                           bool & leftBeforeRight) ->bool {
 484     return ctx.customAtomOrderer(left, right, leftBeforeRight);
 485   }));
 486 }
 487
 488 } // namespace mach_o
 489 } // namespace lld