Chawan's (old) new GC

In version 0.5.0, Chawan's browser engine uses a new memory management strategy based on wiring QuickJS's garbage collector into Nim's ARC memory manager. Seeing that the result is a considerable improvement over 0.4.4, I've decided to ~~brag~~ write an informative post about it.

Problem statement

Why does Chawan have to care about the GC at all? At first glance it would seem that by using a language with a built-in GC (Nim), its runtime would solve memory management for us automatically. However, things get a bit more complicated when JavaScript enters the picture.

To run JS code, Chawan uses QuickJS, which, as usual with JS engines, has its own built-in GC. The question therefore is how to get two separate runtimes (Nim & QJS) to agree on what objects can be freed and what cannot.

Before going anywhere further, let me introduce a motivating example. A large part of the browser's memory allocation comes from the DOM, so Node is as good as it gets[1]:

type Node = ref object of EventTarget
  parentNode: Node
  firstChild: Node
  previousSibling: Node
  nextSibling: Node

Two things to notice:

Node itself is cyclic. In particular, a Node points to its parent Node, while the parent Node indirectly holds its children (firstChild -> nextSibling -> ...). The reason this matters is that both Nim and QuickJS use reference counting, but plain reference counting cannot clean up cycles, so they both have their own cycle collector as well.
The list of JS properties is nowhere to be found.

The what? But indeed, DOM objects (as any other JS-exposed object) are capable of holding arbitrary properties:

document.getElementById('x').veryImportantProperty = 'hello world';
console.log(document.getElementById('x').veryImportantProperty);
/* -> hello world */

The way this works (in all browsers to my knowledge) is that on the first access from JS, the native Node object is linked to a newly allocated wrapper JS object, and vice versa. So we get a graph like:

One box titled "Node", includes the members parentNode,
firstChild, previousSibling, nextSibling, and finally, the pointer "wrapper"
pointing to the second box. The second box, titled "JSObject", includes
the members "shape", the pointer "opaque" pointing back to the "Node" box,
and the pointer "props" which points to a third box including the property
"veryImportantProperty".

With this we arrive at the main source of our predicament, which is that this graph is also cyclic. A Node object must look up its existing JSObject wrapper on each JS access (say, from getElementById), but the JSObject must also hold a reference to the original Node so that it can access properties such as parentNode etc.

The good news is that this is easy to achieve with the tools we have at our disposal. On the Nim side, we might define a native JSRootObj type with a member pointing to the JS wrapper object, and subclass every JS-exposed object from that. And on the QuickJS side, the JS_SetOpaque API allows attaching an arbitrary pointer to the JSObject.

The bad news is that the above sketch leaks. Although both Nim and QuickJS have cycle collectors, the two know nothing of each other, so the moment JS code accesses any DOM node, that creates a cycle that persists until the user closes the page. This is not acceptable with RAM prices these days, so some solution is necessary.

Object resurrection

Here's what Chawan 0.4.4 did. First off, on the Nim side it used refc, which is deferred refcounting (local variables skip refcounts; the stack is scanned periodically) plus mark & sweep for cycle collection. As noted above, refc is entirely separate from the QuickJS GC, so the two had to be sync'ed somehow.

Upon the first JS access, 0.4.4 assigned the wrapper object a strong reference of the Nim object (say, Node), while the Nim object only held a weak reference to the JS wrapper object. In fact, this "reference" was simply a hash table entry storing the wrapper's pointer, keyed on the Nim object's pointer.

The problem with this approach is that by itself, it cannot handle the above example:

document.getElementById('x').veryImportantProperty = 'hello world';
/* x's wrapper is no longer referenced; QuickJS deallocates it ASAP,
   together with veryImportantProperty. */
console.log(document.getElementById('x').veryImportantProperty);
/* -> undefined */

In other words, holding a reference to either side must keep the other side alive as well; using a weak reference breaks this assumption.

To solve this, I patched QJS to support object resurrection. Whenever the reference count of a wrapper JSObject reached zero, it would call a can_destroy hook, which did the following[2]:

