1. cache 中存储的是什么？

在 objc_class结构体中，有 cache 这个成员，而且还是一个结构体类型：

 // Class ISA;
    Class superclass;
    cache_t cache;             // formerly cache pointer and vtable
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
    ...

我们直接看cache_t的源码：

struct cache_t {
//macOS、模拟器 -- 主要是架构区分
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    // explicit_atomic 显示原子性，目的是为了能够 保证 增删改查时 线程的安全性
   // 方法的缓存数组（以散列表的形式存储 bucket_t，用来存储sel imp）
    explicit_atomic<struct bucket_t *> _buckets;
// _buckets 的数组长度-1，容量的临界值
    explicit_atomic<mask_t> _mask;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 // 64位真机
    // 掩码和 Buckets 指针共同保存在 uintptr_t 类型的 _maskAndBuckets中
    explicit_atomic<uintptr_t> _maskAndBuckets;
    // 未使用的容量
    mask_t _mask_unused;
    
    // 高 16 位是 mask 掩码，即 _maskAndBuckets 右移 48 位得到 mask
    static constexpr uintptr_t maskShift = 48;
    // 掩码后的其他位必须为 0
    // msgSend  利用这些额外的位，在单个指令中从 _maskAndBuckets 构造了值 mask<<4
    static constexpr uintptr_t maskZeroBits = 4;

    // 我们可以保存的最大的 mask 值
    // (64 - maskShift) 即掩码位数，然后 将 1 左移掩码位数后再减 1 即 16 位能保存的最大二进制数值
    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
        
    // 应用于 _maskAndBuckets 的掩码，以获取 buckets 指针
    // 1 左移 44（48-4）位后再减 1（44 位 1，其余都是 0 的数值）
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;

    // 确保我们有足够的位用于存储 buckets 指针。
    static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers.");

#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4 //非64位 真机
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;

    // _maskAndBuckets 将掩码移位存储在低 4 位中，并将 buckets  指针存储在该值的其余部分中
#else
#error Unknown cache mask storage type.
#endif
    
#if __LP64__
    // 如果是 64 位环境的话，会多一个 _flags 标志位
    uint16_t _flags;
#endif
    // 缓存数组的已占用量
    uint16_t _occupied;

    //方法省略.....
}

我们看到最上面有一个宏判断，其实是架构的处理：

#define CACHE_MASK_STORAGE_OUTLINED 1
#define CACHE_MASK_STORAGE_HIGH_16 2
#define CACHE_MASK_STORAGE_LOW_4 3

#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
#endif

我们再来看bucket_t的源码，分为两个版本：真机和非真机，不同的区别只是在于 sel 和 imp 的顺序不一致：

struct bucket_t {
private:
    // IMP-first is better for arm64e ptrauth and no worse for arm64.
    // SEL-first is better for armv7* and i386 and x86_64.
#if __arm64__ // 真机
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else // 非真机
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
... 方法等其他部分
}

所以通过上面两个结构体可以知道，cache 中缓存的是sel-imp。
整体结构如下所示：

image.png

2. 在 cache 中查找 sel-imp

cache_t中查找存储的sel-imp，有以下两种方式:

• 通过源码查找
• 脱离源码在项目中查找

2.1 准备工作

创建一个 Person 类，并定义两个属性和 5 个实例方法及其实现：

@interface Person : NSObject
@property (nonatomic, strong) NSString *name;
@property (nonatomic, copy) NSString *nickName;

- (void)sayHello;
- (void)sayCode;
- (void)sayMaster;
- (void)sayNB;
+ (void)sayHappy;
@end

@implementation Person

- (void)sayHello{
    NSLog(@"Person say: %s",__func__);
}
- (void)sayCode{
    NSLog(@"Person say: %s",__func__);
}
- (void)sayMaster{
    NSLog(@"Person say: %s",__func__);
}
- (void)sayNB{
    NSLog(@"Person say: %s",__func__);
}
+ (void)sayHappy{
    NSLog(@"Person say: %s",__func__);
}

@end

2.2 通过 lldb 调试和源码进行查找

在 main 中定义 Person 对象，并调用其中的 3 个实例方法，添加断点：

