9.iOS底层学习之方法的慢速查找流程

2021-09-29 本文已影响0人牛牛大王奥利给

上一篇学习了objc_msgSend的过程，先来回顾下流程：
-先通过enter进入到objc_msgSend函数，然后去判断消息的接受者是不是为空；
-如果为空直接返回0；
-如果不为空通过对象找到isa近而找到cache，然后通过内存平移找到buckets;
-找到buckets开始从指定的index，从后往前进行遍历，直到找到对的sel把相应的imp返回给消息接受者；
-如果找不到，会走MissLabelDynamic，接下来要讨论的流程，也就是慢速查找流程。

我们通过代码CacheLookup过程发现MissLabelDynamic，传进来的参数对应的是__objc_msgSend_uncached

image.png

//CacheLookup 的宏定义
.macro CacheLookup Mode, Function, MissLabelDynamic, MissLabelConstant

所以，我们具体来看下__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。分别查看下方法的具体实现。

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
    mov x3, #3
    bl  _lookUpImpOrForward
    // IMP in x0
    mov x17, x0
    RESTORE_REGS MSGSEND
.endmacro

TailCallFunctionPointer

.macro TailCallFunctionPointer
    // $0 = function pointer value
    br  $0
.endmacro

结合这两段代码的具体实现可以了解到MethodTableLookup 通过_lookUpImpOrForward方法找到相应的实现后赋值给x17，TailCallFunctionPointer直接返回x17并跳转到相应的地址。

$\color{red}{汇编指令：}$ bl，跳转到某地址（有返回），先将下一指令地址（即函数返回地址）保存到寄存器 lr (x30)中，再进行跳转；一般用于不同方法直接的调用，例如：

// 先将下一指令地址（‘0x100cfa754’ 函数调用后的返回地址）保存到寄存器 ‘lr’ 中，然后再调用 ‘0x100cfa754’ 函数
bl 0x100cfa754  ;

$\color{red}{汇编指令：}$ br，跳转到某寄存器(的值)指向的地址（无返回）, 不会改变 lr (x30) 寄存器的值。

经过上述整体的了解，我们接下来来看_lookUpImpOrForward具体做了什么，怎么查到的imp然后返回给x17。

lookUpImpOrForward

找到lookUpImpOrForward定义如下：

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 = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
    runtimeLock.assertLocked();
    curClass = cls;

    // The code used to lookup the class's cache again right after
    // we take the lock but for the vast majority of the cases
    // evidence shows this is a miss most of the time, hence a time loss.
    // The only codepath calling into this without having performed some
    // kind of cache lookup is class_getInstanceMethod().

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

以上流程梳理：
1、checkIsKnownClass先去检查是否注册类，未注册报错打印错误，会走_objc_fatalv方法；
2、通过方法realizeAndInitializeIfNeeded_locked下的initializeAndMaybeRelock去初始化类父类以及元类等isa的走位图和继承链，为慢速查找做好准备；
3、开始走for循环的遍历查询，先去isConstantOptimizedCache判断是不是要再去查缓存，如果需要进行再一次查缓存，是为了最后确认一次缓存里有没有相应的imp，如果有那么直接返回，走done_unlock；如果isConstantOptimizedCache为false那么会走getMethodNoSuper_nolock方法查询。
4、如果查到直接goto done；如果没有找到方法会curClass = curClass->getSuperclass()去查父类，先去查cache然后继续去走循环，直到跳转到done或者done_unlock，然后返回imp；

$\color{red}{以上为慢速查找的整个流程。}$ 然后来看下查找的具体实现：getMethodNoSuper_nolock。
我们通过getMethodNoSuper_nolock->search_method_list_inline->findMethodInSortedMethodList->findMethodInSortedMethodList找到查找方法的关键实现findMethodInSortedMethodList。

findMethodInSortedMethodList

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

    auto first = list->begin();
    auto base = first;
    decltype(first) 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)getName(probe);
        
        if (keyValue == probeValue) {
            // `probe` is a match.
            // Rewind looking for the *first* occurrence of this value.
            // This is required for correct category overrides.
            while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
                probe--;
            }
            return &*probe;
        }
        
        if (keyValue > probeValue) {
            base = probe + 1;
            count--;
        }
    }
    return nil;
}

以上是查找方法的算法，主要是运用二分查找，也叫折半查找。使用二分查找的条件是 $\color{red}{顺序存储结构}$ ，并且存储的数据是按照关键字大小有序排好的。二分查找的 $\color{red}{时间复杂度}$ 是log以2为底n的对数。了解这些以后我们来详细了解一下方法列表的二分查找的源码。

以上源代码我们带入值进行实际的模拟运行一下：
假设 keyValue=7；
count = 10；
然后我们进入到算法findMethodInSortedMethodList；
$\color{red}{第一趟查找}$ ：
first = 0 = base; count != 0;条件成立进入循环体，probe = base+(count >>1)；
$\color{red}{这里补充一下左移右移运算符的用法，左移右移相当于乘除法的运算，左移一位是当前的值乘以2的一次方，左移n位就是当前的值乘以2的n次方；同样右移n位表示当前的值除以2的n次方}$
所以probe = base+(count >>1)就等同于 probe = base + count/2 = 0+10/2 = 5; 7==5条件为假，接着往下判断是7>5为真，base = probe+1 = 5+1 = 6;
count-- ,count = 9， count右移一位并赋值给自己变成9/2=4;
第一趟查找结束，继续循环；
$\color{red}{第二趟查找}$ ：
probe = base + count/2 = 6+ 4/2 = 8;
7==8条件不成立；
7>8条件不成立，count右移一位变成4/2=2；第二趟结束；
$\color{red}{第三趟查找}$ ：
probe = base + (count >> 1)=base + count/2=6+2/2 = 7;
7==7成立进入keyValue == probeValue条件体内，

 // This is required for correct category overrides.
            while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
                probe--;
           }
            return &*probe;

这个while和分类有关系。如果命中的位置前一个方法也和keyValue，优先去调用前一个，如果不等直接返回probe。一般当前方法的前一个方法也能命中就是分类也去实现了该方法，通过方法的列表的排列和写入，分类的方法是在类的前面的，后面学习分类的时候会进一步分析。

以上源代码整个折半查找大致的过程是这样：
1、拿到list的第一个位置的关键字，然后list的长度，还有待查询关键字；
2、list的count折半，先去查左半区，不相等判断下折半过后的关键字和待查询的关键字的大小，如果待查询的比折半后的大，说明待查询的在右半区，base会移到右半区从刚才查过了的中间的位置的后一个开始，然后count--很细节，我理解的是和while (probe > first && keyValue == (uintptr_t)getName((probe - 1)))这个地方的原因一样，优先去查靠前的方法也就是左侧区域的，有可能有分类再这个要查询的方法前边，这个地方就针对这个做了个优化，如果有分类的同名方法会少执行几次这个方法 while (probe > first && keyValue == (uintptr_t)getName((probe - 1)))(ps:欢迎补充和纠正，只是自己目前的理解，未必准确！）
3、如果查找的关键字比base位置的关键字小，那么继续在左半区查，继续折半，以此类推，直到循环结束，结束的条件就是base和first重合了，此时count为1再右移为0，循环结束；
4、循环结束后，还是没查到返回nil；

以上为慢速查找的学习，接下来一篇将分析慢速查找也没查到该怎么办。