探究引用计数的实现

2016-09-14 本文已影响243人 StanOz

MRR 即为 “manual retain-release”，人为地插入 retain, release 等语句进行内存管理。

内存管理基础规则

整个内存管理模型都是围绕对象拥有权（object ownership）工作的：如果某个对象一直被其它对象所拥有，那么它就会存在，反之则以。遵循以下规则以保证对对象拥有权管理的正确性：

自己生成的对象，自己持有（使用 allow/new/copy/mutableCopy 开头的方法生成并持有对象）；
```
  id obj = [[NSObject alloc] init];
```
非自己生成的对象，自己也能持有（发送 -retain 消息持有对象）；
```
  NSMutableArray *array = [NSMutableArray array];
  [array retain];
```
不再需要自己持有的对象时，应该交出自己的对象所有权（发送 -release 消息释放对象所有权，或者发送 -autorelease 消息延迟释放）；
```
  id obj = [[NSObject alloc] init];
  [obj release];
```
无法释放自己不持有的对象的所有权；

换做引用计数来理解，通过 +alloc/-init 等方法生成一个对象，这对对象被你所持有，它的引用计数（retain count）是 1。对它发送 -retain 消息，引用计数加一，发送 -release 消息则减一，当其引用计数为 0 时，对象所占的内存被系统回收。

引用计数的存储与操作

下面 objc-runtime 的代码来源于 RetVal 的 Github。感谢作者的修复。

引用计数的存储

要知道引用计数是如何存储与操作，除了知道与计数相关的数据结构之外，还要知道 isa 指针的存储优化(non-pointer isa)和 tagged pointer 这两项技术，这些知识在下文中对 -retainCount 等实现的理解有帮助：

non-pointer isa

isa 指针通常用来指向对象所属的类，然而在 64 位的环境下（模拟器不支持），isa 还能存储一些额外的信息，毕竟 64 个比特仅仅存储一个类的地址确实有些浪费。那么，先瞄一下 isa 中 bits 的各个指针变量（以x86_64平台的为例）

    // 变量意义来源于：http://www.sealiesoftware.com/blog/archive/2013/09/24/objc_explain_Non-pointer_isa.html
    // 其意义可能已经有些改变，这里列出来仅供参考。
    struct {
        uintptr_t indexed           : 1;  // 0 表示纯粹的 isa 指针，1 表示 non-pointer isa
        uintptr_t has_assoc         : 1;  // 是否有 associated object，没有的话 dealloc 会更快
        uintptr_t has_cxx_dtor      : 1;  // 是否有 C++/ARC 的析构函数，没有的话 dealloc 会更快
        uintptr_t shiftcls          : 44; // 指向类的指针
        uintptr_t magic             : 6;  // 0x02 用于在调试时区分未初始化的垃圾数据和已经初始化的对象
        uintptr_t weakly_referenced : 1;  // 是否被 weak 变量引用过，没有的话 dealloc 会更快
        uintptr_t deallocating      : 1;  // 是否正在 deallocating
        uintptr_t has_sidetable_rc  : 1;  // 引用计数值是否太大，以至于无法存在 isa 中，需要 SideTable 辅助存储
        uintptr_t extra_rc          : 8;  /* 额外的引用计数值。对象实例化时的本身的引用计数值为 1，而该值为 0。 
                                            向该对象发送 retain 消息后，extra_rc 增加 1。当 extra_rc 太大时，则需要 SideTable 辅助计数。*/
        
         #define RC_ONE   (1ULL<<56)       // bits + RC_ONE 等于 extra_rc + 1
         #define RC_HALF  (1ULL<<7)
    };

tagged pointer

