SQLite

*************************************************************************
**
** This file contains the implementation of a write-ahead log (WAL) used in 
** "journal_mode=WAL" mode.
**
** WRITE-AHEAD LOG (WAL) FILE FORMAT
**
** A wal file consists of a header followed by zero or more "frames".
** Each frame records the revised content of a single page from the
** database file.  All changes to the database are recorded by writing
** frames into the WAL.  Transactions commit when a frame is written that
** contains a commit marker.  A single WAL can and usually does record 
** multiple transactions.  Periodically, the content of the WAL is
** transferred back into the database file in an operation called a
** "checkpoint".

** 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 */
  u32 szPage;           /* Database page size in bytes */
  u32 mxFrame;          /* Index of last valid frame in the WAL */
  u32 nPage;            /* Size of database in pages */
  u32 iCheck1;          /* Checksum value 1 */
  u32 iCheck2;          /* Checksum value 2 */
};

/* Size of serialized WalIndexHdr object. */
#define WALINDEX_HDR_NFIELD (sizeof(WalIndexHdr) / sizeof(u32))

/* A block of 16 bytes beginning at WALINDEX_LOCK_OFFSET is reserved
** for locks. Since some systems only feature 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*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

  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 

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


/*
** Generate an 8 byte checksum based on the data in array aByte[] and the

** initial values of aCksum[0] and aCksum[1]. The checksum is written 

** back into aCksum[] before returning.


*/
static void walChecksumBytes(u8 *a, int nByte, u32 *aCksum){





  u32 s1 = aCksum[0];


  u32 s2 = aCksum[1];



  u8 *aEnd = (u8*)&a[nByte];

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

  do {
    s1 += (a[0]<<24) + (a[1]<<16) + (a[2]<<8) + a[3] + s2;
    s2 += (a[4]<<24) + (a[5]<<16) + (a[6]<<8) + a[7] + s1;
    a += 8;
  }while( a<aEnd );
  aCksum[0] = s1;
  aCksum[1] = s2;
}

/*
** Attempt to change the lock status.
**
** When changing the lock status to SQLITE_SHM_READ, store the
** type of reader lock (either SQLITE_SHM_READ or SQLITE_SHM_READ_FULL)

      pWal->lockState = SQLITE_SHM_READ;
    }
  }
  return rc;
}

/*
** Update the header of the wal-index file.


*/
static void walIndexWriteHdr(Wal *pWal, WalIndexHdr *pHdr){
  volatile u32 *aHdr = pWal->pWiData;                 /* Write header here */
  volatile u32 *aCksum = &aHdr[WALINDEX_HDR_NFIELD];  /* Write cksum here */

  assert( WALINDEX_HDR_NFIELD==sizeof(WalIndexHdr)/4 );
  assert( aHdr!=0 );
  memcpy((void*)aHdr, pHdr, sizeof(WalIndexHdr));
  aCksum[0] = aCksum[1] = 1;
  walChecksumBytes((u8*)aHdr, sizeof(WalIndexHdr), (u32*)aCksum);
}

/*
** 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]);
  return 1;
}

/*
** Define the parameters of the hash tables in the wal-index file. There

    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];
        hdr.iCheck2 = aCksum[1];
        hdr.mxFrame = iFrame;
        hdr.nPage = nTruncate;
        hdr.szPage = szPage;
      }
    }

    sqlite3_free(aFrame);
  }else{
    hdr.iCheck1 = 2;
    hdr.iCheck2 = 3;
  }

finished:
  if( rc==SQLITE_OK && hdr.mxFrame==0 ){
    rc = walIndexRemap(pWal, WALINDEX_MMAP_INCREMENT);
  }
  if( rc==SQLITE_OK ){
    walIndexWriteHdr(pWal, &hdr);
    memcpy(&pWal->hdr, &hdr, sizeof(hdr));

  }
  return rc;
}

/*
** Close an open wal-index.
*/

  if( !pRet ){
    return SQLITE_NOMEM;
  }

  pRet->pVfs = pVfs;
  pRet->pWalFd = (sqlite3_file *)&pRet[1];
  pRet->pDbFd = pDbFd;

  pRet->zWalName = zWal = pVfs->szOsFile + (char*)pRet->pWalFd;
  sqlite3_snprintf(nWal, zWal, "%s-wal", zDbName);
  rc = sqlite3OsShmOpen(pDbFd);

  /* Open file handle on the write-ahead log file. */
  if( rc==SQLITE_OK ){
    pRet->isWindexOpen = 1;

  /* Sync the database file. If successful, update the wal-index. */
  if( sync_flags ){
    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,
  **
  ** then the database could become corrupt.
  **
  ** The easiest thing to do would be to write and sync a dummy header
  ** into the log at this point. Unfortunately, that turns out to be
  ** an unwelcome performance hit. Alternatives are...
  */
#if 0 
  memset(zBuf, 0, WAL_FRAME_HDRSIZE);
  rc = sqlite3OsWrite(pWal->pWalFd, zBuf, WAL_FRAME_HDRSIZE, 0);
  if( rc!=SQLITE_OK ) goto out;
  rc = sqlite3OsSync(pWal->pWalFd, pWal->sync_flags);
#endif

 out:
  walIteratorFree(pIter);
  return rc;
}

/*

** pWal->hdr, then pWal->hdr is updated to the content of the new header
** and *pChanged is set to 1.
**
** If the checksum cannot be verified return non-zero. If the header
** is read successfully and the checksum verified, return zero.
*/
int walIndexTryHdr(Wal *pWal, int *pChanged){
  int i;
  volatile u32 *aWiData;
  u32 aCksum[2] = {1, 1};
  u32 aHdr[WALINDEX_HDR_NFIELD+2];

  assert( pWal->pWiData );
  if( pWal->szWIndex==0 ){
    /* The wal-index is of size 0 bytes. This is handled in the same way
    ** as an invalid header. The caller will run recovery to construct
    ** a valid wal-index file before accessing the database.
    */
    return 1;
  }

  /* Read the header. The caller may or may not have an exclusive 
  ** (WRITE, PENDING, CHECKPOINT or RECOVER) lock on the wal-index
  ** file, meaning it is possible that an inconsistent snapshot is read
  ** from the file. If this happens, return non-zero.
  */
  aWiData = pWal->pWiData;
  for(i=0; i<WALINDEX_HDR_NFIELD+2; i++){
    aHdr[i] = aWiData[i];
  }
  walChecksumBytes((u8*)aHdr, sizeof(u32)*WALINDEX_HDR_NFIELD, aCksum);
  if( aCksum[0]!=aHdr[WALINDEX_HDR_NFIELD]
   || aCksum[1]!=aHdr[WALINDEX_HDR_NFIELD+1]
  ){
    return 1;
  }

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

  }

  /* The header was successfully read. Return zero. */
  return 0;
}

