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