Increase the JSObject wrapper's reference by one.
Decrease the Nim object's (e.g., Node) reference by one. In case the Nim object only had one reference, this would invoke the Nim object's finalizer, which would decrease the JS object's reference again.
Now, the JSObject either has zero or one reference. If it has one, pretend that nothing happened; the object is resurrected. If it has zero, the Nim object has also been finalized, so both are cleaned up.

This worked well enough, but the problem of cross-GC cycles remained:

const element = document.createElement('div');
element.myProperty1 = element.classList;
element.classList.myProperty2 = element;

classList must hold a native reference to element so that methods such as toggle can manipulate the element's class attribute. But element must also hold a native reference to classList, because it is denoted as SameObject in WebIDL, meaning the same Element must always return the same classList object.

Also, the JS wrapper objects refer to each other through myProperty1 and myProperty2:

Four cycles to be seen: between the the two JSObject
wrappers through myProperty1 and myProperty2, between the element and the
class list, between the element & its JSObject wrapper, and between the
classList & its wrapper.

Needless to say this cannot be collected with a cycle collector on just one side. So the approach I took was to extend the QJS cycle collector to Nim, where it would call can_destroy for every wrapper object in the "scan" phase. This appeared to work fine, until I realized it doesn't, because, to quote the commit message of an unfinished fix (confused rambling ahead, feel free to skip):

When one member in a JS cycle is resurrected, the QJS GC would never perform resurrection on the other member, because it has a strong reference from Nim. This has to be solved by temporarily decrementing the Nim strong ref, and incrementing it again after GC.

But even then we still have a problem: when attempting to resurrect a GC'ed object, it has the chance of running the finalizer. So you have to restore refs of members to GC in advance.

waaaaaaaaaaaait a second, doesn't this mean that we can already run the finalizer at the wrong time... I mean say you run finalizer for X first, and then try to resurrect Y. X succeeds, but Y fails, so Y restores its members. But by then, X has already finalized, so if Y has to restore a member, then... ugh.

On the other hand I don't understand why this can even happen, like if X is to be finalized then surely it also held references. I guess the problem is that normally you'd assume all those references are dead, but we change the equation by running a finalizer for Y. So basically we should be fine by

restore non-hook references

finalize

decref non-hook references for finalized objs?

Evidently, the problem was becoming too complex to keep inside my head.

Now, I still think I could have made this work with time. Who knows, maybe there is even a way to make it fast! Yet, in Sir Tony Hoare's famous words, the result would have been a system not obviously without deficiencies, but rather one so complicated that there are no obvious deficiencies. Certainly not something to run untrusted JavaScript code on.

So I decided to cut losses and switch to a different strategy I had already been considering[3].

One ref_count to rule them all

When you think about it, most of our problems arise from having a separate reference count for native objects and their JS wrappers. An easy way around this is to always allocate the JS wrapper object, then store Node as a pointer in the QuickJS "opaque" field and leave refcounting to QJS.

This doesn't sound too bad, until you realize it means you can no longer directly store references:

# Type safety, where are you?
type Node = ptr object of EventTarget
  parentNode: JSValue
  firstChild: JSValue
  previousSibling: JSValue
  nextSibling: JSValue

Well, that, and the fact that a JSObject is huge. Just the struct itself is 72 bytes, and this doesn't even include the properties or malloc header. Chawan is commonly used on memory-constrained devices and with JS disabled, so this is not an expense I would have been comfortable with taking.

But it's not entirely the wrong direction, either. It just needs some adjustments.

First, for type safety, we switch to the ARC Nim runtime, which exposes lifetime hooks that allow customizing the memory management lifecycle of arbitrary objects:

type
  JSRootObj {.inheritable.} = object
    wrapper: JSValue

  JSRef[T: JSRootObj] = distinct ptr T

# there are a couple more, but these are the most interesting ones
proc `=destroy`[T](r: var JSRef[T]) =
  JS_FreeValueRT(globalRuntime, (ptr T)(r).wrapper)

proc `=copy`[T](a: var JSRef[T]; b: JSRef[T]) =
  if a != b:
    `=destroy`(a)
    JS_DupValueRT(globalRuntime, (ptr T)(b).wrapper)
    (ptr T)(a) = (ptr T)(b)

