SQLite4  Check-in [29373a8844]

  void *pVal, int nVal,           /* Expected value */
  int *pRc                        /* IN/OUT: Error code */
){
  if( *pRc==0 ){
    void *pDbVal;
    int nDbVal;
    int rc;

    static int nCall = 0; nCall++;

    rc = tdb_fetch(pDb, pKey, nKey, &pDbVal, &nDbVal);
    testSetError(rc);
    if( rc==0 && (nVal!=nDbVal || (nVal>0 && lsm_memcmp(pVal, pDbVal, nVal))) ){
      testSetError(1);
    }
  }
}

/* Number of elements in an array object. */
#define array_size(x) (sizeof(x)/sizeof(x[0]))

/* Number of read-lock slots in shared memory */
#define BT_NREADER 4

#ifndef MIN
# define MIN(a,b) (((a)<(b))?(a):(b))
#endif
#ifndef MAX
# define MAX(a,b) (((a)>(b))?(a):(b))
#endif


/*************************************************************************
** Interface to bt_pager.c functionality.
*/
typedef struct BtPage BtPage;
typedef struct BtPager BtPager;

int sqlite4BtLogRead(BtLog*, u32 pgno, u8 *aData);
int sqlite4BtLogWrite(BtLog*, u32 pgno, u8 *aData, int bCommit);

int sqlite4BtLogSnapshotOpen(BtLog*);
int sqlite4BtLogSnapshotClose(BtLog*);
int sqlite4BtLogSnapshotWritable(BtLog*);

int sqlite4BtLogSize(BtLog*);
int sqlite4BtLogCheckpoint(BtLog*);

/*
** End of bt_log.c interface.
*************************************************************************/

/*************************************************************************

/*
** 2013 October 18
**
** 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.
**
*************************************************************************
*/



#include "sqliteInt.h"
#include "btInt.h"

#include <string.h>
#include <assert.h>
#include <stdio.h>

#define BT_LOCK_DMS1       0      /* DMS1 */
#define BT_LOCK_DMS2_RW    1      /* DMS2/rw */

    }
  }
  sqlite4_mutex_leave(pShared->pClientMutex);
  
  *ppOut = pOut;
  return rc;
}

int sqlite4BtLockCkpt(BtLock *pLock){
  return btLockLockop(pLock, BT_LOCK_CKPTER, BT_LOCK_EXCL, 0);
}

int sqlite4BtLockCkptUnlock(BtLock *pLock){
  return btLockLockop(pLock, BT_LOCK_CKPTER, BT_LOCK_UNLOCK, 0);
}

  int padding;
  u32 aCksum[2];                  /* Object checksum */
};

/*
** A single instance of this structure follows the two BtShmHdr structures 
** in shared memory.
**
** iWalHdr:
**   This field encodes two pieces of information: the location of the
**   current log file header (slot 0 or slot 1) and the value of the
**   BtWalHdr.iCnt field within it (0, 1 or 2). Encoded as:
**
**           ((iSlot << 2) + iCnt)
**
**   To decode, use:
**
**           iSlot = (ckpthdr.iWalHdr >> 2);
**           iCnt = (ckpthdr.iWalHdr & 0x03);& 0x03);
*/
struct BtCkptHdr {
  u32 iFirstRead;                 /* First uncheckpointed frame */
  u32 iWalHdr;                    /* Description of current wal header */
  u32 iFirstRecover;              /* First recovery frame */
};

