我们这节课探索cache_t,首先我们提出问题，带着问题去找答案。

1.cache_t是什么?

struct cache_t {
    struct bucket_t *_buckets; // 8
    mask_t _mask;  // 4
    mask_t _occupied; // 4
   // 下面都是函数方法
};

从源码上可以看出cache_t是结构体，里面包含了另一个结构体struct bucket_t *_buckets;和两个mask_t，那我们再看结构体bucket_t里面有什么吧,点击进入：

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__
    MethodCacheIMP _imp;
    cache_key_t _key;
#else
    cache_key_t _key;
    MethodCacheIMP _imp;
#endif

public:
    inline cache_key_t key() const { return _key; }
    inline IMP imp() const { return (IMP)_imp; }
    inline void setKey(cache_key_t newKey) { _key = newKey; }
    inline void setImp(IMP newImp) { _imp = newImp; }

    void set(cache_key_t newKey, IMP newImp);
};

从源码可以可看出bucket_t里面包含了2个参数_imp和_key.
我们可以得出cache_t结构体里面有三个元素：

• _buckets散列表,是一个数组,数组里面的每一个元素就是一个bucket_t,bucket_t里面存放两个
  • _key SEL作为key
  • _imp 函数的内存地址
• _mask 散列表的长度
• _occupied 已缓存方法数量

caceh_t是什么我们已经得到的验证，那我们继续验证cache_t是干什么的？

2.cache_t是干什么的？

根据字面意思，我们都知道cache是缓存，那么cache_t又是缓存什么的呢？这又回到了我们类的本质探索方法了，我们新建一个类，里面加添加成员变量hobby和属性nickName.添加示例方法和类方法，用LLDB指令探索一下：

(lldb) x/4gx yx.class
0x100002560: 0x001d800100002539 0x0000000100aff140
0x100002570: 0x0000000101088940 0x0000000300000003
(lldb) p (cache_t *)0x100002570
(cache_t *) $1 = 0x0000000100002570
(lldb) p *$1
(cache_t) $2 = {
  _buckets = 0x0000000101088940
  _mask = 3
  _occupied = 3
}
(lldb) p $2._buckets[0]
(bucket_t) $3 = {
  _key = 4294975016
  _imp = 0x0000000100001a40 (LGTest`-[YXPerson sayCode] at YXPerson.m:11)
}
(lldb) p $2._buckets[1]
(bucket_t) $4 = {
  _key = 4309129704
  _imp = 0x00000001003930d0 (libobjc.A.dylib`::-[NSObject class]() at NSObject.mm:1988)
}
(lldb) p $2._buckets[2]
(bucket_t) $5 = {
  _key = 140734468495962
  _imp = 0x0000000100393440 (libobjc.A.dylib`::-[NSObject respondsToSelector:](SEL) at NSObject.mm:2046)
}
(lldb) p $2._buckets
(bucket_t *) $6 = 0x0000000101088940
(lldb) p *$6
(bucket_t) $7 = {
  _key = 4294975016
  _imp = 0x0000000100001a40 (LGTest`-[YXPerson sayCode] at YXPerson.m:11)
}

由上面打印可以看出，cache_t里面缓存的是方法。现在我们通过lldb打印知道了chche_t是缓存方法的，但是具体代码是怎么走的，我们还不清楚，因为根据lldb我们只能看到结果，那么我们去源码中走一遭。

3.cache_t在源码中的流程

我们打开源码，其中在objc_chche.mm这个文件的最上面有一段注释

* Cache readers (PC-checked by collecting_in_critical())
 * objc_msgSend*
 * cache_getImp
 *
 * Cache writers (hold cacheUpdateLock while reading or writing; not PC-checked)
 * cache_fill         (acquires lock)
 * cache_expand       (only called from cache_fill)
 * cache_create       (only called from cache_expand)
 * bcopy               (only called from instrumented cache_expand)
 * flush_caches        (acquires lock)
 * cache_flush        (only called from cache_fill and flush_caches)
 * cache_collect_free (only called from cache_expand and cache_flush)

从上面我们可以看出 cache的整个流程是从cache_fill开始，全局搜索cache_fill:

void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
#if !DEBUG_TASK_THREADS
    mutex_locker_t lock(cacheUpdateLock);
    cache_fill_nolock(cls, sel, imp, receiver);
#else
    _collecting_in_critical();
    return;
#endif
}

从中cache_fill函数中又调用了cache_fill_nolock函数，那我们继续往下看：

static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
    cacheUpdateLock.assertLocked();

    // Never cache before +initialize is done
    if (!cls->isInitialized()) return;

    // Make sure the entry wasn't added to the cache by some other thread 
    // before we grabbed the cacheUpdateLock.
    if (cache_getImp(cls, sel)) return;

    cache_t *cache = getCache(cls);
    cache_key_t key = getKey(sel);

    // Use the cache as-is if it is less than 3/4 full
    mask_t newOccupied = cache->occupied() + 1;
    mask_t capacity = cache->capacity();
    if (cache->isConstantEmptyCache()) {
        // Cache is read-only. Replace it.
        cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
    }
    else if (newOccupied <= capacity / 4 * 3) {
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        // Cache is too full. Expand it.
        cache->expand();
    }

    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot because the 
    // minimum size is 4 and we resized at 3/4 full.
    bucket_t *bucket = cache->find(key, receiver);
    if (bucket->key() == 0) cache->incrementOccupied();
    bucket->set(key, imp);
}