截屏2021-01-09 下午5.47.39.png

• cache的获取，需要通过 pClass 的首地址平移 16 个字节，即首地址+0x10 获取 cache 的地址
• 从源码中可得，sel-imp是在 cache_t的 _buckets属性中(目前是 macOS 环境)，而且 cache_t结构体也提供了获取_buckets()属性的方法buckets()
• 在没有执行方法调用时，此时的 cache 是没有缓存的，执行了一次方法调用，cache 中就有了一个缓存，即调用一次方法就会缓存一次方法
• 获取了_buckets属性，就可以获取 sel-imp了，这两个的获取在bucket_t结构体中同样提供了相应的获取方法sel()以及imp(pClass)

接着上面的步骤，我们再次调用一个方法，这次我们想要获取第二个 sel，调试过程如下：

截屏2021-01-09 下午6.02.32.png

• 第一个调用方法的存储获取很简单，直接通过_buckets的首地址调用对应的方法即可
• 获取第二个bucket_t需要通过_buckets的首地址进行偏移，即p*($9+1)即可获取第二个bucket_t，如果有多个方法需要获取，以此类推。

2.3 脱离源码通过项目查找

脱离源码环境，就是将所需的源码的部分拷贝至项目中，其完整代码如下：

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

struct lg_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct lg_cache_t {
    struct lg_bucket_t * _buckets;
    mask_t _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct lg_class_data_bits_t {
    uintptr_t bits;
};

struct lg_objc_class {
    Class ISA;
    Class superclass;
    struct lg_cache_t cache;             // formerly cache pointer and vtable
    struct lg_class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
};

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        Person *person = [Person alloc];
        Class pClass = [person class];
        
        [person sayHello];
        [person sayCode];
        
        struct lg_objc_class *lg_pClass = (__bridge struct lg_objc_class *)(pClass);
        NSLog(@"%hu - %u",lg_pClass->cache._occupied,lg_pClass->cache._mask);
        for (mask_t i = 0; i<lg_pClass->cache._mask; i++) {
            // 打印获取的 bucket
            struct lg_bucket_t bucket = lg_pClass->cache._buckets[I];
            NSLog(@"%@ - %p",NSStringFromSelector(bucket._sel),bucket._imp);
        }
    }
    return 0;
}

注：objc_class的ISA 属性是继承自 objc_object的，但这里去掉了这个关系，所以将 ISA 属性直接加上了。

输出结果：

2021-01-10 14:30:07.436173+0800 DebugTest[5488:251965] Person say: -[Person sayHello]
2021-01-10 14:30:07.436624+0800 DebugTest[5488:251965] Person say: -[Person sayCode]
2021-01-10 14:30:07.436683+0800 DebugTest[5488:251965] 2 - 3
2021-01-10 14:30:07.436827+0800 DebugTest[5488:251965] sayHello - 0x2940
2021-01-10 14:30:07.436913+0800 DebugTest[5488:251965] sayCode - 0x2eb0
2021-01-10 14:30:07.436956+0800 DebugTest[5488:251965] (null) - 0x0

再增加两个方法的调用，其打印结果如下：

2021-01-10 15:12:27.852728+0800 DebugTest[5627:264649] Person say: -[Person sayHello]
2021-01-10 15:12:27.853139+0800 DebugTest[5627:264649] Person say: -[Person sayCode]
2021-01-10 15:12:27.853204+0800 DebugTest[5627:264649] Person say: -[Person sayHello]
2021-01-10 15:12:27.853247+0800 DebugTest[5627:264649] Person say: -[Person sayNB]
2021-01-10 15:12:27.853286+0800 DebugTest[5627:264649] 1 - 7
2021-01-10 15:12:27.853328+0800 DebugTest[5627:264649] (null) - 0x0
2021-01-10 15:12:27.853469+0800 DebugTest[5627:264649] sayNB - 0x2ed8
2021-01-10 15:12:27.853519+0800 DebugTest[5627:264649] (null) - 0x0
2021-01-10 15:12:27.853557+0800 DebugTest[5627:264649] (null) - 0x0
2021-01-10 15:12:27.853594+0800 DebugTest[5627:264649] (null) - 0x0
2021-01-10 15:12:27.853629+0800 DebugTest[5627:264649] (null) - 0x0
2021-01-10 15:12:27.853665+0800 DebugTest[5627:264649] (null) - 0x0

