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

[toc]

前言

今天的文章结构会比上篇清晰很多，请放心食用。

cow

cow 是 copy on write 的简写，是一种通过延迟复制时机节省时间和空间的编程技术

本文会通过对 NSMutableDictionary 的底层分析，来分享苹果官方对 cow 的设计思路

以 NSMutableDictionary 为例，cow 机制对时间复杂度和空间复杂度有着非常明显的优化：

	不采用 cow 机制	采用 cow 机制
复制字典的空间复杂度	为字典的所有键值对申请内存	copy 或者 mutalbeCopy 均不需要，第一次修改才会触发申请
复制字典的时间复杂度	需要对所有键值对进行 retain 操作	copy 或者 mutalbeCopy 均不需要，第一次修改才会触发 retain
销毁复制字典的成本	需要对所有键值对进行 release 操作	没有修改过的可变字典不需要对键值对 release 操作

可变字典结构

首先，我们先看看可变字典的内存结构：

注意：此时的 cow 是 NULL

对应到 Obj-C 代码后如下：

 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


struct __cow_state_t {
    unsigned int cow_lock;
    unsigned int copyCount:16;
    unsigned int mutableCopyCount:16;
};

struct KKDic_t {
    __strong Class isa;
    struct {
        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;
};

可变字典的内存分 4 个部分：

Class isa ：代表类实例的类型
id *buffer：指向可变字典保存的键值对
struct state：代表可变字典的各种状态
1. used 代表已经使用的空间大小，与开发者常用的 count 属性对应
2. mutbits 代表对字典变更的次数。初始化时是 1，增删会加 1
3. szidx 通过搭配常量数组 __NSDictionarySizes ，获取字典的容量
4. copyeKeys: 代表需要复制 key
struct __cow_state_t *cow：会指向一个结构体 __cow_state_t
1. cow_lock：多线程对单个可变字典进行复制时，可能存在崩溃或者内存泄露，所以需要锁进行多线程保护
2. copyCount:16：代表对可变字典 copy的次数
3. mutableCopyCount:16：代表对可变字典进行 mutableCopy 的次数

NSMutableDictionary 的 cow 机制浅析

NSMutableDictionary 通过引入一个指向结构体：__cow_state_t 的指针实现了 cow 机制

当复制发生时，__cow_state_t 的引用计数会加 1，并且多个字典会共享一份 __cow_state_t 和 buffer。从而实现常量时间的复制成本

以下面的代码为例：

1

NSMutableDictionary *dicMutableCopy = [mutableDic mutableCopy];

等效的代码非常简单：

1
2
3
4
5
6
7
8


// 省略了 加锁逻辑 和 懒加载 cow

dic0->cow->mutableCopyCount += 1;

struct KKDic_t *dic2 = malloc(sizeof(struct KKDic_t));
dic2->isa = dic0->isa;
dic2->storage = dic0->storage;
dic2->cow = dic0->cow;

通过 dic0->cow->mutableCopyCount += 1;，系统可以避免对申请新的空间持有键值对，并且避免对字典持有的每个键值对进行 retain 操作

[__NSDictionaryM mutableCopy]

[mutableDic mutableCopy]代码执行时，会被转发到 -[__NSDictionaryM mutableCopy] 处执行可变字典复制逻辑。

-[__NSDictionaryM mutableCopy] 会依次完成以下任务：

序章
旧字典懒加载创建 cow
创建新的字典
复制 cow

序章

注意：部分指令只有在开启 线程消毒剂 等场景才会执行

 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


CoreFoundation`-[__NSDictionaryM mutableCopy]:

    1、序章：
    0x1a256c7cc <+0>:   stp    x22, x21, [sp, #-0x30]!
    0x1a256c7d0 <+4>:   stp    x20, x19, [sp, #0x10]
    0x1a256c7d4 <+8>:   stp    x29, x30, [sp, #0x20]

    2、在栈上申请一块空间 0x20，可以存在4个指针
    0x1a256c7d8 <+12>:  add    x29, sp, #0x20            ; =0x20

    3、临时保存 self 到 x19
    0x1a256c7dc <+16>:  mov    x19, x0

    4.1、读取 __cf_tsanReadFunction 指定位置的值，如果非 0，调到 +180 进行处理
    0x1a256c7e0 <+20>:  adrp   x8, 367779
    0x1a256c7e4 <+24>:  add    x8, x8, #0x408            ; =0x408
    (lldb) image lookup -a $x8
      Address: CoreFoundation[0x00000001da16f408] (CoreFoundation.__DATA.__common + 56)
      Summary: CoreFoundation`__cf_tsanReadFunction
    0x1a256c7e8 <+28>:  ldr    x8, [x8]
    0x1a256c7ec <+32>:  cbnz   x8, 0x1a256c880           ; <+180>

