iOS底层探究:objc_msgSend流程分析的慢速查找

objc_msgSend慢速查找流程：系统先按照快速查找流程走的，如果快速的查找不到，然后进入到慢速查找流程里面。下面是慢速查找到到流程分析。

➢ 在配置好到objc4-781源码项目中导航面板区搜索objc_msgSend找到objc-msg-arm64.s文件，然后定位到 STATIC_ENTRY __objc_msgSend_uncached部分，通过查看得出__objc_msgSend_uncached汇编实现的核心MethodTableLookup,源码如下：

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的汇编实现，发现核心代码是_loopUpImpOrForward,下面是其源码内容：

.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

mov x2, x16

mov x3,#3

bl _lookUpImpOrForward

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

上面是通过汇编源码查看得出的，我们也可以通过汇编调试来验证上述部分，下面我们来一同看看汇编调试

➢ 我们以main为例：在类对象[person sayHello]这一行加一个断点，运行项目此时来到[person sayHello]断点这一行（如下图一），运用汇编调试方式（图二），在debug区汇编代码处就可以看到objc_msgSend（图三）这行代码，下面附上截图可以直观感受下：

图一

图二

图三

➢ 此时我们继续跟汇编继续走流程：汇编处objc_msgSend（如上图三）这行加一断点，然后断到该行，此时按住键盘control键+鼠标点住stepinto（如下图四），进入到objc_msgSend汇编（下图五）：

图四

图五

➢ 此时来到来_objc_msgSend_uncached处，在此行加一断点，继续control+setpinto，此时来到了lookUpImpOrForward（如下图七）汇编区：

图七

注释：

① C/C++中调用汇编，去查找会变时，C/C++调用的方法前面需要多加一个下划线

② 汇编中调用C/C++方式时，去查找C/C++方法，需要将汇编调用到方法前面去掉一个下划线

➢ 慢速查找C/C++部分

➢ 根据汇编部分到提示，导航面板区全局搜索lookUpImpOrForward，进一步查找发现其藏到来objc-runtime-new.mm文件中，下面是其源码实现（c函数）：

/***********************************************************************

* lookUpImpOrForward.

* The standard IMP lookup.

* Without LOOKUP_INITIALIZE: tries to avoid +initialize (but sometimes fails)

* Without LOOKUP_CACHE: skips optimistic unlocked lookup (but uses cache elsewhere)

* Most callers should use LOOKUP_INITIALIZE and LOOKUP_CACHE

* inst is an instance of cls or a subclass thereof, or nil if none is known.

* If cls is an un-initialized metaclass then a non-nil inst is faster.

* May return _objc_msgForward_impcache. IMPs destined for external use

* must be converted to _objc_msgForward or _objc_msgForward_stret.

* If you don't want forwarding at all, use LOOKUP_NIL.

**********************************************************************/

IMPlookUpImpOrForward(idinst,SELsel,Classcls,intbehavior)

{

const IMP forward_imp = (IMP)_objc_msgForward_impcache;

IMPimp =nil;

ClasscurClass;

runtimeLock.assertUnlocked();

// Optimistic cache lookup

if(fastpath(behavior &LOOKUP_CACHE)) {

imp =cache_getImp(cls, sel);

if(imp)gotodone_nolock;

}

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

//

// TODO: this check is quite costly during process startup.

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

cls =initializeAndLeaveLocked(cls, inst,runtimeLock);

// runtimeLock may have been dropped but is now locked again

// If sel == initialize, class_initialize will send +initialize and

// then the messenger will send +initialize again after this

// procedure finishes. Of course, if this is not being called

// from the messenger then it won't happen. 2778172

}

runtimeLock.assertLocked();

curClass = cls;

// The code used to lookpu 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(unsignedattempts =unreasonableClassCount();;) {

// curClass method list.

Methodmeth =getMethodNoSuper_nolock(curClass, sel);

if(meth) {

imp = meth->imp;

gotodone;

}

