在 OC底层原理07-类的结构分析 这篇文章中，我们研究了objc_class中的superclass、bits，今天这篇补充研究当时被忽略的cache_t

一、准备工作

1.1、objc4可编译源码，可直接跳到文章最后，下载调试好的源码

1.2、在源码中新增类GomuPerson如下

//: GomuPerson.h
@interface GomuPerson : NSObject

- (void)sayNO;
- (void)sayHello;
- (void)sayCode;
- (void)sayHi;
- (void)sayShare;
+ (void)sayLove;

@end

//: GomuPerson.m
- (void)sayNO{ NSLog(@"调用：%s",__func__); }
- (void)sayHello{ NSLog(@"调用：%s",__func__); }
- (void)sayCode{ NSLog(@"调用：%s",__func__); };
- (void)sayHi{ NSLog(@"调用：%s",__func__); };
- (void)sayShare{ NSLog(@"调用：%s",__func__); };
+ (void)sayLove{ NSLog(@"调用：%s",__func__); }

//: main.m
GomuPerson *p = [GomuPerson alloc];
Class cls = [GomuPerson class];
        
[p sayNO];
[p sayHello];

1.3、重点源码定位

1.3.1 回顾objc_class源码

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
   //: 由于代码量过大，这里只展示关键代码，源码请自行查阅
};

• 在 OC底层原理07-类的结构分析 这篇文章中，我们通过地址平移32拿到了bits，这篇文章依旧先采用这个方法进行研究。

1.3.2 cache_t源码

struct cache_t {
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    //: 我们当前研究的环境macOS/模拟器走这里
    //: macOS: i386 模拟器: x86_64
    explicit_atomic<struct bucket_t *> _buckets;
    explicit_atomic<mask_t> _mask;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    //: (__arm64__) && __LP64__(真机64位) 会走这里
    explicit_atomic<uintptr_t> _maskAndBuckets;
    //: 没有用到，猜想：没开源，或者是苹果程序猿没写完
    mask_t _mask_unused;
    //: mask移动的值
    static constexpr uintptr_t maskShift = 48;
    //: 空出的值，用来分割mask和bucket，虽然属于bucket，但是他永远是0
    static constexpr uintptr_t maskZeroBits = 4;
    //: 可存储的最大掩码值：1向左移16位减1
    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
    //: 获取buckets指针需要做的操作：1向左移44位减1，向左移4的原因是让这4位一直为0，猜测是避免mask和bucket冲突
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << (maskShift - maskZeroBits)) - 1;
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
    //: (__arm64__) && !__LP64__(真机非64位) 会走这里
    explicit_atomic<uintptr_t> _maskAndBuckets;
    mask_t _mask_unused;
    static constexpr uintptr_t maskBits = 4;
    //: 1向左移4位减1
    static constexpr uintptr_t maskMask = (1 << maskBits) - 1;
    //:  取非
    static constexpr uintptr_t bucketsMask = ~maskMask;
#if __LP64__
    uint16_t _flags;
#endif
    uint16_t _occupied;
    //: 由于代码量过大，这里只展示关键代码，源码请自行查阅
}

• 得到4个重要研究的属性：_buckets，_mask，_flags，_occupied

1.3.3 bucket_t源码

struct bucket_t {
private:
    //: IMP-first is better for arm64e ptrauth and no worse for arm64.
    //: IMP-first对arm64e的效果更好，而对arm64也不差。
    //: SEL-first is better for armv7* and i386 and x86_64.
    //: SEL-first适用于armv7 *和i386和x86_64。
#if __arm64__  //: 真机
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else //: 非真机
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
public:
    // 取SEL
    inline SEL sel() const { return _sel.load(memory_order::memory_order_relaxed); }
    // 取IMP
    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;
}

• _buckets里面存了sel和imp

1.3.4 _mask，_flags，_occupied源码

