iOS objc_msgSend 快速查找流程分析

一、objc_msgSend 流程简介

每一个 Objective-C 对象都拥有一个类，每个类都有自己的方法列表。每个方法都拥有选择子、一个指向实现的函数指针和一些元数据（metadata）。objc_msgsend 的工作是使用对象和选择子来查询对应的函数指针，从而跳转到该方法的位置中。

查找的方法可能十分复杂。如果一个方法在当前类中无法查询，那么可能需要在其父类中继续查询。当在父类中也无法找到，则开始调用 runtime 中的消息转发机制。如果这是发送到该类的第一条信息，那么它将会调用该类的 +initialize 方法。

一般情况下，查找的方法需要迅速完成。这与其复杂的查找机制似乎是矛盾的。

Objective-C 解决这个矛盾的方法是利用方法缓存 (Method Cache)。每个类都有一个缓存，它将方法存储为一组选择子和函数指针，在 Objective-C 中被称为 IMP。它们被组织成哈希表的结构，所以查找速度十分迅速。当需要查找方法时，runtime 首先会查询缓存。如果结构不被命中，则开始那一套复杂的查询过程，并将结果存储至缓存，以便下次快速查询。

objc_msgSend 是使用汇编语言编写的。其原因是：其一是使用纯 C 是无法编写一个携带未知参数并跳转至任意函数指针的方法。单纯从语言角度来讲，也没有必要增加这样的功能。其二，对于 objc_msgSend 来说速度是最重要的，只用汇编来实现是十分高效的。

当然，我们也不希望所有的查询过程都是通过汇编来实现。一旦启用了非汇编语言那么就会降低速度。所以我们将消息分成了两个部分，即 objc_msgSend 的高速路径 (fast path)，此处所有的实现使用的是汇编语言，以及缓慢路径 (slow path) 部分，此处的实现手段均为 C 语言。在高速路径中我们可以查询方法指针的缓存表，如果找到直接跳转。否则，则使用 C 代码来处理这次查询。

因此，整个 objc_msgSend 的过程大体如下：

• 获取传入对象所属的类。
• 获取该类的方法缓存表。
• 使用传入的选择子在缓存中查询。
• 如果缓存中不存在，如果缓存中不存在，则开始慢速查找流程。
• 跳转至 IMP 映射位置的方法。

具体是怎么实现的呢？下面开始分析。

二、方法的本质探索

Objective-C 程序有三种途径和运行时系统 runtime 交互：

• Objective-C 代码: @selector()
• NSObject的 方法: NSSelectorFromString()
• runtime 函数: sel_registerName()

 Person *person = [Person alloc];
 [person sayHello];
 
 test();

把 main.m 文件使用如下 clang 编译命令转为cpp 文件，会得到下面 main.cpp 文件

clang -rewrite-objc main.m -o main.cpp

main.cpp 文件

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("sayHello"));

test();

然后我们就可以使用 objc_msgSend 来实现 sayHello 方法的调用，使用 objc_msgSend 的时候，要需要将 Xcode 中 build setting 中的 Enbale Strict of Checking of objc_msgSend Calls 设置为 NO。这样才不会报警告。

objc_msgSend(objc_getClass("Person"), sel_registerName("alloc"));
objc_msgSend(person, sel_registerName("sayHello"));

 test();

• 不管是 alloc 方法 还是 sayHello 方法 ，底层都是通过 objc_msgSend 函数来实现的。因此 OC 方法的本质就是通过 objc_msgSend 来发送消息。

• objc_msgSend(id _Nullable self, SEL _Nonnull op, ...)包含有方法的调用的两个隐藏参数：id self（消息接收者）和SEL sel（方法编号）。

• sel_registerName 等同于 OC 中的@selector()

• C 函数 test 方法直接执行了，并没有通过 objc_msgSend 进行消息发送

方法调用(消息发送)的几种情况

1. 实例方法的调用

objc_msgSend(person, sel_registerName("sayHello"));

2. 类方法的调用

objc_msgSend(objc_getClass("Person"), sel_registerName("alloc"));

3. 父类实例方法的调用

@interface LGStudent : LGPerson
LGStudent *s = [LGStudent alloc];

struct objc_super lgSuper;
lgSuper.receiver = s;
lgSuper.super_class = [LGPerson class];
objc_msgSendSuper(&lgSuper, @selector(sayHello));

4. 父类类方法的调用

@interface LGPerson : NSObject
+(void)sayNB;
@end

struct objc_super myClassSuper;
myClassSuper.receiver = [s class];
myClassSuper.super_class = class_getSuperclass(object_getClass([s class]));// 元类
objc_msgSendSuper(&myClassSuper, sel_registerName("sayNB"));

三、objc_msgSend流程分析

