iOS-底层原理9：objc_class 中 cache 原理分

在iOS-底层原理7：isa与类关联的原理和iOS-底层原理8：类 & 类结构分析中，分析了objc_class中isa和bits，这篇文章主要是分析objc_calss中的cache属性

1、源码初探

step1: 打开objc4源码， 搜索objc_class

objc_class结构体

step2: 点击进入cache_t

2.1: 暂时剔除const、void、static和函数

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;

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

查看其中的宏定义

// 是真机且是64位系统 
#if defined(__arm64__) && __LP64__              
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16
// 是真机但不是64位系统
#elif defined(__arm64__) && !__LP64__ 
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_LOW_4
// 其他
#else                                 
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_OUTLINED
#endif

2.2:现在我以macos为平台来进行探究。简化cache_t代码：

struct cache_t {
    explicit_atomic<struct bucket_t *> _buckets;
    explicit_atomic<mask_t> _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

但如果是真机呢

struct cache_t {
   explicit_atomic<uintptr_t> _maskAndBuckets;
   mask_t _mask_unused; // 猜测是系统暂时没用到的参数。😂  占坑
   
   // mask掩码移动位数
   static constexpr uintptr_t maskShift = 48;
   
   // 掩码清零4位
  static constexpr uintptr_t maskZeroBits = 4;
   
   // 可以存储的最大mask掩码值(2^16 - 1)
   static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
   
   // 用于从`_maskAndBuckets`中找回`buckets`的指针位置
   //  (1 << (48 - 4)) - 1  buckets最大位数只有43位
   static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
   
   // 没有足够的空间来存放buckets了
   static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers.");
  
   uint16_t _flags;
   uint16_t _occupied;
}

可以看到在真机的架构中，mask和bucket是写在一起，目的是为了优化，可以通过各自的掩码来获取相应的数据

step3: 进入bucket_t源码

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
    //方法等其他部分省略
}

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

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

cache_t缓存机制

初步了解了cache_t的内部结构，现在我们来探索cache_t的缓存机制

step1: 新建一个LBHPerson类，定义如下的属性、方法及其实现

//.h
@interface LBHPerson : NSObject

@property (nonatomic, copy) NSString *name;
@property (nonatomic, copy) NSString *nickName;

- (void)instanceMethod1;
- (void)instanceMethod2;
- (void)instanceMethod3;
- (void)instanceMethod4;
- (void)instanceMethod5;
+ (void)classMethod;

@end

//.m
@implementation LBHPerson

- (void)instanceMethod1
{
    NSLog(@"%s",__func__);
}
- (void)instanceMethod2
{
    NSLog(@"%s",__func__);
}
- (void)instanceMethod3
{
    NSLog(@"%s",__func__);
}
- (void)instanceMethod4
{
    NSLog(@"%s",__func__);
}
- (void)instanceMethod5
{
    NSLog(@"%s",__func__);
}

+ (void)classMethod
{
    NSLog(@"%s",__func__);
}

@end

step2: 在main函数中实例化LBHPerson类，并调用其中的3个实例方法，在person调用第一个方法处加一个断点，如图：

step3: lldb调试--在没有执行任何方法

* cache属性的获取，需要通过pclass的首地址平移16字节

step4: 点击step over，程序执行一步，此时-[LBHPerson instanceMethod1]已经执行，我们再看下此时cache的情况

* 从源码的分析中，我们知道sel-imp是在cache_t的_buckets属性（目前处于macOS环境），而在cache_t结构体中提供了获取_buckets属性的方法buckets()

* bucket_t结构体提供了获取sel属性的方法sel()和获取imp属性的方法imp(cls)

从lldb打印结果来看，sel、imp、mask、occupied等值出现了变化，由上图可知，在没有执行方法调用时，此时的cache是没有缓存的，执行了一次方法调用，cache中就有了一个缓存，即调用一次方法就会缓存一次方法。

我们现在了解了如何获取cache中sel-imp，如何验证打印的sel和imp就是我们调用的呢？

在machoView工具打开target的可执行文件，在方法列表中查看其imp的值是否是一致的，如果一致，说明打印的这个sel-imp就是LBHPerson的实例方法

