iOS底层原理--009：消息慢速查找

1. 流程探索
2. 慢速查找流程
总结

消息快速查找流程中，如果无法命中缓存，进入MissLabelDynamic流程。而MissLabelDynamic即是调用CacheLookup时传入的__objc_msgSend_uncached

1. 流程探索

在objc4-818.2源码中，搜索__objc_msgSend_uncached关键字

在objc-msg-arm64文件中，找到相关汇编代码

STATIC_ENTRY __objc_msgSend_uncached
UNWIND __objc_msgSend_uncached, FrameWithNoSaves
// THIS IS NOT A CALLABLE C FUNCTION
// Out-of-band p15 is the class to search
MethodTableLookup
TailCallFunctionPointer x17
END_ENTRY __objc_msgSend_uncached

不难看出，中间的MethodTableLookup和TailCallFunctionPointer流程，即是核心代码

1.1 `TailCallFunctionPointer`

.macro TailCallFunctionPointer
    // $0 = function pointer value
    br    $0
.endmacro

只包含一句代码，跳转到指定$0的函数地址
$0为调用TailCallFunctionPointer时传入的x17寄存器
由此可见，x17存储的函数地址，在调用TailCallFunctionPointer之前已经存在。所以TailCallFunctionPointer并不是核心代码

1.2 `MethodTableLookup`

.macro MethodTableLookup
    SAVE_REGS MSGSEND
    // lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
    // receiver and selector already in x0 and x1
    mov    x2, x16
    mov    x3, #3
    bl    _lookUpImpOrForward
    // IMP in x0
    mov    x17, x0
    RESTORE_REGS MSGSEND
.endmacro

x17的值由x0提供，而MethodTableLookup中，并没有针对x0的赋值
在汇编中，x0寄存器用作返回值。所以，在_lookUpImpOrForward函数中，一定存在x0寄存器的赋值

1.3 `_lookUpImpOrForward`

在源码中，搜索_lookUpImpOrForward关键字，找不到任何相关的代码实现

这种情况，可以对最初入口__objc_msgSend_uncached设置符号断点，通过汇编结合动态调试寻找线索

运行objc源码，来到__objc_msgSend_uncached断点

调用的lookUpImpOrForward函数，并且不是汇编代码实现，而是objc-runtime-new.mm文件中的C/C++函数

汇编和C/C++的相互调用：

C/C++中调用汇编，在汇编代码中查找时，在方法名称最前面加一个下划线
汇编中调用C/C++函数，在C/C++代码中查找时，去掉方法名称最前面的一个下划线

2. 慢速查找流程

2.1 `C/C++`代码

在objc-runtime-new.mm文件中，找到lookUpImpOrForward的函数实现

2.1.1 `lookUpImpOrForward`

NEVER_INLINE
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    //定义forward_imp
    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    IMP imp = nil;
    Class curClass;
    runtimeLock.assertUnlocked();
    if (slowpath(!cls->isInitialized())) {
        behavior |= LOOKUP_NOCACHE;
    }
    runtimeLock.lock();
    //判断Class是否已被注册
    checkIsKnownClass(cls);
    //初始化类的ro和rw表
    //初始化类的父类及元类
    //递归操作，初始化父类链中的所有类，直到NSObject的父类为nil
    //目的：用于查找方法，当子类没有该方法，在父类中继续查找
    cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
    runtimeLock.assertLocked();
    curClass = cls;
    //死循环，符合条件，通过goto或break跳出循环
    for (unsigned attempts = unreasonableClassCount();;) {
        //在共享缓存中查找，由于多线程写入方法，此时可能会找到之前未缓存的方法
        if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
#if CONFIG_USE_PREOPT_CACHES
            imp = cache_getImp(curClass, sel);
            if (imp) goto done_unlock;
            curClass = curClass->cache.preoptFallbackClass();
#endif
        } else {
            //在当前类的方法列表中查找
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {
                //找到imp，跳转done流程
                imp = meth->imp(false);
                goto done;
            }
            //判断是否存在父类
            if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
                //如果父类为空，imp赋值为forward_imp，停止循环
                imp = forward_imp;
                break;
            }
        }
        if (slowpath(--attempts == 0)) {
            _objc_fatal("Memory corruption in class list.");
        }
        //此时curClass为Superclass，执行父类的快速查找流程
        //在父类的缓存中查找，cache_getImp由汇编代码实现
        imp = cache_getImp(curClass, sel);
        //判断父类中找到的imp是否为forward
        if (slowpath(imp == forward_imp)) {
            //是父类forward_imp，停止循环
            break;
        }
        if (fastpath(imp)) {
            //从父类中找到imp，跳转done流程
            goto done;
        }
    }
    //没有找到方法实现，尝试一次方法解析
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        //动态方法决议的控制条件，表示流程只走一次
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
    }
 done:
    if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) {
#if CONFIG_USE_PREOPT_CACHES
        while (cls->cache.isConstantOptimizedCache(/* strict */true)) {
            cls = cls->cache.preoptFallbackClass();
        }
#endif
        //找到imp，写入缓存，和cache_t::insert形成闭环
        log_and_fill_cache(cls, imp, sel, inst, curClass);
    }
 done_unlock:
    runtimeLock.unlock();
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
    return imp;
}

