This README provides an overview of the precise GC interface used by
Racket. The header files "gc2.h" and "gc2_dump.h" provide additional
API documentation.

GC Interface
------------

The GC interface for Racket is designed to support precise collection
with both moving and non-moving collectors. Generational and
incremental collectors must rely on hardware-based memory protection
for their implementation (to detect writes into old objects, etc.).

As a general rule, all pointers to collectable objects reference the
beginning of the object (i.e., the pointer is never into the interior
of the object). The exception is that a pointer may reference the
interior of an "Interior" object, but Racket allocates such objects
infrequently, and only as relatively large objects.

All allocated memory must be longword-aligned. For architectures where
`double' values must be 8-byte aligned, the GC must provide 8-byte
aligned memory in response to an allocation request for a memory size
divisible by 8. Except for atomic memory, allocated objects must be
completely initialized with 0s.

Memory locations that hold pointers to collectable objects can also
hold pointers to non-collectable memory. They may also contain a
"fixnum" integer, where the lowest bit is set (so it could never be
confused with a longword-aligned pointer). Thus, the collector must
distinguish between longword-aligned pointers into collected memory
regions and all other pointers.

At any point when the allocator/collector is invoked, Racket will
have set the GC_variable_stack variable to indicate a chain of local
pointer variables on the stack (i.e., both the chain of record and the
pointer variables themselves are on the stack). The GC_variable_stack
global points to a value of the form

     struct {
        void *next_frame;
        intptr_t frame_size;
        void **pointers[...];
     }

where the size of `pointers' is indicated by `frame_size'. Each
element of `pointers' is usually the address of a pointer of the
stack. It can also be 0, in which case the next `pointers' element is
an integer, and the following `pointers' element is a pointer to an
array of the indicated size. (The three `pointers' slots contribute 3
towards the value of `frame_size'.)

The `next_frame' field in the structure gives the address of the next
frame on the stack, and so on. The garbage collector should follow the
chain of frames, adjusting pointers for copying collection, until it
reaches a frame that is the same as the value returned by
GC_get_thread_stack_base() (which is supplied by Racket).

More generally, GC_mark_variable_stack() can be used to GC a stack
that has been copied into the heap. See below for more details.

Marking and Moving Objects
--------------------------

Cooperation between the garbage collector's movement of objects and
Racket's view of object shapes (pointers versus non-pointers) is
mediated by "mark" and "fixup" functions:

 * The "mark" pass traverses objects in the heap, potentially moving
   them and adjusting references.

 * An optional extra "fixup" pass further adjusts references to moved
   objects.

The mark and fixup steps are exposed by gcMARK and gcFIXUP macros that
are provided by the collector. In addition, the collector provides a
GC_resolve operation, which converts an object's old address to a new
one in the case that the object is being moved; given an object's new
address GC_resolve returns the same address. A GC_is_marked operation
reports whether an object at its old address has been marked; it works
only on old addresses.

Normally, the mark function for an object is called only when the
object is first marked in a given GC pass. With generational
collection, the mark function can be called for an old-generation
object if it potentially changed since a previous collection; still,
the mark function will be called only once during that collection, so
it's as if the object were in the new generation. With incremental
collection, however, a macro procedure can be called due to changes
even if the object is already incrementally marked as an
old-generaiton object. The GC_current_mode() function reports the
current mode for a given call to the marking function.

Memory Kinds
------------

