<title>Dynamic Memory Allocation In SQLite</title>

<h1>Dynamic Memory Allocation In SQLite</h1>
<tcl>hd_keywords {memory allocation}</tcl>

<p>SQLite uses dynamic memory allocation to obtain
memory for storing various objects
(ex: [database connections] and [prepared statements]) and to build
a memory cache of the database file and to hold the results of queries.
Much effort has gone into making the dynamic memory allocation subsystem
of SQLite reliable, predictable, robust, secure, and efficient.</p>

<p>This document provides an overview of dynamic memory allocation within 
SQLite.  The target audience is software engineers who are tuning their
use of SQLite for peak performance in demanding environments.
Nothing in this document is required knowledge for using SQLite.  The
default settings and configuration for SQLite will work well in most
applications.  However, the information contained in this document may
be useful to engineers who are tuning SQLite to comply with special
requirements or to run under unusual circumstances.</p>

<a name="features"></a>
<h2>1.0 Features</h2>

<p>The SQLite core and its memory allocation subsystem provides the 
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 do without the requested memory.
</p></li>

<li><p>
<b>No memory leaks.</b>
The application is responsible 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 or other system
errors.
</p></li>

<li><p>
<b>Memory usage limits.</b>
The [sqlite3_soft_heap_limit64()] mechanism allows the application to
set a memory usage limit that SQLite strives to stay below.  SQLite
will attempt to reuse memory from its caches rather than allocating new
memory as it approaches the soft limit.
</p></li>

<li><p>
<b>Zero-malloc option.</b>
The application can optionally provide SQLite with several buffers of bulk memory
at startup and SQLite will then use those provided buffers for all of
its memory allocation needs and never call system malloc() or free().
</p></li>

<li><p>
<b>Application-supplied memory allocators.</b>
The application can provide SQLite with pointers to alternative 
memory allocators at start-time.  The alternative memory allocator
will be used in place of system malloc() and free().
</p></li>

<li><p>
<b>Proof against breakdown and fragmentation.</b>
SQLite can be configured so that, subject to certain usage constraints
detailed below, it is guaranteed to never fail a memory allocation
or fragment the heap.
This property is important to long-running, high-reliability
embedded systems where a memory allocation error could contribute
to an overall system failure.
</p></li>

<li><p>
<b>Memory usage statistics.</b>
Applications can see how much memory they are using and detect when
memory usage is approaching or exceeding design boundaries.
</p></li>

