If an IMP is not found, the search process does not end. Instead, another process ———— slow search process begins. So let’s take a look at the slow lookup process of objc_msgSend through a series of analyses!

Links to the Runtime messaging series

[I] Analysis of the process of quick search for Runtime messages

[2] Analysis of Runtime message slow search process

[c] Runtime dynamic method resolution and message forwarding

Objc_msgSend Process Review

When sending messages, objc_msgSend (Receiver, _cmd) is called to send messages, where receiver is the receiver of messages and _cmd is the content of messages. As follows:

Person *p = [Person alloc];
[p test];

// Convert to CPP
Person *p = ((Person *objc_msgSend(objc_getClass("Person"), sel_registerName("alloc")); 
objc_msgSend(p, sel_registerName("test"));    
Copy the code

1. Objc_msgSend Quick lookup review

1. Find ISA by class

Cache_t = isa; cache_t = isa

Then grab buckets for the storage method and try to grab IMP from bucket via hash array

4. Return if found, or continue traversing the other buckets if not found

5, finally enter the slow search process.

2. Objc_msgSend Slow search

Here, we start with a function ———— lookUpImpOrForward, which we trace back to in assembly analysis of fast lookups and start another journey of message lookups ———— slow lookups!

Objc_msgSend slow lookup parsing

LookUpImpOrForward method

• The following program is an implementation of lookUpImpOrForward in the Runtime. Refer to the comments for details:

#pragmaMark - Message lookup process, core content

NEVER_INLINE
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
#pragmaMark - Look for IMP from _objc_msgForward_impcache
    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    IMP imp = nil;
    Class curClass;

    runtimeLock.assertUnlocked(a);#pragmaMark - On the first initialization, mark the class as not Initialized yet
    if (slowpath(! cls->isInitialized())) {
        behavior |= LOOKUP_NOCACHE;
    }

    runtimeLock.lock(a);#pragmaMark - Checks whether the class has done an Initialized binding
    checkIsKnownClass(cls);
    cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
    runtimeLock.assertLocked(a); curClass = cls;#pragmaMark - Finds the method of the current class through the for loop
    for (unsigned attempts = unreasonableClassCount();;) {
        if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
#if CONFIG_USE_PREOPT_CACHES


#pragmaMark - left left left left left left left left left left down down down down down down down down down left left left left left left left left left left down down down down down down down down down left left left left left left left left left left down down down down down down down down down left left left left left left left left left down down down down down down down down left left left left left left down down down down down
#pragmaMark - Start looking for methods in the cache and method list

            imp = cache_getImp(curClass, sel);
            if (imp) goto done_unlock;
            curClass = curClass->cache.preoptFallbackClass(a);#endif
        } else {

#pragmaMark - Find methods in the list of methods in the current class (binary search method to find methods)
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {
                imp = meth->imp(false);
                goto done;
            }

#pragmaMark - No method found and no subsequent processing, out of the loop
            if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
                imp = forward_imp;
                break; }}#pragmaMark - The number of binary lookup attempts for the parent class ends, sending an error notification
        if (slowpath(--attempts == 0)) {
            _objc_fatal("Memory corruption in class list.");
        }

#pragmaMark - left left left left left left left left left left down down down down down down down down down left left left left left left left left left left down down down down down down down down down left left left left left left left left left left down down down down down down down down down left left left left left left left left left down down down down down down down down left left left left left left down down down down down
#pragmaMark - This class could not find a method and started looking for methods in the parent class's cache and method list
        imp = cache_getImp(curClass, sel);
        if (slowpath(imp == forward_imp)) {
#pragmaMark - Finds AN IMP in the cache and jumps out of the current loop to process the IMP
            break;
        }
        
        if (fastpath(imp)) {
#pragmaMark - Finds that the IMP is in the parent class, caches it into its own class information, and then processes the IMP
            gotodone; }}#pragmaMark - If imp is not implemented, then enter the message dynamic parsing process, if implemented, no processing, continue to follow up
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

