垃圾回收之引用计数

思来想去，决定总结一下垃圾回收机制。引用计数与我结缘最早，也比较简单、基础，遂决定从引用计数入手。

—— 不管人非笑，不管人毁谤，不管人荣辱，任他功夫有进有退，我只是这致良知的主宰不息，久久自然有得力处

Reference Counting

对象在创建时保存一个自身被引用的计数，初始值为1。每次被新的变量引用，该值加1。相反，则减去1。当该值等于0时，占用空间被系统回收。

什么是对象呢？

var neojos int64 = 32
var ptrNeojos *int64 = &name

如上所示，我们创建了一个int64类型的object，命名为neojos。程序中对该object的操作都是通过使用neojos来实现的。而ptrNeojos其实又创建了一个*int64类型的object，但它的值保存的是neojos的地址。

对于ptrNeojos来说，它的生命周期跟普通变量的生命周期没有区别。唯一区别的是，当它生命周期结束后，ptrNeojos会被垃圾回收，而底层指向的object却不会。

如何计数呢？

Object * obj1 = new Object(); // RefCount(obj1) starts at 1
Object * obj2 = obj1;         // RefCount(obj1) incremented to 2 as new reference is added
Object * obj3 = new Object(); 

obj2->SomeMethod();
obj2 = NULL;                  // RefCount(obj1) decremented to 1 as ref goes away
obj1 = obj3;                  // RefCount(obj1) decremented to 0 and can be collected

obj1指向了一个匿名对象，为了方便，我们叫anonymousObj。上述代码展示了anonymousObj从创建到被垃圾回收的整个过程。垃圾回收对象的内存空间，上述过程中obj1对象的地址不会发生改变，只是底层引用的对象发生了变化。

下面的例子，用于测试ptrName代表的对象在赋值过程中不会发生变化。

func TestCase2(t *testing.T) {
    var name int64 = 32

    var ptrName *int64 = &name
    t.Log(&ptrName)        //0xc42000e078

    ptrName = nil
    t.Log(&ptrName)        //0xc42000e078
}

如何实现

基于不同的语言会有不同的实现方式，但思路是相通的。

存储结构和申请空间

创建对象的时候，申请额外的空间用于存储引用计数，同时对外隐藏该空间的存在。如下图，Header部分就用于存储引用计数。所以，程序返回的指针实际是ActualData的首地址，调用者完全意识不到header的存在，而GC执行的时候却可以通过对象的地址访问Header。

如下代码，申请地址时，将引用计数初始化为1。同时，返回ActualData的指针地址。后续的引用计数更新，释放对象空间都通过判断Header来处理。

//Header结构
struct MemHeader
{
    UINT32 refCount;
};

// cb is the number of bytes to be allocated
PVOID GC_Alloc(size_t cb)
{
    // allocate MemHeader + cb but cast it to MemHeader
    MemHeader* pHdr = (MemHeader*)PlatformAlloc(MEMHEADERSIZE + cb);
    if (pHdr == NULL)
        return NULL;

    // set the initial refCount
    pHdr->refCount = 1;

    // increment the pointer by the size of MemHeader 
    // and make it point to the start of the actual data
    ++pHdr;

    return (PVOID)pHdr;
}

//访问Header头
inline MemHeader * GetHeader(PVOID pMem)
{
    return ((MemHeader*)pMem) - 1;
}

基类实现

对象可以意识到引用计数机制的存在，明确的增加或减少引用计数。这种情况适用于：调用者手动释放空间的场合。那么，所有对象需要继承一个通用的基类，来实现这部分计数逻辑。

class ReferenceCount
{
    int count;
 
    ReferenceCount()
    {
        count = 1; //start at 1 as creation implies at least once reference is being made
    }
 
    void increment()
    {
        count++;
    }
 
    void decrement()
    {
        count--;
        if( count == 0 )
            delete this;
    }
};
 
//any reference counted object simply derives from the above type
class MyType : public ReferenceCount { ... }

对象引用关系

对象与对象之间存在相互调用，当其中一个对象的引用计数减为0时，该对象“引用链”上其他对象的引用计数都需要被更新。GC如何执行清理的呢？

当object1释放object3的引用时，object3和object5的引用计数都需要被更新，而这是一个递归检查、更新的过程。

VOID GC_ReleaseRef(PVOID pMem)
{
    if (pMem == NULL) return;
    MemHeader *pHdr = GetHeader(pMem);
    --(pHdr->refCount);
    if (pHdr->refCount == 0)
    {
        foreach(PVOID pChild in Get_Child(pHdr)) 
            GC_ReleaseRef(pChild);
        PlatformFree(pHdr);
    }
}

GC扫描

除了自动回收垃圾外，GC的扫描是从哪里开始的？拿Java来解释，GC roots就是Java中的ClassLoader。

ClassLoader

After that when we try to use a Class, Java ClassLoader loads that class into memory

ClassLoader按需将使用到的class加载到内存，熟悉PHP的可以跟Laravel Container做类比。

GC roots

In Java, there are special objects called Garbage Collection Roots (GC roots). They serve as a root objects for Garbage Collection marking mechanism (see picture).

参考文章：

1. Java ClassLoader
2. What are GC roots for classes?
3. Garbage Collection in Java
4. Garbage Collection vs Automatic Reference Counting
5. What’s an object? What’s a variable?
6. What is reference counting?
7. Back To Basics: Reference Counting Garbage Collection

有疑问加站长微信联系（非本文作者）