Documentation Source Text

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

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

<p>SQLite makes extensive use of dynamic memory allocation to obtain
the memory it needs to store 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, 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
................................................................................
<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>

<li><p>
<b>Memory usage limits.</b>
The [sqlite3_soft_heap_limit()] mechanism allows the application to
set a memory usage limit that SQLite strives to stay below.  SQLite
................................................................................
<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>

<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 definitely 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 sentinal values at both ends
of each memory allocation to verify that nothing within SQLite writes
................................................................................
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
insure 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 spotted and quinched.</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 application.  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 a 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 advice
one allocation at a time until the entire test procedure runs to
completion without hitting a memory allocation error.  This whole
................................................................................
strong evidence that dynamic memory allocation is used correctly
everywhere within SQLite.</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 are particularly
strict requirements may want to adjust the configuation to more closely
align SQLite to their needs.
Both compile-time and start-time configuration options are available.</p>

<a name="altalloc"></a>
<h3>3.1 Alternative low-level memory allocators</h3>

................................................................................

<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 implementation 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>

................................................................................
[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
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>

<a name="memsysx"></a>
<h4>3.1.4 Experimental memory allocators</h4>
................................................................................
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 release 3.6.1), but it has not been maintained for several release
cycles and probably does not work. Memsys4 was an attempt to use mmap()
to obtain memory for use and then use madvise() to release unused pages
back to the operating system so that they could be reused by other
processes.  The target platform for memsys4 was Google Android.  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
................................................................................
as temporary storage when rebalancing a btree.  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 stack approach 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>
................................................................................
[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>

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

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

<p>SQLite uses of 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, 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
................................................................................
<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 or other system
errors.
</p></li>

<li><p>
<b>Memory usage limits.</b>
The [sqlite3_soft_heap_limit()] mechanism allows the application to
set a memory usage limit that SQLite strives to stay below.  SQLite
................................................................................
<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 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 sentinal values at both ends
of each memory allocation to verify that nothing within SQLite writes
................................................................................
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
insure 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 a 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 advice
one allocation at a time until the entire test procedure runs to
completion without hitting a memory allocation error.  This whole
................................................................................
strong evidence that dynamic memory allocation is used correctly
everywhere within SQLite.</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 configuation to more closely
align SQLite to their needs.
Both compile-time and start-time configuration options are available.</p>

<a name="altalloc"></a>
<h3>3.1 Alternative low-level memory allocators</h3>

................................................................................

<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>

................................................................................
[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 memroy 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 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>

<a name="memsysx"></a>
<h4>3.1.4 Experimental memory allocators</h4>
................................................................................
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 release 3.6.1), but it has not been maintained for several release
cycles and probably does not work. 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 target platform for memsys4 was Google Android.  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
................................................................................
as temporary storage when rebalancing a btree.  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>
................................................................................
[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>