Documentation Source Text

Check-in [f0f85bacb3]
Login

Many hyperlinks are disabled.
Use anonymous login to enable hyperlinks.

Overview
Comment:Continuing work on the malloc.html document.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: f0f85bacb331c75b1f243235b090da86c6fb6d50
User & Date: drh 2008-08-05 03:35:00
Context
2008-08-05
18:37
Last minute updatest to the documentation before 3.6.1. check-in: 57f8360ad3 user: drh tags: trunk
03:35
Continuing work on the malloc.html document. check-in: f0f85bacb3 user: drh tags: trunk
2008-08-04
22:01
Updates to the malloc.html document. check-in: 2722f22a04 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to pages/malloc.in.

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
...
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
...
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
...
275
276
277
278
279
280
281
282


283
284
285
286
287
288
289
290
291
292
...
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
...
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
...
578
579
580
581
582
583
584
585
586
587

588
589
590
591
592
593
594
595
...
603
604
605
606
607
608
609

610
611
612
613
614
615
616
617
618
...
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
...
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
...
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
...
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
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 try to
find the memory it needs from a backup memory source.  (Details
are provided below.)
Failing that, SQLite will either stop what
it is doing and return the
[SQLITE_NOMEM] error code back up to the application or it will
make due without the requested memory.
</p></li>

<li><p>
<b>No memory leaks.</b>
The application must destroy 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>
................................................................................
</p></li>

</ul>

<a name="testing"></a>
<h2>2.0 Testing</h2>

<p>The source code to SQLite consists mostly of test cases.  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>

................................................................................

<tcl>hd_fragment memsys5 memsys5</tcl>
<h4>3.1.3 Zero-malloc memory allocator</h4>

<p>When SQLite is compiled with the [SQLITE_ENABLE_MEMSYS5] 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 ina build, memsys5 is not 
enabled by default.
To enable memsys5, the application must invoke the following SQLite 
interface at start-time:</p>

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_HEAP], pBuf, szBuf, mnReq);
</pre></blockquote>

................................................................................
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.</p>



<p>The memsys5 allocator is designed for use on embedded systems, 
though there is nothing to prevent its use on workstations if desired.
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
................................................................................
SQLite falls back to using the regular memory allocator for its scratch
memory allocations.  The default setup is sz=0 and N=0 so the use
of the regular memory allocator is the default behavior.</p>

<tcl>hd_fragment pagecache {pagecache memory allocator}</tcl>
<h3>3.3 Page cache memory</h3>

<p>The database page cache subsystem within SQLite uses more
dynamically allocated memory than any other part of SQLite.  In fact,
the database page cache typically consumes over 10 times more memory
than all other parts of SQLite combined.</p>

<p>SQLite can be configured to make page cache memory allocations from
a separate memory pool, distinct from the memory pool where other allocations
are drawn from.  This can have two advantages:</p>

<ul>
<li><p>
Because allocations are all the same size, the memory allocator has much
less work to do for allocating and freeing and hence runs faster.




</p></li>

<li><p>
Because allocations are all the same size, the <b>n</b> parameter in the
[Robson proof] 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.


</p></li>
</ul>

<p>The page-cache memory allocator is disabled by default.
An application can enabled it at start-time as follows:</p>

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_PAGECACHE], pBuf, sz, N);
</pre></blockquote>

<p>The pBuf parameter is a pointer to a contiguous range of bytes that
SQLite will use for for page-cache memory allocations.  The buffer must be
at least sz*N bytes in size.  The "sz" parameter
is the maximum 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>

<tcl>hd_fragment lookaside {lookaside memory allocator}</tcl>
<h3>3.4 Lookaside memory allocator</h3>

