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