3...2..1... Collect the Trash!

Ok so y'all probably remember wayyyyy back in October when I was discussing writing a garbage collector. Well, I really don't expect you to remember that. "You" being the pronoun referring to my two subscribers (one being a stalker). Ok, yeah I flatter myself, in reality, it's probably not a stalker of physical attraction, rather a psychotic blood thirsty individual. *waves*

Well, why do I want to dance with a garbage collector? Isn't that the evil-bastard-child/antithesis to region based memory management (RBMM), what I have been working on the past two years or so? Nope! Garbage collection can be a compliment. See, RBMM works by analyzing a program at compile-time (my system uses a gcc-plugin). From this analysis the compiler can insert memory allocation and reclaim calls (think malloc/free) at compile time. My system automatically free's memory, based on which objects point to which other objects. These groupings of objects can come from the same region of memory. A region cannot be reclaimed until all objects in it are no longer needed. Then, in one quick swoop, the memory of the region (the space that all the objects take-up) can be reclaimed. This fast memory reclaim is a key benefit of RBMM, as there is no need to visit each object and reclaim its memory individually.

Unfortunately, not all object lifetimes can be decided at compile time, such as global variables, or values pointed to/aliased by globals. This means that some objects cannot be reclaimed based on a compile-time static analysis. If these undecidable-lifetime objects are in a region, then that region lives for the entire lifetime of the program. Static analysis cannot force a region to die, unless it can be 100% sure that the region contents (objects) are never needed again. Global nastyness creates region bloat, as some objects might be reclaimable, and not others. As I previously mentioned, a region cannot be removed until ALL of its objects are no longer alive. If a global variable pops into the region, then that region now lives forever. Like a virus.

The above issue means that a garbage collector can actually benefit an RBMM system. That is what I have been working on: a combining of RBMM and garbage collection. This is not unique, and has been done before; however, the way we implement our collector is unique, but that is not discussed in this post.

Disclaimer: Grammar nuts please note that this is a blog post, so I am immediately relieved of any misuse of narrative modes. This is a design for my PhD and something that I have worked on with my advisers quite a bit (the "we"). The code is mine.

What I want to discuss in this post is how we locate stack variables. Stack variables form a subset of the root-set. The root-set being a collection of variables that are live at the time of garbage collection. If any data is accessible through the root-set then that object is also alive and must survive garbage collection. Else, the memory for data/objects that is not reachable can be collected. I will not go into details, or even the collector type I have chosen (e.g. mark-sweep, or copy, etc). Instead, I just want to talk about finding the stack variables; as I said a sub-set of the root set. Globals and registers also can be part of the root-set, but this post is only about stack variables </redundancy>.

When the garbage collector kicks-in the collector needs to start somewhere. It starts by scanning the root-set. Well, how does the collector get this root set? Specifically, what this post is concerned with is obtaining a sub-set of the roots, the stack variables. If you are familiar with stack-frames or activation records, the values there in the stack must be scanned. If any of those variables point to objects dynamically allocated (e.g. heap variables or variables from a region), then such objects must survive collection, and their memory cannot be recycled.

I have implemented a compiler modification (gcc-plugin) which provides hints to the garbage collector as to how to trace the stack of the program. This is how the collector gets the subset of the root-set, the stack variables. Actually, it is so cool and nifty I warranted this entire blog post to the notion.

My aim is to provide, at compile-time, a table that can be read by the garbage collector at runtime. During compile-time, as the source-code is being processed my plugin locates all function calls in the program. At the return of each function call a label is inserted (think assembly goto/label). This label is unique for each callsite, and makes up the key into a table that I am building. This key points to information about the function that the label is inside. For the example just below, the three labels are unique, but all point to the same function information. Information about my_function(), which specifies what local variables it has (x, y, z), if the variables are pointers, and how big the variables are.

void my_function(void)
{
    int x;
    float y;
    double z;

    foo();
__label0:

    bar();
__label1:

    baz();
__label2;
}

The function above has three callees (foo, bar, baz). At each call site, my plugin inserts a label. Now, why do I insert labels? Well, at runtime we need a way of associating the return point for each function call (foo, bar, baz). At compile time I do not have any addresses to use, hell, addresses are created by the OS when the executable is loaded; we haven't even finished compiling the source code yet! The solution is to insert a label which can be used at compile time to build a table of stack-variable information. The loader will fix-up the addresses, and at runtime the labels will have the correct address that the function call returns to. Recall that each time a function is called, the return instruction pointer RIP or return address will be stored on the stack. This value will be the same as the respected label. For instance, consider that my_function() is being executed, and the line which calls bar() is executed. When bar() gets called, the return point, which now happens to also match __label1, is placed onto the stack. And when bar() returns, the return point is now the same as __label1. The only thing we have done so far is insert labels. No big deal. Note: I doubt anyone except for maybe one person has read this far, if you do, email me, you kick so much ass, that next time we meet, I will buy you coffee produced from the most lavish and rare of coffee seeds: unicorn digested coffee. I will then serenade you with a ear-piercing song and proclaim you Captain Badassery and dance around bear-chested wearing a Burger-King crown and throw pennies at your feet.

As mentioned, the labels are entries into a table that contains function information (variables, stack size, etc). When the garbage collector kicks-in, it looks at the stack and locates the return point. That value is a key into a function table my plugin generated, remember the RIP coincides with the added labels. The collector uses the RIP/label as a key to get function information, and then processes the variables (figuring out which heap values can be accessed though the local variables in that function). Once that function is scanned, its caller function is scanned, and so on... it's turtles all the way down... until the collector hits main(). Then this portion of garbage collection is complete.

TLDR; Anyways, the above diatribe is an expose into the use of labels for providing a means of accessing stack variables, and providing a compile-time generated way of performing a runtime stack trace.

Have an awesome New Year and may all of your garbage be collected properly!

-Matt