src/mem3.c

   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 #include "sqliteInt.h"
  27
  28 /*
  29 ** This version of the memory allocator is only built into the library
  30 ** SQLITE_ENABLE_MEMSYS3 is defined. Defining this symbol does not
  31 ** mean that the library will use a memory-pool by default, just that
  32 ** it is available. The mempool allocator is activated by calling
  33 ** sqlite3_config().
  34 */
  35 #ifdef SQLITE_ENABLE_MEMSYS3
  36
  37 /*
  38 ** Maximum size (in Mem3Blocks) of a "small" chunk.
  39 */
  40 #define MX_SMALL 10
  41
  42
  43 /*
  44 ** Number of freelist hash slots
  45 */
  46 #define N_HASH  61
  47
  48 /*
  49 ** A memory allocation (also called a "chunk") consists of two or
  50 ** more blocks where each block is 8 bytes.  The first 8 bytes are
  51 ** a header that is not returned to the user.
  52 **
  53 ** A chunk is two or more blocks that is either checked out or
  54 ** free.  The first block has format u.hdr.  u.hdr.size4x is 4 times the
  55 ** size of the allocation in blocks if the allocation is free.
  56 ** The u.hdr.size4x&1 bit is true if the chunk is checked out and
  57 ** false if the chunk is on the freelist.  The u.hdr.size4x&2 bit
  58 ** is true if the previous chunk is checked out and false if the
  59 ** previous chunk is free.  The u.hdr.prevSize field is the size of
  60 ** the previous chunk in blocks if the previous chunk is on the
  61 ** freelist. If the previous chunk is checked out, then
  62 ** u.hdr.prevSize can be part of the data for that chunk and should
  63 ** not be read or written.
  64 **
  65 ** We often identify a chunk by its index in mem3.aPool[].  When
  66 ** this is done, the chunk index refers to the second block of
  67 ** the chunk.  In this way, the first chunk has an index of 1.
  68 ** A chunk index of 0 means "no such chunk" and is the equivalent
  69 ** of a NULL pointer.
  70 **
  71 ** The second block of free chunks is of the form u.list.  The
  72 ** two fields form a double-linked list of chunks of related sizes.
  73 ** Pointers to the head of the list are stored in mem3.aiSmall[]
  74 ** for smaller chunks and mem3.aiHash[] for larger chunks.
  75 **
  76 ** The second block of a chunk is user data if the chunk is checked
  77 ** out.  If a chunk is checked out, the user data may extend into
  78 ** the u.hdr.prevSize value of the following chunk.
  79 */
  80 typedef struct Mem3Block Mem3Block;
  81 struct Mem3Block {
  82   union {
  83     struct {
  84       u32 prevSize;   /* Size of previous chunk in Mem3Block elements */
  85       u32 size4x;     /* 4x the size of current chunk in Mem3Block elements */
  86     } hdr;
  87     struct {
  88       u32 next;       /* Index in mem3.aPool[] of next free chunk */
  89       u32 prev;       /* Index in mem3.aPool[] of previous free chunk */
  90     } list;
  91   } u;
  92 };
  93
  94 /*
  95 ** All of the static variables used by this module are collected
  96 ** into a single structure named "mem3".  This is to keep the
  97 ** static variables organized and to reduce namespace pollution
  98 ** when this module is combined with other in the amalgamation.
  99 */
 100 static SQLITE_WSD struct Mem3Global {
 101   /*
 102   ** Memory available for allocation. nPool is the size of the array
 103   ** (in Mem3Blocks) pointed to by aPool less 2.
 104   */
 105   u32 nPool;
 106   Mem3Block *aPool;
 107
 108   /*
 109   ** True if we are evaluating an out-of-memory callback.
 110   */
 111   int alarmBusy;
 112
 113   /*
 114   ** Mutex to control access to the memory allocation subsystem.
 115   */
 116   sqlite3_mutex *mutex;
 117
 118   /*
 119   ** The minimum amount of free space that we have seen.
 120   */
 121   u32 mnMaster;
 122
 123   /*
 124   ** iMaster is the index of the master chunk.  Most new allocations
 125   ** occur off of this chunk.  szMaster is the size (in Mem3Blocks)
 126   ** of the current master.  iMaster is 0 if there is not master chunk.
 127   ** The master chunk is not in either the aiHash[] or aiSmall[].
 128   */
 129   u32 iMaster;
 130   u32 szMaster;
 131
 132   /*
 133   ** Array of lists of free blocks according to the block size
 134   ** for smaller chunks, or a hash on the block size for larger
 135   ** chunks.
 136   */
 137   u32 aiSmall[MX_SMALL-1];   /* For sizes 2 through MX_SMALL, inclusive */
 138   u32 aiHash[N_HASH];        /* For sizes MX_SMALL+1 and larger */
 139 } mem3 = { 97535575 };
 140
 141 #define mem3 GLOBAL(struct Mem3Global, mem3)
 142
 143 /*
 144 ** Unlink the chunk at mem3.aPool[i] from list it is currently
 145 ** on.  *pRoot is the list that i is a member of.
 146 */
 147 static void memsys3UnlinkFromList(u32 i, u32 *pRoot){
 148   u32 next = mem3.aPool[i].u.list.next;
 149   u32 prev = mem3.aPool[i].u.list.prev;
 150   assert( sqlite3_mutex_held(mem3.mutex) );
 151   if( prev==0 ){
 152     *pRoot = next;
 153   }else{
 154     mem3.aPool[prev].u.list.next = next;
 155   }
 156   if( next ){
 157     mem3.aPool[next].u.list.prev = prev;
 158   }
 159   mem3.aPool[i].u.list.next = 0;
 160   mem3.aPool[i].u.list.prev = 0;
 161 }
 162
 163 /*
 164 ** Unlink the chunk at index i from
 165 ** whatever list is currently a member of.
 166 */
 167 static void memsys3Unlink(u32 i){
 168   u32 size, hash;
 169   assert( sqlite3_mutex_held(mem3.mutex) );
 170   assert( (mem3.aPool[i-1].u.hdr.size4x & 1)==0 );
 171   assert( i>=1 );
 172   size = mem3.aPool[i-1].u.hdr.size4x/4;
 173   assert( size==mem3.aPool[i+size-1].u.hdr.prevSize );
 174   assert( size>=2 );
 175   if( size <= MX_SMALL ){
 176     memsys3UnlinkFromList(i, &mem3.aiSmall[size-2]);
 177   }else{
 178     hash = size % N_HASH;
 179     memsys3UnlinkFromList(i, &mem3.aiHash[hash]);
 180   }
 181 }
 182
 183 /*
 184 ** Link the chunk at mem3.aPool[i] so that is on the list rooted
 185 ** at *pRoot.
 186 */
 187 static void memsys3LinkIntoList(u32 i, u32 *pRoot){
 188   assert( sqlite3_mutex_held(mem3.mutex) );
 189   mem3.aPool[i].u.list.next = *pRoot;
 190   mem3.aPool[i].u.list.prev = 0;
 191   if( *pRoot ){
 192     mem3.aPool[*pRoot].u.list.prev = i;
 193   }
 194   *pRoot = i;
 195 }
 196
 197 /*
 198 ** Link the chunk at index i into either the appropriate
 199 ** small chunk list, or into the large chunk hash table.
 200 */
 201 static void memsys3Link(u32 i){
 202   u32 size, hash;
 203   assert( sqlite3_mutex_held(mem3.mutex) );
 204   assert( i>=1 );
 205   assert( (mem3.aPool[i-1].u.hdr.size4x & 1)==0 );
 206   size = mem3.aPool[i-1].u.hdr.size4x/4;
 207   assert( size==mem3.aPool[i+size-1].u.hdr.prevSize );
 208   assert( size>=2 );
 209   if( size <= MX_SMALL ){
 210     memsys3LinkIntoList(i, &mem3.aiSmall[size-2]);
 211   }else{
 212     hash = size % N_HASH;
 213     memsys3LinkIntoList(i, &mem3.aiHash[hash]);
 214   }
 215 }
 216
 217 /*
 218 ** If the STATIC_MEM mutex is not already held, obtain it now. The mutex
 219 ** will already be held (obtained by code in malloc.c) if
 220 ** sqlite3GlobalConfig.bMemStat is true.
 221 */
 222 static void memsys3Enter(void){
 223   if( sqlite3GlobalConfig.bMemstat==0 && mem3.mutex==0 ){
 224     mem3.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_MEM);
 225   }
 226   sqlite3_mutex_enter(mem3.mutex);
 227 }
 228 static void memsys3Leave(void){
 229   sqlite3_mutex_leave(mem3.mutex);
 230 }
 231
 232 /*
 233 ** Called when we are unable to satisfy an allocation of nBytes.
 234 */
 235 static void memsys3OutOfMemory(int nByte){
 236   if( !mem3.alarmBusy ){
 237     mem3.alarmBusy = 1;
 238     assert( sqlite3_mutex_held(mem3.mutex) );
 239     sqlite3_mutex_leave(mem3.mutex);
 240     sqlite3_release_memory(nByte);
 241     sqlite3_mutex_enter(mem3.mutex);
 242     mem3.alarmBusy = 0;
 243   }
 244 }
 245
 246
 247 /*
 248 ** Chunk i is a free chunk that has been unlinked.  Adjust its
 249 ** size parameters for check-out and return a pointer to the
 250 ** user portion of the chunk.
 251 */
 252 static void *memsys3Checkout(u32 i, u32 nBlock){
 253   u32 x;
 254   assert( sqlite3_mutex_held(mem3.mutex) );
 255   assert( i>=1 );
 256   assert( mem3.aPool[i-1].u.hdr.size4x/4==nBlock );
 257   assert( mem3.aPool[i+nBlock-1].u.hdr.prevSize==nBlock );
 258   x = mem3.aPool[i-1].u.hdr.size4x;
 259   mem3.aPool[i-1].u.hdr.size4x = nBlock*4 | 1 | (x&2);
 260   mem3.aPool[i+nBlock-1].u.hdr.prevSize = nBlock;
 261   mem3.aPool[i+nBlock-1].u.hdr.size4x |= 2;
 262   return &mem3.aPool[i];
 263 }
 264
 265 /*
 266 ** Carve a piece off of the end of the mem3.iMaster free chunk.
 267 ** Return a pointer to the new allocation.  Or, if the master chunk
 268 ** is not large enough, return 0.
 269 */
 270 static void *memsys3FromMaster(u32 nBlock){
 271   assert( sqlite3_mutex_held(mem3.mutex) );
 272   assert( mem3.szMaster>=nBlock );
 273   if( nBlock>=mem3.szMaster-1 ){
 274     /* Use the entire master */
 275     void *p = memsys3Checkout(mem3.iMaster, mem3.szMaster);
 276     mem3.iMaster = 0;
 277     mem3.szMaster = 0;
 278     mem3.mnMaster = 0;
 279     return p;
 280   }else{
 281     /* Split the master block.  Return the tail. */
 282     u32 newi, x;
 283     newi = mem3.iMaster + mem3.szMaster - nBlock;
 284     assert( newi > mem3.iMaster+1 );
 285     mem3.aPool[mem3.iMaster+mem3.szMaster-1].u.hdr.prevSize = nBlock;
 286     mem3.aPool[mem3.iMaster+mem3.szMaster-1].u.hdr.size4x |= 2;
 287     mem3.aPool[newi-1].u.hdr.size4x = nBlock*4 + 1;
 288     mem3.szMaster -= nBlock;
 289     mem3.aPool[newi-1].u.hdr.prevSize = mem3.szMaster;
 290     x = mem3.aPool[mem3.iMaster-1].u.hdr.size4x & 2;
 291     mem3.aPool[mem3.iMaster-1].u.hdr.size4x = mem3.szMaster*4 | x;
 292     if( mem3.szMaster < mem3.mnMaster ){
 293       mem3.mnMaster = mem3.szMaster;
 294     }
 295     return (void*)&mem3.aPool[newi];
 296   }
 297 }
 298
 299 /*
 300 ** *pRoot is the head of a list of free chunks of the same size
 301 ** or same size hash.  In other words, *pRoot is an entry in either
 302 ** mem3.aiSmall[] or mem3.aiHash[].
 303 **
 304 ** This routine examines all entries on the given list and tries
 305 ** to coalesce each entries with adjacent free chunks.
 306 **
 307 ** If it sees a chunk that is larger than mem3.iMaster, it replaces
 308 ** the current mem3.iMaster with the new larger chunk.  In order for
 309 ** this mem3.iMaster replacement to work, the master chunk must be
 310 ** linked into the hash tables.  That is not the normal state of
 311 ** affairs, of course.  The calling routine must link the master
 312 ** chunk before invoking this routine, then must unlink the (possibly
 313 ** changed) master chunk once this routine has finished.
 314 */
 315 static void memsys3Merge(u32 *pRoot){
 316   u32 iNext, prev, size, i, x;
 317
 318   assert( sqlite3_mutex_held(mem3.mutex) );
 319   for(i=*pRoot; i>0; i=iNext){
 320     iNext = mem3.aPool[i].u.list.next;
 321     size = mem3.aPool[i-1].u.hdr.size4x;
 322     assert( (size&1)==0 );
 323     if( (size&2)==0 ){
 324       memsys3UnlinkFromList(i, pRoot);
 325       assert( i > mem3.aPool[i-1].u.hdr.prevSize );
 326       prev = i - mem3.aPool[i-1].u.hdr.prevSize;
 327       if( prev==iNext ){
 328         iNext = mem3.aPool[prev].u.list.next;
 329       }
 330       memsys3Unlink(prev);
 331       size = i + size/4 - prev;
 332       x = mem3.aPool[prev-1].u.hdr.size4x & 2;
 333       mem3.aPool[prev-1].u.hdr.size4x = size*4 | x;
 334       mem3.aPool[prev+size-1].u.hdr.prevSize = size;
 335       memsys3Link(prev);
 336       i = prev;
 337     }else{
 338       size /= 4;
 339     }
 340     if( size>mem3.szMaster ){
 341       mem3.iMaster = i;
 342       mem3.szMaster = size;
 343     }
 344   }
 345 }
 346
 347 /*
 348 ** Return a block of memory of at least nBytes in size.
 349 ** Return NULL if unable.
 350 **
 351 ** This function assumes that the necessary mutexes, if any, are
 352 ** already held by the caller. Hence "Unsafe".
 353 */
 354 static void *memsys3MallocUnsafe(int nByte){
 355   u32 i;
 356   u32 nBlock;
 357   u32 toFree;
 358
 359   assert( sqlite3_mutex_held(mem3.mutex) );
 360   assert( sizeof(Mem3Block)==8 );
 361   if( nByte<=12 ){
 362     nBlock = 2;
 363   }else{
 364     nBlock = (nByte + 11)/8;
 365   }
 366   assert( nBlock>=2 );
 367
 368   /* STEP 1:
 369   ** Look for an entry of the correct size in either the small
 370   ** chunk table or in the large chunk hash table.  This is
 371   ** successful most of the time (about 9 times out of 10).
 372   */
 373   if( nBlock <= MX_SMALL ){
 374     i = mem3.aiSmall[nBlock-2];
 375     if( i>0 ){
 376       memsys3UnlinkFromList(i, &mem3.aiSmall[nBlock-2]);
 377       return memsys3Checkout(i, nBlock);
 378     }
 379   }else{
 380     int hash = nBlock % N_HASH;
 381     for(i=mem3.aiHash[hash]; i>0; i=mem3.aPool[i].u.list.next){
 382       if( mem3.aPool[i-1].u.hdr.size4x/4==nBlock ){
 383         memsys3UnlinkFromList(i, &mem3.aiHash[hash]);
 384         return memsys3Checkout(i, nBlock);
 385       }
 386     }
 387   }
 388
 389   /* STEP 2:
 390   ** Try to satisfy the allocation by carving a piece off of the end
 391   ** of the master chunk.  This step usually works if step 1 fails.
 392   */
 393   if( mem3.szMaster>=nBlock ){
 394     return memsys3FromMaster(nBlock);
 395   }
 396
 397
 398   /* STEP 3:
 399   ** Loop through the entire memory pool.  Coalesce adjacent free
 400   ** chunks.  Recompute the master chunk as the largest free chunk.
 401   ** Then try again to satisfy the allocation by carving a piece off
 402   ** of the end of the master chunk.  This step happens very
 403   ** rarely (we hope!)
 404   */
 405   for(toFree=nBlock*16; toFree<(mem3.nPool*16); toFree *= 2){
 406     memsys3OutOfMemory(toFree);
 407     if( mem3.iMaster ){
 408       memsys3Link(mem3.iMaster);
 409       mem3.iMaster = 0;
 410       mem3.szMaster = 0;
 411     }
 412     for(i=0; i<N_HASH; i++){
 413       memsys3Merge(&mem3.aiHash[i]);
 414     }
 415     for(i=0; i<MX_SMALL-1; i++){
 416       memsys3Merge(&mem3.aiSmall[i]);
 417     }
 418     if( mem3.szMaster ){
 419       memsys3Unlink(mem3.iMaster);
 420       if( mem3.szMaster>=nBlock ){
 421         return memsys3FromMaster(nBlock);
 422       }
 423     }
 424   }
 425
 426   /* If none of the above worked, then we fail. */
 427   return 0;
 428 }
 429
 430 /*
 431 ** Free an outstanding memory allocation.
 432 **
 433 ** This function assumes that the necessary mutexes, if any, are
 434 ** already held by the caller. Hence "Unsafe".
 435 */
 436 static void memsys3FreeUnsafe(void *pOld){
 437   Mem3Block *p = (Mem3Block*)pOld;
 438   int i;
 439   u32 size, x;
 440   assert( sqlite3_mutex_held(mem3.mutex) );
 441   assert( p>mem3.aPool && p<&mem3.aPool[mem3.nPool] );
 442   i = p - mem3.aPool;
 443   assert( (mem3.aPool[i-1].u.hdr.size4x&1)==1 );
 444   size = mem3.aPool[i-1].u.hdr.size4x/4;
 445   assert( i+size<=mem3.nPool+1 );
 446   mem3.aPool[i-1].u.hdr.size4x &= ~1;
 447   mem3.aPool[i+size-1].u.hdr.prevSize = size;
 448   mem3.aPool[i+size-1].u.hdr.size4x &= ~2;
 449   memsys3Link(i);
 450
 451   /* Try to expand the master using the newly freed chunk */
 452   if( mem3.iMaster ){
 453     while( (mem3.aPool[mem3.iMaster-1].u.hdr.size4x&2)==0 ){
 454       size = mem3.aPool[mem3.iMaster-1].u.hdr.prevSize;
 455       mem3.iMaster -= size;
 456       mem3.szMaster += size;
 457       memsys3Unlink(mem3.iMaster);
 458       x = mem3.aPool[mem3.iMaster-1].u.hdr.size4x & 2;
 459       mem3.aPool[mem3.iMaster-1].u.hdr.size4x = mem3.szMaster*4 | x;
 460       mem3.aPool[mem3.iMaster+mem3.szMaster-1].u.hdr.prevSize = mem3.szMaster;
 461     }
 462     x = mem3.aPool[mem3.iMaster-1].u.hdr.size4x & 2;
 463     while( (mem3.aPool[mem3.iMaster+mem3.szMaster-1].u.hdr.size4x&1)==0 ){
 464       memsys3Unlink(mem3.iMaster+mem3.szMaster);
 465       mem3.szMaster += mem3.aPool[mem3.iMaster+mem3.szMaster-1].u.hdr.size4x/4;
 466       mem3.aPool[mem3.iMaster-1].u.hdr.size4x = mem3.szMaster*4 | x;
 467       mem3.aPool[mem3.iMaster+mem3.szMaster-1].u.hdr.prevSize = mem3.szMaster;
 468     }
 469   }
 470 }
 471
 472 /*
 473 ** Return the size of an outstanding allocation, in bytes.  The
 474 ** size returned omits the 8-byte header overhead.  This only
 475 ** works for chunks that are currently checked out.
 476 */
 477 static int memsys3Size(void *p){
 478   Mem3Block *pBlock;
 479   assert( p!=0 );
 480   pBlock = (Mem3Block*)p;
 481   assert( (pBlock[-1].u.hdr.size4x&1)!=0 );
 482   return (pBlock[-1].u.hdr.size4x&~3)*2 - 4;
 483 }
 484
 485 /*
 486 ** Round up a request size to the next valid allocation size.
 487 */
 488 static int memsys3Roundup(int n){
 489   if( n<=12 ){
 490     return 12;
 491   }else{
 492     return ((n+11)&~7) - 4;
 493   }
 494 }
 495
 496 /*
 497 ** Allocate nBytes of memory.
 498 */
 499 static void *memsys3Malloc(int nBytes){
 500   sqlite3_int64 *p;
 501   assert( nBytes>0 );          /* malloc.c filters out 0 byte requests */
 502   memsys3Enter();
 503   p = memsys3MallocUnsafe(nBytes);
 504   memsys3Leave();
 505   return (void*)p;
 506 }
 507
 508 /*
 509 ** Free memory.
 510 */
 511 static void memsys3Free(void *pPrior){
 512   assert( pPrior );
 513   memsys3Enter();
 514   memsys3FreeUnsafe(pPrior);
 515   memsys3Leave();
 516 }
 517
 518 /*
 519 ** Change the size of an existing memory allocation
 520 */
 521 static void *memsys3Realloc(void *pPrior, int nBytes){
 522   int nOld;
 523   void *p;
 524   if( pPrior==0 ){
 525     return sqlite3_malloc(nBytes);
 526   }
 527   if( nBytes<=0 ){
 528     sqlite3_free(pPrior);
 529     return 0;
 530   }
 531   nOld = memsys3Size(pPrior);
 532   if( nBytes<=nOld && nBytes>=nOld-128 ){
 533     return pPrior;
 534   }
 535   memsys3Enter();
 536   p = memsys3MallocUnsafe(nBytes);
 537   if( p ){
 538     if( nOld<nBytes ){
 539       memcpy(p, pPrior, nOld);
 540     }else{
 541       memcpy(p, pPrior, nBytes);
 542     }
 543     memsys3FreeUnsafe(pPrior);
 544   }
 545   memsys3Leave();
 546   return p;
 547 }
 548
 549 /*
 550 ** Initialize this module.
 551 */
 552 static int memsys3Init(void *NotUsed){
 553   UNUSED_PARAMETER(NotUsed);
 554   if( !sqlite3GlobalConfig.pHeap ){
 555     return SQLITE_ERROR;
 556   }
 557
 558   /* Store a pointer to the memory block in global structure mem3. */
 559   assert( sizeof(Mem3Block)==8 );
 560   mem3.aPool = (Mem3Block *)sqlite3GlobalConfig.pHeap;
 561   mem3.nPool = (sqlite3GlobalConfig.nHeap / sizeof(Mem3Block)) - 2;
 562
 563   /* Initialize the master block. */
 564   mem3.szMaster = mem3.nPool;
 565   mem3.mnMaster = mem3.szMaster;
 566   mem3.iMaster = 1;
 567   mem3.aPool[0].u.hdr.size4x = (mem3.szMaster<<2) + 2;
 568   mem3.aPool[mem3.nPool].u.hdr.prevSize = mem3.nPool;
 569   mem3.aPool[mem3.nPool].u.hdr.size4x = 1;
 570
 571   return SQLITE_OK;
 572 }
 573
 574 /*
 575 ** Deinitialize this module.
 576 */
 577 static void memsys3Shutdown(void *NotUsed){
 578   UNUSED_PARAMETER(NotUsed);
 579   mem3.mutex = 0;
 580   return;
 581 }
 582
 583
 584
 585 /*
 586 ** Open the file indicated and write a log of all unfreed memory
 587 ** allocations into that log.
 588 */
 589 void sqlite3Memsys3Dump(const char *zFilename){
 590 #ifdef SQLITE_DEBUG
 591   FILE *out;
 592   u32 i, j;
 593   u32 size;
 594   if( zFilename==0 || zFilename[0]==0 ){
 595     out = stdout;
 596   }else{
 597     out = fopen(zFilename, "w");
 598     if( out==0 ){
 599       fprintf(stderr, "** Unable to output memory debug output log: %s **\n",
 600                       zFilename);
 601       return;
 602     }
 603   }
 604   memsys3Enter();
 605   fprintf(out, "CHUNKS:\n");
 606   for(i=1; i<=mem3.nPool; i+=size/4){
 607     size = mem3.aPool[i-1].u.hdr.size4x;
 608     if( size/4<=1 ){
 609       fprintf(out, "%p size error\n", &mem3.aPool[i]);
 610       assert( 0 );
 611       break;
 612     }
 613     if( (size&1)==0 && mem3.aPool[i+size/4-1].u.hdr.prevSize!=size/4 ){
 614       fprintf(out, "%p tail size does not match\n", &mem3.aPool[i]);
 615       assert( 0 );
 616       break;
 617     }
 618     if( ((mem3.aPool[i+size/4-1].u.hdr.size4x&2)>>1)!=(size&1) ){
 619       fprintf(out, "%p tail checkout bit is incorrect\n", &mem3.aPool[i]);
 620       assert( 0 );
 621       break;
 622     }
 623     if( size&1 ){
 624       fprintf(out, "%p %6d bytes checked out\n", &mem3.aPool[i], (size/4)*8-8);
 625     }else{
 626       fprintf(out, "%p %6d bytes free%s\n", &mem3.aPool[i], (size/4)*8-8,
 627                   i==mem3.iMaster ? " **master**" : "");
 628     }
 629   }
 630   for(i=0; i<MX_SMALL-1; i++){
 631     if( mem3.aiSmall[i]==0 ) continue;
 632     fprintf(out, "small(%2d):", i);
 633     for(j = mem3.aiSmall[i]; j>0; j=mem3.aPool[j].u.list.next){
 634       fprintf(out, " %p(%d)", &mem3.aPool[j],
 635               (mem3.aPool[j-1].u.hdr.size4x/4)*8-8);
 636     }
 637     fprintf(out, "\n");
 638   }
 639   for(i=0; i<N_HASH; i++){
 640     if( mem3.aiHash[i]==0 ) continue;
 641     fprintf(out, "hash(%2d):", i);
 642     for(j = mem3.aiHash[i]; j>0; j=mem3.aPool[j].u.list.next){
 643       fprintf(out, " %p(%d)", &mem3.aPool[j],
 644               (mem3.aPool[j-1].u.hdr.size4x/4)*8-8);
 645     }
 646     fprintf(out, "\n");
 647   }
 648   fprintf(out, "master=%d\n", mem3.iMaster);
 649   fprintf(out, "nowUsed=%d\n", mem3.nPool*8 - mem3.szMaster*8);
 650   fprintf(out, "mxUsed=%d\n", mem3.nPool*8 - mem3.mnMaster*8);
 651   sqlite3_mutex_leave(mem3.mutex);
 652   if( out==stdout ){
 653     fflush(stdout);
 654   }else{
 655     fclose(out);
 656   }
 657 #else
 658   UNUSED_PARAMETER(zFilename);
 659 #endif
 660 }
 661
 662 /*
 663 ** This routine is the only routine in this file with external
 664 ** linkage.
 665 **
 666 ** Populate the low-level memory allocation function pointers in
 667 ** sqlite3GlobalConfig.m with pointers to the routines in this file. The
 668 ** arguments specify the block of memory to manage.
 669 **
 670 ** This routine is only called by sqlite3_config(), and therefore
 671 ** is not required to be threadsafe (it is not).
 672 */
 673 const sqlite3_mem_methods *sqlite3MemGetMemsys3(void){
 674   static const sqlite3_mem_methods mempoolMethods = {
 675      memsys3Malloc,
 676      memsys3Free,
 677      memsys3Realloc,
 678      memsys3Size,
 679      memsys3Roundup,
 680      memsys3Init,
 681      memsys3Shutdown,
 682      0
 683   };
 684   return &mempoolMethods;
 685 }
 686
 687 #endif /* SQLITE_ENABLE_MEMSYS3 */