从一道 iOS 面试题到 Swift 对象模型和运行时细节——「iOS 面试之道」勘误

面试工作基本结束，如果不出什么意外（比如资方最后撤回录用邀约之类）的话我将会去一家我认为比较有作为空间的公司工作。在准备面试过程中，我买了一本「iOS 面试之道」看，然而发现里面在技术这一部分还是有一些纰漏的。发现这些纰漏后我发了电子邮件给本书技术部分的共同作者，但是后来又发现其实那封邮件中也有一些错误。现在有时间校对了一下并且扩充了一些内容后选择在中文 web 上刊登出来。因为其中一道题目涉及冗长的 Swift 对象模型和运行时细节，所以单独写成一篇文章发布出来，其余的再组成第二篇文章。这篇文章是第一篇，主要讨论「iOS 面试之道」中第 34 页中有关链表的代码范例。

自动引用计数 + 超长链表释放 == 爆栈？

我注意到本书 34 页中有关链表的代码范例使用了自动引用计数的方式管理链表节点的后继节点。然而根据我的经验，这种构造方法会造成在链表过长后出现链表在释放时爆栈而最终导致 app 崩溃的隐患。

class ListNode {
    var val: Int
    var next: ListNode?
    
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}
复制代码

我们可以打开 Xcode 新建一个 macOS 命令行工程，输入如下代码：

import Foundation

print("Main thread stack size: ", Thread.main.stackSize)

class ListNode {
    var val: Int
    var next: ListNode?
    
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
}

autoreleasepool {
    let root = ListNode(0)
    
    var current = root
    
    for _ in 0..<100000 {
        let next = ListNode(0)
        current.next = next
        current = next
    }
}

print("Foo")
复制代码

思考题：你在上述代码中感到了什么异样没有？

如果不爆栈，那么这个程序将最后输出 "Foo"。但是在运行期间，这个程序就崩溃了——Xcode 会将左侧的 Navigator 面板切换到 Debug Navigator 然后显示下列内容：

依靠直觉，我们可以猜测，应该是因为编译器给 ListNode 自动生成的 deinit 中释放 next 的过程是一个递归过程，100000 个节点将导致递归过程太深，然后调用栈爆了（俗称爆栈）。但是问题来了：

• 真的是这样吗？
• Swift 不会做尾递归优化吗？

尾递归优化指的是，一个递归函数在函数体尾部调用其自身时，我们可以不创建一个新的栈帧（stack frame）而直接利用原有的栈帧来进行计算，这样就可以避免递归过程中可能出现的因为调用栈太深而爆栈的危险；这个优化是编译优化中的一个可选部分，具体有无由编译器厂商决定。

要深入理解尾递归以及讨论 iOS 开发中的尾递归优化会涉及到编译原理的运行时环境中的过程抽象这个部分，我之后会专门撰文谈谈 iOS 开发中的过程抽象，这里我们先不做深入讨论。

这些问题都需要我们对 Swift 的对类实例进行释放时的工作机制有一个基本的了解。

追踪 ListNode 实例的释放过程

为了更加详细地了解 Swift 的工作机制，我们一般都会想到去直接考察编译后产生的二进制文件。我们可以将 ListNode 部分的代码保存为一个名为 CallStack.swift 的文件，然后在命令行用 swiftc CallStack.swift 编译后再用 Hopper 反编译出来：

显然，Swift 编译器也使用了类似 C++ 编译器的 name mangling 的技术对译元（translation unit，既参与编译的每一份源文件，我不太清楚中文译法，自己译的）中的成员名字进行改编，以此让 Swift 中函数和类型的重名现象降至最低。但是这也造成了在这张图中，我们除了能猜测出 val 和 next 这两个 properties 的 accessors 对应的过程（既二进制文件中函数对应的机器码）之外，就再也猜测不出究竟哪个过程是这个自动生成的 deinit 函数对应的过程了。

「函数」和「过程」的区别在不同语境下不同。在计算机编程刚刚兴起时，函数指的是有返回值的函数，而过程指的是没有返回值的函数；到了现在，人们几乎已经不再区别函数和过程。在这里，我用函数表示 Swift 中的函数，而过程表示函数在二进制文件中对应的机器码序列。

如果这时我们能回溯到更加高一级的编译产物中，也许能找到答案。但是对于很多人而言，也许只知道源代码转换成 AST（抽象语法树），AST 转换成 LLVM IR（LLVM 中间表述），然后 LLVM IR 生成机器码，再又链接器合成目标文件（可执行文件或者库）的这个流程；并且对于这些人而言，查看和分析 AST 或者 LLVM IR 是非常陌生的。但是 Swift 的编译过程有点不一样：Swift 的编译过程不等同于传统 Clang + LLVM 的编译过程，在 AST和 LLVM IR之间还会生成一个叫 SIL（Swift Intermediate Language，Swift 中间语言）的产物。SIL 是 Swift AST 和 LLVM IR 之间的一层抽象，是一种具备高层（相对于机器语言这种底层）语义的 SSA 形式（静态单次赋值形式） 的编译器中间表述。如果你看不懂前面这句，那么可以认为 SIL 就是一种具备高级语言语义（既「指令集」抽象自 Swift 运行时，而不单纯是目标平台）以及机器底层抽象（比如说使用 %0 %1 %2 ... %n 来表示虚拟寄存器，同时可以部分操纵内存布局的）这两种知识的综合体。因为其具备高层语义又兼顾底层，也许我们能在这里面找到 ListNode 的 deinit 函数的相关信息（如果你可以上 YouTube 可以看看这个视频了解一下 SIL 是什么，不过需要一点编译器相关的知识）。

于是这里我们需要在命令行使用 swiftc -emit-sil CallStack.swift 来获得这份源代码的 SIL。

使用 -emit-sil 和 -emit-silgen 都可以生成 Swift SIL，但是前者会附带语法诊断信息，而后者是生（raw）SIL。

deinit 过程分析：SIL 视角

通过搜索 ListNode.deinit 我们可以找到如下内容：

// ListNode.deinit
sil hidden @$s9CallStack8ListNodeCfd : $@convention(method) (@guaranteed ListNode) -> @owned Builtin.NativeObject {
// %0                                             // users: %4, %2, %1
bb0(%0 : $ListNode):
  debug_value %0 : $ListNode, let, name "self", argno 1 // id: %1
  %2 = ref_element_addr %0 : $ListNode, #ListNode.next // user: %3
  destroy_addr %2 : $*Optional<ListNode>          // id: %3
  %4 = unchecked_ref_cast %0 : $ListNode to $Builtin.NativeObject // user: %5
  return %4 : $Builtin.NativeObject               // id: %5
} // end sil function '$s9CallStack8ListNodeCfd'
复制代码

有趣的是，即使你在 ListNode 中自定义一个空白的 deinit 函数，Swift 编译器还是会生成同样的 SIL，可见 Swift 编译器是会在自定义的 deinit 函数中自动补全该摧毁的所有实例成员的摧毁（destroy）代码的。

于是我们可以知道， $s9CallStack8ListNodeCfd 这个过程对应的是 ListNode.deinit 这个函数，其 SIL 的主要内容如下：

bb0(%0 : $ListNode):
  ...
  %2 = ref_element_addr %0 : $ListNode, #ListNode.next // user: %3
  destroy_addr %2 : $*Optional<ListNode>          // id: %3
  ...
}
复制代码

首先我们要注意到 bb0 这个东西：

bb 意指 basic block，这是来自 LLVM 中的一个概念：既一段最基本的代码块。

一段改写成 SIL 的 Swift 函数可能只有一个 basic block，也可能因为有各种控制流的加入（if-else 或者 switch-case 之类的）导致有很多个 basic blocks。 bb0 就是指的函数体内的第 0 个 basic block。

然后，我们还可以注意到 bb0 背后还有一个 (%0 : $ListNode) ：

在这里，这个 %0 本质上是 bb0 这个 basic block 内的本地变量，指的是第 0 号虚拟寄存器，而其类型就是 ListNode 。特别的，这个第 0 号虚拟寄存器充当这个 basic block 的第一个「形式参数」——当然， bb0 不是函数，这里我只是借用「形式参数」这个概念来帮助大家理解这个 %0 到底是个什么玩意儿。之后你还会在 SIL 中看到 %1 %2 %3 ... %n 这种表记，这些都是「第 n 号虚拟寄存器」的意思——同时他们也被都是「本地变量」。同样，这种表记方法也来自 LLVM IR，而 SIL 借鉴之。

最后，就是 ref_element_addr 和 destroy_addr 这些东西是什么：

这些东西被称为 SIL 指令。这些东西也是 SIL 之所以被称为 SIL (Swift Intermediate Language) 的原因——因为这些 SIL 指令并不是有关目标平台指令的抽象，而是 Swift 运行时的抽象。我们可以将这些 SIL 指令理解为一个函数，实际上这些指令在最后生成 LLVM IR 后也确实会去调用那些由 C++ 编写的 Swift 运行时中对应的函数。

接下来我们讨论一下这段 SIL 干了啥：

这部分的内容主要就是将 bb0 的 %0 传入 ref_element_addr 指令。然后用 %2 接住返回值，再将这个返回值传入 destroy_addr 指令。

我们可以在 这里 找到 ref_element_addr 指令的说明：

sil-instruction ::= 'ref_element_addr' sil-operand ',' sil-decl-ref

%1 = ref_element_addr %0 : $C, #C.field
// %0 must be a value of class type $C
// #C.field must be a non-static physical field of $C
// %1 will be of type $*U where U is the type of the selected field
//   of C
复制代码

所以我们知道，这个指令是用来获得实例变量的地址的。

你可能看不懂 sil-instruction ::= 'ref_element_addr' sil-operand ',' sil-decl-ref 是什么意思，不要急，我下面会讲。

而

%2 = ref_element_addr %0 : $ListNode, #ListNode.next
复制代码

的意思就是获得关于 %0 上这个 ListNode 实例的 ListNode.next 实例变量的地址。

接下来一句：

destroy_addr %2 : $*Optional<ListNode>
复制代码

我们可以在 这里 找到 destroy_addr 的文档：

sil-instruction ::= 'destroy_addr' sil-operand

destroy_addr %0 : $*T
// %0 must be of an address $*T type
复制代码