    4.2、开始调用 线程消毒剂
    0x1a256c880 <+180>: adrp   x9, 367779
    0x1a256c884 <+184>: add    x9, x9, #0x440            ; =0x440
    (lldb) image lookup -a $x9
      Address: CoreFoundation[0x00000001da16f440] (CoreFoundation.__DATA.__common + 112)
      Summary: CoreFoundation`__CFTSANTagMutableDictionary

    4.3、组装参数，x0 是 self，x1 是 lr 寄存器，x2 是 __CFTSANTagMutableDictionary 保存的内容
    (lldb) p/x $lr
    (unsigned long) $17 = 0x0000000100779a74
    (lldb) p/x $x30
    (unsigned long) $19 = 0x0000000100779a74
    (lldb)
    0x1a256c888 <+188>: ldr    x2, [x9]
    0x1a256c88c <+192>: mov    x0, x19
    0x1a256c890 <+196>: mov    x1, x30
    4.4、调用 4.1 读取的函数
    0x1a256c894 <+200>: blr    x8
    4.5、返回 +36 继续执行
    0x1a256c898 <+204>: b      0x1a256c7f0               ; <+36>

iOS 模拟器开启线程消毒剂

iOS 模拟器开启线程消毒剂后的堆栈如下：

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


(lldb) bt
* thread #1, queue = 'com.apple.main-thread', stop reason = instruction step into
  * frame #0: 0x0000000109936160 libclang_rt.tsan_iossim_dynamic.dylib`__tsan_external_read
    frame #1: 0x00007fff20490381 CoreFoundation`-[__NSDictionaryM mutableCopy] + 164


