When do slow lookups happen

When fast lookups are not found in the cache, slow lookups occur. Slow lookups occur when methods are found in the list of methods in the class and its inheritance chain.

__objc_msgLookup_uncached is called when we don’t find a method to be executed during a quick lookup. The core method in this method is MethodTableLookup, which queries methods from the list of methods ached.

__objc_msgLookup_uncached source

STATIC_ENTRY __objc_msgSend_uncached UNWIND __objc_msgSend_uncached, MethodTableLookup TailCallFunctionPointer x17 END_ENTRY __objc_msgSend_uncachedCopy the code

MethodTableLookup source

.macro MethodTableLookup SAVE_REGS MSGSEND // lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER) // receiver and selector already in x0 and x1 mov x2, x16 mov x3, // IMP in X0 mov X17, x0 RESTORE_REGS MSgsen.endmacroCopy the code
  • MethodTableLookupAnd the way we’re going to look at it is_lookUpImpOrForwardMethods;
  • Global search_lookUpImpOrForwardMethod, we found that the assembly only calls, and can not find implementation;
  • C implements _lookUpImpOrForward, so we should search for lookUpImpOrForward methods here.
  • ※※ There is a little trick here, assembly method names usually have two underscores, remove an underscore is the corresponding C++ method name, so remove an underscore is the corresponding C method name.
  • So let’s look atlookUpImpOrForwardInternal implementation.

Slow to find

lookUpImpOrForward

First we search globally for lookUpImpOrForward, which we can see in objC-Runtime-new.mm.

IMP lookUpImpOrForward(id inst, SEL sel, Class cls, Int behavior) {// define a _objc_msgForward for message forwarding const IMP forward_IMP = (IMP)_objc_msgForward_impcache; // initialize an empty IMP function pointer IMP IMP = nil; // Declare the current Class object Class curClass; runtimeLock.assertUnlocked(); // Check whether the current class has been initialized. cls->isInitialized())) { behavior |= LOOKUP_NOCACHE; } runtimeLock.lock(); // Check whether the current class is a known class, i.e. whether the checkIsKnownClass(CLS) has been loaded; / / get the current class object CLS = realizeAndInitializeIfNeeded_locked (inst, CLS, behaviors & LOOKUP_INITIALIZE); // runtimeLock may have been dropped but is now locked again runtimeLock.assertLocked(); // Assign the current operation to the class object curClass = CLS; Reasonableclasscount ();) { if (curClass->cache.isConstantOptimizedCache(/* strict */true)) { #if CONFIG_USE_PREOPT_CACHES imp = cache_getImp(curClass, sel); if (imp) goto done_unlock; curClass = curClass->cache.preoptFallbackClass(); Method meth = getMethodNoSuper_nolock(curClass, meth = getMethodNoSuper_nolock); sel); If (meth) {imp = meth->imp(false); if (meth) {meth->imp(false); goto done; } // Check whether the parent of the current class is empty and assign the parent to the current class. Slowpath ((curClass = curClass->getSuperclass()) == 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."); Imp = cache_getImp(curClass, sel);} // Superclass cache. 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); } // Complete the slow search done: if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) { #if CONFIG_USE_PREOPT_CACHES while (cls->cache.isConstantOptimizedCache(/* strict */true)) { cls = cls->cache.preoptFallbackClass(); } #endif log_and_fill_cache(CLS, IMP, sel, inst, curClass); } done_unlock: runtimeLock.unlock(); if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) { return nil; } return imp; }Copy the code

RealizeAndInitializeIfNeeded_locked for current class object method

realizeAndInitializeIfNeeded_locked(id inst, Class cls, bool initialize) { runtimeLock.assertLocked(); // Check whether the current class is implemented. If not, implement slowPath (! CLS - > isRealized ())) {/ / to determine the current class inheritance chain and ISA inheritance chain CLS = realizeClassMaybeSwiftAndLeaveLocked (CLS, runtimeLock); RuntimeLock may have been dropped but is now locked again} // If (slowPath (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 } return cls; }Copy the code

Determines the inheritance chain of the current class and the inheritance chain of ISA

  • Determine the parent class of the current class, and perform recursion, and finally determine the inheritance chain of the class, and determine the following class;
  • Determine metaclass and recursively determine the inheritance chain of metaclass.
  • inrealizeClassWithoutSwiftIn the calladdSubclassTo associate a parent class with a child class, and passaddRootClassTo determine the following class.
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(); if (! cls->isSwiftStable_ButAllowLegacyForNow()) { // Non-Swift class. Realize it now with the lock still held. // fixme wrong  in the future for objc subclasses of swift classes realizeClassWithoutSwift(cls, nil); if (! leaveLocked) lock.unlock(); } else { // Swift class. We need to drop locks and call the Swift // runtime to initialize it. lock.unlock(); cls = realizeSwiftClass(cls); ASSERT(cls->isRealized()); // callback must have provoked realization if (leaveLocked) lock.lock(); } return cls; } static Class realizeClassWithoutSwift(Class cls, Class previously) { runtimeLock.assertLocked(); ..................... Supercls = realizeClassWithoutSwift(remapClass(CLS ->getSuperclass()), nil); // Get metaclass ISA metacls = realizeClassWithoutSwift(remapClass(CLS ->ISA()), nil); ..................... // setSuperclass CLS ->setSuperclass(supercls); // Set the metaclass CLS ->initClassIsa(metacls); // Connect this class to its superclass's subclass lists if (supercls) {// If superclass exists, Add the current class to the superclass subclass addSubclass(supercls, CLS); } else {// otherwise set the current class to follow addRootClass(CLS); } // Attach categories methodizeClass(cls, previously); return cls; }Copy the code

GetMethodNoSuper_nolock Binary lookup of method list

Method Lookup process

getMethodNoSuper_nolock->search_method_list_inline->findMethodInSortedMethodList->findMethodInSortedMethodList

FindMethodInSortedMethodList dichotomy

Dichotomy search a bit: query speed, also known as half search method.

findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName) { 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)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))) { probe--; } return &*probe; } if (keyValue > probeValue) { base = probe + 1; count--; } } return nil; }Copy the code

