| 1 |
<!DOCTYPE html> |
| 2 |
<html><head> |
| 3 |
<meta name="viewport" content="width=device-width, initial-scale=1.0"> |
| 4 |
<meta http-equiv="content-type" content="text/html; charset=UTF-8"> |
| 5 |
<link href="sqlite.css" rel="stylesheet"> |
| 6 |
<title>Dynamic Memory Allocation In SQLite</title> |
| 7 |
<!-- path= --> |
| 8 |
</head> |
| 9 |
<body> |
| 10 |
<div class=nosearch> |
| 11 |
<a href="index.html"> |
| 12 |
<img class="logo" src="images/sqlite370_banner.svg" alt="SQLite" border="0"> |
| 13 |
</a> |
| 14 |
<div><!-- IE hack to prevent disappearing logo --></div> |
| 15 |
<div class="tagline desktoponly"> |
| 16 |
Small. Fast. Reliable.<br>Choose any three. |
| 17 |
</div> |
| 18 |
<div class="menu mainmenu"> |
| 19 |
<ul> |
| 20 |
<li><a href="index.html">Home</a> |
| 21 |
<li class='mobileonly'><a href="javascript:void(0)" onclick='toggle_div("submenu")'>Menu</a> |
| 22 |
<li class='wideonly'><a href='about.html'>About</a> |
| 23 |
<li class='desktoponly'><a href="docs.html">Documentation</a> |
| 24 |
<li class='desktoponly'><a href="download.html">Download</a> |
| 25 |
<li class='wideonly'><a href='copyright.html'>License</a> |
| 26 |
<li class='desktoponly'><a href="support.html">Support</a> |
| 27 |
<li class='desktoponly'><a href="prosupport.html">Purchase</a> |
| 28 |
<li class='search' id='search_menubutton'> |
| 29 |
<a href="javascript:void(0)" onclick='toggle_search()'>Search</a> |
| 30 |
</ul> |
| 31 |
</div> |
| 32 |
<div class="menu submenu" id="submenu"> |
| 33 |
<ul> |
| 34 |
<li><a href='about.html'>About</a> |
| 35 |
<li><a href='docs.html'>Documentation</a> |
| 36 |
<li><a href='download.html'>Download</a> |
| 37 |
<li><a href='support.html'>Support</a> |
| 38 |
<li><a href='prosupport.html'>Purchase</a> |
| 39 |
</ul> |
| 40 |
</div> |
| 41 |
<div class="searchmenu" id="searchmenu"> |
| 42 |
<form method="GET" action="search"> |
| 43 |
<select name="s" id="searchtype"> |
| 44 |
<option value="d">Search Documentation</option> |
| 45 |
<option value="c">Search Changelog</option> |
| 46 |
</select> |
| 47 |
<input type="text" name="q" id="searchbox" value=""> |
| 48 |
<input type="submit" value="Go"> |
| 49 |
</form> |
| 50 |
</div> |
| 51 |
</div> |
| 52 |
<script> |
| 53 |
function toggle_div(nm) { |
| 54 |
var w = document.getElementById(nm); |
| 55 |
if( w.style.display=="block" ){ |
| 56 |
w.style.display = "none"; |
| 57 |
}else{ |
| 58 |
w.style.display = "block"; |
| 59 |
} |
| 60 |
} |
| 61 |
function toggle_search() { |
| 62 |
var w = document.getElementById("searchmenu"); |
| 63 |
if( w.style.display=="block" ){ |
| 64 |
w.style.display = "none"; |
| 65 |
} else { |
| 66 |
w.style.display = "block"; |
| 67 |
setTimeout(function(){ |
| 68 |
document.getElementById("searchbox").focus() |
| 69 |
}, 30); |
| 70 |
} |
| 71 |
} |
| 72 |
function div_off(nm){document.getElementById(nm).style.display="none";} |
| 73 |
window.onbeforeunload = function(e){div_off("submenu");} |
| 74 |
/* Disable the Search feature if we are not operating from CGI, since */ |
| 75 |
/* Search is accomplished using CGI and will not work without it. */ |
| 76 |
if( !location.origin || !location.origin.match || !location.origin.match(/http/) ){ |
| 77 |
document.getElementById("search_menubutton").style.display = "none"; |
| 78 |
} |
| 79 |
/* Used by the Hide/Show button beside syntax diagrams, to toggle the */ |
| 80 |
function hideorshow(btn,obj){ |
| 81 |
var x = document.getElementById(obj); |
| 82 |
var b = document.getElementById(btn); |
| 83 |
if( x.style.display!='none' ){ |
| 84 |
x.style.display = 'none'; |
| 85 |
b.innerHTML='show'; |
| 86 |
}else{ |
| 87 |
x.style.display = ''; |
| 88 |
b.innerHTML='hide'; |
| 89 |
} |
| 90 |
return false; |
| 91 |
} |
| 92 |
var antiRobot = 0; |
| 93 |
function antiRobotGo(){ |
| 94 |
if( antiRobot!=3 ) return; |
| 95 |
antiRobot = 7; |
| 96 |
var j = document.getElementById("mtimelink"); |
| 97 |
if(j && j.hasAttribute("data-href")) j.href=j.getAttribute("data-href"); |
| 98 |
} |
| 99 |
function antiRobotDefense(){ |
| 100 |
document.body.onmousedown=function(){ |
| 101 |
antiRobot |= 2; |
| 102 |
antiRobotGo(); |
| 103 |
document.body.onmousedown=null; |
| 104 |
} |
| 105 |
document.body.onmousemove=function(){ |
| 106 |
antiRobot |= 2; |
| 107 |
antiRobotGo(); |
| 108 |
document.body.onmousemove=null; |
| 109 |
} |
| 110 |
setTimeout(function(){ |
| 111 |
antiRobot |= 1; |
| 112 |
antiRobotGo(); |
| 113 |
}, 100) |
| 114 |
antiRobotGo(); |
| 115 |
} |
| 116 |
antiRobotDefense(); |
| 117 |
</script> |
| 118 |
<div class=fancy> |
| 119 |
<div class=nosearch> |
| 120 |
<div class="fancy_title"> |
| 121 |
Dynamic Memory Allocation In SQLite |
| 122 |
</div> |
| 123 |
<details class="fancy_toc"> |
| 124 |
<summary>Table Of Contents</summary> |
| 125 |
<div id="toc_sub"><div class="fancy-toc1"><a href="#_features">1. Features</a></div> |
| 126 |
<div class="fancy-toc1"><a href="#_testing">2. Testing</a></div> |
| 127 |
<div class="fancy-toc2"><a href="#_use_of_reallocarray_">2.1. Use of reallocarray()</a></div> |
| 128 |
<div class="fancy-toc1"><a href="#_configuration">3. Configuration</a></div> |
| 129 |
<div class="fancy-toc2"><a href="#_alternative_low_level_memory_allocators">3.1. Alternative low-level memory allocators</a></div> |
| 130 |
<div class="fancy-toc3"><a href="#the_default_memory_allocator">3.1.1. The default memory allocator</a></div> |
| 131 |
<div class="fancy-toc3"><a href="#the_debugging_memory_allocator">3.1.2. The debugging memory allocator</a></div> |
| 132 |
<div class="fancy-toc3"><a href="#the_win32_native_memory_allocator">3.1.3. The Win32 native memory allocator</a></div> |
| 133 |
<div class="fancy-toc3"><a href="#zero_malloc_memory_allocator">3.1.4. Zero-malloc memory allocator</a></div> |
| 134 |
<div class="fancy-toc3"><a href="#experimental_memory_allocators">3.1.5. Experimental memory allocators</a></div> |
| 135 |
<div class="fancy-toc3"><a href="#application_defined_memory_allocators">3.1.6. Application-defined memory allocators</a></div> |
| 136 |
<div class="fancy-toc3"><a href="#memory_allocator_overlays">3.1.7. Memory allocator overlays</a></div> |
| 137 |
<div class="fancy-toc3"><a href="#no_op_memory_allocator_stub">3.1.8. No-op memory allocator stub</a></div> |
| 138 |
<div class="fancy-toc2"><a href="#_page_cache_memory">3.2. Page cache memory</a></div> |
| 139 |
<div class="fancy-toc2"><a href="#_lookaside_memory_allocator">3.3. Lookaside memory allocator</a></div> |
| 140 |
<div class="fancy-toc3"><a href="#two_size_lookaside">3.3.1. Two-Size Lookaside</a></div> |
| 141 |
<div class="fancy-toc2"><a href="#_memory_status">3.4. Memory status</a></div> |
| 142 |
<div class="fancy-toc2"><a href="#_setting_memory_usage_limits">3.5. Setting memory usage limits</a></div> |
| 143 |
<div class="fancy-toc1"><a href="#_mathematical_guarantees_against_memory_allocation_failures">4. Mathematical Guarantees Against Memory Allocation Failures</a></div> |
| 144 |
<div class="fancy-toc2"><a href="#_computing_and_controlling_parameters_m_and_n">4.1. Computing and controlling parameters M and n</a></div> |
| 145 |
<div class="fancy-toc2"><a href="#_ductile_failure">4.2. Ductile failure</a></div> |
| 146 |
<div class="fancy-toc1"><a href="#_stability_of_memory_interfaces">5. Stability Of Memory Interfaces</a></div> |
| 147 |
</div> |
| 148 |
</details> |
| 149 |
</div> |
| 150 |
|
| 151 |
|
| 152 |
|
| 153 |
|
| 154 |
|
| 155 |
<h1 style="margin-left:1.0em" notoc="1" id="overview"> Overview</h1> |
| 156 |
|
| 157 |
<p>SQLite uses dynamic memory allocation to obtain |
| 158 |
memory for storing various objects |
| 159 |
(ex: <a href="c3ref/sqlite3.html">database connections</a> and <a href="c3ref/stmt.html">prepared statements</a>) and to build |
| 160 |
a memory cache of the database file and to hold the results of queries. |
| 161 |
Much effort has gone into making the dynamic memory allocation subsystem |
| 162 |
of SQLite reliable, predictable, robust, secure, and efficient.</p> |
| 163 |
|
| 164 |
<p>This document provides an overview of dynamic memory allocation within |
| 165 |
SQLite. The target audience is software engineers who are tuning their |
| 166 |
use of SQLite for peak performance in demanding environments. |
| 167 |
Nothing in this document is required knowledge for using SQLite. The |
| 168 |
default settings and configuration for SQLite will work well in most |
| 169 |
applications. However, the information contained in this document may |
| 170 |
be useful to engineers who are tuning SQLite to comply with special |
| 171 |
requirements or to run under unusual circumstances.</p> |
| 172 |
|
| 173 |
<a name="features"></a> |
| 174 |
<h1 id="_features"><span>1. </span> Features</h1> |
| 175 |
|
| 176 |
<p>The SQLite core and its memory allocation subsystem provides the |
| 177 |
following capabilities:</p> |
| 178 |
|
| 179 |
<ul> |
| 180 |
<li><p> |
| 181 |
<b>Robust against allocation failures.</b> |
| 182 |
If a memory allocation ever fails (that is to say, |
| 183 |
if malloc() or realloc() ever return NULL) |
| 184 |
then SQLite will recover gracefully. SQLite will first attempt |
| 185 |
to free memory from unpinned cache pages then retry the allocation |
| 186 |
request. |
| 187 |
Failing that, SQLite will either stop what |
| 188 |
it is doing and return the |
| 189 |
<a href="rescode.html#nomem">SQLITE_NOMEM</a> error code back up to the application or it will |
| 190 |
make do without the requested memory. |
| 191 |
</p></li> |
| 192 |
|
| 193 |
<li><p> |
| 194 |
<b>No memory leaks.</b> |
| 195 |
The application is responsible for destroying any objects it allocates. |
| 196 |
(For example, the application must use <a href="c3ref/finalize.html">sqlite3_finalize()</a> on |
| 197 |
every <a href="c3ref/stmt.html">prepared statement</a> and <a href="c3ref/close.html">sqlite3_close()</a> on every |
| 198 |
<a href="c3ref/sqlite3.html">database connection</a>.) But as long as |
| 199 |
the application cooperates, SQLite will never leak memory. This is |
| 200 |
true even in the face of memory allocation failures or other system |
| 201 |
errors. |
| 202 |
</p></li> |
| 203 |
|
| 204 |
<li><p> |
| 205 |
<b>Memory usage limits.</b> |
| 206 |
The <a href="c3ref/hard_heap_limit64.html">sqlite3_soft_heap_limit64()</a> mechanism allows the application to |
| 207 |
set a memory usage limit that SQLite strives to stay below. SQLite |
| 208 |
will attempt to reuse memory from its caches rather than allocating new |
| 209 |
memory as it approaches the soft limit. |
| 210 |
</p></li> |
| 211 |
|
| 212 |
<li><p> |
| 213 |
<b>Zero-malloc option.</b> |
| 214 |
The application can optionally provide SQLite with several buffers of bulk memory |
| 215 |
at startup and SQLite will then use those provided buffers for all of |
| 216 |
its memory allocation needs and never call system malloc() or free(). |
| 217 |
</p></li> |
| 218 |
|
| 219 |
<li><p> |
| 220 |
<b>Application-supplied memory allocators.</b> |
| 221 |
The application can provide SQLite with pointers to alternative |
| 222 |
memory allocators at start-time. The alternative memory allocator |
| 223 |
will be used in place of system malloc() and free(). |
| 224 |
</p></li> |
| 225 |
|
| 226 |
<li><p> |
| 227 |
<b>Proof against breakdown and fragmentation.</b> |
| 228 |
SQLite can be configured so that, subject to certain usage constraints |
| 229 |
detailed below, it is guaranteed to never fail a memory allocation |
| 230 |
or fragment the heap. |
| 231 |
This property is important to long-running, high-reliability |
| 232 |
embedded systems where a memory allocation error could contribute |
| 233 |
to an overall system failure. |
| 234 |
</p></li> |
| 235 |
|
| 236 |
<li><p> |
| 237 |
<b>Memory usage statistics.</b> |
| 238 |
Applications can see how much memory they are using and detect when |
| 239 |
memory usage is approaching or exceeding design boundaries. |
| 240 |
</p></li> |
| 241 |
|
| 242 |
<a name="pwwo"></a> |
| 243 |
<li><p> |
| 244 |
<b>Plays well with memory debuggers.</b> |
| 245 |
Memory allocation in SQLite is structured so that standard |
| 246 |
third-party memory debuggers (such as <a href="http://dmalloc.com">dmalloc</a> or |
| 247 |
<a href="http://valgrind.org">valgrind</a>) can be used to verify correct |
| 248 |
memory allocation behavior.</p> |
| 249 |
|
| 250 |
</li><li><p> |
| 251 |
<b>Minimal calls to the allocator.</b> |
| 252 |
The system malloc() and free() implementations are inefficient |
| 253 |
on many systems. SQLite strives to reduce overall processing time |
| 254 |
by minimizing its use of malloc() and free(). |
| 255 |
</p></li> |
| 256 |
|
| 257 |
<li><p> |
| 258 |
<b>Open access.</b> |
| 259 |
Pluggable SQLite extensions or even the application itself can |
| 260 |
access to the same underlying memory allocation |
| 261 |
routines used by SQLite through the |
| 262 |
<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. |
| 263 |
</p></li> |
| 264 |
|
| 265 |
</ul> |
| 266 |
|
| 267 |
<a name="testing"></a> |
| 268 |
<h1 id="_testing"><span>2. </span> Testing</h1> |
| 269 |
|
| 270 |
<p>Most of the code in the SQLite source tree is devoted purely to |
| 271 |
<a href="testing.html">testing and verification</a>. Reliability is important to SQLite. |
| 272 |
Among the tasks of the test infrastructure is to ensure that |
| 273 |
SQLite does not misuse dynamically allocated memory, that SQLite |
| 274 |
does not leak memory, and that SQLite responds |
| 275 |
correctly to a dynamic memory allocation failure.</p> |
| 276 |
|
| 277 |
<p>The test infrastructure verifies that SQLite does not misuse |
| 278 |
dynamically allocated memory by using a specially instrumented |
| 279 |
memory allocator. The instrumented memory allocator is enabled |
| 280 |
at compile-time using the <a href="compile.html#memdebug">SQLITE_MEMDEBUG</a> option. The instrumented |
| 281 |
memory allocator is much slower than the default memory allocator and |
| 282 |
so its use is not recommended in production. But when |
| 283 |
enabled during testing, |
| 284 |
the instrumented memory allocator performs the following checks:</p> |
| 285 |
|
| 286 |
<ul> |
| 287 |
<li><p><b>Bounds checking.</b> |
| 288 |
The instrumented memory allocator places sentinel values at both ends |
| 289 |
of each memory allocation to verify that nothing within SQLite writes |
| 290 |
outside the bounds of the allocation.</p></li> |
| 291 |
|
| 292 |
<li><p><b>Use of memory after freeing.</b> |
| 293 |
When each block of memory is freed, every byte is overwritten with a |
| 294 |
nonsense bit pattern. This helps to ensure that no memory is ever |
| 295 |
used after having been freed.</p></li> |
| 296 |
|
| 297 |
<li><p><b>Freeing memory not obtained from malloc.</b> |
| 298 |
Each memory allocation from the instrumented memory allocator contains |
| 299 |
sentinels used to verify that every allocation freed came |
| 300 |
from prior malloc.</p></li> |
| 301 |
|
| 302 |
<li><p><b>Uninitialized memory.</b> |
| 303 |
The instrumented memory allocator initializes each memory allocation |
| 304 |
to a nonsense bit pattern to help ensure that the user makes no |
| 305 |
assumptions about the content of allocation memory.</p></li> |
| 306 |
</ul> |
| 307 |
|
| 308 |
<p>Regardless of whether or not the instrumented memory allocator is |
| 309 |
used, SQLite keeps track of how much memory is currently checked out. |
| 310 |
There are hundreds of test scripts used for testing SQLite. At the |
| 311 |
end of each script, all objects are destroyed and a test is made to |
| 312 |
ensure that all memory has been freed. This is how memory |
| 313 |
leaks are detected. Notice that memory leak detection is in force at |
| 314 |
all times, during test builds and during production builds. Whenever |
| 315 |
one of the developers runs any individual test script, memory leak |
| 316 |
detection is active. Hence memory leaks that do arise during development |
| 317 |
are quickly detected and fixed.</p> |
| 318 |
|
| 319 |
<a name="oomtesting"></a> |
| 320 |
<p>The response of SQLite to out-of-memory (OOM) errors is tested using |
| 321 |
a specialized memory allocator overlay that can simulate memory failures. |
| 322 |
The overlay is a layer that is inserted in between the memory allocator |
| 323 |
and the rest of SQLite. The overlay passes most memory allocation |
| 324 |
requests straight through to the underlying allocator and passes the |
| 325 |
results back up to the requester. But the overlay can be set to |
| 326 |
cause the Nth memory allocation to fail. To run an OOM test, the overlay |
| 327 |
is first set to fail on the first allocation attempt. Then some test |
| 328 |
script is run and verification that the allocation was correctly caught |
| 329 |
and handled is made. Then the overlay is set to fail on the second |
| 330 |
allocation and the test repeats. The failure point continues to advance |
| 331 |
one allocation at a time until the entire test procedure runs to |
| 332 |
completion without hitting a memory allocation error. This whole |
| 333 |
test sequence is run twice. On the first pass, the |
| 334 |
overlay is set to fail only the Nth allocation. On the second pass, |
| 335 |
the overlay is set to fail the Nth and all subsequent allocations.</p> |
| 336 |
|
| 337 |
<p>Note that the memory leak detection logic continues to work even |
| 338 |
when the OOM overlay is being used. This verifies that SQLite |
| 339 |
does not leak memory even when it encounters memory allocation errors. |
| 340 |
Note also that the OOM overlay can work with any underlying memory |
| 341 |
allocator, including the instrumented memory allocator that checks |
| 342 |
for memory allocation misuse. In this way it is verified that |
| 343 |
OOM errors do not induce other kinds of memory usage errors.</p> |
| 344 |
|
| 345 |
<p>Finally, we observe that the instrumented memory allocator and the |
| 346 |
memory leak detector both work over the entire SQLite test suite and |
| 347 |
the <a href="testing.html#tcl">TCL test suite</a> provides over 99% statement test coverage and that |
| 348 |
the <a href="th3.html">TH3</a> test harness provides <a href="testing.html#coverage">100% branch test coverage</a> |
| 349 |
with no leak leaks. This is |
| 350 |
strong evidence that dynamic memory allocation is used correctly |
| 351 |
everywhere within SQLite.</p> |
| 352 |
|
| 353 |
<a name="allocarray"></a> |
| 354 |
<h2 id="_use_of_reallocarray_"><span>2.1. </span> Use of reallocarray()</h2> |
| 355 |
|
| 356 |
<p>The reallocarray() interface is a recent innovation (circa 2014) |
| 357 |
from the OpenBSD community that grow out of efforts to prevent the |
| 358 |
next <a href="http://heartbleed.com">"heartbleed" bug</a> by avoiding 32-bit integer |
| 359 |
arithmetic overflow on memory allocation size computations. The |
| 360 |
reallocarray() function has both unit-size and count parameters. |
| 361 |
To allocate memory sufficient to hold an array of N elements each X-bytes |
| 362 |
in size, one calls "reallocarray(0,X,N)". This is preferred over |
| 363 |
the traditional technique of invoking "malloc(X*N)" as reallocarray() |
| 364 |
eliminates the risk that the X*N multiplication will overflow and |
| 365 |
cause malloc() to return a buffer that is a different size from what |
| 366 |
the application expected.</p> |
| 367 |
|
| 368 |
<p>SQLite does not use reallocarray(). The reason is that reallocarray() |
| 369 |
is not useful to SQLite. It turns out that SQLite never does memory |
| 370 |
allocations that are the simple product of two integers. Instead, SQLite |
| 371 |
does allocations of the form "X+C" or "N*X+C" or "M*N*X+C" or |
| 372 |
"N*X+M*Y+C", and so forth. The reallocarray() interface is not helpful |
| 373 |
in avoiding integer overflow in those cases.</p> |
| 374 |
|
| 375 |
<p>Nevertheless, integer overflow in the computation of memory allocation |
| 376 |
sizes is a concern that SQLite would like to deal with. To prevent |
| 377 |
problems, all SQLite internal memory allocations occur using thin wrapper |
| 378 |
functions that take a signed 64-bit integer size parameter. The SQLite |
| 379 |
source code is audited to ensure that all size computations are carried |
| 380 |
out using 64-bit signed integers as well. SQLite will |
| 381 |
refuse to allocate more than about 2GB of memory at one go. (In common |
| 382 |
use, SQLite seldom ever allocates more than about 8KB of memory at a time |
| 383 |
so a 2GB allocation limit is not a burden.) So the 64-bit size parameter |
| 384 |
provides lots of headroom for detecting overflows. The same audit that |
| 385 |
verifies that all size computations are done as 64-bit signed integers |
| 386 |
also verifies that it is impossible to overflow a 64-bit integer |
| 387 |
during the computation.</p> |
| 388 |
|
| 389 |
<p>The code audits used to ensure that memory allocation size computations |
| 390 |
do not overflow in SQLite are repeated prior to every SQLite release.</p> |
| 391 |
|
| 392 |
<a name="config"></a> |
| 393 |
<h1 id="_configuration"><span>3. </span> Configuration</h1> |
| 394 |
|
| 395 |
<p>The default memory allocation settings in SQLite are appropriate |
| 396 |
for most applications. However, applications with unusual or particularly |
| 397 |
strict requirements may want to adjust the configuration to more closely |
| 398 |
align SQLite to their needs. |
| 399 |
Both compile-time and start-time configuration options are available.</p> |
| 400 |
|
| 401 |
<a name="altalloc"></a> |
| 402 |
|
| 403 |
<h2 id="_alternative_low_level_memory_allocators"><span>3.1. </span> Alternative low-level memory allocators</h2> |
| 404 |
|
| 405 |
<p>The SQLite source code includes several different memory allocation |
| 406 |
modules that can be selected at compile-time, or to a limited extent |
| 407 |
at start-time.</p> |
| 408 |
|
| 409 |
<a name="defaultalloc"></a> |
| 410 |
|
| 411 |
<h3 id="the_default_memory_allocator"><span>3.1.1. </span>The default memory allocator</h3> |
| 412 |
|
| 413 |
<p>By default, SQLite uses the malloc(), realloc(), and free() routines |
| 414 |
from the standard C library for its memory allocation needs. These routines |
| 415 |
are surrounded by a thin wrapper that also provides a "memsize()" function |
| 416 |
that will return the size of an existing allocation. The memsize() function |
| 417 |
is needed to keep an accurate count of the number of bytes of outstanding |
| 418 |
memory; memsize() determines how many bytes to remove from the outstanding |
| 419 |
count when an allocation is freed. The default allocator implements |
| 420 |
memsize() by always allocating 8 extra bytes on each malloc() request and |
| 421 |
storing the size of the allocation in that 8-byte header.</p> |
| 422 |
|
| 423 |
<p>The default memory allocator is recommended for most applications. |
| 424 |
If you do not have a compelling need to use an alternative memory |
| 425 |
allocator, then use the default.</p> |
| 426 |
|
| 427 |
<a name="memdebug"></a> |
| 428 |
|
| 429 |
<h3 id="the_debugging_memory_allocator"><span>3.1.2. </span>The debugging memory allocator</h3> |
| 430 |
|
| 431 |
<p>If SQLite is compiled with the <a href="compile.html#memdebug">SQLITE_MEMDEBUG</a> compile-time option, |
| 432 |
then a different, heavy wrapper is used around system malloc(), realloc(), |
| 433 |
and free(). |
| 434 |
The heavy wrapper allocates around 100 bytes of extra space |
| 435 |
with each allocation. The extra space is used to place sentinel values |
| 436 |
at both ends of the allocation returned to the SQLite core. When an |
| 437 |
allocation is freed, |
| 438 |
these sentinels are checked to make sure the SQLite core did not overrun |
| 439 |
the buffer in either direction. When the system library is GLIBC, the |
| 440 |
heavy wrapper also makes use of the GNU backtrace() function to examine |
| 441 |
the stack and record the ancestor functions of the malloc() call. When |
| 442 |
running the SQLite test suite, the heavy wrapper also records the name of |
| 443 |
the current test case. These latter two features are useful for |
| 444 |
tracking down the source of memory leaks detected by the test suite.</p> |
| 445 |
|
| 446 |
<p>The heavy wrapper that is used when <a href="compile.html#memdebug">SQLITE_MEMDEBUG</a> is set also |
| 447 |
makes sure each new allocation is filled with nonsense data prior to |
| 448 |
returning the allocation to the caller. And as soon as an allocation |
| 449 |
is free, it is again filled with nonsense data. These two actions help |
| 450 |
to ensure that the SQLite core does not make assumptions about the state |
| 451 |
of newly allocated memory and that memory allocations are not used after |
| 452 |
they have been freed.</p> |
| 453 |
|
| 454 |
<p>The heavy wrapper employed by <a href="compile.html#memdebug">SQLITE_MEMDEBUG</a> is intended for use |
| 455 |
only during testing, analysis, and debugging of SQLite. The heavy wrapper |
| 456 |
has a significant performance and memory overhead and probably should not |
| 457 |
be used in production.</p> |
| 458 |
|
| 459 |
<a name="win32heap"></a> |
| 460 |
|
| 461 |
<h3 id="the_win32_native_memory_allocator"><span>3.1.3. </span>The Win32 native memory allocator</h3> |
| 462 |
|
| 463 |
<p>If SQLite is compiled for Windows with the <a href="compile.html#win32_malloc">SQLITE_WIN32_MALLOC</a> |
| 464 |
compile-time option, then a different, thin wrapper is used around |
| 465 |
HeapAlloc(), HeapReAlloc(), and HeapFree(). The thin wrapper uses the |
| 466 |
configured SQLite heap, which will be different from the default process |
| 467 |
heap if the <a href="compile.html#win32_heap_create">SQLITE_WIN32_HEAP_CREATE</a> compile-time option is used. In |
| 468 |
addition, when an allocation is made or freed, HeapValidate() will be |
| 469 |
called if SQLite is compiled with assert() enabled and the |
| 470 |
<a href="compile.html#win32_malloc_validate">SQLITE_WIN32_MALLOC_VALIDATE</a> compile-time option.</p> |
| 471 |
|
| 472 |
<a name="memsys5"></a> |
| 473 |
|
| 474 |
<h3 id="zero_malloc_memory_allocator"><span>3.1.4. </span>Zero-malloc memory allocator</h3> |
| 475 |
|
| 476 |
<p>When SQLite is compiled with the <a href="compile.html#enable_memsys5">SQLITE_ENABLE_MEMSYS5</a> option, an |
| 477 |
alternative memory allocator that does not use malloc() is included in the |
| 478 |
build. The SQLite developers refer to this alternative memory allocator |
| 479 |
as "memsys5". Even when it is included in the build, memsys5 is |
| 480 |
disabled by default. |
| 481 |
To enable memsys5, the application must invoke the following SQLite |
| 482 |
interface at start-time:</p> |
| 483 |
|
| 484 |
<blockquote><pre> |
| 485 |
<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); |
| 486 |
</pre></blockquote> |
| 487 |
|
| 488 |
<p>In the call above, pBuf is a pointer to a large, contiguous chunk |
| 489 |
of memory space that SQLite will use to satisfy all of its memory |
| 490 |
allocation needs. pBuf might point to a static array or it might |
| 491 |
be memory obtained from some other application-specific mechanism. |
| 492 |
szBuf is an integer that is the number of bytes of memory space |
| 493 |
pointed to by pBuf. mnReq is another integer that is the |
| 494 |
minimum size of an allocation. Any call to <a href="c3ref/free.html">sqlite3_malloc(N)</a> where |
| 495 |
N is less than mnReq will be rounded up to mnReq. mnReq must be |
| 496 |
a power of two. We shall see later that the mnReq parameter is |
| 497 |
important in reducing the value of <b>n</b> and hence the minimum memory |
| 498 |
size requirement in the <a href="malloc.html#nofrag">Robson proof</a>.</p> |
| 499 |
|
| 500 |
<p>The memsys5 allocator is designed for use on embedded systems, |
| 501 |
though there is nothing to prevent its use on workstations. |
| 502 |
The szBuf is typically between a few hundred kilobytes up to a few |
| 503 |
dozen megabytes, depending on system requirements and memory budget.</p> |
| 504 |
|
| 505 |
<p>The algorithm used by memsys5 can be called "power-of-two, |
| 506 |
first-fit". The sizes of all memory allocation |
| 507 |
requests are rounded up to a power of two and the request is satisfied |
| 508 |
by the first free slot in pBuf that is large enough. Adjacent freed |
| 509 |
allocations are coalesced using a buddy system. When used appropriately, |
| 510 |
this algorithm provides mathematical guarantees against fragmentation and |
| 511 |
breakdown, as described further <a href="#nofrag">below</a>.</p> |
| 512 |
|
| 513 |
<a name="memsysx"></a> |
| 514 |
|
| 515 |
<h3 id="experimental_memory_allocators"><span>3.1.5. </span>Experimental memory allocators</h3> |
| 516 |
|
| 517 |
<p>The name "memsys5" used for the zero-malloc memory allocator implies |
| 518 |
that there are several additional memory allocators available, and indeed |
| 519 |
there are. The default memory allocator is "memsys1". The debugging |
| 520 |
memory allocator is "memsys2". Those have already been covered.</p> |
| 521 |
|
| 522 |
<p>If SQLite is compiled with <a href="compile.html#enable_memsys3">SQLITE_ENABLE_MEMSYS3</a> then another |
| 523 |
zero-malloc memory allocator, similar to memsys5, is included in the |
| 524 |
source tree. The memsys3 allocator, like memsys5, must be activated |
| 525 |
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 |
| 526 |
uses the memory buffer supplied as its source for all memory allocations. |
| 527 |
The difference between memsys3 and memsys5 is that memsys3 uses a |
| 528 |
different memory allocation algorithm that seems to work well in |
| 529 |
practice, but which does not provide mathematical |
| 530 |
guarantees against memory fragmentation and breakdown. Memsys3 was |
| 531 |
a predecessor to memsys5. The SQLite developers now believe that |
| 532 |
memsys5 is superior to |
| 533 |
memsys3 and that all applications that need a zero-malloc memory |
| 534 |
allocator should use memsys5 in preference to memsys3. Memsys3 is |
| 535 |
considered both experimental and deprecated and will likely be removed |
| 536 |
from the source tree in a future release of SQLite.</p> |
| 537 |
|
| 538 |
<p>Memsys4 and memsys6 were experimental memory allocators |
| 539 |
introduced in around 2007 and subsequently removed from the |
| 540 |
source tree in around 2008, after it became clear that they |
| 541 |
added no new value.</p> |
| 542 |
|
| 543 |
<p>Other experimental memory allocators might be added in future releases |
| 544 |
of SQLite. One may anticipate that these will be called memsys7, memsys8, |
| 545 |
and so forth.</p> |
| 546 |
|
| 547 |
<a name="appalloc"></a> |
| 548 |
<h3 id="application_defined_memory_allocators"><span>3.1.6. </span>Application-defined memory allocators</h3> |
| 549 |
|
| 550 |
<p>New memory allocators do not have to be part of the SQLite source tree |
| 551 |
nor included in the sqlite3.c <a href="amalgamation.html">amalgamation</a>. Individual applications can |
| 552 |
supply their own memory allocators to SQLite at start-time.</p> |
| 553 |
|
| 554 |
<p>To cause SQLite to use a new memory allocator, the application |
| 555 |
simply calls:</p> |
| 556 |
|
| 557 |
<blockquote><pre> |
| 558 |
<a href="c3ref/config.html">sqlite3_config</a>(<a href="c3ref/c_config_covering_index_scan.html#sqliteconfigmalloc">SQLITE_CONFIG_MALLOC</a>, pMem); |
| 559 |
</pre></blockquote> |
| 560 |
|
| 561 |
<p>In the call above, pMem is a pointer to an <a href="c3ref/mem_methods.html">sqlite3_mem_methods</a> object |
| 562 |
that defines the interface to the application-specific memory allocator. |
| 563 |
The <a href="c3ref/mem_methods.html">sqlite3_mem_methods</a> object is really just a structure containing |
| 564 |
pointers to functions to implement the various memory allocation primitives. |
| 565 |
</p> |
| 566 |
|
| 567 |
<p>In a multi-threaded application, access to the <a href="c3ref/mem_methods.html">sqlite3_mem_methods</a> |
| 568 |
is serialized if and only if <a href="c3ref/c_config_covering_index_scan.html#sqliteconfigmemstatus">SQLITE_CONFIG_MEMSTATUS</a> is enabled. |
| 569 |
If <a href="c3ref/c_config_covering_index_scan.html#sqliteconfigmemstatus">SQLITE_CONFIG_MEMSTATUS</a> is disabled then the methods in |
| 570 |
<a href="c3ref/mem_methods.html">sqlite3_mem_methods</a> must take care of their own serialization needs.</p> |
| 571 |
|
| 572 |
<a name="overlayalloc"></a> |
| 573 |
<h3 id="memory_allocator_overlays"><span>3.1.7. </span>Memory allocator overlays</h3> |
| 574 |
|
| 575 |
<p>An application can insert layers or "overlays" in between the |
| 576 |
SQLite core and the underlying memory allocator. |
| 577 |
For example, the <a href="#oomtesting">out-of-memory test logic</a> |
| 578 |
for SQLite uses an overlay that can simulate memory allocation |
| 579 |
failures.</p> |
| 580 |
|
| 581 |
<p>An overlay can be created by using the</p> |
| 582 |
|
| 583 |
<blockquote><pre> |
| 584 |
<a href="c3ref/config.html">sqlite3_config</a>(<a href="c3ref/c_config_covering_index_scan.html#sqliteconfiggetmalloc">SQLITE_CONFIG_GETMALLOC</a>, pOldMem); |
| 585 |
</pre></blockquote> |
| 586 |
|
| 587 |
<p>interface to obtain pointers to the existing memory allocator. |
| 588 |
The existing allocator is saved by the overlay and is used as |
| 589 |
a fallback to do real memory allocation. Then the overlay is |
| 590 |
inserted in place of the existing memory allocator using |
| 591 |
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 |
| 592 |
<a href="#appalloc">above</a>. |
| 593 |
|
| 594 |
<a name="stuballoc"></a> |
| 595 |
</p><h3 id="no_op_memory_allocator_stub"><span>3.1.8. </span>No-op memory allocator stub</h3> |
| 596 |
|
| 597 |
<p>If SQLite is compiled with the <a href="compile.html#zero_malloc">SQLITE_ZERO_MALLOC</a> option, then |
| 598 |
the <a href="malloc.html#defaultalloc">default memory allocator</a> is omitted and replaced by a stub |
| 599 |
memory allocator that never allocates any memory. Any calls to the |
| 600 |
stub memory allocator will report back that no memory is available.</p> |
| 601 |
|
| 602 |
<p>The no-op memory allocator is not useful by itself. It exists only |
| 603 |
as a placeholder so that SQLite has a memory allocator to link against |
| 604 |
on systems that may not have malloc(), free(), or realloc() in their |
| 605 |
standard library. |
| 606 |
An application that is compiled with <a href="compile.html#zero_malloc">SQLITE_ZERO_MALLOC</a> will need to |
| 607 |
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 |
| 608 |
<a href="c3ref/c_config_covering_index_scan.html#sqliteconfigheap">SQLITE_CONFIG_HEAP</a> to specify a new alternative memory allocator |
| 609 |
before beginning to use SQLite.</p> |
| 610 |
|
| 611 |
<a name="pagecache"></a> |
| 612 |
|
| 613 |
<h2 id="_page_cache_memory"><span>3.2. </span> Page cache memory</h2> |
| 614 |
|
| 615 |
<p>In most applications, the database page cache subsystem within |
| 616 |
SQLite uses more dynamically allocated memory than all other parts |
| 617 |
of SQLite combined. It is not unusual to see the database page cache |
| 618 |
consume over 10 times more memory than the rest of SQLite combined.</p> |
| 619 |
|
| 620 |
<p>SQLite can be configured to make page cache memory allocations from |
| 621 |
a separate and distinct memory pool of fixed-size |
| 622 |
slots. This can have two advantages:</p> |
| 623 |
|
| 624 |
<ul> |
| 625 |
<li><p> |
| 626 |
Because allocations are all the same size, the memory allocator can |
| 627 |
operate much faster. The allocator need not bother with coalescing |
| 628 |
adjacent free slots or searching for a slot |
| 629 |
of an appropriate size. All unallocated memory slots can be stored on |
| 630 |
a linked list. Allocating consists of removing the first entry from the |
| 631 |
list. Deallocating is simply adding an entry to the beginning of the list. |
| 632 |
</p></li> |
| 633 |
|
| 634 |
<li><p> |
| 635 |
With a single allocation size, the <b>n</b> parameter in the |
| 636 |
<a href="malloc.html#nofrag">Robson proof</a> is 1, and the total memory space required by the allocator |
| 637 |
(<b>N</b>) is exactly equal to maximum memory used (<b>M</b>). |
| 638 |
No additional memory is required to cover fragmentation overhead, thus |
| 639 |
reducing memory requirements. This is particularly important for the |
| 640 |
page cache memory since the page cache constitutes the largest component |
| 641 |
of the memory needs of SQLite. |
| 642 |
</p></li> |
| 643 |
</ul> |
| 644 |
|
| 645 |
<p>The page-cache memory allocator is disabled by default. |
| 646 |
An application can enable it at start-time as follows:</p> |
| 647 |
|
| 648 |
<blockquote><pre> |
| 649 |
<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); |
| 650 |
</pre></blockquote> |
| 651 |
|
| 652 |
<p>The pBuf parameter is a pointer to a contiguous range of bytes that |
| 653 |
SQLite will use for page-cache memory allocations. The buffer must be |
| 654 |
at least sz*N bytes in size. The "sz" parameter |
| 655 |
is the size of each page-cache allocation. N is the maximum |
| 656 |
number of available allocations.</p> |
| 657 |
|
| 658 |
<p>Note that each page cache allocation is larger than the database |
| 659 |
page size. If the database page size is Z, each page cache memory |
| 660 |
allocation will be for Z+Y bytes, where Y is a constant that depends |
| 661 |
on compile-time options and the target processor. For a particular |
| 662 |
platform and build of SQLite, Y can be determined using the |
| 663 |
<a href="c3ref/c_config_covering_index_scan.html#sqliteconfigpcachehdrsz">SQLITE_CONFIG_PCACHE_HDRSZ</a> option to <a href="c3ref/config.html">sqlite3_config()</a>. |
| 664 |
|
| 665 |
</p><p>If SQLite needs a page-cache entry that is larger than "sz" bytes or |
| 666 |
if it needs more than N entries, it falls back to using the |
| 667 |
general-purpose memory allocator.</p> |
| 668 |
|
| 669 |
<a name="lookaside"></a> |
| 670 |
|
| 671 |
<h2 id="_lookaside_memory_allocator"><span>3.3. </span> Lookaside memory allocator</h2> |
| 672 |
|
| 673 |
<p>SQLite <a href="c3ref/sqlite3.html">database connections</a> make many |
| 674 |
small and short-lived memory allocations. |
| 675 |
This occurs most commonly when compiling SQL statements using |
| 676 |
<a href="c3ref/prepare.html">sqlite3_prepare_v2()</a> but also to a lesser extent when running |
| 677 |
<a href="c3ref/stmt.html">prepared statements</a> using <a href="c3ref/step.html">sqlite3_step()</a>. These small memory |
| 678 |
allocations are used to hold things such as the names of tables |
| 679 |
and columns, parse tree nodes, individual query results values, |
| 680 |
and B-Tree cursor objects. There are consequently |
| 681 |
many calls to malloc() and free() - so many calls that malloc() and |
| 682 |
free() end up using a significant fraction of the CPU time assigned |
| 683 |
to SQLite.</p> |
| 684 |
|
| 685 |
<p>SQLite <a href="releaselog/3_6_1.html">version 3.6.1</a> (2008-08-06) |
| 686 |
introduced the lookaside memory allocator to |
| 687 |
help reduce the memory allocation load. In the lookaside allocator, |
| 688 |
each <a href="c3ref/sqlite3.html">database connection</a> preallocates a single large chunk of memory |
| 689 |
(typically in the range of 60 to 120 kilobytes) and divides that chunk |
| 690 |
up into small fixed-size "slots" of around 100 to 1000 byte each. This |
| 691 |
becomes the lookaside memory pool. Thereafter, memory allocations |
| 692 |
associated with the <a href="c3ref/sqlite3.html">database connection</a> and that are not too large |
| 693 |
are satisfied using one of the lookaside pool slots rather than by calling |
| 694 |
the general-purpose memory allocator. Larger allocations continue to |
| 695 |
use the general-purpose memory allocator, as do allocations that occur |
| 696 |
when the lookaside pool slots are all checked out. |
| 697 |
But in many cases, the memory |
| 698 |
allocations are small enough and there are few enough outstanding that |
| 699 |
the new memory requests can be satisfied from the lookaside |
| 700 |
pool.</p> |
| 701 |
|
| 702 |
<p>Because lookaside allocations are always the same size, the allocation |
| 703 |
and deallocation algorithms are very quick. There is no |
| 704 |
need to coalesce adjacent free slots or search for a slot |
| 705 |
of a particular size. Each <a href="c3ref/sqlite3.html">database connection</a> maintains a singly-linked |
| 706 |
list of unused slots. Allocation requests simply pull the first |
| 707 |
element of this list. Deallocations simply push the element back onto |
| 708 |
the front of the list. |
| 709 |
Furthermore, each <a href="c3ref/sqlite3.html">database connection</a> is assumed to already be |
| 710 |
running in a single thread (there are mutexes already in |
| 711 |
place to enforce this) so no additional mutexing is required to |
| 712 |
serialize access to the lookaside slot freelist. |
| 713 |
Consequently, lookaside memory |
| 714 |
allocations and deallocations are very fast. In speed tests on |
| 715 |
Linux and Mac OS X workstations, SQLite has shown overall performance |
| 716 |
improvements as high as 10% to 15%, depending on how the workload |
| 717 |
and lookaside are configured.</p> |
| 718 |
|
| 719 |
<p>The size of the lookaside memory pool has a global default value |
| 720 |
but can also be configured on a connection-by-connection basis. |
| 721 |
To change the default size of the lookaside memory pool at |
| 722 |
compile-time, use the |
| 723 |
<a href="compile.html#default_lookaside">-DSQLITE_DEFAULT_LOOKASIDE=<i>SZ,N</i></a> |
| 724 |
option. |
| 725 |
To change the default size of the lookaside memory pool at |
| 726 |
start-time, use the <a href="c3ref/config.html">sqlite3_config()</a> interface:</p> |
| 727 |
|
| 728 |
<blockquote><pre> |
| 729 |
<a href="c3ref/config.html">sqlite3_config</a>(<a href="c3ref/c_config_covering_index_scan.html#sqliteconfiglookaside">SQLITE_CONFIG_LOOKASIDE</a>, sz, cnt); |
| 730 |
</pre></blockquote> |
| 731 |
|
| 732 |
<p>The "sz" parameter is the size in bytes of each lookaside slot. |
| 733 |
The "cnt" parameter is |
| 734 |
the total number of lookaside memory slots per database connection. |
| 735 |
The total amount |
| 736 |
of lookaside memory allocated to each <a href="c3ref/sqlite3.html">database connection</a> is |
| 737 |
sz*cnt bytes. |
| 738 |
</p> |
| 739 |
|
| 740 |
<p>The lookaside pool can be changed for an individual |
| 741 |
<a href="c3ref/sqlite3.html">database connection</a> "db" using this call:</p> |
| 742 |
|
| 743 |
<blockquote><pre> |
| 744 |
<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); |
| 745 |
</pre></blockquote> |
| 746 |
|
| 747 |
<p>The "pBuf" parameter is a pointer to memory space that will be |
| 748 |
used for the lookaside memory pool. If pBuf is NULL, then SQLite |
| 749 |
will obtain its own space for the memory pool using <a href="c3ref/free.html">sqlite3_malloc()</a>. |
| 750 |
The "sz" and "cnt" parameters are the size of each lookaside slot |
| 751 |
and the number of slots, respectively. If pBuf is not NULL, then it |
| 752 |
must point to at least sz*cnt bytes of memory.</p> |
| 753 |
|
| 754 |
<p>The lookaside configuration can only be changed while there are |
| 755 |
no outstanding lookaside allocations for the database connection. |
| 756 |
Hence, the configuration should be set immediately after creating the |
| 757 |
database connection using <a href="c3ref/open.html">sqlite3_open()</a> (or equivalent) and before |
| 758 |
evaluating any SQL statements on the connection.</p> |
| 759 |
|
| 760 |
<h3 id="two_size_lookaside"><span>3.3.1. </span>Two-Size Lookaside</h3> |
| 761 |
|
| 762 |
<p> |
| 763 |
Beginning with SQLite version 3.31.0 (2020-01-22), |
| 764 |
lookaside supports two memory pools, each with a different size |
| 765 |
slot. The small-slot pool uses 128-byte slots and the large-slot |
| 766 |
pool uses whatever size is specified by <a href="c3ref/c_dbconfig_defensive.html#sqlitedbconfiglookaside">SQLITE_DBCONFIG_LOOKASIDE</a> |
| 767 |
(defaulting to 1200 bytes). Splitting the pool in two like this |
| 768 |
allows memory allocations to be covered by lookaside more often |
| 769 |
while at the same time reducing per-database-connection heap usage |
| 770 |
from 120KB down to 48KB. |
| 771 |
|
| 772 |
</p><p> |
| 773 |
Configuration continues to use the SQLITE_DBCONFIG_LOOKASIDE or |
| 774 |
SQLITE_CONFIG_LOOKASIDE configuration options, as described above, |
| 775 |
with parameters "sz" and "cnt". The total heap space used for |
| 776 |
lookaside continues to be sz*cnt bytes. But the space is allocated |
| 777 |
between the small-slot lookaside and big-slot lookaside, with |
| 778 |
preference given to small-slot lookaside. The total number of |
| 779 |
slots will usually exceed "cnt", since "sz" is typically much |
| 780 |
larger than the small-slot size of 128 bytes. |
| 781 |
|
| 782 |
</p><p> |
| 783 |
The default lookaside configuration has changed from 100 slots |
| 784 |
of 1200 bytes each (120KB) to be 40 slots of 1200 bytes each |
| 785 |
(48KB). This space ends up being allocated as 93 slots of |
| 786 |
128 bytes each and 30 slots of 1200 bytes each. So more lookaside |
| 787 |
slots are available but much less heap space is used. |
| 788 |
|
| 789 |
</p><p> |
| 790 |
The default lookaside configuration, the size of the small-slots, |
| 791 |
and the details of how heap space is allocated between small-slots |
| 792 |
and big-slots, are all subject to change from one release to the |
| 793 |
next. |
| 794 |
|
| 795 |
|
| 796 |
<a name="memstatus"></a> |
| 797 |
|
| 798 |
</p><h2 id="_memory_status"><span>3.4. </span> Memory status</h2> |
| 799 |
|
| 800 |
<p>By default, SQLite keeps statistics on its memory usage. These |
| 801 |
statistics are useful in helping to determine how much memory an |
| 802 |
application really needs. The statistics can also be used in |
| 803 |
high-reliability systems to determine |
| 804 |
if the memory usage is coming close to or exceeding the limits |
| 805 |
of the <a href="malloc.html#nofrag">Robson proof</a> and hence that the memory allocation subsystem is |
| 806 |
liable to breakdown.</p> |
| 807 |
|
| 808 |
<p>Most memory statistics are global, and therefore the tracking of |
| 809 |
statistics must be serialized with a mutex. Statistics are turned |
| 810 |
on by default, but an option exists to disable them. By disabling |
| 811 |
memory statistics, |
| 812 |
SQLite avoids entering and leaving a mutex on each memory allocation |
| 813 |
and deallocation. That savings can be noticeable on systems where |
| 814 |
mutex operations are expensive. To disable memory statistics, the |
| 815 |
following interface is used at start-time:</p> |
| 816 |
|
| 817 |
<blockquote><pre> |
| 818 |
<a href="c3ref/config.html">sqlite3_config</a>(<a href="c3ref/c_config_covering_index_scan.html#sqliteconfigmemstatus">SQLITE_CONFIG_MEMSTATUS</a>, onoff); |
| 819 |
</pre></blockquote> |
| 820 |
|
| 821 |
<p>The "onoff" parameter is true to enable the tracking of memory |
| 822 |
statistics and false to disable statistics tracking.</p> |
| 823 |
|
| 824 |
<p>Assuming statistics are enabled, the following routine can be used |
| 825 |
to access them:</p> |
| 826 |
|
| 827 |
<blockquote><pre> |
| 828 |
<a href="c3ref/status.html">sqlite3_status</a>(<a href="c3ref/c_status_malloc_count.html#sqlitestatusmemoryused">verb</a>, &current, &highwater, resetflag); |
| 829 |
</pre></blockquote> |
| 830 |
|
| 831 |
<p>The "verb" argument determines what statistic is accessed. |
| 832 |
There are <a href="c3ref/c_status_malloc_count.html#sqlitestatusmemoryused">various verbs</a> defined. The |
| 833 |
list is expected to grow as the <a href="c3ref/status.html">sqlite3_status()</a> interface matures. |
| 834 |
The current value of the selected parameter is written into integer |
| 835 |
"current" and the highest historical value |
| 836 |
is written into integer "highwater". If resetflag is true, then |
| 837 |
the high-water mark is reset down to the current value after the call |
| 838 |
returns.</p> |
| 839 |
|
| 840 |
<p>A different interface is used to find statistics associated with a |
| 841 |
single <a href="c3ref/sqlite3.html">database connection</a>:</p> |
| 842 |
|
| 843 |
<blockquote><pre> |
| 844 |
<a href="c3ref/db_status.html">sqlite3_db_status</a>(db, <a href="c3ref/c_dbstatus_options.html#sqlitedbstatuslookasideused">verb</a>, &current, &highwater, resetflag); |
| 845 |
</pre></blockquote> |
| 846 |
|
| 847 |
<p>This interface is similar except that it takes a pointer to |
| 848 |
a <a href="c3ref/sqlite3.html">database connection</a> as its first argument and returns statistics about |
| 849 |
that one object rather than about the entire SQLite library. |
| 850 |
The <a href="c3ref/db_status.html">sqlite3_db_status()</a> interface currently only recognizes a |
| 851 |
single verb <a href="c3ref/c_dbstatus_options.html#sqlitedbstatuslookasideused">SQLITE_DBSTATUS_LOOKASIDE_USED</a>, though additional verbs |
| 852 |
may be added in the future.</p> |
| 853 |
|
| 854 |
<p>The per-connection statistics do not use global variables and hence |
| 855 |
do not require mutexes to update or access. Consequently the |
| 856 |
per-connection statistics continue to function even if |
| 857 |
<a href="c3ref/c_config_covering_index_scan.html#sqliteconfigmemstatus">SQLITE_CONFIG_MEMSTATUS</a> is turned off.</p> |
| 858 |
|
| 859 |
<a name="heaplimit"></a> |
| 860 |
<h2 id="_setting_memory_usage_limits"><span>3.5. </span> Setting memory usage limits</h2> |
| 861 |
|
| 862 |
<p>The <a href="c3ref/hard_heap_limit64.html">sqlite3_soft_heap_limit64()</a> interface can be used to set an |
| 863 |
upper bound on the total amount of outstanding memory that the |
| 864 |
general-purpose memory allocator for SQLite will allow to be outstanding |
| 865 |
at one time. If attempts are made to allocate more memory than specified |
| 866 |
by the soft heap limit, then SQLite will first attempt to free cache |
| 867 |
memory before continuing with the allocation request. The soft heap |
| 868 |
limit mechanism only works if <a href="malloc.html#memstatus">memory statistics</a> are enabled and |
| 869 |
it works best |
| 870 |
if the SQLite library is compiled with the <a href="compile.html#enable_memory_management">SQLITE_ENABLE_MEMORY_MANAGEMENT</a> |
| 871 |
compile-time option.</p> |
| 872 |
|
| 873 |
<p>The soft heap limit is "soft" in this sense: If SQLite is not able |
| 874 |
to free up enough auxiliary memory to stay below the limit, it goes |
| 875 |
ahead and allocates the extra memory and exceeds its limit. This occurs |
| 876 |
under the theory that it is better to use additional memory than to fail |
| 877 |
outright.</p> |
| 878 |
|
| 879 |
<p>As of SQLite <a href="releaselog/3_6_1.html">version 3.6.1</a> (2008-08-06), |
| 880 |
the soft heap limit only applies to the |
| 881 |
general-purpose memory allocator. The soft heap limit does not know |
| 882 |
about or interact with |
| 883 |
the <a href="malloc.html#pagecache">pagecache memory allocator</a> or the <a href="malloc.html#lookaside">lookaside memory allocator</a>. |
| 884 |
This deficiency will likely be addressed in a future release.</p> |
| 885 |
|
| 886 |
<a name="nofrag"></a> |
| 887 |
|
| 888 |
<h1 id="_mathematical_guarantees_against_memory_allocation_failures"><span>4. </span> Mathematical Guarantees Against Memory Allocation Failures</h1> |
| 889 |
|
| 890 |
<p>The problem of dynamic memory allocation, and specifically the |
| 891 |
problem of a memory allocator breakdown, has been studied by |
| 892 |
J. M. Robson and the results published as:</p> |
| 893 |
|
| 894 |
<blockquote> |
| 895 |
J. M. Robson. "Bounds for Some Functions Concerning Dynamic |
| 896 |
Storage Allocation". <i>Journal of the Association for |
| 897 |
Computing Machinery</i>, Volume 21, Number 8, July 1974, |
| 898 |
pages 491-499. |
| 899 |
</blockquote> |
| 900 |
|
| 901 |
<p>Let us use the following notation (similar but not identical to |
| 902 |
Robson's notation):</p> |
| 903 |
|
| 904 |
<blockquote> |
| 905 |
<table cellpadding="10" border="0"> |
| 906 |
<tr><td valign="top"><b>N</b></td> |
| 907 |
<td valign="top"> |
| 908 |
The amount of raw memory needed by the memory allocation system |
| 909 |
in order to guarantee that no memory allocation will ever fail. |
| 910 |
</td></tr> |
| 911 |
<tr><td valign="top"><b>M</b></td> |
| 912 |
<td valign="top"> |
| 913 |
The maximum amount of memory that the application has checked out. |
| 914 |
</td></tr> |
| 915 |
<tr><td valign="top"><b>n</b></td> |
| 916 |
<td valign="top"> |
| 917 |
The ratio of the largest memory allocation to the smallest. We assume |
| 918 |
that every memory allocation size is an integer multiple of the smallest memory |
| 919 |
allocation size. |
| 920 |
</td></tr> |
| 921 |
</table> |
| 922 |
</blockquote> |
| 923 |
|
| 924 |
<p>Robson proves the following result:</p> |
| 925 |
|
| 926 |
<blockquote> |
| 927 |
<b>N</b> = <b>M</b>*(1 + (log<sub>2</sub> <b>n</b>)/2) - <b>n</b> + 1 |
| 928 |
</blockquote> |
| 929 |
|
| 930 |
<p>Colloquially, the Robson proof shows that in order to guarantee |
| 931 |
breakdown-free operation, any memory allocator must use a memory pool |
| 932 |
of size <b>N</b> which exceeds the maximum amount of memory ever |
| 933 |
used <b>M</b> by a multiplier that depends on <b>n</b>, |
| 934 |
the ratio of the largest to the smallest allocation size. In other |
| 935 |
words, unless all memory allocations are of exactly the same size |
| 936 |
(<b>n</b>=1) then the system needs access to more memory than it will |
| 937 |
ever use at one time. Furthermore, we see that the amount of surplus |
| 938 |
memory required grows rapidly as the ratio of largest to smallest |
| 939 |
allocations increases, and so there is strong incentive to keep all |
| 940 |
allocations as near to the same size as possible.</p> |
| 941 |
|
| 942 |
<p>Robson's proof is constructive. |
| 943 |
He provides an algorithm for computing a sequence of allocation |
| 944 |
and deallocation operations that will lead to an allocation failure due to |
| 945 |
memory fragmentation if available memory is as much as one byte |
| 946 |
less than <b>N</b>. |
| 947 |
And, Robson shows that a power-of-two first-fit memory allocator |
| 948 |
(such as implemented by <a href="malloc.html#memsys5">memsys5</a>) will never fail a memory allocation |
| 949 |
provided that available memory is <b>N</b> or more bytes.</p> |
| 950 |
|
| 951 |
<p>The values <b>M</b> and <b>n</b> are properties of the application. |
| 952 |
If an application is constructed in such a way that both <b>M</b> and |
| 953 |
<b>n</b> are known, or at least have known upper bounds, and if the |
| 954 |
application uses |
| 955 |
the <a href="malloc.html#memsys5">memsys5</a> memory allocator and is provided with <b>N</b> bytes of |
| 956 |
available memory space using <a href="c3ref/c_config_covering_index_scan.html#sqliteconfigheap">SQLITE_CONFIG_HEAP</a> |
| 957 |
then Robson proves that no memory allocation request will ever fail |
| 958 |
within the application. |
| 959 |
To put this another way, the application developer can select a value |
| 960 |
for <b>N</b> that will guarantee that no call to any SQLite interface |
| 961 |
will ever return <a href="rescode.html#nomem">SQLITE_NOMEM</a>. The memory pool will never become |
| 962 |
so fragmented that a new memory allocation request cannot be satisfied. |
| 963 |
This is an important property for |
| 964 |
applications where a software fault could cause injury, physical harm, or |
| 965 |
loss of irreplaceable data.</p> |
| 966 |
|
| 967 |
<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> |
| 968 |
|
| 969 |
<p>The Robson proof applies separately to each of the memory allocators |
| 970 |
used by SQLite:</p> |
| 971 |
|
| 972 |
<ul> |
| 973 |
<li>The general-purpose memory allocator (<a href="malloc.html#memsys5">memsys5</a>).</li> |
| 974 |
<li>The <a href="malloc.html#pagecache">pagecache memory allocator</a>.</li> |
| 975 |
<li>The <a href="malloc.html#lookaside">lookaside memory allocator</a>.</li> |
| 976 |
</ul> |
| 977 |
|
| 978 |
<p>For allocators other than <a href="malloc.html#memsys5">memsys5</a>, |
| 979 |
all memory allocations are of the same size. Hence, <b>n</b>=1 |
| 980 |
and therefore <b>N</b>=<b>M</b>. In other words, the memory pool need |
| 981 |
be no larger than the largest amount of memory in use at any given moment.</p> |
| 982 |
|
| 983 |
<p>The usage of pagecache memory is somewhat harder to control in |
| 984 |
SQLite version 3.6.1, though mechanisms are planned for subsequent |
| 985 |
releases that will make controlling pagecache memory much easier. |
| 986 |
Prior to the introduction of these new mechanisms, the only way |
| 987 |
to control pagecache memory is using the <a href="pragma.html#pragma_cache_size">cache_size pragma</a>.</p> |
| 988 |
|
| 989 |
<p>Safety-critical applications will usually want to modify the |
| 990 |
default lookaside memory configuration so that when the initial |
| 991 |
lookaside memory buffer is allocated during <a href="c3ref/open.html">sqlite3_open()</a> the |
| 992 |
resulting memory allocation is not so large as to force the <b>n</b> |
| 993 |
parameter to be too large. In order to keep <b>n</b> under control, |
| 994 |
it is best to try to keep the largest memory allocation below 2 or 4 |
| 995 |
kilobytes. Hence, a reasonable default setup for the lookaside |
| 996 |
memory allocator might be any of the following:</p> |
| 997 |
|
| 998 |
<blockquote><pre> |
| 999 |
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 32, 32); /* 1K */ |
| 1000 |
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 64, 32); /* 2K */ |
| 1001 |
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 32, 64); /* 2K */ |
| 1002 |
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 64, 64); /* 4K */ |
| 1003 |
</pre></blockquote> |
| 1004 |
|
| 1005 |
<p>Another approach is to initially disable the lookaside memory |
| 1006 |
allocator:</p> |
| 1007 |
|
| 1008 |
<blockquote><pre> |
| 1009 |
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 0, 0); |
| 1010 |
</pre></blockquote> |
| 1011 |
|
| 1012 |
<p>Then let the application maintain a separate pool of larger |
| 1013 |
lookaside memory buffers that it can distribute to <a href="c3ref/sqlite3.html">database connections</a> |
| 1014 |
as they are created. In the common case, the application will only |
| 1015 |
have a single <a href="c3ref/sqlite3.html">database connection</a> and so the lookaside memory pool |
| 1016 |
can consist of a single large buffer.</p> |
| 1017 |
|
| 1018 |
<blockquote><pre> |
| 1019 |
sqlite3_db_config(db, SQLITE_DBCONFIG_LOOKASIDE, aStatic, 256, 500); |
| 1020 |
</pre></blockquote> |
| 1021 |
|
| 1022 |
<p>The lookaside memory allocator is really intended as performance |
| 1023 |
optimization, not as a method for assuring breakdown-free memory allocation, |
| 1024 |
so it is not unreasonable to completely disable the lookaside memory |
| 1025 |
allocator for safety-critical operations.</p> |
| 1026 |
|
| 1027 |
<p>The general purpose memory allocator is the most difficult memory pool |
| 1028 |
to manage because it supports allocations of varying sizes. Since |
| 1029 |
<b>n</b> is a multiplier on <b>M</b> we want to keep <b>n</b> as small |
| 1030 |
as possible. This argues for keeping the minimum allocation size for |
| 1031 |
<a href="malloc.html#memsys5">memsys5</a> as large as possible. In most applications, the |
| 1032 |
<a href="malloc.html#lookaside">lookaside memory allocator</a> is able to handle small allocations. So |
| 1033 |
it is reasonable to set the minimum allocation size for <a href="malloc.html#memsys5">memsys5</a> to |
| 1034 |
2, 4 or even 8 times the maximum size of a lookaside allocation. |
| 1035 |
A minimum allocation size of 512 is a reasonable setting.</p> |
| 1036 |
|
| 1037 |
<p>Further to keeping <b>n</b> small, one desires to keep the size of |
| 1038 |
the largest memory allocations under control. |
| 1039 |
Large requests to the general-purpose memory allocator |
| 1040 |
might come from several sources:</p> |
| 1041 |
|
| 1042 |
<ol> |
| 1043 |
<li>SQL table rows that contain large strings or BLOBs.</li> |
| 1044 |
<li>Complex SQL queries that compile down to large <a href="c3ref/stmt.html">prepared statements</a>.</li> |
| 1045 |
<li>SQL parser objects used internally by <a href="c3ref/prepare.html">sqlite3_prepare_v2()</a>.</li> |
| 1046 |
<li>Storage space for <a href="c3ref/sqlite3.html">database connection</a> objects.</li> |
| 1047 |
<li>Page cache memory allocations that overflow into the general-purpose |
| 1048 |
memory allocator.</li> |
| 1049 |
<li>Lookaside buffer allocations for new <a href="c3ref/sqlite3.html">database connections</a>.</li> |
| 1050 |
</ol> |
| 1051 |
|
| 1052 |
<p>The last two allocations can be controlled and/or eliminated by |
| 1053 |
configuring the <a href="malloc.html#pagecache">pagecache memory allocator</a>, |
| 1054 |
and <a href="malloc.html#lookaside">lookaside memory allocator</a> appropriately, as described above. |
| 1055 |
The storage space required for <a href="c3ref/sqlite3.html">database connection</a> objects depends |
| 1056 |
to some extent on the length of the filename of the database file, but |
| 1057 |
rarely exceeds 2KB on 32-bit systems. (More space is required on |
| 1058 |
64-bit systems due to the increased size of pointers.) |
| 1059 |
Each parser object uses about 1.6KB of memory. Thus, elements 3 through 6 |
| 1060 |
above can easily be controlled to keep the maximum memory allocation |
| 1061 |
size below 2KB.</p> |
| 1062 |
|
| 1063 |
<p>If the application is designed to manage data in small pieces, |
| 1064 |
then the database should never contain any large strings or BLOBs |
| 1065 |
and hence element 1 above should not be a factor. If the database |
| 1066 |
does contain large strings or BLOBs, they should be read using |
| 1067 |
<a href="c3ref/blob.html">incremental BLOB I/O</a> and rows that contain the |
| 1068 |
large strings or BLOBs should never be updated by any means other |
| 1069 |
than <a href="c3ref/blob.html">incremental BLOB I/O</a>. Otherwise, the |
| 1070 |
<a href="c3ref/step.html">sqlite3_step()</a> routine will need to read the entire row into |
| 1071 |
contiguous memory at some point, and that will involve at least |
| 1072 |
one large memory allocation.</p> |
| 1073 |
|
| 1074 |
<p>The final source of large memory allocations is the space to hold |
| 1075 |
the <a href="c3ref/stmt.html">prepared statements</a> that result from compiling complex SQL |
| 1076 |
operations. Ongoing work by the SQLite developers is reducing the |
| 1077 |
amount of space required here. But large and complex queries might |
| 1078 |
still require <a href="c3ref/stmt.html">prepared statements</a> that are several kilobytes in |
| 1079 |
size. The only workaround at the moment is for the application to |
| 1080 |
break complex SQL operations up into two or more smaller and simpler |
| 1081 |
operations contained in separate <a href="c3ref/stmt.html">prepared statements</a>.</p> |
| 1082 |
|
| 1083 |
<p>All things considered, applications should normally be able to |
| 1084 |
hold their maximum memory allocation size below 2K or 4K. This |
| 1085 |
gives a value for log<sub>2</sub>(<b>n</b>) of 2 or 3. This will |
| 1086 |
limit <b>N</b> to between 2 and 2.5 times <b>M</b>.</p> |
| 1087 |
|
| 1088 |
<p>The maximum amount of general-purpose memory needed by the application |
| 1089 |
is determined by such factors as how many simultaneous open |
| 1090 |
<a href="c3ref/sqlite3.html">database connection</a> and <a href="c3ref/stmt.html">prepared statement</a> objects the application |
| 1091 |
uses, and on the complexity of the <a href="c3ref/stmt.html">prepared statements</a>. For any |
| 1092 |
given application, these factors are normally fixed and can be |
| 1093 |
determined experimentally using <a href="c3ref/c_status_malloc_count.html#sqlitestatusmemoryused">SQLITE_STATUS_MEMORY_USED</a>. |
| 1094 |
A typical application might only use about 40KB of general-purpose |
| 1095 |
memory. This gives a value of <b>N</b> of around 100KB.</p> |
| 1096 |
|
| 1097 |
<h2 id="_ductile_failure"><span>4.2. </span> Ductile failure</h2> |
| 1098 |
|
| 1099 |
<p>If the memory allocation subsystems within SQLite are configured |
| 1100 |
for breakdown-free operation but the actual memory usage exceeds |
| 1101 |
design limits set by the <a href="malloc.html#nofrag">Robson proof</a>, SQLite will usually continue |
| 1102 |
to operate normally. |
| 1103 |
The <a href="malloc.html#pagecache">pagecache memory allocator</a> |
| 1104 |
and the <a href="malloc.html#lookaside">lookaside memory allocator</a> automatically failover |
| 1105 |
to the <a href="malloc.html#memsys5">memsys5</a> general-purpose memory allocator. And it is usually the |
| 1106 |
case that the <a href="malloc.html#memsys5">memsys5</a> memory allocator will continue to function |
| 1107 |
without fragmentation even if <b>M</b> and/or <b>n</b> exceeds the limits |
| 1108 |
imposed by the <a href="malloc.html#nofrag">Robson proof</a>. The <a href="malloc.html#nofrag">Robson proof</a> shows that it is |
| 1109 |
possible for a memory allocation to break down and fail in this |
| 1110 |
circumstance, but such a failure requires an especially |
| 1111 |
despicable sequence of allocations and deallocations - a sequence that |
| 1112 |
SQLite has never been observed to follow. So in practice it is usually |
| 1113 |
the case that the limits imposed by Robson can be exceeded by a |
| 1114 |
considerable margin with no ill effect.</p> |
| 1115 |
|
| 1116 |
<p>Nevertheless, application developers are admonished to monitor |
| 1117 |
the state of the memory allocation subsystems and raise alarms when |
| 1118 |
memory usage approaches or exceeds Robson limits. In this way, |
| 1119 |
the application will provide operators with abundant warning well |
| 1120 |
in advance of failure. |
| 1121 |
The <a href="malloc.html#memstatus">memory statistics</a> interfaces of SQLite provide the application with |
| 1122 |
all the mechanism necessary to complete the monitoring portion of |
| 1123 |
this task.</p> |
| 1124 |
|
| 1125 |
<a name="stability"></a> |
| 1126 |
<h1 id="_stability_of_memory_interfaces"><span>5. </span> Stability Of Memory Interfaces</h1> |
| 1127 |
|
| 1128 |
<p><b>Update:</b> As of SQLite version 3.7.0 (2010-07-21), |
| 1129 |
all of SQLite memory allocation interfaces |
| 1130 |
are considered stable and will be supported in future releases.</p> |
| 1131 |
<p align="center"><small><i>This page was last updated on 2025-11-13 07:12:58Z </small></i></p> |
| 1132 |
|