你不知道的TaggedPointer

一、环境介绍

mac版本：Mac Mojave 10.14
objc版本：objc runtime 750

二、为什么要使用TaggedPointer？

以前我们初始化一个对象（64位为例），开发的代码如下

NSNumber *number2 = [NSNumber numberWithInteger:2];

此时的内存图如下

15469379882496.jpg

可以看到我就想存一个2用掉了24个字节，由于我们的NSNumber和NSDate对象的值一般不需要8个字节，4个字节的长度2^31=2147483648可以表达的数量已经达到了20多亿了，为了不造成内存的浪费，想到将指针的值(8个字节)进行拆分，一部分表示数据，一部分用来表示是一个特殊的指针，他不执行任何对象，这就是TaggedPointer技术，这样指针 = Data + Tag，那么我们的存一个数字只需要8个字节就够了。

三、一个简单的例子

3.1 版本新特性

NSNumber *number1 = @1;
NSNumber *number2 = @2;
NSNumber *number3 = @3;
NSNumber *numberFFFF = @(0xFFFF);

NSLog(@"number1 pointer is %p", number1);
NSLog(@"number2 pointer is %p", number2);
NSLog(@"number3 pointer is %p", number3);
NSLog(@"numberffff pointer is %p", numberFFFF);

输出结果却是这个样子的

number1 pointer is 0x19ec25e574ba1459
number2 pointer is 0x19ec25e574ba1759
number3 pointer is 0x19ec25e574ba1659
numberffff pointer is 0x19ec25e57445ea59

这个地址有点特殊，研究了一下，发现原来是在10_14以后苹果对TaggedPointer进行了混淆，文件objc-runtime-new.m写到

static void
initializeTaggedPointerObfuscator(void)
{
    if (sdkIsOlderThan(10_14, 12_0, 12_0, 5_0, 3_0) ||
        DisableTaggedPointerObfuscation) {
        objc_debug_taggedpointer_obfuscator = 0;
    } else {
        arc4random_buf(&objc_debug_taggedpointer_obfuscator,
                       sizeof(objc_debug_taggedpointer_obfuscator));
        objc_debug_taggedpointer_obfuscator &= ~_OBJC_TAG_MASK;
    }
}

混淆的代码也很简单，类似这种加入加密前的数据是a,加密后的数据为b，
那么：

加密：b = a ^ objc_debug_taggedpointer_obfuscator,
解密: a = b ^ objc_debug_taggedpointer_obfuscator.

这里利用了异或的特性，源码如下：

static inline void * _Nonnull
_objc_encodeTaggedPointer(uintptr_t ptr)
{
    return (void *)(objc_debug_taggedpointer_obfuscator ^ ptr);
}

static inline uintptr_t
_objc_decodeTaggedPointer(const void * _Nullable ptr)
{
    return (uintptr_t)ptr ^ objc_debug_taggedpointer_obfuscator;
}

所以要想知道0x19ec25e574ba1459是什么意思，还是要知道objc_debug_taggedpointer_obfuscator值，这是个随机值，要想获取这个值：

方法一：通过断点来获取

15471013678173.jpg

通过lldb指令读取

(lldb) p/x objc_debug_taggedpointer_obfuscator
(uintptr_t) $0 = 0x19ec25e574ba157e

方法二：看来runtime源码知道objc_debug_taggedpointer_obfuscator是个全局变量，只要在我们用的地方申明一下即可

extern uintptr_t objc_debug_taggedpointer_obfuscator;

通过NSLog打印就可以了

NSLog(@"%lx",objc_debug_taggedpointer_obfuscator);

为了方便查看，简单写了一个方法，用来解开混淆

uintptr_t _objc_decodeTaggedPointer_(id  ptr) {
    NSString *p = [NSString stringWithFormat:@"%ld",ptr];
    return [p longLongValue] ^ objc_debug_taggedpointer_obfuscator;
}

3.2 真实的地址

NSNumber *number1 = @1;
NSNumber *number2 = @2;
NSNumber *number3 = @3;
NSNumber *numberFFFF = @(0xFFFF);