<p>SQLite [database connections] make numerous
small and short-lived memory allocations.
This occurs most commonly when compiling SQL statements using
[sqlite3_prepare_v2()] but also to a lessor extent when running
[prepared statements] using [sqlite3_step()].  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.  These small memory allocations result
in 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 [version 3.6.1] introduced the lookaside memory allocator to
help reduce the memory allocation load.  In the lookaside allocator,
each [database connection] preallocates a single large chunk of memory
(typically in the range of 50 to 100 kilobytes) and divides that chunk
up into small fixed-size "slots" of around 50 to 200 byte each.  This
becomes the lookaside memory pool.  Thereafter, memory allocations
associated with the [database connection] and that are small enough are
allocated as one of the pieces of the lookaside pool 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 all the lookaside pool slots are already 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 fast and efficient.  There is no
need to coalesce adjacent free slots nor search for a slot
of a particular size.  Each [database connection] maintains a singly-linked
list of unused slots.  Allocation requests simply pull the first
element of this list.  Decallocations simply push the element back onto
the front of the list.
Furthermore, each [database connection] is assumed to already be
running in a single thread (and in fact there are mutexes already in
place to enforce this) so no mutexing is required to pull or push

entries from the lookaside 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
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.
................................................................................

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_LOOKASIDE], sz, cnt);
</pre></blockquote>

<p>The "sz" parameter is the size in bytes of each lookaside slot.
The default is 100 bytes.  The "cnt" parameter is
the total number of lookaside memory slots.  The default value is 500
slots. The total amount
of lookaside memory allocated to each [database connection] is
sz*cnt bytes.  Hence the lookaside memory pool allocated per database 
connection by default is 50 kilobytes in size.
(Note: these default values are for SQLite [version 3.6.1] and are subject
to changes in future releases.)
</p>

<p>The lookaside pool can be changed for an individual
[database connection] "db" using this call:</p>

................................................................................
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 [Robson proof] and hence that the memory allocation subsystem is 
liable to breakdown.</p>

<p>Most memory statistics are global, and hence the tracking of
statistics requires a mutex.  Statistics are turned on by default,
but an option exists to disable them.  By disabling memory statistics,

SQLite avoids entrying and leave a mutex on each memory allocation
and deallocation.  That savings can be noticable on systems where
mutex operations are expensive.  To disable memory statistics, the
following interface is used at start-time:</p>

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_MEMSTATUS], onoff);
</pre></blockquote>
................................................................................
<blockquote><pre>
[sqlite3_status]([SQLITE_STATUS_MEMORY_USED|verb], &current, &highwater, resetflag);
</pre></blockquote>

<p>The "verb" argument determines what statistic is accessed.
There are [SQLITE_STATUS_MEMORY_USED | various verbs] defined.  The
list is expected to grow as the [sqlite3_status()] interface matures.

The current value is written into integer "current" and the high-water
marks 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 [database connection]:</p>

<blockquote><pre>
................................................................................
the [pagecache memory allocator], or the [lookaside memory allocator].
This deficiency will likely be addressed in a future release.</p>

<tcl>hd_fragment nofrag {Robson proof}</tcl>
<h2>4.0 Mathematical Guarantees Against Memory Allocation Failures</h2>

<p>The problem of dynamic memory allocation, and specifically the
problem of a memory allocator breaking down and failing to return
requested memory, has been studied by
J. M. Robson and the results published in 1974 as:</p>

<blockquote>
J. M. Robson.  "Bounds for Some Functions Concerning Dynamic
Storage Allocation".  <i>Jounral of the Association for
Computing Machinery</i>, Volume 21, Number 8, July 1974,
pages 491-499.
</blockquote>

<p>Define 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
................................................................................

<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>The proof is constructive. 
Robson provides an algorithm for computing a sequence of malloc()
and free() operations that will lead to a malloc() failure due to
memory fragmentation if available memory is as much as one byte
less than <b>N</b>.
And, he shows that a power-of-two first-fit memory allocator
(such as implemented by [memsys5]) 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 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 it uses

