在最近排查问题的过程中，发现经常需要和字典的汇编码打交道。在阅读汇编代码的过程中，由于对字典的内存布局不够了解，而对应的汇编码又经过了高度优化，因此排查成本极高。经过一段时间的学习和挣扎才勉强能看懂代码，再加上笔者一直对 Swift 源码比较感兴趣，因此谨以此文记录并且交流下学习过程。
俗话说授人以鱼不如授人以渔，本文只会分析字典的下标访问方法的源码调试和汇编实现，希望起到抛砖引玉额效果。
在四年前的博客 中，我从代码层面介绍了 Swift 字典的实现。四年过去了，Swift 字典的实现没有发生很大的改动，因此这篇文章也还具备一定的参考价值。
由于汇编中存在较多对字节内存布局的直接操作，所以在开始学习前有必要简单介绍下字典的内部布局，在源码中其实已经有了明确的描述。
如果不考虑兼容 ObjC 中的 NSDictionary 的场景，Swift 原生的字典最终内部会存储一个 __RawDictionaryStorage 类的实例。我们知道类实例在 0x0 和 0x8 的偏移分别是它的 isa 指针和引用计数，因此真正的成员变量是从 0x10 开始布局的。它们分别是：
- 0x10: count，表示字典内部键值对的数量
- 0x18: capacity，表示在不触发扩容之前，当前最多能存储多少个键值对，如果存不下会触发扩容的流程。
- 0x20: _scale，中文翻译叫规模，这是字典非常关键的一个属性，2 的 scale 次方(后面记为
2^scale) 是 bucket 的个数，也就是物理上”真正的”最多能存储多少个键值对，只不过一般到达capacity的时候就会触发扩容。它的类型是Int8，因此只占一个字节 - 0x21：_reservedScale，暂时用不到，类型也是
Int8，占一个字节 - 0x22: _extra，源码注释明确说了没用，类型是
Int16，占两个字节 - 0x24: _age，暂时用不到，类型是
Int32，占四个字节 - 0x28: _seed，做哈希函数时用到种子
- 0x30: _rawKeys，存储 Key 的指针，下文会有介绍
- 0x38: _rawValues，存储 Value 的指针，下文会有介绍
这里最重要几个属性，分别是 count(+0x10)、scale(+0x20)、rawKeys(+0x30) 和 rawValues(+0x38).
上述是 __RawDictionaryStorage 实例的成员变量的布局结构，实际上从 0x40 的偏移位置开始，才是真正存放的数据：
从 0x40 的偏移开始存放的是实例的 bitset，中文可以翻译为位图。它定义在源码的 stdlib/public/core/Bitset.swift 文件中:
internal struct _UnsafeBitset {
internal let words: UnsafeMutablePointer<Word>
internal let wordCount: Int
internal init(words: UnsafeMutablePointer<Word>, wordCount: Int) {
self.words = words
self.wordCount = wordCount
}
}有 C 语言基础的同学应该可以看出，它存储了一个 Word 的指针和数量，其实就是一个 Word 结构的数组。
至于 Word 的结构就更加简单了：
internal struct Word {
@usableFromInline
internal var value: UInt
@inlinable
internal init(_ value: UInt) {
self.value = value
}
}它本质上就是一个 UInt，特殊之处在于这个 UInt 一共 64 位，每一位都可以用来表示一个对应位置是否被占用。这样的一位被称为一个 Bucket（桶）。
上面已经介绍过，Bucket 的数量一定是 2 的整数次方，这个整数就用 scale 表示。
举个例子，当 scale = 7 时，共有 2 ^ 7 = 128 个 Bucket，需要两个 Word 存储。此时实例的 +0x40 和 +0x48 的位置就是由两个 Word 组成的一个 bitset
紧随位图之后的内存区域是真正存储 Keys 的内存地址。它有点类似于 Key 的数组，不过各个 Key 并不是连续存储，而是根据它所在的 Buck 决定存储在哪个位置。这块内存地址的总大小是 2^scale * sizeof(Key)，没有存放 Key 的位置可以理解为空。
这块内存的起始位置，可以通过 scale 计算出 Bucket 的数量，从而计算出 Word 的数量和 Bitset 的大小得出。也可以直接看 +0x30 偏移上的 _rawKeys 指针。
在 Keys 的内存地址之后就是 Values 的内存，和 Keys 的存储方式是完全一样的。它的大小是 2^scale * sizeof(Value)，起始位置可以动态计算，也可以直接读取 +0x38 偏移上的 _rawValues 指针。
至此我们已经清楚的掌握了字典的内存布局，接下来会通过阅读一段源码来加深理解。
首先构造一段测试代码，并且在 Release 模式下进行编译：
@inline(never)
func find(dic: [String: Int], key: String) -> Int? {
return dic[key]
}对应的汇编实现如图所示：
这里的参数 dic 通过 $rdi 寄存器传入函数，首先检查 +0x10 的偏移是不是 0。如果是 0 就会走右侧绿色分支，返回 nil。这段很好理解，前面已经分析过 +0x10 的位置存储了 count，如果 count = 0 表示空字典是不需要再做任何处理的。
如果字典不为空，会调用 generic specialization <Swift.String> of Swift.__RawDictionaryStorage.find 函数。这是 find 函数的范型特化版本，内部的实现稍后分析，它会返回一个 bucket 和 Bool 标记位，用来表示是否找到。如果找不到也是返回 nil。
如果能找到，那么 bucket 的值会存储在 $rax 寄存器中，通过下面的方式去读取：
; r13 + 0x38 是 _rawValues 的指针
; 那么 [r13 + 0x38] 就是得到了 _rawValues 实际的内存地址
mov rcx, qword [r13+0x38]
; 类似于数组的下标访问，rcx 是起点，rax 是 bucket，0x8 是 Int 的大小
; 把读取到的的值存储到 r15 寄存器
mov r15, qword [rcx+rax*8]这样的取值逻辑是符合此前的内存布局分析的。
这里我们详细分析一下 __RawDictionaryStorage 的 find 函数。
它对应的源码：
@inline(never)
internal final func find<Key: Hashable>(_ key: Key) -> (bucket: _HashTable.Bucket, found: Bool) {
return find(key, hashValue: key._rawHashValue(seed: _seed))
}这段函数比较简单，它会计算 key 的哈希值，然后传入内部的 find 函数
可以看到 Hasher 的初始化参数 seed 来自于字典本身 +0x28 偏移的位置，这也符合之前的内存布局分析
这个函数的源码如下：
internal final func find<Key: Hashable>(_ key: Key, hashValue: Int) -> (bucket: _HashTable.Bucket, found: Bool) {
let hashTable = _hashTable
var bucket = hashTable.idealBucket(forHashValue: hashValue)
while hashTable._isOccupied(bucket) {
if uncheckedKey(at: bucket) == key {
return (bucket, true)
}
bucket = hashTable.bucket(wrappedAfter: bucket)
}
return (bucket, false)
}对应的汇编实现比较复杂，我们分段来看。分析逻辑通过注释的形式给出：
; 首先明确参数：
; 第一个入参是 String 类型，使用 rdi、rsi 两个寄存器传参
; 第二个参数是 hashValue，类型是 Int，使用 rdx 寄存器传参
mov rbx, rdx
; cl 是 _scale，Int8 类型，所以用低 8 位就可以表示
mov cl, byte [r13+0x20]
; r14 = 2^scale - 1
; 这个 r14 是在计算 bucketMast
mov r14, 0xffffffffffffffff
shl r14, cl
not r14
; rbx: hashValue & bucketMast
; 这里是在计算 idealBucket
and rbx, r14这段汇编对应了 hashTable.idealBucket 函数，作用是计算出这个哈希值预期要存放的 Bucket：
internal struct _HashTable {
internal var words: UnsafeMutablePointer<Word>
internal let bucketMask: Int
internal init(words: UnsafeMutablePointer<Word>, bucketCount: Int) {
self.words = words
self.bucketMask = bucketCount &- 1
}
internal func idealBucket(forHashValue hashValue: Int) -> Bucket {
return Bucket(offset: hashValue & bucketMask)
}
}为什么 hashValue & (2^scale - 1) 就是预期的 Bucket 呢？其实既是一个小算法，我们知道 2^scale - 1 其实就是 scale 个 1 组成的二进制，与这个数字做按位与运算，就是只保留这个 hashValue 的低 scale 位。
再看接下来的一段汇编：
; rax 是 idealBucket / 64，也就是 word
shr rax, 0x6
; r13 + 0x40 是 bitset 的起始地址，再加上 rax*8 是第 rax 个 word 的地址
; 对应源码中的 words[bucket.word]
mov rax, qword [r13+rax*8+0x40]
; 获取对应 word 的第 bt 位，对应 _isOccupied 函数
; 注意这里的 rbx 可能大于 64，但是 bt 指令的参数会自动对 rbx 做模 64 的运算
; 因此这里 rbx 实际上对应代码里的 bucket.bit
; bt 指令和后面的 jae 跳转判断，对应 uncheckedContains 函数
bt rax, rbx
; bit = 0 -> CF = 0 -> 走绿色分支，直接返回，说明此时 Bucket 没有被占用
jae loc_100003d78这一段对应着 _isOccupied 函数：
internal func _isOccupied(_ bucket: Bucket) -> Bool {
return words[bucket.word].uncheckedContains(bucket.bit)
}
internal struct Bucket {
internal var offset: Int
internal var word: Int {
return _UnsafeBitset.word(for: offset)
}
internal var bit: Int {
return _UnsafeBitset.bit(for: offset)
}
}
extension _UnsafeBitset {
internal static func word(for element: Int) -> Int {
// Note: We perform on UInts to get faster unsigned math (shifts).
let element = UInt(bitPattern: element)
let capacity = UInt(bitPattern: Word.capacity)
return Int(bitPattern: element / capacity)
}
internal static func bit(for element: Int) -> Int {
// Note: We perform on UInts to get faster unsigned math (masking).
let element = UInt(bitPattern: element)
let capacity = UInt(bitPattern: Word.capacity)
return Int(bitPattern: element % capacity)
}
}看起来比较长，其实核心思想就是：对于一个 Bucket 来说它的 word 和 bit 分别是自身的值除以 capacity 的值和余数（也就是模）。检查一个 Bucket 是否占用，也就是检查第 word 个 bit 上的值是不是 1。
如果被占用了，就要把这一位的 Key 取出来，看看是不是和参数相同，因为这一位也可能是在做哈希时，因为产生了碰撞而被迫放到了这里。
; r15 是 _rawKeys
mov r15, qword [r13+0x30]
; rbx 是 idealBucket
mov rax, rbx
; rax = idealBucket * 16
; 这是因为一个 String 占 16 字节
shl rax, 0x4
; 此时 r15 + rax 是 Keys 数组在下标为 bucket 的位置的值了
; 对应 uncheckedKey
mov rdi, qword [r15+rax]
mov rsi, qword [r15+rax+8]对应的 uncheckedKey 函数非常简单，就是取下标：
internal final func uncheckedKey<Key: Hashable>(at bucket: _HashTable.Bucket) -> Key {
return keys[bucket.offset]
}接下来跳过一段字符串判等的逻辑，当不相等时，来到最后一个函数，获取下一个 Bucket：
; rbx 是 bucket，先 +1
; 然后再按位与上 bucketMask 得到新的 bucket
add rbx, 0x1
and rbx, r14对应的 Swift 源码：
internal func bucket(wrappedAfter bucket: Bucket) -> Bucket {
// The bucket is less than bucketCount, which is power of two less than
// Int.max. Therefore adding 1 does not overflow.
return Bucket(offset: (bucket.offset &+ 1) & bucketMask)
}以上就是 _find 函数内部所有的关键逻辑分析
最后，除了直接对照源码和汇编实现以外，我们还可以直接调试 Swift 源码，从另一个角度来理解 Swift 源码的工作原理。
这方面的资料比较多，这里就简单描述下具体步骤和我遇到的一些细节问题：
- 首先创建一个
swift-project目录，这个目录用于编译 Swift 源码 - 在
swift-project目录下下载 Swift 源码，执行命令：git clone https://github.com/apple/swift.git - 进入
swift-project/swift目录，执行命令：./utils/update-checkout --clone下载 Swift 的依赖。 - 下载万完成后可以在
swift-project目录下看到出现了很多和swift同级的目录 - 进入
swift-project/swift目录，执行开始编译源码：/swift/utils/build-script -r --debug-swift-stdlib --lldb - 编译完成后用
VSCode打开swift-project目录，并且安装 CodeLLDB 插件 - 在调试页面，创建自定义的
launch.json文件：
{
"version": "0.2.0",
"configurations": [
{
"type": "lldb",
"request": "launch",
"name": "Debug",
"program": "${workspaceFolder}/build/Ninja-RelWithDebInfoAssert+stdlib-DebugAssert/swift-macosx-x86_64/bin/swift",
"args": ["path/to/your/swift-file"],
"cwd": "${workspaceFolder}"
}
]
}这里需要注意的是，很多网上教程贴出的配置 args 都是空的，这样会导致 Swift 进入命令行解释模式(REPL)，但是这个能力已经被禁止了。所以需要把自己需要被执行的 Swift 文件作为参数填进来。
然后在自己感兴趣的 Swift 源码部分打上断点，启动调试就可以了。效果如图所示：
其实笔者还是更想用 Xcode 进行调试。无奈网上的资料表示 VSCode 的支持程度更好，更推荐。使用 Xcode 调试的文章也比较老，尝试了一下没有成功。只能再研究下，后续成功了再做分享了。
本文可以主要分为三个部分：
- 介绍字典的内存布局，主要关注
count、scale、rawKeys/Values这些固定布局结构和bitset、Keys/Values这些不固定布局的结构。 - 介绍下标方法的实现，包括源码层实现与汇编层实现，深入理解字典相关的概念和函数的原理
- 简单介绍动态调试 Swift 源码的方案
希望上述方案能够帮助读者更好的理解字典和其它 Swift 的源码。