preface

The Runimte Runtime & The Nature of Methods, the underlying principles of IOS, explores the fast lookup process of methods, which is the cache lookup. If not found in the cache, then the slow lookup process of methods will be entered. Explore the slow search process on this sunny summer day

The preparatory work

Iced 🍉
Objc4-818.2 – the source code

`objc_msgSend_uncached`

In the current class, cache lookup process if you don’t have to find the target method, jump MissLabelDynamic process MissLabelDynamic = __objc_msgSend_uncached, search __objc_msgSend_uncached and find the entrance, The real machine assembly code is as follows

    STATIC_ENTRY __objc_msgSend_uncached
    UNWIND __objc_msgSend_uncached, FrameWithNoSaves

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

    MethodTableLookup
    TailCallFunctionPointer x17

    END_ENTRY __objc_msgSend_uncached
Copy the code

A few simple lines of assembly code, the most important thing is MethodTableLookup and TailCallFunctionPointer x17, now we don’t know what X17 is, so let’s see what x17 does in TailCallFunctionPointer, The global search TailCallFunctionPointer code is as follows

    // A12 + iPhone X +
    #if __has_feature(ptrauth_calls).#else. .macro TailCallFunctionPointer// $0 = function pointer value
            br	$0
    .endmacro
    ...
    #endif
Copy the code

TailCallFunctionPointer is just one line of assembly code BR $0. $0 = p17; br $0 = p17; br $0 = p17; br $0 = P17; br $0 = P17; br $0 = P17 Guess p17 register should store IMP

The p17 register is not assigned to __objc_msgSend_uncached, so it can only be assigned to MethodTableLookup. The following code

.macro MethodTableLookup
	
    SAVE_REGS MSGSEND

    // lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
    // receiver and selector already in x0 and x1
    // x16 = class
    mov	x2, x16   
    // 3 is assigned to x3
    mov	x3, #3               
    // bl: b: jump l: link register // Before jump _lookUpImpOrForward,
    // Save the address of the next instruction in the LR register, i.e. save the address of the instruction (mov x17, x0) in the LR register
    // After _lookUpImpOrForwar, execute the address in the LR register
    bl	_lookUpImpOrForward   

    // The value of the first argument to x0 is stored in x0, and the return value of the method is also stored in x0, which should be the return value IMP of _lookUpImpOrForward
    // x0 is assigned to x17
    mov	x17, x0  

    RESTORE_REGS MSGSEND

.endmacro
Copy the code

