** The pager is used to access a database disk file.  It implements
** atomic commit and rollback through the use of a journal file that
** is separate from the database file.  The pager also implements file
** locking to prevent two processes from writing the same database
** file simultaneously, or one process from reading the database while
** another is writing.
**
** @(#) $Id: pager.c,v 1.474 2008/08/22 12:57:09 drh Exp $
*/
#ifndef SQLITE_OMIT_DISKIO
#include "sqliteInt.h"

/*
** Macros for troubleshooting.  Normally turned off
*/
................................................................................
  vfsFlags |=  SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE |
            SQLITE_OPEN_EXCLUSIVE | SQLITE_OPEN_DELETEONCLOSE;
  rc = sqlite3OsOpen(pPager->pVfs, 0, pFile, vfsFlags, 0);
  assert( rc!=SQLITE_OK || pFile->pMethods );
  return rc;
}

static int pagerStress(void *);

/*
** Create a new page cache and put a pointer to the page cache in *ppPager.
** The file to be cached need not exist.  The file is not locked until
** the first call to sqlite3PagerGet() and is only held open until the
** last page is released using sqlite3PagerUnref().
**
................................................................................
#endif

  return rc;
}

/*
** Given a list of pages (connected by the PgHdr.pDirty pointer) write
** every one of those pages out to the database file and mark them all
** as clean.


*/
static int pager_write_pagelist(PgHdr *pList){
  Pager *pPager;
  int rc;

  if( pList==0 ) return SQLITE_OK;
  pPager = pList->pPager;
................................................................................
      PAGERTRACE3("NOSTORE %d page %d\n", PAGERID(pPager), pList->pgno);
    }
#endif
    if( rc ) return rc;
#ifdef SQLITE_CHECK_PAGES
    pList->pageHash = pager_pagehash(pList);
#endif
    makeClean(pList);
    pList = pList->pDirty;
  }

  /* sqlite3PcacheCleanAll(pPager->pPCache); */
  return SQLITE_OK;
}

................................................................................
/*
** This function is called by the pcache layer when it has reached some
** soft memory limit. The argument is a pointer to a purgeable Pager 
** object. This function attempts to make a single dirty page that has no
** outstanding references (if one exists) clean so that it can be recycled 
** by the pcache layer.
*/
static int pagerStress(void *p){
  Pager *pPager = (Pager *)p;
  PgHdr *pPg = sqlite3PcacheDirtyPage(pPager->pPCache);
  int rc = SQLITE_OK;

  if( pPg ){
    assert( pPg->flags&PGHDR_DIRTY );
    if( pPager->errCode==SQLITE_OK ){
      if( pPg->flags&PGHDR_NEED_SYNC ){
        rc = syncJournal(pPager);
        if( rc==SQLITE_OK && pPager->fullSync && 
          !(sqlite3OsDeviceCharacteristics(pPager->fd)&SQLITE_IOCAP_SAFE_APPEND)
        ){
          pPager->nRec = 0;
          rc = writeJournalHdr(pPager);
        }
      }
      if( rc==SQLITE_OK ){

        rc = pager_write_pagelist(pPg);
      }
      if( rc!=SQLITE_OK ){
        pager_error(pPager, rc);
      }
    }else{
      sqlite3PcacheMakeClean(pPg);
    }



  }
  return rc;
}


/*
** Return 1 if there is a hot journal on the given pager.

** The pager is used to access a database disk file.  It implements
** atomic commit and rollback through the use of a journal file that
** is separate from the database file.  The pager also implements file
** locking to prevent two processes from writing the same database
** file simultaneously, or one process from reading the database while
** another is writing.
**
** @(#) $Id: pager.c,v 1.475 2008/08/22 16:22:17 danielk1977 Exp $
*/
#ifndef SQLITE_OMIT_DISKIO
#include "sqliteInt.h"

/*
** Macros for troubleshooting.  Normally turned off
*/
................................................................................
  vfsFlags |=  SQLITE_OPEN_READWRITE | SQLITE_OPEN_CREATE |
            SQLITE_OPEN_EXCLUSIVE | SQLITE_OPEN_DELETEONCLOSE;
  rc = sqlite3OsOpen(pPager->pVfs, 0, pFile, vfsFlags, 0);
  assert( rc!=SQLITE_OK || pFile->pMethods );
  return rc;
}

static int pagerStress(void *,PgHdr *);

/*
** Create a new page cache and put a pointer to the page cache in *ppPager.
** The file to be cached need not exist.  The file is not locked until
** the first call to sqlite3PagerGet() and is only held open until the
** last page is released using sqlite3PagerUnref().
**
................................................................................
#endif

  return rc;
}

/*
** Given a list of pages (connected by the PgHdr.pDirty pointer) write
** every one of those pages out to the database file. No calls are made
** to the page-cache to mark the pages as clean. It is the responsibility
** of the caller to use PcacheCleanAll() or PcacheMakeClean() to mark
** the pages as clean.
*/
static int pager_write_pagelist(PgHdr *pList){
  Pager *pPager;
  int rc;

  if( pList==0 ) return SQLITE_OK;
  pPager = pList->pPager;
................................................................................
      PAGERTRACE3("NOSTORE %d page %d\n", PAGERID(pPager), pList->pgno);
    }
#endif
    if( rc ) return rc;
#ifdef SQLITE_CHECK_PAGES
    pList->pageHash = pager_pagehash(pList);
#endif
    /* makeClean(pList); */
    pList = pList->pDirty;
  }

  /* sqlite3PcacheCleanAll(pPager->pPCache); */
  return SQLITE_OK;
}

