前言

IOS底层原理之Runimte 运行时&方法的本质 中探究了方法的快速查找流程既缓存查找，如果缓存中没有查找到，下面就会进入方法慢速查找流程。在这阳光明媚的夏天探究下方法慢速查找流程

准备工作

• 冰镇 ?
• objc4-818.2 源码

objc_msgSend_uncached

在当前类中，缓存查找流程中如果没有到查找目标方法，跳转MissLabelDynamic流程
MissLabelDynamic = __objc_msgSend_uncached，搜索__objc_msgSend_uncached并找到入口，真机汇编代码如下

    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 x17，现在不知道x17是什么，那么看TailCallFunctionPointer中x17做了什么，全局搜索TailCallFunctionPointer代码如下

    // A12 以上 iPhone X 以上的
    #if __has_feature(ptrauth_calls)
    ...
    #else
    ...
    .macro TailCallFunctionPointer
            // $0 = function pointer value
            br	$0
    .endmacro
    ...
    #endif
复制代码

TailCallFunctionPointer就一行汇编代码br $0.因为$0 = p17，br $0的意思读取p17寄存器中的地址并且跳转到该地址，因为我们是在查询方法就是根据找sel找imp，在根据TailCallFunctionPointer提示。猜测p17寄存器应该存的是imp

p17寄存器在__objc_msgSend_uncached没有赋值的地方，那么只能在MethodTableLookup赋值。代码如下

.macro MethodTableLookup
	
    SAVE_REGS MSGSEND

    // lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
    // receiver and selector already in x0 and x1
    // x16 = class 赋值给x2
    mov	x2, x16   
    // 3 赋值给 x3
    mov	x3, #3               
    // bl：b：跳转 l：链接寄存器 //在跳转到之前_lookUpImpOrForward之前，
    // 将下一条指令的地址保存到lr寄存器中，既将(mov x17, x0)的指令地址保存在lr中
    // 当_lookUpImpOrForwar执行完以后，执行lr寄存器中的地址
    bl	_lookUpImpOrForward   

    // x0 第一个参数的值保存在x0，方法的返回值也保存在x0在这应该是_lookUpImpOrForward 的返回值imp
    // x0 赋值给 x17
    mov	x17, x0  

    RESTORE_REGS MSGSEND

.endmacro
复制代码

通过_lookUpImpOrForward查询到imp，将imp赋值给x17寄存器，全局搜索_lookUpImpOrForward，发现汇编里面没有_lookUpImpOrForward的定义或者实现，全局搜索lookUpImpOrForward

lookUpImpOrForward的返回值是imp，疑问：为什么lookUpImpOrForward实现使用汇编呢？

• 汇编更接近机器语言，查询速度更快。缓存查找流程是快速在缓存中找到方法，而慢速查找流程是不断的遍历methodlist过程，这个过程很慢
• 方法中有的参数是不确定的，但是在C语言中参数必须是确定的，而汇编可以让你感觉更加的动态化

objc_msgSend_uncached总结

• 通过MethodTableLookup查询将查询到imp作为返回值存在x0寄存器，将x0寄存器的值赋值给x17寄存器
• 通过 TailCallFunctionPointer x17直接调用x17寄存器中的imp
• __objc_msgSend_uncached–> MethodTableLookup–> _lookUpImpOrForward –>TailCallFunctionPointer

lookUpImpOrForward

lookUpImpOrForward根据sel查询imp，具体是怎么查询imp下面探究下

IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    //定义消息转发forward_imp  //behavior传入的是 3  = LOOKUP_INITIALIZE|LOOKUP_RESOLVER
    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    IMP imp = nil;
    Class curClass;

    runtimeLock.assertUnlocked();
    
    /*
    //判断类是否初始化 没有初始化 behavior = LOOKUP_NOCACHE|LOOKUP_INITIALIZE|LOOKUP_RESOLVER  
    //发送给类的第一条消息通常是+new或+alloc或+self会初始化类
    */
    if (slowpath(!cls->isInitialized())) {
        behavior |= LOOKUP_NOCACHE;
    }

    //加锁防止多线程访问出现错乱
    runtimeLock.lock();

    checkIsKnownClass(cls); //是否注册类 是否被dyld加载的类
    //实现类包括实现isa走位中的父类和元类 //初始化类和父类
    cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
     
    runtimeLock.assertLocked();
    
    curClass = cls;

    //获取锁后，代码再次查找类的缓存，但绝大多数情况下，证据表明大部分时间都未命中，因此浪费时间。
    //唯一没有执行某种缓存查找的代码路径就是class_getInstanceMethod()。
    // unreasonableClassCount 类迭代上限 根据翻译来的
    for (unsigned attempts = unreasonableClassCount();;) {
        //判断是否有共享缓存缓存优化，一般是系统的方法比如NSLog，一般的方法不会走
        if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
            #if CONFIG_USE_PREOPT_CACHES
            /*
            再一次查询共享缓存，目的可能在你查询过程中
            别的线程可能调用了这个方法共享缓存中有了直接去查询
            */
            imp = cache_getImp(curClass, sel);//缓存中根据sel查询imp
            //如果imp存在即缓存中有 跳转到done_unlock流程
            if (imp) goto done_unlock;        
            //具体干啥不知道我感觉是获取父类的里面是进行的偏移
            curClass = curClass->cache.preoptFallbackClass();
            #endif
        }
        else {
            // curClass method list.
            // 在curClass类中采用二分查找算法查找methodlist
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {                // 如果找到了sel对应的方法
                imp = meth->imp(false);//获取对应的imp
                goto done;             //跳转到 done 流程
            }
             // curClass = curClass->getSuperclass() 直到为nil走if里面的流程，不为nil走下面流程
            if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
                //就是在循环里面没有找到对应的sel的方法，把定义息转发forward_imp赋值给imp
                imp = forward_imp; 
                break;
            }
        }

        // Halt if there is a cycle in the superclass chain.
        if (slowpath(--attempts == 0)) { // 如果父类中存在循环则停止
            _objc_fatal("Memory corruption in class list.");
        }

        // 去父类的缓存中查找imp
        imp = cache_getImp(curClass, sel);
        if (slowpath(imp == forward_imp)) {
            //如果父类返回的是forward_imp 停止查找，那么就跳出循环
            break;
        }
        if (fastpath(imp)) {
            //如果缓存中有就跳转done流程
            goto done;
        }
    }

    // No implementation found. Try method resolver once.
    // 如果查询方法的没有实现，系统会尝试一次方法解析
    // behavior = 3 LOOKUP_RESOLVER = 2
    // behavior & LOOKUP_RESOLVER = 3 & 2 = 2 所以成立进入条件
    // 再次进入behavior = 1 & 2 = 0 不会在进入条件里面只执行一次动态方法决议 
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        //behavior = behavior ^ LOOKUP_RESOLVER = 3 ^ 2 = 1
        behavior ^= LOOKUP_RESOLVER; 
        //动态方法决议
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

 done:
    //(behavior & LOOKUP_NOCACHE) == 0 成立  behavior = 3
    //LOOKUP_NOCACHE = 8 所以(behavior & LOOKUP_NOCACHE) = 0
    if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) {
#if CONFIG_USE_PREOPT_CACHES
        while (cls->cache.isConstantOptimizedCache(/* strict */true)) {
            cls = cls->cache.preoptFallbackClass();
        }
#endif
        //将查询到的sel和imp插入到缓存 注意：插入的是当前类的缓存
        log_and_fill_cache(cls, imp, sel, inst, curClass);
    }
 done_unlock:
    //解锁
    runtimeLock.unlock();
    /*
    如果 (behavior & LOOKUP_NIL)成立则 behavior ！= LOOKUP_NIL
    且imp == forward_imp 没有查询到直接返回 nil
    */
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
    return imp;
}
复制代码

慢速查找流程

• 是否注册类，如果没有直接报错
• 是否实现cls，如果没有实现，则先去实现类以及相关的isa走位链和isa继承链中类的实现，目的是方法查找时到父类中去查询
• 类是否初始化，如果没有则初始化，这一步我觉着是创建类对象比如调用类方法时，就是类对象调用实例方法

cls开始遍历查询

• 判断是否有共享缓存，目的是有可能在查过过程中这个方法被调用缓存了，如果有的话直接从缓存中取，没有共享缓存则开始到本类中查询
• 在类中采用二分查找算法查找methodlist中的方法，如果找到插入缓存中，循环结束

父类缓存中查询

