readme

内存垃圾收集程序

Copyright 1988, 1989 Hans-J. Boehm, Alan J. Demers
This material may be freely distributed, provided this notice is retained.
This material is provided as is, with no warranty expressed or implied.
Use at your own risk.

  This collector was developed as a part of research projects supported in
part by the National Science Foundation and the Defense Advance Research
Projects Agency.  The SPARC specific code was contributed by Mark Weiser
([e-mail]).  The Encore Multimax modifications were supplied by
Kevin Kenny ([e-mail]).  The adaptation to the RT is largely due
to Vernon Lee, on machines made available by IBM. (Blame for misinstallation
of those modifications goes to the first author, however.) Some of the
improvements incorporated in this version were suggested by David Chase at
Olivetti Research.

  This is intended to be a general purpose, garbage collecting storage
allocator.  The algorithms used are described in:

Boehm, H., and M. Weiser, "Garbage Collection in an Uncooperative Environment",
Software Practice & Experience, September 1988, pp. 807-820.

  Many of the ideas underlying the collector have previously been explored
by others.  (We discovered recently that Doug McIlroy wrote a more or less
similar collector that is part of version 8 UNIX (tm).)  However none of this
work appears to have been widely disseminated.

  The tools for detecting storage leaks described in the above paper
are not included here.  There is some hope that they might be released
by Xerox in the future.

  Since the collector does not require pointers to be tagged, it does not
attempt to insure that all inaccessible storage is reclaimed.  However,
in our experience, it is typically more successful at reclaiming unused
memory than most C programs using explicit deallocation.

  In the following, an "object" is defined to be a region of memory allocated
by the routines described below.  

  Any objects not intended to be collected must be pointed to either
from other such accessible objects, or from the registers,
stack, data, or statically allocated bss segments.  It is usually assumed
that all such pointers point to the beginning of the object.  (This does
not disallow interior pointers; it simply requires that there must be a
pointer to the beginning of every accessible object, in addition to any
interior pointers.  Conditionally compiled code to check for pointers to the
interiors of objects is supplied.  As explained in "runtime.h", this
may create other problems, however.)
  Note that pointers inside memory allocated by the standard "malloc" are not
seen by the garbage collector.  Thus objects pointed to only from such a
region may be prematurely deallocated.  It is thus suggested that the
standard "malloc" be used only for memory regions, such as I/O buffers, that
are guaranteed not to contain pointers.  Pointers in C language automatic,
static, or register variables, are correctly recognized.
  The collector is designed to minimize stack growth if link fields inside
structures are allocated first.  (Normally only linked lists of lengths
exceeding about 100000 will cause this to be noticable.)
  Signal processing for most signals is deferred during collection. (This
is not done on the MIPS machine under System V, where this seem to require
many system calls.  If signal handling is desired, the user will probably
find it necessary to suspend those signals that are actually used.)
  As distributed, the collector produces garbage collection statistics
during every collection.  Once the collector is known to operate properly,
these can be suppressed by undefining the appropriate macros at the top
of "runtime.h".  (The given statistics exhibit a few peculiarities.
Things don't appear to add up for a variety of reasons, most notably
fragmentation losses.  These are probably much more significant for the
contrived program "test.c" than for your application.)
  The collector currently is designed to run essentially unmodified on
the following machines:

	    Sun 3
	    Sun 4  (except under some versions of 3.2)
	    Vax under Berkeley UNIX
	    Sequent Symmetry  (no concurrency)
	    Encore Multimax   (no concurrency)
	    MIPS M/120 (and presumably M/2000) (System V)
	    IBM PC/RT  (Berkeley UNIX)

  For these machines you should check the beginning of runtime.h
to verify that the machine type is correctly defined.  On an Encore Multimax,
MIPS M/120, or a PC/RT, you will also need to make changes to the
Makefile, as described by comments there.
  In all cases we assume that pointer alignment is consistent with that
enforced by the standard C compilers.  If you use a nonstandard compiler
you may have to adjust the alignment parameters defined in runtime.h.
  On a MIPS machine or PC/RT, we assume that no calls to sbrk occur during a
collection. (This is necessary due to the way stack expansion works on these
machines.) This may become false if certain kinds of I/O calls are inserted
into the collector.

  For machines not already mentioned, the following are likely to require
change:

1.  The parameters at the top of runtime.h and the definition of
    TMP_POINTER_MASK further down in the same file.
2.  mach_dep.c.  This includes routines to mark from registers,
    and to save registers not normally preserved by the C compiler.
    (The latter should not be necessary unless assembly language calls
    to the allocator are used.)  If your machine does not allow in-line
    assembly code, this may be replaced by a .s file (as we did for the MIPS
    machine and the PC/RT).

  For a different UN*X version or different machine using the Motorola 68000,
Vax, SPARC, 80386, NS 32000, PC/RT, or MIPS architecture, it should frequently
suffice to change definitions in runtime.h.

  The following routines are intended to be directly called by the user.
Note that only gc_malloc and gc_init are necessary.  The remaining routines
are used solely to enhance performance.  It is suggested that they be used
only after initial debugging.

1)  gc_init()
    - called once before allocation to initialize the collector.

2)  gc_malloc(nbytes)
    - allocate an object of size nbytes.  Unlike malloc, the object is
      cleared before being returned to the user.  (For even better performance,
      it may help to expand the relevant part of gc_malloc in line.
      This is done by the Russell compiler, for example.)  Gc_malloc will
      invoke the garbage collector when it determines this to be appropriate.
      (A number of previous collector bugs resulted in objects not getting
      completely cleared.  We claim these are all fixed.  But if you encounter
      problems, this is a likely source to check for.  The collector tries
      hard to avoid clearing any words that it doesn't have to.  Thus this
      is a bit subtle.)
      

3)  gc_malloc_atomic(nbytes)
    - allocate an object of size nbytes that is guaranteed not to contain any
      pointers.  The returned object is not guaranteed to be cleeared.
      (Can always be replaced by gc_malloc, but results in faster collection
      times.  The collector will probably run faster if large character
      arrays, etc. are allocated with gc_malloc_atomic than if they are
      statically allocated.)

4)  gc_free(object)
    - explicitly deallocate an object returned by gc_malloc or
      gc_malloc_atomic.  Not necessary, but can be used to minimize
      collections if performance is critical.

5)  expand_hp(number_of_4K_blocks)
    - Explicitly increase the heap size.  (This is normally done automatically
      if a garbage collection failed to reclaim enough memory.  Explicit
      calls to expand_hp may prevent unnecessarily frequent collections at
      program startup.)

  The global variable dont_gc can be set to a non-zero value to inhibit
collections, e.g. during a time-critical section of code.  (This may cause
otherwise unnecessary exansion of the process' memory.)
  The variable non_gc_bytes, which is normally 0, may be changed to reflect
the amount of memory allocated by the above routines that should not be
considered as a candidate for collection.  Collections are inhibited
if this exceeds a given fraction (currently 3/4) of the total heap size.
The heap is simply expanded instead.  Careless use may, of course, result
in excessive memory consumption.
  Some additional tuning is possible through the parameters defined
near the top of runtime.h.
  
  The two gc_malloc routines may be declared to return a suitable pointer
type.  It is not intended that runtime.h be included by the user program.
If only gc_malloc is intended to be used, it might be appropriate to define:

#define malloc(n) gc_malloc(n)
#define calloc(m,n) gc_malloc((m)*(n))

  No attempt is made to use obscure names for garbage collector routines
and data structures.  Name conflicts are possible.  (Running "nm gc.o"
should identify names to be avoided.)

  Please address bug reports to [e-mail].