第九节课 消息慢速查找

上篇文章我们分析了快速查找流程，并绘制了流程图，结尾处，当快速查找结束并没有找到想要的，这个时候我们就来到了慢速查找流程了。我们先来简单回顾下，然后再继续分析慢速查找流程

objc_mesgSend流程回顾

1: cmp    p0, #0

2: GetClassFromIsa_p16 p13, 1, x0    // p16 = class

3: CacheLookup NORMAL, _objc_msgSend, __objc_msgSend_uncached

3.1 : LLookupStart -> CACHE_MASK_STORAGE_HIGH_16

// 获取cache
ldr    p11, [x16, #CACHE]            // p11 = mask|buckets

CONFIG_USE_PREOPT_CACHES == 1

// p11 的 0 号位置是否为0  不为0 -> LLookupPreopt（共享缓存）
tbnz    p11, #0, LLookupPreopt\Function
and    p10, p11, #0x0000fffffffffffe    // p10 = buckets

// p1 sel >> 7 等价于 value ^= value >> 7;
//为什么右移7位？因为在mask_t cache_hash的读取的时候就是右移的7位，相互对应
eor    p12, p1, p1, LSR #7
// 哈希 index
//前48位是Bucket，后16位是mask，右移48位后得到mask
and    p12, p12, p11, LSR #48        // x12 = (_cmd ^ (_cmd >> 7)) & mask

// index << 4
// 2 * 16（左移4位相当于*16）
// buckets + 32
// 对应下标 : p13 第一个要查bucket(sel imp)
add    p13, p10, p12, LSL #(1+PTRSHIFT)
                    // p13 = buckets + ((_cmd & mask) << (1+PTRSHIFT))
// sel -> imp

                        // do {
//  *bucket--  p17, p9
//  bucket 里面的东西 imp (p17) sel (p9)
//  查到的 sel (p9) 和我们 say1
//  循环查找，直到Hit
1:  ldp p17, p9, [x13], #-BUCKET_SIZE   //     {imp, sel} = *bucket--
    cmp p9, p1              //     if (sel != _cmd) {
    b.ne    3f              //         scan more
                        //     } else {
2:  CacheHit \Mode              // hit:    call or return imp
                        //     }
3:  cbz p9, \MissLabelDynamic       //     if (sel == 0) goto Miss;
    cmp p13, p10            // } while (bucket >= buckets)
    b.hs    1b 
    
                        // do {
4:  ldp p17, p9, [x13], #-BUCKET_SIZE   //     {imp, sel} = *bucket--
    cmp p9, p1              //     if (sel == _cmd)
    b.eq    2b              //         goto hit
    cmp p9, #0              // } while (sel != 0 &&
    ccmp    p13, p12, #0, ne        //     bucket > first_probed)
    b.hi    4b

__objc_msgSend_uncached

此方法是进入慢速查找流程的起因，此方法是作为参数传递进CacheLookup的，如果CacheLookup查找不到imp的时候会执行MissLabelDynamic，也就是执行了__objc_msgSend_uncached

在objc-msg-arm64.s文件中查找__objc_msgSend_uncached的汇编实现，其中的核心是MethodTableLookup（即查询方法列表），其源码如下

    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
    // imp
    MethodTableLookup
    TailCallFunctionPointer x17

    END_ENTRY __objc_msgSend_uncached

MethodTableLookup

    SAVE_REGS MSGSEND

    // lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
    // receiver and selector already in x0 and x1
    //lookUpImpOrForward方法需要4个参数：
    //obj      = x0
    //sel      = x1
    //cls      = x2
    //behavior = x3 = 3
    mov x2, x16
    mov x3, #3
    //bl：跳转指令，并将回家的路存在x30寄存器（lr）
    bl  _lookUpImpOrForward

    // IMP in x0 --
    // 经过_lookUpImpOrForward拿到的返回值（IMP）将存在x0位置
    // 将x0赋值给x17
    mov x17, x0

    RESTORE_REGS MSGSEND

保存信息方法，已知x0是receiver，x1是_cmd,即sel，先将x16（LGPerson类）存在x2寄存器，将3存在x3寄存器，然后跳转至关键方法_lookUpImpOrForward，这个方法返回值在汇编的角度来看是储存在x0寄存器的，所以当_lookUpImpOrForward执行完成，将返回值x0存入x17.

TailCallFunctionPointer

//A12以上芯片（支持arm64e结构）
#if __has_feature(ptrauth_calls)
// JOP
.macro TailCallFunctionPointer
    // $0 = function pointer value
    // $0 表示的是参数x17
    braaz   $0
.endmacro

#else
// not JOP

.macro TailCallFunctionPointer
    // $0 = function pointer value
    // $0 表示的是参数x17
    br  $0
.endmacro

总结一下：

1. 当快速查找流程无法命中的时候会进入慢速查找流程

2. 慢速查找流程__objc_msgSend_uncached会执行2行代码

• MethodTableLookup（去查找并返回imp）
• TailCallFunctionPointer（跳转至x17寄存器，也就是imp所在的寄存器）

4. 慢速查找流程将会进入C++中执行，然后通过x0寄存器返回，继续在汇编中向下执行，方法查找流程最终会跳转至x17寄存器（无论是慢速查找还是快速查找。

lookUpImpOrForward（慢速查找流程核心）

根据汇编部分的提示，全局续搜索lookUpImpOrForward，最后在objc-runtime-new.mm文件中找到了源码实现，这是一个c实现的函数

// 缓存 找不到 - lookUpImpOrForward - 慢速 - methodlist
// 汇编 缓存 参数未知

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

    if (slowpath(!cls->isInitialized())) {
        behavior |= LOOKUP_NOCACHE;
    }
    runtimeLock.lock();

    //检查类是否被注册了 
    checkIsKnownClass(cls);
    
    /**初始化跟cls实例对象在isa指向图中的每一个类（class、superClass、metaClass）
    以便后续自己类里面找不到方法去父类里面依次向上找
    所以在此处对所有相关的类进行了初始化
    对rw、ro的一些处理，后面会讲
    */
    cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
    runtimeLock.assertLocked();
    curClass = cls;

    /**
      循环查找类对象的methodList，当前类没有的话就找父类
      父类没有就找父类的父类，一直找到NSObject类
      如果NSObject都找不到的话最终curClass会指向nil
      将事先准备好的forward_imp赋值给imp
      然后结束慢速查找流程，接下来进入Runtime消息转发机制
    */

    for (unsigned attempts = unreasonableClassCount();;) {
        if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
        //再次查找共享缓存，防止查找过程中有新的插入。通常情况下我们的自定义方法不会出现在共享缓存中
#if CONFIG_USE_PREOPT_CACHES
            imp = cache_getImp(curClass, sel);
            if (imp) goto done_unlock;
            curClass = curClass->cache.preoptFallbackClass();
#endif
        } else {
            // curClass method list.
            //在当前类的方法列表里面查找，这是重点。查找算法是二分法
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {
                imp = meth->imp(false);
                goto done;
            }

            if (slowpath((curClass = curClass->getSuperclass()) == 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;
        }
    }

    // No implementation found. Try method resolver once.

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

 done:
    if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) {
#if CONFIG_USE_PREOPT_CACHES
        while (cls->cache.isConstantOptimizedCache(/* strict */true)) {
            cls = cls->cache.preoptFallbackClass();
        }
#endif
        log_and_fill_cache(cls, imp, sel, inst, curClass);
    }
 done_unlock:
    runtimeLock.unlock();
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
    return imp;
}