首先进行初始化判断，判断从缓存中能不能拿到方法的imp，拿到直接return，拿不到继续往下走：

// Never cache before +initialize is done
    if (!cls->isInitialized()) return;

    // Make sure the entry wasn't added to the cache by some other thread 
    // before we grabbed the cacheUpdateLock.
    if (cache_getImp(cls, sel)) return;

在拿到类中的cache_t这个结构体，并且通过sel得到散列表中的key：

  cache_t *cache = getCache(cls);
  cache_key_t key = getKey(sel);

然后创建一个新的newOccupied，告诉缓存下面要缓存一个方法，然后再读取现在缓存中的容量capacity：

 mask_t newOccupied = cache->occupied() + 1;
 mask_t capacity = cache->capacity();

然后把占位的容量和当前缓存中的容量做对比：

 if (cache->isConstantEmptyCache()) {
     // Cache is read-only. Replace it.
     cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
 }
 else if (newOccupied <= capacity / 4 * 3) {
     // Cache is less than 3/4 full. Use it as-is.
 }
 else {
     // Cache is too full. Expand it.
     cache->expand();
 }

• if (cache->isConstantEmptyCache())是空的，则进行cache->reallocate()。
• if (newOccupied <= capacity / 4 * 3) 如果新的占位容量小于等于当前容量的3/4，则不作处理
• 然后如果新的占位容量大于当前容量的3/4，则进行扩容处理cache->expand()
  我们再来看一下，如果cache是空的，进行reallocate是怎么是实现的？扩容cache->expand()又是怎么实现的？我们先点击进去reallocate()函数看看其干了什么：

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    bool freeOld = canBeFreed();

    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);
    
// 下面这个就是把旧的bucket_t给抹掉，释放内存
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false);
    }
}

我们看到reallocate里面首先拿到以前的bucket_t结构体，然后根据新的占位容量newCapacity创建一个新的bucket_t *newBuckets结构体，然后往下走进入setBucketsAndMask，我们看看这个东西做了什么事:

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    _buckets = newBuckets;//属性buckets赋值 
    _mask = newMask;// mask赋值 4-1=3
    _occupied = 0;// occupied设置为0（这个地方为0是因为我们还没进行缓存，所以标记为0）
}

以上我们可以总结出cache如果是空的，进行属性buckets赋值 ，mask赋值，occupied设置为0。我们在看看扩容是怎么实现的，上源码：

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    
    uint32_t oldCapacity = capacity();
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;
  *
  能进入到扩容的这里面 _mask 是有值的，并且是并且我们知道得到的oldCapacity是_maks + 1，
  申请的一份新的容量是 oldCapacity * 2，我们可以验证一下开辟两倍的空间是最划算的。
  *

    if ((uint32_t)(mask_t)newCapacity != newCapacity) {
        // mask overflow - can't grow further
        // fixme this wastes one bit of mask
        newCapacity = oldCapacity;
    }

    //这里如同刚开始没有缓存的时候，重新让系统来开辟
    reallocate(oldCapacity, newCapacity);

以上我们可总结出cache扩容，就是重新申请一个容量是原来2倍的新容量。
cache是空的和扩容cache->expand()的时候我们知道是怎么回事了，那么我们回到主线来继续走进入到bucket_t *bucket = cache->find(key, receiver);也就是根据key和receiver在缓存中查找bucket_t：

bucket_t * cache_t::find(cache_key_t k, id receiver)
{
    assert(k != 0);

    bucket_t *b = buckets();
    mask_t m = mask();
// 通过cache_hash函数 [begin = k & m]计算出key的值 k 对应的index的值 begin，用来记录查询起始索引
    mask_t begin = cache_hash(k, m);
    
    // begin赋值给i，用于切换索引
    mask_t i = begin;
    do {
        if (b[i].key() == 0  ||  b[i].key() == k) {
            // 用这个i从散列表取值，如果取出来的bucket_t 的 key = k，则查询成功，返回bucket_t
            // 如果key = 0， 说明在索引i的位置上还没有缓存过方法，同样需要返回该bucket_t，用于终止缓存查询。
            return &b[i];
        }
    } while ((i = cache_next(i, m)) != begin);
// 这里其实就是找到我们cache_t中buckets列表里面需要匹配的bucket。
    // hack
    // 如果此时还没有找到key对应的bucket_t，或者是空的bucket_t，则循环结束，说明查找失败，调用下面的bad_cache函数
    Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
    cache_t::bad_cache(receiver, (SEL)k, cls);
}

上一步我们如果找到bucket_t，那么我们直接进行填充bucket->set(key, imp);，但是我们还有一种就是没有找到sel的情况，所以要进行一个判断：

if (bucket->key() == 0) cache->incrementOccupied();
//cache->incrementOccupied()这个函数里面就是下面这个：
void cache_t::incrementOccupied() 
{
    _occupied++;
}

然后进行bucket填充

bucket->set(key, imp);

以上就是cache_t分析。