This page is part of the web mail archives of SRFI 50 from before July 7th, 2015. The new archives for SRFI 50 contain all messages, not just those from before July 7th, 2015.
I remember someone (Richard K.?) remarking at the Scheme 2003 workshop
that any discussion about threading seems inevitably to turn into a
discussion about what "thread" really means, so let me show my colors
up front. When I say "thread", I'm referring to all of the following:
- The pleasant notation for some kinds of algorithms and user-visible
behavior. The Concurrent ML / eXene attitude. This view of threads
can easily be implemented entirely in the interpreter, with no
operating system support.
- An abstraction that helps programmers write code which can run in
parallel on multi-processor or hyperthreaded systems, for a
performance gain.
- The existing "thread" facilities provided by many popular operating
systems. If I want to write Scheme code which acts as a plug-in or
an extension to any existing multi-threaded application out there
(Mozilla? Apache?), I can never be a first-class citizen if my
Scheme system's "threads" are not the real thing. Sure, I could
always fake it in various ways, but in my experience it'll always
show through in some annoying way whether you're doing it Right or
not.
If I'm reading the proposal right, the interface does not support this
notion of "threads".
If doing so simply isn't interesting to the SRFI-50 authors, I can
understand that; it would be a major design change, and the best ways
I know of to address it do add some run-time overhead, and do
complicate the interface, while providing no benefit to
single-threaded programs, which I would assume are still
overwhelmingly the most common sort.
----
Assuming it is interesting:
The proposal states that "the garbage collector may run whenever an
object is allocated in the heap." In context, I think that really
means, "the garbage collector may *only* run..." In a multi-threaded
context, I think this must mean that the collector may only run when
any thread allocates an object on the heap, which isn't much of a
restriction at all; the collector can run at any time.
If that is so, then the way the proposal suggests C code should refer
to Scheme values makes it impossible for the collector to find and
relocate heap references. The C compiler may have stashed them
anywhere, in disguised forms, and it is probably unwilling to tell you
much about where they are at any given time.
The values returned by macros like SCHEME_EXTRACT_VALUE_POINTER and
EXTRACT_STRING also can't be trusted long enough to be useful.
The Java Native Interface handles this problem by essentially
forbidding C code from ever referring directly to a GC'd object.
Instead, C code may only handle "references" to GC'd objects. This
restriction is enforced by the type system. References are explicitly
freed objects, which is way people are accustomed to working in C.
And because the explicit-free model is a complete pain in the neck,
the JNI tries to ease that pain by segregating references into "local"
and "global", where "local" references are freed for you at a
convenient time.
(It doesn't work to make the scheme_value type the reference type:
references do need to be freed, somehow, whereas assignment to a
properly protected scheme_value variable is sufficient to drop the
reference to the object it used to refer to.)
At http://svn.red-bean.com/repos/minor/trunk/include/minor/minor.h,
there is a sketch of a C API interface to a Scheme system that can
support all the goals of SRFI-50 (precision; permitting copying
collectors; etc.), and also support multithreaded programs. The
comments at the top of that file explain the approach I've outlined
above in more detail. This is a work in progress; it has not
undergone any review to speak of. But I think it does address the
concerns I raised above. I've included the relevant section at bottom.
I think I have a pretty efficient implementation of this, too:
- The implementations of the functions in the interface do not need to
hold a mutex while they operate on the real Scheme values. "car"
does not require the acquisition and release of a mutex.
The only synchronization that actually takes place is between a
thread and its own signal handlers, so it can be done in C with
assignments to volatile variables --- ordinary, unsynchronized
stores that the compiler has less freedom to reorder and optimize
out.
- Local references are allocated in small constant time, and all the
local references owned by a particular call are freed en masse.
It's all untested; these are just assertions. The rest of the code is
there in that web hierarchy, if you don't mind the programmerly
equivalent of seeing me in my underwear.
The drawbacks compared to the proposed SRFI-50's approach are, as I
see it:
- SRFI-50 requires the programmer to do pretty simple annotations (the
GC_PROTECT macros), whereas the JNI approach makes the programmer
responsible for freeing references. Sure, the "local reference"
tweak handles the common cases, but you still have to think harder
to make sure you got it right.
- SRFI-50 allows code to directly manipulate references to Scheme
objects, where as the JNI requires the creation and destruction of
reference objects as well.
----
/* mn_refs: References to Minor objects. */
/* To support garbage collection, the Minor run-time needs to be able
to find all the Minor objects C code is examining at any given
time: if C code has access to an object, then the garbage collector
will make sure not to free it.
The functions in this interface never return, or accept, direct
pointers to Minor objects. Instead, we introduce one level of
indirection: they return and accept `mn_ref' objects, which refer
to Minor objects.
C code:
mn_ref *x;
+-----+
| . | the mn_ref
+--|--+ +-----+
`--------->| . |
+--|--+ ,--------------.
`-------->| minor object |
`--------------'
(The Minor objects themselves, of course, point directly to each
other; mn_refs are strictly an interface to non-GC'd languages.)
For example, the functions to construct and access pairs are
decared like this:
mn_ref *mn_cons (mn_call *c, mn_ref *car, mn_ref *cdr);
mn_ref *mn_car (mn_call *c, mn_ref *car);
mn_ref *mn_cdr (mn_call *c, mn_ref *cdr);
(Ignore the 'mn_call' arguments for the moment.) The Minor
run-time keeps a list of all the mn_refs that have been given to C
code, and protects all the objects those mn_refs refer to from
being garbage collected. We try to make mn_refs as lightweight as
possible.
C code using this interface is responsible for making sure every
mn_ref it is given gets freed. Since this can be a rather complex
task to manage, we introduce some wrinkles to make the common cases
easy. Mn_refs come in two kinds: local, and global.
- A local mn_ref is owned by a particular call of a C function by
Minor code; when that function call returns, all the local refs
it owns are automatically freed.
Specifically, when Minor calls a C function, it passes an extra
argument: a 'mn_call *' pointing to a call object created just
for that Minor->C call. The functions in this interface that
construct local references all take a 'mn_call *' as their first
argument, and return local mn_refs owned by that call (with some
exceptions, all marked as such). The call object also owns any
mn_refs the C function may have received as arguments from Minor
code. When the C function returns, all the local refs its call
object owns are automatically freed, along with the call object
itself.
This means that, in the common case of Minor calling a C function
that does some work on its arguments and then returns without
stashing any Minor objects in global variables or data
structures, the C code doesn't need to do any extra bookkeeping;
once it returns, all the mn_refs it accumulated --- all local ---
will be freed.
However, the convenience of local mn_refs comes at a price: local
mn_refs should not be stored in global variables, nor should they
be shared with other threads. To get around this problem, you
can promote a local mn_ref to a global mn_ref:
- A global mn_ref lives until you explicitly free it. Global refs
can be shared amongst other threads, and stored in global
variables. However, since global refs are never automatically
reclaimed, C code must take care of freeing them at the right
time itself; global refs are more work to manage.
Like any other kind of object shared between multiple threads,
it's up to the user of this interface to ensure that one thread
isn't using a global reference while another thread is freeing
it.
This interface provides functions to convert local mn_refs to
global mn_refs and vice versa, and a function to explicitly free
refs when necessary.
There are also some cases where C code will need to explicitly free
local mn_refs, before the call that owns them returns. For
example, if a loop traverses a list using mn_car and mn_cdr, each
element is returned as a local mn_ref. To avoid consuming storage
proportional to the length of the list for all those local mn_refs,
the loop must free them as it goes. To accomodate cases like this,
there is also a function that explicitly frees a local mn_ref.
Almost every function in this interface takes a 'mn_call *' as its
first argument; unless stated otherwise, any mn_ref values it
returns are owned by that call. When we use the call in the
obvious way, we don't bother to give it a name in the prototype,
for (a tiny bit of) legibility.
The exception is, obviously, the function that gives you your very
first call: mn_thread_first_call takes no arguments, and returns a
call object. Since calls can't be shared amongst threads, every
thread that wants to use this API must call this function. The
first time it is called, we initialize the Minor library.
Some subtleties:
- Except where we state otherwise, all the functions in this
interface promise to free any local refs they allocate before
they return (other than the local ref(s) they return). This
allows these functions to be used within long-running loops
without accumulating local refs the caller has no way to free.
- You may notice that even functions that don't need to allocate or
return local references still expect a call argument --- if
there's no need to indicate who should own any new local refs,
why does the function need to know the current call? The
collector also uses calls internally, as a cheap way to keep
track of which threads might be accessing heap objects. If
you've ever touched a heap object, you must have a call. So we
can take care of adding a thread to our list when we allocate
them their first call --- instead of having every function in
this interface check to make sure the calling thread is
registered.
- You may notice that this interface doesn't provide any functions
that change the heap object a reference refers to. This is an
important property, because it allows this interface to be
perfectly thread-safe without doing any memory or execution
synchronization while accessing references. Where the user's
code shares references between threads (global references only,
please), it's the user's responsibility to do the right sorts of
mutual exclusion to make that sharing kosher --- and that takes
care of us, as well. The users manage the same synchronization
burden they've always had; we don't add to it, in complexity or
run-time overhead.
(The functions mn_to_car and mn_to_cdr look a little like
side-effecting functions, but the specification actually says
they destroy the original reference and return you a fresh one.
And it's always up to the client code to ensure that nobody
destroys an object while someone else is using it. So the
calling thread must have the only live pointer to the
reference.) */