前言

上一篇講解了objc_msgSend調(diào)用流程并在緩存中找到對(duì)應(yīng)方法奋献。今天我們來(lái)詳解在緩存中找不到對(duì)應(yīng)方法的情況晴音。

回到objc_msgSend源碼中調(diào)用cacheLookup方法的地方：

LGetIsaDone:
// calls imp or objc_msgSend_uncached
CacheLookup NORMAL, _objc_msgSend, __objc_msgSend_uncached

cacheLookup定義：

.macro CacheLookup Mode, Function, MissLabelDynamic, MissLabelConstant

當(dāng)找不到緩存中方法的時(shí)候執(zhí)行：

3:  cbz p9, \MissLabelDynamic       //     if (sel == 0) goto Miss;
    cmp p13, p10            // } while (bucket >= buckets)
    b.hs    1b

對(duì)應(yīng)cacheLookup的調(diào)用及傳參，可知當(dāng)找不到緩存方法時(shí)會(huì)調(diào)用_objc_msgSend_uncached肾砂，這個(gè)方法其實(shí)之前在查看方法堆棧信息時(shí)已經(jīng)見(jiàn)到過(guò)了：

insert之前的調(diào)用信息

_objc_msgSend_uncached源碼解析

本篇依然使用objc_msg_arm64.s來(lái)分析_objc_msgSend_uncached源碼：

STATIC_ENTRY __objc_msgSend_uncached
UNWIND __objc_msgSend_uncached, FrameWithNoSaves

// THIS IS NOT A CALLABLE C FUNCTION
// Out-of-band p15 is the class to search
    
MethodTableLookup
TailCallFunctionPointer x17

END_ENTRY __objc_msgSend_uncached

方法很簡(jiǎn)潔芬沉，核心方法就在MethodTableLookup和TailCallFunctionPointer x17，其中：

.macro TailCallFunctionPointer
    // $0 = function pointer value
    br  $0
.endmacro

TailCallFunctionPointer其實(shí)就是返回x17趣倾，所以_objc_msgSend_uncached的真正核心就在于MethodTableLookup:

.macro MethodTableLookup
    
    SAVE_REGS MSGSEND

    // lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
    // receiver and selector already in x0 and x1
    mov x2, x16
    mov x3, #3
    bl  _lookUpImpOrForward

    // IMP in x0
    mov x17, x0

    RESTORE_REGS MSGSEND

.endmacro

可看到值得關(guān)注的核心方法就是_lookUpImpOrForward聘惦，繼續(xù)找他的源碼，發(fā)現(xiàn)匯編里沒(méi)有儒恋，終于回到了runtime-new.mm善绎。方法代碼很長(zhǎng)，但包含了著名的慢速查找過(guò)程

慢速查找

在lookUpImpOrForward源碼中诫尽，我們需要關(guān)注的重點(diǎn)在于如何找到imp的禀酱，首先關(guān)注核心代碼：

for (unsigned attempts = unreasonableClassCount();;) {
        if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
#if CONFIG_USE_PREOPT_CACHES
            imp = cache_getImp(curClass, sel);
            if (imp) goto done_unlock;
            curClass = curClass->cache.preoptFallbackClass();
#endif
        } else {
            // curClass method list.
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {
                imp = meth->imp(false);
                goto done;
            }

            if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
                // No implementation found, and method resolver didn't help.
                // Use forwarding.
                imp = forward_imp;
                break;
            }
        }

        // Halt if there is a cycle in the superclass chain.
        if (slowpath(--attempts == 0)) {
            _objc_fatal("Memory corruption in class list.");
        }

        // Superclass cache.
        imp = cache_getImp(curClass, sel);
        if (slowpath(imp == forward_imp)) {
            // Found a forward:: entry in a superclass.
            // Stop searching, but don't cache yet; call method
            // resolver for this class first.
            break;
        }
        if (fastpath(imp)) {
            // Found the method in a superclass. Cache it in this class.
            goto done;
        }
    }

注意到這是一個(gè)沒(méi)有終止條件和變量的死循環(huán)，跳出循環(huán)的地方就是我們要重點(diǎn)看的地方break和goto牧嫉。我們逐句分析所謂慢速查找到底是怎么做的：

if (curClass->cache.isConstantOptimizedCache(/* strict */true))

