第九節(jié)課 消息慢速查找

上篇文章我們分析了快速查找流程荸百，并繪制了流程圖，結(jié)尾處滨攻，當(dāng)快速查找結(jié)束并沒(méi)有找到想要的够话，這個(gè)時(shí)候我們就來(lái)到了慢速查找流程了。我們先來(lái)簡(jiǎn)單回顧下光绕，然后再繼續(xù)分析慢速查找流程

objc_mesgSend流程回顧

1: cmp    p0, #0

2: GetClassFromIsa_p16 p13, 1, x0    // p16 = class

3: CacheLookup NORMAL, _objc_msgSend, __objc_msgSend_uncached

3.1 : LLookupStart -> CACHE_MASK_STORAGE_HIGH_16

// 獲取cache
ldr    p11, [x16, #CACHE]            // p11 = mask|buckets

CONFIG_USE_PREOPT_CACHES == 1

// p11 的 0 號(hào)位置是否為0  不為0 -> LLookupPreopt（共享緩存）
tbnz    p11, #0, LLookupPreopt\Function
and    p10, p11, #0x0000fffffffffffe    // p10 = buckets

// p1 sel >> 7 等價(jià)于 value ^= value >> 7;
//為什么右移7位女嘲？因?yàn)樵趍ask_t cache_hash的讀取的時(shí)候就是右移的7位，相互對(duì)應(yīng)
eor    p12, p1, p1, LSR #7
// 哈希 index
//前48位是Bucket奇钞，后16位是mask澡为，右移48位后得到mask
and    p12, p12, p11, LSR #48        // x12 = (_cmd ^ (_cmd >> 7)) & mask

// index << 4
// 2 * 16（左移4位相當(dāng)于*16）
// buckets + 32
// 對(duì)應(yīng)下標(biāo) : p13 第一個(gè)要查bucket(sel imp)
add    p13, p10, p12, LSL #(1+PTRSHIFT)
                    // p13 = buckets + ((_cmd & mask) << (1+PTRSHIFT))
// sel -> imp

                        // do {
//  *bucket--  p17, p9
//  bucket 里面的東西 imp (p17) sel (p9)
//  查到的 sel (p9) 和我們 say1
//  循環(huán)查找漂坏，直到Hit
1:  ldp p17, p9, [x13], #-BUCKET_SIZE   //     {imp, sel} = *bucket--
    cmp p9, p1              //     if (sel != _cmd) {
    b.ne    3f              //         scan more
                        //     } else {
2:  CacheHit \Mode              // hit:    call or return imp
                        //     }
3:  cbz p9, \MissLabelDynamic       //     if (sel == 0) goto Miss;
    cmp p13, p10            // } while (bucket >= buckets)
    b.hs    1b 
    
                        // do {
4:  ldp p17, p9, [x13], #-BUCKET_SIZE   //     {imp, sel} = *bucket--
    cmp p9, p1              //     if (sel == _cmd)
    b.eq    2b              //         goto hit
    cmp p9, #0              // } while (sel != 0 &&
    ccmp    p13, p12, #0, ne        //     bucket > first_probed)
    b.hi    4b

__objc_msgSend_uncached

此方法是進(jìn)入慢速查找流程的起因景埃，此方法是作為參數(shù)傳遞進(jìn)CacheLookup的，如果CacheLookup查找不到imp的時(shí)候會(huì)執(zhí)行MissLabelDynamic顶别，也就是執(zhí)行了__objc_msgSend_uncached

在objc-msg-arm64.s文件中查找__objc_msgSend_uncached的匯編實(shí)現(xiàn)谷徙，其中的核心是MethodTableLookup（即查詢(xún)方法列表），其源碼如下

    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
    // imp
    MethodTableLookup
    TailCallFunctionPointer x17

    END_ENTRY __objc_msgSend_uncached

MethodTableLookup

    SAVE_REGS MSGSEND

    // lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
    // receiver and selector already in x0 and x1
    //lookUpImpOrForward方法需要4個(gè)參數(shù)：
    //obj      = x0
    //sel      = x1
    //cls      = x2
    //behavior = x3 = 3
    mov x2, x16
    mov x3, #3
    //bl：跳轉(zhuǎn)指令驯绎，并將回家的路存在x30寄存器（lr）
    bl  _lookUpImpOrForward

    // IMP in x0 --
    // 經(jīng)過(guò)_lookUpImpOrForward拿到的返回值（IMP）將存在x0位置
    // 將x0賦值給x17
    mov x17, x0

    RESTORE_REGS MSGSEND

保存信息方法完慧，已知x0是receiver，x1是_cmd,即sel剩失，先將x16（LGPerson類(lèi)）存在x2寄存器屈尼，將3存在x3寄存器，然后跳轉(zhuǎn)至關(guān)鍵方法_lookUpImpOrForward拴孤，這個(gè)方法返回值在匯編的角度來(lái)看是儲(chǔ)存在x0寄存器的脾歧，所以當(dāng)_lookUpImpOrForward執(zhí)行完成，將返回值x0存入x17.

TailCallFunctionPointer

//A12以上芯片（支持arm64e結(jié)構(gòu)）
#if __has_feature(ptrauth_calls)
// JOP
.macro TailCallFunctionPointer
    // $0 = function pointer value
    // $0 表示的是參數(shù)x17
    braaz   $0
.endmacro

#else
// not JOP

.macro TailCallFunctionPointer
    // $0 = function pointer value
    // $0 表示的是參數(shù)x17
    br  $0
.endmacro

總結(jié)一下：

1. 當(dāng)快速查找流程無(wú)法命中的時(shí)候會(huì)進(jìn)入慢速查找流程

2. 慢速查找流程__objc_msgSend_uncached會(huì)執(zhí)行2行代碼

• MethodTableLookup（去查找并返回imp）
• TailCallFunctionPointer（跳轉(zhuǎn)至x17寄存器演熟，也就是imp所在的寄存器）

4. 慢速查找流程將會(huì)進(jìn)入C++中執(zhí)行鞭执，然后通過(guò)x0寄存器返回司顿，繼續(xù)在匯編中向下執(zhí)行，方法查找流程最終會(huì)跳轉(zhuǎn)至x17寄存器（無(wú)論是慢速查找還是快速查找兄纺。

lookUpImpOrForward（慢速查找流程核心）

根據(jù)匯編部分的提示大溜，全局續(xù)搜索lookUpImpOrForward，最后在objc-runtime-new.mm文件中找到了源碼實(shí)現(xiàn)估脆，這是一個(gè)c實(shí)現(xiàn)的函數(shù)

// 緩存 找不到 - lookUpImpOrForward - 慢速 - methodlist
// 匯編 緩存 參數(shù)未知

NEVER_INLINE
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    IMP imp = nil;
    Class curClass;

    runtimeLock.assertUnlocked();

    if (slowpath(!cls->isInitialized())) {
        behavior |= LOOKUP_NOCACHE;
    }
    runtimeLock.lock();

    //檢查類(lèi)是否被注冊(cè)了 
    checkIsKnownClass(cls);
    
    /**初始化跟cls實(shí)例對(duì)象在isa指向圖中的每一個(gè)類(lèi)（class钦奋、superClass、metaClass）
    以便后續(xù)自己類(lèi)里面找不到方法去父類(lèi)里面依次向上找
    所以在此處對(duì)所有相關(guān)的類(lèi)進(jìn)行了初始化
    對(duì)rw疙赠、ro的一些處理锨苏，后面會(huì)講
    */
    cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
    runtimeLock.assertLocked();
    curClass = cls;

    /**
      循環(huán)查找類(lèi)對(duì)象的methodList，當(dāng)前類(lèi)沒(méi)有的話就找父類(lèi)
      父類(lèi)沒(méi)有就找父類(lèi)的父類(lèi)棺聊，一直找到NSObject類(lèi)
      如果NSObject都找不到的話最終curClass會(huì)指向nil
      將事先準(zhǔn)備好的forward_imp賦值給imp
      然后結(jié)束慢速查找流程伞租，接下來(lái)進(jìn)入Runtime消息轉(zhuǎn)發(fā)機(jī)制
    */

    for (unsigned attempts = unreasonableClassCount();;) {
        if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
        //再次查找共享緩存，防止查找過(guò)程中有新的插入限佩。通常情況下我們的自定義方法不會(huì)出現(xiàn)在共享緩存中
#if CONFIG_USE_PREOPT_CACHES
            imp = cache_getImp(curClass, sel);
            if (imp) goto done_unlock;
            curClass = curClass->cache.preoptFallbackClass();
#endif
        } else {
            // curClass method list.
            //在當(dāng)前類(lèi)的方法列表里面查找葵诈，這是重點(diǎn)。查找算法是二分法
            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.
        // 父類(lèi) 快速 -> 慢速 ->
        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;
        }
    }

    // No implementation found. Try method resolver once.

    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

 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);
    }
 done_unlock:
    runtimeLock.unlock();
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
    return imp;
}

