在 _objc_msgSend分析之CacheLookup中，我们分析到当在cache中未找到对应的IMP时，汇编代码执行MissLabelDynamic（__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
复制代码

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

.macro TailCallFunctionPointer
	// $0 = function pointer value
	br	$0
.endmacro
复制代码

在 __objc_msgSend_uncached中执行了 MethodTableLookup以及 TailCallFunctionPointer x17。
在MethodTableLookup中，调用了 _lookUpImpOrForward（// lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)） 这个函数。然后返回一个IMP，写入到x0，x17中，最后在TailCallFunctionPointer x17直接跳转执行IMP。

所以接一下来的重点就是 _lookUpImpOrForward。

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.
    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().

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

复制代码

在分析 _lookUpImpOrForward之前，先确定目标，现在是想通过SEL找到对应的IMP，所以在 _lookUpImpOrForward方法中，我们的目标就是IMP。暂时忽略一些无关代码。

在 _lookUpImpOrForward的代码逻辑为：

1.if (slowpath(!cls->isInitialized())) 先判断当前的cls是否初始化，

2.checkIsKnownClass(cls)，检测当前class的是否注册加载。

3.cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE), 这一步内部是对class的 ro，rw进行赋值，设置supercls，metacls（在设置的同时，也是递归调用对superclass，以及元类初始化），我们知道method_list，存放在对应的ro，rw中,所以这些操作只为后面for循环查找imp做准备。

for (unsigned attempts = unreasonableClassCount();;)，循环
*if (curClass->cache.isConstantOptimizedCache(/ strict */true))**，先判断有没有缓存，如果有，先在缓存中查找
如果没有缓存，就先 Method meth = getMethodNoSuper_nolock(curClass, sel) 在当前class中查找，

7.如果在当前类中未找到，就 if (slowpath((curClass = curClass->getSuperclass()) == nil)) 先判断当前类的Superclass是否为nil，如果为空，直接返回 forward_imp（const IMP forward_imp = (IMP)_objc_msgForward_impcache），如果不为nil，将curClass = curClass->getSuperclass()， imp = cache_getImp(curClass, sel);，继续循环执行 5，6，7。

8.如果所有的class都找不到，resolveMethod_locked(inst, sel, cls, behavior); 方法决议流程。

9.如果在for循环中找到IMP，log_and_fill_cache(cls, imp, sel, inst, curClass); 插入缓存。

分析getMethodNoSuper_nolock

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.
        method_t *m = search_method_list_inline(*mlists, sel);
        if (m) return m;
    }

    return nil;
}
复制代码

1.判断当前ASSERT(cls->isRealized()) class是都实现。

2.auto const methods = cls->data()->methods() 通过cls 拿到rw，然后拿到对应的methods。

3.循环遍历methods，method_t*m = search_method_list_inline(*mlists, sel) 因为这个methods是个二维数组，所以需要在内部list中继续查找。

search_method_list_inline层层调用，最后调用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;
    
    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;
}

复制代码

在findMethodInSortedMethodList中，运用了二分法，进行方法的查找。我们通过断点，更清晰查看一下对应的的流程。

@interface LGPerson : NSObject{
    NSString *hobby;
}

@property (nonatomic, copy) NSString *name;
@property (nonatomic) int age;

// 方法 - + OC  C/C++ 函数
// 元类
- (void)saySomething;
+ (void)sayNB;
复制代码

1.断点发现，当前class的methods的总数为5（0101B），然后probe = base + (count >> 1) probe = 首地址+2，5取一半，刚好取到3，

2.uintptr_t probeValue = (uintptr_t)getName(probe)，通过方法的地址，拿到对应的SEL

3.if (keyValue == probeValue) 如果命中了，还需要 while (probe > first && keyValue == (uintptr_t)getName((probe – 1))) 判断是否有分类重写，因为分类重写了对应的方法后，会将对应的IMP方法放在前面，所以这个 probe – 1，找到最前面的实现，然后。

4.if (keyValue > probeValue)，如果当前keyValue大于probeValue，那证明要找的sel还在后面，base = probe + 1， count–，所以讲base往后移，避免当前索引再次查找。

继续for循环，此时先将count >>= 1（右移1位相当于除以2，缩小一半），缩小查找范围，

通过打印，当前的count == 2(0010B)，然后再次右移1位，得到probe = base + 1 ，然后打印对象的base， probe，发现probe的index = 1（这是C++的迭代器，并且重载的+法，接着循环 3，4，5，如果找到就返回对应的method的地址，如果没有就返回nil。

总结：通过对 __objc_msgSend_uncached分析，我们找到的 _lookUpImpOrForward，分析的代码的逻辑，先去判断当前的class 是否初始化，并递归调用，对当前class，以及父类，元类的ro，rw赋值，为慢速查找流程做准备，在慢速查找流程中，循环递归遍历class的methods（如果当前class未找到，获取父类，继续在父类查找），在遍历methods时，巧妙的运用的二分查找算法，查找对应的方法实现（如果有分类重写，需要找到最前面的方法实现）。

文章版权归作者所有，未经允许请勿转载。

THE END

IOS