在類的結(jié)構(gòu)分析一文中提到過cache_t,但并未對其進(jìn)行具體的分析,今天我們就一起看看iOS中的方法緩存在底層是如何實現(xiàn)的.

cache_t結(jié)構(gòu)體

struct cache_t {
    struct bucket_t *_buckets;//結(jié)構(gòu)體指針,緩存放在這里面
    mask_t _mask;//在64位下為uint32_t類型,代表總的可以緩存的方法數(shù)量
    mask_t _occupied;//當(dāng)前已緩存的方法數(shù)量

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

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

由bucket_t的結(jié)構(gòu)可知:在arm64的環(huán)境下,存儲的為_imp方法的實現(xiàn)和相應(yīng)的_key.

源碼流程分析

如果我們要找方法的緩存,那么我們就要先找到struct bucket_t *_buckets結(jié)構(gòu)體指針,那么我們該如何尋找呢?接下來我們就一步步踏上尋找_buckets之旅.
首先在cache_t的結(jié)構(gòu)體中我們看到了 _mask,并且在緩存方法中我們看到一個mask()函數(shù),查看mask()方法我們發(fā)現(xiàn)其只是返回了一個_mask,并未對_mask的值進(jìn)行操作;

mask_t cache_t::mask() 
{
    return _mask; 
}

通過全局搜索mask()方法,我們發(fā)現(xiàn)在capacity()方法中調(diào)用了mask()方法,但具體作用并不知道;

mask_t cache_t::capacity() 
{
    return mask() ? mask()+1 : 0; 
}

繼續(xù)對capacity()方法進(jìn)行全局搜索,發(fā)現(xiàn)在expand()方法中調(diào)用了該方法:

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();//斷言
    
    uint32_t oldCapacity = capacity();//舊的容量,
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;//如果oldCapacity為0,此時就為INIT_CACHE_SIZE也就是4,如果不為0,則newCapacity為oldCapacity的兩倍

    if ((uint32_t)(mask_t)newCapacity != newCapacity) {
        // mask overflow - can't grow further
        // fixme this wastes one bit of mask
        newCapacity = oldCapacity;
    }

    reallocate(oldCapacity, newCapacity);
}

enum {
    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2)//將1左移兩位也就是4
};

只從字面意思我們看出: expand(擴(kuò)容), capacity(容量),既然需要擴(kuò)容,就肯定需要一定的條件,那么我們就看看在什么時候,開始進(jìn)行擴(kuò)容,通過搜索我們發(fā)現(xiàn)在cache_fill_nolock方法中調(diào)用了expand():

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

    // Never cache before +initialize is done
    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;//從緩存中得到imp,如果拿到就直接返回,沒有就繼續(xù)走下面的方法

    cache_t *cache = getCache(cls);//獲取緩存
    cache_key_t key = getKey(sel);//通過sel拿到相應(yīng)的key,是一個哈希表

    // Use the cache as-is if it is less than 3/4 full
    mask_t newOccupied = cache->occupied() + 1;//創(chuàng)建一個newOccupied
    mask_t capacity = cache->capacity();
   //如果是空就直接創(chuàng)建
    if (cache->isConstantEmptyCache()) {
        // Cache is read-only. Replace it.
        cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
    }
    //判斷是逗超出3/4臨界點,如果超出就需要進(jìn)行擴(kuò)容操作
    else if (newOccupied <= capacity / 4 * 3) {
        // Cache is less than 3/4 full. Use it as-is.
    }
    else {
        //擴(kuò)容到原來的兩倍
        // 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);//通過key找到相應(yīng)的bucket
    if (bucket->key() == 0) cache->incrementOccupied();
    bucket->set(key, imp);
}

由上面的分析我們可以看出如果cache為空則會調(diào)用reallocate()方法,如果容量大于3/4則需要進(jìn)行擴(kuò)容操作

reallocate分析

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    bool freeOld = canBeFreed();//根據(jù)isConstantEmptyCache判斷是否釋放舊的緩存

    bucket_t *oldBuckets = buckets();//獲取舊的buckets
    bucket_t *newBuckets = allocateBuckets(newCapacity);//創(chuàng)建新的buckets

    // 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);//將newCapacity-1作為參數(shù)傳入setBucketsAndMask方法中進(jìn)行賦值
    
    if (freeOld) {//清理舊緩存
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false);
    }
}

bool cache_t::canBeFreed()
{
    return !isConstantEmptyCache();
}

setBucketsAndMask分析

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.

    // ensure other threads see buckets contents before buckets pointer
    mega_barrier();

    _buckets = newBuckets;
    
    // ensure other threads see new buckets before new mask
    mega_barrier();
    
    _mask = newMask;//由reallocate方法我們可以知道此時的_mask值實際上為新擴(kuò)容后的容量減1 
    _occupied = 0;
}

