iOS-慢速方法查找

在iOS-快速方法查找中，如果没有找到方法实现，最终都会走到__objc_msgSend_uncached汇编函数,汇编源码实现

.macro 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
    
    MethodTableLookup//方法列表查找
    TailCallFunctionPointer x17

    END_ENTRY __objc_msgSend_uncached

.endmacro

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
    bl  _lookUpImpOrForward //跳转执行_lookUpImpOrForward

    // IMP in x0
    mov x17, x0

    RESTORE_REGS MSGSEND

.endmacro

当我们在当前文件继续搜索_lookUpImpOrForward，发现找不到其实现。全局搜索呢？

全局搜索搜索结果
发现全是调用,跳转，那么这个方法实现去哪里了呢。这里有个小知识点：

注：
1、C/C++中调用 汇编 ，去查找汇编时，C/C++调用的方法需要多加一个下划线
2、汇编 中调用 C/C++方法时，去查找C/C++方法，需要将汇编调用的方法去掉一个下划线

最终我们在objc-runtime-new中找到了该方法实现，终于又回到了熟悉的c/c++代码（汇编再见）

image.png

我们来康康源码吧

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.
    
    //检测类是否已经注册到内存中
    checkIsKnownClass(cls);
    
    //确认继承链，方便后面方法查找
    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().
    
    //死循环，死循环会用break，goto跳出循环
    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.
            //查找方法列表，getMethodNoSuper_nolock用的二分查找
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {
                imp = meth->imp(false);
                goto done;
            }
            //将curClass赋值为superclass并判断是否为nil，后面就进入了父类的查找啦，从这里可以看出是延继承链倒着往上查找
            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
        //写入缓存，会调用cache.insert方法，注意这里不管是在父类找到imp还是本来imp最终都会缓存到本类
        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;
}

源码中关键地方我都添加了中文注释，总结一下慢速查找流程

慢速查找流程

方法列表查找过程中有个二分查找，相对有趣，贴一下源码

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;

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

对比_objc_msgSend,_cache_getImp

汇编函数_objc_msgSend,_cache_getImp实现, 中间调用CacheLookup时参数不同, 导致最后处理分支情况不一样, 分析如下: .macro CacheLookup Mode, Function, MissLabelDynamic, MissLabelConstant

_objc_msgSend缓存未命中情况下, 最终会调用lookUpImpOrForward查找流程
ENTRY _objc_msgSend
CacheLookup NORMAL, _objc_msgSend, __objc_msgSend_uncached

_objc_msgSend 缓存未命中
-> CacheLookup
-> MissLabelDynamic(__objc_msgSend_uncached)
-> MethodTableLookup
-> lookUpImpOrForward
_cache_getImp缓存未命中情况下, 最终会返回imp为0, 而不回去调用lookUpImpOrForward, 这点需要注意.
回到查找流程中,查找父类的imp代码imp = cache_getImp(curClass, sel);, 未命中情况下如果不是返回0, 而是返回forward_imp的话, 直接break; 也就是说只找第一个superclass的缓存就结束了, 而不会继续查找第一个superclass方法列表, 也不会查找到superclass链上的其他类了. 反向验证了, 苹果这么实现_cache_getImp的道理.

STATIC_ENTRY _cache_getImp
CacheLookup GETIMP, _cache_getImp, LGetImpMissDynamic, LGetImpMissConstant

_cache_getImp 缓存未命中
-> CacheLookup
-> MissLabelDynamic(LGetImpMissDynamic)
-> ret x0 // x0的值为0