前言

在对类的结构分析中，我们探索了类 class_data_bits_t bits; 成员，本篇探索一下类的另一个成员 cache_t cache;，本篇文章探索的点主要有：

cache_t 的结构分析
bucket_t 结构分析及 buckets() 存储方式分析
insert() 函数分析
- 方法缓存步骤 — cache 扩容
- 找到存储位置的过程分析 — 哈希分析

一、探索 cache_t 在底层的存储结构

1.1 cache源码结构定义分析

cache，从名字来看我们可以猜测到其作用是用于缓存，但是具体是为了缓存什么数据呢？我们依然借助源码以及LLDB调试来进行分析。首先来看一下源码中定义，从 objc_class 中找到 cache_t cache，点击进入可以查看到 cache_t 的定义，如下为 cache_t的成员 的定义：

struct cache_t {
private:
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask; // 8字节， buckets 与 mask 的合体
    union {
        struct {
            explicit_atomic<mask_t>    _maybeMask; // 4字节，存储 mask
#if __LP64__
            uint16_t                   _flags;  // 2字节，在__LP64__下才会有
#endif
            uint16_t                   _occupied; // 2字节，表示当前缓存的占用
        };
        explicit_atomic<preopt_cache_t *> _originalPreoptCache; // 8
    };
 /**
 后面还包含其他的函数，以及一些静态变量的定义和初始化
 数量较多，这里就不展示了，可以在源码中查看
 */
};
复制代码

在这部分源码定义中，我们看到的只有 buckets、maybyMask、occupied 等几个成员，关于它们的意义也只能猜测，并不能确定其真实意义及用法。遇到这种问题，我们也不用纠结，虽然从字面意义看不出来，但是关于cache_t还有很多函数，我们可以观察下其函数对成员的操作，来确定 cache_t 具体是缓存什么的。

虽然 cache_t 的函数有很多，但是从中我们还是可以找到几个关键函数，其定义如下：

    mask_t mask() const; // 获取mask，mask_t其实是一个 uint32_t 类型
    void incrementOccupied(); // _occupied自增
    
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);
    void collect_free(bucket_t *oldBuckets, mask_t oldCapacity);
    static bucket_t *emptyBuckets();
    static bucket_t *allocateBuckets(mask_t newCapacity);
    static bucket_t *emptyBucketsForCapacity(mask_t capacity, bool allocate = true);
    static struct bucket_t * endMarker(struct bucket_t *b, uint32_t cap);
复制代码

在上面的几个方法中，我们发现它们都会操作一个结构体 bucket_t，这个结构体是做什么的呢？点击进入其定义处，可以发现如下代码：

bucket_t 的成员包括 sel 和 imp，分别表示方法名称及方法实现，由此可见 cache_t 是用来缓存方法的，我们只要到其对应的bucket_t 就可以找到缓存的方法。

1.2 buckets 分析

1.2.1 LLDB获取缓存的方法

由上一节我们知道只要获取到了 bucket_t 就可以得到缓存的方法，但是 cache_t 并没有一个成员包含 bucket，我们该如何探索呢？

在探索类的底层原理时，class_rw_t 提供了 properties()、methods() 等函数，用于获取对应的属性、方法等。同样的，我们可以在 cache_t 中找到一个函数 buckets()，返回了一个bucket_t指针，其函数实现如下：

struct bucket_t *cache_t::buckets() const
{
    uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return (bucket_t *)(addr & bucketsMask);
}
复制代码

与探索类的属性一样，我们也同样采用 LLDB 调试来获取，cache_t 中缓存的方法。 cache_t cache 作为 objc_class的第三个成员，因此首地址偏移 isa 和 superclass的大小，即 16 字节即可。我们依然用 BPPerson 为例子，不过要增加几个方法用于测试，代码定义如下图所示：

我们从两种情况分别进行探索，看下不调用方法和调用方法时，cache_t 的结果分别是什么

1、不调用方法的结果如下图所示：

可以看到，在方法没有调用时，所得到的 caceh_t 的 _maybeMask 和 _occupied 均为空，即未调用过方法时 cache_t 不会缓存方法。这里也很好理解，没有方法调用过，当然也不需要缓存。

2、下面重点看下方法调用情况下，cache_t 的缓存情况。下图分别第一次为只调用 task1 和同时调用 task1 和 task2 的情况：

