iOS管理对象内存的数据结构以及操作算法--SideTables、RefcountMap、weak_table_t
fatmouse
7年前
<p>第一次写文章语言表达能力太差。如果有哪里表达的不够清晰可以直接评论回复我,我来加以修改。这篇文章力求脱离语言的特性，咱们多讲结构和算法。即使你不懂iOS开发，不懂Objective-C语言也可以看这篇文章。</p> <p>通过阅读本文你可以了解iOS管理对象内存的数据结构是什么样的，以及操作逻辑。对象的reatin、release、dealloc操作是该通过怎样的算法实现的，weak指针是如何自动变nil的。</p> <h2>一、引用计数的概念</h2> <p>这一部分是写给非iOS工程师的，便于大家了解引用计数、循环引用、弱引用的概念。如果已经了解相关概念可以直接跳过第一部分。</p> <p>大家都知道想要占用一块内存很容易，咱们 new 一个对象就完事儿了。但是什么时候回收？不回收自然是不成的，内存再大也不能完全不回收利用。回收早了的话,真正用到的时候会出现 野指针 问题。回收晚了又浪费宝贵的内存资源。咱们得拿出一套管理内存的方法才成。本文只讨论iOS管理对象内存的 引用计数 法。</p> <p>内存中每一个对象都有一个属于自己的引用计数器。当某个对象A被另一个家伙引用时，A的引用计数器就+1,如果再有一个家伙引用到A，那么A的引用计数就再+1。当其中某个家伙不再引用A了，A的引用计数会-1。直到A的引用计数减到了0,那么就没有人再需要它了，就是时候把它释放掉了。</p> <p>在引用计数中，每一个对象负责维护对象所有引用的计数值。当一个新的引用指向对象时，引用计数器就递增，当去掉一个引用时，引用计数就递减。当引用计数到零时，该对象就将释放占有的资源。</p> <p>采用上述机制看似就可以知道对象在内存中应该何时释放了，但是还有一个 <strong>循环引用</strong> 的问题需要我们解决。</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/8dd56a27d292ceb350aa7abacd053bbb.jpg"></p> <p>现在内存中有两个对象，A和B。</p> <pre> <code class="language-objectivec">A.x = B; B.y = A;</code></pre> <ul> <li>假如A是做视频处理的，B是处理音频的。</li> <li>现在A的引用计数是1(被B.y引用)。</li> <li>现在B的引用计数也是1(被A.x引用)。</li> <li>那么当A处理完它的视频工作以后,发现自己的引用计数是1不是0,他心里想"哦还有人需要我，我还不能被释放。"</li> <li>当B处理完音频操作以后他发现他的引用计数也是1，他心里也觉得"我还不能被释放还有人需要我。"</li> </ul> <p>这样两个对象互相循环引用着对方谁都不会被释放就造成了内存泄露。为了解决这个问题我们来引入 <strong>弱引用</strong> 的概念。</p> <p>弱引用指向要引用的对象，但是不会增加那个对象的引用计数。就像下面这个图这样。 <em>虚线为弱引用</em> (艾玛我画图画的真丑)</p> <p style="text-align:center"><img src="https://simg.open-open.com/show/0683110b9fab46b0159f7748f8631c65.jpg"></p> <p> </p> <pre> <code class="language-objectivec">A.x = B; __weak B.y = A;</code></pre> <p>这里我们让B的y是一个弱引用，它还可以指向A但是不增加A的引用计数。</p> <ul> <li>所以A的引用计数是0，B的引用计数是1(被A.x引用)。</li> <li>当A处理完他的视频操作以后，发现自己的引用计数是0了，ok他可以释放了。</li> <li>随之A.x也被释放了。( <em>A.x是对象A内部的一个变量</em> )</li> <li>A.x被释放了以后B的引用计数就也变成0了。</li> <li>然后B处理完他的音频操作以后也可以释放了。</li> </ul> <p>循环引用的问题解决了。我们不妨思考一下，这套方案还会不会有其它的问题？</p> <p>思考中...</p> <p>还有一个 野指针 的问题等待我们解决。</p> <ul> <li>如果A先处理完他的视频任务之后被释放了。</li> <li>这时候B还在处理中。</li> <li>但是处理过程中B需要访问A (B.y)来获取一些数据。</li> <li>由于A已经被释放了,所以再访问的时候就造成了 野指针 错误。</li> </ul> <p>因此我们还需要一个机制，可以让A释放之后，我再访问所有指向A的指针( <em>比如B.y</em> )的时候都可以友好的得知A已经不存在了,从而避免出错。</p> <p>我们这里假设用一个数组,把所有指向A的弱引用都存起来，然后当A被释放的时候把数组内所有的若引用都设置成nil( <em>相当于其他语言中的NULL</em> )。这样当B再访问B.y的时候就会返回nil。通过判空的方式就可以避免野指针错误了。当然说起来简单，下面我们来看看苹果是如何实现的。</p> <h2>二、抛出问题</h2> <p>前面絮絮叨叨说了一大堆，其实真正现在才抛出本次讨论的问题。</p> <ul> <li>1、如何实现的引用计数管理,控制加一减一和释放？</li> <li>2、为何维护的weak指针防止野指针错误？</li> </ul> <h2>三、数据结构分析( <em>SideTables、RefcountMap、weak_table_t</em> )</h2> <p style="text-align:center"><img src="https://simg.open-open.com/show/e663628c2d2723d550d0e3b08e0e0f71.jpg"></p> <p>咱们先来讨论最顶层的 <strong>SideTables</strong></p> <p style="text-align:center"><img src="https://simg.open-open.com/show/c6f18750f38b1d6ea6b68647087cdfec.jpg"></p> <p>为了管理所有对象的引用计数和weak指针，苹果创建了一个全局的SideTables，虽然名字后面有个"s"不过他其实是一个全局的 <a href="/misc/goto?guid=4959741461044136119" rel="nofollow,noindex">Hash</a> 表，里面的内容装的都是 <strong>SideTable</strong> 结构体而已。它使用对象的 <strong>内存地址当它的key</strong> 。管理引用计数和weak指针就靠它了。</p> <p>因为对象引用计数相关操作应该是 <strong>原子性</strong> 的。不然如果多个线程同时去写一个对象的引用计数，那就会造成数据错乱，失去了内存管理的意义。同时又因为内存中对象的数量是 <strong>非常非常庞大</strong> 的需要非常频繁的操作SideTables，所以 <strong>不</strong> 能对整个Hash表加锁。苹果采用了 <strong>分离锁</strong> 技术。</p> <p>分离锁和分拆锁的区别</p> <p>降低锁竞争的另一种方法是降低线程请求锁的频率。分拆锁 (lock splitting) 和分离锁 (lock striping) 是达到此目的两种方式。相互独立的状态变量，应该使用独立的锁进行保护。有时开发人员会错误地使用一个锁保护所有的状态变量。这些技术减小了锁的粒度，实现了更好的可伸缩性。但是，这些锁需要仔细地分配，以降低发生死锁的危险。</p> <p>如果一个锁守护多个相互独立的状态变量，你可能能够通过分拆锁，使每一个锁守护不同的变量，从而改进可伸缩性。通过这样的改变，使每一个锁被请求的频率都变小了。分拆锁对于中等竞争强度的锁，能够有效地把它们大部分转化为非竞争的锁，使性能和可伸缩性都得到提高。</p> <p>分拆锁有时候可以被扩展，分成若干加锁块的集合，并且它们归属于相互独立的对象，这样的情况就是分离锁。</p> <p>因为是使用对象的内存地址当key所以Hash的分部也很平均。假设Hash表有n个元素，则可以将Hash的冲突减少到n分之一，支持n路的并发写操作。</p> <h2>SideTable</h2> <p>当我们通过SideTables[key]来得到SideTable的时候，SideTable的结构如下:</p> <h2>1,一把自旋锁。 <em>spinlock_t slock;</em></h2> <p>自旋锁 比较适用于锁使用者保持锁时间比较短的情况。正是由于自旋锁使用者一般保持锁时间非常短，因此选择自旋而不是睡眠是非常必要的，自旋锁的效率远高于互斥锁。信号量和读写信号量适合于保持时间较长的情况，它们会导致调用者睡眠，因此只能在进程上下文使用，而自旋锁适合于保持时间非常短的情况，它可以在任何上下文使用。</p> <p>它的作用是在操作引用技术的时候对SideTable加锁，避免数据错误。</p> <p>苹果在对锁的选择上可以说是精益求精。苹果知道对于引用计数的操作其实是非常快的。所以选择了虽然不是那么高级但是确实效率高的自旋锁，我在这里只能说"双击666，老铁们！ 没毛病！"</p> <h2>2,引用计数器 RefcountMap refcnts;</h2> <p>对象具体的引用计数数量是记录在这里的。</p> <p>这里注意RefcountMap其实是个C++的 <a href="/misc/goto?guid=4959741461136625764" rel="nofollow,noindex">Map</a> 。为什么Hash以后还需要个Map？其实苹果采用的是分块化的方法。</p> <p>举个例子</p> <p>假设现在内存中有16个对象。</p> <p>0x0000、0x0001、0x0010、0x0011、0x0100......</p> <p>咱们创建一个SideTables[8]来存放这16个对象，那么查找的时候发生Hash冲突的概率就是八分之一。</p> <p>假设SideTables[0x0000]和SideTables[0x1111]冲突,映射到相同的结果。</p> <pre> <code class="language-objectivec">SideTables[0x0000] == SideTables[0x1111] ==> 都指向同一个SideTable</code></pre> <p>苹果把两个对象的内存管理都放到里同一个SideTable中。你在这个SideTable中需要再次调用 <em>table.refcnts.find(0x0000</em> )或者 <em>table.refcnts.find(0x1111)</em> 来找到他们真正的引用计数。</p> <p>这里是一个分流。内存中对象的数量实在是太庞大了我们通过第一个Hash表只是过滤了第一次，然后我们还需要再通过这个Map才能精确的定位到我们要找的对象的引用计数器。</p> <p><em>引用计数器的存储结构如下</em></p> <p style="text-align:center"><img src="https://simg.open-open.com/show/6a84b12f2a2de9c1cbb173699fcb3090.jpg"></p> <p>引用计数器的数据类型是:</p> <pre> <code class="language-objectivec">typedef __darwin_size_t size_t;</code></pre> <p>再进一步看它的定义其实是 unsigned long ，在32位和64位操作系统中，它分别占用32和64个bit。</p> <p>苹果经常使用 bit mask 技术。这里也不例外。拿32位系统为例的话，可以理解成有32个盒子排成一排横着放在你面前。盒子里可以装0或者1两个数字。我们规定最后边的盒子是低位，左边的盒子是高位。</p> <ul> <li>(1UL<<0)的意思是将一个"1"放到最右侧的盒子里，然后将这个"1"向左移动0位(就是原地不动):0x0000 0000 0000 0000 0000 0000 0000 0001</li> <li>(1UL<<1)的意思是将一个"1"放到最右侧的盒子里,然后将这个"1"向左移动1位:0x0000 0000 0000 0000 0000 0000 0000 0010</li> </ul> <p>下面来分析引用计数器( <em>图中右侧</em> )的结构,从低位到高位。</p> <ul> <li> <p>(1UL<<0) WEAKLY_REFERENCED</p> <p>表示是否有弱引用指向这个对象，如果有的话(值为1)在对象释放的时候需要把所有指向它的弱引用都变成nil( <em>相当于其他语言的NULL</em> )，避免野指针错误。</p> </li> <li> <p>(1UL<<1) DEALLOCATING</p> <p>表示对象是否正在被释放。1正在释放，0没有。</p> </li> <li> <p>REAL COUNT</p> <p>图中REAL COUNT的部分才是对象真正的引用计数存储区。所以咱们说的引用计数加一或者减一，实际上是对整个unsigned long加四或者减四,因为真正的计数是从2^2位开始的。</p> </li> <li> <p>(1UL<<(WORD_BITS-1)) SIDE_TABLE_RC_PINNED</p> <p>其中WORD_BITS在32位和64位系统的时候分别等于32和64。其实这一位没啥具体意义，就是随着对象的引用计数不断变大。如果这一位都变成1了，就表示引用计数已经最大了不能再增加了。</p> </li> </ul> <h2>3,维护weak指针的结构体 weak_table_t weak_table;</h2> <p style="text-align:center"><img src="https://simg.open-open.com/show/e663628c2d2723d550d0e3b08e0e0f71.jpg"></p> <p>上面的RefcountMap refcnts;是一个一层结构，可以通过key直接找到对应的value。而这里是一个两层结构。</p> <p>第一层结构体中包含两个元素。</p> <p>第一个元素 weak_entry_t *weak_entries; 是一个数组,上面的RefcountMap是要通过find(key)来找到精确的元素的。weak_entries则是通过循环遍历来找到对应的entry。</p> <p><em>(上面管理引用计数苹果使用的是Map,这里管理weak指针苹果使用的是数组,有兴趣的朋友可以思考一下为什么苹果会分别采用这两种不同的结构)</em></p> <p>第二个元素num_entries是用来维护保证数组始终有一个合适的size。比如数组中元素的数量超过3/4的时候将数组的大小乘以2。</p> <h3>第二层weak_entry_t的结构包含3个部分</h3> <ul> <li>1,referent:<br> 被指对象的地址。前面循环遍历查找的时候就是判断目标地址是否和他相等。</li> <li>2,referrers<br> 可变数组,里面保存着所有指向这个对象的弱引用的地址。当这个对象被释放的时候，referrers里的所有指针都会被设置成nil。</li> <li>3,inline_referrers<br> 只有4个元素的数组，默认情况下用它来存储弱引用的指针。当大于4个的时候使用referrers来存储指针。</li> </ul> <h2>OK大家来看着图看着伪代码走一遍流程</h2> <h2>1,alloc</h2> <p>这时候其实并不操作SideTable，具体可以参考:</p> <p>深入浅出ARC(上)</p> <p>Objc使用了类似散列表的结构来记录引用计数。并且在初始化的时候设为了一。</p> <h2>2,retain: NSObject.mm line:1402-1417</h2> <pre> <code class="language-objectivec">//1、通过对象内存地址，在SideTables找到对应的SideTable SideTable& table = SideTables()[this]; //2、通过对象内存地址，在refcnts中取出引用计数 size_t& refcntStorage = table.refcnts[this]; //3、判断PINNED位，不为1则+4 if (! (refcntStorage & PINNED)) { refcntStorage += (1UL<<2); }</code></pre> <h2>3,release NSObject.mm line:1524-1551</h2> <pre> <code class="language-objectivec">table.lock(); 引用计数 = table.refcnts.find(this); if (引用计数 == table.refcnts.end()) { //标记对象为正在释放 table.refcnts[this] = SIDE_TABLE_DEALLOCATING; } else if (引用计数 < SIDE_TABLE_DEALLOCATING) { //这里很有意思，当出现小余(1UL<<1) 的情况的时候 //就是前面引用计数位都是0,后面弱引用标记位WEAKLY_REFERENCED可能有弱引用1 //或者没弱引用0 //为了不去影响WEAKLY_REFERENCED的状态 引用计数 |= SIDE_TABLE_DEALLOCATING; } else if ( SIDE_TABLE_RC_PINNED位为0) { 引用计数 -= SIDE_TABLE_RC_ONE; } table.unlock(); 如果做完上述操作后如果需要释放对象，则调用dealloc</code></pre> <h2>4,dealloc NSObject.mm line:1555-1571</h2> <p>dealloc操作也做了大量了逻辑判断和其它处理，咱们这里抛开那些逻辑只讨论下面部分 sidetable_clearDeallocating()</p> <pre> <code class="language-objectivec">SideTable& table = SideTables()[this]; table.lock(); 引用计数 = table.refcnts.find(this); if (引用计数 != table.refcnts.end()) { if (引用计数中SIDE_TABLE_WEAKLY_REFERENCED标志位为1) { weak_clear_no_lock(&table.weak_table, (id)this); } //从refcnts中删除引用计数 table.refcnts.erase(it); } table.unlock();</code></pre> <p>weak_clear_no_lock() 是关键，它才是在对象被销毁的时候处理所有弱引用指针的方法。</p> <pre> <code class="language-objectivec">weak_clear_no_lock objc-weak.mm line:461-504 void weak_clear_no_lock(weak_table_t *weak_table, id referent_id) { //1、拿到被销毁对象的指针 objc_object *referent = (objc_object *)referent_id; //2、通过 指针 在weak_table中查找出对应的entry weak_entry_t *entry = weak_entry_for_referent(weak_table, referent); if (entry == nil) { /// XXX shouldn't happen, but does with mismatched CF/objc //printf("XXX no entry for clear deallocating %p\n", referent); return; } //3、将所有的引用设置成nil weak_referrer_t *referrers; size_t count; if (entry->out_of_line()) { //3.1、如果弱引用超过4个则将referrers数组内的弱引用都置成nil。 referrers = entry->referrers; count = TABLE_SIZE(entry); } else { //3.2、不超过4个则将inline_referrers数组内的弱引用都置成nil referrers = entry->inline_referrers; count = WEAK_INLINE_COUNT; } //循环设置所有的引用为nil for (size_t i = 0; i < count; ++i) { objc_object **referrer = referrers[i]; if (referrer) { if (*referrer == referent) { *referrer = nil; } else if (*referrer) { _objc_inform("__weak variable at %p holds %p instead of %p. " "This is probably incorrect use of " "objc_storeWeak() and objc_loadWeak(). " "Break on objc_weak_error to debug.\n", referrer, (void*)*referrer, (void*)referent); objc_weak_error(); } } } //4、从weak_table中移除entry weak_entry_remove(weak_table, entry); }</code></pre> <p>讲到这里我们就已经把SideTables的操作流程过一遍了，希望大家看的开心。</p> <h2>参考文献</h2> <ul> <li><a href="/misc/goto?guid=4959741461229572189" rel="nofollow,noindex">iOS进阶——iOS（Objective-C）内存管理·二</a></li> <li><a href="/misc/goto?guid=4959741461308262766" rel="nofollow,noindex">深入浅出ARC(上)</a></li> <li><a href="/misc/goto?guid=4959741461404402437" rel="nofollow,noindex">我们的对象会经历什么</a></li> <li><a href="/misc/goto?guid=4958973894466564171" rel="nofollow,noindex">Objective-C 引用计数原理</a></li> <li><a href="/misc/goto?guid=4959741461529710247" rel="nofollow,noindex">神经病院Objective-C Runtime入院第一天——isa和Class</a></li> <li><a href="/misc/goto?guid=4959741461612208451" rel="nofollow,noindex">深入理解Tagged Pointer</a></li> <li><a href="/misc/goto?guid=4959741461693832049" rel="nofollow,noindex">Why is weak_table_t a member of SideTable in Objective-C runtime?</a></li> <li><a href="/misc/goto?guid=4959741461786015058" rel="nofollow,noindex">How can the Objective-C runtime know whether a weakly referenced object is still alive?</a></li> </ul> <p> </p> <p>来自：http://www.jianshu.com/p/ef6d9bf8fe59</p> <p> </p>