malloc.html

sqlite的帮助文档

<blockquote>
<table cellpadding="10" border="0">
<tr><td valign="top"><b>N</b></td>
<td valign="top">
The amount of raw memory needed by the memory allocation system
in order to guarantee that no memory allocation will ever fail.
</td></tr>
<tr><td valign="top"><b>M</b></td>
<td valign="top">
The maximum amount of memory that the application ever has checked out
at any point in time.
</td></tr>
<tr><td valign="top"><b>n</b></td>
<td valign="top">
The ratio of the largest memory allocation to the smallest.  We assume
that every memory allocation size is an integer multiple of the smallest memory
allocation size.
</td></tr>
</table>
</blockquote>

<p>Robson proves the following result:</p>

<blockquote>
<b>N</b> = <b>M</b>*(1 + (log<sub>2</sub> <b>n</b>)/2) - <b>n</b> + 1
</blockquote>

<p>Colloquially, the Robson proof shows that in order to guarantee
breakdown-free operation, any memory allocator must use a memory pool
of size <b>N</b> which exceeds the maximum amount of memory every
used <b>M</b> by a multiplier that depends on <b>n</b>, 
the ratio of the largest to the smallest allocation size.  In other
words, unless all memory allocations are of exactly the same size
(<b>n</b>=1) then the system needs access to more memory than it will
ever use at one time.  Furthermore, we see that the amount of surplus
memory required grows rapidly as the ratio of largest to smallest
allocations increases, and so there is strong incentive to keep all
allocations as near to the same size as possible.</p>

<p>Robson's proof is constructive. 
He provides an algorithm for computing a sequence of allocation
and deallocation operations that will lead to an allocation failure due to
memory fragmentation if available memory is as much as one byte
less than <b>N</b>.
And, Robson shows that a power-of-two first-fit memory allocator
(such as implemented by <a href="malloc.html#memsys5">memsys5</a>) will never fail a memory allocation
provided that available memory is <b>N</b> or more bytes.</p>

<p>The values <b>M</b> and <b>n</b> are properties of the application.
If an application is constructed in such a way that both <b>M</b> and
<b>n</b> are known, or at least have known upper bounds, and if the
application uses
the <a href="malloc.html#memsys5">memsys5</a> memory allocator and is provided with <b>N</b> bytes of
available memory space using <a href="c3ref/c_config_getmalloc.html">SQLITE_CONFIG_HEAP</a>
then Robson proves that no memory allocation request will ever fail
within the application.
To put this another way, the application developer can select a value
for <b>N</b> that will guarantee that no call to any SQLite interface
will ever return <a href="c3ref/c_abort.html">SQLITE_NOMEM</a>.  The memory pool will never become
so fragmented that a new memory allocation request cannot be satisfied.
This is an important property for
applications where a software fault could cause injury, physical harm, or
loss of irreplaceable data.</p>

<h3>4.1 Computing and controlling parameters <b>M</b> and <b>n</b></h3>

<p>The Robson proof applies separately to each of the memory allocators
used by SQLite:</p>

<ul>
<li>The general-purpose memory allocator (<a href="malloc.html#memsys5">memsys5</a>).</li>
<li>The <a href="malloc.html#scratch">scratch memory allocator</a>.</li>
<li>The <a href="malloc.html#pagecache">pagecache memory allocator</a>.</li>
<li>The <a href="malloc.html#lookaside">lookaside memory allocator</a>.</li>
</ul>

<p>For allocators other than <a href="malloc.html#memsys5">memsys5</a>,
all memory allocations are of the same size.  Hence, <b>n</b>=1
and therefore <b>N</b>=<b>M</b>.  In other words, the memory pool need
be no larger than the largest amount of memory in use at any given moment.</p>

<p>SQLite guarantees that no thread will ever use more than a single
scratch memory slot at one time.  So if an application allocates as many
scratch memory slots as there are threads, and assuming the size of
each slot is large enough, there is never a chance of overflowing the
scratch memory allocator.  An upper bound on the size of scratch memory
allocations is six times the largest page size.  It is easy, therefore,
to guarantee breakdown-free operation of the scratch memory allocator.</p>

<p>The usage of pagecache memory is somewhat harder to control in
SQLite version 3.6.1, though mechanisms are planned for subsequent
releases that will make controlling pagecache memory much easier.
Prior to the introduction of these new mechanisms, the only way
to control pagecache memory is using the <a href="pragma.html#pragma_cache_size">cache_size pragma</a>.</p>

