This is the first day of my participation in the August Challenge. For details, see:August is more challenging

Slow lookup of messages_objc_msgSend_uncached

Since we entered fast search for the first time in the last chapter, it entered slow search for _objc_msgSend_uncached after we failed to find a method.

incacheIn abucket_tIf all the caches can not be hit, the next step is to enter the slow lookup process of the message, that is, byassemblySearch – >C/C++Code lookup.

A diagram of the slow lookup process:

This method is passed to CacheLookup as a parameter. If CacheLookup fails to find imp, MissLabelDynamic will be executed. __objc_msgSend_uncached.

Graph TB subgraph [__lookUpImpOrForward] -- > B C + + language [getMethodNoSuper_nolock] - > [findMethodInSortedMethodList] -- > C F[__objc_msgSend] --> G[CacheLookUp] --> F[__objc_msgSend] --> G[CacheLookUp] --> | can't hit the cache | H [__objc_msgSend_uncached] - > [MethodTableLookup] -- > I J [TailCallFunctionPointer x7] end I -. - > | | A concrete implementation process

Slow to find__objc_msgSend_uncachedThe process of:

  • 1 in CacheLookup assembly, when cache cannot be found, MissLabelDynamic will be executed, that is __objc_msgSend_uncached

  • __objC_msgSend_cached in 2 compilation will execute MethodTableLookup and TailCallFunctionPointer x17

  • 3. Execute four instructions on x16 saving class address to x2, assign value #3 to x3, jump to the lookUpImpOrForward method in c++ source code, move x0 to x17

    • For (unsigned attempts = unreasonableClassCount();;)

    • ② Add thread lock, enter binary search method

    • (3) If log_and_fill_cache is found, the imp will be inserted into the cache, and the next objc_msg_Send will do a quick lookup

    • ④ If you can’t find it, go up the search chain through ISA: Shared cache -> methodList -> Superclass -> NSObject -> nil -> break out of the loop. If superclass=nil, imp = forward_IMP, enter the message forwarding process (next section).

  • 4 TailCallFunctionPointer X17, get the search result of the previous step will jump to register X17

__objc_msgSend_uncachedSource code analysis

Assembly source code:

STATIC_ENTRY __objc_msgSend_uncached
	UNWIND __objc_msgSend_uncached, FrameWithNoSaves
	
	// call the C++ code to perform the slow lookup process
	MethodTableLookup
	// Jump to register X17 and wait to assemble the logic
	TailCallFunctionPointer x17

END_ENTRY __objc_msgSend_uncached
Copy the code

MethodTableLookup

Save the information method, x0 is receiver, x1 is _cmd, that is sel, first x16 (LGPerson class) in register X2, 0x03 in register X3, and then jump to the critical method lookUpImpOrForward, The return value from this method is stored in the X0 register in assembly terms, so when lookUpImpOrForward completes, the return value x0 is stored in X17.

C++ source code:

.macro MethodTableLookup	
	SAVE_REGS MSGSEND

	// lookUpImpOrForward(obj, sel, cls, behavior)
	// receiver and selector already in x0 and x1
	// The lookUpImpOrForward method takes four arguments:
	//obj = x0
	//sel = x1
	//cls = x2
	//behavior = x3 = 3
	mov	x2, x16
	mov	x3, #3
	//bl: jump instruction and store the way home in register X30 (LR)
	bl	_lookUpImpOrForward

	// The return value (IMP) from _lookUpImpOrForward will exist at x0
	// Assign x0 to x17
	mov	x17, x0

	RESTORE_REGS MSGSEND

.endmacro
Copy the code

TailCallFunctionPointer

//A12 + chip (support ARM64E)
#if __has_feature(ptrauth_calls)

// If the IMP is found through the slow lookup process, it will jump to register X17
// to provide for subsequent assembly to continue execution
.macro TailCallFunctionPointer
	// $0 indicates the parameter x17
	braaz	$0
.endmacro
#else
.macro TailCallFunctionPointer
	// $0 indicates the parameter x17
	br	$0
.endmacro
Copy the code

Conclusion:

The slow lookup process __objc_msgSend_uncached will execute 2 directives, MethodTableLookup will lookup and return IMP. TailCallFunctionPointer will jump to register x17, where imp is located. The slow lookup process will go to C++, return through register x0, and continue down assembly. The method lookup process will eventually jump to register x17 (either slow or fast lookup).

lookUpImpOrForward(Slow lookup process core)

lookUpimpOrForwardDiagram of the process:

