iOS-底层探索09：方法的慢速查找流程分析

作者: differ_iOSER | 来源:发表于2020-09-22 17:31 被阅读0次

iOS 底层探索文章汇总

一、前言

上一篇文章iOS objc_msgSend 流程分析中我们分析了objc_msgSend的底层代码以及方法的查找流程，objc_msgSend也叫做方法的快速查找流程，那么这篇文章我们就一起分析方法的慢速查找流程是怎样的。

二、一个方法查找流程的问题

首先定义一个类NAPerson：

@interface NAPerson : NSObject
@end

@implementation NAPerson
@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        [NAPerson performSelector:@selector(sayEasy)];
    }
    return 0;
}

打印结果：unrecognized selector sent to class 0x100008268

然后定义一个分类

@interface NSObject (NACate)
- (void)sayEasy;//可注释
@end

@implementation NSObject (NACate)
- (void)sayEasy {
    NSLog(@"%s",__func__);
}
@end

现在运行就不会报错了，原因如下：
参考isa 指向图，类方法的查找流程为：元类 -->元类的父类 --> 根元类 --> 根类(NSObject)。而且调用类方法就是调用元类的实例方法，所以能在NSObject分类中能够找到sayEasy的实现。

NSObject的实例方法，所有以NSObject为根类的类都可以调用（可作为类方法调用，也可作为实例方法调用）

NSObject的类方法，所有以NSObject为根类的类都可以作为类方法调用，但不能作为实例方法调用

三、方法慢速查找流程分析

当方法进行快速查找流程objc_msgSend没有找到方法后就会进入慢速查找流程即进入lookUpImpOrForward方法:

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();

    // Optimistic cache lookup
    if (fastpath(behavior & LOOKUP_CACHE)) {
        imp = cache_getImp(cls, sel);
        if (imp) goto done_nolock;
    }

    runtimeLock.lock();// 加锁防止对并发实现的竞争

    // TODO: this check is quite costly during process startup.
    checkIsKnownClass(cls);// 检查是否是合法注册的类，防止CFI攻击

    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
    } //判断是否是initialize方法，初始化所有相关的类

    runtimeLock.assertLocked();
    curClass = cls;

    // 再次查找类缓存的方法
    for (unsigned attempts = unreasonableClassCount();;) {
        // curClass method list.
        Method meth = getMethodNoSuper_nolock(curClass, sel);
        if (meth) {
            imp = meth->imp;
            goto done;
        }

        if (slowpath((curClass = curClass->superclass) == nil)) {
            // 没有找到实现，将imp赋值为forward_imp，所以class_getMethodImplementation
            // 对于没有实现的方法也会返回值
            imp = forward_imp;
            break;
        }

        // 如果超类链中存在循环，则停止。
        if (slowpath(--attempts == 0)) {
            _objc_fatal("Memory corruption in class list.");
        }

        // Superclass cache.
        // 在缓存中查找，如果之前这个方法标记了forward_imp，那么这次查找也可能找不到实现
        imp = cache_getImp(curClass, sel);
        if (slowpath(imp == forward_imp)) {
            //在超类中发现一个forward::条目。
            //停止搜索，但还没有缓存;首先调用该类的方法解析器。
            break;
        }
        if (fastpath(imp)) {
            // 在超类中找到该方法。在这个类中缓存它。
            goto done;
        }
    }

    // No implementation found. Try method resolver once.
    // 在本类和父类的继承链中均没找到方法的实现就进入 消息转发机制
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;//behavior = behavior^LOOKUP_RESOLVER;
        return resolveMethod_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)) {
        return nil;
    }
    return imp;
}

细节分析和流程图均可参考iOS objc_msgSend 流程分析文章下半部分的分析。

这里主要分析方法列表中的二分查找：
因为方法列表中的方法是排好顺序的，所以使用二分查找速度比较快。
进入方法的流程如下：
lookUpImpOrForward--->getMethodNoSuper_nolock--->search_method_list_inline--->findMethodInSortedMethodList

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;
    uint32_t count;
    
    for (count = list->count; count != 0; count >>= 1) {//count >>= 1: count = count >> 1
        probe = base + (count >> 1); // 取中间值count >> 1即表示是中间值
        
        uintptr_t probeValue = (uintptr_t)probe->name;
        
        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)probe[-1].name) {
                probe--;
            }
            return (method_t *)probe;
        }
        
        if (keyValue > probeValue) {
            base = probe + 1;
            count--;
        }
    }
    
    return nil;
}

