在上一篇文章中，我们了解了cache的写入流程，那么是怎么进行方法的查找呢，接下来我们在这篇以及下面的文章来进行探讨，本篇文章先对方法的快速查找进行分析。
在分析之前，先来说一下Runtime，Runtime是给OC这门对象语言提供的运行时，是通过底层的C，C++和汇编实现的，其中Runtime的使用方式有三种：
第一种：通过OC代码，例如 [person sayNB]
第二种：通过NSObject里面的方法，例如isKindOfClass
第三种：通过Runtime API，例如class_getInstanceSize
说到这里， 我觉得附上一张关系图能让你们更加清晰
了解Runtime之后，我们接下来玩一个有意思的东西
我们把代码编译后，来到 clang，把里面的代码实现拿到main函数里面，运行，发现结果和OC的上层调用方法是一摸一样的，从而可以看出，我们的方法到了底层之后，就是 通过objc_msgSend消息发送的
也可以通过msg搜索把Enable Strict Checking of objc_ msgSend Calls严厉机制关了，用objc_msgSend来发送消息，就像这样
效果等同于[person1 sayNB];，除了这一点，我们还可以用person1的调用执行父类中实现，通过objc_msgSendSuper来实现
在这个过程中，我们的子类是没有实现 sayhello的，所以从中可以看出 [person sayHello]和 objc_msgSendSuper执行的都是父类中的 sayHello。
那么问题来了，objc_msgSend是怎么找到我们的方法的呢？ 现在我们明白了OC上层调用的方法，到了下层是发送消息。 消息里有sel和imp，通过sel方法编号绑定imp，imp就是我们的函数指针地址，通过imp我们可以找到具体的内容。那么我们怎么通过sel找到imp呢， 这就是本篇文章关注的重点
objc_msgSend 快速查找流程分析
由于C和C++查找的话比汇编慢了一丢丢，为了提高性能和方法的动态性，sel找imp是通过汇编找的。听到汇编不要紧张，不要惊慌，看不懂汇编没关系，我会标好注释，我们只需要知道流程即可
我们先找到我们的汇编代码，通过xcode搜索objc_msgsend，由于是汇编写的，所以找后缀.s 的文件，然后我们常用的架构又是arm64，所以最终找到了objc-msg-arm64.s里面
通过 ENTRY _objc_msgSend找到底层的汇编源码
在讲这个代码之前，我们要始终记住一点，就是我们一直都在通过sel找imp，记住这一点之后，我们分析代码的时候不会迷路
好了，开始我们的汇编分析之旅：
// _objc_msgSend 入口
ENTRY _objc_msgSend
// 无窗口
UNWIND _objc_msgSend, NoFrame
// cmp 是对比的意思， p0 是objc_msgSend的第一个参数。意思是p0先和空做对比，如果为空就没有必要往下走了。
cmp p0, #0 // nil check and tagged pointer check
// le小于 --支持taggedpointer（小对象类型）的流程
#if SUPPORT_TAGGED_POINTERS
b.le LNilOrTagged // (MSB tagged pointer looks negative)
#else
// p0 等于 0 时，直接返回 空
b.eq LReturnZero
#endif
// 根据对象拿出isa
ldr p13, [x0] // p13 = isa
// 根据isa 拿出类
GetClassFromIsa_p16 p13 // p16 = class
// 获取isa完毕
LGetIsaDone:
// CacheLookup，从缓存里面获取imp的流程，也就是我们今天探讨的重点，从sel-imp快速查找流程
// calls imp or objc_msgSend_uncached
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
到这一步我相信都很容易理解，主要是拿到类信息，即class，拿到class之后来到CacheLookup从缓存里面获取imp的流程。
我们先来看如何拿到class的，先找到macro GetClassFromIsa_p16，然后看源码实现
有一说一，#if SUPPORT_INDEXED_ISA里面的这些汇编我也看不太懂，参考了高人的指点。不过我们也不需要看懂，因为我们arm64真机不会走到那里面去，我们走的是#elif __LP64__里面，这里面就很好理解了， 直接拿isa & ISA_MASK 就可以获取到类信息，这个在之前的文章已经讲过。
好了，获取class完成后，接下来我们重点分析CacheLookup， 我们首先找到macro CacheLookup，注意，在当前类里面找，别找到别人家去了
.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
// CACHE是一个宏定义， 2 * 8 = 16 #define CACHE (2 * __SIZEOF_POINTER__)
// p16是isa，isa位移16个字节得到我们的cache，然而cache的首地址又是mask_buckets
// 然后把cache又放到p11里面
ldr p11, [x16, #CACHE] // p11 = mask|buckets
// ------------ arm64位真机
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
// p11(cache) & 0x0000ffffffffffff ，mask高16位抹零，得到buckets，存到p10 = buckets
and p10, p11, #0x0000ffffffffffff // p10 = buckets
// LSR：p11(cache)逻辑右移48位，拿到mask。 然后 mask & p1(sel & mask) ，得到sel-imp的下标index（即前面讲过的cache_hash的下标） 存入p12
and p12, p1, p11, LSR #48 // x12 = _cmd & mask
// --------- 非arm64位真机 这些就不用看了
#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是获取的下标，然后逻辑左移4位，相当于是（下标 * 16(16是sel和imp的大小)），再由p10(buckets)通过内存平移的方式得到bucket保存到p12中
add p12, p10, p12, LSL #(1+PTRSHIFT) = (1 + 3) = 4
// p12 = buckets + ((_cmd & mask) << (1+PTRSHIFT))
// 得到bucket之后通过指针地址得到{imp, sel}，然后将imp 和 sel分别赋值为p17 和 p9
ldp p17, p9, [x12] // {imp, sel} = *bucket
// 接下来就是开始循环了， 判断当前bucket的 sel 与 p1（传入的sel）是否相等
1: cmp p9, p1 // if (bucket->sel != _cmd)
// 如果不相同，则跳入2f
b.ne 2f // scan more
// 如果相同直接返回imp
CacheHit $0 // call or return imp
// 没有找到 进入2f， 如果一直都找不到， 因为是normal ，跳转至__objc_msgSend_uncached
2: // not hit: p12 = not-hit bucket
CheckMiss $0 // miss if bucket->sel == 0
// 判断p12（下标对应的bucket）是否 等于 p10（buckets数组第一个元素），如果等于，则跳转到3f
cmp p12, p10 // wrap if bucket == buckets
// 如果相等 跳入3f
b.eq 3f
// 因为要将p12的指针指到buckets的最后一个元素后，所以进行了bucket--， 向前一直查找下去
ldp p17, p9, [x12, #-BUCKET_SIZE]! // {imp, sel} = *--bucket
// 跳转至第1步，递归继续对比 sel 与 cmd
b 1b // loop
3: // wrap: p12 = first bucket, w11 = mask
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
// p11（mask）右移44位 相当于mask左移4位，直接定位到buckets的最后一个元素
// 注意，这个地方会往下面走，不会再回去了
add p12, p12, p11, LSR #(48 - (1+PTRSHIFT))
// 把当前查询的bucket人为设为最后一个元素给了p12，然后会往下走
// 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.
// 上面步骤之后然后在继续查找，拿到x12（即p12）bucket中的 imp-sel 分别存入 p17-p9
ldp p17, p9, [x12] // {imp, sel} = *bucket
// 比较 sel 与 p1（传入的参数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
// 如果一直找不到，则CheckMiss
CheckMiss $0 // miss if bucket->sel == 0
// 判断p12（bucket）是否 等于 p10（buckets数组第一个元素）-- 表示前面已经没有了，但是还是没有找到
cmp p12, p10 // wrap if bucket == buckets
// 如果等于，跳转至第3步
b.eq 3f
// 从p12 buckets首地址 - 实际需要平移的内存大小BUCKET_SIZE，得到得到第二个bucket元素，imp-sel分别存入p17-p9，即向前查找
ldp p17, p9, [x12, #-BUCKET_SIZE]! // {imp, sel} = *--bucket
// 跳转至第1步，继续对比 sel 与 cmd
b 1b // loop
LLookupEnd$1:
LLookupRecover$1:
3: // double wrap
// 跳转至JumpMiss 因为是normal ，跳转至__objc_msgSend_uncached
JumpMiss $0
.endmacro
看完这一大篇汇编代码，有的同学可能不太明白，我也是费了老大功夫写这个注释。看不懂汇编没关系，流程弄明白再百度汇编语法慢慢看。
我们来总结一下，我相信我总结的能够让你更加清晰整个流程，把流程弄清楚再来看汇编也许感觉就不一样了。
主要分为以下六步：
1、拿到类的isa之后通过内存平移16个字节，找到我们的cache，就是汇编中的p11
2、从cache里面取出buckets和mask，通过cmd & mask 拿到哈希下标index存入p12
3、根据所得的哈希下标index 和 buckets内存平移，取出哈希下标对应的bucket
4、 判断bucket的sel 与 传入的参数cmd是否相等，如果相等直接返回imp，如果不相等则判断是否是第一个元素，如果是，把当前bucket人为设为最后一个元素，进入到第五个步骤。 如果不是则{imp, sel} = *--bucket，递归向前查找回到第四个步骤，继续进行对比
注意，人为设定到最后一个元素只有一次，设定完就会到第五个步骤
5、找到了第一个元素，人为设定到最后一个元素之后：再递归向前查找：比较 sel 与 传入的参数cmd 是否相等，如果不相等，继续向前查找，直到找到sel等于cmd，返回imp。
6、 如果步骤4和步骤5两次递归完了后还没找到则会跳到__objc_msgSend_uncached，进入慢速查找流程，我们下篇文章再进行分析。
最后，再附上一张objc_msgSend快速查找流程图结束今天的内容