................................................................................
/*
** This function is called by the pcache layer when it has reached some
** soft memory limit. The argument is a pointer to a purgeable Pager 
** object. This function attempts to make a single dirty page that has no
** outstanding references (if one exists) clean so that it can be recycled 
** by the pcache layer.
*/
static int pagerStress(void *p, PgHdr *pPg){
  Pager *pPager = (Pager *)p;

  int rc = SQLITE_OK;


  assert( pPg->flags&PGHDR_DIRTY );
  if( pPager->errCode==SQLITE_OK ){
    if( pPg->flags&PGHDR_NEED_SYNC ){
      rc = syncJournal(pPager);
      if( rc==SQLITE_OK && pPager->fullSync && 
        !(sqlite3OsDeviceCharacteristics(pPager->fd)&SQLITE_IOCAP_SAFE_APPEND)
      ){
        pPager->nRec = 0;
        rc = writeJournalHdr(pPager);
      }
    }
    if( rc==SQLITE_OK ){
      pPg->pDirty = 0;
      rc = pager_write_pagelist(pPg);
    }
    if( rc!=SQLITE_OK ){
      pager_error(pPager, rc);
    }


  }

  if( rc==SQLITE_OK ){
    sqlite3PcacheMakeClean(pPg);
  }
  return rc;
}


/*
** Return 1 if there is a hot journal on the given pager.

**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file implements that page cache.
**
** @(#) $Id: pcache.c,v 1.7 2008/08/21 20:21:35 drh Exp $
*/
#include "sqliteInt.h"

/*
** A complete page cache is an instance of this structure.
*/
struct PCache {
................................................................................
  int szExtra;                        /* Size of extra space for each page */
  int nHash;                          /* Number of slots in apHash[] */
  int nPage;                          /* Total number of pages in apHash */
  int nMax;                           /* Configured cache size */
  PgHdr **apHash;                     /* Hash table for fast lookup by pgno */
  int bPurgeable;                     /* True if pages are on backing store */
  void (*xDestroy)(PgHdr*);           /* Called when refcnt goes 1->0 */
  int (*xStress)(void*);              /* Call to try to make pages clean */
  void *pStress;                      /* Argument to xStress */
  PgHdr *pClean;                      /* List of clean pages in use */
  PgHdr *pDirty;                      /* List of dirty pages */
  int nRef;                           /* Number of outstanding page refs */

  int iInUseMM;
  int iInUseDB;
................................................................................
** by the pcache.mxPage and pcache.mxPagePurgeable variables. If
** mxPage is non-zero, then the system tries to limit the number of
** cached pages stored to mxPage. In this case mxPagePurgeable is not 
** used.
**
** If mxPage is zero, then the system tries to limit the number of
** pages held by purgable caches to mxPagePurgeable.







*/
static struct PCacheGlobal {
  int isInit;                         /* True when initialized */
  sqlite3_mutex *mutex_mem2;          /* static mutex MUTEX_STATIC_MEM2 */
  sqlite3_mutex *mutex_lru;           /* static mutex MUTEX_STATIC_LRU */
  PCache *pAll;                       /* list of all page caches */
  int nPage;                          /* Number of pages */
  int nPurgeable;                     /* Number of pages in purgable caches */
  int mxPage;                         /* Globally configured page maximum */
  int mxPagePurgeable;                /* Purgeable page maximum */
  PgHdr *pLruHead, *pLruTail;         /* Global LRU list of unused pages */



