** 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.377 2007/08/27 17:27:49 danielk1977 Exp $
*/
#ifndef SQLITE_OMIT_DISKIO
#include "sqliteInt.h"
#include <assert.h>
#include <string.h>

/*
................................................................................
/*
** This macro rounds values up so that if the value is an address it
** is guaranteed to be an address that is aligned to an 8-byte boundary.
*/
#define FORCE_ALIGNMENT(X)   (((X)+7)&~7)

typedef struct PgHdr PgHdr;



























typedef struct PagerLruLink PagerLruLink;
struct PagerLruLink {
  PgHdr *pNext;
  PgHdr *pPrev;
};

/*
................................................................................
*/
#define PGHDR_TO_DATA(P)  ((void*)(&(P)[1]))
#define DATA_TO_PGHDR(D)  (&((PgHdr*)(D))[-1])
#define PGHDR_TO_EXTRA(G,P) ((void*)&((char*)(&(G)[1]))[(P)->pageSize])
#define PGHDR_TO_HIST(P,PGR)  \
            ((PgHistory*)&((char*)(&(P)[1]))[(PGR)->pageSize+(PGR)->nExtra])

typedef struct PagerLruList PagerLruList;
struct PagerLruList {
  PgHdr *pFirst;
  PgHdr *pLast;
  PgHdr *pFirstSynced;   /* First page in list with PgHdr.needSync==0 */
};

/*
** A open page cache is an instance of the following structure.
**
** Pager.errCode may be set to SQLITE_IOERR, SQLITE_CORRUPT, or
** or SQLITE_FULL. Once one of the first three errors occurs, it persists
** and is returned as the result of every major pager API call.  The
** SQLITE_FULL return code is slightly different. It persists only until the
................................................................................
    cnt++;   /* Something to set a breakpoint on */
  }
# define REFINFO(X)  pager_refinfo(X)
#else
# define REFINFO(X)
#endif








static void listAdd(PagerLruList *pList, PagerLruLink *pLink, PgHdr *pPg){
  pLink->pNext = 0;
  pLink->pPrev = pList->pLast;






  if( pList->pLast ){
    int iOff = (char *)pLink - (char *)pPg;
    PagerLruLink *pLastLink = (PagerLruLink *)(&((u8 *)pList->pLast)[iOff]);
    pLastLink->pNext = pPg;
  }else{
    assert(!pList->pFirst);
................................................................................

  pList->pLast = pPg;
  if( !pList->pFirstSynced && pPg->needSync==0 ){
    pList->pFirstSynced = pPg;
  }
}







static void listRemove(PagerLruList *pList, PagerLruLink *pLink, PgHdr *pPg){
  int iOff = (char *)pLink - (char *)pPg;






  if( pPg==pList->pFirst ){
    pList->pFirst = pLink->pNext;
  }
  if( pPg==pList->pLast ){
    pList->pLast = pLink->pPrev;
  }
................................................................................
    pList->pFirstSynced = p;
  }

  pLink->pNext = pLink->pPrev = 0;
}

/* 
** Add page to the free-list 


*/
static void lruListAdd(PgHdr *pPg){
  listAdd(&pPg->pPager->lru, &pPg->free, pPg);
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
  if( !pPg->pPager->memDb ){
    sqlite3_mutex_enter(sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU));
    listAdd(&sqlite3LruPageList, &pPg->gfree, pPg);
    sqlite3_mutex_leave(sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU));
  }
#endif
}

/* 
** Remove page from free-list 


*/
static void lruListRemove(PgHdr *pPg){
  listRemove(&pPg->pPager->lru, &pPg->free, pPg);
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
  if( !pPg->pPager->memDb ){
    sqlite3_mutex_enter(sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU));
    listRemove(&sqlite3LruPageList, &pPg->gfree, pPg);
    sqlite3_mutex_leave(sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU));
  }
#endif
}

