前言

Runtime 消息发送与转发流程总是大家关注的重点，却常常忽略方法缓存机制这个显著提升 objc_msgSend 性能的幕后功臣。

本文会通过源码梳理消息发送与转发流程，重点分析方法缓存机制的实现细节。行文过程中会涉及到一些汇编代码，不过不影响理解核心逻辑。

源码基于 Runtime 750，arm64 架构。

一、从 objc_msgSend 谈起

注意：arm64 汇编代码会出现很多p字母，实际上是一个宏，64 位下是x，32 位下是w，p就是寄存器。

在分析缓存机制之前，先梳理一下消息发送与转发的流程，找到何时进行缓存的存储与读取。

objc_msgSend

objc_msgSend 代码如下：

    ENTRY _objc_msgSend
    UNWIND _objc_msgSend, NoFram

    ...// 处理对象是 tagged pointer 或 nil 的情况（x0 存的是 objc_object 对象地址）

    ldr p13, [x0]            // p13 = isa 把 x0 指向内存的前 64 位放到 p13（即是 objc_object 的 isa 成员变量）
    GetClassFromIsa_p16 p13  // p16 = class 通过 isa 找到 class
LGetIsaDone:
    CacheLookup NORMAL       // 从方法缓存或方法列表中找到 IMP 并调用
    ...

在 64 位系统下GetClassFromIsa_p16宏代码为：

.macro GetClassFromIsa_p16
    ...
    and p16, $0, #ISA_MASK  // #define ISA_MASK 0x0000000ffffffff8ULL
    ...

$0获取宏的第一个参数，调用时传的p13，即是isa。这一步做的操作就是使用ISA_MASK掩码找到isa变量中的Class并放入p16（isa是union isa_t类型，在很多系统中已经不是单纯的指向Class，还包含了内存管理等信息，所以需要用掩码来获取）。

CacheLookup

CacheLookup包含读取方法缓存的核心逻辑，代码后面分析。

目前只需要知道它会查询当前Class的方法缓存，主要产生两种结果：若缓存命中，返回IMP或调用IMP；若缓存未命中，调用__objc_msgSend_uncached (找到IMP会调用) 或__objc_msgLookup_uncached (找到IMP不会调用) 方法。

    STATIC_ENTRY __objc_msgSend_uncached
    UNWIND __objc_msgSend_uncached, FrameWithNoSaves

    MethodTableLookup
    TailCallFunctionPointer x17

    END_ENTRY __objc_msgSend_uncached

MethodTableLookup后面就是较为复杂的方法查询逻辑了，若找到了IMP会放到x17寄存器中，然后把x17的值传递给TailCallFunctionPointer宏调用方法。

MethodTableLookup

