The complete work-in-progress SQLite recover virtual table.

third_party/sqlite/src/src/recover.c

Index: third_party/sqlite/src/src/recover.c
diff --git a/third_party/sqlite/src/src/recover.c b/third_party/sqlite/src/src/recover.c
index d65cc5602dd53fd2f0e3b008882a7b0a624faaad..6f7df47ff6f3a0b04e8223a4866ad213998fb48a 100644
--- a/third_party/sqlite/src/src/recover.c
+++ b/third_party/sqlite/src/src/recover.c
@@ -153,11 +153,60 @@
  * 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 nested cursors.  The
+ * cursors are implemented with this 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 ar 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".
+ *
+ * RecoverInteriorCursor iterates the child pages in an interior table
+ * node described in section 1.5 "B-tree Pages".
+ *
+ * RecoverCursor pulls these together to iterate the rows of a table,
+ * returning results via the SQLite virtual table interface.
+ */
+/* TODO(shess): Some unlinked leaf pages could potentially be found by
+ * looking at the pointer map pages to find pages which reference an
+ * interior node but which that node does not reference.
+ */
+/* TODO(shess): This code assumes UTF8 databases.  Add handling for
+ * UTF16le and UTF16be.
+ */
+/* TODO(shess): The code doesn't monitor the freelist, so it can't
+ * enforce that cells don't overlap free areas.
+ */
+/* TODO(shess): The code is pretty lax WRT interior nodes.  It only
+ * reads the 32-bit child page number from the cell, ignoring the
+ * rowid.  This is probably fine, though.
+ */
+/* TODO(shess): Use auto_vacuum information to figure out which table
+ * a page is from.
+ */
+/* TODO(shess): Review to convert recursive routines into iterative as
+ * appropriate.
+ */
 /* 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.
+ * specify what to do for NULL.  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.
  */
 
 #include <assert.h>
@@ -185,6 +234,9 @@
 
 /* Generic constants and helper functions. */
 
+static const unsigned char kTableLeafPage = 0x0D;
+static const unsigned char kTableInteriorPage = 0x05;
+
 /* Accepted types are specified by a mask.  Conveniently, SQLite's
  * data-storage types use small integers from 1 to 5...
  */
@@ -195,9 +247,128 @@ static const unsigned char kMaskBlob = (1<<SQLITE_BLOB);
 static const unsigned char kMaskText = (1<<SQLITE_TEXT);
 static const unsigned char kMaskRowid = 1;
 
-/* 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 unsigned decodeUnsigned16(const unsigned char *pData){
+  return (pData[0]<<8) + pData[1];
+}
+static unsigned decodeUnsigned32(const unsigned char *pData){
+  return (pData[0]<<24) + (pData[1]<<16) + (pData[2]<<8) + pData[3];
+}
+static int decodeInt8(const unsigned char *pData){
+  return (int)(*pData);
+}
+static int decodeInt16(const unsigned char *pData){
+  return (decodeInt8(pData)<<8) + pData[1];
+}
+static int decodeInt24(const unsigned char *pData){
+  return (decodeInt16(pData)<<8) + pData[2];
+}
+static int decodeInt32(const unsigned char *pData){
+  return (decodeInt24(pData)<<8) + pData[3];
+}
+static i64 decodeInt48(const unsigned char *pData){
+  return (((i64)decodeInt32(pData))<<16) + (pData[4]<<8) + pData[5];
+}
+static i64 decodeInt64(const unsigned char *pData){
+  return (decodeInt48(pData)<<16) + (pData[6]<<8) + pData[7];
+}
+static double decodeFloat64(const unsigned char *pData){
+  u64 x = decodeInt64(pData);
+  return *((double*)(&x));
+}
+
+/* Return 1 if c 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;
+}
+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;
+}
+
+static const unsigned char *PageData(DbPage *pPage, unsigned iOffset){
+  assert( iOffset<=pPage->nPageSize );
+  return pPage->pData + iOffset;
+}
+static const unsigned char *PageHeader(DbPage *pPage){
+  if( pPage->pgno==1 ){
+    return PageData(pPage, 100);
+  }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) ){
+      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".
+ * http://www.sqlite.org/fileformat2.html#record_format
  */
