3.16 Garbage Collectors

Complete this assignment with Team Two.

You must submit this in an archive named "gc.zip". This archive must contain a folder named "gc". This folder must contain all the files specified below. You must attach "gc.zip" to an email whose subject is "BYU - Fall 2011 - CS 330 - gc" and whose message body contains the name of everyone on your team (each on a separate line.) You must send this email to jay@cs.byu.edu before 5pm (Provo time) on 11/17. Ensure that what you are satisfied with what you submit, because only your chronologically first submission will be graded. Ensure that you follow these instructions exactly, since submissions that do not meet these requirements (i.e. do not have the correct format) will receive no credit, despite the time and energy you put into the assignment. Please see Turn In Policy for more information.

You must submit this in a file named "mark-and-sweep.rkt".

You must submit this in a file named "stop-and-copy.rkt".

In this assignment, you will implement two garbage collectors: mark & sweep, and stop & copy. 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.

3.16.1 Writing your Garbage Collectors

You must complete this assignment using a specific language. Choose Determine language from source in the DrRacket menu, then write

#lang plai/collector

as the first line of your program, overwritting the default #lang at the top of the file.

This language defines an interface to a program’s stack and heap that you will use to implement garbage collection.

3.16.1.1 Required Functions

Your garbage collectors must implement the following functions:

3.16.1.2 Provided Functions

To help you write these functions, the GC Collector Racket language defines an interface for the heap and the roots:

Note: Sometimes you have to fake roots in case a live object is only reachable from arguments passed to a collector function. For example, you should pass the first and rest addresses to get-root-set in your implementation of gc:cons. (This is not the only example!)

3.16.2 Testing your Garbage Collectors

You must complete this assignment using a specific language. Choose Determine language from source in the DrRacket menu, then write

#lang plai/mutator

as the first line of your program, overwritting the default #lang at the top of the file.

The remainder of the program is in a subset of Racket with numbers, symbols, lists, etc. The primitives of the language map directly to the procedures you define in your garbage collector.

3.16.3 Sample Code

To get you started, we’ve provided a sample mutator and a trivial collector that signals an error when the heap fills up. (In fact, our collector does signal an error with the mutator we’ve provided, if you don’t increase the size of the heap.)

3.16.3.1 Trivial Collector

"collector.rkt":

#lang plai/collector

(define heap-ptr 'uninitialized-heap-ptr)

(define (init-allocator)

(set! heap-ptr 0))

(define (gc:alloc-flat p)

(begin

(when (> (+ heap-ptr 2) (heap-size))

(error 'gc:alloc-flat "out of memory"))

(heap-set! heap-ptr 'prim)

(heap-set! (+ 1 heap-ptr) p)

(set! heap-ptr (+ 2 heap-ptr))

(- heap-ptr 2)))

(define (gc:cons f r)

(begin

(when (> (+ heap-ptr 3) (heap-size))

(error 'gc:cons "out of memory"))

(heap-set! heap-ptr 'cons)

(heap-set! (+ 1 heap-ptr) f)

(heap-set! (+ 2 heap-ptr) r)

(set! heap-ptr (+ 3 heap-ptr))

(- heap-ptr 3)))

(define (gc:cons? a)

(eq? (heap-ref a) 'cons))

(define (gc:first a)

(heap-ref (+ 1 a)))

(define (gc:rest a)

(heap-ref (+ 2 a)))

(define (gc:set-first! a f)

(if (gc:cons? a)

(heap-set! (+ 1 a) f)

(error 'set-first! "expects address of cons")))

(define (gc:set-rest! a r)

(heap-set! (+ 2 a) r))

(define (gc:flat? a)

(eq? (heap-ref a) 'prim))

(define (gc:deref a)

(heap-ref (+ 1 a)))

3.16.3.2 Sample Mutator

"mutator.rkt":

#lang plai/mutator

(allocator-setup "collector.rkt" 84)

(define (fact x)

(if (zero? x)

1

(* x (fact (sub1 x)))))

(define (fact-help x a)

(if (zero? x)

a

(fact-help (sub1 x) (* x a))))

(define lst (cons 1 (cons 2 (cons 3 empty))))

(define (map-add n lst)

(map (lambda (x) (+ n x)) lst))

(define (map f lst)

(if (cons? lst)

(cons (f (first lst)) (map f (rest lst)))

empty))

(define (filter p lst)

(if (cons? lst)

(if (p (first lst))

(cons (first lst) (filter p (rest lst)))

(filter p (rest lst)))

lst))

(define (append l1 l2)

(if (cons? l1)

(cons (first l1) (append (rest l1) l2))

l2))

(define (length lst)

(if (empty? lst)

0

(add1 (length (rest lst)))))

(define tail (cons 1 empty))

(define head (cons 4 (cons 3 (cons 2 tail))))

(set-rest! tail head)

(printf "res ~a~n" head)

(set! head empty)

(set! tail head)

(printf "res ~a~n" lst)

(printf "res ~a~n" (length '(hello goodbye)))

(printf "res ~a~n" (map sub1 lst))

(printf "(fact-help 15 1): ~a~n" (fact-help 15 1))

(printf "(fact 9): ~a~n" (fact 9))

(printf "(append lst lst): ~a~n" (append lst lst))

(printf "(map-add 5 lst): ~a~n" (map-add 5 lst))

(printf "(filter even? (map sub1 lst)): ~a~n"

(filter even? (map sub1 lst)))

(printf "(length lst): ~a~n" (length lst))

If your collector works correctly on the heap size you’ve specified, this should result in:

> (printf "res ~a~n" head)

res #0={4 3 2 1 . #0#}

> (set! head empty)

> (set! tail head)

> (printf "res ~a~n" lst)

res (1 2 3)

> (printf "res ~a~n" (length '(hello goodbye)))

res 2

> (printf "res ~a~n" (map sub1 lst))

res (0 1 2)

> (printf "(fact-help 15 1): ~a~n" (fact-help 15 1))

(fact-help 15 1): 1307674368000

> (printf "(fact 9): ~a~n" (fact 9))

(fact 9): 362880

> (printf "(append lst lst): ~a~n" (append lst lst))

(append lst lst): (1 2 3 1 2 3)

> (printf "(map-add 5 lst): ~a~n" (map-add 5 lst))

(map-add 5 lst): (6 7 8)

> (printf "(filter even? (map sub1 lst)): ~a~n"           (filter even? (map sub1 lst)))

(filter even? (map sub1 lst)): (0 2)

> (printf "(length lst): ~a~n" (length lst))

(length lst): 3

3.16.4 Notes

You must store bookkeeping data on the heap provided by GC Collector Racket. You may store 2-3 atomic values, such as addresses into the heap as variables in your garbage collector. We will assume they represent machine registers. However, all compound data structures must be on the heap.

In particular, in the mark & sweep collector, you should maintain a free list in the heap. That is, you should not use any auxiliary data structure; instead, use the available space in the heap to keep track of the free list. You may use one extra box (“register”) to point to the start of the free list. You may need to adjust your allocation accordingly to have enough space to maintain free list pointers!

3.16.5 Grading

This assignment is graded as a written assignment. The coding style guidelines count as a single question.