iOS进阶之路 (五)cache_t 方法缓存

608 阅读8分钟

上篇文章中,我们探索了Class的结构,并学习了其内部的成员了isa,superClass以及bits的作用,还剩下一个cache_t cache没有进行详细的介绍,我们只能基本知道,其内部存放的只是一个key和imp的键值对,本文就系统的学习cache_t。

1. cache_t的结构

先看下cache_t的源码

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

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:tmask_t可以看出是一个无符号Int类型,在64位下为uint32_t
  • _occupied:字面意思容积
  • _buckets:结构体指针

字面意思上cache肯定是一种缓存,而且又与方法有关。我们先猜测,cache的功能就是对方法进行缓存,加快方法调用速度。

2. cache_t 调试

2.1 LLVM调试

还是熟悉的测试代码

@interface AKPerson : NSObject {
    NSString *hobby;
}

@property (nonatomic, copy) NSString *name;

- (void)personInstanceMethed;
- (void)personInstanceMethed2;
- (void)personInstanceMethed3;
+ (void)personClassMethod;

@end

@implementation AKPerson

- (void)personInstanceMethed {}

- (void)personInstanceMethed2 {}

- (void)personInstanceMethed3 {}
+ (void)personClassMethod {}

@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        AKPerson *person = [[AKPerson alloc] init];
        Class clz = object_getClass(person);
        
        [person personInstanceMethed];

    }
    return 0;
}

_mask = 3,_occupied = 2,而且我们在_buckets找到了init和personInstanceMethed方法。

2.2 伪代码调试

LLVM调试太容易蒙圈了,我们用更直观的伪代码调试。

typedef uint32_t mask_t;
typedef uintptr_t cache_key_t;
typedef unsigned long  uintptr_t;

struct ak_bucket_t {
    IMP _imp;
    cache_key_t _key;
};

struct ak_cache_t {
    struct ak_bucket_t *_buckets;
    mask_t _mask;
    mask_t _occupied;
};

struct ak_class_data_bits_t {
    uintptr_t bits;
};

struct ak_objc_class {
    Class ISA;
    Class superclass;
    struct ak_cache_t cache;             // formerly cache pointer and vtable
    struct ak_class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
};

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        AKPerson *person = [[AKPerson alloc] init];
        Class clz = object_getClass(person);
        
        [person personInstanceMethed];
        
        struct ak_objc_class *ak_pClass = (__bridge struct ak_objc_class *)(clz);
        for (mask_t i = 0; i < ak_pClass->cache._mask; i++) {
            struct ak_bucket_t bucket = ak_pClass->cache._buckets[i];
            NSLog(@"%lu - %p",bucket._key,bucket._imp);
        }

    }
    return 0;
}

cmd + B 开始调试

  1. 调用一个实例方法

  • _mask = 3, _occupied = 2,与LLVM调试一致。
  1. 调用2个实例方法

  • _mask = 3, _occupied = 3,一切都很顺利。
  1. 调用3个实例方法
  • 然而当我们一次调用3个实例方法测试时,_mask = 7, _occupied = 1,这又是什么原因呢?
  • 为什么缓存了init和personInstanceMethed,没有缓存alloc方法呢?上一章我们说过,对象的方法存在类中,类的类方法以实例方法的形式存在元类中。alloc是类方法,存在元类中。

3. cache_t 策略

通过伪代码测试发现:cache_t不是调用一个方法就添加一个缓存,应该有特殊的缓存策略。

3.1 寻找切入点

  • 既然_mask发生了变化,我们就寻着_mask的线索,找cache_t中_mask发生变化的函数。首先想到的就是mask()函数,结果发现其只是反回了_mask本身。
mask_t cache_t::mask() 
{
    return _mask; 
}
  • 继续搜索mask(),发现在capacity()中有mask的相应操作,但是很模糊。
mask_t cache_t::capacity() 
{
    return mask() ? mask()+1 : 0; 
}

3.2 expand()

继续搜索capacity(), 找到了expand()扩容方法。

enum {
    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2)
};

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

  • 如果oldCapacity == 0,那么久用INIT_CACHE_SIZE(1<<2 实际为4)来初始化
  • 否则,那么就用 oldCapacity * 2 来作为newCapacity。
  • reallocate 创建并覆盖原来的缓存reallocate

扩容的逻辑我们已经找到,继续找cache_t何时何地调用了expand()。

3.3 cache_fill_nolock()

很快在cache_fill_nolock中找到了。

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

    if (!cls->isInitialized()) return;  // 1. 类是否初始化对象,没有就返回

    // 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; // 2. 通过cls和sel查找是否已经有缓存
    
    cache_t *cache = getCache(cls);     // 3. 获取当前cls的缓存

    // Use the cache as-is if it is less than 3/4 full
    mask_t newOccupied = cache->occupied() + 1;     // 4. newOccupied = occupied + 1
    mask_t capacity = cache->capacity();            // 5. 获取capacity
    
    if (cache->isConstantEmptyCache()) {                            
        // Cache is read-only. Replace it.
        cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);       // 6.1 如果缓存为空,重新创建并覆盖之前的缓存
    }
    else if (newOccupied <= capacity / 4 * 3) {
        // Cache is less than 3/4 full. Use it as-is.       // 6.2 如果新的缓存占用大小 <= 缓存容量的四分之三,则可以进行缓存流程
    }
    else {
        // Cache is too full. Expand it.                        
        cache->expand();        // 6.3 如果缓存不为空,且缓存占用大小已经超过了容量的四分之三,则需要进行扩容
    }

    bucket_t *bucket = cache->find(sel, receiver);      // 7.  通过key在缓存中查找到对应的bucket_t
    if (bucket->sel() == 0) cache->incrementOccupied(); 
    bucket->set<Atomic>(sel, imp);      // 8. 如果找到的bucket中key为0,那么_occupied++, 把key、imp成对放入bucket。
}
  1. 先根据cls找到当前类的缓存cache
  2. 新建newOccupied = cache.occupied + 1
  3. 如果newOccupied为空,新建并覆盖cache
  4. 如果newOccupied <= cache的容积 * 0.75,缓存
  5. 如果newOccupied > cache的容积 * 0.75, 扩容
  6. 把最新的imp和key缓存了下来,cache中仅仅只留下了最新的方法,这里就适用了LRU算法,把最近调用过的方法缓存下来