objc_msgSend 的快速查找流程是用汇编实现的，主要原因有

• c 语言不可能通过写一个函数来保留未知的参数并且跳转到一个人任意的函数指针。c 语言没有满足做这件事情的必要特性。
• 性能更高，汇编是更接近系统底层的语言。

3.1 _objc_msgSend

打开 objc 源码，搜索 objc_msgSend , 直接来到 objc-msg-arm64.s 的 ENTRY _objc_msgSend 中

读取 x0 的首地址 存入 p13。x0 为第一个参数，依然是 消息接收者，不管它是类还是对象，它的第一个成员都是 isa， 所以取x0的首地址，即为 isa， 将 isa 存入 p13 。这里取 isa 的目的是因为 ，不管是对象方法还是类方法，我们都可以通过 isa 的指向 在类或元类的缓存或方法列表中去查找。所以接下来就要通过 isa 取到类或元类。

此时对 isa 处理已经完成，已经找到当前类，接下来就是去缓存里面找方法，如果有直接返回对应的 imp ，CacheLookup 的参数分为三种，NORMAL（正常的去查找） 、 GETIMP（直接返回 IMP） 和LOOKUP（主动的慢速去查找）。

 ENTRY _objc_msgSend
    UNWIND _objc_msgSend, NoFrame //没窗口
    //对比p0寄存器是否为空，其中x0-x7是参数，x0可能会是返回值
    cmp p0, #0          // nil check and tagged pointer check
#if SUPPORT_TAGGED_POINTERS
//如果是LNilOrTagged返回空
    b.le    LNilOrTagged        //  (MSB tagged pointer looks negative)
#else
    b.eq    LReturnZero
#endif
    //ldr是数据读取指令，将x0中的数据读取到p13中
    ldr p13, [x0]       // p13 = isa
    //根据isa拿到类。
    GetClassFromIsa_p16 p13     // p16 = class  GetClassFromIsa_p16是一个宏，取面具，isa & ISA_MASK，得到当前类-获取传入对象所属的类
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 + 函数名
    END_ENTRY _objc_msgSend

3.2、GetClassFromIsa_p16

isa & ISA_MASK，得到当前类

.macro GetClassFromIsa_p16 /* src */

