慢速查找汇编分析
在上篇文章iOS底层 - objc_msgSend快速查找流程分析中我们分析了通过汇编进行的objc_msgSend快速查找流程：CacheLookup 汇编方法在cache缓存中没找到，CheckMiss 和 JumpMiss 都会跳到__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
TailCallFunctionPointer x17
END_ENTRY __objc_msgSend_uncached
此方法中最重要的就是MethodTableLookup查找方法列表函数。
.macro MethodTableLookup
// push frame
SignLR
stp fp, lr, [sp, #-16]!
mov fp, sp
// save parameter registers: x0..x8, q0..q7
sub sp, sp, #(10*8 + 8*16)
stp q0, q1, [sp, #(0*16)]
stp q2, q3, [sp, #(2*16)]
stp q4, q5, [sp, #(4*16)]
stp q6, q7, [sp, #(6*16)]
stp x0, x1, [sp, #(8*16+0*8)]
stp x2, x3, [sp, #(8*16+2*8)]
stp x4, x5, [sp, #(8*16+4*8)]
stp x6, x7, [sp, #(8*16+6*8)]
str x8, [sp, #(8*16+8*8)]
// 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 registers and return
ldp q0, q1, [sp, #(0*16)]
ldp q2, q3, [sp, #(2*16)]
ldp q4, q5, [sp, #(4*16)]
ldp q6, q7, [sp, #(6*16)]
ldp x0, x1, [sp, #(8*16+0*8)]
ldp x2, x3, [sp, #(8*16+2*8)]
ldp x4, x5, [sp, #(8*16+4*8)]
ldp x6, x7, [sp, #(8*16+6*8)]
ldr x8, [sp, #(8*16+8*8)]
mov sp, fp
ldp fp, lr, [sp], #16
AuthenticateLR
.endmacro
在MethodTableLookup中经过一系列准备工作，将会跳转到_lookUpImpOrForward方法，全局查找_lookUpImpOrForward方法，但未找到，那么我们猜想一下是否_lookUpImpOrForward方法就不在汇编中，而是在C/C++中？
验证
创建继承自NSObject的类LGPerson，并添加方法sayHello，main.m文件中创建实例并调用方法：
int main(int argc, const char * argv[]) {
@autoreleasepool {
// insert code here...
LGPerson *person = [LGPerson alloc];
1 [person sayHello];
}
return 0;
}
在调用sayHello方法处打下断点，打开Debug--->Debug Workflow --->Always show Disassembly，程序来到底层汇编中：
方法调用汇编查看
在图中16行
objc_msgSend方法处打下断点，继续下一步，程序停住，按下control + step into ,进入到objc_msgSend 汇编方法中：
objc_msgSend方法汇编
发现此时
objc_msgSend方法最后也跳转到了_objc_msgSend_uncached 中，对我们上面的汇编代码在cache中没找到跳转到_objc_msgSend_uncached方法一样。接着打下断点，继续让程序进入
_objc_msgSend_uncached 方法汇编中：
_objc_msgSend_uncached汇编代码
我们看到代码最终会跳到方法
lookUpImpOrForward中，在C++文件 objc-runtime-new.mm:6099 处。
慢速查找C/C++分析
全局搜索lookUpImpOrForward ，找到objc-runtime-new.mm 文件中对应的C代码：
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();
// Optimistic cache lookup
// 考虑多线程过程影响，如果别的线程缓存了，那么直接利用cache_getImp汇编方法快速查找，CacheLookup GETIMP, _cache_getImp
// 找到了就直接返回imp， 没找到继续步骤
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);
}
// 是否类已经初始化过了，进行初始化
if (slowpath((behavior & LOOKUP_INITIALIZE) && !cls->isInitialized())) {
cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
}
runtimeLock.assertLocked();
curClass = cls;
// 无限循环方法 当imp = forward_imp时 break 退出循环
for (unsigned attempts = unreasonableClassCount();;) {
// curClass method list.
// 最终使用二分法 查找当前 curClass 类中是否有对应的imp
Method meth = getMethodNoSuper_nolock(curClass, sel);
if (meth) {
imp = meth->imp;
goto done;
}
// 当前类方法列表没找到，将当前类变为当前类的父类，如果父类为nil，则imp赋值forward_imp退出此for循环
if (slowpath((curClass = curClass->superclass) == nil)) {
// No implementation found, and method resolver didn't help.
// Use forwarding.
imp = forward_imp;
break;
}
// Halt if there is a cycle in the superclass chain.
if (slowpath(--attempts == 0)) {
_objc_fatal("Memory corruption in class list.");
}
// Superclass cache.
// 优先通过cache_getImp 汇编查找父类缓存，如果找到直接下面的go done
// 如果没有找到，那么下一个循环，找父类的方法列表，然后父类的父类的缓存，方法列表，直到最后父类为nil 退出循环。
imp = cache_getImp(curClass, sel);
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;
}
if (fastpath(imp)) {
// Found the method in a superclass. Cache it in this class.
goto done;
}
}
// No implementation found. Try method resolver once.
// 到这里 说明没找到方法，最后 给一次方法解析机会
if (slowpath(behavior & LOOKUP_RESOLVER)) {
//动态方法决议的控制条件，表示流程只走一次
behavior ^= LOOKUP_RESOLVER;
return resolveMethod_locked(inst, sel, cls, behavior);
}
done:
// 将找到的sel/imp信息缓存进cache
log_and_fill_cache(cls, imp, sel, inst, curClass);
runtimeLock.unlock();
done_nolock:
if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
return nil;
}
return imp;
}
其中，getMethodNoSuper_nolock 查找当前类中是否有sel所对应的Method（method_t结构体），
getMethodNoSuper_nolock ---> search_method_list_inline ---> findMethodInSortedMethodList：
ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
ASSERT(list);
const method_t * const first = &list->first;
const method_t *base = first;
const method_t *probe;
uintptr_t keyValue = (uintptr_t)key;
uint32_t count;
/** 举例讲解二分法 方（法列表从前往后 ，从大到小的顺序排列）
// 0x01 0x02 0x03 0x04 0x05 0x05 0x06 0x07 0x08
// keyValue = 0x02
// base = 0x01
// probe = 0x05 --> 0x03 --> 0x02
// 1 count 8 >> 1 = 4
// 2 count 4 >> 1 = 2
// 3 count 2 >> 1 = 1 此时probe = 0x02 即找到了
// keyValue = 0x07
// base = 0x01 --> 0x06
// probe = 0x05 --> 0x07
// 1 count 8 >> 1 = 4
// 2 count 7 >> 1 = 3 此时probe = 0x07 即找到了
*/
for (count = list->count; count != 0; count >>= 1) {
probe = base + (count >> 1);
uintptr_t probeValue = (uintptr_t)probe->name;
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)probe[-1].name) {
probe--;
}
return (method_t *)probe;
}
if (keyValue > probeValue) {
base = probe + 1;
count--;
}
}
return nil;
}
cache_getImp 方法解析
objc_msg_arm64.s 文件中cache_getimp 汇编代码如下：
STATIC_ENTRY _cache_getImp
GetClassFromIsa_p16 p0
// 所带的$0 与 objc_msgSend （NORMAL） 不一样
CacheLookup GETIMP, _cache_getImp
LGetImpMiss:
mov p0, #0
ret
END_ENTRY _cache_getImp
发现汇编走的方法也是CacheLookup 方法 ，快速方法查找父类的缓存里是否有此方法的缓存。
总结
- 所有
实例方法的实现查找路径为：类-->父类-->NSObject-->nil - 所有
类方法的实现查找路径为：元类-->根元类-->NSObject-->nil - 如果在上方两条方法寻找链中都
未找到，则会尝试动态方法决议，最后给一次机会。 - 如果动态方法决议
失败，那么会触发消息转发，寻找实现了此方法的别的类。
