oc-底层原理分析之Cache_t

在类的结构分析一文中我们探索了类的底层定义，其中的属性Cache_t我们并没有深入研究，这一篇文章我们来深入探索一下Cache_t

注意：以下的源码解读都是在mac电脑上运行，也就是说基于x86的结构，请记住这一点

什么是Cache_t

要搞清楚什么是Cache_t和Cache_t用来做什么，我们先看看在objc源码中，Cache_t的定义

struct cache_t {
    explicit_atomic<struct bucket_t *> _buckets;
    explicit_atomic<mask_t> _mask;
    uint16_t _occupied;

public:
    static bucket_t *emptyBuckets();
    
    struct bucket_t *buckets();
    mask_t mask();
    mask_t occupied();
    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    void initializeToEmpty();
    //部分代码已略
}

通过源码我们看到Cache_t结构体中定义了三个属性：

1. _buckets
2. _mask
3. _occupied

但是我们现在并不知道这三个属性用来做什么，要搞清楚这三个属性的作用，我们通过一个例子来探索一下

先定义一个WPerson类：

@interface WPerson : NSObject

@property (nonatomic, copy) NSString *lgName;
@property (nonatomic, strong) NSString *nickName;

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

@implementation WPerson
- (void)sayHello{
    NSLog(@"WPerson say : %s",__func__);
}

- (void)sayCode{
    NSLog(@"WPerson say : %s",__func__);
}

- (void)sayMaster{
    NSLog(@"WPerson say : %s",__func__);
}

- (void)sayNB{
    NSLog(@"WPerson say : %s",__func__);
}

+ (void)sayHappy{
    NSLog(@"WPerson say : %s",__func__);
}
@end

现在我们创建一个WPerson对象，然后调用sayHello方法：

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        WPerson *p  = [WPerson alloc];
        Class pClass = [WPerson class];
        [p sayHello];

        NSLog(@"%@",pClass);
    }
    return 0;
}

Cache_t 结构探索

先找到pClass的首地址：

• x/4gx pClass：以16进制形式打印出pClass地址

  0x100002288: 0x0000000100002260 0x0000000100334140
  0x100002298: 0x00000001006f4050 0x0001802400000003
  

  pClass首地址为：0x100002288

• 通过在类结构分析一文中我们得知了类的结构如下：

  struct objc_class : objc_object {
      // 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
  
      class_rw_t *data() const {
          return bits.data();
      }
  }
  

  由于isa和superclass都占用8个字节，所以我们要访问到cache，我们需要将首地址偏移16字节，所以：

  (lldb) p (cache_t *)0x100002298
  (cache_t *) $1 = 0x0000000100002298
  

  我们得到了cache的地址

• 访问cache.buckets(),我们知道_buckets是一个数组，所以我们先访问第一个值看存储的是什么

  (lldb) p $2.buckets()[0]
  (bucket_t) $3 = {
  _sel = {
  std::__1::atomic<objc_selector *> = ""
  }
  _imp = {
  std::__1::atomic<unsigned long> = 11912
  }
  

}
```
我们得到一个bucket_t结构，我们再看看bucket_t的源码：

```c
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

public:
    inline SEL sel() const { return _sel.load(memory_order::memory_order_relaxed); }

    inline IMP imp(Class cls) const {
        uintptr_t imp = _imp.load(memory_order::memory_order_relaxed);
        if (!imp) return nil;
#if CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_PTRAUTH
        SEL sel = _sel.load(memory_order::memory_order_relaxed);
        return (IMP)
            ptrauth_auth_and_resign((const void *)imp,
                                    ptrauth_key_process_dependent_code,
                                    modifierForSEL(sel, cls),
                                    ptrauth_key_function_pointer, 0);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_ISA_XOR
        return (IMP)(imp ^ (uintptr_t)cls);
#elif CACHE_IMP_ENCODING == CACHE_IMP_ENCODING_NONE
        return (IMP)imp;
#else
#error Unknown method cache IMP encoding.
#endif
    }

//部分代码已略去
};
```
我们看到`bucket_t`有两个属性`_sel`和`_imp`，看到这里是不是很熟悉，但是别急，我们先来打印一下sel的值

• 打印sel

  (lldb) p $3.sel()
  (SEL) $4 = "sayHello"
  

我们看到结果打印出了我们刚刚调用的方法sayHello，我们如果多调用几个方法，这里可以打印出多个方法
所以我们得出结论：

cache_t用来缓存类的sel以及imp

既然我们知道了cache_t用来缓存类的方法，那么还有一些疑问：

1. 缓存的策略是什么呢？
2. 如果空间不足，如何对空间进行扩容？
3. 缓存又是怎么读取的？（这部分内容接下来会补上）

带着这三个疑问，我们开始探索

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

    // Use the cache as-is if it is less than 3/4 full
    mask_t newOccupied = occupied() + 1;
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE;
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) { // 4  3 + 1 bucket cache_t
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 扩容两倍 4
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);  // 内存 库容完毕
}

从这里我们可以看到：

1. 如果buckets还未初始化，则会先调用reallocate()方法对buckets进行初始化，初始的存储大小为INIT_CACHE_SIZE我们看到INIT_CACHE_SIZE定义为(1 << INIT_CACHE_SIZE_LOG2)也就是4
2. 如果本次插入后所占用的空间小于总空间的3/4时，则直接进行数据插入
3. 如果本次插入后所占用的空间>=3/4，则需要对总空间进行扩容，如何进行的扩容，在cache_t扩容部分会有讲解

我们知道了在_buckets中存储的是bucket_t类型，当数据insert的时候，都会创建一个bucket_t变量

mask

_buckets是一个数组，如果我们要通过某个方法的sel去查找imp，我们怎么查找呢？我们大概率会想去去遍历_buckets，但是这样的效率是低下的，每一次的方法查找都会遍历整个缓存，那么有没有什么办法能不遍历呢？

我们来看看源码中采用的方式，我们在源码中能看到这样一个方法：

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}

mask传入的是mask_t m = capacity - 1;也就是当前的容量 - 1。通过和mask相与，我们得到的数字肯定是小于等于mask的，通过这种方式就可以得到sel和数组index的对应关系，在查找的时候就可以直接通过sel得到数组对应的index，不再需要遍历整个数组

但是你可能有一个疑问，这样不会出现编码的冲突吗？不同的sel会不会得到同一个index呢？答案是会的，源码中也解决了这个问题

bucket_t *b = buckets();
mask_t m = capacity - 1;
mask_t begin = cache_hash(sel, m);
mask_t i = begin;
    
do {
    if (fastpath(b[i].sel() == 0)) {
        incrementOccupied();
        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));

如果index存在了，就会调用cache_next重新生成一个index来存储，直到找到合适的位置

cache_t扩容

capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;  // 扩容两倍
if (capacity > MAX_CACHE_SIZE) {
    capacity = MAX_CACHE_SIZE;
}
reallocate(oldCapacity, capacity, true);  // 内存 库容完毕

我们可以看到扩容的原则是当前容量的两倍，并且扩容时，重新调用reallocate将原来的数据清空。也就是说扩容后，原来的数据将不存在，重新调用原有方法的时候才会重新进行缓存，如果你这时候去打印cache中的所有数据，得到的并不是你当前调用的所有方法，也能得到验证