美文网首页
OC底层原理09 - 消息流程之慢速查找

OC底层原理09 - 消息流程之慢速查找

作者: H雷610 | 来源:发表于2020-12-25 16:16 被阅读0次

    在上一篇OC底层原理08 - objc_msgSend流程之快速查找文章中,我们分析了快速查找流程,如果快速查不到,则需要进入慢速查找流程,以下是慢速查找的分析过程

    objc_msgSend 慢速查找流程分析

    慢速查找-汇编部分

    在快速查找流程中,如果缓存中没有找到方法实现,无论是走到CheckMiss还是JumpMiss,最终都会走到__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 p16 is the class to search
        
        MethodTableLookup
        TailCallFunctionPointer x17
    
        END_ENTRY __objc_msgSend_uncached
    
    • 搜索MethodTableLookup的汇编实现,其中的核心是_lookUpImpOrForward,汇编源码实现如下
    .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)]
    
        // 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 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
    

    验证
    通过汇编调试进行验证,流程如下

    • main中,在[person instanceMethod1]方法调用处加一个断点,并且开启汇编调试 【Debug -- Debug worlflow -- 勾选Always show Disassembly】,运行程序
      image.png
    • 按住control + stepinto,进入objc_msgSend的汇编
      image.png
    • _objc_msgSend_uncached加一个断点,继续执行,然后按住control + stepinto,进入汇编
      image.png
      从上可以看出最后走到的就是lookUpImpOrForward

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

    • 根据汇编部分的提示,全局续搜索lookUpImpOrForward,最后在objc-runtime-new.mm文件中找到了源码实现,这是一个C实现的函数
    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();
    
        // 再次执行快速查找,如果找到则直接返回imp
        // 目的:防止多线程操作时,刚好调用函数,该方法此时已经缓存
        if (fastpath(behavior & LOOKUP_CACHE)) {
            imp = cache_getImp(cls, sel);
            if (imp) goto done_nolock;
        }
    
        // 加锁,目的是保证读取的线程安全
        runtimeLock.lock();
    
        // 判断是否是一个已知的类:判断当前类是否是已经被认可的类,即已经加载的类
        checkIsKnownClass(cls);
    
        // 判断类是否实现,如果没有,需要先实现,此时的目的是为了确定父类链
        if (slowpath(!cls->isRealized())) {
            cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
        }
        // 判断类是否初始化,如果没有,需要先初始化
        if (slowpath((behavior & LOOKUP_INITIALIZE) && !cls->isInitialized())) {
            cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
        }
    
        runtimeLock.assertLocked();
        curClass = cls;
    
        
        for (unsigned attempts = unreasonableClassCount();;) {
            // 在当前类的方法列表查找(采用二分查找),如果找到,则返回,将方法缓存到 cache 中
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {
                imp = meth->imp;
                goto done;
            }
            // 代表当前类没有找到,将 当前类 设置为 当前类的父类,并判断父类是否为nil
            if (slowpath((curClass = curClass->superclass) == nil)) {
                // 未找到方法实现,方法解析器也不行,使用转发
                imp = forward_imp;
                break;
            }
    
            // 如果父类链中存在循环,则停止
            if (slowpath(--attempts == 0)) {
                _objc_fatal("Memory corruption in class list.");
            }
    
            // 从父类缓存里面查找 如果未找到此时不会进入慢速查找
            imp = cache_getImp(curClass, sel);
            if (slowpath(imp == forward_imp)) {
                // 如果在父类中找到了forward,则停止查找,且不缓存,首先调用此类的方法解析器
                break;
            }
            if (fastpath(imp)) {
                // 如果在父类中,找到了此方法,将其存储到cache中
                goto done;
            }
        }
    
        // 没有找到方法实现,尝试一次方法解析
        if (slowpath(behavior & LOOKUP_RESOLVER)) {
            // 动态方法决议的控制条件,表示流程只走一次
            behavior ^= LOOKUP_RESOLVER;
            return resolveMethod_locked(inst, sel, cls, behavior);
        }
    
     done:
        // 存储到缓存
        log_and_fill_cache(cls, imp, sel, inst, curClass);
        // 解锁
        runtimeLock.unlock();
     done_nolock:
        if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
            return nil;
        }
        return imp;
    }
    
    其整体的慢速查找流程如图所示 image.png

    主要流程如下

    1. cache缓存中进行查找,即快速查找,找到则直接返回imp,反之,则进入step2
    2. 判断cls
      2.1 判断类是否已知,如果不是,则报错
      2.2 判断类是否实现,如果没有,则需要先实现,确定其父类链,此时实例化的目的是为了确定父类链、ro、以及rw等,方法后续数据的读取以及查找的循环
      2.3 判断类是否初始化,如果没有,则初始化
    3. for循环,按照类继承链或者元类继承链的顺序查找
      3.1 当前cls方法列表中使用二分查找算法进行方法查找,如果找到,则进入cache写入流程OC底层原理07 - objc_class 中 cache 原理分析),并返回imp,如果没有找到,则返回nil,并继续
      3.2 当前cls被赋值为父类,如果父类等于nil,则imp = 消息转发,跳出循环,执行step4
      3.3 如果父类链中存在循环,则报错,终止循环
      3.4 父类缓存中查找方法
      • 如果未找到,即imp = 0x0,继续循环查找,执行step3
      • 如果找到,判断imp == forward_imp,相等执行step4,否则返回imp,并执行cache写入流程
    4. 判断是否执行过动态方法解析
      • 如果没有,执行动态方法解析
      • 如果执行过一次动态方法解析,则走到消息转发流程

    getMethodNoSuper_nolock方法:二分查找方法列表

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

    image.png 核心方法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;
        uint32_t count;
        
        for (count = list->count; count != 0; count >>= 1) {
            probe = base + (count >> 1);
            
            uintptr_t probeValue = (uintptr_t)probe->name;
            
            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)probe[-1].name) {
                    probe--;
                }
                return (method_t *)probe;
            }
            
            if (keyValue > probeValue) {
                base = probe + 1;
                count--;
            }
        }
        
        return nil;
    }
    

    算法原理大致为:从第一次查找开始,每次都取中间位置,与想查找的keyvalue值作比较

    • 如果不相等,首先判断所要查找keyValue和当前值probeValue比较,如果keyValue大于probeValue,将起始位置替换为当前位置继续二分查找,如果循环至count = 0还是没有找到,则直接返回nil
    • 如果相等,则需要往前移一位继续判断是否相等(排除分类方法),如果相等 继续前移不相等则将当前位置的方法实现返回

    cache_getImp方法:父类缓存查找

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

    image.png
    • 如果父类缓存中找到了方法实现,则跳转至CacheHit即命中,则直接返回imp
    • 如果父类缓存中没有找到方法实现,则跳转至CheckMiss或者JumpMiss,通过判断$0跳转至LGetImpMiss,直接返回nil

    总结

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

    相关文章

      网友评论

          本文标题:OC底层原理09 - 消息流程之慢速查找

          本文链接:https://www.haomeiwen.com/subject/nwwenktx.html