dyld3/shared-cache/IMPCachesBuilder.hpp

   1 //
   2 //  IMPCachesBuilder.hpp
   3 //  dyld
   4 //
   5 //  Created by Thomas Deniau on 20/01/2020.
   6 //
   7
   8 #pragma once
   9
  10 #include "CacheBuilder.h"
  11 #include "IMPCaches.hpp"
  12 #include <random>
  13
  14 namespace IMPCaches {
  15
  16 class IMPCachesBuilder {
  17 public:
  18     SelectorMap selectors;
  19
  20     /// Parses source dylibs to figure out which methods end up in which caches
  21     bool parseDylibs(Diagnostics& diag);
  22
  23     /// Builds a map of the class hierarchy across all dylibs. This is especially used to resolve
  24     /// cross-dylib dependencies for superclasses and categories.
  25     void buildClassesMap(Diagnostics& diag);
  26
  27     /// The entry point of the algorithm
  28     void buildPerfectHashes(HoleMap& holeMap, Diagnostics& diag);
  29
  30     /// Regenerate the hole map if we needed to evict dylibs.
  31     void computeLowBits(HoleMap& holeMap);
  32
  33     // Total size the hash tables will need.
  34     size_t totalIMPCachesSize() const;
  35
  36     void clear() {
  37         // FIXME: Implement this
  38     }
  39
  40     /** Classes for which we want to generate IMP caches according to the input JSON config laid down by OrderFiles
  41      * The value is the index of the class in the json file (they are ordered by decreasing order of importance)
  42      * This isn't just a vector because we also need to test for membership quickly */
  43     std::unordered_map<std::string_view, int> neededClasses;
  44     std::unordered_map<std::string_view, int> neededMetaclasses;
  45
  46     // Classes for which we don't generate IMP caches, but which we need to track
  47     // to attach categories to them and find the right implementation for
  48     // inlined selectors
  49     std::unordered_set<std::string_view> trackedClasses;
  50     std::unordered_set<std::string_view> trackedMetaclasses;
  51
  52     // List of classes with the same name that appear in different images.
  53     // We should not try to play with fire and try to support duplicated
  54     // classes in IMP caches.
  55
  56     using ClassSet = std::unordered_set<ClassKey, ClassKeyHasher>;
  57     ClassSet duplicateClasses;
  58
  59     /// Selectors which we want to inline into child classes' caches.
  60     std::unordered_set<std::string_view> selectorsToInline;
  61     std::vector<const Selector*> inlinedSelectors;
  62
  63     // Class hierarchies to flatten:
  64     // In every class, include every selector including
  65     // the ones from superclasses up to the flattening root.
  66     // This lets us enable constant caches for some of the classes which are not leaves.
  67     // We avoid the pyramid of doom by making sure selectors from superclasses are
  68     // included in child caches, up until some flattening root, and msgSend will
  69     // fallback to the superclass of the flattening root if it can't find the selector
  70     // it expects.
  71     std::unordered_set<std::string_view> metaclassHierarchiesToFlatten;
  72     std::unordered_set<std::string_view> classHierarchiesToFlatten;
  73
  74     /// All the dylibs the algorith, works on.
  75     std::vector<CacheBuilder::DylibInfo> & dylibs;
  76
  77     IMPCachesBuilder(std::vector<CacheBuilder::DylibInfo>& allDylibs, const dyld3::json::Node& optimizerConfiguration, Diagnostics& diag, TimeRecorder& timeRecorder, const dyld3::closure::FileSystem& fileSystem);
  78
  79     struct ObjCClass {
  80
  81         const dyld3::MachOAnalyzer* superclassMA = nullptr;
  82         const uint8_t*      metaClass           = nullptr;
  83         const uint8_t*      superclass          = nullptr;
  84         uint64_t            methodListVMaddr    = 0;
  85         const char*         className           = nullptr;
  86         bool                isRootClass         = false;
  87         bool                isMetaClass         = false;
  88
  89         const IMPCaches::ClassData::ClassLocator superclassLocator() const {
  90             uint64_t loadAddress = superclassMA->preferredLoadAddress();
  91             __block std::optional<unsigned> segmentIndex;
  92             __block std::optional<unsigned> segmentOffset;
  93             uint64_t superclassVMAddr = (superclass - (const uint8_t*)superclassMA) + loadAddress;
  94             superclassMA->forEachSegment(^(const dyld3::MachOAnalyzer::SegmentInfo &info, bool &stop) {
  95                 if (info.vmAddr <= superclassVMAddr && (info.vmAddr + info.vmSize) > superclassVMAddr) {
  96                     segmentIndex = info.segIndex;
  97                     segmentOffset = (unsigned)(superclassVMAddr - info.vmAddr);
  98                     stop = true;
  99                     return;
 100                 }
 101             });
 102             assert(segmentIndex.has_value() && segmentOffset.has_value());
 103             return IMPCaches::ClassData::ClassLocator {
 104                 .installName = superclassMA->installName(),
 105                 .segmentIndex = *segmentIndex,
 106                 .segmentOffset = *segmentOffset,
 107             };
 108         }
 109     };
 110     struct ObjCCategory {
 111         const dyld3::MachOAnalyzer* classMA = nullptr;
 112         const uint8_t* cls = nullptr;
 113     };
 114
 115 private:
 116
 117     /// Is this a class for which we want to generate an IMP cache?
 118     bool isClassInteresting(const ObjCClass& theClass) const;
 119
 120     /// Is this a class for which we want to generate an IMP cache, or on which we want to track method attachment by categories?
 121     bool isClassInterestingOrTracked(const ObjCClass& theClass) const;
 122
 123     /// Adds a method to a given class's cache.
 124     void addMethod(IMPCaches::ClassData* classDataPtr, const char* methodName, const char* installName, const char* className, const char* catName, bool inlined, bool fromFlattening);
 125
 126     /// Inline a method from a parent's cache to a child's cache.
 127     void inlineMethodIfNeeded(IMPCaches::ClassData* classToInlineIn, const char* classToInlineFrom, const char* catToInlineFrom, const char* installNameToInlineFrom, const char* name, std::set<Selector*> & seenSelectors, bool isFlattening);
 128
 129     /// Map from location (address in the mmapped source dylib) to class info built by buildClassesMap()
 130     std::unordered_map<const uint8_t*, ObjCClass> objcClasses;
 131
 132     /// Map from location (address in the mmapped source dylib) to category info built by buildClassesMap()
 133     std::unordered_map<const uint8_t*, ObjCCategory> objcCategories;
 134
 135     /// Address space where the selectors are going to live. Used to determine at which address we'll actually layout each selector.
 136     IMPCaches::AddressSpace addressSpace;
 137
 138     /// Find a shift and a mask for each class. Returns the number of classes that we could not place.
 139     int findShiftsAndMasks();
 140
 141     /// Shuffles selectors around to satisfy size constraints.  Returns the number of classes that we could not place.
 142     int solveGivenShiftsAndMasks();
 143
 144     /// Determine classes we need to track category attachment on (for later inlining)
 145     void buildTrackedClasses(CacheBuilder::DylibInfo& dylib, const dyld3::MachOAnalyzer* ma);
 146
 147     /// Parses the method lists in the source dylibs to determine what will end up in which IMP cache.
 148     void populateMethodLists(CacheBuilder::DylibInfo& dylib, const dyld3::MachOAnalyzer* ma, int* duplicateClassCount);
 149
 150     /// Go through categories and add the methods from the category to the corresponding class's IMP cache
 151     void attachCategories(CacheBuilder::DylibInfo& dylib, const dyld3::MachOAnalyzer* ma);
 152
 153     // Inline some selectors (driven by the OrderFiles) from parent caches into child caches.
 154     void inlineSelectors(CacheBuilder::DylibInfo& dylib, std::unordered_map<std::string_view, CacheBuilder::DylibInfo*> & dylibsByInstallName, const dyld3::MachOAnalyzer* ma);
 155
 156     void fillAllClasses(std::vector<IMPCaches::ClassData*> & allClasses);
 157     void fillAllMethods(std::vector<IMPCaches::Selector*> & allMethods);
 158     void removeUninterestingClasses();
 159
 160     struct TargetClassFindingResult {
 161         bool success;
 162         const dyld3::MachOLoaded* foundInDylib;
 163         const uint8_t* location;
 164     };
 165
 166     struct BindTarget {
 167         std::string                 symbolName      = "";
 168         const dyld3::MachOAnalyzer* targetDylib     = nullptr;
 169         bool                        isWeakImport    = false;
 170     };
 171
 172     struct DylibAndDeps {
 173         const dyld3::MachOAnalyzer*         ma = nullptr;
 174         __block std::vector<std::string>    dependentLibraries;
 175     };
 176
 177     TargetClassFindingResult findTargetClass(const dyld3::MachOAnalyzer* ma, uint64_t targetClassVMAddr, uint64_t targetClassPointerVMAddr, const char* logContext, const std::unordered_map<uint64_t, uint64_t> & bindLocations, std::vector<BindTarget> & bindTargets, std::unordered_map<std::string, DylibAndDeps> &dylibMap);
 178
 179     const std::string * nameAndIsMetaclassPairFromNode(const dyld3::json::Node & node, bool* metaclass);
 180
 181     Diagnostics& _diagnostics;
 182     TimeRecorder& _timeRecorder;
 183     const dyld3::closure::FileSystem& _fileSystem;
 184 };
 185
 186 }