IOS9 Slow search process

One, when to enter the slow search

The quick lookup process is cache lookup. If it is not found in the cache, the method slow lookup process will be entered

Second, __objc_msgSend_uncached

Search globally for STATIC_ENTRY __objc_msgSend_uncached in objC source code

Arm64 source code content

	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

Source code analysis: core parts also methodTable ELookup and TailCallFunctionPointer x17
MethodTableLookup calls c++ code to perform a slow lookup process
TailCallFunctionPointer x17 jump to register X17 with the result of the previous step

MethodTableLookup

Global search arm64 source code

.macro MethodTableLookup
	
	SAVE_REGS MSGSEND

	// lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
	// receiver and selector already in x0 and x1
	mov	x2, x16
	mov	x3, #3
	bl	_lookUpImpOrForward

	// IMP in x0
	mov	x17, x0

	RESTORE_REGS MSGSEND

.endmacro
Copy the code

What do we do with the source code

X16 = class assigns x2
3 is assigned to x3
Jump to _lookUpImpOrForward to look for IMP
Place the IMP found in X0 and assign x0 to X17

TailCallFunctionPointer

// The IMP is found through the slow search process, so it will jump to register X17
// to provide subsequent assembly to continue execution
.macro TailCallFunctionPointer
	// $0 = function pointer value
        // $0 represents the parameter x17
	braaz	$0
.endmacro

.macro TailCallFunctionPointer
	// $0 = function pointer value
	br	$0
.endmacro

Copy the code

Explore and learn

Quick Lookup processNo find will enterSlow search process
Slow search process__objc_msgSend_uncachedWill perform2MethodTableLookup to find and returnimp.TailCallFunctionPointerJump tox17The register, which is thetaimpRegister in which
The slow lookup process will enterC++, then returns through the X0 register, continues down in assembly, and the method lookup process eventually jumps to the X17 register (either slow or fast lookup)

lookUpImpOrForward

NEVER_INLINE
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
{
// create forward_imp and give Dimmer the value _objc_msgForward_impcache
    const IMP forward_imp = (IMP)_objc_msgForward_impcache;
    IMP imp = nil;// Create an IMP to receive an IMP from sel
    
    // Create the class to look for. This class is always changing through isa's pointing relationship.
    // until it ends up pointing to NSObject's parent class nil
    Class curClass;

    runtimeLock.assertUnlocked();

    if(slowpath(! cls->isInitialized())) {/** The first message sent to the class is usually +new or +alloc or +self but at this point the class has not been initialized, Behavior = 1, behavior = 1, LOOKUP_NOCACHE = 1, behavior = 1, LOOKUP_NOCACHE = 1, behavior = 1, LOOKUP_NOCACHE = 1, behavior = 1, LOOKUP_NOCACHE = 1, behavior = 1, LOOKUP_NOCACHE = 1, behavior = 1, LOOKUP_NOCACHE = 1, behavior = 1, LOOKUP_NOCACHE = 1 If the class is already initialized, behavior is not changed, behavior=3 and our custom method can be loaded into the cache. * /

        
        behavior |= LOOKUP_NOCACHE;
    }

// runtimeLock was held during checks by isRealized and isInitialized
// Prevent competing with concurrent implementations.
    runtimeLock.lock();

    // Check if the class is registered
    checkIsKnownClass(cls);

/** Initializes CLS instance objects in each class (class and metaClass) in the ISA pointing diagram so that subsequent classes cannot find methods in the parent class, so all related classes are initialized here */

    cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
  
  //runtimeLock may have been dropped but is now locked again
    runtimeLock.assertLocked();
    //curClass is the current instance object's class
    curClass = cls;

class_getInstanceMethod().

/** * Loops through the class object's methodList, looking for the parent if the current class doesn't have one Find all the way to the NSObject class * if NSObject isn't found * eventually curClass will point to nil * assign the prepared forward_IMP to IMP * and end the slow lookup process, and then go to the Runtime message forwarding mechanism */

    for (unsigned attempts = unreasonableClassCount();;) {
        if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
#if CONFIG_USE_PREOPT_CACHES
/** * The first step is to check if there are any methods in the shared cache. */ Usually our custom methods do not appear in the shared cache
            imp = cache_getImp(curClass, sel);
            if (imp) goto done_unlock;
            curClass = curClass->cache.preoptFallbackClass();
#endif
        } else {
           /** * search the list of methods in the current class, this is important * search algorithm is binary */
            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 * and query the parent until it finds NSObject's parent nil * assign the prepared forward_IMP to IMP * and end the slow lookup process, Next, the Runtime message forwarding mechanism completes the loop 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 it up in the cache of the parent class
        imp = cache_getImp(curClass, sel);
        // If not found, the default forward_IMP is assigned to imp
        if (slowpath(imp == forward_imp)) {
            break;
        }
        // If found
        if (fastpath(imp)) {
            // Insert the found method into the cache for the next lookup to use the fast cache lookup
            gotodone; }}// No implementation was found. Try the method resolver once.
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
        behavior ^= LOOKUP_RESOLVER;
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

// find sel imp, load method into cache
 done:
    if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) {
#if CONFIG_USE_PREOPT_CACHES
        while (cls->cache.isConstantOptimizedCache(/* strict */true)) {
            cls = cls->cache.preoptFallbackClass();
        }
#endif
        log_and_fill_cache(cls, imp, sel, inst, curClass);
    }
 done_unlock:
    runtimeLock.unlock();
    if (slowpath((behavior & LOOKUP_NIL) && imp == forward_imp)) {
        return nil;
    }
    return imp;
}
Copy the code