LRU算法的全称是Least Recently Used,也就是最近最少使用策略——这个策略的核心思想就是先淘汰最近最少使用的内容,在方法缓存中也用到了这种算法

3.4 cache_t::reallocate()

来看下mask和bucket是如何创建的

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

bucket_t *allocateBuckets(mask_t newCapacity)
{
    // Allocate one extra bucket to mark the end of the list.
    // This can't overflow mask_t because newCapacity is a power of 2.
    // fixme instead put the end mark inline when +1 is malloc-inefficient
    bucket_t *newBuckets = (bucket_t *)
        calloc(cache_t::bytesForCapacity(newCapacity), 1);

    bucket_t *end = cache_t::endMarker(newBuckets, newCapacity);

#if __arm__
    // End marker's key is 1 and imp points BEFORE the first bucket.
    // This saves an instruction in objc_msgSend.
    end->setKey((cache_key_t)(uintptr_t)1);
    end->setImp((IMP)(newBuckets - 1));
#else
    // End marker's key is 1 and imp points to the first bucket.
    end->setKey((cache_key_t)(uintptr_t)1);
    end->setImp((IMP)newBuckets);
#endif
    
    if (PrintCaches) recordNewCache(newCapacity);

    return newBuckets;
}

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    // objc_msgSend uses mask and buckets with no locks.
    // It is safe for objc_msgSend to see new buckets but old mask.
    // (It will get a cache miss but not overrun the buckets' bounds).
    // It is unsafe for objc_msgSend to see old buckets and new mask.
    // Therefore we write new buckets, wait a lot, then write new mask.
    // objc_msgSend reads mask first, then buckets.

    // ensure other threads see buckets contents before buckets pointer
    mega_barrier();

    _buckets = newBuckets;
    
    // ensure other threads see new buckets before new mask
    mega_barrier();
    
    _mask = newMask;
    _occupied = 0;
}
  1. oldBuckets获取到当前bucket
  2. 传入新的缓存容量allocateBuckets初始化bucket_t,保存在newBuckets
  3. setBucketsAndMask做的操作: 用新创建的bucket保存,mask=newcapcity-1,occupied置零(因为还没有方法缓存)
  4. 如果缓存不为空(需要释放)则释放原先的bucket、capacity

3.5 4.cache_t::find

cache_t::find是 查找class对应的cache的bucket

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);
}
  1. 获取当前cache_t下所有的缓存bucket
  2. 获取当前cache_t的缓存容量减一的值mask_t
  3. 获取起始索引
  4. 遍历bucket_t:如果key == 0 说明索引i位置上还没有缓存过方法;如果bucket的key == k,查询成功,返回bucket_t

4. 总结

4.1 为什么在0.75的时候进行扩容

capacity的变化主要发生在扩容cache->expand()的时候,当缓存已经占满了四分之三的时候,会进行两倍原来缓存空间大小的扩容。

在哈希这种数据结构里面,有一个概念用来表示空位的多少叫做装载因子——装载因子越大,说明空闲位置越少,冲突越多,散列表的性能会下降 负载因子是3/4的时候,空间利用率比较高,而且避免了相当多的Hash冲突,提升了空间效率

4.2 bucket与mask、capacity、sel、imp的关系

类cls拥有属性cache_t,cache_t中的buckets有多个bucket,bucket里存储着方法实现imp和方法编号sel强转成的key值cache_key_t

  • mask对于bucket,主要是用来在缓存查找时的哈希算法
  • capacity对于bucket,可以获取到cache_t中bucket的数量

4.3 cache_t的作用

Class中的Cache主要是为了在消息发送的过程中,进行方法的缓存,加快调用效率。其中使用了动态扩容的方法,当容量达到最大值的0.75时,开始2倍扩容,扩容时会完全抹除旧的buckets,并且创建新的buckets代替,之后把最近一次临界的imp和key缓存进来。

4.4 cache_t什么时候调用?

 * Cache readers (PC-checked by collecting_in_critical())
 * objc_msgSend*
 * cache_getImp

cache_fill_nolock的调用时机,我们在源码中可以看到,是在cache_fill中进行了调用。cache_fill的调用时机其实是在method lookup的过程中调用的,而方法查找则要牵扯到objc_msgSend,也就是消息发送机制。所以我们姑且可以认为,在消息发送的过程中,先通过缓存查找imp,如果查找到就直接调用,如果没有,那么就进行缓存。

关于消息发送机制,我们下篇文章会学习。

5. 参考资料

iOS探索 cache_t分析

HashMap的负载因子为什么默认是0.75?