iOS底层原理11：消息流程分析之慢速查找

2021-07-06 本文已影响0人黑白森林无间道

在前面的文章iOS底层原理10：消息流程分析之快速查找中，我们分析了快速查找流程，如果快速查不到，则需要进入慢速查找流程，以下是慢速查找的分析过程

1、objc_msgSend 慢速查找流程分析

1.1、慢速查找-汇编部分分析

在快速查找流程中，如果没有找到方法实现，会走到__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 存储到x17寄存器
    MethodTableLookup
    // 相当于【br x17】
    TailCallFunctionPointer x17
END_ENTRY __objc_msgSend_uncached

查看MethodTableLookup的汇编实现，调用了_lookUpImpOrForward函数来查找方法，汇编代码如下：

.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
//---- _lookUpImpOrForward的参数: 【x0 = receiver;  x1 = _cmd;  x2 = isa即类的首地址； x3 = 3 】
    bl  _lookUpImpOrForward // 核心代码【须牢记】

    // IMP in x0
    mov x17, x0

    RESTORE_REGS MSGSEND

.endmacro

1.2、通过汇编调试验证

在ViewController.m的[person sayHello];方法调用处添加断点，运行程序，开启汇编调试【Debug -- Debug worlflow -- 勾选Always show Disassembly】

image

按住control + Step into，进入objc_msgSend的汇编

image

在_objc_msgSend_uncached加一个断点，执行到断点处，按住control + Step into，进入汇编

image

从上可以看出最后走到的就是lookUpImpOrForward，此时并不是汇编实现

慢速查找-C/C++部分

lookUpImpOrForward源码分析

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

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())) {
        // The first message sent to a class is often +new or +alloc, or +self
        // which goes through objc_opt_* or various optimized entry points.
        //
        // However, the class isn't realized/initialized yet at this point,
        // and the optimized entry points fall down through objc_msgSend,
        // which ends up here.
        //
        // We really want to avoid caching these, as it can cause IMP caches
        // to be made with a single entry forever.
        //
        // Note that this check is racy as several threads might try to
        // message a given class for the first time at the same time,
        // in which case we might cache anyway.
        behavior |= LOOKUP_NOCACHE;
    }

    // runtimeLock is held during isRealized and isInitialized checking
    // to prevent races against concurrent realization.

    // runtimeLock is held during method search to make
    // method-lookup + cache-fill atomic with respect to method addition.
    // Otherwise, a category could be added but ignored indefinitely because
    // the cache was re-filled with the old value after the cache flush on
    // behalf of the category.
    
    //加锁，目的是保证读取的线程安全
    runtimeLock.lock();

    // We don't want people to be able to craft a binary blob that looks like
    // a class but really isn't one and do a CFI attack.
    //
    // To make these harder we want to make sure this is a class that was
    // either built into the binary or legitimately registered through
    // objc_duplicateClass, objc_initializeClassPair or objc_allocateClassPair.
    //判断是否是一个已知的类：是否注册类 是否被dyld加载的类
    checkIsKnownClass(cls);

    //1、判断类是否实现，如果没有，需要先实现，此时的目的是为了确定父类链，方法后续的循环
    //2、判断类是否初始化，如果没有，需要先初始化
    cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
    // runtimeLock may have been dropped but is now locked again
    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();;) {
        //判断是否有共享缓存缓存优化，一般是系统的方法比如NSLog，一般的方法不会走
        if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
#if CONFIG_USE_PREOPT_CACHES
            /*
            再一次查询共享缓存，目的可能在你查询过程中
            别的线程可能调用了这个方法共享缓存中有了直接去查询
            */
            imp = cache_getImp(curClass, sel);
            //如果imp存在即缓存中有 跳转到done_unlock流程
            if (imp) goto done_unlock;
            curClass = curClass->cache.preoptFallbackClass();
#endif
        } else {
            // curClass method list.
            // 在curClass类中采用二分查找算法查找methodlist
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {
                imp = meth->imp(false); //获取对应的imp
                goto done;              //跳转到 done 流程
            }

            if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
                // No implementation found, and method resolver didn't help.
                // Use forwarding.
                // 判断父类是否为空， 为空的话（即类的继承链走完）imp 赋值为 _objc_msgForward_impcache
                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
        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;
}

