OC類底層探索 — 方法緩存cache_t

前言

從之前對類的探索，還剩下類對象 objc_class 的成員 cache 沒有探索笙瑟〉莸荩看名字我們知道它是緩存喷橙，下面我們通過源碼研究一下。

struct objc_class : objc_object {
    // Class ISA; // 8
    Class superclass; // 8
    cache_t cache;    // 16 不是8         // formerly cache pointer and vtable
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags

    class_rw_t *data() { 
        return bits.data();
    }

    // ...省略...

一登舞、cache_t 源碼分析

1. cache_t 基本結(jié)構(gòu)

struct cache_t {
    struct bucket_t *_buckets; // 8
    mask_t _mask;  // 4
    mask_t _occupied; // 4

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

    mask_t capacity();
    bool isConstantEmptyCache();
    bool canBeFreed();

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

    void expand();
    void reallocate(mask_t oldCapacity, mask_t newCapacity);
    struct bucket_t * find(cache_key_t key, id receiver);

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

_buckets：數(shù)組贰逾，是bucket_t結(jié)構(gòu)體的數(shù)組，bucket_t是用來存放方法的SEL內(nèi)存地址和IMP的

_mask：的大小是數(shù)組大小 - 1菠秒，用作掩碼似踱。（因為這里維護(hù)的數(shù)組大小都是2的整數(shù)次冪，所以_mask的二進(jìn)制位000011, 000111, 001111）剛好可以用作hash取余數(shù)的掩碼稽煤。剛好保證相與后不超過緩存大小核芽。

_occupied：當(dāng)前已緩存的方法數(shù)，緩存數(shù)組中已使用的容量酵熙。

2. 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__
    MethodCacheIMP _imp;
    cache_key_t _key;
#else
    cache_key_t _key;
    MethodCacheIMP _imp;
#endif

public:
    inline cache_key_t key() const { return _key; }
    inline IMP imp() const { return (IMP)_imp; }
    inline void setKey(cache_key_t newKey) { _key = newKey; }
    inline void setImp(IMP newImp) { _imp = newImp; }

    void set(cache_key_t newKey, IMP newImp);
};

_imp：函數(shù)調(diào)用地址轧简，方法實現(xiàn)IMP
cache_key_t _key： _key實際就是sel強轉(zhuǎn)(cache_key_t)sel，把sel方法名字轉(zhuǎn)為十進(jìn)制匾二。

通過觀察 arm64 中哮独，存的是MethodCacheIMP _imp拳芙、cache_key_t _key，這些屬性證明緩存的就是方法皮璧。

二舟扎、cache_t 緩存方法的流程

1. 緩存入口

點擊cache_t中的public函數(shù)，會進(jìn)入到objc-cache.mm源碼中悴务，在最上邊會看到這樣一段說明：

/* 
 *Cache readers (PC-checked by collecting_in_critical())
 * objc_msgSend*
 * cache_getImp
 * 
 * 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)
*/

緩存的讀寫睹限，以及需要調(diào)用的方法順序，那么我們先從寫入 Cache writers 來看讯檐。
首先就是 cache_fill羡疗。

2. cache_fill

查看 cache_fill 源碼，我們發(fā)現(xiàn)主要是調(diào)用了 cache_fill_nolock 方法：

void cache_fill(Class cls, SEL sel, IMP imp, id receiver)
{
#if !DEBUG_TASK_THREADS
    mutex_locker_t lock(cacheUpdateLock);
    cache_fill_nolock(cls, sel, imp, receiver);
#else
    _collecting_in_critical();
    return;
#endif
}

3. cache_fill_nolock

static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
    cacheUpdateLock.assertLocked();

    // Never cache before +initialize is done
    // 沒有初始化的緩存直接return
    if (!cls->isInitialized()) return;
    
    // Make sure the entry wasn't added to the cache by some other thread 
    // before we grabbed the cacheUpdateLock.
    if (cache_getImp(cls, sel)) return;

    cache_t *cache = getCache(cls);
    cache_key_t key = getKey(sel);

    // Use the cache as-is if it is less than 3/4 full
    mask_t newOccupied = cache->occupied() + 1;
    mask_t capacity = cache->capacity();
    if (cache->isConstantEmptyCache()) {
        // Cache is read-only. Replace it.
        cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
    }
    else if (newOccupied <= capacity / 4 * 3) {
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        // Cache is too full. Expand it.
        cache->expand();
    }

    // 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.
    bucket_t *bucket = cache->find(key, receiver);
    if (bucket->key() == 0) cache->incrementOccupied();
    bucket->set(key, imp);
}

cache_getImp

if (cache_getImp(cls, sel)) return;
判斷當(dāng)前cls下的sel是否已經(jīng)被緩存了别洪，如果已經(jīng)有緩存直接返回叨恨。確保緩存沒有被其他線程寫入，才能進(jìn)行接下來的填充緩存的操作挖垛。

getCache

cache_t *cache = getCache(cls);
獲取當(dāng)前類的緩存痒钝，內(nèi)部實現(xiàn)如下：

cache_t *getCache(Class cls) 
{
    assert(cls);
    return &cls->cache;
}

getKey

cache_key_t key = getKey(sel);
通過sel方法獲取緩存key，其實就是一個類型的強轉(zhuǎn)痢毒，內(nèi)部實現(xiàn)如下：

