src/ImageLoader.cpp

   1 /* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-
   2  *
   3  * Copyright (c) 2004-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 #define __STDC_LIMIT_MACROS
  26 #include <stdint.h>
  27 #include <stdlib.h>
  28 #include <errno.h>
  29 #include <fcntl.h>
  30 #include <mach/mach.h>
  31 #include <mach-o/fat.h>
  32 #include <sys/types.h>
  33 #include <sys/stat.h>
  34 #include <sys/mman.h>
  35 #include <sys/param.h>
  36 #include <sys/mount.h>
  37 #include <sys/sysctl.h>
  38 #include <libkern/OSAtomic.h>
  39 #include <string_view>
  40
  41 #include <atomic>
  42
  43 #include "Tracing.h"
  44
  45 #include "ImageLoader.h"
  46
  47
  48 uint32_t                                                                ImageLoader::fgImagesUsedFromSharedCache = 0;
  49 uint32_t                                                                ImageLoader::fgImagesWithUsedPrebinding = 0;
  50 uint32_t                                                                ImageLoader::fgImagesRequiringCoalescing = 0;
  51 uint32_t                                                                ImageLoader::fgImagesHasWeakDefinitions = 0;
  52 uint32_t                                                                ImageLoader::fgTotalRebaseFixups = 0;
  53 uint32_t                                                                ImageLoader::fgTotalBindFixups = 0;
  54 uint32_t                                                                ImageLoader::fgTotalBindSymbolsResolved = 0;
  55 uint32_t                                                                ImageLoader::fgTotalBindImageSearches = 0;
  56 uint32_t                                                                ImageLoader::fgTotalLazyBindFixups = 0;
  57 uint32_t                                                                ImageLoader::fgTotalPossibleLazyBindFixups = 0;
  58 uint32_t                                                                ImageLoader::fgTotalSegmentsMapped = 0;
  59 uint64_t                                                                ImageLoader::fgTotalBytesMapped = 0;
  60 uint64_t                                                                ImageLoader::fgTotalLoadLibrariesTime;
  61 uint64_t                                                                ImageLoader::fgTotalObjCSetupTime = 0;
  62 uint64_t                                                                ImageLoader::fgTotalDebuggerPausedTime = 0;
  63 uint64_t                                                                ImageLoader::fgTotalRebindCacheTime = 0;
  64 uint64_t                                                                ImageLoader::fgTotalRebaseTime;
  65 uint64_t                                                                ImageLoader::fgTotalBindTime;
  66 uint64_t                                                                ImageLoader::fgTotalWeakBindTime;
  67 uint64_t                                                                ImageLoader::fgTotalDOF;
  68 uint64_t                                                                ImageLoader::fgTotalInitTime;
  69 uint16_t                                                                ImageLoader::fgLoadOrdinal = 0;
  70 uint32_t                                                                ImageLoader::fgSymbolTrieSearchs = 0;
  71 std::vector<ImageLoader::InterposeTuple>ImageLoader::fgInterposingTuples;
  72 uintptr_t                                                               ImageLoader::fgNextPIEDylibAddress = 0;
  73
  74
  75
  76 ImageLoader::ImageLoader(const char* path, unsigned int libCount)
  77         : fPath(path), fRealPath(NULL), fDevice(0), fInode(0), fLastModified(0),
  78         fPathHash(0), fDlopenReferenceCount(0), fInitializerRecursiveLock(NULL),
  79         fLoadOrder(fgLoadOrdinal++), fDepth(0), fObjCMappedNotified(false), fState(0), fLibraryCount(libCount),
  80         fMadeReadOnly(false), fAllLibraryChecksumsAndLoadAddressesMatch(false), fLeaveMapped(false), fNeverUnload(false),
  81         fHideSymbols(false), fMatchByInstallName(false),
  82         fInterposed(false), fRegisteredDOF(false), fAllLazyPointersBound(false),
  83     fBeingRemoved(false), fAddFuncNotified(false),
  84         fPathOwnedByImage(false), fIsReferencedDownward(false),
  85         fWeakSymbolsBound(false)
  86 {
  87         if ( fPath != NULL )
  88                 fPathHash = hash(fPath);
  89         if ( libCount > 512 )
  90                 dyld::throwf("too many dependent dylibs in %s", path);
  91 }
  92
  93
  94 void ImageLoader::deleteImage(ImageLoader* image)
  95 {
  96         delete image;
  97 }
  98
  99
 100 ImageLoader::~ImageLoader()
 101 {
 102         if ( fRealPath != NULL )
 103                 delete [] fRealPath;
 104         if ( fPathOwnedByImage && (fPath != NULL) )
 105                 delete [] fPath;
 106 }
 107
 108 void ImageLoader::setFileInfo(dev_t device, ino_t inode, time_t modDate)
 109 {
 110         fDevice = device;
 111         fInode = inode;
 112         fLastModified = modDate;
 113 }
 114
 115 void ImageLoader::setMapped(const LinkContext& context)
 116 {
 117         fState = dyld_image_state_mapped;
 118         context.notifySingle(dyld_image_state_mapped, this, NULL);  // note: can throw exception
 119 }
 120
 121 int ImageLoader::compare(const ImageLoader* right) const
 122 {
 123         if ( this->fDepth == right->fDepth ) {
 124                 if ( this->fLoadOrder == right->fLoadOrder )
 125                         return 0;
 126                 else if ( this->fLoadOrder < right->fLoadOrder )
 127                         return -1;
 128                 else
 129                         return 1;
 130         }
 131         else {
 132                 if ( this->fDepth < right->fDepth )
 133                         return -1;
 134                 else
 135                         return 1;
 136         }
 137 }
 138
 139 void ImageLoader::setPath(const char* path)
 140 {
 141         if ( fPathOwnedByImage && (fPath != NULL) )
 142                 delete [] fPath;
 143         fPath = new char[strlen(path)+1];
 144         strcpy((char*)fPath, path);
 145         fPathOwnedByImage = true;  // delete fPath when this image is destructed
 146         fPathHash = hash(fPath);
 147         if ( fRealPath != NULL ) {
 148                 delete [] fRealPath;
 149                 fRealPath = NULL;
 150         }
 151 }
 152
 153 void ImageLoader::setPathUnowned(const char* path)
 154 {
 155         if ( fPathOwnedByImage && (fPath != NULL) ) {
 156                 delete [] fPath;
 157         }
 158         fPath = path;
 159         fPathOwnedByImage = false;
 160         fPathHash = hash(fPath);
 161 }
 162
 163 void ImageLoader::setPaths(const char* path, const char* realPath)
 164 {
 165         this->setPath(path);
 166         fRealPath = new char[strlen(realPath)+1];
 167         strcpy((char*)fRealPath, realPath);
 168 }
 169
 170
 171 const char* ImageLoader::getRealPath() const
 172 {
 173         if ( fRealPath != NULL )
 174                 return fRealPath;
 175         else
 176                 return fPath;
 177 }
 178
 179 uint32_t ImageLoader::hash(const char* path)
 180 {
 181         // this does not need to be a great hash
 182         // it is just used to reduce the number of strcmp() calls
 183         // of existing images when loading a new image
 184         uint32_t h = 0;
 185         for (const char* s=path; *s != '\0'; ++s)
 186                 h = h*5 + *s;
 187         return h;
 188 }
 189
 190 bool ImageLoader::matchInstallPath() const
 191 {
 192         return fMatchByInstallName;
 193 }
 194
 195 void ImageLoader::setMatchInstallPath(bool match)
 196 {
 197         fMatchByInstallName = match;
 198 }
 199
 200 bool ImageLoader::statMatch(const struct stat& stat_buf) const
 201 {
 202         return ( (this->fDevice == stat_buf.st_dev) && (this->fInode == stat_buf.st_ino) );
 203 }
 204
 205 const char* ImageLoader::shortName(const char* fullName)
 206 {
 207         // try to return leaf name
 208         if ( fullName != NULL ) {
 209                 const char* s = strrchr(fullName, '/');
 210                 if ( s != NULL )
 211                         return &s[1];
 212         }
 213         return fullName;
 214 }
 215
 216 const char* ImageLoader::getShortName() const
 217 {
 218         return shortName(fPath);
 219 }
 220
 221 void ImageLoader::setLeaveMapped()
 222 {
 223         fLeaveMapped = true;
 224 }
 225
 226 void ImageLoader::setHideExports(bool hide)
 227 {
 228         fHideSymbols = hide;
 229 }
 230
 231 bool ImageLoader::hasHiddenExports() const
 232 {
 233         return fHideSymbols;
 234 }
 235
 236 bool ImageLoader::isLinked() const
 237 {
 238         return (fState >= dyld_image_state_bound);
 239 }
 240
 241 time_t ImageLoader::lastModified() const
 242 {
 243         return fLastModified;
 244 }
 245
 246 bool ImageLoader::containsAddress(const void* addr) const
 247 {
 248         for(unsigned int i=0, e=segmentCount(); i < e; ++i) {
 249                 const uint8_t* start = (const uint8_t*)segActualLoadAddress(i);
 250                 const uint8_t* end = (const uint8_t*)segActualEndAddress(i);
 251                 if ( (start <= addr) && (addr < end) && !segUnaccessible(i) )
 252                         return true;
 253         }
 254         return false;
 255 }
 256
 257 bool ImageLoader::overlapsWithAddressRange(const void* start, const void* end) const
 258 {
 259         for(unsigned int i=0, e=segmentCount(); i < e; ++i) {
 260                 const uint8_t* segStart = (const uint8_t*)segActualLoadAddress(i);
 261                 const uint8_t* segEnd = (const uint8_t*)segActualEndAddress(i);
 262                 if ( strcmp(segName(i), "__UNIXSTACK") == 0 ) {
 263                         // __UNIXSTACK never slides.  This is the only place that cares
 264                         // and checking for that segment name in segActualLoadAddress()
 265                         // is too expensive.
 266                         segStart -= getSlide();
 267                         segEnd -= getSlide();
 268                 }
 269                 if ( (start <= segStart) && (segStart < end) )
 270                         return true;
 271                 if ( (start <= segEnd) && (segEnd < end) )
 272                         return true;
 273                 if ( (segStart < start) && (end < segEnd) )
 274                         return true;
 275         }
 276         return false;
 277 }
 278
 279 void ImageLoader::getMappedRegions(MappedRegion*& regions) const
 280 {
 281         for(unsigned int i=0, e=segmentCount(); i < e; ++i) {
 282                 MappedRegion region;
 283                 region.address = segActualLoadAddress(i);
 284                 region.size = segSize(i);
 285                 *regions++ = region;
 286         }
 287 }
 288
 289
 290
 291 bool ImageLoader::dependsOn(ImageLoader* image) {
 292         for(unsigned int i=0; i < libraryCount(); ++i) {
 293                 if ( libImage(i) == image )
 294                         return true;
 295         }
 296         return false;
 297 }
 298
 299
 300 static bool notInImgageList(const ImageLoader* image, const ImageLoader** dsiStart, const ImageLoader** dsiCur)
 301 {
 302         for (const ImageLoader** p = dsiStart; p < dsiCur; ++p)
 303                 if ( *p == image )
 304                         return false;
 305         return true;
 306 }
 307
 308 bool ImageLoader::findExportedSymbolAddress(const LinkContext& context, const char* symbolName,
 309                                                                                         const ImageLoader* requestorImage, int requestorOrdinalOfDef,
 310                                                                                         bool runResolver, const ImageLoader** foundIn, uintptr_t* address) const
 311 {
 312         const Symbol* sym = this->findExportedSymbol(symbolName, true, foundIn);
 313         if ( sym != NULL ) {
 314                 *address = (*foundIn)->getExportedSymbolAddress(sym, context, requestorImage, runResolver);
 315                 return true;
 316         }
 317         return false;
 318 }
 319
 320
 321 // private method that handles circular dependencies by only search any image once
 322 const ImageLoader::Symbol* ImageLoader::findExportedSymbolInDependentImagesExcept(const char* name,
 323                         const ImageLoader** dsiStart, const ImageLoader**& dsiCur, const ImageLoader** dsiEnd, const ImageLoader** foundIn) const
 324 {
 325         const ImageLoader::Symbol* sym;
 326         // search self
 327         if ( notInImgageList(this, dsiStart, dsiCur) ) {
 328                 sym = this->findExportedSymbol(name, false, this->getPath(), foundIn);
 329                 if ( sym != NULL )
 330                         return sym;
 331                 *dsiCur++ = this;
 332         }
 333
 334         // search directly dependent libraries
 335         for(unsigned int i=0; i < libraryCount(); ++i) {
 336                 ImageLoader* dependentImage = libImage(i);
 337                 if ( (dependentImage != NULL) && notInImgageList(dependentImage, dsiStart, dsiCur) ) {
 338                         sym = dependentImage->findExportedSymbol(name, false, libPath(i), foundIn);
 339                         if ( sym != NULL )
 340                                 return sym;
 341                 }
 342         }
 343
 344         // search indirectly dependent libraries
 345         for(unsigned int i=0; i < libraryCount(); ++i) {
 346                 ImageLoader* dependentImage = libImage(i);
 347                 if ( (dependentImage != NULL) && notInImgageList(dependentImage, dsiStart, dsiCur) ) {
 348                         *dsiCur++ = dependentImage;
 349                         sym = dependentImage->findExportedSymbolInDependentImagesExcept(name, dsiStart, dsiCur, dsiEnd, foundIn);
 350                         if ( sym != NULL )
 351                                 return sym;
 352                 }
 353         }
 354
 355         return NULL;
 356 }
 357
 358
 359 const ImageLoader::Symbol* ImageLoader::findExportedSymbolInDependentImages(const char* name, const LinkContext& context, const ImageLoader** foundIn) const
 360 {
 361         unsigned int imageCount = context.imageCount()+2;
 362         const ImageLoader* dontSearchImages[imageCount];
 363         dontSearchImages[0] = this; // don't search this image
 364         const ImageLoader** cur = &dontSearchImages[1];
 365         return this->findExportedSymbolInDependentImagesExcept(name, &dontSearchImages[0], cur, &dontSearchImages[imageCount], foundIn);
 366 }
 367
 368 const ImageLoader::Symbol* ImageLoader::findExportedSymbolInImageOrDependentImages(const char* name, const LinkContext& context, const ImageLoader** foundIn) const
 369 {
 370         unsigned int imageCount = context.imageCount()+2;
 371         const ImageLoader* dontSearchImages[imageCount];
 372         const ImageLoader** cur = &dontSearchImages[0];
 373         return this->findExportedSymbolInDependentImagesExcept(name, &dontSearchImages[0], cur, &dontSearchImages[imageCount], foundIn);
 374 }
 375
 376 // this is called by initializeMainExecutable() to interpose on the initial set of images
 377 void ImageLoader::applyInterposing(const LinkContext& context)
 378 {
 379         dyld3::ScopedTimer timer(DBG_DYLD_TIMING_APPLY_INTERPOSING, 0, 0, 0);
 380         if ( fgInterposingTuples.size() != 0 )
 381                 this->recursiveApplyInterposing(context);
 382 }
 383
 384
 385 uintptr_t ImageLoader::interposedAddress(const LinkContext& context, uintptr_t address, const ImageLoader* inImage, const ImageLoader* onlyInImage)
 386 {
 387         //dyld::log("interposedAddress(0x%08llX), tupleCount=%lu\n", (uint64_t)address, fgInterposingTuples.size());
 388         for (std::vector<InterposeTuple>::iterator it=fgInterposingTuples.begin(); it != fgInterposingTuples.end(); it++) {
 389                 //dyld::log("    interposedAddress: replacee=0x%08llX, replacement=0x%08llX, neverImage=%p, onlyImage=%p, inImage=%p\n",
 390                 //                              (uint64_t)it->replacee, (uint64_t)it->replacement,  it->neverImage, it->onlyImage, inImage);
 391                 // replace all references to 'replacee' with 'replacement'
 392                 if ( (address == it->replacee) && (inImage != it->neverImage) && ((it->onlyImage == NULL) || (inImage == it->onlyImage)) ) {
 393                         if ( context.verboseInterposing ) {
 394                                 dyld::log("dyld interposing: replace 0x%lX with 0x%lX\n", it->replacee, it->replacement);
 395                         }
 396                         return it->replacement;
 397                 }
 398         }
 399         return address;
 400 }
 401
 402 void ImageLoader::applyInterposingToDyldCache(const LinkContext& context) {
 403         if (!context.dyldCache)
 404                 return;
 405         if (!context.dyldCache->header.builtFromChainedFixups)
 406                 return;
 407         if (fgInterposingTuples.empty())
 408                 return;
 409         // For each of the interposed addresses, see if any of them are in the shared cache.  If so, find
 410         // that image and apply its patch table to all uses.
 411         uintptr_t cacheStart = (uintptr_t)context.dyldCache;
 412         for (std::vector<InterposeTuple>::iterator it=fgInterposingTuples.begin(); it != fgInterposingTuples.end(); it++) {
 413                 if ( context.verboseInterposing )
 414                         dyld::log("dyld: interpose: Trying to interpose address 0x%08llx\n", (uint64_t)it->replacee);
 415                 uint32_t imageIndex;
 416                 uint32_t cacheOffsetOfReplacee = (uint32_t)(it->replacee - cacheStart);
 417                 if (!context.dyldCache->addressInText(cacheOffsetOfReplacee, &imageIndex))
 418                         continue;
 419                 dyld3::closure::ImageNum imageInCache = imageIndex+1;
 420                 if ( context.verboseInterposing )
 421                         dyld::log("dyld: interpose: Found shared cache image %d for 0x%08llx\n", imageInCache, (uint64_t)it->replacee);
 422                 context.dyldCache->forEachPatchableExport(imageIndex, ^(uint32_t cacheOffsetOfImpl, const char* exportName) {
 423                         // Skip patching anything other than this symbol
 424                         if (cacheOffsetOfImpl != cacheOffsetOfReplacee)
 425                                 return;
 426                         if ( context.verboseInterposing ) {
 427                                 const dyld3::closure::Image* image = context.dyldCache->cachedDylibsImageArray()->imageForNum(imageInCache);
 428                                 dyld::log("dyld: interpose: Patching uses of symbol %s in shared cache binary at %s\n", exportName, image->path());
 429                         }
 430                         uintptr_t newLoc = it->replacement;
 431                         context.dyldCache->forEachPatchableUseOfExport(imageIndex, cacheOffsetOfImpl, ^(dyld_cache_patchable_location patchLocation) {
 432                                 uintptr_t* loc = (uintptr_t*)(cacheStart+patchLocation.cacheOffset);
 433 #if __has_feature(ptrauth_calls)
 434                                 if ( patchLocation.authenticated ) {
 435                                         dyld3::MachOLoaded::ChainedFixupPointerOnDisk ptr = *(dyld3::MachOLoaded::ChainedFixupPointerOnDisk*)loc;
 436                                         ptr.arm64e.authRebase.auth      = true;
 437                                         ptr.arm64e.authRebase.addrDiv   = patchLocation.usesAddressDiversity;
 438                                         ptr.arm64e.authRebase.diversity = patchLocation.discriminator;
 439                                         ptr.arm64e.authRebase.key       = patchLocation.key;
 440                                         *loc = ptr.arm64e.signPointer(loc, newLoc + DyldSharedCache::getAddend(patchLocation));
 441                                         if ( context.verboseInterposing )
 442                                                 dyld::log("dyld: interpose: *%p = %p (JOP: diversity 0x%04X, addr-div=%d, key=%s)\n",
 443                                                                   loc, (void*)*loc, patchLocation.discriminator, patchLocation.usesAddressDiversity, DyldSharedCache::keyName(patchLocation));
 444                                         return;
 445                                 }
 446 #endif
 447                                 if ( context.verboseInterposing )
 448                                         dyld::log("dyld: interpose: *%p = 0x%0llX (dyld cache patch) to %s\n", loc, newLoc + DyldSharedCache::getAddend(patchLocation), exportName);
 449                                 *loc = newLoc + (uintptr_t)DyldSharedCache::getAddend(patchLocation);
 450                         });
 451                 });
 452         }
 453 }
 454
 455 void ImageLoader::addDynamicInterposingTuples(const struct dyld_interpose_tuple array[], size_t count)
 456 {
 457         for(size_t i=0; i < count; ++i) {
 458                 ImageLoader::InterposeTuple tuple;
 459                 tuple.replacement               = (uintptr_t)array[i].replacement;
 460                 tuple.neverImage                = NULL;
 461                 tuple.onlyImage             = this;
 462                 tuple.replacee                  = (uintptr_t)array[i].replacee;
 463                 // chain to any existing interpositions
 464                 for (std::vector<InterposeTuple>::iterator it=fgInterposingTuples.begin(); it != fgInterposingTuples.end(); it++) {
 465                         if ( (it->replacee == tuple.replacee) && (it->onlyImage == this) ) {
 466                                 tuple.replacee = it->replacement;
 467                         }
 468                 }
 469                 ImageLoader::fgInterposingTuples.push_back(tuple);
 470         }
 471 }
 472
 473 // <rdar://problem/29099600> dyld should tell the kernel when it is doing root fix-ups
 474 void ImageLoader::vmAccountingSetSuspended(const LinkContext& context, bool suspend)
 475 {
 476 #if __arm__ || __arm64__
 477         static bool sVmAccountingSuspended = false;
 478         if ( suspend == sVmAccountingSuspended )
 479                 return;
 480     if ( context.verboseBind )
 481         dyld::log("set vm.footprint_suspend=%d\n", suspend);
 482     int newValue = suspend ? 1 : 0;
 483     int oldValue = 0;
 484     size_t newlen = sizeof(newValue);
 485     size_t oldlen = sizeof(oldValue);
 486     int ret = sysctlbyname("vm.footprint_suspend", &oldValue, &oldlen, &newValue, newlen);
 487     if ( context.verboseBind && (ret != 0) )
 488                 dyld::log("vm.footprint_suspend => %d, errno=%d\n", ret, errno);
 489         sVmAccountingSuspended = suspend;
 490 #endif
 491 }
 492
 493
 494 void ImageLoader::link(const LinkContext& context, bool forceLazysBound, bool preflightOnly, bool neverUnload, const RPathChain& loaderRPaths, const char* imagePath)
 495 {
 496         //dyld::log("ImageLoader::link(%s) refCount=%d, neverUnload=%d\n", imagePath, fDlopenReferenceCount, fNeverUnload);
 497
 498         // clear error strings
 499         (*context.setErrorStrings)(0, NULL, NULL, NULL);
 500
 501         uint64_t t0 = mach_absolute_time();
 502         this->recursiveLoadLibraries(context, preflightOnly, loaderRPaths, imagePath);
 503         context.notifyBatch(dyld_image_state_dependents_mapped, preflightOnly);
 504
 505         // we only do the loading step for preflights
 506         if ( preflightOnly )
 507                 return;
 508
 509         uint64_t t1 = mach_absolute_time();
 510         context.clearAllDepths();
 511         this->recursiveUpdateDepth(context.imageCount());
 512
 513         __block uint64_t t2, t3, t4, t5;
 514         {
 515                 dyld3::ScopedTimer(DBG_DYLD_TIMING_APPLY_FIXUPS, 0, 0, 0);
 516                 t2 = mach_absolute_time();
 517                 this->recursiveRebaseWithAccounting(context);
 518                 context.notifyBatch(dyld_image_state_rebased, false);
 519
 520                 t3 = mach_absolute_time();
 521                 if ( !context.linkingMainExecutable )
 522                         this->recursiveBindWithAccounting(context, forceLazysBound, neverUnload);
 523
 524                 t4 = mach_absolute_time();
 525                 if ( !context.linkingMainExecutable )
 526                         this->weakBind(context);
 527                 t5 = mach_absolute_time();
 528         }
 529
 530         // interpose any dynamically loaded images
 531         if ( !context.linkingMainExecutable && (fgInterposingTuples.size() != 0) ) {
 532                 dyld3::ScopedTimer timer(DBG_DYLD_TIMING_APPLY_INTERPOSING, 0, 0, 0);
 533                 this->recursiveApplyInterposing(context);
 534         }
 535
 536         // now that all fixups are done, make __DATA_CONST segments read-only
 537         if ( !context.linkingMainExecutable )
 538                 this->recursiveMakeDataReadOnly(context);
 539
 540     if ( !context.linkingMainExecutable )
 541         context.notifyBatch(dyld_image_state_bound, false);
 542         uint64_t t6 = mach_absolute_time();
 543
 544         if ( context.registerDOFs != NULL ) {
 545                 std::vector<DOFInfo> dofs;
 546                 this->recursiveGetDOFSections(context, dofs);
 547                 context.registerDOFs(dofs);
 548         }
 549         uint64_t t7 = mach_absolute_time();
 550
 551         // clear error strings
 552         (*context.setErrorStrings)(0, NULL, NULL, NULL);
 553
 554         fgTotalLoadLibrariesTime += t1 - t0;
 555         fgTotalRebaseTime += t3 - t2;
 556         fgTotalBindTime += t4 - t3;
 557         fgTotalWeakBindTime += t5 - t4;
 558         fgTotalDOF += t7 - t6;
 559
 560         // done with initial dylib loads
 561         fgNextPIEDylibAddress = 0;
 562 }
 563
 564
 565 void ImageLoader::printReferenceCounts()
 566 {
 567         dyld::log("      dlopen=%d for %s\n", fDlopenReferenceCount, getPath() );
 568 }
 569
 570
 571 bool ImageLoader::decrementDlopenReferenceCount()
 572 {
 573         if ( fDlopenReferenceCount == 0 )
 574                 return true;
 575         --fDlopenReferenceCount;
 576         return false;
 577 }
 578
 579
 580 // <rdar://problem/14412057> upward dylib initializers can be run too soon
 581 // To handle dangling dylibs which are upward linked but not downward, all upward linked dylibs
 582 // have their initialization postponed until after the recursion through downward dylibs
 583 // has completed.
 584 void ImageLoader::processInitializers(const LinkContext& context, mach_port_t thisThread,
 585                                                                          InitializerTimingList& timingInfo, ImageLoader::UninitedUpwards& images)
 586 {
 587         uint32_t maxImageCount = context.imageCount()+2;
 588         ImageLoader::UninitedUpwards upsBuffer[maxImageCount];
 589         ImageLoader::UninitedUpwards& ups = upsBuffer[0];
 590         ups.count = 0;
 591         // Calling recursive init on all images in images list, building a new list of
 592         // uninitialized upward dependencies.
 593         for (uintptr_t i=0; i < images.count; ++i) {
 594                 images.imagesAndPaths[i].first->recursiveInitialization(context, thisThread, images.imagesAndPaths[i].second, timingInfo, ups);
 595         }
 596         // If any upward dependencies remain, init them.
 597         if ( ups.count > 0 )
 598                 processInitializers(context, thisThread, timingInfo, ups);
 599 }
 600
 601
 602 void ImageLoader::runInitializers(const LinkContext& context, InitializerTimingList& timingInfo)
 603 {
 604         uint64_t t1 = mach_absolute_time();
 605         mach_port_t thisThread = mach_thread_self();
 606         ImageLoader::UninitedUpwards up;
 607         up.count = 1;
 608         up.imagesAndPaths[0] = { this, this->getPath() };
 609         processInitializers(context, thisThread, timingInfo, up);
 610         context.notifyBatch(dyld_image_state_initialized, false);
 611         mach_port_deallocate(mach_task_self(), thisThread);
 612         uint64_t t2 = mach_absolute_time();
 613         fgTotalInitTime += (t2 - t1);
 614 }
 615
 616
 617 void ImageLoader::bindAllLazyPointers(const LinkContext& context, bool recursive)
 618 {
 619         if ( ! fAllLazyPointersBound ) {
 620                 fAllLazyPointersBound = true;
 621
 622                 if ( recursive ) {
 623                         // bind lower level libraries first
 624                         for(unsigned int i=0; i < libraryCount(); ++i) {
 625                                 ImageLoader* dependentImage = libImage(i);
 626                                 if ( dependentImage != NULL )
 627                                         dependentImage->bindAllLazyPointers(context, recursive);
 628                         }
 629                 }
 630                 // bind lazies in this image
 631                 this->doBindJustLazies(context);
 632         }
 633 }
 634
 635
 636 bool ImageLoader::allDependentLibrariesAsWhenPreBound() const
 637 {
 638         return fAllLibraryChecksumsAndLoadAddressesMatch;
 639 }
 640
 641
 642 void ImageLoader::markedUsedRecursive(const std::vector<DynamicReference>& dynamicReferences)
 643 {
 644         // already visited here
 645         if ( fMarkedInUse )
 646                 return;
 647         fMarkedInUse = true;
 648
 649         // clear mark on all statically dependent dylibs
 650         for(unsigned int i=0; i < libraryCount(); ++i) {
 651                 ImageLoader* dependentImage = libImage(i);
 652                 if ( dependentImage != NULL ) {
 653                         dependentImage->markedUsedRecursive(dynamicReferences);
 654                 }
 655         }
 656
 657         // clear mark on all dynamically dependent dylibs
 658         for (std::vector<ImageLoader::DynamicReference>::const_iterator it=dynamicReferences.begin(); it != dynamicReferences.end(); ++it) {
 659                 if ( it->from == this )
 660                         it->to->markedUsedRecursive(dynamicReferences);
 661         }
 662
 663 }
 664
 665 unsigned int ImageLoader::recursiveUpdateDepth(unsigned int maxDepth)
 666 {
 667         // the purpose of this phase is to make the images sortable such that
 668         // in a sort list of images, every image that an image depends on
 669         // occurs in the list before it.
 670         if ( fDepth == 0 ) {
 671                 // break cycles
 672                 fDepth = maxDepth;
 673
 674                 // get depth of dependents
 675                 unsigned int minDependentDepth = maxDepth;
 676                 for(unsigned int i=0; i < libraryCount(); ++i) {
 677                         ImageLoader* dependentImage = libImage(i);
 678                         if ( (dependentImage != NULL) && !libIsUpward(i) ) {
 679                                 unsigned int d = dependentImage->recursiveUpdateDepth(maxDepth);
 680                                 if ( d < minDependentDepth )
 681                                         minDependentDepth = d;
 682                         }
 683                 }
 684
 685                 // make me less deep then all my dependents
 686                 fDepth = minDependentDepth - 1;
 687         }
 688
 689         return fDepth;
 690 }
 691
 692
 693 void ImageLoader::recursiveLoadLibraries(const LinkContext& context, bool preflightOnly, const RPathChain& loaderRPaths, const char* loadPath)
 694 {
 695         if ( fState < dyld_image_state_dependents_mapped ) {
 696                 // break cycles
 697                 fState = dyld_image_state_dependents_mapped;
 698
 699                 // get list of libraries this image needs
 700                 DependentLibraryInfo libraryInfos[fLibraryCount];
 701                 this->doGetDependentLibraries(libraryInfos);
 702
 703                 // get list of rpaths that this image adds
 704                 std::vector<const char*> rpathsFromThisImage;
 705                 this->getRPaths(context, rpathsFromThisImage);
 706                 const RPathChain thisRPaths(&loaderRPaths, &rpathsFromThisImage);
 707
 708                 // try to load each
 709                 bool canUsePrelinkingInfo = true;
 710                 for(unsigned int i=0; i < fLibraryCount; ++i){
 711                         ImageLoader* dependentLib;
 712                         bool depLibReExported = false;
 713                         DependentLibraryInfo& requiredLibInfo = libraryInfos[i];
 714                         if ( preflightOnly && context.inSharedCache(requiredLibInfo.name) ) {
 715                                 // <rdar://problem/5910137> dlopen_preflight() on image in shared cache leaves it loaded but not objc initialized
 716                                 // in preflight mode, don't even load dylib that are in the shared cache because they will never be unloaded
 717                                 setLibImage(i, NULL, false, false);
 718                                 continue;
 719                         }
 720                         try {
 721                                 unsigned cacheIndex;
 722                                 dependentLib = context.loadLibrary(requiredLibInfo.name, true, this->getPath(), &thisRPaths, cacheIndex);
 723                                 if ( dependentLib == this ) {
 724                                         // found circular reference, perhaps DYLD_LIBARY_PATH is causing this rdar://problem/3684168
 725                                         dependentLib = context.loadLibrary(requiredLibInfo.name, false, NULL, NULL, cacheIndex);
 726                                         if ( dependentLib != this )
 727                                                 dyld::warn("DYLD_ setting caused circular dependency in %s\n", this->getPath());
 728                                 }
 729                                 if ( fNeverUnload )
 730                                         dependentLib->setNeverUnload();
 731                                 if ( requiredLibInfo.upward ) {
 732                                 }
 733                                 else {
 734                                         dependentLib->fIsReferencedDownward = true;
 735                                 }
 736                                 LibraryInfo actualInfo = dependentLib->doGetLibraryInfo(requiredLibInfo.info);
 737                                 depLibReExported = requiredLibInfo.reExported;
 738                                 if ( ! depLibReExported ) {
 739                                         // for pre-10.5 binaries that did not use LC_REEXPORT_DYLIB
 740                                         depLibReExported = dependentLib->isSubframeworkOf(context, this) || this->hasSubLibrary(context, dependentLib);
 741                                 }
 742                                 // check found library version is compatible
 743                                 // <rdar://problem/89200806> 0xFFFFFFFF is wildcard that matches any version
 744                                 if ( (requiredLibInfo.info.minVersion != 0xFFFFFFFF) && (actualInfo.minVersion < requiredLibInfo.info.minVersion)
 745                                                 && ((dyld3::MachOFile*)(dependentLib->machHeader()))->enforceCompatVersion() ) {
 746                                         // record values for possible use by CrashReporter or Finder
 747                                         dyld::throwf("Incompatible library version: %s requires version %d.%d.%d or later, but %s provides version %d.%d.%d",
 748                                                         this->getShortName(), requiredLibInfo.info.minVersion >> 16, (requiredLibInfo.info.minVersion >> 8) & 0xff, requiredLibInfo.info.minVersion & 0xff,
 749                                                         dependentLib->getShortName(), actualInfo.minVersion >> 16, (actualInfo.minVersion >> 8) & 0xff, actualInfo.minVersion & 0xff);
 750                                 }
 751                                 // prebinding for this image disabled if any dependent library changed
 752                                 //if ( !depLibCheckSumsMatch )
 753                                 //      canUsePrelinkingInfo = false;
 754                                 // prebinding for this image disabled unless both this and dependent are in the shared cache
 755                                 if ( !dependentLib->inSharedCache() || !this->inSharedCache() )
 756                                         canUsePrelinkingInfo = false;
 757
 758                                 //if ( context.verbosePrebinding ) {
 759                                 //      if ( !requiredLib.checksumMatches )
 760                                 //              fprintf(stderr, "dyld: checksum mismatch, (%u v %u) for %s referencing %s\n",
 761                                 //                      requiredLibInfo.info.checksum, actualInfo.checksum, this->getPath(),    dependentLib->getPath());
 762                                 //      if ( dependentLib->getSlide() != 0 )
 763                                 //              fprintf(stderr, "dyld: dependent library slid for %s referencing %s\n", this->getPath(), dependentLib->getPath());
 764                                 //}
 765                         }
 766                         catch (const char* msg) {
 767                                 //if ( context.verbosePrebinding )
 768                                 //      fprintf(stderr, "dyld: exception during processing for %s referencing %s\n", this->getPath(), dependentLib->getPath());
 769                                 if ( requiredLibInfo.required ) {
 770                                         fState = dyld_image_state_mapped;
 771                                         // record values for possible use by CrashReporter or Finder
 772                                         if ( strstr(msg, "Incompatible library version") != NULL )
 773                                                 (*context.setErrorStrings)(DYLD_EXIT_REASON_DYLIB_WRONG_VERSION, this->getPath(), requiredLibInfo.name, NULL);
 774                                         else if ( strstr(msg, "architecture") != NULL )
 775                                                 (*context.setErrorStrings)(DYLD_EXIT_REASON_DYLIB_WRONG_ARCH, this->getPath(), requiredLibInfo.name, NULL);
 776                                         else if ( strstr(msg, "file system sandbox") != NULL )
 777                                                 (*context.setErrorStrings)(DYLD_EXIT_REASON_FILE_SYSTEM_SANDBOX, this->getPath(), requiredLibInfo.name, NULL);
 778                                         else if ( strstr(msg, "code signature") != NULL )
 779                                                 (*context.setErrorStrings)(DYLD_EXIT_REASON_CODE_SIGNATURE, this->getPath(), requiredLibInfo.name, NULL);
 780                                         else if ( strstr(msg, "malformed") != NULL )
 781                                                 (*context.setErrorStrings)(DYLD_EXIT_REASON_MALFORMED_MACHO, this->getPath(), requiredLibInfo.name, NULL);
 782                                         else
 783                                                 (*context.setErrorStrings)(DYLD_EXIT_REASON_DYLIB_MISSING, this->getPath(), requiredLibInfo.name, NULL);
 784                                         const char* newMsg = dyld::mkstringf("Library not loaded: %s\n  Referenced from: %s\n  Reason: %s", requiredLibInfo.name, this->getRealPath(), msg);
 785                                         free((void*)msg);       // our free() will do nothing if msg is a string literal
 786                                         throw newMsg;
 787                                 }
 788                                 free((void*)msg);       // our free() will do nothing if msg is a string literal
 789                                 // ok if weak library not found
 790                                 dependentLib = NULL;
 791                                 canUsePrelinkingInfo = false;  // this disables all prebinding, we may want to just slam import vectors for this lib to zero
 792                         }
 793                         setLibImage(i, dependentLib, depLibReExported, requiredLibInfo.upward);
 794                 }
 795                 fAllLibraryChecksumsAndLoadAddressesMatch = canUsePrelinkingInfo;
 796
 797                 // tell each to load its dependents
 798                 for(unsigned int i=0; i < libraryCount(); ++i) {
 799                         ImageLoader* dependentImage = libImage(i);
 800                         if ( dependentImage != NULL ) {
 801                                 dependentImage->recursiveLoadLibraries(context, preflightOnly, thisRPaths, libraryInfos[i].name);
 802                         }
 803                 }
 804
 805                 // do deep prebind check
 806                 if ( fAllLibraryChecksumsAndLoadAddressesMatch ) {
 807                         for(unsigned int i=0; i < libraryCount(); ++i){
 808                                 ImageLoader* dependentImage = libImage(i);
 809                                 if ( dependentImage != NULL ) {
 810                                         if ( !dependentImage->allDependentLibrariesAsWhenPreBound() )
 811                                                 fAllLibraryChecksumsAndLoadAddressesMatch = false;
 812                                 }
 813                         }
 814                 }
 815
 816                 // free rpaths (getRPaths() malloc'ed each string)
 817                 for(std::vector<const char*>::iterator it=rpathsFromThisImage.begin(); it != rpathsFromThisImage.end(); ++it) {
 818                         const char* str = *it;
 819                         free((void*)str);
 820                 }
 821
 822         }
 823 }
 824
 825
 826 void ImageLoader::recursiveRebaseWithAccounting(const LinkContext& context)
 827 {
 828         this->recursiveRebase(context);
 829         vmAccountingSetSuspended(context, false);
 830 }
 831
 832 void ImageLoader::recursiveRebase(const LinkContext& context)
 833 {
 834         if ( fState < dyld_image_state_rebased ) {
 835                 // break cycles
 836                 fState = dyld_image_state_rebased;
 837
 838                 try {
 839                         // rebase lower level libraries first
 840                         for(unsigned int i=0; i < libraryCount(); ++i) {
 841                                 ImageLoader* dependentImage = libImage(i);
 842                                 if ( dependentImage != NULL )
 843                                         dependentImage->recursiveRebase(context);
 844                         }
 845
 846                         // rebase this image
 847                         doRebase(context);
 848
 849                         // notify
 850                         context.notifySingle(dyld_image_state_rebased, this, NULL);
 851                 }
 852                 catch (const char* msg) {
 853                         // this image is not rebased
 854                         fState = dyld_image_state_dependents_mapped;
 855             CRSetCrashLogMessage2(NULL);
 856                         throw;
 857                 }
 858         }
 859 }
 860
 861 void ImageLoader::recursiveApplyInterposing(const LinkContext& context)
 862 {
 863         if ( ! fInterposed ) {
 864                 // break cycles
 865                 fInterposed = true;
 866
 867                 try {
 868                         // interpose lower level libraries first
 869                         for(unsigned int i=0; i < libraryCount(); ++i) {
 870                                 ImageLoader* dependentImage = libImage(i);
 871                                 if ( dependentImage != NULL )
 872                                         dependentImage->recursiveApplyInterposing(context);
 873                         }
 874
 875                         // interpose this image
 876                         doInterpose(context);
 877                 }
 878                 catch (const char* msg) {
 879                         // this image is not interposed
 880                         fInterposed = false;
 881                         throw;
 882                 }
 883         }
 884 }
 885
 886 void ImageLoader::recursiveMakeDataReadOnly(const LinkContext& context)
 887 {
 888         if ( ! fMadeReadOnly ) {
 889                 // break cycles
 890                 fMadeReadOnly = true;
 891
 892                 try {
 893                         // handle lower level libraries first
 894                         for(unsigned int i=0; i < libraryCount(); ++i) {
 895                                 ImageLoader* dependentImage = libImage(i);
 896                                 if ( dependentImage != NULL )
 897                                         dependentImage->recursiveMakeDataReadOnly(context);
 898                         }
 899
 900                         // if this image has __DATA_CONST, make that segment read-only
 901                         makeDataReadOnly();
 902                 }
 903                 catch (const char* msg) {
 904                         fMadeReadOnly = false;
 905                         throw;
 906                 }
 907         }
 908 }
 909
 910
 911 void ImageLoader::recursiveBindWithAccounting(const LinkContext& context, bool forceLazysBound, bool neverUnload)
 912 {
 913         this->recursiveBind(context, forceLazysBound, neverUnload);
 914         vmAccountingSetSuspended(context, false);
 915 }
 916
 917 void ImageLoader::recursiveBind(const LinkContext& context, bool forceLazysBound, bool neverUnload)
 918 {
 919         // Normally just non-lazy pointers are bound immediately.
 920         // The exceptions are:
 921         //   1) DYLD_BIND_AT_LAUNCH will cause lazy pointers to be bound immediately
 922         //   2) some API's (e.g. RTLD_NOW) can cause lazy pointers to be bound immediately
 923         if ( fState < dyld_image_state_bound ) {
 924                 // break cycles
 925                 fState = dyld_image_state_bound;
 926
 927                 try {
 928                         // bind lower level libraries first
 929                         for(unsigned int i=0; i < libraryCount(); ++i) {
 930                                 ImageLoader* dependentImage = libImage(i);
 931                                 if ( dependentImage != NULL )
 932                                         dependentImage->recursiveBind(context, forceLazysBound, neverUnload);
 933                         }
 934                         // bind this image
 935                         this->doBind(context, forceLazysBound);
 936                         // mark if lazys are also bound
 937                         if ( forceLazysBound || this->usablePrebinding(context) )
 938                                 fAllLazyPointersBound = true;
 939                         // mark as never-unload if requested
 940                         if ( neverUnload )
 941                                 this->setNeverUnload();
 942
 943                         context.notifySingle(dyld_image_state_bound, this, NULL);
 944                 }
 945                 catch (const char* msg) {
 946                         // restore state
 947                         fState = dyld_image_state_rebased;
 948             CRSetCrashLogMessage2(NULL);
 949                         throw;
 950                 }
 951         }
 952 }
 953
 954
 955
 956 // These are mangled symbols for all the variants of operator new and delete
 957 // which a main executable can define (non-weak) and override the
 958 // weak-def implementation in the OS.
 959 static const char* const sTreatAsWeak[] = {
 960     "__Znwm", "__ZnwmRKSt9nothrow_t",
 961     "__Znam", "__ZnamRKSt9nothrow_t",
 962     "__ZdlPv", "__ZdlPvRKSt9nothrow_t", "__ZdlPvm",
 963     "__ZdaPv", "__ZdaPvRKSt9nothrow_t", "__ZdaPvm",
 964     "__ZnwmSt11align_val_t", "__ZnwmSt11align_val_tRKSt9nothrow_t",
 965     "__ZnamSt11align_val_t", "__ZnamSt11align_val_tRKSt9nothrow_t",
 966     "__ZdlPvSt11align_val_t", "__ZdlPvSt11align_val_tRKSt9nothrow_t", "__ZdlPvmSt11align_val_t",
 967     "__ZdaPvSt11align_val_t", "__ZdaPvSt11align_val_tRKSt9nothrow_t", "__ZdaPvmSt11align_val_t"
 968 };
 969
 970 size_t ImageLoader::HashCString::hash(const char* v) {
 971     // FIXME: Use hash<string_view> when it has the correct visibility markup
 972     return std::hash<std::string_view>{}(v);
 973 }
 974
 975 bool ImageLoader::EqualCString::equal(const char* s1, const char* s2) {
 976     return strcmp(s1, s2) == 0;
 977 }
 978
 979 void ImageLoader::weakBind(const LinkContext& context)
 980 {
 981
 982         if (!context.useNewWeakBind) {
 983                 weakBindOld(context);
 984                 return;
 985         }
 986
 987         if ( context.verboseWeakBind )
 988                 dyld::log("dyld: weak bind start:\n");
 989         uint64_t t1 = mach_absolute_time();
 990
 991         // get set of ImageLoaders that participate in coalecsing
 992         ImageLoader* imagesNeedingCoalescing[fgImagesRequiringCoalescing];
 993         unsigned imageIndexes[fgImagesRequiringCoalescing];
 994         int count = context.getCoalescedImages(imagesNeedingCoalescing, imageIndexes);
 995
 996         // count how many have not already had weakbinding done
 997         int countNotYetWeakBound = 0;
 998         int countOfImagesWithWeakDefinitionsNotInSharedCache = 0;
 999         for(int i=0; i < count; ++i) {
1000                 if ( ! imagesNeedingCoalescing[i]->weakSymbolsBound(imageIndexes[i]) )
1001                         ++countNotYetWeakBound;
1002                 if ( ! imagesNeedingCoalescing[i]->inSharedCache() )
1003                         ++countOfImagesWithWeakDefinitionsNotInSharedCache;
1004         }
1005
1006         // don't need to do any coalescing if only one image has overrides, or all have already been done
1007         if ( (countOfImagesWithWeakDefinitionsNotInSharedCache > 0) && (countNotYetWeakBound > 0) ) {
1008                 if (!context.weakDefMapInitialized) {
1009                         // Initialize the weak def map as the link context doesn't run static initializers
1010                         new (&context.weakDefMap) dyld3::Map<const char*, std::pair<const ImageLoader*, uintptr_t>, ImageLoader::HashCString, ImageLoader::EqualCString>();
1011                         context.weakDefMapInitialized = true;
1012                 }
1013 #if __MAC_OS_X_VERSION_MIN_REQUIRED
1014           // only do alternate algorithm for dlopen(). Use traditional algorithm for launch
1015           if ( !context.linkingMainExecutable ) {
1016                   // Don't take the memory hit of weak defs on the launch path until we hit a dlopen with more weak symbols to bind
1017                   if (!context.weakDefMapProcessedLaunchDefs) {
1018                           context.weakDefMapProcessedLaunchDefs = true;
1019
1020                           // Walk the nlist for all binaries from launch and fill in the map with any other weak defs
1021                           for (int i=0; i < count; ++i) {
1022                                   const ImageLoader* image = imagesNeedingCoalescing[i];
1023                                   // skip images without defs.  We've processed launch time refs already
1024                                   if ( !image->hasCoalescedExports() )
1025                                           continue;
1026                                   // Only process binaries which have had their weak symbols bound, ie, not the new ones we are processing now
1027                                   // from this dlopen
1028                                   if ( !image->weakSymbolsBound(imageIndexes[i]) )
1029                                           continue;
1030
1031                                   Diagnostics diag;
1032                                   const dyld3::MachOAnalyzer* ma = (const dyld3::MachOAnalyzer*)image->machHeader();
1033                                   ma->forEachWeakDef(diag, ^(const char *symbolName, uintptr_t imageOffset, bool isFromExportTrie) {
1034                                           uintptr_t targetAddr = (uintptr_t)ma + imageOffset;
1035                                           if ( isFromExportTrie ) {
1036                                                   // Avoid duplicating the string if we already have the symbol name
1037                                                   if ( context.weakDefMap.find(symbolName) != context.weakDefMap.end() )
1038                                                           return;
1039                                                   symbolName = strdup(symbolName);
1040                                           }
1041                                           context.weakDefMap.insert({ symbolName, { image, targetAddr } });
1042                                   });
1043                           }
1044                   }
1045
1046                   // Walk the nlist for all binaries in dlopen and fill in the map with any other weak defs
1047                   for (int i=0; i < count; ++i) {
1048                           const ImageLoader* image = imagesNeedingCoalescing[i];
1049                           if ( image->weakSymbolsBound(imageIndexes[i]) )
1050                                   continue;
1051                           // skip images without defs.  We'll process refs later
1052                           if ( !image->hasCoalescedExports() )
1053                                   continue;
1054                           Diagnostics diag;
1055                           const dyld3::MachOAnalyzer* ma = (const dyld3::MachOAnalyzer*)image->machHeader();
1056                           ma->forEachWeakDef(diag, ^(const char *symbolName, uintptr_t imageOffset, bool isFromExportTrie) {
1057                                   uintptr_t targetAddr = (uintptr_t)ma + imageOffset;
1058                                   if ( isFromExportTrie ) {
1059                                           // Avoid duplicating the string if we already have the symbol name
1060                                           if ( context.weakDefMap.find(symbolName) != context.weakDefMap.end() )
1061                                                   return;
1062                                           symbolName = strdup(symbolName);
1063                                   }
1064                                   context.weakDefMap.insert({ symbolName, { image, targetAddr } });
1065                           });
1066                   }
1067                 // for all images that need weak binding
1068                 for (int i=0; i < count; ++i) {
1069                         ImageLoader* imageBeingFixedUp = imagesNeedingCoalescing[i];
1070                         if ( imageBeingFixedUp->weakSymbolsBound(imageIndexes[i]) )
1071                                 continue; // weak binding already completed
1072                         bool imageBeingFixedUpInCache = imageBeingFixedUp->inSharedCache();
1073
1074                         if ( context.verboseWeakBind )
1075                                 dyld::log("dyld: checking for weak symbols in %s\n", imageBeingFixedUp->getPath());
1076                         // for all symbols that need weak binding in this image
1077                         ImageLoader::CoalIterator coalIterator;
1078                         imageBeingFixedUp->initializeCoalIterator(coalIterator, i, imageIndexes[i]);
1079                         while ( !imageBeingFixedUp->incrementCoalIterator(coalIterator) ) {
1080                                 const char*         nameToCoalesce = coalIterator.symbolName;
1081                                 uintptr_t           targetAddr     = 0;
1082                                 const ImageLoader*  targetImage;
1083                                 // Seatch the map for a previous definition to use
1084                                 auto weakDefIt = context.weakDefMap.find(nameToCoalesce);
1085                                 if ( (weakDefIt != context.weakDefMap.end()) && (weakDefIt->second.first != nullptr) ) {
1086                                         // Found a previous defition
1087                                         targetImage = weakDefIt->second.first;
1088                                         targetAddr = weakDefIt->second.second;
1089                                 } else {
1090                                         // scan all images looking for definition to use
1091                                         for (int j=0; j < count; ++j) {
1092                                                 const ImageLoader* anImage = imagesNeedingCoalescing[j];
1093                                                 bool anImageInCache = anImage->inSharedCache();
1094                                                 // <rdar://problem/47986398> Don't look at images in dyld cache because cache is
1095                                                 //  already coalesced.  Only images outside cache can potentially override something in cache.
1096                                                 if ( anImageInCache && imageBeingFixedUpInCache )
1097                                                         continue;
1098
1099                                                 //dyld::log("looking for %s in %s\n", nameToCoalesce, anImage->getPath());
1100                                                 const ImageLoader* foundIn;
1101                                                 const Symbol* sym = anImage->findExportedSymbol(nameToCoalesce, false, &foundIn);
1102                                                 if ( sym != NULL ) {
1103                                                         targetAddr = foundIn->getExportedSymbolAddress(sym, context);
1104                                                         targetImage = foundIn;
1105                                                         if ( context.verboseWeakBind )
1106                                                                 dyld::log("dyld:   found weak %s at 0x%lX in %s\n", nameToCoalesce, targetAddr, foundIn->getPath());
1107                                                         break;
1108                                                 }
1109                                         }
1110                                 }
1111                                 if ( (targetAddr != 0) && (coalIterator.image != targetImage) ) {
1112                                         coalIterator.image->updateUsesCoalIterator(coalIterator, targetAddr, (ImageLoader*)targetImage, 0, context);
1113                                         if (weakDefIt == context.weakDefMap.end()) {
1114                                                 if (targetImage->neverUnload()) {
1115                                                         // Add never unload defs to the map for next time
1116                                                         context.weakDefMap.insert({ nameToCoalesce, { targetImage, targetAddr } });
1117                                                         if ( context.verboseWeakBind ) {
1118                                                                 dyld::log("dyld: weak binding adding %s to map\n", nameToCoalesce);
1119                                                         }
1120                                                 } else {
1121                                                         // Add a placeholder for unloadable symbols which makes us fall back to the regular search
1122                                                         context.weakDefMap.insert({ nameToCoalesce, { targetImage, targetAddr } });
1123                                                         if ( context.verboseWeakBind ) {
1124                                                                 dyld::log("dyld: weak binding adding unloadable placeholder %s to map\n", nameToCoalesce);
1125                                                         }
1126                                                 }
1127                                         }
1128                                         if ( context.verboseWeakBind )
1129                                                 dyld::log("dyld:     adjusting uses of %s in %s to use definition from %s\n", nameToCoalesce, coalIterator.image->getPath(), targetImage->getPath());
1130                                 }
1131                         }
1132                         imageBeingFixedUp->setWeakSymbolsBound(imageIndexes[i]);
1133                 }
1134           }
1135           else
1136 #endif // __MAC_OS_X_VERSION_MIN_REQUIRED
1137           {
1138                 // make symbol iterators for each
1139                 ImageLoader::CoalIterator iterators[count];
1140                 ImageLoader::CoalIterator* sortedIts[count];
1141                 for(int i=0; i < count; ++i) {
1142                         imagesNeedingCoalescing[i]->initializeCoalIterator(iterators[i], i, imageIndexes[i]);
1143                         sortedIts[i] = &iterators[i];
1144                         if ( context.verboseWeakBind )
1145                                 dyld::log("dyld: weak bind load order %d/%d for %s\n", i, count, imagesNeedingCoalescing[i]->getIndexedPath(imageIndexes[i]));
1146                 }
1147
1148                 // walk all symbols keeping iterators in sync by
1149                 // only ever incrementing the iterator with the lowest symbol
1150                 int doneCount = 0;
1151                 while ( doneCount != count ) {
1152                         //for(int i=0; i < count; ++i)
1153                         //      dyld::log("sym[%d]=%s ", sortedIts[i]->loadOrder, sortedIts[i]->symbolName);
1154                         //dyld::log("\n");
1155                         // increment iterator with lowest symbol
1156                         if ( sortedIts[0]->image->incrementCoalIterator(*sortedIts[0]) )
1157                                 ++doneCount;
1158                         // re-sort iterators
1159                         for(int i=1; i < count; ++i) {
1160                                 int result = strcmp(sortedIts[i-1]->symbolName, sortedIts[i]->symbolName);
1161                                 if ( result == 0 )
1162                                         sortedIts[i-1]->symbolMatches = true;
1163                                 if ( result > 0 ) {
1164                                         // new one is bigger then next, so swap
1165                                         ImageLoader::CoalIterator* temp = sortedIts[i-1];
1166                                         sortedIts[i-1] = sortedIts[i];
1167                                         sortedIts[i] = temp;
1168                                 }
1169                                 if ( result < 0 )
1170                                         break;
1171                         }
1172                         // process all matching symbols just before incrementing the lowest one that matches
1173                         if ( sortedIts[0]->symbolMatches && !sortedIts[0]->done ) {
1174                                 const char* nameToCoalesce = sortedIts[0]->symbolName;
1175                                 // pick first symbol in load order (and non-weak overrides weak)
1176                                 uintptr_t targetAddr = 0;
1177                                 ImageLoader* targetImage = NULL;
1178                                 unsigned targetImageIndex = 0;
1179                                 for(int i=0; i < count; ++i) {
1180                                         if ( strcmp(iterators[i].symbolName, nameToCoalesce) == 0 ) {
1181                                                 if ( context.verboseWeakBind )
1182                                                         dyld::log("dyld: weak bind, found %s weak=%d in %s \n", nameToCoalesce, iterators[i].weakSymbol, iterators[i].image->getIndexedPath((unsigned)iterators[i].imageIndex));
1183                                                 if ( iterators[i].weakSymbol ) {
1184                                                         if ( targetAddr == 0 ) {
1185                                                                 targetAddr = iterators[i].image->getAddressCoalIterator(iterators[i], context);
1186                                                                 if ( targetAddr != 0 ) {
1187                                                                         targetImage = iterators[i].image;
1188                                                                         targetImageIndex = (unsigned)iterators[i].imageIndex;
1189                                                                 }
1190                                                         }
1191                                                 }
1192                                                 else {
1193                                                         targetAddr = iterators[i].image->getAddressCoalIterator(iterators[i], context);
1194                                                         if ( targetAddr != 0 ) {
1195                                                                 targetImage = iterators[i].image;
1196                                                                 targetImageIndex = (unsigned)iterators[i].imageIndex;
1197                                                                 // strong implementation found, stop searching
1198                                                                 break;
1199                                                         }
1200                                                 }
1201                                         }
1202                                 }
1203                                 // tell each to bind to this symbol (unless already bound)
1204                                 if ( targetAddr != 0 ) {
1205                                         if ( context.verboseWeakBind ) {
1206                                                 dyld::log("dyld: weak binding all uses of %s to copy from %s\n",
1207                                                                         nameToCoalesce, targetImage->getIndexedShortName(targetImageIndex));
1208                                         }
1209                                         for(int i=0; i < count; ++i) {
1210                                                 if ( strcmp(iterators[i].symbolName, nameToCoalesce) == 0 ) {
1211                                                         if ( context.verboseWeakBind ) {
1212                                                                 dyld::log("dyld: weak bind, setting all uses of %s in %s to 0x%lX from %s\n",
1213                                                                                         nameToCoalesce, iterators[i].image->getIndexedShortName((unsigned)iterators[i].imageIndex),
1214                                                                                         targetAddr, targetImage->getIndexedShortName(targetImageIndex));
1215                                                         }
1216                                                         if ( ! iterators[i].image->weakSymbolsBound(imageIndexes[i]) )
1217                                                                 iterators[i].image->updateUsesCoalIterator(iterators[i], targetAddr, targetImage, targetImageIndex, context);
1218                                                         iterators[i].symbolMatches = false;
1219                                                 }
1220                                         }
1221                                         if (targetImage->neverUnload()) {
1222                                                 // Add never unload defs to the map for next time
1223                                                 context.weakDefMap.insert({ nameToCoalesce, { targetImage, targetAddr } });
1224                                                 if ( context.verboseWeakBind ) {
1225                                                         dyld::log("dyld: weak binding adding %s to map\n",
1226                                                                                 nameToCoalesce);
1227                                                 }
1228                                         }
1229                                 }
1230
1231                         }
1232                 }
1233
1234                 for (int i=0; i < count; ++i) {
1235                         if ( imagesNeedingCoalescing[i]->weakSymbolsBound(imageIndexes[i]) )
1236                                 continue;       // skip images already processed
1237
1238                         if ( imagesNeedingCoalescing[i]->usesChainedFixups() ) {
1239                                 // during binding of references to weak-def symbols, the dyld cache was patched
1240                                 // but if main executable has non-weak override of operator new or delete it needs is handled here
1241                                 for (const char* weakSymbolName : sTreatAsWeak) {
1242                                         const ImageLoader* dummy;
1243                                         imagesNeedingCoalescing[i]->resolveWeak(context, weakSymbolName, true, false, &dummy);
1244                                 }
1245                         }
1246 #if __arm64e__
1247                         else {
1248                                 // support traditional arm64 app on an arm64e device
1249                                 // look for weak def symbols in this image which may override the cache
1250                                 ImageLoader::CoalIterator coaler;
1251                                 imagesNeedingCoalescing[i]->initializeCoalIterator(coaler, i, 0);
1252                                 imagesNeedingCoalescing[i]->incrementCoalIterator(coaler);
1253                                 while ( !coaler.done ) {
1254                                         const ImageLoader* dummy;
1255                                         // a side effect of resolveWeak() is to patch cache
1256                                         imagesNeedingCoalescing[i]->resolveWeak(context, coaler.symbolName, true, false, &dummy);
1257                                         imagesNeedingCoalescing[i]->incrementCoalIterator(coaler);
1258                                 }
1259                         }
1260 #endif
1261                 }
1262
1263                 // mark all as having all weak symbols bound
1264                 for(int i=0; i < count; ++i) {
1265                         imagesNeedingCoalescing[i]->setWeakSymbolsBound(imageIndexes[i]);
1266                 }
1267           }
1268         }
1269
1270         uint64_t t2 = mach_absolute_time();
1271         fgTotalWeakBindTime += t2  - t1;
1272
1273         if ( context.verboseWeakBind )
1274                 dyld::log("dyld: weak bind end\n");
1275 }
1276
1277
1278 void ImageLoader::weakBindOld(const LinkContext& context)
1279 {
1280         if ( context.verboseWeakBind )
1281                 dyld::log("dyld: weak bind start:\n");
1282         uint64_t t1 = mach_absolute_time();
1283         // get set of ImageLoaders that participate in coalecsing
1284         ImageLoader* imagesNeedingCoalescing[fgImagesRequiringCoalescing];
1285         unsigned imageIndexes[fgImagesRequiringCoalescing];
1286         int count = context.getCoalescedImages(imagesNeedingCoalescing, imageIndexes);
1287
1288         // count how many have not already had weakbinding done
1289         int countNotYetWeakBound = 0;
1290         int countOfImagesWithWeakDefinitionsNotInSharedCache = 0;
1291         for(int i=0; i < count; ++i) {
1292                 if ( ! imagesNeedingCoalescing[i]->weakSymbolsBound(imageIndexes[i]) )
1293                         ++countNotYetWeakBound;
1294                 if ( ! imagesNeedingCoalescing[i]->inSharedCache() )
1295                         ++countOfImagesWithWeakDefinitionsNotInSharedCache;
1296         }
1297
1298         // don't need to do any coalescing if only one image has overrides, or all have already been done
1299         if ( (countOfImagesWithWeakDefinitionsNotInSharedCache > 0) && (countNotYetWeakBound > 0) ) {
1300 #if __MAC_OS_X_VERSION_MIN_REQUIRED
1301           // only do alternate algorithm for dlopen(). Use traditional algorithm for launch
1302           if ( !context.linkingMainExecutable ) {
1303                 // for all images that need weak binding
1304                 for (int i=0; i < count; ++i) {
1305                         ImageLoader* imageBeingFixedUp = imagesNeedingCoalescing[i];
1306                         if ( imageBeingFixedUp->weakSymbolsBound(imageIndexes[i]) )
1307                                 continue; // weak binding already completed
1308                         bool imageBeingFixedUpInCache = imageBeingFixedUp->inSharedCache();
1309
1310                         if ( context.verboseWeakBind )
1311                                 dyld::log("dyld: checking for weak symbols in %s\n", imageBeingFixedUp->getPath());
1312                         // for all symbols that need weak binding in this image
1313                         ImageLoader::CoalIterator coalIterator;
1314                         imageBeingFixedUp->initializeCoalIterator(coalIterator, i, imageIndexes[i]);
1315                         while ( !imageBeingFixedUp->incrementCoalIterator(coalIterator) ) {
1316                                 const char*         nameToCoalesce = coalIterator.symbolName;
1317                                 uintptr_t           targetAddr     = 0;
1318                                 const ImageLoader*  targetImage;
1319                                 // scan all images looking for definition to use
1320                                 for (int j=0; j < count; ++j) {
1321                                         const ImageLoader* anImage = imagesNeedingCoalescing[j];
1322                                         bool anImageInCache = anImage->inSharedCache();
1323                                         // <rdar://problem/47986398> Don't look at images in dyld cache because cache is
1324                                         //  already coalesced.  Only images outside cache can potentially override something in cache.
1325                                         if ( anImageInCache && imageBeingFixedUpInCache )
1326                                                 continue;
1327
1328                                         //dyld::log("looking for %s in %s\n", nameToCoalesce, anImage->getPath());
1329                                         const ImageLoader* foundIn;
1330                                         const Symbol* sym = anImage->findExportedSymbol(nameToCoalesce, false, &foundIn);
1331                                         if ( sym != NULL ) {
1332                                                 if ( (foundIn->getExportedSymbolInfo(sym) & ImageLoader::kWeakDefinition) == 0 ) {
1333                                                         // found non-weak def, use it and stop looking
1334                                                         targetAddr = foundIn->getExportedSymbolAddress(sym, context);
1335                                                         targetImage = foundIn;
1336                                                         if ( context.verboseWeakBind )
1337                                                                 dyld::log("dyld:   found strong %s at 0x%lX in %s\n", nameToCoalesce, targetAddr, foundIn->getPath());
1338                                                         break;
1339                                                 }
1340                                                 else {
1341                                                         // found weak-def, only use if no weak found yet
1342                                                         if ( targetAddr == 0 ) {
1343                                                                 targetAddr = foundIn->getExportedSymbolAddress(sym, context);
1344                                                                 targetImage = foundIn;
1345                                                                 if ( context.verboseWeakBind )
1346                                                                         dyld::log("dyld:   found weak %s at 0x%lX in %s\n", nameToCoalesce, targetAddr, foundIn->getPath());
1347                                                         }
1348                                                 }
1349                                         }
1350                                 }
1351                                 if ( (targetAddr != 0) && (coalIterator.image != targetImage) ) {
1352                                         coalIterator.image->updateUsesCoalIterator(coalIterator, targetAddr, (ImageLoader*)targetImage, 0, context);
1353                                         if ( context.verboseWeakBind )
1354                                                 dyld::log("dyld:     adjusting uses of %s in %s to use definition from %s\n", nameToCoalesce, coalIterator.image->getPath(), targetImage->getPath());
1355                                 }
1356                         }
1357                         imageBeingFixedUp->setWeakSymbolsBound(imageIndexes[i]);
1358                 }
1359           }
1360           else
1361 #endif // __MAC_OS_X_VERSION_MIN_REQUIRED
1362           {
1363                 // make symbol iterators for each
1364                 ImageLoader::CoalIterator iterators[count];
1365                 ImageLoader::CoalIterator* sortedIts[count];
1366                 for(int i=0; i < count; ++i) {
1367                         imagesNeedingCoalescing[i]->initializeCoalIterator(iterators[i], i, imageIndexes[i]);
1368                         sortedIts[i] = &iterators[i];
1369                         if ( context.verboseWeakBind )
1370                                 dyld::log("dyld: weak bind load order %d/%d for %s\n", i, count, imagesNeedingCoalescing[i]->getIndexedPath(imageIndexes[i]));
1371                 }
1372
1373                 // walk all symbols keeping iterators in sync by
1374                 // only ever incrementing the iterator with the lowest symbol
1375                 int doneCount = 0;
1376                 while ( doneCount != count ) {
1377                         //for(int i=0; i < count; ++i)
1378                         //      dyld::log("sym[%d]=%s ", sortedIts[i]->loadOrder, sortedIts[i]->symbolName);
1379                         //dyld::log("\n");
1380                         // increment iterator with lowest symbol
1381                         if ( sortedIts[0]->image->incrementCoalIterator(*sortedIts[0]) )
1382                                 ++doneCount;
1383                         // re-sort iterators
1384                         for(int i=1; i < count; ++i) {
1385                                 int result = strcmp(sortedIts[i-1]->symbolName, sortedIts[i]->symbolName);
1386                                 if ( result == 0 )
1387                                         sortedIts[i-1]->symbolMatches = true;
1388                                 if ( result > 0 ) {
1389                                         // new one is bigger then next, so swap
1390                                         ImageLoader::CoalIterator* temp = sortedIts[i-1];
1391                                         sortedIts[i-1] = sortedIts[i];
1392                                         sortedIts[i] = temp;
1393                                 }
1394                                 if ( result < 0 )
1395                                         break;
1396                         }
1397                         // process all matching symbols just before incrementing the lowest one that matches
1398                         if ( sortedIts[0]->symbolMatches && !sortedIts[0]->done ) {
1399                                 const char* nameToCoalesce = sortedIts[0]->symbolName;
1400                                 // pick first symbol in load order (and non-weak overrides weak)
1401                                 uintptr_t targetAddr = 0;
1402                                 ImageLoader* targetImage = NULL;
1403                                 unsigned targetImageIndex = 0;
1404                                 for(int i=0; i < count; ++i) {
1405                                         if ( strcmp(iterators[i].symbolName, nameToCoalesce) == 0 ) {
1406                                                 if ( context.verboseWeakBind )
1407                                                         dyld::log("dyld: weak bind, found %s weak=%d in %s \n", nameToCoalesce, iterators[i].weakSymbol, iterators[i].image->getIndexedPath((unsigned)iterators[i].imageIndex));
1408                                                 if ( iterators[i].weakSymbol ) {
1409                                                         if ( targetAddr == 0 ) {
1410                                                                 targetAddr = iterators[i].image->getAddressCoalIterator(iterators[i], context);
1411                                                                 if ( targetAddr != 0 ) {
1412                                                                         targetImage = iterators[i].image;
1413                                                                         targetImageIndex = (unsigned)iterators[i].imageIndex;
1414                                                                 }
1415                                                         }
1416                                                 }
1417                                                 else {
1418                                                         targetAddr = iterators[i].image->getAddressCoalIterator(iterators[i], context);
1419                                                         if ( targetAddr != 0 ) {
1420                                                                 targetImage = iterators[i].image;
1421                                                                 targetImageIndex = (unsigned)iterators[i].imageIndex;
1422                                                                 // strong implementation found, stop searching
1423                                                                 break;
1424                                                         }
1425                                                 }
1426                                         }
1427                                 }
1428                                 // tell each to bind to this symbol (unless already bound)
1429                                 if ( targetAddr != 0 ) {
1430                                         if ( context.verboseWeakBind ) {
1431                                                 dyld::log("dyld: weak binding all uses of %s to copy from %s\n",
1432                                                                         nameToCoalesce, targetImage->getIndexedShortName(targetImageIndex));
1433                                         }
1434                                         for(int i=0; i < count; ++i) {
1435                                                 if ( strcmp(iterators[i].symbolName, nameToCoalesce) == 0 ) {
1436                                                         if ( context.verboseWeakBind ) {
1437                                                                 dyld::log("dyld: weak bind, setting all uses of %s in %s to 0x%lX from %s\n",
1438                                                                                         nameToCoalesce, iterators[i].image->getIndexedShortName((unsigned)iterators[i].imageIndex),
1439                                                                                         targetAddr, targetImage->getIndexedShortName(targetImageIndex));
1440                                                         }
1441                                                         if ( ! iterators[i].image->weakSymbolsBound(imageIndexes[i]) )
1442                                                                 iterators[i].image->updateUsesCoalIterator(iterators[i], targetAddr, targetImage, targetImageIndex, context);
1443                                                         iterators[i].symbolMatches = false;
1444                                                 }
1445                                         }
1446                                 }
1447
1448                         }
1449                 }
1450
1451                 for (int i=0; i < count; ++i) {
1452                         if ( imagesNeedingCoalescing[i]->weakSymbolsBound(imageIndexes[i]) )
1453                                 continue;       // skip images already processed
1454
1455                         if ( imagesNeedingCoalescing[i]->usesChainedFixups() ) {
1456                                 // during binding of references to weak-def symbols, the dyld cache was patched
1457                                 // but if main executable has non-weak override of operator new or delete it needs is handled here
1458                                 for (const char* weakSymbolName : sTreatAsWeak) {
1459                                         const ImageLoader* dummy;
1460                                         imagesNeedingCoalescing[i]->resolveWeak(context, weakSymbolName, true, false, &dummy);
1461                                 }
1462                         }
1463 #if __arm64e__
1464                         else {
1465                                 // support traditional arm64 app on an arm64e device
1466                                 // look for weak def symbols in this image which may override the cache
1467                                 ImageLoader::CoalIterator coaler;
1468                                 imagesNeedingCoalescing[i]->initializeCoalIterator(coaler, i, 0);
1469                                 imagesNeedingCoalescing[i]->incrementCoalIterator(coaler);
1470                                 while ( !coaler.done ) {
1471                                         const ImageLoader* dummy;
1472                                         // a side effect of resolveWeak() is to patch cache
1473                                         imagesNeedingCoalescing[i]->resolveWeak(context, coaler.symbolName, true, false, &dummy);
1474                                         imagesNeedingCoalescing[i]->incrementCoalIterator(coaler);
1475                                 }
1476                         }
1477 #endif
1478                 }
1479
1480                 // mark all as having all weak symbols bound
1481                 for(int i=0; i < count; ++i) {
1482                         imagesNeedingCoalescing[i]->setWeakSymbolsBound(imageIndexes[i]);
1483                 }
1484           }
1485         }
1486
1487         uint64_t t2 = mach_absolute_time();
1488         fgTotalWeakBindTime += t2  - t1;
1489
1490         if ( context.verboseWeakBind )
1491                 dyld::log("dyld: weak bind end\n");
1492 }
1493
1494
1495
1496 void ImageLoader::recursiveGetDOFSections(const LinkContext& context, std::vector<DOFInfo>& dofs)
1497 {
1498         if ( ! fRegisteredDOF ) {
1499                 // break cycles
1500                 fRegisteredDOF = true;
1501
1502                 // gather lower level libraries first
1503                 for(unsigned int i=0; i < libraryCount(); ++i) {
1504                         ImageLoader* dependentImage = libImage(i);
1505                         if ( dependentImage != NULL )
1506                                 dependentImage->recursiveGetDOFSections(context, dofs);
1507                 }
1508                 this->doGetDOFSections(context, dofs);
1509         }
1510 }
1511
1512 void ImageLoader::setNeverUnloadRecursive() {
1513         if ( ! fNeverUnload ) {
1514                 // break cycles
1515                 fNeverUnload = true;
1516
1517                 // gather lower level libraries first
1518                 for(unsigned int i=0; i < libraryCount(); ++i) {
1519                         ImageLoader* dependentImage = libImage(i);
1520                         if ( dependentImage != NULL )
1521                                 dependentImage->setNeverUnloadRecursive();
1522                 }
1523         }
1524 }
1525
1526 void ImageLoader::recursiveSpinLock(recursive_lock& rlock)
1527 {
1528         // try to set image's ivar fInitializerRecursiveLock to point to this lock_info
1529         // keep trying until success (spin)
1530 #pragma clang diagnostic push
1531 #pragma clang diagnostic ignored "-Wdeprecated-declarations"
1532         while ( ! OSAtomicCompareAndSwapPtrBarrier(NULL, &rlock, (void**)&fInitializerRecursiveLock) ) {
1533                 // if fInitializerRecursiveLock already points to a different lock_info, if it is for
1534                 // the same thread we are on, the increment the lock count, otherwise continue to spin
1535                 if ( (fInitializerRecursiveLock != NULL) && (fInitializerRecursiveLock->thread == rlock.thread) )
1536                         break;
1537         }
1538 #pragma clang diagnostic pop
1539         ++(fInitializerRecursiveLock->count);
1540 }
1541
1542 void ImageLoader::recursiveSpinUnLock()
1543 {
1544         if ( --(fInitializerRecursiveLock->count) == 0 )
1545                 fInitializerRecursiveLock = NULL;
1546 }
1547
1548 void ImageLoader::InitializerTimingList::addTime(const char* name, uint64_t time)
1549 {
1550         for (int i=0; i < count; ++i) {
1551                 if ( strcmp(images[i].shortName, name) == 0 ) {
1552                         images[i].initTime += time;
1553                         return;
1554                 }
1555         }
1556         images[count].initTime = time;
1557         images[count].shortName = name;
1558         ++count;
1559 }
1560
1561 void ImageLoader::recursiveInitialization(const LinkContext& context, mach_port_t this_thread, const char* pathToInitialize,
1562                                                                                   InitializerTimingList& timingInfo, UninitedUpwards& uninitUps)
1563 {
1564         recursive_lock lock_info(this_thread);
1565         recursiveSpinLock(lock_info);
1566
1567         if ( fState < dyld_image_state_dependents_initialized-1 ) {
1568                 uint8_t oldState = fState;
1569                 // break cycles
1570                 fState = dyld_image_state_dependents_initialized-1;
1571                 try {
1572                         // initialize lower level libraries first
1573                         for(unsigned int i=0; i < libraryCount(); ++i) {
1574                                 ImageLoader* dependentImage = libImage(i);
1575                                 if ( dependentImage != NULL ) {
1576                                         // don't try to initialize stuff "above" me yet
1577                                         if ( libIsUpward(i) ) {
1578                                                 uninitUps.imagesAndPaths[uninitUps.count] = { dependentImage, libPath(i) };
1579                                                 uninitUps.count++;
1580                                         }
1581                                         else if ( dependentImage->fDepth >= fDepth ) {
1582                                                 dependentImage->recursiveInitialization(context, this_thread, libPath(i), timingInfo, uninitUps);
1583                                         }
1584                 }
1585                         }
1586
1587                         // record termination order
1588                         if ( this->needsTermination() )
1589                                 context.terminationRecorder(this);
1590
1591                         // let objc know we are about to initialize this image
1592                         uint64_t t1 = mach_absolute_time();
1593                         fState = dyld_image_state_dependents_initialized;
1594                         oldState = fState;
1595                         context.notifySingle(dyld_image_state_dependents_initialized, this, &timingInfo);
1596
1597                         // initialize this image
1598                         bool hasInitializers = this->doInitialization(context);
1599
1600                         // let anyone know we finished initializing this image
1601                         fState = dyld_image_state_initialized;
1602                         oldState = fState;
1603                         context.notifySingle(dyld_image_state_initialized, this, NULL);
1604
1605                         if ( hasInitializers ) {
1606                                 uint64_t t2 = mach_absolute_time();
1607                                 timingInfo.addTime(this->getShortName(), t2-t1);
1608                         }
1609                 }
1610                 catch (const char* msg) {
1611                         // this image is not initialized
1612                         fState = oldState;
1613                         recursiveSpinUnLock();
1614                         throw;
1615                 }
1616         }
1617
1618         recursiveSpinUnLock();
1619 }
1620
1621
1622 static void printTime(const char* msg, uint64_t partTime, uint64_t totalTime)
1623 {
1624         static uint64_t sUnitsPerSecond = 0;
1625         if ( sUnitsPerSecond == 0 ) {
1626                 struct mach_timebase_info timeBaseInfo;
1627                 if ( mach_timebase_info(&timeBaseInfo) != KERN_SUCCESS )
1628                         return;
1629                 sUnitsPerSecond = 1000000000ULL * timeBaseInfo.denom / timeBaseInfo.numer;
1630         }
1631         if ( partTime < sUnitsPerSecond ) {
1632                 uint32_t milliSecondsTimesHundred = (uint32_t)((partTime*100000)/sUnitsPerSecond);
1633                 uint32_t milliSeconds = (uint32_t)(milliSecondsTimesHundred/100);
1634                 uint32_t percentTimesTen = (uint32_t)((partTime*1000)/totalTime);
1635                 uint32_t percent = percentTimesTen/10;
1636                 if ( milliSeconds >= 100 )
1637                         dyld::log("%s: %u.%02u milliseconds (%u.%u%%)\n", msg, milliSeconds, milliSecondsTimesHundred-milliSeconds*100, percent, percentTimesTen-percent*10);
1638                 else if ( milliSeconds >= 10 )
1639                         dyld::log("%s:  %u.%02u milliseconds (%u.%u%%)\n", msg, milliSeconds, milliSecondsTimesHundred-milliSeconds*100, percent, percentTimesTen-percent*10);
1640                 else
1641                         dyld::log("%s:   %u.%02u milliseconds (%u.%u%%)\n", msg, milliSeconds, milliSecondsTimesHundred-milliSeconds*100, percent, percentTimesTen-percent*10);
1642         }
1643         else {
1644                 uint32_t secondsTimeTen = (uint32_t)((partTime*10)/sUnitsPerSecond);
1645                 uint32_t seconds = secondsTimeTen/10;
1646                 uint32_t percentTimesTen = (uint32_t)((partTime*1000)/totalTime);
1647                 uint32_t percent = percentTimesTen/10;
1648                 dyld::log("%s: %u.%u seconds (%u.%u%%)\n", msg, seconds, secondsTimeTen-seconds*10, percent, percentTimesTen-percent*10);
1649         }
1650 }
1651
1652 static char* commatize(uint64_t in, char* out)
1653 {
1654         uint64_t div10 = in / 10;
1655         uint8_t delta = in - div10*10;
1656         char* s = &out[32];
1657         int digitCount = 1;
1658         *s = '\0';
1659         *(--s) = '0' + delta;
1660         in = div10;
1661         while ( in != 0 ) {
1662                 if ( (digitCount % 3) == 0 )
1663                         *(--s) = ',';
1664                 div10 = in / 10;
1665                 delta = in - div10*10;
1666                 *(--s) = '0' + delta;
1667                 in = div10;
1668                 ++digitCount;
1669         }
1670         return s;
1671 }
1672
1673
1674 void ImageLoader::printStatistics(unsigned int imageCount, const InitializerTimingList& timingInfo)
1675 {
1676         uint64_t totalTime = fgTotalLoadLibrariesTime  + fgTotalRebaseTime + fgTotalBindTime + fgTotalWeakBindTime + fgTotalDOF + fgTotalInitTime;
1677
1678         uint64_t totalDyldTime = totalTime - fgTotalDebuggerPausedTime - fgTotalRebindCacheTime;
1679         printTime("Total pre-main time", totalDyldTime, totalDyldTime);
1680         printTime("         dylib loading time", fgTotalLoadLibrariesTime-fgTotalDebuggerPausedTime, totalDyldTime);
1681         printTime("        rebase/binding time", fgTotalRebaseTime+fgTotalBindTime+fgTotalWeakBindTime-fgTotalRebindCacheTime, totalDyldTime);
1682         printTime("            ObjC setup time", fgTotalObjCSetupTime, totalDyldTime);
1683         printTime("           initializer time", fgTotalInitTime-fgTotalObjCSetupTime, totalDyldTime);
1684         dyld::log("           slowest intializers :\n");
1685         for (uintptr_t i=0; i < timingInfo.count; ++i) {
1686                 uint64_t t = timingInfo.images[i].initTime;
1687                 if ( t*50 < totalDyldTime )
1688                         continue;
1689                 dyld::log("%30s ", timingInfo.images[i].shortName);
1690                 if ( strncmp(timingInfo.images[i].shortName, "libSystem.", 10) == 0 )
1691                         t -= fgTotalObjCSetupTime;
1692                         printTime("", t, totalDyldTime);
1693         }
1694         dyld::log("\n");
1695 }
1696
1697 void ImageLoader::printStatisticsDetails(unsigned int imageCount, const InitializerTimingList& timingInfo)
1698 {
1699         uint64_t totalTime = fgTotalLoadLibrariesTime  + fgTotalRebaseTime + fgTotalBindTime + fgTotalWeakBindTime + fgTotalDOF + fgTotalInitTime;
1700         char commaNum1[40];
1701         char commaNum2[40];
1702
1703         printTime("  total time", totalTime, totalTime);
1704         dyld::log("  total images loaded:  %d (%u from dyld shared cache)\n", imageCount, fgImagesUsedFromSharedCache);
1705         dyld::log("  total segments mapped: %u, into %llu pages\n", fgTotalSegmentsMapped, fgTotalBytesMapped/4096);
1706         printTime("  total images loading time", fgTotalLoadLibrariesTime, totalTime);
1707         printTime("  total load time in ObjC", fgTotalObjCSetupTime, totalTime);
1708         printTime("  total debugger pause time", fgTotalDebuggerPausedTime, totalTime);
1709         printTime("  total dtrace DOF registration time", fgTotalDOF, totalTime);
1710         dyld::log("  total rebase fixups:  %s\n", commatize(fgTotalRebaseFixups, commaNum1));
1711         printTime("  total rebase fixups time", fgTotalRebaseTime, totalTime);
1712         dyld::log("  total binding fixups: %s\n", commatize(fgTotalBindFixups, commaNum1));
1713         if ( fgTotalBindSymbolsResolved != 0 ) {
1714                 uint32_t avgTimesTen = (fgTotalBindImageSearches * 10) / fgTotalBindSymbolsResolved;
1715                 uint32_t avgInt = fgTotalBindImageSearches / fgTotalBindSymbolsResolved;
1716                 uint32_t avgTenths = avgTimesTen - (avgInt*10);
1717                 dyld::log("total binding symbol lookups: %s, average images searched per symbol: %u.%u\n",
1718                                 commatize(fgTotalBindSymbolsResolved, commaNum1), avgInt, avgTenths);
1719         }
1720         printTime("  total binding fixups time", fgTotalBindTime, totalTime);
1721         printTime("  total weak binding fixups time", fgTotalWeakBindTime, totalTime);
1722         printTime("  total redo shared cached bindings time", fgTotalRebindCacheTime, totalTime);
1723         dyld::log("  total bindings lazily fixed up: %s of %s\n", commatize(fgTotalLazyBindFixups, commaNum1), commatize(fgTotalPossibleLazyBindFixups, commaNum2));
1724         printTime("  total time in initializers and ObjC +load", fgTotalInitTime-fgTotalObjCSetupTime, totalTime);
1725         for (uintptr_t i=0; i < timingInfo.count; ++i) {
1726                 uint64_t t = timingInfo.images[i].initTime;
1727                 if ( t*1000 < totalTime )
1728                         continue;
1729                 dyld::log("%42s ", timingInfo.images[i].shortName);
1730                 if ( strncmp(timingInfo.images[i].shortName, "libSystem.", 10) == 0 )
1731                         t -= fgTotalObjCSetupTime;
1732                 printTime("", t, totalTime);
1733         }
1734
1735 }
1736
1737
1738 //
1739 // copy path and add suffix to result
1740 //
1741 //  /path/foo.dylib             _debug   =>   /path/foo_debug.dylib
1742 //  foo.dylib                   _debug   =>   foo_debug.dylib
1743 //  foo                         _debug   =>   foo_debug
1744 //  /path/bar                   _debug   =>   /path/bar_debug
1745 //  /path/bar.A.dylib   _debug   =>   /path/bar.A_debug.dylib
1746 //
1747 void ImageLoader::addSuffix(const char* path, const char* suffix, char* result)
1748 {
1749         strcpy(result, path);
1750
1751         char* start = strrchr(result, '/');
1752         if ( start != NULL )
1753                 start++;
1754         else
1755                 start = result;
1756
1757         char* dot = strrchr(start, '.');
1758         if ( dot != NULL ) {
1759                 strcpy(dot, suffix);
1760                 strcat(&dot[strlen(suffix)], &path[dot-result]);
1761         }
1762         else {
1763                 strcat(result, suffix);
1764         }
1765 }
1766
1767
1768 //
1769 // This function is the hotspot of symbol lookup.  It was pulled out of findExportedSymbol()
1770 // to enable it to be re-written in assembler if needed.
1771 //
1772 const uint8_t* ImageLoader::trieWalk(const uint8_t* start, const uint8_t* end, const char* s)
1773 {
1774         //dyld::log("trieWalk(%p, %p, %s)\n", start, end, s);
1775         ++fgSymbolTrieSearchs;
1776         const uint8_t* p = start;
1777         while ( p != NULL ) {
1778                 uintptr_t terminalSize = *p++;
1779                 if ( terminalSize > 127 ) {
1780                         // except for re-export-with-rename, all terminal sizes fit in one byte
1781                         --p;
1782                         terminalSize = read_uleb128(p, end);
1783                 }
1784                 if ( (*s == '\0') && (terminalSize != 0) ) {
1785                         //dyld::log("trieWalk(%p) returning %p\n", start, p);
1786                         return p;
1787                 }
1788                 const uint8_t* children = p + terminalSize;
1789                 if ( children > end ) {
1790                         dyld::log("trieWalk() malformed trie node, terminalSize=0x%lx extends past end of trie\n", terminalSize);
1791                         return NULL;
1792                 }
1793                 //dyld::log("trieWalk(%p) sym=%s, terminalSize=%lu, children=%p\n", start, s, terminalSize, children);
1794                 uint8_t childrenRemaining = *children++;
1795                 p = children;
1796                 uintptr_t nodeOffset = 0;
1797                 for (; childrenRemaining > 0; --childrenRemaining) {
1798                         const char* ss = s;
1799                         //dyld::log("trieWalk(%p) child str=%s\n", start, (char*)p);
1800                         bool wrongEdge = false;
1801                         // scan whole edge to get to next edge
1802                         // if edge is longer than target symbol name, don't read past end of symbol name
1803                         char c = *p;
1804                         while ( c != '\0' ) {
1805                                 if ( !wrongEdge ) {
1806                                         if ( c != *ss )
1807                                                 wrongEdge = true;
1808                                         ++ss;
1809                                 }
1810                                 ++p;
1811                                 c = *p;
1812                         }
1813                         if ( wrongEdge ) {
1814                                 // advance to next child
1815                                 ++p; // skip over zero terminator
1816                                 // skip over uleb128 until last byte is found
1817                                 while ( (*p & 0x80) != 0 )
1818                                         ++p;
1819                                 ++p; // skip over last byte of uleb128
1820                                 if ( p > end ) {
1821                                         dyld::log("trieWalk() malformed trie node, child node extends past end of trie\n");
1822                                         return NULL;
1823                                 }
1824                         }
1825                         else {
1826                                 // the symbol so far matches this edge (child)
1827                                 // so advance to the child's node
1828                                 ++p;
1829                                 nodeOffset = read_uleb128(p, end);
1830                                 if ( (nodeOffset == 0) || ( &start[nodeOffset] > end) ) {
1831                                         dyld::log("trieWalk() malformed trie child, nodeOffset=0x%lx out of range\n", nodeOffset);
1832                                         return NULL;
1833                                 }
1834                                 s = ss;
1835                                 //dyld::log("trieWalk() found matching edge advancing to node 0x%lx\n", nodeOffset);
1836                                 break;
1837                         }
1838                 }
1839                 if ( nodeOffset != 0 )
1840                         p = &start[nodeOffset];
1841                 else
1842                         p = NULL;
1843         }
1844         //dyld::log("trieWalk(%p) return NULL\n", start);
1845         return NULL;
1846 }
1847
1848
1849
1850 uintptr_t ImageLoader::read_uleb128(const uint8_t*& p, const uint8_t* end)
1851 {
1852         uint64_t result = 0;
1853         int              bit = 0;
1854         do {
1855                 if (p == end)
1856                         dyld::throwf("malformed uleb128");
1857
1858                 uint64_t slice = *p & 0x7f;
1859
1860                 if (bit > 63)
1861                         dyld::throwf("uleb128 too big for uint64, bit=%d, result=0x%0llX", bit, result);
1862                 else {
1863                         result |= (slice << bit);
1864                         bit += 7;
1865                 }
1866         } while (*p++ & 0x80);
1867         return (uintptr_t)result;
1868 }
1869
1870
1871 intptr_t ImageLoader::read_sleb128(const uint8_t*& p, const uint8_t* end)
1872 {
1873         int64_t result = 0;
1874         int bit = 0;
1875         uint8_t byte;
1876         do {
1877                 if (p == end)
1878                         throw "malformed sleb128";
1879                 byte = *p++;
1880                 result |= (((int64_t)(byte & 0x7f)) << bit);
1881                 bit += 7;
1882         } while (byte & 0x80);
1883         // sign extend negative numbers
1884         if ( (byte & 0x40) != 0 )
1885                 result |= (~0ULL) << bit;
1886         return (intptr_t)result;
1887 }
1888
1889
1890 VECTOR_NEVER_DESTRUCTED_IMPL(ImageLoader::InterposeTuple);
1891 VECTOR_NEVER_DESTRUCTED_IMPL(ImagePair);
1892
1893
1894