NSLog(@"number1 pointer is %p---真实地址:==0x%lx", number1,_objc_decodeTaggedPointer_(number1));
NSLog(@"number2 pointer is %p---真实地址:==0x%lx", number2,_objc_decodeTaggedPointer_(number2));
NSLog(@"number3 pointer is %p---真实地址:==0x%lx", number3,_objc_decodeTaggedPointer_(number3));
NSLog(@"numberffff pointer is %p---真实地址:==0x%lx", numberFFFF,_objc_decodeTaggedPointer_(numberFFFF));

输出

number1 pointer is 0xfda27e12be89be71---真实地址:==0x127
number2 pointer is 0xfda27e12be89bd71---真实地址:==0x227
number3 pointer is 0xfda27e12be89bc71---真实地址:==0x327
numberffff pointer is 0xfda27e12be764071---真实地址:==0xffff27

会发现，不管运行多少次，都是以27结尾，我们有理由相信，苹果贡献了1个字节（8个bit）来标识这是个特殊的指针，最后1个字节用来标识，这个类指针，判断是否是TaggedPointer不同平台判断的方式不一样，但对我们理解根本不影响

static inline bool 
_objc_isTaggedPointer(const void * _Nullable ptr)
{
    return ((uintptr_t)ptr & _OBJC_TAG_MASK) == _OBJC_TAG_MASK;
}

mac平台最后一个为1；
iPhone和模拟器，为最高位是1。

那么剩下的7个字节是不是都用来存放数据呢？

3.3 TaggedPointer存储的数字的最大值

NSNumber *numberF13   = @(0xFFFFFFFFFFFFF);
NSNumber *numberF13_1 = @(0x1FFFFFFFFFFFFF);
NSNumber *numberF13_3 = @(0x3FFFFFFFFFFFFF);
NSNumber *numberF13_7 = @(0x7FFFFFFFFFFFFF);
NSNumber *numberF14   = @(0xFFFFFFFFFFFFFF);

NSLog(@"numberF13 pointer is %p---真实地址:==0x%lx", numberF13,_objc_decodeTaggedPointer_(numberF13));
NSLog(@"numberF13_1 pointer is %p---真实地址:==0x%lx", numberF13_1,_objc_decodeTaggedPointer_(numberF13_1));
NSLog(@"numberF13_3 pointer is %p---真实地址:==0x%lx", numberF13_3,_objc_decodeTaggedPointer_(numberF13_3));
NSLog(@"numberF13_7 pointer is %p---真实地址:==0x%lx", numberF13_7,_objc_decodeTaggedPointer_(numberF13_7));
   
NSLog(@"numberF14 pointer is %p---真实地址:==0x%lx", numberF14,_objc_decodeTaggedPointer_(numberF14));

输出如下

number1 pointer is 0x20f9850034a2e631---真实地址:==0x127
number2 pointer is 0x20f9850034a2e531---真实地址:==0x227
number3 pointer is 0x20f9850034a2e431---真实地址:==0x327
numberffff pointer is 0x20f98500345d1831---真实地址:==0xffff27
numberF13 pointer is 0x2f067affcb5d1821---真实地址:==0xfffffffffffff37
numberF13_1 pointer is 0x3f067affcb5d1821---真实地址:==0x1fffffffffffff37
numberF13_3 pointer is 0x1f067affcb5d1821---真实地址:==0x3fffffffffffff37
numberF13_7 pointer is 0x5f067affcb5d1821---真实地址:==0x7fffffffffffff37

numberF14 pointer is 0x102500210

从输出可以看出，到numberF14地址已经是真正的oc对象的地址了，说明有效存储位置有56位，所以TaggedPointer所能表达的数字范围为[0 2^65)。

四、思考：你会如何实现`NSString`的TaggedPointer？

我们现在想做的事情就是如何利用指针来存储我们的字符数据，而指针的大小就是8个字节，一共64位，如何利用这个64位呢？由NSNumber的灵感，可以使用低1位来表示是TaggedPointer类型，其他三位来表示具体哪个类的，对于字符串，需要存储它的长度，再让出4位，还剩下56位，从而问题转为如何利用这个56位。

