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