大佬的技术博客，拜读了一下，理解的七七八八，做一个记录和研究吧。

文章地址： Baby’s First Garbage Collector – journal.stuffwithstuff.com

简易的垃圾回收机制

在计算机运行的过程中，会不断的分配和释放内存。尤其是在一些低级的语言中，内存的分配和释放都需要程序员手动分配。如果不对内存加以分配和管理，就会导致系统资源耗尽，从而发生内存泄露。或者如果错误的释放了正在使用的内存空间，那么又会导致系统崩溃。所以一个合理的垃圾回收机制，可以自动识别并回收不再使用的内存，减轻程序员的负担。

垃圾回收的几种实现

• **引用计数：**为每个对象维护一个引用计数器，初始化为1，每当有一个新的引用指向它，计数器就+1。每当一个引用失效，则将计数器-1。当计数器为0时，说明对象不再被引用，就被垃圾回收器回收了。
• **标记-清除算法：**从一个"根对象"开始，通过引用关系遍历所有可以到达的对象，并将其标记为“存活”。然后回收器再扫描一遍内存空间，找出没有被标记的"垃圾",并将其回收
• **复制算法：**将内存分为两块，分别是“从空间”和“到空间”,再内存分配时，只使用从空间，当从空间被填满时，回收器开始工作，其从根对象开始遍历所有的可达对象，并将其复制到到空间。然后将从空间和到空间的身份进行互换，继续使用从空间进行内存的分配
• **标记-整理算法：**首先从根对象开始遍历所有可达对象，然后移动存活对象到内存空间的另一端，并更新他们的引用。最后回收器，回收所有没有使用的内存碎片。相当于复制算法和标记-清除算法的结合版

这里我们将要使用的垃圾回收机制是 标记-清除算法 ，现在我们需要明确什么是垃圾什么是被使用中的内存空间。

垃圾，指的是之前分配但现在不再使用的内存。使用中的定义则较为复杂，有以下几点：

• 任何处于作用域中的变量所引用的对象都是处于使用中的
• 任何被另一个正在使用中的对象所引用的对象都是处于使用中的（注意理解，这是一条递归规则）

所以我们需要从变量开始遍历对象，以达到所有可以到达的对象，对于不可到达的对象，将其收回。

标记与清除

关键在于对对象的遍历和标记，其原理十分的简单：

• 从根部开始遍历整个对象图。每到达一个对象，就将其上的"标记"设置为true
• 完成后，遍历查找所有的未被设置的对象，并将其删除

对象

垃圾回收器常常被用于各种编程语言中，但是我们这只是演示其功能，我们就只用基本的数据类型，和简单的虚拟机来实现这个功能并创建一些可回收的垃圾。我们用一个枚举变量来标识对象的类型：

typedef enum{
    OBJ_INT,
    OBJ_PAIR
} ObjectType;

这里定义了两种数据类型，一个是数据类型，一个是成对类型。这个对可以是各种组合，可以是一对数，或者一对对对象，或者一个数和一个对对象。这样的话可以实现对象之间的相互引用，这样的话就可以得到一个连续的引用对象的树，我们我们可以定义出它：

typedef struct sObject{
    ObjectType type;
    union{
        // OBJ_INT
        int value;
        
        //OBJ_PAIR
        struct {
            struct sObject * head;
            struct sObject * tail;
        };
    };
} Object;

用type字段来标识值的类型——int/pair，然后用联合体来存储

小小的虚拟机

现在我们可以在虚拟机种使用这个数据类型，我们的虚拟机拥有一个栈，用来存储当前作用域中的变量。

typedef struct {
    Object * stack[STACK_MAX];
    int stackSize;
} VM;

这个结构体中包含两个部分：

• 一个是一个栈空间，用来存储栈中存储的对象的地址
• 一个是当前栈的大小

我们在此基础之上继续编写一个创建并初始化虚拟机的函数：

VM * newVM(){
    VM * vm = malloc(sizeof (VM));
    vm->stackSize = 0;
    return vm;
}

