[iOS] 消息流程分析之快速查找

在之前介绍的 cache 写入流程之前，还有一个 cache 读取流程，即 objc_msgSend和 cache_getImp，我们这次了解一下。

1. Runtime介绍

在分析消息流程之前，需要了解下什么是 Runtime ?
runtime 是运行时，区别于编译时：

• 编译时 是源代码翻译成机器能识别的代码的过程，主要是对语言进行最基本的检查报错，即词法分析、语法分析等，是一个静态的阶段
• 运行时 是代码跑起来，被装载到内存中的过程，如果此时出错，则程序会崩溃，是一个动态阶段

Runtime的使用可以通过 OC 代码调用（[person sayNB]）或者 Runtime API （class_getInstanceSize）的调用。

2. 方法

2.1 方法的本质

我们继续使用 clang 编译 main.cpp文件，查看方法调用的实现：

//main.m中方法的调用
Person *person = [Person alloc];
[person sayNB];
[person sayHello];

//👇clang编译后的底层实现
Person *person = ((Person *(*)(id, SEL))(void *)objc_msgSend)((id)objc_getClass("Person"), sel_registerName("alloc"));
((void (*)(id, SEL))(void *)objc_msgSend)((id)person, sel_registerName("sayNB"));
((void (*)(id, SEL))(void *)objc_msgSend)((id)person, sel_registerName("sayHello"));

通过上面可以看出，方法调用的本质其实就是objc_msgSend 消息发送。

2.2 验证objc_msgSend

我们可以使用 objc_msgSend方法来完成[person sayNB]的调用，查看其打印是否一致。

注意：
1.使用 Runtime 提供的 API，需要先导入头文件#import <objc/message.h>
2.需要将target --> Build Setting -->搜索msg -- 将enable strict checking of obc_msgSend calls由YES改为NO，将严厉的检查机制关掉，否则objc_msgSend的参数会报错

示例代码如下：

Person *person = [Person alloc];
objc_msgSend(person,sel_registerName("sayNB"));
[person sayNB];

输出结果：

2021-01-10 15:16:50.504489+0800 DebugTest[5689:267922] Person say: -[Person sayNB]
2021-01-10 15:16:50.504999+0800 DebugTest[5689:267922] Person say: -[Person sayNB]

发现其打印结果是一致的，[person sayNB] 底层就是objc_msgSend(person,sel_registerName("sayNB"))

2.3 对象方法调用实际执行是父类的实现

我们可以尝试让person的调用执行父类中的实现，通过objc_msgSendSuper实现。

2.3.1 定义两个类：Person 和 Teacher，父类Person 中实现了 sayHello方法

@interface Person : NSObject
- (void)sayHello;
@end
@implementation Person
- (void)sayHello{
    NSLog(@"Person say: %s",__func__);
}
@end

@interface Teacher : Person
- (void)sayHello;
- (void)sayNB;
@end
@implementation Teacher
- (void)sayNB{
    NSLog(@"Person say: %s",__func__);
}
@end

main.h 中的调用：

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        Person *person = [Person alloc];
        Teacher *teacher = [Teacher alloc];
        [teacher sayHello];

        struct objc_super ttsuper;
        ttsuper.receiver = teacher; //消息的接收者还是teacher
        ttsuper.super_class = [Person class]; //告诉父类是谁
            
        //消息的接受者还是自己 - 父类 - 请你直接找我的父亲
        objc_msgSendSuper(&ttsuper, sel_registerName("sayHello"));
    }
    return 0;
}

objc_msgSendSuper方法中有两个参数(结构体，sel)，这个结构体类型是 objc_super定义的结构体对象，需要指定receiver和super_class两个属性。

• objc_msgSendSuper方法定义

objc_msgSendSuper(struct objc_super * _Nonnull super, SEL _Nonnull op, ...)
    OBJC_AVAILABLE(10.0, 2.0, 9.0, 1.0, 2.0);

• objc_super定义

struct objc_super {
    /// Specifies an instance of a class.
    __unsafe_unretained _Nonnull id receiver;

