This is part of my series on EvilVM, a project to create a tiny injectable VM with language support for EvilTM agent features for pen-testers like me. In other words, a programming language and agent framework specifically designed for post-exploitation. The goal is to allow ad-hoc, reliable adaptation of malicious agents to situational needs during a pen-test. And to build it from scratch for fun (of course). The index and overview for this project can be found here.

Garbage Collection: Shoulders of Babies

I had slapped together a little Lisp interpreter some time ago, and it was pretty rough, but technically worked. I had implemented some data structures for representing data types and pairs (linked list nodes, basically), and had an S-expression parser and very simple interpreter. But then, after tons of work and some barely working code, I hit a serious issue. I hadn’t considered memory management at all, and I realized that garbage collection was in my future.

So I started researching. There are lots of great articles on garbage collection. One of the best is this 9-part series on the Microsoft blog. I won’t judge the source, it’s really good material! This got me thinking that maybe writing a garbage collector wouldn’t be so bad. But backporting it into all the glue I had written in my toy Lisp interpreter was a really frightful thought.

Meanwhile, in another context, I read the first tech book in a long time to really stimulate my imagination. I’m working with my kids (8 and 10 years old) on making games. As I started working up a halfway decent game engine for them to use, I stumbled onto Game Programming Patterns by Munificent Bob. This was a truly fascinating book – in part because the ideas were so appropriate to my problem domain at the time, but also because Bob is a really smart guy, adds lots of great flavor to the content, and uses great examples. One of his chapters is about using a bytecode VM to add a layer of configurability to a game engine.

With my new tech-crush on Bob’s material, I hopped over to his blog, and it was like lightning struck. Munificent Bob not only wrote the most interesting tech book I’ve read this year, but he also wrote a blog post that I had read, but was unable to re-find when I wanted it: Baby’s First Garbage Collector. Wow, thanks Bob!

Bob’s Baby’s First Garbage Collector (BBFGC from now on) is on github, and the article is fantastic. So I realized that EvilVM should start with a combination of these two ideas: a garbage collector, loosely based on Bob’s example, and a bytecode virtual machine.

NOTE: I recognize that BBFGC is woefully inefficient. It runs malloc() and free() for every allocation and deallocation, for example. I intend eventually to migrate this to using object pools and a few other enhancements. For now, it’s important that I have a GC at the beginning with a simple interface that can grow later.

In this post, I’ll not focus on the raw details of the garbage collector – it really is just adapted straight from Bob’s code. I renamed some things, etc., but otherwise the same. As an aside, I wrote it all while I reread through the blog post. It helps a lot to type the code out because I start to internalize how it works and where things are.

What I thought I’d document for this article is what I need to do to Bob’s GC to make it more useful for EvilVM. That will require delving a bit into my current conception for the design of the EvilVM runtime.

Additional Data Types

BBFGC is set up for two data types – integers and pairs. I have to decide if I’m going to somehow represent everything as integers, or if I’m going to expand the number of datatypes. I could do everything as int values. Strings are just chars, and even in Unicode most of them fit in an int. Pointers are probably the size of an int, etc. But I added a bunch of types:

  • i32, u32, i8, u8, float, double – for obvious reasons
  • pointer – since EvilVM will be managing lots of C structs and interfacing with system APIs, I will need some way to represent a pointer.
  • symbol – I’m very likely to either build a Lisp out of this, or at least borrow the symbol idea. So a symbol is an integer (really, an index into a symbol table), but should have its own fundamental type.
  • vector – in playing around, I’ve already found a few uses for an array. So a vector is a dynamically allocated array of pointers to objects. When I get to the instruction set, it’ll be more clear, but having a fundamental data type that represents an array is handy. In my case, a vector actually is a pointer to its region in memory as well as a length field.

Code-wise, this just means adding to the object definition in BBFGC’s code. Here’s mine, e.g.:

typedef struct sobject {
    data_type type;
    unsigned char mark;
    struct sobject *next;

    union {
            int i32_value;            // TYPE_INT
            int u32_value;            // TYPE_UINT
            char i8_value;            // TYPE_CHAR
            unsigned char u8_value;   // TYPE_UCHAR
            float float_value;        // TYPE_FLOAT
            double double_value;      // TYPE_DOUBLE
            void *ptr_value;          // TYPE_PTR
            int symbol;               // TYPE_SYMBOL

            struct {                  // TYPE_VECTOR
                    struct sobject **vector;
                    int length;
            };

            struct {                  // TYPE_PAIR
                    struct data_obj* car;
                    struct data_obj* cdr;
            };
    };
} object;

