iOS类的结构分析之cache

前言

在类的结构探究分析中，我们了解了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
}

并且详细研究了bits及其中的属性，成员变量和方法，今天我会带大家详细探究cache的结构及其工作流程。
本期内容比较深，但如果你有胆跟着我走到最后，相信你会对类的结构有更加清晰的认识！

准备工作##

既然是研究类的缓存cache，猜测它里面会存储什么呢？属性，成员变量和方法应该都有吧，并且作为缓存来讲必然会有读和写两种操作，我们接下来会以此为分析路径一步步探索。
依旧是FCPerson:

image.png

为了研究方法，多搞一些实例方法，别忘了实现一下。

通过LLDB方式获取缓存中的方法

1. 理清cache_t结构
之前猜测cache中应该缓存了很多数据，我们先从方法入手。只调用instanceMethod1，打好断点，咱们正式开始

image.png

类的结构探究分析中我们已经计算了cache大小为16字节，并且通过首地址平移32获得的bits，自然，获取cache_t为首地址平移16：

cache_t结构

如图，$3就是FCPerson的cache_t。我们配合着cache_t源码来了解这些数据：

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

• cache_t是一个结构体
• _bucketsAndMaybeMask字面意思，桶+可能的mask，占8字节，具体含义未知
• 接下来是一个联合体，其中第一个成员为结构体，切结构体的第二个成员_flags条件为LP64（Linex或Mac OS X），必然符合，所以_originalPreoptCache就先不需要看了。
• 第一个结构体中_maybeMask看起来跟外围的_bucketsAndMaybeMask或许有关，_flags标记，_occupied字面意思为占用位置，三个成员都已经打印出来了。

2. 取出缓存中的方法
光看cache_t的结构，暂时还看不出哪些是与我们目标相关的东西。为了获取缓存中的方法，探究缓存针对方法的读写过程，我们来看cache_t源码下方的方法，看有没有相关的方法。cache_t中的方法很多，有一串方法引起了我的注意：

    static bucket_t *emptyBuckets();  // 清空
    static bucket_t *allocateBuckets(mask_t newCapacity);  // 开辟创建
    static bucket_t *emptyBucketsForCapacity(mask_t capacity, bool allocate = true);
    static struct bucket_t * endMarker(struct bucket_t *b, uint32_t cap);

    struct bucket_t *buckets() const; // 获取桶子们

这一串是对桶子的操作，清空，创建以及获取桶子数组，必然跟刚才的_bucketsAndMaybeMask也有关联，那么再看看桶子究竟是个啥：

struct bucket_t {
#if __arm64__
    explicit_atomic<uintptr_t> _imp;
    explicit_atomic<SEL> _sel;
#else
    explicit_atomic<SEL> _sel;
    explicit_atomic<uintptr_t> _imp;
#endif
}

显而易见，桶子是用来存储方法的容器！

再在struct bucket_t中继续查看桶子的相关操作方法，看到了：

inline SEL sel()
inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls)

分别是获取SEL和IMP，我们来用LLDB走一遍试一试，首先获取buckets：

获取buckets
输出buckets内容

尝试调用sel和imp方法：

sel&imp

获取成功！拿到了缓存中的instanceMethod1及其实现Imp！

3. 插入方法解析
有取必有存，我们再回到cache_t当中寻找存储的方法，很容易看到：

void insert(SEL sel, IMP imp, id receiver);

无须猜测，这个insert必然是向缓存中插入方法，去掉多余代码后：

void cache_t::insert(SEL sel, IMP imp, id receiver) {
    // Use the cache as-is if until we exceed our expected fill ratio.
    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 <= cache_fill_ratio(capacity))) {
        // Cache is less than 3/4 or 7/8 full. Use it as-is.
    }
#if CACHE_ALLOW_FULL_UTILIZATION
    else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) {
        // Allow 100% cache utilization for small buckets. Use it as-is.
    }
#endif
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        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.
    do {
        if (fastpath(b[i].sel() == 0)) {
            incrementOccupied();
            b[i].set<Atomic, Encoded>(b, 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));

    bad_cache(receiver, (SEL)sel);
#endif // !DEBUG_TASK_THREADS
}

只保留关键代码依然很长，但已经很易读了：

