1 //===------ lib/ReaderWriter/MachO/LayoutPass.h - Handles Layout of atoms -===//
2 //
3 //                             The LLVM Linker
4 //
5 // This file is distributed under the University of Illinois Open Source
6 // License. See LICENSE.TXT for details.
7 //
8 //===----------------------------------------------------------------------===//
9 
10 #ifndef LLD_READER_WRITER_MACHO_LAYOUT_PASS_H
11 #define LLD_READER_WRITER_MACHO_LAYOUT_PASS_H
12 
13 #include "lld/Core/File.h"
14 #include "lld/Core/Pass.h"
15 #include "lld/Core/Reader.h"
16 #include "lld/Core/Simple.h"
17 #include "llvm/ADT/DenseMap.h"
18 #include <map>
19 #include <string>
20 #include <vector>
21 
22 namespace lld {
23 class DefinedAtom;
24 class SimpleFile;
25 
26 namespace mach_o {
27 
28 /// This linker pass does the layout of the atoms. The pass is done after the
29 /// order their .o files were found on the command line, then by order of the
30 /// atoms (address) in the .o file.  But some atoms have a preferred location
31 /// in their section (such as pinned to the start or end of the section), so
32 /// the sort must take that into account too.
33 class LayoutPass : public Pass {
34 public:
35   struct SortKey {
SortKeySortKey36     SortKey(OwningAtomPtr<DefinedAtom> &&atom,
37             const DefinedAtom *root, uint64_t override)
38     : _atom(std::move(atom)), _root(root), _override(override) {}
39     OwningAtomPtr<DefinedAtom> _atom;
40     const DefinedAtom *_root;
41     uint64_t _override;
42 
43     // Note, these are only here to appease MSVC bots which didn't like
44     // the same methods being implemented/deleted in OwningAtomPtr.
SortKeySortKey45     SortKey(SortKey &&key) : _atom(std::move(key._atom)), _root(key._root),
46                              _override(key._override) {
47       key._root = nullptr;
48     }
49 
50     SortKey &operator=(SortKey &&key) {
51       _atom = std::move(key._atom);
52       _root = key._root;
53       key._root = nullptr;
54       _override = key._override;
55       return *this;
56     }
57 
58   private:
59     SortKey(const SortKey &) = delete;
60     void operator=(const SortKey&) = delete;
61   };
62 
63   typedef std::function<bool (const DefinedAtom *left, const DefinedAtom *right,
64                               bool &leftBeforeRight)> SortOverride;
65 
66   LayoutPass(const Registry &registry, SortOverride sorter);
67 
68   /// Sorts atoms in mergedFile by content type then by command line order.
69   llvm::Error perform(SimpleFile &mergedFile) override;
70 
71   ~LayoutPass() override = default;
72 
73 private:
74   // Build the followOn atoms chain as specified by the kindLayoutAfter
75   // reference type
76   void buildFollowOnTable(const File::AtomRange<DefinedAtom> &range);
77 
78   // Build a map of Atoms to ordinals for sorting the atoms
79   void buildOrdinalOverrideMap(const File::AtomRange<DefinedAtom> &range);
80 
81   const Registry &_registry;
82   SortOverride _customSorter;
83 
84   typedef llvm::DenseMap<const DefinedAtom *, const DefinedAtom *> AtomToAtomT;
85   typedef llvm::DenseMap<const DefinedAtom *, uint64_t> AtomToOrdinalT;
86 
87   // A map to be used to sort atoms. It represents the order of atoms in the
88   // result; if Atom X is mapped to atom Y in this map, X will be located
89   // immediately before Y in the output file. Y might be mapped to another
90   // atom, constructing a follow-on chain. An atom cannot be mapped to more
91   // than one atom unless all but one atom are of size zero.
92   AtomToAtomT _followOnNexts;
93 
94   // A map to be used to sort atoms. It's a map from an atom to its root of
95   // follow-on chain. A root atom is mapped to itself. If an atom is not in
96   // _followOnNexts, the atom is not in this map, and vice versa.
97   AtomToAtomT _followOnRoots;
98 
99   AtomToOrdinalT _ordinalOverrideMap;
100 
101   // Helper methods for buildFollowOnTable().
102   const DefinedAtom *findAtomFollowedBy(const DefinedAtom *targetAtom);
103   bool checkAllPrevAtomsZeroSize(const DefinedAtom *targetAtom);
104 
105   void setChainRoot(const DefinedAtom *targetAtom, const DefinedAtom *root);
106 
107   std::vector<SortKey> decorate(File::AtomRange<DefinedAtom> &atomRange) const;
108 
109   void undecorate(File::AtomRange<DefinedAtom> &atomRange,
110                   std::vector<SortKey> &keys) const;
111 
112   // Check if the follow-on graph is a correct structure. For debugging only.
113   void checkFollowonChain(const File::AtomRange<DefinedAtom> &range);
114 };
115 
116 } // namespace mach_o
117 } // namespace lld
118 
119 #endif // LLD_READER_WRITER_MACHO_LAYOUT_PASS_H
120