第十节—objc_msgSend(二)方法慢速查找流程
本文为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
