垃圾回收之引用計數
—— 不管人非笑,不管人毀謗,不管人榮辱,任他功夫有進有退,我只是這致良知的主宰不息,久久自然有得力處
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).