注意：分类方法排在方法列表中的前面，所以在方法列表中查找到方法后还需要向前查找同名的分类方法，所以调用方法时会选择调用分类中的方法（这里的分类不能是父类的分类）。

findMethodInSortedMethodList方法使用的就是二分向前查找算法

针对该算法分析如下：
假设count = 8，first = 0分别查找1、3、7这三个数：

查找1：

第一步：
count = 8
probe = 0 + 4 = 4
第二步：
count = 4
probe = 0 + 2 = 2
第三步：
count = 2
probe = 0 + 1 = 1
keyValue == probeValue -----return

查找3：

第一步：
count = 8
probe = 0 + 4 = 4
第二步：
count = 4
probe = 0 + 2 = 2
keyValue > probeValue
base = 2 + 1 = 3
count = 3
第三步：
count = 1
probe = 3 + 0 = 3
keyValue == probeValue -----return

查找7：

第一步：
count = 8
probe = 0 + 4 = 4
keyValue > probeValue
base = 4 + 1 = 5
count = 7
第二步：
count = 3
probe = 5 + 1 = 6
keyValue > probeValue
base = 6 + 1 = 7
count = 2
第三步：
count = 1
probe = 7 + 0 = 7
keyValue == probeValue -----return

四、动态方法决议（动态解析）

如果lookUpImpOrForward方法中找不到方法在本类和父类中的实现，那么就会回进入resolveMethod_locked方法进行动态方法决议。

// No implementation found. Try method resolver once.
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

^异或运算、&与运算参考逻辑运算介绍

4.1 resolveMethod_locked

static NEVER_INLINE IMP
resolveMethod_locked(id inst, SEL sel, Class cls, int behavior)
{
    runtimeLock.assertLocked();
    ASSERT(cls->isRealized());

    runtimeLock.unlock();

    if (! cls->isMetaClass()) {
        // try [cls resolveInstanceMethod:sel]
        resolveInstanceMethod(inst, sel, cls);
    } 
    else {
        // try [nonMetaClass resolveClassMethod:sel]
        // and [cls resolveInstanceMethod:sel]
        resolveClassMethod(inst, sel, cls);
        if (!lookUpImpOrNil(inst, sel, cls)) {
            resolveInstanceMethod(inst, sel, cls);
        }
    }

    // chances are that calling the resolver have populated the cache
    // so attempt using it
    return lookUpImpOrForward(inst, sel, cls, behavior | LOOKUP_CACHE);
}

resolveMethod_locked主要作用是判断类是否是元类

如果不是元类则进入resolveInstanceMethod继续处理
如果是元类则进入resolveClassMethod继续处理，并且通过lookUpImpOrNil判断非空，最后也会调用resolveInstanceMethod进行对象方法的动态解析，因为根据isa走位图，万物皆对象，最终都会继承自NSObject，都会找到NSObject的对象方法中。

示例代码：

@interface LGPerson : NSObject
- (void)sayMaster;
@end

@implementation LGPerson
- (void)sayMaster{
    NSLog(@"%s",__func__);
}

+ (BOOL)resolveInstanceMethod:(SEL)sel {
    if (sel == @selector(say666)) {
        NSLog(@"%@ 来了",NSStringFromSelector(sel));
        
//        IMP imp           = class_getMethodImplementation(self, @selector(sayMaster));
//        Method sayMMethod = class_getInstanceMethod(self, @selector(sayMaster));
//        const char *type  = method_getTypeEncoding(sayMMethod);
//        return class_addMethod(self, sel, imp, type);
    }
    
    return [super resolveInstanceMethod:sel];
}
@end

方法调用：
LGPerson *person = [LGPerson alloc];
[person say666];

打印结果如下：

 say666 来了
 say666 来了
 -[LGPerson say666]: unrecognized selector sent to instance 0x1007ab250

为什么会打印两次？
第一次是因为lookUpImpOrForward调用，第二次是因为methodSignatureForSelector方法调用后又进行了一次慢速查找，如果resolveInstanceMethod :方法中返回了方法的实现就不会进行消息转发也就不会再进行慢速查找了。（在下面resolveInstanceMethod方法中断点打印堆栈信息即可验证）

