OC底层原理13：cache_t底层原理分析

前言

我们在前面的 OC底层原理10：类 & 类结构分析 中
得知 类 都是以 objc_class 模板创建的，而 objc_class 中包含许多属性，如 Class ISA、Class superclass、cache_t cache、class_data_bits_t bits，并分析了 ISA、superclass、bits，本文主要分析 cache_t 中的 cache 属性。

cache_t 结构分析

通过 objc4-781源码 ，查看 cache_t 的源码结构如下：

// cache 存的是什么？ 怎么存的？
// cache 用来缓存
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;
    // _mask 掩码，即面具 -- 类似于isa的掩码，即位域
    explicit_atomic<mask_t> _mask;
    
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 // 真机 & 64位
    // _maskAndBuckets 把原来的两个结构 _buckets 和 _mask 写成一个了，作用 为了优化
    explicit_atomic<uintptr_t> _maskAndBuckets;
    // 苹果没有写完
    mask_t _mask_unused;
    
    // 静态的省略...
        
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4 // 真机 不是64位的
    
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;

    // 静态的省略...
    
#else
#error Unknown cache mask storage type.
#endif
    
#if __LP64__
    // 位置标记
    uint16_t _flags;
#endif
    // 占位
    uint16_t _occupied;

    //其他方法省略.....

分析 cache_t 的结构：

• 首先我们需要了解一下苹果设备的不同的 架构，如下：

  • MacOS 架构：i386
  • 真机 架构：arm64
  • 模拟器 架构：x86

• 通过上面的 cache_t 源码可知，分为 3 个架构处理：

  • CACHE_MASK_STORAGE_OUTLINED：表示运行的环境是 MacOS 或者 模拟器
  • CACHE_MASK_STORAGE_HIGH_16：表示运行的环境是 64位 的 真机
  • CACHE_MASK_STORAGE_LOW_4：表示运行的环境是 非64位 的 真机

我们可以点进 CACHE_MASK_STORAGE 中查看具体的定义：

#define CACHE_MASK_STORAGE_OUTLINED 1 
#define CACHE_MASK_STORAGE_HIGH_16 2
#define CACHE_MASK_STORAGE_LOW_4 3

#if defined(__arm64__) && __LP64__ // 真机 & 64位
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16
#elif defined(__arm64__) && !__LP64__ // 真机 & 非64位
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_LOW_4
#else // MacOS 或 模拟器
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_OUTLINED
#endif

• explicit_atomic：表示 显示原子性，目的是为了能够保证 增删改查时 线程的安全性

• _buckets：是一个 struct bucket_t 的结构体，其内部源码如下：

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__ // 真机 64位
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else // 非真机
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif

由 bucket_t 源码可知，其内部保存的是 SEL 和 IMP

• _mask：是 masK_t 结构，掩码，即面具，类似于 isa中的掩码即 位域

  • 真机 环境： uint32_t 类型的
  • 其他 环境：uint16_t 类型的

masK_t 的内部结构如下：

#if __LP64__
typedef uint32_t mask_t;  // x86_64 & arm64 asm are less efficient with 16-bits
#else
typedef uint16_t mask_t;
#endif

• _maskAndBuckets： 真机 环境把原来的两个结构 _buckets 和 _mask 写成一个了，作用是 为了优化

【总结】

通过上面几个结构体分析，我们可以得出一个如下的结构图：

【补充知识】sel & imp 的关系

我们知道，每一个方法都有一个 sel 和 imp，sel 就是 方法编号，imp 就是 函数指针(方法实现)，我们在查找方法的时候是一个非常漫长的过程，oc 的 函数实现 是通过 下层c/c++ 来实现的，oc上层 的 sel 和 imp 起始是 对下层 的 封装

【方法的组成】:

• SEL：方法编号
• IMP：函数指针地址

【用通俗易懂的方式解释】：

SEL：相当于书本目录的名称
IMP：相当于书本目录的页码

• 首先明白我们要找到书本的什么内容（sel目录里面的名称）
• 通过名称找到对应的书本页码（imp）
• 通过页码去定位具体的内容

下面用一张图表示：

cache中查找sel-imp

cache_t 中查找存储的 sel-imp，有以下两种方式

• 通过源码查找
• 脱离源码在项目中查找

【准备工作】

• 自定义一个 ZJPerson 类，并定义 2个属性 和 5个实例方法 及其 实现

ZJPerson.h 中

