_lookUpImpOrForward慢速方法查找

前言

在《IOS底层原理之Runimte 运行时&方法的本质》一文中已经分析了objc_msgSend查找缓存（cache）的流程，也就是objc_msgSend的快速查找流程，当cache中找不到imp的时候，就会进入慢速查找的过程。

资料准备

• objc4-818.2 源码
• Objective-C Runtime

objc_msgSend_uncached流程实现

当在cache中没有找到目标方法时候，汇编会进入MissLabelDynamic流程，而MissLabelDynamic = __objc_msgSend_uncached,那么我们在源码中直接搜索__objc_msgSend_uncached，得到一下的实现代码：

    STATIC_ENTRY __objc_msgSend_uncached
    UNWIND __objc_msgSend_uncached, FrameWithNoSaves

    // THIS IS NOT A CALLABLE C FUNCTION
    // Out-of-band p15 is the class to search

    MethodTableLookup
    TailCallFunctionPointer x17

    END_ENTRY __objc_msgSend_uncached

以上就是短短的几行汇编代码，那么他做的是什么呢，主要是看MethodTableLookup和TailCallFunctionPointer方法的实现。x17又是什么呢？以下查看TailCallFunctionPointer方法的实现。(源码中全局搜索TailCallFunctionPointer)

TailCallFunctionPointer方法实现

    // A12 以上 iPhone X 以上的
    #if __has_feature(ptrauth_calls)
    ...
    #else
    ...
    .macro TailCallFunctionPointer
            // $0 = function pointer value
            br  $0
    .endmacro
    ...
    #endif

通过TailCallFunctionPointer的汇编实现流程并没有发现x17寄存器赋值的地方，那么猜想在MethodTableLookup方法中。（其实看MethodTableLookup方法名字就猜得出是干嘛的 --> 查询方法表）

MethodTableLookup方法实现

.macro MethodTableLookup
    
    SAVE_REGS MSGSEND

    // lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
    // receiver and selector already in x0 and x1
    mov x2, x16              //x16 = class赋值给了x2
    mov x3, #3               //x3 = 3
    bl  _lookUpImpOrForward  //跳转到_lookUpImpOrForward（objc_msgSend的慢速方法查找入口）
                             //bl跳转时候会保存吓一跳指令的位置到lr寄存器中，保存回家的路

    // IMP in x0
    mov x17, x0              //x0寄存器作为返回值的存储地方，保存的是_lookUpImpOrForward方法返回的imp
                             //那么x17 = imp

    RESTORE_REGS MSGSEND

.endmacro

MethodTableLookup方法内部实现主要是跳转到_lookUpImpOrForward方法（objc_msgSend的慢速查找流程），返回查找到的imp给x17。
注意：汇编中的_lookUpImpOrForward方法前面带下划线_，那么代表的是跳转到C++的方法中。

疑问：为什么_lookUpImpOrForward实现用的是C++，而之前说道查找cache的时候用的是汇编呢？

• 汇编更接近机器语言，查询速度更快。缓存查找流程是快速在缓存中找到方法，而慢速查找流程是不断的遍历methodlist过程，这个过程很慢
• 方法中有的参数是不确定的，但是在C语言中参数必须是确定的，而汇编可以让你感觉更加的动态化。

objc_msgSend_uncached总结

• 通过MethodTableLookup查询将查询到imp作为返回值存在x0寄存器，将x0寄存器的值赋值给x17寄存器
• 通过TailCallFunctionPointer x17直接调用x17寄存器中的imp，找到方法体并实现。
  -__objc_msgSend_uncached--> MethodTableLookup--> _lookUpImpOrForward -->TailCallFunctionPointer-->方法实现了。

objc_msgSend_uncached流程图

objc_msgSend_uncached流程

lookUpImpOrForward

lookUpImpOrForward方法是通过传进来的SEL来查找IMP的，那么具体怎样查询，请看看lookUpImpOrForward方法流程：

IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    //定义消息转发forward_imp  //behavior传进来的是3，代表LOOKUP_INITALIZE\LOOKUP_REDOLVER
    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    //返回的imp
    IMP imp = nil;
     //当前查找的cls
    Class curClass;

    runtimeLock.assertUnlocked();
    /*
     判断类是否已经初始化，没有初始化：behavior = LOOKUP_INITALIZE\LOOKUP_REDOLVER\LOOKUP_NOCACHE
     发送类的第一条消息通常是+new或者+alloc或者+self的初始化
     */
    if (slowpath(!cls->isInitialized())) {
       //修改behavior的状态
        behavior |= LOOKUP_NOCACHE;
    }
     //运行时上锁，防止多线程访问出现错乱的情况
    runtimeLock.lock();  
    checkIsKnownClass(cls);  //是否注册类-->是否被dyld加载的类，注册后的类会加入allocatedClasses表
    //实现初始化过程中需要的类-->初始化类和父类，为以后的查找做好准备。
    cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
    // runtimeLock may have been dropped but is now locked again
    runtimeLock.assertLocked();
    //赋值需要查找的类
    curClass = cls;

    //这是一个死循环，除非进入goto方法（return），或者break
    //在获取锁后，代码会再次查找类的缓存，在大多数情况下是不是命中的，因此浪费时间。
    //唯一没有执行某种缓存查找的路径就是class_getInstanceMethod()
    
    for (unsigned attempts = unreasonableClassCount();;) {
        //判断是否有共享缓存，一般指的是系统方法,如:NSLog等，自定义的方法一般不走
        if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
#if CONFIG_USE_PREOPT_CACHES
            /*
             再次查询共享缓存，因为在比查询的过成功其他线程调用了某个系统方法；
             因此共享缓存有机会存在目标方法
             */
            //缓存中根据sel查找imp
            imp = cache_getImp(curClass, sel);
            //如果查到目标imp，就跳到done_unlock，返回imp
            if (imp) goto done_unlock;
            curClass = curClass->cache.preoptFallbackClass();
#endif
        } else {
            // curClass method list.
            //在curClass中，使用二分法查找methodList
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            //如果找到了sel对应的方法
            if (meth) {
                //提出方法的imp
                imp = meth->imp(false);
                //跳转到done流程
                goto done;
            }
      ........
     //此处省略了一部分代码(主要是查找父类，进行以上几步的操作)
// No implementation found. Try method resolver once.
    //动态方法决议
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        //behavior = 3   LOOKUP_RESOLVER = 2
        //3^2 = 1
        behavior ^= LOOKUP_RESOLVER;
        //动态方法决议
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

 done:
    //behavior =3  LOOKUP_NOCACHE = 8
    //3 & 8 = 0b0011 & 0b1000 = 0b000 = 0,以下的判断成立
    if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) {
#if CONFIG_USE_PREOPT_CACHES
        while (cls->cache.isConstantOptimizedCache(/* strict */true)) {
            cls = cls->cache.preoptFallbackClass();
        }
#endif
        //将查询到sel和imp插入到当前类的缓存
        log_and_fill_cache(cls, imp, sel, inst, curClass);
    }
 done_unlock:
    //runtime解锁
    runtimeLock.unlock();
    /*
     如果behavior & LOOKUP_NIL成立的话，behavior != LOOKUP_NIL
     且imp == forword_imp,没有查询到直接返回nil
     */
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
    //返回查到的imp
    return imp;
}

分析得出lookUpImpOrForward大致以下的流程：

• 慢速查找流程
  • 判断cls（类）是否已经初始化，改变behavior的值。
  • 判断cls（类）是否已经注册，没有注册的话直接报错。
  • 是否实现cls（类），如果没有实现就会根据isa的走位链和继承链去初始化其父类（super class）和元类（metal class），以方便之后的查找。
• cls遍历查询
  • 判断是否有共享缓存，目的是有可能在查过过程中这个方法被调用缓存了，如果有的话直接从缓存中取，没有共享缓存则开始到本类中查询。
  • 在类中采用二分查找算法查找methodlist中的方法，如果找到插入缓存中，循环结束。
