4 ** The author disclaims copyright to this source code. In place of
5 ** a legal notice, here is a blessing:
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.
11 *************************************************************************
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.
19 ** A Page cache line looks like this:
21 ** -------------------------------------------------------------
22 ** | database page content | PgHdr1 | MemPage | PgHdr |
23 ** -------------------------------------------------------------
25 ** The database page content is up front (so that buffer overreads tend to
26 ** flow harmlessly into the PgHdr1, MemPage, and PgHdr extensions). MemPage
27 ** is the extension added by the btree.c module containing information such
28 ** as the database page number and how that database page is used. PgHdr
29 ** is added by the pcache.c layer and contains information used to keep track
30 ** of which pages are "dirty". PgHdr1 is an extension added by this
31 ** module (pcache1.c). The PgHdr1 header is a subclass of sqlite3_pcache_page.
32 ** PgHdr1 contains information needed to look up a page by its page number.
33 ** The superclass sqlite3_pcache_page.pBuf points to the start of the
34 ** database page content and sqlite3_pcache_page.pExtra points to PgHdr.
36 ** The size of the extension (MemPage+PgHdr+PgHdr1) can be determined at
37 ** runtime using sqlite3_config(SQLITE_CONFIG_PCACHE_HDRSZ, &size). The
38 ** sizes of the extensions sum to 272 bytes on x64 for 3.8.10, but this
39 ** size can vary according to architecture, compile-time options, and
40 ** SQLite library version number.
42 ** If SQLITE_PCACHE_SEPARATE_HEADER is defined, then the extension is obtained
43 ** using a separate memory allocation from the database page content. This
44 ** seeks to overcome the "clownshoe" problem (also called "internal
45 ** fragmentation" in academic literature) of allocating a few bytes more
46 ** than a power of two with the memory allocator rounding up to the next
47 ** power of two, and leaving the rounded-up space unused.
49 ** This module tracks pointers to PgHdr1 objects. Only pcache.c communicates
50 ** with this module. Information is passed back and forth as PgHdr1 pointers.
52 ** The pcache.c and pager.c modules deal pointers to PgHdr objects.
53 ** The btree.c module deals with pointers to MemPage objects.
55 ** SOURCE OF PAGE CACHE MEMORY:
57 ** Memory for a page might come from any of three sources:
59 ** (1) The general-purpose memory allocator - sqlite3Malloc()
60 ** (2) Global page-cache memory provided using sqlite3_config() with
61 ** SQLITE_CONFIG_PAGECACHE.
62 ** (3) PCache-local bulk allocation.
64 ** The third case is a chunk of heap memory (defaulting to 100 pages worth)
65 ** that is allocated when the page cache is created. The size of the local
66 ** bulk allocation can be adjusted using
68 ** sqlite3_config(SQLITE_CONFIG_PAGECACHE, (void*)0, 0, N).
70 ** If N is positive, then N pages worth of memory are allocated using a single
71 ** sqlite3Malloc() call and that memory is used for the first N pages allocated.
72 ** Or if N is negative, then -1024*N bytes of memory are allocated and used
73 ** for as many pages as can be accomodated.
75 ** Only one of (2) or (3) can be used. Once the memory available to (2) or
76 ** (3) is exhausted, subsequent allocations fail over to the general-purpose
77 ** memory allocator (1).
79 ** Earlier versions of SQLite used only methods (1) and (2). But experiments
80 ** show that method (3) with N==100 provides about a 5% performance boost for
83 #include "sqliteInt.h"
85 typedef struct PCache1 PCache1
;
86 typedef struct PgHdr1 PgHdr1
;
87 typedef struct PgFreeslot PgFreeslot
;
88 typedef struct PGroup PGroup
;
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
97 sqlite3_pcache_page page
; /* Base class. Must be first. pBuf & pExtra */
98 unsigned int iKey
; /* Key value (page number) */
99 u8 isBulkLocal
; /* This page from bulk local storage */
100 u8 isAnchor
; /* This is the PGroup.lru element */
101 PgHdr1
*pNext
; /* Next in hash table chain */
102 PCache1
*pCache
; /* Cache that currently owns this page */
103 PgHdr1
*pLruNext
; /* Next in LRU list of unpinned pages */
104 PgHdr1
*pLruPrev
; /* Previous in LRU list of unpinned pages */
108 ** A page is pinned if it is no on the LRU list
110 #define PAGE_IS_PINNED(p) ((p)->pLruNext==0)
111 #define PAGE_IS_UNPINNED(p) ((p)->pLruNext!=0)
113 /* Each page cache (or PCache) belongs to a PGroup. A PGroup is a set
114 ** of one or more PCaches that are able to recycle each other's unpinned
115 ** pages when they are under memory pressure. A PGroup is an instance of
116 ** the following object.
118 ** This page cache implementation works in one of two modes:
120 ** (1) Every PCache is the sole member of its own PGroup. There is
121 ** one PGroup per PCache.
123 ** (2) There is a single global PGroup that all PCaches are a member
126 ** Mode 1 uses more memory (since PCache instances are not able to rob
127 ** unused pages from other PCaches) but it also operates without a mutex,
128 ** and is therefore often faster. Mode 2 requires a mutex in order to be
129 ** threadsafe, but recycles pages more efficiently.
131 ** For mode (1), PGroup.mutex is NULL. For mode (2) there is only a single
132 ** PGroup which is the pcache1.grp global variable and its mutex is
133 ** SQLITE_MUTEX_STATIC_LRU.
136 sqlite3_mutex
*mutex
; /* MUTEX_STATIC_LRU or NULL */
137 unsigned int nMaxPage
; /* Sum of nMax for purgeable caches */
138 unsigned int nMinPage
; /* Sum of nMin for purgeable caches */
139 unsigned int mxPinned
; /* nMaxpage + 10 - nMinPage */
140 unsigned int nPurgeable
; /* Number of purgeable pages allocated */
141 PgHdr1 lru
; /* The beginning and end of the LRU list */
144 /* Each page cache is an instance of the following object. Every
145 ** open database file (including each in-memory database and each
146 ** temporary or transient database) has a single page cache which
147 ** is an instance of this object.
149 ** Pointers to structures of this type are cast and returned as
150 ** opaque sqlite3_pcache* handles.
153 /* Cache configuration parameters. Page size (szPage) and the purgeable
154 ** flag (bPurgeable) and the pnPurgeable pointer are all set when the
155 ** cache is created and are never changed thereafter. nMax may be
156 ** modified at any time by a call to the pcache1Cachesize() method.
157 ** The PGroup mutex must be held when accessing nMax.
159 PGroup
*pGroup
; /* PGroup this cache belongs to */
160 unsigned int *pnPurgeable
; /* Pointer to pGroup->nPurgeable */
161 int szPage
; /* Size of database content section */
162 int szExtra
; /* sizeof(MemPage)+sizeof(PgHdr) */
163 int szAlloc
; /* Total size of one pcache line */
164 int bPurgeable
; /* True if cache is purgeable */
165 unsigned int nMin
; /* Minimum number of pages reserved */
166 unsigned int nMax
; /* Configured "cache_size" value */
167 unsigned int n90pct
; /* nMax*9/10 */
168 unsigned int iMaxKey
; /* Largest key seen since xTruncate() */
170 /* Hash table of all pages. The following variables may only be accessed
171 ** when the accessor is holding the PGroup mutex.
173 unsigned int nRecyclable
; /* Number of pages in the LRU list */
174 unsigned int nPage
; /* Total number of pages in apHash */
175 unsigned int nHash
; /* Number of slots in apHash[] */
176 PgHdr1
**apHash
; /* Hash table for fast lookup by key */
177 PgHdr1
*pFree
; /* List of unused pcache-local pages */
178 void *pBulk
; /* Bulk memory used by pcache-local */
182 ** Free slots in the allocator used to divide up the global page cache
183 ** buffer provided using the SQLITE_CONFIG_PAGECACHE mechanism.
186 PgFreeslot
*pNext
; /* Next free slot */
190 ** Global data used by this cache.
192 static SQLITE_WSD
struct PCacheGlobal
{
193 PGroup grp
; /* The global PGroup for mode (2) */
195 /* Variables related to SQLITE_CONFIG_PAGECACHE settings. The
196 ** szSlot, nSlot, pStart, pEnd, nReserve, and isInit values are all
197 ** fixed at sqlite3_initialize() time and do not require mutex protection.
198 ** The nFreeSlot and pFree values do require mutex protection.
200 int isInit
; /* True if initialized */
201 int separateCache
; /* Use a new PGroup for each PCache */
202 int nInitPage
; /* Initial bulk allocation size */
203 int szSlot
; /* Size of each free slot */
204 int nSlot
; /* The number of pcache slots */
205 int nReserve
; /* Try to keep nFreeSlot above this */
206 void *pStart
, *pEnd
; /* Bounds of global page cache memory */
207 /* Above requires no mutex. Use mutex below for variable that follow. */
208 sqlite3_mutex
*mutex
; /* Mutex for accessing the following: */
209 PgFreeslot
*pFree
; /* Free page blocks */
210 int nFreeSlot
; /* Number of unused pcache slots */
211 /* The following value requires a mutex to change. We skip the mutex on
212 ** reading because (1) most platforms read a 32-bit integer atomically and
213 ** (2) even if an incorrect value is read, no great harm is done since this
214 ** is really just an optimization. */
215 int bUnderPressure
; /* True if low on PAGECACHE memory */
219 ** All code in this file should access the global structure above via the
220 ** alias "pcache1". This ensures that the WSD emulation is used when
221 ** compiling for systems that do not support real WSD.
223 #define pcache1 (GLOBAL(struct PCacheGlobal, pcache1_g))
226 ** Macros to enter and leave the PCache LRU mutex.
228 #if !defined(SQLITE_ENABLE_MEMORY_MANAGEMENT) || SQLITE_THREADSAFE==0
229 # define pcache1EnterMutex(X) assert((X)->mutex==0)
230 # define pcache1LeaveMutex(X) assert((X)->mutex==0)
231 # define PCACHE1_MIGHT_USE_GROUP_MUTEX 0
233 # define pcache1EnterMutex(X) sqlite3_mutex_enter((X)->mutex)
234 # define pcache1LeaveMutex(X) sqlite3_mutex_leave((X)->mutex)
235 # define PCACHE1_MIGHT_USE_GROUP_MUTEX 1
238 /******************************************************************************/
239 /******** Page Allocation/SQLITE_CONFIG_PCACHE Related Functions **************/
243 ** This function is called during initialization if a static buffer is
244 ** supplied to use for the page-cache by passing the SQLITE_CONFIG_PAGECACHE
245 ** verb to sqlite3_config(). Parameter pBuf points to an allocation large
246 ** enough to contain 'n' buffers of 'sz' bytes each.
248 ** This routine is called from sqlite3_initialize() and so it is guaranteed
249 ** to be serialized already. There is no need for further mutexing.
251 void sqlite3PCacheBufferSetup(void *pBuf
, int sz
, int n
){
252 if( pcache1
.isInit
){
254 if( pBuf
==0 ) sz
= n
= 0;
258 pcache1
.nSlot
= pcache1
.nFreeSlot
= n
;
259 pcache1
.nReserve
= n
>90 ? 10 : (n
/10 + 1);
260 pcache1
.pStart
= pBuf
;
262 pcache1
.bUnderPressure
= 0;
264 p
= (PgFreeslot
*)pBuf
;
265 p
->pNext
= pcache1
.pFree
;
267 pBuf
= (void*)&((char*)pBuf
)[sz
];
274 ** Try to initialize the pCache->pFree and pCache->pBulk fields. Return
275 ** true if pCache->pFree ends up containing one or more free pages.
277 static int pcache1InitBulk(PCache1
*pCache
){
280 if( pcache1
.nInitPage
==0 ) return 0;
281 /* Do not bother with a bulk allocation if the cache size very small */
282 if( pCache
->nMax
<3 ) return 0;
283 sqlite3BeginBenignMalloc();
284 if( pcache1
.nInitPage
>0 ){
285 szBulk
= pCache
->szAlloc
* (i64
)pcache1
.nInitPage
;
287 szBulk
= -1024 * (i64
)pcache1
.nInitPage
;
289 if( szBulk
> pCache
->szAlloc
*(i64
)pCache
->nMax
){
290 szBulk
= pCache
->szAlloc
*(i64
)pCache
->nMax
;
292 zBulk
= pCache
->pBulk
= sqlite3Malloc( szBulk
);
293 sqlite3EndBenignMalloc();
295 int nBulk
= sqlite3MallocSize(zBulk
)/pCache
->szAlloc
;
297 PgHdr1
*pX
= (PgHdr1
*)&zBulk
[pCache
->szPage
];
298 pX
->page
.pBuf
= zBulk
;
299 pX
->page
.pExtra
= &pX
[1];
302 pX
->pNext
= pCache
->pFree
;
304 zBulk
+= pCache
->szAlloc
;
307 return pCache
->pFree
!=0;
311 ** Malloc function used within this file to allocate space from the buffer
312 ** configured using sqlite3_config(SQLITE_CONFIG_PAGECACHE) option. If no
313 ** such buffer exists or there is no space left in it, this function falls
314 ** back to sqlite3Malloc().
316 ** Multiple threads can run this routine at the same time. Global variables
317 ** in pcache1 need to be protected via mutex.
319 static void *pcache1Alloc(int nByte
){
321 assert( sqlite3_mutex_notheld(pcache1
.grp
.mutex
) );
322 if( nByte
<=pcache1
.szSlot
){
323 sqlite3_mutex_enter(pcache1
.mutex
);
324 p
= (PgHdr1
*)pcache1
.pFree
;
326 pcache1
.pFree
= pcache1
.pFree
->pNext
;
328 pcache1
.bUnderPressure
= pcache1
.nFreeSlot
<pcache1
.nReserve
;
329 assert( pcache1
.nFreeSlot
>=0 );
330 sqlite3StatusHighwater(SQLITE_STATUS_PAGECACHE_SIZE
, nByte
);
331 sqlite3StatusUp(SQLITE_STATUS_PAGECACHE_USED
, 1);
333 sqlite3_mutex_leave(pcache1
.mutex
);
336 /* Memory is not available in the SQLITE_CONFIG_PAGECACHE pool. Get
337 ** it from sqlite3Malloc instead.
339 p
= sqlite3Malloc(nByte
);
340 #ifndef SQLITE_DISABLE_PAGECACHE_OVERFLOW_STATS
342 int sz
= sqlite3MallocSize(p
);
343 sqlite3_mutex_enter(pcache1
.mutex
);
344 sqlite3StatusHighwater(SQLITE_STATUS_PAGECACHE_SIZE
, nByte
);
345 sqlite3StatusUp(SQLITE_STATUS_PAGECACHE_OVERFLOW
, sz
);
346 sqlite3_mutex_leave(pcache1
.mutex
);
349 sqlite3MemdebugSetType(p
, MEMTYPE_PCACHE
);
355 ** Free an allocated buffer obtained from pcache1Alloc().
357 static void pcache1Free(void *p
){
359 if( SQLITE_WITHIN(p
, pcache1
.pStart
, pcache1
.pEnd
) ){
361 sqlite3_mutex_enter(pcache1
.mutex
);
362 sqlite3StatusDown(SQLITE_STATUS_PAGECACHE_USED
, 1);
363 pSlot
= (PgFreeslot
*)p
;
364 pSlot
->pNext
= pcache1
.pFree
;
365 pcache1
.pFree
= pSlot
;
367 pcache1
.bUnderPressure
= pcache1
.nFreeSlot
<pcache1
.nReserve
;
368 assert( pcache1
.nFreeSlot
<=pcache1
.nSlot
);
369 sqlite3_mutex_leave(pcache1
.mutex
);
371 assert( sqlite3MemdebugHasType(p
, MEMTYPE_PCACHE
) );
372 sqlite3MemdebugSetType(p
, MEMTYPE_HEAP
);
373 #ifndef SQLITE_DISABLE_PAGECACHE_OVERFLOW_STATS
376 nFreed
= sqlite3MallocSize(p
);
377 sqlite3_mutex_enter(pcache1
.mutex
);
378 sqlite3StatusDown(SQLITE_STATUS_PAGECACHE_OVERFLOW
, nFreed
);
379 sqlite3_mutex_leave(pcache1
.mutex
);
386 #ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
388 ** Return the size of a pcache allocation
390 static int pcache1MemSize(void *p
){
391 if( p
>=pcache1
.pStart
&& p
<pcache1
.pEnd
){
392 return pcache1
.szSlot
;
395 assert( sqlite3MemdebugHasType(p
, MEMTYPE_PCACHE
) );
396 sqlite3MemdebugSetType(p
, MEMTYPE_HEAP
);
397 iSize
= sqlite3MallocSize(p
);
398 sqlite3MemdebugSetType(p
, MEMTYPE_PCACHE
);
402 #endif /* SQLITE_ENABLE_MEMORY_MANAGEMENT */
405 ** Allocate a new page object initially associated with cache pCache.
407 static PgHdr1
*pcache1AllocPage(PCache1
*pCache
, int benignMalloc
){
411 assert( sqlite3_mutex_held(pCache
->pGroup
->mutex
) );
412 if( pCache
->pFree
|| (pCache
->nPage
==0 && pcache1InitBulk(pCache
)) ){
414 pCache
->pFree
= p
->pNext
;
417 #ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
418 /* The group mutex must be released before pcache1Alloc() is called. This
419 ** is because it might call sqlite3_release_memory(), which assumes that
420 ** this mutex is not held. */
421 assert( pcache1
.separateCache
==0 );
422 assert( pCache
->pGroup
==&pcache1
.grp
);
423 pcache1LeaveMutex(pCache
->pGroup
);
425 if( benignMalloc
){ sqlite3BeginBenignMalloc(); }
426 #ifdef SQLITE_PCACHE_SEPARATE_HEADER
427 pPg
= pcache1Alloc(pCache
->szPage
);
428 p
= sqlite3Malloc(sizeof(PgHdr1
) + pCache
->szExtra
);
435 pPg
= pcache1Alloc(pCache
->szAlloc
);
436 p
= (PgHdr1
*)&((u8
*)pPg
)[pCache
->szPage
];
438 if( benignMalloc
){ sqlite3EndBenignMalloc(); }
439 #ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
440 pcache1EnterMutex(pCache
->pGroup
);
442 if( pPg
==0 ) return 0;
444 p
->page
.pExtra
= &p
[1];
448 (*pCache
->pnPurgeable
)++;
453 ** Free a page object allocated by pcache1AllocPage().
455 static void pcache1FreePage(PgHdr1
*p
){
459 assert( sqlite3_mutex_held(p
->pCache
->pGroup
->mutex
) );
460 if( p
->isBulkLocal
){
461 p
->pNext
= pCache
->pFree
;
464 pcache1Free(p
->page
.pBuf
);
465 #ifdef SQLITE_PCACHE_SEPARATE_HEADER
469 (*pCache
->pnPurgeable
)--;
473 ** Malloc function used by SQLite to obtain space from the buffer configured
474 ** using sqlite3_config(SQLITE_CONFIG_PAGECACHE) option. If no such buffer
475 ** exists, this function falls back to sqlite3Malloc().
477 void *sqlite3PageMalloc(int sz
){
478 return pcache1Alloc(sz
);
482 ** Free an allocated buffer obtained from sqlite3PageMalloc().
484 void sqlite3PageFree(void *p
){
490 ** Return true if it desirable to avoid allocating a new page cache
493 ** If memory was allocated specifically to the page cache using
494 ** SQLITE_CONFIG_PAGECACHE but that memory has all been used, then
495 ** it is desirable to avoid allocating a new page cache entry because
496 ** presumably SQLITE_CONFIG_PAGECACHE was suppose to be sufficient
497 ** for all page cache needs and we should not need to spill the
498 ** allocation onto the heap.
500 ** Or, the heap is used for all page cache memory but the heap is
501 ** under memory pressure, then again it is desirable to avoid
502 ** allocating a new page cache entry in order to avoid stressing
503 ** the heap even further.
505 static int pcache1UnderMemoryPressure(PCache1
*pCache
){
506 if( pcache1
.nSlot
&& (pCache
->szPage
+pCache
->szExtra
)<=pcache1
.szSlot
){
507 return pcache1
.bUnderPressure
;
509 return sqlite3HeapNearlyFull();
513 /******************************************************************************/
514 /******** General Implementation Functions ************************************/
517 ** This function is used to resize the hash table used by the cache passed
518 ** as the first argument.
520 ** The PCache mutex must be held when this function is called.
522 static void pcache1ResizeHash(PCache1
*p
){
527 assert( sqlite3_mutex_held(p
->pGroup
->mutex
) );
534 pcache1LeaveMutex(p
->pGroup
);
535 if( p
->nHash
){ sqlite3BeginBenignMalloc(); }
536 apNew
= (PgHdr1
**)sqlite3MallocZero(sizeof(PgHdr1
*)*nNew
);
537 if( p
->nHash
){ sqlite3EndBenignMalloc(); }
538 pcache1EnterMutex(p
->pGroup
);
540 for(i
=0; i
<p
->nHash
; i
++){
542 PgHdr1
*pNext
= p
->apHash
[i
];
543 while( (pPage
= pNext
)!=0 ){
544 unsigned int h
= pPage
->iKey
% nNew
;
545 pNext
= pPage
->pNext
;
546 pPage
->pNext
= apNew
[h
];
550 sqlite3_free(p
->apHash
);
557 ** This function is used internally to remove the page pPage from the
558 ** PGroup LRU list, if is part of it. If pPage is not part of the PGroup
559 ** LRU list, then this function is a no-op.
561 ** The PGroup mutex must be held when this function is called.
563 static PgHdr1
*pcache1PinPage(PgHdr1
*pPage
){
565 assert( PAGE_IS_UNPINNED(pPage
) );
566 assert( pPage
->pLruNext
);
567 assert( pPage
->pLruPrev
);
568 assert( sqlite3_mutex_held(pPage
->pCache
->pGroup
->mutex
) );
569 pPage
->pLruPrev
->pLruNext
= pPage
->pLruNext
;
570 pPage
->pLruNext
->pLruPrev
= pPage
->pLruPrev
;
573 assert( pPage
->isAnchor
==0 );
574 assert( pPage
->pCache
->pGroup
->lru
.isAnchor
==1 );
575 pPage
->pCache
->nRecyclable
--;
581 ** Remove the page supplied as an argument from the hash table
582 ** (PCache1.apHash structure) that it is currently stored in.
583 ** Also free the page if freePage is true.
585 ** The PGroup mutex must be held when this function is called.
587 static void pcache1RemoveFromHash(PgHdr1
*pPage
, int freeFlag
){
589 PCache1
*pCache
= pPage
->pCache
;
592 assert( sqlite3_mutex_held(pCache
->pGroup
->mutex
) );
593 h
= pPage
->iKey
% pCache
->nHash
;
594 for(pp
=&pCache
->apHash
[h
]; (*pp
)!=pPage
; pp
=&(*pp
)->pNext
);
598 if( freeFlag
) pcache1FreePage(pPage
);
602 ** If there are currently more than nMaxPage pages allocated, try
603 ** to recycle pages to reduce the number allocated to nMaxPage.
605 static void pcache1EnforceMaxPage(PCache1
*pCache
){
606 PGroup
*pGroup
= pCache
->pGroup
;
608 assert( sqlite3_mutex_held(pGroup
->mutex
) );
609 while( pGroup
->nPurgeable
>pGroup
->nMaxPage
610 && (p
=pGroup
->lru
.pLruPrev
)->isAnchor
==0
612 assert( p
->pCache
->pGroup
==pGroup
);
613 assert( PAGE_IS_UNPINNED(p
) );
615 pcache1RemoveFromHash(p
, 1);
617 if( pCache
->nPage
==0 && pCache
->pBulk
){
618 sqlite3_free(pCache
->pBulk
);
619 pCache
->pBulk
= pCache
->pFree
= 0;
624 ** Discard all pages from cache pCache with a page number (key value)
625 ** greater than or equal to iLimit. Any pinned pages that meet this
626 ** criteria are unpinned before they are discarded.
628 ** The PCache mutex must be held when this function is called.
630 static void pcache1TruncateUnsafe(
631 PCache1
*pCache
, /* The cache to truncate */
632 unsigned int iLimit
/* Drop pages with this pgno or larger */
634 TESTONLY( int nPage
= 0; ) /* To assert pCache->nPage is correct */
635 unsigned int h
, iStop
;
636 assert( sqlite3_mutex_held(pCache
->pGroup
->mutex
) );
637 assert( pCache
->iMaxKey
>= iLimit
);
638 assert( pCache
->nHash
> 0 );
639 if( pCache
->iMaxKey
- iLimit
< pCache
->nHash
){
640 /* If we are just shaving the last few pages off the end of the
641 ** cache, then there is no point in scanning the entire hash table.
642 ** Only scan those hash slots that might contain pages that need to
644 h
= iLimit
% pCache
->nHash
;
645 iStop
= pCache
->iMaxKey
% pCache
->nHash
;
646 TESTONLY( nPage
= -10; ) /* Disable the pCache->nPage validity check */
648 /* This is the general case where many pages are being removed.
649 ** It is necessary to scan the entire hash table */
656 assert( h
<pCache
->nHash
);
657 pp
= &pCache
->apHash
[h
];
658 while( (pPage
= *pp
)!=0 ){
659 if( pPage
->iKey
>=iLimit
){
662 if( PAGE_IS_UNPINNED(pPage
) ) pcache1PinPage(pPage
);
663 pcache1FreePage(pPage
);
666 TESTONLY( if( nPage
>=0 ) nPage
++; )
669 if( h
==iStop
) break;
670 h
= (h
+1) % pCache
->nHash
;
672 assert( nPage
<0 || pCache
->nPage
==(unsigned)nPage
);
675 /******************************************************************************/
676 /******** sqlite3_pcache Methods **********************************************/
679 ** Implementation of the sqlite3_pcache.xInit method.
681 static int pcache1Init(void *NotUsed
){
682 UNUSED_PARAMETER(NotUsed
);
683 assert( pcache1
.isInit
==0 );
684 memset(&pcache1
, 0, sizeof(pcache1
));
688 ** The pcache1.separateCache variable is true if each PCache has its own
689 ** private PGroup (mode-1). pcache1.separateCache is false if the single
690 ** PGroup in pcache1.grp is used for all page caches (mode-2).
692 ** * Always use a unified cache (mode-2) if ENABLE_MEMORY_MANAGEMENT
694 ** * Use a unified cache in single-threaded applications that have
695 ** configured a start-time buffer for use as page-cache memory using
696 ** sqlite3_config(SQLITE_CONFIG_PAGECACHE, pBuf, sz, N) with non-NULL
699 ** * Otherwise use separate caches (mode-1)
701 #if defined(SQLITE_ENABLE_MEMORY_MANAGEMENT)
702 pcache1
.separateCache
= 0;
703 #elif SQLITE_THREADSAFE
704 pcache1
.separateCache
= sqlite3GlobalConfig
.pPage
==0
705 || sqlite3GlobalConfig
.bCoreMutex
>0;
707 pcache1
.separateCache
= sqlite3GlobalConfig
.pPage
==0;
710 #if SQLITE_THREADSAFE
711 if( sqlite3GlobalConfig
.bCoreMutex
){
712 pcache1
.grp
.mutex
= sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_LRU
);
713 pcache1
.mutex
= sqlite3MutexAlloc(SQLITE_MUTEX_STATIC_PMEM
);
716 if( pcache1
.separateCache
717 && sqlite3GlobalConfig
.nPage
!=0
718 && sqlite3GlobalConfig
.pPage
==0
720 pcache1
.nInitPage
= sqlite3GlobalConfig
.nPage
;
722 pcache1
.nInitPage
= 0;
724 pcache1
.grp
.mxPinned
= 10;
730 ** Implementation of the sqlite3_pcache.xShutdown method.
731 ** Note that the static mutex allocated in xInit does
732 ** not need to be freed.
734 static void pcache1Shutdown(void *NotUsed
){
735 UNUSED_PARAMETER(NotUsed
);
736 assert( pcache1
.isInit
!=0 );
737 memset(&pcache1
, 0, sizeof(pcache1
));
740 /* forward declaration */
741 static void pcache1Destroy(sqlite3_pcache
*p
);
744 ** Implementation of the sqlite3_pcache.xCreate method.
746 ** Allocate a new cache.
748 static sqlite3_pcache
*pcache1Create(int szPage
, int szExtra
, int bPurgeable
){
749 PCache1
*pCache
; /* The newly created page cache */
750 PGroup
*pGroup
; /* The group the new page cache will belong to */
751 int sz
; /* Bytes of memory required to allocate the new cache */
753 assert( (szPage
& (szPage
-1))==0 && szPage
>=512 && szPage
<=65536 );
754 assert( szExtra
< 300 );
756 sz
= sizeof(PCache1
) + sizeof(PGroup
)*pcache1
.separateCache
;
757 pCache
= (PCache1
*)sqlite3MallocZero(sz
);
759 if( pcache1
.separateCache
){
760 pGroup
= (PGroup
*)&pCache
[1];
761 pGroup
->mxPinned
= 10;
763 pGroup
= &pcache1
.grp
;
765 if( pGroup
->lru
.isAnchor
==0 ){
766 pGroup
->lru
.isAnchor
= 1;
767 pGroup
->lru
.pLruPrev
= pGroup
->lru
.pLruNext
= &pGroup
->lru
;
769 pCache
->pGroup
= pGroup
;
770 pCache
->szPage
= szPage
;
771 pCache
->szExtra
= szExtra
;
772 pCache
->szAlloc
= szPage
+ szExtra
+ ROUND8(sizeof(PgHdr1
));
773 pCache
->bPurgeable
= (bPurgeable
? 1 : 0);
774 pcache1EnterMutex(pGroup
);
775 pcache1ResizeHash(pCache
);
778 pGroup
->nMinPage
+= pCache
->nMin
;
779 pGroup
->mxPinned
= pGroup
->nMaxPage
+ 10 - pGroup
->nMinPage
;
780 pCache
->pnPurgeable
= &pGroup
->nPurgeable
;
782 static unsigned int dummyCurrentPage
;
783 pCache
->pnPurgeable
= &dummyCurrentPage
;
785 pcache1LeaveMutex(pGroup
);
786 if( pCache
->nHash
==0 ){
787 pcache1Destroy((sqlite3_pcache
*)pCache
);
791 return (sqlite3_pcache
*)pCache
;
795 ** Implementation of the sqlite3_pcache.xCachesize method.
797 ** Configure the cache_size limit for a cache.
799 static void pcache1Cachesize(sqlite3_pcache
*p
, int nMax
){
800 PCache1
*pCache
= (PCache1
*)p
;
801 if( pCache
->bPurgeable
){
802 PGroup
*pGroup
= pCache
->pGroup
;
803 pcache1EnterMutex(pGroup
);
804 pGroup
->nMaxPage
+= (nMax
- pCache
->nMax
);
805 pGroup
->mxPinned
= pGroup
->nMaxPage
+ 10 - pGroup
->nMinPage
;
807 pCache
->n90pct
= pCache
->nMax
*9/10;
808 pcache1EnforceMaxPage(pCache
);
809 pcache1LeaveMutex(pGroup
);
814 ** Implementation of the sqlite3_pcache.xShrink method.
816 ** Free up as much memory as possible.
818 static void pcache1Shrink(sqlite3_pcache
*p
){
819 PCache1
*pCache
= (PCache1
*)p
;
820 if( pCache
->bPurgeable
){
821 PGroup
*pGroup
= pCache
->pGroup
;
823 pcache1EnterMutex(pGroup
);
824 savedMaxPage
= pGroup
->nMaxPage
;
825 pGroup
->nMaxPage
= 0;
826 pcache1EnforceMaxPage(pCache
);
827 pGroup
->nMaxPage
= savedMaxPage
;
828 pcache1LeaveMutex(pGroup
);
833 ** Implementation of the sqlite3_pcache.xPagecount method.
835 static int pcache1Pagecount(sqlite3_pcache
*p
){
837 PCache1
*pCache
= (PCache1
*)p
;
838 pcache1EnterMutex(pCache
->pGroup
);
840 pcache1LeaveMutex(pCache
->pGroup
);
846 ** Implement steps 3, 4, and 5 of the pcache1Fetch() algorithm described
847 ** in the header of the pcache1Fetch() procedure.
849 ** This steps are broken out into a separate procedure because they are
850 ** usually not needed, and by avoiding the stack initialization required
851 ** for these steps, the main pcache1Fetch() procedure can run faster.
853 static SQLITE_NOINLINE PgHdr1
*pcache1FetchStage2(
858 unsigned int nPinned
;
859 PGroup
*pGroup
= pCache
->pGroup
;
862 /* Step 3: Abort if createFlag is 1 but the cache is nearly full */
863 assert( pCache
->nPage
>= pCache
->nRecyclable
);
864 nPinned
= pCache
->nPage
- pCache
->nRecyclable
;
865 assert( pGroup
->mxPinned
== pGroup
->nMaxPage
+ 10 - pGroup
->nMinPage
);
866 assert( pCache
->n90pct
== pCache
->nMax
*9/10 );
867 if( createFlag
==1 && (
868 nPinned
>=pGroup
->mxPinned
869 || nPinned
>=pCache
->n90pct
870 || (pcache1UnderMemoryPressure(pCache
) && pCache
->nRecyclable
<nPinned
)
875 if( pCache
->nPage
>=pCache
->nHash
) pcache1ResizeHash(pCache
);
876 assert( pCache
->nHash
>0 && pCache
->apHash
);
878 /* Step 4. Try to recycle a page. */
879 if( pCache
->bPurgeable
880 && !pGroup
->lru
.pLruPrev
->isAnchor
881 && ((pCache
->nPage
+1>=pCache
->nMax
) || pcache1UnderMemoryPressure(pCache
))
884 pPage
= pGroup
->lru
.pLruPrev
;
885 assert( PAGE_IS_UNPINNED(pPage
) );
886 pcache1RemoveFromHash(pPage
, 0);
887 pcache1PinPage(pPage
);
888 pOther
= pPage
->pCache
;
889 if( pOther
->szAlloc
!= pCache
->szAlloc
){
890 pcache1FreePage(pPage
);
893 pGroup
->nPurgeable
-= (pOther
->bPurgeable
- pCache
->bPurgeable
);
897 /* Step 5. If a usable page buffer has still not been found,
898 ** attempt to allocate a new one.
901 pPage
= pcache1AllocPage(pCache
, createFlag
==1);
905 unsigned int h
= iKey
% pCache
->nHash
;
908 pPage
->pNext
= pCache
->apHash
[h
];
909 pPage
->pCache
= pCache
;
912 *(void **)pPage
->page
.pExtra
= 0;
913 pCache
->apHash
[h
] = pPage
;
914 if( iKey
>pCache
->iMaxKey
){
915 pCache
->iMaxKey
= iKey
;
922 ** Implementation of the sqlite3_pcache.xFetch method.
924 ** Fetch a page by key value.
926 ** Whether or not a new page may be allocated by this function depends on
927 ** the value of the createFlag argument. 0 means do not allocate a new
928 ** page. 1 means allocate a new page if space is easily available. 2
929 ** means to try really hard to allocate a new page.
931 ** For a non-purgeable cache (a cache used as the storage for an in-memory
932 ** database) there is really no difference between createFlag 1 and 2. So
933 ** the calling function (pcache.c) will never have a createFlag of 1 on
934 ** a non-purgeable cache.
936 ** There are three different approaches to obtaining space for a page,
937 ** depending on the value of parameter createFlag (which may be 0, 1 or 2).
939 ** 1. Regardless of the value of createFlag, the cache is searched for a
940 ** copy of the requested page. If one is found, it is returned.
942 ** 2. If createFlag==0 and the page is not already in the cache, NULL is
945 ** 3. If createFlag is 1, and the page is not already in the cache, then
946 ** return NULL (do not allocate a new page) if any of the following
947 ** conditions are true:
949 ** (a) the number of pages pinned by the cache is greater than
952 ** (b) the number of pages pinned by the cache is greater than
953 ** the sum of nMax for all purgeable caches, less the sum of
954 ** nMin for all other purgeable caches, or
956 ** 4. If none of the first three conditions apply and the cache is marked
957 ** as purgeable, and if one of the following is true:
959 ** (a) The number of pages allocated for the cache is already
962 ** (b) The number of pages allocated for all purgeable caches is
963 ** already equal to or greater than the sum of nMax for all
966 ** (c) The system is under memory pressure and wants to avoid
967 ** unnecessary pages cache entry allocations
969 ** then attempt to recycle a page from the LRU list. If it is the right
970 ** size, return the recycled buffer. Otherwise, free the buffer and
971 ** proceed to step 5.
973 ** 5. Otherwise, allocate and return a new page buffer.
975 ** There are two versions of this routine. pcache1FetchWithMutex() is
976 ** the general case. pcache1FetchNoMutex() is a faster implementation for
977 ** the common case where pGroup->mutex is NULL. The pcache1Fetch() wrapper
978 ** invokes the appropriate routine.
980 static PgHdr1
*pcache1FetchNoMutex(
985 PCache1
*pCache
= (PCache1
*)p
;
988 /* Step 1: Search the hash table for an existing entry. */
989 pPage
= pCache
->apHash
[iKey
% pCache
->nHash
];
990 while( pPage
&& pPage
->iKey
!=iKey
){ pPage
= pPage
->pNext
; }
992 /* Step 2: If the page was found in the hash table, then return it.
993 ** If the page was not in the hash table and createFlag is 0, abort.
994 ** Otherwise (page not in hash and createFlag!=0) continue with
995 ** subsequent steps to try to create the page. */
997 if( PAGE_IS_UNPINNED(pPage
) ){
998 return pcache1PinPage(pPage
);
1002 }else if( createFlag
){
1003 /* Steps 3, 4, and 5 implemented by this subroutine */
1004 return pcache1FetchStage2(pCache
, iKey
, createFlag
);
1009 #if PCACHE1_MIGHT_USE_GROUP_MUTEX
1010 static PgHdr1
*pcache1FetchWithMutex(
1015 PCache1
*pCache
= (PCache1
*)p
;
1018 pcache1EnterMutex(pCache
->pGroup
);
1019 pPage
= pcache1FetchNoMutex(p
, iKey
, createFlag
);
1020 assert( pPage
==0 || pCache
->iMaxKey
>=iKey
);
1021 pcache1LeaveMutex(pCache
->pGroup
);
1025 static sqlite3_pcache_page
*pcache1Fetch(
1030 #if PCACHE1_MIGHT_USE_GROUP_MUTEX || defined(SQLITE_DEBUG)
1031 PCache1
*pCache
= (PCache1
*)p
;
1034 assert( offsetof(PgHdr1
,page
)==0 );
1035 assert( pCache
->bPurgeable
|| createFlag
!=1 );
1036 assert( pCache
->bPurgeable
|| pCache
->nMin
==0 );
1037 assert( pCache
->bPurgeable
==0 || pCache
->nMin
==10 );
1038 assert( pCache
->nMin
==0 || pCache
->bPurgeable
);
1039 assert( pCache
->nHash
>0 );
1040 #if PCACHE1_MIGHT_USE_GROUP_MUTEX
1041 if( pCache
->pGroup
->mutex
){
1042 return (sqlite3_pcache_page
*)pcache1FetchWithMutex(p
, iKey
, createFlag
);
1046 return (sqlite3_pcache_page
*)pcache1FetchNoMutex(p
, iKey
, createFlag
);
1052 ** Implementation of the sqlite3_pcache.xUnpin method.
1054 ** Mark a page as unpinned (eligible for asynchronous recycling).
1056 static void pcache1Unpin(
1058 sqlite3_pcache_page
*pPg
,
1061 PCache1
*pCache
= (PCache1
*)p
;
1062 PgHdr1
*pPage
= (PgHdr1
*)pPg
;
1063 PGroup
*pGroup
= pCache
->pGroup
;
1065 assert( pPage
->pCache
==pCache
);
1066 pcache1EnterMutex(pGroup
);
1068 /* It is an error to call this function if the page is already
1069 ** part of the PGroup LRU list.
1071 assert( pPage
->pLruPrev
==0 && pPage
->pLruNext
==0 );
1072 assert( PAGE_IS_PINNED(pPage
) );
1074 if( reuseUnlikely
|| pGroup
->nPurgeable
>pGroup
->nMaxPage
){
1075 pcache1RemoveFromHash(pPage
, 1);
1077 /* Add the page to the PGroup LRU list. */
1078 PgHdr1
**ppFirst
= &pGroup
->lru
.pLruNext
;
1079 pPage
->pLruPrev
= &pGroup
->lru
;
1080 (pPage
->pLruNext
= *ppFirst
)->pLruPrev
= pPage
;
1082 pCache
->nRecyclable
++;
1085 pcache1LeaveMutex(pCache
->pGroup
);
1089 ** Implementation of the sqlite3_pcache.xRekey method.
1091 static void pcache1Rekey(
1093 sqlite3_pcache_page
*pPg
,
1097 PCache1
*pCache
= (PCache1
*)p
;
1098 PgHdr1
*pPage
= (PgHdr1
*)pPg
;
1101 assert( pPage
->iKey
==iOld
);
1102 assert( pPage
->pCache
==pCache
);
1104 pcache1EnterMutex(pCache
->pGroup
);
1106 h
= iOld
%pCache
->nHash
;
1107 pp
= &pCache
->apHash
[h
];
1108 while( (*pp
)!=pPage
){
1113 h
= iNew
%pCache
->nHash
;
1115 pPage
->pNext
= pCache
->apHash
[h
];
1116 pCache
->apHash
[h
] = pPage
;
1117 if( iNew
>pCache
->iMaxKey
){
1118 pCache
->iMaxKey
= iNew
;
1121 pcache1LeaveMutex(pCache
->pGroup
);
1125 ** Implementation of the sqlite3_pcache.xTruncate method.
1127 ** Discard all unpinned pages in the cache with a page number equal to
1128 ** or greater than parameter iLimit. Any pinned pages with a page number
1129 ** equal to or greater than iLimit are implicitly unpinned.
1131 static void pcache1Truncate(sqlite3_pcache
*p
, unsigned int iLimit
){
1132 PCache1
*pCache
= (PCache1
*)p
;
1133 pcache1EnterMutex(pCache
->pGroup
);
1134 if( iLimit
<=pCache
->iMaxKey
){
1135 pcache1TruncateUnsafe(pCache
, iLimit
);
1136 pCache
->iMaxKey
= iLimit
-1;
1138 pcache1LeaveMutex(pCache
->pGroup
);
1142 ** Implementation of the sqlite3_pcache.xDestroy method.
1144 ** Destroy a cache allocated using pcache1Create().
1146 static void pcache1Destroy(sqlite3_pcache
*p
){
1147 PCache1
*pCache
= (PCache1
*)p
;
1148 PGroup
*pGroup
= pCache
->pGroup
;
1149 assert( pCache
->bPurgeable
|| (pCache
->nMax
==0 && pCache
->nMin
==0) );
1150 pcache1EnterMutex(pGroup
);
1151 if( pCache
->nPage
) pcache1TruncateUnsafe(pCache
, 0);
1152 assert( pGroup
->nMaxPage
>= pCache
->nMax
);
1153 pGroup
->nMaxPage
-= pCache
->nMax
;
1154 assert( pGroup
->nMinPage
>= pCache
->nMin
);
1155 pGroup
->nMinPage
-= pCache
->nMin
;
1156 pGroup
->mxPinned
= pGroup
->nMaxPage
+ 10 - pGroup
->nMinPage
;
1157 pcache1EnforceMaxPage(pCache
);
1158 pcache1LeaveMutex(pGroup
);
1159 sqlite3_free(pCache
->pBulk
);
1160 sqlite3_free(pCache
->apHash
);
1161 sqlite3_free(pCache
);
1165 ** This function is called during initialization (sqlite3_initialize()) to
1166 ** install the default pluggable cache module, assuming the user has not
1167 ** already provided an alternative.
1169 void sqlite3PCacheSetDefault(void){
1170 static const sqlite3_pcache_methods2 defaultMethods
= {
1173 pcache1Init
, /* xInit */
1174 pcache1Shutdown
, /* xShutdown */
1175 pcache1Create
, /* xCreate */
1176 pcache1Cachesize
, /* xCachesize */
1177 pcache1Pagecount
, /* xPagecount */
1178 pcache1Fetch
, /* xFetch */
1179 pcache1Unpin
, /* xUnpin */
1180 pcache1Rekey
, /* xRekey */
1181 pcache1Truncate
, /* xTruncate */
1182 pcache1Destroy
, /* xDestroy */
1183 pcache1Shrink
/* xShrink */
1185 sqlite3_config(SQLITE_CONFIG_PCACHE2
, &defaultMethods
);
1189 ** Return the size of the header on each page of this PCACHE implementation.
1191 int sqlite3HeaderSizePcache1(void){ return ROUND8(sizeof(PgHdr1
)); }
1194 ** Return the global mutex used by this PCACHE implementation. The
1195 ** sqlite3_status() routine needs access to this mutex.
1197 sqlite3_mutex
*sqlite3Pcache1Mutex(void){
1198 return pcache1
.mutex
;
1201 #ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
1203 ** This function is called to free superfluous dynamically allocated memory
1204 ** held by the pager system. Memory in use by any SQLite pager allocated
1205 ** by the current thread may be sqlite3_free()ed.
1207 ** nReq is the number of bytes of memory required. Once this much has
1208 ** been released, the function returns. The return value is the total number
1209 ** of bytes of memory released.
1211 int sqlite3PcacheReleaseMemory(int nReq
){
1213 assert( sqlite3_mutex_notheld(pcache1
.grp
.mutex
) );
1214 assert( sqlite3_mutex_notheld(pcache1
.mutex
) );
1215 if( sqlite3GlobalConfig
.pPage
==0 ){
1217 pcache1EnterMutex(&pcache1
.grp
);
1218 while( (nReq
<0 || nFree
<nReq
)
1219 && (p
=pcache1
.grp
.lru
.pLruPrev
)!=0
1222 nFree
+= pcache1MemSize(p
->page
.pBuf
);
1223 #ifdef SQLITE_PCACHE_SEPARATE_HEADER
1224 nFree
+= sqlite3MemSize(p
);
1226 assert( PAGE_IS_UNPINNED(p
) );
1228 pcache1RemoveFromHash(p
, 1);
1230 pcache1LeaveMutex(&pcache1
.grp
);
1234 #endif /* SQLITE_ENABLE_MEMORY_MANAGEMENT */
1238 ** This function is used by test procedures to inspect the internal state
1239 ** of the global cache.
1241 void sqlite3PcacheStats(
1242 int *pnCurrent
, /* OUT: Total number of pages cached */
1243 int *pnMax
, /* OUT: Global maximum cache size */
1244 int *pnMin
, /* OUT: Sum of PCache1.nMin for purgeable caches */
1245 int *pnRecyclable
/* OUT: Total number of pages available for recycling */
1248 int nRecyclable
= 0;
1249 for(p
=pcache1
.grp
.lru
.pLruNext
; p
&& !p
->isAnchor
; p
=p
->pLruNext
){
1250 assert( PAGE_IS_UNPINNED(p
) );
1253 *pnCurrent
= pcache1
.grp
.nPurgeable
;
1254 *pnMax
= (int)pcache1
.grp
.nMaxPage
;
1255 *pnMin
= (int)pcache1
.grp
.nMinPage
;
1256 *pnRecyclable
= nRecyclable
;