img_cover@1x.jpg

前言

想要成為一名iOS開發(fā)高手雁佳，免不了閱讀源碼。以下是筆者在OC源碼探索中梳理的一個(gè)小系列——類與對(duì)象篇软能，歡迎大家閱讀指正扳缕，同時(shí)也希望對(duì)大家有所幫助慌闭。

1. OC源碼分析之對(duì)象的創(chuàng)建
2. OC源碼分析之isa
3. OC源碼分析之類的結(jié)構(gòu)解讀
4. OC源碼分析之方法的緩存原理
5. OC源碼分析之方法的查找原理
6. OC源碼分析之方法的解析與轉(zhuǎn)發(fā)原理

本文是針對(duì) 方法緩存——cache_t 的分析（且源碼版本是 objc4-756.2），下面進(jìn)入正文躯舔。

1 cache_t源碼分析

當(dāng)你的OC項(xiàng)目編譯完成后驴剔，類的實(shí)例方法（方法編號(hào)SEL 和 函數(shù)地址IMP）就保存在類的方法列表中。我們知道 OC 為了實(shí)現(xiàn)其動(dòng)態(tài)性粥庄，將 方法的調(diào)用包裝成了 SEL 尋找 IMP 的過(guò)程丧失。試想一下，如果每次調(diào)用方法惜互，都要去類的方法列表（甚至父類布讹、根類的方法列表）中查詢其函數(shù)地址，勢(shì)必會(huì)對(duì)性能造成極大的損耗载佳。為了解決這一問(wèn)題炒事，OC 采用了方法緩存的機(jī)制來(lái)提高調(diào)用效率，也就是cache_t蔫慧，其作用就是緩存已調(diào)用的方法。當(dāng)調(diào)用方法時(shí)权薯，objc_msgSend會(huì)先去緩存中查找姑躲，如果找到就執(zhí)行該方法；如果不在緩存中盟蚣，則去類的方法列表（包括父類黍析、根類的方法列表）查找，找到后會(huì)將方法的SEL和IMP緩存到cache_t中屎开，以便下次調(diào)用時(shí)能夠快速執(zhí)行阐枣。

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

首先看一下cache_t的結(jié)構(gòu)

struct cache_t {
    struct bucket_t *_buckets;  // 緩存數(shù)組，即哈希桶
    mask_t _mask;               // 緩存數(shù)組的容量臨界值
    mask_t _occupied;           // 緩存數(shù)組中已緩存方法數(shù)量

    ... // 一些函數(shù)
};

#if __LP64__
typedef uint32_t mask_t;
#else
typedef uint16_t mask_t;
#endif

struct bucket_t {
private:
#if __arm64__
    uintptr_t _imp;
    SEL _sel;
#else
    SEL _sel;
    uintptr_t _imp;
#endif
    ... // 一些方法
};

從上面源碼不難看出，在64位CPU架構(gòu)下蔼两，cache_t長(zhǎng)度是16字節(jié)甩鳄。單從結(jié)構(gòu)來(lái)看，方法是緩存在bucket_t（又稱哈希桶）中额划，接下來(lái)用個(gè)例子驗(yàn)證一下cache_t是否緩存了已調(diào)用的方法妙啃。

1.2 方法緩存的驗(yàn)證

1. 創(chuàng)建一個(gè)簡(jiǎn)單的Person類，代碼如下

@interface Person : NSObject

- (void)methodFirst;
- (void)methodSecond;
- (void)methodThird;

@end

@implementation Person

- (void)methodFirst {
    NSLog(@"%s", __FUNCTION__);
}

- (void)methodSecond {
    NSLog(@"%s", __FUNCTION__);
}

- (void)methodThird {
    NSLog(@"%s", __FUNCTION__);
}

@end

2. 方法調(diào)用前的cache_t

在方法調(diào)用前打個(gè)斷點(diǎn)俊戳，看看cache_t的緩存情況

image

說(shuō)明：

• 從objc_class結(jié)構(gòu)很容易推導(dǎo)得出揖赴，0x1000011d8是cache_t首地址。（對(duì)類的結(jié)構(gòu)感興趣的同學(xué)請(qǐng)戳 OC源碼分析之類的結(jié)構(gòu)解讀）
• 由于還沒(méi)有任何方法調(diào)用抑胎，所以_mask和_occupied都是0

