Documentation Source Text

following capabilities:</p>

<ul>
<li><p>
<b>Robust against allocation failures.</b>
If a memory allocation ever fails (that is to say, 
if malloc() or realloc() ever return NULL)
then SQLite will recover gracefully.   SQLite will first attempt
to free memory from unpinned cache pages then retry the allocation
request.  
Failing that, SQLite will either stop what
it is doing and return the
[SQLITE_NOMEM] error code back up to the application or it will
make due without the requested memory.
</p></li>

<li><p>
<b>No memory leaks.</b>
The application is resposible for destroying any objects it allocates.
(For example, the application must use [sqlite3_finalize()] on 
every [prepared statement] and [sqlite3_close()] on every 
[database connection].)   But as long as
the application cooperates, SQLite will never leak memory.  This is
true even in the face of memory allocation failures of other system
errors.
</p></li>

</p></li>

</ul>

<a name="testing"></a>
<h2>2.0 Testing</h2>

<p>Over
75% of the code in the SQLite source tree is devoted purely to testing
and verification.  Reliability is important to SQLite.
Among the tasks of the test infrastructure is to insure that
SQLite does not misuse dynamically allocated memory, that SQLite
does not leak memory, and that SQLite responses
correctly to a dynamic memory allocation failure.</p>

<tcl>hd_fragment memsys5 memsys5</tcl>
<h4>3.1.3 Zero-malloc memory allocator</h4>

<p>When SQLite is compiled with the [SQLITE_ENABLE_MEMSYS5] option, an
alternative memory allocator that does not use malloc() is included in the
build.  The SQLite developers refer to this alternative memory allocator
as "memsys5".  Even when it is included in the build, memsys5 is 
disabled by default.
To enable memsys5, the application must invoke the following SQLite 
interface at start-time:</p>

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_HEAP], pBuf, szBuf, mnReq);
</pre></blockquote>

<p>In the call above, pBuf is a pointer to a large, contiguous chunk
of memory space that SQLite will use to satisfy all of its memory
allocation needs.   pBuf might point to a static array or it might
be memory obtained from some other application-specific mechanism.
szBuf is an integer which is the number of bytes of memry space
pointed to by pBuf.  mnReq is another integer which is the
minimum size of an allocation.  Any call to [sqlite3_malloc(N)] where
N is less than mnReq will be rounded up to mnReq.  mnReq must be
a power of two.  We shall see later that the mnReq parameter is
important in reducing the value of <b>n</b> and hence the minimum memory
size requirement in the [Robson proof].</p>

<p>The memsys5 allocator is designed for use on embedded systems, 
though there is nothing to prevent its use on workstations.
The szBuf is typically between a few hundred kilobytes up to a few
dozen megabytes, depending on system requirements and memory budget.</p>

<p>The algorithm used by memsys5 is can be called "power-of-two,
first-fit".  The sizes of all memory allocation 
requests are rounded up to a power of two and that the request is satisfied
by the first free slot in pBuf that is large enough.  Adjacent freed

SQLite falls back to using the regular memory allocator for its scratch
memory allocations.  The default setup is sz=0 and N=0 so the use
of the regular memory allocator is the default behavior.</p>

<tcl>hd_fragment pagecache {pagecache memory allocator}</tcl>
<h3>3.3 Page cache memory</h3>

<p>In most applications, the database page cache subsystem within 
SQLite uses more dynamically allocated memory than all other parts
of SQLite combined.  It is not unusual to see the database page cache
consumes over 10 times more memory than the rest of SQLite combined.</p>

<p>SQLite can be configured to make page cache memory allocations from
a separate and distinct memory pool of fixed-size
slots.  This can have two advantages:</p>

<ul>
<li><p>
Because allocations are all the same size, the memory allocator can
operate much faster.  The allocator need not bother with coalescing 
adjacent free slots nor searching for a slot
of an appropriate size.  All unallocated memory slots can be stored on
a linked list.  Allocating consists of removing the first entry from the
list.  Deallocating is simply adding an entry to the beginning of the list.
</p></li>

