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

So we’ve looked at the essence of the method which is message sending, objc_msgSend, and today we’re going to look at the cached lookup logic in objc_msgSend. Objc_msgSend process

  • When receiver exists, the ISA of the message receiver is obtained
  • Using isa&ISA_MASK, we get the class object
  • Successfully get the class object, enter the CacheLookup process of CacheLookup, which is the so-called sel-imp quick lookup process

First, the fast lookup process, the method cache lookup, is implemented using assembly, the purpose is to improve efficiency. Because assembly code is closest to the solar language, storage space and execution time can be optimized to the greatest extent. Secondly, assembly code for dynamic parameters, variable parameters by better support.

1.CacheLookup to find the cache

1.1 Analysis of CacheLookup source code

//NORMAL, _objc_msgSend, __objc_msgSend_uncached .macro CacheLookup Mode, Function, MissLabelDynamic, MissLabelConstant // Requirements: // // Cache does not exist NULL, x0 set to 0 // GETIMP: // The cache-miss is just RETURNING NULL (setting x0 to 0) // - x0 contains the receiver // - x1 contains the selector // - x16 contains the isa // - other registers are set as Per Calling Conventions // // Calls p16 that store CLS, Mov x15, x16 // stash the original isa //_objc_msgSend LLookupStart\Function: // p1 = SEL, P16 = isa //arm64 64 OSX/SIMULATOR #if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS The first address is _bucketsAndMaybeMask LDR p10, [x16, # CACHE] / / p10 = mask | buckets / / LSR logic moves to the right p11 = _bucketsAndMaybeMask > > 48 is mask LSR p11, p10. P11 = mask //p10 = _bucketsAndMaybeMask & 0xffFFFFFFFF = buckets and p10, p10, p10 #0xffffffffffff // p10 = buckets //x12 = CMD & mask w1 W11 which is p11 which is performing the cache_hash. There is no >>7 bit operation and w12, w1, W11 // x12 = _cmd & mask //arm64 64 CACHE_MASK_STORAGE_HIGH_16 ldr p11, [x16, #CACHE] // p11 = mask|buckets //arm64 + iOS + ! #if __has_feature(ptrauth_calls) // The TBNZ test bit is not 0. Corresponds to TBZ. P11 If bit 0 is not 0, go to LLookupPreopt\Function. tbnz p11, #0, LLookupPreopt\Function //p10 = _bucketsAndMaybeMask & 0x0000ffffffffffff = buckets and p10, p11, #0x0000ffffffffffff // p10 = buckets #else //p10 = _bucketsAndMaybeMask & 0x0000fffffffffffe = buckets and p10, p11, P10 = buckets //p11 is not 0 TBNZ p11, #0, LLookupPreopt\Function #endif // eOR EOR{S}{cond} Rd, Rn, Operand2 //p12 = selector ^ (selector >> 7) LSR #7 //p12 = p&(_bucketsAndMaybeMask >> 48) = index & mask = sub-index and p12, p12, p11 LSR #48 // x12 = (_cmd ^ (_cmd >> 7)) & mask #else //p10 = _bucketsAndMaybeMask & 0x0000ffffffffffff = buckets and p10, p11, // p10 = buckets //p12 = selectors & (_bucketsAndMaybeMask >>48) = sel & mask = sub-index and p12, p1, p11, LSR #48 // x12 = _cmd & mask #endif // CONFIG_USE_PREOPT_CACHES //arm64 32 #elif CACHE_MASK_STORAGE == After CACHE_MASK_STORAGE_LOW_4 / / 4 for the number of mask front 0 case LDR p11, [x16, # CACHE] / / p11 = mask | buckets and p10, p11, And p11, p11, p11, #0xf // p11 = maskShift Mov p12, # 0xFFFF LSR p11, p12, p11 // p11 = mask = 0xFFFF >> p11 and p12, p1 P11 // x12 = _cmd & mask #else #error Unsupported cache mask storage for ARM64. #endif P11 = mask (arm64 is _bucketsAndMaybeMask), P12 = index // p13 (bucket_t) = buckets + index <<4 PTRSHIFT ARM64 = 3. Buckets + index *16 = buckets + index *16 I'm just going to shift it directly to the address of the element. // p13 = buckets + ((_cmd &mask) << (1+PTRSHIFT)) // p13 = buckets + ((_cmd &mask) << (1+PTRSHIFT)) // p13 = buckets + ((_cmd &mask) << (1+PTRSHIFT)) Do {//p17 = imp, p9 = sel 1: ldp p17, p9, [x13], #-BUCKET_SIZE // {imp, sel} = *bucket-- //sel - _cmd ! For __objc_msgSend_uncached CMP p9, p1 if (sel! = _cmd) {b.n3f // scan more //} else {// call imp, Mode = NORMAL 2: CacheHit \Mode // hit: Call or return IMP hit //} // __objc_msgSend_cached // \MissLabelDynamic 3: CBZ p9, \MissLabelDynamic // if (sel == 0) goto Miss; CMP p13, p10 // buckets = bucket // buckets = bucket // buckets = bucket // buckets = bucket // buckets = bucket // buckets = bucket // buckets = bucket // buckets = bucket // if the unsigned is greater than or equal to, go to 1:f b = front and back b. HSS 1b #if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS Shift to find bucket_t of the corresponding mask. Add p13, P10, W11 UXTW #(1+PTRSHIFT) // p13 = buckets + (mask << 1+PTRSHIFT) #elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16 //p13 Buckets + (mask >> 44) And you don't have to move to the left anymore. Add p13, p10, p11, LSR #(48 - (1+PTRSHIFT)) // p13 = buckets + (mask << 1+PTRSHIFT) // see comment about maskZeroBits #elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4 //p13 = buckets + (mask << 4) Find the bucket_t of the corresponding mask. add p13, p10, p11, LSL #(1+PTRSHIFT) // p13 = buckets + (mask << 1+PTRSHIFT) #else #error Unsupported cache mask storage for ARM64. #endif P12 = buckets + (p12<<4) index = bucket_t add p12, p10, p12, LSL #(1+PTRSHIFT) // p12 = first probed bucket // do {//p17 = imp p9 = sel 4: ldp p17, p9, [x13], #-BUCKET_SIZE // {imp, sel} = *bucket-- //sel - _cmd cmp p9, P1 // if (sel == _cmd) //sel == _cmd jump CacheHit b.q 2b // goto hit //sel! = nil cmp p9, #0 // } while (sel ! = 0 && // CCMP p13, p12, #0, ne // bucket > first_probed) LLookupRecover\Function: // Cache still not found, cache completely does not exist __objc_msgSend_uncached() b \MissLabelDynamicCopy the code