3. 方法調(diào)用后的cache_t

執(zhí)行alloc和init這兩個(gè)方法后燥滑，cache_t變化如下

image

從上圖可知，調(diào)用init后阿逃，_mask的值是3突倍，_occupied則是1。_buckets指針的值（數(shù)組首地址）發(fā)生了變化（從0x1003db250變成0x101700090）盆昙，同時(shí)緩存了init方法的SEL和IMP羽历。

思考：
1. alloc 方法調(diào)用后，緩存在哪里淡喜？
2. 為什么 init 方法不在 _buckets 第一個(gè)位置秕磷？ 

繼續(xù)執(zhí)行methodFirst，再看cache_t

image

此時(shí)炼团，_mask的值是3（沒(méi)發(fā)生變化）澎嚣，_occupied則變成了2，_buckets指針地址沒(méi)變瘟芝，增加緩存了methodFirst方法的SEL和IMP易桃。

接著是執(zhí)行methodSecond，且看

image

顯然锌俱，_occupied變成了3晤郑，而_buckets指針地址不改變，同時(shí)新增methodSecond的方法緩存贸宏。

最后執(zhí)行methodThird后造寝，再看cache_t變化

image

這次的結(jié)果就完全不同了。_mask的值變成7吭练，_occupied則重新變成了1诫龙，而_buckets不僅首地址變了，之前緩存的init鲫咽、methodFirst和methodSecond方法也沒(méi)了签赃，僅存在的只有新增的methodThird方法谷异。看來(lái)锦聊，cache_t并非是如我們所愿的那樣——調(diào)用一個(gè)方法就緩存一個(gè)方法歹嘹。

思考：之前緩存的方法（init、methodFirst 和 methodSecond）哪去了括丁？

1.3 cache_t小結(jié)

讓我們梳理一下上面的例子荞下。在依次執(zhí)行Person的實(shí)例方法init、methodFirst史飞、methodSecond尖昏、methodThird后，cache_t變化如下

可見(jiàn)纹笼，cache_t的確能實(shí)時(shí)緩存已調(diào)用的方法纹份。

上面的驗(yàn)證過(guò)程也可以幫助我們理解cache_t三個(gè)成員變量的意義。直接從單詞含義上解析廷痘，bucket可譯為桶（即哈希桶）蔓涧，用于裝方法；occupied可譯為已占有笋额，表示已緩存的方法數(shù)量元暴；mask可譯為面具、掩飾物兄猩，乍看無(wú)頭緒茉盏，但是注意到cache_t中有獲取容量的函數(shù)（capacity），其源碼如下

struct cache_t {
    ...
    mask_t mask();
    mask_t capacity();
    ...
}

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

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

由此可以得出厦滤，如果_mask是0援岩，說(shuō)明未調(diào)用實(shí)例方法，即桶的容量為0掏导；當(dāng)_mask不等于0的時(shí)候，意味著已經(jīng)調(diào)用過(guò)實(shí)例方法羽峰，此時(shí)桶的容量為_mask + 1趟咆。故添瓷，_mask從側(cè)面反映了桶的容量。

2 cache_t的方法緩存原理

接下來(lái)值纱，筆者將從方法的調(diào)用過(guò)程開始分析cache_t的方法緩存原理鳞贷。

2.1 cache_fill

OC方法的本質(zhì)是 消息發(fā)送（即objc_msgSend），底層是通過(guò)方法的 SEL 查找 IMP虐唠。調(diào)用方法時(shí)搀愧，objc_msgSend會(huì)去cache_t中查詢方法的函數(shù)實(shí)現(xiàn)（這部分是由匯編代碼實(shí)現(xiàn)的，非常高效）疆偿，在緩存中找的過(guò)程暫且不表咱筛；當(dāng)緩存中沒(méi)有的時(shí)候，則去類的方法列表中查找杆故，直至找到后迅箩，再調(diào)用cache_fill，目的是為了將方法緩存到cache_t中处铛，其源碼如下

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
}

objc_msgSend的具體流程筆者將另起一文分析饲趋，這里不作贅述。

