SQLite

/*
** 2004 April 6
**
** The author disclaims copyright to this source code.  In place of
** a legal notice, here is a blessing:
**
**    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: btree.c,v 1.350 2007/04/02 05:07:47 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.

/* Forward declaration required by autoVacuumCommit(). */
static int allocateBtreePage(BtShared *, MemPage **, Pgno *, Pgno, u8);

/*
** This routine is called prior to sqlite3PagerCommit when a transaction
** is commited for an auto-vacuum database.
**
** If SQLITE_OK is returned, then *pnTrunc is set to the number of pages
** the database file should be truncated to during the commit process. 
** i.e. the database has been reorganized so that only the first *pnTrunc
** pages are in use.
*/
static int autoVacuumCommit(BtShared *pBt, Pgno *pnTrunc){
  Pager *pPager = pBt->pPager;
  Pgno nFreeList;            /* Number of pages remaining on the free-list. */
  int nPtrMap;               /* Number of pointer-map pages deallocated */
  Pgno origSize;             /* Pages in the database file */
  Pgno finSize;              /* Pages in the database file after truncation */
  int rc;                    /* Return code */
  u8 eType;

  }

  /* Figure out how many free-pages are in the database. If there are no
  ** free pages, then auto-vacuum is a no-op.
  */
  nFreeList = get4byte(&pBt->pPage1->aData[36]);
  if( nFreeList==0 ){
    *pnTrunc = 0;
    return SQLITE_OK;
  }

  /* This block figures out how many pages there are in the database
  ** now (variable origSize), and how many there will be after the
  ** truncation (variable finSize).
  **

  ** truncate the database file to finSize pages and consider the
  ** free-list empty.
  */
  rc = sqlite3PagerWrite(pBt->pPage1->pDbPage);
  if( rc!=SQLITE_OK ) goto autovacuum_out;
  put4byte(&pBt->pPage1->aData[32], 0);
  put4byte(&pBt->pPage1->aData[36], 0);
  *pnTrunc = finSize;
  assert( finSize!=PENDING_BYTE_PAGE(pBt) );

autovacuum_out:
  assert( nRef==sqlite3PagerRefcount(pPager) );
  if( rc!=SQLITE_OK ){
    sqlite3PagerRollback(pPager);
  }

** 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.314 2007/04/02 05:07:47 danielk1977 Exp $
*/
#ifndef SQLITE_OMIT_DISKIO
#include "sqliteInt.h"
#include "os.h"
#include "pager.h"
#include <assert.h>
#include <string.h>

}

/*
** Sort the list of pages in accending order by pgno.  Pages are
** connected by pDirty pointers.  The pPrevDirty pointers are
** corrupted by this sort.
*/
#define N_SORT_BUCKET_ALLOC 25
#define N_SORT_BUCKET       25
#ifdef SQLITE_TEST
  int sqlite3_pager_n_sort_bucket = 0;
  #undef N_SORT_BUCKET
  #define N_SORT_BUCKET \
   (sqlite3_pager_n_sort_bucket?sqlite3_pager_n_sort_bucket:N_SORT_BUCKET_ALLOC)
#endif
static PgHdr *sort_pagelist(PgHdr *pIn){
  PgHdr *a[N_SORT_BUCKET_ALLOC], *p;
  int i;
  memset(a, 0, sizeof(a));
  while( pIn ){
    p = pIn;
    pIn = p->pDirty;
    p->pDirty = 0;
    for(i=0; i<N_SORT_BUCKET-1; i++){
      if( a[i]==0 ){
        a[i] = p;
        break;
      }else{
        p = merge_pagelist(a[i], p);
        a[i] = 0;
      }
    }
    if( i==N_SORT_BUCKET-1 ){
      /* Coverage: To get here, there need to be 2^(N_SORT_BUCKET) 
      ** elements in the input list. This is possible, but impractical.
      ** Testing this line is the point of global variable
      ** sqlite3_pager_n_sort_bucket.
      */
      a[i] = merge_pagelist(a[i], p);
    }
  }
  p = a[0];
  for(i=1; i<N_SORT_BUCKET; i++){
    p = merge_pagelist(p, a[i]);
  }

    IOTRACE(("ALWAYS_ROLLBACK %p\n", pPager))
    pPager->alwaysRollback = 1;
  }

  /* Unlink the old page from the free list and the hash table
  */
  unlinkPage(pPg);
  if( pPg && pPg->pgno!=0 ){
    TEST_INCR(pPager->nOvfl);
  }

  *ppPg = pPg;
  return SQLITE_OK;
}

