iOS底层之cache_t探究

我们在iOS底层之类的结构分析分析了类的内部结构，而类的C/C++底层实际是objc_class结构体，其中包含了4个成员。

类的底层结构
那么这一节我们来探究cache_t——类的方法缓存的真面目，存储了什么，怎么存储的。

cache_t的结构

我们从cache_t的源码看：

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    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;
}
#endif
    
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;
  // ......
//省略了其他静态成员和方法

这里的系统架构的判断条件宏定义是：

#define CACHE_MASK_STORAGE_OUTLINED 1
#define CACHE_MASK_STORAGE_HIGH_16 2
#define CACHE_MASK_STORAGE_LOW_4 3

#if defined(__arm64__) && __LP64__
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16
#elif defined(__arm64__) && !__LP64__
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_LOW_4
#else
#define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_OUTLINED
#endif

可以看到
CACHE_MASK_STORAGE_HIGH_16——真机64位架构
CACHE_MASK_STORAGE_LOW_4——真机非64位架构
CACHE_MASK_STORAGE_OUTLINED——非真机即macOS环境

在macOS环境和真机64位环境下，它们的区别是：

cache_t结构

cache_t的成员主要包括了:

1. macOS环境下:
   _buckets：桶，包含了sel方法编号、imp函数指针地址。原子安全的。
   _mask：掩码。原子安全的。
2. 64位真机环境下 :
   _maskAndBuckets：将_mask和_buckets放在一起。也就是存储_mask & _buckets的结果。原子安全的。

公共成员：
_mask_unused：未使用的掩码，全局搜索后发现，这个成员并没有被使用，猜测可能是没开源出来或者是这部分还未写完。
_flags：位置标识。
_occupied：已占用的。

1.成员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<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
}

可以看到存储了_imp和_sel，它们都是原子安全的，区别是，它们的顺序不一样。在64位环境下，imp放在前面对arm64e架构的ptrauth更好，而其他环境下，sel放在前面对armv7*、i386、 x86_64架构更优。

那么我们知道了bucket_t的结构，就可以通过项目去查看下我们实例的对象的方法编号和实现了。

定义一个类，包括属性和实例方法、类方法。

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

- (void)sayHello;

- (void)sayWorld;

- (void)sayMaster;

- (void)sayNB;

+ (void)sayHappy;

@end

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

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

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

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

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

在main.m文件中

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


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

在[p sayHello];设置一个断点，运行，并打印调试BKPerson类的cache_t信息：

这一步通过打印类的内存首地址，偏移16个字节（isa和superclass成员各占了8字节）后得到的内存位置就是cache_t的信息。打印可以看到，这时候只初始化了类的实例对象，还没有执行实例方法。_buckets里的_sel=null，_imp=0，而且_mask=0，_occupied=0。

我们将断点跳到下一行代码。再打印cache_t：

可以看到这时候的cache_t里面是：_buckets里的_sel=""，_imp=11928，而且_mask=3，_occupied=1。而这个变数是因为我们执行了sayHello这个方法。

难道真的是因为执行了sayHello吗，我不信？
为了验证这一点，那么可以打印下_buckets的信息：

⚠️这里要注意的是：如果直接使用打印的信息里的成员去打印，像图上那样的，是会取不到的。这时候我们可以查看cache_t的定义，看看有没有相关的方法。

struct cache_t {
    struct bucket_t *buckets();
    mask_t mask();
    mask_t occupied();
}

可以找到以上方法，而如果要打印sel和imp，则需要查看bucket_t的定义:

struct bucket_t {
    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
    }
}

这时再通过以上方法打印：

可以百分百确定，由于执行到了sayHello方法，所以cache_t存储的信息发生了改变。

进一步验证，我们把断点跳到下一行。执行了sayWorld方法。

可以看到这时的_occupied=2，但是我们继续用之前的方式打印sel和imp，却还是只能打印出sayHello，而sayWorld没看到，但是通过成员名_buckets可以确定这是一个集合类型。

那么问题是，如何打印出_buckets这个集合里的所有元素？

这里有两种方式：
第一种：使用数组下标的方式访问元素

既然我们知道buckets是个数组，那么可以用下标方式，取出第0个、第1个元素，而打印第1个元素，可以得到sayWorld的信息。

第二种：使用地址偏移，访问集合元素

我们知道，对于一个数组，我们可以将数组指针+下标数，之后对其*取值，得出元素。比如，这里sayWorld是第二个元素，则对buckets数组指针，进行+1，之后用*整体取值，可以得出sayWorld元素。

可以发现，我们现在是在源码环境，而每次打印值都需要$取变量，很麻烦。那我们能在日常开发环境中进行调试吗？
答案是肯定的。
脱离源码环境，我们可以模拟底层的类型结构，一样可以调试。

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

