4 GC Collector Language, 2
| #lang plai/gc2/collector | package: plai |
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
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.
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
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
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.
Returns the location of root.
Updates root to refer to loc.
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:
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)
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) (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.
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.
If the given location refers to a cons cell, this should return the first
field. Otherwise, it should signal an error.
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
loc : location?
Returns #true if loc refers to a cons cell. This function should never signal an error.
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. Uf 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.