Garbage Collector Simulation

A garbage collector(GC) can automatically determine if an object is reachable and reclaim unreachable objects. We have discussed two types of GC: mark/sweep and copying. The goal of this part is to implement a simulator for a mark/sweep GC in Java.

What does a mark/sweep GC do?

Perform a reachabilityanalysis; this analysis starts from a set of root objects and iteratively identifies objects that are reachable (directly or transitively) from root objects.

Mark each reachable object.

Sweep all objects that are unmarked.

Simulating a Mark/Sweep garbage collector in Java

Implementation of a real GC requires identification of all stack variables and object references. It is very difficult to achieve without modifying JVM. In this project, we are not implementing a real GC. Instead, we are going to implement the Mark/Sweep algorithm in a simulated environment. For a given Java program (i.e., a test case), the simulated GC should be able to scan the objects created in the program and report those that are unreachable and should be deallocated.

Building a simulation library

The first step is to build a library to make all the heap references (pointers) available to us. Suppose our target program only supports the following four types of instructions:

Assignment instruction: A a = b;

Object creation: A a= new A();

Object read: b = a.f;

Object write: a.f = b;

In the simulated environment, we should have our own modeling of each type of instruction. For example, we need to create a class called GCSimulator, and inside this class, we create a static method for each type of instruction to model its effect. The skeleton of the class is as follows:

class GCSimilator

{

static void assign(String aName, String bName, Object o)

{}

// aName and bName represent the variable names a and b, respectively;

// o denotes the object referenced by a and b static void createObject (String aName, Object o) {}

// aName is the name of variable a, and o represents the newly created object static void readObject (String bName, String aName, Object o)

{}

// bName and aName represent the two variables b and a,

// and o denotes the heap object referenced by b static void writeObject(String aName, String bName, String fieldname, Object oa, Object ob)

{}

// bName and aName represent the two variables b and a,

// fieldname denotes the name of the field f,

// oa denotes the heap object referenced by a,

// and ob denotes the heap object referenced by b

static void gc()

{}

// a gc method that will be explicitly called to collect garbage

}

In a test Java program, for each statement, we (manually) add a call to a simulation method to capture its effect. For instance, a modified Java program looks like the following:

class Test{

static void main(String args[]) {

A a = new A(); GCSimulator.createObject(a, a);

B b = new B(); GCSimulator.createObject(b, b);

B c = b; GCSimulator.assign(c, b, b);

c.f = a; GCSimulator.writeObject(c, a, f, c, a);

P p = a.m; GCSimulator.readObject(p, a, p);

GCSimulator.gc();

}

}

In our GC simulator, we use string names a, b, c, d to represent stack variables. Different variables in a method must have different names. These strings can help us identify the roots for a GC traversal. A reference can be simulated by using a hashmap. In a Java program, there are two types of references: (1) stack-heap reference: a stack variable containing a pointer that points to a heap object; and (2) a heap-heap reference: a field of an object containing a pointer that points to another heap object. To simulate type 1 references, we can create a hash map stackRef in GCSimilator; Each entry in the hash map is a pair of a string (representing a stack variable) and an object (pointed to by the variable). For example, in method assign, we add pair into the stackRef; in method readObject, should be added to stackRef. To simulate type 2 references, we create another hash map heapRef in GCSimulator; each entry is a > pair. For each object o, heapRef maps it to a another map, which, in turn, maps each field name to an object. When a field write is seen (i.e., writeObject), we need to perform the following map update: ((Map)heapRef.get(oa)).put(fieldname, ob) ), which basically replaces the old object referenced by the field fieldname of oa with a new object ob. By appropriately implementing each simulation method, we can simulate all real reference relationships in our environment, which will be used later to perform reachability analysis.

Reachability analysis

The simulated GC does not automatically run. A programmer needs to explicitly call a library method GCSimulator.gc() to invoke the GC. We need to implement this gc method. The first step is to identify root objects. In our environment, they are objects pointed to by stack variables. We can easily find these objects by traversing the value set of map stackRef. Next, we should develop a graph traversal algorithm that iteratively identifies transitively reachable objects by chasing references (in map heapRef).

Identifying unreachable objects

Any object encountered in the reachability analysis is a reachable object. Our goal is to identify and print unreachable objects. This requires us to use a set to store all objects created during the execution. For example, every time we see an object allocation (in method createObject), we add the newly created object o into the set. When GC is invoked, we traverse this set and report objects that havent been encountered in the reachability analysis.

Output of the simulator

The GC simulator should be available as a library that provides the aforementioned methods. We will create a set of test programs with calls to your library methods (including the GC method). After each GC runs, the simulator should print unreachable objects in the following format:

GC#1:

The following objects are unreachable:

Object a , Object f,

GC#2:

The following objects are unreachable:

Object a , Object b,