【iOS】cache

前言

之前分析類的結構的時候，有遇到一個cache_t，當時說是用來保存方法緩存的結構，這篇文章來從源碼詳細介紹一下cache_t

概覽cache_t

cache_t結構

類在底層的結構如之前所述，存在著cache_t屬性，而cache_t的結構如下：

struct cache_t {
private:// explicit_atomic 顯示原子性，目的是為了能夠 保證 增刪改查時 線程的安全性explicit_atomic<uintptr_t> _bucketsAndMaybeMask; //8union {struct {//一共 8explicit_atomic<mask_t>    _maybeMask; //4
#if __LP64__uint16_t                   _flags;//2
#endifuint16_t                   _occupied;//2};explicit_atomic<preopt_cache_t *> _originalPreoptCache;};#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED//macOS、模擬器 -- 主要是架構區分// _bucketsAndMaybeMask is a buckets_t pointer// _maybeMask is the buckets maskstatic 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_ADDRSstatic 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_CACHESstatic constexpr uintptr_t preoptBucketsMarker = 1ul;static constexpr uintptr_t preoptBucketsMask = bucketsMask & ~preoptBucketsMarker;
#endif
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 //64位真機// _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_CACHESstatic 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 1static 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 0xffffreturn value | ((objc::mask16ShiftBits(cache->mask) - 1) << 60);}
#else// 63..53: hash_mask// 52..48: hash_shift// 47.. 1: buckets ptr//      0: always 1static 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//非64位 真機// _bucketsAndMaybeMask is a buckets_t pointer in the top 28 bits// _maybeMask is unused, the mask length is stored in the low 4 bitsstatic 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.
#endifbool isConstantEmptyCache() const;bool canBeFreed() const;mask_t mask() const;#if CONFIG_USE_PREOPT_CACHESvoid initializeToPreoptCacheInDisguise(const preopt_cache_t *cache);const preopt_cache_t *disguised_preopt_cache() const;
#endifvoid incrementOccupied();void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);void collect_free(bucket_t *oldBuckets, mask_t oldCapacity);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);void bad_cache(id receiver, SEL sel) __attribute__((noreturn, cold));public:// The following four fields are public for objcdt's use only.// objcdt reaches into fields while the process is suspended// hence doesn't care for locks and pesky little details like this// and can safely use these.unsigned capacity() const;struct bucket_t *buckets() const;Class cls() const;#if CONFIG_USE_PREOPT_CACHESconst preopt_cache_t *preopt_cache() const;
#endifmask_t occupied() const;void initializeToEmpty();#if CONFIG_USE_PREOPT_CACHESbool isConstantOptimizedCache(bool strict = false, uintptr_t empty_addr = (uintptr_t)&_objc_empty_cache) const;bool shouldFlush(SEL sel, IMP imp) const;bool isConstantOptimizedCacheWithInlinedSels() const;Class preoptFallbackClass() const;void maybeConvertToPreoptimized();void initializeToEmptyOrPreoptimizedInDisguise();
#elseinline bool isConstantOptimizedCache(bool strict = false, uintptr_t empty_addr = 0) const { return false; }inline bool shouldFlush(SEL sel, IMP imp) const {return cache_getImp(cls(), sel) == imp;}inline bool isConstantOptimizedCacheWithInlinedSels() const { return false; }inline void initializeToEmptyOrPreoptimizedInDisguise() { initializeToEmpty(); }
#endifvoid insert(SEL sel, IMP imp, id receiver);void copyCacheNolock(objc_imp_cache_entry *buffer, int len);void destroy();void eraseNolock(const char *func);static void init();static void collectNolock(bool collectALot);static size_t bytesForCapacity(uint32_t cap);#if __LP64__bool getBit(uint16_t flags) const {return _flags & flags;}void setBit(uint16_t set) {__c11_atomic_fetch_or((_Atomic(uint16_t) *)&_flags, set, __ATOMIC_RELAXED);}void clearBit(uint16_t clear) {__c11_atomic_fetch_and((_Atomic(uint16_t) *)&_flags, ~clear, __ATOMIC_RELAXED);}
#endif#if FAST_CACHE_ALLOC_MASKbool hasFastInstanceSize(size_t extra) const{if (__builtin_constant_p(extra) && extra == 0) {return _flags & FAST_CACHE_ALLOC_MASK16;}return _flags & FAST_CACHE_ALLOC_MASK;}size_t fastInstanceSize(size_t extra) const{ASSERT(hasFastInstanceSize(extra));//Gcc的內建函數 __builtin_constant_p 用于判斷一個值是否為編譯時常數，如果參數EXP 的值是常數，函數返回 1，否則返回 0if (__builtin_constant_p(extra) && extra == 0) {return _flags & FAST_CACHE_ALLOC_MASK16;} else {size_t size = _flags & FAST_CACHE_ALLOC_MASK;// remove the FAST_CACHE_ALLOC_DELTA16 that was added// by setFastInstanceSize//刪除由setFastInstanceSize添加的FAST_CACHE_ALLOC_DELTA16 8個字節return align16(size + extra - FAST_CACHE_ALLOC_DELTA16);}}void setFastInstanceSize(size_t newSize){// Set during realization or construction only. No locking needed.uint16_t newBits = _flags & ~FAST_CACHE_ALLOC_MASK;uint16_t sizeBits;// Adding FAST_CACHE_ALLOC_DELTA16 allows for FAST_CACHE_ALLOC_MASK16// to yield the proper 16byte aligned allocation size with a single masksizeBits = word_align(newSize) + FAST_CACHE_ALLOC_DELTA16;sizeBits &= FAST_CACHE_ALLOC_MASK;if (newSize <= sizeBits) {newBits |= sizeBits;}_flags = newBits;}
#elsebool hasFastInstanceSize(size_t extra) const {return false;}size_t fastInstanceSize(size_t extra) const {abort();}void setFastInstanceSize(size_t extra) {// nothing}
#endif
};

