objc_msgSend底层之慢速查找

在上一篇文章中，如果方法在cache中没有查找到imp，那么就会来到_lookUpImpOrForward。全局搜索“_lookUpImpOrForward”并没有找到相关实现。而实际上_lookUpImpOrForward是由C++实现的，因为汇编中调用C++的方法需要在方法名前多加一个下划线，所以全局查找lookUpImpOrForward，便可以在objc-runtime-new.mm的6094～6203行找到定义。

要查找汇编中调用的C++方法，需要去掉方法前的一个下划线，而如果需要查找在C++中调用的汇编代码，需要在方法前添加一个下划线

本文便是通过对lookUpImpOrForward方法进行探究来看OC底层是如果慢速查找的。

lookUpImpOrForward初探

首先对lookUpImpOrForward的实现进行解析。

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
    // 尝试通过cache快速查找到imp
    // 之所以再次在缓存中查找是考虑到有可能其他线程调用了这个方法，导致此时缓存已经有这个方法
    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.
    //
    // TODO: this check is quite costly during process startup.
    // 判断是否已知类，如果不是内部会做一系列操作
    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);
        // 如果查找到匹配的，goto done执行返回
        if (meth) {
            imp = meth->imp;
            goto done;
        }
        // 如果当前类方法列表中没有找到，来到下面的流程
        
        // 将curClass设为父类，判断是否为空
        // 为空则结束循环
        if (slowpath((curClass = curClass->superclass) == nil)) {
            // No implementation found, and method resolver didn't help.
            // Use forwarding.
            // 如果当前父类为nil，说明当前类为根类
            // 设置imp为_objc_msgForward_impcache，结束循环
            imp = forward_imp;
            break;
        }

        // Halt if there is a cycle in the superclass chain.
        // 每循环一次，attempts-1
        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;
        }
        // 如果父类中找到方法，goto done，结束循环
        if (fastpath(imp)) {
            // Found the method in a superclass. Cache it in this class.
            goto done;
        }
    }

    // No implementation found. Try method resolver once.
    // 如果父类中都没有找方法，去到动态方法决议
    // behavior & LOOKUP_RESOLVER是为了判断这个流程来过一次动态方法决议
    // 动态方法决议只来一次
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        // behavior ^= LOOKUP_RESOLVER后behavior & LOOKUP_RESOLVER便为false，保证这里只来一次
        behavior ^= LOOKUP_RESOLVER;
        // 去到动态方法决议
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

// 这里是方法找到的流程
 done:
    //打印log并将方法缓存在cache中，方便下次调用可以通过快速查找找到
    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;
}

可以看到lookUpImpOrForward有以下步骤

**1. 先在cache中再查找一次，避免出现多线程调用cache此时添加了方法的情况

2. 查看当前类是否已经为已知类、是否实现、是否初始化，如果没有会对类进行一些处理
3. 开启一个循环，在当前类的方法列表中查找方法
4. 如果找到将方法缓存在cache中，返回imp
5. 没有在当前类中没有找到，会通过superclass指针找到父类
6. 首先会在父类的缓存中查找，如果父类中没有，那么在下次循环中再来到父类的方法列表中查找，重复4、5的流程，直到找到根类为止
7. 父类中查找也会经过快速查找->慢速查找的过程，也就是汇编再到C++的过程，如果父类中找到了方法，方法
8. 如果一直到根类都没有找到该方法，那么就会来到动态方法决议，动态方法决议只走一次**

getMethodNoSuper_nolock方法查找过程

查看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;
}

跟进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->entsize() == sizeof(method_t);
    
    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方法，如果是未经过排序，那么会通过一般遍历查找。

查看findMethodInSortedMethodList，可以明显看到这是一个二分查找的过程

ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
    ASSERT(list);
    // 拿到方法列表首元素
    const method_t * const first = &list->first;
    const method_t *base = first;
    // 二分查找的较小值
    const method_t *probe;
    // 目标值
    uintptr_t keyValue = (uintptr_t)key;
    uint32_t count;
    
    // 循环查找
    // 首先从第一个元素开始 
    // 每次减少一半（>>1,逻辑右移，相当于/2，比如，5，二进制0x0101，右移为0b0010, 结果为2）
    for (count = list->count; count != 0; count >>= 1) {
        // base+count的一半，probe是较小值base和较大值的中间值
        probe = base + (count >> 1);
        // 到probe的sel
        uintptr_t probeValue = (uintptr_t)probe->name;
        // 比较当前中间的方法sel与目标sel是否一致
        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 (method_t *)probe;
        }
        // 如果目标的sel大于中间的sel，说明方法在probe的右边，所以将较小值base移至probe+1的位置，因为base往前了一个单位，所以count-1，下次循环是>>1才会定位到中间位置
        // 如果目标sel小于，下次的较小值仍然为原来的值，count在下次循环是会变为原来的1/2，所以probe下次循环时会加上上次循环时count的1/4，从而定位到中间的位置
        if (keyValue > probeValue) {
            base = probe + 1;
            count--;
        }
    }
    
    return nil;
}

也就是

**1. 如果方法列表没有经过排序，会通过一般遍历查找方法

2. 如果方法列表已经排序过了，会通过二分法查找方法**

总结

大致流程可以用下图概括：

慢速查找.png