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