Coverage Report

Created: 2019-07-24 05:18

/Users/buildslave/jenkins/workspace/clang-stage2-coverage-R/llvm/tools/lld/lib/ReaderWriter/MachO/LayoutPass.cpp
Line
Count
Source (jump to first uncovered line)
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
1.28k
                            std::string &reason) {
179
1.28k
  const DefinedAtom *left = lc._atom.get();
180
1.28k
  const DefinedAtom *right = rc._atom.get();
181
1.28k
  if (left == right) {
182
44
    reason = "same";
183
44
    return false;
184
44
  }
185
1.24k
186
1.24k
  // Find the root of the chain if it is a part of a follow-on chain.
187
1.24k
  const DefinedAtom *leftRoot = lc._root;
188
1.24k
  const DefinedAtom *rightRoot = rc._root;
189
1.24k
190
1.24k
  // Sort atoms by their ordinal overrides only if they fall in the same
191
1.24k
  // chain.
192
1.24k
  if (leftRoot == rightRoot) {
193
4
    LLVM_DEBUG(reason = formatReason("override", lc._override, rc._override));
194
4
    return lc._override < rc._override;
195
4
  }
196
1.23k
197
1.23k
  // Sort same permissions together.
198
1.23k
  DefinedAtom::ContentPermissions leftPerms = leftRoot->permissions();
199
1.23k
  DefinedAtom::ContentPermissions rightPerms = rightRoot->permissions();
200
1.23k
201
1.23k
  if (leftPerms != rightPerms) {
202
660
    LLVM_DEBUG(
203
660
        reason = formatReason("contentPerms", (int)leftPerms, (int)rightPerms));
204
660
    return leftPerms < rightPerms;
205
660
  }
206
579
207
579
  // Sort same content types together.
208
579
  DefinedAtom::ContentType leftType = leftRoot->contentType();
209
579
  DefinedAtom::ContentType rightType = rightRoot->contentType();
210
579
211
579
  if (leftType != rightType) {
212
281
    LLVM_DEBUG(reason =
213
281
                   formatReason("contentType", (int)leftType, (int)rightType));
214
281
    return leftType < rightType;
215
281
  }
216
298
217
298
  // Use custom sorter if supplied.
218
298
  if (customSorter) {
219
298
    bool leftBeforeRight;
220
298
    if (customSorter(leftRoot, rightRoot, leftBeforeRight))
221
9
      return leftBeforeRight;
222
289
  }
223
289
224
289
  // Sort by .o order.
225
289
  const File *leftFile = &leftRoot->file();
226
289
  const File *rightFile = &rightRoot->file();
227
289
228
289
  if (leftFile != rightFile) {
229
24
    LLVM_DEBUG(reason = formatReason(".o order", (int)leftFile->ordinal(),
230
24
                                     (int)rightFile->ordinal()));
231
24
    return leftFile->ordinal() < rightFile->ordinal();
232
24
  }
233
265
234
265
  // Sort by atom order with .o file.
235
265
  uint64_t leftOrdinal = leftRoot->ordinal();
236
265
  uint64_t rightOrdinal = rightRoot->ordinal();
237
265
238
265
  if (leftOrdinal != rightOrdinal) {
239
265
    LLVM_DEBUG(reason = formatReason("ordinal", (int)leftRoot->ordinal(),
240
265
                                     (int)rightRoot->ordinal()));
241
265
    return leftOrdinal < rightOrdinal;
242
265
  }
243
0
244
0
  llvm::errs() << "Unordered: <" << left->name() << "> <"
245
0
               << right->name() << ">\n";
246
0
  llvm_unreachable("Atoms with Same Ordinal!");
247
0
}
248
249
static bool compareAtoms(const LayoutPass::SortKey &lc,
250
                         const LayoutPass::SortKey &rc,
251
1.28k
                         LayoutPass::SortOverride customSorter) {
252
1.28k
  std::string reason;
253
1.28k
  bool result = compareAtomsSub(lc, rc, customSorter, reason);
254
1.28k
  LLVM_DEBUG({
255
1.28k
    StringRef comp = result ? "<" : ">=";
256
1.28k
    llvm::dbgs() << "Layout: '" << lc._atom.get()->name()
257
1.28k
                 << "' " << comp << " '"
258
1.28k
                 << rc._atom.get()->name() << "' (" << reason << ")\n";
259
1.28k
  });
260
1.28k
  return result;
261
1.28k
}
262
263
LayoutPass::LayoutPass(const Registry &registry, SortOverride sorter)
264
170
    : _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
