IOS底层源码-cache_t分析

在之前的文章中分析了objc_class中isa和bits，这次分析的是objc_class中的cache属性，cache缓存_sel和_imp.在真机架构中mask和bucket写在一起，目的是为了优化，通过各自的的掩码来获取相应数据。

cache.png

查看cache_t源码，分成3个架构处理分别是

CACHE_MASK_STORAGE_OUTLINED 运行环境是模拟机和masOS
CACHE_MASK_STORAGE_HIGH_16 运行环境是64位的真机
CACHE_MASK_STORAGE_LOW_4 运行环境非64位的真机

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

查看bucket_t的源码，分为真机和非真机，却就是_sel和_imp的位置不同

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

cache中查找sel-imp

cache_t 查找sel-imp，有两种方式：

通过源码查找
脱离源码项目中查找

源码查找sel-imp

定义一个LGPerson类，定义属性和实例方法以及类方法

//.h文件
@interface LGPerson : NSObject
@property (nonatomic, copy) NSString *lgName;
@property (nonatomic, strong) NSString *nickName;

- (void)sayHello;

- (void)sayCode;

- (void)sayMaster;

- (void)sayNB;

+ (void)sayHappy;

@end

//.m文件
@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

在main函数定义的[p sayHello];打一个断点，通过lldb命令调试流程,打印cache信息

cache信息
在main函数定义的[p sayMaster];打一个断点，通过lldb命令调试流程

cache信息
从图中可以看出，cache属性的获取需要平移16位
sel-imp是cache_t的_buckets属性中（目前处于masOS环境），cache_t结构体中提供了获取_buckets属性的方法buckets()
通过 cache_t结构体提供的sel()和imp (cls)方法在_buckets属性中获取对应的数据

通过上图可知，没有调用方法的时候，cache是没有缓存的，调用了方法，cache中就有缓存即调用一次方法就会缓存一次

这里我们了解了如何打印sel-imp，但是我们还需要验证打印的信息是否正确
通过machoView打开可执行文件，在Function stars中查看imp，发现信息是一致的。

接着我们进行打印第二个sel，lldb命令流程

获取第二个sel-imp

第一个方法打印非常方便，但是第二个sel-imp就涉及到偏移的知识，可以IOS- 底层原理-类结构分析中提及多指针偏移，这里通过_buckets属性的首地址偏移即 p *($3+1)即可获取第二个方法的sel 和imp

脱离源码通过项目查找

重新创建一个没有源码的项目，讲源码中需要的cache相关的结构体，内容复制过来并修改名字。

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

LGPerson类中多定义几个方法，在main函数中调用

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];
         
        // _occupied  _mask 是什么  cup - 1
        // 会变化 2-3 -> 2-7
        // bucket 会有丢失  重新申请
        // 顺序有点问题  哈希
        
        // cache_t 底层原理
        // 线索 :
        
        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;
}

这里就有一个问题需要注意，就是objc_class的ISA是继承自objc_object,但是我们在拷贝过来的时候，去掉了objc_class继承关系，现在需要将这个属性明确，否则会出现下面的现象

如果将ISA加上就显示正常了

针对打印的结果，我们有几个疑惑

_mask和_occupied是什么？
bucket数据为什么会丢失，并且为什么打印乱序？
cache_t中的_ocupied为什么是从2开始？
为什么随着方法调用的增多，其打印的occupied 和 mask会变化

带着上述的疑问，进行cache底层探索

在cache_t_中的_mask属性开始分析，找cache_t中引起变化的函数，发现了incrementOccupied()函数
incrementOccupied()的具体实现

搜索incrementOccupied()查找源码，此时只有cache_t::insert调用了这个方法

insert方法可以理解为cache_t的插入，cache存储的就是sel-imp，因此从insert进行分析，下面是insert流程图

insert流程.png

全局搜索insert(),发现cache_fill符合条件调用

insert分析

源码实现如下

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

首先根据occupied的值计算出当前缓存占用量，当属性没有调用方法，occupied()为0，newOccupied为1

 mask_t newOccupied = occupied() + 1;

关于缓存占用计算，需要说明的是：

使用alloc申请空间，此时他就是一个对象，如果再调用init，也是会加入缓存那么occupied +1
调用方法时，也是会加入缓存即occupied增加，在原基础上增加
对象属性赋值是，会隐式调用set方法，occupied也会增加，在原基础上增加

缓存占用量判断

第一次创建，默认开辟4个

 if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE;
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }

如果缓存占用小于等于3/4，将不做处理

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

如果缓存占用大于3/4，会进行两倍扩容以及重新开辟空间

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

allocateBuckets 开辟空间

该方法，在第一次创建以及两倍扩容时，都会使用，其源码实现如下

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

allocateBuckets方法：向系统申请开辟内存，即开辟bucket，此时的bucket只是一个临时变量
setBucketsAndMask方法：将临时的bucket存入缓存中，此时的存储分为两种情况：
- 如果是真机，根据bucket和mask的位置存储，并将occupied占用设置为0
- 如果不是真机，正常存储bucket和mask，并将occupied占用设置为0
如果有旧的buckets，需要清理之前的缓存，即调用cache_collect_free方法，其源码实现如下

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

 *  _garbage_make_room方法：创建垃圾回收空间

如果是第一次，需要分配回收空间
如果不是第一次，则将内存段加大，即原有内存*2
cache_collect方法：垃圾回收，清理旧的bucket

bucket进行内部imp和sel赋值

这部分主要是根据cache_hash方法，即哈希算法，计算sel-imp存储的哈希下标，分为以下三种情况：

如果哈希下标的位置未存储sel，即该下标位置获取sel等于0，此时将sel-imp存储进去，并将occupied占用大小加1
如果当前哈希下标存储的sel 等于即将插入的sel，则直接返回
如果当前哈希下标存储的sel 不等于即将插入的sel，则重新经过cache_next方法即哈希冲突算法，重新进行哈希计算，得到新的下标，再去对比进行存储

涉及的两种哈希算法，其源码如下

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__
// 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_t的源码就分析完毕了

疑问解答

1 _mask和_occupied是什么？

_mask是指掩码数据，用于在哈希算法或者哈希冲突算法中计算哈希下标，其中mask 等于capacity - 1。
_occupied：哈希表中 sel-imp 的占用大小
2 bucket数据为什么会丢失，并且为什么打印乱序？
数据丢失：原因是在扩容时，是将原有的内存全部清除了，再重新申请了内存导致的。
乱序：sel-imp的存储是通过哈希算法计算下标的，其计算的下标有可能已经存储了sel，所以又需要通过哈希冲突算法重新计算哈希下标，所以导致下标是随机的，并不是固定的。
3 cache_t中的_ocupied为什么是从2开始？
4 为什么随着方法调用的增多，其打印的occupied 和 mask会变化
因为LGPerson通过alloc创建的对象，并对其两个属性赋值的原因，会隐式调用set方法，set方法的调用也会导致occupied变化