第一個(gè)if條件很有意思比勉，是再去cache中找了一遍是否含有對(duì)應(yīng)方法的imp，可以視為一種預(yù)防處理驹止，比如有些方法插入出現(xiàn)了延時(shí)浩聋，在進(jìn)入慢速查找之前還沒(méi)插入完成，所以在正式進(jìn)入慢速查找之前再檢查確認(rèn)一遍臊恋，避免出現(xiàn)不必要的慢速查找衣洁，提升效率。緩存中查找方法我們就不再贅述了抖仅，直接看else中的邏輯Method meth = getMethodNoSuper_nolock(curClass, sel);坊夫，其中getMethodNoSuper_nolock是：

static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
    runtimeLock.assertLocked();

    ASSERT(cls->isRealized());
    // fixme nil cls? 
    // fixme nil sel?

    auto const methods = cls->data()->methods();
    for (auto mlists = methods.beginLists(),
              end = methods.endLists();
         mlists != end;
         ++mlists)
    {
        // <rdar://problem/46904873> getMethodNoSuper_nolock is the hottest
        // caller of search_method_list, inlining it turns
        // getMethodNoSuper_nolock into a frame-less function and eliminates
        // any store from this codepath.
        method_t *m = search_method_list_inline(*mlists, sel);
        if (m) return m;
    }

    return nil;
}

• ASSERT(cls->isRealized());：判斷cls是否已注冊(cè)（以后會(huì)講到）；
• auto const methods = cls->data()->methods();：這句大家很熟息了撤卢，取出當(dāng)前class的方法列表（詳見(jiàn)類的結(jié)構(gòu)解析）环凿；
• for循環(huán)遍歷類的每一個(gè)方法列表（類的方法列表可能是二位數(shù)組class method_array_t : public list_array_tt<method_t, method_list_t, method_list_t_authed_ptr>），查找的核心方法search_method_list_inline去掉多余代碼后為：

search_method_list_inline(const method_list_t *mlist, SEL sel)
{
    int methodListIsFixedUp = mlist->isFixedUp();
    int methodListHasExpectedSize = mlist->isExpectedSize();
    
    if (fastpath(methodListIsFixedUp && methodListHasExpectedSize)) {
        return findMethodInSortedMethodList(sel, mlist);
    } else {
        // Linear search of unsorted method list
        if (auto *m = findMethodInUnsortedMethodList(sel, mlist))
            return m;
    }
    return nil;
}

可以看到放吩，查找的核心方法是findMethodInSortedMethodList(sel, mlist)智听，繼續(xù)查看他的源碼找到核心方法指向了findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)，也就是慢速查找方法的重點(diǎn)二分查找法（為什么用二分法？因?yàn)橐粋€(gè)類可能含有的方法可能數(shù)量很多）：

findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)
{
    ASSERT(list);

    auto first = list->begin();
    auto base = first;
    decltype(first) probe;

    uintptr_t keyValue = (uintptr_t)key;
    uint32_t count;
    
    for (count = list->count; count != 0; count >>= 1) {
        probe = base + (count >> 1);
        
        uintptr_t probeValue = (uintptr_t)getName(probe);
        
        if (keyValue == probeValue) {
            // `probe` is a match.
            // Rewind looking for the *first* occurrence of this value.
            // This is required for correct category overrides.
            while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
                probe--;
            }
            return &*probe;
        }
        
        if (keyValue > probeValue) {
            base = probe + 1;
            count--;
        }
    }
    
    return nil;
}

