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.11 2008/07/16 12:25:32 drh 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 struct {

    89   /*

    90   ** The alarm callback and its arguments.  The mem5.mutex lock will

    91   ** be held while the callback is running.  Recursive calls into

    92   ** the memory subsystem are allowed, but no new callbacks will be

    93   ** issued.  The alarmBusy variable is set to prevent recursive

    94   ** callbacks.

    95   */

    96   sqlite3_int64 alarmThreshold;

    97   void (*alarmCallback)(void*, sqlite3_int64,int);

    98   void *alarmArg;

    99   int alarmBusy;

   100   

   101   /*

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

   103   */

   104   sqlite3_mutex *mutex;

   105 

   106   /*

   107   ** Performance statistics

   108   */

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

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

   111   u64 totalExcess;    /* Total internal fragmentation */

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

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

   114   u32 maxOut;         /* Maximum instantaneous currentOut */

   115   u32 maxCount;       /* Maximum instantaneous currentCount */

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

   117   

   118   /*

   119   ** Lists of free blocks of various sizes.

   120   */

   121   int aiFreelist[LOGMAX+1];

   122 

   123   /*

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

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

   126   */

   127   u8 *aCtrl;

   128 

   129   /*

   130   ** Memory available for allocation

   131   */

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

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

   134   u8 *zPool;

   135 } mem5;

   136 

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

   138 

   139 /*

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

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

   142 */

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

   144   int next, prev;

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

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

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

   148 

   149   next = MEM5LINK(i)->next;

   150   prev = MEM5LINK(i)->prev;

   151   if( prev<0 ){

   152     mem5.aiFreelist[iLogsize] = next;

   153   }else{

   154     MEM5LINK(prev)->next = next;

   155   }

   156   if( next>=0 ){

   157     MEM5LINK(next)->prev = prev;

   158   }

   159 }

   160 

   161 /*

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

   163 ** free list.

   164 */

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

   166   int x;

   167   assert( sqlite3_mutex_held(mem5.mutex) );

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

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

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

   171 

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

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

   174   if( x>=0 ){

   175     assert( x<mem5.nBlock );

   176     MEM5LINK(x)->prev = i;

   177   }

   178   mem5.aiFreelist[iLogsize] = i;

   179 }

   180 

   181 /*

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

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

   184 ** sqlite3Config.bMemStat is true.

   185 */

   186 static void memsys5Enter(void){

   187   if( sqlite3Config.bMemstat==0 && mem5.mutex==0 ){

   188     mem5.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);

   189   }

   190   sqlite3_mutex_enter(mem5.mutex);

   191 }

   192 static void memsys5Leave(void){

   193   sqlite3_mutex_leave(mem5.mutex);

   194 }

   195 

   196 /*

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

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

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

   200 */

   201 static int memsys5Size(void *p){

   202   int iSize = 0;

   203   if( p ){

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

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

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

   207   }

   208   return iSize;

   209 }

   210 

   211 /*

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

   213 ** entry and return its index. 

   214 */

   215 static int memsys5UnlinkFirst(int iLogsize){

   216   int i;

   217   int iFirst;

   218 

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

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

   221   assert( iFirst>=0 );

   222   while( i>0 ){

   223     if( i<iFirst ) iFirst = i;

   224     i = MEM5LINK(i)->next;

   225   }

   226   memsys5Unlink(iFirst, iLogsize);

   227   return iFirst;

   228 }

   229 

   230 /*

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

   232 ** Return NULL if unable.

   233 */

   234 static void *memsys5MallocUnsafe(int nByte){

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

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

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

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

   239 

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

   241   ** requests are counted */

   242   if( nByte>mem5.maxRequest ){

   243     mem5.maxRequest = nByte;

   244   }

   245 

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

   247   if( nByte>POW2_MAX ) return 0;

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

   249 

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

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

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

   253   */

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

   255   if( iBin>LOGMAX ) return 0;

   256   i = memsys5UnlinkFirst(iBin);

   257   while( iBin>iLogsize ){

   258     int newSize;

   259 

   260     iBin--;

   261     newSize = 1 << iBin;

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

   263     memsys5Link(i+newSize, iBin);

   264   }

   265   mem5.aCtrl[i] = iLogsize;

   266 

   267   /* Update allocator performance statistics. */

   268   mem5.nAlloc++;

   269   mem5.totalAlloc += iFullSz;

   270   mem5.totalExcess += iFullSz - nByte;

   271   mem5.currentCount++;

   272   mem5.currentOut += iFullSz;

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

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

   275 

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

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

   278 }

   279 

   280 /*

   281 ** Free an outstanding memory allocation.

   282 */

   283 static void memsys5FreeUnsafe(void *pOld){

   284   u32 size, iLogsize;

   285   int iBlock;             

   286 

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

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

   289   */

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

   291 

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

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

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

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

   296 

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

   298   size = 1<<iLogsize;

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

   300 

   301   mem5.aCtrl[iBlock] |= CTRL_FREE;

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

   303   assert( mem5.currentCount>0 );

   304   assert( mem5.currentOut>=0 );

   305   mem5.currentCount--;

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

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

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

   309 

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

   311   while( iLogsize<LOGMAX ){

   312     int iBuddy;

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

   314       iBuddy = iBlock - size;

   315     }else{

   316       iBuddy = iBlock + size;

   317     }

   318     assert( iBuddy>=0 );

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

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

   321     memsys5Unlink(iBuddy, iLogsize);

   322     iLogsize++;

   323     if( iBuddy<iBlock ){

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

   325       mem5.aCtrl[iBlock] = 0;

   326       iBlock = iBuddy;

   327     }else{

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

   329       mem5.aCtrl[iBuddy] = 0;

   330     }

   331     size *= 2;

   332   }

   333   memsys5Link(iBlock, iLogsize);

   334 }

   335 

   336 /*

   337 ** Allocate nBytes of memory

   338 */

   339 static void *memsys5Malloc(int nBytes){

   340   sqlite3_int64 *p = 0;

   341   if( nBytes>0 ){

   342     memsys5Enter();

   343     p = memsys5MallocUnsafe(nBytes);

   344     memsys5Leave();

   345   }

   346   return (void*)p; 

   347 }

   348 

   349 /*

   350 ** Free memory.

   351 */

   352 static void memsys5Free(void *pPrior){

   353   if( pPrior==0 ){

   354 assert(0);

   355     return;

   356   }

   357   memsys5Enter();

   358   memsys5FreeUnsafe(pPrior);

   359   memsys5Leave();  

   360 }

   361 

   362 /*

   363 ** Change the size of an existing memory allocation

   364 */

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

   366   int nOld;

   367   void *p;

   368   if( pPrior==0 ){

   369     return memsys5Malloc(nBytes);

   370   }

   371   if( nBytes<=0 ){

   372     memsys5Free(pPrior);

   373     return 0;

   374   }

   375   nOld = memsys5Size(pPrior);

   376   if( nBytes<=nOld ){

   377     return pPrior;

   378   }

   379   memsys5Enter();

   380   p = memsys5MallocUnsafe(nBytes);

   381   if( p ){

   382     memcpy(p, pPrior, nOld);

   383     memsys5FreeUnsafe(pPrior);

   384   }

   385   memsys5Leave();

   386   return p;

   387 }

   388 

   389 /*

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

   391 */

   392 static int memsys5Roundup(int n){

   393   int iFullSz;

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

   395   return iFullSz;

   396 }

   397 

   398 static int memsys5Log(int iValue){

   399   int iLog;

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

   401   return iLog;

   402 }

   403 

   404 /*

   405 ** Initialize this module.

   406 */

   407 static int memsys5Init(void *NotUsed){

   408   int ii;

   409   int nByte = sqlite3Config.nHeap;

   410   u8 *zByte = (u8 *)sqlite3Config.pHeap;

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

   412   int iOffset;

   413 

   414   if( !zByte ){

   415     return SQLITE_ERROR;

   416   }

   417 

   418   nMinLog = memsys5Log(sqlite3Config.mnReq);

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

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

   421     mem5.nAtom = mem5.nAtom << 1;

   422   }

   423 

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

   425   mem5.zPool = zByte;

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

   427 

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

   429     mem5.aiFreelist[ii] = -1;

   430   }

   431 

   432   iOffset = 0;

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

   434     int nAlloc = (1<<ii);

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

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

   437       memsys5Link(iOffset, ii);

   438       iOffset += nAlloc;

   439     }

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

   441   }

   442 

   443   return SQLITE_OK;

   444 }

   445 

   446 /*

   447 ** Deinitialize this module.

   448 */

   449 static void memsys5Shutdown(void *NotUsed){

   450   return;

   451 }

   452 

   453 /*

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

   455 ** allocations into that log.

   456 */

   457 void sqlite3Memsys5Dump(const char *zFilename){

   458 #ifdef SQLITE_DEBUG

   459   FILE *out;

   460   int i, j, n;

   461   int nMinLog;

   462 

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

   464     out = stdout;

   465   }else{

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

   467     if( out==0 ){

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

   469                       zFilename);

   470       return;

   471     }

   472   }

   473   memsys5Enter();

   474   nMinLog = memsys5Log(mem5.nAtom);

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

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

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

   478   }

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

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

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

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

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

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

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

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

   487   memsys5Leave();

   488   if( out==stdout ){

   489     fflush(stdout);

   490   }else{

   491     fclose(out);

   492   }

   493 #endif

   494 }

   495 

   496 /*

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

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

   499 ** struct populated with the memsys5 methods.

   500 */

   501 const sqlite3_mem_methods *sqlite3MemGetMemsys5(void){

   502   static const sqlite3_mem_methods memsys5Methods = {

   503      memsys5Malloc,

   504      memsys5Free,

   505      memsys5Realloc,

   506      memsys5Size,

   507      memsys5Roundup,

   508      memsys5Init,

   509      memsys5Shutdown,

   510      0

   511   };

   512   return &memsys5Methods;

   513 }

   514 

   515 #endif /* SQLITE_ENABLE_MEMSYS5 */