一个简单开发的垃圾收集器工作原理详解

一.工作原理

      最近在实现一个阉割版的函数式语言（编译器已完成，虚拟机在憋的过程中，之后会发帖），希望内存管理的部分由虚拟机来完成，而不是由客户自己折腾，这样显然可以降低客户使用这门语言的难度，比如不需要担心内存泄漏，减少内存运用不当的bug，这里客户只管放心地一直申请内存就行，不再需要手工释放内存（如果让客户选择是否自己释放都行，会提高难度，起码得做个平衡树放着这些申请的内存地址便于查找，这里先偷懒）。

      首先讲一下虚拟机的内存管理机制。众所周知，频繁地申请和释放内存会大大降低效率，所以我们可以在虚拟机运行一开始的时候就统一申请内存，虚拟机运行结束在统一释放内存。如果中间有某些内存已经不需要再次使用，继续占着茅坑不拉屎是非常不道德的，于是需要对此做点事情，造成内存已释放的“假象”。这里强调一下，虚拟机知道哪块内存正在使用、哪块内存不需再用就行了，实际上程序吃的内存还是没有减少。声明一下，下文提到的申请和释放内存讲的都是“假象”。

      如何实现这个机制呢？本能地想到引用计数，记录下到底有多少个对象引用这块内存，如果引用计数为0就释放内存。后来才意识到引用计数是行不通的，万一有环形数据结构（如一个对象自己引用自己），显然会造成内存泄漏。然后就动了对象池的念头，如果用这种方法，需要很多个对象池，包括虚拟机运行中的表、堆栈里的各种数据类型的对象，这么多个对象池看着很碍眼，于是还是决定实现垃圾收集器。

      下面介绍垃圾收集器的工作机制。内存单元并不会在变成垃圾的同时就立刻被回收，而是保持不可到达的状态，直到内存被耗尽或者内存分配达到某个阈值，用户程序会被挂起，此时才进行垃圾收集，也就是先标记正在使用的内存，再清除垃圾，即内存回收。垃圾收集器回收足够的内存后，用户程序就可以继续工作。如国无法恢复足够多的内存，则抛出异常。

1. 标记

      标记是为了识别垃圾，依靠对所有存活对象进行一次全局遍历来确定哪些内存可以回收。这个遍历从根出发（运行时的栈和表），利用相互引用关系，标记所有存活对象，除此之外，其他内存就是垃圾。这里强调下，标记并不会沿着已经被标记的单元追踪下去，这确保了标记能够终止。

2. 缩并

      用户程序在堆上分配多种大小不同的对象，经过标记，我们发现，堆空间变得破碎，如果不扩展堆，也许就无法分配一个大型对象，因为找不到一个足够大的“空洞”容纳新的对象 ，即使空闲内存的总量是足够的。还有另外一个问题，经过若干个垃圾收集周期后，分配一个小型对象要采用什么算法？首次匹配代价低点，但是会产生更多碎片；最佳匹配产生的碎片少了，但是耗费的代价高。这显然提高了内存分配的难度。基于以上的讨论，对内存进行缩并就是自然的事了。即把空闲的内存扫到一起，也把正在使用的内存扫到一起，这样就把堆空间分成了两部分。这样空闲的内存连续了，也就解决了内存碎片的问题。当为新对象分配内存时，再也不用寻找合适的“空洞”，只需把记录空闲内存的基点后移，大大提高了内存分配的效率。

3. 分代收集

      我们先有这样的假设：大多数对象都在年轻的时候死亡，而越老的对象则越不可能死亡。在垃圾收集的过程中，用户程序是被挂起的，如果对整个堆都进行垃圾收集，显然用户程序等待的时间是很长的。如果我们能把工作集中在回收最有可能是垃圾的对象上，就能让内存回收的效率更高，对用户程序的影响更小。

      基于以上假设，我们需要区分年轻对象和年老对象。把对象按年龄分到堆中的不同区域里，其中最年轻的分代会被频繁地收集，而较老的分代则收集频率会低得多。对象首先在最年轻的分代里分配，如果它们的寿命足够长，能够在足够多次收集中存活下来（这里就是一次），则会被提升到较老的分代里。这里注意一下，较老的对象可能引用了较年轻的对象，我们仍需对此进行扫描，但是我们现在不必把年老的对象从一个半区复制到另一个半区了，将垃圾收集器的努力集中在回收最年轻的分代所占据的内存上，节省了用户等待的时间。
二．具体实现之一

　　之前已经介绍过垃圾收集器的工作机制了，这篇文章主要针对垃圾收集器的总体设计。

