iOS底层学习 - cache_t的原理分析

本文的主要目的是理解cache_t以及sel-imp的缓存原理

cache中存储的是什么？

首先，我们需要知道cache中存储的到底是什么？

查看cache_t的源码，发现分成了3个架构的处理，其中真机的架构中，mask和bucket是写在一起，目的是为了优化，可以通过各自的掩码来获取相应的数据
- CACHE_MASK_STORAGE_OUTLINED 表示运行的环境 模拟器 或者 macOS
- CACHE_MASK_STORAGE_HIGH_16 表示运行环境是 64位的真机
- CACHE_MASK_STORAGE_LOW_4 表示运行环境是 非64位的真机

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED//macOS、模拟器 -- 主要是架构区分
    // explicit_atomic 显示原子性，目的是为了能够 保证 增删改查时 线程的安全性
    //等价于 struct bucket_t * _buckets;
    //_buckets 中放的是 sel imp
    //_buckets的读取 有提供相应名称的方法 buckets()
    explicit_atomic<struct bucket_t *> _buckets;
    explicit_atomic<mask_t> _mask;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 //64位真机
    explicit_atomic<uintptr_t> _maskAndBuckets;//写在一起的目的是为了优化
    mask_t _mask_unused;

    //以下都是掩码，即面具 -- 类似于isa的掩码，即位域
    // 掩码省略....
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4 //非64位 真机
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;

    //以下都是掩码，即面具 -- 类似于isa的掩码，即位域
    // 掩码省略....
#else
#error Unknown cache mask storage type.
#endif

#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;

    //方法省略.....
}

查看bucket_t的源码，同样分为两个版本，真机 和 非真机，不同的区别在于sel 和 imp的顺序不一致

struct bucket_t {
private:
#if __arm64__ //真机
    //explicit_atomic 是加了原子性的保护
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else //非真机
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
    //方法等其他部分省略
}

所以通过上面两个结构体源码可知，cache中缓存的是sel-imp

整体的结构如下图所示

image

在cache中查找sel-imp

准备工作

在main中定义一个LGPersons类，并定义两个属性及4个实例方法及其实现，并在main函数中调用

@interface LGPersons : NSObject
@property (nonatomic, copy) NSString *name;
@property (nonatomic, strong) NSString *nickName;

- (void)sayHello;

- (void)sayCode;

- (void)say1;

- (void)say2;

@end

@implementation LGPersons

- (void)sayHello{
    NSLog(@"%s",__func__);
}

- (void)sayCode{
    NSLog(@" %s",__func__);
}

- (void)say1{
    NSLog(@" %s",__func__);
}

- (void)say2{
    NSLog(@" %s",__func__);
}

LGPersons *person=[LGPersons alloc];
Class pClass=[LGPersons class];
[person sayHello];
[person sayCode];
[person say1];
[person say2];

通过源码查找

运行执行，断在[person sayHello];部分，此时执行以下lldb调试流程

cache分析1.png
- 因为在类的结构中，cache之前有isa和superclass，各占用了8个字节，总共16个字节，所以cache属性的获取，需要通过pclass的首地址平移16字节，再强转为cache_t，打印地址。
- 此时_occupied的值为0。
执行代码，到达[person sayCode]一行。再次打印cache_t内容:

cache分析2.png
- 此时imp有值了,_occupied占用位置也由0变成了1 。
我们继续跟进，打印_buckets内容，确定他存储的是不是我们所定义的方法:

cache分析3.png
- 从源码的分析中，我们知道sel-imp是在cache_t的_buckets属性中（目前处于macOS环境），而在cache_t结构体中提供了获取_buckets属性的方法buckets()
- 获取了_buckets属性，就可以获取sel-imp了，这两个的获取在bucket_t结构体中同样提供了相应的获取方法sel() 以及 imp(pClass),打印出来就是sayHello
照着上面的逻辑继续执行一行代码，运行[person sayCode]，打印buckets数组。

cache分析4.png

*如图，既然拿到了数组首地址，而数组的元素类型都是一致的，我们可以通过内存偏移读取元素。当然因为buckets是一个数组，就可以直接使用数组下标进行读取，例如p $10[1].sel()就可直接打印出相应的结果

cache_t的缓存原理

查看cache_t结构，发现源码中，有incrementOccupied函数和setBucketsAndMask函数。
看到incrementOccupied方法就应该想到添加,cache的含义就是缓存,进入incrementOccupied方法中

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

全局搜索执行该方法的位置，找到void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)中

cache_insert.png

跟随源码继续探究insert方法是在何时调用的,全局搜索cache->insert,只有一个地方

cahce_fill.png

分析这段代码，是当cls->isInitialized()为真,则获取cache,把cls的sel和imp以及receiver插入到cache中。内容不多，我们再回头看看void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)方法具体做了些什么

void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
#if CONFIG_USE_CACHE_LOCK
    cacheUpdateLock.assertLocked();
#else
    runtimeLock.assertLocked();
