方法慢速查找过程分析

前言

书接上回objc_msgSend流程分析，我们知道了消息发送首先会去cache_t中缓存的方法列表中查找，其实这是方法快速查找的过程，如果缓存中未找到，就会进入慢速查找流程，那么慢速查找的具体流程是怎么处理的呢？下面将给大家大致分析一下。

慢速查找入口

首先，必须找到入口，我们才能进入分析，那么入口在哪里呢？在objc_msgSend流程分析一文中，在CacheLookup汇编过程中扔未找到SEL的话，最终都会走到__objc_msgSend_uncached，这个就是入口。

然后，在源码工程中全局搜索__objc_msgSend_uncached，截图如下：

uncached.png
找到STATIC_ENTRY，这是汇编入口，我们只看arm64情况下，汇编代码如下:

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和 TailCallFunctionPointer，先全局搜索TailCallFunctionPointer，如下图：

TailCallFunctionPointer.png
只是读取一个地址值，看不出其它内容，那么我们只能再搜索MethodTableLookup，如下图：
MethodTableLookup.png
同样只看arm64情况，找到定义.macro，源码如下：

.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

    // 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

.endmacro

我们观察，前后两大部分全是寄存器变量的处理，可以不管，中间有一句关键代码bl _lookUpImpOrForward，再全局搜索_lookUpImpOrForward，如下图：

_lookUpImpOrForward.png
只有这一个地方，怎么办？既然汇编层没有，我们再找上一层c/c++，干掉下划线，全局搜索lookUpImpOrForward，如下图：
lookUpImpOrForward.png
objc-runtime-old.mm不管，在objc-runtime-new.mm中查到了方法的定义
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)，至此，我们终于到了，lookUpImpOrForward就是慢速查找的入口函数！

上述查找的流程大致如下：
objc_msgSend --> __objc_msgSend_uncached --> MethodTableLookup --> _lookUpImpOrForward汇编层 --> lookUpImpOrForward c/c++层

lookUpImpOrForward 流程

接下来我们重点分析一下lookUpImpOrForward的流程处理，由于函数代码很多，按照以往惯例，我们分段分析。(省略部分注释。。。)

section1-- 准备工作

    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    IMP imp = nil;
    Class curClass;

    runtimeLock.assertUnlocked();

    
    if (fastpath(behavior & LOOKUP_CACHE)) {
        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();

• 一些变量，锁的声明
• imp = cache_getImp(cls, sel);再次的查找缓存，why？因为可能存在多线程的情况，可能在调用的同时，别的线程在缓存，所以再去读一次缓存，多给一次取缓存的机会。
• checkIsKnownClass(cls);字面意思-->检查是否是已知的类，类里面有啥信息？当然是方法列表，属性列表，协议等，将这些信息加载到内存后，肯定是为了方便从缓存读取，更加方便，速度更快。
• 第一个if slowpath(!cls->isRealized())，跟进realizeClassMaybeSwiftAndLeaveLocked-->realizeClassMaybeSwiftMaybeRelock-->realizeClassWithoutSwift
  • realizeClassWithoutSwift源码很长，只看关键代码

static Class realizeClassWithoutSwift(Class cls, Class previously)
{
    // 省略部分代码。。。
    cls->superclass = supercls;
    cls->initClassIsa(metacls);

    // 省略部分代码。。。

    // Connect this class to its superclass's subclass lists
    if (supercls) {
        addSubclass(supercls, cls);
    } else {
        addRootClass(cls);
    }

    // Attach categories
    methodizeClass(cls, previously);

    return cls;
}

从cls->superclass = supercls;和addSubclass(supercls, cls);可以看出，既给子类cls的父类superclass赋值，又在父类supercls中addSubclass添加子类，就像是个双向链表，子类指向父类，父类又指向子类，这明显是在确立继承关系。

• 再看第二个if(behavior & LOOKUP_INITIALIZE) && !cls->isInitialized()) -->initializeAndLeaveLocked-->initializeAndMaybeRelock，大致意思是，若cls未初始化，那么初始化，不做深究。

section2-- for无限循环

    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)) {
            // 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);
        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;
        }
    }

1. curClass = cls;-->curClass指向当前已经确定好继承链的cls
2. for (unsigned attempts = unreasonableClassCount();;)是一种无限循环
3. Method meth = getMethodNoSuper_nolock(curClass, sel); -->在当前类找