• for循環(huán)的條件為（count = 方法數(shù)到推；count不等于0考赛；count右移1位），這里右移1位相當(dāng)于除以2莉测，為了方便邏輯理解颜骤，這里假設(shè)count = 8（8-1000右移一位變?yōu)?0100，相當(dāng)于8除以2）捣卤；
• probe = base + (count >> 1);：base初始值為begin忍抽，也就是0，probe = 0 + （8>>1 = 4）= 4董朝，for循環(huán)第一次查找的位置是4號(hào)位置;
• keyValue就是傳進(jìn)來(lái)的SEL轉(zhuǎn)成long類型的值鸠项，假設(shè)keyValue等于7，同樣的probeValue就是probe轉(zhuǎn)為long類型的值 uintptr_t probeValue = (uintptr_t)getName(probe)益涧，將兩者相比較看取到的probe值是否等于傳進(jìn)來(lái)的SEL锈锤；
• 如果相等，意為找到了對(duì)應(yīng)方法闲询。這之間還存在一個(gè)white循環(huán)久免，通過(guò)注釋可知這是查找category中是否有重寫當(dāng)前方法，存在則執(zhí)行probe--扭弧，這也證明了：當(dāng)有category重寫當(dāng)前方法時(shí)阎姥，將執(zhí)行category中的方法，并且鸽捻，當(dāng)有多個(gè)category重寫同一方法時(shí)呼巴，會(huì)執(zhí)行最后一個(gè)category中的方法。如果category中沒(méi)有重寫方法御蒲，則返回&*probe衣赶，也就是對(duì)應(yīng)的imp；
• 如果不相等厚满，則判斷如果SEL轉(zhuǎn)成的值大于4府瞄，則base = probe + 1等于5，count--等于7碘箍，開(kāi)始第二次循環(huán)
• 第二次循環(huán)時(shí)遵馆，循環(huán)條件上count>>1也就是7>>1為3，probe = base + (count >> 1)即probe = 5 + （3>>1 = 1）= 6丰榴，即第二次查找在數(shù)組的第六位货邓。再次沒(méi)找到的話符合keyValue > probeValue，base = 6+1 = 7四濒，count-- = 3 - 1 = 2换况，開(kāi)始第三次循環(huán)职辨；
• 第三次循環(huán)，循環(huán)條件上count>>1也就是2>>1為1复隆，probe = base + (count >> 1)即probe = 7 + （1>>1 = 0）= 7拨匆，即第三次查找在數(shù)組的第七位姆涩，找到了對(duì)應(yīng)方法挽拂。
• 如果keyValue小于4會(huì)怎么樣大家可以自己走一遍，體會(huì)一下count在循環(huán)中連續(xù)右移1位的精妙之處骨饿。
• 如果一直沒(méi)有找到亏栈，則最終返回nil。
  至此宏赘，慢速查找過(guò)程的二分查找法分析完畢绒北。

像父類中查找方法

重新回到lookUpImpOrForward中，如果在方法列表中沒(méi)有找到對(duì)應(yīng)方法察署，那么接下來(lái)：

if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
     // No implementation found, and method resolver didn't help.
     // Use forwarding.
     imp = forward_imp;
     break;
}

這里其實(shí)做了兩步操作闷游，首先在if條件中，將curClass賦值為了當(dāng)前類的父類curClass = curClass->getSuperclass()贴汪，如果有父類脐往，則跳過(guò)；如果當(dāng)前類沒(méi)有父類扳埂，意味著當(dāng)前類已經(jīng)是根類业簿，要查找的方法在本類至根類都沒(méi)有對(duì)應(yīng)方法的實(shí)現(xiàn)，因此返回了forward_imp開(kāi)始進(jìn)入消息轉(zhuǎn)發(fā)流程阳懂，這一點(diǎn)其實(shí)在之前類的方法歸屬中探究過(guò)梅尤，當(dāng)查找一個(gè)類中是否有對(duì)應(yīng)方法的實(shí)現(xiàn)時(shí)，即使沒(méi)有實(shí)現(xiàn)該方法岩调，也會(huì)有imp返回值巷燥，返回的是_objc_msgForward，消息轉(zhuǎn)發(fā)將在下一篇重點(diǎn)講解号枕。

再繼續(xù)缰揪，獲取到父類之后：

// Superclass cache.
imp = cache_getImp(curClass, sel);
if (fastpath(imp)) {
     // Found the method in a superclass. Cache it in this class.
    goto done;
}

其中cache_getImp需要我們回到匯編中：

STATIC_ENTRY _cache_getImp

    GetClassFromIsa_p16 p0, 0
    CacheLookup GETIMP, _cache_getImp, LGetImpMissDynamic, LGetImpMissConstant