    /// Specifies the particular superclass of the instance to message. 
#if !defined(__cplusplus)  &&  !__OBJC2__
    /* For compatibility with old objc-runtime.h header */
    __unsafe_unretained _Nonnull Class class;
#else
    __unsafe_unretained _Nonnull Class super_class;
#endif
    /* super_class is the first class to search */
};
#endif

打印结果如下：

2021-01-10 17:15:34.474233+0800 DebugTest[6098:312101] Person say: -[Person sayHello]
2021-01-10 17:15:34.474333+0800 DebugTest[6098:312101] Person say: -[Person sayHello]

发现无论是[teacher sayHello]还是objc_msgSendSuper都执行的是父类中sayHello的实现，所以我们可以大胆猜测一下：方法调用，首先是在类中查找，如果类中没有找到，会到类的父类中查找。
我们继续探索下 objc_msgSend的源码去验证一下。

3. objc_msgSend快速查找流程分析

在objc源码中搜索objc_msgSend，由于我们日常开发的都是架构 arm64，所以需要在arm64.s后缀的文件中查找objc_msgSend的源码实现，发现是用汇编实现的，其汇编整体执行的流程如下：

image.png

3.1objc_msgSend汇编源码

objc_msgSend是消息发送的源码入口，使用汇编实现的，源码如下：

// 消息发送的入口，objc_msgSend 主要是拿到接收者的 isa 信息
    ENTRY _objc_msgSend
    UNWIND _objc_msgSend, NoFrame

    // 判断 p0 是否为 nil，p0是 objc_msgSend 的第一个参数：消息接受者 receiver
    cmp p0, #0          // nil check and tagged pointer check
    
#if SUPPORT_TAGGED_POINTERS // 如果支持 Tagged Pointer
    // p0 <= 0(有符号数的比较) ，说明receiver要么为nil，要么就是个Tagged Pointer
    b.le    LNilOrTagged        //  (MSB tagged pointer looks negative)
#else
    // 执行LReturnZero流程
    b.eq    LReturnZero
#endif
    // 从 x0 寄存器中取出 isa，存储到 p13中
    ldr p13, [x0]       // p13 = isa
    // GetClassFromIsa_p16 是一个宏，在 64 位架构下通过 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

其汇编实现等价于 C 语言实现：

id objc_msgSend(id self, SEL _cmd,...){
    (1)`NilTest`：对receiver(即self)进行非空测试。
    if (!self) return;
    
    (2)`LNilOrTagged`：receiver非空，获取其类cls的地址。
    Class cls = self->getIsa();
    
    (3)`CacheLookup NORMAL, _objc_msgSend`：遍历cls的缓存查找_cmd，如命中则返回其imp；未命中则开启慢查找。
    IMP imp = CacheLookup(cls,_cmd);
    if(imp) {
        TailCallCachedImp imp, &imp, _cmd, cls; //汇编语句，arm64缓存查找的汇编显示只走到了这里。
    } else {
        (4) `__objc_msgSend_uncached` ---> `MethodTableLookup`---> 
        `lookUpImpOrForward(self, _cmd, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER);`：缓存未命中，开启慢查找 ---> 方法列表查找
        imp = MethodTableLookup(cls,_cmd);
        TailCallFunctionPointer imp;  //汇编语句，arm64慢查找的汇编显示只走到了这里。
    }
    return 0;    
}

3.1.1 【第一步】判断objc_msgSend方法的第一个参数 receiver

• 如果支持tagged pointer，跳转至LNilOrTagged
  • 如果小对象为空，直接返回空，即LReturnZero
  • 如果小对象不为空，则处理小对象的 isa，走到【第二步】
• 如果既不是小对象，receiver 也不为空，有以下两步：
  • 从 receiver 中取出isa存入p13寄存器
  • 通过GetClassFromIsa_p16中，arm64架构下通过 isa & ISA_MASK获取shiftcls位域的类信息，即class，GetClassFromIsa_p16的汇编实现如下，然后走到【第二步】

.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基址 根据 偏移量 进行 内存偏移
    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位系统
#elif __LP64__ 
    // 64-bit packed isa