Graph TD A1([" _objC_msgSend_cached "]) A2[" _objC_msgSend_cached "] A3["MethodTableLookup<br> 模 式 :obj,sel, CLS,behavior"] A["_lookUpImpOrForward"] B{"! CLS - > isInitialized () < br > class is initialized < br > "} D {" checkIsknownClass (CLS) < br > whether or not registered to < br > be LLDB loaded classes < br > "} C [" behaviour | = LOOKUP_NOCACHE < br > no cache method "] [" error Attempt to use unknown "] E E1 [" realizeAndInitializeIfNeeded_locked < br > such related parent metaclass recursive initialization "] F {" CLS - > isRealized () < br > class is implemented "} G [" realizeClassMaybeSwiftAndLeaveLocked < br > implementation class and isa walk a chain that is associated with inheritance chain class "] } I["initializeAndLeaveLocked "<br> <br> initializeAndLeaveLocked "] I1["curClass = CLS "] I1["curClass = CLS "]  I2{"for(unsigned attempts = unreasonableClassCount();;) < br > to iterate over class "} J {" curClass - > cache. IsConstantOptimizedCache < br > if there is a Shared cache, < br > is determined by _bucketsAndMaybeMask first, < br > 1 is a Shared cache "} J1["getMethodNoSuper_nolock"] J2["search_method_list_inline"] K["imp=cache_getImp<br GetMethodNoSuper_nolock <br> Binary query list "] M{" Imp exists "} N{" METH detected IMP"} S["done process "] S1{"(Behavior & LOOKUP_NOCACHE) == Whether can 0 < br > cache imp "} T [" curClass = curClass - > < br > cache. PreoptFallbackClass () "] R{"curClass=curClass->getSuperClass()<br> assign superclass to curClass<br>curClass == nil<br> check whether curClass is nil"} O [log_and_fill_cache "< br > insert cache"] O1 [" done_unlock process "] O2 {" ((behaviors & LOOKUP_NIL) && < br > imp = = forward_imp)) = = 1 < br > "} P["imp = forward_imp<br> break loop "] Q["imp = getimp (curClass, sel)<br> "] Q1["GetClassFromIsa_p16 p0, 0"] Q2[" LGetImpMissDynamic<br> "] V{"imp == forward_imp"} W1{"(behavior & } W["behavior ^= LOOKUP_RESOLVER;<br>imp=resolveMethod_locked<br> "] } X["return imp"] X1["return nil"] Z(["TailCallFunctionPointer x17"]) A1 --> A2 A2 --> A3 A3 - > - > B B - > | | D B - > whether | | C C > D D -- - > | | E1 is E1 > F D -- - > | no | E F - > whether | | G F - > is | | H H - > | | I H -- > is | | I1 I1 - > I2 I2 - > is | | J I2 - > whether | | W1 W1 - > is | | W W - > W2 W1 - > whether | | S J - > whether | | J1 J1 -- -- > J2 J2 > whether | | L L -- -- > Whether N N - > | | R R - > whether | | Q V - > is | | Y Y - > whether | | I2 V - > whether | | I2 J - > is | | K K > M M -- - > | | O1 is M - > whether | | T T -- -- > Q Q > Q1 Q1 -- > Q2 Q2 - > Q3 Q3 > V N -- -- > is | | S S1 - > is | | O O -- -- > O1 O1 O2 - > > O2 is | | X O2 - > whether | | X1 R - > is | | P P - > I2 Y -- > is | | S S -- -- -- -- > > S1 X Z

lookUpimpOrForwardSource code analysis

