src/ld/Resolver.cpp

   1 /* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-*
   2  *
   3  * Copyright (c) 2009-2010 Apple Inc. All rights reserved.
   4  *
   5  * @APPLE_LICENSE_HEADER_START@
   6  *
   7  * This file contains Original Code and/or Modifications of Original Code
   8  * as defined in and that are subject to the Apple Public Source License
   9  * Version 2.0 (the 'License'). You may not use this file except in
  10  * compliance with the License. Please obtain a copy of the License at
  11  * http://www.opensource.apple.com/apsl/ and read it before using this
  12  * file.
  13  *
  14  * The Original Code and all software distributed under the License are
  15  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  16  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  17  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  19  * Please see the License for the specific language governing rights and
  20  * limitations under the License.
  21  *
  22  * @APPLE_LICENSE_HEADER_END@
  23  */
  24
  25
  26 #include <stdlib.h>
  27 #include <sys/types.h>
  28 #include <sys/stat.h>
  29 #include <sys/mman.h>
  30 #include <sys/sysctl.h>
  31 #include <fcntl.h>
  32 #include <errno.h>
  33 #include <limits.h>
  34 #include <unistd.h>
  35 #include <mach/mach_time.h>
  36 #include <mach/vm_statistics.h>
  37 #include <mach/mach_init.h>
  38 #include <mach/mach_host.h>
  39 #include <dlfcn.h>
  40 #include <mach-o/dyld.h>
  41 #include <mach-o/fat.h>
  42
  43 #include <string>
  44 #include <map>
  45 #include <set>
  46 #include <string>
  47 #include <vector>
  48 #include <list>
  49 #include <algorithm>
  50 #include <dlfcn.h>
  51 #include <AvailabilityMacros.h>
  52
  53 #include "Options.h"
  54
  55 #include "ld.hpp"
  56 #include "InputFiles.h"
  57 #include "SymbolTable.h"
  58 #include "Resolver.h"
  59 #include "parsers/lto_file.h"
  60
  61
  62 namespace ld {
  63 namespace tool {
  64
  65
  66 //
  67 // An ExportAtom has no content.  It exists so that the linker can track which imported
  68 // symbols came from which dynamic libraries.
  69 //
  70 class UndefinedProxyAtom : public ld::Atom
  71 {
  72 public:
  73                                                                                         UndefinedProxyAtom(const char* nm)
  74                                                                                                 : ld::Atom(_s_section, ld::Atom::definitionProxy,
  75                                                                                                         ld::Atom::combineNever, ld::Atom::scopeLinkageUnit,
  76                                                                                                         ld::Atom::typeUnclassified,
  77                                                                                                         ld::Atom::symbolTableIn, false, false, false, ld::Atom::Alignment(0)),
  78                                                                                                         _name(nm) {}
  79         // overrides of ld::Atom
  80         virtual const ld::File*                                         file() const            { return NULL; }
  81         virtual const char*                                                     name() const            { return _name; }
  82         virtual uint64_t                                                        size() const            { return 0; }
  83         virtual uint64_t                                                        objectAddress() const { return 0; }
  84         virtual void                                                            copyRawContent(uint8_t buffer[]) const { }
  85         virtual void                                                            setScope(Scope)         { }
  86
  87 protected:
  88
  89         virtual                                                                 ~UndefinedProxyAtom() {}
  90
  91         const char*                                                             _name;
  92
  93         static ld::Section                                              _s_section;
  94 };
  95
  96 ld::Section UndefinedProxyAtom::_s_section("__TEXT", "__import", ld::Section::typeImportProxies, true);
  97
  98
  99
 100
 101 class AliasAtom : public ld::Atom
 102 {
 103 public:
 104                                                                                 AliasAtom(const ld::Atom& target, const char* nm) :
 105                                                                                         ld::Atom(target.section(), target.definition(), ld::Atom::combineNever,
 106                                                                                                         ld::Atom::scopeGlobal, target.contentType(),
 107                                                                                                         target.symbolTableInclusion(), target.dontDeadStrip(),
 108                                                                                                         target.isThumb(), true, target.alignment()),
 109                                                                                         _name(nm),
 110                                                                                         _aliasOf(target),
 111                                                                                         _fixup(0, ld::Fixup::k1of1, ld::Fixup::kindNoneFollowOn, &target) { }
 112
 113         // overrides of ld::Atom
 114         virtual const ld::File*                         file() const            { return _aliasOf.file(); }
 115         virtual const char*                                             translationUnitSource() const
 116                                                                                                                         { return _aliasOf.translationUnitSource(); }
 117         virtual const char*                                     name() const            { return _name; }
 118         virtual uint64_t                                        size() const            { return 0; }
 119         virtual uint64_t                                        objectAddress() const { return _aliasOf.objectAddress(); }
 120         virtual void                                            copyRawContent(uint8_t buffer[]) const { }
 121         virtual const uint8_t*                          rawContentPointer() const { return NULL; }
 122         virtual unsigned long                           contentHash(const class ld::IndirectBindingTable& ibt) const
 123                                                                                                                         { return _aliasOf.contentHash(ibt);  }
 124         virtual bool                                            canCoalesceWith(const ld::Atom& rhs, const class ld::IndirectBindingTable& ibt) const
 125                                                                                                                         { return _aliasOf.canCoalesceWith(rhs,ibt); }
 126         virtual ld::Fixup::iterator                             fixupsBegin() const     { return (ld::Fixup*)&_fixup; }
 127         virtual ld::Fixup::iterator                             fixupsEnd()     const   { return &((ld::Fixup*)&_fixup)[1]; }
 128         virtual ld::Atom::UnwindInfo::iterator  beginUnwind() const { return  NULL; }
 129         virtual ld::Atom::UnwindInfo::iterator  endUnwind() const       { return NULL; }
 130         virtual ld::Atom::LineInfo::iterator    beginLineInfo() const { return  NULL; }
 131         virtual ld::Atom::LineInfo::iterator    endLineInfo() const { return NULL; }
 132
 133         void                                                                    setFinalAliasOf() const {
 134                                                                                                 (const_cast<AliasAtom*>(this))->setAttributesFromAtom(_aliasOf);
 135                                                                                         }
 136
 137 private:
 138         const char*                                                     _name;
 139         const ld::Atom&                                         _aliasOf;
 140         ld::Fixup                                                       _fixup;
 141 };
 142
 143
 144
 145 class SectionBoundaryAtom : public ld::Atom
 146 {
 147 public:
 148         static SectionBoundaryAtom*                     makeSectionBoundaryAtom(const char* name, bool start, const char* segSectName);
 149         static SectionBoundaryAtom*                     makeOldSectionBoundaryAtom(const char* name, bool start);
 150
 151         // overrides of ld::Atom
 152         virtual const ld::File*                         file() const            { return NULL; }
 153         virtual const char*                                     name() const            { return _name; }
 154         virtual uint64_t                                        size() const            { return 0; }
 155         virtual void                                            copyRawContent(uint8_t buffer[]) const { }
 156         virtual const uint8_t*                          rawContentPointer() const { return NULL; }
 157         virtual uint64_t                                        objectAddress() const { return 0; }
 158
 159 private:
 160
 161                                                                                 SectionBoundaryAtom(const char* nm, const ld::Section& sect,
 162                                                                                                                         ld::Atom::ContentType cont) :
 163                                                                                         ld::Atom(sect,
 164                                                                                                         ld::Atom::definitionRegular,
 165                                                                                                         ld::Atom::combineNever,
 166                                                                                                         ld::Atom::scopeLinkageUnit,
 167                                                                                                         cont,
 168                                                                                                         ld::Atom::symbolTableNotIn,
 169                                                                                                         false, false, true, ld::Atom::Alignment(0)),
 170                                                                                         _name(nm) { }
 171
 172         const char*                                                     _name;
 173 };
 174
 175 SectionBoundaryAtom* SectionBoundaryAtom::makeSectionBoundaryAtom(const char* name, bool start, const char* segSectName)
 176 {
 177
 178         const char* segSectDividor = strrchr(segSectName, '$');
 179         if ( segSectDividor == NULL )
 180                 throwf("malformed section$ symbol name: %s", name);
 181         const char* sectionName = segSectDividor + 1;
 182         int segNameLen = segSectDividor - segSectName;
 183         if ( segNameLen > 16 )
 184                 throwf("malformed section$ symbol name: %s", name);
 185         char segName[18];
 186         strlcpy(segName, segSectName, segNameLen+1);
 187
 188         const ld::Section* section = new ld::Section(strdup(segName), sectionName, ld::Section::typeUnclassified);
 189         return new SectionBoundaryAtom(name, *section, (start ? ld::Atom::typeSectionStart : typeSectionEnd));
 190 }
 191
 192 SectionBoundaryAtom* SectionBoundaryAtom::makeOldSectionBoundaryAtom(const char* name, bool start)
 193 {
 194         // e.g. __DATA__bss__begin
 195         char segName[18];
 196         strlcpy(segName, name, 7);
 197
 198         char sectName[18];
 199         int nameLen = strlen(name);
 200         strlcpy(sectName, &name[6], (start ? nameLen-12 : nameLen-10));
 201         warning("grandfathering in old symbol '%s' as alias for 'section$%s$%s$%s'", name, start ? "start" : "end", segName, sectName);
 202         const ld::Section* section = new ld::Section(strdup(segName), strdup(sectName), ld::Section::typeUnclassified);
 203         return new SectionBoundaryAtom(name, *section, (start ? ld::Atom::typeSectionStart : typeSectionEnd));
 204 }
 205
 206
 207
 208
 209 class SegmentBoundaryAtom : public ld::Atom
 210 {
 211 public:
 212         static SegmentBoundaryAtom*                     makeSegmentBoundaryAtom(const char* name, bool start, const char* segName);
 213         static SegmentBoundaryAtom*                     makeOldSegmentBoundaryAtom(const char* name, bool start);
 214
 215         // overrides of ld::Atom
 216         virtual const ld::File*                         file() const            { return NULL; }
 217         virtual const char*                                     name() const            { return _name; }
 218         virtual uint64_t                                        size() const            { return 0; }
 219         virtual void                                            copyRawContent(uint8_t buffer[]) const { }
 220         virtual const uint8_t*                          rawContentPointer() const { return NULL; }
 221         virtual uint64_t                                        objectAddress() const { return 0; }
 222
 223 private:
 224
 225                                                                                 SegmentBoundaryAtom(const char* nm, const ld::Section& sect,
 226                                                                                                                         ld::Atom::ContentType cont) :
 227                                                                                         ld::Atom(sect,
 228                                                                                                         ld::Atom::definitionRegular,
 229                                                                                                         ld::Atom::combineNever,
 230                                                                                                         ld::Atom::scopeLinkageUnit,
 231                                                                                                         cont,
 232                                                                                                         ld::Atom::symbolTableNotIn,
 233                                                                                                         false, false, true, ld::Atom::Alignment(0)),
 234                                                                                         _name(nm) { }
 235
 236         const char*                                                     _name;
 237 };
 238
 239 SegmentBoundaryAtom* SegmentBoundaryAtom::makeSegmentBoundaryAtom(const char* name, bool start, const char* segName)
 240 {
 241         if ( *segName == '\0' )
 242                 throwf("malformed segment$ symbol name: %s", name);
 243         if ( strlen(segName) > 16 )
 244                 throwf("malformed segment$ symbol name: %s", name);
 245
 246         if ( start ) {
 247                 const ld::Section* section = new ld::Section(segName, "__start", ld::Section::typeFirstSection, true);
 248                 return new SegmentBoundaryAtom(name, *section, ld::Atom::typeSectionStart);
 249         }
 250         else {
 251                 const ld::Section* section = new ld::Section(segName, "__end", ld::Section::typeLastSection, true);
 252                 return new SegmentBoundaryAtom(name, *section, ld::Atom::typeSectionEnd);
 253         }
 254 }
 255
 256 SegmentBoundaryAtom* SegmentBoundaryAtom::makeOldSegmentBoundaryAtom(const char* name, bool start)
 257 {
 258         // e.g. __DATA__begin
 259         char temp[18];
 260         strlcpy(temp, name, 7);
 261         char* segName = strdup(temp);
 262
 263         warning("grandfathering in old symbol '%s' as alias for 'segment$%s$%s'", name, start ? "start" : "end", segName);
 264
 265         if ( start ) {
 266                 const ld::Section* section = new ld::Section(segName, "__start", ld::Section::typeFirstSection, true);
 267                 return new SegmentBoundaryAtom(name, *section, ld::Atom::typeSectionStart);
 268         }
 269         else {
 270                 const ld::Section* section = new ld::Section(segName, "__end", ld::Section::typeLastSection, true);
 271                 return new SegmentBoundaryAtom(name, *section, ld::Atom::typeSectionEnd);
 272         }
 273 }
 274
 275 void Resolver::initializeState()
 276 {
 277         // set initial objc constraint based on command line options
 278         if ( _options.objcGc() )
 279                 _internal.objcObjectConstraint = ld::File::objcConstraintRetainReleaseOrGC;
 280         else if ( _options.objcGcOnly() )
 281                 _internal.objcObjectConstraint = ld::File::objcConstraintGC;
 282
 283         _internal.cpuSubType = _options.subArchitecture();
 284 }
 285
 286 void Resolver::buildAtomList()
 287 {
 288         // each input files contributes initial atoms
 289         _atoms.reserve(1024);
 290         _inputFiles.forEachInitialAtom(*this);
 291
 292         _completedInitialObjectFiles = true;
 293
 294         //_symbolTable.printStatistics();
 295 }
 296
 297
 298 void Resolver::doFile(const ld::File& file)
 299 {
 300         const ld::relocatable::File* objFile = dynamic_cast<const ld::relocatable::File*>(&file);
 301         const ld::dylib::File* dylibFile = dynamic_cast<const ld::dylib::File*>(&file);
 302
 303         if ( objFile != NULL ) {
 304                 // update which form of ObjC is being used
 305                 switch ( file.objCConstraint() ) {
 306                         case ld::File::objcConstraintNone:
 307                                 break;
 308                         case ld::File::objcConstraintRetainRelease:
 309                                 if ( _internal.objcObjectConstraint == ld::File::objcConstraintGC )
 310                                         throwf("%s built with incompatible Garbage Collection settings to link with previous .o files", file.path());
 311                                 if ( _options.objcGcOnly() )
 312                                         throwf("command line specified -objc_gc_only, but file is retain/release based: %s", file.path());
 313                                 if ( _options.objcGc() )
 314                                         throwf("command line specified -objc_gc, but file is retain/release based: %s", file.path());
 315                                 _internal.objcObjectConstraint = ld::File::objcConstraintRetainRelease;
 316                                 break;
 317                         case ld::File::objcConstraintRetainReleaseOrGC:
 318                                 if ( _internal.objcObjectConstraint == ld::File::objcConstraintNone )
 319                                         _internal.objcObjectConstraint = ld::File::objcConstraintRetainReleaseOrGC;
 320                                 break;
 321                         case ld::File::objcConstraintGC:
 322                                 if ( _internal.objcObjectConstraint == ld::File::objcConstraintRetainRelease )
 323                                         throwf("%s built with incompatible Garbage Collection settings to link with previous .o files", file.path());
 324                                 _internal.objcObjectConstraint = ld::File::objcConstraintGC;
 325                                 break;
 326                 }
 327
 328                 // in -r mode, if any .o files have dwarf then add UUID to output .o file
 329                 if ( objFile->debugInfo() == ld::relocatable::File::kDebugInfoDwarf )
 330                         _internal.someObjectFileHasDwarf = true;
 331
 332                 // remember if any .o file did not have MH_SUBSECTIONS_VIA_SYMBOLS bit set
 333                 if ( ! objFile->canScatterAtoms() )
 334                         _internal.allObjectFilesScatterable = false;
 335
 336                 // update cpu-sub-type
 337                 cpu_subtype_t nextObjectSubType = file.cpuSubType();
 338                 switch ( _options.architecture() ) {
 339                         case CPU_TYPE_ARM:
 340                                 if ( _options.subArchitecture() != nextObjectSubType ) {
 341                                         if ( (_options.subArchitecture() == CPU_SUBTYPE_ARM_ALL) && _options.forceCpuSubtypeAll() ) {
 342                                                 // hack to support gcc multillib build that tries to make sub-type-all slice
 343                                         }
 344                                         else if ( nextObjectSubType == CPU_SUBTYPE_ARM_ALL ) {
 345                                                 warning("CPU_SUBTYPE_ARM_ALL subtype is deprecated: %s", file.path());
 346                                         }
 347                                         else if ( _options.allowSubArchitectureMismatches() ) {
 348                                                 //warning("object file %s was built for different arm sub-type (%d) than link command line (%d)",
 349                                                 //      file.path(), nextObjectSubType, _options.subArchitecture());
 350                                         }
 351                                         else {
 352                                                 throwf("object file %s was built for different arm sub-type (%d) than link command line (%d)",
 353                                                         file.path(), nextObjectSubType, _options.subArchitecture());
 354                                         }
 355                                 }
 356                                 break;
 357
 358                         case CPU_TYPE_I386:
 359                                 _internal.cpuSubType = CPU_SUBTYPE_I386_ALL;
 360                                 break;
 361
 362                         case CPU_TYPE_X86_64:
 363                                 _internal.cpuSubType = CPU_SUBTYPE_X86_64_ALL;
 364                                 break;
 365                 }
 366         }
 367         if ( dylibFile != NULL ) {
 368                 // update which form of ObjC dylibs are being linked
 369                 switch ( dylibFile->objCConstraint() ) {
 370                         case ld::File::objcConstraintNone:
 371                                 break;
 372                         case ld::File::objcConstraintRetainRelease:
 373                                 if ( _internal.objcDylibConstraint == ld::File::objcConstraintGC )
 374                                         throwf("%s built with incompatible Garbage Collection settings to link with previous dylibs", file.path());
 375                                 if ( _options.objcGcOnly() )
 376                                         throwf("command line specified -objc_gc_only, but dylib is retain/release based: %s", file.path());
 377                                 if ( _options.objcGc() )
 378                                         throwf("command line specified -objc_gc, but dylib is retain/release based: %s", file.path());
 379                                 _internal.objcDylibConstraint = ld::File::objcConstraintRetainRelease;
 380                                 break;
 381                         case ld::File::objcConstraintRetainReleaseOrGC:
 382                                 if ( _internal.objcDylibConstraint == ld::File::objcConstraintNone )
 383                                         _internal.objcDylibConstraint = ld::File::objcConstraintRetainReleaseOrGC;
 384                                 break;
 385                         case ld::File::objcConstraintGC:
 386                                 if ( _internal.objcDylibConstraint == ld::File::objcConstraintRetainRelease )
 387                                         throwf("%s built with incompatible Garbage Collection settings to link with previous dylibs", file.path());
 388                                 _internal.objcDylibConstraint = ld::File::objcConstraintGC;
 389                                 break;
 390                 }
 391         }
 392
 393 }
 394
 395 void Resolver::doAtom(const ld::Atom& atom)
 396 {
 397         //fprintf(stderr, "Resolver::doAtom(%p), name=%s, sect=%s\n", &atom, atom.name(), atom.section().sectionName());
 398
 399         // add to list of known atoms
 400         _atoms.push_back(&atom);
 401
 402         // adjust scope
 403         if ( _options.hasExportRestrictList() || _options.hasReExportList() ) {
 404                 const char* name = atom.name();
 405                 switch ( atom.scope() ) {
 406                         case ld::Atom::scopeTranslationUnit:
 407                                 break;
 408                         case ld::Atom::scopeLinkageUnit:
 409                                 if ( _options.hasExportMaskList() && _options.shouldExport(name) ) {
 410                                         // <rdar://problem/5062685> ld does not report error when -r is used and exported symbols are not defined.
 411                                         if ( _options.outputKind() == Options::kObjectFile )
 412                                                 throwf("cannot export hidden symbol %s", name);
 413                                         // .objc_class_name_* symbols are special
 414                                         if ( atom.section().type() != ld::Section::typeObjC1Classes ) {
 415                                                 if ( atom.definition() == ld::Atom::definitionProxy ) {
 416                                                         // .exp file says to export a symbol, but that symbol is in some dylib being linked
 417                                                         if ( _options.canReExportSymbols() ) {
 418                                                                 // marking proxy atom as global triggers the re-export
 419                                                                 (const_cast<ld::Atom*>(&atom))->setScope(ld::Atom::scopeGlobal);
 420                                                         }
 421                                                         else if ( _options.outputKind() == Options::kDynamicLibrary ) {
 422                                                                 if ( atom.file() != NULL )
 423                                                                         warning("target OS does not support re-exporting symbol %s from %s\n", _options.demangleSymbol(name), atom.file()->path());
 424                                                                 else
 425                                                                         warning("target OS does not support re-exporting symbol %s\n", _options.demangleSymbol(name));
 426                                                         }
 427                                                 }
 428                                                 else {
 429                                                         if ( atom.file() != NULL )
 430                                                                 warning("cannot export hidden symbol %s from %s", _options.demangleSymbol(name), atom.file()->path());
 431                                                         else
 432                                                                 warning("cannot export hidden symbol %s", _options.demangleSymbol(name));
 433                                                 }
 434                                         }
 435                                 }
 436                                 else if ( _options.shouldReExport(name) && _options.canReExportSymbols() ) {
 437                                         if ( atom.definition() == ld::Atom::definitionProxy ) {
 438                                                 // marking proxy atom as global triggers the re-export
 439                                                 (const_cast<ld::Atom*>(&atom))->setScope(ld::Atom::scopeGlobal);
 440                                         }
 441                                         else {
 442                                                 throwf("requested re-export symbol %s is not from a dylib, but from %s\n", _options.demangleSymbol(name), atom.file()->path());
 443                                         }
 444                                 }
 445                                 break;
 446                         case ld::Atom::scopeGlobal:
 447                                 // check for globals that are downgraded to hidden
 448                                 if ( ! _options.shouldExport(name) ) {
 449                                         (const_cast<ld::Atom*>(&atom))->setScope(ld::Atom::scopeLinkageUnit);
 450                                         //fprintf(stderr, "demote %s to hidden\n", name);
 451                                 }
 452                                 if ( _options.canReExportSymbols() && _options.shouldReExport(name) ) {
 453                                         throwf("requested re-export symbol %s is not from a dylib, but from %s\n", _options.demangleSymbol(name), atom.file()->path());
 454                                 }
 455                                 break;
 456                 }
 457         }
 458
 459         // work around for kernel that uses 'l' labels in assembly code
 460         if ( (atom.symbolTableInclusion() == ld::Atom::symbolTableNotInFinalLinkedImages)
 461                         && (atom.name()[0] == 'l') && (_options.outputKind() == Options::kStaticExecutable)
 462                         && (strncmp(atom.name(), "ltmp", 4) != 0) )
 463                 (const_cast<ld::Atom*>(&atom))->setSymbolTableInclusion(ld::Atom::symbolTableIn);
 464
 465
 466         // tell symbol table about non-static atoms
 467         if ( atom.scope() != ld::Atom::scopeTranslationUnit ) {
 468                 _symbolTable.add(atom, _options.deadCodeStrip() && _completedInitialObjectFiles);
 469
 470                 // add symbol aliases defined on the command line
 471                 if ( _options.haveCmdLineAliases() ) {
 472                         const std::vector<Options::AliasPair>& aliases = _options.cmdLineAliases();
 473                         for (std::vector<Options::AliasPair>::const_iterator it=aliases.begin(); it != aliases.end(); ++it) {
 474                                 if ( strcmp(it->realName, atom.name()) == 0 ) {
 475                                         const AliasAtom* alias = new AliasAtom(atom, it->alias);
 476                                         _aliasesFromCmdLine.push_back(alias);
 477                                         this->doAtom(*alias);
 478                                 }
 479                         }
 480                 }
 481         }
 482
 483         // convert references by-name or by-content to by-slot
 484         this->convertReferencesToIndirect(atom);
 485
 486         // remember if any atoms are proxies that require LTO
 487         if ( atom.contentType() == ld::Atom::typeLTOtemporary )
 488                 _haveLLVMObjs = true;
 489
 490         if ( _options.deadCodeStrip() ) {
 491                 // add to set of dead-strip-roots, all symbols that the compiler marks as don't strip
 492                 if ( atom.dontDeadStrip() )
 493                         _deadStripRoots.insert(&atom);
 494
 495                 if ( atom.scope() == ld::Atom::scopeGlobal ) {
 496                         // <rdar://problem/5524973> -exported_symbols_list that has wildcards and -dead_strip
 497                         // in dylibs, every global atom in initial .o files is a root
 498                         if ( _options.hasWildCardExportRestrictList() || _options.allGlobalsAreDeadStripRoots() ) {
 499                                 if ( _options.shouldExport(atom.name()) )
 500                                         _deadStripRoots.insert(&atom);
 501                         }
 502                 }
 503         }
 504 }
 505
 506 bool Resolver::isDtraceProbe(ld::Fixup::Kind kind)
 507 {
 508         switch (kind) {
 509                 case ld::Fixup::kindStoreX86DtraceCallSiteNop:
 510                 case ld::Fixup::kindStoreX86DtraceIsEnableSiteClear:
 511                 case ld::Fixup::kindStoreARMDtraceCallSiteNop:
 512                 case ld::Fixup::kindStoreARMDtraceIsEnableSiteClear:
 513                 case ld::Fixup::kindStoreThumbDtraceCallSiteNop:
 514                 case ld::Fixup::kindStoreThumbDtraceIsEnableSiteClear:
 515                 case ld::Fixup::kindDtraceExtra:
 516                         return true;
 517                 default:
 518                         break;
 519         }
 520         return false;
 521 }
 522
 523 void Resolver::convertReferencesToIndirect(const ld::Atom& atom)
 524 {
 525         // convert references by-name or by-content to by-slot
 526         SymbolTable::IndirectBindingSlot slot;
 527         const ld::Atom* dummy;
 528         ld::Fixup::iterator end = atom.fixupsEnd();
 529         for (ld::Fixup::iterator fit=atom.fixupsBegin(); fit != end; ++fit) {
 530                 switch ( fit->binding ) {
 531                         case ld::Fixup::bindingByNameUnbound:
 532                                 if ( isDtraceProbe(fit->kind) && (_options.outputKind() != Options::kObjectFile ) ) {
 533                                         // in final linked images, remove reference
 534                                         fit->binding = ld::Fixup::bindingNone;
 535                                 }
 536                                 else {
 537                                         slot = _symbolTable.findSlotForName(fit->u.name);
 538                                         fit->binding = ld::Fixup::bindingsIndirectlyBound;
 539                                         fit->u.bindingIndex = slot;
 540                                 }
 541                                 break;
 542                         case ld::Fixup::bindingByContentBound:
 543                                 switch ( fit->u.target->combine() ) {
 544                                         case ld::Atom::combineNever:
 545                                         case ld::Atom::combineByName:
 546                                                 assert(0 && "wrong combine type for bind by content");
 547                                                 break;
 548                                         case ld::Atom::combineByNameAndContent:
 549                                                 slot = _symbolTable.findSlotForContent(fit->u.target, &dummy);
 550                                                 fit->binding = ld::Fixup::bindingsIndirectlyBound;
 551                                                 fit->u.bindingIndex = slot;
 552                                                 break;
 553                                         case ld::Atom::combineByNameAndReferences:
 554                                                 slot = _symbolTable.findSlotForReferences(fit->u.target, &dummy);
 555                                                 fit->binding = ld::Fixup::bindingsIndirectlyBound;
 556                                                 fit->u.bindingIndex = slot;
 557                                                 break;
 558                                 }
 559                                 break;
 560                         case ld::Fixup::bindingNone:
 561                         case ld::Fixup::bindingDirectlyBound:
 562                         case ld::Fixup::bindingsIndirectlyBound:
 563                                 break;
 564                 }
 565         }
 566 }
 567
 568
 569 void Resolver::addInitialUndefines()
 570 {
 571         // add initial undefines from -u option
 572         for (Options::UndefinesIterator it=_options.initialUndefinesBegin(); it != _options.initialUndefinesEnd(); ++it) {
 573                 _symbolTable.findSlotForName(*it);
 574         }
 575 }
 576
 577 void Resolver::resolveUndefines()
 578 {
 579         // keep looping until no more undefines were added in last loop
 580         unsigned int undefineGenCount = 0xFFFFFFFF;
 581         while ( undefineGenCount != _symbolTable.updateCount() ) {
 582                 undefineGenCount = _symbolTable.updateCount();
 583                 std::vector<const char*> undefineNames;
 584                 _symbolTable.undefines(undefineNames);
 585                 for(std::vector<const char*>::iterator it = undefineNames.begin(); it != undefineNames.end(); ++it) {
 586                         const char* undef = *it;
 587                         // load for previous undefine may also have loaded this undefine, so check again
 588                         if ( ! _symbolTable.hasName(undef) ) {
 589                                 _inputFiles.searchLibraries(undef, true, true, false, *this);
 590                                 if ( !_symbolTable.hasName(undef) && (_options.outputKind() != Options::kObjectFile) ) {
 591                                         if ( strncmp(undef, "section$", 8) == 0 ) {
 592                                                 if ( strncmp(undef, "section$start$", 14) == 0 ) {
 593                                                         this->doAtom(*SectionBoundaryAtom::makeSectionBoundaryAtom(undef, true, &undef[14]));
 594                                                 }
 595                                                 else if ( strncmp(undef, "section$end$", 12) == 0 ) {
 596                                                         this->doAtom(*SectionBoundaryAtom::makeSectionBoundaryAtom(undef, false, &undef[12]));
 597                                                 }
 598                                         }
 599                                         else if ( strncmp(undef, "segment$", 8) == 0 ) {
 600                                                 if ( strncmp(undef, "segment$start$", 14) == 0 ) {
 601                                                         this->doAtom(*SegmentBoundaryAtom::makeSegmentBoundaryAtom(undef, true, &undef[14]));
 602                                                 }
 603                                                 else if ( strncmp(undef, "segment$end$", 12) == 0 ) {
 604                                                         this->doAtom(*SegmentBoundaryAtom::makeSegmentBoundaryAtom(undef, false, &undef[12]));
 605                                                 }
 606                                         }
 607                                         else if ( _options.outputKind() == Options::kPreload ) {
 608                                                 // for iBoot grandfather in old style section labels
 609                                                 int undefLen = strlen(undef);
 610                                                 if ( strcmp(&undef[undefLen-7], "__begin") == 0 ) {
 611                                                         if ( undefLen > 13 )
 612                                                                 this->doAtom(*SectionBoundaryAtom::makeOldSectionBoundaryAtom(undef, true));
 613                                                         else
 614                                                                 this->doAtom(*SegmentBoundaryAtom::makeOldSegmentBoundaryAtom(undef, true));
 615                                                 }
 616                                                 else if ( strcmp(&undef[undefLen-5], "__end") == 0 ) {
 617                                                         if ( undefLen > 11 )
 618                                                                 this->doAtom(*SectionBoundaryAtom::makeOldSectionBoundaryAtom(undef, false));
 619                                                         else
 620                                                                 this->doAtom(*SegmentBoundaryAtom::makeOldSegmentBoundaryAtom(undef, false));
 621                                                 }
 622                                         }
 623                                 }
 624                         }
 625                 }
 626                 // <rdar://problem/5894163> need to search archives for overrides of common symbols
 627                 if ( _symbolTable.hasExternalTentativeDefinitions() ) {
 628                         bool searchDylibs = (_options.commonsMode() == Options::kCommonsOverriddenByDylibs);
 629                         std::vector<const char*> tents;
 630                         _symbolTable.tentativeDefs(tents);
 631                         for(std::vector<const char*>::iterator it = tents.begin(); it != tents.end(); ++it) {
 632                                 // load for previous tentative may also have loaded this tentative, so check again
 633                                 const ld::Atom* curAtom = _symbolTable.atomForSlot(_symbolTable.findSlotForName(*it));
 634                                 assert(curAtom != NULL);
 635                                 if ( curAtom->definition() == ld::Atom::definitionTentative ) {
 636                                         _inputFiles.searchLibraries(*it, searchDylibs, true, true, *this);
 637                                 }
 638                         }
 639                 }
 640         }
 641
 642         // create proxies as needed for undefined symbols
 643         if ( (_options.undefinedTreatment() != Options::kUndefinedError) || (_options.outputKind() == Options::kObjectFile) ) {
 644                 std::vector<const char*> undefineNames;
 645                 _symbolTable.undefines(undefineNames);
 646                 for(std::vector<const char*>::iterator it = undefineNames.begin(); it != undefineNames.end(); ++it) {
 647                         // make proxy
 648                         this->doAtom(*new UndefinedProxyAtom(*it));
 649                 }
 650         }
 651
 652         // support -U option
 653         if ( _options.someAllowedUndefines() ) {
 654                 std::vector<const char*> undefineNames;
 655                 _symbolTable.undefines(undefineNames);
 656                 for(std::vector<const char*>::iterator it = undefineNames.begin(); it != undefineNames.end(); ++it) {
 657                         if ( _options.allowedUndefined(*it) ) {
 658                                 // make proxy
 659                                 this->doAtom(*new UndefinedProxyAtom(*it));
 660                         }
 661                 }
 662         }
 663
 664 }
 665
 666
 667 void Resolver::markLive(const ld::Atom& atom, WhyLiveBackChain* previous)
 668 {
 669         //fprintf(stderr, "markLive(%p) %s\n", &atom, atom.name());
 670         // if -why_live cares about this symbol, then dump chain
 671         if ( (previous->referer != NULL) && _options.printWhyLive(atom.name()) ) {
 672                 fprintf(stderr, "%s from %s\n", atom.name(), atom.file()->path());
 673                 int depth = 1;
 674                 for(WhyLiveBackChain* p = previous; p != NULL; p = p->previous, ++depth) {
 675                         for(int i=depth; i > 0; --i)
 676                                 fprintf(stderr, "  ");
 677                         fprintf(stderr, "%s from %s\n", p->referer->name(), p->referer->file()->path());
 678                 }
 679         }
 680
 681         // if already marked live, then done (stop recursion)
 682         if ( atom.live() )
 683                 return;
 684
 685         // mark this atom is live
 686         (const_cast<ld::Atom*>(&atom))->setLive();
 687
 688         // mark all atoms it references as live
 689         WhyLiveBackChain thisChain;
 690         thisChain.previous = previous;
 691         thisChain.referer = &atom;
 692         for (ld::Fixup::iterator fit = atom.fixupsBegin(), end=atom.fixupsEnd(); fit != end; ++fit) {
 693                 const ld::Atom* target;
 694                 switch ( fit->kind ) {
 695                         case ld::Fixup::kindNone:
 696                         case ld::Fixup::kindNoneFollowOn:
 697                         case ld::Fixup::kindNoneGroupSubordinate:
 698                         case ld::Fixup::kindNoneGroupSubordinateFDE:
 699                         case ld::Fixup::kindNoneGroupSubordinateLSDA:
 700                         case ld::Fixup::kindSetTargetAddress:
 701                         case ld::Fixup::kindSubtractTargetAddress:
 702                         case ld::Fixup::kindStoreTargetAddressLittleEndian32:
 703                         case ld::Fixup::kindStoreTargetAddressLittleEndian64:
 704                         case ld::Fixup::kindStoreTargetAddressBigEndian32:
 705                         case ld::Fixup::kindStoreTargetAddressBigEndian64:
 706                         case ld::Fixup::kindStoreTargetAddressX86PCRel32:
 707                         case ld::Fixup::kindStoreTargetAddressX86BranchPCRel32:
 708                         case ld::Fixup::kindStoreTargetAddressX86PCRel32GOTLoad:
 709                         case ld::Fixup::kindStoreTargetAddressX86PCRel32GOTLoadNowLEA:
 710                         case ld::Fixup::kindStoreTargetAddressX86PCRel32TLVLoad:
 711                         case ld::Fixup::kindStoreTargetAddressX86PCRel32TLVLoadNowLEA:
 712                         case ld::Fixup::kindStoreTargetAddressX86Abs32TLVLoad:
 713                         case ld::Fixup::kindStoreTargetAddressX86Abs32TLVLoadNowLEA:
 714                         case ld::Fixup::kindStoreTargetAddressARMBranch24:
 715                         case ld::Fixup::kindStoreTargetAddressThumbBranch22:
 716                                 if ( fit->binding == ld::Fixup::bindingByContentBound ) {
 717                                         // normally this was done in convertReferencesToIndirect()
 718                                         // but a archive loaded .o file may have a forward reference
 719                                         SymbolTable::IndirectBindingSlot slot;
 720                                         const ld::Atom* dummy;
 721                                         switch ( fit->u.target->combine() ) {
 722                                                 case ld::Atom::combineNever:
 723                                                 case ld::Atom::combineByName:
 724                                                         assert(0 && "wrong combine type for bind by content");
 725                                                         break;
 726                                                 case ld::Atom::combineByNameAndContent:
 727                                                         slot = _symbolTable.findSlotForContent(fit->u.target, &dummy);
 728                                                         fit->binding = ld::Fixup::bindingsIndirectlyBound;
 729                                                         fit->u.bindingIndex = slot;
 730                                                         break;
 731                                                 case ld::Atom::combineByNameAndReferences:
 732                                                         slot = _symbolTable.findSlotForReferences(fit->u.target, &dummy);
 733                                                         fit->binding = ld::Fixup::bindingsIndirectlyBound;
 734                                                         fit->u.bindingIndex = slot;
 735                                                         break;
 736                                         }
 737                                 }
 738                                 switch ( fit->binding ) {
 739                                         case ld::Fixup::bindingDirectlyBound:
 740                                                 markLive(*(fit->u.target), &thisChain);
 741                                                 break;
 742                                         case ld::Fixup::bindingByNameUnbound:
 743                                                 // doAtom() did not convert to indirect in dead-strip mode, so that now
 744                                                 fit->u.bindingIndex = _symbolTable.findSlotForName(fit->u.name);
 745                                                 fit->binding = ld::Fixup::bindingsIndirectlyBound;
 746                                                 // fall into next case
 747                                         case ld::Fixup::bindingsIndirectlyBound:
 748                                                 target = _internal.indirectBindingTable[fit->u.bindingIndex];
 749                                                 if ( target == NULL ) {
 750                                                         const char* targetName = _symbolTable.indirectName(fit->u.bindingIndex);
 751                                                         _inputFiles.searchLibraries(targetName, true, true, false, *this);
 752                                                         target = _internal.indirectBindingTable[fit->u.bindingIndex];
 753                                                 }
 754                                                 if ( target != NULL ) {
 755                                                         if ( target->definition() == ld::Atom::definitionTentative ) {
 756                                                                 // <rdar://problem/5894163> need to search archives for overrides of common symbols
 757                                                                 bool searchDylibs = (_options.commonsMode() == Options::kCommonsOverriddenByDylibs);
 758                                                                 _inputFiles.searchLibraries(target->name(), searchDylibs, true, true, *this);
 759                                                                 // recompute target since it may have been overridden by searchLibraries()
 760                                                                 target = _internal.indirectBindingTable[fit->u.bindingIndex];
 761                                                         }
 762                                                         this->markLive(*target, &thisChain);
 763                                                 }
 764                                                 else {
 765                                                         _atomsWithUnresolvedReferences.push_back(&atom);
 766                                                 }
 767                                                 break;
 768                                         default:
 769                                                 assert(0 && "bad binding during dead stripping");
 770                                 }
 771                                 break;
 772             default:
 773                 break;
 774                 }
 775         }
 776
 777 }
 778
 779 class NotLiveLTO {
 780 public:
 781         bool operator()(const ld::Atom* atom) const {
 782                 if (atom->live() || atom->dontDeadStrip() )
 783                         return false;
 784                 // don't kill combinable atoms in first pass
 785                 switch ( atom->combine() ) {
 786                         case ld::Atom::combineByNameAndContent:
 787                         case ld::Atom::combineByNameAndReferences:
 788                                 return false;
 789                         default:
 790                                 return true;
 791                 }
 792         }
 793 };
 794
 795 void Resolver::deadStripOptimize(bool force)
 796 {
 797         // only do this optimization with -dead_strip
 798         if ( ! _options.deadCodeStrip() )
 799                 return;
 800
 801         // add entry point (main) to live roots
 802         const ld::Atom* entry = this->entryPoint(true);
 803         if ( entry != NULL )
 804                 _deadStripRoots.insert(entry);
 805
 806         // add -exported_symbols_list, -init, and -u entries to live roots
 807         for (Options::UndefinesIterator uit=_options.initialUndefinesBegin(); uit != _options.initialUndefinesEnd(); ++uit) {
 808                 SymbolTable::IndirectBindingSlot slot = _symbolTable.findSlotForName(*uit);
 809                 if ( _internal.indirectBindingTable[slot] == NULL ) {
 810                         _inputFiles.searchLibraries(*uit, false, true, false, *this);
 811                 }
 812                 if ( _internal.indirectBindingTable[slot] != NULL )
 813                         _deadStripRoots.insert(_internal.indirectBindingTable[slot]);
 814         }
 815
 816         // this helper is only referenced by synthesize stubs, assume it will be used
 817         if ( _internal.classicBindingHelper != NULL )
 818                 _deadStripRoots.insert(_internal.classicBindingHelper);
 819
 820         // this helper is only referenced by synthesize stubs, assume it will be used
 821         if ( _internal.compressedFastBinderProxy != NULL )
 822                 _deadStripRoots.insert(_internal.compressedFastBinderProxy);
 823
 824         // this helper is only referenced by synthesized lazy stubs, assume it will be used
 825         if ( _internal.lazyBindingHelper != NULL )
 826                 _deadStripRoots.insert(_internal.lazyBindingHelper);
 827
 828         // add all dont-dead-strip atoms as roots
 829         for (std::vector<const ld::Atom*>::const_iterator it=_atoms.begin(); it != _atoms.end(); ++it) {
 830                 const ld::Atom* atom = *it;
 831                 if ( atom->dontDeadStrip() ) {
 832                         //fprintf(stderr, "dont dead strip: %p %s %s\n", atom, atom->section().sectionName(), atom->name());
 833                         _deadStripRoots.insert(atom);
 834                         // unset liveness, so markLive() will recurse
 835                         (const_cast<ld::Atom*>(atom))->setLive(0);
 836                 }
 837         }
 838
 839         // mark all roots as live, and all atoms they reference
 840         for (std::set<const ld::Atom*>::iterator it=_deadStripRoots.begin(); it != _deadStripRoots.end(); ++it) {
 841                 WhyLiveBackChain rootChain;
 842                 rootChain.previous = NULL;
 843                 rootChain.referer = *it;
 844                 this->markLive(**it, &rootChain);
 845         }
 846
 847         // now remove all non-live atoms from _atoms
 848         const bool log = false;
 849         if ( log ) {
 850                 fprintf(stderr, "deadStripOptimize() all %ld atoms with liveness:\n", _atoms.size());
 851                 for (std::vector<const ld::Atom*>::const_iterator it=_atoms.begin(); it != _atoms.end(); ++it) {
 852                         const ld::File* file = (*it)->file();
 853                         fprintf(stderr, "  live=%d  atom=%p  name=%s from=%s\n", (*it)->live(), *it, (*it)->name(),  (file ? file->path() : "<internal>"));
 854                 }
 855         }
 856
 857         if ( _haveLLVMObjs && !force ) {
 858                 // <rdar://problem/9777977> don't remove combinable atoms, they may come back in lto output
 859                 _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(), NotLiveLTO()), _atoms.end());
 860         }
 861         else {
 862                 _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(), NotLive()), _atoms.end());
 863         }
 864
 865         if ( log ) {
 866                 fprintf(stderr, "deadStripOptimize() %ld remaining atoms\n", _atoms.size());
 867                 for (std::vector<const ld::Atom*>::const_iterator it=_atoms.begin(); it != _atoms.end(); ++it) {
 868                         fprintf(stderr, "  live=%d  atom=%p  name=%s\n", (*it)->live(), *it, (*it)->name());
 869                 }
 870         }
 871 }
 872
 873
 874 // This is called when LTO is used but -dead_strip is not used.
 875 // Some undefines were eliminated by LTO, but others were not.
 876 void Resolver::remainingUndefines(std::vector<const char*>& undefs)
 877 {
 878         StringSet  undefSet;
 879         // search all atoms for references that are unbound
 880         for (std::vector<const ld::Atom*>::const_iterator it=_atoms.begin(); it != _atoms.end(); ++it) {
 881                 const ld::Atom* atom = *it;
 882                 for (ld::Fixup::iterator fit=atom->fixupsBegin(); fit != atom->fixupsEnd(); ++fit) {
 883                         switch ( (ld::Fixup::TargetBinding)fit->binding ) {
 884                                 case ld::Fixup::bindingByNameUnbound:
 885                                         assert(0 && "should not be by-name this late");
 886                                         undefSet.insert(fit->u.name);
 887                                         break;
 888                                 case ld::Fixup::bindingsIndirectlyBound:
 889                                         if ( _internal.indirectBindingTable[fit->u.bindingIndex] == NULL ) {
 890                                                 undefSet.insert(_symbolTable.indirectName(fit->u.bindingIndex));
 891                                         }
 892                                         break;
 893                                 case ld::Fixup::bindingByContentBound:
 894                                 case ld::Fixup::bindingNone:
 895                                 case ld::Fixup::bindingDirectlyBound:
 896                                         break;
 897                         }
 898                 }
 899         }
 900         // look for any initial undefines that are still undefined
 901         for (Options::UndefinesIterator uit=_options.initialUndefinesBegin(); uit != _options.initialUndefinesEnd(); ++uit) {
 902                 if ( ! _symbolTable.hasName(*uit) ) {
 903                         undefSet.insert(*uit);
 904                 }
 905         }
 906
 907         // copy set to vector
 908         for (StringSet::const_iterator it=undefSet.begin(); it != undefSet.end(); ++it) {
 909         fprintf(stderr, "undef: %s\n", *it);
 910                 undefs.push_back(*it);
 911         }
 912 }
 913
 914 void Resolver::liveUndefines(std::vector<const char*>& undefs)
 915 {
 916         StringSet  undefSet;
 917         // search all live atoms for references that are unbound
 918         for (std::vector<const ld::Atom*>::const_iterator it=_atoms.begin(); it != _atoms.end(); ++it) {
 919                 const ld::Atom* atom = *it;
 920                 if ( ! atom->live() )
 921                         continue;
 922                 for (ld::Fixup::iterator fit=atom->fixupsBegin(); fit != atom->fixupsEnd(); ++fit) {
 923                         switch ( (ld::Fixup::TargetBinding)fit->binding ) {
 924                                 case ld::Fixup::bindingByNameUnbound:
 925                                         assert(0 && "should not be by-name this late");
 926                                         undefSet.insert(fit->u.name);
 927                                         break;
 928                                 case ld::Fixup::bindingsIndirectlyBound:
 929                                         if ( _internal.indirectBindingTable[fit->u.bindingIndex] == NULL ) {
 930                                                 undefSet.insert(_symbolTable.indirectName(fit->u.bindingIndex));
 931                                         }
 932                                         break;
 933                                 case ld::Fixup::bindingByContentBound:
 934                                 case ld::Fixup::bindingNone:
 935                                 case ld::Fixup::bindingDirectlyBound:
 936                                         break;
 937                         }
 938                 }
 939         }
 940         // look for any initial undefines that are still undefined
 941         for (Options::UndefinesIterator uit=_options.initialUndefinesBegin(); uit != _options.initialUndefinesEnd(); ++uit) {
 942                 if ( ! _symbolTable.hasName(*uit) ) {
 943                         undefSet.insert(*uit);
 944                 }
 945         }
 946
 947         // copy set to vector
 948         for (StringSet::const_iterator it=undefSet.begin(); it != undefSet.end(); ++it) {
 949                 undefs.push_back(*it);
 950         }
 951 }
 952
 953
 954
 955 // <rdar://problem/8252819> warn when .objc_class_name_* symbol missing
 956 class ExportedObjcClass
 957 {
 958 public:
 959         ExportedObjcClass(const Options& opt) : _options(opt)  {}
 960
 961         bool operator()(const char* name) const {
 962                 if ( (strncmp(name, ".objc_class_name_", 17) == 0) && _options.shouldExport(name) ) {
 963                         warning("ignoring undefined symbol %s from -exported_symbols_list", name);
 964                         return true;
 965                 }
 966                 const char* s = strstr(name, "CLASS_$_");
 967                 if ( s != NULL ) {
 968                         char temp[strlen(name)+16];
 969                         strcpy(temp, ".objc_class_name_");
 970                         strcat(temp, &s[8]);
 971                         if ( _options.wasRemovedExport(temp) ) {
 972                                 warning("ignoring undefined symbol %s from -exported_symbols_list", temp);
 973                                 return true;
 974                         }
 975                 }
 976                 return false;
 977         }
 978 private:
 979         const Options& _options;
 980 };
 981
 982
 983 // temp hack for undefined aliases
 984 class UndefinedAlias
 985 {
 986 public:
 987         UndefinedAlias(const Options& opt) : _aliases(opt.cmdLineAliases()) {}
 988
 989         bool operator()(const char* name) const {
 990                 for (std::vector<Options::AliasPair>::const_iterator it=_aliases.begin(); it != _aliases.end(); ++it) {
 991                         if ( strcmp(it->realName, name) == 0 ) {
 992                                 warning("undefined base symbol '%s' for alias '%s'", name, it->alias);
 993                                 return true;
 994                         }
 995                 }
 996                 return false;
 997         }
 998 private:
 999         const std::vector<Options::AliasPair>&  _aliases;
1000 };
1001
1002
1003
1004 static const char* pathLeafName(const char* path)
1005 {
1006         const char* shortPath = strrchr(path, '/');
1007         if ( shortPath == NULL )
1008                 return path;
1009         else
1010                 return &shortPath[1];
1011 }
1012
1013 bool Resolver::printReferencedBy(const char* name, SymbolTable::IndirectBindingSlot slot)
1014 {
1015         unsigned foundReferenceCount = 0;
1016         for (std::vector<const ld::Atom*>::const_iterator it=_atoms.begin(); it != _atoms.end(); ++it) {
1017                 const ld::Atom* atom = *it;
1018                 for (ld::Fixup::iterator fit=atom->fixupsBegin(); fit != atom->fixupsEnd(); ++fit) {
1019                         if ( fit->binding == ld::Fixup::bindingsIndirectlyBound ) {
1020                                 if ( fit->u.bindingIndex == slot ) {
1021                                         if ( atom->contentType() == ld::Atom::typeNonLazyPointer ) {
1022                                                 const ld::Atom* existingAtom;
1023                                                 unsigned int nlSlot = _symbolTable.findSlotForReferences(atom, &existingAtom);
1024                                                 if ( printReferencedBy(name, nlSlot) )
1025                                                         ++foundReferenceCount;
1026                                         }
1027                                         else if ( atom->contentType() == ld::Atom::typeCFI ) {
1028                                                 fprintf(stderr, "      Dwarf Exception Unwind Info (__eh_frame) in %s\n", pathLeafName(atom->file()->path()));
1029                                                 ++foundReferenceCount;
1030                                         }
1031                                         else {
1032                                                 fprintf(stderr, "      %s in %s\n", _options.demangleSymbol(atom->name()), pathLeafName(atom->file()->path()));
1033                                                 ++foundReferenceCount;
1034                                                 break; // if undefined used twice in a function, only show first
1035                                         }
1036                                 }
1037                         }
1038                 }
1039                 if ( foundReferenceCount > 6 ) {
1040                         fprintf(stderr, "      ...\n");
1041                         break; // only show first six uses of undefined symbol
1042                 }
1043         }
1044         return (foundReferenceCount != 0);
1045 }
1046
1047 void Resolver::checkUndefines(bool force)
1048 {
1049         // when using LTO, undefines are checked after bitcode is optimized
1050         if ( _haveLLVMObjs && !force )
1051                 return;
1052
1053         // error out on any remaining undefines
1054         bool doPrint = true;
1055         bool doError = true;
1056         switch ( _options.undefinedTreatment() ) {
1057                 case Options::kUndefinedError:
1058                         break;
1059                 case Options::kUndefinedDynamicLookup:
1060                         doError = false;
1061                         break;
1062                 case Options::kUndefinedWarning:
1063                         doError = false;
1064                         break;
1065                 case Options::kUndefinedSuppress:
1066                         doError = false;
1067                         doPrint = false;
1068                         break;
1069         }
1070         std::vector<const char*> unresolvableUndefines;
1071         if ( _options.deadCodeStrip() )
1072                 this->liveUndefines(unresolvableUndefines);
1073     else if( _haveLLVMObjs )
1074                 this->remainingUndefines(unresolvableUndefines); // <rdar://problem/10052396> LTO may have eliminated need for some undefines
1075         else
1076                 _symbolTable.undefines(unresolvableUndefines);
1077
1078         // <rdar://problem/8252819> assert when .objc_class_name_* symbol missing
1079         if ( _options.hasExportMaskList() ) {
1080                 unresolvableUndefines.erase(std::remove_if(unresolvableUndefines.begin(), unresolvableUndefines.end(), ExportedObjcClass(_options)), unresolvableUndefines.end());
1081         }
1082
1083         // hack to temporarily make missing aliases a warning
1084         if ( _options.haveCmdLineAliases() ) {
1085                 unresolvableUndefines.erase(std::remove_if(unresolvableUndefines.begin(), unresolvableUndefines.end(), UndefinedAlias(_options)), unresolvableUndefines.end());
1086         }
1087
1088         const int unresolvableCount = unresolvableUndefines.size();
1089         int unresolvableExportsCount = 0;
1090         if ( unresolvableCount != 0 ) {
1091                 if ( doPrint ) {
1092                         if ( _options.printArchPrefix() )
1093                                 fprintf(stderr, "Undefined symbols for architecture %s:\n", _options.architectureName());
1094                         else
1095                                 fprintf(stderr, "Undefined symbols:\n");
1096                         for (int i=0; i < unresolvableCount; ++i) {
1097                                 const char* name = unresolvableUndefines[i];
1098                                 unsigned int slot = _symbolTable.findSlotForName(name);
1099                                 fprintf(stderr, "  \"%s\", referenced from:\n", _options.demangleSymbol(name));
1100                                 // scan all atoms for references
1101                                 bool foundAtomReference = printReferencedBy(name, slot);
1102                                 // scan command line options
1103                                 if  ( !foundAtomReference ) {
1104                                         // might be from -init command line option
1105                                         if ( (_options.initFunctionName() != NULL) && (strcmp(name, _options.initFunctionName()) == 0) ) {
1106                                                 fprintf(stderr, "     -init command line option\n");
1107                                         }
1108                                         // or might be from exported symbol option
1109                                         else if ( _options.hasExportMaskList() && _options.shouldExport(name) ) {
1110                                                 fprintf(stderr, "     -exported_symbol[s_list] command line option\n");
1111                                         }
1112                                         // or might be from re-exported symbol option
1113                                         else if ( _options.hasReExportList() && _options.shouldReExport(name) ) {
1114                                                 fprintf(stderr, "     -reexported_symbols_list command line option\n");
1115                                         }
1116                                         else if ( (_options.outputKind() == Options::kDynamicExecutable)
1117                                                         && (_options.entryName() != NULL) && (strcmp(name, _options.entryName()) == 0) ) {
1118                                                 fprintf(stderr, "     implicit entry/start for main executable\n");
1119                                         }
1120                                         else {
1121                                                 bool isInitialUndefine = false;
1122                                                 for (Options::UndefinesIterator uit=_options.initialUndefinesBegin(); uit != _options.initialUndefinesEnd(); ++uit) {
1123                                                         if ( strcmp(*uit, name) == 0 ) {
1124                                                                 isInitialUndefine = true;
1125                                                                 break;
1126                                                         }
1127                                                 }
1128                                                 if ( isInitialUndefine )
1129                                                         fprintf(stderr, "     -u command line option\n");
1130                                         }
1131                                         ++unresolvableExportsCount;
1132                                 }
1133                                 // be helpful and check for typos
1134                                 bool printedStart = false;
1135                                 for (SymbolTable::byNameIterator sit=_symbolTable.begin(); sit != _symbolTable.end(); sit++) {
1136                                         const ld::Atom* atom = *sit;
1137                                         if ( (atom != NULL) && (atom->symbolTableInclusion() == ld::Atom::symbolTableIn) && (strstr(atom->name(), name) != NULL) ) {
1138                                                 if ( ! printedStart ) {
1139                                                         fprintf(stderr, "     (maybe you meant: %s", atom->name());
1140                                                         printedStart = true;
1141                                                 }
1142                                                 else {
1143                                                         fprintf(stderr, ", %s ", atom->name());
1144                                                 }
1145                                         }
1146                                 }
1147                                 if ( printedStart )
1148                                         fprintf(stderr, ")\n");
1149                                 // <rdar://problem/8989530> Add comment to error message when __ZTV symbols are undefined
1150                                 if ( strncmp(name, "__ZTV", 5) == 0 ) {
1151                                         fprintf(stderr, "  NOTE: a missing vtable usually means the first non-inline virtual member function has no definition.\n");
1152                                 }
1153                         }
1154                 }
1155                 if ( doError )
1156                         throw "symbol(s) not found";
1157         }
1158
1159 }
1160
1161
1162
1163 void Resolver::checkDylibSymbolCollisions()
1164 {
1165         for (SymbolTable::byNameIterator it=_symbolTable.begin(); it != _symbolTable.end(); it++) {
1166                 const ld::Atom* atom = *it;
1167                 if ( atom == NULL )
1168                         continue;
1169                 if ( atom->scope() == ld::Atom::scopeGlobal ) {
1170                         // <rdar://problem/5048861> No warning about tentative definition conflicting with dylib definition
1171                         // for each tentative definition in symbol table look for dylib that exports same symbol name
1172                         if ( atom->definition() == ld::Atom::definitionTentative ) {
1173                                 _inputFiles.searchLibraries(atom->name(), true, false, false, *this);
1174                         }
1175                         // record any overrides of weak symbols in any linked dylib
1176                         if ( (atom->definition() == ld::Atom::definitionRegular) && (atom->symbolTableInclusion() == ld::Atom::symbolTableIn) ) {
1177                                 if ( _inputFiles.searchWeakDefInDylib(atom->name()) )
1178                                         (const_cast<ld::Atom*>(atom))->setOverridesDylibsWeakDef();
1179                         }
1180                 }
1181         }
1182 }
1183
1184
1185 const ld::Atom* Resolver::entryPoint(bool searchArchives)
1186 {
1187         const char* symbolName = NULL;
1188         bool makingDylib = false;
1189         switch ( _options.outputKind() ) {
1190                 case Options::kDynamicExecutable:
1191                 case Options::kStaticExecutable:
1192                 case Options::kDyld:
1193                 case Options::kPreload:
1194                         symbolName = _options.entryName();
1195                         break;
1196                 case Options::kDynamicLibrary:
1197                         symbolName = _options.initFunctionName();
1198                         makingDylib = true;
1199                         break;
1200                 case Options::kObjectFile:
1201                 case Options::kDynamicBundle:
1202                 case Options::kKextBundle:
1203                         return NULL;
1204                         break;
1205         }
1206         if ( symbolName != NULL ) {
1207                 SymbolTable::IndirectBindingSlot slot = _symbolTable.findSlotForName(symbolName);
1208                 if ( (_internal.indirectBindingTable[slot] == NULL) && searchArchives ) {
1209                         // <rdar://problem/7043256> ld64 can not find a -e entry point from an archive
1210                         _inputFiles.searchLibraries(symbolName, false, true, false, *this);
1211                 }
1212                 if ( _internal.indirectBindingTable[slot] == NULL ) {
1213                         if ( strcmp(symbolName, "start") == 0 )
1214                                 throwf("entry point (%s) undefined.  Usually in crt1.o", symbolName);
1215                         else
1216                                 throwf("entry point (%s) undefined.", symbolName);
1217                 }
1218                 else if ( _internal.indirectBindingTable[slot]->definition() == ld::Atom::definitionProxy ) {
1219                         if ( makingDylib )
1220                                 throwf("-init function (%s) found in linked dylib, must be in dylib being linked", symbolName);
1221                 }
1222                 return _internal.indirectBindingTable[slot];
1223         }
1224         return NULL;
1225 }
1226
1227
1228 void Resolver::fillInHelpersInInternalState()
1229 {
1230         // look up well known atoms
1231         bool needsStubHelper = true;
1232         switch ( _options.outputKind() ) {
1233                 case Options::kDynamicExecutable:
1234                 case Options::kDynamicLibrary:
1235                 case Options::kDynamicBundle:
1236                         needsStubHelper = true;
1237                         break;
1238                 case Options::kDyld:
1239                 case Options::kKextBundle:
1240                 case Options::kObjectFile:
1241                 case Options::kStaticExecutable:
1242                 case Options::kPreload:
1243                         needsStubHelper = false;
1244                         break;
1245         }
1246
1247         _internal.classicBindingHelper = NULL;
1248         if ( needsStubHelper && !_options.makeCompressedDyldInfo() ) {
1249                 // "dyld_stub_binding_helper" comes from .o file, so should already exist in symbol table
1250                 if ( _symbolTable.hasName("dyld_stub_binding_helper") ) {
1251                         SymbolTable::IndirectBindingSlot slot = _symbolTable.findSlotForName("dyld_stub_binding_helper");
1252                         _internal.classicBindingHelper = _internal.indirectBindingTable[slot];
1253                 }
1254         }
1255
1256         _internal.lazyBindingHelper = NULL;
1257         if ( _options.usingLazyDylibLinking() ) {
1258                 // "dyld_lazy_dylib_stub_binding_helper" comes from lazydylib1.o file, so should already exist in symbol table
1259                 if ( _symbolTable.hasName("dyld_lazy_dylib_stub_binding_helper") ) {
1260                         SymbolTable::IndirectBindingSlot slot = _symbolTable.findSlotForName("dyld_lazy_dylib_stub_binding_helper");
1261                         _internal.lazyBindingHelper = _internal.indirectBindingTable[slot];
1262                 }
1263                 if ( _internal.lazyBindingHelper == NULL )
1264                         throw "symbol dyld_lazy_dylib_stub_binding_helper not defined (usually in lazydylib1.o)";
1265         }
1266
1267         _internal.compressedFastBinderProxy = NULL;
1268         if ( needsStubHelper && _options.makeCompressedDyldInfo() ) {
1269                 // "dyld_stub_binder" comes from libSystem.dylib so will need to manually resolve
1270                 if ( !_symbolTable.hasName("dyld_stub_binder") ) {
1271                         _inputFiles.searchLibraries("dyld_stub_binder", true, false, false, *this);
1272                 }
1273                 if ( _symbolTable.hasName("dyld_stub_binder") ) {
1274                         SymbolTable::IndirectBindingSlot slot = _symbolTable.findSlotForName("dyld_stub_binder");
1275                         _internal.compressedFastBinderProxy = _internal.indirectBindingTable[slot];
1276                 }
1277                 if ( _internal.compressedFastBinderProxy == NULL ) {
1278                         if ( _options.undefinedTreatment() != Options::kUndefinedError ) {
1279                                 // make proxy
1280                                 _internal.compressedFastBinderProxy = new UndefinedProxyAtom("dyld_stub_binder");
1281                                 this->doAtom(*_internal.compressedFastBinderProxy);
1282                         }
1283                 }
1284         }
1285 }
1286
1287
1288 void Resolver::fillInInternalState()
1289 {
1290         // store atoms into their final section
1291         for (std::vector<const ld::Atom*>::iterator it = _atoms.begin(); it != _atoms.end(); ++it) {
1292                 _internal.addAtom(**it);
1293         }
1294
1295         // <rdar://problem/7783918> make sure there is a __text section so that codesigning works
1296         if ( (_options.outputKind() == Options::kDynamicLibrary) || (_options.outputKind() == Options::kDynamicBundle) )
1297                 _internal.getFinalSection(*new ld::Section("__TEXT", "__text", ld::Section::typeCode));
1298 }
1299
1300 void Resolver::fillInEntryPoint()
1301 {
1302         _internal.entryPoint = this->entryPoint(true);
1303 }
1304
1305
1306
1307 void Resolver::removeCoalescedAwayAtoms()
1308 {
1309         const bool log = false;
1310         if ( log ) {
1311                 fprintf(stderr, "removeCoalescedAwayAtoms() starts with %lu atoms\n", _atoms.size());
1312         }
1313         _atoms.erase(std::remove_if(_atoms.begin(), _atoms.end(), AtomCoalescedAway()), _atoms.end());
1314         if ( log ) {
1315                 fprintf(stderr, "removeCoalescedAwayAtoms() after removing coalesced atoms, %lu remain\n", _atoms.size());
1316                 for (std::vector<const ld::Atom*>::const_iterator it=_atoms.begin(); it != _atoms.end(); ++it) {
1317                         fprintf(stderr, "  atom=%p %s\n", *it, (*it)->name());
1318                 }
1319         }
1320 }
1321
1322 void Resolver::linkTimeOptimize()
1323 {
1324         // only do work here if some llvm obj files where loaded
1325         if ( ! _haveLLVMObjs )
1326                 return;
1327
1328         // run LLVM lto code-gen
1329         lto::OptimizeOptions optOpt;
1330         optOpt.outputFilePath                           = _options.outputFilePath();
1331         optOpt.tmpObjectFilePath                        = _options.tempLtoObjectPath();
1332         optOpt.preserveAllGlobals                       = _options.allGlobalsAreDeadStripRoots() || _options.hasExportRestrictList();
1333         optOpt.verbose                                          = _options.verbose();
1334         optOpt.saveTemps                                        = _options.saveTempFiles();
1335         optOpt.pie                                                      = _options.positionIndependentExecutable();
1336         optOpt.mainExecutable                           = _options.linkingMainExecutable();;
1337         optOpt.staticExecutable                         = (_options.outputKind() == Options::kStaticExecutable);
1338         optOpt.relocatable                                      = (_options.outputKind() == Options::kObjectFile);
1339         optOpt.allowTextRelocs                          = _options.allowTextRelocs();
1340         optOpt.linkerDeadStripping                      = _options.deadCodeStrip();
1341         optOpt.arch                                                     = _options.architecture();
1342         optOpt.llvmOptions                                      = &_options.llvmOptions();
1343
1344         std::vector<const ld::Atom*>            newAtoms;
1345         std::vector<const char*>                        additionalUndefines;
1346         if ( ! lto::optimize(_atoms, _internal, optOpt, *this, newAtoms, additionalUndefines) )
1347                 return; // if nothing done
1348
1349
1350         // add all newly created atoms to _atoms and update symbol table
1351         for(std::vector<const ld::Atom*>::iterator it = newAtoms.begin(); it != newAtoms.end(); ++it)
1352                 this->doAtom(**it);
1353
1354         // some atoms might have been optimized way (marked coalesced), remove them
1355         this->removeCoalescedAwayAtoms();
1356
1357         // run through all atoms again and make sure newly codegened atoms have references bound
1358         for (std::vector<const ld::Atom*>::const_iterator it=_atoms.begin(); it != _atoms.end(); ++it)
1359                 this->convertReferencesToIndirect(**it);
1360
1361         // adjust section of any new
1362         for (std::vector<const AliasAtom*>::const_iterator it=_aliasesFromCmdLine.begin(); it != _aliasesFromCmdLine.end(); ++it) {
1363                 const AliasAtom* aliasAtom = *it;
1364                 // update fields in AliasAtom to match newly constructed mach-o atom
1365                 aliasAtom->setFinalAliasOf();
1366         }
1367
1368         // resolve new undefines (e.g calls to _malloc and _memcpy that llvm compiler conjures up)
1369         for(std::vector<const char*>::iterator uit = additionalUndefines.begin(); uit != additionalUndefines.end(); ++uit) {
1370                 const char *targetName = *uit;
1371                 // these symbols may or may not already be in linker's symbol table
1372                 if ( ! _symbolTable.hasName(targetName) ) {
1373                         _inputFiles.searchLibraries(targetName, true, true, false, *this);
1374                 }
1375         }
1376
1377         // if -dead_strip on command line
1378         if ( _options.deadCodeStrip() ) {
1379                 // clear liveness bit
1380                 for (std::vector<const ld::Atom*>::const_iterator it=_atoms.begin(); it != _atoms.end(); ++it) {
1381                         (const_cast<ld::Atom*>(*it))->setLive((*it)->dontDeadStrip());
1382                 }
1383                 // and re-compute dead code
1384                 this->deadStripOptimize(true);
1385         }
1386
1387         // <rdar://problem/12386559> if -exported_symbols_list on command line, re-force scope
1388         if ( _options.hasExportMaskList() ) {
1389                 for (std::vector<const ld::Atom*>::const_iterator it=_atoms.begin(); it != _atoms.end(); ++it) {
1390                         const ld::Atom* atom = *it;
1391                         if ( atom->scope() == ld::Atom::scopeGlobal ) {
1392                                 if ( !_options.shouldExport(atom->name()) ) {
1393                                         (const_cast<ld::Atom*>(atom))->setScope(ld::Atom::scopeLinkageUnit);
1394                                 }
1395                         }
1396                 }
1397         }
1398
1399         if ( _options.outputKind() == Options::kObjectFile ) {
1400                 // if -r mode, add proxies for new undefines (e.g. ___stack_chk_fail)
1401                 this->resolveUndefines();
1402         }
1403         else {
1404                 // last chance to check for undefines
1405                 this->checkUndefines(true);
1406
1407                 // check new code does not override some dylib
1408                 this->checkDylibSymbolCollisions();
1409         }
1410 }
1411
1412
1413 void Resolver::tweakWeakness()
1414 {
1415         // <rdar://problem/7977374> Add command line options to control symbol weak-def bit on exported symbols
1416         if ( _options.hasWeakBitTweaks() ) {
1417                 for (std::vector<ld::Internal::FinalSection*>::iterator sit = _internal.sections.begin(); sit != _internal.sections.end(); ++sit) {
1418                         ld::Internal::FinalSection* sect = *sit;
1419                         for (std::vector<const ld::Atom*>::iterator ait = sect->atoms.begin(); ait != sect->atoms.end(); ++ait) {
1420                                 const ld::Atom* atom = *ait;
1421                                 if ( atom->definition() != ld::Atom::definitionRegular )
1422                                         continue;
1423                                 const char* name = atom->name();
1424                                 if ( atom->scope() == ld::Atom::scopeGlobal ) {
1425                                         if ( atom->combine() == ld::Atom::combineNever ) {
1426                                                 if ( _options.forceWeak(name) )
1427                                                         (const_cast<ld::Atom*>(atom))->setCombine(ld::Atom::combineByName);
1428                                         }
1429                                         else if ( atom->combine() == ld::Atom::combineByName ) {
1430                                                 if ( _options.forceNotWeak(name) )
1431                                                         (const_cast<ld::Atom*>(atom))->setCombine(ld::Atom::combineNever);
1432                                         }
1433                                 }
1434                                 else {
1435                                         if ( _options.forceWeakNonWildCard(name) )
1436                                                 warning("cannot force to be weak, non-external symbol %s", name);
1437                                         else if ( _options.forceNotWeakNonWildcard(name) )
1438                                                 warning("cannot force to be not-weak, non-external symbol %s", name);
1439                                 }
1440                         }
1441                 }
1442         }
1443 }
1444
1445
1446 void Resolver::resolve()
1447 {
1448         this->initializeState();
1449         this->buildAtomList();
1450         this->addInitialUndefines();
1451         this->fillInHelpersInInternalState();
1452         this->resolveUndefines();
1453         this->deadStripOptimize();
1454         this->checkUndefines();
1455         this->checkDylibSymbolCollisions();
1456         this->removeCoalescedAwayAtoms();
1457         this->fillInEntryPoint();
1458         this->linkTimeOptimize();
1459         this->fillInInternalState();
1460         this->tweakWeakness();
1461     _symbolTable.checkDuplicateSymbols();
1462 }
1463
1464
1465
1466 } // namespace tool
1467 } // namespace ld
1468
1469
1470