/*

}

/* Move the write position of the WAL back to iFrame.  Called in
** response to a ROLLBACK TO command.
*/
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;
}

/* 
** Write a set of frames to the log. The caller must hold the write-lock
** on the log file (obtained using sqlite3WalWriteLock()).
*/
int sqlite3WalFrames(
  Wal *pWal,                      /* Wal handle to write to */
  int szPage,                     /* Database page-size in bytes */
  PgHdr *pList,                   /* List of dirty pages to write */
  Pgno nTruncate,                 /* Database size after this commit */
  int isCommit,                   /* True if this is a commit */
  int sync_flags                  /* Flags to pass to OsSync() (or 0) */
){
  int rc;                         /* Used to catch return codes */
  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); 

    /* Update the private copy of the header. */
    pWal->hdr.szPage = szPage;
    pWal->hdr.mxFrame = iFrame;
    if( isCommit ){
      pWal->hdr.iChange++;
      pWal->hdr.nPage = nTruncate;
    }
    pWal->hdr.iCheck1 = aCksum[0];
    pWal->hdr.iCheck2 = aCksum[1];

    /* If this is a commit, update the wal-index header too. */
    if( isCommit ){
      walIndexWriteHdr(pWal, &pWal->hdr);
      pWal->iCallback = iFrame;
    }
  }

  walIndexUnmap(pWal);
  return rc;
}

    execsql { BEGIN ; SELECT * FROM t1 }
  } {1 2 3 4 5 6}
  do_test wal-10.$tn.9 {
    sql2 COMMIT
    catchsql { INSERT INTO t1 VALUES(9, 10) }
  } {1 {database is locked}}
  do_test wal-10.$tn.10 {
    execsql { COMMIT; BEGIN; INSERT INTO t1 VALUES(9, 10); COMMIT; }



    execsql { SELECT * FROM t1 }
  } {1 2 3 4 5 6 7 8 9 10}

  # Open a read transaction with [db2]. Check that this prevents [db] from
  # checkpointing the database. But not from writing to it.
  #
  do_test wal-10.$tn.11 {

      # The page-size in the log file header is set to $pgsz. If the
      # WAL code considers $pgsz to be a valid SQLite database file page-size,
      # 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
  

        }
      }

      if {$method == "xShmLock"} { lappend ::locks [lindex $args 2] }
      return SQLITE_OK
    }


    execsql { SELECT count(a), sum(a) FROM t1 } db2
  } $res

  do_test wal2-1.$tn.2 {
    set ::locks
  } $wal_locks
}

         4    7   {6 21}   {7 28}    2
         5    8   {7 28}   {8 36}    3
         6    9   {8 36}   {9 45}    4
         7   10   {9 45}   {10 55}   5
         8   11   {10 55}  {11 66}   6
         9   12   {11 66}  {12 78}   7
} {
  do_test wal2-1.$tn.1 {
    set oldhdr [set_tvfs_hdr $::shm_file]
    execsql { INSERT INTO t1 VALUES($iInsert) }
    execsql { SELECT count(a), sum(a) FROM t1 }
  } $res1

  do_test wal2-2.$tn.2 {
    set ::locks [list]

do_test wal2-6.5.3 {
  execsql { PRAGMA wal_checkpoint }
} {}

db close

finish_test