xref: /llvm-project/llvm/lib/ExecutionEngine/JITLink/MachOLinkGraphBuilder.cpp (revision 2a35d59b2f70c377c1aff206ad5a7105e1d387e8)
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     auto Prot = static_cast<sys::Memory::ProtectionFlags>(
112         sys::Memory::MF_READ | sys::Memory::MF_WRITE);
113     CommonSection = &G->createSection(CommonSectionName, Prot);
114   }
115   return *CommonSection;
116 }
117 
118 Error MachOLinkGraphBuilder::createNormalizedSections() {
119   // Build normalized sections. Verifies that section data is in-range (for
120   // sections with content) and that address ranges are non-overlapping.
121 
122   LLVM_DEBUG(dbgs() << "Creating normalized sections...\n");
123 
124   for (auto &SecRef : Obj.sections()) {
125     NormalizedSection NSec;
126     uint32_t DataOffset = 0;
127 
128     auto SecIndex = Obj.getSectionIndex(SecRef.getRawDataRefImpl());
129 
130     if (Obj.is64Bit()) {
131       const MachO::section_64 &Sec64 =
132           Obj.getSection64(SecRef.getRawDataRefImpl());
133 
134       memcpy(&NSec.SectName, &Sec64.sectname, 16);
135       NSec.SectName[16] = '\0';
136       memcpy(&NSec.SegName, Sec64.segname, 16);
137       NSec.SegName[16] = '\0';
138 
139       NSec.Address = Sec64.addr;
140       NSec.Size = Sec64.size;
141       NSec.Alignment = 1ULL << Sec64.align;
142       NSec.Flags = Sec64.flags;
143       DataOffset = Sec64.offset;
144     } else {
145       const MachO::section &Sec32 = Obj.getSection(SecRef.getRawDataRefImpl());
146 
147       memcpy(&NSec.SectName, &Sec32.sectname, 16);
148       NSec.SectName[16] = '\0';
149       memcpy(&NSec.SegName, Sec32.segname, 16);
150       NSec.SegName[16] = '\0';
151 
152       NSec.Address = Sec32.addr;
153       NSec.Size = Sec32.size;
154       NSec.Alignment = 1ULL << Sec32.align;
155       NSec.Flags = Sec32.flags;
156       DataOffset = Sec32.offset;
157     }
158 
159     LLVM_DEBUG({
160       dbgs() << "  " << NSec.SegName << "," << NSec.SectName << ": "
161              << formatv("{0:x16}", NSec.Address) << " -- "
162              << formatv("{0:x16}", NSec.Address + NSec.Size)
163              << ", align: " << NSec.Alignment << ", index: " << SecIndex
164              << "\n";
165     });
166 
167     // Get the section data if any.
168     if (!isZeroFillSection(NSec)) {
169       if (DataOffset + NSec.Size > Obj.getData().size())
170         return make_error<JITLinkError>(
171             "Section data extends past end of file");
172 
173       NSec.Data = Obj.getData().data() + DataOffset;
174     }
175 
176     // Get prot flags.
177     // FIXME: Make sure this test is correct (it's probably missing cases
178     // as-is).
179     sys::Memory::ProtectionFlags Prot;
180     if (NSec.Flags & MachO::S_ATTR_PURE_INSTRUCTIONS)
181       Prot = static_cast<sys::Memory::ProtectionFlags>(sys::Memory::MF_READ |
182                                                        sys::Memory::MF_EXEC);
183     else
184       Prot = static_cast<sys::Memory::ProtectionFlags>(sys::Memory::MF_READ |
185                                                        sys::Memory::MF_WRITE);
186 
187     if (!isDebugSection(NSec)) {
188       auto FullyQualifiedName =
189           G->allocateString(StringRef(NSec.SegName) + "," + NSec.SectName);
190       NSec.GraphSection = &G->createSection(
191           StringRef(FullyQualifiedName.data(), FullyQualifiedName.size()),
192           Prot);
193     } else
194       LLVM_DEBUG({
195         dbgs() << "    " << NSec.SegName << "," << NSec.SectName
196                << " is a debug section: No graph section will be created.\n";
197       });
198 
199     IndexToSection.insert(std::make_pair(SecIndex, std::move(NSec)));
200   }
201 
202   std::vector<NormalizedSection *> Sections;
203   Sections.reserve(IndexToSection.size());
204   for (auto &KV : IndexToSection)
205     Sections.push_back(&KV.second);
206 
207   // If we didn't end up creating any sections then bail out. The code below
208   // assumes that we have at least one section.
209   if (Sections.empty())
210     return Error::success();
211 
212   llvm::sort(Sections,
213              [](const NormalizedSection *LHS, const NormalizedSection *RHS) {
214                assert(LHS && RHS && "Null section?");
215                if (LHS->Address != RHS->Address)
216                  return LHS->Address < RHS->Address;
217                return LHS->Size < RHS->Size;
218              });
219 
220   for (unsigned I = 0, E = Sections.size() - 1; I != E; ++I) {
221     auto &Cur = *Sections[I];
222     auto &Next = *Sections[I + 1];
223     if (Next.Address < Cur.Address + Cur.Size)
224       return make_error<JITLinkError>(
225           "Address range for section " +
226           formatv("\"{0}/{1}\" [ {2:x16} -- {3:x16} ] ", Cur.SegName,
227                   Cur.SectName, Cur.Address, Cur.Address + Cur.Size) +
228           "overlaps section \"" + Next.SegName + "/" + Next.SectName + "\"" +
229           formatv("\"{0}/{1}\" [ {2:x16} -- {3:x16} ] ", Next.SegName,
230                   Next.SectName, Next.Address, Next.Address + Next.Size));
231   }
232 
233   return Error::success();
234 }
235 
236 Error MachOLinkGraphBuilder::createNormalizedSymbols() {
237   LLVM_DEBUG(dbgs() << "Creating normalized symbols...\n");
238 
239   for (auto &SymRef : Obj.symbols()) {
240 
241     unsigned SymbolIndex = Obj.getSymbolIndex(SymRef.getRawDataRefImpl());
242     uint64_t Value;
243     uint32_t NStrX;
244     uint8_t Type;
245     uint8_t Sect;
246     uint16_t Desc;
247 
248     if (Obj.is64Bit()) {
249       const MachO::nlist_64 &NL64 =
250           Obj.getSymbol64TableEntry(SymRef.getRawDataRefImpl());
251       Value = NL64.n_value;
252       NStrX = NL64.n_strx;
253       Type = NL64.n_type;
254       Sect = NL64.n_sect;
255       Desc = NL64.n_desc;
256     } else {
257       const MachO::nlist &NL32 =
258           Obj.getSymbolTableEntry(SymRef.getRawDataRefImpl());
259       Value = NL32.n_value;
260       NStrX = NL32.n_strx;
261       Type = NL32.n_type;
262       Sect = NL32.n_sect;
263       Desc = NL32.n_desc;
264     }
265 
266     // Skip stabs.
267     // FIXME: Are there other symbols we should be skipping?
268     if (Type & MachO::N_STAB)
269       continue;
270 
271     Optional<StringRef> Name;
272     if (NStrX) {
273       if (auto NameOrErr = SymRef.getName())
274         Name = *NameOrErr;
275       else
276         return NameOrErr.takeError();
277     }
278 
279     LLVM_DEBUG({
280       dbgs() << "  ";
281       if (!Name)
282         dbgs() << "<anonymous symbol>";
283       else
284         dbgs() << *Name;
285       dbgs() << ": value = " << formatv("{0:x16}", Value)
286              << ", type = " << formatv("{0:x2}", Type)
287              << ", desc = " << formatv("{0:x4}", Desc) << ", sect = ";
288       if (Sect)
289         dbgs() << static_cast<unsigned>(Sect - 1);
290       else
291         dbgs() << "none";
292       dbgs() << "\n";
293     });
294 
295     // If this symbol has a section, sanity check that the addresses line up.
296     if (Sect != 0) {
297       auto NSec = findSectionByIndex(Sect - 1);
298       if (!NSec)
299         return NSec.takeError();
300 
301       if (Value < NSec->Address || Value > NSec->Address + NSec->Size)
302         return make_error<JITLinkError>("Address " + formatv("{0:x}", Value) +
303                                         " for symbol " + *Name +
304                                         " does not fall within section");
305 
306       if (!NSec->GraphSection) {
307         LLVM_DEBUG({
308           dbgs() << "  Skipping: Symbol is in section " << NSec->SegName << "/"
309                  << NSec->SectName
310                  << " which has no associated graph section.\n";
311         });
312         continue;
313       }
314     }
315 
316     IndexToSymbol[SymbolIndex] =
317         &createNormalizedSymbol(*Name, Value, Type, Sect, Desc,
318                                 getLinkage(Desc), getScope(*Name, Type));
319   }
320 
321   return Error::success();
322 }
323 
324 void MachOLinkGraphBuilder::addSectionStartSymAndBlock(
325     Section &GraphSec, uint64_t Address, const char *Data, uint64_t Size,
326     uint32_t Alignment, bool IsLive) {
327   Block &B =
328       Data ? G->createContentBlock(GraphSec, ArrayRef<char>(Data, Size),
329                                    Address, Alignment, 0)
330            : G->createZeroFillBlock(GraphSec, Size, Address, Alignment, 0);
331   auto &Sym = G->addAnonymousSymbol(B, 0, Size, false, IsLive);
332   assert(!AddrToCanonicalSymbol.count(Sym.getAddress()) &&
333          "Anonymous block start symbol clashes with existing symbol address");
334   AddrToCanonicalSymbol[Sym.getAddress()] = &Sym;
335 }
336 
337 Error MachOLinkGraphBuilder::graphifyRegularSymbols() {
338 
339   LLVM_DEBUG(dbgs() << "Creating graph symbols...\n");
340 
341   /// We only have 256 section indexes: Use a vector rather than a map.
342   std::vector<std::vector<NormalizedSymbol *>> SecIndexToSymbols;
343   SecIndexToSymbols.resize(256);
344 
345   // Create commons, externs, and absolutes, and partition all other symbols by
346   // section.
347   for (auto &KV : IndexToSymbol) {
348     auto &NSym = *KV.second;
349 
350     switch (NSym.Type & MachO::N_TYPE) {
351     case MachO::N_UNDF:
352       if (NSym.Value) {
353         if (!NSym.Name)
354           return make_error<JITLinkError>("Anonymous common symbol at index " +
355                                           Twine(KV.first));
356         NSym.GraphSymbol = &G->addCommonSymbol(
357             *NSym.Name, NSym.S, getCommonSection(), 0, NSym.Value,
358             1ull << MachO::GET_COMM_ALIGN(NSym.Desc),
359             NSym.Desc & MachO::N_NO_DEAD_STRIP);
360       } else {
361         if (!NSym.Name)
362           return make_error<JITLinkError>("Anonymous external symbol at "
363                                           "index " +
364                                           Twine(KV.first));
365         NSym.GraphSymbol = &G->addExternalSymbol(
366             *NSym.Name, 0,
367             NSym.Desc & MachO::N_WEAK_REF ? Linkage::Weak : Linkage::Strong);
368       }
369       break;
370     case MachO::N_ABS:
371       if (!NSym.Name)
372         return make_error<JITLinkError>("Anonymous absolute symbol at index " +
373                                         Twine(KV.first));
374       NSym.GraphSymbol = &G->addAbsoluteSymbol(
375           *NSym.Name, NSym.Value, 0, Linkage::Strong, Scope::Default,
376           NSym.Desc & MachO::N_NO_DEAD_STRIP);
377       break;
378     case MachO::N_SECT:
379       SecIndexToSymbols[NSym.Sect - 1].push_back(&NSym);
380       break;
381     case MachO::N_PBUD:
382       return make_error<JITLinkError>(
383           "Unupported N_PBUD symbol " +
384           (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) +
385           " at index " + Twine(KV.first));
386     case MachO::N_INDR:
387       return make_error<JITLinkError>(
388           "Unupported N_INDR symbol " +
389           (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) +
390           " at index " + Twine(KV.first));
391     default:
392       return make_error<JITLinkError>(
393           "Unrecognized symbol type " + Twine(NSym.Type & MachO::N_TYPE) +
394           " for symbol " +
395           (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) +
396           " at index " + Twine(KV.first));
397     }
398   }
399 
400   // Loop over sections performing regular graphification for those that
401   // don't have custom parsers.
402   for (auto &KV : IndexToSection) {
403     auto SecIndex = KV.first;
404     auto &NSec = KV.second;
405 
406     if (!NSec.GraphSection) {
407       LLVM_DEBUG({
408         dbgs() << "  " << NSec.SegName << "/" << NSec.SectName
409                << " has no graph section. Skipping.\n";
410       });
411       continue;
412     }
413 
414     // Skip sections with custom parsers.
415     if (CustomSectionParserFunctions.count(NSec.GraphSection->getName())) {
416       LLVM_DEBUG({
417         dbgs() << "  Skipping section " << NSec.GraphSection->getName()
418                << " as it has a custom parser.\n";
419       });
420       continue;
421     } else if ((NSec.Flags & MachO::SECTION_TYPE) ==
422                MachO::S_CSTRING_LITERALS) {
423       if (auto Err = graphifyCStringSection(
424               NSec, std::move(SecIndexToSymbols[SecIndex])))
425         return Err;
426       continue;
427     } else
428       LLVM_DEBUG({
429         dbgs() << "  Graphifying regular section "
430                << NSec.GraphSection->getName() << "...\n";
431       });
432 
433     bool SectionIsNoDeadStrip = NSec.Flags & MachO::S_ATTR_NO_DEAD_STRIP;
434     bool SectionIsText = NSec.Flags & MachO::S_ATTR_PURE_INSTRUCTIONS;
435 
436     auto &SecNSymStack = SecIndexToSymbols[SecIndex];
437 
438     // If this section is non-empty but there are no symbols covering it then
439     // create one block and anonymous symbol to cover the entire section.
440     if (SecNSymStack.empty()) {
441       if (NSec.Size > 0) {
442         LLVM_DEBUG({
443           dbgs() << "    Section non-empty, but contains no symbols. "
444                     "Creating anonymous block to cover "
445                  << formatv("{0:x16}", NSec.Address) << " -- "
446                  << formatv("{0:x16}", NSec.Address + NSec.Size) << "\n";
447         });
448         addSectionStartSymAndBlock(*NSec.GraphSection, NSec.Address, NSec.Data,
449                                    NSec.Size, NSec.Alignment,
450                                    SectionIsNoDeadStrip);
451       } else
452         LLVM_DEBUG({
453           dbgs() << "    Section empty and contains no symbols. Skipping.\n";
454         });
455       continue;
456     }
457 
458     // Sort the symbol stack in by address, alt-entry status, scope, and name.
459     // We sort in reverse order so that symbols will be visited in the right
460     // order when we pop off the stack below.
461     llvm::sort(SecNSymStack, [](const NormalizedSymbol *LHS,
462                                 const NormalizedSymbol *RHS) {
463       if (LHS->Value != RHS->Value)
464         return LHS->Value > RHS->Value;
465       if (isAltEntry(*LHS) != isAltEntry(*RHS))
466         return isAltEntry(*RHS);
467       if (LHS->S != RHS->S)
468         return static_cast<uint8_t>(LHS->S) < static_cast<uint8_t>(RHS->S);
469       return LHS->Name < RHS->Name;
470     });
471 
472     // The first symbol in a section can not be an alt-entry symbol.
473     if (!SecNSymStack.empty() && isAltEntry(*SecNSymStack.back()))
474       return make_error<JITLinkError>(
475           "First symbol in " + NSec.GraphSection->getName() + " is alt-entry");
476 
477     // If the section is non-empty but there is no symbol covering the start
478     // address then add an anonymous one.
479     if (SecNSymStack.back()->Value != NSec.Address) {
480       auto AnonBlockSize = SecNSymStack.back()->Value - NSec.Address;
481       LLVM_DEBUG({
482         dbgs() << "    Section start not covered by symbol. "
483                << "Creating anonymous block to cover [ "
484                << formatv("{0:x16}", NSec.Address) << " -- "
485                << formatv("{0:x16}", NSec.Address + AnonBlockSize) << " ]\n";
486       });
487       addSectionStartSymAndBlock(*NSec.GraphSection, NSec.Address, NSec.Data,
488                                  AnonBlockSize, NSec.Alignment,
489                                  SectionIsNoDeadStrip);
490     }
491 
492     // Visit section symbols in order by popping off the reverse-sorted stack,
493     // building blocks for each alt-entry chain and creating symbols as we go.
494     while (!SecNSymStack.empty()) {
495       SmallVector<NormalizedSymbol *, 8> BlockSyms;
496 
497       BlockSyms.push_back(SecNSymStack.back());
498       SecNSymStack.pop_back();
499       while (!SecNSymStack.empty() &&
500              (isAltEntry(*SecNSymStack.back()) ||
501               SecNSymStack.back()->Value == BlockSyms.back()->Value)) {
502         BlockSyms.push_back(SecNSymStack.back());
503         SecNSymStack.pop_back();
504       }
505 
506       // BlockNSyms now contains the block symbols in reverse canonical order.
507       JITTargetAddress BlockStart = BlockSyms.front()->Value;
508       JITTargetAddress BlockEnd = SecNSymStack.empty()
509                                       ? NSec.Address + NSec.Size
510                                       : SecNSymStack.back()->Value;
511       JITTargetAddress BlockOffset = BlockStart - NSec.Address;
512       JITTargetAddress BlockSize = BlockEnd - BlockStart;
513 
514       LLVM_DEBUG({
515         dbgs() << "    Creating block for " << formatv("{0:x16}", BlockStart)
516                << " -- " << formatv("{0:x16}", BlockEnd) << ": "
517                << NSec.GraphSection->getName() << " + "
518                << formatv("{0:x16}", BlockOffset) << " with "
519                << BlockSyms.size() << " symbol(s)...\n";
520       });
521 
522       Block &B =
523           NSec.Data
524               ? G->createContentBlock(
525                     *NSec.GraphSection,
526                     ArrayRef<char>(NSec.Data + BlockOffset, BlockSize),
527                     BlockStart, NSec.Alignment, BlockStart % NSec.Alignment)
528               : G->createZeroFillBlock(*NSec.GraphSection, BlockSize,
529                                        BlockStart, NSec.Alignment,
530                                        BlockStart % NSec.Alignment);
531 
532       Optional<JITTargetAddress> LastCanonicalAddr;
533       JITTargetAddress SymEnd = BlockEnd;
534       while (!BlockSyms.empty()) {
535         auto &NSym = *BlockSyms.back();
536         BlockSyms.pop_back();
537 
538         bool SymLive =
539             (NSym.Desc & MachO::N_NO_DEAD_STRIP) || SectionIsNoDeadStrip;
540 
541         auto &Sym = createStandardGraphSymbol(NSym, B, SymEnd - NSym.Value,
542                                               SectionIsText, SymLive,
543                                               LastCanonicalAddr != NSym.Value);
544 
545         if (LastCanonicalAddr != Sym.getAddress()) {
546           if (LastCanonicalAddr)
547             SymEnd = *LastCanonicalAddr;
548           LastCanonicalAddr = Sym.getAddress();
549         }
550       }
551     }
552   }
553 
554   return Error::success();
555 }
556 
557 Symbol &MachOLinkGraphBuilder::createStandardGraphSymbol(NormalizedSymbol &NSym,
558                                                          Block &B, size_t Size,
559                                                          bool IsText,
560                                                          bool IsNoDeadStrip,
561                                                          bool IsCanonical) {
562 
563   LLVM_DEBUG({
564     dbgs() << "      " << formatv("{0:x16}", NSym.Value) << " -- "
565            << formatv("{0:x16}", NSym.Value + Size) << ": ";
566     if (!NSym.Name)
567       dbgs() << "<anonymous symbol>";
568     else
569       dbgs() << NSym.Name;
570     if (IsText)
571       dbgs() << " [text]";
572     if (IsNoDeadStrip)
573       dbgs() << " [no-dead-strip]";
574     if (!IsCanonical)
575       dbgs() << " [non-canonical]";
576     dbgs() << "\n";
577   });
578 
579   auto &Sym = NSym.Name ? G->addDefinedSymbol(B, NSym.Value - B.getAddress(),
580                                               *NSym.Name, Size, NSym.L, NSym.S,
581                                               IsText, IsNoDeadStrip)
582                         : G->addAnonymousSymbol(B, NSym.Value - B.getAddress(),
583                                                 Size, IsText, IsNoDeadStrip);
584   NSym.GraphSymbol = &Sym;
585 
586   if (IsCanonical)
587     setCanonicalSymbol(Sym);
588 
589   return Sym;
590 }
591 
592 Error MachOLinkGraphBuilder::graphifySectionsWithCustomParsers() {
593   // Graphify special sections.
594   for (auto &KV : IndexToSection) {
595     auto &NSec = KV.second;
596 
597     // Skip non-graph sections.
598     if (!NSec.GraphSection)
599       continue;
600 
601     auto HI = CustomSectionParserFunctions.find(NSec.GraphSection->getName());
602     if (HI != CustomSectionParserFunctions.end()) {
603       auto &Parse = HI->second;
604       if (auto Err = Parse(NSec))
605         return Err;
606     }
607   }
608 
609   return Error::success();
610 }
611 
612 Error MachOLinkGraphBuilder::graphifyCStringSection(
613     NormalizedSection &NSec, std::vector<NormalizedSymbol *> NSyms) {
614 
615   assert(NSec.GraphSection && "C string literal section missing graph section");
616   assert(NSec.Data && "C string literal section has no data");
617 
618   LLVM_DEBUG({
619     dbgs() << "  Graphifying C-string literal section "
620            << NSec.GraphSection->getName() << "\n";
621   });
622 
623   if (NSec.Data[NSec.Size - 1] != '\0')
624     return make_error<JITLinkError>("C string literal section " +
625                                     NSec.GraphSection->getName() +
626                                     " does not end with null terminator");
627 
628   /// Sort into reverse order to use as a stack.
629   llvm::sort(NSyms,
630              [](const NormalizedSymbol *LHS, const NormalizedSymbol *RHS) {
631                if (LHS->Value != RHS->Value)
632                  return LHS->Value > RHS->Value;
633                if (LHS->L != RHS->L)
634                  return LHS->L > RHS->L;
635                if (LHS->S != RHS->S)
636                  return LHS->S > RHS->S;
637                if (RHS->Name) {
638                  if (!LHS->Name)
639                    return true;
640                  return *LHS->Name > *RHS->Name;
641                }
642                return false;
643              });
644 
645   bool SectionIsNoDeadStrip = NSec.Flags & MachO::S_ATTR_NO_DEAD_STRIP;
646   bool SectionIsText = NSec.Flags & MachO::S_ATTR_PURE_INSTRUCTIONS;
647   JITTargetAddress BlockStart = 0;
648 
649   // Scan section for null characters.
650   for (size_t I = 0; I != NSec.Size; ++I)
651     if (NSec.Data[I] == '\0') {
652       JITTargetAddress BlockEnd = I + 1;
653       size_t BlockSize = BlockEnd - BlockStart;
654       // Create a block for this null terminated string.
655       auto &B = G->createContentBlock(*NSec.GraphSection,
656                                       {NSec.Data + BlockStart, BlockSize},
657                                       NSec.Address + BlockStart, 1, 0);
658 
659       LLVM_DEBUG({
660         dbgs() << "    Created block " << formatv("{0:x}", B.getAddress())
661                << " -- " << formatv("{0:x}", B.getAddress() + B.getSize())
662                << " for \"" << StringRef(B.getContent().data()) << "\"\n";
663       });
664 
665       // If there's no symbol at the start of this block then create one.
666       if (NSyms.empty() || NSyms.back()->Value != B.getAddress()) {
667         auto &S = G->addAnonymousSymbol(B, 0, BlockSize, false, false);
668         setCanonicalSymbol(S);
669         LLVM_DEBUG({
670           dbgs() << "      Adding anonymous symbol for c-string block "
671                  << formatv("{0:x16} -- {1:x16}", S.getAddress(),
672                             S.getAddress() + BlockSize)
673                  << "\n";
674         });
675       }
676 
677       // Process any remaining symbols that point into this block.
678       JITTargetAddress LastCanonicalAddr = B.getAddress() + BlockEnd;
679       while (!NSyms.empty() &&
680              NSyms.back()->Value < (B.getAddress() + BlockSize)) {
681         auto &NSym = *NSyms.back();
682         size_t SymSize = (B.getAddress() + BlockSize) - NSyms.back()->Value;
683         bool SymLive =
684             (NSym.Desc & MachO::N_NO_DEAD_STRIP) || SectionIsNoDeadStrip;
685 
686         bool IsCanonical = false;
687         if (LastCanonicalAddr != NSym.Value) {
688           IsCanonical = true;
689           LastCanonicalAddr = NSym.Value;
690         }
691 
692         createStandardGraphSymbol(NSym, B, SymSize, SectionIsText, SymLive,
693                                   IsCanonical);
694 
695         NSyms.pop_back();
696       }
697 
698       BlockStart += BlockSize;
699     }
700 
701   return Error::success();
702 }
703 
704 } // end namespace jitlink
705 } // end namespace llvm
706