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 
28 using namespace llvm;
29 using namespace llvm::MachO;
30 using namespace lld;
31 using namespace lld::macho;
32 
33 namespace {
34 class LCLinkEdit;
35 class LCDyldInfo;
36 class LCSymtab;
37 
38 class Writer {
39 public:
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.
64 class LCDyldInfo : public LoadCommand {
65 public:
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 
97 class LCDysymtab : public LoadCommand {
98 public:
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 
108 class LCSegment : public LoadCommand {
109 public:
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 
156 private:
157   StringRef name;
158   OutputSegment *seg;
159 };
160 
161 class 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 
173 class LCSymtab : public LoadCommand {
174 public:
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
198 class LCDylib : public LoadCommand {
199 public:
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 
218 private:
219   LoadCommandType type;
220   StringRef path;
221 };
222 
223 class LCLoadDylinker : public LoadCommand {
224 public:
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 
241 private:
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 
248 void 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 
262 void 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 
302 static 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.
310 static 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 
336 static 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 
346 static 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 
367 template <typename T, typename F>
368 static 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.
375 static 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 
403 void 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 
451 void 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 
468 void 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 
480 void 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 
487 void 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 
533 void macho::writeResult() { Writer().run(); }
534 
535 void 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