前言

在上篇文章iOS探索底层-objc_msgSend&快速方法查找中，我们探索了objc_msgSend调用过程中的快速查找流程，并分析了其汇编代码，它主要是在cache中快速的查找是否存在方法的缓存，如果存在，则直接调用。但是我们遗留了一个问题，那就是如果没有查找到，会怎么办呢。今天我们就来探索如果快速方法查找没有找到，苹果会进行什么操作。

objc_msgSend_uncached

在上篇文章中，我们分析到了，如果没有在方法的快速查找流程中没有找到的话，最后会调用\MissLabelDynamic这个参数，这个参数实际上就是我们调用CacheLookup函数时传入的__objc_msgSend_uncached这个方法，那么我们全局搜索他

TailCallFunctionPointer

很简单的几行汇编代码，其中只有两个方法，一个叫做MethodTableLookup，一个叫做TailCallFunctionPointer。因为方法的返回值才是最重要的，所以从后面开始看，全局搜索TailCallFunctionPointer

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

非常简单的代码，就是返回并跳转到$0位置执行，实际上就是返回的函数。

MethodTableLookup

既然如此，那么x17就只能在MethodTableLookup进行赋值了，继续去探索他

.macro MethodTableLookup
	SAVE_REGS MSGSEND
	// lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
	// receiver and selector already in x0 and x1
        //**将x16赋值给x2,也就是我们的Class，类对象**
	mov	x2, x16
        //**将3赋值给x3**
	mov	x3, #3
	bl	_lookUpImpOrForward

	//**将x0赋值给x17**
	mov	x17, x0

	RESTORE_REGS MSGSEND

.endmacro
复制代码

_lookUpImpOrForward

在这个方法里，我们很轻易的找到了给x17赋值的地方，就是x0，那么x0是什么呢？就只能去_lookUpImpOrForward中寻找答案了，因为x0就是他的返回值。

在搜索结果中，并没有发现函数的实现，只有函数的调用，那么怎么办呢？我们将_去掉，直接搜索lookUpImpOrForward看看

很神奇，我们在objc-runtime-new.mm中找到了这个方法的实现，并且它的返回值，就是我们要寻找的IMP。

总结

我们简单的梳理一下objc_msgSend_uncached的流程

将MethodTableLookup方法的返回值x17通过TailCallFunctionPointer返回回去
MethodTableLookup方法中，通过_lookUpImpOrForward方法查找到IMP然后赋值给x17

那么为什么快速方法是用汇编编写的，而后面的lookUpImpOrForward方法查找流程为什么用C/C++写呢？答案是

汇编编写的代码，更加接近机器语言，执行效率更高。而在缓存中查找的目的也是为了更加的效率，所以快速方法查找流程使用汇编编写更加适合。

汇编代码相对来说更加难以理解，比起C/C++更加安全

汇编中的参数更加动态化，不像C/C++中调用方法必须参数确定，否则就无法调用

lookUpImpOrForward流程

探索完了objc_msgSend_uncached，我们就来看看lookUpImpOrForward到底干了什么。

NEVER_INLINE
//**behavior = 3 LOOKUP_INITIALIZE|LOOKUP_RESOLVER**
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();

    //**判断类是否有初始化，如果没有初始化**
    //**则behavior =LOOKUP_INITIALIZE|LOOKUP_RESOLVER|LOOKUP_NOCACHE **
    if (slowpath(!cls->isInitialized())) {
    
        behavior |= LOOKUP_NOCACHE;
    }

    runtimeLock.lock();
    //**判断是否注册类**
    checkIsKnownClass(cls);
    //**初始类的，父类、元类，已经父类的父类、元类等等，直到根类和根源类初始化完毕**
    cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
    runtimeLock.assertLocked();
    curClass = cls;
    //**进入循环，死循环，必须在内部有跳转才能出来**
    for (unsigned attempts = unreasonableClassCount();;) {
        //**判断是否有共享缓存，一般是系统的函数方法才能调用**
        if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
#if CONFIG_USE_PREOPT_CACHES
            //**这里也是调用到了`_cache_getImp`汇编代码，最终调用了`CacheLookup`查找共享缓存**
            //**因为可能在你调用的过程中，其他线程已经写入缓存了，那就可以直接调用了**
            imp = cache_getImp(curClass, sel);
            //**如果找到就直接跳出到done_unlock**
            if (imp) goto done_unlock;
            //**我理解为标记为不使用共享缓存，然后在下次循环时，就走else流程继续查找了**
            curClass = curClass->cache.preoptFallbackClass();
#endif
        } else {
            //**获取当前类的方法列表,使用二分查找法去查找对应sel的Method**
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {
                //**找到了，则获取对应sel的imp**
                imp = meth->imp(false);
                //**找到了则直接跳转到done**
                goto done;
            }
            
            //**将curClass赋值为它的父类，并且判断是否等于nil**
            if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
                //**如果等于nil，则直接进入动态方法决议,也就是没有找到**
                imp = forward_imp;
                break;
            }
        }

        if (slowpath(--attempts == 0)) {
            _objc_fatal("Memory corruption in class list.");
        }

        // Superclass cache.
        //**通过cache_getImp快速方法查找流程去查找父类的cache中是否存在该方法**
        imp = cache_getImp(curClass, sel);
        if (slowpath(imp == forward_imp)) {
            //**如果父类返回的是forward_imp，则停止继续查找，跳出**
            break;
        }
        //**父类缓存里面找到了，则直接去done**
        if (fastpath(imp)) {
            goto done;
        }
        //**这是是循环最后的地方，也就是父类的缓存中没找到方法的话，会继续循环，从头开始**
        //**因为这个时候curClass已经指向父类了，所以再次循环是查找父类的方法列表**
    }

    //**这个时候传入的behavior为LOOKUP_INITIALIZE|LOOKUP_RESOLVER**
    //**条件成立，会进入，然后重置behavior为LOOKUP_INITIALIZE**
    //**再次调用则不会进入**
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;
        //**动态方法决议流程**
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

 done:
    //**未初始化的类中在上面条件中包含了LOOKUP_NOCACHE，所以不会进入，否则会进入**
    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();
    //**动态方法决议完成后，还是没有该方法，直接返回nil**
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
    //**返回找到的imp**
    return imp;
}
复制代码

