[EXPERIMENT] Emacs with the SpiderMonkey garbage collector

[Pip Cet]

Hello everyone,

I'm typing this in a version of Emacs that uses the SpiderMonkey
(Mozilla's JavaScript engine) garbage collector, which I've just
succeeded in starting for the first time.  It's an experiment, and I'm
perfectly happy to abandon it and leave with what I've learned; but I
think it's an interesting experiment, and it might help those actually
wanting to use a different garbage collector in the official version
of Emacs. Most of the code is available at
https://github.com/pipcet/emacs/tree/c%2B%2B (This code won't work
as-is yet, I'm afraid. I'm trying to figure out how to get the gnulib
files to build for C++. It's also missing some very recent changes.
I'm hoping to fix that soon, but if you actually want to try things,
it might be best to contact me by email. Also, if anyone could help me
find a better place to host free software, that would be very much
appreciated).

Again, this is an experiment. It's currently slow, unstable, contains
known bugs, will not work except on GNU/Linux with X (and with a
specific hacked version of the SpiderMonkey library), leaks memory,
and provides no practical advantages over official Emacs. I'm writing
this now because I'm trying to decide how much more time to spend on
it, and would appreciate comments and feedback. And, of course,
questions!

The main difference between the current mark-and-sweep garbage
collector and the SpiderMonkey garbage collector is that the latter is
a copying garbage collector and precise, meaning that objects may
change address during GC and that only typed values, not memory
locations that might or might not be, must be traced.  A minor
difference is that GC can happen at any time the code is in the
JavaScript API, meaning that we can no longer get away with stretches
of code that "never GC".

I was hoping to find some bugs in official Emacs during this process,
but have been mostly[1] unsuccessful--I have found bugs, but only ones
introduced by my previous changes.

Let me describe in detail some of the changes I made and how I made them:

1. Make Emacs compile with CC="g++" CFLAGS="-fpermissive"

This was harder than it sounds. In fact, I ended up writing a simple
parser for "Emacs C", the unpreprocessed source code as it appears in
the repository, and performing the necessary replacements
automatically.  As a side effect, declarations of the form

    int x, y;

are rewritten to

    int x; int y;

2. Replace Lisp_Object in the source code

My plan was to use JS::Value objects instead of Lisp_Object.

In order to properly use SpiderMonkey, stack objects must be rooted:
I've decided to use separate types for (a) stack values and values in
structs that live on the stack (b) values on the heap (c) values on
structs that live on the heap (d) return values (e) function
arguments. (In order, ELisp_Value, ELisp_Heap_Value,
ELisp_Struct_Value, ELisp_Return_Value, ELisp_Handle).  While
Lisp_Object values need to be protected, pointers to Lisp_Object need
not, so there is a simple ELisp_Pointer type (which is currently
bloated because it determines at run time whether it's pointing to an
ELisp_Value or an ELisp_Struct_Value), as well as vector (resizeable
arrays) and array (fixed size) types.

Luckily, I was able to modify the C-to-C++ conversion script to
determine automatically which of the replacement types to use for most
of the ~10k instances of "Lisp_Object" in the Emacs source code. In
fact, I decided to keep this approach, modifying the C source code as
little as necessary, then turning each .c or .h file in the src
directory into a C++ .c.cc or .h.hh file, then (ideally) not modifying
the resulting C++ files.  It's currently not quite clean that way.

3. Replace lisp.h

The replacement, jslisp.h.hh, defines ELisp_Value etc. to be C++ types
based on SpiderMonkey's JS::Value, which can be a non-NaN double, or
an NaN-boxed object pointer, 32-bit integer[2], undefined, null, or a
JavaScript symbol or string.  I'm only using doubles, integers, and
JavaScript objects. (So strings and symbols are JavaScript objects,
including Qnil). Each object points (using the JS_GetPrivate pointer)
to an unmovable structure in memory, which in turn contains a copy of
the JavaScript value that represents it. This combines the
disadvantages of a moving and a non-moving garbage collector, but it
was good enough for this experiment.

ELisp_Value, for example, is a rooted type which has a non-trivial
constructor which registers the JS::Value it contains in a "root list"
and a destructor that removes it. In ordinary code, you can otherwise
use it much like a Lisp_Object.

