iOS底层探索--方法慢速查找

前言

  在 iOS底层探索--方法快速查找(汇编)流程&慢速查找初探 这一篇章我们研究了方法的快速查找流程，以及慢速方法查找初探：如果在 cache 找不到 imp ，就会调用 MissLabelDynamic 参数，实际调用了 _objc_msgSend_uncached 方法，然后再该方法中调用MethodTableLookup函数，在 MethodTableLookup 中调用了_lookUpImpOrForward 函数，我们研究过程就成功的从汇编到了C/C++慢速查找过程。

转换过程

源码中查找lookUpImpOrForward

  在源码中查找一下lookUpImpOrForward方法调用及查找流程发现有几个地方调用了lookUpImpOrForward，分别是：

1. 在获取类的class_getClassMethod和类的实例方法class_getInstanceMethod时，即调用runtime API获取类方法和实例方法时
2. _lookUpImpTryCache处调用

lookUpImpOrForward调用

lookUpImpOrForward流程

1. checkIsKnownClass(cls) 检测类是否是合法注册的类
2. realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE)如果尚未实现，则实现给定的类;如果尚未初始化，则初始化该类（这部分个人认为对于懒加载类，需要时才加载，根据类内存，绑定ro，rw，rwe，superclass，isa，categories，protocols，对方法根据地址进行排序等操作）
3. for死循环递归查找
   • 1. getMethodNoSuper_nolock(curClass, sel)查找Method
     2. 找到就log_and_fill_cache(cls, imp, sel, inst, curClass);
     3. 找不到，则获取父类 curClass->getSuperclass()
     4. 在superclass的cache中查找 imp = cache_getImp(curClass, sel)，此时进入汇编快速查找流程，如果找到则同步本类的cache
        • _cache_getImp
        • CacheLookup方法
     5. 继续循环1、2、3、4直到curClass == nil结束循环
4. 循环递归找不到方法，则imp = _objc_msgForward_impcachebreak跳出循环，并尝试进行方法解析resolveMethod_locked (inst , sel , cls , behavior)，保证只进行解析一次（如何做到的呢？）
   • behavior = 3 ,LOOKUP_RESOLVER = 2 if (slowpath(behavior & LOOKUP_RESOLVER)){ behavior ^= LOOKUP_RESOLVER}
     1. 第一次来 3 & 2 = 2 ，条件成了，进入 然后 behavior = 3 ^ 2 = 1
     2. 第二次来 1 & 2 = 0 ，条件不成立，不进入
        • 非元类 !cls->isMetaClass()
          • resolveInstanceMethod(inst, sel, cls);
        • 元类
          • resolveClassMethod(inst, sel, cls);
5. 如果以上能找到IMP，则打印并填充缓存log_and_fill_cache(cls, imp, sel, inst, curClass);
6. 如果找不到imp = _objc_msgForward_impcache

lookUpImp慢速查找流程 image.png

getMethodNoSuper_nolock流程

  该方法中可以看到，方法存储的结构是一个二维数组，会遍历调用调用search_method_list_inline，该方法会根据method列表是否修复过（进行排序过，这部分是在类的加载的时候做的事情），调用findMethodInSortedMethodList和findMethodInUnsortedMethodList。排序过的方法列表findMethodInSortedMethodList函数会进行而为查找算法查找，对未排序的方法列表，findMethodInUnsortedMethodList函数进行挨个遍历查找。

getMethodNoSuper_nolock流程

方法的查找（递归算法查找）

template<class getNameFunc>
ALWAYS_INLINE static method_t *
findMethodInUnsortedMethodList(SEL sel, const method_list_t *list, const getNameFunc &getName)
{
    // 递归遍历未排序方法列表
    for (auto& meth : *list) {
        if (getName(meth) == sel) return &meth;
    }
    return nil; // 找不到则返回nil
}

方法的查找（二分查找算法）

/***********************************************************************
 * search_method_list_inline
 **********************************************************************/
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; // 探针（一个来回摆动的指针，不断的取来获取name与sel对比）又因为SEL是进行hash之后的，保证了其唯一性

    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)getName(probe);
        
        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)getName((probe - 1))) {
                // 如果前一个的名字sel也一样，并且探针不是起始位置，则表示前一个是分类中的方法，说明了如果分类重写了类的方法，调用该方法的时候会调用分类的方法
                probe--;
            }
            return &*probe;
        }
        
        if (keyValue > probeValue) { // 如果探针的位置小于keyValue，说明在后半段（base从探针+1的位置开始），否则在前半段（base不变）
            base = probe + 1;
            count--;
        }
    }
    
    return nil;
}

二分查找案例1

while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
                // 如果前一个的名字sel也一样，并且探针不是起始位置，则表示前一个是分类中的方法，说明了如果分类重写了类的方法，调用该方法的时候会调用分类的方法
                probe--;
   }

  如果找到了方法，则循环遍历取探针的前一个方法，直到取到最前面一个相同的SEL。这可以证明如果分类重写了原来类的方法，则会调用分类方法。在底层中方法并不是覆盖了，只是插入方法列表的时候放到了原类的方法前面。

二分查找案例2

cache的insert流程：
cls->cache.insert(sel, imp, receiver);

1. 检测类的初始化标志位，如果没有初始化就什么不干
2. 拿到newOccupied，oldCapacity，capacity初始值=oldCapacity
3. 判断是否第一次申请缓存空间还是需要扩容
   1. 判断如果是空缓存，如果是就申请缓存空间reallocate(oldCapacity, capacity, /* freeOld */false); 创建容量为capacity大小（INIT_CACHE_SIZE，即是1<<2 = 4）的空间
      • 获取旧的buckets（根据第三个参数为true就进行释放旧值）
      • 调用allocateBuckets(newCapacity);创建一个capacity（4个）大小容量的buckets容器（以下说明创建的时候最后一个bucket_t就已经被占用了作为一个标记）
        • calloc(bytesForCapacity(newCapacity), 1);创建容器
        • 获取到最后一个bucket_t指针end
        • 设置最后一个bucket_t的SEL为1，IMP指向容器的首地址，也就是第一个bucket_t
        • 检测环境变量OBJC_PRINT_CACHE_SETUP为true，打印缓存容器
      • setBucketsAndMask(newBuckets, newCapacity - 1);设置的时候排除最后一个结束标志位固定占用的大小
        • _occupied初始化为0
      • 如果是扩容也就是freeOld=true则collect_free(oldBuckets, oldCapacity)
   2. 如果有缓存空间了，新的占用量newOccupied + 1个结束标记bucket <= 缓存填充比例3/4.
   3. 如果达到扩容条件（也就是大于缓存填充比例），就进行2倍扩容，但是capacity最大不超过2^16=65536，重新调用reallocate(oldCapacity, capacity, true);创建更大的容器，并且把旧的bucktes释放，也就是把所有的bucket_t丢弃。（为什么丢弃：因为将旧数据挪到新的buckets的CPU开销成本太大）
4. 创建一个新的bucket_t b = buckets()， 对sel进行hash ---> (sel & (capacity-1))得到一个下标
5. 进行do...while循环，查找一个未使用的插槽并插入
   • 以sel的hash值为key，从bucket中取出sel,
     • 如果不存在_occupied++，给bucket set sel和IMP set(b，sel, imp, cls())，设置的时候根据是都原子和encode对IMP进行编码再存储
     • 如果sel已经存在，说明已存在缓存，则什么也不干直接退出
   • 条件cache_next(i, (capacity - 1)) --> (i + 1) & (capacity - 1) != begin也就是进行在哈希
6. 如果插入不成功，就bad_cache

cache的insert流程