getMethodNoSuper_nolock(二分查找流程)

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

    ASSERT(cls->isRealized());

    //获取methodList，methodList因为数据类型的原因可能为二维数组
    //循环条件是数组不为空，即开始位置不等于结束位置
    auto const methods = cls->data()->methods();
    for (auto mlists = methods.beginLists(),
              end = methods.endLists();
         mlists != end;
         ++mlists)
    {
        //进入search_method_list_inline修复为有序list
        method_t *m = search_method_list_inline(*mlists, sel);
        if (m) return m;
    }

    return nil;
}

getMethodNoSuper_nolock->search_method_list_inline->findMethodInSortedMethodList逐步深入，进入二分法核心算法代码如下：

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; //key 等于 say666
    uint32_t count;
    //base相当于low，count是max，probe是middle，这就是二分
    for (count = list->count; count != 0; count >>= 1) {
        //从首地址+下标 --> 移动到中间位置（count >> 1 右移1位即 count/2 = 4）
        probe = base + (count >> 1); 
        
        uintptr_t probeValue = (uintptr_t)probe->name;
        
        //如果查找的key的keyvalue等于中间位置（probe）的probeValue，则直接返回中间位置
        if (keyValue == probeValue) { 
            // -- while 平移 -- 排除分类重名方法
            while (probe > first && keyValue == (uintptr_t)probe[-1].name) {
                //排除分类重名方法（方法的存储是先存储类方法，在存储分类---按照先进后出的原则，分类方法最先出，而我们要取的类方法，所以需要先排除分类方法）
                //如果是两个分类，就看谁先进行加载
                probe--;
            }
            return (method_t *)probe;
        }
        
        //如果keyValue 大于 probeValue，就往probe即中间位置的右边查找
        if (keyValue > probeValue) { 
            base = probe + 1;
            count--;
        }
    }
    
    return nil;
}

