iOS底層之objc_msgSend消息快速查找

前言

在上一篇文章iOS底層之cache_t探索中完残，我們了解了方法寫入cache中的流程，接下來我們了解些方法從cache中讀的流程。

了解Runtime

runtime稱為運行時，它區(qū)別于編譯時

運行時是代碼跑起來晌砾，被裝載到內(nèi)存中的過程，如果此時出錯烦磁，則程序會崩潰养匈，是一個動態(tài)階段
編譯時是源代碼翻譯成機器能識別的代碼的過程，主要是對語言進行最基本的檢查報錯都伪，即詞法分析呕乎、語法分析等，是一個靜態(tài)的階段

runtime 交互有三種方式

Objective-C Code直接調(diào)用例：[obj run]等
Framework&Service 例：NSSelectorFromString陨晶、isKindeofClass楣嘁、isMemberOfClass等
RuntimeAPI 例：class_getInstanceSize等

runtime與底層的關(guān)系

Runtime三種方式及底層的關(guān)系

其中的compiler就是我們了解的編譯器，即LLVM珍逸，例如OC的alloc對應(yīng)底層的objc_alloc逐虚， runtime system library 就是底層庫。

探索方法的本質(zhì)

方法的底層實現(xiàn)

在iOS底層之類的重要組成部分-isa結(jié)構(gòu)體分析這篇文章中谆膳，我們了解到可以通過clang命令將main.m文件編譯成main.cpp文件來看底層源碼實現(xiàn)叭爱。接下來我們我可以得到如下代碼

//main.m中方法的調(diào)用
WJPerson *person = [WJPerson alloc];
[person sayHello];
[person sayThanksYou];

//??clang編譯后的底層實現(xiàn)
WJPerson *person = ((WJPerson *(*)(id, SEL))(void *)objc_msgSend)((id)objc_getClass("WJPerson"), sel_registerName("alloc"));
((void (*)(id, SEL))(void *)objc_msgSend)((id)person, sel_registerName("sayHello"));
((void (*)(id, SEL))(void *)objc_msgSend)((id)person, sel_registerName("sayThanksYou"));

通過上述代碼可以看出，方法的本質(zhì)就是objc_msgSend消息發(fā)送漱病。
接下來我們驗證一下通過objc_msgSend方法來完成[person sayHello]的調(diào)用买雾，查看其打印是否是一致把曼。main.m中的代碼如下

WJPerson *person = [WJPerson alloc];
[person sayHello];
[person sayThanksYou];
objc_msgSend(person,sel_registerName("sayHello"));

注
1、直接調(diào)用objc_msgSend漓穿，需要導(dǎo)入頭文件#import <objc/message.h>或#import <objc/runtime.h>
2嗤军、需要將target --> Build Setting -->搜索msg -- 將enable strict checking of obc_msgSend calls由YES改為NO，將嚴厲的檢查機制關(guān)掉晃危，否則objc_msgSend的參數(shù)會報錯

打印結(jié)果如下

objc_msgSend方法調(diào)用打印結(jié)果

父類與子類的方法之間的關(guān)聯(lián)

為了方便驗證叙赚，我們再創(chuàng)建一個WJTeacher類，繼承與WJPerson僚饭，在父類WJPerson中聲明并實現(xiàn)一個方法震叮，在子類WJTeacher中只聲明不實現(xiàn)這個方法

@interface WJPerson : NSObject

- (void)personDesc;

@end

@implementation WJPerson

- (void)personDesc{
    NSLog(@"I am person");
}

@end

@interface WJTeacher : WJPerson

- (void)personDesc;

@end

@implementation WJTeacher

@end

然后在main.m中使用oc代碼和runtime底層api objc_msgSendSuper分別調(diào)用一下這個方法

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        WJPerson *person = [WJPerson alloc];
        WJTeacher *teacher = [WJTeacher alloc];
        [teacher personDesc];
        
        struct objc_super wjsuper;
        wjsuper.receiver = teacher; //消息的接收者是teacher
        wjsuper.super_class = [WJPerson class]; //告訴父類是誰
            
        //消息的接受者還是自己 - 父類 - 請你直接找我的父親
        objc_msgSendSuper(&wjsuper, sel_registerName("personDesc"));
    }
    return 0;
}

最后結(jié)果如下圖所示

子類方法調(diào)用轉(zhuǎn)為執(zhí)行父類的實現(xiàn)的打印結(jié)果