<a name="pwwo"></a>
<li><p>
<b>Plays well with memory debuggers.</b>
Memory allocation in SQLite is structured so that standard
third-party memory debuggers (such as [http://dmalloc.com | dmalloc] or 
[http://valgrind.org | valgrind]) can be used to verify correct
memory allocation behavior.</p>

<li><p>
<b>Minimal calls to the allocator.</b>
The system malloc() and free() implementations are inefficient
on many systems.  SQLite strives to reduce overall processing time
by minimizing its use of malloc() and free().
</p></li>

<li><p>
<b>Open access.</b>
Pluggable SQLite extensions or even the application itself can 
access to the same underlying memory allocation
routines used by SQLite through the
[sqlite3_malloc()], [sqlite3_realloc()], and [sqlite3_free()] interfaces.
</p></li>

</ul>

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

<p>Most of the code in the SQLite source tree is devoted purely to 
[testing | testing and verification].  Reliability is important to SQLite.
Among the tasks of the test infrastructure is to ensure that
SQLite does not misuse dynamically allocated memory, that SQLite
does not leak memory, and that SQLite responds
correctly to a dynamic memory allocation failure.</p>

<p>The test infrastructure verifies that SQLite does not misuse
dynamically allocated memory by using a specially instrumented
memory allocator.  The instrumented memory allocator is enabled
at compile-time using the [SQLITE_MEMDEBUG] option.  The instrumented
memory allocator is much slower than the default memory allocator and
so its use is not recommended in production.  But when
enabled during testing, 
the instrumented memory allocator performs the following checks:</p>

<ul>
<li><p><b>Bounds checking.</b>
The instrumented memory allocator places sentinel values at both ends
of each memory allocation to verify that nothing within SQLite writes
outside the bounds of the allocation.</p></li>

<li><p><b>Use of memory after freeing.</b>
When each block of memory is freed, every byte is overwritten with a
nonsense bit pattern.  This helps to ensure that no memory is ever
used after having been freed.</p></li>

<li><p><b>Freeing memory not obtained from malloc.</b>
Each memory allocation from the instrumented memory allocator contains
sentinels used to verify that every allocation freed came
from prior malloc.</p></li>

<li><p><b>Uninitialized memory.</b>
The instrumented memory allocator initializes each memory allocation
to a nonsense bit pattern to help ensure that the user makes no
assumptions about the content of allocation memory.</p></li>
</ul>

<p>Regardless of whether or not the instrumented memory allocator is
used, SQLite keeps track of how much memory is currently checked out.
There are hundreds of test scripts used for testing SQLite.  At the
end of each script, all objects are destroyed and a test is made to
ensure that all  memory has been freed.  This is how memory
leaks are detected.  Notice that memory leak detection is in force at
all times, during test builds and during production builds.  Whenever
one of the developers runs any individual test script, memory leak
detection is active.  Hence memory leaks that do arise during development
are quickly detected and fixed.</p>

<a name="oomtesting"></a>
<p>The response of SQLite to out-of-memory (OOM) errors is tested using
a specialized memory allocator overlay that can simulate memory failures.
The overlay is a layer that is inserted in between the memory allocator
and the rest of SQLite.  The overlay passes most memory allocation
requests straight through to the underlying allocator and passes the
results back up to the requester.  But the overlay can be set to 
cause the Nth memory allocation to fail.  To run an OOM test, the overlay
is first set to fail on the first allocation attempt.  Then some test
script is run and verification that the allocation was correctly caught
and handled is made.  Then the overlay is set to fail on the second
allocation and the test repeats.  The failure point continues to advance
one allocation at a time until the entire test procedure runs to
completion without hitting a memory allocation error.  This whole
test sequence run twice.  On the first pass, the
overlay is set to fail only the Nth allocation.  On the second pass,
the overlay is set to fail the Nth and all subsequent allocations.</p>

<p>Note that the memory leak detection logic continues to work even
when the OOM overlay is being used.  This verifies that SQLite
does not leak memory even when it encounters memory allocation errors.
Note also that the OOM overlay can work with any underlying memory
allocator, including the instrumented memory allocator that checks
for memory allocation misuse.  In this way it is verified that 
OOM errors do not induce other kinds of memory usage errors.</p>

<p>Finally, we observe that the instrumented memory allocator and the
memory leak detector both work over the entire SQLite test suite and
the [TCL test suite] provides over 99% statement test coverage and that
the [TH3] test harness provides [test coverage | 100% branch test coverage]
with no leak leaks. This is
strong evidence that dynamic memory allocation is used correctly
everywhere within SQLite.</p>

<a name="allocarray"></a>
<h3>2.1 Use of reallocarray()</h3>

<p>The reallocarray() interface is a recent innovation (circa 2014)
from the OpenBSD community that grow out of efforts to prevent the
next [http://heartbleed.com | "heartbleed" bug] by avoiding 32-bit integer
arithmetic overflow on memory allocation size computations.  The
reallocarray() function has both unit-size and count parameters.
To allocate memory sufficient to hold an array of N elements each X-bytes
in size, one calls "reallocarray(0,X,N)".  This is preferred over
the traditional technique of invoking "malloc(X*N)" as reallocarray()
eliminates the risk that the X*N multiplication will overflow and
cause malloc() to return a buffer that is a different size from what
the application expected.</p>

<p>SQLite does not use reallocarray().  The reason is that reallocarray()
is not useful to SQLite.  It turns out that SQLite never does memory
allocations that are the simple product of two integers.  Instead, SQLite
does allocations of the form "X+C" or "N*X+C" or "M*N*X+C" or
"N*X+M*Y+C", and so forth.  The reallocarray() interface is not helpful
in avoiding integer overflow in those cases.</p>

<p>Nevertheless, integer overflow in the computation of memory allocation
sizes is a concern that SQLite would like to deal with.  To prevent
problems, all SQLite internal memory allocations occur using thin wrapper
functions that take a signed 64-bit integer size parameter.  The SQLite 
source code is audited to ensure that all size computations are carried 
out using 64-bit signed integers as well.  SQLite will
refuse to allocate more than about 2GB of memory at one go.  (In common
use, SQLite seldom ever allocates more than about 8KB of memory at a time
so a 2GB allocation limit is not a burden.)  So the 64-bit size parameter
provides lots of headroom for detecting overflows.  The same audit that
verifies that all size computations are done as 64-bit signed integers
also verifies that it is impossible to overflow a 64-bit integer
during the computation.</p>

<p>The code audits used to ensure that memory allocation size computations
do not overflow in SQLite are repeated prior to every SQLite release.</p>

<a name="config"></a>
<h2>3.0 Configuration</h2>

<p>The default memory allocation settings in SQLite are appropriate
for most applications.  However, applications with unusual or particularly
strict requirements may want to adjust the configuration to more closely
align SQLite to their needs.
Both compile-time and start-time configuration options are available.</p>

<tcl>hd_fragment altalloc {built-in memory allocators}</tcl>
<h3>3.1 Alternative low-level memory allocators</h3>

<p>The SQLite source code includes several different memory allocation
modules that can be selected at compile-time, or to a limited extent
at start-time.</p>

<tcl>hd_fragment defaultalloc {default memory allocator}</tcl>
<h4>3.1.1 The default memory allocator</h4>

<p>By default, SQLite uses the malloc(), realloc(), and free() routines
from the standard C library for its memory allocation needs.  These routines
are surrounded by a thin wrapper that also provides a "memsize()" function
that will return the size of an existing allocation.  The memsize() function
is needed to keep an accurate count of the number of bytes of outstanding
memory; memsize() determines how many bytes to remove from the outstanding
count when an allocation is freed.  The default allocator implements
memsize() by always allocating 8 extra bytes on each malloc() request and
storing the size of the allocation in that 8-byte header.</p>

<p>The default memory allocator is recommended for most applications.
If you do not have a compelling need to use an alternative memory
allocator, then use the default.</p>

<tcl>hd_fragment memdebug {debugging memory allocator} *memsys2</tcl>
<h4>3.1.2 The debugging memory allocator</h4>

<p>If SQLite is compiled with the [SQLITE_MEMDEBUG] compile-time option,
then a different, heavy wrapper is used around system malloc(), realloc(), 
and free().
The heavy wrapper allocates around 100 bytes of extra space
with each allocation.  The extra space is used to place sentinel values 
at both ends of the allocation returned to the SQLite core.  When an
allocation is freed,
these sentinels are checked to make sure the SQLite core did not overrun
the buffer in either direction.  When the system library is GLIBC, the 
heavy wrapper also makes use of the GNU backtrace() function to examine
the stack and record the ancestor functions of the malloc() call.  When
running the SQLite test suite, the heavy wrapper also records the name of
the current test case.  These latter two features are useful for
tracking down the source of memory leaks detected by the test suite.</p>

<p>The heavy wrapper that is used when [SQLITE_MEMDEBUG] is set also
makes sure each new allocation is filled with nonsense data prior to
returning the allocation to the caller.  And as soon as an allocation
is free, it is again filled with nonsense data.  These two actions help
to ensure that the SQLite core does not make assumptions about the state
of newly allocated memory and that memory allocations are not used after
they have been freed.</p>

<p>The heavy wrapper employed by [SQLITE_MEMDEBUG] is intended for use
only during testing, analysis, and debugging of SQLite.  The heavy wrapper
has a significant performance and memory overhead and probably should not
be used in production.</p>

<tcl>hd_fragment win32heap {Win32 native memory allocator}</tcl>
<h4>3.1.3 The Win32 native memory allocator</h4>

<p>If SQLite is compiled for Windows with the [SQLITE_WIN32_MALLOC]
compile-time option, then a different, thin wrapper is used around
HeapAlloc(), HeapReAlloc(), and HeapFree().  The thin wrapper uses the
configured SQLite heap, which will be different from the default process
heap if the [SQLITE_WIN32_HEAP_CREATE] compile-time option is used.  In
addition, when an allocation is made or freed, HeapValidate() will be
called if SQLite is compiled with assert() enabled and the
[SQLITE_WIN32_MALLOC_VALIDATE] compile-time option.</p>

<tcl>hd_fragment memsys5 *memsys5 {zero-malloc memory allocator}</tcl>
<h4>3.1.4 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 that is the number of bytes of memory space
pointed to by pBuf.  mnReq is another integer that 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 can be called "power-of-two,
first-fit".  The sizes of all memory allocation 
requests are rounded up to a power of two and the request is satisfied
by the first free slot in pBuf that is large enough.  Adjacent freed
allocations are coalesced using a buddy system. When used appropriately,
this algorithm provides mathematical guarantees against fragmentation and
breakdown, as described further <a href="#nofrag">below</a>.</p>

<tcl>hd_fragment memsysx {experimental memory allocators}</tcl>
<h4>3.1.5 Experimental memory allocators</h4>

<p>The name "memsys5" used for the zero-malloc memory allocator implies
that there are several additional memory allocators available, and indeed
there are.  The default memory allocator is "memsys1".  The debugging
memory allocator is "memsys2".  Those have already been covered.</p>

<p>If SQLite is compiled with [SQLITE_ENABLE_MEMSYS3] then another
zero-malloc memory allocator, similar to memsys5, is included in the
source tree.  The memsys3 allocator, like memsys5, must be activated
by a call to [sqlite3_config]([SQLITE_CONFIG_HEAP],...).  Memsys3
uses the memory buffer supplied as its source for all memory allocations.
The difference between memsys3 and memsys5 is that memsys3 uses a
different memory allocation algorithm that seems to work well in
practice, but which does not provide mathematical
guarantees against memory fragmentation and breakdown.  Memsys3 was
a predecessor to memsys5.  The SQLite developers now believe that 
memsys5 is superior to
memsys3 and that all applications that need a zero-malloc memory
allocator should use memsys5 in preference to memsys3.  Memsys3 is
considered both experimental and deprecated and will likely be removed 
from the source tree in a future release of SQLite.</p>

<p>Code for memsys4 is still in the SQLite source tree (as of this writing - 
SQLite [version 3.6.1]), but it has not been maintained for several release
cycles and probably does not work.  (Update: memsys4 was removed as
of [version 3.6.5]) Memsys4 was an attempt to use mmap()
to obtain memory and then use madvise() to release unused pages
back to the operating system so that they could be reused by other
processes.  The work on memsys4 has been abandoned and the memsys4 module
will likely be removed from the source tree in the near future.</p>

<p>Memsys6 uses system malloc() and free() to obtain the memory it needs.
Memsys6 serves as an aggregator.  Memsys6 only calls system malloc() to obtain
large allocations.  It then subdivides those large allocations to services 
multiple smaller memory allocation requests coming from the SQLite core.
Memsys6 is intended for use in systems where
system malloc() is particularly inefficient.  The idea behind memsys6 is
to reduce the number of calls to system malloc() by a factor of 10 or more.</p>

<p>Memsys6 is made available by compiling SQLite with the SQLITE_ENABLE_MEMSYS6
compile-time option and then at start-time invoking:</p>

<blockquote><pre>
[sqlite3_config](SQLITE_CONFIG_CHUNKALLOC);
</pre></blockquote>

<p>Memsys6 was added in SQLite [version 3.6.1].
It is very experimental.  Its future is uncertain and it may be removed
in a subsequent release.  Update:  Memsys6 was removed as of 
[version 3.6.5].</p>

<p>Other experimental memory allocators might be added in future releases
of SQLite.  One may anticipate that these will be called memsys7, memsys8,
and so forth.</p>

<a name="appalloc"></a>
<h4>3.1.6 Application-defined memory allocators</h4>

<p>New memory allocators do not have to be part of the SQLite source tree
nor included in the sqlite3.c [amalgamation].  Individual applications can
supply their own memory allocators to SQLite at start-time.</p>

<p>To cause SQLite to use a new memory allocator, the application
simply calls:</p>

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_MALLOC], pMem);
</pre></blockquote>

<p>In the call above, pMem is a pointer to an [sqlite3_mem_methods] object
that defines the interface to the application-specific memory allocator.
The [sqlite3_mem_methods] object is really just a structure containing
pointers to functions to implement the various memory allocation primitives.
</p>

<p>In a multi-threaded application, access to the [sqlite3_mem_methods]
is serialized if and only if [SQLITE_CONFIG_MEMSTATUS] is enabled.
If [SQLITE_CONFIG_MEMSTATUS] is disabled then the methods in
[sqlite3_mem_methods] must take care of their own serialization needs.</p>

<a name="overlayalloc"></a>
<h4>3.1.7 Memory allocator overlays</h4>

<p>An application can insert layers or "overlays" in between the
SQLite core and the underlying memory allocator.
For example, the <a href="#oomtesting">out-of-memory test logic</a>
for SQLite uses an overlay that can simulate memory allocation
failures.</p>

<p>An overlay can be created by using the</p>

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_GETMALLOC], pOldMem);
</pre></blockquote>

