微信号:learnSwift

介绍:每天推送一篇精品Swift文章,无偿翻译,共同学习.;;

剖析 ARM 64 架构中的 objc_msgSend

2018-08-06 23:49 Mike Ash

译者:BigNerdCoding;校对:pmst,shanks;定稿:CMB

很高兴,我又回来了。在刚刚过去的 WWDC 期间,我在 CocoaConf Next Door 做个一个关于剖析 ARM64 上 objc_msgSend 运行流程的发言。现在我将整理后的内容重新发布到 Friday Q&A 上。

概述

每个 Objective-C 对象都会指向一个类,而每个类又包含一个方法列表。每个方法则由选择器(selector)、函数指针和一些元数据(metadata)构成。objc_msgSend 职责就是接收对象(object)和选择器(selector),根据选择器名称找到对应方法的函数指针并跳转执行该函数。

查找过程相对来说还是比较复杂的。若某个方法在当前类中未找到,就需要沿着继承链继续在父类中查找。如果在父类中也未查询到的话,则会触发 runtime 机制中的消息转发机制。任何对象在接收到第一条消息后都会触发类方法 +initialize

因为每次方法调用都会触发上述流程,所以在常见场景下的查找速度必须非常快。显然这与复杂的操作过程之间存在一定冲突。

为了解决这对矛盾提高查询速度,Objective-C 采用了方法缓存策略。每个类都会使用哈希表将其方法按照 Selector - IMPs(函数指针) 键值对关系缓存起来。这样在查询方法时,runtime 首先会直接去哈希表中查询。如果哈希表中不存在的话则转而执行原有复杂、缓慢的处理流程,并将最终结果缓存起来已备下次使用。

objc_msgSend 用汇编语言进行实现,具体理由有两个:首先纯 C 语言无法实现这么一个函数:接收不定个数且未知类型的参数作为入参跳转至任意函数指针(即调用实现);其次,执行速度对 objc_msgSend 来说非常重要,汇编语言能最大化提升该项指标。

当然,使用汇编语言实现整个复杂的消息处理过程是不现实的,而且也没这种必要。因为有些流程一旦触发程序都会变慢,无论采用何种语言层面的实现。整个消息处理流程代码可以分为两个部分:通过汇编代码实现的快速路径部分(fast path) ,C 语言实现的慢路径流程(slow path)。其中汇编代码对应缓存表中查询方法部分并且未命中时跳转 C 代码来进行下一步处理。

因此,objc_msgSend 代码处理流程大致如下:

  1. 获取消息对象所对应的类信息

  2. 获取类所对应的方法缓存

  3. 在方法缓存中查询 selector 对象的函数实现

  4. 如果查询失败则调用 C 代码进行下一步处理

  5. 跳转到 IMP 所指的函数实现

下面开始分析其具体实现。

执行过程的指令

objc_msgSend 在不同情形下执行路径不尽相同。对于向 nil 发送消息,标记指针(tagged pointers),哈希表冲突会相应特殊代码中进行处理。下面我将通过最常见也是最简单的情形来解释 objc_msgSend  的执行,即处理 non-nil、non-tagged 消息并且哈希表也能命中该方法。我会在该过程中标记出那些需要注意的处理路径岔路口,然后回过头来进行详细讲解。

我将列出单条或一组指令,然后在下面紧接相关解释内容。

每条指令前面都会有一个地址偏移量,可以将其看作一个指示跳转位置的标记量。

ARM64 架构中包含 31 个 64 位整型寄存器,对应符号表示为 x0 - x30 。每个寄存器的低 32 位也可以通过 w0 到 w30 进行访问,就像它也是一个单独的寄存器。其中 x0 到 x7 被用来保存函数调用时的前 8 个参数。这意味着 objc_msgSend 函数中的 self 参数保存在 x0 而 _cmd 保存在 x1 。

起始指令如下:

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

该段指令是将 self 与 0 进行有符号比较,如果 self 不大于 0 的话则会进行跳转处理。等于 0 其实就相当于 nil 对象,也就是说此时会调用向 nil 发送消息情形下对应的特定代码。另外,该指令也被用于标记指针(tagged pointers)的处理。ARM64 通过设置最高位为 1 来标记 Tagged Pointers(x86-64 则是最低位),此时对应有符号数比为负。对于普通指针来说,上述处理分支都会不被触发。

asm
0x0008 ldr    x13, [x0]

该指令将 x0 中所表示的 self 的 isa 地址加载到 x13 寄存器中。

asm
0x000c and    x16, x13, #0xffffffff8

