SQLite

** Do various sanity checks on a single page of a tree.  Return
** the tree depth.  Root pages return 0.  Parents of root pages
** return 1, and so forth.
** 
** These checks are done:
**
**      1.  Make sure that cells and freeblocks do not overlap
**          but combine to completely cover the page.
**  NO  2.  Make sure cell keys are in order.
**  NO  3.  Make sure no key is less than or equal to zLowerBound.
**  NO  4.  Make sure no key is greater than or equal to zUpperBound.
**      5.  Check the integrity of overflow pages.
**      6.  Recursively call checkTreePage on all children.
**      7.  Verify that the depth of all children is the same.
**      8.  Make sure this page is at least 33% full or else it is
**          the root of the tree.
*/
static int checkTreePage(
  IntegrityCk *pCheck,  /* Context for the sanity check */
  int iPage,            /* Page number of the page to check */
  i64 *pnParentMinKey, 
  i64 *pnParentMaxKey
){
  MemPage *pPage;
  int i, rc, depth, d2, pgno, cnt;
  int hdr, cellStart;
  int nCell;
  u8 *data;
  BtShared *pBt;
  int usableSize;
  u32 *heap = 0;
  u32 x, prev = 0;
  i64 nMinKey = 0;
  i64 nMaxKey = 0;

  const char *saved_zPfx = pCheck->zPfx;
  int saved_v1 = pCheck->v1;
  int saved_v2 = pCheck->v2;

  /* Check that the page exists
  */
  pBt = pCheck->pBt;
  usableSize = pBt->usableSize;
  if( iPage==0 ) return 0;
  if( checkRef(pCheck, iPage) ) return 0;
  pCheck->zPfx = "Page %d: ";
  pCheck->v1 = iPage;
  if( (rc = btreeGetPage(pBt, (Pgno)iPage, &pPage, 0))!=0 ){
    checkAppendMsg(pCheck,
       "unable to get the page. error code=%d", rc);
    depth = -1;
    goto end_of_check;
  }

  /* Clear MemPage.isInit to make sure the corruption detection code in
  ** btreeInitPage() is executed.  */
  pPage->isInit = 0;
  if( (rc = btreeInitPage(pPage))!=0 ){
    assert( rc==SQLITE_CORRUPT );  /* The only possible error from InitPage */
    checkAppendMsg(pCheck,
                   "btreeInitPage() returns error code %d", rc);
    releasePage(pPage);
    depth = -1;
    goto end_of_check;
  }

  /* Check out all the cells.
  */


  depth = 0;















  for(i=0; i<pPage->nCell && pCheck->mxErr; i++){
    u8 *pCell;
    u32 sz;
    CellInfo info;

    /* Check payload overflow pages
    */
    pCheck->zPfx = "On tree page %d cell %d: ";
    pCheck->v1 = iPage;
    pCheck->v2 = i;
    pCell = findCell(pPage,i);
    pPage->xParseCell(pPage, pCell, &info);
    sz = info.nPayload;
    /* For intKey pages, check that the keys are in order.
    */
    if( pPage->intKey ){
      if( i==0 ){
        nMinKey = nMaxKey = info.nKey;
      }else if( info.nKey <= nMaxKey ){
        checkAppendMsg(pCheck,
           "Rowid %lld out of order (previous was %lld)", info.nKey, nMaxKey);




      }

      nMaxKey = info.nKey;



    }

    if( (sz>info.nLocal) 


     && (&pCell[info.iOverflow]<=&pPage->aData[pBt->usableSize])
    ){
      int nPage = (sz - info.nLocal + usableSize - 5)/(usableSize - 4);
      Pgno pgnoOvfl = get4byte(&pCell[info.iOverflow]);
#ifndef SQLITE_OMIT_AUTOVACUUM
      if( pBt->autoVacuum ){
        checkPtrmap(pCheck, pgnoOvfl, PTRMAP_OVERFLOW1, iPage);
      }
#endif
      checkList(pCheck, 0, pgnoOvfl, nPage);
    }

    /* Check sanity of left child page.
    */
    if( !pPage->leaf ){
      pgno = get4byte(pCell);
#ifndef SQLITE_OMIT_AUTOVACUUM
      if( pBt->autoVacuum ){
        checkPtrmap(pCheck, pgno, PTRMAP_BTREE, iPage);
      }
#endif
      d2 = checkTreePage(pCheck, pgno, &nMinKey, i==0?NULL:&nMaxKey);
      if( i>0 && d2!=depth ){
        checkAppendMsg(pCheck, "Child page depth differs");
      }
      depth = d2;
    }
  }

  if( !pPage->leaf ){
    pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    pCheck->zPfx = "On page %d at right child: ";
    pCheck->v1 = iPage;
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pBt->autoVacuum ){
      checkPtrmap(pCheck, pgno, PTRMAP_BTREE, iPage);



    }
#endif
    checkTreePage(pCheck, pgno, NULL, !pPage->nCell?NULL:&nMaxKey);
  }
 
  /* For intKey leaf pages, check that the min/max keys are in order
  ** with any left/parent/right pages.
  */



  pCheck->zPfx = "Page %d: ";
  pCheck->v1 = iPage;
  if( pPage->leaf && pPage->intKey ){
    /* if we are a left child page */
    if( pnParentMinKey ){
      /* if we are the left most child page */
      if( !pnParentMaxKey ){
        if( nMaxKey > *pnParentMinKey ){
          checkAppendMsg(pCheck,
              "Rowid %lld out of order (max larger than parent min of %lld)",
              nMaxKey, *pnParentMinKey);
        }
      }else{
        if( nMinKey <= *pnParentMinKey ){
          checkAppendMsg(pCheck,
              "Rowid %lld out of order (min less than parent min of %lld)",
              nMinKey, *pnParentMinKey);
        }
        if( nMaxKey > *pnParentMaxKey ){
          checkAppendMsg(pCheck,
              "Rowid %lld out of order (max larger than parent max of %lld)",
              nMaxKey, *pnParentMaxKey);
        }
        *pnParentMinKey = nMaxKey;
      }
    /* else if we're a right child page */
    } else if( pnParentMaxKey ){
      if( nMinKey <= *pnParentMaxKey ){
        checkAppendMsg(pCheck,
            "Rowid %lld out of order (min less than parent max of %lld)",
            nMinKey, *pnParentMaxKey);
      }
    }
  }

  /* Check for complete coverage of the page
  */
  data = pPage->aData;
  hdr = pPage->hdrOffset;
  heap = (u32*)sqlite3PageMalloc( pBt->pageSize );
  pCheck->zPfx = 0;
  if( heap==0 ){
    pCheck->mallocFailed = 1;
  }else{
    int contentOffset = get2byteNotZero(&data[hdr+5]);
    assert( contentOffset<=usableSize );  /* Enforced by btreeInitPage() */
    heap[0] = 0;
    btreeHeapInsert(heap, contentOffset-1);
    /* EVIDENCE-OF: R-37002-32774 The two-byte integer at offset 3 gives the
    ** number of cells on the page. */
    nCell = get2byte(&data[hdr+3]);
    /* EVIDENCE-OF: R-23882-45353 The cell pointer array of a b-tree page
    ** immediately follows the b-tree page header. */
    cellStart = hdr + 12 - 4*pPage->leaf;
    /* EVIDENCE-OF: R-02776-14802 The cell pointer array consists of K 2-byte
    ** integer offsets to the cell contents. */
    for(i=nCell-1; i>=0; i--){
      u32 pc = get2byteAligned(&data[cellStart+i*2]);
      u32 size = pPage->xCellSize(pPage, &data[pc]);
      if( (int)(pc+size-1)>=usableSize ){
        pCheck->zPfx = 0;
        checkAppendMsg(pCheck,
            "Corruption detected in cell %d on page %d",i,iPage);
      }else{
        btreeHeapInsert(heap, (pc<<16)|(pc+size-1));
      }
    }
    /* EVIDENCE-OF: R-20690-50594 The second field of the b-tree page header
    ** is the offset of the first freeblock, or zero if there are no
    ** freeblocks on the page. */
    i = get2byte(&data[hdr+1]);
    while( i>0 ){
      int size, j;

      assert( j<=usableSize-4 );   /* Enforced by btreeInitPage() */
      i = j;
    }
    cnt = 0;
    assert( heap[0]>0 );
    assert( (heap[1]>>16)==0 );
    btreeHeapPull(heap,&prev);

    while( btreeHeapPull(heap,&x) ){
      if( (prev&0xffff)+1>(x>>16) ){
        checkAppendMsg(pCheck,
          "Multiple uses for byte %u of page %d", x>>16, iPage);
        break;
      }else{
        cnt += (x>>16) - (prev&0xffff) - 1;
        prev = x;
      }
    }
    cnt += usableSize - (prev&0xffff) - 1;
    /* EVIDENCE-OF: R-43263-13491 The total number of bytes in all fragments
    ** is stored in the fifth field of the b-tree page header.
    ** EVIDENCE-OF: R-07161-27322 The one-byte integer at offset 7 gives the
    ** number of fragmented free bytes within the cell content area.
    */
    if( heap[0]==0 && cnt!=data[hdr+7] ){
      checkAppendMsg(pCheck,
          "Fragmentation of %d bytes reported as %d on page %d",
          cnt, data[hdr+7], iPage);
    }
  }
  sqlite3PageFree(heap);
  releasePage(pPage);