  int szSlot;                         /* Size of each free slot */
  void *pStart, *pEnd;                /* Bounds of pagecache malloc range */
  PgFreeslot *pFree;                  /* Free page blocks */
} pcache = {0};

/*
** All global variables used by this module (most of which are grouped 
** together in global structure "pcache" above) except the list of all
** pager-caches starting with pcache.pAll, are protected by the static 
** SQLITE_MUTEX_STATIC_LRU mutex. A pointer to this mutex is stored in
** variable "pcache.mutex_lru".
**
** The list of all pager-caches (PCache structures) headed by pcache.pAll 
** is protected by SQLITE_MUTEX_STATIC_MEM2.
**
** Access to the contents of the individual PCache structures is not 
** protected. It is the job of the caller to ensure that these structures
** are accessed in a thread-safe manner. However, this module provides the
** functions sqlite3PcacheLock() and sqlite3PcacheUnlock() that may be used
** by the caller to increment/decrement a lock-count on an individual 
** pager-cache object. This module guarantees that the xStress() callback
** will not be invoked on a pager-cache with a non-zero lock-count except
** from within a call to sqlite3PcacheFetch() on the same pager. A call
** to sqlite3PcacheLock() may block if such an xStress() call is currently 
** underway.
**
** Before the xStress callback of a pager-cache (PCache) is invoked, the
** SQLITE_MUTEX_STATIC_MEM2 mutex is obtained and the SQLITE_MUTEX_STATIC_LRU 
** mutex released (in that order) before making the call.
**
** Deadlock within the module is avoided by never blocking on the MEM2 
** mutex while the LRU mutex is held.
*/

#define pcacheEnterGlobal() sqlite3_mutex_enter(pcache.mutex_lru)
#define pcacheExitGlobal()  sqlite3_mutex_leave(pcache.mutex_lru)
................................................................................

/*
** Remove a page from the global LRU list
*/
static void pcacheRemoveFromLruList(PgHdr *pPage){
  assert( sqlite3_mutex_held(pcache.mutex_lru) );
  if( pPage->pCache->bPurgeable==0 ) return;





  if( pPage->pNextLru ){
    pPage->pNextLru->pPrevLru = pPage->pPrevLru;
  }else{
    assert( pcache.pLruTail==pPage );
    pcache.pLruTail = pPage->pPrevLru;
  }
  if( pPage->pPrevLru ){
................................................................................
    */
    assert( pcache.pLruHead );
    pPage->pNextLru = 0;
    pPage->pPrevLru = pcache.pLruTail;
    pcache.pLruTail->pNextLru = pPage;
    pcache.pLruTail = pPage;
    pPage->flags &= ~PGHDR_REUSE_UNLIKELY;



  }else{
    /* If reuse is possible. the page goes at the beginning of the LRU
    ** list so that it will be the last to be recycled.
    */
    if( pcache.pLruHead ){
      pcache.pLruHead->pPrevLru = pPage;
    }
    pPage->pNextLru = pcache.pLruHead;
    pcache.pLruHead = pPage;
    pPage->pPrevLru = 0;
    if( pcache.pLruTail==0 ){
      pcache.pLruTail = pPage;



    }
  }
}

/*********************************************** Memory Allocation ***********
**
** Initialize the page cache memory pool.
................................................................................
  assert( p->apSave[0]==0 );
  assert( p->apSave[1]==0 );
  assert( p && p->pCache );
  return sqlite3MallocSize(p);
}

static PgHdr *pcacheRecycle(PCache *pCache){
  PCache *pCsr;
  PgHdr *p = 0;

  assert( pcache.isInit );
  assert( sqlite3_mutex_held(pcache.mutex_lru) );






  if( !pcache.pLruTail && SQLITE_OK==sqlite3_mutex_try(pcache.mutex_mem2) ){



    /* Invoke xStress() callbacks until the LRU list contains at least one
    ** page that can be reused or until the xStress() callback of all
    ** caches has been invoked.









    */
    for(pCsr=pcache.pAll; pCsr&&!pcache.pLruTail; pCsr=pCsr->pNextAll){
      assert( pCsr->iInUseMM==0 );

      pCsr->iInUseMM = 1;
      if( pCsr->xStress && (pCsr->iInUseDB==0 || pCache==pCsr) ){
        pcacheExitGlobal();
        pCsr->xStress(pCsr->pStress);
        pcacheEnterGlobal();
      }


      pCsr->iInUseMM = 0;


    }




