dyld-732.8.tar.gz

[apple/dyld.git] / src / ImageLoaderMegaDylib.cpp

/* -*- mode: C++; c-basic-offset: 4; tab-width: 4 -*-
 *
 * Copyright (c) 2015 Apple Inc. All rights reserved.
 *
 * @APPLE_LICENSE_HEADER_START@
 * 
 * This file contains Original Code and/or Modifications of Original Code
 * as defined in and that are subject to the Apple Public Source License
 * Version 2.0 (the 'License'). You may not use this file except in
 * compliance with the License. Please obtain a copy of the License at
 * http://www.opensource.apple.com/apsl/ and read it before using this
 * file.
 * 
 * The Original Code and all software distributed under the License are
 * distributed on an 'AS IS' basis, WITHOUT WARRANTY OF ANY KIND, EITHER
 * EXPRESS OR IMPLIED, AND APPLE HEREBY DISCLAIMS ALL SUCH WARRANTIES,
 * INCLUDING WITHOUT LIMITATION, ANY WARRANTIES OF MERCHANTABILITY,
 * FITNESS FOR A PARTICULAR PURPOSE, QUIET ENJOYMENT OR NON-INFRINGEMENT.
 * Please see the License for the specific language governing rights and
 * limitations under the License.
 * 
 * @APPLE_LICENSE_HEADER_END@
 */


#if __arm__ || __arm64__
  #include <System/sys/mman.h>
#else
  #include <sys/mman.h>
#endif
#include <string.h>
#include <dlfcn.h>
#include <fcntl.h>
#include <errno.h>
#include <sys/types.h>
#include <sys/fcntl.h>
#include <sys/stat.h> 
#include <sys/param.h>
#include <mach/mach.h>
#include <mach/thread_status.h>
#include <mach-o/loader.h> 
#include <mach-o/dyld_images.h>
#include <libkern/OSAtomic.h>

#include "ImageLoaderMegaDylib.h"
#include "ImageLoaderMachO.h"
#include "dyldLibSystemInterface.h"
#include "Tracing.h"
#include "dyld2.h"

// from dyld_gdb.cpp 
extern void addImagesToAllImages(uint32_t infoCount, const dyld_image_info info[]);

extern "C" int _dyld_func_lookup(const char* name, void** address);


#ifndef EXPORT_SYMBOL_FLAGS_KIND_ABSOLUTE
        #define EXPORT_SYMBOL_FLAGS_KIND_ABSOLUTE                       0x02
#endif

// relocation_info.r_length field has value 3 for 64-bit executables and value 2 for 32-bit executables
#if __LP64__
        #define RELOC_SIZE 3
        #define LC_SEGMENT_COMMAND              LC_SEGMENT_64
        #define LC_ROUTINES_COMMAND             LC_ROUTINES_64
        struct macho_segment_command    : public segment_command_64  {};
        struct macho_section                    : public section_64  {};        
        struct macho_routines_command   : public routines_command_64  {};       
#else
        #define RELOC_SIZE 2
        #define LC_SEGMENT_COMMAND              LC_SEGMENT
        #define LC_ROUTINES_COMMAND             LC_ROUTINES
        struct macho_segment_command    : public segment_command {};
        struct macho_section                    : public section  {};   
        struct macho_routines_command   : public routines_command  {};  
#endif



#if SUPPORT_ACCELERATE_TABLES
 

ImageLoaderMegaDylib* ImageLoaderMegaDylib::makeImageLoaderMegaDylib(const dyld_cache_header* header, long slide, const macho_header* mainMH, const LinkContext& context)
{
        return new ImageLoaderMegaDylib(header, slide, mainMH, context);
}

struct DATAdyld {
        void*                   dyldLazyBinder;         // filled in at launch by dyld to point into dyld to &stub_binding_helper
        void*                   dyldFuncLookup;         // filled in at launch by dyld to point into dyld to &_dyld_func_lookup
        ProgramVars             vars;
};




ImageLoaderMegaDylib::ImageLoaderMegaDylib(const dyld_cache_header* header, long slide, const macho_header* mainMH, const LinkContext& context)
        : ImageLoader("dyld shared cache", 0), _header(header), _linkEditBias(NULL), _slide(slide),
         _lockArray(NULL), _lockArrayInUseCount(0)
{
        pthread_mutex_init(&_lockArrayGuard, NULL);
        const dyld_cache_mapping_info* mappings = (const dyld_cache_mapping_info*)((uint8_t*)_header + _header->mappingOffset);
        const dyld_cache_mapping_info* lastMapping = &mappings[_header->mappingCount-1];
        const dyld_cache_accelerator_info* accHeader = (dyld_cache_accelerator_info*)(_header->accelerateInfoAddr + slide);
        for (const dyld_cache_mapping_info* m=mappings; m <= lastMapping; ++m) {
                if ( m->initProt == VM_PROT_READ ) {
                        _linkEditBias = (uint8_t*)(m->address - m->fileOffset) + _slide;
                }
        }

        _endOfCacheInMemory = (void*)(lastMapping->address + lastMapping->size + slide);
        _images = (const dyld_cache_image_info*)((uint8_t*)_header + _header->imagesOffset);
        _imageExtras = (dyld_cache_image_info_extra*)((char*)accHeader + accHeader->imagesExtrasOffset);
        _initializers = (dyld_cache_accelerator_initializer*)((char*)accHeader + accHeader->initializersOffset);
        _reExportsArray = (uint16_t*)((char*)accHeader + accHeader->reExportListOffset);
        _dependenciesArray = (uint16_t*)((char*)accHeader + accHeader->depListOffset);
        _bottomUpArray = (uint16_t*)((char*)accHeader + accHeader->bottomUpListOffset);
        _rangeTable = (dyld_cache_range_entry*)((char*)accHeader + accHeader->rangeTableOffset);
        _rangeTableCount = accHeader->rangeTableCount;
        _imageCount = accHeader->imageExtrasCount;
        _stateFlags = (uint8_t*)calloc(_imageCount, 1);
        _initializerCount = accHeader->initializersCount;
        _dylibsTrieStart = (uint8_t*)accHeader + accHeader->dylibTrieOffset;
        _dylibsTrieEnd = _dylibsTrieStart + accHeader->dylibTrieSize;
        _imageTextInfo = (dyld_cache_image_text_info*)((uint8_t*)_header + _header->imagesTextOffset);
        DATAdyld* dyldSection = (DATAdyld*)(accHeader->dyldSectionAddr + slide);
        dyldSection->dyldLazyBinder = NULL; // not used by libdyld.dylib
        dyldSection->dyldFuncLookup = (void*)&_dyld_func_lookup;
        dyldSection->vars.mh = mainMH;
        context.setNewProgramVars(dyldSection->vars);
}


void ImageLoaderMegaDylib::unreachable() const
{
        abort();
}

