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.  Every
  18 ** entry in the cache holds a single page of the database file.  The
  19 ** btree layer only operates on the cached copy of the database pages.
  20 **
  21 ** A page cache entry is "clean" if it exactly matches what is currently
  22 ** on disk.  A page is "dirty" if it has been modified and needs to be
  23 ** persisted to disk.
  24 **
  25 ** pDirty, pDirtyTail, pSynced:
  26 **   All dirty pages are linked into the doubly linked list using
  27 **   PgHdr.pDirtyNext and pDirtyPrev. The list is maintained in LRU order
  28 **   such that p was added to the list more recently than p->pDirtyNext.
  29 **   PCache.pDirty points to the first (newest) element in the list and
  30 **   pDirtyTail to the last (oldest).
  31 **
  32 **   The PCache.pSynced variable is used to optimize searching for a dirty
  33 **   page to eject from the cache mid-transaction. It is better to eject
  34 **   a page that does not require a journal sync than one that does.
  35 **   Therefore, pSynced is maintained so that it *almost* always points
  36 **   to either the oldest page in the pDirty/pDirtyTail list that has a
  37 **   clear PGHDR_NEED_SYNC flag or to a page that is older than this one
  38 **   (so that the right page to eject can be found by following pDirtyPrev
  39 **   pointers).
  40 */
  41 struct PCache {
  42   PgHdr *pDirty, *pDirtyTail;         /* List of dirty pages in LRU order */
  43   PgHdr *pSynced;                     /* Last synced page in dirty page list */
  44   i64 nRefSum;                        /* Sum of ref counts over all pages */
  45   int szCache;                        /* Configured cache size */
  46   int szSpill;                        /* Size before spilling occurs */
  47   int szPage;                         /* Size of every page in this cache */
  48   int szExtra;                        /* Size of extra space for each page */
  49   u8 bPurgeable;                      /* True if pages are on backing store */
  50   u8 eCreate;                         /* eCreate value for for xFetch() */
  51   int (*xStress)(void*,PgHdr*);       /* Call to try make a page clean */
  52   void *pStress;                      /* Argument to xStress */
  53   sqlite3_pcache *pCache;             /* Pluggable cache module */
  54 };
  55
  56 /********************************** Test and Debug Logic **********************/
  57 /*
  58 ** Debug tracing macros.  Enable by by changing the "0" to "1" and
  59 ** recompiling.
  60 **
  61 ** When sqlite3PcacheTrace is 1, single line trace messages are issued.
  62 ** When sqlite3PcacheTrace is 2, a dump of the pcache showing all cache entries
  63 ** is displayed for many operations, resulting in a lot of output.
  64 */
  65 #if defined(SQLITE_DEBUG) && 0
  66   int sqlite3PcacheTrace = 2;       /* 0: off  1: simple  2: cache dumps */
  67   int sqlite3PcacheMxDump = 9999;   /* Max cache entries for pcacheDump() */
  68 # define pcacheTrace(X) if(sqlite3PcacheTrace){sqlite3DebugPrintf X;}
  69   static void pcachePageTrace(int i, sqlite3_pcache_page *pLower){
  70     PgHdr *pPg;
  71     unsigned char *a;
  72     int j;
  73     if( pLower==0 ){
  74       printf("%3d: NULL\n", i);
  75     }else{
  76       pPg = (PgHdr*)pLower->pExtra;
  77       printf("%3d: nRef %2lld flgs %02x data ", i, pPg->nRef, pPg->flags);
  78       a = (unsigned char *)pLower->pBuf;
  79       for(j=0; j<12; j++) printf("%02x", a[j]);
  80       printf(" ptr %p\n", pPg);
  81     }
  82   }
  83   static void pcacheDump(PCache *pCache){
  84     int N;
  85     int i;
  86     sqlite3_pcache_page *pLower;
  87
  88     if( sqlite3PcacheTrace<2 ) return;
  89     if( pCache->pCache==0 ) return;
  90     N = sqlite3PcachePagecount(pCache);
  91     if( N>sqlite3PcacheMxDump ) N = sqlite3PcacheMxDump;
  92     for(i=1; i<=N; i++){
  93        pLower = sqlite3GlobalConfig.pcache2.xFetch(pCache->pCache, i, 0);
  94        pcachePageTrace(i, pLower);
  95        if( pLower && ((PgHdr*)pLower)->pPage==0 ){
  96          sqlite3GlobalConfig.pcache2.xUnpin(pCache->pCache, pLower, 0);
  97        }
  98     }
  99   }
 100 #else
 101 # define pcacheTrace(X)
 102 # define pcachePageTrace(PGNO, X)
 103 # define pcacheDump(X)
 104 #endif
 105
 106 /*
 107 ** Return 1 if pPg is on the dirty list for pCache.  Return 0 if not.
 108 ** This routine runs inside of assert() statements only.
 109 */
 110 #if defined(SQLITE_ENABLE_EXPENSIVE_ASSERT)
 111 static int pageOnDirtyList(PCache *pCache, PgHdr *pPg){
 112   PgHdr *p;
 113   for(p=pCache->pDirty; p; p=p->pDirtyNext){
 114     if( p==pPg ) return 1;
 115   }
 116   return 0;
 117 }
 118 static int pageNotOnDirtyList(PCache *pCache, PgHdr *pPg){
 119   PgHdr *p;
 120   for(p=pCache->pDirty; p; p=p->pDirtyNext){
 121     if( p==pPg ) return 0;
 122   }
 123   return 1;
 124 }
 125 #else
 126 # define pageOnDirtyList(A,B)    1
 127 # define pageNotOnDirtyList(A,B) 1
 128 #endif
 129
 130 /*
 131 ** Check invariants on a PgHdr entry.  Return true if everything is OK.
 132 ** Return false if any invariant is violated.
 133 **
 134 ** This routine is for use inside of assert() statements only.  For
 135 ** example:
 136 **
 137 **          assert( sqlite3PcachePageSanity(pPg) );
 138 */
 139 #ifdef SQLITE_DEBUG
 140 int sqlite3PcachePageSanity(PgHdr *pPg){
 141   PCache *pCache;
 142   assert( pPg!=0 );
 143   assert( pPg->pgno>0 || pPg->pPager==0 );    /* Page number is 1 or more */
 144   pCache = pPg->pCache;
 145   assert( pCache!=0 );      /* Every page has an associated PCache */
 146   if( pPg->flags & PGHDR_CLEAN ){
 147     assert( (pPg->flags & PGHDR_DIRTY)==0 );/* Cannot be both CLEAN and DIRTY */
 148     assert( pageNotOnDirtyList(pCache, pPg) );/* CLEAN pages not on dirtylist */
 149   }else{
 150     assert( (pPg->flags & PGHDR_DIRTY)!=0 );/* If not CLEAN must be DIRTY */
 151     assert( pPg->pDirtyNext==0 || pPg->pDirtyNext->pDirtyPrev==pPg );
 152     assert( pPg->pDirtyPrev==0 || pPg->pDirtyPrev->pDirtyNext==pPg );
 153     assert( pPg->pDirtyPrev!=0 || pCache->pDirty==pPg );
 154     assert( pageOnDirtyList(pCache, pPg) );
 155   }
 156   /* WRITEABLE pages must also be DIRTY */
 157   if( pPg->flags & PGHDR_WRITEABLE ){
 158     assert( pPg->flags & PGHDR_DIRTY );     /* WRITEABLE implies DIRTY */
 159   }
 160   /* NEED_SYNC can be set independently of WRITEABLE.  This can happen,
 161   ** for example, when using the sqlite3PagerDontWrite() optimization:
 162   **    (1)  Page X is journalled, and gets WRITEABLE and NEED_SEEK.
 163   **    (2)  Page X moved to freelist, WRITEABLE is cleared
 164   **    (3)  Page X reused, WRITEABLE is set again
 165   ** If NEED_SYNC had been cleared in step 2, then it would not be reset
 166   ** in step 3, and page might be written into the database without first
 167   ** syncing the rollback journal, which might cause corruption on a power
 168   ** loss.
 169   **
 170   ** Another example is when the database page size is smaller than the
 171   ** disk sector size.  When any page of a sector is journalled, all pages
 172   ** in that sector are marked NEED_SYNC even if they are still CLEAN, just
 173   ** in case they are later modified, since all pages in the same sector
 174   ** must be journalled and synced before any of those pages can be safely
 175   ** written.
 176   */
 177   return 1;
 178 }
 179 #endif /* SQLITE_DEBUG */
 180
 181
 182 /********************************** Linked List Management ********************/
 183
 184 /* Allowed values for second argument to pcacheManageDirtyList() */
 185 #define PCACHE_DIRTYLIST_REMOVE   1    /* Remove pPage from dirty list */
 186 #define PCACHE_DIRTYLIST_ADD      2    /* Add pPage to the dirty list */
 187 #define PCACHE_DIRTYLIST_FRONT    3    /* Move pPage to the front of the list */
 188
 189 /*
 190 ** Manage pPage's participation on the dirty list.  Bits of the addRemove
 191 ** argument determines what operation to do.  The 0x01 bit means first
 192 ** remove pPage from the dirty list.  The 0x02 means add pPage back to
 193 ** the dirty list.  Doing both moves pPage to the front of the dirty list.
 194 */
 195 static void pcacheManageDirtyList(PgHdr *pPage, u8 addRemove){
 196   PCache *p = pPage->pCache;
 197
 198   pcacheTrace(("%p.DIRTYLIST.%s %d\n", p,
 199                 addRemove==1 ? "REMOVE" : addRemove==2 ? "ADD" : "FRONT",
 200                 pPage->pgno));
 201   if( addRemove & PCACHE_DIRTYLIST_REMOVE ){
 202     assert( pPage->pDirtyNext || pPage==p->pDirtyTail );
 203     assert( pPage->pDirtyPrev || pPage==p->pDirty );
 204
 205     /* Update the PCache1.pSynced variable if necessary. */
 206     if( p->pSynced==pPage ){
 207       p->pSynced = pPage->pDirtyPrev;
 208     }
 209
 210     if( pPage->pDirtyNext ){
 211       pPage->pDirtyNext->pDirtyPrev = pPage->pDirtyPrev;
 212     }else{
 213       assert( pPage==p->pDirtyTail );
 214       p->pDirtyTail = pPage->pDirtyPrev;
 215     }
 216     if( pPage->pDirtyPrev ){
 217       pPage->pDirtyPrev->pDirtyNext = pPage->pDirtyNext;
 218     }else{
 219       /* If there are now no dirty pages in the cache, set eCreate to 2.
 220       ** This is an optimization that allows sqlite3PcacheFetch() to skip
 221       ** searching for a dirty page to eject from the cache when it might
 222       ** otherwise have to.  */
 223       assert( pPage==p->pDirty );
 224       p->pDirty = pPage->pDirtyNext;
 225       assert( p->bPurgeable || p->eCreate==2 );
 226       if( p->pDirty==0 ){         /*OPTIMIZATION-IF-TRUE*/
 227         assert( p->bPurgeable==0 || p->eCreate==1 );
 228         p->eCreate = 2;
 229       }
 230     }
 231   }
 232   if( addRemove & PCACHE_DIRTYLIST_ADD ){
 233     pPage->pDirtyPrev = 0;
 234     pPage->pDirtyNext = p->pDirty;
 235     if( pPage->pDirtyNext ){
 236       assert( pPage->pDirtyNext->pDirtyPrev==0 );
 237       pPage->pDirtyNext->pDirtyPrev = pPage;
 238     }else{
 239       p->pDirtyTail = pPage;
 240       if( p->bPurgeable ){
 241         assert( p->eCreate==2 );
 242         p->eCreate = 1;
 243       }
 244     }
 245     p->pDirty = pPage;
 246
 247     /* If pSynced is NULL and this page has a clear NEED_SYNC flag, set
 248     ** pSynced to point to it. Checking the NEED_SYNC flag is an
 249     ** optimization, as if pSynced points to a page with the NEED_SYNC
 250     ** flag set sqlite3PcacheFetchStress() searches through all newer
 251     ** entries of the dirty-list for a page with NEED_SYNC clear anyway.  */
 252     if( !p->pSynced
 253      && 0==(pPage->flags&PGHDR_NEED_SYNC)   /*OPTIMIZATION-IF-FALSE*/
 254     ){
 255       p->pSynced = pPage;
 256     }
 257   }
 258   pcacheDump(p);
 259 }
 260
 261 /*
 262 ** Wrapper around the pluggable caches xUnpin method. If the cache is
 263 ** being used for an in-memory database, this function is a no-op.
 264 */
 265 static void pcacheUnpin(PgHdr *p){
 266   if( p->pCache->bPurgeable ){
 267     pcacheTrace(("%p.UNPIN %d\n", p->pCache, p->pgno));
 268     sqlite3GlobalConfig.pcache2.xUnpin(p->pCache->pCache, p->pPage, 0);
 269     pcacheDump(p->pCache);
 270   }
 271 }
 272
 273 /*
 274 ** Compute the number of pages of cache requested.   p->szCache is the
 275 ** cache size requested by the "PRAGMA cache_size" statement.
 276 */
 277 static int numberOfCachePages(PCache *p){
 278   if( p->szCache>=0 ){
 279     /* IMPLEMENTATION-OF: R-42059-47211 If the argument N is positive then the
 280     ** suggested cache size is set to N. */
 281     return p->szCache;
 282   }else{
 283     i64 n;
 284     /* IMPLEMENTATION-OF: R-59858-46238 If the argument N is negative, then the
 285     ** number of cache pages is adjusted to be a number of pages that would
 286     ** use approximately abs(N*1024) bytes of memory based on the current
 287     ** page size. */
 288     n = ((-1024*(i64)p->szCache)/(p->szPage+p->szExtra));
 289     if( n>1000000000 ) n = 1000000000;
 290     return (int)n;
 291   }
 292 }
 293
 294 /*************************************************** General Interfaces ******
 295 **
 296 ** Initialize and shutdown the page cache subsystem. Neither of these
 297 ** functions are threadsafe.
 298 */
 299 int sqlite3PcacheInitialize(void){
 300   if( sqlite3GlobalConfig.pcache2.xInit==0 ){
 301     /* IMPLEMENTATION-OF: R-26801-64137 If the xInit() method is NULL, then the
 302     ** built-in default page cache is used instead of the application defined
 303     ** page cache. */
 304     sqlite3PCacheSetDefault();
 305     assert( sqlite3GlobalConfig.pcache2.xInit!=0 );
 306   }
 307   return sqlite3GlobalConfig.pcache2.xInit(sqlite3GlobalConfig.pcache2.pArg);
 308 }
 309 void sqlite3PcacheShutdown(void){
 310   if( sqlite3GlobalConfig.pcache2.xShutdown ){
 311     /* IMPLEMENTATION-OF: R-26000-56589 The xShutdown() method may be NULL. */
 312     sqlite3GlobalConfig.pcache2.xShutdown(sqlite3GlobalConfig.pcache2.pArg);
 313   }
 314 }
 315
 316 /*
 317 ** Return the size in bytes of a PCache object.
 318 */
 319 int sqlite3PcacheSize(void){ return sizeof(PCache); }
 320
 321 /*
 322 ** Create a new PCache object. Storage space to hold the object
 323 ** has already been allocated and is passed in as the p pointer.
 324 ** The caller discovers how much space needs to be allocated by
 325 ** calling sqlite3PcacheSize().
 326 **
 327 ** szExtra is some extra space allocated for each page.  The first
 328 ** 8 bytes of the extra space will be zeroed as the page is allocated,
 329 ** but remaining content will be uninitialized.  Though it is opaque
 330 ** to this module, the extra space really ends up being the MemPage
 331 ** structure in the pager.
 332 */
 333 int sqlite3PcacheOpen(
 334   int szPage,                  /* Size of every page */
 335   int szExtra,                 /* Extra space associated with each page */
 336   int bPurgeable,              /* True if pages are on backing store */
 337   int (*xStress)(void*,PgHdr*),/* Call to try to make pages clean */
 338   void *pStress,               /* Argument to xStress */
 339   PCache *p                    /* Preallocated space for the PCache */
 340 ){
 341   memset(p, 0, sizeof(PCache));
 342   p->szPage = 1;
 343   p->szExtra = szExtra;
 344   assert( szExtra>=8 );  /* First 8 bytes will be zeroed */
 345   p->bPurgeable = bPurgeable;
 346   p->eCreate = 2;
 347   p->xStress = xStress;
 348   p->pStress = pStress;
 349   p->szCache = 100;
 350   p->szSpill = 1;
 351   pcacheTrace(("%p.OPEN szPage %d bPurgeable %d\n",p,szPage,bPurgeable));
 352   return sqlite3PcacheSetPageSize(p, szPage);
 353 }
 354
 355 /*
 356 ** Change the page size for PCache object. The caller must ensure that there
 357 ** are no outstanding page references when this function is called.
 358 */
 359 int sqlite3PcacheSetPageSize(PCache *pCache, int szPage){
 360   assert( pCache->nRefSum==0 && pCache->pDirty==0 );
 361   if( pCache->szPage ){
 362     sqlite3_pcache *pNew;
 363     pNew = sqlite3GlobalConfig.pcache2.xCreate(
 364                 szPage, pCache->szExtra + ROUND8(sizeof(PgHdr)),
 365                 pCache->bPurgeable
 366     );
 367     if( pNew==0 ) return SQLITE_NOMEM_BKPT;
 368     sqlite3GlobalConfig.pcache2.xCachesize(pNew, numberOfCachePages(pCache));
 369     if( pCache->pCache ){
 370       sqlite3GlobalConfig.pcache2.xDestroy(pCache->pCache);
 371     }
 372     pCache->pCache = pNew;
 373     pCache->szPage = szPage;
 374     pcacheTrace(("%p.PAGESIZE %d\n",pCache,szPage));
 375   }
 376   return SQLITE_OK;
 377 }
 378
 379 /*
 380 ** Try to obtain a page from the cache.
 381 **
 382 ** This routine returns a pointer to an sqlite3_pcache_page object if
 383 ** such an object is already in cache, or if a new one is created.
 384 ** This routine returns a NULL pointer if the object was not in cache
 385 ** and could not be created.
 386 **
 387 ** The createFlags should be 0 to check for existing pages and should
 388 ** be 3 (not 1, but 3) to try to create a new page.
 389 **
 390 ** If the createFlag is 0, then NULL is always returned if the page
 391 ** is not already in the cache.  If createFlag is 1, then a new page
 392 ** is created only if that can be done without spilling dirty pages
 393 ** and without exceeding the cache size limit.
 394 **
 395 ** The caller needs to invoke sqlite3PcacheFetchFinish() to properly
 396 ** initialize the sqlite3_pcache_page object and convert it into a
 397 ** PgHdr object.  The sqlite3PcacheFetch() and sqlite3PcacheFetchFinish()
 398 ** routines are split this way for performance reasons. When separated
 399 ** they can both (usually) operate without having to push values to
 400 ** the stack on entry and pop them back off on exit, which saves a
 401 ** lot of pushing and popping.
 402 */
 403 sqlite3_pcache_page *sqlite3PcacheFetch(
 404   PCache *pCache,       /* Obtain the page from this cache */
 405   Pgno pgno,            /* Page number to obtain */
 406   int createFlag        /* If true, create page if it does not exist already */
 407 ){
 408   int eCreate;
 409   sqlite3_pcache_page *pRes;
 410
 411   assert( pCache!=0 );
 412   assert( pCache->pCache!=0 );
 413   assert( createFlag==3 || createFlag==0 );
 414   assert( pCache->eCreate==((pCache->bPurgeable && pCache->pDirty) ? 1 : 2) );
 415
 416   /* eCreate defines what to do if the page does not exist.
 417   **    0     Do not allocate a new page.  (createFlag==0)
 418   **    1     Allocate a new page if doing so is inexpensive.
 419   **          (createFlag==1 AND bPurgeable AND pDirty)
 420   **    2     Allocate a new page even it doing so is difficult.
 421   **          (createFlag==1 AND !(bPurgeable AND pDirty)
 422   */
 423   eCreate = createFlag & pCache->eCreate;
 424   assert( eCreate==0 || eCreate==1 || eCreate==2 );
 425   assert( createFlag==0 || pCache->eCreate==eCreate );
 426   assert( createFlag==0 || eCreate==1+(!pCache->bPurgeable||!pCache->pDirty) );
 427   pRes = sqlite3GlobalConfig.pcache2.xFetch(pCache->pCache, pgno, eCreate);
 428   pcacheTrace(("%p.FETCH %d%s (result: %p) ",pCache,pgno,
 429                createFlag?" create":"",pRes));
 430   pcachePageTrace(pgno, pRes);
 431   return pRes;
 432 }
 433
 434 /*
 435 ** If the sqlite3PcacheFetch() routine is unable to allocate a new
 436 ** page because no clean pages are available for reuse and the cache
 437 ** size limit has been reached, then this routine can be invoked to
 438 ** try harder to allocate a page.  This routine might invoke the stress
 439 ** callback to spill dirty pages to the journal.  It will then try to
 440 ** allocate the new page and will only fail to allocate a new page on
 441 ** an OOM error.
 442 **
 443 ** This routine should be invoked only after sqlite3PcacheFetch() fails.
 444 */
 445 int sqlite3PcacheFetchStress(
 446   PCache *pCache,                 /* Obtain the page from this cache */
 447   Pgno pgno,                      /* Page number to obtain */
 448   sqlite3_pcache_page **ppPage    /* Write result here */
 449 ){
 450   PgHdr *pPg;
 451   if( pCache->eCreate==2 ) return 0;
 452
 453   if( sqlite3PcachePagecount(pCache)>pCache->szSpill ){
 454     /* Find a dirty page to write-out and recycle. First try to find a
 455     ** page that does not require a journal-sync (one with PGHDR_NEED_SYNC
 456     ** cleared), but if that is not possible settle for any other
 457     ** unreferenced dirty page.
 458     **
 459     ** If the LRU page in the dirty list that has a clear PGHDR_NEED_SYNC
 460     ** flag is currently referenced, then the following may leave pSynced
 461     ** set incorrectly (pointing to other than the LRU page with NEED_SYNC
 462     ** cleared). This is Ok, as pSynced is just an optimization.  */
 463     for(pPg=pCache->pSynced;
 464         pPg && (pPg->nRef || (pPg->flags&PGHDR_NEED_SYNC));
 465         pPg=pPg->pDirtyPrev
 466     );
 467     pCache->pSynced = pPg;
 468     if( !pPg ){
 469       for(pPg=pCache->pDirtyTail; pPg && pPg->nRef; pPg=pPg->pDirtyPrev);
 470     }
 471     if( pPg ){
 472       int rc;
 473 #ifdef SQLITE_LOG_CACHE_SPILL
 474       sqlite3_log(SQLITE_FULL,
 475                   "spill page %d making room for %d - cache used: %d/%d",
 476                   pPg->pgno, pgno,
 477                   sqlite3GlobalConfig.pcache2.xPagecount(pCache->pCache),
 478                 numberOfCachePages(pCache));
 479 #endif
 480       pcacheTrace(("%p.SPILL %d\n",pCache,pPg->pgno));
 481       rc = pCache->xStress(pCache->pStress, pPg);
 482       pcacheDump(pCache);
 483       if( rc!=SQLITE_OK && rc!=SQLITE_BUSY ){
 484         return rc;
 485       }
 486     }
 487   }
 488   *ppPage = sqlite3GlobalConfig.pcache2.xFetch(pCache->pCache, pgno, 2);
 489   return *ppPage==0 ? SQLITE_NOMEM_BKPT : SQLITE_OK;
 490 }
 491
 492 /*
 493 ** This is a helper routine for sqlite3PcacheFetchFinish()
 494 **
 495 ** In the uncommon case where the page being fetched has not been
 496 ** initialized, this routine is invoked to do the initialization.
 497 ** This routine is broken out into a separate function since it
 498 ** requires extra stack manipulation that can be avoided in the common
 499 ** case.
 500 */
 501 static SQLITE_NOINLINE PgHdr *pcacheFetchFinishWithInit(
 502   PCache *pCache,             /* Obtain the page from this cache */
 503   Pgno pgno,                  /* Page number obtained */
 504   sqlite3_pcache_page *pPage  /* Page obtained by prior PcacheFetch() call */
 505 ){
 506   PgHdr *pPgHdr;
 507   assert( pPage!=0 );
 508   pPgHdr = (PgHdr*)pPage->pExtra;
 509   assert( pPgHdr->pPage==0 );
 510   memset(&pPgHdr->pDirty, 0, sizeof(PgHdr) - offsetof(PgHdr,pDirty));
 511   pPgHdr->pPage = pPage;
 512   pPgHdr->pData = pPage->pBuf;
 513   pPgHdr->pExtra = (void *)&pPgHdr[1];
 514   memset(pPgHdr->pExtra, 0, 8);
 515   pPgHdr->pCache = pCache;
 516   pPgHdr->pgno = pgno;
 517   pPgHdr->flags = PGHDR_CLEAN;
 518   return sqlite3PcacheFetchFinish(pCache,pgno,pPage);
 519 }
 520
 521 /*
 522 ** This routine converts the sqlite3_pcache_page object returned by
 523 ** sqlite3PcacheFetch() into an initialized PgHdr object.  This routine
 524 ** must be called after sqlite3PcacheFetch() in order to get a usable
 525 ** result.
 526 */
 527 PgHdr *sqlite3PcacheFetchFinish(
 528   PCache *pCache,             /* Obtain the page from this cache */
 529   Pgno pgno,                  /* Page number obtained */
 530   sqlite3_pcache_page *pPage  /* Page obtained by prior PcacheFetch() call */
 531 ){
 532   PgHdr *pPgHdr;
 533
 534   assert( pPage!=0 );
 535   pPgHdr = (PgHdr *)pPage->pExtra;
 536
 537   if( !pPgHdr->pPage ){
 538     return pcacheFetchFinishWithInit(pCache, pgno, pPage);
 539   }
 540   pCache->nRefSum++;
 541   pPgHdr->nRef++;
 542   assert( sqlite3PcachePageSanity(pPgHdr) );
 543   return pPgHdr;
 544 }
 545
 546 /*
 547 ** Decrement the reference count on a page. If the page is clean and the
 548 ** reference count drops to 0, then it is made eligible for recycling.
 549 */
 550 void SQLITE_NOINLINE sqlite3PcacheRelease(PgHdr *p){
 551   assert( p->nRef>0 );
 552   p->pCache->nRefSum--;
 553   if( (--p->nRef)==0 ){
 554     if( p->flags&PGHDR_CLEAN ){
 555       pcacheUnpin(p);
 556     }else{
 557       pcacheManageDirtyList(p, PCACHE_DIRTYLIST_FRONT);
 558       assert( sqlite3PcachePageSanity(p) );
 559     }
 560   }
 561 }
 562
 563 /*
 564 ** Increase the reference count of a supplied page by 1.
 565 */
 566 void sqlite3PcacheRef(PgHdr *p){
 567   assert(p->nRef>0);
 568   assert( sqlite3PcachePageSanity(p) );
 569   p->nRef++;
 570   p->pCache->nRefSum++;
 571 }
 572
 573 /*
 574 ** Drop a page from the cache. There must be exactly one reference to the
 575 ** page. This function deletes that reference, so after it returns the
 576 ** page pointed to by p is invalid.
 577 */
 578 void sqlite3PcacheDrop(PgHdr *p){
 579   assert( p->nRef==1 );
 580   assert( sqlite3PcachePageSanity(p) );
 581   if( p->flags&PGHDR_DIRTY ){
 582     pcacheManageDirtyList(p, PCACHE_DIRTYLIST_REMOVE);
 583   }
 584   p->pCache->nRefSum--;
 585   sqlite3GlobalConfig.pcache2.xUnpin(p->pCache->pCache, p->pPage, 1);
 586 }
 587
 588 /*
 589 ** Make sure the page is marked as dirty. If it isn't dirty already,
 590 ** make it so.
 591 */
 592 void sqlite3PcacheMakeDirty(PgHdr *p){
 593   assert( p->nRef>0 );
 594   assert( sqlite3PcachePageSanity(p) );
 595   if( p->flags & (PGHDR_CLEAN|PGHDR_DONT_WRITE) ){    /*OPTIMIZATION-IF-FALSE*/
 596     p->flags &= ~PGHDR_DONT_WRITE;
 597     if( p->flags & PGHDR_CLEAN ){
 598       p->flags ^= (PGHDR_DIRTY|PGHDR_CLEAN);
 599       pcacheTrace(("%p.DIRTY %d\n",p->pCache,p->pgno));
 600       assert( (p->flags & (PGHDR_DIRTY|PGHDR_CLEAN))==PGHDR_DIRTY );
 601       pcacheManageDirtyList(p, PCACHE_DIRTYLIST_ADD);
 602       assert( sqlite3PcachePageSanity(p) );
 603     }
 604     assert( sqlite3PcachePageSanity(p) );
 605   }
 606 }
 607
 608 /*
 609 ** Make sure the page is marked as clean. If it isn't clean already,
 610 ** make it so.
 611 */
 612 void sqlite3PcacheMakeClean(PgHdr *p){
 613   assert( sqlite3PcachePageSanity(p) );
 614   assert( (p->flags & PGHDR_DIRTY)!=0 );
 615   assert( (p->flags & PGHDR_CLEAN)==0 );
 616   pcacheManageDirtyList(p, PCACHE_DIRTYLIST_REMOVE);
 617   p->flags &= ~(PGHDR_DIRTY|PGHDR_NEED_SYNC|PGHDR_WRITEABLE);
 618   p->flags |= PGHDR_CLEAN;
 619   pcacheTrace(("%p.CLEAN %d\n",p->pCache,p->pgno));
 620   assert( sqlite3PcachePageSanity(p) );
 621   if( p->nRef==0 ){
 622     pcacheUnpin(p);
 623   }
 624 }
 625
 626 /*
 627 ** Make every page in the cache clean.
 628 */
 629 void sqlite3PcacheCleanAll(PCache *pCache){
 630   PgHdr *p;
 631   pcacheTrace(("%p.CLEAN-ALL\n",pCache));
 632   while( (p = pCache->pDirty)!=0 ){
 633     sqlite3PcacheMakeClean(p);
 634   }
 635 }
 636
 637 /*
 638 ** Clear the PGHDR_NEED_SYNC and PGHDR_WRITEABLE flag from all dirty pages.
 639 */
 640 void sqlite3PcacheClearWritable(PCache *pCache){
 641   PgHdr *p;
 642   pcacheTrace(("%p.CLEAR-WRITEABLE\n",pCache));
 643   for(p=pCache->pDirty; p; p=p->pDirtyNext){
 644     p->flags &= ~(PGHDR_NEED_SYNC|PGHDR_WRITEABLE);
 645   }
 646   pCache->pSynced = pCache->pDirtyTail;
 647 }
 648
 649 /*
 650 ** Clear the PGHDR_NEED_SYNC flag from all dirty pages.
 651 */
 652 void sqlite3PcacheClearSyncFlags(PCache *pCache){
 653   PgHdr *p;
 654   for(p=pCache->pDirty; p; p=p->pDirtyNext){
 655     p->flags &= ~PGHDR_NEED_SYNC;
 656   }
 657   pCache->pSynced = pCache->pDirtyTail;
 658 }
 659
 660 /*
 661 ** Change the page number of page p to newPgno.
 662 */
 663 void sqlite3PcacheMove(PgHdr *p, Pgno newPgno){
 664   PCache *pCache = p->pCache;
 665   sqlite3_pcache_page *pOther;
 666   assert( p->nRef>0 );
 667   assert( newPgno>0 );
 668   assert( sqlite3PcachePageSanity(p) );
 669   pcacheTrace(("%p.MOVE %d -> %d\n",pCache,p->pgno,newPgno));
 670   pOther = sqlite3GlobalConfig.pcache2.xFetch(pCache->pCache, newPgno, 0);
 671   if( pOther ){
 672     PgHdr *pXPage = (PgHdr*)pOther->pExtra;
 673     assert( pXPage->nRef==0 );
 674     pXPage->nRef++;
 675     pCache->nRefSum++;
 676     sqlite3PcacheDrop(pXPage);
 677   }
 678   sqlite3GlobalConfig.pcache2.xRekey(pCache->pCache, p->pPage, p->pgno,newPgno);
 679   p->pgno = newPgno;
 680   if( (p->flags&PGHDR_DIRTY) && (p->flags&PGHDR_NEED_SYNC) ){
 681     pcacheManageDirtyList(p, PCACHE_DIRTYLIST_FRONT);
 682     assert( sqlite3PcachePageSanity(p) );
 683   }
 684 }
 685
 686 /*
 687 ** Drop every cache entry whose page number is greater than "pgno". The
 688 ** caller must ensure that there are no outstanding references to any pages
 689 ** other than page 1 with a page number greater than pgno.
 690 **
 691 ** If there is a reference to page 1 and the pgno parameter passed to this
 692 ** function is 0, then the data area associated with page 1 is zeroed, but
 693 ** the page object is not dropped.
 694 */
 695 void sqlite3PcacheTruncate(PCache *pCache, Pgno pgno){
 696   if( pCache->pCache ){
 697     PgHdr *p;
 698     PgHdr *pNext;
 699     pcacheTrace(("%p.TRUNCATE %d\n",pCache,pgno));
 700     for(p=pCache->pDirty; p; p=pNext){
 701       pNext = p->pDirtyNext;
 702       /* This routine never gets call with a positive pgno except right
 703       ** after sqlite3PcacheCleanAll().  So if there are dirty pages,
 704       ** it must be that pgno==0.
 705       */
 706       assert( p->pgno>0 );
 707       if( p->pgno>pgno ){
 708         assert( p->flags&PGHDR_DIRTY );
 709         sqlite3PcacheMakeClean(p);
 710       }
 711     }
 712     if( pgno==0 && pCache->nRefSum ){
 713       sqlite3_pcache_page *pPage1;
 714       pPage1 = sqlite3GlobalConfig.pcache2.xFetch(pCache->pCache,1,0);
 715       if( ALWAYS(pPage1) ){  /* Page 1 is always available in cache, because
 716                              ** pCache->nRefSum>0 */
 717         memset(pPage1->pBuf, 0, pCache->szPage);
 718         pgno = 1;
 719       }
 720     }
 721     sqlite3GlobalConfig.pcache2.xTruncate(pCache->pCache, pgno+1);
 722   }
 723 }
 724
 725 /*
 726 ** Close a cache.
 727 */
 728 void sqlite3PcacheClose(PCache *pCache){
 729   assert( pCache->pCache!=0 );
 730   pcacheTrace(("%p.CLOSE\n",pCache));
 731   sqlite3GlobalConfig.pcache2.xDestroy(pCache->pCache);
 732 }
 733
 734 /*
 735 ** Discard the contents of the cache.
 736 */
 737 void sqlite3PcacheClear(PCache *pCache){
 738   sqlite3PcacheTruncate(pCache, 0);
 739 }
 740
 741 /*
 742 ** Merge two lists of pages connected by pDirty and in pgno order.
 743 ** Do not bother fixing the pDirtyPrev pointers.
 744 */
 745 static PgHdr *pcacheMergeDirtyList(PgHdr *pA, PgHdr *pB){
 746   PgHdr result, *pTail;
 747   pTail = &result;
 748   assert( pA!=0 && pB!=0 );
 749   for(;;){
 750     if( pA->pgno<pB->pgno ){
 751       pTail->pDirty = pA;
 752       pTail = pA;
 753       pA = pA->pDirty;
 754       if( pA==0 ){
 755         pTail->pDirty = pB;
 756         break;
 757       }
 758     }else{
 759       pTail->pDirty = pB;
 760       pTail = pB;
 761       pB = pB->pDirty;
 762       if( pB==0 ){
 763         pTail->pDirty = pA;
 764         break;
 765       }
 766     }
 767   }
 768   return result.pDirty;
 769 }
 770
 771 /*
 772 ** Sort the list of pages in ascending order by pgno.  Pages are
 773 ** connected by pDirty pointers.  The pDirtyPrev pointers are
 774 ** corrupted by this sort.
 775 **
 776 ** Since there cannot be more than 2^31 distinct pages in a database,
 777 ** there cannot be more than 31 buckets required by the merge sorter.
 778 ** One extra bucket is added to catch overflow in case something
 779 ** ever changes to make the previous sentence incorrect.
 780 */
 781 #define N_SORT_BUCKET  32
 782 static PgHdr *pcacheSortDirtyList(PgHdr *pIn){
 783   PgHdr *a[N_SORT_BUCKET], *p;
 784   int i;
 785   memset(a, 0, sizeof(a));
 786   while( pIn ){
 787     p = pIn;
 788     pIn = p->pDirty;
 789     p->pDirty = 0;
 790     for(i=0; ALWAYS(i<N_SORT_BUCKET-1); i++){
 791       if( a[i]==0 ){
 792         a[i] = p;
 793         break;
 794       }else{
 795         p = pcacheMergeDirtyList(a[i], p);
 796         a[i] = 0;
 797       }
 798     }
 799     if( NEVER(i==N_SORT_BUCKET-1) ){
 800       /* To get here, there need to be 2^(N_SORT_BUCKET) elements in
 801       ** the input list.  But that is impossible.
 802       */
 803       a[i] = pcacheMergeDirtyList(a[i], p);
 804     }
 805   }
 806   p = a[0];
 807   for(i=1; i<N_SORT_BUCKET; i++){
 808     if( a[i]==0 ) continue;
 809     p = p ? pcacheMergeDirtyList(p, a[i]) : a[i];
 810   }
 811   return p;
 812 }
 813
 814 /*
 815 ** Return a list of all dirty pages in the cache, sorted by page number.
 816 */
 817 PgHdr *sqlite3PcacheDirtyList(PCache *pCache){
 818   PgHdr *p;
 819   for(p=pCache->pDirty; p; p=p->pDirtyNext){
 820     p->pDirty = p->pDirtyNext;
 821   }
 822   return pcacheSortDirtyList(pCache->pDirty);
 823 }
 824
 825 /*
 826 ** Return the total number of references to all pages held by the cache.
 827 **
 828 ** This is not the total number of pages referenced, but the sum of the
 829 ** reference count for all pages.
 830 */
 831 i64 sqlite3PcacheRefCount(PCache *pCache){
 832   return pCache->nRefSum;
 833 }
 834
 835 /*
 836 ** Return the number of references to the page supplied as an argument.
 837 */
 838 i64 sqlite3PcachePageRefcount(PgHdr *p){
 839   return p->nRef;
 840 }
 841
 842 /*
 843 ** Return the total number of pages in the cache.
 844 */
 845 int sqlite3PcachePagecount(PCache *pCache){
 846   assert( pCache->pCache!=0 );
 847   return sqlite3GlobalConfig.pcache2.xPagecount(pCache->pCache);
 848 }
 849
 850 #ifdef SQLITE_TEST
 851 /*
 852 ** Get the suggested cache-size value.
 853 */
 854 int sqlite3PcacheGetCachesize(PCache *pCache){
 855   return numberOfCachePages(pCache);
 856 }
 857 #endif
 858
 859 /*
 860 ** Set the suggested cache-size value.
 861 */
 862 void sqlite3PcacheSetCachesize(PCache *pCache, int mxPage){
 863   assert( pCache->pCache!=0 );
 864   pCache->szCache = mxPage;
 865   sqlite3GlobalConfig.pcache2.xCachesize(pCache->pCache,
 866                                          numberOfCachePages(pCache));
 867 }
 868
 869 /*
 870 ** Set the suggested cache-spill value.  Make no changes if if the
 871 ** argument is zero.  Return the effective cache-spill size, which will
 872 ** be the larger of the szSpill and szCache.
 873 */
 874 int sqlite3PcacheSetSpillsize(PCache *p, int mxPage){
 875   int res;
 876   assert( p->pCache!=0 );
 877   if( mxPage ){
 878     if( mxPage<0 ){
 879       mxPage = (int)((-1024*(i64)mxPage)/(p->szPage+p->szExtra));
 880     }
 881     p->szSpill = mxPage;
 882   }
 883   res = numberOfCachePages(p);
 884   if( res<p->szSpill ) res = p->szSpill;
 885   return res;
 886 }
 887
 888 /*
 889 ** Free up as much memory as possible from the page cache.
 890 */
 891 void sqlite3PcacheShrink(PCache *pCache){
 892   assert( pCache->pCache!=0 );
 893   sqlite3GlobalConfig.pcache2.xShrink(pCache->pCache);
 894 }
 895
 896 /*
 897 ** Return the size of the header added by this middleware layer
 898 ** in the page-cache hierarchy.
 899 */
 900 int sqlite3HeaderSizePcache(void){ return ROUND8(sizeof(PgHdr)); }
 901
 902 /*
 903 ** Return the number of dirty pages currently in the cache, as a percentage
 904 ** of the configured cache size.
 905 */
 906 int sqlite3PCachePercentDirty(PCache *pCache){
 907   PgHdr *pDirty;
 908   int nDirty = 0;
 909   int nCache = numberOfCachePages(pCache);
 910   for(pDirty=pCache->pDirty; pDirty; pDirty=pDirty->pDirtyNext) nDirty++;
 911   return nCache ? (int)(((i64)nDirty * 100) / nCache) : 0;
 912 }
 913
 914 #ifdef SQLITE_DIRECT_OVERFLOW_READ
 915 /*
 916 ** Return true if there are one or more dirty pages in the cache. Else false.
 917 */
 918 int sqlite3PCacheIsDirty(PCache *pCache){
 919   return (pCache->pDirty!=0);
 920 }
 921 #endif
 922
 923 #if defined(SQLITE_CHECK_PAGES) || defined(SQLITE_DEBUG)
 924 /*
 925 ** For all dirty pages currently in the cache, invoke the specified
 926 ** callback. This is only used if the SQLITE_CHECK_PAGES macro is
 927 ** defined.
 928 */
 929 void sqlite3PcacheIterateDirty(PCache *pCache, void (*xIter)(PgHdr *)){
 930   PgHdr *pDirty;
 931   for(pDirty=pCache->pDirty; pDirty; pDirty=pDirty->pDirtyNext){
 932     xIter(pDirty);
 933   }
 934 }
 935 #endif