Cache_t, as its name implies, is used to cache some data. In the underlying structure of Class, there is a cache_t cache, which serves primarily as a cache for calling methods. Convenient next call is directly from the cache to obtain THE IMP address, speed up the execution efficiency.
Analyze the underlying structure of Cache_T
struct cache_t {
private:
explicit_atomic<uintptr_t> _bucketsAndMaybeMask;
union {
struct {
explicit_atomic<mask_t> _maybeMask;
#if __LP64__
uint16_t _flags;
#endif
uint16_t _occupied;
};
explicit_atomic<preopt_cache_t *> _originalPreoptCache;
};
}
Copy the codeUnderlying cache_t is a structure containing a uintptr_t _bucketsAndMaybeMask, followed by a shared structure with a pointer to preopT_cache_t. Now that you’ve looked briefly at the underlying structure of Cache_t, let’s take a look at what else there is.
#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; 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 buckets_t pointer in the low 48 bits // _maybeMask is unused, the mask is stored in the top 16 bits. // How much the mask is shifted by. 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"); #else #error Unknown cache mask storage type. #endifCopy the codeThese are static variables where you see a lot of left shift and the comments at the end explain what the bits stand for, similar to ISA. Then there are some member functions (cache operations, like database operations, CURD, so pick the right ones).
void insert(SEL sel, IMP imp, id receiver); Insert (sel, IMP) into cache
void cache_t::insert(SEL sel, IMP imp, id receiver) { runtimeLock.assertLocked(); // Never cache before +initialize is done if (slowpath(! cls()->isInitialized())) { return; } if (isConstantOptimizedCache()) { _objc_fatal("cache_t::insert() called with a preoptimized cache for %s", cls()->nameForLogging()); } #if DEBUG_TASK_THREADS return _collecting_in_critical(); #else #if CONFIG_USE_CACHE_LOCK mutex_locker_t lock(cacheUpdateLock); #endif ASSERT(sel ! = 0 && cls()->isInitialized()); // Use the cache as-is if until we exceed our expected fill ratio. mask_t newOccupied = occupied() + 1; unsigned oldCapacity = capacity(), capacity = oldCapacity; if (slowpath(isConstantEmptyCache())) { // Cache is read-only. Replace it. if (! capacity) capacity = INIT_CACHE_SIZE; reallocate(oldCapacity, capacity, /* freeOld */false); } else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) { // Cache is less than 3/4 or 7/8 full. Use it as-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 { capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; if (capacity > MAX_CACHE_SIZE) { capacity = MAX_CACHE_SIZE; } reallocate(oldCapacity, capacity, true); } bucket_t *b = buckets(); mask_t m = capacity - 1; mask_t begin = cache_hash(sel, m); mask_t i = begin; // Scan for the first unused slot and insert there. // There is guaranteed to be an empty slot. do { if (fastpath(b[i].sel() == 0)) { incrementOccupied(); b[i].set<Atomic, Encoded>(b, sel, imp, cls()); return; } if (b[i].sel() == sel) { // The entry was added to the cache by some other thread // before we grabbed the cacheUpdateLock. return; } } while (fastpath((i = cache_next(i, m)) ! = begin)); bad_cache(receiver, (SEL)sel); #endif // ! DEBUG_TASK_THREADS }Copy the codeInsert specific logic:
It’s occupied with preparing for final exams; it’s occupied with preparing for final exams; it’s occupied with preparing for final exams; Check whether the current cache is empty and create a cache if it is. If the current cache is not empty and is larger than 3/4 of the capacity, double the capacity. Then hash sel and capacity to get an index, and cache the corresponding SEL, IMP, and class. If the current exists, no operation is performed.
Concrete function analysis
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 codeGet the old oldBuckets, create a newBuckets of size newCapacity, and setBucketsAndMask(newBuckets, newcapacity-1); And release the oldBuckets
The bucket structure is also a structure, which caches SEL and IMP
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; #endifCopy the codevoid cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask) { // objc_msgSend uses mask and buckets with no locks. // It is safe for objc_msgSend to see new buckets but old mask. // (It will get a cache miss but not overrun the buckets' bounds). // It is unsafe for objc_msgSend to see old buckets and new mask. // Therefore we write new buckets, wait a lot, then write new mask. // objc_msgSend reads mask first, then buckets. #ifdef __arm__ // ensure other threads see buckets contents before buckets pointer mega_barrier(); _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_relaxed); // ensure other threads see new buckets before new mask mega_barrier(); _maybeMask.store(newMask, memory_order_relaxed); _occupied = 0; #elif __x86_64__ || i386 // ensure other threads see buckets contents before buckets pointer _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_release); // ensure other threads see new buckets before new mask _maybeMask.store(newMask, memory_order_release); _occupied = 0; #else #error Don't know how to do setBucketsAndMask on this architecture. #endif }Copy the codesetBucketsAndMask(newBuckets, newCapacity – 1); NewMask (newCapacity-1) **; _occupied = 0; Learn from this the first member variable in the cache_T structure, _bucketsAndMaybeMask, and the meaning of _occupied.
The hash function
static inline mask_t cache_hash(SEL sel, mask_t mask)
{
uintptr_t value = (uintptr_t)sel;
#if CONFIG_USE_PREOPT_CACHES
value ^= value >> 7;
#endif
return (mask_t)(value & mask);
}
Copy the codeMove SEL and SEL to the right by 7 bits, and then operate with mask.