ImageLoaderMegaDylib::~ImageLoaderMegaDylib()
{
}

const char*     ImageLoaderMegaDylib::getInstallPath() const {
        unreachable();
}

const macho_header* ImageLoaderMegaDylib::getIndexedMachHeader(unsigned index) const
{
        if ( index > _header->imagesCount )
                dyld::throwf("cache image index out of range (%u), max=%u", index, _header->imagesCount - 1);
        return (const macho_header*)(_images[index].address + _slide);
}

const char* ImageLoaderMegaDylib::getIndexedPath(unsigned index) const
{
        if ( index > _header->imagesCount )
                dyld::throwf("cache image index out of range (%u), max=%u", index, _header->imagesCount - 1);
        return (char*)_header + _images[index].pathFileOffset;
}

const char* ImageLoaderMegaDylib::getIndexedShortName(unsigned index) const
{
        const char* path = getIndexedPath(index);
        const char* lastSlash = strrchr(path, '/');
        if ( lastSlash == NULL )
                return path;
        else
                return lastSlash+1;
}

void ImageLoaderMegaDylib::getDylibUUID(unsigned int index, uuid_t uuid) const
{
        if ( index > _header->imagesCount )
                dyld::throwf("cache image index out of range (%u), max=%u", index, _header->imagesCount - 1);
        memcpy(uuid, _imageTextInfo[index].uuid, 16);
}

void ImageLoaderMegaDylib::printSegments(const macho_header* mh) const
{
        const uint32_t cmd_count = mh->ncmds;
        const struct load_command* const cmds = (struct load_command*)((uint8_t*)mh + sizeof(macho_header));
        const struct load_command* cmd = cmds;
        const macho_segment_command* seg;
        for (uint32_t i = 0; i < cmd_count; ++i) {
                switch (cmd->cmd) {
                        case LC_SEGMENT_COMMAND:
                                seg = (macho_segment_command*)cmd;
                                dyld::log("%18s at 0x%08lX->0x%08lX\n", seg->segname, (long)(seg->vmaddr + _slide), (long)(seg->vmaddr + seg->vmsize + _slide));
                                break;
                }
                cmd = (const struct load_command*)(((char*)cmd)+cmd->cmdsize);
        }
}

bool ImageLoaderMegaDylib::hasDylib(const char* path, unsigned* index) const
{
        const uint8_t* imageNode = ImageLoader::trieWalk(_dylibsTrieStart, _dylibsTrieEnd, path);
        if ( imageNode == NULL ) {
  #if __MAC_OS_X_VERSION_MIN_REQUIRED
                // not all symlinks are recorded as aliases in accelerator tables
                if ( (strncmp(path, "/usr/lib/", 9) == 0) || (strncmp(path, "/System/Library/", 16) == 0) ) {
                        char resolvedPath[PATH_MAX];
                        if ( realpath(path, resolvedPath) != NULL ) {
                                imageNode = ImageLoader::trieWalk(_dylibsTrieStart, _dylibsTrieEnd, resolvedPath);
                        }
                }
                if ( imageNode == NULL )
                        return false;
  #else
                return false;
  #endif
        }
        *index = (unsigned)read_uleb128(imageNode, _dylibsTrieEnd);
        return true;
}

bool ImageLoaderMegaDylib::addressInCache(const void* address, const mach_header** mh, const char** path, unsigned* index)
{
        // quick out of bounds check
#if __x86_64__
        if ( (uintptr_t)address < 0x7FFF70000000LL )
                return false;
#else
        if ( address < (void*)_header )
                return false;
#endif
        if ( address > _endOfCacheInMemory )
                return false;

        uint64_t unslidAddress = (uint64_t)address - _slide;
        // linear search for now
        const dyld_cache_range_entry* rangeTableEnd = &_rangeTable[_rangeTableCount];
        for (const dyld_cache_range_entry* r = _rangeTable; r < rangeTableEnd; ++r) {
                if ( (r->startAddress <= unslidAddress) && (unslidAddress < r->startAddress+r->size) ) {
                        *index = r->imageIndex;
                        *mh = (mach_header*)getIndexedMachHeader(r->imageIndex);
                        *path = getIndexedPath(r->imageIndex);
                        return true;
                }
        }

        return false;
}


bool ImageLoaderMegaDylib::findUnwindSections(const void* address, dyld_unwind_sections* info)
{
        const char* path;
        unsigned index;
        if ( addressInCache(address, &info->mh, &path, &index) ) {
                info->dwarf_section = NULL;
                info->dwarf_section_length = 0;
                ImageLoaderMachO::findSection(info->mh, "__TEXT", "__eh_frame", (void**)&info->dwarf_section, &info->dwarf_section_length);

                info->compact_unwind_section = NULL;
                info->compact_unwind_section_length = 0;
                ImageLoaderMachO::findSection(info->mh, "__TEXT", "__unwind_info", (void**)&info->compact_unwind_section, &info->compact_unwind_section_length);

                return true;
        }
        return false;
}


unsigned ImageLoaderMegaDylib::findImageIndex(const LinkContext& context, const char* path) const
{
        unsigned index;
        if ( hasDylib(path, &index) )
                return index;

        if ( strncmp(path, "@rpath/libswift", 15) == 0 ) {
                // <rdar://problem/51352017> a stable swift app built to run on pre-iOS-12.2 will use @rpath to reference swift dylibs in OS
                const char* trailingPath = &path[7];
                char possiblePath[strlen(trailingPath)+16];
                strcpy(possiblePath, "/usr/lib/swift/");
                strcat(possiblePath, trailingPath);
                if ( hasDylib(possiblePath, &index) )
                        return index;
        }
        else if ( strncmp(path, "@rpath/", 7) == 0 ) {
                // <rdar://problem/26934069> Somehow we found the dylib in the cache, but it is not this literal string, try simple expansions of @rpath
                std::vector<const char*> rpathsFromMainExecutable;
                context.mainExecutable->getRPaths(context, rpathsFromMainExecutable);
                rpathsFromMainExecutable.push_back("/System/Library/Frameworks/");
                rpathsFromMainExecutable.push_back("/usr/lib/swift/");
                const char* trailingPath = &path[7];
                for (const char* anRPath : rpathsFromMainExecutable) {
                        if ( anRPath[0] != '/' )
                                continue;
                        char possiblePath[strlen(anRPath) + strlen(trailingPath)+2];
                        strcpy(possiblePath, anRPath);
                        if ( possiblePath[strlen(possiblePath)-1] != '/' )
                                strcat(possiblePath, "/");
                        strcat(possiblePath, trailingPath);
                        if ( hasDylib(possiblePath, &index) ) {
                                return index;
                        }
                }
        }
    else {
        // handle symlinks embedded in load commands
        char resolvedPath[PATH_MAX];
        realpath(path, resolvedPath);
        int realpathErrno = errno;
        // If realpath() resolves to a path which does not exist on disk, errno is set to ENOENT
        if ( (realpathErrno == ENOENT) || (realpathErrno == 0) ) {
            if ( strcmp(resolvedPath, path) != 0 )
                return findImageIndex(context, resolvedPath);
        }
    }

        dyld::throwf("no cache image with name (%s)", path);
}

