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.181 2004/08/08 19:43:30 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** For a detailed discussion of BTrees, refer to
**
**     Donald E. Knuth, THE ART OF COMPUTER PROGRAMMING, Volume 3:
**     "Sorting And Searching", pages 473-480. Addison-Wesley
**     Publishing Company, Reading, Massachusetts.

** A cursor is a pointer to a particular entry in the BTree.
** The entry is identified by its MemPage and the index in
** MemPage.aCell[] of the entry.
*/
struct BtCursor {
  Btree *pBt;               /* The Btree to which this cursor belongs */
  BtCursor *pNext, *pPrev;  /* Forms a linked list of all cursors */

  int (*xCompare)(void*,int,const void*,int,const void*); /* Key comp func */
  void *pArg;               /* First arg to xCompare() */
  Pgno pgnoRoot;            /* The root page of this tree */
  MemPage *pPage;           /* Page that contains the entry */
  int idx;                  /* Index of the entry in pPage->aCell[] */
  CellInfo info;            /* A parse of the cell we are pointing at */
  u8 wrFlag;                /* True if writable */

  int iTable,                                 /* Root page of table to open */
  int wrFlag,                                 /* 1 to write. 0 read-only */
  int (*xCmp)(void*,int,const void*,int,const void*), /* Key Comparison func */
  void *pArg,                                 /* First arg to xCompare() */
  BtCursor **ppCur                            /* Write new cursor here */
){
  int rc;
  BtCursor *pCur;


  *ppCur = 0;
  if( wrFlag ){
    static int checkReadLocks(Btree*,Pgno,BtCursor*);
    if( pBt->readOnly ){
      return SQLITE_READONLY;
    }
    if( checkReadLocks(pBt, iTable, 0) ){
      return SQLITE_LOCKED;
    }
  }
  if( pBt->pPage1==0 ){
    rc = lockBtree(pBt);
    if( rc!=SQLITE_OK ){

      return rc;
    }
  }
  pCur = sqliteMallocRaw( sizeof(*pCur) );
  if( pCur==0 ){
    rc = SQLITE_NOMEM;
    goto create_cursor_exception;

  pCur->idx = 0;
  memset(&pCur->info, 0, sizeof(pCur->info));
  pCur->pNext = pBt->pCursor;
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur;
  }
  pCur->pPrev = 0;








  pBt->pCursor = pCur;
  pCur->isValid = 0;
  pCur->status = SQLITE_OK;
  *ppCur = pCur;
  return SQLITE_OK;

create_cursor_exception:

  if( pCur ){
    releasePage(pCur->pPage);
    sqliteFree(pCur);
  }
  unlockBtreeIfUnused(pBt);
  return rc;
}

  }else{
    pBt->pCursor = pCur->pNext;
  }
  if( pCur->pNext ){
    pCur->pNext->pPrev = pCur->pPrev;
  }
  releasePage(pCur->pPage);





  unlockBtreeIfUnused(pBt);
  sqliteFree(pCur);
  return SQLITE_OK;
}