容易看到，垃圾收集器分成两个区域，SmallObjectHeap存放小型对象，LargeObjectHeap存放大型对象。SmallObjectHeap会进行内存缩并，而对LargeObjectHeap进行内存缩并显然不合适，移动大型对象会花很大代价。这里强调下，SamllObjectHeap和LargeObjectHeap各自是一个连续的内存区域，其中三个分代只是做一下标志而已。

        class GC
        {
        private:
            static const int LARGE_OBJECT_SIZE;                //大型对象最小大小
            static const int SMALL_OBJECT_SIZE;                //小型对象最小大小

            SmallObjectHeap* SmallHeap;                        //小型对象堆
            LargeObjectHeap* LargeHeap;                        //大型对象堆

            Pool<ObjectHandle> ObjectHandlePool;

            bool IsLargeObject(const int size)const;        //判断是否为大型对象

        public:
            void Clear();                                    //释放GC申请所有内存
            ObjectHandle* Alloc(const int size);            //分配size大小的对象
            void Collect(const int generationIndex=0);        //对LarObjectHeap和SmallObjectHeap中第0-generationIndex分代进行垃圾收集
            void Mark(ObjectHandle* handle);                //标记对象handle，表示其为存活对象

接下来详细介绍下SmallObjectHeap。

        class Generation            //分代
        {
        public:
            int Start;                //开始位置
            int Size;                //该分代大小
            int AllocateIndex;        //该分代空闲内存起始位置
            int Free;                //该分代空闲内存大小

            void Init(const int start, const int size);
            bool CanAlloc(const int size)const;            //该分代的空闲内存是否足以分配size大小的对象
            void AfterAlloc(const int size);            //分配size大小的对象后更新该分代信息
        };

        class SmallObjectHeap                        //小型对象堆
        {
        private:
            static const int TOTAL;
            int Total;                                //真实内存区域Data的大小
            int Free;                                //空闲内存的大小

            char* Data;                                //真实内存区域
            const int GenerationCount;                //分多少代
            Generation* Generations;                //各分代的详细信息
            ObjectHandleContainer ObjectHandles;    //记录所有分配出去的ObjectHandle，便于垃圾收集的时候更新信息

        public:
            void Clear();                                                                    //释放该小型对象堆申请的所有内存
            ObjectHandle* Alloc(const int size, Pool<ObjectHandle>& ObjectHandlePool);        //分配size大小的对象
            void Collect(const int generationIndex=0);                                        //对0-generationIndex代进行垃圾收集
        };

下面我们看下之前一直提到的ObjectHandle。垃圾收集器对外提供的都是ObjectHandle，所有的工作都只能建立在ObjectHandle上而不是针对一个char*，包括标记对象、回收内存等。这里稍微提一下用ObjectHandle而非直接对char*进行操作的好处。我们知道内存缩并的时候，是需要把存活对象的内存里的数据复制到别的地方去的，意味着对象所在地内存区域会有变动，而如果这里的垃圾收集器我并不希望有内存缩并这个动作，这意味着对象真实存在的内存区域并不会改变，于是char*是死的，并不会跑，如果我一律都用ObjectHandle.GetPointer()来获得对象真实的内存区域，那么一切文章都可以封装在ObjectHandle里，而没有必要垃圾收集机制的改变就大幅度地变动代码。

        enum ObjectHandleType                   //区别对象是否被外部指针引用
        {
            handleNORMAL,
            handlePINNED                              //外部指针指向的对象不可被收集
        };

        class ObjectHandle
        {
        private:
            char* Data;                                    //内存区域
        public:
            ObjectHandleType Type;                //Handle类型

            int Start;                                        //开始位置
            int Size;                                         //对象大小
            bool Marked;                                 //对象是否被标记

            void Init(char* data, const int start, const int size, const ObjectHandleType type=handleNORMAL);
            void Move(const int index);            //将对象移动到指定的位置，参数为开始位置
            char* GetPointer();                         //返回对象所在地内存区域，即在Data的基础上后移Start个位置
        };

三．具体实现之二

      已经讲述过垃圾收集器的工作机制和总体实现了，这篇文章主要针对标记和内存缩并进行具体阐述。

1. 标记

      我们知道，标记存活对象是为了识别出垃圾，依靠对所有存活对象进行一次全局遍历来确定哪些内存可以回收。这个遍历从根出发，利用相互引用关系，标记所有存活对象，除此之外，其他内存就是垃圾。这里强调下，标记并不会沿着已经被标记的单元追踪下去，这确保了标记能够终止。

      对于对象间的相互引用关系，这针对不同的对象类型又有所不同。对象类型指的是ObjectHandle可被解释为整型、布尔型、字符串、数组等等。显然，基本数据类型比如整型，只需要看看自己是否被标记就可以了，但是对于复合数据类型，比如数组，必须再继续跟踪每个数组元素到底有没有被标记。于是我们发现，针对不同的对象类型，遍历方法是不一样的，所以想办法把不同对象类型的遍历方法分开来写，万一需求增加了，想再增加别的对象类型，比如结构体，只需要增加代码，就没有必要因此大幅度地修改代码了。

      上文提到，我们会为每个对象类型写自己的遍历方法，这里我们将这件事封装在Walker里。Walker提供接口，具体的对象类型可以继承并实现之，这里用整型对象类型，即IntWalker举例。

        class Walker
        {
        public:
            virtual void WalkObject(ObjectHandle* handle)const=0;
        };

        class IntWalker : public Walker
        {
        public:
            virtual void WalkObject(ObjectHandle* handle)const
            {
                handle->Marked=true;
            }
        };
      自然地，我们还需要根据ObjectHandle的对象类型来选择不同的Walker，这里把它封装在WalkerSelector里。
        enum ObjectType        //对象类型
        {
            objectINT,
            objectBOOL,
            objectSTRING,
            objectARRAY,
            objectSTRUCT
        };

        class WalkerSelector
        {
        private:
            static IntWalker* intWalker;
        public:
            static Walker* GetWalker(ObjectHandle* handle)
        };

        Walker* WalkerSelector::GetWalker(ObjectHandle* handle)
        {
            ObjectType type=Describer::GetType(handle);
            switch(type)
            {
            case objectINT:
                return intWalker;
            default:
                throw "handle类型出错";
            }
        }

      GC里Mark的实现就显得非常容易了。  

        void GC::Mark(ObjectHandle* handle)
        {
            WalkerSelector::GetWalker(handle)->WalkObject(handle);
        }

2. 内存缩并

      内存缩并可以解决内存碎片的问题，垃圾收集器的工作机制中已经提过。本文主要针对其具体算法和实现。这里我们先明确一下，如果是对第n代进行垃圾收集，那么意味着第0-n代都会进行操作。假设我们只有3代，如果是对第2代进行垃圾收集，那么存活对象就不需要进行提升；反之，如果是第0代或第1代的存活对象，则需要对其进行提升。所以我们的讨论分两种情况。（下图红色区域表示存活对象，蓝色区域表示非存活对象，绿色区域表示已清扫到一起的空闲内存）

      对第0代或第1代进行垃圾收集：只需把存活对象提升到更高一代的空闲内存即可。

      对第2代进行垃圾收集：我们需要记录FreeIndex和FreeCount，分别表示空闲内存的起始位置和大小。在扫描过程中，我们需要把存活对象往前移，把空闲内存往后移，具体如下图：

      代码实现如下：
        void SmallObjectHeap::Collect(const int generationIndex)
        {
            for (int i=generationIndex; i>=0; i--)
            {
                int count=ObjectHandles.ObjectHandleCount[i];
                ObjectHandles.Clear(i);
                if (i==GenerationCount-1)    //对第2代进行收集
                {
                    int FreeIndex=Generations[i].Start;        //空闲内存起始位置
                    int FreeCount=0;    //空闲内存大小
                    for (int j=0; j<count; j++)
                    {
                        ObjectHandle* handle=ObjectHandles.Data[i][j];
                        if (handle->Marked || handle->Type==handlePINNED)
                        {
                            if (FreeCount) handle->Move(FreeIndex);
                            FreeIndex+=handle->Size;
                            ObjectHandles.Add(handle, i);
                        }
                        else FreeCount+=handle->Size;
                    }
                }
                else    //对第0代或第1代进行收集
                {
                    int FreeIndex=Generations[i+1].Start;
                    for (int j=0; j<count; j++)
                    {
                        ObjectHandle* handle=ObjectHandles.Data[i][j];
                        if (handle->Marked || handle->Type==handlePINNED)
                        {
                            handle->Move(FreeIndex);
                            FreeIndex+=handle->Size;
                            ObjectHandles.Add(handle, i);
                        }
                    }
                }
            }
        }

Logo
华为开发者空间

华为开发者空间，是为全球开发者打造的专属开发空间，汇聚了华为优质开发资源及工具，致力于让每一位开发者拥有一台云主机，基于华为根生态开发、创新。

更多推荐

cover

2024华为开发者盛典，海外开发者代表团走进华为

avatar 华为开发者空间
cover

华为“行业AI应用创新孵化营”走进中国医科大学，共探人才培养新模式

avatar 华为开发者空间
cover

拦截烂SQL，解读GaussDB(DWS)查询过滤器过滤规则原理

avatar 华为开发者空间