<p>Safety-critical applications will usually want to modify the
default lookaside memory configuration so that when the initial
lookaside memory buffer is allocated during <a href="c3ref/open.html">sqlite3_open()</a> the
resulting memory allocation is not so large as to force the <b>n</b>
parameter to be too large.  In order to keep <b>n</b> under control,
it is best to try to keep the largest memory allocation below 2 or 4
kilobytes.  Hence, a reasonable default setup for the lookaside
memory allocator might any one of the following:</p>

<blockquote><pre>
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 32, 32);  /* 1K */
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 64, 32);  /* 2K */
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 32, 64);  /* 2K */
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 64, 64);  /* 4K */
</pre></blockquote>

<p>Another approach is to initially disable the lookaside memory
allocator:</p>

<blockquote><pre>
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 0, 0);
</pre></blockquote>

<p>Then let the application maintain a separate pool of larger
lookaside memory buffers that it can distribute to <a href="c3ref/sqlite3.html">database connections</a>
as they are created.  In the common case, the application will only
have a single <a href="c3ref/sqlite3.html">database connection</a> and so the lookaside memory pool
can consist of a single large buffer.</p>

<blockquote><pre>
sqlite3_db_config(db, SQLITE_DBCONFIG_LOOKASIDE, aStatic, 256, 500);
</pre></blockquote>

<p>The lookaside memory allocator is really intended as performance
optimization, not as a method for assuring breakdown-free memory allocation,
so it is not unreasonable to completely disable the lookaside memory
allocator for safety-critical operations.</p>

<p>The general purpose memory allocator is the most difficult memory pool
to manage because it supports allocations of varying sizes.  Since 
<b>n</b> is a multiplier on <b>M</b> we want to keep <b>n</b> as small
as possible.  This argues for keeping the minimum allocation size for
<a href="malloc.html#memsys5">memsys5</a> as large as possible.  In most applications, the
<a href="malloc.html#lookaside">lookaside memory allocator</a> is able to handle small allocations.  So
it is reasonable to set the minimum allocation size for <a href="malloc.html#memsys5">memsys5</a> to
2, 4 or even 8 times the maximum size of a lookaside allocation.  
A minimum allocation size of 512 is a reasonable setting.</p>

<p>Further to keeping <b>n</b> small, one desires to keep the size of
the largest memory allocations under control.
Large requests to the general-purpose memory allocator
might come from several sources:</p>

<ol>
<li>SQL table rows that contain large strings or BLOBs.</li>
<li>Complex SQL queries that compile down to large <a href="c3ref/stmt.html">prepared statements</a>.</li>
<li>SQL parser objects used internally by <a href="c3ref/prepare.html">sqlite3_prepare_v2()</a>.</li>
<li>Storage space for <a href="c3ref/sqlite3.html">database connection</a> objects.</li>
<li>Scratch memory allocations that overflow into the general-purpose
    memory allocator.</li>
<li>Page cache memory allocations that overflow into the general-purpose
    memory allocator.</li>
<li>Lookaside buffer allocations for new <a href="c3ref/sqlite3.html">database connections</a>.</li>
</ol>

<p>The last three allocations can be controlled and/or eliminated by
configuring the <a href="malloc.html#scratch">scratch memory allocator</a>, <a href="malloc.html#pagecache">pagecache memory allocator</a>,
and <a href="malloc.html#lookaside">lookaside memory allocator</a> appropriately, as described above.
The storage space required for <a href="c3ref/sqlite3.html">database connection</a> objects depends
to some extent on the length of the filename of the database file, but
rarely exceeds 2KB on 32-bit systems.  (More space is required on
64-bit systems due to the increased size of pointers.)
Each parser object uses about 1.6KB of memory.  Thus, elements 3 through 7
above can easily be controlled to keep the maximum memory allocation
size below 2KB.</p>

<p>If the application is designed to manage data in small pieces,
then the database should never contain any large strings or BLOBs
and hence element 1 above should not be a factor.  If the database
does contain large strings or BLOBs, they should be read using
<a href="c3ref/blob.html">incremental BLOB I/O</a> and rows that contain the
large strings or BLOBs should never be update by any means other
than <a href="c3ref/blob.html">incremental BLOB I/O</a>.  Otherwise, the 
<a href="c3ref/step.html">sqlite3_step()</a> routine will need to read the entire row into
contiguous memory at some point, and that will involve at least
one large memory allocation.</p>