然后我们添加能对虚拟机的栈进行操作的函数：

void push(VM * vm,Object * value){
    if(vm->stackSize > STACK_MAX){
        fprintf(stderr,"Stack overflow");
        exit(0);
    }
    vm->stack[vm->stackSize++] = value;
}
Object * pop(VM * vm){
    if(vm->stackSize < 0){
        fprintf(stderr,"Stack underflow");
        exit(0);
    }
    return vm->stack[--vm->stackSize];
}

我们现在可以存放变量了，那么我们也需要一个创建变量的程序：

Object * newObject(VM * vm,ObjectType type){
    Object * object = malloc(sizeof (Object));
    object->type = type;
    return object;
}

上面的辅助函数实现了对变量内存的分配，和内存类型的设定，我们在此基础上编写指定的数据类型：

void pushInt(VM *vm,int intValue){
    Object* object = newObject(vm,OBJ_INT);
    object->value = intValue;
    push(vm,object);
}
Object * pushPair(VM * vm){
    Object* object = newObject(vm,OBJ_PAIR);
    /*
    原文这里用的是pop，但我发现使用pop会导致栈上数量减少，从而导致在标识环节无法为所有变量打上标记
    所以改成相对索引，才能达到我们想要的效果
    */
    object->tail = vm->stack[vm->stackSize-2];
    object->head = vm->stack[vm->stackSize-1];

    push(vm,object);
    return object;
}

这就是我们的小虚拟机，如果我们真的有一个调用这些函数的解析器和解释器，那么我们手上就真的有一门语言了。如果我们有足够的内存，它甚至可以运行真正的程序。

标记

我们可以在之前的基础上开始我们的垃圾回收，第一个阶段就是标记。我们需要遍历所有可以到达的对象并设置他们的标记位，现在我们需要为之前的Object结构设置一个标记位。且当我们创建一个新的对象时，我们修改newObject()以初始化marked为零。

typedef struct sObject{
    unsigned char marked;
	...
} Object;
Object * newObject(VM * vm,ObjectType type){
    Object * object = malloc(sizeof (Object));
    object->type = type;
    object->marked = 0;
    return object;
}

接下来我们开始准备标记所有可到达的函数，我们先从内存中的变量开始（即遍历栈），不过首先我们需要实现我们的标记函数，然后再遍历标记中调用：

void mark(Object * object){
    object->marked = 1;
}
void markAll(VM * vm){
    for(int i=0;i<vm->stackSize;i++)
        mark(vm->stack[i]);
}

不过这还远远不够，我们标记的对象本身确实是可以到达的，但是我们还有一种成对类型。在这里，我们需要意识到可达性是传递的，我们可以用递归实现这个过程：

void mark(Object * object){
    //这里是用于检测当前对象是否被遍历过，避免两个对象互相引用的情况
    if(object->marked) return;
    object->marked = 1;
    if(object->type == OBJ_PAIR){
        mark(object->head);
        mark(object->tail);
    }
}

现在我们的标记已经完成了，我们可以使用markAll()来实现对内存空间的标记

清除

现在最最最重要的一个环节到了，我们需要遍历我们分配的所有对象，并释放那些未被标记到的对象，但是这里有一个问题，按照定义，未标记的对象对我们而言是不可到达的。

VM已经实现了对对象的引用予以，所以哦我们只将对象的指针存储在变量和成对变量中。一旦对象不再被其他变量所引用，虚拟机就完全失去了它，这就发生了内存泄露。为了解决这个问题，VM需要有自己的对象引用，这些引用和用户可见的语义是不同的，换而言之，我们可以自己跟踪它们。

实现的方式也很简单，我们创建一个链表，用来加入我们分配过的所有对象，我们在Object中完成这个过程：

typedef struct sObject{
    // 用来指向对象列表中的下一个对象
    struct sObject* next;
	...
} Object;

虚拟机则负责跟踪该列表的头部：

