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