<p>interface to obtain pointers to the existing memory allocator.
The existing allocator is saved by the overlay and is used as
a fallback to do real memory allocation.  Then the overlay is
inserted in place of the existing memory allocator using
the [sqlite3_config]([SQLITE_CONFIG_MALLOC],...) as described
<a href="#appalloc">above</a>.

<a name="stuballoc"></a>
<h4>3.1.8 No-op memory allocator stub</h4>

<p>If SQLite is compiled with the [SQLITE_ZERO_MALLOC] option, then
the [default memory allocator] is omitted and replaced by a stub
memory allocator that never allocates any memory.  Any calls to the
stub memory allocator will report back that no memory is available.</p>

<p>The no-op memory allocator is not useful by itself.  It exists only
as a placeholder so that SQLite has a memory allocator to link against
on systems that may not have malloc(), free(), or realloc() in their
standard library.
An application that is compiled with [SQLITE_ZERO_MALLOC] will need to
use [sqlite3_config()] together with [SQLITE_CONFIG_MALLOC] or
[SQLITE_CONFIG_HEAP] to specify a new alternative memory allocator
before beginning to use SQLite.</p>

<tcl>hd_fragment scratch {scratch memory allocator}</tcl>
<h3>3.2 Scratch memory</h3>

<p>SQLite occasionally needs a large chunk of "scratch" memory to
perform some transient calculation.  Scratch memory is used, for example,
as temporary storage when rebalancing a B-Tree.  These scratch memory
allocations are typically about 10 kilobytes in size and are
transient - lasting
only for the duration of a single, short-lived function call.</p>

