阅读 127

objc_msgSend分析-慢速查找

**阅读此文需要对于objc_object、objc_class以及结构体内部cache_t有一定的了解。 **

环境:xcode 11.5

源码:objc4-781

上文分析了objc_msgSend发送消息时的快速查找,主要流程是在汇编代码中执行,当快速查找没有找到时,将会执行慢速查找流程__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 p16 is the class to search
	
	MethodTableLookup
	TailCallFunctionPointer x17

	END_ENTRY __objc_msgSend_uncached
复制代码

__objc_msgSend_uncached通过MethodTableLookup来进行方法的查找,再执行TailCallFunctionPointer

.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
    // x16 = isa, #3 = LOOKUP_INITIALIZE | LOOKUP_RESOLVER
	mov	x2, x16
	mov	x3, #3
    // x0 = receiver x1 = selector x2 = class x3 = LOOKUP_INITIALIZE | LOOKUP_RESOLVER
    // 执行_lookUpImpOrForward
	bl	_lookUpImpOrForward
	// 返回值位于x0中
	// 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
复制代码

使用代码验证上述流程: 在断点处查看汇编代码: 点击control+stepinto可以进入objc_msgSend 进入_objc_msgSend_uncached 最终执行了lookUpImpOrForward,代码位于objc-runtime-new.mm:6095行

lookUpImpOrForward

// 
参数如下:
x0 = receiver 
x1 = selector 
x2 = class 
x3 = LOOKUP_INITIALIZE | LOOKUP_RESOLVER
根据不同的behavior会执行不同的分支

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

    // Optimistic cache lookup
    // 如果behavior标识符需要再查找缓存的话,重新查找一遍缓存
    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);
        // runtimeLock may have been dropped but is now locked again
    }

    if (slowpath((behavior & LOOKUP_INITIALIZE) && !cls->isInitialized())) {
    	// 如果没有初始化,需要初始化,会执行+initialize方法。
        cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
    }

    runtimeLock.assertLocked();
    curClass = cls;

    for (unsigned attempts = unreasonableClassCount();;) {
        // curClass method list.
        // 在curClass中寻找方法,不在父类中寻找
        Method meth = getMethodNoSuper_nolock(curClass, sel);
        if (meth) {
            imp = meth->imp;
            goto done;
        }
	
        if (slowpath((curClass = curClass->superclass) == nil)) {
        	// 如果curClass的父类为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.
        // 如果父子类关系中有缓存在的话,attempts<0,发生异常
        if (slowpath(--attempts == 0)) {
            _objc_fatal("Memory corruption in class list.");
        }

        // Superclass cache.
        // 在父类缓存中查找缓存。
        imp = cache_getImp(curClass, sel);
        if (slowpath(imp == forward_imp)) {
        	//如果父类中发现了forward的imp,停止查找,不进行缓存,先调用这个类的方法解析。
            break;
        }
        if (fastpath(imp)) {
            // 在父类中找到了方法实现,缓存到当前class即receiver对应的class中
            goto done;
        }
    }

    // No implementation found. Try method resolver once.
	 (behavior = 11) & 10 = 10
     behavior = 11 ^ 10 = 01
     behavior = 01 & 10 = 0
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
    	// 表示此处代码在本次流程中只会执行一次
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

 done:
 	// 存储sel以及imp到当前cls的缓存中去,此处衔接到cache_t的存储方法部分。
    log_and_fill_cache(cls, imp, sel, inst, curClass);
    runtimeLock.unlock();
 done_nolock:
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
    	// 如果当前behavior属于LOOKUP_NIL并且找到了forward_imp,返回空。
        return nil;
    }
    return imp;
}
复制代码

整体流程图大致如下所示:

慢速查找中,behavior的值为:LOOKUP_INITIALIZE | LOOKUP_RESOLVER

_objc_msgForward_impcache

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
复制代码
// Default forward handler halts the process.
__attribute__((noreturn, cold)) void
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;
复制代码

_objc_msgForward_impcache会调用objc_forward_handler,在该函数的实现中发现了一些熟悉的信息:unrecognized selector sent to instance

_cache_getImp

改方法位于汇编代码中,获取对应的isa,通过CacheLookup进行方法查找,需要注意的是这一次的查找和快速查找有些区别,参数为GETIMP,因此查找过程中并不会触发__objc_msgSend_uncached方法。

STATIC_ENTRY _cache_getImp

	GetClassFromIsa_p16 p0
	CacheLookup GETIMP, _cache_getImp
复制代码

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

该方法会在当前类cls的方法列表中查找sel对应的method

我们可以看到方法列表是一个类似二维数组的结构。

其核心方法为search_method_list_inline

ALWAYS_INLINE static method_t *
search_method_list_inline(const method_list_t *mlist, SEL sel)
{
    int methodListIsFixedUp = mlist->isFixedUp();
    int methodListHasExpectedSize = mlist->entsize() == sizeof(method_t);
    
    if (fastpath(methodListIsFixedUp && methodListHasExpectedSize)) {
        return findMethodInSortedMethodList(sel, mlist);
    } else {
        // Linear search of unsorted method list
        for (auto& meth : *mlist) {
            if (meth.name == sel) return &meth;
        }
    }
    #if DEBUG
   	...
    #endif
    return nil;
}
复制代码

调用了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) {
    	// count >> 1等价于 count/2, 通过指针平移找到list中间位置的method probe
        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;
        }
        // 要查找的方法>中间位置,base=probe+1
        if (keyValue > probeValue) {
            base = probe + 1;
            count--;
        }
        // 此时还有一种情况就是 keyValue < probeValue。在循环的开始probe = base + (count >> 1),可以获得正确的中位数
    }
    
    return nil;
}
复制代码

getMethodNoSuper_nolock本质上是利用了二分查找从cls内部的方法列表中进行查找。