在前面 iOS 类的结构分析 分析了 objc_class 的 bits， 今天我们来分析 objc_class 的 cache。

cache

首先我们通过源码来查看它的定义

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED //macOS、模拟器
    explicit_atomic<struct bucket_t *> _buckets;
    explicit_atomic<mask_t> _mask;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 //64位真机
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4 //非64位 真机
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;
#else
#error Unknown cache mask storage type.
#endif
    
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;
}

上面源码剔除了 const、void、static 和函数。explicit_atomic 是将普通指针转换为原子指针的操作，为了线程安全。这里我们无需过多的关注，我们发现 cache_t 的源码分成了3个架构的处理

• CACHE_MASK_STORAGE_OUTLINED 表示运行的环境 模拟器 或者 macOS
• CACHE_MASK_STORAGE_HIGH_16 表示运行环境是 64位的真机
• CACHE_MASK_STORAGE_LOW_4 表示运行环境是 非64位 的真机

此外，我们还看到在真机的架构中，mask 和 bucket 是写在一起，目的是为了优化，可以通过各自的掩码来获取相应的数据。我们再看下 bucket_t 的源码

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
    //方法等其他部分省略
}

同样的分为真机和非真机，唯一不同的是 sel 和 imp 的位置不同，由此我们可以猜测 cache 中存储的是 sel-imp。尽管不同 CPU 架构下的名称以及存储方式不同，但作用大致是相同的，我们可以将 cache_t 的结构简单理解如下：

下面我们来验证下

准备工作

定义一个 LCPerson 类，并定义2个实例方法及其实现

@interface LCPerson : NSObject

- (void)sayHello;
- (void)sayCode;

@end

@implementation LCPerson

- (void)sayHello {
    NSLog(@"sayHello");
}

- (void)sayCode {
    NSLog(@"sayCode");
}

@end

在 main 函数中创建一个 LCPerson 对象，并调用实例方法

断点调试

运行项目，此时会走到我们打的断点处，获取 LCPerson 类的首地址，偏移十六字节得到 cache 并打印数据信息（通过 objc_class 的源码：isa 占8字节，superClass 占8字节）

此时并没有执行任何方法，所以 sel 为 null，imp 为 0，执行下一步，再次打印 cache 的数据信息

我们看到 _buckets 里面有数据了，通过 cache_t 源码提供的 bucket() 方法打印查看

bucket_t 的源码提供了获取 sel imp 的方法，打印查看

以上可以知道，在没有执行方法调用时，此时的 cache 是没有缓存的，执行了一次方法调用，cache 中就有了一个缓存，即调用一次方法就会缓存一次方法。我们再次运行下一步，此时我们要怎么获取缓存的第二个方法（如果后续再添加方法，要怎么获取）？这里我们运用 指针偏移，即通过 buckets 的首地址偏移去获取后面缓存的方法，流程如下

原理解析

在上面我们获取 cache_t 的结构时，除了 _buckets 还有三个成员：

• _mask ：有2个作用，作为当前可存储的最大容量；作为掩码，取已缓存方法在 _buckets 中的下标
• _flags ：标记
• occupied：占位符，_buckets 中 已缓存的方法数量

由上面的调试信息，看一看到，每调用一个实例方法，_mask _flags 以及 occupied 会有相应的变化，下面我们调用多个方法，观察它们如何的变化

已调用的方法数量	0	1	2	3	4	5	6	7	8
_mask的值	0	3	3	7	7	7	7	7	15
_flags的值	32784	32784	32784	32784	32784	32784	32784	32784	32784
_occupied的值	0	1	2	1	2	3	4	5	1

我们发现，_mask 的值随着方法的调用数量在增加，但是 _occupied 的值似乎增加到一定程度后会回到1的值，那么 cache_t 是如何存储的？我们一探究竟

• 首先我们去 cache_t 的源码，乍一看好像没有直接的存储入口，但我们看到一个很特殊的操作方法

我们看下它的源码实现

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

看到这里，感觉有点眉目了，然后再全局搜索下什么地方调用了这个函数

在 objc->Source->objc-cache.mm 类的 cache_t 的 insert 调用了，顾名思义是插入的意思，我们继续搜索 insert() 方法的调用，此时搜索的地方很多，凭着判断，我们最终定位到了 objc-cache.mm 中 cache_fill 方法中的调用

