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