static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
    runtimeLock.assertLocked();

    ASSERT(cls->isRealized());
    // fixme nil cls? 
    // fixme nil sel?

    // 遍历methodList --> 二分查找
    auto const methods = cls->data()->methods();
    for (auto mlists = methods.beginLists(),
              end = methods.endLists();
         mlists != end;
         ++mlists)
    {
        // <rdar://problem/46904873> getMethodNoSuper_nolock is the hottest
        // caller of search_method_list, inlining it turns
        // getMethodNoSuper_nolock into a frame-less function and eliminates
        // any store from this codepath.
        method_t *m = search_method_list_inline(*mlists, sel);
        if (m) return m;
    }

    return nil;
}

3.1. auto const methods = cls->data()->methods();获取方法列表
3.2. for (auto mlists = methods.beginLists(), end = methods.endLists(); mlists != end; ++mlists)从头到尾开始遍历

• search_method_list_inline(*mlists, sel);查找方法 --> findMethodInSortedMethodList

ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
    ASSERT(list);

    // first指向list首地址
    const method_t * const first = &list->first;
    // base先指向first
    const method_t *base = first;
    // probe表示list元素method_t *，就是指向方法的指针
    const method_t *probe;
    // keyValue表示当前要寻找方法的指针
    uintptr_t keyValue = (uintptr_t)key;
    // for循环的条件
    uint32_t count;
    // count指向方法列表最大个数值
    for (count = list->count; count != 0; count >>= 1) {
        // count右移1位 =count除2，那么probe先指向中间位置
        probe = base + (count >> 1);
        // probeValue-->当前中间位置的方法地址，因为method_t结构体中name是第一个成员，那么name的地址就是method_t的地址
        uintptr_t probeValue = (uintptr_t)probe->name;
        // 方法找到时
        if (keyValue == probeValue) {
            // keyValue == (uintptr_t)probe[-1].name--> probe前面的位置的那么也和keyValue相同
            // 分类中的方法 存在和当前方法重名的情况 分类中方法列表在本类的方法列表之后
            // 所以while循环的条件是-->直到前面的方法不重名时，即第一个时，就退出循环
            // 扩展：多个分类的加载顺序是由分类文件编译的顺序决定的
            while (probe > first && keyValue == (uintptr_t)probe[-1].name) {
                probe--;
            }
            return (method_t *)probe;
        }
        // 为什么不判断小于呢？-->其实方法method_t在列表list中的地址是按照从小到大的顺序排列的，先插入的地址小于后插入的地址，所以小于的话，说明当前的probeValue对应的method_t在后面，所以继续循环，count继续除2，再一次对半分，让probe指针向前移动
        // 如果keyValue 大于 probeValue，就往probe即中间位置的右边查找
        if (keyValue > probeValue) {
            // for循环的起始指针base移到probe后面的method_t的地址位置
            base = probe + 1;
            // count自减1，假如count初始值为8，第一次循环时，probe = base + (count>>1 --> 8>>1 = 4)是指向base+4的位置，
            // 第二次循环count >>=1 --> 7>>1=3再probe = base + (count >>1 --> 3>>1 = 1) -->probe = base+1 的位置-->此时base指向下标5，probe就指向下标为6的位置 --> 其实就是在第一次对半分后，在后面那1/2部分的里面再对半分
            count--;
        }
    }
    
    return nil;
}

在当前类找，遍历methods的算法，这是二分查找法，请看每一步都写的注释。自我理解，不对的地方请指正！如果找的到，那么goto done;（见section5）

3.3. 当前类找不到的话，那么就找缓存，注意是父类的缓存，why?注意下面的if
curClass = curClass->superclass -->curClass指向了当前cls的父类

if (slowpath((curClass = curClass->superclass) == nil)) {
    // No implementation found, and method resolver didn't help.
    // Use forwarding.
    imp = forward_imp;
    break;
}

4.imp = cache_getImp(curClass, sel);--> 查找父类的缓存，跟缓存相关的处理都是汇编代码：

STATIC_ENTRY _cache_getImp

    GetClassFromIsa_p16 p0
    CacheLookup GETIMP, _cache_getImp

LGetImpMiss:
    mov p0, #0
    ret

    END_ENTRY _cache_getImp

4.1.CacheLookup GETIMP 注意条件是GETIMP，在缓存中查找时，查看CacheLookup汇编源码，未找到的话，最终进入JumpMiss $0，此时$0 == GETIMP-->LGetImpMiss-->mov p0, #0

5. 接着判断if (slowpath(imp == forward_imp))，是则退出循环
6. 如果没找到，继续循环，再进入父类的父类，直到nil，imp = forward_imp后退出循环，代码如下：

if (slowpath((curClass = curClass->superclass) == nil)) {
    // No implementation found, and method resolver didn't help.
    // Use forwarding.
    imp = forward_imp;
    break;
}

6.如果找到了if (fastpath(imp))，去goto done（见section5）。

section 4-- 最后给一次机会

