酷酷的哀殿


  • 首页

  • 技术

  • 笔记

  • 杂记

  • Todo

  • 关于

  • 搜索
close

跟着 NSDictionary 的底层设计学习优化技巧(1)

时间: 2021-05-01   |   阅读: 5088 字 ~11分钟

最近有些群友反馈自己经常遇到一些与 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];

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

image

二、__NSPlaceholderDictionary

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

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

1
2
id obj = nil;
NSDictionary *dic = @{ @"k" : @"v", obj : obj };
  1. 在字典的初始化过程中,+[NSDictionary dictionaryWithObjects:forKeys:count:]会先调用objc_alloc 进行初始化

    image

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

    image

  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 进入不可变数组的通用处理逻辑

    image

  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)

    image

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

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

    敲重点:

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

    2、数组的长度是 40

    image

  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,并将对应位置的值取出来

    image

    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 区域

    image

     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)

    image

      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?0816l
    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 键值对的结构体

image

总结

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

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

相关推荐

  • 跟着 NSDictionary 的底层设计学习优化技巧(2)
  • 跟着 NSDictionary 的底层设计学习优化技巧(3)
  • Hugo 网站优化总结(1)
  • 网站加载优化(1)
#优化技巧# #性能# #NSDictionary# ##
x86_64 的 CALL 指令长度是固定的吗?
跟着 NSDictionary 的底层设计学习优化技巧(2)
  • 文章目录
  • 站点概览
酷酷的哀殿

酷酷的哀殿

单身狗

74 日志
83 标签
    • 一、·NSDictionary· 结构简介
      • 1、类簇
      • 2、语法糖
    • 二、__NSPlaceholderDictionary
    • 三、__NSDictionaryI
    • 总结
© 2021 酷酷的哀殿 京ICP备18052541号-2
Powered by - Hugo v0.80.0
Theme by - NexT
0%