在cache_t的機構當中，有一個極為重要的屬性，就是_bucketsAndMaybeMask，它是一個bucket_t類型的結構體指針。

查看bucket_t的結構可以發現它大致存放了imp，實際上bucket作為一個桶，就是用來存放imp方法實現以及它的key，所以結合以上兩個結構體可知，cache中緩存的正是sel-imp

在cache_t結構體中提供了獲取_buckets屬性的方法buckets()，獲取了_buckets屬性，就可以獲取sel-imp了，這兩個的獲取在bucket_t結構體中也提供了相應的獲取方法sel() 以及imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls)。

在沒有執行方法調用時，cache中沒有緩存，執行了一次方法調用，cache中就有了一個緩存，即調用一次方法就會緩存一次方法

深入cache_t

cache_t中有一個函數叫incrementOccupied()，具體實現為：

全局搜索這個函數，發現它只在cache_t的insert方法有調用

insert方法，顧名思義其實就是往cache中插入sel-imp的方法。全局搜索cache_t::insert方法，發現在寫入之前，還有一步操作就是查找sel-imp，即cache的讀取

分析insert方法

insert方法的源碼如下：

void cache_t::insert(SEL sel, IMP imp, id receiver)
{runtimeLock.assertLocked();// Never cache before +initialize is doneif (slowpath(!cls()->isInitialized())) {return;}if (isConstantOptimizedCache()) {_objc_fatal("cache_t::insert() called with a preoptimized cache for %s",cls()->nameForLogging());}#if DEBUG_TASK_THREADSreturn _collecting_in_critical();
#else
#if CONFIG_USE_CACHE_LOCKmutex_locker_t lock(cacheUpdateLock);
#endifASSERT(sel != 0 && cls()->isInitialized());// Use the cache as-is if until we exceed our expected fill ratio.mask_t newOccupied = occupied() + 1;//沒有屬性賦值的情況下 occupied() = 0, newOccupied = 1unsigned oldCapacity = capacity(), capacity = oldCapacity;if (slowpath(isConstantEmptyCache())) {//小概率發生的,即當 occupied() = 0時,即創建緩存,創建屬于小概率事件// Cache is read-only. Replace it.if (!capacity) capacity = INIT_CACHE_SIZE;//初始化時,capacity = 4 (1<<2)reallocate(oldCapacity, capacity, /* freeOld */false);//開辟空間//到目前為止,if的流程的操作都是初始化創建}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.//如果小于等于占用內存的3/4,什么都不用做/*第一次時,申請開辟的內存是4個,如果此時已經有3個從bucket插入到cache里面,再插入一個,就是4個.當大于4即當前下標是4,就數組越界了,這是肯定不行的,所以需要在原理的容量上進行兩倍擴容*/}
#if CACHE_ALLOW_FULL_UTILIZATIONelse if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) {// Allow 100% cache utilization for small buckets. Use it as-is.}
#endifelse {//如果超出了3/4,則需要擴容(兩倍擴容) -- 即 occupied 為2時,就沒有進去了//擴容算法: 有capacity時,擴容兩倍,沒有capacity就初始化為4capacity = 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 = capacity - 1mask_t begin = cache_hash(sel, m);//求cache哈希,即哈希下標---通過哈希算法函數計算 sel存儲的下標mask_t i = begin;// Scan for the first unused slot and insert there.// There is guaranteed to be an empty slot.//如果存在了哈希沖突,則從沖突的下標開始遍歷 即進行do-while循環do {//如果當前遍歷的下標拿不到sel,即表示當前下標沒有存儲selif (fastpath(b[i].sel() == 0)) {//則將sel存儲進去,并將對應的 occupied標記++,即從0變為1incrementOccupied();b[i].set<Atomic, Encoded>(b, sel, imp, cls());return;}//如果當前哈希下標的sel等于準備插入的sel,則直接返回if (b[i].sel() == sel) {// The entry was added to the cache by some other thread// before we grabbed the cacheUpdateLock.return;}//如果當前計算的哈希下標已經存儲了sel,且兩個sel不相等,需要重新進行哈希計算 得到新的下標} while (fastpath((i = cache_next(i, m)) != begin));bad_cache(receiver, (SEL)sel);
#endif // !DEBUG_TASK_THREADS
}

