objc_msgSend_uncached 慢速查找-一一网

上一篇文章中，objc_msgSend通过在类的cache中找不到方法，会调用objc_msgSend_uncached，这里，我们探索它的流程。

objc_msgSend_uncached

        STATIC_ENTRY __objc_msgSend_uncached
	UNWIND __objc_msgSend_uncached, FrameWithNoSaves
	
	MethodTableLookup
	TailCallFunctionPointer x17

	END_ENTRY __objc_msgSend_uncached
复制代码

macro MethodTableLookup

	// 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

.endmacro
复制代码

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

通过这几段汇编代码可以看出，MethodTableLookup调用_lookUpImpOrForward获取imp，并且把imp保存在x0中，也就是imp是这个函数的返回值。然后把imp放在x17中，跳转x17执行。重点就是_lookUpImpOrForward获取imp的过程，全局搜索这个函数，这次不是汇编，而是C++。

_lookUpImpOrForward 慢速查找

查找前的准备

    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    IMP imp = nil;
    Class curClass; 
    
    checkIsKnownClass(cls);

    cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
复制代码

检查当前类是否存在，并且初始化一系列相关的类和元类，可参考isa走位图。

二分查找-方法

二分查找是一种针对有序列表的查找算法，每次进行折半，然后与所查找的值比较。例如：从数组[1,2,3,5,6,8,10]中找8，第一次折半找到5，比8小，再次从[6,8,10]中折半查找，取出8，则找到结果。

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

复制代码

进入一个死循环，首先查找一下缓存，在这一系列的调用过程中，方法可能已经在缓存中了。如果没有，则开始查找自己的methodlist。进入getMethodNoSuper_nolock->search_method_list_inline->findMethodInSortedMethodList->findMethodInSortedMethodList，下面是苹果的二分查找，来找sel。

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

复制代码

例如 list = [0, 1, 2, 3, 4, 5, 6, 7] first = 0, base = 0, count = 8

 假如需要查找的key = 6
 第一次进入循环:
         probe = base + count >> 1 = 0 + 4 = 4   ***第一次查找的是4***
         key > probe
            base = probe + 1 = 5
            count-- = 7
 第二次进入循环：count != 0  count >>= 1 = 3 
         probe = base + count >> 1 = 5 + 1 = 6   ***第二次查找的是6***
         key = probe. 找到，返回probe
复制代码

 假如需要查找的key = 1
 第一次进入循环:
         probe = base + count >> 1 = 0 + 4 = 4   ***第一次查找的是4***
         
 第二次进入循环：count != 0  count >>= 1 = 4 
         probe = base + count >> 1 = 0 + 2 = 2   ***第二次查找的是2***
         
 第三次进入循环：count != 0  count >>= 1 = 2 
         probe = base + count >> 1 = 0 + 1 = 1   ***第三次查找的是1***
         key = probe. 找到，返回probe
复制代码

如果找到方法之后，goto done跳出循环，调用log_and_fill_cache->cls->cache.insert(sel, imp, receiver)，把方法加入缓存，下次就可以直接快速查找。
如果没有找到方法，则去父类中寻找imp = cache_getImp(curClass, sel)，cache_getImp又进入汇编代码，先从cache中查找，如果找不到，返回一个0到这个循环中，然后回到第2步执行，进行慢速查找。如果没有，再去父类中查找，这样循环下去。

      if (slowpath((curClass = curClass->getSuperclass()) == nil)) {    //这里取出父类curClass = curClass->getSuperclass()
                // No implementation found, and method resolver didn't help.
                // Use forwarding.
                imp = forward_imp;
                break;
             }
// Superclass cache.
imp = cache_getImp(curClass, sel);
复制代码

	STATIC_ENTRY _cache_getImp

	GetClassFromIsa_p16 p0, 0
	CacheLookup GETIMP, _cache_getImp, LGetImpMissDynamic, LGetImpMissConstant

LGetImpMissDynamic:
	mov	p0, #0
	ret

LGetImpMissConstant:
	mov	p0, p2
	ret

	END_ENTRY _cache_getImp
复制代码

如果NSObject中还没有方法，父类已经为nil，则调用imp = forward_imp，也就是_objc_msgForward_impcache(第1步时的赋值)，跳出循环，报错...unrecognized selector sent...。

        STATIC_ENTRY __objc_msgForward_impcache

	// No stret specialization.
	b	__objc_msgForward

	END_ENTRY __objc_msgForward_impcache

	
	ENTRY __objc_msgForward

	adrp	x17, __objc_forward_handler@PAGE
	ldr	p17, [x17, __objc_forward_handler@PAGEOFF]
	TailCallFunctionPointer x17
	
	END_ENTRY __objc_msgForward
        
复制代码

objc_defaultForwardHandler(id self, SEL sel)
{
    _objc_fatal("%c[%s %s]: unrecognized selector sent to instance %p "
                "(no message forward handler is installed)", 
                class_isMetaClass(object_getClass(self)) ? '+' : '-', 
                object_getClassName(self), sel_getName(sel), self);
}
void *_objc_forward_handler = (void*)objc_defaultForwardHandler;
复制代码

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

THE END

IOS