前言
上一篇讲解了objc_msgSend调用流程并在缓存中找到对应方法。今天我们来详解在缓存中找不到对应方法的情况。
回到objc_msgSend源码中调用cacheLookup方法的地方：
LGetIsaDone:
// calls imp or objc_msgSend_uncached
CacheLookup NORMAL, _objc_msgSend, __objc_msgSend_uncached
cacheLookup定义：
.macro CacheLookup Mode, Function, MissLabelDynamic, MissLabelConstant
当找不到缓存中方法的时候执行：
3: cbz p9, \MissLabelDynamic // if (sel == 0) goto Miss;
cmp p13, p10 // } while (bucket >= buckets)
b.hs 1b
对应cacheLookup的调用及传参，可知当找不到缓存方法时会调用_objc_msgSend_uncached，这个方法其实之前在查看方法堆栈信息时已经见到过了：
接下来，来看看
_objc_msgSend_uncached到底做了什么。
_objc_msgSend_uncached源码解析
本篇依然使用objc_msg_arm64.s来分析_objc_msgSend_uncached源码：
STATIC_ENTRY __objc_msgSend_uncached
UNWIND __objc_msgSend_uncached, FrameWithNoSaves
// THIS IS NOT A CALLABLE C FUNCTION
// Out-of-band p15 is the class to search
MethodTableLookup
TailCallFunctionPointer x17
END_ENTRY __objc_msgSend_uncached
方法很简洁，核心方法就在MethodTableLookup和TailCallFunctionPointer x17，其中：
.macro TailCallFunctionPointer
// $0 = function pointer value
br $0
.endmacro
TailCallFunctionPointer其实就是返回x17，所以_objc_msgSend_uncached的真正核心就在于MethodTableLookup:
.macro MethodTableLookup
SAVE_REGS MSGSEND
// 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_REGS MSGSEND
.endmacro
可看到值得关注的核心方法就是_lookUpImpOrForward，继续找他的源码，发现汇编里没有，终于回到了runtime-new.mm。方法代码很长，但包含了著名的慢速查找过程
慢速查找
在lookUpImpOrForward源码中，我们需要关注的重点在于如何找到imp的，首先关注核心代码：
for (unsigned attempts = unreasonableClassCount();;) {
if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
#if CONFIG_USE_PREOPT_CACHES
imp = cache_getImp(curClass, sel);
if (imp) goto done_unlock;
curClass = curClass->cache.preoptFallbackClass();
#endif
} else {
// curClass method list.
Method meth = getMethodNoSuper_nolock(curClass, sel);
if (meth) {
imp = meth->imp(false);
goto done;
}
if (slowpath((curClass = curClass->getSuperclass()) == 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.
goto done;
}
}
注意到这是一个没有终止条件和变量的死循环，跳出循环的地方就是我们要重点看的地方break和goto。我们逐句分析所谓慢速查找到底是怎么做的：
if (curClass->cache.isConstantOptimizedCache(/* strict */true))
第一个if条件很有意思，是再去cache中找了一遍是否含有对应方法的imp，可以视为一种预防处理，比如有些方法插入出现了延时，在进入慢速查找之前还没插入完成，所以在正式进入慢速查找之前再检查确认一遍，避免出现不必要的慢速查找，提升效率。缓存中查找方法我们就不再赘述了，直接看else中的逻辑Method meth = getMethodNoSuper_nolock(curClass, sel);，其中getMethodNoSuper_nolock是：
static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
runtimeLock.assertLocked();
ASSERT(cls->isRealized());
// fixme nil cls?
// fixme nil sel?
auto const methods = cls->data()->methods();
for (auto mlists = methods.beginLists(),
end = methods.endLists();
mlists != end;
++mlists)
{
// <rdar://problem/46904873> getMethodNoSuper_nolock is the hottest
// caller of search_method_list, inlining it turns
// getMethodNoSuper_nolock into a frame-less function and eliminates
// any store from this codepath.
method_t *m = search_method_list_inline(*mlists, sel);
if (m) return m;
}
return nil;
}
-
ASSERT(cls->isRealized());：判断cls是否已注册（以后会讲到）； -
auto const methods = cls->data()->methods();：这句大家很熟息了，取出当前class的方法列表（详见类的结构解析）； - for循环遍历类的每一个方法列表（类的方法列表可能是二位数组
class method_array_t : public list_array_tt<method_t, method_list_t, method_list_t_authed_ptr>），查找的核心方法search_method_list_inline去掉多余代码后为：
search_method_list_inline(const method_list_t *mlist, SEL sel)
{
int methodListIsFixedUp = mlist->isFixedUp();
int methodListHasExpectedSize = mlist->isExpectedSize();
if (fastpath(methodListIsFixedUp && methodListHasExpectedSize)) {
return findMethodInSortedMethodList(sel, mlist);
} else {
// Linear search of unsorted method list
if (auto *m = findMethodInUnsortedMethodList(sel, mlist))
return m;
}
return nil;
}
可以看到，查找的核心方法是findMethodInSortedMethodList(sel, mlist)，继续查看他的源码找到核心方法指向了findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)，也就是慢速查找方法的重点二分查找法（为什么用二分法？因为一个类可能含有的方法可能数量很多）：
findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)
{
ASSERT(list);
auto first = list->begin();
auto base = first;
decltype(first) probe;
uintptr_t keyValue = (uintptr_t)key;
uint32_t count;
for (count = list->count; count != 0; count >>= 1) {
probe = base + (count >> 1);
uintptr_t probeValue = (uintptr_t)getName(probe);
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)getName((probe - 1))) {
probe--;
}
return &*probe;
}
if (keyValue > probeValue) {
base = probe + 1;
count--;
}
}
return nil;
}
- for循环的条件为（count = 方法数；count不等于0；count右移1位），这里右移1位相当于除以2，为了方便逻辑理解，这里假设count = 8（8-
1000右移一位变为40100，相当于8除以2）； -
probe = base + (count >> 1);：base初始值为begin，也就是0，probe = 0 + （8>>1 = 4）= 4，for循环第一次查找的位置是4号位置; - keyValue就是传进来的SEL转成long类型的值，假设keyValue等于7，同样的probeValue就是probe转为long类型的值
uintptr_t probeValue = (uintptr_t)getName(probe)，将两者相比较看取到的probe值是否等于传进来的SEL； - 如果相等，意为找到了对应方法。这之间还存在一个white循环，通过注释可知这是查找category中是否有重写当前方法，存在则执行probe--，这也证明了：当有category重写当前方法时，将执行category中的方法，并且，当有多个category重写同一方法时，会执行最后一个category中的方法。如果category中没有重写方法，则返回
&*probe，也就是对应的imp； - 如果不相等，则判断如果SEL转成的值大于4，则
base = probe + 1等于5，count--等于7，开始第二次循环 - 第二次循环时，循环条件上
count>>1也就是7>>1为3，probe = base + (count >> 1)即probe = 5 + （3>>1 = 1）= 6，即第二次查找在数组的第六位。再次没找到的话符合keyValue > probeValue，base = 6+1 = 7，count-- = 3 - 1 = 2，开始第三次循环； - 第三次循环，循环条件上
count>>1也就是2>>1为1，probe = base + (count >> 1)即probe = 7 + （1>>1 = 0）= 7，即第三次查找在数组的第七位，找到了对应方法。 - 如果keyValue小于4会怎么样大家可以自己走一遍，体会一下count在循环中连续右移1位的精妙之处。
- 如果一直没有找到，则最终返回nil。
至此，慢速查找过程的二分查找法分析完毕。
像父类中查找方法
重新回到lookUpImpOrForward中，如果在方法列表中没有找到对应方法，那么接下来：
if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
// No implementation found, and method resolver didn't help.
// Use forwarding.
imp = forward_imp;
break;
}
这里其实做了两步操作，首先在if条件中，将curClass赋值为了当前类的父类curClass = curClass->getSuperclass()，如果有父类，则跳过；如果当前类没有父类，意味着当前类已经是根类，要查找的方法在本类至根类都没有对应方法的实现，因此返回了forward_imp开始进入消息转发流程，这一点其实在之前类的方法归属中探究过，当查找一个类中是否有对应方法的实现时，即使没有实现该方法，也会有imp返回值，返回的是_objc_msgForward，消息转发将在下一篇重点讲解。
再继续，获取到父类之后：
// Superclass cache.
imp = cache_getImp(curClass, sel);
if (fastpath(imp)) {
// Found the method in a superclass. Cache it in this class.
goto done;
}
其中cache_getImp需要我们回到汇编中：
STATIC_ENTRY _cache_getImp
GetClassFromIsa_p16 p0, 0
CacheLookup GETIMP, _cache_getImp, LGetImpMissDynamic, LGetImpMissConstant
CacheLookup代码我们已经很熟悉了，跟之前objc_msgSend中的流程一样，获取isa->class，然后在缓存中查找方法，如果父类缓存中有的对应方法imp的话同样执行goto done;。但是这里要注意区别：在第一次FCPerson调用CacheLookup过程中第一个参数是NORMAL，NORMAL模式使得缓存中找不到imp后执行objc_msgSend_uncached，但是现在查到父类的时候，传参为GETIMP，我们来看区别：
.if \Mode == GETIMP
b.ne \MissLabelConstant // cache miss
sub x0, x16, x17, LSR #32 // imp = isa - imp_offs
SignAsImp x0
ret
.else
b.ne 5f // cache miss
sub x17, x16, x17, LSR #32 // imp = isa - imp_offs
.if \Mode == NORMAL
br x17
.elseif \Mode == LOOKUP
orr x16, x16, #3 // for instrumentation, note that we hit a constant cache
SignAsImp x17
ret
.else
可以看到当Mode = GETIMP时，查找不到会直接返回空，因此慢速查找过程中，父类缓存中没找到，不会调用uncache方法，而是直接返回nil然后继续lookUpImpOrForward中的循环，而再次循环时cls已经是superClass了，重新对父类再次执行慢速查找的流程，直至找到根类，其实整个查找的过程就递归的过程。
接下来我们继续分析找到方法的imp后，goto done;做了什么：
done:
if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) {
#if CONFIG_USE_PREOPT_CACHES
while (cls->cache.isConstantOptimizedCache(/* strict */true)) {
cls = cls->cache.preoptFallbackClass();
}
#endif
log_and_fill_cache(cls, imp, sel, inst, curClass);
}
核心方法：log_and_fill_cache(cls, imp, sel, inst, curClass);就是说当一个本不在缓存中的方法找到imp后，将会进行缓存填充，把新的方法放入缓存中，方便下一次可以直接在缓存中找方法，不需要再次经过慢速查找：
log_and_fill_cache(Class cls, IMP imp, SEL sel, id receiver, Class implementer)
{
#if SUPPORT_MESSAGE_LOGGING
if (slowpath(objcMsgLogEnabled && implementer)) {
bool cacheIt = logMessageSend(implementer->isMetaClass(),
cls->nameForLogging(),
implementer->nameForLogging(),
sel);
if (!cacheIt) return;
}
#endif
cls->cache.insert(sel, imp, receiver);
}
看到cls->cache.insert(sel, imp, receiver);，终于达到了终点insert方法！
总结
综合之前几篇我们的学习，可以得到一个整体的流程：
1.类的结构中有方法列表methods和缓存的方法列表cache_t；
2.对对象发送消息时执行objc_msgSend；
3.objc_msgSend时会先在cache中找，没有就会调用objc_msgSend_uncached走到lookUpImpOrForward方法进行循环慢速查找，通过二分法去methods中查找；
4.如果没找到则会开始递归，到父类的缓存中找，找不到的话不会调用objc_msgSend_uncached，而是返回空并且继续lookUpImpOrForward循环，这次循环时，查找的目标cls变为superClass，对superClass进行慢速查找，最终到根类；
4.如果在cache中找到，则直接执行；如果在methods中找到，则把方法插入缓存insert；
5.如果都没有，开始消息转发流程。