由結(jié)果發(fā)現(xiàn)不論是[person sayHello]還是objc_msgSendSuper都執(zhí)行的是父類中sayHello的實現(xiàn)，所以這里鳍鸵，我們可以作一個猜測：方法調(diào)用苇瓣，首先是在類中查找，如果類中沒有找到偿乖，會到類的父類中查找击罪。
為了驗證我們的發(fā)現(xiàn)，我們分析一下底層源碼實現(xiàn)

objc_msgSend 快速查找流程分析

在objc4-781源碼中贪薪，搜索objc_msgSend媳禁，由于我們?nèi)粘ｉ_發(fā)的都是架構(gòu)是arm64，所以需要在arm64.s后綴的文件中查找objc_msgSend源碼實現(xiàn)古掏，搜索發(fā)現(xiàn)objc_msgSend方法的匯編起始位置為ENTRY _objc_msgSend

//---- 消息發(fā)送 -- 匯編入口--objc_msgSend主要是拿到接收者的isa信息
ENTRY _objc_msgSend 
//---- 無窗口
    UNWIND _objc_msgSend, NoFrame 
    
//---- p0 和空對比损话，即判斷接收者是否存在侦啸，其中p0是objc_msgSend的第一個參數(shù)-消息接收者receiver
    cmp p0, #0          // nil check and tagged pointer check 
//---- le小于 --支持taggedpointer（小對象類型）的流程
#if SUPPORT_TAGGED_POINTERS
    b.le    LNilOrTagged        //  (MSB tagged pointer looks negative) 
#else
//---- p0 等于 0 時槽唾，直接返回 空
    b.eq    LReturnZero 
#endif 
//---- p0即receiver 肯定存在的流程
//---- 根據(jù)對象拿出isa ，即從x0寄存器指向的地址 取出 isa光涂，存入 p13寄存器
    ldr p13, [x0]       // p13 = isa 
//---- 在64位架構(gòu)下通過 p16 = isa（p13） & ISA_MASK庞萍，拿出shiftcls信息，得到class信息
    GetClassFromIsa_p16 p13     // p16 = class 
LGetIsaDone:
    // calls imp or objc_msgSend_uncached 
//---- 如果有isa忘闻，走到CacheLookup 即緩存查找流程钝计，也就是所謂的sel-imp快速查找流程
    CacheLookup NORMAL, _objc_msgSend

#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

通過分析上述代碼我們可以總結(jié)一下：
【第一步】cmp p0, #0：先判斷接收者是否存在齐佳，如果不存在直接返回b.eq LReturnZero
【第二步】ldr p13, [x0]：如果接收者存在私恬，則取出對象的isa指針，然后通過GetClassFromIsa_p16 p13方法取出isa中的shiftcls位域信息炼吴，即class本鸣。

接下來我們看下 GetClassFromIsa_p16的源碼實現(xiàn)

.macro GetClassFromIsa_p16 /* src */
//---- 此處用于watchOS
#if SUPPORT_INDEXED_ISA 
    // Indexed isa
//---- 將isa的值存入p16寄存器
    mov p16, $0         // optimistically set dst = src 
    tbz p16, #ISA_INDEX_IS_NPI_BIT, 1f  // done if not non-pointer isa -- 判斷是否是 nonapointer isa
    // isa in p16 is indexed
//---- 將_objc_indexed_classes所在的頁的基址 讀入x10寄存器
    adrp    x10, _objc_indexed_classes@PAGE 
//---- x10 = x10 + _objc_indexed_classes(page中的偏移量) --x10基址 根據(jù) 偏移量 進行 內(nèi)存偏移
    add x10, x10, _objc_indexed_classes@PAGEOFF