+static u64 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;
+    default :           /* TEXT or BLOB. */
+      return (iSerialType>>1) - 6;
+  }
+  assert( !"UNKNOWN TYPE");
+  return 0;
+}
 /* True if iSerialType refers to a blob. */
 static int SerialTypeIsBlob(u64 iSerialType){
   assert( iSerialType>=12 );
@@ -292,6 +463,749 @@ static int getRootPage(sqlite3 *db, const char *zDb, const char *zTable,
   return rc;
 }
 
+/* Cursor for iterating the table interior nodes.  Each cell contains
+ * a page number and a rowid.  The child page contains items left of
+ * the rowid (less than).  The rightmost page of the subtree is stored
+ * in the header.
+ *
+ * interiorCursorDestroy - release all resources associated with the
+ *                         cursor and any parent cursors.
+ * interiorCursorCreate - create a cursor with the given parent and page.
+ * interiorCursorEOF - returns true if neither the cursor nor the
+ *                     parent cursors can return any more data.
+ * interiorCursorNextPage - fetch the next child page from the cursor.
+ *
+ * interiorCursorNextPage() returns the next child page at the
+ * cursor's level in the table tree.  If the cursor runs out of cells,
+ * the parent is called to provide new nodes at the same level, until
+ * all levels are exhausted.  Non-table pages at the cursor's depth
+ * are skipped, as are pages which would cause a loop, unexpected leaf
+ * table pages are returned to the caller, interior table pages are
+ * loaded and interated.  Returns SQLITE_ROW if a child page is
+ * returned.  SQLITE_DONE can be returned even if interiorCursorEOF()
+ * returned false, for instance if a parent cursor returns a final
+ * non-table page.
+ *
+ * Note that while interiorCursorNextPage() will refuse to follow
+ * loops, it does not keep track of pages returned for purposes of
+ * preventing duplication.
+ */
+typedef struct RecoverInteriorCursor RecoverInteriorCursor;
+struct RecoverInteriorCursor {
+  RecoverInteriorCursor *pParent; /* Parent node to this node. */
+  DbPage *pPage;                  /* Reference to leaf page. */
+  unsigned nPageSize;             /* Size of page. */
+  unsigned nChildren;             /* Number of children on the page. */
+  unsigned iChild;                /* Index of next child to return. */
+};
+
+static void interiorCursorDestroy(RecoverInteriorCursor *pCursor){
+  while( pCursor ){
+    RecoverInteriorCursor *p = pCursor;
+    pCursor = pCursor->pParent;
+
+    if( p->pPage ){
+      sqlite3PagerUnref(p->pPage);
+      p->pPage = NULL;
+    }
+
+    memset(p, 0xA5, sizeof(*p));
+    sqlite3_free(p);
+  }
+}
+
+/* Internal helper.  Reset storage in preparation for iterating pPage. */
+static void interiorCursorSetPage(RecoverInteriorCursor *pCursor,
+                                  DbPage *pPage){
+  if( pCursor->pPage ){
+    sqlite3PagerUnref(pCursor->pPage);
+    pCursor->pPage = NULL;
+  }
+  pCursor->pPage = pPage;
+  pCursor->iChild = 0;
+
+  /* A child for each cell, plus one in the header. */
+  pCursor->nChildren = decodeUnsigned16(PageHeader(pPage) + 3) + 1;
+}
+
+static int interiorCursorCreate(RecoverInteriorCursor *pParent,
+                                DbPage *pPage, int nPageSize,
+                                RecoverInteriorCursor **ppCursor){
+  RecoverInteriorCursor *pCursor =
+    sqlite3_malloc(sizeof(RecoverInteriorCursor));
+  if( !pCursor ){
+    return SQLITE_NOMEM;
+  }
+
+  memset(pCursor, 0, sizeof(*pCursor));
+  pCursor->pParent = pParent;
+  pCursor->nPageSize = nPageSize;
+  interiorCursorSetPage(pCursor, pPage);
+  *ppCursor = pCursor;
+  return SQLITE_OK;
+}
+
+/* Internal helper.  Return the child page number at iChild. */
+static unsigned interiorCursorChildPage(RecoverInteriorCursor *pCursor){
+  assert( pCursor->iChild<pCursor->nChildren );
+
+  /* Rightmost child is in the header. */
+  const unsigned char *pPageHeader = PageHeader(pCursor->pPage);
+  if( pCursor->iChild==pCursor->nChildren-1 ){
+    return decodeUnsigned32(pPageHeader + 8);
+  }
+
+  /* Each cell is a 4-byte integer page number and a varint rowid
+   * which is greater than the rowid of items in that sub-tree.  This
+   * code ignores the latter constraint.  Note that the offset is from
+   * the beginning of the page, not from the header.
+   */
+  const unsigned char *pOffsets = pPageHeader + 12;
+  unsigned offset = decodeUnsigned16(pOffsets + pCursor->iChild*2);
+  if( offset<=pCursor->nPageSize-4 ){
+    return decodeUnsigned32(PageData(pCursor->pPage, offset));
+  }
+
+  /* If the offset is broken, return an invalid page number. */
+  return 0;
+}
+
+static int interiorCursorEOF(RecoverInteriorCursor *pCursor){
+  while( pCursor ){
+    if( pCursor->iChild<pCursor->nChildren ){
+      return 0;
+    }
+    pCursor = pCursor->pParent;
+  }
+  return 1;
+}
+
+/* Internal helper.  Used to detect if iPage would cause a loop. */
+static int interiorCursorPageInUse(RecoverInteriorCursor *pCursor,
+                                   unsigned iPage){
+  while( pCursor ){
+    if( pCursor->pPage->pgno==iPage ){
+      return 1;
+    }
+    pCursor = pCursor->pParent;
+  }
+  return 0;
+}
+
+/* NOTE(shess): This code may recurse up to the parent.  The stack
+ * depth should be proportional to the log of the table size, so it
+ * has not seemed worthwhile to convert it to an iterative form.
+ */
+static int interiorCursorNextPage(RecoverInteriorCursor *pCursor,
+                                  DbPage **ppPage){
+  while( !interiorCursorEOF(pCursor) ){
+    /* This page has no more children.  Get next page from parent. */
+    while( pCursor->iChild>=pCursor->nChildren ){
+      if( !pCursor->pParent ){
+        return SQLITE_DONE;
+      }
+
+      int rc = interiorCursorNextPage(pCursor->pParent, ppPage);
+      if( rc!=SQLITE_ROW ){
+        return rc;
+      }
+
+      const unsigned char *pPageHeader = PageHeader(*ppPage);
+      if( *pPageHeader==kTableLeafPage ){
+        return SQLITE_ROW;
+      }else if( *pPageHeader==kTableInteriorPage ){
+        interiorCursorSetPage(pCursor, *ppPage);
+        *ppPage = NULL;
+      }else{
+        sqlite3PagerUnref(*ppPage);
+        *ppPage = NULL;
+      }
+    }
+
+    /* Find a valid child page which isn't in use. */
+    while( pCursor->iChild<pCursor->nChildren ){
+      const unsigned iPage = interiorCursorChildPage(pCursor);
+      pCursor->iChild++;
+      if( interiorCursorPageInUse(pCursor, iPage) ){
+        fprintf(stderr, "Loop detected at %d\n", iPage);
+      }else{
+        int rc = sqlite3PagerAcquire(pCursor->pPage->pPager, iPage, ppPage, 0);
+        if( rc==SQLITE_OK ){
+          return SQLITE_ROW;
+        }
+      }
+    }
+  }
+  return SQLITE_DONE;
+}
+
+/* Structure for dealing with overflow pages.  The row's main page
+ * stores an overflow page number after the local payload, with
+ * overflow pages forming a linked list forward from there.
+ *
+ * overflowDestroy - releases all resources associated with the structure.
+ * overflowMaybeCreate - create the overflow structure if it is needed
+ *                       to represent the given record.  See function comment.
+ * overflowGetSegment - fetch a segment from the record, accounting
+ *                      for overflow pages.  Segments which are not
+ *                      entirely contained with a page are constructed
+ *                      into a buffer which is returned.  See function comment.
+ */
+/* TODO(shess): Since overflowMaybeCreate() can pass back a NULL, it
+ * might make sense to have overflowDestroy() and overflowGetSegment()
+ * accept a NULL and make appropriate decisions.
+ */
+typedef struct RecoverOverflow RecoverOverflow;
+struct RecoverOverflow {
+  RecoverOverflow *pNextOverflow;
+  DbPage *pPage;
+  unsigned nPageSize;
+};
+
+static void overflowDestroy(RecoverOverflow *pOverflow){
+  while( pOverflow ){
+    RecoverOverflow *p = pOverflow;
+    pOverflow = p->pNextOverflow;
+
+    if( p->pPage ){
+      sqlite3PagerUnref(p->pPage);
+      p->pPage = NULL;
+    }
+
+    memset(p, 0xA5, sizeof(*p));
+    sqlite3_free(p);
+  }
+}
+
+/* The target record paylod begins at iOffset on pPage.  If nBytes can
+ * be satisfied entire in-page, then no overflow pages are needed and
+ * *pnLocalBytes is set to nBytes.  Otherwise, *ppOverflow is set to
+ * the head of a list of overflow pages, and *pnLocalBytes is set to
+ * the number of bytes local to pPage.
+ */
+static int overflowMaybeCreate(DbPage *pPage, unsigned nPageSize,
+                               unsigned iOffset, unsigned nBytes,
+                               unsigned *pnLocalBytes,
+                               RecoverOverflow **ppOverflow){
+  /* Calculations from section 1.5 of
+   * http://www.sqlite.org/fileformat2.html .
+   */
+  if( nBytes<=nPageSize-35 ){
+    *pnLocalBytes = nBytes;
+    *ppOverflow = NULL;
+    return SQLITE_OK;
+  }
+
+  unsigned m = ((nPageSize-12)*32/255)-23;
+  unsigned nLocalBytes = m + ((nBytes - m)%(nPageSize - 4));
+  if( nPageSize-35<nLocalBytes ){
+    nLocalBytes = nPageSize - 35;
+  }
+
+  /* Don't read off the end of the page. */
+  if( iOffset+nLocalBytes+4>nPageSize ){
+    return SQLITE_CORRUPT;
+  }
+
+  unsigned iNextPage = decodeUnsigned32(PageData(pPage, iOffset) + nLocalBytes);
+  int rc = SQLITE_OK;
+  nBytes -= nLocalBytes;
+
+  /* Ends of a linked list of overflow pages, and number of pages. */
+  RecoverOverflow *pFirstOverflow = NULL;
+  RecoverOverflow *pLastOverflow = NULL;
+  unsigned nPages = 0;
+
+  /* While there are more pages to read, and more pages are needed. */
+  while( iNextPage && nPages*(nPageSize-4)<nBytes ){
+    rc = sqlite3PagerAcquire(pPage->pPager, iNextPage, &pPage, 0);
+    if( rc!=SQLITE_OK ){
+      break;
+    }
+
+    RecoverOverflow *pOverflow = sqlite3_malloc(sizeof(RecoverOverflow));
+    if( !pOverflow ){
+      sqlite3PagerUnref(pPage);
+      rc = SQLITE_NOMEM;
+      break;
+    }
+    memset(pOverflow, 0, sizeof(*pOverflow));
+    pOverflow->pPage = pPage;
+    pOverflow->nPageSize = nPageSize;
+
+    if( !pFirstOverflow ){
+      pFirstOverflow = pOverflow;
+    }else{
+      pLastOverflow->pNextOverflow = pOverflow;
+    }
+    pLastOverflow = pOverflow;
+    nPages++;
+    iNextPage = decodeUnsigned32(pPage->pData);
+  }
+
+  /* If there were not enough pages, or too many, things are corrupt. */
+  if( rc==SQLITE_OK && (nPages*(nPageSize-4)<nBytes || iNextPage) ){
+    rc = SQLITE_CORRUPT;
+  }
+
+  if( rc==SQLITE_OK ){
+    *ppOverflow = pFirstOverflow;
+    *pnLocalBytes = nLocalBytes;
+  }else if( pFirstOverflow ){
+    overflowDestroy(pFirstOverflow);
+  }
+  return rc;
+}
+
+/* Gets a record segment, taking into account overflow pages.  pPage
+ * is the initial database page which contains nBytes of row data at
+ * iOffset. iReqOffset and nReqBytes give the target range desired,
+ * offset from the beginning of the record (at iOffset).  The segment
+ * is returned in *ppBase, possibly in an allocated buffer.  If so,
+ * *pbFree is set true and *ppBase should eventually be freed using
+ * sqlite3_free().
+ *
+ * If the request can be satisfied from pPage, then pOverflow can
+ * safely be NULL.
+ */
+static int overflowGetSegment(DbPage *pPage, unsigned iOffset, unsigned nBytes,
+                              RecoverOverflow *pOverflow,
+                              unsigned iReqOffset, unsigned nReqBytes,
+                              unsigned char **ppBase, int *pbFree){
+  /* Skip past initial pages. */
+  while( iReqOffset>=nBytes && pOverflow ){
+    iReqOffset -= nBytes;
+    pPage = pOverflow->pPage;
+    iOffset = 4;
+    nBytes = pOverflow->nPageSize - 4;
+    pOverflow = pOverflow->pNextOverflow;
+  }
+
+  /* If the requested data cannot be satisfied. */
+  if( iReqOffset+nReqBytes>iOffset+nBytes && !pOverflow ){
+    return SQLITE_ERROR;
+  }
+
+  /* If the requested segment is entirely within the local segment,
+   * return an internal pointer.
+   */
+  if( iReqOffset+nReqBytes<=nBytes ){
+    *ppBase = pPage->pData + iOffset + iReqOffset;
+    *pbFree = 0;
+    return SQLITE_OK;
+  }
+
+  /* Construct a buffer by copying pieces from multiple pages. */
+  unsigned char *pBase = sqlite3_malloc(nReqBytes);
+  if( !pBase ){
+    return SQLITE_NOMEM;
+  }
+  unsigned nBase = 0;
+  while( nBase<nReqBytes ){
+    unsigned nCopyBytes = nBytes - iReqOffset;
+    if( nReqBytes-nBase<nCopyBytes ){
+      nCopyBytes = nReqBytes - nBase;
+    }
+    memcpy(pBase + nBase, pPage->pData + iOffset + iReqOffset, nCopyBytes);
+    nBase += nCopyBytes;
+    if( pOverflow ){
+      iReqOffset = 0;
+      pPage = pOverflow->pPage;
+      iOffset = 4;
+      nBytes = pOverflow->nPageSize - 4;
+      pOverflow = pOverflow->pNextOverflow;
+    }else if( nBase<nReqBytes ){
+      /* More data is wanted, but no further overflow pages. */
+      sqlite3_free(pBase);
+      return SQLITE_ERROR;
+    }
+  }
+  assert( nBase==nReqBytes );
+  *ppBase = pBase;
+  *pbFree = 1;
+  return SQLITE_OK;
+}
+
+/* Primary structure for iterating the contents of a table.
+ *
+ * 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 return 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 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.
+ *
+ * leafCursorCellColInfo() accounts for overflow pages using
+ * overflowGetSegment().
+ */
+typedef struct RecoverLeafCursor RecoverLeafCursor;
+struct RecoverLeafCursor {
+  RecoverInteriorCursor *pParent;  /* Parent node to this node. */
+  DbPage *pPage;                   /* Reference to leaf page. */
+  unsigned nPageSize;              /* Size of left page. */
+  unsigned nCells;                 /* Number of cells on the page. */
+  unsigned iCell;                  /* Current cell. */
+
+  /* Info parsed from the current cell's data.  pHeader is necessary
+   * because the header can extend into overflow, though it is usually
+   * in-page.
+   */
+  i64 iRowid;                      /* rowid parsed. */
+  unsigned nCols;                  /* how many data items in the cell. */
+  unsigned iPayloadOffset;         /* offset to payload. */
+  unsigned nPayloadBytes;          /* Size of payload. */
+  unsigned nLocalBytes;            /* In-page portion of payload. */
+  unsigned nHeaderBytes;           /* Size of payload header. */
+  unsigned char *pHeader;          /* Header data for payload. */
+  int bFreeHeader;                 /* True if header needs to be freed. */
+  RecoverOverflow *pOverflow;      /* Cell overflow info, if needed. */
+};
+
+/* Internal helper.  Returns SQLITE_OK if the page is accepted (in
+ * which case the caller no longer owns it).  pPage may be NULL after
+ * this call, in which case the passed page was either an interior
+ * page (in which case it adds a new parent cursor), or a non-table
+ * page.
+ */
+static int leafCursorLoadPage(RecoverLeafCursor *pCursor, DbPage *pPage){
+  if( pCursor->pPage ){
+    sqlite3PagerUnref(pCursor->pPage);
+    pCursor->pPage = NULL;
+  }
+
+  /* If the page is an unexpected interior node, inject a new stack
+   * layer and try again from there.
+   */
+  const unsigned char *pPageHeader = PageHeader(pPage);
+  if( pPageHeader[0]==kTableInteriorPage ){
+    RecoverInteriorCursor *pParent;
+    int rc = interiorCursorCreate(pCursor->pParent, pPage, pCursor->nPageSize,
+                                  &pParent);
+    if( rc!=SQLITE_OK ){
+      return rc;
+    }
+    pCursor->pParent = pParent;
+    return SQLITE_OK;
+  }
+
+  /* If the page is not a leaf node, skip it. */
+  if( pPageHeader[0]!=kTableLeafPage ){
+    sqlite3PagerUnref(pPage);
+    return SQLITE_OK;
+  }
+
+  /* Take ownership of the page and start decoding. */
+  pCursor->pPage = pPage;
+  pCursor->iCell = 0;
+  pCursor->nCells = decodeUnsigned16(pPageHeader + 3);
+  return SQLITE_OK;
+}
+
+static int leafCursorNextPage(RecoverLeafCursor *pCursor){
+  if( !pCursor->pParent ){
+    return SQLITE_DONE;
+  }
+
+  /* Get the next page from the parent and load it, until one sticks
+   * or there are no more pages.
+   */
+  do {
+    DbPage *pNextPage;
+    int rc = interiorCursorNextPage(pCursor->pParent, &pNextPage);
+    if( rc!=SQLITE_ROW ){
+      assert( rc==SQLITE_DONE );
+      return rc;
+    }
+
+    rc = leafCursorLoadPage(pCursor, pNextPage);
+    if( rc!=SQLITE_OK ){
+      sqlite3PagerUnref(pNextPage);
+      return rc;
+    }
+  } while( !pCursor->pPage );
+
+  return SQLITE_ROW;
+}
+
+static void leafCursorDestroy(RecoverLeafCursor *pCursor){
+  if( pCursor->pHeader && pCursor->bFreeHeader ){
+    sqlite3_free(pCursor->pHeader);
+    pCursor->pHeader = NULL;
+  }
+
+  if( pCursor->pOverflow ){
+    overflowDestroy(pCursor->pOverflow);
+    pCursor->pOverflow = NULL;
+  }
+
+  if( pCursor->pParent ){
+    interiorCursorDestroy(pCursor->pParent);
+    pCursor->pParent = NULL;
+  }
+
+  if( pCursor->pPage ){
+    sqlite3PagerUnref(pCursor->pPage);
+    pCursor->pPage = NULL;
+  }
+
+  memset(pCursor, 0xA5, sizeof(*pCursor));
+  sqlite3_free(pCursor);
+}
+
+static int leafCursorCreate(Pager *pPager, int nPageSize,
+                            int 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 ){
+    leafCursorDestroy(pCursor);
+    return rc;
+  }
+  if( !pCursor->pPage ){
+    rc = leafCursorNextPage(pCursor);
+    if( rc!=SQLITE_DONE && rc!=SQLITE_ROW ){
+      leafCursorDestroy(pCursor);
+      return rc;
+    }
+  }
+  /* TODO(shess): What should happen if leafCursorNextPage() returned
+   * SQLITE_DONE?  It means there were no leaf pages, so probably the
+   * cursor should just go directly to EOF.  Without having tested it,
+   * it looks like iCell == nCells == 0, so leafCursorNextValidCell()
+   * will return SQLITE_DONE.  But leafCursorCellSetup() called from
+   * recoverOpen() will not go well.
+   */
+  *ppCursor = pCursor;
+  return SQLITE_OK;
+}
+
+static int ValidateError(){
+  return SQLITE_ERROR;
+}
+
+static int leafCursorCellSetup(RecoverLeafCursor *pCursor){
+  assert( pCursor->iCell<pCursor->nCells );
+
+  if( pCursor->pOverflow ){
+    overflowDestroy(pCursor->pOverflow);
+    pCursor->pOverflow = NULL;
+  }
+
+  /* Find the offset to the row. */
+  const unsigned char *pPageHeader = PageHeader(pCursor->pPage);
+  const unsigned char *pOffsets = pPageHeader + 8;
+  const unsigned iOffset = decodeUnsigned16(pOffsets + pCursor->iCell*2);
+  if( iOffset>=pCursor->nPageSize ){
+    return ValidateError();
+  }
+
+  const unsigned char *pCell = PageData(pCursor->pPage, iOffset);
+  const unsigned nCellMaxBytes = pCursor->nPageSize - iOffset;
+  unsigned l = 0;
+
+  /* B-tree leaf cells lead with varint payload size and varint rowid.
+   * Then there is the 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 + l, nCellMaxBytes - l, 3) ){
+    return ValidateError();
+  }
+
+  u32 nPayloadBytes;
+  l += getVarint32(pCell + l, nPayloadBytes);
+  assert( iOffset+l<=pCursor->nPageSize );
+  pCursor->nPayloadBytes = nPayloadBytes;
+
+  u64 iRowid;  /* Ignored */
+  l += getVarint(pCell + l, &iRowid);
+  assert( iOffset+l<=pCursor->nPageSize );
+  pCursor->iRowid = (i64)iRowid;
+
+  pCursor->iPayloadOffset = iOffset + l;
+
+  int rc = overflowMaybeCreate(pCursor->pPage, pCursor->nPageSize,
+                               iOffset + l, nPayloadBytes,
+                               &pCursor->nLocalBytes, &pCursor->pOverflow);
+  if( rc!=SQLITE_OK ){
+    return ValidateError();
+  }
+
+  /* Check that no other cell overlaps this cell. */
+  int i;
+  const unsigned iEndOffset = iOffset + l + pCursor->nLocalBytes;
+  for( i=0; i<pCursor->nCells; ++i ){
+    const unsigned iOtherOffset = decodeUnsigned16(pOffsets + i*2);
+    if( iOtherOffset>iOffset && iOtherOffset<iEndOffset ){
+      return ValidateError();
+    }
+  }
+
+  unsigned pl = 0;
+  u64 nHeaderBytes;
+  pl = getVarint(pCell + l, &nHeaderBytes);
+  assert( nHeaderBytes<=nPayloadBytes );
+  pCursor->nHeaderBytes = nHeaderBytes;
+
+  /* The header potentially could be large enough to overflow. */
+  rc = overflowGetSegment(pCursor->pPage, iOffset + l, pCursor->nLocalBytes,
+                          pCursor->pOverflow, 0, nHeaderBytes,
+                          &pCursor->pHeader, &pCursor->bFreeHeader);
+  if( rc!=SQLITE_OK ){
+    return ValidateError();
+  }
+
+  u64 nRecordBytes = 0;
+  unsigned nCols = 0;
+  while( pl<nHeaderBytes ){
+    if( !checkVarint(pCursor->pHeader + pl, nHeaderBytes - pl) ){
+      return ValidateError();
+    }
+    u64 iSerialType;
+    pl += getVarint(pCursor->pHeader + pl, &iSerialType);
+    if( iSerialType==10 || iSerialType==11 ){
+      return ValidateError();
+    }
+    nRecordBytes += SerialTypeLength(iSerialType);
+    nCols++;
+  }
+  pCursor->nCols = nCols;
+
+  /* Parsing the header used as many bytes as expected. */
+  if( pl!=nHeaderBytes ){
+    return ValidateError();
+  }
+
+  /* Calculated payload is size of expected payload. */
+  if( nHeaderBytes+nRecordBytes!=nPayloadBytes ){
+    return ValidateError();
+  }
+
+  return SQLITE_OK;
+}
+
+static i64 leafCursorCellRowid(RecoverLeafCursor *pCursor){
+  return pCursor->iRowid;
+}
+
+static unsigned leafCursorCellColumns(RecoverLeafCursor *pCursor){
+  return pCursor->nCols;
+}
+
+/* If ppBase is non-NULL, it and pbFree will be appropriately set
+ * using overflowGetSegment().  If *pbFree is set true, *ppBase must
+ * be freed using sqlite3_free().
+ *
+ * Pass NULL for ppBase to prevent retrieving the data segment.
+ */
+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->nCols ){
+    *piColType = 0;
+    if( ppBase ){
+      *ppBase = 0;
+      *pbFree = 0;
+    }
+    return SQLITE_OK;
+  }
+
+  /* Must be able to decode header size. */
+  const unsigned char *pHeader = pCursor->pHeader;
+  if( !checkVarint(pHeader, pCursor->nHeaderBytes) ){
+    return SQLITE_CORRUPT;
+  }
+
+  u64 nHeaderBytes;
+  unsigned l = getVarint(pHeader, &nHeaderBytes);
+  assert( nHeaderBytes==pCursor->nHeaderBytes );
+
+  u64 nRecordBytes = 0;
+  unsigned iColsSkipped = 0;
+  u64 iSerialType;
+  if( !checkVarint(pHeader + l, nHeaderBytes - l) ){
+    return SQLITE_CORRUPT;
+  }
+  l += getVarint(pHeader + l, &iSerialType);
+  while( iColsSkipped<iCol && l<nHeaderBytes ){
+    nRecordBytes += SerialTypeLength(iSerialType);
+    if( !checkVarint(pHeader + l, nHeaderBytes - l) ){
+      return SQLITE_CORRUPT;
+    }
+    l += getVarint(pHeader + l, &iSerialType);
+    iColsSkipped++;
+  }
+
+  /* Column's data extends past payload end. */
+  const unsigned nColBytes = SerialTypeLength(iSerialType);
+  if( nHeaderBytes+nRecordBytes+nColBytes>pCursor->nPayloadBytes ){
+    return SQLITE_CORRUPT;
+  }
+
+  *piColType = iSerialType;
+  if( ppBase ){
+    return overflowGetSegment(pCursor->pPage,
+                              pCursor->iPayloadOffset + nHeaderBytes,
+                              pCursor->nLocalBytes - nHeaderBytes,
+                              pCursor->pOverflow,
+                              nRecordBytes, nColBytes,
+                              ppBase, pbFree);
+  }
+  return SQLITE_OK;
+}
+
+static int leafCursorNextValidCell(RecoverLeafCursor *pCursor){
+  while( 1 ){
+    /* Move to the next cell. */
+    pCursor->iCell++;
+
+    /* If the leaf is done, get the next leaf. */
+    if( pCursor->iCell>=pCursor->nCells ){
+      int rc = leafCursorNextPage(pCursor);
+      if( rc!=SQLITE_ROW ){
+        return rc;
+      }
+    }
+
+    /* If the cell is valid, indicate that a row is available. */
+    int rc = leafCursorCellSetup(pCursor);
+    if( rc==SQLITE_OK ){
+      return SQLITE_ROW;
+    }
+
+    /* Iterate until done or a valid row is found. */
+    fprintf(stderr, "Skipping invalid cell\n");
+  }
+  return SQLITE_ERROR;
+}
+
 typedef struct Recover Recover;
 struct Recover {
   sqlite3_vtab base;
@@ -363,7 +1277,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;
 };
 