struct BtShm {
  BtShmHdr hdr1;
  BtShmHdr hdr2;
  BtCkptHdr ckpt;

** initialize the shared-memory accordingly.
*/
static int btLogRecover(BtLog *pLog){
  bt_env *pVfs = pLog->pLock->pVfs;
  i64 nByte = 0;                  /* Size of log file on disk */
  int rc;                         /* Return code */
  BtWalHdr *pHdr = 0;
  int iSlot = 0;

  /* Read a log file header from the start of the file. */
  rc = pVfs->xSize(pLog->pFd, &nByte);
  if( rc==SQLITE4_OK && nByte>0 ){
    BtWalHdr hdr1;
    rc = btLogReadHeader(pLog, 0, &hdr1);
    if( rc==SQLITE4_OK ){
      BtWalHdr hdr2;
      rc = btLogReadHeader(pLog, hdr1.nSector, &hdr2);
      if( rc==SQLITE4_NOTFOUND ){
        pHdr = &hdr1;
      }else if( rc==SQLITE4_OK ){
        int aGreater[3] = {1, 2, 0};
        pHdr = ((hdr2.iCnt==aGreater[hdr1.iCnt]) ? &hdr2 : &hdr1);
      }
      iSlot = (pHdr==&hdr2);
    }else if( rc==SQLITE4_NOTFOUND ){
      int iOff;
      for(iOff=256; iOff<=65536 && rc==SQLITE4_NOTFOUND; iOff=iOff*2){
        rc = btLogReadHeader(pLog, iOff, &hdr1);
      }
      if( rc==SQLITE4_OK ){
        pHdr = &hdr1;
        iSlot = 1;
      }
    }
    if( rc==SQLITE4_NOTFOUND ) rc = SQLITE4_OK;
  }

  /* If a header was successfully read from the file, scan the log file
  ** and populate the shared-memory hash tables.  */
  if( pHdr ){
    u32 iCommit = 0;
    rc = btLogTraverse(pLog, pHdr, btLogRecoverFrame, (void*)&iCommit);
    if( rc==SQLITE4_OK && iCommit>0 ){
      BtShm *pShm = btLogShm(pLog);
      pShm->ckpt.iFirstRead = 1;
      pShm->ckpt.iWalHdr = (iSlot<<2) + pHdr->iCnt;
      pShm->ckpt.iFirstRecover = 1;
      pLog->snapshot.aLog[4] = 1;
      pLog->snapshot.aLog[5] = iCommit;
      rc = btLogHashRollback(pLog, btLogFrameHash(pLog, iCommit), iCommit);
    }
  }

  return rc;

  zWal = sqlite4BtPagerFilename(pPager, BT_PAGERFILE_LOG);
  rc = pVfs->xOpen(pEnv, pVfs, zWal, 0, &pLog->pFd);

  if( rc==SQLITE4_OK && bRecover ){
    rc = btLogMapShm(pLog, 0);
    if( rc==SQLITE4_OK ){
      BtShm *pShm = btLogShm(pLog);
      memset(pShm, 0, sizeof(BtShm));
      pShm->ckpt.iFirstRead = 1;
      pShm->ckpt.iFirstRecover = 1;
      btLogZeroSnapshot(pLog);
      rc = btLogRecover(pLog);
    }
    if( rc==SQLITE4_OK ){
      rc = btLogUpdateSharedHdr(pLog);
    }
  }

**
** If any other error occurs, an SQLite4 error code is returned. The final
** state of buffer aData[] is undefined in this case.
*/
int sqlite4BtLogRead(BtLog *pLog, u32 pgno, u8 *aData){
  const int pgsz = sqlite4BtPagerPagesize((BtPager*)(pLog->pLock));
  int iHash;
  int iHashLast;
  int rc = SQLITE4_NOTFOUND;
  u32 iFrame = 0;

  iHash = btLogFrameHash(pLog, pLog->snapshot.aLog[5]);
  iHashLast = btLogFrameHash(pLog, pLog->snapshot.aLog[4]);
  for( ; rc==SQLITE4_NOTFOUND && iHash>=iHashLast && iFrame==0; iHash--){
    rc = btLogHashSearch(pLog, iHash, pgno, &iFrame);
  }

  if( rc==SQLITE4_OK && iFrame!=0 ){
    bt_env *pVfs = pLog->pLock->pVfs;
    i64 iOff;
    assert( rc==SQLITE4_OK );

      rc = btLogSnapshot(pLog, &shmhdr);
    }
    if( rc==SQLITE4_OK && memcmp(&shmhdr, &pLog->snapshot, sizeof(BtShmHdr)) ){
      sqlite4BtLockReaderUnlock(pLog->pLock);
      rc = SQLITE4_NOTFOUND;
    }
  }

  if( rc==SQLITE4_OK ){
    BtShm *pShm = btLogShm(pLog);
    u32 iCkpt = pShm->ckpt.iFirstRead;
    if( iCkpt>pLog->snapshot.aLog[4] ){
      pLog->snapshot.aLog[4] = iCkpt;
    }
  }

  return rc;
}

int sqlite4BtLogSnapshotClose(BtLog *pLog){
  sqlite4BtLockReaderUnlock(pLog->pLock);
  return SQLITE4_OK;
}

int sqlite4BtLogSnapshotWritable(BtLog *pLog){
  return 1;
}

static void btLogMergeInplace(
  u32 *aLeft, int nLeft,          /* Left hand input array */
  u32 *aRight, int nRight,        /* Right hand input array */
  u32 *aSpace,                    /* Temporary space */
  int *pnOut                      /* OUT: Size of aLeft[] after merge */
){
  int iLeft = 0;
  int iRight = 0;
  int iOut = 0;

  while( iLeft<nLeft || iRight<nRight ){
    u32 v;
    if( iRight==nRight || (iLeft<nLeft && aLeft[iLeft]<aRight[iRight]) ){
      assert( iLeft<nLeft );
      v = aLeft[iLeft++];
    }else{
      assert( iRight<nRight );
      v = aRight[iRight++];
    }
    if( v && (iOut==0 || v!=aSpace[iOut-1]) ) aSpace[iOut++] = v;
  }

  memcpy(aLeft, aSpace, iOut*sizeof(u32));
  memset(&aLeft[iOut], 0, ((nLeft+nRight)-iOut) * sizeof(u32));
  *pnOut = iOut;
}

static void btLogMergeSort(
  u32 *aPgno,                     /* Array to sort */
  int *pnPgno,                    /* IN/OUT: Number of entries in aPgno[] */
  u32 *aSpace                     /* Temporary space */
){
  int nMerge;
  int nPgno = *pnPgno;

  for(nMerge=1; nMerge<nPgno; nMerge=nMerge*2){
    int iLeft;
    for(iLeft=0; iLeft<nPgno; iLeft+=(nMerge*2)){
      u32 *aLeft = &aPgno[iLeft];
      int nLeft = MIN(nMerge, nPgno-iLeft);
      u32 *aRight = &aPgno[iLeft+nMerge];
      int nRight = MIN(nMerge, nPgno-iLeft-nLeft);
      btLogMergeInplace(aLeft, nLeft, aRight, nRight, aSpace, pnPgno);
    }
  }
}

/*
** Parameters iFirst and iLast are frame numbers for frames that are part 
** of the current log. This function scans the wal-index from iFirst to
** iLast (inclusive) and records the set of page numbers that occur once.
** This set is sorted in ascending order and returned via the output 
** variables *paPgno and *pnPgno.
** 
*/
static int btLogGatherPgno(
  BtLog *pLog,                    /* Log module handle */
  u32 iFirst,                     /* First frame to gather pgnos from */
  u32 iLast,                      /* Last frame to gather pgnos from */
  u32 **paPgno,                   /* OUT: s4_malloc'd array of sorted pgno */
  int *pnPgno                     /* OUT: Number of entries in *paPgno */
){
  u32 i;
  u32 *aPgno;                     /* Returned array */
  u32 *aSpace;                    /* Temporary space used by merge-sort */
  int nMax = (iLast - iFirst) + 1;
  int rc = SQLITE4_OK;

  /* Allocate space to collect all page numbers. */
  aPgno = (u32*)sqlite4_malloc(pLog->pLock->pEnv, sizeof(u32)*nMax*2);
  if( aPgno==0 ) rc = btErrorBkpt(SQLITE4_NOMEM);
  aSpace = &aPgno[nMax];

  /* Copy the required page numbers into the allocated array */
  for(i=iFirst; rc==SQLITE4_OK && i<=iLast; i++){
    u32 *aPage;
    ht_slot *aHash;
    u32 iZero;
    rc = btLogFindHash(pLog, btLogFrameHash(pLog, i), &aHash, &aPage, &iZero);
    if( rc==SQLITE4_OK ){
      aPgno[i-iFirst] = aPage[i-iZero];
    }
  }

  /* Sort the contents of the array in ascending order. This step also 
  ** eliminates any  duplicate page numbers. */
  if( rc==SQLITE4_OK ){
    btLogMergeSort(aPgno, &nMax, aSpace);
    *pnPgno = nMax;
    *paPgno = aPgno;
  }else{
    sqlite4_free(pLog->pLock->pEnv, aPgno);
    *paPgno = 0;
    *pnPgno = 0;
  }

  return rc;
}

/*
** Return the number of frames in the log file according to the current
** snapshot.
*/
int sqlite4BtLogSize(BtLog *pLog){
  return (int)pLog->snapshot.aLog[5] - (int)pLog->snapshot.aLog[4];
}

int sqlite4BtLogCheckpoint(BtLog *pLog){
  BtLock *pLock = pLog->pLock;
  int rc;

  /* Take the CHECKPOINTER lock. */
  rc = sqlite4BtLockCkpt(pLock);
  if( rc==SQLITE4_OK ){
    const int pgsz = sqlite4BtPagerPagesize((BtPager*)pLock);
    bt_env *pVfs = pLock->pVfs;
    bt_file *pFd = pLock->pFd;
    BtShm *pShm;                  /* Pointer to shared-memory region */
    u32 iFirst;                   /* First frame to checkpoint */
    u32 iLast;                    /* Last frame to checkpoint */
    u32 *aPgno = 0;               /* Array of page numbers to checkpoint */
    int nPgno;                    /* Number of entries in aPgno[] */
    int i;                        /* Used to loop through aPgno[] */
    u8 *aBuf;                     /* Buffer to load page data into */

    /* Allocate space to load log data into */
    aBuf = sqlite4_malloc(pLock->pEnv, pgsz);
    if( aBuf==0 ) rc = btErrorBkpt(SQLITE4_NOMEM);
    
    /* Figure out the set of page numbers stored in the part of the log 
    ** file being checkpointed. Remove any duplicates and sort them in 
    ** ascending order.  */
    if( rc==SQLITE4_OK ){
      pShm = btLogShm(pLog);
      iFirst = pShm->ckpt.iFirstRead;
      iLast = pLog->snapshot.aLog[5];
      rc = btLogGatherPgno(pLog, iFirst, iLast, &aPgno, &nPgno);
    }

    /* Copy data from the log file to the database file. */
    for(i=0; rc==SQLITE4_OK && i<nPgno; i++){
      u32 pgno = aPgno[i];
      rc = sqlite4BtLogRead(pLog, pgno, aBuf);
      if( rc==SQLITE4_OK ){
        i64 iOff = (i64)pgsz * (pgno-1);
        rc = pVfs->xWrite(pFd, iOff, aBuf, pgsz);
      }
    }

    /* Update the first field of the checkpoint-header. This tells readers
    ** that they need not consider anything that in the log before this
    ** point (since the data has already been copied into the database
    ** file).  */
    if( rc==SQLITE4_OK ){
      pShm->ckpt.iFirstRead = iLast+1;
      pVfs->xShmBarrier(pLog->pFd);
    }

    /* Write a new header into the log file. This tells any future recovery
    ** where it should start reading the log. Once this new header is synced
    ** to disk, the space cleared by this checkpoint operation can be 
    ** reused.  */
    if( rc==SQLITE4_OK ){
      int iSlot = ((pShm->ckpt.iWalHdr >> 2) + 1) % 2;
      i64 iOff;
      BtWalHdr hdr;
      BtFrameHdr fhdr;

      memset(&hdr, 0, sizeof(BtWalHdr));
      hdr.iMagic = BT_WAL_MAGIC;
      hdr.iVersion = BT_WAL_VERSION;
      hdr.iCnt = (((pShm->ckpt.iWalHdr & 0x03) + 1) % 3);
      hdr.nSector = pLog->snapshot.nSector;
      hdr.nPgsz = pgsz;
      hdr.iFirstFrame = iLast+1;

      iOff = btLogFrameOffset(pLog, pgsz, iLast);
      rc = btLogReadData(pLog, iOff, (u8*)&fhdr, sizeof(BtFrameHdr));
      if( rc==SQLITE4_OK ){
        hdr.iSalt1 = fhdr.aCksum[0];
        hdr.iSalt2 = fhdr.aCksum[1];
        rc = btLogWriteHeader(pLog, iSlot, &hdr);
      }
      if( rc==SQLITE4_OK ){
        pShm->ckpt.iWalHdr = (iSlot<<2) + hdr.iCnt;
      }
    }

    /* Update the second field of the checkpoint header. This tells future
    ** writers that it is now safe to recycle pages before this point
    ** (assuming all live readers are cleared).  */
    if( rc==SQLITE4_OK ){
      pShm->ckpt.iFirstRecover = iLast+1;
      pVfs->xShmBarrier(pLog->pFd);
    }

    /* Free the buffer and drop the checkpointer lock */
    sqlite4_free(pLock->pEnv, aBuf);
    sqlite4BtLockCkptUnlock(pLog->pLock);
  }
  return rc;
}

/*
** Values that make up the single byte flags field at the start of
** b-tree pages. 
*/
#define BT_PGFLAGS_INTERNAL 0x01  /* True for non-leaf nodes */








/* #define BT_STDERR_DEBUG 1 */

struct bt_db {
  sqlite4_env *pEnv;              /* SQLite environment */
  BtPager *pPager;                /* Underlying page-based database */
  bt_cursor *pAllCsr;             /* List of all open cursors */
};

#include <string.h>
#include <assert.h>
#include <stdio.h>

/* By default pages are 1024 bytes in size. */
#define BT_DEFAULT_PGSZ 1024

/* By default auto-checkpoint is 1000 */
#define BT_DEFAULT_AUTOCKPT 1000

typedef struct BtPageHash BtPageHash;
typedef struct BtDbhdr BtDbhdr;

/*
** Hash table for page references currently in memory. Manipulated using
** the following functions:

  u32 pgsz;                       /* Page size in bytes */
  u32 nPg;                        /* Number of pages in database */
  u32 cookie;                     /* User cookie value (SQL schema cookie) */
};

