本文为L_Ares个人写作，以任何形式转载请表明原文出处。

在第九节—objc_msgSend消息快速转发的流程中，我们发现了当我们递归取到cache_t中的bucket的sel和objc_msgSend入参的id SEL不一致的时候，CacheLookUp会跳转到函数CheckMiss并传入$0存储的CacheLookUp的requirements。

上一节不说是因为CheckMiss在汇编中的代码如下 :

.macro CheckMiss
    // miss if bucket->sel == 0
.if $0 == GETIMP
    cbz p9, LGetImpMiss
.elseif $0 == NORMAL
    cbz p9, __objc_msgSend_uncached
.elseif $0 == LOOKUP
    cbz p9, __objc_msgLookup_uncached
.else
.abort oops
.endif
.endmacro

上节说过了，一般情况下，CacheLookUp的requirements都是Normal，是正常的查找流程，所以这里会走到__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 p16 is the class to search
    
    MethodTableLookup    //这里就是__objc_msgSend_uncached调用的方法
    TailCallFunctionPointer x17

    END_ENTRY __objc_msgSend_uncached

官方有很明显的注释，这是一个不可以在汇编里面调用的C方法，p16寄存器中是要搜索的类。

那么再看MethodTableLookup

图1.png

这里我就截图到这个位置，因为下面也没有bl跳转到方法的地方了，也就是说，这里我们最能理解的就是这个_lookUpImpOrForward。

上面的那些操作都是把参数存进寄存器，因为这里就要跳转到C里面了，汇编可以有未知参数的存在，动态的去进行操作。但是C不行啊，C是静态的，所以把这些需要的参数都先搞定，再进入C。

这里就要说一个关于C/C++和汇编的互相调用中，有一个规定 :

• 在C/C++中调用汇编的时候，想要在汇编中查找这个汇编方法，要在调用的汇编方法前面添加一个下划线_，例如，C/C++中调用汇编方法，方法名为A，那么你在汇编中找A就要找_A。
• 与其相反的，在汇编中调用C/C++的方法，那么方法名前面的下划线_就要去掉一个。

那么，我们现在要找的方法就变成了lookUpImpOrForward，这个也就是真正的CheckMiss和JumpMiss的核心所在。

一、lookUpImpOrForward主线流程

还是使用objc4-781源码

全局搜索lookUpImpOrForward，别的都不用管，我们这里已经是探索Rutime了，所以直接找带Runtime的文件中的lookUpImpOrForward。

图2.png

来看lookUpImpOrForward的主线思路。

这里我会开始分步骤，代码的流程是正常的贴，我会按照步骤来解释，主线上的分线会在下面的模块说。

1. 检查

/**
 标准的IMP查找
     (1)大多数调用者应该使用LOOKUP_INITIALIZE和LOOKUP_CACHE
     (2)返回_objc_msgForward_impcache类型的变量。
     (3)外部使用的imp必须转换为_objc_msgForward或_objc_msgForward_stret。
     (4)如果不想转发，使用LOOKUP_NIL
 */
/**
 @param inst 是一个类的实例或者子类，如果都不是的话，那inst就是nil。
 @param cls 如果cls是一个未初始化的元类，那么一个非空的inst会更快
 */
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    //定义一个返回值(消息的转发)
    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    //置空一个imp
    IMP imp = nil;
    Class curClass;

    //提醒一下没有上锁
    runtimeLock.assertUnlocked();

    //再主动的进行一次快速查找，也就是缓存查找
    //这样可以防止多线程的时候，其他线程调用了方法，方法被存入了cache，就可以找到了
    //找到了就直接返回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.assertLocked();
    //把已经确认过是已知的，而且已经实现的，也初始化过的类，给到我们上面定义过的Class变量
    curClass = cls;

第一步骤非常的明显，都是检查、准备工作。

(1). 先走了一遍快速查找的流程，检查是否因为多线程的原因，在查找的中途，有其他的线程向缓存中插入了方法的实现。如果有，那么下面的就都不走了，通过cls和sel找到对应的类的方法实现imp，直接返回imp。

