使用C++实现一个Mark-Sweep的GC

enum class ObjectType {
    OBJ_INT,
    OBJ_PAIR
};

class Object {
public:
    ObjectType type;
    unsigned char marked;

    /* The next object in the linked list of heap allocated objects. */
    struct Object *next;

    union {
        /* OBJ_INT */
        int value;

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

    void static objectPrint(Object *object);
};

void Object::objectPrint(Object *object) {
    switch (object->type) {
        case ObjectType::OBJ_INT:
            std::cout << object->value << std::endl;
            break;

        case ObjectType::OBJ_PAIR:
            printf("(");
            Object::objectPrint(object->head);
            printf(", ");
            Object::objectPrint(object->tail);
            printf(")");
            break;
    }
}

#define STACK_MAX 256
#define INITIAL_GC_THRESHOLD 8

class VM {
public:
    Object *stack[STACK_MAX]{};
    int stackSize;

    /* The first object in the linked list of all objects on the heap. */
    Object *firstObject;

    /* The total number of currently allocated objects. */
    int numObjects;

    /* The number of objects required to trigger a GC. */
    int maxObjects;

    VM();

    ~VM();

    void static assert(int condition, const char *message);

    void push(Object *value);

    Object *pop();

    void mark(Object *object);

    void markAll();

    void sweep();

    void gc();

    Object *newObject(ObjectType type);

    void pushInt(int intValue);

    Object *pushPair();

    void freeVM();
};

#define STACK_MAX 256
class VM {
public:
    Object *stack[STACK_MAX]{};
    int stackSize;
    ……
};

VM::VM() {
    std::cout << "vm started!" << std::endl;
    this->stackSize = 0;
    this->firstObject = nullptr;
    this->numObjects = 0;
    this->maxObjects = INITIAL_GC_THRESHOLD;
}

VM::~VM() {
    std::cout << "all objects cleaned, vm closed!" << std::endl;
}

void VM::assert(int condition, const char *message) {
    if (!condition) {
        std::cout << message << std::endl;
        exit(1);
    }
}

void VM::push(Object *value) {
    assert(this->stackSize < STACK_MAX, "Stack overflow!");
    this->stack[this->stackSize++] = value;
}

Object *VM::pop() {
    assert(this->stackSize > 0, "Stack underflow!");
    return this->stack[--this->stackSize];
}

Object *VM::newObject(ObjectType type) {
    if (this->numObjects == this->maxObjects) gc();

    auto *object = new Object();
    object->type = type;
    object->next = this->firstObject;
    this->firstObject = object;
    object->marked = 0;

    this->numObjects++;

    return object;
}

void VM::pushInt(int intValue) {
    Object *object = newObject(ObjectType::OBJ_INT);
    object->value = intValue;

    push(object);
}

Object *VM::pushPair() {
    Object *object = newObject(ObjectType::OBJ_PAIR);
    object->tail = pop();
    object->head = pop();

    push(object);
    return object;
}

void VM::mark(Object *object) {
    /* If already marked, we're done. Check this first to avoid recursively
       on cycles in the object graph. */
    if (object->marked) return;

    object->marked = 1;

    if (object->type == ObjectType::OBJ_PAIR) {
        mark(object->head);
        mark(object->tail);
    }
}

void VM::markAll() {
    for (int i = 0; i < this->stackSize; i++) {
        mark(this->stack[i]);
    }
}

void VM::sweep() {
    Object **object = &this->firstObject;
    while (*object) {
        if (!(*object)->marked) {
            /* This object wasn't reached, so remove it from the list and free it. */
            Object *unreached = *object;

            *object = unreached->next;
            delete (unreached);

            this->numObjects--;
        } else {
            /* This object was reached, so unmark it (for the next GC) and move on to
             the next. */
            (*object)->marked = 0;
            object = &(*object)->next;
        }
    }
}

void VM::gc() {
    int i_numObjects = this->numObjects;

    markAll();
    sweep();

    this->maxObjects = this->numObjects == 0 ? INITIAL_GC_THRESHOLD : this->numObjects * 2;

    printf("Collected %d objects, %d remaining.\n", i_numObjects - this->numObjects,
           this->numObjects);
}

void test1() {
    printf("Test 1: Objects on stack are preserved.\n");
    auto vm = new VM();
    vm->pushInt(1);
    vm->pushInt(2);

    vm->gc();
    VM::assert(vm->numObjects == 2, "Should have preserved objects.");
    vm->freeVM();
    delete (vm);
}

void test2() {
    printf("Test 2: Unreached objects are collected.\n");
    auto vm = new VM();
    vm->pushInt(1);
    vm->pushInt(2);
    vm->pop();
    vm->pop();

    vm->gc();
    VM::assert(vm->numObjects == 0, "Should have collected objects.");
    vm->freeVM();
    delete (vm);
}

void test3() {
    printf("Test 3: Reach nested objects.\n");
    auto vm = new VM();
    vm->pushInt(1);
    vm->pushInt(2);
    vm->pushPair();
    vm->pushInt(3);
    vm->pushInt(4);
    vm->pushPair();
    vm->pushPair();

    vm->gc();
    VM::assert(vm->numObjects == 7, "Should have reached objects.");
    vm->freeVM();
    delete (vm);
}

void test4() {
    printf("Test 4: Handle cycles.\n");
    auto vm = new VM();
    vm->pushInt(1);
    vm->pushInt(2);
    Object *a = vm->pushPair();
    vm->pushInt(3);
    vm->pushInt(4);
    Object *b = vm->pushPair();

    /* Set up a cycle, and also make 2 and 4 unreachable and collectible. */
    a->tail = b;
    b->tail = a;

    vm->gc();
    VM::assert(vm->numObjects == 4, "Should have collected objects.");
    vm->freeVM();
    delete (vm);
}

void perfTest() {
    printf("Performance Test.\n");
    auto vm = new VM();

    for (int i = 0; i < 1000; i++) {
        for (int j = 0; j < 20; j++) {
            vm->pushInt(i);
        }

        for (int k = 0; k < 20; k++) {
            vm->pop();
        }
    }
    vm->freeVM();
    delete (vm);
}

int main() {
    test1();
    test2();
    test3();
    test4();
    perfTest();

    return 0;
}