跟着 NSDictionary 的底层设计学习优化技巧（1）

最近有些群友反馈自己经常遇到一些与 NSDictionary 底层相关的面试题。

本系列文章会通过分析系统库汇编的方式对此类问题进行答疑解惑 😁

一、·NSDictionary· 结构简介

1、类簇

在 iOS 的系统库中，很多集合类都是类簇。

尽管我们通常只会用到 NSDictionary 和 NSMutableDictionary 两个类，但是系统库会存在很多不同的子类。

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63

classDiagram

class __NSFrozenDictionaryM {
	SCD_Struct_NS35* storage;
	__cow_state_t* cow;
}

class  __NSDictionaryM  {
	SCD_Struct_NS35* storage;
	__cow_state_t* cow;
}

class __NSCFDictionary {
	unsigned char _cfinfo[4];
	unsigned _rc;
	unsigned _bits[4];
	void* _callbacks;
	id* _values;
	id* _keys;
}

class NSConstantDictionary {
	unsigned long long _options;
	unsigned long long _count;
	const id* _keys;
	const id* _objects;
}

class NSSharedKeyDictionary {
	NSSharedKeySet* _keyMap;
	unsigned long long _count;
	id* _values;
	/*function pointer*/void* _ifkIMP;
	NSMutableDictionary* _sideDic;
	unsigned long long _mutations;
	BOOL _doKVO;
}

class __NSDictionaryI {
	unsigned _used : 57;
	unsigned _copyKeys : 1;
	unsigned _szidx : 6;
	id _list[0];
}

class __NSSingleEntryDictionaryI {
  id _obj;
	id _key;
}

__NSCFDictionary --> NSMutableDictionary
__NSDictionary0 --> NSDictionary
__NSDictionaryI --> NSDictionary
__NSDictionaryM --> NSMutableDictionary
__NSFrozenDictionaryM --> NSDictionary
__NSPlaceholderDictionary --> NSMutableDictionary
__NSSingleEntryDictionaryI --> NSDictionary
NSCFDictionary --> __NSCFDictionary
NSConstantDictionary --> NSDictionary
NSDictionary --> NSObject
NSMutableDictionary --> NSDictionary
NSSharedKeyDictionary --> NSMutableDictionary

2、语法糖

从 Xcode 4.4 开始，编译器新增了一些被称为 字面量 的语法糖。

以下面的代码为例：

1

NSDictionary *masses = @{ @"H" : @1.0078,  @"He" : @4.0026, @"O" : @15.9990, @"C" : @12.0096 };

clang 编译器的 SemaExprObjC.cpp 会将上述代码转为下面等价实现：

1
2
3
4

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];

通过查看编译产出的汇编代码，我们可以证明上面的结论：

二、__NSPlaceholderDictionary

__NSPlaceholderDictionary 是占位的类型，通常只出现在崩溃日志中。

本节会以下面的代码为例对 __NSPlaceholderDictionary 出现的场景进行分析

1
2

id obj = nil;
NSDictionary *dic = @{ @"k" : @"v", obj : obj };

1. 在字典的初始化过程中，+[NSDictionary dictionaryWithObjects:forKeys:count:]会先调用objc_alloc 进行初始化

   

2. objc_alloc 会转发到 +[NSDictionary alloc] 处理

   

3. 随后会经过层层转发，最后调用 +[NSDictionary allocWithZone:] 进行下一步处理

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26

   ## 第一次转发 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

4. [NSDictionary allocWithZone:] 会转发到 __NSDictionaryImmutablePlaceholder 进入不可变数组的通用处理逻辑

   

