前言

從前面一篇文章類的原理探究中，我們可以看到類的結(jié)構(gòu)如下：

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

并且我們在上一篇文章中已經(jīng)探索了類的bits數(shù)據(jù)結(jié)構(gòu)，今天我們來看一下類的cache_t的結(jié)構(gòu)

開始探究

1.cache_t數(shù)據(jù)結(jié)構(gòu)

通過LLDB輸出cache_t的結(jié)構(gòu)如下：

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

那bucket_t結(jié)構(gòu)是啥呢？

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里面存儲(chǔ)的就是方法的SEL與IMP，那么怎么驗(yàn)證呢，我們從cache_t結(jié)構(gòu)體中可以看到它提供了一個(gè)struct bucket_t *buckets() const;buckets()函數(shù)，
所以下面我們通過LLDB獲取一下bucket_t數(shù)據(jù)如下：

但是一看，里面數(shù)據(jù)為空啊，所以我們調(diào)用一下類的對(duì)象方法，然后用LLDB輸出bucket_t的sel與imp

所以cache_t是針對(duì)于方法進(jìn)行緩存。并且它的數(shù)據(jù)結(jié)構(gòu)是

struct cache_t {
private:
    explicit_atomic<uintptr_t> _bucketsAndMaybeMask; // 存儲(chǔ)的是buckets地址與maybeMask
    union {
        struct {
            explicit_atomic<mask_t>    _maybeMask; // maybeMask是開辟的大小-1
#if __LP64__
            uint16_t                   _flags;   
#endif
            uint16_t                   _occupied; // 緩存的方法數(shù)量
        };
        explicit_atomic<preopt_cache_t *> _originalPreoptCache; 
    };

2. sel與imp緩存的插入與讀取

在cache_t結(jié)構(gòu)中有一個(gè)insert方法，下面我們來看一下insert方法。

void cache_t::insert(SEL sel, IMP imp, id receiver)
{ 
   // Use the cache as-is if until we exceed our expected fill ratio.
   //如果超過了預(yù)期的填充比率，就按原樣使用緩存。
    mask_t newOccupied = occupied() + 1; // 1+1
    unsigned oldCapacity = capacity(), capacity = oldCapacity;
    if (slowpath(isConstantEmptyCache())) {
        // Cache is read-only. Replace it.
        if (!capacity) capacity = INIT_CACHE_SIZE;//4，開辟的大小
        reallocate(oldCapacity, capacity, /* freeOld */false);
    }
    else if (fastpath(newOccupied + CACHE_END_MARKER <= cache_fill_ratio(capacity))) {
        // 緩存小于3/4或7/8。按原樣使用它。
    }
#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 {// 4*2 = 8
        capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE; //當(dāng)緩存使用超過3/4的時(shí)候進(jìn)行兩倍擴(kuò)容。
        if (capacity > MAX_CACHE_SIZE) {
            capacity = MAX_CACHE_SIZE;
        }
        reallocate(oldCapacity, capacity, true);
    }

    bucket_t *b = buckets();//讀取已有的緩存
    mask_t m = capacity - 1; // 4-1=3
    mask_t begin = cache_hash(sel, m);//類指向緩存。SEL是key。buckets緩存SEL+IMP。緩存從來沒有建立在dyld共享緩存。     
    mask_t i = begin;//插入位置

    // Scan for the first unused slot and insert there.
    // There is guaranteed to be an empty slot.
    // 掃描第一個(gè)未使用的插槽并在那里插入。
    //保證有一個(gè)空槽。
    do {
        if (fastpath(b[i].sel() == 0)) {//如果有空的位置，進(jìn)行sel與imp插入
            incrementOccupied(); //occupied =  occupied + 1
            b[i].set<Atomic, Encoded>(b, sel, imp, cls());
            return;
        }
        if (b[i].sel() == sel) { //緩存已經(jīng)插入了，就不再插入了
            // 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_next(i, m)避免哈希沖突
    bad_cache(receiver, (SEL)sel);
}
#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;
}
#else

總結(jié)一下就是：

1.就是先開辟一個(gè)bucket_t哈希表，并且將buckets地址與_maybeMask存儲(chǔ)在cache_t結(jié)構(gòu)體的_bucketsAndMaybeMask變量中。_maybeMask = capacity -1，capacity是開辟空間的大小。

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) {
        collect_free(oldBuckets, oldCapacity);
    }
}

