Lab 4: Garbage Collector

Lab Overview

There are two parts in this lab. In the first part, you'll design and implement various GC maps, and modify your current C code generator to generate them. GC maps are compiler-generated data structures to tell Gimple various information it needs to collect garbage; for instance, the GC maps will tell Gimple the locations in memory of declared variables (of reference types) in a given method, so that Gimple can start, from these locations, to traverse the Java heap for reachable objects; and also GC maps will tell the Gimple collector the detailed memory layout of of heap-allocated objects, so that Gimple can traverse each object's children (i.e., fields with reference types).

And in the second part of this lab, you'll design and implement the Gimple garbage collector based on Cheney's copying algorithm.

Getting Started

  $ git commit -am 'my solution to lab3'
  $ git checkout -b Lab4 origin/Lab4

Again, you will now need to merge your code from Lab3 into the new Lab4 branch:

  $ git merge Lab3

  $ git commit -am 'lab4 init'

Now, you can import the new Lab4 code into your Eclipse. There is no new files for this lab. You will complete this lab by modifying existing code.

Hand-in Procedure

Part A: GC Maps

From the conceptual point of view, during the execution of a Java application, all heap-allocated objects form a directed graph in the heap, with objects as graph vertex and fields of reference types as graph edges. For instance, consider the sample Java heap at the right hand, the program variable p points to an object with value 15 in the first field, and this object is a graph vertex with two fields (of reference types) followed by the field 15.

Conceptually, the task of a garbage collector can be divided into two sub-tasks: scanning and collecting. During the scanning phase, the collector scans through the (object) directed graph to mark which objects are reachable whereas which are not. Then, during the collecting phase, the collector will reclaim unreachable objects to obtain more spaces. After the collection, it's often the case that there will be more spaces in the heap for future allocations. Of course, the division of the garbage collection into canning and collecting is more of explanation purpose. Many real garbage collectors combine the two phases in some way or even make use of other strategies.

So, for the graph traversal to work, two challenges must be addressed: first, how does the garbage collector know where to start to traverse the directed graph? i.e., the garbage collector must have enough knowledge about the positions of graph's roots. For instance, consider the right-hand graph, the garbage collector must find out the positions for declared program variable p and r.

