diff options
| -rw-r--r-- | manifest | 18 | ||||
| -rw-r--r-- | manifest.uuid | 2 | ||||
| -rw-r--r-- | src/mem5.c | 88 |
3 files changed, 81 insertions, 27 deletions
@@ -1,8 +1,8 @@ -----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1 -C Always\scall\ssqlite3_malloc()\sin\ssqlite3OsInit(),\seven\swhen\snot\scompiled\nwith\sSQLITE_TEST. -D 2009-08-17T16:01:11 +C Fix\sa\sbug\sin\smem5.c\swhich\swould\scause\san\sinfinite\sloop\son\san\sattempt\nto\sallocate\smore\sthan\s1073741824\sbytes\sof\scontiguous\smemory.\s\sAlso,\ssome\ncleanup\sof\smem5.c.\s\sMore\swork\sto\sdo\son\sthis. +D 2009-08-18T01:54:19 F Makefile.arm-wince-mingw32ce-gcc fcd5e9cd67fe88836360bb4f9ef4cb7f8e2fb5a0 F Makefile.in 0f7761c5d1c62ae7a841e3393ffaff1fa0f5c00a F Makefile.linux-gcc d53183f4aa6a9192d249731c90dbdffbd2c68654 @@ -135,7 +135,7 @@ F src/mem0.c f2f84062d1f35814d6535c9f9e33de3bfb3b132c F src/mem1.c e6d5c23941288df8191b8a98c28e3f57771e2270 F src/mem2.c d02bd6a5b34f2d59012a852615621939d9c09548 F src/mem3.c 67153ec933e08b70714055e872efb58a6b287939 -F src/mem5.c 838309b521c96a2a34507f74a5a739d28de4aac6 +F src/mem5.c 51f22f4783c974e4470ed25df4eefb4cfe00be86 F src/memjournal.c e68cb5f7e828b84d5bf2ea16c5d87f1ed7e9fe7f F src/mutex.c 73899d158560117c02909b6e9ffe2bad2560a817 F src/mutex.h 9e686e83a88838dac8b9c51271c651e833060f1e @@ -749,14 +749,14 @@ F tool/speedtest2.tcl ee2149167303ba8e95af97873c575c3e0fab58ff F tool/speedtest8.c 2902c46588c40b55661e471d7a86e4dd71a18224 F tool/speedtest8inst1.c 293327bc76823f473684d589a8160bde1f52c14e F tool/vdbe-compress.tcl 672f81d693a03f80f5ae60bfefacd8a349e76746 -P 67ad21abf88abb7a3e2eacddcaf1ab5d54149807 -R ec549832cb633402033ac649502759b2 +P b98a8706a61ad27c881b6820eee10d06bfb27417 +R 55b70508511043089513b3f1c6289087 U drh -Z be48c323c8b8282b760b014b1ad810ca +Z 305dee8c9b3dcd54033772b896ca7e5f -----BEGIN PGP SIGNATURE----- Version: GnuPG v1.4.6 (GNU/Linux) -iD8DBQFKiX7KoxKgR168RlERAm/TAJ9kojYfPGoCSQZ1ggED1UZNojnliQCeMPZF -46q/U09ODtw1dhYAA6r5GcY= -=35NL +iD8DBQFKignOoxKgR168RlERAlG5AJ9phi2yeZEaFeweSkbDMgEHcJrKoACdGfdb +YW3YUgjZLG6Xr9VGmvvZdPA= +=CF4j -----END PGP SIGNATURE----- diff --git a/manifest.uuid b/manifest.uuid index 9b8888fbc..36c79a905 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -b98a8706a61ad27c881b6820eee10d06bfb27417
\ No newline at end of file +783b751a38f9f911c5ebdf738c255b7111978f76
\ No newline at end of file diff --git a/src/mem5.c b/src/mem5.c index f9389e9e9..02f665e9c 100644 --- a/src/mem5.c +++ b/src/mem5.c @@ -13,7 +13,7 @@ ** allocation subsystem for use by SQLite. ** ** This version of the memory allocation subsystem omits all -** use of malloc(). The SQLite user supplies a block of memory +** use of malloc(). The application gives SQLite a block of memory ** before calling sqlite3_initialize() from which allocations ** are made and returned by the xMalloc() and xRealloc() ** implementations. Once sqlite3_initialize() has been called, @@ -23,7 +23,30 @@ ** This version of the memory allocation subsystem is included ** in the build only if SQLITE_ENABLE_MEMSYS5 is defined. ** -** $Id: mem5.c,v 1.19 2008/11/19 16:52:44 danielk1977 Exp $ +** This memory allocator uses the following algorithm: +** +** 1. All memory allocations sizes are rounded up to a power of 2. +** +** 2. To adjacent and aligned free blocks are coalesced into a single +** block of the next larger size. +** +** 3. New memory is allocated from the first available free block. +** +** This algorithm is described in: 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 n be the size of the largest allocation divided by the minimum +** allocation size (after rounding all sizes up to a power of 2.) Let M +** be the maximum amount of memory ever outstanding at one time. Let +** N be the total amount of memory available for allocation. Robson +** proved that this memory allocator will never breakdown due to +** fragmentation as long as the following constraint holds: +** +** N >= M*(1 + log2(n)/2) - n + 1 +** +** The sqlite3_status() logic tracks the maximum values of n and M so +** that an application can, at any time, verify this constraint. */ #include "sqliteInt.h" @@ -37,6 +60,9 @@ ** A minimum allocation is an instance of the following structure. ** Larger allocations are an array of these structures where the ** size of the array is a power of 2. +** +** The size of this object must be a power of two. That fact is +** verified in memsys5Init(). */ typedef struct Mem5Link Mem5Link; struct Mem5Link { @@ -46,8 +72,8 @@ struct Mem5Link { /* ** Maximum size of any allocation is ((1<<LOGMAX)*mem5.nAtom). Since -** mem5.nAtom is always at least 8, this is not really a practical -** limitation. +** mem5.nAtom is always at least 8 and 32-bit integers are used, +** it is not actually possible to reach this limit. */ #define LOGMAX 30 @@ -69,7 +95,7 @@ static SQLITE_WSD struct Mem5Global { */ int nAtom; /* Smallest possible allocation in bytes */ int nBlock; /* Number of nAtom sized blocks in zPool */ - u8 *zPool; + u8 *zPool; /* Memory available to be allocated */ /* ** Mutex to control access to the memory allocation subsystem. @@ -99,10 +125,17 @@ static SQLITE_WSD struct Mem5Global { */ u8 *aCtrl; -} mem5 = { 19804167 }; +} mem5 = { 0 }; +/* +** Access the static variable through a macro for SQLITE_OMIT_WSD +*/ #define mem5 GLOBAL(struct Mem5Global, mem5) +/* +** Assuming mem5.zPool is divided up into an array of Mem5Link +** structures, return a pointer to the idx-th such lik. +*/ #define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.nAtom])) /* @@ -198,7 +231,13 @@ static int memsys5UnlinkFirst(int iLogsize){ /* ** Return a block of memory of at least nBytes in size. -** Return NULL if unable. +** Return NULL if unable. Return NULL if nBytes==0. +** +** The caller guarantees that nByte positive. +** +** The caller has obtained a mutex prior to invoking this +** routine so there is never any chance that two or more +** threads can be in this routine at the same time. */ static void *memsys5MallocUnsafe(int nByte){ int i; /* Index of a mem5.aPool[] slot */ @@ -206,12 +245,20 @@ static void *memsys5MallocUnsafe(int nByte){ int iFullSz; /* Size of allocation rounded up to power of 2 */ int iLogsize; /* Log2 of iFullSz/POW2_MIN */ + /* nByte must be a positive */ + assert( nByte>0 ); + /* Keep track of the maximum allocation request. Even unfulfilled ** requests are counted */ if( (u32)nByte>mem5.maxRequest ){ mem5.maxRequest = nByte; } + /* Abort if the size is too great */ + if( nByte > 0x40000000 ){ + return 0; + } + /* Round nByte up to the next valid power of two */ for(iFullSz=mem5.nAtom, iLogsize=0; iFullSz<nByte; iFullSz *= 2, iLogsize++){} @@ -250,7 +297,7 @@ static void *memsys5MallocUnsafe(int nByte){ */ static void memsys5FreeUnsafe(void *pOld){ u32 size, iLogsize; - int iBlock; + int iBlock; /* Set iBlock to the index of the block pointed to by pOld in ** the array of mem5.nAtom byte blocks pointed to by mem5.zPool. @@ -316,26 +363,27 @@ static void *memsys5Malloc(int nBytes){ /* ** Free memory. +** +** The outer layer memory allocator prevents this routine from +** being called with pPrior==0. */ static void memsys5Free(void *pPrior){ - if( pPrior==0 ){ -assert(0); - return; - } + assert( pPrior!=0 ); memsys5Enter(); memsys5FreeUnsafe(pPrior); memsys5Leave(); } /* -** Change the size of an existing memory allocation +** Change the size of an existing memory allocation. +** +** The outer layer memory allocator prevents this routine from +** being called with pPrior==0. */ static void *memsys5Realloc(void *pPrior, int nBytes){ int nOld; void *p; - if( pPrior==0 ){ - return memsys5Malloc(nBytes); - } + assert( pPrior!=0 ); if( nBytes<=0 ){ memsys5Free(pPrior); return 0; @@ -355,14 +403,20 @@ static void *memsys5Realloc(void *pPrior, int nBytes){ } /* -** Round up a request size to the next valid allocation size. +** Round up a request size to the next valid allocation size. If +** the allocation is too large to be handled by this allocation system, +** return 0. */ static int memsys5Roundup(int n){ int iFullSz; + if( n > 0x40000000 ) return 0; for(iFullSz=mem5.nAtom; iFullSz<n; iFullSz *= 2); return iFullSz; } +/* +** Return the logarithm base 2 of iValue. +*/ static int memsys5Log(int iValue){ int iLog; for(iLog=0; (1<<iLog)<iValue; iLog++); |