[Gc] Two-phase finalization?

[David Kastrup]

The Scheme interpreter Guile has been using the Boehm GC since version
2.0 and that's part of the reason the music typesetter LilyPond has not
yet been ported to Guile 2.

Guile offers user-defined types and in particular allows registering a
deallocation procedure for them via

-- C Function: void scm_set_smob_free (scm_t_bits tc, size_t (*free)
(SCM obj))
This function sets the smob freeing procedure (sometimes referred
to as a "finalizer") for the smob type specified by the tag TC. TC
is the tag returned by ‘scm_make_smob_type’.

The FREE procedure must deallocate all resources that are directly
associated with the smob instance OBJ. It must assume that all
‘SCM’ values that it references have already been freed and are
thus invalid.

It must also not call any libguile function or macro except
‘scm_gc_free’, ‘SCM_SMOB_FLAGS’, ‘SCM_SMOB_DATA’,
‘SCM_SMOB_DATA_2’, and ‘SCM_SMOB_DATA_3’.

Note in particular the second paragraph which clearly states that with
respect to finalization order, there are no guarantees. Now LilyPond
uses STL containers with pointers to other C++ structures with a Scheme
presence a lot. It keeps these structures from being collected by using
a mark procedure registered via

-- C Function: void scm_set_smob_mark (scm_t_bits tc, SCM (*mark) (SCM
obj))
This function sets the smob marking procedure for the smob type
specified by the tag TC. TC is the tag returned by
‘scm_make_smob_type’.

Defining a marking procedure may sometimes be unnecessary because
large parts of the process’ memory (with the exception of
‘scm_gc_malloc_pointerless’ regions, and ‘malloc’- or
‘scm_malloc’-allocated memory) are scanned for live pointers(1).

The MARK procedure must cause ‘scm_gc_mark’ to be called for every
‘SCM’ value that is directly referenced by the smob instance OBJ.
One of these ‘SCM’ values can be returned from the procedure and
Guile will call ‘scm_gc_mark’ for it. This can be used to avoid
deep recursions for smob instances that form a list.

It must not call any libguile function or macro except
‘scm_gc_mark’, ‘SCM_SMOB_FLAGS’, ‘SCM_SMOB_DATA’,
‘SCM_SMOB_DATA_2’, and ‘SCM_SMOB_DATA_3’.

Now the problem we encounter is that if some structure A points to B and
some structure B points to A and both A and B are placed into
finalization, then the finalization of A will delete the associated C++
structure. If now a mark pass is allowed through B, it will try to
access the deleted C++ structure of A.

Topological ordering will not do the trick since cyclical references are
quite typical (a NoteHead has a reference to the corresponding Stem, a
Stem has references to all corresponding NoteHeads).

So what we need here is a setting/hook where queuing some group of
objects for finalization will _stop_ any marking on them (including
false positives of the conservative marking process) before the first
finalization through a type hook stored via scm_set_smob_free on any
member of that group of objects occurs.

Individual objects don't have hooks of their own but they have some
additional bits available where one could record "placed into
finalization queue, don't call its scm_set_smob_mark hook any more"
information.

The problem is how to get this information, or how to get these
semantics from Boehm GC. Any ideas?

[David Kastrup]

Post by David Kastrup
Now the problem we encounter is that if some structure A points to B and
some structure B points to A and both A and B are placed into
finalization, then the finalization of A will delete the associated C++
structure. If now a mark pass is allowed through B, it will try to
access the deleted C++ structure of A.
Topological ordering will not do the trick since cyclical references are
quite typical (a NoteHead has a reference to the corresponding Stem, a
Stem has references to all corresponding NoteHeads).

Have all of them corresponding C++ objects? Do you want the garbage
collector to devise a safe deallocation order, or does deallocation
happen by another mechanism?

No, a "safe deallocation order" is unachievable because of cycles.
Guile has replaced its own allocator with the Boehm GC. There is a
mismatch in semantics for type hooks registered with
scm_set_smob_free/scm_set_smob_mark which have the following
description:

-- C Function: void scm_set_smob_free (scm_t_bits tc, size_t (*free)
(SCM obj))
This function sets the smob freeing procedure (sometimes referred
to as a "finalizer") for the smob type specified by the tag TC. TC
is the tag returned by ‘scm_make_smob_type’.

