Weak Boxes

Luke Tierney
1999/10/28

Introduction

This report describes the interface and implementation of weak references added to XLISP-STAT starting with Release 3.52.14. Weak references allow a reference to an item to be held that does not protect the item from garbage collection. While other strong references to the object are available, the weak reference object contains a reference to the item that can be retrieved. Once no strong references exist and the item has been garbage-collected, the reference value in the weak reference item is set to nil.

One of the uses of weak references is to manage Lisp items that represent operating system resources. It is often useful to allow the internal representation of the resource to have a reference to the Lisp item representing the resource, but using a standard strong reference would prevent garbage collection of the Lisp representation even if it is not reachable from the Lisp side. Just saving the address of the Lisp pointer without registering it for GC-protection would avoid this problem but would then result in a dangling pointer since the internal representation has no way of knowing whether the pointer is valid or not. By using a weak reference, the internal representation can access the Lisp representation while it is still available, but will see nil as the reference once the representation has been garbage-collected.

Interface

The interface consists of two functions. The constructor function make-weak-box takes one argument, the reference item, and returns a new weak box. The accessor function weak-box-value takes a weak box and returns the contents of its reference cell, either the item passed to the constructor or nil if the item has been garbage collected.

These two functions should be accessed as exported functions in the system package.

Examples

We can construct two boxes and access their values: 
> (setf b1 (system:make-weak-box (list 1)))
#<Weak Box: #4004e458>
> (setf b2 (system:make-weak-box (list 2)))
#<Weak Box: #4004f608>
> (system:weak-box-value b1)
(1)
> (system:weak-box-value b2)
(2)

Next, save the value in b2 in x, thus establishing a strong reference, clear the history variables, and do a gc. Then b1's weak reference has been cleared, but because of the strong reference to the contents of b2 through x, b2's reference has not been cleared. 

> (setf x (system:weak-box-value b2))
(2)
> (setf * nil ** nil *** nil)
NIL
(2)
> (gc)
NIL
> (system:weak-box-value b1)
NIL
> (system:weak-box-value b2)
(2)

After clearing the history variables and x and running a gc, the contents of b2 has also been cleared: 

> (setf * nil ** nil *** nil x nil)
NIL
> (gc)
NIL
> (system:weak-box-value b2)
NIL

Next, we can again create some weak boxes but this time save them in a workspace. Again the contents of b2 is also assigned to x and the history variables are cleared. 

> (setf b1 (system:make-weak-box (list 1)))
#<Weak Box: #400510a8>
> (setf b2 (system:make-weak-box (list 2)))
#<Weak Box: #4004c0d8>
> (setf x (system:weak-box-value b2))
(2)
> (setf * nil ** nil *** nil)
NIL
> (save-workspace "fred.wks")

A gc is executed prior to creating the saved workspace. Therefore in a new process started from the saved workspace the contents of b1 has been cleared but, because of the strong reference through x, the contents of b2 has not. 

nokomis% xlisp -wfred.wks
XLISP-PLUS version 3.04
Portions Copyright (c) 1988, by David Betz.
Modified by Thomas Almy and others.
XLISP-STAT Release 3.52.13 (Beta).
Copyright (c) 1989-1999, by Luke Tierney.

> b1
#<Weak Box: #400510a0>
> b2
#<Weak Box: #4004c0d0>
> x
(2)
> (weak-box-value b1)
NIL
> (weak-box-value b2)
(2)

Implementation

Weak boxes are implemented as CONS cells. Their car contains the referenced item, and their cdr is used to place them on a list of weak boxes. At the end of a collection the list is processed. Unreachable boxes are removed and reachable boxes with unreachable contents are cleared. To allow weak boxes to be maintained in saved workspaces, the head of the weak box list is written out at the beginning of a save and read in at the beginning of a restore.

The patch file should work against 3.52.13, though I haven't tried it yet to make sure. 

<weakbox.patch>=
<xldmem.h changes>
<xldmem.c changes>
<xlftab.h changes>
<xlftab.c changes>
<xlglob.h changes>
<xlglob.c changes>
<xlimage.c changes>
<xlprin.c changes>
<xlinit.c changes>
<xlsys.c changes>

Changes to xlglob.c and xlglob.h

A global variable xlweakboxes is added to hold the list of weak boxes. It is statically initialized to nil so the GC works during workspace initialization. A global a_weakbox for the type symbol is also added. 

<xlglob.h changes>= (<-U)
Index: xlglob.h
===================================================================
RCS file: /NOKOMIS/users/luke/SRC/xlispstat/xlglob.h,v
retrieving revision 1.19
diff -r1.19 xlglob.h
115a116
> XLGLOBAL LVAL a_weakbox;
206a208,210
> 
> /* Weak box list */
> XLGLOBAL LVAL xlweakboxes;
Defines a_weakbox, xlweakboxes (links are to index).

<xlglob.c changes>= (<-U)
Index: xlglob.c
===================================================================
RCS file: /NOKOMIS/users/luke/SRC/xlispstat/xlglob.c,v
retrieving revision 1.22
diff -r1.22 xlglob.c
144a145
> LVAL a_weakbox=NULL;
195a197,199
> 
> /* Weak box list */
> LVAL xlweakboxes = NIL;
Defines a_weakbox, xlweakboxes (links are to index).

Changes in xldmem.h

A WEAKBOX type is added. To make room for a few more additions, CONS is shifted down to 16, along with the other CONS-like types. 

<xldmem.h changes>= (<-U)
Index: xldmem.h
===================================================================
RCS file: /NOKOMIS/users/luke/SRC/xlispstat/xldmem.h,v
retrieving revision 1.16
diff -r1.16 xldmem.h
265a266
> #define WEAKBOX 13
268,269c269,270
< #define CONS  13
< #define COMPLEX 14
---
> #define CONS  16
> #define COMPLEX 17
271c272
< #define RATIO 15
---
> #define RATIO 18
273,275c274,276
< #define USTREAM 16
< #define DARRAY  17
< #define RNDSTATE 18
---
> #define USTREAM 19
> #define DARRAY  20
> #define RNDSTATE 21
277c278
< #define BCCLOSURE 19
---
> #define BCCLOSURE 22
Defines WEAKBOX (links are to index).

Changes in xlftab.c and xlftab.h

Entries for the weak box constructor and accessor functions are added to the function table. 

<xlftab.c changes>= (<-U)
Index: xlftab.c
===================================================================
RCS file: /NOKOMIS/users/luke/SRC/xlispstat/xlftab.c,v
retrieving revision 1.37
diff -r1.37 xlftab.c
312a313,314
> {   "MAKE-WEAK-BOX",    S, xmkweakbox   },
> {   "WEAK-BOX-VALUE",   S, xweakboxval  },
865,866d866
< {   NULL,               S, xnotimp      },
< {   NULL,               S, xnotimp      },
Defines make-weak-box, weak-box-value (links are to index).

<xlftab.h changes>= (<-U)
Index: xlftab.h
===================================================================
RCS file: /NOKOMIS/users/luke/SRC/xlispstat/xlftab.h,v
retrieving revision 1.32
diff -r1.32 xlftab.h
125c125,126
<     xgc(V),xexpand(V),xalloc(V),xmem(V),xregfinal(V);
---
>     xgc(V),xexpand(V),xalloc(V),xmem(V),xregfinal(V),
>     xmkweakbox(V),xweakboxval(V);
Defines make-weak-box, weak-box-value (links are to index).

Changes to xlimage.c

The current value of the weak box list xlweakboxes is written out and read in at the beginning of the save/restore process. Weak boxes are treated like CONS cells during reading and writing of saved images, i.e. both car and cdr are followed. 

<xlimage.c changes>= (<-U)
Index: xlimage.c
===================================================================
RCS file: /NOKOMIS/users/luke/SRC/xlispstat/xlimage.c,v
retrieving revision 1.22
diff -r1.22 xlimage.c
110a111,113
>     /* write out the weak box list head */
>     writeptr(cvoptr(xlweakboxes));
> 
132a136
>           case WEAKBOX:
321a326,328
>     /* read in the weak box list head */
>     xlweakboxes = cviptr(readptr());
> 
340a348
>       case WEAKBOX:

Changes to xldmem.c

Weak boxes are implemented as CONS cells. Their car contains the referenced item, and their cdr is used to place them on the xlweakboxes list. 

