Background
Q1. Swap spaces
Q2. GC for flat items
Q3. GC for cons pairs
Q4. GC for closures
Finishing up

Background

In this assignment you will implement a two space copying collector similar to the one discussed in Lecture 19. You are welcome to refer to that collector as a reference, but I cannot promise it will be easy to copy code from there. If you do use it directly, make sure to credit your sources.

A skeleton of two space garbage collector is provided. At the top of the file you can find definitions defining the heap structure. There are two slots for metadata, and the rest of the heap is divided into two spaces (conceptually). The first slot is the offset, which defines which space the system is currently allocating into, and the second slot defines where in the current space to next allocate. Doing allocation requires using both slots:

;; malloc : size -> address
(define (malloc n)
  (when (> (+ (ptr) n) (space-size))
    (gc!))
  (when (> (+ (ptr) n) (space-size))
    (error 'malloc "out of memory!"))
  (heap-set! LOC:PTR (+ (ptr) n))
  (+ (heap-ref LOC:OFFSET) (- (ptr) n)))

Q1. Swap spaces

Define a function swap-spaces! that swaps the from and to spaces. This function should not move any allocated records, just update the heap metadata. Your function should pass the following tests.

(module+ test

  ;; Initially, allocations are in the left half.
  (test/heap
      (make-vector (+ 4 METADATA-SIZE) '?)
    (gc:alloc-flat #f)
    (current-heap)
    #(2 2 flat #f ? ?))

  ;; After calling swap-spaces!, allocations are in the right half
  (test/heap
      (make-vector (+ 4 METADATA-SIZE) '?)
    (swap-spaces!)
    (gc:alloc-flat #f)
    (current-heap)
    #(4 2 ? ? flat #f))

  ;; Swapping twice is back to allocating in left
  (test/heap
      (make-vector (+ 4 METADATA-SIZE) '?)
    (swap-spaces!)
    (swap-spaces!)
    (gc:alloc-flat #f)
    (current-heap)
    #(2 2 flat #f ? ?))
  )

Q2. GC for flat items

Write an initial version of the function gc! that can handle “flat” items (e.g. numbers, booleans). Your initial function should pass the following test.

(test/heap
    (make-vector 12 '?)
  (define f1 (gc:alloc-flat #f))
  (with-roots (f1)
    (gc!)
    (cons (current-heap) (map read-root (get-root-set))))
  (cons
   #(7 2 forwarded 7 ? ? ? flat #f ? ? ?)
   '(7)))

Q3. GC for cons pairs

Update your function gc! so that it can handle cons pairs. This will require moving the two records pointed to by the cons record.

Your updated function should pass the following test.

(test/heap
    (make-vector 18  '?)
  (define c1
    (gc:cons
     (simple-root (gc:alloc-flat #f))
     (simple-root (gc:alloc-flat #t))))
  (with-roots (c1)
    (gc!)
    (cons (current-heap) (map read-root (get-root-set))))
  (cons
   #(10 7 forwarded 13 forwarded 15 forwarded 10 4 ? cons 13 15 flat #f flat #t ?)
   '(10)))

For this part and the next you will need to modify the API of gc! and malloc to take one or more extra arguments for roots. It’s up to you how to manage this, but I suggest using rest arguments since that will allow leaving most of the calls to gc! as they are.

Q4. GC for closures

Update your function gc! that can handle closures. From a GC perspective clos records are like variable sized cons records, so the main difference from the previous question is figuring how many slots to copy. Your updated function should pass the following test.

(test/heap
    (make-vector 18  '?)
  (define cl1
    (gc:closure 'dummy (list (simple-root (gc:alloc-flat #f)))))
  (with-roots (cl1)
    (gc!)
    (cons (current-heap) (map read-root (get-root-set))))
  (cons
   #(10 6 forwarded 14 forwarded 10 1 2 ? ? clos dummy 1 14 flat #f ? ?)
   '(10)))

Finishing up

Make sure you have complete test coverage and test documentation.

Run some small mutator tests like fib.rkt. Include the mutator tests you run as block comments in your submission.

(module+ test
  (test/heap
      (make-vector 12 '?)
    (define f1 (gc:alloc-flat #f))
    (gc! (simple-root f1))
    (current-heap)
    #(7 2 forwarded 7 ? ? ? flat #f ? ? ?)))

Table of Contents