Re: 'conservative' GC == 'risky' GC

chase@Think.COM (David Chase) writes:
>2. TMB's comment could be very wrong, depending upon how sure you want to
>be of your conservative GC. It's one thing to observe that a compiler
>rarely, if ever, thwarts your conservative GC. It's an extraordinarily
>much harder thing for a compiler writer to verify, after the fact, that
>the compiler will never, ever, hide a pointer from the conservative
>garbage collector (and yes, I actually considered doing this while working
>on an optimizer at Sun. The result of this informal spare-time study was
>to try instead the approach described in the paper that Hans Boehm and I
>wrote). This job is made especially hard because (as Chris Aoki observed)
>"how are you going to test the damn thing?" Simply running your tests
>isn't going to do much at all, because garbage collections are relatively
>rare, even in a generational system. Furthermore, failures (especially in
>a multithreaded environment) may be horribly non-repeatable. I'd like to
>think that I'm good enough and careful enough a programmer to get it right
>from first principles if I started writing a compiler from scratch (as if
>someone would pay me to do this), but we tested plenty much back at Sun,
>and damned if the tests didn't show me where I'd screwed up from time to
>time (in one case, the bug lay hidden for 18 months).


While I certainly agree with all of the above, it seems to me we're already
there. Multiple threads invariably introduce the possibility of unrepeatable
bugs. Nonconservative garbage collectors are probably even more prone
to bugs that arise form violation of the compiler/collector interface.
Even traditional malloc implementations suffer from this problem. How
do you tell that your malloc implementation is thread safe? (Just wrapping
locks around malloc and free is pretty safe, but might not perform well
in some environments. And I know of one or two buggy lock implementations
that weren't uncovered for a while.)


Even if you forget about threads, you have the same problem with signal-
safety on many systems. How many programs can you find that call printf
in response to receiving an asynchronous signal (e.g. SIGQUIT)? This is
not legal, and is often unsafe. (The program may have been in the middle
of a malloc or free call, with the malloc data structures in an inconsistent
state. Printf may allocate. I think most implementations do under some
circumstances.) I claim the probability that such a bug would be uncovered by
most testing schemes is negligible.


As another example, several RISC architectures (e.g. SPARC and MIPS, I
think) do not completely hide hardware interrupts (e.g. process
preemptions, translation faults) from user level processes. Conventions
dictate that user level code should not look at certain registers that may
be affected. User code may also have to guarantee stack pointer validity
after every instruction. How do you test conformance of your compiler and
run-time system? (It's easy to build a longjump implementation that
has an invalid sp during a one instruction window. What's the probability
of getting preempted at that point?).


It seems to me the real problem is asynchrony, which is hard to avoid.
Better testing tools would help, but this is a hard problem with or
without conservative garbage collection.


Hans-J. Boehm
(boehm@parc.xerox.com)
--

Return to the comp.compilers page.
Search the comp.compilers archives again.