前言

我们在iOS底层原理–isa&类结构探究这篇文章里已经分析过isa & bits了，那么类里面就还剩下一个☝️重要的组成部分cache，也就是本篇我们需要研究的内容。话不多说，直接开撸。

源码分析cache

探究cache底层，肯定离不开源码。我们先看下源码，大致就能了解cache的数据结构，大概知道里面大概会存储哪些内容。

通过源码我们可以看到cache的数据结构如下?：

• bucketsAndMaybeMask
• 联合体（_maybeMask _flags _occupied _originalPreoptCache）

同时我们发现源码里有一个词高频出现bucket，我们看下bucket里面又是些什么？

• 真机架构下：imp&sel
• 非真机架构下：sel&imp

我们可以看出不论真机还是模拟器bucket里都是imp和sel，只是顺序不同。

在cache中找sel & imp

我们使用两种不同的方式查询存储在cache中的sel & imp：

1. 之前我们用过的方式：通过源码进行lldb调试分析。
2. 脱离源码直接通过代码分析。

lldb分析cache

准备工作

• 老规矩定义一个YSHPerson，如下图：

• 在main.m里依次调用实例方法，并打上一个小小的断点，方便我们调试

• 运行项目，进入断点后，开始进行lldb调试

总结

• 通过类的首地址偏移16字节，我们就能拿到cache的地址，这里类似前面去获取bits地址。
• 上面?我们已经知道了sel & imp存储在cache_t的_buckets中，在cache_t源码中我们也找到了一个获取_buckets属性的方法buckets()。
• 而在buckets源码中，我们也找到了相应获取sel & imp的方法sel()和imp(nil,class)

脱离源码分析

准备工作

我们将源码拷贝至我们的项目，按照源码的数据结构，修改成我们自定义的。如下图：（注意：objc_class里面切勿忘记添加isa，否则获取内存地址会获取错误）

?我们来看下打印结果：

其实从打印结果来看，我们是懵✏️的。

1. _occupied是什么？为什么是从3开始的？
2. _maybeMask是什么？为什么是7？
3. 为什么打印出来的方法不全，最开始调用的walk/run方法没有打印出来，并且打印的顺序并不是我们调用的顺序？

接下来，就让我们带着上面的问题，进行cache底层原理探索。

cache_t底层原理

我们还是结合源码进行分析，一般都会无从下手，我们可以这么想，cache是英文意思是缓存，既然是缓存，就肯定会有数据变化。那我们就从能引起数据变化的方法打开缺口，尝试一下，看下到底能不能分析。

• void incrementOccupied();

我们从cache_t源码里找，发现里这个函数，从字面意思来看，是说occupied自增，引起了occupied的变化，那我们看下这个函数的具体实现。

• 我们在源码全局搜索incrementOccupied函数，看看都在什么地方调用了，发现只在objc_cache.mm文件中的insert(SEL sel, IMP imp, id receiver)函数中调用了。

• insert顾名思义就是插入的意思，插入的是什么呢？我看到该函数有3个参数：sel、imp、receiver，我们上面分析的cache里缓存的就是sel和imp，说明insert是我们分析cache_t的☝️非常非常重要的方法。

通过源码，我们可以分析出来，insert方法主要分为以下几步：

1. 计算当前缓存占用量
2. 通过判断缓存占用量是否超过总空间的3/4，是否需要开辟内存空间
3. 针对需要存储的bucket进行sel和imp赋值。

下面?我们详细分析下insert方法每一步，都具体做了哪些操作。

• 根据occupied()计算出当前的缓存占用量，然后+1，得到newOccupied

 mask_t newOccupied = occupied() + 1;   //occupied初始值为0，此处为0+1 
复制代码

• 判断isConstantEmptyCache()是否是第一次缓存方法?
• • 如果是第一次缓存方法，caapcity也为0，也就是说默认第一次开辟4个bucket空间( capacity = INIT_CACHE_SIZE = (1 << 2),1左移两位就是4 (0100))，调用reallocate方法开辟空间。

//当occupied为0时，可以理解为第一次缓存方法时，所以为小概率事件，此处用slowpath
if (slowpath(isConstantEmptyCache())) {
        // INIT_CACHE_SIZE = (1 << 2),1左移两位就是4 (0100)
        if (!capacity) capacity = INIT_CACHE_SIZE;
        //释放旧缓存空间，开辟新缓存空间
        reallocate(oldCapacity, capacity, /* freeOld */false); 
    }
复制代码