<p>In older versions of SQLite, the scratch memory was obtained from
the processor stack.  That works great on workstations with a large stack.
But pulling large buffers from the stack 
caused problems on embedded systems with a 
small processor stack (typically 4K or 8K).  And so SQLite was modified
to allocate scratch memory from the heap.</p>

<p>However, doing occasional large transient allocations from the heap can
lead to memory fragmentation in embedded systems.  To work around this
problem, a separate memory allocation system for scratch memory has been
created.</p>

<p>The scratch memory allocator is set up as follows:</p>

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

<p>The pBuf parameter is a pointer to a contiguous range of bytes that
SQLite will use for all scratch memory allocations.  The buffer must be
at least sz*N bytes in size.  The "sz" parameter
is the maximum size of each scratch allocation.  N is the maximum 
number of simultaneous scratch allocations.  The "sz" parameter should
be approximately 6 times the maximum database page size.  N should
be twice the number of threads running in the system.  No single thread will
ever request more than two scratch allocation at a time so if there
are never more than N threads, then there will always be enough scratch
memory available.</p>

<p>If the scratch memory setup does not define enough memory, then
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 or 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 enable 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 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 lesser 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 or 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.  Deallocations 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>

<blockquote><pre>
[sqlite3_db_config](db, [SQLITE_DBCONFIG_LOOKASIDE], pBuf, sz, cnt);
</pre></blockquote>

