在OC底层原理05 - isa与类关联的原理和OC底层原理06 - 类 & 类结构分析中，分析了objc_class中isa和bits，这篇文章主要是分析objc_calss中的cache属性

cache初探

• 打开objc4源码， 搜索objc_class
  image.png
• 查看cache_t源码，发现分成了3个架构的处理，其中真机的架构中，mask和bucket是写在一起，目的是为了优化，可以通过各自的掩码来获取相应的数据
  • CACHE_MASK_STORAGE_OUTLINED表示运行的环境为模拟器或macOS
  • CACHE_MASK_STORAGE_HIGH_16表示运行环境为64位真机
  • CACHE_MASK_STORAGE_LOW_4表示运行环境为非64位真机

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED    // macOS、模拟器
    // explicit_atomic 显示原子性，目的是为了能够 保证 增删改查时 线程的安全性
    // 等价于 struct bucket_t * _buckets;
    // _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;

    // 掩码代码省略...    

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

    // 部分代码省略.....
};

• 查看bucket_t源码，同样分为两个版本，真机和非真机，不同的区别在于sel和imp的顺序不同

struct bucket_t {
private:
#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

cache_t缓存机制

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

在源码中查找

• 定义一个HLPerson类，并添加属性及方法，如下

@interface HLPerson : NSObject

@property (nonatomic, copy) NSString *name;
@property (nonatomic, copy) NSString *nickName;

- (void)instanceMethod1;
- (void)instanceMethod2;
- (void)instanceMethod3;
- (void)instanceMethod4;
- (void)instanceMethod5;
+ (void)classMethod;

@end

//.m
@implementation HLPerson

- (void)instanceMethod1 {
    NSLog(@"%s",__func__);
}
- (void)instanceMethod2 {
    NSLog(@"%s",__func__);
}
- (void)instanceMethod3 {
    NSLog(@"%s",__func__);
}
- (void)instanceMethod4 {
    NSLog(@"%s",__func__);
}
- (void)instanceMethod5 {
    NSLog(@"%s",__func__);
}

+ (void)classMethod {
    NSLog(@"%s",__func__);
}

@end

• 在main中定义HLPerson类的对象person，并调用其中的3个实例方法，在person调用第一个方法处添加断点，运行代码
  image.png
• 程序运行至断点处，lldb调试
  image.png
  从lldb打印结果来看，sel、imp、mask、occupied等值出现了变化，由上图可知，在没有执行方法调用时，此时的cache是没有缓存的，执行了一次方法调用，cache中就有了一个缓存，即调用一次方法就会缓存一次方法。
  【验证】使用machoView打开target的可执行文件，在方法列表中查看其imp的值是否是一致的，如下所示，发现是一致的，所以打印的这个sel-imp就是HLPerson的实例方法
  
  image.png
• 点击step over，程序再执行一步，此时-[HLPerson instanceMethod2]已经执行，我们再看下此时cache的情况
  
  image.png
  
  发现获取到的buckets中sel和之前是相同的，此时想要获取第二个sel，应该通过指针平移获取
  
  image.png
  
  这样虽然也能获取到数据，但是操作过程略显繁琐，所以我们换一种方式凡是进行探索

脱离源码环境

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

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

struct hl_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct hl_cache_t {
    struct hl_bucket_t * _buckets;
    mask_t _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct hl_class_data_bits_t {
    uintptr_t bits;
};

struct hl_objc_class {
    Class ISA;
    Class superclass;
    struct hl_cache_t cache;             // formerly cache pointer and vtable
    struct hl_class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
};

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        HLPerson *person  = [HLPerson alloc];
        Class pClass = [HLPerson class];  
        [person instanceMethod1];
        [person instanceMethod2];
        [person instanceMethod3];
        [person instanceMethod4];
      
        struct hl_objc_class *hl_pClass = (__bridge struct hl_objc_class *)(pClass);
        NSLog(@"%hu - %u", hl_pClass->cache._occupied, hl_pClass->cache._mask);
        for (mask_t i = 0; i<hl_pClass->cache._mask; i++) {
            // 打印获取的 bucket
            struct hl_bucket_t bucket = hl_pClass->cache._buckets[i];
            NSLog(@"%@ - %p", NSStringFromSelector(bucket._sel), bucket._imp);
        }
    }
    return 0;
}

运行项目，结果如下

image.png

• 1、_mask是什么？
• 2、_occupied是什么？
• 3、_occupied和_mask随什么变化？
• 4、_bucket数据为什么会有丢失的情况？
• 5、方法存储顺序是顺序存储还是有别的规则？

带着上述的这些疑问，下面来进行cache底层原理的探索

cache_t底层原理分析

• 首先，从cache_t中的_mask属性开始分析，找cache_t中引起变化的函数，发现了incrementOccupied()函数
  
  image.png
  跳转至incrementOccupied()
  image.png
• 在源码中全局搜索incrementOccupied()函数，发现只在cache_t的insert方法有调用
  
  image.png
• insert方法，理解为cache_t的插入，而cache中存储的就是sel-imp，所以cache的原理从insert方法开始分析，以下是cache原理分析的流程图
  
  image.png
• 全局搜索->insert方法，发现只有cache_fill方法中的调用符合
  
  image.png
