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.7 2008/07/28 19:34:53 drh 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 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;

   114 

   115 /*

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

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

   118 */

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

   120   int next, prev;

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

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

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

   124 

   125   next = MEM6LINK(i)->next;

   126   prev = MEM6LINK(i)->prev;

   127   if( prev<0 ){

   128     pChunk->aiFreelist[iLogsize] = next;

   129   }else{

   130     MEM6LINK(prev)->next = next;

   131   }

   132   if( next>=0 ){

   133     MEM6LINK(next)->prev = prev;

   134   }

   135 }

   136 

   137 /*

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

   139 ** free list.

   140 */

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

   142   int x;

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

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

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

   146 

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

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

   149   if( x>=0 ){

   150     assert( x<pChunk->nBlock );

   151     MEM6LINK(x)->prev = i;

   152   }

   153   pChunk->aiFreelist[iLogsize] = i;

   154 }

   155 

   156 

   157 /*

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

   159 ** entry and return its index. 

   160 */

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

   162   int i;

   163   int iFirst;

   164 

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

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

   167   assert( iFirst>=0 );

   168   memsys6Unlink(pChunk, iFirst, iLogsize);

   169   return iFirst;

   170 }

   171 

   172 static int roundupLog2(int n){

   173   static const char LogTable256[256] = {

   174     0,                                                    /* 1 */

   175     1,                                                    /* 2 */

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

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

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

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

   180     6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6, 6,

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

   182     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,

   183     7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7, 7,

   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,       /* 65..128 */

   186     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,

   187     8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8,

   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,       /* 129..256 */

   194   };

   195 

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

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

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

   199 }

   200 

   201 /*

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

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

   204 */

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

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

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

   208 

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

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

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

   212   */

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

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

   215   i = memsys6UnlinkFirst(pChunk, iBin);

   216   while( iBin>iLogsize ){

   217     int newSize;

   218     iBin--;

   219     newSize = 1 << iBin;

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

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

   222   }

   223   pChunk->aCtrl[i] = iLogsize;

   224 

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

   226   pChunk->nCheckedOut++;

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

   228 }

   229 

   230 /*

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

   232 ** and a part of chunk object pChunk.

   233 */

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

   235   u32 size, iLogsize;

   236   int iBlock;             

   237 

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

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

   240   */

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

   242 

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

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

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

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

   247 

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

   249   size = 1<<iLogsize;

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

   251 

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

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

   254 

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

   256   while( iLogsize<mem6.nLogThreshold ){

   257     int iBuddy;

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

   259       iBuddy = iBlock - size;

   260     }else{

   261       iBuddy = iBlock + size;

   262     }

   263     assert( iBuddy>=0 );

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

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

   266     memsys6Unlink(pChunk, iBuddy, iLogsize);

   267     iLogsize++;

   268     if( iBuddy<iBlock ){

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

   270       pChunk->aCtrl[iBlock] = 0;

   271       iBlock = iBuddy;

   272     }else{

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

   274       pChunk->aCtrl[iBuddy] = 0;

   275     }

   276     size *= 2;

   277   }

   278   pChunk->nCheckedOut--;

   279   memsys6Link(pChunk, iBlock, iLogsize);

   280 }

   281 

   282 /*

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

   284 ** to have been allocated from chunk pChunk.

   285 */

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

   287   int iSize = 0;

   288   if( p ){

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

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

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

   292   }

   293   return iSize;

   294 }

   295 

   296 /*

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

   298 */

   299 static int chunkIsEmpty(Mem6Chunk *pChunk){

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

   301 }

   302 

   303 /*

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

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

   306 */

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

   308   int ii;

   309   int iOffset;

   310   Mem6Chunk *pChunk = (Mem6Chunk *)zChunk;

   311 

   312   assert( nChunk>sizeof(Mem6Chunk) );

   313   assert( nMinAlloc>sizeof(Mem6Link) );

   314 

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

   316   pChunk->nAtom = nMinAlloc;

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

   318 

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

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

   321 

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

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

   324   }

   325 

   326   iOffset = 0;

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

   328     int nAlloc = (1<<ii);

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

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

   331       memsys6Link(pChunk, iOffset, ii);

   332       iOffset += nAlloc;

   333     }

   334   }

   335 

   336   return pChunk;

   337 }

   338 

   339 

   340 static void mem6Enter(void){

   341   sqlite3_mutex_enter(mem6.mutex);

   342 }

   343 

   344 static void mem6Leave(void){

   345   sqlite3_mutex_leave(mem6.mutex);

   346 }

   347 

   348 /*

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

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

   351 */

   352 static int nextChunkSize(void){

   353   int iTotal = MIN_CHUNKSIZE;

   354   Mem6Chunk *p;

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

   356     iTotal = iTotal*2;

   357   }

   358   return iTotal;

   359 }

   360 

   361 static void freeChunk(Mem6Chunk *pChunk){

   362   Mem6Chunk **pp = &mem6.pChunk;

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

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

   365   free(pChunk);

   366 }

   367 

   368 static void *memsys6Malloc(int nByte){

   369   Mem6Chunk *pChunk;

   370   void *p = 0;

   371   int nTotal = nByte+8;

   372   int iOffset = 0;

   373 

   374   if( nTotal>mem6.nThreshold ){

   375     p = malloc(nTotal);

   376   }else{

   377     int iLogsize = 0;

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

   379       iLogsize = roundupLog2(nTotal) - LOG2_MINALLOC;

   380     }

   381     mem6Enter();

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

   383       p = chunkMalloc(pChunk, iLogsize);

   384       if( p ){

   385         break;

   386       }

   387     }

   388     if( !p ){

   389       int iSize = nextChunkSize();

   390       p = malloc(iSize);

   391       if( p ){

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

   393         pChunk->pNext = mem6.pChunk;

   394         mem6.pChunk = pChunk;

   395         p = chunkMalloc(pChunk, iLogsize);

   396         assert(p);

   397       }

   398     }

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

   400     mem6Leave();

   401   }

   402 

   403   if( !p ){

   404     return 0;

   405   }

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

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

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

   409 }

   410 

   411 static int memsys6Size(void *pPrior){

   412   if( pPrior==0 ) return 0;

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

   414 }

   415 

   416 static void memsys6Free(void *pPrior){

   417   int iSlot;

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

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

   420   if( iSlot ){

   421     Mem6Chunk *pChunk;

   422     mem6Enter();

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

   424     chunkFree(pChunk, p);

   425     if( chunkIsEmpty(pChunk) ){

   426       freeChunk(pChunk);

   427     }

   428     mem6Leave();

   429   }else{

   430     free(p);

   431   }

   432 }

   433 

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

   435   void *p2;

   436 

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

   438     p2 = p;

   439   }else{

   440     p2 = memsys6Malloc(nByte);

   441     if( p && p2 ){

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

   443       memsys6Free(p);

   444     }

   445   }

   446 

   447   return p2;

   448 }

   449 

   450 static int memsys6Roundup(int n){

   451   if( n>mem6.nThreshold ){

   452     return n;

   453   }else{

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

   455   }

   456 }

   457 

   458 static int memsys6Init(void *pCtx){

   459   u8 bMemstat = sqlite3Config.bMemstat;

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

   461   mem6.pChunk = 0;

   462   mem6.nThreshold = sqlite3Config.nSmall;

   463   if( mem6.nThreshold<=0 ){

   464     mem6.nThreshold = SMALL_MALLOC_DEFAULT_THRESHOLD;

   465   }

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

   467   if( !bMemstat ){

   468     mem6.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);

   469   }

   470   return SQLITE_OK;

   471 }

   472 

   473 static void memsys6Shutdown(void *pCtx){

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

   475 }

   476 

   477 /*

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

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

   480 ** struct populated with the memsys6 methods.

   481 */

   482 const sqlite3_mem_methods *sqlite3MemGetMemsys6(void){

   483   static const sqlite3_mem_methods memsys6Methods = {

   484      memsys6Malloc,

   485      memsys6Free,

   486      memsys6Realloc,

   487      memsys6Size,

   488      memsys6Roundup,

   489      memsys6Init,

   490      memsys6Shutdown,

   491      0

   492   };

   493   return &memsys6Methods;

   494 }

   495 

   496 #endif