Documentation Source Text

Check-in [98e50e4e24]
Login

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: 98e50e4e24c34355e1aaa4033286c216cb753bb1
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
Unified Diff Ignore Whitespace Patch
Changes to pages/malloc.in.
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 makes extensive use of dynamic memory allocation to obtain
the memory it needs to store 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





|
|







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
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 of 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







|







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
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 responses
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 definitely 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







|







|







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
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 spotted and quinched.</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 application.  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







|







|







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
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 are 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 implementation 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>








|




















|







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
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 memry 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 that 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>







|














|







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
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 for use 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







|







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

414
415
416
417
418
419
420
421
422
423
424
425
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 stack approach 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>







>
|



|







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
832
833
834
835
836
837
838
839
[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 memory allocations against 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>







|







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>