/*
** This function is called to free superfluous dynamically allocated memory

        }
        assert(pPager->state==PAGER_SHARED || 
            (pPager->exclusiveMode && pPager->state>PAGER_SHARED)
        );
      }

      if( pPager->pAll ){
        /* The shared-lock has just been acquired on the database file
        ** and there are already pages in the cache (from a previous
        ** read or write transaction). If the value of the change-counter
        ** stored in Pager.iChangeCount matches that found on page 1 of
        ** the database file, then no database changes have occured since
        ** the cache was last valid and it is safe to retain the cached
        ** pages. Otherwise, if Pager.iChangeCount does not match the
        ** change-counter on page 1 of the file, the current cache contents
        ** must be discarded.
        */

        PgHdr *pPage1 = pager_lookup(pPager, 1);
        if( pPage1 ){
          unlinkPage(pPage1);

          assert( pPager->pFirst==pPager->pFirstSynced );
          pPage1->pNextFree = pPager->pFirst;
          if( pPager->pFirst ){
            pPager->pFirst->pPrevFree = pPage1;
          }else{
            assert( !pPager->pLast );
            pPager->pLast = pPage1;
          }
          pPager->pFirst = pPage1;
          pPager->pFirstSynced = pPage1;

        }

        assert( !pager_lookup(pPager, 1) );
        rc = sqlite3PagerAcquire(pPager, 1, &pPage1, 0);
        if( rc==SQLITE_OK ){
	  /* The change-counter is stored at offset 24. See also
          ** pager_incr_changecounter().

    if( pPager->state==PAGER_UNLOCK ){
      pPager->state = PAGER_SHARED;
    }
  }

  return rc;
}

/*
** Allocate or recycle space for a single page.
*/
static int pagerAllocatePage(Pager *pPager, PgHdr **ppPg){
  int rc = SQLITE_OK;
  PgHdr *pPg;

  if( !(pPager->pFirstSynced && pPager->pFirstSynced->pgno==0) && (
      pPager->nPage<pPager->mxPage || pPager->pFirst==0 || MEMDB ||
      (pPager->pFirstSynced==0 && pPager->doNotSync)
  ) ){
    /* Create a new page */
    if( pPager->nPage>=pPager->nHash ){
      pager_resize_hash_table(pPager,
         pPager->nHash<256 ? 256 : pPager->nHash*2);
      if( pPager->nHash==0 ){
        rc = SQLITE_NOMEM;
        goto pager_allocate_out;
      }
    }
    pPg = sqliteMallocRaw( sizeof(*pPg) + pPager->pageSize
                            + sizeof(u32) + pPager->nExtra
                            + MEMDB*sizeof(PgHistory) );
    if( pPg==0 ){
      rc = SQLITE_NOMEM;
      goto pager_allocate_out;
    }
    memset(pPg, 0, sizeof(*pPg));
    if( MEMDB ){
      memset(PGHDR_TO_HIST(pPg, pPager), 0, sizeof(PgHistory));
    }
    pPg->pPager = pPager;
    pPg->pNextAll = pPager->pAll;
    pPager->pAll = pPg;
    pPager->nPage++;
    if( pPager->nPage>pPager->nMaxPage ){
      assert( pPager->nMaxPage==(pPager->nPage-1) );
      pPager->nMaxPage++;
    }
  }else{
    /* Recycle an existing page with a zero ref-count. */
    rc = pager_recycle(pPager, 1, &pPg);
    if( rc!=SQLITE_OK ){
      goto pager_allocate_out;
    }
    assert( pPager->state>=SHARED_LOCK );
    assert(pPg);
  }
  *ppPg = pPg;

pager_allocate_out:
  return rc;
}

/*
** Acquire a page.
**
** A read lock on the disk file is obtained when the first page is acquired. 
** This read lock is dropped when the last page is released.
**

  pPg = pager_lookup(pPager, pgno);
  if( pPg==0 ){
    /* The requested page is not in the page cache. */
    int nMax;
    int h;
    TEST_INCR(pPager->nMiss);






























    rc = pagerAllocatePage(pPager, &pPg);
    if( rc!=SQLITE_OK ){
      return rc;
    }



    pPg->pgno = pgno;
    if( pPager->aInJournal && (int)pgno<=pPager->origDbSize ){
      sqlite3CheckMemory(pPager->aInJournal, pgno/8);
      assert( pPager->journalOpen );
      pPg->inJournal = (pPager->aInJournal[pgno/8] & (1<<(pgno&7)))!=0;
      pPg->needSync = 0;
    }else{

**    May you share freely, never taking more than you give.
**
*************************************************************************
** Code for testing the pager.c module in SQLite.  This code
** is not included in the SQLite library.  It is used for automated
** testing of the SQLite library.
**
** $Id: test2.c,v 1.43 2007/04/02 05:07:47 danielk1977 Exp $
*/
#include "sqliteInt.h"
#include "os.h"
#include "pager.h"
#include "tcl.h"
#include <stdlib.h>
#include <string.h>

*/
int Sqlitetest2_Init(Tcl_Interp *interp){
  extern int sqlite3_io_error_persist;
  extern int sqlite3_io_error_pending;
  extern int sqlite3_io_error_hit;
  extern int sqlite3_diskfull_pending;
  extern int sqlite3_diskfull;
  extern int sqlite3_pager_n_sort_bucket;
  static struct {
    char *zName;
    Tcl_CmdProc *xProc;
  } aCmd[] = {
    { "pager_open",              (Tcl_CmdProc*)pager_open          },
    { "pager_close",             (Tcl_CmdProc*)pager_close         },
    { "pager_commit",            (Tcl_CmdProc*)pager_commit        },

     (char*)&sqlite3_diskfull_pending, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_diskfull",
     (char*)&sqlite3_diskfull, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_pending_byte",
     (char*)&sqlite3_pending_byte, TCL_LINK_INT);
  Tcl_LinkVar(interp, "pager_pagesize",
     (char*)&test_pagesize, TCL_LINK_INT);
  Tcl_LinkVar(interp, "sqlite_pager_n_sort_bucket",
     (char*)&sqlite3_pager_n_sort_bucket, TCL_LINK_INT);
  return TCL_OK;
}

# 2007 March 24
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    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: cache.test,v 1.1 2007/04/02 05:07:48 danielk1977 Exp $

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

ifcapable {!pager_pragmas} {
  finish_test
  return
}

proc pager_cache_size {db} {
  set bt [btree_from_db $db]
  array set stats [btree_pager_stats $bt]
  return $stats(page)
}

do_test cache-1.1 {
  pager_cache_size db
} {0}

do_test cache-1.2 {
  execsql {
    CREATE TABLE abc(a, b, c);
    INSERT INTO abc VALUES(1, 2, 3);
  }
  pager_cache_size db
} {2}

# At one point, repeatedly locking and unlocking the cache was causing
# a resource leak of one page per repetition. The page wasn't actually
# leaked, but would not be reused until the pager-cache was full (i.e. 
# 2000 pages by default).
#
# This tests that once the pager-cache is initialised, it can be locked
# and unlocked repeatedly without internally allocating any new pages.
#
set cache_size [pager_cache_size db]
for {set ii 0} {$ii < 10} {incr ii} {

  do_test cache-1.3.$ii {
    execsql {SELECT * FROM abc}
    pager_cache_size db
  } $::cache_size

}

finish_test

#    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.8 2007/04/02 05:07:48 danielk1977 Exp $

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

  catchsql {
    SELECT * FROM abc;
  } db2
} {0 {}}
do_test malloc5-1.5 {
  # Manipulate the cache so that it contains two unused pages. One requires 
  # a journal-sync to free, the other does not.
  db2 close
  execsql {
    SELECT * FROM abc;
    CREATE TABLE def(d, e, f);
  }
  sqlite3_release_memory 500
} $::pgalloc
do_test malloc5-1.6 {
  # Database should not be locked this time. The above test case only
  # requested 500 bytes of memory, which can be obtained by freeing the page
  # that does not require an fsync().
  sqlite3 db2 test.db
  catchsql {
    SELECT * FROM abc;
  } db2
} {0 {}}
do_test malloc5-1.7 {
  # Release another 500 bytes of memory. This time we require a sync(), 
  # so the database file will be locked afterwards.
  db2 close
  sqlite3_release_memory 500
} $::pgalloc
do_test malloc5-1.8 {
  sqlite3 db2 test.db
  catchsql {
    SELECT * FROM abc;
  } db2
} {1 {database is locked}}
do_test malloc5-1.9 {
  execsql {
    COMMIT;

# 2006 September 4
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    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 regression tests for SQLite library.
#
# $Id: misc7.test,v 1.10 2007/04/02 05:07:48 danielk1977 Exp $

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

do_test misc7-1 {
  c_misuse_test
} {}

} {hello}
do_test misc7-7.2 {
  execsql {
    DETACH aux;
  }
} {}

# Test the UTF-16 version of the "out of memory" message (used when
# malloc fails during sqlite3_open() ).
#
ifcapable utf16 {
  do_test misc7-8 {
    encoding convertfrom unicode [sqlite3_errmsg16 0x00000000]
  } {out of memory}
}

  if {!$rc || ($rc && [string first "columns" $msg]==0)} {
    set msg
  } else {
    error $msg
  }
}

sqlite3 db test.db
set sqlite_pager_n_sort_bucket 4
do_test misc7-17 {
  execsql {
    PRAGMA integrity_check;
    VACUUM;
    PRAGMA integrity_check;
  }
} {ok ok}
set sqlite_pager_n_sort_bucket 0

finish_test

# 2001 September 15
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    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 regression tests for SQLite library.  The
# focus of this script is page cache subsystem.
#
# $Id: pager.test,v 1.27 2007/04/02 05:07:48 danielk1977 Exp $


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

if {[info commands pager_open]!=""} {
db close

  expr {$::g1!=0}
} {1}
do_test pager-2.12 {
  page_number $::g1
} {1}
do_test pager-2.13 {
  pager_stats $::p1
} {ref 1 page 1 max 10 size 0 state 1 err 0 hit 1 miss 2 ovfl 0}
do_test pager-2.14 {
  set v [catch {
    page_write $::g1 "Page-One"
  } msg]
  lappend v $msg
} {0 {}}
do_test pager-2.15 {
  pager_stats $::p1
} {ref 1 page 1 max 10 size 1 state 2 err 0 hit 1 miss 2 ovfl 0}
do_test pager-2.16 {
  page_read $::g1
} {Page-One}
do_test pager-2.17 {
  set v [catch {
    pager_commit $::p1
  } msg]
  lappend v $msg
} {0 {}}
do_test pager-2.20 {
  pager_stats $::p1
} {ref 1 page 1 max 10 size -1 state 1 err 0 hit 2 miss 2 ovfl 0}
do_test pager-2.19 {
  pager_pagecount $::p1
} {1}
do_test pager-2.21 {
  pager_stats $::p1
} {ref 1 page 1 max 10 size 1 state 1 err 0 hit 2 miss 2 ovfl 0}
do_test pager-2.22 {
  page_unref $::g1
} {}
do_test pager-2.23 {
  pager_stats $::p1
} {ref 0 page 1 max 10 size -1 state 0 err 0 hit 2 miss 2 ovfl 0}
do_test pager-2.24 {
  set v [catch {
    page_get $::p1 1
  } ::g1]
  if {$v} {lappend v $::g1}
  set v
} {0}