[sqlite] iOS running recover virtual table.

third_party/sqlite/ext/recover.c

 /*
 ** 2012 Jan 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.
 */
@@ skipping 192 matching lines @@
  */
 /* 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.
  */
 
 #include <assert.h>
 #include <ctype.h>
+#include <stdint.h>
 #include <stdio.h>
+#include <stdlib.h>
 #include <string.h>
 
-/* 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()
- * sqlite3BtreeGetOptimalReserve()
- * sqlite3PagerGet() and sqlite3PagerUnref()
- * getVarint().
- */
+#if defined(SQLITE_CORE) && !defined(SQLITE_CORE_NOT_REALLY)
+
+/* Compiling as part of SQLite core, pull in internal APIs. */
 #include "sqliteInt.h"
+#define recoverGetVarint(p, v) sqlite3GetVarint(p, v)
+
+#else
+
+/* Compiling as a module outside of SQLite.  Define local versions of some types
+** and functions.  These are copied and modestly adapted from SQLite source
+** code.
+*/
+#include "sqlite3.h"
+
+/* Copied from SQLite internals. */
+typedef uint8_t u8;
+typedef uint32_t u32;
+typedef uint64_t u64;
+typedef int64_t i64;
+
+/*
+** A convenience macro that returns the number of elements in
+** an array.
+*/
+#define ArraySize(X)    ((int)(sizeof(X)/sizeof(X[0])))
+
+/*
+** Bitmasks used by sqlite3GetVarint().  These precomputed constants
+** are defined here rather than simply putting the constant expressions
+** inline in order to work around bugs in the RVT compiler.
+**
+** SLOT_2_0     A mask for  (0x7f<<14) | 0x7f
+**
+** SLOT_4_2_0   A mask for  (0x7f<<28) | SLOT_2_0
+*/
+#define SLOT_2_0     0x001fc07f
+#define SLOT_4_2_0   0xf01fc07f
+
+/*
+** Read a 64-bit variable-length integer from memory starting at p[0].
+** Return the number of bytes read.  The value is stored in *v.
+*/
+static unsigned char recoverGetVarint(const unsigned char *p, u64 *v){
+  u32 a,b,s;
+
+  a = *p;
+  /* a: p0 (unmasked) */
+  if (!(a&0x80))
+  {
+    *v = a;
+    return 1;
+  }
+
+  p++;
+  b = *p;
+  /* b: p1 (unmasked) */
+  if (!(b&0x80))
+  {
+    a &= 0x7f;
+    a = a<<7;
+    a |= b;
+    *v = a;
+    return 2;
+  }
+
+  /* Verify that constants are precomputed correctly */
+  assert( SLOT_2_0 == ((0x7f<<14) | (0x7f)) );
+  assert( SLOT_4_2_0 == ((0xfU<<28) | (0x7f<<14) | (0x7f)) );
+
+  p++;
+  a = a<<14;
+  a |= *p;
+  /* a: p0<<14 | p2 (unmasked) */
+  if (!(a&0x80))
+  {
+    a &= SLOT_2_0;
+    b &= 0x7f;
+    b = b<<7;
+    a |= b;
+    *v = a;
+    return 3;
+  }
+
+  /* CSE1 from below */
+  a &= SLOT_2_0;
+  p++;
+  b = b<<14;
+  b |= *p;
+  /* b: p1<<14 | p3 (unmasked) */
+  if (!(b&0x80))
+  {
+    b &= SLOT_2_0;
+    /* moved CSE1 up */
+    /* a &= (0x7f<<14)|(0x7f); */
+    a = a<<7;
+    a |= b;
+    *v = a;
+    return 4;
+  }
+
+  /* a: p0<<14 | p2 (masked) */
+  /* b: p1<<14 | p3 (unmasked) */
+  /* 1:save off p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
+  /* moved CSE1 up */
+  /* a &= (0x7f<<14)|(0x7f); */
+  b &= SLOT_2_0;
+  s = a;
+  /* s: p0<<14 | p2 (masked) */
+
+  p++;
+  a = a<<14;
+  a |= *p;
+  /* a: p0<<28 | p2<<14 | p4 (unmasked) */
+  if (!(a&0x80))
+  {
+    /* we can skip these cause they were (effectively) done above
+    ** while calculating s */
+    /* a &= (0x7f<<28)|(0x7f<<14)|(0x7f); */
+    /* b &= (0x7f<<14)|(0x7f); */
+    b = b<<7;
+    a |= b;
+    s = s>>18;
+    *v = ((u64)s)<<32 | a;
+    return 5;
+  }
+
+  /* 2:save off p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
+  s = s<<7;
+  s |= b;
+  /* s: p0<<21 | p1<<14 | p2<<7 | p3 (masked) */
+
+  p++;
+  b = b<<14;
+  b |= *p;
+  /* b: p1<<28 | p3<<14 | p5 (unmasked) */
+  if (!(b&0x80))
+  {
+    /* we can skip this cause it was (effectively) done above in calc'ing s */
+    /* b &= (0x7f<<28)|(0x7f<<14)|(0x7f); */
+    a &= SLOT_2_0;
+    a = a<<7;
+    a |= b;
+    s = s>>18;
+    *v = ((u64)s)<<32 | a;
+    return 6;
+  }
+
+  p++;
+  a = a<<14;
+  a |= *p;
+  /* a: p2<<28 | p4<<14 | p6 (unmasked) */
+  if (!(a&0x80))
+  {
+    a &= SLOT_4_2_0;
+    b &= SLOT_2_0;
+    b = b<<7;
+    a |= b;
+    s = s>>11;
+    *v = ((u64)s)<<32 | a;
+    return 7;
+  }
+
+  /* CSE2 from below */
+  a &= SLOT_2_0;
+  p++;
+  b = b<<14;
+  b |= *p;
+  /* b: p3<<28 | p5<<14 | p7 (unmasked) */
+  if (!(b&0x80))
+  {
+    b &= SLOT_4_2_0;
+    /* moved CSE2 up */
+    /* a &= (0x7f<<14)|(0x7f); */
+    a = a<<7;
+    a |= b;
+    s = s>>4;
+    *v = ((u64)s)<<32 | a;
+    return 8;
+  }
+
+  p++;
+  a = a<<15;
+  a |= *p;
+  /* a: p4<<29 | p6<<15 | p8 (unmasked) */
+
+  /* moved CSE2 up */
+  /* a &= (0x7f<<29)|(0x7f<<15)|(0xff); */
+  b &= SLOT_2_0;
+  b = b<<8;
+  a |= b;
+
+  s = s<<4;
+  b = p[-4];
+  b &= 0x7f;
+  b = b>>3;
+  s |= b;
+
+  *v = ((u64)s)<<32 | a;
+
+  return 9;
+}
+#endif
 
 /* For debugging. */
 #if 0
 #define FNENTRY() fprintf(stderr, "In %s\n", __FUNCTION__)
 #else
 #define FNENTRY()
 #endif
 
 /* Generic constants and helper functions. */
 
 static const unsigned char kTableLeafPage = 0x0D;
 static const unsigned char kTableInteriorPage = 0x05;
 
 /* From section 1.2. */
 static const unsigned kiHeaderPageSizeOffset = 16;
 static const unsigned kiHeaderReservedSizeOffset = 20;
 static const unsigned kiHeaderEncodingOffset = 56;
