iOS底层探索值cache_t缓存

通过之前的探索iOS底层探索之类&类的结构分析，知道了类中含有
Class isa、Class superClass、cache_t cache，class_data_bits_t bits。
并且前面章节iOS 底层探索之isa结构分析和iOS底层探索之类&类的结构分析分别对isa和bits进行了分析，由于superClass的继承链在isa中也进行了分析，接下来重点分析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;
    
    // How much the mask is shifted by.
    static constexpr uintptr_t maskShift = 48;
    
    // Additional bits after the mask which must be zero. msgSend
    // takes advantage of these additional bits to construct the value
    // `mask << 4` from `_maskAndBuckets` in a single instruction.
    static constexpr uintptr_t maskZeroBits = 4;
    
    // The largest mask value we can store.
    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
    
    // The mask applied to `_maskAndBuckets` to retrieve the buckets pointer.
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
    
    // Ensure we have enough bits for the buckets pointer.
    static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers.");
#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;

    static constexpr uintptr_t maskBits = 4;
    static constexpr uintptr_t maskMask = (1 << maskBits) - 1;
    static constexpr uintptr_t bucketsMask = ~maskMask;
#else
#error Unknown cache mask storage type.
#endif
    
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;
省略部分代码...
};

首先分析：

//如果是macOS、模拟器 --
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
//如果64位 真机
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
//如果不是64位 真机
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
#else
#error Unknown cache mask storage type.
#endif

这样我们就可以很清楚了

如果是macOS或者模拟器

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

如果64位真机

explicit_atomic<uintptr_t> _maskAndBuckets;
mask_t _mask_unused;
uint16_t _flags;
uint16_t _occupied;
//静态变量----掩码
// How much the mask is shifted by.
static constexpr uintptr_t maskShift = 48;
    
// Additional bits after the mask which must be zero. msgSend
// takes advantage of these additional bits to construct the value
// `mask << 4` from `_maskAndBuckets` in a single instruction.
static constexpr uintptr_t maskZeroBits = 4;
    
// The largest mask value we can store.
static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
    
// The mask applied to `_maskAndBuckets` to retrieve the buckets pointer.
static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
    
// Ensure we have enough bits for the buckets pointer.
static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers.");

如果真机非64位

explicit_atomic<uintptr_t> _maskAndBuckets;
mask_t _mask_unused;
uint16_t _flags;
uint16_t _occupied;
//静态变量--掩码
static constexpr uintptr_t maskBits = 4;
static constexpr uintptr_t maskMask = (1 << maskBits) - 1;
static constexpr uintptr_t bucketsMask = ~maskMask;

bucket_t的结构

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
    //方法等其他部分省略
}

根据的分析可以将结构图做出如下图所示：

整体结构如图所示

首先需要objc781的源码工程，需要自己配置的可参考cooci老师的GitHub
然后我们创建LGPerson类，申明一些方法，如下代码

@interface LGPerson : NSObject
@property (nonatomic, copy) NSString *lgName;
@property (nonatomic, strong) NSString *nickName;

- (void)sayHello;

- (void)sayCode;

- (void)sayMaster;

- (void)sayNB;

+ (void)sayHappy;

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

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

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

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

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

通过一系列的lldb调试：

lldb调试大法

lldb调试后发现，
当没有执行任何方法时：_occupied = 0，_mask = 0;
执行第一个方法时：_occupied = 1，_mask = 3;
执行第二个方法时：_occupied = 2，_mask = 3;
执行第三个方法时：_occupied = 1，_mask = 7,并且buckets里面找不到前面2个已经执行的方法。

Cache_t脱离源码环境分析

接下来，仿造Cache_t的结构，脱离源码环境进行探索：

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

struct lg_bucket_t {
    SEL _sel;
    IMP _imp;
};

struct lg_cache_t {
    struct lg_bucket_t * _buckets;
    mask_t _mask;
    uint16_t _flags;
    uint16_t _occupied;
};

struct lg_class_data_bits_t {
    uintptr_t bits;
};