cache_key_t getKey(SEL sel) 
{
    assert(sel);
    return (cache_key_t)sel;
}

mask_t newOccupied = cache->occupied() + 1;

在已占用內(nèi)存occupied的基礎(chǔ)上 +1送矩，得到新的緩存占用大小newOccupied。

mask_t capacity = cache->capacity();

獲取當(dāng)前hash表的容量闸准，也就是總?cè)萘看笮　?/p>

cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);

判斷緩存是否為空；如果緩存為空梢灭，重新開辟空間夷家，最少4字節(jié)

if (cache->isConstantEmptyCache()) {
    cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
}

// 1左移兩位，也就是4字節(jié)
enum {
    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2)
};

reallocate：重新開辟緩存空間

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    // 是否需要釋放舊緩存
    bool freeOld = canBeFreed();

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

    // 設(shè)置新的buckets和mask
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    // 釋放舊緩存
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false);
    }
}

cache->expand();

判斷newOccupied大于總?cè)萘康?/4敏释，走expand()進(jìn)行緩存擴(kuò)容库快，小于等于3/4仍使用現(xiàn)有緩存空間。

else if (newOccupied <= capacity / 4 * 3) {
    // Cache is less than 3/4 full. Use it as-is.
} else {
    cache->expand();
}

expand：擴(kuò)容

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    // 舊緩存空間
    uint32_t oldCapacity = capacity(); 
    // 擴(kuò)容為二倍舊的緩存空間
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE; 

    if ((uint32_t)(mask_t)newCapacity != newCapacity) {
        // mask overflow - can't grow further
        // fixme this wastes one bit of mask
        newCapacity = oldCapacity;
    }
    // 重新開辟內(nèi)存
    reallocate(oldCapacity, newCapacity);
}

最后把新調(diào)用的方法添加到緩存中钥顽，并存儲key和imp

// 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.
bucket_t *bucket = cache->find(key, receiver); // 找到桶
if (bucket->key() == 0) cache->incrementOccupied(); // 如果key==0則說明之前未存儲過這個key义屏，占用空間+1
bucket->set(key, imp); // 存儲 key和imp 到bucket

3. ·find() 查找緩存key

bucket_t * cache_t::find(cache_key_t k, id receiver)
{
    assert(k != 0);

    bucket_t *b = buckets();
    mask_t m = mask();
    // 通過cache_hash函數(shù)【begin  = k & m】計算出key值 k 對應(yīng)的 index值 begin，用來記錄查詢起始索引
    mask_t begin = cache_hash(k, m);
    // begin 賦值給 i蜂大，用于切換索引
    mask_t i = begin;
    do {
        if (b[i].key() == 0  ||  b[i].key() == k) {
            //用這個i從散列表取值闽铐，如果取出來的bucket_t的 key = k，則查詢成功奶浦，返回該bucket_t兄墅，
            //如果key = 0，說明在索引i的位置上還沒有緩存過方法澳叉，同樣需要返回該bucket_t隙咸，用于中止緩存查詢沐悦。
            return &b[i];
        }
    } while ((i = cache_next(i, m)) != begin);
    // 這一步其實相當(dāng)于 i = i-1,回到上面do循環(huán)里面，相當(dāng)于查找散列表上一個單元格里面的元素五督，再次進(jìn)行key值 k的比較藏否，
    //當(dāng)i=0時，也就i指向散列表最首個元素索引的時候重新將mask賦值給i充包，使其指向散列表最后一個元素副签，重新開始反向遍歷散列表，
    //其實就相當(dāng)于繞圈误证，把散列表頭尾連起來继薛，不就是一個圈嘛，從begin值開始愈捅，遞減索引值遏考，當(dāng)走過一圈之后，必然會重新回到begin值蓝谨，
    //如果此時還沒有找到key對應(yīng)的bucket_t灌具，或者是空的bucket_t，則循環(huán)結(jié)束譬巫，說明查找失敗咖楣，調(diào)用bad_cache方法。
 
    // hack
    Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
    cache_t::bad_cache(receiver, (SEL)k, cls);
}

mask_t begin = cache_hash(s, m);

static inline mask_t cache_hash(cache_key_t key, mask_t mask) 
{
    return (mask_t)(key & mask);
}

cache_hash(s, m) 是 hash 算法芦昔，bucket_t里邊緩存的實際上就是一個hash表诱贿，可以看做是 key：value 的結(jié)構(gòu)，begin是查詢的起始索引咕缎。

do...white

閉環(huán)查找珠十，如果取出來的 key = k，則查詢成功凭豪，返回該bucket_t焙蹭；
如果 key = 0，說明在索引 i 的位置上還沒有緩存過方法嫂伞，同樣需要返回該 bucket_t孔厉，用于中止緩存查詢。

do {
    if (b[i].key() == 0  ||  b[i].key() == k) {
        return &b[i];
    }
} while ((i = cache_next(i, m)) != begin);

static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}

三帖努、總結(jié)

實例方法緩存在類中撰豺，類方法緩存在元類中

方法緩存是以 hash表 的形式存儲

cache_t 當(dāng)前使用緩存空間在大于3/4時會進(jìn)行擴(kuò)容，擴(kuò)容時會抹除舊的 buckets 創(chuàng)建新的二倍當(dāng)前空間拼余，然后把最近一次的臨界方法緩存進(jìn)來

緩存方法是為了最大化提高程序的執(zhí)行效率