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