sl@0: /*
sl@0: ** 2007 October 14
sl@0: **
sl@0: ** The author disclaims copyright to this source code.  In place of
sl@0: ** a legal notice, here is a blessing:
sl@0: **
sl@0: **    May you do good and not evil.
sl@0: **    May you find forgiveness for yourself and forgive others.
sl@0: **    May you share freely, never taking more than you give.
sl@0: **
sl@0: *************************************************************************
sl@0: ** This file contains the C functions that implement a memory
sl@0: ** allocation subsystem for use by SQLite. 
sl@0: **
sl@0: ** This version of the memory allocation subsystem omits all
sl@0: ** use of malloc(). The SQLite user supplies a block of memory
sl@0: ** before calling sqlite3_initialize() from which allocations
sl@0: ** are made and returned by the xMalloc() and xRealloc() 
sl@0: ** implementations. Once sqlite3_initialize() has been called,
sl@0: ** the amount of memory available to SQLite is fixed and cannot
sl@0: ** be changed.
sl@0: **
sl@0: ** This version of the memory allocation subsystem is included
sl@0: ** in the build only if SQLITE_ENABLE_MEMSYS5 is defined.
sl@0: **
sl@0: ** $Id: mem5.c,v 1.14 2008/09/02 17:52:52 danielk1977 Exp $
sl@0: */
sl@0: #include "sqliteInt.h"
sl@0: 
sl@0: /*
sl@0: ** This version of the memory allocator is used only when 
sl@0: ** SQLITE_POW2_MEMORY_SIZE is defined.
sl@0: */
sl@0: #ifdef SQLITE_ENABLE_MEMSYS5
sl@0: 
sl@0: /*
sl@0: ** Log2 of the minimum size of an allocation.  For example, if
sl@0: ** 4 then all allocations will be rounded up to at least 16 bytes.
sl@0: ** If 5 then all allocations will be rounded up to at least 32 bytes.
sl@0: */
sl@0: #ifndef SQLITE_POW2_LOGMIN
sl@0: # define SQLITE_POW2_LOGMIN 6
sl@0: #endif
sl@0: 
sl@0: /*
sl@0: ** Log2 of the maximum size of an allocation.
sl@0: */
sl@0: #ifndef SQLITE_POW2_LOGMAX
sl@0: # define SQLITE_POW2_LOGMAX 20
sl@0: #endif
sl@0: #define POW2_MAX (((unsigned int)1)<<SQLITE_POW2_LOGMAX)
sl@0: 
sl@0: /*
sl@0: ** Number of distinct allocation sizes.
sl@0: */
sl@0: #define NSIZE (SQLITE_POW2_LOGMAX - SQLITE_POW2_LOGMIN + 1)
sl@0: 
sl@0: /*
sl@0: ** A minimum allocation is an instance of the following structure.
sl@0: ** Larger allocations are an array of these structures where the
sl@0: ** size of the array is a power of 2.
sl@0: */
sl@0: typedef struct Mem5Link Mem5Link;
sl@0: struct Mem5Link {
sl@0:   int next;       /* Index of next free chunk */
sl@0:   int prev;       /* Index of previous free chunk */
sl@0: };
sl@0: 
sl@0: /*
sl@0: ** Maximum size of any allocation is ((1<<LOGMAX)*mem5.nAtom). Since
sl@0: ** mem5.nAtom is always at least 8, this is not really a practical
sl@0: ** limitation.
sl@0: */
sl@0: #define LOGMAX 30
sl@0: 
sl@0: /*
sl@0: ** Masks used for mem5.aCtrl[] elements.
sl@0: */
sl@0: #define CTRL_LOGSIZE  0x1f    /* Log2 Size of this block relative to POW2_MIN */
sl@0: #define CTRL_FREE     0x20    /* True if not checked out */
sl@0: 
sl@0: /*
sl@0: ** All of the static variables used by this module are collected
sl@0: ** into a single structure named "mem5".  This is to keep the
sl@0: ** static variables organized and to reduce namespace pollution
sl@0: ** when this module is combined with other in the amalgamation.
sl@0: */
sl@0: static SQLITE_WSD struct Mem5Global {
sl@0:   /*
sl@0:   ** Memory available for allocation
sl@0:   */
sl@0:   int nAtom;       /* Smallest possible allocation in bytes */
sl@0:   int nBlock;      /* Number of nAtom sized blocks in zPool */
sl@0:   u8 *zPool;
sl@0:   
sl@0:   /*
sl@0:   ** Mutex to control access to the memory allocation subsystem.
sl@0:   */
sl@0:   sqlite3_mutex *mutex;
sl@0: 
sl@0:   /*
sl@0:   ** Performance statistics
sl@0:   */
sl@0:   u64 nAlloc;         /* Total number of calls to malloc */
sl@0:   u64 totalAlloc;     /* Total of all malloc calls - includes internal frag */
sl@0:   u64 totalExcess;    /* Total internal fragmentation */
sl@0:   u32 currentOut;     /* Current checkout, including internal fragmentation */
sl@0:   u32 currentCount;   /* Current number of distinct checkouts */
sl@0:   u32 maxOut;         /* Maximum instantaneous currentOut */
sl@0:   u32 maxCount;       /* Maximum instantaneous currentCount */
sl@0:   u32 maxRequest;     /* Largest allocation (exclusive of internal frag) */
sl@0:   
sl@0:   /*
sl@0:   ** Lists of free blocks of various sizes.
sl@0:   */
sl@0:   int aiFreelist[LOGMAX+1];
sl@0: 
sl@0:   /*
sl@0:   ** Space for tracking which blocks are checked out and the size
sl@0:   ** of each block.  One byte per block.
sl@0:   */
sl@0:   u8 *aCtrl;
sl@0: 
sl@0: } mem5 = { 19804167 };
sl@0: 
sl@0: #define mem5 GLOBAL(struct Mem5Global, mem5)
sl@0: 
sl@0: #define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.nAtom]))
sl@0: 
sl@0: /*
sl@0: ** Unlink the chunk at mem5.aPool[i] from list it is currently
sl@0: ** on.  It should be found on mem5.aiFreelist[iLogsize].
sl@0: */
sl@0: static void memsys5Unlink(int i, int iLogsize){
sl@0:   int next, prev;
sl@0:   assert( i>=0 && i<mem5.nBlock );
sl@0:   assert( iLogsize>=0 && iLogsize<=LOGMAX );
sl@0:   assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
sl@0: 
sl@0:   next = MEM5LINK(i)->next;
sl@0:   prev = MEM5LINK(i)->prev;
sl@0:   if( prev<0 ){
sl@0:     mem5.aiFreelist[iLogsize] = next;
sl@0:   }else{
sl@0:     MEM5LINK(prev)->next = next;
sl@0:   }
sl@0:   if( next>=0 ){
sl@0:     MEM5LINK(next)->prev = prev;
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Link the chunk at mem5.aPool[i] so that is on the iLogsize
sl@0: ** free list.
sl@0: */
sl@0: static void memsys5Link(int i, int iLogsize){
sl@0:   int x;
sl@0:   assert( sqlite3_mutex_held(mem5.mutex) );
sl@0:   assert( i>=0 && i<mem5.nBlock );
sl@0:   assert( iLogsize>=0 && iLogsize<=LOGMAX );
sl@0:   assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );
sl@0: 
sl@0:   x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize];
sl@0:   MEM5LINK(i)->prev = -1;
sl@0:   if( x>=0 ){
sl@0:     assert( x<mem5.nBlock );
sl@0:     MEM5LINK(x)->prev = i;
sl@0:   }
sl@0:   mem5.aiFreelist[iLogsize] = i;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** If the STATIC_MEM mutex is not already held, obtain it now. The mutex
sl@0: ** will already be held (obtained by code in malloc.c) if
sl@0: ** sqlite3GlobalConfig.bMemStat is true.
sl@0: */
sl@0: static void memsys5Enter(void){
sl@0:   if( sqlite3GlobalConfig.bMemstat==0 && mem5.mutex==0 ){
sl@0:     mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);
sl@0:   }
sl@0:   sqlite3_mutex_enter(mem5.mutex);
sl@0: }
sl@0: static void memsys5Leave(void){
sl@0:   sqlite3_mutex_leave(mem5.mutex);
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Return the size of an outstanding allocation, in bytes.  The
sl@0: ** size returned omits the 8-byte header overhead.  This only
sl@0: ** works for chunks that are currently checked out.
sl@0: */
sl@0: static int memsys5Size(void *p){
sl@0:   int iSize = 0;
sl@0:   if( p ){
sl@0:     int i = ((u8 *)p-mem5.zPool)/mem5.nAtom;
sl@0:     assert( i>=0 && i<mem5.nBlock );
sl@0:     iSize = mem5.nAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));
sl@0:   }
sl@0:   return iSize;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Find the first entry on the freelist iLogsize.  Unlink that
sl@0: ** entry and return its index. 
sl@0: */
sl@0: static int memsys5UnlinkFirst(int iLogsize){
sl@0:   int i;
sl@0:   int iFirst;
sl@0: 
sl@0:   assert( iLogsize>=0 && iLogsize<=LOGMAX );
sl@0:   i = iFirst = mem5.aiFreelist[iLogsize];
sl@0:   assert( iFirst>=0 );
sl@0:   while( i>0 ){
sl@0:     if( i<iFirst ) iFirst = i;
sl@0:     i = MEM5LINK(i)->next;
sl@0:   }
sl@0:   memsys5Unlink(iFirst, iLogsize);
sl@0:   return iFirst;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Return a block of memory of at least nBytes in size.
sl@0: ** Return NULL if unable.
sl@0: */
sl@0: static void *memsys5MallocUnsafe(int nByte){
sl@0:   int i;           /* Index of a mem5.aPool[] slot */
sl@0:   int iBin;        /* Index into mem5.aiFreelist[] */
sl@0:   int iFullSz;     /* Size of allocation rounded up to power of 2 */
sl@0:   int iLogsize;    /* Log2 of iFullSz/POW2_MIN */
sl@0: 
sl@0:   /* Keep track of the maximum allocation request.  Even unfulfilled
sl@0:   ** requests are counted */
sl@0:   if( nByte>mem5.maxRequest ){
sl@0:     mem5.maxRequest = nByte;
sl@0:   }
sl@0: 
sl@0:   /* Round nByte up to the next valid power of two */
sl@0:   if( nByte>POW2_MAX ) return 0;
sl@0:   for(iFullSz=mem5.nAtom, iLogsize=0; iFullSz<nByte; iFullSz *= 2, iLogsize++){}
sl@0: 
sl@0:   /* Make sure mem5.aiFreelist[iLogsize] contains at least one free
sl@0:   ** block.  If not, then split a block of the next larger power of
sl@0:   ** two in order to create a new free block of size iLogsize.
sl@0:   */
sl@0:   for(iBin=iLogsize; mem5.aiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){}
sl@0:   if( iBin>LOGMAX ) return 0;
sl@0:   i = memsys5UnlinkFirst(iBin);
sl@0:   while( iBin>iLogsize ){
sl@0:     int newSize;
sl@0: 
sl@0:     iBin--;
sl@0:     newSize = 1 << iBin;
sl@0:     mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;
sl@0:     memsys5Link(i+newSize, iBin);
sl@0:   }
sl@0:   mem5.aCtrl[i] = iLogsize;
sl@0: 
sl@0:   /* Update allocator performance statistics. */
sl@0:   mem5.nAlloc++;
sl@0:   mem5.totalAlloc += iFullSz;
sl@0:   mem5.totalExcess += iFullSz - nByte;
sl@0:   mem5.currentCount++;
sl@0:   mem5.currentOut += iFullSz;
sl@0:   if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount;
sl@0:   if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut;
sl@0: 
sl@0:   /* Return a pointer to the allocated memory. */
sl@0:   return (void*)&mem5.zPool[i*mem5.nAtom];
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Free an outstanding memory allocation.
sl@0: */
sl@0: static void memsys5FreeUnsafe(void *pOld){
sl@0:   u32 size, iLogsize;
sl@0:   int iBlock;             
sl@0: 
sl@0:   /* Set iBlock to the index of the block pointed to by pOld in 
sl@0:   ** the array of mem5.nAtom byte blocks pointed to by mem5.zPool.
sl@0:   */
sl@0:   iBlock = ((u8 *)pOld-mem5.zPool)/mem5.nAtom;
sl@0: 
sl@0:   /* Check that the pointer pOld points to a valid, non-free block. */
sl@0:   assert( iBlock>=0 && iBlock<mem5.nBlock );
sl@0:   assert( ((u8 *)pOld-mem5.zPool)%mem5.nAtom==0 );
sl@0:   assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 );
sl@0: 
sl@0:   iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;
sl@0:   size = 1<<iLogsize;
sl@0:   assert( iBlock+size-1<mem5.nBlock );
sl@0: 
sl@0:   mem5.aCtrl[iBlock] |= CTRL_FREE;
sl@0:   mem5.aCtrl[iBlock+size-1] |= CTRL_FREE;
sl@0:   assert( mem5.currentCount>0 );
sl@0:   assert( mem5.currentOut>=0 );
sl@0:   mem5.currentCount--;
sl@0:   mem5.currentOut -= size*mem5.nAtom;
sl@0:   assert( mem5.currentOut>0 || mem5.currentCount==0 );
sl@0:   assert( mem5.currentCount>0 || mem5.currentOut==0 );
sl@0: 
sl@0:   mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
sl@0:   while( iLogsize<LOGMAX ){
sl@0:     int iBuddy;
sl@0:     if( (iBlock>>iLogsize) & 1 ){
sl@0:       iBuddy = iBlock - size;
sl@0:     }else{
sl@0:       iBuddy = iBlock + size;
sl@0:     }
sl@0:     assert( iBuddy>=0 );
sl@0:     if( (iBuddy+(1<<iLogsize))>mem5.nBlock ) break;
sl@0:     if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;
sl@0:     memsys5Unlink(iBuddy, iLogsize);
sl@0:     iLogsize++;
sl@0:     if( iBuddy<iBlock ){
sl@0:       mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;
sl@0:       mem5.aCtrl[iBlock] = 0;
sl@0:       iBlock = iBuddy;
sl@0:     }else{
sl@0:       mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;
sl@0:       mem5.aCtrl[iBuddy] = 0;
sl@0:     }
sl@0:     size *= 2;
sl@0:   }
sl@0:   memsys5Link(iBlock, iLogsize);
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Allocate nBytes of memory
sl@0: */
sl@0: static void *memsys5Malloc(int nBytes){
sl@0:   sqlite3_int64 *p = 0;
sl@0:   if( nBytes>0 ){
sl@0:     memsys5Enter();
sl@0:     p = memsys5MallocUnsafe(nBytes);
sl@0:     memsys5Leave();
sl@0:   }
sl@0:   return (void*)p; 
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Free memory.
sl@0: */
sl@0: static void memsys5Free(void *pPrior){
sl@0:   if( pPrior==0 ){
sl@0: assert(0);
sl@0:     return;
sl@0:   }
sl@0:   memsys5Enter();
sl@0:   memsys5FreeUnsafe(pPrior);
sl@0:   memsys5Leave();  
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Change the size of an existing memory allocation
sl@0: */
sl@0: static void *memsys5Realloc(void *pPrior, int nBytes){
sl@0:   int nOld;
sl@0:   void *p;
sl@0:   if( pPrior==0 ){
sl@0:     return memsys5Malloc(nBytes);
sl@0:   }
sl@0:   if( nBytes<=0 ){
sl@0:     memsys5Free(pPrior);
sl@0:     return 0;
sl@0:   }
sl@0:   nOld = memsys5Size(pPrior);
sl@0:   if( nBytes<=nOld ){
sl@0:     return pPrior;
sl@0:   }
sl@0:   memsys5Enter();
sl@0:   p = memsys5MallocUnsafe(nBytes);
sl@0:   if( p ){
sl@0:     memcpy(p, pPrior, nOld);
sl@0:     memsys5FreeUnsafe(pPrior);
sl@0:   }
sl@0:   memsys5Leave();
sl@0:   return p;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Round up a request size to the next valid allocation size.
sl@0: */
sl@0: static int memsys5Roundup(int n){
sl@0:   int iFullSz;
sl@0:   for(iFullSz=mem5.nAtom; iFullSz<n; iFullSz *= 2);
sl@0:   return iFullSz;
sl@0: }
sl@0: 
sl@0: static int memsys5Log(int iValue){
sl@0:   int iLog;
sl@0:   for(iLog=0; (1<<iLog)<iValue; iLog++);
sl@0:   return iLog;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Initialize this module.
sl@0: */
sl@0: static int memsys5Init(void *NotUsed){
sl@0:   int ii;
sl@0:   int nByte = sqlite3GlobalConfig.nHeap;
sl@0:   u8 *zByte = (u8 *)sqlite3GlobalConfig.pHeap;
sl@0:   int nMinLog;                 /* Log of minimum allocation size in bytes*/
sl@0:   int iOffset;
sl@0: 
sl@0:   if( !zByte ){
sl@0:     return SQLITE_ERROR;
sl@0:   }
sl@0: 
sl@0:   nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq);
sl@0:   mem5.nAtom = (1<<nMinLog);
sl@0:   while( sizeof(Mem5Link)>mem5.nAtom ){
sl@0:     mem5.nAtom = mem5.nAtom << 1;
sl@0:   }
sl@0: 
sl@0:   mem5.nBlock = (nByte / (mem5.nAtom+sizeof(u8)));
sl@0:   mem5.zPool = zByte;
sl@0:   mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.nAtom];
sl@0: 
sl@0:   for(ii=0; ii<=LOGMAX; ii++){
sl@0:     mem5.aiFreelist[ii] = -1;
sl@0:   }
sl@0: 
sl@0:   iOffset = 0;
sl@0:   for(ii=LOGMAX; ii>=0; ii--){
sl@0:     int nAlloc = (1<<ii);
sl@0:     if( (iOffset+nAlloc)<=mem5.nBlock ){
sl@0:       mem5.aCtrl[iOffset] = ii | CTRL_FREE;
sl@0:       memsys5Link(iOffset, ii);
sl@0:       iOffset += nAlloc;
sl@0:     }
sl@0:     assert((iOffset+nAlloc)>mem5.nBlock);
sl@0:   }
sl@0: 
sl@0:   return SQLITE_OK;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Deinitialize this module.
sl@0: */
sl@0: static void memsys5Shutdown(void *NotUsed){
sl@0:   return;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Open the file indicated and write a log of all unfreed memory 
sl@0: ** allocations into that log.
sl@0: */
sl@0: void sqlite3Memsys5Dump(const char *zFilename){
sl@0: #ifdef SQLITE_DEBUG
sl@0:   FILE *out;
sl@0:   int i, j, n;
sl@0:   int nMinLog;
sl@0: 
sl@0:   if( zFilename==0 || zFilename[0]==0 ){
sl@0:     out = stdout;
sl@0:   }else{
sl@0:     out = fopen(zFilename, "w");
sl@0:     if( out==0 ){
sl@0:       fprintf(stderr, "** Unable to output memory debug output log: %s **\n",
sl@0:                       zFilename);
sl@0:       return;
sl@0:     }
sl@0:   }
sl@0:   memsys5Enter();
sl@0:   nMinLog = memsys5Log(mem5.nAtom);
sl@0:   for(i=0; i<=LOGMAX && i+nMinLog<32; i++){
sl@0:     for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){}
sl@0:     fprintf(out, "freelist items of size %d: %d\n", mem5.nAtom << i, n);
sl@0:   }
sl@0:   fprintf(out, "mem5.nAlloc       = %llu\n", mem5.nAlloc);
sl@0:   fprintf(out, "mem5.totalAlloc   = %llu\n", mem5.totalAlloc);
sl@0:   fprintf(out, "mem5.totalExcess  = %llu\n", mem5.totalExcess);
sl@0:   fprintf(out, "mem5.currentOut   = %u\n", mem5.currentOut);
sl@0:   fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount);
sl@0:   fprintf(out, "mem5.maxOut       = %u\n", mem5.maxOut);
sl@0:   fprintf(out, "mem5.maxCount     = %u\n", mem5.maxCount);
sl@0:   fprintf(out, "mem5.maxRequest   = %u\n", mem5.maxRequest);
sl@0:   memsys5Leave();
sl@0:   if( out==stdout ){
sl@0:     fflush(stdout);
sl@0:   }else{
sl@0:     fclose(out);
sl@0:   }
sl@0: #endif
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** This routine is the only routine in this file with external 
sl@0: ** linkage. It returns a pointer to a static sqlite3_mem_methods
sl@0: ** struct populated with the memsys5 methods.
sl@0: */
sl@0: const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){
sl@0:   static const sqlite3_mem_methods memsys5Methods = {
sl@0:      memsys5Malloc,
sl@0:      memsys5Free,
sl@0:      memsys5Realloc,
sl@0:      memsys5Size,
sl@0:      memsys5Roundup,
sl@0:      memsys5Init,
sl@0:      memsys5Shutdown,
sl@0:      0
sl@0:   };
sl@0:   return &memsys5Methods;
sl@0: }
sl@0: 
sl@0: #endif /* SQLITE_ENABLE_MEMSYS5 */