• 全局搜索cache_fill，发现在写入之前，还有一步操作，即cache读取，即查找sel-imp，如下所示
  
  image.png
  可以看到在cache写入流程前有一个读取流程，读取流程将在下篇文章中分析探讨，本文还是回到insert写入上

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

    // 原occupied计数+1
    mask_t newOccupied = occupied() + 1;
    // 进入capacity()查看： return mask() ? mask()+1 : 0;
    // 就是当前mask有值就+1，否则设置初始值0
    unsigned oldCapacity = capacity(), capacity = oldCapacity;

    // 当前缓存是否为空
    if (slowpath(isConstantEmptyCache())) {
        // Cache 是只读的，所以只能替换而不能修改
        // 如果为空，就给空间设置初始值4(进入INIT_CACHE_SIZE查看，可以发现就是1<<2，就是二进制100，十进制为4)
        if (!capacity) capacity = INIT_CACHE_SIZE;

        // 创建新空间（第三个入参为false，表示不需要释放旧空间）
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }

    // CACHE_END_MARKER 就是 1
    // 如果当前计数 + 1 <= 空间的 3/4，表示空间够用，不需要空间扩容，不作处理
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) {
        // Cache is less than 3/4 full. Use it as-is.
    }

    // 如果计数大于3/4， 就需要进行扩容操作
    else {
        // 如果空间存在，就2倍扩容。 如果不存在，就设为初始值4
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;

        // 防止超出最大空间值（2^16 - 1）
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }

        // 创建新空间（第三个入参为true，表示需要释放旧空间）
        reallocate(oldCapacity, capacity, true);
    }

    // 读取现在的buckets数组
    bucket_t *b = buckets();
    // 新的mask值(当前空间最大存储大小 - 1)
    mask_t m = capacity - 1;
    // 使用hash计算当前函数的位置(内部就是sel & m， 就是取余操作，保障begin值在m当前可用空间内)
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;

    do {
        // 如果当前位置为空，直接写入存储
        if (fastpath(b[i].sel() == 0)) {
            // Occupied计数+1
            incrementOccupied();
            // 将sel和imp与cls关联起来并写入内存中
            b[i].set<Atomic, Encoded>(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;
        }

        // 程序运行到这步，代表位置有值，且储存sel不是当前sel，那么再次使用哈希算法找下一个空位置去写入
        // 需要注意的是，cache_next内部有分支： 
        // 如果是arm64真机环境： 从最大空间位置开始，依次-1往回找空位
        // 如果是arm旧版真机、x86_64电脑、i386模拟器： 从当前位置开始，依次+1往后找空位。不能超过最大空间。
        // 因为当前空间是没超出mask最大空间的，所以一定有空位置可以放置的。
    } while (fastpath((i = cache_next(i, m)) != begin));

    // 各种错误处理
    cache_t::bad_cache(receiver, (SEL)sel, cls);
}

• 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__
#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__
#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
}

reallocate方法分析

该方法，在第一次创建以及两倍扩容时，都会调用，其作用为开辟新空间，释放旧空间，源码实现如下

ALWAYS_INLINE
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方法分析

其作用为创建新空间大小的buckets数组，此时的buckets是一个临时变量，源码如下

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

setBucketsAndMask方法分析

将临时的bucket存入缓存中

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    // 如果是macOS或者模拟器环境，分开存储 bucket_t 和 mask_t
    // 将 _occupied 置为 0
#ifdef __arm__
    mega_barrier();
    _buckets.store(newBuckets, memory_order::memory_order_relaxed);    
    mega_barrier();
    _mask.store(newMask, memory_order::memory_order_relaxed);
    _occupied = 0;
#elif __x86_64__ || i386
    _buckets.store(newBuckets, memory_order::memory_order_release);
    _mask.store(newMask, memory_order::memory_order_release);
    _occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}

#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    // 创建两个临时变量存储 newBuckets 和 newMask
    uintptr_t buckets = (uintptr_t)newBuckets;
    uintptr_t mask = (uintptr_t)newMask;
    
    // 判断所要存储的数据是否小于最大值
    ASSERT(buckets <= bucketsMask);
    ASSERT(mask <= maxMask);
    
    // static constexpr uintptr_t maskShift = 48;
    // 将 newMask 存储在 高48位，newBuckets 存储在 低16位
    _maskAndBuckets.store(((uintptr_t)newMask << maskShift) | (uintptr_t)newBuckets, std::memory_order_relaxed);

    // 将 _occupied 置为 0
    _occupied = 0;
}

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

至此，cache_t的原理基本分析完成了，至于前文提及的几个问题，我们现在也有答案

疑问解答

1、_mask是什么？
_mask是指掩码数据，用于在哈希算法或者哈希冲突算法中计算哈希下标，_mask等于capacity - 1
2、_occupied是什么？

• _occupied表示哈希表中sel-imp的占用大小 (即可以理解为分配的内存中已经存储的sel-imp的个数)，
• init会导致_occupied变化
• 属性赋值，也会隐式调用，导致_occupied变化
• 方法调用，导致_occupied变化

3、_occupied和_mask随什么变化？
_occupied为当前缓存的方法个数，_mask等于总容量-1。当调用一个未缓存的方式时_occupied + 1，如果新的_occupied再+1不小于总容量的3/4时，例如总容量为4，调用第3个未缓存方法时，总容量为8，调用第6个未缓存方法时，就需要对cache的内存进行两倍扩容，此时_mask被重新赋值，_occupied重置为0
4、_bucket数据为什么会有丢失的情况
在扩容时，是将原有的内存全部清除了，再重新申请了内存导致的
5、方法存储顺序是顺序存储还是有别的规则？
因为sel-imp的存储是通过哈希算法计算下标的，其计算的下标有可能已经存储了sel，所以又需要通过哈希冲突算法重新计算哈希下标，所以导致下标是随机的，并不是固定的