void ImageLoaderMegaDylib::initializeCoalIterator(CoalIterator& it, unsigned int loadOrder, unsigned imageIndex)
{
        it.image = this;
        it.symbolName = " ";
        it.loadOrder = loadOrder;
        it.weakSymbol = false;
        it.symbolMatches = false;
        it.done = false;
        it.curIndex = 0;
        it.endIndex = _imageExtras[imageIndex].weakBindingsSize;
        it.address = 0;
        it.type = 0;
        it.addend = 0;
        it.imageIndex = imageIndex;
}

bool ImageLoaderMegaDylib::incrementCoalIterator(CoalIterator& it)
{
        if ( it.done )
                return false;
                
        if ( _imageExtras[it.imageIndex].weakBindingsSize == 0 ) {
                /// hmmm, ld set MH_WEAK_DEFINES or MH_BINDS_TO_WEAK, but there is no weak binding info
                it.done = true;
                it.symbolName = "~~~";
                return true;
        }
        const uint8_t* start = (uint8_t*)(_imageExtras[it.imageIndex].weakBindingsAddr + _slide);
        const uint8_t* end = (uint8_t*)(_imageExtras[it.imageIndex].weakBindingsAddr + _slide + _imageExtras[it.imageIndex].weakBindingsSize);
        const uint8_t* p = start + it.curIndex;
        uintptr_t count;
        uintptr_t skip;
        uint64_t segOffset;
        unsigned segIndex;
        const mach_header* mh;
        while ( p < end ) {
                uint8_t immediate = *p & BIND_IMMEDIATE_MASK;
                uint8_t opcode = *p & BIND_OPCODE_MASK;
                ++p;
                switch (opcode) {
                        case BIND_OPCODE_DONE:
                                it.done = true;
                                it.curIndex = p - start;
                                it.symbolName = "~~~"; // sorts to end
                                return true;
                        case BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM:
                                it.symbolName = (char*)p;
                                it.weakSymbol = ((immediate & BIND_SYMBOL_FLAGS_NON_WEAK_DEFINITION) == 0);
                                it.symbolMatches = false;
                                while (*p != '\0')
                                        ++p;
                                ++p;
                                it.curIndex = p - start;
                                return false;
                        case BIND_OPCODE_SET_TYPE_IMM:
                                it.type = immediate;
                                break;
                        case BIND_OPCODE_SET_ADDEND_SLEB:
                                it.addend = read_sleb128(p, end);
                                break;
                        case BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB:
                                segIndex = immediate;
                                segOffset = read_uleb128(p, end);
                                mh = (mach_header*)getIndexedMachHeader((unsigned)it.imageIndex);
                                if ( uintptr_t segPrefAddress = ImageLoaderMachO::segPreferredAddress(mh, segIndex) )
                                        it.address = segPrefAddress + (uintptr_t)segOffset + _slide;
                                else
                                        dyld::throwf("BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB has segment %d which is too large", segIndex);
                                break;
                        case BIND_OPCODE_ADD_ADDR_ULEB:
                                it.address += read_uleb128(p, end);
                                break;
                        case BIND_OPCODE_DO_BIND:
                                it.address += sizeof(intptr_t);
                                break;
                        case BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB:
                                it.address += read_uleb128(p, end) + sizeof(intptr_t);
                                break;
                        case BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED:
                                it.address += immediate*sizeof(intptr_t) + sizeof(intptr_t);
                                break;
                        case BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB:
                                count = read_uleb128(p, end);
                                skip = read_uleb128(p, end);
                                for (uint32_t i=0; i < count; ++i) {
                                        it.address += skip + sizeof(intptr_t);
                                }
                                break;
                        default:
                                dyld::throwf("bad weak bind opcode '%d' found after processing %d bytes in '%s'", *p, (int)(p-start), this->getPath());
                }
        }
        /// hmmm, BIND_OPCODE_DONE is missing...
        it.done = true;
        it.symbolName = "~~~";
        //dyld::log("missing BIND_OPCODE_DONE for image %s\n", this->getPath());
        return true;
}

uintptr_t ImageLoaderMegaDylib::getAddressCoalIterator(CoalIterator& it, const LinkContext& context)
{
        //dyld::log("looking for %s in %s\n", it.symbolName, this->getPath());
        uintptr_t address;
        if ( findInChainedTries(context, it.symbolName, (unsigned)it.imageIndex, NULL, false, &address) ) {
                return address;
        }
        return 0;
}

