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
26namespace llvm {
27namespace jitlink {
28
29class MachOLinkGraphBuilder {
30public:
31 virtual ~MachOLinkGraphBuilder();
32 Expected<std::unique_ptr<LinkGraph>> buildGraph();
33
34protected:
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,
87 std::shared_ptr<orc::SymbolStringPool> SSP, Triple TT,
88 SubtargetFeatures Features,
89 LinkGraph::GetEdgeKindNameFunction GetEdgeKindName);
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(Val: 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(Val: Index);
121 if (I == IndexToSection.end())
122 return make_error<JITLinkError>(Args: "No section recorded for index " +
123 formatv(Fmt: "{0:d}", Vals&: 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(Val: Index);
132 if (I == IndexToSymbol.end())
133 return make_error<JITLinkError>(Args: "No symbol at index " +
134 formatv(Fmt: "{0:d}", Vals&: 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(x: Address);
144 if (I == NSec.CanonicalSymbols.begin())
145 return nullptr;
146 return std::prev(x: 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>(Args: "No symbol covering address " +
158 formatv(Fmt: "{0:x16}", Vals&: 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(Rel: 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
182private:
183 static unsigned getPointerSize(const object::MachOObjectFile &Obj);
184 static llvm::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} // end namespace jitlink
240} // end namespace llvm
241
242#endif // LIB_EXECUTIONENGINE_JITLINK_MACHOLINKGRAPHBUILDER_H
243