背景：

我們知道oc調(diào)用方法是objc_send_message，具體流程就是疮跑，去isa指針?biāo)傅念惢蛟悓?duì)象的對(duì)應(yīng)的方法緩存cache_t中查找身弊，如果在緩存中找到雾狈，則直接返回對(duì)應(yīng)IMP；如果沒找到母怜，則去類或元類的方法類表中查找余耽，找到了，返回IMP苹熏，并保存到對(duì)應(yīng)的cache_t中碟贾，便于下次查找使用；如果在類或元類的方法列表也沒找到轨域，則進(jìn)入消息解析轉(zhuǎn)發(fā)流程袱耽，直到unrecognized selector sent to instance。
方法的查找是需要速度的疙挺，為了速度扛邑，就有查找流程中的緩存，所以我們有必要了解cache_t铐然。

類結(jié)構(gòu)

我們知道object-c的類Class的底層實(shí)現(xiàn)是一個(gè)object_class的結(jié)構(gòu)體如下：

struct objc_class : objc_object {//繼承objc_object蔬崩，objc_object對(duì)應(yīng)oc就是實(shí)例對(duì)象，從這點(diǎn)講搀暑，類也是對(duì)象沥阳，萬物皆對(duì)象
    // Class ISA;//isa指針
    Class superclass;//指向父類的指針
    cache_t cache;             //  方法緩存列表
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags 類的其他信息數(shù)據(jù)，例如自点，屬性桐罕、方法、協(xié)議等
    ...
}

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

struct cache_t {
    struct bucket_t *_buckets;///存儲(chǔ)方法的類表桂敛，hash表
    mask_t _mask;//hash算法使用到的鹽
    mask_t _occupied;//列表中也被占用的位置數(shù)
    ...
}

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__//iOS
    uintptr_t _imp;//函數(shù)指針I(yè)MP
    SEL _sel;//selector
#else
    SEL _sel;
    uintptr_t _imp;
#endif
    ...
}

既然是緩存列表功炮，就有更新（寫入），查（讀仁趸！）等邏輯薪伏，有一段官方文字如下：

Method cache locking (GrP 2001-1-14)
 *
 * For speed, objc_msgSend does not acquire any locks when it reads 
 * method caches. Instead, all cache changes are performed so that any 
 * objc_msgSend running concurrently with the cache mutator will not 
 * crash or hang or get an incorrect result from the cache. 
 *
 * When cache memory becomes unused (e.g. the old cache after cache 
 * expansion), it is not immediately freed, because a concurrent 
 * objc_msgSend could still be using it. Instead, the memory is 
 * disconnected from the data structures and placed on a garbage list. 
 * The memory is now only accessible to instances of objc_msgSend that 
 * were running when the memory was disconnected; any further calls to 
 * objc_msgSend will not see the garbage memory because the other data 
 * structures don't point to it anymore. The collecting_in_critical
 * function checks the PC of all threads and returns FALSE when all threads 
 * are found to be outside objc_msgSend. This means any call to objc_msgSend 
 * that could have had access to the garbage has finished or moved past the 
 * cache lookup stage, so it is safe to free the memory.
 *
 * All functions that modify cache data or structures must acquire the 
 * cacheUpdateLock to prevent interference from concurrent modifications.
 * The function that frees cache garbage must acquire the cacheUpdateLock 
 * and use collecting_in_critical() to flush out cache readers.
 * The cacheUpdateLock is also used to protect the custom allocator used 
 * for large method cache blocks.
 *
 * 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)
 *
 * UNPROTECTED cache readers (NOT thread-safe; used for debug info only)
 * cache_print
 * _class_printMethodCaches
 * _class_printDuplicateCacheEntries
 * _class_printMethodCacheStatistics

從上面的文檔可以看出，寫入的入口函數(shù)是cache_fill粗仓，讀取緩存的入口是cache_getImp嫁怀，下面一一解讀：

寫入操作cache_fill：

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
}