typedef struct {
    // 对象列表中的首指针
    Object * firstObject;
	...
} VM;

在newVM()中，我们将头指针初始化为NULL。每次创建对象时，我们都将其添加到列表中：

VM * newVM(){
    VM * vm = malloc(sizeof (VM));
    vm->firstObject = NULL;
    vm->stackSize = 0;
    return vm;
}
Object * newObject(VM * vm,ObjectType type){
    Object * object = malloc(sizeof (Object));
    object->type = type;
    object->marked = 0;
    
    //将声明的变量加入对象列表中
    object->next = vm->firstObject;
    vm->firstObject = object;
    
    return object;
}

现在我们想要删除未标记的对象，只需要遍历列表即可，我们进行清除函数的实现

void sweep(VM * vm){
    Object ** object = &vm->firstObject;
    while(*object){
        if(!(*object)->marked){
            //如果对象未被标记,从链表中移除并释放
            Object * unreached = * object;
            *object = unreached->next;
            free(unreached);
        }else{
            //如果对象被标记了，就移除标记(为之后的GC准备),然后进行下一步
            (*object)->marked = 0;
            object = &(*object)->next;
        }
    }
}

这个代码看起来确实抽象，但是其逻辑实际上十分简单。它遍历整个链表。每当遇到未标记的对象，就释放内存，并将其从链表中移除。执行这个过程中后，我们就删除了所有不可到达的对象。（这里的二重指针真搞人心态，实际上这个object指向当前对象的next地址）。

OK至此为止，我们的垃圾回收器已经完成了，我们将其简单的合并起来：

void GC(VM * vm){
    markAll(vm);
    sweep(vm);
}

但是不止如此，由于内存是有限的，我们需要设置一个对象数量的阈值，一旦超过这个数量就启动GC对内存进行垃圾回收，我们可以通过拓展VM来计算和设置数量：

typedef struct {
    //当前分配的对象的总数
    int numObjects;
    //触发GC的对象的总数
    int maxObjects;
	...
} VM;

然后再VM的创建中初始化他们：

VM * newVM(){
	...
    vm->numObjects = 0;
    vm->maxObjects = INITIAL_GC_THRESHOLD;
    return vm;
}

其中INITIAL_GC_THRESHOLD是第一次启动垃圾回收的对象的数量，这个可以自行调整。

当我们每创建一个对象时，我们都需要增加numObject的数量并进行判断，当其到达最大值时进行垃圾回收：

Object * newObject(VM * vm,ObjectType type){
	...
    //增加对象数量
    vm->numObjects++;
    return object;
}

当然每当我们使用sweep释放一个对象，我们也应该在程序中减少当前对象的数量：

void sweep(VM * vm){
    Object ** object = &vm->firstObject;
    while(*object){
        if(!(*object)->marked){
			...
            free(unreached);
            vm->numObjects--;
        }else{
			...
        }
    }
}

最后我们需要修改GC()来更新最大值：

void GC(VM * vm){
    markAll(vm);
    sweep(vm);
    vm->maxObjects = vm->numObjects*2;
}

每次回收后我们的剩余活动对象数量会动态更新GC的触发值，如果活动对象变多，就会扩大。如果大量的活动对象被释放，就会自动缩小。

演示

本来是想演示一下这个程序怎么使用的，感觉还是算了，因为这个过程并不是很直观，所以就不在此演示了，不过如果能一直看到这里，想必整个过程始终是心里有数的了，就不在此过多概述。

好吧我还是让AI写了一个测试集：