@@ -379,15 +1293,27 @@ static int recoverOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
     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;
@@ -396,40 +1322,67 @@ 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.
- */
-struct {
-  u64 iColType;
-  const char *zTypeName;
-} gMockData[5] = {
-  { 0, "NULL"},
-  { 1, "INTEGER"},
-  { 7, "FLOAT"},
-  { 13, "TEXT"},
-  { 12, "BLOB"},
-};
+/* Helpful place to set a breakpoint. */
+static int RecoverInvalidCell(){
+  return SQLITE_ERROR;
+}
+
+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]&kMaskRowid) ){
+      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(
@@ -438,7 +1391,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 = leafCursorCellSetup(pCursor->pLeafCursor);
+  if( rc!=SQLITE_OK || recoverValidateLeafCell(pRecover, pCursor)!=SQLITE_OK ){
+    return recoverNext(pVtabCursor);
+  }
+
+  return SQLITE_OK;
 }
 
 static int recoverEof(sqlite3_vtab_cursor *pVtabCursor){
@@ -458,29 +1421,58 @@ static int recoverColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){
 
   /* ROWID alias. */
   if( (pRecover->pTypes[i]&kMaskRowid) ){
-    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;
+  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_int(ctx, decodeInt8(pColData)); break;
+    case 2 : sqlite3_result_int(ctx, decodeInt16(pColData)); break;
+    case 3 : sqlite3_result_int(ctx, decodeInt24(pColData)); break;
+      /* TODO(shess): Make sure that this is valid for large values. */
+    case 4 : sqlite3_result_int(ctx, decodeInt32(pColData)); break;
+    case 5 : sqlite3_result_int64(ctx, decodeInt48(pColData)); break;
+    case 6 : sqlite3_result_int64(ctx, decodeInt64(pColData)); 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;
+      }
+
+      u64 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;
 }
@@ -488,7 +1480,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;
 }