1 /*

     2 ** 2008 July 24

     3 **

     4 ** The author disclaims copyright to this source code.  In place of

     5 ** a legal notice, here is a blessing:

     6 **

     7 **    May you do good and not evil.

     8 **    May you find forgiveness for yourself and forgive others.

     9 **    May you share freely, never taking more than you give.

    10 **

    11 *************************************************************************

    12 **

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

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

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

    16 **

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

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

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

    20 **

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

    22 ** default system.

    23 **

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

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

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

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

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

    29 **

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

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

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

    33 ** significant real-time slowdown.

    34 **

    35 ** $Id: mem6.c,v 1.10 2008/09/02 17:52:52 danielk1977 Exp $

    36 */

    37 

    38 #ifdef SQLITE_ENABLE_MEMSYS6

    39 

    40 #include "sqliteInt.h"

    41 

    42 /*

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

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

    45 ** limitation

    46 */

    47 #define LOGMAX 30

    48 

    49 /*

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

    51 */

    52 #define SMALL_MALLOC_DEFAULT_THRESHOLD 256

    53 

    54 /*

    55 ** Minimum size for a memory chunk.

    56 */

    57 #define MIN_CHUNKSIZE (1<<16)

    58 

    59 #define LOG2_MINALLOC 4

    60 

    61 

    62 typedef struct Mem6Chunk Mem6Chunk;

    63 typedef struct Mem6Link Mem6Link;

    64 

    65 /*

    66 ** A minimum allocation is an instance of the following structure.

    67 ** Larger allocations are an array of these structures where the

    68 ** size of the array is a power of 2.

    69 */

    70 struct Mem6Link {

    71   int next;       /* Index of next free chunk */

    72   int prev;       /* Index of previous free chunk */

    73 };

    74 

    75 /*

    76 ** Masks used for mem5.aCtrl[] elements.

    77 */

    78 #define CTRL_LOGSIZE  0x1f    /* Log2 Size of this block relative to POW2_MIN */

    79 #define CTRL_FREE     0x20    /* True if not checked out */

    80 

    81 struct Mem6Chunk {

    82   Mem6Chunk *pNext;

    83 

    84   /*

    85   ** Lists of free blocks of various sizes.

    86   */

    87   int aiFreelist[LOGMAX+1];

    88 

    89   int nCheckedOut; /* Number of currently outstanding allocations */

    90 

    91   /*

    92   ** Space for tracking which blocks are checked out and the size

    93   ** of each block. One byte per block.

    94   */

    95   u8 *aCtrl;

    96 

    97   /*

    98   ** Memory available for allocation

    99   */

   100   int nAtom;       /* Smallest possible allocation in bytes */

   101   int nBlock;      /* Number of nAtom sized blocks in zPool */

   102   u8 *zPool;       /* Pointer to memory chunk from which allocations are made */

   103 };

   104 

   105 #define MEM6LINK(idx) ((Mem6Link *)(&pChunk->zPool[(idx)*pChunk->nAtom]))

   106 

   107 static SQLITE_WSD struct Mem6Global {

   108   int nMinAlloc;                  /* Minimum allowed allocation size */

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

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

   111   sqlite3_mutex *mutex;

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

   113 } mem6 = { 48642791 };

   114 

   115 #define mem6 GLOBAL(struct Mem6Global, mem6)

   116 

   117 /*

   118 ** Unlink the chunk at pChunk->aPool[i] from list it is currently

   119 ** on.  It should be found on pChunk->aiFreelist[iLogsize].

   120 */

   121 static void memsys6Unlink(Mem6Chunk *pChunk, int i, int iLogsize){

   122   int next, prev;

   123   assert( i>=0 && i<pChunk->nBlock );

   124   assert( iLogsize>=0 && iLogsize<=mem6.nLogThreshold );

   125   assert( (pChunk->aCtrl[i] & CTRL_LOGSIZE)==iLogsize );

   126 

   127   next = MEM6LINK(i)->next;

   128   prev = MEM6LINK(i)->prev;

   129   if( prev<0 ){

   130     pChunk->aiFreelist[iLogsize] = next;

   131   }else{

   132     MEM6LINK(prev)->next = next;

   133   }

   134   if( next>=0 ){

   135     MEM6LINK(next)->prev = prev;

   136   }

   137 }

   138 

   139 /*

   140 ** Link the chunk at mem5.aPool[i] so that is on the iLogsize

   141 ** free list.

   142 */

   143 static void memsys6Link(Mem6Chunk *pChunk, int i, int iLogsize){

   144   int x;

   145   assert( i>=0 && i<pChunk->nBlock );

   146   assert( iLogsize>=0 && iLogsize<=mem6.nLogThreshold );

   147   assert( (pChunk->aCtrl[i] & CTRL_LOGSIZE)==iLogsize );

   148 

   149   x = MEM6LINK(i)->next = pChunk->aiFreelist[iLogsize];

   150   MEM6LINK(i)->prev = -1;

   151   if( x>=0 ){

   152     assert( x<pChunk->nBlock );

   153     MEM6LINK(x)->prev = i;

   154   }

   155   pChunk->aiFreelist[iLogsize] = i;

   156 }

   157 

   158 

   159 /*

   160 ** Find the first entry on the freelist iLogsize.  Unlink that

   161 ** entry and return its index. 

   162 */

   163 static int memsys6UnlinkFirst(Mem6Chunk *pChunk, int iLogsize){

   164   int i;

   165   int iFirst;

   166 

   167   assert( iLogsize>=0 && iLogsize<=mem6.nLogThreshold );

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

   169   assert( iFirst>=0 );

   170   memsys6Unlink(pChunk, iFirst, iLogsize);

   171   return iFirst;

   172 }

   173 

   174 static int roundupLog2(int n){

   175   static const char LogTable256[256] = {

   176     0,                                                    /* 1 */

   177     1,                                                    /* 2 */

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

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

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

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

   182     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,

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

   184     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,

   185     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,

   186     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,

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

   188     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,

   189     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,

   190     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,

   191     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,

   192     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,

   193     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,

   194     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,

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

   196   };

   197 

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

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

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

   201 }

   202 

   203 /*

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

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

   206 */

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

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

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

   210 

   211   /* Make sure mem5.aiFreelist[iLogsize] contains at least one free

   212   ** block.  If not, then split a block of the next larger power of

   213   ** two in order to create a new free block of size iLogsize.

   214   */

   215   for(iBin=iLogsize; pChunk->aiFreelist[iBin]<0 && iBin<=mem6.nLogThreshold; iBin++){}

   216   if( iBin>mem6.nLogThreshold ) return 0;

   217   i = memsys6UnlinkFirst(pChunk, iBin);

   218   while( iBin>iLogsize ){

   219     int newSize;

   220     iBin--;

   221     newSize = 1 << iBin;

   222     pChunk->aCtrl[i+newSize] = CTRL_FREE | iBin;

   223     memsys6Link(pChunk, i+newSize, iBin);

   224   }

   225   pChunk->aCtrl[i] = iLogsize;

   226 

   227   /* Return a pointer to the allocated memory. */

   228   pChunk->nCheckedOut++;

   229   return (void*)&pChunk->zPool[i*pChunk->nAtom];

   230 }

   231 

   232 /*

   233 ** Free the allocation pointed to by p, which is guaranteed to be non-zero

   234 ** and a part of chunk object pChunk.

   235 */

   236 static void chunkFree(Mem6Chunk *pChunk, void *pOld){

   237   u32 size, iLogsize;

   238   int iBlock;             

   239 

   240   /* Set iBlock to the index of the block pointed to by pOld in 

   241   ** the array of pChunk->nAtom byte blocks pointed to by pChunk->zPool.

   242   */

   243   iBlock = ((u8 *)pOld-pChunk->zPool)/pChunk->nAtom;

   244 

   245   /* Check that the pointer pOld points to a valid, non-free block. */

   246   assert( iBlock>=0 && iBlock<pChunk->nBlock );

   247   assert( ((u8 *)pOld-pChunk->zPool)%pChunk->nAtom==0 );

   248   assert( (pChunk->aCtrl[iBlock] & CTRL_FREE)==0 );

   249 

   250   iLogsize = pChunk->aCtrl[iBlock] & CTRL_LOGSIZE;

   251   size = 1<<iLogsize;

   252   assert( iBlock+size-1<pChunk->nBlock );

   253 

   254   pChunk->aCtrl[iBlock] |= CTRL_FREE;

   255   pChunk->aCtrl[iBlock+size-1] |= CTRL_FREE;

   256 

   257   pChunk->aCtrl[iBlock] = CTRL_FREE | iLogsize;

   258   while( iLogsize<mem6.nLogThreshold ){

   259     int iBuddy;

   260     if( (iBlock>>iLogsize) & 1 ){

   261       iBuddy = iBlock - size;

   262     }else{

   263       iBuddy = iBlock + size;

   264     }

   265     assert( iBuddy>=0 );

   266     if( (iBuddy+(1<<iLogsize))>pChunk->nBlock ) break;

   267     if( pChunk->aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;

   268     memsys6Unlink(pChunk, iBuddy, iLogsize);

   269     iLogsize++;

   270     if( iBuddy<iBlock ){

   271       pChunk->aCtrl[iBuddy] = CTRL_FREE | iLogsize;

   272       pChunk->aCtrl[iBlock] = 0;

   273       iBlock = iBuddy;

   274     }else{

   275       pChunk->aCtrl[iBlock] = CTRL_FREE | iLogsize;

   276       pChunk->aCtrl[iBuddy] = 0;

   277     }

   278     size *= 2;

   279   }

   280   pChunk->nCheckedOut--;

   281   memsys6Link(pChunk, iBlock, iLogsize);

   282 }

   283 

   284 /*

   285 ** Return the actual size of the block pointed to by p, which is guaranteed

   286 ** to have been allocated from chunk pChunk.

   287 */

   288 static int chunkSize(Mem6Chunk *pChunk, void *p){

   289   int iSize = 0;

   290   if( p ){

   291     int i = ((u8 *)p-pChunk->zPool)/pChunk->nAtom;

   292     assert( i>=0 && i<pChunk->nBlock );

   293     iSize = pChunk->nAtom * (1 << (pChunk->aCtrl[i]&CTRL_LOGSIZE));

   294   }

   295   return iSize;

   296 }

   297 

   298 /*

   299 ** Return true if there are currently no outstanding allocations.

   300 */

   301 static int chunkIsEmpty(Mem6Chunk *pChunk){

   302   return (pChunk->nCheckedOut==0);

   303 }

   304 

   305 /*

   306 ** Initialize the buffer zChunk, which is nChunk bytes in size, as

   307 ** an Mem6Chunk object. Return a copy of the zChunk pointer.

   308 */

   309 static Mem6Chunk *chunkInit(u8 *zChunk, int nChunk, int nMinAlloc){

   310   int ii;

   311   int iOffset;

   312   Mem6Chunk *pChunk = (Mem6Chunk *)zChunk;

   313 

   314   assert( nChunk>sizeof(Mem6Chunk) );

   315   assert( nMinAlloc>sizeof(Mem6Link) );

   316 

   317   memset(pChunk, 0, sizeof(Mem6Chunk));

   318   pChunk->nAtom = nMinAlloc;

   319   pChunk->nBlock = ((nChunk-sizeof(Mem6Chunk)) / (pChunk->nAtom+sizeof(u8)));

   320 

   321   pChunk->zPool = (u8 *)&pChunk[1];

   322   pChunk->aCtrl = &pChunk->zPool[pChunk->nBlock*pChunk->nAtom];

   323 

   324   for(ii=0; ii<=mem6.nLogThreshold; ii++){

   325     pChunk->aiFreelist[ii] = -1;

   326   }

   327 

   328   iOffset = 0;

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

   330     int nAlloc = (1<<ii);

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

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

   333       memsys6Link(pChunk, iOffset, ii);

   334       iOffset += nAlloc;

   335     }

   336   }

   337 

   338   return pChunk;

   339 }

   340 

   341 

   342 static void mem6Enter(void){

   343   sqlite3_mutex_enter(mem6.mutex);

   344 }

   345 

   346 static void mem6Leave(void){

   347   sqlite3_mutex_leave(mem6.mutex);

   348 }

   349 

   350 /*

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

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

   353 */

   354 static int nextChunkSize(void){

   355   int iTotal = MIN_CHUNKSIZE;

   356   Mem6Chunk *p;

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

   358     iTotal = iTotal*2;

   359   }

   360   return iTotal;

   361 }

   362 

   363 static void freeChunk(Mem6Chunk *pChunk){

   364   Mem6Chunk **pp = &mem6.pChunk;

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

   366   *pp = (*pp)->pNext;

   367   free(pChunk);

   368 }

   369 

   370 static void *memsys6Malloc(int nByte){

   371   Mem6Chunk *pChunk;

   372   void *p = 0;

   373   int nTotal = nByte+8;

   374   int iOffset = 0;

   375 

   376   if( nTotal>mem6.nThreshold ){

   377     p = malloc(nTotal);

   378   }else{

   379     int iLogsize = 0;

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

   381       iLogsize = roundupLog2(nTotal) - LOG2_MINALLOC;

   382     }

   383     mem6Enter();

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

   385       p = chunkMalloc(pChunk, iLogsize);

   386       if( p ){

   387         break;

   388       }

   389     }

   390     if( !p ){

   391       int iSize = nextChunkSize();

   392       p = malloc(iSize);

   393       if( p ){

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

   395         pChunk->pNext = mem6.pChunk;

   396         mem6.pChunk = pChunk;

   397         p = chunkMalloc(pChunk, iLogsize);

   398         assert(p);

   399       }

   400     }

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

   402     mem6Leave();

   403   }

   404 

   405   if( !p ){

   406     return 0;

   407   }

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

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

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

   411 }

   412 

   413 static int memsys6Size(void *pPrior){

   414   if( pPrior==0 ) return 0;

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

   416 }

   417 

   418 static void memsys6Free(void *pPrior){

   419   int iSlot;

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

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

   422   if( iSlot ){

   423     Mem6Chunk *pChunk;

   424     mem6Enter();

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

   426     chunkFree(pChunk, p);

   427     if( chunkIsEmpty(pChunk) ){

   428       freeChunk(pChunk);

   429     }

   430     mem6Leave();

   431   }else{

   432     free(p);

   433   }

   434 }

   435 

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

   437   void *p2;

   438 

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

   440     p2 = p;

   441   }else{

   442     p2 = memsys6Malloc(nByte);

   443     if( p && p2 ){

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

   445       memsys6Free(p);

   446     }

   447   }

   448 

   449   return p2;

   450 }

   451 

   452 static int memsys6Roundup(int n){

   453   if( n>mem6.nThreshold ){

   454     return n;

   455   }else{

   456     return (1<<roundupLog2(n));

   457   }

   458 }

   459 

   460 static int memsys6Init(void *pCtx){

   461   u8 bMemstat = sqlite3GlobalConfig.bMemstat;

   462   mem6.nMinAlloc = (1 << LOG2_MINALLOC);

   463   mem6.pChunk = 0;

   464   mem6.nThreshold = sqlite3GlobalConfig.nSmall;

   465   if( mem6.nThreshold<=0 ){

   466     mem6.nThreshold = SMALL_MALLOC_DEFAULT_THRESHOLD;

   467   }

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

   469   if( !bMemstat ){

   470     mem6.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);

   471   }

   472   return SQLITE_OK;

   473 }

   474 

   475 static void memsys6Shutdown(void *pCtx){

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

   477 }

   478 

   479 /*

   480 ** This routine is the only routine in this file with external 

   481 ** linkage. It returns a pointer to a static sqlite3_mem_methods

   482 ** struct populated with the memsys6 methods.

   483 */

   484 const sqlite3_mem_methods *sqlite3MemGetMemsys6(void){

   485   static const sqlite3_mem_methods memsys6Methods = {

   486      memsys6Malloc,

   487      memsys6Free,

   488      memsys6Realloc,

   489      memsys6Size,

   490      memsys6Roundup,

   491      memsys6Init,

   492      memsys6Shutdown,

   493      0

   494   };

   495   return &memsys6Methods;

   496 }

   497 

   498 #endif