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