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 22typedef struct PCache1 PCache1; 23typedef struct PgHdr1 PgHdr1; 24typedef struct PgFreeslot PgFreeslot; 25typedef 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*/ 49struct 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*/ 66struct 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*/ 96struct 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*/ 108struct PgFreeslot { 109 PgFreeslot *pNext; /* Next free slot */ 110}; 111 112/* 113** Global data used by this cache. 114*/ 115static 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*/ 179void 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*/ 208static 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*/ 243static 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*/ 272static 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*/ 289static 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*/ 311static 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*/ 326void *sqlite3PageMalloc(int sz){ 327 return pcache1Alloc(sz); 328} 329 330/* 331** Free an allocated buffer obtained from sqlite3PageMalloc(). 332*/ 333void 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*/ 354static 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*/ 371static 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*/ 417static 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*/ 451static 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*/ 468static 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*/ 486static 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*/ 517static 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*/ 535static 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*/ 546static 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*/ 602static 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*/ 619static 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*/ 682static 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 777fetch_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*/ 791static 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*/ 827static 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*/ 867static 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*/ 882static 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*/ 902void 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*/ 929int 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*/ 953void 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 970