int main() {
    // 创建一个新的虚拟机实例
    VM * vm = newVM();

    // 向虚拟机中压入一些整数
    pushInt(vm, 10);
    pushInt(vm, 20);
    pushInt(vm, 30);

    // 创建一个对子对象，它包含两个整数对象
    Object * pair1 = pushPair(vm);

    // 再次压入一些整数
    pushInt(vm, 40);
    pushInt(vm, 50);

    // 创建另一个对子对象，它包含两个整数对象
    Object * pair2 = pushPair(vm);

    // 弹出一些对象，模拟使用后不再需要的场景
    pop(vm);
    pop(vm);

    // 打印当前虚拟机中的对象数量
    printf("Objects before GC: %d\n", vm->numObjects);

    // 触发垃圾回收
    GC(vm);

    // 打印垃圾回收后的对象数量
    printf("Objects after GC: %d\n", vm->numObjects);

    // 清理虚拟机占用的内存
    sweep(vm); // 再次调用 sweep 以确保所有对象都被释放

    // 释放虚拟机实例占用的内存
    free(vm);

    return 0;
}

这是它的测试集，符合我们想要的结果。

源代码

#include <stdio.h>
#include <stdlib.h>

#define STACK_MAX 256
#define INITIAL_GC_THRESHOLD 10

//数据结构定义
typedef enum{
    OBJ_INT,
    OBJ_PAIR
} ObjectType;

typedef struct sObject{
    // 用来指向对象列表中的下一个对象
    struct sObject* next;
    unsigned char marked;
    ObjectType type;
    union{
        // OBJ_INT
        int value;

        //OBJ_PAIR
        struct {
            struct sObject * head;
            struct sObject * tail;
        };
    };
} Object;

typedef struct {
    //当前分配的对象的总数
    int numObjects;
    //触发GC的对象的总数
    int maxObjects;
    // 对象列表中的首指针
    Object * firstObject;
    Object * stack[STACK_MAX];
    int stackSize;
} VM;

//虚拟机的基本操作与实现
VM * newVM(){
    VM * vm = malloc(sizeof (VM));
    vm->firstObject = NULL;
    vm->stackSize = 0;
    vm->numObjects = 0;
    vm->maxObjects = INITIAL_GC_THRESHOLD;
    return vm;
}

void push(VM * vm,Object * value){
    if(vm->stackSize > STACK_MAX){
        fprintf(stderr,"Stack overflow");
        exit(0);
    }
    vm->stack[vm->stackSize++] = value;
}
Object * pop(VM * vm){
    if(vm->stackSize < 0){
        fprintf(stderr,"Stack underflow");
        exit(0);
    }
    return vm->stack[--vm->stackSize];
}

Object * newObject(VM * vm,ObjectType type){
    Object * object = malloc(sizeof (Object));
    object->type = type;
    object->marked = 0;

    //将声明的变量加入对象列表中
    object->next = vm->firstObject;
    vm->firstObject = object;

    //增加对象数量
    vm->numObjects++;
    return object;
}

void pushInt(VM *vm,int intValue){
    Object* object = newObject(vm,OBJ_INT);
    object->value = intValue;
    push(vm,object);
}
Object * pushPair(VM * vm){
    Object* object = newObject(vm,OBJ_PAIR);
    object->tail = vm->stack[vm->stackSize-2];
    object->head = vm->stack[vm->stackSize-1];

    push(vm,object);
    return object;
}

//垃圾回收机制函数
void mark(Object * object){
    if(object->marked) return;
    object->marked = 1;
    if(object->type == OBJ_PAIR){
        mark(object->head);
        mark(object->tail);
    }
}
void markAll(VM * vm){
    for(int i=0;i<vm->stackSize;i++)
        mark(vm->stack[i]);
}
void sweep(VM * vm){
    Object ** object = &vm->firstObject;
    while(*object){
        if(!(*object)->marked){
            //如果对象未被标记,从链表中移除并释放
            Object * unreached = * object;
            *object = unreached->next;
            free(unreached);
            vm->numObjects--;
        }else{
            //如果对象被标记了，就移除标记(为之后的GC准备),然后进行下一步
            (*object)->marked = 0;
            object = &(*object)->next;
        }
    }
}

void GC(VM * vm){
    markAll(vm);
    sweep(vm);
    vm->maxObjects = vm->numObjects*2;
}

int main(){

}