Add mem6.c, a new allocator. More to come. (CVS 5467)
FossilOrigin-Name: 192bc192185a7b475ef9331e2a4a0dc68083ec03
diff --git a/src/main.c b/src/main.c
index 70a9ad9..8cd1d64 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 @@
}
#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 7f164f8..359ce5d 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 @@
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 @@
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 5e9a999..46ae707 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 @@
}
-/*
-** 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 @@
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 0000000..a1b9898
--- /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 20545ab..3a7f1a2 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 @@
#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 07d7a3f..28d6176 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 *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 052f198..30df034 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 @@
}
/*
+** 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 @@
{ "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 }
};