objc_class中的cache_t分析

本文探索的的主要是两点

1、cache_t的结构

2、cache_t里存储的哪些

cache_t结构分析

打开源码，点进cache_t中查看cache_t的底层代码

便于分析，暂时剔除去里面的static等静态变量

#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;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
    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;

public:
//省略方法

首先搞清楚这里的用来做判断条件的宏是什么意思

#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
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_OUTLINED//模拟器或者macOS
#endif

以上代码大致可以cache_t所包含的内容:
非真机端：_buckets 、_mask 、flags 、_occupied
真机端：_maskAndBuckets 、flags 、_occupied
注：真机端时，_maskAndBuckets ，编译器为了优化，将_buckets 、_mask 合并

-再看下_buckets包含哪些

struct bucket_t {
private:
#if __arm64__
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif

_buckets包含了_imp和_sel,真机和非真机只是imp和sel的顺序不一样
至此我们可以得出cache_t内包含的的就是_buckets 、_mask 、flags 、_occupied

下面我们分析cache-t是怎么缓存imp-sel以及 flags和_occupied的含义

cache_t流程分析

1、源码环境下分析

在person类里创建多个方法

@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 {
        // insert code here...
        LGPerson *p  = [LGPerson alloc];
        Class pClass = [LGPerson class];
        [p sayHello];
        [p sayCode];
        [p sayMaster];

在[p sayHello]处打断点，打印结果如下

执行到sayHello时

往下走，执行完[p sayHello]后，发现

执行完sayHello

我们发现_occupied 值发生变化，由0->1了，可以得出，_occupied是占用位置的意义,并且我门发现imp也有值了,

我们来看一下，sel-IMP内容
我们知道sel-imp存在于bucket里，那我们就在bucket里找获取 sel-imp的函数

读取bucket

到bucket里

image.png

下面我们获取sel和imp

image.png

buckets是一个数组，上面操作实际的获取的buckets中的第一个元素，我们继续往下走，看是否是打印出第二个的方法

image.png

可以看出，cahe_t中存储了运行完的方法

下面我们继续走完所有的方法

首先看下cache_t的情况

image.png

mask、occpupied都发生了变化，

再打印看下imp、sel的情况

image.png

只存储了最后一个方法

现在我们再添加一些方法，试试添加属性。看是否被存储

image.png

数组中只有1、2、3有值，且2、3顺序并不是代码中方法的执行顺序

至此可以得出一些奇怪的现象

1、occupied和mask在变化，且既不是递增也不是递减的变化，是按照什么规则变化？mask代表什么？
2、sel和imp丢失了，为什么？
3、方法的存储顺序和执行顺序不一致

下面我们就着重分析这三个疑问，为了便于打印，我们可以将源码的数据类型复制进.m文件中

2、脱离源码环境下分析

注意点:

只要保留好底层结构、剔除无用的代码
1、需要类。所有OC类都是以底层objc_class为模板创建的，所以我们可以直接将任何类强转为wl_objc_class。在进行结构读取,因为没有继承来的objc_class,所以结构中要加上ISA
2、需要cache_t，进去cache_t源码里精炼出结构，其中 explicit_atomic(原子性，用于多线程操作时，数据的安全优化)可以去除
3、需要buckets，包含imp和sel
4、需要mask，进去查看，mask本质是uint32_t
最终提炼出最终的需要的类型结构

truct wl_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct wl_cache_t {
    struct wl_bucket_t * _buckets;
    mask_t _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct wl_class_data_bits_t {
    uintptr_t bits;
};

struct wl_objc_class {
    Class ISA;
    Class superclass;
    struct wl_cache_t cache;             // formerly cache pointer and vtable
    struct wl_class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
};

加入到代码中使用

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

struct wl_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct wl_cache_t {
    struct wl_bucket_t * _buckets;
    mask_t _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct wl_class_data_bits_t {
    uintptr_t bits;
};

struct wl_objc_class {
    Class ISA;
    Class superclass;
    struct wl_cache_t cache;             // formerly cache pointer and vtable
    struct wl_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];  // objc_clas
        [p say1];
        [p say2];
        [p say3];
        [p say4];
        struct wl_objc_class *wl_pClass = (__bridge struct wl_objc_class *)(pClass);
        NSLog(@"%hu - %u",wl_pClass->cache._occupied,wl_pClass->cache._mask);
        for (mask_t i = 0; i<wl_pClass->cache._mask; i++) {
            // 打印获取的 bucket
            struct wl_bucket_t bucket = wl_pClass->cache._buckets[i];
            NSLog(@"%@ - %p",NSStringFromSelector(bucket._sel),bucket._imp);
        }

        
        NSLog(@"Hello, World!");

打印显示

image.png

以上，可以更清晰感受出occupied和mask的意义、sel-imp打印顺序和调用顺序不匹配的问题以及相关bucket丢失的问题

1、occupied：当前在缓存中的方法占有空间
2、mask：整个缓存所拥有总空间
3、丢失了一些缓存的方法以及方法插入的位置不是原顺序

下面我们带着这些疑问像cachet原理探索

cache_t原理分析

步骤：
一、寻找影响occupied 和mask值的函数
二、缓存空间是如何分配的

步骤一：

在cachet里，我们发现有以下关于occupied函数

image.png

字面意思是occupied的增加方法，查看该函数的实现

void cache_t::incrementOccupied() //occupied自增
{
    _occupied++;
}

继续在源码中搜索在哪里调用此函数

image.png

insert方法调用了occupied自增函数,insert可以理解为缓存的插入，即 sel-imp插入缓存的函数

下面即insert全局搜索

image.png

发现关于cache中的insert函数在cache_fill中也被调用

全局搜索cache_fill

image.png

发现在插入cache前，先读取了cache，即先sel-imp从缓存中读取，然后再将sel-imp写入缓存中。
这个在下面章节(消息发送）中探索，先查看插入函数是怎么操作的

回到insert函数里

image.png

以上分为三个步骤
【一】计算occupied:即当前所占缓存大小，当没有调用属性set方法时或者init方法时，occupied为0,那么newOccupied=1

mask_t newOccupied = occupied() + 1;

【二】计算缓存所要使用的总空间:
注：其中每一个判读里都有一个reallocate函数
查看得知是一个释放旧空间，获取新空间的实现函数

image.png

分析具体分配空间的操作

首先,如果是第一次创建，空间初始值为4

//oldCapacity 和 capacity的初始值都为0
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        //初始空间为0时,capacity = INIT_CACHE_SIZE = 1 << 2 = 4
        if (!capacity) capacity = INIT_CACHE_SIZE;
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }

如果缓存空间<= 3/4时,缓存还是4个不变。如:初始时，newOccupied为1，所开辟总空间还是为4

//初始时：1+1 <= 3
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) {
        // Cache is less than 3/4 full. Use it as-is.
    }

如果缓存大小 > 3/4时，如:newOccupied为3，所开辟总空间为4*2 = 8

else {
        //如果计数大于3/4， 就需要进行扩容操作
        // 如果空间存在，就2倍扩容。 如果不存在，就设为初始值4
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        //最大扩容空间为1<<16 = 2^15
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        //释放旧空间，创建新缓存空间（第三个入参为true，表示需要释放旧空间）
        reallocate(oldCapacity, capacity, true);
    }

【三】将sel-imp写进缓存

image.png

首先用cache_hash哈希算法设置方法首次要插入的位置

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

判断要插入的位置是否已被占用，如果被占用，即使用哈希冲突算法cache_next重新计算位置

#if __arm__  ||  __x86_64__  ||  __i386__
#define CACHE_END_MARKER 1
static inline mask_t cache_next(mask_t i, mask_t mask) {
    //非真机以及老的arm真机环境下，向后走一位。将当前的下标 +1 & mask，重新进行哈希计算，得到一个新的下标
    return (i+1) & mask;
}

#elif __arm64__
#define CACHE_END_MARKER 0
static inline mask_t cache_next(mask_t i, mask_t mask) {
    //如果i是空，则为mask，mask = cap -1，如果不为空，则 i-1，向前插入sel-imp
    return i ? i-1 : mask;
}

即有三种情况

如果哈希下标的位置未存储sel，即该下标位置获取sel等于0，此时将sel存储进去
当前哈希下标存储的sel 等于即将插入的sel，说明已经存储进去了，直接返回
如果当前哈希下标存储的sel 不等于即将插入的sel，则经过哈希冲突算法，重新进行计算，得到新的下标，再去对比进行存储

至此，cache_t原理分析完毕，针对于以上的疑问，我们可以得出答案了

1、 mask是掩码，大小=缓存方法所开辟的总空间大小 - 1，作用是用来和需插入到缓存的sel进行&操作，得出sel下标
2、 occupied表示哈希表中 sel-imp 的占用大小 (即可以理解为分配的内存中已经存储了sel-imp的的个数)，其中init、属性赋值、方法调用都会增加occupied的大小
3、随着方法的调用，mask的大小比实际需要大小要大，是因为，当目前使用使用的大小+1 > 3/4*总大小时，空间会扩容到目前的2倍，假如如目前是2个方法调用，因为初始空间capacity是4，occupied = 2，那么newOccupied = 2+1 = 3，newOccupied + CACHE_END_MARKER >= capacity / 4 * 3（其中CACHE_END_MARKER = 1),此时capacity就会扩容到8，所以我们只调用了2个方法时。打印出来的mask已经为7了
4、方法存储顺序和调用顺序不一致：是因为可能目前空间已经>3/4了，需要释放了旧的空间，重新分配了空间。方法的下标使用哈希算法计算得出的，可能之前的下标已经被其他方法占用，产生了冲突，利用哈希冲突算法重新计算下标，存储方法，所以顺序是随机的。
5、丢失了一些方法：扩容时，是将原有的内存全部清除了，再重新申请了内存导致的

最后，我们可以得出整个cache_t操作流程
后补