In the previous objc_msgSend process analysis quick lookup article, we analyzed the quick lookup process. If the quick lookup is not available, we need to enter the slow lookup process. The following is the slow lookup analysis process

Objc_msgSend Analysis of the slow search process

Slow lookup – assembly part

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

  • inobjc-msg-arm64.sFind in file__objc_msgSend_uncachedThe assembly implementation, the core of which isMethodtable ELookup (list of query methods), the 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 // TailCallFunctionPointer x17 END_ENTRY __objc_msgSend_uncachedCopy 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, IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP IMP #(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 .endmacroCopy the code

validation

The above assembly process can be verified by assembly debugging

  • In main, place a breakpoint on the method call of the [Person sayHello] object, for example, and run the program with Debug — Debug worlflow — Always show Disassembly enabled

  • Add a breakpoint to objc_msgSend in assembler, execute the break, hold down control + stepinto, enter objc_msgSend in assembler

  • Add a breakpoint to _objc_msgSend_uncached, break it, and hold down control + stepinto to compile

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

Note: 1, C/C++ call assembly, to find assembly, C/C++ call method need to add an underscore 2, assembly call C/C++ method, to find C/C++ method, need to remove an underscore assembly call method

Slow lookup -C/C++ section

  • Follow the instructions in the assembly section to continue the search globallylookUpImpOrForwardAnd finally theobjc-runtime-new.mmFile found in the source code implementation, this is aC implements the function
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, Int behavior) {// Define message forwarding const IMP forward_IMP = (IMP)_objc_msgForward_impcache; IMP imp = nil; Class curClass; runtimeLock.assertUnlocked(); // return imp directly if found If (fastPath (behavior & LOOKUP_CACHE)) {imp = cache_getImp(CLS, sel); if (imp) goto done_nolock; } runtimelock.lock (); CheckIsKnownClass (CLS); // Check whether the current class is a known class. Slowpath (!); // Check whether the class is implemented. If not, implement it first. cls->isRealized())) { cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock); If (slowPath ((behavior & LOOKUP_INITIALIZE) &&! cls->isInitialized())) { cls = initializeAndLeaveLocked(cls, inst, runtimeLock); } runtimeLock.assertLocked(); curClass = cls; UnreasonableClassCount -- indicates the upper limit of the class's iteration // For (unsigned attempts = unreasonableClassCount(); Method meth = getMethodNoSuper_nolock(curClass, sel); Method meth = getMethodNoSuper_nolock(curClass, sel); if (meth) { imp = meth->imp; goto done; If (slowPath ((curClass = curClass->superclass) == nil)) {slowpath((curClass = curClass->superclass) == nil); Use forward IMP = forward_IMP; break; } // Stop if (slowpath(--attempts == 0)) {_objc_fatal("Memory corruption in class list "); } // imp = cache_getImp(curClass, sel); Slowpath (imp == forward_imp)) {// If (slowpath(imp == forward_imp)) {// If (slowpath(imp == forward_imp)) {// If (slowpath(imp == forward_imp)); } if (fastPath (imp)) {if (fastPath (imp)) {goto done; If (slowpath(behavior & LOOKUP_RESOLVER)) {if (slowpath(behavior & LOOKUP_RESOLVER)) { return resolveMethod_locked(inst, sel, cls, behavior); } 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 figure 1

There are mainly the following steps:

  • [first step] Cache cache search, that is, fast search, find a direct return to IMP, otherwise, enter [second step]

  • [Step 2] Judge CLS

    • Is the class known? If not, an error is reported

    • Whether the class is implemented, if not, it needs to be implemented first to determine the parent class chain. At this time, the purpose of instantiation is to determine the parent class chain, RO, and RW, etc., and the subsequent data reading and searching cycle of the method

    • Whether to initialize. If no, initialize

  • [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, enter the cache write process (in iOS- Underlying Principles 11: Objc_class cache principle analysis article has been detailed), and return IMP, if not found, return nil

    • CLS is currently assigned to the parent class. If the parent class is nil, IMP = message forward, and the recursion terminates.

    • If there is a loop in the parent chain, an error is reported and the loop is terminated

    • Look up methods in the parent cache

      • If it doesn’t, it returns nil and continues the loop

      • If found, it returns to IMP and executes the cache write process

  • [Step 4] Determine if dynamic method resolution has been performed

    • If not, perform dynamic method resolution

    • If dynamic method resolution has been performed once, the message forwarding process is entered

The above is the slow search process of the method. The principle of binary search and the detailed steps of the parent class cache search are explained in detail below

GetMethodNoSuper_nolock method: List of binary lookup methods

The process for finding a list of methods is as follows,

Its binary search core source code implementation is as follows

ALWAYS_INLINE 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; // Key equals say666 uint32_t count; //base = low, count = Max, probe = middle count ! = 0; Count >>= 1) {// Probe = base + (count >> 1); uintptr_t probeValue = (uintptr_t)probe->name; // If the probe's keyvalue equals the probe's probeValue, If (probe > first && keyValue ==) {// -- while translation -- exclude the classification name method while (probe > first && keyValue == (uintptr_t)probe[-1].name) {// Uintptr_t)probe[-1].name); It depends on who loads the probe first. } return (method_t *)probe; If (keyValue > probeValue) {base = probe + 1; count--; } } return nil; }Copy the code

The algorithm principle is described as follows: Starting from the first lookup, every time take the middle position, and want to find the key value of values, if equal, you will need to eliminate classification method, and then the query to the location of the method to return to, if not equal, you need to continue to binary search, if the loop to count = 0 or not found, returns nil directly, as shown below:

Taking the say666 instance method of the LGPerson class as an example, the binary lookup is as follows

Cache_getImp method: superclass cache lookup

The cache_getImp method is implemented by assembly _cache_getImp, passing in $0 as GETIMP, as shown below

  • 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

conclusion

  • 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

Common methods are not implemented error source code

If no implementation is found in the process of fast lookup, slow lookup, or method resolution, message forwarding is used, and the process is as follows

Message forwarding will be implemented

  • 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
  • Assembler implementation to find__objc_forward_handler, and did not find, in the source code to remove an underscore for global search_objc_forward_handler, has the following implementation, which is essentially calledobjc_defaultForwardHandlermethods
// 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)) ? '+' : '-', 
                object_getClassName(self), sel_getName(sel), self);
}
void *_objc_forward_handler = (void*)objc_defaultForwardHandler;

Copy the code

If objc_defaultForwardHandler looks familiar, this is the most common error we see in everyday development: not implementing a function, running an application, crashing.