2 GC Collector Scheme
GC Collector Scheme is based on PLAI Scheme. It provides
additional procedures and syntax for writing garbage collectors.
2.1 Garbage Collector Interface
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.
Determines if
v is an integer between
0 and
(- (heap-size) 1) inclusive.
Determines if v is a root.
Sets the value at loc to val.
Returns the value at loc.
Returns the current roots as a list. Local roots are created for the
identifiers id as well.
Returns the location of root.
Updates the root to reference the given location.
Given a closure stored on the heap, returns a list of the roots reachable
from the closure’s environment. If proc is not reachable, the
empty list is returned.
Evaluates each of the body-exprs in a context where
the value of heap-expr is used as the heap. Useful in
tests:
(with-roots roots-expr expr1 expr2 ...)
|
| |
|
Evaluates each of expr1 and the expr2s in
in a context with the result of roots-expr
as additional roots.
This function 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 this function to note specific locations as roots
and set up better tests for your GC.
2.2 Garbage Collector Exports
A garbage collector must define the following functions:
init-allocator is called before all other procedures by a
mutator. Place any requisite initialization code here.
Given the location of a flat Scheme value, this procedure should return that
value. If the location does not hold a flat value, this function should signal
an error.
This procedure should allocate a flat Scheme value (number, symbol, boolean,
closure 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.
Note that closures are flat values. The environment of a closure is internally
managed, but contains references to values on the heap. Therefore, during
garbage collection, the environment of reachable closures must be updated. The
language exposes the environment via the procedure-roots function.
Given the location of 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.
If cons-cell refers to a cons cell, set the head of the cons cell to
first-value. Otherwise, signal an error.
If cons-cell refers to a cons cell, set the tail of the cons cell to
rest-value. Otherwise, signal an error.
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.