** 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.
**
*************************************************************************
** $Id: btree.c,v 1.509 2008/09/05 05:02:47 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"

................................................................................
  pBt = pPage->pBt;
  assert( pBt!=0 );
  assert( pParent==0 || pParent->pBt==pBt );
  assert( sqlite3_mutex_held(pBt->mutex) );
  assert( pPage->pgno==sqlite3PagerPagenumber(pPage->pDbPage) );
  assert( pPage == sqlite3PagerGetExtra(pPage->pDbPage) );
  assert( pPage->aData == sqlite3PagerGetData(pPage->pDbPage) );



  if( pPage->pParent!=pParent && (pPage->pParent!=0 || pPage->isInit) ){
    /* The parent page should never change unless the file is corrupt */
    return SQLITE_CORRUPT_BKPT;
  }
  if( pPage->isInit ) return SQLITE_OK;
  if( pPage->pParent==0 && pParent!=0 ){
    pPage->pParent = pParent;
................................................................................
  BtShared *pBt,          /* The database file */
  Pgno pgno,           /* Number of the page to get */
  MemPage **ppPage,    /* Write the page pointer here */
  MemPage *pParent     /* Parent of the page */
){
  int rc;
  assert( sqlite3_mutex_held(pBt->mutex) );

  if( pgno==0 ){
    return SQLITE_CORRUPT_BKPT; 
  }
  rc = sqlite3BtreeGetPage(pBt, pgno, ppPage, 0);

  if( rc==SQLITE_OK && (*ppPage)->isInit==0 ){
    rc = sqlite3BtreeInitPage(*ppPage, pParent);







    if( rc!=SQLITE_OK ){
      releasePage(*ppPage);
      *ppPage = 0;
    }
  }

  return rc;
}

/*
** Release a MemPage.  This should be called once for each prior
** call to sqlite3BtreeGetPage.
*/
................................................................................
  }

  rc = getAndInitPage(pBt, pgno, &pPage, pParent);
  if( rc ) goto cleardatabasepage_out;
  for(i=0; i<pPage->nCell; i++){
    pCell = findCell(pPage, i);
    if( !pPage->leaf ){
      rc = clearDatabasePage(pBt, get4byte(pCell), pPage->pParent, 1);
      if( rc ) goto cleardatabasepage_out;
    }
    rc = clearCell(pPage, pCell);
    if( rc ) goto cleardatabasepage_out;
  }
  if( !pPage->leaf ){
    rc = clearDatabasePage(pBt, get4byte(&pPage->aData[8]), pPage->pParent, 1);
    if( rc ) goto cleardatabasepage_out;
  }
  if( freePageFlag ){
    rc = freePage(pPage);
  }else if( (rc = sqlite3PagerWrite(pPage->pDbPage))==0 ){
    zeroPage(pPage, pPage->aData[0] | PTF_LEAF);
  }

** 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.
**
*************************************************************************
** $Id: btree.c,v 1.510 2008/09/10 14:45:58 danielk1977 Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
** Including a description of file format and an overview of operation.
*/
#include "btreeInt.h"

................................................................................
  pBt = pPage->pBt;
  assert( pBt!=0 );
  assert( pParent==0 || pParent->pBt==pBt );
  assert( sqlite3_mutex_held(pBt->mutex) );
  assert( pPage->pgno==sqlite3PagerPagenumber(pPage->pDbPage) );
  assert( pPage == sqlite3PagerGetExtra(pPage->pDbPage) );
  assert( pPage->aData == sqlite3PagerGetData(pPage->pDbPage) );
  if( pPage==pParent ){
    return SQLITE_CORRUPT_BKPT;
  }
  if( pPage->pParent!=pParent && (pPage->pParent!=0 || pPage->isInit) ){
    /* The parent page should never change unless the file is corrupt */
    return SQLITE_CORRUPT_BKPT;
  }
  if( pPage->isInit ) return SQLITE_OK;
  if( pPage->pParent==0 && pParent!=0 ){
    pPage->pParent = pParent;
................................................................................
  BtShared *pBt,          /* The database file */
  Pgno pgno,           /* Number of the page to get */
  MemPage **ppPage,    /* Write the page pointer here */
  MemPage *pParent     /* Parent of the page */
){
  int rc;
  assert( sqlite3_mutex_held(pBt->mutex) );
  assert( !pParent || pParent->isInit );
  if( pgno==0 ){
    return SQLITE_CORRUPT_BKPT; 
  }
  rc = sqlite3BtreeGetPage(pBt, pgno, ppPage, 0);
  if( rc==SQLITE_OK ){
    if( (*ppPage)->isInit==0 ){
      rc = sqlite3BtreeInitPage(*ppPage, pParent);
    }else if( pParent && ((*ppPage)==pParent || (*ppPage)->pParent!=pParent) ){
      /* This condition indicates a loop in the b-tree structure (the scenario
      ** where database corruption has caused a page to be a direct or
      ** indirect descendant of itself).
      */ 
      rc = SQLITE_CORRUPT_BKPT;
    }
    if( rc!=SQLITE_OK ){
      releasePage(*ppPage);
      *ppPage = 0;
    }
  }

  return rc;
}

