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