七、cache_t 分析

主要内容：cache_t的底层原理：分析cache_t缓存的内家及怎样缓存的。
一、分析cache_t主要存储的是什么，怎样查询出存储的信息
二、类的 cache_t 底层原理，怎么缓存的类方法

一、分析cache_t主要存储的是什么，怎样查询出存储的信息

前面两章已经分析了 objc_class结构体中的 isa 和 bits，接下来分析cache_t

1.分析cache_t的结构及存储信息

• cache_t的结构

//cache 支持 macOS、模拟器、真机
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;
   //苹果没有写完，搜索 setBucketsAndMask发现： error Don't know how to do setBucketsAndMask on this architecture.
    mask_t _mask_unused;
    // 代码省略......
    //省略的是掩码，即面具 -- 类似于isa的掩码，即位域
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4 // 非64位真机
    explicit_atomic<uintptr_t> _maskAndBuckets;
    //苹果没有写完，搜索 setBucketsAndMask发现： error Don't know how to do setBucketsAndMask on this architecture.
    mask_t _mask_unused;
    // 代码省略......
    //省略的是掩码，即面具 -- 类似于isa的掩码，即位域
#else
#error Unknown cache mask storage type.
#endif

• CACHE_MASK_STORAGE 说明

/*
macOS:   i386
模拟器:   x86
真机:    arm64
*/
#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

• bucket_t 的结构

struct bucket_t {
#if __arm64__    //真机
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else    // 非真机
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
//方法部分省略......

通过上面cache_t结构体可知：cache中缓存的是方法(sel 和 imp)

整体的结构图：

• 整体的结构图.png

2.查询缓存的信息

在cache_t中查找存储的方法(sel,imp) 有两种方式

• 通过源码 断点lldb查找
• 脱离源码查找

准备工作

• 定义 LGPerson 类

@interface LGPerson : NSObject
- (void)sayHello;
- (void)sayCode;
- (void)sayMaster;
- (void)sayNB;
- (void)sayHappy;
@end

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

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

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

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

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

• main 函数

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        LGPerson *p  = [LGPerson alloc];
        Class pClass = [LGPerson class];

        [p sayHello];
        [p sayCode];
        [p sayMaster];
//        [p sayNB];
//        [p sayHappy];

        NSLog(@"%@",pClass);
    }
    return 0;
}

通过源码 断点lldb查找

• 运行，加断点[p sayHello], 调试的lldb如下

• sayHello执行前后变化.png

• 接着上面的步骤，我们再次调用一个方法，我们想要获取第二个sel，其调试的lldb如下，通过 _buckets属性的首地址偏移，获得更多方法 例如：p *($10+1)

• 执行第二个方法.png

• 还有一种用数组方式读取buckets中的数据， 例：p $9.buckets()[0], p $9.buckets()[10]

• 用数组形式获得 buckets 中的数据.png

总结

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

• 从源码的分析中，我们知道sel 和 imp是在cache_t的_buckets属性中，而在cache_t结构体中提供了获取_buckets属性的方法buckets()

• 获取了_buckets属性，就可以获取sel 和 imp了，这两个的获取在bucket_t结构体中同样提供了相应的获取方法sel() 以及 imp(pClass)

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

脱离源码查找
脱离源码环境，将所需的 源码的部分拷贝到顶目中

#import "LGPerson.h"
#import <objc/runtime.h>

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 {
        LGPerson *p  = [LGPerson alloc];
        Class pClass = [LGPerson class];  
        [p sayHello];
        [p sayCode];
//        [p sayNB];
//        [p sayMaster];
//        [p sayHappy];

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

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

• 两个方法的打印结果是：

• 两个方法.png

• 增加两个方法的调用，打印结果：

• 四个方法.png

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

• 1、_mask是什么？
• 2、_occupied 是什么？
• 3、为什么随着方法调用的增多，其打印的occupied和 mask会变化？ 2-3 变为 1-7
• 4、bucket数据为什么会有丢失的情况？，例如1-7 中，只有 sayNB 和 sayMaster 方法有函数指针
• 5、2-7中sayNB 和 sayMaster 的打印顺序为什么是sayMaster先打印，sayNB后打印，即顺序有问题？

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

二、类的 cache_t 底层原理，怎么缓存的类方法

• 首先查找cache_t中引起变化的函数(因为属性是决定不了什么，只是代表保存的数据，函数决定变化)，发现了incrementOccupied()函数，该函数的具体实现是_occupied++;

• cache_t的部分方法.png

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

• insert.png

• insert方法，是cache_t的插入操作，而cache中存储的是 sel ,imp，所以cache_t原理从 insert 开始分析，cache_t的原理分析图如下

• cache_t的原理分析图.png

insert 方法分析

• 在 insert 方法主要源码：
• insert方法主要源码.png

1.计算出当前缓存占用量

// 没有属性赋值的情况下 occupied 为 0
mask_t newOccupied = occupied() + 1;

调用 init方法 、属性赋值、方法调用 时 occupied 都会增加

2.第一次进来就申请开辟空间（默认开辟4个）

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

** reallocate方法：开辟空间**

主要有以下几步：

• 1. allocateBuckets 向系统申请开辟内存，即开辟 bucket，此时的 bucket 是一个临时变量。
• 2.setBucketsAndMask 将临时的 bucket 存储缓存中，并将 当前占用设空_occupied = 0
• 3. 如果有旧 buckets， cache_collect_free 清理之前的缓存
  • _garbage_make_room() 清空之前的缓存
    1）如果第一次，需要分配回收空间
    2）如果不是第一次，将内存段加大，原有内存*2
  • garbage_refs[garbage_count++] = data; 纪录缓存这一次的 bucket
• 4.cache_collect 垃圾回收，清理旧的 bucket

3.小于等于 3/4 不做处理

 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.
        // 如果 (newOccupied + 1) <= capacity /4 * 3, 什么都不操作
    }
    

4.超过 3/4 进行两倍扩容，并开辟空间重新梳理缓存

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

5.针对需要存储的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
}
}

#else
#error unknown architecture
#endif

疑问解答:

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

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

• init 、属性赋值 、方法调用 都导致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，所以又需要通过哈希冲突算法重新计算哈希下标 ，所以导致下标是随机的，并不是固定的