> From: Jim Blandy <xxxxxx@redhat.com>
> I'm sorry. I shouldn't be trying to write so late at night.
Your fresh explanation is much clearer to me. Here's what seems to
be wrong with it :-)
> In code using this SRFI's interface, there are two classes of Scheme
> values:
> [1.] Values that reside in GCPRO'd variables.
> [2.] Values that reside anywhere else: in other variables,
> compiler-generated temporaries, and so on.
Just as an aside, there's a third class (not directly related to this
sub-thread but worth keeping in mind when thinking about the draft.
Your second class could be more precisely stated:
[2.] Values implied by the execution of FFI-using code and which
may reside in a location other than a GCPRO'd varriable such
as in registers, compiler-generated temporaries, and so on.
and the third is:
[3.] Values which reside in Scheme locations not directly accessible
to FFI-using code such as the CAR and CDR of a pair or the
elements of a vector.
The gist of my "Pika from first principles" argument is that we can
eliminate [2.] entirely, and subsume [1.] into [3.] -- leaving just
one type of Scheme value which is completely and abstractly under the
control of the Scheme implementation.
> Values in the first class the GC can update when it relocates objects;
> those in the second class it cannot, because it can't find them.
> Values in the second class are unavoidable if you're actually
> operating on the values, since you can't control the code the compiler
> generates.
> By using the 'begin / end' pair of functions, you'd promise the
> SRFI-50 implementation that, outside such pairs, no values of the
> second class exist, and it is free to collect at any time. When any
> thread is within such a pair, there exist object references the
> collector can't find or update, so collection has to wait until the
> thread reaches a "may gc" function.
> Is that better? Or worse? :)
It's a clearer explanation. I'm not sure how useful it is to solve
the problem. Consider for example that, applying the rule as you've
stated it, all calls to any function that accepts or returns a Scheme
value must be made from within a gc-excluding begin/end pair.
A return statement in a scheme-value-returning function must rely on
the caller of that function to be within a begin/end pair.
Absent an extension to the idea, effectively all FFI-using code will
be executed within one big critical section -- GC could never take
place while any FFI-using function is executing.
I said earlier that I didn't see how what you were proposing could be
the same as what kelsey was talking about because it didn't explain
the "re-" in "exit and re-enter critical sections" that he spoke of.
Perhaps what he meant wasn't a need for begin/end pairs -- but instead
two pairs of entry points:
SCHEME_ENTER_CRITICAL_SECTION
SCHEME_LEAVE_CRITICAL_SECTION
SCHEME_ENTER_UNCRITICAL_SECTION
SCHEME_LEAVE_UNCRITICAL_SECTION
with rules like:
~ within a single thread, critical sections may not be dynamically
nested directly within other critical sections. i.e., this is
illegal:
SCHEME_ENTER_CRITICAL_SECTION;
SCHEME_ENTER_CRITICAL_SECTION; /* illegal */
SCHEME_LEAVE_CRITICAL_SECTION;
SCHEME_LEAVE_CRITICAL_SECTION;
~ within a single threaded system, uncritical sections may be directly
nested within critical sections and vice versa. So this is legal:
SCHEME_ENTER_CRITICAL_SECTION;
SCHEME_ENTER_UNCRITICAL_SECTION;
SCHEME_ENTER_CRITICAL_SECTION;
SCHEME_LEAVE_CRITICAL_SECTION;
SCHEME_LEAVE_UNCRITICAL_SECTION;
SCHEME_LEAVE_CRITICAL_SECTION;
~ entry to C from Scheme is implicitly within a critical section
~ outside of any Scheme dynamic scope (in a thread), code is
implicitly within an uncritical section
So now I can write something like:
scheme_value
foo (....scheme_value parameters ...)
{
GCPROTECT my parameters;
do scheme stuff;
SCHEME_ENTER_UNCRITICAL_SECTION;
do anything but scheme stuff here;
SCHEME_LEAVE_UNCRITICAL_SECTION;
do more scheme stuff;
return some value;
}
Of course, the "(may GC)" functions are then those that may themselves
create an uncritical section.
That has a minor drawback. To write good code using it, it would be a
mistake to write something like:
while ( .... possibly very long loop ...)
{
do scheme stuff;
}
or anything similar. I would have to remember to write:
while ( .... possibly very long loop ...)
{
do scheme stuff;
SCHEME_ENTER_UNCRITICAL_SECTION;
SCHEME_LEAVE_UNCRITICAL_SECTION;
}
or else prove that "do scheme stuff" involves a call to a "(may GC)"
entry point.
Of course -- I personally like the idea of interrupt polling and this
is nearly the same thing -- so I won't complain too loudly about that.
However, while this idea does make progress on the problem of
scheduling some kinds of GC implementation in multi-threaded systems,
it still doesn't change the fact that the draft FFI fails on first
principles. Recall that it fails in these three ways:
1) requires that Scheme values be representable as C rvalues
2) requires that the contents of some Scheme locations be
referencable as the value of a C lvalue expression
3) requires that the contents of some Scheme locations be mutable
using the C assignment operator -- that the location be
repersentable as an lvalue, that the value to be stored be
representable as an rvalue, and that the compiler is free to
implement the mutation in the manner of a C assignment operation.
Let us turn our attention to the possibility of an incremental copying
collector in a single-threaded system and see what happens wrt. to
(3) in particular.
The draft FFI proposes to allow an unbounded number of lvalues to be
registered as GC roots. We've established in earlier conversation
that it is reasonable to expect those locations to be incrementally
traced. Even with the ENTER/LEAVE macros added, the draft will still
permit (within a critical section):
x = y;
and if `x' has already been traced, but `y' not, then `x' will be
given a stale value -- it will violate the tri-color invariant.
The only workaround the draft permits is to trace _all_ GCPROTected
lvalues within a single uncritical section. In other words, it
requires a trace-step of unbounded duration.
Similar problems arise with, for example, parameter passing and
return values.
And although these problems are easilly illustrated with incremental
collectors -- they aren't unique to them. Any collection technique
using read and write barriers faces an analogous problem: that since
the draft permits barrierless reads and writes of an unbounded number
of locations between GC points, GC is forced to examine an unbounded
number of locations to see where untrapped values may have been
written between GC points.
The spirit of the ENTER/LEAVE macros, and indeed the "(may GC)"
declarations in the draft, is to guarantee the existence of "GC
points" when GC may take place, guaranteeing that there are no "type
[2.] values" at those points:
[2.] Values implied by the execution of FFI-using code and which
may reside in a location other than a GCPRO'd varriable such
as in registers, compiler-generated temporaries, and so on.
We can understand the most fatal flaws with that goal by observing
that:
a) Barrier techniques, whether in the GC or elsewhere, have
a stronger requirement than the non-existence of type [2.]
values: they additionally require that the Scheme implementation
control reading or writing of Scheme-value-holding locations.
b) Even if we agree to blow-off barrier techniques in SRFI-50,
still, achieving the goal of the ENTER/LEAVE macros creates
a new problem: that of ensuring that GC-points occur frequently
enough.
If, instead, we fully abstract over scheme values, scheme locations,
and primitive operations on these things -- then both flaws are
eliminated.
-t
