Weak References and Finalization


A particularly useful feature of Smalltalk is automatic garbage collection. The beauty of garbage collection is that it relieves one of the responsibility of explicitly managing the lifetime of objects, and consequently one doesn't have to spend 80% of one's time fixing bugs caused by holding onto memory for too long or short a time. You might be familiar with the nightmares of explicit memory management in other languages! Smalltalk's philosophy, in contrast, is that memory management is the responsibility of the environment, not the programmer, and so the Virtual Machine (VM) automatically reclaims the space used by objects when they are no longer in use. The VM determines that an object is garbage by detecting that there is no reference path by which it can be reached from the "roots of the world". In Smalltalk the system dictionary (imaginatively named Smalltalk) contains the roots of the world, and every other interesting object is reachable from there. Even if an object references itself, or is part of an incestuous chain of indirect circular references, the VM will find it and reclaim it if it is not reachable from a root.

There is, of course, a fatal flaw in Smalltalk's garbage collection scheme - it is based on the assumption that the entire world is implemented in Smalltalk (a pleasant thought, but not entirely practical).

Early versions of Smalltalk-80™ did indeed provide the entire operating system, but today we need to integrate with external systems that provide windowing and other operating system services. In order to do this, we need to be able to "own" external resources (typically by holding onto a "handle"), and to release them when they are no longer required. For example, if we wanted to implement a Bitmap class for Dolphin, then we would need to make use of the native Windows™ bitmaps by encapsulating their handles in a Dolphin class. When the Dolphin Bitmap object is garbage collected we must ensure that the external resource is also freed. We don't want to explicitly program the freeing every time we're finished with a bitmap as we don't always know when we're finished, it's not consistent with other objects, and, in any case, its far too much bother, and far too easy to get wrong. To enjoy those sort of masochistic pleasures we suggest using C++. The solution to the problem in Dolphin is Finalization.

There is a further problem which manifests itself in circumstances where we need to maintain global registries of objects, but only while they remain "live".

As Smalltalk programmers concerned with our personal hygiene, we don't like globals, but there are occasions when we need some means of globally accessing objects. We might, for example, prefer (or need) to share a single instance of a class so that no more than one instance has the same "value" or contents.

Symbols are an example of a class where we need a single unique instance for each representable value, and where we require global access to these instances. There is also an infinite set of possible symbol values, so we cannot simply pre-create all the instances. The solution is to use a global registry of symbols (a symbol table). Each time we come across a symbol value we've not seen before, we put a new symbol into the symbol table so that we can use it again the next time we see that value. This is a great way to acquire a symbol table. It is also a great way to acquire a load of symbols which are no longer used, except in the symbol table (including all the typos one makes when programming). We could periodically purge all the dead symbols, but this requires explicit intervention, and is hardly a satisfactory solution to the problem in general.

So occasionally we need to maintain registries of objects internal to Smalltalk. The Dolphin solution to this problem is Weak References.

We will almost always want to maintain a registry of objects which own external resources, in order to provide efficient and effective sharing and access. The Dolphin solution to this is a combination of Finalization and Weak References.

N.B. There are similar facilities in other Smalltalks, but they are generally less comprehensive and powerful. There are, unfortunately, no standard mechanisms.

And finally??

Generally we don't want to be bothered about the expiry of an object, we let the VM deal with cleaning up all the old rubbish. Finalization is for those cases where we do want, or need, to get involved.

Dolphin provides a mechanism by which objects are informed when they are about to expire. How objects respond to this notification, i.e. how they finalize themselves, is their own business - Zen and the Art of Finalization provides advice.

Any Dolphin object can be marked as requiring finalization, on an instance specific basic, and is then guaranteed to receive a #finalize message before it actually dies (i.e. the memory it occupies is freed). The default implementation of #finalize (in Object) is to do nothing:

finalize
	"Perform any death-bed operations as the receiver is about to expire. The default is to
	do nothing.

	It is not necessary to remove an objects finalization mark, since this has already been
	done by the garbage collector. Should you wish an object to be finalized again, you must
	send it #beFinalizable again (this can be done from the #finalize message, but be careful
	as this may leave the object in an endless loop of finalizations, consuming system resources).

	The receiver will cease to exist at some time after its finalize method has completed (at
	the very latest at the next GC), unless that method causes additional references to be 
	taken to the receiver. It is a good idea to remove any circular references in an object's
	finalize method to shorten its remaining life.

	Note that this method is only sent to objects which are marked as requiring
	finalization (see #beFinalizable) when their last strong reference is removed. The
	object will not receiver the message immediately, but only on the next run of the 
	Finalizer process (which runs at a low priority), and if the object has outstanding 
	weak references, only then after a run of the full garbage collector (which is necessarily 
	a relatively infrequent occurrence)."

The comment in this method is quite instructive, but we'll ignore some of the details for now.

Finalization explains the procedure for implementing finalization in some detail, but in summary:

Having taken these steps you can merrily create objects in the certain knowledge that they will clean up after themselves when they are no longer required, because the MemoryManager makes certain guarantees to objects marked as requiring finalization (those it considers to have "last requests"):

The memory manager is careful to ensure that objects queued for finalization remain valid until their finalization is complete (and of course objects can rescue themselves in the #finalize method too, although they will have lost all their former weak references), and this can result in some apparent strangeness when finalizable objects reference other finalizable objects. The precise finalization behaviour is defined in The Rules. It may be important to understand these rules in order to correctly code #finalize methods where non-trivial relationships exist between finalizable objects and/or weakly referencing objects, but this is an advanced topic so be warned!.

It is worth noting that finalization is performed asynchronously by a lower priority process, and this has a number of implications:

Weak References

A Weak Reference (also called a Weak Pointer Reference) is one whose hold on other objects is only tenuous, and which will permit those objects to be garbage collected if there are no references to them from the more assertive members of the object community.

The fundamental concept behind weak references is simple; they are ignored by the garbage collector when it is traversing the object reference graph from the roots of the world in an attempt to locate accessible objects, and consequently objects which are reachable from the root only if a weak link is followed, are garbage.

Dolphin permits any indexable pointer object to be weak - the attribute is not limited to objects of a particular class as in some other Smalltalks. The named instance variables of such weaklings are not weak - if they were they would find it well nigh impossible to maintain their internal state (they'd risk losing it on every GC). This is not, in practice, a limitation because it is always possible to simulate a named variable with a pair of accessors and a fixed index, and in any case it is mostly collections which need to be weak, and these are more conveniently implemented with indexable variables.

The memory manager also makes certain guarantees to objects marked with the weak attribute:

Note that the GC does not remove references to corpse from previous reapings. Should this be the behaviour desired, then weaklings must tidy away corpses themselves in their #elementsExpired: method (e.g. see WeakArray>>nilAllCorpsesAndDo:).

You may be wondering why the memory manager doesn't just nil expired weak references during the GC, rather than replacing them with corpses? Well, this might work for simple data structures, but many objects (e.g. hashed collections) are too complicated, and need to be able to identify which of their elements have been lost in order to carry out efficient and effective repairs. One might also need to be able to identify the deaths in order to perform pseudo-finalization on behalf of objects which are not in themselves finalizable (e.g. by keeping a parallel collection of "executors").

How does one implement weaklings? This depends on whether the weaklings need go through a mourning process in order to repair themselves after suffering bereavements (i.e. they need to implement #elementsExpired:). There are no special requirements on bereavement immune weaklings which do not need mourn, but otherwise the procedure is quite involved, not least because mourning weaklings need to be process safe. It is preferable to re-use an existing weak collection (directly or by encapsulation) rather than implementing your own. If this is not possible, then Weakling explains the procedure in detail.

Example weaklings can be found in Dolphin implementing the symbol table, and the dependency and event mechanisms.

How do Finalization and Mourning Actually Work?

The identification and queuing of objects for finalization, and conversion of weak references to corpses, is a by-product of garbage collection (although there are some fairly significant modifications to the garbage collector to enable this "by-product"). The rules by which this process is governed are described below. Precisely when garbage collection is performed (and therefore when objects finally get a chance to carry out their last requests) is a policy decision made by the memory manager (and for the current beta release, this policy is rather simplistic). The memory manager is also responsible for administering last rites (sending #finalize) and bereavement counselling (sending #elementsExpired:) for those objects queued by the garbage collector.

The memory manager maintains a pair of processes for each of these tasks, referred to as the Finalizer and the Undertaker. The respective tasks of these two processes are to dequeue objects from the separate finalization and bereavement queues, and send them #finalize and #elementsExpired: messages. The main loop of these processes are very simple, for example:

finalizerMain
	"Private - Wait for objects to be queued to the system finalization queue, then attempt to empty that queue. 
	The VM signals the queue semaphore each time it queues a group of objects to the queue so the 
	semaphore's signal count does not reflect the number of elements waiting in the queue (this is to 
	reduce the asynchronous signalling overhead and to permit user code to force synchronous finalization 
	by directly invoking administerLastRites). Should the finalizer be prematurely terminated by an error 
	occurring in a #finalize or #finalizeElements: method, then it will be restarted the next time the 
	system goes idle, but the semaphores signal count will not be reset, so any waiting objects should 
	get serviced in the near future, assuming Processor time is available."
	
	finalizer := Processor activeProcess.
	finalizer name: 'Finalizer'.
	[finalizer == Processor activeProcess] whileTrue: [
		lastRequests wait. 
		self administerLastRites]

Communication between the memory manager's processes and the VM is achieved by the use of a pair of Semaphores which the VM signals whenever it places new elements in the queues. The VM only signals each semaphore once, no matter how many items it places in their respective queues, so the processes employ a secondary loop to dequeue objects until the queues are empty, for example:

administerLastRites
	"Private - Dequeue dying objects from the system finalization queue, and send them a 
	#finalize message. Multiple finalization processes are permissible because access to the 
	VM queue is atomic (which is in any case required for synchronisation with the VM's garbage 
	collection activities). This allows a user Process to synchronously perform finalization at 
	certain points, for example, so that all objects pending finalization are processed before 
	the image is saved. This may be necessary because the Finalizer runs at a very low priority."
	
	| dying |
	[(dying := self dequeueForFinalization) isNil] 
		whileFalse: [dying finalize]

Objects dequeued for finalization, are not in any special state, so there are no restrictions on the operations which can be performed against them.

The finalizer runs at a priority one level above the base idle priority in order to minimize the impact of finalization on the foreground system processing. This can result in some delay before finalization if intensive processing is underway. However, as the comment in the method states, finalization can be forced at foreground priority at any time by simply sending #administerLastRites to the memory manager. For example, this is done when saving the image to ensure that objects requiring finalization are not saved down into the image:

onPreSaveImage
	"Private - Clean up before a snapshot. We perform a compacting garbage collect
	to minimize the image size, and then move objects queued for finalization. 
	Two garbage collects are performed to ensure that any objects surviving the first
	GC because they are referenced by objects pending finalization will be collected
	by the compacting GC. We need to ensure that all objects pending finalization
	do actually get finalized to ensure that those holding external resources 
	are cleared down, otherwise, when they are later finalized in a new session, 
	their internal state will be invalid (they will contain invalid handles). 
	It is not necessary to inform weak objects of their losses, because the Undertaker 
	runs at a high priority and should interrupt us to perform that task."

	self
		collectGarbage;
		administerLastRites

The undertaker, in contrast, runs at a very high priority (only just below the priority of the timing process which administers Delays). This is necessary because weaklings generally need to repair the damage sustained from the loss of constituents as soon as possible.

The memory manager monitors the state of its finalizer and undertaker whenever the system is about to go idle, and if it finds that either is not ready to run, or is not waiting on the appropriate semaphore, then it starts a new process. This is a defensive operation to try to prevent system melt down if finalization/mourning code either causes an exception, or inappropriately puts the process to sleep.

The Rules

The co-ordination and initiation of Finalization and the murdering of Weak References are the responsibility of the memory manager, and are performed during a garbage collection (GC) cycle, according to the following rules (you may want to skip this advanced topic):

You may be wondering why these complex rules are necessary, why not just finalize every candidate marked as requiring finalization? Well, the rules are designed to ensure that objects queued for finalization remain valid until their finalization is complete. If we simply queued every candidate for finalization, then we could not guarantee that constituent objects had not already been finalized. This would make coding #finalize methods horribly complicated and confusing.

Bereavement notifications are not sent to all weaklings by default, because the necessity of rescuing GC'able weak objects to receive the notification can potentially extend the lifetime of large groups of weak objects referenced by other weak objects (e.g. weak tree nodes) due to a "cascading rescue" effect. Cascading rescues significantly degrade the operation of the system because they may prevent garbage weaklings from being collected for many many GC cycles.

The memory manager must ensure that an object does not receive a #finalize message until there are no strong references to it (which are not circular), and we need to take account of strong references from objects which are queued for finalization in the same garbage collection cycle. Even if an object to be finalized is only referenced from another object to be finalized in the same cycle, we must delay its finalization until the next cycle, so that parents are finalized before children, otherwise the parent may not be in a valid state during its finalize. It is not acceptable to have the order of finalization depend purely on the ordering the objects are visited during garbage collection.

Where a finalizable object is circularly referenced (perhaps indirectly), we must ensure that it can be garbage collected - so this precludes simply marking any candidates for finalization, and then only actually finalising those which are unreferenced, because this would mean that circularly referencing finalizable objects (phew!) would never be garbage collected. In fact it is possible that an indirect circular reference could exist between two finalizable objects, and where this is the case there is no general mechanism for deciding which to finalize first, since there is no notion of ownership.

This complexity is probably one of the reasons that some other Smalltalks do not support finalization of objects directly. They have only weak references and implement finalization with it: Any object which is not directly reachable through a strong pointer chain is garbage collected, and any weak references are "nilled". The weakly referencing objects which suffer bereavements, are informed, and it is up to them to perform finalization actions on behalf of the objects that they have lost. This is typically achieved by having a copy of the finalizable objects, and using them as 'executors'. This approach makes garbage collection simpler, but is inefficient and requries more complex Smalltalk classes to support it. Furthermore, it does not address the finalization ordering problem. If you want to implement such finalization in Dolphin, you do so quite easily using mourning weak objects, because the Dolphin facilities are a superset.

Zen and the art of Finalization

With the capability to do object finalization, there is a a choice to make about when to use it. If anything, the temptation will be to overuse it, especially since the expression ObjectWhichParpsOnDeath new beFinalizable can provide almost instant gratification.

Those of us with a C++ background might be tempted into using confusing finalization, releasing, destructors and deleting, so here is a quote from the great man himself to clarify things:

'When implementing a garbage collection scheme one must decide whether to invoke the destructor for a collected object or not. Deciding which is the right thing to do is not easy. In [The C++ Programming Language, 2nd Edition] I wrote:

"Garbage collection can be seen as a way of simulating an infinite memory in a limited memory. With this in mind, we can answer the common question: Should a garbage collector call the destructor for an object it recycles? The answer is no, because an object placed on free store and never deleted is never destroyed. Seen in this light using delete is simply a way of requesting the destructor to be called (together with a notification to the system that the object's memory may be recycled). But what if we actually do want an action performed for an object allocated on the free store but never deleted? Note that this problem does not arise for static and automatic objects; their destructors are always called implicitly. Note also that actions performed "at garbage-collection time" are unpredictable because they may happen at any time between the last use of the object and "the end of the program." This implies that the state of the program at the time of their execution is unknown. This again makes such actions hard to program correctly and less useful than is sometimes imagined.

Where such actions are needed, the problem of performing an action at some unspecified "destruction time" can be solved by providing a registration server. An object that needs a service performed "at the end of the program" places its address and a pointer to a "cleanup" function in a global associative array."

I am now less certain. This model would certainly work, but maybe having the garbage collector call the destructors would be sufficiently simple to use to be worthwhile. That depends on exactly what objects are collected and what actions their destructors perform. This is a question that can't be decided by armchair philosophy, and there doesn't seem to be much relevant experience from other languages. Unfortunately, it is also a problem for which it is hard to conduct real experiments."

Byarne Stroustrup, The Design and Evolution of C++, 1994

So, Stroustrup points out that actually freeing the memory occupied by an object and object destruction are distinct things, and he cannot decide whether we should implicitly perform the latter when we automatically perform the former (i.e. garbage collection). Of course, Dolphin has superior garbage collection facilities to C++, and there are two forms of "destructor".

In C++ it is possible to both call operator delete against an object, AND invoke its destructor directly (with the former implicitly doing the latter). In Smalltalk one doesn't have the capability to do the former - one cannot (thankfully) force an object to disappear. Objects stubbornly continue to exist while there are outstanding references to them from other objects, and as one may not be the "owner" of all the sources of reference (and one cannot necessarily predict who will want to reference one's object), one can't always make an object disappear just by nilling the references one knows about. The nearest equivalent, though only by convention, is explicitly sending an Object the a #release or #free message - a kind of notification that one expects it to disappear, and want it to release any resources it is holding.

Sending #release or #free is similar to directly invoking a destructor. It can be error prone to send a release message to an object, though not as error prone as deleting a pointer which some other C++ object is referencing, because, depending on the implementation, it may put the object into an invalid state. Release messages should not be sent to objects from objects which do not "own" them, unless the release method leaves the object in an valid state. In general, try to have release methods which leave the receiver in a valid state, perhaps by using lazily initialising accessor methods.

In Smalltalk all objects are potentially garbage collectable, and one cannot predict when this will occur, or what state other objects in the system will be when this happens. Therefore #finalize can be safely used to do local destruction, but should not, in general, perform the kind of actions that release methods are likely to do (like removing the object from certain collections etc.), because one does not necessarily know what state those other objects are in. Indeed, in order for an object to be finalized, it must have no outstanding references, and even weak object references will have been changed to the corpse object by the VM before an object receives a #finalize message. It is for this reason that the default implementation of #finalize in Object does not send #release or #free. #finalize may be received by an object marked as finalizable some unspecified and unpredictable time after it becomes ready to be finalized. Indeed it is possible that an object may never get finalized, if, for example, there are processor hogging processes running at priorities above the system background priority (if this is the case arrange to send #administerLastRites to the memory manager from a higher priority process).

In summary: