慢速查找-匯編部分
在objc-msg-arm64.s文件中查找__objc_msgSend_uncached的匯編實(shí)現(xiàn)盆顾，其中的核心是MethodTableLookup（即查詢方法列表）佑刷，其源碼如下
.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
其中的核心是_lookUpImpOrForward，上述匯編的過(guò)程，可以通過(guò)匯編調(diào)試來(lái)驗(yàn)證
在main中嚣潜，例如[person sayHello]對(duì)象方法調(diào)用處加一個(gè)斷點(diǎn)懒棉，并且開啟匯編調(diào)試【Debug -- Debug worlflow -- 勾選Always show Disassembly】，運(yùn)行程序
匯編中objc_msgSend加一個(gè)斷點(diǎn)该抒，執(zhí)行斷住慌洪，按住control + stepinto，進(jìn)入objc_msgSend的匯編：
在_objc_msgSend_uncached加一個(gè)斷點(diǎn)凑保，執(zhí)行斷住冈爹，按住control + stepinto，進(jìn)入?yún)R編
慢速查找-C/C++部分
根據(jù)匯編部分的提示欧引，全局續(xù)搜索lookUpImpOrForward频伤，最后在objc-runtime-new.mm文件中找到了源碼實(shí)現(xiàn)，這是一個(gè)c實(shí)現(xiàn)的函數(shù)
IM PlookUpImpOrForward(id?inst,SEL?sel,Class cls,int?behavior)
{
? ? const IMP forward_imp = (IMP)_objc_msgForward_impcache;
? ? IMP?imp =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);
? ? ? ? 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;
}
其整體的慢速查找流程如圖所示：
主要有以下幾步：
1.cache緩存中進(jìn)行查找芝此，即快速查找憋肖，找到則直接返回imp，反之婚苹，則進(jìn)入第2步
2.判斷cls是否是已知類岸更，如果不是，則報(bào)錯(cuò)膊升；類是否實(shí)現(xiàn)坐慰，如果沒有，則需要先實(shí)現(xiàn)，確定其父類鏈结胀，此時(shí)實(shí)例化的目的是為了確定父類鏈赞咙，方法后續(xù)的循環(huán)，是否初始化糟港，如果沒有攀操，則初始化
3.for循環(huán)，按照類繼承鏈 或者 元類繼承鏈的順序查找
當(dāng)前cls的方法列表中使用二分查找算法查找方法秸抚，如果找到速和，則進(jìn)入cache寫入流程并返回imp，如果沒有找到剥汤，則返回nil當(dāng)前cls被賦值為父類颠放，如果父類等于nil，則imp = 消息轉(zhuǎn)發(fā)吭敢，并終止遞歸碰凶，進(jìn)入第4步
如果父類鏈中存在循環(huán)，則報(bào)錯(cuò)鹿驼，終止循環(huán)
父類緩存中查找方法
如果未找到欲低，則直接返回nil，繼續(xù)循環(huán)查找
如果找到畜晰，則直接返回imp砾莱，執(zhí)行cache寫入流程
4.判斷是否執(zhí)行過(guò)動(dòng)態(tài)方法解析
，如果沒有凄鼻，執(zhí)行動(dòng)態(tài)方法解析
如果執(zhí)行過(guò)一次動(dòng)態(tài)方法解析腊瑟，則走到消息轉(zhuǎn)發(fā)流程
getMethodNoSuper_nolock方法：二分查找方法列表
查找方法列表的流程如下所示：
其二分查找核心的源碼實(shí)現(xiàn)如下：
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; //key 等于 say666
? ? uint32_t count;
? ? //base相當(dāng)于low，count是max块蚌，probe是middle闰非，這就是二分
? ? for (count = list->count; count != 0; count >>= 1) {
? ? ? ? //從首地址+下標(biāo) --> 移動(dòng)到中間位置（count >> 1 左移1位即 count/2 = 4）
? ? ? ? probe = base + (count >> 1);
? ? ? ? uintptr_t probeValue = (uintptr_t)probe->name;
? ? ? ? //如果查找的key的keyvalue等于中間位置（probe）的probeValue，則直接返回中間位置
? ? ? ? if (keyValue == probeValue) {
? ? ? ? ? ? // -- while 平移 -- 排除分類重名方法
? ? ? ? ? ? while (probe > first && keyValue == (uintptr_t)probe[-1].name) {
? ? ? ? ? ? ? ? //排除分類重名方法（方法的存儲(chǔ)是先存儲(chǔ)類方法匈子，在存儲(chǔ)分類---按照先進(jìn)后出的原則河胎，分類方法最先出，而我們要取的類方法虎敦，所以需要先排除分類方法）
? ? ? ? ? ? ? ? //如果是兩個(gè)分類游岳，就看誰(shuí)先進(jìn)行加載
? ? ? ? ? ? ? ? probe--;
? ? ? ? ? ? }
? ? ? ? ? ? return (method_t *)probe;
? ? ? ? }
? ? ? ? //如果keyValue 大于 probeValue，就往probe即中間位置的右邊查找
? ? ? ? if (keyValue > probeValue) {
? ? ? ? ? ? base = probe + 1;
? ? ? ? ? ? count--;
? ? ? ? }
? ? }
? ? return nil;
}
算法原理簡(jiǎn)述為：從第一次查找開始其徙，每次都取中間位置胚迫，與想查找的key的value值作比較，如果相等唾那，則需要排除分類方法访锻，然后將查詢到的位置的方法實(shí)現(xiàn)返回，如果不相等，則需要繼續(xù)二分查找期犬，如果循環(huán)至count = 0還是沒有找到河哑，則直接返回nil，如下所示：
以查找LGPerson類的say666實(shí)例方法為例龟虎，其二分查找過(guò)程如下
cache_getImp方法：父類緩存查找
cache_getImp方法是通過(guò)匯編_cache_getImp實(shí)現(xiàn)璃谨，傳入的$0?是?GETIMP，如下所示：
如果父類緩存中找到了方法實(shí)現(xiàn)鲤妥，則跳轉(zhuǎn)至CacheHit即命中佳吞，則直接返回imp
如果在父類緩存中，沒有找到方法實(shí)現(xiàn)棉安，則跳轉(zhuǎn)至CheckMiss或者JumpMiss底扳，通過(guò)判斷$0跳轉(zhuǎn)至LGetImpMiss，直接返回nil
總結(jié)
對(duì)于對(duì)象方法（即實(shí)例方法）贡耽，即在類中查找衷模，其慢速查找的父類鏈?zhǔn)牵侯?-父類--根類--nil
對(duì)于類方法，即在元類中查找菇爪，其慢速查找的父類鏈?zhǔn)牵涸?-根元類--根類--nil