Yet, we still rely on the wrapper object for participating in the QuickJS GC, which we've already established is unacceptable. So here comes the trick: we turn the Nim object into a QuickJS GC object.

In QJS this is easy: just extend JSGCObjectTypeEnum with a new JS_GC_OBJ_TYPE_FOREIGN entry, handle it in the GC's switch statements, and we're done. The header itself looks like:

typedef struct JSForeignObject {
    JSGCObjectHeader header; /* needed by GC */
    JSGCObjectHeader *target;
    uint32_t class_id; /* for RTTI */
    int free_mark; /* for handling cycles */
    uint8_t data[]; /* user data */
} JSForeignObject;

Pay special attention to target, which is a pointer to either the wrapper JSObject (another GC object type) or the JSForeignObject itself. Besides not having to put this in JSRootObj, this has the important purpose of unifying the two reference counts.

First, after allocating a JSForeignObject (say, Node), we set target to the object's header itself. Our refcounting procedures follow this indirection, so until the wrapper object is allocated, we adjust the ref_count field of our own header.

Things change when JS accesses Node for the first time. As before, we allocate a wrapper JSObject, but then:

Transfer the reference count accumulated by the JSForeignObject to the wrapper JSObject.
Set the target field to the JSObject.

Now the two objects are married together until the wrapper JSObject either loses all reference counts, or gets cleaned up by the cycle collector. At that point we use the QuickJS finalizer feature to clean up the attached JSForeignObject too[4].

Similarly, we trace objects using the gc_mark QuickJS hook. Here Nim's macro system comes in handy, so that we don't have to write a procedure marking all fields for each and every object, but rather get it generated automatically in most cases[5].

With the C API in place, let's take a look at the Nim side. The previously introduced JSRef is adjusted to accept any object (that will be allocated inside the data field), like this:

type
  JSRef*[T] = distinct ptr T

proc destroyAux(p: ptr pointer) {.exportc: "cha_jsDestroyImpl".} =
  if p[] != nil:
    JS_FreeForeignObject(globalRuntime, p[])

proc dupAux(p: pointer): pointer {.exportc: "cha_jsDup".} =
  if p == nil:
    return nil
  return JS_DupForeignObject(globalRuntime, p)

proc copyAux(dest: ptr pointer; r: pointer) {.exportc: "cha_jsCopyImpl".} =
  if dest[] != r:
    destroyAux(dest)
    dest[] = dupAux(r)

proc sinkAux(dest: ptr pointer; r: pointer) {.exportc: "cha_jsSinkImpl".} =
  destroyAux(dest)
  dest[] = r

proc `=destroy`[T](r: var JSRef[T]) {.
  importc: "cha_jsDestroy", header: "quickjs-aux.h".}

proc `=copy`[T](dest: var JSRef[T]; r: JSRef[T]) {.
  importc: "cha_jsCopy", header: "quickjs-aux.h".}

proc `=dup`[T](r: JSRef[T]): JSRef[T] {.
  importc: "cha_jsDup", header: "quickjs-aux.h".}

proc `=sink`[T](dest: var JSRef[T]; r: JSRef[T]) {.
  importc: "cha_jsSink", header: "quickjs-aux.h".}

proc jsNew0(p: ptr pointer; class: JSClassID; size: csize_t) =
  p[] = 

template jsNew*[T](x: T): JSRef[T] =
  var r: JSRef[T]
  cast[ptr pointer](addr r)[] = JS_NewForeignObject(globalRuntime,
    getClassID(T), csize_t(sizeof(T)))
  if r != nil:
    var y = x
    copyMem(cast[ptr T](r), addr y, sizeof(T))
    {.cast(raises: []).}:
      wasMoved(y)
  r

=destroy decreases reference count of r. =copy unrefs dest (the lvalue) and sets it to an incref'd r. =sink is documented to be an optimization but in practice you have to provide it for distinct ptr; effectively it corresponds to dest = move(r) where dest already holds another value. Finally, =dup is an optimization of =copy that doesn't have to destroy the lvalue.