/*
** Release a MemPage.  This should be called once for each prior
** call to sqlite3BtreeGetPage.
*/
................................................................................
  }

  rc = getAndInitPage(pBt, pgno, &pPage, pParent);
  if( rc ) goto cleardatabasepage_out;
  for(i=0; i<pPage->nCell; i++){
    pCell = findCell(pPage, i);
    if( !pPage->leaf ){
      rc = clearDatabasePage(pBt, get4byte(pCell), pPage, 1);
      if( rc ) goto cleardatabasepage_out;
    }
    rc = clearCell(pPage, pCell);
    if( rc ) goto cleardatabasepage_out;
  }
  if( !pPage->leaf ){
    rc = clearDatabasePage(pBt, get4byte(&pPage->aData[8]), pPage, 1);
    if( rc ) goto cleardatabasepage_out;
  }
  if( freePageFlag ){
    rc = freePage(pPage);
  }else if( (rc = sqlite3PagerWrite(pPage->pDbPage))==0 ){
    zeroPage(pPage, pPage->aData[0] | PTF_LEAF);
  }

# 2008 Sep 10
#
# 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 specifically focuses
# on loops in the B-Tree structure. A loop is formed in a B-Tree structure
# when there exists a page that is both an a descendent or ancestor of
# itself.
#
# $Id: corruptB.test,v 1.1 2008/09/10 14:45:58 danielk1977 Exp $

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


do_test corruptB-1.1 {
  execsql {
    PRAGMA auto_vacuum = 1;
    CREATE TABLE t1(x);
    INSERT INTO t1 VALUES(randomblob(200));
    INSERT INTO t1 SELECT randomblob(200) FROM t1;
    INSERT INTO t1 SELECT randomblob(200) FROM t1;
    INSERT INTO t1 SELECT randomblob(200) FROM t1;
    INSERT INTO t1 SELECT randomblob(200) FROM t1;
    INSERT INTO t1 SELECT randomblob(200) FROM t1;
  }
  expr {[file size test.db] > (1024*9)}
} {1}
integrity_check corruptB-1.2

file copy -force test.db bak.db

# Set the right-child of a B-Tree rootpage to refer to the root-page itself.
#
do_test corruptB-1.3.1 {
  set ::root [execsql {SELECT rootpage FROM sqlite_master}]
  set ::offset [expr {($::root-1)*1024}]
  hexio_write test.db [expr $offset+8] [hexio_render_int32 $::root]
} {4}
do_test corruptB-1.3.2 {
  sqlite3 db test.db
  catchsql { SELECT * FROM t1 }
} {1 {database disk image is malformed}}

# Set the left-child of a cell in a B-Tree rootpage to refer to the 
# root-page itself.
#
do_test corruptB-1.4.1 {
  db close
  file copy -force bak.db test.db
  set cell_offset [hexio_get_int [hexio_read test.db [expr $offset+12] 2]]
  hexio_write test.db [expr $offset+$cell_offset] [hexio_render_int32 $::root]
} {4}
do_test corruptB-1.4.2 {
  sqlite3 db test.db
  catchsql { SELECT * FROM t1 }
} {1 {database disk image is malformed}}

# Now grow the table B-Tree so that it is more than 2 levels high.
#
do_test corruptB-1.5.1 {
  db close
  file copy -force bak.db test.db
  sqlite3 db test.db
  execsql {
    INSERT INTO t1 SELECT randomblob(200) FROM t1;
    INSERT INTO t1 SELECT randomblob(200) FROM t1;
    INSERT INTO t1 SELECT randomblob(200) FROM t1;
    INSERT INTO t1 SELECT randomblob(200) FROM t1;
    INSERT INTO t1 SELECT randomblob(200) FROM t1;
    INSERT INTO t1 SELECT randomblob(200) FROM t1;
    INSERT INTO t1 SELECT randomblob(200) FROM t1;
  }
} {}

file copy -force test.db bak.db

# Set the right-child pointer of the right-child of the root page to point
# back to the root page.
#
do_test corruptB-1.6.1 {
  db close
  set iRightChild [hexio_get_int [hexio_read test.db [expr $offset+8] 4]]
  set c_offset [expr ($iRightChild-1)*1024]
  hexio_write test.db [expr $c_offset+8] [hexio_render_int32 $::root]
} {4}
do_test corruptB-1.6.2 {
  sqlite3 db test.db
  catchsql { SELECT * FROM t1 }
} {1 {database disk image is malformed}}

# Set the left-child pointer of a cell of the right-child of the root page to
# point back to the root page.
#
do_test corruptB-1.7.1 {
  db close
  file copy -force bak.db test.db
  set cell_offset [hexio_get_int [hexio_read test.db [expr $c_offset+12] 2]]
  hexio_write test.db [expr $c_offset+$cell_offset] [hexio_render_int32 $::root]
} {4}
do_test corruptB-1.7.2 {
  sqlite3 db test.db
  catchsql { SELECT * FROM t1 }
} {1 {database disk image is malformed}}

do_test corruptB-1.8.1 {
  db close
  set cell_offset [hexio_get_int [hexio_read test.db [expr $offset+12] 2]]
  set iLeftChild [
      hexio_get_int [hexio_read test.db [expr $offset+$cell_offset] 4]
  ]
  set c_offset [expr ($iLeftChild-1)*1024]
  hexio_write test.db [expr $c_offset+8] [hexio_render_int32 $::root]
} {4}
do_test corruptB-1.8.2 {
  sqlite3 db test.db
  catchsql { SELECT * FROM t1 }
} {1 {database disk image is malformed}}

# Set the left-child pointer of a cell of the right-child of the root page to
# point back to the root page.
#
do_test corruptB-1.9.1 {
  db close
  file copy -force bak.db test.db
  set cell_offset [hexio_get_int [hexio_read test.db [expr $c_offset+12] 2]]
  hexio_write test.db [expr $c_offset+$cell_offset] [hexio_render_int32 $::root]
} {4}
do_test corruptB-1.9.2 {
  sqlite3 db test.db
  catchsql { SELECT * FROM t1 }
} {1 {database disk image is malformed}}

finish_test