算法原理：从第一次查找开始，每次都取中间位置，与想查找的key的value值作比较，如果相等，则需要排除分类方法，然后将查询到的位置的方法实现返回，如果不相等，则需要继续二分查找，如果循环至count = 0还是没有找到，则直接返回nil，如下所示：

09-二分查找.png

例子：

假设要查找的sel对应的在第7位，list.count=8

第一次进入循环，probe = base + （ 8 >> 1 ） = 0 + 4 = 4

那么第一次查找的范围就是0-8，匹配元素位置是4，判定结果keyValue（7）> prebeValue(4)，未匹配

满足keyValue > probeValue，base = probe + 1 = 4 + 1 = 5，count-- = 7

第二次进入循环，此时count = 7 >> 1 = 3, probe = 5 + 3 >> 1 = 6

第二次查找的范围是5-8，匹配元素位置是6，判定结果keyValue（7）> prebeValue(6)，未匹配

满足keyValue > probeValue，base = probe + 1 = 6 + 1 = 7，count-- = 2

第三次进入循环，此时count = 2 >> 1 = 1, probe = 7 + 1 >> 1 = 7

第三次查找的元素是7，匹配，返回imp

log_and_fill_cache(缓存填充)

如果记录器允许，调用cache的insert方法，将其插入缓存，下一次的查找就会进行快速缓存查找了。

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
    cls->cache.insert(sel, imp, receiver);
}

总结

lookUpImpOrForward，此过程为慢速查找流程，通过死循环的方式不断遍历来查找imp，对于全局性来讲，首先去找共享缓存，然后查自己的methodList，如果自己没有，找父类，父类没有，找NSObject，NSObject没有，会指向nil，最终跳出来。

共享缓存 -> methodList -> 父类 -> NSObject -> nil - >跳出循环

补充点：

为什么快速查找缓存要使用汇编编写，而不是用C++编写呢？

汇编更接近机器的语言，执行效率非常的快，安全，这是优点。但是由于方法是特别的多，通过汇编查找缓存的方式可以最大程序的优化执行效率。另外，汇编在执行的时候，参数可以是未知的，这一点区别与C/C++，参数一定是调用前就已经指定好了，明确参数，汇编的另一优点也就体现了，相对于C/C++更加的动态化。

为什么要执行慢速查找流程，全部使用汇编进行快速查找不爽吗？

因为在缓存中已经找不到了，进入了慢速查找流程，这个时候需要去找方法，不断的遍历methodList的过程，通过isa的指向关系，自己找不到，找爸爸，爸爸找不到，找爷爷，一路向上遍历查找，直到nil。因为这个过程是一个耗时过程，所以放在C/C++中执行。