NSPR is a portability layer underlying most ports of the Netscape clients and servers. It was originally written to serve as the system portability layer underlying Netscape's own ports of the Sun Java VM code, and subsequently extended to be used their other server and client applications. I've got a port of the Kaffe JVM hacked (mostly, but not entirely, by means of Kaffe's own system abstraction layer) up and limping, to the point of passing most of the regression tests.
It basically exists to provide a single, consistent API on all platforms to which Netscape wishes to port their apps for all basic system services *except* GUI user-interface widgetry (which is irrelevant for the servers, and handled by separate pieces of idiosyncratic, platform-dependant code on the clients). Services provided by NSPR implementations on various platforms include threads and thread synchronization, memory management, and I/O; there are also hooks for such things as garbage collectors.
(The fairly simple mark/sweep GC they use for their ports of the Sun JVM is included as part of the package, with a separate library, but it isn't yet documented and some of the interface to it appears not to have been completely worked out; they also say they have a fairly slick mostly-copying GC internally which has much better performance, but which they haven't packaged even that much yet --- they might be willing to put it out on mozilla.org as freeware if they knew someone was going to do something with it that would make it worth their effort. In any case, I used the Kaffe GC for my port).
The rest of this report describes the techinical approach I used for the port, its current status, and some problems encountered.
Kaffe is a clean-room reimplementation of Sun's Java VM spec,
which can run as either an interpreter (on all supported platforms),
or a JIT-style compiler (on some). It was originally written for
Posix-style systems without a great deal of concern for portability to
radically different sorts of platforms (e.g., the native Windows or
Mac APIs); ports to those, where they have been done, have generally
gone through Posix emulation libraries. Recent Kaffe releases have
tried to abstract away from direct invocation of the Posix library
calls; instead, invocations of such functions as read,
open and so forth are redirected through a table of
function pointers by means of C macros, along these lines:
#define open(A,B,C) (*Kaffe_SystemCallInterface._open)(A,B,C) #define read(A,B,C) (*Kaffe_SystemCallInterface._read)(A,B,C) #define write(A,B,C) (*Kaffe_SystemCallInterface._write)(A,B,C) #define lseek(A,B,C) (*Kaffe_SystemCallInterface._lseek)(A,B,C)
(However, as discussed below, the macrofication here is not complete; some system calls are left out --- subprocess creation, for instance, is currently a hack which, among other problems, relies on fork() and exec() calls, which generally don't exist in that form on non-Posix platforms. Also, the functions in the system call interfact table are required to implement Posix interfaces. This can be problematic on systems whose native interfaces don't correspond directly to anything in Posix; if, for instance, several system calls are required to get all the information which is returned on a Posix system by a stat() call --- most of which is generally not of interest to any particular caller).
The implementation of threads used was initially strictly internal to
Kaffe itself; it does not use Posix threads even where available. The
initial implementation did not cleanly separate the internal threads
code from the JVM implementation proper. Recent releases attempt to
abstract away the threads interface from Kaffe proper; however, as
discussed below, the specifications for those functions are still
entangled somewhat with JVM implementation details --- the interfaces,
for instance, are specified in terms of java.lang.Thread objects,
rather than void * abstracted thread and lock
structures.
I've got a port of Kaffe up and limping on NSPR --- it runs the compiler (javac), and most of the regression tests that ship with Kaffe; however, it does not pass the exec test (because NSPR does not support anything like the Posix fork() --- it can't, since some APIs have no such call), nor the GC torture test (for reasons unknown); a final annoyance is that it sometimes hangs without exiting when the primordial Java thread throws an exception, for reasons discussed below.
This discussion of the port will be divided into three parts, each corresponding to one (or two) of the tables of function pointers defining the Kaffe interface between system support and the VM proper. These are: I/O support and OS interactions, locks and threads, and memory management. (These areas do interact somewhat; in particular, the garbage collector needs to have some hooks into the memory manager, and I'll have a few things to say about that. However, most issues can be put most squarely into one category or another.
As discussed above, Kaffe's system-call interface is a table of function pointers, each of which is expected to implement some Posix-style system call (suspending the invoking thread and allowing others to proceed where it is appropriate to do so, e.g., while waiting to read data from the user's tty or a socket). Unfortunately, NSPR is not close to being a Posix clone, which leads to a number of somewhat awkward hacks in the implementation.
To begin with, NSPR I/O handles (the moral equivalent to Unix file
descriptors) are pointers, not integers. The function pointers in the
Kaffe_SystemCallInterface table, on the other hand, are
required to have Posix-like signatures --- which requires them, in
particular, to take integral file descriptors. To make matters worse,
it is not entirely whether or how the Kaffe code itself depends on the
traditional semantics of those descriptors (e.g., open(), etc., give
the lowest unused integer; 0, 1, 2 as stdin, stdout, stderr by
convention); this could cause problems if I attempted to deal with
this issue by casting NSPR's PRFileDesc *'s to integer
(even if there weren't the risk of trunctation on platforms with
64-bit pointers).
I dealt with this issue by creating a table of shadow file
descriptors, which are indices into an array of PRFileDesc
*'s; initialization code sets up the first three entries to
point to PR_STDIN, etc., on startup. This approach is
not without problems. In particular, the table itself needs to be
guarded with a mutex in order to prevent simulatneous
open's (or accept's, etc.) from grabbing the
same file descriptor. Since threads only need to grab the lock when
performing an action which could potentially create a new file
descriptor, contention for this lock isn't nearly as bad as it might
be, but it is still potentially a performance issue; what's more
significant is that the thing is just a bother.
(The code which handles exec()s in Kaffe-on-Unix now also relies
on a fixfd() function which is supposed to "NSPR-ize" a
native file descriptor obtained by the native methods of
java.lang.UNIXProcess by directly invoking the
pipe() system call; there is no documented way to do
anything like this through NSPR, and in this case, at least, I would
rather stay away from the undocumented internal black magic which can
do the job. Ironically enough, NSPR does provide a PR_Pipe() system
call; if pipe(), rather than fixfd(), were
in the Kaffe_SystemCallInterface, then the existing Kaffe
code could be easily made to work on NSPR, though it would still be
Posix-dependant).
Another problem is that work-alikes for certain Posix system calls
are not directly available from NSPR, and need to be synthesized from
what NSPR does provide. I have already mentioned the extreme cases of
fork() and exec(), the former of which is
not provided in any form by many native systems (including Win32), and
hence cannot be provided by NSPR, thus keeping Kaffe's exec()
regression test from passing.
However, there are other cases where the Posix functionality is
awkward to synthesize from what NSPR provides. Some of these have to
do with conversions between, e.g., NSPR's net address formats and the
native Posix forms which could only be avoided by having the Kaffe
code "go NSPR" and not use the Posix address formats. (Which might be
a useful idea if one wanted to use NSPR as a vehicle to port Kaffe
onto a system where the Posix in_addr formats are not
native, or not declared in header files with the usual Posix names ---
but that's another rant).
There are other cases, though, where Posix lumps together
logically separate items. An interesting case is stat(),
which lumps together queries for file-size information, file-type
information, and access status. NSPR's PR_GetFileInfo
returns file size, but it returns less information on file type than a
Posix stat(), and none on access permissions. (I could
recover some of the access information by invoking a few
PR_Access calls, but for now I'm punting).
Another bothersome case is Posix select() --- it
takes a lot of tedious code to turn this into a PR_Poll.
One last annoyance which has not yet come up, but which might in
any attempt to use my Kaffe/NSPR code as the base for a port to a
non-Posix system, is that not all of the Kaffe code has yet been
rearranged to invoke the system services it needs by indirecting
through the Kaffe_SystemCallInterface. A rather extreme
case of this caused a bug in an early version of the port --- the
fstat system call was simply omitted from the table.
(This resulted in the compiler failing when it tried to feed one of my
shadow file descriptors to the native Posix fstat).
Last I checked, problems of this sort remained elsewhere; in
particular, some of the code for handling class files still used the
native libc fopen, etc.
Kaffe has two separate function tables which contain functions which involve the closely related areas of thread operations and locks (including condition variable operations).
For the most part, what Kaffe wants maps pretty directly onto what NSPR provides, so there aren't many problems here. (Monitors and condition variables are pretty much the same everwhere --- except for Win32, where the people who designed the API thought they were smarter than Tony Hoare and Per Brinch Hansen, an opinion which is difficult to justify in terms of the results). Since things working easily and straightforwardly aren't interesting, I will instead discuss cases where Kaffe needs some functionality which NSPR does not directly provide and what I've tried to do about it.
The really nasty cases are these: making a thread exit on its own, having one thread stop another asynchronously, and obtaining stack bounds. (There are also some nasty issues involving the treatment of locks in the presence of the "spin-lock" Kaffe requires to block all threads --- however, this is primarily a feature which has to do with interactions with the GC, so I discuss it in that section). But first, a few quick words on data structures.
Both thread and lock interfaces are actually defined in terms of
Kaffe-internal structures (in the case of the thread functions,
actually handles to the relevant instances of
java.lang.Thread). NSPR, in turn, provides interfaces
which take pointers to NSPR internal functions (e.g., PRThread
*'s). Fortunately, both provide a slot in their own structure
for a void* pointer to some random glue object --- for
NSPR, I use the execution environment pointer set by the undocumented
internal PR_Set/GetExecutionEnvironment calls. I set
both of these to point to a glue structure which points to the Kaffe
thread object, the NSPR thread object, and various internal state
which is needed by a running thread. (This glue object is allocated
when the thread starts and deallocated when it stops; the pointer is
set to black-magic values for not-yet-started or dead threads; this is
how the Kaffe thread-is-alive query works).
There is one minor porting issue associated with these data
structures: in part because the thread interface is itself defined in
terms of Hjava_lang_Thread's, the implementations of the
functions have to be more tied up with the semantics of the Java
implementation itself than might be ideal. Fortunately, there isn't
too much of this; the prime example is that Kaffe, following Sun's own
JVM implementation, handles the Thread.join() method by
doing a notify() on the target Thread
object. This is something that would ideally be handled by
platform-specific code (since there is no obvious platform
dependancy), but right now, the platform-specific code for each
platform has to do the notify().
Another annoyance along these lines (perhaps more significant) is that the Kaffe code does not provide away for the platform-specific layer to to inform the platform-independant code (presumably, as part of an initialization step) of what numerical range of priorities are available; as a result, I'm forced to map the ten numerical levels demanded by Kaffe onto the four provided by NSPR, with results which might easily be an unpleasant surprise to somebody.
On to more serious porting issues, where NSPR simply does not provide some functionality which Kaffe needs. In many cases, NSPR can be defended for not allowing programmers to do things which are almost always mistakes, but which Java (and hence, perforce, Kaffe) allows; nevertheless, if we need to implement Java, it all has to be kludged somehow.
The first of these is surprisingly basic; NSPR provides no call
which causes the currently running thread to (synchronously!) exit ---
perhaps to make it harder to make a thread exit still holding some
mutex. The only documented way to make an NSPR thread exit is for its
initial function to return. Since the Kaffe thread interface does
have an exit() call, what I have it do is simply
longjmp() back into the thread startup code, which then
returns; however, there is the risk here that (depending on how this
messy thing is invoked!) there may be some NSPR-internal stack
unwinding which fails to happen because of this kludge. (I'm not
aware of any such issues, but this may simply reflect incomplete
knowledge of NSPR).
However, this kludge does not --- in fact, cannot --- work for the
primordial thread, due to the way that the
Kaffe_ThreadInterface requires it to be initialized. The
Kaffe code invokes a CreateFirstThread function which is
supposed to set up a Hjava_lang_Thread for the primordial
thread --- but that function returns, meaning that the
longjmp() trick described above can't work. So, for the
primordial thread, my thread exit function is actually a no-op --- a
truly messy non-solution. (This messiness is probably the reason why
my port sometimes hangs when the primordial thread throws an uncaught
exception).
The case discussed above is simply when a thread wants to exit on
its own. Life gets harder when one thread tries asynchronously
stopping another, e.g. by Java Thread.stop(). Note that
Thread.stop() is not supposed to immediately and
unconditionally stop the target thread; rather, it is supposed to
cause that thread to throw an exception. (In fact, there's a
documented variant form, not supported by Kaffe, which asynchronously
throws an arbitrary exception object, not necessarily the
usual ThreadDeath). So, what we need to implement this
is a way to have one thread asynchronously cause another not to
terminate immediately, but rather to run some code (in particular, the
code to throw an exception).
NSPR provides nothing like this, for two very good reasons.
First, invoking such a thing is a genuinely bad idea --- it can be
very tricky to make sure that if a thread gets asynchronously
interrupted in a critical section, it leaves whatever data structures
it was diddling in a consistent state. (I'm referring here to Java
application-level data structures, though similar considerations
obviously apply to the internal structures of the VM itself). Second,
the native threads layers on many platforms provide nothing that
immediately fills the bill. On pthreads, one could
consider trying pthread_kill, which is more or less
analogous to Unix interprocess signals; however, on Windows, the
closest thing is an extremely dangerous function which
terminates the target thread immediately and unconditionally, without
providing any hooks for running cleanup code (or, say, throwing an
exception).
The closest thing which NSPR does provide is a
PR_Interrupt function, which causes certain blocking
functions to return early with an error condition. (Though NSPR's API
here is surprisingly spare --- while a thread can clear its own
interrupted flag, there is no documented way for it to check
whether it has been interrupted or not). So, interrupting a thread
will wake it up if it is asleep, but will not force it to do anything
in particular once awake.
The best hack I've come up with to deal with this situation --- incompletely implemented in my current code --- is to set a "want-stop" flag in the "glue" structure which ties the Kaffe and NSPR thread objects together, and checking that flag wherever it is reasonable to do so. However, this approach has problems; the overhead is far from trivial (a few function calls for each check), and it doesn't even always work; the JIT-generated code for, e.g.
while (true) { int four = 2 + 2; }
probably never invokes any function which could perform one of these checks, and so a thread caught in this loop would be an uninterruptible cycle-sucker. (For a more realistic example, consider something long and compute-intensive, such as an FFT, coded carefully to avoid any storage allocation --- or coded directly as a native method which avoids any invocation of the runtime support).
It isn't really clear how this could be handled in the general case without hooks into the Kaffe JIT code generator (or interpreter, when running in that mode); with hooks, one could imagine such tricks as having a "current thread interrupted flag" checked, e.g., at the top of every basic block, or both at backward branches and method invocation. If it is possible to put this flag in a register (which would, of course, require one threads to be able to alter the saved registers of another, suspended thread --- something which may be impossible with native threads on many platforms), the overhead for such an approach can be extremely low.
(One interesting implementation of this idea is in the runtime support for Standard ML of New Jersey, an implementation of the ML functional language. It minimizes storage allocation overhead by having each basic block reserve as much free memory as it can possibly allocate --- this is finite, since a basic block has no branches by definition. The storage is taken from a region delimited by base and limit registers established by convention on each machine; so, the common-case storage allocation overhead is a register-to-register move, an addition, a compare, and a branch-not-taken (to the GC trap handler).
SML/NL sends asynchronous traps by changing the storage bounds register so that it will appear that no storage is available; the thread then quickly traps to the storage manager, which then determines that this was an asynch trap rather than a real storage overrun, and acts accordingly. The only overhead this mechanism imposes over the work already performed by storage allocation is that it requires basic blocks which allocate no storage to attempt to "allocate" 0 bytes, just for the sake of the range check; this is a compare and branch-not-taken for each such basic block in the common case).
One last bothersome aspect of the Kaffe thread interface is that a routine in the thread-system layer is required to traverse the stack from one exception frame to the next. For the most part, the details of this operation have a lot more to do with code generation than with the threads machinery per se. However, the routine is in the thread-specific code anyway because, for the JIT, it needs to determine at one specific point whether a pointer is outside the bounds of the current stack. (For the interpreter, the same check is made by simply comparing the pointer to a sentinel value; I'm not sure why the same approach wouldn't suffice for the JIT, and it would certainly make it easier to adapt Kaffe to a new threads package, but c'est la vie).
My approach to this is to put a pointer to the stack base (or actually, a pointer to an integer within the stack frame of my thread startup code) inside the thread glue structure described above, and to take the other bound for the stack to be the address of an integer within the stack frame of the function making the comparison. There are two problems with this approach. The more minor is that it can be difficult to set up the stack bounds for the primordial thread; my current approach is a pure kludge (adding 8K to an address in the stack frame of the function doing the setup). More seriously, getting a handle on the glue structure requires a couple of function calls per stack frame traversed; this can't be good for Kaffe's already somewhat pokey exception-handling overhead.
Two comments on alternative approaches: First, use of some of the NSPR GC hooks (discussed below) might allow access to NSPR's own stack bounds, but it probably wouldn't reduce the overhead, and might increase it. Second, as mentioned above, if the Kaffe code proper could arrange for the Kaffe JIT to terminate its chains of exceptions frames by a set sentinel value (the way Kaffe already does in interpretive mode), the whole messy issue would simply go away.
As discussed above, NSPR comes with a simple mark/sweep GC which is used by Netscape's own Java VM, but I'm not presently using it; I'm using the Kaffe GC instead. So, while Kaffe does have a table of function pointers which point to various GC-related functions, I have not written any new implementations of any of those functions.
(The only change I've made to Kaffe's storage management code
pe se is to change the lowest-level memory allocation
function --- pagealloc --- so that it always calls the
NSPR PR_Malloc function, rather than invoking a raw
sbrk).
However, the interactions between the garbage collector and the
thread support are tricky and potentially nasty. There are basically
two things that the Kaffe GC requires of the thread support: it must
be able to keep all mutator threads from allocating storage while it
is doing a collection, and it must be able to invoke a routine which
will cause all running threads' stacks and registers to be
conservatively marked (by calling the Kaffe GC's
markObject and walkConservative functions;
currently, there is no way for another GC to plug different
implementations into a table --- it simply must supply functions of
those names).
Fortunately, NSPR threads provide (undocumented) hooks to
accomplish both of these functions; they are declared in the header
file <private/pprthred.h>. However, in some
respects, these are not quite what Kaffe wants.
Let us begin with the requirement that the GC should be able to
stop all threads. NSPR provides hooks to accomplish this ---
specifically, the undocumented PR_SuspendAll and
PR_ResumeAll functions. However, these are not exactly
what Kaffe wants for its spinon and spinoff
functions --- in part because those functions are invoked by the Kaffe
plaftorm-independant code in places which don't have anything obvious
to do with GC.
Firstly, invocations of the NSPR functions do not nest; Kaffe
demands that they be able to nest (and, furthermore, that there be a
function --- spinoffAll --- which allows other threads to
proceed regardless of how deeply they are nested; the only invocation
of this in Kaffe is in exception handling, and it would be lovely to
remove it from there). Working around this requires the code to
maintain a count of how deeply nested the Kaffe code has gotten inside
spinoff's.
Second, the NSPR code complains bitterly if any code
attempts to locking a mutex, for arguably legitimate reasons. (If you
try to lock a mutex which some other thread holds, and all threads are
suspended, how is the lock ever going to get released so that you can
grab it? However, it may be a bit extreme to abort
unconditionally, rather than just in case the lock is
actually held by some other thread). Nevertheless, there is Kaffe
code which attempts to grab mutexes while the spinlock is
held (i.e., while code scheduling is blocked).
look here: My approach to dealing with this issue is simple, cheesy, and perhaps broken (in fact, it may be the source of the GC torture-test bugs) --- I simply turn all operations on locks (though not on condition variables) to no-ops while the spin-lock is held. This may be OK, if the code doesn't attempt to grab some lock while the spin-lock is held, and expect to keep it once the spin-lock is released. However, I haven't gone through all the GC code to verify that this is the case --- and if it isn't, then, of course, things are badly broken by my kludge.
One last note --- the Kaffe GC grabs the spin-lock (i.e., attempts
to suspend all threads) quite frequently. In particular, it grabs the
spin-lock on any memory allocation, in order to guard manipulation of
its own data structures. The assumption here appears to be that
grabbing the spin-lock is cheaper than, e.g., grabbing an ordinary
mutex. For Kaffe's original, native threads, this may well be the
case; however, it is not the case for all implementations of NSPR. In
particular, for NSPR-on-pthreads, PR_SuspendAll involves
sending a blizzard of pthread_kill signals --- this would
have extremely high overhead if several dozen threads were running,
and a couple of signals were sent to each every time any of them did a
memory allocation.
Look here: (There are also uses of the spin-lock
elsewhere --- in particular, it is used by the platform-independant
lock management code to guard its own hash table mapping Java objects
to their monitors; a simpler, platform-dependant mutex might suffice
here, and the otherwise inscrutable argument to the
spinon and spinoff functions is probably
intended to support such usage).
Fortunately, arranging to mark the stacks of running threads is
somewhat simpler, due to a better fit between Kaffe and NSPR. In
fact, NSPR provides a PR_ScanStacks function which does
pretty much what you want --- it calls another function (supplied as
an argument), giving that function pointers to the starts and ends of
regions containing potential live pointers, including running threads'
stacks, register dumps, etc.
Specifically, this cycles through all threads which have been
marked GCABLE, by means of undocumented NSPR functions;
I simply apply this tag to all threads which I create (including,
perforce, the GC thread itself and the finalizer thread).
Look here: The only potential subtlety here is that I've
taken the "don't worry, be happy" approach to verifying that the stack
bounds for the primordial thread are actually set correctly; if they
aren't, there is, once again, potential nastiness (but perhaps severe
enough that the compiler would blow up, and it doesn't).
There are a few relatively minor things that I just haven't done yet; these include implementation of runFinalizersOnExit and the set/getsockopt functions. There are no conceptual problems here; I've just wanted to attack harder problems first.
One last note: the legal status of the port is somewhat dubious, due to interference between the GPL which applies to the public Kaffe distribution, vs. the NPL which applies to NSPR; the problem is that GPLed code can only be distributed as part of a GPLed complete work, and the NPL does not allow the code it covers to be distributed in that fashion. Either Netscape or Transvirtual would have to change their license conditions to clear up this situation --- Transvirtual could do it by distributing under the LGPL or Artistic license, or perhaps by adding a codicil to the GPL which states that they consider NSPR implementations to fall under the "basic system facilities" exemption of the GPL. Netscape could clear it up only by making a GPLed distribution of at least the NSPR itself available.
(Of course, if the goal is to integrate Kaffe into the Mozilla web browser as a whole, some of the above tricks would have to be modified in order to make it legal to link Kaffe not just with NSPR, but with all of Mozilla. However, there is technical work pending here as well, or at least not yet made public; in particular, any such project would need to use the OJI stubs within Mozilla, documentation for which is not yet publically available).