Core logic:

  • The index of SEL in buckets is found according to different architectures. P10 = buckets, P11 = mask / _bucketsAndMaybeMask (arm64_64 is _bucketsAndMaybeMask); P12 = index.

    • arm64_64In the case of if_bucketsAndMaybeMaskThe first0Bit is1executeLLookupPreopt\Function.

  • P13 = buckets + index << 4 Find the address of buckets corresponding to CLS, and translate the address to bucket_t

  • The do-while loop scans the first half of buckets[index] (the logic of the second half is not here).

    • If there isselIf the value is empty, it indicates that there is no cache__objc_msgSend_uncached().
    • Hit directlyCacheHit \ModeHere,ModeforNORMAL.

  • P13 = buckets[mask], the last element (the last element under ARM64 does not have its address, so it is equivalent to buckets[count-1]).

  • P13 = buckets + mask << 4 Locate the address of buckets corresponding to the mask, and translate the address to bucket_t

  • The do-while loop scans the elements preceding buckets[mask] up to index (not including index).

    • hitCacheHit \Mode
    • If there isselIf the value is null, there is no cache and the loop is terminated.

  • __objc_msgSend_uncached()

  1. CACHEiscache_tThe relativeisaThe deviation. #define CACHE (2 *SIZEOF_POINTER)
  2. maskZeroBitsIt is always4position0.p13 = buckets + (_bucketsAndMaybeMask >> 44)Moves to the right44You don’t have to< < 4To find the correspondingbucket_tThe address of. This is becausemaskZeroBitsinarm64_64The reason for the existence of.
  3. f bRepresent thefrontwithback“Down” means up.

Second, the LLookupPreopt \ Function

If bit 0 of _bucketsAndMaybeMask is 1 then LLookupPreopt\Function is executed in the arm64_64 real machine. A brief look at the assembly reveals that the _originalPreoptCache in cache_T is related.

2.1 LLookupPreopt\Function source analysis

