注册

lookUpImpOrForward 消息慢速查找(下)

3.1.2 search_method_list_inline

ALWAYS_INLINE static method_t *
search_method_list_inline(const method_list_t *mlist, SEL sel)

{
//methodlist是否已经修复
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。
  • 无序进入循环查找findMethodInUnsortedMethodList。

⚠️ 那么就有个问题，排序是什么时候完成的？
既然是method_t相关类型那就进去搜一下sort相关的关键字。发现了如下方法：

 struct SortBySELAddress :
public std::binary_function<const struct method_t::big&,
const struct method_t::big&, bool>

    {
bool operator() (const struct method_t::big& lhs,
const struct method_t::big& rhs)

        { return lhs.name < rhs.name; }

    };

1b89ba8cfcb453ff781b65923bbc1cc5.png

是在_read_images类加载映射的时候注册调用的。又见到了_read_images，这个方法将在后面继续研究。

结论：类在加载实例化的时候进行的排序，是按照sel address进行排序的。

3.1.3 findMethodInSortedMethodList 二分查找

findMethodInSortedMethodList会根据架构最终进入各自的findMethodInSortedMethodList方法，这里以x86为例进行分析：

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;


    uintptr_t keyValue = (uintptr_t)key;
//method list count
uint32_t count;
//count >>= 1 相当于除以2。加入count为8
for (count = list->count; count != 0; count >>= 1) {//7 >> 1 = 3，前一个已经比较了4，这里就完美的避开了4。
//base是为了配合少查找
//probe中间元素，第一次 probe = 0 + 8 >> 1 = 4

        probe = base + (count >> 1);
//sel

        uintptr_t probeValue = (uintptr_t)getName(probe);
//与要查找的sel是否匹配
if (keyValue == probeValue) {
// `probe` is a match.
// Rewind looking for the *first* occurrence of this value.
// This is required for correct category overrides.
//查找分类同名sel。如果匹配了就找分类中的。因为分类是在前面的，所以一直找到最开始的位置。
while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {

                probe--;

            }
//匹配则返回。
return &*probe;

        }
//没有匹配
if (keyValue > probeValue) {//大于的情况下，在后半部分
//没有匹配的情况下，如果sel在后半部分，这里base指向了上次查找的后面一个位置。

            base = probe + 1;//5
//count对应减1

            count--;//7 -- 操作为了少做比较，因为已经比较过了

        }
//在前半部分不进行额外操作。

    }

return nil;

}
  • 首先是一个循环比较，条件是count >>= 1，这里是对count进行减半，相当于二分。
  • base是为了少做比较，相当于是一个基线，当要继续往后查找的时候base为当前查找元素的下一个元素。
  • 当要继续往后查找的时候count进行了--操作，这一步是为了count >>= 1不包含已经比较过的范围。
  • 找到值的时候会循环继续往前查找，因为存在分类与类中方法同名的情况（分类方法放在类中同名方法前面），一直找到不同名为止。

⚠️根据源码可以得到以下结论：
1.分类方法调用先找类中方法，再逐次找到分类方法，直到找到第一个。
2.因为判断条件是当前命中元素与前一个元素比较，sel相同的情况下才继续查找，那就说明分类的方法是插入类中方法列表中的，都在对应类中方法的前面。

  • 查找完毕后会返回lookUpImpOrForward

这里以有8个方法为类来分析查找流程，过程如下：

比较开始值：count = 8 base = 0 probe = 4
- 第一次：比较 probe = 4
- keyValue > probeValue  count = 3（先--，再>>1） base = 5  probe = 6

        第二次： 比较 probe = 6
- keyValue > probeValue count = 1（先--，再>>1） base = 7  probe = 7

            第三次：比较 probe = 7
- keyValue > probeValue count = 0（先--，再>>1） base = 8  probe = 8（count == 0）
- keyValue < probeValue count = 0（>>1） base = 7  probe = 7 （count == 0）
- keyValue < probeValue count = 1（>>1） base = 5  probe = 5

            第三次：比较 probe = 5
- keyValue > probeValue count = 0（先--，再>>1） base = 6  probe = 6 （count == 0）
- keyValue < probeValue count = 0（>>1） base = 5  probe = 5（count == 0）
- keyValue < probeValue count = 4（>>1） base = 0  probe = 2

        第二次：比较 probe = 2
- keyValue > probeValue count = 1（先--，再>>1） base = 3  probe = 3

            第三次：比较 probe = 3
- keyValue > probeValue count = 0（先--，再>>1） base = 4  --（count == 0）
- keyValue < probeValue count = 0（>>1） base = 3  -- （count == 0）
- keyValue < probeValue count = 2（>>1） base = 1  probe = 1

            第三次：比较 probe = 1
