This lesson's interactive features are locked, please to keep using them

Handling Cycles

We built a simple reference counting garbage collector. It can handle:

Simple types, like INT and FLOAT
Dynamically allocated types, like STRING
Static container types, like VECTOR3
Dynamic container types, like ARRAY

However, there's one little problem with our implementation. Take a look at this code:

snek_object_t *first = new_snek_array(1);
snek_object_t *second = new_snek_array(1);
// refcounts: first = 1, second = 1
snek_array_set(first, 0, second);
// refcounts: first = 1, second = 2
refcount_dec(first);
// refcounts: first = 0, second = 1
refcount_dec(second);
// refcounts: first = 0, second = 0
// all free!

We create a first array, and shove the second array inside of it. Everything here works as expected. The trouble arises when we introduce a cycle: for example, first contains second, but second also contains first...

Assignment

Run the code in its current state. Notice that the assertions in main.c fail. Even though we decremented both the first and second arrays' refcounts, neither was freed: the refcounts are not 0!

Fix the assertions to pass by updating them to match the sad reality of our current implementation.

You'll still see a memory leak warning after you get the tests passing. That's expected! We're proving that refcounting is broken for cycles, and we'll fix it in upcoming lessons.

Observe

The reason both refcounts are stuck at 1 after being decremented is that, when first has its refcount decremented, it already has 2. So it only drops to 1, which does not trigger a "free" of the second array:

void refcount_dec(snek_object_t *obj) {
  if (obj == NULL) {
    return;
  }
  obj->refcount--;
  if (obj->refcount == 0) {
    // this doesn't happen when refcount is 1
    return refcount_free(obj);
  }
  return;
}

And because second still has 2 refcounts, it also only drops to 1, which fails to trigger a "free" of the first array.

In other words, we have a cycle, and our simple reference counting garbage collector can't handle it.