C++下垃圾回收器的实现

C++下的垃圾回收机制可能会在下个版本加入，我只是想通过实例，分析垃圾回收器的内部机制，深入了解以后，在以后
的项目中，就可以对是否需要垃圾回收功能做出准确的判断。

它是否影响性能，能影响多少，回收的代价等等问题就会显得更加明确。

对C++下垃圾回收的讨论很多，有兴趣可以看看这里和这里。至于实现，惠普的垃圾回收器是一个产品化的开源项目，而且已经被很多项目使用。但是他的具体实现总是让人感觉不是很可靠。云风是一个简单的回收器，有人对其源码进行研究，有兴趣可以看这里，它没有内存紧缩功能。

首先，说说垃圾回收的目标，也就是需求。
1. 不能有内存泄漏（最基本的要求）。
2. 能自动回收无用内存（当然需要解决循环引用问题）。
3. 能整理内存（内存紧缩），程序运行时间长了，总会有小块内存无法被重复使用。

先说说前两条需求，程序中的所有已分配内存都应该有其对应的指针指向它，如果一块内存没有任何指针指向它，那么我们说这块内存被泄漏了（这里内存泄漏的定义和Java不太一样）。

简单的表述就是无用对象且不可达。

什么叫可达？可达表示从哪里为起点可达？这里要引出一个叫根集的概念：在程序运行的任意状态，寄存器（考虑多核CPU在多线程下），程序栈，和静态数据段中所有的指针的集合叫根集。
所以可达指的是这块内存从根集出发，可以找到一个指向它的指针，不可达就是找不到。

要实现垃圾回收器，首先要能在程序的任意状态，找到根集。其次是要能管理所有堆上的内存。当从根集扫描发现一块不可达内存时，这块内存就应该被收集。

注意上图：黄色的指针表示它是根集，红色的指针则不是根集。
要回收内存，首先要知道内存的地址，所以上图中4块内存的地址是必须知道的。

看看要回收内存，需要知道那些信息吧：

根集和内存块集。收集前，先从根集顺着黑色的箭头开始扫描，对所以扫描到的内存块做个标记，然后从内存块集中检查所有内存块，如果被做了标记，就保留，如果没有做标记，就收集。

怎么得到根集呢？对于像Java，C#之类的语言，它的指针是受到虚拟机或者Framework控制的，但是在C++中，原生的指针（raw pointer）是不受控制的，而且Scott Meyers([More] Effective C++)的作者,
Andrew Koenig夫妇(C++ 沉思录）的作者，这些大牛们多次劝告，不要使用原生指针。

所以以前有auto_ptr, 现在有shared_ptr问世。为了得到根集，我也将原生指针进行包装，只不过不用于所有权管理，也不用于引用计数，而是用于得到根集。
首先看看指针的定义：

class pointer_base
{
public:
    virtual ~pointer_base()
    {}

    virtual void* get_ptr() const = 0;
    virtual void set_ptr(const void *p) = 0;
};

template <class _T>
class pointer : public pointer_base
{
public:
    pointer()
        : p(NULL)
    {
        

gc_register(*this);
    }

    pointer(_T* t)
        : p(t)
    {
        gc_register(*this);
    }

    _T& operator*() const
    {
        return *p;
    }

    _T* operator->() const
    {
        return p;
    }
private:
    _T *p;
};

 

注意pointer的构造函数，它将自己注册到根集中去。

再看看根集：

std::list<pointer_base *> gc_root_set;

gc_register 函数也就是做了一个push_back。

有人会问，那要是出现这种情况：

class A
{
    //
};

class B
{
    pointer<A> pA;
};

void main()
{
    B* pB = new B();
}

 

那不是pB->pA在堆上吗？不应该属于根集呀。
这个问题就要和内存块管理扯上关系啦，下篇再说
整个垃圾回收器已经写完并简单的测试代码在这里,有兴趣可以看看并测试。