2.2 cache_fill_nolock

cache_fill又會(huì)來(lái)到cache_fill_nolock撤蟆，這個(gè)函數(shù)的作用是將方法的SEL和IMP寫入_buckets奕塑，同時(shí)更新_mask和_occupied。

其源碼以及詳細(xì)分析如下：

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

    // 如果類未初始化
    if (!cls->isInitialized()) return;

    // 在獲取cacheUpdateLock之前家肯，確保其他線程沒(méi)有將該方法寫入緩存
    if (cache_getImp(cls, sel)) return;

    // 獲取 cls 的 cache_t指針
    cache_t *cache = getCache(cls);

    // newOccupied為新的方法緩存數(shù)龄砰，等于 當(dāng)前方法緩存數(shù)+1
    mask_t newOccupied = cache->occupied() + 1;
    // 獲取當(dāng)前cache_t的總?cè)萘浚?mask+1
    mask_t capacity = cache->capacity();
    if (cache->isConstantEmptyCache()) {
        // 當(dāng)?shù)谝淮握{(diào)用類的實(shí)例方法時(shí)（如本文的【1.2】例中的`init`）
        cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
    }
    else if (newOccupied <= capacity / 4 * 3) {
        // 新的方法緩存數(shù) 不大于 總?cè)萘康?/4息楔，按原樣使用寝贡，無(wú)需擴(kuò)容
    }
    else {
        // 新的方法緩存數(shù) 大于 總?cè)萘康?/4，需要擴(kuò)容
        cache->expand();
    }

    // 根據(jù)sel獲取bucket值依，此bucket的sel一般為0（說(shuō)明這個(gè)位置還沒(méi)緩存方法）圃泡，
    // 也可能與實(shí)參sel相等（hash沖突，可能性很低）
    bucket_t *bucket = cache->find(sel, receiver);
    // 當(dāng)且僅當(dāng)bucket的sel為0時(shí)愿险，執(zhí)行_occupied++
    if (bucket->sel() == 0) cache->incrementOccupied();
    // 更新bucket的sel和imp
    bucket->set<Atomic>(sel, imp);
}

// INIT_CACHE_SIZE 即為4
enum {
    INIT_CACHE_SIZE_LOG2 = 2,
    INIT_CACHE_SIZE      = (1 << INIT_CACHE_SIZE_LOG2)
};

從上面的源碼不難看出颇蜡，cache_fill_nolock主要是cache_t緩存方法的調(diào)度中心，在這里會(huì)

1. 決定執(zhí)行_buckets的哪一種緩存策略（初始化后緩存辆亏、直接緩存风秤、擴(kuò)容后緩存，三者取一）扮叨；
2. 然后通過(guò)方法的sel找到一個(gè)bucket缤弦，并更新這個(gè)bucket的sel和imp。（如果這個(gè)bucket的sel為0彻磁，說(shuō)明是個(gè)空桶碍沐，正好可以緩存方法狸捅，于是執(zhí)行_occupied++）。

思考：為什么擴(kuò)容臨界點(diǎn)是 3/4累提？

2.3 reallocate

在下面這兩種情況下會(huì)執(zhí)行reallocate：

• 一是第一次初始化_buckets的時(shí)候
• 另一種則是_buckets擴(kuò)容的時(shí)候

我們來(lái)看一下reallocate做了哪些事情

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    // 當(dāng)且僅當(dāng)`_buckets`中有緩存方法時(shí)尘喝，feeOld為true
    bool freeOld = canBeFreed();

    // 獲取當(dāng)前buckets指針，即_buckets
    bucket_t *oldBuckets = buckets();
    // 開辟新的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);

    // 將新buckets斋陪、新mask（newCapacity-1）分別賦值跟當(dāng)前的 _buckets 和 _mask
    setBucketsAndMask(newBuckets, newCapacity - 1);
    
    if (freeOld) {
        // 釋放舊的buckets內(nèi)存空間
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false);
    }
}

reallocate完美解釋了在例【1.2】中的幾個(gè)情況：

• init執(zhí)行完后朽褪，_buckets指針地址變了，_mask變成了3无虚；
• methodThird執(zhí)行完后缔赠，_buckets不僅指針地址變了，同時(shí)之前緩存的init骑科、methodFirst和methodSecond方法也都不在了

