IOS underlying principles + reverse article summary

In the previous article iOS- Underlying Principle 12: Quick Search for Message Flow Analysis, we analyzed the fast search process. If the fast search cannot be found, it needs to enter the slow search process. The following is the analysis process of the slow search

Objc_msgSend Slow search process analysis

Slow lookup – Assembly section

In the quick lookup process, if you don’t find a method implementation, whether you go to CheckMiss or JumpMiss, you end up with the __objc_msgSend_uncached assembly function

  • inobjc-msg-arm64.sFind in file__objc_msgSend_uncachedAssembly implementation, the core of which isMethodTableLookup (query method list), whose 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 method list TailCallFunctionPointer x17 END_ENTRY __objC_MSgSend_cachedCopy the code
  • searchMethodTableLookupAssembly implementation, the core of which is_lookUpImpOrForward, the assembly source code implementation is 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 bd_lookupimporforward // IMP 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 .endmacroCopy the code

validation

The above assembly process can be verified by assembly debugging

  • inmain, such as[person sayHello]Object method call with a breakpoint, andDebug -- Debug worlflow -- select Always show Disassembly, run the program

  • In the assemblyobjc_msgSendAdd a break point and perform a break hold and holdcontrol + stepintoAnd into theobjc_msgSendThe assembly of

  • in_objc_msgSend_uncachedAdd a break point and perform a break hold and holdcontrol + stepinto, enter the assembly

And you can see from the top that what you end up with islookUpImpOrForwardThis is not a assembly implementation

(C/C++) (C/C++) (C/C++) (C/C++) (C/C++) (C/C++) (C/C++) (C/C++) (C/C++) (C/C++

Find the -c /C++ part slowly

  • Global search continues as prompted in the assembly sectionlookUpImpOrForwardAnd finally theobjc-runtime-new.mmFile to find the source code implementation, this is aFunction implemented in C
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, Int behavior) {const IMP forward_imp = (IMP)_objc_msgForward_impcache; IMP imp = nil; Class curClass; runtimeLock.assertUnlocked(); // Return imp if found // If (fastPath (Behavior & LOOKUP_CACHE)) {imp = cache_getImp(CLS, sel); if (imp) goto done_nolock; } // Lock to ensure thread-safe reading runtimelock.lock (); CheckIsKnownClass (CLS) : checkIsKnownClass(CLS) : checkIsKnownClass(CLS); If (slowpath(!)); // If (slowpath(!); 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 class iteration // (guess the reason for the recursion is that attempts subtract one on the first loop and are still within the upper limit on the second loop) Unsigned attempts = unreasonableClassCount();; Method meth = getMethodNoSuper_nolock(curClass, sel); if (meth) { imp = meth->imp; goto done; If (slowPath ((curClass = curClass->superclass) == nil)) {//-- slowPath ((curClass = curClass->superclass) == nil); Imp = forward_imp; break; If (slowPath (--attempts == 0)) {_objc_fatal("Memory corruption in class list."); } // -- parent class cache IMP = cache_getImp(curClass, sel); If (slowPath (imp == forward_imp)) {// If slowPath (imp == forward_IMP) is found in the parent class, stop looking, do not cache, first call this class's method parser break; } if (fastpath(imp)) {// if this method is found in the parent class, store it in the cache goto done; Behavior ^= LOOKUP_RESOLVER; behavior ^= LOOKUP_RESOLVER; behavior ^= LOOKUP_RESOLVER; return resolveMethod_locked(inst, sel, cls, behavior); } done: // Save 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

There are mainly the following steps:

  • [Step 1]cacheCache, i.eQuickly find, and return directly if foundimp, otherwise, enter [Step 2]
  • [Step 2] Judgecls

    • 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 loop of reading and searching the subsequent data of the method

    • Whether to initialize, if not, then initialize

  • [Step 3]The for loopAccording to theClass inheritance chain or metaclass inheritance chainSequential lookup of

    • The current CLS method list uses the binary search algorithm to find the method, if found, then enter the cache write process (described in iOS- Underlying Principle 11: Cache Principle analysis in objC_class), and return IMP, if not found, then return nil

    • CLS is currently assigned to the parent class. If the parent is nil, IMP = message forwarding, and the recursion is terminated. [Step 4]

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

    • Find method in the parent cache

      • If you don’t find it, you just return nil and continue the loop

      • If so, the imp is returned and the cache write process is executed

  • [Step 4]judgeWhether or not it has been executedDynamic method analysis

    • If not, dynamic method resolution is performed

    • If dynamic method resolution has been performed once, it goes to the message forwarding process

Above is the method of slow search process, the following in detail to explain the principle of binary search and parent cache search detailed steps

Method getMethodNoSuper_nolock: binary search method list

Search method listtheprocessAs shown below,

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 = say666 uint32_t count; For (count = list->count; count ! = 0; Count >>= 1) {// probe = base + (count >> 1); uintptr_t probeValue = (uintptr_t)probe->name; // If the keyvalue of the probe is equal to the probeValue of the probe, If (keyValue == probeValue) {// -- while shift -- while (probe > first && keyValue ==) (uintptr_t)probe[-1].name) {uintptr_t)probe[-1].name) {// if there are two classifications, It depends on who loads probe first. } return (method_t *)probe; If (keyValue > probeValue) {base = probe + 1; // If (keyValue > probeValue) {base = probe + 1; count--; } } return nil; }Copy the code

Algorithm principleThe description is: from the first search, every timeMiddle position, and want to findThe value of the key valuesFor comparison, ifequal, you need toExclusion classification methodThen return the query to the location of the method, ifNot equal to the, you need toContinue binary search, if the loop tocount = 0orCould not findIs returned directlynil, as shown below:

To findLGPersonOf the classSay666 instance methodFor example, the binary search process is as follows

The cache_getImp method: superclass cache lookup

cache_getImpAnd the way to do that is throughAssembler the _cache_getImp implementationAnd the incoming$0 是 GETIMP, as shown below

  • If the method implementation is found in the parent cache, it jumps to a CacheHit and returns IMP directly

  • If no method implementation is found in the parent cache, jump to CheckMiss or JumpMiss, jump to LGetImpMiss by judging $0, and return nil directly

conclusion

  • For object methods (i.e., instance methods), that is, looking in the class, the chain of slow lookup is: class — parent — root –nil

  • For a class method, that is, looking in a metaclass, the chain of slow looking superclasses is: metaclass — root metaclass — root class –nil

  • If neither a fast lookup nor a slow lookup finds a method implementation, dynamic method resolution is attempted

  • If the dynamic method resolution is still not found, the message is forwarded

Common methods are not implemented error source

If no implementation is found in the fast find, slow find, and method resolution processes, message forwarding is used, and the process is as follows

Message forwarding is implemented

  • Where _objc_msgForward_impcache is an assembly implementation, it jumps to__objc_msgForwardAt its core__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
  • In the assembly implementation__objc_forward_handlerIs not found, remove an underscore from the source code to search globally_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, it’s one of the most common mistakes we make in everyday development: failing to implement a function, running a program, and crashing.