objc_msgSend 消息快速查找（cache查找）
2021-06-27 本文已影响0人
HotPotCat
上一篇文章分析了objc_msgSend的汇编实现，这边文章继续分析objc_msgSend中缓存的查找逻辑以及汇编代码是如何进入c/c++代码的。
一、CacheLookup 查找缓存
1.1 CacheLookup源码分析
传递的参数是NORMAL, _objc_msgSend, __objc_msgSend_uncached：
//NORMAL, _objc_msgSend, __objc_msgSend_uncached
.macro CacheLookup Mode, Function, MissLabelDynamic, MissLabelConstant
// requirements:
// //缓存不存在返回NULL，x0设置为0
// 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
//
//调用过来的p16存储的是cls，将cls存储在x15.
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
//isa->cache，首地址也就是_bucketsAndMaybeMask
ldr p10, [x16, #CACHE] // p10 = mask|buckets
//lsr逻辑右移 p11 = _bucketsAndMaybeMask >> 48 也就是 mask
lsr p11, p10, #48 // p11 = mask
//p10 = _bucketsAndMaybeMask & 0xffffffffffff = buckets（保留后48位）
and p10, p10, #0xffffffffffff // p10 = buckets
//x12 = cmd & mask w1为第二个参数cmd（self，cmd...），w11也就是p11 也就是执行cache_hash。这里没有>>7位的操作
and w12, w1, w11 // x12 = _cmd & mask
//arm64 64 真机这里p11计算后是_bucketsAndMaybeMask
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
ldr p11, [x16, #CACHE] // p11 = mask|buckets
//arm64 + iOS + !模拟器 + 非mac应用
#if CONFIG_USE_PREOPT_CACHES
//iphone 12以后指针验证
#if __has_feature(ptrauth_calls)
//tbnz 测试位不为0则跳转。与tbz对应。 p11 第0位不为0则跳转 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, #0x0000fffffffffffe // p10 = buckets
//p11 第0位不为0则跳转 LLookupPreopt\Function。
tbnz p11, #0, LLookupPreopt\Function
#endif
//eor 逻辑异或(^) 格式为：EOR{S}{cond} Rd, Rn, Operand2
//p12 = selector ^ (selector >> 7) select 右移7位&自己给到p12
eor p12, p1, p1, LSR #7
//p12 = p12 & (_bucketsAndMaybeMask >> 48) = index & mask值 = buckets中的下标
and p12, p12, p11, LSR #48 // x12 = (_cmd ^ (_cmd >> 7)) & mask
#else
//p10 = _bucketsAndMaybeMask & 0x0000ffffffffffff = buckets
and p10, p11, #0x0000ffffffffffff // p10 = buckets
//p12 = selector & (_bucketsAndMaybeMask >>48) = sel & mask = buckets中的下标
and p12, p1, p11, LSR #48 // x12 = _cmd & mask
#endif // CONFIG_USE_PREOPT_CACHES
//arm64 32
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
//后4位为mask前置0的个数的case
ldr p11, [x16, #CACHE] // p11 = mask|buckets
and p10, p11, #~0xf // p10 = buckets 相当于后4位置为0，取前32位
and p11, p11, #0xf // p11 = maskShift 取的是后4位，为mask前置位的0的个数
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
//通过上面的计算 p10 = buckets，p11 = mask（arm64真机是_bucketsAndMaybeMask）， p12 = index
// p13（bucket_t） = buckets + 下标 << 4 PTRSHIFT arm64 为3. <<4 位为16字节 buckets + 下标 *16 = buckets + index *16 也就是直接平移到了第几个元素的地址。
add p13, p10, p12, LSL #(1+PTRSHIFT)
// p13 = buckets + ((_cmd & mask) << (1+PTRSHIFT))
//这里就直接遍历查找了，因为arm64下cache_next相当于遍历（这里只扫描了前面）
// do {
//p17 = imp, p9 = sel
1: ldp p17, p9, [x13], #-BUCKET_SIZE // {imp, sel} = *bucket--
//sel - _cmd != 0 则跳转 3:，也就意味着没有找到就跳转到__objc_msgSend_uncached
cmp p9, p1 // if (sel != _cmd) {
b.ne 3f // scan more
// } else {
//找到则调用或者返回imp，Mode为 NORMAL
2: CacheHit \Mode // hit: call or return imp 命中
// }
//__objc_msgSend_uncached
//缓存中找不到方法就走__objc_msgSend_uncached逻辑了。
//cbz 为0跳转 sel == nil 跳转 \MissLabelDynamic
3: cbz p9, \MissLabelDynamic // if (sel == 0) goto Miss; 有空位没有找到说明没有缓存
//bucket_t - buckets 由于是递减操作
cmp p13, p10 // } while (bucket >= buckets) //⚠️ 这里一直是往前找，后面的元素在后面还有一次循环。
//无符号大于等于 则跳转1:f b 分别代表front与back
b.hs 1b
//没有命中cache 查找 p13 = mask对应的元素，也就是倒数第二个
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16_BIG_ADDRS
//p13 = buckets + (mask << 4) 平移找到对应mask的bucket_t。UXTW 将w11扩展为64位后左移4
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) 这里右移44位，少移动4位就不用再左移了。因为maskZeroBits的存在 就找到了mask对应元素的地址
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) 找到对应mask的bucket_t。
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
//之前已经往前查找过了，这里从后往index查找
// 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跳转CacheHit
b.eq 2b // goto hit
//sel ！= nil
cmp p9, #0 // } while (sel != 0 &&
//
ccmp p13, p12, #0, ne // bucket > first_probed)
//有值跳转4:
b.hi 4b
LLookupEnd\Function:
LLookupRecover\Function:
//仍然没有找到缓存，缓存彻底不存在 __objc_msgSend_uncached()
b \MissLabelDynamic
核心逻辑：
- 根据不同架构找到
buckets中sel对应的index，p10 = buckets，p11 = mask / _bucketsAndMaybeMask（arm64_64 是 _bucketsAndMaybeMask），p12 = index。-
arm64_64的情况下如果_bucketsAndMaybeMask第0位为1则执行LLookupPreopt\Function。
-
-
p13 = buckets + index << 4找到cls对应的buckets地址，地址平移找到对应bucket_t -
do-while循环扫描buckets[index]的前半部分（后半部分逻辑不在这里）。- 如果存在
sel为空，则说明是没有缓存的，就直接__objc_msgSend_uncached()。 - 命中直接
CacheHit \Mode，这里Mode为NORMAL。
- 如果存在
- 平移获得
p13 = buckets[mask]对应的元素，也就是最后一个元素（arm64下最后一个不存自身地址，也就相当于buckets[count - 1]）。 -
p13 = buckets + mask << 4找到mask对应的buckets地址，地址平移找到对应bucket_t -
do-while循环扫描buckets[mask]的前面元素，直到index（不包含index）。- 命中
CacheHit \Mode - 如果存在
sel为空，则说明是没有缓存的，就直接结束循环。
- 命中
- 最终仍然没有找到则执行
__objc_msgSend_uncached()
CACHE是cache_t相对isa的偏移。 #define CACHE (2 * __SIZEOF_POINTER__)maskZeroBits始终是4位0，p13 = buckets + (_bucketsAndMaybeMask >> 44)右移44位后就不用再<<4找到对应bucket_t的地址了。这是因为maskZeroBits在arm64_64下存在的原因。fb分别代表front与back，往下往上的意思。
1.2 CacheLookup 伪代码实现
//NORMAL, _objc_msgSend, __objc_msgSend_uncached
void CacheLookup(Mode,Function,MissLabelDynamic,MissLabelConstant) {
//1. 根据架构不同集算sel在buckets中的index
if (arm64_64 && OSX/SIMULATOR) {
p10 = isa->cache //_bucketsAndMaybeMask
p11 = _bucketsAndMaybeMask >> 48//mask
p10 = _bucketsAndMaybeMask & 0xffffffffffff//buckets
x12 = sel & mask //index 也就是执行cache_hash
} else if (arm64_64) {//真机 //这个分支下没有计算mask
p11 = isa->cache //_bucketsAndMaybeMask
if (arm64 + iOS + !模拟器 + 非mac应用) {
if (开启指针验证 ) {
if (_bucketsAndMaybeMask 第0位 ！= 0) {
goto LLookupPreopt\Function
} else {
p10 = _bucketsAndMaybeMask & 0x0000ffffffffffff//buckets
}
} else {
p10 = _bucketsAndMaybeMask & 0x0000fffffffffffe //buckets
if (_bucketsAndMaybeMask 第0位 ！= 0) {
goto LLookupPreopt\Function
}
}
//计算index
p12 = selector ^ (selector >> 7)
p12 = p12 & (_bucketsAndMaybeMask & 48) = p12 & mask//index
} else {
p10 = _bucketsAndMaybeMask & 0x0000ffffffffffff //buckets
p12 = selector & (_bucketsAndMaybeMask >>48) //index
}
} else if (arm64_32) {
p11 = _bucketsAndMaybeMask
p10 = _bucketsAndMaybeMask &（~0xf）//buckets 相当于后4位置为0，取前32位
p11 = _bucketsAndMaybeMask & 0xf //mask前置位0的个数
p11 = 0xffff >> p11 //获取到mask的值
x12 = selector & mask //index
} else {
#error Unsupported cache mask storage for ARM64.
}
//通过上面的计算 p10 = buckets，p11 = mask/_bucketsAndMaybeMask， p12 = index
p13 = buckets + index << 4 //找到cls对应的buckets地址。地址平移找到对应bucket_t。
//2.找缓存（这里只扫描了前面）
do {
p13 = *bucket-- //赋值后指向前一个bucket
p17 = bucket.imp
p9 = bucket.sel
if (p9 != selector) {
if (p9 == 0) {//说明没有缓存
__objc_msgSend_uncached()
}
} else {//缓存命中，走命中逻辑 call or return imp
CacheHit \Mode
}
} while(bucket >= buckets) //buckets是首地址，bucket是index对应的buckct往前移动
//查找完后还没有缓存？
//查找 p13 = mask对应的元素，也就是最后一个元素
if (arm64_64 && OSX/SIMULATOR) {
p13 = buckets + (mask << 4)
} else if (arm64_64) {//真机
p13 = buckets + (_bucketsAndMaybeMask >> 44)//这里右移44位，少移动4位就不用再左移了。这里就找到了对应index的bucket_t。
} else if (arm64_32) {
p13 = buckets + (mask << 4)
} else {
#error Unsupported cache mask storage for ARM64.
}
//index的bucket_t 从mask对应的buckets开始再往前找
p12 = buckets + (index<<4)
do {
p17 = imp;
p9 = sel;
*p13--;
if (p9 == selector) {//命中
CacheHit \Mode
}
} while (p9 != nil && bucket > p12)//从后往前 p9位nil则证明没有存，也就不存在缓存了。
//仍然没有找到缓存，缓存彻底不存在。
__objc_msgSend_uncached()
}
二、LLookupPreopt\Function
在arm64_64真机的情况下，如果_bucketsAndMaybeMask的第0位为1则会执行LLookupPreopt\Function的逻辑。简单看了下汇编发现与cache_t 中的_originalPreoptCache有关。
2.1 LLookupPreopt\Function 源码分析
LLookupPreopt\Function:
#if __has_feature(ptrauth_calls)
//p10 = _bucketsAndMaybeMask & 0x007ffffffffffffe = buckets
and p10, p11, #0x007ffffffffffffe // p10 = x
//buckets x16为cls 验证
autdb x10, x16 // auth as early as possible
#endif
// x12 = (_cmd - first_shared_cache_sel)
//(_cmd >> 12 + PAGE) << 12 + PAGEOFF 第一个sel
adrp x9, _MagicSelRef@PAGE
ldr p9, [x9, _MagicSelRef@PAGEOFF]
//差值index
sub p12, p1, 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
// 取到 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 是否找到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.ne 5f // cache miss
//imp（x17） = (isa - sel_offs>> 32)
sub x17, x16, x17, LSR #32 // imp = isa - imp_offs
.if \Mode == NORMAL
//跳转imp
br x17
.elseif \Mode == LOOKUP
//x16 = isa | 3 //这里为或的意思
orr x16, x16, #3 // for instrumentation, note that we hit a constant cache
//注册imp
SignAsImp x17
ret
.else
.abort unhandled mode \Mode
.endif
//x9 = buckets-1
5: ldursw x9, [x10, #-8] // offset -8 is the fallback offset
//计算回调isa x16 = x16 + x9
add x16, x16, x9 // compute the fallback isa
//使用新isa重新查找缓存
b LLookupStart\Function // lookup again with a new isa
.endif
- 找到
imp就跳转/返回。 - 没有找到返回下一个
isa重新CacheLookup。 - 这块进入的查找共享缓存， 与
cache_t的_originalPreoptCache有关。maskZeroBits这4位就是用来判断是否有_originalPreoptCache的。
⚠️@TODO 真机调试的时候进不到这块流程，这块分析的还不是很透彻，后面再补充。
三、CacheHit
在查找缓存命中后会执行CacheHit。
3.1 CacheHit源码分析
#define NORMAL 0
#define GETIMP 1
#define LOOKUP 2
// CacheHit: x17 = cached IMP, x10 = address of buckets, x1 = SEL, x16 = isa
.macro CacheHit
//这里传入的为NORMAL
.if $0 == NORMAL
//调用imp TailCallCachedImp(imp,buckets,sel,isa)
TailCallCachedImp x17, x10, x1, x16 // authenticate and call imp
.elseif $0 == GETIMP
//返回imp
mov p0, p17
//imp == nil跳转9:
cbz p0, 9f // don't ptrauth a nil imp
//有imp执行AuthAndResignAsIMP(imp,buckets,sel,isa)最后给到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与x15比较
cmp x16, x15
//cinc如果相等 就将x16+1，否则就设成0.
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
- 这里其实走的是
NORMAL逻辑，NORMAL的case直接验证并且跳转imp。 -
TailCallCachedImp内部执行的是imp^cls，对imp进行了解码。 -
GETIMP返回imp。 -
LOOKUP查找注册imp并返回。
3.1 CacheHit伪代码实现
//x17 = cached IMP, x10 = address of buckets, x1 = SEL, x16 = isa
void CacheHit(Mode) {
if (Mode == NORMAL) {
//imp = imp^cls 解码
TailCallCachedImp x17, x10, x1, x16 // 解码跳转imp
} else if (Mode == GETIMP) {
p0 = IMP
if (p0 == nil) {
return
} else {
AuthAndResignAsIMP(imp,buckets,sel,isa)//resign cached imp as IMP
}
} else if (Mode == LOOKUP) {
AuthAndResignAsIMP(x17, buckets, sel, isa)//resign cached imp as IMP
if (isa == x15) {
x16 += 1
} else {
x16 = 0
}
} else {
.abort oops//报错
}
}
四、__objc_msgSend_uncached
在缓存没有命中的情况下会走到__objc_msgSend_uncached()的逻辑：
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
//查找imp
MethodTableLookup
//跳转imp
TailCallFunctionPointer x17
END_ENTRY __objc_msgSend_uncached
-
MethodTableLookup查找imp -
TailCallFunctionPointer跳转imp
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 //是否初始化,imp没有实现尝试resolver
//_lookUpImpOrForward(receiver,selector,cls,LOOKUP_INITIALIZE | LOOKUP_RESOLVER)
mov x3, #3
bl _lookUpImpOrForward
// IMP in x0
mov x17, x0
RESTORE_REGS MSGSEND
.endmacro
- 调用
_lookUpImpOrForward查找imp。这里就调用到了c/c++的代码了：
IMP lookUpImpOrForward(id inst, SEL sel, Class cls, int behavior)
最终会调用_lookUpImpOrForward进入c/c++环境逻辑。
对于架构的一些理解
LP64 //64位
x86_64 // interl 64位
i386 // intel 32位
arm // arm指令 32 位
arm64 //arm64指令
arm64 && LP64 //arm64 64位
arm64 && !LP64 //arm64 32 位
⚠️ 当然也可以通过真机跟踪汇编代码读取寄存器进行，与源码分析的是一致的，走其中的一个分支。
五、 objc_msgSend流程图
objc_msgSend流程图
总结
- 判断
receiver是否存在。 - 通过
isa获取cls。 -
cls内存平移0x10获取cache也就是_bucketsAndMaybeMask。 - 通过
buckets & bucketsMask获取buckets`地址。 - 通过
bucketsMask >> maskShift获取mask。 - 通过
sel & mask获取第一次查找的index。 -
buckets + index << 4找到index对应的地址。 -
do-while循环判断找缓存，这次从[index～0]查找imp。 - 取到
buckets[mask]继续do-while循环，从[mask~index)查找imp。两次查找过程中如果有sel为空则会结束查找。走__objc_msgSend_uncached的逻辑。 - 找到
imp就解码跳转imp。