• 父类缓存中查询
  • 此时curClass = superclass，到父类的缓存中找，如果找到则插入到本类的缓存中。如果父类中返回的是forward_imp则跳出遍历，执行消息转发。
  • 如果没有在superclass的缓存中找到，那么curClass = superclass就会进入像上面cls循环查找methodlist的流程，直到curClass = nil，imp = forword_imp就进行消息的转发。
• 动态方法决议
  • 如果cls以及父类都没有查询到，此时系统会给你一次机会，判断是否执行过动态方法决议，如果没有则走动态方法决议。（下一篇文章详细分析哦）。
  • 如果动态决议方法执行过，imp = forward_imp会走done流程插入缓存，会走done_unlock流程 return imp进入消息转发阶段。

behavior

/* method lookup */
enum {
    LOOKUP_INITIALIZE = 1,
    LOOKUP_RESOLVER = 2,
    LOOKUP_NIL = 4,
    LOOKUP_NOCACHE = 8,
};

• LOOKUP_INITIALIZE： 控制是否去进行类的初始化。有值初始化，没有不初始化。
• LOOKUP_RESOLVER：是否进行动态方法决议。有值决议，没有值不决议。
  -LOOKUP_NIL：是否进行forward(消息转发)。有值不进行，没有值进行。
• LOOKUP_NOCACHE：是否插入缓存。有值不插入缓存，没有值插入。

lookUpImpOrForward 流程图

lookUpImpOrForward 流程图

realizeAndInitializeIfNeeded_locked -- 实现和实例化类

static Class
realizeAndInitializeIfNeeded_locked(id inst, Class cls, bool initialize)
{
    runtimeLock.assertLocked();
    //经验判断cls->isRealized()是小概率时事件，cls->isRealized()大概率是=YES
    //判断类是否实现，目的是实现isa走位图的isa走位链与继承链
    if (slowpath(!cls->isRealized())) {
        cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
        // runtimeLock may have been dropped but is now locked again
    }
    //判断类是否已经初始化，没有的话进入判断实现初始化
    if (slowpath(initialize && !cls->isInitialized())) {
        cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
        // runtimeLock may have been dropped but is now locked again

        // If sel == initialize, class_initialize will send +initialize and
        // then the messenger will send +initialize again after this
        // procedure finishes. Of course, if this is not being called
        // from the messenger then it won't happen. 2778172
    }
    return cls;
}

• realizeClassMaybeSwiftAndLeaveLocked方法中的realizeClassWithoutSwift就是去实现类的isa走位链和继承链中相关的类。
• initializeAndMaybeRelock的initializeNonMetaClass就是初始化类和父类的。

findMethodInSortedMethodList -- 二分法查找算法

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

    auto first = list->begin();   //第一个method的位置
    auto base = first;            //base = 第一个method的位置
    decltype(first) probe;        //中间值，拿来进行以下二分法运算的

    uintptr_t keyValue = (uintptr_t)key; //把key转化成uintptr_t类型，因为修复过后的method_list_t中的元素进行了排序
    uint32_t count;   //方法数组的个数
    /*
     count >>= 1 = count = count >> 1 =count = count/2(二分)
     假如:count = list->count = 8
     下一个循环的时候count >>= 1 = 7 >> 1 = 3;
     */
    
    for (count = list->count; count != 0; ) {
        probe = base + (count >> 1);  //第一次： probe = 0+8>>1 = 4
        //获取中间值的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) {
            base = probe + 1;   //base = 5，base 的开始位置为5，因为4已经比较过了，没必要了
            count--;    //count = 8 - 1 = 7,为了减少循环对比，以为count = 8的是否在第一轮已经比较过了
        }
    }
    //查询没有的话返回nil
    return nil;
}

注意：方法列表中的方法是经过修复的，意思就是按照sel大小进行过排序的。

• 二分法查找算法其实就是每次找到范围内的·中间位置和keyValue比较，如果相等直接返回查找到的方法（如果有分类方法就返回分类方法）
• 如果不相等则继续二分法查询，不断缩小查询的范围，如果最后还是没有查询到则返回nil。（count-- 目的就是过滤之前重复的判断）

