IOS Low-level exploration: Slow lookup of methods

This is the 11th day of my participation in the August More Text Challenge. For details, see:August is more challenging

In the previous article, we introduced the fast lookup process for methods, the cache lookup, and then the slow lookup process for methods if they are not found in the cache. In the message quick lookup process, if the cache cannot be hit, the MissLabelDynamic process is entered. And MissLabelDynamic is __objc_msgSend_uncached when calling CacheLookup

1. Process exploration

In the objC4-818.2 source code, search for the keyword __objc_msgSend_uncached

In the objc-msg-arm64 file, find the relevant assembly code

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

• MethodTableLookupandTailCallFunctionPointerThe process is the core code

1.1 TailCallFunctionPointer

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

• $0Function address of
• $0For the callTailCallFunctionPointerWhen the incomingx17register
• It follows that,x17Store the address of the function in the callTailCallFunctionPointerHas existed before. soTailCallFunctionPointerIt’s not core code

1.2 MethodTableLookup

.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

• x17The value of thex0To provide andMethodTableLookupIs not directed atx0The assignment of
• In assembly,x0Register is used as the return value. So, in_lookUpImpOrForwardIn the function, it must existx0Register assignment

1.3 _lookUpImpOrForward

You can search for _lookUpImpOrForward in the source code and find no relevant code for this. You can set a symbolic breakpoint on the original entry __objc_msgSend_uncached and run the objc source code through assembly and dynamic debugging for clues. Goes to the break point for __objc_msgSend_uncached

• Of the calllookUpImpOrForwardFunction, and is not implemented in assembly code, butobjc-runtime-new.mmIn the fileC/C++function

Assembly and C/C++ calls to each other:

• C/C++When looking in assembly code, precede the method name with an underscore
• Call in assemblyC/C++Function,C/C++When looking in code, remove the first underscore of the method name

2. The search process is slow

2.1 C/C++code

In objc-Runtimenew.mm, find the implementation of lookUpImpOrForward

2.1.1 lookUpImpOrForward