/*
** Pager object.
**
** nAutoCkpt:
**   If a transaction is committed and there are this many frames in the
**   log file, automatically run a checkpoint operation.
*/
struct BtPager {
  BtLock btl;                     /* Variables shared with bt_lock module */
  BtLog *pLog;                    /* Logging module */
  int iTransactionLevel;          /* Current transaction level (see bt.h) */
  char *zFile;                    /* Database file name */
  int nFile;                      /* Length of string zFile in bytes */
  BtPageHash hash;                /* Hash table */
  BtPage *pDirty;                 /* List of all dirty pages */
  int nTotalRef;                  /* Total number of outstanding page refs */
  int nAutoCkpt;                  /* Auto-checkpoint when log is this large */
  int bDoAutoCkpt;                /* Do auto-checkpoint after next unlock */
  BtDbhdr dbhdr;

};


/**************************************************************************
** Interface to BtPageHash object.
*/

  nByte = sizeof(BtPager) + nExtra;
  p = (BtPager*)sqlite4_malloc(pEnv, nByte);
  if( !p ) return btErrorBkpt(SQLITE4_NOMEM); 
  memset(p, 0, nByte);

  p->btl.pEnv = pEnv;
  p->btl.pVfs = sqlite4BtEnvDefault();
  p->nAutoCkpt = BT_DEFAULT_AUTOCKPT;
  *pp = p;
  return SQLITE4_OK;
}

