什么时候会进行慢速查找

当快速查找也就是在缓存中找不到时，就会来到慢速查找流程，所谓的慢速查找就是当类以及类的继承链的方法列表中进行方法查找。
在快速查找时没找到需要执行的方法时，会调用__objc_msgLookup_uncached进行处理，该方法中的核心方法是MethodTableLookup，从方法列表中查询方法。

__objc_msgLookup_uncached源码

  1. STATIC_ENTRY __objc_msgSend_uncached
  2. UNWIND __objc_msgSend_uncached, FrameWithNoSaves
  4. // 方法列表中查找方法
  5. MethodTableLookup
  6. TailCallFunctionPointer x17
  8. END_ENTRY __objc_msgSend_uncached

MethodTableLookup源码

  1. .macro MethodTableLookup
  3.     SAVE_REGS MSGSEND
  5.     // lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
  6.     // receiver and selector already in x0 and x1
  7.     mov    x2, x16
  8.     mov    x3, #3
  9.     // 研究的核心 方法查找的实现
  10.     bl    _lookUpImpOrForward
  12.     // IMP in x0
  13.     mov    x17, x0
  15.     RESTORE_REGS MSGSEND
  17. .endmacro
  • MethodTableLookup方法中我们要研究的是_lookUpImpOrForward方法；
  • 全局搜索_lookUpImpOrForward方法，我们发现汇编中只有调用，并找不到实现；
  • 其实_lookUpImpOrForward是C来实现的，所以此处我们应该搜索lookUpImpOrForward方法。
  • ※※在这里有一个小技巧，汇编方法方法名前一般有两个下划线，去掉一个下划线就是对应的C++方法的方法名，那么在去掉一个下划线就是对应C方法的方法名。

  • 下面我们来看lookUpImpOrForward内部实现。

    慢速查找

    lookUpImpOrForward

    首先我们全局搜索lookUpImpOrForward，可以看到在objc-runtime-new.mm中。

    1. IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
    2. {
    3.   // 定义一个_objc_msgForward用于处理消息转发
    4.   const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    5.   // 初始化一个空的IMP函数指针
    6.   IMP imp = nil;
    7.   // 声明当前操作的类对象
    8.   Class curClass;
    10.   runtimeLock.assertUnlocked();
    12.   // 判断当前类是否已经初始化完成
    13.   if (slowpath(!cls->isInitialized())) {
    14.       behavior |= LOOKUP_NOCACHE;
    15.   }
    17.   runtimeLock.lock();
    19.   // 判断当前类是否是一个已知类，也就是是否已经加载
    20.   checkIsKnownClass(cls);
    21.   // 获取当前类对象
    22.   cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
    23.   // runtimeLock may have been dropped but is now locked again
    24.   runtimeLock.assertLocked();
    25.   // 赋值当前操作的类对象
    26.   curClass = cls;
    28.   // 循环遍历从继承链的方法列表中查询方法实现
    29.   for (unsigned attempts = unreasonableClassCount();;) {
    30.       if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
    31. #if CONFIG_USE_PREOPT_CACHES
    32.           imp = cache_getImp(curClass, sel);
    33.           if (imp) goto done_unlock;
    34.           curClass = curClass->cache.preoptFallbackClass();
    35. #endif
    36.       } else {
    37.           // curClass method list.
    38.           // 采用二分法从当前类的方法列表中查询当前方法是否存在
    39.           Method meth = getMethodNoSuper_nolock(curClass, sel);
    40.           // 如果返回的meth存在，则说明查找到了，获取方法的imp并进行赋值，结束慢速查找流程
    41.           if (meth) {
    42.               imp = meth->imp(false);
    43.               goto done;
    44.           }
    46.           // 此处判断当前类的父类是否为空，并将父类赋值给当前类，如果父类为nil时仍查找失败，则结束慢速查找
    47.           if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
    48.               // No implementation found, and method resolver didn't help.
    49.               // Use forwarding.
    50.               imp = forward_imp;
    51.               break;
    52.           }
    53.       }
    55.       // Halt if there is a cycle in the superclass chain.
    56.       if (slowpath(--attempts == 0)) {
    57.           _objc_fatal("Memory corruption in class list.");
    58.       }
    60.       // Superclass cache.
    61.       // 优先从父类的缓存中在查找一次，如果为找到则进入下次循环，从父类方法列表中进行查找
    62.       imp = cache_getImp(curClass, sel);
    63.       if (slowpath(imp == forward_imp)) {
    64.           // Found a forward:: entry in a superclass.
    65.           // Stop searching, but don't cache yet; call method
    66.           // resolver for this class first.
    67.           break;
    68.       }
    69.       // 如果从父类的缓存中查找的话，则结束慢速查找
    70.       if (fastpath(imp)) {
    71.           // Found the method in a superclass. Cache it in this class.
    72.           goto done;
    73.       }
    74.   }
    76.   // No implementation found. Try method resolver once.
    77.   // 如果遍历结束，查找方法失败，则进入到消息转发流程
    78.   // 会调用resolveMethod_locked进行消息转发
    79.   if (slowpath(behavior & LOOKUP_RESOLVER)) {
    80.       behavior ^= LOOKUP_RESOLVER;
    81.       return resolveMethod_locked(inst, sel, cls, behavior);
    82.   }
    84. // 完成慢速查找
    85. done:
    86.   if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) {
    87. #if CONFIG_USE_PREOPT_CACHES
    88.       while (cls->cache.isConstantOptimizedCache(/* strict */true)) {
    89.           cls = cls->cache.preoptFallbackClass();
    90.       }
    91. #endif
    92.       // 将方法加入到缓存中
    93.       log_and_fill_cache(cls, imp, sel, inst, curClass);
    94.   }
    95. done_unlock:
    96.   runtimeLock.unlock();
    97.   if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
    98.       return nil;
    99.   }
    100.   return imp;
    101. }

    realizeAndInitializeIfNeeded_locked获取当前类对象方法

    1. realizeAndInitializeIfNeeded_locked(id inst, Class cls, bool initialize)
    2. {
    3.   runtimeLock.assertLocked();
    4.   // 判断当前类是否已经实现，如果没实现需要先实现
    5.   if (slowpath(!cls->isRealized())) {
    6.       // 确定当前类的继承链和ISA的继承链
    7.       cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
    8.       // runtimeLock may have been dropped but is now locked again
    9.   }
    11.   // 判断是否初始化，如果没有，则需要先进行初始化
    12.   if (slowpath(initialize && !cls->isInitialized())) {
    13.       cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
    14.       // runtimeLock may have been dropped but is now locked again
    16.       // If sel == initialize, class_initialize will send +initialize and
    17.       // then the messenger will send +initialize again after this
    18.       // procedure finishes. Of course, if this is not being called
    19.       // from the messenger then it won't happen. 2778172
    20.   }
    21.   return cls;
    22. }

    确定当前类的继承链和ISA的继承链

  • 确定当前类的父类，并执行递归，最终确定类的继承链，并确定跟类；

  • 确定元类，并将元类的继承链也递归确定下来；
  • 在realizeClassWithoutSwift中调用addSubclass来将父类与子类关联起来，并通过addRootClass来确定跟类。 ```objectivec static Class realizeClassMaybeSwiftAndLeaveLocked(Class cls, mutex_t& lock) { return realizeClassMaybeSwiftMaybeRelock(cls, lock, true); }

static Class realizeClassMaybeSwiftMaybeRelock(Class cls, mutex_t& lock, bool leaveLocked) { lock.assertLocked();

  1. if (!cls->isSwiftStable_ButAllowLegacyForNow()) {
  2.     // Non-Swift class. Realize it now with the lock still held.
  3.     // fixme wrong in the future for objc subclasses of swift classes
  4.     realizeClassWithoutSwift(cls, nil);
  5.     if (!leaveLocked) lock.unlock();
  6. } else {
  7.     // Swift class. We need to drop locks and call the Swift
  8.     // runtime to initialize it.
  9.     lock.unlock();
  10.     cls = realizeSwiftClass(cls);
  11.     ASSERT(cls->isRealized());    // callback must have provoked realization
  12.     if (leaveLocked) lock.lock();
  13. }
  15. return cls;

}

static Class realizeClassWithoutSwift(Class cls, Class previously) { runtimeLock.assertLocked();

  1. …………
  2. // 获取父类
  3. supercls = realizeClassWithoutSwift(remapClass(cls->getSuperclass()), nil);
  4. // 获取元类 ISA
  5. metacls = realizeClassWithoutSwift(remapClass(cls->ISA()), nil);
  6. …………
  8. // 设置父类
  9. cls->setSuperclass(supercls);
  10. // 设置元类
  11. cls->initClassIsa(metacls);
  13. // Connect this class to its superclass's subclass lists
  14. if (supercls) {
  15.     // 如果父类存在，将当前类添加为父类的子类
  16.     addSubclass(supercls, cls);
  17. } else {
  18.     // 否则将当前类设置为跟类
  19.     addRootClass(cls);
  20. }
  22. // Attach categories
  23. methodizeClass(cls, previously);
  25. return cls;

}

  1. <a name="rbU7u"></a>
  2. ### getMethodNoSuper_nolock方法列表二分查找
  3. <a name="k9AuL"></a>
  4. #### 方法查找流程
  5. getMethodNoSuper_nolock->search_method_list_inline->findMethodInSortedMethodList->findMethodInSortedMethodList
  6. <a name="JZE1o"></a>
  7. #### findMethodInSortedMethodList二分法实现
  8. 二分法查找的有点：查询速度快，又称折半查找法。
  9. ```objectivec
  10. findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)
  11. {
  12.     ASSERT(list);
  14.     auto first = list->begin();
  15.     auto base = first;
  16.     decltype(first) probe;
  18.     uintptr_t keyValue = (uintptr_t)key;
  19.     uint32_t count;
  21.     for (count = list->count; count != 0; count >>= 1) {
  22.         probe = base + (count >> 1);
  24.         uintptr_t probeValue = (uintptr_t)getName(probe);
  26.         if (keyValue == probeValue) {
  27.             // `probe` is a match.
  28.             // Rewind looking for the *first* occurrence of this value.
  29.             // This is required for correct category overrides.
  30.             while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
  31.                 probe--;
  32.             }
  33.             return &*probe;
  34.         }
  36.         if (keyValue > probeValue) {
  37.             base = probe + 1;
  38.             count--;
  39.         }
  40.     }
  42.     return nil;
  43. }

