在前面的文章iOS底层原理10：消息流程分析之快速查找中，我们分析了快速查找流程，如果快速查不到，则需要进入慢速查找流程，以下是慢速查找的分析过程
1、objc_msgSend 慢速查找流程分析
1.1、慢速查找-汇编部分分析
在快速查找流程中，如果没有找到方法实现，会走到__objc_msgSend_uncached汇编函数
- 在
objc-msg-arm64.s文件中查找__objc_msgSend_uncached的汇编实现，其中的核心是MethodTableLookup（即查询方法列表），其源码如下
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
// 查询方法列表，将方法imp 存储到x17寄存器
MethodTableLookup
// 相当于【br x17】
TailCallFunctionPointer x17
END_ENTRY __objc_msgSend_uncached
- 查看
MethodTableLookup的汇编实现，调用了_lookUpImpOrForward函数来查找方法，汇编代码如下：
.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
//---- _lookUpImpOrForward的参数: 【x0 = receiver; x1 = _cmd; x2 = isa即类的首地址； x3 = 3 】
bl _lookUpImpOrForward // 核心代码【须牢记】
// IMP in x0
mov x17, x0
RESTORE_REGS MSGSEND
.endmacro
1.2、通过汇编调试验证
- 在
ViewController.m的[person sayHello];方法调用处添加断点，运行程序，开启汇编调试【Debug -- Debug worlflow -- 勾选Always show Disassembly】
image
- 按住
control + Step into，进入objc_msgSend的汇编
image
- 在
_objc_msgSend_uncached加一个断点，执行到断点处，按住control + Step into，进入汇编
image
从上可以看出最后走到的就是lookUpImpOrForward，此时并不是汇编实现
慢速查找-C/C++部分
lookUpImpOrForward源码分析
- 根据汇编部分的提示，全局续搜索
lookUpImpOrForward，最后在objc-runtime-new.mm文件中找到了源码实现，这是一个c实现的函数
NEVER_INLINE
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();
if (slowpath(!cls->isInitialized())) {
// The first message sent to a class is often +new or +alloc, or +self
// which goes through objc_opt_* or various optimized entry points.
//
// However, the class isn't realized/initialized yet at this point,
// and the optimized entry points fall down through objc_msgSend,
// which ends up here.
//
// We really want to avoid caching these, as it can cause IMP caches
// to be made with a single entry forever.
//
// Note that this check is racy as several threads might try to
// message a given class for the first time at the same time,
// in which case we might cache anyway.
behavior |= LOOKUP_NOCACHE;
}
// 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.
//判断是否是一个已知的类：是否注册类 是否被dyld加载的类
checkIsKnownClass(cls);
//1、判断类是否实现，如果没有，需要先实现，此时的目的是为了确定父类链，方法后续的循环
//2、判断类是否初始化，如果没有，需要先初始化
cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
// runtimeLock may have been dropped but is now locked again
runtimeLock.assertLocked();
curClass = cls;
// The code used to lookup 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 (unsigned attempts = unreasonableClassCount();;) {
//判断是否有共享缓存缓存优化，一般是系统的方法比如NSLog，一般的方法不会走
if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
#if CONFIG_USE_PREOPT_CACHES
/*
再一次查询共享缓存，目的可能在你查询过程中
别的线程可能调用了这个方法共享缓存中有了直接去查询
*/
imp = cache_getImp(curClass, sel);
//如果imp存在即缓存中有 跳转到done_unlock流程
if (imp) goto done_unlock;
curClass = curClass->cache.preoptFallbackClass();
#endif
} else {
// curClass method list.
// 在curClass类中采用二分查找算法查找methodlist
Method meth = getMethodNoSuper_nolock(curClass, sel);
if (meth) {
imp = meth->imp(false); //获取对应的imp
goto done; //跳转到 done 流程
}
if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
// No implementation found, and method resolver didn't help.
// Use forwarding.
// 判断父类是否为空， 为空的话（即类的继承链走完）imp 赋值为 _objc_msgForward_impcache
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
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:
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);
}
done_unlock:
runtimeLock.unlock();
if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
return nil;
}
return imp;
}
方法查找流程主要有以下几步：
- 【第一步】
cache缓存中进行查找，即快速查找，找到则直接返回imp，反之，则进入【第二步】 - 【第二步】
慢速查找流程，先判断cls- 是否是
注册类，如果不是，则报错 - 判断类是否
实现，如果没有，需要先实现，此时的目的是为了确定父类链，方便后续的循环 - 判断类是否
初始化，如果没有，需要先初始化
- 是否是
- 【第三步】
for循环，按照类继承链或者元类继承链的顺序查找- 当前cls的
方法列表中使用二分查找算法查找方法，如果找到，则进入log_and_fill_cache，进行cache写入流程（在iOS底层原理09：类结构分析——cache属性文章中已经详述过），并返回imp - 如果没有找到，当前
cls被赋值为父类，如果父类等于nil，则imp = _objc_msgForward_impcache（消息转发），并终止递归判断，进入【第四步】 - 如果
父类链中存在循环，则报错，终止循环 -
父类缓存中查找方法- 如果
未找到，则直接返回nil，继续循环查找 - 如果
找到，则直接返回imp，执行cache写入流程
- 如果
- 当前cls的
- 【第四步】判断是否执行过
动态方法解析- 如果没有，执行
动态方法解析 - 如果
执行过一次动态方法解析，则走到消息转发流程
- 如果没有，执行
以上就是方法的慢速查找流程，下面在分别详细解释二分查找原理 以及 父类缓存查找详细步骤
二分查找方法列表（getMethodNoSuper_nolock方法）
查找方法列表的流程如下所示
image
其二分查找核心的源码实现如下
/***********************************************************************
* search_method_list_inline
**********************************************************************/
template<class getNameFunc>
ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)
{
ASSERT(list);
auto first = list->begin();
auto base = first;
decltype(first) probe;
// 把key直接转换成uintptr_t 因为修复过后的method_list_t中的元素是排过序的
uintptr_t keyValue = (uintptr_t)key;
uint32_t count;
//base相当于low，count是max，probe是middle，这就是二分
// 假如 count = list->count = 8 ； （count >>= 1） = 4
for (count = list->count; count != 0; count >>= 1) {
//从首地址+下标 --> 移动到中间位置（count >> 1 右移1位即 count/2 = 4）
probe = base + (count >> 1);
uintptr_t probeValue = (uintptr_t)getName(probe);
// 如果 目标key == 中间位置的key 匹配成功
if (keyValue == probeValue) {
// `probe` is a match.
// Rewind looking for the *first* occurrence of this value.
// This is required for correct category overrides.
// -- while 平移 -- 排除分类重名方法
while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
//分类覆盖，分类中有相同名字的方法，如果有分类的方法我们就获取分类的方法，多个分类看编译的顺序
probe--;
}
//返回方法的地址
return &*probe;
}
//如果keyValue 大于 probeValue，就往probe即中间位置的右边查找
if (keyValue > probeValue) {
base = probe + 1;
count--;
}
}
return nil;
}
算法原理简述为：从第一次查找开始，每次都取中间位置，与想查找的key的value值作比较，如果相等，则需要排除分类方法，然后将查询到的位置的方法实现返回，如果不相等，则需要继续二分查找，如果循环至count = 0还是没有找到，则直接返回nil，如下所示：
流程图待补充
父类缓存查找（cache_getImp方法）
cache_getImp方法是通过汇编_cache_getImp实现，传入的$0 是 GETIMP，如下所示
image
- 如果
父类缓存中找到了方法实现，则跳转至CacheHit即命中，则直接返回imp - 如果在
父类缓存中，没有找到方法实现，则跳转至LGetImpMissDynamic，将p0的值设为0x0，即返回nil
总结
- 对于
对象方法（即实例方法），即在类中查找，其慢速查找的父类链是：类--父类--根类--nil - 对于
类方法，即在元类中查找，其慢速查找的父类链是：元类--根元类--根类--nil - 如果
快速查找、慢速查找也没有找到方法实现，则尝试动态方法决议 - 如果
动态方法决议仍然没有找到，则进行消息转发
网友评论