src/ld/ld.cpp

   1 /* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-*
   2  *
   3  * Copyright (c) 2005-2011 Apple Inc. All rights reserved.
   4  *
   5  * @APPLE_LICENSE_HEADER_START@
   6  *
   7  * This file contains Original Code and/or Modifications of Original Code
   8  * as defined in and that are subject to the Apple Public Source License
   9  * Version 2.0 (the 'License'). You may not use this file except in
  10  * compliance with the License. Please obtain a copy of the License at
  11  * http://www.opensource.apple.com/apsl/ and read it before using this
  12  * file.
  13  *
  14  * The Original Code and all software distributed under the License are
  15  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  16  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  17  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  19  * Please see the License for the specific language governing rights and
  20  * limitations under the License.
  21  *
  22  * @APPLE_LICENSE_HEADER_END@
  23  */
  24
  25 // start temp HACK for cross builds
  26 extern "C" double log2 ( double );
  27 //#define __MATH__
  28 // end temp HACK for cross builds
  29
  30
  31 #include <stdlib.h>
  32 #include <sys/types.h>
  33 #include <sys/stat.h>
  34 #include <sys/mman.h>
  35 #include <sys/sysctl.h>
  36 #include <fcntl.h>
  37 #include <errno.h>
  38 #include <limits.h>
  39 #include <unistd.h>
  40 #include <execinfo.h>
  41 #include <mach/mach_time.h>
  42 #include <mach/vm_statistics.h>
  43 #include <mach/mach_init.h>
  44 #include <mach/mach_host.h>
  45 #include <dlfcn.h>
  46 #include <mach-o/dyld.h>
  47 #include <dlfcn.h>
  48 #include <AvailabilityMacros.h>
  49
  50 #include <string>
  51 #include <map>
  52 #include <set>
  53 #include <string>
  54 #include <vector>
  55 #include <list>
  56 #include <algorithm>
  57 #include <unordered_map>
  58 #include <cxxabi.h>
  59
  60 #include "Options.h"
  61
  62 #include "MachOFileAbstraction.hpp"
  63 #include "Architectures.hpp"
  64 #include "ld.hpp"
  65
  66 #include "InputFiles.h"
  67 #include "Resolver.h"
  68 #include "OutputFile.h"
  69 #include "Snapshot.h"
  70
  71 #include "passes/stubs/make_stubs.h"
  72 #include "passes/dtrace_dof.h"
  73 #include "passes/got.h"
  74 #include "passes/tlvp.h"
  75 #include "passes/huge.h"
  76 #include "passes/compact_unwind.h"
  77 #include "passes/order.h"
  78 #include "passes/branch_island.h"
  79 #include "passes/branch_shim.h"
  80 #include "passes/objc.h"
  81 #include "passes/dylibs.h"
  82 #include "passes/bitcode_bundle.h"
  83 #include "passes/code_dedup.h"
  84
  85 #include "parsers/archive_file.h"
  86 #include "parsers/macho_relocatable_file.h"
  87 #include "parsers/macho_dylib_file.h"
  88 #include "parsers/lto_file.h"
  89 #include "parsers/opaque_section_file.h"
  90
  91
  92 struct PerformanceStatistics {
  93         uint64_t                                                startTool;
  94         uint64_t                                                startInputFileProcessing;
  95         uint64_t                                                startResolver;
  96         uint64_t                                                startDylibs;
  97         uint64_t                                                startPasses;
  98         uint64_t                                                startOutput;
  99         uint64_t                                                startDone;
 100         vm_statistics_data_t                    vmStart;
 101         vm_statistics_data_t                    vmEnd;
 102 };
 103
 104
 105 class InternalState : public ld::Internal
 106 {
 107 public:
 108                                                                                         InternalState(const Options& opts) : _options(opts), _atomsOrderedInSections(false) { }
 109         virtual ld::Internal::FinalSection*             addAtom(const ld::Atom& atom);
 110         virtual ld::Internal::FinalSection*             getFinalSection(const ld::Section&);
 111                         ld::Internal::FinalSection*     getFinalSection(const char* seg, const char* sect, ld::Section::Type type);
 112
 113         uint64_t                                                                assignFileOffsets();
 114         void                                                                    setSectionSizesAndAlignments();
 115         void                                                                    sortSections();
 116         void                                                                    markAtomsOrdered() { _atomsOrderedInSections = true; }
 117         bool                                                                    hasReferenceToWeakExternal(const ld::Atom& atom);
 118
 119         virtual                                                                 ~InternalState() {}
 120 private:
 121         bool                                                                    inMoveRWChain(const ld::Atom& atom, const char* filePath, const char*& dstSeg, bool& wildCardMatch);
 122         bool                                                                    inMoveROChain(const ld::Atom& atom, const char* filePath, const char*& dstSeg, bool& wildCardMatch);
 123
 124         class FinalSection : public ld::Internal::FinalSection
 125         {
 126         public:
 127                                                                         FinalSection(const ld::Section& sect, uint32_t sectionsSeen, const Options&);
 128                 static int                                      sectionComparer(const void* l, const void* r);
 129                 static const ld::Section&       outputSection(const ld::Section& sect, bool mergeZeroFill);
 130                 static const ld::Section&       objectOutputSection(const ld::Section& sect, const Options&);
 131         private:
 132                 friend class InternalState;
 133                 static uint32_t         sectionOrder(const ld::Section& sect, uint32_t sectionsSeen, const Options& options);
 134                 static uint32_t         segmentOrder(const ld::Section& sect, const Options& options);
 135                 uint32_t                        _segmentOrder;
 136                 uint32_t                        _sectionOrder;
 137
 138                 static std::vector<const char*> _s_segmentsSeen;
 139                 static ld::Section              _s_DATA_data;
 140                 static ld::Section              _s_DATA_const;
 141                 static ld::Section              _s_TEXT_text;
 142                 static ld::Section              _s_TEXT_const;
 143                 static ld::Section              _s_DATA_nl_symbol_ptr;
 144                 static ld::Section              _s_DATA_common;
 145                 static ld::Section              _s_DATA_zerofill;
 146                 static ld::Section              _s_DATA_DIRTY_data;
 147                 static ld::Section              _s_DATA_CONST_const;
 148         };
 149
 150         bool hasZeroForFileOffset(const ld::Section* sect);
 151         uint64_t pageAlign(uint64_t addr);
 152         uint64_t pageAlign(uint64_t addr, uint64_t pageSize);
 153
 154         struct SectionHash {
 155                 size_t operator()(const ld::Section*) const;
 156         };
 157         struct SectionEquals {
 158                 bool operator()(const ld::Section* left, const ld::Section* right) const;
 159         };
 160         typedef std::unordered_map<const ld::Section*, FinalSection*, SectionHash, SectionEquals> SectionInToOut;
 161
 162
 163         SectionInToOut                  _sectionInToFinalMap;
 164         const Options&                  _options;
 165         bool                                    _atomsOrderedInSections;
 166         std::unordered_map<const ld::Atom*, const char*> _pendingSegMove;
 167 };
 168
 169 ld::Section     InternalState::FinalSection::_s_DATA_data( "__DATA", "__data",  ld::Section::typeUnclassified);
 170 ld::Section     InternalState::FinalSection::_s_DATA_const("__DATA", "__const", ld::Section::typeUnclassified);
 171 ld::Section     InternalState::FinalSection::_s_TEXT_text( "__TEXT", "__text",  ld::Section::typeCode);
 172 ld::Section     InternalState::FinalSection::_s_TEXT_const("__TEXT", "__const", ld::Section::typeUnclassified);
 173 ld::Section     InternalState::FinalSection::_s_DATA_nl_symbol_ptr("__DATA", "__nl_symbol_ptr", ld::Section::typeNonLazyPointer);
 174 ld::Section     InternalState::FinalSection::_s_DATA_common("__DATA", "__common", ld::Section::typeZeroFill);
 175 ld::Section     InternalState::FinalSection::_s_DATA_zerofill("__DATA", "__zerofill", ld::Section::typeZeroFill);
 176 ld::Section     InternalState::FinalSection::_s_DATA_DIRTY_data( "__DATA_DIRTY", "__data",  ld::Section::typeUnclassified);
 177 ld::Section     InternalState::FinalSection::_s_DATA_CONST_const( "__DATA_CONST", "__const",  ld::Section::typeUnclassified);
 178
 179 std::vector<const char*> InternalState::FinalSection::_s_segmentsSeen;
 180
 181
 182 size_t InternalState::SectionHash::operator()(const ld::Section* sect) const
 183 {
 184         size_t hash = 0;
 185         ld::CStringHash temp;
 186         hash += temp.operator()(sect->segmentName());
 187         hash += temp.operator()(sect->sectionName());
 188         return hash;
 189 }
 190
 191 bool InternalState::SectionEquals::operator()(const ld::Section* left, const ld::Section* right) const
 192 {
 193         return (*left == *right);
 194 }
 195
 196
 197 InternalState::FinalSection::FinalSection(const ld::Section& sect, uint32_t sectionsSeen, const Options& opts)
 198         : ld::Internal::FinalSection(sect),
 199           _segmentOrder(segmentOrder(sect, opts)),
 200           _sectionOrder(sectionOrder(sect, sectionsSeen, opts))
 201 {
 202         //fprintf(stderr, "FinalSection(%16s, %16s) _segmentOrder=%3d, _sectionOrder=0x%08X\n",
 203         //              this->segmentName(), this->sectionName(), _segmentOrder, _sectionOrder);
 204 }
 205
 206 const ld::Section& InternalState::FinalSection::outputSection(const ld::Section& sect, bool mergeZeroFill)
 207 {
 208         // merge sections in final linked image
 209         switch ( sect.type() ) {
 210                 case ld::Section::typeLiteral4:
 211                 case ld::Section::typeLiteral8:
 212                 case ld::Section::typeLiteral16:
 213                         if ( strcmp(sect.segmentName(), "__TEXT") == 0 )
 214                                 return _s_TEXT_const;
 215                         break;
 216                 case ld::Section::typeUnclassified:
 217                         if ( strcmp(sect.segmentName(), "__DATA") == 0 ) {
 218                                 if ( strcmp(sect.sectionName(), "__datacoal_nt") == 0 )
 219                                         return _s_DATA_data;
 220                                 if ( strcmp(sect.sectionName(), "__const_coal") == 0 )
 221                                         return _s_DATA_const;
 222                         }
 223                         else if ( strcmp(sect.segmentName(), "__TEXT") == 0 ) {
 224                                 if ( strcmp(sect.sectionName(), "__const_coal") == 0 )
 225                                         return _s_TEXT_const;
 226                         }
 227                         else if ( strcmp(sect.segmentName(), "__DATA_DIRTY") == 0 ) {
 228                                 if ( strcmp(sect.sectionName(), "__datacoal_nt") == 0 )
 229                                         return _s_DATA_DIRTY_data;
 230                         }
 231                         else if ( strcmp(sect.segmentName(), "__DATA_CONST") == 0 ) {
 232                                 if ( strcmp(sect.sectionName(), "__const_coal") == 0 )
 233                                         return _s_DATA_CONST_const;
 234                         }
 235                         break;
 236                 case ld::Section::typeZeroFill:
 237                         if ( mergeZeroFill )
 238                                 return _s_DATA_zerofill;
 239                         break;
 240                 case ld::Section::typeCode:
 241                         if ( strcmp(sect.segmentName(), "__TEXT") == 0 ) {
 242                                 if ( strcmp(sect.sectionName(), "__textcoal_nt") == 0 )
 243                                         return _s_TEXT_text;
 244                                 else if ( strcmp(sect.sectionName(), "__StaticInit") == 0 )
 245                                         return _s_TEXT_text;
 246                         }
 247                         break;
 248                 case ld::Section::typeNonLazyPointer:
 249                         if ( strcmp(sect.segmentName(), "__DATA") == 0 ) {
 250                                 if ( strcmp(sect.sectionName(), "__nl_symbol_ptr") == 0 )
 251                                         return _s_DATA_nl_symbol_ptr;
 252                         }
 253                         else if ( strcmp(sect.segmentName(), "__IMPORT") == 0 ) {
 254                                 if ( strcmp(sect.sectionName(), "__pointers") == 0 )
 255                                         return _s_DATA_nl_symbol_ptr;
 256                         }
 257                         break;
 258                 case ld::Section::typeTentativeDefs:
 259                         if ( (strcmp(sect.segmentName(), "__DATA") == 0) && (strcmp(sect.sectionName(), "__comm/tent") == 0) ) {
 260                                 if ( mergeZeroFill )
 261                                         return _s_DATA_zerofill;
 262                                 else
 263                                         return _s_DATA_common;
 264                         }
 265                         break;
 266                         // FIX ME: more
 267                 default:
 268                         break;
 269         }
 270         return sect;
 271 }
 272
 273 const ld::Section& InternalState::FinalSection::objectOutputSection(const ld::Section& sect, const Options& options)
 274 {
 275         // in -r mode the only section that ever changes is __tenative -> __common with -d option
 276         if ( (sect.type() == ld::Section::typeTentativeDefs) && options.makeTentativeDefinitionsReal())
 277                 return _s_DATA_common;
 278         return sect;
 279 }
 280
 281 uint32_t InternalState::FinalSection::segmentOrder(const ld::Section& sect, const Options& options)
 282 {
 283         if ( options.outputKind() == Options::kPreload ) {
 284                 if ( strcmp(sect.segmentName(), "__HEADER") == 0 )
 285                         return 0;
 286                 const std::vector<const char*>& order = options.segmentOrder();
 287                 for (size_t i=0; i != order.size(); ++i) {
 288                         if ( strcmp(sect.segmentName(), order[i]) == 0 )
 289                                 return i+1;
 290                 }
 291                 if ( strcmp(sect.segmentName(), "__TEXT") == 0 )
 292                         return order.size()+1;
 293                 if ( strcmp(sect.segmentName(), "__DATA") == 0 )
 294                         return order.size()+2;
 295         }
 296         else if ( options.outputKind() == Options::kStaticExecutable ) {
 297                 const std::vector<const char*>& order = options.segmentOrder();
 298                 for (size_t i=0; i != order.size(); ++i) {
 299                         if ( strcmp(sect.segmentName(), order[i]) == 0 )
 300                                 return i+1;
 301                 }
 302                 if ( strcmp(sect.segmentName(), "__PAGEZERO") == 0 )
 303                         return 0;
 304                 if ( strcmp(sect.segmentName(), "__TEXT") == 0 )
 305                         return order.size()+1;
 306                 if ( strcmp(sect.segmentName(), "__DATA") == 0 )
 307                         return order.size()+2;
 308         }
 309         else {
 310                 if ( strcmp(sect.segmentName(), "__PAGEZERO") == 0 )
 311                         return 0;
 312                 if ( strcmp(sect.segmentName(), "__TEXT") == 0 )
 313                         return 1;
 314                 if ( strcmp(sect.segmentName(), "__TEXT_EXEC") == 0 )
 315                         return 2;
 316                 // in -r mode, want __DATA  last so zerofill sections are at end
 317                 if ( strcmp(sect.segmentName(), "__DATA") == 0 )
 318                         return (options.outputKind() == Options::kObjectFile) ? 6 : 3;
 319                 if ( strcmp(sect.segmentName(), "__OBJC") == 0 )
 320                         return 4;
 321                 if ( strcmp(sect.segmentName(), "__IMPORT") == 0 )
 322                         return 5;
 323         }
 324         // layout non-standard segments in order seen (+100 to shift beyond standard segments)
 325         for (uint32_t i=0; i < _s_segmentsSeen.size(); ++i) {
 326                 if ( strcmp(_s_segmentsSeen[i], sect.segmentName()) == 0 )
 327                         return i+100;
 328         }
 329         _s_segmentsSeen.push_back(sect.segmentName());
 330         return _s_segmentsSeen.size()-1+100;
 331 }
 332
 333 uint32_t InternalState::FinalSection::sectionOrder(const ld::Section& sect, uint32_t sectionsSeen, const Options& options)
 334 {
 335         if ( sect.type() == ld::Section::typeFirstSection )
 336                 return 0;
 337         if ( sect.type() == ld::Section::typeMachHeader )
 338                 return 1;
 339         if ( sect.type() == ld::Section::typeLastSection )
 340                 return INT_MAX;
 341         const std::vector<const char*>* sectionList = options.sectionOrder(sect.segmentName());
 342         if ( ((options.outputKind() == Options::kPreload) || (options.outputKind() == Options::kDyld)) && (sectionList != NULL) ) {
 343                 uint32_t count = 10;
 344                 for (std::vector<const char*>::const_iterator it=sectionList->begin(); it != sectionList->end(); ++it, ++count) {
 345                         if ( strcmp(*it, sect.sectionName()) == 0 )
 346                                 return count;
 347                 }
 348         }
 349         if ( strcmp(sect.segmentName(), "__TEXT") == 0 ) {
 350                 switch ( sect.type() ) {
 351                         case ld::Section::typeCode:
 352                                 // <rdar://problem/8346444> make __text always be first "code" section
 353                                 if ( strcmp(sect.sectionName(), "__text") == 0 )
 354                                         return 10;
 355                                 else
 356                                         return 11;
 357                         case ld::Section::typeNonStdCString:
 358                                 if ( (strcmp(sect.sectionName(), "__oslogstring") == 0) && options.makeEncryptable() )
 359                                         return INT_MAX-1;
 360                                 else
 361                                         return sectionsSeen+20;
 362                         case ld::Section::typeStub:
 363                                 return 12;
 364                         case ld::Section::typeStubHelper:
 365                                 return 13;
 366                         case ld::Section::typeLSDA:
 367                                 return INT_MAX-4;
 368                         case ld::Section::typeUnwindInfo:
 369                                 return INT_MAX-3;
 370                         case ld::Section::typeCFI:
 371                                 return INT_MAX-2;
 372                         case ld::Section::typeStubClose:
 373                                 return INT_MAX;
 374                         default:
 375                                 return sectionsSeen+20;
 376                 }
 377         }
 378         else if ( strncmp(sect.segmentName(), "__DATA", 6) == 0 ) {
 379                 switch ( sect.type() ) {
 380                         case ld::Section::typeLazyPointerClose:
 381                                 return 8;
 382                         case ld::Section::typeDyldInfo:
 383                                 return 9;
 384                         case ld::Section::typeNonLazyPointer:
 385                                 return 10;
 386                         case ld::Section::typeLazyPointer:
 387                                 return 11;
 388                         case ld::Section::typeInitializerPointers:
 389                                 return 12;
 390                         case ld::Section::typeTerminatorPointers:
 391                                 return 13;
 392                         case ld::Section::typeTLVInitialValues:
 393                                 return INT_MAX-259; // need TLV zero-fill to follow TLV init values
 394                         case ld::Section::typeTLVZeroFill:
 395                                 return INT_MAX-258;
 396                         case ld::Section::typeZeroFill:
 397                                 // make sure __huge is always last zerofill section
 398                                 if ( strcmp(sect.sectionName(), "__huge") == 0 )
 399                                         return INT_MAX-1;
 400                                 else
 401                                         return INT_MAX-256+sectionsSeen; // <rdar://problem/25448494> zero fill need to be last and in "seen" order
 402                         default:
 403                                 // <rdar://problem/14348664> __DATA,__const section should be near __mod_init_func not __data
 404                                 if ( strcmp(sect.sectionName(), "__const") == 0 )
 405                                         return 14;
 406                                 // <rdar://problem/17125893> Linker should put __cfstring near __const
 407                                 if ( strcmp(sect.sectionName(), "__cfstring") == 0 )
 408                                         return 15;
 409                                 // <rdar://problem/7435296> Reorder sections to reduce page faults in object files
 410                                 else if ( strcmp(sect.sectionName(), "__objc_classlist") == 0 )
 411                                         return 20;
 412                                 else if ( strcmp(sect.sectionName(), "__objc_nlclslist") == 0 )
 413                                         return 21;
 414                                 else if ( strcmp(sect.sectionName(), "__objc_catlist") == 0 )
 415                                         return 22;
 416                                 else if ( strcmp(sect.sectionName(), "__objc_nlcatlist") == 0 )
 417                                         return 23;
 418                                 else if ( strcmp(sect.sectionName(), "__objc_protolist") == 0 )
 419                                         return 24;
 420                                 else if ( strcmp(sect.sectionName(), "__objc_imageinfo") == 0 )
 421                                         return 25;
 422                                 else if ( strcmp(sect.sectionName(), "__objc_const") == 0 )
 423                                         return 26;
 424                                 else if ( strcmp(sect.sectionName(), "__objc_selrefs") == 0 )
 425                                         return 27;
 426                                 else if ( strcmp(sect.sectionName(), "__objc_msgrefs") == 0 )
 427                                         return 28;
 428                                 else if ( strcmp(sect.sectionName(), "__objc_protorefs") == 0 )
 429                                         return 29;
 430                                 else if ( strcmp(sect.sectionName(), "__objc_classrefs") == 0 )
 431                                         return 30;
 432                                 else if ( strcmp(sect.sectionName(), "__objc_superrefs") == 0 )
 433                                         return 31;
 434                                 else if ( strcmp(sect.sectionName(), "__objc_ivar") == 0 )
 435                                         return 32;
 436                                 else if ( strcmp(sect.sectionName(), "__objc_data") == 0 )
 437                                         return 33;
 438                                 else
 439                                         return sectionsSeen+40;
 440                 }
 441         }
 442         // make sure zerofill in any other section is at end of segment
 443         if ( sect.type() == ld::Section::typeZeroFill )
 444                 return INT_MAX-256+sectionsSeen;
 445         return sectionsSeen+20;
 446 }
 447
 448 #ifndef NDEBUG
 449 static void validateFixups(const ld::Atom& atom)
 450 {
 451         //fprintf(stderr, "validateFixups %s\n", atom.name());
 452         bool lastWasClusterEnd = true;
 453         ld::Fixup::Cluster lastClusterSize = ld::Fixup::k1of1;
 454         uint32_t curClusterOffsetInAtom = 0;
 455         for (ld::Fixup::iterator fit=atom.fixupsBegin(); fit != atom.fixupsEnd(); ++fit) {
 456                 //fprintf(stderr, "  fixup offset=%d, cluster=%d\n", fit->offsetInAtom, fit->clusterSize);
 457                 assert((fit->offsetInAtom <= atom.size()) || (fit->offsetInAtom == 0));
 458                 if ( fit->firstInCluster() ) {
 459                         assert(lastWasClusterEnd);
 460                         curClusterOffsetInAtom = fit->offsetInAtom;
 461                         lastWasClusterEnd = (fit->clusterSize == ld::Fixup::k1of1);
 462                 }
 463                 else {
 464                         assert(!lastWasClusterEnd);
 465                         assert(fit->offsetInAtom == curClusterOffsetInAtom);
 466                         switch ((ld::Fixup::Cluster)fit->clusterSize) {
 467                                 case ld::Fixup::k1of1:
 468                                 case ld::Fixup::k1of2:
 469                                 case ld::Fixup::k1of3:
 470                                 case ld::Fixup::k1of4:
 471                                 case ld::Fixup::k1of5:
 472                                         lastWasClusterEnd = false;
 473                                         break;
 474                                 case ld::Fixup::k2of2:
 475                                         assert(lastClusterSize = ld::Fixup::k1of2);
 476                                         lastWasClusterEnd = true;
 477                                         break;
 478                                 case ld::Fixup::k2of3:
 479                                         assert(lastClusterSize = ld::Fixup::k1of3);
 480                                         lastWasClusterEnd = false;
 481                                         break;
 482                                 case ld::Fixup::k2of4:
 483                                         assert(lastClusterSize = ld::Fixup::k1of4);
 484                                         lastWasClusterEnd = false;
 485                                         break;
 486                                 case ld::Fixup::k2of5:
 487                                         assert(lastClusterSize = ld::Fixup::k1of5);
 488                                         lastWasClusterEnd = false;
 489                                         break;
 490                                 case ld::Fixup::k3of3:
 491                                         assert(lastClusterSize = ld::Fixup::k2of3);
 492                                         lastWasClusterEnd = true;
 493                                         break;
 494                                 case ld::Fixup::k3of4:
 495                                         assert(lastClusterSize = ld::Fixup::k2of4);
 496                                         lastWasClusterEnd = false;
 497                                         break;
 498                                 case ld::Fixup::k3of5:
 499                                         assert(lastClusterSize = ld::Fixup::k2of5);
 500                                         lastWasClusterEnd = false;
 501                                         break;
 502                                 case ld::Fixup::k4of4:
 503                                         assert(lastClusterSize = ld::Fixup::k3of4);
 504                                         lastWasClusterEnd = true;
 505                                         break;
 506                                 case ld::Fixup::k4of5:
 507                                         assert(lastClusterSize = ld::Fixup::k3of5);
 508                                         lastWasClusterEnd = false;
 509                                         break;
 510                                 case ld::Fixup::k5of5:
 511                                         assert(lastClusterSize = ld::Fixup::k4of5);
 512                                         lastWasClusterEnd = true;
 513                                         break;
 514                         }
 515                 }
 516                 lastClusterSize = fit->clusterSize;
 517                 if ( fit->binding == ld::Fixup::bindingDirectlyBound ) {
 518                         assert(fit->u.target != NULL);
 519                 }
 520         }
 521         switch (lastClusterSize) {
 522                 case ld::Fixup::k1of1:
 523                 case ld::Fixup::k2of2:
 524                 case ld::Fixup::k3of3:
 525                 case ld::Fixup::k4of4:
 526                 case ld::Fixup::k5of5:
 527                         break;
 528                 default:
 529                         assert(0 && "last fixup was not end of cluster");
 530                         break;
 531         }
 532 }
 533 #endif
 534
 535 bool InternalState::hasReferenceToWeakExternal(const ld::Atom& atom)
 536 {
 537         // if __DATA,__const atom has pointer to weak external symbol, don't move to __DATA_CONST
 538         const ld::Atom* target = NULL;
 539         for (ld::Fixup::iterator fit=atom.fixupsBegin(); fit != atom.fixupsEnd(); ++fit) {
 540                 if ( fit->firstInCluster() ) {
 541                         target = NULL;
 542                 }
 543                 switch ( fit->binding ) {
 544                         case ld::Fixup::bindingNone:
 545                         case ld::Fixup::bindingByNameUnbound:
 546                                 break;
 547                         case ld::Fixup::bindingByContentBound:
 548                         case ld::Fixup::bindingDirectlyBound:
 549                                 target = fit->u.target;
 550                                 break;
 551                         case ld::Fixup::bindingsIndirectlyBound:
 552                                 target = indirectBindingTable[fit->u.bindingIndex];
 553                                 break;
 554                 }
 555                 if ( (target != NULL) && (target->definition() == ld::Atom::definitionRegular)
 556                         && (target->combine() == ld::Atom::combineByName) && (target->scope() == ld::Atom::scopeGlobal) ) {
 557                         return true;
 558                 }
 559         }
 560         return false;
 561 }
 562
 563 bool InternalState::inMoveRWChain(const ld::Atom& atom, const char* filePath, const char*& dstSeg, bool& wildCardMatch)
 564 {
 565         if ( !_options.hasDataSymbolMoves() )
 566                 return false;
 567
 568         auto pos = _pendingSegMove.find(&atom);
 569         if ( pos != _pendingSegMove.end() ) {
 570                 dstSeg = pos->second;
 571                 return true;
 572         }
 573
 574         bool result = false;
 575         if ( _options.moveRwSymbol(atom.name(), filePath, dstSeg, wildCardMatch) )
 576                 result = true;
 577
 578         for (ld::Fixup::iterator fit=atom.fixupsBegin(); fit != atom.fixupsEnd(); ++fit) {
 579                 if ( fit->kind == ld::Fixup::kindNoneFollowOn ) {
 580                         if ( fit->binding == ld::Fixup::bindingDirectlyBound ) {
 581                                 if ( inMoveRWChain(*(fit->u.target), filePath, dstSeg, wildCardMatch) )
 582                                         result = true;
 583                         }
 584                 }
 585         }
 586
 587         if ( result ) {
 588                 for (ld::Fixup::iterator fit=atom.fixupsBegin(); fit != atom.fixupsEnd(); ++fit) {
 589                         if ( fit->kind == ld::Fixup::kindNoneFollowOn ) {
 590                                 if ( fit->binding == ld::Fixup::bindingDirectlyBound ) {
 591                                         _pendingSegMove[fit->u.target] = dstSeg;
 592                                 }
 593                         }
 594                 }
 595         }
 596
 597         return result;
 598 }
 599
 600
 601 bool InternalState::inMoveROChain(const ld::Atom& atom, const char* filePath, const char*& dstSeg, bool& wildCardMatch)
 602 {
 603         if ( !_options.hasCodeSymbolMoves() )
 604                 return false;
 605
 606         auto pos = _pendingSegMove.find(&atom);
 607         if ( pos != _pendingSegMove.end() ) {
 608                 dstSeg = pos->second;
 609                 return true;
 610         }
 611
 612         bool result = false;
 613         if ( _options.moveRoSymbol(atom.name(), filePath, dstSeg, wildCardMatch) )
 614                 result = true;
 615
 616         for (ld::Fixup::iterator fit=atom.fixupsBegin(); fit != atom.fixupsEnd(); ++fit) {
 617                 if ( fit->kind == ld::Fixup::kindNoneFollowOn ) {
 618                         if ( fit->binding == ld::Fixup::bindingDirectlyBound ) {
 619                                 if ( inMoveROChain(*(fit->u.target), filePath, dstSeg, wildCardMatch) )
 620                                         result = true;
 621                         }
 622                 }
 623         }
 624
 625         if ( result ) {
 626                 for (ld::Fixup::iterator fit=atom.fixupsBegin(); fit != atom.fixupsEnd(); ++fit) {
 627                         if ( fit->kind == ld::Fixup::kindNoneFollowOn ) {
 628                                 if ( fit->binding == ld::Fixup::bindingDirectlyBound ) {
 629                                         _pendingSegMove[fit->u.target] = dstSeg;
 630                                 }
 631                         }
 632                 }
 633         }
 634
 635         return result;
 636 }
 637
 638
 639
 640
 641 ld::Internal::FinalSection* InternalState::addAtom(const ld::Atom& atom)
 642 {
 643         //fprintf(stderr, "addAtom: %s\n", atom.name());
 644         ld::Internal::FinalSection* fs = NULL;
 645         const char* curSectName = atom.section().sectionName();
 646         const char* curSegName = atom.section().segmentName();
 647         ld::Section::Type sectType = atom.section().type();
 648         const ld::File* f = atom.file();
 649         const char* path = (f != NULL) ? f->path() : NULL;
 650         if ( atom.section().type() == ld::Section::typeTentativeDefs ) {
 651                 // tentative defintions don't have a real section name yet
 652                 sectType = ld::Section::typeZeroFill;
 653                 if ( _options.mergeZeroFill() )
 654                         curSectName = FinalSection::_s_DATA_zerofill.sectionName();
 655                 else
 656                         curSectName = FinalSection::_s_DATA_common.sectionName();
 657         }
 658         // Support for -move_to_r._segment
 659         if ( atom.symbolTableInclusion() == ld::Atom::symbolTableIn ) {
 660                 const char* dstSeg;
 661                 bool wildCardMatch;
 662                 if ( inMoveRWChain(atom, path, dstSeg, wildCardMatch) ) {
 663                         if ( (sectType != ld::Section::typeZeroFill)
 664                           && (sectType != ld::Section::typeUnclassified)
 665                           && (sectType != ld::Section::typeTentativeDefs)
 666                           && (sectType != ld::Section::typeDyldInfo) ) {
 667                                 if ( !wildCardMatch )
 668                                         warning("cannot move symbol '%s' from file %s to segment '%s' because symbol is not data (is %d)", atom.name(), path, dstSeg, sectType);
 669                         }
 670                         else {
 671                                 curSegName = dstSeg;
 672                                 if ( _options.traceSymbolLayout() )
 673                                         printf("symbol '%s', -move_to_rw_segment mapped it to %s/%s\n", atom.name(), curSegName, curSectName);
 674                                 fs = this->getFinalSection(curSegName, curSectName, sectType);
 675                         }
 676                 }
 677                 if ( (fs == NULL) && inMoveROChain(atom, path, dstSeg, wildCardMatch) ) {
 678                         if ( (sectType != ld::Section::typeCode)
 679                           && (sectType != ld::Section::typeUnclassified) ) {
 680                                 if ( !wildCardMatch )
 681                                         warning("cannot move symbol '%s' from file %s to segment '%s' because symbol is not code (is %d)", atom.name(), path, dstSeg, sectType);
 682                         }
 683                         else {
 684                                 curSegName = dstSeg;
 685                                 if ( _options.traceSymbolLayout() )
 686                                         printf("symbol '%s', -move_to_ro_segment mapped it to %s/%s\n", atom.name(), curSegName, curSectName);
 687                                 fs = this->getFinalSection(curSegName, curSectName, ld::Section::typeCode);
 688                         }
 689                 }
 690         }
 691         // support for -rename_section and -rename_segment
 692         for (const Options::SectionRename& rename : _options.sectionRenames()) {
 693                 if ( (strcmp(curSectName, rename.fromSection) == 0) && (strcmp(curSegName, rename.fromSegment) == 0) ) {
 694                         if ( _options.useDataConstSegment() && (strcmp(curSectName, "__const") == 0) && (strcmp(curSegName, "__DATA") == 0) && hasReferenceToWeakExternal(atom) ) {
 695                                 // if __DATA,__const atom has pointer to weak external symbol, don't move to __DATA_CONST
 696                                 curSectName = "__const_weak";
 697                                 fs = this->getFinalSection(curSegName, curSectName, sectType);
 698                                 if ( _options.traceSymbolLayout() )
 699                                         printf("symbol '%s', contains pointers to weak symbols, so mapped it to __DATA/__const_weak\n", atom.name());
 700                         }
 701                         else if ( _options.useDataConstSegment() && (sectType == ld::Section::typeNonLazyPointer) && hasReferenceToWeakExternal(atom) ) {
 702                                 // if __DATA,__nl_symbol_ptr atom has pointer to weak external symbol, don't move to __DATA_CONST
 703                                 curSectName = "__got_weak";
 704                                 fs = this->getFinalSection("__DATA", curSectName, sectType);
 705                                 if ( _options.traceSymbolLayout() )
 706                                         printf("symbol '%s', contains pointers to weak symbols, so mapped it to __DATA/__got_weak\n", atom.name());
 707                         }
 708                         else {
 709                                 curSegName = rename.toSegment;
 710                                 curSectName = rename.toSection;
 711                                 fs = this->getFinalSection(rename.toSegment, rename.toSection, sectType);
 712                                 if ( _options.traceSymbolLayout() )
 713                                         printf("symbol '%s', -rename_section mapped it to %s/%s\n", atom.name(), fs->segmentName(), fs->sectionName());
 714                         }
 715                 }
 716         }
 717         for (const Options::SegmentRename& rename : _options.segmentRenames()) {
 718                 if ( strcmp(curSegName, rename.fromSegment) == 0 ) {
 719                         if ( _options.traceSymbolLayout() )
 720                                 printf("symbol '%s', -rename_segment mapped it to %s/%s\n", atom.name(), rename.toSegment, curSectName);
 721                         fs = this->getFinalSection(rename.toSegment, curSectName, sectType);
 722                 }
 723         }
 724
 725         // if no override, use default location
 726         if ( fs == NULL ) {
 727                 fs = this->getFinalSection(atom.section());
 728                 if ( _options.traceSymbolLayout() && (atom.symbolTableInclusion() == ld::Atom::symbolTableIn) )
 729                         printf("symbol '%s', use default mapping to %s/%s\n", atom.name(), fs->segmentName(), fs->sectionName());
 730         }
 731
 732         //fprintf(stderr, "InternalState::doAtom(%p), name=%s, sect=%s, finalseg=%s\n", &atom, atom.name(), atom.section().sectionName(), fs->segmentName());
 733 #ifndef NDEBUG
 734         validateFixups(atom);
 735 #endif
 736         if ( _atomsOrderedInSections ) {
 737                 // make sure this atom is placed before any trailing section$end$ atom
 738                 if ( (fs->atoms.size() > 1) && (fs->atoms.back()->contentType() == ld::Atom::typeSectionEnd) ) {
 739                         // last atom in section$end$ atom, insert before it
 740                         const ld::Atom* endAtom = fs->atoms.back();
 741                         fs->atoms.pop_back();
 742                         fs->atoms.push_back(&atom);
 743                         fs->atoms.push_back(endAtom);
 744                 }
 745                 else {
 746                         // not end atom, just append new atom
 747                         fs->atoms.push_back(&atom);
 748                 }
 749         }
 750         else {
 751                 // normal case
 752                 fs->atoms.push_back(&atom);
 753         }
 754         this->atomToSection[&atom] = fs;
 755         return fs;
 756 }
 757
 758
 759
 760 ld::Internal::FinalSection* InternalState::getFinalSection(const char* seg, const char* sect, ld::Section::Type type)
 761 {
 762         for (std::vector<ld::Internal::FinalSection*>::iterator it=sections.begin(); it != sections.end(); ++it) {
 763                 if ( (strcmp((*it)->segmentName(),seg) == 0) && (strcmp((*it)->sectionName(),sect) == 0) )
 764                         return *it;
 765         }
 766         return this->getFinalSection(*new ld::Section(seg, sect, type, false));
 767 }
 768
 769 ld::Internal::FinalSection* InternalState::getFinalSection(const ld::Section& inputSection)
 770 {
 771         const ld::Section* baseForFinalSection = &inputSection;
 772
 773         // see if input section already has a FinalSection
 774         SectionInToOut::iterator pos = _sectionInToFinalMap.find(&inputSection);
 775         if ( pos != _sectionInToFinalMap.end() ) {
 776                 return pos->second;
 777         }
 778
 779         // otherwise, create a new final section
 780         switch ( _options.outputKind() ) {
 781                 case Options::kStaticExecutable:
 782                 case Options::kDynamicExecutable:
 783                 case Options::kDynamicLibrary:
 784                 case Options::kDynamicBundle:
 785                 case Options::kDyld:
 786                 case Options::kKextBundle:
 787                 case Options::kPreload:
 788                         {
 789                                 // coalesce some sections
 790                                 const ld::Section& outSect = FinalSection::outputSection(inputSection, _options.mergeZeroFill());
 791                                 pos = _sectionInToFinalMap.find(&outSect);
 792                                 if ( pos != _sectionInToFinalMap.end() ) {
 793                                         _sectionInToFinalMap[&inputSection] = pos->second;
 794                                         //fprintf(stderr, "_sectionInToFinalMap[%p] = %p\n", &inputSection, pos->second);
 795                                         return pos->second;
 796                                 }
 797                                 else if ( outSect != inputSection ) {
 798                                         // new output section created, but not in map
 799                                         baseForFinalSection = &outSect;
 800                                 }
 801                         }
 802                         break;
 803                 case Options::kObjectFile:
 804                         baseForFinalSection = &FinalSection::objectOutputSection(inputSection, _options);
 805                         pos = _sectionInToFinalMap.find(baseForFinalSection);
 806                         if ( pos != _sectionInToFinalMap.end() ) {
 807                                 _sectionInToFinalMap[&inputSection] = pos->second;
 808                                 //fprintf(stderr, "_sectionInToFinalMap[%p] = %p\n", &inputSection, pos->second);
 809                                 return pos->second;
 810                         }
 811                         break;
 812         }
 813
 814         InternalState::FinalSection* result = new InternalState::FinalSection(*baseForFinalSection,
 815                                                                                                                                         _sectionInToFinalMap.size(), _options);
 816         _sectionInToFinalMap[baseForFinalSection] = result;
 817         //fprintf(stderr, "_sectionInToFinalMap[%p(%s)] = %p\n", baseForFinalSection, baseForFinalSection->sectionName(), result);
 818         sections.push_back(result);
 819         return result;
 820 }
 821
 822
 823 int InternalState::FinalSection::sectionComparer(const void* l, const void* r)
 824 {
 825         const FinalSection* left  = *(FinalSection**)l;
 826         const FinalSection* right = *(FinalSection**)r;
 827         if ( left->_segmentOrder != right->_segmentOrder )
 828                 return (left->_segmentOrder - right->_segmentOrder);
 829         return (left->_sectionOrder - right->_sectionOrder);
 830 }
 831
 832 void InternalState::sortSections()
 833 {
 834         //fprintf(stderr, "UNSORTED final sections:\n");
 835         //for (std::vector<ld::Internal::FinalSection*>::iterator it = sections.begin(); it != sections.end(); ++it) {
 836         //      fprintf(stderr, "final section %p %s/%s\n", (*it), (*it)->segmentName(), (*it)->sectionName());
 837         //}
 838         qsort(&sections[0], sections.size(), sizeof(FinalSection*), &InternalState::FinalSection::sectionComparer);
 839         //fprintf(stderr, "SORTED final sections:\n");
 840         //for (std::vector<ld::Internal::FinalSection*>::iterator it = sections.begin(); it != sections.end(); ++it) {
 841         //      fprintf(stderr, "final section %p %s/%s\n", (*it), (*it)->segmentName(), (*it)->sectionName());
 842         //}
 843         assert((sections[0]->type() == ld::Section::typeMachHeader)
 844                 || ((sections[0]->type() == ld::Section::typeFirstSection) && (sections[1]->type() == ld::Section::typeMachHeader))
 845                 || ((sections[0]->type() == ld::Section::typePageZero) && (sections[1]->type() == ld::Section::typeMachHeader))
 846                 || ((sections[0]->type() == ld::Section::typePageZero) && (sections[1]->type() == ld::Section::typeFirstSection) && (sections[2]->type() == ld::Section::typeMachHeader)) );
 847
 848 }
 849
 850
 851 bool InternalState::hasZeroForFileOffset(const ld::Section* sect)
 852 {
 853         switch ( sect->type() ) {
 854                 case ld::Section::typeZeroFill:
 855                 case ld::Section::typeTLVZeroFill:
 856                         return _options.optimizeZeroFill();
 857                 case ld::Section::typePageZero:
 858                 case ld::Section::typeStack:
 859                 case ld::Section::typeTentativeDefs:
 860                         return true;
 861                 default:
 862                         break;
 863         }
 864         return false;
 865 }
 866
 867 uint64_t InternalState::pageAlign(uint64_t addr)
 868 {
 869         const uint64_t alignment = _options.segmentAlignment();
 870         return ((addr+alignment-1) & (-alignment));
 871 }
 872
 873 uint64_t InternalState::pageAlign(uint64_t addr, uint64_t pageSize)
 874 {
 875         return ((addr+pageSize-1) & (-pageSize));
 876 }
 877
 878 void InternalState::setSectionSizesAndAlignments()
 879 {
 880         for (std::vector<ld::Internal::FinalSection*>::iterator sit = sections.begin(); sit != sections.end(); ++sit) {
 881                 ld::Internal::FinalSection* sect = *sit;
 882                 if ( sect->type() == ld::Section::typeAbsoluteSymbols ) {
 883                         // absolute symbols need their finalAddress() to their value
 884                         for (std::vector<const ld::Atom*>::iterator ait = sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
 885                                 const ld::Atom* atom = *ait;
 886                                 (const_cast<ld::Atom*>(atom))->setSectionOffset(atom->objectAddress());
 887                         }
 888                 }
 889                 else {
 890                         uint16_t maxAlignment = 0;
 891                         uint64_t offset = 0;
 892                         for (std::vector<const ld::Atom*>::iterator ait = sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
 893                                 const ld::Atom* atom = *ait;
 894                                 bool pagePerAtom = false;
 895                                 uint32_t atomAlignmentPowerOf2 = atom->alignment().powerOf2;
 896                                 uint32_t atomModulus = atom->alignment().modulus;
 897                                 if ( _options.pageAlignDataAtoms() && ( strncmp(atom->section().segmentName(), "__DATA", 6) == 0) ) {
 898                                         // most objc sections cannot be padded
 899                                         bool contiguousObjCSection = ( strncmp(atom->section().sectionName(), "__objc_", 7) == 0 );
 900                                         if ( strcmp(atom->section().sectionName(), "__objc_const") == 0 )
 901                                                 contiguousObjCSection = false;
 902                                         if ( strcmp(atom->section().sectionName(), "__objc_data") == 0 )
 903                                                 contiguousObjCSection = false;
 904                                         switch ( atom->section().type() ) {
 905                                                 case ld::Section::typeUnclassified:
 906                                                 case ld::Section::typeTentativeDefs:
 907                                                 case ld::Section::typeZeroFill:
 908                                                         if ( contiguousObjCSection )
 909                                                                 break;
 910                                                         pagePerAtom = true;
 911                                                         if ( atomAlignmentPowerOf2 < 12 ) {
 912                                                                 atomAlignmentPowerOf2 = 12;
 913                                                                 atomModulus = 0;
 914                                                         }
 915                                                         break;
 916                                                 default:
 917                                                         break;
 918                                         }
 919                                 }
 920                                 if ( atomAlignmentPowerOf2 > maxAlignment )
 921                                         maxAlignment = atomAlignmentPowerOf2;
 922                                 // calculate section offset for this atom
 923                                 uint64_t alignment = 1 << atomAlignmentPowerOf2;
 924                                 uint64_t currentModulus = (offset % alignment);
 925                                 uint64_t requiredModulus = atomModulus;
 926                                 if ( currentModulus != requiredModulus ) {
 927                                         if ( requiredModulus > currentModulus )
 928                                                 offset += requiredModulus-currentModulus;
 929                                         else
 930                                                 offset += requiredModulus+alignment-currentModulus;
 931                                 }
 932                                 // LINKEDIT atoms are laid out later
 933                                 if ( sect->type() != ld::Section::typeLinkEdit ) {
 934                                         (const_cast<ld::Atom*>(atom))->setSectionOffset(offset);
 935                                         offset += atom->size();
 936                                         if ( pagePerAtom ) {
 937                                                 offset = (offset + 4095) & (-4096); // round up to end of page
 938                                         }
 939                                 }
 940                                 if ( (atom->scope() == ld::Atom::scopeGlobal)
 941                                         && (atom->definition() == ld::Atom::definitionRegular)
 942                                         && (atom->combine() == ld::Atom::combineByName)
 943                                         && ((atom->symbolTableInclusion() == ld::Atom::symbolTableIn)
 944                                          || (atom->symbolTableInclusion() == ld::Atom::symbolTableInAndNeverStrip)) ) {
 945                                                 this->hasWeakExternalSymbols = true;
 946                                                 if ( _options.warnWeakExports() )
 947                                                         warning("weak external symbol: %s", atom->name());
 948                                 }
 949                         }
 950                         sect->size = offset;
 951                         // section alignment is that of a contained atom with the greatest alignment
 952                         sect->alignment = maxAlignment;
 953                         // unless -sectalign command line option overrides
 954                         if  ( _options.hasCustomSectionAlignment(sect->segmentName(), sect->sectionName()) )
 955                                 sect->alignment = _options.customSectionAlignment(sect->segmentName(), sect->sectionName());
 956                         // each atom in __eh_frame has zero alignment to assure they pack together,
 957                         // but compilers usually make the CFIs pointer sized, so we want whole section
 958                         // to start on pointer sized boundary.
 959                         if ( sect->type() == ld::Section::typeCFI )
 960                                 sect->alignment = 3;
 961                         if ( sect->type() == ld::Section::typeTLVDefs )
 962                                 this->hasThreadLocalVariableDefinitions = true;
 963                 }
 964         }
 965
 966         // <rdar://problem/24221680> All __thread_data and __thread_bss sections must have same alignment
 967         uint8_t maxThreadAlign = 0;
 968         for (ld::Internal::FinalSection* sect : sections) {
 969                 if ( (sect->type() == ld::Section::typeTLVInitialValues) || (sect->type() == ld::Section::typeTLVZeroFill) ) {
 970                         if ( sect->alignment > maxThreadAlign )
 971                                 maxThreadAlign = sect->alignment;
 972                 }
 973         }
 974         for (ld::Internal::FinalSection* sect : sections) {
 975                 if ( (sect->type() == ld::Section::typeTLVInitialValues) || (sect->type() == ld::Section::typeTLVZeroFill) ) {
 976                         sect->alignment = maxThreadAlign;
 977                 }
 978         }
 979
 980 }
 981
 982 uint64_t InternalState::assignFileOffsets()
 983 {
 984         const bool log = false;
 985         const bool hiddenSectionsOccupyAddressSpace = ((_options.outputKind() != Options::kObjectFile)
 986                                                                                                 && (_options.outputKind() != Options::kPreload));
 987         const bool segmentsArePageAligned = (_options.outputKind() != Options::kObjectFile);
 988
 989         uint64_t address = 0;
 990         const char* lastSegName = "";
 991         uint64_t floatingAddressStart = _options.baseAddress();
 992         bool haveFixedSegments = false;
 993
 994         // mark all sections as not having an address yet
 995         for (std::vector<ld::Internal::FinalSection*>::iterator it = sections.begin(); it != sections.end(); ++it) {
 996                 ld::Internal::FinalSection* sect = *it;
 997                 sect->alignmentPaddingBytes = 0;
 998                 sect->address = ULLONG_MAX;
 999         }
1000
1001         // first pass, assign addresses to sections in segments with fixed start addresses
1002         if ( log ) fprintf(stderr, "Fixed address segments:\n");
1003         for (std::vector<ld::Internal::FinalSection*>::iterator it = sections.begin(); it != sections.end(); ++it) {
1004                 ld::Internal::FinalSection* sect = *it;
1005                 if ( ! _options.hasCustomSegmentAddress(sect->segmentName()) )
1006                         continue;
1007                 haveFixedSegments = true;
1008                 if ( segmentsArePageAligned ) {
1009                         if ( strcmp(lastSegName, sect->segmentName()) != 0 ) {
1010                                 address = _options.customSegmentAddress(sect->segmentName());
1011                                 lastSegName = sect->segmentName();
1012                         }
1013                 }
1014                 // adjust section address based on alignment
1015                 uint64_t unalignedAddress = address;
1016                 uint64_t alignment = (1 << sect->alignment);
1017                 address = ( (unalignedAddress+alignment-1) & (-alignment) );
1018
1019                 // update section info
1020                 sect->address = address;
1021                 sect->alignmentPaddingBytes = (address - unalignedAddress);
1022
1023                 // sanity check size
1024                 if ( ((address + sect->size) > _options.maxAddress()) && (_options.outputKind() != Options::kObjectFile)
1025                                                                                                                           && (_options.outputKind() != Options::kStaticExecutable) )
1026                         throwf("section %s (address=0x%08llX, size=%llu) would make the output executable exceed available address range",
1027                                                 sect->sectionName(), address, sect->size);
1028
1029                 if ( log ) fprintf(stderr, "  address=0x%08llX, hidden=%d, alignment=%02d, section=%s,%s\n",
1030                                                 sect->address, sect->isSectionHidden(), sect->alignment, sect->segmentName(), sect->sectionName());
1031                 // update running totals
1032                 if ( !sect->isSectionHidden() || hiddenSectionsOccupyAddressSpace )
1033                         address += sect->size;
1034
1035                 // if TEXT segment address is fixed, then flow other segments after it
1036                 if ( strcmp(sect->segmentName(), "__TEXT") == 0 ) {
1037                         floatingAddressStart = address;
1038                 }
1039         }
1040
1041         // second pass, assign section addresses to sections in segments that are ordered after a segment with a fixed address
1042         if ( haveFixedSegments && !_options.segmentOrder().empty() ) {
1043                 if ( log ) fprintf(stderr, "After Fixed address segments:\n");
1044                 lastSegName = "";
1045                 ld::Internal::FinalSection* lastSect = NULL;
1046                 for (std::vector<ld::Internal::FinalSection*>::iterator it = sections.begin(); it != sections.end(); ++it) {
1047                         ld::Internal::FinalSection* sect = *it;
1048                         if ( (sect->address == ULLONG_MAX) && _options.segmentOrderAfterFixedAddressSegment(sect->segmentName()) ) {
1049                                 address = lastSect->address + lastSect->size;
1050                                 if ( (strcmp(lastSegName, sect->segmentName()) != 0) && segmentsArePageAligned ) {
1051                                         // round up size of last segment
1052                                         address = pageAlign(address, _options.segPageSize(lastSegName));
1053                                 }
1054                                 // adjust section address based on alignment
1055                                 uint64_t unalignedAddress = address;
1056                                 uint64_t alignment = (1 << sect->alignment);
1057                                 address = ( (unalignedAddress+alignment-1) & (-alignment) );
1058                                 sect->alignmentPaddingBytes = (address - unalignedAddress);
1059                                 sect->address = address;
1060                                 if ( log ) fprintf(stderr, "  address=0x%08llX, hidden=%d, alignment=%02d, section=%s,%s\n",
1061                                                                         sect->address, sect->isSectionHidden(), sect->alignment, sect->segmentName(), sect->sectionName());
1062                                 // update running totals
1063                                 if ( !sect->isSectionHidden() || hiddenSectionsOccupyAddressSpace )
1064                                         address += sect->size;
1065                         }
1066                         lastSegName = sect->segmentName();
1067                         lastSect = sect;
1068                 }
1069         }
1070
1071         // last pass, assign addresses to remaining sections
1072         address = floatingAddressStart;
1073         lastSegName = "";
1074         ld::Internal::FinalSection* overlappingFixedSection = NULL;
1075         ld::Internal::FinalSection* overlappingFlowSection = NULL;
1076         ld::Internal::FinalSection* prevSect = NULL;
1077         if ( log ) fprintf(stderr, "Regular layout segments:\n");
1078         for (std::vector<ld::Internal::FinalSection*>::iterator it = sections.begin(); it != sections.end(); ++it) {
1079                 ld::Internal::FinalSection* sect = *it;
1080                 if ( sect->address != ULLONG_MAX )
1081                         continue;
1082                 if ( (_options.outputKind() == Options::kPreload) && (sect->type() == ld::Section::typeMachHeader) ) {
1083                         sect->alignmentPaddingBytes = 0;
1084                         continue;
1085                 }
1086                 if ( segmentsArePageAligned ) {
1087                         if ( strcmp(lastSegName, sect->segmentName()) != 0 ) {
1088                                 // round up size of last segment if needed
1089                                 if ( *lastSegName != '\0' ) {
1090                                         address = pageAlign(address, _options.segPageSize(lastSegName));
1091                                 }
1092                                 // set segment address based on end of last segment
1093                                 address = pageAlign(address);
1094                                 lastSegName = sect->segmentName();
1095                         }
1096                 }
1097
1098                 // adjust section address based on alignment
1099                 uint64_t unalignedAddress = address;
1100                 uint64_t alignment = (1 << sect->alignment);
1101                 address = ( (unalignedAddress+alignment-1) & (-alignment) );
1102
1103                 // update section info
1104                 sect->address = address;
1105                 sect->alignmentPaddingBytes = (address - unalignedAddress);
1106
1107                 // <rdar://problem/21994854> if first section is more aligned than segment, move segment start up to match
1108                 if ( (prevSect != NULL) && (prevSect->type() == ld::Section::typeFirstSection) && (strcmp(prevSect->segmentName(), sect->segmentName()) == 0) ) {
1109                         assert(prevSect->size == 0);
1110                         if ( prevSect->address != sect->address ) {
1111                                 prevSect->alignmentPaddingBytes += (sect->address - prevSect->address);
1112                                 prevSect->address = sect->address;
1113                         }
1114                 }
1115
1116                 // sanity check size
1117                 if ( ((address + sect->size) > _options.maxAddress()) && (_options.outputKind() != Options::kObjectFile)
1118                                                                                                                           && (_options.outputKind() != Options::kStaticExecutable) )
1119                                 throwf("section %s (address=0x%08llX, size=%llu) would make the output executable exceed available address range",
1120                                                 sect->sectionName(), address, sect->size);
1121
1122                 // sanity check it does not overlap a fixed address segment
1123                 for (std::vector<ld::Internal::FinalSection*>::iterator sit = sections.begin(); sit != sections.end(); ++sit) {
1124                         ld::Internal::FinalSection* otherSect = *sit;
1125                         if ( ! _options.hasCustomSegmentAddress(otherSect->segmentName()) )
1126                                 continue;
1127                         if ( otherSect->size == 0 )
1128                                 continue;
1129                         if ( sect->size == 0 )
1130                                 continue;
1131                         if ( sect->address > otherSect->address ) {
1132                                 if ( (otherSect->address+otherSect->size) > sect->address ) {
1133                                         overlappingFixedSection = otherSect;
1134                                         overlappingFlowSection = sect;
1135                                 }
1136                         }
1137                         else {
1138                                 if ( (sect->address+sect->size) > otherSect->address ) {
1139                                         overlappingFixedSection = otherSect;
1140                                         overlappingFlowSection = sect;
1141                                 }
1142                         }
1143                 }
1144
1145                 if ( log ) fprintf(stderr, "  address=0x%08llX, size=0x%08llX, hidden=%d, alignment=%02d, padBytes=%d, section=%s,%s\n",
1146                                                         sect->address, sect->size, sect->isSectionHidden(), sect->alignment, sect->alignmentPaddingBytes,
1147                                                         sect->segmentName(), sect->sectionName());
1148                 // update running totals
1149                 if ( !sect->isSectionHidden() || hiddenSectionsOccupyAddressSpace )
1150                         address += sect->size;
1151                 prevSect = sect;
1152         }
1153         if ( overlappingFixedSection != NULL ) {
1154                 fprintf(stderr, "Section layout:\n");
1155                 for (std::vector<ld::Internal::FinalSection*>::iterator it = sections.begin(); it != sections.end(); ++it) {
1156                         ld::Internal::FinalSection* sect = *it;
1157                         //if ( sect->isSectionHidden() )
1158                         //      continue;
1159                         fprintf(stderr, "  address:0x%08llX, alignment:2^%d, size:0x%08llX, padBytes:%d, section:%s/%s\n",
1160                                                         sect->address, sect->alignment, sect->size, sect->alignmentPaddingBytes,
1161                                                         sect->segmentName(), sect->sectionName());
1162
1163                 }
1164                 throwf("Section (%s/%s) overlaps fixed address section (%s/%s)",
1165                         overlappingFlowSection->segmentName(), overlappingFlowSection->sectionName(),
1166                         overlappingFixedSection->segmentName(), overlappingFixedSection->sectionName());
1167         }
1168
1169
1170         // third pass, assign section file offsets
1171         uint64_t fileOffset = 0;
1172         lastSegName = "";
1173         if ( log ) fprintf(stderr, "All segments with file offsets:\n");
1174         for (std::vector<ld::Internal::FinalSection*>::iterator it = sections.begin(); it != sections.end(); ++it) {
1175                 ld::Internal::FinalSection* sect = *it;
1176                 if ( hasZeroForFileOffset(sect) ) {
1177                         // fileoff of zerofill sections is moot, but historically it is set to zero
1178                         sect->fileOffset = 0;
1179
1180                         // <rdar://problem/10445047> align file offset with address layout
1181                         fileOffset += sect->alignmentPaddingBytes;
1182                 }
1183                 else {
1184                         // page align file offset at start of each segment
1185                         if ( segmentsArePageAligned && (*lastSegName != '\0') && (strcmp(lastSegName, sect->segmentName()) != 0) ) {
1186                                 fileOffset = pageAlign(fileOffset, _options.segPageSize(lastSegName));
1187                         }
1188                         lastSegName = sect->segmentName();
1189
1190                         // align file offset with address layout
1191                         fileOffset += sect->alignmentPaddingBytes;
1192
1193                         // update section info
1194                         sect->fileOffset = fileOffset;
1195
1196                         // update running total
1197                         fileOffset += sect->size;
1198                 }
1199
1200                 if ( log ) fprintf(stderr, "  fileoffset=0x%08llX, address=0x%08llX, hidden=%d, size=%lld, alignment=%02d, section=%s,%s\n",
1201                                 sect->fileOffset, sect->address, sect->isSectionHidden(), sect->size, sect->alignment,
1202                                 sect->segmentName(), sect->sectionName());
1203         }
1204
1205 #if 0
1206         // for encrypted iPhoneOS apps
1207         if ( _options.makeEncryptable() ) {
1208                 // remember end of __TEXT for later use by load command
1209                 for (std::vector<ld::Internal::FinalSection*>::iterator it = state.sections.begin(); it != state.sections.end(); ++it) {
1210                         ld::Internal::FinalSection* sect = *it;
1211                         if ( strcmp(sect->segmentName(), "__TEXT") == 0 ) {
1212                                 _encryptedTEXTendOffset = pageAlign(sect->fileOffset + sect->size);
1213                         }
1214                 }
1215         }
1216 #endif
1217
1218         // return total file size
1219         return fileOffset;
1220 }
1221
1222 static char* commatize(uint64_t in, char* out)
1223 {
1224         char* result = out;
1225         char rawNum[30];
1226         sprintf(rawNum, "%llu", in);
1227         const int rawNumLen = strlen(rawNum);
1228         for(int i=0; i < rawNumLen-1; ++i) {
1229                 *out++ = rawNum[i];
1230                 if ( ((rawNumLen-i) % 3) == 1 )
1231                         *out++ = ',';
1232         }
1233         *out++ = rawNum[rawNumLen-1];
1234         *out = '\0';
1235         return result;
1236 }
1237
1238 static void printTime(const char* msg, uint64_t partTime, uint64_t totalTime)
1239 {
1240         static uint64_t sUnitsPerSecond = 0;
1241         if ( sUnitsPerSecond == 0 ) {
1242                 struct mach_timebase_info timeBaseInfo;
1243                 if ( mach_timebase_info(&timeBaseInfo) != KERN_SUCCESS )
1244       return;
1245     sUnitsPerSecond = 1000000000ULL * timeBaseInfo.denom / timeBaseInfo.numer;
1246         }
1247         if ( partTime < sUnitsPerSecond ) {
1248                 uint32_t milliSecondsTimeTen = (partTime*10000)/sUnitsPerSecond;
1249                 uint32_t milliSeconds = milliSecondsTimeTen/10;
1250                 uint32_t percentTimesTen = (partTime*1000)/totalTime;
1251                 uint32_t percent = percentTimesTen/10;
1252                 fprintf(stderr, "%24s: % 4d.%d milliseconds (% 4d.%d%%)\n", msg, milliSeconds, milliSecondsTimeTen-milliSeconds*10, percent, percentTimesTen-percent*10);
1253         }
1254         else {
1255                 uint32_t secondsTimeTen = (partTime*10)/sUnitsPerSecond;
1256                 uint32_t seconds = secondsTimeTen/10;
1257                 uint32_t percentTimesTen = (partTime*1000)/totalTime;
1258                 uint32_t percent = percentTimesTen/10;
1259                 fprintf(stderr, "%24s: % 4d.%d seconds (% 4d.%d%%)\n", msg, seconds, secondsTimeTen-seconds*10, percent, percentTimesTen-percent*10);
1260         }
1261 }
1262
1263
1264 static void getVMInfo(vm_statistics_data_t& info)
1265 {
1266         mach_msg_type_number_t count = sizeof(vm_statistics_data_t) / sizeof(natural_t);
1267         kern_return_t error = host_statistics(mach_host_self(), HOST_VM_INFO,
1268                                                         (host_info_t)&info, &count);
1269         if (error != KERN_SUCCESS) {
1270                 bzero(&info, sizeof(vm_statistics_data_t));
1271         }
1272 }
1273
1274
1275
1276 static const char* sOverridePathlibLTO = NULL;
1277
1278 //
1279 // This is magic glue that overrides the default behaviour
1280 // of lazydylib1.o which is used to lazily load libLTO.dylib.
1281 //
1282 extern "C" const char* dyld_lazy_dylib_path_fix(const char* path);
1283 const char* dyld_lazy_dylib_path_fix(const char* path)
1284 {
1285         if ( sOverridePathlibLTO != NULL )
1286                 return sOverridePathlibLTO;
1287         else
1288                 return path;
1289 }
1290
1291
1292
1293 int main(int argc, const char* argv[])
1294 {
1295         const char* archName = NULL;
1296         bool showArch = false;
1297         bool archInferred = false;
1298         try {
1299                 PerformanceStatistics statistics;
1300                 statistics.startTool = mach_absolute_time();
1301
1302                 // create object to track command line arguments
1303                 Options options(argc, argv);
1304                 InternalState state(options);
1305
1306                 // allow libLTO to be overridden by command line -lto_library
1307                 sOverridePathlibLTO = options.overridePathlibLTO();
1308
1309                 // gather vm stats
1310                 if ( options.printStatistics() )
1311                         getVMInfo(statistics.vmStart);
1312
1313                 // update strings for error messages
1314                 showArch = options.printArchPrefix();
1315                 archName = options.architectureName();
1316                 archInferred = (options.architecture() == 0);
1317
1318                 // open and parse input files
1319                 statistics.startInputFileProcessing = mach_absolute_time();
1320                 ld::tool::InputFiles inputFiles(options, &archName);
1321
1322                 // load and resolve all references
1323                 statistics.startResolver = mach_absolute_time();
1324                 ld::tool::Resolver resolver(options, inputFiles, state);
1325                 resolver.resolve();
1326
1327                 // add dylibs used
1328                 statistics.startDylibs = mach_absolute_time();
1329                 inputFiles.dylibs(state);
1330
1331                 // do initial section sorting so passes have rough idea of the layout
1332                 state.sortSections();
1333
1334                 // run passes
1335                 statistics.startPasses = mach_absolute_time();
1336                 ld::passes::objc::doPass(options, state);
1337                 ld::passes::stubs::doPass(options, state);
1338                 ld::passes::huge::doPass(options, state);
1339                 ld::passes::got::doPass(options, state);
1340                 ld::passes::tlvp::doPass(options, state);
1341                 ld::passes::dylibs::doPass(options, state);     // must be after stubs and GOT passes
1342                 ld::passes::order::doPass(options, state);
1343                 state.markAtomsOrdered();
1344                 ld::passes::dedup::doPass(options, state);
1345                 ld::passes::branch_shim::doPass(options, state);        // must be after stubs
1346                 ld::passes::branch_island::doPass(options, state);      // must be after stubs and order pass
1347                 ld::passes::dtrace::doPass(options, state);
1348                 ld::passes::compact_unwind::doPass(options, state);  // must be after order pass
1349                 ld::passes::bitcode_bundle::doPass(options, state);  // must be after dylib
1350
1351                 // sort final sections
1352                 state.sortSections();
1353
1354                 // write output file
1355                 statistics.startOutput = mach_absolute_time();
1356                 ld::tool::OutputFile out(options);
1357                 out.write(state);
1358                 statistics.startDone = mach_absolute_time();
1359
1360                 // print statistics
1361                 //mach_o::relocatable::printCounts();
1362                 if ( options.printStatistics() ) {
1363                         getVMInfo(statistics.vmEnd);
1364                         uint64_t totalTime = statistics.startDone - statistics.startTool;
1365                         printTime("ld total time", totalTime, totalTime);
1366                         printTime(" option parsing time", statistics.startInputFileProcessing  -        statistics.startTool,                           totalTime);
1367                         printTime(" object file processing", statistics.startResolver                    -      statistics.startInputFileProcessing,totalTime);
1368                         printTime(" resolve symbols", statistics.startDylibs                             -      statistics.startResolver,                       totalTime);
1369                         printTime(" build atom list", statistics.startPasses                             -      statistics.startDylibs,                         totalTime);
1370                         printTime(" passess", statistics.startOutput                             -      statistics.startPasses,                         totalTime);
1371                         printTime(" write output", statistics.startDone                          -      statistics.startOutput,                         totalTime);
1372                         fprintf(stderr, "pageins=%u, pageouts=%u, faults=%u\n",
1373                                                                 statistics.vmEnd.pageins-statistics.vmStart.pageins,
1374                                                                 statistics.vmEnd.pageouts-statistics.vmStart.pageouts,
1375                                                                 statistics.vmEnd.faults-statistics.vmStart.faults);
1376                         char temp[40];
1377                         fprintf(stderr, "processed %3u object files,  totaling %15s bytes\n", inputFiles._totalObjectLoaded, commatize(inputFiles._totalObjectSize, temp));
1378                         fprintf(stderr, "processed %3u archive files, totaling %15s bytes\n", inputFiles._totalArchivesLoaded, commatize(inputFiles._totalArchiveSize, temp));
1379                         fprintf(stderr, "processed %3u dylib files\n", inputFiles._totalDylibsLoaded);
1380                         fprintf(stderr, "wrote output file            totaling %15s bytes\n", commatize(out.fileSize(), temp));
1381                 }
1382                 // <rdar://problem/6780050> Would like linker warning to be build error.
1383                 if ( options.errorBecauseOfWarnings() ) {
1384                         fprintf(stderr, "ld: fatal warning(s) induced error (-fatal_warnings)\n");
1385                         return 1;
1386                 }
1387         }
1388         catch (const char* msg) {
1389                 if ( strstr(msg, "malformed") != NULL )
1390                         fprintf(stderr, "ld: %s\n", msg);
1391                 else if ( archInferred )
1392                         fprintf(stderr, "ld: %s for inferred architecture %s\n", msg, archName);
1393                 else if ( showArch )
1394                         fprintf(stderr, "ld: %s for architecture %s\n", msg, archName);
1395                 else
1396                         fprintf(stderr, "ld: %s\n", msg);
1397                 return 1;
1398         }
1399
1400         return 0;
1401 }
1402
1403
1404 #ifndef NDEBUG
1405 // implement assert() function to print out a backtrace before aborting
1406 void __assert_rtn(const char* func, const char* file, int line, const char* failedexpr)
1407 {
1408     Snapshot *snapshot = Snapshot::globalSnapshot;
1409
1410     snapshot->setSnapshotMode(Snapshot::SNAPSHOT_DEBUG);
1411     snapshot->createSnapshot();
1412         snapshot->recordAssertionMessage("Assertion failed: (%s), function %s, file %s, line %d.\n", failedexpr, func, file, line);
1413
1414         void* callStack[128];
1415         int depth = ::backtrace(callStack, 128);
1416         char* buffer = (char*)malloc(1024);
1417         for(int i=0; i < depth-1; ++i) {
1418                 Dl_info info;
1419                 dladdr(callStack[i], &info);
1420                 const char* symboName = info.dli_sname;
1421                 if ( (symboName != NULL) && (strncmp(symboName, "_Z", 2) == 0) ) {
1422                         size_t bufLen = 1024;
1423                         int result;
1424                         char* unmangled = abi::__cxa_demangle(symboName, buffer, &bufLen, &result);
1425                         if ( unmangled != NULL )
1426                                 symboName = unmangled;
1427                 }
1428                 long offset = (uintptr_t)callStack[i] - (uintptr_t)info.dli_saddr;
1429                 fprintf(stderr, "%d  %p  %s + %ld\n", i, callStack[i], symboName, offset);
1430                 snapshot->recordAssertionMessage("%d  %p  %s + %ld\n", i, callStack[i], symboName, offset);
1431         }
1432     fprintf(stderr, "A linker snapshot was created at:\n\t%s\n", snapshot->rootDir());
1433         fprintf(stderr, "ld: Assertion failed: (%s), function %s, file %s, line %d.\n", failedexpr, func, file, line);
1434         exit(1);
1435 }
1436 #endif
1437
1438