判断cls是否已注册

◦ 已注册，继续代码流程
◦ 未注册，在checkIsKnownClass函数中报错

判断cls的实现

◦ 实现类的isa走位和父类链

判断cls的初始化

◦ 准备ro和rw表
◦ 初始化类的父类及元类
◦ 递归操作，初始化父类链中的所有类，直到NSObject的父类为nil
◦ 目的：用于查找方法，当子类没有该方法，在父类中继续查找

查找imp

◦ 死循环，符合条件，通过goto或break跳出循环

共享缓存中查找

◦ 由于多线程写入方法，此时可能会找到之前未缓存的方法

当前类中查找

◦ 在当前类的方法列表中查找，使用二分查找法
◦ 找到imp，跳转done流程

判断父类是否存在

◦ 如果父类为空，imp赋值为forward_imp，使用break停止循环，进入动态方法决议流程

在父类中查找imp

◦ 此时curClass为Superclass
◦ 执行父类的快速查找流程
◦ 在父类的缓存中查找，cache_getImp由汇编代码实现
◦ 找到imp，如果是父类的forward_imp，使用break停止循环，进入动态方法决议流程。否则，跳转done流程
◦ 未找到imp，遍历父类继续查找

动态方法决议

◦ 当前类和父类中，都找不方法，进入动态方法决议流程
◦ 判断是否执行过方法动态决议
◦ 如果没有，执行方法动态决议
◦ 如果执行过一次方法动态决议，执行消息转发流程

done流程

◦ 找到imp，写入缓存，和cache_t::insert形成闭环

2.1.2 `realizeAndInitializeIfNeeded_locked`

static Class
realizeAndInitializeIfNeeded_locked(id inst, Class cls, bool initialize)
{
    runtimeLock.assertLocked();
    //!cls->isRealized()为小概率发生事件
    //判断类是否实现isa走位和父类链
    if (slowpath(!cls->isRealized())) {
        cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
    }
    //判断类的初始化，必须先初始化
    if (slowpath(initialize && !cls->isInitialized())) {
        cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
    }
    return cls;
}

realizeClassMaybeSwiftAndLeaveLocked中的realizeClassWithoutSwift用于实现isa走位和父类链
initializeAndLeaveLocked中的initializeNonMetaClass用于类的初始化，准备ro和rw表，并初始化类的父类及元类

2.1.3 `callInitialize`

void callInitialize(Class cls)
{
    ((void(*)(Class, SEL))objc_msgSend)(cls, @selector(initialize));
    asm("");
}

initializeNonMetaClass中的callInitialize，用于类在初始化时，使用objc_msgSend自动发送initialize消息
开发者使用Method Swizzle，可以在类的initialize方法中进行HOOK，相比load方法，不会影响启动速度

2.1.4 `getMethodNoSuper_nolock`

static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
    runtimeLock.assertLocked();
    ASSERT(cls->isRealized());
    auto const methods = cls->data()->methods();
    for (auto mlists = methods.beginLists(),
              end = methods.endLists();
         mlists != end;
         ++mlists)
    {
        method_t *m = search_method_list_inline(*mlists, sel);
        if (m) return m;
    }
    return nil;
}

方法列表的结构中，包含method_array_t和method_list_t，属于二维数组结构
从method_array_t中遍历获取method_list_t

2.1.5 `search_method_list_inline`

