SQLite recover virtual table support for reading leaf nodes.

Uses the SQLite pager layer to fetch a leaf node and read the data
from it, returning the data as the results from a query against a
recover table.

This CL should cause no changes to Chromium, as it does not get compiled.

BUG=109482
TEST=SQLite test suite.


Review URL: https://chromiumcodereview.appspot.com/13196005

git-svn-id: svn://svn.chromium.org/chrome/trunk/src@191739 0039d316-1c4b-4281-b951-d872f2087c98

3 files changed, 874 insertions, 56 deletions

diff --git a/third_party/sqlite/src/src/recover-alt.c b/third_party/sqlite/src/src/recover-alt.c
index 46da9ce..d87c079 100644
--- a/third_party/sqlite/src/src/recover-alt.c
+++ b/third_party/sqlite/src/src/recover-alt.c
@@ -163,26 +163,67 @@
  * as lack of atomic updates between pages is the primary form of
  * corruption I have seen in the wild.
  */
+/* The implementation is via a series of cursors.  The cursor
+ * implementations follow the pattern:
+ *
+ * // Creates the cursor using various initialization info.
+ * int cursorCreate(...);
+ *
+ * // Returns 1 if there is no more data, 0 otherwise.
+ * int cursorEOF(Cursor *pCursor);
+ *
+ * // Various accessors can be used if not at EOF.
+ *
+ * // Move to the next item.
+ * int cursorNext(Cursor *pCursor);
+ *
+ * // Destroy the memory associated with the cursor.
+ * void cursorDestroy(Cursor *pCursor);
+ *
+ * References in the following are to sections at
+ * http://www.sqlite.org/fileformat2.html .
+ *
+ * RecoverLeafCursor iterates the records in a leaf table node
+ * described in section 1.5 "B-tree Pages".  When the node is
+ * exhausted, an interior cursor is used to get the next leaf node,
+ * and iteration continues there.
+ *
+ * RecoverInteriorCursor iterates the child pages in an interior table
+ * node described in section 1.5 "B-tree Pages".  When the node is
+ * exhausted, a parent interior cursor is used to get the next
+ * interior node at the same level, and iteration continues there.
+ *
+ * Together these record the path from the leaf level to the root of
+ * the tree.  Iteration happens from the leaves rather than the root
+ * both for efficiency and putting the special case at the front of
+ * the list is easier to implement.
+ *
+ * RecoverCursor uses a RecoverLeafCursor to iterate the rows of a
+ * table, returning results via the SQLite virtual table interface.
+ */
 /* TODO(shess): It might be useful to allow DEFAULT in types to
  * specify what to do for NULL when an ALTER TABLE case comes up.
  * Unfortunately, simply adding it to the exposed schema and using
  * sqlite3_result_null() does not cause the default to be generate.
  * Handling it ourselves seems hard, unfortunately.
  */
+/* TODO(shess): Account for the reserved region on pages (value from
+ * offset 20 in the database header).
+ */
 
 #include <assert.h>
 #include <ctype.h>
 #include <stdio.h>
 #include <string.h>
 
-/* Internal things that are used:
+/* Internal SQLite things that are used:
  * u32, u64, i64 types.
  * Btree, Pager, and DbPage structs.
  * DbPage.pData, .pPager, and .pgno
  * sqlite3 struct.
  * sqlite3BtreePager() and sqlite3BtreeGetPageSize()
  * sqlite3PagerAcquire() and sqlite3PagerUnref()
- * getVarint32() and getVarint().
+ * getVarint().
  */
 #include "sqliteInt.h"
 
@@ -195,6 +236,20 @@
 
 /* Generic constants and helper functions. */
 
+static const unsigned char kTableLeafPage = 0x0D;
+static const unsigned char kTableInteriorPage = 0x05;
+
+/* From section 1.5. */
+static const unsigned kiPageTypeOffset = 0;
+static const unsigned kiPageFreeBlockOffset = 1;
+static const unsigned kiPageCellCountOffset = 3;
+static const unsigned kiPageCellContentOffset = 5;
+static const unsigned kiPageFragmentedBytesOffset = 7;
+static const unsigned knPageLeafHeaderBytes = 8;
+/* Interior pages contain an additional field. */
+static const unsigned kiPageRightChildOffset = 8;
+static const unsigned kiPageInteriorHeaderBytes = 12;
+
 /* Accepted types are specified by a mask. */
 #define MASK_ROWID (1<<0)
 #define MASK_INTEGER (1<<1)
@@ -203,10 +258,146 @@
 #define MASK_BLOB (1<<4)
 #define MASK_NULL (1<<5)
 
