Documentation Source Text

Check-in [d482cfb5ea]
Login

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

Overview
Comment:Remove the scratch memory allocator.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA3-256: d482cfb5eac713f8d20a364b5ccf2c7e45e57f5eebc0242a0cf5a02b69adc86f
User & Date: drh 2017-08-29 13:19:37
Context
2017-08-30
04:46
Update the CPU usage improvement for 3.21.0. check-in: 4ea4e27dc5 user: drh tags: trunk
2017-08-29
13:19
Remove the scratch memory allocator. check-in: d482cfb5ea user: drh tags: trunk
2017-08-25
17:54
Update the change log for 3.21.0. check-in: 2d9f1292ff user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to pages/changes.in.

42
43
44
45
46
47
48



49
50
51
52
53
54
55
<li> Fewer "stat()" system calls issued by the unix VFS.
<li> Query planner enhancements:
<ol type="a">
<li> Enhanced the [LIKE optimization] so that it works with an ESCAPE clause.
</ol>
<li> Enhanced the [CSV virtual table] so that it accepts the last row of
     input if the final new-line character is missing.



<li> Added the swarm virtual table to the existing union virtual table extension.
<li> Miscellaneous [microoptimizations] reduce CPU usage by about 1.6%.
<li> Bug fixes:
<ol type="a">
<li> Fix a faulty assert() statement discovered by OSSFuzz.
     Ticket [https://sqlite.org/src/info/cb91bf4290c211d|cb91bf4290c211d]
<li> Fix an obscure memory leak in [sqlite3_result_pointer()].







>
>
>







42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
<li> Fewer "stat()" system calls issued by the unix VFS.
<li> Query planner enhancements:
<ol type="a">
<li> Enhanced the [LIKE optimization] so that it works with an ESCAPE clause.
</ol>
<li> Enhanced the [CSV virtual table] so that it accepts the last row of
     input if the final new-line character is missing.
<li> Remove the rarely-used "scratch" memory allocator.  Replace it with the
     [SQLITE_CONFIG_SMALL_MALLOC] configuration setting that gives SQLite
     a hint large memory allocations should be avoided when possible.
<li> Added the swarm virtual table to the existing union virtual table extension.
<li> Miscellaneous [microoptimizations] reduce CPU usage by about 1.6%.
<li> Bug fixes:
<ol type="a">
<li> Fix a faulty assert() statement discovered by OSSFuzz.
     Ticket [https://sqlite.org/src/info/cb91bf4290c211d|cb91bf4290c211d]
<li> Fix an obscure memory leak in [sqlite3_result_pointer()].

Changes to pages/malloc.in.

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
...
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
...
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
...
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
...
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
...
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
on systems that may not have malloc(), free(), or realloc() in their
standard library.
An application that is compiled with [SQLITE_ZERO_MALLOC] will need to
use [sqlite3_config()] together with [SQLITE_CONFIG_MALLOC] or
[SQLITE_CONFIG_HEAP] to specify a new alternative memory allocator
before beginning to use SQLite.</p>

<tcl>hd_fragment scratch {scratch memory allocator}</tcl>
<h2> Scratch memory</h2>

<p>SQLite occasionally needs a large chunk of "scratch" memory to
perform some transient calculation.  Scratch memory is used, for example,
as temporary storage when rebalancing a B-Tree.  These scratch memory
allocations are typically about 10 kilobytes in size and are
transient - lasting
only for the duration of a single, short-lived function call.</p>

<p>In older versions of SQLite, the scratch memory was obtained from
the processor stack.  That works great on workstations with a large stack.
But pulling large buffers from the stack 
caused problems on embedded systems with a 
small processor stack (typically 4K or 8K).  And so SQLite was modified
to allocate scratch memory from the heap.</p>

<p>However, doing occasional large transient allocations from the heap can
lead to memory fragmentation in embedded systems.  To work around this
problem, a separate memory allocation system for scratch memory has been
created.</p>

<p>The scratch memory allocator is set up as follows:</p>

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

<p>The pBuf parameter is a pointer to a contiguous range of bytes that
SQLite will use for all scratch memory allocations.  The buffer must be
at least sz*N bytes in size.  The "sz" parameter
is the maximum size of each scratch allocation.  N is the maximum 
number of simultaneous scratch allocations.  The "sz" parameter should
be approximately 6 times the maximum database page size.  N should
be twice the number of threads running in the system.  No single thread will
ever request more than two scratch allocation at a time so if there
are never more than N threads, then there will always be enough scratch
memory available.</p>

<p>If the scratch memory setup does not define enough memory, then
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>
<h2> 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 [version 3.6.1] ([dateof: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 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 [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
................................................................................
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 [version 3.6.1] ([dateof:3.6.1]), 
the soft heap limit only applies to the
general-purpose memory allocator.  The soft heap limit does not know
about or interact with the [scratch memory allocator], 
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>
<h1> 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
................................................................................
<h2> 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 ([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 two
scratch memory slots at one time.  So if an application allocates twice as many
scratch memory slots as there are threads, and assuming 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>

<p>Safety-critical applications will usually want to modify the
................................................................................
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
................................................................................

<h2> 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 [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
despicable sequence of allocations and deallocations - a sequence that







<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<
<







 







|







 







|
|







 







<









<
<
<
<
<
<
<
<







 







<
<





|
|







 







|
|







449
450
451
452
453
454
455












































456
457
458
459
460
461
462
...
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
...
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
...
767
768
769
770
771
772
773

774
775
776
777
778
779
780
781
782








783
784
785
786
787
788
789
...
840
841
842
843
844
845
846


847
848
849
850
851
852
853
854
855
856
857
858
859
860
...
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
on systems that may not have malloc(), free(), or realloc() in their
standard library.
An application that is compiled with [SQLITE_ZERO_MALLOC] will need to
use [sqlite3_config()] together with [SQLITE_CONFIG_MALLOC] or
[SQLITE_CONFIG_HEAP] to specify a new alternative memory allocator
before beginning to use SQLite.</p>













































<tcl>hd_fragment pagecache {pagecache memory allocator}</tcl>
<h2> 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 [version 3.6.1] ([dateof: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 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 [database connection] 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
................................................................................
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 [version 3.6.1] ([dateof:3.6.1]), 
the soft heap limit only applies to the
general-purpose memory allocator.  The soft heap limit does not know
about or interact with
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>
<h1> 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
................................................................................
<h2> 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 ([memsys5]).</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>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>

<p>Safety-critical applications will usually want to modify the
................................................................................
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>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 two allocations can be controlled and/or eliminated by
configuring the [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
................................................................................

<h2> 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 [Robson proof], SQLite will usually continue 
to operate normally.
The the [pagecache memory allocator]
and the [lookaside memory allocator] 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
despicable sequence of allocations and deallocations - a sequence that