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 21using namespace lld; 22 23#define DEBUG_TYPE "LayoutPass" 24 25namespace lld { 26namespace mach_o { 27 28static bool compareAtoms(const LayoutPass::SortKey &, 29 const LayoutPass::SortKey &, 30 LayoutPass::SortOverride customSorter); 31 32#ifndef NDEBUG 33// Return "reason (leftval, rightval)" 34static 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. 42static 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. 53typedef llvm::DenseMap<const DefinedAtom *, const DefinedAtom *> AtomToAtomT; 54 55static 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 72static void showCycleDetectedError(const Registry ®istry, 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. 96static void checkNoCycleInFollowonChain(const Registry ®istry, 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 111static 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 136static 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. 149void 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 175static 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() << "> <" << right->name() 245 << ">\n"; 246 llvm_unreachable("Atoms with Same Ordinal!"); 247} 248 249static 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 263LayoutPass::LayoutPass(const Registry ®istry, 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. 268const 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. 289bool 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. 306void 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 334void 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 402void 403LayoutPass::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 422std::vector<LayoutPass::SortKey> 423LayoutPass::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 435void 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 443llvm::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 480void addLayoutPass(PassManager &pm, const MachOLinkingContext &ctx) { 481 pm.add(std::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 490