[iOS底层]-cache_t分析

2020/9/18 posted in  iOS底层 总阅读量

[iOS底层]-类的结构分析中我们讨论了类的结构如下:

同时使用首地址偏移的办法研究了bits,同样,今天我们也用此方法来研究一下类的cache

cache_t是什么?

下载cache_t分析demo(基于objc4-781源码),使用首地址偏移方法打印cache_t,偏移量为8+8=16

  • _buckets: 是一个数组,存放多个bucket_t结构体指针,bucket_t存放selimp.
  • _mask: 地址掩码,和前面我们接触过的ISA_MASK是类似的。
  • flags: 标记
  • _occupied: 缓存的个数,记录缓存数量。

查看cache_t源码,确实是存在上面4个属性。

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    explicit_atomic<struct bucket_t *> _buckets; 
    explicit_atomic<mask_t> _mask;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;

#if __LP64__
    uint16_t _flags; 
#endif
    uint16_t _occupied;
};

CACHE_MASK_STORAGE_OUTLINED: 模拟器和MacOS
CACHE_MASK_STORAGE_HIGH_16: 真机并且64位
CACHE_MASK_STORAGE_LOW_4: 真机不是64位

_buckets信息打印

_buckets根据源码可知是explicit_atomic<struct bucket_t *>类型的一个数组,explicit_atomic是继承自std::atomic<T>,主要是确保线程安全。其中泛型struct bucket_t *才是真正的类型,定义如下。

struct bucket_t {
    // 属性
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;

    // 方法
    inline SEL sel() const { ...省略实现 }
    inline IMP imp(Class cls) const { ...省略实现 }
};

main.m的19行打一个断点,运行后打印_buckets信息。

lldb打印信息如下:

  • 获取buckets需要调用cache_t的buckets()方法
  • 调用bucket_t的sel()方法打印sel。
  • 调用bucket_t的imp()方法打印imp。
  • 多个bucket可以使用p $2.buckets()[0].sel()来打印,通过数组下标打印多个bucket。

cache_t是如何存储的?

objc-cache.mm文件中我们可以找到cache_t::insert方法,这个方法的实现就是cache_t的存储过程。

根据源码我们可以发现insert方法主要做了三件事:

  1. 开辟buckets所需内存
  2. 计算插入位置
  3. 插入缓存

开辟buckets

下面是cache_t::insert中关于buckets内存开辟部分的源码

void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
    ...
    
    // Use the cache as-is if it is less than 3/4 full
    mask_t newOccupied = occupied() + 1; // 计算出当前缓存已占用数量
    unsigned oldCapacity = capacity(), capacity = oldCapacity; // 读取旧容量
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE;
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) { // 4  3 + 1 bucket cache_t
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 扩容两倍 4
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);  // 内存 库容完毕
    }
    
    ...
}
  • 先计算出当前已占用多少容量
  • 读取旧容量,然后判断容量是否够存
    1. 没有开辟缓存空间,则开辟空间,一次开辟4个
    2. 如果已占用数量小于等于开辟空间的3/4,不开辟空间
    3. 如果超过3/4的容量,则在当前内存基础上进行一倍的扩容。

每次开辟空间后都调用了reallocate方法,这个方法是什么作用呢?

ALWAYS_INLINE
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    bucket_t *oldBuckets = buckets();
    bucket_t *newBuckets = allocateBuckets(newCapacity); //开辟新空间

    ASSERT(newCapacity > 0);
    ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);

    setBucketsAndMask(newBuckets, newCapacity - 1); // 存储buckets和mask
    
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity); //释放旧buckets
    }
}
  • 根据newCapacity开辟内存空间

    // allocateBuckets方法里开辟内存的代码
    bucket_t *newBuckets = (bucket_t *)calloc(cache_t::bytesForCapacity(newCapacity), 1);
    
  • 储存newBucketsmaskmasknewCapacity - 1

    // 真机状态下,setBucketsAndMask存储代码
    _maskAndBuckets.store(((uintptr_t)newMask << maskShift) | (uintptr_t)newBuckets, std::memory_order_relaxed);
    
  • 如果要释放旧缓存,则调用cache_collect_free方法。

  • 本方法作用就是在扩容后重新分配空间,同时会清空以前的缓存。每次扩容后重新开始记录缓存。

扩容算法流程如下图所示


计算插入位置并缓存

ALWAYS_INLINE
void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
    ...

    bucket_t *b = buckets(); // 获取buckets地址
    mask_t m = capacity - 1; // 获取mask
    mask_t begin = cache_hash(sel, m); // 通过哈希算法sel & mask计算出插入的位置
    mask_t i = begin;

    // 通过循环保证begin不和已有的值冲突
    do {
        if (fastpath(b[i].sel() == 0)) {
            incrementOccupied();
            b[i].set<Atomic, Encoded>(sel, imp, cls);
            return;
        }
        if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }
    } while (fastpath((i = cache_next(i, m)) != begin));
    
    ...
}
  • 通过哈希算法计算出插入位置
  • 判断插入位置是否有冲突
    • 没有冲突,调用incrementOccupied();方法增加占用计数,调用b[i].set<Atomic, Encoded>(sel, imp, cls);缓存sel和imp
    • 有冲突,再次进行哈希,计数出新的位置,直到没有冲突为止。