IOS low-level exploration slow search

The cache could not find assembly analysis

MissLabelDynamic is the third parameter to CacheLookup in the assembly lookup flow:

       // NORMAL, _objc_msgSend, __objc_msgSend_uncached , MissLabelConstant
.macro CacheLookup Mode, Function, MissLabelDynamic, MissLabelConstant
Copy the code

Ached, and cached globally, in objC-msG-arm64.s

.endmacro

	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
	// Important information is in methodTable elookup
	MethodTableLookup
        // This is the call return
	TailCallFunctionPointer x17

	END_ENTRY __objc_msgSend_uncached
Copy the 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
        //IMP is the return value of _lookUpImpOrForward in x0
	mov	x17, x0

	RESTORE_REGS MSGSEND

.endmacro
Copy the code

Global lookup lookUpImpOrForward is found in objc-Runtime-new.mm:

// Slow search process
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
Copy the code

It’s c++. Why is the lookup cache written in a pool rather than c++?

Assembly is closer to machine language and the flow of execution is very fast
Assembly is more dynamic (parameters unknown),CThe language parameters must be fixed

Slow lookup lookUpImpOrForward analysis

NEVER_INLINE
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(a);// // Checks whether the class is initialized
     if (slowpath(! cls->isInitialized())) {
        behavior |= LOOKUP_NOCACHE;
    }
    
    // Lock to prevent multithreading
     runtimeLock.lock(a);// Check whether the class is known and registered in the current cache table
     checkIsKnownClass(cls); 
      // Initialize classes, parent classes, metaclasses (isa bitwise implementation)
     cls = realizeAndInitializeIfNeeded_locked(inst, cls, behavior & LOOKUP_INITIALIZE);
    // runtimeLock may have been dropped but is now locked again
    runtimeLock.assertLocked(a); curClass = cls;/ / death cycle
     for (unsigned attempts = unreasonableClassCount();;) {
        if (curClass->cache.isConstantOptimizedCache(/* strict */true)) {
            // Find the shared cache
#if CONFIG_USE_PREOPT_CACHES
            imp = cache_getImp(curClass, sel);
            if (imp) goto done_unlock;
            curClass = curClass->cache.preoptFallbackClass(a);#endif
        } else {
            // curClass method list.
            // List of lookup methods (binary lookup)
            Method meth = getMethodNoSuper_nolock(curClass, sel);
            if (meth) {
                imp = meth->imp(false);
                goto done;
            }
             // Current class = curClass->getSuperclass() The parent of the current class
 if (slowpath((curClass = curClass->getSuperclass()) == nil)) {
                // No implementation found, and method resolver didn't help.
                // Use forwarding.
                // Neither the parent nor the parent found the message forward
                imp = forward_imp;
                break; }}// Halt if there is a cycle in the superclass chain.
        if (slowpath(--attempts == 0)) {
            _objc_fatal("Memory corruption in class list.");
        }

        // Superclass cache.
         // This class is not found.
        imp = cache_getImp(curClass, sel);
        if (slowpath(imp == forward)) {
        // If the parent class returns a forward, stop the search and call the method
            // Found a forward:: entry in a superclass.
            // Stop searching, but don't cache yet; call method
            // resolver for this class first.
            break;
        }
        if (fastpath(imp)) {
            // Found the method in a superclass. Cache it in this class.
            gotodone; }}// No implementation found. Try method resolver once.
   // The method is not implemented. Try the method resolver once.
   // 3 &2 = 2
    if (slowpath(behavior & LOOKUP_RESOLVER)) {
    // behavior = 0
        behavior ^= LOOKUP_RESOLVER;
        // Dynamic method resolution
        return resolveMethod_locked(inst, sel, cls, behavior);
    }

 done:
    if (fastpath((behavior & LOOKUP_NOCACHE) == 0)) {
#if CONFIG_USE_PREOPT_CACHES
        while (cls->cache.isConstantOptimizedCache(/* strict */true)) {
            cls = cls->cache.preoptFallbackClass(a); }#endif
       // Cache population
        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

LookUpImpOrForward Slow lookup process:

checkIsKnownClassCheck whether the current class is a registered classAttempt to use unknown class
realizeAndInitializeIfNeeded_lockedInitializes the implementation of classes, superclasses, metaclasses, superclasses, etc.isaStep implementation)

For loop traversal:

Search the shared cache and return if found
If the shared cache is not found, search for the current class (binary search). If found, exit the loop and perform cache fill log_AND_fill_cache
If the parent of the current class is not found, the parent of the current class is found. If the parent of the current class is also found, the Memory corruption in the class list is reported.
If it finds it, it exits the loop and fills log_and_fill_cache. If it doesn’t find it, it looks for the parent (recursively) until curClass=nil. If it doesn’t find it, forward_IMP is assigned to IMP.
If the dynamic method resolution is not executed, it can be executed once. If it is not implemented, the message is forwarded.

