iOS-底层（10）：objc_msgSend流程分析之慢速查找

objc_msgSend 慢速查找流程分析

前一篇我们分析了汇编快速查找，如果没有找到，就会进入CheckMiss或者JumpMiss

.macro CheckMiss
    // miss if bucket->sel == 0
.if $0 == GETIMP
    cbz p9, LGetImpMiss
.elseif $0 == NORMAL
    cbz p9, __objc_msgSend_uncached
.elseif $0 == LOOKUP
    cbz p9, __objc_msgLookup_uncached
.else
.abort oops
.endif
.endmacro

.macro JumpMiss
.if $0 == GETIMP
    b   LGetImpMiss
.elseif $0 == NORMAL
    b   __objc_msgSend_uncached
.elseif $0 == LOOKUP
    b   __objc_msgLookup_uncached
.else
.abort oops
.endif
.endmacro

然后进入到__objc_msgSend_uncached，

STATIC_ENTRY __objc_msgSend_uncached
    UNWIND __objc_msgSend_uncached, FrameWithNoSaves

    // THIS IS NOT A CALLABLE C FUNCTION
    // Out-of-band p16 is the class to search
    
    MethodTableLookup //方法表中查找
    TailCallFunctionPointer x17

    END_ENTRY __objc_msgSend_uncached

MethodTableLookup

