OC底层探索（十一）：IMP慢速查找

CacheLookUp到慢速查找

• 之前我们探究了快速查找流程
• 但当缓存里找不到的时候，就会调用MissLabelDynamic
• MissLabelDynamic = objc_msgSend_uncache

.endmacro

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

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

//
.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
    bl	_lookUpImpOrForward

    // IMP in x0
    mov	x17, x0

    RESTORE_REGS MSGSEND

.endmacro

复制代码

lookUpImpOrForward解析

NEVER_INLINE
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    // 创建有用于转发的imp
    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    // 变量 imp, curClass(当前类)
    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;
    // ;; 死循环，没有任何条件判断可以出这个循环
    // attempts 类的大小
    for (unsigned attempts = unreasonableClassCount();;) {
    // 如果当前类是共享缓存
        if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
#if CONFIG_USE_PREOPT_CACHES
     // cache_getImp 汇编方法
            imp = cache_getImp(curClass, sel);
            if (imp) goto done_unlock;
            curClass = curClass->cache.preoptFallbackClass();
#endif
        } else {
            // curClass method list.
            // 通过sel，找 meth
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {
                // 拿到 imp
                imp = meth->imp(false);
                // 执行 done 结束循环
                goto done;
            }
            //如果当前类没找meth,就去找其父类，curClass = superclass, 直到找到nil
            if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
                // No implementation found, and method resolver didn't help.
                // Use forwarding.
                // 没有找到的话就将 forward_imp赋值，结束循环
                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.
        // curClass =  Superclass
        // 父类根据sel去查找imp
        imp = cache_getImp(curClass, sel);
        
        // 如果是 forward_imp，结束循环
        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;
        }
        
        // 找到了执行done
        if (fastpath(imp)) {
            // Found the method in a superclass. Cache it in this class.
            goto done;
        }
    }

    // No implementation found. Try method resolver once.
    
    // 如果都没找到，执行 resolveMethod_locked
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

// 找到就走done
 done:
    // behavior = LOOKUP_INITIALIZE | LOOKUP_RESOLVER
    if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) {
    // 查找共享缓存
#if CONFIG_USE_PREOPT_CACHES
        while (cls->cache.isConstantOptimizedCache(/* strict */true)) {
            cls = cls->cache.preoptFallbackClass();
        }
#endif
      // 调用 insertCache，插入缓存
        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;
}

复制代码

• 创建一个 forward_imp
• 判断类有没有初始化
• 检测类是否加载
• 没有加载，就加载该类
• 开启一个死循环
• 如果是共享缓存，则查找共享缓存
• 如果不是则调用getMethodNoSuper_nolock,通过self，查找 method
• 如果有method,取出其中的imp, 然后调用done, 然后调log_and_fill_cache,插入缓存

，返回imp

• 如果没有method, curCls = superClass,查找父类，调用ache_getImp(curClass, sel)汇编，其实是就是调用了Cache_LookUp,快速查找imp,没有再走父类的慢速查找，就是递归。,有则走 done，没有则继续循环查找父类直到nil
• 当所有类都没找到时，调用resolveMethod_locked, 进入消息决议阶段

getMethodNoSuper_nolock 如何查找 method

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

    ASSERT(cls->isRealized());
    // fixme nil cls? 
    // fixme nil sel?

    // 找到方法列表
    auto const methods = cls->data()->methods();
    // 遍历
    for (auto mlists = methods.beginLists(),
              end = methods.endLists();
         mlists != end;
         ++mlists)
    {
        // <rdar://problem/46904873> getMethodNoSuper_nolock is the hottest
        // caller of search_method_list, inlining it turns
        // getMethodNoSuper_nolock into a frame-less function and eliminates
        // any store from this codepath.
        // 根据sel 检索 method
        method_t *m = search_method_list_inline(*mlists, sel);
        if (m) return m;
    }

    return nil;
}
复制代码

search_method_list_inline

ALWAYS_INLINE static method_t *
search_method_list_inline(const method_list_t *mlist, SEL sel)
{
    // Ignore any flags in the top bits, just look at the bottom two.
    int methodListIsFixedUp = mlist->isFixedUp();
    // 是否有大小
    int methodListHasExpectedSize = mlist->isExpectedSize();
    
    if (fastpath(methodListIsFixedUp && methodListHasExpectedSize)) {
        return findMethodInSortedMethodList(sel, mlist);
    } else {
        // Linear search of unsorted method list
        if (auto *m = findMethodInUnsortedMethodList(sel, mlist))
            return m;
    }

#if DEBUG
    // sanity-check negative results
    if (mlist->isFixedUp()) {
        for (auto& meth : *mlist) {
            if (meth.name() == sel) {
                _objc_fatal("linear search worked when binary search did not");
            }
        }
    }
#endif

    return nil;
}
复制代码

findMethodInSortedMethodList

ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
   // M1 用的samll
    if (list->isSmallList()) {
        if (CONFIG_SHARED_CACHE_RELATIVE_DIRECT_SELECTORS && objc::inSharedCache((uintptr_t)list)) {
            return findMethodInSortedMethodList(key, list, [](method_t &m) { return m.getSmallNameAsSEL(); });
        } else {
            return findMethodInSortedMethodList(key, list, [](method_t &m) { return m.getSmallNameAsSELRef(); });
        }
    } else {
        return findMethodInSortedMethodList(key, list, [](method_t &m) { return m.big().name; });
    }
}
复制代码

findMethodInSortedMethodList 二分算法

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;

    uintptr_t keyValue = (uintptr_t)key;
    uint32_t count;
    
    // count = count / 2 这有赋值
    // probe = base + count / 2, 这里没有赋值count
    
    // 例如：list->count = 9, 要取到第8个，keyValue = i
    // 0 1 2 3 4 5 6 7 8 
    // a b c d e f g h i 
    // 1. base = 0, count = 9 , probe = 0 + 9 / 2 = 4, probeValue = e
    //    keyValue != probeValue
    //    keyValue > probeValue
    //    base = probe + 1 = 4 + 1 = 5
    //    count = 9 - 1 = 8
    //    count = 8 / 2 = 4
    // 2. probe = 5 +  4 / 2 = 7
    //    keyValue != probeValue
    //    keyValue > probeValue
    //    base = 7 + 1, 
    //    count = 4 - 1 = 3
    //    count = 3 / 2 = 1
    //    probe = 8 + 1 / 2 = 8
    //    keyValue == probeValue
    
    // 要取到第0个，keyValue = a
    // 1. base = 0 , count = 9, probe = 0 + 9 / 2 = 4
    //    keyValue != probeValue
    //    keyValue < probeValue
    // 2. count = 9 / 2 = 4
    //    probe = 0 + 4 / 2 = 2
    //    keyValue != probeValue
    //    keyValue < probeValue
    // 3. count = 4 / 2 = 2
    //    probe = 0 + 2 / 2 = 1
    //    keyValue != probeValue
    //    keyValue < probeValue
    // 4. count = 1 / 2 = 0
    //    probe = 0 + 0 /2 = 0 
    //    keyValue == probeValue

    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;
}
复制代码

• 用一 个 probe探针
• 一个 base, 开始 base = 0
• probe = base + count / 2, 也就是中间位置
• 当目标数值大于 probe时，将base 向 probe 前加一,因为大于所以左边的就不用找了，
• 小于的话，就在左边，base 不变，count = count / 2 , probe = count / 2, 再判断大小，如果一直小于，则一直二分到count = 1