iOS 探索cache_t

前面我们探索类的时候，了解类的结构。并且有看到objc_class中包含cache属性是用来做方法缓存的，其是一个cache_t结构体，那cache_t内部又是什么样的？是如果做到换方法缓存呢？今天我们就来一探究竟。

一、 cache_t结构

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

...
}

这是我们前面了解到的objc_class的结构，主要包括以下：

• ISA：objc_class继承与objc_object，而objc_object中只有isa，所以这里的ISA实际上来自于objc_object，注释并不代表不存在，只是说明不是在这个地方。
• superclass：superclass 的类型依然是Class， 指向了类的父类。
• cache：来自于cache_t结构体，是方法列表的缓存，存储了最近使用的方法
• bits：来自于class_data_bits_t，存储了类更详细的信息，我们后面会探索

objc_class 是继承自 objc_object的，也就是说 类 也是一个对象。这也是万物皆对象的由来。因其继承自 objc_object ，自然默认就含有了objc_object的成员 isa。

接下来主角登场，我们进入cache_t中看下其结构，因为cache_t源码还是很多，我们提炼一下关键信息：

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    // 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
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
    // _maskAndBuckets stores the mask shift in the low 4 bits, and
    // the buckets pointer in the remainder of the value. The mask
    // shift is the value where (0xffff >> shift) produces the correct
    // mask. This is equal to 16 - log2(cache_size).
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;

查看cache_t的源码，发现分成了3个架构的处理，其中真机的架构中，mask和bucket是写在一起，目的是为了优化，可以通过各自的掩码来获取相应的数据：
这三个架构分别是：

• CACHE_MASK_STORAGE_OUTLINED:表示运行的环境 模拟器 或者 macOS

• CACHE_MASK_STORAGE_HIGH_16:表示运行环境是 64位的真机

• CACHE_MASK_STORAGE_LOW_4:表示运行环境是 非64位 的真机

虽然是三种架构，但是他们结构中都包含了：

image.png

_buckets中是bucket_t的集合，我们再看下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，原子性，保证安全
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
...
}

bucket_t同样分为两种类型：真机和非真机，但是他们都包含了：

• sel: 方法编号
• imp: 方法的函数指针

至此，我们总结下从objc_class到bucket_t的结构：

image.png

二、在cache中查找sel-imp

方式一：lldb调试

我们新建mac app项目，创建一个LPPerson类，并新建部分方法：

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

- (void)say1;

- (void)say2;

- (void)say3;

- (void)say4;

+ (void)say5;

@end

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

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

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

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

+ (void)say5{
    NSLog(@"LPPerson say : %s",__func__);
}

@end

并在main.m中创建person对象并调用方法：

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        LPPerson *p  = [LPPerson alloc];
        Class pClass = [LPPerson class];
        [p say1];
        [p say2];
        [p say3];


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

我们在[p say1];这里打上断点,进行如下调试：

(lldb) p/x pClass
(Class) $0 = 0x0000000100008298 LPPerson
(lldb) p (cache_t *)0x00000001000082a8
(cache_t *) $1 = 0x00000001000082a8
(lldb) p *$1
(cache_t) $2 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = {
      Value = 0x0000000100346460
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = {
      Value = 0
    }
  }
  _flags = 32804
  _occupied = 0
}
(lldb) p $2.buckets()
(bucket_t *) $3 = 0x0000000100346460
(lldb) p *$3
(bucket_t) $4 = {
  _sel = {
    std::__1::atomic<objc_selector *> = (null) {
      Value = (null)
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 0
    }
  }
}
(lldb) p $4.sel()
(SEL) $5 = <no value available>
(lldb) p $4.imp(pClass)
(IMP) $6 = 0x0000000000000000

cache属性的获取，需要通过pclass的首地址平移16字节，即首地址+0x10获取cache的地址

从源码的分析中，我们知道sel-imp是在cache_t的_buckets属性中（目前处于macOS环境），而在cache_t结构体中提供了获取_buckets属性的方法buckets()

获取了_buckets属性，就可以获取sel-imp了，这两个的获取在bucket_t结构体中同样提供了相应的获取方法sel()以及 imp(pClass)