%1 = load %0
strong_release %1
复制代码

我们可以从中得知：这句 SIL 其实相当于执行：

strong_release %2 : $*Optional<ListNode>
复制代码

而文档对 strong_release 的解释如下：

strong_release %0 : $T
// $T must be a reference type.
复制代码

所以我们知道， strong_release 会减少该对象的强引用计数。在强引用计数到 0 的时候，对象被摧毁，且弱引用被置 nil 。当强引用计数和 unowned 引用计数都到 0 的时候，对象内存被释放（deallocated）。

结合我们构造出来的 ListNode 这个类分析一下：因为除了 ListNode 体内有一个指向 next 节点的强引用之外就没有任何 unowned 引用了，我们不难得出：这句 SIL 意图是摧毁（destroy）实例变量 next ，但是随后将引发实例变量 next 背后所指向的内存空间被释放（deallocated）。

可是我们可以发现，这个 deinit 函数对应的 SIL 中并没有释放（deallocate） ListNode 实例的相关内容，我们不禁要问：是不是有一个函数会「包裹」住 deinit 然后专门用来释放 ListNode ？又或者释放一个对象实例其实是由 Swift 运行时包办的？

一个「惊喜」……

我们首先验证第一个猜测：在我们生成的 SIL 内容中搜索 $s9CallStack8ListNodeCfd 也就是 deinit 对应的过程，之后我们会发现 Swift 编译器还生成了一个叫 $s9CallStack8ListNodeCfD 的过程，对应的 Swift 函数名根据 SIL 中的注释应该是 ListNode.__deallocating_deinit 。同时这个过程「包裹」了我们的 deinit 函数：

// ListNode.__deallocating_deinit
sil hidden @$s9CallStack8ListNodeCfD : $@convention(method) (@owned ListNode) -> () {
// %0                                             // users: %3, %1
bb0(%0 : $ListNode):
  debug_value %0 : $ListNode, let, name "self", argno 1 // id: %1
  // function_ref ListNode.deinit
  %2 = function_ref @$s9CallStack8ListNodeCfd : $@convention(method) (@guaranteed ListNode) -> @owned Builtin.NativeObject // user: %3
  %3 = apply %2(%0) : $@convention(method) (@guaranteed ListNode) -> @owned Builtin.NativeObject // user: %4
  %4 = unchecked_ref_cast %3 : $Builtin.NativeObject to $ListNode // user: %5
  dealloc_ref %4 : $ListNode                      // id: %5
  %6 = tuple ()                                   // user: %7
  return %6 : $()                                 // id: %7
} // end sil function '$s9CallStack8ListNodeCfD'
复制代码

所以我们第一个猜测是真的。

__deallocating_deinit 过程分析：SIL 视角

ListNode.__deallocating_deinit 函数的 SIL 中的主要内容如下：

bb0(%0 : $ListNode):
  %2 = function_ref @$s9CallStack8ListNodeCfd : $@convention(method) (@guaranteed ListNode) -> @owned Builtin.NativeObject // user: %3
  %3 = apply %2(%0) : $@convention(method) (@guaranteed ListNode) -> @owned Builtin.NativeObject // user: %4
  %4 = unchecked_ref_cast %3 : $Builtin.NativeObject to $ListNode // user: %5
  dealloc_ref %4 : $ListNode                      // id: %5
  ...
}
复制代码

这段 SIL 中的内容比较繁复，主要是将 bb0 的 %0 传递给了过程 $s9CallStack8ListNodeCfd （也就是 ListNode.deinit 函数对应的 SIL 函数），再用 %3 接住上面这个函数的返回值后将返回值扮演（cast，我不知道这个字怎么译，自己想的译法）成 ListNode 储存到 %4 中，然后将 %4 作为实际参数传递给 SIL 指令 dealloc_ref 。

我们可以在 这里 找到 dealloc_ref 的文档：

sil-instruction ::= 'dealloc_ref' ('[' 'stack' ']')? sil-operand

dealloc_ref [stack] %0 : $T
// $T must be a class type
复制代码

于是我们可以知道， dealloc_ref 这个 SIL 指令是用来释放并且反初始化类实例的，然后这个过程会忽略引用计数，并且要求实例的引用计数为 1。同时，这个 SIL 指令不会摧毁（destroy）实例内部的 stored properties，stored properties 中的内容必须在执行 dealloc_ref 指令前就被清除掉（就是 ListNode.deinit 所干的活了）。

dealloc_ref [ stack ] %foo : $Bar

dealloc_ref %foo : $Bar
复制代码

sil-instruction ::= 'dealloc_ref' stack-operand-or-epsilon sil-operand
stack-operand-or-epsilon ::= 'stack'
                          |  ε
复制代码

你可能还会注意到 dealloc_ref 这个指令的文档提到了分配一个类实例的 SIL 指令 alloc_ref 以及一个叫 [stack] 的参数。根据上面我对 EBNF 的解释，你不难得出其实 Swift 是支持在 stack 内存上分配类实例这点事实。但是我还没空去研究如何在代码中实现这点，所以这里不展开说明。

ListNode 实例释放过程 SIL 总结

我们可以从上述节选的 SIL 内容推测出来 ListNode.__deallocating_deinit 这个函数是用来释放（deallocate）heap 内存上的为对象分配的内存的，而这个过程中则调用了 ListNode.deinit 。这个 ListNode.deinit 函数则负责对实例内部的成员进行摧毁（destroy）。当然，在这里 ListNode 的 next 成员并没有其他 unowned 引用或者强引用，于是摧毁（destroy）这个 next 实例成员的同时也会引发 next 节点指向的内存区域被释放（deallocated）。显然，上述过程将引发一个间接递归调用。

现在我们可以再次打开 Hopper 找到 deinit 对应的过程。

其中我们发现 swiftc 为 deinit 生成机器码后这个过程实际上会调用一个叫 _$s9CallStack8ListNodeCSgWOh 的过程，于是我们找到它：

是的，你会看到最终这个过程调用了 swift_release 这个函数，根据我们之前对 deinit 的 SIL 的研究，这个函数应该就是对应着 dealloc_ref 这个 SIL 指令，也应该就是这个过程最终行使了对 next 节点的释放。

思考题：请猜测 Swift 为 ListNode 的成员摧毁过程单独生成一个函数，并从 deinit 外联（outline）到该函数的设计意图。

我们可以从名字上猜测出这个函数的作用可能和 [NSObject -release] 或者 CFRelease 差不多，根据我们对引用计数的常识，其行为也应该就是进行引用计数到 0 之后将内存释放这么一个动作。但是这只是猜测，我们还要从源代码角度对其进行验证。

在这里我们要说明的是， swift_release 是 Swift 运行时的一部分，由 Swift 标准库提供。 Swift 标准库在 Swift 程序被编译的过程中将会被链接到目标文件上。以下分析过程中我们都不能忘记我们是在考证 Swift 运行时的构成，而不是我们写的关于 ListNode 这个程序的构成。

追踪 swift_release

使用 git 克隆 Swift 源代码，并将分支切换到 swift-5.0-branch 。

在 Swift 源代码中搜索 swift_release 我们可以在 include/swift/Runtime/HeapObject.h 找到下列代码：

namespace swift {

...

SWIFT_RUNTIME_EXPORT
void swift_release(HeapObject *object);

...

}
复制代码

在这里我们可以看见 swift_release 是一个 swift 这个命名空间下一个拥有 HeapObject * 类型形式参数的函数，但是我们还不能确定这就是我们要找的——因为这部分代码是由 C++ 实现的 Swift 的运行时代码，在 C++ 中开发者可以对函数名字改编（name mangling）规则进行选择——既，是用 C 的规则改编还是用 C++ 的规则改编。

根据 C 的规则进行改编后， swift_release 应该叫 _swift_release ；而根据 C++ 的规则改编后，抱歉，C++ 的改编规则太复杂，我也记不得……但是会和 _swift_release 差很远。

而如果要让一个 C++ 头/源文件中的函数或者变量名字使用 C 的名字改编规则进行名字改编，那么就必须加上 extern "C" 这个前缀。

为了求证这个函数就是我们要找的 swift_release 函数，我们需要找到 SWIFT_RUNTIME_EXPORT 这个宏。我们可以在 stdlib/public/SwiftShims/Visibility.h 找到这个宏的定义：

#if defined(__cplusplus)
#define SWIFT_RUNTIME_EXPORT extern "C" SWIFT_EXPORT_ATTRIBUTE
#else
#define SWIFT_RUNTIME_EXPORT SWIFT_EXPORT_ATTRIBUTE
#endif
复制代码

我们发现这是一套可以根据语言来做切换的宏，其中如果是按照 C++ 来编译（既被 C++ 源文件 include）的话， SWIFT_RUNTIME_EXPORT 的内容就是 extern "C" SWIFT_EXPORT_ATTRIBUTE ，而如果按照 C 来编译（既被 C 源文件 include）的话就是 SWIFT_EXPORT_ATTRIBUTE 。于是我们可以知道，这个在 swift 命名空间下的 swift_release 函数在完成编译后其二进制符号并不会以 C++ 的方式进行改编，以 C 的方式进行改编。所以我们可以确定这就是我们要找的函数。

小议 swift_release 函数签名

在这里我们还有一个疑问：为什么这个函数的形式参数是 HeapObject * 类型的？

很多人觉得，可能是因为 Swift 和 Objective-C 一样有一个公共根类——只是说 Swift 没有把这个公共根类暴露出来。

这样说可以说对了一半，但是在这里属于答非所问了：确实，在后面我们可以看到：一旦 Swift 编译过程中选择了支持 Objective-C 运行时，那么在 Swift 中除了 @objc 这种消息转发级别的保证 Swift 对象和 Objective-C 对象间互操作性（interoperability）的语言特性之外，每一个 Swift 类都会有一个对应的 Objective-C 类以保证 Swift 和 Objective-C 之间最基本的生命周期控制方面的互操作性，而所有 Swift 类的 Objective-C 对应类都继承自一个公共根类就是 SwiftObject 。

至于「所有 Swift 类都有一个公共根类叫 HeapObject 」，这就差得远了。为什么？