计算机中存储的就是0和1，对于字符串的编码有ASCII和非ASCII：

ASCII是利用一个字节的大小表示字符的，一共是128个（最高位都为0）；
后面为了统一编码出现了Unicode编码，Unicode是规定了符号的二进制代码，没有规定如何存储，具体如何存储的，后来就出现了，UTF-16（字符用两个字节或四个字节表示）、UTF-32（字符用四个字节表示）和UTF-8（最常用的，兼容了ASCII）

对于非ASCII：

如果是UTF-32编码的,要想包含所有Unicode，需要4个字节，那么最多也只能保存1个字符，没有任何意义；
如果是 UTF-16编码的，要想包含所有Unicode，也需要4个字节，最少也需要2个字节，按最少的算，那么56位，也只能放3个16为的字符，还是很少；
如果是UTF-8，如果撇开ASCII的话，那么也是最多需要4个字节，最少2个字节，56位还是最多放3个字节。

对于非ASCII我们貌似没有找到一个好的方案来存储，那么我们要实现TaggedPointer的话，是不是可以不考虑非ASCII的情况，毕竟在实际场景，我们用到ASCII的场景的几率还是比非ASCII大的多，对于非ASCII的还是交给开辟控件的方式。

对于ASCII:

如果我们不考虑非ASCII的话，那么有以下方案可以用来存储数据：

方案一: 使用8位存储一个字符，这也是默认计算机存储ASCII的方式，由于占用一个字节，那么这种方式56位可以放7个字节；
方案二: 使用7位存储一个字符，ASCII其实真正存储数据的是7位，如果是用7位表示一个字符的话，那么最多可以放8个字节，比方案一多出一个字节；
方案三: 使用6位存储，有人可能想6位怎么可能，存储ASCII最少也得7位啊，6怎么存储，是的，直接存是不行的，但是我们可以不直接存字符，而是提供一个表格，存索引。ASCII一共有128个，但是我们常用的根本就没有那么多，那么我们可以不可以选出一些常用的来作为我们的可选值？ 6位的话，最多可以存储2^ 6 = 64个不同的字符,所以肯定是不能满查找ASCII集合，但是，我们可以找来常见的64个字符比如[a-zA-z0-9./_-],这里就有66个了，再从这个66个里面取出2个不常用的就可以了，这样的话我们就可以存储9个字节了；
方案四: 使用5位存储，这种的话我们的查找范围就缩小为了2^5 = 32个，也就是我们要在方案三的基础上在找出更加常用的32个字符，这种方案可以存储11个字符；
方案五: 使用4位存储，那范围就是2^4 = 16个，这种感觉行也行，但是范围太小了
更少的想想不大可能了

下面看下苹果是如何实现的

五、对于NSString苹果是如何使用TaggedPointer的？

5.1 现象

添加测试如下测试代码

NSMutableString *imutable = [NSMutableString string];
NSString *immutable;
char c = 'a';
do {
 [imutable appendFormat: @"%c", c++];
 immutable = [imutable copy];
 NSLog(@"源地址：%p 真实地址：0x%lx %@ %@", immutable,_objc_decodeTaggedPointer_(immutable), immutable, object_getClass(immutable));
} while(((uintptr_t)immutable & 1) == 1);

输出，这里我省去了源地址，因为这里打印了类的类型更直观写

真实地址：0x6115                 a               NSTaggedPointerString
真实地址：0x626125               ab              NSTaggedPointerString
真实地址：0x63626135             abc             NSTaggedPointerString
真实地址：0x6463626145           abcd            NSTaggedPointerString
真实地址：0x656463626155         abcde           NSTaggedPointerString
真实地址：0x66656463626165       abcdef          NSTaggedPointerString
真实地址：0x6766656463626175     abcdefg         NSTaggedPointerString
真实地址：0x22038a01169585       abcdefgh        NSTaggedPointerString
真实地址：0x880e28045a54195      abcdefghi       NSTaggedPointerString
真实地址：0xf9eb5f3ca3c376e0     abcdefghij      __NSCFString

