diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/main.c | 9 | ||||
| -rw-r--r-- | src/mem1.c | 22 | ||||
| -rw-r--r-- | src/mem2.c | 18 | ||||
| -rw-r--r-- | src/mem6.c | 410 | ||||
| -rw-r--r-- | src/sqlite.h.in | 4 | ||||
| -rw-r--r-- | src/sqliteInt.h | 4 | ||||
| -rw-r--r-- | src/test_malloc.c | 23 |
7 files changed, 470 insertions, 20 deletions
diff --git a/src/main.c b/src/main.c index 70a9ad9e2..8cd1d6414 100644 --- a/src/main.c +++ b/src/main.c @@ -14,7 +14,7 @@ ** other files are for internal use by SQLite and should not be ** accessed by users of the library. ** -** $Id: main.c,v 1.480 2008/07/22 05:13:30 shane Exp $ +** $Id: main.c,v 1.481 2008/07/24 08:20:40 danielk1977 Exp $ */ #include "sqliteInt.h" #include <ctype.h> @@ -267,6 +267,13 @@ int sqlite3_config(int op, ...){ } #endif +#if defined(SQLITE_ENABLE_MEMSYS6) + case SQLITE_CONFIG_CHUNKALLOC: { + sqlite3Config.m = *sqlite3MemGetMemsys6(); + break; + } +#endif + default: { rc = SQLITE_ERROR; break; diff --git a/src/mem1.c b/src/mem1.c index 7f164f8ce..359ce5d8c 100644 --- a/src/mem1.c +++ b/src/mem1.c @@ -17,7 +17,7 @@ ** This file contains implementations of the low-level memory allocation ** routines specified in the sqlite3_mem_methods object. ** -** $Id: mem1.c,v 1.23 2008/06/23 15:10:25 danielk1977 Exp $ +** $Id: mem1.c,v 1.24 2008/07/24 08:20:40 danielk1977 Exp $ */ #include "sqliteInt.h" @@ -120,13 +120,7 @@ static void sqlite3MemShutdown(void *NotUsed){ return; } -/* -** This routine is the only routine in this file with external linkage. -** -** Populate the low-level memory allocation function pointers in -** sqlite3Config.m with pointers to the routines in this file. -*/ -void sqlite3MemSetDefault(void){ +sqlite3_mem_methods *sqlite3MemGetDefault(void){ static const sqlite3_mem_methods defaultMethods = { sqlite3MemMalloc, sqlite3MemFree, @@ -137,7 +131,17 @@ void sqlite3MemSetDefault(void){ sqlite3MemShutdown, 0 }; - sqlite3_config(SQLITE_CONFIG_MALLOC, &defaultMethods); + return &defaultMethods; +} + +/* +** This routine is the only routine in this file with external linkage. +** +** Populate the low-level memory allocation function pointers in +** sqlite3Config.m with pointers to the routines in this file. +*/ +void sqlite3MemSetDefault(void){ + sqlite3_config(SQLITE_CONFIG_MALLOC, sqlite3MemGetDefault()); } #endif /* SQLITE_SYSTEM_MALLOC */ diff --git a/src/mem2.c b/src/mem2.c index 5e9a999b7..46ae707e6 100644 --- a/src/mem2.c +++ b/src/mem2.c @@ -19,7 +19,7 @@ ** This file contains implementations of the low-level memory allocation ** routines specified in the sqlite3_mem_methods object. ** -** $Id: mem2.c,v 1.34 2008/07/10 18:13:42 drh Exp $ +** $Id: mem2.c,v 1.35 2008/07/24 08:20:40 danielk1977 Exp $ */ #include "sqliteInt.h" @@ -304,11 +304,7 @@ static void *sqlite3MemRealloc(void *pPrior, int nByte){ } -/* -** Populate the low-level memory allocation function pointers in -** sqlite3Config.m with pointers to the routines in this file. -*/ -void sqlite3MemSetDefault(void){ +sqlite3_mem_methods *sqlite3MemGetDefault(void){ static const sqlite3_mem_methods defaultMethods = { sqlite3MemMalloc, sqlite3MemFree, @@ -319,7 +315,15 @@ void sqlite3MemSetDefault(void){ sqlite3MemShutdown, 0 }; - sqlite3_config(SQLITE_CONFIG_MALLOC, &defaultMethods); + return &defaultMethods; +} + +/* +** Populate the low-level memory allocation function pointers in +** sqlite3Config.m with pointers to the routines in this file. +*/ +void sqlite3MemSetDefault(void){ + sqlite3_config(SQLITE_CONFIG_MALLOC, sqlite3MemGetDefault()); } /* diff --git a/src/mem6.c b/src/mem6.c new file mode 100644 index 000000000..a1b9898d5 --- /dev/null +++ b/src/mem6.c @@ -0,0 +1,410 @@ +/* +** 2008 July 24 +** +** 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. +** +************************************************************************* +** +** $Id: mem6.c,v 1.1 2008/07/24 08:20:40 danielk1977 Exp $ +*/ + +#ifdef SQLITE_ENABLE_MEMSYS6 + +/* +** Maximum size of any allocation is ((1<<LOGMAX)*Mem6Chunk.nAtom). Since +** Mem6Chunk.nAtom is always at least 8, this is not really a practical +** limitation. +*/ +#define LOGMAX 30 + +#include "sqliteInt.h" + +typedef struct Mem6Chunk Mem6Chunk; +typedef struct Mem6Link Mem6Link; + +/* +** 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. +*/ +struct Mem6Link { + int next; /* Index of next free chunk */ + int prev; /* Index of previous free chunk */ +}; + +/* +** Masks used for mem5.aCtrl[] elements. +*/ +#define CTRL_LOGSIZE 0x1f /* Log2 Size of this block relative to POW2_MIN */ +#define CTRL_FREE 0x20 /* True if not checked out */ + +struct Mem6Chunk { + Mem6Chunk *pNext; + + /* + ** Lists of free blocks of various sizes. + */ + int aiFreelist[LOGMAX+1]; + + int nCheckedOut; /* Number of currently outstanding allocations */ + + /* + ** Space for tracking which blocks are checked out and the size + ** of each block. One byte per block. + */ + u8 *aCtrl; + + /* + ** Memory available for allocation + */ + int nAtom; /* Smallest possible allocation in bytes */ + int nBlock; /* Number of nAtom sized blocks in zPool */ + u8 *zPool; /* Pointer to memory chunk from which allocations are made */ +}; + +#define MEM6LINK(idx) ((Mem6Link *)(&pChunk->zPool[(idx)*pChunk->nAtom])) + +/* +** Unlink the chunk at pChunk->aPool[i] from list it is currently +** on. It should be found on pChunk->aiFreelist[iLogsize]. +*/ +static void memsys6Unlink(Mem6Chunk *pChunk, int i, int iLogsize){ + int next, prev; + assert( i>=0 && i<pChunk->nBlock ); + assert( iLogsize>=0 && iLogsize<=LOGMAX ); + assert( (pChunk->aCtrl[i] & CTRL_LOGSIZE)==iLogsize ); + + next = MEM6LINK(i)->next; + prev = MEM6LINK(i)->prev; + if( prev<0 ){ + pChunk->aiFreelist[iLogsize] = next; + }else{ + MEM6LINK(prev)->next = next; + } + if( next>=0 ){ + MEM6LINK(next)->prev = prev; + } +} + +/* +** Link the chunk at mem5.aPool[i] so that is on the iLogsize +** free list. +*/ +static void memsys6Link(Mem6Chunk *pChunk, int i, int iLogsize){ + int x; + assert( i>=0 && i<pChunk->nBlock ); + assert( iLogsize>=0 && iLogsize<=LOGMAX ); + assert( (pChunk->aCtrl[i] & CTRL_LOGSIZE)==iLogsize ); + + x = MEM6LINK(i)->next = pChunk->aiFreelist[iLogsize]; + MEM6LINK(i)->prev = -1; + if( x>=0 ){ + assert( x<pChunk->nBlock ); + MEM6LINK(x)->prev = i; + } + pChunk->aiFreelist[iLogsize] = i; +} + + +/* +** Find the first entry on the freelist iLogsize. Unlink that +** entry and return its index. +*/ +static int memsys6UnlinkFirst(Mem6Chunk *pChunk, int iLogsize){ + int i; + int iFirst; + + assert( iLogsize>=0 && iLogsize<=LOGMAX ); + i = iFirst = pChunk->aiFreelist[iLogsize]; + assert( iFirst>=0 ); + while( i>0 ){ + if( i<iFirst ) iFirst = i; + i = MEM6LINK(i)->next; + } + memsys6Unlink(pChunk, iFirst, iLogsize); + return iFirst; +} + +/* +** Allocate and return a block of nByte bytes from chunk pChunk. If the +** allocation request cannot be satisfied, return 0. +*/ +static void *chunkMalloc(Mem6Chunk *pChunk, int nByte){ + int i; /* Index of a mem5.aPool[] slot */ + int iBin; /* Index into mem5.aiFreelist[] */ + int iFullSz; /* Size of allocation rounded up to power of 2 */ + int iLogsize; /* Log2 of iFullSz/POW2_MIN */ + + /* Round nByte up to the next valid power of two */ + if( nByte>(pChunk->nBlock*pChunk->nAtom) ) return 0; + for(iFullSz=pChunk->nAtom, iLogsize=0; iFullSz<nByte; iFullSz *= 2, iLogsize++){} + + /* Make sure mem5.aiFreelist[iLogsize] contains at least one free + ** block. If not, then split a block of the next larger power of + ** two in order to create a new free block of size iLogsize. + */ + for(iBin=iLogsize; pChunk->aiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){} + if( iBin>LOGMAX ) return 0; + i = memsys6UnlinkFirst(pChunk, iBin); + while( iBin>iLogsize ){ + int newSize; + + iBin--; + newSize = 1 << iBin; + pChunk->aCtrl[i+newSize] = CTRL_FREE | iBin; + memsys6Link(pChunk, i+newSize, iBin); + } + pChunk->aCtrl[i] = iLogsize; + + /* Return a pointer to the allocated memory. */ + pChunk->nCheckedOut++; + return (void*)&pChunk->zPool[i*pChunk->nAtom]; +} + +/* +** Free the allocation pointed to by p, which is guaranteed to be non-zero +** and a part of chunk object pChunk. +*/ +static void chunkFree(Mem6Chunk *pChunk, void *pOld){ + u32 size, iLogsize; + int iBlock; + + /* Set iBlock to the index of the block pointed to by pOld in + ** the array of pChunk->nAtom byte blocks pointed to by pChunk->zPool. + */ + iBlock = ((u8 *)pOld-pChunk->zPool)/pChunk->nAtom; + + /* Check that the pointer pOld points to a valid, non-free block. */ + assert( iBlock>=0 && iBlock<pChunk->nBlock ); + assert( ((u8 *)pOld-pChunk->zPool)%pChunk->nAtom==0 ); + assert( (pChunk->aCtrl[iBlock] & CTRL_FREE)==0 ); + + iLogsize = pChunk->aCtrl[iBlock] & CTRL_LOGSIZE; + size = 1<<iLogsize; + assert( iBlock+size-1<pChunk->nBlock ); + + pChunk->aCtrl[iBlock] |= CTRL_FREE; + pChunk->aCtrl[iBlock+size-1] |= CTRL_FREE; + + pChunk->aCtrl[iBlock] = CTRL_FREE | iLogsize; + while( iLogsize<LOGMAX ){ + int iBuddy; + if( (iBlock>>iLogsize) & 1 ){ + iBuddy = iBlock - size; + }else{ + iBuddy = iBlock + size; + } + assert( iBuddy>=0 ); + if( (iBuddy+(1<<iLogsize))>pChunk->nBlock ) break; + if( pChunk->aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break; + memsys6Unlink(pChunk, iBuddy, iLogsize); + iLogsize++; + if( iBuddy<iBlock ){ + pChunk->aCtrl[iBuddy] = CTRL_FREE | iLogsize; + pChunk->aCtrl[iBlock] = 0; + iBlock = iBuddy; + }else{ + pChunk->aCtrl[iBlock] = CTRL_FREE | iLogsize; + pChunk->aCtrl[iBuddy] = 0; + } + size *= 2; + } + pChunk->nCheckedOut--; + memsys6Link(pChunk, iBlock, iLogsize); +} + +/* +** Return the actual size of the block pointed to by p, which is guaranteed +** to have been allocated from chunk pChunk. +*/ +static int chunkSize(Mem6Chunk *pChunk, void *p){ + int iSize = 0; + if( p ){ + int i = ((u8 *)p-pChunk->zPool)/pChunk->nAtom; + assert( i>=0 && i<pChunk->nBlock ); + iSize = pChunk->nAtom * (1 << (pChunk->aCtrl[i]&CTRL_LOGSIZE)); + } + return iSize; +} + +/* +** Return true if there are currently no outstanding allocations. +*/ +static int chunkIsEmpty(Mem6Chunk *pChunk){ + return (pChunk->nCheckedOut==0); +} + +/* +** Initialize the buffer zChunk, which is nChunk bytes in size, as +** an Mem6Chunk object. Return a copy of the zChunk pointer. +*/ +static Mem6Chunk *chunkInit(u8 *zChunk, int nChunk, int nMinAlloc){ + int ii; + int iOffset; + Mem6Chunk *pChunk = (Mem6Chunk *)zChunk; + + assert( nChunk>sizeof(Mem6Chunk) ); + assert( nMinAlloc>sizeof(Mem6Link) ); + + memset(pChunk, 0, sizeof(Mem6Chunk)); + pChunk->nAtom = nMinAlloc; + pChunk->nBlock = ((nChunk-sizeof(Mem6Chunk)) / (pChunk->nAtom+sizeof(u8))); + + pChunk->zPool = (u8 *)&pChunk[1]; + pChunk->aCtrl = &pChunk->zPool[pChunk->nBlock*pChunk->nAtom]; + + for(ii=0; ii<=LOGMAX; ii++){ + pChunk->aiFreelist[ii] = -1; + } + + iOffset = 0; + for(ii=LOGMAX; ii>=0; ii--){ + int nAlloc = (1<<ii); + if( (iOffset+nAlloc)<=pChunk->nBlock ){ + pChunk->aCtrl[iOffset] = ii | CTRL_FREE; + memsys6Link(pChunk, iOffset, ii); + iOffset += nAlloc; + } + assert((iOffset+nAlloc)>pChunk->nBlock); + } + + return pChunk; +} + +struct Mem6Global { + sqlite3_mem_methods parent; /* Used to allocate chunks */ + int nChunkSize; /* Size of each chunk, in bytes. */ + int nMinAlloc; /* Minimum allowed allocation size */ + + /* This data structure will be fixed... */ + Mem6Chunk *pChunk; /* Singly linked list of all memory chunks */ +} mem6; + +/* +** The argument is a pointer that may or may not have been allocated from +** one of the Mem6Chunk objects managed within mem6. If it is, return +** a pointer to the owner chunk. If not, return 0. +*/ +static Mem6Chunk *findChunk(u8 *p){ + Mem6Chunk *pChunk; + for(pChunk=mem6.pChunk; pChunk; pChunk=pChunk->pNext){ + if( p>=pChunk->zPool && p<=&pChunk->zPool[pChunk->nBlock*pChunk->nAtom] ){ + return pChunk; + } + } + return 0; +} + +static void freeChunk(Mem6Chunk *pChunk){ + Mem6Chunk **pp = &mem6.pChunk; + for( pp=&mem6.pChunk; *pp!=pChunk; pp = &(*pp)->pNext ); + *pp = (*pp)->pNext; + mem6.parent.xFree(pChunk); +} + +static void *memsys6Malloc(int nByte){ + Mem6Chunk *pChunk; + void *p; + if( nByte>=mem6.nChunkSize/3 ){ + return mem6.parent.xMalloc(nByte); + } + for(pChunk=mem6.pChunk; pChunk; pChunk=pChunk->pNext){ + p = chunkMalloc(pChunk, nByte); + if( p ){ + return p; + } + } + + p = mem6.parent.xMalloc(mem6.nChunkSize); + if( p ){ + pChunk = chunkInit((u8 *)p, mem6.nChunkSize, mem6.nMinAlloc); + pChunk->pNext = mem6.pChunk; + mem6.pChunk = pChunk; + p = chunkMalloc(pChunk, nByte); + assert(p); + } + + return p; +} + +static int memsys6Size(void *p){ + Mem6Chunk *pChunk = findChunk(p); + return (pChunk ? chunkSize(pChunk, p) : mem6.parent.xSize(p)); +} + +static void memsys6Free(void *p){ + Mem6Chunk *pChunk = findChunk(p); + if( pChunk ){ + chunkFree(pChunk, p); + if( chunkIsEmpty(pChunk) ){ + freeChunk(pChunk); + } + }else{ + mem6.parent.xFree(p); + } +} + +static void *memsys6Realloc(void *p, int nByte){ + Mem6Chunk *pChunk = findChunk(p); + void *p2; + + if( !pChunk ){ + return mem6.parent.xRealloc(p, nByte); + } + + p2 = memsys6Malloc(nByte); + if( p2 ){ + assert( memsys6Size(p)<nByte ); + memcpy(p2, p, memsys6Size(p)); + memsys6Free(p); + } + return p2; +} + + +static int memsys6Roundup(int n){ + int iFullSz; + for(iFullSz=mem6.nMinAlloc; iFullSz<n; iFullSz *= 2); + return iFullSz; +} + +static int memsys6Init(void *pCtx){ + mem6.parent = *sqlite3MemGetDefault(); + mem6.nChunkSize = (1<<16); + mem6.nMinAlloc = 16; + mem6.pChunk = 0; + + /* Initialize the parent allocator. */ + mem6.parent.xInit(mem6.parent.pAppData); + + return SQLITE_OK; +} + +static void memsys6Shutdown(void *pCtx){ +} + +/* +** This routine is the only routine in this file with external +** linkage. It returns a pointer to a static sqlite3_mem_methods +** struct populated with the memsys6 methods. +*/ +const sqlite3_mem_methods *sqlite3MemGetMemsys6(void){ + static const sqlite3_mem_methods memsys6Methods = { + memsys6Malloc, + memsys6Free, + memsys6Realloc, + memsys6Size, + memsys6Roundup, + memsys6Init, + memsys6Shutdown, + 0 + }; + return &memsys6Methods; +} + +#endif diff --git a/src/sqlite.h.in b/src/sqlite.h.in index 20545ab8c..3a7f1a220 100644 --- a/src/sqlite.h.in +++ b/src/sqlite.h.in @@ -30,7 +30,7 @@ ** the version number) and changes its name to "sqlite3.h" as ** part of the build process. ** -** @(#) $Id: sqlite.h.in,v 1.377 2008/07/23 18:25:56 drh Exp $ +** @(#) $Id: sqlite.h.in,v 1.378 2008/07/24 08:20:40 danielk1977 Exp $ */ #ifndef _SQLITE3_H_ #define _SQLITE3_H_ @@ -1158,6 +1158,8 @@ struct sqlite3_mem_methods { #define SQLITE_CONFIG_MUTEX 10 /* sqlite3_mutex_methods* */ #define SQLITE_CONFIG_GETMUTEX 11 /* sqlite3_mutex_methods* */ +#define SQLITE_CONFIG_CHUNKALLOC 12 /* nil */ + /* ** CAPI3REF: Enable Or Disable Extended Result Codes {H12200} <S10700> diff --git a/src/sqliteInt.h b/src/sqliteInt.h index 07d7a3f81..28d6176d5 100644 --- a/src/sqliteInt.h +++ b/src/sqliteInt.h @@ -11,7 +11,7 @@ ************************************************************************* ** Internal interface definitions for SQLite. ** -** @(#) $Id: sqliteInt.h,v 1.743 2008/07/23 18:17:32 drh Exp $ +** @(#) $Id: sqliteInt.h,v 1.744 2008/07/24 08:20:40 danielk1977 Exp $ */ #ifndef _SQLITEINT_H_ #define _SQLITEINT_H_ @@ -1841,8 +1841,10 @@ void sqlite3ScratchFree(void*); void *sqlite3PageMalloc(int); void sqlite3PageFree(void*); void sqlite3MemSetDefault(void); +sqlite3_mem_methods *sqlite3MemGetDefault(void); const sqlite3_mem_methods *sqlite3MemGetMemsys5(void); const sqlite3_mem_methods *sqlite3MemGetMemsys3(void); +const sqlite3_mem_methods *sqlite3MemGetMemsys6(void); void sqlite3BenignMallocHooks(void (*)(void), void (*)(void)); #ifndef SQLITE_MUTEX_NOOP diff --git a/src/test_malloc.c b/src/test_malloc.c index 052f198ea..30df0348f 100644 --- a/src/test_malloc.c +++ b/src/test_malloc.c @@ -13,7 +13,7 @@ ** This file contains code used to implement test interfaces to the ** memory allocation subsystem. ** -** $Id: test_malloc.c,v 1.38 2008/07/16 12:25:32 drh Exp $ +** $Id: test_malloc.c,v 1.39 2008/07/24 08:20:40 danielk1977 Exp $ */ #include "sqliteInt.h" #include "tcl.h" @@ -957,6 +957,26 @@ static int test_config_memstatus( } /* +** Usage: sqlite3_config_chunkalloc +** +*/ +static int test_config_chunkalloc( + void * clientData, + Tcl_Interp *interp, + int objc, + Tcl_Obj *CONST objv[] +){ + int rc; + if( objc!=1 ){ + Tcl_WrongNumArgs(interp, 1, objv, ""); + return TCL_ERROR; + } + rc = sqlite3_config(SQLITE_CONFIG_CHUNKALLOC); + Tcl_SetObjResult(interp, Tcl_NewIntObj(rc)); + return TCL_OK; +} + +/* ** Usage: ** ** sqlite3_config_heap NBYTE NMINALLOC @@ -1142,6 +1162,7 @@ int Sqlitetest_malloc_Init(Tcl_Interp *interp){ { "install_malloc_faultsim", test_install_malloc_faultsim ,0 }, { "sqlite3_config_heap", test_config_heap ,0 }, { "sqlite3_config_memstatus", test_config_memstatus ,0 }, + { "sqlite3_config_chunkalloc", test_config_chunkalloc ,0 }, { "sqlite3_dump_memsys3", test_dump_memsys3 ,3 }, { "sqlite3_dump_memsys5", test_dump_memsys3 ,5 } }; |