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_MEMSYS3 is defined.

    25 **

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

    27 */

    28 #include "sqliteInt.h"

    29 

    30 /*

    31 ** This version of the memory allocator is only built into the library

    32 ** SQLITE_ENABLE_MEMSYS3 is defined. Defining this symbol does not

    33 ** mean that the library will use a memory-pool by default, just that

    34 ** it is available. The mempool allocator is activated by calling

    35 ** sqlite3_config().

    36 */

    37 #ifdef SQLITE_ENABLE_MEMSYS3

    38 

    39 /*

    40 ** Maximum size (in Mem3Blocks) of a "small" chunk.

    41 */

    42 #define MX_SMALL 10

    43 

    44 

    45 /*

    46 ** Number of freelist hash slots

    47 */

    48 #define N_HASH  61

    49 

    50 /*

    51 ** A memory allocation (also called a "chunk") consists of two or 

    52 ** more blocks where each block is 8 bytes.  The first 8 bytes are 

    53 ** a header that is not returned to the user.

    54 **

    55 ** A chunk is two or more blocks that is either checked out or

    56 ** free.  The first block has format u.hdr.  u.hdr.size4x is 4 times the

    57 ** size of the allocation in blocks if the allocation is free.

    58 ** The u.hdr.size4x&1 bit is true if the chunk is checked out and

    59 ** false if the chunk is on the freelist.  The u.hdr.size4x&2 bit

    60 ** is true if the previous chunk is checked out and false if the

    61 ** previous chunk is free.  The u.hdr.prevSize field is the size of

    62 ** the previous chunk in blocks if the previous chunk is on the

    63 ** freelist. If the previous chunk is checked out, then

    64 ** u.hdr.prevSize can be part of the data for that chunk and should

    65 ** not be read or written.

    66 **

    67 ** We often identify a chunk by its index in mem3.aPool[].  When

    68 ** this is done, the chunk index refers to the second block of

    69 ** the chunk.  In this way, the first chunk has an index of 1.

    70 ** A chunk index of 0 means "no such chunk" and is the equivalent

    71 ** of a NULL pointer.

    72 **

    73 ** The second block of free chunks is of the form u.list.  The

    74 ** two fields form a double-linked list of chunks of related sizes.

    75 ** Pointers to the head of the list are stored in mem3.aiSmall[] 

    76 ** for smaller chunks and mem3.aiHash[] for larger chunks.

    77 **

    78 ** The second block of a chunk is user data if the chunk is checked 

    79 ** out.  If a chunk is checked out, the user data may extend into

    80 ** the u.hdr.prevSize value of the following chunk.

    81 */

    82 typedef struct Mem3Block Mem3Block;

    83 struct Mem3Block {

    84   union {

    85     struct {

    86       u32 prevSize;   /* Size of previous chunk in Mem3Block elements */

    87       u32 size4x;     /* 4x the size of current chunk in Mem3Block elements */

    88     } hdr;

    89     struct {

    90       u32 next;       /* Index in mem3.aPool[] of next free chunk */

    91       u32 prev;       /* Index in mem3.aPool[] of previous free chunk */

    92     } list;

    93   } u;

    94 };

    95 

    96 /*

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

    98 ** into a single structure named "mem3".  This is to keep the

    99 ** static variables organized and to reduce namespace pollution

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

   101 */

   102 static SQLITE_WSD struct Mem3Global {

   103   /*

   104   ** Memory available for allocation. nPool is the size of the array

   105   ** (in Mem3Blocks) pointed to by aPool less 2.

   106   */

   107   u32 nPool;

   108   Mem3Block *aPool;

   109 

   110   /*

   111   ** True if we are evaluating an out-of-memory callback.

   112   */

   113   int alarmBusy;

   114   

   115   /*

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

   117   */

   118   sqlite3_mutex *mutex;

   119   

   120   /*

   121   ** The minimum amount of free space that we have seen.

   122   */

   123   u32 mnMaster;

   124 

   125   /*

   126   ** iMaster is the index of the master chunk.  Most new allocations

   127   ** occur off of this chunk.  szMaster is the size (in Mem3Blocks)

   128   ** of the current master.  iMaster is 0 if there is not master chunk.

   129   ** The master chunk is not in either the aiHash[] or aiSmall[].

   130   */

   131   u32 iMaster;

   132   u32 szMaster;

   133 

   134   /*

   135   ** Array of lists of free blocks according to the block size 

   136   ** for smaller chunks, or a hash on the block size for larger

   137   ** chunks.

   138   */

   139   u32 aiSmall[MX_SMALL-1];   /* For sizes 2 through MX_SMALL, inclusive */

   140   u32 aiHash[N_HASH];        /* For sizes MX_SMALL+1 and larger */

   141 } mem3 = { 97535575 };

   142 

   143 #define mem3 GLOBAL(struct Mem3Global, mem3)

   144 

   145 /*

   146 ** Unlink the chunk at mem3.aPool[i] from list it is currently

   147 ** on.  *pRoot is the list that i is a member of.

   148 */

   149 static void memsys3UnlinkFromList(u32 i, u32 *pRoot){

   150   u32 next = mem3.aPool[i].u.list.next;

   151   u32 prev = mem3.aPool[i].u.list.prev;

   152   assert( sqlite3_mutex_held(mem3.mutex) );

   153   if( prev==0 ){

   154     *pRoot = next;

   155   }else{

   156     mem3.aPool[prev].u.list.next = next;

   157   }

   158   if( next ){

   159     mem3.aPool[next].u.list.prev = prev;

   160   }

   161   mem3.aPool[i].u.list.next = 0;

   162   mem3.aPool[i].u.list.prev = 0;

   163 }

   164 

   165 /*

   166 ** Unlink the chunk at index i from 

   167 ** whatever list is currently a member of.

   168 */

   169 static void memsys3Unlink(u32 i){

   170   u32 size, hash;

   171   assert( sqlite3_mutex_held(mem3.mutex) );

   172   assert( (mem3.aPool[i-1].u.hdr.size4x & 1)==0 );

   173   assert( i>=1 );

   174   size = mem3.aPool[i-1].u.hdr.size4x/4;

   175   assert( size==mem3.aPool[i+size-1].u.hdr.prevSize );

   176   assert( size>=2 );

   177   if( size <= MX_SMALL ){

   178     memsys3UnlinkFromList(i, &mem3.aiSmall[size-2]);

   179   }else{

   180     hash = size % N_HASH;

   181     memsys3UnlinkFromList(i, &mem3.aiHash[hash]);

   182   }

   183 }

   184 

   185 /*

   186 ** Link the chunk at mem3.aPool[i] so that is on the list rooted

   187 ** at *pRoot.

   188 */

   189 static void memsys3LinkIntoList(u32 i, u32 *pRoot){

   190   assert( sqlite3_mutex_held(mem3.mutex) );

   191   mem3.aPool[i].u.list.next = *pRoot;

   192   mem3.aPool[i].u.list.prev = 0;

   193   if( *pRoot ){

   194     mem3.aPool[*pRoot].u.list.prev = i;

   195   }

   196   *pRoot = i;

   197 }

   198 

   199 /*

   200 ** Link the chunk at index i into either the appropriate

   201 ** small chunk list, or into the large chunk hash table.

   202 */

   203 static void memsys3Link(u32 i){

   204   u32 size, hash;

   205   assert( sqlite3_mutex_held(mem3.mutex) );

   206   assert( i>=1 );

   207   assert( (mem3.aPool[i-1].u.hdr.size4x & 1)==0 );

   208   size = mem3.aPool[i-1].u.hdr.size4x/4;

   209   assert( size==mem3.aPool[i+size-1].u.hdr.prevSize );

   210   assert( size>=2 );

   211   if( size <= MX_SMALL ){

   212     memsys3LinkIntoList(i, &mem3.aiSmall[size-2]);

   213   }else{

   214     hash = size % N_HASH;

   215     memsys3LinkIntoList(i, &mem3.aiHash[hash]);

   216   }

   217 }

   218 

   219 /*

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

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

   222 ** sqlite3GlobalConfig.bMemStat is true.

   223 */

   224 static void memsys3Enter(void){

   225   if( sqlite3GlobalConfig.bMemstat==0 && mem3.mutex==0 ){

   226     mem3.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);

   227   }

   228   sqlite3_mutex_enter(mem3.mutex);

   229 }

   230 static void memsys3Leave(void){

   231   sqlite3_mutex_leave(mem3.mutex);

   232 }

   233 

   234 /*

   235 ** Called when we are unable to satisfy an allocation of nBytes.

   236 */

   237 static void memsys3OutOfMemory(int nByte){

   238   if( !mem3.alarmBusy ){

   239     mem3.alarmBusy = 1;

   240     assert( sqlite3_mutex_held(mem3.mutex) );

   241     sqlite3_mutex_leave(mem3.mutex);

   242     sqlite3_release_memory(nByte);

   243     sqlite3_mutex_enter(mem3.mutex);

   244     mem3.alarmBusy = 0;

   245   }

   246 }

   247 

   248 

   249 /*

   250 ** Chunk i is a free chunk that has been unlinked.  Adjust its 

   251 ** size parameters for check-out and return a pointer to the 

   252 ** user portion of the chunk.

   253 */

   254 static void *memsys3Checkout(u32 i, int nBlock){

   255   u32 x;

   256   assert( sqlite3_mutex_held(mem3.mutex) );

   257   assert( i>=1 );

   258   assert( mem3.aPool[i-1].u.hdr.size4x/4==nBlock );

   259   assert( mem3.aPool[i+nBlock-1].u.hdr.prevSize==nBlock );

   260   x = mem3.aPool[i-1].u.hdr.size4x;

   261   mem3.aPool[i-1].u.hdr.size4x = nBlock*4 | 1 | (x&2);

   262   mem3.aPool[i+nBlock-1].u.hdr.prevSize = nBlock;

   263   mem3.aPool[i+nBlock-1].u.hdr.size4x |= 2;

   264   return &mem3.aPool[i];

   265 }

   266 

   267 /*

   268 ** Carve a piece off of the end of the mem3.iMaster free chunk.

   269 ** Return a pointer to the new allocation.  Or, if the master chunk

   270 ** is not large enough, return 0.

   271 */

   272 static void *memsys3FromMaster(int nBlock){

   273   assert( sqlite3_mutex_held(mem3.mutex) );

   274   assert( mem3.szMaster>=nBlock );

   275   if( nBlock>=mem3.szMaster-1 ){

   276     /* Use the entire master */

   277     void *p = memsys3Checkout(mem3.iMaster, mem3.szMaster);

   278     mem3.iMaster = 0;

   279     mem3.szMaster = 0;

   280     mem3.mnMaster = 0;

   281     return p;

   282   }else{

   283     /* Split the master block.  Return the tail. */

   284     u32 newi, x;

   285     newi = mem3.iMaster + mem3.szMaster - nBlock;

   286     assert( newi > mem3.iMaster+1 );

   287     mem3.aPool[mem3.iMaster+mem3.szMaster-1].u.hdr.prevSize = nBlock;

   288     mem3.aPool[mem3.iMaster+mem3.szMaster-1].u.hdr.size4x |= 2;

   289     mem3.aPool[newi-1].u.hdr.size4x = nBlock*4 + 1;

   290     mem3.szMaster -= nBlock;

   291     mem3.aPool[newi-1].u.hdr.prevSize = mem3.szMaster;

   292     x = mem3.aPool[mem3.iMaster-1].u.hdr.size4x & 2;

   293     mem3.aPool[mem3.iMaster-1].u.hdr.size4x = mem3.szMaster*4 | x;

   294     if( mem3.szMaster < mem3.mnMaster ){

   295       mem3.mnMaster = mem3.szMaster;

   296     }

   297     return (void*)&mem3.aPool[newi];

   298   }

   299 }

   300 

   301 /*

   302 ** *pRoot is the head of a list of free chunks of the same size

   303 ** or same size hash.  In other words, *pRoot is an entry in either

   304 ** mem3.aiSmall[] or mem3.aiHash[].  

   305 **

   306 ** This routine examines all entries on the given list and tries

   307 ** to coalesce each entries with adjacent free chunks.  

   308 **

   309 ** If it sees a chunk that is larger than mem3.iMaster, it replaces 

   310 ** the current mem3.iMaster with the new larger chunk.  In order for

   311 ** this mem3.iMaster replacement to work, the master chunk must be

   312 ** linked into the hash tables.  That is not the normal state of

   313 ** affairs, of course.  The calling routine must link the master

   314 ** chunk before invoking this routine, then must unlink the (possibly

   315 ** changed) master chunk once this routine has finished.

   316 */

   317 static void memsys3Merge(u32 *pRoot){

   318   u32 iNext, prev, size, i, x;

   319 

   320   assert( sqlite3_mutex_held(mem3.mutex) );

   321   for(i=*pRoot; i>0; i=iNext){

   322     iNext = mem3.aPool[i].u.list.next;

   323     size = mem3.aPool[i-1].u.hdr.size4x;

   324     assert( (size&1)==0 );

   325     if( (size&2)==0 ){

   326       memsys3UnlinkFromList(i, pRoot);

   327       assert( i > mem3.aPool[i-1].u.hdr.prevSize );

   328       prev = i - mem3.aPool[i-1].u.hdr.prevSize;

   329       if( prev==iNext ){

   330         iNext = mem3.aPool[prev].u.list.next;

   331       }

   332       memsys3Unlink(prev);

   333       size = i + size/4 - prev;

   334       x = mem3.aPool[prev-1].u.hdr.size4x & 2;

   335       mem3.aPool[prev-1].u.hdr.size4x = size*4 | x;

   336       mem3.aPool[prev+size-1].u.hdr.prevSize = size;

   337       memsys3Link(prev);

   338       i = prev;

   339     }else{

   340       size /= 4;

   341     }

   342     if( size>mem3.szMaster ){

   343       mem3.iMaster = i;

   344       mem3.szMaster = size;

   345     }

   346   }

   347 }

   348 

   349 /*

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

   351 ** Return NULL if unable.

   352 **

   353 ** This function assumes that the necessary mutexes, if any, are

   354 ** already held by the caller. Hence "Unsafe".

   355 */

   356 static void *memsys3MallocUnsafe(int nByte){

   357   u32 i;

   358   int nBlock;

   359   int toFree;

   360 

   361   assert( sqlite3_mutex_held(mem3.mutex) );

   362   assert( sizeof(Mem3Block)==8 );

   363   if( nByte<=12 ){

   364     nBlock = 2;

   365   }else{

   366     nBlock = (nByte + 11)/8;

   367   }

   368   assert( nBlock>=2 );

   369 

   370   /* STEP 1:

   371   ** Look for an entry of the correct size in either the small

   372   ** chunk table or in the large chunk hash table.  This is

   373   ** successful most of the time (about 9 times out of 10).

   374   */

   375   if( nBlock <= MX_SMALL ){

   376     i = mem3.aiSmall[nBlock-2];

   377     if( i>0 ){

   378       memsys3UnlinkFromList(i, &mem3.aiSmall[nBlock-2]);

   379       return memsys3Checkout(i, nBlock);

   380     }

   381   }else{

   382     int hash = nBlock % N_HASH;

   383     for(i=mem3.aiHash[hash]; i>0; i=mem3.aPool[i].u.list.next){

   384       if( mem3.aPool[i-1].u.hdr.size4x/4==nBlock ){

   385         memsys3UnlinkFromList(i, &mem3.aiHash[hash]);

   386         return memsys3Checkout(i, nBlock);

   387       }

   388     }

   389   }

   390 

   391   /* STEP 2:

   392   ** Try to satisfy the allocation by carving a piece off of the end

   393   ** of the master chunk.  This step usually works if step 1 fails.

   394   */

   395   if( mem3.szMaster>=nBlock ){

   396     return memsys3FromMaster(nBlock);

   397   }

   398 

   399 

   400   /* STEP 3:  

   401   ** Loop through the entire memory pool.  Coalesce adjacent free

   402   ** chunks.  Recompute the master chunk as the largest free chunk.

   403   ** Then try again to satisfy the allocation by carving a piece off

   404   ** of the end of the master chunk.  This step happens very

   405   ** rarely (we hope!)

   406   */

   407   for(toFree=nBlock*16; toFree<(mem3.nPool*16); toFree *= 2){

   408     memsys3OutOfMemory(toFree);

   409     if( mem3.iMaster ){

   410       memsys3Link(mem3.iMaster);

   411       mem3.iMaster = 0;

   412       mem3.szMaster = 0;

   413     }

   414     for(i=0; i<N_HASH; i++){

   415       memsys3Merge(&mem3.aiHash[i]);

   416     }

   417     for(i=0; i<MX_SMALL-1; i++){

   418       memsys3Merge(&mem3.aiSmall[i]);

   419     }

   420     if( mem3.szMaster ){

   421       memsys3Unlink(mem3.iMaster);

   422       if( mem3.szMaster>=nBlock ){

   423         return memsys3FromMaster(nBlock);

   424       }

   425     }

   426   }

   427 

   428   /* If none of the above worked, then we fail. */

   429   return 0;

   430 }

   431 

   432 /*

   433 ** Free an outstanding memory allocation.

   434 **

   435 ** This function assumes that the necessary mutexes, if any, are

   436 ** already held by the caller. Hence "Unsafe".

   437 */

   438 void memsys3FreeUnsafe(void *pOld){

   439   Mem3Block *p = (Mem3Block*)pOld;

   440   int i;

   441   u32 size, x;

   442   assert( sqlite3_mutex_held(mem3.mutex) );

   443   assert( p>mem3.aPool && p<&mem3.aPool[mem3.nPool] );

   444   i = p - mem3.aPool;

   445   assert( (mem3.aPool[i-1].u.hdr.size4x&1)==1 );

   446   size = mem3.aPool[i-1].u.hdr.size4x/4;

   447   assert( i+size<=mem3.nPool+1 );

   448   mem3.aPool[i-1].u.hdr.size4x &= ~1;

   449   mem3.aPool[i+size-1].u.hdr.prevSize = size;

   450   mem3.aPool[i+size-1].u.hdr.size4x &= ~2;

   451   memsys3Link(i);

   452 

   453   /* Try to expand the master using the newly freed chunk */

   454   if( mem3.iMaster ){

   455     while( (mem3.aPool[mem3.iMaster-1].u.hdr.size4x&2)==0 ){

   456       size = mem3.aPool[mem3.iMaster-1].u.hdr.prevSize;

   457       mem3.iMaster -= size;

   458       mem3.szMaster += size;

   459       memsys3Unlink(mem3.iMaster);

   460       x = mem3.aPool[mem3.iMaster-1].u.hdr.size4x & 2;

   461       mem3.aPool[mem3.iMaster-1].u.hdr.size4x = mem3.szMaster*4 | x;

   462       mem3.aPool[mem3.iMaster+mem3.szMaster-1].u.hdr.prevSize = mem3.szMaster;

   463     }

   464     x = mem3.aPool[mem3.iMaster-1].u.hdr.size4x & 2;

   465     while( (mem3.aPool[mem3.iMaster+mem3.szMaster-1].u.hdr.size4x&1)==0 ){

   466       memsys3Unlink(mem3.iMaster+mem3.szMaster);

   467       mem3.szMaster += mem3.aPool[mem3.iMaster+mem3.szMaster-1].u.hdr.size4x/4;

   468       mem3.aPool[mem3.iMaster-1].u.hdr.size4x = mem3.szMaster*4 | x;

   469       mem3.aPool[mem3.iMaster+mem3.szMaster-1].u.hdr.prevSize = mem3.szMaster;

   470     }

   471   }

   472 }

   473 

   474 /*

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

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

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

   478 */

   479 static int memsys3Size(void *p){

   480   Mem3Block *pBlock;

   481   if( p==0 ) return 0;

   482   pBlock = (Mem3Block*)p;

   483   assert( (pBlock[-1].u.hdr.size4x&1)!=0 );

   484   return (pBlock[-1].u.hdr.size4x&~3)*2 - 4;

   485 }

   486 

   487 /*

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

   489 */

   490 static int memsys3Roundup(int n){

   491   if( n<=12 ){

   492     return 12;

   493   }else{

   494     return ((n+11)&~7) - 4;

   495   }

   496 }

   497 

   498 /*

   499 ** Allocate nBytes of memory.

   500 */

   501 static void *memsys3Malloc(int nBytes){

   502   sqlite3_int64 *p;

   503   assert( nBytes>0 );          /* malloc.c filters out 0 byte requests */

   504   memsys3Enter();

   505   p = memsys3MallocUnsafe(nBytes);

   506   memsys3Leave();

   507   return (void*)p; 

   508 }

   509 

   510 /*

   511 ** Free memory.

   512 */

   513 void memsys3Free(void *pPrior){

   514   assert( pPrior );

   515   memsys3Enter();

   516   memsys3FreeUnsafe(pPrior);

   517   memsys3Leave();

   518 }

   519 

   520 /*

   521 ** Change the size of an existing memory allocation

   522 */

   523 void *memsys3Realloc(void *pPrior, int nBytes){

   524   int nOld;

   525   void *p;

   526   if( pPrior==0 ){

   527     return sqlite3_malloc(nBytes);

   528   }

   529   if( nBytes<=0 ){

   530     sqlite3_free(pPrior);

   531     return 0;

   532   }

   533   nOld = memsys3Size(pPrior);

   534   if( nBytes<=nOld && nBytes>=nOld-128 ){

   535     return pPrior;

   536   }

   537   memsys3Enter();

   538   p = memsys3MallocUnsafe(nBytes);

   539   if( p ){

   540     if( nOld<nBytes ){

   541       memcpy(p, pPrior, nOld);

   542     }else{

   543       memcpy(p, pPrior, nBytes);

   544     }

   545     memsys3FreeUnsafe(pPrior);

   546   }

   547   memsys3Leave();

   548   return p;

   549 }

   550 

   551 /*

   552 ** Initialize this module.

   553 */

   554 static int memsys3Init(void *NotUsed){

   555   if( !sqlite3GlobalConfig.pHeap ){

   556     return SQLITE_ERROR;

   557   }

   558 

   559   /* Store a pointer to the memory block in global structure mem3. */

   560   assert( sizeof(Mem3Block)==8 );

   561   mem3.aPool = (Mem3Block *)sqlite3GlobalConfig.pHeap;

   562   mem3.nPool = (sqlite3GlobalConfig.nHeap / sizeof(Mem3Block)) - 2;

   563 

   564   /* Initialize the master block. */

   565   mem3.szMaster = mem3.nPool;

   566   mem3.mnMaster = mem3.szMaster;

   567   mem3.iMaster = 1;

   568   mem3.aPool[0].u.hdr.size4x = (mem3.szMaster<<2) + 2;

   569   mem3.aPool[mem3.nPool].u.hdr.prevSize = mem3.nPool;

   570   mem3.aPool[mem3.nPool].u.hdr.size4x = 1;

   571 

   572   return SQLITE_OK;

   573 }

   574 

   575 /*

   576 ** Deinitialize this module.

   577 */

   578 static void memsys3Shutdown(void *NotUsed){

   579   return;

   580 }

   581 

   582 

   583 

   584 /*

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

   586 ** allocations into that log.

   587 */

   588 void sqlite3Memsys3Dump(const char *zFilename){

   589 #ifdef SQLITE_DEBUG

   590   FILE *out;

   591   int i, j;

   592   u32 size;

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

   594     out = stdout;

   595   }else{

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

   597     if( out==0 ){

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

   599                       zFilename);

   600       return;

   601     }

   602   }

   603   memsys3Enter();

   604   fprintf(out, "CHUNKS:\n");

   605   for(i=1; i<=mem3.nPool; i+=size/4){

   606     size = mem3.aPool[i-1].u.hdr.size4x;

   607     if( size/4<=1 ){

   608       fprintf(out, "%p size error\n", &mem3.aPool[i]);

   609       assert( 0 );

   610       break;

   611     }

   612     if( (size&1)==0 && mem3.aPool[i+size/4-1].u.hdr.prevSize!=size/4 ){

   613       fprintf(out, "%p tail size does not match\n", &mem3.aPool[i]);

   614       assert( 0 );

   615       break;

   616     }

   617     if( ((mem3.aPool[i+size/4-1].u.hdr.size4x&2)>>1)!=(size&1) ){

   618       fprintf(out, "%p tail checkout bit is incorrect\n", &mem3.aPool[i]);

   619       assert( 0 );

   620       break;

   621     }

   622     if( size&1 ){

   623       fprintf(out, "%p %6d bytes checked out\n", &mem3.aPool[i], (size/4)*8-8);

   624     }else{

   625       fprintf(out, "%p %6d bytes free%s\n", &mem3.aPool[i], (size/4)*8-8,

   626                   i==mem3.iMaster ? " **master**" : "");

   627     }

   628   }

   629   for(i=0; i<MX_SMALL-1; i++){

   630     if( mem3.aiSmall[i]==0 ) continue;

   631     fprintf(out, "small(%2d):", i);

   632     for(j = mem3.aiSmall[i]; j>0; j=mem3.aPool[j].u.list.next){

   633       fprintf(out, " %p(%d)", &mem3.aPool[j],

   634               (mem3.aPool[j-1].u.hdr.size4x/4)*8-8);

   635     }

   636     fprintf(out, "\n"); 

   637   }

   638   for(i=0; i<N_HASH; i++){

   639     if( mem3.aiHash[i]==0 ) continue;

   640     fprintf(out, "hash(%2d):", i);

   641     for(j = mem3.aiHash[i]; j>0; j=mem3.aPool[j].u.list.next){

   642       fprintf(out, " %p(%d)", &mem3.aPool[j],

   643               (mem3.aPool[j-1].u.hdr.size4x/4)*8-8);

   644     }

   645     fprintf(out, "\n"); 

   646   }

   647   fprintf(out, "master=%d\n", mem3.iMaster);

   648   fprintf(out, "nowUsed=%d\n", mem3.nPool*8 - mem3.szMaster*8);

   649   fprintf(out, "mxUsed=%d\n", mem3.nPool*8 - mem3.mnMaster*8);

   650   sqlite3_mutex_leave(mem3.mutex);

   651   if( out==stdout ){

   652     fflush(stdout);

   653   }else{

   654     fclose(out);

   655   }

   656 #endif

   657 }

   658 

   659 /*

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

   661 ** linkage.

   662 **

   663 ** Populate the low-level memory allocation function pointers in

   664 ** sqlite3GlobalConfig.m with pointers to the routines in this file. The

   665 ** arguments specify the block of memory to manage.

   666 **

   667 ** This routine is only called by sqlite3_config(), and therefore

   668 ** is not required to be threadsafe (it is not).

   669 */

   670 const sqlite3_mem_methods *sqlite3MemGetMemsys3(void){

   671   static const sqlite3_mem_methods mempoolMethods = {

   672      memsys3Malloc,

   673      memsys3Free,

   674      memsys3Realloc,

   675      memsys3Size,

   676      memsys3Roundup,

   677      memsys3Init,

   678      memsys3Shutdown,

   679      0

   680   };

   681   return &mempoolMethods;

   682 }

   683 

   684 #endif /* SQLITE_ENABLE_MEMSYS3 */