9、方法的调用原理（2）

好消息，先前电脑升级成Big Sur，导致新系统下源码调试有问题，现在Big Sur又更新版本了，已经可以配置源码调试了，这篇文章后将用新的环境来研究。

2.方法调用的流程

2.2——methods查找(慢速查找)

鉴于研究慢速查找，因此对源码修改一下：

@interface Person : NSObject
@property (nonatomic,assign)   int age;
@property (nonatomic,strong)   NSString *nickname;
@property (nonatomic,assign)   float height;
@property (nonatomic,strong)   NSString *name;

-(void)laugh;
-(void)cry;
-(void)run;
-(void)jump;
-(void)doNothing;
@end

@implementation Person
-(void)laugh
{
    NSLog(@"LMAO");
}

-(void)cry
{
    NSLog(@"cry me a river");
}

-(void)run
{
    NSLog(@"run! Forrest run!");
}

-(void)jump
{
    NSLog(@"you jump,I jump!");
}

-(void)doNothing
{
    NSLog(@"Today,I dont wanna do anything~");
}


//-(void)talkShow
//{
//    NSLog(@"roast king!");
//}


@end

@interface Saler : Person

@property (nonatomic,strong)   NSString *brand;


-(void)talkShow;

+(void)sayGiao;

@end

@implementation Saler

//-(void)talkShow
//{
//    NSLog(@"roast king!");
//}


//+(void)sayGiao
//{
//    NSLog(@"one geli my giao!");
//}
@end

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        //main方法中
        Saler *person =  [Saler alloc];
        
        person.age = 10;
        person.nickname = @"pp";
        person.height = 180.0;
        person.name = @"ppext";
        person.brand = @"apple";

        Saler *saler = [Saler alloc];
        saler.age = 28;
        saler.nickname = @"xx";
        saler.height = 175.0;
        saler.name = @"xxext";
        saler.brand = @"apple";
//实例方法
//        [saler talkShow];
//类方法
        [Saler sayGiao];   
    }
    return 0;
}

书接上文，8、方法调用原理（1）中在cache的查找流程完成后，会调用lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)，下面就对这个方法进行全局搜索，研究一下流程：

IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    IMP imp = nil;
    Class curClass;

    runtimeLock.assertUnlocked();

    // Optimistic cache lookup
    if (fastpath(behavior & LOOKUP_CACHE)) {
        imp = cache_getImp(cls, sel);
        if (imp) goto done_nolock;
    }

    // runtimeLock is held during isRealized and isInitialized checking
    // to prevent races against concurrent realization.

    // runtimeLock is held during method search to make
    // method-lookup + cache-fill atomic with respect to method addition.
    // Otherwise, a category could be added but ignored indefinitely because
    // the cache was re-filled with the old value after the cache flush on
    // behalf of the category.

    runtimeLock.lock();

    // We don't want people to be able to craft a binary blob that looks like
    // a class but really isn't one and do a CFI attack.
    //
    // To make these harder we want to make sure this is a class that was
    // either built into the binary or legitimately registered through
    // objc_duplicateClass, objc_initializeClassPair or objc_allocateClassPair.
    checkIsKnownClass(cls);

    if (slowpath(!cls->isRealized())) {
        cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
        // runtimeLock may have been dropped but is now locked again
    }

    if (slowpath((behavior & LOOKUP_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
    }

    runtimeLock.assertLocked();
    curClass = cls;

    // The code used to lookpu the class's cache again right after
    // we take the lock but for the vast majority of the cases
    // evidence shows this is a miss most of the time, hence a time loss.
    //
    // The only codepath calling into this without having performed some
    // kind of cache lookup is class_getInstanceMethod().

    for (unsigned attempts = unreasonableClassCount();;) {
        // curClass method list.
        Method meth = getMethodNoSuper_nolock(curClass, sel);
        if (meth) {
            imp = meth->imp(false);
            goto done;
        }

        if (slowpath((curClass = curClass->superclass) == nil)) {
            // No implementation found, and method resolver didn't help.
            // Use forwarding.
            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.");
        }

        // Superclass cache.
        imp = cache_getImp(curClass, sel);
        if (slowpath(imp == forward_imp)) {
            // Found a forward:: entry in a superclass.
            // Stop searching, but don't cache yet; call method
            // resolver for this class first.
            break;
        }
        if (fastpath(imp)) {
            // Found the method in a superclass. Cache it in this class.
            goto done;
        }
    }

    // No implementation found. Try method resolver once.

    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

 done:
    log_and_fill_cache(cls, imp, sel, inst, curClass);
    runtimeLock.unlock();
 done_nolock:
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
    return imp;
}

根据上文对MethodTableLookup源码注释分析知道是这种参数传递调用lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)，与大多数objc-4 781.1源码类似，这里也分slowpath和fastpath分支：
第一个分支fastpath(behavior & LOOKUP_CACHE)是判断是否是在查找cache中的buckets进入的的lookUpImpOrForward方法，而且大概率是的，就直接调用cache_getImp方法，可以参考8、方法的调用原理（1）中objc_MsgSend()的流程，正常的快速查找流程。
第二个分支slowpath(!cls->isRealized())，显而易见确认类是否是实现的，而且大概率是实现了的，没实现的话，会先进行类的实现再走下一步骤，且类的实现分两种，一种是非Swift类型的，另一种是Swift类型。
第三个分支slowpath((behavior & LOOKUP_INITIALIZE) && !cls->isInitialized())，确认behavior是否是查询类的初始化且类是否已经初始化了，大概率是已经初始化了的，没有的话就对类进行初始化。
第四个分支for (unsigned attempts = unreasonableClassCount();;)固定数目循环，unreasonableClassCount循环次数多少是根据继承链而定，结合4、isa与对象、类的关系的isa走位图分析如果是实例方法： 实例——类——父类——NSObject，如果是类方法：类——元类——根元类——NSObject，断点调试发现会循环制NSObject的父类，也就是nil然后就跳出循环了。
第四——一个分支Method meth = getMethodNoSuper_nolock(curClass, sel)方法列表中二分法搜寻方法，不搜寻父类的，搜到则跳转至done代码块。
第四——二个分支slowpath((curClass = curClass->superclass) == nil)判断父类是否存在，存在概率很大，并将curClass变成父类，没有父类就将进入imp = forward_imp,也就是消息转发流程。
第四——三个分支slowpath(--attempts == 0)判断循环次数是否是0，大概率不为0，如果为0就是内存中类列表被污染，报错。
第四——四个分支slowpath(imp == forward_imp)，在这个之前imp = cache_getImp(curClass, sel)先搜索当前类的缓存是否有这个方法，这里的当前类可能是已经转化为父类了curClass = curClass->superclass；然后就是判断是否走消息转发流程，是的话直接跳出循环，大概率不是转发流程。
第四——五个分支fastpath(imp)判断imp是否找到，大概率找到，找到就会走done代码块。
第五个分支slowpath(behavior & LOOKUP_RESOLVER)，判断当前代码流程行为是否是LOOKUP_RESOLVER，大概率不是，就会走if的代码块，进入resolveMethod_locked对方法进行决议，意味着类以及父类中都没发现该方法，resolveMethod_locked主要是：

static NEVER_INLINE IMP
resolveMethod_locked(id inst, SEL sel, Class cls, int behavior)
{
    runtimeLock.assertLocked();
    ASSERT(cls->isRealized());

    runtimeLock.unlock();

    if (! cls->isMetaClass()) {
        // try [cls resolveInstanceMethod:sel]
        resolveInstanceMethod(inst, sel, cls);
    } 
    else {
        // try [nonMetaClass resolveClassMethod:sel]
        // and [cls resolveInstanceMethod:sel]
        resolveClassMethod(inst, sel, cls);
        if (!lookUpImpOrNil(inst, sel, cls)) {
            resolveInstanceMethod(inst, sel, cls);
        }
    }

    // chances are that calling the resolver have populated the cache
    // so attempt using it
    return lookUpImpOrForward(inst, sel, cls, behavior | LOOKUP_CACHE);
}

判断是实例方法还是类方法，来发送决议方法消息，并进入lookUpImpOrForward查找决议方法的IMP，流程和之前分析lookUpImpOrForward类似，只不过换做是寻找resolveInstanceMethod或者resolveClassMethod，resolveClassMethod也就是类的InsatanceMethod，在NSObject中必然找到这个方法所以必然是找的到的。

最后：
done: log_and_fill_cache记录并插入cache
done_nolock：slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)
判断是否当前流程行为是否是LOOKUP_NIL且imp == forward_imp，大概率不是，如果不是将返回nil。
return：返回imp。
到看到forward和resolve的方法就可以基本知道，慢速查找基本完成。因为这两个方法将消息发送重新定向了这里两个消息的发送。

如果对这里的分析中的大概率、小概率有所疑问，请参考查漏补缺。

2.3——慢速查找补充分析

2.3.1 getMethodNoSuper_nolock方法