ALWAYS_INLINE static method_t *
search_method_list_inline(const method_list_t *mlist, SEL sel)
{
    int methodListIsFixedUp = mlist->isFixedUp();
    int methodListHasExpectedSize = mlist->isExpectedSize();
    if (fastpath(methodListIsFixedUp && methodListHasExpectedSize)) {
        return findMethodInSortedMethodList(sel, mlist);
    } else {
        if (auto *m = findMethodInUnsortedMethodList(sel, mlist))
            return m;
    }
    return nil;
}

findMethodInSortedMethodList：在排序后的方法列表中查找指定方法

2.1.6 `findMethodInSortedMethodList`

ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
    if (list->isSmallList()) {
        if (CONFIG_SHARED_CACHE_RELATIVE_DIRECT_SELECTORS && objc::inSharedCache((uintptr_t)list)) {
            return findMethodInSortedMethodList(key, list, [](method_t &m) { return m.getSmallNameAsSEL(); });
        } else {
            return findMethodInSortedMethodList(key, list, [](method_t &m) { return m.getSmallNameAsSELRef(); });
        }
    } else {
        return findMethodInSortedMethodList(key, list, [](method_t &m) { return m.big().name; });
    }
}

如果是M1电脑，进入isSmallList的判断。否则进入else流程，使用二分查找法，寻找指定方法

2.1.7 二分查找法

template<class getNameFunc>
ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)
{
    ASSERT(list);
    auto first = list->begin();
    auto base = first;
    decltype(first) probe;
    uintptr_t keyValue = (uintptr_t)key;
    uint32_t count;
    //base为low，probe为middle，count为max
    //count >>= 1相当于count/2，砍半
    for (count = list->count; count != 0; count >>= 1) {
        //base+count/2，保证probe始终为middle
        probe = base + (count >> 1);
        uintptr_t probeValue = (uintptr_t)getName(probe);
        //方法编号的对比
        if (keyValue == probeValue) {
            //找到该方法，判断probe的值如果不是开始，并且probe-1得到的方法还是该方法
            //执行probe--，遍历，直到probe为开始或probe-1不是该方法为止
            //目的：由于分类重写，相同的方法可能不止一个，这里要找到相同方法中最靠前的那个
            while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
                probe--;
            }
            return &*probe;
        }
        //该方法编号，大于砍半后的方法编号，往probe的右侧查找
        if (keyValue > probeValue) {
            base = probe + 1;
            count--;
        }
    }
    return nil;
}

查找过程：表中方法编号按升序排列，将表中间位置记录的方法编号与将要查找的方法编号比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果查找的方法编号大于中间位置记录的方法编号，则进一步查找后一子表，否则进一步查找前一子表。重复以上过程，直到找到满足条件的记录，此时查找成功。或直到子表不存在为止，此时查找不成功

2.2 汇编代码

2.2.1 `cache_getImp`

慢速查找流程中，当前类的方法列表中，未找到imp，则会执行父类的快速查找流程，调用cache_getImp，在父类的缓存中查找

cache_getImp由汇编实现，在objc-msg-arm64.s文件中找到代码

    STATIC_ENTRY _cache_getImp
    GetClassFromIsa_p16 p0, 0
    CacheLookup GETIMP, _cache_getImp, LGetImpMissDynamic, LGetImpMissConstant
LGetImpMissDynamic:
    mov    p0, #0
    ret
LGetImpMissConstant:
    mov    p0, p2
    ret
    END_ENTRY _cache_getImp

父类进入快速查找流程，传入的参数略有区别，不会进入__objc_msgSend_uncached流程

2.2.2 `GetClassFromIsa_p16`

.macro GetClassFromIsa_p16 src, needs_auth, auth_address /* note: auth_address is not required if !needs_auth */
.if \needs_auth == 0 // _cache_getImp takes an authed class already
    mov    p16, \src
.else
    // 64-bit packed isa
    ExtractISA p16, \src, \auth_address
.endif
.endmacro

入参：

◦ src：Superclass
◦ needs_auth：0
◦ auth_address：参数缺失

mov p16, \src：将src的值，赋值p16寄存器

◦ p16寄存器：存储类对象

2.2.3 `CacheLookup`

.macro CacheLookup Mode, Function, MissLabelDynamic, MissLabelConstant
  mov x15, x16      // stash the original isa

入参：

◦ Mode：GETIMP
◦ Function：_cache_getImp
◦ MissLabelDynamic：LGetImpMissDynamic
◦ MissLabelConstant：LGetImpMissConstant