注意橡淑，_occupied的變化是在回到cache_fill_nolock后發(fā)生的。

思考：擴(kuò)容后咆爽，為什么不直接把之前緩存的方法加入新的buckets中梁棠？

2.4 expand

從cache_fill_nolock源碼來(lái)看，當(dāng)新的方法緩存數(shù)（_occupied+1）大于總?cè)萘浚╛mask+1）時(shí)斗埂，會(huì)對(duì)_buckets進(jìn)行擴(kuò)容符糊，也就是執(zhí)行expand函數(shù)，其源碼如下

void cache_t::expand()
{
    cacheUpdateLock.assertLocked();
    
    // 獲取當(dāng)前總?cè)萘壳盒祝確mask+1
    uint32_t oldCapacity = capacity();
    // 新的容量 = 舊容量 * 2
    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);
}

這個(gè)函數(shù)非常簡(jiǎn)單男娄，僅僅是計(jì)算好新的容量后，就去調(diào)用reallocate函數(shù)漾稀。需要注意的是：

• 在不超過(guò)uint32_t大心Ｏ小（4字節(jié)）時(shí)，每次擴(kuò)容為原來(lái)的2倍
• 如果超過(guò)了uint32_t崭捍，則重新申請(qǐng)跟原來(lái)一樣大小的buckets

2.5 find

在執(zhí)行完相應(yīng)的buckets策略后尸折，接下來(lái)就需要找到合適的位置（bucket），以存儲(chǔ)
方法的SEL和IMP殷蛇。find具體做的事情就是根據(jù)方法的SEL实夹，返回一個(gè)符合要求的bucket，同樣上源碼

bucket_t * cache_t::find(SEL s, id receiver)
{
    assert(s != 0);
    // 獲取當(dāng)前buckets粒梦，即_buckets
    bucket_t *b = buckets();
    // 獲取當(dāng)前mask亮航，即_mask
    mask_t m = mask();
    // 由 sel & mask 得出起始索引值
    mask_t begin = cache_hash(s, m);
    mask_t i = begin;
    do {
        // sel為0：說(shuō)明 i 這個(gè)位置尚未緩存方法；
        // sel等于s：命中緩存匀们，說(shuō)明 i 這個(gè)位置已緩存方法缴淋，可能是hash沖突
        if (b[i].sel() == 0  ||  b[i].sel() == s) {
            return &b[i];
        }
    } while ((i = cache_next(i, m)) != begin);

    // hack
    // 找不到多余的哈希桶（出錯(cuò)的處理，打印問(wèn)題）。一般不會(huì)走到這里宴猾！
    Class cls = (Class)((uintptr_t)this - offsetof(objc_class, cache));
    cache_t::bad_cache(receiver, (SEL)s, cls);
}

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}

#if __arm__  ||  __x86_64__  ||  __i386__
// objc_msgSend has few registers available.
// Cache scan increments and wraps at special end-marking bucket.
#define CACHE_END_MARKER 1
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return (i+1) & mask;
}

#elif __arm64__
// objc_msgSend has lots of registers available.
// Cache scan decrements. No end marker needed.
#define CACHE_END_MARKER 0
static inline mask_t cache_next(mask_t i, mask_t mask) {
    return i ? i-1 : mask;
}

#else
#error unknown architecture
#endif

從源碼可以發(fā)現(xiàn)圆存，find找bucket的方式用到了hash的思想：以_buckets作為哈希桶叼旋，以cache_hash作為哈希函數(shù)仇哆，進(jìn)行哈希運(yùn)算后得出索引值index（本質(zhì)是xx & mask，所以index最大值就是_mask的值）夫植。由于索引值是通過(guò)哈希運(yùn)算得出的讹剔，其結(jié)果自然是無(wú)序的，這也是為什么上例中init方法不在_buckets第一個(gè)位置的原因详民。

3 多線程對(duì)方法緩存的影響

既然哈希桶的數(shù)量是在運(yùn)行時(shí)動(dòng)態(tài)增加的延欠，那么在多線程環(huán)境下調(diào)用方法時(shí)，對(duì)方法的緩存有沒(méi)有什么影響呢沈跨？且看下面的分析由捎。