void ImageLoaderMegaDylib::updateUsesCoalIterator(CoalIterator& it, uintptr_t value, ImageLoader* targetImage, unsigned targetIndex, const LinkContext& context)
{

        const uint8_t* start = (uint8_t*)(_imageExtras[it.imageIndex].weakBindingsAddr + _slide);
        const uint8_t* end = (uint8_t*)(_imageExtras[it.imageIndex].weakBindingsAddr + _slide + _imageExtras[it.imageIndex].weakBindingsSize);
        const uint8_t* p = start + it.curIndex;

        uint8_t type = it.type;
        uintptr_t address = it.address;
        const char* symbolName = it.symbolName;
        intptr_t addend = it.addend;
        uint64_t segOffset;
        unsigned segIndex;
        const mach_header* mh;
        uintptr_t count;
        uintptr_t skip;
        bool done = false;
        bool boundSomething = false;
        const char* targetImagePath = targetImage ? targetImage->getIndexedPath(targetIndex) : NULL;
        while ( !done && (p < end) ) {
                uint8_t immediate = *p & BIND_IMMEDIATE_MASK;
                uint8_t opcode = *p & BIND_OPCODE_MASK;
                ++p;
                switch (opcode) {
                        case BIND_OPCODE_DONE:
                                done = true;
                                break;
                        case BIND_OPCODE_SET_SYMBOL_TRAILING_FLAGS_IMM:
                                done = true;
                                break;
                        case BIND_OPCODE_SET_TYPE_IMM:
                                type = immediate;
                                break;
                        case BIND_OPCODE_SET_ADDEND_SLEB:
                                addend = read_sleb128(p, end);
                                break;
                        case BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB:
                                segIndex = immediate;
                                segOffset = read_uleb128(p, end);
                                mh = (mach_header*)getIndexedMachHeader((unsigned)it.imageIndex);
                                if ( uintptr_t segPrefAddress = ImageLoaderMachO::segPreferredAddress(mh, segIndex) )
                                        address = segPrefAddress + (uintptr_t)segOffset + _slide;
                                else
                                        dyld::throwf("BIND_OPCODE_SET_SEGMENT_AND_OFFSET_ULEB has segment %d which is too large", segIndex);
                                break;
                        case BIND_OPCODE_ADD_ADDR_ULEB:
                                address += read_uleb128(p, end);
                                break;
                        case BIND_OPCODE_DO_BIND:
                                ImageLoaderMachO::bindLocation(context, 0, address, value, type, symbolName, addend, getIndexedPath((unsigned)it.imageIndex), targetImagePath, "weak ", NULL, _slide);
                                boundSomething = true;
                                address += sizeof(intptr_t);
                                break;
                        case BIND_OPCODE_DO_BIND_ADD_ADDR_ULEB:
                                ImageLoaderMachO::bindLocation(context, 0, address, value, type, symbolName, addend, getIndexedPath((unsigned)it.imageIndex), targetImagePath, "weak ", NULL, _slide);
                                boundSomething = true;
                                address += read_uleb128(p, end) + sizeof(intptr_t);
                                break;
                        case BIND_OPCODE_DO_BIND_ADD_ADDR_IMM_SCALED:
                                ImageLoaderMachO::bindLocation(context, 0, address, value, type, symbolName, addend, getIndexedPath((unsigned)it.imageIndex), targetImagePath, "weak ", NULL, _slide);
                                boundSomething = true;
                                address += immediate*sizeof(intptr_t) + sizeof(intptr_t);
                                break;
                        case BIND_OPCODE_DO_BIND_ULEB_TIMES_SKIPPING_ULEB:
                                count = read_uleb128(p, end);
                                skip = read_uleb128(p, end);
                                for (uint32_t i=0; i < count; ++i) {
                                        ImageLoaderMachO::bindLocation(context, 0, address, value, type, symbolName, addend, getIndexedPath((unsigned)it.imageIndex), targetImagePath, "weak ", NULL, _slide);
                                        boundSomething = true;
                                        address += skip + sizeof(intptr_t);
                                }
                                break;
                        default:
                                dyld::throwf("bad bind opcode %d in weak binding info", *p);
                }
        }
        // C++ weak coalescing cannot be tracked by reference counting.  Error on side of never unloading.
        if ( boundSomething && (targetImage != this) )
                context.addDynamicReference(this, targetImage);
}


void ImageLoaderMegaDylib::appendImagesNeedingCoalescing(ImageLoader* images[], unsigned imageIndexes[], unsigned& count)
{
        for (unsigned i=0; i < _imageCount; ++i) {
                uint16_t index = _bottomUpArray[i];
                if ( _stateFlags[index] == kStateUnused )
                        continue;
                if ( _imageExtras[index].weakBindingsSize == 0 )
                        continue;
                images[count] = this;
                imageIndexes[count] = index;
                ++count;
        }
}


bool ImageLoaderMegaDylib::weakSymbolsBound(unsigned index)
{
        return ( _stateFlags[index] >= kStateFlagWeakBound );
}

void ImageLoaderMegaDylib::setWeakSymbolsBound(unsigned index)
{
        if ( _stateFlags[index] == kStateFlagBound )
                _stateFlags[index] = kStateFlagWeakBound;
}


void ImageLoaderMegaDylib::recursiveMarkLoaded(const LinkContext& context, unsigned imageIndex)
{
        if ( _stateFlags[imageIndex] != kStateUnused )
                return;

        const macho_header* mh = getIndexedMachHeader(imageIndex);
        const char* path = getIndexedPath(imageIndex);

        if ( context.verboseLoading )
                dyld::log("dyld: loaded: %s\n", path);
        if ( context.verboseMapping ) {
                dyld::log("dyld: Using shared cached for %s\n", path);
                printSegments(mh);
        }
        
        // change state to "loaded" before recursing to break cycles
        _stateFlags[imageIndex] = kStateLoaded;
        ++fgImagesUsedFromSharedCache;

        dyld_image_info debuggerInfo;
        debuggerInfo.imageLoadAddress = (mach_header*)mh;
        debuggerInfo.imageFilePath = path;
        debuggerInfo.imageFileModDate = 0;
        addImagesToAllImages(1, &debuggerInfo);

        if ( _imageExtras[imageIndex].weakBindingsSize != 0 ) {
                ++fgImagesRequiringCoalescing;
                ++fgImagesHasWeakDefinitions;
        }

        unsigned startArrayIndex = _imageExtras[imageIndex].dependentsStartArrayIndex;
        for (int i=startArrayIndex; _dependenciesArray[i] != 0xFFFF; ++i) {
                unsigned subDep = (_dependenciesArray[i] & 0x7FFF); // mask off upward bit
                recursiveMarkLoaded(context, subDep);
        }
}

void ImageLoaderMegaDylib::recursiveLoadLibraries(const LinkContext& context, bool preflightOnly, const RPathChain& loaderRPaths, const char* loadPath)
{
        unsigned index = findImageIndex(context, loadPath);
        recursiveMarkLoaded(context, index);
}

unsigned int ImageLoaderMegaDylib::recursiveUpdateDepth(unsigned int maxDepth)
{
        setDepth(maxDepth);
        return maxDepth;
}


const ImageLoader::Symbol* ImageLoaderMegaDylib::findExportedSymbol(const char* name, bool searchReExports, const char* thisPath, const ImageLoader** foundIn) const
{
        unsigned index;
        if ( !hasDylib(thisPath, &index) )
                return NULL;
        const uint8_t* exportNode;
        const uint8_t* exportTrieEnd;
        unsigned foundinIndex;
        // <rdar://problem/22068598> always search re-exports
        // the point of searchReExports was to break cycles in dylibs, we don't have cycles in cache, so ok to search deep
        searchReExports = true;
        if ( searchReExports ) {
                if ( !exportTrieHasNodeRecursive(name, index, &exportNode, &exportTrieEnd, &foundinIndex) )
                        return NULL;
        }
        else {
                if ( !exportTrieHasNode(name, index, &exportNode, &exportTrieEnd) )
                        return NULL;
        }
        *foundIn = this;
        return (ImageLoader::Symbol*)exportNode;
}

bool ImageLoaderMegaDylib::exportTrieHasNode(const char* symbolName, unsigned index,
                                                                                         const uint8_t** exportNode, const uint8_t** exportTrieEnd) const
{
        const uint8_t* start = (uint8_t*)(_imageExtras[index].exportsTrieAddr + _slide);
        const uint32_t size = _imageExtras[index].exportsTrieSize;
        if ( size == 0 )
                return false;
        const uint8_t* end = start + size;
        const uint8_t* node = ImageLoader::trieWalk(start, end, symbolName);
        if ( node == NULL )
                return false;
        *exportNode = node;
        *exportTrieEnd = end;
        return true;
}