+(BOOL)resolveInstanceMethod:(SEL)sel方法中放开注释打印结果如下：

 say666 来了
 -[LGPerson sayMaster]

注意两次打印结果的区别

4.2 resolveInstanceMethod

static void resolveInstanceMethod(id inst, SEL sel, Class cls)
{
    runtimeLock.assertUnlocked();
    ASSERT(cls->isRealized());
    SEL resolve_sel = @selector(resolveInstanceMethod:);

    if (!lookUpImpOrNil(cls, resolve_sel, cls->ISA())) {
        // Resolver not implemented.
        return;
    }

    BOOL (*msg)(Class, SEL, SEL) = (typeof(msg))objc_msgSend;
    bool resolved = msg(cls, resolve_sel, sel);方法调用

    // Cache the result (good or bad) so the resolver doesn't fire next time.
    // +resolveInstanceMethod adds to self a.k.a. cls
    IMP imp = lookUpImpOrNil(inst, sel, cls);断点bt打印堆栈信息即可发现两次方法调用的流程

    if (resolved  &&  PrintResolving) {
        if (imp) {
            _objc_inform("RESOLVE: method %c[%s %s] "
                         "dynamically resolved to %p", 
                         cls->isMetaClass() ? '+' : '-', 
                         cls->nameForLogging(), sel_getName(sel), imp);
        }
        else {
            // Method resolver didn't add anything?
            _objc_inform("RESOLVE: +[%s resolveInstanceMethod:%s] returned YES"
                         ", but no new implementation of %c[%s %s] was found",
                         cls->nameForLogging(), sel_getName(sel), 
                         cls->isMetaClass() ? '+' : '-', 
                         cls->nameForLogging(), sel_getName(sel));
        }
    }
}

该函数实质是做了一次方法的解析操作

初始化一个resolve_sel resolveInstanceMethod
然后查找该resolve_sel，找到后则继续处理，找不到就直接返回
通过objc_msgSend发送消息，这里发送的是resolveInstanceMethod消息，如果返回YES则说明该方法被实现，否则未实现。
如果实现并且解析处做了转发，说明该sel指向了新的imp，并通过下面的打印来说明新IMP被动态实现，或者没找到。

4.3 resolveClassMethod

static void resolveClassMethod(id inst, SEL sel, Class cls)
{
    runtimeLock.assertUnlocked();
    ASSERT(cls->isRealized());
    ASSERT(cls->isMetaClass());

    if (!lookUpImpOrNil(inst, @selector(resolveClassMethod:), cls)) {
        // Resolver not implemented.
        return;
    }

    Class nonmeta;
    {
        mutex_locker_t lock(runtimeLock);
        nonmeta = getMaybeUnrealizedNonMetaClass(cls, inst);
        // +initialize path should have realized nonmeta already
        if (!nonmeta->isRealized()) {
            _objc_fatal("nonmeta class %s (%p) unexpectedly not realized",
                        nonmeta->nameForLogging(), nonmeta);
        }
    }
    BOOL (*msg)(Class, SEL, SEL) = (typeof(msg))objc_msgSend;
    bool resolved = msg(nonmeta, @selector(resolveClassMethod:), sel);

    // Cache the result (good or bad) so the resolver doesn't fire next time.
    // +resolveClassMethod adds to self->ISA() a.k.a. cls
    IMP imp = lookUpImpOrNil(inst, sel, cls);

    if (resolved  &&  PrintResolving) {
        if (imp) {
            _objc_inform("RESOLVE: method %c[%s %s] "
                         "dynamically resolved to %p", 
                         cls->isMetaClass() ? '+' : '-', 
                         cls->nameForLogging(), sel_getName(sel), imp);
        }
        else {
            // Method resolver didn't add anything?
            _objc_inform("RESOLVE: +[%s resolveClassMethod:%s] returned YES"
                         ", but no new implementation of %c[%s %s] was found",
                         cls->nameForLogging(), sel_getName(sel), 
                         cls->isMetaClass() ? '+' : '-', 
                         cls->nameForLogging(), sel_getName(sel));
        }
    }
}

该函数跟resolveInstanceMethod差不多，唯一的区别就是发消息的时候是向元类发送消息。其余的就不在赘述了。

示例代码：

