objc_msgSend:方法的快速查找

在Cache_t的结构和原理一文中，我们通过insert函数来分析了cache的实现原理。沿着cache_t::insert(Class cls, SEL sel, IMP imp, id receiver)这条主线我们来探索，在insert之前发生了什么，通过查看源码我们找到了void cache_fill(Class cls, SEL sel, IMP imp, id receiver)方法，在cache_fill之前是什么操作呢？

 * objc_msgSend // 1
 * cache_getImp  // 2
 *
 * Cache writers (hold cacheUpdateLock while reading or writing; not PC-checked)
 * cache_fill         (acquires lock) // 3
 * cache_expand       (only called from cache_fill) // 4
 * cache_create       (only called from cache_expand)
 * bcopy               (only called from instrumented cache_expand)
 * flush_caches        (acquires lock)
 * cache_flush        (only called from cache_fill and flush_caches)
 * cache_collect_free (only called from cache_expand and cache_flu

• 1，函数调用会转变为 objc_msgSend函数。
• 2，从cache_t里面查找该方法实现。
• 3，向cache_t里面插入新的bucket(_sel, _imp)
• 4，如果_occupied已达到阈值，则进行扩容。
  我们今天就一起来探索objc_msg_send的方法快速查找。

运行时

代码程序按照执行时机有两种状态编译时和运行时。

编译时：就是编译器把源代码翻译成及其能识别的代码。主要是做一些简单的翻译工作。

• 1，会进行静态类型检查。
• 2，在预编译时，会展开所有的宏定义。
• 3，进行语法分析,语义分析等等。

运行时：就是将代码跑起来，已经被装载到内存中去了。
iOS 中，runtime有俩个版本，一个是Legacy版本，一个是Modern版本（现行版本）。

jiegoutu.png
如上图所示，OC代码会经过llvm(编译器)，将代码转化为runtime System Library能识别的方法。

消息发送初步探索

我们将如下代码通过clang转化为c++

LGPerson *person = [LGPerson alloc];
[person sayHello];

xcrun -sdk iphoneos clang -arch arm64 -rewrite-objc -fobjc-arc -fobjc-runtime=ios-8.0.0 main.m -o main.cpp

上面的代码还转化为

LGPerson *person = ((LGPerson *(*)(id, SEL))(void *)objc_msgSend)((id)objc_getClass("LGPerson"), sel_registerName("alloc"));
((void (*)(id, SEL))(void *)objc_msgSend)((id)person, sel_registerName("sayHello"));

上面C++代码可简化为

LGPerson *person = objc_msgSend(objc_getClass("LGPerson"), sel_registerName("alloc"));
objc_msgSend((id)person, sel_registerName("sayHello"));

从如上代码我们可以看出，sayHello该方法调用，转化为可objc_msgSend函数调用。那objc_msgSend是怎么来发送消息呢，我们来进行下一步探讨。

objc_msgSend

源码中关于objc_msgSend的实现是一段汇编代码

    ENTRY _objc_msgLookup
    UNWIND _objc_msgLookup, NoFrame
    cmp p0, #0          // nil check and tagged pointer check
#if SUPPORT_TAGGED_POINTERS
    b.le    LLookup_NilOrTagged //  (MSB tagged pointer looks negative)
#else
    b.eq    LLookup_Nil
#endif
    ldr p13, [x0]       // p13 = isa
    GetClassFromIsa_p16 p13     // p16 = class  // 1
LLookup_GetIsaDone:
    // returns imp
    CacheLookup LOOKUP, _objc_msgLookup  // 2 

• 1，通过isa信息，来得到类的信息，在isa的结构一文中，我们可以得到，将isa & ISA_MASK就可以得到类信息。
• 2，CacheLookup在cache_t中查找是否有该方法。

下面我们来着重分析 CacheLookup:

CacheLookup

在Cache_t的结构和原理一文中，我们讲解了 cache是如何存储的，接下来，我们来分析它是如何查找的？

cacheLookup的实现如下所示：

.macro CacheLookup
LLookupStart$1:

    // p1 = SEL, p16 = isa
    ldr p11, [x16, #CACHE]              // p11 = mask|buckets

#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    and p10, p11, #0x0000ffffffffffff   // p10 = buckets
    and p12, p1, p11, LSR #48       // x12 = _cmd & mask
#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


    add p12, p10, p12, LSL #(1+PTRSHIFT)
                     // p12 = buckets + ((_cmd & mask) << (1+PTRSHIFT))

    ldp p17, p9, [x12]      // {imp, sel} = *bucket
1:  cmp p9, p1          // if (bucket->sel != _cmd)
    b.ne    2f          //     scan more
    CacheHit $0         // call or return imp
    
2:  // not hit: p12 = not-hit bucket
    CheckMiss $0            // miss if bucket->sel == 0
    cmp p12, p10        // wrap if bucket == buckets
    b.eq    3f
    ldp p17, p9, [x12, #-BUCKET_SIZE]!  // {imp, sel} = *--bucket
    b   1b          // loop

3:  // wrap: p12 = first bucket, w11 = mask
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
    add p12, p12, p11, LSR #(48 - (1+PTRSHIFT))
                    // 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.

    ldp p17, p9, [x12]      // {imp, sel} = *bucket
1:  cmp p9, p1          // if (bucket->sel != _cmd)
    b.ne    2f          //     scan more
    CacheHit $0         // call or return imp
    
2:  // not hit: p12 = not-hit bucket
    CheckMiss $0            // miss if bucket->sel == 0
    cmp p12, p10        // wrap if bucket == buckets
    b.eq    3f
    ldp p17, p9, [x12, #-BUCKET_SIZE]!  // {imp, sel} = *--bucket
    b   1b          // loop

LLookupEnd$1:
LLookupRecover$1:
3:  // double wrap
    JumpMiss $0

.endmacro

其大致流程如下

• 1，将 sel与mask进行与运算，得到一个索引值，
• 2，如果在buckets中，直接命中（_imp == 查找的imp），则返回对应的_imp。
• 3，如果 在buckets中，直接命中且 _imp != 查找的imp，则在buckets的尾部开始查找该_imp。
• 4，如果在buckets中没有找到该_imp，则返回nil，会调用objc_msgSend_uncached方法。

总结

在这篇文章里，我们探索了探索了objc_msgSend里面的快速查找流程，主要是从cache_t缓存的方法中进行查找。