On this page:
4.1 Garbage Collector Interface for GC2
heap-size
location?
root?
heap-value?
heap-set!
heap-ref
get-root-set
read-root
set-root!
simple-root
make-root
with-heap
current-heap
with-roots
4.2 Garbage Collector Exports for GC2
init-allocator
gc:  deref
gc:  alloc-flat
gc:  cons
gc:  first
gc:  rest
gc:  set-first!
gc:  set-rest!
gc:  cons?
gc:  flat?
gc:  closure
gc:  closure-code-ptr
gc:  closure-env-ref
gc:  closure?

4 GC Collector Language, 2🔗ℹ

 #lang plai/gc2/collector package: plai-lib

GC Collector Scheme is based on PLAI. It provides additional procedures and syntax for writing garbage collectors.

4.1 Garbage Collector Interface for GC2🔗ℹ

The GC Collector Scheme language provides the following functions that provide access to the heap and root set:

Returns the size of the heap. The size of the heap is specified by the mutator that uses the garbage collector. See allocator-setup for more information.

procedure

(location? v)  boolean?

  v : any/c
Determines if v is an integer between 0 and (- (heap-size) 1) inclusive.

procedure

(root? v)  boolean?

  v : any/c
Determines if v is a root.

procedure

(heap-value? v)  boolean?

  v : any/c
A value that may be stored on the heap. Roughly corresponds to the contract (or/c boolean? number? symbol? empty?).

procedure

(heap-set! loc val)  void?

  loc : location?
  val : heap-value?
Sets the value at loc to val.

procedure

(heap-ref loc)  heap-value?

  loc : location?
Returns the value at loc.

syntax

(get-root-set)

Returns the current root?s as a list. This returns valid roots only when invoked via the mutator language. Otherwise it returns only what has been set up with with-roots.

Note that if your collector is being invoked via gc:cons or gc:closure, then there may be live data that is not reachable via the result of get-root-set, but that is reachable via the roots passed as arguments to those functions.

procedure

(read-root root)  location?

  root : root?
Returns the location of root.

procedure

(set-root! root loc)  void?

  root : root?
  loc : location?
Updates root to refer to loc.

procedure

(simple-root l)  root?

  l : location?
Makes a root that is initialized with l.

procedure

(make-root name get set)  root?

  name : symbol?
  get : (-> location?)
  set : (-> location? void?)
Creates a new root. When read-root is called, it invokes get and when set-root! is called, it invokes set.

For example, this creates a root that uses the local variable x to hold its location:
(let ([x 1])
  (make-root 'x
             (λ () x)
             (λ (new-x) (set! x new-x))))

syntax

(with-heap heap-expr body-expr ...)

 
  heap-expr : (vectorof heap-value?)
Evaluates each of the body-exprs in a context where the value of heap-expr is used as the heap. Useful in tests:
(test (with-heap (make-vector 20)
        (init-allocator)
        (gc:deref (gc:alloc-flat 2)))
      2)

Bound to the current heap inside of with-heap.

syntax

(with-roots (root-var ...) expr1 expr2 ...)

 
  root-var : location?
Evaluates each of expr1 and the expr2s in in a context with additional roots, one for each of the root-vars. The get-root-set function returns these additional roots. Calling read-root on one of the newly created roots returns the value of the corresponding root-var and calling set-root! mutates the corresponding variable.

This form is intended to be used in test suites for collectors. Since your test suites are not running in the
language, get-root-set returns a list consisting only of the roots it created, not all of the other roots it normally would return. Use with-roots to note specific locations as roots and set up better tests for your GC.

(test (with-heap (make-vector 4)
                 (init-allocator)
                 (define f1 (gc:alloc-flat 1))
                 (define r1 (make-root 'f1
                                       (λ () f1)
                                       (λ (v) (set! f1 v))))
                 (define c1 (gc:cons r1 r1))
                 (with-roots (c1)
                             (gc:deref
                              (gc:first
                               (gc:cons r1 r1)))))
      1)

4.2 Garbage Collector Exports for GC2🔗ℹ

A garbage collector must define the following functions:

procedure

(init-allocator)  void?

init-allocator is called before all other procedures by a mutator. Place any requisite initialization code here.

procedure

(gc:deref loc)  heap-value?

  loc : location?
Given the location of a flat value, this procedure should return that value. If the location does not hold a flat value, this function should signal an error.

procedure

(gc:alloc-flat val)  location?

  val : heap-value?
This procedure should allocate a flat value (number, symbol, boolean, or empty list) on the heap, returning its location (a number). The value should occupy a single heap cell, though you may use additional space to store a tag, etc. You are also welcome to pre-allocate common constants (e.g., the empty list). This procedure may need to perform a garbage-collection. If there is still insufficient space, it should signal an error.

procedure

(gc:cons first rest)  location?

  first : root?
  rest : root?
Given two roots, one for the first and rest values, this procedure must allocate a cons cell on the heap. If there is insufficient space to allocate the cons cell, it should signal an error.

procedure

(gc:first cons-cell)  location?

  cons-cell : location?
If the given location refers to a cons cell, this should return the first field. Otherwise, it should signal an error.

procedure

(gc:rest cons-cell)  location?

  cons-cell : location?
If the given location refers to a cons cell, this should return the rest field. Otherwise, it should signal an error.

procedure

(gc:set-first! cons-cell first-value)  void?

  cons-cell : location?
  first-value : location?
If cons-cell refers to a cons cell, set the head of the cons cell to first-value. Otherwise, signal an error.

procedure

(gc:set-rest! cons-cell rest-value)  void?

  cons-cell : location?
  rest-value : location?
If cons-cell refers to a cons cell, set the tail of the cons cell to rest-value. Otherwise, signal an error.

procedure

(gc:cons? loc)  boolean?

  loc : location?

Returns #true if loc refers to a cons cell. This function should never signal an error.

procedure

(gc:flat? loc)  boolean?

  loc : location?
Returns #true if loc refers to a flat value. This function should never signal an error.

procedure

(gc:closure code-ptr free-vars)  location?

  code-ptr : heap-value?
  free-vars : (listof root?)
Allocates a closure with code-ptr and the free variables in the list free-vars.

procedure

(gc:closure-code-ptr loc)  heap-value?

  loc : location?
Given a location returned from an earlier allocation check to see if it is a closure; if not signal an error. If so, return the code-ptr for that closure.

procedure

(gc:closure-env-ref loc i)  location?

  loc : location?
  i : exact-nonnegative-integer?
Given a location returned from an earlier allocation, check to see if it is a closure; if not signal an error. If so, return the ith variable in the closure (counting from 0).

procedure

(gc:closure? loc)  boolean?

  loc : location?
Determine if a previously allocated location holds a closure. This function will be called only with locations previous returned from an allocating function or passed to set-root!. It should never signal an error.