RedBrain @ $HOME : ~ $

Garbage collection is a subject we all wish we knew more about, many software developers think they understand the concept fully and think building it should then be a trivial task. Building a ref-counted garbage collector, was much much more painful than i ever expected in crules. I am going to focus on how this work in an interpreted language and maybe a few months on how it will work in GccPy an Ahead of time implementation of Python on GCC.

So what is reference counting, take for instance the expression in a dynamic language:

x = 2 + 3 + 4 + 5;

So what happens in this expression in an interpreter? You can tell ‘x’ is a variable which will store the result of the expression ‘2 + 3 + 4 + 5′. Well to understand this simple example you first have to look at how this expression is evaluated, for instance these values ‘2,3….’ are still literals at this parse stage. What that means is they are numbers but dont paticularly have any meaning within the language yet, for instance python and crules need to ‘fold’ this literals into objects @see

`extern crl_symbol_obj * crl_rr_literal_fold( crl_symbol_obj * lit, crl_context_table * context )` in rr_bin_eval.c

In this case it looks at the literal object and then looks up for the apropriate object definition to create the Integer Object so the language knows how to do addition subtraction and some other member functions etc.

So ok lets look at this at a more semantic level what will happen is:

t1 = 2;
t2 = 3;
t3 = 4;
t4 = 5;

These address’s ‘t#’ are not actually accessible within the language its just a way of showing these are folded and we have addresses to them. Then we will have:

t5 = t1 + t2;
t6 = t5 + t3;
t7 = t6 + t4;

And now t7 should have the result of: 14 . And now finally:

x = t7;

So ok now you see how this is evaluated within at least a semantic context, what is ref counting?! So you can notice to get that simple result of 14 we had to create quite a few tmp objects as ‘t#’ But how does the runtime, tell which are temporary and which are still needed. Its as simple as adding in a ’signed long refcount’ to your Intermediate Representation.

In crules the notion of a context is the key to understanding how it all works so for each of these folded objects we create them with:

`Crl_Symbol_Init_Ctx( retval, context );` which is a pre-processor macro to initialize the crl_symbol_obj * retval, within this context. So what that is need for is when the garbage collector is invoked we need to be able to sweep over something to look for dead references in other words any objects with reference count ‘<= 0′ i say <= 0, and not simply zero because of how context poping and pushing can work and you can have a ref count of -2 in some cases but that’s besides the point.

So when this object is created within a context the garbage collection is able to sweep over a stack of context’s and look decide what needs deleted, so lets
look at the ref counting itself now.

Semantic | Refcount
——————-
t1       | 1
t2       | 1
t3       | 1
t4       | 1
t5       | 0
t6       | 0
t7       | 0

This shows the resulted ref counts after this is run:

t1 = 2;
t2 = 3;
t3 = 4;
t4 = 5;

Now lets look at what happens for:

t5 = t1 + t2

Semantic | Refcount
——————-
t1       | 2
t2       | 2
t3       | 1
t4       | 1
t5       | 1
t6       | 0
t7       | 0

So this is where it gets a little more tricky once that t5 has been evaluated t1 and t2 are de-referenced again.

Semantic | Refcount
——————-
t1       | 1
t2       | 1
t3       | 1
t4       | 1
t5       | 1
t6       | 0
t7       | 0

So the same idea happens for t6 and t7, and then we have the resultant table of:

Semantic | Refcount
——————-
t1       | 1
t2       | 1
t3       | 1
t4       | 1
t5       | 1
t6       | 1
t7       | 1

But now we know by common sense t1->t6 are all gabage its only t7 which is of any interest since this is what the variable ‘x’ now points to. But this is kind of down to how you implement it how you dec-rement those ref counts when i run in crules they are handled after each use.

Take a peek at rr_bin_eval.c and rr_math.c and rr_runtime.c in crl_rr_evaluate_expression( … )

So ok we should now have the table of:

Semantic | Refcount
——————-
t1       | 0
t2       | 0
t3       | 0
t4       | 0
t5       | 0
t6       | 0
t7       | 1

The key thing to remember is we dont have ref counts on the variable ‘x’ its what x points to! This is the whole key idea of how a dynamic type system works.

Now in crules the garbage collector is invoked when we have executed a full procedure, so in this case if i was to feed in directly this expression into the interpreter the garbage collector would be invoked if this was part of a function or procedure it would be executed once we hit the end of the block.

So now what comes in the idea of Mark-Sweep, this is probably what you understand of a mark sweep algorithm it sweeps over the stack and heap looking for dead refernces. So ok that makes sense but in the end its horrible vague and if you are to do that its an incredibly linear way of doing things. In essence crules has a mark sweep algorithm. But what really happens is i sweep and mark then free.

So to invoke the garbage collector in crules we call:

`extern void crl_garbage_invoke_sweep( crl_context_table * const );`

So what happens in gg_garbage.c, loops through each context in the context_table stack and looks through the symbol_stack and checks for objects of <= 0 ref count and marks them as garbage and sets the vector entry to NULL so it cant be collected again and result in a double free etc. Then once that is once it automaticaly invokes the garbage collector and runs over a vector of marked objects and free’s them one by one this could be speed up with pthreads but i havent got around to doing that.

This does not mean if your writing a builting object type or module as a dynamic lib .so, you have to invoke the garbage collection yourself you dont and if your writing crules code you dont have to do anything its all automatic except for the real intrinsic bits and pieces to the runtime within the interpreter.

Ok this is a good overview of ref counting but there is more lets take the example:

x = 2;
y = x;
z = y;

So as before we fold the literal ‘2′:

t1 = 2;
x  = t1;            t1 – ref count 1
y  = x = t1;        t1 – ref count 2
z  = y = t1;        t2 – ref count 3

Remember what we check is what the accessors point to, we never have a ref count on x or y or z its the value t1. So we have 3 objects simply pointing to the same object, We cannot free t1 at all! or we will surely break something!

We can only safely delete this if each of these accessors went out of scope in the current context example if we stopped the session. we can decrement. But to understand what i mean more deeply we have to look at how functions and argument passing works and how the context stack works.

So i will finish this in a 2nd part tutorial soon in a review of how crules internals work. I hope some of you are still awake!