Documentation Source Text

Check-in [080d9901f8]
Login

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

Overview
Comment:Continuing work on the memory allocator documentation.
Timelines: family | ancestors | descendants | both | trunk
Files: files | file ages | folders
SHA1: 080d9901f8287fb1eab471dd2bdd1204771113a2
User & Date: drh 2008-08-04 18:08:57
Context
2008-08-04
22:01
Updates to the malloc.html document. check-in: 2722f22a04 user: drh tags: trunk
18:08
Continuing work on the memory allocator documentation. check-in: 080d9901f8 user: drh tags: trunk
13:45
Enhanced markings for experimental and deprecated interfaces. check-in: afc454f404 user: drh tags: trunk
Changes
Hide Diffs Unified Diffs Ignore Whitespace Patch

Changes to pages/capi3ref.in.

529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
  eval hd_keywords $keywords

  hd_puts "<h2>$title</h2>"
  hd_puts "<blockquote><pre>"
  hd_puts "$code"
  hd_puts "</pre></blockquote>"
  if {$supported($kw)==1} {
    hd_resolve {<p><b>Important:</b> This interface is [experimental]}
    hd_resolve {and is subject to change without notice.</p>}
  }
  regsub -all "\n\n+" $body "</p>\n\n<p>" body
  hd_resolve <p>$body</p>
  hd_enable_main 0
  hd_puts {<p>See also lists of
  <a href="objlist.html">Objects</a>,







|







529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
  eval hd_keywords $keywords

  hd_puts "<h2>$title</h2>"
  hd_puts "<blockquote><pre>"
  hd_puts "$code"
  hd_puts "</pre></blockquote>"
  if {$supported($kw)==1} {
    hd_resolve {<p><b>Important:</b> This interface is [experimental] }
    hd_resolve {and is subject to change without notice.</p>}
  }
  regsub -all "\n\n+" $body "</p>\n\n<p>" body
  hd_resolve <p>$body</p>
  hd_enable_main 0
  hd_puts {<p>See also lists of
  <a href="objlist.html">Objects</a>,

Changes to pages/changes.in.

38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
    }
    hd_close_aux
    hd_enable_main 1
  }
}

chng {2008 Aug 6 (3.6.1)} {
<li>Added the "lookaside memory allocator" for a speed improvement in excess
    of 15% on some workloads.  (Your mileage may vary.)</li>
<li>Added the [SQLITE_CONFIG_LOOKASIDE] verb to [sqlite3_config()] to control
    the default lookaside configuration.</li>
<li>Added the [sqlite3_db_config()] and [sqlite3_db_status()] interfaces for
    controlling and monitoring the lookaside allocator separately on each
    [database connection].</li>
<li>Numerious other performance enhancements</li>







|







38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
    }
    hd_close_aux
    hd_enable_main 1
  }
}

