解析objc_msgSend(ARM64)

概览

每个Objective-C对象都有相应的类,这个类都有一个方法列表。类中的每个方法都有一个选择子、一个指向方法实现的函数指针和一些元数据。objc_msgSend的工作就是通过传入的对象和选择子,查找相应方法的函数指针,然后跳转到该函数指针。

查找方法的流程是非常复杂的。如果这个方法没有在对应的类上被找到,就会到该类的父类中去查询。如果所有类都没有这个方法,那么就会调用runtime消息中的forwarding代码。如果这是发送到该类上的第一条消息,就同时会调用该类的+initialize方法。

但是在一般情况下,查询方法需要非常快,因为有成千上万次查询。这就与前面复杂的查找过程相矛盾了。

Objective-C解决这个冲突的方法是方法缓存。每个类都有一个方法缓存,它将方法存储为选择子和函数指针的键值对,这个函数指针在Objective-C中被称为IMPS。这个选择子和函数指针键值对被存为一个哈希表,所以查找速度很快。查找方法时,runtime首先查询缓存。如果方法不在缓存中,则进入相对慢且复杂的进一步查询。查到之后会将结果放入缓存中,这样下一次查询更快。

objc_msgSend是用汇编写的。原因有二:一是不能编写保留未知参数的函数,并跳转到C中的任意函数指针。C语言没有必要的特性来做这样的事情。二是objc_msgSend需要保证快速的查询,那就需要直接操作指令来保证。

当然,你不需要用汇编语言编写整个复杂的消息查找程序。objc_msgSend的代码可以分为两部分:一是objc_msgSend缓存查询,它是用汇编写的,二是分级查询,是用C实现的。汇编部分在高速缓存中查找方法,如果发现该方法就跳转到该方法上。如果该方法不在缓存中,则调用C代码来处理进一步的查询。

总的来说,在调用objc_msgSend时会执行以下操作:

  1. 获取传入的对象的类。
  2. 获取该类的方法缓存。
  3. 使用传入的选择器来查找缓存中的方法。
  4. 如果不在缓存中,则调用C代码。
  5. 跳转到该方法的IMP。

用汇编查询缓存

objc_msgSend根据具体情况可以采取不同的查询策略,比如消息发送到nil、标记的指针(tagged pointers)和哈希表的冲突等情况。首先看看最常见的情况:即将消息发送到非nil非标记指针,同时在高速缓存中找到了该方法,而无需进行进一步扫描查询。对于其他的特殊情况,我们在分析完常见情形时再来分析。

在这里,每条指令前面都有一个从函数开始的偏移量。这作为一个计数器,让你识别跳转目标。

ARM64有31个整型寄存器,从x0x31,它们是64位的。同时也可以使用w0w30访问每个寄存器的低32位,就像它是一个单独的寄存器一样。寄存器x0x7用于将前8个参数传递给函数。这意味着objc_msgSend接收x0中的self参数和x1中的选择子_cmd参数。

让我们开始!

0x0000 cmp     x0, #0x0
0x0004 b.le    0x6c

如果self(x0)小于等于0,则跳转到别处。0代表nil,则处理message发送到nil的特殊情况。这里同时也处理标记指针。在ARM64上标记指针设置高32位(在x86-64上是低32位)。如果设置了高位,那么对于有符号整数时,该值为负。对于self是普通指针的常见情况,将不会进入该分支。

0x0008 ldr    x13, [x0]

通过加载x0来加载selfisa,其中包含self。现在x13寄存器包含isa

0x000c and    x16, x13, #0xffffffff8

ARM64可以使用非指针的isas。传统上isa指向对象的类,而非指针isa则通过空闲位将一些其他信息填充到isa中来。该指令执行一个逻辑与来过滤所有的额外位信息,并将实际的类指针信息放入x16中。