machoView查看

step5: 点击step over，程序再执行一步，此时-[LBHPerson instanceMethod2]已经执行，我们再看下此时cache的情况

获取到的buckets同step4中是同一个，如何获取对应的sel和imp?

指针偏移

同样通过数组下标也是可以的。

为了更好的研究，我们脱离源码环境在项目中探索

脱离源码

typedef uint32_t mask_t;  // x86_64 & arm64 asm are less efficient with 16-bits

struct lg_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct lg_cache_t {
    struct lg_bucket_t * _buckets;
    mask_t _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct lg_class_data_bits_t {
    uintptr_t bits;
};

struct lg_objc_class {
    Class ISA;
    Class superclass;
    struct lg_cache_t cache;             // formerly cache pointer and vtable
    struct lg_class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
};

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        
        LBHPerson *person = [LBHPerson alloc];
        Class pClass = [LBHPerson class];
        
        
        [person instanceMethod1];
        [person instanceMethod2];
        [person instanceMethod3];
        [person instanceMethod4];
        [person instanceMethod5];
        
        
        struct lg_objc_class *lg_pClass = (__bridge struct lg_objc_class *)(pClass);
        NSLog(@"%hu - %u",lg_pClass->cache._occupied,lg_pClass->cache._mask);
        for (mask_t i = 0; i<lg_pClass->cache._mask; i++) {
            // 打印获取的 bucket
            struct lg_bucket_t bucket = lg_pClass->cache._buckets[i];
            NSLog(@"%@ - %p",NSStringFromSelector(bucket._sel),bucket._imp);
        }

    }
    return 0;
}

看下输出结果:

针对上面的打印结果，有以下几点疑问：

1、_mask是什么？
2、_occupied 是什么？
3、occupied 和 mask随什么变化？
4、bucket数据为什么会有丢失的情况？
5、方法打印顺序不是调用顺序？

带着这些疑问我们对cache_t底层进行进一步的探索

cache_t底层深入探索

step1: 进入cache_t结构体，从cache_t的_occupied属性开始分析

2.1: 看一下incrementOccupied()的实现

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

step2: 在源码中全局搜索incrementOccupied()函数，发现只在cache_t的insert方法有调用

• insert方法，理解为cache_t的插入，而cache中存储的就是sel-imp，所以cache的原理从insert方法开始分析，以下是cache原理分析的流程图：

step3: 全局搜索insert(方法，发现只有cache_fill方法中的调用符合

step4: 全局搜索cache_fill，发现在写入之前，还有一步操作，即cache读取，即查找sel-imp，如下所示

可以看到在cache写入流程前有一个读取流程，我们在下一篇文章讲解读取流程，本文还是回到insert写入上

查看insert源码

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

重点分析

这个函数主要分为三部分

* 【第一步】计算出当前的缓存占用量
* 【第二步】根据缓存占用量判断执行的操作
* 【第三步】针对需要存储的bucket进行内部imp和sel赋值

【第一步】根据occupied的值计算出当前的缓存占用量，当属性未赋值及无方法调用时，此时的occupied()为0，而newOccupied为1，如下所示

mask_t newOccupied = occupied() + 1;

//occupied() 
mask_t cache_t::occupied() 
{
    return _occupied;
}

关于缓存占用量的计算，有以下几点说明：

• 当对象已经通过alloc方法创建，再调用init方法，occupied会+1
• 当有属性赋值时，会隐式调用set方法，occupied也会增加，即有几个属性赋值，occupied就会在原有的基础上加几个
• 当有方法调用时，occupied也会增加，即有几次调用，occupied就会在原有的基础上加几个

capacity()方法

//当前mask有值就+1，否则设置初始值0
unsigned cache_t::capacity()
{
    return mask() ? mask()+1 : 0; 
}

【第二步】根据缓存占用量判断执行的操作

* 【if】如果是第一次创建，则默认开辟4个

if (slowpath(isConstantEmptyCache())) { //小概率发生的 即当 occupied() = 0时，即创建缓存，创建属于小概率事件
  // Cache is read-only. Replace it.
  if (!capacity) capacity = INIT_CACHE_SIZE; //初始化时，capacity = 4（1<<2 -- 100）
  reallocate(oldCapacity, capacity, /* freeOld */false); //开辟空间
  //到目前为止，if的流程的操作都是初始化创建
}

* 【else if】 如果缓存占用量<=3/4，则不作任何处理

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

* 【else】 如果缓存占用量>3/4，则需要进行两倍扩容以及重新开辟空间

else {//如果超出了3/4，则需要扩容（两倍扩容）
    //扩容算法： 有cap时，扩容两倍，没有cap就初始化为4
    capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 扩容两倍 2*4 = 8
    if (capacity > MAX_CACHE_SIZE) {
        capacity = MAX_CACHE_SIZE;
    }
    // 走到这里表示 曾经有，但是已经满了，需要重新梳理
    reallocate(oldCapacity, capacity, true);
    // 内存 扩容完毕
}

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

• reallocate----> allocateBuckets方法：向系统申请开辟内存，即开辟bucket，此时的bucket只是一个临时变量

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

• reallocate---->setBucketsAndMask方法：将临时的bucket存入缓存中，此时的存储分为两种情况：

  • 如果是真机，根据bucket和mask的位置存储，并将occupied占用设置为0
    

    

  • 如果不是真机，正常存储bucket和mask，并将occupied占用设置为0

  

• reallocate---->cache_collect_free方法：如果有旧的buckets，需要清理之前的缓存，即调用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);
}

