hd_keywords {memory allocation}

Overview

SQLite uses dynamic memory allocation to obtain memory for storing various objects (ex: [database connections] and [prepared statements]) and to build a memory cache of the database file and to hold the results of queries. Much effort has gone into making the dynamic memory allocation subsystem of SQLite reliable, predictable, robust, secure, and efficient.

This document provides an overview of dynamic memory allocation within SQLite. The target audience is software engineers who are tuning their use of SQLite for peak performance in demanding environments. Nothing in this document is required knowledge for using SQLite. The default settings and configuration for SQLite will work well in most applications. However, the information contained in this document may be useful to engineers who are tuning SQLite to comply with special requirements or to run under unusual circumstances.

Features

The SQLite core and its memory allocation subsystem provides the following capabilities:

Testing

Most of the code in the SQLite source tree is devoted purely to [testing | testing and verification]. Reliability is important to SQLite. Among the tasks of the test infrastructure is to ensure that SQLite does not misuse dynamically allocated memory, that SQLite does not leak memory, and that SQLite responds correctly to a dynamic memory allocation failure.

The test infrastructure verifies that SQLite does not misuse dynamically allocated memory by using a specially instrumented memory allocator. The instrumented memory allocator is enabled at compile-time using the [SQLITE_MEMDEBUG] option. The instrumented memory allocator is much slower than the default memory allocator and so its use is not recommended in production. But when enabled during testing, the instrumented memory allocator performs the following checks:

Regardless of whether or not the instrumented memory allocator is used, SQLite keeps track of how much memory is currently checked out. There are hundreds of test scripts used for testing SQLite. At the end of each script, all objects are destroyed and a test is made to ensure that all memory has been freed. This is how memory leaks are detected. Notice that memory leak detection is in force at all times, during test builds and during production builds. Whenever one of the developers runs any individual test script, memory leak detection is active. Hence memory leaks that do arise during development are quickly detected and fixed.

The response of SQLite to out-of-memory (OOM) errors is tested using a specialized memory allocator overlay that can simulate memory failures. The overlay is a layer that is inserted in between the memory allocator and the rest of SQLite. The overlay passes most memory allocation requests straight through to the underlying allocator and passes the results back up to the requester. But the overlay can be set to cause the Nth memory allocation to fail. To run an OOM test, the overlay is first set to fail on the first allocation attempt. Then some test script is run and verification that the allocation was correctly caught and handled is made. Then the overlay is set to fail on the second allocation and the test repeats. The failure point continues to advance one allocation at a time until the entire test procedure runs to completion without hitting a memory allocation error. This whole test sequence run twice. On the first pass, the overlay is set to fail only the Nth allocation. On the second pass, the overlay is set to fail the Nth and all subsequent allocations.

Note that the memory leak detection logic continues to work even when the OOM overlay is being used. This verifies that SQLite does not leak memory even when it encounters memory allocation errors. Note also that the OOM overlay can work with any underlying memory allocator, including the instrumented memory allocator that checks for memory allocation misuse. In this way it is verified that OOM errors do not induce other kinds of memory usage errors.

Finally, we observe that the instrumented memory allocator and the memory leak detector both work over the entire SQLite test suite and the [TCL test suite] provides over 99% statement test coverage and that the [TH3] test harness provides [test coverage | 100% branch test coverage] with no leak leaks. This is strong evidence that dynamic memory allocation is used correctly everywhere within SQLite.

Use of reallocarray()