// _mask 是一个 unsigned int 类型
typedef unsigned int uint32_t;
typedef uint32_t mask_t; 

// _flags, _occupied 是一个unsigned short 类型
typedef unsigned short uint16_t;
uint16_t _flags;
uint16_t _occupied;

• _mask，_flags，_occupied是用来计数的

二、基于macOS(x88_64)，研究cache_t

2.1 调用2个方法后下一个断点

image.png

2.2 研究方法一：lldb调试

// 调用方法NSLog打印
调用：-[GomuPerson sayNO]
调用：-[GomuPerson sayHello]
// 拿到类`GomuPerson `的首地址
(lldb) p/x cls
(Class) $0 = 0x00000001000083c8 GomuPerson
// 地址平移16位，拿到`cache_t`
(lldb) p/x (cache_t *)0x00000001000083d8
(cache_t *) $1 = 0x00000001000083d8
// 从 cache_t 中取 buckets()
// 由于 buckets() 是一个集合，所以我们可以用下标去取
// 取第一个位置的buckets()中的sel
(lldb) p ($1->buckets())[0].sel()，为sayNO
(SEL) $2 = "sayNO"
// 取第二个位置的buckets()中的sel，为空
(lldb) p ($1->buckets())[1].sel()
(SEL) $3 = <no value available>
// 取第三个位置的buckets()中的sel，为sayHello
(lldb) p ($1->buckets())[2].sel()
(SEL) $4 = "sayHello"
// 取第一个位置的buckets()中的imp
(lldb) p ($1->buckets())[0].imp(cls)
(IMP) $5 = 0x0000000100003bd0 (GomuTest`-[GomuPerson sayNO])
// 取第二个位置的buckets()中的imp
(lldb) p ($1->buckets())[1].imp(cls)
(IMP) $6 = 0x0000000000000000
// 取第三个位置的buckets()中的imp
(lldb) p ($1->buckets())[2].imp(cls)
(IMP) $7 = 0x0000000100003c00 (GomuTest`-[GomuPerson sayHello])
(lldb) 

// p ($1->buckets())[2].sel()  和下面的写法等价
// p *(($1->buckets())+2)->imp(cls)
// 2种取集合的方式，通过下标[2]，通过指针平移+2

• 调用方法，cache会对该方法进行存储
• 方法存储不是连续的
• 结构体里面的属性只是存值的地方，结构体值变化需要依赖方法，所以我们取buckets，不是直接$1._buckets，而是调用方法$1.buckets()，sel，imp同理

2.2 研究方法二：脱离源码构造自定义源码结构体

2.2.1 重新准备没有源码的环境，创建新的GomuPerson，如下

//: GomuPerson.h
- (void)say1;
- (void)say2;
- (void)say3;
- (void)say4;
- (void)say5;
- (void)say6;
- (void)say7;
+ (void)sayHappy;

//: GomuPerson.m
- (void)say1{
    NSLog(@"调用：%s",__func__);
}
- (void)say2{
    NSLog(@"调用：%s",__func__);
}
- (void)say3{
    NSLog(@"调用 : %s",__func__);
}
- (void)say4{
    NSLog(@"调用 : %s",__func__);
}
- (void)say5{
    NSLog(@"调用 : %s",__func__);
}
- (void)say6{
    NSLog(@"调用 : %s",__func__);
}
- (void)say7{
    NSLog(@"调用 : %s",__func__);
}
+ (void)sayHappy{
    NSLog(@"调用 : %s",__func__);
}

2.2.2 把cache_t源码赋值，进行改错补齐，不研究的属性直接删除，如下:

//: main.m
typedef uint32_t mask_t; 
//: cache_t 中的 bucket_t
struct gomu_bucket_t {
    SEL _sel;
    IMP _imp;
};
//: cache_t
struct gomu_cache_t {
    struct gomu_bucket_t * _buckets;
    mask_t _mask;
    uint16_t _flags;
    uint16_t _occupied;
};
//: class_data_bits_t
struct gomu_class_data_bits_t {
    uintptr_t bits;
};
//: objc_class
struct gomu_objc_class {
    Class ISA;
    Class superclass;
    struct gomu_cache_t cache;        
    struct gomu_class_data_bits_t bits; 
};