if(slowpath((curClass = curClass->superclass) ==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); // 有问题???? cache_getImp - lookup - lookUpImpOrForward

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.

gotodone;

}

}

// No implementation found. Try method resolver once.

if(slowpath(behavior &LOOKUP_RESOLVER)) {

behavior ^=LOOKUP_RESOLVER;

returnresolveMethod_locked(inst, sel, cls, behavior);

}

done:

log_and_fill_cache(cls, imp, sel, inst, curClass);

runtimeLock.unlock();

done_nolock:

if(slowpath((behavior &LOOKUP_NIL) && imp == forward_imp)) {

returnnil;

}

returnimp;

}

通过分析上面到源码实现得出整体到慢速流程图如下图八：

图八

➢下面是慢速流程图详细分析

⒈cache缓存中进行快速查找，如果找到则直接返回imp，否则进入第二步

⒉判断cls是否是已知类，如果不是就报错；类是否实现，如果没有则需要先实现，然后确定去父链，此时实例化的目的是为了确定父链、ro、rw等，方便方法后续数据的查找以及查找的循环；是否初始化，如果没有，则初始化

⒊for循环，按照类类继承链或者元类继承链的顺序查找：当前cls的方法列表中使用二分查找算法查找方法，如果找到，则进入cache写入流程，并返回imp，如果找不到就返回nil；当前cls被赋值为父类，如果父类为nil，则imp=消息转发，并中指递归，进入第四步；如果父类中存在循环，则报错终止循环；父类中查找方法（如果未找到，则直接返回nil，继续循环查找，如果找到，则返回imp，进行cache写入，方便后续的查找）

⒋判断是否执行过动态方法解析：如果没有，则执行动态方法解析；如果执行过一次动态方法解析，则走到消息转发流程

以上是方法的慢速查找流程，下面拓展下二分查找原理以及父类缓存查找详细步骤

➢ getMethodNoSuper_nolock方法：二分查找方法列表流程图以及核心源码如下：

二分方法查找流程图

/***********************************************************************

* search_method_list_inline

**********************************************************************/

ALWAYS_INLINE static method_t *

findMethodInSortedMethodList(SEL key, const method_list_t *list)

{

ASSERT(list);

constmethod_t*constfirst = &list->first;

constmethod_t*base = first;

constmethod_t*probe;

uintptr_tkeyValue = (uintptr_t)key;

uint32_tcount;

for(count = list->count; count !=0; count >>=1) {

probe = base + (count >>1);

uintptr_tprobeValue = (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;

}

if(keyValue > probeValue) {

base = probe +1;

count--;

}

}

return nil;

}

注释：

算法原理：从第一次开始查找，每次曲中间位置，与查找的key的value做对比，如果相等则需要排除分类方法，然后将查询到的位置发方法实现返回；如果不相等，则需要继续二分查找，如果循环至count=0还是没有找到，则直接返回nil，这里借用下网上的图片（图九）：

图九

以查找LGPerson类的say666实例方法为例，其二分查找过程如图十：

图十

➢ cache_getImp方法：父类缓存查找

cache_getImp方法是通过汇编_cache_getImp实现的，传入的$0是getImp，如下图十一：

图十一

⒜ 如果父类找到了方法实现，则CacheHit命中，直接返回imp

⒝ 如果父类缓存中没有找到方法实现，则CheckMiss或者JumpMiss，通过$0跳转至LGetImpMiss，直接返回nil

❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖

总结

❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖❖

☞ 对于对象方法，即在类中查找，其慢速查找的父类链是：类➛父类➛根类➛nil

☞ 对于类方法，，即在元类中查找（类方法在元类中是以对象方法的形式存在的），其慢速查找的父类链是：元类➛根元类➛根类➛nil

☞ 如果快速查找和慢速查找都没有找到方法的实现，则需要走动态方法决议（苹果爸爸给了开发者后悔的补救措施）

➢ 如果动态方法决议仍然没有找到，则进行消息转发（下一篇进行讲解，敬请期待）