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