在类信息查找Method对应的就是在getMethodNoSuper_nolock方法中：

static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
    runtimeLock.assertLocked();

    ASSERT(cls->isRealized());
    // fixme nil cls? 
    // fixme nil sel?

    auto const methods = cls->data()->methods();
    for (auto mlists = methods.beginLists(),
              end = methods.endLists();
         mlists != end;
         ++mlists)
    {
        // <rdar://problem/46904873> getMethodNoSuper_nolock is the hottest
        // caller of search_method_list, inlining it turns
        // getMethodNoSuper_nolock into a frame-less function and eliminates
        // any store from this codepath.
        method_t *m = search_method_list_inline(*mlists, sel);
        if (m) return m;
    }

    return nil;
}

与之前文章6、类结构分析分析lldb打印对应，通过data来获得methods，通过search_method_list_inline方法类定位对应要找的method_t，再就是对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 {
        // Linear search of unsorted method list
        for (auto& meth : *mlist) {
            if (meth.name() == sel) return &meth;
        }
    }

#if DEBUG
    // sanity-check negative results
    if (mlist->isFixedUp()) {
        for (auto& meth : *mlist) {
            if (meth.name() == sel) {
                _objc_fatal("linear search worked when binary search did not");
            }
        }
    }
#endif

    return nil;
}

到这步，在类信息中搜索方法的流程就基本上清楚，这个方法内还有一个findMethodInSortedMethodList方法是具体的查找算法，也分析一下：

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

    auto first = list->begin();
    auto base = first;
    decltype(first) probe;

    uintptr_t keyValue = (uintptr_t)key;
    uint32_t count;
    
    for (count = list->count; count != 0; count >>= 1) {
        probe = base + (count >> 1);
        
        uintptr_t probeValue = (uintptr_t)probe->name();
        
        if (keyValue == probeValue) {
            // `probe` is a match.
            // Rewind looking for the *first* occurrence of this value.
            // This is required for correct category overrides.
            while (probe > first && keyValue == (uintptr_t)(probe - 1)->name()) {
                probe--;
            }
            return &*probe;
        }
        
        if (keyValue > probeValue) {
            base = probe + 1;
            count--;
        }
    }
    
    return nil;
}

主要在for循环内，是逆序的循环，而且每次count >>= 1，右移一位，这个跨度是多大，在二进制中相当于1/2，特点很明显二分法查找。
当查找到keyValue == probeValue时，下面while循环是为了找到比当前的probe更靠前的位置是否还存在这个方法名，注释的解释是需要正确的分类重载，那大概可以猜测的时分类方法重载时，是会将分类方法插在原有方法之前的位置。
找到后就会返回probe这个method_t。

2.3.2 imp = cache_getImp(curClass, sel)方法

在lookUpImpOrForward方法中的流程还没有完全分析完成，比较重要的漏掉的，在getMethodNoSuper_nolock之后有imp = cache_getImp(curClass, sel);方法，注释就是父类的Cache，也就是自身的方法列表没找到，先在父类的cache中查找，这里其实流程和之前文章8、方法的调用原理（1）中的_objc_msgSend方法中的：CacheLookup NORMAL, _objc_msgSend方法的调用类似，这里调用的是CacheLookup GETIMP, _cache_getImp，对照_objc_msgSend的参数调用的是person这个对象，获取的是这个对象的isa。_cache_getImp传入的参数是curClass，获取的是这个类的isa，以为处在for的死循环中，curClass是按照实例——类——父类——NSObject或者类——元类——根元类——NSObject的变化来的，会循环按这个继承链查找，所以这里会查询父类或者元类的cache混存中是否存在对应的方法。

2.4——methods查找(慢速查找）总结

慢速查找流程图 这个就是慢速查找基本流程（也是借鉴了大神的图-。-）。
这里分析要注意：
1、for循环那一段代码块和消息决议resolveMethod_locked已经涉及了嵌套的调用lookUpImpOrForward方法，需要开启Debug——>Debug Workflow——>Always Show Disassembly来断点调试。（lookUpImpOrForward为什么写的这么凌乱，因为它是一个无限月渎的方法-。-）
2、测试的类和方法，要适当不实现，让流程走向方法无法查找到的情况，就如源码注销的部分代码。
3、整个流程是分代码块分析拼凑形成，最早的分析流程可能很凌乱，但是主要线路是两条：一条是找到imp，一条是找不到imp。
4、慢速查找流程没查找到会走向resolveMethod_locked或者forward。
5、消息决议方法也会走消息发送流程，即resolveInstanceMethod也会走objc_msgSend的流程。