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 "OutputSection.h"
49 #include "SymbolTable.h"
50 #include "Symbols.h"
51 #include "Target.h"
52 
53 #include "lld/Common/ErrorHandler.h"
54 #include "lld/Common/Memory.h"
55 #include "llvm/BinaryFormat/MachO.h"
56 #include "llvm/Support/Endian.h"
57 #include "llvm/Support/MemoryBuffer.h"
58 #include "llvm/Support/Path.h"
59 
60 using namespace llvm;
61 using namespace llvm::MachO;
62 using namespace llvm::support::endian;
63 using namespace llvm::sys;
64 using namespace lld;
65 using namespace lld::macho;
66 
67 std::vector<InputFile *> macho::inputFiles;
68 
69 // Open a given file path and return it as a memory-mapped file.
70 Optional<MemoryBufferRef> macho::readFile(StringRef path) {
71   // Open a file.
72   auto mbOrErr = MemoryBuffer::getFile(path);
73   if (auto ec = mbOrErr.getError()) {
74     error("cannot open " + path + ": " + ec.message());
75     return None;
76   }
77 
78   std::unique_ptr<MemoryBuffer> &mb = *mbOrErr;
79   MemoryBufferRef mbref = mb->getMemBufferRef();
80   make<std::unique_ptr<MemoryBuffer>>(std::move(mb)); // take mb ownership
81 
82   // If this is a regular non-fat file, return it.
83   const char *buf = mbref.getBufferStart();
84   auto *hdr = reinterpret_cast<const MachO::fat_header *>(buf);
85   if (read32be(&hdr->magic) != MachO::FAT_MAGIC)
86     return mbref;
87 
88   // Object files and archive files may be fat files, which contains
89   // multiple real files for different CPU ISAs. Here, we search for a
90   // file that matches with the current link target and returns it as
91   // a MemoryBufferRef.
92   auto *arch = reinterpret_cast<const MachO::fat_arch *>(buf + sizeof(*hdr));
93 
94   for (uint32_t i = 0, n = read32be(&hdr->nfat_arch); i < n; ++i) {
95     if (reinterpret_cast<const char *>(arch + i + 1) >
96         buf + mbref.getBufferSize()) {
97       error(path + ": fat_arch struct extends beyond end of file");
98       return None;
99     }
100 
101     if (read32be(&arch[i].cputype) != target->cpuType ||
102         read32be(&arch[i].cpusubtype) != target->cpuSubtype)
103       continue;
104 
105     uint32_t offset = read32be(&arch[i].offset);
106     uint32_t size = read32be(&arch[i].size);
107     if (offset + size > mbref.getBufferSize())
108       error(path + ": slice extends beyond end of file");
109     return MemoryBufferRef(StringRef(buf + offset, size), path.copy(bAlloc));
110   }
111 
112   error("unable to find matching architecture in " + path);
113   return None;
114 }
115 
116 static const load_command *findCommand(const mach_header_64 *hdr,
117                                        uint32_t type) {
118   const uint8_t *p =
119       reinterpret_cast<const uint8_t *>(hdr) + sizeof(mach_header_64);
120 
121   for (uint32_t i = 0, n = hdr->ncmds; i < n; ++i) {
122     auto *cmd = reinterpret_cast<const load_command *>(p);
123     if (cmd->cmd == type)
124       return cmd;
125     p += cmd->cmdsize;
126   }
127   return nullptr;
128 }
129 
130 std::vector<InputSection *>
131 InputFile::parseSections(ArrayRef<section_64> sections) {
132   std::vector<InputSection *> ret;
133   ret.reserve(sections.size());
134 
135   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
136 
137   for (const section_64 &sec : sections) {
138     InputSection *isec = make<InputSection>();
139     isec->file = this;
140     isec->header = &sec;
141     isec->name = StringRef(sec.sectname, strnlen(sec.sectname, 16));
142     isec->segname = StringRef(sec.segname, strnlen(sec.segname, 16));
143     isec->data = {buf + sec.offset, static_cast<size_t>(sec.size)};
144     if (sec.align >= 32)
145       error("alignment " + std::to_string(sec.align) + " of section " +
146             isec->name + " is too large");
147     else
148       isec->align = 1 << sec.align;
149     isec->flags = sec.flags;
150     ret.push_back(isec);
151   }
152 
153   return ret;
154 }
155 
156 void InputFile::parseRelocations(const section_64 &sec,
157                                  std::vector<Reloc> &relocs) {
158   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
159   ArrayRef<any_relocation_info> relInfos(
160       reinterpret_cast<const any_relocation_info *>(buf + sec.reloff),
161       sec.nreloc);
162 
163   for (const any_relocation_info &anyRel : relInfos) {
164     Reloc r;
165     if (anyRel.r_word0 & R_SCATTERED) {
166       error("TODO: Scattered relocations not supported");
167     } else {
168       auto rel = reinterpret_cast<const relocation_info &>(anyRel);
169       r.type = rel.r_type;
170       r.offset = rel.r_address;
171       r.addend = target->getImplicitAddend(buf + sec.offset + r.offset, r.type);
172       if (rel.r_extern) {
173         r.target = symbols[rel.r_symbolnum];
174       } else {
175         if (rel.r_symbolnum == 0 || rel.r_symbolnum > sections.size())
176           fatal("invalid section index in relocation for offset " +
177                 std::to_string(r.offset) + " in section " + sec.sectname +
178                 " of " + getName());
179         r.target = sections[rel.r_symbolnum - 1];
180       }
181     }
182     relocs.push_back(r);
183   }
184 }
185 
186 ObjFile::ObjFile(MemoryBufferRef mb) : InputFile(ObjKind, mb) {
187   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
188   auto *hdr = reinterpret_cast<const mach_header_64 *>(mb.getBufferStart());
189   ArrayRef<section_64> objSections;
190 
191   if (const load_command *cmd = findCommand(hdr, LC_SEGMENT_64)) {
192     auto *c = reinterpret_cast<const segment_command_64 *>(cmd);
193     objSections = ArrayRef<section_64>{
194         reinterpret_cast<const section_64 *>(c + 1), c->nsects};
195     sections = parseSections(objSections);
196   }
197 
198   // TODO: Error on missing LC_SYMTAB?
199   if (const load_command *cmd = findCommand(hdr, LC_SYMTAB)) {
200     auto *c = reinterpret_cast<const symtab_command *>(cmd);
201     const char *strtab = reinterpret_cast<const char *>(buf) + c->stroff;
202     ArrayRef<const nlist_64> nList(
203         reinterpret_cast<const nlist_64 *>(buf + c->symoff), c->nsyms);
204 
205     symbols.reserve(c->nsyms);
206 
207     for (const nlist_64 &sym : nList) {
208       StringRef name = strtab + sym.n_strx;
209 
210       // Undefined symbol
211       if (!sym.n_sect) {
212         symbols.push_back(symtab->addUndefined(name));
213         continue;
214       }
215 
216       InputSection *isec = sections[sym.n_sect - 1];
217       const section_64 &objSec = objSections[sym.n_sect - 1];
218       uint64_t value = sym.n_value - objSec.addr;
219 
220       // Global defined symbol
221       if (sym.n_type & N_EXT) {
222         symbols.push_back(symtab->addDefined(name, isec, value));
223         continue;
224       }
225 
226       // Local defined symbol
227       symbols.push_back(make<Defined>(name, isec, value));
228     }
229   }
230 
231   // The relocations may refer to the symbols, so we parse them after we have
232   // the symbols loaded.
233   if (!sections.empty()) {
234     auto it = sections.begin();
235     for (const section_64 &sec : objSections) {
236       parseRelocations(sec, (*it)->relocs);
237       ++it;
238     }
239   }
240 }
241 
242 DylibFile::DylibFile(MemoryBufferRef mb, DylibFile *umbrella)
243     : InputFile(DylibKind, mb) {
244   if (umbrella == nullptr)
245     umbrella = this;
246 
247   auto *buf = reinterpret_cast<const uint8_t *>(mb.getBufferStart());
248   auto *hdr = reinterpret_cast<const mach_header_64 *>(mb.getBufferStart());
249 
250   // Initialize dylibName.
251   if (const load_command *cmd = findCommand(hdr, LC_ID_DYLIB)) {
252     auto *c = reinterpret_cast<const dylib_command *>(cmd);
253     dylibName = reinterpret_cast<const char *>(cmd) + read32le(&c->dylib.name);
254   } else {
255     error("dylib " + getName() + " missing LC_ID_DYLIB load command");
256     return;
257   }
258 
259   // Initialize symbols.
260   if (const load_command *cmd = findCommand(hdr, LC_DYLD_INFO_ONLY)) {
261     auto *c = reinterpret_cast<const dyld_info_command *>(cmd);
262     parseTrie(buf + c->export_off, c->export_size,
263               [&](const Twine &name, uint64_t flags) {
264                 symbols.push_back(symtab->addDylib(saver.save(name), umbrella));
265               });
266   } else {
267     error("LC_DYLD_INFO_ONLY not found in " + getName());
268     return;
269   }
270 
271   if (hdr->flags & MH_NO_REEXPORTED_DYLIBS)
272     return;
273 
274   const uint8_t *p =
275       reinterpret_cast<const uint8_t *>(hdr) + sizeof(mach_header_64);
276   for (uint32_t i = 0, n = hdr->ncmds; i < n; ++i) {
277     auto *cmd = reinterpret_cast<const load_command *>(p);
278     p += cmd->cmdsize;
279     if (cmd->cmd != LC_REEXPORT_DYLIB)
280       continue;
281 
282     auto *c = reinterpret_cast<const dylib_command *>(cmd);
283     StringRef reexportPath =
284         reinterpret_cast<const char *>(c) + read32le(&c->dylib.name);
285     // TODO: Expand @loader_path, @executable_path etc in reexportPath
286     Optional<MemoryBufferRef> buffer = readFile(reexportPath);
287     if (!buffer) {
288       error("unable to read re-exported dylib at " + reexportPath);
289       return;
290     }
291     reexported.push_back(make<DylibFile>(*buffer, umbrella));
292   }
293 }
294 
295 DylibFile::DylibFile() : InputFile(DylibKind, MemoryBufferRef()) {}
296 
297 DylibFile *DylibFile::createLibSystemMock() {
298   auto *file = make<DylibFile>();
299   file->mb = MemoryBufferRef("", "/usr/lib/libSystem.B.dylib");
300   file->dylibName = "/usr/lib/libSystem.B.dylib";
301   file->symbols.push_back(symtab->addDylib("dyld_stub_binder", file));
302   return file;
303 }
304 
305 ArchiveFile::ArchiveFile(std::unique_ptr<llvm::object::Archive> &&f)
306     : InputFile(ArchiveKind, f->getMemoryBufferRef()), file(std::move(f)) {
307   for (const object::Archive::Symbol &sym : file->symbols())
308     symtab->addLazy(sym.getName(), this, sym);
309 }
310 
311 void ArchiveFile::fetch(const object::Archive::Symbol &sym) {
312   object::Archive::Child c =
313       CHECK(sym.getMember(), toString(this) +
314                                  ": could not get the member for symbol " +
315                                  sym.getName());
316 
317   if (!seen.insert(c.getChildOffset()).second)
318     return;
319 
320   MemoryBufferRef mb =
321       CHECK(c.getMemoryBufferRef(),
322             toString(this) +
323                 ": could not get the buffer for the member defining symbol " +
324                 sym.getName());
325   auto file = make<ObjFile>(mb);
326   sections.insert(sections.end(), file->sections.begin(), file->sections.end());
327 }
328 
329 // Returns "<internal>" or "baz.o".
330 std::string lld::toString(const InputFile *file) {
331   return file ? std::string(file->getName()) : "<internal>";
332 }
333