可以看到，此时buckets中并没有数据，因为其内部没有sel和imp的存在
我们在[p say2]加上断点，并放开[p say1]的断点，并再次打印：

2020-09-19 15:20:45.571484+0800 KCObjc[18159:13023877] LPPerson say : -[LPPerson say1]
(lldb) p *$1
(cache_t) $7 = {
  _buckets = {
    std::__1::atomic<bucket_t *> = {
      Value = 0x0000000102070af0
    }
  }
  _mask = {
    std::__1::atomic<unsigned int> = {
      Value = 3
    }
  }
  _flags = 32804
  _occupied = 1
}

可以发现，_occupied从0变成了1，_mask 从0变为了3,
我们获取下$3.buckets()

(lldb) p $7.buckets()
(bucket_t *) $8 = 0x0000000101d04790
(lldb) p *$8
(bucket_t) $9 = {
  _sel = {
    std::__1::atomic<objc_selector *> = "" {
      Value = ""
    }
  }
  _imp = {
    std::__1::atomic<unsigned long> = {
      Value = 48824
    }
  }
}
(lldb) p $9.sel()
(SEL) $10 = "say1"
(lldb) p $9.imp()
(IMP) $11 = 0x0000000100003c20 (KCObjc`-[LPPerson say1])

从这一步，我们可以到，buckets中有了一个bucket_t，并且获取这个bucket_t中的sel和imp正是我们执行的say1方法。

方式二：模拟源码

lldb可能不是很直接，并且可能相对麻烦点，那么我们就模拟源码来实现一个cache_t，再观察下：
新建一个工程，同样使用刚才的LPPerson，在mian.m中模拟源码：

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

struct lp_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct lp_cache_t {
    struct lp_bucket_t * _buckets;
    mask_t _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct lp_class_data_bits_t {
    uintptr_t bits;
};

struct lp_objc_class {
    Class ISA;
    Class superclass;
    struct lp_cache_t cache;             // formerly cache pointer and vtable
    struct lp_class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
};


int main(int argc, const char * argv[]) {
    @autoreleasepool {
        LPPerson *p  = [LPPerson alloc];
        Class pClass = [LPPerson class];  // objc_clas
        [p say1];
       // [p say2];
       // [p say3];
       // [p say4];
         
        
        struct lp_objc_class *lp_pClass = (__bridge struct lp_objc_class *)(pClass);
        NSLog(@"%hu - %u",lp_pClass->cache._occupied,lp_pClass->cache._mask);
        for (mask_t i = 0; i<lp_pClass->cache._mask; i++) {
            // 打印获取的 bucket
            struct lp_bucket_t bucket = lp_pClass->cache._buckets[i];
            NSLog(@"%@ - %p",NSStringFromSelector(bucket._sel),bucket._imp);
        }

        
        NSLog(@"Hello, World!");
    }
    return 0;
}

我们先执行say1 一个方法，看下结果：

LPPerson say : -[LPPerson say1]
1 - 3
say1 - 0xb850
(null) - 0x0
(null) - 0x0
Hello, World!

再放开say2的注释，执行2个方法后，再看下结果：

LPPerson say : -[LPPerson say1]
LPPerson say : -[LPPerson say2]
2 - 3
say1 - 0xb858
say2 - 0xb808
(null) - 0x0
Hello, World!

再放开所有的注释，执行4个方法后，再看下结果：

LPPerson say : -[LPPerson say1]
LPPerson say : -[LPPerson say2]
LPPerson say : -[LPPerson say3]
LPPerson say : -[LPPerson say4]
2 - 7
say4 - 0xb9b8
(null) - 0x0
say3 - 0xb9e8
(null) - 0x0
(null) - 0x0
(null) - 0x0
(null) - 0x0
Hello, World!

通过上面的结果，我们可以发现几个问题：

• mask和occupied是什么？
• mask和occupied会有变化，为什么会变化？并且变化的没有规律。
• buckets中sel和imp并不是全部保存，有些已经执行过的方法，按理说应该要缓存，但是结果却没有。这是为什么？

接下来我们就来分析下

三、cache_t原理分析

查看cache_t源码，会发现这样的代码：

public:
    static bucket_t *emptyBuckets();
    
    struct bucket_t *buckets();
    mask_t mask();
    mask_t occupied();
    void incrementOccupied();

incrementOccupied()，函数名字面意思应该是增加occupied，进入函数内部：

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

果然，这里就是处理_occupied的增加的，再全局搜索下，看哪里用到这个方法

image.png

void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
...
    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));
...
}

那这里面应该就是负责往cache里面inser方法的地方了，我们接下来就重点分析下：

第一步、根据当前的缓存情况，并根据条件执行各种操作：

 // Use the cache as-is if it is less than 3/4 full
    ///1、获取当前的占用量
    mask_t newOccupied = occupied() + 1;  
    ///2、获取当前缓存的最大缓存量
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    ///3、判断当前cache是否为空
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        ///最大缓存量为空，则赋值为INIT_CACHE_SIZE == 4
        if (!capacity) capacity = INIT_CACHE_SIZE;
        ///开辟空间
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }  ///4、判断当前容量是否没有超过最大容量的3/4
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) {
        // Cache is less than 3/4 full. Use it as-is.
    }///5、判断当前容量超过最大容量的3/4，则需要扩容，新的容量为原来容量的2倍
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);
    }

具体步骤如下：

• 1、获取当前的占用量
• 2、获取当前缓存的最大缓存量
• 3、判断当前cache是否为空
  1)、最大缓存量为空，则赋值为INIT_CACHE_SIZE == 4

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

INIT_CACHE_SIZE = INIT_CACHE_SIZE_LOG2左移1位，INIT_CACHE_SIZE_LOG2= 2，左移1位即为4。
2)、开辟空间

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    ///判断是够存在oldBuckets
    bucket_t *oldBuckets = buckets();
    ///  创建新的临时newBuckets
    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);
   //插入newBuckets
    setBucketsAndMask(newBuckets, newCapacity - 1);
    //释放oldBuckets
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
    }
}

• 4、判断当前容量是否没有超过最大容量的3/4
• 5、判断当前容量超过最大容量的3/4，则需要扩容，新的容量为原来容量的2倍,并扩大空间

 capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);

第二步、找到合适的bucket位置，存放sel和imp

    /// 1、初始化buckets
    bucket_t *b = buckets();
     /// 2、倒序查找，所以获取当前最大容量- 1
    mask_t m = capacity - 1;
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;
     ///3、利用hash算法，找bucket_t的位置，如果当前bucket_t的sel和要插入的不一样，则存储，反之，继续寻找位置。
    // 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();
            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));

具体步骤如下：

• 1、初始化buckets
• 2、获取当前缓存的最大缓存量,并利用哈希算法，算出一个开始位置
• 3、利用hash算法得到要插入的位置，如果当前bucket_t的sel和要插入的不一样，则存储，反之，继续寻找位置

1. 、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）
}

2. 、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
}

insert的流程我们可以总结如下流程图:

image.png

基于上面的分析，针对开始的问题，我们可以知道答案如下：
1、_mask和_occupied是什么？
_mask是指掩码数据，用于在哈希算法或者哈希冲突算法中计算哈希下标，其中mask 等于capacity - 1
_occupied表示哈希表中 sel-imp的占用大小 (即可以理解为分配的内存中已经存储了sel-imp的的个数)

2、为什么occupied 和mask会变化？

因为在cache初始化时，分配的空间是4个，随着方法调用的增多，当存储的sel-imp个数，即newOccupied + CACHE_END_MARKER（等于1）的和 超过 总容量的3/4,例如有4个时，当 occupied等于2时，就需要对cache的内存进行两倍扩容

3、bucket数据为什么会有丢失的情况？
原因是在扩容时，是将原有的内存全部清除了，再重新申请了内存导致的。并且因为sel-imp的存储是通过哈希算法计算下标的，其计算的下标有可能已经存储了sel，所以又需要通过哈希冲突算法重新计算哈希下标，所以导致下标是随机的，并不是固定的。

觉得不错记得点赞哦！听说看完点赞的人逢考必过，逢奖必中。ღ( ´･ᴗ･` )比心