The FREE procedure must deallocate all resources that are directly
associated with the smob instance OBJ. It must assume that all
‘SCM’ values that it references have already been freed and are
thus invalid.

It must also not call any libguile function or macro except
‘scm_gc_free’, ‘SCM_SMOB_FLAGS’, ‘SCM_SMOB_DATA’,
‘SCM_SMOB_DATA_2’, and ‘SCM_SMOB_DATA_3’.

The FREE procedure must return 0.

Note that defining a freeing procedure is not necessary if the
resources associated with OBJ consists only of memory allocated
with ‘scm_gc_malloc’ or ‘scm_gc_malloc_pointerless’ because this
memory is automatically reclaimed by the garbage collector when it
is no longer needed (*note ‘scm_gc_malloc’: Memory Blocks.).

-- C Function: void scm_set_smob_mark (scm_t_bits tc, SCM (*mark) (SCM
obj))
This function sets the smob marking procedure for the smob type
specified by the tag TC. TC is the tag returned by
‘scm_make_smob_type’.

Defining a marking procedure may sometimes be unnecessary because
large parts of the process’ memory (with the exception of
‘scm_gc_malloc_pointerless’ regions, and ‘malloc’- or
‘scm_malloc’-allocated memory) are scanned for live pointers(1).

The MARK procedure must cause ‘scm_gc_mark’ to be called for every
‘SCM’ value that is directly referenced by the smob instance OBJ.
One of these ‘SCM’ values can be returned from the procedure and
Guile will call ‘scm_gc_mark’ for it. This can be used to avoid
deep recursions for smob instances that form a list.

It must not call any libguile function or macro except
‘scm_gc_mark’, ‘SCM_SMOB_FLAGS’, ‘SCM_SMOB_DATA’,
‘SCM_SMOB_DATA_2’, and ‘SCM_SMOB_DATA_3’.

Note in particular that scm_set_smob_free states:

The FREE procedure must deallocate all resources that are directly
associated with the smob instance OBJ. It must assume that all
‘SCM’ values that it references have already been freed and are
thus invalid.

In contrast to that, finalizers in Boehm GC work with fully valid
objects. In particular, mark passes are made through the finalized data
that expect operative data and consequently call for topologically
sorted finalization while scm_set_smob_free may not depend on any valid
pointers for doing its work: it really is much more related to
destructing objects than to finalizing them.

I _think_ that reading gc.h I have found a workable solution: set Java
collection semantics with GC_set_java_finalization (1);

GC_API GC_ATTR_DEPRECATED int GC_java_finalization;
/* Mark objects reachable from finalizable */
/* objects in a separate post-pass. This makes */
/* it a bit safer to use non-topologically- */
/* ordered finalization. Default value is */
/* determined by JAVA_FINALIZATION macro. */
/* Enables register_finalizer_unreachable to */
/* work correctly. */
/* The setter and getter are unsynchronized. */
GC_API void GC_CALL GC_set_java_finalization(int);
GC_API int GC_CALL GC_get_java_finalization(void);