_lookUpImpOrForward (import: import: import: import: import: import: import: import: import: import: import: import: import: import: import: import: import: import: import: import: import: import: import: import: import: import: import: import Global search lookUpImpOrForward

The return value of lookUpImpOrForward is IMP, and the question is: Why does the lookUpImpOrForward implementation use assembly?

Assembly is closer to machine language and queries are faster. The cache lookup process is to quickly find methods in the cache, while the slow lookup process is to iteratemethodlistThe process, the process is slow
Some of the parameters in a method are uncertain, but in C the parameters must be certain, and assembly makes you feel more dynamic

`objc_msgSend_uncached`conclusion

throughMethodTableLookupQuery will be queriedimpExists as a return valuex0Register, willx0Register value assigned tox17register
through TailCallFunctionPointer x17Direct callx17In registerimp
__objc_msgSend_uncached–> MethodTableLookup–> _lookUpImpOrForward –>TailCallFunctionPointer

`lookUpImpOrForward`

LookUpImpOrForward to query the imp based on sel

IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    / / define the message forwarding forward_imp / / behaviors of the incoming is 3 = LOOKUP_INITIALIZE | LOOKUP_RESOLVER
    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    IMP imp = nil;
    Class curClass;

    runtimeLock.assertUnlocked(a);/ * / / whether class initialization Uninitialized behaviors = LOOKUP_NOCACHE | LOOKUP_INITIALIZE | LOOKUP_RESOLVER / / the first message sent to the class is usually + new + alloc or + self will initialize class * /
    if (slowpath(! cls->isInitialized())) {
        behavior |= LOOKUP_NOCACHE;
    }

    // Lock to prevent multithreaded access disorder
    runtimeLock.lock(a);checkIsKnownClass(cls); // Whether to register class whether the class was loaded by dyld
    // The implementation class includes the parent class and metaclass that implement the ISA walk // the initializer class and parent class
    cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
     
    runtimeLock.assertLocked(a); curClass = cls;// After the lock is acquired, the code looks in the cache of the class again, but most of the time, the evidence is that most of the time the hit is missed, so time is wasted.
    // The only code path that doesn't perform some kind of cache lookup is class_getInstanceMethod().
    UnreasonableClassCount class iteration upper limit according to translation
    for (unsigned attempts = unreasonableClassCount();;) {
        // Determine whether there is a shared cache optimization, usually system methods such as NSLog, common methods will not go
        if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
            #if CONFIG_USE_PREOPT_CACHES
            /* Query the shared cache again, the purpose may be in your query process other threads may call this method to have the shared cache directly query */
            imp = cache_getImp(curClass, sel);// Query imp based on sel in cache
            // If imp exists, jump to done_UNLOCK process in cache
            if (imp) goto done_unlock;        
            // Retrieve the subclass from the subclass
            curClass = curClass->cache.preoptFallbackClass(a);#endif
        }
        else {
            // curClass method list.
            // Use binary search to find methodList in curClass
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {                // If a method corresponding to sel is found
                imp = meth->imp(false);// Obtain the imp
                goto done;             // Jump to the done process
            }
             CurClass = curClass->getSuperclass(); // curClass = curClass->getSuperclass()
            if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
                // if no sel is found in the loop, assign the value forward_IMP to imp
                imp = forward_imp; 
                break; }}// Halt if there is a cycle in the superclass chain.
        if (slowpath(--attempts == 0)) { // Stop if a loop exists in the parent class
            _objc_fatal("Memory corruption in class list.");
        }

        // Look for IMP in the parent class cache
        imp = cache_getImp(curClass, sel);
        if (slowpath(imp == forward_imp)) {
            // If the parent returns forward_IMP to stop looking, then break out of the loop
            break;
        }
        if (fastpath(imp)) {
            // If there is one in the cache, jump to the done process
            gotodone; }}// No implementation found. Try method resolver once.
    // If the query method is not implemented, the system will attempt method resolution once
    // behavior = 3 LOOKUP_RESOLVER = 2
    Behavior & LOOKUP_RESOLVER = 3 & 2 = 2
    Behavior = 1 & 2 = 0; behavior = 1 & 2 = 0
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        //behavior = behavior ^ LOOKUP_RESOLVER = 3 ^ 2 = 1
        behavior ^= LOOKUP_RESOLVER; 
        // Dynamic method resolution
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

 done:
    (behavior & LOOKUP_NOCACHE) == 0 behavior = 3
    (behavior & LOOKUP_NOCACHE) = 0
    if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) {
#if CONFIG_USE_PREOPT_CACHES
        while (cls->cache.isConstantOptimizedCache(/* strict */true)) {
            cls = cls->cache.preoptFallbackClass(a); }#endif
        // Insert sel and IMP into the cache
        log_and_fill_cache(cls, imp, sel, inst, curClass);
    }
 done_unlock:
    / / unlock
    runtimeLock.unlock(a);/* if (behavior & LOOKUP_NIL) is true = LOOKUP_NIL and IMP == forward_IMP does not query nil */
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
    return imp;
}
Copy the code

Slow search process

Whether to register the class, if no direct error
Whether to implementclsIf it is not implemented, implement it firstclassAnd relatedIsa a chainandIsa inheritance chainIn the class, the purpose is to find methods in the superclass to query
If the class is initialized, if it is not initialized, this step I think is to create a class object like when you call a class method, it’s the class object calling an instance method

CLS begins to traverse the query

Determine if there is a shared cache, so that it is possible that this method was called in the process of checking, if so, directly from the cache, and if there is no shared cache then start querying in this class
Binary search algorithm is used in the classmethodlistIf it is found inserted into the cache, the loop ends

Superclass cache

If a loop exists in the parent class, terminate the query and break out of the loop
At this timecurClass = superclass, to the cache of the parent class, if found, insert intoThis classIn the cache of. If the parent class returns aforward_impThe traversal jumps out and the message is forwarded
If this is not found in this classcurClass = superclassEnter andclsClass through the same lookup process untilcurClass = nil.imp = forward_impForwarding messages

Dynamic method resolution

ifclsAs well asThe parent classIn this case, the system will give you a chance to determine whether the dynamic method resolution has been executed. If not, the dynamic method resolution will be used
If the dynamic resolution method is executed,imp = forward_impWill godoneprocessInserted into the cacheWould go,done_unlockprocessreturn impThe message forwarding phase is entered

`lookUpImpOrForward`The flow chart

Implement and instantiate classes

