Merge Chromium + Blink git repositories
[chromium-blink-merge.git] / third_party / sqlite / sqlite-src-3080704 / src / pcache.c
blob191a9d00f41ded328642e71fa5da12138f38bc35
1 /*
2 ** 2008 August 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.
11 *************************************************************************
12 ** This file implements that page cache.
14 #include "sqliteInt.h"
17 ** A complete page cache is an instance of this structure.
19 struct PCache {
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 szCache; /* Configured cache size */
24 int szPage; /* Size of every page in this cache */
25 int szExtra; /* Size of extra space for each page */
26 u8 bPurgeable; /* True if pages are on backing store */
27 u8 eCreate; /* eCreate value for for xFetch() */
28 int (*xStress)(void*,PgHdr*); /* Call to try make a page clean */
29 void *pStress; /* Argument to xStress */
30 sqlite3_pcache *pCache; /* Pluggable cache module */
31 PgHdr *pPage1; /* Reference to page 1 */
35 ** Some of the assert() macros in this code are too expensive to run
36 ** even during normal debugging. Use them only rarely on long-running
37 ** tests. Enable the expensive asserts using the
38 ** -DSQLITE_ENABLE_EXPENSIVE_ASSERT=1 compile-time option.
40 #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
41 # define expensive_assert(X) assert(X)
42 #else
43 # define expensive_assert(X)
44 #endif
46 /********************************** Linked List Management ********************/
48 /* Allowed values for second argument to pcacheManageDirtyList() */
49 #define PCACHE_DIRTYLIST_REMOVE 1 /* Remove pPage from dirty list */
50 #define PCACHE_DIRTYLIST_ADD 2 /* Add pPage to the dirty list */
51 #define PCACHE_DIRTYLIST_FRONT 3 /* Move pPage to the front of the list */
54 ** Manage pPage's participation on the dirty list. Bits of the addRemove
55 ** argument determines what operation to do. The 0x01 bit means first
56 ** remove pPage from the dirty list. The 0x02 means add pPage back to
57 ** the dirty list. Doing both moves pPage to the front of the dirty list.
59 static void pcacheManageDirtyList(PgHdr *pPage, u8 addRemove){
60 PCache *p = pPage->pCache;
62 if( addRemove & PCACHE_DIRTYLIST_REMOVE ){
63 assert( pPage->pDirtyNext || pPage==p->pDirtyTail );
64 assert( pPage->pDirtyPrev || pPage==p->pDirty );
66 /* Update the PCache1.pSynced variable if necessary. */
67 if( p->pSynced==pPage ){
68 PgHdr *pSynced = pPage->pDirtyPrev;
69 while( pSynced && (pSynced->flags&PGHDR_NEED_SYNC) ){
70 pSynced = pSynced->pDirtyPrev;
72 p->pSynced = pSynced;
75 if( pPage->pDirtyNext ){
76 pPage->pDirtyNext->pDirtyPrev = pPage->pDirtyPrev;
77 }else{
78 assert( pPage==p->pDirtyTail );
79 p->pDirtyTail = pPage->pDirtyPrev;
81 if( pPage->pDirtyPrev ){
82 pPage->pDirtyPrev->pDirtyNext = pPage->pDirtyNext;
83 }else{
84 assert( pPage==p->pDirty );
85 p->pDirty = pPage->pDirtyNext;
86 if( p->pDirty==0 && p->bPurgeable ){
87 assert( p->eCreate==1 );
88 p->eCreate = 2;
91 pPage->pDirtyNext = 0;
92 pPage->pDirtyPrev = 0;
94 if( addRemove & PCACHE_DIRTYLIST_ADD ){
95 assert( pPage->pDirtyNext==0 && pPage->pDirtyPrev==0 && p->pDirty!=pPage );
97 pPage->pDirtyNext = p->pDirty;
98 if( pPage->pDirtyNext ){
99 assert( pPage->pDirtyNext->pDirtyPrev==0 );
100 pPage->pDirtyNext->pDirtyPrev = pPage;
101 }else{
102 p->pDirtyTail = pPage;
103 if( p->bPurgeable ){
104 assert( p->eCreate==2 );
105 p->eCreate = 1;
108 p->pDirty = pPage;
109 if( !p->pSynced && 0==(pPage->flags&PGHDR_NEED_SYNC) ){
110 p->pSynced = pPage;
116 ** Wrapper around the pluggable caches xUnpin method. If the cache is
117 ** being used for an in-memory database, this function is a no-op.
119 static void pcacheUnpin(PgHdr *p){
120 if( p->pCache->bPurgeable ){
121 if( p->pgno==1 ){
122 p->pCache->pPage1 = 0;
124 sqlite3GlobalConfig.pcache2.xUnpin(p->pCache->pCache, p->pPage, 0);
129 ** Compute the number of pages of cache requested.
131 static int numberOfCachePages(PCache *p){
132 if( p->szCache>=0 ){
133 return p->szCache;
134 }else{
135 return (int)((-1024*(i64)p->szCache)/(p->szPage+p->szExtra));
139 /*************************************************** General Interfaces ******
141 ** Initialize and shutdown the page cache subsystem. Neither of these
142 ** functions are threadsafe.
144 int sqlite3PcacheInitialize(void){
145 if( sqlite3GlobalConfig.pcache2.xInit==0 ){
146 /* IMPLEMENTATION-OF: R-26801-64137 If the xInit() method is NULL, then the
147 ** built-in default page cache is used instead of the application defined
148 ** page cache. */
149 sqlite3PCacheSetDefault();
151 return sqlite3GlobalConfig.pcache2.xInit(sqlite3GlobalConfig.pcache2.pArg);
153 void sqlite3PcacheShutdown(void){
154 if( sqlite3GlobalConfig.pcache2.xShutdown ){
155 /* IMPLEMENTATION-OF: R-26000-56589 The xShutdown() method may be NULL. */
156 sqlite3GlobalConfig.pcache2.xShutdown(sqlite3GlobalConfig.pcache2.pArg);
161 ** Return the size in bytes of a PCache object.
163 int sqlite3PcacheSize(void){ return sizeof(PCache); }
166 ** Create a new PCache object. Storage space to hold the object
167 ** has already been allocated and is passed in as the p pointer.
168 ** The caller discovers how much space needs to be allocated by
169 ** calling sqlite3PcacheSize().
171 int sqlite3PcacheOpen(
172 int szPage, /* Size of every page */
173 int szExtra, /* Extra space associated with each page */
174 int bPurgeable, /* True if pages are on backing store */
175 int (*xStress)(void*,PgHdr*),/* Call to try to make pages clean */
176 void *pStress, /* Argument to xStress */
177 PCache *p /* Preallocated space for the PCache */
179 memset(p, 0, sizeof(PCache));
180 p->szPage = 1;
181 p->szExtra = szExtra;
182 p->bPurgeable = bPurgeable;
183 p->eCreate = 2;
184 p->xStress = xStress;
185 p->pStress = pStress;
186 p->szCache = 100;
187 return sqlite3PcacheSetPageSize(p, szPage);
191 ** Change the page size for PCache object. The caller must ensure that there
192 ** are no outstanding page references when this function is called.
194 int sqlite3PcacheSetPageSize(PCache *pCache, int szPage){
195 assert( pCache->nRef==0 && pCache->pDirty==0 );
196 if( pCache->szPage ){
197 sqlite3_pcache *pNew;
198 pNew = sqlite3GlobalConfig.pcache2.xCreate(
199 szPage, pCache->szExtra + sizeof(PgHdr), pCache->bPurgeable
201 if( pNew==0 ) return SQLITE_NOMEM;
202 sqlite3GlobalConfig.pcache2.xCachesize(pNew, numberOfCachePages(pCache));
203 if( pCache->pCache ){
204 sqlite3GlobalConfig.pcache2.xDestroy(pCache->pCache);
206 pCache->pCache = pNew;
207 pCache->pPage1 = 0;
208 pCache->szPage = szPage;
210 return SQLITE_OK;
214 ** Try to obtain a page from the cache.
216 ** This routine returns a pointer to an sqlite3_pcache_page object if
217 ** such an object is already in cache, or if a new one is created.
218 ** This routine returns a NULL pointer if the object was not in cache
219 ** and could not be created.
221 ** The createFlags should be 0 to check for existing pages and should
222 ** be 3 (not 1, but 3) to try to create a new page.
224 ** If the createFlag is 0, then NULL is always returned if the page
225 ** is not already in the cache. If createFlag is 1, then a new page
226 ** is created only if that can be done without spilling dirty pages
227 ** and without exceeding the cache size limit.
229 ** The caller needs to invoke sqlite3PcacheFetchFinish() to properly
230 ** initialize the sqlite3_pcache_page object and convert it into a
231 ** PgHdr object. The sqlite3PcacheFetch() and sqlite3PcacheFetchFinish()
232 ** routines are split this way for performance reasons. When separated
233 ** they can both (usually) operate without having to push values to
234 ** the stack on entry and pop them back off on exit, which saves a
235 ** lot of pushing and popping.
237 sqlite3_pcache_page *sqlite3PcacheFetch(
238 PCache *pCache, /* Obtain the page from this cache */
239 Pgno pgno, /* Page number to obtain */
240 int createFlag /* If true, create page if it does not exist already */
242 int eCreate;
244 assert( pCache!=0 );
245 assert( pCache->pCache!=0 );
246 assert( createFlag==3 || createFlag==0 );
247 assert( pgno>0 );
249 /* eCreate defines what to do if the page does not exist.
250 ** 0 Do not allocate a new page. (createFlag==0)
251 ** 1 Allocate a new page if doing so is inexpensive.
252 ** (createFlag==1 AND bPurgeable AND pDirty)
253 ** 2 Allocate a new page even it doing so is difficult.
254 ** (createFlag==1 AND !(bPurgeable AND pDirty)
256 eCreate = createFlag & pCache->eCreate;
257 assert( eCreate==0 || eCreate==1 || eCreate==2 );
258 assert( createFlag==0 || pCache->eCreate==eCreate );
259 assert( createFlag==0 || eCreate==1+(!pCache->bPurgeable||!pCache->pDirty) );
260 return sqlite3GlobalConfig.pcache2.xFetch(pCache->pCache, pgno, eCreate);
264 ** If the sqlite3PcacheFetch() routine is unable to allocate a new
265 ** page because new clean pages are available for reuse and the cache
266 ** size limit has been reached, then this routine can be invoked to
267 ** try harder to allocate a page. This routine might invoke the stress
268 ** callback to spill dirty pages to the journal. It will then try to
269 ** allocate the new page and will only fail to allocate a new page on
270 ** an OOM error.
272 ** This routine should be invoked only after sqlite3PcacheFetch() fails.
274 int sqlite3PcacheFetchStress(
275 PCache *pCache, /* Obtain the page from this cache */
276 Pgno pgno, /* Page number to obtain */
277 sqlite3_pcache_page **ppPage /* Write result here */
279 PgHdr *pPg;
280 if( pCache->eCreate==2 ) return 0;
283 /* Find a dirty page to write-out and recycle. First try to find a
284 ** page that does not require a journal-sync (one with PGHDR_NEED_SYNC
285 ** cleared), but if that is not possible settle for any other
286 ** unreferenced dirty page.
288 for(pPg=pCache->pSynced;
289 pPg && (pPg->nRef || (pPg->flags&PGHDR_NEED_SYNC));
290 pPg=pPg->pDirtyPrev
292 pCache->pSynced = pPg;
293 if( !pPg ){
294 for(pPg=pCache->pDirtyTail; pPg && pPg->nRef; pPg=pPg->pDirtyPrev);
296 if( pPg ){
297 int rc;
298 #ifdef SQLITE_LOG_CACHE_SPILL
299 sqlite3_log(SQLITE_FULL,
300 "spill page %d making room for %d - cache used: %d/%d",
301 pPg->pgno, pgno,
302 sqlite3GlobalConfig.pcache.xPagecount(pCache->pCache),
303 numberOfCachePages(pCache));
304 #endif
305 rc = pCache->xStress(pCache->pStress, pPg);
306 if( rc!=SQLITE_OK && rc!=SQLITE_BUSY ){
307 return rc;
310 *ppPage = sqlite3GlobalConfig.pcache2.xFetch(pCache->pCache, pgno, 2);
311 return *ppPage==0 ? SQLITE_NOMEM : SQLITE_OK;
315 ** This is a helper routine for sqlite3PcacheFetchFinish()
317 ** In the uncommon case where the page being fetched has not been
318 ** initialized, this routine is invoked to do the initialization.
319 ** This routine is broken out into a separate function since it
320 ** requires extra stack manipulation that can be avoided in the common
321 ** case.
323 static SQLITE_NOINLINE PgHdr *pcacheFetchFinishWithInit(
324 PCache *pCache, /* Obtain the page from this cache */
325 Pgno pgno, /* Page number obtained */
326 sqlite3_pcache_page *pPage /* Page obtained by prior PcacheFetch() call */
328 PgHdr *pPgHdr;
329 assert( pPage!=0 );
330 pPgHdr = (PgHdr*)pPage->pExtra;
331 assert( pPgHdr->pPage==0 );
332 memset(pPgHdr, 0, sizeof(PgHdr));
333 pPgHdr->pPage = pPage;
334 pPgHdr->pData = pPage->pBuf;
335 pPgHdr->pExtra = (void *)&pPgHdr[1];
336 memset(pPgHdr->pExtra, 0, pCache->szExtra);
337 pPgHdr->pCache = pCache;
338 pPgHdr->pgno = pgno;
339 return sqlite3PcacheFetchFinish(pCache,pgno,pPage);
343 ** This routine converts the sqlite3_pcache_page object returned by
344 ** sqlite3PcacheFetch() into an initialized PgHdr object. This routine
345 ** must be called after sqlite3PcacheFetch() in order to get a usable
346 ** result.
348 PgHdr *sqlite3PcacheFetchFinish(
349 PCache *pCache, /* Obtain the page from this cache */
350 Pgno pgno, /* Page number obtained */
351 sqlite3_pcache_page *pPage /* Page obtained by prior PcacheFetch() call */
353 PgHdr *pPgHdr;
355 if( pPage==0 ) return 0;
356 pPgHdr = (PgHdr *)pPage->pExtra;
358 if( !pPgHdr->pPage ){
359 return pcacheFetchFinishWithInit(pCache, pgno, pPage);
361 if( 0==pPgHdr->nRef ){
362 pCache->nRef++;
364 pPgHdr->nRef++;
365 if( pgno==1 ){
366 pCache->pPage1 = pPgHdr;
368 return pPgHdr;
372 ** Decrement the reference count on a page. If the page is clean and the
373 ** reference count drops to 0, then it is made eligible for recycling.
375 void SQLITE_NOINLINE sqlite3PcacheRelease(PgHdr *p){
376 assert( p->nRef>0 );
377 p->nRef--;
378 if( p->nRef==0 ){
379 p->pCache->nRef--;
380 if( (p->flags&PGHDR_DIRTY)==0 ){
381 pcacheUnpin(p);
382 }else if( p->pDirtyPrev!=0 ){
383 /* Move the page to the head of the dirty list. */
384 pcacheManageDirtyList(p, PCACHE_DIRTYLIST_FRONT);
390 ** Increase the reference count of a supplied page by 1.
392 void sqlite3PcacheRef(PgHdr *p){
393 assert(p->nRef>0);
394 p->nRef++;
398 ** Drop a page from the cache. There must be exactly one reference to the
399 ** page. This function deletes that reference, so after it returns the
400 ** page pointed to by p is invalid.
402 void sqlite3PcacheDrop(PgHdr *p){
403 assert( p->nRef==1 );
404 if( p->flags&PGHDR_DIRTY ){
405 pcacheManageDirtyList(p, PCACHE_DIRTYLIST_REMOVE);
407 p->pCache->nRef--;
408 if( p->pgno==1 ){
409 p->pCache->pPage1 = 0;
411 sqlite3GlobalConfig.pcache2.xUnpin(p->pCache->pCache, p->pPage, 1);
415 ** Make sure the page is marked as dirty. If it isn't dirty already,
416 ** make it so.
418 void sqlite3PcacheMakeDirty(PgHdr *p){
419 p->flags &= ~PGHDR_DONT_WRITE;
420 assert( p->nRef>0 );
421 if( 0==(p->flags & PGHDR_DIRTY) ){
422 p->flags |= PGHDR_DIRTY;
423 pcacheManageDirtyList(p, PCACHE_DIRTYLIST_ADD);
428 ** Make sure the page is marked as clean. If it isn't clean already,
429 ** make it so.
431 void sqlite3PcacheMakeClean(PgHdr *p){
432 if( (p->flags & PGHDR_DIRTY) ){
433 pcacheManageDirtyList(p, PCACHE_DIRTYLIST_REMOVE);
434 p->flags &= ~(PGHDR_DIRTY|PGHDR_NEED_SYNC);
435 if( p->nRef==0 ){
436 pcacheUnpin(p);
442 ** Make every page in the cache clean.
444 void sqlite3PcacheCleanAll(PCache *pCache){
445 PgHdr *p;
446 while( (p = pCache->pDirty)!=0 ){
447 sqlite3PcacheMakeClean(p);
452 ** Clear the PGHDR_NEED_SYNC flag from all dirty pages.
454 void sqlite3PcacheClearSyncFlags(PCache *pCache){
455 PgHdr *p;
456 for(p=pCache->pDirty; p; p=p->pDirtyNext){
457 p->flags &= ~PGHDR_NEED_SYNC;
459 pCache->pSynced = pCache->pDirtyTail;
463 ** Change the page number of page p to newPgno.
465 void sqlite3PcacheMove(PgHdr *p, Pgno newPgno){
466 PCache *pCache = p->pCache;
467 assert( p->nRef>0 );
468 assert( newPgno>0 );
469 sqlite3GlobalConfig.pcache2.xRekey(pCache->pCache, p->pPage, p->pgno,newPgno);
470 p->pgno = newPgno;
471 if( (p->flags&PGHDR_DIRTY) && (p->flags&PGHDR_NEED_SYNC) ){
472 pcacheManageDirtyList(p, PCACHE_DIRTYLIST_FRONT);
477 ** Drop every cache entry whose page number is greater than "pgno". The
478 ** caller must ensure that there are no outstanding references to any pages
479 ** other than page 1 with a page number greater than pgno.
481 ** If there is a reference to page 1 and the pgno parameter passed to this
482 ** function is 0, then the data area associated with page 1 is zeroed, but
483 ** the page object is not dropped.
485 void sqlite3PcacheTruncate(PCache *pCache, Pgno pgno){
486 if( pCache->pCache ){
487 PgHdr *p;
488 PgHdr *pNext;
489 for(p=pCache->pDirty; p; p=pNext){
490 pNext = p->pDirtyNext;
491 /* This routine never gets call with a positive pgno except right
492 ** after sqlite3PcacheCleanAll(). So if there are dirty pages,
493 ** it must be that pgno==0.
495 assert( p->pgno>0 );
496 if( ALWAYS(p->pgno>pgno) ){
497 assert( p->flags&PGHDR_DIRTY );
498 sqlite3PcacheMakeClean(p);
501 if( pgno==0 && pCache->pPage1 ){
502 memset(pCache->pPage1->pData, 0, pCache->szPage);
503 pgno = 1;
505 sqlite3GlobalConfig.pcache2.xTruncate(pCache->pCache, pgno+1);
510 ** Close a cache.
512 void sqlite3PcacheClose(PCache *pCache){
513 assert( pCache->pCache!=0 );
514 sqlite3GlobalConfig.pcache2.xDestroy(pCache->pCache);
518 ** Discard the contents of the cache.
520 void sqlite3PcacheClear(PCache *pCache){
521 sqlite3PcacheTruncate(pCache, 0);
525 ** Merge two lists of pages connected by pDirty and in pgno order.
526 ** Do not both fixing the pDirtyPrev pointers.
528 static PgHdr *pcacheMergeDirtyList(PgHdr *pA, PgHdr *pB){
529 PgHdr result, *pTail;
530 pTail = &result;
531 while( pA && pB ){
532 if( pA->pgno<pB->pgno ){
533 pTail->pDirty = pA;
534 pTail = pA;
535 pA = pA->pDirty;
536 }else{
537 pTail->pDirty = pB;
538 pTail = pB;
539 pB = pB->pDirty;
542 if( pA ){
543 pTail->pDirty = pA;
544 }else if( pB ){
545 pTail->pDirty = pB;
546 }else{
547 pTail->pDirty = 0;
549 return result.pDirty;
553 ** Sort the list of pages in accending order by pgno. Pages are
554 ** connected by pDirty pointers. The pDirtyPrev pointers are
555 ** corrupted by this sort.
557 ** Since there cannot be more than 2^31 distinct pages in a database,
558 ** there cannot be more than 31 buckets required by the merge sorter.
559 ** One extra bucket is added to catch overflow in case something
560 ** ever changes to make the previous sentence incorrect.
562 #define N_SORT_BUCKET 32
563 static PgHdr *pcacheSortDirtyList(PgHdr *pIn){
564 PgHdr *a[N_SORT_BUCKET], *p;
565 int i;
566 memset(a, 0, sizeof(a));
567 while( pIn ){
568 p = pIn;
569 pIn = p->pDirty;
570 p->pDirty = 0;
571 for(i=0; ALWAYS(i<N_SORT_BUCKET-1); i++){
572 if( a[i]==0 ){
573 a[i] = p;
574 break;
575 }else{
576 p = pcacheMergeDirtyList(a[i], p);
577 a[i] = 0;
580 if( NEVER(i==N_SORT_BUCKET-1) ){
581 /* To get here, there need to be 2^(N_SORT_BUCKET) elements in
582 ** the input list. But that is impossible.
584 a[i] = pcacheMergeDirtyList(a[i], p);
587 p = a[0];
588 for(i=1; i<N_SORT_BUCKET; i++){
589 p = pcacheMergeDirtyList(p, a[i]);
591 return p;
595 ** Return a list of all dirty pages in the cache, sorted by page number.
597 PgHdr *sqlite3PcacheDirtyList(PCache *pCache){
598 PgHdr *p;
599 for(p=pCache->pDirty; p; p=p->pDirtyNext){
600 p->pDirty = p->pDirtyNext;
602 return pcacheSortDirtyList(pCache->pDirty);
606 ** Return the total number of referenced pages held by the cache.
608 int sqlite3PcacheRefCount(PCache *pCache){
609 return pCache->nRef;
613 ** Return the number of references to the page supplied as an argument.
615 int sqlite3PcachePageRefcount(PgHdr *p){
616 return p->nRef;
620 ** Return the total number of pages in the cache.
622 int sqlite3PcachePagecount(PCache *pCache){
623 assert( pCache->pCache!=0 );
624 return sqlite3GlobalConfig.pcache2.xPagecount(pCache->pCache);
627 #ifdef SQLITE_TEST
629 ** Get the suggested cache-size value.
631 int sqlite3PcacheGetCachesize(PCache *pCache){
632 return numberOfCachePages(pCache);
634 #endif
637 ** Set the suggested cache-size value.
639 void sqlite3PcacheSetCachesize(PCache *pCache, int mxPage){
640 assert( pCache->pCache!=0 );
641 pCache->szCache = mxPage;
642 sqlite3GlobalConfig.pcache2.xCachesize(pCache->pCache,
643 numberOfCachePages(pCache));
647 ** Free up as much memory as possible from the page cache.
649 void sqlite3PcacheShrink(PCache *pCache){
650 assert( pCache->pCache!=0 );
651 sqlite3GlobalConfig.pcache2.xShrink(pCache->pCache);
654 #if defined(SQLITE_CHECK_PAGES) || defined(SQLITE_DEBUG)
656 ** For all dirty pages currently in the cache, invoke the specified
657 ** callback. This is only used if the SQLITE_CHECK_PAGES macro is
658 ** defined.
660 void sqlite3PcacheIterateDirty(PCache *pCache, void (*xIter)(PgHdr *)){
661 PgHdr *pDirty;
662 for(pDirty=pCache->pDirty; pDirty; pDirty=pDirty->pDirtyNext){
663 xIter(pDirty);
666 #endif