contrib/llvm/tools/lld/lib/ReaderWriter/MachO/MachONormalizedFileFromAtoms.cpp

   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
  38 using llvm::StringRef;
  39 using llvm::isa;
  40 using namespace llvm::MachO;
  41 using namespace lld::mach_o::normalized;
  42 using namespace lld;
  43
  44 namespace {
  45
  46 struct AtomInfo {
  47   const DefinedAtom  *atom;
  48   uint64_t            offsetInSection;
  49 };
  50
  51 struct 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
  76 SectionInfo::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
  89 struct 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
 101 SegmentInfo::SegmentInfo(StringRef n)
 102  : name(n), address(0), size(0), init_access(0), max_access(0),
 103    normalizedSegmentIndex(0) {
 104 }
 105
 106 class Util {
 107 public:
 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
 146 private:
 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
 206 Util::~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
 223 SectionInfo *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
 254 struct MachOFinalSectionFromAtomType {
 255   StringRef                 segmentName;
 256   StringRef                 sectionName;
 257   SectionType               sectionType;
 258   DefinedAtom::ContentType  atomType;
 259 };
 260
 261 const 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
 301 SectionInfo *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
 338 SectionInfo *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
 371 void 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
 394 void Util::processDefinedAtoms(const lld::File &atomFile) {
 395   for (const DefinedAtom *atom : atomFile.defined()) {
 396     processAtomAttributes(atom);
 397     assignAtomToSection(atom);
 398   }
 399 }
 400
 401 void 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
 423 void 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
 435 SegmentInfo *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
 477 unsigned 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
 485 bool Util::SegmentSorter::operator()(const SegmentInfo *left,
 486                                   const SegmentInfo *right) {
 487   return (weight(left) < weight(right));
 488 }
 489
 490 unsigned 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
 502 bool Util::TextSectionSorter::operator()(const SectionInfo *left,
 503                                          const SectionInfo *right) {
 504   return (weight(left) < weight(right));
 505 }
 506
 507 void 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
 550 void 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.
 560 void 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
 582 void 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
 618 void 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
 630 void 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
 646 void 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
 693 void 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
 703 void 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
 717 void 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
 731 void 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
 788 uint16_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
 818 bool Util::AtomSorter::operator()(const AtomAndIndex &left,
 819                                   const AtomAndIndex &right) {
 820   return (left.atom->name().compare(right.atom->name()) < 0);
 821 }
 822
 823 llvm::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
 871 llvm::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
 971 const 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
 980 const 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
 993 void 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
1043 void 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
1090 int Util::dylibOrdinal(const SharedLibraryAtom *sa) {
1091   return _dylibInfo[sa->loadName()].ordinal;
1092 }
1093
1094 void 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
1108 uint32_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
1117 void 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
1160 void 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
1204 void 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
1246 void 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
1303 void 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
1331 uint32_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
1349 namespace lld {
1350 namespace mach_o {
1351 namespace normalized {
1352
1353 /// Convert a set of Atoms into a normalized mach-o file.
1354 llvm::Expected<std::unique_ptr<NormalizedFile>>
1355 normalizedFromAtoms(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