if (slowpath(behavior & LOOKUP_RESOLVER)) {
    behavior ^= LOOKUP_RESOLVER;
    return resolveMethod_locked(inst, sel, cls, behavior);
}

1. behavior初始值是LOOKUP_INITIALIZE | LOOKUP_RESOLVER 详见汇编MethodTableLookup，显然能满足判断条件，接着behavior ^= LOOKUP_RESOLVER那么此时behavior = LOOKUP_INITIALIZE
2. 接着resolveMethod_locked(inst, sel, cls, behavior)，这是动态方法决议。

动态方法决议流程源码

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

3.判断当前cls是否元类cls->isMetaClass()
4.不是元类，则resolveInstanceMethod(inst, sel, cls)
5.是元类，则resolveClassMethod(inst, sel, cls);-->!lookUpImpOrNil(inst, sel, cls)-->未找到时resolveInstanceMethod(inst, sel, cls)
6.最后lookUpImpOrForward(inst, sel, cls, behavior | LOOKUP_CACHE)，此时behavior = LOOKUP_INITIALIZE | LOOKUP_CACHE

7. 再次进入lookUpImpOrForward，执行到if判断behavior & LOOKUP_RESOLVER时，就不满足条件了，所以resolveMethod_locked只有一次机会

疑问：为什么元类的时候，判断完resolveClassMethod的实现后，还要再判断resolveInstanceMethod？

带着上面的问题，我们先看看resolveInstanceMethod 核心代码如下

static void resolveInstanceMethod(id inst, SEL sel, Class cls)
{
    // 省略部分ASSERT
    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);

    IMP imp = lookUpImpOrNil(inst, sel, cls);

    if (resolved  &&  PrintResolving) {
       // 省略部分代码
    }
}

1. bool resolved = msg(cls, resolve_sel, sel); -->向当前类cls中objc_msgSend发送消息resolveInstanceMethod-->当前类cls是否实现了方法resolveInstanceMethod
2. IMP imp = lookUpImpOrNil(inst, sel, cls);-->缓存查找resolveInstanceMethod的结果，下一次消息发送的时候，就不用走到这一步了

再看看resolveClassMethod，核心源码如下

static void resolveClassMethod(id inst, SEL sel, Class cls)
{
    // 省略部分ASSERT

    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) {
       // 省略部分代码。。。
    }
}

1. !lookUpImpOrNil(inst, @selector(resolveClassMethod:), cls)-->元类cls未实现resolveClassMethod，直接return
2. nonmeta是未被系统实现的元类，那么先getMaybeUnrealizedNonMetaClass初始化元类，暂不深究
3. 同理，发送消息 bool resolved = msg(cls, @selector(resolveClassMethod:), sel); -->向当前元类cls中objc_msgSend发送消息resolveClassMethod-->当前远类cls是否实现了方法resolveClassMethod
4. IMP imp = lookUpImpOrNil(inst, sel, cls);-->缓存查找resolveClassMethod的结果，下一次消息发送的时候，就不用走到这一步了

问题答案：

1. 在isa走位图中，元类的继承链关系，元类的父类最终是根元类，根元类的父类是NSObject，所以元类未实现resolveClassMethod的话，向上找父类，最终找到了根类NSObject。
2. 然后类方法存储在元类中，但是类方法对于元类自身来说，其实也是实例方法，所以最终会走到NSObject的resolveInstanceMethod方法里。

section 5-- 找到后goto done

done:
    log_and_fill_cache(cls, imp, sel, inst, curClass);

static void
log_and_fill_cache(Class cls, IMP imp, SEL sel, id receiver, Class implementer)
{
#if SUPPORT_MESSAGE_LOGGING
    if (slowpath(objcMsgLogEnabled && implementer)) {
        bool cacheIt = logMessageSend(implementer->isMetaClass(), 
                                      cls->nameForLogging(),
                                      implementer->nameForLogging(), 
                                      sel);
        if (!cacheIt) return;
    }
#endif
    cache_fill(cls, sel, imp, receiver);
}

cache_fill再熟悉不过，缓存方法。至此，lookUpImpOrForward流程结束！

总结

我们首先在objc_msgSend流程中发现，如果在当前类的cache_t中未找到方法实现，则会走到汇编__objc_msgSend_uncached，这是慢速查找的开始，再跟进汇编搜索到慢速查找的入口函数lookUpImpOrForward，然后大致分析了慢速查找的流程，大致是：

加载类信息(方法列表，属性列表，协议列表等)-->确认当前类的继承链-->for循环：先找自己（二分查找法）-->未找到则再找父类...根类->未找到进入动态方法决议

大致流程图如下：

慢速查找.jpg