調(diào)用另外一個(gè)函數(shù)cache_fill_nolock：

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;//類對(duì)象沒有初始化妹沙，直接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;
/**先試著取一下墩剖，可能其他的線程
調(diào)用過該方法界轩，取到直接return反症，
后面詳細(xì)講解讀取緩存,這里的
cache_getImp函數(shù)實(shí)現(xiàn)是通過
匯編語言寫的，就是為了速度*/

    cache_t *cache = getCache(cls);//拿到類對(duì)象對(duì)應(yīng)的cache_t

    // Use the cache as-is if it is less than 3/4 full
    mask_t newOccupied = cache->occupied() + 1;//暫用位置試著加1
    mask_t capacity = cache->capacity();//獲取hash表的容量
    if (cache->isConstantEmptyCache()) {
        // Cache is read-only. Replace it.
        cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);//為空存捺，創(chuàng)建bucket
    }
    else if (newOccupied <= capacity / 4 * 3) {
        // Cache is less than 3/4 full. Use it as-is.沒超過3/4槐沼，直接使用
    }
    else {
        // Cache is too full. Expand it.
        cache->expand();//超過3/4，hash擴(kuò)容
    }

    // 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(sel, receiver);//通過hash算法找到對(duì)應(yīng)位置的bucket
    if (bucket->sel() == 0) cache->incrementOccupied();//更新Occupied的值
    bucket->set<Atomic>(sel, imp);存儲(chǔ)sel及對(duì)應(yīng)的imp
}

函數(shù)幾點(diǎn)說明：

1. cache_getImp()的具體實(shí)現(xiàn)是匯編語言捌治，一切是為了速度跟性能母赵；
2. 如果其他線程在執(zhí)行寫操作，直接return具滴；
3. buckets初始的容量是4凹嘲， INIT_CACHE_SIZE；

enum {
    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2)
};

4. 當(dāng)buckets的存儲(chǔ)的bucket超過了容量的3/4時(shí)构韵，會(huì)觸發(fā)擴(kuò)容周蹭。

創(chuàng)建bucket

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    bool freeOld = canBeFreed();//舊的緩存是否能清空

    bucket_t *oldBuckets = buckets();//先拿到舊的緩存
    bucket_t *newBuckets = allocateBuckets(newCapacity);//根據(jù)新的容量，new一份新的緩存

    // 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);//設(shè)置對(duì)應(yīng)的成員變量
    
    if (freeOld) {//是否需要釋放舊的緩存疲恢，擴(kuò)容后舊的緩存處理
        cache_collect_free(oldBuckets, oldCapacity);//暫存在其他地方
        cache_collect(false);//在合適的時(shí)機(jī)釋放凶朗，沒有其他的線程在read cache的時(shí)候
    }
}

在上面的函數(shù)中，我們注意到了舊的緩存的處理邏輯的影子（可以猜測(cè)到显拳，擴(kuò)容應(yīng)該也會(huì)調(diào)用這個(gè)函數(shù)棚愤，后面會(huì)講解到），在這里先說明一下幾點(diǎn)：

1. 擴(kuò)容重新hash杂数，舊的緩存沒有分配到新的buckets中宛畦；
2. 沒有在新的buckets中分配位置，但并不是立馬就釋放掉了揍移，
   而是存放在通過cache_collect_free 申請(qǐng)的garbage_refs里面次和，等到該類沒有對(duì)象發(fā)送消息或者讀取緩存時(shí)，然后釋放掉那伐；
3. 上面兩點(diǎn)的出發(fā)點(diǎn)踏施，都是為了性能跟速度。

將擴(kuò)容導(dǎo)致的舊緩存存放在內(nèi)存的其他區(qū)域garbage_refs

// table of refs to free罕邀，bucket_t的二維表
static bucket_t **garbage_refs = 0;
enum {
    INIT_GARBAGE_COUNT = 128
};
 //一開始是一個(gè)容量為128的二維表畅形，隨著增多，會(huì)不斷的2倍擴(kuò)容
static void _garbage_make_room(void)
{
    static int first = 1;

    // Create the collection table the first time it is needed
    if (first)
    {
        first = 0;
        garbage_refs = (bucket_t**)
            malloc(INIT_GARBAGE_COUNT * sizeof(void *));
        garbage_max = INIT_GARBAGE_COUNT;
    }

    // Double the table if it is full
    else if (garbage_count == garbage_max)
    {//滿了二倍擴(kuò)容
        garbage_refs = (bucket_t**)
            realloc(garbage_refs, garbage_max * 2 * sizeof(void *));
        garbage_max *= 2;
    }
}

cache_collect_free诉探，存放舊緩存

static void cache_collect_free(bucket_t *data, mask_t capacity)
{
    cacheUpdateLock.assertLocked();

    if (PrintCaches) recordDeadCache(capacity);

    _garbage_make_room ();
    garbage_byte_size += cache_t::bytesForCapacity(capacity);
    garbage_refs[garbage_count++] = data;
}

在合適的時(shí)機(jī)釋放舊緩存

