src/ld/ld.cpp

   1 /* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-*
   2  * Copyright (c) 2005-2009 Apple Inc. All rights reserved.
   3  *
   4  * @APPLE_LICENSE_HEADER_START@
   5  *
   6  * This file contains Original Code and/or Modifications of Original Code
   7  * as defined in and that are subject to the Apple Public Source License
   8  * Version 2.0 (the 'License'). You may not use this file except in
   9  * compliance with the License. Please obtain a copy of the License at
  10  * http://www.opensource.apple.com/apsl/ and read it before using this
  11  * file.
  12  *
  13  * The Original Code and all software distributed under the License are
  14  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  15  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  16  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  17  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  18  * Please see the License for the specific language governing rights and
  19  * limitations under the License.
  20  *
  21  * @APPLE_LICENSE_HEADER_END@
  22  */
  23
  24 // start temp HACK for cross builds
  25 extern "C" double log2 ( double );
  26 #define __MATH__
  27 // end temp HACK for cross builds
  28
  29
  30 #include <stdlib.h>
  31 #include <sys/types.h>
  32 #include <sys/stat.h>
  33 #include <sys/mman.h>
  34 #include <sys/sysctl.h>
  35 #include <fcntl.h>
  36 #include <errno.h>
  37 #include <limits.h>
  38 #include <unistd.h>
  39 #include <mach/mach_time.h>
  40 #include <mach/vm_statistics.h>
  41 #include <mach/mach_init.h>
  42 #include <mach/mach_host.h>
  43 #include <dlfcn.h>
  44
  45 #include <string>
  46 #include <map>
  47 #include <set>
  48 #include <string>
  49 #include <vector>
  50 #include <list>
  51 #include <algorithm>
  52 #include <ext/hash_map>
  53 #include <dlfcn.h>
  54 #include <AvailabilityMacros.h>
  55
  56 #include "configure.h"
  57 #include "Options.h"
  58
  59 #include "ObjectFile.h"
  60
  61 #include "MachOReaderRelocatable.hpp"
  62 #include "ArchiveReader.hpp"
  63 #include "MachOReaderDylib.hpp"
  64 #include "MachOWriterExecutable.hpp"
  65
  66
  67 #if LTO_SUPPORT
  68 #include "LTOReader.hpp"
  69 #endif
  70
  71 #include "OpaqueSection.hpp"
  72
  73
  74 class CStringComparor
  75 {
  76 public:
  77         bool operator()(const char* left, const char* right) const { return (strcmp(left, right) < 0); }
  78 };
  79
  80 class CStringEquals
  81 {
  82 public:
  83         bool operator()(const char* left, const char* right) const { return (strcmp(left, right) == 0); }
  84 };
  85
  86 class Section : public ObjectFile::Section
  87 {
  88 public:
  89         static Section* find(const char* sectionName, const char* segmentName, bool zeroFill, bool createIfNeeded=true);
  90         static void             assignIndexes();
  91         const char*             getName() { return fSectionName; }
  92 private:
  93                                         Section(const char* sectionName, const char* segmentName, bool zeroFill);
  94
  95         struct Sorter {
  96                 static int      segmentOrdinal(const char* segName);
  97                 bool operator()(Section* left, Section* right);
  98         };
  99
 100         typedef __gnu_cxx::hash_map<const char*, uint32_t, __gnu_cxx::hash<const char*>, CStringEquals> NameToOrdinal;
 101         typedef __gnu_cxx::hash_map<const char*, class Section*, __gnu_cxx::hash<const char*>, CStringEquals> NameToSection;
 102         //typedef std::map<const char*, class Section*, CStringComparor> NameToSection;
 103
 104         char                    fSectionName[18];
 105         char                    fSegmentName[18];
 106         bool                    fZeroFill;
 107
 108         static NameToSection                    fgMapping;
 109         static std::vector<Section*>    fgSections;
 110         static NameToOrdinal                    fgSegmentDiscoverOrder;
 111 };
 112
 113 Section::NameToSection  Section::fgMapping;
 114 std::vector<Section*>   Section::fgSections;
 115 Section::NameToOrdinal  Section::fgSegmentDiscoverOrder;
 116
 117 Section::Section(const char* sectionName, const char* segmentName, bool zeroFill)
 118  : fZeroFill(zeroFill)
 119 {
 120         strlcpy(fSectionName, sectionName, sizeof(fSectionName));
 121         strlcpy(fSegmentName, segmentName, sizeof(fSegmentName));
 122
 123         this->fIndex = fgSections.size() + 20;  // room for 20 standard sections
 124         // special placement of some sections
 125         if ( strcmp(segmentName, "__TEXT") == 0 ) {
 126                 // sort unwind info to end of segment
 127                 if ( strcmp(sectionName, "__eh_frame") == 0 )
 128                         this->fIndex = INT_MAX;
 129                 else if ( strcmp(sectionName, "__unwind_info") == 0 )
 130                         this->fIndex = INT_MAX-1;
 131                 else if ( strcmp(sectionName, "__gcc_except_tab") == 0 )
 132                         this->fIndex = INT_MAX-2;
 133         }
 134         else if ( strcmp(segmentName, "__DATA") == 0 ) {
 135                 // sort sections dyld will touch to start of segment
 136                 if ( strcmp(sectionName, "__dyld") == 0 )
 137                         this->fIndex = 1;
 138                 else if ( strcmp(sectionName, "__program_vars") == 0 )
 139                         this->fIndex = 1;
 140                 else if ( strcmp(sectionName, "__mod_init_func") == 0 )
 141                         this->fIndex = 2;
 142                 else if ( strcmp(sectionName, "__nl_symbol_ptr") == 0 )
 143                         this->fIndex = 3;
 144                 else if ( strcmp(sectionName, "__la_symbol_ptr") == 0 )
 145                         this->fIndex = 4;
 146                 else if ( strcmp(sectionName, "__const") == 0 )
 147                         this->fIndex = 5;
 148                 else if ( strcmp(sectionName, "__cfstring") == 0 )
 149                         this->fIndex = 6;
 150                 else if ( strcmp(sectionName, "__gcc_except_tab") == 0 )
 151                         this->fIndex = 7;
 152                 else if ( strcmp(sectionName, "__objc_data") == 0 )
 153                         this->fIndex = 8;
 154                 else if ( strcmp(sectionName, "__objc_msgrefs") == 0 )
 155                         this->fIndex = 9;
 156                 else if ( strcmp(sectionName, "__objc_protorefs") == 0 )
 157                         this->fIndex = 10;
 158                 else if ( strcmp(sectionName, "__objc_selrefs") == 0 )
 159                         this->fIndex = 11;
 160                 else if ( strcmp(sectionName, "__objc_classrefs") == 0 )
 161                         this->fIndex = 12;
 162                 else if ( strcmp(sectionName, "__objc_superrefs") == 0 )
 163                         this->fIndex = 13;
 164                 else if ( strcmp(sectionName, "__objc_const") == 0 )
 165                         this->fIndex = 14;
 166                 else if ( strcmp(sectionName, "__objc_classlist") == 0 )
 167                         this->fIndex = 15;
 168                 else if ( strcmp(sectionName, "__objc_nlclslist") == 0 )
 169                         this->fIndex = 16;
 170                 else if ( strcmp(sectionName, "__objc_catlist") == 0 )
 171                         this->fIndex = 17;
 172                 else if ( strcmp(sectionName, "__objc_protolist") == 0 )
 173                         this->fIndex = 18;
 174                 else if ( strcmp(sectionName, "__objc_imageinfo") == 0 )
 175                         this->fIndex = 19;
 176
 177         }
 178
 179         //fprintf(stderr, "new Section(%s, %s) => %p, %u\n", sectionName, segmentName, this, this->getIndex());
 180 }
 181
 182 Section* Section::find(const char* sectionName, const char* segmentName, bool zeroFill, bool createIfNeeded)
 183 {
 184         NameToSection::iterator pos = fgMapping.find(sectionName);
 185         if ( pos != fgMapping.end() ) {
 186                 if ( strcmp(pos->second->fSegmentName, segmentName) == 0 )
 187                         return pos->second;
 188                 // otherwise same section name is used in different segments, look slow way
 189                 for (std::vector<Section*>::iterator it=fgSections.begin(); it != fgSections.end(); it++) {
 190                         if ( (strcmp((*it)->fSectionName, sectionName) == 0) && (strcmp((*it)->fSegmentName, segmentName) == 0) )
 191                                 return *it;
 192                 }
 193         }
 194
 195         if ( !createIfNeeded )
 196                 return NULL;
 197
 198         // does not exist, so make a new one
 199         Section* sect = new Section(sectionName, segmentName, zeroFill);
 200         fgMapping[sectionName] = sect;
 201         fgSections.push_back(sect);
 202
 203         if ( (strcmp(sectionName, "__text") == 0) && (strcmp(segmentName, "__TEXT") == 0) ) {
 204                 // special case __StaticInit to be right after __text
 205                 find("__StaticInit", "__TEXT", false);
 206         }
 207
 208         // remember segment discovery order
 209         if ( fgSegmentDiscoverOrder.find(segmentName) == fgSegmentDiscoverOrder.end() )
 210                 fgSegmentDiscoverOrder[segmentName] = fgSegmentDiscoverOrder.size();
 211
 212         return sect;
 213 }
 214
 215 int Section::Sorter::segmentOrdinal(const char* segName)
 216 {
 217         if ( strcmp(segName, "__HEADER") == 0 )
 218                 return 1;
 219         if ( strcmp(segName, "__PAGEZERO") == 0 )
 220                 return 1;
 221         if ( strcmp(segName, "__TEXT") == 0 )
 222                 return 2;
 223         if ( strcmp(segName, "__DATA") == 0 )
 224                 return 3;
 225         if ( strcmp(segName, "__OBJC") == 0 )
 226                 return 4;
 227         if ( strcmp(segName, "__OBJC2") == 0 )
 228                 return 5;
 229         if ( strcmp(segName, "__LINKEDIT") == 0 )
 230                 return INT_MAX; // linkedit segment should always sort last
 231         else
 232                 return fgSegmentDiscoverOrder[segName]+6;
 233 }
 234
 235
 236 bool Section::Sorter::operator()(Section* left, Section* right)
 237 {
 238         // Segment is primary sort key
 239         int leftSegOrdinal = segmentOrdinal(left->fSegmentName);
 240         int rightSegOrdinal = segmentOrdinal(right->fSegmentName);
 241         if ( leftSegOrdinal < rightSegOrdinal )
 242                 return true;
 243         if ( leftSegOrdinal > rightSegOrdinal )
 244                 return false;
 245
 246         // zerofill section sort to the end
 247         if ( !left->fZeroFill && right->fZeroFill )
 248                 return true;
 249         if ( left->fZeroFill && !right->fZeroFill )
 250                 return false;
 251
 252         // section discovery order is last sort key
 253         return left->fIndex < right->fIndex;
 254 }
 255
 256 void Section::assignIndexes()
 257 {
 258         //printf("unsorted sections:\n");
 259         //for (std::vector<Section*>::iterator it=fgSections.begin(); it != fgSections.end(); it++) {
 260         //      printf("section: name=%s, segment: name=%s, discovery order=%d\n", (*it)->fSectionName, (*it)->fSegmentName, (*it)->fIndex);
 261         //}
 262
 263         // sort it
 264         std::sort(fgSections.begin(), fgSections.end(), Section::Sorter());
 265
 266         // assign correct section ordering to each Section object
 267         unsigned int newOrder = 1;
 268         for (std::vector<Section*>::iterator it=fgSections.begin(); it != fgSections.end(); it++)
 269                 (*it)->fIndex = newOrder++;
 270
 271         //printf("sorted sections:\n");
 272         //for (std::vector<Section*>::iterator it=fgSections.begin(); it != fgSections.end(); it++) {
 273         //      printf("section: index=%d, obj=%p, name=%s\n", (*it)->fIndex, (*it), (*it)->fSectionName);
 274         //}
 275 }
 276
 277 class Linker : public ObjectFile::Reader::DylibHander {
 278 public:
 279                                                 Linker(int argc, const char* argv[]);
 280
 281         const char*                     getArchPrefix();
 282         const char*                     architectureName();
 283         bool                            showArchitectureInErrors();
 284         bool                            isInferredArchitecture();
 285         void                            createReaders();
 286         void                            createWriter();
 287         void                            addInputFile(ObjectFile::Reader* reader, const Options::FileInfo& );
 288         void                            setOutputFile(ExecutableFile::Writer* writer);
 289         void                            link();
 290         void                            optimize();
 291
 292         // implemenation from ObjectFile::Reader::DylibHander
 293         virtual ObjectFile::Reader* findDylib(const char* installPath, const char* fromPath);
 294
 295 private:
 296         struct WhyLiveBackChain
 297         {
 298                 WhyLiveBackChain*       previous;
 299                 ObjectFile::Atom*       referer;
 300         };
 301
 302         ObjectFile::Reader*     createReader(const Options::FileInfo&);
 303         void                            addAtom(ObjectFile::Atom& atom);
 304         void                            addAtoms(std::vector<class ObjectFile::Atom*>& atoms);
 305         void                            buildAtomList();
 306         void                            adjustScope();
 307         void                            processDylibs();
 308         void                            markDead(ObjectFile::Atom* atom);
 309         void                            updateConstraints(ObjectFile::Reader* reader);
 310         void                            loadAndResolve();
 311         void                            processDTrace();
 312         void                            checkObjC();
 313         void                            loadUndefines();
 314         void                            checkUndefines();
 315         void                            resolveReferences();
 316         void                            deadStripResolve();
 317         void                            addLiveRoot(const char* name);
 318         void                            moveToFrontOfSection(ObjectFile::Atom* atom);
 319         ObjectFile::Atom*       findAtom(const Options::OrderedSymbol& pair);
 320         void                            logArchive(ObjectFile::Reader* reader);
 321         void                            sortSections();
 322         void                            sortAtoms();
 323         void                            tweakLayout();
 324         void                            writeDotOutput();
 325         static bool                     minimizeStab(ObjectFile::Reader::Stab& stab);
 326         static const char*      truncateStabString(const char* str);
 327         void                            collectDebugInfo();
 328         void                            writeOutput();
 329         ObjectFile::Atom*       entryPoint(bool orInit);
 330         ObjectFile::Atom*       dyldClassicHelper();
 331         ObjectFile::Atom*       dyldCompressedHelper();
 332         ObjectFile::Atom*       dyldLazyLibraryHelper();
 333         const char*                     assureFullPath(const char* path);
 334         void                            markLive(ObjectFile::Atom& atom, Linker::WhyLiveBackChain* previous);
 335         void                            collectStabs(ObjectFile::Reader* reader, std::map<const class ObjectFile::Atom*, uint32_t>& atomOrdinals);
 336         void                            synthesizeDebugNotes(std::vector<class ObjectFile::Atom*>& allAtomsByReader);
 337         void                            printStatistics();
 338         void                            printTime(const char* msg, uint64_t partTime, uint64_t totalTime);
 339         char*                           commatize(uint64_t in, char* out);
 340         void                            getVMInfo(vm_statistics_data_t& info);
 341         cpu_type_t                      inferArchitecture();
 342         void                            checkDylibClientRestrictions(ObjectFile::Reader* reader);
 343         void                            logDylib(ObjectFile::Reader* reader, bool indirect);
 344
 345         void                                                                    resolve(ObjectFile::Reference* reference);
 346         void                                                                    resolveFrom(ObjectFile::Reference* reference);
 347         std::vector<class ObjectFile::Atom*>*   addJustInTimeAtoms(const char* name, bool searchDylibs, bool searchArchives, bool okToMakeProxy);
 348         void                                                                    addJustInTimeAtomsAndMarkLive(const char* name);
 349
 350         ObjectFile::Reader*     addDylib(ObjectFile::Reader* reader, const Options::FileInfo& info, uint64_t mappedLen);
 351         ObjectFile::Reader*     addObject(ObjectFile::Reader* reader, const Options::FileInfo& info, uint64_t mappedLen);
 352         ObjectFile::Reader*     addArchive(ObjectFile::Reader* reader, const Options::FileInfo& info, uint64_t mappedLen);
 353
 354         void                            logTraceInfo(const char* format, ...);
 355
 356
 357         class SymbolTable
 358         {
 359         public:
 360                 typedef __gnu_cxx::hash_map<const char*, ObjectFile::Atom*, __gnu_cxx::hash<const char*>, CStringEquals> Mapper;
 361
 362                                                         SymbolTable(Linker&);
 363                 void                            require(const char* name);
 364                 bool                            add(ObjectFile::Atom& atom);
 365                 ObjectFile::Atom*       find(const char* name);
 366                 unsigned int            getRequireCount() { return fRequireCount; }
 367                 void                            getUndefinesNames(std::vector<const char*>& undefines);
 368                 void                            getTentativesNames(std::vector<const char*>& tents);
 369                 bool                            hasExternalTentativeDefinitions() { return fHasExternalTentativeDefinitions; }
 370                 bool                            hasExternalWeakDefinitions() { return fHasExternalWeakDefinitions; }
 371                 void                            setHasExternalWeakDefinitions(bool value) { fHasExternalWeakDefinitions = value; }
 372                 Mapper::iterator        begin() { return fTable.begin(); }
 373                 Mapper::iterator        end()   { return fTable.end(); }
 374
 375         private:
 376                 Linker&                         fOwner;
 377                 Mapper                          fTable;
 378                 unsigned int            fRequireCount;
 379                 bool                            fHasExternalTentativeDefinitions;
 380                 bool                            fHasExternalWeakDefinitions;
 381         };
 382
 383         class AtomSorter
 384         {
 385         public:
 386                 AtomSorter(std::map<const ObjectFile::Atom*, uint32_t>* map, std::set<const ObjectFile::Atom*>& inits,
 387                                                         std::set<const ObjectFile::Atom*>& terms) :
 388                                 fOverriddenOrdinalMap(map), fInitializerSet(inits), fTerminatorSet(terms) {}
 389                 bool operator()(const ObjectFile::Atom* left, const ObjectFile::Atom* right);
 390         private:
 391                 std::map<const ObjectFile::Atom*, uint32_t>*    fOverriddenOrdinalMap;
 392                 std::set<const ObjectFile::Atom*>&                              fInitializerSet;
 393                 std::set<const ObjectFile::Atom*>&                              fTerminatorSet;
 394         };
 395
 396         typedef std::map<const char*, uint32_t, CStringComparor> SectionOrder;
 397
 398         struct DTraceProbeInfo {
 399                 DTraceProbeInfo(const ObjectFile::Atom* a, uint32_t o, const char* n) : atom(a), offset(o), probeName(n) {}
 400                 const ObjectFile::Atom*                 atom;
 401                 uint32_t                                                offset;
 402                 const char*                                             probeName;
 403         };
 404         typedef __gnu_cxx::hash_map<const char*, std::vector<DTraceProbeInfo>, __gnu_cxx::hash<const char*>, CStringEquals>     ProviderToProbes;
 405         typedef __gnu_cxx::hash_set<const char*, __gnu_cxx::hash<const char*>, CStringEquals>  CStringSet;
 406         typedef __gnu_cxx::hash_map<const char*, ObjectFile::Reader*, __gnu_cxx::hash<const char*>, CStringEquals>      InstallNameToReader;
 407
 408         struct IndirectLibrary {
 409                 const char*                                                     path;
 410                 uint64_t                                                        fileLen;
 411                 ObjectFile::Reader*                                     reader;
 412                 std::set<ObjectFile::Reader*>           parents;
 413                 ObjectFile::Reader*                                     reExportedViaDirectLibrary;
 414         };
 415
 416         ObjectFile::Reader* findDirectLibraryWhichReExports(struct IndirectLibrary& indirectLib);
 417
 418         Options                                                                                         fOptions;
 419         SymbolTable                                                                                     fGlobalSymbolTable;
 420         uint32_t                                                                                        fNextInputOrdinal;
 421         std::vector<class ObjectFile::Reader*>                          fInputFiles;
 422         ExecutableFile::Writer*                                                         fOutputFile;
 423         InstallNameToReader                                                                     fDylibMap;
 424         std::map<ObjectFile::Reader*,LibraryOptions>            fDylibOptionsMap;
 425         std::set<ObjectFile::Reader*>                                           fDylibsProcessed;
 426         ObjectFile::Reader*                                                                     fBundleLoaderReader;
 427         std::vector<class ObjectFile::Reader*>                          fReadersThatHaveSuppliedAtoms;
 428         std::vector<class ObjectFile::Atom*>                            fAllAtoms;
 429         std::set<class ObjectFile::Reader*>                                     fArchiveReaders;
 430         std::set<class ObjectFile::Reader*>                                     fArchiveReadersLogged;
 431         std::set<class ObjectFile::Atom*>                                       fDeadAtoms;
 432         std::set<ObjectFile::Atom*>                                                     fLiveAtoms;
 433         std::set<ObjectFile::Atom*>                                                     fLiveRootAtoms;
 434         std::set<const ObjectFile::Atom*>                                       fInitializerAtoms;
 435         std::set<const ObjectFile::Atom*>                                       fTerminatorAtoms;
 436         std::set<const ObjectFile::Atom*>                                       fRegularDefAtomsThatOverrideADylibsWeakDef;
 437         std::vector<class ObjectFile::Reader::Stab>                     fStabs;
 438         std::vector<class ObjectFile::Atom*>                            fAtomsWithUnresolvedReferences;
 439         std::set<class ObjectFile::Atom*>                                       fAtomsOverriddenByLateLoads;
 440         bool                                                                                            fInitialLoadsDone;
 441         bool                                                                                            fCreateUUID;
 442         bool                                                                                            fCanScatter;
 443         SectionOrder                                                                            fSectionOrder;
 444         cpu_type_t                                                                                      fArchitecture;
 445         const char*                                                                                     fArchitectureName;
 446         bool                                                                                            fArchitectureInferred;
 447         bool                                                                                            fDirectLibrariesComplete;
 448         bool                                                                                            fBiggerThanTwoGigOutput;
 449         uint64_t                                                                                        fOutputFileSize;
 450         uint64_t                                                                                        fTotalZeroFillSize;
 451         uint64_t                                                                                        fTotalSize;
 452         uint64_t                                                                                        fStartTime;
 453         uint64_t                                                                                        fStartCreateReadersTime;
 454         uint64_t                                                                                        fStartCreateWriterTime;
 455         uint64_t                                                                                        fStartBuildAtomsTime;
 456         uint64_t                                                                                        fStartLoadAndResolveTime;
 457         uint64_t                                                                                        fStartSortTime;
 458         uint64_t                                                                                        fStartDebugTime;
 459         uint64_t                                                                                        fStartWriteTime;
 460         uint64_t                                                                                        fEndTime;
 461         uint64_t                                                                                        fTotalObjectSize;
 462         uint64_t                                                                                        fTotalArchiveSize;
 463         uint32_t                                                                                        fTotalObjectLoaded;
 464         uint32_t                                                                                        fTotalArchivesLoaded;
 465         uint32_t                                                                                        fTotalDylibsLoaded;
 466         vm_statistics_data_t                                                            fStartVMInfo;
 467         ObjectFile::Reader::ObjcConstraint                                      fCurrentObjCConstraint;
 468         ObjectFile::Reader::CpuConstraint                                       fCurrentCpuConstraint;
 469         bool                                                                                            fObjcReplacmentClasses;
 470         bool                                                                                            fAllDirectDylibsLoaded;
 471 };
 472
 473
 474 Linker::Linker(int argc, const char* argv[])
 475         : fOptions(argc, argv), fGlobalSymbolTable(*this), fNextInputOrdinal(1), fOutputFile(NULL), fBundleLoaderReader(NULL),
 476           fInitialLoadsDone(false), fCreateUUID(fOptions.outputKind() != Options::kObjectFile), fCanScatter(true),
 477           fArchitecture(0), fArchitectureInferred(false), fDirectLibrariesComplete(false), fBiggerThanTwoGigOutput(false),
 478           fOutputFileSize(0), fTotalZeroFillSize(0), fTotalSize(0), fTotalObjectSize(0),
 479           fTotalArchiveSize(0),  fTotalObjectLoaded(0), fTotalArchivesLoaded(0), fTotalDylibsLoaded(0),
 480           fCurrentObjCConstraint(ObjectFile::Reader::kObjcNone), fCurrentCpuConstraint(ObjectFile::Reader::kCpuAny),
 481           fObjcReplacmentClasses(false), fAllDirectDylibsLoaded(false)
 482 {
 483         fStartTime = mach_absolute_time();
 484         if ( fOptions.printStatistics() )
 485                 getVMInfo(fStartVMInfo);
 486
 487         fArchitecture = fOptions.architecture();
 488         if ( fArchitecture == 0 ) {
 489                 // -arch not specified, scan .o files to figure out what it should be
 490                 fArchitecture = inferArchitecture();
 491                 fArchitectureInferred = true;
 492         }
 493         switch (fArchitecture) {
 494                 case CPU_TYPE_POWERPC:
 495                         fArchitectureName = "ppc";
 496                         break;
 497                 case CPU_TYPE_POWERPC64:
 498                         fArchitectureName = "ppc64";
 499                         break;
 500                 case CPU_TYPE_I386:
 501                         fArchitectureName = "i386";
 502                         break;
 503                 case CPU_TYPE_X86_64:
 504                         fArchitectureName = "x86_64";
 505                         break;
 506                 case CPU_TYPE_ARM:
 507                         fArchitectureName = "arm";
 508                         break;
 509                 default:
 510                         fArchitectureName = "unknown architecture";
 511                         break;
 512         }
 513 }
 514
 515 const char*     Linker::architectureName()
 516 {
 517         return fArchitectureName;
 518 }
 519
 520 bool Linker::showArchitectureInErrors()
 521 {
 522         return fOptions.printArchPrefix();
 523 }
 524
 525 bool Linker::isInferredArchitecture()
 526 {
 527         return fArchitectureInferred;
 528 }
 529
 530 cpu_type_t Linker::inferArchitecture()
 531 {
 532         // scan all input files, looking for a thin .o file.
 533         // the first one found is presumably the architecture to link
 534         uint8_t buffer[sizeof(mach_header_64)];
 535         std::vector<Options::FileInfo>& files = fOptions.getInputFiles();
 536         for (std::vector<Options::FileInfo>::iterator it = files.begin(); it != files.end(); ++it) {
 537                 int fd = ::open(it->path, O_RDONLY, 0);
 538                 if ( fd != -1 ) {
 539                         ssize_t amount = read(fd, buffer, sizeof(buffer));
 540                         ::close(fd);
 541                         if ( amount >= (ssize_t)sizeof(buffer) ) {
 542                                 if ( mach_o::relocatable::Reader<ppc>::validFile(buffer) ) {
 543                                         //warning("-arch not used, infering -arch ppc based on %s", it->path);
 544                                         return CPU_TYPE_POWERPC;
 545                                 }
 546                                 else if ( mach_o::relocatable::Reader<ppc64>::validFile(buffer) ) {
 547                                         //warning("-arch not used, infering -arch ppc64 based on %s", it->path);
 548                                         return CPU_TYPE_POWERPC64;
 549                                 }
 550                                 else if ( mach_o::relocatable::Reader<x86>::validFile(buffer) ) {
 551                                         //warning("-arch not used, infering -arch i386 based on %s", it->path);
 552                                         return CPU_TYPE_I386;
 553                                 }
 554                                 else if ( mach_o::relocatable::Reader<x86_64>::validFile(buffer) ) {
 555                                         //warning("-arch not used, infering -arch x86_64 based on %s", it->path);
 556                                         return CPU_TYPE_X86_64;
 557                                 }
 558                                 else if ( mach_o::relocatable::Reader<arm>::validFile(buffer) ) {
 559                                         //warning("-arch not used, infering -arch arm based on %s", it->path);
 560                                         return CPU_TYPE_ARM;
 561                                 }
 562                         }
 563                 }
 564         }
 565
 566         // no thin .o files found, so default to same architecture this was built as
 567         warning("-arch not specified");
 568 #if __ppc__
 569         return CPU_TYPE_POWERPC;
 570 #elif __i386__
 571         return CPU_TYPE_I386;
 572 #elif __ppc64__
 573         return CPU_TYPE_POWERPC64;
 574 #elif __x86_64__
 575         return CPU_TYPE_X86_64;
 576 #elif __arm__
 577         return CPU_TYPE_ARM;
 578 #else
 579         #error unknown default architecture
 580 #endif
 581 }
 582
 583
 584 void Linker::addInputFile(ObjectFile::Reader* reader, const Options::FileInfo& info)
 585 {
 586         fInputFiles.push_back(reader);
 587         fDylibOptionsMap[reader] = info.options;
 588 }
 589
 590 void Linker::setOutputFile(ExecutableFile::Writer* writer)
 591 {
 592         fOutputFile = writer;
 593 }
 594
 595 class InSet
 596 {
 597 public:
 598         InSet(std::set<ObjectFile::Atom*>& deadAtoms) : fDeadAtoms(deadAtoms) {}
 599
 600         bool operator()(ObjectFile::Atom*& atom) const {
 601                 return ( fDeadAtoms.count(atom) != 0 );
 602         }
 603
 604 private:
 605         std::set<ObjectFile::Atom*>& fDeadAtoms;
 606 };
 607
 608 void Linker::loadAndResolve()
 609 {
 610         fStartLoadAndResolveTime = mach_absolute_time();
 611         if ( fOptions.deadStrip() == Options::kDeadStripOff ) {
 612                 // without dead-code-stripping:
 613                 // find atoms to resolve all undefines
 614                 this->loadUndefines();
 615                 // verify nothing is missing
 616                 this->checkUndefines();
 617                 // once all undefines fulfill, then bind all references
 618                 this->resolveReferences();
 619                 // remove atoms weak atoms that have been overridden
 620                 fAllAtoms.erase(std::remove_if(fAllAtoms.begin(), fAllAtoms.end(), InSet(fDeadAtoms)), fAllAtoms.end());
 621         }
 622         else {
 623                 // with dead code stripping:
 624                 // start binding references from roots,
 625                 this->deadStripResolve();
 626                 // verify nothing is missing
 627                 this->checkUndefines();
 628         }
 629 }
 630
 631 void Linker::optimize()
 632 {
 633         // give each reader a chance to do any optimizations
 634         bool didSomething = false;
 635         std::vector<class ObjectFile::Atom*> newAtoms;
 636         std::vector<const char *> additionalUndefines;
 637         std::vector<class ObjectFile::Atom*> newlyDeadAtoms;
 638         for (std::vector<class ObjectFile::Reader*>::iterator it=fInputFiles.begin(); it != fInputFiles.end(); it++) {
 639                 didSomething |= (*it)->optimize(fAllAtoms, newAtoms, additionalUndefines, fDeadAtoms, newlyDeadAtoms, fNextInputOrdinal,
 640                         fOutputFile, entryPoint(true), fOptions.llvmOptions(),
 641                          fOptions.allGlobalsAreDeadStripRoots(), (int)fOptions.outputKind(), fOptions.verbose(),
 642                         fOptions.saveTempFiles(), fOptions.getOutputFilePath(), fOptions.positionIndependentExecutable(),
 643                         fOptions.allowTextRelocs());
 644         }
 645
 646         // only do next steps if some optimization was actually done
 647         if  ( didSomething ) {
 648                 // add all newly created atoms to fAllAtoms and update symbol table
 649                 this->addAtoms(newAtoms);
 650
 651                 // add dead atoms to dead list and remove from fAllAtoms
 652                 for(std::vector<class ObjectFile::Atom*>::iterator itr = newlyDeadAtoms.begin(); itr != newlyDeadAtoms.end(); ++itr)
 653                         markDead(*itr);
 654                 fAllAtoms.erase(std::remove_if(fAllAtoms.begin(), fAllAtoms.end(), InSet(fDeadAtoms)), fAllAtoms.end());
 655
 656                 // Make sure all atoms have a section.  Atoms that were not originally in a mach-o file could
 657                 // not have their section set until now.
 658                 for(std::vector<class ObjectFile::Atom*>::iterator itr = fAllAtoms.begin(); itr != fAllAtoms.end(); ++itr) {
 659                         ObjectFile::Atom *atom = *itr;
 660                         if ( atom->getSection() == NULL )
 661                                 atom->setSection(Section::find(atom->getSectionName(), atom->getSegment().getName(), atom->isZeroFill()));
 662                 }
 663
 664                 // resolve new undefines
 665                 for(std::vector<const char*>::iterator riter = additionalUndefines.begin(); riter != additionalUndefines.end(); ++riter) {
 666                         const char *targetName = *riter;
 667                         //fprintf(stderr, "LTO additional undefine: %s\n", targetName);
 668                         ObjectFile::Atom* target = fGlobalSymbolTable.find(targetName);
 669                         if ( target == NULL) {
 670                                 // mark that this symbol is needed
 671                                 fGlobalSymbolTable.require(targetName);
 672                                 // try to find it in some library
 673                                 this->addJustInTimeAtoms(targetName, true, true, true);
 674                         }
 675                 }
 676
 677                 if ( fOptions.deadStrip() != Options::kDeadStripOff ) {
 678                         // LTO may optimize away some atoms, so dead stripping must be redone
 679                         fLiveAtoms.clear();
 680                         this->deadStripResolve();
 681                 }
 682                 else {
 683                         // LTO may require new library symbols to be loaded, so redo
 684                         this->checkUndefines();
 685                         this->resolveReferences();
 686                 }
 687         }
 688 }
 689
 690
 691 void Linker::adjustScope()
 692 {
 693         // if -exported_symbols_list is used, demoted to hidden, symbols that are not in it
 694         if ( fOptions.hasExportRestrictList() ) {
 695                 // The use of an -export file means the previous computation of fHasExternalWeakDefinitions could change
 696                 fGlobalSymbolTable.setHasExternalWeakDefinitions(false);
 697                 for(std::vector<class ObjectFile::Atom*>::iterator itr = fAllAtoms.begin(); itr != fAllAtoms.end(); ++itr) {
 698                         ObjectFile::Atom *atom = *itr;
 699                         ObjectFile::Atom::Scope scope = atom->getScope();
 700                         const char* name = atom->getName();
 701                         if ( name != NULL ) {
 702                                 if ( scope == ObjectFile::Atom::scopeGlobal ) {
 703                                         // check for globals that are downgraded to hidden
 704                                         if ( !fOptions.shouldExport(name) ) {
 705                                                 atom->setScope(ObjectFile::Atom::scopeLinkageUnit);
 706                                                 //fprintf(stderr, "demote %s to hidden\n", name);
 707                                         }
 708                                         else if ( atom->getDefinitionKind() == ObjectFile::Atom::kWeakDefinition ) {
 709                                                 // we do have an exported weak symbol, turn WEAK_DEFINES back on
 710                                                 fGlobalSymbolTable.setHasExternalWeakDefinitions(true);
 711                                         }
 712                                 }
 713                                 else if ( scope == ObjectFile::Atom::scopeLinkageUnit ) {
 714                                         // check for hiddens that were requested to be exported
 715                                         if ( fOptions.hasExportMaskList() && fOptions.shouldExport(name) ) {
 716                                                 warning("cannot export hidden symbol %s from %s", name, atom->getFile()->getPath());
 717                                         }
 718                                 }
 719                         }
 720                 }
 721         }
 722
 723         // linking is done, so demote hidden symbols to static
 724         if ( (fOptions.outputKind() == Options::kObjectFile) && fOptions.keepPrivateExterns() ) {
 725                 // ld -r -keep_private_externs does not move hidden symbols to static
 726         }
 727         else {
 728                 for(std::vector<class ObjectFile::Atom*>::iterator itr = fAllAtoms.begin(); itr != fAllAtoms.end(); ++itr) {
 729                         ObjectFile::Atom *atom = *itr;
 730                         // <rdar://problem/4637139> hidden common symbols cannot be demoted to static
 731                         if ( (atom->getScope() == ObjectFile::Atom::scopeLinkageUnit) && (atom->getDefinitionKind() != ObjectFile::Atom::kTentativeDefinition) ) {
 732                                 atom->setScope(ObjectFile::Atom::scopeTranslationUnit);
 733                                 //fprintf(stderr, "demote %s to static\n", atom->getDisplayName());
 734                         }
 735                 }
 736         }
 737 }
 738
 739 void Linker::link()
 740 {
 741         this->buildAtomList();
 742         this->loadAndResolve();
 743         this->optimize();
 744         this->adjustScope();
 745         this->checkObjC();
 746         this->processDTrace();
 747         this->tweakLayout();
 748         this->sortSections();
 749         this->sortAtoms();
 750         this->writeDotOutput();
 751         this->collectDebugInfo();
 752         this->writeOutput();
 753         this->printStatistics();
 754
 755         if ( fOptions.pauseAtEnd() )
 756                 sleep(10);
 757 }
 758
 759 void Linker::printTime(const char* msg, uint64_t partTime, uint64_t totalTime)
 760 {
 761         static uint64_t sUnitsPerSecond = 0;
 762         if ( sUnitsPerSecond == 0 ) {
 763                 struct mach_timebase_info timeBaseInfo;
 764                 if ( mach_timebase_info(&timeBaseInfo) == KERN_SUCCESS ) {
 765                         sUnitsPerSecond = 1000000000ULL * timeBaseInfo.denom / timeBaseInfo.numer;
 766                         //fprintf(stderr, "sUnitsPerSecond=%llu\n", sUnitsPerSecond);
 767                 }
 768         }
 769         if ( partTime < sUnitsPerSecond ) {
 770                 uint32_t milliSecondsTimeTen = (partTime*10000)/sUnitsPerSecond;
 771                 uint32_t milliSeconds = milliSecondsTimeTen/10;
 772                 uint32_t percentTimesTen = (partTime*1000)/totalTime;
 773                 uint32_t percent = percentTimesTen/10;
 774                 fprintf(stderr, "%s: %u.%u milliseconds (%u.%u%%)\n", msg, milliSeconds, milliSecondsTimeTen-milliSeconds*10, percent, percentTimesTen-percent*10);
 775         }
 776         else {
 777                 uint32_t secondsTimeTen = (partTime*10)/sUnitsPerSecond;
 778                 uint32_t seconds = secondsTimeTen/10;
 779                 uint32_t percentTimesTen = (partTime*1000)/totalTime;
 780                 uint32_t percent = percentTimesTen/10;
 781                 fprintf(stderr, "%s: %u.%u seconds (%u.%u%%)\n", msg, seconds, secondsTimeTen-seconds*10, percent, percentTimesTen-percent*10);
 782         }
 783 }
 784
 785 char* Linker::commatize(uint64_t in, char* out)
 786 {
 787         char* result = out;
 788         char rawNum[30];
 789         sprintf(rawNum, "%llu", in);
 790         const int rawNumLen = strlen(rawNum);
 791         for(int i=0; i < rawNumLen-1; ++i) {
 792                 *out++ = rawNum[i];
 793                 if ( ((rawNumLen-i) % 3) == 1 )
 794                         *out++ = ',';
 795         }
 796         *out++ = rawNum[rawNumLen-1];
 797         *out = '\0';
 798         return result;
 799 }
 800
 801 void Linker::getVMInfo(vm_statistics_data_t& info)
 802 {
 803         mach_msg_type_number_t count = sizeof(vm_statistics_data_t) / sizeof(natural_t);
 804         kern_return_t error = host_statistics(mach_host_self(), HOST_VM_INFO,
 805                                                         (host_info_t)&info, &count);
 806         if (error != KERN_SUCCESS) {
 807                 bzero(&info, sizeof(vm_statistics_data_t));
 808         }
 809 }
 810
 811 void Linker::printStatistics()
 812 {
 813         fEndTime = mach_absolute_time();
 814         if ( fOptions.printStatistics() ) {
 815                 vm_statistics_data_t endVMInfo;
 816                 getVMInfo(endVMInfo);
 817
 818                 uint64_t totalTime = fEndTime - fStartTime;
 819                 printTime("ld total time", totalTime, totalTime);
 820                 printTime(" option parsing time",       fStartCreateReadersTime -       fStartTime,                                     totalTime);
 821                 printTime(" object file processing",fStartCreateWriterTime -    fStartCreateReadersTime,        totalTime);
 822                 printTime(" output file setup",         fStartBuildAtomsTime -          fStartCreateWriterTime,         totalTime);
 823                 printTime(" build atom list",           fStartLoadAndResolveTime -      fStartBuildAtomsTime,           totalTime);
 824                 printTime(" resolve references",        fStartSortTime -                        fStartLoadAndResolveTime,       totalTime);
 825                 printTime(" sort output",                       fStartDebugTime -                       fStartSortTime,                         totalTime);
 826                 printTime(" process debug info",        fStartWriteTime -                       fStartDebugTime,                        totalTime);
 827                 printTime(" write output",                      fEndTime -                                      fStartWriteTime,                        totalTime);
 828                 fprintf(stderr, "pageins=%u, pageouts=%u, faults=%u\n", endVMInfo.pageins-fStartVMInfo.pageins,
 829                                                                                 endVMInfo.pageouts-fStartVMInfo.pageouts, endVMInfo.faults-fStartVMInfo.faults);
 830                 char temp[40];
 831                 fprintf(stderr, "processed %3u object files,  totaling %15s bytes\n", fTotalObjectLoaded, commatize(fTotalObjectSize, temp));
 832                 fprintf(stderr, "processed %3u archive files, totaling %15s bytes\n", fTotalArchivesLoaded, commatize(fTotalArchiveSize, temp));
 833                 fprintf(stderr, "processed %3u dylib files\n", fTotalDylibsLoaded);
 834                 fprintf(stderr, "wrote output file            totaling %15s bytes\n", commatize(fOutputFileSize, temp));
 835         }
 836 }
 837
 838 inline void Linker::addAtom(ObjectFile::Atom& atom)
 839 {
 840         // add to list of all atoms
 841         fAllAtoms.push_back(&atom);
 842
 843         if ( fOptions.deadStrip() == Options::kDeadStripOff ) {
 844                 // not dead-stripping code, so add atom's references's names to symbol table as to-be-resolved-later
 845                 std::vector<class ObjectFile::Reference*>& references = atom.getReferences();
 846                 for (std::vector<ObjectFile::Reference*>::iterator it=references.begin(); it != references.end(); it++) {
 847                         ObjectFile::Reference* reference = *it;
 848                         if ( reference->getTargetBinding() == ObjectFile::Reference::kUnboundByName )
 849                                 fGlobalSymbolTable.require(reference->getTargetName());
 850                         if ( reference->getFromTargetBinding() == ObjectFile::Reference::kUnboundByName )
 851                                 fGlobalSymbolTable.require(reference->getFromTargetName());
 852                 }
 853                 // update total size info (except for __ZEROPAGE atom)
 854                 if ( atom.getSegment().isContentReadable() ) {
 855                         fTotalSize += atom.getSize();
 856                         if ( atom.isZeroFill() )
 857                                 fTotalZeroFillSize += atom.getSize();
 858                 }
 859         }
 860         else {
 861                 if ( atom.dontDeadStrip() )
 862                         fLiveRootAtoms.insert(&atom);
 863         }
 864
 865         // if in global namespace, add atom itself to symbol table
 866         ObjectFile::Atom::Scope scope = atom.getScope();
 867         const char* name = atom.getName();
 868         if ( (scope != ObjectFile::Atom::scopeTranslationUnit) && (name != NULL) ) {
 869                 // add to symbol table
 870                 fGlobalSymbolTable.add(atom);
 871         }
 872
 873         // record section orders so output file can have same order
 874         if (atom.getSectionName())
 875                 atom.setSection(Section::find(atom.getSectionName(), atom.getSegment().getName(), atom.isZeroFill()));
 876 }
 877
 878
 879 void Linker::markDead(ObjectFile::Atom* atom)
 880 {
 881         //fprintf(stderr, "markDead(%p) %s from %s\n", atom, atom->getDisplayName(), atom->getFile()->getPath());
 882         fDeadAtoms.insert(atom);
 883
 884         // <rdar://problem/6578360> -dead_strip inhibits weak coalescing in no_dead_strip section
 885         if ( fLiveRootAtoms.count(atom) != 0 ) {
 886                 fLiveRootAtoms.erase(atom);
 887         }
 888
 889         //
 890         // The kGroupSubordinate reference kind is used to model group comdat.
 891         // The "signature" atom in the group has a kGroupSubordinate reference to
 892         // all other members of the group.  So, if the signature atom is
 893         // coalesced away, all other atoms in the group should also be removed.
 894         //
 895         std::vector<class ObjectFile::Reference*>& references = atom->getReferences();
 896         for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); rit++) {
 897                 ObjectFile::Reference* ref = *rit;
 898                 if ( ref->getKind() == 2 /*kGroupSubordinate*/ ) {      // FIX FIX
 899                         ObjectFile::Atom* targetAtom = &(ref->getTarget());
 900                         //fprintf(stderr, "  markDead(%p) subordinate %s\n", targetAtom, targetAtom->getDisplayName());
 901                         if ( targetAtom == NULL ) {
 902                                 warning("%s has a group reference to %s but is not bound", atom->getDisplayName(), ref->getTargetName());
 903                         }
 904                         else {
 905                                 if ( targetAtom->getScope() != ObjectFile::Atom::scopeTranslationUnit ) {
 906                                         // ok for .eh symbols to be not static in -r mode
 907                                         if ( (fOptions.outputKind() != Options::kObjectFile) || (strcmp(targetAtom->getSectionName(), "__eh_frame") != 0) )
 908                                                 warning("%s is in a comdat group but its scope is not static", targetAtom->getDisplayName());
 909                                 }
 910                                 this->markDead(targetAtom);
 911                         }
 912                 }
 913         }
 914 }
 915
 916 void Linker::updateConstraints(ObjectFile::Reader* reader)
 917 {
 918         // check objc objects were compiled compatibly
 919         ObjectFile::Reader::ObjcConstraint objcAddition = reader->getObjCConstraint();
 920         if ( reader->getInstallPath() == NULL ) {
 921                 // adding a .o file
 922                 switch ( objcAddition ) {
 923                         case ObjectFile::Reader::kObjcNone:
 924                                 break;
 925                         case ObjectFile::Reader::kObjcRetainRelease:
 926                                 if ( fCurrentObjCConstraint == ObjectFile::Reader::kObjcGC )
 927                                         throwf("%s built with incompatible Garbage Collection settings to link with previous .o files", reader->getPath());
 928                                 fCurrentObjCConstraint = ObjectFile::Reader::kObjcRetainRelease;
 929                                 break;
 930                         case ObjectFile::Reader::kObjcRetainReleaseOrGC:
 931                                 if ( fCurrentObjCConstraint == ObjectFile::Reader::kObjcNone )
 932                                         fCurrentObjCConstraint = ObjectFile::Reader::kObjcRetainReleaseOrGC;
 933                                 break;
 934                         case ObjectFile::Reader::kObjcGC:
 935                                 if ( fCurrentObjCConstraint == ObjectFile::Reader::kObjcRetainRelease )
 936                                         throwf("%s built with incompatible Garbage Collection settings to link with previous .o files", reader->getPath());
 937                                 fCurrentObjCConstraint = ObjectFile::Reader::kObjcGC;
 938                                 break;
 939                 }
 940         }
 941         if ( reader->objcReplacementClasses() )
 942                 fObjcReplacmentClasses = true;
 943
 944         // check cpu sub-types for stricter sub-type
 945         fCurrentCpuConstraint = (ObjectFile::Reader::CpuConstraint)reader->updateCpuConstraint(fCurrentCpuConstraint);
 946 }
 947
 948 inline void Linker::addAtoms(std::vector<class ObjectFile::Atom*>& atoms)
 949 {
 950         bool scanAll = fOptions.readerOptions().fFullyLoadArchives || fOptions.readerOptions().fLoadAllObjcObjectsFromArchives;
 951         bool first = true;
 952         for (std::vector<ObjectFile::Atom*>::iterator it=atoms.begin(); it != atoms.end(); it++) {
 953                 // usually we only need to get the first atom's reader, but
 954                 // with -all_load all atoms from all .o files come come back together
 955                 // so we need to scan all atoms
 956                 if ( first || scanAll ) {
 957                         // update fReadersThatHaveSuppliedAtoms
 958                         ObjectFile::Reader* reader = (*it)->getFile();
 959                         if ( std::find(fReadersThatHaveSuppliedAtoms.begin(), fReadersThatHaveSuppliedAtoms.end(), reader)
 960                                         == fReadersThatHaveSuppliedAtoms.end() ) {
 961                                 fReadersThatHaveSuppliedAtoms.push_back(reader);
 962                                 updateConstraints(reader);
 963                         }
 964                 }
 965                 this->addAtom(**it);
 966                 first = false;
 967         }
 968 }
 969
 970 void Linker::logArchive(ObjectFile::Reader* reader)
 971 {
 972         if ( (fArchiveReaders.count(reader) != 0) && (fArchiveReadersLogged.count(reader) == 0) ) {
 973                 fArchiveReadersLogged.insert(reader);
 974                 const char* fullPath = reader->getPath();
 975                 char realName[MAXPATHLEN];
 976                 if ( realpath(fullPath, realName) != NULL )
 977                         fullPath = realName;
 978                 logTraceInfo("[Logging for XBS] Used static archive: %s\n", fullPath);
 979         }
 980 }
 981
 982
 983 void Linker::buildAtomList()
 984 {
 985         fStartBuildAtomsTime = mach_absolute_time();
 986         // add initial undefines from -u option
 987         std::vector<const char*>& initialUndefines = fOptions.initialUndefines();
 988         for (std::vector<const char*>::iterator it=initialUndefines.begin(); it != initialUndefines.end(); it++) {
 989                 fGlobalSymbolTable.require(*it);
 990         }
 991
 992         // writer can contribute atoms
 993         this->addAtoms(fOutputFile->getAtoms());
 994
 995         // each reader contributes atoms
 996         for (std::vector<class ObjectFile::Reader*>::iterator it=fInputFiles.begin(); it != fInputFiles.end(); it++) {
 997                 ObjectFile::Reader* reader = *it;
 998                 std::vector<class ObjectFile::Atom*>& atoms = reader->getAtoms();
 999                 this->addAtoms(atoms);
1000                 if ( fOptions.readerOptions().fTraceArchives && (atoms.size() != 0) )
1001                         logArchive(reader);
1002         }
1003
1004         // extra command line section always at end
1005         std::vector<Options::ExtraSection>& extraSections = fOptions.extraSections();
1006         for( std::vector<Options::ExtraSection>::iterator it=extraSections.begin(); it != extraSections.end(); ++it) {
1007                 this->addAtoms((new opaque_section::Reader(it->segmentName, it->sectionName, it->path, it->data, it->dataLen, fNextInputOrdinal))->getAtoms());
1008                 fNextInputOrdinal += it->dataLen;
1009         }
1010
1011         // done with all .o files on command line
1012         // everything loaded from now on is a just-in-time atom
1013         fInitialLoadsDone = true;
1014 }
1015
1016 static const char* pathLeafName(const char* path)
1017 {
1018         const char* shortPath = strrchr(path, '/');
1019         if ( shortPath == NULL )
1020                 return path;
1021         else
1022                 return &shortPath[1];
1023 }
1024
1025
1026 void Linker::loadUndefines()
1027 {
1028         // keep looping until no more undefines were added in last loop
1029         unsigned int undefineCount = 0xFFFFFFFF;
1030         while ( undefineCount != fGlobalSymbolTable.getRequireCount() ) {
1031                 undefineCount = fGlobalSymbolTable.getRequireCount();
1032                 std::vector<const char*> undefineNames;
1033                 fGlobalSymbolTable.getUndefinesNames(undefineNames);
1034                 for(std::vector<const char*>::iterator it = undefineNames.begin(); it != undefineNames.end(); ++it) {
1035                         // load for previous undefine may also have loaded this undefine, so check again
1036                         if ( fGlobalSymbolTable.find(*it) == NULL ) {
1037                                 std::vector<class ObjectFile::Atom*>* atoms = this->addJustInTimeAtoms(*it, true, true, true);
1038                                 if ( atoms != NULL )
1039                                         delete atoms;
1040                         }
1041                 }
1042                 // <rdar://problem/5894163> need to search archives for overrides of common symbols
1043                 if ( fGlobalSymbolTable.hasExternalTentativeDefinitions() ) {
1044                         bool searchDylibs = (fOptions.commonsMode() == Options::kCommonsOverriddenByDylibs);
1045                         std::vector<const char*> tentativeDefinitionNames;
1046                         fGlobalSymbolTable.getTentativesNames(tentativeDefinitionNames);
1047                         for(std::vector<const char*>::iterator it = tentativeDefinitionNames.begin(); it != tentativeDefinitionNames.end(); ++it) {
1048                                 // load for previous tentative  may also have overridden this tentative, so check again
1049                                 ObjectFile::Atom* tent = fGlobalSymbolTable.find(*it);
1050                                 if ( (tent != NULL) && (tent->getDefinitionKind() == ObjectFile::Atom::kTentativeDefinition) ) {
1051                                         std::vector<class ObjectFile::Atom*>* atoms = this->addJustInTimeAtoms(*it, searchDylibs, true, false);
1052                                         if ( atoms != NULL )
1053                                                 delete atoms;
1054                                 }
1055                         }
1056                 }
1057         }
1058 }
1059
1060 // temp hack for rdar://problem/4718189 map ObjC class names to new runtime names
1061 class ExportedObjcClass
1062 {
1063 public:
1064         ExportedObjcClass(Options& opt) : fOptions(opt)  {}
1065
1066         bool operator()(const char* name) const {
1067                 if ( fOptions.shouldExport(name) ) {
1068                         if ( strncmp(name, ".objc_class_name_", 17) == 0 )
1069                                 return true;
1070                         if ( strncmp(name, "_OBJC_CLASS_$_", 14) == 0 )
1071                                 return true;
1072                         if ( strncmp(name, "_OBJC_METACLASS_$_", 18) == 0 )
1073                                 return true;
1074                 }
1075                 //fprintf(stderr, "%s is not exported\n", name);
1076                 return false;
1077         }
1078 private:
1079         Options& fOptions;
1080 };
1081
1082
1083 void Linker::checkUndefines()
1084 {
1085         // error out on any remaining undefines
1086         bool doPrint = true;
1087         bool doError = true;
1088         switch ( fOptions.undefinedTreatment() ) {
1089                 case Options::kUndefinedError:
1090                         break;
1091                 case Options::kUndefinedDynamicLookup:
1092                         doError = false;
1093                         break;
1094                 case Options::kUndefinedWarning:
1095                         doError = false;
1096                         break;
1097                 case Options::kUndefinedSuppress:
1098                         doError = false;
1099                         doPrint = false;
1100                         break;
1101         }
1102         std::vector<const char*> unresolvableUndefines;
1103         fGlobalSymbolTable.getUndefinesNames(unresolvableUndefines);
1104
1105         // temp hack for rdar://problem/4718189 map ObjC class names to new runtime names
1106         // ignore unresolved references to Objc class names that are listed in -exported_symbols_list
1107         if ( fOptions.hasExportRestrictList() )
1108                 unresolvableUndefines.erase(std::remove_if(unresolvableUndefines.begin(), unresolvableUndefines.end(), ExportedObjcClass(fOptions)), unresolvableUndefines.end());
1109
1110         const int unresolvableCount = unresolvableUndefines.size();
1111         int unresolvableExportsCount  = 0;
1112         if ( unresolvableCount != 0 ) {
1113                 if ( doPrint ) {
1114                         if ( fOptions.printArchPrefix() )
1115                                 fprintf(stderr, "Undefined symbols for architecture %s:\n", fArchitectureName);
1116                         else
1117                                 fprintf(stderr, "Undefined symbols:\n");
1118                         for (int i=0; i < unresolvableCount; ++i) {
1119                                 const char* name = unresolvableUndefines[i];
1120                                 fprintf(stderr, "  \"%s\", referenced from:\n", name);
1121                                 // scan all atoms for references
1122                                 bool foundAtomReference = false;
1123                                 for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
1124                                         ObjectFile::Atom* atom = *it;
1125                                         std::vector<class ObjectFile::Reference*>& references = atom->getReferences();
1126                                         for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); rit++) {
1127                                                 ObjectFile::Reference* reference = *rit;
1128                                                 if ( reference->getTargetBinding() == ObjectFile::Reference::kUnboundByName ) {
1129                                                         if ( strcmp(reference->getTargetName(), name) == 0 ) {
1130                                                                 fprintf(stderr, "      %s in %s\n", atom->getDisplayName(), pathLeafName(atom->getFile()->getPath()));
1131                                                                 foundAtomReference = true;
1132                                                         }
1133                                                 }
1134                                                 if ( reference->getFromTargetBinding() == ObjectFile::Reference::kUnboundByName ) {
1135                                                         if ( strcmp(reference->getFromTargetName(), name) == 0 ) {
1136                                                                 fprintf(stderr, "      %s in %s\n", atom->getDisplayName(), pathLeafName(atom->getFile()->getPath()));
1137                                                                 foundAtomReference = true;
1138                                                         }
1139                                                 }
1140                                         }
1141                                 }
1142                                 // scan command line options
1143                                 if  ( !foundAtomReference && fOptions.hasExportRestrictList() && fOptions.shouldExport(name) ) {
1144                                         fprintf(stderr, "     -exported_symbols_list command line option\n");
1145                                         ++unresolvableExportsCount;
1146                                 }
1147                         }
1148                 }
1149                 if ( doError )
1150                         throw "symbol(s) not found";
1151         }
1152
1153         // for each tentative definition in symbol table look for dylib that exports same symbol name
1154         if ( fGlobalSymbolTable.hasExternalTentativeDefinitions() ) {
1155                 for (SymbolTable::Mapper::iterator it=fGlobalSymbolTable.begin(); it != fGlobalSymbolTable.end(); ++it) {
1156                         ObjectFile::Atom* atom = it->second;
1157                         if ( (atom != NULL) && (atom->getDefinitionKind()==ObjectFile::Atom::kTentativeDefinition)
1158                                 && (atom->getScope() == ObjectFile::Atom::scopeGlobal) ) {
1159                                 // look for dylibs that export same name as used by global tentative definition
1160                                 addJustInTimeAtoms(atom->getName(), true, false, false);
1161                         }
1162                 }
1163         }
1164
1165
1166         // record any overrides of weak symbols any linked dylib
1167         for (SymbolTable::Mapper::iterator it=fGlobalSymbolTable.begin(); it != fGlobalSymbolTable.end(); ++it) {
1168                 ObjectFile::Atom* atom = it->second;
1169                 if ( (atom != NULL) && (atom->getDefinitionKind()==ObjectFile::Atom::kRegularDefinition)
1170                         && (atom->getScope() == ObjectFile::Atom::scopeGlobal) ) {
1171                         const char* name = atom->getName();
1172                         //fprintf(stderr, "looking for dylibs with a weak %s\n", name);
1173                         // look for dylibs with weak exports of the same name
1174                         for (InstallNameToReader::iterator it=fDylibMap.begin(); it != fDylibMap.end(); it++) {
1175                                 ObjectFile::Reader* reader = it->second;
1176                                 if ( reader->hasWeakExternals() ) {
1177                                         std::vector<class ObjectFile::Atom*>* dylibAtoms = reader->getJustInTimeAtomsFor(name);
1178                                         if ( dylibAtoms != NULL ) {
1179                                                 //fprintf(stderr, "addJustInTimeAtoms(%s) => found in file %s\n", name, reader->getPath() );
1180                                                 // if this is a weak definition in a dylib
1181                                                 if ( (dylibAtoms->at(0)->getDefinitionKind() == ObjectFile::Atom::kExternalWeakDefinition) ) {
1182                                                         fRegularDefAtomsThatOverrideADylibsWeakDef.insert(atom);
1183                                                 }
1184                                         }
1185                                 }
1186                         }
1187                 }
1188         }
1189
1190 }
1191
1192
1193
1194 std::vector<class ObjectFile::Atom*>* Linker::addJustInTimeAtoms(const char* name, bool searchDylibs, bool searchArchives, bool okToMakeProxy)
1195 {
1196         //fprintf(stderr, "addJustInTimeAtoms(%s, searchDylibs=%d, searchArchives=%d)\n", name, searchDylibs, searchArchives );
1197         // when creating final linked image, writer gets first chance
1198         if ( fOptions.outputKind() != Options::kObjectFile ) {
1199                 std::vector<class ObjectFile::Atom*>* atoms = fOutputFile->getJustInTimeAtomsFor(name);
1200                 if ( atoms != NULL ) {
1201                         this->addAtoms(*atoms);
1202                         //fprintf(stderr, "addJustInTimeAtoms(%s) => found in file %s\n", name, fOutputFile->getPath() );
1203                         return atoms;  // found a definition, no need to search anymore
1204                 }
1205         }
1206
1207         // give readers a chance
1208         for (std::vector<class ObjectFile::Reader*>::iterator it=fInputFiles.begin(); it != fInputFiles.end(); it++) {
1209                 ObjectFile::Reader* reader = *it;
1210                 if ( reader != NULL ) {
1211                         // if this reader is a static archive that has the symbol we need, pull in all atoms in that module
1212                         // if this reader is a dylib that exports the symbol we need, have it synthesize an atom for us.
1213                         //fprintf(stderr, "addJustInTimeAtoms(%s), looking in reader %s\n", name, reader->getPath() );
1214                         bool isDylibReader = (reader->getInstallPath() != NULL);
1215                         if ( isDylibReader ? searchDylibs : searchArchives ) {
1216                                 std::vector<class ObjectFile::Atom*>* atoms = reader->getJustInTimeAtomsFor(name);
1217                                 if ( atoms != NULL ) {
1218                                         this->addAtoms(*atoms);
1219                                         //fprintf(stderr, "addJustInTimeAtoms(%s) => found in file %s\n", name, reader->getPath() );
1220                                         if ( !isDylibReader && fOptions.readerOptions().fTraceArchives ) {
1221                                                 logArchive(reader);
1222                                         }
1223                                         // if this is a weak definition in a dylib
1224                                         if ( isDylibReader && (atoms->size() == 1) && (atoms->at(0)->getDefinitionKind() == ObjectFile::Atom::kExternalWeakDefinition) ) {
1225                                                 // keep looking for a non-weak definition
1226                                         }
1227                                         else {
1228                                                 // found a definition, no need to search anymore
1229                                                 return atoms;
1230                                         }
1231                                 }
1232                         }
1233                 }
1234         }
1235
1236         // for two level namesapce, give all implicitly link dylibs a chance
1237         if ( fOptions.nameSpace() == Options::kTwoLevelNameSpace ) {
1238                 for (InstallNameToReader::iterator it=fDylibMap.begin(); it != fDylibMap.end(); it++) {
1239                         if ( it->second->implicitlyLinked() ) {
1240                                 //fprintf(stderr, "addJustInTimeAtoms(%s), looking in implicitly linked %s\n", name, it->second->getPath() );
1241                                 std::vector<class ObjectFile::Atom*>* atoms = it->second->getJustInTimeAtomsFor(name);
1242                                 if ( atoms != NULL ) {
1243                                         this->addAtoms(*atoms);
1244                                         //fprintf(stderr, "addJustInTimeAtoms(%s) => found in file %s\n", name, reader->getPath() );
1245                                         // if this is a weak definition in a dylib
1246                                         if ( (atoms->size() == 1) && (atoms->at(0)->getDefinitionKind() == ObjectFile::Atom::kExternalWeakDefinition) ) {
1247                                                 // keep looking for a non-weak definition
1248                                         }
1249                                         else {
1250                                                 // found a definition, no need to search anymore
1251                                                 return atoms;
1252                                         }
1253                                 }
1254                         }
1255                 }
1256         }
1257
1258         // for flat namespace, give indirect dylibs
1259         if ( fOptions.nameSpace() != Options::kTwoLevelNameSpace ) {
1260                 for (InstallNameToReader::iterator it=fDylibMap.begin(); it != fDylibMap.end(); it++) {
1261                         if ( ! it->second->explicitlyLinked() ) {
1262                                 std::vector<class ObjectFile::Atom*>* atoms = it->second->getJustInTimeAtomsFor(name);
1263                                 if ( atoms != NULL ) {
1264                                         this->addAtoms(*atoms);
1265                                         //fprintf(stderr, "addJustInTimeAtoms(%s) => found in file %s\n", name, reader->getPath() );
1266                                         return atoms;  // found a definition, no need to search anymore
1267                                 }
1268                         }
1269                 }
1270         }
1271
1272         // writer creates a proxy in two cases:
1273         // 1) ld -r is being used to create a .o file
1274         // 2) -undefined dynamic_lookup is being used
1275         // 3) -U _foo is being used
1276         // 4) x86_64 kext bundle is being created
1277         if (    (fOptions.outputKind() == Options::kObjectFile)
1278                 ||  ((fOptions.undefinedTreatment() != Options::kUndefinedError) && okToMakeProxy)
1279                 ||      (fOptions.someAllowedUndefines() && okToMakeProxy)
1280                 ||  (fOptions.outputKind() == Options::kKextBundle) ) {
1281                 ObjectFile::Atom* atom = fOutputFile->getUndefinedProxyAtom(name);
1282                 if ( atom != NULL ) {
1283                         this->addAtom(*atom);
1284                         return NULL;
1285                 }
1286         }
1287         //fprintf(stderr, "addJustInTimeAtoms(%s) => not found\n", name);
1288         return NULL;
1289 }
1290
1291 void Linker::resolve(ObjectFile::Reference* reference)
1292 {
1293         // look in global symbol table
1294         const char* targetName = reference->getTargetName();
1295         ObjectFile::Atom* target = fGlobalSymbolTable.find(targetName);
1296         if ( target == NULL ) {
1297                 throwf("unexpected undefined symbol: %s", targetName);
1298         }
1299         reference->setTarget(*target, reference->getTargetOffset());
1300 }
1301
1302 void Linker::resolveFrom(ObjectFile::Reference* reference)
1303 {
1304         // handle references that have two (from and to) targets
1305         const char* fromTargetName = reference->getFromTargetName();
1306         ObjectFile::Atom* fromTarget = fGlobalSymbolTable.find(fromTargetName);
1307         if ( fromTarget == NULL ) {
1308                 throwf("unexpected undefined symbol: %s", fromTargetName);
1309         }
1310         reference->setFromTarget(*fromTarget);
1311 }
1312
1313
1314 void Linker::resolveReferences()
1315 {
1316         // note: the atom list may grow during this loop as libraries supply needed atoms
1317         for (unsigned int j=0; j < fAllAtoms.size(); ++j) {
1318                 ObjectFile::Atom* atom = fAllAtoms[j];
1319                 std::vector<class ObjectFile::Reference*>& references = atom->getReferences();
1320                 for (std::vector<ObjectFile::Reference*>::iterator it=references.begin(); it != references.end(); it++) {
1321                         ObjectFile::Reference* reference = *it;
1322                         if ( reference->getTargetBinding() == ObjectFile::Reference::kUnboundByName )
1323                                 this->resolve(reference);
1324                         if ( reference->getFromTargetBinding() == ObjectFile::Reference::kUnboundByName )
1325                                 this->resolveFrom(reference);
1326                 }
1327         }
1328 }
1329
1330
1331 // used to remove stabs associated with atoms that won't be in output file
1332 class NotInSet
1333 {
1334 public:
1335         NotInSet(std::set<ObjectFile::Atom*>& theSet) : fSet(theSet) {}
1336
1337         bool operator()(const ObjectFile::Reader::Stab& stab) const {
1338                 if ( stab.atom == NULL )
1339                         return false;   // leave stabs that are not associated with any atome
1340                 else
1341                         return ( fSet.count(stab.atom) == 0 );
1342         }
1343
1344 private:
1345         std::set<ObjectFile::Atom*>& fSet;
1346 };
1347
1348
1349 class NotLive
1350 {
1351 public:
1352         NotLive(std::set<ObjectFile::Atom*>& set) : fLiveAtoms(set)  {}
1353
1354         bool operator()(ObjectFile::Atom*& atom) const {
1355                 //if ( fLiveAtoms.count(atom) == 0 )
1356                 //      fprintf(stderr, "dead strip %s\n", atom->getDisplayName());
1357                 return ( fLiveAtoms.count(atom) == 0 );
1358         }
1359 private:
1360         std::set<ObjectFile::Atom*>& fLiveAtoms;
1361 };
1362
1363
1364 void Linker::addJustInTimeAtomsAndMarkLive(const char* name)
1365 {
1366         //fprintf(stderr, "addJustInTimeAtomsAndMarkLive(%s)\n", name);
1367         std::vector<class ObjectFile::Atom*>* atoms = this->addJustInTimeAtoms(name, true, true, true);
1368         if ( atoms != NULL ) {
1369                 if ( fOptions.allGlobalsAreDeadStripRoots() ) {
1370                         for (std::vector<ObjectFile::Atom*>::iterator it=atoms->begin(); it != atoms->end(); it++) {
1371                                 ObjectFile::Atom* atom = *it;
1372                                 if ( atom->getScope() ==  ObjectFile::Atom::scopeGlobal ) {
1373                                         WhyLiveBackChain rootChain;
1374                                         rootChain.previous = NULL;
1375                                         rootChain.referer = atom;
1376                                         this->markLive(*atom, &rootChain);
1377                                 }
1378                         }
1379                 }
1380                 delete atoms;
1381         }
1382 }
1383
1384 void Linker::markLive(ObjectFile::Atom& atom, struct Linker::WhyLiveBackChain* previous)
1385 {
1386         //fprintf(stderr, "markLive(%p)\n", &atom);
1387         if ( fLiveAtoms.count(&atom) == 0 ) {
1388                 // if -why_live cares about this symbol, then dump chain
1389                 if ( (previous->referer != NULL) && fOptions.printWhyLive(previous->referer->getDisplayName()) ) {
1390                         int depth = 0;
1391                         for(WhyLiveBackChain* p = previous; p != NULL; p = p->previous, ++depth) {
1392                                 for(int i=depth; i > 0; --i)
1393                                         fprintf(stderr, "  ");
1394                                 fprintf(stderr, "%p %s from %s\n", p->referer, p->referer->getDisplayName(), p->referer->getFile()->getPath());
1395                         }
1396                 }
1397                 // set up next chain
1398                 WhyLiveBackChain thisChain;
1399                 thisChain.previous = previous;
1400                 // this atom is live
1401                 fLiveAtoms.insert(&atom);
1402                 // update total size info (except for __ZEROPAGE atom)
1403                 if ( atom.getSegment().isContentReadable() ) {
1404                         fTotalSize += atom.getSize();
1405                         if ( atom.isZeroFill() )
1406                                 fTotalZeroFillSize += atom.getSize();
1407                 }
1408                 // and all atoms it references
1409                 std::vector<class ObjectFile::Reference*>& references = atom.getReferences();
1410                 for (std::vector<ObjectFile::Reference*>::iterator it=references.begin(); it != references.end(); it++) {
1411                         ObjectFile::Reference* reference = *it;
1412                         if ( reference->getTargetBinding() == ObjectFile::Reference::kUnboundByName ) {
1413                                 // look in global symbol table
1414                                 const char* targetName = reference->getTargetName();
1415                                 ObjectFile::Atom* target = fGlobalSymbolTable.find(targetName);
1416                                 if ( (target == NULL) || (target->getDefinitionKind() == ObjectFile::Atom::kTentativeDefinition) ) {
1417                                         // load archives or dylibs
1418                                         this->addJustInTimeAtomsAndMarkLive(targetName);
1419                                 }
1420                                 // look again
1421                                 target = fGlobalSymbolTable.find(targetName);
1422                                 if ( target != NULL ) {
1423                                         reference->setTarget(*target, reference->getTargetOffset());
1424                                 }
1425                                 else {
1426                                         // mark as undefined, for later error processing
1427                                         fAtomsWithUnresolvedReferences.push_back(&atom);
1428                                         fGlobalSymbolTable.require(targetName);
1429                                 }
1430                         }
1431                         switch ( reference->getTargetBinding() ) {
1432                                 case ObjectFile::Reference::kBoundDirectly:
1433                                 case ObjectFile::Reference::kBoundByName:
1434                                         thisChain.referer = &reference->getTarget();
1435                                         markLive(reference->getTarget(), &thisChain);
1436                                         break;
1437                                 case ObjectFile::Reference::kDontBind:
1438                                 case ObjectFile::Reference::kUnboundByName:
1439                                         // do nothing
1440                                         break;
1441                         }
1442                         // do the same as above, for "from target"
1443                         if ( reference->getFromTargetBinding() == ObjectFile::Reference::kUnboundByName ) {
1444                                 // look in global symbol table
1445                                 const char* targetName = reference->getFromTargetName();
1446                                 ObjectFile::Atom* target = fGlobalSymbolTable.find(targetName);
1447                                 if ( (target == NULL) || (target->getDefinitionKind() == ObjectFile::Atom::kTentativeDefinition) ) {
1448                                         // load archives or dylibs
1449                                         this->addJustInTimeAtomsAndMarkLive(targetName);
1450                                 }
1451                                 // look again
1452                                 target = fGlobalSymbolTable.find(targetName);
1453                                 if ( target != NULL ) {
1454                                         reference->setFromTarget(*target);
1455                                 }
1456                                 else {
1457                                         // mark as undefined, for later error processing
1458                                         fGlobalSymbolTable.require(targetName);
1459                                 }
1460                         }
1461                         switch ( reference->getFromTargetBinding() ) {
1462                                 case ObjectFile::Reference::kBoundDirectly:
1463                                 case ObjectFile::Reference::kBoundByName:
1464                                         thisChain.referer = &reference->getFromTarget();
1465                                         markLive(reference->getFromTarget(), &thisChain);
1466                                         break;
1467                                 case ObjectFile::Reference::kUnboundByName:
1468                                 case ObjectFile::Reference::kDontBind:
1469                                         // do nothing
1470                                         break;
1471                         }
1472                 }
1473         }
1474 }
1475
1476
1477 void Linker::addLiveRoot(const char* name)
1478 {
1479         ObjectFile::Atom* target = fGlobalSymbolTable.find(name);
1480         if ( target == NULL ) {
1481                 this->addJustInTimeAtomsAndMarkLive(name);
1482                 target = fGlobalSymbolTable.find(name);
1483         }
1484         if ( target != NULL )
1485                 fLiveRootAtoms.insert(target);
1486 }
1487
1488 void Linker::moveToFrontOfSection(ObjectFile::Atom* atom)
1489 {
1490         // check if already moved to front
1491         if ( fInitializerAtoms.find(atom) == fInitializerAtoms.end() ) {
1492                 // don't re-order initializers from .o files without MH_SUBSECTIONS_VIA_SYMBOLS
1493                 // since that could make all atoms in the file look like initializers
1494                 if ( atom->getFile()->canScatterAtoms() ) {
1495                         //fprintf(stdout, "marking as initializer: %s\n", atom->getDisplayName());
1496                         fInitializerAtoms.insert(atom);
1497                         // mark all functions that this function references
1498                         std::vector<class ObjectFile::Reference*>& references = atom->getReferences();
1499                         for (std::vector<ObjectFile::Reference*>::const_iterator rit=references.begin(); rit != references.end(); rit++) {
1500                                 ObjectFile::Atom* childAtom = &((*rit)->getTarget());
1501                                 if ( childAtom != NULL ) {
1502                                         if ( (*rit)->isBranch() ) {
1503                                                 this->moveToFrontOfSection(childAtom);
1504                                         }
1505                                         else if ( (childAtom->getName() != NULL) && (strncmp(childAtom->getName(), "___tcf_", 7) == 0) ) {
1506                                                 //fprintf(stdout, "marking as terminator: %s\n", childAtom->getDisplayName());
1507                                                 fTerminatorAtoms.insert(childAtom);
1508                                         }
1509                                 }
1510                         }
1511                 }
1512         }
1513 }
1514
1515 void Linker::deadStripResolve()
1516 {
1517         // add main() to live roots
1518         ObjectFile::Atom* entryPoint = this->entryPoint(false);
1519         if ( entryPoint != NULL )
1520                 fLiveRootAtoms.insert(entryPoint);
1521
1522         // add dyld_stub_binding_helper/dyld_stub_binder to live roots
1523         ObjectFile::Atom* dyldHelper = this->dyldClassicHelper();
1524         if ( dyldHelper != NULL )
1525                 fLiveRootAtoms.insert(dyldHelper);
1526         dyldHelper = this->dyldCompressedHelper();
1527         if ( dyldHelper != NULL )
1528                 fLiveRootAtoms.insert(dyldHelper);
1529
1530         // if using lazy dylib loading, add dyld_lazy_dylib_stub_binding_helper() to live roots
1531         if ( fOptions.usingLazyDylibLinking() ) {
1532                 ObjectFile::Atom* dyldLazyDylibHelper = this->dyldLazyLibraryHelper();
1533                 if ( dyldLazyDylibHelper != NULL )
1534                         fLiveRootAtoms.insert(dyldLazyDylibHelper);
1535         }
1536
1537         // add -exported_symbols_list, -init, and -u entries to live roots
1538         std::vector<const char*>& initialUndefines = fOptions.initialUndefines();
1539         for (std::vector<const char*>::iterator it=initialUndefines.begin(); it != initialUndefines.end(); it++)
1540                 addLiveRoot(*it);
1541
1542         // if -exported_symbols_list that has wildcards, we need to find all matches and make them the roots
1543         // <rdar://problem/5524973>
1544         if ( fOptions.hasWildCardExportRestrictList() ) {
1545                 for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
1546                         ObjectFile::Atom* atom = *it;
1547                         if ( (atom->getScope() == ObjectFile::Atom::scopeGlobal)
1548                                 && (fDeadAtoms.count(atom) == 0)
1549                                 && fOptions.shouldExport(atom->getName()) )
1550                                         fLiveRootAtoms.insert(atom);
1551                 }
1552         }
1553
1554         // in some cases, every global scope atom in initial .o files is a root
1555         if ( fOptions.allGlobalsAreDeadStripRoots() ) {
1556                 for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
1557                         ObjectFile::Atom* atom = *it;
1558                         if ( (atom->getScope() == ObjectFile::Atom::scopeGlobal) && (fDeadAtoms.count(atom) == 0) )
1559                                 fLiveRootAtoms.insert(atom);
1560                 }
1561         }
1562
1563         // mark all roots as live, and all atoms they reference
1564         for (std::set<ObjectFile::Atom*>::iterator it=fLiveRootAtoms.begin(); it != fLiveRootAtoms.end(); it++) {
1565                 WhyLiveBackChain rootChain;
1566                 rootChain.previous = NULL;
1567                 rootChain.referer = *it;
1568                 markLive(**it, &rootChain);
1569         }
1570
1571         // it is possible that there are unresolved references that can be resolved now
1572         // this can happen if the first reference to a common symbol in an archive.
1573         // common symbols are not in the archive TOC, but the .o could have been pulled in later.
1574         // <rdar://problem/4654131> ld64 while linking cc1 [ when dead_strip is ON]
1575         for (std::vector<ObjectFile::Atom*>::iterator it=fAtomsWithUnresolvedReferences.begin(); it != fAtomsWithUnresolvedReferences.end(); it++) {
1576                 std::vector<class ObjectFile::Reference*>& references = (*it)->getReferences();
1577                 for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); rit++) {
1578                         ObjectFile::Reference* reference = *rit;
1579                         if ( reference->getTargetBinding() == ObjectFile::Reference::kUnboundByName ) {
1580                                 ObjectFile::Atom* target = fGlobalSymbolTable.find(reference->getTargetName());
1581                                 if ( target != NULL ) {
1582                                         reference->setTarget(*target, reference->getTargetOffset());
1583                                         fLiveAtoms.insert(target);
1584                                         // by just adding this atom to fLiveAtoms set, we are assuming it has no
1585                                         // references, which is true for commons.
1586                                         if ( target->getDefinitionKind() != ObjectFile::Atom::kTentativeDefinition )
1587                                                 warning("internal error %s is not a tentative definition", target->getDisplayName());
1588                                 }
1589                         }
1590                         if ( reference->getFromTargetBinding() == ObjectFile::Reference::kUnboundByName ) {
1591                                 ObjectFile::Atom* target = fGlobalSymbolTable.find(reference->getFromTargetName());
1592                                 if ( target != NULL ) {
1593                                         reference->setFromTarget(*target);
1594                                         fLiveAtoms.insert(target);
1595                                         // by just adding this atom to fLiveAtoms set, we are assuming it has no
1596                                         // references, which is true for commons.
1597                                         if ( target->getDefinitionKind() != ObjectFile::Atom::kTentativeDefinition )
1598                                                 warning("internal error %s is not a tentative definition", target->getDisplayName());
1599                                 }
1600                         }
1601                 }
1602         }
1603
1604         // It is possible that some weak symbols were overridden by lazily load objects from archives
1605         // and we have some atoms that still refer to the overridden ones.
1606         // In that case we need to go back and rebind
1607         if ( fAtomsOverriddenByLateLoads.size() > 0 ) {
1608                 for (std::set<ObjectFile::Atom*>::iterator it=fLiveAtoms.begin(); it != fLiveAtoms.end(); ++it) {
1609                         ObjectFile::Atom* atom = *it;
1610                         std::vector<class ObjectFile::Reference*>& references = atom->getReferences();
1611                         for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); ++rit) {
1612                                 ObjectFile::Reference* reference = *rit;
1613                                 ObjectFile::Atom* toTarget = &reference->getTarget();
1614                                 if ( fAtomsOverriddenByLateLoads.count(toTarget) ) {
1615                                         //fprintf(stderr, "change reference in %p from %p to %p\n", atom, toTarget, fGlobalSymbolTable.find(toTarget->getName()));
1616                                         reference->setTarget(*fGlobalSymbolTable.find(toTarget->getName()), reference->getTargetOffset());
1617                                 }
1618                                 ObjectFile::Atom* fromTarget = &reference->getFromTarget();
1619                                 if ( (fromTarget != NULL) && fAtomsOverriddenByLateLoads.count(fromTarget) ) {
1620                                         //fprintf(stderr, "change from reference in %p from %p to %p\n", atom, fromTarget, fGlobalSymbolTable.find(fromTarget->getName()));
1621                                         reference->setTarget(*fGlobalSymbolTable.find(fromTarget->getName()), reference->getFromTargetOffset());
1622                                 }
1623                         }
1624                 }
1625
1626                 // make sure overriders are live if the atom they overrid was live
1627                 for (std::set<ObjectFile::Atom*>::iterator it=fAtomsOverriddenByLateLoads.begin(); it != fAtomsOverriddenByLateLoads.end(); ++it) {
1628                         ObjectFile::Atom* overriderAtom = *it;
1629                         if ( fLiveAtoms.count(overriderAtom) ) {
1630                                 WhyLiveBackChain rootChain;
1631                                 rootChain.previous = NULL;
1632                                 rootChain.referer = *it;
1633                                 markLive(*fGlobalSymbolTable.find(overriderAtom->getName()), &rootChain);
1634                         }
1635                 }
1636
1637                 // remove overridden atoms from fLiveAtoms
1638                 fAllAtoms.erase(std::remove_if(fAllAtoms.begin(), fAllAtoms.end(), InSet(fAtomsOverriddenByLateLoads)), fAllAtoms.end());
1639                 fAtomsOverriddenByLateLoads.clear();
1640                 // remove dead atoms from fLiveAtoms
1641                 fAllAtoms.erase(std::remove_if(fAllAtoms.begin(), fAllAtoms.end(), InSet(fDeadAtoms)), fAllAtoms.end());
1642         }
1643
1644         // now remove all non-live atoms from fAllAtoms
1645         fAllAtoms.erase(std::remove_if(fAllAtoms.begin(), fAllAtoms.end(), NotLive(fLiveAtoms)), fAllAtoms.end());
1646 }
1647
1648 void Linker::checkObjC()
1649 {
1650         // check dylibs
1651         switch ( fCurrentObjCConstraint ) {
1652                 case ObjectFile::Reader::kObjcNone:
1653                         // can link against any dylib
1654                         break;
1655                 case ObjectFile::Reader::kObjcRetainRelease:
1656                         // cannot link against GC-only dylibs
1657                         for (InstallNameToReader::iterator it=fDylibMap.begin(); it != fDylibMap.end(); it++) {
1658                                 if ( it->second->explicitlyLinked() ) {
1659                                         if ( it->second->getObjCConstraint() == ObjectFile::Reader::kObjcGC )
1660                                                 throwf("this linkage unit uses Retain/Release.  It cannot link against the GC-only dylib: %s", it->second->getPath());
1661                                 }
1662                         }
1663                         break;
1664                 case ObjectFile::Reader::kObjcRetainReleaseOrGC:
1665                         // can link against GC or RR dylibs
1666                         break;
1667                 case ObjectFile::Reader::kObjcGC:
1668                         // cannot link against RR-only dylibs
1669                         for (InstallNameToReader::iterator it=fDylibMap.begin(); it != fDylibMap.end(); it++) {
1670                                 if ( it->second->explicitlyLinked() ) {
1671                                         if ( it->second->getObjCConstraint() == ObjectFile::Reader::kObjcRetainRelease )
1672                                                 throwf("this linkage unit requires GC.  It cannot link against Retain/Release dylib: %s", it->second->getPath());
1673                                 }
1674                         }
1675                         break;
1676         }
1677
1678         // synthesize __OBJC __image_info atom if needed
1679         if ( fCurrentObjCConstraint != ObjectFile::Reader::kObjcNone ) {
1680                 this->addAtom(fOutputFile->makeObjcInfoAtom(fCurrentObjCConstraint, fObjcReplacmentClasses));
1681         }
1682 }
1683
1684
1685 static uint8_t pcRelKind(cpu_type_t arch)
1686 {
1687         switch ( arch ) {
1688                 case CPU_TYPE_POWERPC:
1689                         return ppc::kPointerDiff32;
1690                 case CPU_TYPE_POWERPC64:
1691                         return ppc64::kPointerDiff32;
1692                 case CPU_TYPE_I386:
1693                         return x86::kPointerDiff;
1694                 case CPU_TYPE_X86_64:
1695                         return x86_64::kPointerDiff32;
1696                 case CPU_TYPE_ARM:
1697                         return arm::kPointerDiff;
1698         }
1699         throw "uknown architecture";
1700 }
1701
1702 typedef uint8_t* (*oldcreatedof_func_t) (const char*, cpu_type_t, unsigned int, const char*[], const char*[], uint64_t offsetsInDOF[], size_t* size);
1703 typedef uint8_t* (*createdof_func_t)(cpu_type_t, unsigned int, const char*[], unsigned int, const char*[], const char*[], uint64_t offsetsInDOF[], size_t* size);
1704
1705
1706 void Linker::processDTrace()
1707 {
1708         // only make __dof section in final linked images
1709         if ( fOptions.outputKind() == Options::kObjectFile )
1710                 return;
1711
1712         // scan all atoms looking for dtrace probes
1713         std::vector<DTraceProbeInfo>                                            probeSites;
1714         std::vector<DTraceProbeInfo>                                            isEnabledSites;
1715         std::map<const ObjectFile::Atom*,CStringSet>            atomToDtraceTypes;
1716         for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); ++it) {
1717                 ObjectFile::Atom* atom = *it;
1718                 std::vector<class ObjectFile::Reference*>& references = atom->getReferences();
1719                 for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); ++rit) {
1720                         ObjectFile::Reference* ref = *rit;
1721                         if ( ref->getTargetBinding() == ObjectFile::Reference::kDontBind ) {
1722                                 const char* probeName = ref->getTargetName();
1723                                 if ( probeName != NULL ) {
1724                                         uint32_t offsetInAtom = ref->getFixUpOffset();
1725                                         if ( strncmp(probeName, "___dtrace_probe$", 16) == 0 )
1726                                                 probeSites.push_back(DTraceProbeInfo(atom, offsetInAtom, probeName));
1727                                         else if ( strncmp(probeName, "___dtrace_isenabled$", 20) == 0 )
1728                                                 isEnabledSites.push_back(DTraceProbeInfo(atom, offsetInAtom, probeName));
1729                                         else if ( strncmp(probeName, "___dtrace_", 10) == 0 )
1730                                                 atomToDtraceTypes[atom].insert(probeName);
1731                                 }
1732                         }
1733                 }
1734         }
1735
1736         // if no probes, we're done
1737         if ( (probeSites.size() == 0) && (isEnabledSites.size() == 0) )
1738                 return;
1739
1740         // partition probes by provider name
1741         // The symbol names looks like:
1742         //      "___dtrace_probe$" provider-name "$" probe-name [ "$"... ]
1743         //      "___dtrace_isenabled$" provider-name "$" probe-name [ "$"... ]
1744         ProviderToProbes providerToProbes;
1745         std::vector<DTraceProbeInfo> emptyList;
1746         for(std::vector<DTraceProbeInfo>::iterator it = probeSites.begin(); it != probeSites.end(); ++it) {
1747                 // ignore probes in functions that were coalesed away rdar://problem/5628149
1748                 if ( fDeadAtoms.count((ObjectFile::Atom*)(it->atom)) == 0 ) {
1749                         const char* providerStart = &it->probeName[16];
1750                         const char* providerEnd = strchr(providerStart, '$');
1751                         if ( providerEnd != NULL ) {
1752                                 char providerName[providerEnd-providerStart+1];
1753                                 strlcpy(providerName, providerStart, providerEnd-providerStart+1);
1754                                 ProviderToProbes::iterator pos = providerToProbes.find(providerName);
1755                                 if ( pos == providerToProbes.end() ) {
1756                                         const char* dup = strdup(providerName);
1757                                         providerToProbes[dup] = emptyList;
1758                                 }
1759                                 providerToProbes[providerName].push_back(*it);
1760                         }
1761                 }
1762         }
1763         for(std::vector<DTraceProbeInfo>::iterator it = isEnabledSites.begin(); it != isEnabledSites.end(); ++it) {
1764                 // ignore probes in functions that were coalesed away rdar://problem/5628149
1765                 if ( fDeadAtoms.count((ObjectFile::Atom*)(it->atom)) == 0 ) {
1766                         const char* providerStart = &it->probeName[20];
1767                         const char* providerEnd = strchr(providerStart, '$');
1768                         if ( providerEnd != NULL ) {
1769                                 char providerName[providerEnd-providerStart+1];
1770                                 strlcpy(providerName, providerStart, providerEnd-providerStart+1);
1771                                 ProviderToProbes::iterator pos = providerToProbes.find(providerName);
1772                                 if ( pos == providerToProbes.end() ) {
1773                                         const char* dup = strdup(providerName);
1774                                         providerToProbes[dup] = emptyList;
1775                                 }
1776                                 providerToProbes[providerName].push_back(*it);
1777                         }
1778                 }
1779         }
1780
1781         // create a DOF section for each provider
1782         int dofIndex=1;
1783         CStringSet sectionNamesUsed;
1784         for(ProviderToProbes::iterator pit = providerToProbes.begin(); pit != providerToProbes.end(); ++pit, ++dofIndex) {
1785                 const char* providerName = pit->first;
1786                 const std::vector<DTraceProbeInfo>& probes = pit->second;
1787
1788                 // open library and find dtrace_create_dof()
1789                 void* handle = dlopen("/usr/lib/libdtrace.dylib", RTLD_LAZY);
1790                 if ( handle == NULL )
1791                         throwf("couldn't dlopen() /usr/lib/libdtrace.dylib: %s", dlerror());
1792                 createdof_func_t pCreateDOF = (createdof_func_t)dlsym(handle, "dtrace_ld_create_dof");
1793                 if ( pCreateDOF == NULL )
1794                         throwf("couldn't find \"dtrace_ld_create_dof\" in /usr/lib/libdtrace.dylib: %s", dlerror());
1795                 // build list of typedefs/stability infos for this provider
1796                 CStringSet types;
1797                 for(std::vector<DTraceProbeInfo>::const_iterator it = probes.begin(); it != probes.end(); ++it) {
1798                         std::map<const ObjectFile::Atom*,CStringSet>::iterator pos = atomToDtraceTypes.find(it->atom);
1799                         if ( pos != atomToDtraceTypes.end() ) {
1800                                 for(CStringSet::iterator sit = pos->second.begin(); sit != pos->second.end(); ++sit) {
1801                                         const char* providerStart = strchr(*sit, '$')+1;
1802                                         const char* providerEnd = strchr(providerStart, '$');
1803                                         if ( providerEnd != NULL ) {
1804                                                 char aProviderName[providerEnd-providerStart+1];
1805                                                 strlcpy(aProviderName, providerStart, providerEnd-providerStart+1);
1806                                                 if ( strcmp(aProviderName, providerName) == 0 )
1807                                                         types.insert(*sit);
1808                                         }
1809                                 }
1810                         }
1811                 }
1812                 int typeCount = types.size();
1813                 const char* typeNames[typeCount];
1814                 //fprintf(stderr, "types for %s:\n", providerName);
1815                 uint32_t index = 0;
1816                 for(CStringSet::iterator it = types.begin(); it != types.end(); ++it) {
1817                         typeNames[index] = *it;
1818                         //fprintf(stderr, "\t%s\n", *it);
1819                         ++index;
1820                 }
1821
1822                 // build list of probe/isenabled sites
1823                 const uint32_t probeCount = probes.size();
1824                 const char* probeNames[probeCount];
1825                 const char* funtionNames[probeCount];
1826                 uint64_t offsetsInDOF[probeCount];
1827                 index = 0;
1828                 for(std::vector<DTraceProbeInfo>::const_iterator it = probes.begin(); it != probes.end(); ++it) {
1829                         probeNames[index] = it->probeName;
1830                         funtionNames[index] = it->atom->getName();
1831                         offsetsInDOF[index] = 0;
1832                         ++index;
1833                 }
1834                 //fprintf(stderr, "calling libtrace to create DOF\n");
1835                 //for(uint32_t i=0; i < probeCount; ++i)
1836                 //      fprintf(stderr, "  [%u]\t %s\t%s\n", i, probeNames[i], funtionNames[i]);
1837                 // call dtrace library to create DOF section
1838                 size_t dofSectionSize;
1839                 uint8_t* p = (*pCreateDOF)(fArchitecture, typeCount, typeNames, probeCount, probeNames, funtionNames, offsetsInDOF, &dofSectionSize);
1840                 if ( p != NULL ) {
1841                         char sectionName[18];
1842                         strcpy(sectionName, "__dof_");
1843                         strlcpy(&sectionName[6], providerName, 10);
1844                         // create unique section name so each DOF is in its own section
1845                         if ( sectionNamesUsed.count(sectionName) != 0 ) {
1846                                 sectionName[15] = '0';
1847                                 sectionName[16] = '\0';
1848                                 while ( sectionNamesUsed.count(sectionName) != 0 )
1849                                         ++sectionName[15];
1850                         }
1851                         sectionNamesUsed.insert(sectionName);
1852                         char symbolName[strlen(providerName)+64];
1853                         sprintf(symbolName, "__dtrace_dof_for_provider_%s", providerName);
1854                         opaque_section::Reader* reader = new opaque_section::Reader("__TEXT", sectionName,
1855                                                                                                         "dtrace", p, dofSectionSize, fNextInputOrdinal, symbolName);
1856                         fNextInputOrdinal += dofSectionSize;
1857                         // add references
1858                         for (uint32_t i=0; i < probeCount; ++i) {
1859                                 uint64_t offset = offsetsInDOF[i];
1860                                 //fprintf(stderr, "%s offset[%d]=0x%08llX\n", providerName, i, offset);
1861                                 if ( offset > dofSectionSize )
1862                                         throwf("offsetsInDOF[i]=%0llX > dofSectionSize=%0lX\n", i, offset, dofSectionSize);
1863                                 reader->addSectionReference(pcRelKind(fArchitecture), offset, probes[i].atom, probes[i].offset, reader->getAtoms()[0], 0);
1864                         }
1865                         this->addAtoms(reader->getAtoms());
1866                 }
1867                 else {
1868                         throw "error creating dtrace DOF section";
1869                 }
1870         }
1871 }
1872
1873
1874 static bool matchesObjectFile(ObjectFile::Atom* atom, const char* objectFileLeafName)
1875 {
1876         if ( objectFileLeafName == NULL )
1877                 return true;
1878         const char* atomFullPath = atom->getFile()->getPath();
1879         const char* lastSlash = strrchr(atomFullPath, '/');
1880         if ( lastSlash != NULL ) {
1881                 if ( strcmp(&lastSlash[1], objectFileLeafName) == 0 )
1882                         return true;
1883         }
1884         else {
1885                 if ( strcmp(atomFullPath, objectFileLeafName) == 0 )
1886                         return true;
1887         }
1888         return false;
1889 }
1890
1891
1892 static bool usesAnonymousNamespace(const char* symbol)
1893 {
1894         return ( (strncmp(symbol, "__Z", 3) == 0) && (strstr(symbol, "_GLOBAL__N_") != NULL) );
1895 }
1896
1897
1898 //
1899 //  convert:
1900 //              __ZN20_GLOBAL__N__Z5main2v3barEv                                        =>  _ZN-3barEv
1901 //              __ZN37_GLOBAL__N_main.cxx_00000000_493A01A33barEv       =>  _ZN-3barEv
1902 //
1903 static void canonicalizeAnonymousName(const char* inSymbol, char outSymbol[])
1904 {
1905         const char* globPtr = strstr(inSymbol, "_GLOBAL__N_");
1906         while ( isdigit(*(--globPtr)) )
1907                 ; // loop
1908         char* endptr;
1909         unsigned long length = strtoul(globPtr+1, &endptr, 10);
1910         const char* globEndPtr = endptr + length;
1911         int startLen = globPtr-inSymbol+1;
1912         memcpy(outSymbol, inSymbol, startLen);
1913         outSymbol[startLen] = '-';
1914         strcpy(&outSymbol[startLen+1], globEndPtr);
1915 }
1916
1917
1918 ObjectFile::Atom* Linker::findAtom(const Options::OrderedSymbol& orderedSymbol)
1919 {
1920         ObjectFile::Atom* atom = fGlobalSymbolTable.find(orderedSymbol.symbolName);
1921         if ( atom != NULL ) {
1922                 if ( matchesObjectFile(atom, orderedSymbol.objectFileName) )
1923                         return atom;
1924         }
1925         else {
1926                 // slow case.  The requested symbol is not in symbol table, so might be static function
1927                 static SymbolTable::Mapper hashTableOfTranslationUnitScopedSymbols;
1928                 static SymbolTable::Mapper hashTableOfSymbolsWithAnonymousNamespace;
1929                 static bool built = false;
1930                 // build a hash_map the first time
1931                 if ( !built ) {
1932                         for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
1933                                 atom = *it;
1934                                 const char* name = atom->getName();
1935                                 if ( name != NULL) {
1936                                         if ( usesAnonymousNamespace(name) ) {
1937                                                 // symbol that uses anonymous namespace
1938                                                 char canonicalName[strlen(name)+2];
1939                                                 canonicalizeAnonymousName(name, canonicalName);
1940                                                 const char* hashName = strdup(canonicalName);
1941                                                 SymbolTable::Mapper::iterator pos = hashTableOfSymbolsWithAnonymousNamespace.find(hashName);
1942                                                 if ( pos == hashTableOfSymbolsWithAnonymousNamespace.end() )
1943                                                         hashTableOfSymbolsWithAnonymousNamespace[hashName] = atom;
1944                                                 else
1945                                                         hashTableOfSymbolsWithAnonymousNamespace[hashName] = NULL;      // collision, denote with NULL
1946                                         }
1947                                         else if ( atom->getScope() == ObjectFile::Atom::scopeTranslationUnit ) {
1948                                                 // static function or data
1949                                                 SymbolTable::Mapper::iterator pos = hashTableOfTranslationUnitScopedSymbols.find(name);
1950                                                 if ( pos == hashTableOfTranslationUnitScopedSymbols.end() )
1951                                                         hashTableOfTranslationUnitScopedSymbols[name] = atom;
1952                                                 else
1953                                                         hashTableOfTranslationUnitScopedSymbols[name] = NULL;   // collision, denote with NULL
1954                                         }
1955                                 }
1956                         }
1957                         //fprintf(stderr, "built hash table of %lu static functions\n", hashTableOfTranslationUnitScopedSymbols.size());
1958                         built = true;
1959                 }
1960
1961                 // look for name in hashTableOfTranslationUnitScopedSymbols
1962                 SymbolTable::Mapper::iterator pos = hashTableOfTranslationUnitScopedSymbols.find(orderedSymbol.symbolName);
1963                 if ( pos != hashTableOfTranslationUnitScopedSymbols.end() ) {
1964                         if ( (pos->second != NULL) && matchesObjectFile(pos->second, orderedSymbol.objectFileName) ) {
1965                                 //fprintf(stderr, "found %s in hash table\n", orderedSymbol.symbolName);
1966                                 return pos->second;
1967                         }
1968                         if ( pos->second == NULL )
1969                         // name is in hash table, but atom is NULL, so that means there are duplicates, so we use super slow way
1970                         for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
1971                                 atom = *it;
1972                                 if ( atom->getScope() == ObjectFile::Atom::scopeTranslationUnit ) {
1973                                         const char* name = atom->getName();
1974                                         if ( (name != NULL) && (strcmp(name, orderedSymbol.symbolName) == 0) ) {
1975                                                 if ( matchesObjectFile(atom, orderedSymbol.objectFileName) ) {
1976                                                         if ( fOptions.printOrderFileStatistics() )
1977                                                                 warning("%s specified in order_file but it exists in multiple .o files. "
1978                                                                                 "Prefix symbol with .o filename in order_file to disambiguate", orderedSymbol.symbolName);
1979                                                         return atom;
1980                                                 }
1981                                         }
1982                                 }
1983                         }
1984                 }
1985
1986                 // look for name in hashTableOfSymbolsWithAnonymousNamespace
1987                 if ( usesAnonymousNamespace(orderedSymbol.symbolName) ) {
1988                         // symbol that uses anonymous namespace
1989                         char canonicalName[strlen(orderedSymbol.symbolName)+2];
1990                         canonicalizeAnonymousName(orderedSymbol.symbolName, canonicalName);
1991                         SymbolTable::Mapper::iterator pos = hashTableOfSymbolsWithAnonymousNamespace.find(canonicalName);
1992                         if ( pos != hashTableOfSymbolsWithAnonymousNamespace.end() ) {
1993                                 if ( (pos->second != NULL) && matchesObjectFile(pos->second, orderedSymbol.objectFileName) ) {
1994                                         //fprintf(stderr, "found %s in anonymous namespace hash table\n", canonicalName);
1995                                         return pos->second;
1996                                 }
1997                                 if ( pos->second == NULL )
1998                                 // name is in hash table, but atom is NULL, so that means there are duplicates, so we use super slow way
1999                                 for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
2000                                         atom = *it;
2001                                         const char* name = atom->getName();
2002                                         if ( (name != NULL) && usesAnonymousNamespace(name) ) {
2003                                                 char canonicalAtomName[strlen(name)+2];
2004                                                 canonicalizeAnonymousName(name, canonicalAtomName);
2005                                                 if ( strcmp(canonicalAtomName, canonicalName) == 0 ) {
2006                                                         if ( matchesObjectFile(atom, orderedSymbol.objectFileName) ) {
2007                                                                 if ( fOptions.printOrderFileStatistics() )
2008                                                                         warning("%s specified in order_file but it exists in multiple .o files. "
2009                                                                                 "Prefix symbol with .o filename in order_file to disambiguate", orderedSymbol.symbolName);
2010                                                                 return atom;
2011                                                         }
2012                                                 }
2013                                         }
2014                                 }
2015                         }
2016                 }
2017         }
2018         return NULL;
2019 }
2020
2021
2022 void Linker::sortSections()
2023 {
2024         Section::assignIndexes();
2025 }
2026
2027
2028 //
2029 // Linker::sortAtoms()
2030 //
2031 // The purpose of this method is to take the graph of all Atoms and produce an ordered
2032 // sequence of atoms.  The constraints are that: 1) all Atoms of the same Segment must
2033 // be contiguous, 2)  all Atoms of the same Section must be contigous, 3) Atoms specified
2034 // in an order_file are seqenced as in the order_file and before Atoms not specified,
2035 // 4) Atoms in the same section from the same .o file should be contiguous and sequenced
2036 // in the same order they were in the .o file, 5) Atoms in the same Section but which came
2037 // from different .o files should be sequenced in the same order that the .o files
2038 // were passed to the linker (i.e. command line order).
2039 //
2040 // The way this is implemented is that the linker passes a "base ordinal" to each Reader
2041 // as it is constructed.  The reader should construct it Atoms so that calling getOrdinal()
2042 // on its atoms returns a contiguous range of values starting at the base ordinal.  Then
2043 // sorting is just sorting by section, then by ordinal.
2044 //
2045 // If an order_file is specified, it gets more complicated.  First, an override-ordinal map
2046 // is created.  It causes the sort routine to ignore the value returned by getOrdinal() and
2047 // use the override value instead.  Next some Atoms must be layed out consecutively
2048 // (e.g. hand written assembly that does not end with return, but rather falls into
2049 // the next label).  This is modeled in Readers via a "kFollowOn" reference.  The use of
2050 // kFollowOn refernces produces "clusters" of atoms that must stay together.
2051 // If an order_file tries to move one atom, it may need to move a whole cluster.  The
2052 // algorithm to do this models clusters using two maps.  The "starts" maps maps any
2053 // atom in a cluster to the first Atom in the cluster.  The "nexts" maps an Atom in a
2054 // cluster to the next Atom in the cluster.  With this in place, while processing an
2055 // order_file, if any entry is in a cluster (in "starts" map), then the entire cluster is
2056 // given ordinal overrides.
2057 //
2058 void Linker::sortAtoms()
2059 {
2060         fStartSortTime = mach_absolute_time();
2061         // if -order_file is used, build map of atom ordinal overrides
2062         std::map<const ObjectFile::Atom*, uint32_t>* ordinalOverrideMap = NULL;
2063         std::map<const ObjectFile::Atom*, uint32_t> theOrdinalOverrideMap;
2064         const bool log = false;
2065         if ( fOptions.orderedSymbols().size() != 0 ) {
2066                 // first make a pass to find all follow-on references and build start/next maps
2067                 // which are a way to represent clusters of atoms that must layout together
2068                 std::map<const ObjectFile::Atom*, const ObjectFile::Atom*> followOnStarts;
2069                 std::map<const ObjectFile::Atom*, const ObjectFile::Atom*> followOnNexts;
2070                 for (std::vector<ObjectFile::Atom*>::iterator ait=fAllAtoms.begin(); ait != fAllAtoms.end(); ait++) {
2071                         ObjectFile::Atom* atom = *ait;
2072                         std::vector<class ObjectFile::Reference*>& references = atom->getReferences();
2073                         for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); rit++) {
2074                                 ObjectFile::Reference* ref = *rit;
2075                                 if ( ref->getKind() == 1 ) {    // FIX FIX
2076                                         ObjectFile::Atom* targetAtom = &ref->getTarget();
2077                                         if ( log ) fprintf(stderr, "ref %s -> %s", atom->getDisplayName(), targetAtom->getDisplayName());
2078                                         std::map<const ObjectFile::Atom*, const ObjectFile::Atom*>::iterator startFrom = followOnStarts.find(atom);
2079                                         std::map<const ObjectFile::Atom*, const ObjectFile::Atom*>::iterator startTo = followOnStarts.find(targetAtom);
2080                                         if ( (startFrom == followOnStarts.end()) && (startTo == followOnStarts.end()) ) {
2081                                                 // this is first time we've seen either atom, make simple cluster of the two
2082                                                 if ( log ) fprintf(stderr, "  new cluster\n");
2083                                                 followOnStarts[atom] = atom;
2084                                                 followOnStarts[targetAtom] = atom;
2085                                                 followOnNexts[atom] = targetAtom;
2086                                                 followOnNexts[targetAtom] = NULL;
2087                                         }
2088                                         else if ( (startFrom != followOnStarts.end()) && (startTo == followOnStarts.end()) && (followOnNexts[atom] == NULL) ) {
2089                                                 // atom is at end of an existing cluster, so append target to end of cluster
2090                                                 if ( log ) fprintf(stderr, "  end of cluster starting with %s\n", followOnStarts[atom]->getDisplayName());
2091                                                 followOnNexts[atom] = targetAtom;
2092                                                 followOnNexts[targetAtom] = NULL;
2093                                                 followOnStarts[targetAtom] = followOnStarts[atom];
2094                                         }
2095                                         else {
2096                                                 // gerneral case of inserting into an existing cluster
2097                                                 if ( followOnNexts[atom] != NULL ) {
2098                                                         // an atom with two follow-ons is illegal
2099                                                         warning("can't order %s because both %s and %s must follow it",
2100                                                                                 atom->getDisplayName(), targetAtom->getDisplayName(), followOnNexts[atom]->getDisplayName());
2101                                                 }
2102                                                 else {
2103                                                         // there already exists an atom that says target must be its follow-on
2104                                                         const ObjectFile::Atom* originalStart = startTo->second;
2105                                                         const ObjectFile::Atom* originalPrevious = originalStart;
2106                                                         while ( followOnNexts[originalPrevious] != targetAtom )
2107                                                                 originalPrevious = followOnNexts[originalPrevious];
2108                                                         bool otherIsAlias = (originalPrevious->getSize() == 0);
2109                                                         bool thisIsAlias = (atom->getSize() == 0);
2110                                                         if ( !otherIsAlias && !thisIsAlias ) {
2111                                                                 warning("can't order %s because both %s and %s must preceed it",
2112                                                                                         targetAtom->getDisplayName(), originalPrevious->getDisplayName(), atom->getDisplayName());
2113                                                         }
2114                                                         else if ( otherIsAlias ) {
2115                                                                 if ( originalPrevious == originalStart ) {
2116                                                                         // other is alias at start of cluster, make this the new start of cluster
2117                                                                         if ( log ) fprintf(stderr, "  becomes new start of cluster previous starting with %s\n", originalStart->getDisplayName());
2118                                                                         followOnNexts[atom] = originalPrevious;
2119                                                                         for(const ObjectFile::Atom* nextAtom = atom; nextAtom != NULL; nextAtom = followOnNexts[nextAtom])
2120                                                                                 followOnStarts[nextAtom] = atom;
2121                                                                 }
2122                                                                 else {
2123                                                                         // other is alias in middle of cluster, insert new atom before it
2124                                                                         if ( log ) fprintf(stderr, "  insert into cluster starting with %s before alias %s\n", originalStart->getDisplayName(), originalPrevious->getDisplayName());
2125                                                                         followOnStarts[atom] = originalStart;
2126                                                                         followOnNexts[atom] = originalPrevious;
2127                                                                         for(const ObjectFile::Atom* a = originalStart; a != NULL; a = followOnNexts[a]) {
2128                                                                                 if ( followOnNexts[a] == originalPrevious ) {
2129                                                                                         followOnNexts[a] = atom;
2130                                                                                         break;
2131                                                                                 }
2132                                                                         }
2133                                                                 }
2134                                                         }
2135                                                         else {
2136                                                                 // this is alias, so it can go inbetween originalPrevious and targetAtom
2137                                                                 if ( log ) fprintf(stderr, "  insert into cluster starting with %s after %s\n", originalStart->getDisplayName(), originalPrevious->getDisplayName());
2138                                                                 followOnStarts[atom] = originalStart;
2139                                                                 followOnNexts[atom] = followOnNexts[originalPrevious];
2140                                                                 followOnNexts[originalPrevious] = atom;
2141                                                         }
2142                                                 }
2143                                         }
2144                                 }
2145                         }
2146                 }
2147
2148                 if ( log ) {
2149                         for(std::map<const ObjectFile::Atom*, const ObjectFile::Atom*>::iterator it = followOnStarts.begin(); it != followOnStarts.end(); ++it)
2150                                 fprintf(stderr, "start %s -> %s\n", it->first->getDisplayName(), it->second->getDisplayName());
2151
2152                         for(std::map<const ObjectFile::Atom*, const ObjectFile::Atom*>::iterator it = followOnNexts.begin(); it != followOnNexts.end(); ++it)
2153                                 fprintf(stderr, "next %s -> %s\n", it->first->getDisplayName(), (it->second != NULL) ? it->second->getDisplayName() : "null");
2154                 }
2155
2156                 // with the start/next maps of follow-on atoms we can process the order file and produce override ordinals
2157                 ordinalOverrideMap = &theOrdinalOverrideMap;
2158                 uint32_t index = 0;
2159                 uint32_t matchCount = 0;
2160                 std::vector<Options::OrderedSymbol>& orderedSymbols = fOptions.orderedSymbols();
2161                 for(std::vector<Options::OrderedSymbol>::iterator it = orderedSymbols.begin(); it != orderedSymbols.end(); ++it) {
2162                         ObjectFile::Atom* atom = this->findAtom(*it);
2163                         if ( atom != NULL ) {
2164                                 std::map<const ObjectFile::Atom*, const ObjectFile::Atom*>::iterator start = followOnStarts.find(atom);
2165                                 if ( start != followOnStarts.end() ) {
2166                                         // this symbol for the order file corresponds to an atom that is in a cluster that must lay out together
2167                                         for(const ObjectFile::Atom* nextAtom = start->second; nextAtom != NULL; nextAtom = followOnNexts[nextAtom]) {
2168                                                 std::map<const ObjectFile::Atom*, uint32_t>::iterator pos = theOrdinalOverrideMap.find(nextAtom);
2169                                                 if ( pos == theOrdinalOverrideMap.end() ) {
2170                                                         theOrdinalOverrideMap[nextAtom] = index++;
2171                                                         if (log ) fprintf(stderr, "override ordinal %u assigned to %s in cluster from %s\n", index, nextAtom->getDisplayName(), nextAtom->getFile()->getPath());
2172                                                 }
2173                                                 else {
2174                                                         if (log ) fprintf(stderr, "could not order %s as %u because it was already laid out earlier by %s as %u\n",
2175                                                                                         atom->getDisplayName(), index, followOnStarts[atom]->getDisplayName(), theOrdinalOverrideMap[atom] );
2176                                                 }
2177                                         }
2178                                 }
2179                                 else {
2180                                         theOrdinalOverrideMap[atom] = index;
2181                                         if (log ) fprintf(stderr, "override ordinal %u assigned to %s from %s\n", index, atom->getDisplayName(), atom->getFile()->getPath());
2182                                 }
2183                         }
2184                         else {
2185                                 ++matchCount;
2186                                 //fprintf(stderr, "can't find match for order_file entry %s/%s\n", it->objectFileName, it->symbolName);
2187                         }
2188                          ++index;
2189                 }
2190                 if ( fOptions.printOrderFileStatistics() && (fOptions.orderedSymbols().size() != matchCount) ) {
2191                         warning("only %u out of %lu order_file symbols were applicable", matchCount, fOptions.orderedSymbols().size() );
2192                 }
2193         }
2194
2195         // sort atoms
2196         std::sort(fAllAtoms.begin(), fAllAtoms.end(), Linker::AtomSorter(ordinalOverrideMap, fInitializerAtoms, fTerminatorAtoms));
2197
2198         //fprintf(stderr, "Sorted atoms:\n");
2199         //for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
2200         //      fprintf(stderr, "\t%p, %u  %s\t%s\n", (*it)->getSection(), (*it)->getSection()->getIndex(), (*it)->getDisplayName(), (*it)->getFile()->getPath());
2201         //}
2202 }
2203
2204
2205 // make sure given addresses are within reach of branches, etc
2206 void Linker::tweakLayout()
2207 {
2208         // > 2GB images need their large zero fill atoms sorted to the end to keep access with +/- 2GB
2209         if ( fTotalSize > 0x7F000000 ) {
2210                 fBiggerThanTwoGigOutput = true;
2211
2212                 if ( (fTotalSize-fTotalZeroFillSize) > 0x7F000000 )
2213                         throwf("total output size exceeds 2GB (%lldMB)", (fTotalSize-fTotalZeroFillSize)/(1024*1024));
2214
2215                 // move very large (>1MB) zero fill atoms to a new section at very end of __DATA segment
2216                 Section* hugeZeroFills = Section::find("__huge", "__DATA", true);
2217                 for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
2218                         ObjectFile::Atom* atom = *it;
2219                         if ( atom->isZeroFill() && (atom->getSize() > 1024*1024) && (strcmp(atom->getSegment().getName(), "__DATA") == 0) )
2220                                 atom->setSection(hugeZeroFills);
2221                 }
2222         }
2223
2224         // move all initializers to start of __text section
2225         if ( fOptions.readerOptions().fAutoOrderInitializers ) {
2226                 // move -init function to front of __text
2227                 if ( fOptions.initFunctionName() != NULL ) {
2228                         ObjectFile::Atom* initAtom = fGlobalSymbolTable.find(fOptions.initFunctionName());
2229                         if ( initAtom == NULL )
2230                                 throwf("could not find -init function: \"%s\"", fOptions.initFunctionName());
2231                         moveToFrontOfSection(initAtom);
2232                 }
2233
2234                 // move all functions pointed to by __mod_init_func section to front of __text
2235                 Section* initSection = Section::find("__mod_init_func", "__DATA", false, false);
2236                 if ( initSection != NULL ) {
2237                         for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); ++it) {
2238                                 if ( (*it)->getSection() == initSection ) {
2239                                         std::vector<class ObjectFile::Reference*>& references = (*it)->getReferences();
2240                                         if ( references.size() == 1 )
2241                                                 moveToFrontOfSection(&(references[0]->getTarget()));
2242                                 }
2243                         }
2244                 }
2245         }
2246
2247         // move atoms with relocations to start of __DATA,__data section
2248         // <rdar://problem/6061558> linker should order __DATA segment to reduce dyld dirtied pages
2249         if ( fOptions.orderData() ) {
2250                 bool slideable = false;
2251                 switch ( fOptions.outputKind() ) {
2252                         case Options::kDynamicExecutable:
2253                         case Options::kStaticExecutable:
2254                         case Options::kDyld:
2255                         case Options::kPreload:
2256                         case Options::kObjectFile:
2257                         case Options::kKextBundle:
2258                                 slideable = false;
2259                                 break;
2260                         case Options::kDynamicLibrary:
2261                         case Options::kDynamicBundle:
2262                                 slideable = true;
2263                                 break;
2264                 }
2265                 const bool hasPreferredLoadAddress = (fOptions.baseAddress() != 0);
2266                 Section* dataSection = Section::find("__data", "__DATA", false, false);
2267                 if ( dataSection != NULL ) {
2268                         for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); ++it) {
2269                                 ObjectFile::Atom* dataAtom = *it;
2270                                 if ( dataAtom->getSection() == dataSection ) {
2271                                         std::vector<class ObjectFile::Reference*>& references = dataAtom->getReferences();
2272                                         if ( references.size() > 0 ) {
2273                                                 if ( slideable && !hasPreferredLoadAddress ) {
2274                                                         // in a slidable image dyld will need to rebase and bind so any references will need runtime fixups
2275                                                         // if image has preferred base address, assume it will load there and not rebase
2276                                                         moveToFrontOfSection(dataAtom);
2277                                                 }
2278                                                 else {
2279                                                         // in a non-slideable image, dyld will only do binding, so only references to
2280                                                         // symbols in another dylib will need runtime fixups
2281                                                         //fprintf(stderr, "reference from atom %s\n", dataAtom->getDisplayName());
2282                                                         for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); rit++) {
2283                                                                 ObjectFile::Reference* reference = *rit;
2284                                                                 //fprintf(stderr, "\t%d %s\n", reference->getTarget().getDefinitionKind(), reference->getTarget().getDisplayName());
2285                                                                 if ( (reference->getTarget().getDefinitionKind() == ObjectFile::Atom::kExternalDefinition)
2286                                                                   || (reference->getTarget().getDefinitionKind() == ObjectFile::Atom::kExternalWeakDefinition) ) {
2287                                                                         moveToFrontOfSection(dataAtom);
2288                                                                         break;
2289                                                                 }
2290                                                         }
2291                                                 }
2292                                         }
2293                                 }
2294                         }
2295                 }
2296         }
2297
2298 }
2299
2300
2301 void Linker::writeDotOutput()
2302 {
2303         const char* dotOutFilePath = fOptions.dotOutputFile();
2304         if ( dotOutFilePath != NULL ) {
2305                 FILE* out = fopen(dotOutFilePath, "w");
2306                 if ( out != NULL ) {
2307                         // print header
2308                         fprintf(out, "digraph dg\n{\n");
2309                         fprintf(out, "\tconcentrate = true;\n");
2310                         fprintf(out, "\trankdir = LR;\n");
2311
2312                         // print each atom as a node
2313                         for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
2314                                 ObjectFile::Atom* atom = *it;
2315                                 if ( atom->getFile() != fOutputFile ) {
2316                                         const char* name = atom->getDisplayName();
2317                                         if ( (atom->getDefinitionKind() == ObjectFile::Atom::kExternalDefinition)
2318                                           || (atom->getDefinitionKind() == ObjectFile::Atom::kExternalWeakDefinition) ) {
2319                                                 fprintf(out, "\taddr%p [ shape = plaintext, label = \"%s\" ];\n", atom, name);
2320                                         }
2321                                         else if ( strcmp(atom->getSectionName(), "__cstring") == 0 ) {
2322                                                 char cstring[atom->getSize()+2];
2323                                                 atom->copyRawContent((uint8_t*)cstring);
2324                                                 fprintf(out, "\taddr%p [ label = \"string: '", atom);
2325                                                 for (const char* s=cstring; *s != '\0'; ++s) {
2326                                                         if ( *s == '\n' )
2327                                                                 fprintf(out, "\\\\n");
2328                                                         else
2329                                                                 fputc(*s, out);
2330                                                 }
2331                                                 fprintf(out, "'\" ];\n");
2332                                         }
2333                                         else {
2334                                                 fprintf(out, "\taddr%p [ label = \"%s\" ];\n", atom, name);
2335                                         }
2336                                 }
2337                         }
2338                         fprintf(out, "\n");
2339
2340                         // print each reference as an edge
2341                         for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
2342                                 ObjectFile::Atom* fromAtom = *it;
2343                                 if ( fromAtom->getFile() != fOutputFile ) {
2344                                         std::vector<ObjectFile::Reference*>&  references = fromAtom->getReferences();
2345                                         std::set<ObjectFile::Atom*> seenTargets;
2346                                         for (std::vector<ObjectFile::Reference*>::iterator rit=references.begin(); rit != references.end(); rit++) {
2347                                                 ObjectFile::Reference* reference = *rit;
2348                                                 ObjectFile::Atom* toAtom = &(reference->getTarget());
2349                                                 if ( seenTargets.count(toAtom) == 0 ) {
2350                                                         seenTargets.insert(toAtom);
2351                                                         fprintf(out, "\taddr%p -> addr%p;\n", fromAtom, toAtom);
2352                                                 }
2353                                         }
2354                                 }
2355                         }
2356                         fprintf(out, "\n");
2357
2358                         // push all imports to bottom of graph
2359                         fprintf(out, "{ rank = same; ");
2360                         for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
2361                                 ObjectFile::Atom* atom = *it;
2362                                 if ( atom->getFile() != fOutputFile )
2363                                         if ( (atom->getDefinitionKind() == ObjectFile::Atom::kExternalDefinition)
2364                                           || (atom->getDefinitionKind() == ObjectFile::Atom::kExternalWeakDefinition) ) {
2365                                                 fprintf(out, "addr%p; ", atom);
2366                                         }
2367                         }
2368                         fprintf(out, "};\n ");
2369
2370                         // print footer
2371                         fprintf(out, "}\n");
2372                         fclose(out);
2373                 }
2374                 else {
2375                         warning("could not write dot output file: %s", dotOutFilePath);
2376                 }
2377         }
2378 }
2379
2380 ObjectFile::Atom* Linker::entryPoint(bool orInit)
2381 {
2382         // if main executable, find entry point atom
2383         ObjectFile::Atom* entryPoint = NULL;
2384         switch ( fOptions.outputKind() ) {
2385                 case Options::kDynamicExecutable:
2386                 case Options::kStaticExecutable:
2387                 case Options::kDyld:
2388                 case Options::kPreload:
2389                         entryPoint = fGlobalSymbolTable.find(fOptions.entryName());
2390                         if ( entryPoint == NULL ) {
2391                                 throwf("could not find entry point \"%s\" (perhaps missing crt1.o)", fOptions.entryName());
2392                         }
2393                         break;
2394                 case Options::kDynamicLibrary:
2395                         if ( orInit && (fOptions.initFunctionName() != NULL) ) {
2396                                 entryPoint = fGlobalSymbolTable.find(fOptions.initFunctionName());
2397                                 if ( entryPoint == NULL ) {
2398                                         throwf("could not find -init function: \"%s\"", fOptions.initFunctionName());
2399                                 }
2400                         }
2401                         break;
2402                 case Options::kObjectFile:
2403                 case Options::kDynamicBundle:
2404                 case Options::kKextBundle:
2405                         entryPoint = NULL;
2406                         break;
2407         }
2408         return entryPoint;
2409 }
2410
2411 ObjectFile::Atom* Linker::dyldClassicHelper()
2412 {
2413         if ( fOptions.makeClassicDyldInfo() )
2414                 return fGlobalSymbolTable.find("dyld_stub_binding_helper");
2415         else
2416                 return NULL;
2417 }
2418
2419 ObjectFile::Atom* Linker::dyldCompressedHelper()
2420 {
2421         if ( fOptions.makeCompressedDyldInfo() ) {
2422                 // dyld_stub_binder is in libSystem.B.dylib
2423                 ObjectFile::Atom* atom = fGlobalSymbolTable.find("dyld_stub_binder");
2424                 if ( atom == NULL ) {
2425                         this->addJustInTimeAtoms("dyld_stub_binder", true, false, true);
2426                 }
2427                 atom = fGlobalSymbolTable.find("dyld_stub_binder");
2428                 return atom;
2429         }
2430         else
2431                 return NULL;
2432 }
2433
2434 ObjectFile::Atom* Linker::dyldLazyLibraryHelper()
2435 {
2436         return fGlobalSymbolTable.find("dyld_lazy_dylib_stub_binding_helper");
2437 }
2438
2439 const char* Linker::assureFullPath(const char* path)
2440 {
2441         if ( path[0] == '/' )
2442                 return path;
2443         char cwdbuff[MAXPATHLEN];
2444         if ( getcwd(cwdbuff, MAXPATHLEN) != NULL ) {
2445                 char* result;
2446                 asprintf(&result, "%s/%s", cwdbuff, path);
2447                 if ( result != NULL )
2448                         return result;
2449         }
2450         return path;
2451 }
2452
2453
2454 //
2455 // The stab strings are of the form:
2456 //              <name> ':' <type-code> <number-pari>
2457 //  but the <name> contain a colon.
2458 //  For C++ <name> may contain a double colon (e.g. std::string:f(0,1) )
2459 //  For Objective-C name may contain a colon instead square bracket (e.g. [Foo doit:]:f(0,1) )
2460 //
2461 const char* Linker::truncateStabString(const char* str)
2462 {
2463         enum { start, inObjc } state = start;
2464         for (const char* s = str; *s != 0; ++s) {
2465                 char c = *s;
2466                 switch (state) {
2467                         case start:
2468                                 if ( c == '[' ) {
2469                                         state = inObjc;
2470                                 }
2471                                 else {
2472                                         if ( c == ':' ) {
2473                                                 if ( s[1] == ':' ) {
2474                                                         ++s;
2475                                                 }
2476                                                 else {
2477                                                         // found colon
2478                                                         // Duplicate strndup behavior here.
2479                                                         int trunStrLen = s-str+2;
2480                                                         char* temp = new char[trunStrLen+1];
2481                                                         memcpy(temp, str, trunStrLen);
2482                                                         temp[trunStrLen] = '\0';
2483                                                         return temp;
2484                                                 }
2485                                         }
2486                                 }
2487                                 break;
2488                         case inObjc:
2489                                 if ( c == ']' ) {
2490                                         state = start;
2491                                 }
2492                                 break;
2493                 }
2494         }
2495         // malformed
2496         return str;
2497 }
2498
2499
2500 bool Linker::minimizeStab(ObjectFile::Reader::Stab& stab)
2501 {
2502         switch(stab.type){
2503                 case N_GSYM:
2504                 case N_STSYM:
2505                 case N_LCSYM:
2506                 case N_FUN:
2507                         // these all need truncated strings
2508                         stab.string = truncateStabString(stab.string);
2509                         return true;
2510                 case N_SO:
2511                 case N_OSO:
2512                 case N_OPT:
2513                 case N_SOL:
2514                         // these are included in the minimal stabs, but they keep their full string
2515                         return true;
2516                 default:
2517                         return false;
2518         }
2519 }
2520
2521
2522 struct HeaderRange {
2523         std::vector<ObjectFile::Reader::Stab>::iterator begin;
2524         std::vector<ObjectFile::Reader::Stab>::iterator end;
2525         int                                                                                             parentRangeIndex;
2526         uint32_t                                                                                sum;
2527         bool                                                                                    sumPrecomputed;
2528         bool                                                                                    useEXCL;
2529         bool                                                                                    cannotEXCL; // because of SLINE, etc stabs
2530 };
2531
2532
2533 typedef __gnu_cxx::hash_map<const char*, std::vector<uint32_t>, __gnu_cxx::hash<const char*>, CStringEquals> PathToSums;
2534
2535 // hash table that maps header path to a vector of known checksums for that path
2536 static PathToSums sKnownBINCLs;
2537
2538
2539 void Linker::collectStabs(ObjectFile::Reader* reader, std::map<const class ObjectFile::Atom*, uint32_t>& atomOrdinals)
2540 {
2541         const bool log = false;
2542         bool minimal = ( fOptions.readerOptions().fDebugInfoStripping == ObjectFile::ReaderOptions::kDebugInfoMinimal );
2543         std::vector<class ObjectFile::Reader::Stab>* readerStabs = reader->getStabs();
2544         if ( readerStabs == NULL )
2545                 return;
2546
2547         if ( log ) fprintf(stderr, "processesing %lu stabs for %s\n", readerStabs->size(), reader->getPath());
2548         std::vector<HeaderRange> ranges;
2549         int curRangeIndex = -1;
2550         int count = 0;
2551         ObjectFile::Atom* atomWithLowestOrdinal = NULL;
2552         ObjectFile::Atom* atomWithHighestOrdinal = NULL;
2553         uint32_t highestOrdinal = 0;
2554         uint32_t lowestOrdinal = UINT_MAX;
2555         std::vector<std::pair<ObjectFile::Atom*,ObjectFile::Atom*> > soRanges;
2556         // 1) find all (possibly nested) BINCL/EINCL ranges and their checksums
2557         // 2) find all SO/SO ranges and the first/last atom own by a FUN stab therein
2558         for(std::vector<class ObjectFile::Reader::Stab>::iterator it=readerStabs->begin(); it != readerStabs->end(); ++it) {
2559                 ++count;
2560                 switch ( it->type ) {
2561                         case N_BINCL:
2562                                 {
2563                                         HeaderRange range;
2564                                         range.begin = it;
2565                                         range.end = readerStabs->end();
2566                                         range.parentRangeIndex = curRangeIndex;
2567                                         range.sum = it->value;
2568                                         range.sumPrecomputed = (range.sum != 0);
2569                                         range.useEXCL = false;
2570                                         range.cannotEXCL = false;
2571                                         curRangeIndex = ranges.size();
2572                                         if ( log ) fprintf(stderr, "[%d]BINCL %s\n", curRangeIndex, it->string);
2573                                         ranges.push_back(range);
2574                                 }
2575                                 break;
2576                         case N_EINCL:
2577                                 if ( curRangeIndex == -1 ) {
2578                                         warning("EINCL missing BINCL in %s", reader->getPath());
2579                                 }
2580                                 else {
2581                                         ranges[curRangeIndex].end = it+1;
2582                                         if ( log ) fprintf(stderr, "[%d->%d]EINCL %s\n", curRangeIndex, ranges[curRangeIndex].parentRangeIndex, it->string);
2583                                         curRangeIndex = ranges[curRangeIndex].parentRangeIndex;
2584                                 }
2585                                 break;
2586                         case N_FUN:
2587                                 {
2588                                         std::map<const class ObjectFile::Atom*, uint32_t>::iterator pos = atomOrdinals.find(it->atom);
2589                                         if ( pos != atomOrdinals.end() ) {
2590                                                 uint32_t ordinal = pos->second;
2591                                                 if ( ordinal > highestOrdinal ) {
2592                                                         highestOrdinal = ordinal;
2593                                                         atomWithHighestOrdinal = it->atom;
2594                                                 }
2595                                                 if ( ordinal < lowestOrdinal ) {
2596                                                         lowestOrdinal = ordinal;
2597                                                         atomWithLowestOrdinal = it->atom;
2598                                                 }
2599                                         }
2600                                 }
2601                                 // fall through
2602                         case N_BNSYM:
2603                         case N_ENSYM:
2604                         case N_LBRAC:
2605                         case N_RBRAC:
2606                         case N_SLINE:
2607                         case N_STSYM:
2608                         case N_LCSYM:
2609                                 if ( curRangeIndex != -1 ) {
2610                                         ranges[curRangeIndex].cannotEXCL = true;
2611                                         if ( fOptions.warnStabs() )
2612                                                 warning("cannot do BINCL/EINCL optimzation because of stabs kinds in %s for %s\n", ranges[curRangeIndex].begin->string, reader->getPath());
2613                                 }
2614                                 break;
2615                         case N_SO:
2616                                 if ( (it->string != NULL) && (strlen(it->string) > 0) ) {
2617                                         // start SO, reset hi/low FUN tracking
2618                                         atomWithLowestOrdinal = NULL;
2619                                         atomWithHighestOrdinal = NULL;
2620                                         highestOrdinal = 0;
2621                                         lowestOrdinal = UINT_MAX;
2622                                 }
2623                                 else {
2624                                         // end SO, record hi/low atoms for this SO range
2625                                         soRanges.push_back(std::make_pair<ObjectFile::Atom*,ObjectFile::Atom*>(atomWithLowestOrdinal, atomWithHighestOrdinal));
2626                                 }
2627                                 // fall through
2628                         default:
2629                                 if ( curRangeIndex != -1 ) {
2630                                         if ( ! ranges[curRangeIndex].sumPrecomputed ) {
2631                                                 uint32_t sum = 0;
2632                                                 const char* s = it->string;
2633                                                 char c;
2634                                                 while ( (c = *s++) != 0 ) {
2635                                                         sum += c;
2636                                                         // don't checkusm first number (file index) after open paren in string
2637                                                         if ( c == '(' ) {
2638                                                                 while(isdigit(*s))
2639                                                                         ++s;
2640                                                         }
2641                                                 }
2642                                                 ranges[curRangeIndex].sum += sum;
2643                                         }
2644                                 }
2645
2646                 }
2647         }
2648         if ( log ) fprintf(stderr, "processesed %d stabs for %s\n", count, reader->getPath());
2649         if ( curRangeIndex != -1 )
2650                 warning("BINCL (%s) missing EINCL in %s", ranges[curRangeIndex].begin->string, reader->getPath());
2651
2652         // if no BINCLs
2653         if ( ranges.size() == 0 ) {
2654                 unsigned int soIndex = 0;
2655                 for(std::vector<ObjectFile::Reader::Stab>::iterator it=readerStabs->begin(); it != readerStabs->end(); ++it) {
2656                         // copy minimal or all stabs
2657                         ObjectFile::Reader::Stab stab = *it;
2658                         if ( !minimal || minimizeStab(stab) ) {
2659                                 if ( stab.type == N_SO ) {
2660                                         if ( soIndex < soRanges.size() ) {
2661                                                 if ( (stab.string != NULL) && (strlen(stab.string) > 0) ) {
2662                                                         // starting SO is associated with first atom
2663                                                         stab.atom = soRanges[soIndex].first;
2664                                                 }
2665                                                 else {
2666                                                         // ending SO is associated with last atom
2667                                                         stab.atom = soRanges[soIndex].second;
2668                                                         ++soIndex;
2669                                                 }
2670                                         }
2671                                 }
2672                                 fStabs.push_back(stab);
2673                         }
2674                 }
2675                 return;
2676         }
2677
2678         //fprintf(stderr, "BINCL/EINCL info for %s\n", reader->getPath());
2679         //for(std::vector<HeaderRange>::iterator it=ranges.begin(); it != ranges.end(); ++it) {
2680         //      fprintf(stderr, "%08X %s\n", it->sum, it->begin->string);
2681         //}
2682
2683         // see if any of these BINCL/EINCL ranges have already been seen and therefore can be replaced with EXCL
2684         for(std::vector<HeaderRange>::iterator it=ranges.begin(); it != ranges.end(); ++it) {
2685                 if ( ! it->cannotEXCL ) {
2686                         const char* header = it->begin->string;
2687                         uint32_t sum = it->sum;
2688                         PathToSums::iterator pos = sKnownBINCLs.find(header);
2689                         if ( pos != sKnownBINCLs.end() ) {
2690                                 std::vector<uint32_t>& sums = pos->second;
2691                                 for(std::vector<uint32_t>::iterator sit=sums.begin(); sit != sums.end(); ++sit) {
2692                                         if (*sit == sum) {
2693                                                 //fprintf(stderr, "use EXCL for %s in %s\n", header, reader->getPath());
2694                                                 it->useEXCL = true;
2695                                                 break;
2696                                         }
2697                                 }
2698                                 if ( ! it->useEXCL ) {
2699                                         // have seen this path, but not this checksum
2700                                         //fprintf(stderr, "registering another checksum %08X for %s\n", sum, header);
2701                                         sums.push_back(sum);
2702                                 }
2703                         }
2704                         else {
2705                                 // have not seen this path, so add to known BINCLs
2706                                 std::vector<uint32_t> empty;
2707                                 sKnownBINCLs[header] = empty;
2708                                 sKnownBINCLs[header].push_back(sum);
2709                                 //fprintf(stderr, "registering checksum %08X for %s\n", sum, header);
2710                         }
2711                 }
2712         }
2713
2714         // add a new set of stabs with BINCL/EINCL runs that have been seen before, replaced with EXCLs
2715         curRangeIndex = -1;
2716         const int maxRangeIndex = ranges.size();
2717         int soIndex = 0;
2718         for(std::vector<ObjectFile::Reader::Stab>::iterator it=readerStabs->begin(); it != readerStabs->end(); ++it) {
2719                 switch ( it->type ) {
2720                         case N_BINCL:
2721                                 for(int i=curRangeIndex+1; i < maxRangeIndex; ++i) {
2722                                         if ( ranges[i].begin == it ) {
2723                                                 curRangeIndex = i;
2724                                                 HeaderRange& range = ranges[curRangeIndex];
2725                                                 ObjectFile::Reader::Stab stab = *it;
2726                                                 stab.value = range.sum; // BINCL and EXCL have n_value set to checksum
2727                                                 if ( range.useEXCL )
2728                                                         stab.type = N_EXCL;     // transform BINCL into EXCL
2729                                                 if ( !minimal )
2730                                                         fStabs.push_back(stab);
2731                                                 break;
2732                                         }
2733                                 }
2734                                 break;
2735                         case N_EINCL:
2736                                 if ( curRangeIndex != -1 ) {
2737                                         if ( !ranges[curRangeIndex].useEXCL && !minimal )
2738                                                 fStabs.push_back(*it);
2739                                         curRangeIndex = ranges[curRangeIndex].parentRangeIndex;
2740                                 }
2741                                 break;
2742                         default:
2743                                 if ( (curRangeIndex == -1) || !ranges[curRangeIndex].useEXCL ) {
2744                                         ObjectFile::Reader::Stab stab = *it;
2745                                         if ( !minimal || minimizeStab(stab) ) {
2746                                                 if ( stab.type == N_SO ) {
2747                                                         if ( (stab.string != NULL) && (strlen(stab.string) > 0) ) {
2748                                                                 // starting SO is associated with first atom
2749                                                                 stab.atom = soRanges[soIndex].first;
2750                                                         }
2751                                                         else {
2752                                                                 // ending SO is associated with last atom
2753                                                                 stab.atom = soRanges[soIndex].second;
2754                                                                 ++soIndex;
2755                                                         }
2756                                                 }
2757                                                 fStabs.push_back(stab);
2758                                         }
2759                                 }
2760                 }
2761         }
2762
2763 }
2764
2765
2766 // used to prune out atoms that don't need debug notes generated
2767 class NoDebugNoteAtom
2768 {
2769 public:
2770         NoDebugNoteAtom(const std::map<class ObjectFile::Reader*, uint32_t>& readersWithDwarfOrdinals)
2771                         : fReadersWithDwarfOrdinals(readersWithDwarfOrdinals) {}
2772
2773         bool operator()(const ObjectFile::Atom* atom) const {
2774                 if ( atom->getSymbolTableInclusion() == ObjectFile::Atom::kSymbolTableNotIn )
2775                         return true;
2776                 if ( atom->getName() == NULL )
2777                         return true;
2778                 if ( fReadersWithDwarfOrdinals.find(atom->getFile()) == fReadersWithDwarfOrdinals.end() )
2779                         return true;
2780                 return false;
2781         }
2782
2783 private:
2784         const std::map<class ObjectFile::Reader*, uint32_t>& fReadersWithDwarfOrdinals;
2785 };
2786
2787 // used to sort atoms with debug notes
2788 class ReadersWithDwarfSorter
2789 {
2790 public:
2791         ReadersWithDwarfSorter(const std::map<class ObjectFile::Reader*, uint32_t>& readersWithDwarfOrdinals,
2792                                                    const std::map<const class ObjectFile::Atom*, uint32_t>& atomOrdinals)
2793                         : fReadersWithDwarfOrdinals(readersWithDwarfOrdinals), fAtomOrdinals(atomOrdinals) {}
2794
2795         bool operator()(const ObjectFile::Atom* left, const ObjectFile::Atom* right) const
2796         {
2797                 // first sort by reader
2798                 unsigned int leftReaderIndex  = fReadersWithDwarfOrdinals.find(left->getFile())->second;
2799                 unsigned int rightReaderIndex = fReadersWithDwarfOrdinals.find(right->getFile())->second;
2800                 if ( leftReaderIndex != rightReaderIndex )
2801                         return (leftReaderIndex < rightReaderIndex);
2802
2803                 // then sort by atom ordinal
2804                 unsigned int leftAtomIndex  = fAtomOrdinals.find(left)->second;
2805                 unsigned int rightAtomIndex = fAtomOrdinals.find(right)->second;
2806                 return leftAtomIndex < rightAtomIndex;
2807         }
2808
2809 private:
2810         const std::map<class ObjectFile::Reader*, uint32_t>& fReadersWithDwarfOrdinals;
2811         const std::map<const class ObjectFile::Atom*, uint32_t>& fAtomOrdinals;
2812 };
2813
2814
2815
2816
2817
2818 void Linker::synthesizeDebugNotes(std::vector<class ObjectFile::Atom*>& allAtomsByReader)
2819 {
2820         // synthesize "debug notes" and add them to master stabs vector
2821         const char* dirPath = NULL;
2822         const char* filename = NULL;
2823         bool wroteStartSO = false;
2824         bool useZeroOSOModTime = (getenv("RC_RELEASE") != NULL);
2825         __gnu_cxx::hash_set<const char*, __gnu_cxx::hash<const char*>, CStringEquals>  seenFiles;
2826         for (std::vector<ObjectFile::Atom*>::iterator it=allAtomsByReader.begin(); it != allAtomsByReader.end(); it++) {
2827                 ObjectFile::Atom* atom = *it;
2828                 const char* newDirPath;
2829                 const char* newFilename;
2830                 //fprintf(stderr, "debug note for %s\n", atom->getDisplayName());
2831                 if ( atom->getTranslationUnitSource(&newDirPath, &newFilename) ) {
2832                         // need SO's whenever the translation unit source file changes
2833                         if ( newFilename != filename ) {
2834                                 // gdb like directory SO's to end in '/', but dwarf DW_AT_comp_dir usually does not have trailing '/'
2835                                 if ( (newDirPath != NULL) && (strlen(newDirPath) > 1 ) && (newDirPath[strlen(newDirPath)-1] != '/') )
2836                                         asprintf((char**)&newDirPath, "%s/", newDirPath);
2837                                 if ( filename != NULL ) {
2838                                         // translation unit change, emit ending SO
2839                                         ObjectFile::Reader::Stab endFileStab;
2840                                         endFileStab.atom                = NULL;
2841                                         endFileStab.type                = N_SO;
2842                                         endFileStab.other               = 1;
2843                                         endFileStab.desc                = 0;
2844                                         endFileStab.value               = 0;
2845                                         endFileStab.string              = "";
2846                                         fStabs.push_back(endFileStab);
2847                                 }
2848                                 // new translation unit, emit start SO's
2849                                 ObjectFile::Reader::Stab dirPathStab;
2850                                 dirPathStab.atom                = NULL;
2851                                 dirPathStab.type                = N_SO;
2852                                 dirPathStab.other               = 0;
2853                                 dirPathStab.desc                = 0;
2854                                 dirPathStab.value               = 0;
2855                                 dirPathStab.string              = newDirPath;
2856                                 fStabs.push_back(dirPathStab);
2857                                 ObjectFile::Reader::Stab fileStab;
2858                                 fileStab.atom           = NULL;
2859                                 fileStab.type           = N_SO;
2860                                 fileStab.other          = 0;
2861                                 fileStab.desc           = 0;
2862                                 fileStab.value          = 0;
2863                                 fileStab.string         = newFilename;
2864                                 fStabs.push_back(fileStab);
2865                                 // Synthesize OSO for start of file
2866                                 ObjectFile::Reader::Stab objStab;
2867                                 objStab.atom            = NULL;
2868                                 objStab.type            = N_OSO;
2869                                 // <rdar://problem/6337329> linker should put cpusubtype in n_sect field of nlist entry for N_OSO debug note entries
2870                                 objStab.other           = atom->getFile()->updateCpuConstraint(0);
2871                                 objStab.desc            = 1;
2872                                 objStab.value           = useZeroOSOModTime ? 0 : atom->getFile()->getModificationTime();
2873                                 objStab.string          = assureFullPath(atom->getFile()->getPath());
2874                                 fStabs.push_back(objStab);
2875                                 wroteStartSO = true;
2876                                 // add the source file path to seenFiles so it does not show up in SOLs
2877                                 seenFiles.insert(newFilename);
2878                         }
2879                         filename = newFilename;
2880                         dirPath = newDirPath;
2881                         if ( atom->getSegment().isContentExecutable() && (strncmp(atom->getSectionName(), "__text", 6) == 0) ) {
2882                                 // Synthesize BNSYM and start FUN stabs
2883                                 ObjectFile::Reader::Stab beginSym;
2884                                 beginSym.atom           = atom;
2885                                 beginSym.type           = N_BNSYM;
2886                                 beginSym.other          = 1;
2887                                 beginSym.desc           = 0;
2888                                 beginSym.value          = 0;
2889                                 beginSym.string         = "";
2890                                 fStabs.push_back(beginSym);
2891                                 ObjectFile::Reader::Stab startFun;
2892                                 startFun.atom           = atom;
2893                                 startFun.type           = N_FUN;
2894                                 startFun.other          = 1;
2895                                 startFun.desc           = 0;
2896                                 startFun.value          = 0;
2897                                 startFun.string         = atom->getName();
2898                                 fStabs.push_back(startFun);
2899                                 // Synthesize any SOL stabs needed
2900                                 std::vector<ObjectFile::LineInfo>* lineInfo = atom->getLineInfo();
2901                                 if ( lineInfo != NULL ) {
2902                                         const char* curFile = NULL;
2903                                         for (std::vector<ObjectFile::LineInfo>::iterator it = lineInfo->begin(); it != lineInfo->end(); ++it) {
2904                                                 if ( it->fileName != curFile ) {
2905                                                         if ( seenFiles.count(it->fileName) == 0 ) {
2906                                                                 seenFiles.insert(it->fileName);
2907                                                                 ObjectFile::Reader::Stab sol;
2908                                                                 sol.atom                = 0;
2909                                                                 sol.type                = N_SOL;
2910                                                                 sol.other               = 0;
2911                                                                 sol.desc                = 0;
2912                                                                 sol.value               = 0;
2913                                                                 sol.string              = it->fileName;
2914                                                                 fStabs.push_back(sol);
2915                                                         }
2916                                                         curFile = it->fileName;
2917                                                 }
2918                                         }
2919                                 }
2920                                 // Synthesize end FUN and ENSYM stabs
2921                                 ObjectFile::Reader::Stab endFun;
2922                                 endFun.atom                     = atom;
2923                                 endFun.type                     = N_FUN;
2924                                 endFun.other            = 0;
2925                                 endFun.desc                     = 0;
2926                                 endFun.value            = 0;
2927                                 endFun.string           = "";
2928                                 fStabs.push_back(endFun);
2929                                 ObjectFile::Reader::Stab endSym;
2930                                 endSym.atom                     = atom;
2931                                 endSym.type                     = N_ENSYM;
2932                                 endSym.other            = 1;
2933                                 endSym.desc                     = 0;
2934                                 endSym.value            = 0;
2935                                 endSym.string           = "";
2936                                 fStabs.push_back(endSym);
2937                         }
2938                         else if ( atom->getSymbolTableInclusion() == ObjectFile::Atom::kSymbolTableNotIn ) {
2939                                 // no stabs for atoms that would not be in the symbol table
2940                         }
2941                         else if ( atom->getSymbolTableInclusion() == ObjectFile::Atom::kSymbolTableInAsAbsolute ) {
2942                                 // no stabs for absolute symbols
2943                         }
2944                         else if ( (strcmp(atom->getSectionName(), "__eh_frame") == 0) ) {
2945                                 // no stabs for .eh atoms
2946                         }
2947                         else if ( (strncmp(atom->getName(), "__dtrace_probe$", 15) == 0) ) {
2948                                 // no stabs for old style dtrace probes
2949                         }
2950                         else {
2951                                 ObjectFile::Reader::Stab globalsStab;
2952                                 const char* name = atom->getName();
2953                                 if ( atom->getScope() == ObjectFile::Atom::scopeTranslationUnit ) {
2954                                         // Synthesize STSYM stab for statics
2955                                         globalsStab.atom                = atom;
2956                                         globalsStab.type                = N_STSYM;
2957                                         globalsStab.other               = 1;
2958                                         globalsStab.desc                = 0;
2959                                         globalsStab.value               = 0;
2960                                         globalsStab.string              = name;
2961                                         fStabs.push_back(globalsStab);
2962                                 }
2963                                 else {
2964                                         // Synthesize GSYM stab for other globals
2965                                         globalsStab.atom                = atom;
2966                                         globalsStab.type                = N_GSYM;
2967                                         globalsStab.other               = 1;
2968                                         globalsStab.desc                = 0;
2969                                         globalsStab.value               = 0;
2970                                         globalsStab.string              = name;
2971                                         fStabs.push_back(globalsStab);
2972                                 }
2973                         }
2974                 }
2975         }
2976
2977         if ( wroteStartSO ) {
2978                 //  emit ending SO
2979                 ObjectFile::Reader::Stab endFileStab;
2980                 endFileStab.atom                = NULL;
2981                 endFileStab.type                = N_SO;
2982                 endFileStab.other               = 1;
2983                 endFileStab.desc                = 0;
2984                 endFileStab.value               = 0;
2985                 endFileStab.string              = "";
2986                 fStabs.push_back(endFileStab);
2987         }
2988 }
2989
2990
2991
2992
2993 void Linker::collectDebugInfo()
2994 {
2995         std::map<const class ObjectFile::Atom*, uint32_t>       atomOrdinals;
2996         fStartDebugTime = mach_absolute_time();
2997         if ( fOptions.readerOptions().fDebugInfoStripping != ObjectFile::ReaderOptions::kDebugInfoNone ) {
2998
2999                 // determine mixture of stabs and dwarf
3000                 bool someStabs = false;
3001                 bool someDwarf = false;
3002                 for (std::vector<class ObjectFile::Reader*>::iterator it=fReadersThatHaveSuppliedAtoms.begin();
3003                                 it != fReadersThatHaveSuppliedAtoms.end();
3004                                 it++) {
3005                         ObjectFile::Reader* reader = *it;
3006                         if ( reader != NULL ) {
3007                                 switch ( reader->getDebugInfoKind() ) {
3008                                         case ObjectFile::Reader::kDebugInfoNone:
3009                                                 break;
3010                                         case ObjectFile::Reader::kDebugInfoStabs:
3011                                                 someStabs = true;
3012                                                 break;
3013                                         case ObjectFile::Reader::kDebugInfoDwarf:
3014                                                 someDwarf = true;
3015                                                 fCreateUUID = true;
3016                                                 break;
3017                                     case ObjectFile::Reader::kDebugInfoStabsUUID:
3018                                                 someStabs = true;
3019                                                 fCreateUUID = true;
3020                                                 break;
3021                                         default:
3022                                                 throw "Unhandled type of debug information";
3023                                 }
3024                         }
3025                 }
3026
3027                 if ( someDwarf || someStabs ) {
3028                         // try to minimize re-allocations
3029                         fStabs.reserve(1024);
3030
3031                         // make mapping from atoms to ordinal
3032                         uint32_t ordinal = 1;
3033                         for (std::vector<ObjectFile::Atom*>::iterator it=fAllAtoms.begin(); it != fAllAtoms.end(); it++) {
3034                                 atomOrdinals[*it] = ordinal++;
3035                         }
3036                 }
3037
3038                 // process all dwarf .o files as a batch
3039                 if ( someDwarf ) {
3040                         // make mapping from readers with dwarf to ordinal
3041                         std::map<class ObjectFile::Reader*, uint32_t>   readersWithDwarfOrdinals;
3042                         uint32_t readerOrdinal = 1;
3043                         for (std::vector<class ObjectFile::Reader*>::iterator it=fReadersThatHaveSuppliedAtoms.begin();
3044                                         it != fReadersThatHaveSuppliedAtoms.end();
3045                                         it++) {
3046                                 ObjectFile::Reader* reader = *it;
3047                                 if ( (reader != NULL) && (reader->getDebugInfoKind() == ObjectFile::Reader::kDebugInfoDwarf) ) {
3048                                         readersWithDwarfOrdinals[reader] = readerOrdinal++;
3049                                 }
3050                         }
3051
3052                         // make a vector of atoms
3053                         std::vector<class ObjectFile::Atom*> allAtomsByReader(fAllAtoms.begin(), fAllAtoms.end());
3054                         // remove those not from a reader that has dwarf
3055                         allAtomsByReader.erase(std::remove_if(allAtomsByReader.begin(), allAtomsByReader.end(),
3056                                                                 NoDebugNoteAtom(readersWithDwarfOrdinals)), allAtomsByReader.end());
3057                         // sort by reader then atom ordinal
3058                         std::sort(allAtomsByReader.begin(), allAtomsByReader.end(), ReadersWithDwarfSorter(readersWithDwarfOrdinals, atomOrdinals));
3059                         // add debug notes for each atom
3060                         this->synthesizeDebugNotes(allAtomsByReader);
3061                 }
3062
3063                 // process all stabs .o files one by one
3064                 if ( someStabs ) {
3065                         // get stabs from each reader, in command line order
3066                         for (std::vector<class ObjectFile::Reader*>::iterator it=fReadersThatHaveSuppliedAtoms.begin();
3067                                         it != fReadersThatHaveSuppliedAtoms.end();
3068                                         it++) {
3069                                 ObjectFile::Reader* reader = *it;
3070                                 if ( reader != NULL ) {
3071                                         switch ( reader->getDebugInfoKind() ) {
3072                                                 case ObjectFile::Reader::kDebugInfoDwarf:
3073                                                 case ObjectFile::Reader::kDebugInfoNone:
3074                                                         // do nothing
3075                                                         break;
3076                                                 case ObjectFile::Reader::kDebugInfoStabs:
3077                                                 case ObjectFile::Reader::kDebugInfoStabsUUID:
3078                                                         collectStabs(reader, atomOrdinals);
3079                                                         break;
3080                                                 default:
3081                                                         throw "Unhandled type of debug information";
3082                                         }
3083                                 }
3084                         }
3085                         // remove stabs associated with atoms that won't be in output
3086                         std::set<class ObjectFile::Atom*>       allAtomsSet;
3087                         allAtomsSet.insert(fAllAtoms.begin(), fAllAtoms.end());
3088                         fStabs.erase(std::remove_if(fStabs.begin(), fStabs.end(), NotInSet(allAtomsSet)), fStabs.end());
3089                 }
3090         }
3091 }
3092
3093 void Linker::writeOutput()
3094 {
3095         if ( fOptions.forceCpuSubtypeAll() )
3096                 fCurrentCpuConstraint = ObjectFile::Reader::kCpuAny;
3097
3098         fStartWriteTime = mach_absolute_time();
3099         // tell writer about each segment's atoms
3100         fOutputFileSize = fOutputFile->write(fAllAtoms, fStabs, this->entryPoint(true),
3101                                                                                         this->dyldClassicHelper(),this->dyldCompressedHelper(), this->dyldLazyLibraryHelper(),
3102                                                                                         fCreateUUID, fCanScatter,
3103                                                                                         fCurrentCpuConstraint, fBiggerThanTwoGigOutput,
3104                                                                                         fRegularDefAtomsThatOverrideADylibsWeakDef,
3105                                                                                         fGlobalSymbolTable.hasExternalWeakDefinitions());
3106 }
3107
3108 ObjectFile::Reader* Linker::createReader(const Options::FileInfo& info)
3109 {
3110         // map in whole file
3111         uint64_t len = info.fileLen;
3112         int fd = ::open(info.path, O_RDONLY, 0);
3113         if ( fd == -1 )
3114                 throwf("can't open file, errno=%d", errno);
3115         if ( info.fileLen < 20 )
3116                 throw "file too small";
3117
3118         uint8_t* p = (uint8_t*)::mmap(NULL, info.fileLen, PROT_READ, MAP_FILE | MAP_PRIVATE, fd, 0);
3119         if ( p == (uint8_t*)(-1) )
3120                 throwf("can't map file, errno=%d", errno);
3121
3122         // if fat file, skip to architecture we want
3123         // Note: fat header is always big-endian
3124         const fat_header* fh = (fat_header*)p;
3125         if ( fh->magic == OSSwapBigToHostInt32(FAT_MAGIC) ) {
3126                 const struct fat_arch* archs = (struct fat_arch*)(p + sizeof(struct fat_header));
3127                 uint32_t sliceToUse;
3128                 bool sliceFound = false;
3129                 if ( fOptions.preferSubArchitecture() ) {
3130                         // first try to find a slice that match cpu-type and cpu-sub-type
3131                         for (uint32_t i=0; i < OSSwapBigToHostInt32(fh->nfat_arch); ++i) {
3132                                 if ( (OSSwapBigToHostInt32(archs[i].cputype) == (uint32_t)fArchitecture)
3133                                   && (OSSwapBigToHostInt32(archs[i].cpusubtype) == (uint32_t)fOptions.subArchitecture()) ) {
3134                                         sliceToUse = i;
3135                                         sliceFound = true;
3136                                         break;
3137                                 }
3138                         }
3139                 }
3140                 if ( !sliceFound ) {
3141                         // look for any slice that matches just cpu-type
3142                         for (uint32_t i=0; i < OSSwapBigToHostInt32(fh->nfat_arch); ++i) {
3143                                 if ( OSSwapBigToHostInt32(archs[i].cputype) == (uint32_t)fArchitecture ) {
3144                                         sliceToUse = i;
3145                                         sliceFound = true;
3146                                         break;
3147                                 }
3148                         }
3149                 }
3150                 if ( sliceFound ) {
3151                         uint32_t fileOffset = OSSwapBigToHostInt32(archs[sliceToUse].offset);
3152                         len = OSSwapBigToHostInt32(archs[sliceToUse].size);
3153                         // if requested architecture is page aligned within fat file, then remap just that portion of file
3154                         if ( (fileOffset & 0x00000FFF) == 0 ) {
3155                                 // unmap whole file
3156                                 munmap((caddr_t)p, info.fileLen);
3157                                 // re-map just part we need
3158                                 p = (uint8_t*)::mmap(NULL, len, PROT_READ, MAP_FILE | MAP_PRIVATE, fd, fileOffset);
3159                                 if ( p == (uint8_t*)(-1) )
3160                                         throwf("can't re-map file, errno=%d", errno);
3161                         }
3162                         else {
3163                                 p = &p[fileOffset];
3164                         }
3165                 }
3166         }
3167         ::close(fd);
3168
3169         bool objSubtypeMustMatch = (fOptions.preferSubArchitecture() && !fOptions.allowSubArchitectureMismatches());
3170         switch (fArchitecture) {
3171                 case CPU_TYPE_POWERPC:
3172                         if ( mach_o::relocatable::Reader<ppc>::validFile(p) )
3173                                 return this->addObject(new mach_o::relocatable::Reader<ppc>::Reader(p, info.path, info.modTime, fOptions.readerOptions(), fNextInputOrdinal), info, len);
3174                         else if ( mach_o::dylib::Reader<ppc>::validFile(p, info.options.fBundleLoader) )
3175                                 return this->addDylib(new mach_o::dylib::Reader<ppc>::Reader(p, len, info.path, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
3176                         else if ( archive::Reader<ppc>::validFile(p, len) )
3177                                 return this->addArchive(new archive::Reader<ppc>::Reader(p, len, info.path, info.modTime, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
3178                         break;
3179                 case CPU_TYPE_POWERPC64:
3180                         if ( mach_o::relocatable::Reader<ppc64>::validFile(p) )
3181                                 return this->addObject(new mach_o::relocatable::Reader<ppc64>::Reader(p, info.path, info.modTime, fOptions.readerOptions(), fNextInputOrdinal), info, len);
3182                         else if ( mach_o::dylib::Reader<ppc64>::validFile(p, info.options.fBundleLoader) )
3183                                 return this->addDylib(new mach_o::dylib::Reader<ppc64>::Reader(p, len, info.path, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
3184                         else if ( archive::Reader<ppc64>::validFile(p, len) )
3185                                 return this->addArchive(new archive::Reader<ppc64>::Reader(p, len, info.path, info.modTime, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
3186                         break;
3187                 case CPU_TYPE_I386:
3188                         if ( mach_o::relocatable::Reader<x86>::validFile(p) )
3189                                 return this->addObject(new mach_o::relocatable::Reader<x86>::Reader(p, info.path, info.modTime, fOptions.readerOptions(), fNextInputOrdinal), info, len);
3190                         else if ( mach_o::dylib::Reader<x86>::validFile(p, info.options.fBundleLoader) )
3191                                 return this->addDylib(new mach_o::dylib::Reader<x86>::Reader(p, len, info.path, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
3192                         else if ( archive::Reader<x86>::validFile(p, len) )
3193                                 return this->addArchive(new archive::Reader<x86>::Reader(p, len, info.path, info.modTime, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
3194                         break;
3195                 case CPU_TYPE_X86_64:
3196                         if ( mach_o::relocatable::Reader<x86_64>::validFile(p) )
3197                                 return this->addObject(new mach_o::relocatable::Reader<x86_64>::Reader(p, info.path, info.modTime, fOptions.readerOptions(), fNextInputOrdinal), info, len);
3198                         else if ( mach_o::dylib::Reader<x86_64>::validFile(p, info.options.fBundleLoader) )
3199                                 return this->addDylib(new mach_o::dylib::Reader<x86_64>::Reader(p, len, info.path, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
3200                         else if ( archive::Reader<x86_64>::validFile(p, len) )
3201                                 return this->addArchive(new archive::Reader<x86_64>::Reader(p, len, info.path, info.modTime, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
3202                 case CPU_TYPE_ARM:
3203                         if ( mach_o::relocatable::Reader<arm>::validFile(p, objSubtypeMustMatch, fOptions.subArchitecture()) )
3204                                         return this->addObject(new mach_o::relocatable::Reader<arm>::Reader(p, info.path, info.modTime, fOptions.readerOptions(), fNextInputOrdinal), info, len);
3205                         else if ( mach_o::dylib::Reader<arm>::validFile(p, info.options.fBundleLoader) )
3206                                 return this->addDylib(new mach_o::dylib::Reader<arm>::Reader(p, len, info.path, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
3207                         else if ( archive::Reader<arm>::validFile(p, len) )
3208                                 return this->addArchive(new archive::Reader<arm>::Reader(p, len, info.path, info.modTime, info.options, fOptions.readerOptions(), fNextInputOrdinal), info, len);
3209                         break;
3210         }
3211
3212 #if LTO_SUPPORT
3213         if ( lto::Reader::validFile(p, len, fArchitecture) ) {
3214                 return this->addObject(new lto::Reader(p, len, info.path, info.modTime, fOptions.readerOptions(), fArchitecture), info, len);
3215         }
3216         else if ( !lto::Reader::loaded() && (p[0] == 'B') && (p[1] == 'C')  ) {
3217                 throw "could not process object file.  Looks like an llvm bitcode object file, but libLTO.dylib could not be loaded";
3218         }
3219 #endif
3220         // error handling
3221         if ( ((fat_header*)p)->magic == OSSwapBigToHostInt32(FAT_MAGIC) ) {
3222                 throwf("missing required architecture %s in file", fArchitectureName);
3223         }
3224         else {
3225                 throw "file is not of required architecture";
3226         }
3227 }
3228
3229 void Linker::logDylib(ObjectFile::Reader* reader, bool indirect)
3230 {
3231         if ( fOptions.readerOptions().fTraceDylibs ) {
3232                 const char* fullPath = reader->getPath();
3233                 char realName[MAXPATHLEN];
3234                 if ( realpath(fullPath, realName) != NULL )
3235                         fullPath = realName;
3236                 if ( indirect )
3237                         logTraceInfo("[Logging for XBS] Used indirect dynamic library: %s\n", fullPath);
3238                 else
3239                         logTraceInfo("[Logging for XBS] Used dynamic library: %s\n", fullPath);
3240         }
3241 }
3242
3243
3244
3245 ObjectFile::Reader* Linker::findDylib(const char* installPath, const char* fromPath)
3246 {
3247         //fprintf(stderr, "findDylib(%s, %s)\n", installPath, fromPath);
3248         InstallNameToReader::iterator pos = fDylibMap.find(installPath);
3249         if ( pos != fDylibMap.end() ) {
3250                 return pos->second;
3251         }
3252         else {
3253                 // allow -dylib_path option to override indirect library to use
3254                 for (std::vector<Options::DylibOverride>::iterator dit = fOptions.dylibOverrides().begin(); dit != fOptions.dylibOverrides().end(); ++dit) {
3255                         if ( strcmp(dit->installName,installPath) == 0 ) {\
3256                                 try {
3257                                         Options::FileInfo info = fOptions.findFile(dit->useInstead);
3258                                         ObjectFile::Reader* reader = this->createReader(info);
3259                                         fDylibMap[strdup(installPath)] = reader;
3260                                         this->logDylib(reader, true);
3261                                         return reader;
3262                                 }
3263                                 catch (const char* msg) {
3264                                         warning("ignoring -dylib_file option, %s", msg);
3265                                 }
3266                         }
3267                 }
3268                 char newPath[MAXPATHLEN];
3269                 // handle @loader_path
3270                 if ( strncmp(installPath, "@loader_path/", 13) == 0 ) {
3271                         strcpy(newPath, fromPath);
3272                         char* addPoint = strrchr(newPath,'/');
3273                         if ( addPoint != NULL )
3274                                 strcpy(&addPoint[1], &installPath[13]);
3275                         else
3276                                 strcpy(newPath, &installPath[13]);
3277                         installPath = newPath;
3278                 }
3279                 // note: @executable_path case is handled inside findFileUsingPaths()
3280                 // search for dylib using -F and -L paths
3281                 Options::FileInfo info = fOptions.findFileUsingPaths(installPath);
3282                 try {
3283                         ObjectFile::Reader* reader = this->createReader(info);
3284                         fDylibMap[strdup(installPath)] = reader;
3285                         this->logDylib(reader, true);
3286                         return reader;
3287                 }
3288                 catch (const char* msg) {
3289                         throwf("in %s, %s", info.path, msg);
3290                 }
3291         }
3292 }
3293
3294
3295 void Linker::processDylibs()
3296 {
3297         fAllDirectDylibsLoaded = true;
3298
3299         // mark all dylibs initially specified as required and check if they can be used
3300         for (InstallNameToReader::iterator it=fDylibMap.begin(); it != fDylibMap.end(); it++) {
3301                 it->second->setExplicitlyLinked();
3302                 this->checkDylibClientRestrictions(it->second);
3303         }
3304
3305         // keep processing dylibs until no more dylibs are added
3306         unsigned long lastMapSize = 0;
3307         while ( lastMapSize != fDylibMap.size() ) {
3308                 lastMapSize = fDylibMap.size();
3309                 // can't iterator fDylibMap while modifying it, so use temp buffer
3310                 std::vector<ObjectFile::Reader*> currentUnprocessedReaders;
3311                 for (InstallNameToReader::iterator it=fDylibMap.begin(); it != fDylibMap.end(); it++) {
3312                         if ( fDylibsProcessed.count(it->second) == 0 )
3313                                 currentUnprocessedReaders.push_back(it->second);
3314                 }
3315                 for (std::vector<ObjectFile::Reader*>::iterator it=currentUnprocessedReaders.begin(); it != currentUnprocessedReaders.end(); it++) {
3316                         fDylibsProcessed.insert(*it);
3317                         (*it)->processIndirectLibraries(this);
3318                 }
3319         }
3320
3321         // go back over original dylibs and mark sub frameworks as re-exported
3322         if ( fOptions.outputKind() == Options::kDynamicLibrary ) {
3323                 const char* myLeaf = strrchr(fOptions.installPath(), '/');
3324                 if ( myLeaf != NULL ) {
3325                         for (std::vector<class ObjectFile::Reader*>::iterator it=fInputFiles.begin(); it != fInputFiles.end(); it++) {
3326                                 ObjectFile::Reader* reader = *it;
3327                                 const char* childParent = reader->parentUmbrella();
3328                                 if ( childParent != NULL ) {
3329                                         if ( strcmp(childParent, &myLeaf[1]) == 0 ) {
3330                                                 // set re-export bit of info
3331                                                 std::map<ObjectFile::Reader*,LibraryOptions>::iterator pos = fDylibOptionsMap.find(reader);
3332                                                 if ( pos != fDylibOptionsMap.end() ) {
3333                                                         pos->second.fReExport = true;
3334                                                 }
3335                                         }
3336                                 }
3337                         }
3338                 }
3339         }
3340
3341 }
3342
3343
3344
3345 void Linker::createReaders()
3346 {
3347         fStartCreateReadersTime = mach_absolute_time();
3348         std::vector<Options::FileInfo>& files = fOptions.getInputFiles();
3349         const int count = files.size();
3350         if ( count == 0 )
3351                 throw "no object files specified";
3352         // add all direct object, archives, and dylibs
3353         for (int i=0; i < count; ++i) {
3354                 Options::FileInfo& entry = files[i];
3355                 // ignore /usr/lib/dyld on command line in crt.o build
3356                 if ( strcmp(entry.path, "/usr/lib/dyld") != 0 ) {
3357                         try {
3358                                 this->addInputFile(this->createReader(entry), entry);
3359                         }
3360                         catch (const char* msg) {
3361                                 if ( (strstr(msg, "architecture") != NULL) && !fOptions.errorOnOtherArchFiles() ) {
3362                                         if ( fOptions.ignoreOtherArchInputFiles() ) {
3363                                                 // ignore, because this is about an architecture not in use
3364                                         }
3365                                         else {
3366                                                 warning("in %s, %s", entry.path, msg);
3367                                         }
3368                                 }
3369                                 else {
3370                                         throwf("in %s, %s", entry.path, msg);
3371                                 }
3372                         }
3373                 }
3374         }
3375
3376         this->processDylibs();
3377 }
3378
3379
3380
3381 ObjectFile::Reader* Linker::addArchive(ObjectFile::Reader* reader, const Options::FileInfo& info, uint64_t mappedLen)
3382 {
3383         fNextInputOrdinal += mappedLen;
3384         // remember which readers are archives because they are logged differently
3385         fArchiveReaders.insert(reader);
3386
3387         // update stats
3388         fTotalArchiveSize += mappedLen;
3389         ++fTotalArchivesLoaded;
3390         return reader;
3391 }
3392
3393 ObjectFile::Reader* Linker::addObject(ObjectFile::Reader* reader, const Options::FileInfo& info, uint64_t mappedLen)
3394 {
3395         fNextInputOrdinal += mappedLen;
3396         // any .o files that don't have MH_SUBSECTIONS_VIA_SYMBOLS, that means a generated .o file can't
3397         if ( (fOptions.outputKind() == Options::kObjectFile) && !reader->canScatterAtoms() )
3398                 fCanScatter = false;
3399
3400         // update stats
3401         fTotalObjectSize += mappedLen;
3402         ++fTotalObjectLoaded;
3403         return reader;
3404 }
3405
3406
3407 void Linker::checkDylibClientRestrictions(ObjectFile::Reader* reader)
3408 {
3409         // Check for any restrictions on who can link with this dylib
3410         const char* readerParentName = reader->parentUmbrella() ;
3411         std::vector<const char*>* clients = reader->getAllowableClients();
3412         if ( (readerParentName != NULL) || (clients != NULL) ) {
3413                 // only dylibs that are in an umbrella or have a client list need verification
3414                 const char* installName = fOptions.installPath();
3415                 const char* installNameLastSlash = strrchr(installName, '/');
3416                 bool isParent = false;
3417                 bool isSibling = false;
3418                 bool isAllowableClient = false;
3419                 // There are three cases:
3420                 if ( (readerParentName != NULL) && (installNameLastSlash != NULL) ) {
3421                         // case 1) The dylib has a parent umbrella, and we are creating the parent umbrella
3422                         isParent = ( strcmp(&installNameLastSlash[1], readerParentName) == 0 );
3423
3424                         // hack to support umbrella variants that encode the variant name in the install name
3425                         // e.g. CoreServices_profile
3426                         if ( !isParent ) {
3427                                 const char* underscore = strchr(&installNameLastSlash[1], '_');
3428                                 if ( underscore != NULL ) {
3429                                         isParent = ( strncmp(&installNameLastSlash[1], readerParentName, underscore-installNameLastSlash-1) == 0 );
3430                                 }
3431                         }
3432
3433                         // case 2) The dylib has a parent umbrella, and we are creating a sibling with the same parent
3434                         isSibling = ( (fOptions.umbrellaName() != NULL) && (strcmp(fOptions.umbrellaName(), readerParentName) == 0) );
3435                 }
3436
3437                 if ( !isParent && !isSibling && (clients != NULL) ) {
3438                         // case 3) the dylib has a list of allowable clients, and we are creating one of them
3439                         const char* clientName = fOptions.clientName();
3440                         int clientNameLen = 0;
3441                         if ( clientName != NULL ) {
3442                                 // use client name as specified on command line
3443                                 clientNameLen = strlen(clientName);
3444                         }
3445                         else {
3446                                 // infer client name from output path (e.g. xxx/libfoo_variant.A.dylib --> foo, Bar.framework/Bar_variant --> Bar)
3447                                 clientName = installName;
3448                                 clientNameLen = strlen(clientName);
3449                                 // starts after last slash
3450                                 if ( installNameLastSlash != NULL )
3451                                         clientName = &installNameLastSlash[1];
3452                                 if ( strncmp(clientName, "lib", 3) == 0 )
3453                                         clientName = &clientName[3];
3454                                 // up to first dot
3455                                 const char* firstDot = strchr(clientName, '.');
3456                                 if ( firstDot != NULL )
3457                                         clientNameLen = firstDot - clientName;
3458                                 // up to first underscore
3459                                 const char* firstUnderscore = strchr(clientName, '_');
3460                                 if ( (firstUnderscore != NULL) && ((firstUnderscore - clientName) < clientNameLen) )
3461                                         clientNameLen = firstUnderscore - clientName;
3462                         }
3463
3464                         // Use clientName to check if this dylib is able to link against the allowable clients.
3465                         for (std::vector<const char*>::iterator it = clients->begin(); it != clients->end(); it++) {
3466                                 if ( strncmp(*it, clientName, clientNameLen) == 0 )
3467                                         isAllowableClient = true;
3468                         }
3469                 }
3470
3471                 if ( !isParent && !isSibling && !isAllowableClient ) {
3472                         if ( readerParentName != NULL ) {
3473                                 throwf("cannot link directly with %s.  Link against the umbrella framework '%s.framework' instead.",
3474                                         reader->getPath(), readerParentName);
3475                         }
3476                         else {
3477                                 throwf("cannot link directly with %s", reader->getPath());
3478                         }
3479                 }
3480         }
3481 }
3482
3483
3484 ObjectFile::Reader* Linker::addDylib(ObjectFile::Reader* reader, const Options::FileInfo& info, uint64_t mappedLen)
3485 {
3486         switch ( fOptions.outputKind() ) {
3487                 case Options::kDynamicExecutable:
3488                 case Options::kDynamicLibrary:
3489                 case Options::kDynamicBundle:
3490                         break;
3491                 case Options::kStaticExecutable:
3492                 case Options::kDyld:
3493                 case Options::kPreload:
3494                 case Options::kObjectFile:
3495                 case Options::kKextBundle:
3496                         warning("unexpected dylib (%s) on link line", reader->getPath());
3497                         break;
3498         }
3499
3500         fNextInputOrdinal += mappedLen;
3501         if ( (reader->getInstallPath() == NULL) && !info.options.fBundleLoader ) {
3502                 // this is a "blank" stub
3503                 // silently ignore it
3504                 return reader;
3505         }
3506         // add to map of loaded dylibs
3507         const char* installPath = reader->getInstallPath();
3508         if ( installPath != NULL ) {
3509                 InstallNameToReader::iterator pos = fDylibMap.find(installPath);
3510                 if ( pos == fDylibMap.end() ) {
3511                         fDylibMap[strdup(installPath)] = reader;
3512                 }
3513                 else {
3514                         InstallNameToReader::iterator pos2 = fDylibMap.find(reader->getPath());
3515                         if ( pos2 == fDylibMap.end() )
3516                                 fDylibMap[strdup(reader->getPath())] = reader;
3517                         else
3518                                 warning("duplicate dylib %s", reader->getPath());
3519                 }
3520         }
3521         else if ( info.options.fBundleLoader )
3522                 fBundleLoaderReader = reader;
3523
3524         // log direct readers
3525         if ( !fAllDirectDylibsLoaded )
3526                 this->logDylib(reader, false);
3527
3528         // update stats
3529         ++fTotalDylibsLoaded;
3530
3531         return reader;
3532 }
3533
3534
3535 void Linker::logTraceInfo (const char* format, ...)
3536 {
3537         static int trace_file = -1;
3538         char trace_buffer[MAXPATHLEN * 2];
3539         char *buffer_ptr;
3540         int length;
3541         ssize_t amount_written;
3542         const char *trace_file_path = fOptions.readerOptions().fTraceOutputFile;
3543
3544         if(trace_file == -1) {
3545                 if(trace_file_path != NULL) {
3546                         trace_file = open(trace_file_path, O_WRONLY | O_APPEND | O_CREAT, 0666);
3547                         if(trace_file == -1)
3548                                 throwf("Could not open or create trace file: %s", trace_file_path);
3549                 }
3550                 else {
3551                         trace_file = fileno(stderr);
3552                 }
3553         }
3554
3555     va_list ap;
3556         va_start(ap, format);
3557         length = vsnprintf(trace_buffer, sizeof(trace_buffer), format, ap);
3558         va_end(ap);
3559         buffer_ptr = trace_buffer;
3560
3561         while(length > 0) {
3562                 amount_written = write(trace_file, buffer_ptr, length);
3563                 if(amount_written == -1)
3564                         /* Failure to write shouldn't fail the build. */
3565                         return;
3566                 buffer_ptr += amount_written;
3567                 length -= amount_written;
3568         }
3569 }
3570
3571
3572
3573 void Linker::createWriter()
3574 {
3575         fStartCreateWriterTime = mach_absolute_time();
3576
3577         // make a vector out of all required dylibs in fDylibMap
3578         std::vector<ExecutableFile::DyLibUsed>  dynamicLibraries;
3579         // need to preserve command line order
3580         for (std::vector<class ObjectFile::Reader*>::iterator it=fInputFiles.begin(); it != fInputFiles.end(); it++) {
3581                 ObjectFile::Reader* reader = *it;
3582                 for (InstallNameToReader::iterator mit=fDylibMap.begin(); mit != fDylibMap.end(); mit++) {
3583                         if ( reader == mit->second ) {
3584                                 ExecutableFile::DyLibUsed dylibInfo;
3585                                 dylibInfo.reader = reader;
3586                                 dylibInfo.options = fDylibOptionsMap[reader];
3587                                 dynamicLibraries.push_back(dylibInfo);
3588                                 break;
3589                         }
3590                 }
3591         }
3592         // then add any other dylibs
3593         for (InstallNameToReader::iterator it=fDylibMap.begin(); it != fDylibMap.end(); it++) {
3594                 if ( it->second->implicitlyLinked()  ) {
3595                         // if not already in dynamicLibraries
3596                         bool alreadyInDynamicLibraries = false;
3597                         for (std::vector<ExecutableFile::DyLibUsed>::iterator dit=dynamicLibraries.begin(); dit != dynamicLibraries.end(); dit++) {
3598                                 if ( dit->reader == it->second ) {
3599                                         alreadyInDynamicLibraries = true;
3600                                         break;
3601                                 }
3602                         }
3603                         if ( ! alreadyInDynamicLibraries ) {
3604                                 ExecutableFile::DyLibUsed dylibInfo;
3605                                 dylibInfo.reader = it->second;
3606                                 std::map<ObjectFile::Reader*,LibraryOptions>::iterator pos = fDylibOptionsMap.find(it->second);
3607                                 if ( pos != fDylibOptionsMap.end() ) {
3608                                         dylibInfo.options = pos->second;
3609                                 }
3610                                 else {
3611                                         dylibInfo.options.fWeakImport = false;          // FIX ME
3612                                         dylibInfo.options.fReExport = false;
3613                                         dylibInfo.options.fBundleLoader = false;
3614                                 }
3615                                 dynamicLibraries.push_back(dylibInfo);
3616                         }
3617                 }
3618         }
3619         if ( fBundleLoaderReader != NULL ) {
3620                 ExecutableFile::DyLibUsed dylibInfo;
3621                 dylibInfo.reader = fBundleLoaderReader;
3622                 dylibInfo.options.fWeakImport = false;
3623                 dylibInfo.options.fReExport = false;
3624                 dylibInfo.options.fBundleLoader = true;
3625                 dynamicLibraries.push_back(dylibInfo);
3626         }
3627
3628         const char* path = fOptions.getOutputFilePath();
3629         switch ( fArchitecture ) {
3630                 case CPU_TYPE_POWERPC:
3631                         this->setOutputFile(new mach_o::executable::Writer<ppc>(path, fOptions, dynamicLibraries));
3632                         break;
3633                 case CPU_TYPE_POWERPC64:
3634                         this->setOutputFile(new mach_o::executable::Writer<ppc64>(path, fOptions, dynamicLibraries));
3635                         break;
3636                 case CPU_TYPE_I386:
3637                         this->setOutputFile(new mach_o::executable::Writer<x86>(path, fOptions, dynamicLibraries));
3638                         break;
3639                 case CPU_TYPE_X86_64:
3640                         this->setOutputFile(new mach_o::executable::Writer<x86_64>(path, fOptions, dynamicLibraries));
3641                         break;
3642                 case CPU_TYPE_ARM:
3643                         this->setOutputFile(new mach_o::executable::Writer<arm>(path, fOptions, dynamicLibraries));
3644                         break;
3645                 default:
3646                         throw "unknown architecture";
3647         }
3648 }
3649
3650
3651 Linker::SymbolTable::SymbolTable(Linker& owner)
3652  : fOwner(owner), fRequireCount(0), fHasExternalTentativeDefinitions(false), fHasExternalWeakDefinitions(false)
3653 {
3654 }
3655
3656 void Linker::SymbolTable::require(const char* name)
3657 {
3658         //fprintf(stderr, "require(%s)\n", name);
3659         Mapper::iterator pos = fTable.find(name);
3660         if ( pos == fTable.end() ) {
3661                 fTable[name] = NULL;
3662                 ++fRequireCount;
3663         }
3664 }
3665
3666 // convenience labels for 2-dimensional switch statement
3667 enum AllDefinitionCombinations {
3668         kRegAndReg                              = (ObjectFile::Atom::kRegularDefinition << 3)   | ObjectFile::Atom::kRegularDefinition,
3669         kRegAndWeak                             = (ObjectFile::Atom::kRegularDefinition << 3)   | ObjectFile::Atom::kWeakDefinition,
3670         kRegAndTent                             = (ObjectFile::Atom::kRegularDefinition << 3)   | ObjectFile::Atom::kTentativeDefinition,
3671         kRegAndExtern                   = (ObjectFile::Atom::kRegularDefinition << 3)   | ObjectFile::Atom::kExternalDefinition,
3672         kRegAndExternWeak               = (ObjectFile::Atom::kRegularDefinition << 3)   | ObjectFile::Atom::kExternalWeakDefinition,
3673         kRegAndAbsolute                 = (ObjectFile::Atom::kRegularDefinition << 3)   | ObjectFile::Atom::kAbsoluteSymbol,
3674         kWeakAndReg                             = (ObjectFile::Atom::kWeakDefinition << 3)              | ObjectFile::Atom::kRegularDefinition,
3675         kWeakAndWeak                    = (ObjectFile::Atom::kWeakDefinition << 3)              | ObjectFile::Atom::kWeakDefinition,
3676         kWeakAndTent                    = (ObjectFile::Atom::kWeakDefinition << 3)              | ObjectFile::Atom::kTentativeDefinition,
3677         kWeakAndExtern                  = (ObjectFile::Atom::kWeakDefinition << 3)              | ObjectFile::Atom::kExternalDefinition,
3678         kWeakAndExternWeak              = (ObjectFile::Atom::kWeakDefinition << 3)              | ObjectFile::Atom::kExternalWeakDefinition,
3679         kWeakAndAbsolute                = (ObjectFile::Atom::kWeakDefinition << 3)              | ObjectFile::Atom::kAbsoluteSymbol,
3680         kTentAndReg                             = (ObjectFile::Atom::kTentativeDefinition << 3) | ObjectFile::Atom::kRegularDefinition,
3681         kTentAndWeak                    = (ObjectFile::Atom::kTentativeDefinition << 3) | ObjectFile::Atom::kWeakDefinition,
3682         kTentAndTent                    = (ObjectFile::Atom::kTentativeDefinition << 3) | ObjectFile::Atom::kTentativeDefinition,
3683         kTentAndExtern                  = (ObjectFile::Atom::kTentativeDefinition << 3) | ObjectFile::Atom::kExternalDefinition,
3684         kTentAndExternWeak              = (ObjectFile::Atom::kTentativeDefinition << 3) | ObjectFile::Atom::kExternalWeakDefinition,
3685         kTentAndAbsolute                = (ObjectFile::Atom::kTentativeDefinition << 3) | ObjectFile::Atom::kAbsoluteSymbol,
3686         kExternAndReg                   = (ObjectFile::Atom::kExternalDefinition << 3)  | ObjectFile::Atom::kRegularDefinition,
3687         kExternAndWeak                  = (ObjectFile::Atom::kExternalDefinition << 3)  | ObjectFile::Atom::kWeakDefinition,
3688         kExternAndTent                  = (ObjectFile::Atom::kExternalDefinition << 3)  | ObjectFile::Atom::kTentativeDefinition,
3689         kExternAndExtern                = (ObjectFile::Atom::kExternalDefinition << 3)  | ObjectFile::Atom::kExternalDefinition,
3690         kExternAndExternWeak    = (ObjectFile::Atom::kExternalDefinition << 3)  | ObjectFile::Atom::kExternalWeakDefinition,
3691         kExternAndAbsolute              = (ObjectFile::Atom::kExternalDefinition << 3)  | ObjectFile::Atom::kAbsoluteSymbol,
3692         kExternWeakAndReg               = (ObjectFile::Atom::kExternalWeakDefinition << 3) | ObjectFile::Atom::kRegularDefinition,
3693         kExternWeakAndWeak              = (ObjectFile::Atom::kExternalWeakDefinition << 3) | ObjectFile::Atom::kWeakDefinition,
3694         kExternWeakAndTent              = (ObjectFile::Atom::kExternalWeakDefinition << 3) | ObjectFile::Atom::kTentativeDefinition,
3695         kExternWeakAndExtern    = (ObjectFile::Atom::kExternalWeakDefinition << 3) | ObjectFile::Atom::kExternalDefinition,
3696         kExternWeakAndExternWeak= (ObjectFile::Atom::kExternalWeakDefinition << 3) | ObjectFile::Atom::kExternalWeakDefinition,
3697         kExternWeakAndAbsolute  = (ObjectFile::Atom::kExternalWeakDefinition << 3) | ObjectFile::Atom::kAbsoluteSymbol,
3698         kAbsoluteAndReg                 = (ObjectFile::Atom::kAbsoluteSymbol << 3)              | ObjectFile::Atom::kRegularDefinition,
3699         kAbsoluteAndWeak                = (ObjectFile::Atom::kAbsoluteSymbol << 3)              | ObjectFile::Atom::kWeakDefinition,
3700         kAbsoluteAndTent                = (ObjectFile::Atom::kAbsoluteSymbol << 3)              | ObjectFile::Atom::kTentativeDefinition,
3701         kAbsoluteAndExtern              = (ObjectFile::Atom::kAbsoluteSymbol << 3)              | ObjectFile::Atom::kExternalDefinition,
3702         kAbsoluteAndExternWeak  = (ObjectFile::Atom::kAbsoluteSymbol << 3)              | ObjectFile::Atom::kExternalWeakDefinition,
3703         kAbsoluteAndAbsolute    = (ObjectFile::Atom::kAbsoluteSymbol << 3)              | ObjectFile::Atom::kAbsoluteSymbol
3704 };
3705
3706 bool Linker::SymbolTable::add(ObjectFile::Atom& newAtom)
3707 {
3708         bool useNew = true;
3709         bool checkVisibilityMismatch = false;
3710         const char* name = newAtom.getName();
3711         //fprintf(stderr, "map.add(%s => %p from %s)\n", name, &newAtom, newAtom.getFile()->getPath());
3712         Mapper::iterator pos = fTable.find(name);
3713         ObjectFile::Atom* existingAtom = NULL;
3714         if ( pos != fTable.end() )
3715                 existingAtom = pos->second;
3716         if ( existingAtom != NULL ) {
3717                 // already have atom with same name in symbol table
3718                 switch ( (AllDefinitionCombinations)((existingAtom->getDefinitionKind() << 3) | newAtom.getDefinitionKind()) ) {
3719                         case kRegAndReg:
3720                                 throwf("duplicate symbol %s in %s and %s", name, newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
3721                         case kRegAndWeak:
3722                                 // ignore new weak atom, because we already have a non-weak one
3723                                 useNew = false;
3724                                 break;
3725                         case kRegAndTent:
3726                                 // ignore new tentative atom, because we already have a regular one
3727                                 useNew = false;
3728                                 checkVisibilityMismatch = true;
3729                                 if ( newAtom.getSize() > existingAtom->getSize() ) {
3730                                         warning("for symbol %s tentative definition of size %llu from %s is "
3731                                                                         "is smaller than the real definition of size %llu from %s",
3732                                                                         newAtom.getDisplayName(), newAtom.getSize(), newAtom.getFile()->getPath(),
3733                                                                         existingAtom->getSize(), existingAtom->getFile()->getPath());
3734                                 }
3735                                 break;
3736                         case kRegAndExtern:
3737                                 // ignore external atom, because we already have a one
3738                                 useNew = false;
3739                                 break;
3740                         case kRegAndExternWeak:
3741                                 // ignore external atom, because we already have a one
3742                                 useNew = false;
3743                                 break;
3744                         case kRegAndAbsolute:
3745                                 throwf("duplicate symbol %s in %s and %s", name, newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
3746                                 break;
3747                         case kWeakAndReg:
3748                                 // replace existing weak atom with regular one
3749                                 break;
3750                         case kWeakAndWeak:
3751                                 // have another weak atom, use whichever has largest alignment requirement
3752                                 // because codegen of some client may require alignment
3753                                 useNew = ( newAtom.getAlignment().trailingZeros() > existingAtom->getAlignment().trailingZeros() );
3754                                 checkVisibilityMismatch = true;
3755                                 break;
3756                         case kWeakAndTent:
3757                                 // replace existing weak atom with tentative one ???
3758                                 break;
3759                         case kWeakAndExtern:
3760                                 // keep weak atom, at runtime external one may override
3761                                 useNew = false;
3762                                 break;
3763                         case kWeakAndExternWeak:
3764                                 // keep weak atom, at runtime external one may override
3765                                 useNew = false;
3766                                 break;
3767                         case kWeakAndAbsolute:
3768                                 // replace existing weak atom with absolute one
3769                                 break;
3770                         case kTentAndReg:
3771                                 // replace existing tentative atom with regular one
3772                                 checkVisibilityMismatch = true;
3773                                 if ( newAtom.getSize() < existingAtom->getSize() ) {
3774                                         warning("for symbol %s tentative definition of size %llu from %s is "
3775                                                                         "being replaced by a real definition of size %llu from %s",
3776                                                                         newAtom.getDisplayName(), existingAtom->getSize(), existingAtom->getFile()->getPath(),
3777                                                                         newAtom.getSize(), newAtom.getFile()->getPath());
3778                                 }
3779                                 break;
3780                         case kTentAndWeak:
3781                                 // replace existing tentative atom with weak one ???
3782                                 break;
3783                         case kTentAndTent:
3784                                 // use largest
3785                                 checkVisibilityMismatch = true;
3786                                 if ( newAtom.getSize() < existingAtom->getSize() ) {
3787                                         useNew = false;
3788                                 }
3789                                 else {
3790                                         if ( newAtom.getAlignment().trailingZeros() < existingAtom->getAlignment().trailingZeros() )
3791                                                 warning("alignment lost in merging tentative definition %s", newAtom.getDisplayName());
3792                                 }
3793                                 break;
3794                         case kTentAndExtern:
3795                         case kTentAndExternWeak:
3796                                 // a tentative definition and a dylib definition, so commons-mode decides how to handle
3797                                 switch ( fOwner.fOptions.commonsMode() ) {
3798                                         case Options::kCommonsIgnoreDylibs:
3799                                                 if ( fOwner.fOptions.warnCommons() )
3800                                                         warning("using common symbol %s from %s and ignoring defintion from dylib %s",
3801                                                                         existingAtom->getName(), existingAtom->getFile()->getPath(), newAtom.getFile()->getPath());
3802                                                 useNew = false;
3803                                                 break;
3804                                         case Options::kCommonsOverriddenByDylibs:
3805                                                 if ( fOwner.fOptions.warnCommons() )
3806                                                         warning("replacing common symbol %s from %s with true definition from dylib %s",
3807                                                                         existingAtom->getName(), existingAtom->getFile()->getPath(), newAtom.getFile()->getPath());
3808                                                 break;
3809                                         case Options::kCommonsConflictsDylibsError:
3810                                                 throwf("common symbol %s from %s conflicts with defintion from dylib %s",
3811                                                                 existingAtom->getName(), existingAtom->getFile()->getPath(), newAtom.getFile()->getPath());
3812                                 }
3813                                 break;
3814                         case kTentAndAbsolute:
3815                                 // replace tentative with absolute (can't size check because absolutes have no size)
3816                                 break;
3817                         case kExternAndReg:
3818                                 // replace external atom with regular one
3819                                 break;
3820                         case kExternAndWeak:
3821                                 // replace external atom with weak one
3822                                 break;
3823                         case kExternAndTent:
3824                                 // a tentative definition and a dylib definition, so commons-mode decides how to handle
3825                                 switch ( fOwner.fOptions.commonsMode() ) {
3826                                         case Options::kCommonsIgnoreDylibs:
3827                                                 if ( fOwner.fOptions.warnCommons() )
3828                                                         warning("using common symbol %s from %s and ignoring defintion from dylib %s",
3829                                                                         newAtom.getName(), newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
3830                                                 break;
3831                                         case Options::kCommonsOverriddenByDylibs:
3832                                                 if ( fOwner.fOptions.warnCommons() )
3833                                                         warning("replacing defintion of %s from dylib %s with common symbol from %s",
3834                                                                         newAtom.getName(), existingAtom->getFile()->getPath(), newAtom.getFile()->getPath());
3835                                                 useNew = false;
3836                                                 break;
3837                                         case Options::kCommonsConflictsDylibsError:
3838                                                 throwf("common symbol %s from %s conflicts with defintion from dylib %s",
3839                                                                         newAtom.getName(), newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
3840                                 }
3841                                 break;
3842                         case kExternAndExtern:
3843                                 throwf("duplicate symbol %s in %s and %s\n", name, newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
3844                         case kExternAndExternWeak:
3845                                 // keep strong dylib atom, ignore weak one
3846                                 useNew = false;
3847                                 break;
3848                         case kExternAndAbsolute:
3849                                 // replace external atom with absolute one
3850                                 break;
3851                         case kExternWeakAndReg:
3852                                 // replace existing weak external with regular
3853                                 break;
3854                         case kExternWeakAndWeak:
3855                                 // replace existing weak external with weak (let dyld decide at runtime which to use)
3856                                 break;
3857                         case kExternWeakAndTent:
3858                                 // a tentative definition and a dylib definition, so commons-mode decides how to handle
3859                                 switch ( fOwner.fOptions.commonsMode() ) {
3860                                         case Options::kCommonsIgnoreDylibs:
3861                                                 if ( fOwner.fOptions.warnCommons() )
3862                                                         warning("using common symbol %s from %s and ignoring defintion from dylib %s",
3863                                                                         newAtom.getName(), newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
3864                                                 break;
3865                                         case Options::kCommonsOverriddenByDylibs:
3866                                                 if ( fOwner.fOptions.warnCommons() )
3867                                                         warning("replacing defintion of %s from dylib %s with common symbol from %s",
3868                                                                         newAtom.getName(), existingAtom->getFile()->getPath(), newAtom.getFile()->getPath());
3869                                                 useNew = false;
3870                                                 break;
3871                                         case Options::kCommonsConflictsDylibsError:
3872                                                 throwf("common symbol %s from %s conflicts with defintion from dylib %s",
3873                                                                         newAtom.getName(), newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
3874                                 }
3875                                 break;
3876                         case kExternWeakAndExtern:
3877                                 // replace existing weak external with external
3878                                 break;
3879                         case kExternWeakAndExternWeak:
3880                                 // keep existing external weak
3881                                 useNew = false;
3882                                 break;
3883                         case kExternWeakAndAbsolute:
3884                                 // replace existing weak external with absolute
3885                                 break;
3886                         case kAbsoluteAndReg:
3887                                 throwf("duplicate symbol %s in %s and %s", name, newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
3888                         case kAbsoluteAndWeak:
3889                                 // ignore new weak atom, because we already have a non-weak one
3890                                 useNew = false;
3891                                 break;
3892                         case kAbsoluteAndTent:
3893                                 // ignore new tentative atom, because we already have a regular one
3894                                 useNew = false;
3895                                 break;
3896                         case kAbsoluteAndExtern:
3897                                 // ignore external atom, because we already have a one
3898                                 useNew = false;
3899                                 break;
3900                         case kAbsoluteAndExternWeak:
3901                                 // ignore external atom, because we already have a one
3902                                 useNew = false;
3903                                 break;
3904                         case kAbsoluteAndAbsolute:
3905                                 throwf("duplicate symbol %s in %s and %s", name, newAtom.getFile()->getPath(), existingAtom->getFile()->getPath());
3906                                 break;
3907                 }
3908         }
3909         if ( (existingAtom != NULL) && checkVisibilityMismatch && (newAtom.getScope() != existingAtom->getScope()) ) {
3910                 warning("%s has different visibility (%s) in %s and (%s) in %s",
3911                         newAtom.getDisplayName(), (newAtom.getScope() == 1 ? "hidden" : "default"), newAtom.getFile()->getPath(), (existingAtom->getScope()  == 1 ? "hidden" : "default"), existingAtom->getFile()->getPath());
3912         }
3913         if ( useNew ) {
3914                 fTable[name] = &newAtom;
3915                 if ( existingAtom != NULL ) {
3916                         fOwner.markDead(existingAtom);
3917                         if ( fOwner.fInitialLoadsDone ) {
3918                                 //fprintf(stderr, "existing %p %s overridden by %p\n", existingAtom, existingAtom->getName(), &newAtom);
3919                                 fOwner.fAtomsOverriddenByLateLoads.insert(existingAtom);
3920                         }
3921                 }
3922                 if ( newAtom.getScope() == ObjectFile::Atom::scopeGlobal ) {
3923                         switch ( newAtom.getDefinitionKind() ) {
3924                                 case ObjectFile::Atom::kTentativeDefinition:
3925                                         fHasExternalTentativeDefinitions = true;
3926                                         ++fRequireCount; // added a tentative definition means loadUndefines() needs to continue
3927                                         break;
3928                                 case ObjectFile::Atom::kWeakDefinition:
3929                                         fHasExternalWeakDefinitions = true;
3930                                         break;
3931                                 default:
3932                                         break;
3933                         }
3934                 }
3935         }
3936         else {
3937                 fOwner.markDead(&newAtom);
3938         }
3939         return useNew;
3940 }
3941
3942
3943
3944 ObjectFile::Atom* Linker::SymbolTable::find(const char* name)
3945 {
3946         Mapper::iterator pos = fTable.find(name);
3947         if ( pos != fTable.end() ) {
3948                 return pos->second;
3949         }
3950         return NULL;
3951 }
3952
3953
3954 void Linker::SymbolTable::getUndefinesNames(std::vector<const char*>& undefines)
3955 {
3956         for (Mapper::iterator it=fTable.begin(); it != fTable.end(); it++) {
3957                 if ( it->second == NULL ) {
3958                         undefines.push_back(it->first);
3959                 }
3960         }
3961 }
3962
3963 void Linker::SymbolTable::getTentativesNames(std::vector<const char*>& tents)
3964 {
3965         for (Mapper::iterator it=fTable.begin(); it != fTable.end(); it++) {
3966                 if ( it->second != NULL ) {
3967                         if ( (it->second->getDefinitionKind() == ObjectFile::Atom::kTentativeDefinition)
3968                                  && (it->second->getScope() == ObjectFile::Atom::scopeGlobal) ) {
3969                                     tents.push_back(it->first);
3970                         }
3971                 }
3972         }
3973 }
3974
3975
3976
3977 bool Linker::AtomSorter::operator()(const ObjectFile::Atom* left, const ObjectFile::Atom* right)
3978 {
3979         if ( left == right )
3980                 return false;
3981
3982         // first sort by section order (which is already sorted by segment)
3983         unsigned int leftSectionIndex  =  left->getSection()->getIndex();
3984         unsigned int rightSectionIndex = right->getSection()->getIndex();
3985         if ( leftSectionIndex != rightSectionIndex)
3986                 return (leftSectionIndex < rightSectionIndex);
3987
3988         // if a -order_file is specified, then sorting is altered to sort those symbols first
3989         if ( fOverriddenOrdinalMap != NULL ) {
3990                 std::map<const ObjectFile::Atom*, uint32_t>::iterator leftPos  = fOverriddenOrdinalMap->find(left);
3991                 std::map<const ObjectFile::Atom*, uint32_t>::iterator rightPos = fOverriddenOrdinalMap->find(right);
3992                 std::map<const ObjectFile::Atom*, uint32_t>::iterator end = fOverriddenOrdinalMap->end();
3993                 if ( leftPos != end ) {
3994                         if ( rightPos != end ) {
3995                                 // both left and right are overridden, so compare overridden ordinals
3996                                 return leftPos->second < rightPos->second;
3997                         }
3998                         else {
3999                                 // left is overridden and right is not, so left < right
4000                                 return true;
4001                         }
4002                 }
4003                 else {
4004                         if ( rightPos != end ) {
4005                                 // right is overridden and left is not, so right < left
4006                                 return false;
4007                         }
4008                         else {
4009                                 // neither are overridden, do default sort
4010                                 // fall into default sorting below
4011                         }
4012                 }
4013         }
4014
4015         // the __common section can have real or tentative definitions
4016         // we want the real ones to sort before tentative ones
4017         bool leftIsTent  =  (left->getDefinitionKind() == ObjectFile::Atom::kTentativeDefinition);
4018         bool rightIsTent =  (right->getDefinitionKind() == ObjectFile::Atom::kTentativeDefinition);
4019         if ( leftIsTent != rightIsTent )
4020                 return rightIsTent;
4021
4022         // initializers are auto sorted to start of section
4023         if ( !fInitializerSet.empty() ) {
4024                 bool leftFirst  = (fInitializerSet.count(left) != 0);
4025                 bool rightFirst = (fInitializerSet.count(right) != 0);
4026                 if ( leftFirst != rightFirst )
4027                         return leftFirst;
4028         }
4029
4030         // terminators are auto sorted to end of section
4031         if ( !fTerminatorSet.empty() ) {
4032                 bool leftLast  = (fTerminatorSet.count(left) != 0);
4033                 bool rightLast = (fTerminatorSet.count(right) != 0);
4034                 if ( leftLast != rightLast )
4035                         return rightLast;
4036         }
4037
4038         // lastly sort by atom ordinal.  this is already sorted by .o order
4039         return left->getOrdinal() < right->getOrdinal();
4040 }
4041
4042
4043 int main(int argc, const char* argv[])
4044 {
4045         const char* archName = NULL;
4046         bool showArch = false;
4047         bool archInferred = false;
4048         try {
4049                 // create linker object given command line arguments
4050                 Linker ld(argc, argv);
4051
4052                 // save error message prefix
4053                 archName = ld.architectureName();
4054                 archInferred = ld.isInferredArchitecture();
4055                 showArch = ld.showArchitectureInErrors();
4056
4057                 // open all input files
4058                 ld.createReaders();
4059
4060                 // open output file
4061                 ld.createWriter();
4062
4063                 // do linking
4064                 ld.link();
4065         }
4066         catch (const char* msg) {
4067                 if ( archInferred )
4068                         fprintf(stderr, "ld: %s for inferred architecture %s\n", msg, archName);
4069                 else if ( showArch )
4070                         fprintf(stderr, "ld: %s for architecture %s\n", msg, archName);
4071                 else
4072                         fprintf(stderr, "ld: %s\n", msg);
4073                 return 1;
4074         }
4075
4076         return 0;
4077 }