OC 消息查找流程

上一篇 OC 方法的本质中提到OC的方法调用依赖于runtime实现的api(objc_msgSend、objc_msgSendSuper等等) 提供消息发送功能实现的。

objc_msgSend是最常见的，也是使用频率最高的消息发送的函数，这里就拿objc_msgSend举例

消息查找入口 objc_msgSend

objc_msgSend在源码中是用汇编实现的，原因应该是 objc_msgSend的使用频率非常高，几乎所有的oc方法的调用都会使用，所以对速度的要求非常高；这个角度看objc_msgSend使用汇编实现就可以理解了。

objc_msgSend包含了快速查找和慢速查找，快速查找如果未命中缓存,则进行慢速查找。

快速查找CacheLookup

快速查找流程在汇编宏CacheLookup中，所谓快速查找就是从cache中查找IMP。

CacheLookup流程分析

准备工作

    ldp p10, p11, [x16, #CACHE] // p10 = buckets, p11 = occupied|mask
#if !__LP64__
    and w11, w11, 0xffff    // p11 = mask
#endif
    and w12, w1, w11        // x12 = _cmd & mask
    add p12, p10, p12, LSL #(1+PTRSHIFT)
                     // p12 = buckets + ((_cmd & mask) << (1+PTRSHIFT))

    ldp p17, p9, [x12]      // {imp, sel} = *bucket

这部分代码是为查找做准备
拿到buckets、occupied、mask
使用_cmd & mask计算出 index，并偏移到index指向的bucket
把 p17、p9分别设置为 imp，sel

判断是否命中

1:  cmp p9, p1          // if (bucket->sel != _cmd)
    b.ne    2f          //     scan more
    CacheHit $0         // call or return imp

如果p9 != p1,跳转到标号2
如果找到则继续执行CacheHit，call or return imp

查找下一个bucket

2:  // not hit: p12 = not-hit bucket
    CheckMiss $0            // miss if bucket->sel == 0
    cmp p12, p10        // wrap if bucket == buckets
    b.eq    3f
    ldp p17, p9, [x12, #-BUCKET_SIZE]!  // {imp, sel} = *--bucket
    b   1b          // loop

当前 $0 是 NORMAL
CheckMiss判断当前p12的bucket的sel是否存在，如果存在就进行下一步对比，如果不存在就会进入未命中缓存流程__objc_msgSend_uncached
如果bucket->sel存在，则判断是否回到了开始查找过缓存的bucket,如果回到了起点则跳转到标号3，如果未回到起点则跳转到标号1 loop就此形成

未命中缓存处理

3:  // double wrap
    JumpMiss $0

标号3是对未命中缓存进行处理
JumpMiss NORMAL就会进入未命中缓存处理__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 p16 is the class to search
    
    MethodTableLookup
    TailCallFunctionPointer x17

    END_ENTRY __objc_msgSend_uncached

__objc_msgSend_uncached 对未命中缓存的情况进行处理
这里主要做了两件事 1.执行宏MethodTableLookup ，2. 尝试调用查找结果TailCallFunctionPointer
MethodTableLookup是从方法列表中查找（相对比较慢，所以称之为慢速查找）

慢速查找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)]

    // receiver and selector already in x0 and x1
    mov x2, x16
    bl  __class_lookupMethodAndLoadCache3

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

这里就是调用了 __class_lookupMethodAndLoadCache3
其它的是一些准备工作，因为__class_lookupMethodAndLoadCache3最终实现是c函数 _class_lookupMethodAndLoadCache3，所以准备工作比较繁杂。

_class_lookupMethodAndLoadCache3 调度

IMP _class_lookupMethodAndLoadCache3(id obj, SEL sel, Class cls)
{
    return lookUpImpOrForward(cls, sel, obj, 
                              YES/*initialize*/, NO/*cache*/, YES/*resolver*/);
}

_class_lookupMethodAndLoadCache3是一个调度函数
如果查找的对象方法那obj 就是实例对象，cls就是类对象
如果查找的类方法那obj 就是类对象，cls就是元类对象
cache = NO从消息快速查找过来不需要去检查缓存
initialize = YES 不避免调用 +initiallize
resolver = YES 如果未找到，则进行方法解析

lookUpImpOrForward