-/* TODO(shess) |static const unsigned| fails creating the header in GetPager()
-** because |knHeaderSize| isn't |constexpr|.  But this isn't C++, either.
-*/
-enum { knHeaderSize = 100};
+static const unsigned knHeaderSize = 100;
 
 /* From section 1.5. */
 static const unsigned kiPageTypeOffset = 0;
-static const unsigned kiPageFreeBlockOffset = 1;
+/*static const unsigned kiPageFreeBlockOffset = 1;*/
 static const unsigned kiPageCellCountOffset = 3;
-static const unsigned kiPageCellContentOffset = 5;
-static const unsigned kiPageFragmentedBytesOffset = 7;
+/*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)
 #define MASK_FLOAT (1<<2)
 #define MASK_TEXT (1<<3)
@@ skipping 148 matching lines @@
 /* TODO(shess): SQLite by default allocates page metadata in a single allocation
 ** such that the page's data and metadata are contiguous, see pcache1AllocPage
 ** in pcache1.c.  I believe this was intended to reduce malloc churn.  It means
 ** that Chromium's automated tooling would be unlikely to see page-buffer
 ** overruns.  I believe that this code is safe, but for now replicate SQLite's
 ** approach with kExcessSpace.
 */
 const int kExcessSpace = 128;
 typedef struct RecoverPage RecoverPage;
 struct RecoverPage {
-  Pgno pgno;                     /* Page number for this page */
+  u32 pgno;                      /* Page number for this page */
   void *pData;                   /* Page data for pgno */
   RecoverPager *pPager;          /* The pager this page is part of */
 };
 
 static void pageDestroy(RecoverPage *pPage){
   sqlite3_free(pPage->pData);
   memset(pPage, 0xA5, sizeof(*pPage));
   sqlite3_free(pPage);
 }
 
