慢速查找-汇编部分
在objc-msg-arm64.s文件中查找__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
其中的核心是_lookUpImpOrForward，上述汇编的过程，可以通过汇编调试来验证
在main中，例如[person sayHello]对象方法调用处加一个断点，并且开启汇编调试【Debug -- Debug worlflow -- 勾选Always show Disassembly】，运行程序
汇编中objc_msgSend加一个断点，执行断住，按住control + stepinto，进入objc_msgSend的汇编：
在_objc_msgSend_uncached加一个断点，执行断住，按住control + stepinto，进入汇编
慢速查找-C/C++部分
根据汇编部分的提示，全局续搜索lookUpImpOrForward，最后在objc-runtime-new.mm文件中找到了源码实现，这是一个c实现的函数
IM PlookUpImpOrForward(id inst,SEL sel,Class cls,int behavior)
{
const IMP forward_imp = (IMP)_objc_msgForward_impcache;
IMP imp =nil;
ClasscurClass;
runtimeLock.assertUnlocked();
// Optimistic cache lookup
if(fastpath(behavior &LOOKUP_CACHE)) {
imp =cache_getImp(cls, sel);
if(imp)gotodone_nolock;
}
// runtimeLock is held during isRealized and isInitialized checking
// to prevent races against concurrent realization.
// runtimeLock is held during method search to make
// method-lookup + cache-fill atomic with respect to method addition.
// Otherwise, a category could be added but ignored indefinitely because
// the cache was re-filled with the old value after the cache flush on
// behalf of the category.
runtimeLock.lock();
// We don't want people to be able to craft a binary blob that looks like
// a class but really isn't one and do a CFI attack.
//
// To make these harder we want to make sure this is a class that was
// either built into the binary or legitimately registered through
// objc_duplicateClass, objc_initializeClassPair or objc_allocateClassPair.
//
// TODO: this check is quite costly during process startup.
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 may have been dropped but is now locked again
// If sel == initialize, class_initialize will send +initialize and
// then the messenger will send +initialize again after this
// procedure finishes. Of course, if this is not being called
// from the messenger then it won't happen. 2778172
}
runtimeLock.assertLocked();
curClass = cls;
// The code used to lookpu the class's cache again right after
// we take the lock but for the vast majority of the cases
// evidence shows this is a miss most of the time, hence a time loss.
//
// The only codepath calling into this without having performed some
// kind of cache lookup is class_getInstanceMethod().
for(unsignedattempts =unreasonableClassCount();;) {
// curClass method list.
Methodmeth =getMethodNoSuper_nolock(curClass, sel);
if(meth) {
imp = meth->imp;
gotodone;
}
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.
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.
gotodone;
}
}
// No implementation found. Try method resolver once.
if(slowpath(behavior &LOOKUP_RESOLVER)) {
behavior ^=LOOKUP_RESOLVER;
returnresolveMethod_locked(inst, sel, cls, behavior);
}
done:
log_and_fill_cache(cls, imp, sel, inst, curClass);
runtimeLock.unlock();
done_nolock:
if(slowpath((behavior &LOOKUP_NIL) && imp == forward_imp)) {
returnnil;
}
returnimp;
}
其整体的慢速查找流程如图所示：
主要有以下几步：
1.cache缓存中进行查找，即快速查找，找到则直接返回imp，反之，则进入第2步
2.判断cls是否是已知类，如果不是，则报错；类是否实现，如果没有，则需要先实现，确定其父类链，此时实例化的目的是为了确定父类链，方法后续的循环，是否初始化，如果没有，则初始化
3.for循环，按照类继承链 或者 元类继承链的顺序查找
当前cls的方法列表中使用二分查找算法查找方法，如果找到，则进入cache写入流程并返回imp，如果没有找到，则返回nil当前cls被赋值为父类，如果父类等于nil，则imp = 消息转发，并终止递归，进入第4步
如果父类链中存在循环，则报错，终止循环
父类缓存中查找方法
如果未找到，则直接返回nil，继续循环查找
如果找到，则直接返回imp，执行cache写入流程
4.判断是否执行过动态方法解析
，如果没有，执行动态方法解析
如果执行过一次动态方法解析，则走到消息转发流程
getMethodNoSuper_nolock方法：二分查找方法列表
查找方法列表的流程如下所示：
其二分查找核心的源码实现如下：
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; //key 等于 say666
uint32_t count;
//base相当于low，count是max，probe是middle，这就是二分
for (count = list->count; count != 0; count >>= 1) {
//从首地址+下标 --> 移动到中间位置（count >> 1 左移1位即 count/2 = 4）
probe = base + (count >> 1);
uintptr_t probeValue = (uintptr_t)probe->name;
//如果查找的key的keyvalue等于中间位置（probe）的probeValue，则直接返回中间位置
if (keyValue == probeValue) {
// -- while 平移 -- 排除分类重名方法
while (probe > first && keyValue == (uintptr_t)probe[-1].name) {
//排除分类重名方法（方法的存储是先存储类方法，在存储分类---按照先进后出的原则，分类方法最先出，而我们要取的类方法，所以需要先排除分类方法）
//如果是两个分类，就看谁先进行加载
probe--;
}
return (method_t *)probe;
}
//如果keyValue 大于 probeValue，就往probe即中间位置的右边查找
if (keyValue > probeValue) {
base = probe + 1;
count--;
}
}
return nil;
}
算法原理简述为：从第一次查找开始，每次都取中间位置，与想查找的key的value值作比较，如果相等，则需要排除分类方法，然后将查询到的位置的方法实现返回，如果不相等，则需要继续二分查找，如果循环至count = 0还是没有找到，则直接返回nil，如下所示：
以查找LGPerson类的say666实例方法为例，其二分查找过程如下
cache_getImp方法：父类缓存查找
cache_getImp方法是通过汇编_cache_getImp实现，传入的$0 是 GETIMP，如下所示：
如果父类缓存中找到了方法实现，则跳转至CacheHit即命中，则直接返回imp
如果在父类缓存中，没有找到方法实现，则跳转至CheckMiss或者JumpMiss，通过判断$0跳转至LGetImpMiss，直接返回nil
总结
对于对象方法（即实例方法），即在类中查找，其慢速查找的父类链是：类--父类--根类--nil
对于类方法，即在元类中查找，其慢速查找的父类链是：元类--根元类--根类--nil
