ext/recover/dbdata.c

   1 /*
   2 ** 2019-04-17
   3 **
   4 ** The author disclaims copyright to this source code.  In place of
   5 ** a legal notice, here is a blessing:
   6 **
   7 **    May you do good and not evil.
   8 **    May you find forgiveness for yourself and forgive others.
   9 **    May you share freely, never taking more than you give.
  10 **
  11 ******************************************************************************
  12 **
  13 ** This file contains an implementation of two eponymous virtual tables,
  14 ** "sqlite_dbdata" and "sqlite_dbptr". Both modules require that the
  15 ** "sqlite_dbpage" eponymous virtual table be available.
  16 **
  17 ** SQLITE_DBDATA:
  18 **   sqlite_dbdata is used to extract data directly from a database b-tree
  19 **   page and its associated overflow pages, bypassing the b-tree layer.
  20 **   The table schema is equivalent to:
  21 **
  22 **     CREATE TABLE sqlite_dbdata(
  23 **       pgno INTEGER,
  24 **       cell INTEGER,
  25 **       field INTEGER,
  26 **       value ANY,
  27 **       schema TEXT HIDDEN
  28 **     );
  29 **
  30 **   IMPORTANT: THE VIRTUAL TABLE SCHEMA ABOVE IS SUBJECT TO CHANGE. IN THE
  31 **   FUTURE NEW NON-HIDDEN COLUMNS MAY BE ADDED BETWEEN "value" AND
  32 **   "schema".
  33 **
  34 **   Each page of the database is inspected. If it cannot be interpreted as
  35 **   a b-tree page, or if it is a b-tree page containing 0 entries, the
  36 **   sqlite_dbdata table contains no rows for that page.  Otherwise, the
  37 **   table contains one row for each field in the record associated with
  38 **   each cell on the page. For intkey b-trees, the key value is stored in
  39 **   field -1.
  40 **
  41 **   For example, for the database:
  42 **
  43 **     CREATE TABLE t1(a, b);     -- root page is page 2
  44 **     INSERT INTO t1(rowid, a, b) VALUES(5, 'v', 'five');
  45 **     INSERT INTO t1(rowid, a, b) VALUES(10, 'x', 'ten');
  46 **
  47 **   the sqlite_dbdata table contains, as well as from entries related to
  48 **   page 1, content equivalent to:
  49 **
  50 **     INSERT INTO sqlite_dbdata(pgno, cell, field, value) VALUES
  51 **         (2, 0, -1, 5     ),
  52 **         (2, 0,  0, 'v'   ),
  53 **         (2, 0,  1, 'five'),
  54 **         (2, 1, -1, 10    ),
  55 **         (2, 1,  0, 'x'   ),
  56 **         (2, 1,  1, 'ten' );
  57 **
  58 **   If database corruption is encountered, this module does not report an
  59 **   error. Instead, it attempts to extract as much data as possible and
  60 **   ignores the corruption.
  61 **
  62 ** SQLITE_DBPTR:
  63 **   The sqlite_dbptr table has the following schema:
  64 **
  65 **     CREATE TABLE sqlite_dbptr(
  66 **       pgno INTEGER,
  67 **       child INTEGER,
  68 **       schema TEXT HIDDEN
  69 **     );
  70 **
  71 **   It contains one entry for each b-tree pointer between a parent and
  72 **   child page in the database.
  73 */
  74
  75 #if !defined(SQLITEINT_H)
  76 #include "sqlite3ext.h"
  77
  78 typedef unsigned char u8;
  79 typedef unsigned int u32;
  80
  81 #endif
  82 SQLITE_EXTENSION_INIT1
  83 #include <string.h>
  84 #include <assert.h>
  85
  86 #ifndef SQLITE_OMIT_VIRTUALTABLE
  87
  88 #define DBDATA_PADDING_BYTES 100
  89
  90 typedef struct DbdataTable DbdataTable;
  91 typedef struct DbdataCursor DbdataCursor;
  92
  93 /* Cursor object */
  94 struct DbdataCursor {
  95   sqlite3_vtab_cursor base;       /* Base class.  Must be first */
  96   sqlite3_stmt *pStmt;            /* For fetching database pages */
  97
  98   int iPgno;                      /* Current page number */
  99   u8 *aPage;                      /* Buffer containing page */
 100   int nPage;                      /* Size of aPage[] in bytes */
 101   int nCell;                      /* Number of cells on aPage[] */
 102   int iCell;                      /* Current cell number */
 103   int bOnePage;                   /* True to stop after one page */
 104   int szDb;
 105   sqlite3_int64 iRowid;
 106
 107   /* Only for the sqlite_dbdata table */
 108   u8 *pRec;                       /* Buffer containing current record */
 109   sqlite3_int64 nRec;             /* Size of pRec[] in bytes */
 110   sqlite3_int64 nHdr;             /* Size of header in bytes */
 111   int iField;                     /* Current field number */
 112   u8 *pHdrPtr;
 113   u8 *pPtr;
 114   u32 enc;                        /* Text encoding */
 115
 116   sqlite3_int64 iIntkey;          /* Integer key value */
 117 };
 118
 119 /* Table object */
 120 struct DbdataTable {
 121   sqlite3_vtab base;              /* Base class.  Must be first */
 122   sqlite3 *db;                    /* The database connection */
 123   sqlite3_stmt *pStmt;            /* For fetching database pages */
 124   int bPtr;                       /* True for sqlite3_dbptr table */
 125 };
 126
 127 /* Column and schema definitions for sqlite_dbdata */
 128 #define DBDATA_COLUMN_PGNO        0
 129 #define DBDATA_COLUMN_CELL        1
 130 #define DBDATA_COLUMN_FIELD       2
 131 #define DBDATA_COLUMN_VALUE       3
 132 #define DBDATA_COLUMN_SCHEMA      4
 133 #define DBDATA_SCHEMA             \
 134       "CREATE TABLE x("           \
 135       "  pgno INTEGER,"           \
 136       "  cell INTEGER,"           \
 137       "  field INTEGER,"          \
 138       "  value ANY,"              \
 139       "  schema TEXT HIDDEN"      \
 140       ")"
 141
 142 /* Column and schema definitions for sqlite_dbptr */
 143 #define DBPTR_COLUMN_PGNO         0
 144 #define DBPTR_COLUMN_CHILD        1
 145 #define DBPTR_COLUMN_SCHEMA       2
 146 #define DBPTR_SCHEMA              \
 147       "CREATE TABLE x("           \
 148       "  pgno INTEGER,"           \
 149       "  child INTEGER,"          \
 150       "  schema TEXT HIDDEN"      \
 151       ")"
 152
 153 /*
 154 ** Connect to an sqlite_dbdata (pAux==0) or sqlite_dbptr (pAux!=0) virtual
 155 ** table.
 156 */
 157 static int dbdataConnect(
 158   sqlite3 *db,
 159   void *pAux,
 160   int argc, const char *const*argv,
 161   sqlite3_vtab **ppVtab,
 162   char **pzErr
 163 ){
 164   DbdataTable *pTab = 0;
 165   int rc = sqlite3_declare_vtab(db, pAux ? DBPTR_SCHEMA : DBDATA_SCHEMA);
 166
 167   (void)argc;
 168   (void)argv;
 169   (void)pzErr;
 170   if( rc==SQLITE_OK ){
 171     pTab = (DbdataTable*)sqlite3_malloc64(sizeof(DbdataTable));
 172     if( pTab==0 ){
 173       rc = SQLITE_NOMEM;
 174     }else{
 175       memset(pTab, 0, sizeof(DbdataTable));
 176       pTab->db = db;
 177       pTab->bPtr = (pAux!=0);
 178     }
 179   }
 180
 181   *ppVtab = (sqlite3_vtab*)pTab;
 182   return rc;
 183 }
 184
 185 /*
 186 ** Disconnect from or destroy a sqlite_dbdata or sqlite_dbptr virtual table.
 187 */
 188 static int dbdataDisconnect(sqlite3_vtab *pVtab){
 189   DbdataTable *pTab = (DbdataTable*)pVtab;
 190   if( pTab ){
 191     sqlite3_finalize(pTab->pStmt);
 192     sqlite3_free(pVtab);
 193   }
 194   return SQLITE_OK;
 195 }
 196
 197 /*
 198 ** This function interprets two types of constraints:
 199 **
 200 **       schema=?
 201 **       pgno=?
 202 **
 203 ** If neither are present, idxNum is set to 0. If schema=? is present,
 204 ** the 0x01 bit in idxNum is set. If pgno=? is present, the 0x02 bit
 205 ** in idxNum is set.
 206 **
 207 ** If both parameters are present, schema is in position 0 and pgno in
 208 ** position 1.
 209 */
 210 static int dbdataBestIndex(sqlite3_vtab *tab, sqlite3_index_info *pIdx){
 211   DbdataTable *pTab = (DbdataTable*)tab;
 212   int i;
 213   int iSchema = -1;
 214   int iPgno = -1;
 215   int colSchema = (pTab->bPtr ? DBPTR_COLUMN_SCHEMA : DBDATA_COLUMN_SCHEMA);
 216
 217   for(i=0; i<pIdx->nConstraint; i++){
 218     struct sqlite3_index_constraint *p = &pIdx->aConstraint[i];
 219     if( p->op==SQLITE_INDEX_CONSTRAINT_EQ ){
 220       if( p->iColumn==colSchema ){
 221         if( p->usable==0 ) return SQLITE_CONSTRAINT;
 222         iSchema = i;
 223       }
 224       if( p->iColumn==DBDATA_COLUMN_PGNO && p->usable ){
 225         iPgno = i;
 226       }
 227     }
 228   }
 229
 230   if( iSchema>=0 ){
 231     pIdx->aConstraintUsage[iSchema].argvIndex = 1;
 232     pIdx->aConstraintUsage[iSchema].omit = 1;
 233   }
 234   if( iPgno>=0 ){
 235     pIdx->aConstraintUsage[iPgno].argvIndex = 1 + (iSchema>=0);
 236     pIdx->aConstraintUsage[iPgno].omit = 1;
 237     pIdx->estimatedCost = 100;
 238     pIdx->estimatedRows =  50;
 239
 240     if( pTab->bPtr==0 && pIdx->nOrderBy && pIdx->aOrderBy[0].desc==0 ){
 241       int iCol = pIdx->aOrderBy[0].iColumn;
 242       if( pIdx->nOrderBy==1 ){
 243         pIdx->orderByConsumed = (iCol==0 || iCol==1);
 244       }else if( pIdx->nOrderBy==2 && pIdx->aOrderBy[1].desc==0 && iCol==0 ){
 245         pIdx->orderByConsumed = (pIdx->aOrderBy[1].iColumn==1);
 246       }
 247     }
 248
 249   }else{
 250     pIdx->estimatedCost = 100000000;
 251     pIdx->estimatedRows = 1000000000;
 252   }
 253   pIdx->idxNum = (iSchema>=0 ? 0x01 : 0x00) | (iPgno>=0 ? 0x02 : 0x00);
 254   return SQLITE_OK;
 255 }
 256
 257 /*
 258 ** Open a new sqlite_dbdata or sqlite_dbptr cursor.
 259 */
 260 static int dbdataOpen(sqlite3_vtab *pVTab, sqlite3_vtab_cursor **ppCursor){
 261   DbdataCursor *pCsr;
 262
 263   pCsr = (DbdataCursor*)sqlite3_malloc64(sizeof(DbdataCursor));
 264   if( pCsr==0 ){
 265     return SQLITE_NOMEM;
 266   }else{
 267     memset(pCsr, 0, sizeof(DbdataCursor));
 268     pCsr->base.pVtab = pVTab;
 269   }
 270
 271   *ppCursor = (sqlite3_vtab_cursor *)pCsr;
 272   return SQLITE_OK;
 273 }
 274
 275 /*
 276 ** Restore a cursor object to the state it was in when first allocated
 277 ** by dbdataOpen().
 278 */
 279 static void dbdataResetCursor(DbdataCursor *pCsr){
 280   DbdataTable *pTab = (DbdataTable*)(pCsr->base.pVtab);
 281   if( pTab->pStmt==0 ){
 282     pTab->pStmt = pCsr->pStmt;
 283   }else{
 284     sqlite3_finalize(pCsr->pStmt);
 285   }
 286   pCsr->pStmt = 0;
 287   pCsr->iPgno = 1;
 288   pCsr->iCell = 0;
 289   pCsr->iField = 0;
 290   pCsr->bOnePage = 0;
 291   sqlite3_free(pCsr->aPage);
 292   sqlite3_free(pCsr->pRec);
 293   pCsr->pRec = 0;
 294   pCsr->aPage = 0;
 295 }
 296
 297 /*
 298 ** Close an sqlite_dbdata or sqlite_dbptr cursor.
 299 */
 300 static int dbdataClose(sqlite3_vtab_cursor *pCursor){
 301   DbdataCursor *pCsr = (DbdataCursor*)pCursor;
 302   dbdataResetCursor(pCsr);
 303   sqlite3_free(pCsr);
 304   return SQLITE_OK;
 305 }
 306
 307 /*
 308 ** Utility methods to decode 16 and 32-bit big-endian unsigned integers.
 309 */
 310 static u32 get_uint16(unsigned char *a){
 311   return (a[0]<<8)|a[1];
 312 }
 313 static u32 get_uint32(unsigned char *a){
 314   return ((u32)a[0]<<24)
 315        | ((u32)a[1]<<16)
 316        | ((u32)a[2]<<8)
 317        | ((u32)a[3]);
 318 }
 319
 320 /*
 321 ** Load page pgno from the database via the sqlite_dbpage virtual table.
 322 ** If successful, set (*ppPage) to point to a buffer containing the page
 323 ** data, (*pnPage) to the size of that buffer in bytes and return
 324 ** SQLITE_OK. In this case it is the responsibility of the caller to
 325 ** eventually free the buffer using sqlite3_free().
 326 **
 327 ** Or, if an error occurs, set both (*ppPage) and (*pnPage) to 0 and
 328 ** return an SQLite error code.
 329 */
 330 static int dbdataLoadPage(
 331   DbdataCursor *pCsr,             /* Cursor object */
 332   u32 pgno,                       /* Page number of page to load */
 333   u8 **ppPage,                    /* OUT: pointer to page buffer */
 334   int *pnPage                     /* OUT: Size of (*ppPage) in bytes */
 335 ){
 336   int rc2;
 337   int rc = SQLITE_OK;
 338   sqlite3_stmt *pStmt = pCsr->pStmt;
 339
 340   *ppPage = 0;
 341   *pnPage = 0;
 342   if( pgno>0 ){
 343     sqlite3_bind_int64(pStmt, 2, pgno);
 344     if( SQLITE_ROW==sqlite3_step(pStmt) ){
 345       int nCopy = sqlite3_column_bytes(pStmt, 0);
 346       if( nCopy>0 ){
 347         u8 *pPage;
 348         pPage = (u8*)sqlite3_malloc64(nCopy + DBDATA_PADDING_BYTES);
 349         if( pPage==0 ){
 350           rc = SQLITE_NOMEM;
 351         }else{
 352           const u8 *pCopy = sqlite3_column_blob(pStmt, 0);
 353           memcpy(pPage, pCopy, nCopy);
 354           memset(&pPage[nCopy], 0, DBDATA_PADDING_BYTES);
 355         }
 356         *ppPage = pPage;
 357         *pnPage = nCopy;
 358       }
 359     }
 360     rc2 = sqlite3_reset(pStmt);
 361     if( rc==SQLITE_OK ) rc = rc2;
 362   }
 363
 364   return rc;
 365 }
 366
 367 /*
 368 ** Read a varint.  Put the value in *pVal and return the number of bytes.
 369 */
 370 static int dbdataGetVarint(const u8 *z, sqlite3_int64 *pVal){
 371   sqlite3_uint64 u = 0;
 372   int i;
 373   for(i=0; i<8; i++){
 374     u = (u<<7) + (z[i]&0x7f);
 375     if( (z[i]&0x80)==0 ){ *pVal = (sqlite3_int64)u; return i+1; }
 376   }
 377   u = (u<<8) + (z[i]&0xff);
 378   *pVal = (sqlite3_int64)u;
 379   return 9;
 380 }
 381
 382 /*
 383 ** Like dbdataGetVarint(), but set the output to 0 if it is less than 0
 384 ** or greater than 0xFFFFFFFF. This can be used for all varints in an
 385 ** SQLite database except for key values in intkey tables.
 386 */
 387 static int dbdataGetVarintU32(const u8 *z, sqlite3_int64 *pVal){
 388   sqlite3_int64 val;
 389   int nRet = dbdataGetVarint(z, &val);
 390   if( val<0 || val>0xFFFFFFFF ) val = 0;
 391   *pVal = val;
 392   return nRet;
 393 }
 394
 395 /*
 396 ** Return the number of bytes of space used by an SQLite value of type
 397 ** eType.
 398 */
 399 static int dbdataValueBytes(int eType){
 400   switch( eType ){
 401     case 0: case 8: case 9:
 402     case 10: case 11:
 403       return 0;
 404     case 1:
 405       return 1;
 406     case 2:
 407       return 2;
 408     case 3:
 409       return 3;
 410     case 4:
 411       return 4;
 412     case 5:
 413       return 6;
 414     case 6:
 415     case 7:
 416       return 8;
 417     default:
 418       if( eType>0 ){
 419         return ((eType-12) / 2);
 420       }
 421       return 0;
 422   }
 423 }
 424
 425 /*
 426 ** Load a value of type eType from buffer pData and use it to set the
 427 ** result of context object pCtx.
 428 */
 429 static void dbdataValue(
 430   sqlite3_context *pCtx,
 431   u32 enc,
 432   int eType,
 433   u8 *pData,
 434   sqlite3_int64 nData
 435 ){
 436   if( eType>=0 && dbdataValueBytes(eType)<=nData ){
 437     switch( eType ){
 438       case 0:
 439       case 10:
 440       case 11:
 441         sqlite3_result_null(pCtx);
 442         break;
 443
 444       case 8:
 445         sqlite3_result_int(pCtx, 0);
 446         break;
 447       case 9:
 448         sqlite3_result_int(pCtx, 1);
 449         break;
 450
 451       case 1: case 2: case 3: case 4: case 5: case 6: case 7: {
 452         sqlite3_uint64 v = (signed char)pData[0];
 453         pData++;
 454         switch( eType ){
 455           case 7:
 456           case 6:  v = (v<<16) + (pData[0]<<8) + pData[1];  pData += 2;
 457           case 5:  v = (v<<16) + (pData[0]<<8) + pData[1];  pData += 2;
 458           case 4:  v = (v<<8) + pData[0];  pData++;
 459           case 3:  v = (v<<8) + pData[0];  pData++;
 460           case 2:  v = (v<<8) + pData[0];  pData++;
 461         }
 462
 463         if( eType==7 ){
 464           double r;
 465           memcpy(&r, &v, sizeof(r));
 466           sqlite3_result_double(pCtx, r);
 467         }else{
 468           sqlite3_result_int64(pCtx, (sqlite3_int64)v);
 469         }
 470         break;
 471       }
 472
 473       default: {
 474         int n = ((eType-12) / 2);
 475         if( eType % 2 ){
 476           switch( enc ){
 477 #ifndef SQLITE_OMIT_UTF16
 478             case SQLITE_UTF16BE:
 479               sqlite3_result_text16be(pCtx, (void*)pData, n, SQLITE_TRANSIENT);
 480               break;
 481             case SQLITE_UTF16LE:
 482               sqlite3_result_text16le(pCtx, (void*)pData, n, SQLITE_TRANSIENT);
 483               break;
 484 #endif
 485             default:
 486               sqlite3_result_text(pCtx, (char*)pData, n, SQLITE_TRANSIENT);
 487               break;
 488           }
 489         }else{
 490           sqlite3_result_blob(pCtx, pData, n, SQLITE_TRANSIENT);
 491         }
 492       }
 493     }
 494   }
 495 }
 496
 497 /*
 498 ** Move an sqlite_dbdata or sqlite_dbptr cursor to the next entry.
 499 */
 500 static int dbdataNext(sqlite3_vtab_cursor *pCursor){
 501   DbdataCursor *pCsr = (DbdataCursor*)pCursor;
 502   DbdataTable *pTab = (DbdataTable*)pCursor->pVtab;
 503
 504   pCsr->iRowid++;
 505   while( 1 ){
 506     int rc;
 507     int iOff = (pCsr->iPgno==1 ? 100 : 0);
 508     int bNextPage = 0;
 509
 510     if( pCsr->aPage==0 ){
 511       while( 1 ){
 512         if( pCsr->bOnePage==0 && pCsr->iPgno>pCsr->szDb ) return SQLITE_OK;
 513         rc = dbdataLoadPage(pCsr, pCsr->iPgno, &pCsr->aPage, &pCsr->nPage);
 514         if( rc!=SQLITE_OK ) return rc;
 515         if( pCsr->aPage ) break;
 516         if( pCsr->bOnePage ) return SQLITE_OK;
 517         pCsr->iPgno++;
 518       }
 519       pCsr->iCell = pTab->bPtr ? -2 : 0;
 520       pCsr->nCell = get_uint16(&pCsr->aPage[iOff+3]);
 521     }
 522
 523     if( pTab->bPtr ){
 524       if( pCsr->aPage[iOff]!=0x02 && pCsr->aPage[iOff]!=0x05 ){
 525         pCsr->iCell = pCsr->nCell;
 526       }
 527       pCsr->iCell++;
 528       if( pCsr->iCell>=pCsr->nCell ){
 529         sqlite3_free(pCsr->aPage);
 530         pCsr->aPage = 0;
 531         if( pCsr->bOnePage ) return SQLITE_OK;
 532         pCsr->iPgno++;
 533       }else{
 534         return SQLITE_OK;
 535       }
 536     }else{
 537       /* If there is no record loaded, load it now. */
 538       if( pCsr->pRec==0 ){
 539         int bHasRowid = 0;
 540         int nPointer = 0;
 541         sqlite3_int64 nPayload = 0;
 542         sqlite3_int64 nHdr = 0;
 543         int iHdr;
 544         int U, X;
 545         int nLocal;
 546
 547         switch( pCsr->aPage[iOff] ){
 548           case 0x02:
 549             nPointer = 4;
 550             break;
 551           case 0x0a:
 552             break;
 553           case 0x0d:
 554             bHasRowid = 1;
 555             break;
 556           default:
 557             /* This is not a b-tree page with records on it. Continue. */
 558             pCsr->iCell = pCsr->nCell;
 559             break;
 560         }
 561
 562         if( pCsr->iCell>=pCsr->nCell ){
 563           bNextPage = 1;
 564         }else{
 565
 566           iOff += 8 + nPointer + pCsr->iCell*2;
 567           if( iOff>pCsr->nPage ){
 568             bNextPage = 1;
 569           }else{
 570             iOff = get_uint16(&pCsr->aPage[iOff]);
 571           }
 572
 573           /* For an interior node cell, skip past the child-page number */
 574           iOff += nPointer;
 575
 576           /* Load the "byte of payload including overflow" field */
 577           if( bNextPage || iOff>pCsr->nPage ){
 578             bNextPage = 1;
 579           }else{
 580             iOff += dbdataGetVarintU32(&pCsr->aPage[iOff], &nPayload);
 581           }
 582
 583           /* If this is a leaf intkey cell, load the rowid */
 584           if( bHasRowid && !bNextPage && iOff<pCsr->nPage ){
 585             iOff += dbdataGetVarint(&pCsr->aPage[iOff], &pCsr->iIntkey);
 586           }
 587
 588           /* Figure out how much data to read from the local page */
 589           U = pCsr->nPage;
 590           if( bHasRowid ){
 591             X = U-35;
 592           }else{
 593             X = ((U-12)*64/255)-23;
 594           }
 595           if( nPayload<=X ){
 596             nLocal = nPayload;
 597           }else{
 598             int M, K;
 599             M = ((U-12)*32/255)-23;
 600             K = M+((nPayload-M)%(U-4));
 601             if( K<=X ){
 602               nLocal = K;
 603             }else{
 604               nLocal = M;
 605             }
 606           }
 607
 608           if( bNextPage || nLocal+iOff>pCsr->nPage ){
 609             bNextPage = 1;
 610           }else{
 611
 612             /* Allocate space for payload. And a bit more to catch small buffer
 613             ** overruns caused by attempting to read a varint or similar from
 614             ** near the end of a corrupt record.  */
 615             pCsr->pRec = (u8*)sqlite3_malloc64(nPayload+DBDATA_PADDING_BYTES);
 616             if( pCsr->pRec==0 ) return SQLITE_NOMEM;
 617             memset(pCsr->pRec, 0, nPayload+DBDATA_PADDING_BYTES);
 618             pCsr->nRec = nPayload;
 619
 620             /* Load the nLocal bytes of payload */
 621             memcpy(pCsr->pRec, &pCsr->aPage[iOff], nLocal);
 622             iOff += nLocal;
 623
 624             /* Load content from overflow pages */
 625             if( nPayload>nLocal ){
 626               sqlite3_int64 nRem = nPayload - nLocal;
 627               u32 pgnoOvfl = get_uint32(&pCsr->aPage[iOff]);
 628               while( nRem>0 ){
 629                 u8 *aOvfl = 0;
 630                 int nOvfl = 0;
 631                 int nCopy;
 632                 rc = dbdataLoadPage(pCsr, pgnoOvfl, &aOvfl, &nOvfl);
 633                 assert( rc!=SQLITE_OK || aOvfl==0 || nOvfl==pCsr->nPage );
 634                 if( rc!=SQLITE_OK ) return rc;
 635                 if( aOvfl==0 ) break;
 636
 637                 nCopy = U-4;
 638                 if( nCopy>nRem ) nCopy = nRem;
 639                 memcpy(&pCsr->pRec[nPayload-nRem], &aOvfl[4], nCopy);
 640                 nRem -= nCopy;
 641
 642                 pgnoOvfl = get_uint32(aOvfl);
 643                 sqlite3_free(aOvfl);
 644               }
 645             }
 646
 647             iHdr = dbdataGetVarintU32(pCsr->pRec, &nHdr);
 648             if( nHdr>nPayload ) nHdr = 0;
 649             pCsr->nHdr = nHdr;
 650             pCsr->pHdrPtr = &pCsr->pRec[iHdr];
 651             pCsr->pPtr = &pCsr->pRec[pCsr->nHdr];
 652             pCsr->iField = (bHasRowid ? -1 : 0);
 653           }
 654         }
 655       }else{
 656         pCsr->iField++;
 657         if( pCsr->iField>0 ){
 658           sqlite3_int64 iType;
 659           if( pCsr->pHdrPtr>&pCsr->pRec[pCsr->nRec] ){
 660             bNextPage = 1;
 661           }else{
 662             pCsr->pHdrPtr += dbdataGetVarintU32(pCsr->pHdrPtr, &iType);
 663             pCsr->pPtr += dbdataValueBytes(iType);
 664           }
 665         }
 666       }
 667
 668       if( bNextPage ){
 669         sqlite3_free(pCsr->aPage);
 670         sqlite3_free(pCsr->pRec);
 671         pCsr->aPage = 0;
 672         pCsr->pRec = 0;
 673         if( pCsr->bOnePage ) return SQLITE_OK;
 674         pCsr->iPgno++;
 675       }else{
 676         if( pCsr->iField<0 || pCsr->pHdrPtr<&pCsr->pRec[pCsr->nHdr] ){
 677           return SQLITE_OK;
 678         }
 679
 680         /* Advance to the next cell. The next iteration of the loop will load
 681         ** the record and so on. */
 682         sqlite3_free(pCsr->pRec);
 683         pCsr->pRec = 0;
 684         pCsr->iCell++;
 685       }
 686     }
 687   }
 688
 689   assert( !"can't get here" );
 690   return SQLITE_OK;
 691 }
 692
 693 /*
 694 ** Return true if the cursor is at EOF.
 695 */
 696 static int dbdataEof(sqlite3_vtab_cursor *pCursor){
 697   DbdataCursor *pCsr = (DbdataCursor*)pCursor;
 698   return pCsr->aPage==0;
 699 }
 700
 701 /*
 702 ** Return true if nul-terminated string zSchema ends in "()". Or false
 703 ** otherwise.
 704 */
 705 static int dbdataIsFunction(const char *zSchema){
 706   size_t n = strlen(zSchema);
 707   if( n>2 && zSchema[n-2]=='(' && zSchema[n-1]==')' ){
 708     return (int)n-2;
 709   }
 710   return 0;
 711 }
 712
 713 /*
 714 ** Determine the size in pages of database zSchema (where zSchema is
 715 ** "main", "temp" or the name of an attached database) and set
 716 ** pCsr->szDb accordingly. If successful, return SQLITE_OK. Otherwise,
 717 ** an SQLite error code.
 718 */
 719 static int dbdataDbsize(DbdataCursor *pCsr, const char *zSchema){
 720   DbdataTable *pTab = (DbdataTable*)pCsr->base.pVtab;
 721   char *zSql = 0;
 722   int rc, rc2;
 723   int nFunc = 0;
 724   sqlite3_stmt *pStmt = 0;
 725
 726   if( (nFunc = dbdataIsFunction(zSchema))>0 ){
 727     zSql = sqlite3_mprintf("SELECT %.*s(0)", nFunc, zSchema);
 728   }else{
 729     zSql = sqlite3_mprintf("PRAGMA %Q.page_count", zSchema);
 730   }
 731   if( zSql==0 ) return SQLITE_NOMEM;
 732
 733   rc = sqlite3_prepare_v2(pTab->db, zSql, -1, &pStmt, 0);
 734   sqlite3_free(zSql);
 735   if( rc==SQLITE_OK && sqlite3_step(pStmt)==SQLITE_ROW ){
 736     pCsr->szDb = sqlite3_column_int(pStmt, 0);
 737   }
 738   rc2 = sqlite3_finalize(pStmt);
 739   if( rc==SQLITE_OK ) rc = rc2;
 740   return rc;
 741 }
 742
 743 /*
 744 ** Attempt to figure out the encoding of the database by retrieving page 1
 745 ** and inspecting the header field. If successful, set the pCsr->enc variable
 746 ** and return SQLITE_OK. Otherwise, return an SQLite error code.
 747 */
 748 static int dbdataGetEncoding(DbdataCursor *pCsr){
 749   int rc = SQLITE_OK;
 750   int nPg1 = 0;
 751   u8 *aPg1 = 0;
 752   rc = dbdataLoadPage(pCsr, 1, &aPg1, &nPg1);
 753   assert( rc!=SQLITE_OK || nPg1==0 || nPg1>=512 );
 754   if( rc==SQLITE_OK && nPg1>0 ){
 755     pCsr->enc = get_uint32(&aPg1[56]);
 756   }
 757   sqlite3_free(aPg1);
 758   return rc;
 759 }
 760
 761
 762 /*
 763 ** xFilter method for sqlite_dbdata and sqlite_dbptr.
 764 */
 765 static int dbdataFilter(
 766   sqlite3_vtab_cursor *pCursor,
 767   int idxNum, const char *idxStr,
 768   int argc, sqlite3_value **argv
 769 ){
 770   DbdataCursor *pCsr = (DbdataCursor*)pCursor;
 771   DbdataTable *pTab = (DbdataTable*)pCursor->pVtab;
 772   int rc = SQLITE_OK;
 773   const char *zSchema = "main";
 774   (void)idxStr;
 775   (void)argc;
 776
 777   dbdataResetCursor(pCsr);
 778   assert( pCsr->iPgno==1 );
 779   if( idxNum & 0x01 ){
 780     zSchema = (const char*)sqlite3_value_text(argv[0]);
 781     if( zSchema==0 ) zSchema = "";
 782   }
 783   if( idxNum & 0x02 ){
 784     pCsr->iPgno = sqlite3_value_int(argv[(idxNum & 0x01)]);
 785     pCsr->bOnePage = 1;
 786   }else{
 787     rc = dbdataDbsize(pCsr, zSchema);
 788   }
 789
 790   if( rc==SQLITE_OK ){
 791     int nFunc = 0;
 792     if( pTab->pStmt ){
 793       pCsr->pStmt = pTab->pStmt;
 794       pTab->pStmt = 0;
 795     }else if( (nFunc = dbdataIsFunction(zSchema))>0 ){
 796       char *zSql = sqlite3_mprintf("SELECT %.*s(?2)", nFunc, zSchema);
 797       if( zSql==0 ){
 798         rc = SQLITE_NOMEM;
 799       }else{
 800         rc = sqlite3_prepare_v2(pTab->db, zSql, -1, &pCsr->pStmt, 0);
 801         sqlite3_free(zSql);
 802       }
 803     }else{
 804       rc = sqlite3_prepare_v2(pTab->db,
 805           "SELECT data FROM sqlite_dbpage(?) WHERE pgno=?", -1,
 806           &pCsr->pStmt, 0
 807       );
 808     }
 809   }
 810   if( rc==SQLITE_OK ){
 811     rc = sqlite3_bind_text(pCsr->pStmt, 1, zSchema, -1, SQLITE_TRANSIENT);
 812   }else{
 813     pTab->base.zErrMsg = sqlite3_mprintf("%s", sqlite3_errmsg(pTab->db));
 814   }
 815
 816   /* Try to determine the encoding of the db by inspecting the header
 817   ** field on page 1. */
 818   if( rc==SQLITE_OK ){
 819     rc = dbdataGetEncoding(pCsr);
 820   }
 821
 822   if( rc==SQLITE_OK ){
 823     rc = dbdataNext(pCursor);
 824   }
 825   return rc;
 826 }
 827
 828 /*
 829 ** Return a column for the sqlite_dbdata or sqlite_dbptr table.
 830 */
 831 static int dbdataColumn(
 832   sqlite3_vtab_cursor *pCursor,
 833   sqlite3_context *ctx,
 834   int i
 835 ){
 836   DbdataCursor *pCsr = (DbdataCursor*)pCursor;
 837   DbdataTable *pTab = (DbdataTable*)pCursor->pVtab;
 838   if( pTab->bPtr ){
 839     switch( i ){
 840       case DBPTR_COLUMN_PGNO:
 841         sqlite3_result_int64(ctx, pCsr->iPgno);
 842         break;
 843       case DBPTR_COLUMN_CHILD: {
 844         int iOff = pCsr->iPgno==1 ? 100 : 0;
 845         if( pCsr->iCell<0 ){
 846           iOff += 8;
 847         }else{
 848           iOff += 12 + pCsr->iCell*2;
 849           if( iOff>pCsr->nPage ) return SQLITE_OK;
 850           iOff = get_uint16(&pCsr->aPage[iOff]);
 851         }
 852         if( iOff<=pCsr->nPage ){
 853           sqlite3_result_int64(ctx, get_uint32(&pCsr->aPage[iOff]));
 854         }
 855         break;
 856       }
 857     }
 858   }else{
 859     switch( i ){
 860       case DBDATA_COLUMN_PGNO:
 861         sqlite3_result_int64(ctx, pCsr->iPgno);
 862         break;
 863       case DBDATA_COLUMN_CELL:
 864         sqlite3_result_int(ctx, pCsr->iCell);
 865         break;
 866       case DBDATA_COLUMN_FIELD:
 867         sqlite3_result_int(ctx, pCsr->iField);
 868         break;
 869       case DBDATA_COLUMN_VALUE: {
 870         if( pCsr->iField<0 ){
 871           sqlite3_result_int64(ctx, pCsr->iIntkey);
 872         }else if( &pCsr->pRec[pCsr->nRec] >= pCsr->pPtr ){
 873           sqlite3_int64 iType;
 874           dbdataGetVarintU32(pCsr->pHdrPtr, &iType);
 875           dbdataValue(
 876               ctx, pCsr->enc, iType, pCsr->pPtr,
 877               &pCsr->pRec[pCsr->nRec] - pCsr->pPtr
 878           );
 879         }
 880         break;
 881       }
 882     }
 883   }
 884   return SQLITE_OK;
 885 }
 886
 887 /*
 888 ** Return the rowid for an sqlite_dbdata or sqlite_dptr table.
 889 */
 890 static int dbdataRowid(sqlite3_vtab_cursor *pCursor, sqlite_int64 *pRowid){
 891   DbdataCursor *pCsr = (DbdataCursor*)pCursor;
 892   *pRowid = pCsr->iRowid;
 893   return SQLITE_OK;
 894 }
 895
 896
 897 /*
 898 ** Invoke this routine to register the "sqlite_dbdata" virtual table module
 899 */
 900 static int sqlite3DbdataRegister(sqlite3 *db){
 901   static sqlite3_module dbdata_module = {
 902     0,                            /* iVersion */
 903     0,                            /* xCreate */
 904     dbdataConnect,                /* xConnect */
 905     dbdataBestIndex,              /* xBestIndex */
 906     dbdataDisconnect,             /* xDisconnect */
 907     0,                            /* xDestroy */
 908     dbdataOpen,                   /* xOpen - open a cursor */
 909     dbdataClose,                  /* xClose - close a cursor */
 910     dbdataFilter,                 /* xFilter - configure scan constraints */
 911     dbdataNext,                   /* xNext - advance a cursor */
 912     dbdataEof,                    /* xEof - check for end of scan */
 913     dbdataColumn,                 /* xColumn - read data */
 914     dbdataRowid,                  /* xRowid - read data */
 915     0,                            /* xUpdate */
 916     0,                            /* xBegin */
 917     0,                            /* xSync */
 918     0,                            /* xCommit */
 919     0,                            /* xRollback */
 920     0,                            /* xFindMethod */
 921     0,                            /* xRename */
 922     0,                            /* xSavepoint */
 923     0,                            /* xRelease */
 924     0,                            /* xRollbackTo */
 925     0                             /* xShadowName */
 926   };
 927
 928   int rc = sqlite3_create_module(db, "sqlite_dbdata", &dbdata_module, 0);
 929   if( rc==SQLITE_OK ){
 930     rc = sqlite3_create_module(db, "sqlite_dbptr", &dbdata_module, (void*)1);
 931   }
 932   return rc;
 933 }
 934
 935 #ifdef _WIN32
 936 __declspec(dllexport)
 937 #endif
 938 int sqlite3_dbdata_init(
 939   sqlite3 *db,
 940   char **pzErrMsg,
 941   const sqlite3_api_routines *pApi
 942 ){
 943   SQLITE_EXTENSION_INIT2(pApi);
 944   (void)pzErrMsg;
 945   return sqlite3DbdataRegister(db);
 946 }
 947
 948 #endif /* ifndef SQLITE_OMIT_VIRTUALTABLE */