add ordered guardians

[mflatt]

Ordered finalization is intended to make certain finalization patterns more composable. A library might want to finalize internal parts of a data structure while allowing applications to finalize external pieces that refer to the internal parts. In that case, the goal is to finalize the internal pieces only after the application is definitely done with the external parts, including finalization on those external parts. Ordered finalization seems difficult to use correctly, but it looks like a good option for handling foreign resources.

This patch includes two changes to guardians: it uses the seginfo trigger mechanism to avoid quadratic-time handling of guardian chains (which are, granted, unlikely in practice), and it adds an optional ordered? argument to make-guardian to provide a form of ordered finalization. I initially planned to stage those changes as two commits, but various representation choices interact, so they're together here.

The implementation adds a field to a guardian entry, and so there's a second field to preserve double-word alignment – which I think is necessary to declare and initialize to work right with the GC, but correct me if that's not right. Since two words seem to be necessary for the one extra bit of information I need to distinguish ordered and unordered finalization, I used the second word to make the handling of triggers more convenient.

Another possible choice is to keep separate lists of ordered and unordered entries, but that seems much less convenient in the GC implementation. Also, the trigger lists in the seginfo record would have to be kept separate somehow, and triggers for "hold" versus "final" lists would have to be kept separate. I can think of ways to encode two extra bits of information in the current record, but the ways I see are too ugly unless this seems like a crucial issue.

The documentation update is minimal. It's unlikely to be a good specification of ordered finalization, and it certainly doesn't get across the pitfalls and intended use of ordered finalization.

[dybvig]

Thanks!

I agree that guardians should be handled using the trigger mechanism even though chains might be rare.

sweep() is probably not the right tool to use to process the contents of the objects guarded by an ordered guardian. I believe there are at least three problems that might result:

• Weak-pair car fields are not processed by sweep(), so objects reachable from the car field will not be ordered properly, and cycles through the car field will not prevent the weak pair from being finalized.

• The processing of ephemeron pairs is deferred via add_ephemeron_to_pending(). I haven't traced this through, but this might cause a problem similar to the problem with weak pairs.

• In general, cycles leading back to the object passed to sweep() will cause the object to be forwarded out from under sweep(). That is, the first two fields of the object being swept will be overwritten with the forward marker and forwarding address. In some cases where this might cause harm, it happens not to do so; for example, if the car field of a (regular) pair points to the pair, relocating the car causes the pair's fields to be overwritten, but because the cdr field is now a pointer to the new-space pair, relocating the cdr field causes no harm. In the case of code objects, overwriting the first two fields can cause the wrong length to be passed to S_record_code_mod(). While the latter issue is easily fixed by grabbing the length early, the situation is inherently fragile.

It might be possible to solve the weak-pair and ephemeron-pair problems with a specialized version of sweep(), though I believe that if a weak or ephemeron has already been forwarded, we'll still have to sweep it. The other problem seems trickier. We could solve it by copying guarded objects before sweeping them, but that's an unfortunate bit of extra run-time overhead.

[mflatt]

In the case of weak and ephemeron pairs, I concluded that weak references shouldn't count against ordered finalization. I'm not 100% certain of that choice (or anything else about finalization), and it makes some applications that I have in mind more difficult, but it seems workable. Meanwhile, having weak references prevent finalization doesn't seem like it would work in my application, because ordered-finalized objects will typically reside as keys in a weak hashtable.

I didn't think of the problem with sweep and forwarding. A shortcut of not copying+sweeping for objects that contain only non-ptr values would likely cover most applications that I have in mind.

[mflatt]

It turns out that the fragile situation goes wrong if a pair's car refers back to the pair. The forwarding mark gets overwritten with the forwarded pointer for the car, while the cdr has been modified to the forwarded pointer. In the end, an extra pair is created, and a weak reference can see the wrong copy.

I think maybe a pair is the only object that can go wrong that way, but the new commit tries to resolve the fragility more generally. Instead of making a copy of the object, sweep_in_old() scans for immediate self-references, and it just copies the object normally if it finds any. Only if the object is free of immediate self references, it continues on to sweep().

The duplication of the sweep() dispatch is a little awkward, but seems ok to me. I'm less happy with the duplication of seep_record(), but maybe it's ok. Handling threads seemed like too much work and unlikely to be useful, so sweep_in_old() just treats every thread as referring to itself.

[mflatt]

Rebased.

This implementation of ordered guardians has worked well for Racket-on-Chez. Racket's drawing and GUI libraries particularly rely on ordered finalization to ensure that resources are safely deallocated, and ordered guardians have worked as expected over the past year.

[mflatt]

Included in v9.9.9 merge 47daa9b34016de84fd111801d9d589d15a523abe.