SQLite

** A single WAL file can be used multiple times.  In other words, the
** WAL can fill up with frames and then be checkpointed and then new
** frames can overwrite the old ones.  A WAL always grows from beginning
** toward the end.  Checksums and counters attached to each frame are
** used to determine which frames within the WAL are valid and which
** are leftovers from prior checkpoints.
**
** The WAL header is 24 bytes in size and consists of the following six
** big-endian 32-bit unsigned integer values:
**
**     0: Magic number.  0x377f0682 (big endian)
**     4: File format version.  Currently 3007000
**     8: Database page size.  Example: 1024
**    12: Checkpoint sequence number
**    16: Salt-1, random integer that changes with each checkpoint
**    20: Salt-2, a different random integer changing with salt-1
**
** Immediately following the wal-header are zero or more frames. Each
** frame consists of a 24-byte frame-header followed by a <page-size> bytes
** of page data. The frame-header is broken into 6 big-endian 32-bit unsigned 
** integer values, as follows:
**
**     0: Page number.
**     4: For commit records, the size of the database image in pages 
**        after the commit. For all other records, zero.
**     8: Checkpoint sequence number (copied from the header)
**    12: Salt-1 (copied from the header)
**    16: Checksum-1.
**    20: Checksum-2.
**
** READER ALGORITHM
**
** To read a page from the database (call it page number P), a reader
** first checks the WAL to see if it contains page P.  If so, then the
** last valid instance of page P that is or is followed by a commit frame
** become the value read.  If the WAL contains no copies of page P that

/* Object declarations */
typedef struct WalIndexHdr WalIndexHdr;
typedef struct WalIterator WalIterator;


/*
** The following object stores information from the wal-index header.
**
** This object is *not* a copy of the wal-index header.
**
** Member variables iCheck1 and iCheck2 contain the checksum for the
** last frame written to the wal, or 2 and 3 respectively if the log 
** is currently empty.
*/
struct WalIndexHdr {
  u32 iChange;          /* Counter incremented each transaction */

** do not read or write data from the region of the file on which locks
** are applied.
*/
#define WALINDEX_LOCK_OFFSET   ((sizeof(WalIndexHdr))+2*sizeof(u32))
#define WALINDEX_LOCK_RESERVED 8

/* Size of header before each frame in wal */
#define WAL_FRAME_HDRSIZE 24

/* Size of write ahead log header */
#define WAL_HDRSIZE 24

/*
** Return the offset of frame iFrame in the write-ahead log file, 
** assuming a database page size of szPage bytes. The offset returned
** is to the start of the write-ahead log frame-header.
*/
#define walFrameOffset(iFrame, szPage) (                               \

  volatile u32 *pWiData;     /* Pointer to wal-index content in memory */
  u8 lockState;              /* SQLITE_SHM_xxxx constant showing lock state */
  u8 readerType;             /* SQLITE_SHM_READ or SQLITE_SHM_READ_FULL */
  u8 exclusiveMode;          /* Non-zero if connection is in exclusive mode */
  u8 isWindexOpen;           /* True if ShmOpen() called on pDbFd */
  WalIndexHdr hdr;           /* Wal-index for current snapshot */
  char *zWalName;            /* Name of WAL file */
  u32 nCkpt;                 /* Checkpoint sequence number */
  u32 iSalt1, iSalt2;        /* Two random salt values */
};


/*
** This structure is used to implement an iterator that loops through
** all frames in the WAL in database page order. Where two or more frames
** correspond to the same database page, the iterator visits only the 

}

/*
** This function encodes a single frame header and writes it to a buffer
** supplied by the caller. A frame-header is made up of a series of 
** 4-byte big-endian integers, as follows:
**

**     0: Page number.
**     4: For commit records, the size of the database image in pages 
**        after the commit. For all other records, zero.
**     8: Checkpoint sequence number (copied from the header)
**    12: Salt-1 (copied from the header)
**    16: Checksum-1.
**    20: Checksum-2.
*/
static void walEncodeFrame(
  Wal *pWal,                      /* The write-ahead log */
  u32 *aCksum,                    /* IN/OUT: Checksum values */
  u32 iPage,                      /* Database page number for frame */
  u32 nTruncate,                  /* New db size (or 0 for non-commit frames) */
  int nData,                      /* Database page size (size of aData[]) */
  u8 *aData,                      /* Pointer to page data (for checksum) */
  u8 *aFrame                      /* OUT: Write encoded frame here */
){
  assert( WAL_FRAME_HDRSIZE==24 );

  sqlite3Put4byte(&aFrame[0], iPage);
  sqlite3Put4byte(&aFrame[4], nTruncate);
  sqlite3Put4byte(&aFrame[8], pWal->nCkpt);
  sqlite3Put4byte(&aFrame[12], pWal->iSalt1);

  walChecksumBytes(aFrame, 8, aCksum);
  walChecksumBytes(aData, nData, aCksum);

  sqlite3Put4byte(&aFrame[16], aCksum[0]);
  sqlite3Put4byte(&aFrame[20], aCksum[1]);
}

