Debian Codegraph @

www/malloc.html

raw
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>, &amp;current, &amp;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>, &amp;current, &amp;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