// Cache not found -lookupImporforward -slow methodList
// The assembly cache parameter is unknown
NEVER_INLINE
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    // Create forward_IMP and give the default value _objc_msgForward_impcache(in assembly objc-msg-arm64.s: jump to __objc_msgForward)
    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    // Create imp to receive IMP lookup through SEL
    IMP imp = nil;
    // Create the class to look for. This class will always change through the isa reference relationship.
    // Until it finally points to NSObject's superclass nil
    Class curClass;

    runtimeLock.assertUnlocked(a);if (slowpath(! cls->isInitialized())) {
        /** The first message sent to a class is usually +new or +alloc or +self. (behavior = 3 | 8 = 11) (behavior & LOOKUP_NOCACHE) == 0, 8 & 11 = 8) If the class is already initialized, we will not change the value of behavior, behavior=3, and our custom method will load normally into the cache. * /
        behavior |= LOOKUP_NOCACHE;
    }

    // runtimeLock is held during isRealized and isInitialized checks
    // Prevent competition with concurrent implementations.
    runtimeLock.lock(a);// Check whether the class is registered
    // Prevent man-made CFI attacks
    checkIsKnownClass(cls);

    /** initialize the CLS instance object in the ISA pointing diagram for each class (class and metaClass) so that it can't find methods in its own class and then look up in its parent class
    cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
    // runtimeLock may have been dropped but is now locked again
    runtimeLock.assertLocked(a);//curClass is the class of the current instance object
    curClass = cls;

    /** * loop through a methodList for a methodList object, using a methodList for a methodList object. Keep finding NSObject * if you can't find NSObject * eventually curClass will point to nil * assign the preprepared forward_IMP to IMP * and then end the slow lookup process, and then go to Runtime message forwarding */
    for (unsigned attempts = unreasonableClassCount();;) {
        if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
#if CONFIG_USE_PREOPT_CACHES
            /** * The first step is to find out if there is any method in the shared cache
            imp = cache_getImp(curClass, sel);
            if (imp) goto done_unlock;
            curClass = curClass->cache.preoptFallbackClass(a);#endif
        } else {
            /** * look in the list of methods in the current class, this is the focus * the search algorithm is dichotomy */
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {
                imp = meth->imp(false);
                goto done;
            }
            /** * If the current class is not found, take the methodList that points curClass to superclass * query the superclass until you find NSObject's superclass nil * assign the preprepared forward_IMP to IMP * and end the slow lookup process, Next we enter the Runtime message forwarding mechanism * to end the loop */
            if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
                imp = forward_imp;
                break; }}// Memory in the class list is corrupted
        if (slowpath(--attempts == 0)) {
            _objc_fatal("Memory corruption in class list.");
        }

        // Look in the cache of the parent class, here again enter the assembly lookup process
        imp = cache_getImp(curClass, sel);
        // If not found, assign the default forward_IMP to IMP
        if (slowpath(imp == forward_imp)) {
            // Found a forward:: entry in a superclass.
            // Stop searching, but don't cache yet; call method
            // resolver for this class first.
            break;
        }
        // If found
        if (fastpath(imp)) {
            // Insert the found method into the cache so that the next lookup uses the fast cache lookup
            gotodone; }}// No implementation found. Try method resolver once.

    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

// Find the IMP corresponding to sel and load the method into the cache
 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

realizeClassWithoutSwift

Only two lines of key source code are listed, representing recursive initializer classes and metaclasses

static Class realizeClassWithoutSwift(Class cls, Class previously)
{
    supercls = realizeClassWithoutSwift(remapClass(cls->getSuperclass()), nil);
    metacls = realizeClassWithoutSwift(remapClass(cls->ISA()), nil);
}
Copy the code

getMethodNoSuper_nolock(Binary search process)

static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
    runtimeLock.assertLocked(a);ASSERT(cls->isRealized());
    
    // Retrieve the methods() from CLS data()
    auto const methods = cls->data() - >methods(a);for (auto mlists = methods.beginLists(),
              end = methods.endLists(a); mlists ! = end; ++mlists) {// Go to the search_method_list_inline fix to an ordered list
        // Find the current sel from the list of methods
        // The custom methods in the class first go here, methods.beginLists()

        method_t *m = search_method_list_inline(*mlists, sel);
        if (m) return m;
    }

    return nil;
}
Copy the code

search_method_list_inline

Fixed the function that letters to the methodList become ordered

ALWAYS_INLINE static method_t *
search_method_list_inline(const method_list_t *mlist, SEL sel)
{
    int methodListIsFixedUp = mlist->isFixedUp(a);int methodListHasExpectedSize = mlist->isExpectedSize(a);if (fastpath(methodListIsFixedUp && methodListHasExpectedSize)) {
        return findMethodInSortedMethodList(sel, mlist);
    } else {
        // Linear search of unsorted method list
        if (auto *m = findMethodInUnsortedMethodList(sel, mlist))
            return m;
    }

    return nil;
}
Copy the code

findMethodInSortedMethodList(Sortedmethodlist)

IsSmallList is the computer of M1.

ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
    if (list->isSmallList()) {
        if (CONFIG_SHARED_CACHE_RELATIVE_DIRECT_SELECTORS && objc::inSharedCache((uintptr_t)list)) {
            return findMethodInSortedMethodList(key, list, [](method_t &m) { return m.getSmallNameAsSEL(a); }); }else {
            return findMethodInSortedMethodList(key, list, [](method_t &m) { return m.getSmallNameAsSELRef(); });
        }
    } else {
        return findMethodInSortedMethodList(key, list, [](method_t &m) { return m.big().name; }); }}Copy the code

FindMethodInSortedMethodList (binary search method to realize the real)