IMP lookUpImpOrForward(Class cls, SEL sel, id inst, 
                       bool initialize, bool cache, bool resolver)
{
    IMP imp = nil;
    bool triedResolver = NO;  //已经经过方法解析标记

    //如果cache = YES，就进行缓存检查
    //从快速查找过来cache = NO，就不需要进行缓存检查
    if (cache) {
        imp = cache_getImp(cls, sel);
        if (imp) return imp;
    }

    /*
      加锁，有可能有多个线程进行消息查找
    */
    runtimeLock.lock();
    //判断是否是已知的class
    checkIsKnownClass(cls);
    
    /*
     如果cls未实现，则连同父类一起实现
     cls实现的就是 ro 和 rw 相关内容，我前面有相关内容就不展开
    */
    if (!cls->isRealized()) {
        cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
    }
    
    /*
     cls初始化，最终会调+initialize
     从快速查找过来 initialize = YES，表示不避免调用 +initialize
     如果 !cls->isInitialized() cls没有初始化就执行 +initialize
    */
    if (initialize && !cls->isInitialized()) {
        cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
    }

 retry: 
    runtimeLock.assertLocked();

    //尝试从cls->cache中查找imp，如果找到 return imp
    imp = cache_getImp(cls, sel);
    if (imp) goto done;

    // 尝试从cls中查找方法
    {
        Method meth = getMethodNoSuper_nolock(cls, sel);
        if (meth) {
            /*
            如果找到
            1.加入到缓存中，最终调用cache_fill（之前的 cache_t中有描述）
            2.将imp赋值为查找到的meth->imp
            3.跳转到 done标记
            */
            log_and_fill_cache(cls, meth->imp, sel, inst, cls);
            imp = meth->imp;
            goto done;
        }
    }

    // 尝试从父类中的 缓存中或者 方法列表中查找
    //遍历cls的所有superclass，直到superclass = nil位置 （也就是到基类或者根元类）
    {
        unsigned attempts = unreasonableClassCount();
        for (Class curClass = cls->superclass;
             curClass != nil;
             curClass = curClass->superclass)
        {
            // Superclass cache.
            imp = cache_getImp(curClass, sel);
            if (imp) {
                if (imp != (IMP)_objc_msgForward_impcache) {

                    log_and_fill_cache(cls, imp, sel, inst, curClass);
                    goto done;
                }
                else {
                    // Found a forward:: entry in a superclass.
                    // Stop searching, but don't cache yet; call method 
                    // resolver for this class first.
                    break;
                }
            }
            
            // 查找遍历的curClass中的方法列表
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {
                log_and_fill_cache(cls, meth->imp, sel, inst, curClass);
                imp = meth->imp;
                goto done;
            }
        }
    }

    //没有找到实现， 尝试方法动态解析
    if (resolver  &&  !triedResolver) {
        runtimeLock.unlock();
        resolveMethod(cls, sel, inst);
        runtimeLock.lock();
        // Don't cache the result; we don't hold the lock so it may have 
        // changed already. Re-do the search from scratch instead.
        triedResolver = YES;
        goto retry;
    }

    // No implementation found, and method resolver didn't help. 
    // Use forwarding.
    // 没有找到实现, 而且方法解析也没有帮助. 
    // 使用消息转发.
    imp = (IMP)_objc_msgForward_impcache;
    cache_fill(cls, sel, imp, inst);

 done:
    runtimeLock.unlock();  //解锁

    return imp;
}

_objc_msgForward_impcache的用途是消息转发,这里主要了解消息查找流程暂时不展开

getMethodNoSuper_nolock

static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
    for (auto mlists = cls->data()->methods.beginLists(), 
              end = cls->data()->methods.endLists(); 
         mlists != end;
         ++mlists)
    {
        method_t *m = search_method_list(*mlists, sel);
        if (m) return m;
    }
    return nil;
}

getMethodNoSuper_nolock遍历cls->methods存放到 mlists中
通过search_method_list函数查找sel对应的method
search_method_list主要依赖于findMethodInSortedMethodList
findMethodInSortedMethodList使用二分法从list中查找method

未找到消息的处理

月有阴晴圆缺，人有旦夕祸福,如果方法未实现又该如何处理

动态方法解析

    //没有找到实现， 尝试方法动态解析
    if (resolver  &&  !triedResolver) {
        runtimeLock.unlock();
        resolveMethod(cls, sel, inst);
        runtimeLock.lock();
        // Don't cache the result; we don't hold the lock so it may have 
        // changed already. Re-do the search from scratch instead.
        triedResolver = YES;
        goto retry;
    }

resolver入参，是否使用方法动态解析
triedResolver表示是否已经尝试过动态解析
goto retry会跳转到 retry 标记执行，再次尝试消息查找
从goto retry的意图来看，难道resolveMethod会给cls添加sel?

resolveMethod

void _class_resolveMethod(Class cls, SEL sel, id inst)
{
    if (! cls->isMetaClass()) {
        // try [cls resolveInstanceMethod:sel]

        _class_resolveInstanceMethod(cls, sel, inst);
    } 
    else {
        // try [nonMetaClass resolveClassMethod:sel]
        // and [cls resolveInstanceMethod:sel]
        _class_resolveClassMethod(cls, sel, inst); 
        if (!lookUpImpOrNil(cls, sel, inst, 
                            NO/*initialize*/, YES/*cache*/, NO/*resolver*/)) 
        {
            // 对象方法解析
            _class_resolveInstanceMethod(cls, sel, inst);
        }
    }
}

调用流程分析

if (! cls->isMetaClass()) 判断是否是元类
如果非元类，尝试解析实例方法 _class_resolveInstanceMethod
如果元类，尝试解析类方法_class_resolveClassMethod
- 再次尝试查找imp
- 如果未找到imp，就对元类对象进行实例方法解析 _class_resolveInstanceMethod