同样的，tagged pointer 也是 64 位环境下一种利用指针优化存储技术，用来存储一些小对象（实际上只是栈上的一段数据，可能算不上是一个 Objective-C 对象），减少 malloc/free 在堆上的开销。在 objc_internal.h 中能看到以下的类型支持 tagged pointer:

    OBJC_TAG_NSAtom            = 0,
    OBJC_TAG_1                 = 1,
    OBJC_TAG_NSString          = 2,
    OBJC_TAG_NSNumber          = 3,
    OBJC_TAG_NSIndexPath       = 4,
    OBJC_TAG_NSManagedObjectID = 5,
    OBJC_TAG_NSDate            = 6,
    OBJC_TAG_7                 = 7

对于一个 tagged pointer，其内存布局如下：

MSB	60 bit	3 bit	1 bit	LSB
<	payload	tag index，即上面所列出来的类型	1 表示 tagged pointer 对象，0 表示普通对象	>

你可以写这么一段代码去验证对象是否为 tagged pointer 对象，以及检查它的类型：

    NSNumber *obj = @1;
        
    uintptr_t ptr = 0xF;
    uintptr_t result = ((uintptr_t)obj & ptr);
        
    NSLog(@"obj's pointer: %p", obj);
    NSLog(@"isTaggedPointer: %lu", result & 0x1);
    NSLog(@"TaggedPointerType: %lu", (result >> 1 & 0x7));

有人会试 NSString *obj = @"Hello!";，想看看它是不是 tagged pointer。
答案是否定的。str 指向的是 TEXT 段的一个常量指针，合理的实验方式是 NSString *obj = [NSString stringWithFormat:@"Hello!"]; 。

SideTable

上面的讨论中，我们引出了一个 SideTable 这样的东西。当一个对象的引用计数很大时（extra_rc 超出所能表示的范围），需要它辅助记录对象的引用计数。此时实际的计数值：retainCount = 1 + extra_rc + sideTable.refcnts[obj] 中的值。在 NSObject.mm 中的它，看起来大概是这样的：

    typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap;

    struct SideTable {
        spinlock_t slock;   // 自旋锁，保证对 sideTable 操作的原子性
        RefcountMap refcnts; // 存储引用计数的哈希表
        weak_table_t weak_table; // weak 表，这个放到 ARC 再讨论
        ...
    }

SideTable 将自旋锁、引用计数表和一个 weak 表封装到了一起。当需要根据对象读取 SideTable 时，会从一个名为 SideTableBuf 的静态数组中找到相应的 SideTable：

    // 出于某些原因以下面这种方式分配 4096 个字节，即为 64 个 sideTable 的大小
    alignas(sizeof(StripedMap<SideTable>)) static uint8_t SideTableBuf[sizeof(StripedMap<SideTable>)];

    // StripedMap 重载了 [] 运算符，具体实现可以查看源码，这里不再赘叙
    SideTable& table = SideTables()[this];

你可以理解 SideTableBuf 有 64 个格子，每个格子里面都有个 SideTable。每个对象指针可以通过计算映射到其中的一个格子中，然后再从格子中读取 refcnts 去找到自己的额外的引用计数。

值得注意的是存储引用计数的哈希表 RefcountMap refcnts，键是将对象指针包裹了一层的 DisguisedPtr，值是对象额外的引用计数值再左移两位，所以我们读取这个值的时候要再右移两位。

引用计数的操作

上面扯完了引用计数相关的数据结构，那么接下来分析 -retainCount,-retain,-release 在 objc-runtime 源码中的实现。有两点需要注意的：

objc-object.h 文件中对于这些方法背后函数的实现有两套，通过条件编译的宏 SUPPORT_NONPOINTER_ISA 区分，我第一次看的时候就搞蒙了；
这些方法上面都有 // Replaced by ObjectAlloc 这样的一行注释，应该是说这些方法被 Core Foundation 的实现给替换了，所以下面的分析可能与实际的逻辑不符。

下面的分析以 SUPPORT_NONPOINTER_ISA 为真的代码为例子。

retainCount

-retainCount 的实现最终落到下面这个函数上：

