**    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.20 2008/08/28 08:31:48 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** A complete page cache is an instance of this structure.
**
** A cache may only be deleted by its owner and while holding the
................................................................................
*/
static int pcacheCheckSynced(PCache *pCache){
  PgHdr *p = pCache->pDirtyTail;
  for(p=pCache->pDirtyTail; p!=pCache->pSynced; p=p->pPrev){
    assert( p->nRef || (p->flags&PGHDR_NEED_SYNC) );
  }
  return (p==0 || p->nRef || (p->flags&PGHDR_NEED_SYNC)==0);
  return 1;
}
#endif /* !NDEBUG && SQLITE_ENABLE_EXPENSIVE_ASSERT */



/*
** Remove a page from its hash table (PCache.apHash[]).
*/
static void pcacheRemoveFromHash(PgHdr *pPage){
  /* assert( pcacheMutexHeld() ); *** FIXME ****/
  if( pPage->pPrevHash ){
    pPage->pPrevHash->pNextHash = pPage->pNextHash;
  }else{
    PCache *pCache = pPage->pCache;
    u32 h = pPage->pgno % pCache->nHash;
    assert( pCache->apHash[h]==pPage );
    pCache->apHash[h] = pPage->pNextHash;
................................................................................
** Insert a page into the hash table
**
** The mutex must be held by the caller.
*/
static void pcacheAddToHash(PgHdr *pPage){
  PCache *pCache = pPage->pCache;
  u32 h = pPage->pgno % pCache->nHash;
  /* assert( pcacheMutexHeld() ); *** FIXME *****/
  pPage->pNextHash = pCache->apHash[h];
  pPage->pPrevHash = 0;
  if( pCache->apHash[h] ){
    pCache->apHash[h]->pPrevHash = pPage;
  }
  pCache->apHash[h] = pPage;
  pCache->nPage++;
................................................................................
/*
** Attempt to increase the size the hash table to contain
** at least nHash buckets.
*/
static int pcacheResizeHash(PCache *pCache, int nHash){
  PgHdr *p;
  PgHdr **pNew;
  /* assert( pcacheMutexHeld() ); **** FIXME *****/
#ifdef SQLITE_MALLOC_SOFT_LIMIT
  if( nHash*sizeof(PgHdr*)>SQLITE_MALLOC_SOFT_LIMIT ){
    nHash = SQLITE_MALLOC_SOFT_LIMIT/sizeof(PgHdr *);
  }
#endif

  pNew = (PgHdr **)sqlite3_malloc(sizeof(PgHdr*)*nHash);

  if( !pNew ){
    return SQLITE_NOMEM;
  }
  memset(pNew, 0, sizeof(PgHdr *)*nHash);
  sqlite3_free(pCache->apHash);
  pCache->apHash = pNew;
  pCache->nHash = nHash;
................................................................................
/*
** Remove a page from a linked list that is headed by *ppHead.
** *ppHead is either PCache.pClean or PCache.pDirty.
*/
static void pcacheRemoveFromList(PgHdr **ppHead, PgHdr *pPage){
  int isDirtyList = (ppHead==&pPage->pCache->pDirty);
  assert( ppHead==&pPage->pCache->pClean || ppHead==&pPage->pCache->pDirty );
  /* assert( pcacheMutexHeld() || ppHead!=&pPage->pCache->pClean ); *** FIXME */

  if( pPage->pPrev ){
    pPage->pPrev->pNext = pPage->pNext;
  }else{
    assert( *ppHead==pPage );
    *ppHead = pPage->pNext;
  }
................................................................................
static int pcacheRecycleOrAlloc(PCache *pCache, PgHdr **ppPage){
  PgHdr *p = 0;

  int szPage = pCache->szPage;
  int szExtra = pCache->szExtra;

  assert( pcache.isInit );
  assert( sqlite3_mutex_notheld(pcache.mutex) );

  *ppPage = 0;
  pcacheEnterMutex();

  /* If we have reached the limit for pinned/dirty pages, and there is at
  ** least one dirty page, invoke the xStress callback to cause a page to
  ** become clean.
  */
  expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );
  expensive_assert( pcacheCheckSynced(pCache) );
................................................................................
    p = 0;
  }

  if( !p ){
    p = pcachePageAlloc(pCache);
  }

  pcacheExitMutex();
  *ppPage = p;
  return (p?SQLITE_OK:SQLITE_NOMEM);
}

/*************************************************** General Interfaces ******
**
** Initialize and shutdown the page cache subsystem. Neither of these 
................................................................................
*/
int sqlite3PcacheFetch(
  PCache *pCache,       /* Obtain the page from this cache */
  Pgno pgno,            /* Page number to obtain */
  int createFlag,       /* If true, create page if it does not exist already */
  PgHdr **ppPage        /* Write the page here */
){

  PgHdr *pPage;

  assert( pcache.isInit );
  assert( pCache!=0 );
  assert( pgno>0 );
  expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );



  /* Search the hash table for the requested page. Exit early if it is found. */
  if( pCache->apHash ){
    u32 h = pgno % pCache->nHash;
    pcacheEnterMutex();
    for(pPage=pCache->apHash[h]; pPage; pPage=pPage->pNextHash){
      if( pPage->pgno==pgno ){
        if( pPage->nRef==0 ){
          if( 0==(pPage->flags&PGHDR_DIRTY) ){
            pcacheRemoveFromLruList(pPage);
            pCache->nPinned++;
          }
          pCache->nRef++;
        }
        pPage->nRef++;
        *ppPage = pPage;
        pcacheExitMutex();
        return SQLITE_OK;
      }
    }
    pcacheExitMutex();
  }

  if( createFlag ){
    int rc = SQLITE_OK;
    if( pCache->nHash<=pCache->nPage ){
      rc = pcacheResizeHash(pCache, pCache->nHash<256 ? 256 : pCache->nHash*2);
      if( rc!=SQLITE_OK ){
        return rc;
      }
    }


    rc = pcacheRecycleOrAlloc(pCache, ppPage);
    if( rc!=SQLITE_OK ){
      return rc;
    }
    pPage = *ppPage;

    pPage->pPager = 0;
    pPage->flags = 0;
    pPage->pDirty = 0;
    pPage->pgno = pgno;
    pPage->pCache = pCache;
    pPage->nRef = 1;
    pCache->nRef++;
    pCache->nPinned++;
    pcacheAddToList(&pCache->pClean, pPage);
    pcacheAddToHash(pPage);
  }else{
    *ppPage = 0;
  }





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

  return SQLITE_OK;
}

/*
** Dereference a page.  When the reference count reaches zero,
** move the page to the LRU list if it is clean.
*/
void sqlite3PcacheRelease(PgHdr *p){
................................................................................
void sqlite3PcacheDrop(PgHdr *p){
  PCache *pCache;
  assert( p->nRef==1 );
  assert( 0==(p->flags&PGHDR_DIRTY) );
  pCache = p->pCache;
  pCache->nRef--;
  pCache->nPinned--;

  pcacheRemoveFromList(&pCache->pClean, p);
  pcacheRemoveFromHash(p);
  pcacheEnterMutex();
  pcachePageFree(p);
  pcacheExitMutex();
}

/*
** Make sure the page is marked as dirty.  If it isn't dirty already,
** make it so.
................................................................................
void sqlite3PcacheMakeDirty(PgHdr *p){
  PCache *pCache;
  p->flags &= ~PGHDR_DONT_WRITE;
  if( p->flags & PGHDR_DIRTY ) return;
  assert( (p->flags & PGHDR_DIRTY)==0 );
  assert( p->nRef>0 );
  pCache = p->pCache;

  pcacheRemoveFromList(&pCache->pClean, p);
  pcacheAddToList(&pCache->pDirty, p);

  p->flags |= PGHDR_DIRTY;
}

/*
** Make sure the page is marked as clean.  If it isn't clean already,
** make it so.
*/
void sqlite3PcacheMakeClean(PgHdr *p){
  PCache *pCache;
  if( (p->flags & PGHDR_DIRTY)==0 ) return;
  assert( p->apSave[0]==0 && p->apSave[1]==0 );
  assert( p->flags & PGHDR_DIRTY );
  pCache = p->pCache;
  pcacheRemoveFromList(&pCache->pDirty, p);
  pcacheEnterMutex();
  pcacheAddToList(&pCache->pClean, p);
  p->flags &= ~PGHDR_DIRTY;
  if( p->nRef==0 ){
    pcacheAddToLruList(p);
    pCache->nPinned--;
  }
  expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );










  pcacheExitMutex();

}

/*
** Make every page in the cache clean.
*/
void sqlite3PcacheCleanAll(PCache *pCache){
  PgHdr *p;
................................................................................
/*
** 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.
*/
void sqlite3PcacheMove(PgHdr *p, Pgno newPgno){
  assert( p->nRef>0 );

  pcacheRemoveFromHash(p);
  p->pgno = newPgno;
  if( newPgno==0 ){
    p->flags |= PGHDR_REUSE_UNLIKELY;
    pcacheEnterMutex();
    pcacheFree(p->apSave[0]);
    pcacheFree(p->apSave[1]);
    pcacheExitMutex();
    p->apSave[0] = 0;
    p->apSave[1] = 0;

    sqlite3PcacheMakeClean(p);
  }

  pcacheAddToHash(p);

}

/*
** Remove all content from a page cache
*/
void pcacheClear(PCache *pCache){
  PgHdr *p, *pNext;

**    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.21 2008/08/28 10:21:17 danielk1977 Exp $
*/
#include "sqliteInt.h"

/*
** A complete page cache is an instance of this structure.
**
** A cache may only be deleted by its owner and while holding the
................................................................................
*/
static int pcacheCheckSynced(PCache *pCache){
  PgHdr *p = pCache->pDirtyTail;
  for(p=pCache->pDirtyTail; p!=pCache->pSynced; p=p->pPrev){
    assert( p->nRef || (p->flags&PGHDR_NEED_SYNC) );
  }
  return (p==0 || p->nRef || (p->flags&PGHDR_NEED_SYNC)==0);

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



/*
** Remove a page from its hash table (PCache.apHash[]).
*/
static void pcacheRemoveFromHash(PgHdr *pPage){
  assert( pcacheMutexHeld() );
  if( pPage->pPrevHash ){
    pPage->pPrevHash->pNextHash = pPage->pNextHash;
  }else{
    PCache *pCache = pPage->pCache;
    u32 h = pPage->pgno % pCache->nHash;
    assert( pCache->apHash[h]==pPage );
    pCache->apHash[h] = pPage->pNextHash;
................................................................................
** Insert a page into the hash table
**
** The mutex must be held by the caller.
*/
static void pcacheAddToHash(PgHdr *pPage){
  PCache *pCache = pPage->pCache;
  u32 h = pPage->pgno % pCache->nHash;
  assert( pcacheMutexHeld() );
  pPage->pNextHash = pCache->apHash[h];
  pPage->pPrevHash = 0;
  if( pCache->apHash[h] ){
    pCache->apHash[h]->pPrevHash = pPage;
  }
  pCache->apHash[h] = pPage;
  pCache->nPage++;
................................................................................
/*
** Attempt to increase the size the hash table to contain
** at least nHash buckets.
*/
static int pcacheResizeHash(PCache *pCache, int nHash){
  PgHdr *p;
  PgHdr **pNew;
  assert( pcacheMutexHeld() );
#ifdef SQLITE_MALLOC_SOFT_LIMIT
  if( nHash*sizeof(PgHdr*)>SQLITE_MALLOC_SOFT_LIMIT ){
    nHash = SQLITE_MALLOC_SOFT_LIMIT/sizeof(PgHdr *);
  }
#endif
  pcacheExitMutex();
  pNew = (PgHdr **)sqlite3Malloc(sizeof(PgHdr*)*nHash);
  pcacheEnterMutex();
  if( !pNew ){
    return SQLITE_NOMEM;
  }
  memset(pNew, 0, sizeof(PgHdr *)*nHash);
  sqlite3_free(pCache->apHash);
  pCache->apHash = pNew;
  pCache->nHash = nHash;
................................................................................
/*
** Remove a page from a linked list that is headed by *ppHead.
** *ppHead is either PCache.pClean or PCache.pDirty.
*/
static void pcacheRemoveFromList(PgHdr **ppHead, PgHdr *pPage){
  int isDirtyList = (ppHead==&pPage->pCache->pDirty);
  assert( ppHead==&pPage->pCache->pClean || ppHead==&pPage->pCache->pDirty );
  assert( pcacheMutexHeld() || ppHead!=&pPage->pCache->pClean );

  if( pPage->pPrev ){
    pPage->pPrev->pNext = pPage->pNext;
  }else{
    assert( *ppHead==pPage );
    *ppHead = pPage->pNext;
  }
................................................................................
static int pcacheRecycleOrAlloc(PCache *pCache, PgHdr **ppPage){
  PgHdr *p = 0;

  int szPage = pCache->szPage;
  int szExtra = pCache->szExtra;

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

  *ppPage = 0;


  /* If we have reached the limit for pinned/dirty pages, and there is at
  ** least one dirty page, invoke the xStress callback to cause a page to
  ** become clean.
  */
  expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );
  expensive_assert( pcacheCheckSynced(pCache) );
................................................................................
    p = 0;
  }

  if( !p ){
    p = pcachePageAlloc(pCache);
  }


  *ppPage = p;
  return (p?SQLITE_OK:SQLITE_NOMEM);
}

/*************************************************** General Interfaces ******
**
** Initialize and shutdown the page cache subsystem. Neither of these 
................................................................................
*/
int sqlite3PcacheFetch(
  PCache *pCache,       /* Obtain the page from this cache */
  Pgno pgno,            /* Page number to obtain */
  int createFlag,       /* If true, create page if it does not exist already */
  PgHdr **ppPage        /* Write the page here */
){
  int rc = SQLITE_OK;
  PgHdr *pPage = 0;

  assert( pcache.isInit );
  assert( pCache!=0 );
  assert( pgno>0 );
  expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );

  pcacheEnterMutex();

  /* 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 ){
          if( 0==(pPage->flags&PGHDR_DIRTY) ){
            pcacheRemoveFromLruList(pPage);
            pCache->nPinned++;
          }
          pCache->nRef++;
        }
        pPage->nRef++;
        break;


      }
    }

  }

  if( !pPage && createFlag ){

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


    }


    if( rc==SQLITE_OK ){
      rc = pcacheRecycleOrAlloc(pCache, &pPage);


    }

    if( rc==SQLITE_OK ){
      pPage->pPager = 0;
      pPage->flags = 0;
      pPage->pDirty = 0;
      pPage->pgno = pgno;
      pPage->pCache = pCache;
      pPage->nRef = 1;
      pCache->nRef++;
      pCache->nPinned++;
      pcacheAddToList(&pCache->pClean, pPage);
      pcacheAddToHash(pPage);


    }
  }

  pcacheExitMutex();

  *ppPage = pPage;
  expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );
  assert( pPage || !createFlag || rc!=SQLITE_OK );
  return rc;
}

/*
** Dereference a page.  When the reference count reaches zero,
** move the page to the LRU list if it is clean.
*/
void sqlite3PcacheRelease(PgHdr *p){
................................................................................
void sqlite3PcacheDrop(PgHdr *p){
  PCache *pCache;
  assert( p->nRef==1 );
  assert( 0==(p->flags&PGHDR_DIRTY) );
  pCache = p->pCache;
  pCache->nRef--;
  pCache->nPinned--;
  pcacheEnterMutex();
  pcacheRemoveFromList(&pCache->pClean, p);
  pcacheRemoveFromHash(p);

  pcachePageFree(p);
  pcacheExitMutex();
}

/*
** Make sure the page is marked as dirty.  If it isn't dirty already,
** make it so.
................................................................................
void sqlite3PcacheMakeDirty(PgHdr *p){
  PCache *pCache;
  p->flags &= ~PGHDR_DONT_WRITE;
  if( p->flags & PGHDR_DIRTY ) return;
  assert( (p->flags & PGHDR_DIRTY)==0 );
  assert( p->nRef>0 );
  pCache = p->pCache;
  pcacheEnterMutex();
  pcacheRemoveFromList(&pCache->pClean, p);
  pcacheAddToList(&pCache->pDirty, p);
  pcacheExitMutex();
  p->flags |= PGHDR_DIRTY;
}





void pcacheMakeClean(PgHdr *p){
  PCache *pCache = p->pCache;

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

  pcacheRemoveFromList(&pCache->pDirty, p);

  pcacheAddToList(&pCache->pClean, p);
  p->flags &= ~PGHDR_DIRTY;
  if( p->nRef==0 ){
    pcacheAddToLruList(p);
    pCache->nPinned--;
  }
  expensive_assert( pCache->nPinned==pcachePinnedCount(pCache) );
}

/*
** Make sure the page is marked as clean.  If it isn't clean already,
** make it so.
*/
void sqlite3PcacheMakeClean(PgHdr *p){
  if( (p->flags & PGHDR_DIRTY) ){
    pcacheEnterMutex();
    pcacheMakeClean(p);
    pcacheExitMutex();
  }
}

/*
** Make every page in the cache clean.
*/
void sqlite3PcacheCleanAll(PCache *pCache){
  PgHdr *p;
................................................................................
/*
** 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.
*/
void sqlite3PcacheMove(PgHdr *p, Pgno newPgno){
  assert( p->nRef>0 );
  pcacheEnterMutex();
  pcacheRemoveFromHash(p);
  p->pgno = newPgno;
  if( newPgno==0 ){
    p->flags |= PGHDR_REUSE_UNLIKELY;

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

    p->apSave[0] = 0;
    p->apSave[1] = 0;
    if( (p->flags & PGHDR_DIRTY) ){
      pcacheMakeClean(p);
    }
  }
  pcacheAddToHash(p);
  pcacheExitMutex();
}

/*
** Remove all content from a page cache
*/
void pcacheClear(PCache *pCache){
  PgHdr *p, *pNext;

#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
#   This file contains tests that attempt to break the pcache module
#   by bombarding it with simultaneous requests from multiple threads.
#     
# $Id: thread003.test,v 1.1 2008/08/28 08:31:48 danielk1977 Exp $

set testdir [file dirname $argv0]

source $testdir/tester.tcl
source $testdir/thread_common.tcl
if {[info commands sqlthread] eq ""} {
  finish_test
................................................................................
    unset -nocomplain finished($zFile)
    thread_spawn finished($zFile) $thread_procs $SCRIPT
  }
  foreach zFile {test.db test2.db} {
    if {![info exists finished($zFile)]} {
      vwait finished($zFile)
    }
  }
  expr 0
} {0}















































































finish_test

#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
#   This file contains tests that attempt to break the pcache module
#   by bombarding it with simultaneous requests from multiple threads.
#     
# $Id: thread003.test,v 1.2 2008/08/28 10:21:17 danielk1977 Exp $

set testdir [file dirname $argv0]

source $testdir/tester.tcl
source $testdir/thread_common.tcl
if {[info commands sqlthread] eq ""} {
  finish_test
................................................................................
    unset -nocomplain finished($zFile)
    thread_spawn finished($zFile) $thread_procs $SCRIPT
  }
  foreach zFile {test.db test2.db} {
    if {![info exists finished($zFile)]} {
      vwait finished($zFile)
    }
  }
  expr 0
} {0}

# This test is the same as the test above, except that each thread also
# writes to the database. This causes pages to be moved back and forth 
# between the caches internal dirty and clean lists, which is another
# opportunity for a thread-related bug to present itself.
#
set nSecond 30
puts "Starting thread003.3 (should run for ~$nSecond seconds)"
do_test thread003.3 {
  foreach zFile {test.db test2.db} {
    set SCRIPT [format {
      set iStart [clock seconds]
      set iEnd [expr {[clock seconds] + %d}]
      set ::DB [sqlthread open %s]
  
      # Set the cache size to 15 pages per cache. 30 available globally.
      execsql { PRAGMA cache_size = 15 }
  
      while {[clock seconds] < $iEnd} {
        set iQuery [expr {int(rand()*5000)}]
        execsql "SELECT * FROM t1 WHERE a = $iQuery"
        execsql "UPDATE t1 SET b = randomblob(200) 
                 WHERE a < $iQuery AND a > $iQuery + 20
        "
      }
  
      sqlite3_close $::DB
      expr 1
    } $nSecond $zFile]
  
    unset -nocomplain finished($zFile)
    thread_spawn finished($zFile) $thread_procs $SCRIPT
  }
  foreach zFile {test.db test2.db} {
    if {![info exists finished($zFile)]} {
      vwait finished($zFile)
    }
  }
  expr 0
} {0}

# In this test case, one thread is continually querying the database.
# The other thread does not have a database connection, but calls
# sqlite3_release_memory() over and over again.
#
set nSecond 30
puts "Starting thread003.3 (should run for ~$nSecond seconds)"
do_test thread003.4 {
  thread_spawn finished(1) $thread_procs [format {
    set iEnd [expr {[clock seconds] + %d}]
    set ::DB [sqlthread open test.db]

    # Set the cache size to 15 pages per cache. 30 available globally.
    execsql { PRAGMA cache_size = 15 }

    while {[clock seconds] < $iEnd} {
      set iQuery [expr {int(rand()*5000)}]
      execsql "SELECT * FROM t1 WHERE a = $iQuery"
    }

    sqlite3_close $::DB
    expr 1
  } $nSecond] 
  thread_spawn finished(2) [format {
    set iEnd [expr {[clock seconds] + %d}]

    while {[clock seconds] < $iEnd} {
      sqlite3_release_memory 1000
    }
  } $nSecond]
  
  foreach ii {1 2} {
    if {![info exists finished($ii)]} {
      vwait finished($ii)
    }
  }
  expr 0
} {0}

finish_test