the [memsys5] memory allocator and is provided with <b>N</b> bytes of
available memory space using [sqlite3_config]([SQLITE_CONFIG_HEAP],...),
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> which will guarantee that no call to any SQLite interface
will ever return [SQLITE_NOMEM].  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,
loss of irreplaceable data, or significant financial loss.</p>

<h3>4.1 Computing and controlling parameters <b>M</b> and <b>n</b></h3>

<p>The Robson proof applies separately to each of the memory allocators
used by SQLite:</p>

<ul>
<li>The general-purpose memory allocator (usually [memsys5] for
    applications that care about the Robson proof.)</li>
<li>The [scratch memory allocator].</li>
<li>The [pagecache memory allocator].</li>
<li>The [lookaside memory allocator].</li>
</ul>

<p>For all memory allocators other than the general-purpose memory
allocator, 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>SQLite guarantees that no thread will ever use more than a single
scratch memory slot at one time.  So if an application allocates as many
scratch memory slots as there are threads, and assuming the the size of
each slot is large enough, there is never a chance of overflowing the
scratch memory allocator.  An upper bound on the size of scratch memory
allocations is six times the largest page size.  It is easy, therefore,
to guarantee breakdown-free operation of the scratch memory allocator.
Simply assign buffers shows size is larger than six times the maximum
page size and at least one buffer per thread.</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 [cache_size pragma].</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 opertions.</p>

<p>The general purpose memory allocator is the most difficult memory pool
to manage, since it support 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
[memsys5] as large as possible.  In most appliations, the
[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>Large memory allocations 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>
<li>Scratch memory allocations that overflow into the general-purpose
................................................................................
    memory allocator.</li>
<li>Page cache memory allocations that overflow into the general-purpose
    memory allocator.</li>
<li>Lookaside buffer allocations for new [database connections].</li>
</ol>

<p>The last three allocations can be controlled and/or eliminated by
configuring the scratch memory allocator, pagecache memory allocator,
and lookaside memory allocator appropriate, as described above.
The storage space required for [database connection] 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 7
above can easily be controlled to keep the maximum memory allocation
size below 2KB.</p>
................................................................................

<p>The final source of large memory allocations is the space to hold
the [prepared statements] 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 [prepared statements] 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 smaller and simpler 
operations contained in separate [prepared statements].</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 
[database connection] and [prepared statement] objects the application
uses, and on the complexity of the [prepared statements].  For any
given application, these factors are normally fixed and can be
determined experiementally using [SQLITE_STATUS_MEMORY_USED].
A typical application might only use about 40KB of general-purpose
memory.  This gives a value of <b>N</b> of about 100KB.</p>

<h3>4.2 Ductile failure</h3>

<p>Safety-critical appliations should include a safety margin
in memory sizing calculations and should monitor memory usage at
run-time using the [sqlite3_status()] and [sqlite3_db_status()] 
interfaces to make sure that memory usage does not exceed design 
limits.  Nevertheless, we observe that even if memory usage does
exceed limits, SQLite will usually continue to operate normally.
The [scratch memory allocator], the [pagecache memory allocator],
and the [lookaside memory allocator] all automatically failover
to the general-purpose memory allocator.  And it is usually the
case that the [memsys5] memory allocator will continue to function
without fragmentation even if <b>M</b> exceeds the <b>N/n</b> limit

imposed by the Robson proof.  It is possible for a memory allocation
to fail in this circumstance, but a failure requires an especially
dispicable sequence of allocations and deallocations - a sequence that
SQLite has never been observed to follow.  So it is often the case
that the limits imposed by Robson can be exceeded by a factor of
two with not ill effect. </p>











<a name="stability"></a>
<h2>5.0 Stability Of Memory Interfaces</h2>

<p>As of this writing (circa SQLite version 3.6.1) all of the alternative
memory allocators and mechanisms for manipulating, controlling, and
measuring memory allocation in SQLite are considered experimental and







|
|
|








|







 







|







 







|
|







 







|
>
>


|







 







|
|
|
|


|
|



|
|
>
>
>
>



|



|
>
>













|









|






|
|









|
|


|






|






|
|
>
|







 







|
|


|







 







|
|
|
>
|







 







>
|
|







 







|
<
|



|




|







 







>
>
>
>
>
>
>
>
>
>
>
>
|
|
|


|





|
>

|







|
|







|
<





|
|









|
<
<







 







|











>
>
>
|







 







|
|







 







|







 







|



|
|
|
<
<
|


|

|
>
|
|

|
|
<
>
>
>
>
>
>
>
>
>
>







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
...
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
...
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
...
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
...
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
...
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
...
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
...
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
...
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
...
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
...
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
...
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
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
[SQLITE_NOMEM] error code back up to the application or it will
make due without the requested memory.
</p></li>

<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>
................................................................................
</p></li>

</ul>

<a name="testing"></a>
<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>

................................................................................

<tcl>hd_fragment memsys5 memsys5</tcl>
<h4>3.1.3 Zero-malloc memory allocator</h4>

<p>When SQLite is compiled with the [SQLITE_ENABLE_MEMSYS5] 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>
[sqlite3_config]([SQLITE_CONFIG_HEAP], pBuf, szBuf, mnReq);
</pre></blockquote>

................................................................................
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
................................................................................
SQLite falls back to using the regular memory allocator for its scratch
memory allocations.  The default setup is sz=0 and N=0 so the use
of the regular memory allocator is the default behavior.</p>

<tcl>hd_fragment pagecache {pagecache memory allocator}</tcl>
<h3>3.3 Page cache memory</h3>

<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
consumes 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 nor 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
[Robson proof] 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 enabled it at start-time as follows:</p>

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_PAGECACHE], pBuf, sz, N);
</pre></blockquote>

