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