impCan’t find the case

As mentioned in objc_msgSend message forwarding process Exploration 1, when we call the underlying objc_msgSend method, we will look for the IMP pointer corresponding to SEL in the class cache. The cacheHit method goes when it is found, and the cache hits. This is a quick lookup process, but if it can’t be found, as discussed in objc_msgSend message forwarding Process Exploration 1, the __objc_msgSend_uncached method is called. Here’s a look at the next step in calling this method. This is the slow lookup process of messages.

__objc_msgSend_uncachedMethod call flow

  1. __objc_msgSend_uncached

Global search find__objc_msgSend_uncachedThe entry to the method, which is looking atarm64Framework under the source code.

  1. MethodTableLookup 
.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 is stored in x0. If the IMP is stored in x0, it must be returned. So IMP is x17, X0 RESTORE_REGS MSgsendMacro in the return value of BL _lookUpImpOrForwardCopy the code

This means IMP is stored in x0 and must be returned if it is in x0. Because X0 is the first register location and the location where the return value is stored, IMP is in the return value of BL _lookUpImpOrForward.

  1. _lookUpImpOrForward

Same global search to findlookUpImpOrForwardMethods.

One thing you can notice here is, why is the flow of cached lookup methods written in assembly? Here are a few reasons.

  1. Assembly is closer to the bottom, more efficient, faster to find the cache
  2. Method parameters are not fixed and cannot be satisfied by C or C ++ methods, while assembly methods can be more dynamic
  1. checkIsKnownClass(Class cls)
static void
checkIsKnownClass(Class cls)
{
    if (slowpath(!isKnownClass(cls))) {
        _objc_fatal("Attempt to use unknown class %p.", cls);
    }
}
Copy the code

In this method you enter the isKnownClass(Class CLS) method.

static bool isKnownClass(Class cls) { if (fastpath(objc::dataSegmentsRanges.contains(cls->data()->witness, (uintptr_t)cls))) { return true; } auto &set = objc::allocatedClasses.get(); return set.find(cls) ! = set.end() || dataSegmentsContain(cls); }Copy the code

The main function of this step is to determine whether the current Class is registered in the cache table.

  1. realizeAndInitializeIfNeeded_locked

realizeAndInitializeIfNeeded_locked -> realizeClassMaybeSwiftAndLeaveLocked -> realizeClassMaybeSwiftMaybeRelock -> realizeClassWithoutSwift

