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