综合上述的搜索的方法调用，我们可以猜测，当方法第一次调用时，就会以此调用 cache_fill、cache_t::insert 插入缓存

• cache_fill

void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
    runtimeLock.assertLocked();

#if !DEBUG_TASK_THREADS
    // Never cache before +initialize is done
    if (cls->isInitialized()) {
        cache_t *cache = getCache(cls);
#if CONFIG_USE_CACHE_LOCK
        mutex_locker_t lock(cacheUpdateLock);
#endif
        cache->insert(cls, sel, imp, receiver); //定位到此
    }
#else
    _collecting_in_critical();
#endif
}

• cache_t::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();
#endif

    ASSERT(sel != 0 && cls->isInitialized());
    /** 
      1注： 下面这一部分为初始化的过程，如果 occupied()为0,  并且buckets中无缓存内容 ，
      则开辟 4 个存储空间大小 为默认初始值。
   */
    mask_t newOccupied = occupied() + 1; // 即将要占用的数 = 已占用数+ 1
    unsigned oldCapacity = capacity(), capacity = oldCapacity; // 获取目前已占用数
    if (slowpath(isConstantEmptyCache())) {   // 如果缓存是空的
        if (!capacity) capacity = INIT_CACHE_SIZE;// 如果capacity 为0 初始化为4 
        reallocate(oldCapacity, capacity, /* freeOld */false); // 根据当前内容分配空间
    }

    /** 
      2注： 以下为判断空间是否足够过程
      如果空间不足,  扩容到原空间大小的2倍值，并重新分配空间大小
      并释放已存储的缓存，插入新缓存
   */
    //  arm64下 如果 newOccupied <= 容量的4分之3，存储空间还足够，不需额外处理
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) {
        // Cache is less than 3/4 full. Use it as-is.
    }
    // 如果超过 4分之3  
    else {
        // 扩容为原空间的 2倍大小  
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) { 
            capacity = MAX_CACHE_SIZE;  //  最大不能 超出 1<< 16
        }
        reallocate(oldCapacity, capacity, true); // 重新分配空间   存储新的数据，抹除已有缓存
    }
 
    /** 
      3注： 以下为插入缓存的过程
      遍历 buckets()内容，如果在缓存中找到了 传入的方法，直接退出
      如果在缓存中没有找到 传入的方法 将_occupied ++;，并且将方法存入缓存
      如果遇到hash冲突， cache_t查找下一个 直到回到begin 全部查找结束
    */

    // 获取散列表
    bucket_t *b = buckets();
    // 获取散列表大小 - 1
    mask_t m = capacity - 1;
    // 通过cache_hash函数【begin  = sel & m】计算出key值 k 对应的 index值
    // begin，用来记录查询起始索引
    mask_t begin = cache_hash(sel, m);
    // begin 赋值给 i，用于切换索引
    mask_t i = begin;

    do {
        if (fastpath(b[i].sel() == 0)) {  // 如果没有找到缓存的方法
            incrementOccupied(); //   _occupied ++;
            b[i].set<Atomic, Encoded>(sel, imp, cls); // 缓存实例方法
            return;
        }
        if (b[i].sel() == sel) {  // 如果找到需要缓存的方法，什么都不做，并退出循环
      
            return;
        }
    } while (fastpath((i = cache_next(i, m)) != begin));
// 当出现hash碰撞 cache_t查找下一个 直到回到begin 全部查找结束

    cache_t::bad_cache(receiver, (SEL)sel, cls);
}

cache->insert 函数大致做了 3件事

1.初始化缓存空间
2.判断是否需要扩容，如果需要，以原始空间的2倍扩容，重新分配空间，释放已有缓存信息
3.根据散列表中是否已有该方法的缓存情况插入缓存

流程图

• 初始化缓存空间

如果缓存空间还没有初始化，我们要对缓存空间进行初始化操作，默认开辟 4 个 bucket_t 大小的存储空间

enum {
    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2), //4
    MAX_CACHE_SIZE_LOG2  = 16,
    MAX_CACHE_SIZE       = (1 << MAX_CACHE_SIZE_LOG2),
};

