【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方法即哈希冲突算法，重新进行哈希计算，得到新的下标，再去对比进行存储