From 0d18020b807c861e876e3ad9cc54a05874aacd2e Mon Sep 17 00:00:00 2001 From: drh Date: Thu, 14 Feb 2008 23:26:56 +0000 Subject: [PATCH] Add the experimental mem5.c memory allocator. Allocate the content part of cache pages separately from the header. (See check-ins (4495) and (4409)). (CVS 4789) FossilOrigin-Name: 669ece8c82bfa69add852589dd1211751cb26fb2 --- main.mk | 5 +- manifest | 25 +- manifest.uuid | 2 +- src/mem1.c | 23 +- src/mem2.c | 34 +-- src/mem3.c | 10 +- src/mem4.c | 13 +- src/mem5.c | 662 ++++++++++++++++++++++++++++++++++++++++++++++++ src/pager.c | 17 +- src/sqliteInt.h | 28 +- 10 files changed, 737 insertions(+), 82 deletions(-) create mode 100644 src/mem5.c diff --git a/main.mk b/main.mk index 5b1fe53728..924a69fee3 100644 --- a/main.mk +++ b/main.mk @@ -51,8 +51,8 @@ TCCX = $(TCC) $(OPTS) -I. -I$(TOP)/src LIBOBJ+= alter.o analyze.o attach.o auth.o btmutex.o btree.o build.o \ callback.o complete.o date.o delete.o \ expr.o fault.o func.o hash.o insert.o journal.o loadext.o \ - main.o malloc.o mem1.o mem2.o mem3.o mem4.o mutex.o mutex_os2.o \ - mutex_unix.o mutex_w32.o \ + main.o malloc.o mem1.o mem2.o mem3.o mem4.o mem5.o \ + mutex.o mutex_os2.o mutex_unix.o mutex_w32.o \ opcodes.o os.o os_os2.o os_unix.o os_win.o \ pager.o parse.o pragma.o prepare.o printf.o random.o \ select.o table.o $(TCLOBJ) tokenize.o trigger.o \ @@ -109,6 +109,7 @@ SRC = \ $(TOP)/src/mem2.c \ $(TOP)/src/mem3.c \ $(TOP)/src/mem4.c \ + $(TOP)/src/mem5.c \ $(TOP)/src/mutex.c \ $(TOP)/src/mutex.h \ $(TOP)/src/mutex_os2.c \ diff --git a/manifest b/manifest index 95301d781e..453691fcaf 100644 --- a/manifest +++ b/manifest @@ -1,5 +1,5 @@ -C Fix\sa\stypo\sin\sa\scomment\sused\sto\sgenerate\sdocumentation.\s(CVS\s4788) -D 2008-02-14T23:24:16 +C Add\sthe\sexperimental\smem5.c\smemory\sallocator.\s\sAllocate\sthe\scontent\spart\nof\scache\spages\sseparately\sfrom\sthe\sheader.\s\s(See\scheck-ins\s(4495)\sand\s(4409)).\s(CVS\s4789) +D 2008-02-14T23:26:56 F Makefile.arm-wince-mingw32ce-gcc ac5f7b2cef0cd850d6f755ba6ee4ab961b1fadf7 F Makefile.in bc2b5df3e3d0d4b801b824b7ef6dec43812b049b F Makefile.linux-gcc d53183f4aa6a9192d249731c90dbdffbd2c68654 @@ -64,7 +64,7 @@ F ext/icu/README.txt 3b130aa66e7a681136f6add198b076a2f90d1e33 F ext/icu/icu.c 12e763d288d23b5a49de37caa30737b971a2f1e2 F install-sh 9d4de14ab9fb0facae2f48780b874848cbf2f895 F ltmain.sh 56abb507100ed2d4261f6dd1653dec3cf4066387 -F main.mk ad3a30d15d88f7d7c58b3c5f6bcee6f917043887 +F main.mk e5649378177ca11d8a115a09e4284d14ffdc64d6 F mkdll.sh 712e74f3efe08a6ba12b2945d018a29a89d7fe3b F mkextu.sh 416f9b7089d80e5590a29692c9d9280a10dbad9f F mkextw.sh 1a866b53637dab137191341cc875575a5ca110fb @@ -105,10 +105,11 @@ F src/loadext.c d17a0f760d6866aacf5262f97d8efaaad379cdd7 F src/main.c b4014b71979a58d6aa79549fdf87175ab7bdf1cc F src/malloc.c 60e392a4c12c839517f9b0db7b995f825444fb35 F src/md5.c c5fdfa5c2593eaee2e32a5ce6c6927c986eaf217 -F src/mem1.c b15e107d51bdd4bcf410c18798ee48bee4768d4e -F src/mem2.c ed0cb11ae43a3cc92bfb07172c2801956e94eaba -F src/mem3.c 4ca65028bd5aabebc087cd29ab2ac1c10ce6a0d4 -F src/mem4.c 36ecd536a8b7acfe4cbf011353dae6ea68121e40 +F src/mem1.c 62a821702d3292809ca78e7c55c3ca04b05a3757 +F src/mem2.c 021eecbb210cfe90a8e7be9f04b01329d2c38851 +F src/mem3.c 979191678eb1aac0af7e5df9ab3897a07410ff4c +F src/mem4.c 45c328ec6dcb7e8d319cb383615b5fe547ca5409 +F src/mem5.c addb464d2328ad5dcd38a127a19a10fb654e1349 F src/mutex.c 3259f62c2429967aee6dc112117a6d2f499ef061 F src/mutex.h 079fa6fe9da18ceb89e79012c010594c6672addb F src/mutex_os2.c 19ab15764736f13b94b4f70e53f77547cbddd47a @@ -125,7 +126,7 @@ F src/os_unix.c e4daef7628f690fa2b188af3632fb18f96525946 F src/os_unix.h 5768d56d28240d3fe4537fac08cc85e4fb52279e F src/os_win.c c832d528ea774c7094d887749d71884984c9034c F src/os_win.h 41a946bea10f61c158ce8645e7646b29d44f122b -F src/pager.c 2ed81808091ce42ceb1cf209e4ce87922a0065c8 +F src/pager.c 1960545a871f9b57a80e485e5969ee045b7a00d8 F src/pager.h 8174615ffd14ccc2cad2b081b919a398fa95e3f9 F src/parse.y 00f2698c8ae84f315be5e3f10b63c94f531fdd6d F src/pragma.c e3f39f8576234887ecd0c1de43dc51af5855930c @@ -137,7 +138,7 @@ F src/server.c 087b92a39d883e3fa113cae259d64e4c7438bc96 F src/shell.c ca06cb687c40a8bff6307b5fad41a0e86a0f8558 F src/sqlite.h.in 74e71510ce5967333a36329212eca0833f6300bd F src/sqlite3ext.h a93f59cdee3638dc0c9c086f80df743a4e68c3cb -F src/sqliteInt.h 822045362bdddd303a0b17aa09679ba735ffbaa1 +F src/sqliteInt.h c82511830758350ed4cedd0815add7cbb145e08d F src/sqliteLimit.h ee4430f88f69bf63527967bb35ca52af7b0ccb1e F src/table.c 46ccf9b7892a86f57420ae7bac69ecd5e72d26b5 F src/tclsqlite.c 0d4483e37c6a1e87f80565e50d977df6dd2bf732 @@ -617,7 +618,7 @@ F www/tclsqlite.tcl 8be95ee6dba05eabcd27a9d91331c803f2ce2130 F www/vdbe.tcl 87a31ace769f20d3627a64fa1fade7fed47b90d0 F www/version3.tcl 890248cf7b70e60c383b0e84d77d5132b3ead42b F www/whentouse.tcl fc46eae081251c3c181bd79c5faef8195d7991a5 -P aca2bee8662c3adaa47b3e70b1ef35347111f9eb -R c4ed434e338bc60f75c5f2a5d865d5c6 +P 65e66dd81cd821364a2d95a9078d174fd9486288 +R 6ff5217afe1707040720fe27516205be U drh -Z 746cf76953f3d41bcc6c125a1c516040 +Z 6ab02326c39954da923fa8b7ecd38a1d diff --git a/manifest.uuid b/manifest.uuid index 62690a9392..12eda1d0f0 100644 --- a/manifest.uuid +++ b/manifest.uuid @@ -1 +1 @@ -65e66dd81cd821364a2d95a9078d174fd9486288 \ No newline at end of file +669ece8c82bfa69add852589dd1211751cb26fb2 \ No newline at end of file diff --git a/src/mem1.c b/src/mem1.c index 33c4902d96..2b28a8cdb8 100644 --- a/src/mem1.c +++ b/src/mem1.c @@ -12,31 +12,16 @@ ** This file contains the C functions that implement a memory ** allocation subsystem for use by SQLite. ** -** $Id: mem1.c,v 1.15 2008/02/13 18:25:27 danielk1977 Exp $ +** $Id: mem1.c,v 1.16 2008/02/14 23:26:56 drh Exp $ */ +#include "sqliteInt.h" /* ** This version of the memory allocator is the default. It is ** used when no other memory allocator is specified using compile-time ** macros. */ -#if !defined(SQLITE_MEMDEBUG) && !defined(SQLITE_MEMORY_SIZE) \ - && !defined(SQLITE_MMAP_HEAP_SIZE) - -/* -** We will eventually construct multiple memory allocation subsystems -** suitable for use in various contexts: -** -** * Normal multi-threaded builds -** * Normal single-threaded builds -** * Debugging builds -** -** This initial version is suitable for use in normal multi-threaded -** builds. We envision that alternative versions will be stored in -** separate source files. #ifdefs will be used to select the code from -** one of the various memN.c source files for use in any given build. -*/ -#include "sqliteInt.h" +#ifdef SQLITE_SYSTEM_MALLOC /* ** All of the static variables used by this module are collected @@ -239,4 +224,4 @@ void *sqlite3_realloc(void *pPrior, int nBytes){ return (void*)p; } -#endif /* !SQLITE_MEMDEBUG && !SQLITE_OMIT_MEMORY_ALLOCATION */ +#endif /* SQLITE_SYSTEM_MALLOC */ diff --git a/src/mem2.c b/src/mem2.c index 807b720117..45c0266149 100644 --- a/src/mem2.c +++ b/src/mem2.c @@ -12,38 +12,15 @@ ** This file contains the C functions that implement a memory ** allocation subsystem for use by SQLite. ** -** $Id: mem2.c,v 1.20 2008/02/13 18:25:27 danielk1977 Exp $ +** $Id: mem2.c,v 1.21 2008/02/14 23:26:56 drh Exp $ */ +#include "sqliteInt.h" /* ** This version of the memory allocator is used only if the -** SQLITE_MEMDEBUG macro is defined and SQLITE_OMIT_MEMORY_ALLOCATION -** is not defined. +** SQLITE_MEMDEBUG macro is defined */ -#if defined(SQLITE_MEMDEBUG) - -/* -** We will eventually construct multiple memory allocation subsystems -** suitable for use in various contexts: -** -** * Normal multi-threaded builds -** * Normal single-threaded builds -** * Debugging builds -** -** This version is suitable for use in debugging builds. -** -** Features: -** -** * Every allocate has guards at both ends. -** * New allocations are initialized with randomness -** * Allocations are overwritten with randomness when freed -** * Optional logs of malloc activity generated -** * Summary of outstanding allocations with backtraces to the -** point of allocation. -** * The ability to simulate memory allocation failure -*/ -#include "sqliteInt.h" -#include +#ifdef SQLITE_MEMDEBUG /* ** The backtrace functionality is only available with GLIBC @@ -55,6 +32,7 @@ # define backtrace(A,B) 0 # define backtrace_symbols_fd(A,B,C) #endif +#include /* ** Each memory allocation looks like this: @@ -477,4 +455,4 @@ int sqlite3_memdebug_malloc_count(){ } -#endif /* SQLITE_MEMDEBUG && !SQLITE_OMIT_MEMORY_ALLOCATION */ +#endif /* SQLITE_MEMDEBUG */ diff --git a/src/mem3.c b/src/mem3.c index 2d50931ef1..02fdcec2b8 100644 --- a/src/mem3.c +++ b/src/mem3.c @@ -20,19 +20,15 @@ ** This version of the memory allocation subsystem is used if ** and only if SQLITE_MEMORY_SIZE is defined. ** -** $Id: mem3.c,v 1.10 2008/02/14 15:31:52 danielk1977 Exp $ +** $Id: mem3.c,v 1.11 2008/02/14 23:26:56 drh Exp $ */ +#include "sqliteInt.h" /* ** This version of the memory allocator is used only when ** SQLITE_MEMORY_SIZE is defined. */ -#if defined(SQLITE_MEMORY_SIZE) -#include "sqliteInt.h" - -#ifdef SQLITE_MEMDEBUG -# error cannot define both SQLITE_MEMDEBUG and SQLITE_MEMORY_SIZE -#endif +#ifdef SQLITE_MEMORY_SIZE /* ** Maximum size (in Mem3Blocks) of a "small" chunk. diff --git a/src/mem4.c b/src/mem4.c index 7d861d44c5..39180b5f59 100644 --- a/src/mem4.c +++ b/src/mem4.c @@ -12,8 +12,9 @@ ** This file contains the C functions that implement a memory ** allocation subsystem for use by SQLite. ** -** $Id: mem4.c,v 1.1 2007/11/29 18:36:49 drh Exp $ +** $Id: mem4.c,v 1.2 2008/02/14 23:26:56 drh Exp $ */ +#include "sqliteInt.h" /* ** This version of the memory allocator attempts to obtain memory @@ -28,12 +29,7 @@ ** to support. This module may choose to use less memory than requested. ** */ -#if defined(SQLITE_MMAP_HEAP_SIZE) - -#if defined(SQLITE_MEMDEBUG) || defined(SQLITE_MEMORY_SIZE) -# error cannot use SQLITE_MMAP_HEAP_SIZE with either SQLITE_MEMDEBUG \ - or SQLITE_MEMORY_SIZE -#endif +#ifdef SQLITE_MMAP_HEAP_SIZE /* ** This is a test version of the memory allocator that attempts to @@ -43,7 +39,6 @@ #include #include #include -#include "sqliteInt.h" #include @@ -395,4 +390,4 @@ void *sqlite3_realloc(void *pPrior, int nBytes){ return (void*)p; } -#endif /* !SQLITE_MEMDEBUG && !SQLITE_OMIT_MEMORY_ALLOCATION */ +#endif /* SQLITE_MMAP_HEAP_SIZE */ diff --git a/src/mem5.c b/src/mem5.c new file mode 100644 index 0000000000..1ce321a666 --- /dev/null +++ b/src/mem5.c @@ -0,0 +1,662 @@ +/* +** 2007 October 14 +** +** The author disclaims copyright to this source code. In place of +** a legal notice, here is a blessing: +** +** May you do good and not evil. +** May you find forgiveness for yourself and forgive others. +** May you share freely, never taking more than you give. +** +************************************************************************* +** This file contains the C functions that implement a memory +** allocation subsystem for use by SQLite. +** +** This version of the memory allocation subsystem omits all +** use of malloc(). All dynamically allocatable memory is +** contained in a static array, mem.aPool[]. The size of this +** fixed memory pool is SQLITE_POW2_MEMORY_SIZE bytes. +** +** This version of the memory allocation subsystem is used if +** and only if SQLITE_POW2_MEMORY_SIZE is defined. +** +** $Id: mem5.c,v 1.1 2008/02/14 23:26:56 drh Exp $ +*/ +#include "sqliteInt.h" + +/* +** This version of the memory allocator is used only when +** SQLITE_POW2_MEMORY_SIZE is defined. +*/ +#ifdef SQLITE_POW2_MEMORY_SIZE + +/* +** Maximum size (in Mem3Blocks) of a "small" chunk. +*/ +#define MX_SMALL 10 + + +/* +** Number of freelist hash slots +*/ +#define N_HASH 61 + +/* +** A memory allocation (also called a "chunk") consists of two or +** more blocks where each block is 8 bytes. The first 8 bytes are +** a header that is not returned to the user. +** +** A chunk is two or more blocks that is either checked out or +** free. The first block has format u.hdr. u.hdr.size4x is 4 times the +** size of the allocation in blocks if the allocation is free. +** The u.hdr.size4x&1 bit is true if the chunk is checked out and +** false if the chunk is on the freelist. The u.hdr.size4x&2 bit +** is true if the previous chunk is checked out and false if the +** previous chunk is free. The u.hdr.prevSize field is the size of +** the previous chunk in blocks if the previous chunk is on the +** freelist. If the previous chunk is checked out, then +** u.hdr.prevSize can be part of the data for that chunk and should +** not be read or written. +** +** We often identify a chunk by its index in mem.aPool[]. When +** this is done, the chunk index refers to the second block of +** the chunk. In this way, the first chunk has an index of 1. +** A chunk index of 0 means "no such chunk" and is the equivalent +** of a NULL pointer. +** +** The second block of free chunks is of the form u.list. The +** two fields form a double-linked list of chunks of related sizes. +** Pointers to the head of the list are stored in mem.aiSmall[] +** for smaller chunks and mem.aiHash[] for larger chunks. +** +** The second block of a chunk is user data if the chunk is checked +** out. If a chunk is checked out, the user data may extend into +** the u.hdr.prevSize value of the following chunk. +*/ +typedef struct Mem3Block Mem3Block; +struct Mem3Block { + union { + struct { + u32 prevSize; /* Size of previous chunk in Mem3Block elements */ + u32 size4x; /* 4x the size of current chunk in Mem3Block elements */ + } hdr; + struct { + u32 next; /* Index in mem.aPool[] of next free chunk */ + u32 prev; /* Index in mem.aPool[] of previous free chunk */ + } list; + } u; +}; + +/* +** All of the static variables used by this module are collected +** into a single structure named "mem". This is to keep the +** static variables organized and to reduce namespace pollution +** when this module is combined with other in the amalgamation. +*/ +static struct { + /* + ** True if we are evaluating an out-of-memory callback. + */ + int alarmBusy; + + /* + ** Mutex to control access to the memory allocation subsystem. + */ + sqlite3_mutex *mutex; + + /* + ** The minimum amount of free space that we have seen. + */ + u32 mnMaster; + + /* + ** iMaster is the index of the master chunk. Most new allocations + ** occur off of this chunk. szMaster is the size (in Mem3Blocks) + ** of the current master. iMaster is 0 if there is not master chunk. + ** The master chunk is not in either the aiHash[] or aiSmall[]. + */ + u32 iMaster; + u32 szMaster; + + +u64 totalAlloc; +u64 totalExcess; +int nAlloc; + + /* + ** Array of lists of free blocks according to the block size + ** for smaller chunks, or a hash on the block size for larger + ** chunks. + */ + u32 aiSmall[MX_SMALL-1]; /* For sizes 2 through MX_SMALL, inclusive */ + u32 aiHash[N_HASH]; /* For sizes MX_SMALL+1 and larger */ + + /* + ** Memory available for allocation + */ + Mem3Block aPool[SQLITE_POW2_MEMORY_SIZE/sizeof(Mem3Block)+2]; +} mem; + +/* +** Unlink the chunk at mem.aPool[i] from list it is currently +** on. *pRoot is the list that i is a member of. +*/ +static void memsys3UnlinkFromList(u32 i, u32 *pRoot){ + u32 next = mem.aPool[i].u.list.next; + u32 prev = mem.aPool[i].u.list.prev; + assert( sqlite3_mutex_held(mem.mutex) ); + if( prev==0 ){ + *pRoot = next; + }else{ + mem.aPool[prev].u.list.next = next; + } + if( next ){ + mem.aPool[next].u.list.prev = prev; + } + mem.aPool[i].u.list.next = 0; + mem.aPool[i].u.list.prev = 0; +} + +/* +** Unlink the chunk at index i from +** whatever list is currently a member of. +*/ +static void memsys3Unlink(u32 i){ + u32 size, hash; + assert( sqlite3_mutex_held(mem.mutex) ); + assert( (mem.aPool[i-1].u.hdr.size4x & 1)==0 ); + assert( i>=1 ); + size = mem.aPool[i-1].u.hdr.size4x/4; + assert( size==mem.aPool[i+size-1].u.hdr.prevSize ); + assert( size>=2 ); + if( size <= MX_SMALL ){ + memsys3UnlinkFromList(i, &mem.aiSmall[size-2]); + }else{ + hash = size % N_HASH; + memsys3UnlinkFromList(i, &mem.aiHash[hash]); + } +} + +/* +** Link the chunk at mem.aPool[i] so that is on the list rooted +** at *pRoot. +*/ +static void memsys3LinkIntoList(u32 i, u32 *pRoot){ + assert( sqlite3_mutex_held(mem.mutex) ); + mem.aPool[i].u.list.next = *pRoot; + mem.aPool[i].u.list.prev = 0; + if( *pRoot ){ + mem.aPool[*pRoot].u.list.prev = i; + } + *pRoot = i; +} + +/* +** Link the chunk at index i into either the appropriate +** small chunk list, or into the large chunk hash table. +*/ +static void memsys3Link(u32 i){ + u32 size, hash; + assert( sqlite3_mutex_held(mem.mutex) ); + assert( i>=1 ); + assert( (mem.aPool[i-1].u.hdr.size4x & 1)==0 ); + size = mem.aPool[i-1].u.hdr.size4x/4; + assert( size==mem.aPool[i+size-1].u.hdr.prevSize ); + assert( size>=2 ); + if( size <= MX_SMALL ){ + memsys3LinkIntoList(i, &mem.aiSmall[size-2]); + }else{ + hash = size % N_HASH; + memsys3LinkIntoList(i, &mem.aiHash[hash]); + } +} + +/* +** Enter the mutex mem.mutex. Allocate it if it is not already allocated. +** +** Also: Initialize the memory allocation subsystem the first time +** this routine is called. +*/ +static void memsys3Enter(void){ + if( mem.mutex==0 ){ + mem.mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_MEM); + mem.aPool[0].u.hdr.size4x = SQLITE_POW2_MEMORY_SIZE/2 + 2; + mem.aPool[SQLITE_POW2_MEMORY_SIZE/8].u.hdr.prevSize = SQLITE_POW2_MEMORY_SIZE/8; + mem.aPool[SQLITE_POW2_MEMORY_SIZE/8].u.hdr.size4x = 1; + mem.iMaster = 1; + mem.szMaster = SQLITE_POW2_MEMORY_SIZE/8; + mem.mnMaster = mem.szMaster; + } + sqlite3_mutex_enter(mem.mutex); +} + +/* +** Return the amount of memory currently checked out. +*/ +sqlite3_int64 sqlite3_memory_used(void){ + sqlite3_int64 n; + memsys3Enter(); + n = SQLITE_POW2_MEMORY_SIZE - mem.szMaster*8; + sqlite3_mutex_leave(mem.mutex); + return n; +} + +/* +** Return the maximum amount of memory that has ever been +** checked out since either the beginning of this process +** or since the most recent reset. +*/ +sqlite3_int64 sqlite3_memory_highwater(int resetFlag){ + sqlite3_int64 n; + memsys3Enter(); + n = SQLITE_POW2_MEMORY_SIZE - mem.mnMaster*8; + if( resetFlag ){ + mem.mnMaster = mem.szMaster; + } +printf("alloc-cnt=%d avg-size=%lld avg-excess=%lld\n", +mem.nAlloc, mem.totalAlloc/mem.nAlloc, mem.totalExcess/mem.nAlloc); + sqlite3_mutex_leave(mem.mutex); + return n; +} + +/* +** Change the alarm callback. +** +** This is a no-op for the static memory allocator. The purpose +** of the memory alarm is to support sqlite3_soft_heap_limit(). +** But with this memory allocator, the soft_heap_limit is really +** a hard limit that is fixed at SQLITE_POW2_MEMORY_SIZE. +*/ +int sqlite3_memory_alarm( + void(*xCallback)(void *pArg, sqlite3_int64 used,int N), + void *pArg, + sqlite3_int64 iThreshold +){ + return SQLITE_OK; +} + +/* +** Called when we are unable to satisfy an allocation of nBytes. +*/ +static void memsys3OutOfMemory(int nByte){ + if( !mem.alarmBusy ){ + mem.alarmBusy = 1; + assert( sqlite3_mutex_held(mem.mutex) ); + sqlite3_mutex_leave(mem.mutex); + sqlite3_release_memory(nByte); + sqlite3_mutex_enter(mem.mutex); + mem.alarmBusy = 0; + } +} + +/* +** Return the size of an outstanding allocation, in bytes. The +** size returned omits the 8-byte header overhead. This only +** works for chunks that are currently checked out. +*/ +int sqlite3MallocSize(void *p){ + int iSize = 0; + if( p ){ + Mem3Block *pBlock = (Mem3Block*)p; + assert( (pBlock[-1].u.hdr.size4x&1)!=0 ); + iSize = (pBlock[-1].u.hdr.size4x&~3)*2 - 4; + } + return iSize; +} + +/* +** Chunk i is a free chunk that has been unlinked. Adjust its +** size parameters for check-out and return a pointer to the +** user portion of the chunk. +*/ +static void *memsys3Checkout(u32 i, int nBlock){ + u32 x; + assert( sqlite3_mutex_held(mem.mutex) ); + assert( i>=1 ); + assert( mem.aPool[i-1].u.hdr.size4x/4==nBlock ); + assert( mem.aPool[i+nBlock-1].u.hdr.prevSize==nBlock ); + x = mem.aPool[i-1].u.hdr.size4x; + mem.aPool[i-1].u.hdr.size4x = nBlock*4 | 1 | (x&2); + mem.aPool[i+nBlock-1].u.hdr.prevSize = nBlock; + mem.aPool[i+nBlock-1].u.hdr.size4x |= 2; + return &mem.aPool[i]; +} + +/* +** Carve a piece off of the end of the mem.iMaster free chunk. +** Return a pointer to the new allocation. Or, if the master chunk +** is not large enough, return 0. +*/ +static void *memsys3FromMaster(int nBlock){ + assert( sqlite3_mutex_held(mem.mutex) ); + assert( mem.szMaster>=nBlock ); + if( nBlock>=mem.szMaster-1 ){ + /* Use the entire master */ + void *p = memsys3Checkout(mem.iMaster, mem.szMaster); + mem.iMaster = 0; + mem.szMaster = 0; + mem.mnMaster = 0; + return p; + }else{ + /* Split the master block. Return the tail. */ + u32 newi, x; + newi = mem.iMaster + mem.szMaster - nBlock; + assert( newi > mem.iMaster+1 ); + mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.prevSize = nBlock; + mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.size4x |= 2; + mem.aPool[newi-1].u.hdr.size4x = nBlock*4 + 1; + mem.szMaster -= nBlock; + mem.aPool[newi-1].u.hdr.prevSize = mem.szMaster; + x = mem.aPool[mem.iMaster-1].u.hdr.size4x & 2; + mem.aPool[mem.iMaster-1].u.hdr.size4x = mem.szMaster*4 | x; + if( mem.szMaster < mem.mnMaster ){ + mem.mnMaster = mem.szMaster; + } + return (void*)&mem.aPool[newi]; + } +} + +/* +** *pRoot is the head of a list of free chunks of the same size +** or same size hash. In other words, *pRoot is an entry in either +** mem.aiSmall[] or mem.aiHash[]. +** +** This routine examines all entries on the given list and tries +** to coalesce each entries with adjacent free chunks. +** +** If it sees a chunk that is larger than mem.iMaster, it replaces +** the current mem.iMaster with the new larger chunk. In order for +** this mem.iMaster replacement to work, the master chunk must be +** linked into the hash tables. That is not the normal state of +** affairs, of course. The calling routine must link the master +** chunk before invoking this routine, then must unlink the (possibly +** changed) master chunk once this routine has finished. +*/ +static void memsys3Merge(u32 *pRoot){ + u32 iNext, prev, size, i, x; + + assert( sqlite3_mutex_held(mem.mutex) ); + for(i=*pRoot; i>0; i=iNext){ + iNext = mem.aPool[i].u.list.next; + size = mem.aPool[i-1].u.hdr.size4x; + assert( (size&1)==0 ); + if( (size&2)==0 ){ + memsys3UnlinkFromList(i, pRoot); + assert( i > mem.aPool[i-1].u.hdr.prevSize ); + prev = i - mem.aPool[i-1].u.hdr.prevSize; + if( prev==iNext ){ + iNext = mem.aPool[prev].u.list.next; + } + memsys3Unlink(prev); + size = i + size/4 - prev; + x = mem.aPool[prev-1].u.hdr.size4x & 2; + mem.aPool[prev-1].u.hdr.size4x = size*4 | x; + mem.aPool[prev+size-1].u.hdr.prevSize = size; + memsys3Link(prev); + i = prev; + }else{ + size /= 4; + } + if( size>mem.szMaster ){ + mem.iMaster = i; + mem.szMaster = size; + } + } +} + +/* +** Return a block of memory of at least nBytes in size. +** Return NULL if unable. +*/ +static void *memsys3Malloc(int nByte){ + u32 i; + int nBlock; + int toFree; + int x; + + assert( sqlite3_mutex_held(mem.mutex) ); + assert( sizeof(Mem3Block)==8 ); + for(x=256; x= 2 ); + + /* STEP 1: + ** Look for an entry of the correct size in either the small + ** chunk table or in the large chunk hash table. This is + ** successful most of the time (about 9 times out of 10). + */ + if( nBlock <= MX_SMALL ){ + i = mem.aiSmall[nBlock-2]; + if( i>0 ){ + memsys3UnlinkFromList(i, &mem.aiSmall[nBlock-2]); + return memsys3Checkout(i, nBlock); + } + }else{ + int hash = nBlock % N_HASH; + for(i=mem.aiHash[hash]; i>0; i=mem.aPool[i].u.list.next){ + if( mem.aPool[i-1].u.hdr.size4x/4==nBlock ){ + memsys3UnlinkFromList(i, &mem.aiHash[hash]); + return memsys3Checkout(i, nBlock); + } + } + } + + /* STEP 2: + ** Try to satisfy the allocation by carving a piece off of the end + ** of the master chunk. This step usually works if step 1 fails. + */ + if( mem.szMaster>=nBlock ){ + return memsys3FromMaster(nBlock); + } + + + /* STEP 3: + ** Loop through the entire memory pool. Coalesce adjacent free + ** chunks. Recompute the master chunk as the largest free chunk. + ** Then try again to satisfy the allocation by carving a piece off + ** of the end of the master chunk. This step happens very + ** rarely (we hope!) + */ + for(toFree=nBlock*16; toFree=nBlock ){ + return memsys3FromMaster(nBlock); + } + } + } + + /* If none of the above worked, then we fail. */ + return 0; +} + +/* +** Free an outstanding memory allocation. +*/ +void memsys3Free(void *pOld){ + Mem3Block *p = (Mem3Block*)pOld; + int i; + u32 size, x; + assert( sqlite3_mutex_held(mem.mutex) ); + assert( p>mem.aPool && p<&mem.aPool[SQLITE_POW2_MEMORY_SIZE/8] ); + i = p - mem.aPool; + assert( (mem.aPool[i-1].u.hdr.size4x&1)==1 ); + size = mem.aPool[i-1].u.hdr.size4x/4; + assert( i+size<=SQLITE_POW2_MEMORY_SIZE/8+1 ); + mem.aPool[i-1].u.hdr.size4x &= ~1; + mem.aPool[i+size-1].u.hdr.prevSize = size; + mem.aPool[i+size-1].u.hdr.size4x &= ~2; + memsys3Link(i); + + /* Try to expand the master using the newly freed chunk */ + if( mem.iMaster ){ + while( (mem.aPool[mem.iMaster-1].u.hdr.size4x&2)==0 ){ + size = mem.aPool[mem.iMaster-1].u.hdr.prevSize; + mem.iMaster -= size; + mem.szMaster += size; + memsys3Unlink(mem.iMaster); + x = mem.aPool[mem.iMaster-1].u.hdr.size4x & 2; + mem.aPool[mem.iMaster-1].u.hdr.size4x = mem.szMaster*4 | x; + mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.prevSize = mem.szMaster; + } + x = mem.aPool[mem.iMaster-1].u.hdr.size4x & 2; + while( (mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.size4x&1)==0 ){ + memsys3Unlink(mem.iMaster+mem.szMaster); + mem.szMaster += mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.size4x/4; + mem.aPool[mem.iMaster-1].u.hdr.size4x = mem.szMaster*4 | x; + mem.aPool[mem.iMaster+mem.szMaster-1].u.hdr.prevSize = mem.szMaster; + } + } +} + +/* +** Allocate nBytes of memory +*/ +void *sqlite3_malloc(int nBytes){ + sqlite3_int64 *p = 0; + if( nBytes>0 ){ + memsys3Enter(); + p = memsys3Malloc(nBytes); + sqlite3_mutex_leave(mem.mutex); + } + return (void*)p; +} + +/* +** Free memory. +*/ +void sqlite3_free(void *pPrior){ + if( pPrior==0 ){ + return; + } + assert( mem.mutex!=0 ); + sqlite3_mutex_enter(mem.mutex); + memsys3Free(pPrior); + sqlite3_mutex_leave(mem.mutex); +} + +/* +** Change the size of an existing memory allocation +*/ +void *sqlite3_realloc(void *pPrior, int nBytes){ + int nOld; + void *p; + if( pPrior==0 ){ + return sqlite3_malloc(nBytes); + } + if( nBytes<=0 ){ + sqlite3_free(pPrior); + return 0; + } + assert( mem.mutex!=0 ); + nOld = sqlite3MallocSize(pPrior); + if( nBytes<=nOld && nBytes>=nOld-128 ){ + return pPrior; + } + sqlite3_mutex_enter(mem.mutex); + p = memsys3Malloc(nBytes); + if( p ){ + if( nOld>1)!=(size&1) ){ + fprintf(out, "%p tail checkout bit is incorrect\n", &mem.aPool[i]); + assert( 0 ); + break; + } + if( size&1 ){ + fprintf(out, "%p %6d bytes checked out\n", &mem.aPool[i], (size/4)*8-8); + }else{ + fprintf(out, "%p %6d bytes free%s\n", &mem.aPool[i], (size/4)*8-8, + i==mem.iMaster ? " **master**" : ""); + } + } + for(i=0; i0; j=mem.aPool[j].u.list.next){ + fprintf(out, " %p(%d)", &mem.aPool[j], + (mem.aPool[j-1].u.hdr.size4x/4)*8-8); + } + fprintf(out, "\n"); + } + for(i=0; i0; j=mem.aPool[j].u.list.next){ + fprintf(out, " %p(%d)", &mem.aPool[j], + (mem.aPool[j-1].u.hdr.size4x/4)*8-8); + } + fprintf(out, "\n"); + } + fprintf(out, "master=%d\n", mem.iMaster); + fprintf(out, "nowUsed=%d\n", SQLITE_POW2_MEMORY_SIZE - mem.szMaster*8); + fprintf(out, "mxUsed=%d\n", SQLITE_POW2_MEMORY_SIZE - mem.mnMaster*8); + sqlite3_mutex_leave(mem.mutex); + if( out==stdout ){ + fflush(stdout); + }else{ + fclose(out); + } +#endif +} + + +#endif /* !SQLITE_POW2_MEMORY_SIZE */ diff --git a/src/pager.c b/src/pager.c index 5677761ce2..7780110ec2 100644 --- a/src/pager.c +++ b/src/pager.c @@ -18,7 +18,7 @@ ** file simultaneously, or one process from reading the database while ** another is writing. ** -** @(#) $Id: pager.c,v 1.405 2008/02/02 20:47:38 drh Exp $ +** @(#) $Id: pager.c,v 1.406 2008/02/14 23:26:56 drh Exp $ */ #ifndef SQLITE_OMIT_DISKIO #include "sqliteInt.h" @@ -1209,6 +1209,7 @@ static void pager_reset(Pager *pPager){ PAGER_INCR(sqlite3_pager_pgfree_count); pNext = pPg->pNextAll; lruListRemove(pPg); + sqlite3_free(pPg->pData); sqlite3_free(pPg); } assert(pPager->lru.pFirst==0); @@ -2539,6 +2540,7 @@ static void pager_truncate_cache(Pager *pPager){ PAGER_INCR(sqlite3_pager_pgfree_count); unlinkPage(pPg); makeClean(pPg); + sqlite3_free(pPg->pData); sqlite3_free(pPg); pPager->nPage--; } @@ -3205,6 +3207,7 @@ int sqlite3PagerReleaseMemory(int nReq){ ); IOTRACE(("PGFREE %p %d *\n", pPager, pPg->pgno)); PAGER_INCR(sqlite3_pager_pgfree_count); + sqlite3_free(pPg->pData); sqlite3_free(pPg); pPager->nPage--; }else{ @@ -3476,6 +3479,7 @@ static int pagerAllocatePage(Pager *pPager, PgHdr **ppPg){ || MEMDB || (pPager->lru.pFirstSynced==0 && pPager->doNotSync) ){ + void *pData; if( pPager->nPage>=pPager->nHash ){ pager_resize_hash_table(pPager, pPager->nHash<256 ? 256 : pPager->nHash*2); @@ -3487,14 +3491,21 @@ static int pagerAllocatePage(Pager *pPager, PgHdr **ppPg){ pagerLeave(pPager); nByteHdr = sizeof(*pPg) + sizeof(u32) + pPager->nExtra + MEMDB*sizeof(PgHistory); - pPg = sqlite3_malloc( nByteHdr + pPager->pageSize ); + pPg = sqlite3_malloc( nByteHdr ); + if( pPg ){ + pData = sqlite3_malloc( pPager->pageSize ); + if( pData==0 ){ + sqlite3_free(pPg); + pPg = 0; + } + } pagerEnter(pPager); if( pPg==0 ){ rc = SQLITE_NOMEM; goto pager_allocate_out; } memset(pPg, 0, nByteHdr); - pPg->pData = (void*)(nByteHdr + (char*)pPg); + pPg->pData = pData; pPg->pPager = pPager; pPg->pNextAll = pPager->pAll; pPager->pAll = pPg; diff --git a/src/sqliteInt.h b/src/sqliteInt.h index 8a3e6a3232..60ac09e9e9 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -11,7 +11,7 @@ ************************************************************************* ** Internal interface definitions for SQLite. ** -** @(#) $Id: sqliteInt.h,v 1.661 2008/02/13 18:25:27 danielk1977 Exp $ +** @(#) $Id: sqliteInt.h,v 1.662 2008/02/14 23:26:56 drh Exp $ */ #ifndef _SQLITEINT_H_ #define _SQLITEINT_H_ @@ -117,6 +117,32 @@ #endif #endif +/* +** Exactly one of the following macros must be defined in order to +** specify which memory allocation subsystem to use. +** +** SQLITE_SYSTEM_MALLOC // Use normal system malloc() +** SQLITE_MEMDEBUG // Debugging version of system malloc() +** SQLITE_MEMORY_SIZE // internal allocator #1 +** SQLITE_MMAP_HEAP_SIZE // internal mmap() allocator +** SQLITE_POW2_MEMORY_SIZE // internal power-of-two allocator +** +** If none of the above are defined, then set SQLITE_SYSTEM_MALLOC as +** the default. +*/ +#if defined(SQLITE_SYSTEM_MALLOC)+defined(SQLITE_MEMDEBUG)+\ + defined(SQLITE_MEMORY_SIZE)+defined(SQLITE_MMAP_HEAP_SIZE)+\ + defined(SQLITE_POW2_MEMORY_SIZE)>1 +# error "At most one of the following compile-time configuration options\ + is allows: SQLITE_SYSTEM_MALLOC, SQLITE_MEMDEBUG, SQLITE_MEMORY_SIZE,\ + SQLITE_MMAP_HEAP_SIZE, SQLITE_POW2_MEMORY_SIZE" +#endif +#if defined(SQLITE_SYSTEM_MALLOC)+defined(SQLITE_MEMDEBUG)+\ + defined(SQLITE_MEMORY_SIZE)+defined(SQLITE_MMAP_HEAP_SIZE)+\ + defined(SQLITE_POW2_MEMORY_SIZE)==0 +# define SQLITE_SYSTEM_MALLOC 1 +#endif + /* ** We need to define _XOPEN_SOURCE as follows in order to enable ** recursive mutexes on most unix systems. But Mac OS X is different. -- 2.47.3