Ephemerons

[JarrettBillingsley]

Cycles between key-value pairs in weak-key-strong-value tables can keep the values alive even if they aren't referenced anywhere but the table:

    local t = hash.WeakKeyTable()
    local a = {}
    t[a] = {x = a} // cycle!
    a = null
    gc.collectFull()
    writeln(#t) // should print 0, but prints 1 :I

The solution is ephemerons. I have been able to find shockingly little about implementing ephemerons in a reference-counted GC, maybe because virtually all modern GC research is focused on tracing GCs. I did manage to find https://bugzilla.mozilla.org/show_bug.cgi?id=547941#c50, quoted here:

Consider an ephemeron table T, a key A and a value B. We model that by a strong reference from T to B and by a weak reference from T to A.

Suppose now the cycle collector starts to run and detected all the edges for the initial set of gray objects. Then the CC colors black (alive) any gray objects that has an external reference to it. Normally then the CC proceeds recursively to mark black any object recursively reachable from the black (alive) objects. That is modified so during the recursion the CC skips the references from T to any of its value B.

(This would be in base_gc.cycleScanBlack.)

Then, when this is finished, the algorithm consider all black tables T

(Does he mean ALL ephemeron tables in existence, or just those in the potential reference cycle set? My guess is the latter, since it's only cycles which cause this ephemeron issue, but I'm not sure.)

and for them marks as black any key B recursively if the corresponding key A is not gray. Note that, while we consider only tables explicitly colored black, the key A may be "not gray" not only because it is black but also because it is not a member of the initial gray set. That is, A was not member of any cycle yet. This difference comes from the fact that we add strong references only from T to B and not to A.

(I'm not really sure what he means by "initial grey set" here. He then says "A was not a member of any cycle yet"... huh? This of course could be terminology for a different collector and a distinction that isn't necessary for Croc's, but I could be wrong.)

Since this may turn more tables and keys black, that has to be run repeatedly in the same way as the GC marking does in the comment 35.

(Again, not sure which tables are under consideration -- are we guaranteed that only tables in the cycle need to be considered, or all ephemeron tables?)

After this is done, any value B that remains gray in a black T is only referenced via T so it can be removed. This will decrease the reference count to B. After this is done for all such B, then the the CC can proceed with collecting all gray cycles the same way it does now.

So I at least have a starting point if I add ephemeron tables. Would they be regular tables with a flag set on them, or a new type...?