LLookupPreopt\Function: #if __has_feature(ptrauth_calls) //p10 = _bucketsAndMaybeMask & 0x007ffffffffffffe = buckets and p10, p11, P10 = x //buckets x16 x16 // auth as early as possible #endif // x12 = (_cmd - first_shared_cache_sel) //(_cmd >> 12 + PAGE) << 12 + PAGEOFF First sel ADRP x9, _MagicSelRef@PAGE LDR p9, [x9, _MagicSelRef@PAGEOFF] p9 // w9 = ((_cmd - first_shared_cache_sel) >> hash_shift & hash_mask) #if __has_feature(ptrauth_calls) // bits 63.. 60 of x11 are the number of bits in hash_mask // bits 59.. 55 of x11 is hash_shift... lsr x17, x11, #55 // w17 = (hash_shift, ...) //w9 = index >> hash_shift lsr w9, w12, w17 // >>= shift //x17 = _bucketsAndMaybeMask >>60 //mask_bits lsr x17, x11, #60 // w17 = mask_bits mov x11, #0x7fff //x11 = 0x7fff >> mask_bits //mask lsr x11, x11, x17 // p11 = mask (0x7fff >> mask_bits) //x9 = x9 & mask and x9, x9, x11 // &= mask #else // bits 63.. 53 of x11 is hash_mask // bits 52.. 48 of x11 is hash_shift lsr x17, x11, #48 // w17 = (hash_shift, hash_mask) lsr w9, w12, w17 // >>= shift and x9, x9, x11, LSR #53 // &= mask #endif //x17 = el_offs | (imp_offs << 32) ldr x17, [x10, x9, LSL # 3] / / x17 = = sel_offs | (imp_offs < < 32) / / CMP x12 x17 whether find sel CMP x12, w17. uxtw .if \Mode == GETIMP b.ne \MissLabelConstant // cache miss //imp = isa - (sel_offs >> 32) sub x0, x16, x17, LSR #32 //imp = ISA-IMP_offs // Imp SignAsImp x0 ret. Else B.ne5f //imp (x17) = (ISA-SEL_offs >> 32) sub x17, x16, x17, LSR # 32 / / imp = isa - imp_offs. If \ Mode = = NORMAL / / jump imp. Br x17 elseif \ Mode = = LOOKUP / / x16 = isa | 3 / / here for or the meaning of ORR  x16, x16, #3 // for instrumentation, Note that we hit a constant cache // Register IMP SignAsImp x17 ret.else. Abort Unhandled Mode \ mode.endif //x9 = buckets-1 5: Ldursw x9, [x10, #-8] // offset -8 is the fallback offset X9 // compute the fallback isa // b LLookupStart\Function // lookup again with a new isa.endifCopy the code

  • Jump/return when imp is found.

  • Failed to find the next ISA to return to CacheLookup.

  • This incoming lookup shared cache is related to the _originalPreoptCache of cache_T. MaskZeroBits is used to determine whether _originalPreoptCache exists.

Third, CacheHit

A CacheHit is performed after looking for a CacheHit.

3.1 CacheHit source code analysis

#define NORMAL 0 #define GETIMP 1 #define LOOKUP 2 // CacheHit: x17 = cached IMP, x10 = address of buckets, x1 = SEL, If $0 == NORMAL // call IMP TailCallCachedImp(IMP,buckets,sel, ISA) If $0 == GETIMP // Return imp mov p0, P17 // IMP == nil jump 9: CBZ P0, 9f // don't ptrauth a nil IMP // Have IMP execute AuthAndResignAsIMP(IMP,buckets,sel, ISA) finally give back to X0. AuthAndResignAsIMP x0, x10, x1, x16 // authenticate imp and re-sign as IMP 9: ret // return IMP .elseif $0 == LOOKUP // No nil check for ptrauth: the caller would crash anyway when they // jump to a nil IMP. We don't care if that jump also fails ptrauth. Imp (IMP,buckets,sel,isa) AuthAndResignAsIMP x17 x10 x1 X16 // authenticate imp and re-sign as IMP //isa = CMP x16, x15 //cinc = x16+1 // x16 += 1 when x15! = x16 (for instrumentation ; fallback to the parent class) ret // return imp via x17 .else .abort oops .endif .endmacroCopy the code

  • The NORMAL case directly validates and jumps to imp.

  • TailCallCachedImp executes IMP ^ CLS internally and decodes imp.

  • GETIMP returns imp.

  • LOOKUP looks up registered IMP and returns.

Four, __objc_msgSend_uncached

__objc_msgSend_cached () will be cached if the cache does not hit:

STATIC_ENTRY __objc_msgSend_uncached UNWIND __objc_msgSend_uncached, // THIS IS NOT A CALLABLE C FUNCTION // out-of-band p15 IS the class to search // find imp MethodTableLookup // Jump IMP TailCallFunctionPointer x17 END_ENTRY __OBJC_MSgSend_cachedCopy the code
  • MethodTableLookupTo find theimp
  • TailCallFunctionPointerjumpimp

MethodTableLookup

.macro MethodTableLookup SAVE_REGS MSGSEND // lookUpImpOrForward(obj, sel, cls, LOOKUP_INITIALIZE | LOOKUP_RESOLVER) // receiver and selector already in x0 and x1 //x2 = cls mov x2, X16 / / x3 = LOOKUP_INITIALIZE | LOOKUP_RESOLVER / / whether the initialization, imp not implemented to try resolver //_lookUpImpOrForward(receiver,selector,cls,LOOKUP_INITIALIZE | LOOKUP_RESOLVER) mov x3, #3 bl _lookUpImpOrForward // IMP in x0 mov x17, x0 RESTORE_REGS MSGSEND .endmacroCopy the code
  • call_lookUpImpOrForwardTo find theimp. So this is calledc/c++Code for:
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
Copy the code

Will eventually call_lookUpImpOrForwardEnter thec/c++Environment logic.

Objc_msgSend Flow chart