SQLite

**    May you find forgiveness for yourself and forgive others.
**    May you share freely, never taking more than you give.
**
*************************************************************************
** This file contains the C functions that implement mutexes for
** use by the SQLite core.
**
** $Id: mutex.c,v 1.14 2007/08/27 17:27:49 danielk1977 Exp $
*/
/*
** If SQLITE_MUTEX_APPDEF is defined, then this whole module is
** omitted and equivalent functionality must be provided by the
** application that links against the SQLite library.
*/
#ifndef SQLITE_MUTEX_APPDEF

** <ul>
** <li>  SQLITE_MUTEX_FAST
** <li>  SQLITE_MUTEX_RECURSIVE
** <li>  SQLITE_MUTEX_STATIC_MASTER
** <li>  SQLITE_MUTEX_STATIC_MEM
** <li>  SQLITE_MUTEX_STATIC_MEM2
** <li>  SQLITE_MUTEX_STATIC_PRNG
** <li>  SQLITE_MUTEX_STATIC_LRU
** </ul>
**
** The first two constants cause sqlite3_mutex_alloc() to create
** a new mutex.  The new mutex is recursive when SQLITE_MUTEX_RECURSIVE
** is used but not necessarily so when SQLITE_MUTEX_FAST is used.
** The mutex implementation does not need to make a distinction
** between SQLITE_MUTEX_RECURSIVE and SQLITE_MUTEX_FAST if it does