getMethodNoSuper_nolock(二分查找流程)

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

    ASSERT(cls->isRealized());

    //獲取methodList祟同，methodList因?yàn)閿?shù)據(jù)類(lèi)型的原因可能為二維數(shù)組
    //循環(huán)條件是數(shù)組不為空作喘，即開(kāi)始位置不等于結(jié)束位置
    auto const methods = cls->data()->methods();
    for (auto mlists = methods.beginLists(),
              end = methods.endLists();
         mlists != end;
         ++mlists)
    {
        //進(jìn)入search_method_list_inline修復(fù)為有序list
        method_t *m = search_method_list_inline(*mlists, sel);
        if (m) return m;
    }

    return nil;
}

getMethodNoSuper_nolock->search_method_list_inline->findMethodInSortedMethodList逐步深入，進(jìn)入二分法核心算法代碼如下：

ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
    ASSERT(list);

    const method_t * const first = &list->first;
    const method_t *base = first;
    const method_t *probe;
    uintptr_t keyValue = (uintptr_t)key; //key 等于 say666
    uint32_t count;
    //base相當(dāng)于low晕城，count是max泞坦，probe是middle，這就是二分
    for (count = list->count; count != 0; count >>= 1) {
        //從首地址+下標(biāo) --> 移動(dòng)到中間位置（count >> 1 右移1位即 count/2 = 4）
        probe = base + (count >> 1); 
        
        uintptr_t probeValue = (uintptr_t)probe->name;
        
        //如果查找的key的keyvalue等于中間位置（probe）的probeValue砖顷，則直接返回中間位置
        if (keyValue == probeValue) { 
            // -- while 平移 -- 排除分類(lèi)重名方法
            while (probe > first && keyValue == (uintptr_t)probe[-1].name) {
                //排除分類(lèi)重名方法（方法的存儲(chǔ)是先存儲(chǔ)類(lèi)方法贰锁，在存儲(chǔ)分類(lèi)---按照先進(jìn)后出的原則，分類(lèi)方法最先出滤蝠，而我們要取的類(lèi)方法豌熄，所以需要先排除分類(lèi)方法）
                //如果是兩個(gè)分類(lèi)，就看誰(shuí)先進(jìn)行加載
                probe--;
            }
            return (method_t *)probe;
        }
        
        //如果keyValue 大于 probeValue物咳，就往probe即中間位置的右邊查找
        if (keyValue > probeValue) { 
            base = probe + 1;
            count--;
        }
    }
    
    return nil;
}

