在前面的文章中，我们探索了 iOS 类的底层原理，其中比较重要的四个属性，我们已经分析了其中的三个，现在我们开始分析第三个属性 cache_t，对于这个属性，我们可以学习到苹果对于缓存的设计与理解，同时也会接触到消息发送相关的知识。

我们在探索 iOS 底层的时候，尽量不要站在上帝视角去审视相应的技术点，我们应该尽量给自己多问出几个问题，然后尝试去解决每个问题，通过这样的探索，对提高我们阅读源码的能力是十分重要的。

1、 cache_t 基本结构

首先，我们还是再回过头来看看 OC 中类的结构

  1. struct objc_class {
  2.     Class isa;
  3.     Class superclass;
  4.     cache_t cache;          // 方法缓存
  5.     class_data_bits_t bits; // 具体的类信息
  7.     class_rw_t *data() { 
  8.         return bits.data();
  9.     }
  11.     // 省略代码.....
  12. }

接着我们查看一下源码中 cache_t 的定义

  1. struct cache_t {
  2. #if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
  3.     explicit_atomic<struct bucket_t *> _buckets;
  4.     explicit_atomic<mask_t> _mask;
  5. #elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
  6.     explicit_atomic<uintptr_t> _maskAndBuckets;
  7.     mask_t _mask_unused;
  9. #if __LP64__
  10.     uint16_t _flags;
  11. #endif
  12.     uint16_t _occupied;
  14.     // 省略代码.....
  15. }
  1. struct bucket_t {
  2.     // IMP-first is better for arm64e ptrauth and no worse for arm64.
  3.     // SEL-first is better for armv7* and i386 and x86_64.
  4. #if __arm64__
  5.     explicit_atomic<uintptr_t> _imp;
  6.     explicit_atomic<SEL> _sel;
  7. #else
  8.     explicit_atomic<SEL> _sel;
  9.     explicit_atomic<uintptr_t> _imp;
  10. #endif
  12.     // 省略代码.....
  13. }

所以从上面源代码的定义处，我们可以看出，bucket_t 其实缓存的是方法的实现 IMP。上面的苹果注释有一个有意思的地方，就是 IMP-first 和 SEL-first。

IMP-first is better for arm64e ptrauth and no worse for arm64.

  • IMP-first 对 arm64e 的效果更好，对 arm64 不会有坏的影响。

SEL-first is better for armv7* and i386 and x86_64.

  • SEL-first 适用于 armv7* 、i386 和 x86_64。

如果对于 SEL 和 IMP 不是很熟悉的同学可以去 objc4-781 源码中查看关于 method_t 的定义:

  1. struct method_t {
  2.     SEL name;           // 方法选择器
  3.     const char *types;  // 方法类型字符串
  4.     MethodListIMP imp;  // 方法实现
  6.     // 省略代码.....
  7. };

通过上面的源码，我们大致了解了 bucket_t 类型的结构，那么现在问题来了，类中的 cache 是在什么时候以什么样的方式来进行缓存的呢？

2、 LLDB 大法好

了解到 cache_t 和 bucket_t 的基本结构后，我们可以通过 LLDB 来打印验证一下：

image.png

我们发现，断点在18行的时候，_occupied 和 _mask 的值还为0，但当我们走到19行的时候，_occupied 和 _mask 的值已经分别为1和3了，现在我们打印一下 _buckets 里面的内容看看

image.png

我们可以看到，打印到 buckets 的第一个元素的时候，我们的 say111 方法被缓存了，也就是说 _occupied 可能表示的是当前被缓存方法的个数。这里可能会有同学会疑惑，为什么 alloc 方法为什么没有被缓存呢？其实这是因为 alloc 是类方法，根据我们前面探索类底层原理的时候，类方法是存储在元类里面的，所以这里的类对象的缓存里面只会存储对象方法，我们接着下一步执行到20行

image.png

_occupied 的值又发送变化了，我们前面的猜想又得到进一步的验证，我们再往下执行一行

image.png

