OC 原理探索：方法的慢速查找流程-一一网

前言

OC 原理探索：objc_msgSend 流程中我们对objc_msgSend流程进行了分析，objc_msgSend流程是方法的快速查找流程，我们今天来探索一下方法的慢速查找流程。

准备工作

objc4-818.2 源码

一、汇编缓存找不到

汇编源码回 C++ 源码

我们在 OC 原理探索：objc_msgSend 流程中有说到如果没有缓存命中的话，会调用__objc_msgSend_uncached函数，我们去源码中查找这个函数。

在__objc_msgSend_uncached函数中找到了MethodTableLookup，继续查找。

在当前文件中找到了MethodTableLookup的定义，并在函数中找到了_lookUpImpOrForward，去查找_lookUpImpOrForward函数。

我们全局查找，但并没有找到_lookUpImpOrForward相关的定义，怎么办呢，去掉_去查找lookUpImpOrForward。

成功找到了lookUpImpOrForward函数，也宣布从汇编源码正式回到了C++ 源码。

为什么缓存用汇编

1. 速度快

缓存的目的就是为了提高效率，汇编更快，让当前对象快速的找到缓存，优化方法查找的时间。

2. 动态化

汇编更加动态化，我们调用方法时，参数是未知的，C++/C参数要非常的明确

二、慢速查找流程的准备

先看一下lookUpImpOrForward函数的整体结构：

下面对lookUpImpOrForward中的一些函数调用做解析。

checkIsKnownClass

checkIsKnownClass的关键路径：

检查当前class是否已经注册到缓存表中。

realizeAndInitializeIfNeeded_locked

先看下函数的实现：

这个函数中有两条实现路径，针对路径中的关键函数做一些解析。

1. `realizeClassWithoutSwift`

查找路径：realizeClassMaybeSwiftAndLeaveLocked -> realizeClassMaybeSwiftMaybeRelock -> realizeClassWithoutSwift，对函数中的关键代码做一些说明。

一些rw和ro的操作。

递归查找类和元类，如果没有初始化，进行初始化操作。
做这个的意义是什么呢，因为方法在当前类找不到的话，会去父类查找直至根类。

2. initialize

查找路径：initializeAndLeaveLocked -> initializeAndMaybeRelock -> initializeNonMetaClass -> callInitialize：

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

我们平时也会用的initialize函数，这里找到了调用它的地方。

三、二分查找流程

lookUpImpOrForward中的查找流程，核心就是下面这个for 循环：

下面对函数进行解析。

共享缓存

去共享缓存中查找，防止临时有插入进来的方法。

查找函数 getMethodNoSuper_nolock

点击进入getMethodNoSuper_nolock：

方法列表是个二维的数组，循环遍历数组，在循环中通过search_method_list_inline函数去通过sel查找imp。
查找二分查找方法：search_method_list_inline -> findMethodInSortedMethodList -> findMethodInSortedMethodList，下面进行解析。

二分查找 findMethodInSortedMethodList

我们假设count = 16，开始findMethodInSortedMethodList的源码分析。
probe = base + (count >> 1);
- probe = base + (16 >> 1) -> probe = base + (10000 >> 1) -> probe = base + 8，获取列表中间的位置。
uintptr_t probeValue = (uintptr_t)getName(probe);
- probeValue = 中间位置的值。
if (keyValue == probeValue)，中间位置的值和我们寻找的SEL值是否相等。
如果相等：
- 向前遍历找到第一个category的方法。
- return &*probe;，返回找到的方法。
如果不等：
- if (keyValue > probeValue)，判断SEL值是否大于中间值
- 如果SEL大：
  - base = probe + 1;，base = 8 + 1 = 9。
  - count--;，count = 15 = 1111。
  - count >>= 1，count = 7
- 如果SEL小：
  - count >>= 1，count = count >> 1 = 8。

二分查找算法就解析到这里，接下来就是继续遍历，原理是一样的。如果有同学还是不理解可以用下面的代码进行调试，代码是我仿照上面的源码写的。

可调试二分查找算法


int search(int sel,int *a,int count);

int main(int argc, const char * argv[]) {
    @autoreleasepool {

        int a[16] = {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,16};
        int sel = 12;
        
        int index = search(sel, a, 16);
        NSLog(@"index:%d",index);
    }
    return 0;
}
        
int search(int sel,int *a,int count)
{
    int probe = 0;
    int base = 0;
    for (; count != 0; count >>= 1) {
        
        probe = base + (count >> 1);
        
        if (sel == probe) {
            return probe;
        }
        
        if (sel > probe) {
            base = probe + 1;
            count--;
        }
    }
    return -1;
}
复制代码

四、慢速查找递归流程

上面已经探索了通过getMethodNoSuper_nolock函数获取Method，Method可能找到也可能找不到，接下来针对两种情况继续探索。

成功找到 Method

如果成功找到Method，接下来会通过goto语句跳到下面的done。

在done中的关键方法是log_and_fill_cache，点击进入查看实现。

cache.insert函数！！，将找到的Method插入缓存，返回imp结束查找流程。insert函数回到了 OC 类原理探索：cache 结构分析补充我们最开始探索的地方，成功闭环。

没有找到 Method

如果没有找到Method，接下来会去父类中查找，我们继续下面流程的探索。

通过curClass = curClass->getSuperclass()这句代码，curClass已经成为了父类。
如果父类为nil，imp = forward_imp;，结束for 循环。
如果父类不为nil，调用cache_getImp(curClass, sel)，对父类进行缓存的快速查找，接下来对cache_getImp进行解析。

1. cache_getImp

全局搜索cache_getImp：

我们发现并没有找到cache_getImp的实现，猜测应该是去到了汇编，我们去汇编中查找。

在汇编中成功找到_cache_getImp，在 OC 原理探索：objc_msgSend 流程中我们已经对CacheLookup进行过详细的分析，是进行的快速查找流程，但是在这里有所不同。
缓存没找到的情况下，这里的LGetImpMissDynamic是直接返回了nil，不像上一篇中是调用了__objc_msgSend_uncached函数。