reallocate方法中会调用setBucketsAndMask方法。
并且当不是第一次开辟空间是，会调用collect_free释放旧的空间，也就是说为什么我们刚才打印的方法会丢失，二倍扩容后，之前的内存空间就会被释放。

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    bucket_t *oldBuckets = buckets();
    bucket_t *newBuckets = allocateBuckets(newCapacity);

    ASSERT(newCapacity > 0);
    ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
    //此处maybeMask值为newcapacity-1
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
        collect_free(oldBuckets, oldCapacity);
    }
}
复制代码

我们接着看下setBucketsAndMask，在该方法中我们发现，maybeMask的值其实就是capacity-1，即第一次开辟4个空间，则maybeMask为3=4-1。并且为什么cache_t结构体的_bucketsAndMaybeMask里面有bucekts，也是在这里存储的。

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
#ifdef __arm__
    mega_barrier();
    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_relaxed);
    mega_barrier();
    _maybeMask.store(newMask, memory_order_relaxed);
    _occupied = 0;
#elif __x86_64__ || i386
 pointer
    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_release);
    _maybeMask.store(newMask, memory_order_release);
    _occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}
复制代码

• • 如果不是第一次缓存方法，则需要判断当前occupied(newOccupied)是否超过了已开辟的bucket个数的3/4，未超过3/4则什么也不用做，继续往下执行即可。

if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) {
        //CACHE_END_MARKER=1;
        //1+1<=capacity * 3 / 4;
        //如果<=占用空间的3/4那么什么都不用做，证明内存空间够用。
        //为什么是3/4，应该是哈希算法中解决哈希冲突，3/4类似于一个临界点，会大大降低冲突的概率。
    }
static inline mask_t cache_fill_ratio(mask_t capacity) {
        return capacity * 3 / 4;
    }
复制代码

• • 如果超过了3/4，则需要将现有空间*2，也就是说2倍扩容。

//缓存空间不足时，开辟空间*2
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
if (capacity > MAX_CACHE_SIZE) {
    capacity = MAX_CACHE_SIZE;
    }
reallocate(oldCapacity, capacity, true);//释放旧缓存空间，开辟新缓存空间
复制代码

• 需要的空间都开辟后，就需要开始存储sel和imp了。通过cache_hash计算出哈希下标，然后做一个循环，直到命中可以存储的下标，然后将occupied自增+1。

    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    mask_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 {
        if (fastpath(b[i].sel() == 0)) {//如果此处bucket中下标为i的sel为空，则可以在此处存储。
            incrementOccupied();
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());
            return;
        }
        if (b[i].sel() == sel) { //如果找到此处的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));//如果i不等于开始的begin,则一直循环
复制代码

方法补充

• cache_hash哈希算法

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; // value右移7位，然后按位异或
#endif
    return (mask_t)(value & mask);//sel与上mask
}

复制代码

• cache_next哈希冲突算法

#if CACHE_END_MARKER //非真机环境
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;//（将当前的哈希下标 +1） & mask，重新进行哈希计算，得到一个新的下标
}
#elif __arm64__
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;//真机环境下，是向前存储。如果i是空，则为mask，mask = cap -1，如果不为空，则 i-1，向前插入sel-imp
}
#else
#error unexpected configuration
#endif
复制代码

扩展（疑问解答）

• _occupied是什么？为什么是从3开始的？

_occupied是已经分配的内存中已经缓存了的方法个数也就是说存储的sel-imp的个数)。当第三个方法进来的时候，就需要重新开辟空间，occupied重置为0，存储时occupied变为1，当调用完之后，occupied已经自增到3。

• _maybeMask是什么？为什么是7？

_maybeMask可以理解成掩码数据，主要是用于在哈希算法或者哈希冲突算法中计算哈希下标，其中_maybeMask等于capacity – 1，因为进行了二次扩容，4*2=8，_maybeMask=8-1=7。

• 为什么打印出来的方法不全，最开始调用的walk/run方法没有打印出来，并且打印的顺序并不是我们调用的顺序？

在扩容时，重新申请了新的内存空间，并且会释放掉之前的内存空间。而sel和imp存储时并不是连续存储的，而是随机的计算出某个下标。

• 为什么要释放掉oldBuckets，而不是在原空间扩容后，继续在后面存储？

1. 已经申请好的内存空间，是无法再次修改的。这里的二倍扩容，其实是申请了一块新的内存空间。
2. 如果将oldBuckets的缓存都拿出来，迁移到新申请的buckets内存空间上。这种操作是非常消耗性能的。其次苹果的缓存策略是越新越好，每一次扩容清掉oldBuckets。也就是说，假设A方法被调用了一次，没有二次调用了，如果扩容后，依然将A方法缓存进来，后续可能不会再次调用，那么A方法就纯属占着坑位，没有任何意义。

insert流程图

cache_t缓存流程图