preface
From the previous article, we can see that the structure of a class is as follows:
// Class ISA;
Class superclass;
cache_t cache; // formerly cache pointer and vtable
class_data_bits_t bits; // class_rw_t * plus custom rr/alloc flags
.....
}
Copy the codeAnd since we explored the bits data structure of a class in a previous article, today we’ll take a look at the cache_t structure of a class
Begin to explore
1. Cache_t data structures
The structure of the output cache_t via LLDB looks like this:
bucket_tData manipulation
struct cache_t {
static bucket_t *emptyBuckets();
static bucket_t *allocateBuckets(mask_t newCapacity);
static bucket_t *emptyBucketsForCapacity(mask_t capacity, bool allocate = true);
static struct bucket_t * endMarker(struct bucket_t *b, uint32_t cap);
struct bucket_t *buckets() const;
}
Copy the codeSo what is the bucket_t structure?
struct bucket_t { private: // IMP-first is better for arm64e ptrauth and no worse for arm64. // SEL-first is better for armv7* and i386 and x86_64. #if __arm64__ explicit_atomic<uintptr_t> _imp; explicit_atomic<SEL> _sel; #else explicit_atomic<SEL> _sel; explicit_atomic<uintptr_t> _imp; #endif }Copy the codeBucket_t *buckets() const; bucket_t *buckets() const; bucket_t *buckets(); The BUCKET () function is used to retrieve the bucket_t data from the LLDB.
struct cache_t { private: explicit_atomic<uintptr_t> _bucketsAndMaybeMask; Union {struct {explicit_atomic<mask_t> _maybeMask; // maybeMask is open size -1 #if __LP64__ uint16_t _flags; #endif uint16_t _occupied; // The number of cached methods}; explicit_atomic<preopt_cache_t *> _originalPreoptCache; };Copy the code2. Insert and read sel and IMP cache
There is an INSERT method in the cache_t structure. Let’s take a look at the insert method.
void cache_t::insert(SEL sel, IMP imp, Id receiver) {// Use the cache as-is if until we exceed our expected fill ratio. // Use the cache as is if until we exceed our expected fill ratio. mask_t newOccupied = occupied() + 1; // 1+1 unsigned oldCapacity = capacity(), capacity = oldCapacity; if (slowpath(isConstantEmptyCache())) { // Cache is read-only. Replace it. if (! capacity) capacity = INIT_CACHE_SIZE; //4, open size reallocate(oldCapacity, capacity, /* freeOld */false); //4, open size reallocate(oldCapacity, capacity, /* freeOld */false); } else if (fastpath(newpath + CACHE_END_MARKER <= cache_fill_ratio(capacity))) {// Cache is less than 3/4 or 7/8. Use it as it is. } #if CACHE_ALLOW_FULL_UTILIZATION else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) { // Allow 100% cache utilization for small buckets. Use it as-is. } #endif else {// 4*2 = 8 capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; // Double the capacity when the cache usage exceeds 3/4. if (capacity > MAX_CACHE_SIZE) { capacity = MAX_CACHE_SIZE; } reallocate(oldCapacity, capacity, true); } bucket_t *b = buckets(); Mask_t m = capacity - 1; // 4-1=3 mask_t begin = cache_hash(sel, m); // The class points to the cache. SEL is key. Buckets cache SEL+IMP. The cache is never built on dyld shared cache. mask_t i = begin; Scan for the first unused slot and insert there. // There is guaranteed to be an empty slot. // Scan the first unused slot and insert there. // Make sure there is an empty slot. Do {if (fastpath(b[I].sel() == 0)) {// Insert incrementOccupied(); //occupied = occupied + 1 b[i].set<Atomic, Encoded>(b, sel, imp, cls()); return; } if (b[I].sel() == sel) {// Cache has been inserted, Upon getting back on terms // The entry was added to The cache by some other thread // before we rattled The cacheUpdateLock. Return; } } while (fastpath((i = cache_next(i, m)) ! = begin)); //cache_next(I, m) Avoid hash conflicts bad_cache(receiver, (SEL) SEL); } #if CACHE_END_MARKER static inline mask_t cache_next(mask_t i, mask_t mask) { return (i+1) & mask; } #elif __arm64__ static inline mask_t cache_next(mask_t i, mask_t mask) { return i ? i-1 : mask; } #elseCopy the codeTo sum it up:
Buckets and _maybeMask are stored in the _bucketsAndMaybeMask variable in the cache_T structure. _maybeMask = capacity -1, capacity is the size of the space to be created.
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
bucket_t *oldBuckets = buckets();
bucket_t *newBuckets = allocateBuckets(newCapacity);
// Cache's old contents are not propagated.
// This is thought to save cache memory at the cost of extra cache fills.
// fixme re-measure this
ASSERT(newCapacity > 0);
ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
setBucketsAndMask(newBuckets, newCapacity - 1);
if (freeOld) {
collect_free(oldBuckets, oldCapacity);
}
}
Copy the code2. Check whether the usage of buckets is less than 3/4. If the usage is greater than 3/4, double the capacity
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; // Capacity Specifies the size of the openingCopy the code3. Find the empty position and insert SEL + IMP
if (fastpath(b[i].sel() == 0)) {
incrementOccupied();
b[i].set<Atomic, Encoded>(b, sel, imp, cls());
return;
}
Copy the codeThe next step is to look at imp and SEL reading, which is to look at the implementation of buckets() and then at the methods provided in the bucket_t structure.
struct bucket_t *cache_t::buckets() const
{
uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
return (bucket_t *)(addr & bucketsMask);
}
struct bucket_t {
inline SEL sel() const { return _sel.load(memory_order_relaxed); }
inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls) const
}
Copy the codeWhat is a bucketsMask?
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED // _bucketsAndMaybeMask is a buckets_t pointer // _maybeMask is the buckets mask static constexpr uintptr_t bucketsMask = ~0ul; //18446744073709551615 static_assert(! CONFIG_USE_PREOPT_CACHES, "preoptimized caches not supported"); #elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS static constexpr uintptr_t maskShift = 48; static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1; static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << maskShift) - 1; static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers."); #if CONFIG_USE_PREOPT_CACHES static constexpr uintptr_t preoptBucketsMarker = 1ul; static constexpr uintptr_t preoptBucketsMask = bucketsMask & ~preoptBucketsMarker; #endif #elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 // _bucketsAndMaybeMask is a low 48-bit pointer to buckets_t // _maybeMask If not used, the mask is stored in the first 16 bits. static constexpr uintptr_t maskShift = 48; // Additional bits after the mask which must be zero. msgSend // takes advantage of these additional bits to construct the value // `mask << 4` from `_maskAndBuckets` in a single instruction. static constexpr uintptr_t maskZeroBits = 4; // The largest mask value we can store. static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1; // The mask applied to `_maskAndBuckets` to retrieve the buckets pointer. static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1; // Ensure we have enough bits for the buckets pointer. static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers."); #if CONFIG_USE_PREOPT_CACHES static constexpr uintptr_t preoptBucketsMarker = 1ul; #if __has_feature(ptrauth_calls) // 63.. 60: hash_mask_shift // 59.. 55: hash_shift // 54.. 1: buckets ptr + auth // 0: always 1 static constexpr uintptr_t preoptBucketsMask = 0x007ffffffffffffe; static inline uintptr_t preoptBucketsHashParams(const preopt_cache_t *cache) { uintptr_t value = (uintptr_t)cache->shift < < 55; // masks have 11 bits but can be 0, so we compute // the right shift for 0x7fff rather than 0xffff return value | ((objc::mask16ShiftBits(cache->mask) - 1) < < 60); } #else // 63.. 53: hash_mask // 52.. 48: hash_shift // 47.. 1: buckets ptr // 0: always 1 static constexpr uintptr_t preoptBucketsMask = 0x0000fffffffffffe; static inline uintptr_t preoptBucketsHashParams(const preopt_cache_t *cache) { return (uintptr_t)cache->hash_params << 48. } #endif #endif // CONFIG_USE_PREOPT_CACHES #elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4 // _bucketsAndMaybeMask is a buckets_t pointer in the top 28 bits // _maybeMask is unused, the mask length is stored in the low 4 bits static constexpr uintptr_t maskBits = 4; static constexpr uintptr_t maskMask = (1 << maskBits) - 1; static constexpr uintptr_t bucketsMask = ~maskMask; static_assert(! CONFIG_USE_PREOPT_CACHES, "preoptimized caches not supported"); #elseCopy the codeI run on x86_64, bucketsMask = ~0ul, _bucketsAndMaybeMask is a pointer to buckets_t, and verify as follows:
conclusion
Two diagrams summarize the process of the cache_T structure and method caching
