上一篇传送门：
Runtime系列之OC对象和方法本质
对于之前isa相关知识不完整的部分，我又做了一些补充，下面直接进入今天的正题，通过上一篇我们已经知道了Runtime的概念，对象和方法本质以及对象的结构，接下来我会通过一个案例来深入Runtime的底层源码，来解释为什么Runtime是C，C++以及汇编编写的一套API、OC方法获取的方式、方法具体存储方式、具体查找到IMP的方式等等疑问
我们都知道OC方法函数调用，最终都会通过objc_msgSend进行消息转发，把对应方法编号SEL发送给对应的Class，查找到方法函数实现的指针IMP，找到函数实现的指针IMP就是找到对应的方法实现地址。那么接下来我们就深入Runtime源码来分析查找IMP的这个过程。
案例分析：Objective-C方法调用，通过SEL最终找到IMP在Runtime底层是如何实现的？
通过SEL方法编号查找方法实现指针IMP，苹果提供了两种方案，一种是快速的，一种是慢速的；快速查找的方式就是利用缓存机制，使用汇编进行查找；慢速查找就是利用C、C++递归查找；从查找方式我们就可以理解为什么Runtime是C，C++以及汇编编写的一套API了。下面开始汇编快速查找源码分析：(备注一下Runtime源码在苹果官方文档Apple Open Source里面进行下载，git上也有汉语注释版本的Runtime源码)
一、汇编快速查找
首先打开源码，搜索class {遇到typedef就一直点进去，找到类的结构，
图示：
找到类的结构如下
struct objc_class : objc_object {
// Class ISA; 1、该类的isa
Class superclass; 2、该类的父类
cache_t cache; // formerly cache pointer and vtable 3、该类的缓存
class_data_bits_t bits; // class_rw_t * plus custom rr/alloc flags 4、该类所有信息，其中主要包含class_rw_t
...
}
找到类的结构之后，我们就知道该类的isa指针，该类的父类，以及该类的所有信息，那么这个cache是干啥用的呢？对！就是上面我们所说的缓存功能，提供快速查找IMP。
那么这里有一个疑问了：为什么objc_msgSend为什么要使用汇编来写呢？
先来看看我们的需求：
通过传入一个任意的SEL，最终找到方法实现的IMP指针
现在可以解释为什么要用汇编了，原因如下：
1、C语言不可能写一个函数去实现：保留未知的参数，跳转任意的指针
2、C语言本身还是高级语言，汇编语言可以直接通过寄存器进行操作，要比C语言快很多！
好了，介绍完结果后，我们来一步步的深入源码进行验证。
搜索_objc_msgSend 找到对应汇编代码的ENTRY 和 END_ENTRY部分之间的代码，步骤如图2：(备注：有很多架构版本，我们选最常用的arm64架构的就行了)
接下来我把从304行到347行，ENTRY 和 END_ENTRY 部分之间的汇编代码截取出来，如下
ENTRY _objc_msgSend
UNWIND _objc_msgSend, NoFrame
MESSENGER_START
/// x0 recevier
// 消息接收者 消息名称
cmp x0, #0 // nil check and tagged pointer check
b.le LNilOrTagged // (MSB tagged pointer looks negative)
ldr x13, [x0] // x13 = isa
and x16, x13, #ISA_MASK // x16 = class
LGetIsaDone:
CacheLookup NORMAL // calls imp or objc_msgSend_uncached
LNilOrTagged:
b.eq LReturnZero // nil check
// tagged
mov x10, #0xf000000000000000
cmp x0, x10
b.hs LExtTag
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]
b LGetIsaDone
LExtTag:
// 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
LReturnZero:
// x0 is already zero
mov x1, #0
movi d0, #0
movi d1, #0
movi d2, #0
movi d3, #0
MESSENGER_END_NIL
ret
END_ENTRY _objc_msgSend
加上理解注释以及步骤序号之后，如下
ENTRY _objc_msgSend (1、进入我们当前的_objc_msgSend)
UNWIND _objc_msgSend, NoFrame
MESSENGER_START
/// x0 recevier
// 消息接收者 消息名称
cmp x0, #0 // nil check and tagged pointer check (2、逻辑判断; 我们都知道OC里面所有数据类型比如NSNumber，NSString等都会转化成轻量级的tagged pointer特殊数据类型进行处理，这里代码的意思就是做非对象类型或者nil空对象类型处理，如果不是，就直接不处理，只处理有意义的数据。)
b.le LNilOrTagged // (MSB tagged pointer looks negative) (3、b.le是汇编的跳转，这里就是2步骤中判断后，发现数据无意义会走这里，并且接下来会跳转下面对应逻辑的LNilOrTagged)
ldr x13, [x0] // x13 = isa
and x16, x13, #ISA_MASK // x16 = class
LGetIsaDone: (4、重点来了：如果ISA处理完后，会进行缓存查找CacheLookup，如果CacheLookup缓存查找成功就会直接调用IMP，没有缓存就会跳转进行递归查找)
CacheLookup NORMAL // calls imp or objc_msgSend_uncached
LNilOrTagged:(5、如果为nil，就没有必要继续查找了,继续跳转到下面的LReturnZero里面)
b.eq LReturnZero // nil check
// tagged
mov x10, #0xf000000000000000
cmp x0, x10
b.hs LExtTag
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]
b LGetIsaDone //6、 b指令，跳转指令，调用上面第4步的LGetIsaDone
LExtTag:
// 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 //7、 数据有意义，b指令，跳转指令，调用上面第4步的LGetIsaDone
LReturnZero:
// x0 is already zero
mov x1, #0
movi d0, #0
movi d1, #0
movi d2, #0
movi d3, #0
MESSENGER_END_NIL //(8、如果判断逻辑等于nil之后，走到LReturnZero直接返回，停止分析)
ret
END_ENTRY _objc_msgSend
上面这块的逻辑，我用思维导图整理一下，方便大家的理解，见下图3：
结果虽然出来了，但是我们接下来还是要深入源码仔细分析一下为什么是这样的，以及CacheLookup这个指令底层到底做了什么，我把CacheLookup 代码贴在下面,需要注意的是在上面的操作完成后，调用的是CacheLookup NORMAL，**在下面逻辑中注意$0 == NORMAL的逻辑代码，这个逻辑下的才是准确的，接下里我们看CacheLookup这个宏
/********************************************************************
*
* 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
*
********************************************************************/
#define NORMAL 0
#define GETIMP 1
#define LOOKUP 2
.macro CacheHit
.if $0 == NORMAL
MESSENGER_END_FAST
br x17 // call imp
.elseif $0 == GETIMP
mov x0, x17 // return imp
ret
.elseif $0 == LOOKUP
ret // return imp via x17
.else
.abort oops
.endif
.endmacro
.macro CheckMiss
// miss if bucket->sel == 0
.if $0 == GETIMP
cbz x9, LGetImpMiss
.elseif $0 == NORMAL
cbz x9, __objc_msgSend_uncached
.elseif $0 == LOOKUP
cbz x9, __objc_msgLookup_uncached
.else
.abort oops
.endif
.endmacro
.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
.macro CacheLookup
// x1 = SEL, x16 = isa
ldp x10, x11, [x16, #CACHE] // x10 = buckets, x11 = occupied|mask
and w12, w1, w11 // x12 = _cmd & mask
add x12, x10, x12, LSL #4 // x12 = buckets + ((_cmd & mask)<<4)
ldp x9, x17, [x12] // {x9, x17} = *bucket
1: cmp x9, x1 // if (bucket->sel != _cmd)
b.ne 2f // scan more
CacheHit $0 // call or return imp
2: // not hit: x12 = not-hit bucket
CheckMiss $0 // miss if bucket->sel == 0
cmp x12, x10 // wrap if bucket == buckets
b.eq 3f
ldp x9, x17, [x12, #-16]! // {x9, x17} = *--bucket
b 1b // loop
3: // wrap: x12 = first bucket, w11 = mask
add x12, x12, w11, UXTW #4 // x12 = buckets+(mask<<4)
// Clone scanning loop to miss instead of hang when cache is corrupt.
// The slow path may detect any corruption and halt later.
ldp x9, x17, [x12] // {x9, x17} = *bucket
1: cmp x9, x1 // if (bucket->sel != _cmd)
b.ne 2f // scan more
CacheHit $0 // call or return imp
2: // not hit: x12 = not-hit bucket
CheckMiss $0 // miss if bucket->sel == 0
cmp x12, x10 // wrap if bucket == buckets
b.eq 3f
ldp x9, x17, [x12, #-16]! // {x9, x17} = *--bucket
b 1b // loop
3: // double wrap
JumpMiss $0
.endmacro
把这个宏的NORMAL逻辑剥离出来就是下面这些
1: cmp x9, x1 // if (bucket->sel != _cmd)
b.ne 2f // scan more
CacheHit $0 // call or return imp
2: // not hit: x12 = not-hit bucket
CheckMiss $0 // miss if bucket->sel == 0
cmp x12, x10 // wrap if bucket == buckets
b.eq 3f
ldp x9, x17, [x12, #-16]! // {x9, x17} = *--bucket
b 1b // loop
3: // wrap: x12 = first bucket, w11 = mask
add x12, x12, w11, UXTW #4 // x12 = buckets+(mask<<4)
// Clone scanning loop to miss instead of hang when cache is corrupt.
// The slow path may detect any corruption and halt later.
ldp x9, x17, [x12] // {x9, x17} = *bucket
不难发现其中有三个逻辑：**1、CacheHit 2、CheckMiss 以及3、add**
①、CacheHit逻辑分析
把CacheHit的宏定义从上面一大串汇编代码里面剥离出来，再次强调一下一下，由于我们调用的指令是CacheLookup 后面类型的NORMAL，所以我们看宏定义的时候，只需要分析$0 == NORMAL的逻辑就好了
.macro CacheHit
.if $0 == NORMAL
MESSENGER_END_FAST
br x17 // call imp
.elseif $0 == GETIMP
mov x0, x17 // return imp
ret
.elseif $0 == LOOKUP
ret // return imp via x17
.else
.abort oops
.endif
.endmacro
分析这一部分汇编代码，找到.if $0 == NORMAL 逻辑下面的分支，就如我们之前所说的以及图示里面的，CacheHit就是找到缓存中的IMP了，然后直接调用MESSENGER_END_FAST快速处理，然后call imp ；到此为止第一个逻辑分析完成。
②、开始分析CheckMiss逻辑
接着我们再看CheckMiss的宏定义汇编代码
.macro CheckMiss
// miss if bucket->sel == 0
.if $0 == GETIMP
cbz x9, LGetImpMiss
.elseif $0 == NORMAL
cbz x9, __objc_msgSend_uncached
.elseif $0 == LOOKUP
cbz x9, __objc_msgLookup_uncached
.else
.abort oops
.endif
.endmacro
分析这一部分宏定义，同理找到NORMAL逻辑下面的分支，也是一样，会调用__objc_msgSend_uncached 发送没有缓存的逻辑，到此为止，第二个逻辑分析完成。
③、开始分析add逻辑
看add相关注释我们得知，add功能的作用就是：如果找到imp了，但是缓存里面没有这个imp，汇编会提供add功能，把已经找到的imp添加到缓存中，便于下次查找。
接下来重点来了，如果缓存里面找到IMP就返回，如果没找到就会发送__objc_msgSend_uncached,我们再深入到 __objc_msgSend_uncached里面，看一下这个是什么逻辑！
STATIC_ENTRY __objc_msgSend_uncached
UNWIND __objc_msgSend_uncached, FrameWithNoSaves
// THIS IS NOT A CALLABLE C FUNCTION
// Out-of-band x16 is the class to search
MethodTableLookup
br x17
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 x16 is the class to search
MethodTableLookup
ret
END_ENTRY __objc_msgLookup_uncached
重点来了，__objc_msgSend_uncached如果不在缓存里面，就会调用MethodTableLookup指令去方法列表查询！！！！！！
所以我们的IMP最终来源于MethodTableLookup---方法列表查询。
接下来我们继续深入这个宏MethodTableLookup，继续深入逻辑
.macro MethodTableLookup
// push frame
stp fp, lr, [sp, #-16]!
mov fp, sp
// save parameter registers: x0..x8, q0..q7
sub sp, sp, #(10*8 + 8*16)
stp q0, q1, [sp, #(0*16)]
stp q2, q3, [sp, #(2*16)]
stp q4, q5, [sp, #(4*16)]
stp q6, q7, [sp, #(6*16)]
stp x0, x1, [sp, #(8*16+0*8)]
stp x2, x3, [sp, #(8*16+2*8)]
stp x4, x5, [sp, #(8*16+4*8)]
stp x6, x7, [sp, #(8*16+6*8)]
str x8, [sp, #(8*16+8*8)]
// receiver and selector already in x0 and x1
mov x2, x16
bl __class_lookupMethodAndLoadCache3
// imp in x0
mov x17, x0
// restore registers and return
ldp q0, q1, [sp, #(0*16)]
ldp q2, q3, [sp, #(2*16)]
ldp q4, q5, [sp, #(4*16)]
ldp q6, q7, [sp, #(6*16)]
ldp x0, x1, [sp, #(8*16+0*8)]
ldp x2, x3, [sp, #(8*16+2*8)]
ldp x4, x5, [sp, #(8*16+4*8)]
ldp x6, x7, [sp, #(8*16+6*8)]
ldr x8, [sp, #(8*16+8*8)]
mov sp, fp
ldp fp, lr, [sp], #16
.endmacro
MethodTableLookup这个宏里面一堆汇编代码需要我们结合Class的方法列表结构来分析，才会明白汇编为什么这么写，汇编先暂停到这里，我们回过头去查看objc_class的结构。
搜索class {，进入类的结构，这次我们点开类的所有文件class_data_bits_t bits，在里面再次点击进入class_rw_t,会发现里面有我们很想要的的methods（存储函数的数组），properties（存储属性的数组），protocols（存储协议的数组）,Class的函数就是存储在methods这个数组里面，慢速查找就是回到这个数组里面来递归查找。
struct class_rw_t {
// Be warned that Symbolication knows the layout of this structure.
uint32_t flags;
uint32_t version;
const class_ro_t *ro; //ro的意思就是readonly，只读文件，同理rw就是readwrite，可读可写文件
method_array_t methods; //存储方法的数组
property_array_t properties; //存储属性的数组
protocol_array_t protocols; //存储协议的数组
Class firstSubclass;
Class nextSiblingClass;
char *demangledName;
...
};
点击method_array_t methods;进入查看函数数组的结构，我们发现
method_array_t的结构：method_array_t存储了很多 method_t
class method_array_t :
public list_array_tt<method_t, method_list_t>
{
typedef list_array_tt<method_t, method_list_t> Super;
public:
method_list_t **beginCategoryMethodLists() {
return beginLists();
}
method_list_t **endCategoryMethodLists(Class cls);
method_array_t duplicate() {
return Super::duplicate<method_array_t>();
}
};
继续点击method_t，我们找到了它的结构，里面存储了我们想要找到关键信息：SEL name以及IMP imp，其实method_t就是一个哈希表，这个哈希表把name和imp以键值对的形式存储起来！
struct method_t {
SEL name;
const char *types;
IMP imp;
struct SortBySELAddress :
public std::binary_function<const method_t&,
const method_t&, bool>
{
bool operator() (const method_t& lhs,
const method_t& rhs)
{ return lhs.name < rhs.name; }
};
};
好了，class数据结构分析到这里，接下来我们返回之前MethodTableLookup的宏文件里面，找到__class_lookupMethodAndLoadCache3这句代码，重点又来了！
我们接下来想进入__class_lookupMethodAndLoadCache3继续查看，但是死活搜不到！
此时需要注意，把__class_lookupMethodAndLoadCache3前面去掉一个下划线，再搜，发现_class_lookupMethodAndLoadCache3在objc-runtime-new.mm文件里面，已经从汇编文件跳出来，进入了C和C++文件里面了！
接下来我们继续深入C，C++文件分析剩下的过程：
/***********************************************************************
* _class_lookupMethodAndLoadCache.
* Method lookup for dispatchers ONLY. OTHER CODE SHOULD USE lookUpImp().
* This lookup avoids optimistic cache scan because the dispatcher
* already tried that.
**********************************************************************/
IMP _class_lookupMethodAndLoadCache3(id obj, SEL sel, Class cls)
{
return lookUpImpOrForward(cls, sel, obj,
YES/*initialize*/, NO/*cache*/, YES/*resolver*/);
}
这里return调用了一个C函数，前两个参数需要注意一下，我结合lookUpImpOrForward函数给大家解释一下为什么前两个参数在这里要传固定的布尔值
第一个参数必须传YES！ 正是因为之前的逻辑汇编已经编译过类的所有结构，已经处理过isa，逻辑才会到这里来，所以必须传YES
第二个参数必须传NO！ 代表之前逻辑缓存里面并没有查找到IMP，如果传了YES，就代表缓存里面已经有IMP了，那么之前在汇编的逻辑里面imp就会直接返回去了，逻辑就根本不会走到CheckMiss以及到这里来，所以必须传NO
至此，_objc_msgSend底层源码原理的汇编部分大致分析完毕，下一篇文章会重点围绕lookUpImpOrForward，继续深入分析C/C++部分，这篇到此为止啦~
