Adding upstream version 3.40.1.upstream/3.40.1 upstream

Signed-off-by: Daniel Baumann <daniel.baumann@progress-linux.org>
author: Daniel Baumann <daniel.baumann@progress-linux.org> 2024-05-05 17:28:19 +0000
committer: Daniel Baumann <daniel.baumann@progress-linux.org> 2024-05-05 17:28:19 +0000
commit: 18657a960e125336f704ea058e25c27bd3900dcb (patch)
tree: 17b438b680ed45a996d7b59951e6aa34023783f2 /www/malloc.html
parent: Initial commit. (diff)
download: sqlite3-18657a960e125336f704ea058e25c27bd3900dcb.tar.xz
sqlite3-18657a960e125336f704ea058e25c27bd3900dcb.zip
1 files changed, 1142 insertions, 0 deletions
diff --git a/www/malloc.html b/www/malloc.html
new file mode 100644
index 0000000..653f8d9
--- /dev/null
+++ b/www/malloc.html
@@ -0,0 +1,1142 @@
+<!DOCTYPE html>
+<html><head>
+<meta name="viewport" content="width=device-width, initial-scale=1.0">
+<meta http-equiv="content-type" content="text/html; charset=UTF-8">
+<link href="sqlite.css" rel="stylesheet">
+<title>Dynamic Memory Allocation In SQLite</title>
+<!-- path= -->
+</head>
+<body>
+<div class=nosearch>
+<a href="index.html">
+<img class="logo" src="images/sqlite370_banner.gif" alt="SQLite" border="0">
+</a>
+<div><!-- IE hack to prevent disappearing logo --></div>
+<div class="tagline desktoponly">
+Small. Fast. Reliable.<br>Choose any three.
+</div>
+<div class="menu mainmenu">
+<ul>
+<li><a href="index.html">Home</a>
+<li class='mobileonly'><a href="javascript:void(0)" onclick='toggle_div("submenu")'>Menu</a>
+<li class='wideonly'><a href='about.html'>About</a>
+<li class='desktoponly'><a href="docs.html">Documentation</a>
+<li class='desktoponly'><a href="download.html">Download</a>
+<li class='wideonly'><a href='copyright.html'>License</a>
+<li class='desktoponly'><a href="support.html">Support</a>
+<li class='desktoponly'><a href="prosupport.html">Purchase</a>
+<li class='search' id='search_menubutton'>
+<a href="javascript:void(0)" onclick='toggle_search()'>Search</a>
+</ul>
+</div>
+<div class="menu submenu" id="submenu">
+<ul>
+<li><a href='about.html'>About</a>
+<li><a href='docs.html'>Documentation</a>
+<li><a href='download.html'>Download</a>
+<li><a href='support.html'>Support</a>
+<li><a href='prosupport.html'>Purchase</a>
+</ul>
+</div>
+<div class="searchmenu" id="searchmenu">
+<form method="GET" action="search">
+<select name="s" id="searchtype">
+<option value="d">Search Documentation</option>
+<option value="c">Search Changelog</option>
+</select>
+<input type="text" name="q" id="searchbox" value="">
+<input type="submit" value="Go">
+</form>
+</div>
+</div>
+<script>
+function toggle_div(nm) {
+var w = document.getElementById(nm);
+if( w.style.display=="block" ){
+w.style.display = "none";
+}else{
+w.style.display = "block";
+}
+}
+function toggle_search() {
+var w = document.getElementById("searchmenu");
+if( w.style.display=="block" ){
+w.style.display = "none";
+} else {
+w.style.display = "block";
+setTimeout(function(){
+document.getElementById("searchbox").focus()
+}, 30);
+}
+}
+function div_off(nm){document.getElementById(nm).style.display="none";}
+window.onbeforeunload = function(e){div_off("submenu");}
+/* Disable the Search feature if we are not operating from CGI, since */
+/* Search is accomplished using CGI and will not work without it. */
+if( !location.origin || !location.origin.match || !location.origin.match(/http/) ){
+document.getElementById("search_menubutton").style.display = "none";
+}
+/* Used by the Hide/Show button beside syntax diagrams, to toggle the */
+function hideorshow(btn,obj){
+var x = document.getElementById(obj);
+var b = document.getElementById(btn);
+if( x.style.display!='none' ){
+x.style.display = 'none';
+b.innerHTML='show';
+}else{
+x.style.display = '';
+b.innerHTML='hide';
+}
+return false;
+}
+var antiRobot = 0;
+function antiRobotGo(){
+if( antiRobot!=3 ) return;
+antiRobot = 7;
+var j = document.getElementById("mtimelink");
+if(j && j.hasAttribute("data-href")) j.href=j.getAttribute("data-href");
+}
+function antiRobotDefense(){
+document.body.onmousedown=function(){
+antiRobot |= 2;
+antiRobotGo();
+document.body.onmousedown=null;
+}
+document.body.onmousemove=function(){
+antiRobot |= 2;
+antiRobotGo();
+document.body.onmousemove=null;
+}
+setTimeout(function(){
+antiRobot |= 1;
+antiRobotGo();
+}, 100)
+antiRobotGo();
+}
+antiRobotDefense();
+</script>
+<div class=fancy>
+<div class=nosearch>
+<div class="fancy_title">
+Dynamic Memory Allocation In SQLite
+</div>
+<div class="fancy_toc">
+<a onclick="toggle_toc()">
+<span class="fancy_toc_mark" id="toc_mk">&#x25ba;</span>
+Table Of Contents
+</a>
+<div id="toc_sub"><div class="fancy-toc1"><a href="#_features">1.  Features</a></div>
+<div class="fancy-toc1"><a href="#_testing">2.  Testing</a></div>
+<div class="fancy-toc2"><a href="#_use_of_reallocarray_">2.1.  Use of reallocarray()</a></div>
+<div class="fancy-toc1"><a href="#_configuration">3.  Configuration</a></div>
+<div class="fancy-toc2"><a href="#_alternative_low_level_memory_allocators">3.1.  Alternative low-level memory allocators</a></div>
+<div class="fancy-toc3"><a href="#the_default_memory_allocator">3.1.1. The default memory allocator</a></div>
+<div class="fancy-toc3"><a href="#the_debugging_memory_allocator">3.1.2. The debugging memory allocator</a></div>
+<div class="fancy-toc3"><a href="#the_win32_native_memory_allocator">3.1.3. The Win32 native memory allocator</a></div>
+<div class="fancy-toc3"><a href="#zero_malloc_memory_allocator">3.1.4. Zero-malloc memory allocator</a></div>
+<div class="fancy-toc3"><a href="#experimental_memory_allocators">3.1.5. Experimental memory allocators</a></div>
+<div class="fancy-toc3"><a href="#application_defined_memory_allocators">3.1.6. Application-defined memory allocators</a></div>
+<div class="fancy-toc3"><a href="#memory_allocator_overlays">3.1.7. Memory allocator overlays</a></div>
+<div class="fancy-toc3"><a href="#no_op_memory_allocator_stub">3.1.8. No-op memory allocator stub</a></div>
+<div class="fancy-toc2"><a href="#_page_cache_memory">3.2.  Page cache memory</a></div>
+<div class="fancy-toc2"><a href="#_lookaside_memory_allocator">3.3.  Lookaside memory allocator</a></div>
+<div class="fancy-toc3"><a href="#two_size_lookaside">3.3.1. Two-Size Lookaside</a></div>
+<div class="fancy-toc2"><a href="#_memory_status">3.4.  Memory status</a></div>
+<div class="fancy-toc2"><a href="#_setting_memory_usage_limits">3.5.  Setting memory usage limits</a></div>
+<div class="fancy-toc1"><a href="#_mathematical_guarantees_against_memory_allocation_failures">4.  Mathematical Guarantees Against Memory Allocation Failures</a></div>
+<div class="fancy-toc2"><a href="#_computing_and_controlling_parameters_m_and_n">4.1.  Computing and controlling parameters M and n</a></div>
+<div class="fancy-toc2"><a href="#_ductile_failure">4.2.  Ductile failure</a></div>
+<div class="fancy-toc1"><a href="#_stability_of_memory_interfaces">5.  Stability Of Memory Interfaces</a></div>
+</div>
+</div>
+<script>
+function toggle_toc(){
+var sub = document.getElementById("toc_sub")
+var mk = document.getElementById("toc_mk")
+if( sub.style.display!="block" ){
+sub.style.display = "block";
+mk.innerHTML = "&#x25bc;";
+} else {
+sub.style.display = "none";
+mk.innerHTML = "&#x25ba;";
+}
+}
+</script>
+</div>
+
+
+
+
+
+<h1 style="margin-left:1.0em" notoc="1" id="overview"> Overview</h1> 
+
+<p>SQLite uses dynamic memory allocation to obtain
+memory for storing various objects
+(ex: <a href="c3ref/sqlite3.html">database connections</a> and <a href="c3ref/stmt.html">prepared statements</a>) 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>
+<h1 id="_features"><span>1. </span> Features</h1>
+
+<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
+<a href="rescode.html#nomem">SQLITE_NOMEM</a> 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 <a href="c3ref/finalize.html">sqlite3_finalize()</a> on 
+every <a href="c3ref/stmt.html">prepared statement</a> and <a href="c3ref/close.html">sqlite3_close()</a> on every 
+<a href="c3ref/sqlite3.html">database connection</a>.)   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 <a href="c3ref/hard_heap_limit64.html">sqlite3_soft_heap_limit64()</a> 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 <a href="http://dmalloc.com">dmalloc</a> or 
+<a href="http://valgrind.org">valgrind</a>) can be used to verify correct
+memory allocation behavior.</p>
+
+</li><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
+<a href="c3ref/free.html">sqlite3_malloc()</a>, <a href="c3ref/free.html">sqlite3_realloc()</a>, and <a href="c3ref/free.html">sqlite3_free()</a> interfaces.
+</p></li>
+
+</ul>
+
+<a name="testing"></a>
+<h1 id="_testing"><span>2. </span> Testing</h1>
+
+<p>Most of the code in the SQLite source tree is devoted purely to 
+<a href="testing.html">testing and verification</a>.  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 <a href="compile.html#memdebug">SQLITE_MEMDEBUG</a> 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 <a href="testing.html#tcl">TCL test suite</a> provides over 99% statement test coverage and that
+the <a href="th3.html">TH3</a> test harness provides <a href="testing.html#coverage">100% branch test coverage</a>
+with no leak leaks. This is
+strong evidence that dynamic memory allocation is used correctly
+everywhere within SQLite.</p>
+
+<a name="allocarray"></a>
+<h2 id="_use_of_reallocarray_"><span>2.1. </span> Use of reallocarray()</h2>
+
+<p>The reallocarray() interface is a recent innovation (circa 2014)
+from the OpenBSD community that grow out of efforts to prevent the
+next <a href="http://heartbleed.com">"heartbleed" bug</a> 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>
+<h1 id="_configuration"><span>3. </span> Configuration</h1>
+
+<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>
+
+<a name="altalloc"></a>
+
+<h2 id="_alternative_low_level_memory_allocators"><span>3.1. </span> Alternative low-level memory allocators</h2>
+
+<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>
+
+<a name="defaultalloc"></a>
+
+<h3 id="the_default_memory_allocator"><span>3.1.1. </span>The default memory allocator</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>
+
+<a name="memdebug"></a>
+
+<h3 id="the_debugging_memory_allocator"><span>3.1.2. </span>The debugging memory allocator</h3>
+
+<p>If SQLite is compiled with the <a href="compile.html#memdebug">SQLITE_MEMDEBUG</a> 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 <a href="compile.html#memdebug">SQLITE_MEMDEBUG</a> 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 <a href="compile.html#memdebug">SQLITE_MEMDEBUG</a> 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>
+
+<a name="win32heap"></a>
+
+<h3 id="the_win32_native_memory_allocator"><span>3.1.3. </span>The Win32 native memory allocator</h3>
+
+<p>If SQLite is compiled for Windows with the <a href="compile.html#win32_malloc">SQLITE_WIN32_MALLOC</a>
+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 <a href="compile.html#win32_heap_create">SQLITE_WIN32_HEAP_CREATE</a> 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
+<a href="compile.html#win32_malloc_validate">SQLITE_WIN32_MALLOC_VALIDATE</a> compile-time option.</p>
+
+<a name="memsys5"></a>
+
+<h3 id="zero_malloc_memory_allocator"><span>3.1.4. </span>Zero-malloc memory allocator</h3>
+
+<p>When SQLite is compiled with the <a href="compile.html#enable_memsys5">SQLITE_ENABLE_MEMSYS5</a> 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>
+<a href="c3ref/config.html">sqlite3_config</a>(<a href="c3ref/c_config_covering_index_scan.html#sqliteconfigheap">SQLITE_CONFIG_HEAP</a>, 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 <a href="c3ref/free.html">sqlite3_malloc(N)</a> 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 <a href="malloc.html#nofrag">Robson proof</a>.</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>
+
+<a name="memsysx"></a>
+
+<h3 id="experimental_memory_allocators"><span>3.1.5. </span>Experimental memory allocators</h3>
+
+<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 <a href="compile.html#enable_memsys3">SQLITE_ENABLE_MEMSYS3</a> 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 <a href="c3ref/config.html">sqlite3_config</a>(<a href="c3ref/c_config_covering_index_scan.html#sqliteconfigheap">SQLITE_CONFIG_HEAP</a>,...).  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>Memsys4 and memsys6 were experimental memory allocators
+introduced in around 2007 and subsequently removed from the
+source tree in around 2008, after it became clear that they
+added no new value.</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>
+<h3 id="application_defined_memory_allocators"><span>3.1.6. </span>Application-defined memory allocators</h3>
+
+<p>New memory allocators do not have to be part of the SQLite source tree
+nor included in the sqlite3.c <a href="amalgamation.html">amalgamation</a>.  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>
+<a href="c3ref/config.html">sqlite3_config</a>(<a href="c3ref/c_config_covering_index_scan.html#sqliteconfigmalloc">SQLITE_CONFIG_MALLOC</a>, pMem);
+</pre></blockquote>
+
+<p>In the call above, pMem is a pointer to an <a href="c3ref/mem_methods.html">sqlite3_mem_methods</a> object
+that defines the interface to the application-specific memory allocator.
+The <a href="c3ref/mem_methods.html">sqlite3_mem_methods</a> 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 <a href="c3ref/mem_methods.html">sqlite3_mem_methods</a>
+is serialized if and only if <a href="c3ref/c_config_covering_index_scan.html#sqliteconfigmemstatus">SQLITE_CONFIG_MEMSTATUS</a> is enabled.
+If <a href="c3ref/c_config_covering_index_scan.html#sqliteconfigmemstatus">SQLITE_CONFIG_MEMSTATUS</a> is disabled then the methods in
+<a href="c3ref/mem_methods.html">sqlite3_mem_methods</a> must take care of their own serialization needs.</p>
+
+<a name="overlayalloc"></a>
+<h3 id="memory_allocator_overlays"><span>3.1.7. </span>Memory allocator overlays</h3>
+
+<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>
+<a href="c3ref/config.html">sqlite3_config</a>(<a href="c3ref/c_config_covering_index_scan.html#sqliteconfiggetmalloc">SQLITE_CONFIG_GETMALLOC</a>, 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 <a href="c3ref/config.html">sqlite3_config</a>(<a href="c3ref/c_config_covering_index_scan.html#sqliteconfigmalloc">SQLITE_CONFIG_MALLOC</a>,...) as described
+<a href="#appalloc">above</a>.
+
+<a name="stuballoc"></a>
+</p><h3 id="no_op_memory_allocator_stub"><span>3.1.8. </span>No-op memory allocator stub</h3>
+
+<p>If SQLite is compiled with the <a href="compile.html#zero_malloc">SQLITE_ZERO_MALLOC</a> option, then
+the <a href="malloc.html#defaultalloc">default memory allocator</a> 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 <a href="compile.html#zero_malloc">SQLITE_ZERO_MALLOC</a> will need to
+use <a href="c3ref/config.html">sqlite3_config()</a> together with <a href="c3ref/c_config_covering_index_scan.html#sqliteconfigmalloc">SQLITE_CONFIG_MALLOC</a> or
+<a href="c3ref/c_config_covering_index_scan.html#sqliteconfigheap">SQLITE_CONFIG_HEAP</a> to specify a new alternative memory allocator
+before beginning to use SQLite.</p>
+
+<a name="pagecache"></a>
+
+<h2 id="_page_cache_memory"><span>3.2. </span> Page cache memory</h2>
+
+<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
+consume 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
+<a href="malloc.html#nofrag">Robson proof</a> 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>
+<a href="c3ref/config.html">sqlite3_config</a>(<a href="c3ref/c_config_covering_index_scan.html#sqliteconfigpagecache">SQLITE_CONFIG_PAGECACHE</a>, 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>
+
+<a name="lookaside"></a>
+
+<h2 id="_lookaside_memory_allocator"><span>3.3. </span> Lookaside memory allocator</h2>
+
+<p>SQLite <a href="c3ref/sqlite3.html">database connections</a> make many
+small and short-lived memory allocations.
+This occurs most commonly when compiling SQL statements using
+<a href="c3ref/prepare.html">sqlite3_prepare_v2()</a> but also to a lesser extent when running
+<a href="c3ref/stmt.html">prepared statements</a> using <a href="c3ref/step.html">sqlite3_step()</a>.  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 <a href="releaselog/3_6_1.html">version 3.6.1</a> (2008-08-06)
+introduced the lookaside memory allocator to
+help reduce the memory allocation load.  In the lookaside allocator,
+each <a href="c3ref/sqlite3.html">database connection</a> preallocates a single large chunk of memory
+(typically in the range of 60 to 120 kilobytes) and divides that chunk
+up into small fixed-size "slots" of around 100 to 1000 byte each.  This
+becomes the lookaside memory pool.  Thereafter, memory allocations
+associated with the <a href="c3ref/sqlite3.html">database connection</a> and that are not too large
+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 <a href="c3ref/sqlite3.html">database connection</a> 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 <a href="c3ref/sqlite3.html">database connection</a> 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
+and 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 at
+compile-time, use the 
+<a href="compile.html#default_lookaside">-DSQLITE_DEFAULT_LOOKASIDE=<i>SZ,N</i></a>
+option.
+To change the default size of the lookaside memory pool at
+start-time, use the <a href="c3ref/config.html">sqlite3_config()</a> interface:</p>
+
+<blockquote><pre>
+<a href="c3ref/config.html">sqlite3_config</a>(<a href="c3ref/c_config_covering_index_scan.html#sqliteconfiglookaside">SQLITE_CONFIG_LOOKASIDE</a>, sz, cnt);
+</pre></blockquote>
+
+<p>The "sz" parameter is the size in bytes of each lookaside slot.
+The "cnt" parameter is
+the total number of lookaside memory slots per database connection.
+The total amount
+of lookaside memory allocated to each <a href="c3ref/sqlite3.html">database connection</a> is
+sz*cnt bytes. 
+</p>
+
+<p>The lookaside pool can be changed for an individual
+<a href="c3ref/sqlite3.html">database connection</a> "db" using this call:</p>
+
+<blockquote><pre>
+<a href="c3ref/db_config.html">sqlite3_db_config</a>(db, <a href="c3ref/c_dbconfig_defensive.html#sqlitedbconfiglookaside">SQLITE_DBCONFIG_LOOKASIDE</a>, 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 <a href="c3ref/free.html">sqlite3_malloc()</a>.
+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 <a href="c3ref/open.html">sqlite3_open()</a> (or equivalent) and before
+evaluating any SQL statements on the connection.</p>
+
+<h3 id="two_size_lookaside"><span>3.3.1. </span>Two-Size Lookaside</h3>
+
+<p>
+Beginning with SQLite version 3.31.0 (2020-01-22),
+lookaside supports two memory pools, each with a different size
+slot.  The small-slot pool uses 128-byte slots and the large-slot
+pool uses whatever size is specified by <a href="c3ref/c_dbconfig_defensive.html#sqlitedbconfiglookaside">SQLITE_DBCONFIG_LOOKASIDE</a>
+(defaulting to 1200 bytes).  Splitting the pool in two like this
+allows memory allocations to be covered by lookaside more often
+while at the same time reducing per-database-connection heap usage
+from 120KB down to 48KB.
+
+</p><p>
+Configuration continues to use the SQLITE_DBCONFIG_LOOKASIDE or
+SQLITE_CONFIG_LOOKASIDE configuration options, as described above,
+with parameters "sz" and "cnt".  The total heap space used for
+lookaside continues to be sz*cnt bytes.  But the space is allocated
+between the small-slot lookaside and big-slot lookaside, with
+preference given to small-slot lookaside.  The total number of
+slots will usually exceed "cnt", since "sz" is typically much
+larger than the small-slot size of 128 bytes.
+
+</p><p>
+The default lookaside configuration has changed from 100 slots
+of 1200 bytes each (120KB) to be 40 slots of 1200 bytes each
+(48KB).  This space ends up being allocated as 93 slots of
+128 bytes each and 30 slots of 1200 bytes each.  So more lookaside
+slots are available but much less heap space is used.
+
+</p><p>
+The default lookaside configuration, the size of the small-slots,
+and the details of how heap space is allocated between small-slots
+and big-slots, are all subject to change from one release to the
+next.
+
+
+<a name="memstatus"></a>
+
+</p><h2 id="_memory_status"><span>3.4. </span> Memory status</h2>
+
+<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 <a href="malloc.html#nofrag">Robson proof</a> 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>
+<a href="c3ref/config.html">sqlite3_config</a>(<a href="c3ref/c_config_covering_index_scan.html#sqliteconfigmemstatus">SQLITE_CONFIG_MEMSTATUS</a>, 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>
+<a href="c3ref/status.html">sqlite3_status</a>(<a href="c3ref/c_status_malloc_count.html#sqlitestatusmemoryused">verb</a>, &amp;current, &amp;highwater, resetflag);
+</pre></blockquote>
+
+<p>The "verb" argument determines what statistic is accessed.
+There are <a href="c3ref/c_status_malloc_count.html#sqlitestatusmemoryused">various verbs</a> defined.  The
+list is expected to grow as the <a href="c3ref/status.html">sqlite3_status()</a> 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 <a href="c3ref/sqlite3.html">database connection</a>:</p>
+
+<blockquote><pre>
+<a href="c3ref/db_status.html">sqlite3_db_status</a>(db, <a href="c3ref/c_dbstatus_options.html#sqlitedbstatuslookasideused">verb</a>, &amp;current, &amp;highwater, resetflag);
+</pre></blockquote>
+
+<p>This interface is similar except that it takes a pointer to
+a <a href="c3ref/sqlite3.html">database connection</a> as its first argument and returns statistics about
+that one object rather than about the entire SQLite library.
+The <a href="c3ref/db_status.html">sqlite3_db_status()</a> interface currently only recognizes a
+single verb <a href="c3ref/c_dbstatus_options.html#sqlitedbstatuslookasideused">SQLITE_DBSTATUS_LOOKASIDE_USED</a>, 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
+<a href="c3ref/c_config_covering_index_scan.html#sqliteconfigmemstatus">SQLITE_CONFIG_MEMSTATUS</a> is turned off.</p>
+
+<a name="heaplimit"></a>
+<h2 id="_setting_memory_usage_limits"><span>3.5. </span> Setting memory usage limits</h2>
+
+<p>The <a href="c3ref/hard_heap_limit64.html">sqlite3_soft_heap_limit64()</a> 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 than 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 <a href="malloc.html#memstatus">memory statistics</a> are enabled and
+it works best
+if the SQLite library is compiled with the <a href="compile.html#enable_memory_management">SQLITE_ENABLE_MEMORY_MANAGEMENT</a>
+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 allocates 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 <a href="releaselog/3_6_1.html">version 3.6.1</a> (2008-08-06), 
+the soft heap limit only applies to the
+general-purpose memory allocator.  The soft heap limit does not know
+about or interact with
+the <a href="malloc.html#pagecache">pagecache memory allocator</a> or the <a href="malloc.html#lookaside">lookaside memory allocator</a>.
+This deficiency will likely be addressed in a future release.</p>
+
+<a name="nofrag"></a>
+
+<h1 id="_mathematical_guarantees_against_memory_allocation_failures"><span>4. </span> Mathematical Guarantees Against Memory Allocation Failures</h1>
+
+<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 <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_covering_index_scan.html#sqliteconfigheap">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="rescode.html#nomem">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>
+
+<h2 id="_computing_and_controlling_parameters_m_and_n"><span>4.1. </span> Computing and controlling parameters <b>M</b> and <b>n</b></h2>
+
+<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#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>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>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 two allocations can be controlled and/or eliminated by
+configuring the <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 6
+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_count.html#sqlitestatusmemoryused">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>
+
+<h2 id="_ductile_failure"><span>4.2. </span> Ductile failure</h2>
+
+<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#pagecache">pagecache memory allocator</a>
+and the <a href="malloc.html#lookaside">lookaside memory allocator</a> 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>
+<h1 id="_stability_of_memory_interfaces"><span>5. </span> Stability Of Memory Interfaces</h1>
+
+<p><b>Update:</b> As of SQLite version 3.7.0 (2010-07-21), 
+all of SQLite memory allocation interfaces
+are considered stable and will be supported in future releases.</p>
+<p align="center"><small><i>This page last modified on  <a href="https://sqlite.org/docsrc/honeypot" id="mtimelink"  data-href="https://sqlite.org/docsrc/finfo/pages/malloc.in?m=fc088f2b1c81a009c">2022-01-28 19:28:24</a> UTC </small></i></p>
+
author	Daniel Baumann <daniel.baumann@progress-linux.org>	2024-05-05 17:28:19 +0000
committer	Daniel Baumann <daniel.baumann@progress-linux.org>	2024-05-05 17:28:19 +0000
commit	18657a960e125336f704ea058e25c27bd3900dcb (patch)
tree	17b438b680ed45a996d7b59951e6aa34023783f2 /www/malloc.html
parent	Initial commit. (diff)
download	sqlite3-18657a960e125336f704ea058e25c27bd3900dcb.tar.xz sqlite3-18657a960e125336f704ea058e25c27bd3900dcb.zip