Re: Copying GC and finalization

Julian Stecklina wrote:


> Hello,
>
> I am looking for ways to implement finalization of and weak pointers
> to objects in a copying garbage collector. I am quite puzzled on how
> to implement this without losing the nice property of copying garbage
> collectors that there is nothing to do for objects that have become
> garbage.
>
> If anyone can point me to some information, it would be very helpful.
>
> Regards,
> --
> Julian Stecklina
>
> LISP has survived for 21 years because it is an approximate local
> optimum in the space of programming languages. - John McCarthy (1980)


Weak references are easy. During the scavenge any weak container
encountered isn't scavenge immediately. Instead it is added to a
linked list of weak containers (you can thread the list through the
corpse in past space, scavenging the container to survivor space
without scavenging its referents). Then once the scavenge is
complete, traverse the list of weak objects. Any referents that
remain in past space are dead and these fields can be nilled. You can
also arrange that any weak containers that have lost referents get
notified (e.g. add to a queue, have a system-level process extract the
containers form the queue and send them a notification).


Implementing finalization above this is possible but primitive. You
arrange that there is a proxy object for any finalizable object.
Finalizable objects are remembered in a weak container. Proxies are
held in a parallel strong array. When the weak container gets
notified it has lost referents it searches for nilled references,
fetches the corresponding proxy from the weak array, and finalizes the
proxy.


The major problem with this post-mortem finalization scheme is that it
is difficult to keep the proxy up to date.


A better scheme is to use guardians or ephemerons. I'm partial to
ephemerons myself. Ephemerons are marked specially and hold onto some
object. Like weak arrays, when encountered during a scavenge they are
not immediately scavenged unless their referent has already been
scavenged. Once the scavenge has completed, the ephemerons are
processed. Any whose referent has not been scavenged are the sole
referrers to their referent and so can be "triggered", identified as
having a reference to an object that would be collected except for
still being referenced by an ephemeron.


An ephemeron is triggered by placing it in a queue for subsequent
notification and then scavenging its referent (and its referents). In
the course of this more ephemerons may be encountered. The process
continues until all reachable objects have been scavenged and the
reachable ehemerons divided into triggered and untriggered ones.
Subsequently the triggered ephemerons are notified and can then
finalize their referents as a triggered ephemeron knows its referent
is only referenced by other triggered ephemerons.


To arrange for an object to be finalized simply create an ephemeron with
the finalizable object as its referent and put the ephemeron in some
container. On finalizing its referent an ephemeron also removes itself
from the container and is subsequently garbage-collected.


Scavenging can be substituted by or combined with a scan-mark (possibly
incremental). This is the scheme we use in VisualWorks, a leading
Smalltalk system (www.cincomsmalltalk.com)




Heer's a reference for the ephemeron paper:


Ephemerons: a new finalization mechanism
Barry Hayes
Conference on Object Oriented Programming Systems Languages and Applications
Proceedings of the 12th ACM SIGPLAN conference on Object-oriented
programming, systems, languages, and applications
pp 176 - 183, 1997


HTH
--
_______________,,,^..^,,,____________________________
Eliot Miranda Smalltalk - Scene not herd

Return to the comp.compilers page.
Search the comp.compilers archives again.