Slow search flow chart

Cache_getImp analysis

cache_getImp(curClass, sel)

Global search cache_getImp in objc-msG-arm64.s:

STATIC_ENTRY _cache_getImp

	GetClassFromIsa_p16 p0, 0
	CacheLookup GETIMP, _cache_getImp, LGetImpMissDynamic, LGetImpMissConstant
Copy the code

becauseGetClassFromIsa_p16 p0, 0, sop0iscurClass.needs_auth= 0.Mov p16willcurClasstop16.then call

CacheLookup GETIMP, _cache_getImp, LGetImpMissDynamic, LGetImpMissConstant

Copy the code

The search process can be viewed in CacheLookup assembly analysis. If the cache is not found, just put 0 in p0 and return

LGetImpMissDynamic:
	mov	p0, #0
	ret
Copy the code

Binary search process

static method_t *
getMethodNoSuper_nolock(Class cls, SEL sel)
{
    runtimeLock.assertLocked(a);ASSERT(cls->isRealized());
    // fixme nil cls? 
    // fixme nil sel?

    // Get the list of methods
    auto const methods = cls->data() - >methods(a);// Two dimensional array storage method, start list, end list
    for (auto mlists = methods.beginLists(),
              end = methods.endLists(a); mlists ! = end; ++mlists) {// <rdar://problem/46904873> getMethodNoSuper_nolock is the hottest
        // caller of search_method_list, inlining it turns
        // getMethodNoSuper_nolock into a frame-less function and eliminates
        // any store from this codepath.
        // Binary search
        method_t *m = search_method_list_inline(*mlists, sel);
        if (m) return m;
    }

    return nil;
}

Copy the code

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); Omit some codeif (fastpath(methodListIsFixedUp && methodListHasExpectedSize)) {
    // A list of arranged methods
        return findMethodInSortedMethodList(sel, mlist);
    } else {
        // Linear search of unsorted method list
        if (auto *m = findMethodInUnsortedMethodList(sel, mlist))
            returnm; } omit some codereturn nil;
}
Copy the code

ALWAYS_INLINE static method_t *
findMethodInSortedMethodList(SEL key, const method_list_t *list)
{
    //M1 computer goes here
    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 {
        // Binary search
        return findMethodInSortedMethodList(key, list, [](method_t &m) { return m.big().name; }); }}Copy the code

Calling process: lookUpImpOrForward – > getMethodNoSuper_nolock – > search_method_list_inline – > findMethodInSortedMethodList

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

    auto first = list->begin(a);auto base = first;
    decltype(first) probe;

    uintptr_t keyValue = (uintptr_t)key;
    uint32_t count;
    // If count is 8 binary: 1000 move one bit right 0100 is 4 halved
    for(count = list->count; count ! =0; count >>= 1) {
        // Probe initialization is 0
        // probe = 0 + 4 = 4
        probe = base + (count >> 1);
        
        // Obtain the name using probe
        uintptr_t probeValue = (uintptr_t)getName(probe);
        
        // If the method is found
        if (keyValue == probeValue) {
            // `probe` is a match.
            // Rewind looking for the *first* occurrence of this value.
            // This is required for correct category overrides.
            // If the class has this method, call the class method
            while (probe > first && keyValue == (uintptr_t)getName((probe - 1))) {
                probe--;
            }
            / / return method_t
            return &*probe;
        }
        // If not found
        if (keyValue > probeValue) {
            //base = 4+1 = 5
            base = probe + 1;
            //count = 7, continue the loopcount--; }}return nil;
}
Copy the code

If count=8, the binary search logic at position 7 is as follows:

probe = base + (count >> 1), i.e.,probe = 0 + 4(8 >> 1) = 4
I didn’t find it becausekeyValue > probeValue, so the value should be at5to8Between,base = probe + 1, i.e.,base = 4 +1 = 5.
count --, i.e.,8 --.count = 7
count >>= 1, i.e.,7 >> 1 = 3 = count
probe = base + (count >> 1), i.e.,probe = 5 + 1(3 >> 1) = 6
The currentkeyValue > probeValueIt’s still true, so it should be at6to8Between,base = probe + 1, i.e.,base = 5 +1 = 6
count --, i.e.,3 -.count = 2
probe = base + (count >> 1), i.e.,probe = 6 + 1(2 >> 1) = 7
keyValue = probeValueFind the method, if the category has a method of the same name, return the classification method

IOS low-level exploration slow search

The cache could not find assembly analysis

Slow lookup lookUpImpOrForward analysis

Slow search flow chart

Cache_getImp analysis

Binary search process

Related Posts

The various flavors of dependency injection in Swift

Brief introduction to Swift Generic metaprogramming — Building a VFL helper library that is secure at compile time

The height of the iOS landscape keyboard is incorrect. Procedure