//: 获取Buckets，更直观
void getBuckets(Class pClass)
{
    struct gomu_objc_class *gomu_pClass = (__bridge struct gomu_objc_class *)(pClass);
    // 打印 occupied  mask flags
    NSLog(@"occupied = %hu & mask = %u & flags = %u",gomu_pClass->cache._occupied,gomu_pClass->cache._mask,gomu_pClass->cache._flags);
    for (mask_t i = 0; i<gomu_pClass->cache._mask; i++) {
        // 打印获取的 bucket
        struct gomu_bucket_t bucket = gomu_pClass->cache._buckets[i];
        NSLog(@"sel = %@ & imp = %p",NSStringFromSelector(bucket._sel),bucket._imp);
    }
};

2.2.3 不调用方法观察getBuckets打印结果

//: 调用
GomuPerson *p  = [GomuPerson alloc];
Class pClass = [GomuPerson class]; 
getBuckets(pClass);

//: log
occupied = 0 & mask = 0  & flags = 32804

• 当没有调用方法的时候，occupied、mask都为0，即可以判断他们的初始值为0

2.2.4 调用say1观察getBuckets打印结果

//: 调用
[p say1];
getBuckets(pClass);

//: log
occupied = 1 & mask = 3 & flags = 32804
sel = (null) & imp = 0x0
sel = say1 & imp = 0xb840
sel = (null) & imp = 0x0

• occupied为1，mask为3
• flags为32804
• say1方法存进了_buckets中，但是不是存在首位置
• 其他2个位置为空

2.2.5 调用say1、say2观察getBuckets打印结果

//: 调用
[p say1];
[p say2];
getBuckets(pClass);

//: log
occupied = 2 & mask = 3 & flags = 32804
sel = (null) & imp = 0x0
sel = say1 & imp = 0xb840
sel = say2 & imp = 0xb838

• occupied为2，mask为3
• flags为32804
• say1、say2方法存进了_buckets中，但都不是存在首位置
• 剩余1个位置为空

2.2.6 调用say1、say2、say3观察getBuckets打印结果

//: 调用
[p say1];
[p say2];
[p say3];
getBuckets(pClass);

//: log
occupied = 1 & mask = 7 & flags = 32804
sel = (null) & imp = 0x0
sel = (null) & imp = 0x0
sel = (null) & imp = 0x0
sel = say3 & imp = 0xb9f0
sel = (null) & imp = 0x0
sel = (null) & imp = 0x0
sel = (null) & imp = 0x0

• occupied为1，mask为7
• flags为32804
• say1、say2不在了
• say3方法存进了_buckets中，也不是存在首位置
• 剩余6个位置为空

2.2.7 调用say1、say2、say3、say4观察getBuckets打印结果

//: 调用
[p say1];
[p say2];
[p say3];
[p say4];
getBuckets(pClass);

//: log
occupied = 2 & mask = 7 & flags = 32804
sel = say4 & imp = 0xb9c8
sel = (null) & imp = 0x0
sel = (null) & imp = 0x0
sel = say3 & imp = 0xb9f8
sel = (null) & imp = 0x0
sel = (null) & imp = 0x0
sel = (null) & imp = 0x0

• occupied为2，mask为7
• flags为32804
• say1、say2还是不在了
• say3、say4方法存进了_buckets中，也不是存在首位置，无序的
• 剩余5个位置为空

2.2.8 逐步增加方法的调用，得出以下结论

