系统底层源码分析(17)——类结构中的cache

上篇文章探究了类的结构，其中提到cache，今天就来探究一下。

• 结构

struct objc_class : objc_object {
    // Class ISA; 
    Class superclass; // 父类
    cache_t cache;    // 缓存          // formerly cache pointer and vtable
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
    ...
};

struct cache_t {
    struct bucket_t *_buckets;//缓存方法
    mask_t _mask;//缓存容量
    mask_t _occupied;//缓存个数
    ...
};

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

• 作用

1. 从结构可以看出cache作用应该是调用方法后对其缓存，加快之后的调用速度。我们可以写段代码，检验一下：

Person *person = [Person alloc];
Class pClass = [Person class];
[person sayHello];

接着断点运行打印内存结构：

2019-12-25 00:39:22.566292+0800 Test[3586:42169] Person say : -[Person sayHello]
(lldb) x/4gx pClass
0x1000012e0: 0x001d8001000012b9 0x0000000100b36140
0x1000012f0: 0x0000000101e23c20 0x0000000100000003
(lldb) p (cache_t *)0x1000012f0
(cache_t *) $1 = 0x00000001000012f0
(lldb) p *$1
(cache_t) $2 = {
  _buckets = 0x0000000101e23c20
  _mask = 3
  _occupied = 1
}
(lldb) p $2._buckets
(bucket_t *) $3 = 0x0000000101e23c20
(lldb) p *$3
(bucket_t) $4 = {
  _key = 4294971020
  _imp = 0x0000000100000c60 (Test`-[Person sayHello] at Person.m:13)
}

2. 一开始cache没有值，调用[person sayHello]后才有了值，由此可见，类的cache缓存了调用过的实例方法。从而也可以推导出元类的cache缓存了调用过的类方法：

(lldb) p/x 0x001d8001000012b9 & 0x00007ffffffffff8ULL
(unsigned long long) $5 = 0x00000001000012b8

(lldb) x/4gx 0x00000001000012b8
0x1000012b8: 0x001d800100b360f1 0x0000000100b360f0
0x1000012c8: 0x0000000101e236c0 0x0000000200000003
(lldb) p (cache_t *)0x1000012c8
(cache_t *) $6 = 0x00000001000012c8
(lldb) p *$6
(cache_t) $7 = {
  _buckets = 0x0000000101e236c0
  _mask = 3
  _occupied = 2
}
(lldb) p $7._buckets
(bucket_t *) $8 = 0x0000000101e236c0
(lldb) p *$8
(bucket_t) $9 = {
  _key = 4298994200
  _imp = 0x00000001003cc3b0 (libobjc.A.dylib`::+[NSObject alloc]() at NSObject.mm:2294)
}

3. 我们继续验证：

Person *person = [[Person alloc] init];
Class pClass = [Person class];

[person sayHello];
[person sayCode];
[person sayNB]; 

接着断点运行打印内存结构：

(lldb) x/4gx pClass
0x1000012e8: 0x001d8001000012c1 0x0000000100b36140
0x1000012f8: 0x0000000101029950 0x0000000100000007
(lldb) p (cache_t *)0x1000012f8
(cache_t *) $1 = 0x00000001000012f8
(lldb) p *$1
(cache_t) $2 = {
  _buckets = 0x0000000101029950
  _mask = 7
  _occupied = 1
}
(lldb) p $2._buckets
(bucket_t *) $3 = 0x0000000101029950
(lldb) p *$3
(bucket_t) $4 = {
  _key = 0
  _imp = 0x0000000000000000
}
(lldb) p $2._buckets[0]
(bucket_t) $5 = {
  _key = 0
  _imp = 0x0000000000000000
}
(lldb) p $2._buckets[1]
(bucket_t) $6 = {
  _key = 0
  _imp = 0x0000000000000000
}
(lldb) p $2._buckets[2]
(bucket_t) $7 = {
  _key = 4294971026
  _imp = 0x0000000100000ce0 (Test`-[Person sayNB] at Person.m:25)
}
(lldb) p $2._buckets[3]
(bucket_t) $8 = {
  _key = 0
  _imp = 0x0000000000000000
}

测试调用多个方法时，我们发现缓存的方法只有[Person sayNB]，而且_mask从3变成了7，这些看来是缓存策略影响了。

• 源码

1. 我们从objc4-750源码探究，直入主题，从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;//默认0，递增
    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();//超过3/4就扩容
    }

    // 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);//缓存方法
}

2. 第一次调用方法（[person init]），还没缓存，就调用reallocate，这时capacity为0，INIT_CACHE_SIZE为4，最终_mask会等于3：

struct bucket_t *cache_t::buckets() 
{
    return _buckets; 
}

mask_t cache_t::mask() 
{
    return _mask; 
}

mask_t cache_t::occupied() 
{
    return _occupied;
}
...
mask_t cache_t::capacity() 
{
    return mask() ? mask()+1 : 0; //默认0，有值+1
}

enum {
    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2)  //等于4
};

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

    bucket_t *oldBuckets = buckets();
    bucket_t *newBuckets = allocateBuckets(newCapacity);//创建
    ...
    setBucketsAndMask(newBuckets, newCapacity - 1);// -1 是一种算法，为了提前扩容，更安全
    
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);//清空旧的缓存, 所以扩容缓存后，旧的缓存没了
        cache_collect(false);
    }
}

bucket_t *allocateBuckets(mask_t newCapacity)
{
    bucket_t *newBuckets = (bucket_t *)
        calloc(cache_t::bytesForCapacity(newCapacity), 1);//初始化
    ...
    return newBuckets;
}

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    ...
    _buckets = newBuckets;//新的容器
    ...
    _mask = newMask;
    _occupied = 0;//归0
}

3. 经过调多个方法后（最后调用[person sayNB]），_mask经过mask()+1和newCapacity - 1，此时应为4，缓存空间超过容量的3/4（4 > 4*3/4），需要进行扩容：

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    
    uint32_t oldCapacity = capacity();
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;//变成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);//重置缓存大小
}

此时经过reallocate重置缓存大小并清空旧的缓存，所以只保留了[person sayNB]，而且_mask变成2倍为8，再通过newCapacity - 1变成7。

4. 缓存容量调整好后，方法最终都会通过bucket->set(key, imp)缓存下来，方法数量也会通过incrementOccupied记录：

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

void bucket_t::set(cache_key_t newKey, IMP newImp)
{
    assert(_key == 0  ||  _key == newKey);
    
    _imp = newImp;
    
    if (_key != newKey) {
        mega_barrier();
        _key = newKey;
    }
}

• 总结

• 方法缓存是为了提高程序的执行效率；
• 类的cache用来缓存实例方法；
• 元类的cache用来缓存类方法；
• 如果已有缓存就获取返回；如果没有缓存就会创建容器缓存；如果缓存超出容量的3/4就会扩容，变成2倍，并且清空旧的缓存；