C garbage collector.

[Francois-Rene Rideau]

Dear Tunespeople,
   I've modified jql's GC, and it looks like the little it does work,
but we'd need a scheme interpreter to fully test it (any takers?)
see "http://www.eleves.ens.fr:8080/home/rideau/Tunes/files/rtgc-0.2.tgz".
   Only the more I understand this algorithm, the less I like it.
Surely it can be useful for real-time LISP,
but it has a very high overhead on conventional hardware
because of its read barrier and low garbage detection rate,
and I can't see easy ways to add features to it
without breaking the real-time aspect,
and making all the associated overhead useless:
*particularly* error-recovery (catching memory overflow),
destructors, locality preserving, weak pointers, etc.
   Also, the proposed LLL scheme doesn't need hard real-time GC.
I'd prefer something that works fast most of the time,
and runs a major GC once or twice a day,
when everyone's lunching or sleeping.
   Hence, I think I'll completely redo the GC,
using a tracing method.


Note to Eric:
  if you takeover the LLL and/or Migration pages, please tell us!
  If not, please send me the docs you write!
  Also, I'm never sure if that stuff should be in LLL or Migration!



Here is what I just added to LLL/storage.html:


GARBAGE COLLECTION
<LI>
   Objects will be grouped by page-aligned "segments"
of similarly sized objects.
rounding the size up to keep only 2-5 significant bits,
as a compromise to limit the space wasted as padding
while not overmultiplying the number of groups,
which would increase both lookup time and swiss-cheese syndrom.
<LI>
   Orthogonally to size grouping, objects will be grouped
as being read-only or not, linear or not, containing pointers or not,
having a destructor or not.
Some of these attributes might be perobject meta information instead.
<LI>
   Grouping objects is believed to solve most swiss-cheese syndrom related
problems without the need to compact memory. Still, compacting can be
done during "major GCs", once a day.
<LI>
   Meta-data can be kept as one byte per object,
unless we choose treadmill like methods.
<LI>
   Meta-information might be kept offpage, apart from data,
so as not to uselessly fill cache with random data during GC,
depending on the the nature of the objects;
this is particularly effective when people allocate whole pages, btw.
   It can be
<LI>
   A "first generation" heap will be done as a stack,
perhaps using the hbaker92CONS LazyAlloc paper ideas,
or just the standard Appel thingy.
   Hence, allocation of short-lived objects will be fast,
and can be done purely on registers,
without going through all the hassle implied by above plans
that needs lots of metadata memory access.
<LI>
   We could require all objects to be read-only and/or linear,
but for a special reference type;
this would ease object many things
(object identity, write barrier, and many other things).
<LI>
   Particularly, back-pointers from non-linear objects to linear ones
can be done only through a special set of such reference objects anyway.


Notes:

<LI>destructors, weak pointers, migration handlers,
 are all particular cases of special semantics to execute at
 special memory management events,
 like reclaiming of object space, writing the checkpoint,
 restoring from checkpoint, migrating in or out.
 They should be provided a uniform interface,
 but I don't see how it can be made but in ad-hoc ways.

<LI>A copying GC would color destructible objects,
 and activate destructors if they were not triggered since one flip/run/etc.

<LI>Generic functions to access objects might be very costly,
 due to various read or write barriers.
 However, low-level code can be specialized to jump over the barrier,
 or pay part of the fee only,
 when the high-level language (or low-level hacker) could prove that
 the (whole) barrier isn't needed.

<LI>There are lots of things whose average case is good while the
 worst case wastes a lot of space. Such space should be *reserved*
 in virtual memory, so as to ensure the system won't crash even on
 worst-case conditions; but the system will be tuned to work best
 on average conditions.

<LI>the exact details of the above plan, as suit most our programs,
 can only be determined through experimentation.
 Particularly note that it is independent from the GC method being used
 (mark&sweep, mark&don't sweep, stop&copy, hbaker rtgc, etc).




PERSISTENCE

<LI>Persistence can be done at the page level.
<LI>Checkpoints will be triggered manually or by the clock;
when triggered, a checkpoint will wait for next minor GC.
a checkpoint can also be <EM>forced</EM>, in which case it
will be done at next safe point (that is, almost in real-time),
with or without triggering GC;
a timeout will transform triggered checkpoint into forced checkpoint,
perhaps by forcing a GC.
<LI>A checkpoint logs the modified pages;
it first saves the metadata for the pages,
then writes a the contents of the pages compressed with
an appropriate algorithm, that uses the metadata as a hint,
but doesn't waste too much time at that, either,
so that checkpointing performance stays disk-driven.
<LI>If the above code is well written, a major GC could be achieved
by restoring a checkpoint just after saving it!!!
<LI>Checkpointing can be done concurrently with running
if we can control paging and hide the pages with copy-on-write.
OTOP checkpointing must block the process :( :( :(


OTOP tricks for persistence:

<LI>If system dirty page bits are not available (e.g. OTOP),
then they should be manually emulated by software,
with a write barrier :( :(

<LI><EM>BEFORE</EM> a checkpoint, the previous checkpoint will be
 committed in case it hasn't been yet.
 If it wasn't committed, then the checkpoint before it was still valid,
 so everything's fine.
 This allows the process to continue to run after checkpoint writes
 were scheduled, unless we *really* need to stop.

<LI>The problem is that we need <EM>two</EM> fsync() to commit the changes:
 one for all the data, one for atomically committing the super-block
 after everything's done.
 What we may do, if not satisfied with the previous checkpoint,
 is to schedule the fsync() after we let some time to the unix kernel,
 so that we can <EM>hope</EM> that fsync() won't stop the process.



--    ,                                         ,           _ v    ~  ^  --
-- Fare -- rideau@clipper.ens.fr -- Francois-Rene Rideau -- +)ang-Vu Ban --
--                                      '                   / .          --
Join the TUNES project for a computing system based on computing freedom !
                 TUNES is a Useful, Not Expedient System
WWW page at URL: "http://www.eleves.ens.fr:8080/home/rideau/Tunes/"