//---- p16 = class = isa & ISA_MASK(位运算 & 即获取isa中的shiftcls信息)
    and p16, $0, #ISA_MASK 

#else
    // 32-bit raw isa ---- 用于32位系统
    mov p16, $0

#endif

.endmacro

3.1.2 【第二步】获取isa完毕，进入慢速查找流程CacheLookup NORMAL

CacheLookup汇编源码如下：

#define NORMAL 0
#define GETIMP 1
#define LOOKUP 2

// CacheHit: x17 = cached IMP, x12 = address of cached IMP, x1 = SEL, x16 = isa
.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 //authenticate imp and re-sign(签名) as IMP 认证并重新签名IMP
9:  ret             // return IMP 返回 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

// p9: 从缓存 bucket 中取出的 sel 的值
// 进行未命中检查：p9是否为0？（未命中可以，但是sel不能为0！否则就直接宣布Cache中没有进行缓存了！）
// 为0就意味着对应的bucket为nil，之前未插入缓存，说明未缓存！那就别再往下找了，缓存中没有！只能去方法列表中查找了！
.macro CheckMiss //未命中则进入MethodTable中查询！
    // miss if bucket->sel == 0
.if $0 == GETIMP
    cbz p9, LGetImpMiss
.elseif $0 == NORMAL
    cbz p9, __objc_msgSend_uncached //cbz指令：CBZ R, label，R为0则跳转至label处执行；否则不跳转。
.elseif $0 == LOOKUP
    cbz p9, __objc_msgLookup_uncached // cbnz指令：CBNZ R, label R为非0则跳转至label处执行；否则不跳转。
.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

.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 // x0 存的是 receiver
    //   - x1 contains the selector // x1 存的是 selector即 sel
    //   - x16 contains the isa     // x16 存的是 isa
    //   - other registers are set as per calling conventions
    //