在父类中进行查找

  • 我们通过源码可以发现for循环其实是一个死循环，只能通过循环中的break来调出循环。

  • 也就是只有当imp == forward_imp或者curClass->getSuperclass()==nil时才会调出循环。

    1. for (unsigned attempts = unreasonableClassCount();;) {
    2.   …………
    3.   if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
    4.       // No implementation found, and method resolver didn't help.
    5.       // Use forwarding.
    6.       imp = forward_imp;
    7.       break;
    8.   }
    9.   …………
    10.   if (slowpath(imp == forward_imp)) {
    11.       // Found a forward:: entry in a superclass.
    12.       // Stop searching, but don't cache yet; call method
    13.       // resolver for this class first.
    14.       break;
    15.   }
    16.   …………
    17. }

  • 当在类中的methodList中没有找到方法时

    • 首先执行slowpath((curClass = curClass->getSuperclass())将curClass设置为父类
    • 判断父类是否为nil，如果为nil则调出循环
      1. if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
      2. // No implementation found, and method resolver didn't help.
      3. // Use forwarding.
      4. imp = forward_imp;
      5. break;
      6. }

  • 在父类的缓存中查找方法

    • 当前curClass指向的是父类，所以此时查找会查找父类的缓存；
    • 如果在父类的缓存中没有找到，就会进入下次循环，从父类的方法列表中进行慢速查找；
    • 在执行慢速查找时，如果仍然未找到，则会继续将curClass置为父类的父类，继续查找；
    • 直到当父类为nil时，此时会将imp赋值为forward_imp，跳出循环，结束查找流程；
    • 或者在父类中找到方法，将查找到的方法赋值给imp，跳出循环，结束查找流程；

      动态方法决议

      当慢速查找结束仍为找到方法实现时，则会进入到动态方法决议流程
      1. if (slowpath(behavior & LOOKUP_RESOLVER)) {
      2. behavior ^= LOOKUP_RESOLVER;
      3. return resolveMethod_locked(inst, sel, cls, behavior);
      4. }

      找到方法，加入缓存

      找到方法后，会将方法写入缓存，方便下次调用可以快速查找
      1. log_and_fill_cache(cls, imp, sel, inst, curClass);