前面提到过最后一个字节低4位标志是TaggedPointer信息，高4位存放字符串的长度，所以最后一个数字5是标志位，倒数一个数字就是字符串的长度。

从上面的输出可以看出：

当字符串的长度<=7的时候，苹果是直接存储的字符ASCII值，a的ASCII值是61，b是62...。
当字符串长度大于7的时候具体如何做的，我们通过逆向CoreFoundation.framework来查看

5.2 hopper -> length

先来看下length方法，看看是不是和我们猜测的一样

15471101516030.jpg

翻译一下就是


rdi = self ^ *_objc_debug_taggedpointer_obfuscator; // 解密得到真实地址

if ((di & 14 ) == 14) { 也就是//0b1110 我们的字符串的是5(0x0101)，所以走else了
       rax = (di >> 11) & 0xf;
} else {
       rax =(di >>  4 ) & 0xf;
}  


再简化一下就是

======

rax = (di >>  4 ) & 0xf

已经很显然了，就是拿低1字节的高4位的值,证明了我们的猜想。

5.3 hopper -> characterAtIndex

苹果是如何将字符转成NSTaggedPointerString的，不是很好查，但是我们可以反向思考，通过取数据来反推如何存的，

15471113839214.jpg

下面开始简化该伪代码，如果你觉得不想看，可以直接跳到第四次简化开始看。

___stack_chk_guard是为了安全加的，不考虑，前面分析过((((r8 ^ rdi) & 0xe) == 0xe ? 0x1 : 0x0) << 0x3 | 0x4)在这里等价于0x4，arg2就是传进来的index

5.3.1 第一次简化

unsigned short -[NSTaggedPointerString characterAtIndex:](void * self, void * _cmd, unsigned long long arg2) {
    r12 = index;
    rbx = self >>  0x4 & 0xf;
    r8 = self >> 0x4 >> 0x4;
    if (rbx >= 0x8) {
            rdx = rbx;
            if (rbx < 0xa) {
                    do {
                            *(int8_t *)(rbp + rdx + 0xffffffffffffffc7) = *(int8_t *)((r8 & 0x3f) + _sixBitToCharLookup);
                            rdx = rdx - 0x1;
                            r8 = r8 >> 0x6;
                    } while (rdx != 0x0);
            }
            else {
                    do {
                            *(int8_t *)(rbp + rdx + 0xffffffffffffffc7) = *(int8_t *)((r8 & 0x1f) + _sixBitToCharLookup);
                            rdx = rdx - 0x1;
                            r8 = r8 >> 0x5;
                    } while (rdx != 0x0);
            }
    }

    rax = *(int8_t *)(rbp + r12 + 0xffffffffffffffc8) & 0xff;
    
    return rax;
}

继续分析这段代码

self >> 0x4 & 0xf;其实就是字符串的length
self >> 0x4 >> 0x4;其实就是字符串的开始位置
0xffffffffffffffc7其实是-0x39 = -57的补码,0xffffffffffffffc7是-0x38 = -56的补码

5.3.2 第二次简化

unsigned short -[NSTaggedPointerString characterAtIndex:](void * self, void * _cmd, unsigned long long arg2) {
    rbx = length;
    r8 = self >> 0x8;
    if (rbx >= 0x8) {
            if (length < 0xa) {
                    do {
                            *(int8_t *)(rbp - 57 + rdx) = *(int8_t *)((r8 & 0x3f) + _sixBitToCharLookup);
                            rdx = rdx - 0x1;
                            r8 = r8 >> 0x6;
                    } while (rdx != 0x0);
            }
            else {
                    do {
                            *(int8_t *)(rbp - 57 + rdx) = *(int8_t *)((r8 & 0x1f) + _sixBitToCharLookup);
                            rdx = rdx - 0x1;
                            r8 = r8 >> 0x5;
                    } while (rdx != 0x0);
            }
    }

    rax = *(int8_t *)(rbp - 56 + index) & 0xff;
    
    return rax;
}