5. __NSDictionaryImmutablePlaceholder 内部会将常量 ___immutablePlaceholderDictionary 加载到 $rax 寄存器并返回 (x86-64 架构)

   1 2 3 4

   CoreFoundation`__NSDictionaryImmutablePlaceholder: -> 0x7fff2048cbba <+0>: lea rax, [rip + 0x5fd19e7f] ; ___immutablePlaceholderDictionary 0x7fff2048cbc1 <+7>: ret

   

6. 返回 +[NSDictionary dictionaryWithObjects:forKeys:count:] 后，会拼装一个新的方法调用 -[__NSPlaceholderDictionary initWithObjects:forKeys:count:]

   

   相关参数信息：

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24

   类型是 __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)

7. -[__NSPlaceholderDictionary initWithObjects:forKeys:count:] 内部会先做一些基础校验

   本例中，会通过下面的循环依次判断每个值是否合法

   

   1 2 3 4 5 6 7 8 9 10 11 12 13 14

   # 依次判断每个 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>

   1 2 3

   # rdi 是函数的第一个参数，这里会将校验失败的 rcx 传给下个函数 0x7fff2048cca7 <+219>: mov rdi, rcx 0x7fff2048ccaa <+222>: call 0x7fff204a9ec4 ; -[__NSPlaceholderDictionary initWithObjects:forKeys:count:].cold.5

8. -[__NSPlaceholderDictionary initWithObjects:forKeys:count:].cold.5 内部逻辑比较简单，会直接通过 _CFThrowFormattedException 抛出异常

   1 2 3 4 5 6 7 8 9 10

   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

   崩溃日志关键信息：

   注意，我们可以通过崩溃日志的 objects[1] 判断是第二个键值对出现了 nil

   1 2 3 4 5 6 7 8 9

   *** 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 是存有多个键值对的不可变字典，其内部结构如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11

classDiagram
class __NSDictionaryI {
  ## 当前使用的数量
	unsigned _used : 57;
	## 是否复制 key
	unsigned _copyKeys : 1;
	## size 索引
	unsigned _szidx : 6;
	## key 和 value
	id _list[0];
}

本节会通过下面的代码对 __NSDictionaryI 接着上一节内容进行分析

1

NSDictionary *dic = @{ @"k" : @"v", @"k" : @"v2" };

1. -[__NSPlaceholderDictionary initWithObjects:forKeys:count:] 各种校验结束后，会根据情况转发到合适的位置进行处理

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27

   ## rax 代表 count，如果等于 1，则进入 __NSSingleEntryDictionaryI_new 创建流程 0x7fff2048cc63 <+151>: cmp rax, 0x1 0x7fff2048cc67 <+155>: je 0x7fff2048cc7f ; <+179> ## 如果 rax 不等于0，则跳转到 __NSDictionaryI_new 创建流程 0x7fff2048cc69 <+157>: test rax, rax 0x7fff2048cc6c <+160>: jne 0x7fff2048cc90 ; <+196> ## 等于0，则创建 __NSDictionary0__ 0x7fff2048cc6e <+162>: lea rax, [rip + 0x5fd12efb] ; __NSDictionary0__ 0x7fff2048cc75 <+169>: mov rdi, qword ptr [rax] 0x7fff2048cc78 <+172>: pop rbp 0x7fff2048cc79 <+173>: jmp qword ptr [rip + 0x5fba0611] ; (void *)0x00007fff2018fa80: objc_retain 0x7fff2048cc7f <+179>: mov rdi, qword ptr [rsi] 0x7fff2048cc82 <+182>: mov rsi, qword ptr [rdx] 0x7fff2048cc85 <+185>: mov edx, 0x1 0x7fff2048cc8a <+190>: pop rbp 0x7fff2048cc8b <+191>: jmp 0x7fff20354cee ; __NSSingleEntryDictionaryI_new 0x7fff2048cc90 <+196>: mov r8d, 0x1 0x7fff2048cc96 <+202>: mov rdi, rsi 0x7fff2048cc99 <+205>: mov rsi, rdx 0x7fff2048cc9c <+208>: xor edx, edx 0x7fff2048cc9e <+210>: mov rcx, rax 0x7fff2048cca1 <+213>: pop rbp 0x7fff2048cca2 <+214>: jmp 0x7fff203432ca ; __NSDictionaryI_new

   本例的 key 数量大于1，所以会转发到 __NSDictionaryI_new 进行下一步处理（rcx 代表字典的 count ； r8d 等于常量 1，代表会复制 key）

   

2. __NSDictionaryI_new 内部会依次进行以下处理

   1. 通过指令 mov qword ptr [rbp - 0x78], r8 将 常量 1 暂存，
   2. 通过指令 mov r13, rcx 将 字典的 count 存到r13 寄存器
   3. 读取一个常量数组： __NSDictionaryCapacities

   敲重点：

   1、__NSDictionaryCapacities 会搭配后面的 __NSDictionarySizes 常量来控制字典的空间大小和动态扩容

   2、数组的长度是 40

   

3. 字典读取后，会开始进入下面的循环

   1 2 3 4 5 6 7 8 9 10 11

   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 存储的内容进行比较

   并且该循环存在两种截止的情况

   1. 正常情况下，截止条件是取出的值大于等于 r13 （r13 代表 count）
   2. 非正常情况下，r14 等于 0x100（代表循环次数是 64=2^6 次）

   JAE 的含义是：无符号大于等于则跳转

   1 2 3 4

   JA ;无符号大于则跳转 JNA ;无符号不大于则跳转 JAE ;无符号大于等于则跳转 同JNB JNAE ;无符号不大于等于则跳转 同JB

   本例中，count 是 2，所以，截止时，rbx = 0x8，r14 = 0x4

   对应的 arm64 架构的版本：

   1 2 3 4 5 6 7 8 9 10 11 12 13

   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

4. 随后会读取常量数组 __NSDictionarySizes，并将对应位置的值取出来

   

   3 代表该字典可以存储的键值对数量

5. 随后，会通过位移计算 __NSDictionaryI 额外的体积占用，并调用 __CFAllocateObject 创建对象

   本例中，字典最多持有 3 个键值对，体积占用是 6 个指针，对应的体积是 0x30 = 48 = 3 x 2 x 8 = 3<<4

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17

   ## 获取 __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]

   只有较新的 objc 版本才有该方法

   1 2 3 4 5 6 7 8 9 10 11 12

   // 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)); }

6. __CFAllocateObject 内部会调用 class_createInstance 创建该类的实例，并额外申请 0x30 的内存

   

7. __CFAllocateObject 结束后会开始更新实例的值

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81

   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) 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

8. 下一步的逻辑比较简单，就是依次通过 ____NSDictionaryI_new_block_invoke 将输入存储到 _list 区域

   

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16

   传入的参数是 block 和 键值对 (lldb) args rdi = 0x00007ffee731e260 rsi = 0x00000001088e55b8 @"'k'" rdx = 0x00000001088e55f8 @"'v'" rcx = 0x00007fff20343528 CoreFoundation`____NSDictionaryI_new_block_invoke r8 = 0x0000000108c8b054 r9 = 0x0000000000000004 (lldb) po $rdi <__NSStackBlock__: 0x7ffee731e260> signature: "v24@?0@8@16" invoke : 0x7fff20343528 (/Applications/Xcode.app/Contents/Developer/Platforms/iPhoneOS.platform/Library/Developer/CoreSimulator/Profiles/Runtimes/iOS.simruntime/Contents/Resources/RuntimeRoot/System/Library/Frameworks/CoreFoundation.framework/CoreFoundation`____NSDictionaryI_new_block_invoke) copy : 0x7fff2034368f (/Applications/Xcode.app/Contents/Developer/Platforms/iPhoneOS.platform/Library/Developer/CoreSimulator/Profiles/Runtimes/iOS.simruntime/Contents/Resources/RuntimeRoot/System/Library/Frameworks/CoreFoundation.framework/CoreFoundation`__copy_helper_block_e8_32o) dispose : 0x7fff203436a1 (/Applications/Xcode.app/Contents/Developer/Platforms/iPhoneOS.platform/Library/Developer/CoreSimulator/Profiles/Runtimes/iOS.simruntime/Contents/Resources/RuntimeRoot/System/Library/Frameworks/CoreFoundation.framework/CoreFoundation`__destroy_helper_block_e8_32o) (lldb)

9. ____NSDictionaryI_new_block_invoke 内部的汇编比较多，我们只对内部的逻辑进行简单的介绍

   1. 通过调用 hash 和 isEqual: 判断是否有重复的值
   2. 通过 copyWithZone: 将 key 进行复制
   3. 通过 objc_retain 对 value 进行复制操作
   4. 检测到 key 重复后，会将 __NSDictionaryI._used 的值减 1 （会影响字典的生成结果，v2 不会覆盖 v）

   

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141

   CoreFoundation`____NSDictionaryI_new_block_invoke: 0x7fff20343528 <+0>: push rbp 0x7fff20343529 <+1>: mov rbp, rsp 0x7fff2034352c <+4>: push r15 0x7fff2034352e <+6>: push r14 0x7fff20343530 <+8>: push r13 0x7fff20343532 <+10>: push r12 0x7fff20343534 <+12>: push rbx 0x7fff20343535 <+13>: sub rsp, 0x28 0x7fff20343539 <+17>: mov qword ptr [rbp - 0x30], rdx 0x7fff2034353d <+21>: mov r12, rsi 0x7fff20343540 <+24>: mov rax, qword ptr [rdi + 0x28] 0x7fff20343544 <+28>: mov qword ptr [rbp - 0x48], rax 0x7fff20343548 <+32>: mov qword ptr [rbp - 0x38], rdi 0x7fff2034354c <+36>: mov r13, qword ptr [rdi + 0x30] 0x7fff20343550 <+40>: mov rsi, qword ptr [rip + 0x66a2a639] ; "hash" 0x7fff20343557 <+47>: mov rdi, r12 0x7fff2034355a <+50>: call qword ptr [rip + 0x5fce9d18] ; (void *)0x00007fff20173780: objc_msgSend 0x7fff20343560 <+56>: test r13, r13 0x7fff20343563 <+59>: je 0x7fff203435c0 ; <+152> 0x7fff20343565 <+61>: xor edx, edx 0x7fff20343567 <+63>: div r13 0x7fff2034356a <+66>: mov rbx, rdx 0x7fff2034356d <+69>: mov rax, qword ptr [rip + 0x66a2a624] ; "isEqual:" 0x7fff20343574 <+76>: mov qword ptr [rbp - 0x40], rax 0x7fff20343578 <+80>: mov r15, r13 0x7fff2034357b <+83>: lea r14, [rbx + rbx] 0x7fff2034357f <+87>: mov rax, rbx 0x7fff20343582 <+90>: shl rax, 0x4 0x7fff20343586 <+94>: mov rcx, qword ptr [rbp - 0x48] 0x7fff2034358a <+98>: mov rdi, qword ptr [rcx + rax] 0x7fff2034358e <+102>: test rdi, rdi 0x7fff20343591 <+105>: je 0x7fff203435c6 ; <+158> 0x7fff20343593 <+107>: cmp rdi, r12 0x7fff20343596 <+110>: je 0x7fff203435c6 ; <+158> 0x7fff20343598 <+112>: mov rsi, qword ptr [rbp - 0x40] 0x7fff2034359c <+116>: mov rdx, r12 0x7fff2034359f <+119>: call qword ptr [rip + 0x5fce9cd3] ; (void *)0x00007fff20173780: objc_msgSend 0x7fff203435a5 <+125>: test al, al 0x7fff203435a7 <+127>: jne 0x7fff203435c6 ; <+158> 0x7fff203435a9 <+129>: inc rbx 0x7fff203435ac <+132>: cmp rbx, r13 0x7fff203435af <+135>: mov eax, 0x0 0x7fff203435b4 <+140>: cmovae rax, r13 0x7fff203435b8 <+144>: sub rbx, rax 0x7fff203435bb <+147>: dec r15 0x7fff203435be <+150>: jne 0x7fff2034357b ; <+83> 0x7fff203435c0 <+152>: add r13, r13 0x7fff203435c3 <+155>: mov r14, r13 ## rbx 指向 block 0x7fff203435c6 <+158>: mov rbx, qword ptr [rbp - 0x38] ## rax 执行字典的 list 0x7fd38b106670=0x00007fd38b106660+0x10=__NSDictionaryI实例基地址+偏移量 0x7fff203435ca <+162>: mov rax, qword ptr [rbx + 0x28] ## rbx (lldb) x/10a $rbx 0x7ffee8cfa250: 0x00007fff86d3e448 (void *)0x00007fff86d3e420: __NSStackBlock__ 0x7ffee8cfa258: 0x00000000c2000000 0x7ffee8cfa260: 0x00007fff20343528 CoreFoundation`____NSDictionaryI_new_block_invoke 0x7ffee8cfa268: 0x00007fff801993b0 CoreFoundation`__block_descriptor_64_e8_32o_e11_v24 ?0 8 16l 0x7ffee8cfa270: 0x00007fd38b106660 -> 0x00007fff86d70b80 (void *)0x00007fff86d70ba8: __NSDictionaryI 0x7ffee8cfa278: 0x00007fd38b106670 0x7ffee8cfa280: 0x0000000000000003 0x7ffee8cfa288: 0x0000000000000001 0x7ffee8cfa290: 0xe4fcf923d28f0079 0x7ffee8cfa298: 0x00007ffee8cfa480 -> 0x0000000106f095f8 @"'v'" (lldb) x/a $rax 0x7fd38b106670: 0x0000000000000000 (lldb) ## r14 是对 key 进行 hash，并处理后的一个偏移量，这里是判断旧的位置是否有值 0x7fff203435ce <+166>: cmp qword ptr [rax + 8*r14], 0x0 0x7fff203435d3 <+171>: je 0x7fff20343618 ; <+240> ## 如果旧的位置有值，则会抛弃键值对，并将 __NSDictionaryI._used 减一 0x7fff203435d5 <+173>: mov rax, qword ptr [rbx + 0x20] 0x7fff203435d9 <+177>: mov rcx, qword ptr [rip + 0x66a2c540] ; __NSDictionaryI._used 0x7fff203435e0 <+184>: mov rdx, qword ptr [rax + rcx] 0x7fff203435e4 <+188>: lea rsi, [rdx - 0x1] 0x7fff203435e8 <+192>: movabs rdi, 0x1ffffffffffffff 0x7fff203435f2 <+202>: and rdi, rsi 0x7fff203435f5 <+205>: movabs rsi, -0x200000000000000 0x7fff203435ff <+215>: and rsi, rdx 0x7fff20343602 <+218>: or rsi, rdi 0x7fff20343605 <+221>: mov qword ptr [rax + rcx], rsi 0x7fff20343609 <+225>: add rsp, 0x28 0x7fff2034360d <+229>: pop rbx 0x7fff2034360e <+230>: pop r12 0x7fff20343610 <+232>: pop r13 0x7fff20343612 <+234>: pop r14 0x7fff20343614 <+236>: pop r15 0x7fff20343616 <+238>: pop rbp 0x7fff20343617 <+239>: ret ## 旧的位置是 nil 时，代表没有发生冲突，可以将键值对存入字典 ## test 会更新 ZF 标识位，用法如下所示 0 0 1 0 0 1 0 1 <- 输入值 0 0 0 0 1 0 0 1 <- 测试值 0 0 0 0 0 0 0 1 <- 结果：ZF=0 0 0 1 0 0 1 0 0 <- 输入值 0 0 0 0 1 0 0 1 <- 测试值 0 0 0 0 0 0 0 0 <- 结果：ZF=1 ## 本例中， cl 是 1，test cl, 0x1 结果非0，导致 ZF=0 0x7fff20343618 <+240>: mov rcx, qword ptr [rbx + 0x38] 0x7fff2034361c <+244>: test cl, 0x8 0x7fff2034361f <+247>: jne 0x7fff20343637 ; <+271> 0x7fff20343621 <+249>: test cl, 0x1 ## jne 检测到 zf=0 后会进行跳转到 0x7fff2034363d 进行下一步处理 0x7fff20343624 <+252>: jne 0x7fff2034363d ; <+277> 0x7fff20343626 <+254>: test r12, r12 0x7fff20343629 <+257>: jle 0x7fff20343637 ; <+271> ## 对 value 进行 retain，结果是 $rax 0x7fff2034362b <+259>: mov rdi, r12 0x7fff2034362e <+262>: call 0x7fff204ab50c ; symbol stub for: objc_retain ## 0x7fff20343633 <+267>: mov rax, qword ptr [rbx + 0x28] 0x7fff20343637 <+271>: mov qword ptr [rax + 8*r14], r12 0x7fff2034363b <+275>: jmp 0x7fff20343657 ; <+303> ## 对 key 进行复制 0x7fff2034363d <+277>: mov rsi, qword ptr [rip + 0x66a2a654] ; "copyWithZone:" 0x7fff20343644 <+284>: mov rdi, r12 0x7fff20343647 <+287>: xor edx, edx 0x7fff20343649 <+289>: call qword ptr [rip + 0x5fce9c29] ; (void *)0x00007fff20173780: objc_msgSend 0x7fff2034364f <+295>: mov rcx, qword ptr [rbx + 0x28] ## 将复制的 key 存储到指定位置 0x7fff20343653 <+299>: mov qword ptr [rcx + 8*r14], rax 0x7fff20343657 <+303>: mov rdi, qword ptr [rbp - 0x30] 0x7fff2034365b <+307>: mov rax, qword ptr [rbx + 0x28] ## 将 value 移到 (r14<<3+8) 0x7fff2034365f <+311>: shl r14, 0x3 0x7fff20343663 <+315>: or r14, 0x8 0x7fff20343667 <+319>: mov qword ptr [rax + r14], rdi

如下图所示，经过上面的一些列流程后，dic 会变成一个只持有 k 和 v 键值对的结构体

总结

本文主要分享了 NSDictionary 的两个子类：__NSPlaceholderDictionary 和 __NSDictionaryI 的构造过程进行了简单的分析。

下一篇暂定会介绍 cow 机制。