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>(Obj.getFileName(), getPointerSize(Obj),
51                                     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 (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 
76 bool MachOLinkGraphBuilder::isAltEntry(const NormalizedSymbol &NSym) {
77   return NSym.Desc & MachO::N_ALT_ENTRY;
78 }
79 
80 unsigned
81 MachOLinkGraphBuilder::getPointerSize(const object::MachOObjectFile &Obj) {
82   return Obj.is64Bit() ? 8 : 4;
83 }
84 
85 support::endianness
86 MachOLinkGraphBuilder::getEndianness(const object::MachOObjectFile &Obj) {
87   return Obj.isLittleEndian() ? support::little : support::big;
88 }
89 
90 Section &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 
99 Error 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 
203 Error 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 
283 void 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 
296 Error 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 
522 Error 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