SQLite

**      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 */
  char *zParentContext, /* Parent context */
  i64 *pnParentMinKey, 
  i64 *pnParentMaxKey
){
  MemPage *pPage;
  int i, rc, depth, d2, pgno, cnt;
  int hdr, cellStart;
  int nCell;
  u8 *data;
  BtShared *pBt;
  int usableSize;
  char zContext[100];
  char *hit = 0;
  i64 nMinKey = 0;
  i64 nMaxKey = 0;

  sqlite3_snprintf(sizeof(zContext), zContext, "Page %d: ", iPage);

  /* Check that the page exists
  */
  pBt = pCheck->pBt;
  usableSize = pBt->usableSize;

    */
    sqlite3_snprintf(sizeof(zContext), zContext,
             "On tree page %d cell %d: ", iPage, i);
    pCell = findCell(pPage,i);
    btreeParseCellPtr(pPage, pCell, &info);
    sz = info.nData;
    if( !pPage->intKey ) sz += (int)info.nKey;
    /* For intKey pages, check that the keys are in order.
    */
    else if( i==0 ) nMinKey = nMaxKey = info.nKey;
    else{
      if( info.nKey <= nMaxKey ){
        checkAppendMsg(pCheck, zContext, 
            "Rowid %lld out of order (previous was %lld)", info.nKey, nMaxKey);
      }
      nMaxKey = info.nKey;
    }
    assert( sz==info.nPayload );
    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( !pPage->leaf ){
      pgno = get4byte(pCell);
#ifndef SQLITE_OMIT_AUTOVACUUM
      if( pBt->autoVacuum ){
        checkPtrmap(pCheck, pgno, PTRMAP_BTREE, iPage, zContext);
      }
#endif
      d2 = checkTreePage(pCheck, pgno, zContext, &nMinKey, i==0 ? NULL : &nMaxKey);
      if( i>0 && d2!=depth ){
        checkAppendMsg(pCheck, zContext, "Child page depth differs");
      }
      depth = d2;
    }
  }

  if( !pPage->leaf ){
    pgno = get4byte(&pPage->aData[pPage->hdrOffset+8]);
    sqlite3_snprintf(sizeof(zContext), zContext, 
                     "On page %d at right child: ", iPage);
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pBt->autoVacuum ){
      checkPtrmap(pCheck, pgno, PTRMAP_BTREE, iPage, zContext);
    }
#endif
    checkTreePage(pCheck, pgno, zContext, NULL, !pPage->nCell ? NULL : &nMaxKey);
  }
 
  /* For intKey leaf pages, check that the min/max keys are in order
  ** with any left/parent/right pages.
  */
  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, zContext, 
              "Rowid %lld out of order (max larger than parent min of %lld)",
              nMaxKey, *pnParentMinKey);
        }
      }else{
        if( nMinKey <= *pnParentMinKey ){
          checkAppendMsg(pCheck, zContext, 
              "Rowid %lld out of order (min less than parent min of %lld)",
              nMinKey, *pnParentMinKey);
        }
        if( nMaxKey > *pnParentMaxKey ){
          checkAppendMsg(pCheck, zContext, 
              "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, zContext, 
            "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;
  hit = sqlite3PageMalloc( pBt->pageSize );
  if( hit==0 ){
    pCheck->mallocFailed = 1;

      u16 size = 1024;
      int j;
      if( pc<=usableSize-4 ){
        size = cellSizePtr(pPage, &data[pc]);
      }
      if( (pc+size-1)>=usableSize ){
        checkAppendMsg(pCheck, 0, 
            "Corruption detected in cell %d on page %d",i,iPage);
      }else{
        for(j=pc+size-1; j>=pc; j--) hit[j]++;
      }
    }
    i = get2byte(&data[hdr+1]);
    while( i>0 ){
      int size, j;

  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, 0);
    }
#endif
    checkTreePage(&sCheck, aRoot[i], "List of tree roots: ", NULL, NULL);
  }

  /* Make sure every page in the file is referenced
  */
  for(i=1; i<=sCheck.nPage && sCheck.mxErr; i++){
#ifdef SQLITE_OMIT_AUTOVACUUM
    if( sCheck.anRef[i]==0 ){

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 {

# 2010 February 18
#
# The author disclaims copyright to this source code.  In place of
# a legal notice, here is a blessing:
#
#    May you do good and not evil.
#    May you find forgiveness for yourself and forgive others.
#    May you share freely, never taking more than you give.
#
#***********************************************************************
# This file implements regression tests for SQLite library.
#
# This file implements tests to make sure SQLite does not crash or
# segfault if it sees a corrupt database file.  It specifcally
# focuses on rowid order corruption.
#
# $Id: corruptE.test,v 1.14 2009/07/11 06:55:34 danielk1977 Exp $

catch {file delete -force test.db test.db-journal test.bu}

set testdir [file dirname $argv0]
source $testdir/tester.tcl

# Construct a compact, dense database for testing.
#
do_test corruptE-1.1 {
  execsql {
    PRAGMA auto_vacuum = 0;
    PRAGMA legacy_file_format=1;
    BEGIN;
    CREATE TABLE t1(x,y);
    INSERT INTO t1 VALUES(1,1);
    INSERT OR IGNORE INTO t1 SELECT x*2,y FROM t1;
    INSERT OR IGNORE INTO t1 SELECT x*3,y FROM t1;
    INSERT OR IGNORE INTO t1 SELECT x*5,y FROM t1;
    INSERT OR IGNORE INTO t1 SELECT x*7,y FROM t1;
    INSERT OR IGNORE INTO t1 SELECT x*11,y FROM t1;
    INSERT OR IGNORE INTO t1 SELECT x*13,y FROM t1;
    INSERT OR IGNORE INTO t1 SELECT x*17,y FROM t1;
    INSERT OR IGNORE INTO t1 SELECT x*19,y FROM t1;
    CREATE INDEX t1i1 ON t1(x);
    CREATE TABLE t2 AS SELECT x,2 as y FROM t1 WHERE rowid%5!=0;
    COMMIT;
  }
} {}

ifcapable {integrityck} {
  integrity_check corruptE-1.2
}

# Copy file $from into $to
#
proc copy_file {from to} {
  file copy -force $from $to
}

# Setup for the tests.  Make a backup copy of the good database in test.bu.
#
db close
copy_file test.db test.bu
sqlite3 db test.db
set fsize [file size test.db]


do_test corruptE-2.1 {
  db close
  copy_file test.bu test.db

  # insert corrupt byte(s)
  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
  copy_file 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
  copy_file 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
  copy_file 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} \
                {2263 0x29} \
                {2274 0x75} \
                {3267 0xf2} \
                {4104 0x2c} \
                {5113 0x36} \
                {10233 0x84} \
                {10234 0x74} \
                {10239 0x41} \
                {10453 0x11} \
                {11273 0x28} \
                {11455 0x11} \
                {11461 0xe6} \
                {12281 0x99} \
                {12296 0x9e} \
                {12297 0xd7} \
                {13303 0x53} ]

set tc 1
foreach test $tests {
  do_test corruptE-3.$tc {
    db close
    copy_file test.bu test.db

    # insert corrupt byte(s)
    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