chng {2008 Aug 6 (3.6.1)} {
<li>Added the [lookaside memory allocator] for a speed improvement in excess
    of 15% on some workloads.  (Your mileage may vary.)</li>
<li>Added the [SQLITE_CONFIG_LOOKASIDE] verb to [sqlite3_config()] to control
    the default lookaside configuration.</li>
<li>Added the [sqlite3_db_config()] and [sqlite3_db_status()] interfaces for
    controlling and monitoring the lookaside allocator separately on each
    [database connection].</li>
<li>Numerious other performance enhancements</li>

Changes to pages/malloc.in.

13
14
15
16
17
18
19


20
21
22
23
24
25
26
...
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
...
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
...
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
...
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


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>
<h2>1.0 Features</h2>

<p>The SQLite core and its memory allocation subsystem provides the 
following capabilities:</p>

<ul>
................................................................................
from the standard C library for its memory allocation needs.  These routines
are surrounded by a thin wrapper that also provides a "memsize()" function
that will return the size of an existing allocation.  The memsize() function
is needed to keep an accurate count of the number of bytes of outstanding
memory; memsize() determines how many bytes to remove from the outstanding
count when an allocation is freed.  The default implementation implements
memsize() by always allocating 8 extra bytes on each malloc() request and
storing the size of the allocating 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>
<h4>3.1.2 The debugging memory allocator</h4>

<p>If SQLite is compiled with the [SQLITE_MEMDEBUG] compile-time option,
then 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 places sentinal values 
at both ends of the allocation returned to the SQLite core.  Upon freeing

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 record the name of
the current test case.  These latter two features are used to the SQLite
developers to track down memory leaks detected by the test suite.</p>

<p>The heavy wrapper that is used when [SQLITE_MEMDEBUG] 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 insure 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 [SQLITE_MEMDEBUG] 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="memsys5"></a>
<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 the following SQLite interface at
start-time:</p>

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

<p>In the call above, pBuf is a pointer to a large, contiguous chunk
of memory space that SQLite will use to satisfy all of its memory
allocation needs.   pBuf might point to a static array or it might
be memory obtained from some other operating-specific mechanism.
szBuf is an integer which is the number of bytes
of space the pBuf points to.  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 succinctly described as "power-of-two,
first-fit".  By this it is meant that 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.  When used appropriately,

this algorithm provides mathematical guarantees against fragmentation and
breakdown, as described further <a href="#nofrag">below</a>.</p>

<a name="memsysx"></a>
<h4>3.1.4 Experimental memory allocators</h4>

<p>The name "memsys5" used for the zero-malloc memory allocator implies
................................................................................
<p>If SQLite is compiled with [SQLITE_ENABLE_MEMSYS3] than 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 [sqlite3_config]([SQLITE_CONFIG_HEAP],...).  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 an mathematical
guarantees against memory fragmentation and breakdown.  Memsys3 was

a predecessor to memsys5.  We 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 experiemental and may be removed from the source tree in

a future release of SQLite.</p>

<p>Code for memsys4 is still in the SQLite source tree (as of this writing - 
SQLite release 3.6.1), but it has not been maintained for several release
cycles and probably does not work. Memsys4 was an attempt to use mmap()
to obtain memory for use and then use madvise() to release unused pages
back to the operating system so that they could be reused by other
processes.  The target platform for memsys4 was Google Android.  The
work on memsys4 has been abandoned and the memsys4 module will likely be
removed from the source tree in the near future.</p>

<p>Memsys6 uses system malloc() and free() to obtain the memory it needs.
Memsys6 serves as an aggregator.  Memsys6 only calls malloc() to obtain
large allocations.  It then services multiple smaller memory allocation
requests from the SQLite core using each single large allocation obtained
from system malloc().  Memsys6 is intended for use in systems where
system malloc() is particularly inefficient.  The idea behind memsys6 is
to reduce the number of calls to system malloc() by a factor of 10 or more.</p>

<p>Memsys6 is made available by compiling SQLite with the SQLITE_ENABLE_MEMSYS6
compile-time option and then at start-time invoking:</p>

<blockquote><pre>
................................................................................
<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_GETMALLOC], 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
insert in place of the existing memory allocator using
the [sqlite3_config]([SQLITE_CONFIG_MALLOC],...) as described
<a href="#appalloc">above</a>.

<a name="scratch"></a>
<h3>3.2 Scratch memory</h3>

<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 btree.  These scratch memory
allocations are typically about 10 kilobytes in size and by definition

last only for the duration of a single function call.</p>

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

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

<a name="pagecache"></a>
<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 usually consumes about 10 times more memory
than all other parts of SQLite combined.  ....</p>

<a name="lookaside"></a>




































<h3>3.4 Lookaside memory allocator</h3>

<p>












<a name="memstatus"></a>


































































<h3>3.5 Memory status</h3>


























































<a name="heaplimit"></a>
<h3>3.6 Setting memory usage limits</h3>









































































































<a name="nofrag"></a>
<h2>4.0 Anti-fragmentation Guarantee</h2>

