insert的代碼很長，但是其實主要可以分為三個部分：

第一步，計算當前緩存占用量
第二部，根據緩存占用量判斷執行的操作
針對需要存儲的bucket進行內部的sel-imp賦值

下面我們來詳細解釋每個部分各自是如何實現的

計算當前緩存占用量

剛剛incrementOccupied的實現里有一步occupied的自增操作，這個occupied其實就代表著當前緩存中保存的sel-imp對的數量。

insert方法就是根據occupied的值計算出當前的緩存占用量，當屬性未賦值及無方法調用時，此時的occupied()為0，而newOccupied為1

這里有幾個需要注意的點：

alloc申請空間時，此時的對象已經創建，如果再調用init方法，occupied也會+1
當有屬性賦值時，會隱式調用set方法，occupied也會增加，即有幾個屬性賦值，occupied就會在原有的基礎上加幾個
當有方法調用時，occupied也會增加，即有幾次調用，occupied就會在原有的基礎上加幾個

根據緩存占用量判斷執行的操作

如果是第一次創建，那么磨人開辟四個sel-imp的空間

如果緩存占用量小于等于3/4，就不做任何處理

而如果緩存占用量超過了3/4，需要進行兩倍擴容以及重新開辟空間

reallocate方法

在判斷完操作之后，如果是第一次創建或者兩倍擴容，會用到一個方法來開辟空間，這個方法就是reallocate。

這個方法主要有以下幾步：

allocateBuckets方法：向系統申請開辟內存，即開辟bucket，此時的bucket只是一個臨時變量。 setBucketsAndMask方法：將臨時的bucket存入緩存中，此時的存儲分為兩種情況：

1.如果是真機，根據bucket和mask的位置存儲，并將occupied占用設置為0

2.如果不是真機，正常存儲bucket和mask，并將occupied占用設置為0

如果有舊的buckets，需要清理之前的緩存，即調用collect_free方法

可以看到collect_free方法就是創建垃圾回收的空間，然后把需要回收的sel-imp放進去，最后進行回收。

其中_garbage_make_room方法創建垃圾回收空間的邏輯如下圖：

如果是第一次，需要分配回收空間如果不是第一次，則將內存段加大，即原有內存*2

針對需要存儲的bucket進行內部imp和sel賦值

這個部分就是通過哈希算法來計算sel-imp的哈希下標：

如果哈希下標的位置未存儲sel，即該下標位置獲取sel等于0，此時將sel-imp存儲進去，并將occupied占用大小加1
如果當前哈希下標存儲的sel 等于 即將插入的sel，則直接返回
如果當前哈希下標存儲的sel 不等于 即將插入的sel，則重新經過cache_next方法即哈希沖突算法，重新進行哈希計算，得到新的下標，再去對比進行存儲