LLookupStart$1:

    // p1 = SEL, p16 = isa
    // #CACHE 的定义 #define CACHE (2 * __SIZEOF_POINTER__) 即 2 * 8 = 16
    // 从 x16(此时存储的是对象 isa，也就是类信息) 中平移 16 个字节，取出 cache(mask高16位 + buckets低48位) 存入 p11 寄存器
    ldr p11, [x16, #CACHE]              // p11 = mask|buckets

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 // 64位真机
    //  p11(cache) & 0x0000ffffffffffff ，mask高16位抹零，得到buckets 存入p10寄存器-- 即去掉mask，留下buckets
    and p10, p11, #0x0000ffffffffffff   // p10 = buckets
    
    // p11(cache)右移48位，得到mask（即p11 存储mask），mask & p1(msgSend的第二个参数 cmd-sel) ，得到sel-imp的下标index，存入p12（cache insert写入时的哈希下标计算是 通过 sel & mask，读取时也需要通过这种方式）
    and p12, p1, p11, LSR #48       // x12 = _cmd & mask
#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数组首地址，PTRSHIFT = 3，
    // 得到实际内存的偏移量，通过buckets的首地址偏移，获取bucket存入p12寄存器
    // LSL #(1+PTRSHIFT)-- 实际含义就是得到一个bucket占用的内存大小，这里 +1 ,左移 4 位是因为每个 bucket 占 16 个字节
    add p12, p10, p12, LSL #(1+PTRSHIFT)
                     // p12 = buckets + ((_cmd & mask) << (1+PTRSHIFT))
    // 从 x12 寄存器中读取bucket，分别将 imp 和 sel 存入 p17 和 p9 中
    ldp p17, p9, [x12]      // {imp, sel} = *bucket
    // 比较 sel 和 _cmd
1:  cmp p9, p1          // if (bucket->sel != _cmd)
    // 如果不相等，即没有找到，则跳转至 2f
    b.ne    2f          //     scan more
    // 如果缓存命中，找到了，则直接返回 imp
    CacheHit $0         // call or return imp
    
2:  // not hit: p12 = not-hit bucket
    // 如果一直都找不到，因为此时是 NORMAL， CheckMiss 中 跳转到 __objc_msgSend_uncached
    CheckMiss $0            // miss if bucket->sel == 0
    // 判断p12（下标对应的bucket） 是否 等于 p10（buckets数组第一个元素，），如果等于，则跳转至第3步
    cmp p12, p10        // wrap if bucket == buckets
    b.eq    3f // 相等则说明当前的selector在Cache中的起始下标为0！
    // 从x12（即p12 buckets首地址）- 实际需要平移的内存大小BUCKET_SIZE，得到得到第二个bucket元素，imp-sel分别存入p17-p9，即向前查找（（x12取完后被赋了新值！））
    ldp p17, p9, [x12, #-BUCKET_SIZE]!  // {imp, sel} = *--bucket
    b   1b          // loop 循环

3:  // wrap: p12 = first bucket, w11 = mask
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    add p12, p12, p11, LSR #(48 - (1+PTRSHIFT))
                    // p12 = buckets + (mask << 1+PTRSHIFT) 重置p12为Cache中【最后一个】bucket的地址！
#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 bucket 中的 imp sel ，分别存入 p17 和 p9
    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

LLookupEnd$1:
LLookupRecover$1:
3:  // double wrap
// 跳转至JumpMiss 因为是normal ，跳转至__objc_msgSend_uncached
    JumpMiss $0

.endmacro

主要分为以下几步：
[第一步]：
通过isa(类信息) 首地址平移 16 字节(在 objc_class中，首地址距离cache正好16个字节，isa 占8 个字节，superClass 占 8 个字节)，获取 cache，cache 中的高 16 位存储的是 mask，低48位存储的 buckets，p11 = cache

[第二步]：
从 cache 中分别取出 buckets 和 mask，并通过 mask 根据哈希算法计算出哈希下标

• 通过 cache和 0x0000ffffffffffff的&运算，将高 16 位的 mask抹零，得到 buckets 指针地址，即 p10 = buckets
• 将cache右移 48位，得到mask，即p11 = mask
• 将 objc_msgSend 的参数p1（即第二个参数_cmd）& mask，通过哈希算法，得到需要查找存储sel-imp的bucket 下标index，即 p12=index = _cmd & mask。为什么需要这么计算呢？因为在存储 sel-imp时，也是通过同样的哈希算法计算哈希下标进行存储的，所以读取也需要通过同样的方式读取，如下所示：
  image.png

[第三步]：
根据所得的哈希下标index和buckets 首地址，取出哈希下标对应的 bucket

• 其中 PTRSHIFT = 3，左移4位(即 2^4=16字节)，计算出一个 bucket实际占用的大小为16 字节
• 根据计算的哈希下标 index * 16(单个bucket占用的内存大小)，得到bucket 首地址在实际内存中的偏移量
• 通过buckets 首地址 + 实际偏移量，取出index下标对应的 bucket

[第四步]：
根据获取的 bucket，取出其中的imp存入p17，即p17 = imp，取出sel 存入p9，即 p9 = sel

[第五步]：
第一次递归循环

• 比较获取的 bucket 中sel 与objc_msgSend的第二个参数的_cmd(即p1)是否相等
• 如果相等，则直接跳转至 CacheHit(缓存命中)，返回imp
• 如果不相等：
  • 如果一直都找不到，直接跳转至 CheckMiss，因为$0 是 NORMAL，会跳转至__objc_msgSend_uncached，进入慢速查找流程
  • 如果根据index获取的bucket等于buckets 的第一个元素，则人为的将当前 bucket 设置为 buckets的最后一个元素(通过 buckets 首地址+mask 右移 44 位（等同于左移 4 位）直接定位到buckets的最后一个元素)，然后继续进行递归循环(第一个递归循环嵌套第二个递归循环)即[第六步]
  • 如果当前bucket不等于buckets的第一个元素，则继续向前查找，进入第一次递归循环

[第六步]
第二次递归循环，重复[第五步]的操作，与[第五步]中唯一区别是，如果当前的bucket还是等于 buckets的第一个元素，则直接跳转至 JumpMiss，此时的$0是 NORMAL，也是直接跳转至 __objc_msgSend_uncached，进入慢速查找流程。

以下是整个快速查找过程中值的变化过程：

image.png