bool ImageLoaderMegaDylib::exportTrieHasNodeRecursive(const char* symbolName, unsigned index,
                                                                                                                const uint8_t** exportNode, const uint8_t** exportTrieEnd,
                                                                                                                unsigned* foundinIndex) const
{
        // look in trie for image index
        if ( exportTrieHasNode(symbolName, index, exportNode, exportTrieEnd) ) {
                *foundinIndex = index;
                return true;
        }
        // recursively look in all re-exported tries
        unsigned startArrayIndex = _imageExtras[index].reExportsStartArrayIndex;
        for (int i=startArrayIndex; _reExportsArray[i] != 0xFFFF; ++i) {
                unsigned reExIndex = _reExportsArray[i];
                if ( exportTrieHasNodeRecursive(symbolName, reExIndex, exportNode, exportTrieEnd, foundinIndex) )
                        return true;
        }
        return false;
}

bool ImageLoaderMegaDylib::findExportedSymbolAddress(const LinkContext& context, const char* symbolName,
                                                                                                        const ImageLoader* requestorImage, int requestorOrdinalOfDef,
                                                                                                        bool runResolver, const ImageLoader** foundIn, uintptr_t* address) const
{
        const char* definedImagePath = requestorImage->libPath(requestorOrdinalOfDef-1);
        unsigned index = findImageIndex(context, definedImagePath);
        *foundIn = this;
        return findInChainedTries(context, symbolName, index, requestorImage, runResolver, address);
}

uintptr_t ImageLoaderMegaDylib::getExportedSymbolAddress(const Symbol* sym, const LinkContext& context,
                                                                                                                 const ImageLoader* requestor, bool runResolver, const char* symbolName) const
{
        // scan for with trie contains this node
        const uint8_t* exportTrieEnd = NULL;
        unsigned imageIndex = 0xFFFF;
        const macho_header* mh = NULL;
        uint64_t unslidTrieNode = ((uintptr_t)sym) - _slide;
        for (unsigned i=0; i < _imageCount; ++i) {
                uint64_t start = _imageExtras[i].exportsTrieAddr;
                uint64_t end   = _imageExtras[i].exportsTrieAddr +  _imageExtras[i].exportsTrieSize;
                if ( (start < unslidTrieNode) && (unslidTrieNode < end) ) {
                        exportTrieEnd = (uint8_t*)(end + _slide);
                        imageIndex = i;
                        mh = (macho_header*)(_images[imageIndex].address + _slide);
                        break;
                }
        }

        if ( mh == NULL )
                dyld::throwf("getExportedSymbolAddress(Symbol=%p) not in a cache trie", sym);

        const uint8_t* exportNode = (const uint8_t*)sym;
        uintptr_t address;
        processExportNode(context, symbolName ? symbolName : "unknown", imageIndex, exportNode, exportTrieEnd, requestor, runResolver, &address);
        return address;
}

void ImageLoaderMegaDylib::processExportNode(const LinkContext& context, const char* symbolName, unsigned definedImageIndex,
                                                                                        const uint8_t* exportNode, const uint8_t* exportTrieEnd,
                                                                                          const ImageLoader* requestorImage, bool runResolver, uintptr_t* address) const
{
        const macho_header* mh = getIndexedMachHeader(definedImageIndex);
        uintptr_t flags = read_uleb128(exportNode, exportTrieEnd);
        uintptr_t rawAddress;
        switch ( flags & EXPORT_SYMBOL_FLAGS_KIND_MASK ) {
                case EXPORT_SYMBOL_FLAGS_KIND_REGULAR:
                        if ( runResolver && (flags & EXPORT_SYMBOL_FLAGS_STUB_AND_RESOLVER) ) {
                                // this node has a stub and resolver, run the resolver to get target address
                                uintptr_t stub = read_uleb128(exportNode, exportTrieEnd) + (uintptr_t)mh; // skip over stub
                                // <rdar://problem/10657737> interposing dylibs have the stub address as their replacee
                                uintptr_t interposedStub = interposedAddress(context, stub, requestorImage);
                                if ( interposedStub != stub ) {
                                        *address = interposedStub;
                                        return;
                                }
                                // stub was not interposed, so run resolver
                                typedef uintptr_t (*ResolverProc)(void);
                                ResolverProc resolver = (ResolverProc)(read_uleb128(exportNode, exportTrieEnd) + (uintptr_t)mh);
                                *address = (*resolver)();
                                if ( context.verboseBind )
                                        dyld::log("dyld: resolver at %p returned 0x%08lX\n", resolver, *address);
                                return;
                        }
                        if ( flags & EXPORT_SYMBOL_FLAGS_REEXPORT ) {
                                // re-export from another dylib, lookup there
                                const uintptr_t ordinal = read_uleb128(exportNode, exportTrieEnd);
                                const char* importedName = (char*)exportNode;
                                if ( importedName[0] == '\0' )
                                        importedName = symbolName;
                                unsigned startArrayIndex = _imageExtras[definedImageIndex].dependentsStartArrayIndex;
                                unsigned reExImageIndex = _dependenciesArray[startArrayIndex + ordinal-1] & 0x7FFF;
                                if ( findInChainedTries(context, importedName, reExImageIndex, requestorImage, runResolver, address) )
                                        return;
                                dyld::throwf("re-exported symbol '%s' not found for image %s expected re-exported in %s, node=%p",
                                                        symbolName, getIndexedShortName(definedImageIndex), getIndexedShortName(reExImageIndex), exportNode);
                        }
                        rawAddress = read_uleb128(exportNode, exportTrieEnd) + (uintptr_t)mh;
                        *address = interposedAddress(context, rawAddress, requestorImage);
                        return;
                case EXPORT_SYMBOL_FLAGS_KIND_THREAD_LOCAL:
                        if ( flags & EXPORT_SYMBOL_FLAGS_STUB_AND_RESOLVER )
                                dyld::throwf("unsupported exported symbol kind. flags=%lu at node=%p", flags, exportNode);
                        *address = read_uleb128(exportNode, exportTrieEnd) + (uintptr_t)mh;
                        return;
                case EXPORT_SYMBOL_FLAGS_KIND_ABSOLUTE:
                        if ( flags & EXPORT_SYMBOL_FLAGS_STUB_AND_RESOLVER )
                                dyld::throwf("unsupported exported symbol kind. flags=%lu at node=%p", flags, exportNode);
                        *address = read_uleb128(exportNode, exportTrieEnd);
                        return;
                default:
                        dyld::throwf("unsupported exported symbol kind. flags=%lu at node=%p", flags, exportNode);
        }
        //dyld::throwf("unsupported exported symbol node=%p", exportNode);
}