void cache_collect(bool collectALot)
{
    cacheUpdateLock.assertLocked();

    // Done if the garbage is not full日熬，可用內(nèi)存未使用完不需要釋放
    if (garbage_byte_size < garbage_threshold  &&  !collectALot) {
        return;
    }

    // Synchronize collection with objc_msgSend and other cache readers
    if (!collectALot) {
        if (_collecting_in_critical ()) {//檢驗(yàn)其他的線程是否正在發(fā)送消息或者讀取，緩存不釋放
            // objc_msgSend (or other cache reader) is currently looking in
            // the cache and might still be using some garbage.
            if (PrintCaches) {
                _objc_inform ("CACHES: not collecting; "
                              "objc_msgSend in progress");
            }
            return;
        }
    } 
    else {
        // No excuses.
        while (_collecting_in_critical()) //一直檢驗(yàn)是否有發(fā)送該sel阵具，或者讀取緩存
            ;
    }

    // No cache readers in progress - garbage is now deletable

    // Log our progress
    if (PrintCaches) {
        cache_collections++;
        _objc_inform ("CACHES: COLLECTING %zu bytes (%zu allocations, %zu collections)", garbage_byte_size, cache_allocations, cache_collections);
    }
    //能走到這碍遍，說明該類相關(guān)的對(duì)象包括類對(duì)象沒有發(fā)送消息，或者讀取該緩存阳液，可以釋放了這部分緩存
    // Dispose all refs now in the garbage
    // Erase each entry so debugging tools don't see stale pointers.
    while (garbage_count--) {
        auto dead = garbage_refs[garbage_count];
        garbage_refs[garbage_count] = nil;
        free(dead);//釋放
    }
    
    // Clear the garbage count and total size indicator
    garbage_count = 0;
    garbage_byte_size = 0;

    if (PrintCaches) {
        size_t i;
        size_t total_count = 0;
        size_t total_size = 0;

        for (i = 0; i < countof(cache_counts); i++) {
            int count = cache_counts[i];
            int slots = 1 << i;
            size_t size = count * slots * sizeof(bucket_t);

            if (!count) continue;

            _objc_inform("CACHES: %4d slots: %4d caches, %6zu bytes", 
                         slots, count, size);

            total_count += count;
            total_size += size;
        }

        _objc_inform("CACHES:      total: %4zu caches, %6zu bytes", 
                     total_count, total_size);
    }
}

擴(kuò)容函數(shù)expand()

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    
    uint32_t oldCapacity = capacity();
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;//擴(kuò)容的在之前的基礎(chǔ)上翻倍怕敬。

    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);//調(diào)用上面講到過的reallocate
}

擴(kuò)容的在之前的基礎(chǔ)上翻倍。

同過sel的hash查到到對(duì)應(yīng)的bucket

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

    bucket_t *b = buckets();
    mask_t m = mask();
    mask_t begin = cache_hash(s, m);//hash算法
    mask_t i = begin;
    do {
        if (b[i].sel() == 0  ||  b[i].sel() == s) {
            return &b[i];
        }
    } while ((i = cache_next(i, m)) != begin);//hash沖突解決方案帘皿，向上個(gè)位置查找

    // hack东跪，沒查找到，壞的緩存
    Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
    cache_t::bad_cache(receiver, (SEL)s, cls);
}

hash算法

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;//相當(dāng)于%mask鹰溜，確保所有結(jié)果都在buckets的容量之內(nèi)虽填，mask = capacity -1
}

hash沖突算法

static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;//返回前面一個(gè)桶子bucket，直到0的時(shí)候曹动，返回mask（從最后一個(gè)位置開始繼續(xù)往前找）
}

讀取操作

cache_getImp斋日，這部分代碼蘋果是用匯編代碼寫的，一切都是為了性能和速度墓陈，ARM64匯編的相關(guān)可以點(diǎn)擊這里了解：

STATIC_ENTRY _cache_getImp

    GetClassFromIsa_p16 p0//拿到isa恶守，并放到p16寄存器
    CacheLookup GETIMP//查找imp

LGetImpMiss:
    mov p0, #0
    ret

    END_ENTRY _cache_getImp

