OC底层探索（十）：IMP快速查找-一一网

objc_msgSend到CacheLookup

调用方法[person say]
前面我们已经知道调用方法就是发送消息，底层调用的就是objc_msgSend(person, @selector(say))
查看 objc_msgSend汇编流程
然后通过isa&ISA_MASK找到class
然后在跳转找CacheLookup 缓存查找流程，通过sel找imp

CacheLookup, 通过sel查找imp

.macro CacheLookup Mode, Function, MissLabelDynamic, MissLabelConstant
//
// Restart protocol:
//
//   As soon as we're past the LLookupStart\Function label we may have
//   loaded an invalid cache pointer or mask.
//
//   When task_restartable_ranges_synchronize() is called,
//   (or when a signal hits us) before we're past LLookupEnd\Function,
//   then our PC will be reset to LLookupRecover\Function which forcefully
//   jumps to the cache-miss codepath which have the following
//   requirements:
//
//   GETIMP:
//     The cache-miss is just returning NULL (setting x0 to 0)
//
//   NORMAL and LOOKUP:
//   - x0 contains the receiver
//   - x1 contains the selector
//   - x16 contains the isa
//   - other registers are set as per calling conventions
//
// x15 = x16 = isa
mov	x15, x16			// stash the original isa x15 = x16 = isa
LLookupStart\Function: // 开始查找
// p1 = SEL, p16 = isa
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
ldr	p10, [x16, #CACHE]				// p10 = mask|buckets
lsr	p11, p10, #48			// p11 = mask
and	p10, p10, #0xffffffffffff	// p10 = buckets
and	w12, w1, w11			// x12 = _cmd & mask
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
// 真机 1dr = 栈中取值 p11 = [] 
//  X16 = isa  
//  #CACHE = 2 * __SIZEOF_POINTER__ = 16 
//  isa 16 得到 cache_t
//  p11 = [x16, #CACHE] = cache_t 
ldr	p11, [x16, #CACHE]			// p11 = mask|buckets
#if CONFIG_USE_PREOPT_CACHES
#if __has_feature(ptrauth_calls)
tbnz	p11, #0, LLookupPreopt\Function
and	p10, p11, #0x0000ffffffffffff
#else
// p11 = cache_t
// 0x0000fffffffffffe = bucketsMask
// p10 = p11 & 0x0000fffffffffffe = buckets
and	p10, p11, #0x0000fffffffffffe	// p10 = buckets  通过 maks 
// p11 != 0  则跳转
tbnz	p11, #0, LLookupPreopt\Function /
#endif
// p1 = SEL
// P12 = SEL ^ SEL >> 7
eor	p12, p1, p1, LSR #7 
// p11 = cache_t   
// mask = p11 >> 48
// p12 = p12 & mask
// p12 也就是 begin index，最开始查找的bucket的位置
and	p12, p12, p11, LSR #48		// x12 = (_cmd ^ (_cmd >> 7)) & mask,
#else
and	p10, p11, #0x0000ffffffffffff	// p10 = buckets
and	p12, p1, p11, LSR #48		// x12 = _cmd & mask  p12 = mask
#endif // CONFIG_USE_PREOPT_CACHES
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
ldr	p11, [x16, #CACHE]				// p11 = mask|buckets
and	p10, p11, #~0xf			// p10 = buckets
and	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
// p12 = begin, PTRSHIFT = 3
// p12 << 4 = begin * 16 多少个位
// p10 = buckets
// p13 = buckets +  begin * 16 = buckets[begin] = bucket
// p13 也就是 buckets 平移了 begin * 16 得到 bucket
// p13 是第一个bucket
add	p13, p10, p12, LSL #(1+PTRSHIFT) 
                                    // p13 = buckets + ((_cmd & mask) << (1+PTRSHIFT))

                                    // do {
//  #-BUCKET_SIZE = *bucket--
//  [x13] 是取bucket的值赋给 p17和p9
// bucket {imp, sel}, 
// 所以 p17 = imp, p9 = sel
1:	ldp	p17, p9, [x13], #-BUCKET_SIZE	//     {imp, sel} = *bucket--
// p1是目标的sel，也就是say
// 取到的 sel 与目标sel比较是否一样
cmp	p9, p1				//     if (sel != _cmd) {
// 不相等则走下面的 3
b.ne	3f				//         scan more
                                    //     } else {
// 如果相等 缓存命中跳转到 CacheHit
2:	CacheHit \Mode				// hit:    call or return imp
                                    //     }
// 判断当前sel是否为空，为空则走Miss,
3:	cbz	p9, \MissLabelDynamic		//     if (sel == 0) goto Miss;
// 在比较当前的 bucket 是否大于等于 首地址，直到找到首地址，结束循环
cmp	p13, p10			// } while (bucket >= buckets)
// 继续循环 1
b.hs	1b

// wrap-around:
//   p10 = first bucket
//   p11 = mask (and maybe other bits on LP64)
//   p12 = _cmd & mask
//
// A full cache can happen with CACHE_ALLOW_FULL_UTILIZATION.
// So stop when we circle back to the first probed bucket
// rather than when hitting the first bucket again.
//
// Note that we might probe the initial bucket twice
// when the first probed slot is the last entry.


#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
add	p13, p10, w11, UXTW #(1+PTRSHIFT)
                                    // p13 = buckets + (mask << 1+PTRSHIFT)
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
// p10 = buckets
// p11 = chache_t
// mask = chache_t << 48
// PTRSHIFT = 3
// p13 = buckets + (mask << 1+PTRSHIFT)
// p13 = buckets[mask],也就是最后一位的bucket
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
add	p13, p10, p11, LSL #(1+PTRSHIFT)
                                    // p13 = buckets + (mask << 1+PTRSHIFT)
#else
#error Unsupported cache mask storage for ARM64.
#endif
// p12 = begin
// p10 = buckets
// PTRSHIFT= 3
// p12 = p10 + p12 << 4
// p12 = buckets[begin], 第一个bucket
add	p12, p10, p12, LSL #(1+PTRSHIFT)
                                    // p12 = first probed bucket

                                    // do {
// p17(imp), p9(sel),  *bucket--                                   
4:	ldp	p17, p9, [x13], #-BUCKET_SIZE	//     {imp, sel} = *bucket--
// p9 = sel， 
// p1 = 目标 sel
// 如果 sel == 目标 sel
cmp	p9, p1				//     if (sel == _cmd)
// 调回到上面的第二步，也就是CacheHit， 缓存命中
b.eq	2b				//         goto hit
// 不相等，判断 sel 是否为空
// 并且 当前的 bukcet是不是比第一个 bucket的index 要大
// 不满足则结束循环
cmp	p9, #0				// } while (sel != 0 &&
ccmp	p13, p12, #0, ne		//     bucket > first_probed)
// 继续循环，走4
b.hi	4b
复制代码

通过x16 = isa,偏移#CACHE = 16，得到p11 = cache_t
通过p11 = cache_t与上bucketsMask(0x0000fffffffffffe)得到 p10 = buckets
通过 p11 = cache_t 与上mask （<< 48）的掩码得到mask
然后通过 p1 = SEL, p1 ^ p1 << 7 & mask的哈希算法得到第一个bucket的index (p12)
在通过p10 = buckets内存平移 p12 * 16个位，得到p13，也就是第一个bucket
在通过判断 *bucket--, bucket>=buckets,取 bucket
取出bucket中的sel和imp,用sel与p1, 进行比较
相等则缓存命中（CacheHit）
不相等则判断当前sel是否为空，不是空则继续循环
直到找第一个位置，结束循环
然后再将位置定位最后mask的位置
再创建一个循环，判断条件当前循环的 sel != 0，并且bucket大于开始的bucket(p12)
如果 sel == p1 ,缓存命中

CacheHit

// CacheHit: x17 = cached IMP, x10 = address of buckets, x1 = SEL, x16 = isa
.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
.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.
	AuthAndResignAsIMP x17, x10, x1, x16	// authenticate imp and re-sign as IMP
	cmp	x16, x15
	cinc	x16, x16, ne			// x16 += 1 when x15 != x16 (for instrumentation ; fallback to the parent class)
	ret				// return imp via x17
.else
.abort oops
.endif
.endmacro

.macro TailCallCachedImp
	// $0 = cached imp, $1 = address of cached imp, $2 = SEL, $3 = isa
	eor	$0, $0, $3
	br	$0
.endmacro
复制代码