dyld3/shared-cache/IMPCaches.hpp

   1 //
   2 //  IMPCaches.hpp
   3 //  dyld_shared_cache_builder
   4 //
   5 //  Created by Thomas Deniau on 18/12/2019.
   6 //
   7
   8 #ifndef IMPCaches_hpp
   9 #define IMPCaches_hpp
  10
  11 #include <vector>
  12 #include <unordered_map>
  13 #include <unordered_set>
  14 #include <set>
  15 #include <map>
  16 #include <string>
  17 #include <random>
  18
  19 #define DEBUG_SLOTS 1
  20
  21 template <typename P> class objc_method_t;
  22
  23 namespace IMPCaches {
  24 class Selector;
  25 class Constraint;
  26
  27 class ClassData {
  28 private:
  29 #if DEBUG_SLOTS
  30     std::vector<const Selector*> slots;
  31 #else
  32     std::vector<bool> slots;
  33 #endif
  34
  35     // Scratchpad for constraintForMethod
  36     std::vector<int> allowedValues;
  37
  38     void resetSlots();
  39
  40 public:
  41     bool isMetaclass;
  42
  43     // True most of the time, but can also be false in 2 cases:
  44     // * We have entries for classes for which we don't want to generate IMP caches
  45     //   when they are superclasses of "interesting" (= for which we want an IMP cache)
  46     //   classes, so that we can properly attach non-cross-image categories to them and
  47     //   reference the right IMP for child classes which are actually interesting
  48     // * We can also have failed to generate a cache for this class, or for a class
  49     //   in its flattening superclass hierarchy
  50     bool shouldGenerateImpCache;
  51
  52     // Class has duplicates or is a child of a class with duplicates.
  53     bool isPartOfDuplicateSet = false;
  54
  55     // This is set when we drop a class because a class in its flattening superclasss
  56     // hierarchy was dropped. In that case, we won't try to flip its shouldGenerateImpCache
  57     // value back to true when restoring a snapshot. (We could keep track of all the
  58     // dependencies but it would be very messy and the reward is only a few classes here and there).
  59     bool droppedBecauseFlatteningSuperclassWasDropped = false;
  60
  61     uint8_t backtracks = 0;
  62
  63     // For debug purposes
  64     const char* name;
  65
  66     struct Method {
  67         const char* installName = nullptr;
  68         const char* className = nullptr;
  69         const char* categoryName = nullptr;
  70         Selector* selector = nullptr;
  71         bool wasInlined = false;
  72         bool fromFlattening = false;
  73     };
  74
  75     std::vector<Method> methods;
  76
  77     std::string description() const;
  78
  79     int neededBits;
  80
  81     void didFinishAddingMethods();
  82
  83     // Not const because this uses the slots as a scratchpad
  84     Constraint constraintForMethod(const Selector* m);
  85
  86     bool operator<(const ClassData& r) const {
  87         if (isMetaclass != r.isMetaclass) return isMetaclass;
  88         return strcmp(name, r.name) < 0;
  89     }
  90
  91     struct PlacementAttempt {
  92         int numberOfBitsToSet;
  93         int shift;
  94         int neededBits;
  95
  96         PlacementAttempt(int _numberOfBitsToSet, int _shift, int _neededBits) : numberOfBitsToSet(_numberOfBitsToSet), shift(_shift), neededBits(_neededBits) {
  97
  98         }
  99
 100         std::string description() const;
 101
 102         friend bool operator<(const PlacementAttempt& l, const PlacementAttempt& r)
 103         {
 104             return  std::tie(l.neededBits, l.numberOfBitsToSet, l.shift)
 105             < std::tie(r.neededBits, r.numberOfBitsToSet, r.shift);
 106         }
 107
 108         int mask() const {
 109             return (1 << neededBits) - 1;
 110         }
 111
 112         struct PreviousMethodAddress {
 113             int address;
 114             int fixedBitsMask;
 115         };
 116
 117         struct PreviousState {
 118             int neededBits;
 119             int shift;
 120             int mask;
 121             std::unordered_map<Selector*, PreviousMethodAddress> methods;
 122         };
 123
 124         struct Result {
 125             bool success;
 126             PreviousState previousState;
 127         };
 128     };
 129
 130     // Possibilities we go through in the greedy backtracking algorithm findShiftsAndMask()
 131     // Each class has a set (attempts()) of shift-mask possibilities, ordered, and we go through them
 132     // sequentially.
 133     PlacementAttempt attemptForShift(int shift, int neededBits) const;
 134     std::vector<PlacementAttempt> attempts() const;
 135
 136     int shift;
 137
 138     inline int modulo() const {
 139         return 1 << neededBits;
 140     }
 141
 142     inline int mask() const {
 143         return modulo() - 1;
 144     }
 145
 146     // Attempt to place the class with the shift/mask in the attempt argument.
 147     typename PlacementAttempt::Result applyAttempt(const PlacementAttempt& attempt, std::minstd_rand & randomNumberGenerator);
 148
 149     // Reassign the addresses as they were before we produced resultToBacktrackFrom
 150     void backtrack(typename PlacementAttempt::Result& resultToBacktrackFrom);
 151
 152     // Did we have to grow the size of the hash table to one more bit when attempting to place it?
 153     bool hadToIncreaseSize() const;
 154
 155     // Not const because this stomps over the slots array for checking
 156     bool checkConsistency();
 157
 158     // Size in bytes needed for this hash table in the shared cache.
 159     size_t sizeInSharedCache() const;
 160
 161     // Used to store the location of a flattening root's superclass, so that
 162     // we can compute its final vmAddr once we are in the ObjC optimizer.
 163     struct ClassLocator {
 164         const char *installName;
 165         unsigned segmentIndex;
 166         unsigned segmentOffset;
 167         bool operator==(const ClassLocator & other);
 168     };
 169
 170     std::string_view flatteningRootName;
 171     std::set<std::string_view> flattenedSuperclasses;
 172     std::optional<ClassLocator> flatteningRootSuperclass;
 173
 174     // For debug purposes
 175     bool operator==(const ClassData &other);
 176 };
 177
 178 /// A unique selector. Has a name, a list of classes it's used in, and an address (which is actually an offset from
 179 /// the beginning of the selectors section). Due to how the placement algorithm work, it also has a current
 180 /// partial address and the corresponding bitmask of fixed bits. The algorithm adds bits to the partial address
 181 /// as it makes progress and updates the mask accordingly
 182 class Selector {
 183 public:
 184     // For debug purposes
 185     const char* name;
 186
 187     /// Classes the selector is used in
 188     std::vector<IMPCaches::ClassData*> classes;
 189
 190     /// Which bits of address are already set
 191     int fixedBitsMask;
 192
 193     /// Current 128-byte bucket index for this selector. Only the bits in fixedBitsMask are actually frozen.
 194     int inProgressBucketIndex;
 195
 196     /// Full offset of the selector, including its low 7 bits (so, not the bucket's index ; inProgressBucketIndex (assuming all bits are setr by now) << 7 + some low bits)
 197     int offset; // including low bits
 198
 199     /// Number of bits that you would need to freeze if you were to use this selector with this shift and mask.
 200     int numberOfBitsToSet(int shift, int mask) const {
 201         int fixedBits = (fixedBitsMask >> shift) & mask;
 202         return __builtin_popcount(mask) - __builtin_popcount(fixedBits);
 203     }
 204
 205     int numberOfSetBits() const {
 206         return __builtin_popcount(fixedBitsMask);
 207     }
 208
 209     unsigned int size() const {
 210         return (unsigned int)strlen(name) + 1;
 211     }
 212
 213     // For debug purposes
 214     bool operator==(const Selector &other) const {
 215         return (strcmp(name, other.name) == 0)
 216             && (inProgressBucketIndex == other.inProgressBucketIndex)
 217             && (fixedBitsMask == other.fixedBitsMask);
 218     }
 219
 220     bool operator!=(const Selector &other) const {
 221         return !(*this == other);
 222     }
 223
 224 };
 225
 226 class AddressSpace;
 227 std::ostream& operator<<(std::ostream& o, const AddressSpace& c);
 228
 229 struct Hole {
 230     // [startAddress, endAddress[
 231     int startAddress;
 232     int endAddress;
 233     int size() const {
 234         return endAddress - startAddress;
 235     }
 236
 237     // All our intervals are non-overlapping
 238     bool operator<(const Hole& other) const {
 239         auto a = std::make_tuple(size(), startAddress);
 240         auto b = std::make_tuple(other.size(), other.startAddress);
 241         return a < b;
 242     }
 243 };
 244
 245 /// Represents the holes left by the selector placement algorithm, to be filled later with other selectors we did not target.
 246 class HoleMap {
 247 public:
 248
 249     /// Returns the position at which we should place a string of size `size`.
 250     int addStringOfSize(unsigned size);
 251
 252     /// Total size of all the holes
 253     unsigned long totalHoleSize() const;
 254
 255     // Empty the hole map.
 256     void clear();
 257
 258     HoleMap();
 259
 260 private:
 261     friend class AddressSpace;
 262     friend std::ostream& operator<<  (std::ostream& o, const HoleMap& m);
 263
 264     int endAddress = 0;
 265     std::set<IMPCaches::Hole> holes;
 266 };
 267
 268 // A selector that is known to be at offset 0, to let objc easily compute
 269 // the offset of a selector given the SEL.
 270 constexpr std::string_view magicSelector = "\xf0\x9f\xa4\xaf";
 271
 272 /// This is used to place the selectors in 128-byte buckets.
 273 /// The "indices" below are the indices of the 128-byte bucket. To get an actual selector offset from this,
 274 /// we shift the index to the left by 7 bits, and assign low bits depending on the length of each selector (this happens
 275 /// in @see computeLowBits()).
 276 /// The goal of this class is to validate that selectors can actually be placed in the buckets without overflowing
 277 /// the 128-byte total length limit (based on the length of each individual selector)
 278 class AddressSpace {
 279 public:
 280     int sizeAtIndex(int idx) const;
 281     int sizeAvailableAfterIndex(int idx) const;
 282     bool canPlaceMethodAtIndex(const Selector* method, int idx) const;
 283     void placeMethodAtIndex(Selector* method, int idx);
 284
 285     // If we decided to drop any classes, remove the selectors that were only present in them
 286     void removeUninterestingSelectors();
 287
 288     // Once all selectors are placed in their 128-byte buckets,
 289     // actually assign the low 7 bits for each, and make a map of the
 290     // holes so that we can fill them with other selectors later.
 291     void computeLowBits(HoleMap& selectorsHoleMap) const;
 292
 293     std::string description() const;
 294
 295     static const int maximumIndex = (1 << 17) - 1;
 296     static constexpr int bagSizeShift = 7;
 297
 298     friend std::ostream& operator<<  (std::ostream& o, const AddressSpace& c);
 299 private:
 300     inline int bagSizeAtIndex(int idx) const {
 301         static constexpr int bagSize = 1 << bagSizeShift;
 302         static constexpr int bag0Size = bagSize - (magicSelector.length() + 1);
 303         return idx ? bagSize : bag0Size;
 304     }
 305     bool canPlaceWithoutFillingOverflowCellAtIndex(int idx) const;
 306     std::unordered_map<int, std::vector<Selector*>> methodsByIndex;
 307     std::unordered_map<int, int> sizes;
 308 };
 309
 310 /// Represents a constraint on some of the bits of an address
 311 /// It stores a set of allowed values for a given range of bits (shift and mask)
 312 class Constraint {
 313 public:
 314     int mask;
 315     int shift;
 316     std::unordered_set<int> allowedValues;
 317
 318     Constraint intersecting(const Constraint& other) const;
 319     friend std::ostream& operator << (std::ostream& o, const Constraint& c);
 320
 321     bool operator==(const Constraint& other) const {
 322         return mask == other.mask &&
 323                 shift == other.shift &&
 324                 allowedValues == other.allowedValues;
 325     }
 326
 327     struct Hasher {
 328         size_t operator()(const IMPCaches::Constraint& c) const {
 329             return c.shift << 24 | c.mask << 16 | c.allowedValues.size() << 8 | *c.allowedValues.begin();
 330         }
 331     };
 332 };
 333
 334 /// Merges several Constraints together to generate a simplified constraint equivalent to the original set of constraints
 335 class ConstraintSet {
 336     std::unordered_set<Constraint, Constraint::Hasher> constraints;
 337
 338 public:
 339     std::optional<Constraint> mergedConstraint;
 340
 341     bool add(const Constraint& c);
 342     void clear();
 343 };
 344
 345 class SelectorMap {
 346 public:
 347     using UnderlyingMap = std::map<std::string_view, std::unique_ptr<IMPCaches::Selector>>;
 348     UnderlyingMap map;
 349     SelectorMap();
 350 };
 351
 352 // Implemented in OptimizerObjC
 353 size_t sizeForImpCacheWithCount(int entries);
 354
 355 struct ClassKey {
 356     std::string_view name;
 357     bool metaclass;
 358
 359     size_t hash() const {
 360         std::size_t seed = 0;
 361         seed ^= std::hash<std::string_view>()(name) + 0x9e3779b9 + (seed<<6) + (seed>>2);
 362         seed ^= std::hash<bool>()(metaclass) + 0x9e3779b9 + (seed<<6) + (seed>>2);
 363         return seed;
 364     }
 365
 366     bool operator==(const ClassKey &other) const {
 367         return (name == other.name) && (metaclass == other.metaclass);
 368     }
 369 };
 370
 371 struct ClassKeyHasher {
 372     size_t operator()(const ClassKey& k) const {
 373         return k.hash();
 374     }
 375 };
 376
 377 }
 378
 379
 380 #endif /* IMPCaches_hpp */