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.
10: **
11: *************************************************************************
12: ** This file implements that page cache.
13: */
14: #include "sqliteInt.h"
15:
16: /*
17: ** A complete page cache is an instance of this structure.
18: */
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: 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 */
31: };
32:
33: /*
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.
38: */
39: #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
40: # define expensive_assert(X) assert(X)
41: #else
42: # define expensive_assert(X)
43: #endif
44:
45: /********************************** Linked List Management ********************/
46:
47: #if !defined(NDEBUG) && defined(SQLITE_ENABLE_EXPENSIVE_ASSERT)
48: /*
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:
52: **
53: ** expensive_assert( pcacheCheckSynced(pCache) );
54: */
55: static int pcacheCheckSynced(PCache *pCache){
56: PgHdr *p;
57: for(p=pCache->pDirtyTail; p!=pCache->pSynced; p=p->pDirtyPrev){
58: assert( p->nRef || (p->flags&PGHDR_NEED_SYNC) );
59: }
60: return (p==0 || p->nRef || (p->flags&PGHDR_NEED_SYNC)==0);
61: }
62: #endif /* !NDEBUG && SQLITE_ENABLE_EXPENSIVE_ASSERT */
63:
64: /*
65: ** Remove page pPage from the list of dirty pages.
66: */
67: static void pcacheRemoveFromDirtyList(PgHdr *pPage){
68: PCache *p = pPage->pCache;
69:
70: assert( pPage->pDirtyNext || pPage==p->pDirtyTail );
71: assert( pPage->pDirtyPrev || pPage==p->pDirty );
72:
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;
78: }
79: p->pSynced = pSynced;
80: }
81:
82: if( pPage->pDirtyNext ){
83: pPage->pDirtyNext->pDirtyPrev = pPage->pDirtyPrev;
84: }else{
85: assert( pPage==p->pDirtyTail );
86: p->pDirtyTail = pPage->pDirtyPrev;
87: }
88: if( pPage->pDirtyPrev ){
89: pPage->pDirtyPrev->pDirtyNext = pPage->pDirtyNext;
90: }else{
91: assert( pPage==p->pDirty );
92: p->pDirty = pPage->pDirtyNext;
93: }
94: pPage->pDirtyNext = 0;
95: pPage->pDirtyPrev = 0;
96:
97: expensive_assert( pcacheCheckSynced(p) );
98: }
99:
100: /*
101: ** Add page pPage to the head of the dirty list (PCache1.pDirty is set to
102: ** pPage).
103: */
104: static void pcacheAddToDirtyList(PgHdr *pPage){
105: PCache *p = pPage->pCache;
106:
107: assert( pPage->pDirtyNext==0 && pPage->pDirtyPrev==0 && p->pDirty!=pPage );
108:
109: pPage->pDirtyNext = p->pDirty;
110: if( pPage->pDirtyNext ){
111: assert( pPage->pDirtyNext->pDirtyPrev==0 );
112: pPage->pDirtyNext->pDirtyPrev = pPage;
113: }
114: p->pDirty = pPage;
115: if( !p->pDirtyTail ){
116: p->pDirtyTail = pPage;
117: }
118: if( !p->pSynced && 0==(pPage->flags&PGHDR_NEED_SYNC) ){
119: p->pSynced = pPage;
120: }
121: expensive_assert( pcacheCheckSynced(p) );
122: }
123:
124: /*
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.
127: */
128: static void pcacheUnpin(PgHdr *p){
129: PCache *pCache = p->pCache;
130: if( pCache->bPurgeable ){
131: if( p->pgno==1 ){
132: pCache->pPage1 = 0;
133: }
134: sqlite3GlobalConfig.pcache2.xUnpin(pCache->pCache, p->pPage, 0);
135: }
136: }
137:
138: /*************************************************** General Interfaces ******
139: **
140: ** Initialize and shutdown the page cache subsystem. Neither of these
141: ** functions are threadsafe.
142: */
143: int sqlite3PcacheInitialize(void){
144: if( sqlite3GlobalConfig.pcache2.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
147: ** page cache. */
148: sqlite3PCacheSetDefault();
149: }
150: return sqlite3GlobalConfig.pcache2.xInit(sqlite3GlobalConfig.pcache2.pArg);
151: }
152: void sqlite3PcacheShutdown(void){
153: if( sqlite3GlobalConfig.pcache2.xShutdown ){
154: /* IMPLEMENTATION-OF: R-26000-56589 The xShutdown() method may be NULL. */
155: sqlite3GlobalConfig.pcache2.xShutdown(sqlite3GlobalConfig.pcache2.pArg);
156: }
157: }
158:
159: /*
160: ** Return the size in bytes of a PCache object.
161: */
162: int sqlite3PcacheSize(void){ return sizeof(PCache); }
163:
164: /*
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().
169: */
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 */
177: ){
178: memset(p, 0, sizeof(PCache));
179: p->szPage = szPage;
180: p->szExtra = szExtra;
181: p->bPurgeable = bPurgeable;
182: p->xStress = xStress;
183: p->pStress = pStress;
184: p->szCache = 100;
185: }
186:
187: /*
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.
190: */
191: void sqlite3PcacheSetPageSize(PCache *pCache, int szPage){
192: assert( pCache->nRef==0 && pCache->pDirty==0 );
193: if( pCache->pCache ){
194: sqlite3GlobalConfig.pcache2.xDestroy(pCache->pCache);
195: pCache->pCache = 0;
196: pCache->pPage1 = 0;
197: }
198: pCache->szPage = szPage;
199: }
200:
201: /*
202: ** Compute the number of pages of cache requested.
203: */
204: static int numberOfCachePages(PCache *p){
205: if( p->szCache>=0 ){
206: return p->szCache;
207: }else{
208: return (int)((-1024*(i64)p->szCache)/(p->szPage+p->szExtra));
209: }
210: }
211:
212: /*
213: ** Try to obtain a page from the cache.
214: */
215: int sqlite3PcacheFetch(
216: PCache *pCache, /* Obtain the page from this cache */
217: Pgno pgno, /* Page number to obtain */
218: int createFlag, /* If true, create page if it does not exist already */
219: PgHdr **ppPage /* Write the page here */
220: ){
221: sqlite3_pcache_page *pPage = 0;
222: PgHdr *pPgHdr = 0;
223: int eCreate;
224:
225: assert( pCache!=0 );
226: assert( createFlag==1 || createFlag==0 );
227: assert( pgno>0 );
228:
229: /* If the pluggable cache (sqlite3_pcache*) has not been allocated,
230: ** allocate it now.
231: */
232: if( !pCache->pCache && createFlag ){
233: sqlite3_pcache *p;
234: p = sqlite3GlobalConfig.pcache2.xCreate(
235: pCache->szPage, pCache->szExtra + sizeof(PgHdr), pCache->bPurgeable
236: );
237: if( !p ){
238: return SQLITE_NOMEM;
239: }
240: sqlite3GlobalConfig.pcache2.xCachesize(p, numberOfCachePages(pCache));
241: pCache->pCache = p;
242: }
243:
244: eCreate = createFlag * (1 + (!pCache->bPurgeable || !pCache->pDirty));
245: if( pCache->pCache ){
246: pPage = sqlite3GlobalConfig.pcache2.xFetch(pCache->pCache, pgno, eCreate);
247: }
248:
249: if( !pPage && eCreate==1 ){
250: PgHdr *pPg;
251:
252: /* Find a dirty page to write-out and recycle. First try to find a
253: ** page that does not require a journal-sync (one with PGHDR_NEED_SYNC
254: ** cleared), but if that is not possible settle for any other
255: ** unreferenced dirty page.
256: */
257: expensive_assert( pcacheCheckSynced(pCache) );
258: for(pPg=pCache->pSynced;
259: pPg && (pPg->nRef || (pPg->flags&PGHDR_NEED_SYNC));
260: pPg=pPg->pDirtyPrev
261: );
262: pCache->pSynced = pPg;
263: if( !pPg ){
264: for(pPg=pCache->pDirtyTail; pPg && pPg->nRef; pPg=pPg->pDirtyPrev);
265: }
266: if( pPg ){
267: int rc;
268: #ifdef SQLITE_LOG_CACHE_SPILL
269: sqlite3_log(SQLITE_FULL,
270: "spill page %d making room for %d - cache used: %d/%d",
271: pPg->pgno, pgno,
272: sqlite3GlobalConfig.pcache.xPagecount(pCache->pCache),
273: numberOfCachePages(pCache));
274: #endif
275: rc = pCache->xStress(pCache->pStress, pPg);
276: if( rc!=SQLITE_OK && rc!=SQLITE_BUSY ){
277: return rc;
278: }
279: }
280:
281: pPage = sqlite3GlobalConfig.pcache2.xFetch(pCache->pCache, pgno, 2);
282: }
283:
284: if( pPage ){
285: pPgHdr = (PgHdr *)pPage->pExtra;
286:
287: if( !pPgHdr->pPage ){
288: memset(pPgHdr, 0, sizeof(PgHdr));
289: pPgHdr->pPage = pPage;
290: pPgHdr->pData = pPage->pBuf;
291: pPgHdr->pExtra = (void *)&pPgHdr[1];
292: memset(pPgHdr->pExtra, 0, pCache->szExtra);
293: pPgHdr->pCache = pCache;
294: pPgHdr->pgno = pgno;
295: }
296: assert( pPgHdr->pCache==pCache );
297: assert( pPgHdr->pgno==pgno );
298: assert( pPgHdr->pData==pPage->pBuf );
299: assert( pPgHdr->pExtra==(void *)&pPgHdr[1] );
300:
301: if( 0==pPgHdr->nRef ){
302: pCache->nRef++;
303: }
304: pPgHdr->nRef++;
305: if( pgno==1 ){
306: pCache->pPage1 = pPgHdr;
307: }
308: }
309: *ppPage = pPgHdr;
310: return (pPgHdr==0 && eCreate) ? SQLITE_NOMEM : SQLITE_OK;
311: }
312:
313: /*
314: ** Decrement the reference count on a page. If the page is clean and the
315: ** reference count drops to 0, then it is made elible for recycling.
316: */
317: void sqlite3PcacheRelease(PgHdr *p){
318: assert( p->nRef>0 );
319: p->nRef--;
320: if( p->nRef==0 ){
321: PCache *pCache = p->pCache;
322: pCache->nRef--;
323: if( (p->flags&PGHDR_DIRTY)==0 ){
324: pcacheUnpin(p);
325: }else{
326: /* Move the page to the head of the dirty list. */
327: pcacheRemoveFromDirtyList(p);
328: pcacheAddToDirtyList(p);
329: }
330: }
331: }
332:
333: /*
334: ** Increase the reference count of a supplied page by 1.
335: */
336: void sqlite3PcacheRef(PgHdr *p){
337: assert(p->nRef>0);
338: p->nRef++;
339: }
340:
341: /*
342: ** Drop a page from the cache. There must be exactly one reference to the
343: ** page. This function deletes that reference, so after it returns the
344: ** page pointed to by p is invalid.
345: */
346: void sqlite3PcacheDrop(PgHdr *p){
347: PCache *pCache;
348: assert( p->nRef==1 );
349: if( p->flags&PGHDR_DIRTY ){
350: pcacheRemoveFromDirtyList(p);
351: }
352: pCache = p->pCache;
353: pCache->nRef--;
354: if( p->pgno==1 ){
355: pCache->pPage1 = 0;
356: }
357: sqlite3GlobalConfig.pcache2.xUnpin(pCache->pCache, p->pPage, 1);
358: }
359:
360: /*
361: ** Make sure the page is marked as dirty. If it isn't dirty already,
362: ** make it so.
363: */
364: void sqlite3PcacheMakeDirty(PgHdr *p){
365: p->flags &= ~PGHDR_DONT_WRITE;
366: assert( p->nRef>0 );
367: if( 0==(p->flags & PGHDR_DIRTY) ){
368: p->flags |= PGHDR_DIRTY;
369: pcacheAddToDirtyList( p);
370: }
371: }
372:
373: /*
374: ** Make sure the page is marked as clean. If it isn't clean already,
375: ** make it so.
376: */
377: void sqlite3PcacheMakeClean(PgHdr *p){
378: if( (p->flags & PGHDR_DIRTY) ){
379: pcacheRemoveFromDirtyList(p);
380: p->flags &= ~(PGHDR_DIRTY|PGHDR_NEED_SYNC);
381: if( p->nRef==0 ){
382: pcacheUnpin(p);
383: }
384: }
385: }
386:
387: /*
388: ** Make every page in the cache clean.
389: */
390: void sqlite3PcacheCleanAll(PCache *pCache){
391: PgHdr *p;
392: while( (p = pCache->pDirty)!=0 ){
393: sqlite3PcacheMakeClean(p);
394: }
395: }
396:
397: /*
398: ** Clear the PGHDR_NEED_SYNC flag from all dirty pages.
399: */
400: void sqlite3PcacheClearSyncFlags(PCache *pCache){
401: PgHdr *p;
402: for(p=pCache->pDirty; p; p=p->pDirtyNext){
403: p->flags &= ~PGHDR_NEED_SYNC;
404: }
405: pCache->pSynced = pCache->pDirtyTail;
406: }
407:
408: /*
409: ** Change the page number of page p to newPgno.
410: */
411: void sqlite3PcacheMove(PgHdr *p, Pgno newPgno){
412: PCache *pCache = p->pCache;
413: assert( p->nRef>0 );
414: assert( newPgno>0 );
415: sqlite3GlobalConfig.pcache2.xRekey(pCache->pCache, p->pPage, p->pgno,newPgno);
416: p->pgno = newPgno;
417: if( (p->flags&PGHDR_DIRTY) && (p->flags&PGHDR_NEED_SYNC) ){
418: pcacheRemoveFromDirtyList(p);
419: pcacheAddToDirtyList(p);
420: }
421: }
422:
423: /*
424: ** Drop every cache entry whose page number is greater than "pgno". The
425: ** caller must ensure that there are no outstanding references to any pages
426: ** other than page 1 with a page number greater than pgno.
427: **
428: ** If there is a reference to page 1 and the pgno parameter passed to this
429: ** function is 0, then the data area associated with page 1 is zeroed, but
430: ** the page object is not dropped.
431: */
432: void sqlite3PcacheTruncate(PCache *pCache, Pgno pgno){
433: if( pCache->pCache ){
434: PgHdr *p;
435: PgHdr *pNext;
436: for(p=pCache->pDirty; p; p=pNext){
437: pNext = p->pDirtyNext;
438: /* This routine never gets call with a positive pgno except right
439: ** after sqlite3PcacheCleanAll(). So if there are dirty pages,
440: ** it must be that pgno==0.
441: */
442: assert( p->pgno>0 );
443: if( ALWAYS(p->pgno>pgno) ){
444: assert( p->flags&PGHDR_DIRTY );
445: sqlite3PcacheMakeClean(p);
446: }
447: }
448: if( pgno==0 && pCache->pPage1 ){
449: memset(pCache->pPage1->pData, 0, pCache->szPage);
450: pgno = 1;
451: }
452: sqlite3GlobalConfig.pcache2.xTruncate(pCache->pCache, pgno+1);
453: }
454: }
455:
456: /*
457: ** Close a cache.
458: */
459: void sqlite3PcacheClose(PCache *pCache){
460: if( pCache->pCache ){
461: sqlite3GlobalConfig.pcache2.xDestroy(pCache->pCache);
462: }
463: }
464:
465: /*
466: ** Discard the contents of the cache.
467: */
468: void sqlite3PcacheClear(PCache *pCache){
469: sqlite3PcacheTruncate(pCache, 0);
470: }
471:
472: /*
473: ** Merge two lists of pages connected by pDirty and in pgno order.
474: ** Do not both fixing the pDirtyPrev pointers.
475: */
476: static PgHdr *pcacheMergeDirtyList(PgHdr *pA, PgHdr *pB){
477: PgHdr result, *pTail;
478: pTail = &result;
479: while( pA && pB ){
480: if( pA->pgno<pB->pgno ){
481: pTail->pDirty = pA;
482: pTail = pA;
483: pA = pA->pDirty;
484: }else{
485: pTail->pDirty = pB;
486: pTail = pB;
487: pB = pB->pDirty;
488: }
489: }
490: if( pA ){
491: pTail->pDirty = pA;
492: }else if( pB ){
493: pTail->pDirty = pB;
494: }else{
495: pTail->pDirty = 0;
496: }
497: return result.pDirty;
498: }
499:
500: /*
501: ** Sort the list of pages in accending order by pgno. Pages are
502: ** connected by pDirty pointers. The pDirtyPrev pointers are
503: ** corrupted by this sort.
504: **
505: ** Since there cannot be more than 2^31 distinct pages in a database,
506: ** there cannot be more than 31 buckets required by the merge sorter.
507: ** One extra bucket is added to catch overflow in case something
508: ** ever changes to make the previous sentence incorrect.
509: */
510: #define N_SORT_BUCKET 32
511: static PgHdr *pcacheSortDirtyList(PgHdr *pIn){
512: PgHdr *a[N_SORT_BUCKET], *p;
513: int i;
514: memset(a, 0, sizeof(a));
515: while( pIn ){
516: p = pIn;
517: pIn = p->pDirty;
518: p->pDirty = 0;
519: for(i=0; ALWAYS(i<N_SORT_BUCKET-1); i++){
520: if( a[i]==0 ){
521: a[i] = p;
522: break;
523: }else{
524: p = pcacheMergeDirtyList(a[i], p);
525: a[i] = 0;
526: }
527: }
528: if( NEVER(i==N_SORT_BUCKET-1) ){
529: /* To get here, there need to be 2^(N_SORT_BUCKET) elements in
530: ** the input list. But that is impossible.
531: */
532: a[i] = pcacheMergeDirtyList(a[i], p);
533: }
534: }
535: p = a[0];
536: for(i=1; i<N_SORT_BUCKET; i++){
537: p = pcacheMergeDirtyList(p, a[i]);
538: }
539: return p;
540: }
541:
542: /*
543: ** Return a list of all dirty pages in the cache, sorted by page number.
544: */
545: PgHdr *sqlite3PcacheDirtyList(PCache *pCache){
546: PgHdr *p;
547: for(p=pCache->pDirty; p; p=p->pDirtyNext){
548: p->pDirty = p->pDirtyNext;
549: }
550: return pcacheSortDirtyList(pCache->pDirty);
551: }
552:
553: /*
554: ** Return the total number of referenced pages held by the cache.
555: */
556: int sqlite3PcacheRefCount(PCache *pCache){
557: return pCache->nRef;
558: }
559:
560: /*
561: ** Return the number of references to the page supplied as an argument.
562: */
563: int sqlite3PcachePageRefcount(PgHdr *p){
564: return p->nRef;
565: }
566:
567: /*
568: ** Return the total number of pages in the cache.
569: */
570: int sqlite3PcachePagecount(PCache *pCache){
571: int nPage = 0;
572: if( pCache->pCache ){
573: nPage = sqlite3GlobalConfig.pcache2.xPagecount(pCache->pCache);
574: }
575: return nPage;
576: }
577:
578: #ifdef SQLITE_TEST
579: /*
580: ** Get the suggested cache-size value.
581: */
582: int sqlite3PcacheGetCachesize(PCache *pCache){
583: return numberOfCachePages(pCache);
584: }
585: #endif
586:
587: /*
588: ** Set the suggested cache-size value.
589: */
590: void sqlite3PcacheSetCachesize(PCache *pCache, int mxPage){
591: pCache->szCache = mxPage;
592: if( pCache->pCache ){
593: sqlite3GlobalConfig.pcache2.xCachesize(pCache->pCache,
594: numberOfCachePages(pCache));
595: }
596: }
597:
598: /*
599: ** Free up as much memory as possible from the page cache.
600: */
601: void sqlite3PcacheShrink(PCache *pCache){
602: if( pCache->pCache ){
603: sqlite3GlobalConfig.pcache2.xShrink(pCache->pCache);
604: }
605: }
606:
607: #if defined(SQLITE_CHECK_PAGES) || defined(SQLITE_DEBUG)
608: /*
609: ** For all dirty pages currently in the cache, invoke the specified
610: ** callback. This is only used if the SQLITE_CHECK_PAGES macro is
611: ** defined.
612: */
613: void sqlite3PcacheIterateDirty(PCache *pCache, void (*xIter)(PgHdr *)){
614: PgHdr *pDirty;
615: for(pDirty=pCache->pDirty; pDirty; pDirty=pDirty->pDirtyNext){
616: xIter(pDirty);
617: }
618: }
619: #endif
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to pcache.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [ELWIX - Embedded LightWeight unIX -] / embedaddon / sqlite3 / src