1//===- Writer.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#include "Writer.h"
10#include "Config.h"
11#include "InputFiles.h"
12#include "InputSection.h"
13#include "MergedOutputSection.h"
14#include "OutputSection.h"
15#include "OutputSegment.h"
16#include "SymbolTable.h"
17#include "Symbols.h"
18#include "SyntheticSections.h"
19#include "Target.h"
20
21#include "lld/Common/ErrorHandler.h"
22#include "lld/Common/Memory.h"
23#include "llvm/BinaryFormat/MachO.h"
24#include "llvm/Support/LEB128.h"
25#include "llvm/Support/MathExtras.h"
26#include "llvm/Support/Path.h"
27
28using namespace llvm;
29using namespace llvm::MachO;
30using namespace lld;
31using namespace lld::macho;
32
33namespace {
34class LCLinkEdit;
35class LCDyldInfo;
36class LCSymtab;
37
38class Writer {
39public:
40  Writer() : buffer(errorHandler().outputBuffer) {}
41
42  void scanRelocations();
43  void createOutputSections();
44  void createLoadCommands();
45  void assignAddresses(OutputSegment *);
46  void createSymtabContents();
47
48  void openFile();
49  void writeSections();
50
51  void run();
52
53  std::unique_ptr<FileOutputBuffer> &buffer;
54  uint64_t addr = 0;
55  uint64_t fileOff = 0;
56  MachHeaderSection *headerSection = nullptr;
57  LazyBindingSection *lazyBindingSection = nullptr;
58  ExportSection *exportSection = nullptr;
59  StringTableSection *stringTableSection = nullptr;
60  SymtabSection *symtabSection = nullptr;
61};
62
63// LC_DYLD_INFO_ONLY stores the offsets of symbol import/export information.
64class LCDyldInfo : public LoadCommand {
65public:
66  LCDyldInfo(BindingSection *bindingSection,
67             LazyBindingSection *lazyBindingSection,
68             ExportSection *exportSection)
69      : bindingSection(bindingSection), lazyBindingSection(lazyBindingSection),
70        exportSection(exportSection) {}
71
72  uint32_t getSize() const override { return sizeof(dyld_info_command); }
73
74  void writeTo(uint8_t *buf) const override {
75    auto *c = reinterpret_cast<dyld_info_command *>(buf);
76    c->cmd = LC_DYLD_INFO_ONLY;
77    c->cmdsize = getSize();
78    if (bindingSection->isNeeded()) {
79      c->bind_off = bindingSection->fileOff;
80      c->bind_size = bindingSection->getFileSize();
81    }
82    if (lazyBindingSection->isNeeded()) {
83      c->lazy_bind_off = lazyBindingSection->fileOff;
84      c->lazy_bind_size = lazyBindingSection->getFileSize();
85    }
86    if (exportSection->isNeeded()) {
87      c->export_off = exportSection->fileOff;
88      c->export_size = exportSection->getFileSize();
89    }
90  }
91
92  BindingSection *bindingSection;
93  LazyBindingSection *lazyBindingSection;
94  ExportSection *exportSection;
95};
96
97class LCDysymtab : public LoadCommand {
98public:
99  uint32_t getSize() const override { return sizeof(dysymtab_command); }
100
101  void writeTo(uint8_t *buf) const override {
102    auto *c = reinterpret_cast<dysymtab_command *>(buf);
103    c->cmd = LC_DYSYMTAB;
104    c->cmdsize = getSize();
105  }
106};
107
108class LCSegment : public LoadCommand {
109public:
110  LCSegment(StringRef name, OutputSegment *seg) : name(name), seg(seg) {}
111
112  uint32_t getSize() const override {
113    return sizeof(segment_command_64) +
114           seg->numNonHiddenSections() * sizeof(section_64);
115  }
116
117  void writeTo(uint8_t *buf) const override {
118    auto *c = reinterpret_cast<segment_command_64 *>(buf);
119    buf += sizeof(segment_command_64);
120
121    c->cmd = LC_SEGMENT_64;
122    c->cmdsize = getSize();
123    memcpy(c->segname, name.data(), name.size());
124    c->fileoff = seg->fileOff;
125    c->maxprot = seg->maxProt;
126    c->initprot = seg->initProt;
127
128    if (seg->getSections().empty())
129      return;
130
131    c->vmaddr = seg->firstSection()->addr;
132    c->vmsize =
133        seg->lastSection()->addr + seg->lastSection()->getSize() - c->vmaddr;
134    c->nsects = seg->numNonHiddenSections();
135
136    for (OutputSection *osec : seg->getSections()) {
137      c->filesize += osec->getFileSize();
138
139      if (osec->isHidden())
140        continue;
141
142      auto *sectHdr = reinterpret_cast<section_64 *>(buf);
143      buf += sizeof(section_64);
144
145      memcpy(sectHdr->sectname, osec->name.data(), osec->name.size());
146      memcpy(sectHdr->segname, name.data(), name.size());
147
148      sectHdr->addr = osec->addr;
149      sectHdr->offset = osec->fileOff;
150      sectHdr->align = Log2_32(osec->align);
151      sectHdr->flags = osec->flags;
152      sectHdr->size = osec->getSize();
153    }
154  }
155
156private:
157  StringRef name;
158  OutputSegment *seg;
159};
160
161class LCMain : public LoadCommand {
162  uint32_t getSize() const override { return sizeof(entry_point_command); }
163
164  void writeTo(uint8_t *buf) const override {
165    auto *c = reinterpret_cast<entry_point_command *>(buf);
166    c->cmd = LC_MAIN;
167    c->cmdsize = getSize();
168    c->entryoff = config->entry->getFileOffset();
169    c->stacksize = 0;
170  }
171};
172
173class LCSymtab : public LoadCommand {
174public:
175  LCSymtab(SymtabSection *symtabSection, StringTableSection *stringTableSection)
176      : symtabSection(symtabSection), stringTableSection(stringTableSection) {}
177
178  uint32_t getSize() const override { return sizeof(symtab_command); }
179
180  void writeTo(uint8_t *buf) const override {
181    auto *c = reinterpret_cast<symtab_command *>(buf);
182    c->cmd = LC_SYMTAB;
183    c->cmdsize = getSize();
184    c->symoff = symtabSection->fileOff;
185    c->nsyms = symtabSection->getNumSymbols();
186    c->stroff = stringTableSection->fileOff;
187    c->strsize = stringTableSection->getFileSize();
188  }
189
190  SymtabSection *symtabSection = nullptr;
191  StringTableSection *stringTableSection = nullptr;
192};
193
194// There are several dylib load commands that share the same structure:
195//   * LC_LOAD_DYLIB
196//   * LC_ID_DYLIB
197//   * LC_REEXPORT_DYLIB
198class LCDylib : public LoadCommand {
199public:
200  LCDylib(LoadCommandType type, StringRef path) : type(type), path(path) {}
201
202  uint32_t getSize() const override {
203    return alignTo(sizeof(dylib_command) + path.size() + 1, 8);
204  }
205
206  void writeTo(uint8_t *buf) const override {
207    auto *c = reinterpret_cast<dylib_command *>(buf);
208    buf += sizeof(dylib_command);
209
210    c->cmd = type;
211    c->cmdsize = getSize();
212    c->dylib.name = sizeof(dylib_command);
213
214    memcpy(buf, path.data(), path.size());
215    buf[path.size()] = '\0';
216  }
217
218private:
219  LoadCommandType type;
220  StringRef path;
221};
222
223class LCLoadDylinker : public LoadCommand {
224public:
225  uint32_t getSize() const override {
226    return alignTo(sizeof(dylinker_command) + path.size() + 1, 8);
227  }
228
229  void writeTo(uint8_t *buf) const override {
230    auto *c = reinterpret_cast<dylinker_command *>(buf);
231    buf += sizeof(dylinker_command);
232
233    c->cmd = LC_LOAD_DYLINKER;
234    c->cmdsize = getSize();
235    c->name = sizeof(dylinker_command);
236
237    memcpy(buf, path.data(), path.size());
238    buf[path.size()] = '\0';
239  }
240
241private:
242  // Recent versions of Darwin won't run any binary that has dyld at a
243  // different location.
244  const StringRef path = "/usr/lib/dyld";
245};
246} // namespace
247
248void Writer::scanRelocations() {
249  for (InputSection *isec : inputSections) {
250    for (Reloc &r : isec->relocs) {
251      if (auto *s = r.target.dyn_cast<lld::macho::Symbol *>()) {
252        if (isa<Undefined>(s))
253          error("undefined symbol " + s->getName() + ", referenced from " +
254                sys::path::filename(isec->file->getName()));
255        else
256          target->prepareSymbolRelocation(*s, isec, r);
257      }
258    }
259  }
260}
261
262void Writer::createLoadCommands() {
263  headerSection->addLoadCommand(
264      make<LCDyldInfo>(in.binding, lazyBindingSection, exportSection));
265  headerSection->addLoadCommand(
266      make<LCSymtab>(symtabSection, stringTableSection));
267  headerSection->addLoadCommand(make<LCDysymtab>());
268
269  switch (config->outputType) {
270  case MH_EXECUTE:
271    headerSection->addLoadCommand(make<LCMain>());
272    headerSection->addLoadCommand(make<LCLoadDylinker>());
273    break;
274  case MH_DYLIB:
275    headerSection->addLoadCommand(
276        make<LCDylib>(LC_ID_DYLIB, config->installName));
277    break;
278  default:
279    llvm_unreachable("unhandled output file type");
280  }
281
282  uint8_t segIndex = 0;
283  for (OutputSegment *seg : outputSegments) {
284    headerSection->addLoadCommand(make<LCSegment>(seg->name, seg));
285    seg->index = segIndex++;
286  }
287
288  uint64_t dylibOrdinal = 1;
289  for (InputFile *file : inputFiles) {
290    if (auto *dylibFile = dyn_cast<DylibFile>(file)) {
291      headerSection->addLoadCommand(
292          make<LCDylib>(LC_LOAD_DYLIB, dylibFile->dylibName));
293      dylibFile->ordinal = dylibOrdinal++;
294
295      if (dylibFile->reexport)
296        headerSection->addLoadCommand(
297            make<LCDylib>(LC_REEXPORT_DYLIB, dylibFile->dylibName));
298    }
299  }
300}
301
302static size_t getSymbolPriority(const SymbolPriorityEntry &entry,
303                                const InputFile &file) {
304  return std::max(entry.objectFiles.lookup(sys::path::filename(file.getName())),
305                  entry.anyObjectFile);
306}
307
308// Each section gets assigned the priority of the highest-priority symbol it
309// contains.
310static DenseMap<const InputSection *, size_t> buildInputSectionPriorities() {
311  DenseMap<const InputSection *, size_t> sectionPriorities;
312
313  if (config->priorities.empty())
314    return sectionPriorities;
315
316  auto addSym = [&](Defined &sym) {
317    auto it = config->priorities.find(sym.getName());
318    if (it == config->priorities.end())
319      return;
320
321    SymbolPriorityEntry &entry = it->second;
322    size_t &priority = sectionPriorities[sym.isec];
323    priority = std::max(priority, getSymbolPriority(entry, *sym.isec->file));
324  };
325
326  // TODO: Make sure this handles weak symbols correctly.
327  for (InputFile *file : inputFiles)
328    if (isa<ObjFile>(file) || isa<ArchiveFile>(file))
329      for (lld::macho::Symbol *sym : file->symbols)
330        if (auto *d = dyn_cast<Defined>(sym))
331          addSym(*d);
332
333  return sectionPriorities;
334}
335
336static int segmentOrder(OutputSegment *seg) {
337  return StringSwitch<int>(seg->name)
338      .Case(segment_names::pageZero, -2)
339      .Case(segment_names::text, -1)
340      // Make sure __LINKEDIT is the last segment (i.e. all its hidden
341      // sections must be ordered after other sections).
342      .Case(segment_names::linkEdit, std::numeric_limits<int>::max())
343      .Default(0);
344}
345
346static int sectionOrder(OutputSection *osec) {
347  StringRef segname = osec->parent->name;
348  // Sections are uniquely identified by their segment + section name.
349  if (segname == segment_names::text) {
350    if (osec->name == section_names::header)
351      return -1;
352  } else if (segname == segment_names::linkEdit) {
353    return StringSwitch<int>(osec->name)
354        .Case(section_names::binding, -4)
355        .Case(section_names::export_, -3)
356        .Case(section_names::symbolTable, -2)
357        .Case(section_names::stringTable, -1)
358        .Default(0);
359  }
360  // ZeroFill sections must always be the at the end of their segments,
361  // otherwise subsequent sections may get overwritten with zeroes at runtime.
362  if (isZeroFill(osec->flags))
363    return std::numeric_limits<int>::max();
364  return 0;
365}
366
367template <typename T, typename F>
368static std::function<bool(T, T)> compareByOrder(F ord) {
369  return [=](T a, T b) { return ord(a) < ord(b); };
370}
371
372// Sorting only can happen once all outputs have been collected. Here we sort
373// segments, output sections within each segment, and input sections within each
374// output segment.
375static void sortSegmentsAndSections() {
376  llvm::stable_sort(outputSegments,
377                    compareByOrder<OutputSegment *>(segmentOrder));
378
379  DenseMap<const InputSection *, size_t> isecPriorities =
380      buildInputSectionPriorities();
381
382  uint32_t sectionIndex = 0;
383  for (OutputSegment *seg : outputSegments) {
384    seg->sortOutputSections(compareByOrder<OutputSection *>(sectionOrder));
385    for (auto *osec : seg->getSections()) {
386      // Now that the output sections are sorted, assign the final
387      // output section indices.
388      if (!osec->isHidden())
389        osec->index = ++sectionIndex;
390
391      if (!isecPriorities.empty()) {
392        if (auto *merged = dyn_cast<MergedOutputSection>(osec)) {
393          llvm::stable_sort(merged->inputs,
394                            [&](InputSection *a, InputSection *b) {
395                              return isecPriorities[a] > isecPriorities[b];
396                            });
397        }
398      }
399    }
400  }
401}
402
403void Writer::createOutputSections() {
404  // First, create hidden sections
405  headerSection = make<MachHeaderSection>();
406  lazyBindingSection = make<LazyBindingSection>();
407  stringTableSection = make<StringTableSection>();
408  symtabSection = make<SymtabSection>(*stringTableSection);
409  exportSection = make<ExportSection>();
410
411  switch (config->outputType) {
412  case MH_EXECUTE:
413    make<PageZeroSection>();
414    break;
415  case MH_DYLIB:
416    break;
417  default:
418    llvm_unreachable("unhandled output file type");
419  }
420
421  // Then merge input sections into output sections.
422  MapVector<std::pair<StringRef, StringRef>, MergedOutputSection *>
423      mergedOutputSections;
424  for (InputSection *isec : inputSections) {
425    MergedOutputSection *&osec =
426        mergedOutputSections[{isec->segname, isec->name}];
427    if (osec == nullptr)
428      osec = make<MergedOutputSection>(isec->name);
429    osec->mergeInput(isec);
430  }
431
432  for (const auto &it : mergedOutputSections) {
433    StringRef segname = it.first.first;
434    MergedOutputSection *osec = it.second;
435    getOrCreateOutputSegment(segname)->addOutputSection(osec);
436  }
437
438  for (SyntheticSection *ssec : syntheticSections) {
439    auto it = mergedOutputSections.find({ssec->segname, ssec->name});
440    if (it == mergedOutputSections.end()) {
441      if (ssec->isNeeded())
442        getOrCreateOutputSegment(ssec->segname)->addOutputSection(ssec);
443    } else {
444      error("section from " + it->second->firstSection()->file->getName() +
445            " conflicts with synthetic section " + ssec->segname + "," +
446            ssec->name);
447    }
448  }
449}
450
451void Writer::assignAddresses(OutputSegment *seg) {
452  addr = alignTo(addr, PageSize);
453  fileOff = alignTo(fileOff, PageSize);
454  seg->fileOff = fileOff;
455
456  for (auto *osec : seg->getSections()) {
457    addr = alignTo(addr, osec->align);
458    fileOff = alignTo(fileOff, osec->align);
459    osec->addr = addr;
460    osec->fileOff = isZeroFill(osec->flags) ? 0 : fileOff;
461    osec->finalize();
462
463    addr += osec->getSize();
464    fileOff += osec->getFileSize();
465  }
466}
467
468void Writer::openFile() {
469  Expected<std::unique_ptr<FileOutputBuffer>> bufferOrErr =
470      FileOutputBuffer::create(config->outputFile, fileOff,
471                               FileOutputBuffer::F_executable);
472
473  if (!bufferOrErr)
474    error("failed to open " + config->outputFile + ": " +
475          llvm::toString(bufferOrErr.takeError()));
476  else
477    buffer = std::move(*bufferOrErr);
478}
479
480void Writer::writeSections() {
481  uint8_t *buf = buffer->getBufferStart();
482  for (OutputSegment *seg : outputSegments)
483    for (OutputSection *osec : seg->getSections())
484      osec->writeTo(buf + osec->fileOff);
485}
486
487void Writer::run() {
488  // dyld requires __LINKEDIT segment to always exist (even if empty).
489  OutputSegment *linkEditSegment =
490      getOrCreateOutputSegment(segment_names::linkEdit);
491
492  scanRelocations();
493  if (in.stubHelper->isNeeded())
494    in.stubHelper->setup();
495
496  // Sort and assign sections to their respective segments. No more sections nor
497  // segments may be created after these methods run.
498  createOutputSections();
499  sortSegmentsAndSections();
500
501  createLoadCommands();
502
503  // Ensure that segments (and the sections they contain) are allocated
504  // addresses in ascending order, which dyld requires.
505  //
506  // Note that at this point, __LINKEDIT sections are empty, but we need to
507  // determine addresses of other segments/sections before generating its
508  // contents.
509  for (OutputSegment *seg : outputSegments)
510    if (seg != linkEditSegment)
511      assignAddresses(seg);
512
513  // Fill __LINKEDIT contents.
514  in.binding->finalizeContents();
515  lazyBindingSection->finalizeContents();
516  exportSection->finalizeContents();
517  symtabSection->finalizeContents();
518
519  // Now that __LINKEDIT is filled out, do a proper calculation of its
520  // addresses and offsets.
521  assignAddresses(linkEditSegment);
522
523  openFile();
524  if (errorCount())
525    return;
526
527  writeSections();
528
529  if (auto e = buffer->commit())
530    error("failed to write to the output file: " + toString(std::move(e)));
531}
532
533void macho::writeResult() { Writer().run(); }
534
535void macho::createSyntheticSections() {
536  in.binding = make<BindingSection>();
537  in.got = make<GotSection>();
538  in.lazyPointers = make<LazyPointerSection>();
539  in.stubs = make<StubsSection>();
540  in.stubHelper = make<StubHelperSection>();
541  in.imageLoaderCache = make<ImageLoaderCacheSection>();
542}
543