最近有些群友反馈自己经常遇到一些与 NSDictionary 底层相关的面试题。
本系列文章会通过分析系统库汇编的方式对此类问题进行答疑解惑。?
一、·NSDictionary· 结构简介
1、类簇
在 iOS 的系统库中，很多集合类都是类簇。
尽管我们通常只会用到 NSDictionary 和 NSMutableDictionary 两个类，但是系统库会存在很多不同的子类。
2、语法糖
从 Xcode 4.4 开始，编译器新增了一些被称为 字面量 的语法糖。
以下面的代码为例：
代码语言：javascript复制NSDictionary *masses = @{ @"H" : @1.0078, @"He" : @4.0026, @"O" : @15.9990, @"C" : @12.0096 };
clang 编译器的 SemaExprObjC.cpp[1] 会将上述代码转为下面等价实现：
代码语言：javascript复制id keys[] = { @"H", @"He", @"O", @"C" };
id values[] = { [NSNumber numberWithDouble:1.0078], [NSNumber numberWithDouble:4.0026],
[NSNumber numberWithDouble:15.9990], [NSNumber numberWithDouble:12.0096] };
NSDictionary *masses = [NSDictionary dictionaryWithObjects:objects forKeys:keys count:4];
通过查看编译产出的汇编代码，我们可以证明上面的结论：
image
二、__NSPlaceholderDictionary
__NSPlaceholderDictionary 是占位的类型，通常只出现在崩溃日志中。
本节会以下面的代码为例对 __NSPlaceholderDictionary 出现的场景进行分析
id obj = nil;
NSDictionary *dic = @{ @"k" : @"v", obj : obj };
在字典的初始化过程中， [NSDictionary dictionaryWithObjects:forKeys:count:]会先调用objc_alloc 进行初始化
image
objc_alloc 会转发到 [NSDictionary alloc] 处理
image
随后会经过层层转发，最后调用 [NSDictionary allocWithZone:] 进行下一步处理
## 第一次转发
libobjc.A.dylib`objc_alloc:
0x7fff20190b4d < 0>: test rdi, rdi
0x7fff20190b50 < 3>: je 0x7fff20190b6c ; < 31>
0x7fff20190b52 < 5>: mov rax, qword ptr [rdi]
0x7fff20190b55 < 8>: test byte ptr [rax 0x1d], 0x40
0x7fff20190b59 < 12>: jne 0x7fff20188a75 ; _objc_rootAllocWithZone
0x7fff20190b5f < 18>: mov rsi, qword ptr [rip 0x66bc3952] ; "alloc"
-> 0x7fff20190b66 < 25>: jmp qword ptr [rip 0x5fe8d124] ; (void *)0x00007fff20173780: objc_msgSend
0x7fff20190b6c < 31>: xor eax, eax
0x7fff20190b6e < 33>: ret
## 第二次转发
libobjc.A.dylib` [NSObject alloc]:
-> 0x7fff2018ec56 < 0>: jmp 0x7fff2018ec7a ; _objc_rootAlloc
## 第三次转发
libobjc.A.dylib`_objc_rootAlloc:
0x7fff2018ec7a < 0>: mov rax, qword ptr [rdi]
0x7fff2018ec7d < 3>: test byte ptr [rax 0x1d], 0x40
0x7fff2018ec81 < 7>: je 0x7fff2018ec88 ; < 14>
0x7fff2018ec83 < 9>: jmp 0x7fff20188a75 ; _objc_rootAllocWithZone
0x7fff2018ec88 < 14>: mov rsi, qword ptr [rip 0x66bc5831] ; "allocWithZone:"
0x7fff2018ec8f < 21>: xor edx, edx
-> 0x7fff2018ec91 < 23>: jmp qword ptr [rip 0x5fe8eff9] ; (void *)0x00007fff20173780: objc_msgSend
[NSDictionary allocWithZone:] 会转发到 __NSDictionaryImmutablePlaceholder 进入不可变数组的通用处理逻辑
image
__NSDictionaryImmutablePlaceholder 内部会将常量 ___immutablePlaceholderDictionary 加载到 $rax 寄存器并返回 (x86-64 架构)
CoreFoundation`__NSDictionaryImmutablePlaceholder:
-> 0x7fff2048cbba < 0>: lea rax, [rip 0x5fd19e7f] ; ___immutablePlaceholderDictionary
0x7fff2048cbc1 < 7>: ret
返回 [NSDictionary dictionaryWithObjects:forKeys:count:] 后，会拼装一个新的方法调用 -[__NSPlaceholderDictionary initWithObjects:forKeys:count:]
相关参数信息：
代码语言：javascript复制类型是 __NSPlaceholderDictionary
(lldb) x/a $rdi
0x7fff801a6a40: 0x00007fff86d73ec0 (void *)0x00007fff86d73ee8: __NSPlaceholderDictionary
(lldb) x/a $rax
0x7fff801a6a40: 0x00007fff86d73ec0 (void *)0x00007fff86d73ee8: __NSPlaceholderDictionary
方法名是 "initWithObjects:forKeys:count:"
(lldb) x/s $rsi
0x7fff6143917e: "initWithObjects:forKeys:count:"
第一个参数:objects
(lldb) x/2a $rbx
0x7ffedfe95488: 0x000000010fd6e5f8 @"'v'"
0x7ffedfe95490: 0x0000000000000000
第二个参数:keys
(lldb) x/2a $rcx
0x7ffedfe95478: 0x000000010fd6e5b8 @"'k'"
0x7ffedfe95480: 0x0000000000000000
第三个参数：count
(lldb) p/x $r8
(unsigned long) $13 = 0x0000000000000002
(lldb)
-[__NSPlaceholderDictionary initWithObjects:forKeys:count:] 内部会先做一些基础校验
本例中，会通过下面的循环依次判断每个值是否合法
# 依次判断每个 keys[i] 是否等于 nil
0x7fff2048cbf8 < 44>: cmp qword ptr [rsi 8*rcx], 0x0
# 等于 nil 时，转到 0x7fff2048cca7 进行异常处理
0x7fff2048cbfd < 49>: je 0x7fff2048cca7 ; < 219>
# 不等于 nil 时，rcx = rcx 1
0x7fff2048cc03 < 55>: inc rcx
# 判断 rcx 是否等于 rax；rax 是传入的 count
0x7fff2048cc06 < 58>: cmp rax, rcx
# 判断是否将所有的 key 循环结束，如果没有，则转到 0x7fff2048cbf8 进行下一步处理
0x7fff2048cc09 < 61>: jne 0x7fff2048cbf8 ; < 44>
# rdi 是函数的第一个参数，这里会将校验失败的 rcx 传给下个函数
0x7fff2048cca7 < 219>: mov rdi, rcx
0x7fff2048ccaa < 222>: call 0x7fff204a9ec4 ; -[__NSPlaceholderDictionary initWithObjects:forKeys:count:].cold.5
-[__NSPlaceholderDictionary initWithObjects:forKeys:count:].cold.5 内部逻辑比较简单，会直接通过 _CFThrowFormattedException 抛出异常
CoreFoundation`-[__NSPlaceholderDictionary initWithObjects:forKeys:count:].cold.5:
-> 0x7fff204a9ec4 < 0>: push rbp
0x7fff204a9ec5 < 1>: mov rbp, rsp
0x7fff204a9ec8 < 4>: mov rcx, rdi
0x7fff204a9ecb < 7>: lea rax, [rip 0x5fcf9176] ; NSInvalidArgumentException
0x7fff204a9ed2 < 14>: mov rdi, qword ptr [rax]
0x7fff204a9ed5 < 17>: lea rsi, [rip 0x5fcfd33c] ; @"*** %s: attempt to insert nil object from objects[%lu]"
0x7fff204a9edc < 24>: lea rdx, [rip 0x1dc1bc] ; "-[__NSPlaceholderDictionary initWithObjects:forKeys:count:]"
0x7fff204a9ee3 < 31>: xor eax, eax
0x7fff204a9ee5 < 33>: call 0x7fff2049e6bd ; _CFThrowFormattedException
崩溃日志关键信息：
代码语言：javascript复制注意，我们可以通过崩溃日志的
objects[1]判断是第二个键值对出现了nil
*** Terminating app due to uncaught exception 'NSInvalidArgumentException', reason: '*** -[__NSPlaceholderDictionary initWithObjects:forKeys:count:]: attempt to insert nil object from objects[1]'
*** First throw call stack:
(
0 CoreFoundation 0x00007fff20421af6 __exceptionPreprocess 242
1 libobjc.A.dylib 0x00007fff20177e78 objc_exception_throw 48
2 CoreFoundation 0x00007fff2049e77f _CFThrowFormattedException 194
3 CoreFoundation 0x00007fff204a9eea -[__NSPlaceholderDictionary initWithCapacity:].cold.1 0
4 CoreFoundation 0x00007fff2048ccaf -[__NSPlaceholderDictionary initWithObjects:forKeys:count:] 227
5 CoreFoundation 0x00007fff20420773 [NSDictionary dictionaryWithObjects:forKeys:count:] 49
三、__NSDictionaryI
__NSDictionaryI 是存有多个键值对的不可变字典，其内部结构如下：
classDiagram
class __NSDictionaryI {
## 当前使用的数量
unsigned _used : 57;
## 是否复制 key
unsigned _copyKeys : 1;
## size 索引
unsigned _szidx : 6;
## key 和 value
id _list[0];
}
本节会通过下面的代码对 __NSDictionaryI 接着上一节内容进行分析
NSDictionary *dic = @{ @"k" : @"v", @"k" : @"v2" };
-[__NSPlaceholderDictionary initWithObjects:forKeys:count:] 各种校验结束后，会转发到 __NSDictionaryI_new 进行下一步处理（rcx 代表字典的 count ；r8d 等于常量 1，代表会复制 key）
image
__NSDictionaryI_new 内部会依次进行以下处理
敲重点： 1、
__NSDictionaryCapacities会搭配后面的__NSDictionarySizes常量来控制字典的空间大小和动态扩容 2、数组的长度是 40
image
- 通过指令
mov qword ptr [rbp - 0x78], r8将 常量 1 暂存 - 读取一个常量数组：
__NSDictionaryCapacities
字典读取后，会开始进入下面的循环
代码语言：javascript复制 0x7fff203432fd < 51>: lea rax, [rip 0x1dd87c] ; __NSDictionaryCapacities
0x7fff20343304 < 58>: xor ebx, ebx
# 循环
0x7fff20343306 < 60>: cmp qword ptr [rbx rax], r13
0x7fff2034330a < 64>: jae 0x7fff20343322 ; < 88>
0x7fff2034330c < 66>: add rbx, 0x8
0x7fff20343310 < 70>: add r14, 0x4
0x7fff20343314 < 74>: cmp r14, 0x100
## 循环 64次后强制终止（64=0x100/0x4）
0x7fff2034331b < 81>: jne 0x7fff20343306 ; < 60>
汇编代码会依次将 __NSDictionaryCapacities 常量数组的值取出来并和 r13 存储的内容进行比较
代码语言：javascript复制JAE 的含义是：无符号大于等于则跳转
JA ;无符号大于则跳转
JNA ;无符号不大于则跳转
JAE ;无符号大于等于则跳转 同JNB
JNAE ;无符号不大于等于则跳转 同JB
本例中，count 是 2，所以，截止时，rbx = 0x8，r14 = 0x4
对应的 arm64 架构的版本：
代码语言：javascript复制0x00000001803b0e54 A80D00B0 adrp x8, #0x180565000 ; 0x1805651e0@PAGE
0x00000001803b0e58 08810791 add x8, x8, #0x1e0 ; 0x1805651e0@PAGEOFF, ___NSDictionaryCapacities
loc_1803b0e5c:
0x00000001803b0e5c 09797AF8 ldr x9, [x8, x26, lsl #3] ; CODE XREF=___NSDictionaryI_new 100
0x00000001803b0e60 3F0116EB cmp x9, x22
## 大于等于时触发终止
0x00000001803b0e64 A2000054 b.hs loc_1803b0e78
0x00000001803b0e68 5A070091 add x26, x26, #0x1
0x00000001803b0e6c 5F0301F1 cmp x26, #0x40
## 循环 64 次后强制终止（64=0x40/0x1）
0x00000001803b0e70 61FFFF54 b.ne loc_1803b0e5c随后会读取常量数组 __NSDictionarySizes，并将对应位置的值取出来
image
3 代表该字典可以存储的键值对数量
随后，会通过位移计算 __NSDictionaryI 额外的体积占用，并调用 __CFAllocateObject 创建对象
代码语言：javascript复制本例中，字典最多持有 3 个键值对，体积占用是 6 个指针，对应的体积是
0x30 = 48 = 3 x 2 x 8 = 3<<4
## 获取 __NSDictionaryI 类型
0x7fff20343322 < 88>: lea rdi, [rip 0x66a2d857] ; (void *)0x00007fff86d70ba8: __NSDictionaryI
## 获取 [__NSDictionaryI self]，返回值放在 rax 寄存器
0x7fff20343329 < 95>: call 0x7fff204ab4fa ; symbol stub for: objc_opt_self
## rcx 指向 __NSDictionarySizes 常量数组
0x7fff2034332e < 100>: lea rcx, [rip 0x1dd6fb] ; __NSDictionarySizes
## 根据偏移量 0x8 取出 3
0x7fff20343335 < 107>: mov rbx, qword ptr [rbx rcx]
## 放到 rsi 寄存器
0x7fff20343339 < 111>: mov rsi, rbx
## 左移 4 位，相当于 3*16=6*8
0x7fff2034333c < 114>: shl rsi, 0x4
## rdi 持有 __NSDictionaryI
0x7fff20343340 < 118>: mov rdi, rax
## 通过 __CFAllocateObject 创建对象的实例
0x7fff20343343 < 121>: call 0x7fff2043153b ; __CFAllocateObject
objc_opt_self 等价于 [obj self]
代码语言：javascript复制只有较新的
objc版本才有该方法
// Calls [obj self]
id
objc_opt_self(id obj)
{
#if __OBJC2__
if (fastpath(!obj || obj->isTaggedPointer() || !obj->ISA()->hasCustomCore())) {
return obj;
}
#endif
return ((id(*)(id, SEL))objc_msgSend)(obj, @selector(self));
}
__CFAllocateObject 内部会调用 class_createInstance 创建该类的实例，并额外申请 0x30 的内存
__CFAllocateObject 结束后会开始更新实例的值
0x7fff20343343 < 121>: call 0x7fff2043153b ; __CFAllocateObject
刚创建的实例：
0x7f8371e06960: 0x00007fff86d70b80 (void *)0x00007fff86d70ba8: __NSDictionaryI
0x7f8371e06968: 0x0000000000000000
0x7f8371e06970: 0x0000000000000000
0x7f8371e06978: 0x0000000000000000
0x7f8371e06980: 0x0000000000000000
0x7f8371e06988: 0x0000000000000000
0x7f8371e06990: 0x0000000000000000
0x7f8371e06998: 0x0000000000000000
## 下面的汇编代码相当于 dic->_szidx=(r14>>2)；可读性比较差是因为编译器无法优化
### 读取 __NSDictionaryI._szidx 的值
0x7fff20343348 < 126>: mov rdx, qword ptr [rip 0x66a2c7d9] ; __NSDictionaryI._szidx
### 因为 _szidx 只占用6bit，所以需要先读取原来的值
0x7fff2034334f < 133>: mov cl, byte ptr [rax rdx]
### 随后，只保留最低的2bit，_szidx 对应的旧值被清零
0x7fff20343352 < 136>: and cl, 0x3
### 旧的低位2bit加上新的6bit
0x7fff20343355 < 139>: or r14b, cl
### 存储到 _szidx和旁边2位的 bit
0x7fff20343358 < 142>: mov byte ptr [rax rdx], r14b
经过上面的流程，0x7f8371e06968 的高6位内容会被更新
0x7f8371e06960: 0x00007fff86d70b80 (void *)0x00007fff86d70ba8: __NSDictionaryI
0x7f8371e06968: 0x0400000000000000
0x7f8371e06970: 0x0000000000000000
0x7f8371e06978: 0x0000000000000000
0x7f8371e06980: 0x0000000000000000
0x7f8371e06988: 0x0000000000000000
0x7f8371e06990: 0x0000000000000000
0x7f8371e06998: 0x0000000000000000
## 与 _szidx 类似，下面的汇编等价于 dic->_used = (0x1ffffffffffffff & $r13)
0x7fff2034335c < 146>: mov rsi, qword ptr [rip 0x66a2c7bd] ; __NSDictionaryI._used
0x7fff20343363 < 153>: movabs rcx, 0x1ffffffffffffff
0x7fff2034336d < 163>: and rcx, r13
0x7fff20343370 < 166>: movabs rdx, -0x200000000000000
0x7fff2034337a < 176>: and rdx, qword ptr [rax rsi]
0x7fff2034337e < 180>: or rdx, rcx
0x7fff20343381 < 183>: mov qword ptr [rax rsi], rdx
经过上面的流程，0x7f8371e06968 的低57位内容会被更新
(lldb) x/8a $rax
0x7f8371e06960: 0x00007fff86d70b80 (void *)0x00007fff86d70ba8: __NSDictionaryI
0x7f8371e06968: 0x0400000000000002
0x7f8371e06970: 0x0000000000000000
0x7f8371e06978: 0x0000000000000000
0x7f8371e06980: 0x0000000000000000
0x7f8371e06988: 0x0000000000000000
0x7f8371e06990: 0x0000000000000000
0x7f8371e06998: 0x0000000000000000
## [rbp - 0x78] 暂存的是 1 ，所以下面的汇编等价于 dic->_copyKeys = (x&2)
cl=旧8bit
8 位 AL、BL、CL、DL、DIL、SIL、BPL、SPL、R8L、R9L、R10L、R11L、R12L、R13L、R14L、R15L
16 位 AX、BX、CX、DX、DI、SI、BP、SP、R8W、R9W、R10W、R11W、R12W、R13W、R14W、R15W
32 位 EAX、EBX、ECX、EDX、EDI、ESI、EBP、ESP、R8D、R9D、R10D、R11D、R12D、R13D、R14D、R15D
64 位 RAX、RBX、RCX、RDX、RDI、RSI、RBP、RSP、R8、R9、R10、R11、R12、R13、R14、R15
0x7fff20343385 < 187>: mov rsi, qword ptr [rip 0x66a2c7ac] ; __NSDictionaryI._copyKeys
0x7fff2034338c < 194>: mov cl, byte ptr [rax rsi]
0x7fff2034338f < 197>: mov rdi, qword ptr [rbp - 0x78]
0x7fff20343393 < 201>: mov edx, edi
## dl=edx=edi=rdi=*[rbp - 0x78]=1
## 经过 and 后，dl=0
0x7fff20343395 < 203>: and dl, 0x2
## cl=旧8bit，并清掉旧值
0x7fff20343398 < 206>: and cl, -0x3
## 设置新的值
0x7fff2034339b < 209>: or cl, dl
## 存储
0x7fff2034339d < 211>: mov byte ptr [rax rsi], cl
下一步的逻辑比较简单，就是依次通过 ____NSDictionaryI_new_block_invoke 将输入存储到 _list区域
image
____NSDictionaryI_new_block_invoke 内部的汇编比较多，我们只对内部的逻辑进行简单的介绍
image
- 通过调用
hash和isEqual:判断是否有重复的值 - 通过
objc_retain对value进行复制操作
如下图所示，经过上面的一些列流程后，dic 会变成一个只持有 k 和 v 键值对的结构体
image
总结
本文主要分享了 NSDictionary 的两个子类：__NSPlaceholderDictionary 和 __NSDictionaryI 的构造过程进行了简单的分析。
下一篇暂定会介绍 cow 机制。
参考资料
[1]
SemaExprObjC.cpp: https://github.com/apple/llvm-project/blob/bf7404b17f35826f76aede830a7de279afaeb321/clang/lib/Sema/SemaExprObjC.cpp#L965