(2). 加锁操作。检查类的合法性，包括类是否是已知的，类是否有实现，类是否有初始化。缺少的步骤会被补齐，这个过程会对锁有开锁的操作。

(3). 加锁操作，将合法的类赋值给定义的Class对象。

第一步如果都走到这里了，那么就确定当前类cls中真的没有当前方法的缓存了。于是我们可以进入第二步。

2. 沿继承链顺序查找

    //unreasonableClassCount : 类的继承链上限，就是类的继承链往上数还有多少个父辈
    //循环沿链查找
    for (unsigned attempts = unreasonableClassCount();;) {
        
        //通过二分法查找算法获取当前类的方法列表
        //这里会有一步缓存的写入，和cache_insert一样。
        Method meth = getMethodNoSuper_nolock(curClass, sel);

        //如果在当前类的方法列表中找到了imp
        if (meth) {
            //获取到imp，然后去done
            imp = meth->imp;
            goto done;
        }

        //将父类赋值给curClass，并且判断父类是否为空
        if (slowpath((curClass = curClass->superclass) == nil)) {
            //如果父类为空那就证明已经找到NSObjcet这层继承都没找到imp，那肯定找不到imp了，那么就使用转发，imp就存储转发
            imp = forward_imp;
            //即然找到头了，那么就退出递归
            break;
        }

        //如果在父类中一直循环，则停止，并提示类列表中的内存存在损坏
        if (slowpath(--attempts == 0)) {
            _objc_fatal("Memory corruption in class list.");
        }

        //获取父类缓存
        imp = cache_getImp(curClass, sel);
        if (slowpath(imp == forward_imp)) {
            //如果在父类中找到了一个forward转发，那么停止查找，并且不缓存，先调用该类的resolver。
            break;
        }

        //如果在父类中找到了该方法的实现，那么就把它放到缓存中
        if (fastpath(imp)) {
            // Found the method in a superclass. Cache it in this class.
            goto done;
        }
    }

第二步骤就开始进入了沿着继承链一路向上，查找方法是否有在继承链上的类中存在。

(1). 获取继承链的上限，继承链是一定有上限的，大不了最后指向nil。

(2). 获取你传入的类的方法列表。检查你的方法列表是否存在这个方法。

• 如果找到直接就走到done里面记录并且填充缓存。

• 如果imp为nil，即证明当前类没有这个方法的实现。

(3). 把传入的cls的父类赋值给cls，那么cls现在就是它的父类了。

• 如果父类已经是nil了，则证明已经找到NSObject这一层了，还是没有imp，那么就要消息转发，于是把imp赋值消息转发，并且跳出循环。

• 如果父类还不是nil，证明还有父类的方法没有找完，继续下面的步骤(5)(6)。

(4). 检查父类中是否一直在循环，如果父类一直都在循环，那就是类的列表中的内存存在损坏，就会报错并且退出循环。

(5). 获取父类的缓存，找到父类缓存中的sel对应的imp。

(6). 看这个imp是不是消息转发。

• 如果imp不是消息转发，而且是存在的，那么直接进入done，进行cache_insert，存储到缓存中。

• 如果imp是消息转发，那么就停止循环，不缓存，直接先使用这个消息转发。

3. 动态决议

     //没有找到方法的实现，尝试一次使用动态方法解析
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        
        //动态方法决议的控制条件，表示流程只走一次
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

• 到了这里证明cls的sel在整条继承链上都找不到。

• 尝试一次动态方法解析。

二、lookUpImpOrForward分路方法

上面从1～3就是lookUpImpOrForward的主线流程思想。其中还有不少的支线，我们来看一下。按顺序的看。

1. getMethodNoSuper_nolock

上面说过了，我们是通过这个方法获得的cls的方法列表，点进去看它的实现。

static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
    //检查是否加锁
    runtimeLock.assertLocked();

    //检查类是否合法
    ASSERT(cls->isRealized());
    // fixme nil cls? 
    // fixme nil sel?

    //类的bits调用data()获取到了方法列表
    auto const methods = cls->data()->methods();
    
    //循环取得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;
    }

    return nil;
}

