底层原理-08-objc_msgSend之快速查找

1.objc_msgSend快速查找

之前我们进入源码大致看了下objc_msgSend汇编源码如下：

#endif

	ENTRY _objc_msgSend //方法传入会有接受者和方法名
	UNWIND _objc_msgSend, NoFrame

	cmp	p0, #0// 将接受者赋值给p0寄存器，同时判断接受者是否为0
        //如果是0进行下面的判断
        #if SUPPORT_TAGGED_POINTERS//是否支持target_pointers
	b.le	LNilOrTagged// 走下面的LNilOrTagged:方法
         #else
	b.eq	LReturnZero //走下面的LReturnZero:方法，发送一个空的方法
#endif
	ldr	p13, [x0] // 把接受者的首地址也就是isa赋值给p13， p13 = isa
	GetClassFromIsa_p16 p13, 1, x0	//通过这个方法拿到class 并赋值给 p16 = class，需要传入p13即 接收者的isa，1，以及接受者。
LGetIsaDone:
	// calls imp or objc_msgSend_uncached
	CacheLookup NORMAL, _objc_msgSend, __objc_msgSend_uncached//获取到isa的话，进行缓存查找，

#if SUPPORT_TAGGED_POINTERS
LNilOrTagged:
	b.eq	LReturnZero		// nil check 检查对象是否为0，为0的话直接返回发送一个空方法
	GetTaggedClass  //获取小端对象的类
	b	LGetIsaDone//获取isa
// SUPPORT_TAGGED_POINTERS
#endif

LReturnZero:
	// x0 is already zero
	mov	x1, #0
	movi	d0, #0
	movi	d1, #0
	movi	d2, #0
	movi	d3, #0
	ret

END_ENTRY _objc_msgSend//结束
复制代码

• 首先判断recevier是否为空，为空的话，判断是否支持小端，不支持的话直接返回空。
• 小端下，判断是否为负数，负数的话走LNilOrTagged方法。
• 进入LNilOrTagged后，判断小端，是否为空，为空的话返回空，不为空的话进入处理小端对象，获取isa
• recevier不为空的话，拿到isa，并通过GetClassFromIsa_p16 获取类的信息。在arm64架构下，通过isa & isa_mask 进行内存偏移 获取到shiftClass，拿到类的信息，并赋给P16；

1.1 GetClassFromIsa_p16

.macro GetClassFromIsa_p16 src, needs_auth, auth_address /* note: auth_address is not required if !needs_auth */

