MachONormalizedFileFromAtoms.cpp revision 309124 
1//===- lib/ReaderWriter/MachO/MachONormalizedFileFromAtoms.cpp ------------===//
2//
3//                             The LLVM Linker
4//
5// This file is distributed under the University of Illinois Open Source
6// License. See LICENSE.TXT for details.
7//
8//===----------------------------------------------------------------------===//
9
10///
11/// \file Converts from in-memory Atoms to in-memory normalized mach-o.
12///
13///                  +------------+
14///                  | normalized |
15///                  +------------+
16///                        ^
17///                        |
18///                        |
19///                    +-------+
20///                    | Atoms |
21///                    +-------+
22
23#include "MachONormalizedFile.h"
24#include "ArchHandler.h"
25#include "MachONormalizedFileBinaryUtils.h"
26#include "lld/Core/Error.h"
27#include "lld/Core/LLVM.h"
28#include "llvm/ADT/StringRef.h"
29#include "llvm/ADT/StringSwitch.h"
30#include "llvm/Support/Casting.h"
31#include "llvm/Support/Debug.h"
32#include "llvm/Support/ErrorHandling.h"
33#include "llvm/Support/Format.h"
34#include "llvm/Support/MachO.h"
35#include <map>
36#include <system_error>
37
38using llvm::StringRef;
39using llvm::isa;
40using namespace llvm::MachO;
41using namespace lld::mach_o::normalized;
42using namespace lld;
43
44namespace {
45
46struct AtomInfo {
47  const DefinedAtom  *atom;
48  uint64_t            offsetInSection;
49};
50
51struct SectionInfo {
52  SectionInfo(StringRef seg, StringRef sect, SectionType type,
53              const MachOLinkingContext &ctxt, uint32_t attr,
54              bool relocsToDefinedCanBeImplicit);
55
56  StringRef                 segmentName;
57  StringRef                 sectionName;
58  SectionType               type;
59  uint32_t                  attributes;
60  uint64_t                  address;
61  uint64_t                  size;
62  uint16_t                  alignment;
63
64  /// If this is set, the any relocs in this section which point to defined
65  /// addresses can be implicitly generated.  This is the case for the
66  /// __eh_frame section where references to the function can be implicit if the
67  /// function is defined.
68  bool                      relocsToDefinedCanBeImplicit;
69
70
71  std::vector<AtomInfo>     atomsAndOffsets;
72  uint32_t                  normalizedSectionIndex;
73  uint32_t                  finalSectionIndex;
74};
75
76SectionInfo::SectionInfo(StringRef sg, StringRef sct, SectionType t,
77                         const MachOLinkingContext &ctxt, uint32_t attrs,
78                         bool relocsToDefinedCanBeImplicit)
79 : segmentName(sg), sectionName(sct), type(t), attributes(attrs),
80                 address(0), size(0), alignment(1),
81                 relocsToDefinedCanBeImplicit(relocsToDefinedCanBeImplicit),
82                 normalizedSectionIndex(0), finalSectionIndex(0) {
83  uint16_t align = 1;
84  if (ctxt.sectionAligned(segmentName, sectionName, align)) {
85    alignment = align;
86  }
87}
88
89struct SegmentInfo {
90  SegmentInfo(StringRef name);
91
92  StringRef                  name;
93  uint64_t                   address;
94  uint64_t                   size;
95  uint32_t                   init_access;
96  uint32_t                   max_access;
97  std::vector<SectionInfo*>  sections;
98  uint32_t                   normalizedSegmentIndex;
99};
100
101SegmentInfo::SegmentInfo(StringRef n)
102 : name(n), address(0), size(0), init_access(0), max_access(0),
103   normalizedSegmentIndex(0) {
104}
105
106class Util {
107public:
108  Util(const MachOLinkingContext &ctxt)
109      : _ctx(ctxt), _archHandler(ctxt.archHandler()), _entryAtom(nullptr),
110        _hasTLVDescriptors(false), _subsectionsViaSymbols(true) {}
111  ~Util();
112
113  void      processDefinedAtoms(const lld::File &atomFile);
114  void      processAtomAttributes(const DefinedAtom *atom);
115  void      assignAtomToSection(const DefinedAtom *atom);
116  void      organizeSections();
117  void      assignAddressesToSections(const NormalizedFile &file);
118  uint32_t  fileFlags();
119  void      copySegmentInfo(NormalizedFile &file);
120  void      copySectionInfo(NormalizedFile &file);
121  void      updateSectionInfo(NormalizedFile &file);
122  void      buildAtomToAddressMap();
123  llvm::Error addSymbols(const lld::File &atomFile, NormalizedFile &file);
124  void      addIndirectSymbols(const lld::File &atomFile, NormalizedFile &file);
125  void      addRebaseAndBindingInfo(const lld::File &, NormalizedFile &file);
126  void      addExportInfo(const lld::File &, NormalizedFile &file);
127  void      addSectionRelocs(const lld::File &, NormalizedFile &file);
128  void      addFunctionStarts(const lld::File &, NormalizedFile &file);
129  void      buildDataInCodeArray(const lld::File &, NormalizedFile &file);
130  void      addDependentDylibs(const lld::File &, NormalizedFile &file);
131  void      copyEntryPointAddress(NormalizedFile &file);
132  void      copySectionContent(NormalizedFile &file);
133
134  bool allSourceFilesHaveMinVersions() const {
135    return _allSourceFilesHaveMinVersions;
136  }
137
138  uint32_t minVersion() const {
139    return _minVersion;
140  }
141
142  LoadCommandType minVersionCommandType() const {
143    return _minVersionCommandType;
144  }
145
146private:
147  typedef std::map<DefinedAtom::ContentType, SectionInfo*> TypeToSection;
148  typedef llvm::DenseMap<const Atom*, uint64_t> AtomToAddress;
149
150  struct DylibInfo { int ordinal; bool hasWeak; bool hasNonWeak; };
151  typedef llvm::StringMap<DylibInfo> DylibPathToInfo;
152
153  SectionInfo *sectionForAtom(const DefinedAtom*);
154  SectionInfo *getRelocatableSection(DefinedAtom::ContentType type);
155  SectionInfo *getFinalSection(DefinedAtom::ContentType type);
156  void         appendAtom(SectionInfo *sect, const DefinedAtom *atom);
157  SegmentInfo *segmentForName(StringRef segName);
158  void         layoutSectionsInSegment(SegmentInfo *seg, uint64_t &addr);
159  void         layoutSectionsInTextSegment(size_t, SegmentInfo *, uint64_t &);
160  void         copySectionContent(SectionInfo *si, ContentBytes &content);
161  uint16_t     descBits(const DefinedAtom* atom);
162  int          dylibOrdinal(const SharedLibraryAtom *sa);
163  void         segIndexForSection(const SectionInfo *sect,
164                             uint8_t &segmentIndex, uint64_t &segmentStartAddr);
165  const Atom  *targetOfLazyPointer(const DefinedAtom *lpAtom);
166  const Atom  *targetOfStub(const DefinedAtom *stubAtom);
167  llvm::Error getSymbolTableRegion(const DefinedAtom* atom,
168                                   bool &inGlobalsRegion,
169                                   SymbolScope &symbolScope);
170  void         appendSection(SectionInfo *si, NormalizedFile &file);
171  uint32_t     sectionIndexForAtom(const Atom *atom);
172
173  typedef llvm::DenseMap<const Atom*, uint32_t> AtomToIndex;
174  struct AtomAndIndex { const Atom *atom; uint32_t index; SymbolScope scope; };
175  struct AtomSorter {
176    bool operator()(const AtomAndIndex &left, const AtomAndIndex &right);
177  };
178  struct SegmentSorter {
179    bool operator()(const SegmentInfo *left, const SegmentInfo *right);
180    static unsigned weight(const SegmentInfo *);
181  };
182  struct TextSectionSorter {
183    bool operator()(const SectionInfo *left, const SectionInfo *right);
184    static unsigned weight(const SectionInfo *);
185  };
186
187  const MachOLinkingContext &_ctx;
188  mach_o::ArchHandler          &_archHandler;
189  llvm::BumpPtrAllocator        _allocator;
190  std::vector<SectionInfo*>     _sectionInfos;
191  std::vector<SegmentInfo*>     _segmentInfos;
192  TypeToSection                 _sectionMap;
193  std::vector<SectionInfo*>     _customSections;
194  AtomToAddress                 _atomToAddress;
195  DylibPathToInfo               _dylibInfo;
196  const DefinedAtom            *_entryAtom;
197  AtomToIndex                   _atomToSymbolIndex;
198  std::vector<const Atom *>     _machHeaderAliasAtoms;
199  bool                          _hasTLVDescriptors;
200  bool                          _subsectionsViaSymbols;
201  bool                          _allSourceFilesHaveMinVersions = true;
202  LoadCommandType               _minVersionCommandType = (LoadCommandType)0;
203  uint32_t                      _minVersion = 0;
204};
205
206Util::~Util() {
207  // The SectionInfo structs are BumpPtr allocated, but atomsAndOffsets needs
208  // to be deleted.
209  for (SectionInfo *si : _sectionInfos) {
210    // clear() destroys vector elements, but does not deallocate.
211    // Instead use swap() to deallocate vector buffer.
212    std::vector<AtomInfo> empty;
213    si->atomsAndOffsets.swap(empty);
214  }
215  // The SegmentInfo structs are BumpPtr allocated, but sections needs
216  // to be deleted.
217  for (SegmentInfo *sgi : _segmentInfos) {
218    std::vector<SectionInfo*> empty2;
219    sgi->sections.swap(empty2);
220  }
221}
222
223SectionInfo *Util::getRelocatableSection(DefinedAtom::ContentType type) {
224  StringRef segmentName;
225  StringRef sectionName;
226  SectionType sectionType;
227  SectionAttr sectionAttrs;
228  bool relocsToDefinedCanBeImplicit;
229
230  // Use same table used by when parsing .o files.
231  relocatableSectionInfoForContentType(type, segmentName, sectionName,
232                                       sectionType, sectionAttrs,
233                                       relocsToDefinedCanBeImplicit);
234  // If we already have a SectionInfo with this name, re-use it.
235  // This can happen if two ContentType map to the same mach-o section.
236  for (auto sect : _sectionMap) {
237    if (sect.second->sectionName.equals(sectionName) &&
238        sect.second->segmentName.equals(segmentName)) {
239      return sect.second;
240    }
241  }
242  // Otherwise allocate new SectionInfo object.
243  auto *sect = new (_allocator)
244      SectionInfo(segmentName, sectionName, sectionType, _ctx, sectionAttrs,
245                  relocsToDefinedCanBeImplicit);
246  _sectionInfos.push_back(sect);
247  _sectionMap[type] = sect;
248  return sect;
249}
250
251#define ENTRY(seg, sect, type, atomType) \
252  {seg, sect, type, DefinedAtom::atomType }
253
254struct MachOFinalSectionFromAtomType {
255  StringRef                 segmentName;
256  StringRef                 sectionName;
257  SectionType               sectionType;
258  DefinedAtom::ContentType  atomType;
259};
260
261const MachOFinalSectionFromAtomType sectsToAtomType[] = {
262  ENTRY("__TEXT", "__text",           S_REGULAR,          typeCode),
263  ENTRY("__TEXT", "__text",           S_REGULAR,          typeMachHeader),
264  ENTRY("__TEXT", "__cstring",        S_CSTRING_LITERALS, typeCString),
265  ENTRY("__TEXT", "__ustring",        S_REGULAR,          typeUTF16String),
266  ENTRY("__TEXT", "__const",          S_REGULAR,          typeConstant),
267  ENTRY("__TEXT", "__const",          S_4BYTE_LITERALS,   typeLiteral4),
268  ENTRY("__TEXT", "__const",          S_8BYTE_LITERALS,   typeLiteral8),
269  ENTRY("__TEXT", "__const",          S_16BYTE_LITERALS,  typeLiteral16),
270  ENTRY("__TEXT", "__stubs",          S_SYMBOL_STUBS,     typeStub),
271  ENTRY("__TEXT", "__stub_helper",    S_REGULAR,          typeStubHelper),
272  ENTRY("__TEXT", "__gcc_except_tab", S_REGULAR,          typeLSDA),
273  ENTRY("__TEXT", "__eh_frame",       S_COALESCED,        typeCFI),
274  ENTRY("__TEXT", "__unwind_info",    S_REGULAR,          typeProcessedUnwindInfo),
275  ENTRY("__DATA", "__data",           S_REGULAR,          typeData),
276  ENTRY("__DATA", "__const",          S_REGULAR,          typeConstData),
277  ENTRY("__DATA", "__cfstring",       S_REGULAR,          typeCFString),
278  ENTRY("__DATA", "__la_symbol_ptr",  S_LAZY_SYMBOL_POINTERS,
279                                                          typeLazyPointer),
280  ENTRY("__DATA", "__mod_init_func",  S_MOD_INIT_FUNC_POINTERS,
281                                                          typeInitializerPtr),
282  ENTRY("__DATA", "__mod_term_func",  S_MOD_TERM_FUNC_POINTERS,
283                                                          typeTerminatorPtr),
284  ENTRY("__DATA", "__got",            S_NON_LAZY_SYMBOL_POINTERS,
285                                                          typeGOT),
286  ENTRY("__DATA", "__nl_symbol_ptr",  S_NON_LAZY_SYMBOL_POINTERS,
287                                                          typeNonLazyPointer),
288  ENTRY("__DATA", "__thread_vars",    S_THREAD_LOCAL_VARIABLES,
289                                                          typeThunkTLV),
290  ENTRY("__DATA", "__thread_data",    S_THREAD_LOCAL_REGULAR,
291                                                          typeTLVInitialData),
292  ENTRY("__DATA", "__thread_ptrs",    S_THREAD_LOCAL_VARIABLE_POINTERS,
293                                                          typeTLVInitializerPtr),
294  ENTRY("__DATA", "__thread_bss",     S_THREAD_LOCAL_ZEROFILL,
295                                                         typeTLVInitialZeroFill),
296  ENTRY("__DATA", "__bss",            S_ZEROFILL,         typeZeroFill),
297  ENTRY("__DATA", "__interposing",    S_INTERPOSING,      typeInterposingTuples),
298};
299#undef ENTRY
300
301SectionInfo *Util::getFinalSection(DefinedAtom::ContentType atomType) {
302  for (auto &p : sectsToAtomType) {
303    if (p.atomType != atomType)
304      continue;
305    SectionAttr sectionAttrs = 0;
306    switch (atomType) {
307    case DefinedAtom::typeMachHeader:
308    case DefinedAtom::typeCode:
309    case DefinedAtom::typeStub:
310    case DefinedAtom::typeStubHelper:
311      sectionAttrs = S_ATTR_PURE_INSTRUCTIONS | S_ATTR_SOME_INSTRUCTIONS;
312      break;
313    case DefinedAtom::typeThunkTLV:
314      _hasTLVDescriptors = true;
315      break;
316    default:
317      break;
318    }
319    // If we already have a SectionInfo with this name, re-use it.
320    // This can happen if two ContentType map to the same mach-o section.
321    for (auto sect : _sectionMap) {
322      if (sect.second->sectionName.equals(p.sectionName) &&
323          sect.second->segmentName.equals(p.segmentName)) {
324        return sect.second;
325      }
326    }
327    // Otherwise allocate new SectionInfo object.
328    auto *sect = new (_allocator) SectionInfo(
329        p.segmentName, p.sectionName, p.sectionType, _ctx, sectionAttrs,
330        /* relocsToDefinedCanBeImplicit */ false);
331    _sectionInfos.push_back(sect);
332    _sectionMap[atomType] = sect;
333    return sect;
334  }
335  llvm_unreachable("content type not yet supported");
336}
337
338SectionInfo *Util::sectionForAtom(const DefinedAtom *atom) {
339  if (atom->sectionChoice() == DefinedAtom::sectionBasedOnContent) {
340    // Section for this atom is derived from content type.
341    DefinedAtom::ContentType type = atom->contentType();
342    auto pos = _sectionMap.find(type);
343    if ( pos != _sectionMap.end() )
344      return pos->second;
345    bool rMode = (_ctx.outputMachOType() == llvm::MachO::MH_OBJECT);
346    return rMode ? getRelocatableSection(type) : getFinalSection(type);
347  } else {
348    // This atom needs to be in a custom section.
349    StringRef customName = atom->customSectionName();
350    // Look to see if we have already allocated the needed custom section.
351    for(SectionInfo *sect : _customSections) {
352      const DefinedAtom *firstAtom = sect->atomsAndOffsets.front().atom;
353      if (firstAtom->customSectionName().equals(customName)) {
354        return sect;
355      }
356    }
357    // Not found, so need to create a new custom section.
358    size_t seperatorIndex = customName.find('/');
359    assert(seperatorIndex != StringRef::npos);
360    StringRef segName = customName.slice(0, seperatorIndex);
361    StringRef sectName = customName.drop_front(seperatorIndex + 1);
362    auto *sect =
363        new (_allocator) SectionInfo(segName, sectName, S_REGULAR, _ctx,
364                                     0, /* relocsToDefinedCanBeImplicit */ false);
365    _customSections.push_back(sect);
366    _sectionInfos.push_back(sect);
367    return sect;
368  }
369}
370
371void Util::appendAtom(SectionInfo *sect, const DefinedAtom *atom) {
372  // Figure out offset for atom in this section given alignment constraints.
373  uint64_t offset = sect->size;
374  DefinedAtom::Alignment atomAlign = atom->alignment();
375  uint64_t align = atomAlign.value;
376  uint64_t requiredModulus = atomAlign.modulus;
377  uint64_t currentModulus = (offset % align);
378  if ( currentModulus != requiredModulus ) {
379    if ( requiredModulus > currentModulus )
380      offset += requiredModulus-currentModulus;
381    else
382      offset += align+requiredModulus-currentModulus;
383  }
384  // Record max alignment of any atom in this section.
385  if (align > sect->alignment)
386    sect->alignment = atomAlign.value;
387  // Assign atom to this section with this offset.
388  AtomInfo ai = {atom, offset};
389  sect->atomsAndOffsets.push_back(ai);
390  // Update section size to include this atom.
391  sect->size = offset + atom->size();
392}
393
394void Util::processDefinedAtoms(const lld::File &atomFile) {
395  for (const DefinedAtom *atom : atomFile.defined()) {
396    processAtomAttributes(atom);
397    assignAtomToSection(atom);
398  }
399}
400
401void Util::processAtomAttributes(const DefinedAtom *atom) {
402  if (auto *machoFile = dyn_cast<mach_o::MachOFile>(&atom->file())) {
403    // If the file doesn't use subsections via symbols, then make sure we don't
404    // add that flag to the final output file if we have a relocatable file.
405    if (!machoFile->subsectionsViaSymbols())
406      _subsectionsViaSymbols = false;
407
408    // All the source files must have min versions for us to output an object
409    // file with a min version.
410    if (auto v = machoFile->minVersion())
411      _minVersion = std::max(_minVersion, v);
412    else
413      _allSourceFilesHaveMinVersions = false;
414
415    // If we don't have a platform load command, but one of the source files
416    // does, then take the one from the file.
417    if (!_minVersionCommandType)
418      if (auto v = machoFile->minVersionLoadCommandKind())
419        _minVersionCommandType = v;
420  }
421}
422
423void Util::assignAtomToSection(const DefinedAtom *atom) {
424  if (atom->contentType() == DefinedAtom::typeMachHeader) {
425    _machHeaderAliasAtoms.push_back(atom);
426    // Assign atom to this section with this offset.
427    AtomInfo ai = {atom, 0};
428    sectionForAtom(atom)->atomsAndOffsets.push_back(ai);
429  } else if (atom->contentType() == DefinedAtom::typeDSOHandle)
430    _machHeaderAliasAtoms.push_back(atom);
431  else
432    appendAtom(sectionForAtom(atom), atom);
433}
434
435SegmentInfo *Util::segmentForName(StringRef segName) {
436  for (SegmentInfo *si : _segmentInfos) {
437    if ( si->name.equals(segName) )
438      return si;
439  }
440  auto *info = new (_allocator) SegmentInfo(segName);
441
442  // Set the initial segment protection.
443  if (segName.equals("__TEXT"))
444    info->init_access = VM_PROT_READ | VM_PROT_EXECUTE;
445  else if (segName.equals("__PAGEZERO"))
446    info->init_access = 0;
447  else if (segName.equals("__LINKEDIT"))
448    info->init_access = VM_PROT_READ;
449  else {
450    // All others default to read-write
451    info->init_access = VM_PROT_READ | VM_PROT_WRITE;
452  }
453
454  // Set max segment protection
455  // Note, its overkill to use a switch statement here, but makes it so much
456  // easier to use switch coverage to catch new cases.
457  switch (_ctx.os()) {
458    case lld::MachOLinkingContext::OS::unknown:
459    case lld::MachOLinkingContext::OS::macOSX:
460    case lld::MachOLinkingContext::OS::iOS_simulator:
461      if (segName.equals("__PAGEZERO")) {
462        info->max_access = 0;
463        break;
464      }
465      // All others default to all
466      info->max_access = VM_PROT_READ | VM_PROT_WRITE | VM_PROT_EXECUTE;
467      break;
468    case lld::MachOLinkingContext::OS::iOS:
469      // iPhoneOS always uses same protection for max and initial
470      info->max_access = info->init_access;
471      break;
472  }
473  _segmentInfos.push_back(info);
474  return info;
475}
476
477unsigned Util::SegmentSorter::weight(const SegmentInfo *seg) {
478 return llvm::StringSwitch<unsigned>(seg->name)
479    .Case("__PAGEZERO",  1)
480    .Case("__TEXT",      2)
481    .Case("__DATA",      3)
482    .Default(100);
483}
484
485bool Util::SegmentSorter::operator()(const SegmentInfo *left,
486                                  const SegmentInfo *right) {
487  return (weight(left) < weight(right));
488}
489
490unsigned Util::TextSectionSorter::weight(const SectionInfo *sect) {
491 return llvm::StringSwitch<unsigned>(sect->sectionName)
492    .Case("__text",         1)
493    .Case("__stubs",        2)
494    .Case("__stub_helper",  3)
495    .Case("__const",        4)
496    .Case("__cstring",      5)
497    .Case("__unwind_info",  98)
498    .Case("__eh_frame",     99)
499    .Default(10);
500}
501
502bool Util::TextSectionSorter::operator()(const SectionInfo *left,
503                                         const SectionInfo *right) {
504  return (weight(left) < weight(right));
505}
506
507void Util::organizeSections() {
508  // NOTE!: Keep this in sync with assignAddressesToSections.
509  switch (_ctx.outputMachOType()) {
510    case llvm::MachO::MH_EXECUTE:
511      // Main executables, need a zero-page segment
512      segmentForName("__PAGEZERO");
513      // Fall into next case.
514    case llvm::MachO::MH_DYLIB:
515    case llvm::MachO::MH_BUNDLE:
516      // All dynamic code needs TEXT segment to hold the load commands.
517      segmentForName("__TEXT");
518      break;
519    default:
520      break;
521  }
522  segmentForName("__LINKEDIT");
523
524  // Group sections into segments.
525  for (SectionInfo *si : _sectionInfos) {
526    SegmentInfo *seg = segmentForName(si->segmentName);
527    seg->sections.push_back(si);
528  }
529  // Sort segments.
530  std::sort(_segmentInfos.begin(), _segmentInfos.end(), SegmentSorter());
531
532  // Sort sections within segments.
533  for (SegmentInfo *seg : _segmentInfos) {
534    if (seg->name.equals("__TEXT")) {
535      std::sort(seg->sections.begin(), seg->sections.end(),
536                TextSectionSorter());
537    }
538  }
539
540  // Record final section indexes.
541  uint32_t segmentIndex = 0;
542  uint32_t sectionIndex = 1;
543  for (SegmentInfo *seg : _segmentInfos) {
544    seg->normalizedSegmentIndex = segmentIndex++;
545    for (SectionInfo *sect : seg->sections)
546      sect->finalSectionIndex = sectionIndex++;
547  }
548}
549
550void Util::layoutSectionsInSegment(SegmentInfo *seg, uint64_t &addr) {
551  seg->address = addr;
552  for (SectionInfo *sect : seg->sections) {
553    sect->address = llvm::alignTo(addr, sect->alignment);
554    addr = sect->address + sect->size;
555  }
556  seg->size = llvm::alignTo(addr - seg->address, _ctx.pageSize());
557}
558
559// __TEXT segment lays out backwards so padding is at front after load commands.
560void Util::layoutSectionsInTextSegment(size_t hlcSize, SegmentInfo *seg,
561                                                               uint64_t &addr) {
562  seg->address = addr;
563  // Walks sections starting at end to calculate padding for start.
564  int64_t taddr = 0;
565  for (auto it = seg->sections.rbegin(); it != seg->sections.rend(); ++it) {
566    SectionInfo *sect = *it;
567    taddr -= sect->size;
568    taddr = taddr & (0 - sect->alignment);
569  }
570  int64_t padding = taddr - hlcSize;
571  while (padding < 0)
572    padding += _ctx.pageSize();
573  // Start assigning section address starting at padded offset.
574  addr += (padding + hlcSize);
575  for (SectionInfo *sect : seg->sections) {
576    sect->address = llvm::alignTo(addr, sect->alignment);
577    addr = sect->address + sect->size;
578  }
579  seg->size = llvm::alignTo(addr - seg->address, _ctx.pageSize());
580}
581
582void Util::assignAddressesToSections(const NormalizedFile &file) {
583  // NOTE!: Keep this in sync with organizeSections.
584  size_t hlcSize = headerAndLoadCommandsSize(file);
585  uint64_t address = 0;
586  for (SegmentInfo *seg : _segmentInfos) {
587    if (seg->name.equals("__PAGEZERO")) {
588      seg->size = _ctx.pageZeroSize();
589      address += seg->size;
590    }
591    else if (seg->name.equals("__TEXT")) {
592      // _ctx.baseAddress()  == 0 implies it was either unspecified or
593      // pageZeroSize is also 0. In either case resetting address is safe.
594      address = _ctx.baseAddress() ? _ctx.baseAddress() : address;
595      layoutSectionsInTextSegment(hlcSize, seg, address);
596    } else
597      layoutSectionsInSegment(seg, address);
598
599    address = llvm::alignTo(address, _ctx.pageSize());
600  }
601  DEBUG_WITH_TYPE("WriterMachO-norm",
602    llvm::dbgs() << "assignAddressesToSections()\n";
603    for (SegmentInfo *sgi : _segmentInfos) {
604      llvm::dbgs()  << "   address=" << llvm::format("0x%08llX", sgi->address)
605                    << ", size="  << llvm::format("0x%08llX", sgi->size)
606                    << ", segment-name='" << sgi->name
607                    << "'\n";
608      for (SectionInfo *si : sgi->sections) {
609        llvm::dbgs()<< "      addr="  << llvm::format("0x%08llX", si->address)
610                    << ", size="  << llvm::format("0x%08llX", si->size)
611                    << ", section-name='" << si->sectionName
612                    << "\n";
613      }
614    }
615  );
616}
617
618void Util::copySegmentInfo(NormalizedFile &file) {
619  for (SegmentInfo *sgi : _segmentInfos) {
620    Segment seg;
621    seg.name    = sgi->name;
622    seg.address = sgi->address;
623    seg.size    = sgi->size;
624    seg.init_access  = sgi->init_access;
625    seg.max_access  = sgi->max_access;
626    file.segments.push_back(seg);
627  }
628}
629
630void Util::appendSection(SectionInfo *si, NormalizedFile &file) {
631   // Add new empty section to end of file.sections.
632  Section temp;
633  file.sections.push_back(std::move(temp));
634  Section* normSect = &file.sections.back();
635  // Copy fields to normalized section.
636  normSect->segmentName   = si->segmentName;
637  normSect->sectionName   = si->sectionName;
638  normSect->type          = si->type;
639  normSect->attributes    = si->attributes;
640  normSect->address       = si->address;
641  normSect->alignment     = si->alignment;
642  // Record where normalized section is.
643  si->normalizedSectionIndex = file.sections.size()-1;
644}
645
646void Util::copySectionContent(NormalizedFile &file) {
647  const bool r = (_ctx.outputMachOType() == llvm::MachO::MH_OBJECT);
648
649  // Utility function for ArchHandler to find address of atom in output file.
650  auto addrForAtom = [&] (const Atom &atom) -> uint64_t {
651    auto pos = _atomToAddress.find(&atom);
652    assert(pos != _atomToAddress.end());
653    return pos->second;
654  };
655
656  auto sectionAddrForAtom = [&] (const Atom &atom) -> uint64_t {
657    for (const SectionInfo *sectInfo : _sectionInfos)
658      for (const AtomInfo &atomInfo : sectInfo->atomsAndOffsets)
659        if (atomInfo.atom == &atom)
660          return sectInfo->address;
661    llvm_unreachable("atom not assigned to section");
662  };
663
664  for (SectionInfo *si : _sectionInfos) {
665    Section *normSect = &file.sections[si->normalizedSectionIndex];
666    if (isZeroFillSection(si->type)) {
667      const uint8_t *empty = nullptr;
668      normSect->content = llvm::makeArrayRef(empty, si->size);
669      continue;
670    }
671    // Copy content from atoms to content buffer for section.
672    llvm::MutableArrayRef<uint8_t> sectionContent;
673    if (si->size) {
674      uint8_t *sectContent = file.ownedAllocations.Allocate<uint8_t>(si->size);
675      sectionContent = llvm::MutableArrayRef<uint8_t>(sectContent, si->size);
676      normSect->content = sectionContent;
677    }
678    for (AtomInfo &ai : si->atomsAndOffsets) {
679      if (!ai.atom->size()) {
680        assert(ai.atom->begin() == ai.atom->end() &&
681               "Cannot have references without content");
682        continue;
683      }
684      auto atomContent = sectionContent.slice(ai.offsetInSection,
685                                              ai.atom->size());
686      _archHandler.generateAtomContent(*ai.atom, r, addrForAtom,
687                                       sectionAddrForAtom, _ctx.baseAddress(),
688                                       atomContent);
689    }
690  }
691}
692
693void Util::copySectionInfo(NormalizedFile &file) {
694  file.sections.reserve(_sectionInfos.size());
695  // Write sections grouped by segment.
696  for (SegmentInfo *sgi : _segmentInfos) {
697    for (SectionInfo *si : sgi->sections) {
698      appendSection(si, file);
699    }
700  }
701}
702
703void Util::updateSectionInfo(NormalizedFile &file) {
704  file.sections.reserve(_sectionInfos.size());
705  // sections grouped by segment.
706  for (SegmentInfo *sgi : _segmentInfos) {
707    Segment *normSeg = &file.segments[sgi->normalizedSegmentIndex];
708    normSeg->address = sgi->address;
709    normSeg->size = sgi->size;
710    for (SectionInfo *si : sgi->sections) {
711      Section *normSect = &file.sections[si->normalizedSectionIndex];
712      normSect->address = si->address;
713    }
714  }
715}
716
717void Util::copyEntryPointAddress(NormalizedFile &nFile) {
718  if (!_entryAtom) {
719    nFile.entryAddress = 0;
720    return;
721  }
722
723  if (_ctx.outputTypeHasEntry()) {
724    if (_archHandler.isThumbFunction(*_entryAtom))
725      nFile.entryAddress = (_atomToAddress[_entryAtom] | 1);
726    else
727      nFile.entryAddress = _atomToAddress[_entryAtom];
728  }
729}
730
731void Util::buildAtomToAddressMap() {
732  DEBUG_WITH_TYPE("WriterMachO-address", llvm::dbgs()
733                   << "assign atom addresses:\n");
734  const bool lookForEntry = _ctx.outputTypeHasEntry();
735  for (SectionInfo *sect : _sectionInfos) {
736    for (const AtomInfo &info : sect->atomsAndOffsets) {
737      _atomToAddress[info.atom] = sect->address + info.offsetInSection;
738      if (lookForEntry && (info.atom->contentType() == DefinedAtom::typeCode) &&
739          (info.atom->size() != 0) &&
740          info.atom->name() == _ctx.entrySymbolName()) {
741        _entryAtom = info.atom;
742      }
743      DEBUG_WITH_TYPE("WriterMachO-address", llvm::dbgs()
744                      << "   address="
745                      << llvm::format("0x%016X", _atomToAddress[info.atom])
746                      << llvm::format("    0x%09lX", info.atom)
747                      << ", file=#"
748                      << info.atom->file().ordinal()
749                      << ", atom=#"
750                      << info.atom->ordinal()
751                      << ", name="
752                      << info.atom->name()
753                      << ", type="
754                      << info.atom->contentType()
755                      << "\n");
756    }
757  }
758  DEBUG_WITH_TYPE("WriterMachO-address", llvm::dbgs()
759                  << "assign header alias atom addresses:\n");
760  for (const Atom *atom : _machHeaderAliasAtoms) {
761    _atomToAddress[atom] = _ctx.baseAddress();
762#ifndef NDEBUG
763    if (auto *definedAtom = dyn_cast<DefinedAtom>(atom)) {
764      DEBUG_WITH_TYPE("WriterMachO-address", llvm::dbgs()
765                      << "   address="
766                      << llvm::format("0x%016X", _atomToAddress[atom])
767                      << llvm::format("    0x%09lX", atom)
768                      << ", file=#"
769                      << definedAtom->file().ordinal()
770                      << ", atom=#"
771                      << definedAtom->ordinal()
772                      << ", name="
773                      << definedAtom->name()
774                      << ", type="
775                      << definedAtom->contentType()
776                      << "\n");
777    } else {
778      DEBUG_WITH_TYPE("WriterMachO-address", llvm::dbgs()
779                      << "   address="
780                      << llvm::format("0x%016X", _atomToAddress[atom])
781                      << " atom=" << atom
782                      << " name=" << atom->name() << "\n");
783    }
784#endif
785  }
786}
787
788uint16_t Util::descBits(const DefinedAtom* atom) {
789  uint16_t desc = 0;
790  switch (atom->merge()) {
791  case lld::DefinedAtom::mergeNo:
792  case lld::DefinedAtom::mergeAsTentative:
793    break;
794  case lld::DefinedAtom::mergeAsWeak:
795  case lld::DefinedAtom::mergeAsWeakAndAddressUsed:
796    desc |= N_WEAK_DEF;
797    break;
798  case lld::DefinedAtom::mergeSameNameAndSize:
799  case lld::DefinedAtom::mergeByLargestSection:
800  case lld::DefinedAtom::mergeByContent:
801    llvm_unreachable("Unsupported DefinedAtom::merge()");
802    break;
803  }
804  if (atom->contentType() == lld::DefinedAtom::typeResolver)
805    desc |= N_SYMBOL_RESOLVER;
806  if (atom->contentType() == lld::DefinedAtom::typeMachHeader)
807    desc |= REFERENCED_DYNAMICALLY;
808  if (_archHandler.isThumbFunction(*atom))
809    desc |= N_ARM_THUMB_DEF;
810  if (atom->deadStrip() == DefinedAtom::deadStripNever) {
811    if ((atom->contentType() != DefinedAtom::typeInitializerPtr)
812     && (atom->contentType() != DefinedAtom::typeTerminatorPtr))
813    desc |= N_NO_DEAD_STRIP;
814  }
815  return desc;
816}
817
818bool Util::AtomSorter::operator()(const AtomAndIndex &left,
819                                  const AtomAndIndex &right) {
820  return (left.atom->name().compare(right.atom->name()) < 0);
821}
822
823llvm::Error Util::getSymbolTableRegion(const DefinedAtom* atom,
824                                       bool &inGlobalsRegion,
825                                       SymbolScope &scope) {
826  bool rMode = (_ctx.outputMachOType() == llvm::MachO::MH_OBJECT);
827  switch (atom->scope()) {
828  case Atom::scopeTranslationUnit:
829    scope = 0;
830    inGlobalsRegion = false;
831    return llvm::Error();
832  case Atom::scopeLinkageUnit:
833    if ((_ctx.exportMode() == MachOLinkingContext::ExportMode::whiteList) &&
834        _ctx.exportSymbolNamed(atom->name())) {
835      return llvm::make_error<GenericError>(
836                          Twine("cannot export hidden symbol ") + atom->name());
837    }
838    if (rMode) {
839      if (_ctx.keepPrivateExterns()) {
840        // -keep_private_externs means keep in globals region as N_PEXT.
841        scope = N_PEXT | N_EXT;
842        inGlobalsRegion = true;
843        return llvm::Error();
844      }
845    }
846    // scopeLinkageUnit symbols are no longer global once linked.
847    scope = N_PEXT;
848    inGlobalsRegion = false;
849    return llvm::Error();
850  case Atom::scopeGlobal:
851    if (_ctx.exportRestrictMode()) {
852      if (_ctx.exportSymbolNamed(atom->name())) {
853        scope = N_EXT;
854        inGlobalsRegion = true;
855        return llvm::Error();
856      } else {
857        scope = N_PEXT;
858        inGlobalsRegion = false;
859        return llvm::Error();
860      }
861    } else {
862      scope = N_EXT;
863      inGlobalsRegion = true;
864      return llvm::Error();
865    }
866    break;
867  }
868  llvm_unreachable("atom->scope() unknown enum value");
869}
870
871llvm::Error Util::addSymbols(const lld::File &atomFile,
872                             NormalizedFile &file) {
873  bool rMode = (_ctx.outputMachOType() == llvm::MachO::MH_OBJECT);
874  // Mach-O symbol table has three regions: locals, globals, undefs.
875
876  // Add all local (non-global) symbols in address order
877  std::vector<AtomAndIndex> globals;
878  globals.reserve(512);
879  for (SectionInfo *sect : _sectionInfos) {
880    for (const AtomInfo &info : sect->atomsAndOffsets) {
881      const DefinedAtom *atom = info.atom;
882      if (!atom->name().empty()) {
883        SymbolScope symbolScope;
884        bool inGlobalsRegion;
885        if (auto ec = getSymbolTableRegion(atom, inGlobalsRegion, symbolScope)){
886          return ec;
887        }
888        if (inGlobalsRegion) {
889          AtomAndIndex ai = { atom, sect->finalSectionIndex, symbolScope };
890          globals.push_back(ai);
891        } else {
892          Symbol sym;
893          sym.name  = atom->name();
894          sym.type  = N_SECT;
895          sym.scope = symbolScope;
896          sym.sect  = sect->finalSectionIndex;
897          sym.desc  = descBits(atom);
898          sym.value = _atomToAddress[atom];
899          _atomToSymbolIndex[atom] = file.localSymbols.size();
900          file.localSymbols.push_back(sym);
901        }
902      } else if (rMode && _archHandler.needsLocalSymbolInRelocatableFile(atom)){
903        // Create 'Lxxx' labels for anonymous atoms if archHandler says so.
904        static unsigned tempNum = 1;
905        char tmpName[16];
906        sprintf(tmpName, "L%04u", tempNum++);
907        StringRef tempRef(tmpName);
908        Symbol sym;
909        sym.name  = tempRef.copy(file.ownedAllocations);
910        sym.type  = N_SECT;
911        sym.scope = 0;
912        sym.sect  = sect->finalSectionIndex;
913        sym.desc  = 0;
914        sym.value = _atomToAddress[atom];
915        _atomToSymbolIndex[atom] = file.localSymbols.size();
916        file.localSymbols.push_back(sym);
917      }
918    }
919  }
920
921  // Sort global symbol alphabetically, then add to symbol table.
922  std::sort(globals.begin(), globals.end(), AtomSorter());
923  const uint32_t globalStartIndex = file.localSymbols.size();
924  for (AtomAndIndex &ai : globals) {
925    Symbol sym;
926    sym.name  = ai.atom->name();
927    sym.type  = N_SECT;
928    sym.scope = ai.scope;
929    sym.sect  = ai.index;
930    sym.desc  = descBits(static_cast<const DefinedAtom*>(ai.atom));
931    sym.value = _atomToAddress[ai.atom];
932    _atomToSymbolIndex[ai.atom] = globalStartIndex + file.globalSymbols.size();
933    file.globalSymbols.push_back(sym);
934  }
935
936  // Sort undefined symbol alphabetically, then add to symbol table.
937  std::vector<AtomAndIndex> undefs;
938  undefs.reserve(128);
939  for (const UndefinedAtom *atom : atomFile.undefined()) {
940    AtomAndIndex ai = { atom, 0, N_EXT };
941    undefs.push_back(ai);
942  }
943  for (const SharedLibraryAtom *atom : atomFile.sharedLibrary()) {
944    AtomAndIndex ai = { atom, 0, N_EXT };
945    undefs.push_back(ai);
946  }
947  std::sort(undefs.begin(), undefs.end(), AtomSorter());
948  const uint32_t start = file.globalSymbols.size() + file.localSymbols.size();
949  for (AtomAndIndex &ai : undefs) {
950    Symbol sym;
951    uint16_t desc = 0;
952    if (!rMode) {
953      uint8_t ordinal = 0;
954      if (!_ctx.useFlatNamespace())
955        ordinal = dylibOrdinal(dyn_cast<SharedLibraryAtom>(ai.atom));
956      llvm::MachO::SET_LIBRARY_ORDINAL(desc, ordinal);
957    }
958    sym.name  = ai.atom->name();
959    sym.type  = N_UNDF;
960    sym.scope = ai.scope;
961    sym.sect  = 0;
962    sym.desc  = desc;
963    sym.value = 0;
964    _atomToSymbolIndex[ai.atom] = file.undefinedSymbols.size() + start;
965    file.undefinedSymbols.push_back(sym);
966  }
967
968  return llvm::Error();
969}
970
971const Atom *Util::targetOfLazyPointer(const DefinedAtom *lpAtom) {
972  for (const Reference *ref : *lpAtom) {
973    if (_archHandler.isLazyPointer(*ref)) {
974      return ref->target();
975    }
976  }
977  return nullptr;
978}
979
980const Atom *Util::targetOfStub(const DefinedAtom *stubAtom) {
981  for (const Reference *ref : *stubAtom) {
982    if (const Atom *ta = ref->target()) {
983      if (const DefinedAtom *lpAtom = dyn_cast<DefinedAtom>(ta)) {
984        const Atom *target = targetOfLazyPointer(lpAtom);
985        if (target)
986          return target;
987      }
988    }
989  }
990  return nullptr;
991}
992
993void Util::addIndirectSymbols(const lld::File &atomFile, NormalizedFile &file) {
994  for (SectionInfo *si : _sectionInfos) {
995    Section &normSect = file.sections[si->normalizedSectionIndex];
996    switch (si->type) {
997    case llvm::MachO::S_NON_LAZY_SYMBOL_POINTERS:
998      for (const AtomInfo &info : si->atomsAndOffsets) {
999        bool foundTarget = false;
1000        for (const Reference *ref : *info.atom) {
1001          const Atom *target = ref->target();
1002          if (target) {
1003            if (isa<const SharedLibraryAtom>(target)) {
1004              uint32_t index = _atomToSymbolIndex[target];
1005              normSect.indirectSymbols.push_back(index);
1006              foundTarget = true;
1007            } else {
1008              normSect.indirectSymbols.push_back(
1009                                            llvm::MachO::INDIRECT_SYMBOL_LOCAL);
1010            }
1011          }
1012        }
1013        if (!foundTarget) {
1014          normSect.indirectSymbols.push_back(
1015                                             llvm::MachO::INDIRECT_SYMBOL_ABS);
1016        }
1017      }
1018      break;
1019    case llvm::MachO::S_LAZY_SYMBOL_POINTERS:
1020      for (const AtomInfo &info : si->atomsAndOffsets) {
1021        const Atom *target = targetOfLazyPointer(info.atom);
1022        if (target) {
1023          uint32_t index = _atomToSymbolIndex[target];
1024          normSect.indirectSymbols.push_back(index);
1025        }
1026      }
1027      break;
1028    case llvm::MachO::S_SYMBOL_STUBS:
1029      for (const AtomInfo &info : si->atomsAndOffsets) {
1030        const Atom *target = targetOfStub(info.atom);
1031        if (target) {
1032          uint32_t index = _atomToSymbolIndex[target];
1033          normSect.indirectSymbols.push_back(index);
1034        }
1035      }
1036      break;
1037    default:
1038      break;
1039    }
1040  }
1041}
1042
1043void Util::addDependentDylibs(const lld::File &atomFile,NormalizedFile &nFile) {
1044  // Scan all imported symbols and build up list of dylibs they are from.
1045  int ordinal = 1;
1046  for (const SharedLibraryAtom *slAtom : atomFile.sharedLibrary()) {
1047    StringRef loadPath = slAtom->loadName();
1048    DylibPathToInfo::iterator pos = _dylibInfo.find(loadPath);
1049    if (pos == _dylibInfo.end()) {
1050      DylibInfo info;
1051      bool flatNamespaceAtom = &slAtom->file() == _ctx.flatNamespaceFile();
1052
1053      // If we're in -flat_namespace mode (or this atom came from the flat
1054      // namespace file under -undefined dynamic_lookup) then use the flat
1055      // lookup ordinal.
1056      if (flatNamespaceAtom || _ctx.useFlatNamespace())
1057        info.ordinal = BIND_SPECIAL_DYLIB_FLAT_LOOKUP;
1058      else
1059        info.ordinal = ordinal++;
1060      info.hasWeak = slAtom->canBeNullAtRuntime();
1061      info.hasNonWeak = !info.hasWeak;
1062      _dylibInfo[loadPath] = info;
1063
1064      // Unless this was a flat_namespace atom, record the source dylib.
1065      if (!flatNamespaceAtom) {
1066        DependentDylib depInfo;
1067        depInfo.path = loadPath;
1068        depInfo.kind = llvm::MachO::LC_LOAD_DYLIB;
1069        depInfo.currentVersion = _ctx.dylibCurrentVersion(loadPath);
1070        depInfo.compatVersion = _ctx.dylibCompatVersion(loadPath);
1071        nFile.dependentDylibs.push_back(depInfo);
1072      }
1073    } else {
1074      if ( slAtom->canBeNullAtRuntime() )
1075        pos->second.hasWeak = true;
1076      else
1077        pos->second.hasNonWeak = true;
1078    }
1079  }
1080  // Automatically weak link dylib in which all symbols are weak (canBeNull).
1081  for (DependentDylib &dep : nFile.dependentDylibs) {
1082    DylibInfo &info = _dylibInfo[dep.path];
1083    if (info.hasWeak && !info.hasNonWeak)
1084      dep.kind = llvm::MachO::LC_LOAD_WEAK_DYLIB;
1085    else if (_ctx.isUpwardDylib(dep.path))
1086      dep.kind = llvm::MachO::LC_LOAD_UPWARD_DYLIB;
1087  }
1088}
1089
1090int Util::dylibOrdinal(const SharedLibraryAtom *sa) {
1091  return _dylibInfo[sa->loadName()].ordinal;
1092}
1093
1094void Util::segIndexForSection(const SectionInfo *sect, uint8_t &segmentIndex,
1095                                                  uint64_t &segmentStartAddr) {
1096  segmentIndex = 0;
1097  for (const SegmentInfo *seg : _segmentInfos) {
1098    if ((seg->address <= sect->address)
1099      && (seg->address+seg->size >= sect->address+sect->size)) {
1100      segmentStartAddr = seg->address;
1101      return;
1102    }
1103    ++segmentIndex;
1104  }
1105  llvm_unreachable("section not in any segment");
1106}
1107
1108uint32_t Util::sectionIndexForAtom(const Atom *atom) {
1109  uint64_t address = _atomToAddress[atom];
1110  for (const SectionInfo *si : _sectionInfos) {
1111    if ((si->address <= address) && (address < si->address+si->size))
1112      return si->finalSectionIndex;
1113  }
1114  llvm_unreachable("atom not in any section");
1115}
1116
1117void Util::addSectionRelocs(const lld::File &, NormalizedFile &file) {
1118  if (_ctx.outputMachOType() != llvm::MachO::MH_OBJECT)
1119    return;
1120
1121  // Utility function for ArchHandler to find symbol index for an atom.
1122  auto symIndexForAtom = [&] (const Atom &atom) -> uint32_t {
1123    auto pos = _atomToSymbolIndex.find(&atom);
1124    assert(pos != _atomToSymbolIndex.end());
1125    return pos->second;
1126  };
1127
1128  // Utility function for ArchHandler to find section index for an atom.
1129  auto sectIndexForAtom = [&] (const Atom &atom) -> uint32_t {
1130    return sectionIndexForAtom(&atom);
1131  };
1132
1133  // Utility function for ArchHandler to find address of atom in output file.
1134  auto addressForAtom = [&] (const Atom &atom) -> uint64_t {
1135    auto pos = _atomToAddress.find(&atom);
1136    assert(pos != _atomToAddress.end());
1137    return pos->second;
1138  };
1139
1140  for (SectionInfo *si : _sectionInfos) {
1141    Section &normSect = file.sections[si->normalizedSectionIndex];
1142    for (const AtomInfo &info : si->atomsAndOffsets) {
1143      const DefinedAtom *atom = info.atom;
1144      for (const Reference *ref : *atom) {
1145        // Skip emitting relocs for sections which are always able to be
1146        // implicitly regenerated and where the relocation targets an address
1147        // which is defined.
1148        if (si->relocsToDefinedCanBeImplicit && isa<DefinedAtom>(ref->target()))
1149          continue;
1150        _archHandler.appendSectionRelocations(*atom, info.offsetInSection, *ref,
1151                                              symIndexForAtom,
1152                                              sectIndexForAtom,
1153                                              addressForAtom,
1154                                              normSect.relocations);
1155      }
1156    }
1157  }
1158}
1159
1160void Util::addFunctionStarts(const lld::File &, NormalizedFile &file) {
1161  if (!_ctx.generateFunctionStartsLoadCommand())
1162    return;
1163  file.functionStarts.reserve(8192);
1164  // Delta compress function starts, starting with the mach header symbol.
1165  const uint64_t badAddress = ~0ULL;
1166  uint64_t addr = badAddress;
1167  for (SectionInfo *si : _sectionInfos) {
1168    for (const AtomInfo &info : si->atomsAndOffsets) {
1169      auto type = info.atom->contentType();
1170      if (type == DefinedAtom::typeMachHeader) {
1171        addr = _atomToAddress[info.atom];
1172        continue;
1173      }
1174      if (type != DefinedAtom::typeCode)
1175        continue;
1176      assert(addr != badAddress && "Missing mach header symbol");
1177      // Skip atoms which have 0 size.  This is so that LC_FUNCTION_STARTS
1178      // can't spill in to the next section.
1179      if (!info.atom->size())
1180        continue;
1181      uint64_t nextAddr = _atomToAddress[info.atom];
1182      if (_archHandler.isThumbFunction(*info.atom))
1183        nextAddr |= 1;
1184      uint64_t delta = nextAddr - addr;
1185      if (delta) {
1186        ByteBuffer buffer;
1187        buffer.append_uleb128(delta);
1188        file.functionStarts.insert(file.functionStarts.end(), buffer.bytes(),
1189                                   buffer.bytes() + buffer.size());
1190      }
1191      addr = nextAddr;
1192    }
1193  }
1194
1195  // Null terminate, and pad to pointer size for this arch.
1196  file.functionStarts.push_back(0);
1197
1198  auto size = file.functionStarts.size();
1199  for (unsigned i = size, e = llvm::alignTo(size, _ctx.is64Bit() ? 8 : 4);
1200       i != e; ++i)
1201    file.functionStarts.push_back(0);
1202}
1203
1204void Util::buildDataInCodeArray(const lld::File &, NormalizedFile &file) {
1205  if (!_ctx.generateDataInCodeLoadCommand())
1206    return;
1207  for (SectionInfo *si : _sectionInfos) {
1208    for (const AtomInfo &info : si->atomsAndOffsets) {
1209      // Atoms that contain data-in-code have "transition" references
1210      // which mark a point where the embedded data starts of ends.
1211      // This needs to be converted to the mach-o format which is an array
1212      // of data-in-code ranges.
1213      uint32_t startOffset = 0;
1214      DataRegionType mode = DataRegionType(0);
1215      for (const Reference *ref : *info.atom) {
1216        if (ref->kindNamespace() != Reference::KindNamespace::mach_o)
1217          continue;
1218        if (_archHandler.isDataInCodeTransition(ref->kindValue())) {
1219          DataRegionType nextMode = (DataRegionType)ref->addend();
1220          if (mode != nextMode) {
1221            if (mode != 0) {
1222              // Found end data range, so make range entry.
1223              DataInCode entry;
1224              entry.offset = si->address + info.offsetInSection + startOffset;
1225              entry.length = ref->offsetInAtom() - startOffset;
1226              entry.kind   = mode;
1227              file.dataInCode.push_back(entry);
1228            }
1229          }
1230          mode = nextMode;
1231          startOffset = ref->offsetInAtom();
1232        }
1233      }
1234      if (mode != 0) {
1235        // Function ends with data (no end transition).
1236        DataInCode entry;
1237        entry.offset = si->address + info.offsetInSection + startOffset;
1238        entry.length = info.atom->size() - startOffset;
1239        entry.kind   = mode;
1240        file.dataInCode.push_back(entry);
1241      }
1242    }
1243  }
1244}
1245
1246void Util::addRebaseAndBindingInfo(const lld::File &atomFile,
1247                                                        NormalizedFile &nFile) {
1248  if (_ctx.outputMachOType() == llvm::MachO::MH_OBJECT)
1249    return;
1250
1251  uint8_t segmentIndex;
1252  uint64_t segmentStartAddr;
1253  for (SectionInfo *sect : _sectionInfos) {
1254    segIndexForSection(sect, segmentIndex, segmentStartAddr);
1255    for (const AtomInfo &info : sect->atomsAndOffsets) {
1256      const DefinedAtom *atom = info.atom;
1257      for (const Reference *ref : *atom) {
1258        uint64_t segmentOffset = _atomToAddress[atom] + ref->offsetInAtom()
1259                                - segmentStartAddr;
1260        const Atom* targ = ref->target();
1261        if (_archHandler.isPointer(*ref)) {
1262          // A pointer to a DefinedAtom requires rebasing.
1263          if (isa<DefinedAtom>(targ)) {
1264            RebaseLocation rebase;
1265            rebase.segIndex = segmentIndex;
1266            rebase.segOffset = segmentOffset;
1267            rebase.kind = llvm::MachO::REBASE_TYPE_POINTER;
1268            nFile.rebasingInfo.push_back(rebase);
1269          }
1270          // A pointer to an SharedLibraryAtom requires binding.
1271          if (const SharedLibraryAtom *sa = dyn_cast<SharedLibraryAtom>(targ)) {
1272            BindLocation bind;
1273            bind.segIndex = segmentIndex;
1274            bind.segOffset = segmentOffset;
1275            bind.kind = llvm::MachO::BIND_TYPE_POINTER;
1276            bind.canBeNull = sa->canBeNullAtRuntime();
1277            bind.ordinal = dylibOrdinal(sa);
1278            bind.symbolName = targ->name();
1279            bind.addend = ref->addend();
1280            nFile.bindingInfo.push_back(bind);
1281          }
1282        }
1283        else if (_archHandler.isLazyPointer(*ref)) {
1284          BindLocation bind;
1285          if (const SharedLibraryAtom *sa = dyn_cast<SharedLibraryAtom>(targ)) {
1286            bind.ordinal = dylibOrdinal(sa);
1287          } else {
1288            bind.ordinal = llvm::MachO::BIND_SPECIAL_DYLIB_SELF;
1289          }
1290          bind.segIndex = segmentIndex;
1291          bind.segOffset = segmentOffset;
1292          bind.kind = llvm::MachO::BIND_TYPE_POINTER;
1293          bind.canBeNull = false; //sa->canBeNullAtRuntime();
1294          bind.symbolName = targ->name();
1295          bind.addend = ref->addend();
1296          nFile.lazyBindingInfo.push_back(bind);
1297        }
1298      }
1299    }
1300  }
1301}
1302
1303void Util::addExportInfo(const lld::File &atomFile, NormalizedFile &nFile) {
1304  if (_ctx.outputMachOType() == llvm::MachO::MH_OBJECT)
1305    return;
1306
1307  for (SectionInfo *sect : _sectionInfos) {
1308    for (const AtomInfo &info : sect->atomsAndOffsets) {
1309      const DefinedAtom *atom = info.atom;
1310      if (atom->scope() != Atom::scopeGlobal)
1311        continue;
1312      if (_ctx.exportRestrictMode()) {
1313        if (!_ctx.exportSymbolNamed(atom->name()))
1314          continue;
1315      }
1316      Export exprt;
1317      exprt.name = atom->name();
1318      exprt.offset = _atomToAddress[atom] - _ctx.baseAddress();
1319      exprt.kind = EXPORT_SYMBOL_FLAGS_KIND_REGULAR;
1320      if (atom->merge() == DefinedAtom::mergeAsWeak)
1321        exprt.flags = EXPORT_SYMBOL_FLAGS_WEAK_DEFINITION;
1322      else
1323        exprt.flags = 0;
1324      exprt.otherOffset = 0;
1325      exprt.otherName = StringRef();
1326      nFile.exportInfo.push_back(exprt);
1327    }
1328  }
1329}
1330
1331uint32_t Util::fileFlags() {
1332  // FIXME: these need to determined at runtime.
1333  if (_ctx.outputMachOType() == MH_OBJECT) {
1334    return _subsectionsViaSymbols ? MH_SUBSECTIONS_VIA_SYMBOLS : 0;
1335  } else {
1336    uint32_t flags = MH_DYLDLINK;
1337    if (!_ctx.useFlatNamespace())
1338        flags |= MH_TWOLEVEL | MH_NOUNDEFS;
1339    if ((_ctx.outputMachOType() == MH_EXECUTE) && _ctx.PIE())
1340      flags |= MH_PIE;
1341    if (_hasTLVDescriptors)
1342      flags |= (MH_PIE | MH_HAS_TLV_DESCRIPTORS);
1343    return flags;
1344  }
1345}
1346
1347} // end anonymous namespace
1348
1349namespace lld {
1350namespace mach_o {
1351namespace normalized {
1352
1353/// Convert a set of Atoms into a normalized mach-o file.
1354llvm::Expected<std::unique_ptr<NormalizedFile>>
1355normalizedFromAtoms(const lld::File &atomFile,
1356                                           const MachOLinkingContext &context) {
1357  // The util object buffers info until the normalized file can be made.
1358  Util util(context);
1359  util.processDefinedAtoms(atomFile);
1360  util.organizeSections();
1361
1362  std::unique_ptr<NormalizedFile> f(new NormalizedFile());
1363  NormalizedFile &normFile = *f.get();
1364  normFile.arch = context.arch();
1365  normFile.fileType = context.outputMachOType();
1366  normFile.flags = util.fileFlags();
1367  normFile.stackSize = context.stackSize();
1368  normFile.installName = context.installName();
1369  normFile.currentVersion = context.currentVersion();
1370  normFile.compatVersion = context.compatibilityVersion();
1371  normFile.os = context.os();
1372
1373  // If we are emitting an object file, then the min version is the maximum
1374  // of the min's of all the source files and the cmdline.
1375  if (normFile.fileType == llvm::MachO::MH_OBJECT)
1376    normFile.minOSverson = std::max(context.osMinVersion(), util.minVersion());
1377  else
1378    normFile.minOSverson = context.osMinVersion();
1379
1380  normFile.minOSVersionKind = util.minVersionCommandType();
1381
1382  normFile.sdkVersion = context.sdkVersion();
1383  normFile.sourceVersion = context.sourceVersion();
1384
1385  if (context.generateVersionLoadCommand() &&
1386      context.os() != MachOLinkingContext::OS::unknown)
1387    normFile.hasMinVersionLoadCommand = true;
1388  else if (normFile.fileType == llvm::MachO::MH_OBJECT &&
1389           util.allSourceFilesHaveMinVersions() &&
1390           ((normFile.os != MachOLinkingContext::OS::unknown) ||
1391            util.minVersionCommandType())) {
1392    // If we emit an object file, then it should contain a min version load
1393    // command if all of the source files also contained min version commands.
1394    // Also, we either need to have a platform, or found a platform from the
1395    // source object files.
1396    normFile.hasMinVersionLoadCommand = true;
1397  }
1398  normFile.generateDataInCodeLoadCommand =
1399    context.generateDataInCodeLoadCommand();
1400  normFile.pageSize = context.pageSize();
1401  normFile.rpaths = context.rpaths();
1402  util.addDependentDylibs(atomFile, normFile);
1403  util.copySegmentInfo(normFile);
1404  util.copySectionInfo(normFile);
1405  util.assignAddressesToSections(normFile);
1406  util.buildAtomToAddressMap();
1407  util.updateSectionInfo(normFile);
1408  util.copySectionContent(normFile);
1409  if (auto ec = util.addSymbols(atomFile, normFile)) {
1410    return std::move(ec);
1411  }
1412  util.addIndirectSymbols(atomFile, normFile);
1413  util.addRebaseAndBindingInfo(atomFile, normFile);
1414  util.addExportInfo(atomFile, normFile);
1415  util.addSectionRelocs(atomFile, normFile);
1416  util.addFunctionStarts(atomFile, normFile);
1417  util.buildDataInCodeArray(atomFile, normFile);
1418  util.copyEntryPointAddress(normFile);
1419
1420  return std::move(f);
1421}
1422
1423} // namespace normalized
1424} // namespace mach_o
1425} // namespace lld
1426