首先，C++ 中为了保证和 C 语言在「值语义」上的统一，其 struct 和 class 并没有什么实质上的区别，在内存布局上也是一模一样。C++ 的创造者之所以保留了 struct 仅仅是为了和 C 兼容。所以即使上述「所有 Swift 类都有一个公共 根类 叫 HeapObject 」的描述为真，那么也应该改成「所有 Swift 类都有一个公共 根类型 叫 HeapObject 」.

var a: Int = 4
b = a
复制代码

class Foo {
    var int: Int = 0
    init(int: Int) { self.int = int }
}

var a = Foo(int: 0)
b = a
b.int = 10 // a.int == 10; b.int == 10;
复制代码

class Foo {
    int value;
    Foo(int val): value(val) {}
}

auto a = Foo(0);
auto b = a;
b.value = 10; // a.int == 0; b.int == 10;
复制代码

class Foo {
    int value;
    Foo(int val): value(val) {}
}

auto a = new Foo(0);
auto b = a;
b -> value = 10; // a -> int == 10; b -> int == 10;
复制代码

思考题：在明白了「值语义」和「引用语义」的区别后，我再问你在 Swift 中什么时候使用 struct，什么时候使用 class，你还会给出网上那些所谓的「标准答案」吗？

其次，我们可以从 C++ 对象模型（既内存布局）的角度来讨论——因为如果一个 Swift 类要以一个 C++ 类型为根类型的话，那么 Swift 对象和 C++ 的对象至少在内存布局上要是一致的。

我们在 include/swift/SwiftShims/HeapObject.h 中找到 HeapObject 类型的定义：

#define SWIFT_HEAPOBJECT_NON_OBJC_MEMBERS       \
  InlineRefCounts refCounts

/// The Swift heap-object header.
/// This must match RefCountedStructTy in IRGen.
struct HeapObject {
  /// This is always a valid pointer to a metadata object.
  HeapMetadata const *metadata;

  SWIFT_HEAPOBJECT_NON_OBJC_MEMBERS;

#ifdef __cplusplus
  HeapObject() = default;

  // Initialize a HeapObject header as appropriate for a newly-allocated object.
  constexpr HeapObject(HeapMetadata const *newMetadata) 
    : metadata(newMetadata)
    , refCounts(InlineRefCounts::Initialized)
  { }

#ifndef NDEBUG
  void dump() const LLVM_ATTRIBUTE_USED;
#endif

#endif // __cplusplus
}
复制代码

可以发现这是一个 struct ，其中包含一个数据成员 metadata 和一个宏 SWIFT_HEAPOBJECT_NON_OBJC_MEMBERS 。

我们将宏 SWIFT_HEAPOBJECT_NON_OBJC_MEMBERS 展开后可以得到 InlineRefCounts refCounts ，而我们又可以在 include/swift/SwiftShims/RefCount.h 中找到 InlineRefCounts 的定义：

// This definition is a placeholder for importing into Swift.
// It provides size and alignment but cannot be manipulated safely there.
typedef struct {
  __swift_uintptr_t refCounts SWIFT_ATTRIBUTE_UNAVAILABLE;
} InlineRefCountsPlaceholder;

#if !defined(__cplusplus)

typedef InlineRefCountsPlaceholder InlineRefCounts;

#else

...

typedef RefCounts<InlineRefCountBits> InlineRefCounts;

...

#endif
复制代码

我们发现这个类型在 C 和 C++ 中看起来会不一样：

RefCounts<InlineRefCountBits>

而最终我们可以在 stdlib/public/SwiftShims/RefCount.h 中找到 RefCounts 和 InlineRefCountBits 的定义：

enum RefCountInlinedness { RefCountNotInline = false, RefCountIsInline = true };

...

typedef RefCountBitsT<RefCountIsInline> InlineRefCountBits;

...

template <typename RefCountBits>
class RefCounts {
  std::atomic<RefCountBits> refCounts;
  
  ...
}
复制代码

我们继续可以在同一个文件内找到 RefCountBitsT 的定义：

// Basic encoding of refcount and flag data into the object's header.
template <RefCountInlinedness refcountIsInline>
class RefCountBitsT {
  ...

  BitsType bits;
  
  ...
}
复制代码

所以我们可以知道， HeapObject 最终看起来是这样子的：

struct HeapObject {
  HeapMetadata const *metadata;

  RefCounts<RefCountBitsT<true>> refCounts;

#ifdef __cplusplus
  HeapObject() = default;

  // Initialize a HeapObject header as appropriate for a newly-allocated object.
  constexpr HeapObject(HeapMetadata const *newMetadata) 
    : metadata(newMetadata)
    , refCounts(InlineRefCounts::Initialized)
  { }

#ifndef NDEBUG
  void dump() const LLVM_ATTRIBUTE_USED;
#endif

#endif // __cplusplus
}
复制代码

而 struct （包括 class ）在 C++ 中存在两种内存布局：

• 一种是和 C struct 一样的内存布局。

  这种布局保证了和 C API 的互操作性。

• 一种是拥有 C++ 运行时特性的内存布局。

  这种布局不能保证和 C API 的互操作性，但是拥有 C++ 特有的虚函数、值语义相关的构造函数、析沟函数、拷贝构造函数和赋值函数这些运行时特性。

所以说，如果 Swift 类都以一个 C++ 类型作为根类型，那么：

• 要么 Swift 类的实例会和 C struct 是一样的布局；
• 要么 Swift 类的实例会和拥有 C++ 特性的 C++ 类型实例是一样的内存布局。

很明显，一个 Swift 类是拥有继承能力的，而继承之后的类如果没有被标记为 final 或者其成员函数没有被标记为 final 的话，那么将需要使用类似 C++ 中 vtable 的技术来对继承后复写（override，自己译的）了的函数进行消息转发，所以 Swift 类的实例不可能和 C struct 是一样的布局。

这样以来，如果我们要证明或者证否 Swift 类都拥有一个「隐性」的 C++ 根类型——既 HeapObject 的话，仅仅需要查证 HeapObject 这个类型本身是不是一个拥有 C++ 特性的 C++ 类型就可以了。

我们可以看到，上述 HeapObject 的源代码有如下宏：

#ifdef __cplusplus
  ...
#endif // __cplusplus
复制代码

这是一段典型的判定引用该头文件的到底是 C 还是 C++ 源文件的宏，如果是 C++ 的源文件引用了该头文件，那么这个宏内包裹的内容将生效，如果是 C，那么将无效。

同时这段宏内的内容：

HeapObject() = default;

  // Initialize a HeapObject header as appropriate for a newly-allocated object.
  constexpr HeapObject(HeapMetadata const *newMetadata) 
    : metadata(newMetadata)
    , refCounts(InlineRefCounts::Initialized)
  { }

#ifndef NDEBUG
  void dump() const LLVM_ATTRIBUTE_USED;
#endif
复制代码

其目的是定义一个默认的默认构造函数（比较拗口）、一个以常量表达式（ constexpr ）修饰的构造函数以及一个 debug 用的成员函数。在这些 C++ 的「私货」中：

• 我们可以看到 HeapObject 的构造函数 constexpr HeapObject(HeapMetadata const *newMetadata) 是一个 constexpr 函数，C++ 将在编译时就对这个函数进行求值，然后将求值之后的结果写入编译产物；

  而 HeapObject 的默认构造函数 HeapObject() = default; 是默认的。

  所以这些构造函数都是 trivial 的。Trivial 是一个借鉴自数学的概念，在 C/C++ 中指可以通过简单的赋值完成的动作。这些动作并不会导致 HeapObject 异化成一个仅仅兼容 C++ 的类型——因为这些构造函数并不需要使用到 C++ 的运行时特性；

• 新加的成员函数 void dump() const 是非虚（non-virtual）函数。

  这相当于新增一个全局函数 void HeapObjectDump(HeapObject * this) ，且不会导致 HeapObject 异化成一个只能在 C++ 中使用的类型——因为非虚函数也不需要使用到 C++ 运行时特性。

从以上这些看， HeapObject 是考虑了与 C 的兼容的——也就是说 HeapObject 采取的应该是和 C struct 一样的布局。现在我们可以给出 HeapObject 实例的内存布局：

而一个使用 C struct 布局的 C++ 类型怎么可能会是所有 Swift 类的根类型呢？

所以我们知道「所有 Swift 类都有一个公共 根类型 叫 HeapObject 」这点应该是不成立的。

那么到底为什么 swift_release 的形式参数会是 HeapObject * 类型的？

实际上，后面我们会看到， swift_release 的形式参数为 HeapObject * 类型的在这里是一种编程技巧，目的是为 HeapObject * 指向的内存区域提供一个可以在 C/C++ 中访问的途径。

继续探索 swift_release