lookUpImpOrForward流程文字版

由于这个流程是要去循环遍历查找整个方法列表，整体速度相对于快速查找流程会慢很多，所以我们称之位方法的慢速查找路程，下面我们用文字来总结一下，整个慢速查找流程

首先判断类是否注册过，没有则直接报错
根据isa走位链和isa继承链去初始化当前类的，父类，元类，一直到根类和根源类初始化完毕
进入死循环
判断是否使用共享缓存，如果使用则去共享缓存中查找是否存在该方法，找到了则直接跳出循环去done
未使用共享缓存则获取当前类的方法列表methodlist，使用二分法查找法寻找其中是否有该方法，找到则跳出循环，去done
未找到则将当前类赋值为父类，并判断是否为nil，如果是空则表示没有父类直接跳出循环
通过快速方法查找去查找父类的缓存中是否有该方法
如果在父类缓存中找到方法，判断是否是动态方法决议方法，如果是则跳出，否则跳出循环去done
当查找了类的父类，一直到根类都没找到该方法，则死循环结束
如果没有进行过动态方法决议流程，系统会再给一次机会，调用动态方法决议流程
如果最终找到了方法，则将方法写入缓存，方便下次快速查找

lookUpImpOrForward流程图

慢速方法查找流程图.png

二分查找法查找方法

在上面的过程中，我们省了了一个部分，就是怎么在methodlist中去查找我们需要的方法，我们提过一下是使用的二分查找法，那么我们就来探究下，是怎么实现的

static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
    runtimeLock.assertLocked();
    ASSERT(cls->isRealized());
    //**获取当前类中的方法列表**
    auto const methods = cls->data()->methods();
    //**循环当前的方法列表，我们知道二维的，这是循环第一层**
    for (auto mlists = methods.beginLists(),
              end = methods.endLists();
         mlists != end;
         ++mlists)
    {
        //**获取到每个元素的首地址，去其中查找是否有符合条件的sel**
        method_t *m = search_method_list_inline(*mlists, sel);
        //**找到了，返回**
        if (m) return m;
    }
    return nil;
}
复制代码

很明显，这个方法是解析methodlist的第一层，核心的查找方法是search_method_list_inline，而这个方法里面嵌套了好几层，我们直接来看最核心的方法findMethodInSortedMethodList

ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)
{
    ASSERT(list);
    //**获取链表的第一个元素**
    auto first = list->begin();
    //**设置查找基准位base为first**
    auto base = first;
    //**初始化probe，类型为first的类型**
    decltype(first) probe;
    
    //**将我们要查找的sel转换成地址**
    //**由于我们的methodlist是已经排序过的，所以可以直接使用二分查找法**
    uintptr_t keyValue = (uintptr_t)key;
    uint32_t count;  
    //**count就是链表中包含节点的个数**
    //**count >> = 1实际上就等价于 count = count / 2**
    //**假设我们的count = 8**
    //**而我们我们需要查找的方法在第5个**
    //**第一次循环:count = 8,base = 0**
    //**第二次循环:执行count>>=1,count = 3,base = 5**
    //**第三次循环:执行count>>=1,count = 1,base = 5**
    for (count = list->count; count != 0; count >>= 1) {
        //**给中间值probe赋值,**
        //**第一次循环:probe = 0 + 8 >> 1 =4**
        //**第二次循环:probe = 5 + 3 >> 1 =6**
        //**第三次循环:probe = 5 + 1 >> 1 =5**
        probe = base + (count >> 1); 
        
        //**获取probe值对应的元素地址，因为已经排序过，所以可以进行比较**
        uintptr_t probeValue = (uintptr_t)getName(probe);
        //**如果两值相等，则说明probeValue就是我们要找的方法**
        //**第一次循环:5 != 8**
        //**第二次循环:5 != 6**
        //**第三次循环:5 == 5，找到**
        if (keyValue == probeValue) {
            //**分类覆盖，分类中有相同名字的方法**
            //**如果有分类的方法我们就获取分类的方法，多个分类看编译的顺序**
            while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
                probe--;
            }
            //**返回buket的地址**
            return &*probe;
        }
        
        //**如果目标key大于中间key，则基准值base = 中间值+1，总个数Count减1**
        //**第一次循环:5 > 4, base = 4+1 =5 , count = 8-- = 7**
        //**第二次循环:5 < 6, base = 5, count = 3**
        if (keyValue > probeValue) {
            base = probe + 1;
            count--;
        }
        //**再次循环**
    }
    
    return nil;
}
复制代码