• occupied表示缓存在_buckets中的方法数量
• mask表示系统劈开的空间最大值，从 3 即（4-1）开始
• 当occupied最大比mask小2，一旦occupied = mask - 1的时候，mask就会以mask*2-1的算法递增，occupied开始重新从1开始计算，以前存的方法全部从_buckets中清除
• 方法在_buckets中是无序的
• flags为32804，一直没变，猜测它是个固定值

三、从源码方法入手，分析cache_t

3.1 cache_t方法源码

struct cache_t {
    //: 由于代码量过大，这里只展示关键代码，源码请自行查阅

    //: 声明一个空 bucket_t： `objc_cache`类型
    static bucket_t *emptyBuckets();
    //: buckets() 的load方法 ：return _buckets.load(memory_order::memory_order_relaxed);
    struct bucket_t *buckets();
    //: mask() 的load方法 ：return _mask.load(memory_order::memory_order_relaxed);
    mask_t mask();
    //: occupied()的get方法：return _occupied;
    mask_t occupied();
    //: occupied自增：_occupied++;
    void incrementOccupied();
    //: 初始化方法
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    //: 置空
    void initializeToEmpty();
};

• 定位到occupied变化方法incrementOccupied，全局搜索，在cache_t::insert方法中被调用
• 定位到初始化方法setBucketsAndMask

3.2 cache_t::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());
  
    //: occupied + 1
    mask_t newOccupied = occupied() + 1;
    //: 把旧的capacity赋值给新的capacity
    //: capacity()：return mask() ? mask()+1 : 0;
    //: mask不为0就把mask+1赋值给capacity，mask为0就把0赋值给capacity
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    //: 判断是否是第一次缓存，当前研究的类第一次调用方法的时候才会调用
    if (slowpath(isConstantEmptyCache())) {
        //: 如果capacity为0，则给capacity赋初值：INIT_CACHE_SIZE：4
        //: INIT_CACHE_SIZE = (1 << INIT_CACHE_SIZE_LOG2)，INIT_CACHE_SIZE_LOG2 = 2，得到INIT_CACHE_SIZE就是1往左移2位，就是4
        if (!capacity) capacity = INIT_CACHE_SIZE;
        //: 初始化buckets+开辟内存空间
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    else if (fastpath(newOccupied + CACHE_END_MARKER <= capacity / 4 * 3)) {
        //: occupied <= 3/4* capacity 就走这里
        //: 注意：这里的newOccupied已经被+1了，到这里的时候又加了一个CACHE_END_MARKER，所以当occupied = capacity-2的时候就不会走这里了。
        //: 即如果首次capacity=4，当存第三个方法时newOccupied=3，newOccupied+ CACHE_END_MARKER=4，就会走下面else
    }
    else {
        //: `扩容，如果capacity不为0，capacity*2，否则 capacity=4
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        //: 设置capacity最大边界
        if (capacity > MAX_CACHE_SIZE) {
            //: MAX_CACHE_SIZE_LOG2  = 16,
            //: MAX_CACHE_SIZE = (1 << MAX_CACHE_SIZE_LOG2),
            //: MAX_CACHE_SIZE 就是1左移16位，2^16次方
            capacity = MAX_CACHE_SIZE;
        }
        //: 重新初始化buckets+开辟内存空间
        reallocate(oldCapacity, capacity, true);
    }
    //: 创建一个bucket_t类型的指针b
    bucket_t *b = buckets();
    //: 把capacity-1赋值给m
    mask_t m = capacity - 1;
    //: 进行hash散列，把sel放入随机下标的位置
    //: cache_hash : return (mask_t)(uintptr_t)sel & mask;
    //: sel & mask: 会得到一个1-mask的值
    mask_t begin = cache_hash(sel, m);
    //: 把这个位置赋值给i， 作为下面循环的索引
    mask_t i = begin;
    //: do-while循环，目的是随机存入bucket
    //: 如果 key 为 0，说明当前索引位置上还没有缓存过bucket，则把当前bucket存进去，然后跳出循环
    //: 如果需要存的sel和当前位置的sel相等，则跳出循环
    do {
        if (fastpath(b[i].sel() == 0)) {
            //：occupied++
            incrementOccupied();
            //: 构造bucket，并赋值给当前buckets的I这个位置，set方法
            b[i].set<Atomic, Encoded>(sel, imp, cls);
            return;
        }
        //: sel相等
        if (b[i].sel() == sel) {
            return;
        }
    //: cache_next 
    //: 当前环境下 (i+1) & mask
    //: 这里的循环遍历是通过 cache_next 方法实现的，这个方法内部就是当前下标 i 与 mask_t 的值进行与操作，来实现索引更新的
    //: 真机环境下  i ? i-1 : mask (如果i为0就跳到最后，否则进行-1，向前遍历)
    } while (fastpath((i = cache_next(i, m)) != begin));
    //: 容错处理
    cache_t::bad_cache(receiver, (SEL)sel, cls);
}