方法查找流程主要有以下几步：

【第一步】cache缓存中进行查找，即快速查找，找到则直接返回imp，反之，则进入【第二步】
【第二步】慢速查找流程，先判断cls
- 是否是注册类，如果不是，则报错
- 判断类是否实现，如果没有，需要先实现，此时的目的是为了确定父类链，方便后续的循环
- 判断类是否初始化，如果没有，需要先初始化
【第三步】for循环，按照类继承链 或者 元类继承链的顺序查找
- 当前cls的方法列表中使用二分查找算法查找方法，如果找到，则进入log_and_fill_cache，进行cache写入流程（在iOS底层原理09：类结构分析——cache属性文章中已经详述过），并返回imp
- 如果没有找到，当前cls被赋值为父类，如果父类等于nil，则imp = _objc_msgForward_impcache（消息转发），并终止递归判断，进入【第四步】
- 如果父类链中存在循环，则报错，终止循环
- 父类缓存中查找方法
  - 如果未找到，则直接返回nil，继续循环查找
  - 如果找到，则直接返回imp，执行cache写入流程
【第四步】判断是否执行过动态方法解析
- 如果没有，执行动态方法解析
- 如果执行过一次动态方法解析，则走到消息转发流程

以上就是方法的慢速查找流程，下面在分别详细解释二分查找原理 以及 父类缓存查找详细步骤

二分查找方法列表（getMethodNoSuper_nolock方法）

查找方法列表的流程如下所示

image

其二分查找核心的源码实现如下

/***********************************************************************
 * search_method_list_inline
 **********************************************************************/
template<class getNameFunc>
ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)
{
    ASSERT(list);

    auto first = list->begin();
    auto base = first;
    decltype(first) probe;
    // 把key直接转换成uintptr_t 因为修复过后的method_list_t中的元素是排过序的
    uintptr_t keyValue = (uintptr_t)key;
    uint32_t count;
    //base相当于low，count是max，probe是middle，这就是二分
    // 假如 count = list->count = 8 ；  （count >>= 1） = 4
    for (count = list->count; count != 0; count >>= 1) {
        //从首地址+下标 --> 移动到中间位置（count >> 1 右移1位即 count/2 = 4）
        probe = base + (count >> 1);
        
        uintptr_t probeValue = (uintptr_t)getName(probe);
        
        // 如果 目标key ==  中间位置的key 匹配成功
        if (keyValue == probeValue) {
            // `probe` is a match.
            // Rewind looking for the *first* occurrence of this value.
            // This is required for correct category overrides.
            // -- while 平移 -- 排除分类重名方法
            while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
                //分类覆盖，分类中有相同名字的方法，如果有分类的方法我们就获取分类的方法，多个分类看编译的顺序
                probe--;
            }
            //返回方法的地址
            return &*probe;
        }
        //如果keyValue 大于 probeValue，就往probe即中间位置的右边查找
        if (keyValue > probeValue) {
            base = probe + 1;
            count--;
        }
    }
    
    return nil;
}

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

流程图待补充

父类缓存查找（cache_getImp方法）

cache_getImp方法是通过汇编_cache_getImp实现，传入的$0 是 GETIMP，如下所示

image

如果父类缓存中找到了方法实现，则跳转至CacheHit即命中，则直接返回imp
如果在父类缓存中，没有找到方法实现，则跳转至LGetImpMissDynamic，将p0的值设为0x0，即返回nil

总结

对于对象方法（即实例方法），即在类中查找，其慢速查找的父类链是：类--父类--根类--nil
对于类方法，即在元类中查找，其慢速查找的父类链是：元类--根元类--根类--nil
如果快速查找、慢速查找也没有找到方法实现，则尝试动态方法决议
如果动态方法决议仍然没有找到，则进行消息转发

iOS底层原理11：消息流程分析之慢速查找

1、objc_msgSend 慢速查找流程分析

1.1、慢速查找-汇编部分分析

1.2、通过汇编调试验证

慢速查找-C/C++部分

lookUpImpOrForward源码分析

二分查找方法列表（getMethodNoSuper_nolock方法）

父类缓存查找（cache_getImp方法）

总结

猜你喜欢

热点阅读