二分法查找流程

如果上面代码看得比较不清晰的话，那么下面的流程如会给你梳理一遍，请看下图：

二分法流程（大于中间值）
二分法流程（小于中间值）
不难发现keyValue 大于 probeValue算法和keyValue 小于 probeValue，count的利用有一点区别，可以细细体会count的设计，小于的算法 count是作为上边界（就是我们平时理解的二分法），大于的算法，count的设计就很巧妙，不在作为上边界，主要看probe就可以了（排除了重复的循环，增强了效率）。

cache_getImp -- 快速查找

通过源码的查找，发现cache_getImp使用汇编语言实现了，代码如下：

    STATIC_ENTRY _cache_getImp

    GetClassFromIsa_p16 p0, 0
    CacheLookup GETIMP, _cache_getImp, LGetImpMissDynamic, LGetImpMissConstant

LGetImpMissDynamic:
    mov p0, #0
    ret

LGetImpMissConstant:
    mov p0, p2
    ret

    END_ENTRY _cache_getImp

• GetClassFromIsa_p16宏定义和我们开始在本类中查询缓存方法一样，但是参数不一样。
• 最终也是调用CacheLookup方法来进行查找。

GetClassFromIsa_p16

在《IOS底层原理之Runimte 运行时&方法的本质》一文中已经详细的分析了GetClassFromIsa_p16的实现流程，这里就简单的回顾一下：

.macro GetClassFromIsa_p16 src, needs_auth, auth_address 
/* note: auth_address is not required if !needs_auth */

#if SUPPORT_INDEXED_ISA  // armv7k or arm64_32
    ...//省略
1:

#elif __LP64__
.if \needs_auth == 0 // _cache_getImp takes an authed class already
    mov p16, \src
.else //needs_auth = 1 所以走下面的流程
    // 64-bit packed isa
        //把 \src 和 \auth_address 传进ExtractISA 得到的结果赋值给p16寄存器
    ExtractISA p16, \src, \auth_address  
.endif
#else
    // 32-bit raw isa
    mov p16, \src     //返回p16 = class

#endif

cacheLookup过程已经在上一文进行了详细的分析，这里就不详细分析。

• 如果缓存没有命中走LGetImpMissDynamic流程。
• 如果缓存命中Mode = GETIMP。

LGetImpMissDynamic:
    mov p0, #0
    ret

• 在缓存中没有找到所需方法的时候会令p0 = 0，imp = nil；
• 至于缓存命中的过程就不仔这里详细分析了，上一文中已经详细分析了。
  注意：缓存中获取imp是编码过的，此时imp ^ class =解码后的imp。

.macro AuthAndResignAsIMP
    // $0 = cache imp  , $1 = buckets的地址, $2 = SEL  $3 = class
        // $0 = $0 ^ $3 = imp ^ class = 解码后的imp  
    eor $0, $0, $3
.endmacro

实例查找

我们创建一个XXPerson类的实例，定义一个没有方法体的方法sayLost，然后分析崩溃之前的流程，请往下看：

出现了unrecognized崩溃信息，那么这个信息是在哪里发出来的呢？[perosn sayLost]也走了快速查找流程，慢速查找流程，动态方法决议，最后消息转发，最后还是没找到报unrecognized，全局搜索doesNotRecognizeSelector或者unrecognized selector sent to instance，在源码中搜索得出：

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

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

doesNotRecognizeSelector方法是怎么样走下去的，这个我们下篇文章会进行详细的分解。详细分析消息的转发流程。

补充

创建NSObject+XL分类，在分类中添加sayHello方法，并在分类中实现sayHello方法。然后进行如下得调用：

类调用对象方法调用成功了原因是什么？在oc底层没有所谓的实例方法和类方法，获取一个类方法实际上就是获取元类的实例方法，没找到找到根源类，根源类也没有，最后找到NSObject所以可以找到sayHello方法。

总结

和谐学习，不急不躁！知识使人快乐！！