SQLite

/*
** 2004 April 6
**
** 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.
**
*************************************************************************
** $Id: btree.c,v 1.474 2008/07/09 11:49: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"

/*
** Defragment the page given.  All Cells are moved to the
** end of the page and all free space is collected into one
** big FreeBlk that occurs in between the header and cell
** pointer array and the cell content area.
*/
static void defragmentPage(MemPage *pPage){
  int i;                     /* Loop counter */
  int pc;                    /* Address of a i-th cell */
  int addr;                  /* Offset of first byte after cell pointer array */
  int hdr;                   /* Offset to the page header */
  int size;                  /* Size of a cell */
  int usableSize;            /* Number of usable bytes on a page */
  int cellOffset;            /* Offset to the cell pointer array */

  assert( brk>=cellOffset+2*nCell );
  put2byte(&data[hdr+5], brk);
  data[hdr+1] = 0;
  data[hdr+2] = 0;
  data[hdr+7] = 0;
  addr = cellOffset+2*nCell;
  memset(&data[addr], 0, brk-addr);

}

/*
** Allocate nByte bytes of space on a page.
**
** Return the index into pPage->aData[] of the first byte of
** the new allocation. Or return 0 if there is not enough free

  /* Allocate memory from the gap in between the cell pointer array
  ** and the cell content area.
  */
  top = get2byte(&data[hdr+5]);
  nCell = get2byte(&data[hdr+3]);
  cellOffset = pPage->cellOffset;
  if( nFrag>=60 || cellOffset + 2*nCell > top - nByte ){
    defragmentPage(pPage);
    top = get2byte(&data[hdr+5]);
  }
  top -= nByte;
  assert( cellOffset + 2*nCell <= top );
  put2byte(&data[hdr+5], top);
  return top;
}

    data = pPage->aData;
    hdr = pPage->hdrOffset;
    top = get2byte(&data[hdr+5]);
    cellOffset = pPage->cellOffset;
    end = cellOffset + 2*pPage->nCell + 2;
    ins = cellOffset + 2*i;
    if( end > top - sz ){
      defragmentPage(pPage);

      top = get2byte(&data[hdr+5]);
      assert( end + sz <= top );
    }
    idx = allocateSpace(pPage, sz);
    assert( idx>0 );
    assert( end <= get2byte(&data[hdr+5]) );
    pPage->nCell++;

  /* Set the parent of the newly allocated page to pParent. */
  pNew->pParent = pParent;
  sqlite3PagerRef(pParent->pDbPage);

  /* pPage is currently the right-child of pParent. Change this
  ** so that the right-child is the new page allocated above and
  ** pPage is the next-to-right child. 
  **
  ** Ignore the return value of the call to fillInCell(). fillInCell()
  ** may only return other than SQLITE_OK if it is required to allocate
  ** one or more overflow pages. Since an internal table B-Tree cell 
  ** may never spill over onto an overflow page (it is a maximum of 
  ** 13 bytes in size), it is not neccessary to check the return code.
  **
  ** Similarly, the insertCell() function cannot fail if the page
  ** being inserted into is already writable and the cell does not 
  ** contain an overflow pointer. So ignore this return code too.
  */
  assert( pPage->nCell>0 );
  pCell = findCell(pPage, pPage->nCell-1);
  sqlite3BtreeParseCellPtr(pPage, pCell, &info);
  fillInCell(pParent, parentCell, 0, info.nKey, 0, 0, 0, &parentSize);



  assert( parentSize<64 );
  assert( sqlite3PagerIswriteable(pParent->pDbPage) );
  insertCell(pParent, parentIdx, parentCell, parentSize, 0, 4);



  put4byte(findOverflowCell(pParent,parentIdx), pPage->pgno);
  put4byte(&pParent->aData[pParent->hdrOffset+8], pgnoNew);

