iOS cache_t分析

在iOS中对象或者类调用一个方法，这个方法是会被缓存起来的，当下一次再次调用这个方法的时候，会先从缓存里查找，如果没有再从类或者元类以他们的父类中查找。接下来就让我们类分析下缓存是如何实现的。

首先我们来看一下类的定义。

struct objc_class : objc_object {
    // Class ISA;
    Class superclass;
    cache_t cache;             // formerly cache pointer and vtable
    class_data_bits_t bits;
}

我们可以看到这个名为cache_t cache的成员变量。这就是我们今天要探索的主角。

接下来我们来看下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：数组，是bucket_t结构体的数组，bucket_t是用来存放方法的SEL内存地址和IMP的。
• _mask的大小是数组大小 - 1，用作掩码。（因为这里维护的数组大小都是2的整数次幂，所以_mask的二进制位000011, 000111, 001111）刚好可以用作hash取余数的掩码。刚好保证相与后不超过缓存大小。
• _occupied是当前已缓存的方法数。即数组中已使用了多少位置。

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

缓存策略

那么我们的方法是如何缓存的呢？

接下来我们通过_mask找到了

mask_t cache_t::capacity() 
{
    return mask() ? mask()+1 : 0; 
}

再通过capacity()函数定位到

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    
    uint32_t oldCapacity = capacity();
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;//INIT_CACHE_SIZE 为4

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

再通过expand()定位到

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);//这里将sel转化为cache_key_t，也就是数字，主要是为了方便查找、。

    // 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.
        //当容量超过capacity的四分之三时，执行扩容的逻辑。
    }
    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);
}

扩容以及清理的探索

我们发现在扩容函数中调用了reallocate函数，接下来就让我们来看看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);
    
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false);
    }
}

• 首先获取旧的buckets。
• 再根据容量初始化一个新的buckets。
• 再讲新的buckets和mask设置上去，并将_occupied清0。
• 最后将旧的buckets释放掉。

cache在执行扩容的同时会清理掉旧的buckets,也就是说，之前缓存的方法会被清空，这是LRU淘汰算法的一个应用。

最后我们在objc的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)