前言

在上一篇快速查找提到，如果快速查找無法找到相對應的方法，則會進入慢速查找流程，此篇重點在於慢速查找。

流程分析

慢速查找-(彙編)

在快速查找中，第一次遞歸循環，如果找不到會跳轉到CheckMiss 最終進入__objc_msgSend_uncached ，即進入慢速查找流程 ，以及第二次遞歸循環中 ，最終也會跳轉到JumpMiss 也會進入到__objc_msgSend_uncached 也會進入慢速查找流程 。
接著我們開始查找__objc_msgSend_uncached 的彙編實現，可以在objc-msg-arm64.s ，中搜尋到__objc_msgSend_uncached的彙編實現。

  STATIC_ENTRY __objc_msgSend_uncached
    UNWIND __objc_msgSend_uncached, FrameWithNoSaves

    // THIS IS NOT A CALLABLE C FUNCTION
    // Out-of-band p16 is the class to search

  //查找方法列表
    MethodTableLookup
    TailCallFunctionPointer x17

    END_ENTRY __objc_msgSend_uncached

搜索MethodTableLookup ,可以看到通過寄存器的存儲會跳轉到_lookUpImpOrForward
此時可能會想用全局搜索查找_lookUpImpOrForward 然而你會發現找不到我們想要的實現，為什麼呢?我們可以通過彙編調適來了解到為什麼

