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 &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.
96static 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
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 &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.
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