-/* TODO(shess): In the future, these will be used more often.  For
- * now, just pretend they're useful.
+/* Helpers to decode fixed-size fields. */
+static u32 decodeUnsigned16(const unsigned char *pData){
+  return (pData[0]<<8) + pData[1];
+}
+static u32 decodeUnsigned32(const unsigned char *pData){
+  return (decodeUnsigned16(pData)<<16) + decodeUnsigned16(pData+2);
+}
+static i64 decodeSigned(const unsigned char *pData, unsigned nBytes){
+  i64 r = (char)(*pData);
+  while( --nBytes ){
+    r <<= 8;
+    r += *(++pData);
+  }
+  return r;
+}
+/* Derived from vdbeaux.c, sqlite3VdbeSerialGet(), case 7. */
+/* TODO(shess): Determine if swapMixedEndianFloat() applies. */
+static double decodeFloat64(const unsigned char *pData){
+#if !defined(NDEBUG)
+  static const u64 t1 = ((u64)0x3ff00000)<<32;
+  static const double r1 = 1.0;
+  u64 t2 = t1;
+  assert( sizeof(r1)==sizeof(t2) && memcmp(&r1, &t2, sizeof(r1))==0 );
+#endif
+  i64 x = decodeSigned(pData, 8);
+  double d;
+  memcpy(&d, &x, sizeof(x));
+  return d;
+}
+
+/* Return true if a varint can safely be read from pData/nData. */
+/* TODO(shess): DbPage points into the middle of a buffer which
+ * contains the page data before DbPage.  So code should always be
+ * able to read a small number of varints safely.  Consider whether to
+ * trust that or not.
+ */
+static int checkVarint(const unsigned char *pData, unsigned nData){
+  /* In the worst case the decoder takes all 8 bits of the 9th byte. */
+  if( nData>=9 ){
+    return 1;
+  }
+
+  /* Look for a high-bit-clear byte in what's left. */
+  unsigned i;
+  for( i=0; i<nData; ++i ){
+    if( !(pData[i]&0x80) ){
+      return 1;
+    }
+  }
+
+  /* Cannot decode in the space given. */
+  return 0;
+}
+
+/* Return 1 if n varints can be read from pData/nData. */
+static int checkVarints(const unsigned char *pData, unsigned nData,
+                        unsigned n){
+  /* In the worst case the decoder takes all 8 bits of the 9th byte. */
+  if( nData>=9*n ){
+    return 1;
+  }
+
+  unsigned nCur = 0, nFound = 0;
+  unsigned i;
+  for( i=0; nFound<n && i<nData; ++i ){
+    nCur++;
+    if( nCur==9 || !(pData[i]&0x80) ){
+      nFound++;
+      nCur = 0;
+    }
+  }
+
+  return nFound==n;
+}
+
+/* For some reason I kept making mistakes with offset calculations. */
+static const unsigned char *PageData(DbPage *pPage, unsigned iOffset){
+  assert( iOffset<=pPage->nPageSize );
+  return pPage->pData + iOffset;
+}
+
+/* The first page in the file contains a file header in the first 100
+ * bytes.  The page's header information comes after that.  Note that
+ * the offsets in the page's header information are relative to the
+ * beginning of the page, NOT the end of the page header.
+ */
+static const unsigned char *PageHeader(DbPage *pPage){
+  if( pPage->pgno==1 ){
+    const unsigned nDatabaseHeader = 100;
+    return PageData(pPage, nDatabaseHeader);
+  }else{
+    return PageData(pPage, 0);
+  }
+}
+
+/* Helper to fetch the pager and page size for the named database. */
+static int GetPager(sqlite3 *db, const char *zName,
+                    Pager **pPager, unsigned *pnPageSize){
+  Btree *pBt = NULL;
+  int i;
+  for( i=0; i<db->nDb; ++i ){
+    if( strcasecmp(db->aDb[i].zName, zName)==0 ){
+      pBt = db->aDb[i].pBt;
+      break;
+    }
+  }
+  if( !pBt ){
+    return SQLITE_ERROR;
+  }
+
+  *pPager = sqlite3BtreePager(pBt);
+  *pnPageSize = sqlite3BtreeGetPageSize(pBt);
+  return SQLITE_OK;
+}
+
+/* iSerialType is a type read from a record header.  See "2.1 Record Format".
  */
 
