src/third_party/sqlite/src/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 overriden, then neither of
  17 ** these two features are available.
  18 */
  19
  20 #include "sqliteInt.h"
  21
  22 typedef struct PCache1 PCache1;
  23 typedef struct PgHdr1 PgHdr1;
  24 typedef struct PgFreeslot PgFreeslot;
  25 typedef struct PGroup PGroup;
  26
  27 /* Each page cache (or PCache) belongs to a PGroup.  A PGroup is a set
  28 ** of one or more PCaches that are able to recycle each others unpinned
  29 ** pages when they are under memory pressure.  A PGroup is an instance of
  30 ** the following object.
  31 **
  32 ** This page cache implementation works in one of two modes:
  33 **
  34 **   (1)  Every PCache is the sole member of its own PGroup.  There is
  35 **        one PGroup per PCache.
  36 **
  37 **   (2)  There is a single global PGroup that all PCaches are a member
  38 **        of.
  39 **
  40 ** Mode 1 uses more memory (since PCache instances are not able to rob
  41 ** unused pages from other PCaches) but it also operates without a mutex,
  42 ** and is therefore often faster.  Mode 2 requires a mutex in order to be
  43 ** threadsafe, but is able recycle pages more efficient.
  44 **
  45 ** For mode (1), PGroup.mutex is NULL.  For mode (2) there is only a single
  46 ** PGroup which is the pcache1.grp global variable and its mutex is
  47 ** SQLITE_MUTEX_STATIC_LRU.
  48 */
  49 struct PGroup {
  50   sqlite3_mutex *mutex;          /* MUTEX_STATIC_LRU or NULL */
  51   int nMaxPage;                  /* Sum of nMax for purgeable caches */
  52   int nMinPage;                  /* Sum of nMin for purgeable caches */
  53   int mxPinned;                  /* nMaxpage + 10 - nMinPage */
  54   int nCurrentPage;              /* Number of purgeable pages allocated */
  55   PgHdr1 *pLruHead, *pLruTail;   /* LRU list of unpinned pages */
  56 };
  57
  58 /* Each page cache is an instance of the following object.  Every
  59 ** open database file (including each in-memory database and each
  60 ** temporary or transient database) has a single page cache which
  61 ** is an instance of this object.
  62 **
  63 ** Pointers to structures of this type are cast and returned as
  64 ** opaque sqlite3_pcache* handles.
  65 */
  66 struct PCache1 {
  67   /* Cache configuration parameters. Page size (szPage) and the purgeable
  68   ** flag (bPurgeable) are set when the cache is created. nMax may be
  69   ** modified at any time by a call to the pcache1CacheSize() method.
  70   ** The PGroup mutex must be held when accessing nMax.
  71   */
  72   PGroup *pGroup;                     /* PGroup this cache belongs to */
  73   int szPage;                         /* Size of allocated pages in bytes */
  74   int bPurgeable;                     /* True if cache is purgeable */
  75   unsigned int nMin;                  /* Minimum number of pages reserved */
  76   unsigned int nMax;                  /* Configured "cache_size" value */
  77   unsigned int n90pct;                /* nMax*9/10 */
  78
  79   /* Hash table of all pages. The following variables may only be accessed
  80   ** when the accessor is holding the PGroup mutex.
  81   */
  82   unsigned int nRecyclable;           /* Number of pages in the LRU list */
  83   unsigned int nPage;                 /* Total number of pages in apHash */
  84   unsigned int nHash;                 /* Number of slots in apHash[] */
  85   PgHdr1 **apHash;                    /* Hash table for fast lookup by key */
  86
  87   unsigned int iMaxKey;               /* Largest key seen since xTruncate() */
  88 };
  89
  90 /*
  91 ** Each cache entry is represented by an instance of the following
  92 ** structure. A buffer of PgHdr1.pCache->szPage bytes is allocated
  93 ** directly before this structure in memory (see the PGHDR1_TO_PAGE()
  94 ** macro below).
  95 */
  96 struct PgHdr1 {
  97   unsigned int iKey;             /* Key value (page number) */
  98   PgHdr1 *pNext;                 /* Next in hash table chain */
  99   PCache1 *pCache;               /* Cache that currently owns this page */
 100   PgHdr1 *pLruNext;              /* Next in LRU list of unpinned pages */
 101   PgHdr1 *pLruPrev;              /* Previous in LRU list of unpinned pages */
 102 };
 103
 104 /*
 105 ** Free slots in the allocator used to divide up the buffer provided using
 106 ** the SQLITE_CONFIG_PAGECACHE mechanism.
 107 */
 108 struct PgFreeslot {
 109   PgFreeslot *pNext;  /* Next free slot */
 110 };
 111
 112 /*
 113 ** Global data used by this cache.
 114 */
 115 static SQLITE_WSD struct PCacheGlobal {
 116   PGroup grp;                    /* The global PGroup for mode (2) */
 117
 118   /* Variables related to SQLITE_CONFIG_PAGECACHE settings.  The
 119   ** szSlot, nSlot, pStart, pEnd, nReserve, and isInit values are all
 120   ** fixed at sqlite3_initialize() time and do not require mutex protection.
 121   ** The nFreeSlot and pFree values do require mutex protection.
 122   */
 123   int isInit;                    /* True if initialized */
 124   int szSlot;                    /* Size of each free slot */
 125   int nSlot;                     /* The number of pcache slots */
 126   int nReserve;                  /* Try to keep nFreeSlot above this */
 127   void *pStart, *pEnd;           /* Bounds of pagecache malloc range */
 128   /* Above requires no mutex.  Use mutex below for variable that follow. */
 129   sqlite3_mutex *mutex;          /* Mutex for accessing the following: */
 130   int nFreeSlot;                 /* Number of unused pcache slots */
 131   PgFreeslot *pFree;             /* Free page blocks */
 132   /* The following value requires a mutex to change.  We skip the mutex on
 133   ** reading because (1) most platforms read a 32-bit integer atomically and
 134   ** (2) even if an incorrect value is read, no great harm is done since this
 135   ** is really just an optimization. */
 136   int bUnderPressure;            /* True if low on PAGECACHE memory */
 137 } pcache1_g;
 138
 139 /*
 140 ** All code in this file should access the global structure above via the
 141 ** alias "pcache1". This ensures that the WSD emulation is used when
 142 ** compiling for systems that do not support real WSD.
 143 */
 144 #define pcache1 (GLOBAL(struct PCacheGlobal, pcache1_g))
 145
 146 /*
 147 ** When a PgHdr1 structure is allocated, the associated PCache1.szPage
 148 ** bytes of data are located directly before it in memory (i.e. the total
 149 ** size of the allocation is sizeof(PgHdr1)+PCache1.szPage byte). The
 150 ** PGHDR1_TO_PAGE() macro takes a pointer to a PgHdr1 structure as
 151 ** an argument and returns a pointer to the associated block of szPage
 152 ** bytes. The PAGE_TO_PGHDR1() macro does the opposite: its argument is
 153 ** a pointer to a block of szPage bytes of data and the return value is
 154 ** a pointer to the associated PgHdr1 structure.
 155 **
 156 **   assert( PGHDR1_TO_PAGE(PAGE_TO_PGHDR1(pCache, X))==X );
 157 */
 158 #define PGHDR1_TO_PAGE(p)    (void*)(((char*)p) - p->pCache->szPage)
 159 #define PAGE_TO_PGHDR1(c, p) (PgHdr1*)(((char*)p) + c->szPage)
 160
 161 /*
 162 ** Macros to enter and leave the PCache LRU mutex.
 163 */
 164 #define pcache1EnterMutex(X) sqlite3_mutex_enter((X)->mutex)
 165 #define pcache1LeaveMutex(X) sqlite3_mutex_leave((X)->mutex)
 166
 167 /******************************************************************************/
 168 /******** Page Allocation/SQLITE_CONFIG_PCACHE Related Functions **************/
 169
 170 /*
 171 ** This function is called during initialization if a static buffer is
 172 ** supplied to use for the page-cache by passing the SQLITE_CONFIG_PAGECACHE
 173 ** verb to sqlite3_config(). Parameter pBuf points to an allocation large
 174 ** enough to contain 'n' buffers of 'sz' bytes each.
 175 **
 176 ** This routine is called from sqlite3_initialize() and so it is guaranteed
 177 ** to be serialized already.  There is no need for further mutexing.
 178 */
 179 void sqlite3PCacheBufferSetup(void *pBuf, int sz, int n){
 180   if( pcache1.isInit ){
 181     PgFreeslot *p;
 182     sz = ROUNDDOWN8(sz);
 183     pcache1.szSlot = sz;
 184     pcache1.nSlot = pcache1.nFreeSlot = n;
 185     pcache1.nReserve = n>90 ? 10 : (n/10 + 1);
 186     pcache1.pStart = pBuf;
 187     pcache1.pFree = 0;
 188     pcache1.bUnderPressure = 0;
 189     while( n-- ){
 190       p = (PgFreeslot*)pBuf;
 191       p->pNext = pcache1.pFree;
 192       pcache1.pFree = p;
 193       pBuf = (void*)&((char*)pBuf)[sz];
 194     }
 195     pcache1.pEnd = pBuf;
 196   }
 197 }
 198
 199 /*
 200 ** Malloc function used within this file to allocate space from the buffer
 201 ** configured using sqlite3_config(SQLITE_CONFIG_PAGECACHE) option. If no
 202 ** such buffer exists or there is no space left in it, this function falls
 203 ** back to sqlite3Malloc().
 204 **
 205 ** Multiple threads can run this routine at the same time.  Global variables
 206 ** in pcache1 need to be protected via mutex.
 207 */
 208 static void *pcache1Alloc(int nByte){
 209   void *p = 0;
 210   assert( sqlite3_mutex_notheld(pcache1.grp.mutex) );
 211   sqlite3StatusSet(SQLITE_STATUS_PAGECACHE_SIZE, nByte);
 212   if( nByte<=pcache1.szSlot ){
 213     sqlite3_mutex_enter(pcache1.mutex);
 214     p = (PgHdr1 *)pcache1.pFree;
 215     if( p ){
 216       pcache1.pFree = pcache1.pFree->pNext;
 217       pcache1.nFreeSlot--;
 218       pcache1.bUnderPressure = pcache1.nFreeSlot<pcache1.nReserve;
 219       assert( pcache1.nFreeSlot>=0 );
 220       sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_USED, 1);
 221     }
 222     sqlite3_mutex_leave(pcache1.mutex);
 223   }
 224   if( p==0 ){
 225     /* Memory is not available in the SQLITE_CONFIG_PAGECACHE pool.  Get
 226     ** it from sqlite3Malloc instead.
 227     */
 228     p = sqlite3Malloc(nByte);
 229     if( p ){
 230       int sz = sqlite3MallocSize(p);
 231       sqlite3_mutex_enter(pcache1.mutex);
 232       sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_OVERFLOW, sz);
 233       sqlite3_mutex_leave(pcache1.mutex);
 234     }
 235     sqlite3MemdebugSetType(p, MEMTYPE_PCACHE);
 236   }
 237   return p;
 238 }
 239
 240 /*
 241 ** Free an allocated buffer obtained from pcache1Alloc().
 242 */
 243 static void pcache1Free(void *p){
 244   if( p==0 ) return;
 245   if( p>=pcache1.pStart && p<pcache1.pEnd ){
 246     PgFreeslot *pSlot;
 247     sqlite3_mutex_enter(pcache1.mutex);
 248     sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_USED, -1);
 249     pSlot = (PgFreeslot*)p;
 250     pSlot->pNext = pcache1.pFree;
 251     pcache1.pFree = pSlot;
 252     pcache1.nFreeSlot++;
 253     pcache1.bUnderPressure = pcache1.nFreeSlot<pcache1.nReserve;
 254     assert( pcache1.nFreeSlot<=pcache1.nSlot );
 255     sqlite3_mutex_leave(pcache1.mutex);
 256   }else{
 257     int iSize;
 258     assert( sqlite3MemdebugHasType(p, MEMTYPE_PCACHE) );
 259     sqlite3MemdebugSetType(p, MEMTYPE_HEAP);
 260     iSize = sqlite3MallocSize(p);
 261     sqlite3_mutex_enter(pcache1.mutex);
 262     sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_OVERFLOW, -iSize);
 263     sqlite3_mutex_leave(pcache1.mutex);
 264     sqlite3_free(p);
 265   }
 266 }
 267
 268 #ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
 269 /*
 270 ** Return the size of a pcache allocation
 271 */
 272 static int pcache1MemSize(void *p){
 273   if( p>=pcache1.pStart && p<pcache1.pEnd ){
 274     return pcache1.szSlot;
 275   }else{
 276     int iSize;
 277     assert( sqlite3MemdebugHasType(p, MEMTYPE_PCACHE) );
 278     sqlite3MemdebugSetType(p, MEMTYPE_HEAP);
 279     iSize = sqlite3MallocSize(p);
 280     sqlite3MemdebugSetType(p, MEMTYPE_PCACHE);
 281     return iSize;
 282   }
 283 }
 284 #endif /* SQLITE_ENABLE_MEMORY_MANAGEMENT */
 285
 286 /*
 287 ** Allocate a new page object initially associated with cache pCache.
 288 */
 289 static PgHdr1 *pcache1AllocPage(PCache1 *pCache){
 290   int nByte = sizeof(PgHdr1) + pCache->szPage;
 291   void *pPg = pcache1Alloc(nByte);
 292   PgHdr1 *p;
 293   if( pPg ){
 294     p = PAGE_TO_PGHDR1(pCache, pPg);
 295     if( pCache->bPurgeable ){
 296       pCache->pGroup->nCurrentPage++;
 297     }
 298   }else{
 299     p = 0;
 300   }
 301   return p;
 302 }
 303
 304 /*
 305 ** Free a page object allocated by pcache1AllocPage().
 306 **
 307 ** The pointer is allowed to be NULL, which is prudent.  But it turns out
 308 ** that the current implementation happens to never call this routine
 309 ** with a NULL pointer, so we mark the NULL test with ALWAYS().
 310 */
 311 static void pcache1FreePage(PgHdr1 *p){
 312   if( ALWAYS(p) ){
 313     PCache1 *pCache = p->pCache;
 314     if( pCache->bPurgeable ){
 315       pCache->pGroup->nCurrentPage--;
 316     }
 317     pcache1Free(PGHDR1_TO_PAGE(p));
 318   }
 319 }
 320
 321 /*
 322 ** Malloc function used by SQLite to obtain space from the buffer configured
 323 ** using sqlite3_config(SQLITE_CONFIG_PAGECACHE) option. If no such buffer
 324 ** exists, this function falls back to sqlite3Malloc().
 325 */
 326 void *sqlite3PageMalloc(int sz){
 327   return pcache1Alloc(sz);
 328 }
 329
 330 /*
 331 ** Free an allocated buffer obtained from sqlite3PageMalloc().
 332 */
 333 void sqlite3PageFree(void *p){
 334   pcache1Free(p);
 335 }
 336
 337
 338 /*
 339 ** Return true if it desirable to avoid allocating a new page cache
 340 ** entry.
 341 **
 342 ** If memory was allocated specifically to the page cache using
 343 ** SQLITE_CONFIG_PAGECACHE but that memory has all been used, then
 344 ** it is desirable to avoid allocating a new page cache entry because
 345 ** presumably SQLITE_CONFIG_PAGECACHE was suppose to be sufficient
 346 ** for all page cache needs and we should not need to spill the
 347 ** allocation onto the heap.
 348 **
 349 ** Or, the heap is used for all page cache memory put the heap is
 350 ** under memory pressure, then again it is desirable to avoid
 351 ** allocating a new page cache entry in order to avoid stressing
 352 ** the heap even further.
 353 */
 354 static int pcache1UnderMemoryPressure(PCache1 *pCache){
 355   if( pcache1.nSlot && pCache->szPage<=pcache1.szSlot ){
 356     return pcache1.bUnderPressure;
 357   }else{
 358     return sqlite3HeapNearlyFull();
 359   }
 360 }
 361
 362 /******************************************************************************/
 363 /******** General Implementation Functions ************************************/
 364
 365 /*
 366 ** This function is used to resize the hash table used by the cache passed
 367 ** as the first argument.
 368 **
 369 ** The PCache mutex must be held when this function is called.
 370 */
 371 static int pcache1ResizeHash(PCache1 *p){
 372   PgHdr1 **apNew;
 373   unsigned int nNew;
 374   unsigned int i;
 375
 376   assert( sqlite3_mutex_held(p->pGroup->mutex) );
 377
 378   nNew = p->nHash*2;
 379   if( nNew<256 ){
 380     nNew = 256;
 381   }
 382
 383   pcache1LeaveMutex(p->pGroup);
 384   if( p->nHash ){ sqlite3BeginBenignMalloc(); }
 385   apNew = (PgHdr1 **)sqlite3_malloc(sizeof(PgHdr1 *)*nNew);
 386   if( p->nHash ){ sqlite3EndBenignMalloc(); }
 387   pcache1EnterMutex(p->pGroup);
 388   if( apNew ){
 389     memset(apNew, 0, sizeof(PgHdr1 *)*nNew);
 390     for(i=0; i<p->nHash; i++){
 391       PgHdr1 *pPage;
 392       PgHdr1 *pNext = p->apHash[i];
 393       while( (pPage = pNext)!=0 ){
 394         unsigned int h = pPage->iKey % nNew;
 395         pNext = pPage->pNext;
 396         pPage->pNext = apNew[h];
 397         apNew[h] = pPage;
 398       }
 399     }
 400     sqlite3_free(p->apHash);
 401     p->apHash = apNew;
 402     p->nHash = nNew;
 403   }
 404
 405   return (p->apHash ? SQLITE_OK : SQLITE_NOMEM);
 406 }
 407
 408 /*
 409 ** This function is used internally to remove the page pPage from the
 410 ** PGroup LRU list, if is part of it. If pPage is not part of the PGroup
 411 ** LRU list, then this function is a no-op.
 412 **
 413 ** The PGroup mutex must be held when this function is called.
 414 **
 415 ** If pPage is NULL then this routine is a no-op.
 416 */
 417 static void pcache1PinPage(PgHdr1 *pPage){
 418   PCache1 *pCache;
 419   PGroup *pGroup;
 420
 421   if( pPage==0 ) return;
 422   pCache = pPage->pCache;
 423   pGroup = pCache->pGroup;
 424   assert( sqlite3_mutex_held(pGroup->mutex) );
 425   if( pPage->pLruNext || pPage==pGroup->pLruTail ){
 426     if( pPage->pLruPrev ){
 427       pPage->pLruPrev->pLruNext = pPage->pLruNext;
 428     }
 429     if( pPage->pLruNext ){
 430       pPage->pLruNext->pLruPrev = pPage->pLruPrev;
 431     }
 432     if( pGroup->pLruHead==pPage ){
 433       pGroup->pLruHead = pPage->pLruNext;
 434     }
 435     if( pGroup->pLruTail==pPage ){
 436       pGroup->pLruTail = pPage->pLruPrev;
 437     }
 438     pPage->pLruNext = 0;
 439     pPage->pLruPrev = 0;
 440     pPage->pCache->nRecyclable--;
 441   }
 442 }
 443
 444
 445 /*
 446 ** Remove the page supplied as an argument from the hash table
 447 ** (PCache1.apHash structure) that it is currently stored in.
 448 **
 449 ** The PGroup mutex must be held when this function is called.
 450 */
 451 static void pcache1RemoveFromHash(PgHdr1 *pPage){
 452   unsigned int h;
 453   PCache1 *pCache = pPage->pCache;
 454   PgHdr1 **pp;
 455
 456   assert( sqlite3_mutex_held(pCache->pGroup->mutex) );
 457   h = pPage->iKey % pCache->nHash;
 458   for(pp=&pCache->apHash[h]; (*pp)!=pPage; pp=&(*pp)->pNext);
 459   *pp = (*pp)->pNext;
 460
 461   pCache->nPage--;
 462 }
 463
 464 /*
 465 ** If there are currently more than nMaxPage pages allocated, try
 466 ** to recycle pages to reduce the number allocated to nMaxPage.
 467 */
 468 static void pcache1EnforceMaxPage(PGroup *pGroup){
 469   assert( sqlite3_mutex_held(pGroup->mutex) );
 470   while( pGroup->nCurrentPage>pGroup->nMaxPage && pGroup->pLruTail ){
 471     PgHdr1 *p = pGroup->pLruTail;
 472     assert( p->pCache->pGroup==pGroup );
 473     pcache1PinPage(p);
 474     pcache1RemoveFromHash(p);
 475     pcache1FreePage(p);
 476   }
 477 }
 478
 479 /*
 480 ** Discard all pages from cache pCache with a page number (key value)
 481 ** greater than or equal to iLimit. Any pinned pages that meet this
 482 ** criteria are unpinned before they are discarded.
 483 **
 484 ** The PCache mutex must be held when this function is called.
 485 */
 486 static void pcache1TruncateUnsafe(
 487   PCache1 *pCache,             /* The cache to truncate */
 488   unsigned int iLimit          /* Drop pages with this pgno or larger */
 489 ){
 490   TESTONLY( unsigned int nPage = 0; )  /* To assert pCache->nPage is correct */
 491   unsigned int h;
 492   assert( sqlite3_mutex_held(pCache->pGroup->mutex) );
 493   for(h=0; h<pCache->nHash; h++){
 494     PgHdr1 **pp = &pCache->apHash[h];
 495     PgHdr1 *pPage;
 496     while( (pPage = *pp)!=0 ){
 497       if( pPage->iKey>=iLimit ){
 498         pCache->nPage--;
 499         *pp = pPage->pNext;
 500         pcache1PinPage(pPage);
 501         pcache1FreePage(pPage);
 502       }else{
 503         pp = &pPage->pNext;
 504         TESTONLY( nPage++; )
 505       }
 506     }
 507   }
 508   assert( pCache->nPage==nPage );
 509 }
 510
 511 /******************************************************************************/
 512 /******** sqlite3_pcache Methods **********************************************/
 513
 514 /*
 515 ** Implementation of the sqlite3_pcache.xInit method.
 516 */
 517 static int pcache1Init(void *NotUsed){
 518   UNUSED_PARAMETER(NotUsed);
 519   assert( pcache1.isInit==0 );
 520   memset(&pcache1, 0, sizeof(pcache1));
 521   if( sqlite3GlobalConfig.bCoreMutex ){
 522     pcache1.grp.mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU);
 523     pcache1.mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_PMEM);
 524   }
 525   pcache1.grp.mxPinned = 10;
 526   pcache1.isInit = 1;
 527   return SQLITE_OK;
 528 }
 529
 530 /*
 531 ** Implementation of the sqlite3_pcache.xShutdown method.
 532 ** Note that the static mutex allocated in xInit does
 533 ** not need to be freed.
 534 */
 535 static void pcache1Shutdown(void *NotUsed){
 536   UNUSED_PARAMETER(NotUsed);
 537   assert( pcache1.isInit!=0 );
 538   memset(&pcache1, 0, sizeof(pcache1));
 539 }
 540
 541 /*
 542 ** Implementation of the sqlite3_pcache.xCreate method.
 543 **
 544 ** Allocate a new cache.
 545 */
 546 static sqlite3_pcache *pcache1Create(int szPage, int bPurgeable){
 547   PCache1 *pCache;      /* The newly created page cache */
 548   PGroup *pGroup;       /* The group the new page cache will belong to */
 549   int sz;               /* Bytes of memory required to allocate the new cache */
 550
 551   /*
 552   ** The separateCache variable is true if each PCache has its own private
 553   ** PGroup.  In other words, separateCache is true for mode (1) where no
 554   ** mutexing is required.
 555   **
 556   **   *  Always use separate caches (mode-1) if SQLITE_SEPARATE_CACHE_POOLS
 557   **
 558   **   *  Always use a unified cache (mode-2) if ENABLE_MEMORY_MANAGEMENT
 559   **
 560   **   *  Always use a unified cache in single-threaded applications
 561   **
 562   **   *  Otherwise (if multi-threaded and ENABLE_MEMORY_MANAGEMENT is off)
 563   **      use separate caches (mode-1)
 564   */
 565 #ifdef SQLITE_SEPARATE_CACHE_POOLS
 566   const int separateCache = 1;
 567 #elif defined(SQLITE_ENABLE_MEMORY_MANAGEMENT) || SQLITE_THREADSAFE==0
 568   const int separateCache = 0;
 569 #else
 570   int separateCache = sqlite3GlobalConfig.bCoreMutex>0;
 571 #endif
 572
 573   sz = sizeof(PCache1) + sizeof(PGroup)*separateCache;
 574   pCache = (PCache1 *)sqlite3_malloc(sz);
 575   if( pCache ){
 576     memset(pCache, 0, sz);
 577     if( separateCache ){
 578       pGroup = (PGroup*)&pCache[1];
 579       pGroup->mxPinned = 10;
 580     }else{
 581       pGroup = &pcache1_g.grp;
 582     }
 583     pCache->pGroup = pGroup;
 584     pCache->szPage = szPage;
 585     pCache->bPurgeable = (bPurgeable ? 1 : 0);
 586     if( bPurgeable ){
 587       pCache->nMin = 10;
 588       pcache1EnterMutex(pGroup);
 589       pGroup->nMinPage += pCache->nMin;
 590       pGroup->mxPinned = pGroup->nMaxPage + 10 - pGroup->nMinPage;
 591       pcache1LeaveMutex(pGroup);
 592     }
 593   }
 594   return (sqlite3_pcache *)pCache;
 595 }
 596
 597 /*
 598 ** Implementation of the sqlite3_pcache.xCachesize method.
 599 **
 600 ** Configure the cache_size limit for a cache.
 601 */
 602 static void pcache1Cachesize(sqlite3_pcache *p, int nMax){
 603   PCache1 *pCache = (PCache1 *)p;
 604   if( pCache->bPurgeable ){
 605     PGroup *pGroup = pCache->pGroup;
 606     pcache1EnterMutex(pGroup);
 607     pGroup->nMaxPage += (nMax - pCache->nMax);
 608     pGroup->mxPinned = pGroup->nMaxPage + 10 - pGroup->nMinPage;
 609     pCache->nMax = nMax;
 610     pCache->n90pct = pCache->nMax*9/10;
 611     pcache1EnforceMaxPage(pGroup);
 612     pcache1LeaveMutex(pGroup);
 613   }
 614 }
 615
 616 /*
 617 ** Implementation of the sqlite3_pcache.xPagecount method.
 618 */
 619 static int pcache1Pagecount(sqlite3_pcache *p){
 620   int n;
 621   PCache1 *pCache = (PCache1*)p;
 622   pcache1EnterMutex(pCache->pGroup);
 623   n = pCache->nPage;
 624   pcache1LeaveMutex(pCache->pGroup);
 625   return n;
 626 }
 627
 628 /*
 629 ** Implementation of the sqlite3_pcache.xFetch method.
 630 **
 631 ** Fetch a page by key value.
 632 **
 633 ** Whether or not a new page may be allocated by this function depends on
 634 ** the value of the createFlag argument.  0 means do not allocate a new
 635 ** page.  1 means allocate a new page if space is easily available.  2
 636 ** means to try really hard to allocate a new page.
 637 **
 638 ** For a non-purgeable cache (a cache used as the storage for an in-memory
 639 ** database) there is really no difference between createFlag 1 and 2.  So
 640 ** the calling function (pcache.c) will never have a createFlag of 1 on
 641 ** a non-purgable cache.
 642 **
 643 ** There are three different approaches to obtaining space for a page,
 644 ** depending on the value of parameter createFlag (which may be 0, 1 or 2).
 645 **
 646 **   1. Regardless of the value of createFlag, the cache is searched for a
 647 **      copy of the requested page. If one is found, it is returned.
 648 **
 649 **   2. If createFlag==0 and the page is not already in the cache, NULL is
 650 **      returned.
 651 **
 652 **   3. If createFlag is 1, and the page is not already in the cache, then
 653 **      return NULL (do not allocate a new page) if any of the following
 654 **      conditions are true:
 655 **
 656 **       (a) the number of pages pinned by the cache is greater than
 657 **           PCache1.nMax, or
 658 **
 659 **       (b) the number of pages pinned by the cache is greater than
 660 **           the sum of nMax for all purgeable caches, less the sum of
 661 **           nMin for all other purgeable caches, or
 662 **
 663 **   4. If none of the first three conditions apply and the cache is marked
 664 **      as purgeable, and if one of the following is true:
 665 **
 666 **       (a) The number of pages allocated for the cache is already
 667 **           PCache1.nMax, or
 668 **
 669 **       (b) The number of pages allocated for all purgeable caches is
 670 **           already equal to or greater than the sum of nMax for all
 671 **           purgeable caches,
 672 **
 673 **       (c) The system is under memory pressure and wants to avoid
 674 **           unnecessary pages cache entry allocations
 675 **
 676 **      then attempt to recycle a page from the LRU list. If it is the right
 677 **      size, return the recycled buffer. Otherwise, free the buffer and
 678 **      proceed to step 5.
 679 **
 680 **   5. Otherwise, allocate and return a new page buffer.
 681 */
 682 static void *pcache1Fetch(sqlite3_pcache *p, unsigned int iKey, int createFlag){
 683   int nPinned;
 684   PCache1 *pCache = (PCache1 *)p;
 685   PGroup *pGroup;
 686   PgHdr1 *pPage = 0;
 687
 688   assert( pCache->bPurgeable || createFlag!=1 );
 689   assert( pCache->bPurgeable || pCache->nMin==0 );
 690   assert( pCache->bPurgeable==0 || pCache->nMin==10 );
 691   assert( pCache->nMin==0 || pCache->bPurgeable );
 692   pcache1EnterMutex(pGroup = pCache->pGroup);
 693
 694   /* Step 1: Search the hash table for an existing entry. */
 695   if( pCache->nHash>0 ){
 696     unsigned int h = iKey % pCache->nHash;
 697     for(pPage=pCache->apHash[h]; pPage&&pPage->iKey!=iKey; pPage=pPage->pNext);
 698   }
 699
 700   /* Step 2: Abort if no existing page is found and createFlag is 0 */
 701   if( pPage || createFlag==0 ){
 702     pcache1PinPage(pPage);
 703     goto fetch_out;
 704   }
 705
 706   /* The pGroup local variable will normally be initialized by the
 707   ** pcache1EnterMutex() macro above.  But if SQLITE_MUTEX_OMIT is defined,
 708   ** then pcache1EnterMutex() is a no-op, so we have to initialize the
 709   ** local variable here.  Delaying the initialization of pGroup is an
 710   ** optimization:  The common case is to exit the module before reaching
 711   ** this point.
 712   */
 713 #ifdef SQLITE_MUTEX_OMIT
 714   pGroup = pCache->pGroup;
 715 #endif
 716
 717
 718   /* Step 3: Abort if createFlag is 1 but the cache is nearly full */
 719   nPinned = pCache->nPage - pCache->nRecyclable;
 720   assert( nPinned>=0 );
 721   assert( pGroup->mxPinned == pGroup->nMaxPage + 10 - pGroup->nMinPage );
 722   assert( pCache->n90pct == pCache->nMax*9/10 );
 723   if( createFlag==1 && (
 724         nPinned>=pGroup->mxPinned
 725      || nPinned>=(int)pCache->n90pct
 726      || pcache1UnderMemoryPressure(pCache)
 727   )){
 728     goto fetch_out;
 729   }
 730
 731   if( pCache->nPage>=pCache->nHash && pcache1ResizeHash(pCache) ){
 732     goto fetch_out;
 733   }
 734
 735   /* Step 4. Try to recycle a page. */
 736   if( pCache->bPurgeable && pGroup->pLruTail && (
 737          (pCache->nPage+1>=pCache->nMax)
 738       || pGroup->nCurrentPage>=pGroup->nMaxPage
 739       || pcache1UnderMemoryPressure(pCache)
 740   )){
 741     PCache1 *pOtherCache;
 742     pPage = pGroup->pLruTail;
 743     pcache1RemoveFromHash(pPage);
 744     pcache1PinPage(pPage);
 745     if( (pOtherCache = pPage->pCache)->szPage!=pCache->szPage ){
 746       pcache1FreePage(pPage);
 747       pPage = 0;
 748     }else{
 749       pGroup->nCurrentPage -=
 750                (pOtherCache->bPurgeable - pCache->bPurgeable);
 751     }
 752   }
 753
 754   /* Step 5. If a usable page buffer has still not been found,
 755   ** attempt to allocate a new one.
 756   */
 757   if( !pPage ){
 758     if( createFlag==1 ) sqlite3BeginBenignMalloc();
 759     pcache1LeaveMutex(pGroup);
 760     pPage = pcache1AllocPage(pCache);
 761     pcache1EnterMutex(pGroup);
 762     if( createFlag==1 ) sqlite3EndBenignMalloc();
 763   }
 764
 765   if( pPage ){
 766     unsigned int h = iKey % pCache->nHash;
 767     pCache->nPage++;
 768     pPage->iKey = iKey;
 769     pPage->pNext = pCache->apHash[h];
 770     pPage->pCache = pCache;
 771     pPage->pLruPrev = 0;
 772     pPage->pLruNext = 0;
 773     *(void **)(PGHDR1_TO_PAGE(pPage)) = 0;
 774     pCache->apHash[h] = pPage;
 775   }
 776
 777 fetch_out:
 778   if( pPage && iKey>pCache->iMaxKey ){
 779     pCache->iMaxKey = iKey;
 780   }
 781   pcache1LeaveMutex(pGroup);
 782   return (pPage ? PGHDR1_TO_PAGE(pPage) : 0);
 783 }
 784
 785
 786 /*
 787 ** Implementation of the sqlite3_pcache.xUnpin method.
 788 **
 789 ** Mark a page as unpinned (eligible for asynchronous recycling).
 790 */
 791 static void pcache1Unpin(sqlite3_pcache *p, void *pPg, int reuseUnlikely){
 792   PCache1 *pCache = (PCache1 *)p;
 793   PgHdr1 *pPage = PAGE_TO_PGHDR1(pCache, pPg);
 794   PGroup *pGroup = pCache->pGroup;
 795
 796   assert( pPage->pCache==pCache );
 797   pcache1EnterMutex(pGroup);
 798
 799   /* It is an error to call this function if the page is already
 800   ** part of the PGroup LRU list.
 801   */
 802   assert( pPage->pLruPrev==0 && pPage->pLruNext==0 );
 803   assert( pGroup->pLruHead!=pPage && pGroup->pLruTail!=pPage );
 804
 805   if( reuseUnlikely || pGroup->nCurrentPage>pGroup->nMaxPage ){
 806     pcache1RemoveFromHash(pPage);
 807     pcache1FreePage(pPage);
 808   }else{
 809     /* Add the page to the PGroup LRU list. */
 810     if( pGroup->pLruHead ){
 811       pGroup->pLruHead->pLruPrev = pPage;
 812       pPage->pLruNext = pGroup->pLruHead;
 813       pGroup->pLruHead = pPage;
 814     }else{
 815       pGroup->pLruTail = pPage;
 816       pGroup->pLruHead = pPage;
 817     }
 818     pCache->nRecyclable++;
 819   }
 820
 821   pcache1LeaveMutex(pCache->pGroup);
 822 }
 823
 824 /*
 825 ** Implementation of the sqlite3_pcache.xRekey method.
 826 */
 827 static void pcache1Rekey(
 828   sqlite3_pcache *p,
 829   void *pPg,
 830   unsigned int iOld,
 831   unsigned int iNew
 832 ){
 833   PCache1 *pCache = (PCache1 *)p;
 834   PgHdr1 *pPage = PAGE_TO_PGHDR1(pCache, pPg);
 835   PgHdr1 **pp;
 836   unsigned int h;
 837   assert( pPage->iKey==iOld );
 838   assert( pPage->pCache==pCache );
 839
 840   pcache1EnterMutex(pCache->pGroup);
 841
 842   h = iOld%pCache->nHash;
 843   pp = &pCache->apHash[h];
 844   while( (*pp)!=pPage ){
 845     pp = &(*pp)->pNext;
 846   }
 847   *pp = pPage->pNext;
 848
 849   h = iNew%pCache->nHash;
 850   pPage->iKey = iNew;
 851   pPage->pNext = pCache->apHash[h];
 852   pCache->apHash[h] = pPage;
 853   if( iNew>pCache->iMaxKey ){
 854     pCache->iMaxKey = iNew;
 855   }
 856
 857   pcache1LeaveMutex(pCache->pGroup);
 858 }
 859
 860 /*
 861 ** Implementation of the sqlite3_pcache.xTruncate method.
 862 **
 863 ** Discard all unpinned pages in the cache with a page number equal to
 864 ** or greater than parameter iLimit. Any pinned pages with a page number
 865 ** equal to or greater than iLimit are implicitly unpinned.
 866 */
 867 static void pcache1Truncate(sqlite3_pcache *p, unsigned int iLimit){
 868   PCache1 *pCache = (PCache1 *)p;
 869   pcache1EnterMutex(pCache->pGroup);
 870   if( iLimit<=pCache->iMaxKey ){
 871     pcache1TruncateUnsafe(pCache, iLimit);
 872     pCache->iMaxKey = iLimit-1;
 873   }
 874   pcache1LeaveMutex(pCache->pGroup);
 875 }
 876
 877 /*
 878 ** Implementation of the sqlite3_pcache.xDestroy method.
 879 **
 880 ** Destroy a cache allocated using pcache1Create().
 881 */
 882 static void pcache1Destroy(sqlite3_pcache *p){
 883   PCache1 *pCache = (PCache1 *)p;
 884   PGroup *pGroup = pCache->pGroup;
 885   assert( pCache->bPurgeable || (pCache->nMax==0 && pCache->nMin==0) );
 886   pcache1EnterMutex(pGroup);
 887   pcache1TruncateUnsafe(pCache, 0);
 888   pGroup->nMaxPage -= pCache->nMax;
 889   pGroup->nMinPage -= pCache->nMin;
 890   pGroup->mxPinned = pGroup->nMaxPage + 10 - pGroup->nMinPage;
 891   pcache1EnforceMaxPage(pGroup);
 892   pcache1LeaveMutex(pGroup);
 893   sqlite3_free(pCache->apHash);
 894   sqlite3_free(pCache);
 895 }
 896
 897 /*
 898 ** This function is called during initialization (sqlite3_initialize()) to
 899 ** install the default pluggable cache module, assuming the user has not
 900 ** already provided an alternative.
 901 */
 902 void sqlite3PCacheSetDefault(void){
 903   static const sqlite3_pcache_methods defaultMethods = {
 904     0,                       /* pArg */
 905     pcache1Init,             /* xInit */
 906     pcache1Shutdown,         /* xShutdown */
 907     pcache1Create,           /* xCreate */
 908     pcache1Cachesize,        /* xCachesize */
 909     pcache1Pagecount,        /* xPagecount */
 910     pcache1Fetch,            /* xFetch */
 911     pcache1Unpin,            /* xUnpin */
 912     pcache1Rekey,            /* xRekey */
 913     pcache1Truncate,         /* xTruncate */
 914     pcache1Destroy           /* xDestroy */
 915   };
 916   sqlite3_config(SQLITE_CONFIG_PCACHE, &defaultMethods);
 917 }
 918
 919 #ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
 920 /*
 921 ** This function is called to free superfluous dynamically allocated memory
 922 ** held by the pager system. Memory in use by any SQLite pager allocated
 923 ** by the current thread may be sqlite3_free()ed.
 924 **
 925 ** nReq is the number of bytes of memory required. Once this much has
 926 ** been released, the function returns. The return value is the total number
 927 ** of bytes of memory released.
 928 */
 929 int sqlite3PcacheReleaseMemory(int nReq){
 930   int nFree = 0;
 931   assert( sqlite3_mutex_notheld(pcache1.grp.mutex) );
 932   assert( sqlite3_mutex_notheld(pcache1.mutex) );
 933   if( pcache1.pStart==0 ){
 934     PgHdr1 *p;
 935     pcache1EnterMutex(&pcache1.grp);
 936     while( (nReq<0 || nFree<nReq) && ((p=pcache1.grp.pLruTail)!=0) ){
 937       nFree += pcache1MemSize(PGHDR1_TO_PAGE(p));
 938       pcache1PinPage(p);
 939       pcache1RemoveFromHash(p);
 940       pcache1FreePage(p);
 941     }
 942     pcache1LeaveMutex(&pcache1.grp);
 943   }
 944   return nFree;
 945 }
 946 #endif /* SQLITE_ENABLE_MEMORY_MANAGEMENT */
 947
 948 #ifdef SQLITE_TEST
 949 /*
 950 ** This function is used by test procedures to inspect the internal state
 951 ** of the global cache.
 952 */
 953 void sqlite3PcacheStats(
 954   int *pnCurrent,      /* OUT: Total number of pages cached */
 955   int *pnMax,          /* OUT: Global maximum cache size */
 956   int *pnMin,          /* OUT: Sum of PCache1.nMin for purgeable caches */
 957   int *pnRecyclable    /* OUT: Total number of pages available for recycling */
 958 ){
 959   PgHdr1 *p;
 960   int nRecyclable = 0;
 961   for(p=pcache1.grp.pLruHead; p; p=p->pLruNext){
 962     nRecyclable++;
 963   }
 964   *pnCurrent = pcache1.grp.nCurrentPage;
 965   *pnMax = pcache1.grp.nMaxPage;
 966   *pnMin = pcache1.grp.nMinPage;
 967   *pnRecyclable = nRecyclable;
 968 }
 969 #endif