对比两个结果，我们发现 _occupied 的值由 1 变为 2，正好对应方法调用个数由 1 变为 2，而 _maybeMask 的结果一直为 3。我们可以猜测 _occupied 存储已经缓存的方法的个数，_maybeMask 存储的值总容量，即可以缓存的方法的个数，这一点会在稍后的探索中逐步验证。

下面接着图二的结果，验证下如何通过LLDB获取到缓存的方法，步骤及结果如下图：

首先使用 $2(cache_t类型) 调用 buckets() 函数，得到一个 bucket_t * 指针，这里 buckets() 获取到的数据是一个列表，因此需要根据下标去取值。图中 a 和 c 分别取下标 0 和 2 的值，得到了 task2 和 task1，对应调用的两个方法，而下标为 1 处则没有结果。

由此通过LLDB的调试得到了cache中缓存的方法。也证明了调用的方法会缓存到 cache_t 中，而 cache_t 会将不同的方法的 sel 和 imp 存入对应的 bucket_t 中。

1.2.2 buckets 存储方式分析

通过LLDB得到了缓存的方法，但是 buckets 到底是采用什么数据结构存储的呢？数组？还是链表？或者什么其他的数据结构呢，本小节我们就来分析下。

首先我们简介一下数组和链表这两种结构的存储特性：

数组
- 数组在内存中是一片连续的内存空间，在数组创建时就开辟了固定大小的空间，元素间紧密相连
- 数组的特点是查询方便，可以通过下标直接获取，但是在进行插入或删除操作时需要移动的元素个数较多，因而效率不高

链表（这里指单链表）
- 链表的内存空间不连续，每个元素即为一个节点，当前节点保存指向下一节点的地址
- 链表的特点是插入或删除方便，只需要改变节点指向即可，但是在查询时，不能根据下标直接找到对应节点，只能从首节点向后查找，因而查询效率较低

对比这两种数据结构我们发现：

1、buckets() 可以按照下标取值，即内存空间是连续的，所以可以排除链表的结构。

2、buckets() 虽然内存连续，但是其元素间的存储并不连续，在下标1处并未存值，而是直接在下标2处存储值，所以也可以排除数组的数据结构。

既然 buckets 不是链表，也不是数组，还有什么数据结构能够具有空间连续，但是元素存储不连续的特点呢？其实还真有这么一种数据结构 — 那就是哈希。

哈希表，根据英文 hash 音译得名，也被称为散列表。哈希是根据 key 值直接访问其在内存中的数据，这个key 值通过一个函数计算得来，这个函数被称为哈希函数。其存储特点如下图：

由此可以看出，buckets() 的实际存储方式与哈希表的存储特点比较符合，我们可以猜测 buckets() 是以哈希表的方式来存储的，为了验证这一点，我们可以在源码中找寻相关方法。在 cache_t 的 insert() 函数中可以找到如下一段代码：

bucket_t *b = buckets();
    mask_t m = capacity - 1; // 4-1=3
    mask_t begin = cache_hash(sel, m); // 哈希函数，计算出第一次插入的key值
    mask_t i = begin;

    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot.
    do {
        if (fastpath(b[i].sel() == 0)) {
            incrementOccupied();
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());
            return;
        }
        if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }
    } while (fastpath((i = cache_next(i, m)) != begin)); // 如果没有找到，则再次哈希，寻找下一个位置
复制代码

从这段代码中，我们发现两个函数 cache_hash() 和 cache_next()，其代码定义如下：

根据源码与注释可以发现 cache_hash() 函数的作用是 SEL作为key，缓存 buckets 来存储 SEL+IMP。即 SEL 通过位移运算得到存储的 key，这个函数其实就是一个哈希函数。由此也说明 buckets 其实是采用哈希表的结构进行存储的。如下图所示为 cache_t 缓存方法的示意图：

每一个 bucket_t 存储一个 SEL与IMP，用于缓存已经调用的方法，但是这些 bucket_t 并非存放在 cache_t 中，因为如果将 bucket_t 都放在 cache_t 中，将使得 objc_class 所占用的空间越来越大。所以苹果在另外开辟一片内存，用于存储缓存的 bucket_t，cache_t 通过 buckets 获取到这块区域的指针，然后通过下标取相应的 bucket_t，即缓存的方法。

本小节主要介绍了 cache_t 与 bucket_t，总结下来 cache_t、buckets()、bucket_t 的关系可概括如下图：

