Index: third_party/sqlite/recover.patch |
diff --git a/third_party/sqlite/recover.patch b/third_party/sqlite/recover.patch |
new file mode 100644 |
index 0000000000000000000000000000000000000000..b601a445142929a41ca5eaf874e2c340dffaec4f |
--- /dev/null |
+++ b/third_party/sqlite/recover.patch |
@@ -0,0 +1,2194 @@ |
+Add new virtual table 'recover' to src/ and the amalgamation. |
+ |
+Since recover.c is in somewhat active development, it is possible that |
+the patch below will not reliably re-create the file. |
+ |
+shess@chromium.org |
+ |
+Generated with: |
+git diff --cached --relative=third_party/sqlite/src --src-prefix='' --dst-prefix='' > third_party/sqlite/recover.patch |
+[--cached because otherwise the diff adding recover.c wasn't generated.] |
+ |
+diff --git Makefile.in Makefile.in |
+index f3239f3..216742c 100644 |
+--- Makefile.in |
++++ Makefile.in |
+@@ -251,6 +251,7 @@ SRC = \ |
+ $(TOP)/src/prepare.c \ |
+ $(TOP)/src/printf.c \ |
+ $(TOP)/src/random.c \ |
++ $(TOP)/src/recover.c \ |
+ $(TOP)/src/resolve.c \ |
+ $(TOP)/src/rowset.c \ |
+ $(TOP)/src/select.c \ |
+diff --git src/sqlite.h.in src/sqlite.h.in |
+index 62b9326..fb76659 100644 |
+--- src/sqlite.h.in |
++++ src/sqlite.h.in |
+@@ -6403,6 +6403,17 @@ int sqlite3_wal_checkpoint_v2( |
+ #define SQLITE_CHECKPOINT_RESTART 2 |
+ |
+ |
++/* Begin recover.patch for Chromium */ |
++/* |
++** Call to initialize the recover virtual-table modules (see recover.c). |
++** |
++** This could be loaded by default in main.c, but that would make the |
++** virtual table available to Web SQL. Breaking it out allows only |
++** selected users to enable it (currently sql/recovery.cc). |
++*/ |
++int recoverVtableInit(sqlite3 *db); |
++/* End recover.patch for Chromium */ |
++ |
+ /* |
+ ** Undo the hack that converts floating point types to integer for |
+ ** builds on processors without floating point support. |
+diff --git tool/mksqlite3c.tcl tool/mksqlite3c.tcl |
+index fa99f2d..df2df07 100644 |
+--- tool/mksqlite3c.tcl |
++++ tool/mksqlite3c.tcl |
+@@ -293,6 +293,8 @@ foreach file { |
+ main.c |
+ notify.c |
+ |
++ recover.c |
++ |
+ fts3.c |
+ fts3_aux.c |
+ fts3_expr.c |
+diff --git src/recover.c src/recover.c |
+new file mode 100644 |
+index 0000000..6430c8b |
+--- /dev/null |
++++ src/recover.c |
+@@ -0,0 +1,2130 @@ |
++/* |
++** 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. |
++*/ |
++/* TODO(shess): THIS MODULE IS STILL EXPERIMENTAL. DO NOT USE IT. */ |
++/* Implements a virtual table "recover" which can be used to recover |
++ * data from a corrupt table. The table is walked manually, with |
++ * corrupt items skipped. Additionally, any errors while reading will |
++ * be skipped. |
++ * |
++ * Given a table with this definition: |
++ * |
++ * CREATE TABLE Stuff ( |
++ * name TEXT PRIMARY KEY, |
++ * value TEXT NOT NULL |
++ * ); |
++ * |
++ * to recover the data from teh table, you could do something like: |
++ * |
++ * -- Attach another database, the original is not trustworthy. |
++ * ATTACH DATABASE '/tmp/db.db' AS rdb; |
++ * -- Create a new version of the table. |
++ * CREATE TABLE rdb.Stuff ( |
++ * name TEXT PRIMARY KEY, |
++ * value TEXT NOT NULL |
++ * ); |
++ * -- This will read the original table's data. |
++ * CREATE VIRTUAL TABLE temp.recover_Stuff using recover( |
++ * main.Stuff, |
++ * name TEXT STRICT NOT NULL, -- only real TEXT data allowed |
++ * value TEXT STRICT NOT NULL |
++ * ); |
++ * -- Corruption means the UNIQUE constraint may no longer hold for |
++ * -- Stuff, so either OR REPLACE or OR IGNORE must be used. |
++ * INSERT OR REPLACE INTO rdb.Stuff (rowid, name, value ) |
++ * SELECT rowid, name, value FROM temp.recover_Stuff; |
++ * DROP TABLE temp.recover_Stuff; |
++ * DETACH DATABASE rdb; |
++ * -- Move db.db to replace original db in filesystem. |
++ * |
++ * |
++ * Usage |
++ * |
++ * Given the goal of dealing with corruption, it would not be safe to |
++ * create a recovery table in the database being recovered. So |
++ * recovery tables must be created in the temp database. They are not |
++ * appropriate to persist, in any case. [As a bonus, sqlite_master |
++ * tables can be recovered. Perhaps more cute than useful, though.] |
++ * |
++ * The parameters are a specifier for the table to read, and a column |
++ * definition for each bit of data stored in that table. The named |
++ * table must be convertable to a root page number by reading the |
++ * sqlite_master table. Bare table names are assumed to be in |
++ * database 0 ("main"), other databases can be specified in db.table |
++ * fashion. |
++ * |
++ * Column definitions are similar to BUT NOT THE SAME AS those |
++ * provided to CREATE statements: |
++ * column-def: column-name [type-name [STRICT] [NOT NULL]] |
++ * type-name: (ANY|ROWID|INTEGER|FLOAT|NUMERIC|TEXT|BLOB) |
++ * |
++ * Only those exact type names are accepted, there is no type |
++ * intuition. The only constraints accepted are STRICT (see below) |
++ * and NOT NULL. Anything unexpected will cause the create to fail. |
++ * |
++ * ANY is a convenience to indicate that manifest typing is desired. |
++ * It is equivalent to not specifying a type at all. The results for |
++ * such columns will have the type of the data's storage. The exposed |
++ * schema will contain no type for that column. |
++ * |
++ * ROWID is used for columns representing aliases to the rowid |
++ * (INTEGER PRIMARY KEY, with or without AUTOINCREMENT), to make the |
++ * concept explicit. Such columns are actually stored as NULL, so |
++ * they cannot be simply ignored. The exposed schema will be INTEGER |
++ * for that column. |
++ * |
++ * NOT NULL causes rows with a NULL in that column to be skipped. It |
++ * also adds NOT NULL to the column in the exposed schema. If the |
++ * table has ever had columns added using ALTER TABLE, then those |
++ * columns implicitly contain NULL for rows which have not been |
++ * updated. [Workaround using COALESCE() in your SELECT statement.] |
++ * |
++ * The created table is read-only, with no indices. Any SELECT will |
++ * be a full-table scan, returning each valid row read from the |
++ * storage of the backing table. The rowid will be the rowid of the |
++ * row from the backing table. "Valid" means: |
++ * - The cell metadata for the row is well-formed. Mainly this means that |
++ * the cell header info describes a payload of the size indicated by |
++ * the cell's payload size. |
++ * - The cell does not run off the page. |
++ * - The cell does not overlap any other cell on the page. |
++ * - The cell contains doesn't contain too many columns. |
++ * - The types of the serialized data match the indicated types (see below). |
++ * |
++ * |
++ * Type affinity versus type storage. |
++ * |
++ * http://www.sqlite.org/datatype3.html describes SQLite's type |
++ * affinity system. The system provides for automated coercion of |
++ * types in certain cases, transparently enough that many developers |
++ * do not realize that it is happening. Importantly, it implies that |
++ * the raw data stored in the database may not have the obvious type. |
++ * |
++ * Differences between the stored data types and the expected data |
++ * types may be a signal of corruption. This module makes some |
++ * allowances for automatic coercion. It is important to be concious |
++ * of the difference between the schema exposed by the module, and the |
++ * data types read from storage. The following table describes how |
++ * the module interprets things: |
++ * |
++ * type schema data STRICT |
++ * ---- ------ ---- ------ |
++ * ANY <none> any any |
++ * ROWID INTEGER n/a n/a |
++ * INTEGER INTEGER integer integer |
++ * FLOAT FLOAT integer or float float |
++ * NUMERIC NUMERIC integer, float, or text integer or float |
++ * TEXT TEXT text or blob text |
++ * BLOB BLOB blob blob |
++ * |
++ * type is the type provided to the recover module, schema is the |
++ * schema exposed by the module, data is the acceptable types of data |
++ * decoded from storage, and STRICT is a modification of that. |
++ * |
++ * A very loose recovery system might use ANY for all columns, then |
++ * use the appropriate sqlite3_column_*() calls to coerce to expected |
++ * types. This doesn't provide much protection if a page from a |
++ * different table with the same column count is linked into an |
++ * inappropriate btree. |
++ * |
++ * A very tight recovery system might use STRICT to enforce typing on |
++ * all columns, preferring to skip rows which are valid at the storage |
++ * level but don't contain the right types. Note that FLOAT STRICT is |
++ * almost certainly not appropriate, since integral values are |
++ * transparently stored as integers, when that is more efficient. |
++ * |
++ * Another option is to use ANY for all columns and inspect each |
++ * result manually (using sqlite3_column_*). This should only be |
++ * necessary in cases where developers have used manifest typing (test |
++ * to make sure before you decide that you aren't using manifest |
++ * typing!). |
++ * |
++ * |
++ * Caveats |
++ * |
++ * Leaf pages not referenced by interior nodes will not be found. |
++ * |
++ * Leaf pages referenced from interior nodes of other tables will not |
++ * be resolved. |
++ * |
++ * Rows referencing invalid overflow pages will be skipped. |
++ * |
++ * SQlite rows have a header which describes how to interpret the rest |
++ * of the payload. The header can be valid in cases where the rest of |
++ * the record is actually corrupt (in the sense that the data is not |
++ * the intended data). This can especially happen WRT overflow pages, |
++ * 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. |
++ */ |
++ |
++#include <assert.h> |
++#include <ctype.h> |
++#include <stdio.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() |
++ * sqlite3PagerAcquire() and sqlite3PagerUnref() |
++ * getVarint(). |
++ */ |
++#include "sqliteInt.h" |
++ |
++/* 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.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) |
++#define MASK_FLOAT (1<<2) |
++#define MASK_TEXT (1<<3) |
++#define MASK_BLOB (1<<4) |
++#define MASK_NULL (1<<5) |
++ |
++/* 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){ |
++ unsigned i; |
++ |
++ /* 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. */ |
++ 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){ |
++ unsigned nCur = 0; /* Byte offset within current varint. */ |
++ unsigned nFound = 0; /* Number of varints found. */ |
++ unsigned i; |
++ |
++ /* In the worst case the decoder takes all 8 bits of the 9th byte. */ |
++ if( nData>=9*n ){ |
++ return 1; |
++ } |
++ |
++ for( i=0; nFound<n && i<nData; ++i ){ |
++ nCur++; |
++ if( nCur==9 || !(pData[i]&0x80) ){ |
++ nFound++; |
++ nCur = 0; |
++ } |
++ } |
++ |
++ return nFound==n; |
++} |
++ |
++/* ctype and str[n]casecmp() can be affected by locale (eg, tr_TR). |
++ * These versions consider only the ASCII space. |
++ */ |
++/* TODO(shess): It may be reasonable to just remove the need for these |
++ * entirely. The module could require "TEXT STRICT NOT NULL", not |
++ * "Text Strict Not Null" or whatever the developer felt like typing |
++ * that day. Handling corrupt data is a PERFECT place to be pedantic. |
++ */ |
++static int ascii_isspace(char c){ |
++ /* From fts3_expr.c */ |
++ return c==' ' || c=='\t' || c=='\n' || c=='\r' || c=='\v' || c=='\f'; |
++} |
++static int ascii_isalnum(int x){ |
++ /* From fts3_tokenizer1.c */ |
++ return (x>='0' && x<='9') || (x>='A' && x<='Z') || (x>='a' && x<='z'); |
++} |
++static int ascii_tolower(int x){ |
++ /* From fts3_tokenizer1.c */ |
++ return (x>='A' && x<='Z') ? x-'A'+'a' : x; |
++} |
++/* TODO(shess): Consider sqlite3_strnicmp() */ |
++static int ascii_strncasecmp(const char *s1, const char *s2, size_t n){ |
++ const unsigned char *us1 = (const unsigned char *)s1; |
++ const unsigned char *us2 = (const unsigned char *)s2; |
++ while( *us1 && *us2 && n && ascii_tolower(*us1)==ascii_tolower(*us2) ){ |
++ us1++, us2++, n--; |
++ } |
++ return n ? ascii_tolower(*us1)-ascii_tolower(*us2) : 0; |
++} |
++static int ascii_strcasecmp(const char *s1, const char *s2){ |
++ /* If s2 is equal through strlen(s1), will exit while() due to s1's |
++ * trailing NUL, and return NUL-s2[strlen(s1)]. |
++ */ |
++ return ascii_strncasecmp(s1, s2, strlen(s1)+1); |
++} |
++ |
++/* For some reason I kept making mistakes with offset calculations. */ |
++static const unsigned char *PageData(DbPage *pPage, unsigned iOffset){ |
++ assert( iOffset<=pPage->nPageSize ); |
++ return (unsigned char *)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( ascii_strcasecmp(db->aDb[i].zName, zName)==0 ){ |
++ pBt = db->aDb[i].pBt; |
++ break; |
++ } |
++ } |
++ if( !pBt ){ |
++ return SQLITE_ERROR; |
++ } |
++ |
++ *pPager = sqlite3BtreePager(pBt); |
++ *pnPageSize = sqlite3BtreeGetPageSize(pBt) - sqlite3BtreeGetReserve(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 ); |
++ return (iSerialType%2)==0; |
++} |
++ |
++/* Returns true if the serialized type represented by iSerialType is |
++ * compatible with the given type mask. |
++ */ |
++static int SerialTypeIsCompatible(u64 iSerialType, unsigned char mask){ |
++ switch( iSerialType ){ |
++ case 0 : return (mask&MASK_NULL)!=0; |
++ case 1 : return (mask&MASK_INTEGER)!=0; |
++ case 2 : return (mask&MASK_INTEGER)!=0; |
++ case 3 : return (mask&MASK_INTEGER)!=0; |
++ case 4 : return (mask&MASK_INTEGER)!=0; |
++ case 5 : return (mask&MASK_INTEGER)!=0; |
++ case 6 : return (mask&MASK_INTEGER)!=0; |
++ case 7 : return (mask&MASK_FLOAT)!=0; |
++ case 8 : return (mask&MASK_INTEGER)!=0; |
++ case 9 : return (mask&MASK_INTEGER)!=0; |
++ case 10 : assert( !"RESERVED TYPE"); return 0; |
++ case 11 : assert( !"RESERVED TYPE"); return 0; |
++ } |
++ return (mask&(SerialTypeIsBlob(iSerialType) ? MASK_BLOB : MASK_TEXT)); |
++} |
++ |
++/* Versions of strdup() with return values appropriate for |
++ * sqlite3_free(). malloc.c has sqlite3DbStrDup()/NDup(), but those |
++ * need sqlite3DbFree(), which seems intrusive. |
++ */ |
++static char *sqlite3_strndup(const char *z, unsigned n){ |
++ char *zNew; |
++ |
++ if( z==NULL ){ |
++ return NULL; |
++ } |
++ |
++ zNew = sqlite3_malloc(n+1); |
++ if( zNew!=NULL ){ |
++ memcpy(zNew, z, n); |
++ zNew[n] = '\0'; |
++ } |
++ return zNew; |
++} |
++static char *sqlite3_strdup(const char *z){ |
++ if( z==NULL ){ |
++ return NULL; |
++ } |
++ return sqlite3_strndup(z, strlen(z)); |
++} |
++ |
++/* Fetch the page number of zTable in zDb from sqlite_master in zDb, |
++ * and put it in *piRootPage. |
++ */ |
++static int getRootPage(sqlite3 *db, const char *zDb, const char *zTable, |
++ u32 *piRootPage){ |
++ char *zSql; /* SQL selecting root page of named element. */ |
++ sqlite3_stmt *pStmt; |
++ int rc; |
++ |
++ if( strcmp(zTable, "sqlite_master")==0 ){ |
++ *piRootPage = 1; |
++ return SQLITE_OK; |
++ } |
++ |
++ zSql = sqlite3_mprintf("SELECT rootpage FROM %s.sqlite_master " |
++ "WHERE type = 'table' AND tbl_name = %Q", |
++ zDb, zTable); |
++ if( !zSql ){ |
++ return SQLITE_NOMEM; |
++ } |
++ |
++ rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0); |
++ sqlite3_free(zSql); |
++ if( rc!=SQLITE_OK ){ |
++ return rc; |
++ } |
++ |
++ /* Require a result. */ |
++ rc = sqlite3_step(pStmt); |
++ if( rc==SQLITE_DONE ){ |
++ rc = SQLITE_CORRUPT; |
++ }else if( rc==SQLITE_ROW ){ |
++ *piRootPage = sqlite3_column_int(pStmt, 0); |
++ |
++ /* Require only one result. */ |
++ rc = sqlite3_step(pStmt); |
++ if( rc==SQLITE_DONE ){ |
++ rc = SQLITE_OK; |
++ }else if( rc==SQLITE_ROW ){ |
++ rc = SQLITE_CORRUPT; |
++ } |
++ } |
++ sqlite3_finalize(pStmt); |
++ return rc; |
++} |
++ |
++static int getEncoding(sqlite3 *db, const char *zDb, int* piEncoding){ |
++ sqlite3_stmt *pStmt; |
++ int rc; |
++ char *zSql = sqlite3_mprintf("PRAGMA %s.encoding", zDb); |
++ if( !zSql ){ |
++ return SQLITE_NOMEM; |
++ } |
++ |
++ rc = sqlite3_prepare_v2(db, zSql, -1, &pStmt, 0); |
++ sqlite3_free(zSql); |
++ if( rc!=SQLITE_OK ){ |
++ return rc; |
++ } |
++ |
++ /* Require a result. */ |
++ rc = sqlite3_step(pStmt); |
++ if( rc==SQLITE_DONE ){ |
++ /* This case should not be possible. */ |
++ rc = SQLITE_CORRUPT; |
++ }else if( rc==SQLITE_ROW ){ |
++ if( sqlite3_column_type(pStmt, 0)==SQLITE_TEXT ){ |
++ const char* z = (const char *)sqlite3_column_text(pStmt, 0); |
++ /* These strings match the literals in pragma.c. */ |
++ if( !strcmp(z, "UTF-16le") ){ |
++ *piEncoding = SQLITE_UTF16LE; |
++ }else if( !strcmp(z, "UTF-16be") ){ |
++ *piEncoding = SQLITE_UTF16BE; |
++ }else if( !strcmp(z, "UTF-8") ){ |
++ *piEncoding = SQLITE_UTF8; |
++ }else{ |
++ /* This case should not be possible. */ |
++ *piEncoding = SQLITE_UTF8; |
++ } |
++ }else{ |
++ /* This case should not be possible. */ |
++ *piEncoding = SQLITE_UTF8; |
++ } |
++ |
++ /* Require only one result. */ |
++ rc = sqlite3_step(pStmt); |
++ if( rc==SQLITE_DONE ){ |
++ rc = SQLITE_OK; |
++ }else if( rc==SQLITE_ROW ){ |
++ /* This case should not be possible. */ |
++ rc = SQLITE_CORRUPT; |
++ } |
++ } |
++ sqlite3_finalize(pStmt); |
++ return rc; |
++} |
++ |
++/* Cursor for iterating interior nodes. Interior page cells contain a |
++ * child 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 page 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. |
++ * |
++ * Logically, interiorCursorNextPage() returns the next child page |
++ * number from the page the cursor is currently reading, calling the |
++ * parent cursor as necessary to get new pages to read, until done. |
++ * SQLITE_ROW if a page is returned, SQLITE_DONE if out of pages, |
++ * error otherwise. Unfortunately, if the table is corrupted |
++ * unexpected pages can be returned. If any unexpected page is found, |
++ * leaf or otherwise, it is returned to the caller for processing, |
++ * with the interior cursor left empty. The next call to |
++ * interiorCursorNextPage() will recurse to the parent cursor until an |
++ * interior page to iterate is returned. |
++ * |
++ * Note that while interiorCursorNextPage() will refuse to follow |
++ * loops, it does not keep track of pages returned for purposes of |
++ * preventing duplication. |
++ * |
++ * Note that interiorCursorEOF() could return false (not at EOF), and |
++ * interiorCursorNextPage() could still return SQLITE_DONE. This |
++ * could happen if there are more cells to iterate in an interior |
++ * page, but those cells refer to invalid pages. |
++ */ |
++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){ |
++ /* Destroy all the cursors to the root. */ |
++ 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){ |
++ assert( PageHeader(pPage)[kiPageTypeOffset]==kTableInteriorPage ); |
++ |
++ 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. */ |
++ /* TODO(shess): Sanity-check the count? Page header plus per-cell |
++ * cost of 16-bit offset, 32-bit page number, and one varint |
++ * (minimum 1 byte). |
++ */ |
++ pCursor->nChildren = decodeUnsigned16(PageHeader(pPage) + |
++ kiPageCellCountOffset) + 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){ |
++ const unsigned char *pPageHeader; /* Header of the current page. */ |
++ const unsigned char *pCellOffsets; /* Offset to page's cell offsets. */ |
++ unsigned iCellOffset; /* Offset of target cell. */ |
++ |
++ assert( pCursor->iChild<pCursor->nChildren ); |
++ |
++ /* Rightmost child is in the header. */ |
++ pPageHeader = PageHeader(pCursor->pPage); |
++ if( pCursor->iChild==pCursor->nChildren-1 ){ |
++ return decodeUnsigned32(pPageHeader + kiPageRightChildOffset); |
++ } |
++ |
++ /* 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 |
++ * module ignores ordering). The offset is from the beginning of the |
++ * page, not from the page header. |
++ */ |
++ pCellOffsets = pPageHeader + kiPageInteriorHeaderBytes; |
++ iCellOffset = decodeUnsigned16(pCellOffsets + pCursor->iChild*2); |
++ if( iCellOffset<=pCursor->nPageSize-4 ){ |
++ return decodeUnsigned32(PageData(pCursor->pPage, iCellOffset)); |
++ } |
++ |
++ /* 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; |
++} |
++ |
++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; |
++} |
++ |
++/* 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; |
++} |
++ |
++/* Get the next page from the interior cursor at *ppCursor. Returns |
++ * SQLITE_ROW with the page in *ppPage, or SQLITE_DONE if out of |
++ * pages, or the error SQLite returned. |
++ * |
++ * If the tree is uneven, then when the cursor attempts to get a new |
++ * interior page from the parent cursor, it may get a non-interior |
++ * page. In that case, the new page is returned, and *ppCursor is |
++ * updated to point to the parent cursor (this cursor is freed). |
++ */ |
++/* TODO(shess): I've tried to avoid recursion in most of this code, |
++ * but this case is more challenging because the recursive call is in |
++ * the middle of operation. One option for converting it without |
++ * adding memory management would be to retain the head pointer and |
++ * use a helper to "back up" as needed. Another option would be to |
++ * reverse the list during traversal. |
++ */ |
++static int interiorCursorNextPage(RecoverInteriorCursor **ppCursor, |
++ DbPage **ppPage){ |
++ RecoverInteriorCursor *pCursor = *ppCursor; |
++ while( 1 ){ |
++ int rc; |
++ const unsigned char *pPageHeader; /* Header of found page. */ |
++ |
++ /* Find a valid child page which isn't on the stack. */ |
++ 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; |
++ } |
++ } |
++ } |
++ |
++ /* This page has no more children. Get next page from parent. */ |
++ if( !pCursor->pParent ){ |
++ return SQLITE_DONE; |
++ } |
++ rc = interiorCursorNextPage(&pCursor->pParent, ppPage); |
++ if( rc!=SQLITE_ROW ){ |
++ return rc; |
++ } |
++ |
++ /* If a non-interior page is received, that either means that the |
++ * tree is uneven, or that a child was re-used (say as an overflow |
++ * page). Remove this cursor and let the caller handle the page. |
++ */ |
++ pPageHeader = PageHeader(*ppPage); |
++ if( pPageHeader[kiPageTypeOffset]!=kTableInteriorPage ){ |
++ *ppCursor = pCursor->pParent; |
++ pCursor->pParent = NULL; |
++ interiorCursorDestroy(pCursor); |
++ return SQLITE_ROW; |
++ } |
++ |
++ /* Iterate the new page. */ |
++ interiorCursorSetPage(pCursor, *ppPage); |
++ *ppPage = NULL; |
++ } |
++ |
++ assert(NULL); /* NOTREACHED() */ |
++ return SQLITE_CORRUPT; |
++} |
++ |
++/* Large rows are spilled to overflow pages. The row's main page |
++ * stores the overflow page number after the local payload, with a |
++ * linked list forward from there as necessary. overflowMaybeCreate() |
++ * and overflowGetSegment() provide an abstraction for accessing such |
++ * data while centralizing the code. |
++ * |
++ * 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. |
++ */ |
++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); |
++ } |
++} |
++ |
++/* Internal helper. Used to detect if iPage would cause a loop. */ |
++static int overflowPageInUse(RecoverOverflow *pOverflow, unsigned iPage){ |
++ while( pOverflow && pOverflow->pPage->pgno!=iPage ){ |
++ pOverflow = pOverflow->pNextOverflow; |
++ } |
++ return pOverflow!=NULL; |
++} |
++ |
++/* Setup to access an nRecordBytes record beginning at iRecordOffset |
++ * in pPage. If nRecordBytes can be satisfied entirely from pPage, |
++ * then no overflow pages are needed an *pnLocalRecordBytes is set to |
++ * nRecordBytes. Otherwise, *ppOverflow is set to the head of a list |
++ * of overflow pages, and *pnLocalRecordBytes is set to the number of |
++ * bytes local to pPage. |
++ * |
++ * overflowGetSegment() will do the right thing regardless of whether |
++ * those values are set to be in-page or not. |
++ */ |
++static int overflowMaybeCreate(DbPage *pPage, unsigned nPageSize, |
++ unsigned iRecordOffset, unsigned nRecordBytes, |
++ unsigned *pnLocalRecordBytes, |
++ RecoverOverflow **ppOverflow){ |
++ unsigned nLocalRecordBytes; /* Record bytes in the leaf page. */ |
++ unsigned iNextPage; /* Next page number for record data. */ |
++ unsigned nBytes; /* Maximum record bytes as of current page. */ |
++ int rc; |
++ RecoverOverflow *pFirstOverflow; /* First in linked list of pages. */ |
++ RecoverOverflow *pLastOverflow; /* End of linked list. */ |
++ |
++ /* Calculations from the "Table B-Tree Leaf Cell" part of section |
++ * 1.5 of http://www.sqlite.org/fileformat2.html . maxLocal and |
++ * minLocal to match naming in btree.c. |
++ */ |
++ const unsigned maxLocal = nPageSize - 35; |
++ const unsigned minLocal = ((nPageSize-12)*32/255)-23; /* m */ |
++ |
++ /* Always fit anything smaller than maxLocal. */ |
++ if( nRecordBytes<=maxLocal ){ |
++ *pnLocalRecordBytes = nRecordBytes; |
++ *ppOverflow = NULL; |
++ return SQLITE_OK; |
++ } |
++ |
++ /* Calculate the remainder after accounting for minLocal on the leaf |
++ * page and what packs evenly into overflow pages. If the remainder |
++ * does not fit into maxLocal, then a partially-full overflow page |
++ * will be required in any case, so store as little as possible locally. |
++ */ |
++ nLocalRecordBytes = minLocal+((nRecordBytes-minLocal)%(nPageSize-4)); |
++ if( maxLocal<nLocalRecordBytes ){ |
++ nLocalRecordBytes = minLocal; |
++ } |
++ |
++ /* Don't read off the end of the page. */ |
++ if( iRecordOffset+nLocalRecordBytes+4>nPageSize ){ |
++ return SQLITE_CORRUPT; |
++ } |
++ |
++ /* First overflow page number is after the local bytes. */ |
++ iNextPage = |
++ decodeUnsigned32(PageData(pPage, iRecordOffset + nLocalRecordBytes)); |
++ nBytes = nLocalRecordBytes; |
++ |
++ /* While there are more pages to read, and more bytes are needed, |
++ * get another page. |
++ */ |
++ pFirstOverflow = pLastOverflow = NULL; |
++ rc = SQLITE_OK; |
++ while( iNextPage && nBytes<nRecordBytes ){ |
++ RecoverOverflow *pOverflow; /* New overflow page for the list. */ |
++ |
++ rc = sqlite3PagerAcquire(pPage->pPager, iNextPage, &pPage, 0); |
++ if( rc!=SQLITE_OK ){ |
++ break; |
++ } |
++ |
++ 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; |
++ |
++ iNextPage = decodeUnsigned32(pPage->pData); |
++ nBytes += nPageSize-4; |
++ |
++ /* Avoid loops. */ |
++ if( overflowPageInUse(pFirstOverflow, iNextPage) ){ |
++ fprintf(stderr, "Overflow loop detected at %d\n", iNextPage); |
++ rc = SQLITE_CORRUPT; |
++ break; |
++ } |
++ } |
++ |
++ /* If there were not enough pages, or too many, things are corrupt. |
++ * Not having enough pages is an obvious problem, all the data |
++ * cannot be read. Too many pages means that the contents of the |
++ * row between the main page and the overflow page(s) is |
++ * inconsistent (most likely one or more of the overflow pages does |
++ * not really belong to this row). |
++ */ |
++ if( rc==SQLITE_OK && (nBytes<nRecordBytes || iNextPage) ){ |
++ rc = SQLITE_CORRUPT; |
++ } |
++ |
++ if( rc==SQLITE_OK ){ |
++ *ppOverflow = pFirstOverflow; |
++ *pnLocalRecordBytes = nLocalRecordBytes; |
++ }else if( pFirstOverflow ){ |
++ overflowDestroy(pFirstOverflow); |
++ } |
++ return rc; |
++} |
++ |
++/* Use in concert with overflowMaybeCreate() to efficiently read parts |
++ * of a potentially-overflowing record. pPage and iRecordOffset are |
++ * the values passed into overflowMaybeCreate(), nLocalRecordBytes and |
++ * pOverflow are the values returned by that call. |
++ * |
++ * On SQLITE_OK, *ppBase points to nRequestBytes of data at |
++ * iRequestOffset within the record. If the data exists contiguously |
++ * in a page, a direct pointer is returned, otherwise a buffer from |
++ * sqlite3_malloc() is returned with the data. *pbFree is set true if |
++ * sqlite3_free() should be called on *ppBase. |
++ */ |
++/* Operation of this function is subtle. At any time, pPage is the |
++ * current page, with iRecordOffset and nLocalRecordBytes being record |
++ * data within pPage, and pOverflow being the overflow page after |
++ * pPage. This allows the code to handle both the initial leaf page |
++ * and overflow pages consistently by adjusting the values |
++ * appropriately. |
++ */ |
++static int overflowGetSegment(DbPage *pPage, unsigned iRecordOffset, |
++ unsigned nLocalRecordBytes, |
++ RecoverOverflow *pOverflow, |
++ unsigned iRequestOffset, unsigned nRequestBytes, |
++ unsigned char **ppBase, int *pbFree){ |
++ unsigned nBase; /* Amount of data currently collected. */ |
++ unsigned char *pBase; /* Buffer to collect record data into. */ |
++ |
++ /* Skip to the page containing the start of the data. */ |
++ while( iRequestOffset>=nLocalRecordBytes && pOverflow ){ |
++ /* Factor out current page's contribution. */ |
++ iRequestOffset -= nLocalRecordBytes; |
++ |
++ /* Move forward to the next page in the list. */ |
++ pPage = pOverflow->pPage; |
++ iRecordOffset = 4; |
++ nLocalRecordBytes = pOverflow->nPageSize - iRecordOffset; |
++ pOverflow = pOverflow->pNextOverflow; |
++ } |
++ |
++ /* If the requested data is entirely within this page, return a |
++ * pointer into the page. |
++ */ |
++ if( iRequestOffset+nRequestBytes<=nLocalRecordBytes ){ |
++ /* TODO(shess): "assignment discards qualifiers from pointer target type" |
++ * Having ppBase be const makes sense, but sqlite3_free() takes non-const. |
++ */ |
++ *ppBase = (unsigned char *)PageData(pPage, iRecordOffset + iRequestOffset); |
++ *pbFree = 0; |
++ return SQLITE_OK; |
++ } |
++ |
++ /* The data range would require additional pages. */ |
++ if( !pOverflow ){ |
++ /* Should never happen, the range is outside the nRecordBytes |
++ * passed to overflowMaybeCreate(). |
++ */ |
++ assert(NULL); /* NOTREACHED */ |
++ return SQLITE_ERROR; |
++ } |
++ |
++ /* Get a buffer to construct into. */ |
++ nBase = 0; |
++ pBase = sqlite3_malloc(nRequestBytes); |
++ if( !pBase ){ |
++ return SQLITE_NOMEM; |
++ } |
++ while( nBase<nRequestBytes ){ |
++ /* Copy over data present on this page. */ |
++ unsigned nCopyBytes = nRequestBytes - nBase; |
++ if( nLocalRecordBytes-iRequestOffset<nCopyBytes ){ |
++ nCopyBytes = nLocalRecordBytes - iRequestOffset; |
++ } |
++ memcpy(pBase + nBase, PageData(pPage, iRecordOffset + iRequestOffset), |
++ nCopyBytes); |
++ nBase += nCopyBytes; |
++ |
++ if( pOverflow ){ |
++ /* Copy from start of record data in future pages. */ |
++ iRequestOffset = 0; |
++ |
++ /* Move forward to the next page in the list. Should match |
++ * first while() loop. |
++ */ |
++ pPage = pOverflow->pPage; |
++ iRecordOffset = 4; |
++ nLocalRecordBytes = pOverflow->nPageSize - iRecordOffset; |
++ pOverflow = pOverflow->pNextOverflow; |
++ }else if( nBase<nRequestBytes ){ |
++ /* Ran out of overflow pages with data left to deliver. Not |
++ * possible if the requested range fits within nRecordBytes |
++ * passed to overflowMaybeCreate() when creating pOverflow. |
++ */ |
++ assert(NULL); /* NOTREACHED */ |
++ sqlite3_free(pBase); |
++ return SQLITE_ERROR; |
++ } |
++ } |
++ assert( nBase==nRequestBytes ); |
++ *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 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. |
++ * |
++ * leafCursorCellColInfo() accounts for overflow pages in the style of |
++ * overflowGetSegment(). |
++ */ |
++typedef struct RecoverLeafCursor RecoverLeafCursor; |
++struct RecoverLeafCursor { |
++ RecoverInteriorCursor *pParent; /* Parent node to this node. */ |
++ 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 nLocalRecordBytes; /* Amount of record data in-page. */ |
++ unsigned nRecordHeaderBytes; /* Size of record header data. */ |
++ unsigned char *pRecordHeader; /* Pointer to record header data. */ |
++ int bFreeRecordHeader; /* True if record header requires free. */ |
++ RecoverOverflow *pOverflow; /* Cell overflow info, if needed. */ |
++}; |
++ |
++/* 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. |
++ * |
++ * If pPage is an interior page, a new parent cursor is created and |
++ * injected on the stack. This is necessary to handle trees with |
++ * uneven depth, but also is used during initial setup. |
++ * |
++ * If pPage is not a table page at all, it is discarded. |
++ * |
++ * 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){ |
++ const unsigned char *pPageHeader; /* Header of *pPage */ |
++ |
++ /* Release the current page. */ |
++ if( pCursor->pPage ){ |
++ sqlite3PagerUnref(pCursor->pPage); |
++ pCursor->pPage = NULL; |
++ pCursor->iCell = pCursor->nCells = 0; |
++ } |
++ |
++ /* If the page is an unexpected interior node, inject a new stack |
++ * layer and try again from there. |
++ */ |
++ pPageHeader = PageHeader(pPage); |
++ if( pPageHeader[kiPageTypeOffset]==kTableInteriorPage ){ |
++ RecoverInteriorCursor *pParent; |
++ int rc = interiorCursorCreate(pCursor->pParent, pPage, pCursor->nPageSize, |
++ &pParent); |
++ if( rc!=SQLITE_OK ){ |
++ return rc; |
++ } |
++ pCursor->pParent = pParent; |
++ return SQLITE_OK; |
++ } |
++ |
++ /* Not a leaf page, 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){ |
++ if( !pCursor->pParent ){ |
++ return SQLITE_DONE; |
++ } |
++ |
++ /* Repeatedly load the parent's next child page until a leaf is found. */ |
++ 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 leafCursorDestroyCellData(RecoverLeafCursor *pCursor){ |
++ if( pCursor->bFreeRecordHeader ){ |
++ sqlite3_free(pCursor->pRecordHeader); |
++ } |
++ pCursor->bFreeRecordHeader = 0; |
++ pCursor->pRecordHeader = NULL; |
++ |
++ if( pCursor->pOverflow ){ |
++ overflowDestroy(pCursor->pOverflow); |
++ pCursor->pOverflow = NULL; |
++ } |
++} |
++ |
++static void leafCursorDestroy(RecoverLeafCursor *pCursor){ |
++ leafCursorDestroyCellData(pCursor); |
++ |
++ 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); |
++} |
++ |
++/* 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){ |
++ DbPage *pPage; /* Reference to page at iRootPage. */ |
++ RecoverLeafCursor *pCursor; /* Leaf cursor being constructed. */ |
++ int rc; |
++ |
++ /* Start out with the root page. */ |
++ rc = sqlite3PagerAcquire(pPager, iRootPage, &pPage, 0); |
++ if( rc!=SQLITE_OK ){ |
++ return rc; |
++ } |
++ |
++ 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. */ |
++ 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){ |
++ const unsigned char *pPageHeader; /* Header of current page. */ |
++ const unsigned char *pCellOffsets; /* Pointer to page's cell offsets. */ |
++ unsigned iCellOffset; /* Offset of current cell (iCell). */ |
++ const unsigned char *pCell; /* Pointer to data at iCellOffset. */ |
++ unsigned nCellMaxBytes; /* Maximum local size of iCell. */ |
++ unsigned iEndOffset; /* End of iCell's in-page data. */ |
++ u64 nRecordBytes; /* Expected size of cell, w/overflow. */ |
++ u64 iRowid; /* iCell's rowid (in table). */ |
++ unsigned nRead; /* Amount of cell read. */ |
++ unsigned nRecordHeaderRead; /* Header data read. */ |
++ u64 nRecordHeaderBytes; /* Header size expected. */ |
++ unsigned nRecordCols; /* Columns read from header. */ |
++ u64 nRecordColBytes; /* Bytes in payload for those columns. */ |
++ unsigned i; |
++ int rc; |
++ |
++ assert( pCursor->iCell<pCursor->nCells ); |
++ |
++ leafCursorDestroyCellData(pCursor); |
++ |
++ /* Find the offset to the row. */ |
++ pPageHeader = PageHeader(pCursor->pPage); |
++ pCellOffsets = pPageHeader + knPageLeafHeaderBytes; |
++ iCellOffset = decodeUnsigned16(pCellOffsets + pCursor->iCell*2); |
++ if( iCellOffset>=pCursor->nPageSize ){ |
++ return ValidateError(); |
++ } |
++ |
++ pCell = PageData(pCursor->pPage, iCellOffset); |
++ 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(); |
++ } |
++ |
++ nRead = getVarint(pCell, &nRecordBytes); |
++ assert( iCellOffset+nRead<=pCursor->nPageSize ); |
++ pCursor->nRecordBytes = nRecordBytes; |
++ |
++ nRead += getVarint(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; ++i ){ |
++ const unsigned iOtherOffset = decodeUnsigned16(pCellOffsets + i*2); |
++ if( iOtherOffset>iCellOffset && iOtherOffset<iEndOffset ){ |
++ return ValidateError(); |
++ } |
++ } |
++ |
++ nRecordHeaderRead = getVarint(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); |
++ 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(). |
++ */ |
++static int leafCursorCellColInfo(RecoverLeafCursor *pCursor, |
++ unsigned iCol, u64 *piColType, |
++ unsigned char **ppBase, int *pbFree){ |
++ const unsigned char *pRecordHeader; /* Current cell's header. */ |
++ u64 nRecordHeaderBytes; /* Bytes in pRecordHeader. */ |
++ unsigned nRead; /* Bytes read from header. */ |
++ u64 iColEndOffset; /* Offset to end of column in cell. */ |
++ unsigned nColsSkipped; /* Count columns as procesed. */ |
++ u64 iSerialType; /* Type descriptor for current column. */ |
++ |
++ /* 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. */ |
++ 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); |
++ 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); |
++ iColEndOffset += SerialTypeLength(iSerialType); |
++ nColsSkipped++; |
++ } |
++ |
++ /* Column's data extends past record's end. */ |
++ if( nRecordHeaderBytes+iColEndOffset>pCursor->nRecordBytes ){ |
++ return SQLITE_CORRUPT; |
++ } |
++ |
++ *piColType = iSerialType; |
++ if( ppBase ){ |
++ const u32 nColBytes = SerialTypeLength(iSerialType); |
++ |
++ /* Offset from start of record to beginning of column. */ |
++ const unsigned iColOffset = nRecordHeaderBytes+iColEndOffset-nColBytes; |
++ |
++ return overflowGetSegment(pCursor->pPage, pCursor->iRecordOffset, |
++ pCursor->nLocalRecordBytes, pCursor->pOverflow, |
++ iColOffset, nColBytes, ppBase, pbFree); |
++ } |
++ return SQLITE_OK; |
++} |
++ |
++static int leafCursorNextValidCell(RecoverLeafCursor *pCursor){ |
++ while( 1 ){ |
++ int rc; |
++ |
++ /* Move to the next cell. */ |
++ pCursor->iCell++; |
++ |
++ /* No more cells, get the next leaf. */ |
++ if( pCursor->iCell>=pCursor->nCells ){ |
++ rc = leafCursorNextPage(pCursor); |
++ if( rc!=SQLITE_ROW ){ |
++ return rc; |
++ } |
++ assert( pCursor->iCell==0 ); |
++ } |
++ |
++ /* If the cell is valid, indicate that a row is available. */ |
++ 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 */ |
++ unsigned nCols; /* Number of columns in target table */ |
++ unsigned char *pTypes; /* Types of columns in target table */ |
++}; |
++ |
++/* Internal helper for deleting the module. */ |
++static void recoverRelease(Recover *pRecover){ |
++ sqlite3_free(pRecover->zDb); |
++ sqlite3_free(pRecover->zTable); |
++ sqlite3_free(pRecover->pTypes); |
++ memset(pRecover, 0xA5, sizeof(*pRecover)); |
++ sqlite3_free(pRecover); |
++} |
++ |
++/* Helper function for initializing the module. Forward-declared so |
++ * recoverCreate() and recoverConnect() can see it. |
++ */ |
++static int recoverInit( |
++ sqlite3 *, void *, int, const char *const*, sqlite3_vtab **, char ** |
++); |
++ |
++static int recoverCreate( |
++ sqlite3 *db, |
++ void *pAux, |
++ int argc, const char *const*argv, |
++ sqlite3_vtab **ppVtab, |
++ char **pzErr |
++){ |
++ FNENTRY(); |
++ return recoverInit(db, pAux, argc, argv, ppVtab, pzErr); |
++} |
++ |
++/* This should never be called. */ |
++static int recoverConnect( |
++ sqlite3 *db, |
++ void *pAux, |
++ int argc, const char *const*argv, |
++ sqlite3_vtab **ppVtab, |
++ char **pzErr |
++){ |
++ FNENTRY(); |
++ return recoverInit(db, pAux, argc, argv, ppVtab, pzErr); |
++} |
++ |
++/* No indices supported. */ |
++static int recoverBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdxInfo){ |
++ FNENTRY(); |
++ return SQLITE_OK; |
++} |
++ |
++/* Logically, this should never be called. */ |
++static int recoverDisconnect(sqlite3_vtab *pVtab){ |
++ FNENTRY(); |
++ recoverRelease((Recover*)pVtab); |
++ return SQLITE_OK; |
++} |
++ |
++static int recoverDestroy(sqlite3_vtab *pVtab){ |
++ FNENTRY(); |
++ recoverRelease((Recover*)pVtab); |
++ return SQLITE_OK; |
++} |
++ |
++typedef struct RecoverCursor RecoverCursor; |
++struct RecoverCursor { |
++ sqlite3_vtab_cursor base; |
++ RecoverLeafCursor *pLeafCursor; |
++ int iEncoding; |
++ int bEOF; |
++}; |
++ |
++static int recoverOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){ |
++ Recover *pRecover = (Recover*)pVTab; |
++ u32 iRootPage; /* Root page of the backing table. */ |
++ int iEncoding; /* UTF encoding for backing database. */ |
++ unsigned nPageSize; /* Size of pages in backing database. */ |
++ Pager *pPager; /* Backing database pager. */ |
++ RecoverLeafCursor *pLeafCursor; /* Cursor to read table's leaf pages. */ |
++ RecoverCursor *pCursor; /* Cursor to read rows from leaves. */ |
++ int rc; |
++ |
++ FNENTRY(); |
++ |
++ iRootPage = 0; |
++ rc = getRootPage(pRecover->db, pRecover->zDb, pRecover->zTable, |
++ &iRootPage); |
++ if( rc!=SQLITE_OK ){ |
++ return rc; |
++ } |
++ |
++ iEncoding = 0; |
++ rc = getEncoding(pRecover->db, pRecover->zDb, &iEncoding); |
++ if( rc!=SQLITE_OK ){ |
++ return rc; |
++ } |
++ |
++ rc = GetPager(pRecover->db, pRecover->zDb, &pPager, &nPageSize); |
++ if( rc!=SQLITE_OK ){ |
++ return rc; |
++ } |
++ |
++ rc = leafCursorCreate(pPager, nPageSize, iRootPage, &pLeafCursor); |
++ if( rc!=SQLITE_OK ){ |
++ return rc; |
++ } |
++ |
++ pCursor = sqlite3_malloc(sizeof(RecoverCursor)); |
++ if( !pCursor ){ |
++ leafCursorDestroy(pLeafCursor); |
++ return SQLITE_NOMEM; |
++ } |
++ memset(pCursor, 0, sizeof(*pCursor)); |
++ pCursor->base.pVtab = pVTab; |
++ pCursor->pLeafCursor = pLeafCursor; |
++ pCursor->iEncoding = iEncoding; |
++ |
++ *ppCursor = (sqlite3_vtab_cursor*)pCursor; |
++ return SQLITE_OK; |
++} |
++ |
++static int recoverClose(sqlite3_vtab_cursor *cur){ |
++ RecoverCursor *pCursor = (RecoverCursor*)cur; |
++ FNENTRY(); |
++ if( pCursor->pLeafCursor ){ |
++ leafCursorDestroy(pCursor->pLeafCursor); |
++ pCursor->pLeafCursor = NULL; |
++ } |
++ memset(pCursor, 0xA5, sizeof(*pCursor)); |
++ sqlite3_free(cur); |
++ return SQLITE_OK; |
++} |
++ |
++/* 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 int recoverValidateLeafCell(Recover *pRecover, RecoverCursor *pCursor){ |
++ unsigned i; |
++ |
++ /* If the row's storage has too many columns, skip it. */ |
++ if( leafCursorCellColumns(pCursor->pLeafCursor)>pRecover->nCols ){ |
++ return RecoverInvalidCell(); |
++ } |
++ |
++ /* Skip rows with unexpected types. */ |
++ for( i=0; i<pRecover->nCols; ++i ){ |
++ u64 iType; /* Storage type of column i. */ |
++ int rc; |
++ |
++ /* ROWID alias. */ |
++ if( (pRecover->pTypes[i]&MASK_ROWID) ){ |
++ continue; |
++ } |
++ |
++ 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){ |
++ RecoverCursor *pCursor = (RecoverCursor*)pVtabCursor; |
++ Recover *pRecover = (Recover*)pCursor->base.pVtab; |
++ int rc; |
++ |
++ FNENTRY(); |
++ |
++ /* 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; |
++ } |
++ } |
++ |
++ if( rc==SQLITE_DONE ){ |
++ pCursor->bEOF = 1; |
++ return SQLITE_OK; |
++ } |
++ |
++ assert( rc!=SQLITE_OK ); |
++ return rc; |
++} |
++ |
++static int recoverFilter( |
++ sqlite3_vtab_cursor *pVtabCursor, |
++ int idxNum, const char *idxStr, |
++ int argc, sqlite3_value **argv |
++){ |
++ RecoverCursor *pCursor = (RecoverCursor*)pVtabCursor; |
++ Recover *pRecover = (Recover*)pCursor->base.pVtab; |
++ int rc; |
++ |
++ FNENTRY(); |
++ |
++ /* Load the first cell, and iterate forward if it's not valid. */ |
++ /* TODO(shess): What happens if no cells at all are valid? */ |
++ 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){ |
++ RecoverCursor *pCursor = (RecoverCursor*)pVtabCursor; |
++ FNENTRY(); |
++ return pCursor->bEOF; |
++} |
++ |
++static int recoverColumn(sqlite3_vtab_cursor *cur, sqlite3_context *ctx, int i){ |
++ RecoverCursor *pCursor = (RecoverCursor*)cur; |
++ Recover *pRecover = (Recover*)pCursor->base.pVtab; |
++ u64 iColType; /* Storage type of column i. */ |
++ unsigned char *pColData; /* Column i's data. */ |
++ int shouldFree; /* Non-zero if pColData should be freed. */ |
++ int rc; |
++ |
++ FNENTRY(); |
++ |
++ if( i>=pRecover->nCols ){ |
++ return SQLITE_ERROR; |
++ } |
++ |
++ /* ROWID alias. */ |
++ if( (pRecover->pTypes[i]&MASK_ROWID) ){ |
++ sqlite3_result_int64(ctx, leafCursorCellRowid(pCursor->pLeafCursor)); |
++ return SQLITE_OK; |
++ } |
++ |
++ pColData = NULL; |
++ shouldFree = 0; |
++ rc = leafCursorCellColInfo(pCursor->pLeafCursor, i, &iColType, |
++ &pColData, &shouldFree); |
++ if( rc!=SQLITE_OK ){ |
++ return rc; |
++ } |
++ /* 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 : { |
++ u32 l = SerialTypeLength(iColType); |
++ |
++ /* If pColData was already allocated, arrange to pass ownership. */ |
++ sqlite3_destructor_type pFn = SQLITE_TRANSIENT; |
++ if( shouldFree ){ |
++ pFn = sqlite3_free; |
++ shouldFree = 0; |
++ } |
++ |
++ if( SerialTypeIsBlob(iColType) ){ |
++ sqlite3_result_blob(ctx, pColData, l, pFn); |
++ }else{ |
++ if( pCursor->iEncoding==SQLITE_UTF16LE ){ |
++ sqlite3_result_text16le(ctx, (const void*)pColData, l, pFn); |
++ }else if( pCursor->iEncoding==SQLITE_UTF16BE ){ |
++ sqlite3_result_text16be(ctx, (const void*)pColData, l, pFn); |
++ }else{ |
++ sqlite3_result_text(ctx, (const char*)pColData, l, pFn); |
++ } |
++ } |
++ } break; |
++ } |
++ if( shouldFree ){ |
++ sqlite3_free(pColData); |
++ } |
++ return SQLITE_OK; |
++} |
++ |
++static int recoverRowid(sqlite3_vtab_cursor *pVtabCursor, sqlite_int64 *pRowid){ |
++ RecoverCursor *pCursor = (RecoverCursor*)pVtabCursor; |
++ FNENTRY(); |
++ *pRowid = leafCursorCellRowid(pCursor->pLeafCursor); |
++ return SQLITE_OK; |
++} |
++ |
++static sqlite3_module recoverModule = { |
++ 0, /* iVersion */ |
++ recoverCreate, /* xCreate - create a table */ |
++ recoverConnect, /* xConnect - connect to an existing table */ |
++ recoverBestIndex, /* xBestIndex - Determine search strategy */ |
++ recoverDisconnect, /* xDisconnect - Disconnect from a table */ |
++ recoverDestroy, /* xDestroy - Drop a table */ |
++ recoverOpen, /* xOpen - open a cursor */ |
++ recoverClose, /* xClose - close a cursor */ |
++ recoverFilter, /* xFilter - configure scan constraints */ |
++ recoverNext, /* xNext - advance a cursor */ |
++ recoverEof, /* xEof */ |
++ recoverColumn, /* xColumn - read data */ |
++ 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 */ |
++}; |
++ |
++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 |
++ * ASCII alphanumeric plus '_' at this time. |
++ */ |
++static int findWord(const char *zText, |
++ const char **pzWordStart, const char **pzWordEnd){ |
++ int r; |
++ while( ascii_isspace(*zText) ){ |
++ zText++; |
++ } |
++ *pzWordStart = zText; |
++ while( ascii_isalnum(*zText) || *zText=='_' ){ |
++ zText++; |
++ } |
++ r = zText>*pzWordStart; /* In case pzWordStart==pzWordEnd */ |
++ *pzWordEnd = zText; |
++ return r; |
++} |
++ |
++/* Return true if the next word in zText is zWord, also setting |
++ * *pzContinue to the character after the word. |
++ */ |
++static int expectWord(const char *zText, const char *zWord, |
++ const char **pzContinue){ |
++ const char *zWordStart, *zWordEnd; |
++ if( findWord(zText, &zWordStart, &zWordEnd) && |
++ ascii_strncasecmp(zWord, zWordStart, zWordEnd - zWordStart)==0 ){ |
++ *pzContinue = zWordEnd; |
++ return 1; |
++ } |
++ return 0; |
++} |
++ |
++/* Parse the name and type information out of parameter. In case of |
++ * success, *pzNameStart/End contain the name of the column, |
++ * *pzTypeStart/End contain the top-level type, and *pTypeMask has the |
++ * type mask to use for the column. |
++ */ |
++static int findNameAndType(const char *parameter, |
++ const char **pzNameStart, const char **pzNameEnd, |
++ const char **pzTypeStart, const char **pzTypeEnd, |
++ unsigned char *pTypeMask){ |
++ unsigned nNameLen; /* Length of found name. */ |
++ const char *zEnd; /* Current end of parsed column information. */ |
++ int bNotNull; /* Non-zero if NULL is not allowed for name. */ |
++ int bStrict; /* Non-zero if column requires exact type match. */ |
++ const char *zDummy; /* Dummy parameter, result unused. */ |
++ unsigned i; |
++ |
++ /* strictMask is used for STRICT, strictMask|otherMask if STRICT is |
++ * not supplied. zReplace provides an alternate type to expose to |
++ * the caller. |
++ */ |
++ static struct { |
++ const char *zName; |
++ unsigned char strictMask; |
++ unsigned char otherMask; |
++ const char *zReplace; |
++ } kTypeInfo[] = { |
++ { "ANY", |
++ MASK_INTEGER | MASK_FLOAT | MASK_BLOB | MASK_TEXT | MASK_NULL, |
++ 0, "", |
++ }, |
++ { "ROWID", MASK_INTEGER | MASK_ROWID, 0, "INTEGER", }, |
++ { "INTEGER", MASK_INTEGER | MASK_NULL, 0, NULL, }, |
++ { "FLOAT", MASK_FLOAT | MASK_NULL, MASK_INTEGER, NULL, }, |
++ { "NUMERIC", MASK_INTEGER | MASK_FLOAT | MASK_NULL, MASK_TEXT, NULL, }, |
++ { "TEXT", MASK_TEXT | MASK_NULL, MASK_BLOB, NULL, }, |
++ { "BLOB", MASK_BLOB | MASK_NULL, 0, NULL, }, |
++ }; |
++ |
++ if( !findWord(parameter, pzNameStart, pzNameEnd) ){ |
++ return SQLITE_MISUSE; |
++ } |
++ |
++ /* Manifest typing, accept any storage type. */ |
++ if( !findWord(*pzNameEnd, pzTypeStart, pzTypeEnd) ){ |
++ *pzTypeEnd = *pzTypeStart = ""; |
++ *pTypeMask = MASK_INTEGER | MASK_FLOAT | MASK_BLOB | MASK_TEXT | MASK_NULL; |
++ return SQLITE_OK; |
++ } |
++ |
++ nNameLen = *pzTypeEnd - *pzTypeStart; |
++ for( i=0; i<ArraySize(kTypeInfo); ++i ){ |
++ if( ascii_strncasecmp(kTypeInfo[i].zName, *pzTypeStart, nNameLen)==0 ){ |
++ break; |
++ } |
++ } |
++ if( i==ArraySize(kTypeInfo) ){ |
++ return SQLITE_MISUSE; |
++ } |
++ |
++ zEnd = *pzTypeEnd; |
++ bStrict = 0; |
++ if( expectWord(zEnd, "STRICT", &zEnd) ){ |
++ /* TODO(shess): Ick. But I don't want another single-purpose |
++ * flag, either. |
++ */ |
++ if( kTypeInfo[i].zReplace && !kTypeInfo[i].zReplace[0] ){ |
++ return SQLITE_MISUSE; |
++ } |
++ bStrict = 1; |
++ } |
++ |
++ bNotNull = 0; |
++ if( expectWord(zEnd, "NOT", &zEnd) ){ |
++ if( expectWord(zEnd, "NULL", &zEnd) ){ |
++ bNotNull = 1; |
++ }else{ |
++ /* Anything other than NULL after NOT is an error. */ |
++ return SQLITE_MISUSE; |
++ } |
++ } |
++ |
++ /* Anything else is an error. */ |
++ if( findWord(zEnd, &zDummy, &zDummy) ){ |
++ return SQLITE_MISUSE; |
++ } |
++ |
++ *pTypeMask = kTypeInfo[i].strictMask; |
++ if( !bStrict ){ |
++ *pTypeMask |= kTypeInfo[i].otherMask; |
++ } |
++ if( bNotNull ){ |
++ *pTypeMask &= ~MASK_NULL; |
++ } |
++ if( kTypeInfo[i].zReplace ){ |
++ *pzTypeStart = kTypeInfo[i].zReplace; |
++ *pzTypeEnd = *pzTypeStart + strlen(*pzTypeStart); |
++ } |
++ return SQLITE_OK; |
++} |
++ |
++/* Parse the arguments, placing type masks in *pTypes and the exposed |
++ * schema in *pzCreateSql (for sqlite3_declare_vtab). |
++ */ |
++static int ParseColumnsAndGenerateCreate(unsigned nCols, |
++ const char *const *pCols, |
++ char **pzCreateSql, |
++ unsigned char *pTypes, |
++ char **pzErr){ |
++ unsigned i; |
++ char *zCreateSql = sqlite3_mprintf("CREATE TABLE x("); |
++ if( !zCreateSql ){ |
++ return SQLITE_NOMEM; |
++ } |
++ |
++ for( i=0; i<nCols; i++ ){ |
++ const char *zSep = (i < nCols - 1 ? ", " : ")"); |
++ const char *zNotNull = ""; |
++ const char *zNameStart, *zNameEnd; |
++ const char *zTypeStart, *zTypeEnd; |
++ int rc = findNameAndType(pCols[i], |
++ &zNameStart, &zNameEnd, |
++ &zTypeStart, &zTypeEnd, |
++ &pTypes[i]); |
++ if( rc!=SQLITE_OK ){ |
++ *pzErr = sqlite3_mprintf("unable to parse column %d", i); |
++ sqlite3_free(zCreateSql); |
++ return rc; |
++ } |
++ |
++ if( !(pTypes[i]&MASK_NULL) ){ |
++ zNotNull = " NOT NULL"; |
++ } |
++ |
++ /* Add name and type to the create statement. */ |
++ zCreateSql = sqlite3_mprintf("%z%.*s %.*s%s%s", |
++ zCreateSql, |
++ zNameEnd - zNameStart, zNameStart, |
++ zTypeEnd - zTypeStart, zTypeStart, |
++ zNotNull, zSep); |
++ if( !zCreateSql ){ |
++ return SQLITE_NOMEM; |
++ } |
++ } |
++ |
++ *pzCreateSql = zCreateSql; |
++ return SQLITE_OK; |
++} |
++ |
++/* Helper function for initializing the module. */ |
++/* argv[0] module name |
++ * argv[1] db name for virtual table |
++ * argv[2] virtual table name |
++ * argv[3] backing table name |
++ * argv[4] columns |
++ */ |
++/* TODO(shess): Since connect isn't supported, could inline into |
++ * recoverCreate(). |
++ */ |
++/* TODO(shess): Explore cases where it would make sense to set *pzErr. */ |
++static int recoverInit( |
++ sqlite3 *db, /* Database connection */ |
++ void *pAux, /* unused */ |
++ int argc, const char *const*argv, /* Parameters to CREATE TABLE statement */ |
++ sqlite3_vtab **ppVtab, /* OUT: New virtual table */ |
++ char **pzErr /* OUT: Error message, if any */ |
++){ |
++ const unsigned kTypeCol = 4; /* First argument with column type info. */ |
++ Recover *pRecover; /* Virtual table structure being created. */ |
++ char *zDot; /* Any dot found in "db.table" backing. */ |
++ u32 iRootPage; /* Root page of backing table. */ |
++ char *zCreateSql; /* Schema of created virtual table. */ |
++ int rc; |
++ |
++ /* Require to be in the temp database. */ |
++ if( ascii_strcasecmp(argv[1], "temp")!=0 ){ |
++ *pzErr = sqlite3_mprintf("recover table must be in temp database"); |
++ return SQLITE_MISUSE; |
++ } |
++ |
++ /* Need the backing table and at least one column. */ |
++ if( argc<=kTypeCol ){ |
++ *pzErr = sqlite3_mprintf("no columns specified"); |
++ return SQLITE_MISUSE; |
++ } |
++ |
++ pRecover = sqlite3_malloc(sizeof(Recover)); |
++ 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->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; |
++ } |
++ |
++ pRecover->nCols = argc - kTypeCol; |
++ pRecover->pTypes = sqlite3_malloc(pRecover->nCols); |
++ if( !pRecover->zDb || !pRecover->zTable || !pRecover->pTypes ){ |
++ recoverRelease(pRecover); |
++ return SQLITE_NOMEM; |
++ } |
++ |
++ /* Require the backing table to exist. */ |
++ /* TODO(shess): Be more pedantic about the form of the descriptor |
++ * string. This already fails for poorly-formed strings, simply |
++ * because there won't be a root page, but it would make more sense |
++ * to be explicit. |
++ */ |
++ rc = getRootPage(pRecover->db, pRecover->zDb, pRecover->zTable, &iRootPage); |
++ if( rc!=SQLITE_OK ){ |
++ *pzErr = sqlite3_mprintf("unable to find backing table"); |
++ recoverRelease(pRecover); |
++ return rc; |
++ } |
++ |
++ /* Parse the column definitions. */ |
++ rc = ParseColumnsAndGenerateCreate(pRecover->nCols, argv + kTypeCol, |
++ &zCreateSql, pRecover->pTypes, pzErr); |
++ if( rc!=SQLITE_OK ){ |
++ recoverRelease(pRecover); |
++ return rc; |
++ } |
++ |
++ rc = sqlite3_declare_vtab(db, zCreateSql); |
++ sqlite3_free(zCreateSql); |
++ if( rc!=SQLITE_OK ){ |
++ recoverRelease(pRecover); |
++ return rc; |
++ } |
++ |
++ *ppVtab = (sqlite3_vtab *)pRecover; |
++ return SQLITE_OK; |
++} |