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 
43 using namespace llvm;
44 
45 #define DEBUG_TYPE "mc"
46 
47 void 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 
57 bool 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 
71 bool MachObjectWriter::
72 MachSymbolData::operator<(const MachSymbolData &RHS) const {
73   return Symbol->getName() < RHS.Symbol->getName();
74 }
75 
76 bool 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 
83 uint64_t MachObjectWriter::getFragmentAddress(const MCFragment *Fragment,
84                                               const MCAsmLayout &Layout) const {
85   return getSectionAddress(Fragment->getParent()) +
86          Layout.getFragmentOffset(Fragment);
87 }
88 
89 uint64_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 
122 uint64_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 
135 void 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 
166 void 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.
176 void 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 
216 void 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 
260 void 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 
279 void 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 
316 MachObjectWriter::MachSymbolData *
317 MachObjectWriter::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 
327 const 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 
339 void 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 
408 void 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 
422 static 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 
431 void 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 
455 static 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 
463 void 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 
478 void 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
540 void 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 == support::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 
641 void 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 
656 void 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 
664 bool 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 
676 bool 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     // For Darwin x86_64, there is one special case when the reference IsPCRel.
714     // If the fragment with the reference does not have a base symbol but meets
715     // the simple way of dealing with this, in that it is a temporary symbol in
716     // the same atom then it is assumed to be fully resolved.  This is needed so
717     // a relocation entry is not created and so the static linker does not
718     // mess up the reference later.
719     else if(!FB.getAtom() &&
720             SA.isTemporary() && SA.isInSection() && &SecA == &SecB){
721       return true;
722     }
723   }
724 
725   // If they are not in the same section, we can't compute the diff.
726   if (&SecA != &SecB)
727     return false;
728 
729   const MCFragment *FA = SA.getFragment();
730 
731   // Bail if the symbol has no fragment.
732   if (!FA)
733     return false;
734 
735   // If the atoms are the same, they are guaranteed to have the same address.
736   if (FA->getAtom() == FB.getAtom())
737     return true;
738 
739   // Otherwise, we can't prove this is fully resolved.
740   return false;
741 }
742 
743 static MachO::LoadCommandType getLCFromMCVM(MCVersionMinType Type) {
744   switch (Type) {
745   case MCVM_OSXVersionMin:     return MachO::LC_VERSION_MIN_MACOSX;
746   case MCVM_IOSVersionMin:     return MachO::LC_VERSION_MIN_IPHONEOS;
747   case MCVM_TvOSVersionMin:    return MachO::LC_VERSION_MIN_TVOS;
748   case MCVM_WatchOSVersionMin: return MachO::LC_VERSION_MIN_WATCHOS;
749   }
750   llvm_unreachable("Invalid mc version min type");
751 }
752 
753 void MachObjectWriter::populateAddrSigSection(MCAssembler &Asm) {
754   MCSection *AddrSigSection =
755       Asm.getContext().getObjectFileInfo()->getAddrSigSection();
756   unsigned Log2Size = is64Bit() ? 3 : 2;
757   for (const MCSymbol *S : getAddrsigSyms()) {
758     if (!S->isRegistered())
759       continue;
760     MachO::any_relocation_info MRE;
761     MRE.r_word0 = 0;
762     MRE.r_word1 = (Log2Size << 25) | (MachO::GENERIC_RELOC_VANILLA << 28);
763     addRelocation(S, AddrSigSection, MRE);
764   }
765 }
766 
767 uint64_t MachObjectWriter::writeObject(MCAssembler &Asm,
768                                        const MCAsmLayout &Layout) {
769   uint64_t StartOffset = W.OS.tell();
770 
771   populateAddrSigSection(Asm);
772 
773   // Compute symbol table information and bind symbol indices.
774   computeSymbolTable(Asm, LocalSymbolData, ExternalSymbolData,
775                      UndefinedSymbolData);
776 
777   if (!Asm.CGProfile.empty()) {
778     MCSection *CGProfileSection = Asm.getContext().getMachOSection(
779         "__LLVM", "__cg_profile", 0, SectionKind::getMetadata());
780     MCDataFragment *Frag = dyn_cast_or_null<MCDataFragment>(
781         &*CGProfileSection->getFragmentList().begin());
782     assert(Frag && "call graph profile section not reserved");
783     Frag->getContents().clear();
784     raw_svector_ostream OS(Frag->getContents());
785     for (const MCAssembler::CGProfileEntry &CGPE : Asm.CGProfile) {
786       uint32_t FromIndex = CGPE.From->getSymbol().getIndex();
787       uint32_t ToIndex = CGPE.To->getSymbol().getIndex();
788       support::endian::write(OS, FromIndex, W.Endian);
789       support::endian::write(OS, ToIndex, W.Endian);
790       support::endian::write(OS, CGPE.Count, W.Endian);
791     }
792   }
793 
794   unsigned NumSections = Asm.size();
795   const MCAssembler::VersionInfoType &VersionInfo =
796     Layout.getAssembler().getVersionInfo();
797 
798   // The section data starts after the header, the segment load command (and
799   // section headers) and the symbol table.
800   unsigned NumLoadCommands = 1;
801   uint64_t LoadCommandsSize = is64Bit() ?
802     sizeof(MachO::segment_command_64) + NumSections * sizeof(MachO::section_64):
803     sizeof(MachO::segment_command) + NumSections * sizeof(MachO::section);
804 
805   // Add the deployment target version info load command size, if used.
806   if (VersionInfo.Major != 0) {
807     ++NumLoadCommands;
808     if (VersionInfo.EmitBuildVersion)
809       LoadCommandsSize += sizeof(MachO::build_version_command);
810     else
811       LoadCommandsSize += sizeof(MachO::version_min_command);
812   }
813 
814   const MCAssembler::VersionInfoType &TargetVariantVersionInfo =
815       Layout.getAssembler().getDarwinTargetVariantVersionInfo();
816 
817   // Add the target variant version info load command size, if used.
818   if (TargetVariantVersionInfo.Major != 0) {
819     ++NumLoadCommands;
820     assert(TargetVariantVersionInfo.EmitBuildVersion &&
821            "target variant should use build version");
822     LoadCommandsSize += sizeof(MachO::build_version_command);
823   }
824 
825   // Add the data-in-code load command size, if used.
826   unsigned NumDataRegions = Asm.getDataRegions().size();
827   if (NumDataRegions) {
828     ++NumLoadCommands;
829     LoadCommandsSize += sizeof(MachO::linkedit_data_command);
830   }
831 
832   // Add the loh load command size, if used.
833   uint64_t LOHRawSize = Asm.getLOHContainer().getEmitSize(*this, Layout);
834   uint64_t LOHSize = alignTo(LOHRawSize, is64Bit() ? 8 : 4);
835   if (LOHSize) {
836     ++NumLoadCommands;
837     LoadCommandsSize += sizeof(MachO::linkedit_data_command);
838   }
839 
840   // Add the symbol table load command sizes, if used.
841   unsigned NumSymbols = LocalSymbolData.size() + ExternalSymbolData.size() +
842     UndefinedSymbolData.size();
843   if (NumSymbols) {
844     NumLoadCommands += 2;
845     LoadCommandsSize += (sizeof(MachO::symtab_command) +
846                          sizeof(MachO::dysymtab_command));
847   }
848 
849   // Add the linker option load commands sizes.
850   for (const auto &Option : Asm.getLinkerOptions()) {
851     ++NumLoadCommands;
852     LoadCommandsSize += ComputeLinkerOptionsLoadCommandSize(Option, is64Bit());
853   }
854 
855   // Compute the total size of the section data, as well as its file size and vm
856   // size.
857   uint64_t SectionDataStart = (is64Bit() ? sizeof(MachO::mach_header_64) :
858                                sizeof(MachO::mach_header)) + LoadCommandsSize;
859   uint64_t SectionDataSize = 0;
860   uint64_t SectionDataFileSize = 0;
861   uint64_t VMSize = 0;
862   for (const MCSection &Sec : Asm) {
863     uint64_t Address = getSectionAddress(&Sec);
864     uint64_t Size = Layout.getSectionAddressSize(&Sec);
865     uint64_t FileSize = Layout.getSectionFileSize(&Sec);
866     FileSize += getPaddingSize(&Sec, Layout);
867 
868     VMSize = std::max(VMSize, Address + Size);
869 
870     if (Sec.isVirtualSection())
871       continue;
872 
873     SectionDataSize = std::max(SectionDataSize, Address + Size);
874     SectionDataFileSize = std::max(SectionDataFileSize, Address + FileSize);
875   }
876 
877   // The section data is padded to pointer size bytes.
878   //
879   // FIXME: Is this machine dependent?
880   unsigned SectionDataPadding =
881       offsetToAlignment(SectionDataFileSize, is64Bit() ? Align(8) : Align(4));
882   SectionDataFileSize += SectionDataPadding;
883 
884   // Write the prolog, starting with the header and load command...
885   writeHeader(MachO::MH_OBJECT, NumLoadCommands, LoadCommandsSize,
886               Asm.getSubsectionsViaSymbols());
887   uint32_t Prot =
888       MachO::VM_PROT_READ | MachO::VM_PROT_WRITE | MachO::VM_PROT_EXECUTE;
889   writeSegmentLoadCommand("", NumSections, 0, VMSize, SectionDataStart,
890                           SectionDataSize, Prot, Prot);
891 
892   // ... and then the section headers.
893   uint64_t RelocTableEnd = SectionDataStart + SectionDataFileSize;
894   for (const MCSection &Section : Asm) {
895     const auto &Sec = cast<MCSectionMachO>(Section);
896     std::vector<RelAndSymbol> &Relocs = Relocations[&Sec];
897     unsigned NumRelocs = Relocs.size();
898     uint64_t SectionStart = SectionDataStart + getSectionAddress(&Sec);
899     unsigned Flags = Sec.getTypeAndAttributes();
900     if (Sec.hasInstructions())
901       Flags |= MachO::S_ATTR_SOME_INSTRUCTIONS;
902     writeSection(Layout, Sec, getSectionAddress(&Sec), SectionStart, Flags,
903                  RelocTableEnd, NumRelocs);
904     RelocTableEnd += NumRelocs * sizeof(MachO::any_relocation_info);
905   }
906 
907   // Write out the deployment target information, if it's available.
908   auto EmitDeploymentTargetVersion =
909       [&](const MCAssembler::VersionInfoType &VersionInfo) {
910         auto EncodeVersion = [](VersionTuple V) -> uint32_t {
911           assert(!V.empty() && "empty version");
912           unsigned Update = V.getSubminor().value_or(0);
913           unsigned Minor = V.getMinor().value_or(0);
914           assert(Update < 256 && "unencodable update target version");
915           assert(Minor < 256 && "unencodable minor target version");
916           assert(V.getMajor() < 65536 && "unencodable major target version");
917           return Update | (Minor << 8) | (V.getMajor() << 16);
918         };
919         uint32_t EncodedVersion = EncodeVersion(VersionTuple(
920             VersionInfo.Major, VersionInfo.Minor, VersionInfo.Update));
921         uint32_t SDKVersion = !VersionInfo.SDKVersion.empty()
922                                   ? EncodeVersion(VersionInfo.SDKVersion)
923                                   : 0;
924         if (VersionInfo.EmitBuildVersion) {
925           // FIXME: Currently empty tools. Add clang version in the future.
926           W.write<uint32_t>(MachO::LC_BUILD_VERSION);
927           W.write<uint32_t>(sizeof(MachO::build_version_command));
928           W.write<uint32_t>(VersionInfo.TypeOrPlatform.Platform);
929           W.write<uint32_t>(EncodedVersion);
930           W.write<uint32_t>(SDKVersion);
931           W.write<uint32_t>(0); // Empty tools list.
932         } else {
933           MachO::LoadCommandType LCType =
934               getLCFromMCVM(VersionInfo.TypeOrPlatform.Type);
935           W.write<uint32_t>(LCType);
936           W.write<uint32_t>(sizeof(MachO::version_min_command));
937           W.write<uint32_t>(EncodedVersion);
938           W.write<uint32_t>(SDKVersion);
939         }
940       };
941   if (VersionInfo.Major != 0)
942     EmitDeploymentTargetVersion(VersionInfo);
943   if (TargetVariantVersionInfo.Major != 0)
944     EmitDeploymentTargetVersion(TargetVariantVersionInfo);
945 
946   // Write the data-in-code load command, if used.
947   uint64_t DataInCodeTableEnd = RelocTableEnd + NumDataRegions * 8;
948   if (NumDataRegions) {
949     uint64_t DataRegionsOffset = RelocTableEnd;
950     uint64_t DataRegionsSize = NumDataRegions * 8;
951     writeLinkeditLoadCommand(MachO::LC_DATA_IN_CODE, DataRegionsOffset,
952                              DataRegionsSize);
953   }
954 
955   // Write the loh load command, if used.
956   uint64_t LOHTableEnd = DataInCodeTableEnd + LOHSize;
957   if (LOHSize)
958     writeLinkeditLoadCommand(MachO::LC_LINKER_OPTIMIZATION_HINT,
959                              DataInCodeTableEnd, LOHSize);
960 
961   // Write the symbol table load command, if used.
962   if (NumSymbols) {
963     unsigned FirstLocalSymbol = 0;
964     unsigned NumLocalSymbols = LocalSymbolData.size();
965     unsigned FirstExternalSymbol = FirstLocalSymbol + NumLocalSymbols;
966     unsigned NumExternalSymbols = ExternalSymbolData.size();
967     unsigned FirstUndefinedSymbol = FirstExternalSymbol + NumExternalSymbols;
968     unsigned NumUndefinedSymbols = UndefinedSymbolData.size();
969     unsigned NumIndirectSymbols = Asm.indirect_symbol_size();
970     unsigned NumSymTabSymbols =
971       NumLocalSymbols + NumExternalSymbols + NumUndefinedSymbols;
972     uint64_t IndirectSymbolSize = NumIndirectSymbols * 4;
973     uint64_t IndirectSymbolOffset = 0;
974 
975     // If used, the indirect symbols are written after the section data.
976     if (NumIndirectSymbols)
977       IndirectSymbolOffset = LOHTableEnd;
978 
979     // The symbol table is written after the indirect symbol data.
980     uint64_t SymbolTableOffset = LOHTableEnd + IndirectSymbolSize;
981 
982     // The string table is written after symbol table.
983     uint64_t StringTableOffset =
984       SymbolTableOffset + NumSymTabSymbols * (is64Bit() ?
985                                               sizeof(MachO::nlist_64) :
986                                               sizeof(MachO::nlist));
987     writeSymtabLoadCommand(SymbolTableOffset, NumSymTabSymbols,
988                            StringTableOffset, StringTable.getSize());
989 
990     writeDysymtabLoadCommand(FirstLocalSymbol, NumLocalSymbols,
991                              FirstExternalSymbol, NumExternalSymbols,
992                              FirstUndefinedSymbol, NumUndefinedSymbols,
993                              IndirectSymbolOffset, NumIndirectSymbols);
994   }
995 
996   // Write the linker options load commands.
997   for (const auto &Option : Asm.getLinkerOptions())
998     writeLinkerOptionsLoadCommand(Option);
999 
1000   // Write the actual section data.
1001   for (const MCSection &Sec : Asm) {
1002     Asm.writeSectionData(W.OS, &Sec, Layout);
1003 
1004     uint64_t Pad = getPaddingSize(&Sec, Layout);
1005     W.OS.write_zeros(Pad);
1006   }
1007 
1008   // Write the extra padding.
1009   W.OS.write_zeros(SectionDataPadding);
1010 
1011   // Write the relocation entries.
1012   for (const MCSection &Sec : Asm) {
1013     // Write the section relocation entries, in reverse order to match 'as'
1014     // (approximately, the exact algorithm is more complicated than this).
1015     std::vector<RelAndSymbol> &Relocs = Relocations[&Sec];
1016     for (const RelAndSymbol &Rel : llvm::reverse(Relocs)) {
1017       W.write<uint32_t>(Rel.MRE.r_word0);
1018       W.write<uint32_t>(Rel.MRE.r_word1);
1019     }
1020   }
1021 
1022   // Write out the data-in-code region payload, if there is one.
1023   for (MCAssembler::const_data_region_iterator
1024          it = Asm.data_region_begin(), ie = Asm.data_region_end();
1025          it != ie; ++it) {
1026     const DataRegionData *Data = &(*it);
1027     uint64_t Start = getSymbolAddress(*Data->Start, Layout);
1028     uint64_t End;
1029     if (Data->End)
1030       End = getSymbolAddress(*Data->End, Layout);
1031     else
1032       report_fatal_error("Data region not terminated");
1033 
1034     LLVM_DEBUG(dbgs() << "data in code region-- kind: " << Data->Kind
1035                       << "  start: " << Start << "(" << Data->Start->getName()
1036                       << ")"
1037                       << "  end: " << End << "(" << Data->End->getName() << ")"
1038                       << "  size: " << End - Start << "\n");
1039     W.write<uint32_t>(Start);
1040     W.write<uint16_t>(End - Start);
1041     W.write<uint16_t>(Data->Kind);
1042   }
1043 
1044   // Write out the loh commands, if there is one.
1045   if (LOHSize) {
1046 #ifndef NDEBUG
1047     unsigned Start = W.OS.tell();
1048 #endif
1049     Asm.getLOHContainer().emit(*this, Layout);
1050     // Pad to a multiple of the pointer size.
1051     W.OS.write_zeros(
1052         offsetToAlignment(LOHRawSize, is64Bit() ? Align(8) : Align(4)));
1053     assert(W.OS.tell() - Start == LOHSize);
1054   }
1055 
1056   // Write the symbol table data, if used.
1057   if (NumSymbols) {
1058     // Write the indirect symbol entries.
1059     for (MCAssembler::const_indirect_symbol_iterator
1060            it = Asm.indirect_symbol_begin(),
1061            ie = Asm.indirect_symbol_end(); it != ie; ++it) {
1062       // Indirect symbols in the non-lazy symbol pointer section have some
1063       // special handling.
1064       const MCSectionMachO &Section =
1065           static_cast<const MCSectionMachO &>(*it->Section);
1066       if (Section.getType() == MachO::S_NON_LAZY_SYMBOL_POINTERS) {
1067         // If this symbol is defined and internal, mark it as such.
1068         if (it->Symbol->isDefined() && !it->Symbol->isExternal()) {
1069           uint32_t Flags = MachO::INDIRECT_SYMBOL_LOCAL;
1070           if (it->Symbol->isAbsolute())
1071             Flags |= MachO::INDIRECT_SYMBOL_ABS;
1072           W.write<uint32_t>(Flags);
1073           continue;
1074         }
1075       }
1076 
1077       W.write<uint32_t>(it->Symbol->getIndex());
1078     }
1079 
1080     // FIXME: Check that offsets match computed ones.
1081 
1082     // Write the symbol table entries.
1083     for (auto *SymbolData :
1084          {&LocalSymbolData, &ExternalSymbolData, &UndefinedSymbolData})
1085       for (MachSymbolData &Entry : *SymbolData)
1086         writeNlist(Entry, Layout);
1087 
1088     // Write the string table.
1089     StringTable.write(W.OS);
1090   }
1091 
1092   return W.OS.tell() - StartOffset;
1093 }
1094 
1095 std::unique_ptr<MCObjectWriter>
1096 llvm::createMachObjectWriter(std::unique_ptr<MCMachObjectTargetWriter> MOTW,
1097                              raw_pwrite_stream &OS, bool IsLittleEndian) {
1098   return std::make_unique<MachObjectWriter>(std::move(MOTW), OS,
1099                                              IsLittleEndian);
1100 }
1101