- keyValue > probeValue count = 0（先--，再>>1） base = 0  --（count == 0）
- keyValue < probeValue count = 1（>>1） base = 0 probe = 0

                    第四次：比较 probe = 0
- keyValue > probeValue count = 0（先--，再>>1） base = 1  --（count == 0）
- keyValue < probeValue count = 0（>>1） base = 0 -- （count == 0）

代码模拟：

int testFindSortedMethods(int methodCount,int findKey) {
int base = 0;
int probe = 0;
int round = 0;
printf("查找key:%d\n",findKey);
for (int count = methodCount; count != 0; count >>= 1) {

        round++;

        probe = base + (count >> 1);
printf("\t第%d轮 scan count :%d, base:%d,probe:%d\n",round,count,base,probe);
if (findKey == probe) {
printf("\tfound prode:%d\n",probe);
return probe;

        }
if (findKey > probe) {

            base = probe + 1;

            count--;

        }

    }
printf("\tnot found -1\n");
return -1;

}

调用：

testFindSortedMethods(8, 0);

testFindSortedMethods(8, 1);

testFindSortedMethods(8, 2);

testFindSortedMethods(8, 3);

testFindSortedMethods(8, 4);

testFindSortedMethods(8, 5);

testFindSortedMethods(8, 6);

testFindSortedMethods(8, 7);

testFindSortedMethods(8, 8);

testFindSortedMethods(8, 9);

输出：

查找key:0

    第1轮 scan count :8, base:0,probe:4

    第2轮 scan count :4, base:0,probe:2

    第3轮 scan count :2, base:0,probe:1

    第4轮 scan count :1, base:0,probe:0

    found prode:0
查找key:1

    第1轮 scan count :8, base:0,probe:4

    第2轮 scan count :4, base:0,probe:2

    第3轮 scan count :2, base:0,probe:1

    found prode:1
查找key:2

    第1轮 scan count :8, base:0,probe:4

    第2轮 scan count :4, base:0,probe:2

    found prode:2
查找key:3

    第1轮 scan count :8, base:0,probe:4

    第2轮 scan count :4, base:0,probe:2

    第3轮 scan count :1, base:3,probe:3

    found prode:3
查找key:4

    第1轮 scan count :8, base:0,probe:4

    found prode:4
查找key:5

    第1轮 scan count :8, base:0,probe:4

    第2轮 scan count :3, base:5,probe:6

    第3轮 scan count :1, base:5,probe:5

    found prode:5
查找key:6

    第1轮 scan count :8, base:0,probe:4

    第2轮 scan count :3, base:5,probe:6

    found prode:6
查找key:7

    第1轮 scan count :8, base:0,probe:4

    第2轮 scan count :3, base:5,probe:6

    第3轮 scan count :1, base:7,probe:7

    found prode:7
查找key:8

    第1轮 scan count :8, base:0,probe:4

    第2轮 scan count :3, base:5,probe:6

    第3轮 scan count :1, base:7,probe:7

    not found -1
查找key:9

    第1轮 scan count :8, base:0,probe:4

    第2轮 scan count :3, base:5,probe:6

    第3轮 scan count :1, base:7,probe:7

    not found -1

可以看到输出与验证的结论一致。

流程图：


1fa9807af6f67da4c0d84fa688e43be2.png


四、案例分析慢速查找流程

定义一个HPObject以及它的子类HPSubObject，
HPObject定义和实现如下：

@interface HPObject : NSObject

- (void)instanceMethod1;

- (void)instanceMethod2;

+ (void)classMethod;

@end

@implementation HPObject

- (void)instanceMethod1 {
NSLog(@"%s",__func__);

}

+ (void)classMethod {
NSLog(@"%s",__func__);

}

@end

HPSubObject定义和实现如下：

@interface HPSubObject : HPObject

- (void)subInstanceMethod;

@end

@implementation HPSubObject

- (void)subInstanceMethod {
NSLog(@"%s",__func__);

}

@end

根据前面分析的方法查找逻辑测试代码：

#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wundeclared-selector"

        HPSubObject *subObject = [HPSubObject new];
//对象方法 根据慢速查找分析是能找到的

        [subObject subInstanceMethod];

        [subObject instanceMethod1];

        [subObject instanceMethod2];
#pragma clang diagnostic pop

输出：

-[HPSubObject subInstanceMethod]
-[HPObject instanceMethod1]
-[HPSubObject instanceMethod2]: unrecognized selector sent to instance 0x1006addc0
*** Terminating app due to uncaught exception 'NSInvalidArgumentException', reason: '-[HPSubObject instanceMethod2]: unrecognized selector sent to instance 0x1006addc0'
subInstanceMethod与instanceMethod1符合预期。instanceMethod2找不到报错unrecognized selector sent to instance，为什么报这个错误呢？
查看调用堆栈如下：