.macro MethodTableLookup
    // push frame
    SignLR
    stp fp, lr, [sp, #-16]!
    mov fp, sp

    ...// save registers: x0..x8, q0..q7

    // receiver and selector already in x0 and x1
    mov x2, x16
    bl  __class_lookupMethodAndLoadCache3

    // IMP in x0
    mov x17, x0
    
    ...// restore registers

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

由于这个宏内部要跳转函数，意味着lr的变化，所以开辟栈空间后需要把之前的fp/lr值存储到栈上便于复位状态。笔者删除了save registers和restore registers的逻辑，其实就是将各个寄存器的值先存储到栈上，内部函数帧释放时便于复位寄存器的值。

在调用完__class_lookupMethodAndLoadCache3后会把返回在x0的IMP值复制到x17中。

__class_lookupMethodAndLoadCache3是一个 C 函数，跳转之前把x16的值复制到x2中（x16目前存储的就是GetClassFromIsa_p16代码找到的对象的Class），那么此时寄存器布局就是：x0 -> receiver / x1 -> selector / x2 -> class，也就对应了这个方法的参数列表：

IMP _class_lookupMethodAndLoadCache3(id obj, SEL sel, Class cls) {
    return lookUpImpOrForward(cls, sel, obj, 
                              YES/*initialize*/, NO/*cache*/, YES/*resolver*/);
}

lookUpImpOrForward

lookUpImpOrForward方法比较复杂，简化逻辑如下：

IMP lookUpImpOrForward(Class cls, SEL sel, id inst, 
                       bool initialize, bool cache, bool resolver) {
    IMP imp = nil;
    bool triedResolver = NO;
    ...
    // cache 为 YES 查找方法缓存
    if (cache) {
        imp = cache_getImp(cls, sel);
        if (imp) return imp;
    }
    // 加锁
    runtimeLock.lock();
    // 若需要，进行类的初始化以及调用 +initialize 等工作
    ...

retry:
    // 在当前类方法缓存中查找 IMP
    imp = cache_getImp(cls, sel);
    if (imp) goto done;
    // 在当前类方法列表中查找 IMP
    if (找到 IMP) {
        把 IMP 存方法缓存
        goto done;
    }
    // 在父类的方法缓存/方法列表中查找 IMP
    while (Class cur = cls->superClass; cur != nil; cur = cur->superClass) {
        if (在方法缓存中找到 IMP) {
            if (IMP == _objc_msgForward_impcache) { break; }
            把 IMP 存入当前类 cls 的方法缓存
            goto done;
        }
        if (在方法列表中找到 IMP) {
            把 IMP 存入当前类 cls 的方法缓存
            goto done;
        }
    }
    // 没有找到 IMP，尝试进行动态消息处理
    if (resolver  &&  !triedResolver) {
        runtimeLock.unlock();
        _class_resolveMethod(cls, sel, inst);
        runtimeLock.lock();
        triedResolver = YES;
        goto retry;
    }
    // 若动态消息处理失败，IMP 指向一个函数并将 IMP 存方法缓存
    imp = (IMP)_objc_msgForward_impcache;
    cache_fill(cls, sel, imp, inst);

done:
    runtimeLock.unlock();
    return imp;
}

方法缓存的存取

方法缓存存储符合一般逻辑，只要找到了IMP就会进行缓存，加入方法缓存都会调用cache_fill方法。需要注意的是，如果是从父类链中找到的方法，仍然会加入当前类的缓存列表，这样能大大提高查找在父类链中方法的效率。

可能读者会疑惑这个方法为什么还会去取缓存？前面一堆汇编方法走到这里的时候理论上当前类是已经没有对应SEL的方法缓存了。前面个cache_getImp方法是因为lookUpImpOrForward函数会被其它函数调用，并不在前面笔者分析的流程中；而retry:下面的cache_getImp是因为在动态消息处理的时候可能会插入相关IMP然后goto retry。

方法列表的查询

类的方法列表的查询通过getMethodNoSuper_nolock-> search_method_list方法处理，具体的逻辑不展开了，只需知道若方法列表是排过序的会使用二分搜索去查；否则就是一个简单的遍历查询。所以在没有方法缓存的情况下方法的查询效率是很低的，时间复杂度要么是 O(logn) 要么是 O(n)。

消息转发的逻辑

在_class_resolveMethod方法前面调用了unlock()和lock()，关闭了类的保护状态，便于开发者改变类的方法列表等。

_class_resolveMethod会向对象发送+resolveInstanceMethod（实例对象）或+resolveClassMethod（类对象）方法，开发者可以在这两个方法中为类动态加入IMP，_class_resolveMethod出栈后走goto retry会重新尝试查找方法的逻辑。

当然，若开发者没有做处理，IMP仍然找不到，通过!triedResolver避免二次动态消息处理，然后就会让imp = (IMP)_objc_msgForward_impcache。如此一来，当lookUpImpOrForward函数帧释放时，在上层看来仍然是找到IMP了，这个方法就是_objc_msgForward_impcache。那么在前面分析的__objc_msgSend_uncached方法就仍然会调用这个IMP，接下来就是真正的消息转发阶段了。

    STATIC_ENTRY __objc_msgForward_impcache
    b   __objc_msgForward
    END_ENTRY __objc_msgForward_impcache

    ENTRY __objc_msgForward
    adrp    x17, __objc_forward_handler@PAGE
    ldr p17, [x17, __objc_forward_handler@PAGEOFF]
    TailCallFunctionPointer x17
    END_ENTRY __objc_msgForward

可以发现通过页地址加页偏移的方式，拿到__objc_forward_handler的地址并调用，它是一个函数指针，在OBJC2下有默认实现：

__attribute__((noreturn)) void 
objc_defaultForwardHandler(id self, SEL sel)
{
    _objc_fatal("%c[%s %s]: unrecognized selector sent to instance %p "
                "(no message forward handler is installed)", 
                class_isMetaClass(object_getClass(self)) ? '+' : '-', 
                object_getClassName(self), sel_getName(sel), self);
}
void *_objc_forward_handler = (void*)objc_defaultForwardHandler;

最终看到了熟悉的unrecognized selector sent to instance描述。

而对于开发者熟悉的-forwardingTargetForSelector:重定向方法、-forwardInvocation:转发方法，Runtime 源码中没有啥痕迹，在文件后面只有一个更改_objc_forward_handler指针的函数（笔者玩儿不动了，可以猜测方法重定向和方法转发是通过改变这个指针做逻辑的，感兴趣可以查看杨帝的逆向分析消息转发文章：Objective-C 消息发送与转发机制原理）：

void objc_setForwardHandler(void *fwd, void *fwd_stret) {
    _objc_forward_handler = fwd;
    ...
}

小结

到目前为止，整个消息发送机制算是比较清晰了，在按图索骥的过程中，发现了不少方法缓存的存取操作，主要是cache_getImp和cache_fill函数。当然，方法缓存还有清理操作，后面再谈。接下来的部分就着重分析方法缓存的实现细节。

二、方法缓存的数据结构基础

cache_t是方法缓存的数据结构，在objc_class中cache变量偏移64*2位：

struct objc_class : objc_object {
    // Class ISA;
    Class superclass;
    cache_t cache; 
    class_data_bits_t bits; 
...

bits存储了类的属性、协议、方法等，这里不展开描述。cache_t的结构也很简单：

struct cache_t {
    struct bucket_t *_buckets;  // bucket_t 数组
    mask_t _mask;               // 容量缓存个数减1
    mask_t _occupied;           // 有效缓存个数
...

咋一看就像是一个散列表，这和weak弱引用的底层数据结构（weak_table_t/weak_entry_t）如出一辙。bucket_t在 arm64 下代码如下：

struct bucket_t {
    MethodCacheIMP _imp;
    cache_key_t _key;
...

MethodCacheIMP就是IMP别名，cache_key_t就是unsigned long。

三、方法缓存的写入

cache_fill

cache_fill是方法缓存写入的入口方法：

void cache_fill(Class cls, SEL sel, IMP imp, id receiver) {
    mutex_locker_t lock(cacheUpdateLock);
    cache_fill_nolock(cls, sel, imp, receiver);
}

这个lock看起来很奇怪，进去一看实际上是这样一个类：

    class locker : nocopy_t {
        mutex_tt& lock;
    public:
        locker(mutex_tt& newLock) 
            : lock(newLock) { lock.lock(); }
        ~locker() { lock.unlock(); }
    };

在locker构造时加锁，析构时解锁，正好保护了方法作用域内的方法调用。这和 EasyReact 中大量使用的__attribute__((cleanup(AnyFUNC), unused))如出一辙，都是为了实现自动解锁的效果。

cache_fill_nolock

cache_fill_nolock是写入的核心逻辑（为了简短有所修改）：

static void cache_fill_nolock(Class cls, SEL sel, IMP imp, id receiver)
{
    ...
    // 在类初始化之前不允许写入缓存
    if (!cls->isInitialized()) return;
    // 在走到这里的时候，可能在占有 cacheUpdateLock 的时候缓存已经被其它线程写入了，所以先查询一次缓存
    if (cache_getImp(cls, sel)) return;

    cache_t *cache = getCache(cls);
    cache_key_t key = getKey(sel);
    mask_t newOccupied = cache->occupied() + 1;
    mask_t capacity = cache->capacity();

    if (cache->isConstantEmptyCache()) {
        // 如果缓存是只读的，重新分配内存
        cache->reallocate(capacity, capacity ?: INIT_CACHE_SIZE);
    } else if (newOccupied > capacity / 4 * 3) {
        // 如果有效缓存数量超过了 3/4 就进行扩容
        cache->expand();
    }

    // 在散列表中找到一个空置的 bucket 写入数据
    bucket_t *bucket = cache->find(key, receiver);
    if (bucket->key() == 0) cache->incrementOccupied();
    bucket->set(key, imp);
}

锁的抢占

cache_fill方法虽然已经加了锁，但有可能多个线程同时访问，且它们都是往同一个Class添加同一个SEL，若有一个线程占有锁后更新成功，其它线程在空转或挂起一段时间后，就没必要再次写入缓存了，所以if (cache_getImp(cls, sel)) return;这句话是必要的。

这也是个保险措施，因为调用方可能在没有判断Class的某个SEL是否有缓存的时候就调用该方法。

散列表内存分配

void cache_t::reallocate(mask_t oldCapacity, mask_t newCapacity)
{
    bool freeOld = canBeFreed();
    bucket_t *oldBuckets = buckets();
    bucket_t *newBuckets = allocateBuckets(newCapacity);
    ...
    setBucketsAndMask(newBuckets, newCapacity - 1);
    if (freeOld) {
        cache_collect_free(oldBuckets, oldCapacity);
        cache_collect(false);
    }
}

直接将旧的bucket_t数组释放了，然后创建新的数组，开辟内存方法allocateBuckets很简单，就是开辟newCapacity * sizeof(bucket_t)的空间。那么可以确定的是，方法缓存散列表每次分配内存都会放弃之前的缓存。

后面的赋值方法蛮有意思：

#define mega_barrier() \
    __asm__ __volatile__( \
        "dsb    ish" \
        : : : "memory")

void cache_t::setBucketsAndMask(struct bucket_t *newBuckets, mask_t newMask) {
    mega_barrier();
    _buckets = newBuckets;
    mega_barrier();
    _mask = newMask;
    _occupied = 0;
}

因为抛弃了之前的缓存，所以_occupied置为 0。mega_barrier这个内联汇编使用__volatile__关键字阻止编译器缓存变量到寄存器不写回，使用memory内存屏障避免 CPU 使用寄存器来优化执行指令，使用dsb ish隔离指令在它前面的存储器访问操作都执行完毕后，才执行在它后面的指令。这一个使尽浑身解数的宏是为了干嘛呢？

对于cache_t来说，读取_buckets和_mask都是没有加锁的，那么就一定要保证_buckets的实际长度始终大于_mask，最坏的情况不过只是访问不到已有的缓存，不然在进行 hash 运算后很可能访问到错误或非法的内存。

那么第二个mega_barrier()就是为了保证新的_buckets始终会在新的_mask之前赋好值。当然这有个前提，就是新_buckets的长度始终大于旧的。在cache_t算法中并没有削减_buckets内存的逻辑，只有一个清空_buckets数组每个bucket的key/imp的逻辑（清空后内存为 readonly），所以这个前提是能保证的。

在前面cache_fill_nolock方法的if (cache->isConstantEmptyCache())分支正是内存被清空后标记为 readonly 的逻辑，重新分配内存时会开辟一个INIT_CACHE_SIZE (8) 长度的空间，可能有读者会疑问这个时候不就是新_buckets的长度小于旧的么？

其实不然，在清空_buckets时虽然没有削减内存，但_occupied（有效缓存数量）会置为 0，也就是说这种情况下是不会有其它线程访问的。

第一个mega_barrier()就比较梦幻了，笔者可能理解有误：

从newBuckets指针开辟内存到赋值给_buckets的模拟如下：

1、开辟堆内存（地址 0x111）
2、x0 = 0x111
3、_buckets = x0

由于内存访问比寄存器访问慢，很可能被操作系统优化成这样：

1、x0 = 0x111
2、_buckets = x0
3、开辟堆内存（地址 0x111）

那么第三步执行之前_buckets已经有值了，但这个内存还是非法的，所以mega_barrier()起到了关键作用，让第 2 部执行之前必须把开辟堆内存的操作执行完毕。

散列表内存释放

canBeFreed()就是判断这个旧的_buckets是不是清理过后只读的，若不是就可以释放（清理逻辑后面分析）。

释放有两步操作：

第一步cache_collect_free(oldBuckets, oldCapacity);是将待释放的oldBuckets插入一个全局的二维数组：

static bucket_t **garbage_refs = 0;

具体的算法不多说了，反正就是garbage_refs满了时会以两倍的容量扩容。

第二步cache_collect(false);内部会判断garbage_refs的大小，若小于32*1024什么也不做。否则会进入一个循环判断，若进程中没有缓存的访问操作才进行真正的内存释放。

这么做的目的应该也是为了访问安全，保证在对一块cache_t内存访问时不会去释放这块内存。

可以看出，为了访问cache_t的成员变量时不加锁，付出了很大的努力，但是对于这样一个高频访问的缓存机制，这些努力都是值得的。

散列表的扩容

void cache_t::expand() {
    ...
    uint32_t oldCapacity = capacity();
    uint32_t newCapacity = oldCapacity ? oldCapacity*2 : INIT_CACHE_SIZE;
    // 越界处理
    if ((uint32_t)(mask_t)newCapacity != newCapacity) {
        newCapacity = oldCapacity;
    }
    reallocate(oldCapacity, newCapacity);
}

cache_t的_mask成员变量是mask_t类型的，定义为：

#if __LP64__
typedef uint32_t mask_t;  // x86_64 & arm64 asm are less efficient with 16-bits
#else
typedef uint16_t mask_t;
#endif

如注释所说，64 位系统使用 32 位的整形效率较高。上面newCapacity是使用uint32_t运算的，所以若mask_t是 16 位时可能越界，若越界就放弃扩容，只是调用reallocate重新分配和之前等大的内存。

由于之前分析分配内存方法reallocate总是创建新的内存放弃旧的，所以每次扩容都会放弃旧的缓存。可能会担心放弃旧缓存导致消息发送效率下降，其实散列表容量是以两倍的速度扩展的，初始也是 8 个，对于大部分类来说，拓展少许的几次就够了。

扩容时放弃之前的缓存能带来另外一个好处：不用把旧缓存依次按照 hash 算法写入散列表（因为扩容后散列表的容量会变化，将直接影响 hash 值会被掩码截取的对象，所以不得不使用 hash
算法重新插入所有对象），试想若不放弃旧缓存，那将旧缓存同步到新散列表至少有 O(n) 时间消耗，这个过程必然缓存的读取变得不再安全。

散列表的写入

写入操作的核心操作就是通过cache_t的find函数读取一个可用的bucket_t：

bucket_t * cache_t::find(cache_key_t k, id receiver) {
    bucket_t *b = buckets();
    mask_t m = mask();
    mask_t begin = cache_hash(k, m);
    mask_t i = begin;
    do {
        if (b[i].key() == 0  ||  b[i].key() == k) {
            return &b[i];
        }
    } while ((i = cache_next(i, m)) != begin);
    ...
}

cache_hash散列算法就是简单的操作：(mask_t)(key & mask)，然后直接到数组中找出bucket.key()比较，若key为 0 或与目标一致就返回这个bucket的地址。

当发生 hash 碰撞时，就使用cache_next将 hash 值累加 1，以此轮询直到找到空位。cache_next代码为(i+1) & mask，就算 hash 值累加到数组最大值还未找到空位，又会回到数组头部继续寻找。由于在容量达到 3/4 时散列表就会扩容，所以这个find操作是必然能找到空位的。

由于bucket.key() == 0表示这个bucket为空，所以在上层方法中有这样一句代码（_occupied++）：

if (bucket->key() == 0) cache->incrementOccupied();

四、方法缓存的读取

调用objc_msgSend或者cache_getImp中都会调用CacheLookup宏，它们的区别是调用时传的参数不同：

objc_msgSend -> CacheLookup NORMAL
cache_getImp -> CacheLookup GETIMP

下面分析一下CacheLookup的上半截核心代码：

    .macro CacheLookup
        // p1 = SEL, p16 = isa
1        ldp    p10, p11, [x16, #CACHE] // p10 = buckets, p11 = occupied|mask
    #if !__LP64__
         and    w11, w11, 0xffff    // p11 = mask
    #endif
2        and    w12, w1, w11        // x12 = _cmd & mask
3        add    p12, p10, p12, LSL #(1+PTRSHIFT)
                         // p12 = buckets + ((_cmd & mask) << (1+PTRSHIFT))

4        ldp    p17, p9, [x12]      // {imp, sel} = *bucket
5    1: cmp p9, p1          // if (bucket->sel != _cmd)
6        b.ne   2f          //     scan more
7        CacheHit $0            // call or return imp

     2: // not hit: p12 = not-hit bucket
8        CheckMiss $0           // miss if bucket->sel == 0
9        cmp    p12, p10        // wrap if bucket == buckets
10       b.eq   3f
11       ldp    p17, p9, [x12, #-BUCKET_SIZE]!  // {imp, sel} = *--bucket
12       b  1b          // loop
         ...

实际上注释就已经把整个逻辑说明得比较明白了，下面笔者进行一些解释让读者看起来更容易（注意起始的寄存器状态p1 = SEL, p16 = isa）：

• 第 1 行：有定义#define CACHE (2 * __SIZEOF_POINTER__)，所以 64 位系统下CACHE == 64*2，根据数据结构可知这正是objc_class中cache成员变量的偏移量，而cache_t中的第一个 64 位就是_buckets指针，mask_t是 32 位，所以第二个 64 位就是_mask + _occupied。
• 第 2 行：x11寄存器放的_mask + _occupied，那w11就是低 32 位_mask，_cmd & mask就是方法缓存散列表的 hash 算法，所以x12现在就是 hash key 了。
• 第 3 行：通过 hash key 算出指针偏移，找到其对应的bucket_t。PTRSHIFT字面意思是指针偏移，虽然笔者没有找到它的定义，但可以试着推断。由于<< 1就是翻一倍，那么buckets + ((_cmd & mask) << (1+PTRSHIFT)可以转化为：buckets + ((_cmd & mask) * (2 的 1+PTRSHIFT 次方)，一个bucket_t 128 位大小，那可以推断这个PTRSHIFT == 6。我们知道mask是总长度 -1 的值，恰好适用于这里的算法，所以这可能也是为什么存储mask要 -1 的一个原因。
• 第 4 行：x12存了 hash key 对应的bucket_t对象地址了，将bucket的两个成员变量分别取出，现在p17 -> imp / p9 -> sel。
• 第 5 行：p1存的是目标SEL，所以这里是比较一下。
• 第 6 行：如果状态寄存器是 not equel (ne)，则跳转到2:，即第 8 行。
• 第 7 行：命中缓存找到 IMP，调用CacheHit，CacheHit根据$0判断，若是NORMAL则调用IMP；若是GETIMP则返回IMP。
• 第 8 行：调用CheckMiss检查缓存是否丢失，其实就是看p9 (sel) 是否为 0。若为 0 表示缓存丢失都会发生跳转，CacheLookup后面的汇编代码也不会走了。当$0是NORMAL则调用前面分析过的__objc_msgSend_uncached；当$0是GETIMP则跳转到LGetImpMiss，不要奇怪LGetImpMiss是个啥，CacheLookup和CheckMiss都是宏，上层调用有可能就是cache_getImp（跳到LGetImpMiss就复位了）：

    STATIC_ENTRY _cache_getImp
    GetClassFromIsa_p16 p0
    CacheLookup GETIMP
LGetImpMiss:
    mov p0, #0  // 复位
    ret
    END_ENTRY _cache_getImp

• 第 9 行：p10就是数组指针的头部，与当前找到的bucket比较。
• 第 10 行：若相等说明循环完成还没找到缓存，则跳转到3f (暂时不管实现，反正就是跳出 hash 算法查找)。
• 第 11 行：说明 hash 冲突了，有定义#define BUCKET_SIZE (2 * __SIZEOF_POINTER__)，bucket_t正好两个指针大，所以这里就是进行了指针的移动，即向缓存数组前一个下标移动（有点奇怪，方法缓存写入的时候出现 hash 冲突是 +1，这里是 -1，不过总是能完整遍历）。
• 第 12 行：跳转到1b，形成循环。

CacheLookup下半截做了些什么

3:  // wrap: p12 = first bucket, w11 = mask
    add p12, p12, w11, UXTW #(1+PTRSHIFT)
    // p12 = buckets + (mask << 1+PTRSHIFT)
    ...（省略了循环逻辑）

将p12指向散列表末尾，然后做了和前面一样的向前遍历查询。

仔细看前面跳转到3:的指令，若到了这里说明通过 hash key 找到的SEL始终不为 0，但是也不等于目标SEL，也就是始终是 hash 冲突状态，向前遍历完散列表都没有找到目标SEL。

那么，这部分会从散列表尾遍历到散列表头：

散列表头  (上半截遍历部分)  hash key  (未遍历部分)  散列表尾

可能有读者会觉得这个遍历会重复查询上半截代码遍历过的部分，实际上不会。由于散列表会在满 3/4 时就扩容，所以把3:之前未遍历的部分找完就肯定能拿到缓存或者丢失（SEL == 目标或SEL == 0），那循环就会被打破。

五、方法缓存的清理

缓存清理分两种模式，一种是清理散列表的内容，而不是削减散列表的容量；一种是直接释放整个散列表。

清理内容

void cache_erase_nolock(Class cls) {
    ...
    cache_t *cache = getCache(cls);

    mask_t capacity = cache->capacity();
    if (capacity > 0  &&  cache->occupied() > 0) {
        auto oldBuckets = cache->buckets();
        auto buckets = emptyBucketsForCapacity(capacity);
        cache->setBucketsAndMask(buckets, capacity - 1); // also clears occupied
        cache_collect_free(oldBuckets, capacity);
        cache_collect(false);
    }
}

主要是将旧的oldBuckets释放掉，然后通过emptyBucketsForCapacity函数获取新的容量相同的buckets数组，这个方法获取的数组在语言上没有限制只读，但需要把它理解为只读数组。

emptyBucketsForCapacity的大致逻辑：

• 若capacity足够小，返回一个和bucket_t *大小相同的全局变量_objc_empty_cache。
• 否则，从一个静态 hash 表static bucket_t **emptyBucketsList = nil;获取；若未找到，则初始化一个等大的空间，存储进emptyBucketsList，同时把中间空的数组填满，便于 hash key 落在之间的对象获取bucket_t数组。

还记得前面的cache->isConstantEmptyCache()调用判断缓存是否只读么？这个函数实际上就是调用了emptyBucketsForCapacity判断这个缓存数组是否属于只读数组。

为什么要做这么复杂的逻辑来清空一个数组？其实在前面的散列表内存分配一节已经解释了，就是为了保证缓存散列表的读安全。

搜索一下源码，随便列举几个需要调用这个清空方法的地方：

• attachCategories将 Category 信息同步到 Class 时。
• _method_setImplementation / method_exchangeImplementations直接设置方法的实现或交换方法实现时。
• addMethod / addMethods添加方法时。
• setSuperclass设置父类时。

需要清空的情况一句话概括：可能会导致缓存失效时。

直接释放

cache_delete先会通过isConstantEmptyCache函数判断数组内容是否为只读的，若不是只读则调用free直接释放。可能有读者担心这个释放会让方法缓存的读取变得不安全，实际上不会，因为笔者只看到free_class时会调用。

后语

方法缓存机制为了极致的效率而不给读取逻辑加锁，为了让读取安全做了很多额外复杂工作，不过带来的收益是很大的，因为方法缓存读取频率极高。

objc_msgSend 的逻辑无疑是比较复杂的，涉及了不少汇编与操作系统的知识，不过按图索骥分析起来也不是一件很困难的事，在这最后笔者不得不说一句：

iOS 太难了。