/* 
** Set the Pager.pFirstSynced variable 




*/
static void lruListSetFirstSynced(Pager *pPager){
  pPager->lru.pFirstSynced = pPager->lru.pFirst;
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
  if( !pPager->memDb ){
    PgHdr *p;
    sqlite3_mutex_enter(sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU));
................................................................................
      pPg = sqlite3LruPageList.pFirst;
      while( pPg && pPg->pPager->iInUseDB ){
        pPg = pPg->gfree.pNext;
      }
    }
    sqlite3_mutex_leave(sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU));





    if( !pPg ) break;

    pPager = pPg->pPager;
    assert(!pPg->needSync || pPg==pPager->lru.pFirst);
    assert(pPg->needSync || pPg==pPager->lru.pFirstSynced);
  
    rc = pager_recycle(pPager, 1, &pRecycled);
................................................................................
          sizeof(*pPg) + pPager->pageSize
          + sizeof(u32) + pPager->nExtra
          + MEMDB*sizeof(PgHistory) 
      );
      IOTRACE(("PGFREE %p %d *\n", pPager, pPg->pgno));
      PAGER_INCR(sqlite3_pager_pgfree_count);
      sqlite3_free(pPg);

    }else{
      /* An error occured whilst writing to the database file or 
      ** journal in pager_recycle(). The error is not returned to the 
      ** caller of this function. Instead, set the Pager.errCode variable.
      ** The error will be returned to the user (or users, in the case 
      ** of a shared pager cache) of the pager for which the error occured.
      */

** 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.378 2007/08/28 08:00:18 danielk1977 Exp $
*/
#ifndef SQLITE_OMIT_DISKIO
#include "sqliteInt.h"
#include <assert.h>
#include <string.h>

/*
................................................................................
/*
** This macro rounds values up so that if the value is an address it
** is guaranteed to be an address that is aligned to an 8-byte boundary.
*/
#define FORCE_ALIGNMENT(X)   (((X)+7)&~7)

typedef struct PgHdr PgHdr;

/*
** Each pager stores all currently unreferenced pages in a list sorted
** in least-recently-used (LRU) order (i.e. the first item on the list has 
** not been referenced in a long time, the last item has been recently
** used). An instance of this structure is included as part of each
** pager structure for this purpose (variable Pager.lru).
**
** Additionally, if memory-management is enabled, all unreferenced pages 
** are stored in a global LRU list (global variable sqlite3LruPageList).
**
** In both cases, the PagerLruList.pFirstSynced variable points to
** the first page in the corresponding list that does not require an
** fsync() operation before it's memory can be reclaimed. If no such
** page exists, PagerLruList.pFirstSynced is set to NULL.
*/
typedef struct PagerLruList PagerLruList;
struct PagerLruList {
  PgHdr *pFirst;         /* First page in LRU list */
  PgHdr *pLast;          /* Last page in LRU list (the most recently used) */
  PgHdr *pFirstSynced;   /* First page in list with PgHdr.needSync==0 */
};

/*
** The following structure contains the next and previous pointers used
** to link a PgHdr structure into a PagerLruList linked list. 
*/
typedef struct PagerLruLink PagerLruLink;
struct PagerLruLink {
  PgHdr *pNext;
  PgHdr *pPrev;
};

/*
................................................................................
*/
#define PGHDR_TO_DATA(P)  ((void*)(&(P)[1]))
#define DATA_TO_PGHDR(D)  (&((PgHdr*)(D))[-1])
#define PGHDR_TO_EXTRA(G,P) ((void*)&((char*)(&(G)[1]))[(P)->pageSize])
#define PGHDR_TO_HIST(P,PGR)  \
            ((PgHistory*)&((char*)(&(P)[1]))[(PGR)->pageSize+(PGR)->nExtra])








/*
** A open page cache is an instance of the following structure.
**
** Pager.errCode may be set to SQLITE_IOERR, SQLITE_CORRUPT, or
** or SQLITE_FULL. Once one of the first three errors occurs, it persists
** and is returned as the result of every major pager API call.  The
** SQLITE_FULL return code is slightly different. It persists only until the
................................................................................
    cnt++;   /* Something to set a breakpoint on */
  }
