In the previous article we explored fast lookup (caching) of messages, in this article we explore slow lookup.

Compilation exploration back toC++explore

We used the __objc_msgSend_uncached method, which should be used if we don’t get it properly.

STATIC_ENTRY __objc_msgSend_uncached UNWIND __objc_msgSend_uncached, // THIS IS NOT A CALLABLE C FUNCTION // out-of-band p15 IS the class to search // imp // method table lookup MethodTableLookup // The call returns x17 TailCallFunctionPointer x17 END_ENTRY __objc_msgSend_uncached. 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 -- // Pass the method to x17 mov x17, x0 RESTORE_REGS msgsend.endmacroCopy the code

Because x17 is a back value, mov x17, and x0 passes the lookup result to X17, the preceding code must be the lookup procedure, or _lookUpImpOrForward is the specific lookup method that we can easily guess from the name. We searched the objC source globally for _lookUpImpOrForward and found no code defining the method. Since assembly methods are prefixed with _ compared to c++ methods, we tried to remove the underscore to see if there was a corresponding c++ method. In line 6400 of objc-runtime-new.mm, we found the definition of the method.

lookUpImpOrForward

NEVER_INLINE
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    /// omit code
    // Check whether the class is loaded
    checkIsKnownClass(cls);
    Loading classes is not discussed in this article
    cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
    // runtimeLock may have been dropped but is now locked again
    runtimeLock.assertLocked(a); curClass = cls;// The code used to lookup 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().
    /// loop lookup method implementation
    for (unsigned attempts = unreasonableClassCount();;) {
        if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
#if CONFIG_USE_PREOPT_CACHES
            /// share cache lookup
            imp = cache_getImp(curClass, sel);
            if (imp) goto done_unlock;
            curClass = curClass->cache.preoptFallbackClass(a);#endif
        } else {
            // curClass method list.
            // the binary method finds the list of methods of the current class
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {
                // find a way to end the loop and jump to done:
                imp = meth->imp(false);
                goto done;
            }
            if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
                // No implementation found, and method resolver didn't help.
                // Use forwarding.
              	/// The root class was found, but the method implementation was not found. Forward_imp next exploration
                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.");
        }
        // Superclass cache.
      	// Find the parent 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;
        }
        if (fastpath(imp)) {
            / / find the done
            // Found the method in a superclass. Cache it in this class.
            goto done;
        }
      	// Superclass cache not found continue for loop now curClass is actually superclass
    }
    // No implementation found. Try method resolver once.
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
    }
 done:
    if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) {
#if CONFIG_USE_PREOPT_CACHES
        while (cls->cache.isConstantOptimizedCache(/* strict */true)) {
            cls = cls->cache.preoptFallbackClass(a); }#endif
        // The lookup was successfully added to the cache
        log_and_fill_cache(cls, imp, sel, inst, curClass);
    }
 done_unlock:
    runtimeLock.unlock(a);if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
    return imp;
}
Copy the code

Looking at the code and comments, we can clearly see the recursive lookup flow of the method implementation

  1. Find if the shared cache is implemented
  2. Find if the current class has a method, if so, find if the classification method has an implementation, if the classification has an implementation, return the implementation of the classificationimpIf there is no implementation of the classification, return the found implementationimp
  3. If the current class has no implementation method, continue to look for an implementation in the parent class’s cache
  4. If the parent class cache has an implementation, todone:Insert the cache of the class searched (note not the parent class)
  5. If the parent class has no caching implementation, continueforLoop through the list of methods for the parent class
  6. Finally, if the root class is found but not found, executeimp = forward_imp;That’s dynamic method parsing, and dynamic method parsing is our next exploration.

Binary search

GetMethodNoSuper_nolock follow up step by step to find, we can see that the search traversal method is findMethodInSortedMethodList list method, it is clever way of using the binary search list traversal methods, source code is as follows

ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)
{
    ASSERT(list);

    auto first = list->begin(a);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);
        // Current sel== sel to find
        if (keyValue == probeValue) {
            // `probe` is a match.
            // Rewind looking for the *first* occurrence of this value.
            // This is required for correct category overrides.
            // There may be implementations with the same name in the method category
            while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
                probe--;
            }
            return &*probe;
        }

        if (keyValue > probeValue) {
            base = probe + 1; count--; }}return nil;
}
Copy the code

Binary lookup may not be easy to find, so let’s verify this with an example:

  • 1, assumptions,countThe initial value is 9selIn position six,count ! = 0performforcycle
  • 2,probe = base(0) + 4(9 > = 4 > 1) = 4
  • 3,keyValue == probeValueMark foundselexit
  • 4,keyValue > probeValue == trueAt this time,base= 4+1 = 5,count=count--= 8
  • 5,count = count >>1 = 4
  • 6. Second entryforCycle,probe = base(5) + 2(4 > > 1 = 2) = 7
  • 7,keyValue > probeValue == false.count = count >>1 = 2
  • 8. The third entryforCycle,probe = base(5) + 1(1 > > 1 = 2) = 6
  • 9, at this timekeyValue == probeValueFound the method to return, loop three times to find the implementation.

Our example is the case where the actual position of SEL is greater than the median value, and the case where sel is smaller than the median value is similar, so we will not use examples for verification.

conclusion

In this section, we explored the slow search process of the message. The specific process has been listed above. The general process is recursive search class and sel of its parent class.