前两篇文章，探索了类的结构，分析了类中几个重要的属性，isa、superclass、cache_t、bits，并研究了ro、rw、rwe的关系。这篇文章来深入探索cache_t的结构和底层原理。

一.cache_t结构分析

在Objective_C层，一切类均继承自NSObject。对应到底层，类（objc_class）继承自objc_object。查看源码objc_runtime_new.h，结构体objc_class的内部结构。见下图：

其中isa来自父类objc_object，占8个字节；superclass占8个字节；cache占用16个字节。cache_t中存储了类的一些缓存信息。cache_t结构体的部分源码见下图：

1. cache_t结构体大小

解读cache_t源码，其提供了两个属性，_bucketsAndMaybeMask和一个联合体，其中_bucketsAndMaybeMask为uintptr_t泛型，占8个字节，是一个指针地址。联合体中包含一个结构体和一个指针，联合体也占用8个字节，cache_t一共占用16字节的内存空间。

2. _bucketsAndMaybeMask

_bucketsAndMaybeMask是一个哈希表的地址，该哈希表存储了当前缓存的方法编号和方法实现，即bucket_t。针对arm64真机环境，mask和buckets进行了掩码运算，将mask和buckets放在了一起，优化减少了占用空间，_bucketsAndMaybeMask占用8个字节，共64位。其中前16位存储mask，后48位存储buckets。bucket_t结构见下图：

bucket_t中存储了类对象的方法编号_sel，及其指向方法实现的地址指针_imp。同样对环境进行了区分，不同的区别在于sel和imp的顺序不一致。

3. 架构区分

针对不同的系统架构提供了不同的解决方案。机型区分如下图：

针对不同架构，配置参数的设置区分：

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    // _bucketsAndMaybeMask is a buckets_t pointer
    // _maybeMask is the buckets mask

    static constexpr uintptr_t bucketsMask = ~0ul;
    static_assert(!CONFIG_USE_PREOPT_CACHES, "preoptimized caches not supported");
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
    static constexpr uintptr_t maskShift = 48;
    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << maskShift) - 1;
    
    static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers.");
#if CONFIG_USE_PREOPT_CACHES
    static constexpr uintptr_t preoptBucketsMarker = 1ul;
    static constexpr uintptr_t preoptBucketsMask = bucketsMask & ~preoptBucketsMarker;
#endif
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    // _bucketsAndMaybeMask is a buckets_t pointer in the low 48 bits
    // _maybeMask is unused, the mask is stored in the top 16 bits.

    // How much the mask is shifted by.
    static constexpr uintptr_t maskShift = 48;

    // Additional bits after the mask which must be zero. msgSend
    // takes advantage of these additional bits to construct the value
    // `mask << 4` from `_maskAndBuckets` in a single instruction.
    static constexpr uintptr_t maskZeroBits = 4;

    // The largest mask value we can store.
    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
    
    // The mask applied to `_maskAndBuckets` to retrieve the buckets pointer.
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
    
    // Ensure we have enough bits for the buckets pointer.
    static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS,
            "Bucket field doesn't have enough bits for arbitrary pointers.");
复制代码

二.lldb探索cache_t

定义一个类LGHuman，调用了四个对象方法，设置三个断点，分别在这三个断点处查看cache_t的变化情况。(此种方式操作较麻烦，但是相对比较容易理解)见下面代码：

1.三断点调试

运行程序，在断点处，分别分析cache_t的数据存储情况。

断点1——方法sayHello1()和sayHello2()还没有执行，此时查看cache_t的存储情况。获取cache_t数据后，打印数据内容，此时mask=0，occupied=0。见下图：

断点2——继续执行代码，到达断点2处，方法sayHello1()和sayHello2()已被执行，查看此时cache_t的存储情况mask=3，occupied=2。见下图：

在执行两个方法后，通过调用buckets()方法，获取bucket列表，$4即为buckets列表的首地址，第一个元素存储着方法sayHello2。根据首地址偏移，下标+1，获取的bucket，得到sayHello1。见下图：

通过这个输出结构，发现bucket列表是无序的！

断点3——继续执行代码，到达断点3处，方法sayHello3()和sayHello4()已被执行，查看此时cache_t的存储情况，mask=7，occupied=2。见下图：

在断点3处，继续打印buckets中的bucket。根据首地址偏移，最终找到了sayHello3和sayHello4，但是无法获取sayHello1和sayHello2，
这个结果和设想的完全不一样！。见下图：

2.问题思考

