f1afc187aca23d2473ce8e4b2a8af88c44fb7275
[lldb.git] / lld / MachO / InputFiles.cpp
1 //===- InputFiles.cpp -----------------------------------------------------===//
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 // This file contains functions to parse Mach-O object files. In this comment,
10 // we describe the Mach-O file structure and how we parse it.
11 //
12 // Mach-O is not very different from ELF or COFF. The notion of symbols,
13 // sections and relocations exists in Mach-O as it does in ELF and COFF.
14 //
15 // Perhaps the notion that is new to those who know ELF/COFF is "subsections".
16 // In ELF/COFF, sections are an atomic unit of data copied from input files to
17 // output files. When we merge or garbage-collect sections, we treat each
18 // section as an atomic unit. In Mach-O, that's not the case. Sections can
19 // consist of multiple subsections, and subsections are a unit of merging and
20 // garbage-collecting. Therefore, Mach-O's subsections are more similar to
21 // ELF/COFF's sections than Mach-O's sections are.
22 //
23 // A section can have multiple symbols. A symbol that does not have the
24 // N_ALT_ENTRY attribute indicates a beginning of a subsection. Therefore, by
25 // definition, a symbol is always present at the beginning of each subsection. A
26 // symbol with N_ALT_ENTRY attribute does not start a new subsection and can
27 // point to a middle of a subsection.
28 //
29 // The notion of subsections also affects how relocations are represented in
30 // Mach-O. All references within a section need to be explicitly represented as
31 // relocations if they refer to different subsections, because we obviously need
32 // to fix up addresses if subsections are laid out in an output file differently
33 // than they were in object files. To represent that, Mach-O relocations can
34 // refer to an unnamed location via its address. Scattered relocations (those
35 // with the R_SCATTERED bit set) always refer to unnamed locations.
36 // Non-scattered relocations refer to an unnamed location if r_extern is not set
37 // and r_symbolnum is zero.
38 //
39 // Without the above differences, I think you can use your knowledge about ELF
40 // and COFF for Mach-O.
41 //
42 //===----------------------------------------------------------------------===//
43
44 #include "InputFiles.h"
45 #include "Config.h"
46 #include "ExportTrie.h"
47 #include "InputSection.h"
48 #include "MachOStructs.h"
49 #include "OutputSection.h"
50 #include "SymbolTable.h"
51 #include "Symbols.h"
52 #include "Target.h"
53
54 #include "lld/Common/ErrorHandler.h"
55 #include "lld/Common/Memory.h"
56 #include "llvm/BinaryFormat/MachO.h"
57 #include "llvm/Support/Endian.h"
58 #include "llvm/Support/MemoryBuffer.h"
59 #include "llvm/Support/Path.h"
60
61 using namespace llvm;
62 using namespace llvm::MachO;
63 using namespace llvm::support::endian;
64 using namespace llvm::sys;
65 using namespace lld;
66 using namespace lld::macho;
67
68 std::vector<InputFile *> macho::inputFiles;
69
70 // Open a given file path and return it as a memory-mapped file.
71 Optional<MemoryBufferRef> macho::readFile(StringRef path) {
72   // Open a file.
73   auto mbOrErr = MemoryBuffer::getFile(path);
74   if (auto ec = mbOrErr.getError()) {
75     error("cannot open " + path + ": " + ec.message());
76     return None;
77   }
78
79   std::unique_ptr<MemoryBuffer> &mb = *mbOrErr;
80   MemoryBufferRef mbref = mb->getMemBufferRef();
81   make<std::unique_ptr<MemoryBuffer>>(std::move(mb)); // take mb ownership
82
83   // If this is a regular non-fat file, return it.
84   const char *buf = mbref.getBufferStart();
85   auto *hdr = reinterpret_cast<const MachO::fat_header *>(buf);
86   if (read32be(&hdr->magic) != MachO::FAT_MAGIC)
87     return mbref;
88
89   // Object files and archive files may be fat files, which contains
90   // multiple real files for different CPU ISAs. Here, we search for a
91   // file that matches with the current link target and returns it as
92   // a MemoryBufferRef.
93   auto *arch = reinterpret_cast<const MachO::fat_arch *>(buf + sizeof(*hdr));
94
95   for (uint32_t i = 0, n = read32be(&hdr->nfat_arch); i < n; ++i) {
96     if (reinterpret_cast<const char *>(arch + i + 1) >
97         buf + mbref.getBufferSize()) {
98       error(path + ": fat_arch struct extends beyond end of file");
99       return None;
100     }
101
102     if (read32be(&arch[i].cputype) != target->cpuType ||
103         read32be(&arch[i].cpusubtype) != target->cpuSubtype)
104       continue;
105
106     uint32_t offset = read32be(&arch[i].offset);
107     uint32_t size = read32be(&arch[i].size);
108     if (offset + size > mbref.getBufferSize())
109       error(path + ": slice extends beyond end of file");
110     return MemoryBufferRef(StringRef(buf + offset, size), path.copy(bAlloc));
111   }
112
113   error("unable to find matching architecture in " + path);
114   return None;
115 }
116
117 static const load_command *findCommand(const mach_header_64 *hdr,
118                                        uint32_t type) {
119   const uint8_t *p =
120       reinterpret_cast<const uint8_t *>(hdr) + sizeof(mach_header_64);
121
122   for (uint32_t i = 0, n = hdr->ncmds; i < n; ++i) {
123     auto *cmd = reinterpret_cast<const load_command *>(p);
124     if (cmd->cmd == type)
125       return cmd;
126     p += cmd->cmdsize;
127   }
128   return nullptr;
129 }
130
131 void InputFile::parseSections(ArrayRef<section_64> sections) {
132   subsections.reserve(sections.size());
133   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
134
135   for (const section_64 &sec : sections) {
136     InputSection *isec = make<InputSection>();
137     isec->file = this;
138     isec->name = StringRef(sec.sectname, strnlen(sec.sectname, 16));
139     isec->segname = StringRef(sec.segname, strnlen(sec.segname, 16));
140     isec->data = {isZeroFill(sec.flags) ? nullptr : buf + sec.offset,
141                   static_cast<size_t>(sec.size)};
142     if (sec.align >= 32)
143       error("alignment " + std::to_string(sec.align) + " of section " +
144             isec->name + " is too large");
145     else
146       isec->align = 1 << sec.align;
147     isec->flags = sec.flags;
148     subsections.push_back({{0, isec}});
149   }
150 }
151
152 // Find the subsection corresponding to the greatest section offset that is <=
153 // that of the given offset.
154 //
155 // offset: an offset relative to the start of the original InputSection (before
156 // any subsection splitting has occurred). It will be updated to represent the
157 // same location as an offset relative to the start of the containing
158 // subsection.
159 static InputSection *findContainingSubsection(SubsectionMap &map,
160                                               uint32_t *offset) {
161   auto it = std::prev(map.upper_bound(*offset));
162   *offset -= it->first;
163   return it->second;
164 }
165
166 void InputFile::parseRelocations(const section_64 &sec,
167                                  SubsectionMap &subsecMap) {
168   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
169   ArrayRef<any_relocation_info> relInfos(
170       reinterpret_cast<const any_relocation_info *>(buf + sec.reloff),
171       sec.nreloc);
172
173   for (const any_relocation_info &anyRel : relInfos) {
174     if (anyRel.r_word0 & R_SCATTERED)
175       fatal("TODO: Scattered relocations not supported");
176
177     auto rel = reinterpret_cast<const relocation_info &>(anyRel);
178
179     Reloc r;
180     r.type = rel.r_type;
181     r.pcrel = rel.r_pcrel;
182     r.length = rel.r_length;
183     uint64_t rawAddend = target->getImplicitAddend(mb, sec, rel);
184
185     if (rel.r_extern) {
186       r.target = symbols[rel.r_symbolnum];
187       r.addend = rawAddend;
188     } else {
189       if (rel.r_symbolnum == 0 || rel.r_symbolnum > subsections.size())
190         fatal("invalid section index in relocation for offset " +
191               std::to_string(r.offset) + " in section " + sec.sectname +
192               " of " + getName());
193
194       SubsectionMap &targetSubsecMap = subsections[rel.r_symbolnum - 1];
195       const section_64 &targetSec = sectionHeaders[rel.r_symbolnum - 1];
196       uint32_t targetOffset;
197       if (rel.r_pcrel) {
198         // The implicit addend for pcrel section relocations is the pcrel offset
199         // in terms of the addresses in the input file. Here we adjust it so
200         // that it describes the offset from the start of the target section.
201         // TODO: The offset of 4 is probably not right for ARM64, nor for
202         //       relocations with r_length != 2.
203         targetOffset =
204             sec.addr + rel.r_address + 4 + rawAddend - targetSec.addr;
205       } else {
206         // The addend for a non-pcrel relocation is its absolute address.
207         targetOffset = rawAddend - targetSec.addr;
208       }
209       r.target = findContainingSubsection(targetSubsecMap, &targetOffset);
210       r.addend = targetOffset;
211     }
212
213     r.offset = rel.r_address;
214     InputSection *subsec = findContainingSubsection(subsecMap, &r.offset);
215     subsec->relocs.push_back(r);
216   }
217 }
218
219 void InputFile::parseSymbols(ArrayRef<structs::nlist_64> nList,
220                              const char *strtab, bool subsectionsViaSymbols) {
221   // resize(), not reserve(), because we are going to create N_ALT_ENTRY symbols
222   // out-of-sequence.
223   symbols.resize(nList.size());
224   std::vector<size_t> altEntrySymIdxs;
225
226   auto createDefined = [&](const structs::nlist_64 &sym, InputSection *isec,
227                            uint32_t value) -> Symbol * {
228     StringRef name = strtab + sym.n_strx;
229     if (sym.n_type & N_EXT)
230       // Global defined symbol
231       return symtab->addDefined(name, isec, value, sym.n_desc & N_WEAK_DEF);
232     // Local defined symbol
233     return make<Defined>(name, isec, value, sym.n_desc & N_WEAK_DEF);
234   };
235
236   for (size_t i = 0, n = nList.size(); i < n; ++i) {
237     const structs::nlist_64 &sym = nList[i];
238
239     // Undefined symbol
240     if (!sym.n_sect) {
241       StringRef name = strtab + sym.n_strx;
242       symbols[i] = symtab->addUndefined(name);
243       continue;
244     }
245
246     const section_64 &sec = sectionHeaders[sym.n_sect - 1];
247     SubsectionMap &subsecMap = subsections[sym.n_sect - 1];
248     uint64_t offset = sym.n_value - sec.addr;
249
250     // If the input file does not use subsections-via-symbols, all symbols can
251     // use the same subsection. Otherwise, we must split the sections along
252     // symbol boundaries.
253     if (!subsectionsViaSymbols) {
254       symbols[i] = createDefined(sym, subsecMap[0], offset);
255       continue;
256     }
257
258     // nList entries aren't necessarily arranged in address order. Therefore,
259     // we can't create alt-entry symbols at this point because a later symbol
260     // may split its section, which may affect which subsection the alt-entry
261     // symbol is assigned to. So we need to handle them in a second pass below.
262     if (sym.n_desc & N_ALT_ENTRY) {
263       altEntrySymIdxs.push_back(i);
264       continue;
265     }
266
267     // Find the subsection corresponding to the greatest section offset that is
268     // <= that of the current symbol. The subsection that we find either needs
269     // to be used directly or split in two.
270     uint32_t firstSize = offset;
271     InputSection *firstIsec = findContainingSubsection(subsecMap, &firstSize);
272
273     if (firstSize == 0) {
274       // Alias of an existing symbol, or the first symbol in the section. These
275       // are handled by reusing the existing section.
276       symbols[i] = createDefined(sym, firstIsec, 0);
277       continue;
278     }
279
280     // We saw a symbol definition at a new offset. Split the section into two
281     // subsections. The new symbol uses the second subsection.
282     auto *secondIsec = make<InputSection>(*firstIsec);
283     secondIsec->data = firstIsec->data.slice(firstSize);
284     firstIsec->data = firstIsec->data.slice(0, firstSize);
285     // TODO: ld64 appears to preserve the original alignment as well as each
286     // subsection's offset from the last aligned address. We should consider
287     // emulating that behavior.
288     secondIsec->align = MinAlign(firstIsec->align, offset);
289
290     subsecMap[offset] = secondIsec;
291     // By construction, the symbol will be at offset zero in the new section.
292     symbols[i] = createDefined(sym, secondIsec, 0);
293   }
294
295   for (size_t idx : altEntrySymIdxs) {
296     const structs::nlist_64 &sym = nList[idx];
297     SubsectionMap &subsecMap = subsections[sym.n_sect - 1];
298     uint32_t off = sym.n_value - sectionHeaders[sym.n_sect - 1].addr;
299     InputSection *subsec = findContainingSubsection(subsecMap, &off);
300     symbols[idx] = createDefined(sym, subsec, off);
301   }
302 }
303
304 ObjFile::ObjFile(MemoryBufferRef mb) : InputFile(ObjKind, mb) {
305   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
306   auto *hdr = reinterpret_cast<const mach_header_64 *>(mb.getBufferStart());
307
308   if (const load_command *cmd = findCommand(hdr, LC_SEGMENT_64)) {
309     auto *c = reinterpret_cast<const segment_command_64 *>(cmd);
310     sectionHeaders = ArrayRef<section_64>{
311         reinterpret_cast<const section_64 *>(c + 1), c->nsects};
312     parseSections(sectionHeaders);
313   }
314
315   // TODO: Error on missing LC_SYMTAB?
316   if (const load_command *cmd = findCommand(hdr, LC_SYMTAB)) {
317     auto *c = reinterpret_cast<const symtab_command *>(cmd);
318     ArrayRef<structs::nlist_64> nList(
319         reinterpret_cast<const structs::nlist_64 *>(buf + c->symoff), c->nsyms);
320     const char *strtab = reinterpret_cast<const char *>(buf) + c->stroff;
321     bool subsectionsViaSymbols = hdr->flags & MH_SUBSECTIONS_VIA_SYMBOLS;
322     parseSymbols(nList, strtab, subsectionsViaSymbols);
323   }
324
325   // The relocations may refer to the symbols, so we parse them after we have
326   // parsed all the symbols.
327   for (size_t i = 0, n = subsections.size(); i < n; ++i)
328     parseRelocations(sectionHeaders[i], subsections[i]);
329 }
330
331 DylibFile::DylibFile(MemoryBufferRef mb, DylibFile *umbrella)
332     : InputFile(DylibKind, mb) {
333   if (umbrella == nullptr)
334     umbrella = this;
335
336   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
337   auto *hdr = reinterpret_cast<const mach_header_64 *>(mb.getBufferStart());
338
339   // Initialize dylibName.
340   if (const load_command *cmd = findCommand(hdr, LC_ID_DYLIB)) {
341     auto *c = reinterpret_cast<const dylib_command *>(cmd);
342     dylibName = reinterpret_cast<const char *>(cmd) + read32le(&c->dylib.name);
343   } else {
344     error("dylib " + getName() + " missing LC_ID_DYLIB load command");
345     return;
346   }
347
348   // Initialize symbols.
349   if (const load_command *cmd = findCommand(hdr, LC_DYLD_INFO_ONLY)) {
350     auto *c = reinterpret_cast<const dyld_info_command *>(cmd);
351     parseTrie(buf + c->export_off, c->export_size,
352               [&](const Twine &name, uint64_t flags) {
353                 bool isWeakDef = flags & EXPORT_SYMBOL_FLAGS_WEAK_DEFINITION;
354                 symbols.push_back(
355                     symtab->addDylib(saver.save(name), umbrella, isWeakDef));
356               });
357   } else {
358     error("LC_DYLD_INFO_ONLY not found in " + getName());
359     return;
360   }
361
362   if (hdr->flags & MH_NO_REEXPORTED_DYLIBS)
363     return;
364
365   const uint8_t *p =
366       reinterpret_cast<const uint8_t *>(hdr) + sizeof(mach_header_64);
367   for (uint32_t i = 0, n = hdr->ncmds; i < n; ++i) {
368     auto *cmd = reinterpret_cast<const load_command *>(p);
369     p += cmd->cmdsize;
370     if (cmd->cmd != LC_REEXPORT_DYLIB)
371       continue;
372
373     auto *c = reinterpret_cast<const dylib_command *>(cmd);
374     StringRef reexportPath =
375         reinterpret_cast<const char *>(c) + read32le(&c->dylib.name);
376     // TODO: Expand @loader_path, @executable_path etc in reexportPath
377     Optional<MemoryBufferRef> buffer = readFile(reexportPath);
378     if (!buffer) {
379       error("unable to read re-exported dylib at " + reexportPath);
380       return;
381     }
382     reexported.push_back(make<DylibFile>(*buffer, umbrella));
383   }
384 }
385
386 DylibFile::DylibFile(std::shared_ptr<llvm::MachO::InterfaceFile> interface,
387                      DylibFile *umbrella)
388     : InputFile(DylibKind, MemoryBufferRef()) {
389   if (umbrella == nullptr)
390     umbrella = this;
391
392   dylibName = saver.save(interface->getInstallName());
393   // TODO(compnerd) filter out symbols based on the target platform
394   // TODO: handle weak defs
395   for (const auto symbol : interface->symbols())
396     if (symbol->getArchitectures().has(config->arch))
397       symbols.push_back(symtab->addDylib(saver.save(symbol->getName()),
398                                          umbrella, /*isWeakDef=*/false));
399   // TODO(compnerd) properly represent the hierarchy of the documents as it is
400   // in theory possible to have re-exported dylibs from re-exported dylibs which
401   // should be parent'ed to the child.
402   for (auto document : interface->documents())
403     reexported.push_back(make<DylibFile>(document, umbrella));
404 }
405
406 ArchiveFile::ArchiveFile(std::unique_ptr<llvm::object::Archive> &&f)
407     : InputFile(ArchiveKind, f->getMemoryBufferRef()), file(std::move(f)) {
408   for (const object::Archive::Symbol &sym : file->symbols())
409     symtab->addLazy(sym.getName(), this, sym);
410 }
411
412 void ArchiveFile::fetch(const object::Archive::Symbol &sym) {
413   object::Archive::Child c =
414       CHECK(sym.getMember(), toString(this) +
415                                  ": could not get the member for symbol " +
416                                  sym.getName());
417
418   if (!seen.insert(c.getChildOffset()).second)
419     return;
420
421   MemoryBufferRef mb =
422       CHECK(c.getMemoryBufferRef(),
423             toString(this) +
424                 ": could not get the buffer for the member defining symbol " +
425                 sym.getName());
426   auto file = make<ObjFile>(mb);
427   symbols.insert(symbols.end(), file->symbols.begin(), file->symbols.end());
428   subsections.insert(subsections.end(), file->subsections.begin(),
429                      file->subsections.end());
430 }
431
432 // Returns "<internal>" or "baz.o".
433 std::string lld::toString(const InputFile *file) {
434   return file ? std::string(file->getName()) : "<internal>";
435 }