• 如果父类中存在循环则终止查询，跳出循环
• 此时curClass = superclass，到父类的缓存中找，如果找到则插入到本类的缓存中。如果父类中返回的是forward_imp则跳出遍历，执行消息转发
• 如果本类中没有找到此时的curClass = superclass进入和cls类相同的查找流程进行遍历循环，直到 curClass = nil，imp = forward_imp进行消息转发

动态方法决议

• 如果cls以及父类都没有查询到，此时系统会给你一次机会，判断是否执行过动态方法决议，如果没有则走动态方法决议，已经执行过了则进行消息转发

lookUpImpOrForward 流程图

实现和实例化类

static Class
realizeAndInitializeIfNeeded_locked(id inst, Class cls, bool initialize)
{
    runtimeLock.assertLocked();
    // !cls->isRealized()小概率发生 cls->isRealized()大概率是YES
    //判断类是否实现 目的是实现isa走位图中的isa走位链和父类链
    if (slowpath(!cls->isRealized())) {
        cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
        // runtimeLock may have been dropped but is now locked again
    }
    // 类是否初始化 没有先去初始化
    if (slowpath(initialize && !cls->isInitialized())) {
        cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
        // runtimeLock may have been dropped but is now locked again

        // If sel == initialize, class_initialize will send +initialize and
        // then the messenger will send +initialize again after this
        // procedure finishes. Of course, if this is not being called
        // from the messenger then it won't happen. 2778172
    }
    return cls;
    realizeClassWithoutSwift
}

复制代码

• realizeClassMaybeSwiftAndLeaveLocked方法中的realizeClassWithoutSwift就是去实现类的isa走位链和继承链中相关的类
• initializeAndMaybeRelock的initializeNonMetaClass就是初始化类和父类的

二分法查找算法

ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)
{
    ASSERT(list);

    auto first = list->begin();  //第一个method的位置
    auto base = first;
    decltype(first) probe;       //相当于mid
    //把key直接转换成uintptr_t 因为修复过后的method_list_t中的元素是排过序的
    uintptr_t keyValue = (uintptr_t)key;
    uint32_t count;
    //count = 数组的个数 （count >>= 1 = count = count >> 1）
    //count >> 1 就相当于（count/2) 取整
    //1.假如 count = list->count = 8   //2 count =  7 >> 1 = 3
    for (count = list->count; count != 0; count >>= 1) {
        /*
          1. 首地址 + (下标) //地址偏移 中间值 probe = base + 4
          2. 中间值  probe = base（首地址）+ 6
         */
        probe = base + (count >> 1);
        
        //获取中间的sel的值也是强转后的值
        uintptr_t probeValue = (uintptr_t)getName(probe);
        if (keyValue == probeValue) {// 如果 目标key ==  中间位置的key 匹配成功
            //分类覆盖，分类中有相同名字的方法，如果有分类的方法我们就获取分类的方法，多个分类看编译的顺序
            while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
                probe--;
            }
            //返回方法的地址
            return &*probe;
        }
        //如果 keyValue > 中间的位置的值
        if (keyValue > probeValue) {
            /*
               1.base = probe + 1 =  4 + 1 = base（首地址） + 5 向上移 一位
               2.base = probe + 1 ;向上移 一位
             */
            base = probe + 1;
            // 8 -1 = 7 因为比过一次没中 然后循环
            count--;
        }
    }
    
    return nil;//查询完没找到返回nil
}
复制代码

方法列表中的方法是经过修复的，意思就是按照sel大小进行过排序的

• 二分法查找算法其实就是每次找到范围内的中间位置和keyValue比较，如果相等直接返回查找到的方法（当然如果有分类方法就返回分类方法）
• 如果不相等则继续二分法查询，不断缩小查询的范围，如果最后还是没有查询到则返回nil

二分法查找案例

注意：keyValue 大于 probeValue算法和keyValue 小于 probeValue，count的利用有点点区别，可以细细体会count的设计，小于的算法 count是作为上边界，大于的算法，count的设计就很巧妙，不在作为上边界，主要看probe就可以了

cache_getImp

方法快速查找流程是汇编源码实现的

STATIC_ENTRY _cache_getImp

GetClassFromIsa_p16 p0, 0
CacheLookup GETIMP, _cache_getImp, LGetImpMissDynamic, LGetImpMissConstant

LGetImpMissDynamic:
	mov	p0, #0
	ret
复制代码

