OC底层原理14-1：objc-msgSend缓存查找(快速查找)汇编分析

张建 lol
  2023-02-25 18:38:26 2023-02-25 18:38 Created   2023-05-29 19:41:11 2023-05-29 19:41 Updated      

前言

我们得出结论：消息发送objc-msgSend 内部先进行 快速查找 即 缓存（CacheLookup）查找

本文主要继上一章 objc_msgSend 引申，objc_msgSend 是用汇编写的，因为性能好、速度快

汇编的特性：快 + 动态性（不确定）

objc_msgSend 汇编查找流程分析

在 objc4-781源码 中，搜索 objc_msgSend，由于我们日常开发的都是架构 arm64，所以需要找到 objc-msgSend-arm64.s 文件， objc_msgSend 源码实现的入口是在 ENTRY _objc_msgSend 这个文件下，发现是 汇编实现。

  • objc_msgSend 汇编源码

objc_msgSend 是消息发送的源码的入口，其使用 汇编 实现的，_objc_msgSend 源码实现如下:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
// 消息发送 -> 汇编入口 -> _objc_msgSend主要是拿到接收者的isa信息
ENTRY _objc_msgSend
   // 无窗口
	UNWIND _objc_msgSend, NoFrame

   /* 
   p0和空对比，即判断receiver是否存在
   其中p0（消息接收者）是objc_msgSend的第一个参数
   */
	cmp	p0, #0			// nil check and tagged pointer check
// 是否支持 tagged pointers 小对象类型
#if SUPPORT_TAGGED_POINTERS
   // le-小于， 小对象或空判断
	b.le	LNilOrTagged		//  (MSB tagged pointer looks negative)
#else // 否则
   // eq-等于，p0等于0时，直接返回空
	b.eq	LReturnZero
#endif
   // p0即receiver肯定存在的流程
   // 根据对象拿出isa，即从x0寄存器指向的地址 取出 isa，存入p13寄存器
	ldr	p13, [x0]		// p13 = isa
   // 在ram64架构下通过 p16 = isa（p13）& ISA_MASK，拿出shiftcls信息，得到class信息
	GetClassFromIsa_p16 p13		// p16 = class
// 获取isa完毕
LGetIsaDone:
   // calls imp or objc_msgSend_uncached
   // 开启缓存查找流程，即快速查找流程
	CacheLookup NORMAL, _objc_msgSend