struct my_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct my_cache_t {
    struct my_bucket_t * _buckets;
    mask_t _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct my_class_data_bits_t {
    uintptr_t bits;
};

struct my_objc_class {
    Class ISA;
    Class superclass;
    struct my_cache_t cache;             // formerly cache pointer and vtable
    struct my_class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
};

我们只需要取我们需要的成员，继承的关系也可以不要了。而这里需要注意的是：由于objc_class是继承于objc_object，也就继承了isa成员，所以我们去掉了继承的关系后，就要加上isa成员。否则，在打印类的cache_t的相关信息时，就会打印不到正确的值。

之后就可以打印类的方法sel和imp了。

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        BKPerson *p  = [BKPerson alloc];
        Class pClass = [BKPerson class];  // objc_clas
        [p eat1];
        [p eat2];
        [p eat3];
        [p eat4];
        
        struct my_objc_class *my_pClass = (__bridge struct my_objc_class *)(pClass);
        NSLog(@"%hu - %u",my_pClass->cache._occupied,my_pClass->cache._mask);
        for (mask_t i = 0; i<my_pClass->cache._mask; i++) {
            // 打印获取的 bucket
            struct my_bucket_t bucket = my_pClass->cache._buckets[I];
            NSLog(@"%@ - %p",NSStringFromSelector(bucket._sel),bucket._imp);
        }

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

但是当我们只执行eat1和eat2，和执行eat1～eat4，对比打印信息，可以看到：

可以看到_occupied都是2，而_mask从2变成7，而且后一张图的buckets里打印的eat1和eat2不见了，而且eat3和eat4的顺序，是错乱的。

提出问题：_occupied和_mask是什么，为什么_occupied都是2，_mask从2变成7，为什么有些方法缺失了，为什么顺序混乱？

可以知道，产生变化是由于函数的调用，而非成员属性发生变化。
那么从源码查找cache_t，主要包含了以下的函数：

struct cache_t {
    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();

    unsigned capacity();
    bool isConstantEmptyCache();
    bool canBeFreed();
}

点入occupied()

mask_t cache_t::occupied() 
{
    return _occupied;
}

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

可以看到occupied()是一个get方法，incrementOccupied()是对_occupied的递增操作。这就是重点所在。

全局搜索incrementOccupied()的调用，可以看到在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);  // 内存 库容完毕
    }

    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    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();
            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_t::bad_cache(receiver, (SEL)sel, cls);
}

insert分析

mask_t newOccupied = occupied() + 1;：对occupied()加一。

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. 如果是初始化：

由于初始化的情况比较少，所以系统使用slowpath修饰条件以加快指令跳转，当isConstantEmptyCache()缓存为空的时候，也就是刚初始化时，if (!capacity) capacity = INIT_CACHE_SIZE;，给capacity赋初值为4。

    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2),

