message 机制可以说是 objc 最重要的机制。零零散散看了 method cache、method search 以及 message forward，今天把三者串起来总结一下。 message 机制带来很大的灵活性，调用和实现完全解耦，实现上也力求高效，非常值得学习。流程概括来说可以分为三步
- 查 cache ，命中则返回 imp，miss 进入下一步
- 搜索 method list，found 则返回 imp，not found 进入下一步
- resolve method or forward message ，otherwise cann’t respond to selector
一、查 cache
查 cache 是用汇编实现的。理解算法（流程）之前我们先了解一下数据结构（内存模型）。我们知道对象内存模型里面有个 isa 指针，而 isa_t 结构体里面主要是一个类指针，另外还有一些位标志数据（has_assoc、weakly_referenced、extra_rc 等）。类对象模型里面，首先是 superClass，接下来就是我们的主角 cache。cache 是个哈希数组，使用线性探测再散列的方式解决冲突。
struct objc_object {
private:
isa_t isa;
...
union isa_t
{
isa_t() { }
isa_t(uintptr_t value) : bits(value) { }
Class cls;
uintptr_t bits;
...
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
...
struct cache_t {
struct bucket_t *_buckets;
mask_t _mask;
mask_t _occupied;
...
struct bucket_t {
private:
cache_key_t _key;
IMP _imp;
...
然后到了流程这块儿，参考这篇文章，结合源码来说说。这部分源码就在 runtime 源码中，objc-msg-arm64.s，汇编代码。
.macro CacheLookup
// x1 = SEL, x9 = isa
ldp x10, x11, [x9, #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 x16, x17, [x12] // {x16, x17} = *bucket
1: cmp x16, 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->cls == 0
cmp x12, x10 // wrap if bucket == buckets
b.eq 3f
ldp x16, x17, [x12, #-16]! // {x16, 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 x16, x17, [x12] // {x16, x17} = *bucket
1: cmp x16, 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->cls == 0
cmp x12, x10 // wrap if bucket == buckets
b.eq 3f
ldp x16, x17, [x12, #-16]! // {x16, x17} = *--bucket
b 1b // loop
3: // double wrap
JumpMiss $0
.endmacro
参考文章解析的非常详细了。我说一下我的理解。首先程序运行至此，argument 已经塞到了寄存器中，如注释，x1 里面是 sel，x9 里面是 isa，isa 的类型是 objc_class，它的结构是这样的，superclass 指针之后就是 cache 指针。
ldp x10, x11, [x9, #CACHE]
其中 CACHE 是宏，值是 16，因为结构体里还有一个 superclass。如注释，这时 x10 里是 buckets，x11 里面是 mask 和 occupied，它们是 32 位的，可以一起放到 x11 中。
and w12, w1, w11
如注释，sel 和 mask 相与，放到 w12 中，是最简单的 hash，确定 target bucket index。
add x12, x10, x12, LSL #4
如注释，计算 target bucket 的地址。
ldp x16, x17, [x12]
读取 bucket 的内容，分别是 sel 和 imp，放在 x16, x17 当中。
二、在 method list 里查找 imp
整个流程可以看 lookUpImpOrForward 方法。中间还涉及类的 realize、查父类方法列表等细节。这里先单拎 getMethodNoSuper_nolock 说说，调用链接下来是遍历类的方法列表的列表，调用 search_method_list 搜索每一个方法列表，
/***********************************************************************
* getMethodNoSuper_nolock
* fixme
* Locking: runtimeLock must be read- or write-locked by the caller
**********************************************************************/
static method_t *search_method_list(const method_list_t *mlist, SEL sel)
{
int methodListIsFixedUp = mlist->isFixedUp();
int methodListHasExpectedSize = mlist->entsize() == sizeof(method_t);
if (__builtin_expect(methodListIsFixedUp && methodListHasExpectedSize, 1)) {
return findMethodInSortedMethodList(sel, mlist);
} else {
// Linear search of unsorted method list
for (auto& meth : *mlist) {
if (meth.name == sel) return &meth;
}
}
#if DEBUG
// sanity-check negative results
if (mlist->isFixedUp()) {
for (auto& meth : *mlist) {
if (meth.name == sel) {
_objc_fatal("linear search worked when binary search did not");
}
}
}
#endif
return nil;
}
在这个方法里面，根据方法列表是否排过序，分别调用 findMethodInSortedMethodList 进行二分查找或循环查找。
static method_t *findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
assert(list);
const method_t * const first = &list->first;
const method_t *base = first;
const method_t *probe;
uintptr_t keyValue = (uintptr_t)key;
uint32_t count;
for (count = list->count; count != 0; count >>= 1) {
probe = base + (count >> 1);
uintptr_t probeValue = (uintptr_t)probe->name;
if (keyValue == probeValue) {
// `probe` is a match.
// Rewind looking for the *first* occurrence of this value.
// This is required for correct category overrides.
while (probe > first && keyValue == (uintptr_t)probe[-1].name) {
probe--;
}
return (method_t *)probe;
}
if (keyValue > probeValue) {
base = probe + 1;
count--;
}
}
return nil;
}
三、resolve & forward
resolve 如果 cls 是 meta class，代表 object 是 class，调用 _class_resolveClassMethod，否则调用 _class_resolveInstanceMethod。这个时候是我们可以进行 hook 的第一个机会，我们可以在这个时候把实现添加到 method list 中。在这之后，lookUpImpOrForward 会 goto retry，上面的流程都会再走一遍（try this class’s cache，try this class’s method lists，try superclass caches and method lists，try resolve method）当然会有一个是否已经尝试了 resolve 的标识，防止循环的 go to retry。如果 resolve 也没有提供 imp，runtime 会进行 forward。
forward 是我们可以进行 hook 的第二个机会。runtime 会把上面的流程都没法识别的 sel 对应的的 imp 设为 _objc_msgForward_impcache。用汇编实现。一个是效率考虑。一个是函数参数的传递考虑。（这个汇编注释比较少，看不懂，下次再琢磨。看它怎么再回调 c 的代码转移控制流的。这里没弄明白控制流是怎样的。）根据文档，runtime 会先后调用 forwardingTargetForSelector 和 forwardInvocation 这个两个方法继续尝试进行消息的响应。forwardingTargetForSelector 是为了你快速的把消息转发给别的对象而进行的便捷设计。forwardInvocation 则是给你最大的自由度去修改这个 invocation。如果你不实现这个方法，就会调用 NSObject 的默认实现，默认实现调用了 doesNotRecognizeSelector 方法，产生 unrecognized selector sent to instance 这个我们熟悉的 runtime 错误。
![Youmustbeasurprisesomeoneislookingforwardto[图]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)