    frame #4: 0x00007fff201804e3 libobjc.A.dylib`load_images + 1442
    frame #5: 0x0000000109865e54 dyld_sim`dyld::notifySingle(dyld_image_states, ImageLoader const*, ImageLoader::InitializerTimingList*) + 425
    frame #6: 0x0000000109874887 dyld_sim`ImageLoader::recursiveInitialization(ImageLoader::LinkContext const&, unsigned int, char const*, ImageLoader::InitializerTimingList&, ImageLoader::UninitedUpwards&) + 437
    frame #7: 0x0000000109872bb0 dyld_sim`ImageLoader::processInitializers(ImageLoader::LinkContext const&, unsigned int, ImageLoader::InitializerTimingList&, ImageLoader::UninitedUpwards&) + 188
    frame #8: 0x0000000109872c50 dyld_sim`ImageLoader::runInitializers(ImageLoader::LinkContext const&, ImageLoader::InitializerTimingList&) + 82
    frame #9: 0x00000001098662a9 dyld_sim`dyld::initializeMainExecutable() + 199
    frame #10: 0x000000010986ad50 dyld_sim`dyld::_main(macho_header const*, unsigned long, int, char const**, char const**, char const**, unsigned long*) + 4431
    frame #11: 0x00000001098651c7 dyld_sim`start_sim + 122
    frame #12: 0x00000001176cd85c dyld`dyld::useSimulatorDyld(int, macho_header const*, char const*, int, char const**, char const**, char const**, unsigned long*, unsigned long*) + 2308
    frame #13: 0x00000001176cb4f4 dyld`dyld::_main(macho_header const*, unsigned long, int, char const**, char const**, char const**, unsigned long*) + 837
    frame #14: 0x00000001176c6227 dyld`dyldbootstrap::start(dyld3::MachOLoaded const*, int, char const**, dyld3::MachOLoaded const*, unsigned long*) + 453
    frame #15: 0x00000001176c6025 dyld`_dyld_start + 37

对应汇编指令：

1
2
3
4
5
6
7
8


libclang_rt.tsan_iossim_dynamic.dylib`__tsan_external_read:
    0x10c1ff160 <+0>:  push   rbp
    0x10c1ff161 <+1>:  mov    rbp, rsp
    0x10c1ff164 <+4>:  lea    rcx, [rip + 0x15]         ; __tsan::MemoryRead(__tsan::ThreadState*, unsigned long, unsigned long, int)
    0x10c1ff16b <+11>: pop    rbp
    0x10c1ff16c <+12>: jmp    0x10c1fece0               ; __tsan::ExternalAccess(void*, void*, void*, void (*)(__tsan::ThreadState*, unsigned long, unsigned long, int))
    0x10c1ff171 <+17>: nop    word ptr cs:[rax + rax]
    0x10c1ff17b <+27>: nop    dword ptr [rax + rax]

1、旧字典通过懒加载方式创建 cow

第一次复制时，会通过调用函数 _cow_create 进行懒加载 cow

 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


5.1、动态读取 __NSDictionaryM.cow 的偏移量
0x1a256c7f0 <+36>:  adrp   x21, 367773
0x1a256c7f4 <+40>:  ldrsw  x8, [x21, #0xdbc]
(lldb) image lookup -a ((($pc>>12)+367773)<<12)+0xdbc
  Address: CoreFoundation[0x00000001da169dbc] (CoreFoundation.__DATA.__objc_ivar + 1196)
  Summary: CoreFoundation`__NSDictionaryM.cow

5.2、x19 存储 self，x20 指向实例的  __NSDictionaryM.cow
0x1a256c7f8 <+44>:  add    x20, x19, x8

5.3、读取  旧字典 cow 的值
0x1a256c7fc <+48>:  ldar   x8, [x20]
  ldar 是 单向屏障指令。与 cpu 的指令重新排序有关系

5.3、判空操作，第一次复制是0
0x1a256c800 <+52>:  cbnz   x8, 0x1a256c82c           ; <+96>
5.4、如果是空，准备参数，进行第一次的创建 _cow_create(self,1)
0x1a256c804 <+56>:  mov    x0, x19
0x1a256c808 <+60>:  mov    w1, #0x1
0x1a256c80c <+64>:  bl     0x1a245aed8               ; _cow_create

5.5、开始尝试更新 旧字典的 cow
5.5.1、独占获取 x20 的值
0x1a256c810 <+68>:  ldaxr  x8, [x20]

5.5.2、判断是否等于0，如果不等，可能是其它线程已经进行了赋值，需要进入 5.6 将本线程刚创建的 cow 销毁
0x1a256c814 <+72>:  cbnz   x8, 0x1a256c824           ; <+88>

5.5.3、存储数据。注意，这个位置不能加断点，会导致死循环
0x1a256c818 <+76>:  stlxr  w8, x0, [x20]
Store-Release Exclusive Register.
  w8 保存结果：
  0 If the operation updates memory.
  1 If the operation fails to update memory.

5.5.4、判断存储结果，如果存储失败（多线程或者其它原因），返回 5.5.1 重试
0x1a256c81c <+80>:  cbnz   w8, 0x1a256c810           ; <+68>

0x1a256c820 <+84>:  b      0x1a256c82c               ; <+96>

5.6.1、多线程冲突后，开始清除独占数据
0x1a256c824 <+88>:  clrex

5.6.2、多线程冲突后，调用函数 free，将 cow 进行释放
0x1a256c828 <+92>:  bl     0x1a2585b18               ; symbol stub for: -[NSDictionary initWithObjects:forKeys:].cold.1

屏障 (Barriers)

为了保证多线程安全，上一段汇编指令使用了屏障指令

普通的内存屏障是双向的，可以控制内存屏障之前的某些存储操作在内存屏障之前完成，并且内存屏障之后的某些存储操作要在内存屏障之后才能开始。

但是 ARMv8 架构新增的单向屏障 (One-way barriers) Load-Acquire（LDAR 指令）和 Store-Release（STLR 指令）却只限定了单个方向的

Load-Acquire：指令之后的所有加载和存储操作一定不会被重排序到这条指令之前，但是没有要求这条指令之前的所有加载和存储操作一定不能被重排序到这条指令之后。所以，这条指令是单向屏障，只挡住了后面出现的所有内存操作指令，但是没有挡住这条指令之前的所有内存操作指令。

Store-Release：指令之前的所有加载和存储才做一定不会被重排序到这条指令之后，但是没有要求这条指令之后的所有加载和存储操作一定不能被重排序到这条指令之前。所以，这条指令也是单向屏障，只挡住了前面出现的所有内存操作指令，但是没有挡住这条指令之后的所有内存操作指令。

相关知识：iOS 汇编教程（六）CPU 指令重排与内存屏障

旧字典创建 cow (_cow_create)

注意：创建失败会通过函数 _cow_allocation_failure 抛出异常

 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


CoreFoundation`_cow_create:
    0x1a245aed8 <+0>:  stp    x20, x19, [sp, #-0x20]!
    0x1a245aedc <+4>:  stp    x29, x30, [sp, #0x10]
    0x1a245aee0 <+8>:  add    x29, sp, #0x10            ; =0x10

    先在 x19 临时保存参数 x1
    0x1a245aee4 <+12>: mov    x19, x1

    1 通过 calloc 申请一块空间，大小是 8*1
    0x1a245aee8 <+16>: mov    w0, #0x8
    0x1a245aeec <+20>: mov    w1, #0x1
    0x1a245aef0 <+24>: bl     0x1a2585770               ; symbol stub for: -[NSArray indexesOfObjectsWithOptions:passingTest:].cold.1
    frame #0: 0x00000001b18a8388 libsystem_malloc.dylib`calloc
    frame #1: 0x00000001a245aef4 CoreFoundation`_cow_create + 28
    frame #2: 0x00000001a256c810 CoreFoundation`-[__NSDictionaryM mutableCopy] + 68

    1.2 如果申请失败，进入 _cow_allocation_failure 抛出异常
    0x1a245aef4 <+28>: cbz    x0, 0x1a245af18           ; <+64>

    2.1 申请成功后，判断 传入的参数 是否等于1
    0x1a245aef8 <+32>: cmp    w19, #0x1                 ; =0x1

