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