#pragmaMark - left left left left left left left left left left down down down down down down down down down left left left left left left left left left left down down down down down down down down down left left left left left left left left left left down down down down down down down down down left left left left left left left left left down down down down down down down down left left left left left left down down down down down
#pragmaMark-************** Core transaction process ************
#pragmaMark - left left left left left left left left left left down down down down down down down down down left left left left left left left left left left down down down down down down down down down left left left left left left left left left left down down down down down down down down down left left left left left left left left left down down down down down down down down left left left left left left down down down down down

/* * done done: * 1, if there is IMP in cache, return nil */ 2, print and insert method into current class information */ 3, if there is no cache or method like IMP found, return nil */

 done:
    if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) {
#if CONFIG_USE_PREOPT_CACHES
        while (cls->cache.isConstantOptimizedCache(/* strict */true)) {
            cls = cls->cache.preoptFallbackClass(a); }#endif
        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

2. Flow chart of message slow search

3. Key points in the search process

Fast search process we analyzed the assembly related implementation, so slow search is also related to the difficulties exist. For example, in the process of finding a method, what is the basis of the upper level search, search algorithm implementation. So let’s look at these key code implementations!

Analysis of key points in the search process

3.1. How do I find cached methods in a class?

        meth = _cache_getMethod(curClass, sel, _objc_msgForward_impcache);
Copy the code

• We can’t find the implementation of _cache_getMethod in runtime c++ code, so we search for the implementation of assembly:

#pragmaMark goes through isa->class->cache_t->buckets->bucket->SEL IMP
#pragmaMark goes through isa->class->cache_t->buckets->bucket->SEL IMP
#pragmaMark goes through isa->class->cache_t->buckets->bucket->SEL IMP

1: cmp    p0, #0

2: GetClassFromIsa_p16 p13, 1, x0    // p16 = class

3: CacheLookup NORMAL, _objc_msgSend, __objc_msgSend_uncached

3.1 : LLookupStart -> CACHE_MASK_STORAGE_HIGH_16

/ / get the cache
ldr    p11, [x16, #CACHE]            // p11 = mask|buckets

CONFIG_USE_PREOPT_CACHES == 1

// Whether position 0 of P11 is 0 No -> LLookupPreopt
tbnz    p11, #0, LLookupPreopt\Function
and    p10, p11, #0x0000ffffffffffff    // p10 = buckets

// p1 sel >> 7 == value ^= value >> 7;
eor    p12, p1, p1, LSR #7
/ / the hash index
and    p12, p12, p11, LSR #48        // x12 = (_cmd ^ (_cmd >> 7)) & mask

// index << 4
/ / 2 * 16
// buckets + 32
P13 bucket(sel imp)
add    p13, p10, p12, LSL #(1+PTRSHIFT)
                    // p13 = buckets + ((_cmd & mask) << (1+PTRSHIFT))
// sel -> imp

Copy the code

3.2. How to find a method in the list of methods in a class?

• During the search, the following methods are called to perform the method search.

#pragmaMark - Find methods in the list of methods in the current class (binary search method to find methods)

 Method meth = getMethodNoSuper_nolock(curClass, sel);

Copy the code

• GetMethodNoSuper_nolock internally implements the CLS ->data()->methods() procedure.

static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{...auto const methods = cls->data() - >methods(a);for (auto mlists = methods.beginLists(),
              end = methods.endLists(a); mlists ! = end; ++mlists) {method_t *m = search_method_list_inline(*mlists, sel);
        if (m) return m;
    }
    return nil;
}
Copy the code

Iv. Summary of overall thinking:

1, first check whether the class exists, does not exist, return null, otherwise continue,

2, find the class’s cache, IMP return, otherwise continue,

3, find class’s method lists, return IMP if found, otherwise continue,

4, search the superclass cache (superclass) and method lists, find return IMP, otherwise continue

5, if you find IMP, and IMP is not the IMP of this class, the parent class OF IMP cache copy to their own cache next use,

6, if there is no IMP, then the dynamic method resolution and message forwarding process is performed.

The above procedure is a summary of the slow search process of the whole method.