0x0010 ldp    x10, x11, [x16, #0x10]

它将类的缓存信息加载到x10x11中。 ldp指令将两个寄存器的内存数据加载到前两个参数中指定的寄存器中。第三个参数描述了从哪里加载数据,在这里,从x16的偏移量16(十进制)的位置开始,这是类中保存高速缓存信息的区域。缓存结构体代码如下:

typedef uint32_t mask_t;

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字段非常重要:它将哈希表的大小描述为一个掩码,值始终是2的幂减1,像000000001111111这种二进制形式。这个值用来计算选择子的查找索引,同时可以在查询列表时返回到列表末端。

0x0014 and    w12, w1, w11

该指令找寻以_cmd形式传入的选择子在哈希始表中的索引。x1包含_cmd,所以w1包含_cmd的低32位。 w11包含如上所述的_mask。该指令将两者逻辑与后放入w12。这个结果相当于_cmdtable_size的值。

0x0018 add    x12, x10, x12, lsl #4

要想从哈希表中加载数据,需要知道其实际地址,因此只有索引还不够。该指令将左移4位的哈希表索引和bucket地址相加后赋值给x12,因为每个哈希表bucket都是16字节。现在x12指向了要搜索的第一个bucket的地址。

0x001c ldp    x9, x17, [x12]

该指令加载x12(当前bucket)的地址给x9x17。每个bucket包含一个选择子和一个IMPx9现在指向当前bucket的选择子,x17指向当前bucketIMP

0x0020 cmp    x9, x1
0x0024 b.ne   0x2c

这些指令将x9中的选择子与x1中的_cmd进行比较。如果它们不匹配,那么当前的bucket不包含我们正在查找的选择子。在这种情况下,第二条指令跳转到偏移0x2c,用来处理不匹配的bucket。如果匹配到选择子,那么就找到了正在查找的条目,并继续执行下一条指令。

0x0028 br    x17

这里无条件跳转到x17,它包含当前bucket加载的IMP。在这里执行实际的目标方法的实现函数,同时也是objc_msgSend的快速查询的最终阶段。由于所有参数寄存器都不受干扰,因此目标方法将接收所有传入的参数,就如同直接调用一样。
当所有的方法都被缓存后,在如今的硬件设备上快速查询的时间会小于3纳秒。

接着让我们看一下没有匹配到缓存(bucket)的代码逻辑。

0x002c cbz    x9, __objc_msgSend_uncached

x9包含从bucket中加载的选择子。该指令将其与0进行比较,如果为0,则跳转到__objc_msgSend_uncached。没有选择子代表bucket是空的,也就是搜索失败。如果目标方法不在高速缓存中,就需要执行C代码来进行更全面查找。

0x0030 cmp    x12, x10
0x0034 b.eq   0x40

该指令比较x12中的当前bucket地址与x10中的哈希表的起始地址。如果匹配,则跳转到0x40
在这里执行的哈希表搜索实际上是反向运行的。搜索从末尾到起始地址。

0x0038 ldp    x9, x17, [x12, #-0x10]!

ldp加载当前bucket的地址偏移0x10的地址,也就是上一个bucket地址,并赋值给x9x17。地址末尾的感叹号表示寄存器写回,是用新值更新旧值。

0x003c b      0x20

这里循环跳会上面的0x0020的指令。也就是不停的对比bucket,直到找到一个相同的bucket,或者一直没找到直到哈希表的开始位置。

0x0040 add    x12, x12, w11, uxtw #4

跳转到0x0040是,x12已经指向哈希表的开始, 而w11表示哈希表的掩码,也就是表的大小。将w11左移4位后将这两者相加,结果是新的x12再次指向表的末尾。再次从尾到头进行搜索。

0x0044 ldp    x9, x17, [x12]

现在ldp将新的bucket载入x9x17

0x0048 cmp    x9, x1
0x004c b.ne   0x54
0x0050 br     x17

该代码检查当前bucket于传入的_cmd否匹配,匹配跳转到bucket的IMP,不匹配跳转到0x54。这是上面0x0020代码的重复。

0x0054 cbz    x9, __objc_msgSend_uncached

就像之前一样,如果bucket是空的,那么这是一个缓存未命中并且执行C实现的综合查找代码。

0x0058 cmp    x12, x10
0x005c b.eq   0x68

接着再次检查当前的bucket是否到了哈希表的起始,如果再次运行到表的起始,则跳转到0x68。在这种情况下,它跳转到C代码的全面查找:

0x0068 b      __objc_msgSend_uncached

那为什么会出现这个重新扫描呢?源码的解释如下:
当缓存损坏时,克隆扫描循环而不是挂起循环。全面查找时可能会检测到任何损坏并在稍后停止这个循环。
这种情况不常见,但显然苹果开发人员看到由于内存损坏导致缓存充满了损坏的内容,并跳转到C代码来提高诊断。
这个再次检查对正常的代码应该影响很小。没有它,原来的循环可以被重用,这将节省一些指令缓存空间,但只节省一点点。只有对于在哈希表起始附近的选择子,同时发生冲突并且所有先前的条目被占用时,重新扫描才会被调用。

0x0060 ldp    x9, x17, [x12, #-0x10]!
0x0064 b      0x48

这个循环的其余部分与之前一样。将下一个bucket加载到x9x17中,更新x12中的bucket指针,然后返回到循环的顶部。

这样objc_msgSend主体就结束了。那么nil和标记指针的特殊情况是如何的呢?

标记指针(Tagged Pointer)的处理

你可能回忆起在指令最开始的检查,跳转到0x6c来处理这种情况。

0x006c b.eq    0xa4

进入这个逻辑是因为self小于等于0。小于0表示一个标记指针,等于0表示为nil。这两种情况的处理是完全不同的。首先检查是第一种情况还是第二种情况。如果等于0跳转到0xa4。如果不是,继续执行下一条指令。

先简要的说明一下标记指针是如何工作的。标记指针(ARM64)的高4位指明这个对象属于哪个类。这对于标记指针的isa是必要的。当然,4bit几乎不足以拥有一个类指针。因此,有一张特殊的表来存储可用的标记指针类。一个标记指针对象的类通过高4位来查询这张表中的相应的类。

继续。

0x0070 mov    x10, #-0x1000000000000000

这条指令设置x10的高4位都为1,其他都为0。

0x0074 cmp    x0, x10
0x0078 b.hs   0x90

然后看x0是否大于等于x10,如果大于等于则表明是标记指针,则跳到0x90处理额外的类。否则,就直接使用主标记指针表(primary tagged pointer table)。

0x007c adrp   x10, _objc_debug_taggedpointer_classes@PAGE
0x0080 add    x10, x10, _objc_debug_taggedpointer_classes@PAGEOFF

_objc_debug_taggedpointer_classes是主标记指针表。ARM64需要两条指令加载一个符号地址,因为ARM64是64位的,而指令仅只有32位。因此不可能用一条指令来表示一个完整的指针。
x86就不会遇到这个问题,因为它有变长的指令。对于定长指令的机器,需要分片加载。

0x0084 lsr    x11, x0, #60

标记类的索引在x0中的高4位,为了作为索引使用,需要右移60位,使它的范围变为0-15。这条指令把结果存入x11

0x0088 ldr    x16, [x10, x11, lsl #3]

这条指令通过索引来加载主标记指针表中的标记指针。现在x16包含这个类的标记指针。

0x008c b      0x10

x16包含了这个类的标记指针时,就可以返回到上面主分支代码的0x10

0x0090 adrp   x10, _objc_debug_taggedpointer_ext_classes@PAGE
0x0094 add    x10, x10, _objc_debug_taggedpointer_ext_classes@PAGEOFF

额外的标记类处理起来类似。两条指令加载一个指向额外表的指针。

0x0098 ubfx   x11, x0, #52, #8

这条指令加载额外的类索引。它从self中提取52位中的前8位到x11

0x009c ldr    x16, [x10, x11, lsl #3]

像之前一样,利用索引来找寻表中的类,并赋值给x16

0x00a0 b      0x10

得到了x16,就可以继续回到主分支代码执行0x10

nil处理

终于到了nil的处理逻辑。以下是全部指令:

0x00a4 mov    x1, #0x0
0x00a8 movi   d0, #0000000000000000
0x00ac movi   d1, #0000000000000000
0x00b0 movi   d2, #0000000000000000
0x00b4 movi   d3, #0000000000000000
0x00b8 ret

nil的处理是完全不同的,它没有类查询和方法分发。它做的只是返回0给调用者。

实际上objc_msgSend不知道调用者期望哪一种返回值。是返回一个整数、两个整数或者浮点值呢,还是什么都没有返回?

幸好,寄存器可以被安全的重写。整数存在x0x1中,浮点数存在v0-v3中。多个寄存器被用来返回一个小的结构体。

代码清空了x1v0-v3d0-d3表示v0-v3的低32位。因此movi在这清空了上述4个寄存器。这之后,返回ret给调用者。

你可以会问为什么不清空x0。因为x0在这时本身就是空的,所以就不需要清空。

如果需要返回一个大的结构体,而现有的寄存器无法满足呢?这需要调用者的合作。大的结构体返回需要调用者申请足够大的内存。objc_msgSend不能清空内存,因为它不知道返回值有多大。为解决这个问题,在调用objc_msgSend之前,编译器自动生成代码把内存都填充为0。

结论

探究框架的内部实现往往是非常有趣的。通过阅读源码,可以看到objc_msgSend极具艺术性且实现的非常优雅。

参考

Dissecting objc_msgSend on ARM64
arm
Non-pointer isa

Author: MrHook
Link: https://bigjar.github.io/2018/01/29/%E8%A7%A3%E6%9E%90objc-msgSend-ARM64/
Copyright Notice: All articles in this blog are licensed under CC BY-NC-SA 4.0 unless stating additionally.