bp其实就是栈指针，这里使用bp说明是通过bp来操控栈空间的，然后每次循环dx都减1，然后r8左移6位或者5位，这个一般都是数组操作了，如果是5位的话最多存11个字节，所以这里使用一个长度11的数组buffer[11]，dx其实就会游离指针了我们用变量cursor表示

5.3.3 第三次简化

unsigned short -[NSTaggedPointerString characterAtIndex:](void * self, void * _cmd, unsigned long long arg2) {

    int8_t  buffer[11];
    r8 = self >> 0x8;
    
    if (length >= 0x8) {
            base = rbp - 57;
            cursor = length;
            if (length < 0xa) {
                    do {
                            buffer[base + cursor ] = *(int8_t *)((r8 & 0x3f) + _sixBitToCharLookup)
                            cursor = cursor - 0x1;
                            r8 = r8 >> 0x6;
                    } while (rdx != 0x0);
            }
            else {
                    do {
                            buffer[base + cursor ] = *(int8_t *)((r8 & 0x1f) + _sixBitToCharLookup);
                            cursor = cursor - 0x1;
                            r8 = r8 >> 0x5;
                    } while (rdx != 0x0);
            }
    }

    rax = *(int8_t *)(rbp - 56 + index) & 0xff;
    
    return rax;
}

_sixBitToCharLookup到底是什么呢，其实就是字符串

15471761831012.jpg

也就是eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX

其实程序还少了一段代码，hopper翻译伪代码的时候漏掉了

0000000000060d87         cmp        rbx, 0x8
0000000000060d8b         jb         loc_60dd1 // 当bs < 0x8时
...
loc_60dd1:
0000000000060dd1         mov        qword [rbp+var_38], r8

var_38就是-56

15471166175011.jpg

其实就是将r8的值放到[bp-56]的内存处，由于是小端存储，其实就是讲self>> 8的内容存放到对应的内存地址，类似于下面的代码，但是是占8个字节的

 *(uint64_t *)buffer = self >> 8;

5.3.4 第四次简化

unsigned short -[NSTaggedPointerString characterAtIndex:](void * self, void * _cmd, unsigned long long arg2) {

    int8_t  buffer[11];
    r8 = self >> 0x8;
    
    if (length >= 0x8) {
       base = rbp - 57;
       cursor = length;
       _sixBitToCharLookup = 'eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX';
       if (length < 0xa) {
               do {
                   buffer[base + cursor ] = _sixBitToCharLookup[r8 & 0x3f]
                   cursor = cursor - 0x1;
                   r8 = r8 >> 0x6;
               } while (rdx != 0x0);
       } else {
               do {
                   buffer[base + cursor ] = _sixBitToCharLookup[r8 & 0x1f];
                   cursor = cursor - 0x1;
                   r8 = r8 >> 0x5;
               } while (rdx != 0x0);
       }
    } else {
        *(uint64_t *)buffer = self >> 8;
    }

    rax = *(int8_t *)(rbp - 56 + index) & 0xff;
    
    return rax;
}

这就显而易见了，对于字符串苹果的处理如下：

对于小于8个字符的，使用的是8位存储；
[8,10)的是通过6位存储的；
[10,11]的是通过5位存储的。

根据这个结论我们再来看下5.1的现象，对于上面的判断条件分别选一个代表

5.3.4.1 小于`8`位代表`0x66656463626165 -> abcdef`

可以看出是直接存储的；

5.3.4.2 `[8,10)`代表：`0x22038a01169585 -> abcdefgh`

去掉后面的95剩下0x22038a011695，6位排列如下

001000 100000 001110 001010 000000 010001 011010 010101，每一个就对应这个字符串eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX的索引值，为了方便查找做了一个对照表

15469350941106.jpg

所以

001000 100000 001110 001010 000000 010001 011010 010101

分别对应

a b c d e f g h

5.3.4.3 `[10,11]`位代表`abcdefghij`

但是这个类是__NSCFString并不是我们的NSTaggedPointerString，按道理说5位的话是可以存放10个字节的啊，这是什么原因呢？

