1//===- lib/MC/MachObjectWriter.cpp - Mach-O File Writer -------------------===//
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 "llvm/ADT/DenseMap.h"
10#include "llvm/ADT/Twine.h"
11#include "llvm/ADT/iterator_range.h"
12#include "llvm/BinaryFormat/MachO.h"
13#include "llvm/MC/MCAsmBackend.h"
14#include "llvm/MC/MCAsmLayout.h"
15#include "llvm/MC/MCAssembler.h"
16#include "llvm/MC/MCContext.h"
17#include "llvm/MC/MCDirectives.h"
18#include "llvm/MC/MCExpr.h"
19#include "llvm/MC/MCFixupKindInfo.h"
20#include "llvm/MC/MCFragment.h"
21#include "llvm/MC/MCMachObjectWriter.h"
22#include "llvm/MC/MCObjectFileInfo.h"
23#include "llvm/MC/MCObjectWriter.h"
24#include "llvm/MC/MCSection.h"
25#include "llvm/MC/MCSectionMachO.h"
26#include "llvm/MC/MCSymbol.h"
27#include "llvm/MC/MCSymbolMachO.h"
28#include "llvm/MC/MCValue.h"
29#include "llvm/Support/Alignment.h"
30#include "llvm/Support/Casting.h"
31#include "llvm/Support/Debug.h"
32#include "llvm/Support/ErrorHandling.h"
33#include "llvm/Support/LEB128.h"
34#include "llvm/Support/MathExtras.h"
35#include "llvm/Support/raw_ostream.h"
36#include <algorithm>
37#include <cassert>
38#include <cstdint>
39#include <string>
40#include <utility>
41#include <vector>
42
43using namespace llvm;
44
45#define DEBUG_TYPE "mc"
46
47void MachObjectWriter::reset() {
48  Relocations.clear();
49  IndirectSymBase.clear();
50  StringTable.clear();
51  LocalSymbolData.clear();
52  ExternalSymbolData.clear();
53  UndefinedSymbolData.clear();
54  MCObjectWriter::reset();
55}
56
57bool MachObjectWriter::doesSymbolRequireExternRelocation(const MCSymbol &S) {
58  // Undefined symbols are always extern.
59  if (S.isUndefined())
60    return true;
61
62  // References to weak definitions require external relocation entries; the
63  // definition may not always be the one in the same object file.
64  if (cast<MCSymbolMachO>(S).isWeakDefinition())
65    return true;
66
67  // Otherwise, we can use an internal relocation.
68  return false;
69}
70
71bool MachObjectWriter::
72MachSymbolData::operator<(const MachSymbolData &RHS) const {
73  return Symbol->getName() < RHS.Symbol->getName();
74}
75
76bool MachObjectWriter::isFixupKindPCRel(const MCAssembler &Asm, unsigned Kind) {
77  const MCFixupKindInfo &FKI = Asm.getBackend().getFixupKindInfo(
78    (MCFixupKind) Kind);
79
80  return FKI.Flags & MCFixupKindInfo::FKF_IsPCRel;
81}
82
83uint64_t MachObjectWriter::getFragmentAddress(const MCFragment *Fragment,
84                                              const MCAsmLayout &Layout) const {
85  return getSectionAddress(Fragment->getParent()) +
86         Layout.getFragmentOffset(Fragment);
87}
88
89uint64_t MachObjectWriter::getSymbolAddress(const MCSymbol &S,
90                                            const MCAsmLayout &Layout) const {
91  // If this is a variable, then recursively evaluate now.
92  if (S.isVariable()) {
93    if (const MCConstantExpr *C =
94          dyn_cast<const MCConstantExpr>(S.getVariableValue()))
95      return C->getValue();
96
97    MCValue Target;
98    if (!S.getVariableValue()->evaluateAsRelocatable(Target, &Layout, nullptr))
99      report_fatal_error("unable to evaluate offset for variable '" +
100                         S.getName() + "'");
101
102    // Verify that any used symbols are defined.
103    if (Target.getSymA() && Target.getSymA()->getSymbol().isUndefined())
104      report_fatal_error("unable to evaluate offset to undefined symbol '" +
105                         Target.getSymA()->getSymbol().getName() + "'");
106    if (Target.getSymB() && Target.getSymB()->getSymbol().isUndefined())
107      report_fatal_error("unable to evaluate offset to undefined symbol '" +
108                         Target.getSymB()->getSymbol().getName() + "'");
109
110    uint64_t Address = Target.getConstant();
111    if (Target.getSymA())
112      Address += getSymbolAddress(Target.getSymA()->getSymbol(), Layout);
113    if (Target.getSymB())
114      Address += getSymbolAddress(Target.getSymB()->getSymbol(), Layout);
115    return Address;
116  }
117
118  return getSectionAddress(S.getFragment()->getParent()) +
119         Layout.getSymbolOffset(S);
120}
121
122uint64_t MachObjectWriter::getPaddingSize(const MCSection *Sec,
123                                          const MCAsmLayout &Layout) const {
124  uint64_t EndAddr = getSectionAddress(Sec) + Layout.getSectionAddressSize(Sec);
125  unsigned Next = Sec->getLayoutOrder() + 1;
126  if (Next >= Layout.getSectionOrder().size())
127    return 0;
128
129  const MCSection &NextSec = *Layout.getSectionOrder()[Next];
130  if (NextSec.isVirtualSection())
131    return 0;
132  return offsetToAlignment(EndAddr, NextSec.getAlign());
133}
134
135void MachObjectWriter::writeHeader(MachO::HeaderFileType Type,
136                                   unsigned NumLoadCommands,
137                                   unsigned LoadCommandsSize,
138                                   bool SubsectionsViaSymbols) {
139  uint32_t Flags = 0;
140
141  if (SubsectionsViaSymbols)
142    Flags |= MachO::MH_SUBSECTIONS_VIA_SYMBOLS;
143
144  // struct mach_header (28 bytes) or
145  // struct mach_header_64 (32 bytes)
146
147  uint64_t Start = W.OS.tell();
148  (void) Start;
149
150  W.write<uint32_t>(is64Bit() ? MachO::MH_MAGIC_64 : MachO::MH_MAGIC);
151
152  W.write<uint32_t>(TargetObjectWriter->getCPUType());
153  W.write<uint32_t>(TargetObjectWriter->getCPUSubtype());
154
155  W.write<uint32_t>(Type);
156  W.write<uint32_t>(NumLoadCommands);
157  W.write<uint32_t>(LoadCommandsSize);
158  W.write<uint32_t>(Flags);
159  if (is64Bit())
160    W.write<uint32_t>(0); // reserved
161
162  assert(W.OS.tell() - Start == (is64Bit() ? sizeof(MachO::mach_header_64)
163                                           : sizeof(MachO::mach_header)));
164}
165
166void MachObjectWriter::writeWithPadding(StringRef Str, uint64_t Size) {
167  assert(Size >= Str.size());
168  W.OS << Str;
169  W.OS.write_zeros(Size - Str.size());
170}
171
172/// writeSegmentLoadCommand - Write a segment load command.
173///
174/// \param NumSections The number of sections in this segment.
175/// \param SectionDataSize The total size of the sections.
176void MachObjectWriter::writeSegmentLoadCommand(
177    StringRef Name, unsigned NumSections, uint64_t VMAddr, uint64_t VMSize,
178    uint64_t SectionDataStartOffset, uint64_t SectionDataSize, uint32_t MaxProt,
179    uint32_t InitProt) {
180  // struct segment_command (56 bytes) or
181  // struct segment_command_64 (72 bytes)
182
183  uint64_t Start = W.OS.tell();
184  (void) Start;
185
186  unsigned SegmentLoadCommandSize =
187    is64Bit() ? sizeof(MachO::segment_command_64):
188    sizeof(MachO::segment_command);
189  W.write<uint32_t>(is64Bit() ? MachO::LC_SEGMENT_64 : MachO::LC_SEGMENT);
190  W.write<uint32_t>(SegmentLoadCommandSize +
191          NumSections * (is64Bit() ? sizeof(MachO::section_64) :
192                         sizeof(MachO::section)));
193
194  writeWithPadding(Name, 16);
195  if (is64Bit()) {
196    W.write<uint64_t>(VMAddr);                 // vmaddr
197    W.write<uint64_t>(VMSize); // vmsize
198    W.write<uint64_t>(SectionDataStartOffset); // file offset
199    W.write<uint64_t>(SectionDataSize); // file size
200  } else {
201    W.write<uint32_t>(VMAddr);                 // vmaddr
202    W.write<uint32_t>(VMSize); // vmsize
203    W.write<uint32_t>(SectionDataStartOffset); // file offset
204    W.write<uint32_t>(SectionDataSize); // file size
205  }
206  // maxprot
207  W.write<uint32_t>(MaxProt);
208  // initprot
209  W.write<uint32_t>(InitProt);
210  W.write<uint32_t>(NumSections);
211  W.write<uint32_t>(0); // flags
212
213  assert(W.OS.tell() - Start == SegmentLoadCommandSize);
214}
215
216void MachObjectWriter::writeSection(const MCAsmLayout &Layout,
217                                    const MCSection &Sec, uint64_t VMAddr,
218                                    uint64_t FileOffset, unsigned Flags,
219                                    uint64_t RelocationsStart,
220                                    unsigned NumRelocations) {
221  uint64_t SectionSize = Layout.getSectionAddressSize(&Sec);
222  const MCSectionMachO &Section = cast<MCSectionMachO>(Sec);
223
224  // The offset is unused for virtual sections.
225  if (Section.isVirtualSection()) {
226    assert(Layout.getSectionFileSize(&Sec) == 0 && "Invalid file size!");
227    FileOffset = 0;
228  }
229
230  // struct section (68 bytes) or
231  // struct section_64 (80 bytes)
232
233  uint64_t Start = W.OS.tell();
234  (void) Start;
235
236  writeWithPadding(Section.getName(), 16);
237  writeWithPadding(Section.getSegmentName(), 16);
238  if (is64Bit()) {
239    W.write<uint64_t>(VMAddr);      // address
240    W.write<uint64_t>(SectionSize); // size
241  } else {
242    W.write<uint32_t>(VMAddr);      // address
243    W.write<uint32_t>(SectionSize); // size
244  }
245  W.write<uint32_t>(FileOffset);
246
247  W.write<uint32_t>(Log2(Section.getAlign()));
248  W.write<uint32_t>(NumRelocations ? RelocationsStart : 0);
249  W.write<uint32_t>(NumRelocations);
250  W.write<uint32_t>(Flags);
251  W.write<uint32_t>(IndirectSymBase.lookup(&Sec)); // reserved1
252  W.write<uint32_t>(Section.getStubSize()); // reserved2
253  if (is64Bit())
254    W.write<uint32_t>(0); // reserved3
255
256  assert(W.OS.tell() - Start ==
257         (is64Bit() ? sizeof(MachO::section_64) : sizeof(MachO::section)));
258}
259
260void MachObjectWriter::writeSymtabLoadCommand(uint32_t SymbolOffset,
261                                              uint32_t NumSymbols,
262                                              uint32_t StringTableOffset,
263                                              uint32_t StringTableSize) {
264  // struct symtab_command (24 bytes)
265
266  uint64_t Start = W.OS.tell();
267  (void) Start;
268
269  W.write<uint32_t>(MachO::LC_SYMTAB);
270  W.write<uint32_t>(sizeof(MachO::symtab_command));
271  W.write<uint32_t>(SymbolOffset);
272  W.write<uint32_t>(NumSymbols);
273  W.write<uint32_t>(StringTableOffset);
274  W.write<uint32_t>(StringTableSize);
275
276  assert(W.OS.tell() - Start == sizeof(MachO::symtab_command));
277}
278
279void MachObjectWriter::writeDysymtabLoadCommand(uint32_t FirstLocalSymbol,
280                                                uint32_t NumLocalSymbols,
281                                                uint32_t FirstExternalSymbol,
282                                                uint32_t NumExternalSymbols,
283                                                uint32_t FirstUndefinedSymbol,
284                                                uint32_t NumUndefinedSymbols,
285                                                uint32_t IndirectSymbolOffset,
286                                                uint32_t NumIndirectSymbols) {
287  // struct dysymtab_command (80 bytes)
288
289  uint64_t Start = W.OS.tell();
290  (void) Start;
291
292  W.write<uint32_t>(MachO::LC_DYSYMTAB);
293  W.write<uint32_t>(sizeof(MachO::dysymtab_command));
294  W.write<uint32_t>(FirstLocalSymbol);
295  W.write<uint32_t>(NumLocalSymbols);
296  W.write<uint32_t>(FirstExternalSymbol);
297  W.write<uint32_t>(NumExternalSymbols);
298  W.write<uint32_t>(FirstUndefinedSymbol);
299  W.write<uint32_t>(NumUndefinedSymbols);
300  W.write<uint32_t>(0); // tocoff
301  W.write<uint32_t>(0); // ntoc
302  W.write<uint32_t>(0); // modtaboff
303  W.write<uint32_t>(0); // nmodtab
304  W.write<uint32_t>(0); // extrefsymoff
305  W.write<uint32_t>(0); // nextrefsyms
306  W.write<uint32_t>(IndirectSymbolOffset);
307  W.write<uint32_t>(NumIndirectSymbols);
308  W.write<uint32_t>(0); // extreloff
309  W.write<uint32_t>(0); // nextrel
310  W.write<uint32_t>(0); // locreloff
311  W.write<uint32_t>(0); // nlocrel
312
313  assert(W.OS.tell() - Start == sizeof(MachO::dysymtab_command));
314}
315
316MachObjectWriter::MachSymbolData *
317MachObjectWriter::findSymbolData(const MCSymbol &Sym) {
318  for (auto *SymbolData :
319       {&LocalSymbolData, &ExternalSymbolData, &UndefinedSymbolData})
320    for (MachSymbolData &Entry : *SymbolData)
321      if (Entry.Symbol == &Sym)
322        return &Entry;
323
324  return nullptr;
325}
326
327const MCSymbol &MachObjectWriter::findAliasedSymbol(const MCSymbol &Sym) const {
328  const MCSymbol *S = &Sym;
329  while (S->isVariable()) {
330    const MCExpr *Value = S->getVariableValue();
331    const auto *Ref = dyn_cast<MCSymbolRefExpr>(Value);
332    if (!Ref)
333      return *S;
334    S = &Ref->getSymbol();
335  }
336  return *S;
337}
338
339void MachObjectWriter::writeNlist(MachSymbolData &MSD,
340                                  const MCAsmLayout &Layout) {
341  const MCSymbol *Symbol = MSD.Symbol;
342  const MCSymbol &Data = *Symbol;
343  const MCSymbol *AliasedSymbol = &findAliasedSymbol(*Symbol);
344  uint8_t SectionIndex = MSD.SectionIndex;
345  uint8_t Type = 0;
346  uint64_t Address = 0;
347  bool IsAlias = Symbol != AliasedSymbol;
348
349  const MCSymbol &OrigSymbol = *Symbol;
350  MachSymbolData *AliaseeInfo;
351  if (IsAlias) {
352    AliaseeInfo = findSymbolData(*AliasedSymbol);
353    if (AliaseeInfo)
354      SectionIndex = AliaseeInfo->SectionIndex;
355    Symbol = AliasedSymbol;
356    // FIXME: Should this update Data as well?
357  }
358
359  // Set the N_TYPE bits. See <mach-o/nlist.h>.
360  //
361  // FIXME: Are the prebound or indirect fields possible here?
362  if (IsAlias && Symbol->isUndefined())
363    Type = MachO::N_INDR;
364  else if (Symbol->isUndefined())
365    Type = MachO::N_UNDF;
366  else if (Symbol->isAbsolute())
367    Type = MachO::N_ABS;
368  else
369    Type = MachO::N_SECT;
370
371  // FIXME: Set STAB bits.
372
373  if (Data.isPrivateExtern())
374    Type |= MachO::N_PEXT;
375
376  // Set external bit.
377  if (Data.isExternal() || (!IsAlias && Symbol->isUndefined()))
378    Type |= MachO::N_EXT;
379
380  // Compute the symbol address.
381  if (IsAlias && Symbol->isUndefined())
382    Address = AliaseeInfo->StringIndex;
383  else if (Symbol->isDefined())
384    Address = getSymbolAddress(OrigSymbol, Layout);
385  else if (Symbol->isCommon()) {
386    // Common symbols are encoded with the size in the address
387    // field, and their alignment in the flags.
388    Address = Symbol->getCommonSize();
389  }
390
391  // struct nlist (12 bytes)
392
393  W.write<uint32_t>(MSD.StringIndex);
394  W.OS << char(Type);
395  W.OS << char(SectionIndex);
396
397  // The Mach-O streamer uses the lowest 16-bits of the flags for the 'desc'
398  // value.
399  bool EncodeAsAltEntry =
400    IsAlias && cast<MCSymbolMachO>(OrigSymbol).isAltEntry();
401  W.write<uint16_t>(cast<MCSymbolMachO>(Symbol)->getEncodedFlags(EncodeAsAltEntry));
402  if (is64Bit())
403    W.write<uint64_t>(Address);
404  else
405    W.write<uint32_t>(Address);
406}
407
408void MachObjectWriter::writeLinkeditLoadCommand(uint32_t Type,
409                                                uint32_t DataOffset,
410                                                uint32_t DataSize) {
411  uint64_t Start = W.OS.tell();
412  (void) Start;
413
414  W.write<uint32_t>(Type);
415  W.write<uint32_t>(sizeof(MachO::linkedit_data_command));
416  W.write<uint32_t>(DataOffset);
417  W.write<uint32_t>(DataSize);
418
419  assert(W.OS.tell() - Start == sizeof(MachO::linkedit_data_command));
420}
421
422static unsigned ComputeLinkerOptionsLoadCommandSize(
423  const std::vector<std::string> &Options, bool is64Bit)
424{
425  unsigned Size = sizeof(MachO::linker_option_command);
426  for (const std::string &Option : Options)
427    Size += Option.size() + 1;
428  return alignTo(Size, is64Bit ? 8 : 4);
429}
430
431void MachObjectWriter::writeLinkerOptionsLoadCommand(
432  const std::vector<std::string> &Options)
433{
434  unsigned Size = ComputeLinkerOptionsLoadCommandSize(Options, is64Bit());
435  uint64_t Start = W.OS.tell();
436  (void) Start;
437
438  W.write<uint32_t>(MachO::LC_LINKER_OPTION);
439  W.write<uint32_t>(Size);
440  W.write<uint32_t>(Options.size());
441  uint64_t BytesWritten = sizeof(MachO::linker_option_command);
442  for (const std::string &Option : Options) {
443    // Write each string, including the null byte.
444    W.OS << Option << '\0';
445    BytesWritten += Option.size() + 1;
446  }
447
448  // Pad to a multiple of the pointer size.
449  W.OS.write_zeros(
450      offsetToAlignment(BytesWritten, is64Bit() ? Align(8) : Align(4)));
451
452  assert(W.OS.tell() - Start == Size);
453}
454
455static bool isFixupTargetValid(const MCValue &Target) {
456  // Target is (LHS - RHS + cst).
457  // We don't support the form where LHS is null: -RHS + cst
458  if (!Target.getSymA() && Target.getSymB())
459    return false;
460  return true;
461}
462
463void MachObjectWriter::recordRelocation(MCAssembler &Asm,
464                                        const MCAsmLayout &Layout,
465                                        const MCFragment *Fragment,
466                                        const MCFixup &Fixup, MCValue Target,
467                                        uint64_t &FixedValue) {
468  if (!isFixupTargetValid(Target)) {
469    Asm.getContext().reportError(Fixup.getLoc(),
470                                 "unsupported relocation expression");
471    return;
472  }
473
474  TargetObjectWriter->recordRelocation(this, Asm, Layout, Fragment, Fixup,
475                                       Target, FixedValue);
476}
477
478void MachObjectWriter::bindIndirectSymbols(MCAssembler &Asm) {
479  // This is the point where 'as' creates actual symbols for indirect symbols
480  // (in the following two passes). It would be easier for us to do this sooner
481  // when we see the attribute, but that makes getting the order in the symbol
482  // table much more complicated than it is worth.
483  //
484  // FIXME: Revisit this when the dust settles.
485
486  // Report errors for use of .indirect_symbol not in a symbol pointer section
487  // or stub section.
488  for (IndirectSymbolData &ISD : llvm::make_range(Asm.indirect_symbol_begin(),
489                                                  Asm.indirect_symbol_end())) {
490    const MCSectionMachO &Section = cast<MCSectionMachO>(*ISD.Section);
491
492    if (Section.getType() != MachO::S_NON_LAZY_SYMBOL_POINTERS &&
493        Section.getType() != MachO::S_LAZY_SYMBOL_POINTERS &&
494        Section.getType() != MachO::S_THREAD_LOCAL_VARIABLE_POINTERS &&
495        Section.getType() != MachO::S_SYMBOL_STUBS) {
496      MCSymbol &Symbol = *ISD.Symbol;
497      report_fatal_error("indirect symbol '" + Symbol.getName() +
498                         "' not in a symbol pointer or stub section");
499    }
500  }
501
502  // Bind non-lazy symbol pointers first.
503  unsigned IndirectIndex = 0;
504  for (MCAssembler::indirect_symbol_iterator it = Asm.indirect_symbol_begin(),
505         ie = Asm.indirect_symbol_end(); it != ie; ++it, ++IndirectIndex) {
506    const MCSectionMachO &Section = cast<MCSectionMachO>(*it->Section);
507
508    if (Section.getType() != MachO::S_NON_LAZY_SYMBOL_POINTERS &&
509        Section.getType() !=  MachO::S_THREAD_LOCAL_VARIABLE_POINTERS)
510      continue;
511
512    // Initialize the section indirect symbol base, if necessary.
513    IndirectSymBase.insert(std::make_pair(it->Section, IndirectIndex));
514
515    Asm.registerSymbol(*it->Symbol);
516  }
517
518  // Then lazy symbol pointers and symbol stubs.
519  IndirectIndex = 0;
520  for (MCAssembler::indirect_symbol_iterator it = Asm.indirect_symbol_begin(),
521         ie = Asm.indirect_symbol_end(); it != ie; ++it, ++IndirectIndex) {
522    const MCSectionMachO &Section = cast<MCSectionMachO>(*it->Section);
523
524    if (Section.getType() != MachO::S_LAZY_SYMBOL_POINTERS &&
525        Section.getType() != MachO::S_SYMBOL_STUBS)
526      continue;
527
528    // Initialize the section indirect symbol base, if necessary.
529    IndirectSymBase.insert(std::make_pair(it->Section, IndirectIndex));
530
531    // Set the symbol type to undefined lazy, but only on construction.
532    //
533    // FIXME: Do not hardcode.
534    if (Asm.registerSymbol(*it->Symbol))
535      cast<MCSymbolMachO>(it->Symbol)->setReferenceTypeUndefinedLazy(true);
536  }
537}
538
539/// computeSymbolTable - Compute the symbol table data
540void MachObjectWriter::computeSymbolTable(
541    MCAssembler &Asm, std::vector<MachSymbolData> &LocalSymbolData,
542    std::vector<MachSymbolData> &ExternalSymbolData,
543    std::vector<MachSymbolData> &UndefinedSymbolData) {
544  // Build section lookup table.
545  DenseMap<const MCSection*, uint8_t> SectionIndexMap;
546  unsigned Index = 1;
547  for (MCAssembler::iterator it = Asm.begin(),
548         ie = Asm.end(); it != ie; ++it, ++Index)
549    SectionIndexMap[&*it] = Index;
550  assert(Index <= 256 && "Too many sections!");
551
552  // Build the string table.
553  for (const MCSymbol &Symbol : Asm.symbols()) {
554    if (!Asm.isSymbolLinkerVisible(Symbol))
555      continue;
556
557    StringTable.add(Symbol.getName());
558  }
559  StringTable.finalize();
560
561  // Build the symbol arrays but only for non-local symbols.
562  //
563  // The particular order that we collect and then sort the symbols is chosen to
564  // match 'as'. Even though it doesn't matter for correctness, this is
565  // important for letting us diff .o files.
566  for (const MCSymbol &Symbol : Asm.symbols()) {
567    // Ignore non-linker visible symbols.
568    if (!Asm.isSymbolLinkerVisible(Symbol))
569      continue;
570
571    if (!Symbol.isExternal() && !Symbol.isUndefined())
572      continue;
573
574    MachSymbolData MSD;
575    MSD.Symbol = &Symbol;
576    MSD.StringIndex = StringTable.getOffset(Symbol.getName());
577
578    if (Symbol.isUndefined()) {
579      MSD.SectionIndex = 0;
580      UndefinedSymbolData.push_back(MSD);
581    } else if (Symbol.isAbsolute()) {
582      MSD.SectionIndex = 0;
583      ExternalSymbolData.push_back(MSD);
584    } else {
585      MSD.SectionIndex = SectionIndexMap.lookup(&Symbol.getSection());
586      assert(MSD.SectionIndex && "Invalid section index!");
587      ExternalSymbolData.push_back(MSD);
588    }
589  }
590
591  // Now add the data for local symbols.
592  for (const MCSymbol &Symbol : Asm.symbols()) {
593    // Ignore non-linker visible symbols.
594    if (!Asm.isSymbolLinkerVisible(Symbol))
595      continue;
596
597    if (Symbol.isExternal() || Symbol.isUndefined())
598      continue;
599
600    MachSymbolData MSD;
601    MSD.Symbol = &Symbol;
602    MSD.StringIndex = StringTable.getOffset(Symbol.getName());
603
604    if (Symbol.isAbsolute()) {
605      MSD.SectionIndex = 0;
606      LocalSymbolData.push_back(MSD);
607    } else {
608      MSD.SectionIndex = SectionIndexMap.lookup(&Symbol.getSection());
609      assert(MSD.SectionIndex && "Invalid section index!");
610      LocalSymbolData.push_back(MSD);
611    }
612  }
613
614  // External and undefined symbols are required to be in lexicographic order.
615  llvm::sort(ExternalSymbolData);
616  llvm::sort(UndefinedSymbolData);
617
618  // Set the symbol indices.
619  Index = 0;
620  for (auto *SymbolData :
621       {&LocalSymbolData, &ExternalSymbolData, &UndefinedSymbolData})
622    for (MachSymbolData &Entry : *SymbolData)
623      Entry.Symbol->setIndex(Index++);
624
625  for (const MCSection &Section : Asm) {
626    for (RelAndSymbol &Rel : Relocations[&Section]) {
627      if (!Rel.Sym)
628        continue;
629
630      // Set the Index and the IsExtern bit.
631      unsigned Index = Rel.Sym->getIndex();
632      assert(isInt<24>(Index));
633      if (W.Endian == llvm::endianness::little)
634        Rel.MRE.r_word1 = (Rel.MRE.r_word1 & (~0U << 24)) | Index | (1 << 27);
635      else
636        Rel.MRE.r_word1 = (Rel.MRE.r_word1 & 0xff) | Index << 8 | (1 << 4);
637    }
638  }
639}
640
641void MachObjectWriter::computeSectionAddresses(const MCAssembler &Asm,
642                                               const MCAsmLayout &Layout) {
643  uint64_t StartAddress = 0;
644  for (const MCSection *Sec : Layout.getSectionOrder()) {
645    StartAddress = alignTo(StartAddress, Sec->getAlign());
646    SectionAddress[Sec] = StartAddress;
647    StartAddress += Layout.getSectionAddressSize(Sec);
648
649    // Explicitly pad the section to match the alignment requirements of the
650    // following one. This is for 'gas' compatibility, it shouldn't
651    /// strictly be necessary.
652    StartAddress += getPaddingSize(Sec, Layout);
653  }
654}
655
656void MachObjectWriter::executePostLayoutBinding(MCAssembler &Asm,
657                                                const MCAsmLayout &Layout) {
658  computeSectionAddresses(Asm, Layout);
659
660  // Create symbol data for any indirect symbols.
661  bindIndirectSymbols(Asm);
662}
663
664bool MachObjectWriter::isSymbolRefDifferenceFullyResolvedImpl(
665    const MCAssembler &Asm, const MCSymbol &A, const MCSymbol &B,
666    bool InSet) const {
667  // FIXME: We don't handle things like
668  // foo = .
669  // creating atoms.
670  if (A.isVariable() || B.isVariable())
671    return false;
672  return MCObjectWriter::isSymbolRefDifferenceFullyResolvedImpl(Asm, A, B,
673                                                                InSet);
674}
675
676bool MachObjectWriter::isSymbolRefDifferenceFullyResolvedImpl(
677    const MCAssembler &Asm, const MCSymbol &SymA, const MCFragment &FB,
678    bool InSet, bool IsPCRel) const {
679  if (InSet)
680    return true;
681
682  // The effective address is
683  //     addr(atom(A)) + offset(A)
684  //   - addr(atom(B)) - offset(B)
685  // and the offsets are not relocatable, so the fixup is fully resolved when
686  //  addr(atom(A)) - addr(atom(B)) == 0.
687  const MCSymbol &SA = findAliasedSymbol(SymA);
688  const MCSection &SecA = SA.getSection();
689  const MCSection &SecB = *FB.getParent();
690
691  if (IsPCRel) {
692    // The simple (Darwin, except on x86_64) way of dealing with this was to
693    // assume that any reference to a temporary symbol *must* be a temporary
694    // symbol in the same atom, unless the sections differ. Therefore, any PCrel
695    // relocation to a temporary symbol (in the same section) is fully
696    // resolved. This also works in conjunction with absolutized .set, which
697    // requires the compiler to use .set to absolutize the differences between
698    // symbols which the compiler knows to be assembly time constants, so we
699    // don't need to worry about considering symbol differences fully resolved.
700    //
701    // If the file isn't using sub-sections-via-symbols, we can make the
702    // same assumptions about any symbol that we normally make about
703    // assembler locals.
704
705    bool hasReliableSymbolDifference = isX86_64();
706    if (!hasReliableSymbolDifference) {
707      if (!SA.isInSection() || &SecA != &SecB ||
708          (!SA.isTemporary() && FB.getAtom() != SA.getFragment()->getAtom() &&
709           Asm.getSubsectionsViaSymbols()))
710        return false;
711      return true;
712    }
713  }
714
715  // If they are not in the same section, we can't compute the diff.
716  if (&SecA != &SecB)
717    return false;
718
719  const MCFragment *FA = SA.getFragment();
720
721  // Bail if the symbol has no fragment.
722  if (!FA)
723    return false;
724
725  // If the atoms are the same, they are guaranteed to have the same address.
726  if (FA->getAtom() == FB.getAtom())
727    return true;
728
729  // Otherwise, we can't prove this is fully resolved.
730  return false;
731}
732
733static MachO::LoadCommandType getLCFromMCVM(MCVersionMinType Type) {
734  switch (Type) {
735  case MCVM_OSXVersionMin:     return MachO::LC_VERSION_MIN_MACOSX;
736  case MCVM_IOSVersionMin:     return MachO::LC_VERSION_MIN_IPHONEOS;
737  case MCVM_TvOSVersionMin:    return MachO::LC_VERSION_MIN_TVOS;
738  case MCVM_WatchOSVersionMin: return MachO::LC_VERSION_MIN_WATCHOS;
739  }
740  llvm_unreachable("Invalid mc version min type");
741}
742
743void MachObjectWriter::populateAddrSigSection(MCAssembler &Asm) {
744  MCSection *AddrSigSection =
745      Asm.getContext().getObjectFileInfo()->getAddrSigSection();
746  unsigned Log2Size = is64Bit() ? 3 : 2;
747  for (const MCSymbol *S : getAddrsigSyms()) {
748    if (!S->isRegistered())
749      continue;
750    MachO::any_relocation_info MRE;
751    MRE.r_word0 = 0;
752    MRE.r_word1 = (Log2Size << 25) | (MachO::GENERIC_RELOC_VANILLA << 28);
753    addRelocation(S, AddrSigSection, MRE);
754  }
755}
756
757uint64_t MachObjectWriter::writeObject(MCAssembler &Asm,
758                                       const MCAsmLayout &Layout) {
759  uint64_t StartOffset = W.OS.tell();
760
761  populateAddrSigSection(Asm);
762
763  // Compute symbol table information and bind symbol indices.
764  computeSymbolTable(Asm, LocalSymbolData, ExternalSymbolData,
765                     UndefinedSymbolData);
766
767  if (!Asm.CGProfile.empty()) {
768    MCSection *CGProfileSection = Asm.getContext().getMachOSection(
769        "__LLVM", "__cg_profile", 0, SectionKind::getMetadata());
770    MCDataFragment *Frag = dyn_cast_or_null<MCDataFragment>(
771        &*CGProfileSection->getFragmentList().begin());
772    assert(Frag && "call graph profile section not reserved");
773    Frag->getContents().clear();
774    raw_svector_ostream OS(Frag->getContents());
775    for (const MCAssembler::CGProfileEntry &CGPE : Asm.CGProfile) {
776      uint32_t FromIndex = CGPE.From->getSymbol().getIndex();
777      uint32_t ToIndex = CGPE.To->getSymbol().getIndex();
778      support::endian::write(OS, FromIndex, W.Endian);
779      support::endian::write(OS, ToIndex, W.Endian);
780      support::endian::write(OS, CGPE.Count, W.Endian);
781    }
782  }
783
784  unsigned NumSections = Asm.size();
785  const MCAssembler::VersionInfoType &VersionInfo =
786    Layout.getAssembler().getVersionInfo();
787
788  // The section data starts after the header, the segment load command (and
789  // section headers) and the symbol table.
790  unsigned NumLoadCommands = 1;
791  uint64_t LoadCommandsSize = is64Bit() ?
792    sizeof(MachO::segment_command_64) + NumSections * sizeof(MachO::section_64):
793    sizeof(MachO::segment_command) + NumSections * sizeof(MachO::section);
794
795  // Add the deployment target version info load command size, if used.
796  if (VersionInfo.Major != 0) {
797    ++NumLoadCommands;
798    if (VersionInfo.EmitBuildVersion)
799      LoadCommandsSize += sizeof(MachO::build_version_command);
800    else
801      LoadCommandsSize += sizeof(MachO::version_min_command);
802  }
803
804  const MCAssembler::VersionInfoType &TargetVariantVersionInfo =
805      Layout.getAssembler().getDarwinTargetVariantVersionInfo();
806
807  // Add the target variant version info load command size, if used.
808  if (TargetVariantVersionInfo.Major != 0) {
809    ++NumLoadCommands;
810    assert(TargetVariantVersionInfo.EmitBuildVersion &&
811           "target variant should use build version");
812    LoadCommandsSize += sizeof(MachO::build_version_command);
813  }
814
815  // Add the data-in-code load command size, if used.
816  unsigned NumDataRegions = Asm.getDataRegions().size();
817  if (NumDataRegions) {
818    ++NumLoadCommands;
819    LoadCommandsSize += sizeof(MachO::linkedit_data_command);
820  }
821
822  // Add the loh load command size, if used.
823  uint64_t LOHRawSize = Asm.getLOHContainer().getEmitSize(*this, Layout);
824  uint64_t LOHSize = alignTo(LOHRawSize, is64Bit() ? 8 : 4);
825  if (LOHSize) {
826    ++NumLoadCommands;
827    LoadCommandsSize += sizeof(MachO::linkedit_data_command);
828  }
829
830  // Add the symbol table load command sizes, if used.
831  unsigned NumSymbols = LocalSymbolData.size() + ExternalSymbolData.size() +
832    UndefinedSymbolData.size();
833  if (NumSymbols) {
834    NumLoadCommands += 2;
835    LoadCommandsSize += (sizeof(MachO::symtab_command) +
836                         sizeof(MachO::dysymtab_command));
837  }
838
839  // Add the linker option load commands sizes.
840  for (const auto &Option : Asm.getLinkerOptions()) {
841    ++NumLoadCommands;
842    LoadCommandsSize += ComputeLinkerOptionsLoadCommandSize(Option, is64Bit());
843  }
844
845  // Compute the total size of the section data, as well as its file size and vm
846  // size.
847  uint64_t SectionDataStart = (is64Bit() ? sizeof(MachO::mach_header_64) :
848                               sizeof(MachO::mach_header)) + LoadCommandsSize;
849  uint64_t SectionDataSize = 0;
850  uint64_t SectionDataFileSize = 0;
851  uint64_t VMSize = 0;
852  for (const MCSection &Sec : Asm) {
853    uint64_t Address = getSectionAddress(&Sec);
854    uint64_t Size = Layout.getSectionAddressSize(&Sec);
855    uint64_t FileSize = Layout.getSectionFileSize(&Sec);
856    FileSize += getPaddingSize(&Sec, Layout);
857
858    VMSize = std::max(VMSize, Address + Size);
859
860    if (Sec.isVirtualSection())
861      continue;
862
863    SectionDataSize = std::max(SectionDataSize, Address + Size);
864    SectionDataFileSize = std::max(SectionDataFileSize, Address + FileSize);
865  }
866
867  // The section data is padded to pointer size bytes.
868  //
869  // FIXME: Is this machine dependent?
870  unsigned SectionDataPadding =
871      offsetToAlignment(SectionDataFileSize, is64Bit() ? Align(8) : Align(4));
872  SectionDataFileSize += SectionDataPadding;
873
874  // Write the prolog, starting with the header and load command...
875  writeHeader(MachO::MH_OBJECT, NumLoadCommands, LoadCommandsSize,
876              Asm.getSubsectionsViaSymbols());
877  uint32_t Prot =
878      MachO::VM_PROT_READ | MachO::VM_PROT_WRITE | MachO::VM_PROT_EXECUTE;
879  writeSegmentLoadCommand("", NumSections, 0, VMSize, SectionDataStart,
880                          SectionDataSize, Prot, Prot);
881
882  // ... and then the section headers.
883  uint64_t RelocTableEnd = SectionDataStart + SectionDataFileSize;
884  for (const MCSection &Section : Asm) {
885    const auto &Sec = cast<MCSectionMachO>(Section);
886    std::vector<RelAndSymbol> &Relocs = Relocations[&Sec];
887    unsigned NumRelocs = Relocs.size();
888    uint64_t SectionStart = SectionDataStart + getSectionAddress(&Sec);
889    unsigned Flags = Sec.getTypeAndAttributes();
890    if (Sec.hasInstructions())
891      Flags |= MachO::S_ATTR_SOME_INSTRUCTIONS;
892    writeSection(Layout, Sec, getSectionAddress(&Sec), SectionStart, Flags,
893                 RelocTableEnd, NumRelocs);
894    RelocTableEnd += NumRelocs * sizeof(MachO::any_relocation_info);
895  }
896
897  // Write out the deployment target information, if it's available.
898  auto EmitDeploymentTargetVersion =
899      [&](const MCAssembler::VersionInfoType &VersionInfo) {
900        auto EncodeVersion = [](VersionTuple V) -> uint32_t {
901          assert(!V.empty() && "empty version");
902          unsigned Update = V.getSubminor().value_or(0);
903          unsigned Minor = V.getMinor().value_or(0);
904          assert(Update < 256 && "unencodable update target version");
905          assert(Minor < 256 && "unencodable minor target version");
906          assert(V.getMajor() < 65536 && "unencodable major target version");
907          return Update | (Minor << 8) | (V.getMajor() << 16);
908        };
909        uint32_t EncodedVersion = EncodeVersion(VersionTuple(
910            VersionInfo.Major, VersionInfo.Minor, VersionInfo.Update));
911        uint32_t SDKVersion = !VersionInfo.SDKVersion.empty()
912                                  ? EncodeVersion(VersionInfo.SDKVersion)
913                                  : 0;
914        if (VersionInfo.EmitBuildVersion) {
915          // FIXME: Currently empty tools. Add clang version in the future.
916          W.write<uint32_t>(MachO::LC_BUILD_VERSION);
917          W.write<uint32_t>(sizeof(MachO::build_version_command));
918          W.write<uint32_t>(VersionInfo.TypeOrPlatform.Platform);
919          W.write<uint32_t>(EncodedVersion);
920          W.write<uint32_t>(SDKVersion);
921          W.write<uint32_t>(0); // Empty tools list.
922        } else {
923          MachO::LoadCommandType LCType =
924              getLCFromMCVM(VersionInfo.TypeOrPlatform.Type);
925          W.write<uint32_t>(LCType);
926          W.write<uint32_t>(sizeof(MachO::version_min_command));
927          W.write<uint32_t>(EncodedVersion);
928          W.write<uint32_t>(SDKVersion);
929        }
930      };
931  if (VersionInfo.Major != 0)
932    EmitDeploymentTargetVersion(VersionInfo);
933  if (TargetVariantVersionInfo.Major != 0)
934    EmitDeploymentTargetVersion(TargetVariantVersionInfo);
935
936  // Write the data-in-code load command, if used.
937  uint64_t DataInCodeTableEnd = RelocTableEnd + NumDataRegions * 8;
938  if (NumDataRegions) {
939    uint64_t DataRegionsOffset = RelocTableEnd;
940    uint64_t DataRegionsSize = NumDataRegions * 8;
941    writeLinkeditLoadCommand(MachO::LC_DATA_IN_CODE, DataRegionsOffset,
942                             DataRegionsSize);
943  }
944
945  // Write the loh load command, if used.
946  uint64_t LOHTableEnd = DataInCodeTableEnd + LOHSize;
947  if (LOHSize)
948    writeLinkeditLoadCommand(MachO::LC_LINKER_OPTIMIZATION_HINT,
949                             DataInCodeTableEnd, LOHSize);
950
951  // Write the symbol table load command, if used.
952  if (NumSymbols) {
953    unsigned FirstLocalSymbol = 0;
954    unsigned NumLocalSymbols = LocalSymbolData.size();
955    unsigned FirstExternalSymbol = FirstLocalSymbol + NumLocalSymbols;
956    unsigned NumExternalSymbols = ExternalSymbolData.size();
957    unsigned FirstUndefinedSymbol = FirstExternalSymbol + NumExternalSymbols;
958    unsigned NumUndefinedSymbols = UndefinedSymbolData.size();
959    unsigned NumIndirectSymbols = Asm.indirect_symbol_size();
960    unsigned NumSymTabSymbols =
961      NumLocalSymbols + NumExternalSymbols + NumUndefinedSymbols;
962    uint64_t IndirectSymbolSize = NumIndirectSymbols * 4;
963    uint64_t IndirectSymbolOffset = 0;
964
965    // If used, the indirect symbols are written after the section data.
966    if (NumIndirectSymbols)
967      IndirectSymbolOffset = LOHTableEnd;
968
969    // The symbol table is written after the indirect symbol data.
970    uint64_t SymbolTableOffset = LOHTableEnd + IndirectSymbolSize;
971
972    // The string table is written after symbol table.
973    uint64_t StringTableOffset =
974      SymbolTableOffset + NumSymTabSymbols * (is64Bit() ?
975                                              sizeof(MachO::nlist_64) :
976                                              sizeof(MachO::nlist));
977    writeSymtabLoadCommand(SymbolTableOffset, NumSymTabSymbols,
978                           StringTableOffset, StringTable.getSize());
979
980    writeDysymtabLoadCommand(FirstLocalSymbol, NumLocalSymbols,
981                             FirstExternalSymbol, NumExternalSymbols,
982                             FirstUndefinedSymbol, NumUndefinedSymbols,
983                             IndirectSymbolOffset, NumIndirectSymbols);
984  }
985
986  // Write the linker options load commands.
987  for (const auto &Option : Asm.getLinkerOptions())
988    writeLinkerOptionsLoadCommand(Option);
989
990  // Write the actual section data.
991  for (const MCSection &Sec : Asm) {
992    Asm.writeSectionData(W.OS, &Sec, Layout);
993
994    uint64_t Pad = getPaddingSize(&Sec, Layout);
995    W.OS.write_zeros(Pad);
996  }
997
998  // Write the extra padding.
999  W.OS.write_zeros(SectionDataPadding);
1000
1001  // Write the relocation entries.
1002  for (const MCSection &Sec : Asm) {
1003    // Write the section relocation entries, in reverse order to match 'as'
1004    // (approximately, the exact algorithm is more complicated than this).
1005    std::vector<RelAndSymbol> &Relocs = Relocations[&Sec];
1006    for (const RelAndSymbol &Rel : llvm::reverse(Relocs)) {
1007      W.write<uint32_t>(Rel.MRE.r_word0);
1008      W.write<uint32_t>(Rel.MRE.r_word1);
1009    }
1010  }
1011
1012  // Write out the data-in-code region payload, if there is one.
1013  for (MCAssembler::const_data_region_iterator
1014         it = Asm.data_region_begin(), ie = Asm.data_region_end();
1015         it != ie; ++it) {
1016    const DataRegionData *Data = &(*it);
1017    uint64_t Start = getSymbolAddress(*Data->Start, Layout);
1018    uint64_t End;
1019    if (Data->End)
1020      End = getSymbolAddress(*Data->End, Layout);
1021    else
1022      report_fatal_error("Data region not terminated");
1023
1024    LLVM_DEBUG(dbgs() << "data in code region-- kind: " << Data->Kind
1025                      << "  start: " << Start << "(" << Data->Start->getName()
1026                      << ")"
1027                      << "  end: " << End << "(" << Data->End->getName() << ")"
1028                      << "  size: " << End - Start << "\n");
1029    W.write<uint32_t>(Start);
1030    W.write<uint16_t>(End - Start);
1031    W.write<uint16_t>(Data->Kind);
1032  }
1033
1034  // Write out the loh commands, if there is one.
1035  if (LOHSize) {
1036#ifndef NDEBUG
1037    unsigned Start = W.OS.tell();
1038#endif
1039    Asm.getLOHContainer().emit(*this, Layout);
1040    // Pad to a multiple of the pointer size.
1041    W.OS.write_zeros(
1042        offsetToAlignment(LOHRawSize, is64Bit() ? Align(8) : Align(4)));
1043    assert(W.OS.tell() - Start == LOHSize);
1044  }
1045
1046  // Write the symbol table data, if used.
1047  if (NumSymbols) {
1048    // Write the indirect symbol entries.
1049    for (MCAssembler::const_indirect_symbol_iterator
1050           it = Asm.indirect_symbol_begin(),
1051           ie = Asm.indirect_symbol_end(); it != ie; ++it) {
1052      // Indirect symbols in the non-lazy symbol pointer section have some
1053      // special handling.
1054      const MCSectionMachO &Section =
1055          static_cast<const MCSectionMachO &>(*it->Section);
1056      if (Section.getType() == MachO::S_NON_LAZY_SYMBOL_POINTERS) {
1057        // If this symbol is defined and internal, mark it as such.
1058        if (it->Symbol->isDefined() && !it->Symbol->isExternal()) {
1059          uint32_t Flags = MachO::INDIRECT_SYMBOL_LOCAL;
1060          if (it->Symbol->isAbsolute())
1061            Flags |= MachO::INDIRECT_SYMBOL_ABS;
1062          W.write<uint32_t>(Flags);
1063          continue;
1064        }
1065      }
1066
1067      W.write<uint32_t>(it->Symbol->getIndex());
1068    }
1069
1070    // FIXME: Check that offsets match computed ones.
1071
1072    // Write the symbol table entries.
1073    for (auto *SymbolData :
1074         {&LocalSymbolData, &ExternalSymbolData, &UndefinedSymbolData})
1075      for (MachSymbolData &Entry : *SymbolData)
1076        writeNlist(Entry, Layout);
1077
1078    // Write the string table.
1079    StringTable.write(W.OS);
1080  }
1081
1082  return W.OS.tell() - StartOffset;
1083}
1084
1085std::unique_ptr<MCObjectWriter>
1086llvm::createMachObjectWriter(std::unique_ptr<MCMachObjectTargetWriter> MOTW,
1087                             raw_pwrite_stream &OS, bool IsLittleEndian) {
1088  return std::make_unique<MachObjectWriter>(std::move(MOTW), OS,
1089                                             IsLittleEndian);
1090}
1091