What can be gained from this article

  • Assembly to source execution flow
  • __objc_msgsend_cached (Cause of slow lookup process)
  • Why do you want to go through a slow lookup process and use assembly all the time for a quick lookup?
  • Why is the quick lookup cache written in assembly instead of C++?
  • What does MethodTableLookup do?
  • TailCallFunctionPointer
  • LookUpImpOrForward (Slow lookup process core decomposition)
  • What did you do before you walked through methodList?
  • FindMethodInSortedMethodList dichotomy analysis
  • Dichotomy to find Demo
  • Dichotomy search diagram
  • Message slow lookup flow chart

The slow search of the message explores the cause

In the process of searching for a bucket_t in the cache, if all the ccache can not find the bucket_t, the next step is to enter the slow lookup process of the message, that is, by assembly lookup -> C/C++ code lookup.

Assembly to source execution flow

  • Step 1: In CacheLookup, when the cache is not hit, MissLabelDynamic, __objc_msgSend_uncached, is executed

  • Step 2: __objc_MSgSend_cached will execute MethodTableLookup and TailCallFunctionPointer x17

  • Step 3: MethodTableLookup executes four instructions, moving X16 to X2, #3 to X3, jump lookUpImpOrForward, and x0 to X17

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

  • Step 5: Lock and enter the dichotomy search

  • Step 6: If log_and_fill_cache is found, insert imp into the cache and perform a quick lookup next time

  • Step 7: If you can’t find it, go all the way 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.

An illustration of a slow lookup process to find an IMP and insert a cache:

__objc_msgsend_cached (Cause of slow lookup process)

Explore the source code with questions:

Why do you want to go through a slow lookup process and use assembly all the time for a quick lookup?

Why is the quick lookup cache written in assembly instead of C++?

__objc_msgSend_uncached

This method is passed to CacheLookup as a parameter. If CacheLookup fails to find IMP, MissLabelDynamic will be executed, that is, __objc_msgSend_uncached, and __cached. The method is very simple:

  • MethodTableLookup calls C++ code to execute a slow lookup process

  • TailCallFunctionPointer x17 takes the lookup result of the previous step and jumps to register X17

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

To save the information method, x0 is known as receiver, x1 is _cmd, that is sel, x16 (FFPerson class) is stored in register X2, 3 is stored 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.

.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:

  1. When the fast search process cannot be hit, the slow search process is entered

  2. The slow lookup process __objc_msgSend_uncached will execute two directives, MethodTableLookup will find and return IMP, and TailCallFunctionPointer will redirect to register X17, where IMP is located

  3. The slow lookup process will go into C++ and then return through the x0 register to continue down in assembly. The method lookup process will eventually jump to the x17 register (either slow or fast).

Conclusion Diagram:

LookUpImpOrForward (slow lookup process core)

NEVER_INLINE
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
    // Create forward_IMP and give the default value _objc_msgForward_impcache
    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
    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());

    // Get methodList, which may be a two-dimensional array because of the data type
    // If the array is not empty, the start position is not equal to the end position
    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
        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 (already sorted methodlist)

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

Dichotomy to find Demo

Demo 001- Dichotomy in practice

Case code:

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        // insert code here...
        
        auto first = 0;
        auto base = first;
        decltype(first) probe = 0;

        uintptr_t keyValue = 7;
        uint32_t count;
        
        for (count = 8; count ! =0; count >>= 1) {
            NSLog(@"Former = count: % u - the probe: % u",count,probe);
            probe = base + (count >> 1);
            NSLog(@"After = count: % u - the probe: % u",count,probe);
            
            if (keyValue == probe) {
                NSLog(@=keyValue:%lu-- probe:%u,keyValue,probe);
            }
            else{
                NSLog(@=keyValue:%lu-- probe:%u,keyValue,probe);
            }
            
            if (keyValue > probe) {
                base = probe + 1; count--; }}}return 0;
}
Copy the code

Console print result:

2021-07-02 04:06:34.275300+0800 001-binary practice [8192:538571] before =count:8-- probe:0 2021-07-02 04:06:34.276175+0800 After =count:8-- probe:4 2021-07-02 04:06:34.276236+0800 001-dichotomy practice [8192:538571] =keyValue:7-- probe:4 2021-07-02 04:06:42.015297+0800 001 -- binary practice [8192:538571] =count:3-- probe:4 2021-07-02 04:06:42.015397+0800 001-dichotomy practice [8192:538571] =count:3-- probe:6 2021-07-02 04:06:42.015442+0800 001-dichotomy practice [8192:538571] =keyValue:7-- probe:6 2021-07-02 04:06:43.917440+0800 001-binary practice [8192:538571] =count:1-- probe:6 2021-07-02 04:06:43.917615+0800 001-dichotomy practice [8192:538571] =count:1-- probe:7 2021-07-02 04:06:43.917669+0800 001-dichotomy practice [8192:538571] Found = keyValue: 7 - the probe: 7Copy the code

Dichotomy search diagram

