OC类底层探索 — 方法缓存cache_t

前言

从之前对类的探索，还剩下类对象 objc_class 的成员 cache 没有探索。看名字我们知道它是缓存，下面我们通过源码研究一下。

struct objc_class : objc_object {
    // Class ISA; // 8
    Class superclass; // 8
    cache_t cache;    // 16 不是8         // formerly cache pointer and vtable
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags

    class_rw_t *data() { 
        return bits.data();
    }

    // ...省略...

一、cache_t 源码分析

1. cache_t 基本结构

struct cache_t {
    struct bucket_t *_buckets; // 8
    mask_t _mask;  // 4
    mask_t _occupied; // 4

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：数组，是bucket_t结构体的数组，bucket_t是用来存放方法的SEL内存地址和IMP的

_mask：的大小是数组大小 - 1，用作掩码。（因为这里维护的数组大小都是2的整数次幂，所以_mask的二进制位000011, 000111, 001111）刚好可以用作hash取余数的掩码。刚好保证相与后不超过缓存大小。

_occupied：当前已缓存的方法数，缓存数组中已使用的容量。

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

_imp：函数调用地址，方法实现IMP
cache_key_t _key： _key实际就是sel强转(cache_key_t)sel，把sel方法名字转为十进制。

通过观察 arm64 中，存的是MethodCacheIMP _imp、cache_key_t _key，这些属性证明缓存的就是方法。

二、cache_t 缓存方法的流程

1. 缓存入口

点击cache_t中的public函数，会进入到objc-cache.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 writers 来看。
首先就是 cache_fill。

2. cache_fill

查看 cache_fill 源码，我们发现主要是调用了 cache_fill_nolock 方法：

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
}

3. cache_fill_nolock

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

    // Never cache before +initialize is done
    // 没有初始化的缓存直接return
    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);
}

cache_getImp

if (cache_getImp(cls, sel)) return;
判断当前cls下的sel是否已经被缓存了，如果已经有缓存直接返回。确保缓存没有被其他线程写入，才能进行接下来的填充缓存的操作。

getCache

cache_t *cache = getCache(cls);
获取当前类的缓存，内部实现如下：

cache_t *getCache(Class cls) 
{
    assert(cls);
    return &cls->cache;
}

getKey

cache_key_t key = getKey(sel);
通过sel方法获取缓存key，其实就是一个类型的强转，内部实现如下：

cache_key_t getKey(SEL sel) 
{
    assert(sel);
    return (cache_key_t)sel;
}

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

在已占用内存occupied的基础上 +1，得到新的缓存占用大小newOccupied。

mask_t capacity = cache->capacity();

获取当前hash表的容量，也就是总容量大小。

cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);

判断缓存是否为空；如果缓存为空，重新开辟空间，最少4字节

if (cache->isConstantEmptyCache()) {
    cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
}

// 1左移两位，也就是4字节
enum {
    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2)
};

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

    // 设置新的buckets和mask
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    // 释放旧缓存
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false);
    }
}

cache->expand();

判断newOccupied大于总容量的3/4，走expand()进行缓存扩容，小于等于3/4仍使用现有缓存空间。

else if (newOccupied <= capacity / 4 * 3) {
    // Cache is less than 3/4 full. Use it as-is.
} else {
    cache->expand();
}

expand：扩容

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    // 旧缓存空间
    uint32_t oldCapacity = capacity(); 
    // 扩容为二倍旧的缓存空间
    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);
}

最后把新调用的方法添加到缓存中，并存储key和imp

// 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(); // 如果key==0则说明之前未存储过这个key，占用空间+1
bucket->set(key, imp); // 存储 key和imp 到bucket

3. ·find() 查找缓存key

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);
    // 这一步其实相当于 i = i-1,回到上面do循环里面，相当于查找散列表上一个单元格里面的元素，再次进行key值 k的比较，
    //当i=0时，也就i指向散列表最首个元素索引的时候重新将mask赋值给i，使其指向散列表最后一个元素，重新开始反向遍历散列表，
    //其实就相当于绕圈，把散列表头尾连起来，不就是一个圈嘛，从begin值开始，递减索引值，当走过一圈之后，必然会重新回到begin值，
    //如果此时还没有找到key对应的bucket_t，或者是空的bucket_t，则循环结束，说明查找失败，调用bad_cache方法。
 
    // hack
    Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
    cache_t::bad_cache(receiver, (SEL)k, cls);
}

mask_t begin = cache_hash(s, m);

static inline mask_t cache_hash(cache_key_t key, mask_t mask) 
{
    return (mask_t)(key & mask);
}

cache_hash(s, m) 是 hash 算法，bucket_t里边缓存的实际上就是一个hash表，可以看做是 key：value 的结构，begin是查询的起始索引。

do...white

闭环查找，如果取出来的 key = k，则查询成功，返回该bucket_t；
如果 key = 0，说明在索引 i 的位置上还没有缓存过方法，同样需要返回该 bucket_t，用于中止缓存查询。

do {
    if (b[i].key() == 0  ||  b[i].key() == k) {
        return &b[i];
    }
} while ((i = cache_next(i, m)) != begin);

static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}

三、总结

实例方法缓存在类中，类方法缓存在元类中

方法缓存是以 hash表 的形式存储

cache_t 当前使用缓存空间在大于3/4时会进行扩容，扩容时会抹除旧的 buckets 创建新的二倍当前空间，然后把最近一次的临界方法缓存进来

缓存方法是为了最大化提高程序的执行效率