-/************** Begin file mem6.c ********************************************/
-/*
-** 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.10 2008/09/02 17:52:52 danielk1977 Exp $
-*/
-
-#ifdef SQLITE_ENABLE_MEMSYS6
-
-
-/*
-** 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]))
-
-static SQLITE_WSD 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 = { 48642791 };
-
-#define mem6 GLOBAL(struct Mem6Global, 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 = sqlite3GlobalConfig.bMemstat;
- mem6.nMinAlloc = (1 << LOG2_MINALLOC);
- mem6.pChunk = 0;
- mem6.nThreshold = sqlite3GlobalConfig.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.
-*/
-SQLITE_PRIVATE const sqlite3_mem_methods *sqlite3MemGetMemsys6(void){
- static const sqlite3_mem_methods memsys6Methods = {
- memsys6Malloc,
- memsys6Free,
- memsys6Realloc,
- memsys6Size,
- memsys6Roundup,
- memsys6Init,
- memsys6Shutdown,
- 0
- };
- return &memsys6Methods;
-}
-
-#endif
-
-/************** End of mem6.c ************************************************/