Second, during the scanning phase, when the garbage collector walks to a graph vertex (an Java object), how does the collector know how many fields the current vertex has and which of these fields are references, thus should be further traversed (i.e., the node's out-degrees, in the graph theory terminology)? For instance, consider the right graph, when the collector walks to the graph vertex with value 15 from the declared variable p, it must have the knowledge that this object contains two reference fields at offset 1 and 2 separately, so that the graph traversal can continue with these two fields.

To address the first challenge, the garbage collector need the information of the positions of declared reference variables in a machine, the positions can be any region of a machine: global data area, stack slots, machine registers, etc.. The data structures to encode this information are often called the memory GC maps. And it's the compiler's task to generate such data structures.

To address the second challenge, the garbage collector need the information of number of fields contained in an object and among those which are references. The data structure to encode this information is often called the class GC maps. And also it's the compiler's task to generate such data structures.

Naming Allocations

1: class A{
2:   void foo(){ new B().bar(); }
3: }
4: class B{
5:   void bar(){ new B(); }
6: }

There is a simple solution to this problem: you can just name the object just after its allocation. Thus, each allocation expression new id () can be translated into a C comma expression (x=new id(), x) where x is a freshly generated variable. Of course, a new local variable declaration id x; should be generated. With this naming process, the above code will be roughly translated to:

1: class A{
2:   void foo(){ B x; (x=new B(), x).bar(); }
3: }
4: class B{
5:   void bar(){ B y; (y=new B(), y); }
6: }

Memory GC Maps

The data structure you'll use to encode the stack GC map is the bit-vector, which is just a string of "0" and "1"s, with "0" for non-reference variables and "1" for references.

T f (D this, int arg1, A arg2, B arg3){
  A local1;
  int local2;
  C local3;
  ... // statements
}

char *f_arguments_gc_map = "1011";
char *f_locals_gc_map = "101";

Call Stack and GC Stack

The C calling convention and call stack layout can be well explained by the function f from the above exercise. The following figure illustrates the stack layout of f on the x86 ISA:

  ----------------------------------------------------------> low address
   | arg3 | arg2 | arg1 | this | ret | ebp |  locals?
  -----------------------------------------------------------
                                        ^
                                       ebp

T f (D this, int arg1, A arg2, B arg3){
  A local1;
  int local2;
  C local3;
  ... // statements
}

char *f_arguments_gc_map = "1011";

Unfortunately, unlike arguments, you can say nothing about the layout of locals on the call stack. In fact, the C compiler is free to determine any layout for all the method locals: the compiler may rearrange the locals any order other than the order specified by the program text; or the compiler may not put all locals adjacently; or the C compiler may put some or all of the locals (via the so-called register allocation optimization) into machine registers instead of on the call stack, etc.. So, generally speaking, it's unreliable to suppose any specific stack layout for locals.

The solution you'll be using here is to introduce another stack to hold the function locals, and you can call the new stack the GC stack. Each stack frame in the GC stack contains the following elements: the memory GC map for argument; the address of the first argument; the memory map for locals; all the locals. For instance, consider again the method f from the above exercise, you should generate, for the method f, a data structure declaration for f's GC frame of this form:

struct f_gc_frame{
  void *prev;                     // dynamic chain, pointing to f's caller's GC frame
  char *arguments_gc_map;         // should be assigned the value of "f_arguments_gc_map"
  int *arguments_base_address;    // address of the first argument
  char *locals_gc_map;            // should be assigned the value of "f_locals_gc_map"
  struct A *local1;               // remaining fields are method locals
  int local2;
  struct C *local3;
};

// a global pointer
void *prev;
// two memory GC maps "f_arguments_gc_maps" and "f_locals_gc_maps" for this function, as above
// one data structure "f_gc_frame" for GC stack frame, as above
T f (D this, int arg1, A arg2, B arg3){
  // put the GC stack frame onto the call stack
  // note that this frame contains the three original locals in f
  struct f_gc_frame frame;   
  
  // push this frame onto the GC stack by setting up "prev"
  frame.prev = prev;
  prev = &frame; 
  // setting up memory GC maps and corresponding base addresses
  frame.arguments_gc_map = f_arguments_gc_map;
  frame.arguments_base_address = &this;
  frame.locals_gc_map = f_locals_gc_map;
  // initialize locals of this method
    
  ... // statements should be rewritten apporpriately
}

Class GC Maps

struct A_virtual_table{
  char *A_gc_map;   // class GC map
  ...               // virtual methods as before
};

Part B: Copying Collection

The Java Heap

Object Model

In the previous lab, you have used a simple yet standard object model. As there are two different forms of objects in MiniJava: normal objects and (integer) array objects. So, to support virtual method dispatching on normal objects, each object is represented as a sequence of its fields plus a unique virtual method table pointer at the zero offset as a header. And to support array length operations on array objects, arrays contain a length field as a header. However, to support garbage collection, you need a much fancier object model.

For both normal objects and array objects, you can use the following object model (suppose the class name is A):

struct A_class{
  void *vptr;       // virtual method table pointer
  int isObjOrArray; // is this a normal object or an (integer) array object?
  unsigned length;  // array length
  void *forwarding; // forwarding pointer, will be used by your Gimple GC
  ...;              // remainings are normal class or array fields
};

Copying Collection

1:  void f(){
2:    A x = new A();
3:    A y = new A();
4:    return 0;
5:  }

    1 round of GC: 0.3s, collected 512 bytes
    2 round of GC: 0.2s, collected 128 bytes
    3 round of GC: 0.8s, collected 4096 bytes

Handin