前言
最近偶尔出去面试了解一下现在iOS行情和面试会问的问题。其中有这样的一个问题被问到很多次：引用计数原理。回去查资料发现当时回答的很糟糕，于是就在这里单独写一篇文章记录下来。这篇文章只讲一个问题：引用计数的数量存哪里的，文末提到的其他问题后面会单独再写。
预备知识
要说清楚这个问题，我们需要先来了解下面的三个知识点。
调试环境如下。
macOS：10.13.4；
XCode：9.4；
调试设备：My Mac。
Tagged Pointer
这个玩意的详细解释在这里，简单的说64位系统下，对于值小（多小？后面有讲解）的对象指针本身已经存了值的内容了，而不用去指向一个地址再去取这个地址所存对象的值；相信你也知道了，如果是Tagged Pointer的话就少了创建对象的操作。
我们也可以在WWDC2013的《Session 404 Advanced in Objective-C》视频中，看到苹果对于Tagged Pointer特点的介绍：
1：Tagged Pointer专门用来存储小的对象，例如NSNumber和NSDate
2：Tagged Pointer指针的值不再是地址了，而是真正的值。所以，实际上它不再是一个对象了，它只是一个披着对象皮的普通变量而已。所以，它的内存并不存储在堆中，也不需要malloc和free。
3：在内存读取上有着3倍的效率，创建时比以前快106倍。
image
image
Non-pointer isa
我们一直认为实例对象的isa都指向类对象，甚至还看到这样的源码。
typedef struct objc_object *id
struct objc_object {
Class _Nonnull isa;
}
其实这是之前版本的代码了，现在版本的代码早就变了。
struct objc_object {
private:
isa_t isa;
...
}
所以实例对象的isa都指向类对象这样的说法不对。
现在实例对象的isa是一个isa_t联合体，里面存了很多其他的东西，相信你也猜到了引用计数也在其中；如果该实例对象启用了Non-pointer，那么会对isa的其他成员赋值，否则只会对cls赋值。
union isa_t {
Class cls;
...
(还有很多其他的成员，包括引用计数数量)
}
不使用Non-pointer的isa
可以简化为
isa_t isa = {
Class class = Person;
}
因为源码中显示不使用Non-pointer则只对isa的class赋值了，其他的都是默认值，而且除了class其他成员也不会在源码中被使用到。
使用Non-pointer的isa
isa_t isa = {
Class class = Person;
uintptr_t bits = 8303516107940673;
struct {
uintptr_t nonpointer = 1;
uintptr_t has_assoc = 0;
uintptr_t has_cxx_dtor = 0;
uintptr_t shiftcls = 536872040;
uintptr_t magic = 59;
uintptr_t weakly_referenced = 0;
uintptr_t deallocating = 0;
uintptr_t has_sidetable_rc = 0;
uintptr_t extra_rc = 0;
}
}
extra_rc就是存的引用计数，nonpointer = 1表示启用Non-pointer。
isa的赋值是在alloc方法调用时，内部会进入initIsa()方法，你可以进去看一看有啥不同之处。
objc_object::initIsa(Class cls, bool nonpointer, bool hasCxxDtor) {
if (!nonpointer) {
isa.cls = cls;
} else {
isa_t newisa(0);
......
(成员赋值)
......
isa = newisa;
}
}
SideTable
散列表，这是一个比较重要的数据结构，相信你也猜到了这个和对象引用计数有关；如果该对象不是Tagged Pointer且关闭了Non-pointer，那该对象的引用计数就使用SideTable来存。我们先来看一下SideTable结构体定义，至于怎么被使用的且听我慢慢道来。
struct SideTable {
//锁
spinlock_t slock;
//强引用相关
RefcountMap refcnts;
//弱引用相关
weak_table_t weak_table;
...
}
启动应用后，我们第一次看到SideTable其实是在runtime读取image的时候。
void map_images_nolock(unsigned mhCount, const char* const mhPaths[],
const struct mach_header *const mhdrs[]) {
...
static bool firstTime = YES;
if (firstTime) {
AutoreleasePoolPage::init();
SideTableInit();
}
...
}
static void SideTableInit() {
new (SideTableBuf)StripedMap<SideTable>();
}
map_images_nolock会多次调用，因为ImageLoader一批加载很多个image到内存，然后通知runtime去读取这一批image，没错这时候runtime开始从image中处理类了；SideTableInit()方法只会执行一次。
进入正题
下面我们就开始看看对象的引用计数到底存哪里了。我先把判断优先级写一下。
1：对象是否是Tagged Pointer对象；
2：对象是否启用了Non-pointer；
3：对象未启用Non-pointer。
满足1则不判断2，依次类推。
Tagged Pointer对象
retain时。
id objc_object::rootRetain(bool tryRetain, bool handleOverflow) {
if (isTaggedPointer()) return (id)this;
...
}
release时。
bool objc_object::rootRelease(bool performDealloc, bool handleUnderflow) {
if (isTaggedPointer()) return false;
...
}
retainCount时。
uintptr_t objc_object::rootRetainCount() {
if (isTaggedPointer()) return (uintptr_t)this;
...
}
由此可见对于Tagged Pointer对象，并没有任何的引用计数操作，引用计数数量也只是单纯的返回自己地址罢了。
开启了Non-pointer
retain时。
id objc_object::rootRetain(bool tryRetain, bool handleOverflow) {
...
//其实就是对isa的extra_rc变量进行+1，前面说到isa会存很多东西
addc(newisa.bits, 1, 0, &carry);
...
}
release时。
bool objc_object::rootRelease(bool performDealloc, bool handleUnderflow) {
...
//其实就是对isa的extra_rc变量进行-1
subc(newisa.bits, 1, 0, &carry);
...
}
retainCount时。
uintptr_t objc_object::rootRetainCount() {
...
//其实就是获取isa的extra_rc值再+1，alloc新建一个对象时bits.extra_rc为0并不是1，这个要注意。
uintptr_t rc = 1 + bits.extra_rc;
...
}
如果对象开启了Non-pointer，那么引用计数是存在isa中的，引用计数超过255将附加SideTable辅助存储。
更新：看网络上该系列文章时发现自己漏了一个细节，那就是extra_rc是有存储限制，经过测试为255，如果超过255将会附加SideTable辅助存储。详细解释看这里。
未开启Non-pointer isa
这个是最麻烦的，因为要用到SideTable，里面一大堆逻辑；我们拿上面的Person举例，请记住对象的地址。
retain时。
id objc_object::rootRetain(bool tryRetain, bool handleOverflow) {
...
sidetable_retain();
...
}
id objc_object::sidetable_retain() {
SideTable& table = SideTables()[this];
}
在这里不得不讲清楚SideTable的内部实现了，如果不讲清楚则没办法继续看代码。
SideTable中有三个结构体。
spinlock_t：锁，这个就不用说了，一个支持多线程环境运行的库肯定得考虑这个；
weak_table_t：weak表就是这个，用来处理弱引用的，不过本文不讲；
RefcountMap：引用表，引用计数就是这个存的，这个要好好的说明白。
RefcountMap的定义：
typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap;
又臭又长，本来想把类展开出来的，但是发现类会非常的大，而且很难懂；所以我这里讲一下逻辑就可以了，你感兴趣可以深入看看。
当我们第一次通过SideTables()[this]取得table时，这个table中refcnts内容是空的。
（我们省略spinlock_t和weak_table_t）：
SideTable table = {
...
RefcountMap refcnts = {
BucketT *Buckets = NULL;
unsigned NumEntries = 0;
unsigned NumTombstones = 0;
unsigned NumBuckets = 0;
}
...
}
RefcountMap
typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap;
DenseMap 又是一个模板类:
template<typename KeyT, typename ValueT,
bool ZeroValuesArePurgeable = false,
typename KeyInfoT = DenseMapInfo<KeyT> >
class DenseMap : public DenseMapBase<DenseMap<KeyT, ValueT,
ZeroValuesArePurgeable, KeyInfoT>, KeyT, ValueT, KeyInfoT,
ZeroValuesArePurgeable> {
...
BucketT *Buckets;
unsigned NumEntries;
unsigned NumTombstones;
unsigned NumBuckets;
...
}
比较重要的成员中我列举了这几个:
- ZeroValuesArePurgeable 默认值是 false, 但 RefcountMap 指定其初始化为 true. 这个成员标记是否可以使用值为 0 (引用计数为 1) 的桶. 因为空桶存的初始值就是 0, 所以值为 0 的桶和空桶没什么区别. 如果允许使用值为 0 的桶, 查找桶时如果没有找到对象对应的桶, 也没有找到墓碑桶, 就会优先使用值为 0 的桶.
- Buckets 指针管理一段连续内存空间, 也就是数组, 数组成员是 BucketT 类型的对象, 我们这里将 BucketT 对象称为桶(实际上这个数组才应该叫桶, 苹果把数组中的元素称为桶应该是为了形象一些, 而不是哈希桶中的桶的意思). 桶数组在申请空间后, 会进行初始化, 在所有位置上都放上空桶(桶的 key 为 EmptyKey 时是空桶), 之后对引用计数的操作, 都要依赖于桶.
桶的数据类型实际上是 std::pair, 类似于 swift 中的元祖类型, 就是将对象地址和对象的引用计数(这里的引用计数类似于 isa, 也是使用其中的几个 bit 来保存引用计数, 留出几个 bit 来做其它标记位)组合成一个数据类型.
typedef std::pair<KeyT, ValueT> BucketT;
- NumEntries 记录数组中已使用的非空的桶的个数.
- NumTombstones, Tombstone 直译为墓碑, 当一个对象的引用计数为0, 要从桶中取出时, 其所处的位置会被标记为 Tombstone. NumTombstones 就是数组中的墓碑的个数. 后面会介绍到墓碑的作用.
- NumBuckets 桶的数量, 因为数组中始终都充满桶, 所以可以理解为数组大小.
inline uint64_t NextPowerOf2(uint64_t A) {
A |= (A >> 1);
A |= (A >> 2);
A |= (A >> 4);
A |= (A >> 8);
A |= (A >> 16);
A |= (A >> 32);
return A + 1;
}
这是对应 64 位的提供数组大小的方法, 需要为桶数组开辟空间时, 会由这个方法来决定数组大小. 这个算法可以做到把最高位的 1 覆盖到所有低位. 例如 A = 0b10000, (A >> 1) = 0b01000, 按位与就会得到 A = 0b11000, 这个时候 (A >> 2) = 0b00110, 按位与就会得到 A = 0b11110. 以此类推 A 的最高位的 1, 会一直覆盖到高 2 位、高 4 位、高 8 位, 直到最低位. 最后这个充满 1 的二进制数会再加 1, 得到一个 0b1000...(N 个 0). 也就是说, 桶数组的大小会是 2^n.
-
RefcountMap 的工作逻辑(代码分析在最后)
- 通过哈希函数计算对象地址的哈希值, 来从 SideTables 中获取对应的 SideTable. 哈希值重复的对象的引用计数存储在同一个 SideTable 里.
- SideTable 使用 find() 方法和重载 [] 运算符的方式, 通过对象地址来确定对象对应的桶.如何确定的呢，是通过查找算法 LookupBucketFor().
- 下面的解释太复杂，面试被问到时最好结合图来进行简单的自述。
查找算法会先对桶的个数进行判断, 如果桶数为 0 则 return false 回上一级调用插入方法. 如果查找算法找到空桶或者墓碑桶, 同样 return false 回上一级调用插入算法, 不过会先记录下找到的桶. 如果找到了对象对应的桶, 只需要对其引用计数 + 1 或者 - 1. 如果引用计数为 0 需要销毁对象, 就将这个桶中的 key 设置为 TombstoneKey..
value_type& FindAndConstruct(const KeyT &Key) {
BucketT *TheBucket;
if (LookupBucketFor(Key, TheBucket))
return *TheBucket;
return *InsertIntoBucket(Key, ValueT(), TheBucket);
}
- 插入算法会先查看可用量, 如果哈希表的可用量(墓碑桶+空桶的数量)小于 1/4, 则需要为表重新开辟更大的空间, 如果表中的空桶位置少于 1/8 (说明墓碑桶过多), 则需要清理表中的墓碑. 以上两种情况下哈希查找算法会很难查找正确位置, 甚至可能会产生死循环, 所以要先处理表, 处理表之后还会重新分配所有桶的位置, 之后重新查找当前对象的可用位置并插入. 如果没有发生以上两种情况, 就直接把新的对象的引用计数放入调用者提供的桶里.
到这里 SideTables 管理引用计数的流程就讲述完毕了, 更详细的部分由于篇幅有限就不说了, 核心就是数据结构和查找算法.
-
图解
枯燥的流程叙述, 我自己都有点写不下去了. 下面画一下查找算法最核心的部分: RefcountMap 的结构
image
首先我们有一个初始化好的, 大小为 9 的桶数组, 同时有 a b c d e 五个对象要使用桶数组, 这里我们假设五个对象都被哈希算法分配到下标 0 的位置里. a 第一个进入, 但 b c d e 由于下标 0 处已经不是空桶, 则需要进行下一步哈希算法来查找合适的位置, 假设这 4 个对象又恰巧都被分配到了下标为 1 的位置, 但只有 b 可以存入. 假设每一次哈希计算都只给下标增加了 1, 以此类推我们能得到:
image
假设这个时候 c 对象被释放了, 之前提到过这个时候会把对应的位置的 key 设置为 TombstoneKey:
image
接下来就体现了墓碑的作用:
- 如果 c 对象销毁后将下标 2 的桶设置为空桶, 此时为 e 对象增加引用计数, 根据哈希算法查找到下标为 2 的桶时, 就会直接插入, 无法为已经在下标为 4 的桶中的 e 增加引用计数.
- 如果此时初始化了一个新的对象 f, 根据哈希算法查找到下标为 2 的桶时发现桶中放置了墓碑, 此时会记录下来下标 2. 接下来继续哈希算法查找位置, 查找到空桶时, 就证明表中没有对象 f, 此时 f 使用记录好的下标 2 的桶而不是查找到的空桶, 就可以利用到已经释放的位置.
-
查找代码
bool LookupBucketFor(const LookupKeyT &Val,
const BucketT *&FoundBucket) const {
...
if (NumBuckets == 0) { //桶数是0
FoundBucket = 0;
return false; //返回 false 回上层调用添加函数
}
...
unsigned BucketNo = getHashValue(Val) & (NumBuckets-1); //将哈希值与数组最大下标按位与
unsigned ProbeAmt = 1; //哈希值重复的对象需要靠它来重新寻找位置
while (1) {
const BucketT *ThisBucket = BucketsPtr + BucketNo; //头指针 + 下标, 类似于数组取值
//找到的桶中的 key 和对象地址相等, 则是找到
if (KeyInfoT::isEqual(Val, ThisBucket->first)) {
FoundBucket = ThisBucket;
return true;
}
//找到的桶中的 key 是空桶占位符, 则表示可插入
if (KeyInfoT::isEqual(ThisBucket->first, EmptyKey)) {
if (FoundTombstone) ThisBucket = FoundTombstone; //如果曾遇到墓碑, 则使用墓碑的位置
FoundBucket = FoundTombstone ? FoundTombstone : ThisBucket;
return false; //找到空占位符, 则表明表中没有已经插入了该对象的桶
}
//如果找到了墓碑
if (KeyInfoT::isEqual(ThisBucket->first, TombstoneKey) && !FoundTombstone)
FoundTombstone = ThisBucket; // 记录下墓碑
//这里涉及到最初定义 typedef objc::DenseMap<DisguisedPtr<objc_object>,size_t,true> RefcountMap, 传入的第三个参数 true
//这个参数代表是否可以清除 0 值, 也就是说这个参数为 true 并且没有墓碑的时候, 会记录下找到的 value 为 0 的桶
if (ZeroValuesArePurgeable &&
ThisBucket->second == 0 && !FoundTombstone)
FoundTombstone = ThisBucket;
//用于计数的 ProbeAmt 如果大于了数组容量, 就会抛出异常
if (ProbeAmt > NumBuckets) {
_objc_fatal("...");
}
BucketNo += ProbeAmt++; //本次哈希计算得出的下表不符合, 则利用 ProbeAmt 寻找下一个下标
BucketNo&= (NumBuckets-1); //得到新的数字和数组下标最大值按位与
}
}
稍微分析一下这里的哈希算法, 苹果通过 getHashValue(Val) 得出了对象地址的哈希值, 又将这个哈希值和 NumBuckets-1 按位与, 这样做的目的是什么呢. 前面说过 NumBuckets 等于 2^n, 假如 NumBuckets = 0b10000, 那 X & 0b1111 就相当于 X % 16. 一个数对数组元素个数取模, 相信大家都能理解用意. BucketNo += ProbeAmt++ 即是在哈希值重复时, 继续向下查找, 并且查找间隔越来越大, 因为如果查找太密集, 可能会占用到其它对象哈希值对应的位置.
-
插入代码
BucketT *InsertIntoBucketImpl(const KeyT &Key, BucketT *TheBucket) {
unsigned NewNumEntries = getNumEntries() + 1; //桶的使用量 +1
unsigned NumBuckets = getNumBuckets(); //桶的总数
if (NewNumEntries*4 >= NumBuckets*3) { //使用量超过 3/4
this->grow(NumBuckets * 2); //数组大小 * 2做参数, grow 中会决定具体数值
//grow 中会重新布置所有桶的位置, 所以将要插入的对象也要重新确定位置
LookupBucketFor(Key, TheBucket);
NumBuckets = getNumBuckets(); //获取最新的数组大小
}
//如果空桶数量少于 1/8, 哈希查找会很难定位到空桶的位置
if (NumBuckets-(NewNumEntries+getNumTombstones()) <= NumBuckets/8) {
//grow 以原大小重新开辟空间, 重新安排桶的位置并能清除墓碑
this->grow(NumBuckets);
LookupBucketFor(Key, TheBucket); //重新布局后将要插入的对象也要重新确定位置
}
assert(TheBucket);
//找到的 BucketT 标记了 EmptyKey, 可以直接使用
if (KeyInfoT::isEqual(TheBucket->first, getEmptyKey())) {
incrementNumEntries(); //桶使用量 +1
}
else if (KeyInfoT::isEqual(TheBucket->first, getTombstoneKey())) { //如果找到的是墓碑
incrementNumEntries(); //桶使用量 +1
decrementNumTombstones(); //墓碑数量 -1
}
else if (ZeroValuesArePurgeable && TheBucket->second == 0) { //找到的位置是 value 为 0 的位置
TheBucket->second.~ValueT(); //测试中这句代码被直接跳过并没有执行, value 还是 0
} else {
// 其它情况, 并没有成员数量的变化(官方注释是 Updating an existing entry.)
}
return TheBucket;
}
网友评论