<p>The pBuf parameter is a pointer to a contiguous range of bytes that
SQLite will use for 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>

<tcl>hd_fragment lookaside {lookaside memory allocator}</tcl>
<h3>3.4 Lookaside memory allocator</h3>

<p>SQLite [database connections] make many
small and short-lived memory allocations.
This occurs most commonly when compiling SQL statements using
[sqlite3_prepare_v2()] but also to a lessor extent when running
[prepared statements] using [sqlite3_step()].  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 [version 3.6.1] introduced the lookaside memory allocator to
help reduce the memory allocation load.  In the lookaside allocator,
each [database connection] preallocates a single large chunk of memory
(typically in the range of 50 to 100 kilobytes) and divides that chunk
up into small fixed-size "slots" of around 50 to 200 byte each.  This
becomes the lookaside memory pool.  Thereafter, memory allocations
associated with the [database connection] and that are not too larger
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 nor search for a slot
of a particular size.  Each [database connection] maintains a singly-linked
list of unused slots.  Allocation requests simply pull the first
element of this list.  Decallocations simply push the element back onto
the front of the list.
Furthermore, each [database connection] 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
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.
................................................................................

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_LOOKASIDE], sz, cnt);
</pre></blockquote>

<p>The "sz" parameter is the size in bytes of each lookaside slot.
The default is 100 bytes.  The "cnt" parameter is
the total number of lookaside memory slots per database connection.
The default value is 500 slots. The total amount
of lookaside memory allocated to each [database connection] is
sz*cnt bytes.  Hence the lookaside memory pool allocated per database 
connection is 50 kilobytes by default.
(Note: these default values are for SQLite [version 3.6.1] and are subject
to changes in future releases.)
</p>

<p>The lookaside pool can be changed for an individual
[database connection] "db" using this call:</p>

................................................................................
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 [Robson proof] 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 entrying and leaving a mutex on each memory allocation
and deallocation.  That savings can be noticable on systems where
mutex operations are expensive.  To disable memory statistics, the
following interface is used at start-time:</p>

<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_MEMSTATUS], onoff);
</pre></blockquote>
................................................................................
<blockquote><pre>
[sqlite3_status]([SQLITE_STATUS_MEMORY_USED|verb], &current, &highwater, resetflag);
</pre></blockquote>

