cache_t的結構

struct objc_class : objc_object {
    // Class ISA;  繼承自objc_object  //8
    Class superclass;  //8
    cache_t cache;  //16           // formerly cache pointer and vtable
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags
   
    ...
}

在上一篇類的結構分析中， 我們從類的結構體源碼中看到，類中存有一個cache_t cache(方法緩存)，但是沒有做具體分體分析，這篇博客就來具體分析一下cache_t 。
先來看一下cache_t的源碼結構：

struct cache_t {
    struct bucket_t *_buckets;
    mask_t _mask;
    mask_t _occupied;

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: 一個存放bucket_t 結構體的數(shù)組，用來存放緩存方法的imp和緩存的key。
_mask：緩存數(shù)組的大小
_occupied：當前已緩存的方法數(shù)

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

using MethodCacheIMP = IMP;
typedef uintptr_t cache_key_t;

//獲取key
cache_key_t getKey(SEL sel) 
{
    assert(sel);
    return (cache_key_t)sel;
}

_imp: 緩存的方法的imp。
_key: 有sel強轉而來，其實就是SEL的內(nèi)存地址。

了解完了cache_t的結構，我們通過代碼來驗證一下，實際的類中的cache_t是否如我們分析的一樣呢？我們創(chuàng)建一個簡單的person對象，然后調(diào)用一下它的sayHappy方法，然后進入斷點調(diào)試：

image.png

在控制臺做如下輸出：

//打印person的類對象的內(nèi)存地址
(lldb) x/4gx person.class
0x100002518: 0x001d8001000024f1 0x0000000100b37140
0x100002528: 0x0000000100fc4320 0x0000000300000003

//根據(jù)內(nèi)存便宜找到cache_t并打印cache_t的指針
(lldb) p (cache_t *)0x100002528
(cache_t *) $1 = 0x0000000100002528

//打印cache_t
(lldb) p *$1
(cache_t) $2 = {
  _buckets = 0x0000000100fc4320
  _mask = 3
  _occupied = 3
}

//打印_buckets的指針
(lldb) p $2._buckets
(bucket_t *) $3 = 0x0000000100fc4320

//打印_buckets指針指向的地址，也就是_buckets的第一個元素。
(lldb) p *$3
(bucket_t) $4 = {
  _key = 4294974988
  _imp = 0x0000000100001a20 (LGTest`-[ZPerson sayHello] at main.m:124)
}

我們發(fā)現(xiàn)打印出的sayHello方法，正式在上面調(diào)用的[person sayHello]。說明cache_t里確實緩存了我們曾經(jīng)調(diào)用過的方法。那么cache_t是如何進行方法的緩存的呢？請繼續(xù)往下看。

cache_t的緩存查找

在cache_t的結構體里我們看到有這樣一個方法：

struct bucket_t * find(cache_key_t key, id receiver);

點進去看它的具體實現(xiàn)：

bucket_t * cache_t::find(cache_key_t k, id receiver)
{
    assert(k != 0);
    //取出當前cache_t的buckets
    bucket_t *b = buckets();
    //取出當前cache_t的mask
    mask_t m = mask();
    // 通過cache_hash函數(shù)【begin  = k & m】計算出key值 k 對應的 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);
    
   //如果此時還沒有找到key對應的bucket_t，或者是空的bucket_t，則循環(huán)結束，說明查找失敗，調(diào)用bad_cache方法。
    Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
    cache_t::bad_cache(receiver, (SEL)k, cls);

這個方法的作用就是根據(jù)傳進來的key遍歷查找buckets，然后返回存有方法imp的bucket_t。這個方法應該屬于查找流程中的一個過程。我們再在源碼中全局搜索一下，是誰什么時候調(diào)用了這個方法。

我們在cache_fill_nolock方法中找到了find方法調(diào)用。先貼一下cache_fill_nolock方法的源碼實現(xiàn)，在具體分析一下方法里具體干了啥。

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;

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

1、cache_fill_nolock方法傳進來4個參數(shù)：類cls、方法的sel、方法的imp和方法的調(diào)用者。
2、加一把cacheUpdateLock。
3、然后進行一下安全檢查。
4、取出cls中的cahce。
5、根據(jù)sel生成相對應的key。
6、取出當前cache緩存方法的個數(shù)，然后加1，得到newOccupied，新的緩存方法個數(shù)。
7、得到當前cache的最大容量。
8、進行總容量與緩存?zhèn)€數(shù)的判斷：
a.當前cache里面是空的，調(diào)用reallocate開去開辟新的buckets賦值的當前的cache_t
b.當前緩存?zhèn)€數(shù)小于總容量的3/4，不做操作
c.當前緩存?zhèn)€數(shù)不小于總容量的3/4，就調(diào)用expand()去擴容。
9、調(diào)用cache的find方法查找緩存
10、如果沒找到，將已緩存的數(shù)目occupied加1，再將key和imp存入bucket

關于expand()擴容方法，我們在看一下它的實現(xiàn)源碼：

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    
    uint32_t oldCapacity = capacity();
    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;
    }

    reallocate(oldCapacity, newCapacity);
}

我們可以看到，方法中先去取了一下舊的容量大小oldCapacity，然后將oldCapacity乘以2，也就是將oldCapacity擴大了一倍，得到新的容量大小newCapacity。在調(diào)用reallocate()去進行內(nèi)存的開辟，需要將oldCapacity和newCapacity作為參數(shù)傳遞進去。
我們再看一下reallocate()方法的源碼：

{
    bool freeOld = canBeFreed();
      
    //獲取原來的buckets
    bucket_t *oldBuckets = buckets();
    //根據(jù)新的容量大小，創(chuàng)新出新的newBuckets，這個newBuckets是空的
    bucket_t *newBuckets = allocateBuckets(newCapacity);

    assert(newCapacity > 0);
    assert((uintptr_t)(mask_t)(newCapacity-1) == newCapacity-1);
   
    //將新的newCapacity-1作為新的mask大小，再將_buckets和mask存入cache_t，并將occupied置為0
    setBucketsAndMask(newBuckets, newCapacity - 1);
    //將舊的buckets釋放
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false);
    }
}

根據(jù)上面源碼的注釋，我們可以知道reallocate()方法具體做了哪些操作。然后我們再看一下系統(tǒng)都在哪些方法調(diào)用了reallocate()。根據(jù)全局搜索可以找到，有兩處代碼進行了reallocate()方法的調(diào)用。一個是cache_t為空，第一次開辟的時候，再有就就是調(diào)用expand()方法進行擴容的時候。

image.png

關于cache_fill_nolock我們已經(jīng)分析的差不多了。接下來我們再找找哪里調(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
}

找到cache_fill方法調(diào)用了cache_fill_nolock。再繼續(xù)查找，找到lookUpImpOrForward，lookupMethodInClassAndLoadCache兩個方法。根據(jù)方法名可以知道，當進行方法調(diào)用的時候，會進行cache_filll，也就是填充方法緩存。關于方法的調(diào)用，我們后面的博客再將。關于cache_t的分析基本上就是這些了。最后附上一張流程圖，方便理清思路。

cache_t流程圖.png