好的。现在我们继续探索 swift_release 。因为 swift_release 是一个 swift 命名空间下的函数，我们可以尝试搜索 void swift::swift_release( 以找到这个函数的实现文件。在 stdlib/public/Runtime/HeapObject.cpp 中我们可以发现如下内容：

...

void swift::swift_release(HeapObject *object) {
  _swift_release(object);
}

static void _swift_release_(HeapObject *object) {
  SWIFT_RT_TRACK_INVOCATION(object, swift_release);
  if (isValidPointerForNativeRetain(object))
    object->refCounts.decrementAndMaybeDeinit(1);
}

auto swift::_swift_release = _swift_release_;

...
复制代码

我们可以看到 swift_release 这个函数最后跳转到了 _swift_release_ 这个函数内，而 _swift_release_ 在进行了引用计数追踪（ SWIFT_RT_TRACK_INVOCATION ）和原生 Swift 对象的检查（ isValidPointerForNativeRetain ）后调用了 decrementAndMaybeDeinit 这个函数。

再搜索 decrementAndMaybeDeinit 找到其头文件 stdlib/public/SwiftShims/Refcount.h ，然后我们可以发现如下内容：

enum PerformDeinit { DontPerformDeinit = false, DoPerformDeinit = true };

...

template <typename RefCountBits>
class RefCounts {
  std::atomic<RefCountBits> refCounts;

  ...

  LLVM_ATTRIBUTE_ALWAYS_INLINE
  void decrementAndMaybeDeinit(uint32_t dec) {
    doDecrement<DoPerformDeinit>(dec);
  }

  ...
}
复制代码

我们看到 decrementAndMaybeDeinit 调用了 doDecrement 这个模板函数并且将 true 传入了第一个模板参数。于是我们可以在同一个文件找到这个模板函数：

template <typename RefCountBits>
class RefCounts {
  ...
  
  template <PerformDeinit performDeinit>
  bool doDecrement(uint32_t dec) {
    auto oldbits = refCounts.load(SWIFT_MEMORY_ORDER_CONSUME);
    RefCountBits newbits;
    
    do {
      newbits = oldbits;
      bool fast =
        newbits.decrementStrongExtraRefCount(dec);
      if (!fast)
        // Slow paths include side table; deinit; underflow
        return doDecrementSlow<performDeinit>(oldbits, dec);
    } while (!refCounts.compare_exchange_weak(oldbits, newbits,
                                              std::memory_order_release,
                                              std::memory_order_relaxed));

    return false;  // don't deinit
  }

  ...
}
复制代码

这个函数中出现了我们很喜欢讨论的 lock free 编程技巧——CAS（compare and swap），但是我们在这里并不关心这个。我们关心的是在 do...while 循环体内 if(!fast) 这个条件分支下的代码：整体而言，这整个函数负责减少对象的引用计数，并且在适当的时候（无法套用 fast path，既包含 side table、会导致 deinit 以及引用计数小于 0）会调用模板函数 doDecrementSlow 。

我们接着可以在同一个文件内找到 doDecrementSlow 这个模板函数：

template <typename RefCountBits>
class RefCounts {
  ...

  template <PerformDeinit performDeinit>
  bool doDecrementSlow(RefCountBits oldbits, uint32_t dec) {
    RefCountBits newbits;
    
    bool deinitNow;
    do {
      newbits = oldbits;
      
      bool fast =
        newbits.decrementStrongExtraRefCount(dec);
      if (fast) {
        // Decrement completed normally. New refcount is not zero.
        deinitNow = false;
      }
      else if (oldbits.hasSideTable()) {
        // Decrement failed because we're on some other slow path.
        return doDecrementSideTable<performDeinit>(oldbits, dec);
      }
      else {
        // Decrement underflowed. Begin deinit.
        // LIVE -> DEINITING
        deinitNow = true;
        assert(!oldbits.getIsDeiniting());  // FIXME: make this an error?
        newbits = oldbits;  // Undo failed decrement of newbits.
        newbits.setStrongExtraRefCount(0);
        newbits.setIsDeiniting(true);
      }
    } while (!refCounts.compare_exchange_weak(oldbits, newbits,
                                              std::memory_order_release,
                                              std::memory_order_relaxed));
    if (performDeinit && deinitNow) {
      std::atomic_thread_fence(std::memory_order_acquire);
      _swift_release_dealloc(getHeapObject());
    }

    return deinitNow;
  }
  
  ...
}
复制代码

这个函数在确认要执行 deinit 之后将执行 _swift_release_dealloc(getHeapObject()); 来对 heap 上为对象分配的内存进行释放，而之前我们已经在 Debug Navigator 的调用栈中看到了 _swift_release_dealloc 。

但是这个 _swift_release_dealloc 里面又做了什么呢？

_swift_release_dealloc 初探

我们继续搜索 void _swift_release_dealloc( 找到其实现文件 include/swift/Runtime/HeapObject.h ，内容有下：

void _swift_release_dealloc(HeapObject *object) {
  asFullMetadata(object->metadata)->destroy(object);
}
复制代码

我们可以看见，这个函数将 HeapObject * 指针指向的实例中的 metadata 成员传递给了 asFullMetadata 函数，然后又调用了返回值上一个叫 destroy 的看起来像是一个「函数」的成员。

现在我们来考察 asFullMetadata 这个模板函数。我们可以搜索源代码，在 include/Swift/ABI/Metadata.h 中找到相关内容：

...

/// Given a canonical metadata pointer, produce the adjusted metadata pointer.
template <class T>
static inline FullMetadata<T> *asFullMetadata(T *metadata) {
  return (FullMetadata<T>*) (((typename T::HeaderType*) metadata) - 1);
}

...
复制代码

我们可以看到， asFullMetadata 实际上是一个模板函数。在这个模板函数中，其实际上的动作是：

1. 将 metadata 扮演（cast）成 T::HeaderType * 类型；
2. 然后再向后（或者说低地址空间）位移了一个 T::HeaderType 的长度；
3. 最后再扮演（cast）成 FullMetadata<T> * 类型返回。

所以如果我们要了解 asFullMetadata(object->metadata)->destroy(object); 这句到底做了什么，我们就必须要了解：

1. metadata 的类型下的 HeaderType 是什么？
2. metadata 经过位移后，最后扮演（cast）成的类型 FullMetadata<T> * 是什么？
3. FullMetadata<T> 的成员 destroy 是什么？
4. 由 metadata 向低地址空间位移一个 T::HeaderType 长度的位置存放的是什么？

1. metadata 的类型下的 HeaderType 是什么？

我们已经从前文中 HeapObject 的头文件中得知 metadata 的类型是 HeapMetadata ，而在 include/swift/Runtime/HeapObject.h 中我们又可以找到：

struct InProcess;

template <typename Target> struct TargetHeapMetadata;
using HeapMetadata = TargetHeapMetadata<InProcess>;
复制代码

所以我们可以看到 HeapMetadata 的真身其实是 TargetHeapMetadata<InProcess> 。

我们现在要接着查证 TargetHeapMetadata 的内容。我们可以搜索 struct TargetHeapMetadata 在 include/swift/ABI/Metadata.h 中找到如下内容：

template <typename Runtime>
struct TargetHeapMetadata : TargetMetadata<Runtime> {
  using HeaderType = TargetHeapMetadataHeader<Runtime>;

  TargetHeapMetadata() = default;
  constexpr TargetHeapMetadata(MetadataKind kind)
    : TargetMetadata<Runtime>(kind) {}
#if SWIFT_OBJC_INTEROP
  constexpr TargetHeapMetadata(TargetAnyClassMetadata<Runtime> *isa)
    : TargetMetadata<Runtime>(isa) {}
#endif
};
复制代码

于是我们知道了 metadata 类型下的 HeaderType 就是 TargetHeapMetadataHeader<InProcess> 。其定义也可以在 include/swift/ABI/Metadata.h 中被找到：

template <typename Runtime>
struct TargetHeapMetadataHeader
    : TargetHeapMetadataHeaderPrefix<Runtime>,
      TargetTypeMetadataHeader<Runtime> {
  constexpr TargetHeapMetadataHeader(
      const TargetHeapMetadataHeaderPrefix<Runtime> &heapPrefix,
      const TargetTypeMetadataHeader<Runtime> &typePrefix)
    : TargetHeapMetadataHeaderPrefix<Runtime>(heapPrefix),
      TargetTypeMetadataHeader<Runtime>(typePrefix) {}
};
复制代码

2. metadata 经过位移后，最后扮演（cast）成的类型 FullMetadata * 是什么？

我们同样可以在 include/swift/ABI/Metadata.h 中找到如下内容：

template <class T> struct FullMetadata : T::HeaderType, T {
  typedef typename T::HeaderType HeaderType;

  FullMetadata() = default;
  constexpr FullMetadata(const HeaderType &header, const T &metadata)
    : HeaderType(header), T(metadata) {}
};
复制代码

所以我们可以知道： metadata 经过位移后，最终将会被扮演（cast）成 FullMetadata<HeapMetadata> * 。

根据 FullMetadata<T> 的定义， FullMetadata<T> 被特化成 FullMetadata<HeapMetadata> 之后将继承 TargetHeapMetadataHeader<InProcess> 和 TargetHeapMetadata<InProcess> 。

又根据我们之前的考证：

• 因为 FullMetadata 的第一继承目标 TargetHeapMetadataHeader 本身没有数据成员，要考证其数据成员，我们仅需要展开 TargetHeapMetadataHeader 的继承目标 TargetHeapMetadataHeaderPrefix 和 TargetTypeMetadataHeader ，进而就可以知道 FullMetadata 的一部分数据成员。

  我们可以在 include/swift/ABI/Metadata.h 中找到上述两个类型的定义：

  template <typename Runtime>
  struct TargetTypeMetadataHeader {
    /// A pointer to the value-witnesses for this type.  This is only
    /// present for type metadata.
    TargetPointer<Runtime, const ValueWitnessTable> ValueWitnesses;
  };
  
  ...
  
  template <typename Runtime>
  struct TargetHeapMetadataHeaderPrefix {
    /// Destroy the object, returning the allocated size of the object
    /// or 0 if the object shouldn't be deallocated.
    TargetPointer<Runtime, HeapObjectDestroyer> destroy;
  };
  复制代码

  我们不难得出 FullMetadata<HeapMetadata> 下第一个数据成员是 ：

  TargetPointer<Runtime, HeapObjectDestroyer> destroy;
  复制代码

  第二个数据成员是：

  TargetPointer<Runtime, const ValueWitnessTable> ValueWitnesses;
  复制代码

• 而 FullMetadata 的第二继承目标 TargetHeapMetadata 本身也没有数据成员，要考证其数据成员，我们仅需要展开 TargetHeapMetadata 的继承目标 TargetMetadata ，进而就可以知道 FullMetadata 剩下的数据成员。

  我们可以在 include/swift/ABI/Metadata.h 中找到上述这个类型的定义：

  template <typename Runtime>
  struct TargetMetadata {
    using StoredPointer = typename Runtime::StoredPointer;
    
    ...
    
  private:
    /// The kind. Only valid for non-class metadata; getKind() must be used to get
    /// the kind value.
    StoredPointer Kind;
    
    ...
  }
  复制代码

  我们不难得出 FullMetadata<HeapMetadata> 的第三个数据成员是：

  StoredPointer Kind;
  复制代码

那么 TargetPointer 和 StoredPointer 又是什么呢？

在 include/swift/ABI/Metadata.h 中我们可以找到 TargetPointer 的定义：

template <typename Runtime, typename T>
using TargetPointer = typename Runtime::template Pointer<T>;
复制代码

我们看到 TargetPointer 最后实际上会使用模板参数 Runtime 内的 Poitner 这个类型。所以「寻找 TargetPointer 的定义」这个任务现在转化为了寻找模板参数 Runtime 的特化目标类型内的 Poitner 这个类型的定义。

而我们在 InProcess ——也就是上述类型的模板参数 Runtime 的特化目标中就可以找到 StoredPointer 和 Pointer 的定义：

struct InProcess {
  using StoredPointer = uintptr_t;
  
  ...
  
  template <typename T>
  using Pointer = T*;
  
  ...
}
复制代码

我们将上述 Pointer 和 StoredPointer 定义代入之后，可以得到如下结构：

struct FullMetadata<HeapMetadata> {
  HeapObjectDestroyer * destroy;
  const ValueWitnessTable * ValueWitnesses;
  uintptr_t Kind;
}
复制代码

最后在 include/swift/ABI/Metadata.h 中找到 HeapObjectDestroyer 的定义：

using HeapObjectDestroyer =
  SWIFT_CC(swift) void(SWIFT_CONTEXT HeapObject *);
复制代码

我们可以看到 destroy 其实就是一个指向 SWIFT_CC(swift) void (*)(SWIFT_CONTEXT HeapObject *) 函数指针的一个成员。其中， SWIFT_CC 和 SWIFT_CONTEXT 这两个宏的内容在 include/swift/Runtime/Config.h 内，为编译器提供 Swift 专属的调用规制（calling convention，我也不知道这个字怎么译，自己想的译法）方面的标识符。所以最终这个函数指针会指向一个 Swift 函数。

将 HeapObjectDestroyer 的定义代入 FullMetadata<HeapMetadata> 后我们不难得出下图：

3. FullMetadata 的成员 destroy 是什么？

如上图所示： destroy 是一个指向 void (*)(HeapObject *) 函数指针的一个成员，而这个函数是一个 Swift 函数。

4. 由 metadata 向低地址空间位移一个 T::HeaderType 长度的位置存放的是什么？

我们可以看到， metadata 首先被扮演成了 T::HeaderType * 。在这里我们代入特化后的结果既是 HeapMetadata::HeaderType 。然后从上图得知， HeapMetadata::HeaderType 的长度是两个指针的长度，那么 metadata 向低地址空间位移一个 HeapMetadata::HeaderType 长度后实际上会跑到 destroy 这个成员的地址上。最后我们将指针扮演成 FullMetadata<HeapMetadata> * ，那么我们将以 FullMetadata<HeapMetadata> 来观察这个指针背后的内容。

在这里我可以画图来进行直观的说明：

同时，我们也证明了 swift_release 的形式参数是 HeapObject * 在这里只是一种编程技巧——其为该指针背后所指向的内存提供一个在 C/C++ 中访问的途径。

但是 HeapObject 中的 metadata 又是怎么来的？ metadata 指向的内存空间后两个指针长度为什么会是这个类的 destroy 函数？从逻辑上说，要回答这个问题，更好的方法是考察 ListNode 实例的分配过程，而不是释放过程。

追踪 ListNode 实例的内存分配过程

我们再次看到我们之前生成的 SIL 中的一部分内容：

// ListNode.init(_:)
sil hidden @$s9CallStack8ListNodeCyACSicfc : $@convention(method) (Int, @owned ListNode) -> @owned ListNode {
  ...
} // end sil function '$s9CallStack8ListNodeCyACSicfc'
复制代码

是的，我们第一时间会想到要在 init(_:) 函数对应的 SIL 函数中去寻找线索。但是很可惜，这里面没有和 metadata 相关的内容。但是当我们搜索 init(_:) 函数在 SIL 中对应的名字： $s9CallStack8ListNodeCyACSicfc 时，我们会发现有一个叫 $s9CallStack8ListNodeCyACSicfC 的 SIL 函数（对应 Swift 函数名： ListNode.__allocating_init(_:) ）调用了 init(_:) 函数。

// ListNode.__allocating_init(_:)
sil hidden @$s9CallStack8ListNodeCyACSicfC : $@convention(method) (Int, @thick ListNode.Type) -> @owned ListNode {
// %0                                             // user: %4
bb0(%0 : $Int, %1 : $@thick ListNode.Type):
  %2 = alloc_ref $ListNode                        // user: %4
  // function_ref ListNode.init(_:)
  %3 = function_ref @$s9CallStack8ListNodeCyACSicfc : $@convention(method) (Int, @owned ListNode) -> @owned ListNode // user: %4
  %4 = apply %3(%0, %2) : $@convention(method) (Int, @owned ListNode) -> @owned ListNode // user: %5
  return %4 : $ListNode                           // id: %5
} // end sil function '$s9CallStack8ListNodeCyACSicfC'
复制代码

注意到上述代码的第 5 行，我们不难推断出： ListNode.__allocating_init(_:) 这个函数应该是使用了 alloc_ref 这条 SIL 指令来完成对 ListNode 实例的内存分配工作的。但是在这里，整段代码依然没有 metadata 的任何线索。

调查 __allocating_init：LLVM IR 视角

这时候，我们不妨将视野降低一个层级：我们直接考察 LLVM IR，看看里面会有什么内容。首先使用 swiftc -emit-ir CallStack.swift > CallStack.swift.ll 来生成 CallStack.swift 的 LLVM IR。我们可以通过搜索 $s9CallStack8ListNodeCyACSicfC 在第 232 行找到 ListNode.__allocating_init(_:) 函数在 LLVM IR 中对应的函数：

define hidden swiftcc %T9CallStack8ListNodeC* @"$s9CallStack8ListNodeCyACSicfC"(i64, %swift.type* swiftself) #0 {
entry:
  %2 = call swiftcc %swift.metadata_response @"$s9CallStack8ListNodeCMa"(i64 0) #7
  %3 = extractvalue %swift.metadata_response %2, 0
  %4 = call noalias %swift.refcounted* @swift_allocObject(%swift.type* %3, i64 32, i64 7) #2
  %5 = bitcast %swift.refcounted* %4 to %T9CallStack8ListNodeC*
  %6 = call swiftcc %T9CallStack8ListNodeC* @"$s9CallStack8ListNodeCyACSicfc"(i64 %0, %T9CallStack8ListNodeC* swiftself %5)
  ret %T9CallStack8ListNodeC* %6
}
复制代码

我们可以在这个 LLVM IR 函数中清晰地看到 metadata 这个字。那么我们来分析一下这段 LLVM IR 函数：

%
@

首先第一句：

%2 = call swiftcc %swift.metadata_response @"$s9CallStack8ListNodeCMa"(i64 0)
复制代码

通过阅读 call 这条 LLVM IR 指令的文档，我们不难得知这句的意思是通过使用 Swift 的调用规制（calling convention）来调用 LLVM 函数 $s9CallStack8ListNodeCMa ，并且传入一个值为 0 的 i64 类型（不难猜测就是 64 位整型），在获得了一个类型为 %swift.metadata_response 的返回值后再赋值给 %2 。

那么问题来了： $s9CallStack8ListNodeCMa 又是什么？实际上，如果你在 profiling 的时候足够仔细，你可能会发现分配 Swift 对象实例的调用栈里面会出现 type metadata accessor 这种记录（抱歉我作弊了）。在后面的探索中，我们也将不难知道： $s9CallStack8ListNodeCMa 就是 type metadata accessor。

我们可以在我们导出的这份 LLVM IR 的头部找到 %swift.metadata_response 的定义：

%swift.type = type { i64 }
%swift.metadata_response = type { %swift.type*, i64 }
复制代码

其中， type 关键字是 LLVM IR 中自定义 struct 类型的关键字。 %swift.type 就是一个成员只有一个 64 位整型值的 struct ，我们可以从后面的探索得知，这就是一个 Swift 类型对应的 Objective-C meta-class。 %swift.type* 则代表一个指向 %swift.type 的指针。于是类型 %swift.metadata_response 改写成 C 语言代码实际上是：

struct {
    struct {
        int64_t metaclass;
    } SwiftType;
    struct SwiftType * swiftType;
    int64_t foo;
} MetadataResponse;
复制代码

然后第二句：

%3 = extractvalue %swift.metadata_response %2, 0
复制代码

通过阅读 extractvalue 这条 LLVM IR 指令的文档，我们不难得知这句的意思就是以 %swift.metadata_response 类型的结构观察本地变量 %2 ，将其中的第 0 个元素取出。于是我们会实际得到一个 %swift.type * 类型的值，然后赋值给 %3 。

接着第三句：

%4 = call noalias %swift.refcounted* @swift_allocObject(%swift.type* %3, i64 32, i64 7) #2
复制代码

这句的意思是调用 @swift_allocObject 函数，将本地变量 %3 的内容以 %swift.type* 的类型传入第一个参数，将 32 以 i64 的类型传入第二个参数，将 7 以 i64 的类型传入第三个参数，最后将返回值以 %swift.refcounted* 类型赋值给本地变量 %4 。

你可能不知道 noalias 是什么意思。其实理不理解 noalias 在这里没有什么影响， noalias 在修饰返回值时表示： @swift_allocObject 函数的返回值不会在该函数的执行过程中通过该函数的参数这个途径被访问。

接着第四句：

%5 = bitcast %swift.refcounted* %4 to %T9CallStack8ListNodeC*
复制代码

这表示，将本地变量 %4 中的内容从 %swift.refcounted* 类型扮演（cast）成 %T9CallStack8ListNodeC* 类型（用 Swift 来表述就是：CallStack 模块内的 ListNode 这个类的引用），然后赋值给本地变量 %5 。

接着第五句：

%6 = call swiftcc %T9CallStack8ListNodeC* @"$s9CallStack8ListNodeCyACSicfc"(i64 %0, %T9CallStack8ListNodeC* swiftself %5)
复制代码

这句的意思是以 Swift 的调用规制调用 @"$s9CallStack8ListNodeCyACSicfc" 这个函数（也就是 ListNode.init(_:) ），将 0 以 i64 类型传入第一个参数，将本地变量 %5 中的内容以 %T9CallStack8ListNodeC* 的类型（也就是 ListNode 的引用）传入第二个参数，并且给出第二个参数是 self 参数（ swiftself ）的提示，然后将返回值以 %T9CallStack8ListNodeC* （ ListNode 的引用）类型赋值给本地变量 %6 。

最后第六句：

ret %T9CallStack8ListNodeC* %6
复制代码

将本地变量 %6 中的内容以 %T9CallStack8ListNodeC* （ ListNode 的引用）类型返回。

综上，我们可以将以上 LLVM IR 改写成以下 C-like 的语言：

typealias %swift.type * SwiftTypeRef;
typealias %swift.refcounted * SwiftRefCountedRef;
typealias %swift.metadata_response MetadataResponse;
#define ListNodeTypeMetadataAccessor $s9CallStack8ListNodeCMa

ListNode * ListNode__allocating_init(int64_t arg1, SwiftTypeRef self) {
    MetadataResponse %2 = ListNodeTypeMetadataAccessor(0);
    SwiftTypeRef %3 = %2.swiftType;
    SwiftRefCountedRef %4 = swift_allocObject(%3, 32, 7);
    ListNode * %5 = (ListNode *) %4;
    ListNode * %6 = ListNodeInit(0, %5);
    return %6;
}
复制代码

于是我们可以看到， ListNode.__allocating_init(_:) 确实通过调用 type metadata accessor（既 $s9CallStack8ListNodeCMa 这个函数）访问了 ListNode 的 metadata，并且以此分配了 ListNode 实例的内存空间。

调查 Type Metadata Accessor：LLVM IR 视角

接下来我们再来考察 ListNode 的 type metadata accessor（也就是 $s9CallStack8ListNodeCMa 这个函数），看看 Swift 到底是如何在运行时获取一个 class 类型的 metadata 的。搜索 $s9CallStack8ListNodeCMa 我们可以在第 242 行找到这个函数的定义：

; Function Attrs: nounwind readnone
define hidden swiftcc %swift.metadata_response @"$s9CallStack8ListNodeCMa"(i64) #4 {
entry:
  %1 = load %swift.type*, %swift.type** @"$s9CallStack8ListNodeCML", align 8
  %2 = icmp eq %swift.type* %1, null
  br i1 %2, label %cacheIsNull, label %cont

cacheIsNull:                                      ; preds = %entry
  %3 = call %objc_class* @swift_getInitializedObjCClass(%objc_class* bitcast (i64* getelementptr inbounds (<{ void (%T9CallStack8ListNodeC*)*, i8**, i64, %objc_class*, %swift.opaque*, %swift.opaque*, i64, i32, i32, i32, i16, i16, i32, i32, <{ i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor }>*, i8*, i64, i64, i64 (%T9CallStack8ListNodeC*)*, void (i64, %T9CallStack8ListNodeC*)*, { i8*, %TSi* } (i8*, %T9CallStack8ListNodeC*)*, i64 (%T9CallStack8ListNodeC*)*, void (i64, %T9CallStack8ListNodeC*)*, { i8*, %T9CallStack8ListNodeCSg* } (i8*, %T9CallStack8ListNodeC*)*, %T9CallStack8ListNodeC* (i64, %swift.type*)* }>, <{ void (%T9CallStack8ListNodeC*)*, i8**, i64, %objc_class*, %swift.opaque*, %swift.opaque*, i64, i32, i32, i32, i16, i16, i32, i32, <{ i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor }>*, i8*, i64, i64, i64 (%T9CallStack8ListNodeC*)*, void (i64, %T9CallStack8ListNodeC*)*, { i8*, %TSi* } (i8*, %T9CallStack8ListNodeC*)*, i64 (%T9CallStack8ListNodeC*)*, void (i64, %T9CallStack8ListNodeC*)*, { i8*, %T9CallStack8ListNodeCSg* } (i8*, %T9CallStack8ListNodeC*)*, %T9CallStack8ListNodeC* (i64, %swift.type*)* }>* @"$s9CallStack8ListNodeCMf", i32 0, i32 2) to %objc_class*))
  %4 = bitcast %objc_class* %3 to %swift.type*
  store atomic %swift.type* %4, %swift.type** @"$s9CallStack8ListNodeCML" release, align 8
  br label %cont

cont:                                             ; preds = %cacheIsNull, %entry
  %5 = phi %swift.type* [ %1, %entry ], [ %4, %cacheIsNull ]
  %6 = insertvalue %swift.metadata_response undef, %swift.type* %5, 0
  %7 = insertvalue %swift.metadata_response %6, i64 0, 1
  ret %swift.metadata_response %7
}
复制代码