#if SUPPORT_INDEXED_ISA
	// Indexed isa
	mov	p16, \src// optimistically set dst = src，把isa的值存放在寄存器P16
	tbz	p16, #ISA_INDEX_IS_NPI_BIT, 1f	// 判断是否是纯的isa。done if not non-pointer isa
	// isa in p16 is indexed 索引
	adrp	x10, _objc_indexed_classes@PAGE// 把_objc_indexed_classes索引存入x10 寄存器
	add	x10, x10, _objc_indexed_classes@PAGEOFF // x10 = x10+ _objc_indexed_classes@PAGE 获取偏移 根据x10 进行内存偏移
	ubfx	p16, p16, #ISA_INDEX_SHIFT, #ISA_INDEX_BITS  //从p16的ISA_INDEX_SHIFT 到ISA_INDEX_BITS 位获取shiftclass 值 extract index
	ldr	p16, [x10, p16, UXTP #PTRSHIFT]	// load class from array
1:

#elif __LP64__ //64位系统
.if \needs_auth == 0 // _cache_getImp takes an authed class already
	mov	p16, \src //是否已经获取类类的isa，获取类直接赋值
.else
	// 64-bit packed isa
	ExtractISA p16, \src, \auth_address//p16 = isa &isa_mask (获取shiftClass）
.endif
#else
	// 32-bit raw isa
	mov	p16, \src 直接赋值p16 = isa

#endif
复制代码

• 主要通过isa进行内存偏移获取到shiftClass 信息，并吧shiftClass 值赋值给p16.至此类的isa查找完毕。

1.2CacheLookup查找

.macro CacheLookup Mode, Function, MissLabelDynamic, MissLabelConstant

	mov	x15, x16			// stash the original 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 //判断是否是小端模式，真机为小端模式
	ldr	p11, [x16, #CACHE]// p11 = mask|buckets 把isa 首地址偏移16个字节，之前我们知道类的内存地址isa- superclass- cache 这样排的，获取cache值要首地址即isa平移16个字节就可得到cache的地址。
  #if CONFIG_USE_PREOPT_CACHES //arm64真机
    #if __has_feature(ptrauth_calls) //A12芯片
	tbnz	p11, #0, LLookupPreopt\Function //p11测试位判断是否为0，为0条转 LLookupPreopt\Function
	and	p10, p11, #0x0000ffffffffffff // p11即cache_t &0x0000ffffffffffff 拿到buckets 赋值给p10,  p10 = buckets
   #else //A12以下
	and	p10, p11, #0x0000fffffffffffe	// p10 = buckets
	tbnz	p11, #0, LLookupPreopt\Function
   #endif
	eor	p12, p1, p1, LSR #7 //异或（判断2个值是否相同，相同为0不同为1），p12 = p1^(p1>>7) = _cmd^(_cmd>>7)
	and	p12, p12, p11, LSR #48//p11>>48 相当于 _bucketsAndMask >> 48 得到mask  p12 = (_cmd ^ (_cmd >> 7)) & mask 得到hash下的index，  x12 = (_cmd ^ (_cmd >> 7)) & mask
 #else 非arm64真机
	and	p10, p11, #0x0000ffffffffffff	// p10 = buckets
	and	p12, p1, p11, LSR #48		// x12 = _cmd & 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

复制代码

• 首先通过类的isa 进行偏移16个单位拿到cache_t,赋值给p11.
• 通过高位抹零得到buckets，赋值给p10.
• 对cache_t进行偏移得到_bucketsAndMaybeMask的地址,通过平移得到哈希算法下的index

// p10 = buckets首地址 ，p12 = index ,PTRSHIFT是3 一个buceet = sel（8字节）+imp（8字节）= 16字节， 通过首地址偏移获取bucket，存入p13
	add	p13, p10, p12, LSL #(1+PTRSHIFT)
						// p13 = buckets + ((_cmd & mask) << (1+PTRSHIFT))


						// do {
1:	ldp	p17, p9, [x13], #-BUCKET_SIZE	// 拿到bucket取出imp和sel{imp, sel} = *bucket--
	cmp	p9, p1				//比较是否不一样    if (sel != _cmd) {
	b.ne	3f				// 不一样继续查找        scan more
						//     } else {
2:	CacheHit \Mode				//  一样的找到imp hit:    call or return imp
						//     }
3:	cbz	p9, \MissLabelDynamic		//    如果一直找不到说明没有缓存，跳出去 if (sel == 0) goto Miss;
	cmp	p13, p10			// } 小于buckets数量 while (bucket >= buckets)
	b.hs	1b


复制代码

• 执行doWhile循环，从_cmd & mask 得到index 开始取bucket。判断是否有相等的sel=cmd有的话就找到返回imp。
• 如果一直找不到，跳出，进行慢速查找 __objc_msgSend_uncached
• 如果第一个bucket 是buckets的第一个元素则，把bucket设置为最后一个元素，进行后面的二次循环（ bucket > first_probed）
• 如果bucket不是buckets第一个则继续向前查找

#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
	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
	add	p12, p10, p12, LSL #(1+PTRSHIFT)//p10 = buckets,p12
						// p12 = first probed bucket

						// do {
4:	ldp	p17, p9, [x13], #-BUCKET_SIZE	//     {imp, sel} = *bucket--
	cmp	p9, p1				//     if (sel == _cmd)
	b.eq	2b				//         goto hit
	cmp	p9, #0				// } while (sel != 0 &&
	ccmp	p13, p12, #0, ne		//     bucket > first_probed)
	b.hi	4b //如果当前的bukect和p12(根据_cmd和mask 算出index 取出的bucket）相等直接接miss

LLookupEnd\Function:
LLookupRecover\Function:
	b	\MissLabelDynamic

复制代码

• 二次循环，和上面的dowhile循环一样，值得注意的是如果当前的第一个bukect和p12(根据_cmd和mask 算出index 取出的bucket）相等直接返回MissLabelDynamic

2.总结

1. 获取当前消息的接受者，进行判断是否存在，不支持小端模式直接返回空，支持的话进行小端模式获取isa
2. 获取isa后进行内存平移16个单位获取*cache_t,拿到buckets，根据_cmd和mask 获取哈希算法下的index。
3. 根据index取buckets里的bucket，bucket中的sel和_cmd比较，相等的话就找到了，不相等就进行递归*buckets-- 查找，直到bucket 等于buckets第一个元素。
4. 没找到的话进行二次递归，定位到buckets的最后一个元素，取出bucket，往前进行递归查找。如果当前的bukect和p12(根据_cmd和mask 算出index 取出的bucket）相等还没找到直接返回MissLabelDynamic走慢速查找

下面是一张大概的流程图