During the course of a computation, contents of cells which were taken from free space list often becomes unnecessary. They are garbage. In general it is difficult to know exactly which cells are garbage. The responsibility for reclamation is therefore undertaken by the LISP system itself. The fundamen tal assumption of garbage collection is
at any point in a LISP computation, all cells which contain parts of the computation are reachable from a fixed set of known cells or registers.Garbage collection consist of two phases: mark and sweep. The first phase of the garbage collector, called the marking phase, marks all of the LISP data structure which is currently active. By definition, a cell (any LISP data object) is active if it is reachable from the registers, stack, or identifier table. An identifier which is not reachable in this way may still be active if it has a non-NULL value or a non-NIL proplist.
In terms of our implementation, we mark from the registers, from the identifier list (its values and properties), from the SEXPR stack, from the urwelt ar ray and from the ALIST stack. During the mark phase each cell which is active is marked (by using putmark macro) by marking its type field. The following macros (file type.l) are used in marking and sweep phases:
#define putmark(x) (type(x) := 0x80) #define clrmark(x) (type(x) &= 0x7f) #define marked(x) (type(x) & 0x80) #define gtype(x) (type(x) & 0x7f)
A structure might be referenced several times in the marking process, since we allow multiple reference to structure. We must take this into account since, though naive marking of an already marked structure is at wasteful, it is fatal if the structure is self-referential. Marking of structures are done by zmark (file lisp-zfn.l). Once all active structure has been marked, any unmarked cell can be treated as garbage and may be returned to the free storage for reuse. This is done during sweep, the second phase of the garbage collection.
The sweep phase proceeds linearly through pages, collecting all those cells which have not been marked. These unmarked cells are chained together and free pointer of the page is set to this chain. At this stage, unmarking of the marked cells are done also (by zcollect). If all the cells in some page are unmarked then this page is removed from the linked list of pages of a specific type and chained to the freepages list.
There are five garbage collection functions in the file lisp-zfn.l and are described below.
since we are assured that any cells further down the structure have already been marked. If object is a vector, it marks the vector itself and all objects to which the entries in the vector point. If it is a dotted pair, it simply marks all the cells pointed by the car and cdr pointers. Any other object is assumed to be elementary (i.e., contains one cell only) and is marked by marking its cell. An identifiers is marked only if it is in a dynamically allocated page. Compile time identifiers are allocated separately in static locations and therefore they are not marked.