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