@@ skipping 56 matching lines @@
     return PageData(pPage, knHeaderSize);
   }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,
                     RecoverPager **ppPager, unsigned *pnPageSize,
                     int *piEncoding){
-  int rc, iEncoding;
+  int i, rc, iEncoding;
   unsigned nPageSize, nReservedSize;
   unsigned char header[knHeaderSize];
   sqlite3_file *pFile = NULL;
   RecoverPager *pPager;
 
   rc = sqlite3_file_control(db, zName, SQLITE_FCNTL_FILE_POINTER, &pFile);
   if( rc!=SQLITE_OK ) {
     return rc;
   } else if( pFile==NULL ){
     /* The documentation for sqlite3PagerFile() indicates it can return NULL if
@@ skipping 17 matching lines @@
     if( rc==SQLITE_IOERR_SHORT_READ ){
       return SQLITE_CORRUPT;
     }
     return rc;
   }
 
   /* Page size must be a power of two between 512 and 32768 inclusive. */
   nPageSize = decodeUnsigned16(header + kiHeaderPageSizeOffset);
   if( (nPageSize&(nPageSize-1)) || nPageSize>32768 || nPageSize<512 ){
     pFile->pMethods->xUnlock(pFile, SQLITE_LOCK_NONE);
-    return rc;
+    return SQLITE_CORRUPT;
   }
 
   /* Space reserved a the end of the page for extensions.  Usually 0. */
   nReservedSize = header[kiHeaderReservedSizeOffset];
 
   /* 1 for UTF-8, 2 for UTF-16le, 3 for UTF-16be. */
   iEncoding = decodeUnsigned32(header + kiHeaderEncodingOffset);
   if( iEncoding==3 ){
     *piEncoding = SQLITE_UTF16BE;
   } else if( iEncoding==2 ){
     *piEncoding = SQLITE_UTF16LE;
   } else if( iEncoding==1 ){
     *piEncoding = SQLITE_UTF8;
   } else {
     /* This case should not be possible. */
     *piEncoding = SQLITE_UTF8;
   }
+  /*assert( iEncoding==1 || iEncoding==2 || iEncoding==3 );*/
 
   rc = pagerCreate(pFile, nPageSize, &pPager);
   if( rc!=SQLITE_OK ){
     pFile->pMethods->xUnlock(pFile, SQLITE_LOCK_NONE);
     return rc;
   }
 
   *ppPager = pPager;
   *pnPageSize = nPageSize - nReservedSize;
   *piEncoding = iEncoding;
@@ skipping 262 matching lines @@
 
   /* TODO(shess): Check for cell overlaps?  Cells require 4 bytes plus
    * a varint.  Check could be identical to leaf check (or even a
    * shared helper testing for "Cells starting in this range"?).
    */
 
   /* If the offset is broken, return an invalid page number. */
   return 0;
 }
 
+#if 0
 static int interiorCursorEOF(RecoverInteriorCursor *pCursor){
   /* Find a parent with remaining children.  EOF if none found. */
   while( pCursor && pCursor->iChild>=pCursor->nChildren ){
     pCursor = pCursor->pParent;
   }
   return pCursor==NULL;
 }
+#endif
 
 /* Internal helper.  Used to detect if iPage would cause a loop. */
 static int interiorCursorPageInUse(RecoverInteriorCursor *pCursor,
                                    unsigned iPage){
   /* Find any parent using the indicated page. */
   while( pCursor && pCursor->pPage->pgno!=iPage ){
     pCursor = pCursor->pParent;
   }
   return pCursor!=NULL;
 }
@@ skipping 596 matching lines @@
   /* 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();
   }
 
-  nRead = getVarint(pCell, &nRecordBytes);
+  nRead = recoverGetVarint(pCell, &nRecordBytes);
   assert( iCellOffset+nRead<=pCursor->nPageSize );
   pCursor->nRecordBytes = nRecordBytes;
 
-  nRead += getVarint(pCell + nRead, &iRowid);
+  nRead += recoverGetVarint(pCell + nRead, &iRowid);
   assert( iCellOffset+nRead<=pCursor->nPageSize );
   pCursor->iRowid = (i64)iRowid;
 
   pCursor->iRecordOffset = iCellOffset + nRead;
 
   /* Start overflow setup here because nLocalRecordBytes is needed to
    * check cell overlap.
    */
   rc = overflowMaybeCreate(pCursor->pPage, pCursor->nPageSize,
                            pCursor->iRecordOffset, pCursor->nRecordBytes,
                            &pCursor->nLocalRecordBytes,
                            &pCursor->pOverflow);
   if( rc!=SQLITE_OK ){
     return ValidateError();
   }
 
   /* Check that no other cell starts within this cell. */
   iEndOffset = pCursor->iRecordOffset + pCursor->nLocalRecordBytes;
   for( i=0; i<pCursor->nCells && pCellOffsets + i*2 + 2 <= pPageEnd; ++i ){
     const unsigned iOtherOffset = decodeUnsigned16(pCellOffsets + i*2);
     if( iOtherOffset>iCellOffset && iOtherOffset<iEndOffset ){
       return ValidateError();
     }
   }
 
-  nRecordHeaderRead = getVarint(pCell + nRead, &nRecordHeaderBytes);
+  nRecordHeaderRead = recoverGetVarint(pCell + nRead, &nRecordHeaderBytes);
   assert( nRecordHeaderBytes<=nRecordBytes );
   pCursor->nRecordHeaderBytes = nRecordHeaderBytes;
 
   /* Large headers could overflow if pages are small. */
   rc = overflowGetSegment(pCursor->pPage,
                           pCursor->iRecordOffset, pCursor->nLocalRecordBytes,
                           pCursor->pOverflow, 0, nRecordHeaderBytes,
                           &pCursor->pRecordHeader, &pCursor->bFreeRecordHeader);
   if( rc!=SQLITE_OK ){
     return ValidateError();
   }
 
   /* Tally up the column count and size of data. */
   nRecordCols = 0;
   nRecordColBytes = 0;
   while( nRecordHeaderRead<nRecordHeaderBytes ){
     u64 iSerialType;  /* Type descriptor for current column. */
     if( !checkVarint(pCursor->pRecordHeader + nRecordHeaderRead,
                      nRecordHeaderBytes - nRecordHeaderRead) ){
       return ValidateError();
     }
-    nRecordHeaderRead += getVarint(pCursor->pRecordHeader + nRecordHeaderRead,
-                                   &iSerialType);
+    nRecordHeaderRead +=
+        recoverGetVarint(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 ){
@@ skipping 45 matching lines @@
 
   /* Must be able to decode header size. */
   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.
    */
-  nRead = getVarint(pRecordHeader, &nRecordHeaderBytes);
+  nRead = recoverGetVarint(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).
    */
   iColEndOffset = 0;
   nColsSkipped = 0;
   while( nColsSkipped<=iCol && nRead<nRecordHeaderBytes ){
     if( !checkVarint(pRecordHeader + nRead, nRecordHeaderBytes - nRead) ){
       return SQLITE_CORRUPT;
     }
-    nRead += getVarint(pRecordHeader + nRead, &iSerialType);
+    nRead += recoverGetVarint(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;
@@ skipping 374 matching lines @@
   recoverRowid,              /* xRowid - read data */
   0,                         /* xUpdate - write data */
   0,                         /* xBegin - begin transaction */
   0,                         /* xSync - sync transaction */
   0,                         /* xCommit - commit transaction */
   0,                         /* xRollback - rollback transaction */
   0,                         /* xFindFunction - function overloading */
   0,                         /* xRename - rename the table */
 };
 
-CHROMIUM_SQLITE_API
+SQLITE_API
 int recoverVtableInit(sqlite3 *db){
   return sqlite3_create_module_v2(db, "recover", &recoverModule, NULL, 0);
 }
 
 /* This section of code is for parsing the create input and
  * initializing the module.
  */
 
 /* Find the next word in zText and place the endpoints in pzWord*.
  * Returns true if the word is non-empty.  "Word" is defined as
@@ skipping 217 matching lines @@
   if( !pRecover ){
     return SQLITE_NOMEM;
   }
   memset(pRecover, 0, sizeof(*pRecover));
   pRecover->base.pModule = &recoverModule;
   pRecover->db = db;
 
   /* Parse out db.table, assuming main if no dot. */
   zDot = strchr(argv[3], '.');
   if( !zDot ){
-    pRecover->zDb = sqlite3_strdup(db->aDb[0].zName);
+    pRecover->zDb = sqlite3_strdup("main");
     pRecover->zTable = sqlite3_strdup(argv[3]);
   }else if( zDot>argv[3] && zDot[1]!='\0' ){
     pRecover->zDb = sqlite3_strndup(argv[3], zDot - argv[3]);
     pRecover->zTable = sqlite3_strdup(zDot + 1);
   }else{
     /* ".table" or "db." not allowed. */
     *pzErr = sqlite3_mprintf("ill-formed table specifier");
     recoverRelease(pRecover);
     return SQLITE_ERROR;
   }
@@ skipping 29 matching lines @@
   rc = sqlite3_declare_vtab(db, zCreateSql);
   sqlite3_free(zCreateSql);
   if( rc!=SQLITE_OK ){
     recoverRelease(pRecover);
     return rc;
   }
 
   *ppVtab = (sqlite3_vtab *)pRecover;
   return SQLITE_OK;
 }