原来：不管是5位还是6位都是查询的同一个字符串eilotrm.apdnsIc ufkMShjTRxgC4013bDNvwyUL2O856P-B79AFKEWV_zGJ/HYX，也就是上图索引表的颜色区分，5位里面没有包含b字符，但是我们的abcdefghij有b字符，所以不行，修改demo如下看看


NSString *str = [NSString stringWithFormat:@"acdefghijk"];
NSString *str2 = [NSString stringWithFormat:@"acdefghijkm"];
NSString *str3 = [NSString stringWithFormat:@"acdefghijkmn"];
    
NSLog(@"真实地址：0x%lx %@ %@", str,_objc_decodeTaggedPointer_(str), str3, object_getClass(str));
NSLog(@"真实地址：0x%lx %@ %@", str2,_objc_decodeTaggedPointer_(str2), str3, object_getClass(str2));
NSLog(@"真实地址：0x%lx %@ %@", str3,_objc_decodeTaggedPointer_(str3), str3, object_getClass(str3));

输出

真实地址：0x10e5023aa86d2a5 acdefghijk NSTaggedPointerString
真实地址：0x21ca047550da46b5 acdefghijkm NSTaggedPointerString
真实地址：0xc64838cff22b0b46 acdefghijkmn __NSCFString

可以看到能够支持11个字节了，0x10e5023aa86d2a5去掉0x10e5023aa86d2，按5位排列下看看

01000 01110 01010 00000 10001 11010 10101 00001 10110 10010

也就是 a c d e f g h i j k

所以我们可以得出能够存[10,11]位字符是以所存字符在eilotrm.apdnsIc ufkMShjTRxgC4013内为前提的。

最后再来看下苹果对于非ASCII是怎么处理的，以汉字方（Unicode）编码为\u65b9,占3个字节，按道理也是可以放进指针里面的，我们看看苹果有没有这样做

NSString *notAscii_1 = [NSString stringWithFormat:@"方"];

NSLog(@"源地址：%p  %@ %@", notAscii_1,notAscii_1, object_getClass(notAscii_1));

输出

源地址：0x101907df0  方 __NSCFString

发现苹果并没有放进指针内，而是真实的oc对象。

至此，我们之前的猜测一一验证了。

下面总结一下TaggedPointer的特点

六、什么样的字符会放进TaggedPointer？

总结了以下表格，注意这个只适用ASCII的情况，对于非ASCII都是使用的oc对象。

15471895085356.jpg

传入的字符任意一个不在所在行的范围，存的地方就会发生变化。

七、一个和TaggedPointer相关的面试题

下面代码会发生什么问题？

@property (nonatomic, copy) NSString *target;
//.... dispatch_queue_t queue = dispatch_queue_create("parallel", DISPATCH_QUEUE_CONCURRENT);

// 方式一
for (int i = 0; i < 1000000 ; i++) {
    dispatch_async(queue, ^{
        self.target = [NSString stringWithFormat:@"ksddkjalkjd%d",I];
    });
}



//.... dispatch_queue_t queue = dispatch_queue_create("parallel", DISPATCH_QUEUE_CONCURRENT);
// 方式二
for (int i = 0; i < 1000000 ; i++) {
    dispatch_async(queue, ^{
        self.target = [NSString stringWithFormat:@"ksddkjalkj"];
    });
}

先说下结果吧，方式一会闪退，方式二正常运行。

分析这个道题，target的set方法实现

- (void)setTarget:(NSString *)target {
    if(_target != target) {
        [_target release];
        target = [target retain];
    }
}

方式一是真正的oc对象，由于是多线程会出现[_target release];被调用多次，从而闪退；
方式二不是oc对象，而是TaggedPointer,在release和retain的时候都会判断是不是TaggedPointer


objc_object::rootRelease(bool performDealloc, bool handleUnderflow)
{
    if (isTaggedPointer()) return false;

    bool sideTableLocked = false;
    ...
}


ALWAYS_INLINE id 
objc_object::rootRetain(bool tryRetain, bool handleOverflow)
{
    if (isTaggedPointer()) return (id)this;

}

其他的方式可以加锁解决，就不说了。

你不知道的TaggedPointer