Path: utzoo!utgpu!news-server.csri.toronto.edu!bonnie.concordia.ca!uunet!cis.ohio-state.edu!ucbvax!hplabs!otter.hpl.hp.com!hpltoad!cdollin!kers
From: kers@hplb.hpl.hp.com (Chris Dollin)
Newsgroups: comp.lang.lisp
Subject: avoiding the retention of trash
Message-ID: <KERS.91Jun13120231@cdollin.hpl.hp.com>
Date: 13 Jun 91 11:02:31 GMT
Sender: news@hplb.hpl.hp.com (Usenet News Administrator)
Distribution: comp
Organization: Hewlett-Packard Laboratories, Bristol, UK.
Lines: 73
Nntp-Posting-Host: cdollin.hpl.hp.com


I'm implementing a Pop-like language (for the purposes of this discussion, we
can treat Pop as a Lisp-like language), and have hit a worrying possible
problem with garbage collection; or, more exactly, with garbage
*non*-collection. 

It goes like this. On entry to a procedure, a frame is allocated from the
current stack chunk, with enough room to hold all the local variables of the
procedure. (It doesn't make any essential difference if some locals are in
registers; as it happens, the current implementation is a byte-coded virtual
machine, so it's not an issue.) 

Suppose a garbage collection occurs before all the stack slots have been filled
(for example, in an initialisation expression). I can ensure that all the
as-yet unfilled slots have ``sensible'' values (ie do not hold random garbage
that can crash the collector or corrupt store), *but* they may be holding on to
store which was only referred to by a previous use of that stack slot. For
example:

    define procedure make_trash() as
        val pad = 42;
        val junk = { repeat 100000 times false endrepeat }; ;;; make big vector
    enddefine;

    define procedure caught_out() as
        val x = expression_invoking_gc();
        val y = 42;
    enddefine;
 
    define procedure main() as
        make_trash();
        caught_out()
    enddefine;

When caught_out runs, the y slot will be holding on to the big vector allocated
by make_trash.

Now, for procedures running toward the tip of the call tree this may not be too
serious; the locals will probably be overwritten soon, and the next GC will
reclaim the store. But procedures deeper in the stack may *also* be holding on
to dead store - and they won't let go for quite a while.

So, question 1: how much of a problem is this?

Question 2: if it is a problem, how do I solve it? I can think of several
possible solutions:

[a] On procedure entry, zap all local slots with safe values (like numeric 0,
or nil, or false). Cost: every entry is slowed down by the zapping.

[b] Don't allocate locals all at once: allocate them one at a time, when
they're filled. Cost: allocation is no longer as simple as a simple Store
Local, and loops with local declarations pay each time round the body.

[c] Shortly after a local becomes unused (ie, there are no further references
to it), zap it (unnecessary if the compiler can prove it's not a heap value).
In the limit, zap them all at exit. Cost: much like [1], but possibly easier to
optimise. Loops are still a problem.

[d] Record the live ranges of each stack slot and bind into the procedure a
mapping from code position to active ranges. The GC then knows where the *real*
top-of-stack is, and avoids scanning unused slots. Cost: more work for the GC
scanning frames, more work for the compiler in setting up the information, and
store is required (presumably in the procedure header) to store the
description.

Any advice, references, assurances? I'm particularly interested in solutions
that apply when running native code, not interpreted byte-codes, as I plan to
move to a native-code compiler sometime during the next year.
--

Regards, Kers | "Once   I would have been glad   to have made your acquaintance
Renaissance:  | Now   I feel the danger   brought about   by circumstance."