我们在 C底层原理11-objc_msgSend源码分析(方法查找快流程) 一文中，探索了objc_msgSend方法快速查找流程（从缓存中获取方法），cache类型的源码在OC底层全部用汇编实现，优点是快，我们发现如果CacheLookup流程找不到的话，就会进入CheckMiss -> __objc_msgSend_uncached -> MethodTableLookup -> lookUpImpOrForward流程，lookUpImpOrForward也就是我们今天要研究的慢速查找流程，它的源码在objc层中，用OC实现
一、准备工作
1.1、objc4可编译源码，可直接跳到文章最后，下载调试好的源码
1.2、在源码中新增类GomuPerson如下
GomuPerson.h
- (void)sayNO;
GomuPerson.m
//不实现方法，方便后面二分法研究
二、lookUpImpOrForward源码探索
2.1 lookUpImpOrForward方法源码
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
//: -- 创建一个默认forward_imp，并赋值_objc_msgForward_impcache
const IMP forward_imp = (IMP)_objc_msgForward_impcache;
//: -- 创建一个imp，值为nil
IMP imp = nil;
//: -- 创建一个类curClass
Class curClass;
runtimeLock.assertUnlocked();
//: -- 因为是多线程，并且后面要开始耗时操作了，防止获取的时候正在cache的情况没取到，所以再取一次cache
//: -- 如果在当前cls的cache没有找到imp，则继续执行
//: -- 如果找到了，则跳转到done_nolock
if (fastpath(behavior & LOOKUP_CACHE)) {
//: -- 从cls的缓存中取imp
imp = cache_getImp(cls, sel);
if (imp) goto done_nolock;
}
runtimeLock.lock();
//: -- 判断当前cls是否为已知类
//: -- 防止人为制造类，进行CFI攻击
checkIsKnownClass(cls);
//: -- 如果类没有实现，则去实现，并对其继承链进行实现关联
//: -- 类是双向链表，所以需要双向绑定
//: -- cls->superclass = supercls 给cls的父类赋值supercls
//: -- addSubClass(supercls, cls) 给supercls添加subClass
//: -- 猜想，是分类走的流程
if (slowpath(!cls->isRealized())) {
cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
}
//: -- 递归实现类/元类继承链的initialize方法
if (slowpath((behavior & LOOKUP_INITIALIZE) && !cls->isInitialized())) {
cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
}
runtimeLock.assertLocked();
//: -- 把cls赋值给curClass
curClass = cls;
//: -- 开始for循环，递归查找
//: -- 自己的methods -> 父类的cache -> 父类的methods -> 直到nil
for (unsigned attempts = unreasonableClassCount();;) {
//: -- 首先从自己的methods里面查找，这里牵涉到一个优化算法，我们后面单独聊
Method meth = getMethodNoSuper_nolock(curClass, sel);
if (meth) {
//: -- 如果找到了meth，则拿到imp，返回
imp = meth->imp;
goto done;
}
//: -- 把curClass的父类赋值给curClass，然后判断是否为nil
//: -- NSObject的父类为nil，当遍历到nil的时候就默认给imp赋值forward_imp，跳出循环
//: -- 如果不为nil，继续往下走
if (slowpath((curClass = curClass->superclass) == nil)) {
// No implementation found, and method resolver didn't help.
// Use forwarding.
imp = forward_imp;
break;
}
//: -- 防止死循环，给一个出口
if (slowpath(--attempts == 0)) {
_objc_fatal("Memory corruption in class list.");
}
//: -- curClass已经被赋值为它的父类，所以这里从父类的缓存里面找imp
imp = cache_getImp(curClass, sel);
//: -- 当curClass的父类为nil的时候，imp会被赋值forward_imp，就会走这里，跳出循环
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;
}
//: -- 如果找到imp，则跳转到done
//: -- 找自己的时候不会走这里，父类中存在imp才走这里
if (fastpath(imp)) {
// Found the method in a superclass. Cache it in this class.
goto done;
}
}
// No implementation found. Try method resolver once.
//: -- 如果遍历完了父类都没有找到imp，则进行消息处理机制，动态方法决议，这个后面我们会单独开一期来进行讲解
if (slowpath(behavior & LOOKUP_RESOLVER)) {
//: -- 这个算法超级牛 只走一次
//: -- behavior不管是什么，假设是3，0011
//: -- LOOKUP_RESOLVER = 2，0010
//: -- 第一次 0011 & 0010 = 0010 为真
//: -- 进入判断中 behavior = 0011 ^ 0010 = 0001
//: -- 第二次进入 0001 & 0010 = 0000
//: -- 第一次求&，behavior第二位必须为1，才能进入条件，进入之后，求 ^ ，第二位就会变成0，那下次再进入的时候，再求&必然为0，不再进判断
behavior ^= LOOKUP_RESOLVER;
return resolveMethod_locked(inst, sel, cls, behavior);
}
done:
//: -- 把找到的imp存进缓存，方便下次快速查找
log_and_fill_cache(cls, imp, sel, inst, curClass);
runtimeLock.unlock();
done_nolock:
//: -- 判断imp是否被赋值了forward_imp，如果是则返回nil
//: -- 防止多线程操作imp没找到，被赋值为forward_imp时，成功返回了错误的imp
if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
return nil;
}
//: -- 如果在开始慢查询之前，从缓存中找到了则直接返回当前的imp
return imp;
}
- 得出以下流程：
自己的cache-> 自己的methods-> 父亲的cache-> 父亲的methods-> 父亲的父亲的cache-> 父亲的父亲的methods->nil->resolveMethod_locked（动态方法决议） -
附流程图
lookUpImpOrForward流程图.png
2.2 getMethodNoSuper_nolock方法源码
static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
runtimeLock.assertLocked();
ASSERT(cls->isRealized());
//: -- 拿到cls的data()里面存的methods()
auto const methods = cls->data()->methods();
//: -- 循环（目的不清楚）,断点调试的时候要走很多次，加载很多系统的方法列表
for (auto mlists = methods.beginLists(),
end = methods.endLists();
mlists != end;
++mlists)
{
//: -- 从方法列表中找当前sel
//: -- 类中自定义的方法第一次循环的时候走这里，存在methods.beginLists()
method_t *m = search_method_list_inline(*mlists, sel);
if (m) return m;
}
return nil;
}
- 进入
search_method_list_inline后会调用findMethodInSortedMethodList
2.3 findMethodInSortedMethodList源码
ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
ASSERT(list);
//: -- 把第list一个元素赋值给first
const method_t * const first = &list->first;
//: -- 把fistr赋值给base
const method_t *base = first;
const method_t *probe;
//: -- 把当前传入的sel转成uintptr_t类型，并赋值给keyValue
uintptr_t keyValue = (uintptr_t)key;
uint32_t count;
//: -- 二分法查找sel，向前查找
for (count = list->count; count != 0; count >>= 1) {
//: -- 指针平移，相当于地址平移到中间位置，count >> 1相当于count/2
probe = base + (count >> 1);
//: -- 拿到当前probe中的name，这里对应sel
uintptr_t probeValue = (uintptr_t)probe->name;
//: -- 判断当前keyValue是否等于probeValue
if (keyValue == probeValue) {
//: -- 判断是否有分类方法
while (probe > first && keyValue == (uintptr_t)probe[-1].name) {
//: -- 如果有分类方法，并且keyValue不是第一个元素
//: -- 如果类和分类都有同一个方法，则会走这里
//: -- 取当前类前面一位，即分类方法，分类方法后加如methods，优先读取
probe--;
}
//: -- 返回当前找到的method_t
return (method_t *)probe;
}
//: -- 查keyValue比二分位大的时候需要走这里
if (keyValue > probeValue) {
//: -- 如果目标在二分位右边，则讲当前base右移一位
base = probe + 1;
//: -- count自减
count--;
}
}
return nil;
}
2.3.1 对象方法和属性调用前在methods中的储存顺序：
- 先存
对象方法，按照对象方法在.m中的实现顺序依次存储属性按照属性在.h/.m中的声明顺序逆序存储，先get，再set
如下图：(.h中改成.m实现，画错了)
对象方法和属性调用前在methods中的储存顺序图.png
2.3.2 对象方法调用之后在methods中的储存顺序：
- 判断当前
类的类别中是否有该对象方法，有就先存储类别中的对象方法，再存储类中的对象方法（如果类中有，类中可能没有，只有.m实现也会存储），如果没有，则直接存当前类中的对象方法- 先调用的
存储在前面，后调用的存储在上一个方法的后面(即相对最前面)，最先调用的存在最前面没有调用的按照以前的顺序排在后面
如下图：
对象方法调用之后在methods中的储存顺序
2.3.3 findMethodInSortedMethodList中，二分法算法介绍
-
查询目标一直小于遍历中位数，流程图如下
image.png
-
查询目标大于遍历中位数，流程图如下
image.png
三、拓展知识
3.1 交替进入的if的位运算
//: -- LOOKUP_RESOLVER = 2
//: -- 省略外层for循环
if (slowpath(behavior & LOOKUP_RESOLVER)) {
behavior ^= LOOKUP_RESOLVER;
return resolveMethod_locked(inst, sel, cls, behavior);
}
- 把
LOOKUP_RESOLVER换成2进制0010 -
behavior分2种情况，一种是第二位为1，第二种是第二位不为1，分别用1111，1101举例 - 随着
behavior的累加，当第二位为1的时候就能进，第二位为0的时候就不能进（为1不进，为2进，为3不进，为4进...）
第一种情况
1. 第一种`behavior`为1111，`behavior & LOOKUP_RESOLVER`=`1111 & 0010`，为真，进入`if`
2. 进入后`behavior ^= LOOKUP_RESOLVER`，`behavior ` = `1111 ^ 0010` = `1101`
3. 下次循环过来，`behavior & LOOKUP_RESOLVER` = `1101 & 0010`，为假，不再进入循环
得出结论：第二位为1，必然可以进入
循环一次，进入后与0010异或之后，第二位变0，下次与0010求与的时候，必定为假，这样就保证了if只走一次
第二种情况
第二种`behavior`为1101，`behavior & LOOKUP_RESOLVER`=`1101 & 0010`，为假，不能进入`if`
得出结论：第二位为0，连if都进不去
3.2 方法调用的本质，就是找imp，没有实现就找不到imp，和方法声明没关系
-
类中声明并实现了方法，类别中未声明且未实现，则调用类中的方法 -
类中声明并实现了方法，类别中声明但未实现，则调用类中的方法 -
类中声明并实现了方法，类别中未声明但实现，则调用类别中的方法 -
类中声明并实现了方法，类别中声明且实现，则调用类别中的方法 -
类中声明未实现方法，类别中未声明但实现，则调用类别中的方法 -
类中未声明但实现方法，类别中声明但未实现，则调用类中的方法
总结：
类和类别中有一个实现，则谁实现就调用谁的类和类别中都实现，则优先调用类别的类和类别如果都没有声明，则不能直接通过[p sayNO]方式调用，可以通过performSelector，objc_msgSend调用，即方法声明不是必须的
objc_msgSend(p, sel_registerName("sayNO"));
[p performSelector:@selector(sayNO)];
网友评论