<p>The "verb" argument determines what statistic is accessed.
There are [SQLITE_STATUS_MEMORY_USED | various verbs] defined.  The
list is expected to grow as the [sqlite3_status()] 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 [database connection]:</p>

<blockquote><pre>
................................................................................
the [pagecache memory allocator], or the [lookaside memory allocator].
This deficiency will likely be addressed in a future release.</p>

<tcl>hd_fragment nofrag {Robson proof}</tcl>
<h2>4.0 Mathematical Guarantees Against Memory Allocation Failures</h2>

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

<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>Colloqually, 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 every
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 a 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 [memsys5]) 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 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 [memsys5] memory allocator and is provided with <b>N</b> bytes of
available memory space using [SQLITE_CONFIG_HEAP]
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> which will guarantee that no call to any SQLite interface
will ever return [SQLITE_NOMEM].  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>

<h3>4.1 Computing and controlling parameters <b>M</b> and <b>n</b></h3>

<p>The Robson proof applies separately to each of the memory allocators
used by SQLite:</p>

<ul>
<li>The general-purpose memory allocator ([memsys5]).</li>

<li>The [scratch memory allocator].</li>
<li>The [pagecache memory allocator].</li>
<li>The [lookaside memory allocator].</li>
</ul>

<p>For allocators other than [memsys5],
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>SQLite guarantees that no thread will ever use more than a single
scratch memory slot at one time.  So if an application allocates as many
scratch memory slots as there are threads, and assuming the the size of
each slot is large enough, there is never a chance of overflowing the
scratch memory allocator.  An upper bound on the size of scratch memory
allocations is six times the largest page size.  It is easy, therefore,
to guarantee breakdown-free operation of the scratch memory allocator.</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 [cache_size pragma].</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, since it support 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
[memsys5] as large as possible.  In most appliations, the
[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>
<li>Scratch memory allocations that overflow into the general-purpose
................................................................................
    memory allocator.</li>
<li>Page cache memory allocations that overflow into the general-purpose
    memory allocator.</li>
<li>Lookaside buffer allocations for new [database connections].</li>
</ol>

<p>The last three allocations can be controlled and/or eliminated by
configuring the [scratch memory allocator], [pagecache memory allocator],
and [lookaside memory allocator] appropriately, as described above.
The storage space required for [database connection] 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 7
above can easily be controlled to keep the maximum memory allocation
size below 2KB.</p>
................................................................................

<p>The final source of large memory allocations is the space to hold
the [prepared statements] 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 [prepared statements] 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 [prepared statements].</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 
[database connection] and [prepared statement] objects the application
uses, and on the complexity of the [prepared statements].  For any
given application, these factors are normally fixed and can be
determined experiementally using [SQLITE_STATUS_MEMORY_USED].
A typical application might only use about 40KB of general-purpose
memory.  This gives a value of <b>N</b> of around 100KB.</p>

<h3>4.2 Ductile failure</h3>

<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 [Robson proof], SQLite will usually continue 


to operate normally.
The [scratch memory allocator], the [pagecache memory allocator],
and the [lookaside memory allocator] all automatically failover
to the [memsys5] general-purpose memory allocator.  And it is usually the
case that the [memsys5] memory allocator will continue to function
without fragmentation even if <b>M</b> and/or <b>n</b> exceeds the limits
imposed by the [Robson proof].  The [Robson proof] shows that it is 
possible for a memory allocation to break down and fail in this 
circumstance, but such a failure requires an especially
dispicable 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 [memory statistics] interfaces of SQLite provides the application with
all the mechanism necessary to complete the monitoring portion of
this task.</p>

<a name="stability"></a>
<h2>5.0 Stability Of Memory Interfaces</h2>

<p>As of this writing (circa SQLite version 3.6.1) all of the alternative
memory allocators and mechanisms for manipulating, controlling, and
measuring memory allocation in SQLite are considered experimental and