src/pcache1.c

   1 /*
   2 ** 2008 November 05
   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 implements the default page cache implementation (the
  14 ** sqlite3_pcache interface). It also contains part of the implementation
  15 ** of the SQLITE_CONFIG_PAGECACHE and sqlite3_release_memory() features.
  16 ** If the default page cache implementation is overridden, then neither of
  17 ** these two features are available.
  18 **
  19 ** A Page cache line looks like this:
  20 **
  21 **  -------------------------------------------------------------
  22 **  |  database page content   |  PgHdr1  |  MemPage  |  PgHdr  |
  23 **  -------------------------------------------------------------
  24 **
  25 ** The database page content is up front (so that buffer overreads tend to
  26 ** flow harmlessly into the PgHdr1, MemPage, and PgHdr extensions).   MemPage
  27 ** is the extension added by the btree.c module containing information such
  28 ** as the database page number and how that database page is used.  PgHdr
  29 ** is added by the pcache.c layer and contains information used to keep track
  30 ** of which pages are "dirty".  PgHdr1 is an extension added by this
  31 ** module (pcache1.c).  The PgHdr1 header is a subclass of sqlite3_pcache_page.
  32 ** PgHdr1 contains information needed to look up a page by its page number.
  33 ** The superclass sqlite3_pcache_page.pBuf points to the start of the
  34 ** database page content and sqlite3_pcache_page.pExtra points to PgHdr.
  35 **
  36 ** The size of the extension (MemPage+PgHdr+PgHdr1) can be determined at
  37 ** runtime using sqlite3_config(SQLITE_CONFIG_PCACHE_HDRSZ, &size).  The
  38 ** sizes of the extensions sum to 272 bytes on x64 for 3.8.10, but this
  39 ** size can vary according to architecture, compile-time options, and
  40 ** SQLite library version number.
  41 **
  42 ** If SQLITE_PCACHE_SEPARATE_HEADER is defined, then the extension is obtained
  43 ** using a separate memory allocation from the database page content.  This
  44 ** seeks to overcome the "clownshoe" problem (also called "internal
  45 ** fragmentation" in academic literature) of allocating a few bytes more
  46 ** than a power of two with the memory allocator rounding up to the next
  47 ** power of two, and leaving the rounded-up space unused.
  48 **
  49 ** This module tracks pointers to PgHdr1 objects.  Only pcache.c communicates
  50 ** with this module.  Information is passed back and forth as PgHdr1 pointers.
  51 **
  52 ** The pcache.c and pager.c modules deal pointers to PgHdr objects.
  53 ** The btree.c module deals with pointers to MemPage objects.
  54 **
  55 ** SOURCE OF PAGE CACHE MEMORY:
  56 **
  57 ** Memory for a page might come from any of three sources:
  58 **
  59 **    (1)  The general-purpose memory allocator - sqlite3Malloc()
  60 **    (2)  Global page-cache memory provided using sqlite3_config() with
  61 **         SQLITE_CONFIG_PAGECACHE.
  62 **    (3)  PCache-local bulk allocation.
  63 **
  64 ** The third case is a chunk of heap memory (defaulting to 100 pages worth)
  65 ** that is allocated when the page cache is created.  The size of the local
  66 ** bulk allocation can be adjusted using
  67 **
  68 **     sqlite3_config(SQLITE_CONFIG_PAGECACHE, (void*)0, 0, N).
  69 **
  70 ** If N is positive, then N pages worth of memory are allocated using a single
  71 ** sqlite3Malloc() call and that memory is used for the first N pages allocated.
  72 ** Or if N is negative, then -1024*N bytes of memory are allocated and used
  73 ** for as many pages as can be accomodated.
  74 **
  75 ** Only one of (2) or (3) can be used.  Once the memory available to (2) or
  76 ** (3) is exhausted, subsequent allocations fail over to the general-purpose
  77 ** memory allocator (1).
  78 **
  79 ** Earlier versions of SQLite used only methods (1) and (2).  But experiments
  80 ** show that method (3) with N==100 provides about a 5% performance boost for
  81 ** common workloads.
  82 */
  83 #include "sqliteInt.h"
  84
  85 typedef struct PCache1 PCache1;
  86 typedef struct PgHdr1 PgHdr1;
  87 typedef struct PgFreeslot PgFreeslot;
  88 typedef struct PGroup PGroup;
  89
  90 /*
  91 ** Each cache entry is represented by an instance of the following
  92 ** structure. Unless SQLITE_PCACHE_SEPARATE_HEADER is defined, a buffer of
  93 ** PgHdr1.pCache->szPage bytes is allocated directly before this structure
  94 ** in memory.
  95 */
  96 struct PgHdr1 {
  97   sqlite3_pcache_page page;      /* Base class. Must be first. pBuf & pExtra */
  98   unsigned int iKey;             /* Key value (page number) */
  99   u8 isPinned;                   /* Page in use, not on the LRU list */
 100   u8 isBulkLocal;                /* This page from bulk local storage */
 101   u8 isAnchor;                   /* This is the PGroup.lru element */
 102   PgHdr1 *pNext;                 /* Next in hash table chain */
 103   PCache1 *pCache;               /* Cache that currently owns this page */
 104   PgHdr1 *pLruNext;              /* Next in LRU list of unpinned pages */
 105   PgHdr1 *pLruPrev;              /* Previous in LRU list of unpinned pages */
 106 };
 107
 108 /* Each page cache (or PCache) belongs to a PGroup.  A PGroup is a set
 109 ** of one or more PCaches that are able to recycle each other's unpinned
 110 ** pages when they are under memory pressure.  A PGroup is an instance of
 111 ** the following object.
 112 **
 113 ** This page cache implementation works in one of two modes:
 114 **
 115 **   (1)  Every PCache is the sole member of its own PGroup.  There is
 116 **        one PGroup per PCache.
 117 **
 118 **   (2)  There is a single global PGroup that all PCaches are a member
 119 **        of.
 120 **
 121 ** Mode 1 uses more memory (since PCache instances are not able to rob
 122 ** unused pages from other PCaches) but it also operates without a mutex,
 123 ** and is therefore often faster.  Mode 2 requires a mutex in order to be
 124 ** threadsafe, but recycles pages more efficiently.
 125 **
 126 ** For mode (1), PGroup.mutex is NULL.  For mode (2) there is only a single
 127 ** PGroup which is the pcache1.grp global variable and its mutex is
 128 ** SQLITE_MUTEX_STATIC_LRU.
 129 */
 130 struct PGroup {
 131   sqlite3_mutex *mutex;          /* MUTEX_STATIC_LRU or NULL */
 132   unsigned int nMaxPage;         /* Sum of nMax for purgeable caches */
 133   unsigned int nMinPage;         /* Sum of nMin for purgeable caches */
 134   unsigned int mxPinned;         /* nMaxpage + 10 - nMinPage */
 135   unsigned int nCurrentPage;     /* Number of purgeable pages allocated */
 136   PgHdr1 lru;                    /* The beginning and end of the LRU list */
 137 };
 138
 139 /* Each page cache is an instance of the following object.  Every
 140 ** open database file (including each in-memory database and each
 141 ** temporary or transient database) has a single page cache which
 142 ** is an instance of this object.
 143 **
 144 ** Pointers to structures of this type are cast and returned as
 145 ** opaque sqlite3_pcache* handles.
 146 */
 147 struct PCache1 {
 148   /* Cache configuration parameters. Page size (szPage) and the purgeable
 149   ** flag (bPurgeable) are set when the cache is created. nMax may be
 150   ** modified at any time by a call to the pcache1Cachesize() method.
 151   ** The PGroup mutex must be held when accessing nMax.
 152   */
 153   PGroup *pGroup;                     /* PGroup this cache belongs to */
 154   int szPage;                         /* Size of database content section */
 155   int szExtra;                        /* sizeof(MemPage)+sizeof(PgHdr) */
 156   int szAlloc;                        /* Total size of one pcache line */
 157   int bPurgeable;                     /* True if cache is purgeable */
 158   unsigned int nMin;                  /* Minimum number of pages reserved */
 159   unsigned int nMax;                  /* Configured "cache_size" value */
 160   unsigned int n90pct;                /* nMax*9/10 */
 161   unsigned int iMaxKey;               /* Largest key seen since xTruncate() */
 162
 163   /* Hash table of all pages. The following variables may only be accessed
 164   ** when the accessor is holding the PGroup mutex.
 165   */
 166   unsigned int nRecyclable;           /* Number of pages in the LRU list */
 167   unsigned int nPage;                 /* Total number of pages in apHash */
 168   unsigned int nHash;                 /* Number of slots in apHash[] */
 169   PgHdr1 **apHash;                    /* Hash table for fast lookup by key */
 170   PgHdr1 *pFree;                      /* List of unused pcache-local pages */
 171   void *pBulk;                        /* Bulk memory used by pcache-local */
 172 };
 173
 174 /*
 175 ** Free slots in the allocator used to divide up the global page cache
 176 ** buffer provided using the SQLITE_CONFIG_PAGECACHE mechanism.
 177 */
 178 struct PgFreeslot {
 179   PgFreeslot *pNext;  /* Next free slot */
 180 };
 181
 182 /*
 183 ** Global data used by this cache.
 184 */
 185 static SQLITE_WSD struct PCacheGlobal {
 186   PGroup grp;                    /* The global PGroup for mode (2) */
 187
 188   /* Variables related to SQLITE_CONFIG_PAGECACHE settings.  The
 189   ** szSlot, nSlot, pStart, pEnd, nReserve, and isInit values are all
 190   ** fixed at sqlite3_initialize() time and do not require mutex protection.
 191   ** The nFreeSlot and pFree values do require mutex protection.
 192   */
 193   int isInit;                    /* True if initialized */
 194   int separateCache;             /* Use a new PGroup for each PCache */
 195   int nInitPage;                 /* Initial bulk allocation size */
 196   int szSlot;                    /* Size of each free slot */
 197   int nSlot;                     /* The number of pcache slots */
 198   int nReserve;                  /* Try to keep nFreeSlot above this */
 199   void *pStart, *pEnd;           /* Bounds of global page cache memory */
 200   /* Above requires no mutex.  Use mutex below for variable that follow. */
 201   sqlite3_mutex *mutex;          /* Mutex for accessing the following: */
 202   PgFreeslot *pFree;             /* Free page blocks */
 203   int nFreeSlot;                 /* Number of unused pcache slots */
 204   /* The following value requires a mutex to change.  We skip the mutex on
 205   ** reading because (1) most platforms read a 32-bit integer atomically and
 206   ** (2) even if an incorrect value is read, no great harm is done since this
 207   ** is really just an optimization. */
 208   int bUnderPressure;            /* True if low on PAGECACHE memory */
 209 } pcache1_g;
 210
 211 /*
 212 ** All code in this file should access the global structure above via the
 213 ** alias "pcache1". This ensures that the WSD emulation is used when
 214 ** compiling for systems that do not support real WSD.
 215 */
 216 #define pcache1 (GLOBAL(struct PCacheGlobal, pcache1_g))
 217
 218 /*
 219 ** Macros to enter and leave the PCache LRU mutex.
 220 */
 221 #if !defined(SQLITE_ENABLE_MEMORY_MANAGEMENT) || SQLITE_THREADSAFE==0
 222 # define pcache1EnterMutex(X)  assert((X)->mutex==0)
 223 # define pcache1LeaveMutex(X)  assert((X)->mutex==0)
 224 # define PCACHE1_MIGHT_USE_GROUP_MUTEX 0
 225 #else
 226 # define pcache1EnterMutex(X) sqlite3_mutex_enter((X)->mutex)
 227 # define pcache1LeaveMutex(X) sqlite3_mutex_leave((X)->mutex)
 228 # define PCACHE1_MIGHT_USE_GROUP_MUTEX 1
 229 #endif
 230
 231 /******************************************************************************/
 232 /******** Page Allocation/SQLITE_CONFIG_PCACHE Related Functions **************/
 233
 234
 235 /*
 236 ** This function is called during initialization if a static buffer is
 237 ** supplied to use for the page-cache by passing the SQLITE_CONFIG_PAGECACHE
 238 ** verb to sqlite3_config(). Parameter pBuf points to an allocation large
 239 ** enough to contain 'n' buffers of 'sz' bytes each.
 240 **
 241 ** This routine is called from sqlite3_initialize() and so it is guaranteed
 242 ** to be serialized already.  There is no need for further mutexing.
 243 */
 244 void sqlite3PCacheBufferSetup(void *pBuf, int sz, int n){
 245   if( pcache1.isInit ){
 246     PgFreeslot *p;
 247     if( pBuf==0 ) sz = n = 0;
 248     sz = ROUNDDOWN8(sz);
 249     pcache1.szSlot = sz;
 250     pcache1.nSlot = pcache1.nFreeSlot = n;
 251     pcache1.nReserve = n>90 ? 10 : (n/10 + 1);
 252     pcache1.pStart = pBuf;
 253     pcache1.pFree = 0;
 254     pcache1.bUnderPressure = 0;
 255     while( n-- ){
 256       p = (PgFreeslot*)pBuf;
 257       p->pNext = pcache1.pFree;
 258       pcache1.pFree = p;
 259       pBuf = (void*)&((char*)pBuf)[sz];
 260     }
 261     pcache1.pEnd = pBuf;
 262   }
 263 }
 264
 265 /*
 266 ** Try to initialize the pCache->pFree and pCache->pBulk fields.  Return
 267 ** true if pCache->pFree ends up containing one or more free pages.
 268 */
 269 static int pcache1InitBulk(PCache1 *pCache){
 270   i64 szBulk;
 271   char *zBulk;
 272   if( pcache1.nInitPage==0 ) return 0;
 273   /* Do not bother with a bulk allocation if the cache size very small */
 274   if( pCache->nMax<3 ) return 0;
 275   sqlite3BeginBenignMalloc();
 276   if( pcache1.nInitPage>0 ){
 277     szBulk = pCache->szAlloc * (i64)pcache1.nInitPage;
 278   }else{
 279     szBulk = -1024 * (i64)pcache1.nInitPage;
 280   }
 281   if( szBulk > pCache->szAlloc*(i64)pCache->nMax ){
 282     szBulk = pCache->szAlloc*pCache->nMax;
 283   }
 284   zBulk = pCache->pBulk = sqlite3Malloc( szBulk );
 285   sqlite3EndBenignMalloc();
 286   if( zBulk ){
 287     int nBulk = sqlite3MallocSize(zBulk)/pCache->szAlloc;
 288     int i;
 289     for(i=0; i<nBulk; i++){
 290       PgHdr1 *pX = (PgHdr1*)&zBulk[pCache->szPage];
 291       pX->page.pBuf = zBulk;
 292       pX->page.pExtra = &pX[1];
 293       pX->isBulkLocal = 1;
 294       pX->isAnchor = 0;
 295       pX->pNext = pCache->pFree;
 296       pCache->pFree = pX;
 297       zBulk += pCache->szAlloc;
 298     }
 299   }
 300   return pCache->pFree!=0;
 301 }
 302
 303 /*
 304 ** Malloc function used within this file to allocate space from the buffer
 305 ** configured using sqlite3_config(SQLITE_CONFIG_PAGECACHE) option. If no
 306 ** such buffer exists or there is no space left in it, this function falls
 307 ** back to sqlite3Malloc().
 308 **
 309 ** Multiple threads can run this routine at the same time.  Global variables
 310 ** in pcache1 need to be protected via mutex.
 311 */
 312 static void *pcache1Alloc(int nByte){
 313   void *p = 0;
 314   assert( sqlite3_mutex_notheld(pcache1.grp.mutex) );
 315   if( nByte<=pcache1.szSlot ){
 316     sqlite3_mutex_enter(pcache1.mutex);
 317     p = (PgHdr1 *)pcache1.pFree;
 318     if( p ){
 319       pcache1.pFree = pcache1.pFree->pNext;
 320       pcache1.nFreeSlot--;
 321       pcache1.bUnderPressure = pcache1.nFreeSlot<pcache1.nReserve;
 322       assert( pcache1.nFreeSlot>=0 );
 323       sqlite3StatusHighwater(SQLITE_STATUS_PAGECACHE_SIZE, nByte);
 324       sqlite3StatusUp(SQLITE_STATUS_PAGECACHE_USED, 1);
 325     }
 326     sqlite3_mutex_leave(pcache1.mutex);
 327   }
 328   if( p==0 ){
 329     /* Memory is not available in the SQLITE_CONFIG_PAGECACHE pool.  Get
 330     ** it from sqlite3Malloc instead.
 331     */
 332     p = sqlite3Malloc(nByte);
 333 #ifndef SQLITE_DISABLE_PAGECACHE_OVERFLOW_STATS
 334     if( p ){
 335       int sz = sqlite3MallocSize(p);
 336       sqlite3_mutex_enter(pcache1.mutex);
 337       sqlite3StatusHighwater(SQLITE_STATUS_PAGECACHE_SIZE, nByte);
 338       sqlite3StatusUp(SQLITE_STATUS_PAGECACHE_OVERFLOW, sz);
 339       sqlite3_mutex_leave(pcache1.mutex);
 340     }
 341 #endif
 342     sqlite3MemdebugSetType(p, MEMTYPE_PCACHE);
 343   }
 344   return p;
 345 }
 346
 347 /*
 348 ** Free an allocated buffer obtained from pcache1Alloc().
 349 */
 350 static void pcache1Free(void *p){
 351   if( p==0 ) return;
 352   if( SQLITE_WITHIN(p, pcache1.pStart, pcache1.pEnd) ){
 353     PgFreeslot *pSlot;
 354     sqlite3_mutex_enter(pcache1.mutex);
 355     sqlite3StatusDown(SQLITE_STATUS_PAGECACHE_USED, 1);
 356     pSlot = (PgFreeslot*)p;
 357     pSlot->pNext = pcache1.pFree;
 358     pcache1.pFree = pSlot;
 359     pcache1.nFreeSlot++;
 360     pcache1.bUnderPressure = pcache1.nFreeSlot<pcache1.nReserve;
 361     assert( pcache1.nFreeSlot<=pcache1.nSlot );
 362     sqlite3_mutex_leave(pcache1.mutex);
 363   }else{
 364     assert( sqlite3MemdebugHasType(p, MEMTYPE_PCACHE) );
 365     sqlite3MemdebugSetType(p, MEMTYPE_HEAP);
 366 #ifndef SQLITE_DISABLE_PAGECACHE_OVERFLOW_STATS
 367     {
 368       int nFreed = 0;
 369       nFreed = sqlite3MallocSize(p);
 370       sqlite3_mutex_enter(pcache1.mutex);
 371       sqlite3StatusDown(SQLITE_STATUS_PAGECACHE_OVERFLOW, nFreed);
 372       sqlite3_mutex_leave(pcache1.mutex);
 373     }
 374 #endif
 375     sqlite3_free(p);
 376   }
 377 }
 378
 379 #ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
 380 /*
 381 ** Return the size of a pcache allocation
 382 */
 383 static int pcache1MemSize(void *p){
 384   if( p>=pcache1.pStart && p<pcache1.pEnd ){
 385     return pcache1.szSlot;
 386   }else{
 387     int iSize;
 388     assert( sqlite3MemdebugHasType(p, MEMTYPE_PCACHE) );
 389     sqlite3MemdebugSetType(p, MEMTYPE_HEAP);
 390     iSize = sqlite3MallocSize(p);
 391     sqlite3MemdebugSetType(p, MEMTYPE_PCACHE);
 392     return iSize;
 393   }
 394 }
 395 #endif /* SQLITE_ENABLE_MEMORY_MANAGEMENT */
 396
 397 /*
 398 ** Allocate a new page object initially associated with cache pCache.
 399 */
 400 static PgHdr1 *pcache1AllocPage(PCache1 *pCache, int benignMalloc){
 401   PgHdr1 *p = 0;
 402   void *pPg;
 403
 404   assert( sqlite3_mutex_held(pCache->pGroup->mutex) );
 405   if( pCache->pFree || (pCache->nPage==0 && pcache1InitBulk(pCache)) ){
 406     p = pCache->pFree;
 407     pCache->pFree = p->pNext;
 408     p->pNext = 0;
 409   }else{
 410 #ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
 411     /* The group mutex must be released before pcache1Alloc() is called. This
 412     ** is because it might call sqlite3_release_memory(), which assumes that
 413     ** this mutex is not held. */
 414     assert( pcache1.separateCache==0 );
 415     assert( pCache->pGroup==&pcache1.grp );
 416     pcache1LeaveMutex(pCache->pGroup);
 417 #endif
 418     if( benignMalloc ){ sqlite3BeginBenignMalloc(); }
 419 #ifdef SQLITE_PCACHE_SEPARATE_HEADER
 420     pPg = pcache1Alloc(pCache->szPage);
 421     p = sqlite3Malloc(sizeof(PgHdr1) + pCache->szExtra);
 422     if( !pPg || !p ){
 423       pcache1Free(pPg);
 424       sqlite3_free(p);
 425       pPg = 0;
 426     }
 427 #else
 428     pPg = pcache1Alloc(pCache->szAlloc);
 429     p = (PgHdr1 *)&((u8 *)pPg)[pCache->szPage];
 430 #endif
 431     if( benignMalloc ){ sqlite3EndBenignMalloc(); }
 432 #ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
 433     pcache1EnterMutex(pCache->pGroup);
 434 #endif
 435     if( pPg==0 ) return 0;
 436     p->page.pBuf = pPg;
 437     p->page.pExtra = &p[1];
 438     p->isBulkLocal = 0;
 439     p->isAnchor = 0;
 440   }
 441   if( pCache->bPurgeable ){
 442     pCache->pGroup->nCurrentPage++;
 443   }
 444   return p;
 445 }
 446
 447 /*
 448 ** Free a page object allocated by pcache1AllocPage().
 449 */
 450 static void pcache1FreePage(PgHdr1 *p){
 451   PCache1 *pCache;
 452   assert( p!=0 );
 453   pCache = p->pCache;
 454   assert( sqlite3_mutex_held(p->pCache->pGroup->mutex) );
 455   if( p->isBulkLocal ){
 456     p->pNext = pCache->pFree;
 457     pCache->pFree = p;
 458   }else{
 459     pcache1Free(p->page.pBuf);
 460 #ifdef SQLITE_PCACHE_SEPARATE_HEADER
 461     sqlite3_free(p);
 462 #endif
 463   }
 464   if( pCache->bPurgeable ){
 465     pCache->pGroup->nCurrentPage--;
 466   }
 467 }
 468
 469 /*
 470 ** Malloc function used by SQLite to obtain space from the buffer configured
 471 ** using sqlite3_config(SQLITE_CONFIG_PAGECACHE) option. If no such buffer
 472 ** exists, this function falls back to sqlite3Malloc().
 473 */
 474 void *sqlite3PageMalloc(int sz){
 475   return pcache1Alloc(sz);
 476 }
 477
 478 /*
 479 ** Free an allocated buffer obtained from sqlite3PageMalloc().
 480 */
 481 void sqlite3PageFree(void *p){
 482   pcache1Free(p);
 483 }
 484
 485
 486 /*
 487 ** Return true if it desirable to avoid allocating a new page cache
 488 ** entry.
 489 **
 490 ** If memory was allocated specifically to the page cache using
 491 ** SQLITE_CONFIG_PAGECACHE but that memory has all been used, then
 492 ** it is desirable to avoid allocating a new page cache entry because
 493 ** presumably SQLITE_CONFIG_PAGECACHE was suppose to be sufficient
 494 ** for all page cache needs and we should not need to spill the
 495 ** allocation onto the heap.
 496 **
 497 ** Or, the heap is used for all page cache memory but the heap is
 498 ** under memory pressure, then again it is desirable to avoid
 499 ** allocating a new page cache entry in order to avoid stressing
 500 ** the heap even further.
 501 */
 502 static int pcache1UnderMemoryPressure(PCache1 *pCache){
 503   if( pcache1.nSlot && (pCache->szPage+pCache->szExtra)<=pcache1.szSlot ){
 504     return pcache1.bUnderPressure;
 505   }else{
 506     return sqlite3HeapNearlyFull();
 507   }
 508 }
 509
 510 /******************************************************************************/
 511 /******** General Implementation Functions ************************************/
 512
 513 /*
 514 ** This function is used to resize the hash table used by the cache passed
 515 ** as the first argument.
 516 **
 517 ** The PCache mutex must be held when this function is called.
 518 */
 519 static void pcache1ResizeHash(PCache1 *p){
 520   PgHdr1 **apNew;
 521   unsigned int nNew;
 522   unsigned int i;
 523
 524   assert( sqlite3_mutex_held(p->pGroup->mutex) );
 525
 526   nNew = p->nHash*2;
 527   if( nNew<256 ){
 528     nNew = 256;
 529   }
 530
 531   pcache1LeaveMutex(p->pGroup);
 532   if( p->nHash ){ sqlite3BeginBenignMalloc(); }
 533   apNew = (PgHdr1 **)sqlite3MallocZero(sizeof(PgHdr1 *)*nNew);
 534   if( p->nHash ){ sqlite3EndBenignMalloc(); }
 535   pcache1EnterMutex(p->pGroup);
 536   if( apNew ){
 537     for(i=0; i<p->nHash; i++){
 538       PgHdr1 *pPage;
 539       PgHdr1 *pNext = p->apHash[i];
 540       while( (pPage = pNext)!=0 ){
 541         unsigned int h = pPage->iKey % nNew;
 542         pNext = pPage->pNext;
 543         pPage->pNext = apNew[h];
 544         apNew[h] = pPage;
 545       }
 546     }
 547     sqlite3_free(p->apHash);
 548     p->apHash = apNew;
 549     p->nHash = nNew;
 550   }
 551 }
 552
 553 /*
 554 ** This function is used internally to remove the page pPage from the
 555 ** PGroup LRU list, if is part of it. If pPage is not part of the PGroup
 556 ** LRU list, then this function is a no-op.
 557 **
 558 ** The PGroup mutex must be held when this function is called.
 559 */
 560 static PgHdr1 *pcache1PinPage(PgHdr1 *pPage){
 561   PCache1 *pCache;
 562
 563   assert( pPage!=0 );
 564   assert( pPage->isPinned==0 );
 565   pCache = pPage->pCache;
 566   assert( pPage->pLruNext );
 567   assert( pPage->pLruPrev );
 568   assert( sqlite3_mutex_held(pCache->pGroup->mutex) );
 569   pPage->pLruPrev->pLruNext = pPage->pLruNext;
 570   pPage->pLruNext->pLruPrev = pPage->pLruPrev;
 571   pPage->pLruNext = 0;
 572   pPage->pLruPrev = 0;
 573   pPage->isPinned = 1;
 574   assert( pPage->isAnchor==0 );
 575   assert( pCache->pGroup->lru.isAnchor==1 );
 576   pCache->nRecyclable--;
 577   return pPage;
 578 }
 579
 580
 581 /*
 582 ** Remove the page supplied as an argument from the hash table
 583 ** (PCache1.apHash structure) that it is currently stored in.
 584 ** Also free the page if freePage is true.
 585 **
 586 ** The PGroup mutex must be held when this function is called.
 587 */
 588 static void pcache1RemoveFromHash(PgHdr1 *pPage, int freeFlag){
 589   unsigned int h;
 590   PCache1 *pCache = pPage->pCache;
 591   PgHdr1 **pp;
 592
 593   assert( sqlite3_mutex_held(pCache->pGroup->mutex) );
 594   h = pPage->iKey % pCache->nHash;
 595   for(pp=&pCache->apHash[h]; (*pp)!=pPage; pp=&(*pp)->pNext);
 596   *pp = (*pp)->pNext;
 597
 598   pCache->nPage--;
 599   if( freeFlag ) pcache1FreePage(pPage);
 600 }
 601
 602 /*
 603 ** If there are currently more than nMaxPage pages allocated, try
 604 ** to recycle pages to reduce the number allocated to nMaxPage.
 605 */
 606 static void pcache1EnforceMaxPage(PCache1 *pCache){
 607   PGroup *pGroup = pCache->pGroup;
 608   PgHdr1 *p;
 609   assert( sqlite3_mutex_held(pGroup->mutex) );
 610   while( pGroup->nCurrentPage>pGroup->nMaxPage
 611       && (p=pGroup->lru.pLruPrev)->isAnchor==0
 612   ){
 613     assert( p->pCache->pGroup==pGroup );
 614     assert( p->isPinned==0 );
 615     pcache1PinPage(p);
 616     pcache1RemoveFromHash(p, 1);
 617   }
 618   if( pCache->nPage==0 && pCache->pBulk ){
 619     sqlite3_free(pCache->pBulk);
 620     pCache->pBulk = pCache->pFree = 0;
 621   }
 622 }
 623
 624 /*
 625 ** Discard all pages from cache pCache with a page number (key value)
 626 ** greater than or equal to iLimit. Any pinned pages that meet this
 627 ** criteria are unpinned before they are discarded.
 628 **
 629 ** The PCache mutex must be held when this function is called.
 630 */
 631 static void pcache1TruncateUnsafe(
 632   PCache1 *pCache,             /* The cache to truncate */
 633   unsigned int iLimit          /* Drop pages with this pgno or larger */
 634 ){
 635   TESTONLY( unsigned int nPage = 0; )  /* To assert pCache->nPage is correct */
 636   unsigned int h;
 637   assert( sqlite3_mutex_held(pCache->pGroup->mutex) );
 638   for(h=0; h<pCache->nHash; h++){
 639     PgHdr1 **pp = &pCache->apHash[h];
 640     PgHdr1 *pPage;
 641     while( (pPage = *pp)!=0 ){
 642       if( pPage->iKey>=iLimit ){
 643         pCache->nPage--;
 644         *pp = pPage->pNext;
 645         if( !pPage->isPinned ) pcache1PinPage(pPage);
 646         pcache1FreePage(pPage);
 647       }else{
 648         pp = &pPage->pNext;
 649         TESTONLY( nPage++; )
 650       }
 651     }
 652   }
 653   assert( pCache->nPage==nPage );
 654 }
 655
 656 /******************************************************************************/
 657 /******** sqlite3_pcache Methods **********************************************/
 658
 659 /*
 660 ** Implementation of the sqlite3_pcache.xInit method.
 661 */
 662 static int pcache1Init(void *NotUsed){
 663   UNUSED_PARAMETER(NotUsed);
 664   assert( pcache1.isInit==0 );
 665   memset(&pcache1, 0, sizeof(pcache1));
 666
 667
 668   /*
 669   ** The pcache1.separateCache variable is true if each PCache has its own
 670   ** private PGroup (mode-1).  pcache1.separateCache is false if the single
 671   ** PGroup in pcache1.grp is used for all page caches (mode-2).
 672   **
 673   **   *  Always use a unified cache (mode-2) if ENABLE_MEMORY_MANAGEMENT
 674   **
 675   **   *  Use a unified cache in single-threaded applications that have
 676   **      configured a start-time buffer for use as page-cache memory using
 677   **      sqlite3_config(SQLITE_CONFIG_PAGECACHE, pBuf, sz, N) with non-NULL
 678   **      pBuf argument.
 679   **
 680   **   *  Otherwise use separate caches (mode-1)
 681   */
 682 #if defined(SQLITE_ENABLE_MEMORY_MANAGEMENT)
 683   pcache1.separateCache = 0;
 684 #elif SQLITE_THREADSAFE
 685   pcache1.separateCache = sqlite3GlobalConfig.pPage==0
 686                           || sqlite3GlobalConfig.bCoreMutex>0;
 687 #else
 688   pcache1.separateCache = sqlite3GlobalConfig.pPage==0;
 689 #endif
 690
 691 #if SQLITE_THREADSAFE
 692   if( sqlite3GlobalConfig.bCoreMutex ){
 693     pcache1.grp.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_LRU);
 694     pcache1.mutex = sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_PMEM);
 695   }
 696 #endif
 697   if( pcache1.separateCache
 698    && sqlite3GlobalConfig.nPage!=0
 699    && sqlite3GlobalConfig.pPage==0
 700   ){
 701     pcache1.nInitPage = sqlite3GlobalConfig.nPage;
 702   }else{
 703     pcache1.nInitPage = 0;
 704   }
 705   pcache1.grp.mxPinned = 10;
 706   pcache1.isInit = 1;
 707   return SQLITE_OK;
 708 }
 709
 710 /*
 711 ** Implementation of the sqlite3_pcache.xShutdown method.
 712 ** Note that the static mutex allocated in xInit does
 713 ** not need to be freed.
 714 */
 715 static void pcache1Shutdown(void *NotUsed){
 716   UNUSED_PARAMETER(NotUsed);
 717   assert( pcache1.isInit!=0 );
 718   memset(&pcache1, 0, sizeof(pcache1));
 719 }
 720
 721 /* forward declaration */
 722 static void pcache1Destroy(sqlite3_pcache *p);
 723
 724 /*
 725 ** Implementation of the sqlite3_pcache.xCreate method.
 726 **
 727 ** Allocate a new cache.
 728 */
 729 static sqlite3_pcache *pcache1Create(int szPage, int szExtra, int bPurgeable){
 730   PCache1 *pCache;      /* The newly created page cache */
 731   PGroup *pGroup;       /* The group the new page cache will belong to */
 732   int sz;               /* Bytes of memory required to allocate the new cache */
 733
 734   assert( (szPage & (szPage-1))==0 && szPage>=512 && szPage<=65536 );
 735   assert( szExtra < 300 );
 736
 737   sz = sizeof(PCache1) + sizeof(PGroup)*pcache1.separateCache;
 738   pCache = (PCache1 *)sqlite3MallocZero(sz);
 739   if( pCache ){
 740     if( pcache1.separateCache ){
 741       pGroup = (PGroup*)&pCache[1];
 742       pGroup->mxPinned = 10;
 743     }else{
 744       pGroup = &pcache1.grp;
 745     }
 746     if( pGroup->lru.isAnchor==0 ){
 747       pGroup->lru.isAnchor = 1;
 748       pGroup->lru.pLruPrev = pGroup->lru.pLruNext = &pGroup->lru;
 749     }
 750     pCache->pGroup = pGroup;
 751     pCache->szPage = szPage;
 752     pCache->szExtra = szExtra;
 753     pCache->szAlloc = szPage + szExtra + ROUND8(sizeof(PgHdr1));
 754     pCache->bPurgeable = (bPurgeable ? 1 : 0);
 755     pcache1EnterMutex(pGroup);
 756     pcache1ResizeHash(pCache);
 757     if( bPurgeable ){
 758       pCache->nMin = 10;
 759       pGroup->nMinPage += pCache->nMin;
 760       pGroup->mxPinned = pGroup->nMaxPage + 10 - pGroup->nMinPage;
 761     }
 762     pcache1LeaveMutex(pGroup);
 763     if( pCache->nHash==0 ){
 764       pcache1Destroy((sqlite3_pcache*)pCache);
 765       pCache = 0;
 766     }
 767   }
 768   return (sqlite3_pcache *)pCache;
 769 }
 770
 771 /*
 772 ** Implementation of the sqlite3_pcache.xCachesize method.
 773 **
 774 ** Configure the cache_size limit for a cache.
 775 */
 776 static void pcache1Cachesize(sqlite3_pcache *p, int nMax){
 777   PCache1 *pCache = (PCache1 *)p;
 778   if( pCache->bPurgeable ){
 779     PGroup *pGroup = pCache->pGroup;
 780     pcache1EnterMutex(pGroup);
 781     pGroup->nMaxPage += (nMax - pCache->nMax);
 782     pGroup->mxPinned = pGroup->nMaxPage + 10 - pGroup->nMinPage;
 783     pCache->nMax = nMax;
 784     pCache->n90pct = pCache->nMax*9/10;
 785     pcache1EnforceMaxPage(pCache);
 786     pcache1LeaveMutex(pGroup);
 787   }
 788 }
 789
 790 /*
 791 ** Implementation of the sqlite3_pcache.xShrink method.
 792 **
 793 ** Free up as much memory as possible.
 794 */
 795 static void pcache1Shrink(sqlite3_pcache *p){
 796   PCache1 *pCache = (PCache1*)p;
 797   if( pCache->bPurgeable ){
 798     PGroup *pGroup = pCache->pGroup;
 799     int savedMaxPage;
 800     pcache1EnterMutex(pGroup);
 801     savedMaxPage = pGroup->nMaxPage;
 802     pGroup->nMaxPage = 0;
 803     pcache1EnforceMaxPage(pCache);
 804     pGroup->nMaxPage = savedMaxPage;
 805     pcache1LeaveMutex(pGroup);
 806   }
 807 }
 808
 809 /*
 810 ** Implementation of the sqlite3_pcache.xPagecount method.
 811 */
 812 static int pcache1Pagecount(sqlite3_pcache *p){
 813   int n;
 814   PCache1 *pCache = (PCache1*)p;
 815   pcache1EnterMutex(pCache->pGroup);
 816   n = pCache->nPage;
 817   pcache1LeaveMutex(pCache->pGroup);
 818   return n;
 819 }
 820
 821
 822 /*
 823 ** Implement steps 3, 4, and 5 of the pcache1Fetch() algorithm described
 824 ** in the header of the pcache1Fetch() procedure.
 825 **
 826 ** This steps are broken out into a separate procedure because they are
 827 ** usually not needed, and by avoiding the stack initialization required
 828 ** for these steps, the main pcache1Fetch() procedure can run faster.
 829 */
 830 static SQLITE_NOINLINE PgHdr1 *pcache1FetchStage2(
 831   PCache1 *pCache,
 832   unsigned int iKey,
 833   int createFlag
 834 ){
 835   unsigned int nPinned;
 836   PGroup *pGroup = pCache->pGroup;
 837   PgHdr1 *pPage = 0;
 838
 839   /* Step 3: Abort if createFlag is 1 but the cache is nearly full */
 840   assert( pCache->nPage >= pCache->nRecyclable );
 841   nPinned = pCache->nPage - pCache->nRecyclable;
 842   assert( pGroup->mxPinned == pGroup->nMaxPage + 10 - pGroup->nMinPage );
 843   assert( pCache->n90pct == pCache->nMax*9/10 );
 844   if( createFlag==1 && (
 845         nPinned>=pGroup->mxPinned
 846      || nPinned>=pCache->n90pct
 847      || (pcache1UnderMemoryPressure(pCache) && pCache->nRecyclable<nPinned)
 848   )){
 849     return 0;
 850   }
 851
 852   if( pCache->nPage>=pCache->nHash ) pcache1ResizeHash(pCache);
 853   assert( pCache->nHash>0 && pCache->apHash );
 854
 855   /* Step 4. Try to recycle a page. */
 856   if( pCache->bPurgeable
 857    && !pGroup->lru.pLruPrev->isAnchor
 858    && ((pCache->nPage+1>=pCache->nMax) || pcache1UnderMemoryPressure(pCache))
 859   ){
 860     PCache1 *pOther;
 861     pPage = pGroup->lru.pLruPrev;
 862     assert( pPage->isPinned==0 );
 863     pcache1RemoveFromHash(pPage, 0);
 864     pcache1PinPage(pPage);
 865     pOther = pPage->pCache;
 866     if( pOther->szAlloc != pCache->szAlloc ){
 867       pcache1FreePage(pPage);
 868       pPage = 0;
 869     }else{
 870       pGroup->nCurrentPage -= (pOther->bPurgeable - pCache->bPurgeable);
 871     }
 872   }
 873
 874   /* Step 5. If a usable page buffer has still not been found,
 875   ** attempt to allocate a new one.
 876   */
 877   if( !pPage ){
 878     pPage = pcache1AllocPage(pCache, createFlag==1);
 879   }
 880
 881   if( pPage ){
 882     unsigned int h = iKey % pCache->nHash;
 883     pCache->nPage++;
 884     pPage->iKey = iKey;
 885     pPage->pNext = pCache->apHash[h];
 886     pPage->pCache = pCache;
 887     pPage->pLruPrev = 0;
 888     pPage->pLruNext = 0;
 889     pPage->isPinned = 1;
 890     *(void **)pPage->page.pExtra = 0;
 891     pCache->apHash[h] = pPage;
 892     if( iKey>pCache->iMaxKey ){
 893       pCache->iMaxKey = iKey;
 894     }
 895   }
 896   return pPage;
 897 }
 898
 899 /*
 900 ** Implementation of the sqlite3_pcache.xFetch method.
 901 **
 902 ** Fetch a page by key value.
 903 **
 904 ** Whether or not a new page may be allocated by this function depends on
 905 ** the value of the createFlag argument.  0 means do not allocate a new
 906 ** page.  1 means allocate a new page if space is easily available.  2
 907 ** means to try really hard to allocate a new page.
 908 **
 909 ** For a non-purgeable cache (a cache used as the storage for an in-memory
 910 ** database) there is really no difference between createFlag 1 and 2.  So
 911 ** the calling function (pcache.c) will never have a createFlag of 1 on
 912 ** a non-purgeable cache.
 913 **
 914 ** There are three different approaches to obtaining space for a page,
 915 ** depending on the value of parameter createFlag (which may be 0, 1 or 2).
 916 **
 917 **   1. Regardless of the value of createFlag, the cache is searched for a
 918 **      copy of the requested page. If one is found, it is returned.
 919 **
 920 **   2. If createFlag==0 and the page is not already in the cache, NULL is
 921 **      returned.
 922 **
 923 **   3. If createFlag is 1, and the page is not already in the cache, then
 924 **      return NULL (do not allocate a new page) if any of the following
 925 **      conditions are true:
 926 **
 927 **       (a) the number of pages pinned by the cache is greater than
 928 **           PCache1.nMax, or
 929 **
 930 **       (b) the number of pages pinned by the cache is greater than
 931 **           the sum of nMax for all purgeable caches, less the sum of
 932 **           nMin for all other purgeable caches, or
 933 **
 934 **   4. If none of the first three conditions apply and the cache is marked
 935 **      as purgeable, and if one of the following is true:
 936 **
 937 **       (a) The number of pages allocated for the cache is already
 938 **           PCache1.nMax, or
 939 **
 940 **       (b) The number of pages allocated for all purgeable caches is
 941 **           already equal to or greater than the sum of nMax for all
 942 **           purgeable caches,
 943 **
 944 **       (c) The system is under memory pressure and wants to avoid
 945 **           unnecessary pages cache entry allocations
 946 **
 947 **      then attempt to recycle a page from the LRU list. If it is the right
 948 **      size, return the recycled buffer. Otherwise, free the buffer and
 949 **      proceed to step 5.
 950 **
 951 **   5. Otherwise, allocate and return a new page buffer.
 952 **
 953 ** There are two versions of this routine.  pcache1FetchWithMutex() is
 954 ** the general case.  pcache1FetchNoMutex() is a faster implementation for
 955 ** the common case where pGroup->mutex is NULL.  The pcache1Fetch() wrapper
 956 ** invokes the appropriate routine.
 957 */
 958 static PgHdr1 *pcache1FetchNoMutex(
 959   sqlite3_pcache *p,
 960   unsigned int iKey,
 961   int createFlag
 962 ){
 963   PCache1 *pCache = (PCache1 *)p;
 964   PgHdr1 *pPage = 0;
 965
 966   /* Step 1: Search the hash table for an existing entry. */
 967   pPage = pCache->apHash[iKey % pCache->nHash];
 968   while( pPage && pPage->iKey!=iKey ){ pPage = pPage->pNext; }
 969
 970   /* Step 2: If the page was found in the hash table, then return it.
 971   ** If the page was not in the hash table and createFlag is 0, abort.
 972   ** Otherwise (page not in hash and createFlag!=0) continue with
 973   ** subsequent steps to try to create the page. */
 974   if( pPage ){
 975     if( !pPage->isPinned ){
 976       return pcache1PinPage(pPage);
 977     }else{
 978       return pPage;
 979     }
 980   }else if( createFlag ){
 981     /* Steps 3, 4, and 5 implemented by this subroutine */
 982     return pcache1FetchStage2(pCache, iKey, createFlag);
 983   }else{
 984     return 0;
 985   }
 986 }
 987 #if PCACHE1_MIGHT_USE_GROUP_MUTEX
 988 static PgHdr1 *pcache1FetchWithMutex(
 989   sqlite3_pcache *p,
 990   unsigned int iKey,
 991   int createFlag
 992 ){
 993   PCache1 *pCache = (PCache1 *)p;
 994   PgHdr1 *pPage;
 995
 996   pcache1EnterMutex(pCache->pGroup);
 997   pPage = pcache1FetchNoMutex(p, iKey, createFlag);
 998   assert( pPage==0 || pCache->iMaxKey>=iKey );
 999   pcache1LeaveMutex(pCache->pGroup);
1000   return pPage;
1001 }
1002 #endif
1003 static sqlite3_pcache_page *pcache1Fetch(
1004   sqlite3_pcache *p,
1005   unsigned int iKey,
1006   int createFlag
1007 ){
1008 #if PCACHE1_MIGHT_USE_GROUP_MUTEX || defined(SQLITE_DEBUG)
1009   PCache1 *pCache = (PCache1 *)p;
1010 #endif
1011
1012   assert( offsetof(PgHdr1,page)==0 );
1013   assert( pCache->bPurgeable || createFlag!=1 );
1014   assert( pCache->bPurgeable || pCache->nMin==0 );
1015   assert( pCache->bPurgeable==0 || pCache->nMin==10 );
1016   assert( pCache->nMin==0 || pCache->bPurgeable );
1017   assert( pCache->nHash>0 );
1018 #if PCACHE1_MIGHT_USE_GROUP_MUTEX
1019   if( pCache->pGroup->mutex ){
1020     return (sqlite3_pcache_page*)pcache1FetchWithMutex(p, iKey, createFlag);
1021   }else
1022 #endif
1023   {
1024     return (sqlite3_pcache_page*)pcache1FetchNoMutex(p, iKey, createFlag);
1025   }
1026 }
1027
1028
1029 /*
1030 ** Implementation of the sqlite3_pcache.xUnpin method.
1031 **
1032 ** Mark a page as unpinned (eligible for asynchronous recycling).
1033 */
1034 static void pcache1Unpin(
1035   sqlite3_pcache *p,
1036   sqlite3_pcache_page *pPg,
1037   int reuseUnlikely
1038 ){
1039   PCache1 *pCache = (PCache1 *)p;
1040   PgHdr1 *pPage = (PgHdr1 *)pPg;
1041   PGroup *pGroup = pCache->pGroup;
1042
1043   assert( pPage->pCache==pCache );
1044   pcache1EnterMutex(pGroup);
1045
1046   /* It is an error to call this function if the page is already
1047   ** part of the PGroup LRU list.
1048   */
1049   assert( pPage->pLruPrev==0 && pPage->pLruNext==0 );
1050   assert( pPage->isPinned==1 );
1051
1052   if( reuseUnlikely || pGroup->nCurrentPage>pGroup->nMaxPage ){
1053     pcache1RemoveFromHash(pPage, 1);
1054   }else{
1055     /* Add the page to the PGroup LRU list. */
1056     PgHdr1 **ppFirst = &pGroup->lru.pLruNext;
1057     pPage->pLruPrev = &pGroup->lru;
1058     (pPage->pLruNext = *ppFirst)->pLruPrev = pPage;
1059     *ppFirst = pPage;
1060     pCache->nRecyclable++;
1061     pPage->isPinned = 0;
1062   }
1063
1064   pcache1LeaveMutex(pCache->pGroup);
1065 }
1066
1067 /*
1068 ** Implementation of the sqlite3_pcache.xRekey method.
1069 */
1070 static void pcache1Rekey(
1071   sqlite3_pcache *p,
1072   sqlite3_pcache_page *pPg,
1073   unsigned int iOld,
1074   unsigned int iNew
1075 ){
1076   PCache1 *pCache = (PCache1 *)p;
1077   PgHdr1 *pPage = (PgHdr1 *)pPg;
1078   PgHdr1 **pp;
1079   unsigned int h;
1080   assert( pPage->iKey==iOld );
1081   assert( pPage->pCache==pCache );
1082
1083   pcache1EnterMutex(pCache->pGroup);
1084
1085   h = iOld%pCache->nHash;
1086   pp = &pCache->apHash[h];
1087   while( (*pp)!=pPage ){
1088     pp = &(*pp)->pNext;
1089   }
1090   *pp = pPage->pNext;
1091
1092   h = iNew%pCache->nHash;
1093   pPage->iKey = iNew;
1094   pPage->pNext = pCache->apHash[h];
1095   pCache->apHash[h] = pPage;
1096   if( iNew>pCache->iMaxKey ){
1097     pCache->iMaxKey = iNew;
1098   }
1099
1100   pcache1LeaveMutex(pCache->pGroup);
1101 }
1102
1103 /*
1104 ** Implementation of the sqlite3_pcache.xTruncate method.
1105 **
1106 ** Discard all unpinned pages in the cache with a page number equal to
1107 ** or greater than parameter iLimit. Any pinned pages with a page number
1108 ** equal to or greater than iLimit are implicitly unpinned.
1109 */
1110 static void pcache1Truncate(sqlite3_pcache *p, unsigned int iLimit){
1111   PCache1 *pCache = (PCache1 *)p;
1112   pcache1EnterMutex(pCache->pGroup);
1113   if( iLimit<=pCache->iMaxKey ){
1114     pcache1TruncateUnsafe(pCache, iLimit);
1115     pCache->iMaxKey = iLimit-1;
1116   }
1117   pcache1LeaveMutex(pCache->pGroup);
1118 }
1119
1120 /*
1121 ** Implementation of the sqlite3_pcache.xDestroy method.
1122 **
1123 ** Destroy a cache allocated using pcache1Create().
1124 */
1125 static void pcache1Destroy(sqlite3_pcache *p){
1126   PCache1 *pCache = (PCache1 *)p;
1127   PGroup *pGroup = pCache->pGroup;
1128   assert( pCache->bPurgeable || (pCache->nMax==0 && pCache->nMin==0) );
1129   pcache1EnterMutex(pGroup);
1130   pcache1TruncateUnsafe(pCache, 0);
1131   assert( pGroup->nMaxPage >= pCache->nMax );
1132   pGroup->nMaxPage -= pCache->nMax;
1133   assert( pGroup->nMinPage >= pCache->nMin );
1134   pGroup->nMinPage -= pCache->nMin;
1135   pGroup->mxPinned = pGroup->nMaxPage + 10 - pGroup->nMinPage;
1136   pcache1EnforceMaxPage(pCache);
1137   pcache1LeaveMutex(pGroup);
1138   sqlite3_free(pCache->pBulk);
1139   sqlite3_free(pCache->apHash);
1140   sqlite3_free(pCache);
1141 }
1142
1143 /*
1144 ** This function is called during initialization (sqlite3_initialize()) to
1145 ** install the default pluggable cache module, assuming the user has not
1146 ** already provided an alternative.
1147 */
1148 void sqlite3PCacheSetDefault(void){
1149   static const sqlite3_pcache_methods2 defaultMethods = {
1150     1,                       /* iVersion */
1151     0,                       /* pArg */
1152     pcache1Init,             /* xInit */
1153     pcache1Shutdown,         /* xShutdown */
1154     pcache1Create,           /* xCreate */
1155     pcache1Cachesize,        /* xCachesize */
1156     pcache1Pagecount,        /* xPagecount */
1157     pcache1Fetch,            /* xFetch */
1158     pcache1Unpin,            /* xUnpin */
1159     pcache1Rekey,            /* xRekey */
1160     pcache1Truncate,         /* xTruncate */
1161     pcache1Destroy,          /* xDestroy */
1162     pcache1Shrink            /* xShrink */
1163   };
1164   sqlite3_config(SQLITE_CONFIG_PCACHE2, &defaultMethods);
1165 }
1166
1167 /*
1168 ** Return the size of the header on each page of this PCACHE implementation.
1169 */
1170 int sqlite3HeaderSizePcache1(void){ return ROUND8(sizeof(PgHdr1)); }
1171
1172 /*
1173 ** Return the global mutex used by this PCACHE implementation.  The
1174 ** sqlite3_status() routine needs access to this mutex.
1175 */
1176 sqlite3_mutex *sqlite3Pcache1Mutex(void){
1177   return pcache1.mutex;
1178 }
1179
1180 #ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
1181 /*
1182 ** This function is called to free superfluous dynamically allocated memory
1183 ** held by the pager system. Memory in use by any SQLite pager allocated
1184 ** by the current thread may be sqlite3_free()ed.
1185 **
1186 ** nReq is the number of bytes of memory required. Once this much has
1187 ** been released, the function returns. The return value is the total number
1188 ** of bytes of memory released.
1189 */
1190 int sqlite3PcacheReleaseMemory(int nReq){
1191   int nFree = 0;
1192   assert( sqlite3_mutex_notheld(pcache1.grp.mutex) );
1193   assert( sqlite3_mutex_notheld(pcache1.mutex) );
1194   if( sqlite3GlobalConfig.nPage==0 ){
1195     PgHdr1 *p;
1196     pcache1EnterMutex(&pcache1.grp);
1197     while( (nReq<0 || nFree<nReq)
1198        &&  (p=pcache1.grp.lru.pLruPrev)!=0
1199        &&  p->isAnchor==0
1200     ){
1201       nFree += pcache1MemSize(p->page.pBuf);
1202 #ifdef SQLITE_PCACHE_SEPARATE_HEADER
1203       nFree += sqlite3MemSize(p);
1204 #endif
1205       assert( p->isPinned==0 );
1206       pcache1PinPage(p);
1207       pcache1RemoveFromHash(p, 1);
1208     }
1209     pcache1LeaveMutex(&pcache1.grp);
1210   }
1211   return nFree;
1212 }
1213 #endif /* SQLITE_ENABLE_MEMORY_MANAGEMENT */
1214
1215 #ifdef SQLITE_TEST
1216 /*
1217 ** This function is used by test procedures to inspect the internal state
1218 ** of the global cache.
1219 */
1220 void sqlite3PcacheStats(
1221   int *pnCurrent,      /* OUT: Total number of pages cached */
1222   int *pnMax,          /* OUT: Global maximum cache size */
1223   int *pnMin,          /* OUT: Sum of PCache1.nMin for purgeable caches */
1224   int *pnRecyclable    /* OUT: Total number of pages available for recycling */
1225 ){
1226   PgHdr1 *p;
1227   int nRecyclable = 0;
1228   for(p=pcache1.grp.lru.pLruNext; p && !p->isAnchor; p=p->pLruNext){
1229     assert( p->isPinned==0 );
1230     nRecyclable++;
1231   }
1232   *pnCurrent = pcache1.grp.nCurrentPage;
1233   *pnMax = (int)pcache1.grp.nMaxPage;
1234   *pnMin = (int)pcache1.grp.nMinPage;
1235   *pnRecyclable = nRecyclable;
1236 }
1237 #endif