第六节课 Cache分析

在之前的文章里面，我们通过分析cache的内存大小来取得bits的地址，但是我们还不知道cache里的内部结构，这篇文章我们就来重点研究下cache

cache数据结构

06-cache.png

p/x pClass之后偏移16字节获取cache_t(之前我们说过，cache的内存地址是首地址+0x10)iOS底层原理_02:类的原理分析（上）

通过上图我们可以看到cache中的内部结构，但是想要继续了解就又得看我们的源码咯

06-cache_t.png

可以看到，cache_t中有_bucketsAndMaybeMask、_maybeMask、_flags、_occupied、_originalPreoptCache这几样东西。

_bucketsAndMaybeMask：存放数据的bit信息，类似于isa不同bit位存放的数据是什么，当前存放的是buckets和maybeMask
_maybeMask：当前的缓存区count，第一次开辟是3
_occupied：当前cache的可存储的buckets数量，默认是0
incrementOccupied():执行_occupied++，_occupied默认是0，每次有方法的插入都会被执行，本质上就是占位+1

但是具体缓存的东西呢？我继续往下看。

06-平移.png

上面这些代码，判断部分就是不同的运行环境，看到里面的代码操作就想到了isa的平移操作。

再往下，我们看到了核心部分的代码bucket_t

06-bucket_t.png

点击进入

06-sel->imp.png

我们终于看到了存储的东西了，那就是一一对应的_sel和_imp。

整体流程如下图

06-分析流程图.png

cache底层LLDB分析

我们知道了cache_t的结构后，接下来就通过LLDB来进行验证

06-buckets().png

获取是获取到了，但是都是null啊？什么情况？因为没有调用任何方法啊😂没调用哪里来的缓存，小伙伴们记得要调用方法哟~

06-buckets()2.png

还是null？这个时候就要分析一下啦~我们buckets是个复数形式哟
我们大胆猜测是通过角标来进行存储

06-下标.png

我们发现只有下标为[1]的地方跟别的下标打印的日志有点区别，我们想取东西取不出来的时候怎么办呢？去源码里找方法咯。

06-sel().png

可以看到在bucket_t源码中，有一个sel()的方法，这下就柳暗花明又一村了

直接尝试

06-saySomething.png

直接搞定✌🏻

Ps：其中的下标为什么不是从0开始的，这部分涉及到哈希链表的问题啦，后续我们再单独分析。

脱离源码分析

仿写cache底层源码

仿写思路

目标是cache，cache是在objc_class里面
参照源码仿造了struct zm_objc_class 防止与源码冲突
由于zm_objc_class内需要cache_t和class_data_bits_t，再次仿造zm_cache_t和zm_class_data_bits_t
仿造zm_cache_t过程中由于缺失mask_t类型，添加了typedef uint32_t mask_t
参照源码得知，sel与imp存在结构体bucket_t中，所以又仿造了zm_bucket_t。至此源码仿造工作完成
对HZMPerson类调用alloc方法，分配内存空间
创建自定义结构体对象pClass，struct zm_objc_class *pClass，将类赋值给自定义对象
通过cache打印当前有多少个方法缓存与最大缓存数量
通过_bucketsAndMaybeMask解析初buckets
循环遍历打印缓存的sel与imp

仿写代码

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

struct zm_bucket_t {
    SEL _sel;
    IMP _imp;
};
struct zm_cache_t {
    struct zm_bucket_t *_bukets; // 8
    mask_t    _maybeMask; // 4
    uint16_t  _flags;  // 2
    uint16_t  _occupied; // 2
};

struct zm_class_data_bits_t {
    uintptr_t bits;
};

// cache class
struct zm_objc_class {
    Class isa;
    Class superclass;
    struct zm_cache_t cache;             // formerly cache pointer and vtable
    struct zm_class_data_bits_t bits;
};


int main(int argc, const char * argv[]) {
    @autoreleasepool {
    HZMPerson *p  = [HZMPerson alloc];
    [p say1];
    [p say2];
    [p say3];
    [p say4];
    [p say5];
    [p say6];
    [p say7];
    struct zm_objc_class *zm_class = (__bridge struct zm_objc_class *)(pClass);
        NSLog(@"%hu - %u",zm_class->cache._occupied,zm_class->cache._maybeMask);
        for (mask_t i = 0; i<zm_class->cache._maybeMask; i++) {
            struct zm_bucket_t bucket = zm_class->cache._bukets[I];
            NSLog(@"%@ - %pf",NSStringFromSelector(bucket._sel),bucket._imp);
        }
        }
    return 0;
}

仿造源码调试结果：

HZMPerson say : -[HZMPerson say1]
HZMPerson say : -[HZMPerson say2]
HZMPerson say : -[HZMPerson say3]
HZMPerson say : -[HZMPerson say4]
HZMPerson say : -[HZMPerson say5]
HZMPerson say : -[HZMPerson say6]
HZMPerson say : -[HZMPerson say7]
HZMPerson say : +[HZMPerson sayHappy]
5 - 7
say4 - 0xb090f
say6 - 0xb330f
say3 - 0xb0c0f
(null) - 0x0f
say5 - 0xb360f
(null) - 0x0f
say7 - 0xb300f

打印是打印出来了，但是下半部分有点奇奇怪怪的。针对上面的打印结果，有以下几点疑问

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

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

cache底层原理分析

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

06-incrementOccupied.png

06-incrementOccupied实现代码.png

可以看到实现的部分就是一个自增的函数

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

06-incrementOccupied()调用.png

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

先全局搜索insert(方法，发现在log_and_fill_cache中调用的

06-log_and_fill_cache.png

然后再去看insert内部，其中重点代码部分为下图所示

06-insert重要三部.png

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

第一步：计算缓存占用量

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

mask_t newOccupied = occupied() + 1;

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

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

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

第一次创建，则默认开辟4个

 if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE;//初始化时，capacity = 4（1<<2 -- 100）
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }

如果缓存占用量小于等于3/4，则不作任何处理

else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) {
        // Cache is less than 3/4 or 7/8 full. Use it as-is.
    }

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

else {// 4*2 = 8
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);
    }

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

06-reallocate.png

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

setBucketsAndMask方法：将临时的bucket存入缓存中，此时的存储分为两种情况：
如果是真机，根据bucket和mask的位置存储，并将occupied占用设置为0
如果不是真机，正常存储bucket和mask，并将occupied占用设置为0

如果有旧的buckets，需要清理之前的缓存，即调用cache_collect_free方法

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

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

如果哈希下标的位置未存储sel，即该下标位置获取sel等于0，此时将sel-imp存储进去，并将occupied占用大小加1
如果当前哈希下标存储的sel 等于 即将插入的sel，则直接返回
如果当前哈希下标存储的sel 不等于 即将插入的sel，则重新经过cache_next方法即哈希冲突算法，重新进行哈希计算，得到新的下标，再去对比进行存储

cache底层流程图

06-cache流程图.png

疑问解答

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中的ocupied为什么是从 2 开始？

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

iOS底层原理_06:Cache分析