方法缓存cache_t 探究

类结构分析中，只看了大致看了一下cache的基本结构，接下来我来深入了解一下cache_t在类对象中的作用。

cache_t的结构

//简化后的cache_t
struct cache_t {
    struct bucket_t *_buckets; 
    mask_t _mask; 
    mask_t _occupied;
}

//简化后的 bucket_t
//存储着方法实现imp 和 缓存的key
struct bucket_t {
    MethodCacheIMP _imp;
    cache_key_t _key; 
};

_buckets 是一个缓存方法的散列表
_mask 表示散列表长度 - 1
_occupied表示已经占用数量

cache_t中的函数分析

前面只看了cache_t的结构，接下来看一下它提供有哪些函数

struct cache_t {
    struct bucket_t *_buckets; 
    mask_t _mask; 
    mask_t _occupied;

public:
    struct bucket_t *buckets();
    mask_t mask();
    mask_t occupied();
    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    void initializeToEmpty();

    mask_t capacity();
    bool isConstantEmptyCache();
    bool canBeFreed();

    static size_t bytesForCapacity(uint32_t cap);
    static struct bucket_t * endMarker(struct bucket_t *b, uint32_t cap);

    void expand();
    void reallocate(mask_t oldCapacity, mask_t newCapacity);
    struct bucket_t * find(cache_key_t key, id receiver);

    static void bad_cache(id receiver, SEL sel, Class isa) __attribute__((noreturn));
};

buckets()
这个方法的实现很简单就是_buckets对外的一个获取函数
mask()
获取缓存容量_mask
occupied()
获取已经占用的缓存个数_occupied
incrementOccupied()
增加缓存，_occupied自++

void cache_t::incrementOccupied() 
{
    _occupied++;
}

setBucketsAndMask(,)
这个函数是设置一个新的Buckets

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    _buckets = newBuckets; //设置新的_buckets 
    _mask = newMask; //设置新buckets的容量
    _occupied = 0; //新buckets默认占用为0
}

initializeToEmpty()
初始化cache并设置为空

void cache_t::initializeToEmpty()
{
    bzero(this, sizeof(*this)); //将cache 所有内容都抹除 （将所有cache的空间都填充为'\0'）
    _buckets = (bucket_t *)&_objc_empty_cache; //把_buckets指向cache empty的实现
}

_objc_empty_cache 为已经提供了的空cache

struct objc_cache _objc_empty_cache =
{
    0,        // mask
    0,        // occupied
    { NULL }  // buckets
};

capacity()

//获取buckets的容量
mask_t cache_t::capacity() 
{
    return mask() ? mask()+1 : 0; 
}

capacity()经过了出来，当mask() == 0时,返回0；当mask() > 0时，返回mask() + 1

mask() == 0 表示了buckets为空的状态
mask() > 0 表示了buckets已经存在缓存

那什么需要mask() + 1 ?
扩容算法需要：expand()中的扩容算法基本逻辑(最小分配的容量是4，当容量存满3/4时，进行扩容，扩容当前容量的两倍)；这样最小容量4的 1/4就是1，这就是mask() + 1的原因。

isConstantEmptyCache()
判断buckets是否为空
canBeFreed()
isConstantEmptyCache()取反，表示buckets不为空可以释放
bytesForCapacity()
expand()

void cache_t::expand()
{
    //拿到原有的buckets容量
    uint32_t oldCapacity = capacity(); 
    
    /*
    计算新buckets的容量
    INIT_CACHE_SIZE = 4
    如果 oldCapacity == 0，则使用最小容量4 
    如果 oldCapacity > 0，则扩容两倍
    */
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;

    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);
}

reallocate()

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    bool freeOld = canBeFreed();
    //拿到原有buckets
    bucket_t *oldBuckets = buckets();
    //创建一个新的buckets
    bucket_t *newBuckets = allocateBuckets(newCapacity);
    
    //设置新的buckets 和 mask（capacity - 1）
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    //抹掉原有buckets的数据
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false);
    }
}

