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