Apart from beginning with a JavaScript value, the actual
constant-address structures are mostly unchanged (I moved some
Lisp_Object struct members that previously weren't GC'd (because they
didn't need to be) to the pseudovector Lisp-Object area so I could
trace them).

4. Replace alloc.c

Most of alloc.c is married to the current garbage collector and needed
to be replaced or simplified, in order to leave memory management to
SpiderMonkey.

Instead, a new file, js.c.cc, contains the new rooting/tracing code:
it registers a hook with SpiderMonkey's garbage collector which
traces, directly or indirectly, all Emacs data except for stack
values, which are traced by SpiderMonkey.

5. Stack unwinding

Emacs uses setjmp()/longjmp(). While I think this code can be
converted to use C++ exceptions instead, I decided it would be easier
to make stack unwinding work with SpiderMonkey. The problem is
destructors of intervening stack frames are not called when unwinding
the stack, so we must find and destroy objects in unwind_to_catch.
This turns out to be easily possible, though we violate the
SpiderMonkey API by accessing fields in a private structure: we save a
stack pointer in the struct handler structure, then compare it to the
current stack pointer upon entering unwind_to_catch.  We then walk the
root lists to find all rooted objects that live in the intervening
stack region and destroy them (and do the same for auto-rooted
vectors, which work the same way but use slightly different code).

6. Calling convention

The usual SpiderMonkey calling convention is that functions do not
return GC types; their arguments are "handles", essentially read-only
pointers to JS::Values.  I decided to return JS::Value objects
directly (except for being wrapped in another class), which opens up
 a race condition:  If f1 and f2 are functions returning
ELisp_Return_Type values, it's illegal to call another function g as
g(f1(...), f2(...)).  f1's return value will not be traced if f2
triggers a GC, so if it is moved there will be a segfault (or worse).
It should be possible to further extend my C-to-C++ script to deal
with this by automatically assigning ELisp_Value temporaries in this
situation. I also decided to pass function arguments as JS::Value
objects, rooting them in the callee instead. Both of these decisions
are open to revision.

7. Misc

Some unions were turned into structs in order to ease tracing them.
Some structs had to be duplicated into a stack and a heap version.
Many previously-unrooted (again, because they didn't need to be)
objects were staticpro'd or added directly to the tracing code.
ELisp_Pointer, a data type representing a pointer to a JS::Value, was
modified to require explicitly-named methods rather than operator
overloading to catch bugs. This introduced new bugs. Finally, after
much debugging, Emacs showed me a usable frame.

8. What now?

While I don't think it's right to have SpiderMonkey-specific code in
Emacs, we don't need to: there's pretty much an automatic API between
Emacs and its garbage collector that's good enough for SpiderMonkey,
but can be trivially implemented by the existing mark-and-sweep
garbage collector. I'd like to make that work, by making as little
code as possible depend on the innards of ELisp_Value etc.

I do not advocate switching to this garbage collection mechanism in
the official Emacs, converting the official Emacs to C++, or renaming
all Lisp_Objects in the official Emacs. I do advocate making the
official Emacs compile with G++ with the -fpermissive option, to help
further experiments. I also think that if there are other ways to make
it easier in the future to switch to a more complicated garbage
collector, we should investigate them, but I need to think about this
more.

The C-to-C++ converter seems potentially useful for other projects (my
initial approach was to try coccinelle, but I never got that to work
right), and should be extended to provide temporary variables
automatically, at which point we can change the calling convention
back to one that uses handles for read-only arguments.

Using JSObject structures for everything is wasteful, particularly in
the case of cons cells, which should require only 16 bytes each. I
think it should be possible to modify SpiderMonkey to assign a unique
tag to cons cells, allowing us to get them down to 24 bytes (car, cdr,
and a hash value (we can no longer use the address because that might
change).

I'd like to get away from the dual
constant-address-structure/pointer-only-JSObject approach. We could
use JSObjects to store rarely-needed properties as JavaScript
properties, and store only commonly-used data in the private
structure. In some cases, we can forego a private structure entirely
(cons cells).

9. Unimplemented

This list is incomplete:
 - non-X environments
 - non-GNU/Linux environments
 - weak hash tables
 - finalizers
 - finalizing markers
 - threads (it's unclear to me whether this is possible)
 - modules
 - images and sounds
 - debugging/backtraces
 - dumping (I'm currently using CANNOT_DUMP=yes. Is that supposed to
work? Because it doesn't without a few changes to the initial Lisp
files.) (Again, I'm not sure this will ever work).
 - reduce warnings (-fpermissive produces copious warnings, most of
which are valid and need to be fixed in the code. Right now, I'm
ignoring them as long as the result works.)
 - remove -fpermissive
 - signal handlers need to be protected specially

In the C-to-C++ converter:
 - operator precedence
 - global (not per-chunk) data, such as function prototypes
 - performance

[1] - there's one place that uses "false" for "NULL", and garbage
collection of markers is O(n^2) in the number of markers per buffer,
which means it tends to dominate GCs in some scenarios (including my
typical usage).  Both are trivial to fix.
[2] - JavaScript doesn't distinguish integers from floating-point
numbers, but SpiderMonkey does. This is relevant because Emacs
sometimes uses a floating-point argument to mean something different
from the equivalent integer argument.

Sorry this got quite long! Any comments, private or public, would be
appreciated.