为什么要创建新的新的buckets来替换原有的buckets并抹掉原有的buckets的方案，而不是在在原有buckets的基础上进行扩容？

减少对方法快速查找流程的影响：调用objc_msgSend时会触发方法快速查找，如果进行扩容需要做一些读写操作，对快速查找影响比较大。

对性能要求比较高：开辟新的buckets空间并抹掉原有buckets的消耗比在原有buckets上进行扩展更加高效

find()

bucket_t * cache_t::find(cache_key_t k, id receiver)
{
    bucket_t *b = buckets();
    mask_t m = mask();
    //计算 key 的 index
    mask_t begin = cache_hash(k, m);
    mask_t i = begin;
    do {
        //key = 0 ，表示i索引的bucket 还没有缓存方法，返回bucket 中止查找
        //key = k, 表示查询成功，返回该bucket
        if (b[i].key() == 0  ||  b[i].key() == k) {
            return &b[i];
        }
    } while ((i = cache_next(i, m)) != begin); //当出现 当出现hash碰撞 cache_next 查找下一个,直到回到begin

    // hack
    Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
    cache_t::bad_cache(receiver, (SEL)k, cls);
}

通过 cache_key_t 查找receiver中的 bucket_t *
如果碰到hash 冲突，则通过cache_next 偏移
cache_next 把散列表的头尾相连（ (i +1) % mask)

Hash

static inline mask_t cache_hash(cache_key_t key, mask_t mask) 
{
    //取余法计算索引
    return (mask_t)(key & mask);
}

key 就是 SEL
映射关系其实就是 key & mask = index
mask = 散列表长度 - 1
所以 index 一定是 <= mask

Hash表的原理： f(key) = index

Hash碰撞

两个方法key & mask,是完全有可能计算出相同的结果，这里是通过这个函数处理

// do {  } while ((i = cache_next(i, m)) != begin);
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}

当发生hash碰撞就查找下一个，cache_next就提供了这种方法，每次 +1 当 (i+1) = mask时，因为有 & mask 所以索引i = 0又回到了散列表头部。
这样就会把散列表头尾连接起来形成一个环。

什么时候存储到cache中

objc_msgSend第一次发送消息会触发方法查找，找到方法后会调用cache_fill()方法把方法缓存到cache中

cache添加缓存的核心代码

//方法查找后会调该方法来缓存方法
void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
    //这里省略了 lock的代码
    //填充cache
    cache_fill_nolock(cls, sel, imp, receiver);
}

static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
    // 如果能找到缓存就直接返回，确保没有其它线程把方法加入到cache中
    if (cache_getImp(cls, sel)) return;

    //获取cls的cache
    cache_t *cache = getCache(cls);
    //换算出sel的key
    cache_key_t key = getKey(sel);

    //加上即将加入缓存的占用数
    mask_t newOccupied = cache->occupied() + 1;
    //拿到当前buckets的容量
    mask_t capacity = cache->capacity();
    if (cache->isConstantEmptyCache()) {
        /*
          当cache为空时，则重新分配空间；
          当 capacity == 0时 ，使用最小的缓存空间 INIT_CACHE_SIZE = 4
        */
        cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
    }
    else if (newOccupied <= capacity / 4 * 3) {
        // Cache is less than 3/4 full. Use it as-is.
        // 使用的空间 newOccupied < 3/4, 不需要扩容
    }
    else {
        // Cache is too full. Expand it.
        // 使用的空间 newOccupied >= 3/4, 对cache进行扩容
        cache->expand();
    }

    //find 使用hash找到可用的bucket指针
    bucket_t *bucket = cache->find(key, receiver);
    //判断 bucket 是否可用，如果可用对齐occupied +1
    if (bucket->key() == 0) cache->incrementOccupied();
    //把缓存方法放到bucket中
    bucket->set(key, imp);
}

总结

mask = 散列表长度 - 1
除了Empty，最小的buckets大小是 4（为了支持扩容算法需要）
cache 扩容策略是 >= 3/4,扩容两倍
cache扩容是创建一个更大的buckets，替换原有的buckets
替换策略为了让方法快速查找更加安全稳定和提高效率