对于这次的打印结果，有以下几点疑问：

• _mask是什么？
• _occupied是什么？
• 为什么随着方法调用的增多，其打印的 occupied 和 mask 会变化？
• 打印的 bucket 数据为什么只有 sayNB了？

3. cache_t 底层原理分析

3.1 主要流程介绍

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

截屏2021-01-10 下午3.18.03.png

void cache_t::incrementOccupied() 
{
    _occupied++;
}

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

截屏2021-01-10 下午3.19.20.png

insert方法就是插入方法了，而 cache 中存储的就是 sel-imp，所以我们从 insert 方法开始分析，下面是 cache 原理分析的流程图：

image.png

3.2 insert 方法实现

ALWAYS_INLINE
void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
#if CONFIG_USE_CACHE_LOCK
    cacheUpdateLock.assertLocked();
#else
    // 加锁，如果加锁失败则执行断言
    runtimeLock.assertLocked(); // 同样，__objc2__ 下使用 runtimeLock 
#endif
    
    // 断言 sel 不能是 0 且 cls 已经完成初始化
    ASSERT(sel != 0 && cls->isInitialized());

    // 如果缓存占用少于 3/4 则可以继续保持原样使用。
    
    // 记录新的占用量（旧的占用量加 1）
    mask_t newOccupied = occupied() + 1;
    
    // 旧容量
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    
    if (slowpath(isConstantEmptyCache())) { // 很可能为假
        // 如果目前是空缓存的话，空缓存只是 static bucket_t **emptyBucketsList 用来占位的，
        // 实际并不存储 bucket_t，我们需要重新申请空间，替换空缓存。
        if (!capacity) capacity = INIT_CACHE_SIZE; // 如果 capacity 为 0，则赋值给初始值 4
        // 根据 capacity 申请新空间并初始化 buckets、mask(capacity - 1)、_occupied 
        // 这里还有一个点，由于旧 buckets 是准备的占位的静态数据是不需要释放的，
        // 所以最后一个参数传递的是 false。
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) { 
        // 大部分情况都在这里
        // 缓存占用少于等于 3/4 的空间。照原样使用。
        
        // 小括号里面加了一个 CACHE_END_MARKER
        // 是因为在 __arm__  ||  __x86_64__  ||  __i386__ 这些平台下，
        // 会在 buckets 的末尾放一个 bucket_t *end，所以这里又加了 1
        // 而 __arm64__ 平台下则不存在这个多 +1
    }
    else {
        // 第三种情况则是需要对散列表空间进行扩容
        // 扩大为原始 capacity 的 2 倍
        // 且这里的扩容时为了性能考虑是不会把旧的缓存复制到新空间的。
        
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        
        // 如果大于 MAX_CACHE_SIZE，则使用 MAX_CACHE_SIZE(1 << 16)
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        
        // 申请空间并做一些初始化
        // 不同与 isConstantEmptyCache 的情况，这里扩容后需要释放旧的 buckets，
        // 所以这里第三个参数传的是 true，表示需要释放旧 buckets，而这里它也不是立即释放的，
        // 在旧 buckets 没有被使用并且收集的旧 buckets 容量已经到达阀值了，
        // 则会真正进行内存空间的释放
        reallocate(oldCapacity, capacity, true);
    }

    // 临时变量
    bucket_t *b = buckets();
    // mask = cap -1
    mask_t m = capacity - 1;
    
    // 使用 sel 和 _mask 进行哈希计算，取得 sel 的哈希值 
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;

    // 扫描第一个未使用的 "插槽"，然后将 bucket_t 插入其中。
    // 保证有一个空插槽，因为最小大小为4，
    // 且上面已经做过判断如果使用占比超过 3/4 则进行扩容，
    // 且这里的扩容为了性能考虑是不会把旧的缓存复制到新空间的，
    // 旧 buckets 会被抛弃，并在合适时候释放其内存空间
    
    // 这里如果发生哈希冲突的话 do while 会进行一个线性的哈希探测(开放寻址法)，
    // 为 sel 和 imp 找一个空位。
    do {
        if (fastpath(b[i].sel() == 0)) {
            // 如果 self 为 0，则表示 sel 的哈希值对应的下标处刚好是一个空位置，
            // 直接把 sel 和 imp 放在此处即可。
            
            // occupied 已占用数量 +1 
            incrementOccupied();
            
            // 以原子方式把 sel 和 imp 保存在 Bucket_t 的 _sel 和 _imp 中 
            b[i].set<Atomic, Encoded>(sel, imp, cls);
            
            return;
        }
        if (b[i].sel() == sel) {

            // 在 cacheUpdateLock(runtimeLock) 加锁之前，
            // 该 sel/imp 已由其他一些线程添加到缓存中。
            
            return;
        }
        
      // 下一个哈希值探测，这里不同的平台不同处理方式依次 +1 或者 -1
    } while (fastpath((i = cache_next(i, m)) != begin));

    // 如果未找到合适的位置则 bad_cache
    cache_t::bad_cache(receiver, (SEL)sel, cls);
}