static Class realizeClassWithoutSwift(Class cls, Class previously) { // 1. Auto ro = (const class_ro_t *) CLS ->data(); auto isMeta = ro->flags & RO_META; if (ro->flags & RO_FUTURE) { // This was a future class. rw data is already allocated. rw = cls->data(); ro = cls->data()->ro(); ASSERT(! isMeta); cls->changeInfo(RW_REALIZED|RW_REALIZING, RW_FUTURE); } else { // Normal class. Allocate writeable class data. rw = objc::zalloc<class_rw_t>(); rw->set_ro(ro); rw->flags = RW_REALIZED|RW_REALIZING|isMeta; cls->setData(rw); } // 2. Execute the realizeClassWithoutSwift method on the parent class and metaclass, which is a recursive method. The superclass and metaclass execute the realizeClassWithoutSwift method on their parent and metaclass at the same time realizeClassWithoutSwift(remapClass(cls->getSuperclass()), nil); metacls = realizeClassWithoutSwift(remapClass(cls->ISA()), nil); CLS ->setSuperclass(supercls); cls->initClassIsa(metacls); }Copy the code

Through the process step by step to realizeClassWithoutSwift method, the method mainly does three functions.

  1. Prepare ro and RW, initialize current class (ro has MethodList and ProtocolList)
  2. Execute the realizeClassWithoutSwift method on the parent class and metaclass, which is a recursive method, The parent class and metaclass execute the realizeClassWithoutSwift method on both their parent class and metaclass
  3. The parent class of CLS is set to SuperCLs, and the ISA Settings of CLS classes point to metaclass

This brings us to the famousisaThe flow chart.

  1. for (unsigned attempts = unreasonableClassCount();;)
for (unsigned attempts = unreasonableClassCount();;) {/ / here will judge did a cache if again (curClass - > cache. IsConstantOptimizedCache strict (/ * * / true)) {# if CONFIG_USE_PREOPT_CACHES imp =  cache_getImp(curClass, sel); if (imp) goto done_unlock; curClass = curClass->cache.preoptFallbackClass(); #endif } else { // curClass method list. Method meth = getMethodNoSuper_nolock(curClass, sel); if (meth) { imp = meth->imp(false); goto done; } if (slowpath((curClass = curClass->getSuperclass()) == nil)) { // No implementation found, and method resolver didn't help. // Use forwarding. imp = forward_imp; break; }}}Copy the code

For (unsigned attempts = unreasonableClassCount(); Is an infinite loop. The cache CONFIG_USE_PREOPT_CACHES is checked again.

  1. getMethodNoSuper_nolock(Class cls, SEL sel)
static method_t * getMethodNoSuper_nolock(Class cls, SEL sel) { runtimeLock.assertLocked(); ASSERT(cls->isRealized()); // fixme nil cls? // fixme nil sel? auto const methods = cls->data()->methods(); for (auto mlists = methods.beginLists(), end = methods.endLists(); mlists ! = end; ++mlists) { // <rdar://problem/46904873> getMethodNoSuper_nolock is the hottest // caller of search_method_list, inlining it turns // getMethodNoSuper_nolock into a frame-less function and eliminates // any store from this codepath. method_t *m = search_method_list_inline(*mlists, sel); if (m) return m; } return nil; }Copy the code

The list of methods for the class is iterated through.

  1. search_method_list_inline(const method_list_t *mlist, SEL sel)
ALWAYS_INLINE static method_t *
search_method_list_inline(const method_list_t *mlist, SEL sel)
{
    int methodListIsFixedUp = mlist->isFixedUp();
    int methodListHasExpectedSize = mlist->isExpectedSize();
    
    if (fastpath(methodListIsFixedUp && methodListHasExpectedSize)) {
        return findMethodInSortedMethodList(sel, mlist);
    } else {
        // Linear search of unsorted method list
        if (auto *m = findMethodInUnsortedMethodList(sel, mlist))
            return m;
    }

#if DEBUG
    // sanity-check negative results
    if (mlist->isFixedUp()) {
        for (auto& meth : *mlist) {
            if (meth.name() == sel) {
                _objc_fatal("linear search worked when binary search did not");
            }
        }
    }
#endif

    return nil;
}
Copy the code
  1. findMethodInSortedMethodList(SEL key, const method_list_t *list)
ALWAYS_INLINE static method_t * findMethodInSortedMethodList(SEL key, const method_list_t *list) { if (list->isSmallList()) { if (CONFIG_SHARED_CACHE_RELATIVE_DIRECT_SELECTORS && objc::inSharedCache((uintptr_t)list)) { return findMethodInSortedMethodList(key, list, [](method_t &m) { return m.getSmallNameAsSEL(); }); } else { return findMethodInSortedMethodList(key, list, [](method_t &m) { return m.getSmallNameAsSELRef(); }); } } else { return findMethodInSortedMethodList(key, list, [](method_t &m) { return m.big().name; }); }}Copy the code

This will determine whether it’s smallList or bigList, because m1 computers will be different.

  1. findMethodInSortedMethodList 
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; uintptr_t keyValue = (uintptr_t)key; uint32_t count; // 1000 - 0100 // 8 - 1 = 7 >> 0111 -> 0011 3 >> 1 == 1 // 0 + 4 = 4 // 5 - 8 // 6-7 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

This step is essentially binary traversal to find the corresponding IMP in method_list_t.

  1. log_and_fill_cache
static void log_and_fill_cache(Class cls, IMP imp, SEL sel, id receiver, Class implementer) { #if SUPPORT_MESSAGE_LOGGING if (slowpath(objcMsgLogEnabled && implementer)) { bool cacheIt = logMessageSend(implementer->isMetaClass(), cls->nameForLogging(), implementer->nameForLogging(), sel); if (! cacheIt) return; } #endif cls->cache.insert(sel, imp, receiver); }Copy the code

After finding imp here, sel and IMP will be added to the cache.

  1. cache_getImp(curClass, sel)
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;
        }
Copy the code

If no corresponding method is found in the current class, it will be searched in the parent class. When the parent class is searched, it will go through the fast search process first, and the slow search process will go through the fast search process if the method cannot be found. If slow does not find a parent that will look up the parent, it is a recursive search process.

  1. forward_imp
if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
                // No implementation found, and method resolver didn't help.
                // Use forwarding.
                imp = forward_imp;
                break;
            }
Copy the code

If you keep looking for the root class and don’t find it, imp is assigned to forward_IMP.