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
17static const char *CommonSectionName = "__common";
18
19namespace llvm {
20namespace jitlink {
21
22MachOLinkGraphBuilder::~MachOLinkGraphBuilder() {}
23
24Expected<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
48MachOLinkGraphBuilder::MachOLinkGraphBuilder(const object::MachOObjectFile &Obj)
49    : Obj(Obj),
50      G(std::make_unique<LinkGraph>(Obj.getFileName(), getPointerSize(Obj),
51                                    getEndianness(Obj))) {}
52
53void MachOLinkGraphBuilder::addCustomSectionParser(
54    StringRef SectionName, SectionParserFunction Parser) {
55  assert(!CustomSectionParserFunctions.count(SectionName) &&
56         "Custom parser for this section already exists");
57  CustomSectionParserFunctions[SectionName] = std::move(Parser);
58}
59
60Linkage MachOLinkGraphBuilder::getLinkage(uint16_t Desc) {
61  if ((Desc & MachO::N_WEAK_DEF) || (Desc & MachO::N_WEAK_REF))
62    return Linkage::Weak;
63  return Linkage::Strong;
64}
65
66Scope MachOLinkGraphBuilder::getScope(StringRef Name, uint8_t Type) {
67  if (Name.startswith("l"))
68    return Scope::Local;
69  if (Type & MachO::N_PEXT)
70    return Scope::Hidden;
71  if (Type & MachO::N_EXT)
72    return Scope::Default;
73  return Scope::Local;
74}
75
76bool MachOLinkGraphBuilder::isAltEntry(const NormalizedSymbol &NSym) {
77  return NSym.Desc & MachO::N_ALT_ENTRY;
78}
79
80unsigned
81MachOLinkGraphBuilder::getPointerSize(const object::MachOObjectFile &Obj) {
82  return Obj.is64Bit() ? 8 : 4;
83}
84
85support::endianness
86MachOLinkGraphBuilder::getEndianness(const object::MachOObjectFile &Obj) {
87  return Obj.isLittleEndian() ? support::little : support::big;
88}
89
90Section &MachOLinkGraphBuilder::getCommonSection() {
91  if (!CommonSection) {
92    auto Prot = static_cast<sys::Memory::ProtectionFlags>(
93        sys::Memory::MF_READ | sys::Memory::MF_WRITE);
94    CommonSection = &G->createSection(CommonSectionName, Prot);
95  }
96  return *CommonSection;
97}
98
99Error MachOLinkGraphBuilder::createNormalizedSections() {
100  // Build normalized sections. Verifies that section data is in-range (for
101  // sections with content) and that address ranges are non-overlapping.
102
103  LLVM_DEBUG(dbgs() << "Creating normalized sections...\n");
104
105  for (auto &SecRef : Obj.sections()) {
106    NormalizedSection NSec;
107    uint32_t DataOffset = 0;
108
109    auto SecIndex = Obj.getSectionIndex(SecRef.getRawDataRefImpl());
110
111    auto Name = SecRef.getName();
112    if (!Name)
113      return Name.takeError();
114
115    if (Obj.is64Bit()) {
116      const MachO::section_64 &Sec64 =
117          Obj.getSection64(SecRef.getRawDataRefImpl());
118
119      NSec.Address = Sec64.addr;
120      NSec.Size = Sec64.size;
121      NSec.Alignment = 1ULL << Sec64.align;
122      NSec.Flags = Sec64.flags;
123      DataOffset = Sec64.offset;
124    } else {
125      const MachO::section &Sec32 = Obj.getSection(SecRef.getRawDataRefImpl());
126      NSec.Address = Sec32.addr;
127      NSec.Size = Sec32.size;
128      NSec.Alignment = 1ULL << Sec32.align;
129      NSec.Flags = Sec32.flags;
130      DataOffset = Sec32.offset;
131    }
132
133    LLVM_DEBUG({
134      dbgs() << "  " << *Name << ": " << formatv("{0:x16}", NSec.Address)
135             << " -- " << formatv("{0:x16}", NSec.Address + NSec.Size)
136             << ", align: " << NSec.Alignment << ", index: " << SecIndex
137             << "\n";
138    });
139
140    // Get the section data if any.
141    {
142      unsigned SectionType = NSec.Flags & MachO::SECTION_TYPE;
143      if (SectionType != MachO::S_ZEROFILL &&
144          SectionType != MachO::S_GB_ZEROFILL) {
145
146        if (DataOffset + NSec.Size > Obj.getData().size())
147          return make_error<JITLinkError>(
148              "Section data extends past end of file");
149
150        NSec.Data = Obj.getData().data() + DataOffset;
151      }
152    }
153
154    // Get prot flags.
155    // FIXME: Make sure this test is correct (it's probably missing cases
156    // as-is).
157    sys::Memory::ProtectionFlags Prot;
158    if (NSec.Flags & MachO::S_ATTR_PURE_INSTRUCTIONS)
159      Prot = static_cast<sys::Memory::ProtectionFlags>(sys::Memory::MF_READ |
160                                                       sys::Memory::MF_EXEC);
161    else
162      Prot = static_cast<sys::Memory::ProtectionFlags>(sys::Memory::MF_READ |
163                                                       sys::Memory::MF_WRITE);
164
165    NSec.GraphSection = &G->createSection(*Name, Prot);
166    IndexToSection.insert(std::make_pair(SecIndex, std::move(NSec)));
167  }
168
169  std::vector<NormalizedSection *> Sections;
170  Sections.reserve(IndexToSection.size());
171  for (auto &KV : IndexToSection)
172    Sections.push_back(&KV.second);
173
174  // If we didn't end up creating any sections then bail out. The code below
175  // assumes that we have at least one section.
176  if (Sections.empty())
177    return Error::success();
178
179  llvm::sort(Sections,
180             [](const NormalizedSection *LHS, const NormalizedSection *RHS) {
181               assert(LHS && RHS && "Null section?");
182               if (LHS->Address != RHS->Address)
183                 return LHS->Address < RHS->Address;
184               return LHS->Size < RHS->Size;
185             });
186
187  for (unsigned I = 0, E = Sections.size() - 1; I != E; ++I) {
188    auto &Cur = *Sections[I];
189    auto &Next = *Sections[I + 1];
190    if (Next.Address < Cur.Address + Cur.Size)
191      return make_error<JITLinkError>(
192          "Address range for section " + Cur.GraphSection->getName() +
193          formatv(" [ {0:x16} -- {1:x16} ] ", Cur.Address,
194                  Cur.Address + Cur.Size) +
195          "overlaps " +
196          formatv(" [ {0:x16} -- {1:x16} ] ", Next.Address,
197                  Next.Address + Next.Size));
198  }
199
200  return Error::success();
201}
202
203Error MachOLinkGraphBuilder::createNormalizedSymbols() {
204  LLVM_DEBUG(dbgs() << "Creating normalized symbols...\n");
205
206  for (auto &SymRef : Obj.symbols()) {
207
208    unsigned SymbolIndex = Obj.getSymbolIndex(SymRef.getRawDataRefImpl());
209    uint64_t Value;
210    uint32_t NStrX;
211    uint8_t Type;
212    uint8_t Sect;
213    uint16_t Desc;
214
215    if (Obj.is64Bit()) {
216      const MachO::nlist_64 &NL64 =
217          Obj.getSymbol64TableEntry(SymRef.getRawDataRefImpl());
218      Value = NL64.n_value;
219      NStrX = NL64.n_strx;
220      Type = NL64.n_type;
221      Sect = NL64.n_sect;
222      Desc = NL64.n_desc;
223    } else {
224      const MachO::nlist &NL32 =
225          Obj.getSymbolTableEntry(SymRef.getRawDataRefImpl());
226      Value = NL32.n_value;
227      NStrX = NL32.n_strx;
228      Type = NL32.n_type;
229      Sect = NL32.n_sect;
230      Desc = NL32.n_desc;
231    }
232
233    // Skip stabs.
234    // FIXME: Are there other symbols we should be skipping?
235    if (Type & MachO::N_STAB)
236      continue;
237
238    Optional<StringRef> Name;
239    if (NStrX) {
240      if (auto NameOrErr = SymRef.getName())
241        Name = *NameOrErr;
242      else
243        return NameOrErr.takeError();
244    }
245
246    LLVM_DEBUG({
247      dbgs() << "  ";
248      if (!Name)
249        dbgs() << "<anonymous symbol>";
250      else
251        dbgs() << *Name;
252      dbgs() << ": value = " << formatv("{0:x16}", Value)
253             << ", type = " << formatv("{0:x2}", Type)
254             << ", desc = " << formatv("{0:x4}", Desc) << ", sect = ";
255      if (Sect)
256        dbgs() << static_cast<unsigned>(Sect - 1);
257      else
258        dbgs() << "none";
259      dbgs() << "\n";
260    });
261
262    // If this symbol has a section, sanity check that the addresses line up.
263    NormalizedSection *NSec = nullptr;
264    if (Sect != 0) {
265      if (auto NSecOrErr = findSectionByIndex(Sect - 1))
266        NSec = &*NSecOrErr;
267      else
268        return NSecOrErr.takeError();
269
270      if (Value < NSec->Address || Value > NSec->Address + NSec->Size)
271        return make_error<JITLinkError>("Symbol address does not fall within "
272                                        "section");
273    }
274
275    IndexToSymbol[SymbolIndex] =
276        &createNormalizedSymbol(*Name, Value, Type, Sect, Desc,
277                                getLinkage(Type), getScope(*Name, Type));
278  }
279
280  return Error::success();
281}
282
283void MachOLinkGraphBuilder::addSectionStartSymAndBlock(
284    Section &GraphSec, uint64_t Address, const char *Data, uint64_t Size,
285    uint32_t Alignment, bool IsLive) {
286  Block &B =
287      Data ? G->createContentBlock(GraphSec, StringRef(Data, Size), Address,
288                                   Alignment, 0)
289           : G->createZeroFillBlock(GraphSec, Size, Address, Alignment, 0);
290  auto &Sym = G->addAnonymousSymbol(B, 0, Size, false, IsLive);
291  assert(!AddrToCanonicalSymbol.count(Sym.getAddress()) &&
292         "Anonymous block start symbol clashes with existing symbol address");
293  AddrToCanonicalSymbol[Sym.getAddress()] = &Sym;
294}
295
296Error MachOLinkGraphBuilder::graphifyRegularSymbols() {
297
298  LLVM_DEBUG(dbgs() << "Creating graph symbols...\n");
299
300  /// We only have 256 section indexes: Use a vector rather than a map.
301  std::vector<std::vector<NormalizedSymbol *>> SecIndexToSymbols;
302  SecIndexToSymbols.resize(256);
303
304  // Create commons, externs, and absolutes, and partition all other symbols by
305  // section.
306  for (auto &KV : IndexToSymbol) {
307    auto &NSym = *KV.second;
308
309    switch (NSym.Type & MachO::N_TYPE) {
310    case MachO::N_UNDF:
311      if (NSym.Value) {
312        if (!NSym.Name)
313          return make_error<JITLinkError>("Anonymous common symbol at index " +
314                                          Twine(KV.first));
315        NSym.GraphSymbol = &G->addCommonSymbol(
316            *NSym.Name, NSym.S, getCommonSection(), 0, NSym.Value,
317            1ull << MachO::GET_COMM_ALIGN(NSym.Desc),
318            NSym.Desc & MachO::N_NO_DEAD_STRIP);
319      } else {
320        if (!NSym.Name)
321          return make_error<JITLinkError>("Anonymous external symbol at "
322                                          "index " +
323                                          Twine(KV.first));
324        NSym.GraphSymbol = &G->addExternalSymbol(
325            *NSym.Name, 0,
326            NSym.Desc & MachO::N_WEAK_REF ? Linkage::Weak : Linkage::Strong);
327      }
328      break;
329    case MachO::N_ABS:
330      if (!NSym.Name)
331        return make_error<JITLinkError>("Anonymous absolute symbol at index " +
332                                        Twine(KV.first));
333      NSym.GraphSymbol = &G->addAbsoluteSymbol(
334          *NSym.Name, NSym.Value, 0, Linkage::Strong, Scope::Default,
335          NSym.Desc & MachO::N_NO_DEAD_STRIP);
336      break;
337    case MachO::N_SECT:
338      SecIndexToSymbols[NSym.Sect - 1].push_back(&NSym);
339      break;
340    case MachO::N_PBUD:
341      return make_error<JITLinkError>(
342          "Unupported N_PBUD symbol " +
343          (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) +
344          " at index " + Twine(KV.first));
345    case MachO::N_INDR:
346      return make_error<JITLinkError>(
347          "Unupported N_INDR symbol " +
348          (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) +
349          " at index " + Twine(KV.first));
350    default:
351      return make_error<JITLinkError>(
352          "Unrecognized symbol type " + Twine(NSym.Type & MachO::N_TYPE) +
353          " for symbol " +
354          (NSym.Name ? ("\"" + *NSym.Name + "\"") : Twine("<anon>")) +
355          " at index " + Twine(KV.first));
356    }
357  }
358
359  // Loop over sections performing regular graphification for those that
360  // don't have custom parsers.
361  for (auto &KV : IndexToSection) {
362    auto SecIndex = KV.first;
363    auto &NSec = KV.second;
364
365    // Skip sections with custom parsers.
366    if (CustomSectionParserFunctions.count(NSec.GraphSection->getName())) {
367      LLVM_DEBUG({
368        dbgs() << "  Skipping section " << NSec.GraphSection->getName()
369               << " as it has a custom parser.\n";
370      });
371      continue;
372    } else
373      LLVM_DEBUG({
374        dbgs() << "  Processing section " << NSec.GraphSection->getName()
375               << "...\n";
376      });
377
378    bool SectionIsNoDeadStrip = NSec.Flags & MachO::S_ATTR_NO_DEAD_STRIP;
379    bool SectionIsText = NSec.Flags & MachO::S_ATTR_PURE_INSTRUCTIONS;
380
381    auto &SecNSymStack = SecIndexToSymbols[SecIndex];
382
383    // If this section is non-empty but there are no symbols covering it then
384    // create one block and anonymous symbol to cover the entire section.
385    if (SecNSymStack.empty()) {
386      if (NSec.Size > 0) {
387        LLVM_DEBUG({
388          dbgs() << "    Section non-empty, but contains no symbols. "
389                    "Creating anonymous block to cover "
390                 << formatv("{0:x16}", NSec.Address) << " -- "
391                 << formatv("{0:x16}", NSec.Address + NSec.Size) << "\n";
392        });
393        addSectionStartSymAndBlock(*NSec.GraphSection, NSec.Address, NSec.Data,
394                                   NSec.Size, NSec.Alignment,
395                                   SectionIsNoDeadStrip);
396      } else
397        LLVM_DEBUG({
398          dbgs() << "    Section empty and contains no symbols. Skipping.\n";
399        });
400      continue;
401    }
402
403    // Sort the symbol stack in by address, alt-entry status, scope, and name.
404    // We sort in reverse order so that symbols will be visited in the right
405    // order when we pop off the stack below.
406    llvm::sort(SecNSymStack, [](const NormalizedSymbol *LHS,
407                                const NormalizedSymbol *RHS) {
408      if (LHS->Value != RHS->Value)
409        return LHS->Value > RHS->Value;
410      if (isAltEntry(*LHS) != isAltEntry(*RHS))
411        return isAltEntry(*RHS);
412      if (LHS->S != RHS->S)
413        return static_cast<uint8_t>(LHS->S) < static_cast<uint8_t>(RHS->S);
414      return LHS->Name < RHS->Name;
415    });
416
417    // The first symbol in a section can not be an alt-entry symbol.
418    if (!SecNSymStack.empty() && isAltEntry(*SecNSymStack.back()))
419      return make_error<JITLinkError>(
420          "First symbol in " + NSec.GraphSection->getName() + " is alt-entry");
421
422    // If the section is non-empty but there is no symbol covering the start
423    // address then add an anonymous one.
424    if (SecNSymStack.back()->Value != NSec.Address) {
425      auto AnonBlockSize = SecNSymStack.back()->Value - NSec.Address;
426      LLVM_DEBUG({
427        dbgs() << "    Section start not covered by symbol. "
428               << "Creating anonymous block to cover [ "
429               << formatv("{0:x16}", NSec.Address) << " -- "
430               << formatv("{0:x16}", NSec.Address + AnonBlockSize) << " ]\n";
431      });
432      addSectionStartSymAndBlock(*NSec.GraphSection, NSec.Address, NSec.Data,
433                                 AnonBlockSize, NSec.Alignment,
434                                 SectionIsNoDeadStrip);
435    }
436
437    // Visit section symbols in order by popping off the reverse-sorted stack,
438    // building blocks for each alt-entry chain and creating symbols as we go.
439    while (!SecNSymStack.empty()) {
440      SmallVector<NormalizedSymbol *, 8> BlockSyms;
441
442      BlockSyms.push_back(SecNSymStack.back());
443      SecNSymStack.pop_back();
444      while (!SecNSymStack.empty() &&
445             (isAltEntry(*SecNSymStack.back()) ||
446              SecNSymStack.back()->Value == BlockSyms.back()->Value)) {
447        BlockSyms.push_back(SecNSymStack.back());
448        SecNSymStack.pop_back();
449      }
450
451      // BlockNSyms now contains the block symbols in reverse canonical order.
452      JITTargetAddress BlockStart = BlockSyms.front()->Value;
453      JITTargetAddress BlockEnd = SecNSymStack.empty()
454                                      ? NSec.Address + NSec.Size
455                                      : SecNSymStack.back()->Value;
456      JITTargetAddress BlockOffset = BlockStart - NSec.Address;
457      JITTargetAddress BlockSize = BlockEnd - BlockStart;
458
459      LLVM_DEBUG({
460        dbgs() << "    Creating block for " << formatv("{0:x16}", BlockStart)
461               << " -- " << formatv("{0:x16}", BlockEnd) << ": "
462               << NSec.GraphSection->getName() << " + "
463               << formatv("{0:x16}", BlockOffset) << " with "
464               << BlockSyms.size() << " symbol(s)...\n";
465      });
466
467      Block &B =
468          NSec.Data
469              ? G->createContentBlock(
470                    *NSec.GraphSection,
471                    StringRef(NSec.Data + BlockOffset, BlockSize), BlockStart,
472                    NSec.Alignment, BlockStart % NSec.Alignment)
473              : G->createZeroFillBlock(*NSec.GraphSection, BlockSize,
474                                       BlockStart, NSec.Alignment,
475                                       BlockStart % NSec.Alignment);
476
477      Optional<JITTargetAddress> LastCanonicalAddr;
478      JITTargetAddress SymEnd = BlockEnd;
479      while (!BlockSyms.empty()) {
480        auto &NSym = *BlockSyms.back();
481        BlockSyms.pop_back();
482
483        bool SymLive =
484            (NSym.Desc & MachO::N_NO_DEAD_STRIP) || SectionIsNoDeadStrip;
485
486        LLVM_DEBUG({
487          dbgs() << "      " << formatv("{0:x16}", NSym.Value) << " -- "
488                 << formatv("{0:x16}", SymEnd) << ": ";
489          if (!NSym.Name)
490            dbgs() << "<anonymous symbol>";
491          else
492            dbgs() << NSym.Name;
493          if (SymLive)
494            dbgs() << " [no-dead-strip]";
495          if (LastCanonicalAddr == NSym.Value)
496            dbgs() << " [non-canonical]";
497          dbgs() << "\n";
498        });
499
500        auto &Sym =
501            NSym.Name
502                ? G->addDefinedSymbol(B, NSym.Value - BlockStart, *NSym.Name,
503                                      SymEnd - NSym.Value, NSym.L, NSym.S,
504                                      SectionIsText, SymLive)
505                : G->addAnonymousSymbol(B, NSym.Value - BlockStart,
506                                        SymEnd - NSym.Value, SectionIsText,
507                                        SymLive);
508        NSym.GraphSymbol = &Sym;
509        if (LastCanonicalAddr != Sym.getAddress()) {
510          if (LastCanonicalAddr)
511            SymEnd = *LastCanonicalAddr;
512          LastCanonicalAddr = Sym.getAddress();
513          setCanonicalSymbol(Sym);
514        }
515      }
516    }
517  }
518
519  return Error::success();
520}
521
522Error MachOLinkGraphBuilder::graphifySectionsWithCustomParsers() {
523  // Graphify special sections.
524  for (auto &KV : IndexToSection) {
525    auto &NSec = KV.second;
526
527    auto HI = CustomSectionParserFunctions.find(NSec.GraphSection->getName());
528    if (HI != CustomSectionParserFunctions.end()) {
529      auto &Parse = HI->second;
530      if (auto Err = Parse(NSec))
531        return Err;
532    }
533  }
534
535  return Error::success();
536}
537
538} // end namespace jitlink
539} // end namespace llvm
540