Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
Comment: | Updates to the malloc document. |
---|---|
Downloads: | Tarball | ZIP archive |
Timelines: | family | ancestors | descendants | both | trunk |
Files: | files | file ages | folders |
SHA1: |
98e50e4e24c34355e1aaa4033286c216 |
User & Date: | drh 2008-09-09 15:12:54.000 |
Context
2008-09-18
| ||
15:22 | Documentation updates for version 3.6.3. (check-in: 49535dba2b user: drh tags: trunk) | |
2008-09-09
| ||
15:12 | Updates to the malloc document. (check-in: 98e50e4e24 user: drh tags: trunk) | |
13:48 | Work on requirements in fileio.html. (check-in: c3a0f6d745 user: dan tags: trunk) | |
Changes
Changes to pages/malloc.in.
1 2 3 4 5 | <title>Dynamic Memory Allocation In SQLite</title> <h1>Dynamic Memory Allocation In SQLite</h1> <tcl>hd_keywords {memory allocation}</tcl> | | | | 1 2 3 4 5 6 7 8 9 10 11 12 13 14 | <title>Dynamic Memory Allocation In SQLite</title> <h1>Dynamic Memory Allocation In SQLite</h1> <tcl>hd_keywords {memory allocation}</tcl> <p>SQLite uses of dynamic memory allocation to obtain memory for storing various objects (ex: [database connections] and [prepared statements]) and to build a memory cache of the database file and to hold the results of queries. Much effort has gone into making the dynamic memory allocation subsystem of SQLite reliable, predictable, robust, and efficient.</p> <p>This document provides an overview of dynamic memory allocation within SQLite. The target audience is software engineers who are tuning their |
︙ | ︙ | |||
44 45 46 47 48 49 50 | <li><p> <b>No memory leaks.</b> The application is resposible for destroying any objects it allocates. (For example, the application must use [sqlite3_finalize()] on every [prepared statement] and [sqlite3_close()] on every [database connection].) But as long as the application cooperates, SQLite will never leak memory. This is | | | 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 | <li><p> <b>No memory leaks.</b> The application is resposible for destroying any objects it allocates. (For example, the application must use [sqlite3_finalize()] on every [prepared statement] and [sqlite3_close()] on every [database connection].) But as long as the application cooperates, SQLite will never leak memory. This is true even in the face of memory allocation failures or other system errors. </p></li> <li><p> <b>Memory usage limits.</b> The [sqlite3_soft_heap_limit()] mechanism allows the application to set a memory usage limit that SQLite strives to stay below. SQLite |
︙ | ︙ | |||
111 112 113 114 115 116 117 | <h2>2.0 Testing</h2> <p>Over 75% of the code in the SQLite source tree is devoted purely to testing and verification. Reliability is important to SQLite. Among the tasks of the test infrastructure is to insure that SQLite does not misuse dynamically allocated memory, that SQLite | | | | 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 | <h2>2.0 Testing</h2> <p>Over 75% of the code in the SQLite source tree is devoted purely to testing and verification. Reliability is important to SQLite. Among the tasks of the test infrastructure is to insure that SQLite does not misuse dynamically allocated memory, that SQLite does not leak memory, and that SQLite responds correctly to a dynamic memory allocation failure.</p> <p>The test infrastructure verifies that SQLite does not misuse dynamically allocated memory by using a specially instrumented memory allocator. The instrumented memory allocator is enabled at compile-time using the [SQLITE_MEMDEBUG] option. The instrumented memory allocator is much slower than the default memory allocator and so its use is not recommended in production. But when enabled during testing, the instrumented memory allocator performs the following checks:</p> <ul> <li><p><b>Bounds checking.</b> The instrumented memory allocator places sentinal values at both ends of each memory allocation to verify that nothing within SQLite writes |
︙ | ︙ | |||
154 155 156 157 158 159 160 | There are hundreds of test scripts used for testing SQLite. At the end of each script, all objects are destroyed and a test is made to insure that all memory has been freed. This is how memory leaks are detected. Notice that memory leak detection is in force at all times, during test builds and during production builds. Whenever one of the developers runs any individual test script, memory leak detection is active. Hence memory leaks that do arise during development | | | | 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 | There are hundreds of test scripts used for testing SQLite. At the end of each script, all objects are destroyed and a test is made to insure that all memory has been freed. This is how memory leaks are detected. Notice that memory leak detection is in force at all times, during test builds and during production builds. Whenever one of the developers runs any individual test script, memory leak detection is active. Hence memory leaks that do arise during development are quickly detected and fixed.</p> <a name="oomtesting"></a> <p>The response of SQLite to out-of-memory (OOM) errors is tested using a specialized memory allocator overlay that can simulate memory failures. The overlay is a layer that is inserted in between the memory allocator and the rest of SQLite. The overlay passes most memory allocation requests straight through to the underlying allocator and passes the results back up to the requester. But the overlay can be set to cause the Nth memory allocation to fail. To run an OOM test, the overlay is first set to fail on the first allocation attempt. Then some test script is run and a verification that the allocation was correctly caught and handled is made. Then the overlay is set to fail on the second allocation and the test repeats. The failure point continues to advice one allocation at a time until the entire test procedure runs to completion without hitting a memory allocation error. This whole |
︙ | ︙ | |||
192 193 194 195 196 197 198 | strong evidence that dynamic memory allocation is used correctly everywhere within SQLite.</p> <a name="config"></a> <h2>3.0 Configuration</h2> <p>The default memory allocation settings in SQLite are appropriate | | | | 192 193 194 195 196 197 198 199 200 201 202 203 204 205 206 207 208 209 210 211 212 213 214 215 216 217 218 219 220 221 222 223 224 225 226 227 | strong evidence that dynamic memory allocation is used correctly everywhere within SQLite.</p> <a name="config"></a> <h2>3.0 Configuration</h2> <p>The default memory allocation settings in SQLite are appropriate for most applications. However, applications with unusual or particularly strict requirements may want to adjust the configuation to more closely align SQLite to their needs. Both compile-time and start-time configuration options are available.</p> <a name="altalloc"></a> <h3>3.1 Alternative low-level memory allocators</h3> <p>The SQLite source code includes several different memory allocation modules that can be selected at compile-time, or to a limited extent at start-time.</p> <a name="defaultalloc"></a> <h4>3.1.1 The default memory allocator</h4> <p>By default, SQLite uses the malloc(), realloc(), and free() routines from the standard C library for its memory allocation needs. These routines are surrounded by a thin wrapper that also provides a "memsize()" function that will return the size of an existing allocation. The memsize() function is needed to keep an accurate count of the number of bytes of outstanding memory; memsize() determines how many bytes to remove from the outstanding count when an allocation is freed. The default allocator implements memsize() by always allocating 8 extra bytes on each malloc() request and storing the size of the allocation in that 8-byte header.</p> <p>The default memory allocator is recommended for most applications. If you do not have a compelling need to use an alternative memory allocator, then use the default.</p> |
︙ | ︙ | |||
271 272 273 274 275 276 277 | [sqlite3_config]([SQLITE_CONFIG_HEAP], pBuf, szBuf, mnReq); </pre></blockquote> <p>In the call above, pBuf is a pointer to a large, contiguous chunk of memory space that SQLite will use to satisfy all of its memory allocation needs. pBuf might point to a static array or it might be memory obtained from some other application-specific mechanism. | | | | 271 272 273 274 275 276 277 278 279 280 281 282 283 284 285 286 287 288 289 290 291 292 293 294 295 296 297 298 299 300 | [sqlite3_config]([SQLITE_CONFIG_HEAP], pBuf, szBuf, mnReq); </pre></blockquote> <p>In the call above, pBuf is a pointer to a large, contiguous chunk of memory space that SQLite will use to satisfy all of its memory allocation needs. pBuf might point to a static array or it might be memory obtained from some other application-specific mechanism. szBuf is an integer which is the number of bytes of memroy space pointed to by pBuf. mnReq is another integer which is the minimum size of an allocation. Any call to [sqlite3_malloc(N)] where N is less than mnReq will be rounded up to mnReq. mnReq must be a power of two. We shall see later that the mnReq parameter is important in reducing the value of <b>n</b> and hence the minimum memory size requirement in the [Robson proof].</p> <p>The memsys5 allocator is designed for use on embedded systems, though there is nothing to prevent its use on workstations. The szBuf is typically between a few hundred kilobytes up to a few dozen megabytes, depending on system requirements and memory budget.</p> <p>The algorithm used by memsys5 is can be called "power-of-two, first-fit". The sizes of all memory allocation requests are rounded up to a power of two and the request is satisfied by the first free slot in pBuf that is large enough. Adjacent freed allocations are coalesced using a buddy system. When used appropriately, this algorithm provides mathematical guarantees against fragmentation and breakdown, as described further <a href="#nofrag">below</a>.</p> <a name="memsysx"></a> <h4>3.1.4 Experimental memory allocators</h4> |
︙ | ︙ | |||
319 320 321 322 323 324 325 | allocator should use memsys5 in preference to memsys3. Memsys3 is considered both experimental and deprecated and will likely be removed from the source tree in a future release of SQLite.</p> <p>Code for memsys4 is still in the SQLite source tree (as of this writing - SQLite release 3.6.1), but it has not been maintained for several release cycles and probably does not work. Memsys4 was an attempt to use mmap() | | | 319 320 321 322 323 324 325 326 327 328 329 330 331 332 333 | allocator should use memsys5 in preference to memsys3. Memsys3 is considered both experimental and deprecated and will likely be removed from the source tree in a future release of SQLite.</p> <p>Code for memsys4 is still in the SQLite source tree (as of this writing - SQLite release 3.6.1), but it has not been maintained for several release cycles and probably does not work. Memsys4 was an attempt to use mmap() to obtain memory and then use madvise() to release unused pages back to the operating system so that they could be reused by other processes. The target platform for memsys4 was Google Android. The work on memsys4 has been abandoned and the memsys4 module will likely be removed from the source tree in the near future.</p> <p>Memsys6 uses system malloc() and free() to obtain the memory it needs. Memsys6 serves as an aggregator. Memsys6 only calls system malloc() to obtain |
︙ | ︙ | |||
407 408 409 410 411 412 413 | as temporary storage when rebalancing a btree. These scratch memory allocations are typically about 10 kilobytes in size and are transient - lasting only for the duration of a single, short-lived function call.</p> <p>In older versions of SQLite, the scratch memory was obtained from the processor stack. That works great on workstations with a large stack. | > | | | 407 408 409 410 411 412 413 414 415 416 417 418 419 420 421 422 423 424 425 426 | as temporary storage when rebalancing a btree. These scratch memory allocations are typically about 10 kilobytes in size and are transient - lasting only for the duration of a single, short-lived function call.</p> <p>In older versions of SQLite, the scratch memory was obtained from the processor stack. That works great on workstations with a large stack. But pulling large buffers from the stack caused problems on embedded systems with a small processor stack (typically 4K or 8K). And so SQLite was modified to allocate scratch memory from the heap.</p> <p>However, doing occasional large transient allocations from the heap can lead to memory fragmentation in embedded systems. To work around this problem, a separate memory allocation system for scratch memory has been created.</p> <p>The scratch memory allocator is set up as follows:</p> <blockquote><pre> |
︙ | ︙ | |||
825 826 827 828 829 830 831 | [lookaside memory allocator] is able to handle small allocations. So it is reasonable to set the minimum allocation size for [memsys5] to 2, 4 or even 8 times the maximum size of a lookaside allocation. A minimum allocation size of 512 is a reasonable setting.</p> <p>Further to keeping <b>n</b> small, one desires to keep the size of the largest memory allocations under control. | | | 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 | [lookaside memory allocator] is able to handle small allocations. So it is reasonable to set the minimum allocation size for [memsys5] to 2, 4 or even 8 times the maximum size of a lookaside allocation. A minimum allocation size of 512 is a reasonable setting.</p> <p>Further to keeping <b>n</b> small, one desires to keep the size of the largest memory allocations under control. Large requests to the general-purpose memory allocator might come from several sources:</p> <ol> <li>SQL table rows that contain large strings or blobs.</li> <li>Complex SQL queries that compile down to large [prepared statements].</li> <li>SQL parser objects used internally by [sqlite3_prepare_v2()].</li> <li>Storage space for [database connection] objects.</li> |
︙ | ︙ |