iOS RunTime Advance 02 (方法缓存详解)

objc_msgSend函数

当某个对象使用语法[receiver message]来调用某个方法时，其实[receiver message]被编译器转化为:

id objc_msgSend ( id self, SEL op, ... );

现在让我们看一下objc_msgSend它具体是如何发送消息:

1. 首先根据receiver对象的isa指针获取它对应的class
2. 优先在class的cache查找message方法，如果找不到，再到methodLists查找
3. 如果没有在class找到，再到super_class查找
4. 一旦找到message这个方法，就执行它实现的IMP

我们都知道Objective-C的方法决议是动态的，但是在底层一个方法究竟是怎么找到的，方法缓存又是怎么运作的却鲜为人知。本文主要从源码角度探究了Objective-C在runtime层的方法决议（Method resolving）过程和方法缓存（Method cache）的实现。

我们来看下runtime层objc_msgSend的源码。
在objc-msg-arm.s中，objc_msgSend的代码如下：
（ps：Apple为了高度优化objc_msgSend的性能，这个文件是汇编写成的，不过即使我们不懂汇编，详尽的注释也可以让我们一窥其真面目）

ENTRY objc_msgSend
# check whether receiver is nil
teq     a1, #0
    beq     LMsgSendNilReceiver

# save registers and load receiver's class for CacheLookup
stmfd   sp!, {a4,v1}
ldr     v1, [a1, #ISA]

# receiver is non-nil: search the cache
CacheLookup a2, v1, LMsgSendCacheMiss

# cache hit (imp in ip) and CacheLookup returns with nonstret (eq) set, restore registers and call
ldmfd   sp!, {a4,v1}
bx      ip

# cache miss: go search the method lists
LMsgSendCacheMiss:
ldmfd sp!, {a4,v1}
b _objc_msgSend_uncached

LMsgSendNilReceiver:
    mov     a2, #0
    bx      lr

LMsgSendExit:
END_ENTRY objc_msgSend


STATIC_ENTRY objc_msgSend_uncached

# Push stack frame
stmfd sp!, {a1-a4,r7,lr}
add     r7, sp, #16

# Load class and selector
ldr a3, [a1, #ISA] /* class = receiver->isa  */
/* selector already in a2 */
/* receiver already in a1 */

# Do the lookup
MI_CALL_EXTERNAL(__class_lookupMethodAndLoadCache3)
MOVE    ip, a1

# Prep for forwarding, Pop stack frame and call imp
teq v1, v1 /* set nonstret (eq) */
ldmfd sp!, {a1-a4,r7,lr}
bx ip

从上述代码中可以看到，objc_msgSend（就arm平台而言）的消息分发分为以下几个步骤：

• 判断receiver是否为nil，也就是objc_msgSend的第一个参数self，也就是要调用的那个方法所属对象
• 从缓存里寻找，找到了则分发，否则
• 利用objc-class.mm中_class_lookupMethodAndLoadCache3方法去寻找selector
  • 如果支持GC，忽略掉非GC环境的方法（retain等）
  • 从本class的method list寻找selector，如果找到，填充到缓存中，并返回selector，否则
  • 寻找父类的method list，并依次往上寻找，直到找到selector，填充到缓存中，并返回selector，否则
  • 调用_class_resolveMethod，如果可以动态resolve为一个selector，不缓存，方法返回，否则
  • 转发这个selector，否则
• 报错，抛出异常

objc_cache(缓存)

在objc-cache.mm中，objc_cache的定义如下：

struct objc_cache {
    uintptr_t mask;            /* total = mask + 1 */
    uintptr_t occupied;       
    cache_entry *buckets[1];
};

它包含了下面三个变量：

1. mask：可以认为是当前能达到的最大index（从0开始的），所以缓存的size（total）是mask+1
2. occupied：被占用的槽位，因为缓存是以散列表的形式存在的，所以会有空槽，而occupied表示当前被占用的数目
3. buckets：用数组表示的hash表，cache_entry类型，每一个cache_entry代表一个方法缓存(buckets定义在objc_cache的最后，说明这是一个可变长度的数组)
   而cache_entry的定义如下：

typedef struct {
    SEL name;     // same layout as struct old_method
    void *unused;
    IMP imp;  // same layout as struct old_method
} cache_entry;

很明显通过 SEL 和 IMP 就可以调用缓存的方法了。

缓存和散列

缓存的存储使用了散列表。
为什么要用散列表呢？因为散列表检索起来更快（时间复杂度往往是O(1)）

插入缓存

我们来看下是方法缓存如何散列和检索的：

/***********************************************************************
* _cache_fill.  Add the specified method to the specified class' cache.
* Returns NO if the cache entry wasn't added: cache was busy, 
*  class is still being initialized, new entry is a duplicate.
* _cache_fill 添加特定的方法到特定的类缓存中，cache entry没有添加的话返回NO：缓存busy、类还在初始化、entry和已有的entry重复。
* 
* Called only from _class_lookupMethodAndLoadCache and
* class_respondsToMethod and _cache_addForwardEntry.
* 只有以上三个函数调用后，才会调用
* 
* Cache locks: cacheUpdateLock must not be held.
**********************************************************************/
bool _cache_fill(Class cls, Method smt, SEL sel)
{
    uintptr_t newOccupied;
    uintptr_t index;
    cache_entry **buckets;
    cache_entry *entry;
    Cache cache;

    cacheUpdateLock.assertUnlocked();

    // Never cache before +initialize is done
    if (!cls->isInitialized()) {
        return NO;
    }

    // Keep tally of cache additions
    totalCacheFills += 1;

    mutex_locker_t lock(cacheUpdateLock);

    entry = (cache_entry *)smt;

    cache = cls->cache;

    // Make sure the entry wasn't added to the cache by some other thread 
    // before we grabbed the cacheUpdateLock.
    // Don't use _cache_getMethod() because _cache_getMethod() doesn't 
    // return forward:: entries.
    if (_cache_getImp(cls, sel)) {
        return NO; // entry is already cached, didn't add new one
    }

    // Use the cache as-is if it is less than 3/4 full
    newOccupied = cache->occupied + 1;
    if ((newOccupied * 4) <= (cache->mask + 1) * 3) {
        // Cache is less than 3/4 full.
        cache->occupied = (unsigned int)newOccupied;
    } else {
        // Cache is too full. Expand it.
        cache = _cache_expand (cls);

        // Account for the addition
        cache->occupied += 1;
    }

    // 往方法缓存里存放一个方法
    // Scan for the first unused slot and insert there. 查找第一个空槽，插入
    // There is guaranteed to be an empty slot because the 
    // minimum size is 4 and we resized at 3/4 full.
    buckets = (cache_entry **)cache->buckets;
    for (index = CACHE_HASH(sel, cache->mask); 
         buckets[index] != NULL; 
         index = (index+1) & cache->mask)
    {
        // empty
    }
    buckets[index] = entry;

    return YES; // successfully added new cache entry
}

这是往方法缓存里存放一个方法的代码（cache fill），我们可以看到sel被散列后找到一个空槽放在buckets中，而CACHE_HASH的定义如下：

#define CACHE_HASH(sel, mask) (((uintptr_t)(sel)>>2) & (mask))

这段代码就是利用了sel的指针地址和mask做了一下简单计算得出的。

查找缓存

从散列表取缓存则是利用汇编语言写成的（是为了高度优化objc_msgSend而使用汇编的）。我们看objc-msg-arm.mm 里面的CacheLookup方法：

.macro CacheLookup /* selReg, classReg, missLabel */

 MOVE r9, $0, LSR #2          /* index = (sel >> 2) */
 ldr     a4, [$1, #CACHE]        /* cache = class->cache */
 add     a4, a4, #BUCKETS        /* buckets = &cache->buckets */

/* search the cache */
/* a1=receiver, a2 or a3=sel, r9=index, a4=buckets, $1=method */
1:
 ldr     ip, [a4, #NEGMASK]      /* mask = cache->mask */
 and     r9, r9, ip              /* index &= mask           */
 ldr     $1, [a4, r9, LSL #2]    /* method = buckets[index] */
 teq     $1, #0                  /* if (method == NULL)     */
 add     r9, r9, #1              /* index++                 */
 beq     $2                      /*     goto cacheMissLabel */

 ldr     ip, [$1, #METHOD_NAME]  /* load method->method_name        */
 teq     $0, ip                  /* if (method->method_name != sel) */
 bne     1b                      /*     retry                       */

/* cache hit, $1 == method triplet address */
/* Return triplet in $1 and imp in ip      */
 ldr     ip, [$1, #METHOD_IMP]   /* imp = method->method_imp */

.endmacro

先求hash，去buckets里找，找不到按照hash冲突的规则继续向下，直到最后。

特殊方法

为什么会有_class_lookupMethodAndLoadCache3这个方法？
这个方法的实现如下所示：

/***********************************************************************
* _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*/);
}

如果单纯看方法名，这个方法应该会从缓存和方法列表中查找一个方法，但是如第一节所讲，在调用这个方法之前，我们已经是从缓存无法找到这个方法了，所以这个方法避免了再去扫描缓存查找方法的过程，而是直接从方法列表找起。从Apple代码的注释，我们也完全可以了解这一点。不顾一切地追求完美和性能，是一种品质。