/*

 ** 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.

 **

 *************************************************************************

 **

 ** This file contains an alternative memory allocation system for SQLite.

 ** This system is implemented as a wrapper around the system provided

 ** by the operating system - vanilla malloc(), realloc() and free().

 **

 ** This system differentiates between requests for "small" allocations 

 ** (by default those of 128 bytes or less) and "large" allocations (all

 ** others). The 256 byte threshhold is configurable at runtime.

 **

 ** All requests for large allocations are passed through to the 

 ** default system.

 **

 ** Requests for small allocations are met by allocating space within

 ** one or more larger "chunks" of memory obtained from the default

 ** memory allocation system. Chunks of memory are usually 64KB or 

 ** larger. The algorithm used to manage space within each chunk is

 ** the same as that used by mem5.c. 

 **

 ** This strategy is designed to prevent the default memory allocation

 ** system (usually the system malloc) from suffering from heap 

 ** fragmentation. On some systems, heap fragmentation can cause a 

 ** significant real-time slowdown.

 **

 ** $Id: mem6.c,v 1.7 2008/07/28 19:34:53 drh Exp $

 */

 #ifdef SQLITE_ENABLE_MEMSYS6

 #include "sqliteInt.h"

 /*

 ** Maximum size of any "small" allocation is ((1<<LOGMAX)*Mem6Chunk.nAtom).

 ** Mem6Chunk.nAtom is always at least 8, so this is not a practical

 ** limitation

 */

 #define LOGMAX 30

 /*

 ** Default value for the "small" allocation size threshold.

 */

 #define SMALL_MALLOC_DEFAULT_THRESHOLD 256

 /*

 ** Minimum size for a memory chunk.

 */

 #define MIN_CHUNKSIZE (1<<16)

 #define LOG2_MINALLOC 4

 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]))

 struct Mem6Global {

   int nMinAlloc;                  /* Minimum allowed allocation size */

   int nThreshold;                 /* Allocs larger than this go to malloc() */

   int nLogThreshold;              /* log2 of (nThreshold/nMinAlloc) */

   sqlite3_mutex *mutex;

   Mem6Chunk *pChunk;              /* Singly linked list of all memory chunks */

 } mem6;

 /*

 ** 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<=mem6.nLogThreshold );

   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<=mem6.nLogThreshold );

   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<=mem6.nLogThreshold );

   i = iFirst = pChunk->aiFreelist[iLogsize];

   assert( iFirst>=0 );

   memsys6Unlink(pChunk, iFirst, iLogsize);

   return iFirst;

 }

 static int roundupLog2(int n){

   static const char LogTable256[256] = {

     0,                                                    /* 1 */

     1,                                                    /* 2 */

     2, 2,                                                 /* 3..4 */

     3, 3, 3, 3,                                           /* 5..8 */

     4, 4, 4, 4, 4, 4, 4, 4,                               /* 9..16 */

     5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5, 5,       /* 17..32 */

     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,

     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,       /* 33..64 */

     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,

     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,

     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,

     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,       /* 65..128 */

     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,

     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,

     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,

     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,

     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,

     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,

     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,

     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,       /* 129..256 */

   };

   assert(n<=(1<<16) && n>0);

   if( n<=256 ) return LogTable256[n-1];

   return LogTable256[(n>>8) - ((n&0xFF)?0:1)] + 8;

 }

 /*

 ** Allocate and return a block of (pChunk->nAtom << iLogsize) bytes from chunk

 ** pChunk. If the allocation request cannot be satisfied, return 0.

 */

 static void *chunkMalloc(Mem6Chunk *pChunk, int iLogsize){

   int i;           /* Index of a mem5.aPool[] slot */

   int iBin;        /* Index into mem5.aiFreelist[] */

   /* 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<=mem6.nLogThreshold; iBin++){}

   if( iBin>mem6.nLogThreshold ) 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<mem6.nLogThreshold ){

     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<=mem6.nLogThreshold; ii++){

     pChunk->aiFreelist[ii] = -1;

   }

   iOffset = 0;

   for(ii=mem6.nLogThreshold; ii>=0; ii--){

     int nAlloc = (1<<ii);

     while( (iOffset+nAlloc)<=pChunk->nBlock ){

       pChunk->aCtrl[iOffset] = ii | CTRL_FREE;

       memsys6Link(pChunk, iOffset, ii);

       iOffset += nAlloc;

     }

   }

   return pChunk;

 }

 static void mem6Enter(void){

   sqlite3_mutex_enter(mem6.mutex);

 }

 static void mem6Leave(void){

   sqlite3_mutex_leave(mem6.mutex);

 }

 /*

 ** Based on the number and size of the currently allocated chunks, return

 ** the size of the next chunk to allocate, in bytes.

 */

 static int nextChunkSize(void){

   int iTotal = MIN_CHUNKSIZE;

   Mem6Chunk *p;

   for(p=mem6.pChunk; p; p=p->pNext){

     iTotal = iTotal*2;

   }

   return iTotal;

 }

 static void freeChunk(Mem6Chunk *pChunk){

   Mem6Chunk **pp = &mem6.pChunk;

   for( pp=&mem6.pChunk; *pp!=pChunk; pp = &(*pp)->pNext );

   *pp = (*pp)->pNext;

   free(pChunk);

 }

 static void *memsys6Malloc(int nByte){

   Mem6Chunk *pChunk;

   void *p = 0;

   int nTotal = nByte+8;

   int iOffset = 0;

   if( nTotal>mem6.nThreshold ){

     p = malloc(nTotal);

   }else{

     int iLogsize = 0;

     if( nTotal>(1<<LOG2_MINALLOC) ){

       iLogsize = roundupLog2(nTotal) - LOG2_MINALLOC;

     }

     mem6Enter();

     for(pChunk=mem6.pChunk; pChunk; pChunk=pChunk->pNext){

       p = chunkMalloc(pChunk, iLogsize);

       if( p ){

         break;

       }

     }

     if( !p ){

       int iSize = nextChunkSize();

       p = malloc(iSize);

       if( p ){

         pChunk = chunkInit((u8 *)p, iSize, mem6.nMinAlloc);

         pChunk->pNext = mem6.pChunk;

         mem6.pChunk = pChunk;

         p = chunkMalloc(pChunk, iLogsize);

         assert(p);

       }

     }

     iOffset = ((u8*)p - (u8*)pChunk);

     mem6Leave();

   }

   if( !p ){

     return 0;

   }

   ((u32 *)p)[0] = iOffset;

   ((u32 *)p)[1] = nByte;

   return &((u32 *)p)[2];

 }

 static int memsys6Size(void *pPrior){

   if( pPrior==0 ) return 0;

   return ((u32*)pPrior)[-1];

 }

 static void memsys6Free(void *pPrior){

   int iSlot;

   void *p = &((u32 *)pPrior)[-2];

   iSlot = ((u32 *)p)[0];

   if( iSlot ){

     Mem6Chunk *pChunk;

     mem6Enter();

     pChunk = (Mem6Chunk *)(&((u8 *)p)[-1 * iSlot]);

     chunkFree(pChunk, p);

     if( chunkIsEmpty(pChunk) ){

       freeChunk(pChunk);

     }

     mem6Leave();

   }else{

     free(p);

   }

 }

 static void *memsys6Realloc(void *p, int nByte){

   void *p2;

   if( p && nByte<=memsys6Size(p) ){

     p2 = p;

   }else{

     p2 = memsys6Malloc(nByte);

     if( p && p2 ){

       memcpy(p2, p, memsys6Size(p));

       memsys6Free(p);

     }

   }

   return p2;

 }

 static int memsys6Roundup(int n){

   if( n>mem6.nThreshold ){

     return n;

   }else{

     return (1<<roundupLog2(n));

   }

 }

 static int memsys6Init(void *pCtx){

   u8 bMemstat = sqlite3Config.bMemstat;

   mem6.nMinAlloc = (1 << LOG2_MINALLOC);

   mem6.pChunk = 0;

   mem6.nThreshold = sqlite3Config.nSmall;

   if( mem6.nThreshold<=0 ){

     mem6.nThreshold = SMALL_MALLOC_DEFAULT_THRESHOLD;

   }

   mem6.nLogThreshold = roundupLog2(mem6.nThreshold) - LOG2_MINALLOC;

   if( !bMemstat ){

     mem6.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);

   }

   return SQLITE_OK;

 }

 static void memsys6Shutdown(void *pCtx){

   memset(&mem6, 0, sizeof(mem6));

 }

 /*

 ** 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