前言

上一篇文章讲了_objc_msgSend快速查找的大致流程，如果根据sel找到了对应imp就直接去执行，如果没有找到就执行MissLabelDynamic。这篇文章来看看MissLabelDynamic是怎么实现的。

lookUpImpOrForward

探索来源

       CacheLookup NORMAL, _objc_msgSend, __objc_msgSend_uncached
.macro CacheLookup Mode, Function, MissLabelDynamic, MissLabelConstant
复制代码

可以看到MissLabelDynamic是在执行_objc_msgSend时传进来的，传入的参数是__objc_msgSend_uncached，接着查找__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

.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

.macro TailCallFunctionPointer
    // $0 = function pointer value
    br	$0
.endmacro
复制代码

把相关代码全部找出来。
__objc_msgSend_uncached里主要的就两句，第二句TailCallFunctionPointer就一个执行命令br $0，再看MethodTableLookup主要是一些加载赋值操作，最主要的还是一句bl _lookUpImpOrForward，意思是跳转到指令_lookUpImpOrForward。

找找它的实现，通过全局搜索没有找到它的实现，只有调用，那么实现在哪里呢？
想一想，如果汇编里面找不到，可能就在C++里，不可能是在llvm里。

那么去掉下划线重新搜索。bingo，找到了，果然是在C++里面。而且看到方法的实现总感觉似曾相识。这不就是之前探索cache_t的时候，找到的调用log_and_fill_cache()的地方么。这样一下子就串起来了，先来探究下lookUpImpOrForward里面做了些什么操作。

方法实现

查找准备

lookUpImpOrForward函数的实现代码过长，之前讲过代码很多的函数，就直接找重点。这个函数就是返回imp，那么就找到imp在哪里赋值的。

可以看到imp的赋值主要是在这个for循环里，那我们就重点研究这段代码。
首先看到的第一个参数就是curClass，先来看看这个是怎么来的。

获取当前实例对象的类

cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
curClass = cls;
复制代码

通过下图来了解下大致流程。

类的实现和初始化.png

开始查找

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
}
复制代码

这里判断是否使用了共享缓存器，如果是就调用cache_getImp。看看这里怎么实现的，全局搜索，在汇编里找到。

    STATIC_ENTRY _cache_getImp

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

LGetImpMissDynamic:
    mov	p0, #0
    ret

LGetImpMissConstant:
    mov	p0, p2
    ret

    END_ENTRY _cache_getImp
复制代码

看到这里，这不就是之前的objc_msgSend里的指令么，怎么又要调用一次。其实主要是因为在开始循环之前的一系列操作或者说有其他地方调用了这个方法，那么缓存中就可能存在了，就可以尝试再走一遍快速查找获取，如果找到了就可以直接返回，就不用再经历一次慢速查找。如果没找到，接着往下走。

Method meth = getMethodNoSuper_nolock(curClass, sel);
if (meth) {
    imp = meth->imp(false);
    goto done;
}
复制代码

这一步是通过当前的class获取meth，为什么要到class去查找，因为方法的缓存就是放在isa的cache里，而实例对象的isa就是它的类。

static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
    auto const methods = cls->data()->methods();
    for (auto mlists = methods.beginLists(), end = methods.endLists();
         mlists != end;
        ++mlists)
    {
        method_t *m = search_method_list_inline(*mlists, sel);
        if (m) return m;
    }
}
复制代码

这个函数获取里包含一个循环，获取到方法的开始数组和结束数组，知道开始数组和结束数组相等，就结束循环。循环里就调用了search_method_list_inline()。

ALWAYS_INLINE static method_t *
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;
    }
}
复制代码

这里就开始查找方法，先判断是否整理过方法列表，如果整理过就进入findMethodInSortedMethodList()，没有整理过就进入findMethodInUnsortedMethodList()。

findMethodInSortedMethodList()

template<class getNameFunc>
ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)
{
    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;
}
复制代码

这个是按序查找的函数实现，为了方便理解，再来画个图。

未命名绘图.png

图中就是大概的查找流程，为了方便理解，使用的脚标来计算，实际上应该是计算的内存地址，通过内存偏移来获取相应的method_t。
通过上图可以看出，本来应该要循环6次才能找到的方法，只用了3次就找到了。这里用的就是著名的二分查找法，这里的例子只用了8个方法，但是我们实际开发当中，远远不止这个数，所以用更高效的查找方法能够大大的节省性能。并且这个二分查找的算法也是写的相当好，大家可以借鉴这个写法。
这里还有注意的一点，在找到了目标sel的时候，还使用了这个判断probe > first && keyValue == (uintptr_t)getName((probe - 1)，这是为什么呢？其实可以看到上面有注释，因为如果该类有分类，且方法重名，那就要优先使用分类里的实现。

findMethodInUnsortedMethodList()

template<class getNameFunc>
ALWAYS_INLINE static method_t *
findMethodInUnsortedMethodList(SEL sel, const method_list_t *list, const getNameFunc &getName)
{
    for (auto& meth : *list) {
        if (getName(meth) == sel) return &meth;
    }
    return nil;
}
复制代码

这个是无序的方法查找，这个就简单暴力一点了，就是遍历整个数组，找到符合的sel直接返回。

查找结果

如果找到了对应的imp，就goto done，done里先判断是否使用共享缓存，如果使用了，就对cls的共享缓存类（这是个什么，暂时不知），然后调用log_and_fill_cache()，这个也和之前看到的串联起来。
逻辑大概就是调用方法 -> 快速查找 -> 未找到，慢速查找 -> 找到了，把imp和sel写入到缓存，形成了一个闭环，非常厉害。

如果没有找到对应的imp，就执行imp = cache_getImp(curClass, sel)，之前不是又快速查找了一次，这里怎么又又要快速查找？其实这里的curClass已经不是当前实例对象的class了，而是class的superclass，因为如果没有找到会执行一次if (slowpath((curClass = curClass->getSuperclass()) == nil))。
cache_getImp在上面已经讲过了，如果在快速查找到了，就直接返回imp，执行goto done。如果没有找到，就返回nil，再走一次循环，通过父类的class去走慢速查找，知道找到对应的imp。
那么如果最后都没有找到呢？这时imp = forward_imp。至此，慢速查找就基本结束了。