insert 方法主要分为以下3部分：

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

3.2.1 计算当前的缓存占用量：

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

mask_t newOccupied = occupied() + 1;

关于缓存占用量的计算，需要注意：

• alloc申请空间时，此时的对象已经创建，如果再调用init 方法，occupied 也会+1，上面示例中我们没有调用 init 方法；
• 当有属性赋值时，会隐式调用set 方法，occupied 也会增加
• 当有方法调用时，occupied 也会增加

3.2.2 根据缓存占用量判断执行的操作：

• 1.如果是第一次创建，默认开辟 4 个
• 2.如果缓存占用量<=当前总量的 3/4，则不作任何处理
• 3.如果缓存占用量超过 3/4，需要进行两倍扩容，以及重新开辟空间，此时之前的缓存会被释放，也就是我们上面看到只有 sayNB 一个方法的原因

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

ALWAYS_INLINE
void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    // 一个临时变量用于记录旧的散列表
    bucket_t *oldBuckets = buckets();
    
    // 为新散列表申请指定容量的空间，此时只是一个临时变量
    bucket_t *newBuckets = allocateBuckets(newCapacity);

    // Cache's old contents are not propagated.
    // 缓存的旧内容不会传播。
    
    // This is thought to save cache memory at the cost of extra cache fills.
    // 这被认为是以额外的缓存填充为代价来节省缓存内存的。
    // fixme re-measure this 重新测量

    ASSERT(newCapacity > 0);
    ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
    
    // 设置 buckets 和 mask，将临时的 buckets 和 mask 存入缓存中
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
        // 这里不是立即释放旧的 bukckts，而是将旧的 buckets 添加到存放旧散列表的列表中，以便稍后释放，注意这里是稍后释放。
        cache_collect_free(oldBuckets, oldCapacity);
    }
}

上面reallocate这个方法主要有以下几步：

• allocateBuckets 方法：向系统申请开辟内存，即开辟 bucket，此时的 bucket 只是一个临时变量
• setBucketsAndMask 方法，将临时的 bucket 和 mask 存入缓存；
  如果是真机，根据 bucket 和 mask 的位置存储，并将occupied 占用设置为 0：
  
  image.png
  
  如果不是真机，正常存储 bucket 和 mask，并将 occupied 占用设置为 0：
  
  image.png
• 如果有旧的buckets，则需要清理之前的缓存，即调用 cache_collect_free方法，其源码实现如下：

static void cache_collect_free(bucket_t *data, mask_t capacity)
{
#if CONFIG_USE_CACHE_LOCK
    cacheUpdateLock.assertLocked();
#else
    runtimeLock.assertLocked(); // 加锁，加锁失败执行断言
#endif

    // 记录等待释放的容量 
    if (PrintCaches) recordDeadCache(capacity);

    // 为 garbage 准备空间，需要时进行扩容，创建垃圾回收空间
    _garbage_make_room ();
    
    // 增加 garbage_byte_size 的值
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    
    // 把旧的 buckets 放进 garbage_refs 中，garbage_count 并自增 1
    garbage_refs[garbage_count++] = data;
    
    // 尝试去释放累积的旧缓存（bucket_t）
    cache_collect(false);
}