struct lg_objc_class {
    Class ISA;
    Class superclass;
    struct lg_cache_t cache;             // formerly cache pointer and vtable
    struct lg_class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
};
int main(int argc, const char * argv[]) {
    @autoreleasepool {
        LGPerson *p  = [LGPerson alloc];
        Class pClass = [LGPerson class];  // objc_clas
        [p say1];
        [p say2];
        [p say3];
        [p say4];

        struct lg_objc_class *lg_pClass = (__bridge struct lg_objc_class *)(pClass);
        NSLog(@"%hu - %u",lg_pClass->cache._occupied,lg_pClass->cache._mask);
        for (mask_t i = 0; i<lg_pClass->cache._mask; i++) {
            // 打印获取的 bucket
            struct lg_bucket_t bucket = lg_pClass->cache._buckets[i];
            NSLog(@"%@ - %p",NSStringFromSelector(bucket._sel),bucket._imp);
        }

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

输出的结果为：

2020-09-20 15:51:33.905822+0800 003-cache_t脱离源码环境分析[3786:143964] LGPerson say : -[LGPerson say1]
2020-09-20 15:51:33.906304+0800 003-cache_t脱离源码环境分析[3786:143964] LGPerson say : -[LGPerson say2]
2020-09-20 15:51:33.906372+0800 003-cache_t脱离源码环境分析[3786:143964] LGPerson say : -[LGPerson say3]
2020-09-20 15:51:33.906437+0800 003-cache_t脱离源码环境分析[3786:143964] LGPerson say : -[LGPerson say4]
2020-09-20 15:51:33.906486+0800 003-cache_t脱离源码环境分析[3786:143964] 2 - 7
2020-09-20 15:51:33.906620+0800 003-cache_t脱离源码环境分析[3786:143964] say4 - 0xb9a8
2020-09-20 15:51:33.906661+0800 003-cache_t脱离源码环境分析[3786:143964] (null) - 0x0
2020-09-20 15:51:33.906716+0800 003-cache_t脱离源码环境分析[3786:143964] say3 - 0xb9d8
2020-09-20 15:51:33.906754+0800 003-cache_t脱离源码环境分析[3786:143964] (null) - 0x0
2020-09-20 15:51:33.906782+0800 003-cache_t脱离源码环境分析[3786:143964] (null) - 0x0
2020-09-20 15:51:33.906809+0800 003-cache_t脱离源码环境分析[3786:143964] (null) - 0x0
2020-09-20 15:51:33.906836+0800 003-cache_t脱离源码环境分析[3786:143964] (null) - 0x0
Program ended with exit code: 0

从上面我可以看出，我们调用了 4个函数方法，但在 buckets里面只存储了2个方法，并且顺序有点问题，并不是按照调用顺序进行存放的。我们带着问题在继续探。

cache_t底层原理分析

当对象调用函数时，_occupied的值会发生变化，我们以此为突破口，在源码中的cache_t发现incrementOccupied方法。然后，查看什么时候调用该函数。
在void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)方法中调用了该函数。

void cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)
{
    // Use the cache as-is if it is less than 3/4 full
    mask_t newOccupied = occupied() + 1;
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    // 1. 如果Cache 是空的话，会初始化一个 4 个字节的空间
    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)) {
        // Cache is less than 3/4 full. Use it as-is.
        // 2. newOccupied + CACHE_END_MARKER <= capacity / 4 * 3 ，直接插入
    }
    else {
        // 3. 否则会扩容
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);
    }
    // 4. 初始化一个指针数组
    bucket_t *b = buckets();
    // 5. 设置掩码为 capacity - 1
    mask_t m = capacity - 1;
    // 6. 根据sel 计算 hash 值
    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 {
        // 7. 当前 插槽 取到 的sel 地址为0， 那么插入新的值
        if (fastpath(b[i].sel() == 0)) {
            // 8. 增加占用字段并且插入
            incrementOccupied();
            b[i].set<Atomic, Encoded>(sel, imp, cls);
            return;
        }
        // 8. 多线程做的判断
        if (b[i].sel() == sel) {
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }
        // 9. 如果当前位置已有值，那么就找下一个位置
    } while (fastpath((i = cache_next(i, m)) != begin));
}

// 10. hash 算法, 保证不会越界
static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}

//11.哈希冲突算法
#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
}

cache缓存的初始内存为4，如果缓存占用量小于等于3/4，则不作任何处理，如果缓存占用量超过3/4，则需要进行两倍扩容以及重新开辟空间。

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

如果有旧的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);

    _garbage_make_room ();//创建垃圾回收空间
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    garbage_refs[garbage_count++] = data;将sel-imp存在后置的位置
    cache_collect(false);//垃圾回收，清理旧的bucket
}

至此可以分析出问题的答案：

_occupied:表示当前buckets()里面的bucket数量。
_mask等于buckets的capacity - 1。
*bucket存放的位置是由sel&capacity - 1决定的，与方法的调用顺序无关，是存储在哈希表中，是无序的。
当buckets的_occupied> capacity * 3/4时，buckets会进行扩容，会对buckets进行重新开辟内存，导致之前存放的bucket会丢失。所以会找不到bucket里面的sel和imp。