1 //===----- MachOLinkGraphBuilder.h - MachO LinkGraph builder ----*- C++ -*-===//
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 // Generic MachO LinkGraph building code.
10 //
11 //===----------------------------------------------------------------------===//
12 
13 #ifndef LIB_EXECUTIONENGINE_JITLINK_MACHOLINKGRAPHBUILDER_H
14 #define LIB_EXECUTIONENGINE_JITLINK_MACHOLINKGRAPHBUILDER_H
15 
16 #include "llvm/ADT/DenseMap.h"
17 #include "llvm/ADT/StringMap.h"
18 #include "llvm/ExecutionEngine/JITLink/JITLink.h"
19 #include "llvm/Object/MachO.h"
20 
21 #include "EHFrameSupportImpl.h"
22 #include "JITLinkGeneric.h"
23 
24 #include <list>
25 
26 namespace llvm {
27 namespace jitlink {
28 
29 class MachOLinkGraphBuilder {
30 public:
31   virtual ~MachOLinkGraphBuilder();
32   Expected<std::unique_ptr<LinkGraph>> buildGraph();
33 
34 protected:
35 
36   struct NormalizedSymbol {
37     friend class MachOLinkGraphBuilder;
38 
39   private:
40     NormalizedSymbol(std::optional<StringRef> Name, uint64_t Value,
41                      uint8_t Type, uint8_t Sect, uint16_t Desc, Linkage L,
42                      Scope S)
43         : Name(Name), Value(Value), Type(Type), Sect(Sect), Desc(Desc), L(L),
44           S(S) {
45       assert((!Name || !Name->empty()) && "Name must be none or non-empty");
46     }
47 
48   public:
49     NormalizedSymbol(const NormalizedSymbol &) = delete;
50     NormalizedSymbol &operator=(const NormalizedSymbol &) = delete;
51     NormalizedSymbol(NormalizedSymbol &&) = delete;
52     NormalizedSymbol &operator=(NormalizedSymbol &&) = delete;
53 
54     std::optional<StringRef> Name;
55     uint64_t Value = 0;
56     uint8_t Type = 0;
57     uint8_t Sect = 0;
58     uint16_t Desc = 0;
59     Linkage L = Linkage::Strong;
60     Scope S = Scope::Default;
61     Symbol *GraphSymbol = nullptr;
62   };
63 
64   // Normalized section representation. Section and segment names are guaranteed
65   // to be null-terminated, hence the extra bytes on SegName and SectName.
66   class NormalizedSection {
67     friend class MachOLinkGraphBuilder;
68 
69   private:
70     NormalizedSection() = default;
71 
72   public:
73     char SectName[17];
74     char SegName[17];
75     orc::ExecutorAddr Address;
76     uint64_t Size = 0;
77     uint64_t Alignment = 0;
78     uint32_t Flags = 0;
79     const char *Data = nullptr;
80     Section *GraphSection = nullptr;
81     std::map<orc::ExecutorAddr, Symbol *> CanonicalSymbols;
82   };
83 
84   using SectionParserFunction = std::function<Error(NormalizedSection &S)>;
85 
86   MachOLinkGraphBuilder(const object::MachOObjectFile &Obj, Triple TT,
87                         SubtargetFeatures Features,
88                         LinkGraph::GetEdgeKindNameFunction GetEdgeKindName);
89 
90   LinkGraph &getGraph() const { return *G; }
91 
92   const object::MachOObjectFile &getObject() const { return Obj; }
93 
94   void addCustomSectionParser(StringRef SectionName,
95                               SectionParserFunction Parse);
96 
97   virtual Error addRelocations() = 0;
98 
99   /// Create a symbol.
100   template <typename... ArgTs>
101   NormalizedSymbol &createNormalizedSymbol(ArgTs &&... Args) {
102     NormalizedSymbol *Sym = reinterpret_cast<NormalizedSymbol *>(
103         Allocator.Allocate<NormalizedSymbol>());
104     new (Sym) NormalizedSymbol(std::forward<ArgTs>(Args)...);
105     return *Sym;
106   }
107 
108   /// Index is zero-based (MachO section indexes are usually one-based) and
109   /// assumed to be in-range. Client is responsible for checking.
110   NormalizedSection &getSectionByIndex(unsigned Index) {
111     auto I = IndexToSection.find(Index);
112     assert(I != IndexToSection.end() && "No section recorded at index");
113     return I->second;
114   }
115 
116   /// Try to get the section at the given index. Will return an error if the
117   /// given index is out of range, or if no section has been added for the given
118   /// index.
119   Expected<NormalizedSection &> findSectionByIndex(unsigned Index) {
120     auto I = IndexToSection.find(Index);
121     if (I == IndexToSection.end())
122       return make_error<JITLinkError>("No section recorded for index " +
123                                       formatv("{0:d}", Index));
124     return I->second;
125   }
126 
127   /// Try to get the symbol at the given index. Will return an error if the
128   /// given index is out of range, or if no symbol has been added for the given
129   /// index.
130   Expected<NormalizedSymbol &> findSymbolByIndex(uint64_t Index) {
131     auto I = IndexToSymbol.find(Index);
132     if (I == IndexToSymbol.end())
133       return make_error<JITLinkError>("No symbol at index " +
134                                       formatv("{0:d}", Index));
135     assert(I->second && "Null symbol at index");
136     return *I->second;
137   }
138 
139   /// Returns the symbol with the highest address not greater than the search
140   /// address, or null if no such symbol exists.
141   Symbol *getSymbolByAddress(NormalizedSection &NSec,
142                              orc::ExecutorAddr Address) {
143     auto I = NSec.CanonicalSymbols.upper_bound(Address);
144     if (I == NSec.CanonicalSymbols.begin())
145       return nullptr;
146     return std::prev(I)->second;
147   }
148 
149   /// Returns the symbol with the highest address not greater than the search
150   /// address, or an error if no such symbol exists.
151   Expected<Symbol &> findSymbolByAddress(NormalizedSection &NSec,
152                                          orc::ExecutorAddr Address) {
153     auto *Sym = getSymbolByAddress(NSec, Address);
154     if (Sym)
155       if (Address <= Sym->getAddress() + Sym->getSize())
156         return *Sym;
157     return make_error<JITLinkError>("No symbol covering address " +
158                                     formatv("{0:x16}", Address));
159   }
160 
161   static Linkage getLinkage(uint16_t Desc);
162   static Scope getScope(StringRef Name, uint8_t Type);
163   static bool isAltEntry(const NormalizedSymbol &NSym);
164 
165   static bool isDebugSection(const NormalizedSection &NSec);
166   static bool isZeroFillSection(const NormalizedSection &NSec);
167 
168   MachO::relocation_info
169   getRelocationInfo(const object::relocation_iterator RelItr) {
170     MachO::any_relocation_info ARI =
171         getObject().getRelocation(RelItr->getRawDataRefImpl());
172     MachO::relocation_info RI;
173     RI.r_address = ARI.r_word0;
174     RI.r_symbolnum = ARI.r_word1 & 0xffffff;
175     RI.r_pcrel = (ARI.r_word1 >> 24) & 1;
176     RI.r_length = (ARI.r_word1 >> 25) & 3;
177     RI.r_extern = (ARI.r_word1 >> 27) & 1;
178     RI.r_type = (ARI.r_word1 >> 28);
179     return RI;
180   }
181 
182 private:
183   static unsigned getPointerSize(const object::MachOObjectFile &Obj);
184   static support::endianness getEndianness(const object::MachOObjectFile &Obj);
185 
186   void setCanonicalSymbol(NormalizedSection &NSec, Symbol &Sym) {
187     auto *&CanonicalSymEntry = NSec.CanonicalSymbols[Sym.getAddress()];
188     // There should be no symbol at this address, or, if there is,
189     // it should be a zero-sized symbol from an empty section (which
190     // we can safely override).
191     assert((!CanonicalSymEntry || CanonicalSymEntry->getSize() == 0) &&
192            "Duplicate canonical symbol at address");
193     CanonicalSymEntry = &Sym;
194   }
195 
196   Section &getCommonSection();
197   void addSectionStartSymAndBlock(unsigned SecIndex, Section &GraphSec,
198                                   orc::ExecutorAddr Address, const char *Data,
199                                   orc::ExecutorAddrDiff Size,
200                                   uint32_t Alignment, bool IsLive);
201 
202   Error createNormalizedSections();
203   Error createNormalizedSymbols();
204 
205   /// Create graph blocks and symbols for externals, absolutes, commons and
206   /// all defined symbols in sections without custom parsers.
207   Error graphifyRegularSymbols();
208 
209   /// Create and return a graph symbol for the given normalized symbol.
210   ///
211   /// NSym's GraphSymbol member will be updated to point at the newly created
212   /// symbol.
213   Symbol &createStandardGraphSymbol(NormalizedSymbol &Sym, Block &B,
214                                     size_t Size, bool IsText,
215                                     bool IsNoDeadStrip, bool IsCanonical);
216 
217   /// Create graph blocks and symbols for all sections.
218   Error graphifySectionsWithCustomParsers();
219 
220   /// Graphify cstring section.
221   Error graphifyCStringSection(NormalizedSection &NSec,
222                                std::vector<NormalizedSymbol *> NSyms);
223 
224   // Put the BumpPtrAllocator first so that we don't free any of the underlying
225   // memory until the Symbol/Addressable destructors have been run.
226   BumpPtrAllocator Allocator;
227 
228   const object::MachOObjectFile &Obj;
229   std::unique_ptr<LinkGraph> G;
230 
231   bool SubsectionsViaSymbols = false;
232   DenseMap<unsigned, NormalizedSection> IndexToSection;
233   Section *CommonSection = nullptr;
234 
235   DenseMap<uint32_t, NormalizedSymbol *> IndexToSymbol;
236   StringMap<SectionParserFunction> CustomSectionParserFunctions;
237 };
238 
239 /// A pass to split up __LD,__compact_unwind sections.
240 class CompactUnwindSplitter {
241 public:
242   CompactUnwindSplitter(StringRef CompactUnwindSectionName)
243       : CompactUnwindSectionName(CompactUnwindSectionName) {}
244   Error operator()(LinkGraph &G);
245 
246 private:
247   StringRef CompactUnwindSectionName;
248 };
249 
250 } // end namespace jitlink
251 } // end namespace llvm
252 
253 #endif // LIB_EXECUTIONENGINE_JITLINK_MACHOLINKGRAPHBUILDER_H
254