if (!capacity) capacity = INIT_CACHE_SIZE;
reallocate(oldCapacity, capacity, /* freeOld */false);

调用 reallocate ，开启开辟空间流程，这里 freeOld 传入的是 false，因为首次初始化，不存在缓存，所以无需清理

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);

    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    // 释放旧的缓存信息
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
    }
}

调用 allocateBuckets 向系统申请 newCapacity 大小的空间

bucket_t *allocateBuckets(mask_t newCapacity)
{
    // Allocate one extra bucket to mark the end of the list.
    // This can't overflow mask_t because newCapacity is a power of 2.
    bucket_t *newBuckets = (bucket_t *)
        calloc(cache_t::bytesForCapacity(newCapacity), 1);

    bucket_t *end = cache_t::endMarker(newBuckets, newCapacity);

#if __arm__
    // End marker's sel is 1 and imp points BEFORE the first bucket.
    // This saves an instruction in objc_msgSend.
    end->set<NotAtomic, Raw>((SEL)(uintptr_t)1, (IMP)(newBuckets - 1), nil);
#else
    // End marker's sel is 1 and imp points to the first bucket.
    end->set<NotAtomic, Raw>((SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    
    if (PrintCaches) recordNewCache(newCapacity);

    return newBuckets;
}

reallocate 中通过 setBucketsAndMask 设置 buckets 和 mask，其中 mask 更新为新申请的总空间大小 - 1 （即 capacity - 1）

• 判断是否需要扩容

在进行方法缓存的时候，还需要判断空间是否够用，因为初始化时默认的空间大小为4。扩容是依据当前的空间大小（capacity） 以及 已占用数（occupied） 的情况进行扩容

capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
if (capacity > MAX_CACHE_SIZE) {
    capacity = MAX_CACHE_SIZE; //  最大 1<< 16
}
reallocate(oldCapacity, capacity, true);

扩容计算完毕之后，要重新调用 reallocate 函数重新分配存储空间，这里调用 reallocate(oldCapacity, capacity, /* freeOld */true); 这里的 freeOld 传入的是 true。释放已有的方法缓存。

需要扩容的时候，进行2倍 (capacity) 扩容，所以新空间大小一直为 4 的整数倍，如 4，8，16，32...，那么 mask 的大小(capacity -1)的取值为 3，7，15，31...

• 插入缓存

内存空间已经开辟完成，下面就是存储方法

bucket_t *b = buckets(); // 获取散列表
mask_t m = capacity - 1; // 获取散列表总长度 - 1 该值= mask的值
mask_t begin = cache_hash(sel, m);
mask_t i = begin;

// Scan for the first unused slot and insert there.
// There is guaranteed to be an empty slot because the
// minimum size is 4 and we resized at 3/4 full.
do {
    if (fastpath(b[i].sel() == 0)) { // 如果没有找到缓存的方法
        incrementOccupied(); //  _occupied ++;
        b[i].set<Atomic, Encoded>(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));

begin 作为散列表的初始查询下标，是经过 sel & mask 计算而来的

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    // 取 & 计算索引
    return (mask_t)(uintptr_t)sel & mask;
}

mask 值 始终为 capacity - 1，do while 循环的条件是 (i = cache_next(i, m) != begin ，判断不等于初始下标值 begin 是为了将散列表中的数据全部遍历结束，而cache_next( ) 是为了解决哈希冲突而进行的二次哈希。

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

根据下标值遍历查找 buckets( ) ，如果找到 sel，说明方法已经缓存，直接return，退出遍历。如果直至遍历结束依然没有在缓存中找到该方法，则将该方法存入 _bucket ，并更新已占用存储数（occupied++）。

• 关于扩容

方法的缓存是以散列表的形式进行存储的，是无序的。在哈希表这种数据结构里面，其性能受装载因子影响，装载因子可以用来表示空位率的大小，其公式为：装载因子 = 已填入的容量 / 散列表的总容量。装载因子越大，说明空闲的位置越少，冲突的可能性越多，散列表的性能会下降。尽可能小的装载因子可以提高散列表的性能，同时太小的值又容易触发扩容条件，所以这里苹果设计了这样一个的适当的值