The exportc/importc pragmas are a type erasure hack to speed up compilation. This way, Nim won't generate hundreds of separate refcounting functions with lengthy identifiers, it just calls cha_jsDestroy etc.[6]

Objects are instantiated using a jsNew template. I've stripped some comments for brevity, but in short it just allocates a new JSForeignObject and fills it with a stack-allocated object. For construction this means instead of the old Node() we use jsNew NodeObj() which is similarly convenient. (Actually, coming from Java, I even like it more...)

Of course, the ref construct (which produces a Nim-managed reference) must be replaced for this to work. Node for example now looks like:

type
  Node = JSRef[NodeObj]

  NodeObj = object of EventTargetObj
    parentNode: Node
    firstChild: Node
    previousSibling: Node
    nextSibling: Node

A bit uglier, but I can live with it.

There are two problems left. First, you cannot access members of a distinct ptr, so we need some kind of automatic dereference. Nim happens to support this with the experimental dotOperators feature - despite being experimental, I found the switch works perfectly for my purposes.

Second, the upcasts. For the regular ref type, Nim will helpfully & transparently upcast your pointers, so that, for example, you can call getAttribute (which takes Element) on an HTMLElement. Regrettably, this is not the case for distinct ptr, and worse, all my attempts to do it automatically failed. (converter was my best bet, and it sort of works, but it slows down both the compiler and the program to a crawl.)

So we need explicit conversion (say, Element(element)), but this is error-prone; it looks the same as a downcast, except the compiler now lacks RTTI to inject checks for these, meaning the same syntax may be used for a trivially correct operation and one that could invoke UB. In the end, I settled on the following pattern:

template asElement*[T: ElementObj](x: JSRef[T]): Element =
  Element(x)

which statically checks if the upcast is valid. This still left me with manually inserting over 700 upcasts, which as you may imagine I wasn't happy about, but in absence of a better solution I decided to live with it.

Benchmarking

Obvious question: is it any faster? My go to benchmark for deciding this is the HTML standard[7], which is such an enormous document that rendering it is a real challenge even for mainstream browsers. Reading such lengthy documentation is also a typical use case for Chawan. So without further ado, let's measure:

$ git checkout 98afdf051621f125421528ca82adaf609096f55a && make -j
$ ./cha .test/h.html >/dev/null # warm up the caches
$ time ./cha .test/h.html >/dev/null

real    0m3.672s <-- this is the relevant number
user    0m0.428s
sys     0m0.041s
$ git checkout 2c580e09f3079edc0ffe5765c8ec553e862e9704 && make -j
$ ./cha .test/h.html >/dev/null
$ time ./cha .test/h.html >/dev/null

real    0m2.934s <-- and then this one
user    0m0.236s
sys     0m0.032s

Not bad, considering this doesn't even use JS much (where you'd expect the most wins from removing the Nim -> JS wrapper side table). Unfortunately, a peek at top reveals memory usage is up at 438M from 359M in 0.4.4, so let's fix that...

Reducing memory usage

Taking another look at the JSForeignObject struct above, we can see the following:

class_id and free_mark take up 4 bytes each, but class_id only really needs 2 bytes (it's already limited to uint16 in other places), and free_mark is just one bit. We can fill the rest with arbitrary data.
JSGCObjectHeader is a doubly-linked list which becomes completely unused the moment we attach a wrapper JS object. (Remember, after that point, the JSForeignObject no longer participates in the GC, but delegates all its refcounts to the JSObject.)

We can exploit this as follows:

typedef struct JSForeignObject {
    JSGCObjectHeader header;
    uint16_t class_id;
    uint16_t free_mark;
    uint32_t magic; /* user magic data */
    uint8_t data[];
} JSForeignObject;

static inline JSGCObjectHeader *js_foreign_opaque(JSForeignObject *obj)
{
    if (obj->header.link.prev)
        return &obj->header;
    return (JSGCObjectHeader *)obj->header.link.next;
}

If we have no wrapper, then both prev and next must be non-null[8]. And if we do, we just set prev to NULL, and then store the wrapper in next. The branch might make things a bit slower, but it's not something I was able to measure on my (admittedly limited) benchmarks.

As for the magic field, we need it as padding for 8-byte alignment of user data, but that doesn't mean we can't use it for other purposes. I ended up stuffing the element index in there (used for :nth-child in CSS) and some identification data for JS accessors such as classList.

After this change, we are looking at 318M for the HTML standard, a 41M reduction over refc. In comparison, Firefox ESR reports 756M and Chromium 658M, so I think we're doing fine.

(Apples to oranges of course; being a TUI browser, Chawan need not bother things such as font rasterization. For a similarly unfair comparison, Lynx accomplishes this feat in 41M - with the caveat that Lynx has no DOM at all.)

Memory- and type-safe JSValue

Besides performance, switching to ARC has also allowed for a few other improvements.

As already mentioned, QuickJS uses a reference-counted JSValue, a tagged union of primitive values/objects for which you'd normally have to adjust the refcounts manually. This quickly becomes a huge spaghetti of free's, especially in a language without goto:

proc blah(ctx: JSContext): JSValue =
  let val = JS_GetSomeObjectSomehow(ctx)
  if JS_IsException(val):
    return JS_EXCEPTION
  let atom = JS_NewAtom(ctx, "someFunction")
  if atom == JS_ATOM_NULL:
    JS_FreeValue(ctx, val)
    return JS_EXCEPTION
  let res = JS_Invoke(ctx, val, atom, nil, 0)
  if JS_IsException(res):
    JS_FreeValue(ctx, val)
    JS_FreeAtom(ctx, atom)
    return JS_EXCEPTION
  # ...
  JS_FreeValue(ctx, val)
  JS_FreeValue(ctx, res)
  JS_FreeAtom(ctx, atom)
  return JS_UNDEFINED

Luckily, with ARC it is possible to add deterministic destructors for JSValues, meaning the compiler will inject all the free's for us. Add in some syntactic sugar for ? to return JS_EXCEPTION if the value itself is an exception, and we get:

proc foo(ctx: JSContext: this: SomeObject; fun: JSValueConst): JSValue =
  let val = ?trace(JS_GetSomeObjectSomehow(ctx))
  let atom = ?JS_NewAtom(ctx, "someFunction")
  let res = ?trace(JS_Call(ctx, val, atom, nil, 0))
  # ...
  return JS_UNDEFINED

That is memory-safety crossed.

Type-safety takes a bit more attention. In principle, 0.4.4 already had bindings that turn JSValues into primitive types or JS objects; for example, you could register a JS procedure like:

proc createElement(document: Document; localName: string): Element {.jsfunc.} =
  ...

and you'd get full type safety. However, there were a couple types left that required automatic reference counting to manage properly:

Callback functions
Untyped JS objects (e.g. addEventListener takes one)
ArrayBuffer, typed arrays in general
String views (in 0.4.4, every function call involving strings copied the string)

The way to work around this (besides copying) is to receive a JSValueConst as a parameter - conceptually an "any" type - and convert it manually. However, WebIDL defines a left-to-right parameter conversion order, so doing this means you now have to manually replicate this. For example, this is wrong:

proc decode(ctx: JSContext; this: JSTextDecoder;
    jsInput: JSValueConst = JS_UNDEFINED; options = TextDecodeOptions()):
    JSValue {.jsfunc.} =
  var input: JSArrayBufferView
  if not JS_IsUndefined(jsInput):
    ?ctx.fromJS(jsInput, input)
  ...

...because options is a dictionary whose conversion is observable from JS, so jsInput must be type-checked before options. At the same time, JSArrayBufferView is just a simple view of the buffer, so moving the conversion into the parameters would also give an opportunity for JS to invalidate the ArrayBuffer (e.g. using transfer inside a getter in options), causing UAF.

The solution, therefore, is to type-check input first, but then turn it into a simple object reference:

proc decode(ctx: JSContext; this: JSTextDecoder; input = BufferSource(nil);
    options = TextDecodeOptions()): JSValue {.jsfunc.} =
  # ...
  var oq = ""
  let stream = this.stream
  if input != nil:
    for chunk in this.tdctx.decode(input.toOpenArray(ctx), not stream):
      oq &= chunk
  # ...

Here, BufferSource is an automatically ref-counted alias of JSObject. When needed, toOpenArray retrieves the ArrayBufferView and yields an openArray[uint8]; this is reasonably safe, since openArray may only be passed through parameters. If the BufferSource was invalidated in the meantime, the conversion produces an empty view, so all is fine.

The other cases are even simpler:

Strings receive a DOMString type which is a view to a refcounted QuickJS string. In other words, copying is no longer necessary[9].
Objects receive a JSObject type which is a pointer type-checked using JS_IsObject.
Callbacks receive a JSCallback type which is JSObject type-checked using JS_IsFunction.

These are all fairly efficient, e.g. JSObject (a pointer) only takes up one machine word, unlike JSValue (a pointer and a tag) which takes up two. For example, this means that when a website stores an event listener, we have to allocate 8 bytes less on 64-bit systems. (That doesn't sound like a lot, but these things add up.)

Conclusion

And... that's it! Chawan now manages memory with one GC and not two, which is faster, safer, and more memory efficient than the previous solution.

Although compromises this took show that it's still at the bleeding edge of what Nim is capable of handling (after all, ARC is only considered stable since around 2023), I'm overall satisfied with how it turned out.

I have of course omitted many details; if you're interested, the jsguide document provides a more detailed overview of the JS bindings, and of course, the code is available at the usual locations.

Appendix: some difficulties

ARC being a relatively new feature, it has some quirks that made implementing all this more painful than expected. Here are the worst offenders.

Nim likes to copy

Although Nim has been capable of returning view types for a good while, the standard library has not always been updated to use these. This comes back to bite us when trying to mark members of a Table:

proc mark(rt: JSRuntime; window: Window; markFunc: JS_MarkFunc) {.jsmark.} =
  for k, svg in window.svgCache:
    rt.markObj(svg, markFunc)

The problem here is that the pairs iterator for Table lacks lent annotations, so looping over it temporarily increases the reference count for each and every svg. This in turn makes markFunc very confused as it's doing cycle collection by temporarily adjusting & checking the reference count.

The solution is simple: don't use std/tables at all. Chawan already had some specialized hash tables, so I just consolidated all of them into a tabutils module and replaced every remaining instance of Table.

Also, to detect similar issues in the future, I added a debug assertion that prevents adjusting refcounts inside jsmark.

Nim doesn't like to copy

This one nearly drove me to give up and rewrite the browser in Rust. In short, a compiler bug caused this to crash:

type
  A = ptr AObj

  AObj = object
    b: B

  B = distinct ptr BObj

  BObj = object
    a: A

proc `=destroy`(r: var B) =
  echo "destroy b"

proc main() =
  var a = create(AObj)
  var b = B(create(BObj))
  a.b = b
  cast[ptr BObj](b).a = a

main()

...because a cast (incorrectly) didn't count as an use of b (up until & including 2.2.10), so the reference got moved into a.b, and then Nim (correctly) set the moved references to zero, so you'd end up with a NULL dereference.

Credit where credit's due, ringabout fixed it very quickly after reporting (thanks!) But with the abysmal Nim packaging situation I can't just rely on this (I still support compilers from 2023...), so I had to find some workaround.

A straightforward way is "just avoid cast", but it's not feasible, because our dot accessors using experimental:dotOperators look like:

template `.`[T](r: JSRef[T]; field: untyped): T =
  cast[ptr T](r).field

If I change that cast to a conversion:

template `.`[T](r: JSRef[T]; field: untyped): T =
  (ptr T)(r).field

then I have the problem that whenever I do something like

document.getElementById(name).parentNode = parent

that is translated to

(ptr Element)(document.getElementById(name)).parentNode = parent

and since this is a conversion, not a cast, Nim thinks there is no refcounting to be done anymore, and straight up leaks the Element reference. (This, I think, makes sense, it's just somewhat counter-intuitive.)

In the end, the macro system came to a rescue: I changed the above template to a macro that analyzes the AST received. If there is a call, we can safely cast (the compiler cannot move anything, so the bug cannot manifest), and otherwise we can convert (we already have a view, so there is nothing to leak). You can marvel in the hack here (provided Codeberg isn't at the verge of death at the moment).