Racket allocates the following kinds of memory objects:

 * Tagged - The object starts with a `short' integer containing the
   tag, but the tag will always be less than 256. After requesting
   memory from the GC, Racket installs the tag before performing any
   other memory operation. Racket provides three functions for each tag:

    o an operation for obtaining the value's size in words (not
      bytes!);

    o an operation for marking pointers within the object; and

    o an operation for another fixup pass.

   The mark and fixup procedures use the gcMARK and gcFIXUP macros
   provided by the collector. The mark and fixup operations also
   return the size of the object, like the size procedure, unless
   GC_NO_SIZE_NEEDED_FROM_PROCS is defined.

 * Atomic - The allocated object contains no pointers to other
   allocated objects.

 * Atomic Tagged - Like a tagged object, but the mark and fixup
   procedures are no-ops.

 * Array - The allocated object is an array of pointers to other
   allocated objects.

 * Pair - specialization of Tagged to pairs.

 * Interior Array - Like array objects, but pointers to the object can
   reference its interior, rather than just the start of the object,
   and the object never moves. Such pointers will always be
   longword-aligned. Racket allocates interior objects infrequently,
   and only as relatively large objects.

 * Weak Box - The object has the following initial structure:

     struct {
       short tag;
       short filler_used_for_hashing;
       void *val;
     }

   Racket reads the `tag' and `val' fields, and both reads and
   writes the `filler_used_for_hashing' field. Racket also provides
   the value to be used for `tag', via GC_init_type_tags(). The reason
   this structure is implemented by the collector is to handle the
   special behavior of the weak link.

   Racket can change `val' at any time; when a collection happens,
   if the object in `val' is collectable and is collected, then `val'
   is zeroed.  The `val' pointer must be updated by the collector if
   the object it refers to is moved by the collector, but it does not
   otherwise keep an object from being collected.

   The interface for creating weak boxes is

    void *GC_malloc_weak_box(void *p, void **secondary, int soffset);

   If the `secondary' argument is not NULL, it points to an auxiliary
   address that should be zeroed (by the collector) whenever `val' is
   zeroed. To allow zeroing in the interior of an allocated pointer,
   the zero-out address is determined by `secondary + soffset'. The
   memory referenced by `secondary' is kept live as long as it isn't
   zeroed by its registration in the weak box, but when the content of
   `secondary + soffset' is zeroed, the `secondary' pointer in the
   weak box should also be zeroed.

 * Late Weak Box - A weak box that holds onto its reference until
   level-2 finalizers are queued (see below). Late weak boxes are
   created with GC_malloc_late_weak_box().

 * Weak Array - The object has the following structure:

     struct {
       intptr_t gc_private[4];
       intptr_t array[...];
     }

   The gc_private array contains collector-private values that are
   neither read nor written by Racket. The array field is an array
   of weak pointers to collectable objects. See GC_malloc_weak_array()
   in gc2.h for more details.

 * Ephemeron - The object has the following initial structure:

     struct {
       short tag;
       short filler_used_for_hashing;
       void *key;
       void *val;
     }

   See "Weak Box" above. The difference for an ephemeron is that
   the ephemeron must hold `val' strongly as long as the wealy-held
   `key' is accessible --- where `val' itself isn't traced unless
   both the ephemeron and `key' are reachable. (In particular,
   a reference from `val' to `key' doesn't prevent collection of
   `key'.)

 * Immobile box - a longword-sized box that can contain a reference to
   a collectable object, but it not itself collectable or movable. An
   immobile box lets Racket refer to a collectable object (through
   one indirection) from memory that is not traversed by the
   collector.

   The GC_malloc_immobile_box() function creates an immobile box with
   an initial value:

     void **GC_malloc_immobile_box(void *p);

   Immobile boxes must be explicitly freed with the
   GC_free_immobile_box() function:

     void GC_free_immobile_box(void **b);

Of course, an implementation of the collector may collapse any of
these categories internally.

Finalization
------------

The finalization interface is

  void GC_set_finalizer(void *p, int tagged, int level,
                        GC_finalization_proc f, void *data,
                        GC_finalization_proc *oldf, void **olddata);

This function installs a finalizer to be queued for invocation when
`p' would otherwise be collected. All ready finalizers should be
called at the end of a collection. (A finalization can trigger calls
back to the collector, but such a collection will not run more
finalizers.) The `p' argument must normally point to the beginning of
a tagged (including atomic or pair) object; that is, `tagged' is
currently required to be non-zero.

The `level' argument refers to an ordering of finalizers. It can be 1,
2, or 3. During a collection, level 1 finalizers are queued first,
then all objects queued for finalization are marked as live and
traversed. Next, level 2 finalizers are queued in the same way. Thus,
if a level 1 object refers to a level 2 object, the level 1 object
will be queued for finalization, and only sometime after the finalizer
is run and the object is again no longer referenced can the level 2
object be finalized. Finally, level 3 finalizers are queued.

The `f' and `data' arguments define the finalizer closure to be called
for `p'. If a finalizer is already installed for `p', it is replaced,
and `oldf' and `olddata' are filled with the old closure. If `f' is
NULL, any existing finalizer is removed and no new one is
installed. The single-callback rule applies across level 1 and level
2 finalizers (but scheme_register_finalizer(), etc., in "salloc.c" can
merge them).

The `p' object isn't actually collected when a finalizer is queued,
since the finalizer will receive `p' as an argument. Weak references
are cleared after level 1 fnalizers are queued, while "late weak box"
references are cleared after level 2 finalizers are clear.

Functions versus Macros
-----------------------

Any function in the defined interface can be implemented as a
macro. Indeed, gcMARK() and gcFIXUP() are expected to be
macros.

Due to the way that the Racket and GRacket code is generated for
precise collection, the header file gc2.h must allow multiple
inclusion in two different phases. If the pre-processor symbol
GC2_JUST_MACROS is defined, then the header should only define
macros. If GC2_JUST_MACROS is not defined, then the header should
define all typedefs, function proptypes, and macros.