算法原理：從第一次查找開(kāi)始锣险，每次都取中間位置，與想查找的key的value值作比較览闰，如果相等芯肤，則需要排除分類(lèi)方法，然后將查詢(xún)到的位置的方法實(shí)現(xiàn)返回压鉴，如果不相等崖咨，則需要繼續(xù)二分查找，如果循環(huán)至count = 0還是沒(méi)有找到晴弃，則直接返回nil掩幢，如下所示：

09-二分查找.png

例子：

假設(shè)要查找的sel對(duì)應(yīng)的在第7位逊拍，list.count=8

第一次進(jìn)入循環(huán)，probe = base + （ 8 >> 1 ） = 0 + 4 = 4

那么第一次查找的范圍就是0-8际邻，匹配元素位置是4芯丧，判定結(jié)果keyValue（7）> prebeValue(4)，未匹配

滿(mǎn)足keyValue > probeValue世曾，base = probe + 1 = 4 + 1 = 5缨恒，count-- = 7

第二次進(jìn)入循環(huán)，此時(shí)count = 7 >> 1 = 3, probe = 5 + 3 >> 1 = 6

第二次查找的范圍是5-8轮听，匹配元素位置是6骗露，判定結(jié)果keyValue（7）> prebeValue(6)，未匹配

滿(mǎn)足keyValue > probeValue血巍，base = probe + 1 = 6 + 1 = 7萧锉，count-- = 2