    sqlite3_mutex_leave(pcache.mutex_mem2);
  }

  p = pcache.pLruTail;




  if( p ){
    pcacheRemoveFromLruList(p);
    pcacheRemoveFromHash(p);
    pcacheRemoveFromList(&p->pCache->pClean, p);

    /* If the always-rollback flag is set on the page being recycled, set 
................................................................................
** has already been allocated and is passed in as the p pointer.
*/
void sqlite3PcacheOpen(
  int szPage,                  /* Size of every page */
  int szExtra,                 /* Extra space associated with each page */
  int bPurgeable,              /* True if pages are on backing store */
  void (*xDestroy)(PgHdr*),    /* Called to destroy a page */
  int (*xStress)(void*),       /* Call to try to make pages clean */
  void *pStress,               /* Argument to xStress */
  PCache *p                    /* Preallocated space for the PCache */
){
  assert( pcache.isInit );
  memset(p, 0, sizeof(PCache));
  p->szPage = szPage;
  p->szExtra = szExtra;
................................................................................
  if( bPurgeable ){
    pcacheEnterGlobal();
    pcache.mxPagePurgeable += p->nMax;
    pcacheExitGlobal();
  }

  /* Add the new pager-cache to the list of caches starting at pcache.pAll */
  assert( sqlite3_mutex_notheld(pcache.mutex_lru) );
  sqlite3_mutex_enter(pcache.mutex_mem2);
  p->pNextAll = pcache.pAll;
  if( pcache.pAll ){
    pcache.pAll->pPrevAll = p;
  }
  p->pPrevAll = 0;
  pcache.pAll = p;
  sqlite3_mutex_leave(pcache.mutex_mem2);
}

/*
** Change the page size for PCache object.  This can only happen
** when the cache is empty.
*/
void sqlite3PcacheSetPageSize(PCache *pCache, int szPage){
................................................................................
  assert( pCache->iInUseDB || pCache->iInUseMM );

  /* Search the hash table for the requested page. Exit early if it is found. */
  if( pCache->apHash ){
    u32 h = pgno % pCache->nHash;
    for(pPage=pCache->apHash[h]; pPage; pPage=pPage->pNextHash){
      if( pPage->pgno==pgno ){
        if( pPage->nRef==0 && (pPage->flags & PGHDR_DIRTY)==0 ){
          pcacheEnterGlobal();
          pcacheRemoveFromLruList(pPage);
          pcacheExitGlobal();
        }
        pcacheRef(pPage, 1);
        *ppPage = pPage;
        return SQLITE_OK;
................................................................................
  assert( p->nRef>0 );
  assert( p->pCache->iInUseDB || p->pCache->iInUseMM );
  pcacheRef(p, -1);
  if( p->nRef!=0 ) return;
  if( p->pCache->xDestroy ){
    p->pCache->xDestroy(p);
  }

  if( (p->flags & PGHDR_DIRTY)!=0 ) return;

  pcacheEnterGlobal();
  pcacheAddToLruList(p);
  pcacheExitGlobal();
}

void sqlite3PcacheRef(PgHdr *p){
  assert(p->nRef>=0);
................................................................................
*/
void sqlite3PcacheMakeClean(PgHdr *p){
  PCache *pCache;
  assert( p->pCache->iInUseDB || p->pCache->iInUseMM );
  if( (p->flags & PGHDR_DIRTY)==0 ) return;
  assert( p->apSave[0]==0 && p->apSave[1]==0 );
  assert( p->flags & PGHDR_DIRTY );
  /* assert( p->nRef>0 ); */
  pCache = p->pCache;
  pcacheRemoveFromList(&pCache->pDirty, p);
  pcacheAddToList(&pCache->pClean, p);
  p->flags &= ~PGHDR_DIRTY;
  if( p->nRef==0 ){
    pcacheEnterGlobal();
    pcacheAddToLruList(p);
    pcacheExitGlobal();
  }
}

/*
** Make every page in the cache clean.
*/
void sqlite3PcacheCleanAll(PCache *pCache){
  PgHdr *p;
  assert( pCache->iInUseDB );

  while( (p = pCache->pDirty)!=0 ){
    assert( p->apSave[0]==0 && p->apSave[1]==0 );
    pcacheRemoveFromList(&pCache->pDirty, p);
    pcacheAddToList(&pCache->pClean, p);
    p->flags &= ~PGHDR_DIRTY;
    if( p->nRef==0 ){

      pcacheEnterGlobal();
      pcacheAddToLruList(p);
      pcacheExitGlobal();
    }
  }
}

/*
** Change the page number of page p to newPgno. If newPgno is 0, then the
** page object is added to the clean-list and the PGHDR_REUSE_UNLIKELY 
** flag set.
*/
................................................................................
  for(p=pCache->pClean; p; p=pNext){
    pNext = p->pNext;
    pcacheRemoveFromLruList(p);
    pcachePageFree(p);
  }
  for(p=pCache->pDirty; p; p=pNext){
    pNext = p->pNext;

    pcachePageFree(p);
  }
  pCache->pClean = 0;
  pCache->pDirty = 0;
  pCache->nPage = 0;
  memset(pCache->apHash, 0, pCache->nHash*sizeof(pCache->apHash[0]));
}
................................................................................
    pNext = p->pNext;
    if( p->pgno>pgno ){
      if( p->nRef==0 ){
        pcacheRemoveFromHash(p);
        if( p->flags&PGHDR_DIRTY ){
          pcacheRemoveFromList(&pCache->pDirty, p);
        }else{
          pcacheRemoveFromLruList(p);
          pcacheRemoveFromList(&pCache->pClean, p);
        }

        pcachePageFree(p);
      }else{
        /* If there are references to the page, it cannot be freed. In this
        ** case, zero the page content instead.
        */
        memset(p->pData, 0, pCache->szPage);
      }
................................................................................


/*
** Close a cache.
*/
void sqlite3PcacheClose(PCache *pCache){
  assert( pCache->iInUseDB==1 );


  /* Free all the pages used by this pager and remove them from the LRU
  ** list. This requires the protection of the MUTEX_STATIC_LRU mutex.
  */
  pcacheEnterGlobal();
  pcacheClear(pCache);
  if( pCache->bPurgeable ){
    pcache.mxPagePurgeable -= pCache->nMax;
  }
  sqlite3_free(pCache->apHash);
  pcacheExitGlobal();

  /* Now remove the pager-cache structure itself from the list of
  ** all such structures headed by pcache.pAll. This required the
  ** MUTEX_STATIC_MEM2 mutex.
  */
  assert( sqlite3_mutex_notheld(pcache.mutex_lru) );
  sqlite3_mutex_enter(pcache.mutex_mem2);
  assert(pCache==pcache.pAll || pCache->pPrevAll);
  assert(pCache->pNextAll==0 || pCache->pNextAll->pPrevAll==pCache);
  assert(pCache->pPrevAll==0 || pCache->pPrevAll->pNextAll==pCache);
  if( pCache->pPrevAll ){
    pCache->pPrevAll->pNextAll = pCache->pNextAll;
  }else{
    pcache.pAll = pCache->pNextAll;
  }
  if( pCache->pNextAll ){
    pCache->pNextAll->pPrevAll = pCache->pPrevAll;
  }
  sqlite3_mutex_leave(pcache.mutex_mem2);

}

/*
** Preserve the content of the page, if it has not been preserved
** already.  If idJournal==0 then this is for the overall transaction.
** If idJournal==1 then this is for the statement journal.
**
................................................................................
  assert( pCache->iInUseDB );
  for(p=pCache->pDirty; p; p=p->pNext){
    p->pDirty = p->pNext;
  }
  return pcacheSortDirtyList(pCache->pDirty);
}

/*
** This function searches cache pCache for a dirty page for which the
** reference count is zero. If such a page can be found, the PgHdr.pDirty
** pointer is set to 0 and a pointer to the page is returned. If no
** such page is found, 0 is returned.
**
** This is used by the pager module to implement the xStress callback.
*/
PgHdr *sqlite3PcacheDirtyPage(PCache *pCache){
  PgHdr *p = 0;
#if 1
  PgHdr *pIter;
  Pgno min_pgno;
  assert( pCache->iInUseMM );
  for(pIter=pCache->pDirty; pIter; pIter=pIter->pNext){
    if( pIter->nRef==0 && (p==0 || pIter->pgno<min_pgno) ){
      p = pIter;
      min_pgno = pIter->pgno;
    }
  }
#else
  assert( pCache->iInUseMM );
  for(p=pCache->pDirty; p && p->nRef; p=p->pNext);
#endif
  assert( pCache->iInUseMM );
  if( p ){
    p->pDirty = 0;
  }
  return p;
}

/* 
** Return the total number of outstanding page references.
*/
int sqlite3PcacheRefCount(PCache *pCache){
  return pCache->nRef;
}

................................................................................
#endif

/* 
** Set flags on all pages in the page cache 
*/
void sqlite3PcacheSetFlags(PCache *pCache, int andMask, int orMask){
  PgHdr *p;


  assert( pCache->iInUseDB || pCache->iInUseMM );












  for(p=pCache->pDirty; p; p=p->pNext){
    p->flags = (p->flags&andMask)|orMask;
  }
  for(p=pCache->pClean; p; p=p->pNext){
    p->flags = (p->flags&andMask)|orMask;
  }









}

/*
** Set the suggested cache-size value.
*/
int sqlite3PcacheGetCachesize(PCache *pCache){
  return pCache->nMax;

**    May you do good and not evil.
**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file implements that page cache.
**
** @(#) $Id: pcache.c,v 1.8 2008/08/22 16:22:17 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** A complete page cache is an instance of this structure.
*/
struct PCache {
................................................................................
  int szExtra;                        /* Size of extra space for each page */
  int nHash;                          /* Number of slots in apHash[] */
  int nPage;                          /* Total number of pages in apHash */
  int nMax;                           /* Configured cache size */
  PgHdr **apHash;                     /* Hash table for fast lookup by pgno */
  int bPurgeable;                     /* True if pages are on backing store */
  void (*xDestroy)(PgHdr*);           /* Called when refcnt goes 1->0 */
  int (*xStress)(void*,PgHdr*);       /* Call to try make a page clean */
  void *pStress;                      /* Argument to xStress */
  PgHdr *pClean;                      /* List of clean pages in use */
  PgHdr *pDirty;                      /* List of dirty pages */
  int nRef;                           /* Number of outstanding page refs */

  int iInUseMM;
  int iInUseDB;
................................................................................
** by the pcache.mxPage and pcache.mxPagePurgeable variables. If
** mxPage is non-zero, then the system tries to limit the number of
** cached pages stored to mxPage. In this case mxPagePurgeable is not 
** used.
**
** If mxPage is zero, then the system tries to limit the number of
** pages held by purgable caches to mxPagePurgeable.
**
** The doubly-linked list that runs between pcache.pLruHead and 
** pcache.pLruTail contains all pages in the system with a zero 
** reference count. The pcache.pLruSynced variable points to the last
** (closest to pcache.pLruTail) entry in this list that does not have
** the PGHDR_NEED_SYNC flag set. This is the page that the pcacheRecycle()
** function will try to recycle.
*/
static struct PCacheGlobal {
  int isInit;                         /* True when initialized */
  sqlite3_mutex *mutex_mem2;          /* static mutex MUTEX_STATIC_MEM2 */
  sqlite3_mutex *mutex_lru;           /* static mutex MUTEX_STATIC_LRU */
  PCache *pAll;                       /* list of all page caches */
  int nPage;                          /* Number of pages */
  int nPurgeable;                     /* Number of pages in purgable caches */
  int mxPage;                         /* Globally configured page maximum */
  int mxPagePurgeable;                /* Purgeable page maximum */
  PgHdr *pLruHead, *pLruTail;         /* Global LRU list of unused pages */
  PgHdr *pLruSynced;                  /* Last synced entry in LRU list  */

  /* Variables related to SQLITE_CONFIG_PAGECACHE settings. */
  int szSlot;                         /* Size of each free slot */
  void *pStart, *pEnd;                /* Bounds of pagecache malloc range */
  PgFreeslot *pFree;                  /* Free page blocks */
} pcache = {0};

/*
** All global variables used by this module (most of which are grouped 
** together in global structure "pcache" above) except the list of all
** pager-caches starting with pcache.pAll, are protected by the static 
** SQLITE_MUTEX_STATIC_LRU mutex. A pointer to this mutex is stored in
** variable "pcache.mutex_lru".
**



** Access to the contents of the individual PCache structures is not 
** protected. It is the job of the caller to ensure that these structures
** are accessed in a thread-safe manner. However, this module provides the
** functions sqlite3PcacheLock() and sqlite3PcacheUnlock() that may be used
** by the caller to increment/decrement a lock-count on an individual 
** pager-cache object. This module guarantees that the xStress() callback
** will not be invoked on a pager-cache with a non-zero lock-count except
** from within a call to sqlite3PcacheFetch() on the same pager. A call
** to sqlite3PcacheLock() may block if such an xStress() call is currently 
** underway.
**
** Before the xStress callback of a pager-cache (PCache) is invoked, the
** SQLITE_MUTEX_STATIC_MEM2 mutex is obtained.

**
** Deadlock within the module is avoided by never blocking on the MEM2 
** mutex while the LRU mutex is held.
*/

#define pcacheEnterGlobal() sqlite3_mutex_enter(pcache.mutex_lru)
#define pcacheExitGlobal()  sqlite3_mutex_leave(pcache.mutex_lru)
................................................................................

/*
** Remove a page from the global LRU list
*/
static void pcacheRemoveFromLruList(PgHdr *pPage){
  assert( sqlite3_mutex_held(pcache.mutex_lru) );
  if( pPage->pCache->bPurgeable==0 ) return;
  if( pPage==pcache.pLruSynced ){
    PgHdr *p;
    for(p=pPage->pPrevLru; p && (p->flags&PGHDR_NEED_SYNC); p=p->pPrevLru);
    pcache.pLruSynced = p;
  }
  if( pPage->pNextLru ){
    pPage->pNextLru->pPrevLru = pPage->pPrevLru;
  }else{
    assert( pcache.pLruTail==pPage );
    pcache.pLruTail = pPage->pPrevLru;
  }
  if( pPage->pPrevLru ){
................................................................................
    */
    assert( pcache.pLruHead );
    pPage->pNextLru = 0;
    pPage->pPrevLru = pcache.pLruTail;
    pcache.pLruTail->pNextLru = pPage;
    pcache.pLruTail = pPage;
    pPage->flags &= ~PGHDR_REUSE_UNLIKELY;
    if( 0==(pPage->flags&PGHDR_NEED_SYNC) ){
      pcache.pLruSynced = pPage;
    }
  }else{
    /* If reuse is possible. the page goes at the beginning of the LRU
    ** list so that it will be the last to be recycled.
    */
    if( pcache.pLruHead ){
      pcache.pLruHead->pPrevLru = pPage;
    }
    pPage->pNextLru = pcache.pLruHead;
    pcache.pLruHead = pPage;
    pPage->pPrevLru = 0;
    if( pcache.pLruTail==0 ){
      pcache.pLruTail = pPage;
    }
    if( pcache.pLruSynced==0 && 0==(pPage->flags&PGHDR_NEED_SYNC) ){
      pcache.pLruSynced = pPage;
    }
  }
}

/*********************************************** Memory Allocation ***********
**
** Initialize the page cache memory pool.
................................................................................
  assert( p->apSave[0]==0 );
  assert( p->apSave[1]==0 );
  assert( p && p->pCache );
  return sqlite3MallocSize(p);
}

static PgHdr *pcacheRecycle(PCache *pCache){

  PgHdr *p = 0;

  assert( pcache.isInit );
  assert( sqlite3_mutex_held(pcache.mutex_lru) );

  p = pcache.pLruSynced;
  if( !p ){
    p = pcache.pLruTail;
  }
  if( p && (p->flags&PGHDR_DIRTY) ){
    if( SQLITE_OK==sqlite3_mutex_try(pcache.mutex_mem2) ){
      int iInUseDB;
      PCache *pC = p->pCache;




      if( pCache==pC ){
        /* If trying to recycle a page from pCache, then set the iInUseDb
        ** flag to zero. This is done so that the sqlite3PcacheSetFlags()
        ** can tell that the LRU mutex is already held.
        **
        ** It is quite safe to modify the iInUseDB variable, because we 
        ** know no other thread will attempt to use pCache (because this
        ** call is being made from within a call to sqlite3PcacheFetch()
        ** on pCache). 
        */

        assert( pCache->iInUseDB );
        iInUseDB = pCache->iInUseDB;
        pCache->iInUseDB = 0;




      }

      assert( pC->iInUseMM==0 );
      pC->iInUseMM = 1;
      if( pC->xStress && pC->iInUseDB==0 ){
        pC->xStress(pC->pStress, p);
      }
      if( pCache==pC ){
        pCache->iInUseDB = iInUseDB;
      }
      pC->iInUseMM = 0;
      sqlite3_mutex_leave(pcache.mutex_mem2);
    }
  }

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

  if( p ){
    pcacheRemoveFromLruList(p);
    pcacheRemoveFromHash(p);
    pcacheRemoveFromList(&p->pCache->pClean, p);

    /* If the always-rollback flag is set on the page being recycled, set 
................................................................................
** has already been allocated and is passed in as the p pointer.
*/
void sqlite3PcacheOpen(
  int szPage,                  /* Size of every page */
  int szExtra,                 /* Extra space associated with each page */
  int bPurgeable,              /* True if pages are on backing store */
  void (*xDestroy)(PgHdr*),    /* Called to destroy a page */
  int (*xStress)(void*,PgHdr*),/* Call to try to make pages clean */
  void *pStress,               /* Argument to xStress */
  PCache *p                    /* Preallocated space for the PCache */
){
  assert( pcache.isInit );
  memset(p, 0, sizeof(PCache));
  p->szPage = szPage;
  p->szExtra = szExtra;
................................................................................
  if( bPurgeable ){
    pcacheEnterGlobal();
    pcache.mxPagePurgeable += p->nMax;
    pcacheExitGlobal();
  }

  /* Add the new pager-cache to the list of caches starting at pcache.pAll */
  pcacheEnterGlobal();

  p->pNextAll = pcache.pAll;
  if( pcache.pAll ){
    pcache.pAll->pPrevAll = p;
  }
  p->pPrevAll = 0;
  pcache.pAll = p;
  pcacheExitGlobal();
}

/*
** Change the page size for PCache object.  This can only happen
** when the cache is empty.
*/
void sqlite3PcacheSetPageSize(PCache *pCache, int szPage){
................................................................................
  assert( pCache->iInUseDB || pCache->iInUseMM );

  /* Search the hash table for the requested page. Exit early if it is found. */
  if( pCache->apHash ){
    u32 h = pgno % pCache->nHash;
    for(pPage=pCache->apHash[h]; pPage; pPage=pPage->pNextHash){
      if( pPage->pgno==pgno ){
        if( pPage->nRef==0 /* && (pPage->flags & PGHDR_DIRTY)==0 */ ){
          pcacheEnterGlobal();
          pcacheRemoveFromLruList(pPage);
          pcacheExitGlobal();
        }
        pcacheRef(pPage, 1);
        *ppPage = pPage;
        return SQLITE_OK;
................................................................................
  assert( p->nRef>0 );
  assert( p->pCache->iInUseDB || p->pCache->iInUseMM );
  pcacheRef(p, -1);
  if( p->nRef!=0 ) return;
  if( p->pCache->xDestroy ){
    p->pCache->xDestroy(p);
  }
#if 0
  if( (p->flags & PGHDR_DIRTY)!=0 ) return;
#endif
  pcacheEnterGlobal();
  pcacheAddToLruList(p);
  pcacheExitGlobal();
}

void sqlite3PcacheRef(PgHdr *p){
  assert(p->nRef>=0);
................................................................................
*/
void sqlite3PcacheMakeClean(PgHdr *p){
  PCache *pCache;
  assert( p->pCache->iInUseDB || p->pCache->iInUseMM );
  if( (p->flags & PGHDR_DIRTY)==0 ) return;
  assert( p->apSave[0]==0 && p->apSave[1]==0 );
  assert( p->flags & PGHDR_DIRTY );
  assert( p->nRef>0 || sqlite3_mutex_held(pcache.mutex_lru) );
  pCache = p->pCache;
  pcacheRemoveFromList(&pCache->pDirty, p);
  pcacheAddToList(&pCache->pClean, p);
  p->flags &= ~PGHDR_DIRTY;





}

/*
** Make every page in the cache clean.
*/
void sqlite3PcacheCleanAll(PCache *pCache){
  PgHdr *p;
  assert( pCache->iInUseDB );
  pcacheEnterGlobal();
  while( (p = pCache->pDirty)!=0 ){
    assert( p->apSave[0]==0 && p->apSave[1]==0 );
    pcacheRemoveFromList(&pCache->pDirty, p);
    pcacheAddToList(&pCache->pClean, p);
    p->flags &= ~PGHDR_DIRTY;

  }
  sqlite3PcacheAssertFlags(pCache, 0, PGHDR_DIRTY);

  pcacheExitGlobal();


}

/*
** Change the page number of page p to newPgno. If newPgno is 0, then the
** page object is added to the clean-list and the PGHDR_REUSE_UNLIKELY 
** flag set.
*/
................................................................................
  for(p=pCache->pClean; p; p=pNext){
    pNext = p->pNext;
    pcacheRemoveFromLruList(p);
    pcachePageFree(p);
  }
  for(p=pCache->pDirty; p; p=pNext){
    pNext = p->pNext;
    pcacheRemoveFromLruList(p);
    pcachePageFree(p);
  }
  pCache->pClean = 0;
  pCache->pDirty = 0;
  pCache->nPage = 0;
  memset(pCache->apHash, 0, pCache->nHash*sizeof(pCache->apHash[0]));
}
................................................................................
    pNext = p->pNext;
    if( p->pgno>pgno ){
      if( p->nRef==0 ){
        pcacheRemoveFromHash(p);
        if( p->flags&PGHDR_DIRTY ){
          pcacheRemoveFromList(&pCache->pDirty, p);
        }else{

          pcacheRemoveFromList(&pCache->pClean, p);
        }
        pcacheRemoveFromLruList(p);
        pcachePageFree(p);
      }else{
        /* If there are references to the page, it cannot be freed. In this
        ** case, zero the page content instead.
        */
        memset(p->pData, 0, pCache->szPage);
      }
................................................................................


/*
** Close a cache.
*/
void sqlite3PcacheClose(PCache *pCache){
  assert( pCache->iInUseDB==1 );
  pcacheEnterGlobal();

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



  pcacheClear(pCache);
  if( pCache->bPurgeable ){
    pcache.mxPagePurgeable -= pCache->nMax;
  }
  sqlite3_free(pCache->apHash);


  /* Now remove the pager-cache structure itself from the list of
  ** all such structures headed by pcache.pAll. 

  */


  assert(pCache==pcache.pAll || pCache->pPrevAll);
  assert(pCache->pNextAll==0 || pCache->pNextAll->pPrevAll==pCache);
  assert(pCache->pPrevAll==0 || pCache->pPrevAll->pNextAll==pCache);
  if( pCache->pPrevAll ){
    pCache->pPrevAll->pNextAll = pCache->pNextAll;
  }else{
    pcache.pAll = pCache->pNextAll;
  }
  if( pCache->pNextAll ){
    pCache->pNextAll->pPrevAll = pCache->pPrevAll;
  }

  pcacheExitGlobal();
}

/*
** Preserve the content of the page, if it has not been preserved
** already.  If idJournal==0 then this is for the overall transaction.
** If idJournal==1 then this is for the statement journal.
**
................................................................................
  assert( pCache->iInUseDB );
  for(p=pCache->pDirty; p; p=p->pNext){
    p->pDirty = p->pNext;
  }
  return pcacheSortDirtyList(pCache->pDirty);
}
































/* 
** Return the total number of outstanding page references.
*/
int sqlite3PcacheRefCount(PCache *pCache){
  return pCache->nRef;
}

................................................................................
#endif

/* 
** Set flags on all pages in the page cache 
*/
void sqlite3PcacheSetFlags(PCache *pCache, int andMask, int orMask){
  PgHdr *p;

  assert( (orMask&PGHDR_NEED_SYNC)==0 );
  assert( pCache->iInUseDB || pCache->iInUseMM );

  /* If this call is being made from within a call to the xStress callback
  ** of a pager-cache (i.e. from within pagerRecycle()), then the 
  ** PCache.iInUseDB will be set to zero. In this case, the LRU mutex is
  ** already held. Otherwise, obtain it before modifying any PgHdr.flags
  ** variables or traversing the LRU list.
  */ 
  if( pCache->iInUseDB ){
    pcacheEnterGlobal();
  }
  assert( sqlite3_mutex_held(pcache.mutex_lru) );

  for(p=pCache->pDirty; p; p=p->pNext){
    p->flags = (p->flags&andMask)|orMask;
  }
  for(p=pCache->pClean; p; p=p->pNext){
    p->flags = (p->flags&andMask)|orMask;
  }

  if( 0==(andMask&PGHDR_NEED_SYNC) ){
    for(p=pcache.pLruTail; p && (p->flags&PGHDR_NEED_SYNC); p=p->pPrevLru);
    pcache.pLruSynced = p;
  }

  if( pCache->iInUseDB ){
    pcacheExitGlobal();
  }
}

/*
** Set the suggested cache-size value.
*/
int sqlite3PcacheGetCachesize(PCache *pCache){
  return pCache->nMax;

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the sqlite page cache
** subsystem. 
**
** @(#) $Id: pcache.h,v 1.3 2008/08/21 20:21:35 drh Exp $
*/

#ifndef _PCACHE_H_

typedef struct PgHdr PgHdr;
typedef struct PCache PCache;

................................................................................
void sqlite3PCacheFree(void*);

/* Create a new pager cache.
** Under memory stress, invoke xStress to try to make pages clean.
** Only clean and unpinned pages can be reclaimed.
*/
void sqlite3PcacheOpen(
  int szPage,                  /* Size of every page */
  int szExtra,                 /* Extra space associated with each page */
  int bPurgeable,              /* True if pages are on backing store */
  void (*xDestroy)(PgHdr *),   /* Called to destroy a page */
  int (*xStress)(void*),       /* Call to try to make pages clean */
  void *pStress,               /* Argument to xStress */
  PCache *pToInit              /* Preallocated space for the PCache */
);

/* Modify the page-size after the cache has been created. */
void sqlite3PcacheSetPageSize(PCache *, int);

/* Return the size in bytes of a PCache object.  Used to preallocate
** storage space.
................................................................................
int sqlite3PcachePreserve(PgHdr*, int);    /* Preserve current page content */
void sqlite3PcacheCommit(PCache*, int);    /* Drop preserved copy */
void sqlite3PcacheRollback(PCache*, int);  /* Rollback to preserved copy */

/* Get a list of all dirty pages in the cache, sorted by page number */
PgHdr *sqlite3PcacheDirtyList(PCache*);

/* Query the cache for a dirty page with a zero ref-count */
PgHdr *sqlite3PcacheDirtyPage(PCache *);

/* Reset and close the cache object */
void sqlite3PcacheClose(PCache*);

/* Set flags on all pages in the page cache */
void sqlite3PcacheSetFlags(PCache*, int andMask, int orMask);

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

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This header file defines the interface that the sqlite page cache
** subsystem. 
**
** @(#) $Id: pcache.h,v 1.4 2008/08/22 16:22:17 danielk1977 Exp $
*/

#ifndef _PCACHE_H_

typedef struct PgHdr PgHdr;
typedef struct PCache PCache;

................................................................................
void sqlite3PCacheFree(void*);

/* Create a new pager cache.
** Under memory stress, invoke xStress to try to make pages clean.
** Only clean and unpinned pages can be reclaimed.
*/
void sqlite3PcacheOpen(
  int szPage,                    /* Size of every page */
  int szExtra,                   /* Extra space associated with each page */
  int bPurgeable,                /* True if pages are on backing store */
  void (*xDestroy)(PgHdr *),     /* Called to destroy a page */
  int (*xStress)(void*, PgHdr*), /* Call to try to make pages clean */
  void *pStress,                 /* Argument to xStress */
  PCache *pToInit                /* Preallocated space for the PCache */
);

/* Modify the page-size after the cache has been created. */
void sqlite3PcacheSetPageSize(PCache *, int);

/* Return the size in bytes of a PCache object.  Used to preallocate
** storage space.
................................................................................
int sqlite3PcachePreserve(PgHdr*, int);    /* Preserve current page content */
void sqlite3PcacheCommit(PCache*, int);    /* Drop preserved copy */
void sqlite3PcacheRollback(PCache*, int);  /* Rollback to preserved copy */

/* Get a list of all dirty pages in the cache, sorted by page number */
PgHdr *sqlite3PcacheDirtyList(PCache*);




/* Reset and close the cache object */
void sqlite3PcacheClose(PCache*);

/* Set flags on all pages in the page cache */
void sqlite3PcacheSetFlags(PCache*, int andMask, int orMask);

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

#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# $Id: mutex1.test,v 1.12 2008/08/21 12:19:44 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

if {[info exists tester_do_binarylog]} {
  finish_test
  return
................................................................................
#   * Multi-threaded mode,
#   * Single-threaded mode.
#
set enable_shared_cache [sqlite3_enable_shared_cache 1]
ifcapable threadsafe {
  foreach {mode mutexes} {
    singlethread {}
    multithread  {fast static_lru static_master static_mem static_mem2 static_prng }
    serialized   {fast recursive static_lru static_master static_mem static_mem2 static_prng }
  } {

    do_test mutex1.2.$mode.1 {
      catch {db close}
      sqlite3_shutdown
      sqlite3_config $mode
    } SQLITE_OK

#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# $Id: mutex1.test,v 1.13 2008/08/22 16:22:17 danielk1977 Exp $

set testdir [file dirname $argv0]
source $testdir/tester.tcl

if {[info exists tester_do_binarylog]} {
  finish_test
  return
................................................................................
#   * Multi-threaded mode,
#   * Single-threaded mode.
#
set enable_shared_cache [sqlite3_enable_shared_cache 1]
ifcapable threadsafe {
  foreach {mode mutexes} {
    singlethread {}
    multithread  {fast static_lru static_master static_mem static_prng }
    serialized   {fast recursive static_lru static_master static_mem static_prng }
  } {

    do_test mutex1.2.$mode.1 {
      catch {db close}
      sqlite3_shutdown
      sqlite3_config $mode
    } SQLITE_OK