<li><p>
With a single allocation size, the <b>n</b> parameter in the
[Robson proof] is 1, and the total memory space required by the allocator
(<b>N</b>) is exactly equal to maximum memory used (<b>M</b>).  
No additional memory is required to cover fragmentation overhead, thus 
reducing memory requirements.  This is particularly important for the
page cache memory since the page cache constitutes the largest component
of the memory needs of SQLite.
</p></li>
</ul>

<p>The page-cache memory allocator is disabled by default.
An application can enabled it at start-time as follows:</p>

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_PAGECACHE], pBuf, sz, N);
</pre></blockquote>

<p>The pBuf parameter is a pointer to a contiguous range of bytes that
SQLite will use for for page-cache memory allocations.  The buffer must be
at least sz*N bytes in size.  The "sz" parameter
is the size of each page-cache allocation.  N is the maximum 
number of available allocations.</p>

<p>If SQLite needs a page-cache entry that is larger than "sz" bytes or
if it needs more than N entries, it falls back to using the
general-purpose memory allocator.</p>

<tcl>hd_fragment lookaside {lookaside memory allocator}</tcl>
<h3>3.4 Lookaside memory allocator</h3>

<p>SQLite [database connections] make many
small and short-lived memory allocations.
This occurs most commonly when compiling SQL statements using
[sqlite3_prepare_v2()] but also to a lessor extent when running
[prepared statements] using [sqlite3_step()].  These small memory
allocations are used to hold things such as the names of tables
and columns, parse tree nodes, individual query results values,
and b-tree cursor objects.  There are consequently
many calls to malloc() and free() - so many calls that malloc() and
free() end up using a significant fraction of the CPU time assigned
to SQLite.</p>

<p>SQLite [version 3.6.1] introduced the lookaside memory allocator to
help reduce the memory allocation load.  In the lookaside allocator,
each [database connection] preallocates a single large chunk of memory
(typically in the range of 50 to 100 kilobytes) and divides that chunk
up into small fixed-size "slots" of around 50 to 200 byte each.  This
becomes the lookaside memory pool.  Thereafter, memory allocations
associated with the [database connection] and that are not too larger
are satisfied using one of the lookaside pool slots rather than by calling
the general-purpose memory allocator.  Larger allocations continue to
use the general-purpose memory allocator, as do allocations that occur
when the lookaside pool slots are all checked out.  
But in many cases, the memory
allocations are small enough and there are few enough outstanding that
the new memory requests can be satisfied from the lookaside
pool.</p>

<p>Because lookaside allocations are always the same size, the allocation
and deallocation algorithms are very quick.  There is no
need to coalesce adjacent free slots nor search for a slot
of a particular size.  Each [database connection] maintains a singly-linked
list of unused slots.  Allocation requests simply pull the first
element of this list.  Decallocations simply push the element back onto
the front of the list.
Furthermore, each [database connection] is assumed to already be
running in a single thread (there are mutexes already in
place to enforce this) so no additional mutexing is required to 
serialize access to the lookaside slot freelist.
Consequently, lookaside memory
allocations and deallocations are very fast.  In speed tests on
Linux and Mac OS-X workstations, SQLite has shown overall performance
improvements as high as 10% and 15%, depending on the workload how
lookaside is configured.</p>

<p>The size of the lookaside memory pool has a global default value
but can also be configured on a connection-by-connection basis.
To change the default size of the lookaside memory pool use the 
following interface at start-time:</p>

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_LOOKASIDE], sz, cnt);
</pre></blockquote>

<p>The "sz" parameter is the size in bytes of each lookaside slot.
The default is 100 bytes.  The "cnt" parameter is
the total number of lookaside memory slots per database connection.
The default value is 500 slots. The total amount
of lookaside memory allocated to each [database connection] is
sz*cnt bytes.  Hence the lookaside memory pool allocated per database 
connection is 50 kilobytes by default.
(Note: these default values are for SQLite [version 3.6.1] and are subject
to changes in future releases.)
</p>

<p>The lookaside pool can be changed for an individual
[database connection] "db" using this call:</p>

statistics are useful in helping to determine how much memory an
application really needs.  The statistics can also be used in
high-reliability system to determine
if the memory usage is coming close to or exceeding the limits 
of the [Robson proof] and hence that the memory allocation subsystem is 
liable to breakdown.</p>

