[gclist] Re: gclist-digest V2 #110

[David Chase]

>> >If I were the on the development team, it would not be difficult 
>> >to decide whether I want to spend more time now debugging a precise
>> >collector where I have control over all aspects of the problem

At 08:34 AM 1/22/98 -0600, Arch Robison wrote:
>	2) Given my track record on writing perfect code, it was likely
>	   that the complicated technique was going to end up failing
>	   more than 1 in 10^n.

I tend to agree with Arch Robison, though I am working on a
system with a perfect collector in it.  Here is an example of
the sort of bug that can persist in an apparently "working"
perfect collector (one that I just fixed):

  if a value is passed to a subroutine
  and if that value needs certain additional info
  and if that value originates in a volatile spill area
  and if another thread requests a garbage collection while the
      additional-info helper routine is running

  then the program will crash.

I discovered this bug in the course of working on another
bug that occurred so infrequently that I only observed it
while running a specially written test program under special
conditions that caused GC to occur as frequently as possible.
I'm not 100% sure that this bug can even occur (depends
upon quirks of register allocation), but don't know that
it cannot, either.

Critics of conservative collection seem to be ignoring the
use of blacklisting; if a bit pattern is discovered in a
conservative scan that points to a page that MIGHT be used
by the GC in the future, that page should be marked as either
unusable or only usable for pointer-free data.

All that said, we do need to be careful that we actually have
control of N.  32 bits is not enough if a program is so
obnoxious as to actually generate a large number of random
bit patterns.  Note that a good hash function will generate
random bit patterns, and that one nice trick in a hash table
is to retain the full hash value for each entry -- this allows
a very fast inequality check, and reduces the cost of table
resizing.

In the case of emacs, another concern is GC-safety of the host
compiler.  Emacs is widely ported, and some platforms (notably
the PPC) have code generation idioms that are not safe for a
conservative GC.  Some things make these problems more likely
to happen; large structures (> 32k in size) raise the risk,
as do multi-threading (but emacs is not preemptively threaded,
is it?) and garbage collection triggered within signal/interrupt
handlers (this seems unlikely, but I do not know).

Hans Boehm and I have been working on this problem on and off
for years; his most recent paper looked like it would do the
job very well, but I recall that it depended upon gcc hacks,
and that it depended upon programmers taking the time to
use particular macros for at-risk pointer operations
(conservatively, for all pointer operations).

Someone should figure out if emacs contains any of these
"risk factors" for GC-unsafety:

  large structures (>32k).
  GC within a signal or interrupt handler.
  preemptively scheduled threads.

David Chase
chase@world.std.com