<p>The "pBuf" parameter is a pointer to memory space that will be
used for the lookaside memory pool.  If pBuf is NULL, then SQLite
will obtain its own space for the memory pool using [sqlite3_malloc()].
The "sz" and "cnt" parameters are the size of each lookaside slot
and the number of slots, respectively.  If pBuf is not NULL, then it
must point to at least sz*cnt bytes of memory.</p>

<p>The lookaside configuration can only be changed while there are
no outstanding lookaside allocations for the database connection.
Hence, the configuration should be set immediately after creating the 
database connection using [sqlite3_open()] (or equivalent) and before
evaluating any SQL statements on the connection.</p>

<tcl>hd_fragment memstatus {memory statistics}</tcl>
<h3>3.5 Memory status</h3>

<p>By default, SQLite keeps statistics on its memory usage.  These
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 entering and leaving a mutex on each memory allocation
and deallocation.  That savings can be noticeable 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>

<p>The "onoff" parameter is true to enable the tracking of memory
statistics and false to disable statistics tracking.</p>

<p>Assuming statistics are enabled, the following routine can be used
to access them:</p>

<blockquote><pre>
[sqlite3_status]([SQLITE_STATUS_MEMORY_USED|verb], &amp;current, &amp;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>
[sqlite3_db_status](db, [SQLITE_DBSTATUS_LOOKASIDE_USED|verb], &amp;current, &amp;highwater, resetflag);
</pre></blockquote>

<p>This interface is similar except that it takes a pointer to
a [database connection] as its first argument and returns statistics about
that one object rather than about the entire SQLite library.
The [sqlite3_db_status()] interface currently only recognizes a
single verb [SQLITE_DBSTATUS_LOOKASIDE_USED], though additional verbs
may be added in the future.</p>

<p>The per-connection statistics do not use global variables and hence
do not require mutexes to update or access.  Consequently the
per-connection statistics continue to function even if
[SQLITE_CONFIG_MEMSTATUS] is turned off.</p>

<a name="heaplimit"></a>
<h3>3.6 Setting memory usage limits</h3>

<p>The [sqlite3_soft_heap_limit64()] interface can be used to set an
upper bound on the total amount of outstanding memory that the
general-purpose memory allocator for SQLite will allow to be outstanding
at one time.  If attempts are made to allocate more memory that specified
by the soft heap limit, then SQLite will first attempt to free cache
memory before continuing with the allocation request.  The soft heap
limit mechanism only works if [memory statistics] are enabled and
it works best
if the SQLite library is compiled with the [SQLITE_ENABLE_MEMORY_MANAGEMENT]
compile-time option.</p>

<p>The soft heap limit is "soft" in this sense:  If SQLite is not able
to free up enough auxiliary memory to stay below the limit, it goes
ahead and allocations the extra memory and exceeds its limit.  This occurs
under the theory that it is better to use additional memory than to fail
outright.</p>

<p>As of SQLite version 3.6.1, the soft heap limit only applies to the
general-purpose memory allocator.  The soft heap limit does not know
about or interact with the [scratch memory allocator], 
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
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 ever
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 [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 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> that 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 two
scratch memory slots at one time.  So if an application allocates twice 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 [cache_size pragma].</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 [sqlite3_open()] 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 [database connections]
as they are created.  In the common case, the application will only
have a single [database connection] 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
[memsys5] as large as possible.  In most applications, 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 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 [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>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
[sqlite3_blob | incremental BLOB I/O] and rows that contain the
large strings or BLOBs should never be update by any means other
than [sqlite3_blob | incremental BLOB I/O].  Otherwise, the 
[sqlite3_step()] 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 [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 experimentally 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
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 [memory statistics] 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><b>Update:</b> As of SQLite version 3.7.0 (2010-07-22), 
all of SQLite memory allocation interfaces
are considered stable and will be supported in future releases.</p>