@interface ZJPerson : NSObject
@property (nonatomic, copy) NSString *zjName;
@property (nonatomic, strong) NSString *nickName;

- (void)sayHello;

- (void)sayCode;

- (void)sayMaster;

- (void)sayNB;

+ (void)sayHappy;

@end

ZJPerson.m 中

@implementation ZJPerson
- (void)sayHello{
    NSLog(@"ZJPerson say : %s",__func__);
}

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

- (void)sayMaster{
    NSLog(@"ZJPerson say : %s",__func__);
}

- (void)sayNB{
    NSLog(@"ZJPerson say : %s",__func__);
}

+ (void)sayHappy{
    NSLog(@"ZJPerson say : %s",__func__);
}
@end

• 在 main.m 中定义 ZJPerson 类的 对象p，并调用其中的 3个实例方法，在第一个方法处加两个 断点

【通过源码查找】

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

由上面的调式流程可知：

• cache属性 的获取，需要通过 pClass 的 首地址平移16字节，即 首地址 + 0x10 获取 cache的地址

• _buckets属性 的获取，在 cache_t 结构体中提供了获取 _buckets 属性的方法 buckets()，在 _buckets 属性中（目前处于macOS环境）缓存着 sel-imp

• sel 和 imp 的获取，在 _buckets 中提供了 sel() 和 imp(pClass) 方法获取 sel 和 imp

由上图可知，在没有执行方法调用之前，此时 cache 是没有缓存的，执行调用了一次之后，cache 中就 缓存 了 一次，即调用一次方法就会缓存一次。

我们在前面了解了如何获取 cache 中 sel-imp，那么如何验证打印的sel-imp 就是我们调用的呢？可以通过 machoView 打开 target 的可执行文件，在方法列表中查看其 imp 的值 是否是一致 的，如下所示，发现是一致的，所以打印的这个 sel-imp 就是 ZJPerson 的实例方法：

【machoView图】：

【imp截图：】

• 接着上面的 LLDB 调试步骤，我们再调一个方法，其 LLDB 调试如下图：

第一个调用方法的存储获取很简单，直接通过 _buckets 的 首地址 调用对应的方法即可，那么获取第二个呢？在之前的 OC底层原理10：类 & 类结构分析 文章中，曾提及过一个概念 指针偏移，所以我们这里可以通过 _buckets 属性的 首地址偏移，即 p *($9+1) 即可获取第二个方法的 sel 和 imp

如果有多个方法需要获取，以此类推，例如 p *($9+i)

【脱离源码通过项目查找】

脱离源码环境，就是将所需的 源码 的部分 拷贝至项目 中，其完整代码如下：

【ZJPerson类】

//*********.h********
@interface ZJPerson : NSObject
@property (nonatomic, copy) NSString *zjName;
@property (nonatomic, strong) NSString *nickName;
- (void)say1;
- (void)say2;
- (void)say3;
- (void)say4;
- (void)say5;
- (void)say6;
- (void)say7;
+ (void)sayHappy;
@end

//*********.m********
@implementation ZJPerson
- (void)say1{
    NSLog(@"ZJPerson say : %s",__func__);
}
- (void)say2{
    NSLog(@"ZJPerson say : %s",__func__);
}
- (void)say3{
    NSLog(@"ZJPerson say : %s",__func__);
}
- (void)say4{
    NSLog(@"ZJPerson say : %s",__func__);
}
- (void)say5{
    NSLog(@"ZJPerson say : %s",__func__);
}
- (void)say6{
    NSLog(@"ZJPerson say : %s",__func__);
}
- (void)say7{
    NSLog(@"ZJPerson say : %s",__func__);
}
+ (void)sayHappy{
    NSLog(@"ZJPerson say : %s",__func__);
}
@end

【main中代码】

#import <Foundation/Foundation.h>
#import "ZJPerson.h"
#import <objc/runtime.h>

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

