Felix Garbage Collector with Reference Counting Uploaded

From: John Max Skaller (skaller_at_[hidden])
Date: 2001-05-07 11:45:27

I have just uploaded flx_gc_1_0.zip to the boost files area.

SUMMARY OF FUNCTIONALITY
------------------------

This system provides both reference counting and garbage
collection, and operates with any data structure and plain
pointers (it is 'data transparent'). Finalisation functions
are supported. 

The collector uses a simple mark-sweep algorithm
of complexity 2r+u, where r are the number of reachable objects,
and u is the number of unreachable objects. Meta-information
is stored in a prefix to the client data area, there are currently
5 pointers and a flag :-(

The current version is NOT thread safe.

DISCUSSION
----------

This package is an enhancement of a simple collector originally
designed for the Felix translator. While its operation and 
use is quite simple, some effort is required to construct the
shape objects required to specify the locations of pointers
in a managed type, and to encode the finaliser. for example,
the following struct X_t, which is to be managed, along with 
Y_t:

struct X_t
{
  X_t(X_t *x, Y_t*y) : p_x(x), p_y(y) {}
  X_t *p_x;
  Y_t *p_y;
};

requires the following meta-information to be coded:

static size_t X_offsets[] = 
{
  offsetof(X_t,p_x),
  offsetof(X_t,p_y)
};

gc_shape_t X_shape
(
  sizeof(X_t),
  0, // no finaliser
  sizeof(X_offsets)/sizeof(size_t),
  X_offsets
);

before objects can be allocated by the expression

        new(collector, X_shape) X_t(0,0) 

Roots are set and released by calling

        collector.add_root(p);
        collector.remove_root(p);
        
Collection is effected by calling

        collector.collect()

The collector must be initialised with a pointer to a user constructed
allocator object (which allows any allocator to be used, but only one).
[A simple malloc/free allocator is supplied in the package]

Reference counting is effected either by the low level primitives

        incref(p)
        decref(p)

or by using higher level functions that take (pointers to pointer)
variables
as arguments:

        init_ptr(&v,p); // initialisation
        set_ptr(&v,p); // assignment
        release_ptr(&v); // destructor

which also set the value of the variable safely. There is also
an unsafe function

        destroy(p)

which unconditionally deletes an object, and a function

        reset_shape(p,new_shape)

which can be used to indicate that the type of object encoded
in a storage location has changed (for example, if it is in a union).

Even my simplistic test routine clearly demonstrated to me the
pitfalls of using reference counting and garbage collection together.
Manual reference counting is very hard to get right. The package
probably requires a suitable smart pointer to help get the
counting right.

The type of finaliser used with ref-counting and garbage collection
are usually quite different: destructors of objects in counting
schemes must decrement ref counts of objects the dying object
depends on, whereas with garbage collection, these can be conveniently
forgotten.

Nevertheless, both facilities are included for two reasons.
The first reason is that reference counting can keep total
memory requirements down more easily than a collector,
especially one that must be called explicitly to invoke collection.

The second reason is that resource acquisition and release managed
by construction and destruction may not occur in a timely or
correctly ordered manner without stronger assurances that those
offered by garbage collection.

It is possible to run a counting scheme independently of use
of a collector, provided the collector supports explicit
deletion by the global operator delete. Unfortunately,
this must be viewed as untenable since a ability to
replace operator delete is unique: it is a very scarce
resource. Therefore, the refcounting and collector are
provided together. [Operator delete must NOT be used 
on managed objects anyhow].

OMISSIONS
---------

The current package is incomplete. It does not provide
convenient 'smart pointers', which would make using
the refcounting scheme and collector easier. These need
to be added.

It is possible to use a pointer to a managed object in
a non-managed object: either the pointer is considered
weak (another way exists to reach the object while
the pointer is held in the foreign object), or,
the object must be made a root. At present, this would
create a problem if you wanted to add the pointer to 
two foreign containers, since add_root can only be called
on non-root. [I'm considering a 'root handle' which 
can be used to make a raw pointer into a root, and which
ref counts <grin> so that the root status is revoked only
when the last handle disappears -- this doesn't delete
the object, just removes it as a root :-]

The package also isn't thread safe. However, all the code
is reentrant, so that multiple threads may use separate
collectors safely. I don't believe this is enough,
since it is common practice to create message objects in 
a dispatcher thread, and destroy them after interpretation
in separate worker threads.

PACKAGE DESCRIPTION
-------------------

To unzip this archive, please create a directory named
flx_gc_1_0, and unzip the archive inside it.
Run all scripts immediately inside the directory.

        mkdir flx_gc_1_0
        cd flx_gc_1_0
        unzip ../flx_gc_1_0

To test the collector and ref counting using g++ under 
a unix system, type

        sh unix_script/unix_text

For other platforms, check out this file and do whatever
is appropriate.

Flx_gc depends on the C++ Standard library, and requires
a platform specific adjustment of the aligment constant
_MAX_ALIGN which is set to 4 in flx_gc.hpp.

English documentation is available in the doc directory, 
including full annotated source listings:

        flat html (en_flx_gc_flat.html)
        plain text (en_flx_gc.txt)
        LaTex2e (en_flx_gc.tex) [not tested!]
        web site with frames (en_flx_gc_top.html)

The interscript literate programmed source is in the diractory
lpsrc, file name flx_gc.ipk. The files in the src and test directory
are generated. I cannot apply patches made from those files.
[Please post plain english descriptions of recommendations,
or, if you are really keen, install interscript and work on
the interscript source :-]

-- 
John (Max) Skaller, mailto:skaller_at_[hidden]
10/1 Toxteth Rd Glebe NSW 2037 Australia voice: 61-2-9660-0850
checkout Vyper http://Vyper.sourceforge.net
download Interscript http://Interscript.sourceforge.net