该方法的实现主要有以下几步：

• _garbage_make_room方法：创建垃圾回收空间

如果是第一次，需要分配回收空间，如果不是第一次，则将内存段加大，即原有内存*2

【第三步】针对需要存储的bucket进行内部imp和sel赋值

这部分主要是根据cache_hash方法，即哈希算法 ，计算sel-imp存储的哈希下标，分为以下三种情况：

1、如果哈希下标的位置未存储sel，即该下标位置获取sel等于0，此时将sel-imp存储进去，并将occupied占用大小加1

2、如果当前哈希下标的位置存储的sel 等于 即将插入的sel，则直接返回

3、如果当前哈希下标的位置存储的sel 不等于 即将插入的sel，则重新经过cache_next方法 即哈希冲突算法，重新进行哈希计算，得到新的下标，再去对比进行存储

其中涉及的两种哈希算法，其源码如下:

• cache_hash：哈希算法

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask; // 通过sel & mask（mask = cap -1）
}

• cache_next：哈希冲突算法

#if __arm__  ||  __x86_64__  ||  __i386__
// objc_msgSend has few registers available.
// Cache scan increments and wraps at special end-marking bucket.
#define CACHE_END_MARKER 1
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask; //（将当前的哈希下标 +1） & mask，重新进行哈希计算，得到一个新的下标
}

#elif __arm64__
// objc_msgSend has lots of registers available.
// Cache scan decrements. No end marker needed.
#define CACHE_END_MARKER 0
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask; //如果i是空，则为mask，mask = cap -1，如果不为空，则 i-1，向前插入sel-imp
}

疑问解答

1、 _mask是什么？

_mask是指掩码数据，用于在哈希算法或者哈希冲突算法中计算哈希下标，其中mask 等于capacity - 1。

2、_occupied 是什么？

_occupied表示哈希表中 sel-imp 的占用大小 (即可以理解为分配的内存中已经存储了sel-imp的的个数)，

3、occupied 和 mask随什么变化？

因为在cache初始化时，分配的空间是4个，随着方法调用的增多，当存储的sel-imp个数，即newOccupied + CACHE_END_MARKER（等于1）的和 超过 总容量的3/4，例如有4个时，当occupied等于2时，就需要对cache的内存进行两倍扩容。

4、bucket数据为什么会有丢失的情况？

原因是在扩容时，是将原有的内存全部清除了，再重新申请了内存导致的

5、方法打印顺序不是调用顺序？

因为sel-imp的存储是通过哈希算法计算下标的，其计算的下标有可能已经存储了sel，所以又需要通过哈希冲突算法重新计算哈希下标，所以导致下标是随机的，并不是固定的。