GC

Eric W. Biederman ebiederm@cse.unl.edu
Thu, 4 Apr 1996 10:21:19 -0600


I am so overloaded right now that I really shouldn't volunteer for
anything, but I find garbage collection intrinsically fun.  So I herby
volunteer to help with the garbage collector for the Forth/LLL thing
you are working on now when a base of code is written.

I while back I began a port of RPL (I may get back to it too) and did
a lot of research into garbage collection. So while I'm not an expert
I know what I'm talking about. 

The only requirement I wish to impose upon code is that pointer in
garbage collected structures be word aligned (this may be relaxed),
and the structures always be typesafe. None of the use pointer as
interger tangle if you please.  Type tagged structures are alright but
not required. 

Please note that relocating and migrating structures is just as
migrating code and possibly more so.  My intention is to use a
possibly beefed up form of relocation/migration information to allow
the garbage collector to be able to do it's work.  

Regarding return value of functions in threaded code, that is to be
garbabe collected.  Threaded code is very much a special case for a
garbage collector, and should be treated as such.  There is the
interesting case that threaded code could be partially collected.
That is if nothing references the top of the piece of code there is no
reason to preserve it.  The other option is for a traversal/collection
order that garantees that if there is a pointer to the top of a
threaded code chunk it will be found before the chunk is moved.  A
third alternative is to split up and recombind threaded in possibly
different ways as it travels through.

I would propose the same techniques for compiled code but that has
the obvious difficulty that I couldn't get my relocation information.
That one bears a little more thought.

Note except for reducing memory fragmentation there is not a good
reason for a garbage collector to have any knowledge of the code or
the type of structures implemented, or have a need to move objects.
While this is theoretically true and the basis of all C garbage
collectors, I want to steer away from this if possible in tunes.

With regards to using sp as the code pointer.  It actually sounds like
a decent idea (assuming you're not using the same stack for
interrupts)  All that would be required would be a special threaded
return instruction that would read the real return address off of
you're real stack.

[ a fun quible, means nothing ]
>   It might be anachronistic of me, but I tend to want to look at the low
> level code sometimes, as that may be the only way to solve a particularly
> nasty problem (in porting joe to QNX, I ended up having to look at the
> generated machine code to see that the frame pointer was being trashed
> somehow and tracking it back to the problem).  Have you ever SEEN code
> output from a compiler (say, like GCC)?  It's not readable by any standards. 
> The Unix weenies tend to say "Well, assembly isn't for humans."  

Actually I've never had that problem, the assembly output from gcc is
quite readable.  But ususally I don't have to type gcc -S to know what
assembly has been generated either. 


[gotta go got a test now, tah tah]
Eric