0
    const DefinedAtom *targetAtom) {
270
0
  // Start from the beginning of the chain and follow the chain until
271
0
  // we find the targetChain.
272
0
  const DefinedAtom *atom = _followOnRoots[targetAtom];
273
0
  while (true) {
274
0
    const DefinedAtom *prevAtom = atom;
275
0
    AtomToAtomT::iterator targetFollowOnAtomsIter = _followOnNexts.find(atom);
276
0
    // The target atom must be in the chain of its root.
277
0
    assert(targetFollowOnAtomsIter != _followOnNexts.end());
278
0
    atom = targetFollowOnAtomsIter->second;
279
0
    if (atom == targetAtom)
280
0
      return prevAtom;
281
0
  }
282
0
}
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
0
bool LayoutPass::checkAllPrevAtomsZeroSize(const DefinedAtom *targetAtom) {
290
0
  const DefinedAtom *atom = _followOnRoots[targetAtom];
291
0
  while (true) {
292
0
    if (atom == targetAtom)
293
0
      return true;
294
0
    if (atom->size() != 0)
295
0
      // TODO: print warning that an impossible layout is being desired by the
296
0
      // user.
297
0
      return false;
298
0
    AtomToAtomT::iterator targetFollowOnAtomsIter = _followOnNexts.find(atom);
299
0
    // The target atom must be in the chain of its root.
300
0
    assert(targetFollowOnAtomsIter != _followOnNexts.end());
301
0
    atom = targetFollowOnAtomsIter->second;
302
0
  }
303
0
}
304
305
// Set the root of all atoms in targetAtom's chain to the given root.
306
void LayoutPass::setChainRoot(const DefinedAtom *targetAtom,
307
0
                              const DefinedAtom *root) {
308
0
  // Walk through the followon chain and override each node's root.
309
0
  while (true) {
310
0
    _followOnRoots[targetAtom] = root;
311
0
    AtomToAtomT::iterator targetFollowOnAtomsIter =
312
0
        _followOnNexts.find(targetAtom);
313
0
    if (targetFollowOnAtomsIter == _followOnNexts.end())
314
0
      return;
315
0
    targetAtom = targetFollowOnAtomsIter->second;
316
0
  }
317
0
}
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
170
void LayoutPass::buildFollowOnTable(const File::AtomRange<DefinedAtom> &range) {
335
170
  ScopedTask task(getDefaultDomain(), "LayoutPass::buildFollowOnTable");
336
170
  // Set the initial size of the followon and the followonNext hash to the
337
170
  // number of atoms that we have.
338
170
  _followOnRoots.reserve(range.size());
339
170
  _followOnNexts.reserve(range.size());
340
732
  for (const DefinedAtom *ai : range) {
341
732
    for (const Reference *r : *ai) {
342
596
      if (r->kindNamespace() != lld::Reference::KindNamespace::all ||
343
596
          
r->kindValue() != lld::Reference::kindLayoutAfter4
)
344
592
        continue;
345
4
      const DefinedAtom *targetAtom = dyn_cast<DefinedAtom>(r->target());
346
4
      _followOnNexts[ai] = targetAtom;
347
4
348
4
      // If we find a followon for the first time, let's make that atom as the
349
4
      // root atom.
350
4
      if (_followOnRoots.count(ai) == 0)
351
3
        _followOnRoots[ai] = ai;
352
4
353
4
      auto iter = _followOnRoots.find(targetAtom);
354
4
      if (iter == _followOnRoots.end()) {
355
4
        // If the targetAtom is not a root of any chain, let's make the root of
356
4
        // the targetAtom to the root of the current chain.
357
4
358
4
        // The expression m[i] = m[j] where m is a DenseMap and i != j is not
359
4
        // safe. m[j] returns a reference, which would be invalidated when a
360
4
        // rehashing occurs. If rehashing occurs to make room for m[i], m[j]
361
4
        // becomes invalid, and that invalid reference would be used as the RHS
362
4
        // value of the expression.
363
4
        // Copy the value to workaround.
364
4
        const DefinedAtom *tmp = _followOnRoots[ai];
365
4
        _followOnRoots[targetAtom] = tmp;
366
4
        continue;
367
4
      }
368
0
      if (iter->second == targetAtom) {
369
0
        // If the targetAtom is the root of a chain, the chain becomes part of
370
0
        // the current chain. Rewrite the subchain's root to the current
371
0
        // chain's root.
372
0
        setChainRoot(targetAtom, _followOnRoots[ai]);
373
0
        continue;
374
0
      }
375
0
      // The targetAtom is already a part of a chain. If the current atom is
376
0
      // of size zero, we can insert it in the middle of the chain just
377
0
      // before the target atom, while not breaking other atom's followon
378
0
      // relationships. If it's not, we can only insert the current atom at
379
0
      // the beginning of the chain. All the atoms followed by the target
380
0
      // atom must be of size zero in that case to satisfy the followon
381
0
      // relationships.
382
0
      size_t currentAtomSize = ai->size();
383
0
      if (currentAtomSize == 0) {
384
0
        const DefinedAtom *targetPrevAtom = findAtomFollowedBy(targetAtom);
385
0
        _followOnNexts[targetPrevAtom] = ai;
386
0
        const DefinedAtom *tmp = _followOnRoots[targetPrevAtom];
387
0
        _followOnRoots[ai] = tmp;
388
0
        continue;
389
0
      }
390
0
      if (!checkAllPrevAtomsZeroSize(targetAtom))
391
0
        break;
392
0
      _followOnNexts[ai] = _followOnRoots[targetAtom];
393
0
      setChainRoot(_followOnRoots[targetAtom], _followOnRoots[ai]);
394
0
    }
395
732
  }
396
170
}
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
170
LayoutPass::buildOrdinalOverrideMap(const File::AtomRange<DefinedAtom> &range) {
404
170
  ScopedTask task(getDefaultDomain(), "LayoutPass::buildOrdinalOverrideMap");
405
170
  uint64_t index = 0;
406
732
  for (const DefinedAtom *ai : range) {
407
732
    const DefinedAtom *atom = ai;
408
732
    if (_ordinalOverrideMap.find(atom) != _ordinalOverrideMap.end())
409
4
      continue;
410
728
    AtomToAtomT::iterator start = _followOnRoots.find(atom);
411
728
    if (start == _followOnRoots.end())
412
725
      continue;
413
10
    
for (const DefinedAtom *nextAtom = start->second; 3
nextAtom;
414
7
         nextAtom = _followOnNexts[nextAtom]) {
415
7
      AtomToOrdinalT::iterator pos = _ordinalOverrideMap.find(nextAtom);
416
7
      if (pos == _ordinalOverrideMap.end())
417
7
        _ordinalOverrideMap[nextAtom] = index++;
418
7
    }
419
3
  }
420
170
}
421
422
std::vector<LayoutPass::SortKey>
423
170
LayoutPass::decorate(File::AtomRange<DefinedAtom> &atomRange) const {
424
170
  std::vector<SortKey> ret;
425
732
  for (OwningAtomPtr<DefinedAtom> &atom : atomRange.owning_ptrs()) {
426
732
    auto ri = _followOnRoots.find(atom.get());
427
732
    auto oi = _ordinalOverrideMap.find(atom.get());
428
732
    const auto *root = (ri == _followOnRoots.end()) ? 
atom.get()725
:
ri->second7
;
429
732
    uint64_t override = (oi == _ordinalOverrideMap.end()) ? 
0725
:
oi->second7
;
430
732
    ret.push_back(SortKey(std::move(atom), root, override));
431
732
  }
432
170
  return ret;
433
170
}
434
435
void LayoutPass::undecorate(File::AtomRange<DefinedAtom> &atomRange,
436
170
                            std::vector<SortKey> &keys) const {
437
170
  size_t i = 0;
438
170
  for (SortKey &k : keys)
439
732
    atomRange[i++] = std::move(k._atom);
440
170
}
441
442
/// Perform the actual pass
443
170
llvm::Error LayoutPass::perform(SimpleFile &mergedFile) {
444
170
  LLVM_DEBUG(llvm::dbgs() << "******** Laying out atoms:\n");
445
170
  // sort the atoms
446
170
  ScopedTask task(getDefaultDomain(), "LayoutPass");
447
170
  File::AtomRange<DefinedAtom> atomRange = mergedFile.defined();
448
170
449
170
  // Build follow on tables
450
170
  buildFollowOnTable(atomRange);
451
170
452
170
  // Check the structure of followon graph if running in debug mode.
453
170
  LLVM_DEBUG(checkFollowonChain(atomRange));
454
170
455
170
  // Build override maps
456
170
  buildOrdinalOverrideMap(atomRange);
457
170
458
170
  LLVM_DEBUG({
459
170
    llvm::dbgs() << "unsorted atoms:\n";
460
170
    printDefinedAtoms(atomRange);
461
170
  });
462
170
463
170
  std::vector<LayoutPass::SortKey> vec = decorate(atomRange);
464
170
  sort(llvm::parallel::par, vec.begin(), vec.end(),
465
1.28k
       [&](const LayoutPass::SortKey &l, const LayoutPass::SortKey &r) -> bool {
466
1.28k
         return compareAtoms(l, r, _customSorter);
467
1.28k
       });
468
170
  LLVM_DEBUG(checkTransitivity(vec, _customSorter));
469
170
  undecorate(atomRange, vec);
470
170
471
170
  LLVM_DEBUG({
472
170
    llvm::dbgs() << "sorted atoms:\n";
473
170
    printDefinedAtoms(atomRange);
474
170
  });
475
170
476
170
  LLVM_DEBUG(llvm::dbgs() << "******** Finished laying out atoms\n");
477
170
  return llvm::Error::success();
478
170
}
479
480
170
void addLayoutPass(PassManager &pm, const MachOLinkingContext &ctx) {
481
170
  pm.add(llvm::make_unique<LayoutPass>(
482
170
      ctx.registry(), [&](const DefinedAtom * left, const DefinedAtom * right,
483
298
                          bool & leftBeforeRight) ->bool {
484
298
    return ctx.customAtomOrderer(left, right, leftBeforeRight);
485
298
  }));
486
170
}
487
488
} // namespace mach_o
489
} // namespace lld