2.檢查buckets使用率是否小于3/4,如果大于3/4就進(jìn)行2倍擴(kuò)容

capacity = capacity ? capacity * 2 : INIT_CACHE_SIZE;//capacity開辟的大小

3.找到空的位置插入sel+imp

 if (fastpath(b[i].sel() == 0)) {
        incrementOccupied();
        b[i].set<Atomic, Encoded>(b, sel, imp, cls());
        return;
}

接下來看一下imp與sel的讀取，也就是查看一下buckets()函數(shù)的實(shí)現(xiàn)，然后在查看bucket_t結(jié)構(gòu)體里面提供的方法。

struct bucket_t *cache_t::buckets() const
{
    uintptr_t addr = _bucketsAndMaybeMask.load(memory_order_relaxed);
    return (bucket_t *)(addr & bucketsMask);
}
struct bucket_t {
inline SEL sel() const { return _sel.load(memory_order_relaxed); }
inline IMP imp(UNUSED_WITHOUT_PTRAUTH bucket_t *base, Class cls) const 
}

bucketsMask是啥呢？

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_OUTLINED
    // _bucketsAndMaybeMask 是 buckets_t 指針
    // _maybeMask is the buckets mask
    static constexpr uintptr_t bucketsMask = ~0ul; //18446744073709551615
    static_assert(!CONFIG_USE_PREOPT_CACHES, "preoptimized caches not supported");
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
    static constexpr uintptr_t maskShift = 48;
    static constexpr uintptr_t maxMask = ((uintptr_t)1 << (64 - maskShift)) - 1;
    static constexpr uintptr_t bucketsMask = ((uintptr_t)1 << maskShift) - 1;
    
    static_assert(bucketsMask >= MACH_VM_MAX_ADDRESS, "Bucket field doesn't have enough bits for arbitrary pointers.");
#if CONFIG_USE_PREOPT_CACHES
    static constexpr uintptr_t preoptBucketsMarker = 1ul;
    static constexpr uintptr_t preoptBucketsMask = bucketsMask & ~preoptBucketsMarker;
#endif
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    // _bucketsAndMaybeMask是一個(gè)低48位的buckets_t指針
    // _maybeMask未使用時(shí)，掩碼存儲(chǔ)在前16位。
    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.");

#if CONFIG_USE_PREOPT_CACHES
    static constexpr uintptr_t preoptBucketsMarker = 1ul;
#if __has_feature(ptrauth_calls)
    // 63..60: hash_mask_shift
    // 59..55: hash_shift
    // 54.. 1: buckets ptr + auth
    //      0: always 1
    static constexpr uintptr_t preoptBucketsMask = 0x007ffffffffffffe;
    static inline uintptr_t preoptBucketsHashParams(const preopt_cache_t *cache) {
        uintptr_t value = (uintptr_t)cache->shift << 55;
        // masks have 11 bits but can be 0, so we compute
        // the right shift for 0x7fff rather than 0xffff
        return value | ((objc::mask16ShiftBits(cache->mask) - 1) << 60);
    }
#else
    // 63..53: hash_mask
    // 52..48: hash_shift
    // 47.. 1: buckets ptr
    //      0: always 1
    static constexpr uintptr_t preoptBucketsMask = 0x0000fffffffffffe;
    static inline uintptr_t preoptBucketsHashParams(const preopt_cache_t *cache) {
        return (uintptr_t)cache->hash_params << 48;
    }
#endif
#endif // CONFIG_USE_PREOPT_CACHES
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
    // _bucketsAndMaybeMask is a buckets_t pointer in the top 28 bits
    // _maybeMask is unused, the mask length is stored in the low 4 bits

    static constexpr uintptr_t maskBits = 4;
    static constexpr uintptr_t maskMask = (1 << maskBits) - 1;
    static constexpr uintptr_t bucketsMask = ~maskMask;
    static_assert(!CONFIG_USE_PREOPT_CACHES, "preoptimized caches not supported");
#else

我在x86_64上面運(yùn)行，bucketsMask = ~0ul，_bucketsAndMaybeMask是buckets_t的指針，驗(yàn)證如下：

總結(jié)

用兩張圖來總結(jié)一下cache_t結(jié)構(gòu)與方法緩存的流程