end_of_check:

  pCheck->zPfx = saved_zPfx;
  pCheck->v1 = saved_v1;
  pCheck->v2 = saved_v2;
  return depth+1;
}
#endif /* SQLITE_OMIT_INTEGRITY_CHECK */

  Btree *p,     /* The btree to be checked */
  int *aRoot,   /* An array of root pages numbers for individual trees */
  int nRoot,    /* Number of entries in aRoot[] */
  int mxErr,    /* Stop reporting errors after this many */
  int *pnErr    /* Write number of errors seen to this variable */
){
  Pgno i;
  int nRef;
  IntegrityCk sCheck;
  BtShared *pBt = p->pBt;

  char zErr[100];

  sqlite3BtreeEnter(p);
  assert( p->inTrans>TRANS_NONE && pBt->inTransaction>TRANS_NONE );
  nRef = sqlite3PagerRefcount(pBt->pPager);
  sCheck.pBt = pBt;
  sCheck.pPager = pBt->pPager;
  sCheck.nPage = btreePagecount(sCheck.pBt);
  sCheck.mxErr = mxErr;
  sCheck.nErr = 0;
  sCheck.mallocFailed = 0;
  sCheck.zPfx = 0;
  sCheck.v1 = 0;
  sCheck.v2 = 0;

  *pnErr = 0;

  if( sCheck.nPage==0 ){
    sqlite3BtreeLeave(p);
    return 0;

  }

  sCheck.aPgRef = sqlite3MallocZero((sCheck.nPage / 8)+ 1);
  if( !sCheck.aPgRef ){
    *pnErr = 1;


    sqlite3BtreeLeave(p);
    return 0;



  }

  i = PENDING_BYTE_PAGE(pBt);
  if( i<=sCheck.nPage ) setPageReferenced(&sCheck, i);
  sqlite3StrAccumInit(&sCheck.errMsg, 0, zErr, sizeof(zErr), SQLITE_MAX_LENGTH);

  /* Check the integrity of the freelist
  */
  sCheck.zPfx = "Main freelist: ";
  checkList(&sCheck, 1, get4byte(&pBt->pPage1->aData[32]),
            get4byte(&pBt->pPage1->aData[36]));
  sCheck.zPfx = 0;

  /* Check all the tables.
  */

  for(i=0; (int)i<nRoot && sCheck.mxErr; i++){

    if( aRoot[i]==0 ) continue;
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pBt->autoVacuum && aRoot[i]>1 ){
      checkPtrmap(&sCheck, aRoot[i], PTRMAP_ROOTPAGE, 0);
    }
#endif
    sCheck.zPfx = "List of tree roots: ";
    checkTreePage(&sCheck, aRoot[i], NULL, NULL);
    sCheck.zPfx = 0;
  }


  /* Make sure every page in the file is referenced
  */
  for(i=1; i<=sCheck.nPage && sCheck.mxErr; i++){
#ifdef SQLITE_OMIT_AUTOVACUUM
    if( getPageReferenced(&sCheck, i)==0 ){
      checkAppendMsg(&sCheck, "Page %d is never used", i);

    if( getPageReferenced(&sCheck, i)!=0 && 
       (PTRMAP_PAGENO(pBt, i)==i && pBt->autoVacuum) ){
      checkAppendMsg(&sCheck, "Pointer map page %d is referenced", i);
    }
#endif
  }

  /* Make sure this analysis did not leave any unref() pages.
  ** This is an internal consistency check; an integrity check
  ** of the integrity check.
  */
  if( NEVER(nRef != sqlite3PagerRefcount(pBt->pPager)) ){
    checkAppendMsg(&sCheck,
      "Outstanding page count goes from %d to %d during this analysis",
      nRef, sqlite3PagerRefcount(pBt->pPager)
    );
  }

  /* Clean  up and report errors.
  */

  sqlite3BtreeLeave(p);
  sqlite3_free(sCheck.aPgRef);
  if( sCheck.mallocFailed ){
    sqlite3StrAccumReset(&sCheck.errMsg);
    *pnErr = sCheck.nErr+1;
    return 0;
  }
  *pnErr = sCheck.nErr;
  if( sCheck.nErr==0 ) sqlite3StrAccumReset(&sCheck.errMsg);



  return sqlite3StrAccumFinish(&sCheck.errMsg);
}
#endif /* SQLITE_OMIT_INTEGRITY_CHECK */