这个函数牵扯到 SSA Form phi nodes 的还原，不好做句读，有兴趣可以直接在这里获取免费正版的 SSA Book 学习一下 SSA Form 相关的知识。这里我直接展示其改写成 C-like 伪代码后的样子：

typealias %swift.type * SwiftTypeRef;
typealias %swift.metadata_response MetadataResponse;
#define ListNodeTypeMetadataAccessor $s9CallStack8ListNodeCMa
#define listNodeMetadataRecord $s9CallStack8ListNodeCMf
static SwiftTypeRef * ListNodeSwiftType = $s9CallStack8ListNodeCML;

MetadataResponse ListNodeTypeMetadataAccessor(i64 arg1) {
    SwiftTypeRef swiftType;
    
    if (*ListNodeSwiftType == NULL) {
        swiftType = (SwiftTypeRef)swift_getInitializedObjCClass(&(listNodeMetadataRecord -> objc_class));
        * ListNodeSwiftType = swiftType
    } else {
        swiftType = * ListNodeSwiftType
    }
    
    MetadataResponse metadataResponse = {
        swiftType,
        0,
    };
    
    return metadataResponse;
}
复制代码

我们可以看到：

• 首先这个函数将检查全局变量 ListNodeSwiftType （也就是 $s9CallStack8ListNodeCML 这个符号）的内容：
  • 如果为 0 ，那么就会将 listNodeMetadataRecord -> objc_class 传入 swift_getInitializedObjCClass 来获得 ListNode 的 swiftType ；
  • 如果不是 0 ，那么会直接使用 ListNodeSwiftType 作为 ListNode 的 swiftType ；