<p>Most memory statistics are global, and therefore the tracking of
statistics must be serialized with a mutex.  Statistics are turned 
on by default,but an option exists to disable them.  By disabling 
memory statistics,
SQLite avoids entrying and leaving a mutex on each memory allocation
and deallocation.  That savings can be noticable on systems where
mutex operations are expensive.  To disable memory statistics, the
following interface is used at start-time:</p>

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_MEMSTATUS], onoff);
</pre></blockquote>

<blockquote><pre>
[sqlite3_status]([SQLITE_STATUS_MEMORY_USED|verb], &current, &highwater, resetflag);
</pre></blockquote>

<p>The "verb" argument determines what statistic is accessed.
There are [SQLITE_STATUS_MEMORY_USED | various verbs] defined.  The
list is expected to grow as the [sqlite3_status()] interface matures.
The current value the selected parameter is written into integer 
"current" and the highest historical value
is written into integer "highwater".  If resetflag is true, then
the high-water mark is reset down to the current value after the call
returns.</p>

<p>A different interface is used to find statistics associated with a
single [database connection]:</p>

<blockquote><pre>

the [pagecache memory allocator], or the [lookaside memory allocator].
This deficiency will likely be addressed in a future release.</p>

<tcl>hd_fragment nofrag {Robson proof}</tcl>
<h2>4.0 Mathematical Guarantees Against Memory Allocation Failures</h2>

<p>The problem of dynamic memory allocation, and specifically the
problem of a memory allocator breakdown, has been studied by

J. M. Robson and the results published as:</p>

<blockquote>
J. M. Robson.  "Bounds for Some Functions Concerning Dynamic
Storage Allocation".  <i>Journal of the Association for
Computing Machinery</i>, Volume 21, Number 8, July 1974,
pages 491-499.
</blockquote>

<p>Let us use the following notation (similar but not identical to
Robson's notation):</p>

<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

<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>Colloqually, 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 a 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 [memsys5]) 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 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 [memsys5] memory allocator and is provided with <b>N</b> bytes of
available memory space using [SQLITE_CONFIG_HEAP]
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> which will guarantee that no call to any SQLite interface
will ever return [SQLITE_NOMEM].  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 ([memsys5]).</li>

<li>The [scratch memory allocator].</li>
<li>The [pagecache memory allocator].</li>
<li>The [lookaside memory allocator].</li>
</ul>

<p>For allocators other than [memsys5],
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 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 [cache_size pragma].</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, since it support 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
[memsys5] as large as possible.  In most appliations, the
[lookaside memory allocator] is able to handle small allocations.  So
it is reasonable to set the minimum allocation size for [memsys5] 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 memory allocations against 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 [prepared statements].</li>
<li>SQL parser objects used internally by [sqlite3_prepare_v2()].</li>
<li>Storage space for [database connection] 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 [database connections].</li>
</ol>

<p>The last three allocations can be controlled and/or eliminated by
configuring the [scratch memory allocator], [pagecache memory allocator],
and [lookaside memory allocator] appropriately, as described above.
The storage space required for [database connection] 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>The final source of large memory allocations is the space to hold
the [prepared statements] 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 [prepared statements] 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 [prepared statements].</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 
[database connection] and [prepared statement] objects the application
uses, and on the complexity of the [prepared statements].  For any
given application, these factors are normally fixed and can be
determined experiementally using [SQLITE_STATUS_MEMORY_USED].
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 [Robson proof], SQLite will usually continue 
to operate normally.
The [scratch memory allocator], the [pagecache memory allocator],
and the [lookaside memory allocator] all automatically failover
to the [memsys5] general-purpose memory allocator.  And it is usually the
case that the [memsys5] memory allocator will continue to function
without fragmentation even if <b>M</b> and/or <b>n</b> exceeds the limits
imposed by the [Robson proof].  The [Robson proof] shows that it is 
possible for a memory allocation to break down and fail in this 
circumstance, but such a failure requires an especially
dispicable 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 [memory statistics] interfaces of SQLite provides 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