static void btFreePage(BtPager *p, BtPage *pPg){
  if( pPg ){
    sqlite4_free(p->btl.pEnv, pPg->aData);

  assert( p->iTransactionLevel==0 );
  rc = sqlite4BtLogSnapshotClose(p->pLog);

  /* Purge the page cache. */
  assert( p->pDirty==0 );
  btPurgeCache(p);

  if( rc==SQLITE4_OK && p->bDoAutoCkpt ){
    sqlite4BtLogCheckpoint(p->pLog);
  }
  p->bDoAutoCkpt = 0;

  return rc;
}

/*
** Commit the current write transaction to disk.
*/
static int btCommitTransaction(BtPager *p){

    }
  }
  p->pDirty = 0;

  if( rc==SQLITE4_OK ){
    rc = p->btl.pVfs->xWrite(p->btl.pFd, 0, (void*)&p->dbhdr, sizeof(BtDbhdr));
  }

  if( p->nAutoCkpt && sqlite4BtLogSize(p->pLog)>=p->nAutoCkpt ){
    p->bDoAutoCkpt = 1;
  }

  return rc;
}

static int btLoadPageData(BtPager *p, BtPage *pPg){
  int rc;                         /* Return code */

  return p->iTransactionLevel;
}

/*
** Query for the database page size. Requires an open read transaction.
*/
int sqlite4BtPagerPagesize(BtPager *p){
  /* assert( p->iTransactionLevel>=1 && p->btl.pFd ); */
  return (int)p->dbhdr.pgsz;
}


/* 
** Query for the root page number. Requires an open read transaction.
*/
u32 sqlite4BtPagerRootpgno(BtPager *p){
  assert( p->iTransactionLevel>=1 && p->btl.pFd );
  return 2;

  }

  sqlite4_free(pSqlEnv, zCwd);
  *pzOut = zOut;
  return rc;
}

static int btPosixOsUnlink(sqlite4_env *pEnv, bt_env *pVfs, const char *zFile){
  int prc = unlink(zFile);
  return prc ? btErrorBkpt(SQLITE4_IOERR) : SQLITE4_OK;
}

int btPosixOsLock(bt_file *pFile, int iLock, int eType){
  int rc = SQLITE4_OK;
  PosixFile *p = (PosixFile *)pFile;

# Delete all files associated with LSM database $file. That is:
#
#     ${file}
#     ${file}-log
#     ${file}-shm
#
proc db_delete {file} {
  forcedelete $file $file-shm $file-log $file-wal
}

# Create a test database
#
proc reset_db {} {
  catch {db close}
  db_delete test.db