OC类底层结构-方法缓存之cache_t

什么是cache_t

cache_t是负责OC类中的结构体objc_class中的缓存模块。比如方法缓存都是通过它实现的。以下是objc_class的结构，其中就有cache_t cache属性：

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

    class_rw_t *data() const {
        return bits.data();
    }
    void setData(class_rw_t *newData) {
        bits.setData(newData);
    }
......省略
}

cache_t的结构解析

cache_t在objc_class的属性是cache，接下来我们查看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.

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

public:
    static bucket_t *emptyBuckets();
    
    struct bucket_t *buckets();
    mask_t mask();
    mask_t occupied();
    void incrementOccupied();
    void setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask);
    void initializeToEmpty();

    unsigned capacity();
    bool isConstantEmptyCache();
    bool canBeFreed();

#if __LP64__
    bool getBit(uint16_t flags) const {
        return _flags & flags;
    }
    void setBit(uint16_t set) {
        __c11_atomic_fetch_or((_Atomic(uint16_t) *)&_flags, set, __ATOMIC_RELAXED);
    }
    void clearBit(uint16_t clear) {
        __c11_atomic_fetch_and((_Atomic(uint16_t) *)&_flags, ~clear, __ATOMIC_RELAXED);
    }
#endif

#if FAST_CACHE_ALLOC_MASK
    bool hasFastInstanceSize(size_t extra) const
    {
        if (__builtin_constant_p(extra) && extra == 0) {
            return _flags & FAST_CACHE_ALLOC_MASK16;
        }
        return _flags & FAST_CACHE_ALLOC_MASK;
    }

    size_t fastInstanceSize(size_t extra) const
    {
        ASSERT(hasFastInstanceSize(extra));

        if (__builtin_constant_p(extra) && extra == 0) {
            return _flags & FAST_CACHE_ALLOC_MASK16;
        } else {
            size_t size = _flags & FAST_CACHE_ALLOC_MASK;
            // remove the FAST_CACHE_ALLOC_DELTA16 that was added
            // by setFastInstanceSize
            return align16(size + extra - FAST_CACHE_ALLOC_DELTA16);
        }
    }

    void setFastInstanceSize(size_t newSize)
    {
        // Set during realization or construction only. No locking needed.
        uint16_t newBits = _flags & ~FAST_CACHE_ALLOC_MASK;
        uint16_t sizeBits;

        // Adding FAST_CACHE_ALLOC_DELTA16 allows for FAST_CACHE_ALLOC_MASK16
        // to yield the proper 16byte aligned allocation size with a single mask
        sizeBits = word_align(newSize) + FAST_CACHE_ALLOC_DELTA16;
        sizeBits &= FAST_CACHE_ALLOC_MASK;
        if (newSize <= sizeBits) {
            newBits |= sizeBits;
        }
        _flags = newBits;
    }
#else
    bool hasFastInstanceSize(size_t extra) const {
        return false;
    }
    size_t fastInstanceSize(size_t extra) const {
        abort();
    }
    void setFastInstanceSize(size_t extra) {
        // nothing
    }
#endif

    static size_t bytesForCapacity(uint32_t cap);
    static struct bucket_t * endMarker(struct bucket_t *b, uint32_t cap);

    void reallocate(mask_t oldCapacity, mask_t newCapacity, bool freeOld);
    void insert(Class cls, SEL sel, IMP imp, id receiver);

    static void bad_cache(id receiver, SEL sel, Class isa) __attribute__((noreturn, cold));
};

这里我们以arm64架构（以下CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16部分）进行分析，我们将上面结构体简化成：

struct cache_t {
    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;//用于读取出bucket_t指针

#if __LP64__
    uint16_t _flags;// 标记位
#endif
    uint16_t _occupied;//已占用的缓存量
}

从代码中可以看到很多的uintptr_t类型数据，那么uintptr_t是什么数据结构呢？以下是通过查看一些资料得到的解释：

是无符号整数类型，能够存储指针。这通常意味着它与指针的大小相同。 它可选地在C ++ 11和更高版本的标准中定义。 想要一个可以保存体系结构指针类型的整数类型的常见原因是对指针执行特定于整数的操作，或者通过将指针提供为整数“句柄”来模糊指针的类型。

其中比较重要的属性_maskAndBuckets就是uintptr_t类型，其实这里就是为了节省内存以及读取方便把mask和buckes指针存在一起。而struct bucket_t中实际上是存储方法SEL和其实现的函数指针的基本结构。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
......省略
}

bucket_t非常简单，实际上就是缓存方法的结构体。通过两个属性uintptr_t _imp和SEL _sel，_imp是方法实现指针，_sel可以认为就是我们方法名称，他们通过bucket_t结构体一一对应。

cache_t怎么进行方法缓存的

想知道cache_t怎么存就得从它的insert方法入手，方法存储的时候会通过cache_fill方法调用insert方法进行存储。首先cache_fill的代码如下：

void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
    runtimeLock.assertLocked();

#if !DEBUG_TASK_THREADS
    // Never cache before +initialize is done
    if (cls->isInitialized()) {
        cache_t *cache = getCache(cls);
#if CONFIG_USE_CACHE_LOCK
        mutex_locker_t lock(cacheUpdateLock);
#endif
        cache->insert(cls, sel, imp, receiver);
    }
#else
    _collecting_in_critical();
#endif
}

通过当前类取出cache属性，然后在调用cache_t的insert方法进行存储。接下来先看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)) {
        // Cache is less than 3/4 full. Use it as-is.
    }
    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 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);
}

这个方法的逻辑大概这样，首先，通过isConstantEmptyCache()方法判断缓存是否为空，如果为空则开辟新的空间，容量为四个字节（capacity = INIT_CACHE_SIZE），并通过方法reallocate创建新的buckets。reallocate代码如下：

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开辟大小为newCapacity的空间，其实正好是四个bucket_t 指针的空间。allocateBuckets代码：

