美文网首页
引用计数RefcountMap工作原理

引用计数RefcountMap工作原理

作者: 萨缪 | 来源:发表于2019-10-09 20:02 被阅读0次

前言

最近偶尔出去面试了解一下现在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;
  ...
}

比较重要的成员中我列举了这几个:

  1. ZeroValuesArePurgeable 默认值是 false, 但 RefcountMap 指定其初始化为 true. 这个成员标记是否可以使用值为 0 (引用计数为 1) 的桶. 因为空桶存的初始值就是 0, 所以值为 0 的桶和空桶没什么区别. 如果允许使用值为 0 的桶, 查找桶时如果没有找到对象对应的桶, 也没有找到墓碑桶, 就会优先使用值为 0 的桶.
  2. Buckets 指针管理一段连续内存空间, 也就是数组, 数组成员是 BucketT 类型的对象, 我们这里将 BucketT 对象称为桶(实际上这个数组才应该叫桶, 苹果把数组中的元素称为桶应该是为了形象一些, 而不是哈希桶中的桶的意思). 桶数组在申请空间后, 会进行初始化, 在所有位置上都放上空桶(桶的 key 为 EmptyKey 时是空桶), 之后对引用计数的操作, 都要依赖于桶.
    桶的数据类型实际上是 std::pair, 类似于 swift 中的元祖类型, 就是将对象地址和对象的引用计数(这里的引用计数类似于 isa, 也是使用其中的几个 bit 来保存引用计数, 留出几个 bit 来做其它标记位)组合成一个数据类型.
typedef std::pair<KeyT, ValueT> BucketT;
  1. NumEntries 记录数组中已使用的非空的桶的个数.
  2. NumTombstones, Tombstone 直译为墓碑, 当一个对象的引用计数为0, 要从桶中取出时, 其所处的位置会被标记为 Tombstone. NumTombstones 就是数组中的墓碑的个数. 后面会介绍到墓碑的作用.
  3. 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 的工作逻辑(代码分析在最后)

  1. 通过哈希函数计算对象地址的哈希值, 来从 SideTables 中获取对应的 SideTable. 哈希值重复的对象的引用计数存储在同一个 SideTable 里.
  2. SideTable 使用 find() 方法和重载 [] 运算符的方式, 通过对象地址来确定对象对应的桶.如何确定的呢，是通过查找算法 LookupBucketFor().
  3. 下面的解释太复杂，面试被问到时最好结合图来进行简单的自述。
    查找算法会先对桶的个数进行判断, 如果桶数为 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. 插入算法会先查看可用量, 如果哈希表的可用量(墓碑桶+空桶的数量)小于 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

接下来就体现了墓碑的作用:

  1. 如果 c 对象销毁后将下标 2 的桶设置为空桶, 此时为 e 对象增加引用计数, 根据哈希算法查找到下标为 2 的桶时, 就会直接插入, 无法为已经在下标为 4 的桶中的 e 增加引用计数.
  2. 如果此时初始化了一个新的对象 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;
  }

相关文章

网友评论

      本文标题：引用计数RefcountMap工作原理

      本文链接：https://www.haomeiwen.com/subject/bjzgpctx.html

      延伸阅读

      深度阅读

      • 您也可以注册成为美文阅读网的作者，发表您的原创作品、分享您的心情！

      栏目导航

      热点阅读

      关于我们|服务条款|联系我们|引用计数RefcountMap工作原理|投稿指南|网站地图|RSS订阅|排版工具|手机版

      提供经典美文摘抄,优美散文欣赏,现代诗歌精选,短篇小说,心情随笔,表白情书范文,故事会在线阅读欣赏

      Copyright © 2014-2023 Haomeiwen.com All Rights Reserved. 好美文阅读网 版权所有

      备案信息：桂公网安备 45052102000051号 · 桂ICP备13007215号-3

      本站所收录作品、热点评论等信息部分来源互联网，目的只是为了系统归纳学习和传递资讯

      所有作品版权归原创作者所有，与本站立场无关，如不慎侵犯了你的权益，请联系我们告知，我们将做删除处理！