Fuhui

垃圾回收之引用计数


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

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

Reference Counting

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

什么是对象呢?
var neojos int64 = 32
var ptrNeojos *int64 = &neojos

如上所示,我们创建了一个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

counter herader

如下代码,申请地址时,将引用计数初始化为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如何执行清理的呢?

relation

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

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).

GC roots


参考文章:

  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