src/ld/ld.hpp

   1 /* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-
   2  *
   3  * Copyright (c) 2005-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 #ifndef __LD_HPP__
  27 #define __LD_HPP__
  28
  29 #include <stdint.h>
  30 #include <math.h>
  31 #include <unistd.h>
  32 #include <assert.h>
  33
  34 #include <vector>
  35 #include <unordered_set>
  36
  37 #include "configure.h"
  38
  39 namespace ld {
  40
  41 //
  42 // ld::File
  43 //
  44 // Abstract base class for all object or library files the linker processes.
  45 //
  46 // forEachAtom() iterates over the Atoms in the order they occur in the file.
  47 //
  48 // justInTimeforEachAtom(name) iterates over lazily created Atoms.  For instance if
  49 // File is a static library, justInTimeforEachAtom() will iterate over the base set
  50 // of Atoms from the archive member implementing 'name'.
  51 //
  52 class File
  53 {
  54 public:
  55         enum ObjcConstraint { objcConstraintNone, objcConstraintRetainRelease,
  56                                                         objcConstraintRetainReleaseOrGC, objcConstraintGC,
  57                                                         objcConstraintRetainReleaseForSimulator };
  58
  59         class AtomHandler {
  60         public:
  61                 virtual                         ~AtomHandler() {}
  62                 virtual void            doAtom(const class Atom&) = 0;
  63                 virtual void            doFile(const class File&) = 0;
  64         };
  65
  66         //
  67         // ld::File::Ordinal
  68         //
  69         // Codifies the rules of ordering input files for symbol precedence. These are:
  70         // - Input files listed on the command line are ordered according to their index in the argument list.
  71         // - Input files listed in a file list are ordered first at the index of the file list argument, then
  72         //   by index in the file list
  73         // - Input files extracted from archives are ordered using the ordinal of the archive itself plus the
  74         //   index of the object file within the archive
  75         // - Indirect dylibs are ordered after all input files derived from the command line, in the order that
  76         //   they are discovered.
  77         // - The LTO object file is last.
  78         //
  79         class Ordinal
  80         {
  81         private:
  82                 // The actual numeric ordinal. Lower values have higher precedence and a zero value is invalid.
  83                 // The 64 bit ordinal is broken into 4 16 bit chunks. The high 16 bits are a "partition" that
  84                 // is used to distinguish major ordinal groups: command line, indirect dylib, LTO.
  85                 // The remaining chunks are used according to the partition (see below).
  86                 uint64_t        _ordinal;
  87
  88                 Ordinal (uint64_t ordinal) : _ordinal(ordinal) {}
  89
  90                 enum { kArgListPartition=0, kIndirectDylibPartition=1, kLTOPartition = 2, kLinkerOptionPartition = 2, InvalidParition=0xffff };
  91                 Ordinal(uint16_t partition, uint16_t majorIndex, uint16_t minorIndex, uint16_t counter) {
  92                         _ordinal = ((uint64_t)partition<<48) | ((uint64_t)majorIndex<<32) | ((uint64_t)minorIndex<<16) | ((uint64_t)counter<<0);
  93                 }
  94
  95                 const uint16_t  partition() const               { return (_ordinal>>48)&0xffff; }
  96                 const uint16_t  majorIndex() const              { return (_ordinal>>32)&0xffff; }
  97                 const uint16_t  minorIndex() const              { return (_ordinal>>16)&0xffff; }
  98                 const uint16_t  counter() const                 { return (_ordinal>>00)&0xffff; }
  99
 100                 const Ordinal nextMajorIndex()          const { assert(majorIndex() < 0xffff); return Ordinal(_ordinal+((uint64_t)1<<32)); }
 101                 const Ordinal nextMinorIndex()          const { assert(minorIndex() < 0xffff); return Ordinal(_ordinal+((uint64_t)1<<16)); }
 102                 const Ordinal nextCounter()             const { assert(counter() < 0xffff); return Ordinal(_ordinal+((uint64_t)1<<0)); }
 103
 104         public:
 105                 Ordinal() : _ordinal(0) {};
 106
 107                 static const Ordinal NullOrdinal()              { return Ordinal((uint64_t)0); }
 108
 109                 const bool validOrdinal() const { return _ordinal != 0; }
 110
 111                 bool operator ==(const Ordinal& rhs) const { return _ordinal == rhs._ordinal; }
 112                 bool operator !=(const Ordinal& rhs) const {    return _ordinal != rhs._ordinal; }
 113                 bool operator < (const Ordinal& rhs) const { return _ordinal < rhs._ordinal; }
 114                 bool operator > (const Ordinal& rhs) const { return _ordinal > rhs._ordinal; }
 115
 116                 // For ordinals derived from the command line args the partition is ArgListPartition
 117                 // The majorIndex is the arg index that pulls in the file, file list, or archive.
 118                 // The minorIndex is used for files pulled in by a file list and the value is the index of the file in the file list.
 119                 // The counter is used for .a files and the value is the index of the object in the archive.
 120                 // Thus, an object pulled in from a .a that was listed in a file list could use all three fields.
 121                 static const Ordinal makeArgOrdinal(uint16_t argIndex) { return Ordinal(kArgListPartition, argIndex, 0, 0); };
 122                 const Ordinal nextFileListOrdinal() const { return nextMinorIndex(); }
 123                 const Ordinal archiveOrdinalWithMemberIndex(uint16_t index) const { return Ordinal(kArgListPartition, majorIndex(), minorIndex(), index); }
 124
 125                 // For indirect libraries the partition is IndirectDylibPartition and the counter is used or order the libraries.
 126                 static const ld::File::Ordinal indirectDylibBase() { return Ordinal(kIndirectDylibPartition, 0, 0, 0); }
 127                 const Ordinal nextIndirectDylibOrdinal() const { return nextCounter(); }
 128
 129                 // For the LTO mach-o the partition is LTOPartition. As there is only one LTO file no other fields are needed.
 130                 static const ld::File::Ordinal LTOOrdinal()                     { return Ordinal(kLTOPartition, 0, 0, 0); }
 131
 132                 // For linker options embedded in object files
 133                 static const ld::File::Ordinal linkeOptionBase() { return Ordinal(kIndirectDylibPartition, 1, 0, 0); }
 134                 const Ordinal nextLinkerOptionOrdinal() { nextCounter(); return *this; };
 135
 136         };
 137
 138         typedef enum { Reloc, Dylib, Archive, Other } Type;
 139
 140                                                                                 File(const char* pth, time_t modTime, Ordinal ord, Type type)
 141                                                                                         : _path(pth), _modTime(modTime), _ordinal(ord), _type(type) { }
 142         virtual                                                         ~File() {}
 143                         const char*                                     path() const                    { return _path; }
 144                         time_t                                          modificationTime() const{ return _modTime; }
 145         Ordinal                                                         ordinal() const                 { return _ordinal; }
 146         virtual bool                                            forEachAtom(AtomHandler&) const = 0;
 147         virtual bool                                            justInTimeforEachAtom(const char* name, AtomHandler&) const = 0;
 148         virtual ObjcConstraint                          objCConstraint() const                  { return objcConstraintNone; }
 149         virtual uint32_t                                        cpuSubType() const              { return 0; }
 150         virtual uint32_t                                        subFileCount() const    { return 1; }
 151     bool                                                                fileExists() const     { return _modTime != 0; }
 152         Type                                                            type() const { return _type; }
 153 private:
 154         const char*                                                     _path;
 155         time_t                                                          _modTime;
 156         const Ordinal                                           _ordinal;
 157         const Type                                                      _type;
 158 };
 159
 160
 161 //
 162 // minumum OS versions
 163 //
 164 enum MacVersionMin { macVersionUnset=0, mac10_4=0x000A0400, mac10_5=0x000A0500,
 165                                                 mac10_6=0x000A0600, mac10_7=0x000A0700, mac10_8=0x000A0800,
 166                                                 mac10_9=0x000A0900, mac10_Future=0x10000000 };
 167 enum IOSVersionMin { iOSVersionUnset=0, iOS_2_0=0x00020000, iOS_3_1=0x00030100,
 168                                                 iOS_4_2=0x00040200, iOS_4_3=0x00040300, iOS_5_0=0x00050000,
 169                                                 iOS_6_0=0x00060000, iOS_7_0=0x00070000, iOS_Future=0x10000000};
 170
 171 namespace relocatable {
 172         //
 173         // ld::relocatable::File
 174         //
 175         // Abstract base class for object files the linker processes.
 176         //
 177         // debugInfo() returns if the object file contains debugger information (stabs or dwarf).
 178         //
 179         // stabs() lazily creates a vector of Stab objects for each atom
 180         //
 181         // canScatterAtoms() true for all compiler generated code.  Hand written assembly can opt-in
 182         // via .subsections_via_symbols directive.  When true it means the linker can break up section
 183         // content at symbol boundaries and do optimizations like coalescing, dead code stripping, or
 184         // apply order files.
 185         //
 186         // optimize() used by libLTO to lazily generate code from llvm bit-code files
 187         //
 188         class File : public ld::File
 189         {
 190         public:
 191                 enum DebugInfoKind { kDebugInfoNone=0, kDebugInfoStabs=1, kDebugInfoDwarf=2, kDebugInfoStabsUUID=3 };
 192                 struct Stab {
 193                         const class Atom*       atom;
 194                         uint8_t                         type;
 195                         uint8_t                         other;
 196                         uint16_t                        desc;
 197                         uint32_t                        value;
 198                         const char*                     string;
 199                 };
 200                 typedef const std::vector< std::vector<const char*> > LinkerOptionsList;
 201
 202                                                                                         File(const char* pth, time_t modTime, Ordinal ord)
 203                                                                                                 : ld::File(pth, modTime, ord, Reloc) { }
 204                 virtual                                                         ~File() {}
 205                 virtual DebugInfoKind                           debugInfo() const = 0;
 206                 virtual const char*                                     debugInfoPath() const { return path(); }
 207                 virtual time_t                                          debugInfoModificationTime() const { return modificationTime(); }
 208                 virtual const std::vector<Stab>*        stabs() const = 0;
 209                 virtual bool                                            canScatterAtoms() const = 0;
 210                 virtual bool                                            hasLongBranchStubs()            { return false; }
 211                 virtual LinkerOptionsList*                      linkerOptions() const = 0;
 212         };
 213 } // namespace relocatable
 214
 215
 216 namespace dylib {
 217
 218         //
 219         // ld::dylib::File
 220         //
 221         // Abstract base class for dynamic shared libraries read by the linker processes.
 222         //
 223         class File : public ld::File
 224         {
 225         public:
 226                 class DylibHandler
 227                 {
 228                 public:
 229                         virtual                         ~DylibHandler() {}
 230                         virtual File*           findDylib(const char* installPath, const char* fromPath) = 0;
 231                 };
 232
 233                                                                                         File(const char* pth, time_t modTime, Ordinal ord)
 234                                                                                                 : ld::File(pth, modTime, ord, Dylib), _dylibInstallPath(NULL),
 235                                                                                                 _dylibTimeStamp(0), _dylibCurrentVersion(0), _dylibCompatibilityVersion(0),
 236                                                                                                 _explicitlyLinked(false), _implicitlyLinked(false),
 237                                                                                                 _lazyLoadedDylib(false), _forcedWeakLinked(false), _reExported(false),
 238                                                                                                 _upward(false), _dead(false) { }
 239                                 const char*                                     installPath() const                     { return _dylibInstallPath; }
 240                                 uint32_t                                        timestamp() const                       { return _dylibTimeStamp; }
 241                                 uint32_t                                        currentVersion() const          { return _dylibCurrentVersion; }
 242                                 uint32_t                                        compatibilityVersion() const{ return _dylibCompatibilityVersion; }
 243                                 void                                            setExplicitlyLinked()           { _explicitlyLinked = true; }
 244                                 bool                                            explicitlyLinked() const        { return _explicitlyLinked; }
 245                                 void                                            setImplicitlyLinked()           { _implicitlyLinked = true; }
 246                                 bool                                            implicitlyLinked() const        { return _implicitlyLinked; }
 247
 248                                 // attributes of how dylib will be used when linked
 249                                 void                                            setWillBeLazyLoadedDylb()               { _lazyLoadedDylib = true; }
 250                                 bool                                            willBeLazyLoadedDylib() const   { return _lazyLoadedDylib; }
 251                                 void                                            setForcedWeakLinked()                   { _forcedWeakLinked = true; }
 252                                 bool                                            forcedWeakLinked() const                { return _forcedWeakLinked; }
 253
 254                                 void                                            setWillBeReExported()                   { _reExported = true; }
 255                                 bool                                            willBeReExported() const                { return _reExported; }
 256                                 void                                            setWillBeUpwardDylib()                  { _upward = true; }
 257                                 bool                                            willBeUpwardDylib() const               { return _upward; }
 258                                 void                                            setWillBeRemoved(bool value)    { _dead = value; }
 259                                 bool                                            willRemoved() const                             { return _dead; }
 260
 261                 virtual void                                            processIndirectLibraries(DylibHandler* handler, bool addImplicitDylibs) = 0;
 262                 virtual bool                                            providedExportAtom() const = 0;
 263                 virtual const char*                                     parentUmbrella() const = 0;
 264                 virtual const std::vector<const char*>* allowableClients() const = 0;
 265                 virtual bool                                            hasWeakExternals() const = 0;
 266                 virtual bool                                            deadStrippable() const = 0;
 267                 virtual bool                                            hasWeakDefinition(const char* name) const = 0;
 268                 virtual bool                                            hasPublicInstallName() const = 0;
 269                 virtual bool                                            allSymbolsAreWeakImported() const = 0;
 270                 virtual const void*                                     codeSignatureDR() const = 0;
 271                 virtual bool                                            installPathVersionSpecific() const { return false; }
 272         protected:
 273                 const char*                                                     _dylibInstallPath;
 274                 uint32_t                                                        _dylibTimeStamp;
 275                 uint32_t                                                        _dylibCurrentVersion;
 276                 uint32_t                                                        _dylibCompatibilityVersion;
 277                 bool                                                            _explicitlyLinked;
 278                 bool                                                            _implicitlyLinked;
 279                 bool                                                            _lazyLoadedDylib;
 280                 bool                                                            _forcedWeakLinked;
 281                 bool                                                            _reExported;
 282                 bool                                                            _upward;
 283                 bool                                                            _dead;
 284         };
 285 } // namespace dylib
 286
 287
 288 namespace archive {
 289         //
 290         // ld::archive::File
 291         //
 292         // Abstract base class for static libraries read by the linker processes.
 293         //
 294         class File : public ld::File
 295         {
 296         public:
 297                                                                                         File(const char* pth, time_t modTime, Ordinal ord)
 298                                                                                                 : ld::File(pth, modTime, ord, Archive) { }
 299                 virtual                                                         ~File() {}
 300                 virtual bool                                            justInTimeDataOnlyforEachAtom(const char* name, AtomHandler&) const = 0;
 301         };
 302 } // namespace archive
 303
 304
 305 //
 306 // ld::Section
 307 //
 308 class Section
 309 {
 310 public:
 311         enum Type { typeUnclassified, typeCode, typePageZero, typeImportProxies, typeLinkEdit, typeMachHeader, typeStack,
 312                                 typeLiteral4, typeLiteral8, typeLiteral16, typeConstants, typeTempLTO,
 313                                 typeCString, typeNonStdCString, typeCStringPointer, typeUTF16Strings, typeCFString, typeObjC1Classes,
 314                                 typeCFI, typeLSDA, typeDtraceDOF, typeUnwindInfo, typeObjCClassRefs, typeObjC2CategoryList,
 315                                 typeZeroFill, typeTentativeDefs, typeLazyPointer, typeStub, typeNonLazyPointer, typeDyldInfo,
 316                                 typeLazyDylibPointer, typeStubHelper, typeInitializerPointers, typeTerminatorPointers,
 317                                 typeStubClose, typeLazyPointerClose, typeAbsoluteSymbols,
 318                                 typeTLVDefs, typeTLVZeroFill, typeTLVInitialValues, typeTLVInitializerPointers, typeTLVPointers,
 319                                 typeFirstSection, typeLastSection, typeDebug };
 320
 321
 322                                         Section(const char* sgName, const char* sctName,
 323                                                                 Type t, bool hidden=false)
 324                                                                 : _segmentName(sgName), _sectionName(sctName),
 325                                                                 _type(t), _hidden(hidden)  {}
 326                                         Section(const Section& sect)
 327                                                                 : _segmentName(sect.segmentName()), _sectionName(sect.sectionName()),
 328                                                                 _type(sect.type()), _hidden(sect.isSectionHidden())  {}
 329
 330         bool                    operator==(const Section& rhs) const { return ( (_hidden==rhs._hidden) &&
 331                                                                                                                 (strcmp(_segmentName, rhs._segmentName)==0) &&
 332                                                                                                                 (strcmp(_sectionName, rhs._sectionName)==0) ); }
 333         bool                    operator!=(const Section& rhs) const { return ! (*this == rhs); }
 334         const char*                     segmentName() const                     { return _segmentName; }
 335         const char*                     sectionName() const                     { return _sectionName; }
 336         Type                            type() const                            { return _type; }
 337         bool                            isSectionHidden() const         { return _hidden; }
 338
 339 private:
 340         const char*                     _segmentName;
 341         const char*                     _sectionName;
 342         Type                            _type;
 343         bool                            _hidden;
 344 };
 345
 346
 347
 348 //
 349 // ld::Fixup
 350 //
 351 // A Fixup describes how part of an Atom's content must be fixed up.  For instance,
 352 // an instruction may contain a displacement to another Atom that must be
 353 // fixed up by the linker.
 354 //
 355 // A Fixup my reference another Atom. There are two kinds of references: direct and by-name.
 356 // With a direct reference, the target is bound by the File that created it.
 357 // For instance a reference to a static would produce a direct reference.
 358 // A by-name reference requires the linker to find the target Atom with the
 359 // required name in order to be bound.
 360 //
 361 // For a link to succeed all Fixup must be bound.
 362 //
 363 // A Reference also has a fix-up-offset.  This is the offset into the content of the
 364 // Atom holding the reference where the fix-up (relocation) will be applied.
 365 //
 366 //
 367 struct Fixup
 368 {
 369         enum TargetBinding { bindingNone, bindingByNameUnbound, bindingDirectlyBound, bindingByContentBound, bindingsIndirectlyBound };
 370         enum Cluster { k1of1, k1of2, k2of2, k1of3, k2of3, k3of3, k1of4, k2of4, k3of4, k4of4, k1of5, k2of5, k3of5, k4of5, k5of5 };
 371         enum Kind       {       kindNone, kindNoneFollowOn,
 372                                         // grouping
 373                                         kindNoneGroupSubordinate,
 374                                         kindNoneGroupSubordinateFDE, kindNoneGroupSubordinateLSDA, kindNoneGroupSubordinatePersonality,
 375                                         // value calculations
 376                                         kindSetTargetAddress,
 377                                         kindSubtractTargetAddress,
 378                                         kindAddAddend,
 379                                         kindSubtractAddend,
 380                                         kindSetTargetImageOffset,
 381                                         kindSetTargetSectionOffset,
 382                                         kindSetTargetTLVTemplateOffset,
 383                                         // pointer store kinds (of current calculated value)
 384                                         kindStore8,
 385                                         kindStoreLittleEndian16,
 386                                         kindStoreLittleEndianLow24of32,
 387                                         kindStoreLittleEndian32,
 388                                         kindStoreLittleEndian64,
 389                                         kindStoreBigEndian16,
 390                                         kindStoreBigEndianLow24of32,
 391                                         kindStoreBigEndian32,
 392                                         kindStoreBigEndian64,
 393                                         // Intel specific store kinds
 394                                         kindStoreX86BranchPCRel8, kindStoreX86BranchPCRel32,
 395                                         kindStoreX86PCRel8, kindStoreX86PCRel16,
 396                                         kindStoreX86PCRel32, kindStoreX86PCRel32_1, kindStoreX86PCRel32_2, kindStoreX86PCRel32_4,
 397                                         kindStoreX86PCRel32GOTLoad, kindStoreX86PCRel32GOTLoadNowLEA, kindStoreX86PCRel32GOT,
 398                                         kindStoreX86PCRel32TLVLoad, kindStoreX86PCRel32TLVLoadNowLEA,
 399                                         kindStoreX86Abs32TLVLoad, kindStoreX86Abs32TLVLoadNowLEA,
 400                                         // ARM specific store kinds
 401                                         kindStoreARMBranch24, kindStoreThumbBranch22,
 402                                         kindStoreARMLoad12,
 403                                         kindStoreARMLow16, kindStoreARMHigh16,
 404                                         kindStoreThumbLow16, kindStoreThumbHigh16,
 405 #if SUPPORT_ARCH_arm64
 406                                         // ARM64 specific store kinds
 407                                         kindStoreARM64Branch26,
 408                                         kindStoreARM64Page21, kindStoreARM64PageOff12,
 409                                         kindStoreARM64GOTLoadPage21, kindStoreARM64GOTLoadPageOff12,
 410                                         kindStoreARM64GOTLeaPage21, kindStoreARM64GOTLeaPageOff12,
 411                                         kindStoreARM64TLVPLoadPage21, kindStoreARM64TLVPLoadPageOff12,
 412                                         kindStoreARM64PointerToGOT, kindStoreARM64PCRelToGOT,
 413 #endif
 414                                         // dtrace probes
 415                                         kindDtraceExtra,
 416                                         kindStoreX86DtraceCallSiteNop, kindStoreX86DtraceIsEnableSiteClear,
 417                                         kindStoreARMDtraceCallSiteNop, kindStoreARMDtraceIsEnableSiteClear,
 418                                         kindStoreARM64DtraceCallSiteNop, kindStoreARM64DtraceIsEnableSiteClear,
 419                                         kindStoreThumbDtraceCallSiteNop, kindStoreThumbDtraceIsEnableSiteClear,
 420                                         // lazy binding
 421                                         kindLazyTarget, kindSetLazyOffset,
 422                                         // data-in-code markers
 423                                         kindDataInCodeStartData, kindDataInCodeStartJT8, kindDataInCodeStartJT16,
 424                                         kindDataInCodeStartJT32, kindDataInCodeStartJTA32, kindDataInCodeEnd,
 425                                         // pointer store combinations
 426                                         kindStoreTargetAddressLittleEndian32,   // kindSetTargetAddress + kindStoreLittleEndian32
 427                                         kindStoreTargetAddressLittleEndian64,   // kindSetTargetAddress + kindStoreLittleEndian64
 428                                         kindStoreTargetAddressBigEndian32,              // kindSetTargetAddress + kindStoreBigEndian32
 429                                         kindStoreTargetAddressBigEndian64,              // kindSetTargetAddress + kindStoreBigEndian364
 430                                         kindSetTargetTLVTemplateOffsetLittleEndian32,  // kindSetTargetTLVTemplateOffset + kindStoreLittleEndian32
 431                                         kindSetTargetTLVTemplateOffsetLittleEndian64,  // kindSetTargetTLVTemplateOffset + kindStoreLittleEndian64
 432                                         // Intel value calculation and store combinations
 433                                         kindStoreTargetAddressX86PCRel32,               // kindSetTargetAddress + kindStoreX86PCRel32
 434                                         kindStoreTargetAddressX86BranchPCRel32, // kindSetTargetAddress + kindStoreX86BranchPCRel32
 435                                         kindStoreTargetAddressX86PCRel32GOTLoad,// kindSetTargetAddress + kindStoreX86PCRel32GOTLoad
 436                                         kindStoreTargetAddressX86PCRel32GOTLoadNowLEA,// kindSetTargetAddress + kindStoreX86PCRel32GOTLoadNowLEA
 437                                         kindStoreTargetAddressX86PCRel32TLVLoad, // kindSetTargetAddress + kindStoreX86PCRel32TLVLoad
 438                                         kindStoreTargetAddressX86PCRel32TLVLoadNowLEA, // kindSetTargetAddress + kindStoreX86PCRel32TLVLoadNowLEA
 439                                         kindStoreTargetAddressX86Abs32TLVLoad,          // kindSetTargetAddress + kindStoreX86Abs32TLVLoad
 440                                         kindStoreTargetAddressX86Abs32TLVLoadNowLEA,    // kindSetTargetAddress + kindStoreX86Abs32TLVLoadNowLEA
 441                                         // ARM value calculation and store combinations
 442                                         kindStoreTargetAddressARMBranch24,              // kindSetTargetAddress + kindStoreARMBranch24
 443                                         kindStoreTargetAddressThumbBranch22,    // kindSetTargetAddress + kindStoreThumbBranch22
 444                                         kindStoreTargetAddressARMLoad12,                // kindSetTargetAddress + kindStoreARMLoad12
 445 #if SUPPORT_ARCH_arm64
 446                                         // ARM64 value calculation and store combinations
 447                                         kindStoreTargetAddressARM64Branch26,            // kindSetTargetAddress + kindStoreARM64Branch26
 448                                         kindStoreTargetAddressARM64Page21,                      // kindSetTargetAddress + kindStoreARM64Page21
 449                                         kindStoreTargetAddressARM64PageOff12,           // kindSetTargetAddress + kindStoreARM64PageOff12
 450                                         kindStoreTargetAddressARM64GOTLoadPage21,       // kindSetTargetAddress + kindStoreARM64GOTLoadPage21
 451                                         kindStoreTargetAddressARM64GOTLoadPageOff12,// kindSetTargetAddress + kindStoreARM64GOTLoadPageOff12
 452                                         kindStoreTargetAddressARM64GOTLeaPage21,        // kindSetTargetAddress + kindStoreARM64GOTLeaPage21
 453                                         kindStoreTargetAddressARM64GOTLeaPageOff12,     // kindSetTargetAddress + kindStoreARM64GOTLeaPageOff12
 454 #endif
 455                         };
 456
 457         union {
 458                 const Atom*     target;
 459                 const char*     name;
 460                 uint64_t        addend;
 461                 uint32_t        bindingIndex;
 462         } u;
 463         uint32_t                offsetInAtom;
 464         Kind                    kind : 8;
 465         Cluster                 clusterSize : 4;
 466         bool                    weakImport : 1;
 467         TargetBinding   binding : 3;
 468         bool                    contentAddendOnly : 1;
 469         bool                    contentDetlaToAddendOnly : 1;
 470         bool                    contentIgnoresAddend : 1;
 471
 472         typedef Fixup*          iterator;
 473
 474         Fixup() :
 475                 offsetInAtom(0), kind(kindNone), clusterSize(k1of1), weakImport(false),
 476                 binding(bindingNone),
 477                 contentAddendOnly(false), contentDetlaToAddendOnly(false), contentIgnoresAddend(false) { u.target = NULL; }
 478
 479         Fixup(Kind k, Atom* targetAtom) :
 480                 offsetInAtom(0), kind(k), clusterSize(k1of1), weakImport(false),
 481                 binding(Fixup::bindingDirectlyBound),
 482                 contentAddendOnly(false), contentDetlaToAddendOnly(false), contentIgnoresAddend(false)
 483                         { assert(targetAtom != NULL); u.target = targetAtom; }
 484
 485         Fixup(uint32_t off, Cluster c, Kind k) :
 486                 offsetInAtom(off), kind(k), clusterSize(c), weakImport(false),
 487                 binding(Fixup::bindingNone),
 488                 contentAddendOnly(false), contentDetlaToAddendOnly(false), contentIgnoresAddend(false)
 489                         { u.addend = 0; }
 490
 491         Fixup(uint32_t off, Cluster c, Kind k, bool weakIm, const char* name) :
 492                 offsetInAtom(off), kind(k), clusterSize(c), weakImport(weakIm),
 493                 binding(Fixup::bindingByNameUnbound),
 494                 contentAddendOnly(false), contentDetlaToAddendOnly(false), contentIgnoresAddend(false)
 495                         { assert(name != NULL); u.name = name; }
 496
 497         Fixup(uint32_t off, Cluster c, Kind k, TargetBinding b, const char* name) :
 498                 offsetInAtom(off), kind(k), clusterSize(c), weakImport(false), binding(b),
 499                 contentAddendOnly(false), contentDetlaToAddendOnly(false), contentIgnoresAddend(false)
 500                         { assert(name != NULL); u.name = name; }
 501
 502         Fixup(uint32_t off, Cluster c, Kind k, const Atom* targetAtom) :
 503                 offsetInAtom(off), kind(k), clusterSize(c), weakImport(false),
 504                 binding(Fixup::bindingDirectlyBound),
 505                 contentAddendOnly(false), contentDetlaToAddendOnly(false), contentIgnoresAddend(false)
 506                         { assert(targetAtom != NULL); u.target = targetAtom; }
 507
 508         Fixup(uint32_t off, Cluster c, Kind k, TargetBinding b, const Atom* targetAtom) :
 509                 offsetInAtom(off), kind(k), clusterSize(c), weakImport(false), binding(b),
 510                 contentAddendOnly(false), contentDetlaToAddendOnly(false), contentIgnoresAddend(false)
 511                         { assert(targetAtom != NULL); u.target = targetAtom; }
 512
 513         Fixup(uint32_t off, Cluster c, Kind k, uint64_t addend) :
 514                 offsetInAtom(off), kind(k), clusterSize(c), weakImport(false),
 515                 binding(Fixup::bindingNone),
 516                 contentAddendOnly(false), contentDetlaToAddendOnly(false), contentIgnoresAddend(false)
 517                         { u.addend = addend; }
 518
 519         bool firstInCluster() const {
 520                 switch (clusterSize) {
 521                         case k1of1:
 522                         case k1of2:
 523                         case k1of3:
 524                         case k1of4:
 525                         case k1of5:
 526                                 return true;
 527                         default:
 528                                 break;
 529                 }
 530                 return false;
 531         }
 532
 533         bool lastInCluster() const {
 534                 switch (clusterSize) {
 535                         case k1of1:
 536                         case k2of2:
 537                         case k3of3:
 538                         case k4of4:
 539                         case k5of5:
 540                                 return true;
 541                         default:
 542                                 break;
 543                 }
 544                 return false;
 545         }
 546
 547 };
 548
 549 //
 550 // ld::Atom
 551 //
 552 // An atom is the fundamental unit of linking.  A C function or global variable is an atom.
 553 // An atom has content and attributes. The content of a function atom is the instructions
 554 // that implement the function.  The content of a global variable atom is its initial bits.
 555 //
 556 // Name:
 557 // The name of an atom is the label name generated by the compiler.  A C compiler names foo()
 558 // as _foo.  A C++ compiler names foo() as __Z3foov.
 559 // The name refers to the first byte of the content.  An atom cannot have multiple entry points.
 560 // Such code is modeled as multiple atoms, each having a "follow on" reference to the next.
 561 // A "follow on" reference is a contraint to the linker to the atoms must be laid out contiguously.
 562 //
 563 // Scope:
 564 // An atom is in one of three scopes: translation-unit, linkage-unit, or global.  These correspond
 565 // to the C visibility of static, hidden, default.
 566 //
 567 // DefinitionKind:
 568 // An atom is one of five defintion kinds:
 569 //      regular                 Most atoms.
 570 //      weak                    C++ compiler makes some functions weak if there might be multiple copies
 571 //                                      that the linker needs to coalesce.
 572 //      tentative               A straggler from ancient C when the extern did not exist. "int foo;" is ambiguous.
 573 //                                      It could be a prototype or it could be a definition.
 574 //      external                This is a "proxy" atom produced by a dylib reader.  It has no content.  It exists
 575 //                                      so that the graph of Atoms can be complete.
 576 //      external-weak   Same as external, but the definition in the dylib is weak.
 577 //
 578 // SymbolTableInclusion:
 579 // An atom may or may not be in the symbol table in an object file.
 580 //  in                          Most atoms for functions or global data
 581 //      not-in                  Anonymous atoms such literal c-strings, or other compiler generated data
 582 //  not-in-final        Atom whose name should not be in the symbol table of final linkd image (e.g. 'l' labels .eh labels)
 583 //      in-never-strip  Atom whose name the strip tool should never remove (e.g. REFERENCED_DYNAMICALLY in mach-o)
 584 //
 585 // ContentType:
 586 // Some atoms require specially processing by the linker based on their content.  For instance, zero-fill data
 587 // atom are group together at the end of the DATA segment to reduce disk size.
 588 //
 589 // ObjectAddress:
 590 // For reproducability, the linker lays out atoms in the order they occurred in the source (object) files.
 591 // The objectAddress() method returns the address of an atom in the object file so that the linker
 592 // can arrange the atoms.
 593 //
 594 //
 595 class Atom
 596 {
 597 public:
 598         enum Scope { scopeTranslationUnit, scopeLinkageUnit, scopeGlobal };
 599         enum Definition { definitionRegular, definitionTentative, definitionAbsolute, definitionProxy };
 600         enum Combine { combineNever, combineByName, combineByNameAndContent, combineByNameAndReferences };
 601         enum ContentType { typeUnclassified, typeZeroFill, typeCString, typeCFI, typeLSDA, typeSectionStart,
 602                                         typeSectionEnd, typeBranchIsland, typeLazyPointer, typeStub, typeNonLazyPointer,
 603                                         typeLazyDylibPointer, typeStubHelper, typeInitializerPointers, typeTerminatorPointers,
 604                                         typeLTOtemporary, typeResolver,
 605                                         typeTLV, typeTLVZeroFill, typeTLVInitialValue, typeTLVInitializerPointers };
 606
 607         enum SymbolTableInclusion { symbolTableNotIn, symbolTableNotInFinalLinkedImages, symbolTableIn,
 608                                                                 symbolTableInAndNeverStrip, symbolTableInAsAbsolute,
 609                                                                 symbolTableInWithRandomAutoStripLabel };
 610         enum WeakImportState { weakImportUnset, weakImportTrue, weakImportFalse };
 611
 612         struct Alignment {
 613                                         Alignment(int p2, int m=0) : powerOf2(p2), modulus(m) {}
 614                 uint8_t         trailingZeros() const { return (modulus==0) ? powerOf2 : __builtin_ctz(modulus); }
 615                 uint16_t        powerOf2;
 616                 uint16_t        modulus;
 617         };
 618         struct LineInfo {
 619                 const char* fileName;
 620                 uint32_t        atomOffset;
 621                 uint32_t        lineNumber;
 622
 623                 typedef LineInfo* iterator;
 624         };
 625         struct UnwindInfo {
 626                 uint32_t        startOffset;
 627                 uint32_t        unwindInfo;
 628
 629                 typedef UnwindInfo* iterator;
 630         };
 631
 632                                                                                         Atom(const Section& sect, Definition d, Combine c, Scope s, ContentType ct,
 633                                                                                                 SymbolTableInclusion i, bool dds, bool thumb, bool al, Alignment a) :
 634                                                                                                         _section(&sect), _address(0), _alignmentModulus(a.modulus),
 635                                                                                                         _alignmentPowerOf2(a.powerOf2), _definition(d), _combine(c),
 636                                                                                                         _dontDeadStrip(dds), _thumb(thumb), _alias(al), _autoHide(false),
 637                                                                                                         _contentType(ct), _symbolTableInclusion(i),
 638                                                                                                         _scope(s), _mode(modeSectionOffset),
 639                                                                                                         _overridesADylibsWeakDef(false), _coalescedAway(false),
 640                                                                                                         _live(false), _machoSection(0), _weakImportState(weakImportUnset)
 641                                                                                                          {
 642                                                                                                         #ifndef NDEBUG
 643                                                                                                                 switch ( _combine ) {
 644                                                                                                                         case combineByNameAndContent:
 645                                                                                                                         case combineByNameAndReferences:
 646                                                                                                                                 assert(_symbolTableInclusion != symbolTableIn);
 647                                                                                                                                 assert(_scope != scopeGlobal);
 648                                                                 break;
 649                                                             case combineByName:
 650                                                             case combineNever:
 651                                                                 break;
 652                                                                                                                 };
 653                                                                                                         #endif
 654                                                                                                          }
 655         virtual                                                                 ~Atom() {}
 656
 657         const Section&                                                  section() const                         { return *_section; }
 658         Definition                                                              definition() const                      { return _definition; }
 659         Combine                                                                 combine() const                         { return _combine; }
 660         Scope                                                                   scope() const                           { return _scope; }
 661         ContentType                                                             contentType() const                     { return _contentType; }
 662         SymbolTableInclusion                                    symbolTableInclusion() const{ return _symbolTableInclusion; }
 663         bool                                                                    dontDeadStrip() const           { return _dontDeadStrip; }
 664         bool                                                                    isThumb() const                         { return _thumb; }
 665         bool                                                                    isAlias() const                         { return _alias; }
 666         Alignment                                                               alignment() const                       { return Alignment(_alignmentPowerOf2, _alignmentModulus); }
 667         bool                                                                    overridesDylibsWeakDef() const  { return _overridesADylibsWeakDef; }
 668         bool                                                                    coalescedAway() const           { return _coalescedAway; }
 669         bool                                                                    weakImported() const            { return _weakImportState == weakImportTrue; }
 670         WeakImportState                                                 weakImportState() const         { return _weakImportState; }
 671         bool                                                                    autoHide() const                        { return _autoHide; }
 672         bool                                                                    live() const                            { return _live; }
 673         uint8_t                                                                 machoSection() const            { assert(_machoSection != 0); return _machoSection; }
 674
 675         void                                                                    setScope(Scope s)                       { _scope = s; }
 676         void                                                                    setSymbolTableInclusion(SymbolTableInclusion i)
 677                                                                                                                                                 { _symbolTableInclusion = i; }
 678         void                                                                    setCombine(Combine c)           { _combine = c; }
 679         void                                                                    setOverridesDylibsWeakDef()     { _overridesADylibsWeakDef = true; }
 680         void                                                                    setCoalescedAway()                      { _coalescedAway = true; }
 681         void                                                                    setWeakImportState(bool w)      { assert(_definition == definitionProxy); _weakImportState = ( w ? weakImportTrue : weakImportFalse); }
 682         void                                                                    setAutoHide()                           { _autoHide = true; }
 683         void                                                                    setLive()                                       { _live = true; }
 684         void                                                                    setLive(bool value)                     { _live = value; }
 685         void                                                                    setMachoSection(unsigned x) { assert(x != 0); assert(x < 256); _machoSection = x; }
 686         void                                                                    setSectionOffset(uint64_t o){ assert(_mode == modeSectionOffset); _address = o; _mode = modeSectionOffset; }
 687         void                                                                    setSectionStartAddress(uint64_t a) { assert(_mode == modeSectionOffset); _address += a; _mode = modeFinalAddress; }
 688         uint64_t                                                                sectionOffset() const           { assert(_mode == modeSectionOffset); return _address; }
 689         uint64_t                                                                finalAddress() const            { assert(_mode == modeFinalAddress); return _address; }
 690 #ifndef NDEBUG
 691         bool                                                                    finalAddressMode() const    { return (_mode == modeFinalAddress); }
 692 #endif
 693         virtual const File*                                             file() const = 0;
 694         virtual const char*                                             translationUnitSource() const { return NULL; }
 695         virtual const char*                                             name() const = 0;
 696         virtual uint64_t                                                objectAddress() const = 0;
 697         virtual uint64_t                                                size() const = 0;
 698         virtual void                                                    copyRawContent(uint8_t buffer[]) const = 0;
 699         virtual const uint8_t*                                  rawContentPointer() const { return NULL; }
 700         virtual unsigned long                                   contentHash(const class IndirectBindingTable&) const { return 0; }
 701         virtual bool                                                    canCoalesceWith(const Atom& rhs, const class IndirectBindingTable&) const { return false; }
 702         virtual Fixup::iterator                                 fixupsBegin() const     { return NULL; }
 703         virtual Fixup::iterator                                 fixupsEnd() const       { return NULL; }
 704         bool                                                                    hasFixupsOfKind(Fixup::Kind kind) const {
 705                 for (ld::Fixup::iterator fit = fixupsBegin(), end=fixupsEnd(); fit != end; ++fit) {
 706                         if ( fit->kind == kind ) return true;
 707                 }
 708                 return false;
 709         }
 710
 711         virtual UnwindInfo::iterator                    beginUnwind() const { return NULL; }
 712         virtual UnwindInfo::iterator                    endUnwind() const       { return NULL; }
 713         virtual LineInfo::iterator                              beginLineInfo() const { return NULL; }
 714         virtual LineInfo::iterator                              endLineInfo() const { return NULL; }
 715
 716 protected:
 717         enum AddressMode { modeSectionOffset, modeFinalAddress };
 718
 719                                                                                         void setAttributesFromAtom(const Atom& a) {
 720                                                                                                         _section = a._section;
 721                                                                                                         _alignmentModulus = a._alignmentModulus;
 722                                                                                                         _alignmentPowerOf2 = a._alignmentPowerOf2;
 723                                                                                                         _definition = a._definition;
 724                                                                                                         _combine = a._combine;
 725                                                                                                         _dontDeadStrip = a._dontDeadStrip;
 726                                                                                                         _thumb = a._thumb;
 727                                                                                                         _autoHide = a._autoHide;
 728                                                                                                         _contentType = a._contentType;
 729                                                                                                         _symbolTableInclusion = a._symbolTableInclusion;
 730                                                                                                         _scope = a._scope;
 731                                                                                                         _mode = a._mode;
 732                                                                                                         _overridesADylibsWeakDef = a._overridesADylibsWeakDef;
 733                                                                                                         _coalescedAway = a._coalescedAway;
 734                                                                                                         _weakImportState = a._weakImportState;
 735                                                                                                 }
 736
 737         const Section *                                         _section;
 738         uint64_t                                                        _address;
 739         uint16_t                                                        _alignmentModulus;
 740         uint8_t                                                         _alignmentPowerOf2;
 741         Definition                                                      _definition : 2;
 742         Combine                                                         _combine : 2;
 743         bool                                                            _dontDeadStrip : 1;
 744         bool                                                            _thumb : 1;
 745         bool                                                            _alias : 1;
 746         int                                                                     _autoHide : 1;
 747         ContentType                                                     _contentType : 5;
 748         SymbolTableInclusion                            _symbolTableInclusion : 3;
 749         Scope                                                           _scope : 2;
 750         AddressMode                                                     _mode: 2;
 751         bool                                                            _overridesADylibsWeakDef : 1;
 752         bool                                                            _coalescedAway : 1;
 753         bool                                                            _live : 1;
 754         unsigned                                                        _machoSection : 8;
 755         WeakImportState                                         _weakImportState : 2;
 756 };
 757
 758
 759 class IndirectBindingTable
 760 {
 761 public:
 762         virtual const char*                     indirectName(uint32_t bindingIndex) const = 0;
 763         virtual const ld::Atom*         indirectAtom(uint32_t bindingIndex) const = 0;
 764 };
 765
 766
 767
 768 // utility classes for using std::unordered_map with c-strings
 769 struct CStringHash {
 770         size_t operator()(const char* __s) const {
 771                 size_t __h = 0;
 772                 for ( ; *__s; ++__s)
 773                         __h = 5 * __h + *__s;
 774                 return __h;
 775         };
 776 };
 777 struct CStringEquals
 778 {
 779         bool operator()(const char* left, const char* right) const { return (strcmp(left, right) == 0); }
 780 };
 781
 782 typedef std::unordered_set<const char*, ld::CStringHash, ld::CStringEquals>  CStringSet;
 783
 784 class Internal
 785 {
 786 public:
 787         class FinalSection : public ld::Section {
 788         public:
 789                                                                                 FinalSection(const Section& sect) : Section(sect), address(0),
 790                                                                                                 fileOffset(0), size(0), alignment(0),
 791                                                                                                 indirectSymTabStartIndex(0), indirectSymTabElementSize(0),
 792                                                                                                 relocStart(0), relocCount(0),
 793                                                                                                 hasLocalRelocs(false), hasExternalRelocs(false) {}
 794                 std::vector<const Atom*>                atoms;
 795                 uint64_t                                                address;
 796                 uint64_t                                                fileOffset;
 797                 uint64_t                                                size;
 798                 uint32_t                                                alignmentPaddingBytes;
 799                 uint8_t                                                 alignment;
 800                 uint32_t                                                indirectSymTabStartIndex;
 801                 uint32_t                                                indirectSymTabElementSize;
 802                 uint32_t                                                relocStart;
 803                 uint32_t                                                relocCount;
 804                 bool                                                    hasLocalRelocs;
 805                 bool                                                    hasExternalRelocs;
 806         };
 807
 808
 809         virtual ld::Internal::FinalSection*     addAtom(const Atom&) = 0;
 810         virtual ld::Internal::FinalSection* getFinalSection(const ld::Section& inputSection) = 0;
 811         virtual                                                         ~Internal() {}
 812                                                                                 Internal() : bundleLoader(NULL),
 813                                                                                         entryPoint(NULL), classicBindingHelper(NULL),
 814                                                                                         lazyBindingHelper(NULL), compressedFastBinderProxy(NULL),
 815                                                                                         objcObjectConstraint(ld::File::objcConstraintNone),
 816                                                                                         objcDylibConstraint(ld::File::objcConstraintNone),
 817                                                                                         cpuSubType(0),
 818                                                                                         allObjectFilesScatterable(true),
 819                                                                                         someObjectFileHasDwarf(false), usingHugeSections(false) { }
 820
 821         std::vector<FinalSection*>                                      sections;
 822         std::vector<ld::dylib::File*>                           dylibs;
 823         std::vector<ld::relocatable::File::Stab>        stabs;
 824         CStringSet                                                                      linkerOptionLibraries;
 825         CStringSet                                                                      linkerOptionFrameworks;
 826         std::vector<const ld::Atom*>                            indirectBindingTable;
 827         const ld::dylib::File*                                          bundleLoader;
 828         const Atom*                                                                     entryPoint;
 829         const Atom*                                                                     classicBindingHelper;
 830         const Atom*                                                                     lazyBindingHelper;
 831         const Atom*                                                                     compressedFastBinderProxy;
 832         ld::File::ObjcConstraint                                        objcObjectConstraint;
 833         ld::File::ObjcConstraint                                        objcDylibConstraint;
 834         uint32_t                                                                        cpuSubType;
 835         bool                                                                            allObjectFilesScatterable;
 836         bool                                                                            someObjectFileHasDwarf;
 837         bool                                                                            usingHugeSections;
 838 };
 839
 840
 841
 842
 843
 844
 845
 846
 847
 848
 849
 850 } // namespace ld
 851
 852 #endif // __LD_HPP__