NEVER_INLINE IMP lookUpImpOrForward(id inst, SEL sel, Class cls, Int behavior) {// define forward_imp const IMP forward_IMP = (IMP)_objc_msgForward_impcache; IMP imp = nil; Class curClass; runtimeLock.assertUnlocked(); if (slowpath(! cls->isInitialized())) { behavior |= LOOKUP_NOCACHE; } runtimeLock.lock(); CheckIsKnownClass (CLS); // Initialize the ro and Rw tables of the class // Initialize the superclass and metaclass of the class // Recursively, initialize all classes in the superclass chain until NSObject's superclass is nil // Purpose: Method used to find, when subclasses don't have the method, continue to search in the parent class CLS = realizeAndInitializeIfNeeded_locked (inst, CLS, behaviors & LOOKUP_INITIALIZE); runtimeLock.assertLocked(); curClass = cls; For (unsigned attempts = unreasonableClassCount();;) {// look in the shared cache, because of the multithreaded write method, At this time may find a way to not cache before the if (curClass - > cache. IsConstantOptimizedCache strict (/ * * / true)) {# if CONFIG_USE_PREOPT_CACHES imp = cache_getImp(curClass, sel); if (imp) goto done_unlock; curClass = curClass->cache.preoptFallbackClass(); #endif} else {meth = getMethodNoSuper_nolock(curClass, sel); If (meth) {// find imp, jump imp = meth-> IMP (false); goto done; If (slowPath ((curClass = curClass->getSuperclass()) == nil)) { Stop loop IMP = forward_IMP; break; } } if (slowpath(--attempts == 0)) { _objc_fatal("Memory corruption in class list."); } cache_getImp(curClass, sel) = cache_getImp(curClass, sel); If (slowpath(imp == forward_IMP)) {// if slowpath(imp == forward_IMP)) {// if slowpath(imp == forward_IMP); } if (fastpath(imp)) {// find imp from parent class goto done; Behavior ^= LOOKUP_RESOLVER; behavior ^= LOOKUP_RESOLVER; behavior ^= LOOKUP_RESOLVER; 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(); } #endif // Find imp, write cache, and loop 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

• clsWhether it is registered
  • Registered, continue code flow
  • Unregistered, incheckIsKnownClassError in function
• judgeclsThe implementation of the
  • The implementation classisaStep and parent chains
• judgeclsThe initialization
  • To prepareroandrwtable
  • Initializes the superclass and metaclass of the class
  • Recursively, initializing all classes in the parent class chain untilNSObjectThe parent classnil
  • Purpose: Used to find a method, when a subclass does not have the method, to continue the search in the superclass
• To find theimp
  • Endless loop, meet the conditions, passgotoorbreakJump out of the loop
• In the shared cache
  • Since multiple threads are writing methods, methods that were not previously cached may be found at this point
• In the current class
  • Look in the list of methods of the current class, using binary search
  • findimpJump,doneprocess
• Determine whether the parent class exists
  • If the superclass is empty,impThe assignment forforward_imp, the use ofbreakStop the loop and enter the dynamic method resolution process
• Look in the parent classimp
  • At this timecurClassforSuperclass
  • Perform a quick lookup process for the parent class
  • Look in the cache of the parent class,cache_getImpBy assembly code
  • findimpIf it is of the parent classforward_imp, the use ofbreakStop the loop and enter the dynamic method resolution process. Otherwise, jumpdoneprocess
  • Not foundimp, iterates over the parent class to continue the search
• Dynamic method resolution
  • In the current class and superclass, no method can be found, enter the dynamic method resolution process
  • Determines whether a method dynamic resolution has been executed
  • If not, implement method dynamic resolution
  • If a method dynamic resolution has been executed once, the message forwarding process is executed
• doneprocess
  • findimp, write to the cache, andcache_t::insertForm a closed loop

2.1.2 realizeAndInitializeIfNeeded_locked

static Class realizeAndInitializeIfNeeded_locked(id inst, Class cls, bool initialize) { runtimeLock.assertLocked(); / /! CLS ->isRealized() // Realized if (slowpath(!) cls->isRealized())) { cls = realizeClassMaybeSwiftAndLeaveLocked(cls, runtimeLock); } if (slowpath(initialize &&! cls->isInitialized())) { cls = initializeAndLeaveLocked(cls, inst, runtimeLock); } return cls; }Copy the code

• realizeClassMaybeSwiftAndLeaveLockedIn therealizeClassWithoutSwiftUsed to implement ISA walk and parent chain
• initializeAndLeaveLockedIn theinitializeNonMetaClassUsed for class initialization, preparationroandrwTable, and initializes the class’s parent class and metaclass

2.1.3 callInitialize

void callInitialize(Class cls) { 
    ((void(*)(Class, SEL))objc_msgSend)(cls, @selector(initialize)); asm(""); 
}
Copy the code

• In thecallInitialize, used to automatically send the initialize message when a class is initialized using objc_msgSend
• Developer useMethod Swizzle, can be in the classinitializeProceed in methodHOOKCompared to,loadMethod does not affect the start speed

2.1.4 getMethodNoSuper_nolock

static method_t * getMethodNoSuper_nolock(Class cls, SEL sel) { runtimeLock.assertLocked(); ASSERT(cls->isRealized()); auto const methods = cls->data()->methods(); for (auto mlists = methods.beginLists(), end = methods.endLists(); mlists ! = end; ++mlists) { method_t *m = search_method_list_inline(*mlists, sel); if (m) return m; } return nil; }Copy the code

• method_array_tandmethod_list_tBelongs to a two-dimensional array structure
• frommethod_array_tTo obtainmethod_list_t

2.1.5 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 { 
        if (auto *m = findMethodInUnsortedMethodList(sel, mlist)) return m; 
    } 
    return nil; 
}
Copy the code

• findMethodInSortedMethodList: Searches for the specified method in the sorted list of methods

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

• If it isM1Computer, enterisSmallListThe judgment. Otherwise enterelseProcess, using binary search, to find the specified method

2.1.7 Binary search

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(); auto base = first; decltype(first) probe; uintptr_t keyValue = (uintptr_t)key; uint32_t count; //base = low, probe = middle, count = Max //count >>= 1; count ! = 0; Count >>= 1) {base+count/2, middle probe = base+ (count >> 1); uintptr_t probeValue = (uintptr_t)getName(probe); If (keyValue == probeValue) {if (keyValue == probeValue) {if (keyValue == probeValue) {if (probeValue == probeValue) {if (probeValue == probeValue) {if (probeValue == probeValue) { Until probe is the beginning or probe-1 is not the method // Purpose: While (probe > first && keyValue == (uintptr_t)getName((probe-1))) {probe--; } return &*probe; If (keyValue > probeValue) {base = probe + 1; count--; } } return nil; }Copy the code

• Search procedure: The method numbers in the table are arranged in ascending order. Compare the method numbers recorded in the middle of the table with the method numbers to be searched. If they are equal, the search is successful. Otherwise, the middle position record is used to divide the table into the first and last two subtables. If the method number of the search is greater than the method number of the middle position record, the second subtable is further searched; otherwise, the former subtable is further searched. Repeat the process until you find a record that meets the criteria. At this point, the search is successful. Or until the child table does not exist, at which point the lookup is unsuccessful

2.2 Assembly Code

2.2.1 cache_getImp

If the imp is not found in the method list of the current class in the slow lookup process, the fast lookup process of the parent class is performed, calling cache_getImp and looking in the cache of the parent class

Cache_getImp is implemented in assembly. Find the code in the objc-msg-arm64.s file

    STATIC_ENTRY _cache_getImp 
    GetClassFromIsa_p16 p0, 0 
    CacheLookup GETIMP, _cache_getImp, LGetImpMissDynamic, LGetImpMissConstant 
    
LGetImpMissDynamic: 
    mov p0, #0 
    ret 
    
LGetImpMissConstant: 
    mov p0, p2 
    ret 
    
    END_ENTRY _cache_getImp
Copy the code

• The parent class enters the quick lookup process. The parameters passed are slightly different and do not enter__objc_msgSend_uncachedprocess

2.2.2 GetClassFromIsa_p16

.macro GetClassFromIsa_p16 src, needs_auth, auth_address /* note: auth_address is not required if ! needs_auth */ .if \needs_auth == 0 // _cache_getImp takes an authed class already mov p16, \src .else // 64-bit packed isa ExtractISA p16, \src, \auth_address .endif .endmacroCopy the code

• The arguments:
  • src:Superclass
  • needs_auth:0
  • auth_address: Parameter missing
• mov p16, \srcWill:srcOf, assign the valuep16register
  • p16Register: Stores class objects

2.2.3 CacheLookup

.macro CacheLookup Mode, Function, MissLabelDynamic, MissLabelConstant 
mov x15, x16 // stash the original isa
Copy the code

• The arguments:

  • Mode:GETIMP
  • Function:_cache_getImp
  • MissLabelDynamic:LGetImpMissDynamic
  • MissLabelConstant:LGetImpMissConstant

• Mov x15, x16: assign the value of register x16 to register x15

  • x15Register: Stores class objects

In CacheLookup, we miss the cache, enter the LGetImpMissDynamic process, assign #0 to the P0 register, which returns nil, and then return to lookUpImpOrForward, continuing the code in the for loop and the slow search process of the parent class

2.2.4 CacheHit

.macro CacheHit 
.if $0 == NORMAL 
    TailCallCachedImp x17, x10, x1, x16 // authenticate and call imp 
.elseif $0 == GETIMP 
    mov p0, p17 
    cbz p0, 9f // don't ptrauth a nil imp 
    AuthAndResignAsIMP x0, x10, x1, x16 // authenticate imp and re-sign as IMP 
9: ret // return IMP
Copy the code

• CacheHit: Cache matching process
• To viewModeIs equal to theGETIMPCode flow based on
• mov p0, p17Will:impThe assignmentp0register
• cbz p0, 9fIf:impNo, enterThe process of 9, the implementation ofretreturn0
• Otherwise,impExist, enterAuthAndResignAsIMPprocess

AuthAndResignAsIMP

.macro AuthAndResignAsIMP 
    // $0 = cached imp, $1 = address of cached imp, $2 = SEL 
    eor $0, $0, $3 
.endmacro
Copy the code

• eor $0, $0, $3: bitwise exclusior,imp = imp ^ cls, equivalent to decoding

In CacheHit, the cache is not hit, go to process 9, execute RET and return 0. Otherwise, enter the AuthAndResignAsIMP process, get the decoded IMP, and return

2.3 the flow chart