oc-底层原理之objc_msgSend方法快速查找

在oc-底层原理分析之Cache_t一文中我们对方法的缓存进行了探讨，这篇文章我们在来研究一下方法的查找

方法的查找有两条线路：

快速查找（通过汇编实现）
慢速查找（通过c实现）（下一篇文章再来探究）

方法快速查找

方法的快速查找实际是通过缓存来查找，在探究之前，我们先来了解一下objc_msgSend，我们要知道方法的查找是在什么时机通过什么入口进入的

objc_msgSend

我们知道objective-c是一门动态语言，所有的方法调用并不是在编译阶段就确定的，当我们通过sel去查找imp的时候是在运行时才具体确定sel所对应的imp地址的，我们来看看下面的例子：
先定义两个类WPerson和WTeacher,WTeacher继承自WPerson

@interface WPerson : NSObject
- (void)sayHello;
@end

@implementation WPerson
- (void)sayHello{
    NSLog(@"hello");
}
@end

@interface WTeacher : WPerson
- (void)sayHello;
- (void)sayNB;
@end

@implementation WTeacher
- (void)sayNB{
    NSLog(@"666");
}
@end

如果我们要调用sayNB方法，我们可以使用WTeacher的对象来调用：

WTeacher *teacher = [WTeacher alloc];
[teacher sayNB];

在类的结构分析一文中我们通过Clang将类编译成.cpp文件后，我们可以看到类的结构中，方法的调用为：

WTeacher *teacher = ((WTeacher *(*)(id, SEL))(void *)objc_msgSend)((id)objc_getClass("WTeacher"), sel_registerName("alloc"));
((void (*)(id, SEL))(void *)objc_msgSend)((id)teacter, sel_registerName("sayNB"));
((void (*)(id, SEL))(void *)objc_msgSend)((id)teacter, sel_registerName("sayHello"));

我们可以看到任何方法的调用都是通过objc_msgSend来给对象发送消息的方式实现，那么我们直接调用objc_msgSend

objc_msgSend(teacher,sel_registerName("sayNB"));

我们也能实现方法的调用，但是如果当我们通过WTeacher调用sayHello方法的时候，实际上调用的是父类的sayHello方法，所以我们也可以直接向发送消息：

struct objc_super tsuper;
tsuper.receiver = teacher;
tsuper.super_class = [WPerson class];
    
objc_msgSendSuper(&tsuper, sel_registerName("sayHello"));

你也可以自己尝试一下。我们可以得出一个结论，

使用oc对象或者类来调用方法时实际上是通过objc_msgSend向对象发送消息

objc_msgSend源码分析

objc_msgSend调用方式为：

objc_msgSend(teacher,sel_registerName("sayNB"));

第一个参数为：消息接受者
第二个参数为：消息的sel

接下来我们研究一下objc_msgSend源码：

objc_msgSend源码有多个版本，arm，arm64，i386，模拟器，我们这里都以arm64为例讲解

arm64的objc_msgSend的源码在objc-msg-arm64.s文件中

objc_msgSend

    ENTRY _objc_msgSend
    UNWIND _objc_msgSend, NoFrame
   // p0是第一个参数：消息接受者
   // 这里先比较p0是否为空，如果为空，则直接返回
    cmp p0, #0  
    //是否支持  TAGGED_POINTERS
#if SUPPORT_TAGGED_POINTERS
    b.le    LNilOrTagged        //  (MSB tagged pointer looks negative)
#else
   //消息接受者为空，直接返回空
    b.eq    LReturnZero
#endif
  //消息接受者不为空
  //p13 获取消息接受者的isa并赋值给p13
    ldr p13, [x0]       // p13 = isa
    //根据获取到的isa获取class并赋值给p16
    GetClassFromIsa_p16 p13     // p16 = class
LGetIsaDone:
    // calls imp or objc_msgSend_uncached
    //isa获取结束，开始在cache中查找imp
    CacheLookup NORMAL, _objc_msgSend

CacheLookup

要理解这部分源码，需要先理解什么是cache_t,我们已经在oc-底层原理分析之Cache_t一文中进行了详细的探索，请先阅读这一部分

.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__) 
    // x16存储的是isa,平移16个字节后得到cache_t并赋值给p11
    ldr p11, [x16, #CACHE]              // p11 = mask|buckets

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
   // 获取buckets p11&0x0000ffffffffffff得到后48位，并赋值给p10
    and p10, p11, #0x0000ffffffffffff   // p10 = buckets
    // 获取hash，逻辑右移48位得到mask
    // 然后p1&mask 得到hash的key，并赋值给p12
    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当前存储的是hash key，先逻辑左移4位然后再和p10相与，得到对应的bucket并保存在p12中
    add p12, p10, p12, LSL #(1+PTRSHIFT)
                     // p12 = buckets + ((_cmd & mask) << (1+PTRSHIFT))
  //将p12属性的imp和sel分别赋值给p17和p9
    ldp p17, p9, [x12]      // {imp, sel} = *bucket
    //判断当前sel和传入的sel是否相等
1:  cmp p9, p1          // if (bucket->sel != _cmd)
  //如果不相等，跳入2f
    b.ne    2f          //     scan more
  //如果相等，跳入CacheHit
    CacheHit $0         // call or return imp
    
2:  // not hit: p12 = not-hit bucket
    CheckMiss $0            // miss if bucket->sel == 0
    // 判断p12和p10是否相等 
    cmp p12, p10        // wrap if bucket == buckets
    //如果相等，跳入3f
    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
  //将p12指向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.

    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

CacheLookup源码详解

首先我们要知道类的结构，如下：

struct objc_class : objc_object {
    // Class ISA;
    Class superclass;
    cache_t cache;             // formerly cache pointer and vtable
    class_data_bits_t bits;    // class_rw_t * plus custom rr/alloc flags

    class_rw_t *data() const {
        return bits.data();
    }
    
    //这里的其他方法以及属性已经略去
}

我们知道objc_class中有以下几个属性：

ISA
superclass
cache

ldr p11, [x16, #CACHE]：p16存储的是isa，CACHE为16个字节，p16平移16字节后就得到cache的地址，所以此时p11存储的是cache地址
and p10, p11, #0x0000ffffffffffff：在cache_t中，低48位存储的是buckets，高16位存储的是mask，用cache指针和0x0000ffffffffffff进行与运算以后，就得到低48位。也就是buckets，所以此时p10 = buckets
and p12, p1, p11, LSR #48：p11（cache）指针逻辑右移48位得到mask，然后再和p1（sel）相与，得到hash key
要理解这一步，就需要了解cache的存储，我们先看cache的insert方法中获取hash key的方法：
```
static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}
```
我们理解了插入时如何生产hash key，那么这一步也不难理解
add p12, p10, p12, LSL #(1+PTRSHIFT)：PTRSHIFT = 3，p12当前是存储的hash key（实际上相当于index），bucket机构体中，包含两个元素 sel 和 imp，占用16个字节，p12逻辑左移4位，相当于 index * 16，然后p10再平移index * 16，得到对应的bucket，此时p12存储的是对应的buckets
add p12, p12, p11, LSR #(48 - (1+PTRSHIFT))：在循环查找中，如果当前bucket已经指向了cache的首地址（也就是buckets的地址），那么说明循环结束了，此时需要将p12指向buckets的最后一个元素

通过以上的快速查找流程，如果没有查到对应的imp，还会经过的慢速查找，关于慢速查找，下一篇文章会有介绍