#if SUPPORT_TAGGED_POINTERS
// 小对象或者空判断
LNilOrTagged: 
         // 直接返回空
	b.eq	LReturnZero		// nil check

	// tagged
	adrp	x10, _objc_debug_taggedpointer_classes@PAGE
	add	x10, x10, _objc_debug_taggedpointer_classes@PAGEOFF
	ubfx	x11, x0, #60, #4
	ldr	x16, [x10, x11, LSL #3]
	adrp	x10, _OBJC_CLASS_$___NSUnrecognizedTaggedPointer@PAGE
	add	x10, x10, _OBJC_CLASS_$___NSUnrecognizedTaggedPointer@PAGEOFF
	cmp	x10, x16
	b.ne	LGetIsaDone

	// ext tagged
	adrp	x10, _objc_debug_taggedpointer_ext_classes@PAGE
	add	x10, x10, _objc_debug_taggedpointer_ext_classes@PAGEOFF
	ubfx	x11, x0, #52, #8
	ldr	x16, [x10, x11, LSL #3]
	b	LGetIsaDone
// 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

主要有以下几个步：

  • 【第一步】判断 objc_msgSend 方法的第一个参数 receiver 是否为空

    • 如果支持 tagged pointer 小对象，跳转至 LNilOrTagged

      • 如果 小对象 为空，则直接返回空，即 LReturnZero
      • 如果 小对象 不为空，则处理小对象的 isa，走到【第二步】

    • 如果 既不是小对象，receiver 也不为空，有以下两步

      • 从 receiver 中取出 isa 存入 p13 寄存器
      • 通过 GetClassFromIsa_p16 中，arm64 架构下通过 isa & ISA_MASK 获取 shiftcls 位域的类信息，即 class，GetClassFromIsa_p16 的汇编实现如下，然后走到【第二步】

  • 【第二步】如果获得 isa 指针

    • 如果有 isa，走到 CacheLookup，即缓存查找流程，也就是所谓的 sel-imp 快速查找流程
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
.macro GetClassFromIsa_p16 /* src */
// 此处用于watchOS
#if SUPPORT_INDEXED_ISA
	// Indexed isa
   // 将isa的值存入p16寄存器
	mov	p16, $0			// optimistically set dst = src
   // 判断是否是 non-pointer isa
	tbz	p16, #ISA_INDEX_IS_NPI_BIT, 1f	// done if not non-pointer isa
	// isa in p16 is indexed
   // 将_objc_indexed_classes 所在的页的基址 读入到x10寄存器
	adrp	x10, _objc_indexed_classes@PAGE
   // x10 = x10 + _objc_indexed(page中的偏移量) -x10基址根据偏移量进行内存偏移
	add	x10, x10, _objc_indexed_classes@PAGEOFF
   // 从p16的第ISA_INDEX_SHIFT位开始，提取 ISA_INDEX_BITS位到p16寄存器，剩余的高位用0补充
	ubfx	p16, p16, #ISA_INDEX_SHIFT, #ISA_INDEX_BITS  // extract index

	ldr	p16, [x10, p16, UXTP #PTRSHIFT]	// load class from array
1:

// 用于64位系统
#elif __LP64__
	// 64-bit packed isa
   // p16 = class = isa & ISA_MASK（位运算 & 即获取isa中的shiftcls信息）
	and	p16, $0, #ISA_MASK

#else
	// 32-bit raw isa
    // 用于32位系统
	mov	p16, $0

#endif

.endmacro

objc_msgSend 缓存（CacheLookup）查找汇编流程

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
.macro CacheLookup
	//
	// Restart protocol:
	//
	//   As soon as we're past the LLookupStart$1 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$1,
	//   then our PC will be reset to LLookupRecover$1 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
	//
LLookupStart$1:

	// p1 = SEL, p16 = isa，#define CACHE（2 * __SIZEOF_POINER__），其中__SIZEOF_POINTER__表示pointer的大小 ，即 2*8 = 16
   // p11 = mask | buckets，从x16（即isa）中平移16字节，取出cache存入p11寄存器，isa距离cache正好16字节：isa（8字节），superClass（8字节），cache（mask高16位 + buckets低48位）
	ldr	p11, [x16, #CACHE]			

// 64位真机
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
   // p11(cache) & 0x0000ffffffffffff ，mask高16位抹零，得到buckets 存入p10寄存器，即去掉mask，留下buckets
	and	p10, p11, #0x0000ffffffffffff // p10 = buckets
	
   /*
    1）先将p11(cache)右移48位，得到mask(即p11 存储mask)
    2）mask & p1（msgSend的第二个参数 cmd-sel），得到sel-imp的下表index(即搜索下标)
    3）存入p12(cache insert写入时的哈希下标计算是 通过 sel & mask，读取时也要用这种方式)
   */
	and	p12, p1, p11, LSR #48		// x12 = _cmd & mask
	
// 非64位真机
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
	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

   /*
     1) p12是下标，p10是buckets数组首地址，下标 * 1<<4(即16)得到实际内存的偏移量，通过buckets的首地址偏移，获取bucket存入p12寄存器
     2) LSL #(1+PTRSHIFT)  实际含义就是得到一个bucket占用内存大小，相当于mask = occupied - 1，_cmd & mask，取余数
   */
	add	p12, p10, p12, LSL #(1+PTRSHIFT)
		             // p12 = buckets + ((_cmd & mask) << (1+PTRSHIFT))
		             
   // 从x12（即p12）中取出bucket，分别将imp和sel存入 p17（存储imp） 和 p9（存储sel）
	ldp	p17, p9, [x12]		// {imp, sel} = *bucket
	
// 比较 sel 和 p1（唇乳的参数cmd）
1:	cmp	p9, p1			// if (bucket->sel != _cmd)
   // 如果不相等，即没有找到，请跳转至2f
	b.ne	2f			//     scan more
   // 如果相等，即CacheHit 缓存命中，直接返回 imp
	CacheHit $0			// call or return imp
	
2:	// not hit: p12 = not-hit bucket
   // 如果一直都找不到，因为是normal，跳转至__objc_msgSend_uncached
	CheckMiss $0			// miss if bucket->sel == 0
   // 判断p12（下标对应的bucket）是否等于p10（buckets数组第一个元素），如果等于则跳转至3f
	cmp	p12, p10		// wrap if bucket == buckets
	// 定位到最后一个元素（即第一个bucket）
	b.eq	3f
   // 从x12（即p12 buckets首地址），实际需要平移的内存大小BUCKET_SIZE,得到第二个bucket元素，imp-sel分别存入p17-p9，即向前查找
	ldp	p17, p9, [x12, #-BUCKET_SIZE]!	// {imp, sel} = *--bucket
	// 挑战至第1步，继续对比 sel与cmd
	b	1b			// loop

3:	// wrap: p12 = first bucket, w11 = mask
#if CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_HIGH_16
   /*
    1) 人为设值到最后一个元素
    2) p11(mask)右移44位，相当于mask左移4位，直接定位到buckets的最后一个元素，缓存查找顺序是向前查找
   */
	add	p12, p12, p11, LSR #(48 - (1+PTRSHIFT))
					// p12 = buckets + (mask << 1+PTRSHIFT)
#elif CACHE_MASK_STORAGE == CACHE_MASK_STORAGE_LOW_4
	add	p12, p12, p11, LSL #(1+PTRSHIFT)
					// p12 = buckets + (mask << 1+PTRSHIFT)
#else
#error Unsupported cache mask storage for ARM64.
#endif

	// Clone scanning loop to miss instead of hang when cache is corrupt.
	// The slow path may detect any corruption and halt later.
   // 再查找一遍缓存（）
   // 拿到x12(即p12) bucket中的 imp-sel 分别存入 p17-p9
	ldp	p17, p9, [x12]		// {imp, sel} = *bucket
// 比较 sel 与 p1（传入的参数cmd）
1:	cmp	p9, p1			// if (bucket->sel != _cmd)
   // 如果不相等，即走到第二步
	b.ne	2f			//     scan more
	// 如果相等，即命中，直接返回imp
	CacheHit $0			// call or return imp
	
2:	// not hit: p12 = not-hit bucket
   // 如果一直找不到，则CheckMiss
	CheckMiss $0			// miss if bucket->sel == 0
	// 判断p12（下标对应的bucket）是否等于p10（buckets数组第一个元素），表示前面已经没有了，但是还是没有找到
	cmp	p12, p10		// wrap if bucket == buckets
	// 如果等于，跳转至第3步
	b.eq	3f
	// 从x12（即p12 buckets首地址），实际需要平移的内存大小BUCKET_SIZE，得到第二个bucket元素，imp-sel分别存入p17-p9，即向前查找
	ldp	p17, p9, [x12, #-BUCKET_SIZE]!	// {imp, sel} = *--bucket
	// 跳转至第1步，继续对比 sel与imp
	b	1b			// loop

LLookupEnd$1:
LLookupRecover$1:
3:	// double wrap
    // 跳转至JumpMiss 因为是normal，跳转至__objc_msgSend_uncached
	JumpMiss $0

.endmacro

// 以下是最后跳转的汇编函数
.macro CacheHit
.if $0 == NORMAL
	TailCallCachedImp x17, x12, x1, x16	// authenticate and call imp
.elseif $0 == GETIMP
	mov	p0, p17
	cbz	p0, 9f			// don't ptrauth a nil imp
	AuthAndResignAsIMP x0, x12, 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, x12, x1, x16	// authenticate imp and re-sign as IMP
	ret				// return imp via x17
.else
.abort oops
.endif
.endmacro

.macro CheckMiss
	// miss if bucket->sel == 0
.if $0 == GETIMP // 如果为GETIMP，跳转至LGetImpMiss
	cbz	p9, LGetImpMiss
.elseif $0 == NORMAL // 如果为NORMAL，跳转至__objc_msgSend_uncached
	cbz	p9, __objc_msgSend_uncached
.elseif $0 == LOOKUP // 如果为LOOKUP，跳转至__objc_msgLookup_uncached
	cbz	p9, __objc_msgLookup_uncached
.else
.abort oops
.endif
.endmacro

.macro JumpMiss
.if $0 == GETIMP
	b	LGetImpMiss
.elseif $0 == NORMAL
	b	__objc_msgSend_uncached
.elseif $0 == LOOKUP
	b	__objc_msgLookup_uncached
.else
.abort oops
.endif
.endmacro

主要分为以下几步：

  • 【第一步】通过 cache 首地址平移 16 字节（因为在objc_class中），首地址 距离 cache 正好 16 字节，即 isa首地址 占 8 字节，superClass占 8 字节），获取 cache，cache中 高16位存mask，低48位存buckets，即 p11 = cache。

  • 【第二步】从cache中分别取出 buckets和mask,并由mask根据哈希算法计算出哈希下标

    • 通过 cache 和 掩码（即0x0000ffffffffffff）的 & 运算，将 高16位mask抹零，得到buckets指针地址，即 p10 = buckets

    • 将 cache 右移 48 位，得到 mask，即 p11 = mask

    • 将 objc_msgSend 的参数 p1 (即第二个参数_cmd) & mask，通过 哈希算法，得到需要查找存储 sel-imp 的 bucket下标index，即 p12 = index = _cmd & mask，为什么通过这种方式呢？因为在 存储sel-imp时，也是通过同样 哈希算法计算哈希下标进行存储，所以 读取 也需要通过同样的方式读取，如下所示：

1
2
3
4
5
6
7
// Class points to cache. SEL is key. Cache buckets store SEL+IMP.
// Caches are never built in the dyld shared cache.

static inline mask_t cache_hash(SEL sel, mask_t mask) 
{
    return (mask_t)(uintptr_t)sel & mask;
}

  • 【第三步】根据所得的 哈希下标Index 和 buckets首地址，取出哈希下标对应的 bucket

    • 其中 PTRSHIFT 等于 3，左移 4 位（即2^4 = 16字节）的目的是计算出一个 bucket 实际占用的大小，结构体 bucket_t 中 sel 占 8 字节，imp 占 8 字节

    • 根据计算的哈希下标 index乘以单个bucket占用的内存大小 ，得到 buckets 首地址在 实际内存中的偏移量

    • 通过 首地址+实际偏移量，获取哈希下标index对应的 bucket

  • 【第四步】根据获取的 bucket，取出其中的 imp 存入 p17，即 p17 = imp，取出 sel 存入 p9，即 p9 = sel

  • 【第五步】第一次递归循环

    • 比较获取的 bucket 中 sel 与 objc_msgSend 的第二个参数的 _cmd(即p1) 是否相等

    • 如果相等，则直接跳转至 CacheHit，即 缓存命中，返回 imp

    • 如果不相等，有以下两种情况

      • 如果一直都找不到，直接跳转至 CheckMiss，因为 $0 是 normal，会跳转至 __objc_msgSend_uncached，即进入 慢速查找流程

      • 如果 根据index获取的bucket 等于 buckets的第一个元素，则 人为 的将 当前bucket设置为buckets的最后一个元素（通过 buckets首地址+mask右移44位（等同于左移4位）直接 定位到bucker的最后一个元素），然后继续进行递归循环（第一个 递归循环嵌套 第二个 递归循环），即【第六步】

      • 如果 当前bucket 不等于 buckets的第一个元素，则继续 向前查找，进入 第一次递归循环

  • 【第六步】第二次递归循环：重复【第五步】的操作，与【第五步】中唯一区别是，如果 当前的bucket还是等于 buckets的第一个元素，则直接跳转至 JumpMiss，此时的 $0 是 normal，也是直接跳转至 __objc_msgSend_uncached，即进入 慢速查找流程

以下是整个 快速查找 过程 值的变化 过程

objc_msgSend通过伪代码实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>

// 查找 imp imp存储在 cache 的 bucket 下
[person sayNB]  -> imp ( cache -> bucket (sel imp))

// 获取当前的对象
id person = 0x10000
// 获取isa
isa_t isa = 0x000000
// isa -> class -> cache
cache_t cache = isa + 16字节

// arm64
// mask|buckets 在一起的
buckets = cache & 0x0000ffffffffffff
// 获取mask
mask = cache LSR #48
// 下标 = mask & sel
index = mask & p1

// bucket 从 buckets 遍历的开始 (起始查询的bucket)
bucket = buckets + index * 16 (sel imp = 16)


int count = 0
// CheckMiss $0
do{

    if ((bucket == buckets) && (count == 0)){ // 进入第二层判断
        // bucket == 第一个元素
        // bucket人为设置到最后一个元素
        bucket = buckets + mask * 16
        count++;
        
    }else if (count == 1) goto CheckMiss
        
    // {imp, sel} = *--bucket
    // 缓存的查找的顺序是: 向前查找
    bucket--;
    imp = bucket.imp;
    sel = bucket.sel;
    
}while (bucket.sel != _cmd)  //  // bucket里面的sel 是否匹配_cmd

// CacheHit $0
return imp

CheckMiss:
    CheckMiss(normal)

结尾

  • 在 缓存（CacheLookup）查找 过程中，如果没有找到方法实现，无论是走到 CheckMiss 还是 JumpMiss，最终都会走到 __objc_msgSend_uncached 汇编函数

CheckMiss源码

1
2
3
4
5
6
7
8
9
10
11
12
.macro CheckMiss
	// miss if bucket->sel == 0
.if $0 == GETIMP
	cbz	p9, LGetImpMiss
.elseif $0 == NORMAL
	cbz	p9, __objc_msgSend_uncached
.elseif $0 == LOOKUP
	cbz	p9, __objc_msgLookup_uncached
.else
.abort oops
.endif
.endmacro

JumpMiss源码

1
2
3
4
5
6
7
8
9
10
11
.macro JumpMiss
.if $0 == GETIMP
	b	LGetImpMiss
.elseif $0 == NORMAL
	b	__objc_msgSend_uncached
.elseif $0 == LOOKUP
	b	__objc_msgLookup_uncached
.else
.abort oops
.endif
.endmacro
  • 在 objc-msg-ram64.s 文件中查找 __objc_msgSend_uncached 的汇编源码，发现其核心是 MethodTableLookup(即查询方法列表) ，因此如果 缓存（CacheLookup）查找 没有找到，就去 MethodTableLookup（即方法列表中查找） ，下一章我们介绍

__objc_msgSend_uncached源码

1
2
3
4
5
6
7
8
9
10
STATIC_ENTRY __objc_msgSend_uncached
	UNWIND __objc_msgSend_uncached, FrameWithNoSaves

	// THIS IS NOT A CALLABLE C FUNCTION
	// Out-of-band p16 is the class to search
	
	// 方法列表查找
	MethodTableLookup
	TailCallFunctionPointer x17

  • Post title：OC底层原理14-1：objc-msgSend缓存查找(快速查找)汇编分析
  • Post author：张建
  • Create time：2023-02-25 18:38:26
  • Post link：https://redefine.ohevan.com/2023/02/25/OC底层原理/OC底层原理14-1：objc-msgSend缓存查找(快速查找)汇编分析/
  • Copyright Notice：All articles in this blog are licensed under BY-NC-SA unless stating additionally.
On this page
OC底层原理14-1：objc-msgSend缓存查找(快速查找)汇编分析
  1. 前言
  2. objc_msgSend 汇编查找流程分析
  3. objc_msgSend 缓存（CacheLookup）查找汇编流程
  4. objc_msgSend通过伪代码实现
  5. 结尾