上篇我们说到isa – 类的底层原理结构,分析了类(objc_class)的底层结构从而得出总结了isa/superclass走位图,class_data_bits_t bits。目前还剩一个cache_t cache上文只是简单的了解,本篇就来探索cache。

cache_t cache这是啥

从名字上看,就是我们开发中时不时就会提到的缓存有关。缓存得官方定义:缓存是指可以进行高速数据交换的存储器，它先于内存与CPU交换数据，因此速率很快。可以看出不管是日常还是官方定义来说，cache都是相当重要的,接下来的探索过程也体现出它的复杂程度,而且从源码来看里面有许多苹果底层代码的设计思路。

cache_t源码分析

(源码使用的是objc4-818.2)

struct cache_t {
private:
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask;
    union {
        struct {
            explicit_atomic<mask_t>    _maybeMask;
#if __LP64__
            uint16_t                   _flags;
#endif
            uint16_t                   _occupied;
        };
        explicit_atomic<preopt_cache_t *> _originalPreoptCache;
    };
   
    /*
     #if defined(__arm64__) && __LP64__
     #if TARGET_OS_OSX || TARGET_OS_SIMULATOR
     // __arm64__的模拟器
     #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
     #else
     //__arm64__的真机
     #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_HIGH_16
     #endif
     #elif defined(__arm64__) && !__LP64__
     //32位 真机
     #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_LOW_4
     #else
     //macOS 模拟器
     #define CACHE_MASK_STORAGE CACHE_MASK_STORAGE_OUTLINED
     #endif
     ******  中间是不同的架构之间的判断 主要是用来不同类型 mask 和 buckets 的掩码
    */
    
    public:
    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);
    unsigned capacity() const;
    struct bucket_t *buckets() const;
    Class cls() const;
    void insert(SEL sel, IMP imp, id receiver);
    
    // 下面方法暂与探索无关
 
};
复制代码

CACHE_MASK_STORAGE

源码可以看出，通过宏定义CACHE_MASK_STORAGE分为4种情况处理, CACHE_MASK_STORAGE是基于不同架构下的.

简单回顾一下苹果的指令集

armv7｜armv7s｜arm64都是ARM处理器的指令集

i386｜x86_64 是Mac处理器的指令集

__LP64__简单理解就是表示CPU的一个地址的长度

__ arm64 __, __LP64__相关扩展

arm64与LP64的区别

Linux的编程模型ILP32和LP64

iOS armv7, armv7s, arm64区别与应用32位、64位配置

CONFIG_USE_PREOPT_CACHES

cache_t内部实现有配置项CONFIG_USE_PREOPT_CACHES对某些系统下的进行优化.

// __arm64__ && IOS操作系统 && !模拟器 && !TARGET_OS_MACCATALYST
#if defined(__arm64__) && TARGET_OS_IOS && !TARGET_OS_SIMULATOR && !TARGET_OS_MACCATALYST
#define CONFIG_USE_PREOPT_CACHES 1
#else
#define CONFIG_USE_PREOPT_CACHES 0
#endif
复制代码

一下探索都基于X86_64架构解析，部分内容会因架构不同而有所不同，请以实际架构为准。

• _bucketsAndMaybeMask变量uintptr_t占8字节和isa_t中的bits类似，也是一个指针类型里面存放地址
• 联合体里有一个结构体和一个结构体指针_originalPreoptCache
• 结构体中有三个成员变量 _maybeMask，_flags，_occupied。
• _originalPreoptCache和结构体是互斥的，_originalPreoptCache初始时候的缓存，现在探究类中的缓存，这个变量基本不会用到
• cache_t提供了公用的方法去获取值，以及根据不同的架构系统去获取mask和buckets的掩码

在cache_t看到了buckets()，这个类似于class_data_bits_t里面的提供的methods()，都是通过方法获取值。查看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
  ....
  //省略无关源码
};
复制代码

• bucket_t区分真机和其它，但是变量没变都是_sel和_imp只不过顺序不一样
• bucket_t里面存的是_sel和_imp，cache里面缓存的应该是方法

cache_t 整体结构图

lldb调试验证

首先创建XJPerson类，自定义一些实例方法，在main函数中创建XJPerson的实例化对象，然后进行lldb调试

• p/x pClass后通过首地址 0x0000000100008740 + 偏移值 0x10 得到cache的地址
• 然后p (cache_t*)$1将地址转化成cache_t类型
• 通过p *$2 取地址的方式显示出cache的内容,此时_maybeMask=0 _occupied = 0因为现在还没调用方法
• p/x $3.buckets()获取buckets地址就是数组的首地址
• p *$4显示bucket里面的内存,_sel和_imp

既然现在因为没有缓存任何方法,那就通过lldb调用对象方法，[p sayHello]继续lldb调试

1. 调用sayHello后，_mayMask和occupied被赋值，这两个变量应该和缓存是有关系
2. bucket_t结构提供了sel()和imp(nil,pClass)方法
3. sayhello方法的sel和imp，存在bucket中，存在cache中

小结

通过lldb调试，结合源码。cache中存的是方法，方法的sel和imp存在bucket。上面的lldb调试虽然能够然我们分析出cache的内部结构，但是实在是又繁琐有容易操作出错，操作出错就得重来。这样很不方便,那有没有更方便的方法呢。