• 之后再将 ListNode 的 swiftType 构造成 metadataResponse 并且返回。

要判断上述代码中，我们会执行哪个条件分支，我们必须首先知道 ListNodeSwiftType 也就是 $s9CallStack8ListNodeCML 的内容。在我们导出的 LLVM IR 文件的第 37 行我们可以找到如下内容：

@"$s9CallStack8ListNodeCML" = internal global %swift.type* null, align 8
复制代码

所以我们知道了，对于我们编译的 ListNode 这段代码， $s9CallStack8ListNodeCML 也就是 ListNodeTypeMetadata 会是 null （也就是 0 ）。同时我们也可以在 Hopper 中搜索 $s9CallStack8ListNodeCML 来进行求证。

可以看到 $s9CallStack8ListNodeCML 确实是 0 。也就是说在我们的代码的运行过程中， ListNode 的 type metadata accessor 会调用 swift_getInitializedObjCClass 来帮助生成 ListNode 类型的 metadata 记录。

在上面这段 LLVM IR 中， swift_getInitializedObjCClass(&(listNodeMetadataRecord -> objc_class)) 这句所对应的 LLVM IR 一般被认为是大部分 LLVM 学习者都容易搞混的点。我这里将这句的 LLVM IR 抽出来单独讲一下：

%3 = call %objc_class* @swift_getInitializedObjCClass(%objc_class* bitcast (i64* getelementptr inbounds (<{ void (%T9CallStack8ListNodeC*)*, i8**, i64, %objc_class*, %swift.opaque*, %swift.opaque*, i64, i32, i32, i32, i16, i16, i32, i32, <{ i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor }>*, i8*, i64, i64, i64 (%T9CallStack8ListNodeC*)*, void (i64, %T9CallStack8ListNodeC*)*, { i8*, %TSi* } (i8*, %T9CallStack8ListNodeC*)*, i64 (%T9CallStack8ListNodeC*)*, void (i64, %T9CallStack8ListNodeC*)*, { i8*, %T9CallStack8ListNodeCSg* } (i8*, %T9CallStack8ListNodeC*)*, %T9CallStack8ListNodeC* (i64, %swift.type*)* }>, <{ void (%T9CallStack8ListNodeC*)*, i8**, i64, %objc_class*, %swift.opaque*, %swift.opaque*, i64, i32, i32, i32, i16, i16, i32, i32, <{ i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, i32, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor, %swift.method_descriptor }>*, i8*, i64, i64, i64 (%T9CallStack8ListNodeC*)*, void (i64, %T9CallStack8ListNodeC*)*, { i8*, %TSi* } (i8*, %T9CallStack8ListNodeC*)*, i64 (%T9CallStack8ListNodeC*)*, void (i64, %T9CallStack8ListNodeC*)*, { i8*, %T9CallStack8ListNodeCSg* } (i8*, %T9CallStack8ListNodeC*)*, %T9CallStack8ListNodeC* (i64, %swift.type*)* }>* @"$s9CallStack8ListNodeCMf", i32 0, i32 2) to %objc_class*))
复制代码

我们可以看到，这一行实在太长。我们可以对其做一下美化：我们将内联在 LLVM IR 指令中的类型结构抽出命名为 %SwiftTypeMetadata ，并且将这句 LLVM IR 分解为多句，于是可得：

%0 = i64* getelementptr inbounds (%SwiftTypeMetadata, %SwiftTypeMetadata * @"$s9CallStack8ListNodeCMf", i32 0, i32 2)
%1 = %objc_class* bitcast (%objc_class* %0 to %objc_class*)
%3 = call %objc_class* @swift_getInitializedObjCClass(%objc_class* %1)
复制代码

这下我们可以很清晰地进行解释了：

• 首先我们要知道， getelementptr 这个指令是用来获得从某一个基地址开始之后某一个元素的 地址 的。很多 LLVM 学习者都会把这条指令理解成「获取某一个基地址开始之后的某一个元素」，这是错的。

  在这里，这条指令以 $s9CallStack8ListNodeCMf 为基础地址，先以 %SwiftTypeMetadata * 类型审视这个地址，移动到从 0 数起的第 0 个元素（ i32 0 的作用）后，再以 %SwiftTypeMetadata 类型审视当前地址，移动到从 0 数起的第 2 个元素（ i32 2 的作用），最后将经过两次移动之后的地址赋值给 %0 。

  于是我们这里实际上获得了一个指向 $s9CallStack8ListNodeCMf 第二个地址的指针；

• 之后我们再用 bitcast 将 %0 扮演成 %objc_class* 再赋值给 %1 ；

• 然后调用 @swift_getInitializedObjCClass ，并将 %1 以 %objc_class* 作为参数传入。

