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