/*
** Return the full pathname of the underlying database file.  Return
** an empty string if the database is in-memory or a TEMP database.

  Pgno nPage;       /* Number of pages in the database */
  int mxErr;        /* Stop accumulating errors when this reaches zero */
  int nErr;         /* Number of messages written to zErrMsg so far */
  int mallocFailed; /* A memory allocation error has occurred */
  const char *zPfx; /* Error message prefix */
  int v1, v2;       /* Values for up to two %d fields in zPfx */
  StrAccum errMsg;  /* Accumulate the error message text here */

};

/*
** Routines to read or write a two- and four-byte big-endian integer values.
*/
#define get2byte(x)   ((x)[0]<<8 | (x)[1])
#define put2byte(p,v) ((p)[0] = (u8)((v)>>8), (p)[1] = (u8)(v))

** Return TRUE if the database file is opened read-only.  Return FALSE
** if the database is (in theory) writable.
*/
u8 sqlite3PagerIsreadonly(Pager *pPager){
  return pPager->readOnly;
}


/*
** Return the number of references to the pager.
*/
int sqlite3PagerRefcount(Pager *pPager){
  return sqlite3PcacheRefCount(pPager->pPCache);
}


/*
** Return the approximate number of bytes of memory currently
** used by the pager and its associated cache.
*/
int sqlite3PagerMemUsed(Pager *pPager){
  int perPageSize = pPager->pageSize + pPager->nExtra + sizeof(PgHdr)

#ifdef SQLITE_ENABLE_ZIPVFS
  int sqlite3PagerWalFramesize(Pager *pPager);
#endif

/* Functions used to query pager state and configuration. */
u8 sqlite3PagerIsreadonly(Pager*);
u32 sqlite3PagerDataVersion(Pager*);

int sqlite3PagerRefcount(Pager*);

int sqlite3PagerMemUsed(Pager*);
const char *sqlite3PagerFilename(Pager*, int);
const sqlite3_vfs *sqlite3PagerVfs(Pager*);
sqlite3_file *sqlite3PagerFile(Pager*);
const char *sqlite3PagerJournalname(Pager*);
int sqlite3PagerNosync(Pager*);
void *sqlite3PagerTempSpace(Pager*);

  db2 eval $::presql
  db2 eval {SELECT rowid FROM t1} {
    set result [db2 eval {pragma integrity_check}]
    break
  }
  set result
} {{*** in database main ***
On tree page 2 cell 0: 2nd reference to page 10
On tree page 2 cell 1: Child page depth differs
Page 4 is never used}}