这时候，_occupied 的值居然变成1了，但是我们往上看一下，的值已经从3变成到7。我们往前回顾一下当前缓存里面缓存的方法

_occupied 的值 _mask 的值 缓存的方法
1 3 Student 的 - say111 方法
2 3 Student 的 - say222 方法

可以看到，当我们缓存第三个方法的时候缓存发送了变化，如果大家对散列表这种数据结构比较熟悉的话，相信已经看出端倪了。是的，这里其实是用到了 开放寻址法 来解决散列冲突的（哈希冲突）。

关于哈希冲突，可以借助鸽笼理论，即把 11 只鸽子放进 10 个抽屉里面，肯定会有一个抽屉里面有 2 只鸽子。是不是理解起来很简单? 如果还有不了解散列表原理的，推荐可以看一下这篇文章，这里就不详细展开分析了 什么是散列表？

通过上面的探索，我们已经了解到方法缓存使用的是哈希表存储，并且为了解决无法避免的哈希冲突使用的是开放寻址法，而开放寻址法必然要在合适的时机进行扩容，这个时机肯定不是会在数据已经装满的时候，我们可以进源码探索一下，我们先定位到 cache_t 的源码处

我们怎么去寻找 cache_t 的扩容算法呢，其实我们应该猜到，我们每次缓存方法的时候，_occupied 的值都会变化，所以我们从这方面入手，通过查找源码我们发现了下面这段函数

  1. void cache_t::incrementOccupied() 
  2. {
  3.     _occupied++;
  4. }

然后我们 全局搜索 incrementOccupied() 函数调用的地方

image.png

只找到了这一处的调用，我们查看一下这个是什么函数，通过函数名和里面的代码函数，我们可以基本确定，这就是我们想要查找的核心部分

image.png

然后我们来看看它里面的判断逻辑是怎样的，为了方便阅读，我们删减一部分无关紧要的代码和注释

  1. void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
  2. {
  3.     // 插入新的方法缓存，并且数量+1
  4.     mask_t newOccupied = occupied() + 1;
  5.     unsigned oldCapacity = capacity(), capacity = oldCapacity;
  7.     // 如果还没有缓存过方法
  8.     if (slowpath(isConstantEmptyCache())) {
  10.         // 最初分配的容量4
  11.         if (!capacity) capacity = INIT_CACHE_SIZE;
  13.         // 创建和分配内存
  14.         reallocate(oldCapacity, capacity, /* freeOld */false);
  15.     }
  16.     else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) {
  17.         // 保证缓存表存的方法数量小于等于容量的3/4
  18.     }
  19.     else {
  21.         // 如果超过容量的3/4，进入扩容，容量进行翻倍处理
  22.         capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
  24.         //  不能超过最大值，最大值为 1 << 16
  25.         if (capacity > MAX_CACHE_SIZE) {
  26.             capacity = MAX_CACHE_SIZE;
  27.         }
  29.         // 超过容量之后，将之前缓存的方法全部清空
  30.         reallocate(oldCapacity, capacity, true);
  31.     }
  33.     bucket_t *b = buckets();
  34.     mask_t m = capacity - 1;
  35.     mask_t begin = cache_hash(sel, m);
  36.     // 通过 sel & mask 计算出 sel 该存放的位置 i
  37.     mask_t i = begin;
  39.     // 如果计算出来的值没有缓存方法，则直接插入保存，否则如果已经有方法插入了，i--，即是如果被占用，往上走一格，还被占用继续往上走，
  40. 因为规则限定了3/4，所以肯定能找到没有保存方法的位置。
  41.     do {
  42.         if (fastpath(b[i].sel() == 0)) {
  43.             incrementOccupied();
  44.             b[i].set<Atomic, Encoded>(sel, imp, cls);
  45.             return;
  46.         }
  48.         // 如果是其他线程已经把方法添加到这里了，那就直接退出循环。
  49.         if (b[i].sel() == sel) {
  50.             return;
  51.         }
  52.     } while (fastpath((i = cache_next(i, m)) != begin)); // i 如果不等于初始位置 i--，继续循环。
  54.     cache_t::bad_cache(receiver, (SEL)sel, cls);
  55. }

