1//=--------- MachOLinkGraphBuilder.cpp - MachO LinkGraph builder ----------===//
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#include "MachOLinkGraphBuilder.h"
14#include <optional>
15
16#define DEBUG_TYPE "jitlink"
17
18static const char *CommonSectionName = "__common";
19
20namespace llvm {
21namespace jitlink {
22
23MachOLinkGraphBuilder::~MachOLinkGraphBuilder() = default;
24
25Expected<std::unique_ptr<LinkGraph>> MachOLinkGraphBuilder::buildGraph() {
26
27 // We only operate on relocatable objects.
28 if (!Obj.isRelocatableObject())
29 return make_error<JITLinkError>(Args: "Object is not a relocatable MachO");
30
31 if (auto Err = createNormalizedSections())
32 return std::move(Err);
33
34 if (auto Err = createNormalizedSymbols())
35 return std::move(Err);
36
37 if (auto Err = graphifyRegularSymbols())
38 return std::move(Err);
39
40 if (auto Err = graphifySectionsWithCustomParsers())
41 return std::move(Err);
42
43 if (auto Err = addRelocations())
44 return std::move(Err);
45
46 return std::move(G);
47}
48
49MachOLinkGraphBuilder::MachOLinkGraphBuilder(
50 const object::MachOObjectFile &Obj, Triple TT, SubtargetFeatures Features,
51 LinkGraph::GetEdgeKindNameFunction GetEdgeKindName)
52 : Obj(Obj),
53 G(std::make_unique<LinkGraph>(args: std::string(Obj.getFileName()),
54 args: std::move(TT), args: std::move(Features),
55 args: getPointerSize(Obj), args: getEndianness(Obj),
56 args: std::move(GetEdgeKindName))) {
57 auto &MachHeader = Obj.getHeader64();
58 SubsectionsViaSymbols = MachHeader.flags & MachO::MH_SUBSECTIONS_VIA_SYMBOLS;
59}
60
61void MachOLinkGraphBuilder::addCustomSectionParser(
62 StringRef SectionName, SectionParserFunction Parser) {
63 assert(!CustomSectionParserFunctions.count(SectionName) &&
64 "Custom parser for this section already exists");
65 CustomSectionParserFunctions[SectionName] = std::move(Parser);
66}
67
68Linkage MachOLinkGraphBuilder::getLinkage(uint16_t Desc) {
69 if ((Desc & MachO::N_WEAK_DEF) || (Desc & MachO::N_WEAK_REF))
70 return Linkage::Weak;
71 return Linkage::Strong;
72}
73
74Scope MachOLinkGraphBuilder::getScope(StringRef Name, uint8_t Type) {
75 if (Type & MachO::N_EXT) {
76 if ((Type & MachO::N_PEXT) || Name.starts_with(Prefix: "l"))
77 return Scope::Hidden;
78 else
79 return Scope::Default;
80 }
81 return Scope::Local;
82}
83
84bool MachOLinkGraphBuilder::isAltEntry(const NormalizedSymbol &NSym) {
85 return NSym.Desc & MachO::N_ALT_ENTRY;
86}
87
88bool MachOLinkGraphBuilder::isDebugSection(const NormalizedSection &NSec) {
89 return (NSec.Flags & MachO::S_ATTR_DEBUG &&
90 strcmp(s1: NSec.SegName, s2: "__DWARF") == 0);
91}
92
93bool MachOLinkGraphBuilder::isZeroFillSection(const NormalizedSection &NSec) {
94 switch (NSec.Flags & MachO::SECTION_TYPE) {
95 case MachO::S_ZEROFILL:
96 case MachO::S_GB_ZEROFILL:
97 case MachO::S_THREAD_LOCAL_ZEROFILL:
98 return true;
99 default:
100 return false;
101 }
102}
103
104unsigned
105MachOLinkGraphBuilder::getPointerSize(const object::MachOObjectFile &Obj) {
106 return Obj.is64Bit() ? 8 : 4;
107}
108
109llvm::endianness
110MachOLinkGraphBuilder::getEndianness(const object::MachOObjectFile &Obj) {
111 return Obj.isLittleEndian() ? llvm::endianness::little
112 : llvm::endianness::big;
113}
114
115Section &MachOLinkGraphBuilder::getCommonSection() {
116 if (!CommonSection)
117 CommonSection = &G->createSection(Name: CommonSectionName,
118 Prot: orc::MemProt::Read | orc::MemProt::Write);
119 return *CommonSection;
120}
121
122Error MachOLinkGraphBuilder::createNormalizedSections() {
123 // Build normalized sections. Verifies that section data is in-range (for
124 // sections with content) and that address ranges are non-overlapping.
125
126 LLVM_DEBUG(dbgs() << "Creating normalized sections...\n");
127
128 for (auto &SecRef : Obj.sections()) {
129 NormalizedSection NSec;
130 uint32_t DataOffset = 0;
131
132 auto SecIndex = Obj.getSectionIndex(Sec: SecRef.getRawDataRefImpl());
133
134 if (Obj.is64Bit()) {
135 const MachO::section_64 &Sec64 =
136 Obj.getSection64(DRI: SecRef.getRawDataRefImpl());
137
138 memcpy(dest: &NSec.SectName, src: &Sec64.sectname, n: 16);
139 NSec.SectName[16] = '\0';
140 memcpy(dest: &NSec.SegName, src: Sec64.segname, n: 16);
141 NSec.SegName[16] = '\0';
142
143 NSec.Address = orc::ExecutorAddr(Sec64.addr);
144 NSec.Size = Sec64.size;
145 NSec.Alignment = 1ULL << Sec64.align;
146 NSec.Flags = Sec64.flags;
147 DataOffset = Sec64.offset;
148 } else {
149 const MachO::section &Sec32 = Obj.getSection(DRI: SecRef.getRawDataRefImpl());
150
151 memcpy(dest: &NSec.SectName, src: &Sec32.sectname, n: 16);
152 NSec.SectName[16] = '\0';
153 memcpy(dest: &NSec.SegName, src: Sec32.segname, n: 16);
154 NSec.SegName[16] = '\0';
155
156 NSec.Address = orc::ExecutorAddr(Sec32.addr);
157 NSec.Size = Sec32.size;
158 NSec.Alignment = 1ULL << Sec32.align;
159 NSec.Flags = Sec32.flags;
160 DataOffset = Sec32.offset;
161 }
162
163 LLVM_DEBUG({
164 dbgs() << " " << NSec.SegName << "," << NSec.SectName << ": "
165 << formatv("{0:x16}", NSec.Address) << " -- "
166 << formatv("{0:x16}", NSec.Address + NSec.Size)
167 << ", align: " << NSec.Alignment << ", index: " << SecIndex
168 << "\n";
169 });
170
171 // Get the section data if any.
172 if (!isZeroFillSection(NSec)) {
173 if (DataOffset + NSec.Size > Obj.getData().size())
174 return make_error<JITLinkError>(
175 Args: "Section data extends past end of file");
176
177 NSec.Data = Obj.getData().data() + DataOffset;
178 }
179
180 // Get prot flags.
181 // FIXME: Make sure this test is correct (it's probably missing cases
182 // as-is).
183 orc::MemProt Prot;
184 if (NSec.Flags & MachO::S_ATTR_PURE_INSTRUCTIONS)
185 Prot = orc::MemProt::Read | orc::MemProt::Exec;
186 else
187 Prot = orc::MemProt::Read | orc::MemProt::Write;
188
189 auto FullyQualifiedName =
190 G->allocateContent(Source: StringRef(NSec.SegName) + "," + NSec.SectName);
191 NSec.GraphSection = &G->createSection(
192 Name: StringRef(FullyQualifiedName.data(), FullyQualifiedName.size()), Prot);
193
194 // TODO: Are there any other criteria for NoAlloc lifetime?
195 if (NSec.Flags & MachO::S_ATTR_DEBUG)
196 NSec.GraphSection->setMemLifetime(orc::MemLifetime::NoAlloc);
197
198 IndexToSection.insert(KV: std::make_pair(x&: SecIndex, y: std::move(NSec)));
199 }
200
201 std::vector<NormalizedSection *> Sections;
202 Sections.reserve(n: IndexToSection.size());
203 for (auto &KV : IndexToSection)
204 Sections.push_back(x: &KV.second);
205
206 // If we didn't end up creating any sections then bail out. The code below
207 // assumes that we have at least one section.
208 if (Sections.empty())
209 return Error::success();
210
211 llvm::sort(C&: Sections,
212 Comp: [](const NormalizedSection *LHS, const NormalizedSection *RHS) {
213 assert(LHS && RHS && "Null section?");
214 if (LHS->Address != RHS->Address)
215 return LHS->Address < RHS->Address;
216 return LHS->Size < RHS->Size;
217 });
218
219 for (unsigned I = 0, E = Sections.size() - 1; I != E; ++I) {
220 auto &Cur = *Sections[I];
221 auto &Next = *Sections[I + 1];
222 if (Next.Address < Cur.Address + Cur.Size)
223 return make_error<JITLinkError>(
224 Args: "Address range for section " +
225 formatv(Fmt: "\"{0}/{1}\" [ {2:x16} -- {3:x16} ] ", Vals&: Cur.SegName,
226 Vals&: Cur.SectName, Vals&: Cur.Address, Vals: Cur.Address + Cur.Size) +
227 "overlaps section \"" + Next.SegName + "/" + Next.SectName + "\"" +
228 formatv(Fmt: "\"{0}/{1}\" [ {2:x16} -- {3:x16} ] ", Vals&: Next.SegName,
229 Vals&: Next.SectName, Vals&: Next.Address, Vals: Next.Address + Next.Size));
230 }
231
232 return Error::success();
233}
234
235Error MachOLinkGraphBuilder::createNormalizedSymbols() {
236 LLVM_DEBUG(dbgs() << "Creating normalized symbols...\n");
237
238 for (auto &SymRef : Obj.symbols()) {
239
240 unsigned SymbolIndex = Obj.getSymbolIndex(Symb: SymRef.getRawDataRefImpl());
241 uint64_t Value;
242 uint32_t NStrX;
243 uint8_t Type;
244 uint8_t Sect;
245 uint16_t Desc;
246
247 if (Obj.is64Bit()) {
248 const MachO::nlist_64 &NL64 =
249 Obj.getSymbol64TableEntry(DRI: SymRef.getRawDataRefImpl());
250 Value = NL64.n_value;
251 NStrX = NL64.n_strx;
252 Type = NL64.n_type;
253 Sect = NL64.n_sect;
254 Desc = NL64.n_desc;
255 } else {
256 const MachO::nlist &NL32 =
257 Obj.getSymbolTableEntry(DRI: SymRef.getRawDataRefImpl());
258 Value = NL32.n_value;
259 NStrX = NL32.n_strx;
260 Type = NL32.n_type;
261 Sect = NL32.n_sect;
262 Desc = NL32.n_desc;
263 }
264
265 // Skip stabs.
266 // FIXME: Are there other symbols we should be skipping?
267 if (Type & MachO::N_STAB)
268 continue;
269
270 std::optional<StringRef> Name;
271 if (NStrX) {
272 if (auto NameOrErr = SymRef.getName())
273 Name = *NameOrErr;
274 else
275 return NameOrErr.takeError();
276 } else if (Type & MachO::N_EXT)
277 return make_error<JITLinkError>(Args: "Symbol at index " +
278 formatv(Fmt: "{0}", Vals&: SymbolIndex) +
279 " has no name (string table index 0), "
280 "but N_EXT bit is set");
281
282 LLVM_DEBUG({
283 dbgs() << " ";
284 if (!Name)
285 dbgs() << "<anonymous symbol>";
286 else
287 dbgs() << *Name;
288 dbgs() << ": value = " << formatv("{0:x16}", Value)
289 << ", type = " << formatv("{0:x2}", Type)
290 << ", desc = " << formatv("{0:x4}", Desc) << ", sect = ";
291 if (Sect)
292 dbgs() << static_cast<unsigned>(Sect - 1);
293 else
294 dbgs() << "none";
295 dbgs() << "\n";
296 });
297
298 // If this symbol has a section, verify that the addresses line up.
299 if (Sect != 0) {
300 auto NSec = findSectionByIndex(Index: Sect - 1);
301 if (!NSec)
302 return NSec.takeError();
303
304 if (orc::ExecutorAddr(Value) < NSec->Address ||
305 orc::ExecutorAddr(Value) > NSec->Address + NSec->Size)
306 return make_error<JITLinkError>(Args: "Address " + formatv(Fmt: "{0:x}", Vals&: Value) +
307 " for symbol " + *Name +
308 " does not fall within section");
309
310 if (!NSec->GraphSection) {
311 LLVM_DEBUG({
312 dbgs() << " Skipping: Symbol is in section " << NSec->SegName << "/"
313 << NSec->SectName
314 << " which has no associated graph section.\n";
315 });
316 continue;
317 }
318 }
319
320 IndexToSymbol[SymbolIndex] =
321 &createNormalizedSymbol(Args&: *Name, Args&: Value, Args&: Type, Args&: Sect, Args&: Desc,
322 Args: getLinkage(Desc), Args: getScope(Name: *Name, Type));
323 }
324
325 return Error::success();
326}
327
328void MachOLinkGraphBuilder::addSectionStartSymAndBlock(
329 unsigned SecIndex, Section &GraphSec, orc::ExecutorAddr Address,
330 const char *Data, orc::ExecutorAddrDiff Size, uint32_t Alignment,
331 bool IsLive) {
332 Block &B =
333 Data ? G->createContentBlock(Parent&: GraphSec, Content: ArrayRef<char>(Data, Size),
334 Address, Alignment, AlignmentOffset: 0)
335 : G->createZeroFillBlock(Parent&: GraphSec, Size, Address, Alignment, AlignmentOffset: 0);
336 auto &Sym = G->addAnonymousSymbol(Content&: B, Offset: 0, Size, IsCallable: false, IsLive);
337 auto SecI = IndexToSection.find(Val: SecIndex);
338 assert(SecI != IndexToSection.end() && "SecIndex invalid");
339 auto &NSec = SecI->second;
340 assert(!NSec.CanonicalSymbols.count(Sym.getAddress()) &&
341 "Anonymous block start symbol clashes with existing symbol address");
342 NSec.CanonicalSymbols[Sym.getAddress()] = &Sym;
343}
344
345Error MachOLinkGraphBuilder::graphifyRegularSymbols() {
346
347 LLVM_DEBUG(dbgs() << "Creating graph symbols...\n");
348
349 /// We only have 256 section indexes: Use a vector rather than a map.
350 std::vector<std::vector<NormalizedSymbol *>> SecIndexToSymbols;
351 SecIndexToSymbols.resize(new_size: 256);
352
353 // Create commons, externs, and absolutes, and partition all other symbols by
354 // section.
355 for (auto &KV : IndexToSymbol) {
356 auto &NSym = *KV.second;
357
358 switch (NSym.Type & MachO::N_TYPE) {
359 case MachO::N_UNDF:
360 if (NSym.Value) {
361 if (!NSym.Name)
362 return make_error<JITLinkError>(Args: "Anonymous common symbol at index " +
363 Twine(KV.first));
364 NSym.GraphSymbol = &G->addDefinedSymbol(
365 Content&: G->createZeroFillBlock(Parent&: getCommonSection(),
366 Size: orc::ExecutorAddrDiff(NSym.Value),
367 Address: orc::ExecutorAddr(),
368 Alignment: 1ull << MachO::GET_COMM_ALIGN(n_desc: NSym.Desc), AlignmentOffset: 0),
369 Offset: 0, Name: *NSym.Name, Size: orc::ExecutorAddrDiff(NSym.Value), L: Linkage::Strong,
370 S: NSym.S, IsCallable: false, IsLive: NSym.Desc & MachO::N_NO_DEAD_STRIP);
371 } else {
372 if (!NSym.Name)
373 return make_error<JITLinkError>(Args: "Anonymous external symbol at "
374 "index " +
375 Twine(KV.first));
376 NSym.GraphSymbol = &G->addExternalSymbol(
377 Name: *NSym.Name, Size: 0, IsWeaklyReferenced: (NSym.Desc & MachO::N_WEAK_REF) != 0);
378 }
379 break;
380 case MachO::N_ABS:
381 if (!NSym.Name)
382 return make_error<JITLinkError>(Args: "Anonymous absolute symbol at index " +
383 Twine(KV.first));
384 NSym.GraphSymbol = &G->addAbsoluteSymbol(
385 Name: *NSym.Name, Address: orc::ExecutorAddr(NSym.Value), Size: 0, L: Linkage::Strong,
386 S: getScope(Name: *NSym.Name, Type: NSym.Type), IsLive: NSym.Desc & MachO::N_NO_DEAD_STRIP);
387 break;
388 case MachO::N_SECT:
389 SecIndexToSymbols[NSym.Sect - 1].push_back(x: &NSym);
390 break;
391 case MachO::N_PBUD:
392 return make_error<JITLinkError>(
393 Args: "Unupported N_PBUD symbol " +
394 (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) +
395 " at index " + Twine(KV.first));
396 case MachO::N_INDR:
397 return make_error<JITLinkError>(
398 Args: "Unupported N_INDR symbol " +
399 (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) +
400 " at index " + Twine(KV.first));
401 default:
402 return make_error<JITLinkError>(
403 Args: "Unrecognized symbol type " + Twine(NSym.Type & MachO::N_TYPE) +
404 " for symbol " +
405 (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) +
406 " at index " + Twine(KV.first));
407 }
408 }
409
410 // Loop over sections performing regular graphification for those that
411 // don't have custom parsers.
412 for (auto &KV : IndexToSection) {
413 auto SecIndex = KV.first;
414 auto &NSec = KV.second;
415
416 if (!NSec.GraphSection) {
417 LLVM_DEBUG({
418 dbgs() << " " << NSec.SegName << "/" << NSec.SectName
419 << " has no graph section. Skipping.\n";
420 });
421 continue;
422 }
423
424 // Skip sections with custom parsers.
425 if (CustomSectionParserFunctions.count(Key: NSec.GraphSection->getName())) {
426 LLVM_DEBUG({
427 dbgs() << " Skipping section " << NSec.GraphSection->getName()
428 << " as it has a custom parser.\n";
429 });
430 continue;
431 } else if ((NSec.Flags & MachO::SECTION_TYPE) ==
432 MachO::S_CSTRING_LITERALS) {
433 if (auto Err = graphifyCStringSection(
434 NSec, NSyms: std::move(SecIndexToSymbols[SecIndex])))
435 return Err;
436 continue;
437 } else
438 LLVM_DEBUG({
439 dbgs() << " Graphifying regular section "
440 << NSec.GraphSection->getName() << "...\n";
441 });
442
443 bool SectionIsNoDeadStrip = NSec.Flags & MachO::S_ATTR_NO_DEAD_STRIP;
444 bool SectionIsText = NSec.Flags & MachO::S_ATTR_PURE_INSTRUCTIONS;
445
446 auto &SecNSymStack = SecIndexToSymbols[SecIndex];
447
448 // If this section is non-empty but there are no symbols covering it then
449 // create one block and anonymous symbol to cover the entire section.
450 if (SecNSymStack.empty()) {
451 if (NSec.Size > 0) {
452 LLVM_DEBUG({
453 dbgs() << " Section non-empty, but contains no symbols. "
454 "Creating anonymous block to cover "
455 << formatv("{0:x16}", NSec.Address) << " -- "
456 << formatv("{0:x16}", NSec.Address + NSec.Size) << "\n";
457 });
458 addSectionStartSymAndBlock(SecIndex, GraphSec&: *NSec.GraphSection, Address: NSec.Address,
459 Data: NSec.Data, Size: NSec.Size, Alignment: NSec.Alignment,
460 IsLive: SectionIsNoDeadStrip);
461 } else
462 LLVM_DEBUG({
463 dbgs() << " Section empty and contains no symbols. Skipping.\n";
464 });
465 continue;
466 }
467
468 // Sort the symbol stack in by address, alt-entry status, scope, and name.
469 // We sort in reverse order so that symbols will be visited in the right
470 // order when we pop off the stack below.
471 llvm::sort(C&: SecNSymStack, Comp: [](const NormalizedSymbol *LHS,
472 const NormalizedSymbol *RHS) {
473 if (LHS->Value != RHS->Value)
474 return LHS->Value > RHS->Value;
475 if (isAltEntry(NSym: *LHS) != isAltEntry(NSym: *RHS))
476 return isAltEntry(NSym: *RHS);
477 if (LHS->S != RHS->S)
478 return static_cast<uint8_t>(LHS->S) < static_cast<uint8_t>(RHS->S);
479 return LHS->Name < RHS->Name;
480 });
481
482 // The first symbol in a section can not be an alt-entry symbol.
483 if (!SecNSymStack.empty() && isAltEntry(NSym: *SecNSymStack.back()))
484 return make_error<JITLinkError>(
485 Args: "First symbol in " + NSec.GraphSection->getName() + " is alt-entry");
486
487 // If the section is non-empty but there is no symbol covering the start
488 // address then add an anonymous one.
489 if (orc::ExecutorAddr(SecNSymStack.back()->Value) != NSec.Address) {
490 auto AnonBlockSize =
491 orc::ExecutorAddr(SecNSymStack.back()->Value) - NSec.Address;
492 LLVM_DEBUG({
493 dbgs() << " Section start not covered by symbol. "
494 << "Creating anonymous block to cover [ " << NSec.Address
495 << " -- " << (NSec.Address + AnonBlockSize) << " ]\n";
496 });
497 addSectionStartSymAndBlock(SecIndex, GraphSec&: *NSec.GraphSection, Address: NSec.Address,
498 Data: NSec.Data, Size: AnonBlockSize, Alignment: NSec.Alignment,
499 IsLive: SectionIsNoDeadStrip);
500 }
501
502 // Visit section symbols in order by popping off the reverse-sorted stack,
503 // building graph symbols as we go.
504 //
505 // If MH_SUBSECTIONS_VIA_SYMBOLS is set we'll build a block for each
506 // alt-entry chain.
507 //
508 // If MH_SUBSECTIONS_VIA_SYMBOLS is not set then we'll just build one block
509 // for the whole section.
510 while (!SecNSymStack.empty()) {
511 SmallVector<NormalizedSymbol *, 8> BlockSyms;
512
513 // Get the symbols in this alt-entry chain, or the whole section (if
514 // !SubsectionsViaSymbols).
515 BlockSyms.push_back(Elt: SecNSymStack.back());
516 SecNSymStack.pop_back();
517 while (!SecNSymStack.empty() &&
518 (isAltEntry(NSym: *SecNSymStack.back()) ||
519 SecNSymStack.back()->Value == BlockSyms.back()->Value ||
520 !SubsectionsViaSymbols)) {
521 BlockSyms.push_back(Elt: SecNSymStack.back());
522 SecNSymStack.pop_back();
523 }
524
525 // BlockNSyms now contains the block symbols in reverse canonical order.
526 auto BlockStart = orc::ExecutorAddr(BlockSyms.front()->Value);
527 orc::ExecutorAddr BlockEnd =
528 SecNSymStack.empty() ? NSec.Address + NSec.Size
529 : orc::ExecutorAddr(SecNSymStack.back()->Value);
530 orc::ExecutorAddrDiff BlockOffset = BlockStart - NSec.Address;
531 orc::ExecutorAddrDiff BlockSize = BlockEnd - BlockStart;
532
533 LLVM_DEBUG({
534 dbgs() << " Creating block for " << formatv("{0:x16}", BlockStart)
535 << " -- " << formatv("{0:x16}", BlockEnd) << ": "
536 << NSec.GraphSection->getName() << " + "
537 << formatv("{0:x16}", BlockOffset) << " with "
538 << BlockSyms.size() << " symbol(s)...\n";
539 });
540
541 Block &B =
542 NSec.Data
543 ? G->createContentBlock(
544 Parent&: *NSec.GraphSection,
545 Content: ArrayRef<char>(NSec.Data + BlockOffset, BlockSize),
546 Address: BlockStart, Alignment: NSec.Alignment, AlignmentOffset: BlockStart % NSec.Alignment)
547 : G->createZeroFillBlock(Parent&: *NSec.GraphSection, Size: BlockSize,
548 Address: BlockStart, Alignment: NSec.Alignment,
549 AlignmentOffset: BlockStart % NSec.Alignment);
550
551 std::optional<orc::ExecutorAddr> LastCanonicalAddr;
552 auto SymEnd = BlockEnd;
553 while (!BlockSyms.empty()) {
554 auto &NSym = *BlockSyms.back();
555 BlockSyms.pop_back();
556
557 bool SymLive =
558 (NSym.Desc & MachO::N_NO_DEAD_STRIP) || SectionIsNoDeadStrip;
559
560 auto &Sym = createStandardGraphSymbol(
561 Sym&: NSym, B, Size: SymEnd - orc::ExecutorAddr(NSym.Value), IsText: SectionIsText,
562 IsNoDeadStrip: SymLive, IsCanonical: LastCanonicalAddr != orc::ExecutorAddr(NSym.Value));
563
564 if (LastCanonicalAddr != Sym.getAddress()) {
565 if (LastCanonicalAddr)
566 SymEnd = *LastCanonicalAddr;
567 LastCanonicalAddr = Sym.getAddress();
568 }
569 }
570 }
571 }
572
573 return Error::success();
574}
575
576Symbol &MachOLinkGraphBuilder::createStandardGraphSymbol(NormalizedSymbol &NSym,
577 Block &B, size_t Size,
578 bool IsText,
579 bool IsNoDeadStrip,
580 bool IsCanonical) {
581
582 LLVM_DEBUG({
583 dbgs() << " " << formatv("{0:x16}", NSym.Value) << " -- "
584 << formatv("{0:x16}", NSym.Value + Size) << ": ";
585 if (!NSym.Name)
586 dbgs() << "<anonymous symbol>";
587 else
588 dbgs() << NSym.Name;
589 if (IsText)
590 dbgs() << " [text]";
591 if (IsNoDeadStrip)
592 dbgs() << " [no-dead-strip]";
593 if (!IsCanonical)
594 dbgs() << " [non-canonical]";
595 dbgs() << "\n";
596 });
597
598 auto SymOffset = orc::ExecutorAddr(NSym.Value) - B.getAddress();
599 auto &Sym =
600 NSym.Name
601 ? G->addDefinedSymbol(Content&: B, Offset: SymOffset, Name: *NSym.Name, Size, L: NSym.L, S: NSym.S,
602 IsCallable: IsText, IsLive: IsNoDeadStrip)
603 : G->addAnonymousSymbol(Content&: B, Offset: SymOffset, Size, IsCallable: IsText, IsLive: IsNoDeadStrip);
604 NSym.GraphSymbol = &Sym;
605
606 if (IsCanonical)
607 setCanonicalSymbol(NSec&: getSectionByIndex(Index: NSym.Sect - 1), Sym);
608
609 return Sym;
610}
611
612Error MachOLinkGraphBuilder::graphifySectionsWithCustomParsers() {
613 // Graphify special sections.
614 for (auto &KV : IndexToSection) {
615 auto &NSec = KV.second;
616
617 // Skip non-graph sections.
618 if (!NSec.GraphSection)
619 continue;
620
621 auto HI = CustomSectionParserFunctions.find(Key: NSec.GraphSection->getName());
622 if (HI != CustomSectionParserFunctions.end()) {
623 auto &Parse = HI->second;
624 if (auto Err = Parse(NSec))
625 return Err;
626 }
627 }
628
629 return Error::success();
630}
631
632Error MachOLinkGraphBuilder::graphifyCStringSection(
633 NormalizedSection &NSec, std::vector<NormalizedSymbol *> NSyms) {
634 assert(NSec.GraphSection && "C string literal section missing graph section");
635 assert(NSec.Data && "C string literal section has no data");
636
637 LLVM_DEBUG({
638 dbgs() << " Graphifying C-string literal section "
639 << NSec.GraphSection->getName() << "\n";
640 });
641
642 if (NSec.Data[NSec.Size - 1] != '\0')
643 return make_error<JITLinkError>(Args: "C string literal section " +
644 NSec.GraphSection->getName() +
645 " does not end with null terminator");
646
647 /// Sort into reverse order to use as a stack.
648 llvm::sort(C&: NSyms,
649 Comp: [](const NormalizedSymbol *LHS, const NormalizedSymbol *RHS) {
650 if (LHS->Value != RHS->Value)
651 return LHS->Value > RHS->Value;
652 if (LHS->L != RHS->L)
653 return LHS->L > RHS->L;
654 if (LHS->S != RHS->S)
655 return LHS->S > RHS->S;
656 if (RHS->Name) {
657 if (!LHS->Name)
658 return true;
659 return *LHS->Name > *RHS->Name;
660 }
661 return false;
662 });
663
664 bool SectionIsNoDeadStrip = NSec.Flags & MachO::S_ATTR_NO_DEAD_STRIP;
665 bool SectionIsText = NSec.Flags & MachO::S_ATTR_PURE_INSTRUCTIONS;
666 orc::ExecutorAddrDiff BlockStart = 0;
667
668 // Scan section for null characters.
669 for (size_t I = 0; I != NSec.Size; ++I) {
670 if (NSec.Data[I] == '\0') {
671 size_t BlockSize = I + 1 - BlockStart;
672 // Create a block for this null terminated string.
673 auto &B = G->createContentBlock(Parent&: *NSec.GraphSection,
674 Content: {NSec.Data + BlockStart, BlockSize},
675 Address: NSec.Address + BlockStart, Alignment: NSec.Alignment,
676 AlignmentOffset: BlockStart % NSec.Alignment);
677
678 LLVM_DEBUG({
679 dbgs() << " Created block " << B.getRange()
680 << ", align = " << B.getAlignment()
681 << ", align-ofs = " << B.getAlignmentOffset() << " for \"";
682 for (size_t J = 0; J != std::min(B.getSize(), size_t(16)); ++J)
683 switch (B.getContent()[J]) {
684 case '\0': break;
685 case '\n': dbgs() << "\\n"; break;
686 case '\t': dbgs() << "\\t"; break;
687 default: dbgs() << B.getContent()[J]; break;
688 }
689 if (B.getSize() > 16)
690 dbgs() << "...";
691 dbgs() << "\"\n";
692 });
693
694 // If there's no symbol at the start of this block then create one.
695 if (NSyms.empty() ||
696 orc::ExecutorAddr(NSyms.back()->Value) != B.getAddress()) {
697 auto &S = G->addAnonymousSymbol(Content&: B, Offset: 0, Size: BlockSize, IsCallable: false, IsLive: false);
698 setCanonicalSymbol(NSec, Sym&: S);
699 LLVM_DEBUG({
700 dbgs() << " Adding symbol for c-string block " << B.getRange()
701 << ": <anonymous symbol> at offset 0\n";
702 });
703 }
704
705 // Process any remaining symbols that point into this block.
706 auto LastCanonicalAddr = B.getAddress() + BlockSize;
707 while (!NSyms.empty() && orc::ExecutorAddr(NSyms.back()->Value) <
708 B.getAddress() + BlockSize) {
709 auto &NSym = *NSyms.back();
710 size_t SymSize = (B.getAddress() + BlockSize) -
711 orc::ExecutorAddr(NSyms.back()->Value);
712 bool SymLive =
713 (NSym.Desc & MachO::N_NO_DEAD_STRIP) || SectionIsNoDeadStrip;
714
715 bool IsCanonical = false;
716 if (LastCanonicalAddr != orc::ExecutorAddr(NSym.Value)) {
717 IsCanonical = true;
718 LastCanonicalAddr = orc::ExecutorAddr(NSym.Value);
719 }
720
721 auto &Sym = createStandardGraphSymbol(NSym, B, Size: SymSize, IsText: SectionIsText,
722 IsNoDeadStrip: SymLive, IsCanonical);
723 (void)Sym;
724 LLVM_DEBUG({
725 dbgs() << " Adding symbol for c-string block " << B.getRange()
726 << ": "
727 << (Sym.hasName() ? Sym.getName() : "<anonymous symbol>")
728 << " at offset " << formatv("{0:x}", Sym.getOffset()) << "\n";
729 });
730
731 NSyms.pop_back();
732 }
733
734 BlockStart += BlockSize;
735 }
736 }
737
738 assert(llvm::all_of(NSec.GraphSection->blocks(),
739 [](Block *B) { return isCStringBlock(*B); }) &&
740 "All blocks in section should hold single c-strings");
741
742 return Error::success();
743}
744
745Error CompactUnwindSplitter::operator()(LinkGraph &G) {
746 auto *CUSec = G.findSectionByName(Name: CompactUnwindSectionName);
747 if (!CUSec)
748 return Error::success();
749
750 if (!G.getTargetTriple().isOSBinFormatMachO())
751 return make_error<JITLinkError>(
752 Args: "Error linking " + G.getName() +
753 ": compact unwind splitting not supported on non-macho target " +
754 G.getTargetTriple().str());
755
756 unsigned CURecordSize = 0;
757 unsigned PersonalityEdgeOffset = 0;
758 unsigned LSDAEdgeOffset = 0;
759 switch (G.getTargetTriple().getArch()) {
760 case Triple::aarch64:
761 case Triple::x86_64:
762 // 64-bit compact-unwind record format:
763 // Range start: 8 bytes.
764 // Range size: 4 bytes.
765 // CU encoding: 4 bytes.
766 // Personality: 8 bytes.
767 // LSDA: 8 bytes.
768 CURecordSize = 32;
769 PersonalityEdgeOffset = 16;
770 LSDAEdgeOffset = 24;
771 break;
772 default:
773 return make_error<JITLinkError>(
774 Args: "Error linking " + G.getName() +
775 ": compact unwind splitting not supported on " +
776 G.getTargetTriple().getArchName());
777 }
778
779 std::vector<Block *> OriginalBlocks(CUSec->blocks().begin(),
780 CUSec->blocks().end());
781 LLVM_DEBUG({
782 dbgs() << "In " << G.getName() << " splitting compact unwind section "
783 << CompactUnwindSectionName << " containing "
784 << OriginalBlocks.size() << " initial blocks...\n";
785 });
786
787 while (!OriginalBlocks.empty()) {
788 auto *B = OriginalBlocks.back();
789 OriginalBlocks.pop_back();
790
791 if (B->getSize() == 0) {
792 LLVM_DEBUG({
793 dbgs() << " Skipping empty block at "
794 << formatv("{0:x16}", B->getAddress()) << "\n";
795 });
796 continue;
797 }
798
799 LLVM_DEBUG({
800 dbgs() << " Splitting block at " << formatv("{0:x16}", B->getAddress())
801 << " into " << (B->getSize() / CURecordSize)
802 << " compact unwind record(s)\n";
803 });
804
805 if (B->getSize() % CURecordSize)
806 return make_error<JITLinkError>(
807 Args: "Error splitting compact unwind record in " + G.getName() +
808 ": block at " + formatv(Fmt: "{0:x}", Vals: B->getAddress()) + " has size " +
809 formatv(Fmt: "{0:x}", Vals: B->getSize()) +
810 " (not a multiple of CU record size of " +
811 formatv(Fmt: "{0:x}", Vals&: CURecordSize) + ")");
812
813 unsigned NumBlocks = B->getSize() / CURecordSize;
814 LinkGraph::SplitBlockCache C;
815
816 for (unsigned I = 0; I != NumBlocks; ++I) {
817 auto &CURec = G.splitBlock(B&: *B, SplitIndex: CURecordSize, Cache: &C);
818 bool AddedKeepAlive = false;
819
820 for (auto &E : CURec.edges()) {
821 if (E.getOffset() == 0) {
822 LLVM_DEBUG({
823 dbgs() << " Updating compact unwind record at "
824 << formatv("{0:x16}", CURec.getAddress()) << " to point to "
825 << (E.getTarget().hasName() ? E.getTarget().getName()
826 : StringRef())
827 << " (at " << formatv("{0:x16}", E.getTarget().getAddress())
828 << ")\n";
829 });
830
831 if (E.getTarget().isExternal())
832 return make_error<JITLinkError>(
833 Args: "Error adding keep-alive edge for compact unwind record at " +
834 formatv(Fmt: "{0:x}", Vals: CURec.getAddress()) + ": target " +
835 E.getTarget().getName() + " is an external symbol");
836 auto &TgtBlock = E.getTarget().getBlock();
837 auto &CURecSym =
838 G.addAnonymousSymbol(Content&: CURec, Offset: 0, Size: CURecordSize, IsCallable: false, IsLive: false);
839 TgtBlock.addEdge(K: Edge::KeepAlive, Offset: 0, Target&: CURecSym, Addend: 0);
840 AddedKeepAlive = true;
841 } else if (E.getOffset() != PersonalityEdgeOffset &&
842 E.getOffset() != LSDAEdgeOffset)
843 return make_error<JITLinkError>(Args: "Unexpected edge at offset " +
844 formatv(Fmt: "{0:x}", Vals: E.getOffset()) +
845 " in compact unwind record at " +
846 formatv(Fmt: "{0:x}", Vals: CURec.getAddress()));
847 }
848
849 if (!AddedKeepAlive)
850 return make_error<JITLinkError>(
851 Args: "Error adding keep-alive edge for compact unwind record at " +
852 formatv(Fmt: "{0:x}", Vals: CURec.getAddress()) +
853 ": no outgoing target edge at offset 0");
854 }
855 }
856 return Error::success();
857}
858
859} // end namespace jitlink
860} // end namespace llvm
861