手把手带你探索Runtime底层原理(一)方法查找

Runtime简单介绍

Objective-C 是一个动态语言，这意味着它不仅需要一个编译器，也需要一个运行时系统来动态得创建类和对象、进行消息传递和转发。理解 Objective-C 的 Runtime 机制可以帮我们更好的了解这个语言，适当的时候还能对语言进行扩展，从系统层面解决项目中的一些设计或技术问题。了解 Runtime ，要先了解它的核心 - 消息传递 （Messaging）。

Runtime 基本是用 C 和汇编写的，可见苹果为了动态系统的高效而作出的努力。你可以在这里 密码:tuw8 下到苹果维护的开源代码。苹果和 GNU 各自维护一个开源的 runtime 版本，这两个版本之间都在努力的保持一致。

Runtime消息发送

一个对象的方法像这样[obj foo]，通过 clang -rewrite-objc命令查看编译后的代码(由于之前的文章操作过，这里不详细解释操作流程了)，编译器转成消息发送objc_msgSend(obj, foo)

objc_msgsend 底层有两种查找方式:

• 快速查找: 通过汇编直接在缓存中找到这个方法并调用
• 慢速查找: 通过c,c++以及汇编一起完成的

为什么要使用汇编？

1. 汇编通过一个函数保留未知参数，然后跳转到任意的指针，可以直接使用寄存器保存，而C无法实现
2. 汇编代码执行的效率高，执行的时间周期准确

快速查找

先在刚刚提供的objc源码里查找objc_msgSend，找到我们常用的架构arm64汇编文件，可以看到ENTRY _objc_msgSend，其实就是这个函数的入口

1._objc_msgSend入口

ENTRY _objc_msgSend
	UNWIND _objc_msgSend, NoFrame

	cmp	p0, #0			// nil check and tagged pointer check
#if SUPPORT_TAGGED_POINTERS
	b.le	LNilOrTagged		//  (MSB tagged pointer looks negative)
#else
	b.eq	LReturnZero
#endif
	ldr	p13, [x0]		// p13 = isa
	GetClassFromIsa_p16 p13		// p16 = class
LGetIsaDone:
	CacheLookup NORMAL		// calls imp or objc_msgSend_uncached