3.1 多線程同時(shí)讀取緩存

在整個(gè)objc_msgSend函數(shù)中，為了達(dá)到最佳的性能饿凛，對(duì)方法緩存的讀取操作是沒(méi)有添加任何鎖的狞玛。而多個(gè)線程同時(shí)調(diào)用已緩存的方法，并不會(huì)引發(fā)_buckets和_mask的變化涧窒，因此多個(gè)線程同時(shí)讀取方法緩存的操作是不會(huì)有安全隱患的心肪。

3.2 多線程同時(shí)寫緩存

從源碼我們知道在桶數(shù)量擴(kuò)容和寫桶數(shù)據(jù)之前，系統(tǒng)使用了一個(gè)全局的互斥鎖（cacheUpdateLock.assertLocked()）來(lái)保證寫入的同步處理纠吴，并且在鎖住的范圍內(nèi)部還做了一次查緩存的操作（if (cache_getImp(cls, sel)) return;）硬鞍，這樣就 保證了哪怕多個(gè)線程同時(shí)寫同一個(gè)方法的緩存也只會(huì)產(chǎn)生寫一次的效果，即多線程同時(shí)寫緩存的操作也不會(huì)有安全隱患戴已。

3.3 多線程同時(shí)讀寫緩存

這個(gè)情況就比較復(fù)雜了固该，我們先看一下objc_msgSend讀緩存的代碼（以 arm64架構(gòu)匯編 為例）