/*
** Make a temporary cursor by filling in the fields of pTempCur.

      rc = balance_nonroot(pPage);
    }
  }
  return rc;
}

/*
** This routine checks all cursors that point to table pgnoRoot.
** If any of those cursors other than pExclude were opened with 
** wrFlag==0 then this routine returns SQLITE_LOCKED.  If all
** cursors that point to pgnoRoot were opened with wrFlag==1
** then this routine returns SQLITE_OK.
**
** In addition to checking for read-locks (where a read-lock 
** means a cursor opened with wrFlag==0) this routine also moves
** all cursors other than pExclude so that they are pointing to the 
** first Cell on root page.  This is necessary because an insert 
** or delete might change the number of cells on a page or delete
** a page entirely and we do not want to leave any cursors 
** pointing to non-existant pages or cells.
*/
static int checkReadLocks(Btree *pBt, Pgno pgnoRoot, BtCursor *pExclude){
  BtCursor *p;

  for(p=pBt->pCursor; p; p=p->pNext){

    if( p->pgnoRoot!=pgnoRoot || p==pExclude ) continue;

    if( p->wrFlag==0 ) return SQLITE_LOCKED;
    if( p->pPage->pgno!=p->pgnoRoot ){
      moveToRoot(p);
    }
  }
  return SQLITE_OK;
}

    /* Must start a transaction before doing an insert */
    return pBt->readOnly ? SQLITE_READONLY : SQLITE_ERROR;
  }
  assert( !pBt->readOnly );
  if( !pCur->wrFlag ){
    return SQLITE_PERM;   /* Cursor not open for writing */
  }
  if( checkReadLocks(pBt, pCur->pgnoRoot, pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }
  rc = sqlite3BtreeMoveto(pCur, pKey, nKey, &loc);
  if( rc ) return rc;
  pPage = pCur->pPage;
  assert( pPage->intKey || nKey>=0 );
  assert( pPage->leaf || !pPage->leafData );

  assert( !pBt->readOnly );
  if( pCur->idx >= pPage->nCell ){
    return SQLITE_ERROR;  /* The cursor is not pointing to anything */
  }
  if( !pCur->wrFlag ){
    return SQLITE_PERM;   /* Did not open this cursor for writing */
  }
  if( checkReadLocks(pBt, pCur->pgnoRoot, pCur) ){
    return SQLITE_LOCKED; /* The table pCur points to has a read lock */
  }
  rc = sqlite3pager_write(pPage->aData);
  if( rc ) return rc;
  pCell = findCell(pPage, pCur->idx);
  if( !pPage->leaf ){
    pgnoChild = get4byte(pCell);

# 2003 September 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.
#
#***********************************************************************
# This file implements regression tests for SQLite library.  The
# focus of this script is a test to replicate the bug reported by
# ticket #842.
#
# Ticket #842 was a database corruption problem caused by a DELETE that
# removed an index entry by not the main table entry.  To recreate the
# problem do this:
#
#   (1) Create a table with an index.  Insert some data into that table.
#   (2) Start a query on the table but do not complete the query.
#   (3) Try to delete a single entry from the table.
#
# Step 3 will fail because there is still a read cursor on the table.
# But the database is corrupted by the DELETE.  It turns out that the
# index entry was deleted first, before the table entry.  And the index
# delete worked.  Thus an entry was deleted from the index but not from
# the table.
#
# The solution to the problem was to detect that the table is locked
# before the index entry is deleted.
#
# $Id: delete2.test,v 1.1 2004/08/08 19:43:30 drh Exp $
#

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

# Create a table that has an index.
#
do_test delete2-1.1 {
  db close
  set DB [sqlite3 db test.db]
  execsql {
    CREATE TABLE q(s string, id string, constraint pk_q primary key(id));
    BEGIN;
    INSERT INTO q(s,id) VALUES('hello','id.1');
    INSERT INTO q(s,id) VALUES('goodbye','id.2');
    INSERT INTO q(s,id) VALUES('again','id.3');
    END;
    SELECT * FROM q;
  }
} {hello id.1 goodbye id.2 again id.3}
do_test delete2-1.2 {
  execsql {
    SELECT * FROM q WHERE id='id.1';
  }
} {hello id.1}
do_test delete2-1.3 {
  execsql {
    PRAGMA integrity_check
  }
} ok

# Start a query on the table.  The query should not use the index.
# Do not complete the query, thus leaving the table locked.
#
do_test delete2-1.4 {
  set STMT [sqlite3_prepare $DB {SELECT * FROM q} -1 TAIL]
  sqlite3_step $STMT
} SQLITE_ROW
do_test delete2-1.5 {
  execsql {PRAGMA integrity_check}
} {ok}

# Try to delete a row from the table.  The delete should fail.
#
do_test delete2-1.6 {
  catchsql {
    DELETE FROM q WHERE rowid=1
  }
} {1 {database table is locked}}
do_test delete2-1.7 {
  execsql {PRAGMA integrity_check}
} {ok}
do_test delete2-1.8 {
  execsql {
    SELECT * FROM q;
  }
} {hello id.1 goodbye id.2 again id.3}

# Finalize the query, thus clearing the lock on the table.  Then
# retry the delete.  The delete should work this time.
#
do_test delete2-1.9 {
  sqlite3_finalize $STMT
  catchsql {
    DELETE FROM q WHERE rowid=1
  }
} {0 {}}
do_test delete2-1.10 {
  execsql {PRAGMA integrity_check}
} {ok}
do_test delete2-1.11 {
  execsql {
    SELECT * FROM q;
  }
} {goodbye id.2 again id.3}

finish_test