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 
20 #include "EHFrameSupportImpl.h"
21 #include "JITLinkGeneric.h"
22 #include "llvm/Object/MachO.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(Optional<StringRef> Name, uint64_t Value, uint8_t Type,
41                      uint8_t Sect, uint16_t Desc, Linkage L, Scope S)
42         : Name(Name), Value(Value), Type(Type), Sect(Sect), Desc(Desc), L(L),
43           S(S) {
44       assert((!Name || !Name->empty()) && "Name must be none or non-empty");
45     }
46 
47   public:
48     NormalizedSymbol(const NormalizedSymbol &) = delete;
49     NormalizedSymbol &operator=(const NormalizedSymbol &) = delete;
50     NormalizedSymbol(NormalizedSymbol &&) = delete;
51     NormalizedSymbol &operator=(NormalizedSymbol &&) = delete;
52 
53     Optional<StringRef> Name;
54     uint64_t Value = 0;
55     uint8_t Type = 0;
56     uint8_t Sect = 0;
57     uint16_t Desc = 0;
58     Linkage L = Linkage::Strong;
59     Scope S = Scope::Default;
60     Symbol *GraphSymbol = nullptr;
61   };
62 
63   class NormalizedSection {
64     friend class MachOLinkGraphBuilder;
65 
66   private:
67     NormalizedSection() = default;
68 
69   public:
70     Section *GraphSection = nullptr;
71     uint64_t Address = 0;
72     uint64_t Size = 0;
73     uint64_t Alignment = 0;
74     uint32_t Flags = 0;
75     const char *Data = nullptr;
76   };
77 
78   using SectionParserFunction = std::function<Error(NormalizedSection &S)>;
79 
80   MachOLinkGraphBuilder(const object::MachOObjectFile &Obj);
81 
82   LinkGraph &getGraph() const { return *G; }
83 
84   const object::MachOObjectFile &getObject() const { return Obj; }
85 
86   void addCustomSectionParser(StringRef SectionName,
87                               SectionParserFunction Parse);
88 
89   virtual Error addRelocations() = 0;
90 
91   /// Create a symbol.
92   template <typename... ArgTs>
93   NormalizedSymbol &createNormalizedSymbol(ArgTs &&... Args) {
94     NormalizedSymbol *Sym = reinterpret_cast<NormalizedSymbol *>(
95         Allocator.Allocate<NormalizedSymbol>());
96     new (Sym) NormalizedSymbol(std::forward<ArgTs>(Args)...);
97     return *Sym;
98   }
99 
100   /// Index is zero-based (MachO section indexes are usually one-based) and
101   /// assumed to be in-range. Client is responsible for checking.
102   NormalizedSection &getSectionByIndex(unsigned Index) {
103     auto I = IndexToSection.find(Index);
104     assert(I != IndexToSection.end() && "No section recorded at index");
105     return I->second;
106   }
107 
108   /// Try to get the section at the given index. Will return an error if the
109   /// given index is out of range, or if no section has been added for the given
110   /// index.
111   Expected<NormalizedSection &> findSectionByIndex(unsigned Index) {
112     auto I = IndexToSection.find(Index);
113     if (I == IndexToSection.end())
114       return make_error<JITLinkError>("No section recorded for index " +
115                                       formatv("{0:u}", Index));
116     return I->second;
117   }
118 
119   /// Try to get the symbol at the given index. Will return an error if the
120   /// given index is out of range, or if no symbol has been added for the given
121   /// index.
122   Expected<NormalizedSymbol &> findSymbolByIndex(uint64_t Index) {
123     if (Index >= IndexToSymbol.size())
124       return make_error<JITLinkError>("Symbol index out of range");
125     auto *Sym = IndexToSymbol[Index];
126     if (!Sym)
127       return make_error<JITLinkError>("No symbol at index " +
128                                       formatv("{0:u}", Index));
129     return *Sym;
130   }
131 
132   /// Returns the symbol with the highest address not greater than the search
133   /// address, or null if no such symbol exists.
134   Symbol *getSymbolByAddress(JITTargetAddress Address) {
135     auto I = AddrToCanonicalSymbol.upper_bound(Address);
136     if (I == AddrToCanonicalSymbol.begin())
137       return nullptr;
138     return std::prev(I)->second;
139   }
140 
141   /// Returns the symbol with the highest address not greater than the search
142   /// address, or an error if no such symbol exists.
143   Expected<Symbol &> findSymbolByAddress(JITTargetAddress Address) {
144     auto *Sym = getSymbolByAddress(Address);
145     if (Sym)
146       if (Address < Sym->getAddress() + Sym->getSize())
147         return *Sym;
148     return make_error<JITLinkError>("No symbol covering address " +
149                                     formatv("{0:x16}", Address));
150   }
151 
152   static Linkage getLinkage(uint16_t Desc);
153   static Scope getScope(StringRef Name, uint8_t Type);
154   static bool isAltEntry(const NormalizedSymbol &NSym);
155 
156   MachO::relocation_info
157   getRelocationInfo(const object::relocation_iterator RelItr) {
158     MachO::any_relocation_info ARI =
159         getObject().getRelocation(RelItr->getRawDataRefImpl());
160     MachO::relocation_info RI;
161     RI.r_address = ARI.r_word0;
162     RI.r_symbolnum = ARI.r_word1 & 0xffffff;
163     RI.r_pcrel = (ARI.r_word1 >> 24) & 1;
164     RI.r_length = (ARI.r_word1 >> 25) & 3;
165     RI.r_extern = (ARI.r_word1 >> 27) & 1;
166     RI.r_type = (ARI.r_word1 >> 28);
167     return RI;
168   }
169 
170 private:
171   static unsigned getPointerSize(const object::MachOObjectFile &Obj);
172   static support::endianness getEndianness(const object::MachOObjectFile &Obj);
173 
174   void setCanonicalSymbol(Symbol &Sym) {
175     auto *&CanonicalSymEntry = AddrToCanonicalSymbol[Sym.getAddress()];
176     // There should be no symbol at this address, or, if there is,
177     // it should be a zero-sized symbol from an empty section (which
178     // we can safely override).
179     assert((!CanonicalSymEntry || CanonicalSymEntry->getSize() == 0) &&
180            "Duplicate canonical symbol at address");
181     CanonicalSymEntry = &Sym;
182   }
183 
184   Section &getCommonSection();
185   void addSectionStartSymAndBlock(Section &GraphSec, uint64_t Address,
186                                   const char *Data, uint64_t Size,
187                                   uint32_t Alignment, bool IsLive);
188 
189   Error createNormalizedSections();
190   Error createNormalizedSymbols();
191 
192   /// Create graph blocks and symbols for externals, absolutes, commons and
193   /// all defined symbols in sections without custom parsers.
194   Error graphifyRegularSymbols();
195 
196   /// Create graph blocks and symbols for all sections.
197   Error graphifySectionsWithCustomParsers();
198 
199   // Put the BumpPtrAllocator first so that we don't free any of the underlying
200   // memory until the Symbol/Addressable destructors have been run.
201   BumpPtrAllocator Allocator;
202 
203   const object::MachOObjectFile &Obj;
204   std::unique_ptr<LinkGraph> G;
205 
206   DenseMap<unsigned, NormalizedSection> IndexToSection;
207   Section *CommonSection = nullptr;
208 
209   DenseMap<uint32_t, NormalizedSymbol *> IndexToSymbol;
210   std::map<JITTargetAddress, Symbol *> AddrToCanonicalSymbol;
211   StringMap<SectionParserFunction> CustomSectionParserFunctions;
212 };
213 
214 } // end namespace jitlink
215 } // end namespace llvm
216 
217 #endif // LIB_EXECUTIONENGINE_JITLINK_MACHOLINKGRAPHBUILDER_H
218