• mask_t newOccupied = occupied() + 1;创建occupied，新的occupied()为0，newOccupied = 1
• oldCapacity，看起来是对可用储存空间的赋值
• 接下来是一长段ifelse，既然从0开始研究，第一次必走isConstantEmptyCache ()条件
• if (!capacity) capacity = INIT_CACHE_SIZE;，其中:

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

则capacity储存空间的初始值为1左移2位，等于4字节

• reallocate(oldCapacity, capacity, /* freeOld */false);划重点，依据oldCapacity，新capacity，对cache重分配空间，上代码：

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
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
        collect_free(oldBuckets, oldCapacity);
    }
}

通过代码很好理解分配空间流程：
拿当前的桶子，用传入的newCapacity创建一个新桶子，然后setBucketsAndMask，通过传入的freeOld来判断是否清空旧桶子，此次传入的是false，所以不用管，而且从0开始研究很容易理解第一次进入方法的时候，旧桶子应该为空。（源码注释：缓存中旧数据不会传递，这是为了节省缓存额外数据时使用的内存，我们后面会讲到）
setBucketsAndMask这个方法是不是很熟悉？明显跟cache_t的第一个成员_bucketsAndMaybeMask相关，点进去看（去掉多余代码）：

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.

    _bucketsAndMaybeMask.store((uintptr_t)newBuckets, memory_order_relaxed);

    _maybeMask.store(newMask, memory_order_relaxed);
    _occupied = 0;
}

可以看到，首先将新桶子的地址储存到_bucketsAndMaybeMask，然后把newMask储存到_maybeMask中，注意到这个_maybeMask其实就是cache_t中联合体里结构体的成员变量，传入的值为newCapacity - 1 = 3，也就是说_maybeMask的含义其实就是开辟的储存空间大小减1，最后为_occupied(其实就是储存的桶子数量/缓存中的方法数量)赋初始值0。（源码注释中讲到了objc_msgSend）
至此，cache_t中第一个成员已经理清了，_bucketsAndMaybeMask中储存的是储存方法的桶子地址及对应开辟的空间大小。

回到insert方法，目前有了桶子，对应的大小（newCapacity - 1 ），并存入到_bucketsAndMaybeMask中，继续往下走：

• bucket_t *b = buckets();获取桶子的哈希列表
• mask_t m = capacity - 1; m = 3
• mask_t begin = cache_hash(sel, m);sel对应在哈希中的起始地址
• do while循环，意义就是对buckets这个哈希列表的赋值过程。通过b[i].sel() == 0判断当前桶子列表里有没有要插入的sel，有则return，没有则incrementOccupied();：

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

_occupied由0变1
然后最后最重要的存储方法b[i].set<Atomic, Encoded>(b, sel, imp, cls());（去掉多余代码）：

void bucket_t::set(bucket_t *base, SEL newSel, IMP newImp, Class cls)
{
    uintptr_t newIMP = (impEncoding == Encoded
                        ? encodeImp(base, newImp, newSel, cls)
                        : (uintptr_t)newImp);

    if (atomicity == Atomic) {
        _imp.store(newIMP, memory_order_relaxed);
        
        if (_sel.load(memory_order_relaxed) != newSel) {
            _sel.store(newSel, memory_order_relaxed);
        }
    } else {
        _imp.store(newIMP, memory_order_relaxed);
        _sel.store(newSel, memory_order_relaxed);
    }
}

方法中针对原子性有一些区别，但最终都是存储Imp和SEL。

这里有一点需要注意一下，当产生哈希冲突时触发i = cache_next(i, m)：

#if CACHE_END_MARKER
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}
#elif __arm64__
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}

根据源码可以看出区别，如果当前环境为真机，则哈希冲突的解决方式为向前存储（i - 1），否则则是向后存储（i + 1）。向前存储依然冲突直至减到0好位置时，则会调到mask的位置重新循环，当从mask也循环到begin的位置依然无法存储时，则跳出循环进入bad_cache(receiver, (SEL)sel);。

**至此，我们完整的分析了一个方法储存到cache中的完整流程，我们再来对照一下之前输出的cache_t结构：

cache_t结构

现在已经非常明确了各个成员变量储存的内容和含义：

• _bucketsAndMaybeMask：存储方法列表的地址信息
• _maybeMask：存储方法开辟的内存大小减1，当前案例为3
• _flags：标记
• _occupied：存储的方法数量，当前案例为1。
  所有值的含义均符合当前案例：调用了一个实例方法，并将其写入cache。