_mask是什么？_occupied是什么？
随着方法的执行，_occupied和_mask的变化为0-0 -> 2-3 -> 2-7，为什么？
buckets中的数据丢失，无法找到sayHello1和sayHello2？为什么数据存储是不连续的？

三.底层探索

1.探究思路

思路：决定一个类功能的是函数，所以从cache_t的函数中去寻找突破口。

cache_t结构体中，有一个方法void incrementOccupied();，增加占用，内部实现为：_occupied++;，很容易理解：向cache_t中插入内容，占用数加1。

全局搜索incrementOccupied()方法，只有一个地方用到了该方法，向cache_t中插入数据，cache_t::insert方法。参数有：方法编号sel，方法实现地址指针imp，消息接受者。见下图：

继续全局搜索cache_t::insert方法找到了一段非常重要的注释，解读注释：cache_t分为cache读取和cache写入两个点。见下图：

通过注释可以了解，objc_msgSend和cache_getImp会进行缓存数据的读取，cache_t::insert会进行缓存数据的插入创建。

要想解决上面留下的问题，肯定要从创建插入的流程进行探索！

2.insert方法研究

cache_t::insert方法关键步骤，见下图。整体可以分为两个部分，第一步进行容器的初始化工作，第二步进行数据插入。

下面详细解读insert流程。

1.容器初始化

设置断点，确保调用sayHello1方法进入断点，lldb输出当前类cls为LGHuman，方法编号sel为sayHello1。见下图：

调用occupied()方法，lldb调试输出可发现，当前占用数为0，新的占用数newOcuupied = 1;可以理解初次插入，当前容器占用为空。所以首次进入缓存为空，会进行容器的创建！见下图：

默认初始化容量:4，即1 << INIT_CACHE_SIZE_LOG2 (1<<2)，然后调用reallocate()方法进行初始化。见下图：

在setBucketsAndMask中，会对内存空间进行开辟，同时设置当前_occupied = 0。见下面源码：

#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 || CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    uintptr_t buckets = (uintptr_t)newBuckets;
    uintptr_t mask = (uintptr_t)newMask;

    ASSERT(buckets <= bucketsMask);
    ASSERT(mask <= maxMask);

    _bucketsAndMaybeMask.store(((uintptr_t)newMask << maskShift) | (uintptr_t)newBuckets, memory_order_relaxed);
    _occupied = 0;
}
复制代码

2.数据插入

容器完成初始化后，进行首次数据插入前，occupied()占用数还为0。见下图：

初始化mask为当前容量减1，即mask = capacity - 1;，并通过cache_hash方法进行hash运算，sel & mask，获取哈希下标，即sel存储下标。hash下标算法源码：

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}
复制代码

所以这里也就解释了，为什么buckets是无序的，因为容器列表并不是一个有序存储的，方法的存储是通过hash下标存储在容器中。同时，为避免hash冲突，进行do while循环处理。如果发现hash下标已经被占用，会调用cache_next方法，重新计算hash下标再进行存储。hash下标容错算法：

#if CACHE_END_MARKER
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}
#elif __arm64__
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}
#else
#error unexpected configuration
#endif

复制代码

如果下标没有被占用，则会插入对应的方法编号和方法实现，并调用incrementOccupied();增加占用数。

3.扩容

继续执行代码，除第一次插入数据时容器为空，需要进行初始化外；其他插入数据过程中，都会对容器占用情况进行判断，当执行到第三个方法sayHello3()时，新的占用情况达到了总容量的3/4，就会走到else流程中，对容器进行扩容。见下图：

fastpath(newOccupied +CACHE_END_MARKER<= capacity /4*3，如果当前占用不超过容量的四分之三，则不需要扩容；否则进入else，对容器进行扩容。扩容算法：

// Historical fill ratio of 75% (since the new objc runtime was introduced).
static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 3 / 4;
}
复制代码

扩容方式为：当前容量的2倍。capacity = capacity ? capacity *2:INIT_CACHE_SIZE;，并且不能超出缓存的最大容量（1<<16）。最大容量：

MAX_CACHE_SIZE_LOG2  = 16,
MAX_CACHE_SIZE       = (1 << MAX_CACHE_SIZE_LOG2),
复制代码

在完成容器的容量判断和扩容后，同样会调用reallocate()方法对容器进行初始化。reallocate方法实现见下图:

因为是扩容，所以会释放之前创建的buckets。这也就解释了，为什么在执行完sayHello3()和sayHello4()后，容器中只有两个方法，找不到sayHello1()和sayHello2()的原因！因为在执行到第三个方法时，进行了扩容，销毁了老的容器，并重新创建了一个容器。