Look it up in the parent class

  • We can see from the source that the for loop is an infinite loop and can only be called by a break in the loop.
  • That is, only whenimp == forward_imporcurClass->getSuperclass()==nilWill call out the loop.
for (unsigned attempts = unreasonableClassCount();;) {..................... if (slowpath((curClass = curClass->getSuperclass()) == nil)) { // No implementation found, and method resolver didn't help. // Use forwarding. imp = forward_imp; break; }..................... 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; }..................... }Copy the code
  • When no method is found in the methodList of a class
    • Executed firstslowpath((curClass = curClass->getSuperclass())Set curClass to the parent class
    • Checks if the parent class is nil, and if it is, calls the loop
if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
    // No implementation found, and method resolver didn't help.
    // Use forwarding.
    imp = forward_imp;
    break;
}
Copy the code
  • Look for methods in the parent’s cache
    • The current curClass refers to the parent class, so the lookup will look for the parent class’s cache.
    • If it is not found in the parent’s cache, it will enter the next loop and perform a slow search from the parent’s list of methods.
    • When a slow lookup is performed, if it is still not found, the curClass is set to the parent class and the search continues.
    • Until the parent class is nil, at which point imp is assigned to forward_IMP, breaking out of the loop and ending the search process;
    • Or find a method in the parent class, will find the method assigned to IMP, jump out of the loop, end the search process;

forward

When the slow search ends and the method implementation is still found, the message forwarding process is entered

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

Find the method and add it to the cache

After finding a method, the method is written to the cache for quick lookup in the next call

log_and_fill_cache(cls, imp, sel, inst, curClass);
Copy the code

\