OC底层探索10-objc_msgSend快速查找流程

在OC底层探索09-cache_t实现原理探索中详细的分析了cache_t中的insert流程。我们知道在插入之前还有:

调用方法流程

objc_msgSend->cache_getImp->cache_fill->insert

****总结：调用->方法快速查找->方法慢速查找->方法动态决议**** 每一步都会进行分步解释。

1. 方法的调用

Person *person = [Person alloc];
[person sayHello];

这就是一个最基本的方法调用。我们通过clang了解到对象会被llvm编译成一个结构体。现在我们依旧使用xcrun来查看方法的本质.

((void (*)(id, SEL))(void *)objc_msgSend)((id)person, sel_registerName("sayHello"));
//简化:
objc_msgSend(person, sel_registerName("sayHello"));

编译之后可以看到方法最终编译为objc_msgSend，想要探索objc_msgSend不妨自己调用一下试试~

#import <objc/message.h>
//objc-message.h中声明的结构体
struct objc_super {
    __unsafe_unretained _Nonnull id receiver;
    __unsafe_unretained _Nonnull Class super_class;
};

{
    Person *person = [Person alloc];
    //调用本类Person方法
    objc_msgSend((id)person, sel_registerName("sayHello"));
    //调用Person父类方法
    struct objc_super sup;
    sup.receiver = person;
    sup.super_class = [Animal class];
    objc_msgSendSuper(&sup, sel_registerName("say"));
}

调用结果和直接调用方法是相同的，因为方法的调用本质：通过sel方法名来寻址imp实现

调用完成后进入方法快速查找流程

2. 方法快速查找

objc_msgSend源码流程

想要了解方法是如何查找的，就需要查看objc_msgSend的方法实现。（前提：方法快速查找流程使用汇编编写）

//objc_msgSend(id，Sel);

    ENTRY _objc_msgSend
    UNWIND _objc_msgSend, NoFrame
// p0表示该方法的第一个参数。
// cmd判断第一个参数是否为空
    cmp p0, #0
// 判断是TAGGED_POINTERS类型
// cmd判断空之后的返回值
#if SUPPORT_TAGGED_POINTERS
    b.le    LNilOrTagged
#else
    b.eq    LReturnZero
#endif

// 将x0地址赋值到p13中去
// 因为x0的地址代表的是消息接受者（对象）的首地址，而对象中第一个值就是isa,所以x0 = p13 = isa
    ldr p13, [x0]       // p13 = isa
//p16 根据isa（有33位代表父类（元类）的一些类位运算） p13获取到Class
    GetClassFromIsa_p16 p13     // p16 = class

LGetIsaDone:
// 进入快速查找流程
// calls imp or objc_msgSend_uncached
CacheLookup NORMAL, _objc_msgSend

objc_msgSend快速查找源码流程

想要看懂这部分内容需要对:类的结构、cacae_t的结构有一个清楚的理解。

以防看的迷糊把一些关键的变量值和寄存器值单独列出来

x0: 消息接受者
x1、p1: 方法Sel
x16、p16: 消息载体：类、元类
p11: cache_t 的地址
p10: buckets地址
x12、p12: 1.buckets中对应sel的下标（会一直变化直到找到sel）
    2.重新赋值后代表下标对应的bucket
p17:找到的imp
p9:找到的sel

#define CACHE            (2 * __SIZEOF_POINTER__)   //2 * 8 == 16
.macro CacheLookup
//查找标识符
LLookupStart$1:

//将类、元类的地址平移16字节，获取cace_t的地址
// p1 = SEL, p16 = isa
    ldr p11, [x16, #CACHE]
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16    //高64位，篇幅问题低位就不解释了
// 通过位运算与上0x0000ffffffffffff，获取后48位buckets地址
    and p10, p11, #0x0000ffffffffffff   // p10 = buckets
// 通过地址向右平移48，获取高16位mask地址，然后逻辑与上sel；通过hash运算得到存储的index
    and p12, p1, p11, LSR #48       // x12 = _cmd & mask
// p12左移4位，相当于乘以16.
//buckets地址加上p12 * 16，通过内存平移找到数组（buckets）中对应元素
    add p12, p10, p12, LSL #(1+PTRSHIFT)
                     // p12 = buckets + ((_cmd & mask) << (1+PTRSHIFT))
                 
//  拿到x12（即p12）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
//相等则返回imp，进行调用
    CacheHit $0         // call or return imp

// p12为空后进行CheckMiss，也就是在整个buckets都没有对应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
// 当前bucket地址向左平移16字节（bucket大小为16字节）向前查找
    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    //只看高64位
// 人为设置到最后一个元素,保证每一位都可以查找到
    add p12, p12, p11, LSR #(48 - (1+PTRSHIFT))
                    // p12 = buckets + (mask << 1+PTRSHIFT)
//再查找一遍缓存       
    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
    JumpMiss $0

.endmacro

objc_msgSend快速查找成功

.macro CacheHit
.if $0 == NORMAL
//找到缓存完成调用
    TailCallCachedImp x17, x12, x1, x16 // authenticate and call imp
    ...
.endmacro

objc_msgSend快速查找失败

进入JumpMiss这就是在缓存中没有找到对应sel

.macro JumpMiss
    ...
//因为是normal ，跳转至__objc_msgSend_uncached
.elseif $0 == NORMAL
    b   __objc_msgSend_uncached
    ...
.endmacro

.macro CheckMiss
    ...
//因为是normal ，跳转至__objc_msgSend_uncached
.elseif $0 == NORMAL
    cbz p9, __objc_msgSend_uncached
    ...
.endmacro

查找失败后都会进入__objc_msgSend_uncached

STATIC_ENTRY __objc_msgSend_uncached
    UNWIND __objc_msgSend_uncached, FrameWithNoSaves
    
    //此处就跳转到下一个流程-慢速查找
    MethodTableLookup
    TailCallFunctionPointer x17

    END_ENTRY __objc_msgSend_uncached

流程图

最后放出一张快速查找流程图

图片转自：简书-月月

增加一个伪代码实现

[person sayHello]  -> imp ( cache -> bucket (sel imp))

// 获取当前的对象
id person = 0x10000
// 获取isa
isa_t isa = 0x10000
// 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)


// CheckMiss $0
int count = 0
do{

    if (sel == _cmd)  goto CacheHit;
    
    if (bucket == buckets && count == 0){ // 进入第二层循环
        // bucket == 第一个元素
        // bucket人为设置到最后一个元素
        bucket = buckets + mask * 16
        count++
        continue
    }
        
    if (bucket == buckets && count == 1){
        goto JumpMiss;
    }
    
    // {imp, sel} = *--bucket
    // 缓存的查找的顺序是: 向前查找
    bucket--;
    imp = bucket.imp;
    sel = bucket.sel;
    
}while (bucket.sel != NULL)

goto CheckMiss;

CacheHit $0
    return imp

CheckMiss:
    CheckMiss(normal)

JumpMiss:
    CheckMiss(normal)