这个方法主要有以下几步：

• _garbage_make_room方法，创建垃圾回收空间：

static void _garbage_make_room(void)
{
    static int first = 1; // 静态局部变量，下次进来 first 依然是上次的值

    // 第一次需要时创建收集表
    if (first)
    {
        first = 0; // 此处置为 0 后，以后调用 _garbage_make_room 再也不会进到这个 if
        // 申请初始空间
        // 申请 INIT_GARBAGE_COUNT * sizeof(void *) 字节个空间。
        // (malloc 不会对空间进行初始化，会保持申请时的垃圾数据)
        garbage_refs = (bucket_t**)malloc(INIT_GARBAGE_COUNT * sizeof(void *));
        
        // 当前 garbage_refs 的容量是 INIT_GARBAGE_COUNT
        garbage_max = INIT_GARBAGE_COUNT;
    }

    // Double the table if it is full
    // 如果当前 garbage_refs 中 refs 的数量等于 garbage_max 就对 garbage_refs 扩容为当前的 2 倍
    else if (garbage_count == garbage_max)
    {
        // garbage_refs 扩容为 2 倍
        garbage_refs = (bucket_t**)
            realloc(garbage_refs, garbage_max * 2 * sizeof(void *));
        // 更新 garbage_max 为 2 倍
        garbage_max *= 2;
    }
}

• 记录存储这次的 bucket
• cache_collect方法，释放累积的旧缓存

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

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

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

cache_hash 哈希算法：

// Class points to cache. SEL is key. Cache buckets store SEL+IMP.
// 类指向缓存。 SEL 是 key。Cache 的 buckets 中保存 SEL+IMP(即 struct bucket_t)。

// Caches are never built in the dyld shared cache.
// Caches 永远不会构建在 dyld 共享缓存中。

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    // 觉的 hash 值计算好随意，就是拿 sel 和 mask 与一下，保证不会越界
    return (mask_t)(uintptr_t)sel & mask;
}

cache_next 哈希冲突算法：
这里是发生哈希冲突时，哈希值的移动探测方式在不同的平台下有不同的处理:

#if __arm__  ||  __x86_64__  ||  __i386__
// objc_msgSend has few registers available.
// objc_msgSend 的可用寄存器很少。

// Cache scan increments and wraps at special end-marking bucket.
// 缓存扫描增量包裹在特殊的末端标记桶上。
//（此处应该说的是 CACHE_END_MARKER 是 1 时的 endMarker 的位置在 buckets 首位）

#define CACHE_END_MARKER 1

// i 每次向后移动 1，与 mask，保证不会越界
//（并且是到达 mask 后再和 mask 与操作会是 0 ，此时则从 buckets 的 0 下标处开始，
// 然后再依次向后移动探测直到到达 begin，如果还没有找到合适位置，那说明发生了内存错误问题）

static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}

#elif __arm64__
// objc_msgSend has lots of registers available.
// objc_msgSend 有很多可用的寄存器。
// Cache scan decrements. No end marker needed.
// 缓存扫描减量。无需结束标记。
//（此处说的是 CACHE_END_MARKER 是 0 时，不存在 endMarker 赋值）

#define CACHE_END_MARKER 0

// i 依次递减
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}

#else

// 未知架构
#error unknown architecture

#endif

到此，cache_t的基本流程分析完成了，现在回答一下上面的几个问题:

• _mask是什么？
  _mask是掩码数据，用在哈希算法或者哈希冲突算法中，其中mask = capacity-1。

• _occupied是什么？
  _occupied表示哈希表中 sel-imp的占用大小，init| 属性赋值 | 方法调用，会导致 occupied 变化。

• 为什么随着方法调用的增多，其打印的 occupied 和 mask 会变化？
  在cahce 初始化时分配的空间是4 个，随着方法调用的增多，存储的 sel-imp个数超过总容量的3/4时，会对 cache 进行两倍扩容。

• 打印的 bucket 数据为什么只有 sayNB 了？
  在扩容时，重新申请内存导致。