It’s not a question of “or” – it can be “and”

Around 1995 we ported our Unix Common Lisp implementation onto the PC. Around this time Nick Levine and I had to do some work on delivery.
The Common Lisp system was delivered as an exe containing a small loader program which loaded a Lisp heap image into memory and started executing it. This was rather neat as virtually the whole system was written in Lisp, including the garbage collector, which meant that virtually all of the system could be patched by dynamically loading code to fix problems (patches were loaded early in the startup sequence so even bugs in the environment could be patched). People liked developing in the rich Lisp environment, but wanted to be able to deliver their applications to customers as standalone executables that didn’t contain the Lisp programming environment, mainly to make them smaller. Previously we had facilitated this by also giving customers a "base" image, a cutdown image without the programming environment into which components and then the application code could be loaded. Howver, the need to have two separate images caused all sorts of problems. For the PC version, we therefore decided to have a single Lisp image and to improve the tree shaking to get rid of large chunks of the code that the user application didn’t need. [It’s called tree shaking because you hold the roots of the tree (the application) and shake the apple tree hard – anything not attached to the root via branches of code will fall away].
 To make the tree shaking easy, the system mainly tried to clean away unneeded entry points and then get rid of information that could be reconstructed after a full garbage collection. Unfortunately there were particular problems around generic functions as defined by CLOS (the Common Lisp Object System). In CLOS the classes and the methods are separate entities. Methods are owned by generic functions which are generally bound to a symbol.
For example, here we define two classes A and B, with B a subclass of A. Two methods on a generic function FOO are defined, with the first specialising on an instance of A and the second on an instance of B.
CL-USER 1 > (defclass a()())
CL-USER 2 > (defclass b(a)())
CL-USER 3 > (defmethod foo ((x a)) (print "method on a called"))
CL-USER 4 > (defmethod foo ((x b)) (print "method on b called"))
CL-USER 5 > (foo (make-instance ‘a))
"method on a called"
CL-USER 6 > (foo (make-instance ‘b))
"method on b called"
During the tree shaking we really wanted to say that the method specialised on B can be shaken away if either the class B can be shaked away or if the generic function FOO can be shaken away. This is difficult to express via normal objects because the garbage collector works on an "or" preservation principle; an object is kept if any of the objects pointing to it are kept.
The solution we came up with was named a gate which I added to the garbage collector. It is basically an object that points to a single target and is pointed to by a number of other objects. The target object is kept alive only if all of the objects that point to it are kept alive (or if the gate itself is referenced via another path). In the mark and sweep collector that we had, this simply meant that we only marked through to the target when all of the incoming objects had been marked.
Before I can demonstrate that, we need to have a quick look at the finaliser mechanism that the Lispworks system used. Finalisers were known as special free actions. When an object flagged for special free action was unmarked after the garbage collection, a set of special free action functions were called on it. These were what would now be called finalisers. The object would survive at least to the next collection depending on what it did. The finaliser ran on the thread that triggered the garbage collection, and in rare occasions it could cause reentry to the garbage collector.
We define a class named Test.
CL-USER 7 > (defclass test()())
This flags all instances as requiring a special free action.
CL-USER 12 > (defmethod initialize-instance :after ((self test) &rest args)
(flag-special-free-action self))
We define a finaliser for objects of type TEST and compile it.
CL-USER 14 > (defun check-for-test (x) (when (typep x ‘test) (print "a Test instance was gc’ed")))
CL-USER 15 > (compile *)
We add this function to the set of special free actions.
CL-USER 16 > (add-special-free-action ‘CHECK-FOR-TEST)
And test it, by making an instance and doing a garbage collection at which point we see the finaliser printing out a message.
CL-USER 17 > (progn (make-instance ‘test) nil)
CL-USER 18 > (mark-and-sweep 3)
"a Test instance was gc’ed"
CL-USER 19 > (mark-and-sweep 3)

And this time make two instances which get collected.
CL-USER 20 > (progn (make-instance ‘test) nil)
CL-USER 21 > (progn (make-instance ‘test) nil)
CL-USER 22 > (mark-and-sweep 3)
"a Test instance was gc’ed"
"a Test instance was gc’ed"
To demonstrate the use of a gate we need some objects that contain pointers to the gate itself. We will use two cons cells that we will maintain references to.
CL-USER 1 > (defvar *a* (cons 1 1))
CL-USER 2 > (defvar *b* (cons 2 2))
We make an instance of a gate, with target an instance of the class TEST (which prints a message when it is collected).
CL-USER 12 > (defvar *gate* (sys::make-gate (make-instance ‘test) *a* *b*))
We put pointers into the two cons cells to point them at the gate.
CL-USER 13 > (progn (setf (car *a*) *gate* (car *b*) *gate*) nil)
We can now get rid of the reference from the variable to the gate (otherwise this will keep it fully alive and the target will not be collected).
CL-USER 14 > (setq *gate* nil)
Garbage collecting now will keep the instance of TEST alive as both *a* and *b* are kept alive by the system and these two variables reference the two cons cells that hold the incoming pointers into the gate.
CL-USER 15 > (mark-and-sweep 3)
Now, we release a hold on the first cons cell.
CL-USER 16 > (setq *a* nil)
This was the only reference to the first cons cell which can now be freed. Because only a single incoming pointer to the gate is now marked, it releases its target object.
CL-USER 17 > (mark-and-sweep 3)
"a Test instance was gc’ed"
CL-USER 18 > (type-of (car *b*))
CL-USER 19 > (sys::gate-target (car *b*))
This allowed us to use the standard garbage collector to do the collecting of generic function methods which could be shaken away if the classes on which they specialised were shaken.
This entry was posted in Computers and Internet. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )


Connecting to %s