我们在 C底层原理11-objc_msgSend源码分析(方法查找快流程) 一文中，探索了objc_msgSend方法快速查找流程（从缓存中获取方法），cache类型的源码在OC底层全部用汇编实现，优点是快，我们发现如果CacheLookup流程找不到的话，就会进入CheckMiss -> __objc_msgSend_uncached -> MethodTableLookup -> lookUpImpOrForward流程，lookUpImpOrForward也就是我们今天要研究的慢速查找流程，它的源码在objc层中，用OC实现

一、准备工作

1.1、objc4可编译源码，可直接跳到文章最后，下载调试好的源码

1.2、在源码中新增类GomuPerson如下

GomuPerson.h
- (void)sayNO;

GomuPerson.m
//不实现方法，方便后面二分法研究

二、lookUpImpOrForward源码探索

2.1 lookUpImpOrForward方法源码

IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
//: -- 创建一个默认forward_imp，并赋值_objc_msgForward_impcache
    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
//: -- 创建一个imp，值为nil
    IMP imp = nil;
//: -- 创建一个类curClass
    Class curClass;

    runtimeLock.assertUnlocked();

//: -- 因为是多线程，并且后面要开始耗时操作了，防止获取的时候正在cache的情况没取到，所以再取一次cache
//: -- 如果在当前cls的cache没有找到imp，则继续执行
//: -- 如果找到了，则跳转到done_nolock
    if (fastpath(behavior & LOOKUP_CACHE)) {
//: -- 从cls的缓存中取imp
        imp = cache_getImp(cls, sel);
        if (imp) goto done_nolock;
    }
    runtimeLock.lock();

//: -- 判断当前cls是否为已知类
//: -- 防止人为制造类，进行CFI攻击
    checkIsKnownClass(cls);

//: -- 如果类没有实现，则去实现，并对其继承链进行实现关联
//: -- 类是双向链表，所以需要双向绑定
//: -- cls->superclass = supercls 给cls的父类赋值supercls
//: -- addSubClass(supercls, cls) 给supercls添加subClass
//: -- 猜想，是分类走的流程
    if (slowpath(!cls->isRealized())) {
        cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
    }
//: -- 递归实现类/元类继承链的initialize方法
    if (slowpath((behavior & LOOKUP_INITIALIZE) && !cls->isInitialized())) {
        cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
    }

    runtimeLock.assertLocked();

//: -- 把cls赋值给curClass
    curClass = cls;

//: -- 开始for循环，递归查找
//: -- 自己的methods -> 父类的cache -> 父类的methods -> 直到nil
    for (unsigned attempts = unreasonableClassCount();;) {
//: -- 首先从自己的methods里面查找，这里牵涉到一个优化算法，我们后面单独聊
        Method meth = getMethodNoSuper_nolock(curClass, sel);
        if (meth) {
//: -- 如果找到了meth，则拿到imp，返回
            imp = meth->imp;
            goto done;
        }

//: -- 把curClass的父类赋值给curClass，然后判断是否为nil
//: -- NSObject的父类为nil，当遍历到nil的时候就默认给imp赋值forward_imp，跳出循环
//: -- 如果不为nil，继续往下走
        if (slowpath((curClass = curClass->superclass) == nil)) {
            // No implementation found, and method resolver didn't help.
            // Use forwarding.
            imp = forward_imp;
            break;
        }

//: -- 防止死循环，给一个出口
        if (slowpath(--attempts == 0)) {
            _objc_fatal("Memory corruption in class list.");
        }

//: -- curClass已经被赋值为它的父类，所以这里从父类的缓存里面找imp
        imp = cache_getImp(curClass, sel);

//: -- 当curClass的父类为nil的时候，imp会被赋值forward_imp，就会走这里，跳出循环
        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;
        }

//: -- 如果找到imp，则跳转到done
//: -- 找自己的时候不会走这里，父类中存在imp才走这里
        if (fastpath(imp)) {
            // Found the method in a superclass. Cache it in this class.
            goto done;
        }
    }

    // No implementation found. Try method resolver once.
//: -- 如果遍历完了父类都没有找到imp，则进行消息处理机制，动态方法决议，这个后面我们会单独开一期来进行讲解
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
//: -- 这个算法超级牛 只走一次
//: -- behavior不管是什么，假设是3，0011
//: -- LOOKUP_RESOLVER = 2，0010
//: -- 第一次 0011 & 0010 = 0010 为真
//: -- 进入判断中 behavior = 0011 ^ 0010 = 0001
//: -- 第二次进入 0001 & 0010 = 0000
//: -- 第一次求&，behavior第二位必须为1，才能进入条件，进入之后，求 ^ ，第二位就会变成0，那下次再进入的时候，再求&必然为0，不再进判断
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

 done:
//: -- 把找到的imp存进缓存，方便下次快速查找
    log_and_fill_cache(cls, imp, sel, inst, curClass);
    runtimeLock.unlock();
 done_nolock:
//: -- 判断imp是否被赋值了forward_imp，如果是则返回nil
//: -- 防止多线程操作imp没找到，被赋值为forward_imp时，成功返回了错误的imp
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
//: -- 如果在开始慢查询之前，从缓存中找到了则直接返回当前的imp
    return imp;
}

• 得出以下流程：
  自己的cache -> 自己的methods -> 父亲的cache -> 父亲的methods -> 父亲的父亲的cache -> 父亲的父亲的methods -> nil -> resolveMethod_locked（动态方法决议）

• 附流程图

  
  lookUpImpOrForward流程图.png

2.2 getMethodNoSuper_nolock方法源码

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

    ASSERT(cls->isRealized());
//: -- 拿到cls的data()里面存的methods()
    auto const methods = cls->data()->methods();
//: -- 循环（目的不清楚）,断点调试的时候要走很多次，加载很多系统的方法列表
    for (auto mlists = methods.beginLists(),
              end = methods.endLists();
         mlists != end;
         ++mlists)
    {
//: -- 从方法列表中找当前sel
//: -- 类中自定义的方法第一次循环的时候走这里，存在methods.beginLists()
         method_t *m = search_method_list_inline(*mlists, sel);
        if (m) return m;
    }
    return nil;
}

• 进入search_method_list_inline后会调用findMethodInSortedMethodList

2.3 findMethodInSortedMethodList源码

ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
    ASSERT(list);
//: -- 把第list一个元素赋值给first
    const method_t * const first = &list->first;

//: -- 把fistr赋值给base
    const method_t *base = first;
    const method_t *probe;

//: -- 把当前传入的sel转成uintptr_t类型，并赋值给keyValue
    uintptr_t keyValue = (uintptr_t)key;
    uint32_t count;

//: -- 二分法查找sel，向前查找
    for (count = list->count; count != 0; count >>= 1) {
//: -- 指针平移，相当于地址平移到中间位置，count >> 1相当于count/2
        probe = base + (count >> 1);
//: -- 拿到当前probe中的name，这里对应sel        
        uintptr_t probeValue = (uintptr_t)probe->name;
//: -- 判断当前keyValue是否等于probeValue
        if (keyValue == probeValue) {
//: -- 判断是否有分类方法
            while (probe > first && keyValue == (uintptr_t)probe[-1].name) {
//: -- 如果有分类方法，并且keyValue不是第一个元素
//: -- 如果类和分类都有同一个方法，则会走这里
//: -- 取当前类前面一位，即分类方法，分类方法后加如methods，优先读取
                probe--;
            }
//: -- 返回当前找到的method_t
            return (method_t *)probe;
        }
//: --  查keyValue比二分位大的时候需要走这里
        if (keyValue > probeValue) {
//: -- 如果目标在二分位右边，则讲当前base右移一位
            base = probe + 1;
//: -- count自减
            count--;
        }
    }
        return nil;
}

2.3.1 对象方法和属性调用前在methods中的储存顺序：

1. 先存对象方法，按照对象方法在.m中的实现顺序依次存储
2. 属性按照属性在.h/.m中的声明顺序逆序存储，先get，再set

如下图：(.h中改成.m实现，画错了)

对象方法和属性调用前在methods中的储存顺序图.png

2.3.2 对象方法调用之后在methods中的储存顺序：

1. 判断当前类的类别中是否有该对象方法，有就先存储类别中的对象方法，再存储类中的对象方法（如果类中有，类中可能没有，只有.m实现也会存储），如果没有，则直接存当前类中的对象方法
2. 先调用的存储在前面，后调用的存储在上一个方法的后面(即相对最前面)，最先调用的存在最前面
3. 没有调用的按照以前的顺序排在后面

如下图：

对象方法调用之后在methods中的储存顺序

2.3.3 findMethodInSortedMethodList中，二分法算法介绍

• 查询目标一直小于遍历中位数，流程图如下

  
  image.png

• 查询目标大于遍历中位数，流程图如下

  
  image.png

三、拓展知识

3.1 交替进入的if的位运算

//: -- LOOKUP_RESOLVER = 2
//: -- 省略外层for循环
if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

• 把LOOKUP_RESOLVER换成2进制0010
• behavior分2种情况，一种是第二位为1，第二种是第二位不为1，分别用1111，1101举例
• 随着behavior的累加，当第二位为1的时候就能进，第二位为0的时候就不能进（为1不进，为2进，为3不进，为4进...）

第一种情况

1. 第一种`behavior`为1111，`behavior & LOOKUP_RESOLVER`=`1111 & 0010`，为真，进入`if`
2. 进入后`behavior ^= LOOKUP_RESOLVER`，`behavior ` = `1111 ^ 0010` = `1101`
3. 下次循环过来，`behavior & LOOKUP_RESOLVER` = `1101 & 0010`，为假，不再进入循环

得出结论：第二位为1，必然可以进入循环一次，进入后与0010异或之后，第二位变0，下次与0010求与的时候，必定为假，这样就保证了if只走一次

第二种情况

第二种`behavior`为1101，`behavior & LOOKUP_RESOLVER`=`1101 & 0010`，为假，不能进入`if`

得出结论：第二位为0，连if都进不去

3.2 方法调用的本质，就是找imp，没有实现就找不到imp，和方法声明没关系

• 类中声明并实现了方法，类别中未声明且未实现，则调用类中的方法

• 类中声明并实现了方法，类别中声明但未实现，则调用类中的方法

• 类中声明并实现了方法，类别中未声明但实现，则调用类别中的方法

• 类中声明并实现了方法，类别中声明且实现，则调用类别中的方法

• 类中声明未实现 方法，类别中未声明但实现，则调用类别中的方法

• 类中未声明但实现 方法，类别中声明但未实现，则调用类中的方法

总结：

• 类和类别中有一个实现，则谁实现就调用谁的
• 类和类别中都实现，则优先调用类别的
• 类和类别如果都没有声明，则不能直接通过[p sayNO]方式调用，可以通过performSelector，objc_msgSend调用，即方法声明不是必须的

objc_msgSend(p, sel_registerName("sayNO"));
[p performSelector:@selector(sayNO)];