bool ImageLoaderMegaDylib::findInChainedTries(const LinkContext& context, const char* symbolName, unsigned definedImageIndex,
                                                                                          const ImageLoader* requestorImage, bool runResolver, uintptr_t* address) const
{
        //dyld::log("findInChainedTries(sym=%s, index=%u, path=%s)\n", symbolName, definedImageIndex, getIndexedPath(definedImageIndex));
        const uint8_t* exportNode;
        const uint8_t* exportTrieEnd;
        unsigned foundinIndex;
        if ( !exportTrieHasNodeRecursive(symbolName, definedImageIndex, &exportNode, &exportTrieEnd, &foundinIndex) )
                return false;

        processExportNode(context, symbolName, foundinIndex, exportNode, exportTrieEnd, requestorImage, runResolver, address);
        return true;
}


bool ImageLoaderMegaDylib::findInChainedTriesAndDependentsExcept(const LinkContext& context, const char* symbolName, unsigned imageIndex,
                                                                                                                                const ImageLoader* requestorImage, bool runResolver, bool alreadyVisited[], uintptr_t* address) const
{
        //dyld::log("findInChainedTriesAndDependentsExcept(sym=%s, index=%u, path=%s)\n", symbolName, imageIndex, getIndexedPath(imageIndex));
        if ( alreadyVisited[imageIndex] )
                return false;
        alreadyVisited[imageIndex] = true;

        if ( findInChainedTries(context, symbolName, imageIndex, requestorImage, runResolver, address) )
                return true;

        unsigned startArrayIndex = _imageExtras[imageIndex].dependentsStartArrayIndex;
        for (int i=startArrayIndex; _dependenciesArray[i] != 0xFFFF; ++i) {
                // ignore upward links
                if ( (_dependenciesArray[i] & 0x8000) == 0 ) {
                        unsigned depIndex = _dependenciesArray[i] & 0x7FFF;
                        if ( _stateFlags[depIndex] != kStateFlagInitialized )
                                continue;
                        if ( findInChainedTriesAndDependentsExcept(context, symbolName, depIndex, requestorImage, runResolver, alreadyVisited, address) )
                                return true;
                }
        }
        return false;
}

bool ImageLoaderMegaDylib::findInChainedTriesAndDependents(const LinkContext& context, const char* symbolName, unsigned definedImageIndex,
                                                                                                                        const ImageLoader* requestorImage, bool runResolver, uintptr_t* address) const
{
        //dyld::log("findInChainedTriesAndDependents(sym=%s, index=%u, path=%s)\n", symbolName, definedImageIndex, getIndexedPath(definedImageIndex));
        if ( findInChainedTries(context, symbolName, definedImageIndex, requestorImage, runResolver, address) )
                return true;

        bool alreadyVisited[_header->imagesCount];
        bzero(alreadyVisited, sizeof(alreadyVisited));
        return findInChainedTriesAndDependentsExcept(context, symbolName, definedImageIndex, requestorImage, runResolver, alreadyVisited, address);
}


bool ImageLoaderMegaDylib::flatFindSymbol(const char* name, bool onlyInCoalesced, const ImageLoader::Symbol** sym, const ImageLoader** image, ImageLoader::CoalesceNotifier notifier)
{
        bool found = false;
        // check export trie of all in-use images
        for (unsigned i=0; i < _imageCount ; ++i) {
                uint16_t imageIndex = _bottomUpArray[i];
                if ( _stateFlags[imageIndex] == kStateUnused )
                        continue;
                const macho_header* mh = getIndexedMachHeader(imageIndex);
                if ( onlyInCoalesced && (mh->flags & MH_WEAK_DEFINES) == 0 )
                        continue;
                const uint8_t* exportNode;
                const uint8_t* exportTrieEnd;
                if ( exportTrieHasNode(name, imageIndex, &exportNode, &exportTrieEnd) ) {
                        if ( notifier )
                                notifier((Symbol*)exportNode, this, (mach_header*)getIndexedMachHeader(imageIndex));
                        if ( !found ) {
                                *sym = (Symbol*)exportNode;
                                *image = this;
                                found = true;
                        }
                        if ( !onlyInCoalesced )
                                return true;
                }
        }
        return found;
}


void ImageLoaderMegaDylib::markAllbound(const LinkContext& context)
{
        for (unsigned i=0; i < _imageCount; ++i) {
                uint16_t imageIndex = _bottomUpArray[i];
                if ( _stateFlags[imageIndex] == kStateLoaded ) {
                        _stateFlags[imageIndex] = kStateFlagBound;
                        context.notifySingleFromCache(dyld_image_state_bound, (mach_header*)getIndexedMachHeader(imageIndex), getIndexedPath(imageIndex));
                }
        }
}


void ImageLoaderMegaDylib::recursiveSpinLockAcquire(unsigned int imageIndex, mach_port_t thisThread)
{
        pthread_mutex_lock(&_lockArrayGuard);
        if ( _lockArray == NULL )
                _lockArray = (recursive_lock*)calloc(_imageCount, sizeof(recursive_lock));
        _lockArrayInUseCount++;
        pthread_mutex_unlock(&_lockArrayGuard);

        recursive_lock* imagesLock = &_lockArray[imageIndex];
        while ( !OSAtomicCompareAndSwap32Barrier(0, thisThread, (int*)&imagesLock->thread) ) {
                if ( imagesLock->thread == thisThread )
                        break;
        }
        imagesLock->count++;
}

void ImageLoaderMegaDylib::recursiveSpinLockRelease(unsigned int imageIndex, mach_port_t thisThread)
{
        recursive_lock* imagesLock = &_lockArray[imageIndex];
        if ( --imagesLock->count == 0 )
                imagesLock->thread = 0;

        pthread_mutex_lock(&_lockArrayGuard);
        _lockArrayInUseCount--;
        if ( _lockArrayInUseCount == 0 ) {
                free((void*)_lockArray);
                _lockArray = NULL;
        }
        pthread_mutex_unlock(&_lockArrayGuard);
}