总结

  1. 方法的存储并不是按照数组那样从前到后进行存储，而是通过 sel & mask 来存储的，所以难免会存在内存利用率低，但是加快了方法查找的速度，即:空间换时间。
  2. 方法缓存是先于 isa 的方法查找的，就是说，缓存中找不到，再到自己的方法列表中查找，找到之后也会缓存到 cache_t 中，如果是父类的方法，也是会缓存到自己的表当中的。
  3. arm64 之后增加了很多 & mask 的操作，获取具体的类信息，也是通过 bits & mask 来获取，里面存储的信息更多了(文中提到的 mask 不同的地方，mask 的值是不同的)。
  4. 如果 cache_next(i,m) 循环到0，还未找到，赋值 i == mask，继续循环，直到 i == begin，证明没有缓存这个方法，这是最差的情况，相当于遍历了一遍数组。

3、自定义输出 cache_t

如果我们每次都使用上方的 lldb 进行调试，估计会累的够呛，我们可以使用一个自定义的方式去打印一下。自定义代码如下：

  1. typedef unsigned long           uintptr_t;
  2. typedef uint32_t mask_t;
  5. struct custom_bucket_t {
  6.     SEL _sel;
  7.     uintptr_t _imp;
  8. };
  10. struct cache_t {
  11.     struct custom_bucket_t *_buckets;
  12.     mask_t _mask;
  13.     mask_t _occupied;
  14. };
  16. struct custom_class_data_bits_t {
  17.     uintptr_t bits;
  18. };
  20. struct custom_objc_class  {
  21.     Class ISA;
  22.     Class superclass;
  23.     struct cache_t cache;
  24.     struct custom_class_data_bits_t bits;
  25. };
  27. int main(int argc, const char * argv[]) {
  28.     @autoreleasepool {
  30.         Student *stu = [Student alloc];
  31.         Class pClass = object_getClass(stu);
  33.         [stu say111];
  34.         [stu say222];
  35.         [stu say333];
  36.         [stu say444];
  37.         [stu say555];
  38.         [stu say666];
  40.         struct custom_objc_class *zl_pClass = (__bridge struct custom_objc_class *)(pClass);
  41.         NSLog(@"%u - %u",zl_pClass->cache._occupied,zl_pClass->cache._mask);
  42.         for (mask_t i = 0; i<zl_pClass->cache._mask; i++) {
  43.             // 打印获取的 bucket
  44.             struct custom_bucket_t bucket = zl_pClass->cache._buckets[i];
  45.             NSLog(@"%@ - %lu",NSStringFromSelector(bucket._sel),bucket._imp);
  46.         }
  48.         NSLog(@"Hello, World!");
  49.     }
  50.     return 0;
  51. }

打印结果如下：

image.png

这样就能很清晰的看到 cache_t 中的缓存方法了。

4、总结

4.1 cache_t 的工作流程

  • 当前查找的 IMP 没有被缓存，调用 reallocate 方法进行创建-分配内存，然后使用 bucket 的 set 方法进行填充缓存。
  • 当前查找的 IMP 已经被缓存了，然后判断缓存容量是否已经达到 3/4 的临界点。
    • 如果已经到了临界点，则需要进行扩容，扩容大小为原来缓存大小的 2 倍。扩容后处于效率的考虑，会清空之前的内容，然后把当前要查找的 IMP 通过 bucket 的 set 方法缓存起来。
    • 如果没有到临界点，那么直接进行缓存。

4.2 cache_t 流程图

image.png

4.3 cache_t 总结

  • cache_t 缓存会提前进行扩容防止溢出。
  • 方法缓存是为了最大化的提高程序的执行效率。
  • 苹果在方法缓存这里用的是 开放寻址法 来解决哈希冲突。
  • 通过 cache_t 我们可以进一步延伸去探究 objc_msgSend，因为查找方法缓存是属于 objc_msgSend 查找方法实现的快速流程。

下一篇我们将继续探索 iOS 中方法的底层原理。