+/* Storage size of iSerialType in bytes.  My interpretation of SQLite
+ * documentation is that text and blob fields can have 32-bit length.
+ * Values past 2^31-12 will need more than 32 bits to encode, which is
+ * why iSerialType is u64.
+ */
+static u32 SerialTypeLength(u64 iSerialType){
+  switch( iSerialType ){
+    case 0 : return 0;  /* NULL */
+    case 1 : return 1;  /* Various integers. */
+    case 2 : return 2;
+    case 3 : return 3;
+    case 4 : return 4;
+    case 5 : return 6;
+    case 6 : return 8;
+    case 7 : return 8;  /* 64-bit float. */
+    case 8 : return 0;  /* Constant 0. */
+    case 9 : return 0;  /* Constant 1. */
+    case 10 : case 11 : assert( !"RESERVED TYPE"); return 0;
+  }
+  return (u32)((iSerialType>>1) - 6);
+}
+
 /* True if iSerialType refers to a blob. */
 static int SerialTypeIsBlob(u64 iSerialType){
   assert( iSerialType>=12 );
@@ -261,7 +452,7 @@ static char *sqlite3_strdup(const char *z){
  * and put it in *piRootPage.
  */
 static int getRootPage(sqlite3 *db, const char *zDb, const char *zTable,
-                       unsigned *piRootPage){
+                       u32 *piRootPage){
   if( strcmp(zTable, "sqlite_master")==0 ){
     *piRootPage = 1;
     return SQLITE_OK;
@@ -300,13 +491,388 @@ static int getRootPage(sqlite3 *db, const char *zDb, const char *zTable,
   return rc;
 }
 
+/* Primary structure for iterating the contents of a table.
+ *
+ * TODO(shess): Handle interior nodes by iterating them for new leaf
+ * pages, with interior nodes iterating their parents, and so on to
+ * the root.  For now, only handles tables with one leaf node.
+ *
+ * TODO(shess): Account for overflow pages.
+ *
+ * leafCursorDestroy - release all resources associated with the cursor.
+ * leafCursorCreate - create a cursor to iterate items from tree at
+ *                    the provided root page.
+ * leafCursorNextValidCell - get the cursor ready to access data from
+ *                           the next valid cell in the table.
+ * leafCursorCellRowid - get the current cell's rowid.
+ * leafCursorCellColumns - get current cell's column count.
+ * leafCursorCellColInfo - get type and data for a column in current cell.
+ *
+ * leafCursorNextValidCell skips cells which fail simple integrity
+ * checks, such as overlapping other cells, or being located at
+ * impossible offsets, or where header data doesn't correctly describe
+ * payload data.  Returns SQLITE_ROW if a valid cell is found,
+ * SQLITE_DONE if all pages in the tree were exhausted.
+ */
+typedef struct RecoverLeafCursor RecoverLeafCursor;
+struct RecoverLeafCursor {
+  /* TODO(shess): Something to handle interior nodes. */
+  DbPage *pPage;                   /* Reference to leaf page. */
+  unsigned nPageSize;              /* Size of pPage. */
+  unsigned nCells;                 /* Number of cells in pPage. */
+  unsigned iCell;                  /* Current cell. */
+
+  /* Info parsed from data in iCell. */
+  i64 iRowid;                      /* rowid parsed. */
+  unsigned nRecordCols;            /* how many items in the record. */
+  u64 iRecordOffset;               /* offset to record data. */
+  /* TODO(shess): nRecordBytes and nRecordHeaderBytes are used in
+   * leafCursorCellColInfo() to prevent buffer overruns.
+   * leafCursorCellDecode() already verified that the cell is valid, so
+   * those checks should be redundant.
+   */
+  u64 nRecordBytes;                /* Size of record data. */
+  unsigned nRecordHeaderBytes;     /* Size of record header data. */
+  unsigned char *pRecordHeader;    /* Pointer to record header data. */
+  /* TODO(shess): Something to handle overflow pages. */
+};
+
+/* Internal helper shared between next-page and create-cursor.  If
+ * pPage is a leaf page, it will be stored in the cursor and state
+ * initialized for reading cells.
+ *
+ * TODO(shess): leafCursorNextPage() will use this when handling
+ * interior pages.  It will loop over pages returned from the parent
+ * interior node until one of them "sticks".
+ *
+ * If SQLITE_OK is returned, the caller no longer owns pPage,
+ * otherwise the caller is responsible for discarding it.
+ */
+static int leafCursorLoadPage(RecoverLeafCursor *pCursor, DbPage *pPage){
+  /* Release the current page. */
+  if( pCursor->pPage ){
+    sqlite3PagerUnref(pCursor->pPage);
+    pCursor->pPage = NULL;
+    pCursor->iCell = pCursor->nCells = 0;
+  }
+
+  /* TODO(shess): If the page is an interior node, use it to generate
+   * leaf pages.  For now, bail out.
+   */
+  const unsigned char *pPageHeader = PageHeader(pPage);
+  if( pPageHeader[kiPageTypeOffset]==kTableInteriorPage ){
+    return SQLITE_ERROR;
+  }
+
+  /* If the page is not a leaf node, skip it. */
+  if( pPageHeader[kiPageTypeOffset]!=kTableLeafPage ){
+    sqlite3PagerUnref(pPage);
+    return SQLITE_OK;
+  }
+
+  /* Take ownership of the page and start decoding. */
+  pCursor->pPage = pPage;
+  pCursor->iCell = 0;
+  pCursor->nCells = decodeUnsigned16(pPageHeader + kiPageCellCountOffset);
+  return SQLITE_OK;
+}
+
+/* Get the next leaf-level page in the tree.  Returns SQLITE_ROW when
+ * a leaf page is found, SQLITE_DONE when no more leaves exist, or any
+ * error which occurred.
+ */
+static int leafCursorNextPage(RecoverLeafCursor *pCursor){
+  /* TODO(shess): Get the next leaf page and load it. */
+  return SQLITE_DONE;
+}
+
+static void leafCursorDestroy(RecoverLeafCursor *pCursor){
+  pCursor->pRecordHeader = NULL;
+
+  if( pCursor->pPage ){
+    sqlite3PagerUnref(pCursor->pPage);
+    pCursor->pPage = NULL;
+  }
+
+  memset(pCursor, 0xA5, sizeof(*pCursor));
+  sqlite3_free(pCursor);
+}
+
+/* Create a cursor to iterate the rows from the leaf pages of a table
+ * rooted at iRootPage.
+ */
+/* TODO(shess): recoverOpen() calls this to setup the cursor, and I
+ * think that recoverFilter() may make a hard assumption that the
+ * cursor returned will turn up at least one valid cell.
+ *
+ * The cases I can think of which break this assumption are:
+ * - pPage is a valid leaf page with no valid cells.
+ * - pPage is a valid interior page with no valid leaves.
+ * - pPage is a valid interior page who's leaves contain no valid cells.
+ * - pPage is not a valid leaf or interior page.
+ */
+static int leafCursorCreate(Pager *pPager, unsigned nPageSize,
+                            u32 iRootPage, RecoverLeafCursor **ppCursor){
+  /* Start out with the root page. */
+  DbPage *pPage;
+  int rc = sqlite3PagerAcquire(pPager, iRootPage, &pPage, 0);
+  if( rc!=SQLITE_OK ){
+    return rc;
+  }
+
+  RecoverLeafCursor *pCursor = sqlite3_malloc(sizeof(RecoverLeafCursor));
+  if( !pCursor ){
+    sqlite3PagerUnref(pPage);
+    return SQLITE_NOMEM;
+  }
+  memset(pCursor, 0, sizeof(*pCursor));
+
+  pCursor->nPageSize = nPageSize;
+
+  rc = leafCursorLoadPage(pCursor, pPage);
+  if( rc!=SQLITE_OK ){
+    sqlite3PagerUnref(pPage);
+    leafCursorDestroy(pCursor);
+    return rc;
+  }
+
+  /* pPage wasn't a leaf page, find the next leaf page. */
+  /* TODO(shess): When interior nodes are handled, this will scan
+   * forward to the first leaf node.
+   */
+  if( !pCursor->pPage ){
+    rc = leafCursorNextPage(pCursor);
+    if( rc!=SQLITE_DONE && rc!=SQLITE_ROW ){
+      leafCursorDestroy(pCursor);
+      return rc;
+    }
+  }
+
+  *ppCursor = pCursor;
+  return SQLITE_OK;
+}
+
+/* Useful for setting breakpoints. */
+static int ValidateError(){
+  return SQLITE_ERROR;
+}
+
+/* Setup the cursor for reading the information from cell iCell. */
+static int leafCursorCellDecode(RecoverLeafCursor *pCursor){
+  assert( pCursor->iCell<pCursor->nCells );
+
+  pCursor->pRecordHeader = NULL;
+
+  /* Find the offset to the row. */
+  const unsigned char *pPageHeader = PageHeader(pCursor->pPage);
+  const unsigned char *pCellOffsets = pPageHeader + knPageLeafHeaderBytes;
+  const unsigned iCellOffset =
+      decodeUnsigned16(pCellOffsets + pCursor->iCell*2);
+  if( iCellOffset>=pCursor->nPageSize ){
+    return ValidateError();
+  }
+
+  const unsigned char *pCell = PageData(pCursor->pPage, iCellOffset);
+  const unsigned nCellMaxBytes = pCursor->nPageSize - iCellOffset;
+
+  /* B-tree leaf cells lead with varint record size, varint rowid and
+   * varint header size.
+   */
+  /* TODO(shess): The smallest page size is 512 bytes, which has an m
+   * of 39.  Three varints need at most 27 bytes to encode.  I think.
+   */
+  if( !checkVarints(pCell, nCellMaxBytes, 3) ){
+    return ValidateError();
+  }
+
+  u64 nRecordBytes;
+  unsigned nRead = getVarint(pCell, &nRecordBytes);
+  assert( iCellOffset+nRead<=pCursor->nPageSize );
+  pCursor->nRecordBytes = nRecordBytes;
+
+  u64 iRowid;
+  nRead += getVarint(pCell + nRead, &iRowid);
+  assert( iCellOffset+nRead<=pCursor->nPageSize );
+  /* TODO(shess): This will not be true with overflow support. */
+  assert( iCellOffset+nRead+nRecordBytes<=pCursor->nPageSize );
+  pCursor->iRowid = (i64)iRowid;
+
+  pCursor->iRecordOffset = iCellOffset + nRead;
+
+  /* Check that no other cell starts within this cell. */
+  unsigned i;
+  const unsigned iEndOffset = iCellOffset + nRecordBytes;
+  for( i=0; i<pCursor->nCells; ++i ){
+    const unsigned iOtherOffset = decodeUnsigned16(pCellOffsets + i*2);
+    if( iOtherOffset>iCellOffset && iOtherOffset<iEndOffset ){
+      return ValidateError();
+    }
+  }
+
+  unsigned nRecordHeaderRead = 0;
+  u64 nRecordHeaderBytes;
+  nRecordHeaderRead = getVarint(pCell + nRead, &nRecordHeaderBytes);
+  assert( nRecordHeaderBytes<=nRecordBytes );
+  pCursor->nRecordHeaderBytes = nRecordHeaderBytes;
+
+  /* TODO(shess): The header data potentially could be large enough to
+   * overflow.  For now just point directly into the page.
+   */
+  pCursor->pRecordHeader = (unsigned char *)PageData(pCursor->pPage,
+                                                     iCellOffset + nRead);
+
+  /* Tally up the column count and size of data. */
+  unsigned nRecordCols = 0;
+  u64 nRecordColBytes = 0;
+  while( nRecordHeaderRead<nRecordHeaderBytes ){
+    if( !checkVarint(pCursor->pRecordHeader + nRecordHeaderRead,
+                     nRecordHeaderBytes - nRecordHeaderRead) ){
+      return ValidateError();
+    }
+    u64 iSerialType;
+    nRecordHeaderRead += getVarint(pCursor->pRecordHeader + nRecordHeaderRead,
+                                   &iSerialType);
+    if( iSerialType==10 || iSerialType==11 ){
+      return ValidateError();
+    }
+    nRecordColBytes += SerialTypeLength(iSerialType);
+    nRecordCols++;
+  }
+  pCursor->nRecordCols = nRecordCols;
+
+  /* Parsing the header used as many bytes as expected. */
+  if( nRecordHeaderRead!=nRecordHeaderBytes ){
+    return ValidateError();
+  }
+
+  /* Calculated record is size of expected record. */
+  if( nRecordHeaderBytes+nRecordColBytes!=nRecordBytes ){
+    return ValidateError();
+  }
+
+  return SQLITE_OK;
+}
+
+static i64 leafCursorCellRowid(RecoverLeafCursor *pCursor){
+  return pCursor->iRowid;
+}
+
+static unsigned leafCursorCellColumns(RecoverLeafCursor *pCursor){
+  return pCursor->nRecordCols;
+}
+
+/* Get the column info for the cell.  Pass NULL for ppBase to prevent
+ * retrieving the data segment.  If *pbFree is true, *ppBase must be
+ * freed by the caller using sqlite3_free().
+ */
+/* TODO(shess): *pbFree will be necessary when supporting overflow. */
+static int leafCursorCellColInfo(RecoverLeafCursor *pCursor,
+                                 unsigned iCol, u64 *piColType,
+                                 unsigned char **ppBase, int *pbFree){
+  /* Implicit NULL for columns past the end.  This case happens when
+   * rows have not been updated since an ALTER TABLE added columns.
+   * It is more convenient to address here than in callers.
+   */
+  if( iCol>=pCursor->nRecordCols ){
+    *piColType = 0;
+    if( ppBase ){
+      *ppBase = 0;
+      *pbFree = 0;
+    }
+    return SQLITE_OK;
+  }
+
+  /* Must be able to decode header size. */
+  const unsigned char *pRecordHeader = pCursor->pRecordHeader;
+  if( !checkVarint(pRecordHeader, pCursor->nRecordHeaderBytes) ){
+    return SQLITE_CORRUPT;
+  }
+
+  /* Rather than caching the header size and how many bytes it took,
+   * decode it every time.
+   */
+  u64 nRecordHeaderBytes;
+  unsigned nRead = getVarint(pRecordHeader, &nRecordHeaderBytes);
+  assert( nRecordHeaderBytes==pCursor->nRecordHeaderBytes );
+
+  /* Scan forward to the indicated column.  Scans to _after_ column
+   * for later range checking.
+   */
+  /* TODO(shess): This could get expensive for very wide tables.  An
+   * array of iSerialType could be built in leafCursorCellDecode(), but
+   * the number of columns is dynamic per row, so it would add memory
+   * management complexity.  Enough info to efficiently forward
+   * iterate could be kept, if all clients forward iterate
+   * (recoverColumn() may not).
+   */
+  u64 iColEndOffset = 0;
+  unsigned nColsSkipped = 0;
+  u64 iSerialType;
+  while( nColsSkipped<=iCol && nRead<nRecordHeaderBytes ){
+    if( !checkVarint(pRecordHeader + nRead, nRecordHeaderBytes - nRead) ){
+      return SQLITE_CORRUPT;
+    }
+    nRead += getVarint(pRecordHeader + nRead, &iSerialType);
+    iColEndOffset += SerialTypeLength(iSerialType);
+    nColsSkipped++;
+  }
+
+  /* Column's data extends past record's end. */
+  if( nRecordHeaderBytes+iColEndOffset>pCursor->nRecordBytes ){
+    return SQLITE_CORRUPT;
+  }
+
+  *piColType = iSerialType;
+  if( ppBase ){
+    /* Offset from end of headers to beginning of column. */
+    const u32 nColBytes = SerialTypeLength(iSerialType);
+    const unsigned iColOffset = iColEndOffset-nColBytes;
+
+    /* Start of record, plus the header, plus the column offset. */
+    const unsigned iOffset =
+        pCursor->iRecordOffset+nRecordHeaderBytes+iColOffset;
+
+    /* TODO(shess): Deal with overflow pages. */
+    *ppBase = (unsigned char *)PageData(pCursor->pPage, iOffset);
+    *pbFree = 0;
+  }
+  return SQLITE_OK;
+}
+
+static int leafCursorNextValidCell(RecoverLeafCursor *pCursor){
+  while( 1 ){
+    /* Move to the next cell. */
+    pCursor->iCell++;
+
+    /* No more cells, get the next leaf. */
+    if( pCursor->iCell>=pCursor->nCells ){
+      int rc = leafCursorNextPage(pCursor);
+      if( rc!=SQLITE_ROW ){
+        return rc;
+      }
+      assert( pCursor->iCell==0 );
+    }
+
+    /* If the cell is valid, indicate that a row is available. */
+    int rc = leafCursorCellDecode(pCursor);
+    if( rc==SQLITE_OK ){
+      return SQLITE_ROW;
+    }
+
+    /* Iterate until done or a valid row is found. */
+    /* TODO(shess): Remove debugging output. */
+    fprintf(stderr, "Skipping invalid cell\n");
+  }
+  return SQLITE_ERROR;
+}
+
 typedef struct Recover Recover;
 struct Recover {
   sqlite3_vtab base;
   sqlite3 *db;                /* Host database connection */
   char *zDb;                  /* Database containing target table */
   char *zTable;               /* Target table */
-  int nCols;                  /* Number of columns in target table */
+  unsigned nCols;             /* Number of columns in target table */
   unsigned char *pTypes;      /* Types of columns in target table */
 };
 
@@ -371,7 +937,7 @@ static int recoverDestroy(sqlite3_vtab *pVtab){
 typedef struct RecoverCursor RecoverCursor;
 struct RecoverCursor {
   sqlite3_vtab_cursor base;
-  i64 iRowid;  /* TODO(shess): Implement for real. */
+  RecoverLeafCursor *pLeafCursor;
   int bEOF;
 };
 
@@ -380,22 +946,34 @@ static int recoverOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
 
   Recover *pRecover = (Recover*)pVTab;
 
-  unsigned iRootPage = 0;
+  u32 iRootPage = 0;
   int rc = getRootPage(pRecover->db, pRecover->zDb, pRecover->zTable,
                        &iRootPage);
   if( rc!=SQLITE_OK ){
     return rc;
   }
 
-  /* TODO(shess): Implement some real stuff in here. */
+  unsigned nPageSize;
+  Pager *pPager;
+  rc = GetPager(pRecover->db, pRecover->zDb, &pPager, &nPageSize);
+  if( rc!=SQLITE_OK ){
+    return rc;
+  }
+
+  RecoverLeafCursor *pLeafCursor;
+  rc = leafCursorCreate(pPager, nPageSize, iRootPage, &pLeafCursor);
+  if( rc!=SQLITE_OK ){
+    return rc;
+  }
 
   RecoverCursor *pCursor = sqlite3_malloc(sizeof(RecoverCursor));
   if( !pCursor ){
+    leafCursorDestroy(pLeafCursor);
     return SQLITE_NOMEM;
   }
   memset(pCursor, 0, sizeof(*pCursor));
   pCursor->base.pVtab = pVTab;
-  pCursor->iRowid = 0;
+  pCursor->pLeafCursor = pLeafCursor;
 
   *ppCursor = (sqlite3_vtab_cursor*)pCursor;
   return SQLITE_OK;
@@ -404,40 +982,70 @@ static int recoverOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
 static int recoverClose(sqlite3_vtab_cursor *cur){
   FNENTRY();
   RecoverCursor *pCursor = (RecoverCursor*)cur;
+  if( pCursor->pLeafCursor ){
+    leafCursorDestroy(pCursor->pLeafCursor);
+    pCursor->pLeafCursor = NULL;
+  }
   memset(pCursor, 0xA5, sizeof(*pCursor));
   sqlite3_free(cur);
   return SQLITE_OK;
 }
 
-/* TODO(shess): Some data for purposes of mocking things.  Will go
- * away.
+/* Helpful place to set a breakpoint. */
+static int RecoverInvalidCell(){
+  return SQLITE_ERROR;
+}
+
+/* Returns SQLITE_OK if the cell has an appropriate number of columns
+ * with the appropriate types of data.
  */
-static struct {
-  u64 iColType;
-  const char *zTypeName;
-} gMockData[] = {
-  { 0, "NULL"},
-  { 1, "INTEGER"},
-  { 7, "FLOAT"},
-  { 13, "TEXT"},
-  { 12, "BLOB"},
-};
+static int recoverValidateLeafCell(Recover *pRecover, RecoverCursor *pCursor){
+  /* If the row's storage has too many columns, skip it. */
+  if( leafCursorCellColumns(pCursor->pLeafCursor)>pRecover->nCols ){
+    return RecoverInvalidCell();
+  }
+
+  /* Skip rows with unexpected types. */
+  unsigned i;
+  for( i=0; i<pRecover->nCols; ++i ){
+    /* ROWID alias. */
+    if( (pRecover->pTypes[i]&MASK_ROWID) ){
+      continue;
+    }
+
+    u64 iType;
+    int rc = leafCursorCellColInfo(pCursor->pLeafCursor, i, &iType, NULL, NULL);
+    assert( rc==SQLITE_OK );
+    if( rc!=SQLITE_OK || !SerialTypeIsCompatible(iType, pRecover->pTypes[i]) ){
+      return RecoverInvalidCell();
+    }
+  }
+
+  return SQLITE_OK;
+}
 
 static int recoverNext(sqlite3_vtab_cursor *pVtabCursor){
   FNENTRY();
   RecoverCursor *pCursor = (RecoverCursor*)pVtabCursor;
   Recover *pRecover = (Recover*)pCursor->base.pVtab;
+  int rc;
 
-  /* iRowid is 1-base, gMockData is 0-based. */
-  while( pCursor->iRowid<ArraySize(gMockData) ){
-    pCursor->iRowid++;
-    if( SerialTypeIsCompatible(gMockData[pCursor->iRowid-1].iColType,
-                               pRecover->pTypes[pRecover->nCols-1]) ){
+  /* Scan forward to the next cell with valid storage, then check that
+   * the stored data matches the schema.
+   */
+  while( (rc = leafCursorNextValidCell(pCursor->pLeafCursor))==SQLITE_ROW ){
+    if( recoverValidateLeafCell(pRecover, pCursor)==SQLITE_OK ){
       return SQLITE_OK;
     }
   }
-  pCursor->bEOF = 1;
-  return SQLITE_OK;
+
+  if( rc==SQLITE_DONE ){
+    pCursor->bEOF = 1;
+    return SQLITE_OK;
+  }
+
+  assert( rc!=SQLITE_OK );
+  return rc;
 }
 
 static int recoverFilter(
@@ -446,7 +1054,17 @@ static int recoverFilter(
   int argc, sqlite3_value **argv
 ){
   FNENTRY();
-  return recoverNext(pVtabCursor);
+  RecoverCursor *pCursor = (RecoverCursor*)pVtabCursor;
+  Recover *pRecover = (Recover*)pCursor->base.pVtab;
+
+  /* Load the first cell, and iterate forward if it's not valid. */
+  /* TODO(shess): What happens if no cells at all are valid? */
+  int rc = leafCursorCellDecode(pCursor->pLeafCursor);
+  if( rc!=SQLITE_OK || recoverValidateLeafCell(pRecover, pCursor)!=SQLITE_OK ){
+    return recoverNext(pVtabCursor);
+  }
+
+  return SQLITE_OK;
 }
 
 static int recoverEof(sqlite3_vtab_cursor *pVtabCursor){
@@ -466,29 +1084,60 @@ static int recoverColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
 
   /* ROWID alias. */
   if( (pRecover->pTypes[i]&MASK_ROWID) ){
-    sqlite3_result_int64(ctx, pCursor->iRowid);
+    sqlite3_result_int64(ctx, leafCursorCellRowid(pCursor->pLeafCursor));
     return SQLITE_OK;
   }
 
-  /* TODO(shess): Replace this with real code. */
-  if( pCursor->iRowid<1 || pCursor->iRowid>ArraySize(gMockData)+1 ){
-    return SQLITE_ERROR;
+  u64 iColType;
+  unsigned char *pColData = NULL;
+  int shouldFree = 0;
+  int rc = leafCursorCellColInfo(pCursor->pLeafCursor, i, &iColType,
+                                 &pColData, &shouldFree);
+  if( rc!=SQLITE_OK ){
+    return rc;
   }
-  if( i==pRecover->nCols-2 ){
-    sqlite3_result_text(ctx, gMockData[pCursor->iRowid-1].zTypeName, -1,
-                        SQLITE_STATIC);
-  }else if( i==pRecover->nCols-1 ){
-    switch( gMockData[pCursor->iRowid-1].iColType ){
-      case 0 : sqlite3_result_null(ctx); break;
-      case 1 : sqlite3_result_int(ctx, 17); break;
-      case 7 : sqlite3_result_double(ctx, 3.1415927); break;
-      case 13 :
-        sqlite3_result_text(ctx, "This is text", -1, SQLITE_STATIC);
-        break;
-      case 12 :
-        sqlite3_result_blob(ctx, "This is a blob", 14, SQLITE_STATIC);
-        break;
+  /* recoverValidateLeafCell() should guarantee that this will never
+   * occur.
+   */
+  if( !SerialTypeIsCompatible(iColType, pRecover->pTypes[i]) ){
+    if( shouldFree ){
+      sqlite3_free(pColData);
     }
+    return SQLITE_ERROR;
+  }
+
+  switch( iColType ){
+    case 0 : sqlite3_result_null(ctx); break;
+    case 1 : sqlite3_result_int64(ctx, decodeSigned(pColData, 1)); break;
+    case 2 : sqlite3_result_int64(ctx, decodeSigned(pColData, 2)); break;
+    case 3 : sqlite3_result_int64(ctx, decodeSigned(pColData, 3)); break;
+    case 4 : sqlite3_result_int64(ctx, decodeSigned(pColData, 4)); break;
+    case 5 : sqlite3_result_int64(ctx, decodeSigned(pColData, 6)); break;
+    case 6 : sqlite3_result_int64(ctx, decodeSigned(pColData, 8)); break;
+    case 7 : sqlite3_result_double(ctx, decodeFloat64(pColData)); break;
+    case 8 : sqlite3_result_int(ctx, 0); break;
+    case 9 : sqlite3_result_int(ctx, 1); break;
+    case 10 : assert( iColType!=10 ); break;
+    case 11 : assert( iColType!=11 ); break;
+
+    default : {
+      /* If pColData was already allocated, arrange to pass ownership. */
+      sqlite3_destructor_type pFn = SQLITE_TRANSIENT;
+      if( shouldFree ){
+        pFn = sqlite3_free;
+        shouldFree = 0;
+      }
+
+      u32 l = SerialTypeLength(iColType);
+      if( SerialTypeIsBlob(iColType) ){
+        sqlite3_result_blob(ctx, pColData, l, pFn);
+      }else{
+        sqlite3_result_text(ctx, (const char*)pColData, l, pFn);
+      }
+    } break;
+  }
+  if( shouldFree ){
+    sqlite3_free(pColData);
   }
   return SQLITE_OK;
 }
@@ -496,7 +1145,7 @@ static int recoverColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
 static int recoverRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){
   FNENTRY();
   RecoverCursor *pCursor = (RecoverCursor*)pVtabCursor;
-  *pRowid = pCursor->iRowid;
+  *pRowid = leafCursorCellRowid(pCursor->pLeafCursor);
   return SQLITE_OK;
 }
 
@@ -660,7 +1309,8 @@ static int findNameAndType(const char *parameter,
 /* Parse the arguments, placing type masks in *pTypes and the exposed
  * schema in *pzCreateSql (for sqlite3_declare_vtab).
  */
-static int ParseColumnsAndGenerateCreate(int nCols, const char *const *pCols,
+static int ParseColumnsAndGenerateCreate(unsigned nCols,
+                                         const char *const *pCols,
                                          char **pzCreateSql,
                                          unsigned char *pTypes,
                                          char **pzErr){
@@ -722,8 +1372,7 @@ static int recoverInit(
    * argv[3] backing table name
    * argv[4] columns
    */
-  const int kTypeCol = 4;
-  int nCols = argc - kTypeCol;
+  const unsigned kTypeCol = 4;
 
   /* Require to be in the temp database. */
   if( strcasecmp(argv[1], "temp")!=0 ){
@@ -732,7 +1381,7 @@ static int recoverInit(
   }
 
   /* Need the backing table and at least one column. */
-  if( nCols<1 ){
+  if( argc<=kTypeCol ){
     *pzErr = sqlite3_mprintf("no columns specified");
     return SQLITE_MISUSE;
   }
@@ -760,7 +1409,7 @@ static int recoverInit(
     return SQLITE_ERROR;
   }
 
-  pRecover->nCols = nCols;
+  pRecover->nCols = argc - kTypeCol;
   pRecover->pTypes = sqlite3_malloc(pRecover->nCols);
   if( !pRecover->zDb || !pRecover->zTable || !pRecover->pTypes ){
     recoverRelease(pRecover);
@@ -773,7 +1422,7 @@ static int recoverInit(
    * because there won't be a root page, but it would make more sense
    * to be explicit.
    */
-  unsigned iRootPage;
+  u32 iRootPage;
   int rc = getRootPage(pRecover->db, pRecover->zDb, pRecover->zTable,
                        &iRootPage);
   if( rc!=SQLITE_OK ){
@@ -784,7 +1433,7 @@ static int recoverInit(
 
   /* Parse the column definitions. */
   char *zCreateSql;
-  rc = ParseColumnsAndGenerateCreate(nCols, argv + kTypeCol,
+  rc = ParseColumnsAndGenerateCreate(pRecover->nCols, argv + kTypeCol,
                                      &zCreateSql, pRecover->pTypes, pzErr);
   if( rc!=SQLITE_OK ){
     recoverRelease(pRecover);
diff --git a/third_party/sqlite/src/test/recover.test b/third_party/sqlite/src/test/recover.test
new file mode 100644
index 0000000..7c5a363
--- /dev/null
+++ b/third_party/sqlite/src/test/recover.test
@@ -0,0 +1,113 @@
+# 2012 January 11 {}
+#
+# 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.
+#
+#***********************************************************************
+# This file implements regression tests for SQLite library.
+#
+# This file implements tests for the recover module, which can read
+# through corrupt rows and pages.
+#
+# $Id$
+
+# TODO(shess): These all test that the module correctly reads good
+# data.  It would be good to implement tests of corrupt data.
+
+set testdir [file dirname $argv0]
+source $testdir/tester.tcl
+
+db eval {
+  DROP TABLE IF EXISTS altered;
+  CREATE TABLE altered (
+    c TEXT
+  );
+  INSERT INTO altered VALUES ('a');
+  INSERT INTO altered VALUES ('b');
+  INSERT INTO altered VALUES ('c');
+  ALTER TABLE altered ADD COLUMN i INTEGER NOT NULL DEFAULT 10;
+  INSERT INTO altered VALUES ('d', 5);
+}
+
+# SQLite will fill the earlier rows with the default.
+do_test recover-alter-1.0 {
+  execsql {SELECT c, i FROM altered ORDER BY rowid}
+} {a 10 b 10 c 10 d 5}
+
+# recover sees NULL for those rows.
+do_test recover-alter-1.1 {
+  db eval {
+    DROP TABLE IF EXISTS temp.altered_recover;
+    CREATE VIRTUAL TABLE temp.altered_recover USING recover(
+      altered,
+      c TEXT,
+      i INTEGER
+    );
+  }
+  execsql {SELECT c, i FROM altered_recover ORDER BY rowid}
+} {a {} b {} c {} d 5}
+
+# Can skip those NULL columns like if they contained a real NULL.
+do_test recover-alter-1.2 {
+  db eval {
+    DROP TABLE IF EXISTS temp.altered_recover;
+    CREATE VIRTUAL TABLE temp.altered_recover USING recover(
+      altered,
+      c TEXT,
+      i INTEGER NOT NULL
+    );
+  }
+  execsql {SELECT c, i FROM altered_recover ORDER BY rowid}
+} {d 5}
+
+if {0} {
+# It would be neat if this could work.  I tried putting "DEFAULT ..."
+# in the schema exposed by the recover table, but it doesn't do the
+# trick.
+do_test recover-alter-1.2 {
+  db eval {
+    DROP TABLE IF EXISTS temp.altered_recover;
+    CREATE VIRTUAL TABLE temp.altered_recover USING recover(
+      altered,
+      c TEXT,
+      i INTEGER NOT NULL DEFAULT 10
+    );
+  }
+  execsql {SELECT c, i FROM altered_recover ORDER BY rowid}
+} {a 10 b 10 c 10 d 5}
+}
+
+# Helper function to generate an arbitrarily-sized table.
+proc generate {table base count} {
+  db eval "DROP TABLE IF EXISTS $table"
+  db transaction immediate {
+    db eval "CREATE TABLE $table (t TEXT,n INT)"
+    for {set i 0} {$i<$count} {incr i} {
+      set t [concat $base $i]
+      db eval [concat {INSERT INTO} $table {VALUES ($t, $i)}]
+    }
+  }
+}
+
+# Leaf-only database parses.
+do_test recover-leaf-1.0 {
+  db close
+  sqlite3 db test.db
+  generate "leaf" "Leaf-node-generating line " 10
+
+  db eval {
+    DROP TABLE IF EXISTS temp.leaf_recover;
+    CREATE VIRTUAL TABLE temp.leaf_recover USING recover(
+      leaf,
+      t TEXT,
+      n INTEGER
+    )
+  }
+  execsql {SELECT t, n FROM leaf_recover ORDER BY rowid}
+} {{Leaf-node-generating line 0} 0 {Leaf-node-generating line 1} 1 {Leaf-node-generating line 2} 2 {Leaf-node-generating line 3} 3 {Leaf-node-generating line 4} 4 {Leaf-node-generating line 5} 5 {Leaf-node-generating line 6} 6 {Leaf-node-generating line 7} 7 {Leaf-node-generating line 8} 8 {Leaf-node-generating line 9} 9}
+
+finish_test
diff --git a/third_party/sqlite/src/test/recover1.test b/third_party/sqlite/src/test/recover1.test
index e38531b..c3541b7 100644
--- a/third_party/sqlite/src/test/recover1.test
+++ b/third_party/sqlite/src/test/recover1.test
@@ -279,4 +279,60 @@ do_test recover-types-6.1 {
   execsql {SELECT rowid, id, rowtype, value, TYPEOF(value) FROM types2_recover}
 } {1 1 NULL {} null 2 2 INTEGER 17 integer 3 3 FLOAT 3.1415927 real 4 4 TEXT {This is text} text 5 5 BLOB {This is a blob} blob}
 
+# Check that each of the possible integer sizes is being decoded.
+# TODO(shess): It would be neat to ACTUALLY test these things.  As-is,
+# this should exercise the code paths, but one needs logging or a
+# debugger to verify that things are stored as expected.
+do_test recover-types-7.0 {
+  db eval {
+    DROP TABLE IF EXISTS integers;
+    CREATE TABLE integers (value);
+
+    -- encoded directly in type info.
+    INSERT INTO integers VALUES (0);
+    INSERT INTO integers VALUES (1);
+
+    -- 8-bit signed.
+    INSERT INTO integers VALUES (2);
+    INSERT INTO integers VALUES (-2);
+    INSERT INTO integers VALUES (127);
+    INSERT INTO integers VALUES (-128);
+
+    -- 16-bit signed.
+    INSERT INTO integers VALUES (12345);
+    INSERT INTO integers VALUES (-12345);
+    INSERT INTO integers VALUES (32767);
+    INSERT INTO integers VALUES (-32768);
+
+    -- 24-bit signed.
+    INSERT INTO integers VALUES (1234567);
+    INSERT INTO integers VALUES (-1234567);
+    INSERT INTO integers VALUES (8388607);
+    INSERT INTO integers VALUES (-8388608);
+
+    -- 32-bit signed.
+    INSERT INTO integers VALUES (1234567890);
+    INSERT INTO integers VALUES (-1234567890);
+    INSERT INTO integers VALUES (2147483647);
+    INSERT INTO integers VALUES (-2147483648);
+
+    -- 48-bit signed.
+    INSERT INTO integers VALUES (123456789012345);
+    INSERT INTO integers VALUES (-123456789012345);
+    INSERT INTO integers VALUES (140737488355327);
+    INSERT INTO integers VALUES (-140737488355328);
+
+    -- 64-bit signed.
+    INSERT INTO integers VALUES (9223372036854775807);
+    INSERT INTO integers VALUES (-9223372036854775808);
+
+    DROP TABLE IF EXISTS integers_recover;
+    CREATE VIRTUAL TABLE temp.integers_recover USING recover(
+      integers,
+      value INTEGER
+    );
+  }
+  execsql {SELECT rowid, value FROM integers_recover}
+} {1 0 2 1 3 2 4 -2 5 127 6 -128 7 12345 8 -12345 9 32767 10 -32768 11 1234567 12 -1234567 13 8388607 14 -8388608 15 1234567890 16 -1234567890 17 2147483647 18 -2147483648 19 123456789012345 20 -123456789012345 21 140737488355327 22 -140737488355328 23 9223372036854775807 24 -9223372036854775808}
+
 finish_test