# define REFINFO(X)  pager_refinfo(X)
#else
# define REFINFO(X)
#endif

/*
** Add page pPg to the end of the linked list managed by structure
** pList (pPg becomes the last entry in the list - the most recently 
** used). Argument pLink should point to either pPg->free or pPg->gfree,
** depending on whether pPg is being added to the pager-specific or
** global LRU list.
*/
static void listAdd(PagerLruList *pList, PagerLruLink *pLink, PgHdr *pPg){
  pLink->pNext = 0;
  pLink->pPrev = pList->pLast;

#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
  assert(pLink==&pPg->free || pLink==&pPg->gfree);
  assert(pLink==&pPg->gfree || pList!=&sqlite3LruPageList);
#endif

  if( pList->pLast ){
    int iOff = (char *)pLink - (char *)pPg;
    PagerLruLink *pLastLink = (PagerLruLink *)(&((u8 *)pList->pLast)[iOff]);
    pLastLink->pNext = pPg;
  }else{
    assert(!pList->pFirst);
................................................................................

  pList->pLast = pPg;
  if( !pList->pFirstSynced && pPg->needSync==0 ){
    pList->pFirstSynced = pPg;
  }
}

/*
** Remove pPg from the list managed by the structure pointed to by pList.
**
** Argument pLink should point to either pPg->free or pPg->gfree, depending 
** on whether pPg is being added to the pager-specific or global LRU list.
*/
static void listRemove(PagerLruList *pList, PagerLruLink *pLink, PgHdr *pPg){
  int iOff = (char *)pLink - (char *)pPg;

#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
  assert(pLink==&pPg->free || pLink==&pPg->gfree);
  assert(pLink==&pPg->gfree || pList!=&sqlite3LruPageList);
#endif

  if( pPg==pList->pFirst ){
    pList->pFirst = pLink->pNext;
  }
  if( pPg==pList->pLast ){
    pList->pLast = pLink->pPrev;
  }
................................................................................
    pList->pFirstSynced = p;
  }

  pLink->pNext = pLink->pPrev = 0;
}

/* 
** Add page pPg to the list of free pages for the pager. If 
** memory-management is enabled, also add the page to the global 
** list of free pages.
*/
static void lruListAdd(PgHdr *pPg){
  listAdd(&pPg->pPager->lru, &pPg->free, pPg);
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
  if( !pPg->pPager->memDb ){
    sqlite3_mutex_enter(sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU));
    listAdd(&sqlite3LruPageList, &pPg->gfree, pPg);
    sqlite3_mutex_leave(sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU));
  }
#endif
}

/* 
** Remove page pPg from the list of free pages for the associated pager.
** If memory-management is enabled, also remove pPg from the global list
** of free pages.
*/
static void lruListRemove(PgHdr *pPg){
  listRemove(&pPg->pPager->lru, &pPg->free, pPg);
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
  if( !pPg->pPager->memDb ){
    sqlite3_mutex_enter(sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU));
    listRemove(&sqlite3LruPageList, &pPg->gfree, pPg);
    sqlite3_mutex_leave(sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU));
  }
#endif
}

/* 
** This function is called just after the needSync flag has been cleared
** from all pages managed by pPager (usually because the journal file
** has just been synced). It updates the pPager->lru.pFirstSynced variable
** and, if memory-management is enabled, the sqlite3LruPageList.pFirstSynced
** variable also.
*/
static void lruListSetFirstSynced(Pager *pPager){
  pPager->lru.pFirstSynced = pPager->lru.pFirst;
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
  if( !pPager->memDb ){
    PgHdr *p;
    sqlite3_mutex_enter(sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU));
................................................................................
      pPg = sqlite3LruPageList.pFirst;
      while( pPg && pPg->pPager->iInUseDB ){
        pPg = pPg->gfree.pNext;
      }
    }
    sqlite3_mutex_leave(sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU));

    /* If pPg==0, then the block above has failed to find a page to
    ** recycle. In this case return early - no further memory will
    ** be released.
    */
    if( !pPg ) break;

    pPager = pPg->pPager;
    assert(!pPg->needSync || pPg==pPager->lru.pFirst);
    assert(pPg->needSync || pPg==pPager->lru.pFirstSynced);
  
    rc = pager_recycle(pPager, 1, &pRecycled);