.macro MethodTableLookup
    
    // push frame
    SignLR
    stp fp, lr, [sp, #-16]!
    mov fp, sp

    // save parameter registers: x0..x8, q0..q7
    sub sp, sp, #(10*8 + 8*16)
    stp q0, q1, [sp, #(0*16)]
    stp q2, q3, [sp, #(2*16)]
    stp q4, q5, [sp, #(4*16)]
    stp q6, q7, [sp, #(6*16)]
    stp x0, x1, [sp, #(8*16+0*8)]
    stp x2, x3, [sp, #(8*16+2*8)]
    stp x4, x5, [sp, #(8*16+4*8)]
    stp x6, x7, [sp, #(8*16+6*8)]
    str x8,     [sp, #(8*16+8*8)]

    // lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
    // receiver and selector already in x0 and x1
    mov x2, x16
    mov x3, #3
    bl  _lookUpImpOrForward//跳转到_lookUpImpOrForward

    // IMP in x0
    mov x17, x0
    
    // restore registers and return
    ldp q0, q1, [sp, #(0*16)]
    ldp q2, q3, [sp, #(2*16)]
    ldp q4, q5, [sp, #(4*16)]
    ldp q6, q7, [sp, #(6*16)]
    ldp x0, x1, [sp, #(8*16+0*8)]
    ldp x2, x3, [sp, #(8*16+2*8)]
    ldp x4, x5, [sp, #(8*16+4*8)]
    ldp x6, x7, [sp, #(8*16+6*8)]
    ldr x8,     [sp, #(8*16+8*8)]

    mov sp, fp
    ldp fp, lr, [sp], #16
    AuthenticateLR

imp找不到会跳转到_lookUpImpOrForward, _lookUpImpOrForward没有.macro宏，说明跳转到c或者c++的代码中。我们可以通过汇编调试验证一下，添加断点，点击control + stepinto

打开debug--> Debug WorkFlow --> always show disassembly

image.png
断住objc_msgSend，继续control + stepInto, 断住_objc_msgSend_uncached，继续control + stepInto image.png

最后走到的是lookUpImpOrForward，这里并不是汇编实现，而是C/C++实现

• 在C/C++中调用汇编，在汇编的定义中要加一个 _ 下划线
• 在汇编中调用C/C++，C/C++的函数定义中要减一个 _ 下划线

慢速查找的C/C++部分

全局搜索lookUpImpOrForward,在最新的objc-runtime-new.mm找到，是一个C函数，我们来看代码，我加了相应的注释

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
        imp = cache_getImp(cls, sel);
        if (imp) goto done_nolock;
    }

    //线程加锁
    runtimeLock.lock();

    //检查是否是被认可的对象，已知类（或者是内置到二进制文件中，或者合法注册通过）
    checkIsKnownClass(cls);
    //如果类没有实现
    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.assertLocked();
    curClass = cls;

    //*unreasonableClassCount为类的任何迭代提供一个上限，在运行时元数据被破坏时防止自旋。
    //这是个无限循环，要使用break或goto来跳出循环
    for (unsigned attempts = unreasonableClassCount();;) {
        // curClass method list.
       // 本类进行一次imp查找
        Method meth = getMethodNoSuper_nolock(curClass, sel);
        if (meth) {
            imp = meth->imp;
            goto done;
        }

        // curClass向继承链传递赋值，当找到nil的时候让 imp = forward_imp, break，终止循环
        if (slowpath((curClass = curClass->superclass) == 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); 
        // 当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;
        }
        // 如果在父类中找到了，直接 goto done
        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:
    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;
}

总结一下上述过程：

1. 找一下缓存，排除多线程影响
2. 判断类是否被认可的类，已知类
3. 判断类是否已实现
4. 判断类是否已初始化
5. 进入for死循环，先进行一次本类的方法查找(二分查找)，让临时类curClass指向父类，通过汇编依次向上查找(cache_getImp)，直到curClass找到nil ，将imp赋值为_objc_msgForward_impcache，然后break跳出循环。
6. 进行一次动态方法决议，resolveMethod_locked 判断，resolveInstanceMethod和resolveInstanceMethod，是否有做处理，如果处理了，重新找一遍imp,若果没有处理，继续lookUpImpOrForward。
7. 消息快速转发,
8. 消息的慢速转发

上面是结合代码的描述过程，我只描述了关键部分，接下来我们来看一下流程图

2251862-8f3c817f232e953b.png

我们来看看二分查找算法的实现：

ALWAYS_INLINE static method_t *
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) {
        probe = base + (count >> 1);
        
        uintptr_t probeValue = (uintptr_t)probe->name;
        
        if (keyValue == probeValue) {
            //如果分类有相同方法，取分类的方法
            while (probe > first && keyValue == (uintptr_t)probe[-1].name) {
                probe--;
            }
            return (method_t *)probe;
        }
        
        if (keyValue > probeValue) {
            base = probe + 1;
            count--;
        }
    }
    
    return nil;
}

二分查找是一种非常高效的查找算法，它的时间复杂度是O(logn)，O(logn) 这种对数时间复杂度。这是一种极其高效的时间复杂度，因为 logn 是一个非常“恐怖”的数量级，即便 n 非常非常大，对应的 logn 也很小。比如 n 等于 2 的 32 次方，这个数很大了吧？大约是 42 亿。也就是说，如果我们在 42 亿个数据中用二分查找一个数据，最多需要比较 32 次。

我们再来看看动态方法决议

static NEVER_INLINE IMP
resolveMethod_locked(id inst, SEL sel, Class cls, int behavior)
{
    runtimeLock.assertLocked();
    ASSERT(cls->isRealized());
    // 给你一次机会,添加imp
    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)) {
        // 类方法在元类里就是实例方法，我们无法在元类里面写方法来处理，但是在NSObject里面是可以处理的，也就是实例方法
            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);
}

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.
        // resolve_sel 没有实现返回
        return;
    }
    //发送一次resolve_sel消息，也就是调用一次resolve_sel方法
    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
    // 再找一次sel的imp;
    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 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));
        }
    }
}

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是否实现，没有时间直接返回，如果有实现，发送消息resolveInstanceMethod，即调用我们自己处理的resolveInstanceMethod方法，然后进入慢速查找lookUpImpOrNil查找IMP，这里找到IMP只是为了打印消息，然后再进入lookUpImpOrNil查找IMP 返回IMP

动态方法决议的处理

#import "LGPerson.h"
#import <objc/message.h>

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

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


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


+ (BOOL)resolveInstanceMethod:(SEL)sel{
    NSLog(@"%@ 来了",NSStringFromSelector(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];
}

+ (BOOL)resolveClassMethod:(SEL)sel{
    NSLog(@"%@ 来了",NSStringFromSelector(sel));
    if (sel == @selector(sayNB)) {
         //注意这里类方法要添加到元类里面
        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 resolveClassMethod:sel];
}

在类方法查找imp的过程中，最终找到NSObject，那么我们想可以统一将动态方法决议写到NSObject的分类中

implementation NSObject (LG)

// 调用方法的时候 - 分类

+ (BOOL)resolveInstanceMethod:(SEL)sel{
    

    NSLog(@"%@ 来了",NSStringFromSelector(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);
    }
    else if (sel == @selector(sayNB)) {
        
        IMP imp           = class_getMethodImplementation(objc_getMetaClass("LGPerson"), @selector(lgClassMethod));
        Method sayMMethod = c lass_getInstanceMethod(objc_getMetaClass("LGPerson"), @selector(lgClassMethod));
        const char *type  = method_getTypeEncoding(sayMMethod);
        return class_addMethod(objc_getMetaClass("LGPerson"), sel, imp, type);
    }
    return NO;
}

/**
 
 1: 分类 - 便利
 2: 方法 - lg_model_tracffic
        - lg - model home - 奔溃 - pop Home
        - lg - mine  - mine
    切面 - SDK - 上传
 3: AOP - 封装SDK - 不处理
 4: 消息转发 - 
 
 */

@end

一般我们不在这一步做处理，因为有可能被子类拦截。我们继续探索动态方法决议之后还走了哪些

在源码中有打印消息发送的开关，我们在OC中使用要用extern 开放出来

extern void instrumentObjcMessageSends(BOOL flag);

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        instrumentObjcMessageSends(YES);
        LGPerson *person = [LGPerson alloc];
        [person sayHello];
        instrumentObjcMessageSends(YES);
        NSLog(@"Hello, World!");
    }
    return 0;
}

通过logMessageSend源码，消息发送打印信息存储在/tmp/msgSends/ 目录，如下所示我们找到打印文件：

image.png

• 发送了两次动态方法决议：resolveInstanceMethod方法
• 发送了两次消息快速转发：forwardingTargetForSelector方法
• 发送了两次消息慢速转发：methodSignatureForSelector + resolveInstanceMethod

我们在通过bt命令看一下调用堆栈

image.png

我们发现___forwardingTarget___在CoreFoundation框架中，但是这个框架苹果并没有开源，我们可以通过image list，读取整个镜像文件,然后搜索CoreFoundation，查看其可执行文件的路径，找到文件，通过hopper进行反汇编

image.png image.png
image.png image.png

判断是否可以响应，发送消息看是否有接收者。

- (id)forwardingTargetForSelector:(SEL)aSelector{
    NSLog(@"%s - %@",__func__,NSStringFromSelector(aSelector));

    // runtime + aSelector + addMethod + imp
    return [super forwardingTargetForSelector:aSelector];
}


- (NSMethodSignature *)methodSignatureForSelector:(SEL)aSelector{
    NSLog(@"%s - %@",__func__,NSStringFromSelector(aSelector));
    return nil;
}

- (void)forwardInvocation:(NSInvocation *)anInvocation{
    NSLog(@"%s - %@",__func__,anInvocation);
    // GM  sayHello - anInvocation - 漂流瓶 - anInvocation
    anInvocation.target = [LGStudent alloc];
    // anInvocation 保存 - 方法
    [anInvocation invoke];
}

2251862-71932fb077753303.jpg image.png

我们可以看到 汇编又调用了一次动态方法决议，这也是为什么resolveInstanceMethod走两遍的原因。

消息转发流程图

未命名文件.png