那么问题来了， %SwiftTypeMetadata 这个类型到底是什么样子的？因为上述 LLVM IR 中我们以 %SwiftTypeMetadata 来审视了 $s9CallStack8ListNodeCMf 这个符号，所以我们不妨看看 $s9CallStack8ListNodeCMf 的内容是什么。在我们生成的 LLVM IR 的第 38 行可以看见 $s9CallStack8ListNodeCMf 的内容。为了方便大家观察，这里我将这个结构体的内容画了出来：

我们又知道，我们将指向上图所示字段中从 0 开始数第 2 个字段的指针扮演成了 %objc_class* （一个指向 Objective-C class 的指针），那么我们不妨用 Objective-C class 的结构体来看看 $s9CallStack8ListNodeCMf 的内容：

可以看见，这个结构体中确实隐含着一个 Objective-C class 结构体。

实际上，如果你记性好，那么你还会发现，这个结构体的第一个成员就是我们的 ListNode.__deallocating_deinit 函数——也就是摧毁（destroy）函数。根据我们前面对 Swift 运行时中 _swift_dealloc_release 函数的研究，我们不难产生直觉——莫非这个结构体从 0 开始数第 2 个成员就是 HeapObject 的 metadata 指针指向的目标？

目前我们还不能肯定，因为代码还没有研究完，我们还不知道后面会发生什么。

接下来我们必须知道 swift_getInitializedObjCClass 这个函数做了什么。

搜索我们导出的 LLVM IR 文件，我们可以发现 swift_getInitializedObjCClass 是一个只有声明（ declare ）没有定义（ define ）的文件。这说明这个函数将在编译时被链接到目标文件，也就是说，这是一个存在于 Swift 标准库中的函数。

调查 swift_getInitializedObjCClass

于是我们可以在 Swift 源代码中搜索 swift_getInitializedObjCClass ，并在 stdlib/public/runtime/SwiftObject.mm 文件中发现如下内容：

Class swift::swift_getInitializedObjCClass(Class c) {
  // Used when we have class metadata and we want to ensure a class has been
  // initialized by the Objective-C runtime. We need to do this because the
  // class "c" might be valid metadata, but it hasn't been initialized yet.
  return [c class];
}
复制代码

是的，这个函数仅仅向传入的参数 c 发送了 [Class +class] 消息，根据 Objective-C 运行时的知识，这将确保 c 在 Objective-C 运行时中被初始化（既 [Class +initialize] 被调用）。然后这个函数会返回 [c class] ——既 c 本身。于是我们可以看见，这个函数就如其名字一样——仅仅只是保证这个 Objective-C class 被初始化而已。

Type Metadata Accessor 小结

我们可以看到 swift_getInitializedObjCClass 在这里并没有起到什么偷天换日的作用，所以我们之前的直觉是对的： HeapObject 的 metadata 指针就是指向 $s9CallStack8ListNodeCMf 开始的结构体上从 0 开始数第 2 个元素的。

我们可以画图做一下说明：

Type Metadata 生成

可以 type metadata 又是怎么生成的呢？我们可以看到 lib/IRGen/GenMeta.cpp 文件中的 SingletonClassMetadataBuilder 这个 C++ 类。这个类将通过使用 LLVM 的 API 来为 ListNode 生成 type metadata 的 LLVM IR。

class SingletonClassMetadataBuilder :
    public ClassMetadataBuilderBase<SingletonClassMetadataBuilder> {
    
    ...
}
复制代码

你会发现这份文件中还有其他的 class metadata builder，实际上，根据 class 是否套用 @_fixed_layout 属性，是否是模块外定义的，是否是泛型的这三点，Swift 会有不同的 type metadata 生成策略。这里我还没有时间一一研究。

我们可以看到其继承自 ClassMetadataBuilderBase<SingletonClassMetadataBuilder> ，而我们又可以在同一个文件内找到 ClassMetadataBuilderBase 的定义：

template<class Impl>
class ClassMetadataBuilderBase : public ClassMetadataVisitor<Impl> {
  ...
}
复制代码

不难看出， ClassMetadataBuilderBase<Impl> 继承自 ClassMetadataVisitor<Impl> ，而 ClassMetadataVisitor 就是非常经典的 visitor 模式的应用了。

我们看到 ClassMetadataVisitor 的 layout 函数，这就是具体生成 type metadata 的地方。

template <class Impl> class ClassMetadataVisitor
    : public NominalMetadataVisitor<Impl>,
      public SILVTableVisitor<Impl> {
public:
  void layout() {
    // HeapMetadata header.
    asImpl().addDestructorFunction();

    // Metadata header.
    super::layout();

    asImpl().addSuperclass();
    asImpl().addClassCacheData();
    asImpl().addClassDataPointer();

    asImpl().addClassFlags();
    asImpl().addInstanceAddressPoint();
    asImpl().addInstanceSize();
    asImpl().addInstanceAlignMask();
    asImpl().addRuntimeReservedBits();
    asImpl().addClassSize();
    asImpl().addClassAddressPoint();
    asImpl().addNominalTypeDescriptor();
    asImpl().addIVarDestroyer();

    // Class members.
    addClassMembers(Target);
  }
}
复制代码

其中 super::layout() 调用的是 NominalMetadataVisitor<Impl> 的 layout 函数，我们在这里也将其贴出来：

template <class Impl> class NominalMetadataVisitor {
public:
  void layout() {
    // Common fields.
    asImpl().addValueWitnessTable();
    asImpl().noteAddressPoint();
    asImpl().addMetadataFlags();
  }
}
复制代码

将 layout 函数体内的函数们逐一展开后，我们就可以将之前获得的 ListNode 的 type metadata 中所有的字段都对上号了：

一般性非泛型非 @_fixed_layout 的 Swift 对象内存布局及 type metadata 布局

同时，在这里我们也可以给出 Swift 中一般非泛型，非 @_fixed_layout 类的内存布局及相应的 type metadata 内存布局：

思考题：你能说明一下 Swift 为什么要这样设计吗？

超长链表爆栈原因小结

至此，我们可以总结出，对于使用 ListNode 这种构型的链表，其被释放的过程中：

1. 根节点首先进入释放过程；
2. 根节点的 __deallocating_deinit 又调用了根节点的 deinit 函数；
3. 根节点的 deinit 又调用了一个由编译器自动生成的外联的 ListNode 成员摧毁过程；
4. 编译器自动生成的外联的 ListNode 成员摧毁过程又调用了 swift_release 来解除对 next 节点的强引用；
5. swift_release 调用 _swift_release_ 来解除对 next 节点的强引用；
6. 因为这里只有一处对这个 next 节点进行强引用且没有 unowned 引用，所以 _swift_release_ 最终会通过 _swift_release_dealloc 来解除对 next 节点强引用
7. _swift_release_dealloc 通过调用 ListNode 的 __deallocating_deinit 函数来摧毁 next 节点；
8. next 节点引用计数变成 0 ，进入释放过程；

我们可以通过查看完全的调用栈来查证上述表述是不是真的。

为了查看完全的调用栈而不是 Debug Navigator 中那点调用栈摘要，我们要点击 Xcode 编辑区左上角「四个方格」的图标，然后点击 Disassembly，再点击当前栈帧 ListNode.deinit 打开全部调用栈。最后我们可以看到下图：

我们可以注意到，上图中没有 swift_release 和 _swift_release_ 两个函数的过程活动记录（procedure activation record，可以粗浅理解为调用栈和 CPU 上寄存器中的记录）。这是因为编译器对这两个函数做了尾部调用优化（TCO），将 call 系列指令（考虑到 32 位和 64 位平台上的完成相同功能的指令名字并不相同，我这里及以下都将称之为「系列指令」）改成了 jmp 系列指令，这样后继的 _swift_release_ 和 _swift_release_dealloc 函数就可以复用起始函数 swift_release 的调用栈了，而我们观察到的就是复用了之后的调用栈。

我们可以在 Xcode 中打下 symbolic breakpoints 来求证。

按下 command + 8 将 Navigator 面板切换到 Breakpoint Navigator。按下面板左下角的 "+" 按钮新增两个 symbolic breakpoints： swift_release 和 _swift_release_ 。

要注意，在节点生成过程中也会触发引用计数，所以这个时候 swift_release 也会被调用，所以我们首先要关掉这两个 breakpoints：

然后在 print("Bar") 这个地方打上 breakpoint：

再次运行程序，待程序运行到 print("Bar") 在 breakpoint 除暂停之后打开 swift_relase 和 _swift_release_ 的断点再继续。之后我们将看到程序将在 swift_relase 和 _swift_release_ 的入口处中止。

我们可以看到 swift_relase 对 _swift_release_ 的调用以及 _swift_release_ 对 _swift_release_dealloc 的调用全部都是由 jmp 系列指令完成的。这就是尾部调用优化（TCO）在指令集这个微观层面的体现。

libswiftCore.dylib`swift_release:
    ....
    0x7fff65730905 <+5>:  jmpq   *0x3351ac9d(%rip)         ; _swift_release
    ....
复制代码

libswiftCore.dylib`_swift_release_:
    ...
    0x7fff65730ce1 <+145>: jmp    0x7fff65731a50            ; _swift_release_dealloc
    ...
复制代码

于是我们通过观察函数的过程活动记录的方法证明了上述我们对 ListNode 的释放过程的描述是正确的。于是我们可以知道：对于以 ListNode 这种方式实现的链表的根节点被完全销毁之前，其后继节点就会被释放，然后因为再也没有对其后继节点进行强引用的地方了，于是这个后继节点也进入到了一个自动的销毁过程。这种销毁就像核裂变一样，是链式反应的，而一旦这个「反应链」很长——既链表本身很长的话就会引起爆栈。当然，爆栈的结果就是应用崩溃。

另外，我们可以观察到，编译器并没有对这个 间接递归 过程进行尾递归优化。

不会爆栈的链表的实现方法

那么用什么方法可以实现永远不会在释放时爆栈的链表呢？

方法 1: 释放时人工处理

我们可以在 ListNode 释放时考虑对 next 节点进行逆向释放，这相当于一道比较多见的面试题：反转链表。于是我们可以写出如下代码：

class ListNode {
    var val: Int
    var next: ListNode?
    