<xmkweakbox definition>= (U->)
> LVAL xmkweakbox(V)
> {
>   LVAL val = xlgetarg();
>   LVAL box = consa(val);
>   xllastarg();
>   ntype(box) = WEAKBOX;
>   Rplacd(box, xlweakboxes);
>   xlweakboxes = box;
>   return box;
> }
Defines xmkweakbox (links are to index).

Right after identifying and forwarding finalizers, weak boxes are processed by traversing the list of weak boxes xlweakboxes. Unreachable boxes are removed, and reachable boxes with unreachable contents are cleared. 

<check_weak_boxes definition>= (U->)
> static void check_weak_boxes()
> {
>   LVAL last = NIL, next = xlweakboxes;
> 
>   while (ntype(next) == WEAKBOX) {
>     if (is_new_node(next)) {
>       /* delete box from weak box list */
>       LVAL tail = cdr(next);
>       if (null(last))
>         xlweakboxes = tail;
>       else
>         Rplacd(last, tail);
>       next = tail;
>     }
>     else {
>       if (is_new_node(car(next)))
>       Rplaca(next, NIL);
>       last = next;
>       next = cdr(next);
>     }
>   }
> }
Defines check_weak_boxes (links are to index).

In forwarding, weak boxes are treated as non-allocated with no children. In other words, neither their car nor cdr are followed. 

<weak box forwarding information>= (U->)
>     type_info[WEAKBOX].allocated = FALSE;
>     type_info[WEAKBOX].has_children = FALSE;

The marking code for the mark-and-sweep collector should work as is with weak boxes, but I haven't thought it through. However, the post-processing of the weak box list (or the finalization stuff for that matter) is not included in this collector, so it currently won't work with weak boxes or finalization.

The accessor just returns the car value. Two macros are defined here since this is the only place they are used; they should really be in xlisp.h. 

<xweakboxval definition>= (U->)
> #define weakboxp(x) (ntype(x) == WEAKBOX)
> #define xlgaweakbox()    (testarg(typearg(weakboxp)))
> LVAL xweakboxval(V)
> {
>   LVAL box = xlgaweakbox();
>   xllastarg();
>   return car(box);
Defines xweakboxval (links are to index).

Here are the rest of the changes: 

<xldmem.c changes>= (<-U)
Index: xldmem.c
===================================================================
RCS file: /NOKOMIS/users/luke/SRC/xlispstat/xldmem.c,v
retrieving revision 1.32
diff -r1.32 xldmem.c
12a13
> static VOID check_weak_boxes(V);
223a225,226
<weak box forwarding information>
1130a1134
>   check_weak_boxes();
2938a2943,2965
<check_weak_boxes definition>
> 
2946a2974,2993
> }
> 
<xmkweakbox definition>
> 
<xweakboxval definition>

Changes to xlprin.c

Weak boxes are printed as unreadable objects. It might be nice to add a readable representation so circular printing can do the right thing, but I won't worry about that for now. One possible approach would be to do readable printing as #.(make-weak-box x). 

<xlprin.c changes>= (<-U)
Index: xlprin.c
===================================================================
RCS file: /NOKOMIS/users/luke/SRC/xlispstat/xlprin.c,v
retrieving revision 1.33
diff -r1.33 xlprin.c
562a563,569
>     case WEAKBOX:
> #ifdef PRINTCIRCLE
>           if (checkcircle(fptr, vptr)) break;
> #endif /* PRINTCIRCLE */
>           checkreadable(vptr);
>           putatm(fptr,"Weak Box",vptr);
>           break;

Changes to xlinit.c

The type symbol a_weakbox is initialized in xlinit.c. 

<xlinit.c changes>= (<-U)
Index: xlinit.c
===================================================================
RCS file: /NOKOMIS/users/luke/SRC/xlispstat/xlinit.c,v
retrieving revision 1.33
diff -r1.33 xlinit.c
555a556
>     a_weakbox    = xlenter("SYSTEM:WEAK-BOX");

Changes to xlsys.c

The internal type-of and typep functions have handlers for the weak box type added to them. 

<xlsys.c changes>= (<-U)
Index: xlsys.c
===================================================================
RCS file: /NOKOMIS/users/luke/SRC/xlispstat/xlsys.c,v
retrieving revision 1.24
diff -r1.24 xlsys.c
131a132
>     case WEAKBOX:     return (a_weakbox);
175a177
>   if (arg == a_weakbox)   return WEAKBOX;

Code Chunks

Identifiers