--- a +++ b/gc.xmlf @@ -0,0 +1,564 @@ +<?xml version="1.0"?><!DOCTYPE book PUBLIC "-//OASIS//DTD DocBook XML V4.4//EN" "http://www.oasis-open.org/docbook/xml/4.4/docbookx.dtd"> +<book lang="en"> + <chapter id="Memory-management"> + <title>Memory Management</title> + <para>The following sections only apply to the &ECL; original garbage collector. + If &ECL; is not compiled with <literal>--disable-boehm</literal>, then an alternative, + less restrictive garbage collector is installed, with the disadvantage + that many of the following functions <literal>#'room</literal>, <literal>si:*gc-verbose*</literal>, + … do no longer work.</para> + + <section id="Implementation-types"> + <title>Implementation Types</title> + <para>Each &ECL; object belongs to one of the 22 <emphasis>implementation types</emphasis>. The + implementation types are shown in Table 4-1 with the corresponding Common-Lisp + data types. In the table, the compiled functions are divided into three + implementation types; <literal>cfun</literal> is the type of compiled functions without + environment, <literal>cclosure</literal> is the type of compiled functions with environment + (i.e., the type of compiled closures) and <literal>gfun</literal> is the type of compiled + generic functions of CLOS.</para> + <para>Table 4-1 Implementation Types</para> + <informaltable> + <tgroup cols="2"> + <colspec colwidth="42*"></colspec> + <colspec colwidth="77*"></colspec> + <tbody> + <row> + <entry><emphasis role="bold"><emphasis>Implementation Type</emphasis></emphasis></entry> + <entry><emphasis role="bold"><emphasis>Common-Lisp Data Type</emphasis></emphasis></entry> + </row> + <row> + <entry><literal>cons</literal></entry> + <entry><literal>cons</literal></entry> + </row> + <row> + <entry><literal>fixnum</literal></entry> + <entry><literal>fixnum</literal></entry> + </row> + <row> + <entry><literal>bignum</literal></entry> + <entry><literal>bignum</literal></entry> + </row> + <row> + <entry><literal>ratio</literal></entry> + <entry><literal>ratio</literal></entry> + </row> + <row> + <entry><literal>short-float</literal></entry> + <entry><literal>short-float</literal></entry> + </row> + <row> + <entry><literal>long-float</literal></entry> + <entry><literal>long-float (= double-float = single-float)</literal></entry> + </row> + <row> + <entry><literal>complex</literal></entry> + <entry><literal>complex</literal></entry> + </row> + <row> + <entry><literal>character</literal></entry> + <entry><literal>character</literal></entry> + </row> + <row> + <entry><literal>symbol</literal></entry> + <entry><literal>symbol</literal></entry> + </row> + <row> + <entry><literal>package</literal></entry> + <entry><literal>package</literal></entry> + </row> + <row> + <entry><literal>hash-table</literal></entry> + <entry><literal>hash-table</literal></entry> + </row> + <row> + <entry><literal>array</literal></entry> + <entry><literal>(and array (not vector))</literal></entry> + </row> + <row> + <entry><literal>vector</literal></entry> + <entry><literal>(and vector (not string) (not bit-vector))</literal></entry> + </row> + <row> + <entry><literal>string</literal></entry> + <entry><literal>string</literal></entry> + </row> + <row> + <entry><literal>bit-vector</literal></entry> + <entry><literal>bit-vector</literal></entry> + </row> + <row> + <entry><literal>structure</literal></entry> + <entry><literal>structure</literal></entry> + </row> + <row> + <entry><literal>stream</literal></entry> + <entry><literal>stream</literal></entry> + </row> + <row> + <entry><literal>random-state</literal></entry> + <entry><literal>random-state</literal></entry> + </row> + <row> + <entry><literal>readtable</literal></entry> + <entry><literal>readtable</literal></entry> + </row> + <row> + <entry><literal>cfun</literal></entry> + <entry><literal>compiled-function without environment</literal></entry> + </row> + <row> + <entry><literal>cclosure</literal></entry> + <entry><literal>compiled-function with environment</literal></entry> + </row> + <row> + <entry><literal>gfun</literal></entry> + <entry><literal>none (CLOS generic-function)</literal></entry> + </row> + <row> + <entry><literal>instance</literal></entry> + <entry><literal>none (CLOS instance)</literal></entry> + </row> + <row> + <entry><literal>thread</literal></entry> + <entry><literal>none (thread)</literal></entry> + </row> + <row> + <entry></entry> + </row> + </tbody> + </tgroup> + </informaltable> + <para>Each object is represented by a cell allocated in the heap area of the + interpreter. The size of the cell is determined by the implementation type of + the object.</para> + <para>The implementation types are classified according to the size of the cells for + the objects of the type, as shown in Table 4-2. The size of the cells in the + same type class is the same.</para> + <para>Table 4-2 Classification of Implementation Types</para> + <informaltable> + <tgroup cols="2"> + <colspec colwidth="28*"></colspec> + <colspec colwidth="43*"></colspec> + <tbody> + <row> + <entry>1</entry> + <entry><literal>CONS BIGNUM RATIO COMPLEX STRUCTURE</literal></entry> + </row> + <row> + <entry>2</entry> + <entry><literal>SHORT-FLOAT RANDOM-STATE READTABLE</literal></entry> + </row> + <row> + <entry>3</entry> + <entry><literal>LONG-FLOAT CFUN CCLOSURE</literal></entry> + </row> + <row> + <entry>4</entry> + <entry><literal>SYMBOL</literal></entry> + </row> + <row> + <entry>5</entry> + <entry><literal>PACKAGE</literal></entry> + </row> + <row> + <entry>6</entry> + <entry><literal>ARRAY HASH-TABLE VECTOR BIT-VECTOR STREAM</literal></entry> + </row> + <row> + <entry>7</entry> + <entry><literal>STRING</literal></entry> + </row> + <row> + <entry>8</entry> + <entry><literal>PATHNAME</literal></entry> + </row> + </tbody> + </tgroup> + </informaltable> + <para>For objects of the (implementation) types <literal>readtable</literal>, <literal>symbol</literal>, + <literal>package</literal>, <literal>array</literal>, <literal>hash-table</literal>, <literal>vector</literal>, + <literal>bit-vector</literal>, <literal>stream</literal>, <literal>cclosure</literal>, <literal>string</literal>, <literal>cfun</literal>, + and <literal>structure</literal> (or <literal>instance</literal>), the cell is simply a header of the + object. The body of the object is allocated separately from the cell and is + managed in a different manner. The memory space occupied by the body of such + an object is called a <firstterm>block</firstterm>. A block is either <firstterm>contiguous</firstterm> or + <firstterm>relocatable</firstterm> depending on the area in which it is allocated. The + difference between the two areas will be explained below. Table 4-3 lists + these types, along with the contents of the body and the kind of the block.</para> + <para>Table 4-3 Types with Bodies</para> + <informaltable> + <tgroup cols="3"> + <colspec colwidth="27*"></colspec> + <colspec colwidth="27*"></colspec> + <colspec colwidth="28*"></colspec> + <tbody> + <row> + <entry><literal>readtable</literal></entry> + <entry><literal>read table</literal></entry> + <entry><literal>contiguous</literal></entry> + </row> + <row> + <entry><literal>symbol</literal></entry> + <entry><literal>symbol name</literal></entry> + <entry><literal>relocatable</literal></entry> + </row> + <row> + <entry><literal>package</literal></entry> + <entry><literal>hash table</literal></entry> + <entry><literal>contiguous</literal></entry> + </row> + <row> + <entry><literal>array</literal></entry> + <entry><literal>array body</literal></entry> + <entry><literal>relocatable or contiguous</literal></entry> + </row> + <row> + <entry><literal>hash-table</literal></entry> + <entry><literal>hash table</literal></entry> + <entry><literal>relocatable</literal></entry> + </row> + <row> + <entry><literal>vector</literal></entry> + <entry><literal>vector body</literal></entry> + <entry><literal>relocatable or contiguous</literal></entry> + </row> + <row> + <entry><literal>bit-vector</literal></entry> + <entry><literal>bit-vector body</literal></entry> + <entry><literal>relocatable or contiguous</literal></entry> + </row> + <row> + <entry><literal>stream</literal></entry> + <entry><literal>I/O buffer</literal></entry> + <entry><literal>contiguous</literal></entry> + </row> + <row> + <entry><literal>cclosure</literal></entry> + <entry><literal>code</literal></entry> + <entry><literal>contiguous</literal></entry> + </row> + <row> + <entry><literal>string</literal></entry> + <entry><literal>string body</literal></entry> + <entry><literal>relocatable or contiguous</literal></entry> + </row> + <row> + <entry><literal>cfun</literal></entry> + <entry><literal>code</literal></entry> + <entry><literal>contiguous</literal></entry> + </row> + <row> + <entry><literal>structure</literal></entry> + <entry><literal>structure body</literal></entry> + <entry><literal>relocatable</literal></entry> + </row> + <row> + <entry><literal>instance</literal></entry> + <entry><literal>instance slots</literal></entry> + <entry><literal>relocatable</literal></entry> + </row> + <row> + <entry><literal>thread</literal></entry> + <entry><literal>thread data</literal></entry> + <entry><literal>contiguous</literal></entry> + </row> + </tbody> + </tgroup> + </informaltable> + <para>Usually, the body of an array, a vector, a bit-vector, or a string is allocated + as a relocatable block. In &ECL;, the function <literal>make-array</literal> takes an + extra keyword argument <replaceable>:static</replaceable>. If the <replaceable>:static</replaceable> argument is supplied + with a non-() value, then the body of the array is allocated as a + contiguous block.</para> + </section> + + <section id="Heap-and-relocatable-areas"> + <title>Heap and Relocatable Areas</title> + <para>The memory space of &ECL; is divided into two parts: the heap area and the + relocatable area. Both areas occupy a contiguous space in the memory.</para> + <para>Cells of &ECL; objects are allocated in the heap. &ECL; divides the heap + into pages (1 page = 2048 bytes), and each page consists of cells in the same + type class (see Table 4-2). Cells in different type classes are allocated in + different pages. Some blocks are also allocated in the heap: They are called + contiguous blocks. The pages for contiguous blocks contain only contiguous + blocks. Thus each page in the heap is either a page for cells in a particular + type class, or a page for contiguous blocks. Blocks not in the heap are called + relocatable blocks and are allocated in the relocatable area.</para> + <para>The user may specify the maximum number of pages that can be allocated for each + type class by calling the &ECL; specific function <literal>allocate</literal>. There is + also a limit on the number of pages for contiguous blocks; the limit can be + altered by calling the &ECL; specific function + <literal>allocate-contiguous-pages</literal> size of the relocatable area is specified by + the &ECL; specific function <literal>allocate-relocatable-pages</literal>. See Section + 4.4 for these functions.</para> + <para>In some installations of &ECL;, the total amount of memory that &ECL; can + use is limited. In such cases, the entire memory may become exhausted before + the maximum number of pages for each type class, for contiguous blocks, or for + the relocatable area have been allocated.</para> + <para>The heap lies in a part of memory with lower address than the relocatable area + and there is a “hole” between the two areas (see Figure 4-1). On request for + a new page of heap, the page with the lowest address in the hole is used. When + the hole is exhausted, the relocatable area is shifted toward the higher + address space and a new hole of an appropriate size is created between the two + areas.</para> + <para>Figure 4-1 Heap and Relocatable Area</para> + <screen><![CDATA[ + Lower address Higher address + +--------------+-------------------+---------------+ + + HEAP | HOLE | RELOCATABLE | + +--------------+-------------------+---------------+ + ]]></screen> + </section> + + <section id="The-garbage-collector"> + <title>The Garbage Collector</title> + <para>&ECL; uses a <emphasis>conservative garbage collection</emphasis> technique for collecting + the C stack and a type accurate technique for areas containing Lisp objects. + Scanning conservatively the C stack, looking for potential pointers to Lisp + objects, ensures that no live Lisp objects get collected, even if they are + passed to external procedures in C or some other language. This approach + greatly simplifies integration of Lisp and C code, since it is not necessary to + protect Lisp object form collection when a foreign function is invoked.</para> + <para>The garbage collector of &ECL; has three levels according to what it + collects:</para> + <orderedlist numeration="arabic"> + <listitem> + <para>cells</para> + </listitem> + <listitem> + <para>cells and relocatable blocks</para> + </listitem> + <listitem> + <para>cells, relocatable blocks and contiguous blocks.</para> + </listitem> + </orderedlist> + <para>In levels 2 and 3, the relocatable area is shifted to the higher address space + to reserve an appropriate number of pages in the hole.</para> + <para>For each type class, &ECL; keeps a free list of unused cells, and when the + free list is exhausted, a new page is allocated, or the garbage collector is + invoked, depending on whether the maximum number of pages for that class have + been allocated or not.</para> + <para>The garbage collector does not compact the heap. That is, cells and + contiguous blocks are never moved to another place. Moreover, once a page is + allocated for a particular type class or for contiguous blocks, that page will + never be freed for other classes, even if the entire page becomes garbage.</para> + <para>On the other hand, the relocatable area is compacted during level 2 and + level 3 of garbage collection. A relocatable block is really relocatable.</para> + <para>The garbage collector is automatically invoked in one of the following + situations. The number in the parentheses indicates the level of garbage + collection that is performed.</para> + <orderedlist numeration="arabic"> + <listitem> + <para>The free list of a certain type class is exhausted + after the maximum number of pages have been allocated for that type class (1).</para> + </listitem> + <listitem> + <para>The hole is exhausted (2).</para> + </listitem> + <listitem> + <para>The relocatable area is exhausted after the maximum number of + pages have been allocated for the relocatable area (2).</para> + </listitem> + <listitem> + <para>The contiguous blocks are exhausted after the maximum number of + pages have been allocated for contiguous blocks (3).</para> + </listitem> + </orderedlist> + <para>The garbage collector is also invoked by the following &ECL; specific + function.</para> + <blockquote> + <screen><indexterm role="fn"><primary>system</primary></indexterm>— Function: <function>system</function> <varname>gc</varname> <varname>x</varname></screen> + <para>The garbage collector is invoked with the level specified by <replaceable>x</replaceable>. If + <replaceable>x</replaceable> is (), the garbage collector is invoked for level 1 garbage + collection. If <replaceable>x</replaceable> is <replaceable>T</replaceable>, it is invoked for level 3 garbage + collection. Otherwise, it is invoked for level 2 garbage collection. If + <literal>sys:*gc-verbose*</literal> is non-(), then it print messages at the start and + end of each garbage collection.</para> + </blockquote> + <blockquote> + <screen><indexterm role="vr"><primary>*gc-verbose*</primary></indexterm>— Variable: <varname>*gc-verbose*</varname>[<type>system</type>] <type>This</type> <varname>variable</varname> <type>controls</type> <varname>whether</varname> <type>to</type> <varname>print</varname> <type>messages</type></screen> + <para>at the start and end of each garbage collection. If <literal>sys:*gc-verbose*</literal> is + (), <literal>gc</literal> fore goes printing any messages. The default value is <literal>T</literal>.</para> + </blockquote> + </section> + + <section id="Allocation-functions"> + <title>Allocation Functions</title> + <para>The following functions are used to set or inspect the (maximum) + number of pages for each type class, for contiguous blocks, or for + relocatable blocks.</para> + <blockquote> + <screen><indexterm role="fn"><primary>allocate</primary></indexterm>— extensions: <function>allocate</function> <varname>type</varname> <varname>number</varname></screen> + <para>Sets the maximum number of pages for the type class of the implementation type + <replaceable>type</replaceable> to <replaceable>number</replaceable>. If more than <replaceable>number</replaceable> pages have already been + allocated, an error is signalled.</para> + </blockquote> + <blockquote> + <screen><indexterm role="fn"><primary>allocated-pages</primary></indexterm>— sys: <function>allocated-pages</function> <varname>type</varname></screen> + <para>Returns the number of pages currently allocated for the type class of the + implementation type <replaceable>type</replaceable>.</para> + </blockquote> + <blockquote> + <screen><indexterm role="fn"><primary>maximum-allocatable-pages</primary></indexterm>— sys: <function>maximum-allocatable-pages</function> <varname>type</varname></screen> + <para>Returns the current maximum number of pages for type class of the + implementation type <replaceable>type</replaceable>.</para> + </blockquote> + <blockquote> + <screen><indexterm role="fn"><primary>allocate-contiguous-pages</primary></indexterm>— sys: <function>allocate-contiguous-pages</function> <varname>number</varname></screen> + <para>Sets the maximum number of pages for contiguous blocks to <replaceable>number</replaceable>.</para> + </blockquote> + <blockquote> + <screen><indexterm role="fn"><primary>allocated-contiguous-pages</primary></indexterm>— sys: <function>allocated-contiguous-pages</function></screen> + <para>Returns the number of pages allocated for contiguous blocks.</para> + </blockquote> + <blockquote> + <screen><indexterm role="fn"><primary>maximum-contiguous-pages</primary></indexterm>— sys: <function>maximum-contiguous-pages</function></screen> + <para>Returns the current maximum number of pages for contiguous blocks.</para> + </blockquote> + <blockquote> + <screen><indexterm role="fn"><primary>allocate-relocatable-pages</primary></indexterm>— sys: <function>allocate-relocatable-pages</function> <varname>number</varname></screen> + <para>Sets the maximum number of pages for relocatable blocks to <replaceable>number</replaceable>. The + relocatable area is expanded to <replaceable>number</replaceable> pages immediately. + Therefore,“the current maximum number” and “the number of pages allocated” + have the same meanings for relocatable blocks.</para> + </blockquote> + <blockquote> + <screen><indexterm role="fn"><primary>allocated-relocatable-pages</primary></indexterm>— sys: <function>allocated-relocatable-pages</function></screen> + <para>Returns the number of pages allocated for relocatable blocks.</para> + </blockquote> + <para>If the pages for a particular type class are exhausted after the maximum number + of pages for that class have been allocated, and if there remain no free cells + (actually, if there remain very few cells), &ECL; behaves as directed by the + argument that was initially passed to the &ECL; specific function <literal>(si::ignore-maximum-pages)</literal>. If the + value is (), then &ECL; signals a correctable error and enters the break loop. + The user can reset the maximum number by calling <literal>allocate</literal> and then + continue the execution of the program by typing <replaceable>:r</replaceable>.</para> + <para>Example:</para> + <para><screen> + >(make-list 100000) + + Correctable error: The storage for CONS is exhausted. + Currently, 531 pages are allocated. + Use ALLOCATE to expand the space. + Signalled by MAKE-LIST. + + Broken at FUNCALL. + >>(ALLOCATE 'CONS 1000) + t + + >>:r + + (nil nil nil nil nil nil nil nil nil nil ............ + </screen></para> + <para>The user can also reset the maximum number of pages for relocatable blocks and + for contiguous blocks in a similar manner. On the other hand, if the value of + <literal>(si::ignore-maximum-pages)</literal> is non-(), then &ECL; automatically + increments the maximum number of pages for the class by 50 percent. The + initial value of <literal>(si::ignore-maximum-pages)</literal> is <replaceable>T</replaceable>.</para> + </section> + + <section id="Storage-information"> + <title>Storage Information</title> + <blockquote> + <screen><indexterm role="fn"><primary>room</primary></indexterm>— Function: <function>room</function> <varname>&optional x</varname></screen> + <para>The function <literal>room</literal> prints the storage information. The argument + <replaceable>x</replaceable> is simply ignored and + the output of <literal>room</literal> is always in the same + format. <literal>room</literal> prints the following information:</para> + </blockquote> + <itemizedlist mark="bullet"> + <listitem> + <para>for each type class</para> + <itemizedlist mark="bullet"> + <listitem> + <para>the number of pages so-far allocated for the type class</para> + </listitem> + <listitem> + <para>the maximum number of pages for the type class</para> + </listitem> + <listitem> + <para>the percentage of used cells to cells so-far allocated</para> + </listitem> + <listitem> + <para>the number of times the garbage collector has been + called to collect cells of the type class</para> + </listitem> + <listitem> + <para>the implementation types that belong to the type class</para> + </listitem> + </itemizedlist> + </listitem> + <listitem> + <para>the number of pages actually allocated for contiguous blocks</para> + </listitem> + <listitem> + <para>the maximum number of pages for contiguous blocks</para> + </listitem> + <listitem> + <para>the number of times the garbage collector has been called to + collect contiguous blocks</para> + </listitem> + <listitem> + <para>the number of pages in the hole</para> + </listitem> + <listitem> + <para>the maximum number of pages for relocatable blocks</para> + </listitem> + <listitem> + <para>the number of times the garbage collector has been called to + collect relocatable blocks</para> + </listitem> + <listitem> + <para>the total number of pages allocated for cells</para> + </listitem> + <listitem> + <para>the total number of pages allocated</para> + </listitem> + <listitem> + <para>the number of available pages</para> + </listitem> + <listitem> + <para>the number of pages &ECL; can use.</para> + </listitem> + </itemizedlist> + <para>The number of times the garbage collector has been called is not shown, if the + number is zero.</para> + <para>In the following example, the maximum of <literal>531</literal> pages have already been + allocated for the type class to which cons belongs, but only 16.9 percent of + the cells are actually used. The garbage collector was once invoked to collect + cells in this type class.</para> + <para><screen> + > (room) + 200/200 48.4% CONS BIGNUM RATIO COMPLEX STRUCTURE + 1/5 7.4% SHORT-FLOAT RANDOM-STATE READTABLE + 10/34 99.3% LONG-FLOAT CFUN CCLOSURE + 47/64 71.9% SYMBOL + 1/1 8.9% PACKAGE + 2/69 81.8% ARRAY HASH-TABLE VECTOR BIT-VECTOR STREAM + 16/40 95.9% STRING + 1/1 6.8% PATHNAME + + 0/271 contiguous (1 blocks) + 127 hole + 40 3.4% relocatable + + 278 pages for cells + 445 total pages + 14709 pages available + 1230 pages in heap but not gc'd + pages needed for gc marking + 16384 maximum pages + </screen></para> + </section> + </chapter> +</book> +<!-- Keep this comment at the end of the file + Local variables: + mode: nxml + sgml-parent-document: "ecl.xml" + sgml-indent-step: 1 + nxml-child-indent: 1 + nxml-outline-child-indent: 1 + fill-column: 79 + End: +-->