在前面的文章中我们探索了objc_class中isa和bits，这次主要是分析objc_calss中的cache属性

一 . cache_t 结构探索

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED//macOS、模拟器 -- 主要是架构区分
    // explicit_atomic 显示原子性，目的是为了能够 保证 增删改查时 线程的安全性
    //等价于 struct bucket_t * _buckets;
    //_buckets 中放的是 sel imp
    //_buckets的读取 有提供相应名称的方法 buckets()
    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;
    
    //以下都是掩码，即面具 -- 类似于isa的掩码，即位域
    // 掩码省略....
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4 //非64位 真机
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;

    //以下都是掩码，即面具 -- 类似于isa的掩码，即位域
    // 掩码省略....
#else
#error Unknown cache mask storage type.
#endif
    
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;

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

struct bucket_t {
private:
#if __arm64__ //真机
    //explicit_atomic 是加了原子性的保护
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else //非真机
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
    //方法等其他部分省略
}

从上面源码可以看出cache_t主要存储sel-imp
主要结构如下图

结构图

• _mask 掩码(面具)用来获取制定位数的数据,如获取isa中的代表对象信息的33位或者44位数据指针信息
• _flags 标记
• _occupied占用位置个数

在第四篇文章,通过指针首地址偏移的方式,分析过bits的结构,现在用同样的方式分析下cache_t的结构

准备一个类 并实现部分方法 main函数中调用断点执行

    Person *p = [[Person alloc] init];

    [p instanceMethod1];
    [p instanceMethod2];
    [p instanceMethod3];
    [p instanceMethod4];
    [p instanceMethod5];
    [p instanceMethod6];
    [p instanceMethod7];
    [p instanceMethod8];

在instanceMethod1之前打断点，通过lldb调试工具，查看p的类的内存结构

(lldb) x/4gx p.class
0x100002488: 0x0000000100002460 0x0000000100334140
0x100002498: 0x0000000100680ff0 0x0005801000000007

我们已知类的内存布局，是以isa、superclass、cache_t、class_data_bits_t顺序排布的，其中isa 与 superclass分别占用8个字节，所以 cache_t的位置应该是从类的首地址偏移16字节的位置，所以我们取0x100002488 偏移 16字节，即 0x100002498的地址

(lldb) p (cache_t *)0x100002498
(cache_t *) $1 = 0x0000000100002498
(lldb) p *$1
(cache_t) $2 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = 0x0000000100680ff0 {
      _sel = {
        std::__1::atomic<objc_selector *> = 0x00007fff75c3186
      }
      _imp = {
        std::__1::atomic<unsigned long> = 4047440
      }
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = 3
  }
  _flags = 32784
  _occupied = 1
}

其中 _buckets中存储 sel的地址 和 编码后的 imp；_mask 为3，_occupied 为1（虽然 自定义的实例方法还没有调用，但是 init方法已执行，所以此处为1），我们继续增加调用方法的数量，观察_mask 与_occupied的取值，

• _mask 3 3 7
• _occupied 1 2 1

为什么会发生这样的变化的 我们进行下面的探索

方法的存取

首先我们要找到存储的源码

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    // ...省略代码 （错误处理相关代码）
    
    // Use the cache as-is if until we exceed our expected fill ratio.
    mask_t newOccupied = occupied() + 1; //没有属性赋值的情况下 newOccupied  = 1 occupied = 0
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    if (slowpath(isConstantEmptyCache())) {//occupied = 0 创建缓存
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE;//初始化 capacity  = 4
        reallocate(oldCapacity, capacity, /* freeOld */false);//开辟空见
    }
    else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) {
        // Cache is less than 3/4 or 7/8 full. Use it as-is.
//如果 <= 占用内存的 3/4  啥也不做
    }
#if CACHE_ALLOW_FULL_UTILIZATION
    else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) {
        // Allow 100% cache utilization for small buckets. Use it as-is.
    }
#endif
    else { //如果超出了 3/4 两倍扩容 即 occupied = 2 的时候
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;//扩容两倍 
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);
    }

    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    mask_t begin = cache_hash(sel, m);//求cache哈希 通过哈希算法请求 sel下标
    mask_t i = begin;

    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot.
//如果存在哈希冲突  ,从冲突的下表开始遍历 
    do {
//如果当前遍历的鞋标都拿不到sel,即表示没有存储sel
        if (fastpath(b[i].sel() == 0)) {
//存储sel   Occupied ++ 
            incrementOccupied();
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());
            return;
        }
//如果当前哈希下标的sel == sel  直接返回
        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));

    bad_cache(receiver, (SEL)sel);
#endif // !DEBUG_TASK_THREADS
}

主要分为以下几部分

【第一步】初始化缓存空间

• 当属性未赋值及无方法调用时，此时的occupied()为0，而newOccupied为1
• init及方法赋值调用set方法 occupied也会+1

reallocate 创建新空间并释放旧空间的函数

• 该方法，在第一次创建以及两倍扩容时，都会使用，其源码实现

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    // 读取旧buckets数组
    bucket_t *oldBuckets = buckets();
    // 创建新空间大小的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

    // 新空间必须大于0
    ASSERT(newCapacity > 0);

    // 新空间-1 转为mask_t类型，再与新空间-1 进行判断
    ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);

    // 设置新的bucktes数组和mask
    // 【重点】我们发现mask就是newCapacity - 1, 表示当前最大可存储空间
    setBucketsAndMask(newBuckets, newCapacity - 1);

    // 释放旧内存空间
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
    }
}

allocateBuckets :向系统申请开辟内存，即开辟bucket

bucket_t *allocateBuckets(mask_t newCapacity)
{
    // 创建1个bucket
    bucket_t *newBuckets = (bucket_t *)
        calloc(cache_t::bytesForCapacity(newCapacity), 1);
    // 将创建的bucket放到当前空间的最尾部，标记数组的结束
    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
    // 将结束标记为sel为1，imp为这个buckets
    end->set<NotAtomic, Raw>((SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif

    // 只是打印记录
    if (PrintCaches) recordNewCache(newCapacity);

    // 返回这个bucket
    return newBuckets;
}

cache_collect_free 释放内存空间 如果有旧的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);

    // 垃圾房： 开辟空间 （如果首次，就开辟初始空间，如果不是，就空间*2进行拓展）
    _garbage_make_room ();
    // 将当前扩容后的capacity加入垃圾房的尺寸中，便于后续释放。
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    // 将当前新数据data存放到 garbage_count 后面 这样可以释放前面的，而保留后面的新值
    garbage_refs[garbage_count++] = data;
    // 不记录之前的缓存 = 【清空之前的缓存】。
    cache_collect(false);
}

【第二步】根据缓存占用量判断执行的操作

• 如果是第一次创建，则默认开辟4个
• 如果缓存占用量小于等于3/4，则不作任何处理
• 如果缓存占用量超过3/4，则需要进行两倍扩容以及重新开辟空间

【第三步】针对需要存储的bucket进行内部imp和sel赋值

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

• 如果哈希下标的位置未存储sel，即该下标位置获取sel等于0，此时将sel-imp存储进去，并将occupied占用大小加1

• 如果当前哈希下标存储的sel 等于 即将插入的sel，则直接返回

• 如果当前哈希下标存储的sel 不等于 即将插入的sel，则重新经过cache_next方法 即哈希冲突算法，重新进行哈希计算，得到新的下标，再去对比进行存储

• cache_hash：哈希算法

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask; // 通过sel & mask（mask = cap -1）
}

• cache_next：哈希冲突算法

#if __arm__  ||  __x86_64__  ||  __i386__
// objc_msgSend has few registers available.
// Cache scan increments and wraps at special end-marking bucket.
#define CACHE_END_MARKER 1
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask; //（将当前的哈希下标 +1） & mask，重新进行哈希计算，得到一个新的下标
}

#elif __arm64__
// objc_msgSend has lots of registers available.
// Cache scan decrements. No end marker needed.
#define CACHE_END_MARKER 0
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask; //如果i是空，则为mask，mask = cap -1，如果不为空，则 i-1，向前插入sel-imp
}

小结：方法的缓存是以散列表的形式进行存储的，所以它是无序的，当 当前缓存数量 超过 散列表 总存储空间的四分之三时，散列表的存储空间以2倍的原始大小进行扩容，并抹除已有缓存。存储缓存时，是通过遍历当前散列表的所有已存储方法，如果散列表中已有缓存，则不存储并结束遍历，如果遍历完毕依然没有找到该方法，则将该方法存入散列表