generational GC.

[William.Lott@AMIRANDA.SLISP.CS.CMU.EDU]

So I'm been thinking about generation GC.  And after talking with Rob and
Bill about various things, I've come up with the following:

First, the memory layout:

Divide memory into some number of generations (Rob feels that 3 is a good
number).

Split each generation into three spaces:
  - Scavenged
  - Unscavenged
  - Code

Each space is actually two spaces: a from-space and a to-space.  But as
only one half of each space is active at any given time (except during GC)
I'll just refer to them as being singular.

The Scavenged space is for objects that must be scavenged, like symbols and
conses.  The unscavenged space is for objects that do not have to be
scavenged, like bit-vectors and strings.  The code space is for code
objects.

Separating code from the other spaces wins in several ways:
 - Everything in the Scavenged space is fully scavengable.
 - Code objects are never modified, so we don't have to worry about storing
   pointers from a younger generation into them.
 - We can limit pages with the execute protection to those that actually
   have code on them.

Laying out the memory is the easy part.  The remaining questions are:

 - When do you flip a generation?
 - When do you tenure a generation?
 - How do you handle forward references?
 - What does the GC lisp function do?
 - What does PURIFY do?

As for when to flip or tenure, I suggest the following (primarily because
it would be easy to implement):

  Store with each generation a flip and a tenure threshold.  When the
  amount of storage used by that generation exceeds the flip threshold,
  initiate a GC for that generation.  If the amount of storage in use is
  also larger than the tenure threshold, then copy live objects into the
  next generation, otherwise copy them into the other half of this
  generation.  Set the flip threshold to the amount of storage in use plus
  some constant, just like we do with *gc-trigger* now.  (Note: if we just
  tenured this generation, the bytes in use by it will be zero.)  Tenuring
  a generation might cause the next generation to overflow it's flip
  threshold, so we have to iterate.

I prefer an explicit check for overflowing the flip threshold inside
allocators instead of a guard page for several reasons.  The youngest
generation is going to fill up much more often, so we will be taking
signals much more often.  All these signals flying around is going to make
debugging a nightmare, and will probably seriously degrade the performance.
We can get away with it now, because we GC so infrequently.

I just though of a problem:  If one generation fills up and triggers a
tenure, we end up coping all the live objects in that generation into the
next generation.  If that fills up the next generation and triggers a
tenure, we end up coping all those objects again.  And potentially again.
But tenures should be infrequent, so maybe this doesn't matter.

As for how to deal with references to newer objects, I suggest the
following (primarily because it will work in the presence of interrupts):

  We change all the VOPs that store descriptor values into other objects to
  instead of just using the store-word instruction themselves, to call an
  assembly routine with the object being modified, the offset into that
  object, and the value being written as arguments.  (For common ones, we
  can make the offset in the object implicit in which assembly routine we
  call.)  The assembly routine checks the two pointers to see if everything
  is okay.  If so, it just does the store and returns.  If not, it stores
  the address being modified in an array associated with the generation of
  the stored pointer.  When a generation is GCed, all the addresses listed
  in this array are fixed up, but the array is preserved.  When a generation
  is tenured, all the entries in this array are checked to see if refered to
  object has become as old as the refering object.  If so, the entry is
  deleted.  If not, the entry is moved to the next generation.  If any of
  these arrays every becomes full, we should probably tenure that
  generation right then and there to try to flush as many entries as
  possible.

This will work in the presences of interrupts because we can make the
assembly routine pseudo-atomic.

As for what GC and PURIFY should do, I suggest the following:

  GC should take an optional argument specifying what generation to GC.
  When GC is explicitly called, it forces a flip of specified generation
  and a tenure of all younger generations up to the specified generation.
  The default for this argument would be the second generation, so the
  effect of calling (GC) would be to flush out the youngest generation.

  Purify would move everything into the oldest generation, performing
  whatever kinds of localify operations we want.  Note: calling GC with the
  generation number for the oldest generation would be the same as a purify
  without the localify.

Comments, etc?

-William