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 *************************************************************************
12 ** This file implements that page cache.
14 #include "sqliteInt.h"
17 ** A complete page cache is an instance of this structure.
20 PgHdr *pDirty, *pDirtyTail; /* List of dirty pages in LRU order */
21 PgHdr *pSynced; /* Last synced page in dirty page list */
22 int nRef; /* Number of referenced pages */
23 int nMax; /* Configured cache size */
24 int szPage; /* Size of every page in this cache */
25 int szExtra; /* Size of extra space for each page */
26 int bPurgeable; /* True if pages are on backing store */
27 int (*xStress)(void*,PgHdr*); /* Call to try make a page clean */
28 void *pStress; /* Argument to xStress */
29 sqlite3_pcache *pCache; /* Pluggable cache module */
30 PgHdr *pPage1; /* Reference to page 1 */
34 ** Some of the assert() macros in this code are too expensive to run
35 ** even during normal debugging. Use them only rarely on long-running
36 ** tests. Enable the expensive asserts using the
37 ** -DSQLITE_ENABLE_EXPENSIVE_ASSERT=1 compile-time option.
39 #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
40 # define expensive_assert(X) assert(X)
42 # define expensive_assert(X)
45 /********************************** Linked List Management ********************/
47 #if !defined(NDEBUG) && defined(SQLITE_ENABLE_EXPENSIVE_ASSERT)
49 ** Check that the pCache->pSynced variable is set correctly. If it
50 ** is not, either fail an assert or return zero. Otherwise, return
51 ** non-zero. This is only used in debugging builds, as follows:
53 ** expensive_assert( pcacheCheckSynced(pCache) );
55 static int pcacheCheckSynced(PCache *pCache){
57 for(p=pCache->pDirtyTail; p!=pCache->pSynced; p=p->pDirtyPrev){
58 assert( p->nRef || (p->flags&PGHDR_NEED_SYNC) );
60 return (p==0 || p->nRef || (p->flags&PGHDR_NEED_SYNC)==0);
62 #endif /* !NDEBUG && SQLITE_ENABLE_EXPENSIVE_ASSERT */
65 ** Remove page pPage from the list of dirty pages.
67 static void pcacheRemoveFromDirtyList(PgHdr *pPage){
68 PCache *p = pPage->pCache;
70 assert( pPage->pDirtyNext || pPage==p->pDirtyTail );
71 assert( pPage->pDirtyPrev || pPage==p->pDirty );
73 /* Update the PCache1.pSynced variable if necessary. */
74 if( p->pSynced==pPage ){
75 PgHdr *pSynced = pPage->pDirtyPrev;
76 while( pSynced && (pSynced->flags&PGHDR_NEED_SYNC) ){
77 pSynced = pSynced->pDirtyPrev;
82 if( pPage->pDirtyNext ){
83 pPage->pDirtyNext->pDirtyPrev = pPage->pDirtyPrev;
85 assert( pPage==p->pDirtyTail );
86 p->pDirtyTail = pPage->pDirtyPrev;
88 if( pPage->pDirtyPrev ){
89 pPage->pDirtyPrev->pDirtyNext = pPage->pDirtyNext;
91 assert( pPage==p->pDirty );
92 p->pDirty = pPage->pDirtyNext;
94 pPage->pDirtyNext = 0;
95 pPage->pDirtyPrev = 0;
97 expensive_assert( pcacheCheckSynced(p) );
101 ** Add page pPage to the head of the dirty list (PCache1.pDirty is set to
104 static void pcacheAddToDirtyList(PgHdr *pPage){
105 PCache *p = pPage->pCache;
107 assert( pPage->pDirtyNext==0 && pPage->pDirtyPrev==0 && p->pDirty!=pPage );
109 pPage->pDirtyNext = p->pDirty;
110 if( pPage->pDirtyNext ){
111 assert( pPage->pDirtyNext->pDirtyPrev==0 );
112 pPage->pDirtyNext->pDirtyPrev = pPage;
115 if( !p->pDirtyTail ){
116 p->pDirtyTail = pPage;
118 if( !p->pSynced && 0==(pPage->flags&PGHDR_NEED_SYNC) ){
121 expensive_assert( pcacheCheckSynced(p) );
125 ** Wrapper around the pluggable caches xUnpin method. If the cache is
126 ** being used for an in-memory database, this function is a no-op.
128 static void pcacheUnpin(PgHdr *p){
129 PCache *pCache = p->pCache;
130 if( pCache->bPurgeable ){
134 sqlite3GlobalConfig.pcache.xUnpin(pCache->pCache, p, 0);
138 /*************************************************** General Interfaces ******
140 ** Initialize and shutdown the page cache subsystem. Neither of these
141 ** functions are threadsafe.
143 int sqlite3PcacheInitialize(void){
144 if( sqlite3GlobalConfig.pcache.xInit==0 ){
145 /* IMPLEMENTATION-OF: R-26801-64137 If the xInit() method is NULL, then the
146 ** built-in default page cache is used instead of the application defined
148 sqlite3PCacheSetDefault();
150 return sqlite3GlobalConfig.pcache.xInit(sqlite3GlobalConfig.pcache.pArg);
152 void sqlite3PcacheShutdown(void){
153 if( sqlite3GlobalConfig.pcache.xShutdown ){
154 /* IMPLEMENTATION-OF: R-26000-56589 The xShutdown() method may be NULL. */
155 sqlite3GlobalConfig.pcache.xShutdown(sqlite3GlobalConfig.pcache.pArg);
160 ** Return the size in bytes of a PCache object.
162 int sqlite3PcacheSize(void){ return sizeof(PCache); }
165 ** Create a new PCache object. Storage space to hold the object
166 ** has already been allocated and is passed in as the p pointer.
167 ** The caller discovers how much space needs to be allocated by
168 ** calling sqlite3PcacheSize().
170 void sqlite3PcacheOpen(
171 int szPage, /* Size of every page */
172 int szExtra, /* Extra space associated with each page */
173 int bPurgeable, /* True if pages are on backing store */
174 int (*xStress)(void*,PgHdr*),/* Call to try to make pages clean */
175 void *pStress, /* Argument to xStress */
176 PCache *p /* Preallocated space for the PCache */
178 memset(p, 0, sizeof(PCache));
180 p->szExtra = szExtra;
181 p->bPurgeable = bPurgeable;
182 p->xStress = xStress;
183 p->pStress = pStress;
188 ** Change the page size for PCache object. The caller must ensure that there
189 ** are no outstanding page references when this function is called.
191 void sqlite3PcacheSetPageSize(PCache *pCache, int szPage){
192 assert( pCache->nRef==0 && pCache->pDirty==0 );
193 if( pCache->pCache ){
194 sqlite3GlobalConfig.pcache.xDestroy(pCache->pCache);
198 pCache->szPage = szPage;
202 ** Try to obtain a page from the cache.
204 int sqlite3PcacheFetch(
205 PCache *pCache, /* Obtain the page from this cache */
206 Pgno pgno, /* Page number to obtain */
207 int createFlag, /* If true, create page if it does not exist already */
208 PgHdr **ppPage /* Write the page here */
214 assert( createFlag==1 || createFlag==0 );
217 /* If the pluggable cache (sqlite3_pcache*) has not been allocated,
220 if( !pCache->pCache && createFlag ){
223 nByte = pCache->szPage + pCache->szExtra + sizeof(PgHdr);
224 p = sqlite3GlobalConfig.pcache.xCreate(nByte, pCache->bPurgeable);
228 sqlite3GlobalConfig.pcache.xCachesize(p, pCache->nMax);
232 eCreate = createFlag * (1 + (!pCache->bPurgeable || !pCache->pDirty));
233 if( pCache->pCache ){
234 pPage = sqlite3GlobalConfig.pcache.xFetch(pCache->pCache, pgno, eCreate);
237 if( !pPage && eCreate==1 ){
240 /* Find a dirty page to write-out and recycle. First try to find a
241 ** page that does not require a journal-sync (one with PGHDR_NEED_SYNC
242 ** cleared), but if that is not possible settle for any other
243 ** unreferenced dirty page.
245 expensive_assert( pcacheCheckSynced(pCache) );
246 for(pPg=pCache->pSynced;
247 pPg && (pPg->nRef || (pPg->flags&PGHDR_NEED_SYNC));
250 pCache->pSynced = pPg;
252 for(pPg=pCache->pDirtyTail; pPg && pPg->nRef; pPg=pPg->pDirtyPrev);
256 rc = pCache->xStress(pCache->pStress, pPg);
257 if( rc!=SQLITE_OK && rc!=SQLITE_BUSY ){
262 pPage = sqlite3GlobalConfig.pcache.xFetch(pCache->pCache, pgno, 2);
267 memset(pPage, 0, sizeof(PgHdr));
268 pPage->pData = (void *)&pPage[1];
269 pPage->pExtra = (void*)&((char *)pPage->pData)[pCache->szPage];
270 memset(pPage->pExtra, 0, pCache->szExtra);
271 pPage->pCache = pCache;
274 assert( pPage->pCache==pCache );
275 assert( pPage->pgno==pgno );
276 assert( pPage->pData==(void *)&pPage[1] );
277 assert( pPage->pExtra==(void *)&((char *)&pPage[1])[pCache->szPage] );
279 if( 0==pPage->nRef ){
284 pCache->pPage1 = pPage;
288 return (pPage==0 && eCreate) ? SQLITE_NOMEM : SQLITE_OK;
292 ** Decrement the reference count on a page. If the page is clean and the
293 ** reference count drops to 0, then it is made elible for recycling.
295 void sqlite3PcacheRelease(PgHdr *p){
299 PCache *pCache = p->pCache;
301 if( (p->flags&PGHDR_DIRTY)==0 ){
304 /* Move the page to the head of the dirty list. */
305 pcacheRemoveFromDirtyList(p);
306 pcacheAddToDirtyList(p);
312 ** Increase the reference count of a supplied page by 1.
314 void sqlite3PcacheRef(PgHdr *p){
320 ** Drop a page from the cache. There must be exactly one reference to the
321 ** page. This function deletes that reference, so after it returns the
322 ** page pointed to by p is invalid.
324 void sqlite3PcacheDrop(PgHdr *p){
326 assert( p->nRef==1 );
327 if( p->flags&PGHDR_DIRTY ){
328 pcacheRemoveFromDirtyList(p);
335 sqlite3GlobalConfig.pcache.xUnpin(pCache->pCache, p, 1);
339 ** Make sure the page is marked as dirty. If it isn't dirty already,
342 void sqlite3PcacheMakeDirty(PgHdr *p){
343 p->flags &= ~PGHDR_DONT_WRITE;
345 if( 0==(p->flags & PGHDR_DIRTY) ){
346 p->flags |= PGHDR_DIRTY;
347 pcacheAddToDirtyList( p);
352 ** Make sure the page is marked as clean. If it isn't clean already,
355 void sqlite3PcacheMakeClean(PgHdr *p){
356 if( (p->flags & PGHDR_DIRTY) ){
357 pcacheRemoveFromDirtyList(p);
358 p->flags &= ~(PGHDR_DIRTY|PGHDR_NEED_SYNC);
366 ** Make every page in the cache clean.
368 void sqlite3PcacheCleanAll(PCache *pCache){
370 while( (p = pCache->pDirty)!=0 ){
371 sqlite3PcacheMakeClean(p);
376 ** Clear the PGHDR_NEED_SYNC flag from all dirty pages.
378 void sqlite3PcacheClearSyncFlags(PCache *pCache){
380 for(p=pCache->pDirty; p; p=p->pDirtyNext){
381 p->flags &= ~PGHDR_NEED_SYNC;
383 pCache->pSynced = pCache->pDirtyTail;
387 ** Change the page number of page p to newPgno.
389 void sqlite3PcacheMove(PgHdr *p, Pgno newPgno){
390 PCache *pCache = p->pCache;
393 sqlite3GlobalConfig.pcache.xRekey(pCache->pCache, p, p->pgno, newPgno);
395 if( (p->flags&PGHDR_DIRTY) && (p->flags&PGHDR_NEED_SYNC) ){
396 pcacheRemoveFromDirtyList(p);
397 pcacheAddToDirtyList(p);
402 ** Drop every cache entry whose page number is greater than "pgno". The
403 ** caller must ensure that there are no outstanding references to any pages
404 ** other than page 1 with a page number greater than pgno.
406 ** If there is a reference to page 1 and the pgno parameter passed to this
407 ** function is 0, then the data area associated with page 1 is zeroed, but
408 ** the page object is not dropped.
410 void sqlite3PcacheTruncate(PCache *pCache, Pgno pgno){
411 if( pCache->pCache ){
414 for(p=pCache->pDirty; p; p=pNext){
415 pNext = p->pDirtyNext;
416 /* This routine never gets call with a positive pgno except right
417 ** after sqlite3PcacheCleanAll(). So if there are dirty pages,
418 ** it must be that pgno==0.
421 if( ALWAYS(p->pgno>pgno) ){
422 assert( p->flags&PGHDR_DIRTY );
423 sqlite3PcacheMakeClean(p);
426 if( pgno==0 && pCache->pPage1 ){
427 memset(pCache->pPage1->pData, 0, pCache->szPage);
430 sqlite3GlobalConfig.pcache.xTruncate(pCache->pCache, pgno+1);
437 void sqlite3PcacheClose(PCache *pCache){
438 if( pCache->pCache ){
439 sqlite3GlobalConfig.pcache.xDestroy(pCache->pCache);
444 ** Discard the contents of the cache.
446 void sqlite3PcacheClear(PCache *pCache){
447 sqlite3PcacheTruncate(pCache, 0);
451 ** Merge two lists of pages connected by pDirty and in pgno order.
452 ** Do not both fixing the pDirtyPrev pointers.
454 static PgHdr *pcacheMergeDirtyList(PgHdr *pA, PgHdr *pB){
455 PgHdr result, *pTail;
458 if( pA->pgno<pB->pgno ){
475 return result.pDirty;
479 ** Sort the list of pages in accending order by pgno. Pages are
480 ** connected by pDirty pointers. The pDirtyPrev pointers are
481 ** corrupted by this sort.
483 ** Since there cannot be more than 2^31 distinct pages in a database,
484 ** there cannot be more than 31 buckets required by the merge sorter.
485 ** One extra bucket is added to catch overflow in case something
486 ** ever changes to make the previous sentence incorrect.
488 #define N_SORT_BUCKET 32
489 static PgHdr *pcacheSortDirtyList(PgHdr *pIn){
490 PgHdr *a[N_SORT_BUCKET], *p;
492 memset(a, 0, sizeof(a));
497 for(i=0; ALWAYS(i<N_SORT_BUCKET-1); i++){
502 p = pcacheMergeDirtyList(a[i], p);
506 if( NEVER(i==N_SORT_BUCKET-1) ){
507 /* To get here, there need to be 2^(N_SORT_BUCKET) elements in
508 ** the input list. But that is impossible.
510 a[i] = pcacheMergeDirtyList(a[i], p);
514 for(i=1; i<N_SORT_BUCKET; i++){
515 p = pcacheMergeDirtyList(p, a[i]);
521 ** Return a list of all dirty pages in the cache, sorted by page number.
523 PgHdr *sqlite3PcacheDirtyList(PCache *pCache){
525 for(p=pCache->pDirty; p; p=p->pDirtyNext){
526 p->pDirty = p->pDirtyNext;
528 return pcacheSortDirtyList(pCache->pDirty);
532 ** Return the total number of referenced pages held by the cache.
534 int sqlite3PcacheRefCount(PCache *pCache){
539 ** Return the number of references to the page supplied as an argument.
541 int sqlite3PcachePageRefcount(PgHdr *p){
546 ** Return the total number of pages in the cache.
548 int sqlite3PcachePagecount(PCache *pCache){
550 if( pCache->pCache ){
551 nPage = sqlite3GlobalConfig.pcache.xPagecount(pCache->pCache);
557 ** Get the suggested cache-size value.
559 int sqlite3PcacheGetCachesize(PCache *pCache){
564 ** Set the suggested cache-size value.
566 void sqlite3PcacheSetCachesize(PCache *pCache, int mxPage){
567 pCache->nMax = mxPage;
568 if( pCache->pCache ){
569 sqlite3GlobalConfig.pcache.xCachesize(pCache->pCache, mxPage);
573 #if defined(SQLITE_CHECK_PAGES) || defined(SQLITE_DEBUG)
575 ** For all dirty pages currently in the cache, invoke the specified
576 ** callback. This is only used if the SQLITE_CHECK_PAGES macro is
579 void sqlite3PcacheIterateDirty(PCache *pCache, void (*xIter)(PgHdr *)){
581 for(pDirty=pCache->pDirty; pDirty; pDirty=pDirty->pDirtyNext){