{Begin SubSec Storage Allocation and Garbage Collection}
{Title Storage Allocation and Garbage Collection}
{Text

{index garbage collection}
{index storage allocation}


In the following discussion, we will speak of a quantity of memory being assigned to a particular data-type, meaning that the space is reserved for storage of elements of that type.  {it Allocation} will refer to the process used to obtain from the already assigned storage a particular location for storing one data element.

A small amount of storage is assigned to each data-type when Interlisp-10 is started; additional storage is assigned only during a garbage collection.

The page{index page} is the smallest unit of memory that may be assigned for use by a particular data-type.  For each page of memory there is a one word entry in a type table.  The entry contains the data-type residing on the page as well as other information about the page.  The type of a pointer is determined by examining the appropriate entry in the type table.

Storage is allocated as is needed by the functions which create new data elements, such as {fn CONS}, {fn PACK}, {fn MKSTRING}.
For example, when a large integer is created by {fn IPLUS}, the integer is stored in the next available location in the space assigned to integers.
If there is no available location, a garbage collection is initiated, which may result in more storage being assigned.

The storage allocation{index storage allocation} and garbage collection methods differ for the various data-types.  The major distinction is between the types with elements of fixed length and the types with elements of arbitrary length.
List cells, atoms, large integers, floating point numbers, and string pointers are fixed length; all occupy 1 word except atoms which use 3 words.
Arrays, print names, and strings (string characters) are variable length.

Elements of fixed length types are stored so that they do not overlap page boundaries.  Thus the pages assigned to a fixed length type need not be adjacent.
If more space is needed, any empty page will be used.
The method of {it allocating} storage for these types employs a free-list of available locations; that is, each available location contains a pointer to the next available location. A new element is stored at the first location on the free-list, and the free-list pointer is updated.{foot
The allocation routine for list cells is more complicated.  Each page containing list cells has a separate free list.  First a page is chosen, then the free list for that page is used.  Lists are the only data-type which operate this way.
}{comment endfootnote}

Elements of variable length data-types {it are} allowed to overlap page boundaries.  Consequently all pages assigned to a particular variable length type must be contiguous.  Space for a new element is allocated following the last space used in the assigned block of contiguous storage.

When Interlisp-10 is first called, a few pages of memory are assigned to each data-type.  When the allocation routine for a type determines that no more space is available in the assigned storage for that type, a garbage collection is initiated.  The garbage collector determines what data is currently in use and reclaims that which is no longer in use.  A garbage collection may also be initiated by the user with the function {fn RECLAIM}{index RECLAIM FN}.

Data in use (also called active data) is any data that can be "reached" from the currently running
program (i.e., variable bindings and functions in execution) or from atoms.
To find the active data the garbage collector "chases" all pointers, beginning with the contents of the push-down lists and the components (i.e., {fn CAR}, {fn CDR}, and function definition cell) of all atoms with at least one non-trivial component.

When a previously unmarked datum is encountered, it is marked, and all pointers contained in it are chased.  Most data-types are marked using bit tables; that is tables containing one bit for each datum.  Arrays, however, are marked using a half-word in the array header.

When the mark and chase process is completed, unmarked (and therefore unused) space is reclaimed.  Elements of fixed length types that are no longer active are reclaimed by adding their locations to the free-list for that type.
This free list allocation method permits reclaiming space without moving any data, thereby avoiding the time consuming process of updating all pointers to moved data.  To reclaim unused space in a block of storage assigned to a variable length type, the active elements are compacted toward the beginning of the storage block, and then a scan of all active data that can contain pointers to the moved data is performed to update the pointers.{foot
If Interlisp-10 types the message {index ARRAYS FOULED Error}{lisp ARRAYS FOULED} during a garbage collection, it means that an array header has been clobbered and no longer makes sense.  This can be due to hardware malfunction, or an as yet undiscovered bug in Interlisp.  The best thing to do under these circumstances is to give up and start over with a fresh system or sysout.
}{comment endfootnote}

Whenever a garbage collection of any type is initiated,{foot
The "type of a garbage collection" or the "type that initiated a garbage collection" means either the type that ran out of space and called the garbage collector, or the argument to {index RECLAIM FN}{fn RECLAIM}.
}{comment endfootnote}
unused space for all fixed length types is reclaimed since the additional cost is slight.  However, space for a variable length type is reclaimed only when that type initiated the garbage collection.

If the amount of storage reclaimed for the type that initiated the garbage collection is less than the minimum free storage requirement for that type, the garbage collector will assign enough additional storage to satisfy the minimum free storage requirement.  The minimum free storage requirement for each data may be set with the function {index MINFS FN}{fn MINFS}.  The garbage collector assigns additional storage to fixed length types by finding empty pages, and adding the appropriate size elements from each page to the free list.
Assigning additional storage to a variable length type involves finding empty pages and moving data so that the empty pages are at the end of the block of storage assigned to that type.

In addition to increasing the storage assigned to the type initiating a garbage collection, the garbage collector will attempt to minimize garbage collections by assigning more storage to other fixed length types according to the following algorithm.  If the amount of active data of a type has increased since the last garbage collection by more than 1/4 of the {fn MINFS}{index MINFS FN} value for that type, storage is increased (if necessary), to attain the {fn MINFS} value.
If active data has increased by less than 1/4 of the {fn MINFS} value, available storage is increased to 1/2 {fn MINFS}.  If there has been no increase, no more storage is added.  For example, if the {index MINFS FN}{fn MINFS} setting is 2000 words, the number of active words has increased by 700, and after all unused words have been collected there are 1000 words available, 1024 additional words (two pages) will be assigned to bring the total to 2024 words available.
If the number of active words had increased by only 300, and there were 500 words available, 512 additional words would be assigned.





{FnDef {FnName RECLAIM} {FnArgs TYPE}
{Text
Initiates a garbage collection of type {arg TYPE}, where {arg TYPE} is either a type name or type number. Value of {fn RECLAIM} is number of words available (for that type) after the collection.
}}


{it
Garbage collections, whether invoked directly by the user or indirectly
by need for storage, do not confine their activity solely to the data type for which they were called, but automatically collect some or all of the other types.
}


{FnDef {FnName GCGAG} {FnArgs MESSAGE}
{Text
Affects messages printed by the garbage collector.  If {arg MESSAGE}={lisp T}, whenever a garbage collection is begun, {lisp "collecting"}{index collecting (Printed by System)} is printed, followed by the type description of the type that initiated the collection.{foot
Note that this type description can be set via the function {fn SETTYPEDESCRIPTION} ({PageRef Fn SETTYPEDESCRIPTION}).
}{comment endfootnote}
When the garbage collection is complete, two numbers are printed:  the number of words collected for that type, and the total number of words available for that type, i.e., allocated but not necessarily currently in use.  Note that other types may also have been collected, and had more storage assigned.

Example:

{lispcode
←RECLAIM(18)

collecting large numbers
511, 3071 free cells
3071
←RECLAIM(LITATOM)

collecting atoms
1020, 1020 free cells
1020
}{comment endlispcode}

If {arg MESSAGE}={lisp NIL}, no garbage collection message is printed, either on entering or leaving the garbage collector.

If {arg MESSAGE} is a list, {fn CAR} of {arg MESSAGE} is printed
(using {fn PRIN1}) when the garbage collection is begun, and {fn CDR} is printed (using {fn PRIN1}) when the collection is finished.  If {arg MESSAGE} is a literal atom or string, {arg MESSAGE} is printed when the garbage collection is begun, and nothing is printed when the collection finishes.

If {arg MESSAGE} is a number,
the message is the same as for {lisp (GCGAG T)}, except if the total number of free pages left after the collection is less than {arg MESSAGE}, the number of free pages is printed, e.g.,

{lispcode
←GCGAG(100)
T
←RECLAIM()

collecting lists
10369, 10369 free cells, 87 pages left.
}{comment endlispcode}

The initial setting for {fn GCGAG} is 40.

The value of {fn GCGAG} is its previous setting.
}}


{FnDef {FnName GCMESS} {FnArgs MESSAGE# STRING}
{Text
{fn GCGAG} is implemented in terms of the primitive {fn GCMESS} which can be used to further refine garbage collection messages for specialized applications.  The garbage collection message is actually composed of seven separate messages:

{lispcode
collecting large numbers{super 1} {super 2}
511,{super 3} 3071 free cells{super 4}, 87{super 5} pages{super 6} left{super 7}
}{comment endlispcode}

message #1 is the "collecting" string.  If {lisp NIL}, then neither it, nor the type dependent field (which is settable via {fn SETTYPEDESCRIPTION} described below) is printed.

message #2 is the carriage-return after the type-dependent field.  Thus to simply print a string at the beginning of a garbage collection,
perform {lisp (GCMESS 1)} and {lisp (GCMESS 2 {arg STRING})}.

message #3 is the "{lisp ,}" which comes after the number of cells actually collected.  If {lisp NIL}, then neither it nor that number are printed.

message #4 is the "{lisp free cells}" which comes after the number of cells that are now allocated.  If {lisp NIL}, neither it nor that number are printed.

message #5 is the number of pages left below which the system prints message 6.

message #6 is the "{lisp pages left}" message.  If {lisp NIL}, neither it nor the number of pages left are printed.

message #7 is the terminating carriage return.
}}


{FnDef {FnName MINFS} {FnArgs N TYPE}
{Text
Sets the minimum amount of free storage which will be
maintained by the garbage collector for data types of
type number or type name {arg TYPE}.
If, after any garbage collection for that type, fewer than {arg N} free words are present, sufficient storage will be added (in 512 word chunks) to raise the level to {arg N}.

If {arg TYPE}={lisp NIL}, {lisp LISTP} is used, i.e., the {fn MINFS}
refers to list words.

If {arg N}={lisp NIL}, {fn MINFS} returns the current {fn MINFS} setting
for the corresponding type.
}}


A {index MINFS FN}{fn MINFS} setting can also be changed dynamically, even during a garbage collection, by typing {index control-S}control-S{foot
{index control-X (TOPS-20) Term}control-X for Interlisp-10 on TOPS-20.
}{comment endfootnote}
followed by a number, followed by a period.  When the {index control-S}control-S is typed, Interlisp immediately clears and saves the input buffer,{index input buffer} rings the {index bell (Printed by System)}bell, and waits for input, which is terminated by any non-number.  The input buffer is then restored, and the program continues.  If the input was terminated by other than a period, it is ignored.  If the control-S was typed during a garbage collection, the number is the new {fn MINFS} setting for the type being collected, otherwise for type 8, i.e., list words.



{FnDef {FnName MINHASH} {FnArgs X}
{Text
The atom hash table{index atom hash table} automatically expands by a specified number of pages each time it fills up.  The number of pages is set via the function {fn MINHASH}.  The initial setting is {lisp (MINHASH 2)} (room for 1024 new atoms).
}}


{FnDef {FnName GCTRP} {FnArgs N}
{Text
"Garbage Collection Trap".  Causes a (simulated) {index control-H}control-H interrupt when the number of free list words remaining equals {arg N}, i.e., when a garbage collection would occur in {arg N} more conses.  The message {index GCTRP (Printed by System)}{lisp GCTRP} is printed, the function {index INTERRUPT FN}{fn INTERRUPT} is called, and a break occurs.  Note that by advising {index INTERRUPT FN}{fn INTERRUPT} the user can program the handling of a {fn GCTRP} instead of going into a break.{foot 
For {fn GCTRP} interrupts, {index INTERRUPT FN}{fn INTERRUPT} is called with {arg INTYPE} (its third argument) equal to 3.  If the user does not want to go into a break, the advice should still allow {fn INTERRUPT} to be entered, but first set {arg INTYPE} to -1.  This will cause {fn INTERRUPT} to "quietly" go away by calling the function that was interrupted.  The advice should {it not} exit {fn INTERRUPT} via {fn RETURN}, as in this case the function that was about to be called when the interrupt occurred would not be called.
}{comment endfootnote}

{fn GCTRP} returns its last setting.

{lisp (GCTRP -1)} will "disable" a previous {fn GCTRP} since there are never -1 free list words.  {fn GCTRP} is initialized this way.

{lisp (GCTRP)} returns the number of list cells left, i.e., number of {fn CONS}es until next type {lisp LISTP} garbage collection.
}}



{FnDef {FnName CLOSER} {FnArgs A X}
{Text
Stores {arg X} into memory location {arg A}.  Both {arg X} and {arg A} must be numbers.
}}


{FnDef {FnName OPENR} {FnArgs A}
{Text
Returns the number in memory location {arg A}, i.e., boxed.
}}



{index *END* *PRIMARY* garbage collection}


}{End SubSec Storage Allocation and Garbage Collection}