我们回来了!WWDC 期间,我在 CocoaConf Next Door 上发言,其中一个专题的内容是关于 objc_msgSend
在 ARM64 架构中的实现。所以决定将其撰写成一篇文章并加入至 Friday Q&A 专题中。
总览
每一个 Objective-C 对象都拥有一个类,每个类都有自己的方法列表。每个方法都拥有选择子、一个指向实现的函数指针和一些元数据(metadata)。objc_msgsend
的工作是使用对象和选择子来查询对应的函数指针,从而跳转到该方法的位置中。
查找的方法可能十分复杂。如果一个方法在当前类中无法查询,那么可能需要在其父类中继续查询。当在父类中也无法找到,则开始调用 runtime 中的消息转发机制。如果这是发送到该类的第一条信息,那么它将会调用该类的 +initialize
方法。
一般情况下,查找的方法需要迅速完成。这与其复杂的查找机制似乎是矛盾的。
Objective-C 解决这个矛盾的方法是利用方法缓存(Method Cache)。每个类都有一个缓存,它将方法存储为一组选择子和函数指针,在 Objective-C 中被称为 IMP。它们被组织成哈希表的结构,所以查找速度十分迅速。当需要查找方法时,runtime 首先会查询缓存。如果结构不被命中,则开始那一套复杂的查询过程,并将结果存储至缓存,以便下次快速查询。
objc_msgSend
是使用汇编语言编写的。其原因是:其一是使用纯 C 是无法编写一个携带未知参数并跳转至任意函数指针的方法。单纯从语言角度来讲,也没有必要增加这样的功能。其二,对于 objc_msgSend
来说速度是最重要的,只用汇编来实现是十分高效的。
当然,我们也不希望所有的查询过程都是通过汇编来实现。一旦启用了非汇编语言那么就会降低速度。所以我们将消息分成了两个部分,即 objc_msgSend
的高速路径(fast path),此处所有的实现使用的是汇编语言,以及缓慢路径(slow path)部分,此处的实现手段均为 C 语言。在高速路径中我们可以查询方法指针的缓存表,如果找到直接跳转。否则,则使用 C 代码来处理这次查询。
因此,整个 objc_msgSend
的过程大体如下:
- 获取传入对象所属的类。
- 获取该类的方法缓存表。
- 使用传入的选择子在缓存中查询。
- 如果缓存中不存在,则调用 C 的慢速代码段。
- 跳转至
IMP
映射位置的方法。
具体是怎么实现的呢?下面开始分析。
导读
objc_msgSend
不同的情况有不同的执行路径。从中包含了处理如消息为 nil
(messages to nil),Tagged pointer 以及哈希表冲突的特殊代码。首相,先来看一个最常见最直观的情况,即消息发送到 non-nil
和 non-tagged
的情况,并且该指定函数指针在哈希表中可以直接获得。这里我将会记录遇到这些判断节点的各种情况,之后当我们到达运行终点后在回头看看其他情况。
我将会列出每个指令(instruction)或指令集(group of instructions),然后讲述它的功能以及调用原因。仅仅去理解每一条提及的指令即可。
每个指令前面都有一个偏移地址。他们就好比一个量化器,来告知程序跳转的位置。
ARM64 有 31 个 64 位寄存器。他们的位置符号从 x0
到 x30
。当然也可以使用寄存器中 w0
到 w30
的低 32 位,他们也是可独立使用的。x0
到 x7
前八位用于传递一个函数。这意味着 objc_msgSend
在 x0
中接收到选择子,在 x1
中接收 _cmd
参数。
0x0000 cmp x0, #0x0
0x0004 b.le 0x6c
如果此处的值小于或等于 0,则 self 与 0 的比较,并在其他位置进行跳转。零代表着 nil
,因此这会使得转发的消息也赋为 nil
。这也是处理 Tagged Pointers
的方案。Tagged Pointers
在 ARM64 上通过在高位来存储数据。(不同于 x86-64 ,其是在低位进行存储。)当高位被占用时,则被解释为存储的是一个有符号整数,且为负。当仅仅是普通指针的情况,程序不会运行到此处。
0x0008 ldr x13, [x0]
译者注:ARM 中的
LDR
为加载指令。LDR R0,[R1]
的意思是 将存储器地址为 R1 的字数据读入存储器 R0。LDR
指令用于从存储器中将一个 32 (ARM64 架构则为 64 位,后者相同)位字数据传送到目的存储器中。该指令通常用于存储器中读取 32 位的字数据套通用寄存器中,然后对数据进行处理。
此处是通过 x0 寄存器指向的 64 位字数据来加载 self
的 isa。x13
寄存器现在则存储着 isa
指针。
0x000c and x16, x13, #0xffffffff8
ARM64 中使用 Non-pointer isa。在以前的做法中 isa
是指向对象的 Class,但是 Non-pointer 将额外信息也天重置 isa 中来充分利用位空间。这个指令用 AND 逻辑算数符以掩码形式过滤额外信息,并将 Class 信息保留至
x16
寄存器中。
0x0010 ldp x10, x11, [x16, #0x10]
这是 objc_msgSend
中我最喜欢的一条指令。它将 Class 信息缓存至 x10
和 x11
中。ldp
指令会从内存中获得两个寄存器的数据保存到前两个指定的寄存器中。第三个参数说明所加载的数据源,当前情况中,以 x16
为基准在偏移 16 位从而得到保存 Class 信息的位置。此结构用 C 语言描述如下:
typedef uint32_t mask_t; // 无符号形 32 位来描述空间位置
struct cache_t {
struct bucket_t *_buckets;
mask_t _mask;
mask_t _occupied;
}
ldp
指令之后,x10
寄存器中已经写入 _buckets
的值,x11
在它的高 32 为中保存了 _occupied
,低 32 位保存了 _mask
。
_occupied
代表哈希表中的元素的数量,在 objc_msgSend
过程中没有太大的作用。而 _mask
相对来说就比较重要了:即象征了哈希表的位数,而且又构造一个等位掩码从而方便进行 AND 运算。这个值往往可以用 2 的整数幂减一来表达,例如 000000001111111
这样的,最后一位是可变不定的。通过该值可以求得选择子的查询索引,并在搜索时仅取得低位。
0x0014 and w12, w1, w11
这条指令用于计算通过 _cmd
传入的选择子在哈希表中的起始索引。x1
用于记录 _cmd
,则 w1
中记录的是 _cmd
的低 32 位。w11
中包含了上面提到的 _mask
。这条指令将两个值做与运算再存入 w12
中。结果相当于 _cmd % table_size
,但是避免模运算的巨大开销。
0x0018 add x12, x10, x12, lsl #4
当然只获取到索引还远远不够。为了从表中加载数据,还需要读取其实际地址。这条指令通过表指针的初始地址加上索引偏移量来计算真实地址。首先想将索引左移 4 位,等效于乘以 16 ,因为每个哈希表的 bucket 是 16 字节。x12
中现在获取到要搜索位置的第一个 bucket 的地址。
0x001c ldp x9, x17, [x12]
之前的 ldp
命令又出现了。这次是从 x12
中的指针指向地址进行加载,这个指针指向了所查找的 bucket。每个 bucket 包含了一个选择子和一个 IMP
。x9
中现在存有当前 bucket 的选择子,x17
中存储着 IMP
。
0x0020 cmp x9, x1
0x0024 b.ne 0x2c
这两天命令首相对 x9
中的选择子和 x1
中的 _cmd
进行比较。如果它们不相等则说明这个 bucket 中不包含我们正在查询的选择子。此时调用第二条命令跳转至 0x2c
位置,处理 bucket 不匹配问题。但如果选择子命中,则查询成功,并执行接下来的步骤。
0x0028 br x17
BR 命令用于跳转到reg内容地址。
这是一个无条件的跳转命令,直接跳转至 x17
中记录的位置,包含之前从 bucket 中加载的 IMP
。从这开始,之后的部分就是目标方法的代码实现,此处也是 objc_msgSend
的 Fast Path 结束为止。所有持有参数的寄存器将不会受到读写干扰,目标方法会接受传入的全部参数,正如直接的函数调用一般。
当所有信息均被缓存后,在现在设备上一路执行下来仅需要 3 纳秒即可结束。
下面来关注一下当缓存中没有所需匹配内容时的情况。
0x002c cbz x9, __objc_msgSend_uncached
x9
中记录了从 bucket 加载到的选择子。首先先将其与 0 进行比较,如果等于 0 则会跳转至 __objc_msgSend_uncached
。这说明 bucket 为空且扫描缓存失败。目标方法不在缓存中,并回到 C 代码中进行更复杂的查询流程。交由 __objc_msgSend_uncached
处理。否则则说明 bucket 不为空,只是没有匹配,进行进行查询流程。
0x0030 cmp x12, x10
0x0034 b.eq 0x40
此处比较 x12
中 bucket 的地址和 x10
中哈希表的起始位置。如果匹配,则跳转到哈希表末端之后的位置仅需执行代码。无法直观的是,哈希表搜索方向是逆向的。查询索引逐步递减,指定搜索至表头,二次搜索时从末端重新开始。笔者并不了解为何以此种方式进行工作,而不是以拉链法在开头地址处插入元素的场景方法,但或许这是一个更安全的流程,并保证了更快的执行速度。
偏移量 0x40
处的代码处理了这种情况。如果不匹配,则执行下面的命令。
0x0038 ldp x9, x17, [x12, #-0x10]!
ldp
又一次出现,在一次从缓存 bucket 中加载。这一次它从偏移量为 0x10
位置加载当前缓存的 bucket
地址。在地址引用标记末尾使用感叹号是一个有趣的特性。这指定一个寄存器进行回写,就是寄存器会更新为计算后的值。这条指令实际上是执行 x12 -=16
来加载新的 bucket,并使 x12
指向这个新的 bucket 地址。
0x003c b 0x20
已经加载到一个新的 bucket,下面继续检查更新后的 bucket 是否匹配。这条命令会返回上面 0x0020
位置,使用新的值在执行一次所有的代码。如果仍旧没有匹配,则继续执行之后的这些代码,或是 bucket 为空情况的处理,或是命中表头后的处理。
0x0040 add x12, x12, w11, uxtw #4
这是当查询到之后的操作。x12
中包含了当前 bucket 的指针,即指向第一个 bucket。w11
存有表的掩码,描述了表的大小。这里将两个值进行了相加运算,并将 w11
左移 4 位。此时 x12
中的结果是指向表末尾的,并且可以从此次恢复查询。
0x0044 ldp x9, x17, [x12]
使用 ldp
操作加载一个新的 bucket 至 x9
和 x17
中。