static Class
realizeAndInitializeIfNeeded_locked(id inst, Class cls, bool initialize)
{
    runtimeLock.assertLocked(a);/ /! CLS ->isRealized() with low probability CLS ->isRealized() with high probability YES
    // Determine whether the class is intended to implement the ISA bitmap in the ISA bitmap and the superclass chain
    if (slowpath(! cls->isRealized())) {
        cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock);
        // runtimeLock may have been dropped but is now locked again
    }
    // Whether the class is initialized is not initialized first
    if (slowpath(initialize && ! cls->isInitialized())) {
        cls = initializeAndLeaveLocked(cls, inst, runtimeLock);
        // runtimeLock may have been dropped but is now locked again

        // If sel == initialize, class_initialize will send +initialize and
        // then the messenger will send +initialize again after this
        // procedure finishes. Of course, if this is not being called
        // from the messenger then it won't happen. 2778172
    }
    return cls;
    realizeClassWithoutSwift
}

Copy the code

realizeClassMaybeSwiftAndLeaveLockedIn the methodrealizeClassWithoutSwiftTo implement classesisaRelated classes in the bit chain and inheritance chain
initializeAndMaybeRelocktheinitializeNonMetaClassThat initializes the class and the superclass

Binary search algorithm

ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)
{
    ASSERT(list);

    auto first = list->begin(a);// The location of the first method
    auto base = first;
    decltype(first) probe;       // is equal to mid
    // Translate key to uintptr_t because the elements in the repaired method_list_t are sorted
    uintptr_t keyValue = (uintptr_t)key;
    uint32_t count;
    // Count = number of arrays (count >>= 1 = count = count >> 1)
    Count >> 1 = (count/2)
    //1. If count = list->count = 8 //2
    for(count = list->count; count ! =0; count >>= 1) {
        /* 1. Probe = base + 4 2. Intermediate probe = base (first address) + 6 */
        probe = base + (count >> 1);
        
        // Get sel in the middle, which is also strongly converted
        uintptr_t probeValue = (uintptr_t)getName(probe);
        if (keyValue == probeValue) {// If the target key == the middle key matches successfully
            // Overwrite a category. There are methods with the same name in a category. If there are methods with the same name, we get the methods of the category
            while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
                probe--;
            }
            // Return the address of the method
            return &*probe;
        }
        // If keyValue > the middle position of the value
        if (keyValue > probeValue) {
            /* 1. Base = probe + 1 = 4 + 1 = base (1) + 5 2. I'm going to move up by one */
            base = probe + 1;
            // 8 minus 1 is 7 because you missed it once and then you loopcount--; }}return nil;//查询完没找到返回nil
}
Copy the code

The methods in the method list are fixed, meaning that they are sorted by sel size

Binary search algorithmIt’s basically every time I find aIn the middleThe location andkeyValueCompare, return the method found if it is equal (of course return the classification method if there is one)
If they are not equal, the binary query is continued, and the scope of the query is narrowed continuously. If there is still no query, the query is returnednil

Binary search case

Note: KeyValue greater than probeValue algorithm and keyValue less than probeValue, count is a little different, you can appreciate the design of count, less than the algorithm count as the upper boundary, greater than the algorithm, the design of count is very clever, Instead of using it as the upper boundary, focus on probe

`cache_getImp`

Method quick lookup process is implemented in the assembler source code

STATIC_ENTRY _cache_getImp

GetClassFromIsa_p16 p0, 0
CacheLookup GETIMP, _cache_getImp, LGetImpMissDynamic, LGetImpMissConstant

LGetImpMissDynamic:
	mov	p0, #0
	ret
Copy the code

The GetClassFromIsa_p16 macro is defined as we started querying the caching method in this class, but with a different parameter needs_auth = 0

.macro GetClassFromIsa_p16 src, needs_auth, auth_address 
/* note: auth_address is not required if ! needs_auth */

#if SUPPORT_INDEXED_ISA  // armv7k or arm64_32./ / to omit
1:

#elif __LP64__
.if \needs_auth == 0 // _cache_getImp takes an authed class already
	mov	p16, \src
.else Needs_auth = 1
	// 64-bit packed isa
        // Pass the \ SRC and \auth_address into ExtractISA and assign the results to register p16
	ExtractISA p16, \src, \auth_address  
.endif
#else
	// 32-bit raw isa
	mov	p16, \src

#endif
Copy the code

Needs_auth ==0, p0=curClass. Assign the value of register P0 to register p16, p16= curClass

The CacheLookup method has been explored before and I won’t go into detail here CacheLookup GETIMP, _cache_getImp, LGetImpMissDynamic, LGetImpMissConstant

If the cache is not hitLGetImpMissDynamicprocess
If the cache hitsMode = GETIMP

LGetImpMissDynamic:
	mov	p0, #0
	ret
Copy the code

LGetImpMissDynamic p0 = 0, if no cache is found, imp = nil is returned

.macro CacheHit
.if $0 == NORMAL
	TailCallCachedImp x17, x10, x1, x16	// authenticate and call imp
.elseif $0 == GETIMP
	mov	p0, p17
	cbz	p0, 9f	 // If IMP = 0, go to 9 and return 0
	AuthAndResignAsIMP x0, x10, x1, x16	// authenticate imp and re-sign as IMP
9:	ret

Copy the code

p17 = imp,p17Register value assigned top0Register,x0 = p0 = imp
ifimp=0Jump straight9processreturn 0
AuthAndResignAsIMPIs also aThe macroforimpDecode it. Get the decodedimpreturn

.macro AuthAndResignAsIMP
	$0 = cache IMP, $1 = address. $2 = SEL $3 = class
        $0 = $0 ^ $3 = imp ^ class = imp
	eor	$0, $0, $3
.endmacro
Copy the code

Imp ^ class = the decoded IMP

Instance to find

Create a LWPerson class, declare a sayHello method, do not implement it

int main(int argc, char * argv[]) {
 
    @autoreleasepool {
        LWPerson * perosn  = [LWPerson alloc];
        [perosn sayHello];
 
    }
    return 0;
}
Copy the code

Unrecognized classic crash information, [PerOSN sayHello] also went through the fast search process, slow search process, dynamic method resolution, finally message forwarding, and finally failed to find the message unrecognized, Do a global search for doesNotRecognizeSelector or unrecognized Selector sent to instance in the source code

// Replaced by CF (throws an NSException)
+ (void)doesNotRecognizeSelector:(SEL)sel {
    _objc_fatal("+[%s %s]: unrecognized selector sent to instance %p".class_getName(self), sel_getName(sel), self);
}

// Replaced by CF (throws an NSException)
- (void)doesNotRecognizeSelector:(SEL)sel {
    _objc_fatal("-[%s %s]: unrecognized selector sent to instance %p".object_getClassName(self), sel_getName(sel), self);
}

__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);
}
Copy the code

