/*

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