3.3 reallocate源码解读

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld)
{
    //: 判断是否有旧的buckets
    bucket_t *oldBuckets = buckets();
    //: 开辟空间calloc，然后强转成bucket_t *类型
    //: 去内存里面申请一个指针地址让他指向newBuckets，并把它转成bucket_t *类型
    bucket_t *newBuckets = allocateBuckets(newCapacity);
    ASSERT(newCapacity > 0);
    ASSERT((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
    //: 初次进来初始化，对mask buckets occupied 进行初始化
    //: 不是初次就会重新初始化，以前的会被干掉
    setBucketsAndMask(newBuckets, newCapacity - 1);
    if (freeOld) {
        //: 清理之前的oldBuckets，并把当前的buckets赋值给最后面的位置，首次不走这里
        cache_collect_free(oldBuckets, oldCapacity);
    }
}

3.4 setBucketsAndMask源码解读

__x86_64__ || i386
void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    //: 给buckets初始化并赋值
    //: 确保其他线程的指针访问之前先存入buckets
    _buckets.store(newBuckets, memory_order::memory_order_release);
    //: 给mask初始化并赋值
    //: 确保其他线程的指针访问之前先存入mask
    _mask.store(newMask, memory_order::memory_order_release);
    //: _occupied置0
    _occupied = 0;

(__arm64__) && __LP64__
    //: 真机中mask和bucket共用64位
    //: newMask << maskShift 左移48位，相当于mask用了左边16位
     //: | newBuckets ,buket存到后面48位中，其实只用了右边44位，而且还减1，最右边1位也没有用
    _maskAndBuckets.store(((uintptr_t)newMask << maskShift) | (uintptr_t)newBuckets, std::memory_order_relaxed);
     //: _occupied置0
    _occupied = 0;
};

四、总结

• occupied确定表示_buckets中的方法数量
• capacity初始值是4，以capacity*2的方式进行递增
• mask表示需要开辟的空间，为当前的capacity - 1
• 当occupied = mask-2的时候，就会重新开辟空间，occupied先置为0，算do-while的时候会自增
• 方法的cache过程经过了hash散列，所以bucket是无序的
• flags还未探索到

五、拓展知识

• 类方法不会存到_buckets中
• 同一个实例方法只会存一次，再次调用只要_buckets中有就不会再存
• cache_t::insert被cache_fill调用，全局搜索cache_fill，会发现如下注释：

• cache读取流程 (下一章分析)
  Cache readers (PC-checked by collecting_in_critical())
  objc_msgSend*
  cache_getImp

• cache写入流程
  Cache writers (hold cacheUpdateLock while reading or writing; not PC-checked)
  cache_fill (acquires lock)
  cache_expand (only called from cache_fill)
  cache_create (only called from cache_expand)
  bcopy (only called from instrumented cache_expand)
  flush_caches (acquires lock)
  cache_flush (only called from cache_fill and flush_caches)
  cache_collect_free (only called from cache_expand and cache_flush)