db2 close

proc corruption_test {args} {
  set A(-corrupt) {}
  set A(-sqlprep) {}

  }
} [list 0 0123456789]
do_test corrupt3-1.10 {
  catchsql {
    PRAGMA integrity_check
  }
} {0 {{*** in database main ***
On tree page 2 cell 0: invalid page number 4
Page 3 is never used}}}
do_test corrupt3-1.11 {
  db close
  hexio_write test.db 2044 [hexio_render_int32 0]
  sqlite3 db test.db
  catchsql {
    SELECT substr(x,1,10) FROM t1
  }
} [list 1 {database disk image is malformed}]
do_test corrupt3-1.12 {
  catchsql {
    PRAGMA integrity_check
  }
} {0 {{*** in database main ***
On tree page 2 cell 0: 1 of 1 pages missing from overflow list starting at 0
Page 3 is never used}}}

finish_test

# Deliberately corrupt some of the cell offsets in the btree page
# on page 2 of the database.
#
# The error message is different depending on whether or not the
# SQLITE_ENABLE_OVERSIZE_CELL_CHECK compile-time option is engaged.
#
ifcapable oversize_cell_check {
  do_test corrupt7-2.1 {
    db close
    hexio_write test.db 1062 FF
    sqlite3 db test.db
    db eval {PRAGMA integrity_check(1)}
  } {{*** in database main ***
Page 2: btreeInitPage() returns error code 11}}
  do_test corrupt7-2.2 {
    db close
    hexio_write test.db 1062 04
    sqlite3 db test.db
    db eval {PRAGMA integrity_check(1)}
  } {{*** in database main ***
Page 2: btreeInitPage() returns error code 11}}
} else {
  do_test corrupt7-2.1 {
    db close
    hexio_write test.db 1062 FF
    sqlite3 db test.db
    db eval {PRAGMA integrity_check(1)}
  } {{*** in database main ***
Corruption detected in cell 15 on page 2}}
  do_test corrupt7-2.2 {
    db close
    hexio_write test.db 1062 04
    sqlite3 db test.db
    db eval {PRAGMA integrity_check(1)}
  } {{*** in database main ***
On tree page 2 cell 15: Rowid 0 out of order (previous was 15)}}
}
  