@interface LGPerson : NSObject
+ (void)sayNB;
+ (void)lgClassMethod;
@end

@implementation LGPerson
+ (void)lgClassMethod{
    NSLog(@"%s",__func__);
}
+ (BOOL)resolveClassMethod:(SEL)sel {
    if (sel == @selector(sayNB)) {
        NSLog(@"%@ 来了",NSStringFromSelector(sel));
        
        IMP imp           = class_getMethodImplementation(self, @selector(lgClassMethod));
        Method sayMMethod = class_getInstanceMethod(self, @selector(lgClassMethod));
        const char *type  = method_getTypeEncoding(sayMMethod);
        return class_addMethod(self, sel, imp, type);
    }
    
    return [super resolveInstanceMethod:sel];
}
@end

方法调用：
[LGPerson sayNB];

打印结果：

 sayNB 来了
 sayNB 来了
 +[LGPerson sayNB]: unrecognized selector sent to class 0x1000082f0

从打印结果来看还是没有找到sayNB方法的实现，但是+ (BOOL)resolveClassMethod:(SEL)sel方法却被调用了。
其原因就是+ (BOOL)resolveClassMethod:(SEL)sel方法将方法的实现添加进类中了，而类方法的实现是保存在元类中的

所以修改+ (BOOL)resolveClassMethod:(SEL)sel方法如下：

+ (BOOL)resolveClassMethod:(SEL)sel {
    if (sel == @selector(sayNB)) {
        NSLog(@"%@ 来了",NSStringFromSelector(sel));
        
        IMP imp           = class_getMethodImplementation(objc_getMetaClass("LGPerson"), @selector(lgClassMethod));
        Method sayMMethod = class_getInstanceMethod(objc_getMetaClass("LGPerson"), @selector(lgClassMethod));
        const char *type  = method_getTypeEncoding(sayMMethod);
        return class_addMethod(objc_getMetaClass("LGPerson"), sel, imp, type);
    }
    
    return [super resolveInstanceMethod:sel];
}

打印结果：
sayNB 来了
+[LGPerson lgClassMethod]

也可以在NSObject中的分类中添加类方法或实例方法的实现都能解决问题，因为添加类方法就是通过继承的关系找到，添加实例方法就通过元类的实例方法找到。

4.4 消息转发

如果没有做动态解析处理，最后会来到消息转发，这也是为什么一开始会在lookUpImpOrForward函数中初始化一个_objc_msgForward_impcache的IMP，然后填充到cls的cache里面。到此我们的消息慢速查找流程就结束了，那么什么是消息的转发机制呢，我们后续再详细讲解。

五、总结

消息的查找有快速流程通过objc_msgSend通过cache查找、慢速流程lookUpImpOrForward进行查找；
从快速查找进入慢速查找一开始是不会进行动态方法解析，而是直接从方法列表进行二分向前查找；
查找前会做好准备，确保类信息完整
首先从当前类的方法列表进行查找，找到就可返回(并缓存)
如果没找到则去父类的缓存进行查找，如果找不到则查找父类的方法列表，找到就可返回(并缓存)，找不到就继续向父类的父类进行查找，直到NSObject；
如果还是没找到就根据当前类是否是元类进行方法的动态解析，解析成功则返回，如果失败就会进入消息转发流程。

慢速方法查找流程:
1、找自己的methodlist
2、找父类的methodlist
3、imp：forward
4、消息处理机制：动态方法决议-对象方法、类方法

消息的转发机制快速转发、慢速转发

参考

iOS Objective-C消息查找流程

iOS-底层探索09：方法的慢速查找流程分析

目录

一、前言

二、一个方法查找流程的问题

三、方法慢速查找流程分析

四、动态方法决议（动态解析）

4.1 resolveMethod_locked

4.2 resolveInstanceMethod

4.3 resolveClassMethod

4.4 消息转发

五、总结

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

V10（逻辑教育）

iOS-底层探索09：方法的慢速查找流程分析

目录

一、前言

二、一个方法查找流程的问题

三、方法慢速查找流程分析

四、动态方法决议（动态解析）

4.1 resolveMethod_locked

4.2 resolveInstanceMethod

4.3 resolveClassMethod

4.4 消息转发

五、 总结

参考

相关文章

网友评论

延伸阅读

深度阅读

栏目导航

热点阅读

V10（逻辑教育）

五、总结