................................................................................
          sizeof(*pPg) + pPager->pageSize
          + sizeof(u32) + pPager->nExtra
          + MEMDB*sizeof(PgHistory) 
      );
      IOTRACE(("PGFREE %p %d *\n", pPager, pPg->pgno));
      PAGER_INCR(sqlite3_pager_pgfree_count);
      sqlite3_free(pPg);
      pPager->nPage--;
    }else{
      /* An error occured whilst writing to the database file or 
      ** journal in pager_recycle(). The error is not returned to the 
      ** caller of this function. Instead, set the Pager.errCode variable.
      ** The error will be returned to the user (or users, in the case 
      ** of a shared pager cache) of the pager for which the error occured.
      */

#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# This file contains test cases focused on the two memory-management APIs, 
# sqlite3_soft_heap_limit() and sqlite3_release_memory().
#
# $Id: malloc5.test,v 1.13 2007/08/22 22:04:37 drh Exp $

#---------------------------------------------------------------------------
# NOTES ON EXPECTED BEHAVIOUR
#
#---------------------------------------------------------------------------


................................................................................
    INSERT INTO abc SELECT * FROM abc;
    INSERT INTO abc SELECT * FROM abc;
    INSERT INTO abc SELECT * FROM abc;
    INSERT INTO abc SELECT * FROM abc;
  }
  sqlite3_release_memory
} 0
do_test malloc5-5.1 {
  sqlite3_soft_heap_limit 5000
  execsql {
    COMMIT;
    PRAGMA temp_store = memory;
    SELECT * FROM abc ORDER BY a;
  }
  expr 1
} {1}





















































































































sqlite3_soft_heap_limit $::soft_limit
finish_test
catch {db close}

#    May you share freely, never taking more than you give.
#
#***********************************************************************
#
# This file contains test cases focused on the two memory-management APIs, 
# sqlite3_soft_heap_limit() and sqlite3_release_memory().
#
# $Id: malloc5.test,v 1.14 2007/08/28 08:00:18 danielk1977 Exp $

#---------------------------------------------------------------------------
# NOTES ON EXPECTED BEHAVIOUR
#
#---------------------------------------------------------------------------


................................................................................
    INSERT INTO abc SELECT * FROM abc;
    INSERT INTO abc SELECT * FROM abc;
    INSERT INTO abc SELECT * FROM abc;
    INSERT INTO abc SELECT * FROM abc;
  }
  sqlite3_release_memory
} 0
do_test malloc5-5.2 {
  sqlite3_soft_heap_limit 5000
  execsql {
    COMMIT;
    PRAGMA temp_store = memory;
    SELECT * FROM abc ORDER BY a;
  }
  expr 1
} {1}
sqlite3_soft_heap_limit $::soft_limit

#-------------------------------------------------------------------------
# The following test cases (malloc5-6.*) test the new global LRU list
# used to determine the pages to recycle when sqlite3_release_memory is
# called and there is more than one pager open.
#
proc nPage {db} {
  set bt [btree_from_db $db]
  array set stats [btree_pager_stats $bt]
  set stats(page)
}
db close
file delete -force test.db test.db-journal test2.db test2.db-journal