<a name="summary"></a>
<h2>5.0 Summary Of Memory Allocator Interfaces</h2>









>
>







 







|









|



|
>





|
|







 







|







|
|








|
|
|









|
|

|
>







 







|

>
|


<
>
|











|
|
|
|







 







|



|





|
>
|


|
|



|







 







|




|
|

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


<
>
>
>
>
>
>
>
>
>
>
>

<
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>


>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>
>



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

>
>
>
>
>
>
>
>
>
>
>
>
>
>
>

|
>
>
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
...
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
...
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
...
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
...
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
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>

<p><i>This report is a work in progress...</i></p>

<a name="features"></a>
<h2>1.0 Features</h2>

<p>The SQLite core and its memory allocation subsystem provides the 
following capabilities:</p>

<ul>
................................................................................
from the standard C library for its memory allocation needs.  These routines
are surrounded by a thin wrapper that also provides a "memsize()" function
that will return the size of an existing allocation.  The memsize() function
is needed to keep an accurate count of the number of bytes of outstanding
memory; memsize() determines how many bytes to remove from the outstanding
count when an allocation is freed.  The default implementation implements
memsize() by always allocating 8 extra bytes on each malloc() request and
storing the size of the allocation in that 8-byte header.</p>

<p>The default memory allocator is recommended for most applications.
If you do not have a compelling need to use an alternative memory
allocator, then use the default.</p>

<a name="memdebug"></a>
<h4>3.1.2 The debugging memory allocator</h4>

<p>If SQLite is compiled with the [SQLITE_MEMDEBUG] 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 places sentinal 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 record 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 [SQLITE_MEMDEBUG] 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 insure 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 [SQLITE_MEMDEBUG] 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>

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

<p>In the call above, pBuf is a pointer to a large, contiguous chunk
of memory space that SQLite will use to satisfy all of its memory
allocation needs.   pBuf might point to a static array or it might
be memory obtained from some other application-specific mechanism.
szBuf is an integer which is the number of bytes of memry space
pointed to by pBuf.  mnReq is another integer which is the
minimum size of an allocation.  Any call to [sqlite3_malloc(N)] where
N is less than mnReq will be rounded up to mnReq.  mnReq must be
a power of two.</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
allocations are coalesced using a buddy system. When used appropriately,
this algorithm provides mathematical guarantees against fragmentation and
breakdown, as described further <a href="#nofrag">below</a>.</p>

<a name="memsysx"></a>
<h4>3.1.4 Experimental memory allocators</h4>

<p>The name "memsys5" used for the zero-malloc memory allocator implies
................................................................................
<p>If SQLite is compiled with [SQLITE_ENABLE_MEMSYS3] than 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 [sqlite3_config]([SQLITE_CONFIG_HEAP],...).  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>Code for memsys4 is still in the SQLite source tree (as of this writing - 
SQLite release 3.6.1), but it has not been maintained for several release
cycles and probably does not work. Memsys4 was an attempt to use mmap()
to obtain memory for use and then use madvise() to release unused pages
back to the operating system so that they could be reused by other
processes.  The target platform for memsys4 was Google Android.  The
work on memsys4 has been abandoned and the memsys4 module will likely be
removed from the source tree in the near future.</p>

<p>Memsys6 uses system malloc() and free() to obtain the memory it needs.
Memsys6 serves as an aggregator.  Memsys6 only calls system malloc() to obtain
large allocations.  It then subdivides those large allocations to services 
multiple smaller memory allocation requests coming from the SQLite core.
Memsys6 is intended for use in systems where
system malloc() is particularly inefficient.  The idea behind memsys6 is
to reduce the number of calls to system malloc() by a factor of 10 or more.</p>

<p>Memsys6 is made available by compiling SQLite with the SQLITE_ENABLE_MEMSYS6
compile-time option and then at start-time invoking:</p>