bucket_t *allocateBuckets(mask_t newCapacity)
{
    // Allocate one extra bucket to mark the end of the list.
    // This can't overflow mask_t because newCapacity is a power of 2.
    bucket_t *newBuckets = (bucket_t *)
        calloc(cache_t::bytesForCapacity(newCapacity), 1);

    bucket_t *end = cache_t::endMarker(newBuckets, newCapacity);

#if __arm__
    // End marker's sel is 1 and imp points BEFORE the first bucket.
    // This saves an instruction in objc_msgSend.
    end->set<NotAtomic, Raw>((SEL)(uintptr_t)1, (IMP)(newBuckets - 1), nil);
#else
    // End marker's sel is 1 and imp points to the first bucket.
    end->set<NotAtomic, Raw>((SEL)(uintptr_t)1, (IMP)newBuckets, nil);
#endif
    
    if (PrintCaches) recordNewCache(newCapacity);

    return newBuckets;
}

得到newBuckets之后返回调用方法setBucketsAndMask初始化并保存:

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask)
{
    uintptr_t buckets = (uintptr_t)newBuckets;
    uintptr_t mask = (uintptr_t)newMask;
    
    ASSERT(buckets <= bucketsMask);
    ASSERT(mask <= maxMask);
    
    _maskAndBuckets.store(((uintptr_t)newMask << maskShift) | (uintptr_t)newBuckets, std::memory_order_relaxed);
    _occupied = 0;
}

这样就得到了新的buckets并且更新到cache_t结构里，然后通过方法buckets()读出来：

 bucket_t *b = buckets()；// 前面创建的buckets

struct bucket_t *cache_t::buckets()
{
    uintptr_t maskAndBuckets = _maskAndBuckets.load(memory_order::memory_order_relaxed);
    return (bucket_t *)(maskAndBuckets & bucketsMask);
}

接下来就通过cache_hash(sel, m)进行哈希计算当前方法存放到buckets的下标：

    mask_t m = capacity - 1;//总容量减1作为掩码
    mask_t begin = cache_hash(sel, m);//哈希算法
    mask_t i = begin;

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}

拿到下标之后判断当前下标是否被占用（fastpath(b[i].sel() == 0)，如果未被占用则直接调用bucket_t存储的set(SEL newSel, IMP newImp, Class cls)方法进行存储，其代码如下：

void bucket_t::set(SEL newSel, IMP newImp, Class cls)
{
    ASSERT(_sel.load(memory_order::memory_order_relaxed) == 0 ||
           _sel.load(memory_order::memory_order_relaxed) == newSel);

    uintptr_t newIMP = (impEncoding == Encoded
                        ? encodeImp(newImp, newSel, cls)
                        : (uintptr_t)newImp);

    if (atomicity == Atomic) {
        _imp.store(newIMP, memory_order::memory_order_relaxed);
        
        if (_sel.load(memory_order::memory_order_relaxed) != newSel) {
#ifdef __arm__
            mega_barrier();
            _sel.store(newSel, memory_order::memory_order_relaxed);
#elif __x86_64__ || __i386__
            _sel.store(newSel, memory_order::memory_order_release);
#else
#error Don't know how to do bucket_t::set on this architecture.
#endif
        }
    } else {
        _imp.store(newIMP, memory_order::memory_order_relaxed);
        _sel.store(newSel, memory_order::memory_order_relaxed);
    }
}

并调用incrementOccupied()对_occupied++；如果已经被占用则先判断是否是同一个sel（b[i].sel() == sel），如果是说明已经存过，如果不是同一个sel则调用i = cache_next(i, m)) != begin继续哈希知道找到满足条件的下标，然后存储。完整代码段：

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

通过对insert方法的分析，可以总结出如下的方法缓存流程：

• 第一次调用顺序如下

1、会通过isConstantEmptyCache()方法判断缓存是否为空 ；
2、第一次进来为空则开辟新的空间，容量为四个字节（capacity = INIT_CACHE_SIZE），并通过方法reallocate创建新的buckets；
3、然后通过cache_hash(sel, m)进行哈希计算当前方法存放到buckets的下标；
4、判断当前下标是否被占用，如果没被占用则直接存储，并调用incrementOccupied()对_occupied++；如果被占用则先判断是否是同一个sel，如果是说明已经存过，如果不是同一个sel则调用i = cache_next(i, m)) != begin继续哈希知道找到满足条件的下标，然后存储。

• 再或多次调用

1、会通过isConstantEmptyCache()方法判断缓存是否为空，不是第一次所以不为空；
2、会判断当前存量是否已经达到总容量的3/4(避免越界)，如果存量还没达到3/4，则走第一次调用的3、4步骤；如果存量已经达到或超过3/4，则会对缓存进行2倍扩容，然后走第一次调用的3、4步骤；

方法缓存什么时候写入？如何读取？

方法调用的时候会在底层调用id objc_msgSend(id self, SEL _cmd, ...)函数进行消息发送，然后根据当前对象的isa指针通过位运算获取当前类的指针，再通过指针平移找到类的cache_t cache，然后再利用bucketsMask和_maskAndBuckets通过位运算得到相应的buckets指针，然后再通过SEL _cmd和对应的mask做位运算得到一个index，先通过index在buckets中读取出sel，如果跟当前的_cmd一致那就返回，如果不一致就跳到buckets的末尾，通过指针平移从后往前查找（可能是因为存的时候大方向是从前往后的，当然不一定是按顺序存储），找到返回，找不到就到类的方法列表中查找，同时写入cache。查找类方法也是一样的，只不过类对象的类变成了元类。