template<class getNameFunc>
ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list, const getNameFunc &getName)
{
    ASSERT(list);
    // Start position: 0
    auto first = list->begin(a);// Base also starts at 0
    auto base = first;
    / / the probe is 0
    decltype(first) probe;
    // To find sel for IMP
    uintptr_t keyValue = (uintptr_t)key;
    / / the number of the list
    uint32_t count;
    
    /** * Count =8 * to enter the loop, probe = base + (8 >> 1) = 0 + 4 = 4 *, then the first search range is 4-8, KeyValue > probeValue, base = probe + 1 = 4 + 1 = 5, Count -- = 7 * (count = 7 >> 1 = 3, probe = 5 + (3 >> 1) = 6) KeyValue > probeValue, base = probe + 1 = 6 + 1 = 7, count-- = 2 * Count = 2 >> 1 = 1, probe = 7 + (1 >> 1) = 7
    for(count = list->count; count ! =0; count >>= 1) {
        probe = base + (count >> 1);
        
        uintptr_t probeValue = (uintptr_t)getName(probe);
        
        if (keyValue == probeValue) {
            // Look ahead for the first IMP to avoid the problem of having the same classification method as the main class method
            // This is why the classification method is loaded
            while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
                probe--;
            }
            return &*probe;
        }
        
        if (keyValue > probeValue) {
            base = probe + 1; count--; }}return nil;
}
Copy the code

Log_and_fill_cache

If the logger allows it, the cache insert method is called to insert it into the cache, and the next lookup will be a quick cache lookup.

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
    cls->cache.insert(sel, imp, receiver);
}
Copy the code

Conclusion:

LookUpImpOrForward, which is a slow lookup process that attempts to find the IMP through an infinite loop, and on a global level, first look for the shared cache, then look for your own methodList, if you don’t have one, look for the parent, the parent doesn’t, look for NSObject, NSObject doesn’t, It’s going to point to nil and eventually it pops out. Process simplification: Share cache -> methodList -> superclass -> NSObject -> nil- > break out of loop

Binary search

Use C++ code to restore the dichotomy search, assuming that the dichotomy is looking for number 3

Case code:

#include <iostream>

using namespace std;

int main(int argc, const char  argv[]) {

    auto first = 0;
    auto base = first;
    decltype(first) probe = 0;
    uintptr_t keyValue = 3;
    uint32_t count;

     
    for (count = 8; count ! =0; count >>= 1) {
    
        cout << "Former = count."<< count << "---probe: " << probe << endl;
        //1. base = 0, count = 8, probe = 0 + (8 >> 1) = 4
        //2. base = 0, count = 8 >> 1 = 4, probe = 0 + (4 >> 1) = 2
        //3. base = 3, count = 3 >> 1 = 1, probe = 3 + (1 >> 1) = 3;
        probe = base + (count >> 1);
        cout << "After = count."<< count << "---probe: " << probe << endl;

        / / 1:3! Is equal to 4. I didn't find it
        / / 2:3! Is equal to 2. I can't find it
        //3: 3 == 3, found
        if (keyValue == probe) {

            cout << "Found =keyValue:" << keyValue << "---probe: " << probe << endl;
            return 0;
            
        }
        else{

            cout << "Not found =keyValue:" << keyValue << "---probe: " << probe << endl;

        }

       //1: 3 < 4, base = 0, count = 8;
       //2: 3 > 2, base = 2 + 1 = 3, count = 4 - 1 = 3;
        if (keyValue > probe) {
            base = probe + 1; count--; }}return 0;

}
Copy the code

Console print result:

before=count: 8---probe: 0

后=count: 8---probe: 4Did not find=keyValue: 3---probe: 4

前=count: 4---probe: 4

后=count: 4---probe: 2Did not find=keyValue: 3---probe: 2

前=count: 1---probe: 2

后=count: 1---probe: 3To find the=keyValue: 3---probe: 3

Program ended with exit code: 0
Copy the code

Conclusion:

Let’s assume that the corresponding sel to be searched is first count= list.count, here assume that count=8 enters the loop for the first time, probe = base + (8 >> 1) = 0 + 4 = 4

So the first search range is 4-8, the matching element position is 4, the judgment result is keyValue(3) < prebeValue(4), no match does not satisfy keyValue > probeValue, base = 0, count = 8;

Count = 8 >> 1 = 4, probe = 0 + (4 >> 1) = 2

The second search range is 1-4, the matching element position is 4, the judgment result is keyValue(3) > prebeValue(4), the mismatch is keyValue > probeValue, base = probe + 1 = 2 + 1 = 3, count– = 3

Count = 3 >> 1 = 1, probe = 3 + (1 >> 1) = 3

The third search for element 3, matches, returns IMP