mov x15, x16：将x16寄存器的值，赋值给x15寄存器

◦ x15寄存器：存储类对象

在CacheLookup中，未命中缓存，进入LGetImpMissDynamic流程，将#0赋值p0寄存器，相当于返回nil，然后回到lookUpImpOrForward函数中，继续for循环中的代码，进行父类的慢速查找流程

2.2.4 `CacheHit`

.macro CacheHit
.if $0 == NORMAL
    TailCallCachedImp x17, x10, x1, x16    // authenticate and call imp
.elseif $0 == GETIMP
    mov    p0, p17
    cbz    p0, 9f            // don't ptrauth a nil imp
    AuthAndResignAsIMP x0, x10, x1, x16    // authenticate imp and re-sign as IMP
9:    ret                // return IMP

CacheHit：缓存命中流程
查看Mode等于GETIMP的代码流程
mov p0, p17：将imp赋值p0寄存器
cbz p0, 9f：如果imp不存在，进入流程9，执行ret返回0
否则，imp存在，进入AuthAndResignAsIMP流程

AuthAndResignAsIMP

.macro AuthAndResignAsIMP
    // $0 = cached imp, $1 = address of cached imp, $2 = SEL
    eor    $0, $0, $3
.endmacro

eor $0, $0, $3：按位异或，imp = imp ^ cls，相当于解码

在CacheHit中，未命中缓存，进入流程9，执行ret返回0。否则，进入AuthAndResignAsIMP流程，拿到解码后的imp，然后返回

2.3 流程图

总结

流程探索：

核心流程：__objc_msgSend_uncached→MethodTableLookup→_lookUpImpOrForward
lookUpImpOrForward函数，并且不是汇编代码实现，而是C/C++函数
汇编和C/C++的相互调用：

◦ C/C++中调用汇编，在汇编代码中查找时，在方法名称最前面加一个下划线
◦ 汇编中调用C/C++函数，在C/C++代码中查找时，去掉方法名称最前面的一个下划线

慢速查找流程：

判断cls是否已注册

◦ 已注册，继续代码流程
◦ 未注册，在checkIsKnownClass函数中报错

判断cls的实现

◦ 实现类的isa走位和父类链

判断cls的初始化

查找imp

◦ 死循环，符合条件，通过goto或break跳出循环

共享缓存中查找

◦ 由于多线程写入方法，此时可能会找到之前未缓存的方法

当前类中查找

◦ 在当前类的方法列表中查找，使用二分查找法
◦ 找到imp，跳转done流程

判断父类是否存在

◦ 如果父类为空，imp赋值为forward_imp，使用break停止循环，进入动态方法决议流程

在父类中查找imp

动态方法决议

done流程

◦ 找到imp，写入缓存，和cache_t::insert形成闭环

二分查找法：

查找过程：表中方法编号按升序排列，将表中间位置记录的方法编号与将要查找的方法编号比较，如果两者相等，则查找成功；否则利用中间位置记录将表分成前、后两个子表，如果查找的方法编号大于中间位置记录的方法编号，则进一步查找后一子表，否则进一步查找前一子表。重复以上过程，直到找到满足条件的记录，此时查找成功。或直到子表不存在为止，此时查找不成功

cache_getImp：

慢速查找流程中，当前类的方法列表中，未找到imp，则会执行父类的快速查找流程，调用cache_getImp，在父类的缓存中查找
cache_getImp由汇编代码实现
父类进入快速查找流程，传入的参数略有区别，不会进入__objc_msgSend_uncached流程
在CacheLookup中，未命中缓存，进入LGetImpMissDynamic流程，将#0赋值p0寄存器，相当于返回nil，然后回到lookUpImpOrForward函数中，继续for循环中的代码，进行父类的慢速查找流程
在CacheHit中，未命中缓存，进入流程9，执行ret返回0。否则，进入AuthAndResignAsIMP流程，拿到解码后的imp，然后返回

1. 流程探索

1.1 TailCallFunctionPointer

1.2 MethodTableLookup

1.3 _lookUpImpOrForward

2. 慢速查找流程

2.1 C/C++代码

2.1.1 lookUpImpOrForward

2.1.2 realizeAndInitializeIfNeeded_locked

2.1.3 callInitialize

2.1.4 getMethodNoSuper_nolock

2.1.5 search_method_list_inline

2.1.6 findMethodInSortedMethodList