类方法解析失败后会对元类对象进行_class_resolveInstanceMethod实例方法解析，因为元类的ISA()是根元类，所以在[NSObject resolveInstanceMethod:]中，既会有实例方法解析，也会有类方法解析。

_class_resolveInstanceMethod 实例方法解析

static void _class_resolveInstanceMethod(Class cls, SEL sel, id inst)
{
    /* 
    * SEL_resolveInstanceMethod = +[cls resolveInstanceMethod:]
    * +resolveInstanceMethod: 在NSObject中有默认是实现 +[NSObject resolveInstanceMethod:] return NO;
    * ! lookUpImpOrNil 判断有两种用途：
    1. 判断 cls->ISA() 中是否实现 +resolveInstanceMethod:
    2. 如果 +resolveInstanceMethod: 存在，那就再cache中存一份
    */
    if (! lookUpImpOrNil(cls->ISA(), SEL_resolveInstanceMethod, cls, 
                         NO/*initialize*/, YES/*cache*/, NO/*resolver*/)) 
    {
        // Resolver not implemented.
        return;
    }

    /*
    * 系统给了一次机会 - 是否对 sel 进行处理
    * 给 +[cls resolveInstanceMethod:] 发送消息，询问是否已经解决
    * 因为前一个 lookUpImpOrNil 的原因，+[cls resolveInstanceMethod:] 走的是快速查找流程
    */
    BOOL (*msg)(Class, SEL, SEL) = (typeof(msg))objc_msgSend;
    bool resolved = msg(cls, SEL_resolveInstanceMethod, sel);

    /*
    * lookUpImpOrNil 再次尝试查找sel，在cache中存一份
    * 如果在前一步 +resolveInstanceMethod 中解决了 sel的问题，可以防止再次触发方法解析
    */
    IMP imp = lookUpImpOrNil(cls, sel, inst, 
                             NO/*initialize*/, YES/*cache*/, NO/*resolver*/);

   //省略了一些日志代码
}

+resolveInstanceMethod 可以对实例方法进行动态解析

_class_resolveClassMethod 类方法解析

static void _class_resolveClassMethod(Class cls, SEL sel, id insst)
{
    /* 
    * SEL_resolveClassMethod = +[cls resolveClassMethod:]
    * +resolveClassMethod: 在NSObject中有默认是实现 +[NSObject resolveClassMethod:] return NO;
    * ! lookUpImpOrNi 判断有两种用途：
    1. 判断 cls 中是否实现 +resolveClassMethod:
    2. 如果 +resolveClassMethod: 存在，那就再cache中存一份
    */
    if (! lookUpImpOrNil(cls, SEL_resolveClassMethod, inst, 
                         NO/*initialize*/, YES/*cache*/, NO/*resolver*/)) 
    {
        // Resolver not implemented.
        return;
    }

    /*
    * 系统给了一次机会 - 是否对 sel 进行处理
    * 这里和实例方法有一些区别，这里cls是元类，inst是类对象
    * _class_getNonMetaClass(cls, inst) 拿到类对象，向类对象发送消息
    * 给 +[cls SEL_resolveClassMethod:] 发送消息，询问是否已经解决
    * 因为前一个 lookUpImpOrNil 的原因，+[cls SEL_resolveClassMethod:] 走的是快速查找流程
    */
    BOOL (*msg)(Class, SEL, SEL) = (typeof(msg))objc_msgSend;
    bool resolved = msg(_class_getNonMetaClass(cls, inst), 
                        SEL_resolveClassMethod, sel);

        /*
    * lookUpImpOrNil 再次尝试查找sel，在cache中存一份
    * 如果在前一步 +resolveClassMethod 中解决了 sel的问题，可以防止再次触发方法解析
    */
    IMP imp = lookUpImpOrNil(cls, sel, inst, 
                             NO/*initialize*/, YES/*cache*/, NO/*resolver*/);

    //省略了一些日志代码
}

+resolveClassMethod 可以对类方法进行动态解析

这里值得注意的是 _class_getNonMetaClass(cls, inst)拿到的是类对象；我们的类方法不是保存在元类里面吗？那应该拿元类才对。
原因：
调用实例方法：msg(实例对象，sel)
调用类方法：msg(类对象，sel)

慢速查找流程梳理

查找cache中是否存在（优化）
checkIsKnownClass检查类是否是已知的类
如果cls未实现就调用realizeClassMaybeSwiftAndLeaveLocked实现（ro、rw）
如果cls未初始化就调用initializeAndLeaveLocked初始化（+initialize）
再次尝试从cache中查找（防止其它线程已经加入cache）
尝试从cls中查找方法，找到就调用log_and_fill_cache加入到cache中
遍历cls所有的superclass，尝试在superclass中查找方法，找到就加入到cache中
如果没有找到实现，就尝试进行动态方法解析
如果还没找到实现，就尝试进行消息转发