#endif
    ASSERT(sel != 0 && cls->isInitialized());
    // 原occupied计数+1
    mask_t newOccupied = occupied() + 1;
    // 进入查看： return mask() ? mask()+1 : 0;
    // 就是当前mask有值就+1，否则设置初始值0
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    // 当前缓存是否为空
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        // 如果为空，就给空间设置初始值4
        // (进入INIT_CACHE_SIZE查看，可以发现就是1<<2，就是二进制100，十进制为4)
        if (!capacity) capacity = INIT_CACHE_SIZE;
        // 创建新空间（第三个入参为false，表示不需要释放旧空间）
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    // CACHE_END_MARKER 就是 1
    // 如果当前计数+1 < 空间的 3/4。 就不用处理
    // 表示空间够用。 不需要空间扩容
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) {
        // Cache is less than 3/4 full. Use it as-is.
    }
    // 如果计数大于3/4， 就需要进行扩容操作
    else {
        // 如果空间存在，就2倍扩容。 如果不存在，就设为初始值4
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        // 防止超出最大空间值（2^16 - 1）
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        // 创建新空间（第三个入参为true，表示需要释放旧空间）
        reallocate(oldCapacity, capacity, true);
    }
    // 读取现在的buckets数组
    bucket_t *b = buckets();
    // 新的mask值(当前空间最大存储大小)
    mask_t m = capacity - 1;
    // 使用hash计算当前函数的位置(内部就是sel & m， 就是取余操作，保障begin值在m当前可用空间内)
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;
    do {
        // 如果当前位置为空（空间位置没被占用）
        if (fastpath(b[i].sel() == 0)) {
            // Occupied计数+1
            incrementOccupied();
            // 将sle和imp与cls关联起来并写入内存中
            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;
        }
        // 如果位置有值，再次使用哈希算法找下一个空位置去写入
        // 需要注意的是，cache_next内部有分支： 
        // 如果是arm64真机环境： 从最大空间位置开始，依次-1往回找空位
        // 如果是arm旧版真机、x86_64电脑、i386模拟器： 从当前位置开始，依次+1往后找空位。不能超过最大空间。
        // 因为当前空间是没超出mask最大空间的，所以一定有空位置可以放置的。
    } while (fastpath((i = cache_next(i, m)) != begin));
    // 各种错误处理
    cache_t::bad_cache(receiver, (SEL)sel, cls);
}

其中的reallocate方法 : 创建新空间并释放旧空间的函数

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    // 读取旧buckets数组
    bucket_t *oldBuckets = buckets();
    // 创建新空间大小的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
    // 新空间必须大于0
    ASSERT(newCapacity > 0);
    // 新空间-1 转为mask_t类型，再与新空间-1 进行判断
    ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
    // 设置新的bucktes数组和mask
    // 【重点】我们发现mask就是newCapacity - 1, 表示当前最大可存储空间
    setBucketsAndMask(newBuckets, newCapacity - 1);
    // 释放旧内存空间
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
    }
}

核心方法allocateBuckets：创建新空间大小的buckets数组

bucket_t *allocateBuckets(mask_t newCapacity)
{
    // 创建1个bucket
    bucket_t *newBuckets = (bucket_t *)
        calloc(cache_t::bytesForCapacity(newCapacity), 1);
    // 将创建的bucket放到当前空间的最尾部，标记数组的结束
    bucket_t *end = cache_t::endMarker(newBuckets, newCapacity);

#if __arm__
    // End marker's sel is 1 and imp points BEFORE the first bucket.
    // This saves an instruction in objc_msgSend.
    end->set<NotAtomic, Raw>((SEL)(uintptr_t)1, (IMP)(newBuckets - 1), nil);
#else
    // 将结束标记为sel为1，imp为这个buckets
    end->set<NotAtomic, Raw>((SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    // 只是打印记录
    if (PrintCaches) recordNewCache(newCapacity);
    // 返回这个bucket
    return newBuckets;
}

cache_collect_free：释放内存空间

static void cache_collect_free(bucket_t *data, mask_t capacity)
{
#if CONFIG_USE_CACHE_LOCK
    cacheUpdateLock.assertLocked();
#else
    runtimeLock.assertLocked();
#endif
    if (PrintCaches) recordDeadCache(capacity);
    // 垃圾房： 开辟空间 （如果首次，就开辟初始空间，如果不是，就空间*2进行拓展）
    _garbage_make_room ();
    // 将当前扩容后的capacity加入垃圾房的尺寸中，便于后续释放。
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    // 将当前新数据data存放到 garbage_count 后面 这样可以释放前面的，而保留后面的新值
    garbage_refs[garbage_count++] = data;
    // 不记录之前的缓存 = 【清空之前的缓存】。
    cache_collect(false);
}

以上就是cache_t的代码分析流程,为了方便理解和查看,下面用流程图的方式具体实现下:

cache_t流程.png

总结:

cache_t作为类结构体中的一个元素,作用是缓存类的sel和imp.使得类在调用方法时能快速的发送消息,减少类查找方法的时间，具体来说就是objc_msgSend执行时会触发方法查找，找到方法后会调用cache_fill()方法把方法缓存到cache中。其中的objc_msgSend 和 cache_getImp为读取流程。
occupied存储的是当前占用的空间大小，函数写入cache缓存时，occupied会加1，mask记录当前cache最大可存储空间。当触发insert操作时，会判断当前空间使用率是否超过3/4，超过则会进行空间的2倍扩容，释放原来的缓存空间，之前cache的所有内容都被清空了，所以occupied重置为0，从新开始计数，mask记录新空间的最大可存储大小。也因为旧空间被释放，此时cache中的buckets数组打印的值就会有丢失的情况。
buckets数组的顺序与执行顺序也不相同，因为插入操作是使用的hash算法，插入位置是经过取余计算的，且如果插入位置已经有值，就会不停的后移1位，直到找到空位置完成插入位置。