SQLite

**      3.  Check the integrity of overflow pages.
**      4.  Recursively call checkTreePage on all children.
**      5.  Verify that the depth of all children is the same.
*/
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 = 0;


  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);
    depth = -1;
    goto end_of_check;
  }



  /* Check out all the cells.
  */
  depth = 0;
  pCheck->zPfx = "On tree page %d cell %d: ";


  for(i=0; i<pPage->nCell && pCheck->mxErr; i++){




    u8 *pCell;





    u32 sz;






















    CellInfo info;

    /* Check payload overflow pages
    */
    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: ";
#ifndef SQLITE_OMIT_AUTOVACUUM
    if( pBt->autoVacuum ){
      checkPtrmap(pCheck, pgno, PTRMAP_BTREE, iPage);
    }
#endif
    d2 = checkTreePage(pCheck, pgno, NULL, !pPage->nCell?NULL:&nMaxKey);
    if( d2!=depth && iPage!=1 ){
      checkAppendMsg(pCheck, "Child page depth differs");
    }
  }
 
  /* For intKey leaf pages, check that the min/max keys are in order
  ** with any left/parent/right pages.
  */
  pCheck->zPfx = "Page %d: ";
  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 = pCheck->heap;
  heap[0] = 0;
  pCheck->zPfx = 0;
  {
    int contentOffset = get2byteNotZero(&data[hdr+5]);
    assert( contentOffset<=usableSize );  /* Enforced by btreeInitPage() */
    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( i<=usableSize-4 );     /* Enforced by btreeInitPage() */
      size = get2byte(&data[i+2]);
      assert( i+size<=usableSize );  /* Enforced by btreeInitPage() */
      btreeHeapInsert(heap, (i<<16)|(i+size-1));
      /* EVIDENCE-OF: R-58208-19414 The first 2 bytes of a freeblock are a
      ** big-endian integer which is the offset in the b-tree page of the next
      ** freeblock in the chain, or zero if the freeblock is the last on the
      ** chain. */
      j = get2byte(&data[i]);
      /* EVIDENCE-OF: R-06866-39125 Freeblocks are always connected in order of
      ** increasing offset. */
      assert( j==0 || j>i+size );  /* Enforced by btreeInitPage() */
      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);
    }
  }

end_of_check:
  releasePage(pPage);
  pCheck->zPfx = saved_zPfx;
  pCheck->v1 = saved_v1;

  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;
  VVA_ONLY( int nRef );
  IntegrityCk sCheck;
  BtShared *pBt = p->pBt;

  char zErr[100];


  sqlite3BtreeEnter(p);
  assert( p->inTrans>TRANS_NONE && pBt->inTransaction>TRANS_NONE );
  assert( (nRef = sqlite3PagerRefcount(pBt->pPager))>=0 );
  sCheck.pBt = pBt;
  sCheck.pPager = pBt->pPager;
  sCheck.nPage = btreePagecount(sCheck.pBt);

  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
    checkTreePage(&sCheck, aRoot[i], 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( getPageReferenced(&sCheck, i)==0 ){
      checkAppendMsg(&sCheck, "Page %d is never used", i);

  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) {}

  hexio_get_int [hexio_read test.db 20 1]
} 0      ;# Unused bytes per page is 0

integrity_check corrupt7-1.4

# 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;

#***********************************************************************
# 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 $

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

# Do not use a codec for tests in this file, as the database file is
# manipulated directly using tcl scripts (using the [hexio_write] command).
#

  forcecopy 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
  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} \
                {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
    forcecopy 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