.macro CacheLookup
    // x1 = SEL, x16 = isa
    ldp x10, x11, [x16, #CACHE] // x10 = buckets, x11 = occupied|mask
    and w12, w1, w11        // x12 = _cmd & mask
    add x12, x10, x12, LSL #4   // x12 = buckets + ((_cmd & mask)<<4)

    ldp x9, x17, [x12]      // {x9, x17} = *bucket
1:  cmp x9, x1          // if (bucket->sel != _cmd)
    b.ne    2f          //     scan more
    CacheHit $0         // call or return imp
    
2:  // not hit: x12 = not-hit bucket
    CheckMiss $0            // miss if bucket->sel == 0
    cmp x12, x10        // wrap if bucket == buckets
    b.eq    3f
    ldp x9, x17, [x12, #-16]!   // {x9, x17} = *--bucket
    b   1b          // loop

3:  // wrap: x12 = first bucket, w11 = mask
    add x12, x12, w11, UXTW #4  // x12 = buckets+(mask<<4)

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

    ldp x9, x17, [x12]      // {x9, x17} = *bucket
1:  cmp x9, x1          // if (bucket->sel != _cmd)
    b.ne    2f          //     scan more
    CacheHit $0         // call or return imp
    
2:  // not hit: x12 = not-hit bucket
    CheckMiss $0            // miss if bucket->sel == 0
    cmp x12, x10        // wrap if bucket == buckets
    b.eq    3f
    ldp x9, x17, [x12, #-16]!   // {x9, x17} = *--bucket
    b   1b          // loop

3:  // double wrap
    JumpMiss $0
    
.endmacro

其中，ldp指令的作用是將數(shù)據(jù)從內(nèi)存讀取出來(lái)存到寄存器糖儡，第一個(gè)ldp代碼會(huì) 把cache_t中的_buckets 和 _occupied | _mask整個(gè)結(jié)構(gòu)體成員分別讀取到x10和x11兩個(gè)寄存器中伐坏，并且CacheLookup的后續(xù)代碼沒(méi)有再次讀取cache_t的成員數(shù)據(jù)，而是一直使用x10和x11中的值進(jìn)行哈希查找休玩。由于CPU能保證單條指令執(zhí)行的原子性著淆，所以 只要保證ldp x10, x11, [x16, #CACHE]這段代碼讀取到的_buckets與_mask是互相匹配的（即要么同時(shí)是擴(kuò)容前的數(shù)據(jù)，要么同時(shí)是擴(kuò)容后的數(shù)據(jù)）拴疤，那么多個(gè)線程同時(shí)讀寫方法緩存也是沒(méi)有安全隱患的永部。

3.3.1 編譯內(nèi)存屏障

這里有個(gè)疑問(wèn)，即系統(tǒng)是如何確保_buckets與_mask的這種一致性的呢呐矾？讓我們看一下這兩個(gè)變量的寫入源碼

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;
    _occupied = 0;
}

這段C++代碼先修改_buckets苔埋，然后再更新_mask的值，為了確保這個(gè)順序不被編譯器優(yōu)化蜒犯，這里使用了mega_baerrier()來(lái)實(shí)現(xiàn) 編譯內(nèi)存屏障（Compiler Memory Barrier）组橄。

如果不設(shè)置 編譯內(nèi)存屏障 的話荞膘，編譯器有可能會(huì)優(yōu)化代碼先賦值_mask，然后才是賦值_buckets玉工，兩者的賦值之間羽资，如果另一個(gè)線程執(zhí)行ldp x10, x11, [x16, #0x10]指令，得到的就是舊_buckets和新_mask遵班，進(jìn)而出現(xiàn)內(nèi)存數(shù)組越界引發(fā)程序崩潰屠升。

而加入了編譯內(nèi)存屏障后，就算得到的是新_buckets和舊_mask狭郑，也不會(huì)導(dǎo)致程序崩潰腹暖。

編譯內(nèi)存屏障僅僅是確保_buckets的賦值會(huì)優(yōu)先于_mask的賦值，也就是說(shuō)翰萨，在任何場(chǎng)景下當(dāng)指令ldp x10, x11, [x16, #CACHE]執(zhí)行后脏答，得到的_buckets數(shù)組的長(zhǎng)度一定是大于或等于_mask+1的，如此就保證了不會(huì)出現(xiàn)內(nèi)存數(shù)組越界導(dǎo)致的程序崩潰亩鬼。可見(jiàn)殖告，借助編譯內(nèi)存屏障的技巧在一定的程度上可以實(shí)現(xiàn)無(wú)鎖讀寫技術(shù)。

對(duì)內(nèi)存屏障感興趣的同學(xué)可戳 理解 Memory barrier（內(nèi)存屏障）

3.3.2 內(nèi)存垃圾回收

我們知道辛孵，在多線程讀寫方法緩存時(shí)丛肮，寫線程可能會(huì)擴(kuò)容_buckets（開辟新的_buckets內(nèi)存，同時(shí)銷毀舊的_buckets）魄缚，此時(shí)宝与，如果其他線程讀取到的_buckets是舊的內(nèi)存，就有可能會(huì)發(fā)生讀內(nèi)存異常而系統(tǒng)崩潰冶匹。為了解決這個(gè)問(wèn)題习劫，OC使用了兩個(gè)全局?jǐn)?shù)組objc_entryPoints、objc_exitPoints嚼隘，分別保存所有會(huì)訪問(wèn)到cache的函數(shù)的起始地址诽里、結(jié)束地址

extern "C" uintptr_t objc_entryPoints[];
extern "C" uintptr_t objc_exitPoints[];

下面列出這些函數(shù)（同樣以 arm64架構(gòu)匯編 為例）

.private_extern _objc_entryPoints
_objc_entryPoints:
    .quad   _cache_getImp
    .quad   _objc_msgSend
    .quad   _objc_msgSendSuper
    .quad   _objc_msgSendSuper2
    .quad   _objc_msgLookup
    .quad   _objc_msgLookupSuper2
    .quad   0

.private_extern _objc_exitPoints
_objc_exitPoints:
    .quad   LExit_cache_getImp
    .quad   LExit_objc_msgSend
    .quad   LExit_objc_msgSendSuper
    .quad   LExit_objc_msgSendSuper2
    .quad   LExit_objc_msgLookup
    .quad   LExit_objc_msgLookupSuper2
    .quad   0

當(dāng)線程擴(kuò)容哈希桶時(shí)，會(huì)先把舊的桶內(nèi)存保存在一個(gè)全局的垃圾回收數(shù)組變量garbage_refs中飞蛹，然后再遍歷當(dāng)前進(jìn)程（在iOS中谤狡，一個(gè)進(jìn)程就是一個(gè)應(yīng)用程序）中的所有線程，查看是否有線程正在執(zhí)行objc_entryPoints列表中的函數(shù)（原理是PC寄存器中的值是否在objc_entryPoints和objc_exitPoints這個(gè)范圍內(nèi)）卧檐，如果沒(méi)有則說(shuō)明沒(méi)有任何線程訪問(wèn)cache墓懂，可以放心地對(duì)garbage_refs中的所有待銷毀的哈希桶內(nèi)存塊執(zhí)行真正的銷毀操作；如果有則說(shuō)明有線程訪問(wèn)cache霉囚，這次就不做處理捕仔，下次再檢查并在適當(dāng)?shù)臅r(shí)候進(jìn)行銷毀。

以上，OC 2.0的runtime巧妙的利用了ldp匯編指令榜跌、編譯內(nèi)存屏障技術(shù)闪唆、內(nèi)存垃圾回收技術(shù)等多種手段來(lái)解決多線程讀寫的無(wú)鎖處理方案，既保證了安全钓葫，又提升了系統(tǒng)的性能悄蕾。

在這里，特別感謝 歐陽(yáng)大哥瓤逼！他的 深入解構(gòu)objc_msgSend函數(shù)的實(shí)現(xiàn) 這篇博文會(huì)幫助你進(jìn)一步了解Runtime的實(shí)現(xiàn)笼吟，其在多線程讀寫方法緩存方面也讓筆者受益匪淺，強(qiáng)烈推薦大家一讀霸旗！

4 問(wèn)題討論

來(lái)到這里，相信大家對(duì)cache_t緩存方法的原理已經(jīng)有了一定的理解∑萁遥現(xiàn)在請(qǐng)看下面的幾個(gè)問(wèn)題：

4.1 類方法的緩存位置

Q：Person類調(diào)用alloc方法后诱告，緩存在哪里？

A：緩存在 Person元類 的 cache_t 中民晒。證明如下圖

image

4.2 _mask的作用

Q：請(qǐng)說(shuō)明cache_t中_mask的作用

A：_mask從側(cè)面反映了cache_t中哈希桶的數(shù)量（哈希桶的數(shù)量 = _mask + 1）精居，保證了查找哈希桶時(shí)不會(huì)出現(xiàn)越界的情況。

題解：從上面的源碼分析潜必，我們知道cache_t在任何一次緩存方法的時(shí)候靴姿，哈希桶的數(shù)量一定是 >=4且能被 4整除的，_mask則等于哈希桶的數(shù)量-1磁滚，也就是說(shuō)佛吓，緩存方法的時(shí)候，_mask的二進(jìn)制位上全都是1垂攘。當(dāng)循環(huán)查詢哈希桶的時(shí)候维雇，索引值是由xx & _mask運(yùn)算得出的，因此索引值是小于哈希桶的數(shù)量的（index <= _mask晒他，故index < capacity）吱型，也就不會(huì)出現(xiàn)越界的情況。

4.3 關(guān)于擴(kuò)容臨界點(diǎn)3/4的討論

Q：為什么擴(kuò)容臨界點(diǎn)是3/4陨仅？

A：一般設(shè)定臨界點(diǎn)就不得不權(quán)衡 空間利用率 和 時(shí)間利用率 津滞。在 3/4 這個(gè)臨界點(diǎn)的時(shí)候，空間利用率比較高灼伤，同時(shí)又避免了相當(dāng)多的哈希沖突触徐，時(shí)間利用率也比較高。

題解：擴(kuò)容臨界點(diǎn)直接影響循環(huán)查找哈希桶的效率饺蔑。設(shè)想兩個(gè)極端情況：

當(dāng)臨界點(diǎn)是1的時(shí)候锌介，也就是說(shuō)當(dāng)全部的哈希桶都緩存有方法時(shí)，才會(huì)擴(kuò)容。這雖然讓開辟出來(lái)的內(nèi)存空間的利用率達(dá)到100%孔祸，但是會(huì)造成大量的哈希沖突隆敢，加劇了查找索引的時(shí)間成本，導(dǎo)致時(shí)間利用率低下崔慧，這與高速緩存的目的相悖拂蝎；

當(dāng)臨界點(diǎn)是0.5的時(shí)候，意味著哈希桶的占用量達(dá)到總數(shù)一半的時(shí)候惶室，就會(huì)擴(kuò)容温自。這雖然極大避免了哈希沖突，時(shí)間利用率非常高皇钞，卻浪費(fèi)了一半的空間悼泌，使得空間利用率低下。這種以空間換取時(shí)間的做法同樣不可燃薪纭馆里；

兩相權(quán)衡下，當(dāng)擴(kuò)容臨界點(diǎn)是3/4的時(shí)候可柿，空間利用率 和 時(shí)間利用率 都相對(duì)比較高鸠踪。

4.4 緩存循環(huán)查找的死循環(huán)情況

Q：緩存循環(huán)查找哈希桶是否會(huì)出現(xiàn)死循環(huán)的情況？

A：不會(huì)出現(xiàn)复斥。

題解：當(dāng)哈希桶的利用率達(dá)到3/4的時(shí)候营密，下次緩存的時(shí)候就會(huì)進(jìn)行擴(kuò)容，即空桶的數(shù)量最少也會(huì)有總數(shù)的1/4目锭，因此循環(huán)查詢索引的時(shí)候评汰，一定會(huì)出現(xiàn)命中緩存或者空桶的情況，從而結(jié)束循環(huán)侣集。

5 總結(jié)

通過(guò)以上例子的驗(yàn)證键俱、源碼的分析以及問(wèn)題的討論，現(xiàn)在總結(jié)一下cache_t的幾個(gè)結(jié)論：

1. cache_t能緩存調(diào)用過(guò)的方法世分。
2. cache_t的三個(gè)成員變量中编振，
   • _buckets的類型是struct bucket_t *，也就是指針數(shù)組臭埋，它表示一系列的哈希桶（已調(diào)用的方法的SEL和IMP就緩存在哈希桶中）踪央，一個(gè)桶可以緩存一個(gè)方法。
   • _mask的類型是mask_t（mask_t在64位架構(gòu)下就是uint32_t瓢阴，長(zhǎng)度為4個(gè)字節(jié)）畅蹂，它的值等于哈希桶的總數(shù)-1（capacity - 1），側(cè)面反映了哈希桶的總數(shù)荣恐。
   • _occupied的類型也是mask_t液斜，它代表的是當(dāng)前_buckets已緩存的方法數(shù)累贤。
3. 當(dāng)緩存的方法數(shù)到達(dá)臨界點(diǎn)（桶總數(shù)的3/4）時(shí)，下次再緩存新的方法時(shí)少漆，首先會(huì)丟棄舊的桶臼膏，同時(shí)開辟新的內(nèi)存，也就是擴(kuò)容（擴(kuò)容后都是全新的桶示损，以后每個(gè)方法都要重新緩存的）渗磅，然后再把新的方法緩存下來(lái)，此時(shí)_occupied為1检访。
4. 當(dāng)多個(gè)線程同時(shí)調(diào)用一個(gè)方法時(shí)始鱼，可分以下幾種情況：
   • 多線程讀緩存：讀緩存由匯編實(shí)現(xiàn)，無(wú)鎖且高效脆贵，由于并沒(méi)有改變_buckets和_mask医清，所以并無(wú)安全隱患。
   • 多線程寫緩存：OC用了個(gè)全局的互斥鎖（cacheUpdateLock.assertLocked()）來(lái)保證不會(huì)出現(xiàn)寫兩次緩存的情況丹禀。
   • 多線程讀寫緩存：OC使用了ldp匯編指令状勤、編譯內(nèi)存屏障技術(shù)、內(nèi)存垃圾回收技術(shù)等多種手段來(lái)解決多線程讀寫的無(wú)鎖處理方案双泪，既保證了安全，又提升了系統(tǒng)的性能密似。

6 參考資料

• 深入解構(gòu)objc_msgSend函數(shù)的實(shí)現(xiàn)
• 理解 Memory barrier（內(nèi)存屏障）

7 PS

• 源碼工程已放到github上焙矛，請(qǐng)戳 objc4-756.2源碼
• 你也可以自行下載 蘋果官方objc4源碼 研究學(xué)習(xí)。
• 轉(zhuǎn)載請(qǐng)注明出處残腌！謝謝村斟！