所以getMethodNoSuper_nolock可以获得类的方法主要是通过了search_method_list_inline函数，那就继续进去看。

2. search_method_list_inline

图3.png

整个函数不管那么多，就看return了什么，除了nil就只有着一个函数，根据函数名也能知道，红框里面的函数findMethodInSortedMethodList是从有序的方法列表中找到方法。所以接着进入看。

3. findMethodInSortedMethodList

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

    //取列表的首地址上的元素，也就是第一个元素，给到first变量
    const method_t * const first = &list->first;
    
    //base是为了下面进入for循环来使用。base方法列表中的第一个元素
    const method_t *base = first;
    
    //先定义着，一会用。
    const method_t *probe;
    
    //keyValue就是我们的方法名sel
    uintptr_t keyValue = (uintptr_t)key;
    
    //方法列表中方法的数量
    uint32_t count;
    
    //从列表的底部开始，只要没有到达第一个方法，count就右移一位(也就是缩小一半取整)
    for (count = list->count; count != 0; count >>= 1) {
        
        //count >> 1就是count / 2
        //base是方法列表的首地址
        //所以probe = 方法列表首地址 + 方法列表数量的一半的下标，也就是方法列表的中间的那个方法吧
        probe = base + (count >> 1);
        
        //取得方法列表中间值的方法的名字
        uintptr_t probeValue = (uintptr_t)probe->name;
        
        //如果sel = name
        if (keyValue == probeValue) {
            // `probe` is a match.
            // Rewind looking for the *first* occurrence of this value.
            // This is required for correct category overrides.
            //倒序查找(就是向上找)这个sel第一次出现在哪里。
            while (probe > first && keyValue == (uintptr_t)probe[-1].name) {
                probe--;
            }
            //找到方法
            return (method_t *)probe;
        }
        
        //如果sel的位置在中间方法的后面
        if (keyValue > probeValue) {
            //首地址就换成中间方法的后面一个方法的地址。
            base = probe + 1;
            //count自减1，就是list最后一个元素的索引
            count--;
        }
    }
    
    return nil;
}

这个就是二分法的算法。仔细看一下注释，再自己算一下，就知道了。

4. cache_getImp

图4.png

看图，跳进来就发现是一个汇编，上面说过了吧，怎么从C找汇编，就是在cache_getImp的前面加上_变成_cache_getImp，然后去全局找_cache_getImp，找到arm64架构下的s文件，再找到带有ENTRY的_cache_getImp，就是它的入口了吧。

找到以后的结果 :

图5.png

和上一节不同的地方是不是requirements从Normal变成了GETIMP。

也是缓存查找流程吧。就是变成了

• 从父类的缓存中找方法实现，如果找到了那么CacheHit，命中缓存，返回imp

• 父类中没有找到方法实现，就跳到CheckMiss或者JumpMiss，再根据$0=GETIMP，跳转到LGetImpMiss，结果就是返回nil。

图6.png 图7.png

三、总结

所谓慢速查找流程，就是从缓存中的查找变成了从类的结构中查找。还记得类的结构吗？

isa,superClass,class_data_bits_t bits,cache_t cache

方法是存储在class_data_bits_t调用方法data()获得的class_rw_t在编译期间复制出来的class_ro_t中的method_list_t类型的baseMethodList中的。

慢速查找就是从baseMethodList中去找，找不到就向上找父类。一直找到nil都没有的话，就动态决议，还没有的话，那就只能消息转发了。

总结一下 :

• 对于实例方法 查找imp方法实现的路径 : 类 ---> 父类 ---> 根类 ---> nil

• 对于类方法查找imp方法实现的路径 : 元类 ---> 根元类 ---> 根类 ---> nil

• 慢速查找都没有找到imp方法实现，那么就尝试一次动态协议。

• 动态协议没有找到，那么就消息转发。

对于还是不清楚的，可以看一下那张神图，我贴出来，不要去看类的继承关系，就看isa的，就是虚线的。

为什么就看isa的？因为一切查找的源头都是从isa开始的。

图8.png