iOS 底层探究：方法的慢速查找-一一网

这是我参与8月更文挑战的第11天，活动详情查看：8月更文挑战

我们在之前的文章中介绍了方法的快速查找流程即缓存查找，如果缓存中没有查找到，下面就会进入到方法的慢速查找流程。
消息快速查找流程中，如果无法命中缓存，进入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(""); 
}
复制代码

中的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 流程图

文章版权归作者所有，未经允许请勿转载。

THE END

IOS

canvas 300行代码实现一个贪吃蛇

spring boot设置全局变量到前端Thymeleaf模板上

CKEditor Preview插件跨站脚本漏洞

ProjectPier ‘upload.php’任意文件上传漏洞

表白语录v3.1去广告版一键生成表白文章

Vue2源码之渲染原理和异步更新(二)

iOS 底层探究：方法的慢速查找

这是我参与8月更文挑战的第11天，活动详情查看：8月更文挑战

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

2.1.7 二分查找法

2.2 汇编代码

2.2.1 cache_getImp

2.2.2 GetClassFromIsa_p16

2.2.3 CacheLookup

2.2.4 CacheHit

2.3 流程图

canvas 300行代码实现一个贪吃蛇

spring boot设置全局变量到前端Thymeleaf模板上

CKEditor Preview插件跨站脚本漏洞

ProjectPier ‘upload.php’任意文件上传漏洞

表白语录v3.1去广告版 一键生成表白文章

Vue2源码之渲染原理和异步更新(二)

iOS 底层探究：方法的慢速查找

这是我参与8月更文挑战的第11天，活动详情查看：8月更文挑战

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

2.1.7 二分查找法

2.2 汇编代码

2.2.1 cache_getImp

2.2.2 GetClassFromIsa_p16

2.2.3 CacheLookup

2.2.4 CacheHit

2.3 流程图

表白语录v3.1去广告版一键生成表白文章

2.1 `C/C++`代码