因为 ARM64 架构下能够使用 non-pointer isas 技术,所以与之前相比 isa 字段不仅可以包含指向 Class 的信息,它还能利用多余比特位存储其它有效信息(例如,引用计数)。这里通过 AND 逻辑运算去除低位的冗余信息得到最终的 Class 的地址并将其存入 x13 寄存器中。

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

这是整个 objc_msgSend 处理流程中我最喜欢的指令。该指令会将 Class 中的方法缓存哈希表加载到 x10 和 x11 两个寄存器中。ldp 指令会将有效的内存信息加载到该指令的前两个寄存器中,而第三个参数则对应该信息的内存地址。在该例中缓存哈希表地址为 x16 寄存器中地址偏移 16 后所处位置。缓存对象数据结构类似于:

c
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 则相对重要:它将哈希表大小描述为了一个便于进行与操作的掩码。_mask 值为 2^n - 1 ,换句话说它的二进制表示将以一组 1 作为结尾,形如 000000001111111 。该值为查询 selector 的哈希表索引以及标记表尾的必要条件。

asm
0x0014 and    w12, w1, w11

该指令用于计算 _cmd 所传递过来的 selector 在哈希表中的起始位置。因为 _cmd 保存在 x1 寄存器中,所以 w1 寄存器则包含了 _cmd 的低 32 位信息。而 w11 寄存器保存了上面提到的 _mask 信息。通过 AND 指令我们将这两个寄存器中数值与操作结果保存到 w12 寄存器中。计算结果相当于 _cmd % table_size  ,但是它却避免了模操作的昂贵开销。

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

仅仅得到索引是不够,为了从表中加载数据,我们需要得到最终的实际地址。而这正是该指令的目的。因为哈希表的 bucket 都是 16 个比特位,所以这里先对 x12 寄存器中的索引值左移 4 位也就是乘以 16 ,然后再将其与表首地址相加后的确切 bucket 地址信息保存到 x12 中。

asm
0x001c ldp    x9, x17, [x12]

再一次通过 ldp 指令,将上一步保存在 x12 寄存器中 bucket 对应的信息加载到 x9 和 x17 寄存器中。因为 bucket 由 selector 和 IMP 两部分构成,所以 x9 对应保存了 selector 信息而 x17 则保存了 IMP 信息。

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

该段指令会将 x9 寄存器中的内容和 x1 中的 _cmd 进行对比,如果它们不等则意味着 bucket 中不包含我们所操作的 selector ,并且在此时跳转到 0x2c 处执行对应的未匹配处理。如果相同的话则表示命中,继续执行下一条指令。

asm
0x0028 br    x17

该指令为无条件跳转到 x17 寄存器所指位置,也就是跳转到 IMP 所指处执行具体实现代码。此时 objc_msgSend 处理流程中最快的路径已经结束。其余参数所做寄存器都没有被干扰,目标方法会接受传入的全部参数,一切行如直接调用目标函数。

在最理想的情形下,objc_msgSend 处理流程最快可以在 3 纳秒内执行完毕。

在介绍完理想的最快情形后,接下来我们需要关注其余几种情形。首先,我们来看下当方法未缓存时的处理。

asm
0x002c cbz    x9, __objc_msgSend_uncached

前面提到 x9 寄存器包含了加载后的 selector 信息。将寄存器中的信息与零进行比较,如果等于 0 的话就跳转到 __objc_msgSend_uncached 代码处。因为等于 0 就意味着 bucket 为空也就是说方法查询失败,selector 对应的方法没有被缓存到哈希表中。此时我们需要调用 C 语言代码进行更为复杂的处理,也就是 __objc_msgSend_uncached 。如果仅仅只是方法不匹配且 bucket 不为空的话,则需要继续进行方法查找。

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

该指令将 x12 寄存器中的当前 bucket 地址与 x10 寄存器中的哈希表首地址进行比较。如果两者内容匹配上了,则我们从哈希表的末尾进行反向查询。虽然我还没弄明白此时为什么没有采用常见的正向遍历查询,但是有理由认为可能这样速度更快。

0x40 表示匹配后跳转目的地址。如果两者不匹配则继续执行下面的指令。

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

再一次代码通过 ldp 指令加载缓存信息,只不过地址为距当前 bucket  偏移 -0x10 所指位置。该指令中的 !符号表示寄存器回写操作,也就是说会使用计算后的结果更新 x12 寄存器。将其用数学方式表示就是:x12 -= 16,将 x12 中表示的地址前移 16 个单位。

asm
0x003c b      0x20

加载新的 bucket 信息后,代码重新跳转到 0x20 处循环查询过程,直到出现下列情形:找到匹配项,bucket 为空,再次回到了哈希表的起始处。

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