由setBucketsAndMask源碼可以看出:該方法實際就是對_buckets, _mask,_occupied進(jìn)行賦值操作;

find()

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

至此,我們大致梳理出了cache_t的基本流程,其大致流程如下:

cache_t流程圖.jpg

實例驗證

創(chuàng)建一個Student的類

@interface Student : NSObject

- (void)study;

- (void)eat;

- (void)play;

@end

只調(diào)用Student中的一個方法時:

Student *student = [Student alloc];
        Class sClass = [Student class];
        [student study];

通過LLDB進(jìn)行調(diào)試

(lldb) x/4gx sClass
0x1000013c8: 0x001d8001000013a1 0x0000000100b36140
0x1000013d8: 0x0000000101938eb0 0x0000000100000003
(lldb) p (cache_t *)0x1000013d8//根據(jù)地址偏移拿到cache_t
(cache_t *) $1 = 0x00000001000013d8
(lldb) p *$1
(cache_t) $2 = {
  _buckets = 0x0000000101938eb0
  _mask = 3//根據(jù)我們上面分析, 一開始o(jì)ldCapacity為0, newCapacity則為4, _mask在賦值的等于newCapacity-1,因此_mask為3
  _occupied = 1 
}
(lldb) p $2._buckets
(bucket_t *) $3 = 0x0000000101938eb0
(lldb) p *$3
(bucket_t) $4 = {
  _key = 4294971012
  _imp = 0x0000000100000dd0 (LGTest`-[Student study] at Student.m:12)
}

調(diào)用4個Student中的方法時:

        Student *student = [[Student alloc] init];
        Class sClass = [Student class];
        [student study];
        [student eat];
        [student play];

通過LLDB進(jìn)行調(diào)試

(lldb) x/4gx sClass
0x1000013e0: 0x001d8001000013b9 0x0000000100b36140
0x1000013f0: 0x0000000100f5b810 0x0000000100000007
(lldb) p (cache_t *)0x1000013f0
(cache_t *) $1 = 0x00000001000013f0
(lldb) p *$1
(cache_t) $2 = {
  _buckets = 0x0000000100f5b810
  _mask = 7//由擴(kuò)容我們可知此時3勢必?zé)o法滿足四個方法的緩存,需要擴(kuò)容,我們知道oldCapacity上次為4, newCapacity則為8, _mask= newCapacity-1 = 7
  _occupied = 1//代表當(dāng)前緩存一個
}
(lldb) p $2._buckets
(bucket_t *) $3 = 0x0000000100f5b810
(lldb) p *$3
(bucket_t) $4 = {
  _key = 0
  _imp = 0x0000000000000000
}
(lldb) p $2._buckets[0]
(bucket_t) $5 = {
  _key = 0
  _imp = 0x0000000000000000
}
(lldb) p $2._buckets[1]
(bucket_t) $6 = {
  _key = 0
  _imp = 0x0000000000000000
}
(lldb) p $2._buckets[2]
(bucket_t) $7 = {
  _key = 140735178921514
  _imp = 0x0000000100000de0 (LGTest`-[Student play] at Student.m:20)
}
(lldb) p $2._buckets[3]
(bucket_t) $8 = {
  _key = 0
  _imp = 0x0000000000000000
}
(lldb) p $2._buckets[4]
(bucket_t) $9 = {
  _key = 0
  _imp = 0x0000000000000000
}
(lldb) p $2._buckets[5]
(bucket_t) $10 = {
  _key = 0
  _imp = 0x0000000000000000
}
(lldb) p $2._buckets[6]
(bucket_t) $11 = {
  _key = 0
  _imp = 0x0000000000000000
}
(lldb) p $2._buckets[7]
(bucket_t) $12 = {
  _key = 0
  _imp = 0x0000000000000000
}

通過打印:我們發(fā)現(xiàn)當(dāng)前的緩存方法只有最后一個調(diào)用的play方法,那么init, study, eat,哪去了呢?在reallocate方法中我們判斷了freeOld,清理了舊的緩存,當(dāng)4個方法的時候其實是調(diào)用了兩次reallocate,第一次cache為空時調(diào)用了一次reallocate此時將_mask置為3,當(dāng)明顯4個方法_mask為3不夠用,因此會調(diào)用擴(kuò)容方法再次調(diào)用reallocate方法,將_mask緩存數(shù)量置為7,并清理舊的緩存,這也就是為什么當(dāng)前緩存數(shù)量為1,且只存在play方法.

總結(jié):

Class中的Cache主要是為了在消息發(fā)送的過程中，進(jìn)行方法的緩存，加快調(diào)用效率，其中使用了動態(tài)擴(kuò)容的方法，當(dāng)容量達(dá)到最大值的3/4時，開始2倍擴(kuò)容，擴(kuò)容時會完全抹除舊的buckets，并且創(chuàng)建新的buckets代替，之后把最近一次臨界的imp和key緩存進(jìn)來.