/*
** Return 1 and populate *piPage, *pnTruncate and aCksum if the 
** frame checksum looks Ok. Otherwise return 0.
*/
static int walDecodeFrame(
  Wal *pWal,                      /* The write-ahead log */
  u32 *aCksum,                    /* IN/OUT: Checksum values */
  u32 *piPage,                    /* OUT: Database page number for frame */
  u32 *pnTruncate,                /* OUT: New db size (or 0 if not commit) */
  int nData,                      /* Database page size (size of aData[]) */
  u8 *aData,                      /* Pointer to page data (for checksum) */
  u8 *aFrame                      /* Frame data */
){
  assert( WAL_FRAME_HDRSIZE==24 );

#if 0
  if( pWal->nCkpt!=sqlite3Get4byte(&aFrame[8]) ){
    return 0;
  }
  if( pWal->iSalt1!=sqlite3Get4byte(&aFrame[12]) ){
    return 0;
  }
#endif

  walChecksumBytes(aFrame, 8, aCksum);
  walChecksumBytes(aData, nData, aCksum);

  if( aCksum[0]!=sqlite3Get4byte(&aFrame[16]) 
   || aCksum[1]!=sqlite3Get4byte(&aFrame[20]) 
  ){
    /* Checksum failed. */
    return 0;
  }

  *piPage = sqlite3Get4byte(&aFrame[0]);
  *pnTruncate = sqlite3Get4byte(&aFrame[4]);

  rc = sqlite3OsFileSize(pWal->pWalFd, &nSize);
  if( rc!=SQLITE_OK ){
    return rc;
  }

  if( nSize>WAL_FRAME_HDRSIZE ){
    u8 aBuf[WAL_HDRSIZE];         /* Buffer to load first frame header into */
    u8 *aFrame = 0;               /* Malloc'd buffer to load entire frame */
    int szFrame;                  /* Number of bytes in buffer aFrame[] */
    u8 *aData;                    /* Pointer to data part of aFrame buffer */
    int iFrame;                   /* Index of last frame read */
    i64 iOffset;                  /* Next offset to read from log file */
    int szPage;                   /* Page size according to the log */
    u32 aCksum[2];                /* Running checksum */

    /* Read in the first frame header in the file (to determine the 
    ** database page size).
    */
    rc = sqlite3OsRead(pWal->pWalFd, aBuf, WAL_HDRSIZE, 0);
    if( rc!=SQLITE_OK ){
      return rc;
    }

    /* If the database page size is not a power of two, or is greater than
    ** SQLITE_MAX_PAGE_SIZE, conclude that the WAL file contains no valid data.
    */
    szPage = sqlite3Get4byte(&aBuf[8]);
    if( szPage&(szPage-1) || szPage>SQLITE_MAX_PAGE_SIZE || szPage<512 ){
      goto finished;
    }
    pWal->nCkpt = sqlite3Get4byte(&aBuf[12]);
    aCksum[0] = sqlite3Get4byte(&aBuf[16]);
    aCksum[1] = sqlite3Get4byte(&aBuf[20]);

    /* Malloc a buffer to read frames into. */
    szFrame = szPage + WAL_FRAME_HDRSIZE;
    aFrame = (u8 *)sqlite3_malloc(szFrame);
    if( !aFrame ){
      return SQLITE_NOMEM;
    }
    aData = &aFrame[WAL_FRAME_HDRSIZE];

    /* Read all frames from the log file. */
    iFrame = 0;
    for(iOffset=WAL_HDRSIZE; (iOffset+szFrame)<=nSize; iOffset+=szFrame){
      u32 pgno;                   /* Database page number for frame */
      u32 nTruncate;              /* dbsize field from frame header */
      int isValid;                /* True if this frame is valid */

      /* Read and decode the next log frame. */
      rc = sqlite3OsRead(pWal->pWalFd, aFrame, szFrame, iOffset);
      if( rc!=SQLITE_OK ) break;
      isValid = walDecodeFrame(pWal, aCksum, &pgno, &nTruncate, szPage,
                               aData, aFrame);
      if( !isValid ) break;
      rc = walIndexAppend(pWal, ++iFrame, pgno);
      if( rc!=SQLITE_OK ) break;

      /* If nTruncate is non-zero, this is a commit record. */
      if( nTruncate ){
        hdr.iCheck1 = aCksum[0];

    rc = sqlite3OsSync(pWal->pDbFd, sync_flags);
    if( rc!=SQLITE_OK ) goto out;
  }
  pWal->hdr.mxFrame = 0;
  pWal->hdr.iCheck1 = 2;
  pWal->hdr.iCheck2 = 3;
  walIndexWriteHdr(pWal, &pWal->hdr);
  pWal->nCkpt++;

  /* TODO: If a crash occurs and the current log is copied into the 
  ** database there is no problem. However, if a crash occurs while
  ** writing the next transaction into the start of the log, such that:
  **
  **   * The first transaction currently in the log is left intact, but
  **   * The second (or subsequent) transaction is damaged,

int sqlite3WalSavepointUndo(Wal *pWal, u32 iFrame){
  int rc = SQLITE_OK;
  u8 aCksum[8];
  assert( pWal->lockState==SQLITE_SHM_WRITE );

  pWal->hdr.mxFrame = iFrame;
  if( iFrame>0 ){
    i64 iOffset = walFrameOffset(iFrame, pWal->hdr.szPage) + sizeof(u32)*4;
    rc = sqlite3OsRead(pWal->pWalFd, aCksum, sizeof(aCksum), iOffset);
    pWal->hdr.iCheck1 = sqlite3Get4byte(&aCksum[0]);
    pWal->hdr.iCheck2 = sqlite3Get4byte(&aCksum[4]);
  }

  return rc;
}

  u32 iFrame;                     /* Next frame address */
  u8 aFrame[WAL_FRAME_HDRSIZE];   /* Buffer to assemble frame-header in */
  PgHdr *p;                       /* Iterator to run through pList with. */
  u32 aCksum[2];                  /* Checksums */
  PgHdr *pLast = 0;               /* Last frame in list */
  int nLast = 0;                  /* Number of extra copies of last page */


  assert( pList );
  assert( pWal->lockState==SQLITE_SHM_WRITE );
  assert( pWal->pWiData==0 );

  /* If this is the first frame written into the log, write the WAL
  ** header to the start of the WAL file. See comments at the top of
  ** this source file for a description of the WAL header format.
  */

  iFrame = pWal->hdr.mxFrame;
  if( iFrame==0 ){
    u8 aWalHdr[WAL_HDRSIZE];        /* Buffer to assembly wal-header in */
    sqlite3Put4byte(&aWalHdr[0], 0x377f0682);
    sqlite3Put4byte(&aWalHdr[4], 3007000);
    sqlite3Put4byte(&aWalHdr[8], szPage);
    sqlite3Put4byte(&aWalHdr[12], pWal->nCkpt);
    sqlite3_randomness(8, &aWalHdr[16]);
    pWal->hdr.iCheck1 = pWal->iSalt1 = sqlite3Get4byte(&aWalHdr[16]);
    pWal->hdr.iCheck2 = pWal->iSalt2 = sqlite3Get4byte(&aWalHdr[20]);
    rc = sqlite3OsWrite(pWal->pWalFd, aWalHdr, sizeof(aWalHdr), 0);
    if( rc!=SQLITE_OK ){
      return rc;
    }
  }

  aCksum[0] = pWal->hdr.iCheck1;
  aCksum[1] = pWal->hdr.iCheck2;

  /* Write the log file. */
  for(p=pList; p; p=p->pDirty){
    u32 nDbsize;                  /* Db-size field for frame header */
    i64 iOffset;                  /* Write offset in log file */

    iOffset = walFrameOffset(++iFrame, szPage);
    
    /* Populate and write the frame header */
    nDbsize = (isCommit && p->pDirty==0) ? nTruncate : 0;
    walEncodeFrame(pWal, aCksum, p->pgno, nDbsize, szPage, p->pData, aFrame);
    rc = sqlite3OsWrite(pWal->pWalFd, aFrame, sizeof(aFrame), iOffset);
    if( rc!=SQLITE_OK ){
      return rc;
    }

    /* Write the page data */
    rc = sqlite3OsWrite(pWal->pWalFd, p->pData, szPage, iOffset+sizeof(aFrame));

    i64 iOffset = walFrameOffset(iFrame+1, szPage);

    assert( isCommit );
    assert( iSegment>0 );

    iSegment = (((iOffset+iSegment-1)/iSegment) * iSegment);
    while( iOffset<iSegment ){
      walEncodeFrame(pWal, aCksum, pLast->pgno, nTruncate, szPage,
                     pLast->pData, aFrame);
      rc = sqlite3OsWrite(pWal->pWalFd, aFrame, sizeof(aFrame), iOffset);
      if( rc!=SQLITE_OK ){
        return rc;
      }

      iOffset += WAL_FRAME_HDRSIZE;
      rc = sqlite3OsWrite(pWal->pWalFd, pLast->pData, szPage, iOffset); 

  [lindex $args 0] eval { PRAGMA page_size = 1024 }
  [lindex $args 0] eval { PRAGMA journal_mode = wal }
  [lindex $args 0] eval { PRAGMA synchronous = normal }
  [lindex $args 0] function blob blob
}

proc log_file_size {nFrame pgsz} {
  expr {24 + ($pgsz+24)*$nFrame}
}

proc log_deleted {logfile} {
  return [expr [file exists $logfile]==0]
}

#

# number of "padding" frames are appended to the log file when a transaction
# is committed in synchronous=FULL mode.
# 
# Do this by creating a database that uses 512 byte pages. Then writing
# a transaction that modifies 171 pages. In synchronous=NORMAL mode, this
# produces a log file of:
#
#   24 + (24+512)*171 = 90312 bytes.
#
# Slightly larger than 11*8192 = 90112 bytes.
#
# Run the test using various different sector-sizes. In each case, the
# WAL code should write the 90300 bytes of log file containing the 
# transaction, then append as may frames as are required to extend the
# log file so that no part of the next transaction will be written into
# a disk-sector used by transaction just committed.
#
set old_pending_byte [sqlite3_test_control_pending_byte 0x10000000]
catch { db close }
foreach {tn sectorsize logsize} {
  1   128  92216
  2   256  92216
  3   512  92216 
  4  1024  92216
  5  2048  92216
  6  4096  94360
  7  8192  98648
} {
  file delete -force test.db test.db-wal test.db-journal
  sqlite3_simulate_device -sectorsize $sectorsize
  sqlite3 db test.db -vfs devsym

  do_test wal-17.$tn.1 {
    execsql {

         5      {0 0 1 2 3 4}
         6      {0 0 1 2 3 4 5 6}
} {
  do_test wal-18.1.$nFrame {
    file copy -force testX.db test.db
    file copy -force testX.db-wal test.db-wal

    hexio_write test.db-wal [expr 24 + $nFrame*(24+1024) + 20] 00000000

    sqlite3 db test.db
    execsql { 
      SELECT * FROM t1;
      PRAGMA integrity_check; 
    }
  } [concat $result ok]

      # the database will be corrupt (because the garbage frame contents
      # will be treated as valid content). If $pgsz is invalid (too small
      # or too large), the db will not be corrupt as the log file will
      # be ignored.
      #
      set c1 22
      set c2 23
      set walhdr [binary format IIIIII 931071618 3007000 $pgsz 1234 $c1 $c2]
      set salt1 $c1
      set framebody [randomblob $pgsz]
      set framehdr  [binary format II $pg 5]
      logcksum c1 c2 $framehdr
      logcksum c1 c2 $framebody
      set framehdr [binary format IIIIII $pg 5 1234 $salt1 $c1 $c2]
      set fd [open test.db-wal w]
      fconfigure $fd -encoding binary -translation binary
      puts -nonewline $fd $walhdr
      puts -nonewline $fd $framehdr
      puts -nonewline $fd $framebody
      close $fd
  

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

ifcapable !wal {finish_test ; return }

proc log_file_size {nFrame pgsz} {
  expr {24 + ($pgsz+24)*$nFrame}
}

# Test organization:
# 
#   walback-1.*: Simple tests.
#   walback-2.*: Test backups when the source db is modified mid-backup.
#

} {SQLITE_DONE SQLITE_OK}
do_test walbak-2.12 {
  string compare [sig db] [sig db2]
} {0}
db2 close

finish_test

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

ifcapable !wal {finish_test ; return }

proc log_file_size {nFrame pgsz} {
  expr {24 + ($pgsz+24)*$nFrame}
}

set ::wal_hook [list]
proc wal_hook {zDb nEntry} {
  lappend ::wal_hook $zDb $nEntry
  return 0
}