当查询到匹配想后会触发该指令。此时 x12 寄存器为最新的 bucket 地址,而 w11 保存了包含哈希表大小的掩码值。该指令将 w11 左移 4 位后将两个值进行叠加得到哈希表尾地址,并将结果保存到 x12 寄存器中,然后接着恢复查询操作。

asm
0x0044 ldp    x9, x17, [x12]

该指令为加载新 bucket 信息到 x9,x17 寄存器中。

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

该段指令与前面的 0x0020 处的功能一致,只要寄存器内容匹配上了就跳转到对应 IMP 位置执行代码。

asm
0x0054 cbz    x9, __objc_msgSend_uncached

同样的,若不匹配则执行与前面 0x002c 一样的处理流程。

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

该指令与 0x0030 处一致,只不过如果此时 x12 寄存器内容依旧是哈希表首地址的话程序会跳转到 0x68 处进行处理。

asm
0x0068 b      __objc_msgSend_uncached

这种情况一般不太容易发生,因为它会导致哈希表持续膨胀。此时哈希表的查询效率会下降而去潜在哈希碰撞的可能性会变高。

至于原因,源码中的注释是这些写的:

Clone scanning loop to miss instead of hang when cache is corrupt. The slow path may detect any corruption and halt later.
当缓存损坏时,需要跳出上面的循环查询流程而不是进入挂起状态。 转而执行慢速路径流程去检测任何可能的损坏并终止代码执行。

我怀疑这种情况很常见,但很显然苹果公司的员工已经看到内存损坏会让哈希表充满无效内容所以在此处跳转到 C 代码中进行错误诊断。

此项检查的存在应该将对未损坏的缓存的影响降低到最小。去除该检查,原来的循环处理流程可以被重用,这会节省一点指令缓存空间。 无论如何,该处理程序器并不是常见的情况。 只会在哈希表的开始位置查询到所需的选择子或者发生了哈希碰撞时才会被调用。

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

该段指令与之前功能一致,加载新 bucket 信息到 x9,x17 寄存器中。更新 x12 中的地址,并跳转到 0x48 处重复查找流程。

objc_msgSend 的主要处理流程到此告一段落,剩下 Tagged Pointer 和 nil 两个特殊情形的处理。

标记指针的处理

我们回到第一组汇编指令的跳转处来讲解标记指针(Tagged Pointer)的处理。

asm
0x006c b.eq    0xa4

当参数 self 不大于 0 时,该指令就会被触发。其中小于 0 对应标记指针,而等于零则对应 nil 。这两种情形有各自的处理流程,所以第一步就是要区分出到底是哪种情形。若为 nil 情形则跳转到 0xa4 处进行处理,否则继续执行。

在继续讲解之前,先简单讨论下标记指针工作原理。 标记指针支持多个类。其中高 4 位(在 ARM64 上)指明了“对象”的类信息,本质上就是 Tagged Pointer 的 isa 。当然 4 个比特位不足以容纳一个类指针,实际上这些信息都被存在了一张特殊表中。我们可以以高 4 位的值为索引去表中查询真正的类信息。

这还不是全部,标记指针(至少在 ARM64 上)支持拓展类。当高 4 位全为 1 时,紧接着的 8 个比特位将被用作拓展类表中的索引值。 这样在运行时支持更多的标记指针类,不过代价就是能存储的有效信息会变少。

下面继续指令的执行。

asm
0x0070 mov    x10, #-0x1000000000000000

该指令将一个整形值(高 4 位为 1 ,其余全为 0)写入 x10 寄存器中。这将用作下一步提取 self 标记位的掩码。

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

这一步时检查拓展标记指针内容。如果 self 大于或者等于 x10 中的值,则意味这 self 的高 4 位也全部为 1 。此时代码会跳转到 0x90 处理拓展类部分的内容,否则就继续执行下面的指令去主标记指针表中的查询类信息。

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

该段指令主要就是加载 _objc_debug_taggedpointer_classes@PAGE  所指的主标记指针表地址。因为 ARM64 上的指针是 64 位宽,而指令只有 32 位宽,所以需要采用类 RISC 标准技术通过两个指令来加载符号地址。

x86 架构则不存在该问题,因为它采用可变长度指令集。它可以通过一个 10 字节长的指令处理上面的问题:2 个字节用来区分具体指令和寄存器,剩下 8 个字节用来保存指针地址。

而在定长指令集机器上,我们只能通过一组命令加以应对。例如,上例就是通过两条指令实现 64 位指针地址的加载操作。adrp 指令加载高 32 位信息然后再通过 add 指令将其与低 32 位进行求和。

asm
0x0084 lsr    x11, x0, #60

