000001  /*
000002  ** 2008 August 05
000003  **
000004  ** The author disclaims copyright to this source code.  In place of
000005  ** a legal notice, here is a blessing:
000006  **
000007  **    May you do good and not evil.
000008  **    May you find forgiveness for yourself and forgive others.
000009  **    May you share freely, never taking more than you give.
000010  **
000011  *************************************************************************
000012  ** This file implements that page cache.
000013  */
000014  #include "sqliteInt.h"
000015  
000016  /*
000017  ** A complete page cache is an instance of this structure.  Every
000018  ** entry in the cache holds a single page of the database file.  The
000019  ** btree layer only operates on the cached copy of the database pages.
000020  **
000021  ** A page cache entry is "clean" if it exactly matches what is currently
000022  ** on disk.  A page is "dirty" if it has been modified and needs to be
000023  ** persisted to disk.
000024  **
000025  ** pDirty, pDirtyTail, pSynced:
000026  **   All dirty pages are linked into the doubly linked list using
000027  **   PgHdr.pDirtyNext and pDirtyPrev. The list is maintained in LRU order
000028  **   such that p was added to the list more recently than p->pDirtyNext.
000029  **   PCache.pDirty points to the first (newest) element in the list and
000030  **   pDirtyTail to the last (oldest).
000031  **
000032  **   The PCache.pSynced variable is used to optimize searching for a dirty
000033  **   page to eject from the cache mid-transaction. It is better to eject
000034  **   a page that does not require a journal sync than one that does. 
000035  **   Therefore, pSynced is maintained so that it *almost* always points
000036  **   to either the oldest page in the pDirty/pDirtyTail list that has a
000037  **   clear PGHDR_NEED_SYNC flag or to a page that is older than this one
000038  **   (so that the right page to eject can be found by following pDirtyPrev
000039  **   pointers).
000040  */
000041  struct PCache {
000042    PgHdr *pDirty, *pDirtyTail;         /* List of dirty pages in LRU order */
000043    PgHdr *pSynced;                     /* Last synced page in dirty page list */
000044    int nRefSum;                        /* Sum of ref counts over all pages */
000045    int szCache;                        /* Configured cache size */
000046    int szSpill;                        /* Size before spilling occurs */
000047    int szPage;                         /* Size of every page in this cache */
000048    int szExtra;                        /* Size of extra space for each page */
000049    u8 bPurgeable;                      /* True if pages are on backing store */
000050    u8 eCreate;                         /* eCreate value for for xFetch() */
000051    int (*xStress)(void*,PgHdr*);       /* Call to try make a page clean */
000052    void *pStress;                      /* Argument to xStress */
000053    sqlite3_pcache *pCache;             /* Pluggable cache module */
000054  };
000055  
000056  /********************************** Test and Debug Logic **********************/
000057  /*
000058  ** Debug tracing macros.  Enable by by changing the "0" to "1" and
000059  ** recompiling.
000060  **
000061  ** When sqlite3PcacheTrace is 1, single line trace messages are issued.
000062  ** When sqlite3PcacheTrace is 2, a dump of the pcache showing all cache entries
000063  ** is displayed for many operations, resulting in a lot of output.
000064  */
000065  #if defined(SQLITE_DEBUG) && 0
000066    int sqlite3PcacheTrace = 2;       /* 0: off  1: simple  2: cache dumps */
000067    int sqlite3PcacheMxDump = 9999;   /* Max cache entries for pcacheDump() */
000068  # define pcacheTrace(X) if(sqlite3PcacheTrace){sqlite3DebugPrintf X;}
000069    void pcacheDump(PCache *pCache){
000070      int N;
000071      int i, j;
000072      sqlite3_pcache_page *pLower;
000073      PgHdr *pPg;
000074      unsigned char *a;
000075    
000076      if( sqlite3PcacheTrace<2 ) return;
000077      if( pCache->pCache==0 ) return;
000078      N = sqlite3PcachePagecount(pCache);
000079      if( N>sqlite3PcacheMxDump ) N = sqlite3PcacheMxDump;
000080      for(i=1; i<=N; i++){
000081         pLower = sqlite3GlobalConfig.pcache2.xFetch(pCache->pCache, i, 0);
000082         if( pLower==0 ) continue;
000083         pPg = (PgHdr*)pLower->pExtra;
000084         printf("%3d: nRef %2d flgs %02x data ", i, pPg->nRef, pPg->flags);
000085         a = (unsigned char *)pLower->pBuf;
000086         for(j=0; j<12; j++) printf("%02x", a[j]);
000087         printf("\n");
000088         if( pPg->pPage==0 ){
000089           sqlite3GlobalConfig.pcache2.xUnpin(pCache->pCache, pLower, 0);
000090         }
000091      }
000092    }
000093    #else
000094  # define pcacheTrace(X)
000095  # define pcacheDump(X)
000096  #endif
000097  
000098  /*
000099  ** Check invariants on a PgHdr entry.  Return true if everything is OK.
000100  ** Return false if any invariant is violated.
000101  **
000102  ** This routine is for use inside of assert() statements only.  For
000103  ** example:
000104  **
000105  **          assert( sqlite3PcachePageSanity(pPg) );
000106  */
000107  #ifdef SQLITE_DEBUG
000108  int sqlite3PcachePageSanity(PgHdr *pPg){
000109    PCache *pCache;
000110    assert( pPg!=0 );
000111    assert( pPg->pgno>0 || pPg->pPager==0 );    /* Page number is 1 or more */
000112    pCache = pPg->pCache;
000113    assert( pCache!=0 );      /* Every page has an associated PCache */
000114    if( pPg->flags & PGHDR_CLEAN ){
000115      assert( (pPg->flags & PGHDR_DIRTY)==0 );/* Cannot be both CLEAN and DIRTY */
000116      assert( pCache->pDirty!=pPg );          /* CLEAN pages not on dirty list */
000117      assert( pCache->pDirtyTail!=pPg );
000118    }
000119    /* WRITEABLE pages must also be DIRTY */
000120    if( pPg->flags & PGHDR_WRITEABLE ){
000121      assert( pPg->flags & PGHDR_DIRTY );     /* WRITEABLE implies DIRTY */
000122    }
000123    /* NEED_SYNC can be set independently of WRITEABLE.  This can happen,
000124    ** for example, when using the sqlite3PagerDontWrite() optimization:
000125    **    (1)  Page X is journalled, and gets WRITEABLE and NEED_SEEK.
000126    **    (2)  Page X moved to freelist, WRITEABLE is cleared
000127    **    (3)  Page X reused, WRITEABLE is set again
000128    ** If NEED_SYNC had been cleared in step 2, then it would not be reset
000129    ** in step 3, and page might be written into the database without first
000130    ** syncing the rollback journal, which might cause corruption on a power
000131    ** loss.
000132    **
000133    ** Another example is when the database page size is smaller than the
000134    ** disk sector size.  When any page of a sector is journalled, all pages
000135    ** in that sector are marked NEED_SYNC even if they are still CLEAN, just
000136    ** in case they are later modified, since all pages in the same sector
000137    ** must be journalled and synced before any of those pages can be safely
000138    ** written.
000139    */
000140    return 1;
000141  }
000142  #endif /* SQLITE_DEBUG */
000143  
000144  
000145  /********************************** Linked List Management ********************/
000146  
000147  /* Allowed values for second argument to pcacheManageDirtyList() */
000148  #define PCACHE_DIRTYLIST_REMOVE   1    /* Remove pPage from dirty list */
000149  #define PCACHE_DIRTYLIST_ADD      2    /* Add pPage to the dirty list */
000150  #define PCACHE_DIRTYLIST_FRONT    3    /* Move pPage to the front of the list */
000151  
000152  /*
000153  ** Manage pPage's participation on the dirty list.  Bits of the addRemove
000154  ** argument determines what operation to do.  The 0x01 bit means first
000155  ** remove pPage from the dirty list.  The 0x02 means add pPage back to
000156  ** the dirty list.  Doing both moves pPage to the front of the dirty list.
000157  */
000158  static void pcacheManageDirtyList(PgHdr *pPage, u8 addRemove){
000159    PCache *p = pPage->pCache;
000160  
000161    pcacheTrace(("%p.DIRTYLIST.%s %d\n", p,
000162                  addRemove==1 ? "REMOVE" : addRemove==2 ? "ADD" : "FRONT",
000163                  pPage->pgno));
000164    if( addRemove & PCACHE_DIRTYLIST_REMOVE ){
000165      assert( pPage->pDirtyNext || pPage==p->pDirtyTail );
000166      assert( pPage->pDirtyPrev || pPage==p->pDirty );
000167    
000168      /* Update the PCache1.pSynced variable if necessary. */
000169      if( p->pSynced==pPage ){
000170        p->pSynced = pPage->pDirtyPrev;
000171      }
000172    
000173      if( pPage->pDirtyNext ){
000174        pPage->pDirtyNext->pDirtyPrev = pPage->pDirtyPrev;
000175      }else{
000176        assert( pPage==p->pDirtyTail );
000177        p->pDirtyTail = pPage->pDirtyPrev;
000178      }
000179      if( pPage->pDirtyPrev ){
000180        pPage->pDirtyPrev->pDirtyNext = pPage->pDirtyNext;
000181      }else{
000182        /* If there are now no dirty pages in the cache, set eCreate to 2. 
000183        ** This is an optimization that allows sqlite3PcacheFetch() to skip
000184        ** searching for a dirty page to eject from the cache when it might
000185        ** otherwise have to.  */
000186        assert( pPage==p->pDirty );
000187        p->pDirty = pPage->pDirtyNext;
000188        assert( p->bPurgeable || p->eCreate==2 );
000189        if( p->pDirty==0 ){         /*OPTIMIZATION-IF-TRUE*/
000190          assert( p->bPurgeable==0 || p->eCreate==1 );
000191          p->eCreate = 2;
000192        }
000193      }
000194    }
000195    if( addRemove & PCACHE_DIRTYLIST_ADD ){
000196      pPage->pDirtyPrev = 0;
000197      pPage->pDirtyNext = p->pDirty;
000198      if( pPage->pDirtyNext ){
000199        assert( pPage->pDirtyNext->pDirtyPrev==0 );
000200        pPage->pDirtyNext->pDirtyPrev = pPage;
000201      }else{
000202        p->pDirtyTail = pPage;
000203        if( p->bPurgeable ){
000204          assert( p->eCreate==2 );
000205          p->eCreate = 1;
000206        }
000207      }
000208      p->pDirty = pPage;
000209  
000210      /* If pSynced is NULL and this page has a clear NEED_SYNC flag, set
000211      ** pSynced to point to it. Checking the NEED_SYNC flag is an 
000212      ** optimization, as if pSynced points to a page with the NEED_SYNC
000213      ** flag set sqlite3PcacheFetchStress() searches through all newer 
000214      ** entries of the dirty-list for a page with NEED_SYNC clear anyway.  */
000215      if( !p->pSynced 
000216       && 0==(pPage->flags&PGHDR_NEED_SYNC)   /*OPTIMIZATION-IF-FALSE*/
000217      ){
000218        p->pSynced = pPage;
000219      }
000220    }
000221    pcacheDump(p);
000222  }
000223  
000224  /*
000225  ** Wrapper around the pluggable caches xUnpin method. If the cache is
000226  ** being used for an in-memory database, this function is a no-op.
000227  */
000228  static void pcacheUnpin(PgHdr *p){
000229    if( p->pCache->bPurgeable ){
000230      pcacheTrace(("%p.UNPIN %d\n", p->pCache, p->pgno));
000231      sqlite3GlobalConfig.pcache2.xUnpin(p->pCache->pCache, p->pPage, 0);
000232      pcacheDump(p->pCache);
000233    }
000234  }
000235  
000236  /*
000237  ** Compute the number of pages of cache requested.   p->szCache is the
000238  ** cache size requested by the "PRAGMA cache_size" statement.
000239  */
000240  static int numberOfCachePages(PCache *p){
000241    if( p->szCache>=0 ){
000242      /* IMPLEMENTATION-OF: R-42059-47211 If the argument N is positive then the
000243      ** suggested cache size is set to N. */
000244      return p->szCache;
000245    }else{
000246      i64 n;
000247      /* IMPLEMANTATION-OF: R-59858-46238 If the argument N is negative, then the
000248      ** number of cache pages is adjusted to be a number of pages that would
000249      ** use approximately abs(N*1024) bytes of memory based on the current
000250      ** page size. */
000251      n = ((-1024*(i64)p->szCache)/(p->szPage+p->szExtra));
000252      if( n>1000000000 ) n = 1000000000;
000253      return (int)n;
000254    }
000255  }
000256  
000257  /*************************************************** General Interfaces ******
000258  **
000259  ** Initialize and shutdown the page cache subsystem. Neither of these 
000260  ** functions are threadsafe.
000261  */
000262  int sqlite3PcacheInitialize(void){
000263    if( sqlite3GlobalConfig.pcache2.xInit==0 ){
000264      /* IMPLEMENTATION-OF: R-26801-64137 If the xInit() method is NULL, then the
000265      ** built-in default page cache is used instead of the application defined
000266      ** page cache. */
000267      sqlite3PCacheSetDefault();
000268      assert( sqlite3GlobalConfig.pcache2.xInit!=0 );
000269    }
000270    return sqlite3GlobalConfig.pcache2.xInit(sqlite3GlobalConfig.pcache2.pArg);
000271  }
000272  void sqlite3PcacheShutdown(void){
000273    if( sqlite3GlobalConfig.pcache2.xShutdown ){
000274      /* IMPLEMENTATION-OF: R-26000-56589 The xShutdown() method may be NULL. */
000275      sqlite3GlobalConfig.pcache2.xShutdown(sqlite3GlobalConfig.pcache2.pArg);
000276    }
000277  }
000278  
000279  /*
000280  ** Return the size in bytes of a PCache object.
000281  */
000282  int sqlite3PcacheSize(void){ return sizeof(PCache); }
000283  
000284  /*
000285  ** Create a new PCache object. Storage space to hold the object
000286  ** has already been allocated and is passed in as the p pointer. 
000287  ** The caller discovers how much space needs to be allocated by 
000288  ** calling sqlite3PcacheSize().
000289  **
000290  ** szExtra is some extra space allocated for each page.  The first
000291  ** 8 bytes of the extra space will be zeroed as the page is allocated,
000292  ** but remaining content will be uninitialized.  Though it is opaque
000293  ** to this module, the extra space really ends up being the MemPage
000294  ** structure in the pager.
000295  */
000296  int sqlite3PcacheOpen(
000297    int szPage,                  /* Size of every page */
000298    int szExtra,                 /* Extra space associated with each page */
000299    int bPurgeable,              /* True if pages are on backing store */
000300    int (*xStress)(void*,PgHdr*),/* Call to try to make pages clean */
000301    void *pStress,               /* Argument to xStress */
000302    PCache *p                    /* Preallocated space for the PCache */
000303  ){
000304    memset(p, 0, sizeof(PCache));
000305    p->szPage = 1;
000306    p->szExtra = szExtra;
000307    assert( szExtra>=8 );  /* First 8 bytes will be zeroed */
000308    p->bPurgeable = bPurgeable;
000309    p->eCreate = 2;
000310    p->xStress = xStress;
000311    p->pStress = pStress;
000312    p->szCache = 100;
000313    p->szSpill = 1;
000314    pcacheTrace(("%p.OPEN szPage %d bPurgeable %d\n",p,szPage,bPurgeable));
000315    return sqlite3PcacheSetPageSize(p, szPage);
000316  }
000317  
000318  /*
000319  ** Change the page size for PCache object. The caller must ensure that there
000320  ** are no outstanding page references when this function is called.
000321  */
000322  int sqlite3PcacheSetPageSize(PCache *pCache, int szPage){
000323    assert( pCache->nRefSum==0 && pCache->pDirty==0 );
000324    if( pCache->szPage ){
000325      sqlite3_pcache *pNew;
000326      pNew = sqlite3GlobalConfig.pcache2.xCreate(
000327                  szPage, pCache->szExtra + ROUND8(sizeof(PgHdr)),
000328                  pCache->bPurgeable
000329      );
000330      if( pNew==0 ) return SQLITE_NOMEM_BKPT;
000331      sqlite3GlobalConfig.pcache2.xCachesize(pNew, numberOfCachePages(pCache));
000332      if( pCache->pCache ){
000333        sqlite3GlobalConfig.pcache2.xDestroy(pCache->pCache);
000334      }
000335      pCache->pCache = pNew;
000336      pCache->szPage = szPage;
000337      pcacheTrace(("%p.PAGESIZE %d\n",pCache,szPage));
000338    }
000339    return SQLITE_OK;
000340  }
000341  
000342  /*
000343  ** Try to obtain a page from the cache.
000344  **
000345  ** This routine returns a pointer to an sqlite3_pcache_page object if
000346  ** such an object is already in cache, or if a new one is created.
000347  ** This routine returns a NULL pointer if the object was not in cache
000348  ** and could not be created.
000349  **
000350  ** The createFlags should be 0 to check for existing pages and should
000351  ** be 3 (not 1, but 3) to try to create a new page.
000352  **
000353  ** If the createFlag is 0, then NULL is always returned if the page
000354  ** is not already in the cache.  If createFlag is 1, then a new page
000355  ** is created only if that can be done without spilling dirty pages
000356  ** and without exceeding the cache size limit.
000357  **
000358  ** The caller needs to invoke sqlite3PcacheFetchFinish() to properly
000359  ** initialize the sqlite3_pcache_page object and convert it into a
000360  ** PgHdr object.  The sqlite3PcacheFetch() and sqlite3PcacheFetchFinish()
000361  ** routines are split this way for performance reasons. When separated
000362  ** they can both (usually) operate without having to push values to
000363  ** the stack on entry and pop them back off on exit, which saves a
000364  ** lot of pushing and popping.
000365  */
000366  sqlite3_pcache_page *sqlite3PcacheFetch(
000367    PCache *pCache,       /* Obtain the page from this cache */
000368    Pgno pgno,            /* Page number to obtain */
000369    int createFlag        /* If true, create page if it does not exist already */
000370  ){
000371    int eCreate;
000372    sqlite3_pcache_page *pRes;
000373  
000374    assert( pCache!=0 );
000375    assert( pCache->pCache!=0 );
000376    assert( createFlag==3 || createFlag==0 );
000377    assert( pCache->eCreate==((pCache->bPurgeable && pCache->pDirty) ? 1 : 2) );
000378  
000379    /* eCreate defines what to do if the page does not exist.
000380    **    0     Do not allocate a new page.  (createFlag==0)
000381    **    1     Allocate a new page if doing so is inexpensive.
000382    **          (createFlag==1 AND bPurgeable AND pDirty)
000383    **    2     Allocate a new page even it doing so is difficult.
000384    **          (createFlag==1 AND !(bPurgeable AND pDirty)
000385    */
000386    eCreate = createFlag & pCache->eCreate;
000387    assert( eCreate==0 || eCreate==1 || eCreate==2 );
000388    assert( createFlag==0 || pCache->eCreate==eCreate );
000389    assert( createFlag==0 || eCreate==1+(!pCache->bPurgeable||!pCache->pDirty) );
000390    pRes = sqlite3GlobalConfig.pcache2.xFetch(pCache->pCache, pgno, eCreate);
000391    pcacheTrace(("%p.FETCH %d%s (result: %p)\n",pCache,pgno,
000392                 createFlag?" create":"",pRes));
000393    return pRes;
000394  }
000395  
000396  /*
000397  ** If the sqlite3PcacheFetch() routine is unable to allocate a new
000398  ** page because no clean pages are available for reuse and the cache
000399  ** size limit has been reached, then this routine can be invoked to 
000400  ** try harder to allocate a page.  This routine might invoke the stress
000401  ** callback to spill dirty pages to the journal.  It will then try to
000402  ** allocate the new page and will only fail to allocate a new page on
000403  ** an OOM error.
000404  **
000405  ** This routine should be invoked only after sqlite3PcacheFetch() fails.
000406  */
000407  int sqlite3PcacheFetchStress(
000408    PCache *pCache,                 /* Obtain the page from this cache */
000409    Pgno pgno,                      /* Page number to obtain */
000410    sqlite3_pcache_page **ppPage    /* Write result here */
000411  ){
000412    PgHdr *pPg;
000413    if( pCache->eCreate==2 ) return 0;
000414  
000415    if( sqlite3PcachePagecount(pCache)>pCache->szSpill ){
000416      /* Find a dirty page to write-out and recycle. First try to find a 
000417      ** page that does not require a journal-sync (one with PGHDR_NEED_SYNC
000418      ** cleared), but if that is not possible settle for any other 
000419      ** unreferenced dirty page.
000420      **
000421      ** If the LRU page in the dirty list that has a clear PGHDR_NEED_SYNC
000422      ** flag is currently referenced, then the following may leave pSynced
000423      ** set incorrectly (pointing to other than the LRU page with NEED_SYNC
000424      ** cleared). This is Ok, as pSynced is just an optimization.  */
000425      for(pPg=pCache->pSynced; 
000426          pPg && (pPg->nRef || (pPg->flags&PGHDR_NEED_SYNC)); 
000427          pPg=pPg->pDirtyPrev
000428      );
000429      pCache->pSynced = pPg;
000430      if( !pPg ){
000431        for(pPg=pCache->pDirtyTail; pPg && pPg->nRef; pPg=pPg->pDirtyPrev);
000432      }
000433      if( pPg ){
000434        int rc;
000435  #ifdef SQLITE_LOG_CACHE_SPILL
000436        sqlite3_log(SQLITE_FULL, 
000437                    "spill page %d making room for %d - cache used: %d/%d",
000438                    pPg->pgno, pgno,
000439                    sqlite3GlobalConfig.pcache2.xPagecount(pCache->pCache),
000440                  numberOfCachePages(pCache));
000441  #endif
000442        pcacheTrace(("%p.SPILL %d\n",pCache,pPg->pgno));
000443        rc = pCache->xStress(pCache->pStress, pPg);
000444        pcacheDump(pCache);
000445        if( rc!=SQLITE_OK && rc!=SQLITE_BUSY ){
000446          return rc;
000447        }
000448      }
000449    }
000450    *ppPage = sqlite3GlobalConfig.pcache2.xFetch(pCache->pCache, pgno, 2);
000451    return *ppPage==0 ? SQLITE_NOMEM_BKPT : SQLITE_OK;
000452  }
000453  
000454  /*
000455  ** This is a helper routine for sqlite3PcacheFetchFinish()
000456  **
000457  ** In the uncommon case where the page being fetched has not been
000458  ** initialized, this routine is invoked to do the initialization.
000459  ** This routine is broken out into a separate function since it
000460  ** requires extra stack manipulation that can be avoided in the common
000461  ** case.
000462  */
000463  static SQLITE_NOINLINE PgHdr *pcacheFetchFinishWithInit(
000464    PCache *pCache,             /* Obtain the page from this cache */
000465    Pgno pgno,                  /* Page number obtained */
000466    sqlite3_pcache_page *pPage  /* Page obtained by prior PcacheFetch() call */
000467  ){
000468    PgHdr *pPgHdr;
000469    assert( pPage!=0 );
000470    pPgHdr = (PgHdr*)pPage->pExtra;
000471    assert( pPgHdr->pPage==0 );
000472    memset(&pPgHdr->pDirty, 0, sizeof(PgHdr) - offsetof(PgHdr,pDirty));
000473    pPgHdr->pPage = pPage;
000474    pPgHdr->pData = pPage->pBuf;
000475    pPgHdr->pExtra = (void *)&pPgHdr[1];
000476    memset(pPgHdr->pExtra, 0, 8);
000477    pPgHdr->pCache = pCache;
000478    pPgHdr->pgno = pgno;
000479    pPgHdr->flags = PGHDR_CLEAN;
000480    return sqlite3PcacheFetchFinish(pCache,pgno,pPage);
000481  }
000482  
000483  /*
000484  ** This routine converts the sqlite3_pcache_page object returned by
000485  ** sqlite3PcacheFetch() into an initialized PgHdr object.  This routine
000486  ** must be called after sqlite3PcacheFetch() in order to get a usable
000487  ** result.
000488  */
000489  PgHdr *sqlite3PcacheFetchFinish(
000490    PCache *pCache,             /* Obtain the page from this cache */
000491    Pgno pgno,                  /* Page number obtained */
000492    sqlite3_pcache_page *pPage  /* Page obtained by prior PcacheFetch() call */
000493  ){
000494    PgHdr *pPgHdr;
000495  
000496    assert( pPage!=0 );
000497    pPgHdr = (PgHdr *)pPage->pExtra;
000498  
000499    if( !pPgHdr->pPage ){
000500      return pcacheFetchFinishWithInit(pCache, pgno, pPage);
000501    }
000502    pCache->nRefSum++;
000503    pPgHdr->nRef++;
000504    assert( sqlite3PcachePageSanity(pPgHdr) );
000505    return pPgHdr;
000506  }
000507  
000508  /*
000509  ** Decrement the reference count on a page. If the page is clean and the
000510  ** reference count drops to 0, then it is made eligible for recycling.
000511  */
000512  void SQLITE_NOINLINE sqlite3PcacheRelease(PgHdr *p){
000513    assert( p->nRef>0 );
000514    p->pCache->nRefSum--;
000515    if( (--p->nRef)==0 ){
000516      if( p->flags&PGHDR_CLEAN ){
000517        pcacheUnpin(p);
000518      }else{
000519        pcacheManageDirtyList(p, PCACHE_DIRTYLIST_FRONT);
000520      }
000521    }
000522  }
000523  
000524  /*
000525  ** Increase the reference count of a supplied page by 1.
000526  */
000527  void sqlite3PcacheRef(PgHdr *p){
000528    assert(p->nRef>0);
000529    assert( sqlite3PcachePageSanity(p) );
000530    p->nRef++;
000531    p->pCache->nRefSum++;
000532  }
000533  
000534  /*
000535  ** Drop a page from the cache. There must be exactly one reference to the
000536  ** page. This function deletes that reference, so after it returns the
000537  ** page pointed to by p is invalid.
000538  */
000539  void sqlite3PcacheDrop(PgHdr *p){
000540    assert( p->nRef==1 );
000541    assert( sqlite3PcachePageSanity(p) );
000542    if( p->flags&PGHDR_DIRTY ){
000543      pcacheManageDirtyList(p, PCACHE_DIRTYLIST_REMOVE);
000544    }
000545    p->pCache->nRefSum--;
000546    sqlite3GlobalConfig.pcache2.xUnpin(p->pCache->pCache, p->pPage, 1);
000547  }
000548  
000549  /*
000550  ** Make sure the page is marked as dirty. If it isn't dirty already,
000551  ** make it so.
000552  */
000553  void sqlite3PcacheMakeDirty(PgHdr *p){
000554    assert( p->nRef>0 || p->pCache->bPurgeable==0 );
000555    testcase( p->nRef==0 );
000556    assert( sqlite3PcachePageSanity(p) );
000557    if( p->flags & (PGHDR_CLEAN|PGHDR_DONT_WRITE) ){    /*OPTIMIZATION-IF-FALSE*/
000558      p->flags &= ~PGHDR_DONT_WRITE;
000559      if( p->flags & PGHDR_CLEAN ){
000560        p->flags ^= (PGHDR_DIRTY|PGHDR_CLEAN);
000561        pcacheTrace(("%p.DIRTY %d\n",p->pCache,p->pgno));
000562        assert( (p->flags & (PGHDR_DIRTY|PGHDR_CLEAN))==PGHDR_DIRTY );
000563        pcacheManageDirtyList(p, PCACHE_DIRTYLIST_ADD);
000564      }
000565      assert( sqlite3PcachePageSanity(p) );
000566    }
000567  }
000568  
000569  /*
000570  ** Make sure the page is marked as clean. If it isn't clean already,
000571  ** make it so.
000572  */
000573  void sqlite3PcacheMakeClean(PgHdr *p){
000574    assert( sqlite3PcachePageSanity(p) );
000575    assert( (p->flags & PGHDR_DIRTY)!=0 );
000576    assert( (p->flags & PGHDR_CLEAN)==0 );
000577    pcacheManageDirtyList(p, PCACHE_DIRTYLIST_REMOVE);
000578    p->flags &= ~(PGHDR_DIRTY|PGHDR_NEED_SYNC|PGHDR_WRITEABLE);
000579    p->flags |= PGHDR_CLEAN;
000580    pcacheTrace(("%p.CLEAN %d\n",p->pCache,p->pgno));
000581    assert( sqlite3PcachePageSanity(p) );
000582    if( p->nRef==0 ){
000583      pcacheUnpin(p);
000584    }
000585  }
000586  
000587  /*
000588  ** Make every page in the cache clean.
000589  */
000590  void sqlite3PcacheCleanAll(PCache *pCache){
000591    PgHdr *p;
000592    pcacheTrace(("%p.CLEAN-ALL\n",pCache));
000593    while( (p = pCache->pDirty)!=0 ){
000594      sqlite3PcacheMakeClean(p);
000595    }
000596  }
000597  
000598  /*
000599  ** Clear the PGHDR_NEED_SYNC and PGHDR_WRITEABLE flag from all dirty pages.
000600  */
000601  void sqlite3PcacheClearWritable(PCache *pCache){
000602    PgHdr *p;
000603    pcacheTrace(("%p.CLEAR-WRITEABLE\n",pCache));
000604    for(p=pCache->pDirty; p; p=p->pDirtyNext){
000605      p->flags &= ~(PGHDR_NEED_SYNC|PGHDR_WRITEABLE);
000606    }
000607    pCache->pSynced = pCache->pDirtyTail;
000608  }
000609  
000610  /*
000611  ** Clear the PGHDR_NEED_SYNC flag from all dirty pages.
000612  */
000613  void sqlite3PcacheClearSyncFlags(PCache *pCache){
000614    PgHdr *p;
000615    for(p=pCache->pDirty; p; p=p->pDirtyNext){
000616      p->flags &= ~PGHDR_NEED_SYNC;
000617    }
000618    pCache->pSynced = pCache->pDirtyTail;
000619  }
000620  
000621  /*
000622  ** Change the page number of page p to newPgno. 
000623  */
000624  void sqlite3PcacheMove(PgHdr *p, Pgno newPgno){
000625    PCache *pCache = p->pCache;
000626    assert( p->nRef>0 );
000627    assert( newPgno>0 );
000628    assert( sqlite3PcachePageSanity(p) );
000629    pcacheTrace(("%p.MOVE %d -> %d\n",pCache,p->pgno,newPgno));
000630    sqlite3GlobalConfig.pcache2.xRekey(pCache->pCache, p->pPage, p->pgno,newPgno);
000631    p->pgno = newPgno;
000632    if( (p->flags&PGHDR_DIRTY) && (p->flags&PGHDR_NEED_SYNC) ){
000633      pcacheManageDirtyList(p, PCACHE_DIRTYLIST_FRONT);
000634    }
000635  }
000636  
000637  /*
000638  ** Drop every cache entry whose page number is greater than "pgno". The
000639  ** caller must ensure that there are no outstanding references to any pages
000640  ** other than page 1 with a page number greater than pgno.
000641  **
000642  ** If there is a reference to page 1 and the pgno parameter passed to this
000643  ** function is 0, then the data area associated with page 1 is zeroed, but
000644  ** the page object is not dropped.
000645  */
000646  void sqlite3PcacheTruncate(PCache *pCache, Pgno pgno){
000647    if( pCache->pCache ){
000648      PgHdr *p;
000649      PgHdr *pNext;
000650      pcacheTrace(("%p.TRUNCATE %d\n",pCache,pgno));
000651      for(p=pCache->pDirty; p; p=pNext){
000652        pNext = p->pDirtyNext;
000653        /* This routine never gets call with a positive pgno except right
000654        ** after sqlite3PcacheCleanAll().  So if there are dirty pages,
000655        ** it must be that pgno==0.
000656        */
000657        assert( p->pgno>0 );
000658        if( p->pgno>pgno ){
000659          assert( p->flags&PGHDR_DIRTY );
000660          sqlite3PcacheMakeClean(p);
000661        }
000662      }
000663      if( pgno==0 && pCache->nRefSum ){
000664        sqlite3_pcache_page *pPage1;
000665        pPage1 = sqlite3GlobalConfig.pcache2.xFetch(pCache->pCache,1,0);
000666        if( ALWAYS(pPage1) ){  /* Page 1 is always available in cache, because
000667                               ** pCache->nRefSum>0 */
000668          memset(pPage1->pBuf, 0, pCache->szPage);
000669          pgno = 1;
000670        }
000671      }
000672      sqlite3GlobalConfig.pcache2.xTruncate(pCache->pCache, pgno+1);
000673    }
000674  }
000675  
000676  /*
000677  ** Close a cache.
000678  */
000679  void sqlite3PcacheClose(PCache *pCache){
000680    assert( pCache->pCache!=0 );
000681    pcacheTrace(("%p.CLOSE\n",pCache));
000682    sqlite3GlobalConfig.pcache2.xDestroy(pCache->pCache);
000683  }
000684  
000685  /* 
000686  ** Discard the contents of the cache.
000687  */
000688  void sqlite3PcacheClear(PCache *pCache){
000689    sqlite3PcacheTruncate(pCache, 0);
000690  }
000691  
000692  /*
000693  ** Merge two lists of pages connected by pDirty and in pgno order.
000694  ** Do not bother fixing the pDirtyPrev pointers.
000695  */
000696  static PgHdr *pcacheMergeDirtyList(PgHdr *pA, PgHdr *pB){
000697    PgHdr result, *pTail;
000698    pTail = &result;
000699    assert( pA!=0 && pB!=0 );
000700    for(;;){
000701      if( pA->pgno<pB->pgno ){
000702        pTail->pDirty = pA;
000703        pTail = pA;
000704        pA = pA->pDirty;
000705        if( pA==0 ){
000706          pTail->pDirty = pB;
000707          break;
000708        }
000709      }else{
000710        pTail->pDirty = pB;
000711        pTail = pB;
000712        pB = pB->pDirty;
000713        if( pB==0 ){
000714          pTail->pDirty = pA;
000715          break;
000716        }
000717      }
000718    }
000719    return result.pDirty;
000720  }
000721  
000722  /*
000723  ** Sort the list of pages in accending order by pgno.  Pages are
000724  ** connected by pDirty pointers.  The pDirtyPrev pointers are
000725  ** corrupted by this sort.
000726  **
000727  ** Since there cannot be more than 2^31 distinct pages in a database,
000728  ** there cannot be more than 31 buckets required by the merge sorter.
000729  ** One extra bucket is added to catch overflow in case something
000730  ** ever changes to make the previous sentence incorrect.
000731  */
000732  #define N_SORT_BUCKET  32
000733  static PgHdr *pcacheSortDirtyList(PgHdr *pIn){
000734    PgHdr *a[N_SORT_BUCKET], *p;
000735    int i;
000736    memset(a, 0, sizeof(a));
000737    while( pIn ){
000738      p = pIn;
000739      pIn = p->pDirty;
000740      p->pDirty = 0;
000741      for(i=0; ALWAYS(i<N_SORT_BUCKET-1); i++){
000742        if( a[i]==0 ){
000743          a[i] = p;
000744          break;
000745        }else{
000746          p = pcacheMergeDirtyList(a[i], p);
000747          a[i] = 0;
000748        }
000749      }
000750      if( NEVER(i==N_SORT_BUCKET-1) ){
000751        /* To get here, there need to be 2^(N_SORT_BUCKET) elements in
000752        ** the input list.  But that is impossible.
000753        */
000754        a[i] = pcacheMergeDirtyList(a[i], p);
000755      }
000756    }
000757    p = a[0];
000758    for(i=1; i<N_SORT_BUCKET; i++){
000759      if( a[i]==0 ) continue;
000760      p = p ? pcacheMergeDirtyList(p, a[i]) : a[i];
000761    }
000762    return p;
000763  }
000764  
000765  /*
000766  ** Return a list of all dirty pages in the cache, sorted by page number.
000767  */
000768  PgHdr *sqlite3PcacheDirtyList(PCache *pCache){
000769    PgHdr *p;
000770    for(p=pCache->pDirty; p; p=p->pDirtyNext){
000771      p->pDirty = p->pDirtyNext;
000772    }
000773    return pcacheSortDirtyList(pCache->pDirty);
000774  }
000775  
000776  /* 
000777  ** Return the total number of references to all pages held by the cache.
000778  **
000779  ** This is not the total number of pages referenced, but the sum of the
000780  ** reference count for all pages.
000781  */
000782  int sqlite3PcacheRefCount(PCache *pCache){
000783    return pCache->nRefSum;
000784  }
000785  
000786  /*
000787  ** Return the number of references to the page supplied as an argument.
000788  */
000789  int sqlite3PcachePageRefcount(PgHdr *p){
000790    return p->nRef;
000791  }
000792  
000793  /* 
000794  ** Return the total number of pages in the cache.
000795  */
000796  int sqlite3PcachePagecount(PCache *pCache){
000797    assert( pCache->pCache!=0 );
000798    return sqlite3GlobalConfig.pcache2.xPagecount(pCache->pCache);
000799  }
000800  
000801  #ifdef SQLITE_TEST
000802  /*
000803  ** Get the suggested cache-size value.
000804  */
000805  int sqlite3PcacheGetCachesize(PCache *pCache){
000806    return numberOfCachePages(pCache);
000807  }
000808  #endif
000809  
000810  /*
000811  ** Set the suggested cache-size value.
000812  */
000813  void sqlite3PcacheSetCachesize(PCache *pCache, int mxPage){
000814    assert( pCache->pCache!=0 );
000815    pCache->szCache = mxPage;
000816    sqlite3GlobalConfig.pcache2.xCachesize(pCache->pCache,
000817                                           numberOfCachePages(pCache));
000818  }
000819  
000820  /*
000821  ** Set the suggested cache-spill value.  Make no changes if if the
000822  ** argument is zero.  Return the effective cache-spill size, which will
000823  ** be the larger of the szSpill and szCache.
000824  */
000825  int sqlite3PcacheSetSpillsize(PCache *p, int mxPage){
000826    int res;
000827    assert( p->pCache!=0 );
000828    if( mxPage ){
000829      if( mxPage<0 ){
000830        mxPage = (int)((-1024*(i64)mxPage)/(p->szPage+p->szExtra));
000831      }
000832      p->szSpill = mxPage;
000833    }
000834    res = numberOfCachePages(p);
000835    if( res<p->szSpill ) res = p->szSpill; 
000836    return res;
000837  }
000838  
000839  /*
000840  ** Free up as much memory as possible from the page cache.
000841  */
000842  void sqlite3PcacheShrink(PCache *pCache){
000843    assert( pCache->pCache!=0 );
000844    sqlite3GlobalConfig.pcache2.xShrink(pCache->pCache);
000845  }
000846  
000847  /*
000848  ** Return the size of the header added by this middleware layer
000849  ** in the page-cache hierarchy.
000850  */
000851  int sqlite3HeaderSizePcache(void){ return ROUND8(sizeof(PgHdr)); }
000852  
000853  /*
000854  ** Return the number of dirty pages currently in the cache, as a percentage
000855  ** of the configured cache size.
000856  */
000857  int sqlite3PCachePercentDirty(PCache *pCache){
000858    PgHdr *pDirty;
000859    int nDirty = 0;
000860    int nCache = numberOfCachePages(pCache);
000861    for(pDirty=pCache->pDirty; pDirty; pDirty=pDirty->pDirtyNext) nDirty++;
000862    return nCache ? (int)(((i64)nDirty * 100) / nCache) : 0;
000863  }
000864  
000865  #ifdef SQLITE_DIRECT_OVERFLOW_READ
000866  /* 
000867  ** Return true if there are one or more dirty pages in the cache. Else false.
000868  */
000869  int sqlite3PCacheIsDirty(PCache *pCache){
000870    return (pCache->pDirty!=0);
000871  }
000872  #endif
000873  
000874  #if defined(SQLITE_CHECK_PAGES) || defined(SQLITE_DEBUG)
000875  /*
000876  ** For all dirty pages currently in the cache, invoke the specified
000877  ** callback. This is only used if the SQLITE_CHECK_PAGES macro is
000878  ** defined.
000879  */
000880  void sqlite3PcacheIterateDirty(PCache *pCache, void (*xIter)(PgHdr *)){
000881    PgHdr *pDirty;
000882    for(pDirty=pCache->pDirty; pDirty; pDirty=pDirty->pDirtyNext){
000883      xIter(pDirty);
000884    }
000885  }
000886  #endif