▼Programming Languages:   Application and Interpretation
►4 GC Collector Language, 2
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
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?
  top  ← prev  up  next → 

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:

procedure

(heap-size) → exact-nonnegative-integer?

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)

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

#lang plai/gc2/mutator

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.

  top  ← prev  up  next →