Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(300)

Side by Side Diff: third_party/sqlite/src/pcache.c

Issue 3108030: Move bundled copy of sqlite one level deeper to better separate it... (Closed) Base URL: svn://svn.chromium.org/chrome/trunk/src/
Patch Set: Created 10 years, 4 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch | Annotate | Revision Log
« no previous file with comments | « third_party/sqlite/src/pcache.h ('k') | third_party/sqlite/src/pcache1.c » ('j') | no next file with comments »
Toggle Intra-line Diffs ('i') | Expand Comments ('e') | Collapse Comments ('c') | Show Comments Hide Comments ('s')
OLDNEW
(Empty)
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 ** @(#) $Id: pcache.c,v 1.47 2009/07/25 11:46:49 danielk1977 Exp $
15 */
16 #include "sqliteInt.h"
17
18 /*
19 ** A complete page cache is an instance of this structure.
20 */
21 struct PCache {
22 PgHdr *pDirty, *pDirtyTail; /* List of dirty pages in LRU order */
23 PgHdr *pSynced; /* Last synced page in dirty page list */
24 int nRef; /* Number of referenced pages */
25 int nMax; /* Configured cache size */
26 int szPage; /* Size of every page in this cache */
27 int szExtra; /* Size of extra space for each page */
28 int bPurgeable; /* True if pages are on backing store */
29 int (*xStress)(void*,PgHdr*); /* Call to try make a page clean */
30 void *pStress; /* Argument to xStress */
31 sqlite3_pcache *pCache; /* Pluggable cache module */
32 PgHdr *pPage1; /* Reference to page 1 */
33 };
34
35 /*
36 ** Some of the assert() macros in this code are too expensive to run
37 ** even during normal debugging. Use them only rarely on long-running
38 ** tests. Enable the expensive asserts using the
39 ** -DSQLITE_ENABLE_EXPENSIVE_ASSERT=1 compile-time option.
40 */
41 #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
42 # define expensive_assert(X) assert(X)
43 #else
44 # define expensive_assert(X)
45 #endif
46
47 /********************************** Linked List Management ********************/
48
49 #if !defined(NDEBUG) && defined(SQLITE_ENABLE_EXPENSIVE_ASSERT)
50 /*
51 ** Check that the pCache->pSynced variable is set correctly. If it
52 ** is not, either fail an assert or return zero. Otherwise, return
53 ** non-zero. This is only used in debugging builds, as follows:
54 **
55 ** expensive_assert( pcacheCheckSynced(pCache) );
56 */
57 static int pcacheCheckSynced(PCache *pCache){
58 PgHdr *p;
59 for(p=pCache->pDirtyTail; p!=pCache->pSynced; p=p->pDirtyPrev){
60 assert( p->nRef || (p->flags&PGHDR_NEED_SYNC) );
61 }
62 return (p==0 || p->nRef || (p->flags&PGHDR_NEED_SYNC)==0);
63 }
64 #endif /* !NDEBUG && SQLITE_ENABLE_EXPENSIVE_ASSERT */
65
66 /*
67 ** Remove page pPage from the list of dirty pages.
68 */
69 static void pcacheRemoveFromDirtyList(PgHdr *pPage){
70 PCache *p = pPage->pCache;
71
72 assert( pPage->pDirtyNext || pPage==p->pDirtyTail );
73 assert( pPage->pDirtyPrev || pPage==p->pDirty );
74
75 /* Update the PCache1.pSynced variable if necessary. */
76 if( p->pSynced==pPage ){
77 PgHdr *pSynced = pPage->pDirtyPrev;
78 while( pSynced && (pSynced->flags&PGHDR_NEED_SYNC) ){
79 pSynced = pSynced->pDirtyPrev;
80 }
81 p->pSynced = pSynced;
82 }
83
84 if( pPage->pDirtyNext ){
85 pPage->pDirtyNext->pDirtyPrev = pPage->pDirtyPrev;
86 }else{
87 assert( pPage==p->pDirtyTail );
88 p->pDirtyTail = pPage->pDirtyPrev;
89 }
90 if( pPage->pDirtyPrev ){
91 pPage->pDirtyPrev->pDirtyNext = pPage->pDirtyNext;
92 }else{
93 assert( pPage==p->pDirty );
94 p->pDirty = pPage->pDirtyNext;
95 }
96 pPage->pDirtyNext = 0;
97 pPage->pDirtyPrev = 0;
98
99 expensive_assert( pcacheCheckSynced(p) );
100 }
101
102 /*
103 ** Add page pPage to the head of the dirty list (PCache1.pDirty is set to
104 ** pPage).
105 */
106 static void pcacheAddToDirtyList(PgHdr *pPage){
107 PCache *p = pPage->pCache;
108
109 assert( pPage->pDirtyNext==0 && pPage->pDirtyPrev==0 && p->pDirty!=pPage );
110
111 pPage->pDirtyNext = p->pDirty;
112 if( pPage->pDirtyNext ){
113 assert( pPage->pDirtyNext->pDirtyPrev==0 );
114 pPage->pDirtyNext->pDirtyPrev = pPage;
115 }
116 p->pDirty = pPage;
117 if( !p->pDirtyTail ){
118 p->pDirtyTail = pPage;
119 }
120 if( !p->pSynced && 0==(pPage->flags&PGHDR_NEED_SYNC) ){
121 p->pSynced = pPage;
122 }
123 expensive_assert( pcacheCheckSynced(p) );
124 }
125
126 /*
127 ** Wrapper around the pluggable caches xUnpin method. If the cache is
128 ** being used for an in-memory database, this function is a no-op.
129 */
130 static void pcacheUnpin(PgHdr *p){
131 PCache *pCache = p->pCache;
132 if( pCache->bPurgeable ){
133 if( p->pgno==1 ){
134 pCache->pPage1 = 0;
135 }
136 sqlite3GlobalConfig.pcache.xUnpin(pCache->pCache, p, 0);
137 }
138 }
139
140 /*************************************************** General Interfaces ******
141 **
142 ** Initialize and shutdown the page cache subsystem. Neither of these
143 ** functions are threadsafe.
144 */
145 int sqlite3PcacheInitialize(void){
146 if( sqlite3GlobalConfig.pcache.xInit==0 ){
147 sqlite3PCacheSetDefault();
148 }
149 return sqlite3GlobalConfig.pcache.xInit(sqlite3GlobalConfig.pcache.pArg);
150 }
151 void sqlite3PcacheShutdown(void){
152 if( sqlite3GlobalConfig.pcache.xShutdown ){
153 sqlite3GlobalConfig.pcache.xShutdown(sqlite3GlobalConfig.pcache.pArg);
154 }
155 }
156
157 /*
158 ** Return the size in bytes of a PCache object.
159 */
160 int sqlite3PcacheSize(void){ return sizeof(PCache); }
161
162 /*
163 ** Create a new PCache object. Storage space to hold the object
164 ** has already been allocated and is passed in as the p pointer.
165 ** The caller discovers how much space needs to be allocated by
166 ** calling sqlite3PcacheSize().
167 */
168 void sqlite3PcacheOpen(
169 int szPage, /* Size of every page */
170 int szExtra, /* Extra space associated with each page */
171 int bPurgeable, /* True if pages are on backing store */
172 int (*xStress)(void*,PgHdr*),/* Call to try to make pages clean */
173 void *pStress, /* Argument to xStress */
174 PCache *p /* Preallocated space for the PCache */
175 ){
176 memset(p, 0, sizeof(PCache));
177 p->szPage = szPage;
178 p->szExtra = szExtra;
179 p->bPurgeable = bPurgeable;
180 p->xStress = xStress;
181 p->pStress = pStress;
182 p->nMax = 100;
183 }
184
185 /*
186 ** Change the page size for PCache object. The caller must ensure that there
187 ** are no outstanding page references when this function is called.
188 */
189 void sqlite3PcacheSetPageSize(PCache *pCache, int szPage){
190 assert( pCache->nRef==0 && pCache->pDirty==0 );
191 if( pCache->pCache ){
192 sqlite3GlobalConfig.pcache.xDestroy(pCache->pCache);
193 pCache->pCache = 0;
194 }
195 pCache->szPage = szPage;
196 }
197
198 /*
199 ** Try to obtain a page from the cache.
200 */
201 int sqlite3PcacheFetch(
202 PCache *pCache, /* Obtain the page from this cache */
203 Pgno pgno, /* Page number to obtain */
204 int createFlag, /* If true, create page if it does not exist already */
205 PgHdr **ppPage /* Write the page here */
206 ){
207 PgHdr *pPage = 0;
208 int eCreate;
209
210 assert( pCache!=0 );
211 assert( createFlag==1 || createFlag==0 );
212 assert( pgno>0 );
213
214 /* If the pluggable cache (sqlite3_pcache*) has not been allocated,
215 ** allocate it now.
216 */
217 if( !pCache->pCache && createFlag ){
218 sqlite3_pcache *p;
219 int nByte;
220 nByte = pCache->szPage + pCache->szExtra + sizeof(PgHdr);
221 p = sqlite3GlobalConfig.pcache.xCreate(nByte, pCache->bPurgeable);
222 if( !p ){
223 return SQLITE_NOMEM;
224 }
225 sqlite3GlobalConfig.pcache.xCachesize(p, pCache->nMax);
226 pCache->pCache = p;
227 }
228
229 eCreate = createFlag * (1 + (!pCache->bPurgeable || !pCache->pDirty));
230 if( pCache->pCache ){
231 pPage = sqlite3GlobalConfig.pcache.xFetch(pCache->pCache, pgno, eCreate);
232 }
233
234 if( !pPage && eCreate==1 ){
235 PgHdr *pPg;
236
237 /* Find a dirty page to write-out and recycle. First try to find a
238 ** page that does not require a journal-sync (one with PGHDR_NEED_SYNC
239 ** cleared), but if that is not possible settle for any other
240 ** unreferenced dirty page.
241 */
242 expensive_assert( pcacheCheckSynced(pCache) );
243 for(pPg=pCache->pSynced;
244 pPg && (pPg->nRef || (pPg->flags&PGHDR_NEED_SYNC));
245 pPg=pPg->pDirtyPrev
246 );
247 if( !pPg ){
248 for(pPg=pCache->pDirtyTail; pPg && pPg->nRef; pPg=pPg->pDirtyPrev);
249 }
250 if( pPg ){
251 int rc;
252 rc = pCache->xStress(pCache->pStress, pPg);
253 if( rc!=SQLITE_OK && rc!=SQLITE_BUSY ){
254 return rc;
255 }
256 }
257
258 pPage = sqlite3GlobalConfig.pcache.xFetch(pCache->pCache, pgno, 2);
259 }
260
261 if( pPage ){
262 if( !pPage->pData ){
263 memset(pPage, 0, sizeof(PgHdr) + pCache->szExtra);
264 pPage->pExtra = (void*)&pPage[1];
265 pPage->pData = (void *)&((char *)pPage)[sizeof(PgHdr) + pCache->szExtra];
266 pPage->pCache = pCache;
267 pPage->pgno = pgno;
268 }
269 assert( pPage->pCache==pCache );
270 assert( pPage->pgno==pgno );
271 assert( pPage->pExtra==(void *)&pPage[1] );
272
273 if( 0==pPage->nRef ){
274 pCache->nRef++;
275 }
276 pPage->nRef++;
277 if( pgno==1 ){
278 pCache->pPage1 = pPage;
279 }
280 }
281 *ppPage = pPage;
282 return (pPage==0 && eCreate) ? SQLITE_NOMEM : SQLITE_OK;
283 }
284
285 /*
286 ** Decrement the reference count on a page. If the page is clean and the
287 ** reference count drops to 0, then it is made elible for recycling.
288 */
289 void sqlite3PcacheRelease(PgHdr *p){
290 assert( p->nRef>0 );
291 p->nRef--;
292 if( p->nRef==0 ){
293 PCache *pCache = p->pCache;
294 pCache->nRef--;
295 if( (p->flags&PGHDR_DIRTY)==0 ){
296 pcacheUnpin(p);
297 }else{
298 /* Move the page to the head of the dirty list. */
299 pcacheRemoveFromDirtyList(p);
300 pcacheAddToDirtyList(p);
301 }
302 }
303 }
304
305 /*
306 ** Increase the reference count of a supplied page by 1.
307 */
308 void sqlite3PcacheRef(PgHdr *p){
309 assert(p->nRef>0);
310 p->nRef++;
311 }
312
313 /*
314 ** Drop a page from the cache. There must be exactly one reference to the
315 ** page. This function deletes that reference, so after it returns the
316 ** page pointed to by p is invalid.
317 */
318 void sqlite3PcacheDrop(PgHdr *p){
319 PCache *pCache;
320 assert( p->nRef==1 );
321 if( p->flags&PGHDR_DIRTY ){
322 pcacheRemoveFromDirtyList(p);
323 }
324 pCache = p->pCache;
325 pCache->nRef--;
326 if( p->pgno==1 ){
327 pCache->pPage1 = 0;
328 }
329 sqlite3GlobalConfig.pcache.xUnpin(pCache->pCache, p, 1);
330 }
331
332 /*
333 ** Make sure the page is marked as dirty. If it isn't dirty already,
334 ** make it so.
335 */
336 void sqlite3PcacheMakeDirty(PgHdr *p){
337 p->flags &= ~PGHDR_DONT_WRITE;
338 assert( p->nRef>0 );
339 if( 0==(p->flags & PGHDR_DIRTY) ){
340 p->flags |= PGHDR_DIRTY;
341 pcacheAddToDirtyList( p);
342 }
343 }
344
345 /*
346 ** Make sure the page is marked as clean. If it isn't clean already,
347 ** make it so.
348 */
349 void sqlite3PcacheMakeClean(PgHdr *p){
350 if( (p->flags & PGHDR_DIRTY) ){
351 pcacheRemoveFromDirtyList(p);
352 p->flags &= ~(PGHDR_DIRTY|PGHDR_NEED_SYNC);
353 if( p->nRef==0 ){
354 pcacheUnpin(p);
355 }
356 }
357 }
358
359 /*
360 ** Make every page in the cache clean.
361 */
362 void sqlite3PcacheCleanAll(PCache *pCache){
363 PgHdr *p;
364 while( (p = pCache->pDirty)!=0 ){
365 sqlite3PcacheMakeClean(p);
366 }
367 }
368
369 /*
370 ** Clear the PGHDR_NEED_SYNC flag from all dirty pages.
371 */
372 void sqlite3PcacheClearSyncFlags(PCache *pCache){
373 PgHdr *p;
374 for(p=pCache->pDirty; p; p=p->pDirtyNext){
375 p->flags &= ~PGHDR_NEED_SYNC;
376 }
377 pCache->pSynced = pCache->pDirtyTail;
378 }
379
380 /*
381 ** Change the page number of page p to newPgno.
382 */
383 void sqlite3PcacheMove(PgHdr *p, Pgno newPgno){
384 PCache *pCache = p->pCache;
385 assert( p->nRef>0 );
386 assert( newPgno>0 );
387 sqlite3GlobalConfig.pcache.xRekey(pCache->pCache, p, p->pgno, newPgno);
388 p->pgno = newPgno;
389 if( (p->flags&PGHDR_DIRTY) && (p->flags&PGHDR_NEED_SYNC) ){
390 pcacheRemoveFromDirtyList(p);
391 pcacheAddToDirtyList(p);
392 }
393 }
394
395 /*
396 ** Drop every cache entry whose page number is greater than "pgno". The
397 ** caller must ensure that there are no outstanding references to any pages
398 ** other than page 1 with a page number greater than pgno.
399 **
400 ** If there is a reference to page 1 and the pgno parameter passed to this
401 ** function is 0, then the data area associated with page 1 is zeroed, but
402 ** the page object is not dropped.
403 */
404 void sqlite3PcacheTruncate(PCache *pCache, Pgno pgno){
405 if( pCache->pCache ){
406 PgHdr *p;
407 PgHdr *pNext;
408 for(p=pCache->pDirty; p; p=pNext){
409 pNext = p->pDirtyNext;
410 if( p->pgno>pgno ){
411 assert( p->flags&PGHDR_DIRTY );
412 sqlite3PcacheMakeClean(p);
413 }
414 }
415 if( pgno==0 && pCache->pPage1 ){
416 memset(pCache->pPage1->pData, 0, pCache->szPage);
417 pgno = 1;
418 }
419 sqlite3GlobalConfig.pcache.xTruncate(pCache->pCache, pgno+1);
420 }
421 }
422
423 /*
424 ** Close a cache.
425 */
426 void sqlite3PcacheClose(PCache *pCache){
427 if( pCache->pCache ){
428 sqlite3GlobalConfig.pcache.xDestroy(pCache->pCache);
429 }
430 }
431
432 /*
433 ** Discard the contents of the cache.
434 */
435 void sqlite3PcacheClear(PCache *pCache){
436 sqlite3PcacheTruncate(pCache, 0);
437 }
438
439 /*
440 ** Merge two lists of pages connected by pDirty and in pgno order.
441 ** Do not both fixing the pDirtyPrev pointers.
442 */
443 static PgHdr *pcacheMergeDirtyList(PgHdr *pA, PgHdr *pB){
444 PgHdr result, *pTail;
445 pTail = &result;
446 while( pA && pB ){
447 if( pA->pgno<pB->pgno ){
448 pTail->pDirty = pA;
449 pTail = pA;
450 pA = pA->pDirty;
451 }else{
452 pTail->pDirty = pB;
453 pTail = pB;
454 pB = pB->pDirty;
455 }
456 }
457 if( pA ){
458 pTail->pDirty = pA;
459 }else if( pB ){
460 pTail->pDirty = pB;
461 }else{
462 pTail->pDirty = 0;
463 }
464 return result.pDirty;
465 }
466
467 /*
468 ** Sort the list of pages in accending order by pgno. Pages are
469 ** connected by pDirty pointers. The pDirtyPrev pointers are
470 ** corrupted by this sort.
471 **
472 ** Since there cannot be more than 2^31 distinct pages in a database,
473 ** there cannot be more than 31 buckets required by the merge sorter.
474 ** One extra bucket is added to catch overflow in case something
475 ** ever changes to make the previous sentence incorrect.
476 */
477 #define N_SORT_BUCKET 32
478 static PgHdr *pcacheSortDirtyList(PgHdr *pIn){
479 PgHdr *a[N_SORT_BUCKET], *p;
480 int i;
481 memset(a, 0, sizeof(a));
482 while( pIn ){
483 p = pIn;
484 pIn = p->pDirty;
485 p->pDirty = 0;
486 for(i=0; ALWAYS(i<N_SORT_BUCKET-1); i++){
487 if( a[i]==0 ){
488 a[i] = p;
489 break;
490 }else{
491 p = pcacheMergeDirtyList(a[i], p);
492 a[i] = 0;
493 }
494 }
495 if( NEVER(i==N_SORT_BUCKET-1) ){
496 /* To get here, there need to be 2^(N_SORT_BUCKET) elements in
497 ** the input list. But that is impossible.
498 */
499 a[i] = pcacheMergeDirtyList(a[i], p);
500 }
501 }
502 p = a[0];
503 for(i=1; i<N_SORT_BUCKET; i++){
504 p = pcacheMergeDirtyList(p, a[i]);
505 }
506 return p;
507 }
508
509 /*
510 ** Return a list of all dirty pages in the cache, sorted by page number.
511 */
512 PgHdr *sqlite3PcacheDirtyList(PCache *pCache){
513 PgHdr *p;
514 for(p=pCache->pDirty; p; p=p->pDirtyNext){
515 p->pDirty = p->pDirtyNext;
516 }
517 return pcacheSortDirtyList(pCache->pDirty);
518 }
519
520 /*
521 ** Return the total number of referenced pages held by the cache.
522 */
523 int sqlite3PcacheRefCount(PCache *pCache){
524 return pCache->nRef;
525 }
526
527 /*
528 ** Return the number of references to the page supplied as an argument.
529 */
530 int sqlite3PcachePageRefcount(PgHdr *p){
531 return p->nRef;
532 }
533
534 /*
535 ** Return the total number of pages in the cache.
536 */
537 int sqlite3PcachePagecount(PCache *pCache){
538 int nPage = 0;
539 if( pCache->pCache ){
540 nPage = sqlite3GlobalConfig.pcache.xPagecount(pCache->pCache);
541 }
542 return nPage;
543 }
544
545 /*
546 ** Get the suggested cache-size value.
547 */
548 int sqlite3PcacheGetCachesize(PCache *pCache){
549 return pCache->nMax;
550 }
551
552 /*
553 ** Set the suggested cache-size value.
554 */
555 void sqlite3PcacheSetCachesize(PCache *pCache, int mxPage){
556 pCache->nMax = mxPage;
557 if( pCache->pCache ){
558 sqlite3GlobalConfig.pcache.xCachesize(pCache->pCache, mxPage);
559 }
560 }
561
562 #if defined(SQLITE_CHECK_PAGES) || defined(SQLITE_DEBUG)
563 /*
564 ** For all dirty pages currently in the cache, invoke the specified
565 ** callback. This is only used if the SQLITE_CHECK_PAGES macro is
566 ** defined.
567 */
568 void sqlite3PcacheIterateDirty(PCache *pCache, void (*xIter)(PgHdr *)){
569 PgHdr *pDirty;
570 for(pDirty=pCache->pDirty; pDirty; pDirty=pDirty->pDirtyNext){
571 xIter(pDirty);
572 }
573 }
574 #endif
OLDNEW
« no previous file with comments | « third_party/sqlite/src/pcache.h ('k') | third_party/sqlite/src/pcache1.c » ('j') | no next file with comments »

Powered by Google App Engine
This is Rietveld 408576698