struct zj_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct zj_cache_t {
    struct zj_bucket_t * _buckets;
    mask_t _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct zj_class_data_bits_t {
    uintptr_t bits;
};

struct zj_objc_class {
    Class ISA;
    Class superclass;
    struct zj_cache_t cache;             // formerly cache pointer and vtable
    struct zj_class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
};


int main(int argc, const char * argv[]) {
    @autoreleasepool {
        ZJPerson *p  = [ZJPerson alloc];
        Class pClass = [ZJPerson class];  // objc_clas
        [p say1];
        [p say2];
        [p say3];
        [p say4];
         
        // _occupied  _mask 是什么  cup - 1
        // 会变化 2-3 -> 2-7
        // bucket 会有丢失  重新申请
        // 顺序有点问题  哈希
        
        // cache_t 底层原理
        // 线索 :
        
        struct zj_objc_class *zj_pClass = (__bridge struct zj_objc_class *)(pClass);
        NSLog(@"%hu - %u",zj_pClass->cache._occupied,zj_pClass->cache._mask);
        for (mask_t i = 0; i<zj_pClass->cache._mask; i++) {
            // 打印获取的 bucket
            struct zj_bucket_t bucket = zj_pClass->cache._buckets[i];
            NSLog(@"%@ - %p",NSStringFromSelector(bucket._sel),bucket._imp);
        }

        
        NSLog(@"Hello, World!");
    }
    return 0;
}

• 这里有个问题需要注意，在源码中，objc_class 的 ISA 属性时继承自 objc_object 的，但在我们将其拷贝过来时，去掉了 objc_class 的继承关系，需要将这个属性明确，否则打印的结果是有问题的，如下图所示：

• 加上 ISA 属性后，其正确的打印结果如下：

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

• _mask 是什么？
• _occupied 是什么？
• 为什么随着方法调用的增多，其打印的 occupied 和 mask 会变化？
• bucket 数据为什么会有 丢失的情况？例如 2-7中，只有say3、say4方法有函数指针？
• 2-7中say3、say4的打印顺序为什么是say4先打印，say3后打印，且还不是挨着的，即 顺序有问题？
• 打印的 cache_t 中的 _occupied 为什么是从 2 开始？

带着上述的这些疑问，下面来进行 cache 底层原理的探索

cache_t 底层原理分析

• 首先，从 cache_t 中的 _mask 属性开始分析，找 cache_t 中引起变化的函数，发现了 incrementOccupied() 函数

该函数的具体实现为

void incrementOccupied(); //Occupied自增

//👇具体实现
void cache_t::incrementOccupied() 
{
    _occupied++;
}

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

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

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

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

但本文的重点还是分析 cache 存储的原理，接下来根据 cache_t 写入的流程图，着重分析 insert 方法

insert 方法分析

在 insert 方法中，其源码实现如下

主要分为以下几部分：

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

1、【第一步】计算出当前的缓存占用量

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

mask_t newOccupied = occupied() + 1;

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

• alloc 申请空间时，此时的 对象已经创建，如果再调用 init 方法，occupied也会+1

• 当 有属性赋值 时，会隐式调用 set 方法，occupied 也会增加，即 有几个属性赋值，occupied就会在原有的基础上加几个

• 当 有方法调用 时，occupied 也会增加，即 有几次调用，occupied就会在原有的基础上加几个

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

• 如果是 第一次创建，则默认开辟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的流程的操作都是初始化创建
}

• 如果缓存占用量 小于等于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 { //如果超出了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);
    // 内存 扩容完毕
}

【realloc方法：开辟空间】

该方法，在 第一次创建 以及 两倍扩容 时，都会使用，其源码实现如图所示

主要有以下几步：

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

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

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

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

• 如果有旧的buckets，需要清理之前的缓存，即调用 cache_collect_free 方法，其源码实现如下

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

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

• 如果是 第一次，需要 分配回收空间

• 如果 不是第一次，则将内存段加大，即 原有内存*2

• 记录 存储 这次的 bucket

• cache_collect 方法：垃圾回收，清理旧的bucket

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

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

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

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

• 如果当前哈希下标存储的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
}

到此，cache_t的原理基本分析完成了，然后前文提及的几个问题，我们现在就有答案了

疑问解答

1、_mask 是什么？

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

2、_occupied 是什么？

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

• init 会导致occupied变化

• 属性赋值，也会隐式调用，导致occupied变化

• 方法调用，导致occupied变化

3、为什么随着方法调用的增多，其打印的 occupied 和 mask 会变化？

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

4、bucket 数据为什么会有 丢失的情况？例如 2-7中，只有say3、say4方法有函数指针？

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

5、2-7中say3、say4的打印顺序为什么是say4先打印，say3后打印，且还不是挨着的，即 顺序有问题？

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

6、打印的 cache_t 中的 _occupied 为什么是从 2 开始？

这里是因为 ZJPerson 通过alloc创建的对象，并 对其两个属性赋值的原因，属性赋值，会隐式调用set方法，set方法 的调用也会导致 occupied变化