.macro MethodTableLookup

    // push frame
    SignLR
    stp fp, lr, [sp, #-16]!
    mov fp, sp

    // save parameter registers: x0..x8, q0..q7
    sub sp, sp, #(10*8 + 8*16)
    stp q0, q1, [sp, #(0*16)]
    stp q2, q3, [sp, #(2*16)]
    stp q4, q5, [sp, #(4*16)]
    stp q6, q7, [sp, #(6*16)]
    stp x0, x1, [sp, #(8*16+0*8)]
    stp x2, x3, [sp, #(8*16+2*8)]
    stp x4, x5, [sp, #(8*16+4*8)]
    stp x6, x7, [sp, #(8*16+6*8)]
    str x8,     [sp, #(8*16+8*8)]

    // 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 registers and return
    ldp q0, q1, [sp, #(0*16)]
    ldp q2, q3, [sp, #(2*16)]
    ldp q4, q5, [sp, #(4*16)]
    ldp q6, q7, [sp, #(6*16)]
    ldp x0, x1, [sp, #(8*16+0*8)]
    ldp x2, x3, [sp, #(8*16+2*8)]
    ldp x4, x5, [sp, #(8*16+4*8)]
    ldp x6, x7, [sp, #(8*16+6*8)]
    ldr x8,     [sp, #(8*16+8*8)]

    mov sp, fp
    ldp fp, lr, [sp], #16
    AuthenticateLR

.endmacro

調適驗證

我們可以使用下斷點的方式透過流程更加直觀的來看到上述的彙編，首先我們在main文件中的對象方法[person sayHello];添加一個斷點，並且進入彙編模式開啟【Debug -- Debug workflow -- 勾選Always show Disassembly】，進入程序，如下圖

並且在objc_msgSend下一個斷點，過掉斷點，斷點來到了objc_msgSend後，按住control + stepinto，進入objc_msgSend的彙編

可以在下方看到_objc_msgSend_uncached ，一樣我們下一個斷點，按住control + stepinto進入彙編

透過上述彙編調適可以看到最後走到lookUpImpOrForward 並且得知objc-runtime-new.mm文件的6099行
彙編文件中調用了C/C++文件的方法，那麼需要去掉下滑線。
反之C/C++文件中調到進入彙編文件的方法，此時需要將要查找的方法加一個下滑線。

慢速查找-(C/C++)

有了彙編找到的lookUpImpOrForward 我們在objc-runtime-new.mm文件中搜尋，可以看到C++語言的源碼實現。

 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();
     // 快速查找，如果找到則直接返回imp
     // 目的:防止多線程操作時，剛好調用函數，此時緩存進來了
     // Optimistic cache lookup
     if (fastpath(behavior & LOOKUP_CACHE)) {
         imp = cache_getImp(cls, sel);
         if (imp) goto done_nolock;
     }

     // 加鎖:目的是保證讀取的線成安全
     runtimeLock.lock();

     //判斷是否是一個已知的類:判斷當前是否已經被認可的類，即已經加載的類
     checkIsKnownClass(cls);

     //判斷類是否實現，如果沒有，需要先實現，此時目的是為了確定父類鏈，方法後續的循環
     if (slowpath(!cls->isRealized())) {
         cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
         // runtimeLock may have been dropped but is now locked again
     }
     //判斷類是否初始化，如果沒有，需要先初始化
     if (slowpath((behavior & LOOKUP_INITIALIZE) && !cls->isInitialized())) {
         cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
         // runtimeLock may have been dropped but is now locked again
     }

     runtimeLock.assertLocked();
     curClass = cls;

          //---查找類的緩存
      //unreasonableClassCount表示類的迭代的上限
      //(猜測這裡遞歸的原因是attempts在第一次循環時做了減一的操作，然後再次循環，若還是在上限範圍內，則繼續遞歸)
     for (unsigned attempts = unreasonableClassCount();;) {
         //---當前類方法列表(採用二分查找法)，如果找到，則返回，將方法緩存到cache中
         Method meth = getMethodNoSuper_nolock(curClass, sel);
         if (meth) {
             imp = meth->imp;
             goto done;
         }
         // 當前類 = 當前類的父類，並判斷父類是否為nil
         if (slowpath((curClass = curClass->superclass) == nil)) {
             //---未找到方法實現，方法解析器也不行，使用轉發
             imp = forward_imp;
             break;
         }

         //如果父類鏈中存在循環，則停止
         if (slowpath(--attempts == 0)) {
             //--未找到方法實現，方法解析器也不行，使用轉發
             _objc_fatal("Memory corruption in class list.");
         }

         //--父類緩存
         imp = cache_getImp(curClass, sel); // 有问题???? cache_getImp - lookup - lookUpImpOrForward
         if (slowpath(imp == forward_imp)) {
             // 如果在父類中找到了forward，則停止查找，且不緩存，首先調用此類的方法解析器
             break;
         }
         if (fastpath(imp)) {
             //如果在父類中找到了此方法 將其存儲到cache中
             goto done;
         }
     }

     // 沒有找到方法實現 嘗試一次方法解析

     if (slowpath(behavior & LOOKUP_RESOLVER)) {
         //動態方法決議的控制條件，表示流程只走一次
         behavior ^= LOOKUP_RESOLVER;
         return resolveMethod_locked(inst, sel, cls, behavior);
     }

  done:
     //存儲到緩存
     log_and_fill_cache(cls, imp, sel, inst, curClass);
     //解鎖
     runtimeLock.unlock();
  done_nolock:
     if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
         return nil;
     }
     return imp;
 }

流程圖如下

步驟解析

【第一步】cache緩存中進行查找，即快速查找，找到則直接返回imp，相反則進入第二步
【第二步】判斷cls
- 是否是已知類，如果不是，則報錯。
- 類是否實現，如果沒有，則需要先實現，確定其父類鏈，此時實例化的目的是為了確定父類鏈，ro，以及rw等，方法後續數據的讀取以及查找的循環。
- 是否初始化，如果沒有，則初始化。
【第三步】for循環。按照類繼承鏈或者元類繼承鏈的順序查找
- 當前cls的方法列表中使用二分查找算法查找方法，如果找到，則進入cache寫入流程，並返回imp，如果沒有找到，則返回nil。
- 當前cls被賦值為父類，如果父類等於nil，則imp = 消息轉發，並終止遞歸，進入第四步。
- 如果父類鏈中存在循環，則報錯，終止循環
- 父類緩存中查找方法
- 如果未找到，則直接返回nil，繼續循環查找
- 如果找到，則直接返回imp，執行cache寫入流程
【第四步】判斷是否執行過動態方法解析
- 如果沒有，執行動態方法解析
- 如果執行過一次動態方法解析，則走到消息轉發流程

以上就是方法的慢速查找流程，下面在分別詳細解釋二分查找原理，以及父類緩存查找詳細步驟

getMethodNoSuper_nolock方法：二分查找方法列表

查找方法列流程如下圖所示

二分查找核心的源碼實現如下

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相当于low，count是max，probe是middle，这就是二分
    for (count = list->count; count != 0; count >>= 1) {
        //从首地址+下标 --> 移动到中间位置（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 平移 -- 排除分类重名方法
            while (probe > first && keyValue == (uintptr_t)probe[-1].name) {
                //排除分类重名方法（方法的存储是先存储类方法，在存储分类---按照先进后出的原则，分类方法最先出，而我们要取的类方法，所以需要先排除分类方法）
                //如果是两个分类，就看谁先进行加载
                probe--;
            }
            return (method_t *)probe;
        }

        //如果keyValue 大于 probeValue，就往probe即中间位置的右边查找
        if (keyValue > probeValue) { 
            base = probe + 1;
            count--;
        }
    }

    return nil;
}

算法原理簡述為:從第一次查找開始，每次都取中間位置，與想查找的key的value值做比較，如果相等，則需要排除分類方法，然後將查詢的位置的方法實現返回，如果不相等，則需要繼續二分查找，如果循環至count = 0 還是沒有找到，則直接返回nil，如下所示：

以查找LGPerson類的say666實例方法為例，其二分查找過程如下

cache_getImp方法：父類緩存查找

cache_getImp 方法是通過彙編_cache_getImp實現，傳入的$0是GETIMP，如下所示
如果父類緩存中，沒有找到方法實現，則跳轉到CheckMiss或者JumpMiss，通過判斷$0跳轉至LGetImpMiss，直接返回nil

總結

對於對象方法(即實例方法)，即在類中查找，其中慢速查找的父類鏈是：類—父類—根類—nil
對於類方法，即在元類中查找，其中慢速查找的父類鏈是：元類—根元類—根類—nil
如果快速查找，慢速查找也沒有找到方法實現，則嘗試動態方法決議
如果動態分方法決議仍然没有找到，則進行消息轉發

常見方法為實現報錯源碼

如果快速查找，慢速查找，方法解析流程中，均沒有找到實現，則使用消息轉發，其流程如下

消息轉發會實現
其中_objc_msgForward_impcache 是彙編實現，會跳轉至_ _objc_msgForward ，其核心是__objc_forward_handler

STATIC_ENTRY __objc_msgForward_impcache

// No stret specialization.
b   __objc_msgForward

END_ENTRY __objc_msgForward_impcache

//👇
ENTRY __objc_msgForward

adrp    x17, __objc_forward_handler@PAGE
ldr p17, [x17, __objc_forward_handler@PAGEOFF]
TailCallFunctionPointer x17

END_ENTRY __objc_msgForward

彙編實現中查找_ _objc_forward_handler ,並沒有找到，在源碼中去掉一個下滑線進行全局搜索_objc_forward_handler 有如下實現，本質是調用objc_defaultForwardHandler 方法。

// Default forward handler halts the process.
__attribute__((noreturn, cold)) void
objc_defaultForwardHandler(id self, SEL sel)
{
    _objc_fatal("%c[%s %s]: unrecognized selector sent to instance %p "
                "(no message forward handler is installed)", 
                class_isMetaClass(object_getClass(self)) ? '+' : '-', 
                object_getClassName(self), sel_getName(sel), self);
}
void *_objc_forward_handler = (void*)objc_defaultForwardHandler;

看著objc_defaultForwardHandler ，這就是我們日常開發中最常見的錯誤：沒有實現函數，進行程序，崩潰時報的錯誤提示

objc_msgSend流程分析(慢速查找)

objc_msgSend流程分析(慢速查找)

前言

流程分析

慢速查找-(彙編)

調適驗證

慢速查找-(C/C++)

步驟解析

getMethodNoSuper_nolock方法：二分查找方法列表

cache_getImp方法：父類緩存查找

總結

常見方法為實現報錯源碼