Binary lookup process (getMethodNoSuper_nolock)

static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
    runtimeLock.assertLocked();

    ASSERT(cls->isRealized());
    
    // Get methodList, which may be a two-dimensional array because of the data type
    // The loop condition is that the array is not empty, i.e. the start position is not equal to the end position
    auto const methods = cls->data()->methods();
    for(auto mlists = methods.beginLists(), end = methods.endLists(); mlists ! = end; ++mlists) {// go to search_method_list_inline and fix to an ordered list
        method_t *m = search_method_list_inline(*mlists, sel);
        if (m) return m;
    }

    return nil;
}
Copy the code

Fix function (search_method_list_inline)

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

#if DEBUG
    // sanity-check negative results
    if (mlist->isFixedUp()) {
        for (auto& meth : *mlist) {
            if (meth.name() == sel) {
                _objc_fatal("linear search worked when binary search did not"); }}}#endif

    return nil;
}
Copy the code

Binary search (findMethodInSortedMethodList)

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) { returnm.getSmallNameAsSELRef(); }); }}else {
        return findMethodInSortedMethodList(key, list, [](method_t &m) { returnm.big().name; }); }}Copy the code

Binary search is really implemented

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();
    // Base starts with 0
    auto base = first;
    / / the probe is 0
    decltype(first) probe;
    // select sel for imp
    uintptr_t keyValue = (uintptr_t)key;
    / / the number of the list
    uint32_t count;
    
  
  /** dichotomy logic works in a lot of places, it can greatly reduce the number of look-ups so let's say we're going to draw numbers from 1 to 10,000 and one of them is a winning number and we're going to draw a lottery and the stupid way to draw is to start at 1 and if you don't get to 2 and so on until the dichotomy is to start at 10,000/2 = 5,000, If you win the lottery and you don't win the lottery, someone will tell you whether your number is too big or too small. If it's too big, the next drawing number will be 0+5000/2 = 2500. If it's too small, the next drawing number will be 5000+5000/2 = 7500. We can save a lot of unnecessary times, quickly draw the big prize, is really a happy thing */
  
    for(count = list->count; count ! =0; count >>= 1) {
        probe = base + (count >> 1);
        
        uintptr_t probeValue = (uintptr_t)getName(probe);
        
        if (keyValue == probeValue) {
        // Find the first occurrence of the IMP, to avoid the classification method is the same as the main class method problem
        // 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 source lottery imitation

        auto first = 0;
        auto base = first;
        decltype(first) probe = 0;
        
        uintptr_t keyValue = 8888;
        uint32_t count;
        uint32_t current = 1;
        
        for (count = 10000; count ! =0; count >>= 1) {
            
            probe = base + (count >> 1);
            NSLog(@" lucky draw % D -- The lucky draw number is % D",current,probe);
            
            if (keyValue == probe) {
                NSLog("Congratulations on winning the lottery. The winning number is % D",probe);
                break;
            }
            else{
                NSLog("Didn't win!! Keep up the good work.");
            }
            
            if (keyValue > probe) {
                base = probe + 1;
                count--;
            }
            current += 1;
            
        }
Copy the code

Lottery results

Slow search process`lookUpImpOrForward`Once you find the IMP, you call log_and_fill_cache.

If the logger allows it, the cache’s 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

LookUpImpOrForward, which is a slow lookup process,
Search continuously by dichotomyimp.
For the global, go firstShared cache.
Then look up yoursmethodListIf you don’t have one, find oneThe parent classThere is no parent classNSObject.
NSObject doesn’t, it points tonil“And finally jumped out.
General process:Shared cache -> methodList -> The parent class -> NSObject -> nil – >Jump out of the loop

One, when to enter the slow search

Second, __objc_msgSend_uncached

MethodTableLookup

TailCallFunctionPointer

Explore and learn

lookUpImpOrForward

Binary lookup process (getMethodNoSuper_nolock)

Fix function (search_method_list_inline)

Binary search (findMethodInSortedMethodList)

Binary search is really implemented

Slow search processlookUpImpOrForwardOnce you find the IMP, you call log_and_fill_cache.

Related Posts

Debug – iOS 14 ImageIO Crash analysis

IOS breaks the sandbox to handle files like Office from other apps (upload, download, preview)

Record Tencent spring 2018 intern recruitment interview experience (Offer)

Slow search process`lookUpImpOrForward`Once you find the IMP, you call log_and_fill_cache.