# This block of test-cases (malloc5-6.1.*) prepares two database files
# for the subsequent tests.
do_test malloc5-6.1.1 {
  sqlite3 db test.db
  execsql {
    PRAGMA page_size=1024;
    PRAGMA default_cache_size=10;
    BEGIN;
    CREATE TABLE abc(a PRIMARY KEY, b, c);
    INSERT INTO abc VALUES(randstr(50,50), randstr(75,75), randstr(100,100));
    INSERT INTO abc 
        SELECT randstr(50,50), randstr(75,75), randstr(100,100) FROM abc;
    INSERT INTO abc 
        SELECT randstr(50,50), randstr(75,75), randstr(100,100) FROM abc;
    INSERT INTO abc 
        SELECT randstr(50,50), randstr(75,75), randstr(100,100) FROM abc;
    INSERT INTO abc 
        SELECT randstr(50,50), randstr(75,75), randstr(100,100) FROM abc;
    INSERT INTO abc 
        SELECT randstr(50,50), randstr(75,75), randstr(100,100) FROM abc;
    INSERT INTO abc 
        SELECT randstr(50,50), randstr(75,75), randstr(100,100) FROM abc;
    COMMIT;
  } 
  copy_file test.db test2.db
  sqlite3 db2 test2.db
  list [expr [file size test.db]/1024] [expr [file size test2.db]/1024]
} {23 23}
do_test malloc5-6.1.2 {
  list [execsql {PRAGMA cache_size}] [execsql {PRAGMA cache_size} db2]
} {10 10}

do_test malloc5-6.2.1 {
  execsql { SELECT * FROM abc } db2
  execsql {SELECT * FROM abc} db
  list [nPage db] [nPage db2]
} {10 10}
do_test malloc5-6.2.2 {
  # If we now try to reclaim some memory, it should come from the db2 cache.
  sqlite3_release_memory 3000
  list [nPage db] [nPage db2]
} {10 7}
do_test malloc5-6.2.3 {
  # Access the db2 cache again, so that all the db2 pages have been used
  # more recently than all the db pages. Then try to reclaim 3000 bytes.
  # This time, 3 pages should be pulled from the db cache.
  execsql { SELECT * FROM abc } db2
  sqlite3_release_memory 3000
  list [nPage db] [nPage db2]
} {7 10}


do_test malloc5-6.3.1 {
  # Now open a transaction and update 2 pages in the db2 cache. Then
  # do a SELECT on the db cache so that all the db pages are more recently
  # used than the db2 pages. When we try to free memory, SQLite should
  # free the non-dirty db2 pages, then the db pages, then finally use
  # sync() to free up the dirty db2 pages. The only page that cannot be
  # freed is page1 of db2. Because there is an open transaction, the
  # btree layer holds a reference to page 1 in the db2 cache.
  execsql {
    BEGIN;
    UPDATE abc SET c = randstr(100,100) 
    WHERE rowid = 1 OR rowid = (SELECT max(rowid) FROM abc);
  } db2
  execsql { SELECT * FROM abc } db
  list [nPage db] [nPage db2]
} {10 10}
do_test malloc5-6.3.2 {
  # Try to release 7700 bytes. This should release all the 
  # non-dirty pages held by db2.
  sqlite3_release_memory [expr 7*1100]
  list [nPage db] [nPage db2]
} {10 3}
do_test malloc5-6.3.3 {
  # Try to release another 1000 bytes. This should come fromt the db
  # cache, since all three pages held by db2 are either in-use or diry.
  sqlite3_release_memory 1000
  list [nPage db] [nPage db2]
} {9 3}
do_test malloc5-6.3.4 {
  # Now release 9900 more (about 9 pages worth). This should expunge
  # the rest of the db cache. But the db2 cache remains intact, because
  # SQLite tries to avoid calling sync().
  sqlite3_release_memory 9900
  list [nPage db] [nPage db2]
} {0 3}
do_test malloc5-6.3.5 {
  # But if we are really insistent, SQLite will consent to call sync()
  # if there is no other option.
  sqlite3_release_memory 1000
  list [nPage db] [nPage db2]
} {0 2}
do_test malloc5-6.3.6 {
  # The referenced page (page 1 of the db2 cache) will not be freed no
  # matter how much memory we ask for:
  sqlite3_release_memory 31459
  list [nPage db] [nPage db2]
} {0 1}

db2 close

sqlite3_soft_heap_limit $::soft_limit
finish_test
catch {db close}