sl@0: /*
sl@0: ** 2008 August 05
sl@0: **
sl@0: ** The author disclaims copyright to this source code.  In place of
sl@0: ** a legal notice, here is a blessing:
sl@0: **
sl@0: **    May you do good and not evil.
sl@0: **    May you find forgiveness for yourself and forgive others.
sl@0: **    May you share freely, never taking more than you give.
sl@0: **
sl@0: *************************************************************************
sl@0: ** This file implements that page cache.
sl@0: **
sl@0: ** @(#) $Id: pcache.c,v 1.33 2008/09/29 11:49:48 danielk1977 Exp $
sl@0: */
sl@0: #include "sqliteInt.h"
sl@0: 
sl@0: /*
sl@0: ** A complete page cache is an instance of this structure.
sl@0: **
sl@0: ** A cache may only be deleted by its owner and while holding the
sl@0: ** SQLITE_MUTEX_STATUS_LRU mutex.
sl@0: */
sl@0: struct PCache {
sl@0:   /*********************************************************************
sl@0:   ** The first group of elements may be read or written at any time by
sl@0:   ** the cache owner without holding the mutex.  No thread other than the
sl@0:   ** cache owner is permitted to access these elements at any time.
sl@0:   */
sl@0:   PgHdr *pDirty, *pDirtyTail;         /* List of dirty pages in LRU order */
sl@0:   PgHdr *pSynced;                     /* Last synced page in dirty page list */
sl@0:   int nRef;                           /* Number of pinned pages */
sl@0:   int nPinned;                        /* Number of pinned and/or dirty pages */
sl@0:   int nMax;                           /* Configured cache size */
sl@0:   int nMin;                           /* Configured minimum cache size */
sl@0:   /**********************************************************************
sl@0:   ** The next group of elements are fixed when the cache is created and
sl@0:   ** may not be changed afterwards.  These elements can read at any time by
sl@0:   ** the cache owner or by any thread holding the the mutex.  Non-owner
sl@0:   ** threads must hold the mutex when reading these elements to prevent
sl@0:   ** the entire PCache object from being deleted during the read.
sl@0:   */
sl@0:   int szPage;                         /* Size of every page in this cache */
sl@0:   int szExtra;                        /* Size of extra space for each page */
sl@0:   int bPurgeable;                     /* True if pages are on backing store */
sl@0:   int (*xStress)(void*,PgHdr*);       /* Call to try make a page clean */
sl@0:   void *pStress;                      /* Argument to xStress */
sl@0:   /**********************************************************************
sl@0:   ** The final group of elements can only be accessed while holding the
sl@0:   ** mutex.  Both the cache owner and any other thread must hold the mutex
sl@0:   ** to read or write any of these elements.
sl@0:   */
sl@0:   int nPage;                          /* Total number of pages in apHash */
sl@0:   int nHash;                          /* Number of slots in apHash[] */
sl@0:   PgHdr **apHash;                     /* Hash table for fast lookup by pgno */
sl@0:   PgHdr *pClean;                      /* List of clean pages in use */
sl@0: };
sl@0: 
sl@0: /*
sl@0: ** Free slots in the page block allocator
sl@0: */
sl@0: typedef struct PgFreeslot PgFreeslot;
sl@0: struct PgFreeslot {
sl@0:   PgFreeslot *pNext;  /* Next free slot */
sl@0: };
sl@0: 
sl@0: /*
sl@0: ** Global data for the page cache.
sl@0: */
sl@0: static SQLITE_WSD struct PCacheGlobal {
sl@0:   int isInit;                         /* True when initialized */
sl@0:   sqlite3_mutex *mutex;               /* static mutex MUTEX_STATIC_LRU */
sl@0: 
sl@0:   int nMaxPage;                       /* Sum of nMaxPage for purgeable caches */
sl@0:   int nMinPage;                       /* Sum of nMinPage for purgeable caches */
sl@0:   int nCurrentPage;                   /* Number of purgeable pages allocated */
sl@0:   PgHdr *pLruHead, *pLruTail;         /* LRU list of unused clean pgs */
sl@0: 
sl@0:   /* Variables related to SQLITE_CONFIG_PAGECACHE settings. */
sl@0:   int szSlot;                         /* Size of each free slot */
sl@0:   void *pStart, *pEnd;                /* Bounds of pagecache malloc range */
sl@0:   PgFreeslot *pFree;                  /* Free page blocks */
sl@0: } pcache = {0};
sl@0: 
sl@0: /*
sl@0: ** All code in this file should access the global pcache structure via the
sl@0: ** alias "pcache_g". This ensures that the WSD emulation is used when
sl@0: ** compiling for systems that do not support real WSD.
sl@0: */
sl@0: #define pcache_g (GLOBAL(struct PCacheGlobal, pcache))
sl@0: 
sl@0: /*
sl@0: ** All global variables used by this module (all of which are grouped 
sl@0: ** together in global structure "pcache" above) are protected by the static 
sl@0: ** SQLITE_MUTEX_STATIC_LRU mutex. A pointer to this mutex is stored in
sl@0: ** variable "pcache.mutex".
sl@0: **
sl@0: ** Some elements of the PCache and PgHdr structures are protected by the 
sl@0: ** SQLITE_MUTEX_STATUS_LRU mutex and other are not.  The protected
sl@0: ** elements are grouped at the end of the structures and are clearly
sl@0: ** marked.
sl@0: **
sl@0: ** Use the following macros must surround all access (read or write)
sl@0: ** of protected elements.  The mutex is not recursive and may not be
sl@0: ** entered more than once.  The pcacheMutexHeld() macro should only be
sl@0: ** used within an assert() to verify that the mutex is being held.
sl@0: */
sl@0: #define pcacheEnterMutex() sqlite3_mutex_enter(pcache_g.mutex)
sl@0: #define pcacheExitMutex()  sqlite3_mutex_leave(pcache_g.mutex)
sl@0: #define pcacheMutexHeld()  sqlite3_mutex_held(pcache_g.mutex)
sl@0: 
sl@0: /*
sl@0: ** Some of the assert() macros in this code are too expensive to run
sl@0: ** even during normal debugging.  Use them only rarely on long-running
sl@0: ** tests.  Enable the expensive asserts using the
sl@0: ** -DSQLITE_ENABLE_EXPENSIVE_ASSERT=1 compile-time option.
sl@0: */
sl@0: #ifdef SQLITE_ENABLE_EXPENSIVE_ASSERT
sl@0: # define expensive_assert(X)  assert(X)
sl@0: #else
sl@0: # define expensive_assert(X)
sl@0: #endif
sl@0: 
sl@0: /********************************** Linked List Management ********************/
sl@0: 
sl@0: #if !defined(NDEBUG) && defined(SQLITE_ENABLE_EXPENSIVE_ASSERT)
sl@0: /*
sl@0: ** This routine verifies that the number of entries in the hash table
sl@0: ** is pCache->nPage.  This routine is used within assert() statements
sl@0: ** only and is therefore disabled during production builds.
sl@0: */
sl@0: static int pcacheCheckHashCount(PCache *pCache){
sl@0:   int i;
sl@0:   int nPage = 0;
sl@0:   for(i=0; i<pCache->nHash; i++){
sl@0:     PgHdr *p;
sl@0:     for(p=pCache->apHash[i]; p; p=p->pNextHash){
sl@0:       nPage++;
sl@0:     }
sl@0:   }
sl@0:   assert( nPage==pCache->nPage );
sl@0:   return 1;
sl@0: }
sl@0: #endif /* !NDEBUG && SQLITE_ENABLE_EXPENSIVE_ASSERT */
sl@0: 
sl@0: 
sl@0: #if !defined(NDEBUG) && defined(SQLITE_ENABLE_EXPENSIVE_ASSERT)
sl@0: /*
sl@0: ** Based on the current value of PCache.nRef and the contents of the
sl@0: ** PCache.pDirty list, return the expected value of the PCache.nPinned
sl@0: ** counter. This is only used in debugging builds, as follows:
sl@0: **
sl@0: **   expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );
sl@0: */
sl@0: static int pcachePinnedCount(PCache *pCache){
sl@0:   PgHdr *p;
sl@0:   int nPinned = pCache->nRef;
sl@0:   for(p=pCache->pDirty; p; p=p->pNext){
sl@0:     if( p->nRef==0 ){
sl@0:       nPinned++;
sl@0:     }
sl@0:   }
sl@0:   return nPinned;
sl@0: }
sl@0: #endif /* !NDEBUG && SQLITE_ENABLE_EXPENSIVE_ASSERT */
sl@0: 
sl@0: 
sl@0: #if !defined(NDEBUG) && defined(SQLITE_ENABLE_EXPENSIVE_ASSERT)
sl@0: /*
sl@0: ** Check that the pCache->pSynced variable is set correctly. If it
sl@0: ** is not, either fail an assert or return zero. Otherwise, return
sl@0: ** non-zero. This is only used in debugging builds, as follows:
sl@0: **
sl@0: **   expensive_assert( pcacheCheckSynced(pCache) );
sl@0: */
sl@0: static int pcacheCheckSynced(PCache *pCache){
sl@0:   PgHdr *p = pCache->pDirtyTail;
sl@0:   for(p=pCache->pDirtyTail; p!=pCache->pSynced; p=p->pPrev){
sl@0:     assert( p->nRef || (p->flags&PGHDR_NEED_SYNC) );
sl@0:   }
sl@0:   return (p==0 || p->nRef || (p->flags&PGHDR_NEED_SYNC)==0);
sl@0: }
sl@0: #endif /* !NDEBUG && SQLITE_ENABLE_EXPENSIVE_ASSERT */
sl@0: 
sl@0: 
sl@0: 
sl@0: /*
sl@0: ** Remove a page from its hash table (PCache.apHash[]).
sl@0: */
sl@0: static void pcacheRemoveFromHash(PgHdr *pPage){
sl@0:   assert( pcacheMutexHeld() );
sl@0:   if( pPage->pPrevHash ){
sl@0:     pPage->pPrevHash->pNextHash = pPage->pNextHash;
sl@0:   }else{
sl@0:     PCache *pCache = pPage->pCache;
sl@0:     u32 h = pPage->pgno % pCache->nHash;
sl@0:     assert( pCache->apHash[h]==pPage );
sl@0:     pCache->apHash[h] = pPage->pNextHash;
sl@0:   }
sl@0:   if( pPage->pNextHash ){
sl@0:     pPage->pNextHash->pPrevHash = pPage->pPrevHash;
sl@0:   }
sl@0:   pPage->pCache->nPage--;
sl@0:   expensive_assert( pcacheCheckHashCount(pPage->pCache) );
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Insert a page into the hash table
sl@0: **
sl@0: ** The mutex must be held by the caller.
sl@0: */
sl@0: static void pcacheAddToHash(PgHdr *pPage){
sl@0:   PCache *pCache = pPage->pCache;
sl@0:   u32 h = pPage->pgno % pCache->nHash;
sl@0:   assert( pcacheMutexHeld() );
sl@0:   pPage->pNextHash = pCache->apHash[h];
sl@0:   pPage->pPrevHash = 0;
sl@0:   if( pCache->apHash[h] ){
sl@0:     pCache->apHash[h]->pPrevHash = pPage;
sl@0:   }
sl@0:   pCache->apHash[h] = pPage;
sl@0:   pCache->nPage++;
sl@0:   expensive_assert( pcacheCheckHashCount(pCache) );
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Attempt to increase the size the hash table to contain
sl@0: ** at least nHash buckets.
sl@0: */
sl@0: static int pcacheResizeHash(PCache *pCache, int nHash){
sl@0:   PgHdr *p;
sl@0:   PgHdr **pNew;
sl@0:   assert( pcacheMutexHeld() );
sl@0: #ifdef SQLITE_MALLOC_SOFT_LIMIT
sl@0:   if( nHash*sizeof(PgHdr*)>SQLITE_MALLOC_SOFT_LIMIT ){
sl@0:     nHash = SQLITE_MALLOC_SOFT_LIMIT/sizeof(PgHdr *);
sl@0:   }
sl@0: #endif
sl@0:   pcacheExitMutex();
sl@0:   pNew = (PgHdr **)sqlite3Malloc(sizeof(PgHdr*)*nHash);
sl@0:   pcacheEnterMutex();
sl@0:   if( !pNew ){
sl@0:     return SQLITE_NOMEM;
sl@0:   }
sl@0:   memset(pNew, 0, sizeof(PgHdr *)*nHash);
sl@0:   sqlite3_free(pCache->apHash);
sl@0:   pCache->apHash = pNew;
sl@0:   pCache->nHash = nHash;
sl@0:   pCache->nPage = 0;
sl@0:  
sl@0:   for(p=pCache->pClean; p; p=p->pNext){
sl@0:     pcacheAddToHash(p);
sl@0:   }
sl@0:   for(p=pCache->pDirty; p; p=p->pNext){
sl@0:     pcacheAddToHash(p);
sl@0:   }
sl@0:   return SQLITE_OK;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Remove a page from a linked list that is headed by *ppHead.
sl@0: ** *ppHead is either PCache.pClean or PCache.pDirty.
sl@0: */
sl@0: static void pcacheRemoveFromList(PgHdr **ppHead, PgHdr *pPage){
sl@0:   int isDirtyList = (ppHead==&pPage->pCache->pDirty);
sl@0:   assert( ppHead==&pPage->pCache->pClean || ppHead==&pPage->pCache->pDirty );
sl@0:   assert( pcacheMutexHeld() || ppHead!=&pPage->pCache->pClean );
sl@0: 
sl@0:   if( pPage->pPrev ){
sl@0:     pPage->pPrev->pNext = pPage->pNext;
sl@0:   }else{
sl@0:     assert( *ppHead==pPage );
sl@0:     *ppHead = pPage->pNext;
sl@0:   }
sl@0:   if( pPage->pNext ){
sl@0:     pPage->pNext->pPrev = pPage->pPrev;
sl@0:   }
sl@0: 
sl@0:   if( isDirtyList ){
sl@0:     PCache *pCache = pPage->pCache;
sl@0:     assert( pPage->pNext || pCache->pDirtyTail==pPage );
sl@0:     if( !pPage->pNext ){
sl@0:       pCache->pDirtyTail = pPage->pPrev;
sl@0:     }
sl@0:     if( pCache->pSynced==pPage ){
sl@0:       PgHdr *pSynced = pPage->pPrev;
sl@0:       while( pSynced && (pSynced->flags&PGHDR_NEED_SYNC) ){
sl@0:         pSynced = pSynced->pPrev;
sl@0:       }
sl@0:       pCache->pSynced = pSynced;
sl@0:     }
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Add a page from a linked list that is headed by *ppHead.
sl@0: ** *ppHead is either PCache.pClean or PCache.pDirty.
sl@0: */
sl@0: static void pcacheAddToList(PgHdr **ppHead, PgHdr *pPage){
sl@0:   int isDirtyList = (ppHead==&pPage->pCache->pDirty);
sl@0:   assert( ppHead==&pPage->pCache->pClean || ppHead==&pPage->pCache->pDirty );
sl@0: 
sl@0:   if( (*ppHead) ){
sl@0:     (*ppHead)->pPrev = pPage;
sl@0:   }
sl@0:   pPage->pNext = *ppHead;
sl@0:   pPage->pPrev = 0;
sl@0:   *ppHead = pPage;
sl@0: 
sl@0:   if( isDirtyList ){
sl@0:     PCache *pCache = pPage->pCache;
sl@0:     if( !pCache->pDirtyTail ){
sl@0:       assert( pPage->pNext==0 );
sl@0:       pCache->pDirtyTail = pPage;
sl@0:     }
sl@0:     if( !pCache->pSynced && 0==(pPage->flags&PGHDR_NEED_SYNC) ){
sl@0:       pCache->pSynced = pPage;
sl@0:     }
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Remove a page from the global LRU list
sl@0: */
sl@0: static void pcacheRemoveFromLruList(PgHdr *pPage){
sl@0:   assert( sqlite3_mutex_held(pcache_g.mutex) );
sl@0:   assert( (pPage->flags&PGHDR_DIRTY)==0 );
sl@0:   if( pPage->pCache->bPurgeable==0 ) return;
sl@0:   if( pPage->pNextLru ){
sl@0:     assert( pcache_g.pLruTail!=pPage );
sl@0:     pPage->pNextLru->pPrevLru = pPage->pPrevLru;
sl@0:   }else{
sl@0:     assert( pcache_g.pLruTail==pPage );
sl@0:     pcache_g.pLruTail = pPage->pPrevLru;
sl@0:   }
sl@0:   if( pPage->pPrevLru ){
sl@0:     assert( pcache_g.pLruHead!=pPage );
sl@0:     pPage->pPrevLru->pNextLru = pPage->pNextLru;
sl@0:   }else{
sl@0:     assert( pcache_g.pLruHead==pPage );
sl@0:     pcache_g.pLruHead = pPage->pNextLru;
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Add a page to the global LRU list.  The page is normally added
sl@0: ** to the front of the list so that it will be the last page recycled.
sl@0: ** However, if the PGHDR_REUSE_UNLIKELY bit is set, the page is added
sl@0: ** to the end of the LRU list so that it will be the next to be recycled.
sl@0: */
sl@0: static void pcacheAddToLruList(PgHdr *pPage){
sl@0:   assert( sqlite3_mutex_held(pcache_g.mutex) );
sl@0:   assert( (pPage->flags&PGHDR_DIRTY)==0 );
sl@0:   if( pPage->pCache->bPurgeable==0 ) return;
sl@0:   if( pcache_g.pLruTail && (pPage->flags & PGHDR_REUSE_UNLIKELY)!=0 ){
sl@0:     /* If reuse is unlikely.  Put the page at the end of the LRU list
sl@0:     ** where it will be recycled sooner rather than later. 
sl@0:     */
sl@0:     assert( pcache_g.pLruHead );
sl@0:     pPage->pNextLru = 0;
sl@0:     pPage->pPrevLru = pcache_g.pLruTail;
sl@0:     pcache_g.pLruTail->pNextLru = pPage;
sl@0:     pcache_g.pLruTail = pPage;
sl@0:     pPage->flags &= ~PGHDR_REUSE_UNLIKELY;
sl@0:   }else{
sl@0:     /* If reuse is possible. the page goes at the beginning of the LRU
sl@0:     ** list so that it will be the last to be recycled.
sl@0:     */
sl@0:     if( pcache_g.pLruHead ){
sl@0:       pcache_g.pLruHead->pPrevLru = pPage;
sl@0:     }
sl@0:     pPage->pNextLru = pcache_g.pLruHead;
sl@0:     pcache_g.pLruHead = pPage;
sl@0:     pPage->pPrevLru = 0;
sl@0:     if( pcache_g.pLruTail==0 ){
sl@0:       pcache_g.pLruTail = pPage;
sl@0:     }
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*********************************************** Memory Allocation ***********
sl@0: **
sl@0: ** Initialize the page cache memory pool.
sl@0: **
sl@0: ** This must be called at start-time when no page cache lines are
sl@0: ** checked out. This function is not threadsafe.
sl@0: */
sl@0: void sqlite3PCacheBufferSetup(void *pBuf, int sz, int n){
sl@0:   PgFreeslot *p;
sl@0:   sz &= ~7;
sl@0:   pcache_g.szSlot = sz;
sl@0:   pcache_g.pStart = pBuf;
sl@0:   pcache_g.pFree = 0;
sl@0:   while( n-- ){
sl@0:     p = (PgFreeslot*)pBuf;
sl@0:     p->pNext = pcache_g.pFree;
sl@0:     pcache_g.pFree = p;
sl@0:     pBuf = (void*)&((char*)pBuf)[sz];
sl@0:   }
sl@0:   pcache_g.pEnd = pBuf;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Allocate a page cache line.  Look in the page cache memory pool first
sl@0: ** and use an element from it first if available.  If nothing is available
sl@0: ** in the page cache memory pool, go to the general purpose memory allocator.
sl@0: */
sl@0: static void *pcacheMalloc(int sz, PCache *pCache){
sl@0:   assert( sqlite3_mutex_held(pcache_g.mutex) );
sl@0:   if( sz<=pcache_g.szSlot && pcache_g.pFree ){
sl@0:     PgFreeslot *p = pcache_g.pFree;
sl@0:     pcache_g.pFree = p->pNext;
sl@0:     sqlite3StatusSet(SQLITE_STATUS_PAGECACHE_SIZE, sz);
sl@0:     sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_USED, 1);
sl@0:     return (void*)p;
sl@0:   }else{
sl@0:     void *p;
sl@0: 
sl@0:     /* Allocate a new buffer using sqlite3Malloc. Before doing so, exit the
sl@0:     ** global pcache mutex and unlock the pager-cache object pCache. This is 
sl@0:     ** so that if the attempt to allocate a new buffer causes the the 
sl@0:     ** configured soft-heap-limit to be breached, it will be possible to
sl@0:     ** reclaim memory from this pager-cache.
sl@0:     */
sl@0:     pcacheExitMutex();
sl@0:     p = sqlite3Malloc(sz);
sl@0:     pcacheEnterMutex();
sl@0: 
sl@0:     if( p ){
sl@0:       sz = sqlite3MallocSize(p);
sl@0:       sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_OVERFLOW, sz);
sl@0:     }
sl@0:     return p;
sl@0:   }
sl@0: }
sl@0: void *sqlite3PageMalloc(int sz){
sl@0:   void *p;
sl@0:   pcacheEnterMutex();
sl@0:   p = pcacheMalloc(sz, 0);
sl@0:   pcacheExitMutex();
sl@0:   return p;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Release a pager memory allocation
sl@0: */
sl@0: static void pcacheFree(void *p){
sl@0:   assert( sqlite3_mutex_held(pcache_g.mutex) );
sl@0:   if( p==0 ) return;
sl@0:   if( p>=pcache_g.pStart && p<pcache_g.pEnd ){
sl@0:     PgFreeslot *pSlot;
sl@0:     sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_USED, -1);
sl@0:     pSlot = (PgFreeslot*)p;
sl@0:     pSlot->pNext = pcache_g.pFree;
sl@0:     pcache_g.pFree = pSlot;
sl@0:   }else{
sl@0:     int iSize = sqlite3MallocSize(p);
sl@0:     sqlite3StatusAdd(SQLITE_STATUS_PAGECACHE_OVERFLOW, -iSize);
sl@0:     sqlite3_free(p);
sl@0:   }
sl@0: }
sl@0: void sqlite3PageFree(void *p){
sl@0:   pcacheEnterMutex();
sl@0:   pcacheFree(p);
sl@0:   pcacheExitMutex();
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Allocate a new page.
sl@0: */
sl@0: static PgHdr *pcachePageAlloc(PCache *pCache){
sl@0:   PgHdr *p;
sl@0:   int sz = sizeof(*p) + pCache->szPage + pCache->szExtra;
sl@0:   assert( sqlite3_mutex_held(pcache_g.mutex) );
sl@0:   p = pcacheMalloc(sz, pCache);
sl@0:   if( p==0 ) return 0;
sl@0:   memset(p, 0, sizeof(PgHdr));
sl@0:   p->pData = (void*)&p[1];
sl@0:   p->pExtra = (void*)&((char*)p->pData)[pCache->szPage];
sl@0:   if( pCache->bPurgeable ){
sl@0:     pcache_g.nCurrentPage++;
sl@0:   }
sl@0:   return p;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Deallocate a page
sl@0: */
sl@0: static void pcachePageFree(PgHdr *p){
sl@0:   assert( sqlite3_mutex_held(pcache_g.mutex) );
sl@0:   if( p->pCache->bPurgeable ){
sl@0:     pcache_g.nCurrentPage--;
sl@0:   }
sl@0:   pcacheFree(p->apSave[0]);
sl@0:   pcacheFree(p->apSave[1]);
sl@0:   pcacheFree(p);
sl@0: }
sl@0: 
sl@0: #ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
sl@0: /*
sl@0: ** Return the number of bytes that will be returned to the heap when
sl@0: ** the argument is passed to pcachePageFree().
sl@0: */
sl@0: static int pcachePageSize(PgHdr *p){
sl@0:   assert( sqlite3_mutex_held(pcache_g.mutex) );
sl@0:   assert( !pcache_g.pStart );
sl@0:   assert( p->apSave[0]==0 );
sl@0:   assert( p->apSave[1]==0 );
sl@0:   assert( p && p->pCache );
sl@0:   return sqlite3MallocSize(p);
sl@0: }
sl@0: #endif
sl@0: 
sl@0: /*
sl@0: ** Attempt to 'recycle' a page from the global LRU list. Only clean,
sl@0: ** unreferenced pages from purgeable caches are eligible for recycling.
sl@0: **
sl@0: ** This function removes page pcache.pLruTail from the global LRU list,
sl@0: ** and from the hash-table and PCache.pClean list of the owner pcache.
sl@0: ** There should be no other references to the page.
sl@0: **
sl@0: ** A pointer to the recycled page is returned, or NULL if no page is
sl@0: ** eligible for recycling.
sl@0: */
sl@0: static PgHdr *pcacheRecyclePage(void){
sl@0:   PgHdr *p = 0;
sl@0:   assert( sqlite3_mutex_held(pcache_g.mutex) );
sl@0: 
sl@0:   if( (p=pcache_g.pLruTail) ){
sl@0:     assert( (p->flags&PGHDR_DIRTY)==0 );
sl@0:     pcacheRemoveFromLruList(p);
sl@0:     pcacheRemoveFromHash(p);
sl@0:     pcacheRemoveFromList(&p->pCache->pClean, p);
sl@0:   }
sl@0: 
sl@0:   return p;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Obtain space for a page. Try to recycle an old page if the limit on the 
sl@0: ** number of pages has been reached. If the limit has not been reached or
sl@0: ** there are no pages eligible for recycling, allocate a new page.
sl@0: **
sl@0: ** Return a pointer to the new page, or NULL if an OOM condition occurs.
sl@0: */
sl@0: static int pcacheRecycleOrAlloc(PCache *pCache, PgHdr **ppPage){
sl@0:   PgHdr *p = 0;
sl@0: 
sl@0:   int szPage = pCache->szPage;
sl@0:   int szExtra = pCache->szExtra;
sl@0: 
sl@0:   assert( pcache_g.isInit );
sl@0:   assert( sqlite3_mutex_held(pcache_g.mutex) );
sl@0: 
sl@0:   *ppPage = 0;
sl@0: 
sl@0:   /* If we have reached either the global or the local limit for 
sl@0:   ** pinned+dirty pages, and there is at least one dirty page,
sl@0:   ** invoke the xStress callback to cause a page to become clean.
sl@0:   */
sl@0:   expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );
sl@0:   expensive_assert( pcacheCheckSynced(pCache) );
sl@0:   if( pCache->xStress
sl@0:    && pCache->pDirty
sl@0:    && (pCache->nPinned>=(pcache_g.nMaxPage+pCache->nMin-pcache_g.nMinPage)
sl@0:            || pCache->nPinned>=pCache->nMax)
sl@0:   ){
sl@0:     PgHdr *pPg;
sl@0:     assert(pCache->pDirtyTail);
sl@0: 
sl@0:     for(pPg=pCache->pSynced; 
sl@0:         pPg && (pPg->nRef || (pPg->flags&PGHDR_NEED_SYNC)); 
sl@0:         pPg=pPg->pPrev
sl@0:     );
sl@0:     if( !pPg ){
sl@0:       for(pPg=pCache->pDirtyTail; pPg && pPg->nRef; pPg=pPg->pPrev);
sl@0:     }
sl@0:     if( pPg ){
sl@0:       int rc;
sl@0:       pcacheExitMutex();
sl@0:       rc = pCache->xStress(pCache->pStress, pPg);
sl@0:       pcacheEnterMutex();
sl@0:       if( rc!=SQLITE_OK && rc!=SQLITE_BUSY ){
sl@0:         return rc;
sl@0:       }
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   /* If either the local or the global page limit has been reached, 
sl@0:   ** try to recycle a page. 
sl@0:   */
sl@0:   if( pCache->bPurgeable && (pCache->nPage>=pCache->nMax-1 ||
sl@0:                              pcache_g.nCurrentPage>=pcache_g.nMaxPage) ){
sl@0:     p = pcacheRecyclePage();
sl@0:   }
sl@0: 
sl@0:   /* If a page has been recycled but it is the wrong size, free it. */
sl@0:   if( p && (p->pCache->szPage!=szPage || p->pCache->szPage!=szExtra) ){
sl@0:     pcachePageFree(p);
sl@0:     p = 0;
sl@0:   }
sl@0: 
sl@0:   if( !p ){
sl@0:     p = pcachePageAlloc(pCache);
sl@0:   }
sl@0: 
sl@0:   *ppPage = p;
sl@0:   return (p?SQLITE_OK:SQLITE_NOMEM);
sl@0: }
sl@0: 
sl@0: /*************************************************** General Interfaces ******
sl@0: **
sl@0: ** Initialize and shutdown the page cache subsystem. Neither of these 
sl@0: ** functions are threadsafe.
sl@0: */
sl@0: int sqlite3PcacheInitialize(void){
sl@0:   assert( pcache_g.isInit==0 );
sl@0:   memset(&pcache_g, 0, sizeof(pcache));
sl@0:   if( sqlite3GlobalConfig.bCoreMutex ){
sl@0:     /* No need to check the return value of sqlite3_mutex_alloc(). 
sl@0:     ** Allocating a static mutex cannot fail.
sl@0:     */
sl@0:     pcache_g.mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU);
sl@0:   }
sl@0:   pcache_g.isInit = 1;
sl@0:   return SQLITE_OK;
sl@0: }
sl@0: void sqlite3PcacheShutdown(void){
sl@0:   memset(&pcache_g, 0, sizeof(pcache));
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Return the size in bytes of a PCache object.
sl@0: */
sl@0: int sqlite3PcacheSize(void){ return sizeof(PCache); }
sl@0: 
sl@0: /*
sl@0: ** Create a new PCache object.  Storage space to hold the object
sl@0: ** has already been allocated and is passed in as the p pointer.
sl@0: */
sl@0: void sqlite3PcacheOpen(
sl@0:   int szPage,                  /* Size of every page */
sl@0:   int szExtra,                 /* Extra space associated with each page */
sl@0:   int bPurgeable,              /* True if pages are on backing store */
sl@0:   int (*xStress)(void*,PgHdr*),/* Call to try to make pages clean */
sl@0:   void *pStress,               /* Argument to xStress */
sl@0:   PCache *p                    /* Preallocated space for the PCache */
sl@0: ){
sl@0:   assert( pcache_g.isInit );
sl@0:   memset(p, 0, sizeof(PCache));
sl@0:   p->szPage = szPage;
sl@0:   p->szExtra = szExtra;
sl@0:   p->bPurgeable = bPurgeable;
sl@0:   p->xStress = xStress;
sl@0:   p->pStress = pStress;
sl@0:   p->nMax = 100;
sl@0:   p->nMin = 10;
sl@0: 
sl@0:   pcacheEnterMutex();
sl@0:   if( bPurgeable ){
sl@0:     pcache_g.nMaxPage += p->nMax;
sl@0:     pcache_g.nMinPage += p->nMin;
sl@0:   }
sl@0: 
sl@0:   pcacheExitMutex();
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Change the page size for PCache object.  This can only happen
sl@0: ** when the cache is empty.
sl@0: */
sl@0: void sqlite3PcacheSetPageSize(PCache *pCache, int szPage){
sl@0:   assert(pCache->nPage==0);
sl@0:   pCache->szPage = szPage;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Try to obtain a page from the cache.
sl@0: */
sl@0: int sqlite3PcacheFetch(
sl@0:   PCache *pCache,       /* Obtain the page from this cache */
sl@0:   Pgno pgno,            /* Page number to obtain */
sl@0:   int createFlag,       /* If true, create page if it does not exist already */
sl@0:   PgHdr **ppPage        /* Write the page here */
sl@0: ){
sl@0:   int rc = SQLITE_OK;
sl@0:   PgHdr *pPage = 0;
sl@0: 
sl@0:   assert( pcache_g.isInit );
sl@0:   assert( pCache!=0 );
sl@0:   assert( pgno>0 );
sl@0:   expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );
sl@0: 
sl@0:   pcacheEnterMutex();
sl@0: 
sl@0:   /* Search the hash table for the requested page. Exit early if it is found. */
sl@0:   if( pCache->apHash ){
sl@0:     u32 h = pgno % pCache->nHash;
sl@0:     for(pPage=pCache->apHash[h]; pPage; pPage=pPage->pNextHash){
sl@0:       if( pPage->pgno==pgno ){
sl@0:         if( pPage->nRef==0 ){
sl@0:           if( 0==(pPage->flags&PGHDR_DIRTY) ){
sl@0:             pcacheRemoveFromLruList(pPage);
sl@0:             pCache->nPinned++;
sl@0:           }
sl@0:           pCache->nRef++;
sl@0:         }
sl@0:         pPage->nRef++;
sl@0:         break;
sl@0:       }
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   if( !pPage && createFlag ){
sl@0:     if( pCache->nHash<=pCache->nPage ){
sl@0:       rc = pcacheResizeHash(pCache, pCache->nHash<256 ? 256 : pCache->nHash*2);
sl@0:     }
sl@0:     if( rc==SQLITE_OK ){
sl@0:       rc = pcacheRecycleOrAlloc(pCache, &pPage);
sl@0:     }
sl@0:     if( rc==SQLITE_OK ){
sl@0:       pPage->pPager = 0;
sl@0:       pPage->flags = 0;
sl@0:       pPage->pDirty = 0;
sl@0:       pPage->pgno = pgno;
sl@0:       pPage->pCache = pCache;
sl@0:       pPage->nRef = 1;
sl@0:       pCache->nRef++;
sl@0:       pCache->nPinned++;
sl@0:       pcacheAddToList(&pCache->pClean, pPage);
sl@0:       pcacheAddToHash(pPage);
sl@0:     }
sl@0:   }
sl@0: 
sl@0:   pcacheExitMutex();
sl@0: 
sl@0:   *ppPage = pPage;
sl@0:   expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );
sl@0:   assert( pPage || !createFlag || rc!=SQLITE_OK );
sl@0:   return rc;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Dereference a page.  When the reference count reaches zero,
sl@0: ** move the page to the LRU list if it is clean.
sl@0: */
sl@0: void sqlite3PcacheRelease(PgHdr *p){
sl@0:   assert( p->nRef>0 );
sl@0:   p->nRef--;
sl@0:   if( p->nRef==0 ){
sl@0:     PCache *pCache = p->pCache;
sl@0:     pCache->nRef--;
sl@0:     if( (p->flags&PGHDR_DIRTY)==0 ){
sl@0:       pCache->nPinned--;
sl@0:       pcacheEnterMutex();
sl@0:       if( pcache_g.nCurrentPage>pcache_g.nMaxPage ){
sl@0:         pcacheRemoveFromList(&pCache->pClean, p);
sl@0:         pcacheRemoveFromHash(p);
sl@0:         pcachePageFree(p);
sl@0:       }else{
sl@0:         pcacheAddToLruList(p);
sl@0:       }
sl@0:       pcacheExitMutex();
sl@0:     }else{
sl@0:       /* Move the page to the head of the caches dirty list. */
sl@0:       pcacheRemoveFromList(&pCache->pDirty, p);
sl@0:       pcacheAddToList(&pCache->pDirty, p);
sl@0:     }
sl@0:   }
sl@0: }
sl@0: 
sl@0: void sqlite3PcacheRef(PgHdr *p){
sl@0:   assert(p->nRef>0);
sl@0:   p->nRef++;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Drop a page from the cache. There must be exactly one reference to the
sl@0: ** page. This function deletes that reference, so after it returns the
sl@0: ** page pointed to by p is invalid.
sl@0: */
sl@0: void sqlite3PcacheDrop(PgHdr *p){
sl@0:   PCache *pCache;
sl@0:   assert( p->nRef==1 );
sl@0:   assert( 0==(p->flags&PGHDR_DIRTY) );
sl@0:   pCache = p->pCache;
sl@0:   pCache->nRef--;
sl@0:   pCache->nPinned--;
sl@0:   pcacheEnterMutex();
sl@0:   pcacheRemoveFromList(&pCache->pClean, p);
sl@0:   pcacheRemoveFromHash(p);
sl@0:   pcachePageFree(p);
sl@0:   pcacheExitMutex();
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Make sure the page is marked as dirty.  If it isn't dirty already,
sl@0: ** make it so.
sl@0: */
sl@0: void sqlite3PcacheMakeDirty(PgHdr *p){
sl@0:   PCache *pCache;
sl@0:   p->flags &= ~PGHDR_DONT_WRITE;
sl@0:   if( p->flags & PGHDR_DIRTY ) return;
sl@0:   assert( (p->flags & PGHDR_DIRTY)==0 );
sl@0:   assert( p->nRef>0 );
sl@0:   pCache = p->pCache;
sl@0:   pcacheEnterMutex();
sl@0:   pcacheRemoveFromList(&pCache->pClean, p);
sl@0:   pcacheAddToList(&pCache->pDirty, p);
sl@0:   pcacheExitMutex();
sl@0:   p->flags |= PGHDR_DIRTY;
sl@0: }
sl@0: 
sl@0: static void pcacheMakeClean(PgHdr *p){
sl@0:   PCache *pCache = p->pCache;
sl@0:   assert( p->apSave[0]==0 && p->apSave[1]==0 );
sl@0:   assert( p->flags & PGHDR_DIRTY );
sl@0:   pcacheRemoveFromList(&pCache->pDirty, p);
sl@0:   pcacheAddToList(&pCache->pClean, p);
sl@0:   p->flags &= ~PGHDR_DIRTY;
sl@0:   if( p->nRef==0 ){
sl@0:     pcacheAddToLruList(p);
sl@0:     pCache->nPinned--;
sl@0:   }
sl@0:   expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Make sure the page is marked as clean.  If it isn't clean already,
sl@0: ** make it so.
sl@0: */
sl@0: void sqlite3PcacheMakeClean(PgHdr *p){
sl@0:   if( (p->flags & PGHDR_DIRTY) ){
sl@0:     pcacheEnterMutex();
sl@0:     pcacheMakeClean(p);
sl@0:     pcacheExitMutex();
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Make every page in the cache clean.
sl@0: */
sl@0: void sqlite3PcacheCleanAll(PCache *pCache){
sl@0:   PgHdr *p;
sl@0:   pcacheEnterMutex();
sl@0:   while( (p = pCache->pDirty)!=0 ){
sl@0:     assert( p->apSave[0]==0 && p->apSave[1]==0 );
sl@0:     pcacheRemoveFromList(&pCache->pDirty, p);
sl@0:     p->flags &= ~PGHDR_DIRTY;
sl@0:     pcacheAddToList(&pCache->pClean, p);
sl@0:     if( p->nRef==0 ){
sl@0:       pcacheAddToLruList(p);
sl@0:       pCache->nPinned--;
sl@0:     }
sl@0:   }
sl@0:   sqlite3PcacheAssertFlags(pCache, 0, PGHDR_DIRTY);
sl@0:   expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );
sl@0:   pcacheExitMutex();
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Change the page number of page p to newPgno. If newPgno is 0, then the
sl@0: ** page object is added to the clean-list and the PGHDR_REUSE_UNLIKELY 
sl@0: ** flag set.
sl@0: */
sl@0: void sqlite3PcacheMove(PgHdr *p, Pgno newPgno){
sl@0:   assert( p->nRef>0 );
sl@0:   pcacheEnterMutex();
sl@0:   pcacheRemoveFromHash(p);
sl@0:   p->pgno = newPgno;
sl@0:   if( newPgno==0 ){
sl@0:     pcacheFree(p->apSave[0]);
sl@0:     pcacheFree(p->apSave[1]);
sl@0:     p->apSave[0] = 0;
sl@0:     p->apSave[1] = 0;
sl@0:     if( (p->flags & PGHDR_DIRTY) ){
sl@0:       pcacheMakeClean(p);
sl@0:     }
sl@0:     p->flags = PGHDR_REUSE_UNLIKELY;
sl@0:   }
sl@0:   pcacheAddToHash(p);
sl@0:   pcacheExitMutex();
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Remove all content from a page cache
sl@0: */
sl@0: static void pcacheClear(PCache *pCache){
sl@0:   PgHdr *p, *pNext;
sl@0:   assert( sqlite3_mutex_held(pcache_g.mutex) );
sl@0:   for(p=pCache->pClean; p; p=pNext){
sl@0:     pNext = p->pNext;
sl@0:     pcacheRemoveFromLruList(p);
sl@0:     pcachePageFree(p);
sl@0:   }
sl@0:   for(p=pCache->pDirty; p; p=pNext){
sl@0:     pNext = p->pNext;
sl@0:     pcachePageFree(p);
sl@0:   }
sl@0:   pCache->pClean = 0;
sl@0:   pCache->pDirty = 0;
sl@0:   pCache->pDirtyTail = 0;
sl@0:   pCache->nPage = 0;
sl@0:   pCache->nPinned = 0;
sl@0:   memset(pCache->apHash, 0, pCache->nHash*sizeof(pCache->apHash[0]));
sl@0: }
sl@0: 
sl@0: 
sl@0: /*
sl@0: ** Drop every cache entry whose page number is greater than "pgno".
sl@0: */
sl@0: void sqlite3PcacheTruncate(PCache *pCache, Pgno pgno){
sl@0:   PgHdr *p, *pNext;
sl@0:   PgHdr *pDirty = pCache->pDirty;
sl@0:   pcacheEnterMutex();
sl@0:   for(p=pCache->pClean; p||pDirty; p=pNext){
sl@0:     if( !p ){
sl@0:       p = pDirty;
sl@0:       pDirty = 0;
sl@0:     }
sl@0:     pNext = p->pNext;
sl@0:     if( p->pgno>pgno ){
sl@0:       if( p->nRef==0 ){
sl@0:         pcacheRemoveFromHash(p);
sl@0:         if( p->flags&PGHDR_DIRTY ){
sl@0:           pcacheRemoveFromList(&pCache->pDirty, p);
sl@0:           pCache->nPinned--;
sl@0:         }else{
sl@0:           pcacheRemoveFromList(&pCache->pClean, p);
sl@0:           pcacheRemoveFromLruList(p);
sl@0:         }
sl@0:         pcachePageFree(p);
sl@0:       }else{
sl@0:         /* If there are references to the page, it cannot be freed. In this
sl@0:         ** case, zero the page content instead.
sl@0:         */
sl@0:         memset(p->pData, 0, pCache->szPage);
sl@0:       }
sl@0:     }
sl@0:   }
sl@0:   pcacheExitMutex();
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** If there are currently more than pcache.nMaxPage pages allocated, try
sl@0: ** to recycle pages to reduce the number allocated to pcache.nMaxPage.
sl@0: */
sl@0: static void pcacheEnforceMaxPage(void){
sl@0:   PgHdr *p;
sl@0:   assert( sqlite3_mutex_held(pcache_g.mutex) );
sl@0:   while( pcache_g.nCurrentPage>pcache_g.nMaxPage && (p = pcacheRecyclePage()) ){
sl@0:     pcachePageFree(p);
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Close a cache.
sl@0: */
sl@0: void sqlite3PcacheClose(PCache *pCache){
sl@0:   pcacheEnterMutex();
sl@0: 
sl@0:   /* Free all the pages used by this pager and remove them from the LRU list. */
sl@0:   pcacheClear(pCache);
sl@0:   if( pCache->bPurgeable ){
sl@0:     pcache_g.nMaxPage -= pCache->nMax;
sl@0:     pcache_g.nMinPage -= pCache->nMin;
sl@0:     pcacheEnforceMaxPage();
sl@0:   }
sl@0:   sqlite3_free(pCache->apHash);
sl@0:   pcacheExitMutex();
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Preserve the content of the page.  It is assumed that the content
sl@0: ** has not been preserved already.
sl@0: **
sl@0: ** If idJournal==0 then this is for the overall transaction.
sl@0: ** If idJournal==1 then this is for the statement journal.
sl@0: **
sl@0: ** This routine is used for in-memory databases only.
sl@0: **
sl@0: ** Return SQLITE_OK or SQLITE_NOMEM if a memory allocation fails.
sl@0: */
sl@0: int sqlite3PcachePreserve(PgHdr *p, int idJournal){
sl@0:   void *x;
sl@0:   int sz;
sl@0:   assert( p->pCache->bPurgeable==0 );
sl@0:   assert( p->apSave[idJournal]==0 );
sl@0:   sz = p->pCache->szPage;
sl@0:   p->apSave[idJournal] = x = sqlite3PageMalloc( sz );
sl@0:   if( x==0 ) return SQLITE_NOMEM;
sl@0:   memcpy(x, p->pData, sz);
sl@0:   return SQLITE_OK;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Commit a change previously preserved.
sl@0: */
sl@0: void sqlite3PcacheCommit(PCache *pCache, int idJournal){
sl@0:   PgHdr *p;
sl@0:   int mask = idJournal==0 ? ~PGHDR_IN_JOURNAL : 0xffffff;
sl@0:   pcacheEnterMutex();     /* Mutex is required to call pcacheFree() */
sl@0:   for(p=pCache->pDirty; p; p=p->pNext){
sl@0:     if( p->apSave[idJournal] ){
sl@0:       pcacheFree(p->apSave[idJournal]);
sl@0:       p->apSave[idJournal] = 0;
sl@0:     }
sl@0:     p->flags &= mask;
sl@0:   }
sl@0:   pcacheExitMutex();
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Rollback a change previously preserved.
sl@0: */
sl@0: void sqlite3PcacheRollback(
sl@0:   PCache *pCache,                  /* Pager cache */
sl@0:   int idJournal,                   /* Which copy to rollback to */
sl@0:   void (*xReiniter)(PgHdr*)        /* Called on each rolled back page */
sl@0: ){
sl@0:   PgHdr *p;
sl@0:   int sz;
sl@0:   int mask = idJournal==0 ? ~PGHDR_IN_JOURNAL : 0xffffff;
sl@0:   pcacheEnterMutex();     /* Mutex is required to call pcacheFree() */
sl@0:   sz = pCache->szPage;
sl@0:   for(p=pCache->pDirty; p; p=p->pNext){
sl@0:     if( p->apSave[idJournal] ){
sl@0:       memcpy(p->pData, p->apSave[idJournal], sz);
sl@0:       pcacheFree(p->apSave[idJournal]);
sl@0:       p->apSave[idJournal] = 0;
sl@0:       if( xReiniter ){
sl@0:         xReiniter(p);
sl@0:       }
sl@0:     }
sl@0:     p->flags &= mask;
sl@0:   }
sl@0:   pcacheExitMutex();
sl@0: }
sl@0: 
sl@0: #ifndef NDEBUG
sl@0: /* 
sl@0: ** Assert flags settings on all pages.  Debugging only.
sl@0: */
sl@0: void sqlite3PcacheAssertFlags(PCache *pCache, int trueMask, int falseMask){
sl@0:   PgHdr *p;
sl@0:   for(p=pCache->pDirty; p; p=p->pNext){
sl@0:     assert( (p->flags&trueMask)==trueMask );
sl@0:     assert( (p->flags&falseMask)==0 );
sl@0:   }
sl@0:   for(p=pCache->pClean; p; p=p->pNext){
sl@0:     assert( (p->flags&trueMask)==trueMask );
sl@0:     assert( (p->flags&falseMask)==0 );
sl@0:   }
sl@0: }
sl@0: #endif
sl@0: 
sl@0: /* 
sl@0: ** Discard the contents of the cache.
sl@0: */
sl@0: int sqlite3PcacheClear(PCache *pCache){
sl@0:   assert(pCache->nRef==0);
sl@0:   pcacheEnterMutex();
sl@0:   pcacheClear(pCache);
sl@0:   pcacheExitMutex();
sl@0:   return SQLITE_OK;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Merge two lists of pages connected by pDirty and in pgno order.
sl@0: ** Do not both fixing the pPrevDirty pointers.
sl@0: */
sl@0: static PgHdr *pcacheMergeDirtyList(PgHdr *pA, PgHdr *pB){
sl@0:   PgHdr result, *pTail;
sl@0:   pTail = &result;
sl@0:   while( pA && pB ){
sl@0:     if( pA->pgno<pB->pgno ){
sl@0:       pTail->pDirty = pA;
sl@0:       pTail = pA;
sl@0:       pA = pA->pDirty;
sl@0:     }else{
sl@0:       pTail->pDirty = pB;
sl@0:       pTail = pB;
sl@0:       pB = pB->pDirty;
sl@0:     }
sl@0:   }
sl@0:   if( pA ){
sl@0:     pTail->pDirty = pA;
sl@0:   }else if( pB ){
sl@0:     pTail->pDirty = pB;
sl@0:   }else{
sl@0:     pTail->pDirty = 0;
sl@0:   }
sl@0:   return result.pDirty;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Sort the list of pages in accending order by pgno.  Pages are
sl@0: ** connected by pDirty pointers.  The pPrevDirty pointers are
sl@0: ** corrupted by this sort.
sl@0: */
sl@0: #define N_SORT_BUCKET_ALLOC 25
sl@0: #define N_SORT_BUCKET       25
sl@0: #ifdef SQLITE_TEST
sl@0:   int sqlite3_pager_n_sort_bucket = 0;
sl@0:   #undef N_SORT_BUCKET
sl@0:   #define N_SORT_BUCKET \
sl@0:    (sqlite3_pager_n_sort_bucket?sqlite3_pager_n_sort_bucket:N_SORT_BUCKET_ALLOC)
sl@0: #endif
sl@0: static PgHdr *pcacheSortDirtyList(PgHdr *pIn){
sl@0:   PgHdr *a[N_SORT_BUCKET_ALLOC], *p;
sl@0:   int i;
sl@0:   memset(a, 0, sizeof(a));
sl@0:   while( pIn ){
sl@0:     p = pIn;
sl@0:     pIn = p->pDirty;
sl@0:     p->pDirty = 0;
sl@0:     for(i=0; i<N_SORT_BUCKET-1; i++){
sl@0:       if( a[i]==0 ){
sl@0:         a[i] = p;
sl@0:         break;
sl@0:       }else{
sl@0:         p = pcacheMergeDirtyList(a[i], p);
sl@0:         a[i] = 0;
sl@0:       }
sl@0:     }
sl@0:     if( i==N_SORT_BUCKET-1 ){
sl@0:       /* Coverage: To get here, there need to be 2^(N_SORT_BUCKET) 
sl@0:       ** elements in the input list. This is possible, but impractical.
sl@0:       ** Testing this line is the point of global variable
sl@0:       ** sqlite3_pager_n_sort_bucket.
sl@0:       */
sl@0:       a[i] = pcacheMergeDirtyList(a[i], p);
sl@0:     }
sl@0:   }
sl@0:   p = a[0];
sl@0:   for(i=1; i<N_SORT_BUCKET; i++){
sl@0:     p = pcacheMergeDirtyList(p, a[i]);
sl@0:   }
sl@0:   return p;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Return a list of all dirty pages in the cache, sorted by page number.
sl@0: */
sl@0: PgHdr *sqlite3PcacheDirtyList(PCache *pCache){
sl@0:   PgHdr *p;
sl@0:   for(p=pCache->pDirty; p; p=p->pNext){
sl@0:     p->pDirty = p->pNext;
sl@0:   }
sl@0:   return pcacheSortDirtyList(pCache->pDirty);
sl@0: }
sl@0: 
sl@0: /* 
sl@0: ** Return the total number of outstanding page references.
sl@0: */
sl@0: int sqlite3PcacheRefCount(PCache *pCache){
sl@0:   return pCache->nRef;
sl@0: }
sl@0: 
sl@0: int sqlite3PcachePageRefcount(PgHdr *p){
sl@0:   return p->nRef;
sl@0: }
sl@0: 
sl@0: /* 
sl@0: ** Return the total number of pages in the cache.
sl@0: */
sl@0: int sqlite3PcachePagecount(PCache *pCache){
sl@0:   assert( pCache->nPage>=0 );
sl@0:   return pCache->nPage;
sl@0: }
sl@0: 
sl@0: #ifdef SQLITE_CHECK_PAGES
sl@0: /*
sl@0: ** This function is used by the pager.c module to iterate through all 
sl@0: ** pages in the cache. At present, this is only required if the
sl@0: ** SQLITE_CHECK_PAGES macro (used for debugging) is specified.
sl@0: */
sl@0: void sqlite3PcacheIterate(PCache *pCache, void (*xIter)(PgHdr *)){
sl@0:   PgHdr *p;
sl@0:   for(p=pCache->pClean; p; p=p->pNext){
sl@0:     xIter(p);
sl@0:   }
sl@0:   for(p=pCache->pDirty; p; p=p->pNext){
sl@0:     xIter(p);
sl@0:   }
sl@0: }
sl@0: #endif
sl@0: 
sl@0: /* 
sl@0: ** Set flags on all pages in the page cache 
sl@0: */
sl@0: void sqlite3PcacheClearFlags(PCache *pCache, int mask){
sl@0:   PgHdr *p;
sl@0: 
sl@0:   /* Obtain the global mutex before modifying any PgHdr.flags variables 
sl@0:   ** or traversing the LRU list.
sl@0:   */ 
sl@0:   pcacheEnterMutex();
sl@0: 
sl@0:   mask = ~mask;
sl@0:   for(p=pCache->pDirty; p; p=p->pNext){
sl@0:     p->flags &= mask;
sl@0:   }
sl@0:   for(p=pCache->pClean; p; p=p->pNext){
sl@0:     p->flags &= mask;
sl@0:   }
sl@0: 
sl@0:   if( 0==(mask&PGHDR_NEED_SYNC) ){
sl@0:     pCache->pSynced = pCache->pDirtyTail;
sl@0:     assert( !pCache->pSynced || (pCache->pSynced->flags&PGHDR_NEED_SYNC)==0 );
sl@0:   }
sl@0: 
sl@0:   pcacheExitMutex();
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Set the suggested cache-size value.
sl@0: */
sl@0: int sqlite3PcacheGetCachesize(PCache *pCache){
sl@0:   return pCache->nMax;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Set the suggested cache-size value.
sl@0: */
sl@0: void sqlite3PcacheSetCachesize(PCache *pCache, int mxPage){
sl@0:   if( mxPage<10 ){
sl@0:     mxPage = 10;
sl@0:   }
sl@0:   if( pCache->bPurgeable ){
sl@0:     pcacheEnterMutex();
sl@0:     pcache_g.nMaxPage -= pCache->nMax;
sl@0:     pcache_g.nMaxPage += mxPage;
sl@0:     pcacheEnforceMaxPage();
sl@0:     pcacheExitMutex();
sl@0:   }
sl@0:   pCache->nMax = mxPage;
sl@0: }
sl@0: 
sl@0: #ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
sl@0: /*
sl@0: ** This function is called to free superfluous dynamically allocated memory
sl@0: ** held by the pager system. Memory in use by any SQLite pager allocated
sl@0: ** by the current thread may be sqlite3_free()ed.
sl@0: **
sl@0: ** nReq is the number of bytes of memory required. Once this much has
sl@0: ** been released, the function returns. The return value is the total number 
sl@0: ** of bytes of memory released.
sl@0: */
sl@0: int sqlite3PcacheReleaseMemory(int nReq){
sl@0:   int nFree = 0;
sl@0:   if( pcache_g.pStart==0 ){
sl@0:     PgHdr *p;
sl@0:     pcacheEnterMutex();
sl@0:     while( (nReq<0 || nFree<nReq) && (p=pcacheRecyclePage()) ){
sl@0:       nFree += pcachePageSize(p);
sl@0:       pcachePageFree(p);
sl@0:     }
sl@0:     pcacheExitMutex();
sl@0:   }
sl@0:   return nFree;
sl@0: }
sl@0: #endif /* SQLITE_ENABLE_MEMORY_MANAGEMENT */
sl@0: 
sl@0: #ifdef SQLITE_TEST
sl@0: void sqlite3PcacheStats(
sl@0:   int *pnCurrent,
sl@0:   int *pnMax,
sl@0:   int *pnMin,
sl@0:   int *pnRecyclable
sl@0: ){
sl@0:   PgHdr *p;
sl@0:   int nRecyclable = 0;
sl@0:   for(p=pcache_g.pLruHead; p; p=p->pNextLru){
sl@0:     nRecyclable++;
sl@0:   }
sl@0: 
sl@0:   *pnCurrent = pcache_g.nCurrentPage;
sl@0:   *pnMax = pcache_g.nMaxPage;
sl@0:   *pnMin = pcache_g.nMinPage;
sl@0:   *pnRecyclable = nRecyclable;
sl@0: }
sl@0: #endif