<blockquote><pre>
................................................................................
<blockquote><pre>
[sqlite3_config]([SQLITE_CONFIG_GETMALLOC], 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 [sqlite3_config]([SQLITE_CONFIG_MALLOC],...) as described
<a href="#appalloc">above</a>.

<tcl>hd_fragment scratch {scratch memory allocator}</tcl>
<h3>3.2 Scratch memory</h3>

<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 btree.  These scratch memory
allocations are typically about 10 kilobytes in size and are
transient - lasting
only for the duration of a single, short-lived function call.</p>

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

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

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

<blockquote><pre>
................................................................................
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>
<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] frequently need to make numerous
small and relatively 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 that malloc() and
free() end up using a significant fraction of the CPU time allocated
to SQLite.</p>


<p>SQLite [version 3.6.1] introduced the lookaside optimization to
help reduce the memory allocation load.  In the lookaside optimization,
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 pieces of around 50 to 200 byte each.  This
becomes the lookaside memory pool.  Thereafter, memory allocations
associated with a the [database connection] that are small enough are
allocated one of the pieces of the lookaside pool rather than 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 entries are already checked out.  
But in many cases, the memory
allocations are small enough and there are few enough outstanding that
the memory allocation 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 allocations nor search for an allocation
of a particular size.  Each [database connection] maintains a singly-linked
list of unused allocations.  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.
To change the default size of the lookaside memory pool use the 
following interface at start-time:</p>

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

<p>The "sz" parameter is the size in bytes of each piece of the
allocation.  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: default values are for SQLite [version 3.6.1] and are subject
to changes in future releases.)
</p>

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

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

<p>The lookaside memory pool size can only be changed when there are
no lookaside allocations outstanding for the database connection.
Hence, the size should be set immediately after creating the database
connection using [sqlite3_open()] (or related function) and before
evaluating any SQL statements on the connection.</p>

<tcl>hd_fragment memstatus {memory statistics}</tcl>
<h3>3.5 Memory status</h3>

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

<p>The "onoff" parameter is true to enable the tracking of memory
statistics an false to disable statistics tracking.</p>

<p>Assuming statistics are enabled, the following routine can be used
to access them:</p>

<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>
[sqlite3_db_status](db, [SQLITE_DBSTATUS_LOOKASIDE_USED|verb], &current, &highwater, resetflag);
</pre></blockquote>

<p>These interface is similar except that it takes a pointer to
an [database connection] as its first argument and returns statistics about
that one object rather than about the entire SQLite library.
The [sqlite3_db_status()] interface currently only recognizes a
single verb [SQLITE_DBSTATUS_LOOKASIDE_USED], 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
[SQLITE_CONFIG_MEMSTATUS] is turned off.</p>

<a name="heaplimit"></a>
<h3>3.6 Setting memory usage limits</h3>

<p>The [sqlite3_soft_heap_limit()] 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 that 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 [memory statistics] are enabled and
if the SQLite library is compiled with the [SQLITE_ENABLE_MEMORY_MANAGEMENT]
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 allocations 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, 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>
<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
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>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>

<p>
<i>To be done:  Discuss how to minimize <b>M</b> and <b>n</b> and
consequently <b>N</b>.</i>
</p>

<p>
<i>To be done:  Discuss how to measure <b>M</b> and <b>n</b> using
[memory statistics].</i>
</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
subject to change from one release to the next.  These interfaces are
in the process of being refined to work on a wide variety of systems
under a range of constraints.  The SQLite developers need the flexibility
to change the memory allocator interfaces in order to best meet the
needs of a wide variety of systems.</p>

<p>One may anticipate that the memory allocator interfaces will
eventually stablize.  Appropriate notice will be given when that
occurs.  In the meantime, applications developers who make use of
these interfaces need to be prepared to modify their applications
to accommodate changes in the SQLite interface.</p>

<a name="summary"></a>
<h2>6.0 Summary Of Memory Allocator Interfaces</h2>

<p><i>To be completed...</i></p>