从上面宏知道INIT_CACHE_SIZE的值为4。
之后执行reallocate(oldCapacity, capacity, /* 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);
    }
}

reallocate这个函数里主要做的是：根据newCapacity开辟buckets内存，而setBucketsAndMask函数定义

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    // objc_msgSend uses mask and buckets with no locks.
    // It is safe for objc_msgSend to see new buckets but old mask.
    // (It will get a cache miss but not overrun the buckets' bounds).
    // It is unsafe for objc_msgSend to see old buckets and new mask.
    // Therefore we write new buckets, wait a lot, then write new mask.
    // objc_msgSend reads mask first, then buckets.

#ifdef __arm__
    // ensure other threads see buckets contents before buckets pointer
    mega_barrier();

    _buckets.store(newBuckets, memory_order::memory_order_relaxed);
    
    // ensure other threads see new buckets before new mask
    mega_barrier();
    
    _mask.store(newMask, memory_order::memory_order_relaxed);
    _occupied = 0;
#elif __x86_64__ || i386
    // ensure other threads see buckets contents before buckets pointer
    _buckets.store(newBuckets, memory_order::memory_order_release);
    
    // ensure other threads see new buckets before new mask
    _mask.store(newMask, memory_order::memory_order_release);
    _occupied = 0;
#else
#error Don't know how to do setBucketsAndMask on this architecture.
#endif
}

做了初始化的工作：根据_buckets和_mask进行内存初始化工作，_occupied设置为0。

2. 如果小于capacity的3/4时
fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)

#define CACHE_END_MARKER 1

可以看到这个宏定义为1，也就是fastpath大部分情况下是这个条件newOccupied+1<= capacity的3/4，则不执行任何语句。

3. 其他情况：也就是newOccupied+1>capacity的3/4
这时候则需要内存扩容：
capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;,如果capacity等于0，则给初始值4，否则，扩容为原来的两倍。
if (capacity > MAX_CACHE_SIZE) { capacity = MAX_CACHE_SIZE; }

    MAX_CACHE_SIZE_LOG2  = 16,
    MAX_CACHE_SIZE       = (1 << MAX_CACHE_SIZE_LOG2),

防止扩容后的capacity超出最大值，最大值为1左移16位。
之后重新梳理内存reallocate(oldCapacity, capacity, true);，要注意这里传入的第三个参数为true，所以会执行reallocate函数里的清理旧垃圾的代码。

if (freeOld) {
   cache_collect_free(oldBuckets, oldCapacity);
}

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

    _garbage_make_room ();
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    garbage_refs[garbage_count++] = data;
    cache_collect(false);
}

static void _garbage_make_room(void)
{
    static int first = 1;

    // Create the collection table the first time it is needed
    if (first)
    {
        first = 0;
        garbage_refs = (bucket_t**)
            malloc(INIT_GARBAGE_COUNT * sizeof(void *));
        garbage_max = INIT_GARBAGE_COUNT;
    }

    // Double the table if it is full
    else if (garbage_count == garbage_max)
    {
        garbage_refs = (bucket_t**)
            realloc(garbage_refs, garbage_max * 2 * sizeof(void *));
        garbage_max *= 2;
    }
}

enum {
    INIT_GARBAGE_COUNT = 128
};

作用：上面我们只是给capacity标记扩容了，那么内存也要相应扩容。

• _garbage_make_room
  初始时，first=1，将first = 0并且开辟128个指针类型字节大小的bucket_t类型指针，垃圾最大值为 128。这时候的capacity为4。
  如果表已经满了，也就是垃圾达到了128。重新开辟两倍原来的garbage_max大小的内存给bucket_t类型指针，也就是buckets。
  否则，则不执行任何代码。
• garbage_byte_size += cache_t::bytesForCapacity(capacity);
  将旧capacity容量加入整个垃圾容量里。
• garbage_refs[garbage_count++] = data;
  将这一次执行的方法缓存先置放在garbage_count下标的位置。

总结：前面就是根据capacity标记进行方法缓存空间的申请，不足则需要扩容。扩容时会将之前的缓存抹除掉，重新开辟双倍大小的空间。扩容之后可以直接开始存储了，不需要算法扫描是否有同样的方法缓存，更加快速。

回到insert方法。
下面

    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    mask_t begin = cache_hash(sel, m);
    mask_t i = begin;

mask_t m = capacity - 1;根据这一句，可以知道前面的mask就是capacity - 1，如果初始化的时候，那么mask=3，如果扩容后，就是4*2-1=7。

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

传入sel和mask的算法计算哈希表存储的位置。

运行断点调试，可以看到当执行sayMaster算出的key值为2，再手动传入sayHellow和sayWorld的sel之后，得出的key分别为0和1。

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

扫描第一个未使用的插槽，保证必定会有一个可用插槽，因为最小尺寸是4，而我们前面已经修改了为3/4就满了。
当扫描哈希表时，大多数情况下b[i].sel() == 0)成立，也就是空插槽，那么就对occupied加1。而

template<Atomicity atomicity, IMPEncoding impEncoding>
void bucket_t::set(SEL newSel, IMP newImp, Class cls)
{
    ASSERT(_sel.load(memory_order::memory_order_relaxed) == 0 ||
           _sel.load(memory_order::memory_order_relaxed) == newSel);

    // objc_msgSend uses sel and imp with no locks.
    // It is safe for objc_msgSend to see new imp but NULL sel
    // (It will get a cache miss but not dispatch to the wrong place.)
    // It is unsafe for objc_msgSend to see old imp and new sel.
    // Therefore we write new imp, wait a lot, then write new sel.
    
    uintptr_t newIMP = (impEncoding == Encoded
                        ? encodeImp(newImp, newSel, cls)
                        : (uintptr_t)newImp);

    if (atomicity == Atomic) {
        _imp.store(newIMP, memory_order::memory_order_relaxed);
        
        if (_sel.load(memory_order::memory_order_relaxed) != newSel) {
#ifdef __arm__
            mega_barrier();
            _sel.store(newSel, memory_order::memory_order_relaxed);
#elif __x86_64__ || __i386__
            _sel.store(newSel, memory_order::memory_order_release);
#else
#error Don't know how to do bucket_t::set on this architecture.
#endif
        }
    } else {
        _imp.store(newIMP, memory_order::memory_order_relaxed);
        _sel.store(newSel, memory_order::memory_order_relaxed);
    }
}

这个函数将类的sel和imp存储到缓存中。之后return跳出。
如果插槽不为空，则判断插槽里的sel和当前要存的sel是否是同一个，如果相同，就返回，不存储。
如果不相同，则执行while语句。如果cache表的下一个插槽的key不等于当前begin，则执行do代码块，如此循环扫描，直到找到插槽插入。

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

这是cache_next的算法。

总结：mask数值等于capacity - 1，使用cache_hash算法获得当前sel的在哈希表的begin开始扫描位置，如果begin位置的插槽为空则存储并返回，不为空则判断是否是同一个sel，相同则返回，不同则使用cache_next算法得到下一个扫描位置，跟当前begin比对，不是同个插槽，则继续循环上面的查找逻辑。

这样就可以解释上面的问题了。
问：_occupied和_mask是什么，为什么_occupied都是2，_mask从2变成7，为什么有些方法缺失了，为什么顺序混乱？

答：_occupied是占用的方法缓存数，_mask是缓存容量的capacity-1，_mask从2变成7是因为capacity初始值为4，容量扩容算法capacity*2，_mask就等于新的capacity-1等于7，而扩容会清理之前的缓存，导致了方法缺失，顺序混乱是因为通过哈希算法以sel为key存储导致。

cache_t的原理分析图如下

cache_t原理分析图