总结如下：

bucket_t 是一个结构体，内部包含两个成员 sel 和 imp，这里是保存缓存的方法的信息
bucket_t 作为元素存储在一个哈希表中，cache_t 通过 buckets() 函数获取到哈希表的首地址
cache_t 作为 objc_class 的成员变量，因此objc_calss就拥有了缓存的方法

二、方法缓存流程源码分析

在上一节探索时，提到了 insert() 函数，但是为什么会突然提到这个函数呢？因为想要探索 bucket 如何存储，那么我们就需要找到开始存储的地方，根据增删改查，我们正好在 cache_t 中找到了 insert()。本小节我们就以 insert() 函数为切入点，来探索下方法缓存的流程。

2.1 insert函数流程

insert() 函数的源码可以分为两部分来看，即 容量的判断与分配 和 存储bucket，下面分别分析下这两部分的源码。

2.1.1 是否扩容的判断

在LLDB获取缓存时，我们发现虽然 _occupied 由1变到了2，但是 _maybeMask 却始终是 3，那么我们猜测 _maybeMask表示总容量，下面我们就来探索下容量分配的源码，来验证下这个猜想，这部分的代码如下：

只是看着一段代码，可能比较混乱，下面我们逐步拆解一下：

850～851 行为获取初始值
- newOccupied = _occupied + 1; 即当前已占用数 + 1，即存入当前方法后的总占用数，后面会用该变量判断是否需要扩容
- oldCapacity, capacity 分别表示 上次容量，当前容量，初始化时 capacity == oldCapacity，后面会发生改变。这里可以看下 函数occupied() 和 函数capacity()

// occupied()返回已经占用的缓存数
mask_t cache_t::occupied() const
{
    return _occupied; 
}

// 获取当前的容量
unsigned cache_t::capacity() const
{
    return mask() ? mask()+1 : 0; 
}

// mask() 函数是根据 _maybeMask 或者 _bucketsAndMaybeMask 取出
// 关于mask()的定义有多处，会根据 CACHE_MASK_STORAGE 判定调用哪个函数定义
mask_t cache_t::mask() const
{
    return _maybeMask.load(memory_order_relaxed);
}
mask_t cache_t::mask() const
{
    uintptr_t maskAndBuckets = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return maskAndBuckets >> maskShift;
}

复制代码

852～856行：为缓存第一个方法时的条件判断，此时已占用数为0，容量也为0，因此会给容量赋一个初始值 INIT_CACHE_SIZE，在源码中该宏定义为4。然后会调用 reallocate 函数开辟存储空间。
```
INIT_CACHE_SIZE_LOG2 = 2,
INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2) // 1 左移2位得 4
复制代码
```

857～863行：为判断没有超出容量，不需要更多操作。

这里调用 cache_fill_ratio 函数，获取到 3/4 的负载因子，不超过这一范围即不需扩容

// 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;
  }
复制代码

865～871行：容量已经需要扩容，进行2倍扩容。这里跟第一次缓存时对比，都调用了 reallocate 函数，我们看下这个函数的实现：

该函数主要做了一下几步：

1、获取当前缓存的 buckets

2、根据新的容量为新的 buckets 开辟内存

3、设置 buckets 和 mask

4、根据 freeOld 决定是否释放老空间

针对缓存的释放可以有个对比，缓存第一个方法时，没有老空间，所以不需要释放；在扩容时，新开辟了空间后，老空间不需要了，所以要释放掉。这里可以看出，在扩容后，原本缓存的方法会被清除掉，之后再调用时会重新缓存到新开辟的内存中。

2.1.2 存储bucket的过程

容量开辟或者扩容后，就要进行存储了，这部分代码如下图所示：

873～876行：这几行是在做数据准备，获取到当前的buckets，通过哈希函数获取到要存储的位置
880～893行：这几行是在进行存储，下面按步骤分析下
- 首先判断当前的位置是否没有存值，即b[i].sel() == 0，如果没有存则占用数加1，并存储bucket_t
- 如果当前位置有值，则判断是否跟存入的是一个方法，如果是则直接return
- 上诉两种情况都不是，则在进行一次hash，计算下一个存储的位置，如此往复，知道最后得到的位置与 begin相同，即内存已存满，此时就不再存储，直接调用 bad_cache 函数。