diff options
Diffstat (limited to 'www/malloc.html')
| -rw-r--r-- | www/malloc.html | 1142 |
1 files changed, 1142 insertions, 0 deletions
diff --git a/www/malloc.html b/www/malloc.html new file mode 100644 index 0000000..2aa73fa --- /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">►</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 = "▼"; +} else { +sub.style.display = "none"; +mk.innerHTML = "►"; +} +} +</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>, &current, &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>, &current, &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=fc088f2b1c">2022-04-18 02:55:50</a> UTC </small></i></p> + |