CacheLookup代碼我們已經(jīng)很熟悉了，跟之前objc_msgSend中的流程一樣堕澄，獲取isa->class邀跃，然后在緩存中查找方法，如果父類緩存中有的對(duì)應(yīng)方法imp的話同樣執(zhí)行goto done;蛙紫。但是這里要注意區(qū)別：在第一次FCPerson調(diào)用CacheLookup過(guò)程中第一個(gè)參數(shù)是NORMAL拍屑，NORMAL模式使得緩存中找不到imp后執(zhí)行objc_msgSend_uncached，但是現(xiàn)在查到父類的時(shí)候坑傅，傳參為GETIMP僵驰，我們來(lái)看區(qū)別：

.if \Mode == GETIMP
    b.ne    \MissLabelConstant      // cache miss
    sub x0, x16, x17, LSR #32       // imp = isa - imp_offs
    SignAsImp x0
    ret
.else
    b.ne    5f              // cache miss
    sub x17, x16, x17, LSR #32      // imp = isa - imp_offs
.if \Mode == NORMAL
    br  x17
.elseif \Mode == LOOKUP
    orr x16, x16, #3 // for instrumentation, note that we hit a constant cache
    SignAsImp x17
    ret
.else

可以看到當(dāng)Mode = GETIMP時(shí)，查找不到會(huì)直接返回空，因此慢速查找過(guò)程中蒜茴，父類緩存中沒(méi)找到星爪，不會(huì)調(diào)用uncache方法，而是直接返回nil然后繼續(xù)lookUpImpOrForward中的循環(huán)粉私，而再次循環(huán)時(shí)cls已經(jīng)是superClass了顽腾，重新對(duì)父類再次執(zhí)行慢速查找的流程，直至找到根類诺核，其實(shí)整個(gè)查找的過(guò)程就遞歸的過(guò)程抄肖。

接下來(lái)我們繼續(xù)分析找到方法的imp后，goto done;做了什么：

done:
    if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) {
#if CONFIG_USE_PREOPT_CACHES
        while (cls->cache.isConstantOptimizedCache(/* strict */true)) {
            cls = cls->cache.preoptFallbackClass();
        }
#endif
        log_and_fill_cache(cls, imp, sel, inst, curClass);
    }

核心方法：log_and_fill_cache(cls, imp, sel, inst, curClass);就是說(shuō)當(dāng)一個(gè)本不在緩存中的方法找到imp后窖杀，將會(huì)進(jìn)行緩存填充漓摩，把新的方法放入緩存中，方便下一次可以直接在緩存中找方法入客，不需要再次經(jīng)過(guò)慢速查找：

log_and_fill_cache(Class cls, IMP imp, SEL sel, id receiver, Class implementer)
{
#if SUPPORT_MESSAGE_LOGGING
    if (slowpath(objcMsgLogEnabled && implementer)) {
        bool cacheIt = logMessageSend(implementer->isMetaClass(), 
                                      cls->nameForLogging(),
                                      implementer->nameForLogging(), 
                                      sel);
        if (!cacheIt) return;
    }
#endif
    cls->cache.insert(sel, imp, receiver);
}

看到cls->cache.insert(sel, imp, receiver);管毙，終于達(dá)到了終點(diǎn)insert方法！

總結(jié)

綜合之前幾篇我們的學(xué)習(xí)桌硫，可以得到一個(gè)整體的流程：
1.類的結(jié)構(gòu)中有方法列表methods和緩存的方法列表cache_t夭咬；
2.對(duì)對(duì)象發(fā)送消息時(shí)執(zhí)行objc_msgSend；
3.objc_msgSend時(shí)會(huì)先在cache中找鞍泉，沒(méi)有就會(huì)調(diào)用objc_msgSend_uncached走到lookUpImpOrForward方法進(jìn)行循環(huán)慢速查找皱埠，通過(guò)二分法去methods中查找；
4.如果沒(méi)找到則會(huì)開(kāi)始遞歸咖驮，到父類的緩存中找边器，找不到的話不會(huì)調(diào)用objc_msgSend_uncached，而是返回空并且繼續(xù)lookUpImpOrForward循環(huán)托修，這次循環(huán)時(shí)忘巧，查找的目標(biāo)cls變?yōu)閟uperClass，對(duì)superClass進(jìn)行慢速查找睦刃，最終到根類砚嘴；
4.如果在cache中找到，則直接執(zhí)行涩拙；如果在methods中找到际长，則把方法插入緩存insert；
5.如果都沒(méi)有兴泥，開(kāi)始消息轉(zhuǎn)發(fā)流程工育。