And then, during finalization, clear out each finalized object's Guile
type-id so that no more hooks (in particular no hook set with
scm_set_smob_mark) will be called in any separate post-pass and no
dependency on the destructed C++ objects or their memory exists at the
time of the post-pass (not that I understand the post-pass' utility in
the first place but that apparently is what's causing the problems shown
in <URL:http://debbugs.gnu.org/cgi/bugreport.cgi?bug=19883>).

As far as I understand the code, the Guile-2 code base already does set
GC_java_finalization. So all that should remain would be clearing out
the type identification for data at finalization time.

[David Kastrup]

Post by David Kastrup
Now the problem we encounter is that if some structure A points to B and
some structure B points to A and both A and B are placed into
finalization, then the finalization of A will delete the associated C++
structure. If now a mark pass is allowed through B, it will try to
access the deleted C++ structure of A.

The typical "solution" to breaking cycles for finalisation is to arrange
objects differently. I use "quotes" because this is more of a work-around,
but I believe that it's the best solution anyone has proposed to the general
problem (I don't know if this will be suitable for lillypond).
A* -> B*
^ |
+-----+
(I use * to indicate that this object has a finalize.
A1*
^
|
A -> B*
^ |
+----+
Now B can be finalised first, followed by A1. So typically you would
put the fields (like file descriptors) in A1 and the other fields in
A. I'm trying to imagine what this means for Lillypond, maybe they're
glyphs for drawing notes or something...

Well, the problem with that approach is that "arrange objects
differently" is a whole lot of work given the current amount of objects,
and that work is not really incremental as you can expect crashes until
finished.

And that's just LilyPond: the documented semantics of the respective
Guile hooks don't match for other applications as well. The main coping
strategy when brought up on the Guile developer list was an exuberant
call for not using mark hooks at all and making all memory GC-scanned.
However, I am less than enthused about that approach for an application
that can eat the majority of addressable memory with large chores (given
32-bit executables) when basically all memory is managed with
conservative garbage collection: I expect too many false positives then.
It's also somewhat tricky to change the manner in which standard C++
data structures provided by the STL libraries manage their allocations
and deallocations.

So I prefer to stick with the same code used with Guile 1 and instead
fix Guile 2 (or put workarounds into LilyPond to the same effect) to
actually have the same semantics as previously regarding the "free"
hooks.

I _think_ that the solution sketched in another mail (basically setting
Java collection semantics for bdwgc in combination with using
finalization for disabling the mark functionality on the destructed
objects) should be workable. So I hope to have self-answered my
question.

I realize this may not be helpful, it's not exactly the answer you
asked for, and I can't begin to guess at how this would work for
Lillypond. However I would like to say that I LOVE the lillypond
software. I have a significant vision impairment and lillypond allows
me to enlarge my sheet music (usually by typing it out again). Thank
you!

My mother has macula degeneration and has stopped playing the violin
because of being unable to sight read well enough. I feel somewhat
guilty for not having worked out a solution for her. But I don't really
see how I could keep up providing scores for her in parallel with the
other stuff I am doing.

[Paul Bone]

Post by David Kastrup

Post by David Kastrup
Now the problem we encounter is that if some structure A points to B and
some structure B points to A and both A and B are placed into
finalization, then the finalization of A will delete the associated C++
structure. If now a mark pass is allowed through B, it will try to
access the deleted C++ structure of A.

The typical "solution" to breaking cycles for finalisation is to arrange
objects differently. I use "quotes" because this is more of a work-around,
but I believe that it's the best solution anyone has proposed to the general
problem (I don't know if this will be suitable for lillypond).
A* -> B*
^ |
+-----+
(I use * to indicate that this object has a finalize.
A1*
^
|
A -> B*
^ |
+----+
Now B can be finalised first, followed by A1. So typically you would
put the fields (like file descriptors) in A1 and the other fields in
A. I'm trying to imagine what this means for Lillypond, maybe they're
glyphs for drawing notes or something...

Well, the problem with that approach is that "arrange objects
differently" is a whole lot of work given the current amount of objects,
and that work is not really incremental as you can expect crashes until
finished.

I can appriciate that. It also increases (maybe doubles) your object count
and may therefore have a performance cost.

Post by David Kastrup
And that's just LilyPond: the documented semantics of the respective
Guile hooks don't match for other applications as well. The main coping
strategy when brought up on the Guile developer list was an exuberant
call for not using mark hooks at all and making all memory GC-scanned.
However, I am less than enthused about that approach for an application
that can eat the majority of addressable memory with large chores (given
32-bit executables) when basically all memory is managed with
conservative garbage collection: I expect too many false positives then.
It's also somewhat tricky to change the manner in which standard C++
data structures provided by the STL libraries manage their allocations
and deallocations.
So I prefer to stick with the same code used with Guile 1 and instead
fix Guile 2 (or put workarounds into LilyPond to the same effect) to
actually have the same semantics as previously regarding the "free"
hooks.
I _think_ that the solution sketched in another mail (basically setting
Java collection semantics for bdwgc in combination with using
finalization for disabling the mark functionality on the destructed
objects) should be workable. So I hope to have self-answered my
question.

That seems reasonable as far as I can tell.