1 /*

     2 ** 2007 October 14

     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 ** This file contains the C functions that implement a memory

    13 ** allocation subsystem for use by SQLite. 

    14 **

    15 ** This version of the memory allocation subsystem omits all

    16 ** use of malloc(). The SQLite user supplies a block of memory

    17 ** before calling sqlite3_initialize() from which allocations

    18 ** are made and returned by the xMalloc() and xRealloc() 

    19 ** implementations. Once sqlite3_initialize() has been called,

    20 ** the amount of memory available to SQLite is fixed and cannot

    21 ** be changed.

    22 **

    23 ** This version of the memory allocation subsystem is included

    24 ** in the build only if SQLITE_ENABLE_MEMSYS5 is defined.

    25 **

    26 ** $Id: mem5.c,v 1.14 2008/09/02 17:52:52 danielk1977 Exp $

    27 */

    28 #include "sqliteInt.h"

    29 

    30 /*

    31 ** This version of the memory allocator is used only when 

    32 ** SQLITE_POW2_MEMORY_SIZE is defined.

    33 */

    34 #ifdef SQLITE_ENABLE_MEMSYS5

    35 

    36 /*

    37 ** Log2 of the minimum size of an allocation.  For example, if

    38 ** 4 then all allocations will be rounded up to at least 16 bytes.

    39 ** If 5 then all allocations will be rounded up to at least 32 bytes.

    40 */

    41 #ifndef SQLITE_POW2_LOGMIN

    42 # define SQLITE_POW2_LOGMIN 6

    43 #endif

    44 

    45 /*

    46 ** Log2 of the maximum size of an allocation.

    47 */

    48 #ifndef SQLITE_POW2_LOGMAX

    49 # define SQLITE_POW2_LOGMAX 20

    50 #endif

    51 #define POW2_MAX (((unsigned int)1)<<SQLITE_POW2_LOGMAX)

    52 

    53 /*

    54 ** Number of distinct allocation sizes.

    55 */

    56 #define NSIZE (SQLITE_POW2_LOGMAX - SQLITE_POW2_LOGMIN + 1)

    57 

    58 /*

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

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

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

    62 */

    63 typedef struct Mem5Link Mem5Link;

    64 struct Mem5Link {

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

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

    67 };

    68 

    69 /*

    70 ** Maximum size of any allocation is ((1<<LOGMAX)*mem5.nAtom). Since

    71 ** mem5.nAtom is always at least 8, this is not really a practical

    72 ** limitation.

    73 */

    74 #define LOGMAX 30

    75 

    76 /*

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

    78 */

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

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

    81 

    82 /*

    83 ** All of the static variables used by this module are collected

    84 ** into a single structure named "mem5".  This is to keep the

    85 ** static variables organized and to reduce namespace pollution

    86 ** when this module is combined with other in the amalgamation.

    87 */

    88 static SQLITE_WSD struct Mem5Global {

    89   /*

    90   ** Memory available for allocation

    91   */

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

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

    94   u8 *zPool;

    95   

    96   /*

    97   ** Mutex to control access to the memory allocation subsystem.

    98   */

    99   sqlite3_mutex *mutex;

   100 

   101   /*

   102   ** Performance statistics

   103   */

   104   u64 nAlloc;         /* Total number of calls to malloc */

   105   u64 totalAlloc;     /* Total of all malloc calls - includes internal frag */

   106   u64 totalExcess;    /* Total internal fragmentation */

   107   u32 currentOut;     /* Current checkout, including internal fragmentation */

   108   u32 currentCount;   /* Current number of distinct checkouts */

   109   u32 maxOut;         /* Maximum instantaneous currentOut */

   110   u32 maxCount;       /* Maximum instantaneous currentCount */

   111   u32 maxRequest;     /* Largest allocation (exclusive of internal frag) */

   112   

   113   /*

   114   ** Lists of free blocks of various sizes.

   115   */

   116   int aiFreelist[LOGMAX+1];

   117 

   118   /*

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

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

   121   */

   122   u8 *aCtrl;

   123 

   124 } mem5 = { 19804167 };

   125 

   126 #define mem5 GLOBAL(struct Mem5Global, mem5)

   127 

   128 #define MEM5LINK(idx) ((Mem5Link *)(&mem5.zPool[(idx)*mem5.nAtom]))

   129 

   130 /*

   131 ** Unlink the chunk at mem5.aPool[i] from list it is currently

   132 ** on.  It should be found on mem5.aiFreelist[iLogsize].

   133 */

   134 static void memsys5Unlink(int i, int iLogsize){

   135   int next, prev;

   136   assert( i>=0 && i<mem5.nBlock );

   137   assert( iLogsize>=0 && iLogsize<=LOGMAX );

   138   assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );

   139 

   140   next = MEM5LINK(i)->next;

   141   prev = MEM5LINK(i)->prev;

   142   if( prev<0 ){

   143     mem5.aiFreelist[iLogsize] = next;

   144   }else{

   145     MEM5LINK(prev)->next = next;

   146   }

   147   if( next>=0 ){

   148     MEM5LINK(next)->prev = prev;

   149   }

   150 }

   151 

   152 /*

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

   154 ** free list.

   155 */

   156 static void memsys5Link(int i, int iLogsize){

   157   int x;

   158   assert( sqlite3_mutex_held(mem5.mutex) );

   159   assert( i>=0 && i<mem5.nBlock );

   160   assert( iLogsize>=0 && iLogsize<=LOGMAX );

   161   assert( (mem5.aCtrl[i] & CTRL_LOGSIZE)==iLogsize );

   162 

   163   x = MEM5LINK(i)->next = mem5.aiFreelist[iLogsize];

   164   MEM5LINK(i)->prev = -1;

   165   if( x>=0 ){

   166     assert( x<mem5.nBlock );

   167     MEM5LINK(x)->prev = i;

   168   }

   169   mem5.aiFreelist[iLogsize] = i;

   170 }

   171 

   172 /*

   173 ** If the STATIC_MEM mutex is not already held, obtain it now. The mutex

   174 ** will already be held (obtained by code in malloc.c) if

   175 ** sqlite3GlobalConfig.bMemStat is true.

   176 */

   177 static void memsys5Enter(void){

   178   if( sqlite3GlobalConfig.bMemstat==0 && mem5.mutex==0 ){

   179     mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);

   180   }

   181   sqlite3_mutex_enter(mem5.mutex);

   182 }

   183 static void memsys5Leave(void){

   184   sqlite3_mutex_leave(mem5.mutex);

   185 }

   186 

   187 /*

   188 ** Return the size of an outstanding allocation, in bytes.  The

   189 ** size returned omits the 8-byte header overhead.  This only

   190 ** works for chunks that are currently checked out.

   191 */

   192 static int memsys5Size(void *p){

   193   int iSize = 0;

   194   if( p ){

   195     int i = ((u8 *)p-mem5.zPool)/mem5.nAtom;

   196     assert( i>=0 && i<mem5.nBlock );

   197     iSize = mem5.nAtom * (1 << (mem5.aCtrl[i]&CTRL_LOGSIZE));

   198   }

   199   return iSize;

   200 }

   201 

   202 /*

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

   204 ** entry and return its index. 

   205 */

   206 static int memsys5UnlinkFirst(int iLogsize){

   207   int i;

   208   int iFirst;

   209 

   210   assert( iLogsize>=0 && iLogsize<=LOGMAX );

   211   i = iFirst = mem5.aiFreelist[iLogsize];

   212   assert( iFirst>=0 );

   213   while( i>0 ){

   214     if( i<iFirst ) iFirst = i;

   215     i = MEM5LINK(i)->next;

   216   }

   217   memsys5Unlink(iFirst, iLogsize);

   218   return iFirst;

   219 }

   220 

   221 /*

   222 ** Return a block of memory of at least nBytes in size.

   223 ** Return NULL if unable.

   224 */

   225 static void *memsys5MallocUnsafe(int nByte){

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

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

   228   int iFullSz;     /* Size of allocation rounded up to power of 2 */

   229   int iLogsize;    /* Log2 of iFullSz/POW2_MIN */

   230 

   231   /* Keep track of the maximum allocation request.  Even unfulfilled

   232   ** requests are counted */

   233   if( nByte>mem5.maxRequest ){

   234     mem5.maxRequest = nByte;

   235   }

   236 

   237   /* Round nByte up to the next valid power of two */

   238   if( nByte>POW2_MAX ) return 0;

   239   for(iFullSz=mem5.nAtom, iLogsize=0; iFullSz<nByte; iFullSz *= 2, iLogsize++){}

   240 

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

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

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

   244   */

   245   for(iBin=iLogsize; mem5.aiFreelist[iBin]<0 && iBin<=LOGMAX; iBin++){}

   246   if( iBin>LOGMAX ) return 0;

   247   i = memsys5UnlinkFirst(iBin);

   248   while( iBin>iLogsize ){

   249     int newSize;

   250 

   251     iBin--;

   252     newSize = 1 << iBin;

   253     mem5.aCtrl[i+newSize] = CTRL_FREE | iBin;

   254     memsys5Link(i+newSize, iBin);

   255   }

   256   mem5.aCtrl[i] = iLogsize;

   257 

   258   /* Update allocator performance statistics. */

   259   mem5.nAlloc++;

   260   mem5.totalAlloc += iFullSz;

   261   mem5.totalExcess += iFullSz - nByte;

   262   mem5.currentCount++;

   263   mem5.currentOut += iFullSz;

   264   if( mem5.maxCount<mem5.currentCount ) mem5.maxCount = mem5.currentCount;

   265   if( mem5.maxOut<mem5.currentOut ) mem5.maxOut = mem5.currentOut;

   266 

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

   268   return (void*)&mem5.zPool[i*mem5.nAtom];

   269 }

   270 

   271 /*

   272 ** Free an outstanding memory allocation.

   273 */

   274 static void memsys5FreeUnsafe(void *pOld){

   275   u32 size, iLogsize;

   276   int iBlock;             

   277 

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

   279   ** the array of mem5.nAtom byte blocks pointed to by mem5.zPool.

   280   */

   281   iBlock = ((u8 *)pOld-mem5.zPool)/mem5.nAtom;

   282 

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

   284   assert( iBlock>=0 && iBlock<mem5.nBlock );

   285   assert( ((u8 *)pOld-mem5.zPool)%mem5.nAtom==0 );

   286   assert( (mem5.aCtrl[iBlock] & CTRL_FREE)==0 );

   287 

   288   iLogsize = mem5.aCtrl[iBlock] & CTRL_LOGSIZE;

   289   size = 1<<iLogsize;

   290   assert( iBlock+size-1<mem5.nBlock );

   291 

   292   mem5.aCtrl[iBlock] |= CTRL_FREE;

   293   mem5.aCtrl[iBlock+size-1] |= CTRL_FREE;

   294   assert( mem5.currentCount>0 );

   295   assert( mem5.currentOut>=0 );

   296   mem5.currentCount--;

   297   mem5.currentOut -= size*mem5.nAtom;

   298   assert( mem5.currentOut>0 || mem5.currentCount==0 );

   299   assert( mem5.currentCount>0 || mem5.currentOut==0 );

   300 

   301   mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;

   302   while( iLogsize<LOGMAX ){

   303     int iBuddy;

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

   305       iBuddy = iBlock - size;

   306     }else{

   307       iBuddy = iBlock + size;

   308     }

   309     assert( iBuddy>=0 );

   310     if( (iBuddy+(1<<iLogsize))>mem5.nBlock ) break;

   311     if( mem5.aCtrl[iBuddy]!=(CTRL_FREE | iLogsize) ) break;

   312     memsys5Unlink(iBuddy, iLogsize);

   313     iLogsize++;

   314     if( iBuddy<iBlock ){

   315       mem5.aCtrl[iBuddy] = CTRL_FREE | iLogsize;

   316       mem5.aCtrl[iBlock] = 0;

   317       iBlock = iBuddy;

   318     }else{

   319       mem5.aCtrl[iBlock] = CTRL_FREE | iLogsize;

   320       mem5.aCtrl[iBuddy] = 0;

   321     }

   322     size *= 2;

   323   }

   324   memsys5Link(iBlock, iLogsize);

   325 }

   326 

   327 /*

   328 ** Allocate nBytes of memory

   329 */

   330 static void *memsys5Malloc(int nBytes){

   331   sqlite3_int64 *p = 0;

   332   if( nBytes>0 ){

   333     memsys5Enter();

   334     p = memsys5MallocUnsafe(nBytes);

   335     memsys5Leave();

   336   }

   337   return (void*)p; 

   338 }

   339 

   340 /*

   341 ** Free memory.

   342 */

   343 static void memsys5Free(void *pPrior){

   344   if( pPrior==0 ){

   345 assert(0);

   346     return;

   347   }

   348   memsys5Enter();

   349   memsys5FreeUnsafe(pPrior);

   350   memsys5Leave();  

   351 }

   352 

   353 /*

   354 ** Change the size of an existing memory allocation

   355 */

   356 static void *memsys5Realloc(void *pPrior, int nBytes){

   357   int nOld;

   358   void *p;

   359   if( pPrior==0 ){

   360     return memsys5Malloc(nBytes);

   361   }

   362   if( nBytes<=0 ){

   363     memsys5Free(pPrior);

   364     return 0;

   365   }

   366   nOld = memsys5Size(pPrior);

   367   if( nBytes<=nOld ){

   368     return pPrior;

   369   }

   370   memsys5Enter();

   371   p = memsys5MallocUnsafe(nBytes);

   372   if( p ){

   373     memcpy(p, pPrior, nOld);

   374     memsys5FreeUnsafe(pPrior);

   375   }

   376   memsys5Leave();

   377   return p;

   378 }

   379 

   380 /*

   381 ** Round up a request size to the next valid allocation size.

   382 */

   383 static int memsys5Roundup(int n){

   384   int iFullSz;

   385   for(iFullSz=mem5.nAtom; iFullSz<n; iFullSz *= 2);

   386   return iFullSz;

   387 }

   388 

   389 static int memsys5Log(int iValue){

   390   int iLog;

   391   for(iLog=0; (1<<iLog)<iValue; iLog++);

   392   return iLog;

   393 }

   394 

   395 /*

   396 ** Initialize this module.

   397 */

   398 static int memsys5Init(void *NotUsed){

   399   int ii;

   400   int nByte = sqlite3GlobalConfig.nHeap;

   401   u8 *zByte = (u8 *)sqlite3GlobalConfig.pHeap;

   402   int nMinLog;                 /* Log of minimum allocation size in bytes*/

   403   int iOffset;

   404 

   405   if( !zByte ){

   406     return SQLITE_ERROR;

   407   }

   408 

   409   nMinLog = memsys5Log(sqlite3GlobalConfig.mnReq);

   410   mem5.nAtom = (1<<nMinLog);

   411   while( sizeof(Mem5Link)>mem5.nAtom ){

   412     mem5.nAtom = mem5.nAtom << 1;

   413   }

   414 

   415   mem5.nBlock = (nByte / (mem5.nAtom+sizeof(u8)));

   416   mem5.zPool = zByte;

   417   mem5.aCtrl = (u8 *)&mem5.zPool[mem5.nBlock*mem5.nAtom];

   418 

   419   for(ii=0; ii<=LOGMAX; ii++){

   420     mem5.aiFreelist[ii] = -1;

   421   }

   422 

   423   iOffset = 0;

   424   for(ii=LOGMAX; ii>=0; ii--){

   425     int nAlloc = (1<<ii);

   426     if( (iOffset+nAlloc)<=mem5.nBlock ){

   427       mem5.aCtrl[iOffset] = ii | CTRL_FREE;

   428       memsys5Link(iOffset, ii);

   429       iOffset += nAlloc;

   430     }

   431     assert((iOffset+nAlloc)>mem5.nBlock);

   432   }

   433 

   434   return SQLITE_OK;

   435 }

   436 

   437 /*

   438 ** Deinitialize this module.

   439 */

   440 static void memsys5Shutdown(void *NotUsed){

   441   return;

   442 }

   443 

   444 /*

   445 ** Open the file indicated and write a log of all unfreed memory 

   446 ** allocations into that log.

   447 */

   448 void sqlite3Memsys5Dump(const char *zFilename){

   449 #ifdef SQLITE_DEBUG

   450   FILE *out;

   451   int i, j, n;

   452   int nMinLog;

   453 

   454   if( zFilename==0 || zFilename[0]==0 ){

   455     out = stdout;

   456   }else{

   457     out = fopen(zFilename, "w");

   458     if( out==0 ){

   459       fprintf(stderr, "** Unable to output memory debug output log: %s **\n",

   460                       zFilename);

   461       return;

   462     }

   463   }

   464   memsys5Enter();

   465   nMinLog = memsys5Log(mem5.nAtom);

   466   for(i=0; i<=LOGMAX && i+nMinLog<32; i++){

   467     for(n=0, j=mem5.aiFreelist[i]; j>=0; j = MEM5LINK(j)->next, n++){}

   468     fprintf(out, "freelist items of size %d: %d\n", mem5.nAtom << i, n);

   469   }

   470   fprintf(out, "mem5.nAlloc       = %llu\n", mem5.nAlloc);

   471   fprintf(out, "mem5.totalAlloc   = %llu\n", mem5.totalAlloc);

   472   fprintf(out, "mem5.totalExcess  = %llu\n", mem5.totalExcess);

   473   fprintf(out, "mem5.currentOut   = %u\n", mem5.currentOut);

   474   fprintf(out, "mem5.currentCount = %u\n", mem5.currentCount);

   475   fprintf(out, "mem5.maxOut       = %u\n", mem5.maxOut);

   476   fprintf(out, "mem5.maxCount     = %u\n", mem5.maxCount);

   477   fprintf(out, "mem5.maxRequest   = %u\n", mem5.maxRequest);

   478   memsys5Leave();

   479   if( out==stdout ){

   480     fflush(stdout);

   481   }else{

   482     fclose(out);

   483   }

   484 #endif

   485 }

   486 

   487 /*

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

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

   490 ** struct populated with the memsys5 methods.

   491 */

   492 const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){

   493   static const sqlite3_mem_methods memsys5Methods = {

   494      memsys5Malloc,

   495      memsys5Free,

   496      memsys5Realloc,

   497      memsys5Size,

   498      memsys5Roundup,

   499      memsys5Init,

   500      memsys5Shutdown,

   501      0

   502   };

   503   return &memsys5Methods;

   504 }

   505 

   506 #endif /* SQLITE_ENABLE_MEMSYS5 */