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