    2.1 根据是否等于 1 更新 新申请的空间
    0x1a245aefc <+36>: cset   w8, eq
    0x1a245af00 <+40>: cset   w9, ne
    0x1a245af04 <+44>: strh   w9, [x0, #0x4]
    0x1a245af08 <+48>: strh   w8, [x0, #0x6]
    cow 变成下面的样子：w8 代表当前 buffer 只有1个持有者，w9 等于0，代表 还没有进行过 mutableCopy，
    (lldb) p/x $w8
    (unsigned int) $0 = 0x00000001
    (lldb) p/x $w9
    (unsigned int) $1 = 0x00000000
    (lldb) p/x $x0
    (unsigned long) $2 = 0x0000000104c0c2a0
    (lldb) x/a 0x0000000104c0c2a0
    0x104c0c2a0: 0x0001000000000000
    (lldb)

    3. 恢复栈
    0x1a245af0c <+52>: ldp    x29, x30, [sp, #0x10]
    0x1a245af10 <+56>: ldp    x20, x19, [sp], #0x20
    0x1a245af14 <+60>: ret

    1.3 获取一个 c 风格字符串
    0x1a245af18 <+64>: adrp   x0, 333999
    0x1a245af1c <+68>: add    x0, x0, #0xb50            ; =0xb50
    (lldb) image lookup -a $x0
      Address: CoreFoundation[0x00000001d1c69b50] (CoreFoundation.__DATA_CONST.__cfstring + 9728)
      Summary: @"Unable to create CoW control block"
    1.4 转到 _cow_allocation_failure 抛出异常
    0x1a245af20 <+72>: bl     0x1a245af24               ; _cow_allocation_failure

_cow_allocation_failure

更新栈后，转到函数 _cow_failure 进一步处理

1
2
3
4


CoreFoundation`_cow_allocation_failure:
0x1a245af24 <+0>: stp    x29, x30, [sp, #-0x10]!
0x1a245af28 <+4>: mov    x29, sp
0x1a245af2c <+8>: bl     0x1a25780ec               ; _cow_failure

_cow_failure

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


CoreFoundation`_cow_failure:
    0x1a25780ec <+0>:  stp    x29, x30, [sp, #-0x10]!
    0x1a25780f0 <+4>:  mov    x29, sp

    1. 生成一个字符串，编码是 kCFStringEncodingASCII = 0x0600
    0x1a25780f4 <+8>:  mov    w1, #0x600
    0x1a25780f8 <+12>: bl     0x1a24b4eb8               ; CFStringGetCStringPtr

    2. 存到特定位置
    0x1a25780fc <+16>: adrp   x8, 367766
    0x1a2578100 <+20>: str    x0, [x8, #0xaa0]

    (lldb) p/x ((($pc>>12)+367766)<<12)+0xaa0
    (unsigned long) $1 = 0x00000001fc20eaa0
    (lldb) image lookup -a  ((($pc>>12)+367766)<<12)+0xaa0
        Address: CoreFoundation[0x00000001da16eaa0] (CoreFoundation.__DATA.__crash_info + 8)
        Summary: CoreFoundation`gCRAnnotations + 8
    (lldb)

    3. 触发崩溃
    0x1a2578104 <+24>: brk    #0x1

2、创建新的字典

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


6、开始创建新的可变字典
6.1、获取 __NSDictionaryM
0x1a256c82c <+96>:  adrp   x0, 366160
0x1a256c830 <+100>: add    x0, x0, #0x268            ; =0x268

6.1、调用 objc_opt_self(__NSDictionaryM)
0x1a256c834 <+104>: bl     0x1a25860a0               ; symbol stub for: -[NSSet intersectsOrderedSet:].cold.1

6.2、调用 __CFAllocateObject 创建 __NSDictionaryM 对应的实例
0x1a256c838 <+108>: mov    x1, #0x0
0x1a256c83c <+112>: bl     0x1a251b1d4               ; __CFAllocateObject

6.3、暂存新的实例到 x20
0x1a256c840 <+116>: mov    x20, x0

注意:新的字典各项属性都是空值

3、旧字典的 cow 进行复制到新字典

通过函数 _cow_copy 和函数 cow_copy_instance 搭配将旧字典的 cow 进行复制，并填充给新字典

 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


6.4、再次获取 __NSDictionaryM.cow 的偏移量
0x1a256c844 <+120>: ldrsw  x8, [x21, #0xdbc]
(lldb) image lookup -a $x21+0xdbc
  Address: CoreFoundation[0x00000001da169dbc] (CoreFoundation.__DATA.__objc_ivar + 1196)
  Summary: CoreFoundation`__NSDictionaryM.cow

6.5、让 x8 保存执行 旧字典 的 cow
0x1a256c848 <+124>: add    x8, x19, x8

6.5、读取 cow 的值
0x1a256c84c <+128>: ldar   x2, [x8]

6.6、获取函数 cow_copy_instance 指针
0x1a256c850 <+132>: adrp   x3, 333723
0x1a256c854 <+136>: add    x3, x3, #0x1e8            ; =0x1e8
(lldb) x/a $x3
0x1f3d071e8: 0x00000001a256ce44 CoreFoundation`cow_copy_instance

7.0、通过 函数 _cow_copy 进行复制，参数：旧字典，常量1，cow, 函数 cow_copy_instance 指针，新字典，常量 1
0x1a256c858 <+140>: mov    x0, x19
0x1a256c85c <+144>: mov    w1, #0x1
0x1a256c860 <+148>: mov    x4, x20
0x1a256c864 <+152>: mov    w5, #0x1
0x1a256c868 <+156>: bl     0x1a245af30               ; _cow_copy

8.0、复制结束，返回新的字典
0x1a256c86c <+160>: mov    x0, x20

9.0、恢复栈
0x1a256c870 <+164>: ldp    x29, x30, [sp, #0x20]
0x1a256c874 <+168>: ldp    x20, x19, [sp, #0x10]
0x1a256c878 <+172>: ldp    x22, x21, [sp], #0x30
0x1a256c87c <+176>: ret

_cow_copy

_cow_copy 函数通过 cow_copy_instance 复制 cow，并将 cow 的计数+1

参数列表：

旧字典
是否属于谢谢
指向旧字典的 cow
函数 cow_copy_instance 指针
新字典
1 代表是 mutableCopy 复制；0 代表 copy 复制

序章

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


CoreFoundation`_cow_copy:
    0x1a245af30 <+0>:   stp    x24, x23, [sp, #-0x40]!
    0x1a245af34 <+4>:   stp    x22, x21, [sp, #0x10]
    0x1a245af38 <+8>:   stp    x20, x19, [sp, #0x20]
    0x1a245af3c <+12>:  stp    x29, x30, [sp, #0x30]

    1. 保存参数
    0x1a245af40 <+16>:  add    x29, sp, #0x30            ; =0x30
    参数5 : 1 代表 mutableCopy; copy 传入的值是 0
    0x1a245af44 <+20>:  mov    x22, x5
    新字典
    0x1a245af48 <+24>:  mov    x20, x4
    函数 cow_copy_instance 指针
    0x1a245af4c <+28>:  mov    x21, x3
    cow
    0x1a245af50 <+32>:  mov    x19, x2
    常量1
    0x1a245af54 <+36>:  mov    x23, x1
    旧字典
    0x1a245af58 <+40>:  mov    x24, x0

加锁

存在多线程复制的可能性，需要加锁

1
2
3


2. 存在多线程复制的可能性，需要加锁
0x1a245af5c <+44>:  mov    x0, x2
0x1a245af60 <+48>:  bl     0x1a258622c               ; symbol stub for: -[__NSFrozenSetM countByEnumeratingWithState:objects:count:].cold.2

加锁相关指令（不同的 cpu 架构，加锁指令会存在一些差异）：

1
2
3
4


libsystem_platform.dylib`os_unfair_recursive_lock_trylock$VARIANT$armv81:
0x1eac34454 <+0>: adrp   x16, 69501
0x1eac34458 <+4>: ldr    x16, [x16, #0x370]
0x1eac3445c <+8>: br     x16

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


libsystem_platform.dylib`os_unfair_lock_lock$VARIANT$mp:
0x1eac307c4 <+0>:  mrs    x8, TPIDRRO_EL0
0x1eac307c8 <+4>:  and    x8, x8, #0xfffffffffffffff8
0x1eac307cc <+8>:  ldr    w2, [x8, #0x18]
0x1eac307d0 <+12>: ldaxr  w8, [x0]
0x1eac307d4 <+16>: cbnz   w8, 0x1eac307e4           ; <+32>
0x1eac307d8 <+20>: stxr   w8, w2, [x0]
(lldb) p/x $w2
(unsigned int) $5 = 0x00000303

(lldb) x/a 0x0000000104c0c2a0
0x104c0c2a0: 0x0001000000000303
(lldb)
0x1eac307dc <+24>: cbnz   w8, 0x1eac307d0           ; <+12>
0x1eac307e0 <+28>: ret
0x1eac307e4 <+32>: clrex
0x1eac307e8 <+36>: mov    w1, #0x0
0x1eac307ec <+40>: b      0x1eac307f0               ; _os_unfair_lock_lock_slow

mutableCopy 逻辑

如果是是通过 [dic mutableCopy]调用该函数，需要将 mutableCopyCount 加一，然后通过函数cow_copy_instance 进行复制

 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


3. 第 1 步曾经将 x5 保存到 x22，所以，w22 是否等于1决定走 mutableCopy 逻辑还是 copy 逻辑
0x1a245af64 <+52>:  cmp    w22, #0x1                 ; =0x1
0x1a245af68 <+56>:  b.ne   0x1a245af9c               ; <+108>

4. 开始 mutableCopy 逻辑
4.1 x19 是 cow
0x1a245af6c <+60>:  ldrh   w8, [x19, #0x6]

4.1.2 如果引用计数超过限制，进入 超限处理逻辑
0x1a245af70 <+64>:  mov    w9, #0xffff
0x1a245af74 <+68>:  cmp    w8, w9
0x1a245af78 <+72>:  b.eq   0x1a245afd0               ; <+160>

4.2 对 mutableCopyCount+1，然后存回去
0x1a245af7c <+76>:  add    w8, w8, #0x1              ; =0x1
0x1a245af80 <+80>:  strh   w8, [x19, #0x6]

5.1 获取 函数 cow_copy_instance 指针
0x1a245af84 <+84>:  ldr    x8, [x21]
(lldb) image lookup -a $x21
  Address: CoreFoundation[0x00000001d1c671e8] (CoreFoundation.__DATA_CONST.__const + 1939624)
  Summary: CoreFoundation`__NSDictionary_cowCallbacks
(lldb) image lookup -a $x8
    Address: CoreFoundation[0x00000001804cce44] (CoreFoundation.__TEXT.__text + 1535540)
    Summary: CoreFoundation`cow_copy_instance

5.2 准备参数并调用 cow_copy_instance(x24,x23,x20,参数5)
0x1a245af88 <+88>:  mov    x0, x24
0x1a245af8c <+92>:  mov    x1, x23
0x1a245af90 <+96>:  mov    x2, x20
0x1a245af94 <+100>: mov    w3, #0x1
0x1a245af98 <+104>: b      0x1a245afc8               ; <+152>
结合第 1 步保存的参数，我们可以推理到等效的 c 代码：
cow_copy_instance(旧字典,常量1,新字典,参数5)

copy 逻辑

如果是是通过 [dic copy]调用该函数，需要将 copyCount 加一，然后通过函数cow_copy_instance 进行复制

 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


6 开始 copy 处理逻辑
6.1 取出 copyCount
0x1a245af9c <+108>: ldrh   w8, [x19, #0x4]

6.2 是否等于最大值
0x1a245afa0 <+112>: mov    w9, #0xffff
0x1a245afa4 <+116>: cmp    w8, w9

6.3 如果等于，则进入 +160 逻辑
0x1a245afa8 <+120>: b.eq   0x1a245afd0               ; <+160>

6.4 不等于时，走正常的+1逻辑
0x1a245afac <+124>: add    w8, w8, #0x1              ; =0x1

6.5 将加1后的值存回 copyCount
0x1a245afb0 <+128>: strh   w8, [x19, #0x4]

6.6 准备参数并调用 cow_copy_instance(x24,x23,x20,x22)
0x1a245afb4 <+132>: ldr    x8, [x21]
0x1a245afb8 <+136>: mov    x0, x24
0x1a245afbc <+140>: mov    x1, x23
0x1a245afc0 <+144>: mov    x2, x20
0x1a245afc4 <+148>: mov    x3, x22
    结合第 1 步保存的参数，我们可以推理到等效的 c 代码：
    cow_copy_instance(旧字典,常量1,新字典,参数5)

0x1a245afc8 <+152>: blr    x8
0x1a245afcc <+156>: b      0x1a245b008               ; <+216>

cow_copy_instance

函数 cow_copy_instance 接收的参数列表如下：

旧字典
旧字典是否属于 __NSDictionaryM
新字典
新字典是否属于 __NSDictionaryM

 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


CoreFoundation`cow_copy_instance:
    1.1、获取 __NSFrozenDictionaryM.cow
    0x1a256ce44 <+0>:  adrp   x8, 367773
    0x1a256ce48 <+4>:  add    x8, x8, #0xdc4            ; =0xdc4
    (lldb) image lookup -a $x8
      Address: CoreFoundation[0x00000001da169dc4] (CoreFoundation.__DATA.__objc_ivar + 1204)
      Summary: CoreFoundation`__NSFrozenDictionaryM.cow

    1.2、获取 __NSDictionaryM.cow
    0x1a256ce4c <+8>:  adrp   x9, 367773
    0x1a256ce50 <+12>: add    x9, x9, #0xdbc            ; =0xdbc
    (lldb) image lookup -a $x9
      Address: CoreFoundation[0x00000001da169dbc] (CoreFoundation.__DATA.__objc_ivar + 1196)
      Summary: CoreFoundation`__NSDictionaryM.cow

    1.3、判断第1个参数是否等于1，如果是，则旧字典当做 __NSDictionaryM 处理
    0x1a256ce54 <+16>: cmp    w1, #0x1                  ; =0x1
    0x1a256ce58 <+20>: csel   x10, x9, x8, eq

    2.1、获取 __NSFrozenDictionaryM.storage
    0x1a256ce5c <+24>: adrp   x11, 367773
    0x1a256ce60 <+28>: add    x11, x11, #0xdc0          ; =0xdc0
    (lldb) image lookup -a $x11
      Address: CoreFoundation[0x00000001da169dc0] (CoreFoundation.__DATA.__objc_ivar + 1200)
      Summary: CoreFoundation`__NSFrozenDictionaryM.storage

    2.2、获取 __NSDictionaryM.storage
    0x1a256ce64 <+32>: adrp   x12, 367773
    0x1a256ce68 <+36>: add    x12, x12, #0xdb8          ; =0xdb8
    (lldb) image lookup -a $x12
        Address: CoreFoundation[0x00000001da169db8] (CoreFoundation.__DATA.__objc_ivar + 1192)
        Summary: CoreFoundation`__NSDictionaryM.storage
    (lldb)

    2.3、判断第1个参数是否等于1，如果是，则旧字典当做 __NSDictionaryM 处理
    0x1a256ce6c <+40>: csel   x13, x12, x11, eq

    1.4、取出 __NSDictionaryM.cow 的值
    0x1a256ce70 <+44>: ldrsw  x10, [x10]

    1.5、x10  是指针，指向旧字典 的 cow
    0x1a256ce74 <+48>: add    x10, x0, x10

    1.6、取出 旧的 cow
    0x1a256ce78 <+52>: ldar   x10, [x10]

    2.4、取出 __NSDictionaryM.storage 的值
    0x1a256ce7c <+56>: ldrsw  x13, [x13]

    3.1、判断第3个参数是否等于1
    0x1a256ce80 <+60>: cmp    w3, #0x1                  ; =0x1

    3.2、如果是，则新字典当做 __NSDictionaryM.cow 处理
    0x1a256ce84 <+64>: csel   x8, x9, x8, eq

    3.3 如果是，则新字典当做 __NSDictionaryM.storage 处理
    0x1a256ce88 <+68>: csel   x9, x12, x11, eq

    3.4 x8是指针，指向 新字典 的 cow
    主要，因为可变字典的 cow 是个指向 __cow_state_t 的指针，所以，新旧两个字典会同时执行一份 __cow_state_t 结构体
    0x1a256ce8c <+72>: ldrsw  x8, [x8]
    0x1a256ce90 <+76>: add    x8, x2, x8

    3.5 将旧的 cow 复制给新字典的 cow
    0x1a256ce94 <+80>: stlr   x10, [x8]

    3.6 将旧字典 storage 整个结构体取出来
    0x1a256ce98 <+84>: ldrsw  x8, [x9]
    0x1a256ce9c <+88>: ldr    q0, [x0, x13]
    (lldb) x/4a $x0
    0x101b05e50: 0x000021a1fbbbc269
    0x101b05e58: 0x0000000101b05e80
    0x101b05e60: 0x0800000680000001
    0x101b05e68: 0x0000000101a077c0
    (lldb) p/x $q0
    (unsigned char __attribute__((ext_vector_type(16)))) $11 = (0x01b05e80, 0x00000001, 0x80000001, 0x08000006)

    3.7 再复制给新的字典
    0x1a256cea0 <+92>: str    q0, [x2, x8]
    0x1a256cea4 <+96>: ret

复制完成后的内存情况：

恢复栈&unlock

1
2
3
4
5
6
7
8


5.3 恢复堆栈，并 unlock
0x1a245b008 <+216>: mov    x0, x19
0x1a245b00c <+220>: ldp    x29, x30, [sp, #0x30]
0x1a245b010 <+224>: ldp    x20, x19, [sp, #0x20]
0x1a245b014 <+228>: ldp    x22, x21, [sp, #0x10]
0x1a245b018 <+232>: ldp    x24, x23, [sp], #0x40
调用 unlock
0x1a245b01c <+236>: b      0x1a2153f3c，

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11


libsystem_platform.dylib`os_unfair_lock_unlock$VARIANT$mp:
      0x1eac309b8 <+0>:  mrs    x8, TPIDRRO_EL0
      0x1eac309bc <+4>:  and    x8, x8, #0xfffffffffffffff8
      0x1eac309c0 <+8>:  ldr    w1, [x8, #0x18]
      0x1eac309c4 <+12>: ldxr   w2, [x0]
      0x1eac309c8 <+16>: stlxr  w8, wzr, [x0]
      0x1eac309cc <+20>: cbnz   w8, 0x1eac309c4           ; <+12>
      0x1eac309d0 <+24>: cmp    w2, w1
      0x1eac309d4 <+28>: b.ne   0x1eac309dc               ; <+36>
      0x1eac309d8 <+32>: ret
      0x1eac309dc <+36>: b      0x1eac309e0               ; _os_unfair_lock_unlock_slow

引用计数超限处理

根据设计，可变字典内部只有两个 16 位分别保存不可变字典和可变字典的引用计数

1
2
3
4
5


struct __cow_state_t {
    unsigned int cow_lock;
    unsigned int copyCount:16;
    unsigned int mutableCopyCount:16;
};

所以，需要在复制次数超过限制时，进行一次特殊处理

 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


7.1 如果超过了阀值，则开始进行 cow_copy_instance 逻辑
0x1a245afd0 <+160>: ldr    x8, [x21]
    (lldb) image lookup -a $x8
    Address: CoreFoundation[0x00000001804cce44] (CoreFoundation.__TEXT.__text + 1535540)
    Summary: CoreFoundation`cow_copy_instance

7.2 准备参数并调用 _copy_instance(x24,x23,x20,x22)
0x1a245afd4 <+164>: mov    x0, x24
0x1a245afd8 <+168>: mov    x1, x23
0x1a245afdc <+172>: mov    x2, x20
0x1a245afe0 <+176>: mov    x3, x22
0x1a245afe4 <+180>: blr    x8
    结合第 1 步保存的参数，我们可以推理到等效的 c 代码：
    cow_copy_instance(旧字典,常量1,新字典, 参数5)

7.3 超出阀值，开始调用 cow_copy_storage
0x1a245afe8 <+184>: ldr    x8, [x21, #0x8]
    (lldb) image lookup -a $x8
    Address: CoreFoundation[0x00000001804ccea8] (CoreFoundation.__TEXT.__text + 1535640)
    Summary: CoreFoundation`cow_copy_storage
0x1a245afec <+188>: mov    x0, x20
0x1a245aff0 <+192>: blr    x8

7.4 如果返回是0，进入失败处理逻辑
0x1a245aff4 <+196>: tbz    w0, #0x0, 0x1a245b020     ; <+240>

7.5 更新 新字典 的 cow
0x1a245aff8 <+200>: ldr    x8, [x21, #0x10]
0x1a245affc <+204>: mov    x0, x20
0x1a245b000 <+208>: mov    x1, #0x0
0x1a245b004 <+212>: blr    x8
(lldb) image lookup -a $x8
  Address: CoreFoundation[0x00000001804ccfbc] (CoreFoundation.__TEXT.__text + 1535916)
  Summary: CoreFoundation`cow_set_cow


8、报告错误
0x1a245b020 <+240>: adrp   x0, 333996
0x1a245b024 <+244>: add    x0, x0, #0x710            ; =0x710
(lldb) image lookup -a $x0
  Address: CoreFoundation[0x00000001d1c67710] (CoreFoundation.__DATA_CONST.__cfstring + 448)
  Summary: @"Failed to grow buffer"
0x1a245b028 <+248>: bl     0x1a245af24               ; _cow_allocation_failure

-[__NSDictionaryM setObject:forKey:]

当我们对一个可变字典的可变副本进行赋值时，就会触发 cow 机制

1
2


NSMutableDictionary *dicMutableCopy =  [dic mutableCopy];
[dicMutableCopy setObject:@"1" forKey:@"11"];

本段开始，只会对关键位置的汇编指令添加注释

_cow_mutate_slow

_cow_mutate_slow 会通过 cow_copy_storage 进行复制操作

参数列表：

字典
cow
保存 4 个特殊函数指针的结构体 __NSDictionary_cowCallbacks

1
2
3
4
5
6


(lldb) x/4a &__NSDictionary_cowCallbacks
0x1f3d071e8: 0x00000001a256ce44 CoreFoundation`cow_copy_instance
0x1f3d071f0: 0x00000001a256cea8 CoreFoundation`cow_copy_storage
0x1f3d071f8: 0x00000001a256cfbc CoreFoundation`cow_set_cow
0x1f3d07200: 0x00000001a256c610 CoreFoundation`cow_cleanup
(lldb)

_cow_mutate_slow：

 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


CoreFoundation`_cow_mutate_slow:
    0x1a245b02c <+0>:  stp    x20, x19, [sp, #-0x20]!
    0x1a245b030 <+4>:  stp    x29, x30, [sp, #0x10]
    0x1a245b034 <+8>:  add    x29, sp, #0x10            ; =0x10
    0x1a245b038 <+12>: mov    x20, x2
    0x1a245b03c <+16>: mov    x19, x0

    1. 偏移0x8，所以是调用 cow_copy_storage
    0x1a245b040 <+20>: ldr    x8, [x2, #0x8]
    0x1a245b044 <+24>: blr    x8

    2. 判断是否复制成功，失败会进入异常处理逻辑
    0x1a245b048 <+28>: tbz    w0, #0x0, 0x1a245b064     ; <+56>

    2.1 如果复制成功，则调用函数 cow_set_cow 进行下一步处理
    0x1a245b04c <+32>: ldr    x2, [x20, #0x10]
    0x1a245b050 <+36>: mov    x0, x19
    0x1a245b054 <+40>: mov    x1, #0x0
    0x1a245b058 <+44>: ldp    x29, x30, [sp, #0x10]
    0x1a245b05c <+48>: ldp    x20, x19, [sp], #0x20
    0x1a245b060 <+52>: br     x2
        拼接参数后是 cow_set_cow（字典,nil）

    3. 异常处理
    0x1a245b064 <+56>: adrp   x0, 333996
    0x1a245b068 <+60>: add    x0, x0, #0x710            ; =0x710
    0x1a245b06c <+64>: bl     0x1a245af24               ; _cow_allocation_failure

cow_copy_storage

cow_set_cow

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


CoreFoundation`cow_set_cow:
    1、动态获取 __NSDictionaryM.cow 的偏移值
    0x1a256cfbc <+0>:  adrp   x8, 367773
    0x1a256cfc0 <+4>:  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

    2、x8 是个指针，指向 字典的 cow
    0x1a256cfc4 <+8>:  add    x8, x0, x8

    3、将 x1 存入到 字典的 cow
    0x1a256cfc8 <+12>: stlr   x1, [x8]
    0x1a256cfcc <+16>: ret

总结

本文通过对可变字典的复制和修改方法的实现进行了逐步的分析，分享了可变字典的 cow 机制