void ImageLoaderMegaDylib::recursiveInitialization(const LinkContext& context, mach_port_t thisThread, unsigned int imageIndex,
                                                                                                        InitializerTimingList& timingInfo, UpwardIndexes& upInits)
{
        // Don't do any locking until libSystem.dylib is initialized, so we can malloc() the lock array
        bool useLock = dyld::gProcessInfo->libSystemInitialized;
        if ( useLock )
                recursiveSpinLockAcquire(imageIndex, thisThread);

        // only run initializers if currently in bound state
        if ( (_stateFlags[imageIndex] == kStateFlagBound) || (_stateFlags[imageIndex] == kStateFlagWeakBound) ) {

                // Each image in cache has its own lock.  We only set the state to Initialized if we hold the lock for the image.
                _stateFlags[imageIndex] = kStateFlagInitialized;

                // first recursively init all dependents
                unsigned startArrayIndex = _imageExtras[imageIndex].dependentsStartArrayIndex;
                for (int i=startArrayIndex; _dependenciesArray[i] != 0xFFFF; ++i) {
                        unsigned subDepIndex = _dependenciesArray[i];
                        // ignore upward links
                        if ( (subDepIndex & 0x8000) == 0 )
                                recursiveInitialization(context, thisThread, subDepIndex, timingInfo, upInits);
            else
                upInits.images[upInits.count++] = (subDepIndex & 0x7FFF);
                }

                // notify objc about this image
                context.notifySingleFromCache(dyld_image_state_dependents_initialized, (mach_header*)getIndexedMachHeader(imageIndex), getIndexedPath(imageIndex));

                // run all initializers for imageIndex
                const dyld_cache_accelerator_initializer* pInitStart = _initializers;
                const dyld_cache_accelerator_initializer* pInitEnd = &pInitStart[_initializerCount];
                bool ranSomeInitializers = false;
                uint64_t t1 = mach_absolute_time();
                for (const dyld_cache_accelerator_initializer* p=pInitStart; p < pInitEnd; ++p) {
                        if ( p->imageIndex == imageIndex ) {
                                Initializer func = (Initializer)(p->functionOffset + (uintptr_t)_header);
                                if ( context.verboseInit )
                                        dyld::log("dyld: calling initializer function %p in %s\n", func, getIndexedPath(imageIndex));
                                bool haveLibSystemHelpersBefore = (dyld::gLibSystemHelpers != NULL);
                                {
                                        dyld3::ScopedTimer timer(DBG_DYLD_TIMING_STATIC_INITIALIZER, (uint64_t)getIndexedMachHeader(imageIndex), (uint64_t)func, 0);
                                        func(context.argc, context.argv, context.envp, context.apple, &context.programVars);
                                };
                                bool haveLibSystemHelpersAfter = (dyld::gLibSystemHelpers != NULL);
                                ranSomeInitializers = true;
                                if ( !haveLibSystemHelpersBefore && haveLibSystemHelpersAfter ) {
                                        // now safe to use malloc() and other calls in libSystem.dylib
                                        dyld::gProcessInfo->libSystemInitialized = true;
                                }
                        }
                }
                if ( ranSomeInitializers ) {
                        uint64_t t2 = mach_absolute_time();
                        const char* shortName = strrchr(getIndexedPath(imageIndex), '/');
                        if ( shortName == NULL )
                                shortName = getIndexedPath(imageIndex);
                        else
                                ++shortName;
                        timingInfo.images[timingInfo.count].shortName = shortName;
                        timingInfo.images[timingInfo.count].initTime = (t2-t1);
                        timingInfo.count++;
                }
        }

        // only unlock if this frame locked (note: libSystemInitialized changes after libSystem's initializer is run)
        if ( useLock )
                recursiveSpinLockRelease(imageIndex, thisThread);
}


void ImageLoaderMegaDylib::recursiveInitialization(const LinkContext& context, mach_port_t thisThread, const char* pathToInitialize,
                                                                                                        InitializerTimingList& timingInfo, UninitedUpwards&)
{
        UpwardIndexes upsBuffer[256];
        UpwardIndexes& ups = upsBuffer[0];
        ups.count = 0;
        unsigned imageIndex = findImageIndex(context, pathToInitialize);
        this->recursiveInitialization(context, thisThread, imageIndex, timingInfo, ups);
        for (int i=0; i < ups.count; ++i) {
                UpwardIndexes upsBuffer2[256];
                UpwardIndexes& ignoreUp = upsBuffer2[0];
                ignoreUp.count = 0;
                this->recursiveInitialization(context, thisThread, ups.images[i], timingInfo, ignoreUp);
        }
}

void ImageLoaderMegaDylib::recursiveBind(const LinkContext& context, bool forceLazysBound, bool neverUnload)
{
        markAllbound(context);
}

uint8_t ImageLoaderMegaDylib::dyldStateToCacheState(dyld_image_states state) {
        switch (state) {
                case dyld_image_state_mapped:
                case dyld_image_state_dependents_mapped:
                        return kStateLoaded;
                case dyld_image_state_bound:
                        return kStateFlagBound;
                case dyld_image_state_initialized:
                        return kStateFlagInitialized;
                case dyld_image_state_rebased:
                case dyld_image_state_dependents_initialized:
                case dyld_image_state_terminated:
                        return kStateUnused;
        }
        return kStateUnused;
}

void ImageLoaderMegaDylib::recursiveApplyInterposing(const LinkContext& context)
{
        if ( context.verboseInterposing )
                dyld::log("dyld: interposing %lu tuples onto shared cache\n", fgInterposingTuples.size());


}

unsigned ImageLoaderMegaDylib::appendImagesToNotify(dyld_image_states state, bool orLater, dyld_image_info* infos)
{
        uint8_t targetCacheState = dyldStateToCacheState(state);
        if ( targetCacheState == kStateUnused )
                return 0;
        unsigned usedCount = 0;
        for (int i=_imageCount-1; i >= 0; --i) {
                uint16_t index = _bottomUpArray[i];
                uint8_t imageState = _stateFlags[index];
                if ( imageState == kStateFlagWeakBound )
                        imageState = kStateFlagBound;
                if ( (imageState == targetCacheState) || (orLater && (imageState > targetCacheState)) ) {
                        infos[usedCount].imageLoadAddress       = (mach_header*)getIndexedMachHeader(index);
                        infos[usedCount].imageFilePath          = getIndexedPath(index);
                        infos[usedCount].imageFileModDate       = 0;
                        ++usedCount;
                }
        }
        return usedCount;
}


bool ImageLoaderMegaDylib::dlopenFromCache(const LinkContext& context, const char* path, int mode, void** handle)
{
        unsigned imageIndex;
        if ( !hasDylib(path, &imageIndex) ) {
                return false;
        }

        // RTLD_NOLOAD means return handle if already loaded, but don't now load it
        if ( mode & RTLD_NOLOAD ) {
                dyld::gLibSystemHelpers->releaseGlobalDyldLock();
                if ( _stateFlags[imageIndex] == kStateUnused ) {
                        *handle = NULL;
                        return true;
                }
        }
        else {
                this->recursiveMarkLoaded(context, imageIndex);
                context.notifyBatch(dyld_image_state_dependents_mapped, false);
                this->markAllbound(context);
                context.notifyBatch(dyld_image_state_bound, false);

                this->weakBind(context);

                // <rdar://problem/25069046> Release dyld global lock before running initializers in dlopen() with customer cache
                dyld::gLibSystemHelpers->releaseGlobalDyldLock();

                InitializerTimingList timingInfo[_initializerCount];
                timingInfo[0].count = 0;
                mach_port_t thisThread  = mach_thread_self();
                UpwardIndexes upsBuffer[256];  // room for 511 dangling upward links
                UpwardIndexes& ups = upsBuffer[0];
                ups.count = 0;
                this->recursiveInitialization(context, thisThread, imageIndex, timingInfo[0], ups);
                // make sure any upward linked dylibs were initialized
                for (int i=0; i < ups.count; ++i) {
                        UpwardIndexes upsBuffer2[256];
                        UpwardIndexes& ignoreUp = upsBuffer2[0];
                        ignoreUp.count = 0;
                        this->recursiveInitialization(context, thisThread, ups.images[i], timingInfo[0], ignoreUp);
                }
                mach_port_deallocate(mach_task_self(), thisThread);
                context.notifyBatch(dyld_image_state_initialized, false);
        }

        *handle = makeCacheHandle(imageIndex, mode);
        return true;
}