#ifndef SQLITE_OMIT_AUTOVACUUM
  /* If this is an auto-vacuum database, update the pointer map
  ** with entries for the new page, and any pointer from the 
  ** cell on the page to an overflow page.

  assert( sqlite3PagerIswriteable(pPage->pDbPage) || pPage->nOverflow==1 );
  pBt = pPage->pBt;
  pParent = pPage->pParent;
  assert( pParent );
  if( SQLITE_OK!=(rc = sqlite3PagerWrite(pParent->pDbPage)) ){
    return rc;
  }

  TRACE(("BALANCE: begin page %d child of %d\n", pPage->pgno, pParent->pgno));

#ifndef SQLITE_OMIT_QUICKBALANCE
  /*
  ** A special case:  If a new entry has just been inserted into a
  ** table (that is, a btree with integer keys and all data at the leaves)
  ** and the new entry is the right-most entry in the tree (it has the

  if( pBt->autoVacuum ){
    int i;
    rc = ptrmapPut(pBt, pChild->pgno, PTRMAP_BTREE, pPage->pgno);
    if( rc ) goto balancedeeper_out;
    for(i=0; i<pChild->nCell; i++){
      rc = ptrmapPutOvfl(pChild, i);
      if( rc!=SQLITE_OK ){
        goto balancedeeper_out;
      }
    }
  }
#endif
  rc = balance_nonroot(pChild);

balancedeeper_out:

# This file implements regression tests for SQLite library.  The
# focus of this file is testing for correct handling of I/O errors
# such as writes failing because the disk is full.
# 
# The tests in this file use special facilities that are only
# available in the SQLite test fixture.
#
# $Id: ioerr.test,v 1.40 2008/07/09 11:49:48 danielk1977 Exp $

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

# If SQLITE_DEFAULT_AUTOVACUUM is set to true, then a simulated IO error
# on the 8th IO operation in the SQL script below doesn't report an error.
#

  db eval { PRAGMA page_size = 1024 }
  db eval { CREATE TABLE t1(x) }
  db eval { INSERT INTO t1 VALUES(randomblob(1100)); }
} -tclbody {
  db eval { INSERT INTO t1 VALUES(randomblob(2000)); }
}
sqlite3_simulate_device -char {} -sectorsize 0
catch {db close}

do_ioerr_test ioerr-13 -ckrefcount true -erc 1 -sqlprep {
  PRAGMA auto_vacuum = incremental;
  CREATE TABLE t1(x);
  CREATE TABLE t2(x);
  INSERT INTO t2 VALUES(randomblob(1500));
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t1 VALUES(randomblob(20));
  INSERT INTO t1 SELECT x FROM t1;
  INSERT INTO t1 SELECT x FROM t1;
  INSERT INTO t1 SELECT x FROM t1;
  INSERT INTO t1 SELECT x FROM t1;
  INSERT INTO t1 SELECT x FROM t1;
  INSERT INTO t1 SELECT x FROM t1;             /* 64 entries in t1 */
  INSERT INTO t1 SELECT x FROM t1 LIMIT 14;    /* 78 entries in t1 */
  DELETE FROM t2 WHERE rowid = 3;
} -sqlbody {
  -- This statement uses the balance_quick() optimization. The new page
  -- is appended to the database file. But the overflow page used by
  -- the new record will be positioned near the start of the database
  -- file, in the gap left by the "DELETE FROM t2 WHERE rowid=3" statement
  -- above.
  --
  -- The point of this is that the statement wil need to update two pointer
  -- map pages. Which introduces another opportunity for an IO error.
  --
  INSERT INTO t1 VALUES(randomblob(2000));
}

do_ioerr_test ioerr-14 -ckrefcount true -erc 1 -sqlprep {
  PRAGMA auto_vacuum = incremental;
  CREATE TABLE t1(x);
  CREATE TABLE t2(x);
  INSERT INTO t2 VALUES(randomblob(1500));
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;
  INSERT INTO t2 SELECT randomblob(1500) FROM t2;

  -- This statement inserts a row into t1 with an overflow page at the
  -- end of the file. A long way from its parent (the root of t1).
  INSERT INTO t1 VALUES(randomblob(1500));
  DELETE FROM t2 WHERE rowid<10;
} -sqlbody {
  -- This transaction will cause the root-page of table t1 to divide
  -- (by calling balance_deeper()). When it does, the "parent" page of the
  -- overflow page inserted in the -sqlprep block above will change and
  -- the corresponding pointer map page be updated. This test case attempts
  -- to cause an IO error during the pointer map page update.
  --
  BEGIN;
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  INSERT INTO t1 VALUES(randomblob(100));
  COMMIT;
}

finish_test