#if SUPPORT_TAGGED_POINTERS
LNilOrTagged:
	b.eq	LReturnZero		// nil check

	// tagged
	adrp	x10, _objc_debug_taggedpointer_classes@PAGE
	add	x10, x10, _objc_debug_taggedpointer_classes@PAGEOFF
	ubfx	x11, x0, #60, #4
	ldr	x16, [x10, x11, LSL #3]
	adrp	x10, _OBJC_CLASS_$___NSUnrecognizedTaggedPointer@PAGE
	add	x10, x10, _OBJC_CLASS_$___NSUnrecognizedTaggedPointer@PAGEOFF
	cmp	x10, x16
	b.ne	LGetIsaDone

	// ext tagged
	adrp	x10, _objc_debug_taggedpointer_ext_classes@PAGE
	add	x10, x10, _objc_debug_taggedpointer_ext_classes@PAGEOFF
	ubfx	x11, x0, #52, #8
	ldr	x16, [x10, x11, LSL #3]
	b	LGetIsaDone
// SUPPORT_TAGGED_POINTERS
#endif

LReturnZero:
	// x0 is already zero
	mov	x1, #0
	movi	d0, #0
	movi	d1, #0
	movi	d2, #0
	movi	d3, #0
	ret

	END_ENTRY _objc_msgSend

可能看不懂汇编，根据注释大概推测其意思,下面的代码主要做了非空检查和无标记指针检查(如果指针小于等于 LNilOrTagged 直接return返回)

cmp	p0, #0			// nil check and tagged pointer check
#if SUPPORT_TAGGED_POINTERS
	b.le	LNilOrTagged		//  (MSB tagged pointer looks negative)
#else
	b.eq	LReturnZero
#endif

接下来看如下代码，根据isa获取这个类，LGetIsaDone是表示isa处理完毕，CacheLookup NORMAL表示直接调用当前的imp或者发送objc_msgSend_uncached无缓存消息

	ldr	p13, [x0]		// p13 = isa
	GetClassFromIsa_p16 p13		// p16 = class
LGetIsaDone:
	CacheLookup NORMAL		// calls imp or objc_msgSend_uncached

2. CacheLookup宏定义

在当前文件里搜索CacheLookup，来到它的宏定义

.macro CacheLookup
	// p1 = SEL, p16 = isa
	ldp	p10, p11, [x16, #CACHE]	// p10 = buckets, p11 = occupied|mask
#if !__LP64__
	and	w11, w11, 0xffff	// p11 = mask
#endif
	and	w12, w1, w11		// x12 = _cmd & mask
	add	p12, p10, p12, LSL #(1+PTRSHIFT)
		             // p12 = buckets + ((_cmd & mask) << (1+PTRSHIFT))

	ldp	p17, p9, [x12]		// {imp, sel} = *bucket
1:	cmp	p9, p1			// if (bucket->sel != _cmd)
	b.ne	2f			//     scan more
	CacheHit $0			// call or return imp
	
2:	// not hit: p12 = not-hit bucket
	CheckMiss $0			// miss if bucket->sel == 0
	cmp	p12, p10		// wrap if bucket == buckets
	b.eq	3f
	ldp	p17, p9, [x12, #-BUCKET_SIZE]!	// {imp, sel} = *--bucket
	b	1b			// loop

3:	// wrap: p12 = first bucket, w11 = mask
	add	p12, p12, w11, UXTW #(1+PTRSHIFT)
		                        // p12 = buckets + (mask << 1+PTRSHIFT)

	// Clone scanning loop to miss instead of hang when cache is corrupt.
	// The slow path may detect any corruption and halt later.

	ldp	p17, p9, [x12]		// {imp, sel} = *bucket
1:	cmp	p9, p1			// if (bucket->sel != _cmd)
	b.ne	2f			//     scan more
	CacheHit $0			// call or return imp
	
2:	// not hit: p12 = not-hit bucket
	CheckMiss $0			// miss if bucket->sel == 0
	cmp	p12, p10		// wrap if bucket == buckets
	b.eq	3f
	ldp	p17, p9, [x12, #-BUCKET_SIZE]!	// {imp, sel} = *--bucket
	b	1b			// loop

3:	// double wrap
	JumpMiss $0
	
.endmacro

在CacheLookup宏定义这里

• CacheHit: 缓存命中，方法的实现IMP在寄存器中，然后传递出去
• CheckMiss: 缓存没命中，发送_objc_msgSend_uncached
• add: 如果缓存里没找到，去其他地方查找到该方法实现后添加到缓存

  

3. CacheHit 和 CheckMiss

.macro CacheHit
.if $0 == NORMAL
	TailCallCachedImp x17, x12	// authenticate and call imp
.elseif $0 == GETIMP
	mov	p0, p17
	AuthAndResignAsIMP x0, x12	// authenticate imp and re-sign as IMP
	ret				// return IMP
.elseif $0 == LOOKUP
	AuthAndResignAsIMP x17, x12	// authenticate imp and re-sign as IMP
	ret				// return imp via x17
.else
.abort oops
.endif
.endmacro

看到CacheHit的宏定义: 在上面调用的时候，传递过来的是NORMAL，执行了TailCallCachedImp,即如果缓存命中的话，则返回缓存里的IMP.

.macro CheckMiss
	// miss if bucket->sel == 0
.if $0 == GETIMP
	cbz	p9, LGetImpMiss
.elseif $0 == NORMAL
	cbz	p9, __objc_msgSend_uncached
.elseif $0 == LOOKUP
	cbz	p9, __objc_msgLookup_uncached
.else
.abort oops
.endif
.endmacro

再看到CheckMiss的宏定义:在上面调用的是NORMAL，所以这里会发送__objc_msgSend_uncached的消息

4.__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

发现这里调用了MethodTableLookup,所以继续跟进查看

.macro MethodTableLookup
	
	// 省略
	// 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)]
	// receiver and selector already in x0 and x1
	mov	x2, x16
	bl	__class_lookupMethodAndLoadCache3
	//省略

.endmacro

• 前面后面的汇编代码只能看到有做字节对齐的操作，不过由于不懂汇编，具体做什么不是很清楚，不过看到了跳转进了一个非常重要的函数__class_lookupMethodAndLoadCache3

• 继续搜索__class_lookupMethodAndLoadCache3发现并不能在当前汇编文件里找到声明，这时猜想会不会是跳转到了代码里

• 于是全局搜索class_lookupMethodAndLoadCache3,果然在objc-runtime-new.mm文件里找到了它的函数实现

IMP _class_lookupMethodAndLoadCache3(id obj, SEL sel, Class cls)
{
    return lookUpImpOrForward(cls, sel, obj, 
                              YES/*initialize*/, NO/*cache*/, YES/*resolver*/);
}

所以这里通过调用lookUpImpOrForward开启了慢速查找的过程

快速查找总结

慢速查找

来到lookUpImpOrForward函数的方法实现源码

IMP lookUpImpOrForward(Class cls, SEL sel, id inst, 
                       bool initialize, bool cache, bool resolver)
{
     IMP imp = nil;
    bool triedResolver = NO;
    runtimeLock.assertUnlocked();

    // Optimistic cache lookup
    // 查找缓存！！！
    if (cache) {
        //汇编代码的方式实现的！
        imp = cache_getImp(cls, sel);
        if (imp) return imp;
    }

    runtimeLock.lock();
    checkIsKnownClass(cls);

    if (!cls->isRealized()) {
        realizeClass(cls);
    }

    if (initialize  &&  !cls->isInitialized()) {
        runtimeLock.unlock();
        _class_initialize (_class_getNonMetaClass(cls, inst));
        runtimeLock.lock();
    }
    //先省略
}

• 首先分析一下从传递进来的三个参数，根据注释 initialize为YES，cache为NO,resolver为YES
• 首先解释一下为什么汇编传递的三个参数为这几个值？在上面分析的汇编里，LGetIsaDone这个判断是在isa处理完毕后才走缓存查找的汇编代码的，所以这个类是加载解析好的，即initialize和resolver都为YES，cache为NO是因为在汇编里快速查找没有找到方法缓存才会执行到这里，所以这里肯定为NO
• 接下来看到这里判断是否有缓存，如果有直接调用汇编里的cache_getImp去获取imp，由于传递进来的cache为NO，所以这里不会执行

// Optimistic cache lookup
    // 查找缓存！！！
    if (cache) {
        //汇编代码的方式实现的！
        imp = cache_getImp(cls, sel);
        if (imp) return imp;
    }
    
    //汇编代码(在之前上面的汇编文件里)
    STATIC_ENTRY _cache_getImp
    GetClassFromIsa_p16 p0
	 CacheLookup GETIMP

• 继续看下去checkIsKnownClass(cls);检查这个类是否已知，如果未知则抛出异常
• 接下来判断类有没有实现和有没有初始化，没有则调用实现方法realizeClass(cls)和初始化方法_class_initialize (_class_getNonMetaClass(cls, inst));

慢速查找重点:retry

在lookUpImpOrForward里还有retry相关的代码，继续分析

retry:    
    runtimeLock.assertLocked();

    // Try this class's cache.

    imp = cache_getImp(cls, sel);
    if (imp) goto done;

    // Try this class's method lists.
    {
        //Method（SEL IMP）
        Method meth = getMethodNoSuper_nolock(cls, sel);
        if (meth) {
            log_and_fill_cache(cls, meth->imp, sel, inst, cls);
            imp = meth->imp;
            goto done;
        }
    }

    // Try superclass caches and method lists.
    {
        unsigned attempts = unreasonableClassCount();
        for (Class curClass = cls->superclass;
             curClass != nil;
             curClass = curClass->superclass)
        {
            // Halt if there is a cycle in the superclass chain.
            if (--attempts == 0) {
                _objc_fatal("Memory corruption in class list.");
            }
            
            // Superclass cache.
            imp = cache_getImp(curClass, sel);
            if (imp) {
                if (imp != (IMP)_objc_msgForward_impcache) {
                    // Found the method in a superclass. Cache it in this class.
                    log_and_fill_cache(cls, imp, sel, inst, curClass);
                    goto done;
                }
                else {
                    // Found a forward:: entry in a superclass.
                    // Stop searching, but don't cache yet; call method 
                    // resolver for this class first.
                    break;
                }
            }
            
            // Superclass method list.
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {
                log_and_fill_cache(cls, meth->imp, sel, inst, curClass);
                imp = meth->imp;
                goto done;
            }
        }
    }

    // No implementation found. Try method resolver once.

    if (resolver  &&  !triedResolver) {
        runtimeLock.unlock();
        _class_resolveMethod(cls, sel, inst);
        runtimeLock.lock();
        // Don't cache the result; we don't hold the lock so it may have 
        // changed already. Re-do the search from scratch instead.
        triedResolver = YES;
        goto retry;
    }

    // No implementation found, and method resolver didn't help. 
    // Use forwarding.
    //_objc_msgForward
    imp = (IMP)_objc_msgForward_impcache;
    cache_fill(cls, sel, imp, inst);

 done:
    runtimeLock.unlock();

    return imp;

1. 第一步看到这里再一次调用了cache_getImp(cls, sel);去从缓存中获取imp，传递进来明明已经知道是NO了，为什么再去查找一次呢?

2. 在objc_init的时候有一个函数remap(cls)，在汇编最开始查找该方法的时候如果没有方法缓存，但可能会在这个类初始化方法objc_init的过程中，对这个类进行了重映射remap，即把该方法添加到方法缓存里了，所以这里要再去查找一次cache有缓存就可能会节省很多时间

3. 接下来先从当前类的方法列表method_list去找，找到了就log_and_fill_cache打印日志并把方法添加到缓存中

4. 如果没找到则继续找父类的缓存cache_getImp(curClass, sel)，再找父类的方法列表，和之前在本类的查找顺序一样,找到了也是添加到方法缓存log_and_fill_cache

5. 慢速查找到上面已经结束了，由于上面整个过程比较慢，所以一般称为慢速。如果没有找到imp,则进行动态方法解析和消息转发，篇幅原因，接下来的这个过程在Runtime底层原理(二)动态方法解析和消息转发

慢速查找总结

以上均为个人探索源码的理解和所得，如有错误请指正，欢迎讨论。