dyld3/shared-cache/OptimizerLinkedit.cpp

   1 /* -*- mode: C++; c-basic-offset: 4; indent-tabs-mode: nil -*-
   2  *
   3  * Copyright (c) 2014 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 #include <dirent.h>
  27 #include <sys/errno.h>
  28 #include <sys/fcntl.h>
  29 #include <mach-o/loader.h>
  30 #include <mach-o/fat.h>
  31 #include <assert.h>
  32
  33 #include <fstream>
  34 #include <string>
  35 #include <algorithm>
  36 #include <unordered_map>
  37 #include <unordered_set>
  38
  39 #include "MachOFileAbstraction.hpp"
  40 #include "Trie.hpp"
  41 #include "DyldSharedCache.h"
  42 #include "CacheBuilder.h"
  43 #include "MachOLoaded.h"
  44
  45 #define ALIGN_AS_TYPE(value, type) \
  46         ((value + alignof(type) - 1) & (-alignof(type)))
  47
  48 namespace {
  49
  50 template <typename P>
  51 class SortedStringPool
  52 {
  53 public:
  54     // add a string and symbol table entry index to be updated later
  55     void add(uint32_t symbolIndex, const char* symbolName) {
  56         _map[symbolName].push_back(symbolIndex);
  57     }
  58
  59     // copy sorted strings to buffer and update all symbol's string offsets
  60     uint32_t copyPoolAndUpdateOffsets(char* dstStringPool, macho_nlist<P>* symbolTable) {
  61         // walk sorted list of strings
  62         dstStringPool[0] = '\0'; // tradition for start of pool to be empty string
  63         uint32_t poolOffset = 1;
  64         for (auto& entry : _map) {
  65             const std::string& symName = entry.first;
  66             // append string to pool
  67             strcpy(&dstStringPool[poolOffset], symName.c_str());
  68             //  set each string offset of each symbol using it
  69             for (uint32_t symbolIndex : entry.second) {
  70                 symbolTable[symbolIndex].set_n_strx(poolOffset);
  71             }
  72             poolOffset += symName.size() + 1;
  73         }
  74         // return size of pool
  75         return poolOffset;
  76     }
  77
  78     size_t size() {
  79         size_t size = 1;
  80         for (auto& entry : _map) {
  81             size += (entry.first.size() + 1);
  82         }
  83         return size;
  84     }
  85
  86
  87 private:
  88     std::map<std::string, std::vector<uint32_t>> _map;
  89 };
  90
  91
  92 } // anonymous namespace
  93
  94
  95 struct LocalSymbolInfo
  96 {
  97     uint32_t    dylibOffset;
  98     uint32_t    nlistStartIndex;
  99     uint32_t    nlistCount;
 100 };
 101
 102
 103 template <typename P>
 104 class LinkeditOptimizer {
 105 public:
 106                     LinkeditOptimizer(void* cacheBuffer, macho_header<P>* mh, Diagnostics& diag);
 107
 108     uint32_t        linkeditSize() { return _linkeditSize; }
 109     uint64_t        linkeditAddr() { return _linkeditAddr; }
 110     const char*     installName() { return _installName; }
 111     void            copyWeakBindingInfo(uint8_t* newLinkEditContent, uint32_t& offset);
 112     void            copyLazyBindingInfo(uint8_t* newLinkEditContent, uint32_t& offset);
 113     void            copyBindingInfo(uint8_t* newLinkEditContent, uint32_t& offset);
 114     void            copyExportInfo(uint8_t* newLinkEditContent, uint32_t& offset);
 115     void            copyExportedSymbols(uint8_t* newLinkEditContent, SortedStringPool<P>& stringPool, uint32_t& offset, uint32_t& symbolIndex);
 116     void            copyImportedSymbols(uint8_t* newLinkEditContent, SortedStringPool<P>& stringPool, uint32_t& offset, uint32_t& symbolIndex);
 117     void            copyLocalSymbols(uint8_t* newLinkEditContent, SortedStringPool<P>& stringPool, uint32_t& offset, uint32_t& symbolIndex,
 118                                      bool redact, std::vector<LocalSymbolInfo>& localSymbolInfos,
 119                                      std::vector<macho_nlist<P>>& unmappedLocalSymbols, SortedStringPool<P>& localSymbolsStringPool);
 120     void            copyFunctionStarts(uint8_t* newLinkEditContent, uint32_t& offset);
 121     void            copyDataInCode(uint8_t* newLinkEditContent, uint32_t& offset);
 122     void            copyIndirectSymbolTable(uint8_t* newLinkEditContent, uint32_t& offset);
 123     void            updateLoadCommands(uint32_t linkeditStartOffset, uint64_t mergedLinkeditAddr, uint64_t newLinkeditSize,
 124                                        uint32_t sharedSymbolTableStartOffset, uint32_t sharedSymbolTableCount,
 125                                        uint32_t sharedSymbolStringsOffset, uint32_t sharedSymbolStringsSize);
 126
 127     macho_header<P>*                        machHeader() { return _mh; }
 128     const std::vector<const char*>          getDownwardDependents() { return _downDependentPaths; }
 129     const std::vector<const char*>          getAllDependents() { return _allDependentPaths; }
 130     const std::vector<const char*>          getReExportPaths() { return _reExportPaths; }
 131     const std::vector<uint64_t>             initializerAddresses() { return _initializerAddresses; }
 132     const std::vector<macho_section<P>*>    dofSections() { return _dofSections; }
 133     uint32_t                                exportsTrieLinkEditOffset() { return _newExportInfoOffset; }
 134     uint32_t                                exportsTrieLinkEditSize() { return _exportInfoSize; }
 135     uint32_t                                weakBindingLinkEditOffset() { return _newWeakBindingInfoOffset; }
 136     uint32_t                                weakBindingLinkEditSize() { return _newWeakBindingSize; }
 137     uint64_t                                dyldSectionAddress() { return _dyldSectionAddr; }
 138     const std::vector<macho_segment_command<P>*>&  segCmds() { return _segCmds; }
 139
 140
 141     static void optimizeLinkedit(CacheBuilder& builder);
 142     static void mergeLinkedits(CacheBuilder& builder, std::vector<LinkeditOptimizer<P>*>& optimizers);
 143
 144 private:
 145
 146     typedef typename P::uint_t pint_t;
 147     typedef typename P::E E;
 148
 149     macho_header<P>*                        _mh;
 150     void*                                   _cacheBuffer;
 151     Diagnostics&                            _diagnostics;
 152     uint32_t                                _linkeditSize        = 0;
 153     uint64_t                                _linkeditAddr        = 0;
 154     const uint8_t*                          _linkeditBias       = nullptr;
 155     const char*                             _installName        = nullptr;
 156     macho_symtab_command<P>*                _symTabCmd          = nullptr;
 157     macho_dysymtab_command<P>*              _dynSymTabCmd       = nullptr;
 158     macho_dyld_info_command<P>*             _dyldInfo           = nullptr;
 159     macho_linkedit_data_command<P>*         _exportTrieCmd      = nullptr;
 160     macho_linkedit_data_command<P>*         _functionStartsCmd  = nullptr;
 161     macho_linkedit_data_command<P>*         _dataInCodeCmd      = nullptr;
 162     std::vector<macho_segment_command<P>*>  _segCmds;
 163     std::unordered_map<uint32_t,uint32_t>   _oldToNewSymbolIndexes;
 164     std::vector<const char*>                _reExportPaths;
 165     std::vector<const char*>                _downDependentPaths;
 166     std::vector<const char*>                _allDependentPaths;
 167     std::vector<uint64_t>                   _initializerAddresses;
 168     std::vector<macho_section<P>*>          _dofSections;
 169     uint32_t                                _newWeakBindingInfoOffset       = 0;
 170     uint32_t                                _newLazyBindingInfoOffset       = 0;
 171     uint32_t                                _newBindingInfoOffset           = 0;
 172     uint32_t                                _newExportInfoOffset            = 0;
 173     uint32_t                                _exportInfoSize                 = 0;
 174     uint32_t                                _newWeakBindingSize             = 0;
 175     uint32_t                                _newExportedSymbolsStartIndex   = 0;
 176     uint32_t                                _newExportedSymbolCount         = 0;
 177     uint32_t                                _newImportedSymbolsStartIndex   = 0;
 178     uint32_t                                _newImportedSymbolCount         = 0;
 179     uint32_t                                _newLocalSymbolsStartIndex      = 0;
 180     uint32_t                                _newLocalSymbolCount            = 0;
 181     uint32_t                                _newFunctionStartsOffset        = 0;
 182     uint32_t                                _newDataInCodeOffset            = 0;
 183     uint32_t                                _newIndirectSymbolTableOffset   = 0;
 184     uint64_t                                _dyldSectionAddr                = 0;
 185 };
 186
 187
 188
 189 template <typename P>
 190 class AcceleratorTables {
 191 public:
 192                 AcceleratorTables(DyldSharedCache* cache, uint64_t linkeditStartAddr, Diagnostics& diag, const std::vector<LinkeditOptimizer<P>*>& optimizers);
 193
 194     uint32_t    totalSize() const;
 195     void        copyTo(uint8_t* buffer);
 196
 197 private:
 198     typedef typename P::E  E;
 199
 200     struct NodeChain;
 201
 202     struct DepNode {
 203         std::vector<DepNode*>   _dependents;
 204         unsigned                _depth;
 205         const char*             _installName;
 206
 207                                 DepNode() : _depth(0), _installName(nullptr) { }
 208         void                    computeDepth();
 209         static void             verifyUnreachable(DepNode* target, NodeChain& chain, Diagnostics& diag, std::unordered_set<DepNode*>& visitedNodes, const std::vector<DepNode*>& from);
 210     };
 211
 212     struct NodeChain {
 213         NodeChain*   prev;
 214         DepNode*     node;
 215     };
 216
 217     std::unordered_map<macho_header<P>*, DepNode>                   _depDAG;
 218     std::vector<dyld_cache_image_info_extra>                        _extraInfo;
 219     std::vector<uint8_t>                                            _trieBytes;
 220     std::vector<uint16_t>                                           _reExportArray;
 221     std::vector<uint16_t>                                           _dependencyArray;
 222     std::vector<uint16_t>                                           _bottomUpArray;
 223     std::vector<dyld_cache_accelerator_initializer>                 _initializers;
 224     std::vector<dyld_cache_accelerator_dof>                         _dofSections;
 225     std::vector<dyld_cache_range_entry>                             _rangeTable;
 226     std::unordered_map<macho_header<P>*, uint32_t>                  _machHeaderToImageIndex;
 227     std::unordered_map<std::string, macho_header<P>*>               _dylibPathToMachHeader;
 228     std::unordered_map<macho_header<P>*, LinkeditOptimizer<P>*>     _machHeaderToOptimizer;
 229     dyld_cache_accelerator_info                                     _acceleratorInfoHeader;
 230 };
 231
 232
 233 template <typename P>
 234 void AcceleratorTables<P>::AcceleratorTables::DepNode::verifyUnreachable(AcceleratorTables<P>::DepNode* target, struct AcceleratorTables<P>::NodeChain& chain, Diagnostics& diag,
 235                                                                         std::unordered_set<DepNode*>& visitedNodes, const std::vector<AcceleratorTables<P>::DepNode*>& from) {
 236     for (DepNode* node : from) {
 237         bool foundCycle = (node == target);
 238         for (NodeChain* c = &chain; c->prev != nullptr; c = c->prev) {
 239             if ( c->node == target ) {
 240                 foundCycle = true;
 241                 break;
 242             }
 243         }
 244         if ( foundCycle ) {
 245             NodeChain* chp = &chain;
 246             std::string msg = std::string("found cycle for ") + target->_installName;
 247             while (chp != nullptr) {
 248                 msg = msg + "\n  " + chp->node->_installName;
 249                 chp = chp->prev;
 250             }
 251             diag.warning("%s", msg.c_str());
 252             return;
 253         }
 254
 255         if ( visitedNodes.count(node) )
 256             continue;
 257         visitedNodes.insert(node);
 258         NodeChain nextChain;
 259         nextChain.prev = &chain;
 260         nextChain.node = node;
 261         verifyUnreachable(target, nextChain, diag, visitedNodes, node->_dependents);
 262     }
 263 }
 264
 265 const uint16_t kBranchIslandDylibIndex = 0x7FFF;
 266
 267 template <typename P>
 268 AcceleratorTables<P>::AcceleratorTables(DyldSharedCache* cache, uint64_t linkeditStartAddr, Diagnostics& diag, const std::vector<LinkeditOptimizer<P>*>& optimizers)
 269 {
 270     // build table mapping tables to map between mach_header, index, and optimizer
 271     for ( LinkeditOptimizer<P>* op : optimizers ) {
 272         _machHeaderToOptimizer[op->machHeader()] = op;
 273     }
 274     const dyld_cache_mapping_info* mappings = (dyld_cache_mapping_info*)((uint8_t*)cache + cache->header.mappingOffset);
 275     uint64_t cacheStartAddress = mappings[0].address;
 276     const dyld_cache_image_info* images = (dyld_cache_image_info*)((uint8_t*)cache + cache->header.imagesOffset);
 277     for (unsigned i=0; i < cache->header.imagesCount; ++i) {
 278         uint64_t segCacheFileOffset = images[i].address - cacheStartAddress;
 279         macho_header<P>* mhMapped = (macho_header<P>*)((uint8_t*)cache+segCacheFileOffset);
 280         const char* path = (char*)cache + images[i].pathFileOffset;
 281         _dylibPathToMachHeader[path] = mhMapped;
 282         // don't add alias entries (path offset in pool near start of cache) to header->index map
 283         if ( images[i].pathFileOffset > segCacheFileOffset )
 284             _machHeaderToImageIndex[mhMapped] = i;
 285     }
 286
 287
 288     // build DAG of image dependencies
 289     for (LinkeditOptimizer<P>* op : optimizers) {
 290         _depDAG[op->machHeader()]._installName = op->installName();
 291     }
 292     for (LinkeditOptimizer<P>* op : optimizers) {
 293         DepNode& node = _depDAG[op->machHeader()];
 294         for (const char* depPath : op->getDownwardDependents()) {
 295             macho_header<P>* depMH = _dylibPathToMachHeader[depPath];
 296             if ( depMH != nullptr ) {
 297                 DepNode* depNode = &_depDAG[depMH];
 298                 node._dependents.push_back(depNode);
 299             }
 300         }
 301     }
 302
 303     // check for cycles in DAG
 304     for (auto& entry : _depDAG) {
 305         DepNode* node = &entry.second;
 306         NodeChain chain;
 307         chain.prev = nullptr;
 308         chain.node = node;
 309         std::unordered_set<DepNode*> visitedNodes;
 310         DepNode::verifyUnreachable(node, chain, diag, visitedNodes, node->_dependents);
 311     }
 312
 313     // compute depth for each DAG node
 314     for (auto& entry : _depDAG) {
 315         entry.second.computeDepth();
 316     }
 317
 318     // build sorted (bottom up) list of images
 319     std::vector<macho_header<P>*> sortedMachHeaders;
 320     sortedMachHeaders.reserve(optimizers.size());
 321     for (LinkeditOptimizer<P>* op : optimizers) {
 322         if ( strcmp(op->installName(), "dyld_shared_cache_branch_islands") != 0 )
 323             sortedMachHeaders.push_back(op->machHeader());
 324         else
 325             _machHeaderToImageIndex[op->machHeader()] = kBranchIslandDylibIndex;
 326     }
 327     std::sort(sortedMachHeaders.begin(), sortedMachHeaders.end(),
 328               [&](macho_header<P>* lmh, macho_header<P>* rmh) -> bool {
 329                 if ( _depDAG[lmh]._depth != _depDAG[rmh]._depth )
 330                     return (_depDAG[lmh]._depth < _depDAG[rmh]._depth);
 331                 else
 332                     return (lmh < rmh);
 333               });
 334
 335     // build zeroed array of extra infos
 336     dyld_cache_image_info_extra emptyExtra;
 337     emptyExtra.exportsTrieAddr              = 0;
 338     emptyExtra.weakBindingsAddr             = 0;
 339     emptyExtra.exportsTrieSize              = 0;
 340     emptyExtra.weakBindingsSize             = 0;
 341     emptyExtra.dependentsStartArrayIndex    = 0;
 342     emptyExtra.reExportsStartArrayIndex     = 0;
 343     _extraInfo.insert(_extraInfo.begin(), sortedMachHeaders.size(), emptyExtra);
 344
 345     //for ( macho_header<P>* mh : sortedMachHeaders ) {
 346     //    fprintf(stderr, "depth: %3d mh: %p  path: %s\n", _depDAG[mh]._depth, mh, _machHeaderToOptimizer[mh]->installName());
 347     //}
 348
 349     // build dependency table
 350     _dependencyArray.push_back(0xFFFF); // reserve 0 slot to be "no-dependencies"
 351     for (macho_header<P>* mh : sortedMachHeaders) {
 352         LinkeditOptimizer<P>* op = _machHeaderToOptimizer[mh];
 353         unsigned index = _machHeaderToImageIndex[mh];
 354         auto depPaths = op->getAllDependents();
 355         if ( depPaths.empty() ) {
 356             _extraInfo[index].dependentsStartArrayIndex = 0;
 357         }
 358         else {
 359             _extraInfo[index].dependentsStartArrayIndex = (uint32_t)_dependencyArray.size();
 360             auto downPaths = op->getDownwardDependents();
 361             for (const char* depPath : depPaths) {
 362                 macho_header<P>* depMH = _dylibPathToMachHeader[depPath];
 363                 uint16_t depIndex = _machHeaderToImageIndex[depMH];
 364                 if ( std::find(downPaths.begin(), downPaths.end(), depPath) == downPaths.end())
 365                     depIndex |= 0x8000;
 366                 _dependencyArray.push_back(depIndex);
 367             }
 368             _dependencyArray.push_back(0xFFFF); // mark end of list
 369        }
 370     }
 371
 372     // build re-exports table
 373     _reExportArray.push_back(0xFFFF); // reserve 0 slot to be "no-re-exports"
 374     for (macho_header<P>* mh : sortedMachHeaders) {
 375         LinkeditOptimizer<P>* op = _machHeaderToOptimizer[mh];
 376         unsigned index = _machHeaderToImageIndex[mh];
 377         auto reExPaths = op->getReExportPaths();
 378         if ( reExPaths.empty() ) {
 379             _extraInfo[index].reExportsStartArrayIndex = 0;
 380         }
 381         else {
 382             _extraInfo[index].reExportsStartArrayIndex = (uint32_t)_reExportArray.size();
 383             for (const char* reExPath : reExPaths) {
 384                 macho_header<P>* reExMH = _dylibPathToMachHeader[reExPath];
 385                 uint32_t reExIndex = _machHeaderToImageIndex[reExMH];
 386                 _reExportArray.push_back(reExIndex);
 387             }
 388             _reExportArray.push_back(0xFFFF); // mark end of list
 389        }
 390     }
 391
 392     // build ordered list of initializers
 393     for (macho_header<P>* mh : sortedMachHeaders) {
 394         LinkeditOptimizer<P>* op = _machHeaderToOptimizer[mh];
 395         unsigned index = _machHeaderToImageIndex[mh];
 396         _bottomUpArray.push_back(index);
 397         for (uint64_t initializer : op->initializerAddresses()) {
 398             //fprintf(stderr, "0x%08llX %s\n", initializer, op->installName());
 399             dyld_cache_accelerator_initializer entry;
 400             entry.functionOffset = (uint32_t)(initializer-cacheStartAddress);
 401             entry.imageIndex = _machHeaderToImageIndex[mh];
 402             _initializers.push_back(entry);
 403         }
 404     }
 405
 406     // build ordered list of DOF sections
 407     for (macho_header<P>* mh : sortedMachHeaders) {
 408         LinkeditOptimizer<P>* op = _machHeaderToOptimizer[mh];
 409         assert(op != NULL);
 410         unsigned imageIndex = _machHeaderToImageIndex[mh];
 411         for (auto& sect : op->dofSections()) {
 412             //fprintf(stderr, "0x%08llX %s\n", initializer, op->installName());
 413             dyld_cache_accelerator_dof entry;
 414             entry.sectionAddress = sect->addr();
 415             entry.sectionSize    = (uint32_t)sect->size();
 416             entry.imageIndex     = imageIndex;
 417             _dofSections.push_back(entry);
 418         }
 419     }
 420
 421
 422     // register exports trie and weak binding info in each dylib with image extra info
 423     for (macho_header<P>* mh : sortedMachHeaders) {
 424         LinkeditOptimizer<P>* op = _machHeaderToOptimizer[mh];
 425         unsigned index = _machHeaderToImageIndex[mh];
 426         _extraInfo[index].exportsTrieAddr  = op->exportsTrieLinkEditOffset() + linkeditStartAddr;
 427         _extraInfo[index].exportsTrieSize  = op->exportsTrieLinkEditSize();
 428         _extraInfo[index].weakBindingsAddr = op->weakBindingLinkEditOffset() + linkeditStartAddr;
 429         _extraInfo[index].weakBindingsSize = op->weakBindingLinkEditSize();
 430     }
 431
 432     // record location of __DATA/__dyld section in libdyld.dylib
 433     macho_header<P>* libdyldMH = _dylibPathToMachHeader["/usr/lib/system/libdyld.dylib"];
 434     LinkeditOptimizer<P>* libdyldOp = _machHeaderToOptimizer[libdyldMH];
 435     uint64_t dyldSectionAddr = libdyldOp->dyldSectionAddress();
 436
 437     // build range table for fast address->image lookups
 438     for (macho_header<P>* mh : sortedMachHeaders) {
 439         LinkeditOptimizer<P>* op = _machHeaderToOptimizer[mh];
 440         unsigned imageIndex = _machHeaderToImageIndex[mh];
 441         for (const macho_segment_command<P>* segCmd : op->segCmds()) {
 442             if ( strcmp(segCmd->segname(), "__LINKEDIT") == 0 )
 443                 continue;
 444             dyld_cache_range_entry entry;
 445             entry.startAddress = segCmd->vmaddr();
 446             entry.size         = (uint32_t)segCmd->vmsize();
 447             entry.imageIndex   = imageIndex;
 448             _rangeTable.push_back(entry);
 449         }
 450     }
 451     std::sort(_rangeTable.begin(), _rangeTable.end(),
 452               [&](const dyld_cache_range_entry& lRange, const dyld_cache_range_entry& rRange) -> bool {
 453                 return (lRange.startAddress < rRange.startAddress);
 454               });
 455
 456     // build trie that maps install names to image index
 457     std::vector<DylibIndexTrie::Entry> dylibEntrys;
 458     for (auto &x : _dylibPathToMachHeader) {
 459         const std::string& path = x.first;
 460         unsigned index = _machHeaderToImageIndex[x.second];
 461         dylibEntrys.push_back(DylibIndexTrie::Entry(path, DylibIndex(index)));
 462     }
 463     DylibIndexTrie dylibsTrie(dylibEntrys);
 464     dylibsTrie.emit(_trieBytes);
 465     while ( (_trieBytes.size() % 4) != 0 )
 466         _trieBytes.push_back(0);
 467
 468     // fill out header
 469     _acceleratorInfoHeader.version              = 1;
 470     _acceleratorInfoHeader.imageExtrasCount     = (uint32_t)_extraInfo.size();
 471     _acceleratorInfoHeader.imagesExtrasOffset   = ALIGN_AS_TYPE(sizeof(dyld_cache_accelerator_info), dyld_cache_image_info_extra);
 472     _acceleratorInfoHeader.bottomUpListOffset   = _acceleratorInfoHeader.imagesExtrasOffset + _acceleratorInfoHeader.imageExtrasCount*sizeof(dyld_cache_image_info_extra);
 473     _acceleratorInfoHeader.dylibTrieOffset      = _acceleratorInfoHeader.bottomUpListOffset + _acceleratorInfoHeader.imageExtrasCount*sizeof(uint16_t);
 474     _acceleratorInfoHeader.dylibTrieSize        = (uint32_t)_trieBytes.size();
 475     _acceleratorInfoHeader.initializersOffset   = ALIGN_AS_TYPE(_acceleratorInfoHeader.dylibTrieOffset + _acceleratorInfoHeader.dylibTrieSize, dyld_cache_accelerator_initializer);
 476     _acceleratorInfoHeader.initializersCount    = (uint32_t)_initializers.size();
 477     _acceleratorInfoHeader.dofSectionsOffset    = ALIGN_AS_TYPE(_acceleratorInfoHeader.initializersOffset + _acceleratorInfoHeader.initializersCount*sizeof(dyld_cache_accelerator_initializer), dyld_cache_accelerator_initializer);
 478     _acceleratorInfoHeader.dofSectionsCount     = (uint32_t)_dofSections.size();
 479     _acceleratorInfoHeader.reExportListOffset   = ALIGN_AS_TYPE(_acceleratorInfoHeader.dofSectionsOffset + _acceleratorInfoHeader.dofSectionsCount*sizeof(dyld_cache_accelerator_dof), dyld_cache_accelerator_dof);
 480     _acceleratorInfoHeader.reExportCount        = (uint32_t)_reExportArray.size();
 481     _acceleratorInfoHeader.depListOffset        = ALIGN_AS_TYPE(_acceleratorInfoHeader.reExportListOffset + _acceleratorInfoHeader.reExportCount*sizeof(uint16_t), uint16_t);
 482     _acceleratorInfoHeader.depListCount         = (uint32_t)_dependencyArray.size();
 483     _acceleratorInfoHeader.rangeTableOffset     = ALIGN_AS_TYPE(_acceleratorInfoHeader.depListOffset + _acceleratorInfoHeader.depListCount*sizeof(uint16_t), dyld_cache_range_entry);
 484     _acceleratorInfoHeader.rangeTableCount      = (uint32_t)_rangeTable.size();
 485     _acceleratorInfoHeader.dyldSectionAddr      = dyldSectionAddr;
 486 }
 487
 488
 489 template <typename P>
 490 void AcceleratorTables<P>::DepNode::computeDepth()
 491 {
 492     if ( _depth != 0 )
 493         return;
 494     _depth = 1;
 495     for (DepNode* node : _dependents) {
 496         node->computeDepth();
 497         if ( node->_depth >= _depth )
 498             _depth = node->_depth + 1;
 499     }
 500 }
 501
 502 template <typename P>
 503 uint32_t AcceleratorTables<P>::totalSize() const
 504 {
 505     return (uint32_t)align(_acceleratorInfoHeader.rangeTableOffset + _acceleratorInfoHeader.rangeTableCount*sizeof(dyld_cache_range_entry), 14);
 506 }
 507
 508 template <typename P>
 509 void AcceleratorTables<P>::copyTo(uint8_t* buffer)
 510 {
 511     memcpy(buffer, &_acceleratorInfoHeader, sizeof(dyld_cache_accelerator_info));
 512     memcpy(&buffer[_acceleratorInfoHeader.imagesExtrasOffset], &_extraInfo[0],       _extraInfo.size()*sizeof(dyld_cache_image_info_extra));
 513     memcpy(&buffer[_acceleratorInfoHeader.bottomUpListOffset], &_bottomUpArray[0],   _bottomUpArray.size()*sizeof(uint16_t));
 514     memcpy(&buffer[_acceleratorInfoHeader.initializersOffset], &_initializers[0],    _initializers.size()*sizeof(dyld_cache_accelerator_initializer));
 515     memcpy(&buffer[_acceleratorInfoHeader.reExportListOffset], &_reExportArray[0],   _reExportArray.size()*sizeof(uint16_t));
 516     memcpy(&buffer[_acceleratorInfoHeader.dofSectionsOffset],  &_dofSections[0],     _dofSections.size()*sizeof(dyld_cache_accelerator_dof));
 517     memcpy(&buffer[_acceleratorInfoHeader.depListOffset],      &_dependencyArray[0], _dependencyArray.size()*sizeof(uint16_t));
 518     memcpy(&buffer[_acceleratorInfoHeader.rangeTableOffset],   &_rangeTable[0],      _rangeTable.size()*sizeof(dyld_cache_range_entry));
 519     memcpy(&buffer[_acceleratorInfoHeader.dylibTrieOffset],    &_trieBytes[0],       _trieBytes.size());
 520 }
 521
 522
 523
 524 template <typename P>
 525 LinkeditOptimizer<P>::LinkeditOptimizer(void* cacheBuffer, macho_header<P>* mh, Diagnostics& diag)
 526 : _mh(mh), _cacheBuffer(cacheBuffer), _diagnostics(diag)
 527 {
 528     const unsigned origLoadCommandsSize = mh->sizeofcmds();
 529     unsigned bytesRemaining = origLoadCommandsSize;
 530     unsigned removedCount = 0;
 531     uint64_t    textSegAddr = 0;
 532     int64_t     slide = 0;
 533     const macho_load_command<P>* const cmds = (macho_load_command<P>*)((uint8_t*)mh + sizeof(macho_header<P>));
 534     const uint32_t cmdCount = mh->ncmds();
 535     const macho_load_command<P>* cmd = cmds;
 536     const macho_dylib_command<P>* dylibCmd;
 537     const macho_routines_command<P>* routinesCmd;
 538     macho_segment_command<P>* segCmd;
 539     for (uint32_t i = 0; i < cmdCount; ++i) {
 540         bool remove = false;
 541         switch (cmd->cmd()) {
 542             case LC_ID_DYLIB:
 543                 _installName = ((macho_dylib_command<P>*)cmd)->name();
 544                 break;
 545             case LC_SYMTAB:
 546                 _symTabCmd = (macho_symtab_command<P>*)cmd;
 547                 break;
 548             case LC_DYSYMTAB:
 549                 _dynSymTabCmd = (macho_dysymtab_command<P>*)cmd;
 550                 break;
 551             case LC_DYLD_INFO:
 552             case LC_DYLD_INFO_ONLY:
 553                 _dyldInfo = (macho_dyld_info_command<P>*)cmd;
 554                 _exportInfoSize = _dyldInfo->export_size();
 555                 break;
 556             case LC_FUNCTION_STARTS:
 557                 _functionStartsCmd = (macho_linkedit_data_command<P>*)cmd;
 558                 break;
 559             case LC_DATA_IN_CODE:
 560                 _dataInCodeCmd = (macho_linkedit_data_command<P>*)cmd;
 561                 break;
 562             case LC_DYLD_EXPORTS_TRIE:
 563                 _exportTrieCmd = (macho_linkedit_data_command<P>*)cmd;
 564                 _exportInfoSize = _exportTrieCmd->datasize();
 565                 break;
 566             case LC_ROUTINES:
 567             case LC_ROUTINES_64:
 568                 routinesCmd = (macho_routines_command<P>*)cmd;
 569                 _initializerAddresses.push_back(routinesCmd->init_address());
 570                 break;
 571             case LC_REEXPORT_DYLIB:
 572             case LC_LOAD_DYLIB:
 573             case LC_LOAD_WEAK_DYLIB:
 574             case LC_LOAD_UPWARD_DYLIB:
 575                 dylibCmd = (macho_dylib_command<P>*)cmd;
 576                 _allDependentPaths.push_back(dylibCmd->name());
 577                 if ( cmd->cmd() != LC_LOAD_UPWARD_DYLIB )
 578                     _downDependentPaths.push_back(dylibCmd->name());
 579                 if ( cmd->cmd() == LC_REEXPORT_DYLIB )
 580                     _reExportPaths.push_back(dylibCmd->name());
 581                break;
 582             case macho_segment_command<P>::CMD:
 583                 segCmd = (macho_segment_command<P>*)cmd;
 584                 _segCmds.push_back(segCmd);
 585                 if ( strcmp(segCmd->segname(), "__TEXT") == 0 ) {
 586                     textSegAddr = segCmd->vmaddr();
 587                     slide = (uint64_t)mh - textSegAddr;
 588                 }
 589                 else if ( strcmp(segCmd->segname(), "__LINKEDIT") == 0 ) {
 590                     _linkeditAddr        = segCmd->vmaddr();
 591                     _linkeditBias        = (uint8_t*)mh + (_linkeditAddr - textSegAddr) - segCmd->fileoff();
 592                     _linkeditSize        = (uint32_t)segCmd->vmsize();
 593                 }
 594                 else if ( segCmd->nsects() > 0 ) {
 595                     macho_section<P>* const sectionsStart = (macho_section<P>*)((uint8_t*)segCmd + sizeof(macho_segment_command<P>));
 596                     macho_section<P>* const sectionsEnd = &sectionsStart[segCmd->nsects()];
 597                     for (macho_section<P>* sect=sectionsStart; sect < sectionsEnd; ++sect) {
 598                         const uint8_t type = sect->flags() & SECTION_TYPE;
 599                         if ( type == S_MOD_INIT_FUNC_POINTERS ) {
 600                             const pint_t* inits = (pint_t*)(sect->addr()+slide);
 601                             const size_t count = sect->size() / sizeof(pint_t);
 602                             for (size_t j=0; j < count; ++j) {
 603                                 uint64_t func = P::getP(inits[j]);
 604                                 _initializerAddresses.push_back(func);
 605                             }
 606                         }
 607                         else if ( type == S_INIT_FUNC_OFFSETS ) {
 608                             const uint32_t* inits = (uint32_t*)(sect->addr()+slide);
 609                             const size_t count = sect->size() / sizeof(uint32_t);
 610                             for (size_t j=0; j < count; ++j) {
 611                                 uint32_t funcOffset = E::get32(inits[j]);
 612                                 _initializerAddresses.push_back(textSegAddr + funcOffset);
 613                             }
 614                         }
 615                         else if ( type == S_DTRACE_DOF ) {
 616                             _dofSections.push_back(sect);
 617                         }
 618                         else if ( (strcmp(sect->sectname(), "__dyld") == 0) && (strncmp(sect->segname(), "__DATA", 6) == 0) ) {
 619                             _dyldSectionAddr = sect->addr();
 620                         }
 621                     }
 622                 }
 623                 break;
 624             case LC_SEGMENT_SPLIT_INFO:
 625                 remove = true;
 626                 break;
 627         }
 628         uint32_t cmdSize = cmd->cmdsize();
 629         macho_load_command<P>* nextCmd = (macho_load_command<P>*)(((uint8_t*)cmd)+cmdSize);
 630         if ( remove ) {
 631             ::memmove((void*)cmd, (void*)nextCmd, bytesRemaining);
 632             ++removedCount;
 633         }
 634         else {
 635             bytesRemaining -= cmdSize;
 636             cmd = nextCmd;
 637         }
 638     }
 639     // zero out stuff removed
 640     ::bzero((void*)cmd, bytesRemaining);
 641     // update header
 642     mh->set_ncmds(cmdCount - removedCount);
 643     mh->set_sizeofcmds(origLoadCommandsSize - bytesRemaining);
 644 }
 645
 646 /*
 647 static void dumpLoadCommands(const uint8_t* mheader)
 648 {
 649     const mach_header* const mh = (mach_header*)mheader;
 650     const uint32_t cmd_count = mh->ncmds;
 651     bool is64 = (mh->magic == MH_MAGIC_64);
 652     const load_command* cmds = (load_command*)(mheader + (is64 ? sizeof(mach_header_64) : sizeof(mach_header)));
 653     const load_command* cmd = cmds;
 654     const segment_command* segCmd;
 655     const segment_command_64* seg64Cmd;
 656     const symtab_command* symTab;
 657     const linkedit_data_command* leData;
 658     const uint8_t* linkEditBias = NULL;
 659     for (uint32_t i = 0; i < cmd_count; ++i) {
 660         switch (cmd->cmd) {
 661             case LC_SEGMENT:
 662                 segCmd = (const segment_command*)cmd;
 663                 printf("LC_SEGMENT\n");
 664                 printf("  segname  = %s\n",     segCmd->segname);
 665                 printf("  vmaddr   = 0x%08X\n", segCmd->vmaddr);
 666                 printf("  vmsize   = 0x%08X\n", segCmd->vmsize);
 667                 printf("  fileoff  = 0x%08X\n", segCmd->fileoff);
 668                 printf("  filesize = 0x%08X\n", segCmd->filesize);
 669                 if ( strcmp(segCmd->segname, "__TEXT") == 0 ) {
 670                     linkEditBias = mheader - segCmd->fileoff;
 671                 }
 672                  break;
 673             case LC_SEGMENT_64:
 674                 seg64Cmd = (const segment_command_64*)cmd;
 675                 printf("LC_SEGMENT_64\n");
 676                 printf("  segname  = %s\n",        seg64Cmd->segname);
 677                 printf("  vmaddr   = 0x%09llX\n",  seg64Cmd->vmaddr);
 678                 printf("  vmsize   = 0x%09llX\n",  seg64Cmd->vmsize);
 679                 printf("  fileoff  = 0x%09llX\n",  seg64Cmd->fileoff);
 680                 printf("  filesize = 0x%09llX\n",  seg64Cmd->filesize);
 681                 if ( strcmp(seg64Cmd->segname, "__TEXT") == 0 ) {
 682                     linkEditBias = mheader - seg64Cmd->fileoff;
 683                 }
 684                 break;
 685             case LC_SYMTAB:
 686                 symTab = (const symtab_command*)cmd;
 687                 printf("LC_SYMTAB\n");
 688                 printf("  symoff   = 0x%08X\n", symTab->symoff);
 689                 printf("  nsyms    = 0x%08X\n", symTab->nsyms);
 690                 printf("  stroff   = 0x%08X\n", symTab->stroff);
 691                 printf("  strsize  = 0x%08X\n", symTab->strsize);
 692                 {
 693                 const char* strPool = (char*)&linkEditBias[symTab->stroff];
 694                 const nlist_64* sym0 = (nlist_64*)(&linkEditBias[symTab->symoff]);
 695                 printf("    sym[0].n_strx = 0x%08X (%s)\n", sym0->n_un.n_strx, &strPool[sym0->n_un.n_strx]);
 696                 printf("    sym[0].n_type = 0x%02X\n", sym0->n_type);
 697                 printf("    sym[0].n_sect = 0x%02X\n", sym0->n_sect);
 698                 printf("    sym[0].n_desc = 0x%04X\n", sym0->n_desc);
 699                 printf("    sym[0].n_value = 0x%llX\n", sym0->n_value);
 700                 const nlist_64* sym1 = (nlist_64*)(&linkEditBias[symTab->symoff+16]);
 701                 printf("    sym[1].n_strx = 0x%08X (%s)\n", sym1->n_un.n_strx, &strPool[sym1->n_un.n_strx]);
 702                 printf("    sym[1].n_type = 0x%02X\n", sym1->n_type);
 703                 printf("    sym[1].n_sect = 0x%02X\n", sym1->n_sect);
 704                 printf("    sym[1].n_desc = 0x%04X\n", sym1->n_desc);
 705                 printf("    sym[1].n_value = 0x%llX\n", sym1->n_value);
 706                 }
 707                  break;
 708             case LC_FUNCTION_STARTS:
 709                 leData = (const linkedit_data_command*)cmd;
 710                 printf("LC_FUNCTION_STARTS\n");
 711                 printf("  dataoff  = 0x%08X\n", leData->dataoff);
 712                 printf("  datasize = 0x%08X\n", leData->datasize);
 713             default:
 714                 //printf("0x%08X\n", cmd->cmd);
 715                 break;
 716         }
 717         cmd = (const load_command*)(((uint8_t*)cmd)+cmd->cmdsize);
 718     }
 719 }
 720 */
 721
 722 template <typename P>
 723 void LinkeditOptimizer<P>::updateLoadCommands(uint32_t mergedLinkeditStartOffset, uint64_t mergedLinkeditAddr, uint64_t newLinkeditSize,
 724                                               uint32_t sharedSymbolTableStartOffset, uint32_t sharedSymbolTableCount,
 725                                               uint32_t sharedSymbolStringsOffset, uint32_t sharedSymbolStringsSize)
 726 {
 727     // update __LINKEDIT segment in all dylibs to overlap the same shared region
 728     for (macho_segment_command<P>* segCmd : _segCmds) {
 729         if ( strcmp(segCmd->segname(), "__LINKEDIT") == 0 ) {
 730             segCmd->set_vmaddr(mergedLinkeditAddr);
 731             segCmd->set_vmsize(newLinkeditSize);
 732             segCmd->set_fileoff(mergedLinkeditStartOffset);
 733             segCmd->set_filesize(newLinkeditSize);
 734         }
 735         else if ( strcmp(segCmd->segname(), "__TEXT") == 0 ) {
 736             // HACK until lldb fixed in: <rdar://problem/20357466> DynamicLoaderMacOSXDYLD fixes for Monarch dyld shared cache
 737             //segCmd->set_fileoff(0);
 738
 739         }
 740    }
 741
 742     // update symbol table to point to shared symbol table
 743     _symTabCmd->set_symoff(mergedLinkeditStartOffset + sharedSymbolTableStartOffset + _newLocalSymbolsStartIndex*sizeof(macho_nlist<P>));
 744     _symTabCmd->set_nsyms(_newLocalSymbolCount+_newExportedSymbolCount+_newImportedSymbolCount);
 745     _symTabCmd->set_stroff(mergedLinkeditStartOffset + sharedSymbolStringsOffset);
 746     _symTabCmd->set_strsize(sharedSymbolStringsSize);
 747
 748     // update dynamic symbol table to have proper offsets into shared symbol table
 749     _dynSymTabCmd->set_ilocalsym(0);
 750     _dynSymTabCmd->set_nlocalsym(_newLocalSymbolCount);
 751     _dynSymTabCmd->set_iextdefsym(_newExportedSymbolsStartIndex-_newLocalSymbolsStartIndex);
 752     _dynSymTabCmd->set_nextdefsym(_newExportedSymbolCount);
 753     _dynSymTabCmd->set_iundefsym(_newImportedSymbolsStartIndex-_newLocalSymbolsStartIndex);
 754     _dynSymTabCmd->set_nundefsym(_newImportedSymbolCount);
 755     _dynSymTabCmd->set_tocoff(0);
 756     _dynSymTabCmd->set_ntoc(0);
 757     _dynSymTabCmd->set_modtaboff(0);
 758     _dynSymTabCmd->set_nmodtab(0);
 759     _dynSymTabCmd->set_indirectsymoff(mergedLinkeditStartOffset + _newIndirectSymbolTableOffset);
 760     _dynSymTabCmd->set_extreloff(0);
 761     _dynSymTabCmd->set_locreloff(0);
 762     _dynSymTabCmd->set_nlocrel(0);
 763
 764     // update dyld info
 765     if ( _dyldInfo != nullptr ) {
 766         _dyldInfo->set_rebase_off(0);
 767         _dyldInfo->set_rebase_size(0);
 768         _dyldInfo->set_bind_off(_dyldInfo->bind_size() ?  mergedLinkeditStartOffset + _newBindingInfoOffset : 0);
 769         _dyldInfo->set_weak_bind_off(_dyldInfo->weak_bind_size() ?  mergedLinkeditStartOffset + _newWeakBindingInfoOffset : 0 );
 770         _dyldInfo->set_lazy_bind_off(_dyldInfo->lazy_bind_size() ?  mergedLinkeditStartOffset + _newLazyBindingInfoOffset : 0 );
 771         _dyldInfo->set_export_off(mergedLinkeditStartOffset + _newExportInfoOffset);
 772     } else if ( _exportTrieCmd != nullptr ) {
 773         _exportTrieCmd->set_dataoff(mergedLinkeditStartOffset + _newExportInfoOffset);
 774     }
 775
 776     // update function-starts
 777     if ( _functionStartsCmd != nullptr )
 778         _functionStartsCmd->set_dataoff(mergedLinkeditStartOffset+_newFunctionStartsOffset);
 779
 780     // update data-in-code
 781     if ( _dataInCodeCmd != nullptr )
 782         _dataInCodeCmd->set_dataoff(mergedLinkeditStartOffset+_newDataInCodeOffset);
 783 }
 784
 785 template <typename P>
 786 void LinkeditOptimizer<P>::copyWeakBindingInfo(uint8_t* newLinkEditContent, uint32_t& offset)
 787 {
 788     if ( _dyldInfo == nullptr )
 789         return;
 790     unsigned size = _dyldInfo->weak_bind_size();
 791     if ( size != 0 ) {
 792         ::memcpy(&newLinkEditContent[offset], &_linkeditBias[_dyldInfo->weak_bind_off()], size);
 793         _newWeakBindingInfoOffset = offset;
 794         _newWeakBindingSize = size;
 795         offset += size;
 796     }
 797 }
 798
 799
 800 template <typename P>
 801 void LinkeditOptimizer<P>::copyLazyBindingInfo(uint8_t* newLinkEditContent, uint32_t& offset)
 802 {
 803     if ( _dyldInfo == nullptr )
 804         return;
 805     unsigned size = _dyldInfo->lazy_bind_size();
 806     if ( size != 0 ) {
 807         ::memcpy(&newLinkEditContent[offset], &_linkeditBias[_dyldInfo->lazy_bind_off()], size);
 808         _newLazyBindingInfoOffset = offset;
 809         offset += size;
 810     }
 811 }
 812
 813 template <typename P>
 814 void LinkeditOptimizer<P>::copyBindingInfo(uint8_t* newLinkEditContent, uint32_t& offset)
 815 {
 816     if ( _dyldInfo == nullptr )
 817         return;
 818     unsigned size = _dyldInfo->bind_size();
 819     if ( size != 0 ) {
 820         ::memcpy(&newLinkEditContent[offset], &_linkeditBias[_dyldInfo->bind_off()], size);
 821         _newBindingInfoOffset = offset;
 822         offset += size;
 823     }
 824 }
 825
 826 template <typename P>
 827 void LinkeditOptimizer<P>::copyExportInfo(uint8_t* newLinkEditContent, uint32_t& offset)
 828 {
 829     if ( (_dyldInfo == nullptr) && (_exportTrieCmd == nullptr) )
 830         return;
 831
 832     uint32_t exportOffset = _exportTrieCmd ? _exportTrieCmd->dataoff() : _dyldInfo->export_off();
 833     uint32_t exportSize   = _exportTrieCmd ? _exportTrieCmd->datasize() : _dyldInfo->export_size();
 834     if ( exportSize != 0 ) {
 835         ::memcpy(&newLinkEditContent[offset], &_linkeditBias[exportOffset], exportSize);
 836         _newExportInfoOffset = offset;
 837         offset += exportSize;
 838     }
 839 }
 840
 841
 842 template <typename P>
 843 void LinkeditOptimizer<P>::copyFunctionStarts(uint8_t* newLinkEditContent, uint32_t& offset)
 844 {
 845     if ( _functionStartsCmd == nullptr )
 846         return;
 847     unsigned size = _functionStartsCmd->datasize();
 848     ::memcpy(&newLinkEditContent[offset], &_linkeditBias[_functionStartsCmd->dataoff()], size);
 849     _newFunctionStartsOffset = offset;
 850     offset += size;
 851 }
 852
 853 template <typename P>
 854 void LinkeditOptimizer<P>::copyDataInCode(uint8_t* newLinkEditContent, uint32_t& offset)
 855 {
 856     if ( _dataInCodeCmd == nullptr )
 857         return;
 858     unsigned size = _dataInCodeCmd->datasize();
 859     ::memcpy(&newLinkEditContent[offset], &_linkeditBias[_dataInCodeCmd->dataoff()], size);
 860     _newDataInCodeOffset = offset;
 861     offset += size;
 862 }
 863
 864
 865 template <typename P>
 866 void LinkeditOptimizer<P>::copyLocalSymbols(uint8_t* newLinkEditContent, SortedStringPool<P>& stringPool, uint32_t& offset, uint32_t& symbolIndex,
 867                                             bool redact, std::vector<LocalSymbolInfo>& localSymbolInfos,
 868                                             std::vector<macho_nlist<P>>& unmappedLocalSymbols, SortedStringPool<P>& localSymbolsStringPool)
 869 {
 870     LocalSymbolInfo localInfo;
 871     localInfo.dylibOffset = (uint32_t)(((uint8_t*)_mh) - (uint8_t*)_cacheBuffer);
 872     localInfo.nlistStartIndex = (uint32_t)unmappedLocalSymbols.size();
 873     localInfo.nlistCount = 0;
 874     _newLocalSymbolsStartIndex = symbolIndex;
 875     const char* strings = (char*)&_linkeditBias[_symTabCmd->stroff()];
 876     const macho_nlist<P>* const symbolTable = (macho_nlist<P>*)(&_linkeditBias[_symTabCmd->symoff()]);
 877     const macho_nlist<P>* const firstExport = &symbolTable[_dynSymTabCmd->ilocalsym()];
 878     const macho_nlist<P>* const lastExport  = &symbolTable[_dynSymTabCmd->ilocalsym()+_dynSymTabCmd->nlocalsym()];
 879     for (const macho_nlist<P>* entry = firstExport; entry < lastExport; ++entry) {
 880         if ( (entry->n_type() & N_TYPE) != N_SECT)
 881             continue;
 882          if ( (entry->n_type() & N_STAB) != 0)
 883             continue;
 884         const char* name = &strings[entry->n_strx()];
 885         macho_nlist<P>* newSymbolEntry = (macho_nlist<P>*)&newLinkEditContent[offset];
 886         *newSymbolEntry = *entry;
 887         if ( redact ) {
 888             // if removing local symbols, change __text symbols to "<redacted>" so backtraces don't have bogus names
 889             if ( entry->n_sect() == 1 ) {
 890                 stringPool.add(symbolIndex, "<redacted>");
 891                 ++symbolIndex;
 892                 offset += sizeof(macho_nlist<P>);
 893             }
 894             // copy local symbol to unmmapped locals area
 895             localSymbolsStringPool.add((uint32_t)unmappedLocalSymbols.size(), name);
 896             unmappedLocalSymbols.push_back(*entry);
 897             unmappedLocalSymbols.back().set_n_strx(0);
 898         }
 899         else {
 900             stringPool.add(symbolIndex, name);
 901             ++symbolIndex;
 902             offset += sizeof(macho_nlist<P>);
 903        }
 904     }
 905     _newLocalSymbolCount = symbolIndex - _newLocalSymbolsStartIndex;
 906     localInfo.nlistCount = (uint32_t)unmappedLocalSymbols.size() - localInfo.nlistStartIndex;
 907     localSymbolInfos.push_back(localInfo);
 908 }
 909
 910
 911 template <typename P>
 912 void LinkeditOptimizer<P>::copyExportedSymbols(uint8_t* newLinkEditContent, SortedStringPool<P>& stringPool, uint32_t& offset, uint32_t& symbolIndex)
 913 {
 914     _newExportedSymbolsStartIndex = symbolIndex;
 915     const char* strings = (char*)&_linkeditBias[_symTabCmd->stroff()];
 916     const macho_nlist<P>* const symbolTable = (macho_nlist<P>*)(&_linkeditBias[_symTabCmd->symoff()]);
 917     const macho_nlist<P>* const firstExport = &symbolTable[_dynSymTabCmd->iextdefsym()];
 918     const macho_nlist<P>* const lastExport  = &symbolTable[_dynSymTabCmd->iextdefsym()+_dynSymTabCmd->nextdefsym()];
 919     uint32_t oldSymbolIndex = _dynSymTabCmd->iextdefsym();
 920     for (const macho_nlist<P>* entry = firstExport; entry < lastExport; ++entry, ++oldSymbolIndex) {
 921         if ( (entry->n_type() & N_TYPE) != N_SECT)
 922             continue;
 923         const char* name = &strings[entry->n_strx()];
 924         if ( strncmp(name, ".objc_", 6) == 0 )
 925             continue;
 926         if ( strncmp(name, "$ld$", 4) == 0 )
 927             continue;
 928         macho_nlist<P>* newSymbolEntry = (macho_nlist<P>*)&newLinkEditContent[offset];
 929         *newSymbolEntry = *entry;
 930         newSymbolEntry->set_n_strx(0);
 931         stringPool.add(symbolIndex, name);
 932         _oldToNewSymbolIndexes[oldSymbolIndex] = symbolIndex - _newLocalSymbolsStartIndex;
 933         ++symbolIndex;
 934         offset += sizeof(macho_nlist<P>);
 935     }
 936     _newExportedSymbolCount = symbolIndex - _newExportedSymbolsStartIndex;
 937 }
 938
 939 template <typename P>
 940 void LinkeditOptimizer<P>::copyImportedSymbols(uint8_t* newLinkEditContent, SortedStringPool<P>& stringPool, uint32_t& offset, uint32_t& symbolIndex)
 941 {
 942     _newImportedSymbolsStartIndex = symbolIndex;
 943     const char* strings = (char*)&_linkeditBias[_symTabCmd->stroff()];
 944     const macho_nlist<P>* const symbolTable = (macho_nlist<P>*)(&_linkeditBias[_symTabCmd->symoff()]);
 945     const macho_nlist<P>* const firstImport = &symbolTable[_dynSymTabCmd->iundefsym()];
 946     const macho_nlist<P>* const lastImport  = &symbolTable[_dynSymTabCmd->iundefsym()+_dynSymTabCmd->nundefsym()];
 947     uint32_t oldSymbolIndex = _dynSymTabCmd->iundefsym();
 948     for (const macho_nlist<P>* entry = firstImport; entry < lastImport; ++entry, ++oldSymbolIndex) {
 949         if ( (entry->n_type() & N_TYPE) != N_UNDF)
 950             continue;
 951         const char* name = &strings[entry->n_strx()];
 952         macho_nlist<P>* newSymbolEntry = (macho_nlist<P>*)&newLinkEditContent[offset];
 953         *newSymbolEntry = *entry;
 954         newSymbolEntry->set_n_strx(0);
 955         stringPool.add(symbolIndex, name);
 956         _oldToNewSymbolIndexes[oldSymbolIndex] = symbolIndex - _newLocalSymbolsStartIndex;
 957         ++symbolIndex;
 958         offset += sizeof(macho_nlist<P>);
 959     }
 960     _newImportedSymbolCount = symbolIndex - _newImportedSymbolsStartIndex;
 961 }
 962
 963 template <typename P>
 964 void LinkeditOptimizer<P>::copyIndirectSymbolTable(uint8_t* newLinkEditContent, uint32_t& offset)
 965 {
 966     _newIndirectSymbolTableOffset = offset;
 967      const uint32_t* const indirectTable = (uint32_t*)&_linkeditBias[_dynSymTabCmd->indirectsymoff()];
 968     uint32_t* newIndirectTable = (uint32_t*)&newLinkEditContent[offset];
 969     for (uint32_t i=0; i < _dynSymTabCmd->nindirectsyms(); ++i) {
 970         uint32_t symbolIndex = E::get32(indirectTable[i]);
 971         if ( (symbolIndex == INDIRECT_SYMBOL_ABS) || (symbolIndex == INDIRECT_SYMBOL_LOCAL) )
 972             E::set32(newIndirectTable[i], symbolIndex);
 973         else
 974             E::set32(newIndirectTable[i], _oldToNewSymbolIndexes[symbolIndex]);
 975         offset += sizeof(uint32_t);
 976     }
 977 }
 978
 979 template <typename P>
 980 void LinkeditOptimizer<P>::mergeLinkedits(CacheBuilder& builder, std::vector<LinkeditOptimizer<P>*>& optimizers)
 981 {
 982     // allocate space for new linkedit data
 983     uint64_t totalUnoptLinkeditsSize = builder._readOnlyRegion.sizeInUse - builder._nonLinkEditReadOnlySize;
 984     uint8_t* newLinkEdit = (uint8_t*)calloc(totalUnoptLinkeditsSize, 1);
 985     SortedStringPool<P> stringPool;
 986     uint32_t offset = 0;
 987
 988     builder._diagnostics.verbose("Merged LINKEDIT:\n");
 989
 990     // copy weak binding info
 991     uint32_t startWeakBindInfosOffset = offset;
 992     for (LinkeditOptimizer<P>* op : optimizers) {
 993         // Skip chained fixups as the in-place linked list isn't valid any more
 994         const dyld3::MachOFile* mf = (dyld3::MachOFile*)op->machHeader();
 995         if (!mf->hasChainedFixups())
 996             op->copyWeakBindingInfo(newLinkEdit, offset);
 997     }
 998     builder._diagnostics.verbose("  weak bindings size:      %5uKB\n", (uint32_t)(offset-startWeakBindInfosOffset)/1024);
 999
1000     // copy export info
1001     uint32_t startExportInfosOffset = offset;
1002     for (LinkeditOptimizer<P>* op : optimizers) {
1003         op->copyExportInfo(newLinkEdit, offset);
1004     }
1005     builder._diagnostics.verbose("  exports info size:       %5uKB\n", (uint32_t)(offset-startExportInfosOffset)/1024);
1006
1007     // in theory, an optimized cache can drop the binding info
1008     if ( true ) {
1009         // copy binding info
1010         uint32_t startBindingsInfosOffset = offset;
1011         for (LinkeditOptimizer<P>* op : optimizers) {
1012             // Skip chained fixups as the in-place linked list isn't valid any more
1013             const dyld3::MachOFile* mf = (dyld3::MachOFile*)op->machHeader();
1014             if (!mf->hasChainedFixups())
1015                 op->copyBindingInfo(newLinkEdit, offset);
1016         }
1017         builder._diagnostics.verbose("  bindings size:           %5uKB\n", (uint32_t)(offset-startBindingsInfosOffset)/1024);
1018
1019        // copy lazy binding info
1020         uint32_t startLazyBindingsInfosOffset = offset;
1021         for (LinkeditOptimizer<P>* op : optimizers) {
1022             // Skip chained fixups as the in-place linked list isn't valid any more
1023             const dyld3::MachOFile* mf = (dyld3::MachOFile*)op->machHeader();
1024             if (!mf->hasChainedFixups())
1025                 op->copyLazyBindingInfo(newLinkEdit, offset);
1026         }
1027         builder._diagnostics.verbose("  lazy bindings size:      %5uKB\n", (offset-startLazyBindingsInfosOffset)/1024);
1028     }
1029
1030     // copy symbol table entries
1031     std::vector<macho_nlist<P>> unmappedLocalSymbols;
1032     if ( builder._options.excludeLocalSymbols )
1033         unmappedLocalSymbols.reserve(0x01000000);
1034     std::vector<LocalSymbolInfo> localSymbolInfos;
1035         localSymbolInfos.reserve(optimizers.size());
1036     SortedStringPool<P> localSymbolsStringPool;
1037     uint32_t symbolIndex = 0;
1038     const uint32_t sharedSymbolTableStartOffset = offset;
1039     uint32_t sharedSymbolTableExportsCount = 0;
1040     uint32_t sharedSymbolTableImportsCount = 0;
1041     for (LinkeditOptimizer<P>* op : optimizers) {
1042          op->copyLocalSymbols(newLinkEdit, stringPool, offset, symbolIndex, builder._options.excludeLocalSymbols,
1043                              localSymbolInfos, unmappedLocalSymbols, localSymbolsStringPool);
1044         uint32_t x = symbolIndex;
1045         op->copyExportedSymbols(newLinkEdit, stringPool, offset, symbolIndex);
1046         sharedSymbolTableExportsCount += (symbolIndex-x);
1047         uint32_t y = symbolIndex;
1048         op->copyImportedSymbols(newLinkEdit, stringPool, offset, symbolIndex);
1049         sharedSymbolTableImportsCount += (symbolIndex-y);
1050     }
1051     uint32_t sharedSymbolTableCount = symbolIndex;
1052     const uint32_t sharedSymbolTableEndOffset = offset;
1053
1054     // copy function starts
1055     uint32_t startFunctionStartsOffset = offset;
1056     for (LinkeditOptimizer<P>* op : optimizers) {
1057         op->copyFunctionStarts(newLinkEdit, offset);
1058     }
1059     builder._diagnostics.verbose("  function starts size:    %5uKB\n", (offset-startFunctionStartsOffset)/1024);
1060
1061     // copy data-in-code info
1062     uint32_t startDataInCodeOffset = offset;
1063     for (LinkeditOptimizer<P>* op : optimizers) {
1064         op->copyDataInCode(newLinkEdit, offset);
1065     }
1066     builder._diagnostics.verbose("  data in code size:       %5uKB\n", (offset-startDataInCodeOffset)/1024);
1067
1068     // copy indirect symbol tables
1069     for (LinkeditOptimizer<P>* op : optimizers) {
1070         op->copyIndirectSymbolTable(newLinkEdit, offset);
1071     }
1072     // if indirect table has odd number of entries, end will not be 8-byte aligned
1073     if ( (offset % sizeof(typename P::uint_t)) != 0 )
1074         offset += 4;
1075
1076     // copy string pool
1077     uint32_t sharedSymbolStringsOffset = offset;
1078     uint32_t sharedSymbolStringsSize = stringPool.copyPoolAndUpdateOffsets((char*)&newLinkEdit[sharedSymbolStringsOffset], (macho_nlist<P>*)&newLinkEdit[sharedSymbolTableStartOffset]);
1079     offset += sharedSymbolStringsSize;
1080     uint32_t newLinkeditUnalignedSize = offset;
1081     uint64_t newLinkeditAlignedSize = align(offset, 14);
1082     builder._diagnostics.verbose("  symbol table size:       %5uKB (%d exports, %d imports)\n", (sharedSymbolTableEndOffset-sharedSymbolTableStartOffset)/1024, sharedSymbolTableExportsCount, sharedSymbolTableImportsCount);
1083     builder._diagnostics.verbose("  symbol string pool size: %5uKB\n", sharedSymbolStringsSize/1024);
1084     builder._sharedStringsPoolVmOffset = (uint32_t)((builder._readOnlyRegion.unslidLoadAddress - builder._readExecuteRegion.unslidLoadAddress) + builder._nonLinkEditReadOnlySize + sharedSymbolStringsOffset);
1085
1086     // overwrite mapped LINKEDIT area in cache with new merged LINKEDIT content
1087     builder._diagnostics.verbose("LINKEDITS optimized from %uMB to %uMB\n", (uint32_t)totalUnoptLinkeditsSize/(1024*1024), (uint32_t)newLinkeditUnalignedSize/(1024*1024));
1088     ::memcpy(builder._readOnlyRegion.buffer+builder._nonLinkEditReadOnlySize, newLinkEdit, newLinkeditAlignedSize);
1089     ::free(newLinkEdit);
1090     builder._readOnlyRegion.sizeInUse = builder._nonLinkEditReadOnlySize + newLinkeditAlignedSize;
1091
1092     // If making cache for customers, add extra accelerator tables for dyld
1093     DyldSharedCache* cacheHeader = (DyldSharedCache*)builder._readExecuteRegion.buffer;
1094     if ( builder._options.optimizeStubs ) {
1095         uint64_t addrWhereAccTablesWillBe     = builder._readOnlyRegion.unslidLoadAddress+builder._readOnlyRegion.sizeInUse;
1096         uint64_t addrWhereMergedLinkWillStart = builder._readOnlyRegion.unslidLoadAddress+builder._nonLinkEditReadOnlySize;
1097         AcceleratorTables<P> tables(cacheHeader, addrWhereMergedLinkWillStart, builder._diagnostics, optimizers);
1098         uint32_t tablesSize = tables.totalSize();
1099         if ( tablesSize < (builder._readOnlyRegion.bufferSize - builder._readOnlyRegion.sizeInUse) ) {
1100             tables.copyTo(builder._readOnlyRegion.buffer+builder._readOnlyRegion.sizeInUse);
1101             cacheHeader->header.accelerateInfoAddr = addrWhereAccTablesWillBe;
1102             cacheHeader->header.accelerateInfoSize = tablesSize;
1103             builder._readOnlyRegion.sizeInUse += align(tablesSize, 14);
1104             builder._diagnostics.verbose("Accelerator tables %uMB\n", (uint32_t)tablesSize/(1024*1024));
1105        }
1106         else {
1107             builder._diagnostics.warning("not enough room to add dyld accelerator tables");
1108         }
1109     }
1110
1111     // overwrite end of un-opt linkedits to create a new unmapped region for local symbols
1112     if ( builder._options.excludeLocalSymbols ) {
1113         const uint32_t entriesOffset = sizeof(dyld_cache_local_symbols_info);
1114         const uint32_t entriesCount  = (uint32_t)localSymbolInfos.size();
1115         const uint32_t nlistOffset   = (uint32_t)align(entriesOffset + entriesCount * sizeof(dyld_cache_local_symbols_info), 4); // 16-byte align start
1116         const uint32_t nlistCount    = (uint32_t)unmappedLocalSymbols.size();
1117         const uint32_t stringsSize   = (uint32_t)localSymbolsStringPool.size();
1118         const uint32_t stringsOffset = nlistOffset + nlistCount * sizeof(macho_nlist<P>);
1119         // allocate buffer for local symbols
1120         const size_t localsBufferSize = align(stringsOffset + stringsSize, 14);
1121         vm_address_t localsBuffer;
1122         if ( ::vm_allocate(mach_task_self(), &localsBuffer, localsBufferSize, VM_FLAGS_ANYWHERE) == 0 ) {
1123             dyld_cache_local_symbols_info* infoHeader = (dyld_cache_local_symbols_info*)localsBuffer;
1124             // fill in header info
1125             infoHeader->nlistOffset       = nlistOffset;
1126             infoHeader->nlistCount        = nlistCount;
1127             infoHeader->stringsOffset     = stringsOffset;
1128             infoHeader->stringsSize       = stringsSize;
1129             infoHeader->entriesOffset     = entriesOffset;
1130             infoHeader->entriesCount      = entriesCount;
1131             // copy info for each dylib
1132             dyld_cache_local_symbols_entry* entries = (dyld_cache_local_symbols_entry*)(((uint8_t*)infoHeader)+entriesOffset);
1133             for (uint32_t i=0; i < entriesCount; ++i) {
1134                 entries[i].dylibOffset        = localSymbolInfos[i].dylibOffset;
1135                 entries[i].nlistStartIndex    = localSymbolInfos[i].nlistStartIndex;
1136                 entries[i].nlistCount         = localSymbolInfos[i].nlistCount;
1137             }
1138             // copy nlists
1139             macho_nlist<P>* newLocalsSymbolTable = (macho_nlist<P>*)(localsBuffer+nlistOffset);
1140             ::memcpy(newLocalsSymbolTable, &unmappedLocalSymbols[0], nlistCount*sizeof(macho_nlist<P>));
1141             // copy string pool
1142             localSymbolsStringPool.copyPoolAndUpdateOffsets(((char*)infoHeader)+stringsOffset, newLocalsSymbolTable);
1143             // update cache header
1144             cacheHeader->header.localSymbolsSize    = localsBufferSize;
1145             // return buffer of local symbols, caller to free() it
1146             builder._localSymbolsRegion.buffer      = (uint8_t*)localsBuffer;
1147             builder._localSymbolsRegion.bufferSize  = localsBufferSize;
1148             builder._localSymbolsRegion.sizeInUse   = localsBufferSize;
1149         }
1150         else {
1151             builder._diagnostics.warning("could not allocate local symbols");
1152         }
1153     }
1154
1155     // update all load commands to new merged layout
1156     uint64_t linkeditsUnslidStartAddr = builder._readOnlyRegion.unslidLoadAddress + builder._nonLinkEditReadOnlySize;
1157     uint32_t linkeditsCacheFileOffset = (uint32_t)(builder._readOnlyRegion.cacheFileOffset + builder._nonLinkEditReadOnlySize);
1158     for (LinkeditOptimizer<P>* op : optimizers) {
1159         op->updateLoadCommands(linkeditsCacheFileOffset, linkeditsUnslidStartAddr, newLinkeditUnalignedSize,
1160                                sharedSymbolTableStartOffset, sharedSymbolTableCount,
1161                                sharedSymbolStringsOffset, sharedSymbolStringsSize);
1162     }
1163 }
1164
1165
1166 template <typename P>
1167 void LinkeditOptimizer<P>::optimizeLinkedit(CacheBuilder& builder)
1168 {
1169     DyldSharedCache* cache = (DyldSharedCache*)builder._readExecuteRegion.buffer;
1170     // construct a LinkeditOptimizer for each image
1171     __block std::vector<LinkeditOptimizer<P>*> optimizers;
1172     cache->forEachImage(^(const mach_header* mh, const char*) {
1173         optimizers.push_back(new LinkeditOptimizer<P>(cache, (macho_header<P>*)mh, builder._diagnostics));
1174     });
1175 #if 0
1176     // add optimizer for each branch pool
1177     for (uint64_t poolOffset : branchPoolOffsets) {
1178         macho_header<P>* mh =  (macho_header<P>*)((char*)cache + poolOffset);
1179         optimizers.push_back(new LinkeditOptimizer<P>(cache, mh, diag));
1180     }
1181 #endif
1182     // merge linkedit info
1183     mergeLinkedits(builder, optimizers);
1184
1185     // delete optimizers
1186     for (LinkeditOptimizer<P>* op : optimizers)
1187         delete op;
1188 }
1189
1190 void CacheBuilder::optimizeLinkedit()
1191 {
1192     if ( _archLayout->is64 ) {
1193         return LinkeditOptimizer<Pointer64<LittleEndian>>::optimizeLinkedit(*this);
1194     }
1195     else {
1196          return LinkeditOptimizer<Pointer32<LittleEndian>>::optimizeLinkedit(*this);
1197     }
1198 }
1199
1200
1201