** or SQLITE_MUTEX_RECURSIVE) is used then sqlite3_mutex_alloc()
** returns a different mutex on every call.  But for the static 
** mutex types, the same mutex is returned on every call that has
** the same type number.
*/
sqlite3_mutex *sqlite3_mutex_alloc(int iType){
  static sqlite3_mutex staticMutexes[] = {
    { PTHREAD_MUTEX_INITIALIZER, },
    { PTHREAD_MUTEX_INITIALIZER, },
    { PTHREAD_MUTEX_INITIALIZER, },
    { PTHREAD_MUTEX_INITIALIZER, },
    { PTHREAD_MUTEX_INITIALIZER, },
  };
  sqlite3_mutex *p;
  switch( iType ){

      if( p ){
        p->id = iType;
        InitializeCriticalSection(&p->mutex);
      }
      break;
    }
    default: {
      static sqlite3_mutex staticMutexes[5];
      static int isInit = 0;
      while( !isInit ){
        static long lock = 0;
        if( InterlockedIncrement(&lock)==1 ){
          int i;
          for(i=0; i<sizeof(staticMutexes)/sizeof(staticMutexes[0]); i++){
            InitializeCriticalSection(&staticMutexes[i].mutex);

** 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;
};

/*
** Each in-memory image of a page begins with the following header.
** This header is only visible to this pager module.  The client
** code that calls pager sees only the data that follows the header.
**
** Client code should call sqlite3PagerWrite() on a page prior to making
** any modifications to that page.  The first time sqlite3PagerWrite()

**     This flag means (when true) that the content of the page has
**     not yet been loaded from disk.  The in-memory content is just
**     garbage.  (Actually, we zero the content, but you should not
**     make any assumptions about the content nevertheless.)  If the
**     content is needed in the future, it should be read from the
**     original database file.
*/

struct PgHdr {
  Pager *pPager;                 /* The pager to which this page belongs */
  Pgno pgno;                     /* The page number for this page */
  PgHdr *pNextHash, *pPrevHash;  /* Hash collision chain for PgHdr.pgno */
  PagerLruLink free;             /* Next and previous free pages */
  PgHdr *pNextAll;               /* A list of all pages */
  u8 inJournal;                  /* TRUE if has been written to journal */
  u8 dirty;                      /* TRUE if we need to write back changes */
  u8 needSync;                   /* Sync journal before writing this page */
  u8 alwaysRollback;             /* Disable DontRollback() for this page */
  u8 needRead;                   /* Read content if PagerWrite() is called */
  short int nRef;                /* Number of users of this page */
  PgHdr *pDirty, *pPrevDirty;    /* Dirty pages */
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
  PagerLruLink gfree;            /* Global list of nRef==0 pages */
#endif
  u32 notUsed;                   /* Buffer space */
#ifdef SQLITE_CHECK_PAGES
  u32 pageHash;
#endif
  /* pPager->pageSize bytes of page data follow this header */
  /* Pager.nExtra bytes of local data follow the page data */
};

** and back again.
*/
#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

  u8 *aInStmt;                /* One bit for each page in the database */
  char *zFilename;            /* Name of the database file */
  char *zJournal;             /* Name of the journal file */
  char *zDirectory;           /* Directory hold database and journal files */
  sqlite3_file *fd, *jfd;     /* File descriptors for database and journal */
  sqlite3_file *stfd;         /* File descriptor for the statement subjournal*/
  BusyHandler *pBusyHandler;  /* Pointer to sqlite.busyHandler */
  PagerLruList lru;           /* LRU list of free pages */

  PgHdr *pAll;                /* List of all pages */
  PgHdr *pStmt;               /* List of pages in the statement subjournal */
  PgHdr *pDirty;              /* List of all dirty pages */
  i64 journalOff;             /* Current byte offset in the journal file */
  i64 journalHdr;             /* Byte offset to previous journal header */
  i64 stmtHdrOff;             /* First journal header written this statement */
  i64 stmtCksum;              /* cksumInit when statement was started */

** The following variable points to the head of a double-linked list
** of all pagers that are eligible for page stealing by the
** sqlite3_release_memory() interface.  Access to this list is
** protected by the SQLITE_MUTEX_STATIC_MEM2 mutex.
*/
#ifdef SQLITE_ENABLE_MEMORY_MANAGEMENT
static Pager *sqlite3PagerList = 0;
static PagerLruList sqlite3LruPageList = {0, 0, 0};
#endif


/*
** Journal files begin with the following magic string.  The data
** was obtained from /dev/random.  It is used only as a sanity check.
**

    );
    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->pFirst = pPg;
  }

  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;
  }
  if( pLink->pPrev ){
    PagerLruLink *pPrevLink = (PagerLruLink *)(&((u8 *)pLink->pPrev)[iOff]);
    pPrevLink->pNext = pLink->pNext;
  }
  if( pLink->pNext ){
    PagerLruLink *pNextLink = (PagerLruLink *)(&((u8 *)pLink->pNext)[iOff]);
    pNextLink->pPrev = pLink->pPrev;
  }
  if( pPg==pList->pFirstSynced ){
    PgHdr *p = pLink->pNext;
    while( p && p->needSync ){
      PagerLruLink *pL = (PagerLruLink *)(&((u8 *)p)[iOff]);
      p = pL->pNext;
    }
    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));
    for(p=sqlite3LruPageList.pFirst; p && p->needSync; p=p->gfree.pNext);
    assert(p==pPager->lru.pFirstSynced || p==sqlite3LruPageList.pFirstSynced);
    sqlite3LruPageList.pFirstSynced = p;
    sqlite3_mutex_leave(sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU));
  }
#endif
}

/*
** Return true if page *pPg has already been written to the statement
** journal (or statement snapshot has been created, if *pPg is part
** of an in-memory database).
*/
static int pageInStatement(PgHdr *pPg){

static void pager_reset(Pager *pPager){
  PgHdr *pPg, *pNext;
  if( pPager->errCode ) return;
  for(pPg=pPager->pAll; pPg; pPg=pNext){
    IOTRACE(("PGFREE %p %d\n", pPager, pPg->pgno));
    PAGER_INCR(sqlite3_pager_pgfree_count);
    pNext = pPg->pNextAll;
    lruListRemove(pPg);
    sqlite3_free(pPg);
  }
  assert(pPager->lru.pFirst==0);
  assert(pPager->lru.pFirstSynced==0);
  assert(pPager->lru.pLast==0);
  pPager->pStmt = 0;
  pPager->pAll = 0;
  pPager->nHash = 0;
  sqlite3_free(pPager->aHash);
  pPager->nPage = 0;
  pPager->aHash = 0;
  pPager->nRef = 0;
}

    pPager->state = PAGER_SHARED;
  }else if( pPager->state==PAGER_SYNCED ){
    pPager->state = PAGER_EXCLUSIVE;
  }
  pPager->origDbSize = 0;
  pPager->setMaster = 0;
  pPager->needSync = 0;
  lruListSetFirstSynced(pPager);
  pPager->dbSize = -1;

  return (rc==SQLITE_OK?rc2:rc);
}

/*
** Compute and return a checksum for the page of data.

/*
** Unlink a page from the free list (the list of all pages where nRef==0)
** and from its hash collision chain.
*/
static void unlinkPage(PgHdr *pPg){
  Pager *pPager = pPg->pPager;








  /* Unlink from free page list */
  lruListRemove(pPg);













  /* Unlink from the pgno hash table */
  unlinkHashChain(pPager, pPg);
}

/*
** This routine is used to truncate the cache when a database

** For non-test systems, page_ref() is a macro that calls _page_ref()
** online of the reference count is zero.  For test systems, page_ref()
** is a real function so that we can set breakpoints and trace it.
*/
static void _page_ref(PgHdr *pPg){
  if( pPg->nRef==0 ){
    /* The page is currently on the freelist.  Remove it. */





    lruListRemove(pPg);









    pPg->pPager->nRef++;
  }
  pPg->nRef++;
  REFINFO(pPg);
}
#ifdef SQLITE_DEBUG
  static void page_ref(PgHdr *pPg){

    pPager->needSync = 0;

    /* Erase the needSync flag from every page.
    */
    for(pPg=pPager->pAll; pPg; pPg=pPg->pNextAll){
      pPg->needSync = 0;
    }
    lruListSetFirstSynced(pPager);
  }

#ifndef NDEBUG
  /* If the Pager.needSync flag is clear then the PgHdr.needSync
  ** flag must also be clear for all pages.  Verify that this
  ** invariant is true.
  */
  else{
    for(pPg=pPager->pAll; pPg; pPg=pPg->pNextAll){
      assert( pPg->needSync==0 );
    }
    assert( pPager->lru.pFirstSynced==pPager->lru.pFirst );
  }
#endif

  return rc;
}

/*

  *ppPg = 0;

  assert(!MEMDB);

  /* Find a page to recycle.  Try to locate a page that does not
  ** require us to do an fsync() on the journal.
  */
  pPg = pPager->lru.pFirstSynced;

  /* If we could not find a page that does not require an fsync()
  ** on the journal file then fsync the journal file.  This is a
  ** very slow operation, so we work hard to avoid it.  But sometimes
  ** it can't be helped.
  */
  if( pPg==0 && pPager->lru.pFirst && syncOk && !MEMDB){
    int iDc = sqlite3OsDeviceCharacteristics(pPager->fd);
    int rc = syncJournal(pPager);
    if( rc!=0 ){
      return rc;
    }
    if( pPager->fullSync && 0==(iDc&SQLITE_IOCAP_SAFE_APPEND) ){
      /* If in full-sync mode, write a new journal header into the
      ** journal file. This is done to avoid ever modifying a journal
      ** header that is involved in the rollback of pages that have
      ** already been written to the database (in case the header is
      ** trashed when the nRec field is updated).
      */
      pPager->nRec = 0;
      assert( pPager->journalOff > 0 );
      assert( pPager->doNotSync==0 );
      rc = writeJournalHdr(pPager);
      if( rc!=0 ){
        return rc;
      }
    }
    pPg = pPager->lru.pFirst;
  }
  if( pPg==0 ){
    return SQLITE_OK;
  }

  assert( pPg->nRef==0 );

** been released, the function returns. The return value is the total number 
** of bytes of memory released.
*/
int sqlite3PagerReleaseMemory(int nReq){
  int nReleased = 0;          /* Bytes of memory released so far */
  sqlite3_mutex *mutex;       /* The MEM2 mutex */
  Pager *pPager;              /* For looping over pagers */
  int rc = SQLITE_OK;

  /* Acquire the memory-management mutex
  */
  mutex = sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_MEM2);
  sqlite3_mutex_enter(mutex);

  /* Signal all database connections that memory management wants
  ** to have access to the pagers.
  */
  for(pPager=sqlite3PagerList; pPager; pPager=pPager->pNext){
     pPager->iInUseMM = 1;
  }

  while( rc==SQLITE_OK && (nReq<0 || nReleased<nReq) ){
    PgHdr *pPg;
    PgHdr *pRecycled;
 
    /* Try to find a page to recycle that does not require a sync(). If

    ** this is not possible, find one that does require a sync().

    */

    sqlite3_mutex_enter(sqlite3_mutex_alloc(SQLITE_MUTEX_STATIC_LRU));
    pPg = sqlite3LruPageList.pFirstSynced;
    while( pPg && (pPg->needSync || pPg->pPager->iInUseDB) ){
      pPg = pPg->gfree.pNext;
    }

    if( !pPg ){
      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);
    assert(pRecycled==pPg || rc!=SQLITE_OK);

    if( rc==SQLITE_OK ){
      /* We've found a page to free. At this point the page has been 
      ** removed from the page hash-table, free-list and synced-list 
      ** (pFirstSynced). It is still in the all pages (pAll) list. 
      ** Remove it from this list before freeing.
      **
      ** Todo: Check the Pager.pStmt list to make sure this is Ok. It 
      ** probably is though.
      */
      PgHdr *pTmp;
      assert( pPg );
      if( pPg==pPager->pAll ){
         pPager->pAll = pPg->pNextAll;
      }else{
        for( pTmp=pPager->pAll; pTmp->pNextAll!=pPg; pTmp=pTmp->pNextAll ){}
        pTmp->pNextAll = pPg->pNextAll;
      }
      nReleased += (
          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.
      */
      assert(
          (rc&0xff)==SQLITE_IOERR ||
          rc==SQLITE_FULL ||
          rc==SQLITE_BUSY
      );
      assert( pPager->state>=PAGER_RESERVED );
      pager_error(pPager, rc);

    }
  }

  /* Clear the memory management flags and release the mutex
  */
  for(pPager=sqlite3PagerList; pPager; pPager=pPager->pNext){
     pPager->iInUseMM = 0;

static int pagerAllocatePage(Pager *pPager, PgHdr **ppPg){
  int rc = SQLITE_OK;
  PgHdr *pPg;

  /* Create a new PgHdr if any of the four conditions defined 
  ** above are met: */
  if( pPager->nPage<pPager->mxPage
   || pPager->lru.pFirst==0 
   || MEMDB
   || (pPager->lru.pFirstSynced==0 && pPager->doNotSync)
  ){
    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;

  CHECK_PAGE(pPg);

  /* When the number of references to a page reach 0, call the
  ** destructor and add the page to the freelist.
  */
  if( pPg->nRef==0 ){
    Pager *pPager = pPg->pPager;










    lruListAdd(pPg);

    if( pPager->xDestructor ){
      pPager->xDestructor(pPg, pPager->pageSize);
    }
  
    /* When all pages reach the freelist, drop the read lock from
    ** the database file.
    */

** on how SQLite interfaces are suppose to operate.
**
** The name of this file under configuration management is "sqlite.h.in".
** The makefile makes some minor changes to this file (such as inserting
** the version number) and changes its name to "sqlite3.h" as
** part of the build process.
**
** @(#) $Id: sqlite.h.in,v 1.243 2007/08/27 17:27:49 danielk1977 Exp $
*/
#ifndef _SQLITE3_H_
#define _SQLITE3_H_
#include <stdarg.h>     /* Needed for the definition of va_list */

/*
** Make sure we can call this stuff from C++.

** <ul>
** <li>  SQLITE_MUTEX_FAST
** <li>  SQLITE_MUTEX_RECURSIVE
** <li>  SQLITE_MUTEX_STATIC_MASTER
** <li>  SQLITE_MUTEX_STATIC_MEM
** <li>  SQLITE_MUTEX_STATIC_MEM2
** <li>  SQLITE_MUTEX_STATIC_PRNG
** <li>  SQLITE_MUTEX_STATIC_LRU
** </ul>
**
** The first two constants cause sqlite3_mutex_alloc() to create
** a new mutex.  The new mutex is recursive when SQLITE_MUTEX_RECURSIVE
** is used but not necessarily so when SQLITE_MUTEX_FAST is used.
** The mutex implementation does not need to make a distinction
** between SQLITE_MUTEX_RECURSIVE and SQLITE_MUTEX_FAST if it does

*/
#define SQLITE_MUTEX_FAST             0
#define SQLITE_MUTEX_RECURSIVE        1
#define SQLITE_MUTEX_STATIC_MASTER    2
#define SQLITE_MUTEX_STATIC_MEM       3  /* sqlite3_malloc() */
#define SQLITE_MUTEX_STATIC_MEM2      4  /* sqlite3_release_memory() */
#define SQLITE_MUTEX_STATIC_PRNG      5  /* sqlite3_random() */
#define SQLITE_MUTEX_STATIC_LRU       6  /* lru page list */


/*
** Undo the hack that converts floating point types to integer for
** builds on processors without floating point support.
*/
#ifdef SQLITE_OMIT_FLOATING_POINT