IOS底层原理之cache_t结构

在Object-C语言中，方法在调用之后都会被缓存起来，在下一次调用的时候就会去缓存中拿取，缓存方法的地方是一个叫cache_t的结构。本文基于源码分析cache_t的结构原理。

1、 cache_t内部结构

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

这一段代码就是cache_t的源码。

• _buckets 是一个bucket_t结构体的数组，bucket_t里面存放SEL的key和imp地址。

struct bucket_t {
   cache_key_t _key;
    MethodCacheIMP _imp;
};

• _mask的大小等于数组的大小-1。
• _occupied 表示的是已经存取的方法的个数。

2、 cache_t的存入

方法在调用的时候，先去缓存中查找，如果缓存中已经存在了该方法，则直接返回，否则就会把方法缓存取来。

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
    cache_key_t key = getKey(sel);//将sel转换为key

    // Use the cache as-is if it is less than 3/4 full
    mask_t newOccupied = cache->occupied() + 1;
    mask_t capacity = cache->capacity();
   //判断cache是否初始化
    if (cache->isConstantEmptyCache()) {
        // Cache is read-only. Replace it.
        //初始化cache
        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();//cache扩容
    }

    // 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);//根据key查找
    if (bucket->key() == 0) cache->incrementOccupied();
    bucket->set(key, imp);//添加方法到缓存
}

• cache尚未初始化，则会分配一个大小为4的数组，_mask赋值为3。
• 如果缓存方法后的大小不大于_buckets容量的四分之三，则表示容量尚未饱和，可以继续缓存方法。
• 如果缓存方法后的大小超过_buckets容量的四分之三，则会扩容为原来的2倍，并放弃原有的缓存，新扩展的缓存为空。

3 、cache的初始化

在cache尚未初始化的时候会调用reallocate方法对cache进行初始化，分配一个大小为4的数组，mask赋值为3。

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    bool freeOld = canBeFreed();
    bucket_t *oldBuckets = buckets();//获取现有的buckets
    bucket_t *newBuckets = allocateBuckets(newCapacity);//开辟一个新的buckets
    // 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);
    //重新设置buckets和mask
    setBucketsAndMask(newBuckets, newCapacity - 1);
   //回收旧的buckets
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false);
    }
}

4、 cache扩容

当需要缓存的方法数量超过了当前容量的四分之三时，进行扩容，扩容为当前容量的2倍。

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    // 拿到当前的容量
    uint32_t oldCapacity = capacity();
    // 扩容当前容量的2倍
    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;
    }
   // 开辟新的buckets
    reallocate(oldCapacity, newCapacity);
}

5、 _buckets查找

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);
    // hack
    Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
    cache_t::bad_cache(receiver, (SEL)k, cls);
}

cache_next方法其实就是i= i-1，回到do循环里面，相当于查找数据的上一个元素。当i=0的时候，i指向的是数组的首元素位置，重新将mask赋值给i，使其指向散列表最后一个元素，重新开始反向遍历数组。

#if __arm__  ||  __x86_64__  ||  __i386__
// objc_msgSend has few registers available.
// Cache scan increments and wraps at special end-marking bucket.
#define CACHE_END_MARKER 1
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}

#elif __arm64__
// objc_msgSend has lots of registers available.
// Cache scan decrements. No end marker needed.
#define CACHE_END_MARKER 0
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}

arm、x86_64、i386平台和arm64平台cache_next方法的处理不一样，我这里只是对arm64平台进行了分析。

6、 cache流程

cache流程图