bool ImageLoaderMegaDylib::makeCacheHandle(const LinkContext& context, unsigned cacheIndex, int mode, void** result)
{
        if ( cacheIndex >= _imageCount )
                return false;

        *result = makeCacheHandle(cacheIndex, mode);
        return true;
}

void* ImageLoaderMegaDylib::makeCacheHandle(unsigned index, int mode)
{
        uint8_t flags = ((mode & RTLD_FIRST) ? 1 : 0);

#if __LP64__
        return (void*)(uintptr_t)( 0xFFEEDDCC00000000LL | (index << 8) | flags);
#else
        return (void*)(uintptr_t)( 0xF8000000 | (index << 8) | flags);
#endif
}

bool ImageLoaderMegaDylib::isCacheHandle(void* handle, unsigned* index, uint8_t* flags)
{
#if __LP64__
        if ( (((uintptr_t)handle) >> 32) == 0xFFEEDDCC ) {
                if ( index )
                        *index = (((uintptr_t)handle) >> 8) & 0xFFFF;
                if ( flags )
                        *flags = ((uintptr_t)handle) & 0xFF;
                return true;
        }
#else
        if ( (((uintptr_t)handle) >> 24) == 0xF8 ) {
                if ( index )
                        *index = (((uintptr_t)handle) >> 8) & 0xFFFF;
                if ( flags )
                        *flags = ((uintptr_t)handle) & 0xFF;
                return true;
        }
#endif
        return false;
}


void* ImageLoaderMegaDylib::dlsymFromCache(const LinkContext& context, void* handle, const char* symbolName, unsigned imageIndex)
{
        unsigned indexInHandle;
        uint8_t flags;
        uintptr_t symAddress;
        if ( handle == RTLD_SELF ) {
                if ( findInChainedTriesAndDependents(context, symbolName, imageIndex, NULL, true, &symAddress) )
                        return (void*)symAddress;
        }
        else if ( handle == RTLD_NEXT ) {
                // FIXME: really need to not look in imageIndex, but look in others.
                if ( findInChainedTriesAndDependents(context, symbolName, imageIndex, NULL, true, &symAddress) )
                        return (void*)symAddress;
        }
        else if ( isCacheHandle(handle, &indexInHandle, &flags) ) {
                bool searchOnlyFirst = (flags & 1);  // RTLD_FIRST
                // normal dlsym(handle,) semantics is that the handle is just the first place to search. RTLD_FIRST disables that
                if ( searchOnlyFirst ) {
                        if ( findInChainedTries(context, symbolName, indexInHandle, NULL, true, &symAddress) )
                                return (void*)symAddress;
                }
                else {
                        if ( findInChainedTriesAndDependents(context, symbolName, indexInHandle, NULL, true, &symAddress) )
                                return (void*)symAddress;
                }
        }

        return NULL;
}

bool ImageLoaderMegaDylib::dladdrFromCache(const void* address, Dl_info* info)
{
        const mach_header* mh;
        unsigned index;
        if ( !addressInCache(address, &mh, &info->dli_fname, &index) )
                return false;

        info->dli_fbase = (void*)mh;
        if ( address == mh ) {
                // special case lookup of header
                info->dli_sname = "__dso_handle";
                info->dli_saddr = info->dli_fbase;
                return true;
        }

        // find closest symbol in the image
        info->dli_sname = ImageLoaderMachO::findClosestSymbol(mh, address, (const void**)&info->dli_saddr);

        // never return the mach_header symbol
        if ( info->dli_saddr == info->dli_fbase ) {
                info->dli_sname = NULL;
                info->dli_saddr = NULL;
                return true;
        }

        // strip off leading underscore
        if ( info->dli_sname != NULL ) {
                if ( info->dli_sname[0] == '_' )
                        info->dli_sname = info->dli_sname +1;
        }
        return true;
}


uintptr_t ImageLoaderMegaDylib::bindLazy(uintptr_t lazyBindingInfoOffset, const LinkContext& context, const mach_header* mh, unsigned imageIndex)
{
        const dyld_info_command* dyldInfoCmd = ImageLoaderMachO::findDyldInfoLoadCommand(mh);
        if ( dyldInfoCmd == NULL )
                return 0;

        const uint8_t* const lazyInfoStart = &_linkEditBias[dyldInfoCmd->lazy_bind_off];
        const uint8_t* const lazyInfoEnd = &lazyInfoStart[dyldInfoCmd->lazy_bind_size];
        uint32_t lbOffset = (uint32_t)lazyBindingInfoOffset;
        uint8_t segIndex;
        uintptr_t segOffset;
        int libraryOrdinal;
        const char* symbolName;
        bool doneAfterBind;
        if ( ImageLoaderMachO::getLazyBindingInfo(lbOffset, lazyInfoStart, lazyInfoEnd, &segIndex, &segOffset, &libraryOrdinal, &symbolName, &doneAfterBind) ) {
                //const char* thisPath = getIndexedPath(imageIndex);
                //dyld::log("%s needs symbol '%s' from ordinal=%d\n", thisPath, symbolName, libraryOrdinal);
                unsigned startDepArrayIndex = _imageExtras[imageIndex].dependentsStartArrayIndex;
                unsigned targetIndex;
                if ( libraryOrdinal == BIND_SPECIAL_DYLIB_SELF )
                        targetIndex = imageIndex;
                else
                        targetIndex = _dependenciesArray[startDepArrayIndex+libraryOrdinal-1] & 0x7FFF;
                //const char* targetPath = getIndexedPath(targetIndex);
                //dyld::log("%s needs symbol '%s' from %s\n", thisPath, symbolName, targetPath);
                uintptr_t targetAddress;
                if ( findInChainedTries(context, symbolName, targetIndex, this, true, &targetAddress) ) {
                        if ( uintptr_t segPrefAddress = ImageLoaderMachO::segPreferredAddress(mh, segIndex) ) {
                                uintptr_t* lp = (uintptr_t*)(segPrefAddress + segOffset + _slide);
                                //dyld::log("    storing 0x%0lX to lp %p\n", targetAddress, lp);
                                *lp = targetAddress;
                                return targetAddress;
                        }
                }
        }

        return 0;
}


#endif // SUPPORT_ACCELERATE_TABLES