d9b196d184e8a35ddde480695ec812c8.png

  • 那么去源码中搜索错误信息找到以下内容：
// Replaced by CF (throws an NSException)
+ (void)doesNotRecognizeSelector:(SEL)sel {
_objc_fatal("+[%s %s]: unrecognized selector sent to instance %p", 
class_getName(self), sel_getName(sel), self);

}

// Replaced by CF (throws an NSException)
- (void)doesNotRecognizeSelector:(SEL)sel {
_objc_fatal("-[%s %s]: unrecognized selector sent to instance %p", 
object_getClassName(self), sel_getName(sel), self);

}

// Default forward handler halts the process.
__attribute__((noreturn, cold)) void
objc_defaultForwardHandler(id self, SEL sel)

{
_objc_fatal("%c[%s %s]: unrecognized selector sent to instance %p "
"(no message forward handler is installed)", 
class_isMetaClass(object_getClass(self)) ? '+' : '-', 
object_getClassName(self), sel_getName(sel), self);

}
void *_objc_forward_handler = (void*)objc_defaultForwardHandler;

那么调用的是哪个呢？断点后并没有进入。根据上面的分析imp找不到的时候会有两个选项resolveMethod_locked或者_objc_msgForward_impcache。
_objc_msgForward_impcache的汇编实现如下：

STATIC_ENTRY __objc_msgForward_impcache

// No stret specialization.

b   __objc_msgForward


END_ENTRY __objc_msgForward_impcache

内部直接调用了__objc_msgForward：

ENTRY __objc_msgForward


adrp    x17, __objc_forward_handler@PAGE

ldr p17, [x17, __objc_forward_handler@PAGEOFF]

TailCallFunctionPointer x17


END_ENTRY __objc_msgForward

可以看到__objc_msgForward的实现是调用__objc_forward_handler，也就是:

// Default forward handler halts the process.
__attribute__((noreturn, cold)) void
objc_defaultForwardHandler(id self, SEL sel)

{
_objc_fatal("%c[%s %s]: unrecognized selector sent to instance %p "
"(no message forward handler is installed)", 
class_isMetaClass(object_getClass(self)) ? '+' : '-', 
object_getClassName(self), sel_getName(sel), self);

}
void *_objc_forward_handler = (void*)objc_defaultForwardHandler;

这也就是报错信息的原因，里面进行了格式化的错误信息打印。

接着增加一个NSObject的分类：

@interface NSObject (Additions)

- (void)categoryInstanceMethod;

@end

@implementation NSObject (Additions)

- (void)categoryInstanceMethod {
NSLog(@"%s",__func__);

}

@end
调用：

#pragma clang diagnostic push
#pragma clang diagnostic ignored "-Wundeclared-selector"

        [HPSubObject classMethod];

        [HPSubObject performSelector:@selector(categoryInstanceMethod)];
#pragma clang diagnostic pop
输出：

+[HPObject classMethod]

-[NSObject(Additions) categoryInstanceMethod]
  • classMethod类方法能找到符合预期。
  • 为什么HPSubObject能调用categoryInstanceMethod实例方法？
    这就涉及到了类的继承链，NSObject元类的父类是NSObject类，所以能找到。

再次说明在OC的底层没有实例和类方法的区分，类方法和实例方法是人为加上去的。我们只是为了配合OC的演出视而不见。

五、 总结

慢速查找流程：

  • checkIsKnownClass检查注册类。
  • realizeAndInitializeIfNeeded_locked初始化类，为方法查找做好准备。
  • 递归查找imp，会涉及到动态缓存库的二次确认以及父类的快速慢速查找。
    • 查找过程会进行二分查找/递归查找。
    • 是否二分要看方法列表是否已经排序，排序操作是在类加载实例化的时候完成的。
    • 二分查找算法很经典，充分利用>>1以及--不多浪费一次机会。
  • 找到imp直接跳转返回。根据LOOKUP_NOCACHE判断是否插入缓存。
  • 没有找到则判断是否进行动态方法决议。
  • 不进行动态方法决议则判断是否要forward


作者：HotPotCat
链接：https://www.jianshu.com/p/db43c28e0e11


0
分享
2021-08-24

0 个评论

要回复文章请先登录或注册

一个开放、互助、协作、创意的社区

关于imGeek
关于专职工程师值守
社区财富榜
赞助商
友情链接
热门标签
京ICP备2023000793号