<p>The final source of large memory allocations is the space to hold
the <a href="c3ref/stmt.html">prepared statements</a> that result from compiling complex SQL
operations.  Ongoing work by the SQLite developers is reducing the
amount of space required here.  But large and complex queries might
still require <a href="c3ref/stmt.html">prepared statements</a> that are several kilobytes in
size.  The only workaround at the moment is for the application to
break complex SQL operations up into two or more smaller and simpler 
operations contained in separate <a href="c3ref/stmt.html">prepared statements</a>.</p>

<p>All things considered, applications should normally be able to
hold their maximum memory allocation size below 2K or 4K.  This
gives a value for log<sub>2</sub>(<b>n</b>) of 2 or 3.  This will
limit <b>N</b> to between 2 and 2.5 times <b>M</b>.</p>

<p>The maximum amount of general-purpose memory needed by the application
is determined by such factors as how many simultaneous open 
<a href="c3ref/sqlite3.html">database connection</a> and <a href="c3ref/stmt.html">prepared statement</a> objects the application
uses, and on the complexity of the <a href="c3ref/stmt.html">prepared statements</a>.  For any
given application, these factors are normally fixed and can be
determined experimentally using <a href="c3ref/c_status_malloc_size.html">SQLITE_STATUS_MEMORY_USED</a>.
A typical application might only use about 40KB of general-purpose
memory.  This gives a value of <b>N</b> of around 100KB.</p>

<h3>4.2 Ductile failure</h3>

<p>If the memory allocation subsystems within SQLite are configured
for breakdown-free operation but the actual memory usage exceeds
design limits set by the <a href="malloc.html#nofrag">Robson proof</a>, SQLite will usually continue 
to operate normally.
The <a href="malloc.html#scratch">scratch memory allocator</a>, the <a href="malloc.html#pagecache">pagecache memory allocator</a>,
and the <a href="malloc.html#lookaside">lookaside memory allocator</a> all automatically failover
to the <a href="malloc.html#memsys5">memsys5</a> general-purpose memory allocator.  And it is usually the
case that the <a href="malloc.html#memsys5">memsys5</a> memory allocator will continue to function
without fragmentation even if <b>M</b> and/or <b>n</b> exceeds the limits
imposed by the <a href="malloc.html#nofrag">Robson proof</a>.  The <a href="malloc.html#nofrag">Robson proof</a> shows that it is 
possible for a memory allocation to break down and fail in this 
circumstance, but such a failure requires an especially
despicable sequence of allocations and deallocations - a sequence that
SQLite has never been observed to follow.  So in practice it is usually
the case that the limits imposed by Robson can be exceeded by a
considerable margin with no ill effect.</p>

<p>Nevertheless, application developers are admonished to monitor
the state of the memory allocation subsystems and raise alarms when
memory usage approaches or exceeds Robson limits.  In this way,
the application will provide operators with abundant warning well
in advance of failure.
The <a href="malloc.html#memstatus">memory statistics</a> interfaces of SQLite provide the application with
all the mechanism necessary to complete the monitoring portion of
this task.</p>

<a name="stability"></a>
<h2>5.0 Stability Of Memory Interfaces</h2>

<p>As of this writing (circa SQLite version 3.6.1) all of the alternative
memory allocators and mechanisms for manipulating, controlling, and
measuring memory allocation in SQLite are considered experimental and
subject to change from one release to the next.  These interfaces are
in the process of being refined to work on a wide variety of systems
under a range of constraints.  The SQLite developers need the flexibility
to change the memory allocator interfaces in order to best meet the
needs of a wide variety of systems.</p>

<p>One may anticipate that the memory allocator interfaces will
eventually stabilize.  Appropriate notice will be given when that
occurs.  In the meantime, applications developers who make use of
these interfaces need to be prepared to modify their applications
to accommodate changes in the SQLite interface.</p>

<a name="summary"></a>
<h2>6.0 Summary Of Memory Allocator Interfaces</h2>

<p><i>To be completed...</i></p>
<hr><small><i>
This page last modified 2008/11/12 14:22:39 UTC
</i></small></div></body></html>