How to call doesNotRecognizeSelector will be explained in detail later in the message forwarding phase

I’m going to create an NSObject+LW class and I’m going to add an object method called testData, and I’m going to implement it only in the class, and declare it in the LWPerson class

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        [LWPerson performSelector:@selector(testData) withObject:nil];
    }
    return 0;
}
Copy the code

2021- 06- 30 19:56:36.949645+0800 KCObjcBuild[1439:30359] NSObject
Copy the code

Why did the class call object method call succeed? There’s no instance method or class method underneath OC, getting a class method is actually getting an instance method on the metaclass, didn’t find the root class, didn’t find the root class, didn’t find the root class, and finally found NSObject so we can find the testData method

conclusion

The process of finding methods is actually quite complex. The method quick lookup process and the quick lookup process have now been explored, followed by dynamic method resolution, and the message forwarding process

mo4tech.com (Moment For Technology) is a global community with thousands techies from across the global hang out!Passionate technologists, be it gadget freaks, tech enthusiasts, coders, technopreneurs, or CIOs, you would find them all here.

IOS underlying principles of the method slow search process

preface

The preparatory work

`objc_msgSend_uncached`

`objc_msgSend_uncached`conclusion

`lookUpImpOrForward`

`lookUpImpOrForward`The flow chart

Implement and instantiate classes

Binary search algorithm

Binary search case

`cache_getImp`

Instance to find

conclusion

IOS underlying principles of the method slow search process

preface

The preparatory work

objc_msgSend_uncached

objc_msgSend_uncachedconclusion

lookUpImpOrForward

lookUpImpOrForwardThe flow chart

Implement and instantiate classes

Binary search algorithm

Binary search case

cache_getImp

Instance to find

conclusion

Related Posts

IOS App componentized development practice

IOS will generate two-dimensional code to scan and share pictures through LAN (wifi)

JavaScriptCore

`objc_msgSend_uncached`

`objc_msgSend_uncached`conclusion

`lookUpImpOrForward`

`lookUpImpOrForward`The flow chart

`cache_getImp`