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