iOS底层原理：消息转发之快速/缓存查找

在上篇博客iOS底层原理：cache_t分析中已经分析了cache的存储方法，那么如何去查找呢？
则就是我们这次的重点了~~~

Runtime

首先在开始分析如何查找cache的时候，我们先介绍下，什么是编译时和运行时。

编译时

将源代码翻译成机器能识别的代码。

主要是进行了词法分析和语法分析；主要是进行类型检查，初步扫描，此时代码还没放到内存中运行起来。常见的就是我们build完毕之后的error和warning都是编译器检查出来的。

运行时

代码运行起来，被装载到内存中

运行时类型检查是在内存中做了些操作，判断是否符合逻辑规范

Runtime 被调用的三种途径

1、Objective-C Code
2、Framework&Service
3、Runtime IPA

架构

三种方式

三种方式，在经过编译器处理后，最后都会调用Runtime中的API方法。

Clang 了解底层

main函数代码：

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

        [person say1];
        [person say2];
        [person say3];
    }
    return 0;
}

clang编译后源码：

int main(int argc, const char * argv[]) {
    /* @autoreleasepool */ { __AtAutoreleasePool __autoreleasepool; 
        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("say1"));
        ((void (*)(id, SEL))(void *)objc_msgSend)((id)person, sel_registerName("say2"));
        ((void (*)(id, SEL))(void *)objc_msgSend)((id)person, sel_registerName("say3"));
    }
    return 0;
}

从上面的对比中，我们其实可以看到，所有的方法调用其实都是通过调用objc_msgSend的。

顾名思义，在iOS中所有的方法，其实就是消息转发，而消息转发包含消息的接受者和消息主体。消息主体其实包含方法编号和参数。

id objc_msgSend(id self, SEL _cmd, ...);

所以，当我们调用方法的时候，其实就是调用了objc_msgSend(id self, SEL _cmd, ...)，其实就是通过sel找到对应的imp（函数指针），imp指向了函数实现。

所以接下来我们着重分析一下objc_msgSend，也就是通过sel找到imp。

objc_msgSend

通过源码，其实我们可以发现objc_msgSend其实是通过汇编来实现的。为什么要用汇编来实现呢？

好处

1、快；iOS整个底层都是通过调用该方法来实现消息转发的，可以提高性能。
2、参数的动态性（不确定性）；

其实objc_msgSend大概流程是通过对象的ISA找到方法(类)，在类(objc_class)中找到cache，如果存在则调用，不存在则找methodlist（整个继承链去查找）。

objc781_objc_msgSend

通过整个流程图，我们去分析下汇编源码：

开始之前了解下部分汇编指令：

b.le ：判断上面cmp的值是小于等于 执行标号，否则直接往下走
b.eq 等于 执行地址 否则往下
cmp 比较（Compare，比较两个数并且更新标志）
ldr 从存储器中加载（Load）字到一个寄存器（Register）中
mov 寄存器加载数据，既能用于寄存器间的传输，也能用于加载立即数（mov x0,#0x10 x0 = 0x10）

_objc_msgSend 源码分析

    ENTRY _objc_msgSend  // _objc_msgSend的入口函数
    UNWIND _objc_msgSend, NoFrame

    // 判断消息接受者是否为空
    cmp p0, #0          // nil check and tagged pointer check
    // 判断是否为taggedpinter对象
#if SUPPORT_TAGGED_POINTERS
    // 如果 cmp p0, #0 小于等于0，则执行标号 LNilOrTagged，否则直接往下走
    b.le    LNilOrTagged        //  (MSB tagged pointer looks negative)
#else
    // 等于 则执行标号 LReturnZero，否则往下走
    b.eq    LReturnZero
#endif
    ldr p13, [x0]       // p13 = isa 找到isa指针
    GetClassFromIsa_p16 p13     // p16 = class 获取class
LGetIsaDone:
    // calls imp or objc_msgSend_uncached
    // 开始缓存查找
    CacheLookup NORMAL, _objc_msgSend

1、首先进入入口函数（ENTRY _objc_msgSend）
2、判断消息接收者是否为空（cmp p0, #0）
3、如果是taggedpinter对象并且cmp p0, #0小于等于0，则执行标号 LNilOrTagged，否则直接往下走
4、如果不是taggedpinter对象并且cmp p0, #0等于0，则执行标号LReturnZero，否则直接往下走
5、找到isa指针（ldr p13, [x0]）
6、找到类class（GetClassFromIsa_p16 p13）

1、GetClassFromIsa_p16源码分析

.macro GetClassFromIsa_p16 /* src */
#if SUPPORT_INDEXED_ISA
    ...省略部分信息...
#elif __LP64__
    // 64-bit packed isa
    and p16, $0, #ISA_MASK
#else
    ...省略部分信息...
#endif
.endmacro

SUPPORT_INDEXED_ISA查找宏定义就可以知道值为0，所以不做分析
and p16, $0, #ISA_MASK，其实就是将传入的p13也就是isa & ISA_MASK之后赋值给了p16，这就是我们在以前博客中提到过的，通过mask获取到我们的目标类了。

找到class之后，LGetIsaDone取isa和class已经完成了，开始进入缓存查找CacheLookup 入参NORMAL