#if SUPPORT_INDEXED_ISA   //苹果手表Watch支持
    // Indexed isa
    mov p16, $0         // optimistically set dst = src
    tbz p16, #ISA_INDEX_IS_NPI_BIT, 1f  // done if not non-pointer isa
    // isa in p16 is indexed
    adrp    x10, _objc_indexed_classes@PAGE
    add x10, x10, _objc_indexed_classes@PAGEOFF
    ubfx    p16, p16, #ISA_INDEX_SHIFT, #ISA_INDEX_BITS  // extract index
    ldr p16, [x10, p16, UXTP #PTRSHIFT] // load class from array
1:

#elif __LP64__   //64位系统
    // 64-bit packed isa
    and p16, $0, #ISA_MASK //p16 = $0 & #ISA_MASK

#else
    // 32-bit raw isa
    mov p16, $0

#endif

.endmacro

3.3、CacheLookup 缓存查找

这一步是查找方法缓存，如果命中缓存就走 CacheHit，没找到走 CheckMiss

/********************************************************************
 *
 * CacheLookup NORMAL|GETIMP|LOOKUP
 * 
 * Locate the implementation for a selector in a class method cache.
 *
 * Takes:
 *   x1 = selector
 *   x16 = class to be searched
 *
 * Kills:
 *   x9,x10,x11,x12, x17
 *
 * On exit: (found) calls or returns IMP
 *                  with x16 = class, x17 = IMP
 *          (not found) jumps to LCacheMiss
 *
 ********************************************************************/
.macro CacheLookup

LLookupStart$1:

    // p1 = SEL, p16 = isa --- 
    // x16代表 class，#CACHE 是一个宏定义 #define CACHE (2 * __SIZEOF_POINTER__)，代表16个字节
    // class 平移 CACHE(也就是16个字节)得到 cache_t，然后将 cache_t里面的 buckets|mask 赋值给p11
    ldr p11, [x16, #CACHE]              // p11 = mask|buckets (前16位为mask,后48位为buckets)

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    and p10, p11, #0x0000ffffffffffff   //  0x0000ffffffffffff代表前16位为0，后48位为1， p10 = p11& 0x0000ffffffffffff,得到bucket,  p10 = buckets
    and p12, p1, p11, LSR #48       // p11逻辑右移48位，得到mask, x12 = _cmd & mask ，得到方法下标，解析请看3.4 _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


    add p12, p10, p12, LSL #(1+PTRSHIFT)
                     // p12 = buckets + ((_cmd & mask) << (1+PTRSHIFT))，buckets偏移方法下标（index）* bucket大小（SEL和IMP共16字节），PTRSHIFT 宏定义为3，左移1+3=4位等于16字节，乘以index,相当于得到对应index的bucket， 拿到下标对应的bucket

    ldp p17, p9, [x12]      // {imp, sel} = *bucket  判断对应下标的bucket的sel和查找的sel是否相同
    //这个地方是p9和P1进行对比  判断是否匹配到缓存
1:  cmp p9, p1          // if (bucket->sel != _cmd)
    //b是跳转的意思 .ne是notEquel的意思  也就是如果p9和p1不匹配就跳转下面2，如果匹配就往下走
    b.ne    2f          //     scan more
    //如果找到就调用并返回CacheHit，缓存命中，传的参数是$0,也就是CacheLookup的参数NORMAL
    CacheHit $0         // call or return imp  
    
2:  // not hit: p12 = not-hit bucket
    //没找到就进行CheckMiss操作,传的参数是$0,也就是CacheLookup的参数NORMAL
    CheckMiss $0            // miss if bucket->sel == 0
    //比较p12和p10 也就是比较取出的bucket和buckets首个元素
    cmp p12, p10        // wrap if bucket == buckets
    //如果相等 说明我们已经遍历完了buckets 去跳转执行3方法 
    b.eq    3f
    //这一句递归更上面递归呼应
    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)
#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.
    //再查找一遍缓存 由于多线程的原因，可能当前调用的方法这时可能已经在别的线程调用结束了，也就是说现在可能缓存中已经有了方法的缓存了，这时我们再遍历一遍，也算是再给缓存查找一次机会吧
    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 $0

.endmacro

3.4 _cmd & mask 获取方法下标

方法下标 = _cmd & mask

cache_t::insert方法
然后我们点击 cache_hash(sel, m) 方法，会跳到如下方法， cache_hash(sel, m)方法

3.5 CacheHit

如果命中了，找到了方法我们就调用 CacheHit 函数

.macro CacheHit
.if $0 == NORMAL //传进来的参数是NORMAL,所以调用TailCallCachedImp，直接将方法缓存起来然后进行调用就OK了
    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

3.6 CheckMiss

如果没命中，就调用 CheckMiss 函数：

.macro CheckMiss
    // miss if bucket->sel == 0
.if $0 == GETIMP
    cbz p9, LGetImpMiss
.elseif $0 == NORMAL //传进来的是NORMAL,所以走这里
    cbz p9, __objc_msgSend_uncached
.elseif $0 == LOOKUP
    cbz p9, __objc_msgLookup_uncached
.else
.abort oops
.endif
.endmacro

四、流程总结

4.1 伪代码

我们把汇编流程总结为了如下伪代码形式，方便大家理解整个流程。

// sayHello的 imp 和 从方法缓存找到对应方法index 的 bucket 的 imp 是否相同
[person sayHello]  -> imp ( cache -> bucket (sel imp)) 

// 获取当前的对象
id person = 0x10000
// 获取isa
isa_t isa = 0x000000
// isa -> class -> cache
cache_t cache = isa + 16字节

// arm64
// mask|buckets 在一起的
buckets = cache & 0x0000ffffffffffff
// 获取mask
mask = cache LSR #48
// 下标 = mask & sel
index = mask & p1

// bucket 从 buckets 遍历的开始 (起始查询的bucket)
bucket = buckets + index * 16 (sel imp = 16)


int count = 0
// CheckMiss $0
do{
    if ((bucket == buckets) && (count == 0)){ // 进入第二层判断
        // bucket == 第一个元素
        // bucket人为设置到最后一个元素
        bucket = buckets + mask * 16
        count++;      
    }else if (count == 1) goto CheckMiss        
    // {imp, sel} = *--bucket
    // 缓存的查找的顺序是: 向前查找
    bucket--;
    imp = bucket.imp;
    sel = bucket.sel;
    
}while (bucket.sel != _cmd)  //  // bucket里面的sel 是否匹配_cmd

// CacheHit $0
return imp

CheckMiss:
    CheckMiss(normal)

4.2 _objc_msgSend流程分析图

_objc_msgSend流程图

4.3 objc_msgSend流程总结

• 方法的本质就是消息发送，消息发送是通过 objc_msgSend 以及其派生函数来实现的。
• objc_msgSend 是使用汇编写的，主要是速度够快，够灵活（C 语言做不到写一个函数来保留未知的参数并且跳转到任意的函数指针）
• objc_msgSend 首先通过汇编快速查找方法缓存，如果找到，调用 TailCallCachedImp 直接将方法缓存起来然后进行调用就OK了，如果查找不到就跳到 CheckMiss ，然后走到iOS objc_msgSend 慢速查找流程分析。