OC Underlying Principle 07: Slow lookup of message flow

The introduction of

Find the flow by testing the code demo method:

Isa and SuperClass trends flow chart:

1.LGPerson instance methods are only implemented and not declared in the NSObject class.

/ / NSObject classification. M
- (void)sayEasy{
  NSLog(@"%s",__func__);
}
/ / call
[student performSelector: @selector(sayEasy)];
Copy the code

Calling NSObject’s – (void)sayEasy method works fine. 2.LGPerson class methods are only declared and not implemented in the NSObject class.

    / / NSObject classification. M
    - (void)sayEasy{
        NSLog(@"%s",__func__);
    }
    + (void)sayEasy{
        NSLog(@"%s",__func__);
    }
    // Call method undeclared, called by performSelector
    [LGStudent performSelector: @selector(sayEasy)];
Copy the code

If the root metaclass + (void)sayEasy is implemented, the root metaclass + (void)sayEasy is called;
If the root metaclass + (void)sayEasy is not implemented, the NSObject class is found along the superclass, and – (void)sayEasy of the NSObject class is called.

Objc_msgSend Slow search

In the objc_msgSend message process quick lookup, we analyzed the quick lookup process. If the quick lookup cannot be found, we need to enter the slow lookup process.

In the quick lookup process, if the method implementation is not found, both CheckMiss and JumpMiss end up with the __objc_msgSend_uncached assembly function.

`__objc_msgSend_uncached`

inobjc-msg-arm64.sFind in file__objc_msgSend_uncachedThe assembly implementation, the core of which isMethodtable ELookup (list of query methods), its source code is as follows:

STATIC_ENTRY __objc_msgSend_uncached
UNWIND __objc_msgSend_uncached, FrameWithNoSaves

// THIS IS NOT A CALLABLE C FUNCTION
// Out-of-band p16 is the class to search

MethodTableLookup // Start querying the list of methods
TailCallFunctionPointer x17

END_ENTRY __objc_msgSend_uncached
Copy the code

searchMethodTableLookupThe assembly implementation, the core of which is_lookUpImpOrForward, assembly source code implementation as follows:

.macro MethodTableLookup
    
    // push frame
    SignLR
    stp fp, lr, [sp, #-16]!
    mov fp, sp

    // save parameter registers: x0.. x8, q0.. q7
    sub sp, sp, #(10*8 + 8*16)
    stp q0, q1, [sp, #(0*16)]
    stp q2, q3, [sp, #(2*16)]
    stp q4, q5, [sp, #(4*16)]
    stp q6, q7, [sp, #(6*16)]
    stp x0, x1, [sp, #(8*16+0*8)]
    stp x2, x3, [sp, #(8*16+2*8)]
    stp x4, x5, [sp, #(8*16+4*8)]
    stp x6, x7, [sp, #(8*16+6*8)]
    str x8,     [sp, #(8*16+8*8)]

    // lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
    // receiver and selector already in x0 and x1
    mov x2, x16
    mov x3, #3
    bl  _lookUpImpOrForward // Core source code

    // IMP in x0
    mov x17, x0
    
    // restore registers and return
    ldp q0, q1, [sp, #(0*16)]
    ldp q2, q3, [sp, #(2*16)]
    ldp q4, q5, [sp, #(4*16)]
    ldp q6, q7, [sp, #(6*16)]
    ldp x0, x1, [sp, #(8*16+0*8)]
    ldp x2, x3, [sp, #(8*16+2*8)]
    ldp x4, x5, [sp, #(8*16+4*8)]
    ldp x6, x7, [sp, #(8*16+6*8)]
    ldr x8,     [sp, #(8*16+8*8)]

    mov sp, fp
    ldp fp, lr, [sp], #16
    AuthenticateLR

.endmacro
Copy the code

The test code validates the above assembly flow

//LGPerson.h
- (void)say666;

//LGPerson.m
//- (void)say666 not implemented

//main.m
LGPerson *person = [LGPerson alloc];
[person say666];
Copy the code

Test the code in the source code[person say666]Interrupt point, open assembly debuggingDebug -- Debug worlflow -- Always show Disassembly
In the assemblyobjc_msgSendAdd a breakpoint, perform the break, holdcontrol + stepintoAnd into theobjc_msgSendThe assembly of
in_objc_msgSend_uncachedAdd a breakpoint, perform the break, holdcontrol + stepintoTo enter assembly.

As you can see from above, lookUpImpOrForward is the last thing that comes up, and it is not an assembly implementation.

Source method search: assembly call C/C ++ method, C/C ++ method implementation of a less underscore; Underline the reverse.

So the global lookUpImpOrForward implementation in the source code comes to the C/C ++ part of the slow lookup. Objc-runtimenew. mm: lookUpImpOrForward: objc-Runtimenew. mm: lookUpImpOrForward: objc-Runtimenew. mm: lookUpImpOrForward:

IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    // Defined message forwarding
    const IMP forward_imp = (IMP)_objc_msgForward_impcache; // Default values are explained separately below
    IMP imp = nil;
    Class curClass;

    runtimeLock.assertUnlocked();

    // Quickly find, if found, return imp directly
    // Purpose: to prevent multithreading from happening when a function is called
    if (fastpath(behavior & LOOKUP_CACHE)) { 
        imp = cache_getImp(cls, sel);
        if (imp) goto done_nolock;
    }
    
    // Add a lock to ensure thread-safe reading
    runtimeLock.lock();
    
    // Check whether the current class is a known class: Check whether the current class is an approved class, that is, a loaded class
    checkIsKnownClass(cls); 
    
    // Check whether the class is implemented. If not, it needs to be implemented first. In this case, the purpose is to determine the parent class chain for subsequent for loop
    if(slowpath(! cls->isRealized())) { cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);// See separate instructions below for details
    }

    // Determine whether the class is initialized, if not, recursively initialize all classes
    if(slowpath((behavior & LOOKUP_INITIALIZE) && ! cls->isInitialized())) {/ / initializeAndLeaveLocked recursive initialization of all classes, call callInitialize method. The callInitialize method sends initialize to the CLS
        cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
    }

    runtimeLock.assertLocked();
    curClass = cls;

    //---- The for loop below is the focus of our research
    
    // unreasonableClassCount -- Indicates the upper limit of class iterations
    // The recursion is due to the fact that the attempts decrement one during the first loop and are still within the upper limit when they loop again.
    for (unsigned attempts = unreasonableClassCount();;) { 
        //-- List of current class methods (using binary search algorithm), if found, return, cache method in cache
        Method meth = getMethodNoSuper_nolock(curClass, sel);// See separate instructions below for details
        if (meth) {
            imp = meth->imp;
            goto done;
        }
        // Current class = the parent of the current class, and determines if the parent is nil
        if (slowpath((curClass = curClass->superclass) == nil)) {
            //-- method implementation not found, method parser also not working, use forward
            imp = forward_imp;
            break;
        }

        // Stop if there is a loop in the parent chain
        if (slowpath(--attempts == 0)) {
            _objc_fatal("Memory corruption in class list.");
        }

        // -- superclass cache
        imp = cache_getImp(curClass, sel);// See separate instructions below for details
        if (slowpath(imp == forward_imp)) { 
            // If an IMP is found in the parent cache, imp is a forward message forward, the lookup stops, and the cache is not cached, and the method resolver of this class is called first
            break;
        }
        if (fastpath(imp)) {
            If the method is found in the parent cache, store it in the cachegoto done; }}// Failed to find method implementation, try method parsing once

    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        // The control condition of the dynamic method resolution, indicating that the process only moves once
        //^ The xor operation is equal to 0 and the different operation is 1
        behavior ^= LOOKUP_RESOLVER; 
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

// Imp is found
 done:
    // Store to cache
    log_and_fill_cache(cls, imp, sel, inst, curClass); 
    / / unlock
    runtimeLock.unlock();
 done_nolock:
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
    return imp;
}
Copy the code

The overall slow search process is shown in the figure below:

`lookUpImpOrForward`

LookUpImpOrForward: IMP forward_IMP = (IMP)_objc_msgForward_impcache; IMP imp = nil; There are mainly the following steps:

Cache_getImp = imp; cache_getImp = imp;
[Step 2] Judge CLS
- checkIsKnownClassDetermine whether or notKnown class, if not, thenAn error
- Whether the classimplementationIf no, yesrealizeClassMaybeSwiftAndLeaveLockedAt this time, the purpose of instantiation is to determine the parent class chain, RO, and RW, etc., the method of subsequent data reading and search cycle
- Whether or notInitialize the, if not, theninitializeAndLeaveLockedInitialize the
[Step 3] For loop, by class inheritance chain or metaclass inheritance chain order to find
- The current CLS method list uses binary search algorithm to find the method, if found, to imp, and enter the cache write process (in the cache principle analysis article has been detailed) log_AND_fill_cache
- CLS is currently assigned to the parent class. If the parent class is nil, imp = forward_IMP forwards the message and terminates the recursion.
- If there is a loop in the parent chain, an error is reported and the loop is terminated
```
// Halt if there is a cycle in the superclass chain.
if (slowpath(--attempts == 0)) {
    _objc_fatal("Memory corruption in class list.");
}
Copy the code
```
- Look up methods in the parent cache
  - ifimp = forward_impIf the message is forwarded, the for loop is broken
  - ifImp found, and not forward_IMPThe directReturns the imp, the implementation ofCache Write Process
After the for loop exits, if no implementation is found, try resolving resolveMethod_locked once

realizeClassMaybeSwiftAndLeaveLocked

RealizeClassMaybeSwiftAndLeaveLocked is aimed to determine the parent chain, for subsequent data preparation for loop. RealizeClassMaybeSwiftAndLeaveLocked internal call realizeClassMaybeSwiftMaybeRelock, Call realizeClassWithoutSwift realizeClassMaybeSwiftMaybeRelock. RealizeClassWithoutSwift main source code as follows:

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

    class_rw_t *rw;
    Class supercls;
    Class metacls;

    if(! cls)return nil;
    if (cls->isRealized()) return cls;
    ASSERT(cls == remapClass(cls));

    // fixme verify class is not in an un-dlopened part of the shared cache?

    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);
    }

#if FAST_CACHE_META
    if (isMeta) cls->cache.setBit(FAST_CACHE_META);
#endif

    // Choose an index for this class.
    // Sets cls->instancesRequireRawIsa if indexes no more indexes are available
    cls->chooseClassArrayIndex();

    if (PrintConnecting) {
        _objc_inform("CLASS: realizing class '%s'%s %p %p #%u %s%s",
                     cls->nameForLogging(), isMeta ? " (meta)" : "", 
                     (void*)cls, ro, cls->classArrayIndex(),
                     cls->isSwiftStable() ? "(swift)" : "",
                     cls->isSwiftLegacy() ? "(pre-stable swift)" : "");
    }

    // Realize superclass and metaclass, if they aren't already.
    // This needs to be done after RW_REALIZED is set above, for root classes.
    // This needs to be done after class index is chosen, for root metaclasses.
    // This assumes that none of those classes have Swift contents,
    // or that Swift's initializers have already been called.
    // fixme that assumption will be wrong if we add support
    // for ObjC subclasses of Swift classes.
    //---- find supercls metacls to determine the inheritance chain of classes and metaclasses in order to find the parent cache latersupercls = realizeClassWithoutSwift(remapClass(cls->superclass), nil); metacls = realizeClassWithoutSwift(remapClass(cls->ISA()), nil); .// Update superclass and metaclass in case of remapping
    //---- put supercls and metacls in
    cls->superclass = supercls;
    cls->initClassIsa(metacls);

    // Reconcile instance variable offsets / layout.
    // This may reallocate class_ro_t, updating our ro variable.
    if(supercls && ! isMeta) reconcileInstanceVariables(cls, supercls, ro);// Set fastInstanceSize if it wasn't set already.
    cls->setInstanceSize(ro->instanceSize);

    // Copy some flags from ro to rw
    if (ro->flags & RO_HAS_CXX_STRUCTORS) {
        cls->setHasCxxDtor();
        if(! (ro->flags & RO_HAS_CXX_DTOR_ONLY)) { cls->setHasCxxCtor(); }}// Propagate the associated objects forbidden flag from ro or from
    // the superclass.
    if ((ro->flags & RO_FORBIDS_ASSOCIATED_OBJECTS) ||
        (supercls && supercls->forbidsAssociatedObjects()))
    {
        rw->flags |= RW_FORBIDS_ASSOCIATED_OBJECTS;
    }

    // Connect this class to its superclass's subclass lists
    if (supercls) {
        addSubclass(supercls, cls);
    } else {
        addRootClass(cls);
    }

    // Attach categories
    //---- paste the list of methods, attributes, and protocols to rwe (rw->ext())
    methodizeClass(cls, previously);

    return cls;
}
Copy the code

Description:

todata() 、ro()The assignment
Recursively findsupercls,metaclsThe class and metaclass inheritance chain is determined for later lookup of the parent class cache
throughcls->superclass = supercls;andaddSubclass(supercls, cls);Verify the parent-child relationship and see that class is a bidirectional list
methodizeClassMethods in turnMethod list, properties, protocolbigRwe (rw - > ext ())in

GetMethodNoSuper_nolock Checks to see if there are any methods in the current curClass

The process is as follows:

static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel){... autoconst 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);// Binary search method list
        if (m) return m;
    }

    return nil;
}
Copy the code

The core calls search_method_list_inline, and the source code for the binary lookup core is as follows:

static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
    ASSERT(list);
    const method_t * const first = &list->first;
    const method_t *base = first;
    const method_t *probe;
    uintptr_t keyValue = (uintptr_t)key;
    uint32_t count;
    
    Sel is incremental in method_list
    for(count = list->count; count ! =0; count >>= 1) {
        probe = base + (count >> 1);
        
        uintptr_t probeValue = (uintptr_t)probe->name;
        
        if (keyValue == probeValue) {
            // `probe` is a match.
            // Rewind looking for the *first* occurrence of this value.
            // This is required for correct category overrides.
            //---- when sel is found and there is a method with the same name in the classification need probe--
            // the method loads the class first and then the classification method
            while (probe > first && keyValue == (uintptr_t)probe[-1].name) {
                probe--;
            }
            return (method_t *)probe;
        }
        
        if (keyValue > probeValue) {
            base = probe + 1; count--; }}return nil;
}
Copy the code

I’m going to take it from the first searchMiddle position, and want to findThe value of the key valuesIn comparison, ifequal, you need toExclusion classification methodAnd then the method implementation of the queried location is returned ifNot equal to the, you need toContinue binary search, if the loop tocount = 0orCould not find, directly returnsnil, as follows:To findLGPersonOf the classSay666 instance methodFor example, the binary search process is as follows:

GetMethodNoSuper_nolock returns to lookUpImpOrForwar if meth has a value, assign imp and cache goto done:

goto done

log_and_fill_cacheThe source code is as follows:

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
    cache_fill(cls, sel, imp, receiver);// write the method to the cache
}
Copy the code

Cache_fill writes methods to the cache. To improve performance by using quick lookups the next time this method is called.

To summarize the flow: objc_msgSend lookup cache -> Slow binary lookup if no cache is found -> cache_fill cache method if found -> Use objc_msgSend lookup cache fast flow next time this method is called.

If slow binary search doesn’t find anything, Slowpath ((curClass = curClass->getSuperclass()) == **nil**)) Continue with lookUpImpOrForward for the rest of the for loop.

Cache_getImp method: superclass cache lookup

STATIC_ENTRY _cache_getImp

    GetClassFromIsa_p16 p0
    CacheLookup GETIMP, _cache_getImp

LGetImpMiss:
    mov p0, #0
    ret
END_ENTRY _cache_getImp
Copy the code

cache_getImpAnd the way to do that is byAssembler _cache_getImp implementationAnd the incoming$0 是 GETIMP, as follows:

If a method implementation is found in the superclass cache, a jump to CacheHit is a hit and imp is returned directly
If no method implementation is found in the parent cache, jump to CheckMiss or JumpMiss, and return nil by checking $0 to LGetImpMiss

ResolveMethod_locked enter dynamic method resolutions

“For”, imp=forward_imp, not found Further down the path leads to the following method:

// No implementation found. Try method resolver once.
if (slowpath(behavior & LOOKUP_RESOLVER)) { // Dynamic method resolutions only come once
    behavior ^= LOOKUP_RESOLVER;
    return resolveMethod_locked(inst, sel, cls, behavior);// Enter the dynamic method resolution
}
Copy the code

resolveMethod_lockedEnter dynamic method resolution

`_objc_msgForward_impcache`

In the abovelookUpImpOrForwardIn the sourceforward_impThe default is_objc_msgForward_impcache.

Where _objc_msgForward_impcache is an assembly implementation that jumps to__objc_msgForward, its core is__objc_forward_handler:

STATIC_ENTRY __objc_msgForward_impcache

// No stret specialization.
b   __objc_msgForward

END_ENTRY __objc_msgForward_impcache

/ / 👇
ENTRY __objc_msgForward

adrp    x17, __objc_forward_handler@PAGE
ldr p17, [x17, __objc_forward_handler@PAGEOFF]
TailCallFunctionPointer x17
    
END_ENTRY __objc_msgForward
Copy the code

__objc_forward_handler is a global search for __objc_forward_handler, which has the following implementation: Essentially calling the objc_defaultForwardHandler method of C/C ++ :

// Default forward handler halts the process.
__attribute__((noreturn, cold)) void
objc_defaultForwardHandler(id self, SEL sel)
{
    _objc_fatal("%c[%s %s]: unrecognized selector sent to instance %p "
                "(no message forward handler is installed)", 
                class_isMetaClass(object_getClass(self)) ? '+' : The '-', 
                object_getClassName(self), sel_getName(sel), self);
}
void *_objc_forward_handler = (void*)objc_defaultForwardHandler;
Copy the code

This is one of the most common mistakes we make in daily development: failure to implement functions, running programs, and crashes.

`lookUpImpOrForward`The process to summarize

For object methods (that is, instance methods), that is, looking in a class, the parent chain of the slow lookup is: class — parent — root –nil
For class methods, that is, looking in metaclass, the parent chain of the slow lookup is: metaclass — root metaclass — root class –nil
If a quick lookup or a slow lookup does not find a method implementation, try dynamic method resolution
If the dynamic method resolution is still not found, the message is forwarded

The following sections describe the method implementation remediation and message forwarding process that we can do before an error is found

The article lists

List of blog posts

Thanks for this reference

IOS – Underlying Principle 13: Slow lookup for message flow analysis

OC Underlying Principle 07: Slow lookup of message flow

The introduction of

Find the flow by testing the code demo method:

Objc_msgSend Slow search

__objc_msgSend_uncached

The test code validates the above assembly flow

The overall slow search process is shown in the figure below:

lookUpImpOrForward

realizeClassMaybeSwiftAndLeaveLocked

GetMethodNoSuper_nolock Checks to see if there are any methods in the current curClass

Cache_getImp method: superclass cache lookup

ResolveMethod_locked enter dynamic method resolutions

_objc_msgForward_impcache

lookUpImpOrForwardThe process to summarize

The article lists

Thanks for this reference

Related Posts

IOS Low-level exploration – KVC

IOS integrated drop – down refresh control & achieve more awareness pull – up loading

Use hitTest to make the bottom overlapped view respond when an overlapped part is clicked

`__objc_msgSend_uncached`

`lookUpImpOrForward`

`_objc_msgForward_impcache`

`lookUpImpOrForward`The process to summarize