1 /*

     2 ** 2008 August 05

     3 **

     4 ** The author disclaims copyright to this source code.  In place of

     5 ** a legal notice, here is a blessing:

     6 **

     7 **    May you do good and not evil.

     8 **    May you find forgiveness for yourself and forgive others.

     9 **    May you share freely, never taking more than you give.

    10 **

    11 *************************************************************************

    12 ** This file implements that page cache.

    13 **

    14 ** @(#) $Id: pcache.c,v 1.33 2008/09/29 11:49:48 danielk1977 Exp $

    15 */

    16 #include "sqliteInt.h"

    17 

    18 /*

    19 ** A complete page cache is an instance of this structure.

    20 **

    21 ** A cache may only be deleted by its owner and while holding the

    22 ** SQLITE_MUTEX_STATUS_LRU mutex.

    23 */

    24 struct PCache {

    25   /*********************************************************************

    26   ** The first group of elements may be read or written at any time by

    27   ** the cache owner without holding the mutex.  No thread other than the

    28   ** cache owner is permitted to access these elements at any time.

    29   */

    30   PgHdr *pDirty, *pDirtyTail;         /* List of dirty pages in LRU order */

    31   PgHdr *pSynced;                     /* Last synced page in dirty page list */

    32   int nRef;                           /* Number of pinned pages */

    33   int nPinned;                        /* Number of pinned and/or dirty pages */

    34   int nMax;                           /* Configured cache size */

    35   int nMin;                           /* Configured minimum cache size */

    36   /**********************************************************************

    37   ** The next group of elements are fixed when the cache is created and

    38   ** may not be changed afterwards.  These elements can read at any time by

    39   ** the cache owner or by any thread holding the the mutex.  Non-owner

    40   ** threads must hold the mutex when reading these elements to prevent

    41   ** the entire PCache object from being deleted during the read.

    42   */

    43   int szPage;                         /* Size of every page in this cache */

    44   int szExtra;                        /* Size of extra space for each page */

    45   int bPurgeable;                     /* True if pages are on backing store */

    46   int (*xStress)(void*,PgHdr*);       /* Call to try make a page clean */

    47   void *pStress;                      /* Argument to xStress */

    48   /**********************************************************************

    49   ** The final group of elements can only be accessed while holding the

    50   ** mutex.  Both the cache owner and any other thread must hold the mutex

    51   ** to read or write any of these elements.

    52   */

    53   int nPage;                          /* Total number of pages in apHash */

    54   int nHash;                          /* Number of slots in apHash[] */

    55   PgHdr **apHash;                     /* Hash table for fast lookup by pgno */

    56   PgHdr *pClean;                      /* List of clean pages in use */

    57 };

    58 

    59 /*

    60 ** Free slots in the page block allocator

    61 */

    62 typedef struct PgFreeslot PgFreeslot;

    63 struct PgFreeslot {

    64   PgFreeslot *pNext;  /* Next free slot */

    65 };

    66 

    67 /*

    68 ** Global data for the page cache.

    69 */

    70 static SQLITE_WSD struct PCacheGlobal {

    71   int isInit;                         /* True when initialized */

    72   sqlite3_mutex *mutex;               /* static mutex MUTEX_STATIC_LRU */

    73 

    74   int nMaxPage;                       /* Sum of nMaxPage for purgeable caches */

    75   int nMinPage;                       /* Sum of nMinPage for purgeable caches */

    76   int nCurrentPage;                   /* Number of purgeable pages allocated */

    77   PgHdr *pLruHead, *pLruTail;         /* LRU list of unused clean pgs */

    78 

    79   /* Variables related to SQLITE_CONFIG_PAGECACHE settings. */

    80   int szSlot;                         /* Size of each free slot */

    81   void *pStart, *pEnd;                /* Bounds of pagecache malloc range */

    82   PgFreeslot *pFree;                  /* Free page blocks */

    83 } pcache = {0};

    84 

    85 /*

    86 ** All code in this file should access the global pcache structure via the

    87 ** alias "pcache_g". This ensures that the WSD emulation is used when

    88 ** compiling for systems that do not support real WSD.

    89 */

    90 #define pcache_g (GLOBAL(struct PCacheGlobal, pcache))

    91 

    92 /*

    93 ** All global variables used by this module (all of which are grouped 

    94 ** together in global structure "pcache" above) are protected by the static 

    95 ** SQLITE_MUTEX_STATIC_LRU mutex. A pointer to this mutex is stored in

    96 ** variable "pcache.mutex".

    97 **

    98 ** Some elements of the PCache and PgHdr structures are protected by the 

    99 ** SQLITE_MUTEX_STATUS_LRU mutex and other are not.  The protected

   100 ** elements are grouped at the end of the structures and are clearly

   101 ** marked.

   102 **

   103 ** Use the following macros must surround all access (read or write)

   104 ** of protected elements.  The mutex is not recursive and may not be

   105 ** entered more than once.  The pcacheMutexHeld() macro should only be

   106 ** used within an assert() to verify that the mutex is being held.

   107 */

   108 #define pcacheEnterMutex() sqlite3_mutex_enter(pcache_g.mutex)

   109 #define pcacheExitMutex()  sqlite3_mutex_leave(pcache_g.mutex)

   110 #define pcacheMutexHeld()  sqlite3_mutex_held(pcache_g.mutex)

   111 

   112 /*

   113 ** Some of the assert() macros in this code are too expensive to run

   114 ** even during normal debugging.  Use them only rarely on long-running

   115 ** tests.  Enable the expensive asserts using the

   116 ** -DSQLITE_ENABLE_EXPENSIVE_ASSERT=1 compile-time option.

   117 */

   118 #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT

   119 # define expensive_assert(X)  assert(X)

   120 #else

   121 # define expensive_assert(X)

   122 #endif

   123 

   124 /********************************** Linked List Management ********************/

   125 

   126 #if !defined(NDEBUG) && defined(SQLITE_ENABLE_EXPENSIVE_ASSERT)

   127 /*

   128 ** This routine verifies that the number of entries in the hash table

   129 ** is pCache->nPage.  This routine is used within assert() statements

   130 ** only and is therefore disabled during production builds.

   131 */

   132 static int pcacheCheckHashCount(PCache *pCache){

   133   int i;

   134   int nPage = 0;

   135   for(i=0; i<pCache->nHash; i++){

   136     PgHdr *p;

   137     for(p=pCache->apHash[i]; p; p=p->pNextHash){

   138       nPage++;

   139     }

   140   }

   141   assert( nPage==pCache->nPage );

   142   return 1;

   143 }

   144 #endif /* !NDEBUG && SQLITE_ENABLE_EXPENSIVE_ASSERT */

   145 

   146 

   147 #if !defined(NDEBUG) && defined(SQLITE_ENABLE_EXPENSIVE_ASSERT)

   148 /*

   149 ** Based on the current value of PCache.nRef and the contents of the

   150 ** PCache.pDirty list, return the expected value of the PCache.nPinned

   151 ** counter. This is only used in debugging builds, as follows:

   152 **

   153 **   expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );

   154 */

   155 static int pcachePinnedCount(PCache *pCache){

   156   PgHdr *p;

   157   int nPinned = pCache->nRef;

   158   for(p=pCache->pDirty; p; p=p->pNext){

   159     if( p->nRef==0 ){

   160       nPinned++;

   161     }

   162   }

   163   return nPinned;

   164 }

   165 #endif /* !NDEBUG && SQLITE_ENABLE_EXPENSIVE_ASSERT */

   166 

   167 

   168 #if !defined(NDEBUG) && defined(SQLITE_ENABLE_EXPENSIVE_ASSERT)

   169 /*

   170 ** Check that the pCache->pSynced variable is set correctly. If it

   171 ** is not, either fail an assert or return zero. Otherwise, return

   172 ** non-zero. This is only used in debugging builds, as follows:

   173 **

   174 **   expensive_assert( pcacheCheckSynced(pCache) );

   175 */

   176 static int pcacheCheckSynced(PCache *pCache){

   177   PgHdr *p = pCache->pDirtyTail;

   178   for(p=pCache->pDirtyTail; p!=pCache->pSynced; p=p->pPrev){

   179     assert( p->nRef || (p->flags&PGHDR_NEED_SYNC) );

   180   }

   181   return (p==0 || p->nRef || (p->flags&PGHDR_NEED_SYNC)==0);

   182 }

   183 #endif /* !NDEBUG && SQLITE_ENABLE_EXPENSIVE_ASSERT */

   184 

   185 

   186 

   187 /*

   188 ** Remove a page from its hash table (PCache.apHash[]).

   189 */

   190 static void pcacheRemoveFromHash(PgHdr *pPage){

   191   assert( pcacheMutexHeld() );

   192   if( pPage->pPrevHash ){

   193     pPage->pPrevHash->pNextHash = pPage->pNextHash;

   194   }else{

   195     PCache *pCache = pPage->pCache;

   196     u32 h = pPage->pgno % pCache->nHash;

   197     assert( pCache->apHash[h]==pPage );

   198     pCache->apHash[h] = pPage->pNextHash;

   199   }

   200   if( pPage->pNextHash ){

   201     pPage->pNextHash->pPrevHash = pPage->pPrevHash;

   202   }

   203   pPage->pCache->nPage--;

   204   expensive_assert( pcacheCheckHashCount(pPage->pCache) );

   205 }

   206 

   207 /*

   208 ** Insert a page into the hash table

   209 **

   210 ** The mutex must be held by the caller.

   211 */

   212 static void pcacheAddToHash(PgHdr *pPage){

   213   PCache *pCache = pPage->pCache;

   214   u32 h = pPage->pgno % pCache->nHash;

   215   assert( pcacheMutexHeld() );

   216   pPage->pNextHash = pCache->apHash[h];

   217   pPage->pPrevHash = 0;

   218   if( pCache->apHash[h] ){

   219     pCache->apHash[h]->pPrevHash = pPage;

   220   }

   221   pCache->apHash[h] = pPage;

   222   pCache->nPage++;

   223   expensive_assert( pcacheCheckHashCount(pCache) );

   224 }

   225 

   226 /*

   227 ** Attempt to increase the size the hash table to contain

   228 ** at least nHash buckets.

   229 */

   230 static int pcacheResizeHash(PCache *pCache, int nHash){

   231   PgHdr *p;

   232   PgHdr **pNew;

   233   assert( pcacheMutexHeld() );

   234 #ifdef SQLITE_MALLOC_SOFT_LIMIT

   235   if( nHash*sizeof(PgHdr*)>SQLITE_MALLOC_SOFT_LIMIT ){

   236     nHash = SQLITE_MALLOC_SOFT_LIMIT/sizeof(PgHdr *);

   237   }

   238 #endif

   239   pcacheExitMutex();

   240   pNew = (PgHdr **)sqlite3Malloc(sizeof(PgHdr*)*nHash);

   241   pcacheEnterMutex();

   242   if( !pNew ){

   243     return SQLITE_NOMEM;

   244   }

   245   memset(pNew, 0, sizeof(PgHdr *)*nHash);

   246   sqlite3_free(pCache->apHash);

   247   pCache->apHash = pNew;

   248   pCache->nHash = nHash;

   249   pCache->nPage = 0;

   250  

   251   for(p=pCache->pClean; p; p=p->pNext){

   252     pcacheAddToHash(p);

   253   }

   254   for(p=pCache->pDirty; p; p=p->pNext){

   255     pcacheAddToHash(p);

   256   }

   257   return SQLITE_OK;

   258 }

   259 

   260 /*

   261 ** Remove a page from a linked list that is headed by *ppHead.

   262 ** *ppHead is either PCache.pClean or PCache.pDirty.

   263 */

   264 static void pcacheRemoveFromList(PgHdr **ppHead, PgHdr *pPage){

   265   int isDirtyList = (ppHead==&pPage->pCache->pDirty);

   266   assert( ppHead==&pPage->pCache->pClean || ppHead==&pPage->pCache->pDirty );

   267   assert( pcacheMutexHeld() || ppHead!=&pPage->pCache->pClean );

   268 

   269   if( pPage->pPrev ){

   270     pPage->pPrev->pNext = pPage->pNext;

   271   }else{

   272     assert( *ppHead==pPage );

   273     *ppHead = pPage->pNext;

   274   }

   275   if( pPage->pNext ){

   276     pPage->pNext->pPrev = pPage->pPrev;

   277   }

   278 

   279   if( isDirtyList ){

   280     PCache *pCache = pPage->pCache;

   281     assert( pPage->pNext || pCache->pDirtyTail==pPage );

   282     if( !pPage->pNext ){

   283       pCache->pDirtyTail = pPage->pPrev;

   284     }

   285     if( pCache->pSynced==pPage ){

   286       PgHdr *pSynced = pPage->pPrev;

   287       while( pSynced && (pSynced->flags&PGHDR_NEED_SYNC) ){

   288         pSynced = pSynced->pPrev;

   289       }

   290       pCache->pSynced = pSynced;

   291     }

   292   }

   293 }

   294 

   295 /*

   296 ** Add a page from a linked list that is headed by *ppHead.

   297 ** *ppHead is either PCache.pClean or PCache.pDirty.

   298 */

   299 static void pcacheAddToList(PgHdr **ppHead, PgHdr *pPage){

   300   int isDirtyList = (ppHead==&pPage->pCache->pDirty);

   301   assert( ppHead==&pPage->pCache->pClean || ppHead==&pPage->pCache->pDirty );

   302 

   303   if( (*ppHead) ){

   304     (*ppHead)->pPrev = pPage;

   305   }

   306   pPage->pNext = *ppHead;

   307   pPage->pPrev = 0;

   308   *ppHead = pPage;

   309 

   310   if( isDirtyList ){

   311     PCache *pCache = pPage->pCache;

   312     if( !pCache->pDirtyTail ){

   313       assert( pPage->pNext==0 );

   314       pCache->pDirtyTail = pPage;

   315     }

   316     if( !pCache->pSynced && 0==(pPage->flags&PGHDR_NEED_SYNC) ){

   317       pCache->pSynced = pPage;

   318     }

   319   }

   320 }

   321 

   322 /*

   323 ** Remove a page from the global LRU list

   324 */

   325 static void pcacheRemoveFromLruList(PgHdr *pPage){

   326   assert( sqlite3_mutex_held(pcache_g.mutex) );

   327   assert( (pPage->flags&PGHDR_DIRTY)==0 );

   328   if( pPage->pCache->bPurgeable==0 ) return;

   329   if( pPage->pNextLru ){

   330     assert( pcache_g.pLruTail!=pPage );

   331     pPage->pNextLru->pPrevLru = pPage->pPrevLru;

   332   }else{

   333     assert( pcache_g.pLruTail==pPage );

   334     pcache_g.pLruTail = pPage->pPrevLru;

   335   }

   336   if( pPage->pPrevLru ){

   337     assert( pcache_g.pLruHead!=pPage );

   338     pPage->pPrevLru->pNextLru = pPage->pNextLru;

   339   }else{

   340     assert( pcache_g.pLruHead==pPage );

   341     pcache_g.pLruHead = pPage->pNextLru;

   342   }

   343 }

   344 

   345 /*

   346 ** Add a page to the global LRU list.  The page is normally added

   347 ** to the front of the list so that it will be the last page recycled.

   348 ** However, if the PGHDR_REUSE_UNLIKELY bit is set, the page is added

   349 ** to the end of the LRU list so that it will be the next to be recycled.

   350 */

   351 static void pcacheAddToLruList(PgHdr *pPage){

   352   assert( sqlite3_mutex_held(pcache_g.mutex) );

   353   assert( (pPage->flags&PGHDR_DIRTY)==0 );

   354   if( pPage->pCache->bPurgeable==0 ) return;

   355   if( pcache_g.pLruTail && (pPage->flags & PGHDR_REUSE_UNLIKELY)!=0 ){

   356     /* If reuse is unlikely.  Put the page at the end of the LRU list

   357     ** where it will be recycled sooner rather than later. 

   358     */

   359     assert( pcache_g.pLruHead );

   360     pPage->pNextLru = 0;

   361     pPage->pPrevLru = pcache_g.pLruTail;

   362     pcache_g.pLruTail->pNextLru = pPage;

   363     pcache_g.pLruTail = pPage;

   364     pPage->flags &= ~PGHDR_REUSE_UNLIKELY;

   365   }else{

   366     /* If reuse is possible. the page goes at the beginning of the LRU

   367     ** list so that it will be the last to be recycled.

   368     */

   369     if( pcache_g.pLruHead ){

   370       pcache_g.pLruHead->pPrevLru = pPage;

   371     }

   372     pPage->pNextLru = pcache_g.pLruHead;

   373     pcache_g.pLruHead = pPage;

   374     pPage->pPrevLru = 0;

   375     if( pcache_g.pLruTail==0 ){

   376       pcache_g.pLruTail = pPage;

   377     }

   378   }

   379 }

   380 

   381 /*********************************************** Memory Allocation ***********

   382 **

   383 ** Initialize the page cache memory pool.

   384 **

   385 ** This must be called at start-time when no page cache lines are

   386 ** checked out. This function is not threadsafe.

   387 */

   388 void sqlite3PCacheBufferSetup(void *pBuf, int sz, int n){

   389   PgFreeslot *p;

   390   sz &= ~7;

   391   pcache_g.szSlot = sz;

   392   pcache_g.pStart = pBuf;

   393   pcache_g.pFree = 0;

   394   while( n-- ){

   395     p = (PgFreeslot*)pBuf;

   396     p->pNext = pcache_g.pFree;

   397     pcache_g.pFree = p;

   398     pBuf = (void*)&((char*)pBuf)[sz];

   399   }

   400   pcache_g.pEnd = pBuf;

   401 }

   402 

   403 /*

   404 ** Allocate a page cache line.  Look in the page cache memory pool first

   405 ** and use an element from it first if available.  If nothing is available

   406 ** in the page cache memory pool, go to the general purpose memory allocator.

   407 */

   408 static void *pcacheMalloc(int sz, PCache *pCache){

   409   assert( sqlite3_mutex_held(pcache_g.mutex) );

   410   if( sz<=pcache_g.szSlot && pcache_g.pFree ){

   411     PgFreeslot *p = pcache_g.pFree;

   412     pcache_g.pFree = p->pNext;

   413     sqlite3StatusSet(SQLITE_STATUS_PAGECACHE_SIZE, sz);

   414     sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_USED, 1);

   415     return (void*)p;

   416   }else{

   417     void *p;

   418 

   419     /* Allocate a new buffer using sqlite3Malloc. Before doing so, exit the

   420     ** global pcache mutex and unlock the pager-cache object pCache. This is 

   421     ** so that if the attempt to allocate a new buffer causes the the 

   422     ** configured soft-heap-limit to be breached, it will be possible to

   423     ** reclaim memory from this pager-cache.

   424     */

   425     pcacheExitMutex();

   426     p = sqlite3Malloc(sz);

   427     pcacheEnterMutex();

   428 

   429     if( p ){

   430       sz = sqlite3MallocSize(p);

   431       sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_OVERFLOW, sz);

   432     }

   433     return p;

   434   }

   435 }

   436 void *sqlite3PageMalloc(int sz){

   437   void *p;

   438   pcacheEnterMutex();

   439   p = pcacheMalloc(sz, 0);

   440   pcacheExitMutex();

   441   return p;

   442 }

   443 

   444 /*

   445 ** Release a pager memory allocation

   446 */

   447 static void pcacheFree(void *p){

   448   assert( sqlite3_mutex_held(pcache_g.mutex) );

   449   if( p==0 ) return;

   450   if( p>=pcache_g.pStart && p<pcache_g.pEnd ){

   451     PgFreeslot *pSlot;

   452     sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_USED, -1);

   453     pSlot = (PgFreeslot*)p;

   454     pSlot->pNext = pcache_g.pFree;

   455     pcache_g.pFree = pSlot;

   456   }else{

   457     int iSize = sqlite3MallocSize(p);

   458     sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_OVERFLOW, -iSize);

   459     sqlite3_free(p);

   460   }

   461 }

   462 void sqlite3PageFree(void *p){

   463   pcacheEnterMutex();

   464   pcacheFree(p);

   465   pcacheExitMutex();

   466 }

   467 

   468 /*

   469 ** Allocate a new page.

   470 */

   471 static PgHdr *pcachePageAlloc(PCache *pCache){

   472   PgHdr *p;

   473   int sz = sizeof(*p) + pCache->szPage + pCache->szExtra;

   474   assert( sqlite3_mutex_held(pcache_g.mutex) );

   475   p = pcacheMalloc(sz, pCache);

   476   if( p==0 ) return 0;

   477   memset(p, 0, sizeof(PgHdr));

   478   p->pData = (void*)&p[1];

   479   p->pExtra = (void*)&((char*)p->pData)[pCache->szPage];

   480   if( pCache->bPurgeable ){

   481     pcache_g.nCurrentPage++;

   482   }

   483   return p;

   484 }

   485 

   486 /*

   487 ** Deallocate a page

   488 */

   489 static void pcachePageFree(PgHdr *p){

   490   assert( sqlite3_mutex_held(pcache_g.mutex) );

   491   if( p->pCache->bPurgeable ){

   492     pcache_g.nCurrentPage--;

   493   }

   494   pcacheFree(p->apSave[0]);

   495   pcacheFree(p->apSave[1]);

   496   pcacheFree(p);

   497 }

   498 

   499 #ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT

   500 /*

   501 ** Return the number of bytes that will be returned to the heap when

   502 ** the argument is passed to pcachePageFree().

   503 */

   504 static int pcachePageSize(PgHdr *p){

   505   assert( sqlite3_mutex_held(pcache_g.mutex) );

   506   assert( !pcache_g.pStart );

   507   assert( p->apSave[0]==0 );

   508   assert( p->apSave[1]==0 );

   509   assert( p && p->pCache );

   510   return sqlite3MallocSize(p);

   511 }

   512 #endif

   513 

   514 /*

   515 ** Attempt to 'recycle' a page from the global LRU list. Only clean,

   516 ** unreferenced pages from purgeable caches are eligible for recycling.

   517 **

   518 ** This function removes page pcache.pLruTail from the global LRU list,

   519 ** and from the hash-table and PCache.pClean list of the owner pcache.

   520 ** There should be no other references to the page.

   521 **

   522 ** A pointer to the recycled page is returned, or NULL if no page is

   523 ** eligible for recycling.

   524 */

   525 static PgHdr *pcacheRecyclePage(void){

   526   PgHdr *p = 0;

   527   assert( sqlite3_mutex_held(pcache_g.mutex) );

   528 

   529   if( (p=pcache_g.pLruTail) ){

   530     assert( (p->flags&PGHDR_DIRTY)==0 );

   531     pcacheRemoveFromLruList(p);

   532     pcacheRemoveFromHash(p);

   533     pcacheRemoveFromList(&p->pCache->pClean, p);

   534   }

   535 

   536   return p;

   537 }

   538 

   539 /*

   540 ** Obtain space for a page. Try to recycle an old page if the limit on the 

   541 ** number of pages has been reached. If the limit has not been reached or

   542 ** there are no pages eligible for recycling, allocate a new page.

   543 **

   544 ** Return a pointer to the new page, or NULL if an OOM condition occurs.

   545 */

   546 static int pcacheRecycleOrAlloc(PCache *pCache, PgHdr **ppPage){

   547   PgHdr *p = 0;

   548 

   549   int szPage = pCache->szPage;

   550   int szExtra = pCache->szExtra;

   551 

   552   assert( pcache_g.isInit );

   553   assert( sqlite3_mutex_held(pcache_g.mutex) );

   554 

   555   *ppPage = 0;

   556 

   557   /* If we have reached either the global or the local limit for 

   558   ** pinned+dirty pages, and there is at least one dirty page,

   559   ** invoke the xStress callback to cause a page to become clean.

   560   */

   561   expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );

   562   expensive_assert( pcacheCheckSynced(pCache) );

   563   if( pCache->xStress

   564    && pCache->pDirty

   565    && (pCache->nPinned>=(pcache_g.nMaxPage+pCache->nMin-pcache_g.nMinPage)

   566            || pCache->nPinned>=pCache->nMax)

   567   ){

   568     PgHdr *pPg;

   569     assert(pCache->pDirtyTail);

   570 

   571     for(pPg=pCache->pSynced; 

   572         pPg && (pPg->nRef || (pPg->flags&PGHDR_NEED_SYNC)); 

   573         pPg=pPg->pPrev

   574     );

   575     if( !pPg ){

   576       for(pPg=pCache->pDirtyTail; pPg && pPg->nRef; pPg=pPg->pPrev);

   577     }

   578     if( pPg ){

   579       int rc;

   580       pcacheExitMutex();

   581       rc = pCache->xStress(pCache->pStress, pPg);

   582       pcacheEnterMutex();

   583       if( rc!=SQLITE_OK && rc!=SQLITE_BUSY ){

   584         return rc;

   585       }

   586     }

   587   }

   588 

   589   /* If either the local or the global page limit has been reached, 

   590   ** try to recycle a page. 

   591   */

   592   if( pCache->bPurgeable && (pCache->nPage>=pCache->nMax-1 ||

   593                              pcache_g.nCurrentPage>=pcache_g.nMaxPage) ){

   594     p = pcacheRecyclePage();

   595   }

   596 

   597   /* If a page has been recycled but it is the wrong size, free it. */

   598   if( p && (p->pCache->szPage!=szPage || p->pCache->szPage!=szExtra) ){

   599     pcachePageFree(p);

   600     p = 0;

   601   }

   602 

   603   if( !p ){

   604     p = pcachePageAlloc(pCache);

   605   }

   606 

   607   *ppPage = p;

   608   return (p?SQLITE_OK:SQLITE_NOMEM);

   609 }

   610 

   611 /*************************************************** General Interfaces ******

   612 **

   613 ** Initialize and shutdown the page cache subsystem. Neither of these 

   614 ** functions are threadsafe.

   615 */

   616 int sqlite3PcacheInitialize(void){

   617   assert( pcache_g.isInit==0 );

   618   memset(&pcache_g, 0, sizeof(pcache));

   619   if( sqlite3GlobalConfig.bCoreMutex ){

   620     /* No need to check the return value of sqlite3_mutex_alloc(). 

   621     ** Allocating a static mutex cannot fail.

   622     */

   623     pcache_g.mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU);

   624   }

   625   pcache_g.isInit = 1;

   626   return SQLITE_OK;

   627 }

   628 void sqlite3PcacheShutdown(void){

   629   memset(&pcache_g, 0, sizeof(pcache));

   630 }

   631 

   632 /*

   633 ** Return the size in bytes of a PCache object.

   634 */

   635 int sqlite3PcacheSize(void){ return sizeof(PCache); }

   636 

   637 /*

   638 ** Create a new PCache object.  Storage space to hold the object

   639 ** has already been allocated and is passed in as the p pointer.

   640 */

   641 void sqlite3PcacheOpen(

   642   int szPage,                  /* Size of every page */

   643   int szExtra,                 /* Extra space associated with each page */

   644   int bPurgeable,              /* True if pages are on backing store */

   645   int (*xStress)(void*,PgHdr*),/* Call to try to make pages clean */

   646   void *pStress,               /* Argument to xStress */

   647   PCache *p                    /* Preallocated space for the PCache */

   648 ){

   649   assert( pcache_g.isInit );

   650   memset(p, 0, sizeof(PCache));

   651   p->szPage = szPage;

   652   p->szExtra = szExtra;

   653   p->bPurgeable = bPurgeable;

   654   p->xStress = xStress;

   655   p->pStress = pStress;

   656   p->nMax = 100;

   657   p->nMin = 10;

   658 

   659   pcacheEnterMutex();

   660   if( bPurgeable ){

   661     pcache_g.nMaxPage += p->nMax;

   662     pcache_g.nMinPage += p->nMin;

   663   }

   664 

   665   pcacheExitMutex();

   666 }

   667 

   668 /*

   669 ** Change the page size for PCache object.  This can only happen

   670 ** when the cache is empty.

   671 */

   672 void sqlite3PcacheSetPageSize(PCache *pCache, int szPage){

   673   assert(pCache->nPage==0);

   674   pCache->szPage = szPage;

   675 }

   676 

   677 /*

   678 ** Try to obtain a page from the cache.

   679 */

   680 int sqlite3PcacheFetch(

   681   PCache *pCache,       /* Obtain the page from this cache */

   682   Pgno pgno,            /* Page number to obtain */

   683   int createFlag,       /* If true, create page if it does not exist already */

   684   PgHdr **ppPage        /* Write the page here */

   685 ){

   686   int rc = SQLITE_OK;

   687   PgHdr *pPage = 0;

   688 

   689   assert( pcache_g.isInit );

   690   assert( pCache!=0 );

   691   assert( pgno>0 );

   692   expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );

   693 

   694   pcacheEnterMutex();

   695 

   696   /* Search the hash table for the requested page. Exit early if it is found. */

   697   if( pCache->apHash ){

   698     u32 h = pgno % pCache->nHash;

   699     for(pPage=pCache->apHash[h]; pPage; pPage=pPage->pNextHash){

   700       if( pPage->pgno==pgno ){

   701         if( pPage->nRef==0 ){

   702           if( 0==(pPage->flags&PGHDR_DIRTY) ){

   703             pcacheRemoveFromLruList(pPage);

   704             pCache->nPinned++;

   705           }

   706           pCache->nRef++;

   707         }

   708         pPage->nRef++;

   709         break;

   710       }

   711     }

   712   }

   713 

   714   if( !pPage && createFlag ){

   715     if( pCache->nHash<=pCache->nPage ){

   716       rc = pcacheResizeHash(pCache, pCache->nHash<256 ? 256 : pCache->nHash*2);

   717     }

   718     if( rc==SQLITE_OK ){

   719       rc = pcacheRecycleOrAlloc(pCache, &pPage);

   720     }

   721     if( rc==SQLITE_OK ){

   722       pPage->pPager = 0;

   723       pPage->flags = 0;

   724       pPage->pDirty = 0;

   725       pPage->pgno = pgno;

   726       pPage->pCache = pCache;

   727       pPage->nRef = 1;

   728       pCache->nRef++;

   729       pCache->nPinned++;

   730       pcacheAddToList(&pCache->pClean, pPage);

   731       pcacheAddToHash(pPage);

   732     }

   733   }

   734 

   735   pcacheExitMutex();

   736 

   737   *ppPage = pPage;

   738   expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );

   739   assert( pPage || !createFlag || rc!=SQLITE_OK );

   740   return rc;

   741 }

   742 

   743 /*

   744 ** Dereference a page.  When the reference count reaches zero,

   745 ** move the page to the LRU list if it is clean.

   746 */

   747 void sqlite3PcacheRelease(PgHdr *p){

   748   assert( p->nRef>0 );

   749   p->nRef--;

   750   if( p->nRef==0 ){

   751     PCache *pCache = p->pCache;

   752     pCache->nRef--;

   753     if( (p->flags&PGHDR_DIRTY)==0 ){

   754       pCache->nPinned--;

   755       pcacheEnterMutex();

   756       if( pcache_g.nCurrentPage>pcache_g.nMaxPage ){

   757         pcacheRemoveFromList(&pCache->pClean, p);

   758         pcacheRemoveFromHash(p);

   759         pcachePageFree(p);

   760       }else{

   761         pcacheAddToLruList(p);

   762       }

   763       pcacheExitMutex();

   764     }else{

   765       /* Move the page to the head of the caches dirty list. */

   766       pcacheRemoveFromList(&pCache->pDirty, p);

   767       pcacheAddToList(&pCache->pDirty, p);

   768     }

   769   }

   770 }

   771 

   772 void sqlite3PcacheRef(PgHdr *p){

   773   assert(p->nRef>0);

   774   p->nRef++;

   775 }

   776 

   777 /*

   778 ** Drop a page from the cache. There must be exactly one reference to the

   779 ** page. This function deletes that reference, so after it returns the

   780 ** page pointed to by p is invalid.

   781 */

   782 void sqlite3PcacheDrop(PgHdr *p){

   783   PCache *pCache;

   784   assert( p->nRef==1 );

   785   assert( 0==(p->flags&PGHDR_DIRTY) );

   786   pCache = p->pCache;

   787   pCache->nRef--;

   788   pCache->nPinned--;

   789   pcacheEnterMutex();

   790   pcacheRemoveFromList(&pCache->pClean, p);

   791   pcacheRemoveFromHash(p);

   792   pcachePageFree(p);

   793   pcacheExitMutex();

   794 }

   795 

   796 /*

   797 ** Make sure the page is marked as dirty.  If it isn't dirty already,

   798 ** make it so.

   799 */

   800 void sqlite3PcacheMakeDirty(PgHdr *p){

   801   PCache *pCache;

   802   p->flags &= ~PGHDR_DONT_WRITE;

   803   if( p->flags & PGHDR_DIRTY ) return;

   804   assert( (p->flags & PGHDR_DIRTY)==0 );

   805   assert( p->nRef>0 );

   806   pCache = p->pCache;

   807   pcacheEnterMutex();

   808   pcacheRemoveFromList(&pCache->pClean, p);

   809   pcacheAddToList(&pCache->pDirty, p);

   810   pcacheExitMutex();

   811   p->flags |= PGHDR_DIRTY;

   812 }

   813 

   814 static void pcacheMakeClean(PgHdr *p){

   815   PCache *pCache = p->pCache;

   816   assert( p->apSave[0]==0 && p->apSave[1]==0 );

   817   assert( p->flags & PGHDR_DIRTY );

   818   pcacheRemoveFromList(&pCache->pDirty, p);

   819   pcacheAddToList(&pCache->pClean, p);

   820   p->flags &= ~PGHDR_DIRTY;

   821   if( p->nRef==0 ){

   822     pcacheAddToLruList(p);

   823     pCache->nPinned--;

   824   }

   825   expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );

   826 }

   827 

   828 /*

   829 ** Make sure the page is marked as clean.  If it isn't clean already,

   830 ** make it so.

   831 */

   832 void sqlite3PcacheMakeClean(PgHdr *p){

   833   if( (p->flags & PGHDR_DIRTY) ){

   834     pcacheEnterMutex();

   835     pcacheMakeClean(p);

   836     pcacheExitMutex();

   837   }

   838 }

   839 

   840 /*

   841 ** Make every page in the cache clean.

   842 */

   843 void sqlite3PcacheCleanAll(PCache *pCache){

   844   PgHdr *p;

   845   pcacheEnterMutex();

   846   while( (p = pCache->pDirty)!=0 ){

   847     assert( p->apSave[0]==0 && p->apSave[1]==0 );

   848     pcacheRemoveFromList(&pCache->pDirty, p);

   849     p->flags &= ~PGHDR_DIRTY;

   850     pcacheAddToList(&pCache->pClean, p);

   851     if( p->nRef==0 ){

   852       pcacheAddToLruList(p);

   853       pCache->nPinned--;

   854     }

   855   }

   856   sqlite3PcacheAssertFlags(pCache, 0, PGHDR_DIRTY);

   857   expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );

   858   pcacheExitMutex();

   859 }

   860 

   861 /*

   862 ** Change the page number of page p to newPgno. If newPgno is 0, then the

   863 ** page object is added to the clean-list and the PGHDR_REUSE_UNLIKELY 

   864 ** flag set.

   865 */

   866 void sqlite3PcacheMove(PgHdr *p, Pgno newPgno){

   867   assert( p->nRef>0 );

   868   pcacheEnterMutex();

   869   pcacheRemoveFromHash(p);

   870   p->pgno = newPgno;

   871   if( newPgno==0 ){

   872     pcacheFree(p->apSave[0]);

   873     pcacheFree(p->apSave[1]);

   874     p->apSave[0] = 0;

   875     p->apSave[1] = 0;

   876     if( (p->flags & PGHDR_DIRTY) ){

   877       pcacheMakeClean(p);

   878     }

   879     p->flags = PGHDR_REUSE_UNLIKELY;

   880   }

   881   pcacheAddToHash(p);

   882   pcacheExitMutex();

   883 }

   884 

   885 /*

   886 ** Remove all content from a page cache

   887 */

   888 static void pcacheClear(PCache *pCache){

   889   PgHdr *p, *pNext;

   890   assert( sqlite3_mutex_held(pcache_g.mutex) );

   891   for(p=pCache->pClean; p; p=pNext){

   892     pNext = p->pNext;

   893     pcacheRemoveFromLruList(p);

   894     pcachePageFree(p);

   895   }

   896   for(p=pCache->pDirty; p; p=pNext){

   897     pNext = p->pNext;

   898     pcachePageFree(p);

   899   }

   900   pCache->pClean = 0;

   901   pCache->pDirty = 0;

   902   pCache->pDirtyTail = 0;

   903   pCache->nPage = 0;

   904   pCache->nPinned = 0;

   905   memset(pCache->apHash, 0, pCache->nHash*sizeof(pCache->apHash[0]));

   906 }

   907 

   908 

   909 /*

   910 ** Drop every cache entry whose page number is greater than "pgno".

   911 */

   912 void sqlite3PcacheTruncate(PCache *pCache, Pgno pgno){

   913   PgHdr *p, *pNext;

   914   PgHdr *pDirty = pCache->pDirty;

   915   pcacheEnterMutex();

   916   for(p=pCache->pClean; p||pDirty; p=pNext){

   917     if( !p ){

   918       p = pDirty;

   919       pDirty = 0;

   920     }

   921     pNext = p->pNext;

   922     if( p->pgno>pgno ){

   923       if( p->nRef==0 ){

   924         pcacheRemoveFromHash(p);

   925         if( p->flags&PGHDR_DIRTY ){

   926           pcacheRemoveFromList(&pCache->pDirty, p);

   927           pCache->nPinned--;

   928         }else{

   929           pcacheRemoveFromList(&pCache->pClean, p);

   930           pcacheRemoveFromLruList(p);

   931         }

   932         pcachePageFree(p);

   933       }else{

   934         /* If there are references to the page, it cannot be freed. In this

   935         ** case, zero the page content instead.

   936         */

   937         memset(p->pData, 0, pCache->szPage);

   938       }

   939     }

   940   }

   941   pcacheExitMutex();

   942 }

   943 

   944 /*

   945 ** If there are currently more than pcache.nMaxPage pages allocated, try

   946 ** to recycle pages to reduce the number allocated to pcache.nMaxPage.

   947 */

   948 static void pcacheEnforceMaxPage(void){

   949   PgHdr *p;

   950   assert( sqlite3_mutex_held(pcache_g.mutex) );

   951   while( pcache_g.nCurrentPage>pcache_g.nMaxPage && (p = pcacheRecyclePage()) ){

   952     pcachePageFree(p);

   953   }

   954 }

   955 

   956 /*

   957 ** Close a cache.

   958 */

   959 void sqlite3PcacheClose(PCache *pCache){

   960   pcacheEnterMutex();

   961 

   962   /* Free all the pages used by this pager and remove them from the LRU list. */

   963   pcacheClear(pCache);

   964   if( pCache->bPurgeable ){

   965     pcache_g.nMaxPage -= pCache->nMax;

   966     pcache_g.nMinPage -= pCache->nMin;

   967     pcacheEnforceMaxPage();

   968   }

   969   sqlite3_free(pCache->apHash);

   970   pcacheExitMutex();

   971 }

   972 

   973 /*

   974 ** Preserve the content of the page.  It is assumed that the content

   975 ** has not been preserved already.

   976 **

   977 ** If idJournal==0 then this is for the overall transaction.

   978 ** If idJournal==1 then this is for the statement journal.

   979 **

   980 ** This routine is used for in-memory databases only.

   981 **

   982 ** Return SQLITE_OK or SQLITE_NOMEM if a memory allocation fails.

   983 */

   984 int sqlite3PcachePreserve(PgHdr *p, int idJournal){

   985   void *x;

   986   int sz;

   987   assert( p->pCache->bPurgeable==0 );

   988   assert( p->apSave[idJournal]==0 );

   989   sz = p->pCache->szPage;

   990   p->apSave[idJournal] = x = sqlite3PageMalloc( sz );

   991   if( x==0 ) return SQLITE_NOMEM;

   992   memcpy(x, p->pData, sz);

   993   return SQLITE_OK;

   994 }

   995 

   996 /*

   997 ** Commit a change previously preserved.

   998 */

   999 void sqlite3PcacheCommit(PCache *pCache, int idJournal){

  1000   PgHdr *p;

  1001   int mask = idJournal==0 ? ~PGHDR_IN_JOURNAL : 0xffffff;

  1002   pcacheEnterMutex();     /* Mutex is required to call pcacheFree() */

  1003   for(p=pCache->pDirty; p; p=p->pNext){

  1004     if( p->apSave[idJournal] ){

  1005       pcacheFree(p->apSave[idJournal]);

  1006       p->apSave[idJournal] = 0;

  1007     }

  1008     p->flags &= mask;

  1009   }

  1010   pcacheExitMutex();

  1011 }

  1012 

  1013 /*

  1014 ** Rollback a change previously preserved.

  1015 */

  1016 void sqlite3PcacheRollback(

  1017   PCache *pCache,                  /* Pager cache */

  1018   int idJournal,                   /* Which copy to rollback to */

  1019   void (*xReiniter)(PgHdr*)        /* Called on each rolled back page */

  1020 ){

  1021   PgHdr *p;

  1022   int sz;

  1023   int mask = idJournal==0 ? ~PGHDR_IN_JOURNAL : 0xffffff;

  1024   pcacheEnterMutex();     /* Mutex is required to call pcacheFree() */

  1025   sz = pCache->szPage;

  1026   for(p=pCache->pDirty; p; p=p->pNext){

  1027     if( p->apSave[idJournal] ){

  1028       memcpy(p->pData, p->apSave[idJournal], sz);

  1029       pcacheFree(p->apSave[idJournal]);

  1030       p->apSave[idJournal] = 0;

  1031       if( xReiniter ){

  1032         xReiniter(p);

  1033       }

  1034     }

  1035     p->flags &= mask;

  1036   }

  1037   pcacheExitMutex();

  1038 }

  1039 

  1040 #ifndef NDEBUG

  1041 /* 

  1042 ** Assert flags settings on all pages.  Debugging only.

  1043 */

  1044 void sqlite3PcacheAssertFlags(PCache *pCache, int trueMask, int falseMask){

  1045   PgHdr *p;

  1046   for(p=pCache->pDirty; p; p=p->pNext){

  1047     assert( (p->flags&trueMask)==trueMask );

  1048     assert( (p->flags&falseMask)==0 );

  1049   }

  1050   for(p=pCache->pClean; p; p=p->pNext){

  1051     assert( (p->flags&trueMask)==trueMask );

  1052     assert( (p->flags&falseMask)==0 );

  1053   }

  1054 }

  1055 #endif

  1056 

  1057 /* 

  1058 ** Discard the contents of the cache.

  1059 */

  1060 int sqlite3PcacheClear(PCache *pCache){

  1061   assert(pCache->nRef==0);

  1062   pcacheEnterMutex();

  1063   pcacheClear(pCache);

  1064   pcacheExitMutex();

  1065   return SQLITE_OK;

  1066 }

  1067 

  1068 /*

  1069 ** Merge two lists of pages connected by pDirty and in pgno order.

  1070 ** Do not both fixing the pPrevDirty pointers.

  1071 */

  1072 static PgHdr *pcacheMergeDirtyList(PgHdr *pA, PgHdr *pB){

  1073   PgHdr result, *pTail;

  1074   pTail = &result;

  1075   while( pA && pB ){

  1076     if( pA->pgno<pB->pgno ){

  1077       pTail->pDirty = pA;

  1078       pTail = pA;

  1079       pA = pA->pDirty;

  1080     }else{

  1081       pTail->pDirty = pB;

  1082       pTail = pB;

  1083       pB = pB->pDirty;

  1084     }

  1085   }

  1086   if( pA ){

  1087     pTail->pDirty = pA;

  1088   }else if( pB ){

  1089     pTail->pDirty = pB;

  1090   }else{

  1091     pTail->pDirty = 0;

  1092   }

  1093   return result.pDirty;

  1094 }

  1095 

  1096 /*

  1097 ** Sort the list of pages in accending order by pgno.  Pages are

  1098 ** connected by pDirty pointers.  The pPrevDirty pointers are

  1099 ** corrupted by this sort.

  1100 */

  1101 #define N_SORT_BUCKET_ALLOC 25

  1102 #define N_SORT_BUCKET       25

  1103 #ifdef SQLITE_TEST

  1104   int sqlite3_pager_n_sort_bucket = 0;

  1105   #undef N_SORT_BUCKET

  1106   #define N_SORT_BUCKET \

  1107    (sqlite3_pager_n_sort_bucket?sqlite3_pager_n_sort_bucket:N_SORT_BUCKET_ALLOC)

  1108 #endif

  1109 static PgHdr *pcacheSortDirtyList(PgHdr *pIn){

  1110   PgHdr *a[N_SORT_BUCKET_ALLOC], *p;

  1111   int i;

  1112   memset(a, 0, sizeof(a));

  1113   while( pIn ){

  1114     p = pIn;

  1115     pIn = p->pDirty;

  1116     p->pDirty = 0;

  1117     for(i=0; i<N_SORT_BUCKET-1; i++){

  1118       if( a[i]==0 ){

  1119         a[i] = p;

  1120         break;

  1121       }else{

  1122         p = pcacheMergeDirtyList(a[i], p);

  1123         a[i] = 0;

  1124       }

  1125     }

  1126     if( i==N_SORT_BUCKET-1 ){

  1127       /* Coverage: To get here, there need to be 2^(N_SORT_BUCKET) 

  1128       ** elements in the input list. This is possible, but impractical.

  1129       ** Testing this line is the point of global variable

  1130       ** sqlite3_pager_n_sort_bucket.

  1131       */

  1132       a[i] = pcacheMergeDirtyList(a[i], p);

  1133     }

  1134   }

  1135   p = a[0];