CS 4536/CS 536 Homework 5: Garbage Collection

Due: Monday, October 5, 11:59pm via turnin (assignment name hwk5)
Collaboration Policy: Individual

The Assignment

In this assignment, you will implement a stop & copy garbage collector. As we have seen, garbage collection involves starting from a root set of references, which reside in local variables and stack frames, and searching for reachable values on the heap. We are providing support code that gives your collector access to a running Scheme program's root set. You just have to implement the memory allocator and the garbage-collection algorithm.

Write your garbage collector in the GC Collector Scheme language level. This language defines an interface to a program's stack and heap that you will use to implement garbage collection. Language-level docs

Your garbage collector must implement the following functions:

• init-allocator :: -> void The mutator implicitly calls this function after initializing the heap and before calling any allocation routines. It is essentially a callback into the allocator indicating that the heap is ready.
• gc:cons :: first-loc rest-loc -> cons-loc returns the address of a new cons cell with the given field addresses; the field addresses are presumed to be already allocated
• gc:cons? :: loc -> boolean returns a boolean that indicates whether the given address refers to a cons cell
• gc:first :: cons-loc -> first-loc and gc:rest :: cons-loc -> rest-loc return the fields of a given cons
• gc:set-first! :: cons-loc first-loc -> void and gc:set-rest! :: cons-loc rest-loc -> void set the addresses of the first and last pointers of a cons cell
• gc:alloc-flat :: atomic -> number allocates space for a flat value and returns the base address of the allocated block
• gc:flat? :: loc -> boolean returns a boolean that indicates whether the given address refers to an atomic value
• gc:deref :: loc -> atomic returns the atomic value stored at the given address

To help you write these functions, the GC Collector Scheme language defines an interface for the heap and the roots (the roots is the set of pointers into the heap from the stack):

• heap-size :: -> number the size of the heap
• heap-value? :: value -> boolean determines whether the given value is a proper atomic type to store on the heap (ie, boolean, number, procedure, symbol or empty)
• heap-set! :: loc atomic -> void stores a value at the specified address
• heap-ref :: loc -> atomic returns the value at the specified address
• get-root-set :: -> listof root returns the roots of the collection
• read-root :: root -> loc returns the address the root references
• set-root! :: root loc -> void updates the root to reference the specified address
• procedure-roots :: procedure -> listof root given a procedure (closure) stored on the heap, returns a list of the root reachable from the closure's environment. If the procedure is not reachable, the empty list is returned.

Your collector should follow these error message conventions:

• An error message with substring "out" if a program is out of memory.
• An error message with substring "expect" if a program has a type error (such as calling gc:first on the address of a flat value).

Testing your Garbage Collector

You may write programs that exercise your garbage collectors using the GC Mutator Scheme language. This language is a subset of Scheme that uses a garbage collector that you specify. The first line of a test program must be:

(allocator-setup "collector.ss" heap-size)

"collector.ss" must be the name of your collector's file. heap-size is the size of the heap your collector will use.

The remainder of the program is in a subset of Scheme with numbers, symbols, lists, etc. The primitives of the language (such as cons, first, rest) map directly to the procedures you define in your garbage collector.

Sample Code

To get you started, here are a sample mutator and a trivial collector that signals an error when the heap fills up. (this collector does signal an error with this mutator, if you don't increase the size of the heap.)

Notes

• During collection, you will need to use get-root-set to obtain the current set of roots. The root set only includes data that have been allocated, not data in the process of being allocated. For example, the first and rest arguments to a gc:cons will not be included automatically in get-root-set. However, get-root-set takes any number of additional addresses as arguments, converts them to roots, and adds them to the returned root set.

• You will want to test your program with small heap sizes, so that the garbage collector runs frequently.

• You may find it convenient to use the Scheme construct set!, which allows you to mutate a variable without using boxes. We recommend you use this feature only in one instance: when swapping the from- and to-spaces. This will save you the trouble of unboxing the heap every time you use it.

What to Turn In

Submit your collector as a file collector.ss (with your name at the top of it). Also submit at least 3 mutator-language files containing tests. Document each test with a comment describing what GC behavior the test is checking. Submit separate files, not a zip.

FAQ

get-root-set seems to return duplicate roots. Is this a bug in the support code? No, this is the intended behavior. Roots come from walking the stack, and several frames may refer to the same variable. Moreover, different variables may refer to the same heap location. You need to update all of them in your stop & copy collector.

It would be a lot easier if I could just make all objects consume the same amount of space. Would that be acceptable? No! We've been extremely easy-going in only making you handle two sizes. To reduce it to one size would make the problem trivial and unrealistic.