脱离源码通过项目查找

测试代码:

void testCase2() {
    Class cls = XJPerson.class;
    struct xj_objc_class *xj_cls = (__bridge  struct xj_objc_class *)cls;
    struct xj_cache_t cache = xj_cls->cache;
    struct xj_bucket_t *buckets = cache._bukets;
    for (uint32_t i = 0; i < cache._maybeMask; i++) {
        struct xj_bucket_t bucket = buckets[i];
        NSLog(@"%@", NSStringFromSelector(bucket._sel));
    }
}

int main(int argc, const char * argv[]) {
    XJPerson *p = [XJPerson alloc];
    [p say1];
    [p say2];
    testCase2();
    return 0;
}
复制代码

测试结果:

(null)
say1
say2
复制代码

那这个cache的过程又是怎么样的呢? 我们找到了cache_t::insert这个方法，下面让我们一起来分析一下，看看他有多厉害。

cache_t::insert

• 先将现在内存占用量与插入sel/imp时在cache总占用量进行对比，看是否需要扩容。
• 然后检测当前cache是否为空，需要申请bucket内存空间，存储sel/imp。
• 最后检测当前总容量是否超过3/4，超过了需要进行扩容，这将会情况回收之前申请的bucket。

补充:哈希表负载因子选择3/4这个界限，是因为在该界限以下插入数据时哈希碰撞概率很小。 如果出现哈希碰撞，需要选择再哈希，或者在一个哈希下标下通过链表/红黑树去插入数据的开销会非常大。

• 通过sel哈希算法计算bucket的哈希下标位置, 并插入sel/imp

void cache_t::insert(SEL sel, IMP imp, id receiver)
{
    ...
    // 使用cache直到超出我们预期的填充率
    // Use the cache as-is if until we exceed our expected fill ratio.
    mask_t newOccupied = occupied() + 1; // _occupied + 1
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    if (slowpath(isConstantEmptyCache())) { // cache为空
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE; // 初始化容量 4
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    // (occupied() + 1) + CACHE_END_MARKER <= 3/4容量 (以这个为例)
    else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) { // newOccupied+1, 容量使用率3/4, 继续使用
        // Cache is less than 3/4 or 7/8 full. Use it as-is.
    }
    // (occupied() + 1) + CACHE_END_MARKER <= 总容量
#if CACHE_ALLOW_FULL_UTILIZATION
    else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) { // newOccupied+1<=capacity 允许容量刚好是用完, 继续使用
        // Allow 100% cache utilization for small buckets. Use it as-is.
    }
#endif
    else {
        // 扩容 (对比3/4容量为例)
        // (occupied() + 1) + CACHE_END_MARKER = occupied() + 2 > 3/4容量, 就会进来
        // 比如: 容量 4, 占用 2, 2 + 2 > 4*(3/4), 扩容
        // 比如: 容量 8, 占用 5, 5 + 2 > 8*(3/4), 扩容
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) { // 容量最大限制 MAX_CACHE_SIZE = 1 << 16, 65536
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true); // true, 清理旧 buckets
    }

    bucket_t *b = buckets();
    mask_t m = capacity - 1;
    mask_t begin = cache_hash(sel, m); // 哈希计算插入位置, cache_hash(sel, m) ==> value & mask
    mask_t i = begin;

    
    // 扫描未使用的位置并插入进去, 插入sel/imp
    // 保证会有一个空位置
    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot.
    do {
        if (fastpath(b[i].sel() == 0)) { // 第i个bucket未存放sel
            incrementOccupied(); // _occupied++; // 位置占用+1
            b[i].set<Atomic, Encoded>(b, sel, imp, cls()); // 第i个bucket, 存入 sel / imp
            return;
        }
        if (b[i].sel() == sel) { // 第i个bucket已存放该sel
            // The entry was added to the cache by some other thread
            // before we grabbed the cacheUpdateLock.
            return;
        }
        
        // 再哈希, cache_next(i, m) ==> (i+1) & mask
        // 1. mask范围内, 往后找桶
        // 2. 超过mask范围
        //    比如 cache_next(7, 7) ==> 8 & 7 ==> 1000 & 111 ==> 0, 回到0, 重头开始找
    } while (fastpath((i = cache_next(i, m)) != begin));

    // 抛异常
    bad_cache(receiver, (SEL)sel);
#endif // !DEBUG_TASK_THREADS
}
复制代码

(源码位置 文件objc-cache.mm的826-895行)

验证扩容规则

@interface XJPerson : NSObject
@end

@implementation XJPerson
- (void)say1 {}
- (void)say2 {}
- (void)say3 {}
- (void)say4 {}
- (void)say5 {}
- (void)say6 {}
- (void)say7 {}
- (void)say8 {}
- (void)say9 {}
@end

void testCase1() {
    XJPerson *p = [XJPerson alloc];
    [p say1]; //初始容量4-1
    [p say2];
    [p say3]; //占用2个, 插入第3个时, 扩容至8-1
    [p say4];
    [p say5];
    [p say6];
    [p say7];
    [p say8]; //占用5个, 插入第6个时, 扩容至16-1
    [p say9];
    NSLog(@"---");
}

int main(int argc, const char * argv[]) {
    testCase1();
    return 0;
}
复制代码

扩容之前

扩容之后

cache_t::insert 流程图