Refcounting GC

A garbage collector's job is simple to state and tricky to implement: automatically free heap memory once nothing needs it anymore. Reference counting is the simplest strategy, every Obj tracks how many places are pointing at it, and frees itself the moment that count hits zero.

#include <stdlib.h>

typedef enum { OBJ_INT, OBJ_STRING } ObjType;

typedef union {
    int intValue;
    char *stringValue;
} ObjValue;

typedef struct Obj {
    ObjType type;
    int refCount;
    ObjValue as;
} Obj;

void objRetain(Obj *obj) {
    if (obj == NULL) return;
    obj->refCount++;
}

void objRelease(Obj *obj) {
    if (obj == NULL) return;
    obj->refCount--;
    if (obj->refCount == 0) {
        if (obj->type == OBJ_STRING) {
            free(obj->as.stringValue); // free the string data first
        }
        free(obj); // then the Obj itself
    }
}

#include <stdlib.h>

typedef enum { OBJ_INT, OBJ_STRING } ObjType;

typedef union {
    int intValue;
    char *stringValue;
} ObjValue;

typedef struct Obj {
    ObjType type;
    int refCount;
    ObjValue as;
} Obj;

void objRetain(Obj *obj) {
    if (obj == NULL) return;
    obj->refCount++;
}

void objRelease(Obj *obj) {
    if (obj == NULL) return;
    obj->refCount--;
    if (obj->refCount == 0) {
        if (obj->type == OBJ_STRING) {
            free(obj->as.stringValue); // free the string data first
        }
        free(obj); // then the Obj itself
    }
}

The rule every piece of code has to follow religiously: call objRetain whenever you store a new reference to an object (assign it to another variable, put it in a list, etc.), and objRelease whenever that reference goes away.

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

typedef enum { OBJ_INT, OBJ_STRING } ObjType;

typedef union {
    int intValue;
    char *stringValue;
} ObjValue;

typedef struct Obj {
    ObjType type;
    int refCount;
    ObjValue as;
} Obj;

struct Obj *objNewInt(int value) {
    Obj *obj = malloc(sizeof(Obj));
    obj->type = OBJ_INT;
    obj->refCount = 1;
    obj->as.intValue = value;
    return obj;
}

void objRetain(Obj *obj) {
    if (obj == NULL) return;
    obj->refCount++;
}

void objRelease(Obj *obj) {
    if (obj == NULL) return;
    obj->refCount--;
    if (obj->refCount == 0) {
        free(obj);
    }
}

int main(void) {
    Obj *a = objNewInt(42);   // refCount = 1
    Obj *b = a;
    objRetain(b);              // refCount = 2, two owners now
    printf("refCount: %d\n", a->refCount);

    objRelease(a);             // refCount = 1, still alive
    printf("refCount: %d\n", b->refCount);

    objRelease(b);             // refCount = 0, freed here
    printf("done\n");
    return 0;
}

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

typedef enum { OBJ_INT, OBJ_STRING } ObjType;

typedef union {
    int intValue;
    char *stringValue;
} ObjValue;

typedef struct Obj {
    ObjType type;
    int refCount;
    ObjValue as;
} Obj;

struct Obj *objNewInt(int value) {
    Obj *obj = malloc(sizeof(Obj));
    obj->type = OBJ_INT;
    obj->refCount = 1;
    obj->as.intValue = value;
    return obj;
}

void objRetain(Obj *obj) {
    if (obj == NULL) return;
    obj->refCount++;
}

void objRelease(Obj *obj) {
    if (obj == NULL) return;
    obj->refCount--;
    if (obj->refCount == 0) {
        free(obj);
    }
}

int main(void) {
    Obj *a = objNewInt(42);   // refCount = 1
    Obj *b = a;
    objRetain(b);              // refCount = 2, two owners now
    printf("refCount: %d\n", a->refCount);

    objRelease(a);             // refCount = 1, still alive
    printf("refCount: %d\n", b->refCount);

    objRelease(b);             // refCount = 0, freed here
    printf("done\n");
    return 0;
}

The fatal flaw: cycles

Refcounting has one well-known blind spot, if object A holds a reference to B, and B holds a reference right back to A, their counts can never reach zero, even if nothing outside the pair references either of them anymore. That memory leaks forever. This isn't a bug you can patch, it's fundamental to how refcounting works, which is exactly why the next lesson introduces a completely different strategy.

TIP

This exact tradeoff is why Python uses reference counting plus a supplementary cycle detector, and why some languages (like the one you're about to build a collector for) choose mark-and-sweep instead, no cycle problem, at the cost of needing to pause and scan everything periodically.

Refcounting GC

The fatal flaw: cycles

📝 Refcounting GC Quiz