SQLite

** The following object holds a copy of the wal-index header content.
**
** The actual header in the wal-index consists of two copies of this
** object.
*/
struct WalIndexHdr {
  u32 iChange;      /* Counter incremented each transaction */
  u16 bigEndCksum;  /* True if checksums in WAL are big-endian */
  u16 szPage;       /* Database page size in bytes */
  u32 mxFrame;      /* Index of last valid frame in the WAL */
  u32 nPage;        /* Size of database in pages */
  u32 aSalt[2];     /* Salt-1 and salt-2 values copied from WAL header */
  u32 aCksum[2];    /* Checksum over all prior fields */
};

/* A block of WALINDEX_LOCK_RESERVED bytes beginning at
** WALINDEX_LOCK_OFFSET is reserved for locks. Since some systems
** only support mandatory file-locks, we do not read or write data
** from the region of the file on which locks are applied.
*/
#define WALINDEX_LOCK_OFFSET   (sizeof(WalIndexHdr)*2)
#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

/* WAL magic value. Either this value, or the same value with the least
** significant bit also set (WAL_MAGIC | 0x00000001) is stored in 32-bit
** big-endian format in the first 4 bytes of a WAL file.
**
** If the LSB is set, then the checksums for each frame within the WAL
** file are calculated by treating all data as an array of 32-bit 
** big-endian words. Otherwise, they are calculated by interpreting 
** all data as 32-bit little-endian words.
*/
#define WAL_MAGIC 0x377f0682

/*
** 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) (                               \

  struct WalSegment {
    int iNext;              /* Next slot in aIndex[] not previously returned */
    u8 *aIndex;             /* i0, i1, i2... such that aPgno[iN] ascending */
    u32 *aPgno;             /* 256 page numbers.  Pointer to Wal.pWiData */
  } aSegment[1];        /* One for every 256 entries in the WAL */
};

/*
** The argument to this macro must be of type u32. On a little-endian
** architecture, it returns the u32 value that results from interpreting
** the 4 bytes as a big-endian value. On a big-endian architecture, it
** returns the value that would be produced by intepreting the 4 bytes
** of the input value as a little-endian integer.
*/
#define BYTESWAP32(x) ( \
    (((x)&0x000000FF)<<24) + (((x)&0x0000FF00)<<8)  \
  + (((x)&0x00FF0000)>>8)  + (((x)&0xFF000000)>>24) \
)

/*
** Generate or extend an 8 byte checksum based on the data in 
** array aByte[] and the initial values of aIn[0] and aIn[1] (or
** initial values of 0 and 0 if aIn==NULL).
**
** The checksum is written back into aOut[] before returning.
**
** nByte must be a positive multiple of 8.
*/
static void walChecksumBytes(
  int nativeCksum, /* True for native byte-order, false for non-native */
  u8 *a,           /* Content to be checksummed */
  int nByte,       /* Bytes of content in a[].  Must be a multiple of 8. */
  const u32 *aIn,  /* Initial checksum value input */
  u32 *aOut        /* OUT: Final checksum value output */
){
  u32 s1, s2;
  u32 *aData = (u32 *)a;
  u32 *aEnd = (u32 *)&a[nByte];

  if( aIn ){
    s1 = aIn[0];
    s2 = aIn[1];
  }else{
    s1 = s2 = 0;
  }

  assert( nByte>=8 );
  assert( (nByte&0x00000007)==0 );

  if( nativeCksum ){
    do {
      s1 += *aData++ + s2;
      s2 += *aData++ + s1;
    }while( aData<aEnd );
  }else{
    do {
      s1 += BYTESWAP32(aData[0]) + s2;
      s2 += BYTESWAP32(aData[1]) + s1;
      aData += 2;
    }while( aData<aEnd );
  }

  aOut[0] = s1;
  aOut[1] = s2;
}