/////////////////////////////////////////////////////////////////////
.macro CacheLookup
    // p1 = SEL, p16 = isa
    ldp p10, p11, [x16, #CACHE] // p10 = buckets, p11 = occupied|mask，通過isa的cache獲取到對(duì)應(yīng)的buckets放到p10寄存器贡必，occupied|mask放到p11寄存器
#if !__LP64__
    and w11, w11, 0xffff    // p11 = mask
#endif
    and w12, w1, w11        
// x12 = _cmd & mask兔港，64位走這個(gè)分支，w11寄存器（p11寄存器的32位）存放的mask仔拟，
//跟p1存放的sel（_cmd就是sel衫樊，我們知道obj_msgSend前面有兩個(gè)
//默認(rèn)參數(shù)，第一個(gè)是self利花，第二個(gè)是_cmd科侈，_cmd就是方法sel，這里也
//一樣炒事，當(dāng)然這里的sel是通過_cache_getImp函數(shù)放進(jìn)去到p1寄存器的兑徘，
//匯編前面8個(gè)寄存器默認(rèn)放函數(shù)的參數(shù)的）進(jìn)行&運(yùn)算
//（cache_fill_nolock函數(shù)的hash算法函數(shù)cache_hash上面有提到過）
//得到buckets的下標(biāo)index，放到p12寄存器
    add p12, p10, p12, LSL #(1+PTRSHIFT)                 
// p12 = buckets + ((_cmd & mask) << (1+PTRSHIFT))羡洛，上面提到bucket
//是一個(gè)結(jié)構(gòu)體挂脑，他的成員是sel跟imp，而且都是 uintptr_t類型欲侮，而uintptr_t就是
//unsigned long類型崭闲，在64位下就是都占8個(gè)字節(jié)，隨意一個(gè)bucket結(jié)構(gòu)體所占的
//內(nèi)存是16個(gè)字節(jié)威蕉，所以從buckets數(shù)組找到對(duì)應(yīng)的元素就可以通過數(shù)組的
//首地址+每個(gè)元素所占內(nèi)存的大小刁俭，即sel對(duì)應(yīng)的bucket = buckets + index*16
//也可以表示為bucket = buckets + index<<4，并且放到p12寄存器中韧涨。

    ldp p17, p9, [x12]      // {imp, sel} = *bucket牍戚，p12寄存器中的imp侮繁，sel取出來，分別放到p17和p9寄存器中
1:  cmp p9, p1          // if (bucket->sel != _cmd)如孝，比較p1宪哩，p9寄存器中的sel
    b.ne    2f          //     scan more，不相等第晰，跳轉(zhuǎn)到2:
    CacheHit $0         // call or return imp 锁孟，相等，返回imp
    
2:  // not hit: p12 = not-hit bucket茁瘦，不相等
    CheckMiss $0            
// miss if bucket->sel == 0品抽，如果對(duì)應(yīng)的sel為空，說明甜熔，沒有緩存圆恤，直接return
    cmp p12, p10        
// wrap if bucket == buckets，比較bucket是否為第一個(gè)元素
    b.eq    3f //為第一個(gè)元素腔稀，跳轉(zhuǎn)到3
    ldp p17, p9, [x12, #-BUCKET_SIZE]!  
// {imp, sel} = *--bucket哑了，不是第一個(gè)元素，說明hash沖突烧颖，向上一個(gè)位置的
//bucket查找弱左，即cache_next函數(shù)，得到的bucket再次將imp炕淮、sel存放在p17和p9寄存器中
    b   1b          // loop拆火，跳轉(zhuǎn)到1，循環(huán)

3:  // wrap: p12 = first bucket, w11 = mask
    add p12, p12, w11, UXTW #(1+PTRSHIFT)                          
 // p12 = buckets + (mask << 1+PTRSHIFT)涂圆，移動(dòng)到最后一個(gè)元素们镜，并賦值給p12寄存器

    // Clone scanning loop to miss instead of hang when cache is corrupt.
    // The slow path may detect any corruption and halt later.

    ldp p17, p9, [x12]      
// {imp, sel} = *bucket，將imp润歉、sel存放在p17和p9寄存器中模狭，繼續(xù)下面的操作，
//跟上面的1踩衩，2相同嚼鹉，區(qū)別在3，當(dāng)跳轉(zhuǎn)到3時(shí)驱富，說明從最后一個(gè)到第一個(gè)都比較
//都沒有找到對(duì)應(yīng)的緩存锚赤，就是沒有查找到，結(jié)束查找褐鸥，返回
1:  cmp p9, p1          // if (bucket->sel != _cmd)
    b.ne    2f          //     scan more
    CacheHit $0         // call or return imp
    
2:  // not hit: p12 = not-hit bucket
    CheckMiss $0            // miss if bucket->sel == 0
    cmp p12, p10        // wrap if bucket == buckets
    b.eq    3f
    ldp p17, p9, [x12, #-BUCKET_SIZE]!  // {imp, sel} = *--bucket
    b   1b          // loop

3:  // double wrap
    JumpMiss $0
    
.endmacro

以上线脚，請(qǐng)指正！！浑侥！