inline uintptr_t 
objc_object::rootRetainCount()
{
    assert(!UseGC);
    if (isTaggedPointer()) return (uintptr_t)this;

    sidetable_lock();
    
    isa_t bits = LoadExclusive(&isa.bits);      if (bits.indexed) {
        uintptr_t rc = 1 + bits.extra_rc;
        if (bits.has_sidetable_rc) {
            rc += sidetable_getExtraRC_nolock();
        }
        sidetable_unlock();
        return rc;
    }

    sidetable_unlock();
    return sidetable_retainCount();
}

在调用 objc_object::rootRetainCount 时，如果当前对象使用的是 tagged pointer，那么直接返回自身的指针值。因为考究存在于栈上的变量的引用计数几乎没有什么意义，它的生命周期由栈来管理。接着，如果对象使用了 non-pointer isa，并且没有使用 SideTable 辅助计数，那么返回对象实例化后的计数值 1 加上额外被 retain 的次数 extra_rc（objc_object::sidetable_getExtraRC_nolock 这个函数实现就不贴了，同下面的差不多）。

对于使用纯粹的 isa 指针的对象，会调到下面这个函数，从 SideTable 中获得计数表，通过 this 指针获得迭代器并访问引用计数值：

uintptr_t
objc_object::sidetable_retainCount()
{
    SideTable& table = SideTables()[this];

    size_t refcnt_result = 1;
    
    table.lock();
    RefcountMap::iterator it = table.refcnts.find(this);
    if (it != table.refcnts.end()) {
        // this is valid for SIDE_TABLE_RC_PINNED too
        refcnt_result += it->second >> SIDE_TABLE_RC_SHIFT;
    }
    table.unlock();
    return refcnt_result;
}

retain & release

理解上面获取引用计数的函数实现之后，对于 retain 和 release 的实现就不难理解了。但由于 id objc_object::rootRetain(bool, bool) 和 bool objc_object::rootRelease(bool, bool) 的实现都比较长，贴在这里有凑字数的嫌疑，而且使用了很多 goto 和递归，阅读起来也不太方便。

所以下面仅对一些关键的逻辑进行分析：

在 id objc_object::rootRetain(bool, bool) 中，如果对象是 tagged pointer object，那么直接返回该对象；对于普通的对象，如果其 isa 指针不用于优化存储，那么通过 goto unindexed; 跳到 unindexed 标签所标记的代码块，对 SideTable 的计数表进行操作；否则进入 do...while() 循环里面，通过下面的代码对 bits.extra 操作：
```
  newisa.bits = addc(newisa.bits, RC_ONE, 0, &carry);  // extra_rc++
```

一旦溢出，对象启用 SideTable 辅助计数，extra_rc 的值为最大值的一半，而将另一半拷贝到对应的 SideTable 中的计数表中。

 // 每次溢出，transcribeToSideTable 为真
 if (transcribeToSideTable) {
    sidetable_addExtraRC_nolock(RC_HALF);
}

在 bool objc_object::rootRelease(bool, bool) 中，对于 tagged pointer object 还是没有任何操作，直接返回。对于 goto unindexed; 跳转的那一块代码，调用 sidetable_release() 函数操作计数表。而在
```
  newisa.bits = subc(newisa.bits, RC_ONE, 0, &carry);  // extra_rc--
```

之后，如果 extra_rc 出现下溢，那么要跳转到 underflow 那一块代码进行操作，从对象的辅助计数表中把原先加到里面的数“要”回来:

// Try to remove some retain counts from the side table.        
size_t borrowed = sidetable_subExtraRC_nolock(RC_HALF);

如果“要”回来的数字大于零，那么将设置 extra_rc 并返回：

// Side table retain count decreased.
// Try to add them to the inline count.
newisa.extra_rc = borrowed - 1;  // redo the original decrement too

否则直接往下执行，向对象发送 -dealloc 消息：

if (performDealloc) {
    ((void(*)(objc_object *, SEL))objc_msgSend)(this, SEL_dealloc);
}

参考

Advanced Memory Management Programming Guide

Objective-C 引用计数原理