src/pcache.c

   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