src/ImageLoaderMegaDylib.cpp

   1 /* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-
   2  *
   3  * Copyright (c) 2015 Apple Inc. All rights reserved.
   4  *
   5  * @APPLE_LICENSE_HEADER_START@
   6  *
   7  * This file contains Original Code and/or Modifications of Original Code
   8  * as defined in and that are subject to the Apple Public Source License
   9  * Version 2.0 (the 'License'). You may not use this file except in
  10  * compliance with the License. Please obtain a copy of the License at
  11  * http://www.opensource.apple.com/apsl/ and read it before using this
  12  * file.
  13  *
  14  * The Original Code and all software distributed under the License are
  15  * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
  16  * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
  17  * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
  18  * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
  19  * Please see the License for the specific language governing rights and
  20  * limitations under the License.
  21  *
  22  * @APPLE_LICENSE_HEADER_END@
  23  */
  24
  25
  26 #if __arm__ || __arm64__
  27   #include <System/sys/mman.h>
  28 #else
  29   #include <sys/mman.h>
  30 #endif
  31 #include <string.h>
  32 #include <dlfcn.h>
  33 #include <fcntl.h>
  34 #include <errno.h>
  35 #include <sys/types.h>
  36 #include <sys/fcntl.h>
  37 #include <sys/stat.h>
  38 #include <sys/param.h>
  39 #include <mach/mach.h>
  40 #include <mach/thread_status.h>
  41 #include <mach-o/loader.h>
  42 #include <libkern/OSAtomic.h>
  43
  44 #include "ImageLoaderMegaDylib.h"
  45 #include "ImageLoaderMachO.h"
  46 #include "mach-o/dyld_images.h"
  47 #include "dyldLibSystemInterface.h"
  48 #include "Tracing.h"
  49 #include "dyld.h"
  50
  51 // from dyld_gdb.cpp
  52 extern void addImagesToAllImages(uint32_t infoCount, const dyld_image_info info[]);
  53
  54 extern "C" int _dyld_func_lookup(const char* name, void** address);
  55
  56
  57 #ifndef EXPORT_SYMBOL_FLAGS_KIND_ABSOLUTE
  58         #define EXPORT_SYMBOL_FLAGS_KIND_ABSOLUTE                       0x02
  59 #endif
  60
  61 // relocation_info.r_length field has value 3 for 64-bit executables and value 2 for 32-bit executables
  62 #if __LP64__
  63         #define RELOC_SIZE 3
  64         #define LC_SEGMENT_COMMAND              LC_SEGMENT_64
  65         #define LC_ROUTINES_COMMAND             LC_ROUTINES_64
  66         struct macho_segment_command    : public segment_command_64  {};
  67         struct macho_section                    : public section_64  {};
  68         struct macho_routines_command   : public routines_command_64  {};
  69 #else
  70         #define RELOC_SIZE 2
  71         #define LC_SEGMENT_COMMAND              LC_SEGMENT
  72         #define LC_ROUTINES_COMMAND             LC_ROUTINES
  73         struct macho_segment_command    : public segment_command {};
  74         struct macho_section                    : public section  {};
  75         struct macho_routines_command   : public routines_command  {};
  76 #endif
  77
  78
  79
  80 #if SUPPORT_ACCELERATE_TABLES
  81
  82
  83 ImageLoaderMegaDylib* ImageLoaderMegaDylib::makeImageLoaderMegaDylib(const dyld_cache_header* header, long slide, const macho_header* mainMH, const LinkContext& context)
  84 {
  85         return new ImageLoaderMegaDylib(header, slide, mainMH, context);
  86 }
  87
  88 struct DATAdyld {
  89         void*                   dyldLazyBinder;         // filled in at launch by dyld to point into dyld to &stub_binding_helper
  90         void*                   dyldFuncLookup;         // filled in at launch by dyld to point into dyld to &_dyld_func_lookup
  91         ProgramVars             vars;
  92 };
  93
  94
  95
  96
  97 ImageLoaderMegaDylib::ImageLoaderMegaDylib(const dyld_cache_header* header, long slide, const macho_header* mainMH, const LinkContext& context)
  98         : ImageLoader("dyld shared cache", 0), _header(header), _linkEditBias(NULL), _slide(slide),
  99          _lockArray(NULL), _lockArrayInUseCount(0)
 100 {
 101         pthread_mutex_init(&_lockArrayGuard, NULL);
 102         const dyld_cache_mapping_info* mappings = (const dyld_cache_mapping_info*)((uint8_t*)_header + _header->mappingOffset);
 103         const dyld_cache_mapping_info* lastMapping = &mappings[_header->mappingCount-1];
 104         const dyld_cache_accelerator_info* accHeader = (dyld_cache_accelerator_info*)(_header->accelerateInfoAddr + slide);
 105         for (const dyld_cache_mapping_info* m=mappings; m <= lastMapping; ++m) {
 106                 if ( m->initProt == VM_PROT_READ ) {
 107                         _linkEditBias = (uint8_t*)(m->address - m->fileOffset) + _slide;
 108                 }
 109         }
 110
 111         _endOfCacheInMemory = (void*)(lastMapping->address + lastMapping->size + slide);
 112         _images = (const dyld_cache_image_info*)((uint8_t*)_header + _header->imagesOffset);
 113         _imageExtras = (dyld_cache_image_info_extra*)((char*)accHeader + accHeader->imagesExtrasOffset);
 114         _initializers = (dyld_cache_accelerator_initializer*)((char*)accHeader + accHeader->initializersOffset);
 115         _reExportsArray = (uint16_t*)((char*)accHeader + accHeader->reExportListOffset);
 116         _dependenciesArray = (uint16_t*)((char*)accHeader + accHeader->depListOffset);
 117         _bottomUpArray = (uint16_t*)((char*)accHeader + accHeader->bottomUpListOffset);
 118         _rangeTable = (dyld_cache_range_entry*)((char*)accHeader + accHeader->rangeTableOffset);
 119         _rangeTableCount = accHeader->rangeTableCount;
 120         _imageCount = accHeader->imageExtrasCount;
 121         _stateFlags = (uint8_t*)calloc(_imageCount, 1);
 122         _initializerCount = accHeader->initializersCount;
 123         _dylibsTrieStart = (uint8_t*)accHeader + accHeader->dylibTrieOffset;
 124         _dylibsTrieEnd = _dylibsTrieStart + accHeader->dylibTrieSize;
 125         _imageTextInfo = (dyld_cache_image_text_info*)((uint8_t*)_header + _header->imagesTextOffset);
 126         DATAdyld* dyldSection = (DATAdyld*)(accHeader->dyldSectionAddr + slide);
 127         dyldSection->dyldLazyBinder = NULL; // not used by libdyld.dylib
 128         dyldSection->dyldFuncLookup = (void*)&_dyld_func_lookup;
 129         dyldSection->vars.mh = mainMH;
 130         context.setNewProgramVars(dyldSection->vars);
 131 }
 132
 133
 134 void ImageLoaderMegaDylib::unreachable() const
 135 {
 136         abort();
 137 }
 138
 139 ImageLoaderMegaDylib::~ImageLoaderMegaDylib()
 140 {
 141 }
 142
 143 const char*     ImageLoaderMegaDylib::getInstallPath() const {
 144         unreachable();
 145 }
 146
 147 const macho_header* ImageLoaderMegaDylib::getIndexedMachHeader(unsigned index) const
 148 {
 149         if ( index > _header->imagesCount )
 150                 dyld::throwf("cache image index out of range (%u), max=%u", index, _header->imagesCount - 1);
 151         return (const macho_header*)(_images[index].address + _slide);
 152 }
 153
 154 const char* ImageLoaderMegaDylib::getIndexedPath(unsigned index) const
 155 {
 156         if ( index > _header->imagesCount )
 157                 dyld::throwf("cache image index out of range (%u), max=%u", index, _header->imagesCount - 1);
 158         return (char*)_header + _images[index].pathFileOffset;
 159 }
 160
 161 const char* ImageLoaderMegaDylib::getIndexedShortName(unsigned index) const
 162 {
 163         const char* path = getIndexedPath(index);
 164         const char* lastSlash = strrchr(path, '/');
 165         if ( lastSlash == NULL )
 166                 return path;
 167         else
 168                 return lastSlash+1;
 169 }
 170
 171 void ImageLoaderMegaDylib::getDylibUUID(unsigned int index, uuid_t uuid) const
 172 {
 173         if ( index > _header->imagesCount )
 174                 dyld::throwf("cache image index out of range (%u), max=%u", index, _header->imagesCount - 1);
 175         memcpy(uuid, _imageTextInfo[index].uuid, 16);
 176 }
 177
 178 void ImageLoaderMegaDylib::printSegments(const macho_header* mh) const
 179 {
 180         const uint32_t cmd_count = mh->ncmds;
 181         const struct load_command* const cmds = (struct load_command*)((uint8_t*)mh + sizeof(macho_header));
 182         const struct load_command* cmd = cmds;
 183         const macho_segment_command* seg;
 184         for (uint32_t i = 0; i < cmd_count; ++i) {
 185                 switch (cmd->cmd) {
 186                         case LC_SEGMENT_COMMAND:
 187                                 seg = (macho_segment_command*)cmd;
 188                                 dyld::log("%18s at 0x%08lX->0x%08lX\n", seg->segname, (long)(seg->vmaddr + _slide), (long)(seg->vmaddr + seg->vmsize + _slide));
 189                                 break;
 190                 }
 191                 cmd = (const struct load_command*)(((char*)cmd)+cmd->cmdsize);
 192         }
 193 }
 194
 195 bool ImageLoaderMegaDylib::hasDylib(const char* path, unsigned* index) const
 196 {
 197         const uint8_t* imageNode = ImageLoader::trieWalk(_dylibsTrieStart, _dylibsTrieEnd, path);
 198         if ( imageNode == NULL ) {
 199   #if __MAC_OS_X_VERSION_MIN_REQUIRED
 200                 // not all symlinks are recorded as aliases in accelerator tables
 201                 if ( (strncmp(path, "/usr/lib/", 9) == 0) || (strncmp(path, "/System/Library/", 16) == 0) ) {
 202                         char resolvedPath[PATH_MAX];
 203                         if ( realpath(path, resolvedPath) != NULL ) {
 204                                 imageNode = ImageLoader::trieWalk(_dylibsTrieStart, _dylibsTrieEnd, resolvedPath);
 205                         }
 206                 }
 207                 if ( imageNode == NULL )
 208                         return false;
 209   #else
 210                 return false;
 211   #endif
 212         }
 213         *index = (unsigned)read_uleb128(imageNode, _dylibsTrieEnd);
 214         return true;
 215 }
 216
 217 bool ImageLoaderMegaDylib::addressInCache(const void* address, const mach_header** mh, const char** path, unsigned* index)
 218 {
 219         // quick out of bounds check
 220 #if __x86_64__
 221         if ( (uintptr_t)address < 0x7FFF70000000LL )
 222                 return false;
 223 #else
 224         if ( address < (void*)_header )
 225                 return false;
 226 #endif
 227         if ( address > _endOfCacheInMemory )
 228                 return false;
 229
 230         uint64_t unslidAddress = (uint64_t)address - _slide;
 231         // linear search for now
 232         const dyld_cache_range_entry* rangeTableEnd = &_rangeTable[_rangeTableCount];
 233         for (const dyld_cache_range_entry* r = _rangeTable; r < rangeTableEnd; ++r) {
 234                 if ( (r->startAddress <= unslidAddress) && (unslidAddress < r->startAddress+r->size) ) {
 235                         *index = r->imageIndex;
 236                         *mh = (mach_header*)getIndexedMachHeader(r->imageIndex);
 237                         *path = getIndexedPath(r->imageIndex);
 238                         return true;
 239                 }
 240         }
 241
 242         return false;
 243 }
 244
 245
 246 bool ImageLoaderMegaDylib::findUnwindSections(const void* address, dyld_unwind_sections* info)
 247 {
 248         const char* path;
 249         unsigned index;
 250         if ( addressInCache(address, &info->mh, &path, &index) ) {
 251                 info->dwarf_section = NULL;
 252                 info->dwarf_section_length = 0;
 253                 ImageLoaderMachO::findSection(info->mh, "__TEXT", "__eh_frame", (void**)&info->dwarf_section, &info->dwarf_section_length);
 254
 255                 info->compact_unwind_section = NULL;
 256                 info->compact_unwind_section_length = 0;
 257                 ImageLoaderMachO::findSection(info->mh, "__TEXT", "__unwind_info", (void**)&info->compact_unwind_section, &info->compact_unwind_section_length);
 258
 259                 return true;
 260         }
 261         return false;
 262 }
 263
 264
 265 unsigned ImageLoaderMegaDylib::findImageIndex(const LinkContext& context, const char* path) const
 266 {
 267         unsigned index;
 268         if ( hasDylib(path, &index) )
 269                 return index;
 270
 271         // <rdar://problem/26934069> Somehow we found the dylib in the cache, but it is not this literal string, try simple expansions of @rpath
 272         if ( strncmp(path, "@rpath/", 7) == 0 ) {
 273                 std::vector<const char*> rpathsFromMainExecutable;
 274                 context.mainExecutable->getRPaths(context, rpathsFromMainExecutable);
 275                 rpathsFromMainExecutable.push_back("/System/Library/Frameworks/");
 276                 const char* trailingPath = &path[7];
 277                 for (const char* anRPath : rpathsFromMainExecutable) {
 278                         if ( anRPath[0] != '/' )
 279                                 continue;
 280                         char possiblePath[strlen(anRPath) + strlen(trailingPath)+2];
 281                         strcpy(possiblePath, anRPath);
 282                         if ( possiblePath[strlen(possiblePath)-1] != '/' )
 283                                 strcat(possiblePath, "/");
 284                         strcat(possiblePath, trailingPath);
 285                         if ( hasDylib(possiblePath, &index) ) {
 286                                 return index;
 287                         }
 288                 }
 289         }
 290     else {
 291         // handle symlinks embedded in load commands
 292         char resolvedPath[PATH_MAX];
 293         realpath(path, resolvedPath);
 294         int realpathErrno = errno;
 295         // If realpath() resolves to a path which does not exist on disk, errno is set to ENOENT
 296         if ( (realpathErrno == ENOENT) || (realpathErrno == 0) ) {
 297             if ( strcmp(resolvedPath, path) != 0 )
 298                 return findImageIndex(context, resolvedPath);
 299         }
 300     }
 301
 302         dyld::throwf("no cache image with name (%s)", path);
 303 }
 304
 305 void ImageLoaderMegaDylib::initializeCoalIterator(CoalIterator& it, unsigned int loadOrder, unsigned imageIndex)
 306 {
 307         it.image = this;
 308         it.symbolName = " ";
 309         it.loadOrder = loadOrder;
 310         it.weakSymbol = false;
 311         it.symbolMatches = false;
 312         it.done = false;
 313         it.curIndex = 0;
 314         it.endIndex = _imageExtras[imageIndex].weakBindingsSize;
 315         it.address = 0;
 316         it.type = 0;
 317         it.addend = 0;
 318         it.imageIndex = imageIndex;
 319 }
 320
 321 bool ImageLoaderMegaDylib::incrementCoalIterator(CoalIterator& it)
 322 {
 323         if ( it.done )
 324                 return false;
 325
 326         if ( _imageExtras[it.imageIndex].weakBindingsSize == 0 ) {
 327                 /// hmmm, ld set MH_WEAK_DEFINES or MH_BINDS_TO_WEAK, but there is no weak binding info
 328                 it.done = true;
 329                 it.symbolName = "~~~";
 330                 return true;
 331         }
 332         const uint8_t* start = (uint8_t*)(_imageExtras[it.imageIndex].weakBindingsAddr + _slide);
 333         const uint8_t* end = (uint8_t*)(_imageExtras[it.imageIndex].weakBindingsAddr + _slide + _imageExtras[it.imageIndex].weakBindingsSize);
 334         const uint8_t* p = start + it.curIndex;
 335         uintptr_t count;
 336         uintptr_t skip;
 337         uint64_t segOffset;
 338         unsigned segIndex;
 339         const mach_header* mh;
 340         while ( p < end ) {
 341                 uint8_t immediate = *p & BIND_IMMEDIATE_MASK;
 342                 uint8_t opcode = *p & BIND_OPCODE_MASK;
 343                 ++p;
 344                 switch (opcode) {
 345                         case BIND_OPCODE_DONE:
 346                                 it.done = true;
 347                                 it.curIndex = p - start;
 348                                 it.symbolName = "~~~"; // sorts to end
 349                                 return true;
 350                         case BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM:
 351                                 it.symbolName = (char*)p;
 352                                 it.weakSymbol = ((immediate & BIND_SYMBOL_FLAGS_NON_WEAK_DEFINITION) == 0);
 353                                 it.symbolMatches = false;
 354                                 while (*p != '\0')
 355                                         ++p;
 356                                 ++p;
 357                                 it.curIndex = p - start;
 358                                 return false;
 359                         case BIND_OPCODE_SET_TYPE_IMM:
 360                                 it.type = immediate;
 361                                 break;
 362                         case BIND_OPCODE_SET_ADDEND_SLEB:
 363                                 it.addend = read_sleb128(p, end);
 364                                 break;
 365                         case BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB:
 366                                 segIndex = immediate;
 367                                 segOffset = read_uleb128(p, end);
 368                                 mh = (mach_header*)getIndexedMachHeader((unsigned)it.imageIndex);
 369                                 if ( uintptr_t segPrefAddress = ImageLoaderMachO::segPreferredAddress(mh, segIndex) )
 370                                         it.address = segPrefAddress + segOffset + _slide;
 371                                 else
 372                                         dyld::throwf("BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB has segment %d which is too large", segIndex);
 373                                 break;
 374                         case BIND_OPCODE_ADD_ADDR_ULEB:
 375                                 it.address += read_uleb128(p, end);
 376                                 break;
 377                         case BIND_OPCODE_DO_BIND:
 378                                 it.address += sizeof(intptr_t);
 379                                 break;
 380                         case BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB:
 381                                 it.address += read_uleb128(p, end) + sizeof(intptr_t);
 382                                 break;
 383                         case BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED:
 384                                 it.address += immediate*sizeof(intptr_t) + sizeof(intptr_t);
 385                                 break;
 386                         case BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB:
 387                                 count = read_uleb128(p, end);
 388                                 skip = read_uleb128(p, end);
 389                                 for (uint32_t i=0; i < count; ++i) {
 390                                         it.address += skip + sizeof(intptr_t);
 391                                 }
 392                                 break;
 393                         default:
 394                                 dyld::throwf("bad weak bind opcode '%d' found after processing %d bytes in '%s'", *p, (int)(p-start), this->getPath());
 395                 }
 396         }
 397         /// hmmm, BIND_OPCODE_DONE is missing...
 398         it.done = true;
 399         it.symbolName = "~~~";
 400         //dyld::log("missing BIND_OPCODE_DONE for image %s\n", this->getPath());
 401         return true;
 402 }
 403
 404 uintptr_t ImageLoaderMegaDylib::getAddressCoalIterator(CoalIterator& it, const LinkContext& context)
 405 {
 406         //dyld::log("looking for %s in %s\n", it.symbolName, this->getPath());
 407         uintptr_t address;
 408         if ( findInChainedTries(context, it.symbolName, (unsigned)it.imageIndex, NULL, false, &address) ) {
 409                 return address;
 410         }
 411         return 0;
 412 }
 413
 414 void ImageLoaderMegaDylib::updateUsesCoalIterator(CoalIterator& it, uintptr_t value, ImageLoader* targetImage, unsigned targetIndex, const LinkContext& context)
 415 {
 416
 417         const uint8_t* start = (uint8_t*)(_imageExtras[it.imageIndex].weakBindingsAddr + _slide);
 418         const uint8_t* end = (uint8_t*)(_imageExtras[it.imageIndex].weakBindingsAddr + _slide + _imageExtras[it.imageIndex].weakBindingsSize);
 419         const uint8_t* p = start + it.curIndex;
 420
 421         uint8_t type = it.type;
 422         uintptr_t address = it.address;
 423         const char* symbolName = it.symbolName;
 424         intptr_t addend = it.addend;
 425         uint64_t segOffset;
 426         unsigned segIndex;
 427         const mach_header* mh;
 428         uintptr_t count;
 429         uintptr_t skip;
 430         bool done = false;
 431         bool boundSomething = false;
 432         const char* targetImagePath = targetImage ? targetImage->getIndexedPath(targetIndex) : NULL;
 433         while ( !done && (p < end) ) {
 434                 uint8_t immediate = *p & BIND_IMMEDIATE_MASK;
 435                 uint8_t opcode = *p & BIND_OPCODE_MASK;
 436                 ++p;
 437                 switch (opcode) {
 438                         case BIND_OPCODE_DONE:
 439                                 done = true;
 440                                 break;
 441                         case BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM:
 442                                 done = true;
 443                                 break;
 444                         case BIND_OPCODE_SET_TYPE_IMM:
 445                                 type = immediate;
 446                                 break;
 447                         case BIND_OPCODE_SET_ADDEND_SLEB:
 448                                 addend = read_sleb128(p, end);
 449                                 break;
 450                         case BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB:
 451                                 segIndex = immediate;
 452                                 segOffset = read_uleb128(p, end);
 453                                 mh = (mach_header*)getIndexedMachHeader((unsigned)it.imageIndex);
 454                                 if ( uintptr_t segPrefAddress = ImageLoaderMachO::segPreferredAddress(mh, segIndex) )
 455                                         address = segPrefAddress + segOffset + _slide;
 456                                 else
 457                                         dyld::throwf("BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB has segment %d which is too large", segIndex);
 458                                 break;
 459                         case BIND_OPCODE_ADD_ADDR_ULEB:
 460                                 address += read_uleb128(p, end);
 461                                 break;
 462                         case BIND_OPCODE_DO_BIND:
 463                                 ImageLoaderMachO::bindLocation(context, 0, address, value, type, symbolName, addend, getIndexedPath((unsigned)it.imageIndex), targetImagePath, "weak ", NULL, _slide);
 464                                 boundSomething = true;
 465                                 address += sizeof(intptr_t);
 466                                 break;
 467                         case BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB:
 468                                 ImageLoaderMachO::bindLocation(context, 0, address, value, type, symbolName, addend, getIndexedPath((unsigned)it.imageIndex), targetImagePath, "weak ", NULL, _slide);
 469                                 boundSomething = true;
 470                                 address += read_uleb128(p, end) + sizeof(intptr_t);
 471                                 break;
 472                         case BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED:
 473                                 ImageLoaderMachO::bindLocation(context, 0, address, value, type, symbolName, addend, getIndexedPath((unsigned)it.imageIndex), targetImagePath, "weak ", NULL, _slide);
 474                                 boundSomething = true;
 475                                 address += immediate*sizeof(intptr_t) + sizeof(intptr_t);
 476                                 break;
 477                         case BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB:
 478                                 count = read_uleb128(p, end);
 479                                 skip = read_uleb128(p, end);
 480                                 for (uint32_t i=0; i < count; ++i) {
 481                                         ImageLoaderMachO::bindLocation(context, 0, address, value, type, symbolName, addend, getIndexedPath((unsigned)it.imageIndex), targetImagePath, "weak ", NULL, _slide);
 482                                         boundSomething = true;
 483                                         address += skip + sizeof(intptr_t);
 484                                 }
 485                                 break;
 486                         default:
 487                                 dyld::throwf("bad bind opcode %d in weak binding info", *p);
 488                 }
 489         }
 490         // C++ weak coalescing cannot be tracked by reference counting.  Error on side of never unloading.
 491         if ( boundSomething && (targetImage != this) )
 492                 context.addDynamicReference(this, targetImage);
 493 }
 494
 495
 496 void ImageLoaderMegaDylib::appendImagesNeedingCoalescing(ImageLoader* images[], unsigned imageIndexes[], unsigned& count)
 497 {
 498         for (unsigned i=0; i < _imageCount; ++i) {
 499                 uint16_t index = _bottomUpArray[i];
 500                 if ( _stateFlags[index] == kStateUnused )
 501                         continue;
 502                 if ( _imageExtras[index].weakBindingsSize == 0 )
 503                         continue;
 504                 images[count] = this;
 505                 imageIndexes[count] = index;
 506                 ++count;
 507         }
 508 }
 509
 510
 511 bool ImageLoaderMegaDylib::weakSymbolsBound(unsigned index)
 512 {
 513         return ( _stateFlags[index] >= kStateFlagWeakBound );
 514 }
 515
 516 void ImageLoaderMegaDylib::setWeakSymbolsBound(unsigned index)
 517 {
 518         if ( _stateFlags[index] == kStateFlagBound )
 519                 _stateFlags[index] = kStateFlagWeakBound;
 520 }
 521
 522
 523 void ImageLoaderMegaDylib::recursiveMarkLoaded(const LinkContext& context, unsigned imageIndex)
 524 {
 525         if ( _stateFlags[imageIndex] != kStateUnused )
 526                 return;
 527
 528         const macho_header* mh = getIndexedMachHeader(imageIndex);
 529         const char* path = getIndexedPath(imageIndex);
 530
 531         if ( context.verboseLoading )
 532                 dyld::log("dyld: loaded: %s\n", path);
 533         if ( context.verboseMapping ) {
 534                 dyld::log("dyld: Using shared cached for %s\n", path);
 535                 printSegments(mh);
 536         }
 537
 538         // change state to "loaded" before recursing to break cycles
 539         _stateFlags[imageIndex] = kStateLoaded;
 540         ++fgImagesUsedFromSharedCache;
 541
 542         dyld_image_info debuggerInfo;
 543         debuggerInfo.imageLoadAddress = (mach_header*)mh;
 544         debuggerInfo.imageFilePath = path;
 545         debuggerInfo.imageFileModDate = 0;
 546         addImagesToAllImages(1, &debuggerInfo);
 547
 548         if ( _imageExtras[imageIndex].weakBindingsSize != 0 ) {
 549                 ++fgImagesRequiringCoalescing;
 550                 ++fgImagesHasWeakDefinitions;
 551         }
 552
 553         unsigned startArrayIndex = _imageExtras[imageIndex].dependentsStartArrayIndex;
 554         for (int i=startArrayIndex; _dependenciesArray[i] != 0xFFFF; ++i) {
 555                 unsigned subDep = (_dependenciesArray[i] & 0x7FFF); // mask off upward bit
 556                 recursiveMarkLoaded(context, subDep);
 557         }
 558 }
 559
 560 void ImageLoaderMegaDylib::recursiveLoadLibraries(const LinkContext& context, bool preflightOnly, const RPathChain& loaderRPaths, const char* loadPath)
 561 {
 562         unsigned index = findImageIndex(context, loadPath);
 563         recursiveMarkLoaded(context, index);
 564 }
 565
 566 unsigned int ImageLoaderMegaDylib::recursiveUpdateDepth(unsigned int maxDepth)
 567 {
 568         setDepth(maxDepth);
 569         return maxDepth;
 570 }
 571
 572
 573 const ImageLoader::Symbol* ImageLoaderMegaDylib::findExportedSymbol(const char* name, bool searchReExports, const char* thisPath, const ImageLoader** foundIn) const
 574 {
 575         unsigned index;
 576         if ( !hasDylib(thisPath, &index) )
 577                 return NULL;
 578         const uint8_t* exportNode;
 579         const uint8_t* exportTrieEnd;
 580         unsigned foundinIndex;
 581         // <rdar://problem/22068598> always search re-exports
 582         // the point of searchReExports was to break cycles in dylibs, we don't have cycles in cache, so ok to search deep
 583         searchReExports = true;
 584         if ( searchReExports ) {
 585                 if ( !exportTrieHasNodeRecursive(name, index, &exportNode, &exportTrieEnd, &foundinIndex) )
 586                         return NULL;
 587         }
 588         else {
 589                 if ( !exportTrieHasNode(name, index, &exportNode, &exportTrieEnd) )
 590                         return NULL;
 591         }
 592         *foundIn = this;
 593         return (ImageLoader::Symbol*)exportNode;
 594 }
 595
 596 bool ImageLoaderMegaDylib::exportTrieHasNode(const char* symbolName, unsigned index,
 597                                                                                          const uint8_t** exportNode, const uint8_t** exportTrieEnd) const
 598 {
 599         const uint8_t* start = (uint8_t*)(_imageExtras[index].exportsTrieAddr + _slide);
 600         const uint32_t size = _imageExtras[index].exportsTrieSize;
 601         if ( size == 0 )
 602                 return false;
 603         const uint8_t* end = start + size;
 604         const uint8_t* node = ImageLoader::trieWalk(start, end, symbolName);
 605         if ( node == NULL )
 606                 return false;
 607         *exportNode = node;
 608         *exportTrieEnd = end;
 609         return true;
 610 }
 611
 612 bool ImageLoaderMegaDylib::exportTrieHasNodeRecursive(const char* symbolName, unsigned index,
 613                                                                                                                 const uint8_t** exportNode, const uint8_t** exportTrieEnd,
 614                                                                                                                 unsigned* foundinIndex) const
 615 {
 616         // look in trie for image index
 617         if ( exportTrieHasNode(symbolName, index, exportNode, exportTrieEnd) ) {
 618                 *foundinIndex = index;
 619                 return true;
 620         }
 621         // recursively look in all re-exported tries
 622         unsigned startArrayIndex = _imageExtras[index].reExportsStartArrayIndex;
 623         for (int i=startArrayIndex; _reExportsArray[i] != 0xFFFF; ++i) {
 624                 unsigned reExIndex = _reExportsArray[i];
 625                 if ( exportTrieHasNodeRecursive(symbolName, reExIndex, exportNode, exportTrieEnd, foundinIndex) )
 626                         return true;
 627         }
 628         return false;
 629 }
 630
 631 bool ImageLoaderMegaDylib::findExportedSymbolAddress(const LinkContext& context, const char* symbolName,
 632                                                                                                         const ImageLoader* requestorImage, int requestorOrdinalOfDef,
 633                                                                                                         bool runResolver, const ImageLoader** foundIn, uintptr_t* address) const
 634 {
 635         const char* definedImagePath = requestorImage->libPath(requestorOrdinalOfDef-1);
 636         unsigned index = findImageIndex(context, definedImagePath);
 637         *foundIn = this;
 638         return findInChainedTries(context, symbolName, index, requestorImage, runResolver, address);
 639 }
 640
 641 uintptr_t ImageLoaderMegaDylib::getExportedSymbolAddress(const Symbol* sym, const LinkContext& context,
 642                                                                                                                  const ImageLoader* requestor, bool runResolver, const char* symbolName) const
 643 {
 644         // scan for with trie contains this node
 645         const uint8_t* exportTrieEnd = NULL;
 646         unsigned imageIndex = 0xFFFF;
 647         const macho_header* mh = NULL;
 648         uint64_t unslidTrieNode = ((uintptr_t)sym) - _slide;
 649         for (unsigned i=0; i < _imageCount; ++i) {
 650                 uint64_t start = _imageExtras[i].exportsTrieAddr;
 651                 uint64_t end   = _imageExtras[i].exportsTrieAddr +  _imageExtras[i].exportsTrieSize;
 652                 if ( (start < unslidTrieNode) && (unslidTrieNode < end) ) {
 653                         exportTrieEnd = (uint8_t*)(end + _slide);
 654                         imageIndex = i;
 655                         mh = (macho_header*)(_images[imageIndex].address + _slide);
 656                         break;
 657                 }
 658         }
 659
 660         if ( mh == NULL )
 661                 dyld::throwf("getExportedSymbolAddress(Symbol=%p) not in a cache trie", sym);
 662
 663         const uint8_t* exportNode = (const uint8_t*)sym;
 664         uintptr_t address;
 665         processExportNode(context, symbolName ? symbolName : "unknown", imageIndex, exportNode, exportTrieEnd, requestor, runResolver, &address);
 666         return address;
 667 }
 668
 669 void ImageLoaderMegaDylib::processExportNode(const LinkContext& context, const char* symbolName, unsigned definedImageIndex,
 670                                                                                         const uint8_t* exportNode, const uint8_t* exportTrieEnd,
 671                                                                                           const ImageLoader* requestorImage, bool runResolver, uintptr_t* address) const
 672 {
 673         const macho_header* mh = getIndexedMachHeader(definedImageIndex);
 674         uintptr_t flags = read_uleb128(exportNode, exportTrieEnd);
 675         uintptr_t rawAddress;
 676         switch ( flags & EXPORT_SYMBOL_FLAGS_KIND_MASK ) {
 677                 case EXPORT_SYMBOL_FLAGS_KIND_REGULAR:
 678                         if ( runResolver && (flags & EXPORT_SYMBOL_FLAGS_STUB_AND_RESOLVER) ) {
 679                                 // this node has a stub and resolver, run the resolver to get target address
 680                                 uintptr_t stub = read_uleb128(exportNode, exportTrieEnd) + (uintptr_t)mh; // skip over stub
 681                                 // <rdar://problem/10657737> interposing dylibs have the stub address as their replacee
 682                                 uintptr_t interposedStub = interposedAddress(context, stub, requestorImage);
 683                                 if ( interposedStub != stub ) {
 684                                         *address = interposedStub;
 685                                         return;
 686                                 }
 687                                 // stub was not interposed, so run resolver
 688                                 typedef uintptr_t (*ResolverProc)(void);
 689                                 ResolverProc resolver = (ResolverProc)(read_uleb128(exportNode, exportTrieEnd) + (uintptr_t)mh);
 690                                 *address = (*resolver)();
 691                                 if ( context.verboseBind )
 692                                         dyld::log("dyld: resolver at %p returned 0x%08lX\n", resolver, *address);
 693                                 return;
 694                         }
 695                         if ( flags & EXPORT_SYMBOL_FLAGS_REEXPORT ) {
 696                                 // re-export from another dylib, lookup there
 697                                 const uintptr_t ordinal = read_uleb128(exportNode, exportTrieEnd);
 698                                 const char* importedName = (char*)exportNode;
 699                                 if ( importedName[0] == '\0' )
 700                                         importedName = symbolName;
 701                                 unsigned startArrayIndex = _imageExtras[definedImageIndex].dependentsStartArrayIndex;
 702                                 unsigned reExImageIndex = _dependenciesArray[startArrayIndex + ordinal-1] & 0x7FFF;
 703                                 if ( findInChainedTries(context, importedName, reExImageIndex, requestorImage, runResolver, address) )
 704                                         return;
 705                                 dyld::throwf("re-exported symbol '%s' not found for image %s expected re-exported in %s, node=%p",
 706                                                         symbolName, getIndexedShortName(definedImageIndex), getIndexedShortName(reExImageIndex), exportNode);
 707                         }
 708                         rawAddress = read_uleb128(exportNode, exportTrieEnd) + (uintptr_t)mh;
 709                         *address = interposedAddress(context, rawAddress, requestorImage);
 710                         return;
 711                 case EXPORT_SYMBOL_FLAGS_KIND_THREAD_LOCAL:
 712                         if ( flags & EXPORT_SYMBOL_FLAGS_STUB_AND_RESOLVER )
 713                                 dyld::throwf("unsupported exported symbol kind. flags=%lu at node=%p", flags, exportNode);
 714                         *address = read_uleb128(exportNode, exportTrieEnd) + (uintptr_t)mh;
 715                         return;
 716                 case EXPORT_SYMBOL_FLAGS_KIND_ABSOLUTE:
 717                         if ( flags & EXPORT_SYMBOL_FLAGS_STUB_AND_RESOLVER )
 718                                 dyld::throwf("unsupported exported symbol kind. flags=%lu at node=%p", flags, exportNode);
 719                         *address = read_uleb128(exportNode, exportTrieEnd);
 720                         return;
 721                 default:
 722                         dyld::throwf("unsupported exported symbol kind. flags=%lu at node=%p", flags, exportNode);
 723         }
 724         dyld::throwf("unsupported exported symbol node=%p", exportNode);
 725 }
 726
 727 bool ImageLoaderMegaDylib::findInChainedTries(const LinkContext& context, const char* symbolName, unsigned definedImageIndex,
 728                                                                                           const ImageLoader* requestorImage, bool runResolver, uintptr_t* address) const
 729 {
 730         //dyld::log("findInChainedTries(sym=%s, index=%u, path=%s)\n", symbolName, definedImageIndex, getIndexedPath(definedImageIndex));
 731         const uint8_t* exportNode;
 732         const uint8_t* exportTrieEnd;
 733         unsigned foundinIndex;
 734         if ( !exportTrieHasNodeRecursive(symbolName, definedImageIndex, &exportNode, &exportTrieEnd, &foundinIndex) )
 735                 return false;
 736
 737         processExportNode(context, symbolName, foundinIndex, exportNode, exportTrieEnd, requestorImage, runResolver, address);
 738         return true;
 739 }
 740
 741
 742 bool ImageLoaderMegaDylib::findInChainedTriesAndDependentsExcept(const LinkContext& context, const char* symbolName, unsigned imageIndex,
 743                                                                                                                                 const ImageLoader* requestorImage, bool runResolver, bool alreadyVisited[], uintptr_t* address) const
 744 {
 745         //dyld::log("findInChainedTriesAndDependentsExcept(sym=%s, index=%u, path=%s)\n", symbolName, imageIndex, getIndexedPath(imageIndex));
 746         if ( alreadyVisited[imageIndex] )
 747                 return false;
 748         alreadyVisited[imageIndex] = true;
 749
 750         if ( findInChainedTries(context, symbolName, imageIndex, requestorImage, runResolver, address) )
 751                 return true;
 752
 753         unsigned startArrayIndex = _imageExtras[imageIndex].dependentsStartArrayIndex;
 754         for (int i=startArrayIndex; _dependenciesArray[i] != 0xFFFF; ++i) {
 755                 // ignore upward links
 756                 if ( (_dependenciesArray[i] & 0x8000) == 0 ) {
 757                         unsigned depIndex = _dependenciesArray[i] & 0x7FFF;
 758                         if ( _stateFlags[depIndex] != kStateFlagInitialized )
 759                                 continue;
 760                         if ( findInChainedTriesAndDependentsExcept(context, symbolName, depIndex, requestorImage, runResolver, alreadyVisited, address) )
 761                                 return true;
 762                 }
 763         }
 764         return false;
 765 }
 766
 767 bool ImageLoaderMegaDylib::findInChainedTriesAndDependents(const LinkContext& context, const char* symbolName, unsigned definedImageIndex,
 768                                                                                                                         const ImageLoader* requestorImage, bool runResolver, uintptr_t* address) const
 769 {
 770         //dyld::log("findInChainedTriesAndDependents(sym=%s, index=%u, path=%s)\n", symbolName, definedImageIndex, getIndexedPath(definedImageIndex));
 771         if ( findInChainedTries(context, symbolName, definedImageIndex, requestorImage, runResolver, address) )
 772                 return true;
 773
 774         bool alreadyVisited[_header->imagesCount];
 775         bzero(alreadyVisited, sizeof(alreadyVisited));
 776         return findInChainedTriesAndDependentsExcept(context, symbolName, definedImageIndex, requestorImage, runResolver, alreadyVisited, address);
 777 }
 778
 779
 780 bool ImageLoaderMegaDylib::flatFindSymbol(const char* name, bool onlyInCoalesced, const ImageLoader::Symbol** sym, const ImageLoader** image, ImageLoader::CoalesceNotifier notifier)
 781 {
 782         bool found = false;
 783         // check export trie of all in-use images
 784         for (unsigned i=0; i < _imageCount ; ++i) {
 785                 uint16_t imageIndex = _bottomUpArray[i];
 786                 if ( _stateFlags[imageIndex] == kStateUnused )
 787                         continue;
 788 #if USES_CHAINED_BINDS
 789                 const macho_header* mh = getIndexedMachHeader(imageIndex);
 790                 if ( onlyInCoalesced && (mh->flags & MH_WEAK_DEFINES) == 0 )
 791                         continue;
 792 #else
 793                 if ( onlyInCoalesced && (_imageExtras[imageIndex].weakBindingsSize == 0) )
 794                         continue;
 795 #endif
 796                 const uint8_t* exportNode;
 797                 const uint8_t* exportTrieEnd;
 798                 if ( exportTrieHasNode(name, imageIndex, &exportNode, &exportTrieEnd) ) {
 799                         if ( notifier )
 800                                 notifier((Symbol*)exportNode, this, (mach_header*)getIndexedMachHeader(imageIndex));
 801                         if ( !found ) {
 802                                 *sym = (Symbol*)exportNode;
 803                                 *image = this;
 804                                 found = true;
 805                         }
 806                         if ( !onlyInCoalesced )
 807                                 return true;
 808                 }
 809         }
 810         return found;
 811 }
 812
 813
 814 void ImageLoaderMegaDylib::markAllbound(const LinkContext& context)
 815 {
 816         for (unsigned i=0; i < _imageCount; ++i) {
 817                 uint16_t imageIndex = _bottomUpArray[i];
 818                 if ( _stateFlags[imageIndex] == kStateLoaded ) {
 819                         _stateFlags[imageIndex] = kStateFlagBound;
 820                         context.notifySingleFromCache(dyld_image_state_bound, (mach_header*)getIndexedMachHeader(imageIndex), getIndexedPath(imageIndex));
 821                 }
 822         }
 823 }
 824
 825
 826 void ImageLoaderMegaDylib::recursiveSpinLockAcquire(unsigned int imageIndex, mach_port_t thisThread)
 827 {
 828         pthread_mutex_lock(&_lockArrayGuard);
 829         if ( _lockArray == NULL )
 830                 _lockArray = (recursive_lock*)calloc(_imageCount, sizeof(recursive_lock));
 831         _lockArrayInUseCount++;
 832         pthread_mutex_unlock(&_lockArrayGuard);
 833
 834         recursive_lock* imagesLock = &_lockArray[imageIndex];
 835         while ( !OSAtomicCompareAndSwap32Barrier(0, thisThread, (int*)&imagesLock->thread) ) {
 836                 if ( imagesLock->thread == thisThread )
 837                         break;
 838         }
 839         imagesLock->count++;
 840 }
 841
 842 void ImageLoaderMegaDylib::recursiveSpinLockRelease(unsigned int imageIndex, mach_port_t thisThread)
 843 {
 844         recursive_lock* imagesLock = &_lockArray[imageIndex];
 845         if ( --imagesLock->count == 0 )
 846                 imagesLock->thread = 0;
 847
 848         pthread_mutex_lock(&_lockArrayGuard);
 849         _lockArrayInUseCount--;
 850         if ( _lockArrayInUseCount == 0 ) {
 851                 free((void*)_lockArray);
 852                 _lockArray = NULL;
 853         }
 854         pthread_mutex_unlock(&_lockArrayGuard);
 855 }
 856
 857
 858 void ImageLoaderMegaDylib::recursiveInitialization(const LinkContext& context, mach_port_t thisThread, unsigned int imageIndex,
 859                                                                                                         InitializerTimingList& timingInfo, UpwardIndexes& upInits)
 860 {
 861         // Don't do any locking until libSystem.dylib is initialized, so we can malloc() the lock array
 862         bool useLock = dyld::gProcessInfo->libSystemInitialized;
 863         if ( useLock )
 864                 recursiveSpinLockAcquire(imageIndex, thisThread);
 865
 866         // only run initializers if currently in bound state
 867         if ( (_stateFlags[imageIndex] == kStateFlagBound) || (_stateFlags[imageIndex] == kStateFlagWeakBound) ) {
 868
 869                 // Each image in cache has its own lock.  We only set the state to Initialized if we hold the lock for the image.
 870                 _stateFlags[imageIndex] = kStateFlagInitialized;
 871
 872                 // first recursively init all dependents
 873                 unsigned startArrayIndex = _imageExtras[imageIndex].dependentsStartArrayIndex;
 874                 for (int i=startArrayIndex; _dependenciesArray[i] != 0xFFFF; ++i) {
 875                         unsigned subDepIndex = _dependenciesArray[i];
 876                         // ignore upward links
 877                         if ( (subDepIndex & 0x8000) == 0 )
 878                                 recursiveInitialization(context, thisThread, subDepIndex, timingInfo, upInits);
 879             else
 880                 upInits.images[upInits.count++] = (subDepIndex & 0x7FFF);
 881                 }
 882
 883                 // notify objc about this image
 884                 context.notifySingleFromCache(dyld_image_state_dependents_initialized, (mach_header*)getIndexedMachHeader(imageIndex), getIndexedPath(imageIndex));
 885
 886                 // run all initializers for imageIndex
 887                 const dyld_cache_accelerator_initializer* pInitStart = _initializers;
 888                 const dyld_cache_accelerator_initializer* pInitEnd = &pInitStart[_initializerCount];
 889                 bool ranSomeInitializers = false;
 890                 uint64_t t1 = mach_absolute_time();
 891                 for (const dyld_cache_accelerator_initializer* p=pInitStart; p < pInitEnd; ++p) {
 892                         if ( p->imageIndex == imageIndex ) {
 893                                 Initializer func = (Initializer)(p->functionOffset + (uintptr_t)_header);
 894                                 if ( context.verboseInit )
 895                                         dyld::log("dyld: calling initializer function %p in %s\n", func, getIndexedPath(imageIndex));
 896                                 bool haveLibSystemHelpersBefore = (dyld::gLibSystemHelpers != NULL);
 897                                 {
 898                                         dyld3::ScopedTimer timer(DBG_DYLD_TIMING_STATIC_INITIALIZER, (uint64_t)getIndexedMachHeader(imageIndex), (uint64_t)func, 0);
 899                                         func(context.argc, context.argv, context.envp, context.apple, &context.programVars);
 900                                 };
 901                                 bool haveLibSystemHelpersAfter = (dyld::gLibSystemHelpers != NULL);
 902                                 ranSomeInitializers = true;
 903                                 if ( !haveLibSystemHelpersBefore && haveLibSystemHelpersAfter ) {
 904                                         // now safe to use malloc() and other calls in libSystem.dylib
 905                                         dyld::gProcessInfo->libSystemInitialized = true;
 906                                 }
 907                         }
 908                 }
 909                 if ( ranSomeInitializers ) {
 910                         uint64_t t2 = mach_absolute_time();
 911                         const char* shortName = strrchr(getIndexedPath(imageIndex), '/');
 912                         if ( shortName == NULL )
 913                                 shortName = getIndexedPath(imageIndex);
 914                         else
 915                                 ++shortName;
 916                         timingInfo.images[timingInfo.count].shortName = shortName;
 917                         timingInfo.images[timingInfo.count].initTime = (t2-t1);
 918                         timingInfo.count++;
 919                 }
 920         }
 921
 922         // only unlock if this frame locked (note: libSystemInitialized changes after libSystem's initializer is run)
 923         if ( useLock )
 924                 recursiveSpinLockRelease(imageIndex, thisThread);
 925 }
 926
 927
 928 void ImageLoaderMegaDylib::recursiveInitialization(const LinkContext& context, mach_port_t thisThread, const char* pathToInitialize,
 929                                                                                                         InitializerTimingList& timingInfo, UninitedUpwards&)
 930 {
 931         unsigned imageIndex;
 932         if ( hasDylib(pathToInitialize, &imageIndex) ) {
 933                 UpwardIndexes upsBuffer[256];
 934                 UpwardIndexes& ups = upsBuffer[0];
 935                 ups.count = 0;
 936                 this->recursiveInitialization(context, thisThread, imageIndex, timingInfo, ups);
 937                 for (int i=0; i < ups.count; ++i) {
 938                         UpwardIndexes upsBuffer2[256];
 939                         UpwardIndexes& ignoreUp = upsBuffer2[0];
 940                         ignoreUp.count = 0;
 941                         this->recursiveInitialization(context, thisThread, ups.images[i], timingInfo, ignoreUp);
 942                 }
 943         }
 944 }
 945
 946 void ImageLoaderMegaDylib::recursiveBind(const LinkContext& context, bool forceLazysBound, bool neverUnload)
 947 {
 948         markAllbound(context);
 949 }
 950
 951 uint8_t ImageLoaderMegaDylib::dyldStateToCacheState(dyld_image_states state) {
 952         switch (state) {
 953                 case dyld_image_state_mapped:
 954                 case dyld_image_state_dependents_mapped:
 955                         return kStateLoaded;
 956                 case dyld_image_state_bound:
 957                         return kStateFlagBound;
 958                 case dyld_image_state_initialized:
 959                         return kStateFlagInitialized;
 960                 case dyld_image_state_rebased:
 961                 case dyld_image_state_dependents_initialized:
 962                 case dyld_image_state_terminated:
 963                         return kStateUnused;
 964         }
 965         return kStateUnused;
 966 }
 967
 968 void ImageLoaderMegaDylib::recursiveApplyInterposing(const LinkContext& context)
 969 {
 970         if ( context.verboseInterposing )
 971                 dyld::log("dyld: interposing %lu tuples onto shared cache\n", fgInterposingTuples.size());
 972
 973
 974 }
 975
 976 unsigned ImageLoaderMegaDylib::appendImagesToNotify(dyld_image_states state, bool orLater, dyld_image_info* infos)
 977 {
 978         uint8_t targetCacheState = dyldStateToCacheState(state);
 979         if ( targetCacheState == kStateUnused )
 980                 return 0;
 981         unsigned usedCount = 0;
 982         for (int i=_imageCount-1; i >= 0; --i) {
 983                 uint16_t index = _bottomUpArray[i];
 984                 uint8_t imageState = _stateFlags[index];
 985                 if ( imageState == kStateFlagWeakBound )
 986                         imageState = kStateFlagBound;
 987                 if ( (imageState == targetCacheState) || (orLater && (imageState > targetCacheState)) ) {
 988                         infos[usedCount].imageLoadAddress       = (mach_header*)getIndexedMachHeader(index);
 989                         infos[usedCount].imageFilePath          = getIndexedPath(index);
 990                         infos[usedCount].imageFileModDate       = 0;
 991                         ++usedCount;
 992                 }
 993         }
 994         return usedCount;
 995 }
 996
 997
 998 bool ImageLoaderMegaDylib::dlopenFromCache(const LinkContext& context, const char* path, int mode, void** handle)
 999 {
1000         unsigned imageIndex;
1001         if ( !hasDylib(path, &imageIndex) ) {
1002                 return false;
1003         }
1004
1005         // RTLD_NOLOAD means return handle if already loaded, but don't now load it
1006         if ( mode & RTLD_NOLOAD ) {
1007                 dyld::gLibSystemHelpers->releaseGlobalDyldLock();
1008                 if ( _stateFlags[imageIndex] == kStateUnused ) {
1009                         *handle = NULL;
1010                         return true;
1011                 }
1012         }
1013         else {
1014                 this->recursiveMarkLoaded(context, imageIndex);
1015                 context.notifyBatch(dyld_image_state_dependents_mapped, false);
1016                 this->markAllbound(context);
1017                 context.notifyBatch(dyld_image_state_bound, false);
1018
1019                 this->weakBind(context);
1020
1021                 // <rdar://problem/25069046> Release dyld global lock before running initializers in dlopen() with customer cache
1022                 dyld::gLibSystemHelpers->releaseGlobalDyldLock();
1023
1024                 InitializerTimingList timingInfo[_initializerCount];
1025                 timingInfo[0].count = 0;
1026                 mach_port_t thisThread  = mach_thread_self();
1027                 UpwardIndexes upsBuffer[256];  // room for 511 dangling upward links
1028                 UpwardIndexes& ups = upsBuffer[0];
1029                 ups.count = 0;
1030                 this->recursiveInitialization(context, thisThread, imageIndex, timingInfo[0], ups);
1031                 // make sure any upward linked dylibs were initialized
1032                 for (int i=0; i < ups.count; ++i) {
1033                         UpwardIndexes upsBuffer2[256];
1034                         UpwardIndexes& ignoreUp = upsBuffer2[0];
1035                         ignoreUp.count = 0;
1036                         this->recursiveInitialization(context, thisThread, ups.images[i], timingInfo[0], ignoreUp);
1037                 }
1038                 mach_port_deallocate(mach_task_self(), thisThread);
1039                 context.notifyBatch(dyld_image_state_initialized, false);
1040         }
1041
1042         *handle = makeCacheHandle(imageIndex, mode);
1043         return true;
1044 }
1045
1046 bool ImageLoaderMegaDylib::makeCacheHandle(const LinkContext& context, unsigned cacheIndex, int mode, void** result)
1047 {
1048         if ( cacheIndex >= _imageCount )
1049                 return false;
1050
1051         *result = makeCacheHandle(cacheIndex, mode);
1052         return true;
1053 }
1054
1055 void* ImageLoaderMegaDylib::makeCacheHandle(unsigned index, int mode)
1056 {
1057         uint8_t flags = ((mode & RTLD_FIRST) ? 1 : 0);
1058
1059 #if __LP64__
1060         return (void*)(uintptr_t)( 0xFFEEDDCC00000000LL | (index << 8) | flags);
1061 #else
1062         return (void*)(uintptr_t)( 0xF8000000 | (index << 8) | flags);
1063 #endif
1064 }
1065
1066 bool ImageLoaderMegaDylib::isCacheHandle(void* handle, unsigned* index, uint8_t* flags)
1067 {
1068 #if __LP64__
1069         if ( (((uintptr_t)handle) >> 32) == 0xFFEEDDCC ) {
1070                 if ( index )
1071                         *index = (((uintptr_t)handle) >> 8) & 0xFFFF;
1072                 if ( flags )
1073                         *flags = ((uintptr_t)handle) & 0xFF;
1074                 return true;
1075         }
1076 #else
1077         if ( (((uintptr_t)handle) >> 24) == 0xF8 ) {
1078                 if ( index )
1079                         *index = (((uintptr_t)handle) >> 8) & 0xFFFF;
1080                 if ( flags )
1081                         *flags = ((uintptr_t)handle) & 0xFF;
1082                 return true;
1083         }
1084 #endif
1085         return false;
1086 }
1087
1088
1089 void* ImageLoaderMegaDylib::dlsymFromCache(const LinkContext& context, void* handle, const char* symbolName, unsigned imageIndex)
1090 {
1091         unsigned indexInHandle;
1092         uint8_t flags;
1093         uintptr_t symAddress;
1094         if ( handle == RTLD_SELF ) {
1095                 if ( findInChainedTriesAndDependents(context, symbolName, imageIndex, NULL, true, &symAddress) )
1096                         return (void*)symAddress;
1097         }
1098         else if ( handle == RTLD_NEXT ) {
1099                 // FIXME: really need to not look in imageIndex, but look in others.
1100                 if ( findInChainedTriesAndDependents(context, symbolName, imageIndex, NULL, true, &symAddress) )
1101                         return (void*)symAddress;
1102         }
1103         else if ( isCacheHandle(handle, &indexInHandle, &flags) ) {
1104                 bool searchOnlyFirst = (flags & 1);  // RTLD_FIRST
1105                 // normal dlsym(handle,) semantics is that the handle is just the first place to search. RTLD_FIRST disables that
1106                 if ( searchOnlyFirst ) {
1107                         if ( findInChainedTries(context, symbolName, indexInHandle, NULL, true, &symAddress) )
1108                                 return (void*)symAddress;
1109                 }
1110                 else {
1111                         if ( findInChainedTriesAndDependents(context, symbolName, indexInHandle, NULL, true, &symAddress) )
1112                                 return (void*)symAddress;
1113                 }
1114         }
1115
1116         return NULL;
1117 }
1118
1119 bool ImageLoaderMegaDylib::dladdrFromCache(const void* address, Dl_info* info)
1120 {
1121         const mach_header* mh;
1122         unsigned index;
1123         if ( !addressInCache(address, &mh, &info->dli_fname, &index) )
1124                 return false;
1125
1126         info->dli_fbase = (void*)mh;
1127         if ( address == mh ) {
1128                 // special case lookup of header
1129                 info->dli_sname = "__dso_handle";
1130                 info->dli_saddr = info->dli_fbase;
1131                 return true;
1132         }
1133
1134         // find closest symbol in the image
1135         info->dli_sname = ImageLoaderMachO::findClosestSymbol(mh, address, (const void**)&info->dli_saddr);
1136
1137         // never return the mach_header symbol
1138         if ( info->dli_saddr == info->dli_fbase ) {
1139                 info->dli_sname = NULL;
1140                 info->dli_saddr = NULL;
1141                 return true;
1142         }
1143
1144         // strip off leading underscore
1145         if ( info->dli_sname != NULL ) {
1146                 if ( info->dli_sname[0] == '_' )
1147                         info->dli_sname = info->dli_sname +1;
1148         }
1149         return true;
1150 }
1151
1152
1153 uintptr_t ImageLoaderMegaDylib::bindLazy(uintptr_t lazyBindingInfoOffset, const LinkContext& context, const mach_header* mh, unsigned imageIndex)
1154 {
1155         const dyld_info_command* dyldInfoCmd = ImageLoaderMachO::findDyldInfoLoadCommand(mh);
1156         if ( dyldInfoCmd == NULL )
1157                 return 0;
1158
1159         const uint8_t* const lazyInfoStart = &_linkEditBias[dyldInfoCmd->lazy_bind_off];
1160         const uint8_t* const lazyInfoEnd = &lazyInfoStart[dyldInfoCmd->lazy_bind_size];
1161         uint32_t lbOffset = (uint32_t)lazyBindingInfoOffset;
1162         uint8_t segIndex;
1163         uintptr_t segOffset;
1164         int libraryOrdinal;
1165         const char* symbolName;
1166         bool doneAfterBind;
1167         if ( ImageLoaderMachO::getLazyBindingInfo(lbOffset, lazyInfoStart, lazyInfoEnd, &segIndex, &segOffset, &libraryOrdinal, &symbolName, &doneAfterBind) ) {
1168                 //const char* thisPath = getIndexedPath(imageIndex);
1169                 //dyld::log("%s needs symbol '%s' from ordinal=%d\n", thisPath, symbolName, libraryOrdinal);
1170                 unsigned startDepArrayIndex = _imageExtras[imageIndex].dependentsStartArrayIndex;
1171                 unsigned targetIndex;
1172                 if ( libraryOrdinal == BIND_SPECIAL_DYLIB_SELF )
1173                         targetIndex = imageIndex;
1174                 else
1175                         targetIndex = _dependenciesArray[startDepArrayIndex+libraryOrdinal-1] & 0x7FFF;
1176                 //const char* targetPath = getIndexedPath(targetIndex);
1177                 //dyld::log("%s needs symbol '%s' from %s\n", thisPath, symbolName, targetPath);
1178                 uintptr_t targetAddress;
1179                 if ( findInChainedTries(context, symbolName, targetIndex, this, true, &targetAddress) ) {
1180                         if ( uintptr_t segPrefAddress = ImageLoaderMachO::segPreferredAddress(mh, segIndex) ) {
1181                                 uintptr_t* lp = (uintptr_t*)(segPrefAddress + segOffset + _slide);
1182                                 //dyld::log("    storing 0x%0lX to lp %p\n", targetAddress, lp);
1183                                 *lp = targetAddress;
1184                                 return targetAddress;
1185                         }
1186                 }
1187         }
1188
1189         return 0;
1190 }
1191
1192
1193 #endif // SUPPORT_ACCELERATE_TABLES
1194
1195
1196