//---- 從p16的第ISA_INDEX_SHIFT位開始，提取 ISA_INDEX_BITS 位 到 p16寄存器硅蹦，剩余的高位用0補充
    ubfx    p16, p16, #ISA_INDEX_SHIFT, #ISA_INDEX_BITS  // extract index 
    ldr p16, [x10, p16, UXTP #PTRSHIFT] // load class from array
1:

//--用于64位系統(tǒng)
#elif __LP64__ 
    // 64-bit packed isa
//---- p16 = class = isa & ISA_MASK(位運算 & 即獲取isa中的shiftcls信息)
    and p16, $0, #ISA_MASK 

#else
    // 32-bit raw isa ---- 用于32位系統(tǒng)
    mov p16, $0

#endif

.endmacro

從上述代碼中可以看到在arm64架構(gòu)下通過isa & ISA_MASK獲取shiftcls位域的類信息荣德。
【第三步】獲取到isa會進入到CacheLookup緩存查找流程

//Ｃ泼骸！ｄ陶啊＠鹉谩！Ｊ鹧省＝辍！艇抠！重點Ｄ宦！＜矣佟Ｒ彀！Ｐ踔亍Ｔ┦佟！Ｇ嗌恕６搅！狠角！
.macro CacheLookup 
    //
    // Restart protocol:
    //
    //   As soon as we're past the LLookupStart$1 label we may have loaded
    //   an invalid cache pointer or mask.
    //
    //   When task_restartable_ranges_synchronize() is called,
    //   (or when a signal hits us) before we're past LLookupEnd$1,
    //   then our PC will be reset to LLookupRecover$1 which forcefully
    //   jumps to the cache-miss codepath which have the following
    //   requirements:
    //
    //   GETIMP:
    //     The cache-miss is just returning NULL (setting x0 to 0)
    //
    //   NORMAL and LOOKUP:
    //   - x0 contains the receiver
    //   - x1 contains the selector
    //   - x16 contains the isa
    //   - other registers are set as per calling conventions
    //
LLookupStart$1:

//---- p1 = SEL, p16 = isa --- #define CACHE (2 * __SIZEOF_POINTER__)号杠，其中 __SIZEOF_POINTER__表示pointer的大小 ，即 2*8 = 16
//---- p11 = mask|buckets -- 從x16（即isa）中平移16字節(jié)丰歌，取出cache 存入p11寄存器 -- isa距離cache 正好16字節(jié)：isa（8字節(jié)）-superClass（8字節(jié)）-cache（mask高16位 + buckets低48位）
    ldr p11, [x16, #CACHE]              
//---- 64位真機
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 
//--- p11(cache) & 0x0000ffffffffffff 姨蟋，mask高16位抹零，得到buckets 存入p10寄存器-- 即去掉mask立帖，留下buckets
    and p10, p11, #0x0000ffffffffffff   // p10 = buckets 
    
//--- p11(cache)右移48位眼溶，得到mask（即p11 存儲mask），mask & p1(msgSend的第二個參數(shù) cmd-sel) 晓勇，得到sel-imp的下標index（即搜索下標） 存入p12（cache insert寫入時的哈希下標計算是 通過 sel & mask堂飞，讀取時也需要通過這種方式）
    and p12, p1, p11, LSR #48       // x12 = _cmd & mask 

//--- 非64位真機
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4 
    and p10, p11, #~0xf         // p10 = buckets
    and p11, p11, #0xf          // p11 = maskShift
    mov p12, #0xffff
    lsr p11, p12, p11               // p11 = mask = 0xffff >> p11
    and p12, p1, p11                // x12 = _cmd & mask
#else
#error Unsupported cache mask storage for ARM64.
#endif

//--- p12是下標 p10是buckets數(shù)組首地址，下標 * 1<<4(即16) 得到實際內(nèi)存的偏移量绑咱，通過buckets的首地址偏移绰筛，獲取bucket存入p12寄存器
//--- LSL #(1+PTRSHIFT)-- 實際含義就是得到一個bucket占用的內(nèi)存大小 -- 相當于mask = occupied -1-- _cmd & mask -- 取余數(shù)
    add p12, p10, p12, LSL #(1+PTRSHIFT)   
                     // p12 = buckets + ((_cmd & mask) << (1+PTRSHIFT)) -- PTRSHIFT是3
                     
//--- 從x12（即p12）中取出 bucket 分別將imp和sel 存入 p17（存儲imp） 和 p9（存儲sel）
    ldp p17, p9, [x12]      // {imp, sel} = *bucket 
    
//--- 比較 sel 與 p1（傳入的參數(shù)cmd）
1:  cmp p9, p1          // if (bucket->sel != _cmd) 
//--- 如果不相等，即沒有找到描融，請?zhí)D(zhuǎn)至 2f
    b.ne    2f          //     scan more 
//--- 如果相等 即cacheHit 緩存命中铝噩，直接返回imp
    CacheHit $0         // call or return imp 
    
2:  // not hit: p12 = not-hit bucket
//--- 如果一直都找不到， 因為是normal 稼稿，跳轉(zhuǎn)至__objc_msgSend_uncached
    CheckMiss $0            // miss if bucket->sel == 0 
//--- 判斷p12（下標對應(yīng)的bucket） 是否 等于 p10（buckets數(shù)組第一個元素薄榛，）讳窟，如果等于，則跳轉(zhuǎn)至第3步
    cmp p12, p10        // wrap if bucket == buckets 
//--- 定位到最后一個元素（即第一個bucket）
    b.eq    3f 
//--- 從x12（即p12 buckets首地址）- 實際需要平移的內(nèi)存大小BUCKET_SIZE敞恋，得到得到第二個bucket元素丽啡，imp-sel分別存入p17-p9，即向前查找
    ldp p17, p9, [x12, #-BUCKET_SIZE]!  // {imp, sel} = *--bucket 
//--- 跳轉(zhuǎn)至第1步硬猫，繼續(xù)對比 sel 與 cmd
    b   1b          // loop 

3:  // wrap: p12 = first bucket, w11 = mask
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
//--- 人為設(shè)置到最后一個元素
//--- p11（mask）右移44位 相當于mask左移4位补箍，直接定位到buckets的最后一個元素，緩存查找順序是向前查找
    add p12, p12, p11, LSR #(48 - (1+PTRSHIFT)) 
                    // p12 = buckets + (mask << 1+PTRSHIFT) 
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
    add p12, p12, p11, LSL #(1+PTRSHIFT)
                    // p12 = buckets + (mask << 1+PTRSHIFT)
#else
#error Unsupported cache mask storage for ARM64.
#endif

    // Clone scanning loop to miss instead of hang when cache is corrupt.
    // The slow path may detect any corruption and halt later.
//--- 再查找一遍緩存()
//--- 拿到x12（即p12）bucket中的 imp-sel 分別存入 p17-p9
    ldp p17, p9, [x12]      // {imp, sel} = *bucket 
    
//--- 比較 sel 與 p1（傳入的參數(shù)cmd）
1:  cmp p9, p1          // if (bucket->sel != _cmd) 
//--- 如果不相等啸蜜，即走到第二步
    b.ne    2f          //     scan more 
//--- 如果相等 即命中坑雅，直接返回imp
    CacheHit $0         // call or return imp  
    
2:  // not hit: p12 = not-hit bucket
//--- 如果一直找不到，則CheckMiss
    CheckMiss $0            // miss if bucket->sel == 0 
//--- 判斷p12（下標對應(yīng)的bucket） 是否 等于 p10（buckets數(shù)組第一個元素）-- 表示前面已經(jīng)沒有了衬横，但是還是沒有找到
    cmp p12, p10        // wrap if bucket == buckets 
    b.eq    3f //如果等于裹粤，跳轉(zhuǎn)至第3步
//--- 從x12（即p12 buckets首地址）- 實際需要平移的內(nèi)存大小BUCKET_SIZE，得到得到第二個bucket元素蜂林，imp-sel分別存入p17-p9遥诉，即向前查找
    ldp p17, p9, [x12, #-BUCKET_SIZE]!  // {imp, sel} = *--bucket 
//--- 跳轉(zhuǎn)至第1步，繼續(xù)對比 sel 與 cmd
    b   1b          // loop 

LLookupEnd$1:
LLookupRecover$1:
3:  // double wrap
//--- 跳轉(zhuǎn)至JumpMiss 因為是normal 噪叙，跳轉(zhuǎn)至__objc_msgSend_uncached

    JumpMiss $0 
.endmacro

//以下是最后跳轉(zhuǎn)的匯編函數(shù)
.macro CacheHit
.if $0 == NORMAL
    TailCallCachedImp x17, x12, x1, x16 // authenticate and call imp
.elseif $0 == GETIMP
    mov p0, p17
    cbz p0, 9f          // don't ptrauth a nil imp
    AuthAndResignAsIMP x0, x12, x1, x16 // authenticate imp and re-sign as IMP
9:  ret             // return IMP
.elseif $0 == LOOKUP
    // No nil check for ptrauth: the caller would crash anyway when they
    // jump to a nil IMP. We don't care if that jump also fails ptrauth.
    AuthAndResignAsIMP x17, x12, x1, x16    // authenticate imp and re-sign as IMP
    ret             // return imp via x17
.else
.abort oops
.endif
.endmacro

.macro CheckMiss
    // miss if bucket->sel == 0
.if $0 == GETIMP 
//--- 如果為GETIMP 矮锈，則跳轉(zhuǎn)至 LGetImpMiss
    cbz p9, LGetImpMiss
.elseif $0 == NORMAL 
//--- 如果為NORMAL ，則跳轉(zhuǎn)至 __objc_msgSend_uncached
    cbz p9, __objc_msgSend_uncached
.elseif $0 == LOOKUP 
//--- 如果為LOOKUP 睁蕾，則跳轉(zhuǎn)至 __objc_msgLookup_uncached
    cbz p9, __objc_msgLookup_uncached
.else
.abort oops
.endif
.endmacro

.macro JumpMiss
.if $0 == GETIMP
    b   LGetImpMiss
.elseif $0 == NORMAL
    b   __objc_msgSend_uncached
.elseif $0 == LOOKUP
    b   __objc_msgLookup_uncached
.else
.abort oops
.endif
.endmacro

接下來我們梳理一下流程：

ldr p11, [x16,：通過cache首地址平移16字節(jié)（因為在objc_class中苞笨，首地址距離cache正好16字節(jié)，即isa占8字節(jié)子眶，superClass占8字節(jié)）瀑凝，獲取cahce，cache中高16位存mask壹店，低48位存buckets猜丹，得到p11 = cache芝加。
從cache中分別取出buckets和mask硅卢，并由mask根據(jù)哈希算法計算出哈希下標
- and p10, p11：通過cache和掩碼（即0x0000ffffffffffff）的 &運算，將高16位mask抹零藏杖，得到buckets指針地址, 得到p10 = buckets将塑，將cache右移48位，得到mask蝌麸，即p11 = mask
- and p12, p1, p11, LSR：將objc_msgSend的參數(shù)p1（即第二個參數(shù)_cmd）& msak,通過哈希算法点寥，得到需要查找存儲sel-imp的bucket下標index，得到p12 = index = _cmd & mask,為什么通過這種方式呢来吩？因為在存儲sel-imp時敢辩，也是通過同樣哈希算法計算哈希下標進行存儲蔽莱，所以讀取也需要通過同樣的方式讀取。
add p12, p10, p12, LSL：根據(jù)所得的哈希下標index和buckets首地址戚长，取出哈希下標對應(yīng)的bucket
- 其中PTRSHIFT等于3盗冷，左移4位（即2^4 = 16字節(jié)）的目的是計算出一個bucket實際占用的大小,結(jié)構(gòu)體bucket_t中sel占8字節(jié)，imp占8字節(jié)
- 根據(jù)計算的哈希下標index 乘以單個bucket占用的內(nèi)存大小同廉，得到buckets首地址在實際內(nèi)存中的偏移量
- 通過首地址 + 實際偏移量仪糖，獲取哈希下標index對應(yīng)的bucket
ldp p17, p9, [x12]：根據(jù)獲取的bucket，取出其中的imp存入p17迫肖，即p17 = imp锅劝，取出sel存入p9，即p9 = sel
第一次遞歸循環(huán)
- cmp p9, p1：比較獲取的bucket中sel 與 objc_msgSend的第二個參數(shù)的_cmd(即p1)是否相等
- CacheHit $0：如果相等蟆湖，則直接跳轉(zhuǎn)至CacheHit故爵，即緩存命中，返回imp
- b.ne 2f：如果不相等隅津，有以下兩種情況
  - CheckMiss $0：如果一直都找不到稠集，直接跳轉(zhuǎn)至CheckMiss，因為$0是normal饥瓷，會跳轉(zhuǎn)至__objc_msgSend_uncached剥纷，即進入慢速查找流程
  - cmp p12, p10：如果index獲取的bucket 等于buckets的第一個元素，
    - ldp p17, p9, [x12,：如果人為的將當前bucket設(shè)置為buckets的最后一個元素（通過buckets首地址+mask右移44位（等同于左移4位）直接定位到bucker的最后一個元素）呢铆，然后繼續(xù)進行遞歸循環(huán)（第一個遞歸循環(huán)嵌套第二個遞歸循環(huán)）
b 1b：第二次遞歸循環(huán)：重復(fù)【5】的操作晦鞋，與【5】中唯一區(qū)別是，如果當前的bucket還是等于buckets的第一個元素棺克，則直接跳轉(zhuǎn)至JumpMiss悠垛，此時的$0是normal，也是直接跳轉(zhuǎn)至__objc_msgSend_uncached娜谊，即進入慢速查找流程

源碼流程圖

接下來我們可以總結(jié)一個源碼流程圖

快速查找流程圖