再来总结一下目前为止，cache存储方法的流程：

cache流程图.png

我们已经清楚了缓存从0到1，存储一个方法的流程，接下来我们继续研究：在已有缓存的情况下，缓存多个方法会发生什么情况。
如图调用4个实例方法后，再输出cache并查看缓存方法：

案例
输出cache_t结构：
打印输出
输出储存的方法：
image.png

提问：

• 调用了4个实例方法，为什么occupied不是4而是2？
• 调用顺序为1，2，3，4，为什么之缓存了3和4？
• Value为什么为7？

带着这些疑问，我们回到insert源码：

mask_t newOccupied = occupied() + 1;

之前已有_occupied = 1，所以这次newOccupied = 1+1 = 2
再看后面一大串if else判断：

    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 <= cache_fill_ratio(capacity))) {
        // Cache is less than 3/4 or 7/8 full. Use it as-is.
    }
#if CACHE_ALLOW_FULL_UTILIZATION
    else if (capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity) {
        // Allow 100% cache utilization for small buckets. Use it as-is.
    }
#endif
    else {
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);
    }

之前已经走过isConstantEmptyCache()，所以这次先看第二个条件fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))，对应定义部分：

#if __arm__  ||  __x86_64__  ||  __i386__
#define CACHE_END_MARKER 1
static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 3 / 4;
}
#elif __arm64__ && !__LP64__
#define CACHE_END_MARKER 0
// Historical fill ratio of 75% (since the new objc runtime was introduced).
static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 3 / 4;
}

#elif __arm64__ && __LP64__
#define CACHE_END_MARKER 0
static inline mask_t cache_fill_ratio(mask_t capacity) {
    return capacity * 7 / 8;
}

这里针对不同的架构做了不同的处理，当前我使用的模拟器测试，所以走i386，CACHE_END_MARKER为1，这句判断的条件为，已知capacity = oldCapacity = 4，newOccupied+1 <= 4*3/4的意义就是判断当前存储方法所占空间是否大于开辟空间的3/4，如果是真机测试则是3/4，如果不大于，则继续走后面的流程，如果大于，则走进else的逻辑。

再看第三个条件capacity <= FULL_UTILIZATION_CACHE_SIZE && newOccupied + CACHE_END_MARKER <= capacity，对应定义部分：

FULL_UTILIZATION_CACHE_SIZE = (1 << FULL_UTILIZATION_CACHE_SIZE_LOG2),
FULL_UTILIZATION_CACHE_SIZE_LOG2 = 3,

FULL_UTILIZATION_CACHE_SIZE - 最大空间为1<<3 = 8，条件：capacity<=8并且newOccupied + 0 <= capacity。注意，走进这个条件的有个先决条件CACHE_ALLOW_FULL_UTILIZATION，当前我用的模拟器，不会走到这个判断中

再看最后的else里做了什么：

• capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;双倍扩容
• reallocate(oldCapacity, capacity, true);reallocate方法之前讲过了，传入的bool值之前是false，现在是true，以为着当走到这里时，会清空之前缓存的桶子，创建新的大桶子。

套用案例我们重新过一遍逻辑：
调用第一个实例方法：newOccupied = 1 -> 走isConstantEmptyCache -> capacity = 4 -> set(set,imp) -> _occupied++ -> _occupied = 1；
调用第二个实例方法：newOccupied = _occupied + 1 = 2, capacity = 4 -> 走fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity)) -> 2+1<=4*3/4符合条件直接跳过 -> set(set,imp) -> _occupied++ -> _occupied = 2；
调用第三个实例方法：newOccupied = _occupied + 1 = 3, capacity = 4 -> 3 + 1<=4*3/4不符合进入else -> 双倍扩容capacity = 8 -> reallocate(oldCapacity, capacity, true) -> setBucketsAndMask(newBuckets, 7) -> _maybeMask = 7，_occupied = 0， freeOld() -> set(set,imp) -> _occupied++ -> _occupied = 1；
调用第四个实例方法：newOccupied = _occupied + 1 = 2, capacity = 8 -> 2 + 1<=8*3/4符合条件直接跳过 -> set(set,imp) -> _occupied++ -> _occupied = 2；

总结

至此已经完全解开了刚才的三个疑问，细心的同学可以一个一个的添加方法，看结果是不是符合逻辑，综上，cache储存方法的完整流程图为：

cache存储方法完整流程