[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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
Split each generation into three spaces:
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
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
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.