# The code path that was causing the buffer overrun that this test
# case was checking for was removed.
#
#do_test corrupt7-3.1 {
#  execsql {
#    DROP TABLE t1;

  hexio_write test.db 2041 [format %02x 0x2e]

  sqlite3 db test.db

  set res [ catchsql {PRAGMA integrity_check} ]
  set ans [lindex $res 1]

  list [regexp {out of order.*previous was} $ans] \
       [regexp {out of order.*max larger than parent max} $ans]
} {1 1}

do_test corruptE-2.2 {
  db close
  forcecopy test.bu test.db

  # insert corrupt byte(s)
  hexio_write test.db 2047 [format %02x 0x84]

  sqlite3 db test.db

  set res [ catchsql {PRAGMA integrity_check} ]
  set ans [lindex $res 1]

  list [regexp {out of order.*previous was} $ans] \
       [regexp {out of order.*min less than parent min} $ans]
} {1 1}

do_test corruptE-2.3 {
  db close
  forcecopy test.bu test.db

  # insert corrupt byte(s)
  hexio_write test.db 7420 [format %02x 0xa8]
  hexio_write test.db 10459 [format %02x 0x8d]

  sqlite3 db test.db

  set res [ catchsql {PRAGMA integrity_check} ]
  set ans [lindex $res 1]

  list [regexp {out of order.*max larger than parent min} $ans]
} {1}

do_test corruptE-2.4 {
  db close
  forcecopy test.bu test.db

  # insert corrupt byte(s)
  hexio_write test.db 10233 [format %02x 0xd0]

  sqlite3 db test.db

  set res [ catchsql {PRAGMA integrity_check} ]
  set ans [lindex $res 1]

  list [regexp {out of order.*min less than parent max} $ans]
} {1}


set tests [list {10233 0xd0} \
                {941 0x42} \
                {1028 0x53} \
                {2041 0xd0} \
                {2042 0x1f} \
                {2047 0xaa} \

    hexio_write test.db [lindex $test 0] [format %02x [lindex $test 1]]

    sqlite3 db test.db

    set res [ catchsql {PRAGMA integrity_check} ]
    set ans [lindex $res 1]

    list [regexp {out of order} $ans]
  } {1}
  incr tc 1
}

finish_test

  }
  db close
  forcecopy test.db testerr.db
  hexio_write testerr.db 15000 [string repeat 55 100]
} {100}

set mainerr {*** in database main ***
Multiple uses for byte 672 of page 15}
set auxerr {*** in database aux ***
Multiple uses for byte 672 of page 15}

set mainerr {/{\*\*\* in database main \*\*\*
Multiple uses for byte 672 of page 15}.*/}
set auxerr {/{\*\*\* in database aux \*\*\*
Multiple uses for byte 672 of page 15}.*/}

do_test 22.2 {
  catch { db close }
  sqlite3 db testerr.db
  execsql { PRAGMA integrity_check }
} $mainerr