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*/ 19struct 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 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 */ 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*/ 55static 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*/ 67static 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*/ 104static 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*/ 128static 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.pcache.xUnpin(pCache->pCache, p, 0); 135 } 136} 137 138/*************************************************** General Interfaces ****** 139** 140** Initialize and shutdown the page cache subsystem. Neither of these 141** functions are threadsafe. 142*/ 143int 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 147 ** page cache. */ 148 sqlite3PCacheSetDefault(); 149 } 150 return sqlite3GlobalConfig.pcache.xInit(sqlite3GlobalConfig.pcache.pArg); 151} 152void 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); 156 } 157} 158 159/* 160** Return the size in bytes of a PCache object. 161*/ 162int 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*/ 170void 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->nMax = 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*/ 191void sqlite3PcacheSetPageSize(PCache *pCache, int szPage){ 192 assert( pCache->nRef==0 && pCache->pDirty==0 ); 193 if( pCache->pCache ){ 194 sqlite3GlobalConfig.pcache.xDestroy(pCache->pCache); 195 pCache->pCache = 0; 196 pCache->pPage1 = 0; 197 } 198 pCache->szPage = szPage; 199} 200 201/* 202** Try to obtain a page from the cache. 203*/ 204int 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 */ 209){ 210 PgHdr *pPage = 0; 211 int eCreate; 212 213 assert( pCache!=0 ); 214 assert( createFlag==1 || createFlag==0 ); 215 assert( pgno>0 ); 216 217 /* If the pluggable cache (sqlite3_pcache*) has not been allocated, 218 ** allocate it now. 219 */ 220 if( !pCache->pCache && createFlag ){ 221 sqlite3_pcache *p; 222 int nByte; 223 nByte = pCache->szPage + pCache->szExtra + sizeof(PgHdr); 224 p = sqlite3GlobalConfig.pcache.xCreate(nByte, pCache->bPurgeable); 225 if( !p ){ 226 return SQLITE_NOMEM; 227 } 228 sqlite3GlobalConfig.pcache.xCachesize(p, pCache->nMax); 229 pCache->pCache = p; 230 } 231 232 eCreate = createFlag * (1 + (!pCache->bPurgeable || !pCache->pDirty)); 233 if( pCache->pCache ){ 234 pPage = sqlite3GlobalConfig.pcache.xFetch(pCache->pCache, pgno, eCreate); 235 } 236 237 if( !pPage && eCreate==1 ){ 238 PgHdr *pPg; 239 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. 244 */ 245 expensive_assert( pcacheCheckSynced(pCache) ); 246 for(pPg=pCache->pSynced; 247 pPg && (pPg->nRef || (pPg->flags&PGHDR_NEED_SYNC)); 248 pPg=pPg->pDirtyPrev 249 ); 250 pCache->pSynced = pPg; 251 if( !pPg ){ 252 for(pPg=pCache->pDirtyTail; pPg && pPg->nRef; pPg=pPg->pDirtyPrev); 253 } 254 if( pPg ){ 255 int rc; 256 rc = pCache->xStress(pCache->pStress, pPg); 257 if( rc!=SQLITE_OK && rc!=SQLITE_BUSY ){ 258 return rc; 259 } 260 } 261 262 pPage = sqlite3GlobalConfig.pcache.xFetch(pCache->pCache, pgno, 2); 263 } 264 265 if( pPage ){ 266 if( !pPage->pData ){ 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; 272 pPage->pgno = pgno; 273 } 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] ); 278 279 if( 0==pPage->nRef ){ 280 pCache->nRef++; 281 } 282 pPage->nRef++; 283 if( pgno==1 ){ 284 pCache->pPage1 = pPage; 285 } 286 } 287 *ppPage = pPage; 288 return (pPage==0 && eCreate) ? SQLITE_NOMEM : SQLITE_OK; 289} 290 291/* 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. 294*/ 295void sqlite3PcacheRelease(PgHdr *p){ 296 assert( p->nRef>0 ); 297 p->nRef--; 298 if( p->nRef==0 ){ 299 PCache *pCache = p->pCache; 300 pCache->nRef--; 301 if( (p->flags&PGHDR_DIRTY)==0 ){ 302 pcacheUnpin(p); 303 }else{ 304 /* Move the page to the head of the dirty list. */ 305 pcacheRemoveFromDirtyList(p); 306 pcacheAddToDirtyList(p); 307 } 308 } 309} 310 311/* 312** Increase the reference count of a supplied page by 1. 313*/ 314void sqlite3PcacheRef(PgHdr *p){ 315 assert(p->nRef>0); 316 p->nRef++; 317} 318 319/* 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. 323*/ 324void sqlite3PcacheDrop(PgHdr *p){ 325 PCache *pCache; 326 assert( p->nRef==1 ); 327 if( p->flags&PGHDR_DIRTY ){ 328 pcacheRemoveFromDirtyList(p); 329 } 330 pCache = p->pCache; 331 pCache->nRef--; 332 if( p->pgno==1 ){ 333 pCache->pPage1 = 0; 334 } 335 sqlite3GlobalConfig.pcache.xUnpin(pCache->pCache, p, 1); 336} 337 338/* 339** Make sure the page is marked as dirty. If it isn't dirty already, 340** make it so. 341*/ 342void sqlite3PcacheMakeDirty(PgHdr *p){ 343 p->flags &= ~PGHDR_DONT_WRITE; 344 assert( p->nRef>0 ); 345 if( 0==(p->flags & PGHDR_DIRTY) ){ 346 p->flags |= PGHDR_DIRTY; 347 pcacheAddToDirtyList( p); 348 } 349} 350 351/* 352** Make sure the page is marked as clean. If it isn't clean already, 353** make it so. 354*/ 355void sqlite3PcacheMakeClean(PgHdr *p){ 356 if( (p->flags & PGHDR_DIRTY) ){ 357 pcacheRemoveFromDirtyList(p); 358 p->flags &= ~(PGHDR_DIRTY|PGHDR_NEED_SYNC); 359 if( p->nRef==0 ){ 360 pcacheUnpin(p); 361 } 362 } 363} 364 365/* 366** Make every page in the cache clean. 367*/ 368void sqlite3PcacheCleanAll(PCache *pCache){ 369 PgHdr *p; 370 while( (p = pCache->pDirty)!=0 ){ 371 sqlite3PcacheMakeClean(p); 372 } 373} 374 375/* 376** Clear the PGHDR_NEED_SYNC flag from all dirty pages. 377*/ 378void sqlite3PcacheClearSyncFlags(PCache *pCache){ 379 PgHdr *p; 380 for(p=pCache->pDirty; p; p=p->pDirtyNext){ 381 p->flags &= ~PGHDR_NEED_SYNC; 382 } 383 pCache->pSynced = pCache->pDirtyTail; 384} 385 386/* 387** Change the page number of page p to newPgno. 388*/ 389void sqlite3PcacheMove(PgHdr *p, Pgno newPgno){ 390 PCache *pCache = p->pCache; 391 assert( p->nRef>0 ); 392 assert( newPgno>0 ); 393 sqlite3GlobalConfig.pcache.xRekey(pCache->pCache, p, p->pgno, newPgno); 394 p->pgno = newPgno; 395 if( (p->flags&PGHDR_DIRTY) && (p->flags&PGHDR_NEED_SYNC) ){ 396 pcacheRemoveFromDirtyList(p); 397 pcacheAddToDirtyList(p); 398 } 399} 400 401/* 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. 405** 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. 409*/ 410void sqlite3PcacheTruncate(PCache *pCache, Pgno pgno){ 411 if( pCache->pCache ){ 412 PgHdr *p; 413 PgHdr *pNext; 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. 419 */ 420 assert( p->pgno>0 ); 421 if( ALWAYS(p->pgno>pgno) ){ 422 assert( p->flags&PGHDR_DIRTY ); 423 sqlite3PcacheMakeClean(p); 424 } 425 } 426 if( pgno==0 && pCache->pPage1 ){ 427 memset(pCache->pPage1->pData, 0, pCache->szPage); 428 pgno = 1; 429 } 430 sqlite3GlobalConfig.pcache.xTruncate(pCache->pCache, pgno+1); 431 } 432} 433 434/* 435** Close a cache. 436*/ 437void sqlite3PcacheClose(PCache *pCache){ 438 if( pCache->pCache ){ 439 sqlite3GlobalConfig.pcache.xDestroy(pCache->pCache); 440 } 441} 442 443/* 444** Discard the contents of the cache. 445*/ 446void sqlite3PcacheClear(PCache *pCache){ 447 sqlite3PcacheTruncate(pCache, 0); 448} 449 450/* 451** Merge two lists of pages connected by pDirty and in pgno order. 452** Do not both fixing the pDirtyPrev pointers. 453*/ 454static PgHdr *pcacheMergeDirtyList(PgHdr *pA, PgHdr *pB){ 455 PgHdr result, *pTail; 456 pTail = &result; 457 while( pA && pB ){ 458 if( pA->pgno<pB->pgno ){ 459 pTail->pDirty = pA; 460 pTail = pA; 461 pA = pA->pDirty; 462 }else{ 463 pTail->pDirty = pB; 464 pTail = pB; 465 pB = pB->pDirty; 466 } 467 } 468 if( pA ){ 469 pTail->pDirty = pA; 470 }else if( pB ){ 471 pTail->pDirty = pB; 472 }else{ 473 pTail->pDirty = 0; 474 } 475 return result.pDirty; 476} 477 478/* 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. 482** 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. 487*/ 488#define N_SORT_BUCKET 32 489static PgHdr *pcacheSortDirtyList(PgHdr *pIn){ 490 PgHdr *a[N_SORT_BUCKET], *p; 491 int i; 492 memset(a, 0, sizeof(a)); 493 while( pIn ){ 494 p = pIn; 495 pIn = p->pDirty; 496 p->pDirty = 0; 497 for(i=0; ALWAYS(i<N_SORT_BUCKET-1); i++){ 498 if( a[i]==0 ){ 499 a[i] = p; 500 break; 501 }else{ 502 p = pcacheMergeDirtyList(a[i], p); 503 a[i] = 0; 504 } 505 } 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. 509 */ 510 a[i] = pcacheMergeDirtyList(a[i], p); 511 } 512 } 513 p = a[0]; 514 for(i=1; i<N_SORT_BUCKET; i++){ 515 p = pcacheMergeDirtyList(p, a[i]); 516 } 517 return p; 518} 519 520/* 521** Return a list of all dirty pages in the cache, sorted by page number. 522*/ 523PgHdr *sqlite3PcacheDirtyList(PCache *pCache){ 524 PgHdr *p; 525 for(p=pCache->pDirty; p; p=p->pDirtyNext){ 526 p->pDirty = p->pDirtyNext; 527 } 528 return pcacheSortDirtyList(pCache->pDirty); 529} 530 531/* 532** Return the total number of referenced pages held by the cache. 533*/ 534int sqlite3PcacheRefCount(PCache *pCache){ 535 return pCache->nRef; 536} 537 538/* 539** Return the number of references to the page supplied as an argument. 540*/ 541int sqlite3PcachePageRefcount(PgHdr *p){ 542 return p->nRef; 543} 544 545/* 546** Return the total number of pages in the cache. 547*/ 548int sqlite3PcachePagecount(PCache *pCache){ 549 int nPage = 0; 550 if( pCache->pCache ){ 551 nPage = sqlite3GlobalConfig.pcache.xPagecount(pCache->pCache); 552 } 553 return nPage; 554} 555 556#ifdef SQLITE_TEST 557/* 558** Get the suggested cache-size value. 559*/ 560int sqlite3PcacheGetCachesize(PCache *pCache){ 561 return pCache->nMax; 562} 563#endif 564 565/* 566** Set the suggested cache-size value. 567*/ 568void sqlite3PcacheSetCachesize(PCache *pCache, int mxPage){ 569 pCache->nMax = mxPage; 570 if( pCache->pCache ){ 571 sqlite3GlobalConfig.pcache.xCachesize(pCache->pCache, mxPage); 572 } 573} 574 575#if defined(SQLITE_CHECK_PAGES) || defined(SQLITE_DEBUG) 576/* 577** For all dirty pages currently in the cache, invoke the specified 578** callback. This is only used if the SQLITE_CHECK_PAGES macro is 579** defined. 580*/ 581void sqlite3PcacheIterateDirty(PCache *pCache, void (*xIter)(PgHdr *)){ 582 PgHdr *pDirty; 583 for(pDirty=pCache->pDirty; pDirty; pDirty=pDirty->pDirtyNext){ 584 xIter(pDirty); 585 } 586} 587#endif 588