Memory management (Re: cvs commit: ...)
Marcin 'Qrczak' Kowalczyk
qrczak at knm.org.pl
Fri Feb 11 07:11:01 EST 2005
"Simon Marlow" <simonmar at microsoft.com> writes:
> What makes it easy for us is that we can make dynamically growable
> arrays quite easily by chaining blocks from the block allocator.
> How do you do memory management in your system?
I have a two-generation copying GC. During GC, locations pointing
to objects to be saved are pushed onto an array which is resized on
demand. This arranges saved objects in depth-first order, rather than
breadth-first as with the classical Cheney loop that GHC uses.
A write barrier used for most kinds of mutable objects pushes changed
locations residing in non-young objects (i.e. in old objects and
static objects) to the same array, only during evaluation rather than
during GC, so they become additional roots at the next minor GC.
A different write barrier is used for resizable arrays and threads,
and this is what I meant in the comment. The contents of arrays are
allocated with malloc and may be reallocated when the array is
resized. This means that the above write barrier can't be used to
register changed locations inside arrays, as they can become invalid
before GC. So instead I used to register pointers to changed arrays
themselves, on a separate array (not resizable because I just forced
a GC when it gets full), and they were scanned in whole during GC.
This caused two problems. When pushing a changed array, I checked
if it's one of 3 most recently changed arrays, to avoid scanning it
multiple times when several of its locations are changed. This didn't
protect against repeated scanning of the same array if 3 other arrays
have been changed between two changes to the given array. And when
at one point I had to mark two changed arrays at once, in a way which
avoids a GC exactly between these changes, this was getting more ugly.
I used a different approach for threads. They don't use the standard
write barrier for two reasons. The stack of a thread may be very
large, so I wanted to avoid pushing addresses of all stack slots onto
the stack of changed locations. And threads were manipulated in some
C code where GC occurring in the middle would be inconvenient.
So instead of pushing all locations of a thread object or its stack
when GC saves it, threads are threaded (argh! an array of changed
arrays, a stack of stack locations, and now threading threads...)
in a list. The list is examined after the regular part of the GC,
threads on the list and objects pointed to by them are saved, which may
indirectly cause more threads to be put on the list, and this proceeds
until the list becomes empty. Non-young thread objects whose contents
are changed are also put on the list, so they are scanned during
This worked well, so I generalized the second approach and now it's
used for arrays too.
__("< Marcin Kowalczyk
\__/ qrczak at knm.org.pl
More information about the Cvs-ghc