2、CacheLookup源码分析

.macro CacheLookup

LLookupStart$1:

    // p1 = SEL, p16 = isa
    ldr p11, [x16, #CACHE]              // p11 = mask|buckets  isa 指针偏移#CACHE(16位)得到cache的地址，也就是_maskAndBuckets

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    and p10, p11, #0x0000ffffffffffff   // p10 = buckets   p10 = p11 & 0x0000ffffffffffff，也就是将mask抹零，获取到buckets
    and p12, p1, p11, LSR #48       // x12 = _cmd & mask / p12 = p1 & (_maskAndBuckets >> 48),也就是 _cmd & mask，存入时候的hash算法
#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))
                     // #define PTRSHIFT 3 ，也就是 p12 = buckets + ((_cmd & mask) << 4 )

    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

3:  // wrap: p12 = first bucket, w11 = mask
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    add p12, p12, p11, LSR #(48 - (1+PTRSHIFT))
                    // (mask|bucket >> 44)  =  mask|bucket >> 48 << 4 = mask << 4
                    // 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

在源码中已经加了部分注释，接下来我们对缓存查找这一步进行详细的分析：

2.1、ldr p11, [x16, #CACHE]：x16就是p16，也就是我们的类对象的isa，对isa指针偏移#CACHE(16位)得到cache的首地址，也就是_maskAndBuckets（具体可查看cache_t的结构）
2.2、and p10, p11, #0x0000ffffffffffff：p10 = p11 & 0x0000ffffffffffff，也就是将mask抹零，获取到buckets，即 p10 = buckets；这里是因为arm64下的mask和buckets是在一起的，也是可以通过cache_t结构分析出来

_maskAndBuckets
2.3、and p12, p1, p11, LSR #48：p1就是我们传入的第一个参数sel _cmd，p12 = _cmd & (_maskAndBuckets >> 48),也就是_cmd & mask，即存入时候的调用的hash函数
2.4、add p12, p10, p12, LSL #(1+PTRSHIFT)：通过全局搜索可以知道PTRSHIFT的值是为3，也就是 p12 = buckets + ((_cmd & mask) << 4 )
2.5、ldp p17, p9, [x12]：p9就是第一个buckets中的第一个bucket，结构为{imp, sel} = *bucket
2.6、cmp p9, p1：p1就是我们传入的_cmd，将找到的sel和传入的_cmd进行比较
2.7、如果找到了则缓存命中，直接返回
2.8、如果没找到，则接着查找b.ne 2f
2.9、CheckMiss $0：判断bucket中的sel是否等于0，如果是，则直接返回，如果不是，则进行下一步
2.10、cmp p12, p10：比较bucket == buckets，也就是看当前的bucket是否是第一个元素
2.11、b.eq 3f：如果2.10中条件成立，则执行3f
- 2.11.1、add p12, p12, p11, LSR #(48 - (1+PTRSHIFT))：将p11右移44位，其实也就是将_maskAndBuckets右移44位，也就是将我们的mask左移4位，即mask << 4，p12其实就是我们获取到的buckets，也就是此处是更新p12的值，即p12 = buckets + (mask << 4)；

根据cache::insert函数的分析，我们以最简单的情况来分析，mask_t m = capacity - 1;，也就是此时的mask = 3。所以 p12 = buckets + (0011 >> 4)，也就是p12 = buckets + 48，此时p12就是我们buckets集合中的最后一个bucket。

2.12、ldp p17, p9, [x12] // {imp, sel} = *bucket：此时p9就是我们最后一个bucket，然后在进行递归比较，知道查找完缓存
2.13、ldp p17, p9, [x12, #-BUCKET_SIZE]!：在2.10中，如果当前的bucket不是buckets中的第一个元素，则向前查找（即{imp, sel} = *--bucket），直到找完缓存
2.14、JumpMiss $0：如果最后都没有找到则会走JumpMiss流程，$0就是NORMAL

以上就是我们整个缓存方法的查找流程了。

3、JumpMiss 源码分析

.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

因为传入的$0是NORMAL，所以我们直接看__objc_msgSend_uncached方法

__objc_msgSend_uncached 源码分析

    END_ENTRY __objc_msgSend_uncached


    STATIC_ENTRY __objc_msgLookup_uncached
    UNWIND __objc_msgLookup_uncached, FrameWithNoSaves

    // THIS IS NOT A CALLABLE C FUNCTION
    // Out-of-band p16 is the class to search
    
    MethodTableLookup
    ret

    END_ENTRY __objc_msgLookup_uncached

可以看到其实最后直接走了MethodTableLookup方法，直接探索下MethodTableLookup

MethodTableLookup

.macro MethodTableLookup
    
    // push frame
    ...省略部分代码...

    // save parameter registers: x0..x8, q0..q7
    ...省略部分代码...

    // 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

    mov sp, fp
    ldp fp, lr, [sp], #16
    AuthenticateLR

.endmacro

一顿疯狂的汇编代码，看的懵逼，直接找到主要方法_lookUpImpOrForward。当我们想继续探索的时候，发现在当前文件中已经搜索不到了。

其实到这里的时候，汇编的快速查找流程才是真正的结束了。接下来就进入了慢速查找流程。