第三次進(jìn)入循環(huán)，此時(shí)count = 2 >> 1 = 1, probe = 7 + 1 >> 1 = 7

第三次查找的元素是7述寡，匹配柿隙，返回imp

log_and_fill_cache(緩存填充)

如果記錄器允許，調(diào)用cache的insert方法鲫凶，將其插入緩存禀崖，下一次的查找就會(huì)進(jìn)行快速緩存查找了。

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

總結(jié)

lookUpImpOrForward螟炫，此過(guò)程為慢速查找流程波附，通過(guò)死循環(huán)的方式不斷遍歷來(lái)查找imp，對(duì)于全局性來(lái)講昼钻，首先去找共享緩存掸屡，然后查自己的methodList，如果自己沒(méi)有换吧，找父類(lèi)折晦，父類(lèi)沒(méi)有钥星，找NSObject沾瓦，NSObject沒(méi)有，會(huì)指向nil谦炒，最終跳出來(lái)贯莺。

共享緩存 -> methodList -> 父類(lèi) -> NSObject -> nil - >跳出循環(huán)

補(bǔ)充點(diǎn)：

為什么快速查找緩存要使用匯編編寫(xiě)，而不是用C++編寫(xiě)呢宁改？

匯編更接近機(jī)器的語(yǔ)言缕探，執(zhí)行效率非常的快，安全还蹲，這是優(yōu)點(diǎn)爹耗。但是由于方法是特別的多耙考，通過(guò)匯編查找緩存的方式可以最大程序的優(yōu)化執(zhí)行效率。另外潭兽，匯編在執(zhí)行的時(shí)候倦始，參數(shù)可以是未知的，這一點(diǎn)區(qū)別與C/C++山卦，參數(shù)一定是調(diào)用前就已經(jīng)指定好了鞋邑，明確參數(shù)，匯編的另一優(yōu)點(diǎn)也就體現(xiàn)了账蓉，相對(duì)于C/C++更加的動(dòng)態(tài)化枚碗。

為什么要執(zhí)行慢速查找流程，全部使用匯編進(jìn)行快速查找不爽嗎铸本？

因?yàn)樵诰彺嬷幸呀?jīng)找不到了肮雨，進(jìn)入了慢速查找流程，這個(gè)時(shí)候需要去找方法箱玷，不斷的遍歷methodList的過(guò)程酷含，通過(guò)isa的指向關(guān)系，自己找不到汪茧，找爸爸椅亚，爸爸找不到，找爺爺舱污，一路向上遍歷查找呀舔，直到nil。因?yàn)檫@個(gè)過(guò)程是一個(gè)耗時(shí)過(guò)程扩灯，所以放在C/C++中執(zhí)行媚赖。