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