The reallocarray() interface is a recent innovation (circa 2014) from the OpenBSD community that grow out of efforts to prevent the next [http://heartbleed.com | "heartbleed" bug] by avoiding 32-bit integer arithmetic overflow on memory allocation size computations. The reallocarray() function has both unit-size and count parameters. To allocate memory sufficient to hold an array of N elements each X-bytes in size, one calls "reallocarray(0,X,N)". This is preferred over the traditional technique of invoking "malloc(X*N)" as reallocarray() eliminates the risk that the X*N multiplication will overflow and cause malloc() to return a buffer that is a different size from what the application expected.

SQLite does not use reallocarray(). The reason is that reallocarray() is not useful to SQLite. It turns out that SQLite never does memory allocations that are the simple product of two integers. Instead, SQLite does allocations of the form "X+C" or "N*X+C" or "M*N*X+C" or "N*X+M*Y+C", and so forth. The reallocarray() interface is not helpful in avoiding integer overflow in those cases.

Nevertheless, integer overflow in the computation of memory allocation sizes is a concern that SQLite would like to deal with. To prevent problems, all SQLite internal memory allocations occur using thin wrapper functions that take a signed 64-bit integer size parameter. The SQLite source code is audited to ensure that all size computations are carried out using 64-bit signed integers as well. SQLite will refuse to allocate more than about 2GB of memory at one go. (In common use, SQLite seldom ever allocates more than about 8KB of memory at a time so a 2GB allocation limit is not a burden.) So the 64-bit size parameter provides lots of headroom for detecting overflows. The same audit that verifies that all size computations are done as 64-bit signed integers also verifies that it is impossible to overflow a 64-bit integer during the computation.

The code audits used to ensure that memory allocation size computations do not overflow in SQLite are repeated prior to every SQLite release.

Configuration

The default memory allocation settings in SQLite are appropriate for most applications. However, applications with unusual or particularly strict requirements may want to adjust the configuration to more closely align SQLite to their needs. Both compile-time and start-time configuration options are available.

hd_fragment altalloc {built-in memory allocators}

Alternative low-level memory allocators

The SQLite source code includes several different memory allocation modules that can be selected at compile-time, or to a limited extent at start-time.

hd_fragment defaultalloc {default memory allocator}

The default memory allocator

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

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.

hd_fragment memdebug {debugging memory allocator} *memsys2

The debugging memory allocator

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 place sentinel values at both ends of the allocation returned to the SQLite core. When an allocation is freed, these sentinels are checked to make sure the SQLite core did not overrun the buffer in either direction. When the system library is GLIBC, the heavy wrapper also makes use of the GNU backtrace() function to examine the stack and record the ancestor functions of the malloc() call. When running the SQLite test suite, the heavy wrapper also records the name of the current test case. These latter two features are useful for tracking down the source of memory leaks detected by the test suite.

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 ensure that the SQLite core does not make assumptions about the state of newly allocated memory and that memory allocations are not used after they have been freed.

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.

hd_fragment win32heap {Win32 native memory allocator}

The Win32 native memory allocator

If SQLite is compiled for Windows with the [SQLITE_WIN32_MALLOC] compile-time option, then a different, thin wrapper is used around HeapAlloc(), HeapReAlloc(), and HeapFree(). The thin wrapper uses the configured SQLite heap, which will be different from the default process heap if the [SQLITE_WIN32_HEAP_CREATE] compile-time option is used. In addition, when an allocation is made or freed, HeapValidate() will be called if SQLite is compiled with assert() enabled and the [SQLITE_WIN32_MALLOC_VALIDATE] compile-time option.

hd_fragment memsys5 *memsys5 {zero-malloc memory allocator}

Zero-malloc memory allocator

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:

[sqlite3_config]([SQLITE_CONFIG_HEAP], pBuf, szBuf, mnReq);

In the call above, pBuf is a pointer to a large, contiguous chunk of memory space that SQLite will use to satisfy all of its memory allocation needs. pBuf might point to a static array or it might be memory obtained from some other application-specific mechanism. szBuf is an integer that is the number of bytes of memory space pointed to by pBuf. mnReq is another integer that is the minimum size of an allocation. Any call to [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 n and hence the minimum memory size requirement in the [Robson proof].

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.

The algorithm used by memsys5 can be called "power-of-two, first-fit". The sizes of all memory allocation requests are rounded up to a power of two and the request is satisfied by the first free slot in pBuf that is large enough. Adjacent freed allocations are coalesced using a buddy system. When used appropriately, this algorithm provides mathematical guarantees against fragmentation and breakdown, as described further below.

hd_fragment memsysx {experimental memory allocators}

Experimental memory allocators

The name "memsys5" used for the zero-malloc memory allocator implies that there are several additional memory allocators available, and indeed there are. The default memory allocator is "memsys1". The debugging memory allocator is "memsys2". Those have already been covered.

If SQLite is compiled with [SQLITE_ENABLE_MEMSYS3] then another zero-malloc memory allocator, similar to memsys5, is included in the source tree. The memsys3 allocator, like memsys5, must be activated by a call to [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.

Memsys4 and memsys6 were experimental memory allocators introduced in around 2007 and subsequently removed from the source tree in around 2008, after it became clear that they added no new value.

Other experimental memory allocators might be added in future releases of SQLite. One may anticipate that these will be called memsys7, memsys8, and so forth.

Application-defined memory allocators

New memory allocators do not have to be part of the SQLite source tree nor included in the sqlite3.c [amalgamation]. Individual applications can supply their own memory allocators to SQLite at start-time.

To cause SQLite to use a new memory allocator, the application simply calls:

[sqlite3_config]([SQLITE_CONFIG_MALLOC], pMem);

In the call above, pMem is a pointer to an [sqlite3_mem_methods] object that defines the interface to the application-specific memory allocator. The [sqlite3_mem_methods] object is really just a structure containing pointers to functions to implement the various memory allocation primitives.

In a multi-threaded application, access to the [sqlite3_mem_methods] is serialized if and only if [SQLITE_CONFIG_MEMSTATUS] is enabled. If [SQLITE_CONFIG_MEMSTATUS] is disabled then the methods in [sqlite3_mem_methods] must take care of their own serialization needs.

Memory allocator overlays

An application can insert layers or "overlays" in between the SQLite core and the underlying memory allocator. For example, the out-of-memory test logic for SQLite uses an overlay that can simulate memory allocation failures.

An overlay can be created by using the

[sqlite3_config]([SQLITE_CONFIG_GETMALLOC], pOldMem);

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

No-op memory allocator stub

If SQLite is compiled with the [SQLITE_ZERO_MALLOC] option, then the [default memory allocator] is omitted and replaced by a stub memory allocator that never allocates any memory. Any calls to the stub memory allocator will report back that no memory is available.

The no-op memory allocator is not useful by itself. It exists only as a placeholder so that SQLite has a memory allocator to link against on systems that may not have malloc(), free(), or realloc() in their standard library. An application that is compiled with [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.

hd_fragment pagecache {pagecache memory allocator}

Page cache memory

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.

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:

The page-cache memory allocator is disabled by default. An application can enable it at start-time as follows:

[sqlite3_config]([SQLITE_CONFIG_PAGECACHE], pBuf, sz, N);

The pBuf parameter is a pointer to a contiguous range of bytes that SQLite will use for page-cache memory allocations. The buffer must be at least sz*N bytes in size. The "sz" parameter is the size of each page-cache allocation. N is the maximum number of available allocations.

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.

hd_fragment lookaside {lookaside memory allocator} \ {lookaside buffer} {lookaside memory} {lookaside}

Lookaside memory allocator

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

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

Because lookaside allocations are always the same size, the allocation and deallocation algorithms are very quick. There is no need to coalesce adjacent free slots or search for a slot of a particular size. Each [database connection] maintains a singly-linked list of unused slots. Allocation requests simply pull the first element of this list. Deallocations simply push the element back onto the front of the list. Furthermore, each [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 and lookaside is configured.

The size of the lookaside memory pool has a global default value but can also be configured on a connection-by-connection basis. To change the default size of the lookaside memory pool at compile-time, use the [SQLITE_DEFAULT_LOOKASIDE|-DSQLITE_DEFAULT_LOOKASIDE=SZ,N] option. To change the default size of the lookaside memory pool at start-time, use the [sqlite3_config()] interface:

[sqlite3_config]([SQLITE_CONFIG_LOOKASIDE], sz, cnt);

The "sz" parameter is the size in bytes of each lookaside slot. The "cnt" parameter is the total number of lookaside memory slots per database connection. The total amount of lookaside memory allocated to each [database connection] is sz*cnt bytes.

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

[sqlite3_db_config](db, [SQLITE_DBCONFIG_LOOKASIDE], pBuf, sz, cnt);

The "pBuf" parameter is a pointer to memory space that will be used for the lookaside memory pool. If pBuf is NULL, then SQLite will obtain its own space for the memory pool using [sqlite3_malloc()]. The "sz" and "cnt" parameters are the size of each lookaside slot and the number of slots, respectively. If pBuf is not NULL, then it must point to at least sz*cnt bytes of memory.

The lookaside configuration can only be changed while there are no outstanding lookaside allocations for the database connection. Hence, the configuration should be set immediately after creating the database connection using [sqlite3_open()] (or equivalent) and before evaluating any SQL statements on the connection.

hd_fragment memstatus {memory statistics}

Memory status

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.

Most memory statistics are global, and therefore the tracking of statistics must be serialized with a mutex. Statistics are turned on by default, but an option exists to disable them. By disabling memory statistics, SQLite avoids entering and leaving a mutex on each memory allocation and deallocation. That savings can be noticeable on systems where mutex operations are expensive. To disable memory statistics, the following interface is used at start-time:

[sqlite3_config]([SQLITE_CONFIG_MEMSTATUS], onoff);

The "onoff" parameter is true to enable the tracking of memory statistics and false to disable statistics tracking.

Assuming statistics are enabled, the following routine can be used to access them:

[sqlite3_status]([SQLITE_STATUS_MEMORY_USED|verb], &current, &highwater, resetflag);

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.

A different interface is used to find statistics associated with a single [database connection]:

[sqlite3_db_status](db, [SQLITE_DBSTATUS_LOOKASIDE_USED|verb], &current, &highwater, resetflag);

This interface is similar except that it takes a pointer to a [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.

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.

Setting memory usage limits

The [sqlite3_soft_heap_limit64()] interface can be used to set an upper bound on the total amount of outstanding memory that the general-purpose memory allocator for SQLite will allow to be outstanding at one time. If attempts are made to allocate more memory than specified by the soft heap limit, then SQLite will first attempt to free cache memory before continuing with the allocation request. The soft heap limit mechanism only works if [memory statistics] are enabled and it works best if the SQLite library is compiled with the [SQLITE_ENABLE_MEMORY_MANAGEMENT] compile-time option.

The soft heap limit is "soft" in this sense: If SQLite is not able to free up enough auxiliary memory to stay below the limit, it goes ahead and allocates the extra memory and exceeds its limit. This occurs under the theory that it is better to use additional memory than to fail outright.

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.

hd_fragment nofrag {Robson proof}

Mathematical Guarantees Against Memory Allocation Failures

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:

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

Let us use the following notation (similar but not identical to Robson's notation):

N The amount of raw memory needed by the memory allocation system in order to guarantee that no memory allocation will ever fail.
M The maximum amount of memory that the application ever has checked out at any point in time.
n 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.

Robson proves the following result:

N = M*(1 + (log2 n)/2) - n + 1

Colloquially, the Robson proof shows that in order to guarantee breakdown-free operation, any memory allocator must use a memory pool of size N which exceeds the maximum amount of memory ever used M by a multiplier that depends on n, the ratio of the largest to the smallest allocation size. In other words, unless all memory allocations are of exactly the same size (n=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.

Robson's proof is constructive. He provides an algorithm for computing a sequence of allocation and deallocation operations that will lead to an allocation failure due to memory fragmentation if available memory is as much as one byte less than N. 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 N or more bytes.

The values M and n are properties of the application. If an application is constructed in such a way that both M and n are known, or at least have known upper bounds, and if the application uses the [memsys5] memory allocator and is provided with N 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 N that 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.

Computing and controlling parameters M and n

The Robson proof applies separately to each of the memory allocators used by SQLite:

For allocators other than [memsys5], all memory allocations are of the same size. Hence, n=1 and therefore N=M. In other words, the memory pool need be no larger than the largest amount of memory in use at any given moment.

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

Safety-critical applications will usually want to modify the default lookaside memory configuration so that when the initial lookaside memory buffer is allocated during [sqlite3_open()] the resulting memory allocation is not so large as to force the n parameter to be too large. In order to keep n under control, it is best to try to keep the largest memory allocation below 2 or 4 kilobytes. Hence, a reasonable default setup for the lookaside memory allocator might any one of the following:

sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 32, 32);  /* 1K */
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 64, 32);  /* 2K */
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 32, 64);  /* 2K */
sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 64, 64);  /* 4K */

Another approach is to initially disable the lookaside memory allocator:

sqlite3_config(SQLITE_CONFIG_LOOKASIDE, 0, 0);

Then let the application maintain a separate pool of larger lookaside memory buffers that it can distribute to [database connections] as they are created. In the common case, the application will only have a single [database connection] and so the lookaside memory pool can consist of a single large buffer.

sqlite3_db_config(db, SQLITE_DBCONFIG_LOOKASIDE, aStatic, 256, 500);

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.

The general purpose memory allocator is the most difficult memory pool to manage because it supports allocations of varying sizes. Since n is a multiplier on M we want to keep n as small as possible. This argues for keeping the minimum allocation size for [memsys5] as large as possible. In most applications, 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.

Further to keeping n small, one desires to keep the size of the largest memory allocations under control. Large requests to the general-purpose memory allocator might come from several sources:

  1. SQL table rows that contain large strings or BLOBs.
  2. Complex SQL queries that compile down to large [prepared statements].
  3. SQL parser objects used internally by [sqlite3_prepare_v2()].
  4. Storage space for [database connection] objects.
  5. Page cache memory allocations that overflow into the general-purpose memory allocator.
  6. Lookaside buffer allocations for new [database connections].

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 size below 2KB.

If the application is designed to manage data in small pieces, then the database should never contain any large strings or BLOBs and hence element 1 above should not be a factor. If the database does contain large strings or BLOBs, they should be read using [sqlite3_blob | incremental BLOB I/O] and rows that contain the large strings or BLOBs should never be update by any means other than [sqlite3_blob | incremental BLOB I/O]. Otherwise, the [sqlite3_step()] routine will need to read the entire row into contiguous memory at some point, and that will involve at least one large memory allocation.

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

All things considered, applications should normally be able to hold their maximum memory allocation size below 2K or 4K. This gives a value for log2(n) of 2 or 3. This will limit N to between 2 and 2.5 times M.

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 experimentally using [SQLITE_STATUS_MEMORY_USED]. A typical application might only use about 40KB of general-purpose memory. This gives a value of N of around 100KB.

Ductile failure

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 M and/or n 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 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.

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 provide the application with all the mechanism necessary to complete the monitoring portion of this task.

Stability Of Memory Interfaces

Update: As of SQLite version 3.7.0 ([dateof:3.7.0]), all of SQLite memory allocation interfaces are considered stable and will be supported in future releases.