--- /dev/null Thu Jan 01 00:00:00 1970 +0000
+++ b/persistentstorage/sql/SQLite/mem5.c Fri Jan 22 11:06:30 2010 +0200
@@ -0,0 +1,515 @@
+/*
+** 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(). The SQLite user supplies 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,
+** the amount of memory available to SQLite is fixed and cannot
+** be changed.
+**
+** This version of the memory allocation subsystem is included
+** in the build only if SQLITE_ENABLE_MEMSYS5 is defined.
+**
+** $Id: mem5.c,v 1.11 2008/07/16 12:25:32 drh Exp $
+*/
+#include "sqliteInt.h"
+
+/*
+** This version of the memory allocator is used only when
+** SQLITE_POW2_MEMORY_SIZE is defined.
+*/
+#ifdef SQLITE_ENABLE_MEMSYS5
+
+/*
+** Log2 of the minimum size of an allocation. For example, if
+** 4 then all allocations will be rounded up to at least 16 bytes.
+** If 5 then all allocations will be rounded up to at least 32 bytes.
+*/
+#ifndef SQLITE_POW2_LOGMIN
+# define SQLITE_POW2_LOGMIN 6
+#endif
+
+/*
+** Log2 of the maximum size of an allocation.
+*/
+#ifndef SQLITE_POW2_LOGMAX
+# define SQLITE_POW2_LOGMAX 20
+#endif
+#define POW2_MAX (((unsigned int)1)<<SQLITE_POW2_LOGMAX)
+
+/*
+** Number of distinct allocation sizes.
+*/
+#define NSIZE (SQLITE_POW2_LOGMAX - SQLITE_POW2_LOGMIN + 1)
+
+/*
+** 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.
+*/
+typedef struct Mem5Link Mem5Link;
+struct Mem5Link {
+ int next; /* Index of next free chunk */
+ int prev; /* Index of previous free chunk */
+};
+
+/*
+** 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.
+*/
+#define LOGMAX 30
+
+/*
+** 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 */
+
+/*
+** All of the static variables used by this module are collected
+** into a single structure named "mem5". 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 {
+ /*
+ ** The alarm callback and its arguments. The mem5.mutex lock will
+ ** be held while the callback is running. Recursive calls into
+ ** the memory subsystem are allowed, but no new callbacks will be
+ ** issued. The alarmBusy variable is set to prevent recursive
+ ** callbacks.
+ */
+ sqlite3_int64 alarmThreshold;
+ void (*alarmCallback)(void*, sqlite3_int64,int);
+ void *alarmArg;
+ int alarmBusy;
+
+ /*
+ ** Mutex to control access to the memory allocation subsystem.
+ */
+ sqlite3_mutex *mutex;
+
+ /*
+ ** Performance statistics
+ */
+ u64 nAlloc; /* Total number of calls to malloc */
+ u64 totalAlloc; /* Total of all malloc calls - includes internal frag */
+ u64 totalExcess; /* Total internal fragmentation */
+ u32 currentOut; /* Current checkout, including internal fragmentation */
+ u32 currentCount; /* Current number of distinct checkouts */
+ u32 maxOut; /* Maximum instantaneous currentOut */
+ u32 maxCount; /* Maximum instantaneous currentCount */
+ u32 maxRequest; /* Largest allocation (exclusive of internal frag) */
+
+ /*
+ ** Lists of free blocks of various sizes.
+ */
+ int aiFreelist[LOGMAX+1];
+
+ /*
+ ** 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;
+} mem5;
+
+#define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.nAtom]))
+
+/*
+** Unlink the chunk at mem5.aPool[i] from list it is currently
+** on. It should be found on mem5.aiFreelist[iLogsize].
+*/
+static void memsys5Unlink(int i, int iLogsize){
+ int next, prev;
+ assert( i>=0 && i<mem5.nBlock );
+ assert( iLogsize>=0 && iLogsize<=LOGMAX );
+ assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
+
+ next = MEM5LINK(i)->next;
+ prev = MEM5LINK(i)->prev;
+ if( prev<0 ){
+ mem5.aiFreelist[iLogsize] = next;
+ }else{
+ MEM5LINK(prev)->next = next;
+ }
+ if( next>=0 ){
+ MEM5LINK(next)->prev = prev;
+ }
+}
+
+/*
+** Link the chunk at mem5.aPool[i] so that is on the iLogsize
+** free list.
+*/
+static void memsys5Link(int i, int iLogsize){
+ int x;
+ assert( sqlite3_mutex_held(mem5.mutex) );
+ assert( i>=0 && i<mem5.nBlock );
+ assert( iLogsize>=0 && iLogsize<=LOGMAX );
+ assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
+
+ x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize];
+ MEM5LINK(i)->prev = -1;
+ if( x>=0 ){
+ assert( x<mem5.nBlock );
+ MEM5LINK(x)->prev = i;
+ }
+ mem5.aiFreelist[iLogsize] = i;
+}
+
+/*
+** If the STATIC_MEM mutex is not already held, obtain it now. The mutex
+** will already be held (obtained by code in malloc.c) if
+** sqlite3Config.bMemStat is true.
+*/
+static void memsys5Enter(void){
+ if( sqlite3Config.bMemstat==0 && mem5.mutex==0 ){
+ mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);
+ }
+ sqlite3_mutex_enter(mem5.mutex);
+}
+static void memsys5Leave(void){
+ sqlite3_mutex_leave(mem5.mutex);
+}
+
+/*
+** 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.
+*/
+static int memsys5Size(void *p){
+ int iSize = 0;
+ if( p ){
+ int i = ((u8 *)p-mem5.zPool)/mem5.nAtom;
+ assert( i>=0 && i<mem5.nBlock );
+ iSize = mem5.nAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));
+ }
+ return iSize;
+}
+
+/*
+** Find the first entry on the freelist iLogsize. Unlink that
+** entry and return its index.
+*/
+static int memsys5UnlinkFirst(int iLogsize){
+ int i;
+ int iFirst;
+
+ assert( iLogsize>=0 && iLogsize<=LOGMAX );
+ i = iFirst = mem5.aiFreelist[iLogsize];
+ assert( iFirst>=0 );
+ while( i>0 ){
+ if( i<iFirst ) iFirst = i;
+ i = MEM5LINK(i)->next;
+ }
+ memsys5Unlink(iFirst, iLogsize);
+ return iFirst;
+}
+
+/*
+** Return a block of memory of at least nBytes in size.
+** Return NULL if unable.
+*/
+static void *memsys5MallocUnsafe(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 */
+
+ /* Keep track of the maximum allocation request. Even unfulfilled
+ ** requests are counted */
+ if( nByte>mem5.maxRequest ){
+ mem5.maxRequest = nByte;
+ }
+
+ /* Round nByte up to the next valid power of two */
+ if( nByte>POW2_MAX ) return 0;
+ for(iFullSz=mem5.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; mem5.aiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){}
+ if( iBin>LOGMAX ) return 0;
+ i = memsys5UnlinkFirst(iBin);
+ while( iBin>iLogsize ){
+ int newSize;
+
+ iBin--;
+ newSize = 1 << iBin;
+ mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;
+ memsys5Link(i+newSize, iBin);
+ }
+ mem5.aCtrl[i] = iLogsize;
+
+ /* Update allocator performance statistics. */
+ mem5.nAlloc++;
+ mem5.totalAlloc += iFullSz;
+ mem5.totalExcess += iFullSz - nByte;
+ mem5.currentCount++;
+ mem5.currentOut += iFullSz;
+ if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount;
+ if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut;
+
+ /* Return a pointer to the allocated memory. */
+ return (void*)&mem5.zPool[i*mem5.nAtom];
+}
+
+/*
+** Free an outstanding memory allocation.
+*/
+static void memsys5FreeUnsafe(void *pOld){
+ u32 size, iLogsize;
+ 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.
+ */
+ iBlock = ((u8 *)pOld-mem5.zPool)/mem5.nAtom;
+
+ /* Check that the pointer pOld points to a valid, non-free block. */
+ assert( iBlock>=0 && iBlock<mem5.nBlock );
+ assert( ((u8 *)pOld-mem5.zPool)%mem5.nAtom==0 );
+ assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 );
+
+ iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;
+ size = 1<<iLogsize;
+ assert( iBlock+size-1<mem5.nBlock );
+
+ mem5.aCtrl[iBlock] |= CTRL_FREE;
+ mem5.aCtrl[iBlock+size-1] |= CTRL_FREE;
+ assert( mem5.currentCount>0 );
+ assert( mem5.currentOut>=0 );
+ mem5.currentCount--;
+ mem5.currentOut -= size*mem5.nAtom;
+ assert( mem5.currentOut>0 || mem5.currentCount==0 );
+ assert( mem5.currentCount>0 || mem5.currentOut==0 );
+
+ mem5.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))>mem5.nBlock ) break;
+ if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;
+ memsys5Unlink(iBuddy, iLogsize);
+ iLogsize++;
+ if( iBuddy<iBlock ){
+ mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;
+ mem5.aCtrl[iBlock] = 0;
+ iBlock = iBuddy;
+ }else{
+ mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
+ mem5.aCtrl[iBuddy] = 0;
+ }
+ size *= 2;
+ }
+ memsys5Link(iBlock, iLogsize);
+}
+
+/*
+** Allocate nBytes of memory
+*/
+static void *memsys5Malloc(int nBytes){
+ sqlite3_int64 *p = 0;
+ if( nBytes>0 ){
+ memsys5Enter();
+ p = memsys5MallocUnsafe(nBytes);
+ memsys5Leave();
+ }
+ return (void*)p;
+}
+
+/*
+** Free memory.
+*/
+static void memsys5Free(void *pPrior){
+ if( pPrior==0 ){
+assert(0);
+ return;
+ }
+ memsys5Enter();
+ memsys5FreeUnsafe(pPrior);
+ memsys5Leave();
+}
+
+/*
+** Change the size of an existing memory allocation
+*/
+static void *memsys5Realloc(void *pPrior, int nBytes){
+ int nOld;
+ void *p;
+ if( pPrior==0 ){
+ return memsys5Malloc(nBytes);
+ }
+ if( nBytes<=0 ){
+ memsys5Free(pPrior);
+ return 0;
+ }
+ nOld = memsys5Size(pPrior);
+ if( nBytes<=nOld ){
+ return pPrior;
+ }
+ memsys5Enter();
+ p = memsys5MallocUnsafe(nBytes);
+ if( p ){
+ memcpy(p, pPrior, nOld);
+ memsys5FreeUnsafe(pPrior);
+ }
+ memsys5Leave();
+ return p;
+}
+
+/*
+** Round up a request size to the next valid allocation size.
+*/
+static int memsys5Roundup(int n){
+ int iFullSz;
+ for(iFullSz=mem5.nAtom; iFullSz<n; iFullSz *= 2);
+ return iFullSz;
+}
+
+static int memsys5Log(int iValue){
+ int iLog;
+ for(iLog=0; (1<<iLog)<iValue; iLog++);
+ return iLog;
+}
+
+/*
+** Initialize this module.
+*/
+static int memsys5Init(void *NotUsed){
+ int ii;
+ int nByte = sqlite3Config.nHeap;
+ u8 *zByte = (u8 *)sqlite3Config.pHeap;
+ int nMinLog; /* Log of minimum allocation size in bytes*/
+ int iOffset;
+
+ if( !zByte ){
+ return SQLITE_ERROR;
+ }
+
+ nMinLog = memsys5Log(sqlite3Config.mnReq);
+ mem5.nAtom = (1<<nMinLog);
+ while( sizeof(Mem5Link)>mem5.nAtom ){
+ mem5.nAtom = mem5.nAtom << 1;
+ }
+
+ mem5.nBlock = (nByte / (mem5.nAtom+sizeof(u8)));
+ mem5.zPool = zByte;
+ mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.nAtom];
+
+ for(ii=0; ii<=LOGMAX; ii++){
+ mem5.aiFreelist[ii] = -1;
+ }
+
+ iOffset = 0;
+ for(ii=LOGMAX; ii>=0; ii--){
+ int nAlloc = (1<<ii);
+ if( (iOffset+nAlloc)<=mem5.nBlock ){
+ mem5.aCtrl[iOffset] = ii | CTRL_FREE;
+ memsys5Link(iOffset, ii);
+ iOffset += nAlloc;
+ }
+ assert((iOffset+nAlloc)>mem5.nBlock);
+ }
+
+ return SQLITE_OK;
+}
+
+/*
+** Deinitialize this module.
+*/
+static void memsys5Shutdown(void *NotUsed){
+ return;
+}
+
+/*
+** Open the file indicated and write a log of all unfreed memory
+** allocations into that log.
+*/
+void sqlite3Memsys5Dump(const char *zFilename){
+#ifdef SQLITE_DEBUG
+ FILE *out;
+ int i, j, n;
+ int nMinLog;
+
+ if( zFilename==0 || zFilename[0]==0 ){
+ out = stdout;
+ }else{
+ out = fopen(zFilename, "w");
+ if( out==0 ){
+ fprintf(stderr, "** Unable to output memory debug output log: %s **\n",
+ zFilename);
+ return;
+ }
+ }
+ memsys5Enter();
+ nMinLog = memsys5Log(mem5.nAtom);
+ for(i=0; i<=LOGMAX && i+nMinLog<32; i++){
+ for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){}
+ fprintf(out, "freelist items of size %d: %d\n", mem5.nAtom << i, n);
+ }
+ fprintf(out, "mem5.nAlloc = %llu\n", mem5.nAlloc);
+ fprintf(out, "mem5.totalAlloc = %llu\n", mem5.totalAlloc);
+ fprintf(out, "mem5.totalExcess = %llu\n", mem5.totalExcess);
+ fprintf(out, "mem5.currentOut = %u\n", mem5.currentOut);
+ fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount);
+ fprintf(out, "mem5.maxOut = %u\n", mem5.maxOut);
+ fprintf(out, "mem5.maxCount = %u\n", mem5.maxCount);
+ fprintf(out, "mem5.maxRequest = %u\n", mem5.maxRequest);
+ memsys5Leave();
+ if( out==stdout ){
+ fflush(stdout);
+ }else{
+ fclose(out);
+ }
+#endif
+}
+
+/*
+** 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 memsys5 methods.
+*/
+const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){
+ static const sqlite3_mem_methods memsys5Methods = {
+ memsys5Malloc,
+ memsys5Free,
+ memsys5Realloc,
+ memsys5Size,
+ memsys5Roundup,
+ memsys5Init,
+ memsys5Shutdown,
+ 0
+ };
+ return &memsys5Methods;
+}
+
+#endif /* SQLITE_ENABLE_MEMSYS5 */