因为索引值保存在 x0 的高 4 位中,所以该指令将 x0 进行右移 60 位取出对应的索引值(取值范围为 0-15)并保存到 x11 中。

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

根据索引值获取标记指针的类信息并保存到 x16 中。

asm
0x008c b      0x10

获得类信息后程序会无条件跳回 0x10 处,并复用主分支中的代码进行方法查询处理。

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

该段指令与前面加载主标记指针表功能一样,只不过此时它用于处理前面提到的拓展表分支。

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

该指令只要是取出 self 中从第 52 位开始的 8 位信息作为拓展表的索引值,并将其保存到 x11 中。

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

再一次,我们将获得的类信息加载到 x16 中。

asm
0x00a0 b      0x10

最后,我们同样跳回到 0x10 处。

接下来,我们来看 nil 情形的处理过程。

`nil` 的处理

作为最后一个特殊情况,下面就是 nil 情形下被执行的所有指令。

asm
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 不知道具体的返回值类型。是整型值、浮点值、亦或者是什么都不返回。

幸运的是,所有用于设置返回值的寄存器都能被安全覆写,即使此次调用过程不会使用到。整型返回值被保存在 x0 和 x1 中,而浮点值则保存在向量寄存器 v0 - v3 中。同时使用多个寄存器可以返回一个小型结构体类型返回值。

在处理 nil 情形时,上诉指令会将 x1 以及 v0 - v3 中的值全部清空并设置为 0。其中 d0 - d3 分别对应向量寄存器 v0 - v3 的后半部分,通过将其设置为 0 清除了后半部分然后在通过 movi 清除所有的寄存器内容。清空返回值寄存器后,控制权将重新回到调用方。

如果返回值为比较大的结构体,那么寄存器可能就变的不够用了。此时就需要调用者做出一些配合。调用者会在一开始为该结构体分配一块内存,然后将其地址提前写入到 x8 寄存器中。在设置返回值的时候,直接往该地址中写数据即可。
因为该内存大小对 objc_msgSend 是透明的,因此不能对其进行清空操作。取而代之的操作就是在调用 objc_msgSend  之前编译器会将其设置为 0 。

以上就是 nil 情形的处理,objc_msgSend 流程到此也宣告结束。

总结

深入框架底层还是很有趣的,而 objc_msgSend  就像一件艺术品,值得细细玩味。

今天的内容到此结束,下次再会为大家带来一些更好的内容。Friday Q&A 很多内容都是由读者驱动而来,所以欢迎大家在下面积极发言。

汇编指令校对者注

  1. #0x0:“#”修饰的数字表示立即数,可简单理解为数值,而非地址:

  2. b :跳转指令,b.le 指比较结果小于等于的时候跳转至某内存地址;

  3. ldr :从内存中读取数据到寄存器;

  4. and:arm 的 and 指令,需要3个操作数,例如 AND R0,R0,#3 是将 R0 寄存器的值与数字3(0x0000003)逻辑与,将结果存储为 R0 寄存器

  5. addADD[con][S] Rd,Rn,operand,将 operand 数据与 Rn 的值相加,结果保存到 Rd 寄存器;

  6. lsl: 逻辑左移指令,可以结合 add 指令一起使用,如ADDS R0,R1,R2,LSL#2,将 R2 寄存器左移 2 位,接着 R1 和 R2 值相加,将结果存储到 R0 中;

  7. cbz:c对应compare,b就是上面的跳转,z对应0 zero,因此这条命令当比较结果为零(Zero)就跳转至之后的指令;

  8. UXTW: 32 位的逻辑左移指令,更多请见[llvm] r205861;

  9. LSR: 逻辑右移;

  10. UBFXUBFX{cond} Rd, Rn, #lsb, #width 从一个寄存器中提取位域,cond —可选,条件码 ;Rd — 目标寄存器 ;Rn — 源寄存器 ;lsb —位域的最低有效位的位置,范围是 0 - 31; width — 位域的宽度,范围是1到 32-lsb

本文由 SwiftGG 翻译组翻译,已经获得作者翻译授权,最新文章请访问 http://swift.gg。


 
SwiftGG翻译组 更多文章 构建一个 @synchronized 在 Swift 中使用马尔可夫链生成文本 Swift Package Manager 重写 macOS 部署目标 何时用 struct?何时用 class? 关于注释
猜您喜欢 Android 应用启动速度优化之 Systrace 的使用 云巴实时案例|云巴多人绘图,随时随地记录分享你的灵感 你是第五只猴子吗?(我对产品经理发飙的理由) 敏捷破冰之旅(六) 轻松筹1.6亿注册用户的Passport账户体系架构设计