从 Objective-C 和 Swift 看字典的性能优化（2）
从 Objective-C 和 Swift 看字典的性能优化（2）
酷酷的哀殿
发布于 2021-05-14 10:39:59
发布于 2021-05-14 10:39:59
NSMutableDictionary 的创建流程
本小节以下面的代码为例介绍 NSMutableDictionary 的创建过程
NSMutableDictionary *mutableDic = [NSMutableDictionary dictionary];
通过下面的指令，我们可以发现 NSMutableDictionary 类并不存在类方法 +[NSMutableDictionary dictionary]
(lldb) b +[NSMutableDictionary dictionary]
Breakpoint 11: no locations (pending).
WARNING: Unable to resolve breakpoint to any actual locations.
所以，我们需要通过条件断点的方式添加合适的断点
(lldb) bmessage +[NSMutableDictionary dictionary]
Setting a breakpoint at \+[NSDictionary dictionary] with condition (void*)object_getClass((id)$x0) == 0x00000001fbbbae68
Breakpoint 19: where = CoreFoundation`+[NSDictionary dictionary], address = 0x00000001a2404ec0
添加断点后，我们会发现+[NSMutableDictionary dictionary] 会跳转到下面的汇编执行初始化任务：
CoreFoundation`+[NSDictionary dictionary]:
0x1a2404ec0 <+0>: stp x29, x30, [sp, #-0x10]!
0x1a2404ec4 <+4>: mov x29, sp
# objc_alloc
0x1a2404ec8 <+8>: bl 0x1a2585f14 ; symbol stub for: -[NSMutableArray replaceObject:].cold.1
# initWithObjects:forKeys:count:
0x1a2404ecc <+12>: adrp x8, 308195
0x1a2404ed0 <+16>: add x1, x8, #0xd8 ; =0xd8
0x1a2404ed4 <+20>: mov x2, #0x0
0x1a2404ed8 <+24>: mov x3, #0x0
0x1a2404edc <+28>: mov x4, #0x0
# 发送消息
0x1a2404ee0 <+32>: bl 0x1a2153e28
0x1a2404ee4 <+36>: ldp x29, x30, [sp], #0x10
# objc_autorelease
0x1a2404ee8 <+40>: b 0x1a2585f44 ; symbol stub for: -[NSMutableArray replaceObjectsAtIndexes:withObjects:].cold.1
该步骤与 __NSDictionaryI 类型，同样会依次执行以下三个任务：
- 通过
objc_alloc申请一块区域，并初始化isa等信息 - 通过
-[NSDictionary initWithObjects:forKeys:count:]实例化 - 通过
objc_autorelease将实例放到自动释放池（）
指令复用
值得注意的是，因为 CoreFoundation 动态库存在很多对 objc_alloc 函数的调用。所以，很多可以复用的汇编指令片段会被提取到单个函数中。
以对 objc_alloc 的调用为例，汇编指令都被会提取并放到一个单独的函数：-[NSMutableArray replaceObject:].cold.1 。
受 arm64 固定指令长度影响，调用函数需要3个指令
可复用指令：
CoreFoundation`-[NSMutableArray replaceObject:].cold.1:
0x1a2585f14 <+0>: adrp x16, 82705
0x1a2585f18 <+4>: add x16, x16, #0x28 ; =0x28
-> 0x1a2585f1c <+8>: br x16
image
NSDate 创建时，同样存在对 -[NSMutableArray replaceObject:].cold.1 的调用
objc_alloc
与 __NSPlaceholderDictionary 的创建过程类似，可变字典同样会通过 objc_alloc 进行层层转发，并跳转到 +[NSDictionary allocWithZone:] 进行下一步处理。
+[NSDictionary allocWithZone:]
+[NSDictionary allocWithZone:] 会先判断 self 的类型
image
检测到 NSMutableDictionary 类型后，会调到 +160 行后进行安全检测，并调用 __NSDictionaryMutablePlaceholder 进行下一步处理
安全检测相关知识可以搜索关键字 clang stack_chk_guard stackprotector
image
__NSDictionaryMutablePlaceholder
与 __NSPlaceholderDictionary 的创建过程类似，__NSDictionaryMutablePlaceholder 同样会将 __NSPlaceholderDictionary 的实例赋值给 $x0 寄存器并返回
注意下面的地址
0x1f3d07178，本文还会再次讲到
image
-[__NSPlaceholderDictionary initWithObjects:forKeys:count:]
-[__NSPlaceholderDictionary initWithObjects:forKeys:count:] 会根据情况对入参进行一系列的判断校验，比如 keys 是 NULL 并且 count 大于 0 时，会抛出异常
入参校验可以参考下面汇编代码的注释：
CoreFoundation`-[__NSPlaceholderDictionary initWithObjects:forKeys:count:]:
0x1a24097b8 <+0>: stp x29, x30, [sp, #-0x10]!
0x1a24097bc <+4>: mov x29, sp
# keys 非 NULL，则跳转到 +16
0x1a24097c0 <+8>: cbnz x3, 0x1a24097c8 ; <+16>
# keys 是 NULL，count 大于 0，抛出异常
0x1a24097c4 <+12>: cbnz x4, 0x1a24098a8 ; <+240>
# 校验 count 数量是否过大，如果过大抛出异常
0x1a24097c8 <+16>: lsr x8, x4, #61
0x1a24097cc <+20>: cbnz x8, 0x1a24098b0 ; <+248>
# count 等于 0，调整到 +52 处理
0x1a24097d0 <+24>: cbz x4, 0x1a24097ec ; <+52>
## 对 keys 进行非空校验
# 开始计数，寄存器 x8 = 0
0x1a24097d4 <+28>: mov x8, #0x0
# 读取当前 key
0x1a24097d8 <+32>: ldr x9, [x3, x8, lsl #3]
# 如果某个 key 是 nil， 则抛出异常
0x1a24097dc <+36>: cbz x9, 0x1a2409898 ; <+224>
# 计数自增1
0x1a24097e0 <+40>: add x8, x8, #0x1 ; =0x1
# 判断是否等于 count
0x1a24097e4 <+44>: cmp x4, x8
# 如果不等于 count，则调到 +32 进行判断，直到遍历结束
0x1a24097e8 <+48>: b.ne 0x1a24097d8 ; <+32>
# values 不等于 NULL，则调到 +60 处理
0x1a24097ec <+52>: cbnz x2, 0x1a24097f4 ; <+60>
# values 等于 NULL， count 不等于 0，则调到 +256 抛出异常
0x1a24097f0 <+56>: cbnz x4, 0x1a24098b8 ; <+256>
# values 等于 NULL，count 等于 0，调到 +88 进行处理
0x1a24097f4 <+60>: cbz x4, 0x1a2409810 ; <+88>
## 对 values 进行非空校验
0x1a24097f8 <+64>: mov x8, #0x0
0x1a24097fc <+68>: ldr x9, [x2, x8, lsl #3]
0x1a2409800 <+72>: cbz x9, 0x1a24098a0 ; <+232>
0x1a2409804 <+76>: add x8, x8, #0x1 ; =0x1
0x1a2409808 <+80>: cmp x4, x8
0x1a240980c <+84>: b.ne 0x1a24097fc ; <+68>
# 获取 ___immutablePlaceholderDictionary
-> 0x1a2409810 <+88>: adrp x8, 334078
0x1a2409814 <+92>: add x8, x8, #0x168 ; =0x168
# self 等于 ___immutablePlaceholderDictionary 时，调整到 +144 进行创建任务
0x1a2409818 <+96>: cmp x0, x8
0x1a240981c <+100>: b.eq 0x1a2409848 ; <+144>
# 获取 ___mutablePlaceholderDictionary
0x1a2409820 <+104>: adrp x8, 334078
0x1a2409824 <+108>: add x8, x8, #0x178 ; =0x178
# self 等于 ___immutablePlaceholderDictionary 时，跳转到 +264 中断
0x1a2409828 <+112>: cmp x0, x8
0x1a240982c <+116>: b.ne 0x1a24098c0 ; <+264>
## 可变字典创建任务
0x1a2409830 <+120>: mov x0, x3
0x1a2409834 <+124>: mov x1, x2
0x1a2409838 <+128>: mov x2, x4
0x1a240983c <+132>: mov w3, #0x3
0x1a2409840 <+136>: ldp x29, x30, [sp], #0x10
0x1a2409844 <+140>: b 0x1a256c344 ; __NSDictionaryM_new
## 不可变字典创建任务
0x1a2409848 <+144>: cmp x4, #0x1 ; =0x1
0x1a240984c <+148>: b.eq 0x1a2409868 ; <+176>
0x1a2409850 <+152>: cbnz x4, 0x1a240987c ; <+196>
0x1a2409854 <+156>: adrp x8, 334061
0x1a2409858 <+160>: add x8, x8, #0xdd0 ; =0xdd0
0x1a240985c <+164>: ldr x0, [x8]
0x1a2409860 <+168>: ldp x29, x30, [sp], #0x10
0x1a2409864 <+172>: b 0x1a2153e58
0x1a2409868 <+176>: ldr x0, [x3]
0x1a240986c <+180>: ldr x1, [x2]
0x1a2409870 <+184>: mov w2, #0x1
0x1a2409874 <+188>: ldp x29, x30, [sp], #0x10
0x1a2409878 <+192>: b 0x1a2462a90 ; __NSSingleEntryDictionaryI_new
0x1a240987c <+196>: mov x0, x3
0x1a2409880 <+200>: mov x1, x2
0x1a2409884 <+204>: mov x2, #0x0
0x1a2409888 <+208>: mov x3, x4
0x1a240988c <+212>: mov w4, #0x1
0x1a2409890 <+216>: ldp x29, x30, [sp], #0x10
0x1a2409894 <+220>: b 0x1a2450e0c ; __NSDictionaryI_new
0x1a2409898 <+224>: mov x0, x8
0x1a240989c <+228>: bl 0x1a25841f4 ; -[__NSPlaceholderDictionary initWithObjects:forKeys:count:].cold.5
0x1a24098a0 <+232>: mov x0, x8
0x1a24098a4 <+236>: bl 0x1a25841c4 ; -[__NSPlaceholderDictionary initWithObjects:forKeys:count:].cold.4
0x1a24098a8 <+240>: mov x0, x4
0x1a24098ac <+244>: bl 0x1a2584134 ; -[__NSPlaceholderDictionary initWithObjects:forKeys:count:].cold.1
# '*** -[__NSPlaceholderDictionary initWithObjects:forKeys:count:]: count (0) of objects array is ridiculous'
0x1a24098b0 <+248>: mov x0, x4
0x1a24098b4 <+252>: bl 0x1a2584164 ; -[__NSPlaceholderDictionary initWithObjects:forKeys:count:].cold.2
0x1a24098b8 <+256>: mov x0, x4
0x1a24098bc <+260>: bl 0x1a2584194 ; -[__NSPlaceholderDictionary initWithObjects:forKeys:count:].cold.3
0x1a24098c0 <+264>: brk #0x1
前面提到过地址 0x00000001d1c67178。在实际运行中， -[__NSPlaceholderDictionary initWithObjects:forKeys:count:] 会通过 self 的地址判断是否需要生成可变类型的实例
image
如果需要生成可变类型，会将 keys、objects、count、常量3 当做参数传给 __NSDictionaryM_new 函数
image
__NSDictionaryM_new
与不可变字典的处理类似，__NSDictionaryM_new 同样将 count 与 常量数组 __NSDictionaryCapacities的值进行判断，并创建合适的实例
首先，我们先看看根据汇编反推到的字典内部结构
struct KKDic_t {
__strong Class isa;
struct {
const id *buffer;
union {
struct {
unsigned long mutations;
};
struct {
unsigned int muts;
unsigned int other;
};
struct {
unsigned mutbits : 31;
unsigned copyKeys : 1;
unsigned used : 25;
unsigned kvo : 1;
unsigned szidx : 6;
};
} state;
} storage;
struct __cow_state_t *cow;
};
used代表已经使用的空间大小，与开发者常用的count属性对应mutbits代表对字典变更的次数。初始化时是1，增删会加1szidx通过搭配 常量数组__NSDictionarySizes，获取字典的容量copyeKeys: 代表需要复制 key
CoreFoundation`__NSDictionaryM_new:
第0个参数是 keys
第1个参数是 keys
第2个参数是 keys
第3个参数是 一个 NS_OPTIONS：可变字典Option
根据汇编反推出的含义：
typedef NS_OPTIONS(NSUInteger, 可变字典Option) {
NSEnumeration初始化复制key = (1UL << 0), // 可以查看函数指令 +520 +556 处的逻辑
NSEnumeration其它情况复制key = (1UL << 1),
NSEnumeration屏蔽对Value进行Retain = (1UL << 2),
};
0x1a256c344 <+0>: sub sp, sp, #0xb0 ; =0xb0
0x1a256c348 <+4>: stp x28, x27, [sp, #0x50]
0x1a256c34c <+8>: stp x26, x25, [sp, #0x60]
0x1a256c350 <+12>: stp x24, x23, [sp, #0x70]
0x1a256c354 <+16>: stp x22, x21, [sp, #0x80]
0x1a256c358 <+20>: stp x20, x19, [sp, #0x90]
0x1a256c35c <+24>: stp x29, x30, [sp, #0xa0]
0x1a256c360 <+28>: add x29, sp, #0xa0 ; =0xa0
# 临时存储 keys 和 常量3 到栈上
0x1a256c364 <+32>: stp x0, x3, [sp, #0x38]
# x20 = x2，代表 count
0x1a256c368 <+36>: mov x20, x2
# values 放到 [sp, #0x30]
0x1a256c36c <+40>: str x1, [sp, #0x30]
##### 一、下面的代码是计算 szidx 和字典的容量
为了降低冲突，容量通常会大于 count；比如 count 等于 6，容量是 7
1. 准备参数
# x19 初始化为 0
0x1a256c370 <+44>: mov x19, #0x0
# x8代表 szidx * 8，初始化时是 0
0x1a256c374 <+48>: mov x8, #0x0
# 后续用来更新 szidx
0x1a256c378 <+52>: mov x9, #0x400000000000000
# x10 代表 __NSDictionaryCapacities
0x1a256c37c <+56>: adrp x10, 464
0x1a256c380 <+60>: add x10, x10, #0x900 ; =0x900
(lldb) image lookup -a $x10
Address: CoreFoundation[0x000000018069c900] (CoreFoundation.__TEXT.__const + 1749472)
Summary: CoreFoundation`__NSDictionaryCapacities
2. 通过循环方式查找 szidx 对应的值
终止条件是 count 过大导致异常，或者 __NSDictionaryCapacities[szidx]>=count
# x11 代表 __NSDictionaryCapacities[szidx]
0x1a256c384 <+64>: ldr x11, [x10, x8]
# 和 count 进行比较
0x1a256c388 <+68>: cmp x11, x20
#大于等于 count 时终止遍历，转到 +96
0x1a256c38c <+72>: b.hs 0x1a256c3a4 ; <+96>
# 指向下一个值，x8 += 0x8
0x1a256c390 <+76>: add x8, x8, #0x8 ; =0x8
# x19 实际上就是 0x400000000000000 * szidx
0x1a256c394 <+80>: add x19, x19, x9
后面会将循环次数存到结构体的 szidx 位置
struct {
unsigned mutbits : 31;
unsigned copyKeys : 1;
unsigned used : 25;
unsigned kvo : 1;
unsigned szidx : 6;
};
# 安全校验：移量是否等于 0x140
0x1a256c398 <+84>: cmp x8, #0x140 ; =0x140
# 不等于才能转到 +64 继续遍历
0x1a256c39c <+88>: b.ne 0x1a256c384 ; <+64>
# 等于 0x140 时触发中断，代表出现了字典无法处理的情况
0x1a256c3a0 <+92>: brk #0x1
3. 从 常量数组 取出桶的容量
x22 保存 从 __NSDictionarySizes[szidx] 取出的字典容量
0x1a256c3a4 <+96>: adrp x9, 464
0x1a256c3a8 <+100>: add x9, x9, #0xa40 ; =0xa40
0x1a256c3ac <+104>: ldr x22, [x9, x8]
(lldb) image lookup -a $x9
Address: CoreFoundation[0x000000018069ca40] (CoreFoundation.__TEXT.__const + 1749792)
Summary: CoreFoundation`__NSDictionarySizes
##### 二、创建空间
# 取出类 __NSDictionaryM
0x1a256c3b0 <+108>: adrp x0, 366160
0x1a256c3b4 <+112>: add x0, x0, #0x268 ; =0x268
(lldb) image lookup -a $x0
Address: CoreFoundation[0x00000001d9b1c268] (CoreFoundation.__DATA_DIRTY.__objc_data + 8680)
Summary: (void *)0x00000001fbbbc290: __NSDictionaryM
# 调用 objc_opt_self，等价于 [__NSDictionaryM self]
0x1a256c3b8 <+116>: bl 0x1a25860a0 ; symbol stub for: -[NSSet intersectsOrderedSet:].cold.1
# 调用 __CFAllocateObject 创建对象
0x1a256c3bc <+120>: mov x1, #0x0
0x1a256c3c0 <+124>: bl 0x1a251b1d4 ; __CFAllocateObject
##### 三、更新 storage
1、动态读取 实例变量 __NSDictionaryM.storage 的偏移量
0x1a256c3c4 <+128>: adrp x10, 367773
0x1a256c3c8 <+132>: ldrsw x8, [x10, #0xdb8]
Address: CoreFoundation[0x00000001da169db8] (CoreFoundation.__DATA.__objc_ivar + 1192)
Summary: CoreFoundation`__NSDictionaryM.storage
# x8 指向 storage 位置
0x1a256c3cc <+136>: add x8, x0, x8
2、初始化状态，等价于 dic->storage.state.muts = 1;
0x1a256c3d0 <+140>: mov w9, #0x1
0x1a256c3d4 <+144>: str w9, [x8, #0x8]
3、更新 copyKeys
# 再次动态读取 实例变量 __NSDictionaryM.storage 的偏移量
0x1a256c3d8 <+148>: ldrsw x8, [x10, #0xdb8]
# 将 dic 临时存储到栈上
0x1a256c3dc <+152>: str x0, [sp, #0x10]
# x21 指向 storage 位置
0x1a256c3e0 <+156>: add x21, x0, x8
# x8 就是之前刚存入的 state
0x1a256c3e4 <+160>: ldr x8, [x21, #0x8]
# 取出函数开头部分保存的 可变字典Option
0x1a256c3e8 <+164>: ldr x9, [sp, #0x40]
# 可变字典Option<<30
0x1a256c3ec <+168>: lsl w9, w9, #30
# x9 = (可变字典Option<<30)&0x80000000 = 0x80000000
0x1a256c3f0 <+172>: and x9, x9, #0x80000000
通过和 x9 进行 orr 操作
等价于根据 **可变字典Option & NSEnumeration其它情况复制key ** 决定是否将结构体的 copyKeys 置为 1
struct {
unsigned mutbits : 31;
unsigned copyKeys : 1;
unsigned used : 25;
unsigned kvo : 1;
unsigned szidx : 6;
};
# x10 = 0xffffffff7fffffff
0x1a256c3f4 <+176>: mov x10, #-0x80000001
# 0x03ffffff7fffffff
0x1a256c3f8 <+180>: movk x10, #0x3ff, lsl #48
前面两个指令等价于下面这个复杂的逻辑
(lldb) p/x ((long)0-0x80000001)&(((long)0x3ff<<48)|(((long)1<<48)-1))
(long) $57 = 0x 03ff ffff 7fff ffff
# mutbits 与 x10 进行 and 计算
0x1a256c3fc <+184>: and x8, x8, x10
前面的几个指令相当于对结构体的 copyKeys 和 szidx 做了置0操作。
struct {
unsigned mutbits : 31;
unsigned copyKeys : 1;
unsigned used : 25;
unsigned kvo : 1;
unsigned szidx : 6;
};
# 或计算
0x1a256c400 <+188>: orr x9, x19, x9
x9 等价于下面的计算，其中 3是 __NSDictionaryM_new 函数接收的一个参数
(lldb) p/x ((long)3<<30)&0x80000000|(0x0400000000000000*循环次数)
高位的 0x04000000 代表循环1次，0x08000000 代表循环2次，依次类推
低位的 0x80000000，代表是否进行 copyKeys，传入的 __NSDictionaryM_new 函数接收的**可变字典Option & NSEnumeration其它情况复制key ** 决定是否置为 0x80000000
(long) $12 = 0x 0400 0000 8000 0000
struct {
unsigned mutbits : 31;
unsigned copyKeys : 1;
unsigned used : 25;
unsigned kvo : 1;
unsigned szidx : 6;
};
# x8 保存最后的新结构体
0x1a256c404 <+192>: orr x8, x9, x8
# 存储到 dic->storage.state
0x1a256c408 <+196>: str x8, [x21, #0x8]
#### 空字典执行逻辑 ####
下面的箭头代表跳转
0. +152 将 dic 临时存储到栈上
1. +200 判断大小是否等于0
2. +228 dic->storage.buffer 置为 NULL
3. +664 cow 置为 NULL
# x20 是字典的大小，如果等于0，跳转到 +228
0x1a256c40c <+200>: cbz x20, 0x1a256c428 ; <+228>
# x22 代表字典容量
0x1a256c410 <+204>: ubfiz x1, x22, #4, #32
# ubfiz 指令与下面的代码等价，代表最多有个 UINT32_MAX 个键值对
NSLog(@"%x", INT32_MAX); // 7fffffff
NSLog(@"%x", UINT32_MAX); // ffffffff
(lldb) p/x (0xabcdef1234567890&UINT32_MAX)<<4
(unsigned long) $12 = 0x0000000345678900
# 左移 4 位 的原因是：键值对需要2个指针保存 key 和 value，64位系统需要 8*2 的空间
# 调用 calloc 申请一块合适的内存，内存大小是 1 * (size << 4)
0x1a256c414 <+208>: mov w0, #0x1
0x1a256c418 <+212>: bl 0x1a2585770 ; symbol stub for: -[NSArray indexesOfObjectsWithOptions:passingTest:].cold.1
# 更新字典的buffer *(dic->storage.buffer)
0x1a256c41c <+216>: mov x24, x0
0x1a256c420 <+220>: str x0, [x21]
0x1a256c424 <+224>: b 0x1a256c430 ; <+236>
# 字典大小等于0时，将 x24 置为0，并将 dic->storage.buffer 置为 NULL
0x1a256c428 <+228>: mov x24, #0x0
0x1a256c42c <+232>: str xzr, [x21]
# 函数入口处曾经将 keys 和 values 指针临时保存到 [sp, #0x38],count 保存到 x20
# 下面的代码会依次校验 keys values size 是否为0，如果是 0，则跳转到 +664 处理
0x1a256c430 <+236>: ldr x8, [sp, #0x38]
0x1a256c434 <+240>: cbz x8, 0x1a256c5dc ; <+664>
0x1a256c438 <+244>: ldr x8, [sp, #0x30]
0x1a256c43c <+248>: cbz x8, 0x1a256c5dc ; <+664>
0x1a256c440 <+252>: cbz x20, 0x1a256c5dc ; <+664>
# 后面会遍历 keys，x23 代表第几个
0x1a256c444 <+256>: mov x23, #0x0
# x22 是容量，x26 后面用于将 key 打散的分母
0x1a256c448 <+260>: and x26, x22, #0xffffffff
# buffer 的前 n 个是 key，后 n 个是 value，所以这里通过 buffer+容量*8 ,计算出 value 存储的起始区域
0x1a256c44c <+264>: add x8, x24, w22, uxtw #3
# values 起始区域备用
0x1a256c450 <+268>: str x8, [sp, #0x48]
# 获取 一个名为 hash 的 Selector 并存到 [sp, #0x20] 备用
0x1a256c454 <+272>: adrp x8, 309224
0x1a256c458 <+276>: add x8, x8, #0x6ba ; =0x6ba
将 hash 和 count 存储到 [sp, #0x20] 和 [sp, #0x28]
0x1a256c45c <+280>: stp x8, x20, [sp, #0x20]
(lldb) image lookup -a $x8
Address: libobjc.A.dylib[0x00000001cbcb46ba] (libobjc.A.dylib.__OBJC_RO + 9668282)
Summary:
(lldb) po (SEL)$x8
"hash"
# 获取一个名为 copyWithZone: 的 Selector，并存到 [sp, #0x8] 备用
0x1a256c460 <+284>: adrp x8, 308270
0x1a256c464 <+288>: add x8, x8, #0xbba ; =0xbba
0x1a256c468 <+292>: str x8, [sp, #0x8]
(lldb) image lookup -va ((($pc>>12)+308270)<<12)+0xbba
Address: libobjc.A.dylib[0x00000001cb8fabba] (libobjc.A.dylib.__OBJC_RO + 5761978)
Summary:
(lldb) image lookup -a $x8
Address: libobjc.A.dylib[0x00000001cb8fabba] (libobjc.A.dylib.__OBJC_RO + 5761978)
(lldb) po (SEL)$x8
"copyWithZone:"
# 将字典取出来；+152 曾经将 dic 存到 [sp, #0x10]
0x1a256c46c <+296>: ldr x8, [sp, #0x10]
# 将字典的 storage 地址存储到 [sp, #0x18]
0x1a256c470 <+300>: add x8, x8, #0x8 ; =0x8
0x1a256c474 <+304>: str x8, [sp, #0x18]
# x25 保存 ___NSDictionaryM_DeletedMarker
0x1a256c478 <+308>: adrp x25, 333723
0x1a256c47c <+312>: add x25, x25, #0x1a8 ; =0x1a8
(lldb) image lookup -a ((($pc>>12)+333723)<<12)+0x1a8
Address: CoreFoundation[0x00000001d1c671a8] (CoreFoundation.__DATA_CONST.__const + 1939560)
Summary: CoreFoundation`___NSDictionaryM_DeletedMarker
# 获取 keys; +32 指令将 keys 存到了 [sp, #0x38]
0x1a256c480 <+316>: ldr x8, [sp, #0x38]
# 开始取出 key
0x1a256c484 <+320>: ldr x27, [x8, x23, lsl #3]
0x1a256c488 <+324>: mov x0, x27
# 开始取出 "hash"
0x1a256c48c <+328>: ldr x1, [sp, #0x20]
# 发送消息
0x1a256c490 <+332>: bl 0x1a2153e28
# 字典容量等于 0 时，直接调到 +448 继续执行
0x1a256c494 <+336>: mov x20, x22
0x1a256c498 <+340>: cbz w22, 0x1a256c504 ; <+448>
# 下面两个指令相当于 hash%字典容量，代表即将插入的桶相对起始位置的偏移量。以下简称“桶偏移量1”
; x8 = x0/x26
; x21 = x0-x8*x26
; x21 = x0-(x0/x26)*x26
; x21 = x0%x26
0x1a256c49c <+344>: udiv x8, x0, x26
0x1a256c4a0 <+348>: msub x21, x8, x26, x0
# 获取一个名为 isEqual: 的 Selector
0x1a256c4a4 <+352>: adrp x8, 310043
0x1a256c4a8 <+356>: add x28, x8, #0x3a ; =0x3a
(lldb) p/x ((($pc>>12)+310043)<<12)+0x3a
(unsigned long) $18 = 0x00000001ee08703a
(lldb) po (SEL)$18
"isEqual:"
# x22 等于桶的可用容量，后面 key 的 hash冲突后会+1
0x1a256c4ac <+360>: mov x22, x26
0x1a256c4b0 <+364>: mov x19, x26
# x24 指向 buffer，x21 是“桶偏移量1”。冲突后，x21 就会向后顺移一位，直到找到合适的位置
# 所以， x0 指向桶的位置存储的内容
0x1a256c4b4 <+368>: ldr x0, [x24, x21, lsl #3]
# 判断“桶偏移量1”位置是否有旧值，没有旧值，直接调到 +464 处理
0x1a256c4b8 <+372>: cbz x0, 0x1a256c514 ; <+464>
# 此处开始处理 “桶偏移量1”存在旧值（hash 冲突）的场景
# 判断是否被标为 ___NSDictionaryM_DeletedMarker ，相同直接调到 +412 处理
0x1a256c4bc <+376>: cmp x0, x25
0x1a256c4c0 <+380>: b.eq 0x1a256c4e0 ; <+412>
# 判断旧的位置和即将存入的 key 地址是否相同，如果相同，进入 +456 的逻辑（key 被放到“桶偏移量1”）
0x1a256c4c4 <+384>: cmp x0, x27
0x1a256c4c8 <+388>: b.eq 0x1a256c50c ; <+456>
# 退化逻辑，通过 isEqual: 判断两个 key 是否相同
0x1a256c4cc <+392>: mov x1, x28
0x1a256c4d0 <+396>: mov x2, x27
# 发送消息
0x1a256c4d4 <+400>: bl 0x1a2153e28
# 如果不等，则说明 key 真的冲突了，需要进入 key 冲突处理逻辑（计算新的“桶偏移量2”，并放入 key）
0x1a256c4d8 <+404>: tbz w0, #0x0, 0x1a256c4e8 ; <+420>
# 如果相同，进入 +456 的逻辑（key 被放到“桶偏移量1”）
0x1a256c4dc <+408>: b 0x1a256c50c ; <+456>
# 如果 x19 仍然等于 字典容量： x26，则 x19=x21,否则保持原样
0x1a256c4e0 <+412>: cmp x19, x26
0x1a256c4e4 <+416>: csel x19, x21, x19, eq
loc_1804cc4e8:
# key hash 冲突处理；
# 1. 将“桶偏移量1”+1
0x1a256c4e8 <+420>: add x8, x21, #0x1 ; =0x1
# 2. 相加后是否超过 桶的数量
0x1a256c4ec <+424>: cmp x8, x26
# 3. 如果小于，则x9=0，否则等于 相加后的值
0x1a256c4f0 <+428>: csel x9, xzr, x26, lo
# 4. 再将 x8-x9;
0x1a256c4f4 <+432>: sub x21, x8, x9
上面的指令合并后如下：
if {(x21+1)<x26) {
x21 = x8-x9 = x8-0 = x21+1-0 = x21+1;
} else {
x21 = x8 -x9 = x8 - x26 = x21+1-x26;
}
简单来说就是“桶偏移量2” = (“桶偏移量1”+1) % 桶的数量
# x22 等于桶的可用容量，减一后，再从 + 368 开始处理，会判断 “桶偏移量2” 位置是否存在冲突
0x1a256c4f8 <+436>: subs x22, x22, #0x1 ; =0x1
0x1a256c4fc <+440>: b.ne 0x1a256c4b4 ; <+368>
0x1a256c500 <+444>: b 0x1a256c51c ; <+472>
0x1a256c504 <+448>: mov x19, #0x0
0x1a256c508 <+452>: b 0x1a256c51c ; <+472>
x19=x21
0x1a256c50c <+456>: mov x19, x21
0x1a256c510 <+460>: b 0x1a256c51c ; <+472>
# 如果 x19 仍然等于 x26，则 x19 等于 x21，否则保持原样
0x1a256c514 <+464>: cmp x19, x26
0x1a256c518 <+468>: csel x19, x21, x19, eq
# 又一次取出 “桶偏移量“对应的桶存储的内容，如果不存在内容，则转到 +512 处理
0x1a256c51c <+472>: ldr x8, [x24, x19, lsl #3]
0x1a256c520 <+476>: cbz x8, 0x1a256c544 ; <+512>
# 取出 buffer 对应 values 存储区域的起始位置
0x1a256c524 <+480>: ldr x8, [sp, #0x48]
# 取出当前 key 对应的 value
0x1a256c528 <+484>: ldr x0, [x8, x19, lsl #3]
0x1a256c52c <+488>: cmp x0, #0x1 ; =0x1
x22 等于 桶的数量
0x1a256c530 <+492>: mov x22, x20
x20 是 count
0x1a256c534 <+496>: ldr x20, [sp, #0x28]
lt 代表小于0或者无序，如果 value 的值小于1，则调到 +616 执行对 value 的处理
0x1a256c538 <+500>: b.lt 0x1a256c5ac ; <+616>
# 否则，调用 objc_release 释放旧的值
0x1a256c53c <+504>: bl 0x1a2153e4c
然后再跳转到 +616 执行对 value 的处理
0x1a256c540 <+508>: b 0x1a256c5ac ; <+616>
# 找到了合适的位置，开始存储 key
# [sp, #0x38] 是 keys
0x1a256c544 <+512>: ldr x8, [sp, #0x38]
# x23 代表当前在处理的 key 索引，x0 等于 key
0x1a256c548 <+516>: ldr x0, [x8, x23, lsl #3]
# [sp, #0x40] 存储了函数接收的一个控制参数，
0x1a256c54c <+520>: ldr x8, [sp, #0x40]
如果参数末位非0，则跳转到 556 处理
0x1a256c550 <+524>: tbnz w8, #0x0, 0x1a256c570 ; <+556>
否则，将 key 的直接直接存入对应位置
0x1a256c554 <+528>: str x0, [x24, x19, lsl #3]
key 和 1 比较
0x1a256c558 <+532>: cmp x0, #0x1 ; =0x1
x22 等于 桶的数量
x20 是 count
0x1a256c55c <+536>: mov x22, x20
0x1a256c560 <+540>: ldr x20, [sp, #0x28]
如果是空，再跳转
0x1a256c564 <+544>: b.lt 0x1a256c588 ; <+580>
对 key 进行 retain 操作
0x1a256c568 <+548>: bl 0x1a2153e58
0x1a256c56c <+552>: b 0x1a256c588 ; <+580>
# 获取前面保存的 SEL: copyWithZone:
0x1a256c570 <+556>: ldr x1, [sp, #0x8]
0x1a256c574 <+560>: mov x2, #0x0
# 发送消息，目的是将 key 进行复制
0x1a256c578 <+564>: bl 0x1a2153e28
# 将复制的 key 存到对应的桶；x24 指向 buffer，加上偏移量 x19 后就可以执行真正的桶
0x1a256c57c <+568>: str x0, [x24, x19, lsl #3]
; x22 等于 桶的数量
; x20 是 count
0x1a256c580 <+572>: mov x22, x20
0x1a256c584 <+576>: ldr x20, [sp, #0x28]
# 动态读取 实例变量 __NSDictionaryM.storage 的偏移量
0x1a256c588 <+580>: adrp x8, 367773
0x1a256c58c <+584>: ldrsw x8, [x8, #0xdb8]
Address: CoreFoundation[0x00000001da169db8] (CoreFoundation.__DATA.__objc_ivar + 1192)
Summary: CoreFoundation`__NSDictionaryM.storage
取出 dic->storage
0x1a256c590 <+588>: ldr x11, [sp, #0x18]
取出 dic->storage.state
0x1a256c594 <+592>: ldr x9, [x11, x8]
下面的几个指令等价于 dic->storage.state.used += 1;
used 宽度是 24位，右侧有32位（mutbits 和 copyKeys）
先对 used+1 操作
0x1a256c598 <+596>: mov x10, #0x100000000
0x1a256c59c <+600>: add x10, x9, x10
逻辑右移，移除 （mutbits 和 copyKeys）
0x1a256c5a0 <+604>: lsr x10, x10, #32
位域操作，将 x10 持有的 24 位的 used 更新 x9
0x1a256c5a4 <+608>: bfi x9, x10, #32, #25
将新的 state 放回 dic->storage.state
0x1a256c5a8 <+612>: str x9, [x11, x8]
; x22 等于 桶的数量
; x20 是 count
# 取出 values
0x1a256c5ac <+616>: ldr x8, [sp, #0x30]
# 取出与 key 配对的 value
0x1a256c5b0 <+620>: ldr x0, [x8, x23, lsl #3]
# 再次取出 buffer 对应的 values
0x1a256c5b4 <+624>: ldr x8, [sp, #0x48]
# 把 value 存进去
0x1a256c5b8 <+628>: str x0, [x8, x19, lsl #3]
# 取出参数**可变字典Option**
0x1a256c5bc <+632>: ldr x8, [sp, #0x40]
看看是否有 **NSEnumeration屏蔽对Value进行Retain**，如果有，则跳过对 value 的 objc_retain 操作
0x1a256c5c0 <+636>: tbnz w8, #0x2, 0x1a256c5d0 ; <+652>
0x1a256c5c4 <+640>: cmp x0, #0x1 ; =0x1
0x1a256c5c8 <+644>: b.lt 0x1a256c5d0 ; <+652>
对 value 进行 objc_retain 操作
0x1a256c5cc <+648>: bl 0x1a2153e58
# x23 代表第几个 key，先 +1
0x1a256c5d0 <+652>: add x23, x23, #0x1 ; =0x1
后与 x20 count 比较
0x1a256c5d4 <+656>: cmp x23, x20
不等则继续遍历
0x1a256c5d8 <+660>: b.ne 0x1a256c480 ; <+316>
# 动态获取 cow 的偏移量
0x1a256c5dc <+664>: adrp x8, 367773
0x1a256c5e0 <+668>: ldrsw x8, [x8, #0xdbc]
(lldb) image lookup -a ((($pc>>12)+367773)<<12)+0xdbc
Address: CoreFoundation[0x00000001da169dbc] (CoreFoundation.__DATA.__objc_ivar + 1196)
Summary: CoreFoundation`__NSDictionaryM.cow
# 取出字典；+152 曾经将 dic 临时存储到栈上
0x1a256c5e4 <+672>: ldr x0, [sp, #0x10]
# 等价于 dic->cow = NULL
0x1a256c5e8 <+676>: add x8, x0, x8
0x1a256c5ec <+680>: stlr xzr, [x8]
恢复栈
0x1a256c5f0 <+684>: ldp x29, x30, [sp, #0xa0]
0x1a256c5f4 <+688>: ldp x20, x19, [sp, #0x90]
0x1a256c5f8 <+692>: ldp x22, x21, [sp, #0x80]
0x1a256c5fc <+696>: ldp x24, x23, [sp, #0x70]
0x1a256c600 <+700>: ldp x26, x25, [sp, #0x60]
0x1a256c604 <+704>: ldp x28, x27, [sp, #0x50]
0x1a256c608 <+708>: add sp, sp, #0xb0 ; =0xb0
0x1a256c60c <+712>: ret
注意：-[NSSet intersectsOrderedSet:].cold.1 等价于调用 objc_opt_self
image
objc_autorelease
objc_autorelease 内部的逻辑比较简单：
- 如果
nil，直接返回 - 如果是
TaggedPointer，直接返回 - 如果类有自定义的
retain或者release方法，则通过调用[objc autorelease] - 判断 x30 寄存器地址指向的指令是否等于
0xaa1d03fdarm64中，fd 03 1d aa等价于mov fp, fp - 如果等于，则将1存储到 tls
- 如果不等，则转发到
objc_object::rootAutorelease2()进行下一步处理
libobjc.A.dylib`objc_autorelease:
0x1b6894d20 <+0>: cmp x0, #0x1 ; =0x1
0x1b6894d24 <+4>: b.lt 0x1b6894d5c ; <+60>
0x1b6894d28 <+8>: ldr x8, [x0]
0x1b6894d2c <+12>: and x8, x8, #0xffffffff8
0x1b6894d30 <+16>: ldrb w8, [x8, #0x20]
0x1b6894d34 <+20>: tbz w8, #0x2, 0x1b6894d64 ; <+68>
0x1b6894d38 <+24>: ldr w8, [x30]
0x1b6894d3c <+28>: mov w9, #0x3fd
0x1b6894d40 <+32>: movk w9, #0xaa1d, lsl #16
0x1b6894d44 <+36>: cmp w8, w9
0x1b6894d48 <+40>: b.ne 0x1b6894d60 ; <+64>
0x1b6894d4c <+44>: mrs x8, TPIDRRO_EL0
0x1b6894d50 <+48>: and x8, x8, #0xfffffffffffffff8
0x1b6894d54 <+52>: mov w9, #0x1
0x1b6894d58 <+56>: str x9, [x8, #0x160]
0x1b6894d5c <+60>: ret
0x1b6894d60 <+64>: b 0x1b6893a50 ; objc_object::rootAutorelease2()
0x1b6894d64 <+68>: adrp x8, 226945
0x1b6894d68 <+72>: add x1, x8, #0xaba ; =0xaba
0x1b6894d6c <+76>: b 0x1b6873460 ; objc_msgSend
总结
本文分享了很多通过 lldb 指令分析汇编和内存的小技巧，并对可变字典创建过程进行了逐步的分析，为下一篇分析 cow 机制打下了基础
本文参与 腾讯云自媒体分享计划，分享自微信公众号。
原始发表：2021-04-29，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读
目录