Memory Management

page is the main storage unit of this LISP implementation. LISP data items (SEXPR) are hold in linked memory pages each of which are of a constant size. This size PAGESIZE is a multiple of the least-common-factor of the sizes of possible data structures (sizes of which are stored in the sz array) that corresponds to a LISP object. Pages are allocated dynamically from the system memory by using malloc.

 
Figure 4.1: Typical page organization.

Each page is a structure of three elements (defined in type.l):

     struct page { struct page *nextpage;
                   char *free;
   char pagebd[PAGESIZE]; } ;

     typedef struct page PAGE, *PPAGE;

where

nextpage

Pointer to the next page of the same page type.

free

Free cell pointer of the link list of the free cells of the page.

pagebd

Space for LISP data types (SEXPR).

PAGESIZE

Size of the page.

PAGE

Page structure type.

PPAGE

Pointer type to a page structure type.

Following variables are also used in memory management:

PPAGE pages[NTYPES], cpages[NTYPES];
PPAGE freepages;

unsigned sz[NTYPES] = { sizeof(PAIR),
                        sizeof(ID),
                        sizeof(STRING),
                        sizeof(INTEGER),
                        sizeof(BIG),
                        sizeof(FLOATING),
                        sizeof(VECTOR) };

NTYPES

Number of dynamically generated cell types (macro). It is 7 in this implementation.

pages

Array of pointers to the first pages of different types. Used by garbage collection.

cpages

Array of pointers to the active pages of different types. Allocation of new items are done from these active pages.

sz

Array which contains the sizes of cells.

freepages

Pointer to a page. It points to the first page of the link list of completely empty pages. These pages are generated and linked by the garbage collector if all the cells in page are unbounded cells. Free pages are untyped pages.

 
Figure 4.2: Item allocation algorithm of type `tp' (roughly).

Allocation of LISP data items are done by two functions, zalloc and zgetpage in file lisp-zfn.l:

zgetpage:

PPAGE zgetpage(unsigned tp);
zgetpage is the function for allocating page of given type tp. Each time it is called it returns a pointer to an empty page which contains the linked list of PAGESIZE/sz[tp] number of free cells of type tp.

Linking is done by zgetpage and first free cell address is put into free pointer of the page. nextpage pointer of the page is always set to NULL. zgetpage returns a page from the free pages list, if there are any pages available (freepages non-NULL). Otherwise it allocates new page from the system sources if possible and otherwise it returns NULL.

zalloc:

PSEXP zalloc(unsigned tp);
zalloc is the lowest-level function for allocating cell of given type tp. Each time it is called it returns a pointer to a fresh cell. It returns a fresh cell, if there are any cells available on active page (free pointer of page non-NULL). Otherwise, it attempts to allocate a new page by calling zgetpage and if zgetpage returns a non-NULL pointer to a fresh page it returns the first cell in that page else it performs garbage collection which constructs linked lists of reusable cells for each type.

Other allocation functions are zcalloc and zsalloc:

zcalloc:

PCHAR zcalloc(unsigned n);
Performs space allocation for identifier print name of size `n' characters from print name space. Returns pointer to the allocated space.

zsalloc:

PCHAR zsalloc(unsigned n);
Allocates space in string space for a string of `n' character long.