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