/*
** Attempt to change the lock status.
**

/*
** Write the header information in pWal->hdr into the wal-index.
**
** The checksum on pWal->hdr is updated before it is written.
*/
static void walIndexWriteHdr(Wal *pWal){
  WalIndexHdr *aHdr;
  walChecksumBytes(1, (u8*)&pWal->hdr,
                   sizeof(pWal->hdr) - sizeof(pWal->hdr.aCksum),
                   0, pWal->hdr.aCksum);
  aHdr = (WalIndexHdr*)pWal->pWiData;
  memcpy(&aHdr[1], &pWal->hdr, sizeof(pWal->hdr));
  sqlite3OsShmBarrier(pWal->pDbFd);
  memcpy(&aHdr[0], &pWal->hdr, sizeof(pWal->hdr));
}

static void walEncodeFrame(
  Wal *pWal,                      /* The write-ahead log */
  u32 iPage,                      /* Database page number for frame */
  u32 nTruncate,                  /* New db size (or 0 for non-commit frames) */
  u8 *aData,                      /* Pointer to page data */
  u8 *aFrame                      /* OUT: Write encoded frame here */
){
  int nativeCksum;                /* True for native byte-order checksums */
  u32 aCksum[2];
  assert( WAL_FRAME_HDRSIZE==24 );
  sqlite3Put4byte(&aFrame[0], iPage);
  sqlite3Put4byte(&aFrame[4], nTruncate);
  memcpy(&aFrame[8], pWal->hdr.aSalt, 8);

  nativeCksum = (pWal->hdr.bigEndCksum==SQLITE_BIGENDIAN);
  walChecksumBytes(nativeCksum, aFrame, 16, 0, aCksum);
  walChecksumBytes(nativeCksum, aData, pWal->szPage, aCksum, aCksum);

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

/*
** Check to see if the frame with header in aFrame[] and content
** in aData[] is valid.  If it is a valid frame, fill *piPage and
** *pnTruncate and return true.  Return if the frame is not valid.
*/
static int walDecodeFrame(
  Wal *pWal,                      /* The write-ahead log */
  u32 *piPage,                    /* OUT: Database page number for frame */
  u32 *pnTruncate,                /* OUT: New db size (or 0 if not commit) */
  u8 *aData,                      /* Pointer to page data (for checksum) */
  u8 *aFrame                      /* Frame data */
){
  int nativeCksum;                /* True for native byte-order checksums */
  u32 aCksum[2];
  assert( WAL_FRAME_HDRSIZE==24 );

  /* A frame is only valid if the salt values in the frame-header
  ** match the salt values in the wal-header. 
  */
  if( memcmp(&pWal->hdr.aSalt, &aFrame[8], 8)!=0 ){
    return 0;
  }

  /* A frame is only valid if a checksum of the first 16 bytes
  ** of the frame-header, and the frame-data matches
  ** the checksum in the last 8 bytes of the frame-header.
  */
  nativeCksum = (pWal->hdr.bigEndCksum==SQLITE_BIGENDIAN);
  walChecksumBytes(nativeCksum, aFrame, 16, 0, aCksum);
  walChecksumBytes(nativeCksum, aData, pWal->szPage, aCksum, aCksum);
  if( aCksum[0]!=sqlite3Get4byte(&aFrame[16]) 
   || aCksum[1]!=sqlite3Get4byte(&aFrame[20]) 
  ){
    /* Checksum failed. */
    return 0;
  }

/*
** Recover the wal-index by reading the write-ahead log file. 
** The caller must hold RECOVER lock on the wal-index file.
*/
static int walIndexRecover(Wal *pWal){
  int rc;                         /* Return Code */
  i64 nSize;                      /* Size of log file */
  WalIndexHdr hdr;                /* Recovered wal-index header */

  assert( pWal->lockState>SQLITE_SHM_READ );
  memset(&hdr, 0, sizeof(hdr));

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

  if( nSize>WAL_HDRSIZE ){
    u8 aBuf[WAL_HDRSIZE];         /* Buffer to load WAL 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 magic;                    /* Magic value read from WAL header */

    /* Read in the WAL header. */


    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. Similarly, if the 'magic' value is invalid, ignore the whole
    ** WAL file.
    */
    magic = sqlite3Get4byte(&aBuf[0]);
    szPage = sqlite3Get4byte(&aBuf[8]);
    if( (magic&0xFFFFFFFE)!=WAL_MAGIC 
     || szPage&(szPage-1) 
     || szPage>SQLITE_MAX_PAGE_SIZE 
     || szPage<512 
    ){
      goto finished;
    }
    hdr.bigEndCksum = pWal->hdr.bigEndCksum = (magic&0x00000001);
    pWal->szPage = szPage;
    pWal->nCkpt = sqlite3Get4byte(&aBuf[12]);
    memcpy(&pWal->hdr.aSalt, &aBuf[16], 8);

    /* Malloc a buffer to read frames into. */
    szFrame = szPage + WAL_FRAME_HDRSIZE;
    aFrame = (u8 *)sqlite3_malloc(szFrame);

  if( memcmp(&h1, &h2, sizeof(h1))!=0 ){
    return 1;   /* Dirty read */
  }  
  if( h1.szPage==0 ){
    return 1;   /* Malformed header - probably all zeros */
  }
  walChecksumBytes(1, (u8*)&h1, sizeof(h1)-sizeof(h1.aCksum), 0, aCksum);
  if( aCksum[0]!=h1.aCksum[0] || aCksum[1]!=h1.aCksum[1] ){
    return 1;   /* Checksum does not match */
  }

  if( memcmp(&pWal->hdr, &h1, sizeof(WalIndexHdr)) ){
    *pChanged = 1;
    memcpy(&pWal->hdr, &h1, sizeof(WalIndexHdr));

  /* 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], (WAL_MAGIC | SQLITE_BIGENDIAN));
    sqlite3Put4byte(&aWalHdr[4], 3007000);
    sqlite3Put4byte(&aWalHdr[8], szPage);
    pWal->szPage = szPage;
    pWal->hdr.bigEndCksum = SQLITE_BIGENDIAN;
    sqlite3Put4byte(&aWalHdr[12], pWal->nCkpt);
    memcpy(&aWalHdr[16], pWal->hdr.aSalt, 8);
    rc = sqlite3OsWrite(pWal->pWalFd, aWalHdr, sizeof(aWalHdr), 0);
    if( rc!=SQLITE_OK ){
      return rc;
    }
  }

  set blob
}

proc logcksum {ckv1 ckv2 blob} {
  upvar $ckv1 c1
  upvar $ckv2 c2

  set scanpattern I*
  if {$::tcl_platform(byteOrder) eq "littleEndian"} {
    set scanpattern i*
  }

  binary scan $blob $scanpattern values
  foreach {v1 v2} $values {
    set c1 [expr {($c1 + $v1 + $c2)&0xFFFFFFFF}]
    set c2 [expr {($c2 + $v2 + $c1)&0xFFFFFFFF}]
  }
}

file copy -force test.db testX.db

      set framebody [randomblob $pgsz]
      set framehdr  [binary format IIII $pg 5 22 23]
      set c1 0
      set c2 0
      logcksum c1 c2 $framehdr
      logcksum c1 c2 $framebody
      set framehdr [binary format IIIIII $pg 5 22 23 $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
  

# 2010 May 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.
#
#***********************************************************************
#

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

ifcapable !wal {finish_test ; return }

# This proc calculates checksums in the same way as those used by SQLite 
# in WAL files. If the $endian argument is "big", then checksums are
# calculated by interpreting data as an array of big-endian integers. If
# it is "little", data is interpreted as an array of little-endian integers.
#
proc log_cksum {endian ckv1 ckv2 blob} {
  upvar $ckv1 c1
  upvar $ckv2 c2

  if {$endian!="big" && $endian!="little"} {
    return -error "Bad value \"$endian\" - must be \"big\" or \"little\""
  }
  set scanpattern I*
  if {$endian == "little"} { set scanpattern i* }

  binary scan $blob $scanpattern values
  foreach {v1 v2} $values {
    set c1 [expr {($c1 + $v1 + $c2)&0xFFFFFFFF}]
    set c2 [expr {($c2 + $v2 + $c1)&0xFFFFFFFF}]
  }
}

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

# Read and return the contents of file $filename. Treat the content as
# binary data.
#
proc readfile {filename} {
  set fd [open $filename]
  fconfigure $fd -encoding binary
  fconfigure $fd -translation binary
  set data [read $fd]
  close $fd
  return $data
}

#
# File $filename must be a WAL file on disk. Check that the checksum of frame
# $iFrame in the file is correct when interpreting data as $endian-endian
# integers ($endian must be either "big" or "little"). If the checksum looks
# correct, return 1. Otherwise 0.
#
proc log_checksum_verify {filename iFrame endian} {
  set data [readfile $filename]
  set c1 0
  set c2 0
  
  binary scan [string range $data 8 11] I pgsz

  set n [log_file_size [expr $iFrame-1] $pgsz]
  binary scan [string range $data [expr $n+16] [expr $n+23]] II expect1 expect2
  log_cksum $endian c1 c2 [string range $data $n [expr $n+15]]
  log_cksum $endian c1 c2 [string range $data [expr $n+24] [expr $n+24+$pgsz-1]]

  set expect1 [expr $expect1&0xFFFFFFFF]
  set expect2 [expr $expect2&0xFFFFFFFF]
  expr {$c1==$expect1 && $c2==$expect2}
}

#
# File $filename must be a WAL file on disk. Compute the checksum for frame
# $iFrame in the file by interpreting data as $endian-endian integers 
# ($endian must be either "big" or "little"). Then write the computed 
# checksum into the file.
#
proc log_checksum_write {filename iFrame endian} {
  set data [readfile $filename]
  set c1 0
  set c2 0
  
  binary scan [string range $data 8 11] I pgsz

  set n [log_file_size [expr $iFrame-1] $pgsz]
  log_cksum $endian c1 c2 [string range $data $n [expr $n+15]]
  log_cksum $endian c1 c2 [string range $data [expr $n+24] [expr $n+24+$pgsz-1]]

  set bin [binary format II $c1 $c2]
  set fd [open $filename r+]
  fconfigure $fd -encoding binary
  fconfigure $fd -translation binary
  seek $fd [expr $n+16]
  puts -nonewline $fd $bin
  close $fd
}

#
# File $filename must be a WAL file on disk. Set the 'magic' field of the
# WAL header to indicate that checksums are $endian-endian ($endian must be
# either "big" or "little").
#
proc log_checksum_writemagic {filename endian} {
  set val [expr {0x377f0682 | ($endian == "big" ? 1 : 0)}]
  set bin [binary format I $val]
  set fd [open $filename r+]
  fconfigure $fd -encoding binary
  fconfigure $fd -translation binary
  puts -nonewline $fd $bin
  close $fd
}

#-------------------------------------------------------------------------
# Test cases walcksum-1.* attempt to verify the following:
#
#   * That both native and non-native order checksum log files can 
#      be recovered.
#
#   * That when appending to native or non-native checksum log files 
#     SQLite continues to use the right kind of checksums.
#
#   * Test point 2 when the appending process is not one that recovered
#     the log file.
#
#   * Test that both native and non-native checksum log files can be
#     checkpointed. And that after doing so the next write to the log
#     file occurs using native byte-order checksums. 
#
set native "big"
if {$::tcl_platform(byteOrder) == "littleEndian"} { set native "little" }
foreach endian {big little} {

  # Create a database. Leave some data in the log file.
  #
  do_test walcksum-1.$endian.1 {
    catch { db close }
    file delete -force test.db test.db-wal test.db-journal
    sqlite3 db test.db
    execsql {
      PRAGMA page_size = 1024;
      PRAGMA auto_vacuum = 0;
      PRAGMA synchronous = NORMAL;

      CREATE TABLE t1(a PRIMARY KEY, b);
      INSERT INTO t1 VALUES(1,  'one');
      INSERT INTO t1 VALUES(2,  'two');
      INSERT INTO t1 VALUES(3,  'three');
      INSERT INTO t1 VALUES(5,  'five');

      PRAGMA journal_mode = WAL;
      INSERT INTO t1 VALUES(8,  'eight');
      INSERT INTO t1 VALUES(13, 'thirteen');
      INSERT INTO t1 VALUES(21, 'twentyone');
    }

    file copy -force test.db test2.db
    file copy -force test.db-wal test2.db-wal
    db close

    list [file size test2.db] [file size test2.db-wal]
  } [list [expr 1024*3] [log_file_size 6 1024]]

  # Verify that the checksums are valid for all frames and that they
  # are calculated by interpreting data in native byte-order.
  #
  for {set f 1} {$f <= 6} {incr f} {
    do_test walcksum-1.$endian.2.$f {
      log_checksum_verify test2.db-wal $f $native
    } 1
  }

  # Replace all checksums in the current WAL file with $endian versions.
  # Then check that it is still possible to recover and read the database.
  #
  for {set f 1} {$f <= 6} {incr f} {
    do_test walcksum-1.$endian.3.$f {
      log_checksum_write test2.db-wal $f $endian
      log_checksum_verify test2.db-wal $f $endian
    } {1}
  }
  do_test walcksum-1.$endian.4.1 {
    log_checksum_writemagic test2.db-wal $endian
    file copy -force test2.db test.db
    file copy -force test2.db-wal test.db-wal
    sqlite3 db test.db
    execsql { SELECT a FROM t1 }
  } {1 2 3 5 8 13 21}

  # Following recovery, any frames written to the log should use the same 
  # endianness as the existing frames. Check that this is the case.
  #
  do_test walcksum-1.$endian.5.0 {
    execsql { 
      PRAGMA synchronous = NORMAL;
      INSERT INTO t1 VALUES(34, 'thirtyfour');
    }
    list [file size test.db] [file size test.db-wal]
  } [list [expr 1024*3] [log_file_size 8 1024]]
  for {set f 1} {$f <= 8} {incr f} {
    do_test walcksum-1.$endian.5.$f {
      log_checksum_verify test.db-wal $f $endian
    } {1}
  }

  # Now connect a second connection to the database. Check that this one
  # (not the one that did recovery) also appends frames to the log using
  # the same endianness for checksums as the existing frames.
  #
  do_test walcksum-1.$endian.6 {
    sqlite3 db2 test.db
    execsql { 
      PRAGMA integrity_check;
      SELECT a FROM t1;
    } db2
  } {ok 1 2 3 5 8 13 21 34}
  do_test walcksum-1.$endian.7.0 {
    execsql { 
      PRAGMA synchronous = NORMAL;
      INSERT INTO t1 VALUES(55, 'fiftyfive');
    } db2
    list [file size test.db] [file size test.db-wal]
  } [list [expr 1024*3] [log_file_size 10 1024]]
  for {set f 1} {$f <= 10} {incr f} {
    do_test walcksum-1.$endian.7.$f {
      log_checksum_verify test.db-wal $f $endian
    } {1}
  }

  # Now that both the recoverer and non-recoverer have added frames to the
  # log file, check that it can still be recovered.
  #
  file copy -force test.db test2.db
  file copy -force test.db-wal test2.db-wal
  do_test walcksum-1.$endian.7.11 {
    sqlite3 db3 test2.db
    execsql { 
      PRAGMA integrity_check;
      SELECT a FROM t1;
    } db3
  } {ok 1 2 3 5 8 13 21 34 55}
  db3 close

  # Run a checkpoint on the database file. Then, check that any frames written
  # to the start of the log use native byte-order checksums.
  #
  do_test walcksum-1.$endian.8.1 {
    execsql {
      PRAGMA wal_checkpoint;
      INSERT INTO t1 VALUES(89, 'eightynine');
    }
    log_checksum_verify test.db-wal 1 $native
  } {1}
  do_test walcksum-1.$endian.8.2 {
    log_checksum_verify test.db-wal 2 $native
  } {1}
  do_test walcksum-1.$endian.8.3 {
    log_checksum_verify test.db-wal 3 $native
  } [expr {$native == $endian}]

  do_test walcksum-1.$endian.9 {
    execsql { 
      PRAGMA integrity_check;
      SELECT a FROM t1;
    } db2
  } {ok 1 2 3 5 8 13 21 34 55 89}

  catch { db close }
  catch { db2 close }
}

finish_test