GetClassFromIsa_p16宏定义和我们开始在本类中查询缓存方法一样，但是参数不一样 needs_auth = 0

.macro GetClassFromIsa_p16 src, needs_auth, auth_address 
/* note: auth_address is not required if !needs_auth */

#if SUPPORT_INDEXED_ISA  // armv7k or arm64_32
	...//省略
1:

#elif __LP64__
.if \needs_auth == 0 // _cache_getImp takes an authed class already
	mov	p16, \src
.else //needs_auth = 1 所以走下面的流程
	// 64-bit packed isa
        //把 \src 和 \auth_address 传进ExtractISA 得到的结果赋值给p16寄存器
	ExtractISA p16, \src, \auth_address  
.endif
#else
	// 32-bit raw isa
	mov	p16, \src

#endif
复制代码

直接走needs_auth==0，p0=curClass。把p0寄存器的值赋值给p16寄存器，p16= curClass

CacheLookup方法前面已经探究过了在这不细说了CacheLookup GETIMP, _cache_getImp, LGetImpMissDynamic, LGetImpMissConstant

• 如果缓存没有命中走 LGetImpMissDynamic流程
• 如果缓存命中 Mode = GETIMP

LGetImpMissDynamic:
	mov	p0, #0
	ret
复制代码

LGetImpMissDynamic流程 p0 = 0，就是没有查到缓存就是返回imp = nil

.macro CacheHit
.if $0 == NORMAL
	TailCallCachedImp x17, x10, x1, x16	// authenticate and call imp
.elseif $0 == GETIMP
	mov	p0, p17
	cbz	p0, 9f	 //如果imp = 0直接跳转9流程 return 0	 
	AuthAndResignAsIMP x0, x10, x1, x16	// authenticate imp and re-sign as IMP
9:	ret

复制代码

• p17 = imp，把p17寄存器的值赋值给p0寄存器，x0 = p0 = imp
• 如果imp=0直接跳转9流程 return 0
• AuthAndResignAsIMP也是一个宏，对imp进行解码，拿到解码后的imp返回

.macro AuthAndResignAsIMP
	// $0 = cache imp  , $1 = buckets的地址, $2 = SEL  $3 = class
        // $0 = $0 ^ $3 = imp ^ class = 解码后的imp  
	eor	$0, $0, $3
.endmacro
复制代码

缓存中获取imp是编码过的，此时imp ^ class = 解码后的imp

实例查找

创建一个LWPerson类，声明一个sayHello方法，不实现

int main(int argc, char * argv[]) {
 
    @autoreleasepool {
        LWPerson * perosn  = [LWPerson alloc];
        [perosn sayHello];
 
    }
    return 0;
}
复制代码

unrecognized经典的崩溃信息，[perosn sayHello]也走了快速查找流程，慢速查找流程，动态方法决议，最后消息转发，最后还是没找到报unrecognized，全局搜索doesNotRecognizeSelector或者unrecognized selector sent to instance，在源码中搜索

// Replaced by CF (throws an NSException)
+ (void)doesNotRecognizeSelector:(SEL)sel {
    _objc_fatal("+[%s %s]: unrecognized selector sent to instance %p", 
                class_getName(self), sel_getName(sel), self);
}

// Replaced by CF (throws an NSException)
- (void)doesNotRecognizeSelector:(SEL)sel {
    _objc_fatal("-[%s %s]: unrecognized selector sent to instance %p", 
                object_getClassName(self), sel_getName(sel), self);
}

__attribute__((noreturn, cold)) 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);
}
复制代码

最后怎么调用doesNotRecognizeSelector后面在消息转发阶段会做详细的说明

下面创建有个NSObject+LW分类里面添加一个对象方法testData，并且只在分类中实现，LWPerson类中声明这个方法

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        [LWPerson performSelector:@selector(testData) withObject:nil];
    }
    return 0;
}
复制代码

2021-06-30 19:56:36.949645+0800 KCObjcBuild[1439:30359] NSObject
复制代码

类调用对象方法调用成功了原因是什么，在oc底层没有所谓的实例方法和类方法，获取一个类方法实际上就是获取元类的实例方法，没找到找到根源类，根源类也没有，最后找到NSObject所以可以找到testData方法

总结

方法的查找流程实际是个很复杂的流程。现在探讨了方法快速查找流程和快速查找流程，后面还有动态方法决议，以及消息转发流程