    init(_ val: Int) {
        self.val = val
        self.next = nil
    }
    
    deinit {
        var currentOrNil: ListNode? = self
        var nodes = [ListNode]()
        
        while let current = currentOrNil {
            nodes.append(current)
            currentOrNil = current.next
        }
        
        for each in nodes.reversed() {
            each.next = nil
        }
    }
}
复制代码

这样，我们将一个递归转换成循环就可以避免 ListNode 释放时后继节点连锁释放所带来的爆栈。我自己写的一个玩具级 LRUCache （之前听说某厂面试必考 LRU cache 所以写了个练手）中所使用的双向链表的 deinit 就使用了这种方法。

然而，使用这种方法构建的链表在每次释放时都要将所有链表节点插入一个动态数组，虽然动态数组插入的复杂度是 均摊 O(1) 的，但是这依然要耗费 O(n) 的辅助空间，在时间上也会多 O(n) 的开销（这也是我为什么说我写的那个 LRU cache 是玩具级的原因）。有没有什么办法可以把这些消除掉？

方法 2: 对链表节点进行 Pooling

考虑到链表是一种将内部结构特征（前驱节点或者后继节点）暴露在使用者面前的数据结构，这使得我们在使用链表的同时也不得不考虑如何去维护这个链表的内部结构，从而给我们带来了不小的智力负担。于是我们可以将其封装在一个类型内部，仅仅让这个类型可以对链表进行操作，然后再对这个类型封装出一些数据集合类型所使用的功能，这样就可以减轻使用链表时的智力负担。

关于以上这点请看星际争霸 I 的开发者撰写的在星际争霸 I 的开发过程中与链表斗智斗勇的系列文章：

I. Tough Times on the Road to Starcraft

II. Avoiding Game Crashes Related to Linked Lists

III. Explaining the Implementation Details of The Fix（抱歉，第三篇他鸽了七年了）

这样以来，我们就可以在这个类型内部套用 pooling 模式了。Pooling 是一个在计算密集型领域（如游戏客户端、大型软件客户端和大型服务器端中）常见的设计模式，其在 iOS 平台上的研发中并不常见。甚至可以说，从 Objective-C 2.0 无效化 [NSObject +allocWithZone:] 这个 API 来看，苹果是并不鼓励开发者在 Objective-C 中使用 pooling 模式的——你要 pooling 那就只能用 C++ 来进行 pooling。Pooling 模式的具体做法是：预先分配一个内存池然后在要创建对象时直接从这个内存池中划分出一部分给这个对象即可——这样我们就可以避免系统的内存分配函数需要访问操作系统中关于资源调度安排的信息这个开销，进一步提高计算性能。当然，在面对解决 ListNode 构型的链表过长而导致释放时崩溃这个问题时，这些都只是 bonus 而不是我们使用 pooling 的根本目的。

在这里我们使用 pooling 模式的根本目的在于：如果我们给每一个要使用链表的封装类型的实例都创建一个内存池，那么在释放链表时我们只需要释放这个内存池就可以了。

刚刚说了，苹果似乎并不鼓励开发者在 Objective-C 中使用 pooling 模式，其实在 Swift 中也无法简单套用 pooling 模式——因为 class 实例的内存分配过程是由 Swift 运行时掌控的。我们可以在 stdlib/public/runtime/Heap.cpp 中找到下列函数：

void *swift::swift_slowAlloc(size_t size, size_t alignMask) {
  void *p;
  // This check also forces "default" alignment to use AlignedAlloc.
  if (alignMask <= MALLOC_ALIGN_MASK) {
    p = malloc(size);
  } else {
    size_t alignment = (alignMask == ~(size_t(0)))
                           ? _swift_MinAllocationAlignment
                           : alignMask + 1;
    p = AlignedAlloc(size, alignment);
  }
  if (!p) swift::crash("Could not allocate memory.");
  return p;
}
复制代码

这就是 Swift 运行时中进行 heap 内存分配的函数，也是最终为 class 实例分配内存空间的函数，我们可以看见其当前实现是利用 C 标准库的 malloc 进行内存分配的，这个过程不可能有任何开发者的参与。为了使用 pooling 模式，我们只能使用 Swift 标准库中的 UnsafeMutablePointer 配合 struct 来实现一个内存池。

当然，你也可以尝试更「野」（野蛮、暴力之意）的路子：用 C 创建好内存池，保证好内存池中每一个实例和 Objective-C 的内存模型一致后再用 CF 对象 bridge 到 Swift 的方法将内存池中的内容 bridge 过来。这样有一个好处就是你可以得到 class 实例而不用裸操作原始指针了。

如果你对这个方法感兴趣，可以参考这篇日本 Qiita 社区（也是一个开发者社区）上的文章：

Swift の Toll-Free Bridge の実装を読む

整体设计思路如下图：

如图所示， _ListStorage 内的维护了一个内存池 buffer 、一个头部节点指针 headOffset （代表使用节点链）和一个重用节点指针 reuseHeadOffset （代表重用节点链）。在这个链表实现中，因为所有节点都在内存池中，我们可以使用节点在内存池中的偏移量来记录 next 节点的位置。

• 初始化时，头部节点指针为空（ -1 ），重用节点指针指向内存池的第一个元素，内存池内的每一个单元的 next 指针都指向下一个单元，最后一个单元的 next 指针为空（ -1 ），此时内存池上每一个单元都在重用节点链上。
• 加入时，从重用节点链上拿下头部节点（如果没有就对内存池进行扩容），插入到使用节点链的头部节点。
• 删除时，将使用节点链的头部节点拿下，并且插入到重用节点链的头部节点。

因为我们总是分配相同大小的单元，所以我们不需要像 malloc 那样在分配的时候留一个小空间来记录本次分配的空间的大小，所以这个内存池的实现会变得非常简单。

我将这个实现的完整代码放在了 GitHub 上，这里我挑几个实现中的重点说说：

• 我在 buffer 内的单元（代码中对应 bucket 这个概念）中并没有直接使用指针来表示后继节点，而是使用了节点在内存池中的偏移量来作为指针值。这么做有一点好处：我们在应用写入时复制（COW）时，整个容器仅仅需要简单复制就可以了。不然的话，我们就要一个指针一个指针来进行厘清了。

• 内存池的增长因子我设置成了 1.5

  let newCapacity = max(1, _capacity + ((_capacity + 1) >> 1))
  复制代码

  因为当我们使用 1.5 的增长因子时，操作系统将有可能有机会重复利用之前分配过的空间。这样可以起到减少内存碎片的效果。

  举例如下：

  第一次分配内存: 1  2
  
  第二次分配内存: .  .  1  2  3
  
  第三次分配内存: .  .  .  .  .  1  2  3  4  5
  
  第四次分配内存：.  .  .  .  .  .  .  .  .  .  1  2  3  4  5  6  7  8
  
  第五次分配内存：.  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  .  . 1 2 3 4 5 6 7 8 9 A B C
  
  第六次分配内存：1  2  3  4  5  6  7  8  9  A  B  C  D  E  F  11 12
  复制代码

  我们可以看到，在第六次分配内存的时候，操作系统存在一个重复利用之前分配过的空间的机会。

  Swift 中 Array 及 ContiguousArray 的增长因子则是 2。我们可以看到 stdlib/public/core/ArrayShared.swift 这个文件中有如下内容：

  @inlinable
  internal func _growArrayCapacity(_ capacity: Int) -> Int {
      return capacity * 2
  }
  复制代码

  这句就控制了 Swift Array 和 ContiguousArray 的扩容因子。所以对于 Swift 的 Array 及 ContiguousArray 而言，操作系统将没有这种重复利用之前分配过的空间的机会。

  在实际工程中，腾讯 IEG 出品的 RapidJSON 和 Facebook 出品的 FBFolly 都是使用的 1.5 为动态数组类型的容器的增长因子。

  Clang 和 GCC 的 C++ STL 中的 std::vector 增长因子也是 2。

• 我们可以通过让我们的链表类型遵从于 Sequence 和 Collection 以让我们能更加方便的在 Swift 中使用这个类型（我在范例代码中已经这么做了）。

  但是要注意的是，因为 Collection 协议自带 Index ，而对链表使用索引访问的时间复杂度是 O(n) 的，加上 Collection 在实现了 subscript 的 getter 之后就会自动实现一个使用这个 subscript 的 iterator ，所以如果这时候我们通过 Swift 中一般遍历 Sequence 和 Collection 的方法（如 for-in 循环）来遍历链表，那么这个性能将会非常差（时间复杂度升至 O(n^2)）。

  所以，你应该自己实现一个 iterator 来完成 O(n) 的遍历时间复杂度（我在范例代码中也已经这么做了）。

• 如果要用于生产环境，你应该还要让这个链表类型遵从于 RangeReplaceableCollection 。这个协议有一个叫 removeAll(keepingCapacity:) 的函数可以跟我们约定一个释放内存池中无用空间的接口。

方法 3: 仅对链表节点的引用进行 Pooling

上述方法太麻烦了，还要自己造内存池（虽然这是个很简单的特例）。有没有什么更简单的方法？

还是有的。

我们可以依然回到使用 class 来创建链表节点这个基本方法，然后选择仅仅对链表节点的引用进行 pooling。这有点像 UITableView 内部对 reusable cells 进行重用的处理方法；Facebook 的 ComponentKit 也会在 view 层级的每一个 view 内部建立一个 reuse pool 来对由 ComponentKit 控制的 subviews 进行重用。这些例子中都仅仅只对对象指针进行了 pooling 而不是对象整体。

整体设计思路如下图：

如图所示， _ListStorage 维护了一个有关链表节点的数组 nodes 、头节点在数组中的偏移量 headNodeIndex 可重用节点在数组中的索引。同时，在链表节点中我们依然要使用数组内偏移量来记录 next 节点在数组中的位置。这样做在这个实现中的好处主要是可以规避引用计数。

我也将这个实现的完整代码放在了 GitHub 上。

同样，对于这个链表实现，如果要用于生产环境，你应该还要让这个链表类型遵从于 RangeReplaceableCollection 。这个协议有一个叫 removeAll(keepingCapacity:) 的函数可以跟我们约定一个释放数据结构中无用空间的接口。

同时我也在范例项目内做了一个简易的 benchmark，方法二的性能明显优于方法三。