Operation steps:

  • For example, suppose the sel you want to find is in the 7th place

  • First count= list.count, where count=8 is assumed

  • On the first entry into the loop, 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 (7) > prebeValue(4), no match

  • KeyValue > probeValue, base = probe + 1 = 4 + 1 = 5, count– = 7

  • Count = 7 >> 1 = 3, probe = 5 + 3 >> 1 = 6

  • The second search range is 6-7, the matching element position is 6, the judgment result is keyValue (7) > prebeValue(6), no match

  • KeyValue > probeValue, base = probe + 1 = 6 + 1 = 7, count– = 2

  • Count = 2 >> 1 = 1, probe = 7 + 1 >> 1 = 7

  • The third search for element 7, matches, returns IMP

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:Shared cache -> methodList -> The parent class -> NSObject -> nil – >Jump out of the loop

Message slow lookup flow chart

Method search process case description

Demo 002- Method call response chain practice

// Inherit: FFBoys -> FFPerson -> NSObject

int main(int argc, const char * argv[]) {
    @autoreleasepool {
        
        FFBoys *boys = [FFBoys alloc];
        
        // The FFBoys instance object calls its own instance method
        [boys prettyBoy];
        
        // The FFBoys class calls its own class methods
        [FFBoys gentelBoy];
        
        // An instance of FFBoys calls its own class methods in perform mode
        [boys performSelector:@selector(gentelBoy)];
        
        //FFBoys class objects perform to call their own instance methods
        [FFBoys performSelector:@selector(prettyBoy)];
        
        // The FFBoys instance object calls the instance method of the superclass
        [boys prettyPerson];
        
        // The FFBoys class object calls the class method of the parent class
        [FFBoys gentelPerson];
        
        // The instance object of FFBoys calls the class method of the parent class in perform mode
        [boys performSelector:@selector(gentelPerson)];
        
        // The class object of FFBoys calls the instance method of the parent class in perform mode
        [FFBoys performSelector:@selector(prettyPerson)];
        
        // The FFBoys instance object calls the instance method of the NSObject class
        [boys prettyGirls];
        
        // The FFBoys class object calls the class method of the NSobject class
        [FFBoys gentelGirls];
        
        // The instance object of FFBoy calls the class method of the NSObject class in perform mode
        [boys performSelector:@selector(gentelGirls)];
        
        // The class object of FFBoy calls the instance method of the NSObject class in Perform mode
        [FFBoys performSelector:@selector(prettyGirls)];
    }
    return 0;
}

Copy the code

Execute print result

2021-07-02 15:01:27.953803+0800 002- Method call Response Chain Practice [9520:713839] -[FFBoys prettyBoy] 2021-07-02 15:01:27.954179+0800 002- Method call response Chain practice [9520:713839] +[FFBoys gentelBoy] 2021-07-02 15:01:27.954462+0800 002- Method call response chain practice [9520:713839] -[FFPerson PrettyPerson] 2021-07-02 15:01:27.954509+0800 002- Method call Response Chain Practice [9520:713839] +[FFPerson gentelPerson] 2021-07-02 15:01:27.954549+0800 002- Method call Response Chain Practice [9520:713839] -[NSObject(FFGirls) prettyGirls] 2021-07-02 15:01:27.954689+0800 954821+0800 002- Method call response Chain Practice [9520:713839] +[NSObject(FFGirls) gentelGirls] 2021-07-02 15:01:27.954821+0800 002- Method call response chain practice [9520:713839] -[NSObject(FFGirls) prettyGirls]Copy the code

Conclusion:

  1. The class instance object boys can call the class instance method -[FFBoys prettyBoy], NSObject(FFGirls) prettyGirls; NSObject(FFGirls) prettyGirls;

  2. The class object FFBoys can call the class method of this class +[FFBoys gentelBoy], can call the class method of its parent class +[FFPerson gentelPerson], You can call the class method on NSObject +[NSObject(FFGirls) gentelGirls]

  3. [NSObject(FFGirls) prettyGirls] [NSObject(FFGirls) prettyGirls] [NSObject(FFGirls) prettyGirls]

  4. Class method +[FFBoys gentelBoy]; class method +[FFPerson gentelPerson]; class method +[NSObject(FFGirls); class method +[NSObject(FFGirls) gentelGirls]

  5. [FFBoys prettyBoy]; [FFPerson prettyPerson]; [NSObject(FFGirls); [NSObject(FFGirls); prettyGirls]

Answer questions raised in the process of source code exploration:

Why is the quick lookup cache written in assembly instead of C++?

Assembly is closer to machine language, execution efficiency is very fast, especially safe, this is the advantage. However, because the methods are special and many, the method of looking up the cache through the assembly can maximize the optimized execution efficiency of the program. In addition, assembly parameters can be unknown at the time of execution, which is different from C/C++. Parameters must be specified before the call. Another advantage of assembly is that it is more dynamic than C/C++.

Why do you want to go through a slow lookup process and use assembly all the time for a quick lookup?

Because I can’t find it in the cache anymore, so I’m in a slow lookup process, so I’m going to have to find a method, and I’m going to iterate through the methodList, through the ISA pointing relationship, and I can’t find it, and dad can’t find it, dad can’t find it, dad can’t find it, grandpa, and I’m going all the way up to nil. Because this process is time consuming, it is executed in C/C++.