Separate Return Stack

In a stack machine, it’s a little irritating to keep return pointers on the stack. You have to juggle the stack around a bit extra to keep things done right. So in a lot of cases, stack machines will have a separate stack – the “return stack” – that is just for return pointers. I ran across some really great discussion about the minimum requirements for a generic stack machine in this article from CMU, BTW. As such, I’ve added an additional stack that works the same way as BBFGC’s “stack” array.

Closure Roots

Another interesting topic is closures. Many languages don’t have them – especially languages of the compiled variety. Put succinctly, a closure is important when you create a new function while your program is running. The closure captures the program’s context when the new function is created. For example, say you want to make a function that returns another function. Here’s an example in Ruby:

def multiplier(amount)
  return Proc.new do |i|
    i * amount
  end
end

This works in Ruby, because it supports closures. For example, I could do something like this:

> doubler = multiplier 2
> tripler = multiplier 3
> doubler.call(6)
=> 12
> tripler.call(6)
=> 18

The Proc “captures” (or “closes over”) the variable binding for the amount variable. When you call the new function later, it “remembers” the value that amount had when it was created because of the closure.

I know for sure that EvilVM must support closures. I’m not entirely sure how I’m going to implement them, but at a minimum, I’m going to need some way to represent a closure (which is, at the very least, a set of variable bindings), and the garbage collector will need to know how to deal with them. This is very important because I don’t want either of the following two failures to happen:

  • GC collects a variable that is referenced in a closure somewhere
  • GC never collects variables in closures

In the first case, I’ll have fatal bugs. In the second, I’ll leak memory every time I create a closure. Depending on how someone uses the closures (I mean… I may have written programs that created millions of closures), it could be an issue. So I’ve added some stubbed support for closures:

typedef struct s_closure {
        object **locals;
        int count;
        struct s_closure *next;
} closure;

struct sVM {
        object  *stack[STACKLEN];  // execution stack
        void    *retstack[RETLEN]; // return value stack
        closure *closures;         // closure stack (linked list)
        . . . 
};

I’ll, for now, look at closures similarly to allocated variables. The closure is going to have some list of bindings (since I should normally know how many external bindings exist when a function is created, I’ll assume it’ll be a dynamically allocated array, hence object **). The mark function in the GC has to be modified as well to traverse this list of closures to make sure that it can mark any of the variables they contain.

Performance Metrics

Finally, when I was doing a bunch of testing with the GC, I found it useful to make sure that I could measure its behavior over time. So I added some values that get updated at different times:

struct sVM {
    . . .    
    int creates;               // total created objects (not decremented during GC like count)
    int reclaims;              // total reclaimed objects
};

This way, I can do things like this:

EVILAPI vm_destroy(VM *vm) {
    vm->stacksize = 0;
    int backup = vm->reclaims;
    vm_gc(vm);
    int i = 0;
    object *cursor = vm->root;
    while (cursor) {
            cursor = cursor->next;
    }
    printf("  [-] GC reclaimed %d objects\n", vm->reclaims - backup);
    printf("  [-] GC reports VM still has %d objects\n", vm->count);
    free(vm);
}

See how I save the value of reclaims before I do a GC run and then check it again later? This lets me ensure that as I do my functional testing I can get data on the behavior of the GC.

Conclusion

I’ve always considered garbage collection to be a mystical thing. I’d read descriptions of it in the past, but without actually sitting down and looking at one, it’s hard to really get a feel for what’s going on. I’m very grateful to Bob Nystrom (Munificent Bob) for his materials. If it wasn’t for his article on BBFGC (and a few other articles on the Internet), I’d have been stuck with going through really complicated garbage collectors, like the famous Boehm-Demers-Weiser – not for the feint of heart!

With this foundation laid, the next thing to tackle is the bytecode VM. Being able to allocate and clean up objects in memory is nice and all, but the whole point is to run code. That’s where I’m going next!