On Jul 16, 2005, at 2:24, Nattfodd wrote:
Hi,
I've produced a new document on GMC (Generational Mark & Compact), the
GC I'm trying to implement as a Summer of Code project. It's called gmc
for dummies and I hope it's plainly understandable (if not, tell me so
and I'll try to make it better). It should explain how things will
hopefully work.
It's here :
http://perso.ens-lyon.fr/alexandre.buisse/divers/gmc_for_dummies.pod
This is not quite the scheme, we were pondering in previous mail and
IRC.
1) pmc_bodies have to be variable sized
2) the scheme is missing the invariant we keep:
C<< &younger_body < &older_body >>
ad 1)
a PMC is a 2 word structure { PMC_BODY *pmc_body; VTABLE *vtable }
a pmc_body of Integer PMC is eventually just { INTVAL int_val }, of a
Float PMC it's the double num_val,
a pmc_body of an object with 2 attributes is:
{ INTVAL n_attr; PMC *class; PMC *attr1; PMC *attr2 }
and a pmc_body of the Hash PMC is basically just the Hash structure w/o
any further indirections...
During the transition phase all pmc_bodies still have an 'UINTVAL
flags' field.
The gmc_header that is prepended to all pmc_bodies has a PMC *back_ptr
and gc flags + some type flags that identify the following PMC body for
gc operations. We need the size of the body for walking the pmc_body
memory and we have to mark the contents of the body, if any.
ad 2)
The free generation is lowest in memory followed by the youngest
generation, the oldest objects have highest memory addresses. Please
note: this invariant exists in the pmc_body area. Therefore the mark GC
operation is one pass:
- mark the root set
- walk the pmc_bodies from left (lowest mem) to right
- if the pmc_body is alive mark it's contents (if any) and proceed
- if the pmc_body isn't marked alive, it's dead
There is no need for any extra todo-list to mark the children of
objects.
We keep the invariant by several means:
a) aggregates/containers are allocated from the left of free
b) non-aggregates are allocated from the right of free
(with a) + b) containers already have their contents at higher
memory addresses)
c) a write barrier checks pointer stores into aggregates (by just
comparing 2 memory addresses - basically)
we can do either:
- make aggregate younger (move to left)
- make stored-into object older (move to right)
- remember in IGP
d) if we have to extend the allocation area, we usually we'll have to
move all existing objects "up", either by a full GC run or by just
copying, because you'll get usually higher memory regions from the OS.
These are of course just my ideas, how GMC could operate.
leo
