Work toward correct btree locking in a multithreaded environment. (CVS 4307)
FossilOrigin-Name: b8cc493b47e618648f645ab73eb0253739e03fcd
diff --git a/src/btmutex.c b/src/btmutex.c
new file mode 100644
index 0000000..4725910
--- /dev/null
+++ b/src/btmutex.c
@@ -0,0 +1,199 @@
+/*
+** 2007 August 27
+**
+** 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: btmutex.c,v 1.1 2007/08/28 02:27:52 drh Exp $
+**
+** This file contains code used to implement mutexes on Btree objects.
+** This code really belongs in btree.c. But btree.c is getting too
+** big and we want to break it down some. This packaged seemed like
+** a good breakout.
+*/
+#include "btreeInt.h"
+#if SQLITE_THREADSAFE && !defined(SQLITE_OMIT_SHARED_CACHE)
+
+
+/*
+** Enter a mutex on the given BTree object.
+**
+** If the object is not sharable, then no mutex is ever required
+** and this routine is a no-op. The underlying mutex is non-recursive.
+** But we keep a reference count in Btree.wantToLock so the behavior
+** of this interface is recursive.
+**
+** To avoid deadlocks, multiple Btrees are locked in the same order
+** by all database connections. The p->pNext is a list of other
+** Btrees belonging to the same database connection as the p Btree
+** which need to be locked after p. If we cannot get a lock on
+** p, then first unlock all of the others on p->pNext, then wait
+** for the lock to become available on p, then relock all of the
+** subsequent Btrees that desire a lock.
+*/
+void sqlite3BtreeEnter(Btree *p){
+ Btree *pLater;
+
+ /* Some basic sanity checking on the Btree. The list of Btrees
+ ** connected by pNext and pPrev should be in sorted order by
+ ** Btree.pBt value. All elements of the list should belong to
+ ** the same connection. Only shared Btrees are on the list. */
+ assert( p->pNext==0 || p->pNext->pBt>p->pBt );
+ assert( p->pPrev==0 || p->pPrev->pBt<p->pBt );
+ assert( p->pNext==0 || p->pNext->pSqlite==p->pSqlite );
+ assert( p->pPrev==0 || p->pPrev->pSqlite==p->pSqlite );
+ assert( p->sharable || (p->pNext==0 && p->pPrev==0) );
+
+ /* Check for locking consistency */
+ assert( !p->locked || p->wantToLock>0 );
+ assert( p->sharable || p->wantToLock==0 );
+
+ /* We should already hold a lock on the database connection */
+ assert( sqlite3BtreeMutexHeld(p->pSqlite->mutex) );
+
+ if( !p->sharable ) return;
+ p->wantToLock++;
+ if( p->locked ) return;
+
+ /* In most cases, we should be able to acquire the lock we
+ ** want without having to go throught the ascending lock
+ ** procedure that follows. Just be sure not to block.
+ */
+ if( sqlite3_mutex_try(p->pBt->mutex)==SQLITE_OK ){
+ p->locked = 1;
+ return;
+ }
+
+ /* To avoid deadlock, first release all locks with a larger
+ ** BtShared address. Then acquire our lock. Then reacquire
+ ** the other BtShared locks that we used to hold in ascending
+ ** order.
+ */
+ for(pLater=p->pNext; pLater; pLater=pLater->pNext){
+ assert( pLater->sharable );
+ assert( pLater->pNext==0 || pLater->pNext->pBt>pLater->pBt );
+ assert( !pLater->locked || pLater->wantToLock>0 );
+ if( pLater->locked ){
+ sqlite3_mutex_leave(pLater->pBt->mutex);
+ pLater->locked = 0;
+ }
+ }
+ sqlite3_mutex_enter(p->pBt->mutex);
+ for(pLater=p->pNext; pLater; pLater=pLater->pNext){
+ if( pLater->wantToLock ){
+ sqlite3_mutex_enter(pLater->pBt->mutex);
+ pLater->locked = 1;
+ }
+ }
+}
+
+/*
+** Exit the recursive mutex on a Btree.
+*/
+void sqlite3BtreeLeave(Btree *p){
+ if( p->sharable ){
+ assert( p->wantToLock>0 );
+ p->wantToLock--;
+ if( p->wantToLock==0 ){
+ assert( p->locked );
+ sqlite3_mutex_leave(p->pBt->mutex);
+ p->locked = 0;
+ }
+ }
+}
+
+/*
+** Potentially dd a new Btree pointer to a BtreeMutexSet.
+** Really only add the Btree if it can possibly be shared with
+** another database connection.
+**
+** The Btrees are kept in sorted order by pBtree->pBt. That
+** way when we go to enter all the mutexes, we can enter them
+** in order without every having to backup and retry and without
+** worrying about deadlock.
+**
+** The number of shared btrees will always be small (usually 0 or 1)
+** so an insertion sort is an adequate algorithm here.
+*/
+void sqlite3BtreeMutexSetInsert(BtreeMutexSet *pSet, Btree *pBtree){
+ int i, j;
+ BtShared *pBt;
+ if( !pBtree->sharable ) return;
+#ifndef NDEBUG
+ {
+ for(i=0; i<pSet->nMutex; i++){
+ assert( pSet->aBtree[i]!=pBtree );
+ }
+ }
+#endif
+ assert( pSet->nMutex>=0 );
+ assert( pSet->nMutex<sizeof(pSet->aBtree)/sizeof(pSet->aBtree[0])-1 );
+ pBt = pBtree->pBt;
+ for(i=0; i<pSet->nMutex; i++){
+ assert( pSet->aBtree[i]!=pBtree );
+ if( pSet->aBtree[i]->pBt>pBt ){
+ for(j=pSet->nMutex; j>i; j--){
+ pSet->aBtree[j] = pSet->aBtree[j-1];
+ }
+ pSet->aBtree[i] = pBtree;
+ return;
+ }
+ }
+ pSet->aBtree[pSet->nMutex++] = pBtree;
+}
+
+/*
+** Enter the mutex of every btree in the set. This routine is
+** called at the beginning of sqlite3VdbeExec(). The mutexes are
+** exited at the end of the same function.
+*/
+void sqlite3BtreeMutexSetEnter(BtreeMutexSet *pSet){
+ int i;
+ for(i=0; i<pSet->nMutex; i++){
+ Btree *p = pSet->aBtree[i];
+ /* Some basic sanity checking */
+ assert( i==0 || pSet->aBtree[i-1]->pBt<p->pBt );
+ assert( !p->locked || p->wantToLock>0 );
+ assert( p->sharable );
+
+ /* We should already hold a lock on the database connection */
+ assert( sqlite3BtreeMutexHeld(p->pSqlite->mutex) );
+
+ p->wantToLock++;
+ if( !p->locked ){
+ sqlite3_mutex_enter(p->pBt->mutex);
+ }
+ }
+}
+
+/*
+** Leave the mutex of every btree in the set.
+*/
+void sqlite3BtreeMutexSetLeave(BtreeMutexSet *pSet){
+ int i;
+ for(i=0; i<pSet->nMutex; i++){
+ Btree *p = pSet->aBtree[i];
+ /* Some basic sanity checking */
+ assert( i==0 || pSet->aBtree[i-1]->pBt<p->pBt );
+ assert( p->locked );
+ assert( p->sharable );
+ assert( p->wantToLock>0 );
+
+ /* We should already hold a lock on the database connection */
+ assert( sqlite3BtreeMutexHeld(p->pSqlite->mutex) );
+
+ p->wantToLock--;
+ if( p->wantToLock==0 ){
+ sqlite3_mutex_leave(p->pBt->mutex);
+ }
+ }
+}
+
+
+#endif /* SQLITE_THREADSAFE && !SQLITE_OMIT_SHARED_CACHE */
diff --git a/src/btree.c b/src/btree.c
index 3d4e55a..cd7b3e1 100644
--- a/src/btree.c
+++ b/src/btree.c
@@ -9,7 +9,7 @@
** May you share freely, never taking more than you give.
**
*************************************************************************
-** $Id: btree.c,v 1.412 2007/08/24 11:52:29 danielk1977 Exp $
+** $Id: btree.c,v 1.413 2007/08/28 02:27:52 drh Exp $
**
** This file implements a external (disk-based) database using BTrees.
** See the header comment on "btreeInt.h" for additional information.
@@ -1388,98 +1388,6 @@
#if SQLITE_THREADSAFE && !defined(SQLITE_OMIT_SHARED_CACHE)
/*
-** Enter a mutex on the given BTree object.
-**
-** If the object is not sharable, then no mutex is ever required
-** and this routine is a no-op. The underlying mutex is non-recursive.
-** But we keep a reference count in Btree.wantToLock so the behavior
-** of this interface is recursive.
-**
-** To avoid deadlocks, multiple Btrees are locked in the same order
-** by all database connections. The p->pNext is a list of other
-** Btrees belonging to the same database connection as the p Btree
-** which need to be locked after p. If we cannot get a lock on
-** p, then first unlock all of the others on p->pNext, then wait
-** for the lock to become available on p, then relock all of the
-** subsequent Btrees that desire a lock.
-*/
-void sqlite3BtreeEnter(Btree *p){
- Btree *pLater;
-
- /* Some basic sanity checking on the Btree. The list of Btrees
- ** connected by pNext and pPrev should be in sorted order by
- ** Btree.pBt value. All elements of the list should belong to
- ** the same connection. Only shared Btrees are on the list. */
- assert( p->pNext==0 || p->pNext->pBt>p->pBt );
- assert( p->pPrev==0 || p->pPrev->pBt<p->pBt );
- assert( p->pNext==0 || p->pNext->pSqlite==p->pSqlite );
- assert( p->pPrev==0 || p->pPrev->pSqlite==p->pSqlite );
- assert( p->sharable || (p->pNext==0 && p->pPrev==0) );
-
- /* Check for locking consistency */
- assert( !p->locked || p->wantToLock>0 );
- assert( p->sharable || p->wantToLock==0 );
-
- /* We should already hold a lock on the database connection */
- assert( sqlite3BtreeMutexHeld(p->pSqlite->mutex) );
-
- if( !p->sharable ) return;
- p->wantToLock++;
- if( p->locked ) return;
-
- /* In most cases, we should be able to acquire the lock we
- ** want without having to go throught the ascending lock
- ** procedure that follows. Just be sure not to block.
- */
- if( sqlite3_mutex_try(p->pBt->mutex)==SQLITE_OK ){
- p->locked = 1;
- return;
- }
-
- /* To avoid deadlock, first release all locks with a larger
- ** BtShared address. Then acquire our lock. Then reacquire
- ** the other BtShared locks that we used to hold in ascending
- ** order.
- */
- for(pLater=p->pNext; pLater; pLater=pLater->pNext){
- assert( pLater->sharable );
- assert( pLater->pNext==0 || pLater->pNext->pBt>pLater->pBt );
- assert( !pLater->locked || pLater->wantToLock>0 );
- if( pLater->locked ){
- sqlite3_mutex_leave(pLater->pBt->mutex);
- pLater->locked = 0;
- }
- }
- sqlite3_mutex_enter(p->pBt->mutex);
- for(pLater=p->pNext; pLater; pLater=pLater->pNext){
- if( pLater->wantToLock ){
- sqlite3_mutex_enter(pLater->pBt->mutex);
- pLater->locked = 1;
- }
- }
-}
-#endif /* !SQLITE_OMIT_SHARED_CACHE */
-
-/*
-** Exit the recursive mutex on a Btree.
-*/
-#if SQLITE_THREADSAFE && !defined(SQLITE_OMIT_SHARED_CACHE)
-void sqlite3BtreeLeave(Btree *p){
- if( p->sharable ){
- assert( p->wantToLock>0 );
- p->wantToLock--;
- if( p->wantToLock==0 ){
- assert( p->locked );
- sqlite3_mutex_leave(p->pBt->mutex);
- p->locked = 0;
- }
- }
-}
-#endif
-
-
-#if SQLITE_THREADSAFE && !defined(SQLITE_OMIT_SHARED_CACHE)
-/*
** Short-cuts for entering and leaving mutexes on a cursor.
*/
static void cursorLeave(BtCursor *p){
@@ -6680,7 +6588,6 @@
*/
const char *sqlite3BtreeGetFilename(Btree *p){
assert( p->pBt->pPager!=0 );
- assert( sqlite3BtreeMutexHeld(p->pBt->mutex) );
return sqlite3PagerFilename(p->pBt->pPager);
}
@@ -6689,7 +6596,6 @@
*/
const char *sqlite3BtreeGetDirname(Btree *p){
assert( p->pBt->pPager!=0 );
- assert( sqlite3BtreeMutexHeld(p->pBt->mutex) );
return sqlite3PagerDirname(p->pBt->pPager);
}
@@ -6700,7 +6606,6 @@
*/
const char *sqlite3BtreeGetJournalname(Btree *p){
assert( p->pBt->pPager!=0 );
- assert( sqlite3BtreeMutexHeld(p->pBt->mutex) );
return sqlite3PagerJournalname(p->pBt->pPager);
}
@@ -6780,7 +6685,6 @@
** Return non-zero if a transaction is active.
*/
int sqlite3BtreeIsInTrans(Btree *p){
- assert( sqlite3BtreeMutexHeld(p->pBt->mutex) );
assert( sqlite3BtreeMutexHeld(p->pSqlite->mutex) );
return (p && (p->inTrans==TRANS_WRITE));
}
@@ -6798,7 +6702,6 @@
** Return non-zero if a read (or write) transaction is active.
*/
int sqlite3BtreeIsInReadTrans(Btree *p){
- assert( sqlite3BtreeMutexHeld(p->pBt->mutex) );
assert( sqlite3BtreeMutexHeld(p->pSqlite->mutex) );
return (p && (p->inTrans!=TRANS_NONE));
}
diff --git a/src/btree.h b/src/btree.h
index 60e0c88..2af90f7 100644
--- a/src/btree.h
+++ b/src/btree.h
@@ -13,7 +13,7 @@
** subsystem. See comments in the source code for a detailed description
** of what each interface routine does.
**
-** @(#) $Id: btree.h,v 1.86 2007/08/22 02:56:43 drh Exp $
+** @(#) $Id: btree.h,v 1.87 2007/08/28 02:27:52 drh Exp $
*/
#ifndef _BTREE_H_
#define _BTREE_H_
@@ -41,6 +41,18 @@
typedef struct Btree Btree;
typedef struct BtCursor BtCursor;
typedef struct BtShared BtShared;
+typedef struct BtreeMutexSet BtreeMutexSet;
+
+/*
+** This structure records all of the Btrees that need to hold
+** a mutex before we enter sqlite3VdbeExec(). The Btrees are
+** are placed in aBtree[] in order of aBtree[]->pBt. That way,
+** we can always lock and unlock them all quickly.
+*/
+struct BtreeMutexSet {
+ int nMutex;
+ Btree *aBtree[SQLITE_MAX_ATTACHED+1];
+};
int sqlite3BtreeOpen(
@@ -170,4 +182,16 @@
int sqlite3BtreePageDump(Btree*, int, int recursive);
#endif
+#if !defined(SQLITE_OMIT_SHARED_CACHE) && SQLITE_THREADSAFE
+ void sqlite3BtreeMutexSetEnter(BtreeMutexSet*);
+ void sqlite3BtreeMutexSetLeave(BtreeMutexSet*);
+ void sqlite3BtreeMutexSetInsert(BtreeMutexSet*, Btree*);
+#else
+# define sqlite3BtreeMutexSetEnter(X)
+# define sqlite3BtreeMutexSetLeave(X)
+# define sqlite3BtreeMutexSetInsert(X,Y)
+#endif
+
+
+
#endif /* _BTREE_H_ */
diff --git a/src/build.c b/src/build.c
index a68137d..a3cb280 100644
--- a/src/build.c
+++ b/src/build.c
@@ -22,7 +22,7 @@
** COMMIT
** ROLLBACK
**
-** $Id: build.c,v 1.438 2007/08/22 20:18:22 drh Exp $
+** $Id: build.c,v 1.439 2007/08/28 02:27:52 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
@@ -164,6 +164,7 @@
sqlite3VdbeJumpHere(v, pParse->cookieGoto-1);
for(iDb=0, mask=1; iDb<db->nDb; mask<<=1, iDb++){
if( (mask & pParse->cookieMask)==0 ) continue;
+ sqlite3VdbeAddMutexBtree(v, db->aDb[iDb].pBt);
sqlite3VdbeAddOp(v, OP_Transaction, iDb, (mask & pParse->writeMask)!=0);
sqlite3VdbeAddOp(v, OP_VerifyCookie, iDb, pParse->cookieValue[iDb]);
}
diff --git a/src/sqliteInt.h b/src/sqliteInt.h
index 1ebc238..bc0e8aa 100644
--- a/src/sqliteInt.h
+++ b/src/sqliteInt.h
@@ -11,7 +11,7 @@
*************************************************************************
** Internal interface definitions for SQLite.
**
-** @(#) $Id: sqliteInt.h,v 1.602 2007/08/27 23:26:59 drh Exp $
+** @(#) $Id: sqliteInt.h,v 1.603 2007/08/28 02:27:52 drh Exp $
*/
#ifndef _SQLITEINT_H_
#define _SQLITEINT_H_
@@ -233,8 +233,8 @@
** Defer sourcing vdbe.h and btree.h until after the "u8" and
** "BusyHandler typedefs.
*/
-#include "vdbe.h"
#include "btree.h"
+#include "vdbe.h"
#include "pager.h"
diff --git a/src/vdbe.c b/src/vdbe.c
index f23c05c..4519fc0 100644
--- a/src/vdbe.c
+++ b/src/vdbe.c
@@ -43,7 +43,7 @@
** in this file for details. If in doubt, do not deviate from existing
** commenting and indentation practices when changing or adding code.
**
-** $Id: vdbe.c,v 1.644 2007/08/21 19:33:57 drh Exp $
+** $Id: vdbe.c,v 1.645 2007/08/28 02:27:52 drh Exp $
*/
#include "sqliteInt.h"
#include <ctype.h>
@@ -465,6 +465,7 @@
if( p->magic!=VDBE_MAGIC_RUN ) return SQLITE_MISUSE;
assert( db->magic==SQLITE_MAGIC_BUSY );
pTos = p->pTos;
+ sqlite3BtreeMutexSetEnter(&p->mtxSet);
if( p->rc==SQLITE_NOMEM ){
/* This happens if a malloc() inside a call to sqlite3_column_text() or
** sqlite3_column_text16() failed. */
@@ -685,10 +686,11 @@
rc = sqlite3VdbeHalt(p);
assert( rc==SQLITE_BUSY || rc==SQLITE_OK );
if( rc==SQLITE_BUSY ){
- p->rc = SQLITE_BUSY;
- return SQLITE_BUSY;
+ p->rc = rc = SQLITE_BUSY;
+ }else{
+ rc = p->rc ? SQLITE_ERROR : SQLITE_DONE;
}
- return p->rc ? SQLITE_ERROR : SQLITE_DONE;
+ goto vdbe_return;
}
/* Opcode: Integer P1 * *
@@ -1003,7 +1005,8 @@
p->popStack = pOp->p1;
p->pc = pc + 1;
p->pTos = pTos;
- return SQLITE_ROW;
+ rc = SQLITE_ROW;
+ goto vdbe_return;
}
/* Opcode: Concat P1 P2 *
@@ -2462,15 +2465,16 @@
p->pTos = pTos;
p->pc = pc;
db->autoCommit = 1-i;
- p->rc = SQLITE_BUSY;
- return SQLITE_BUSY;
+ p->rc = rc = SQLITE_BUSY;
+ goto vdbe_return;
}
}
if( p->rc==SQLITE_OK ){
- return SQLITE_DONE;
+ rc = SQLITE_DONE;
}else{
- return SQLITE_ERROR;
+ rc = SQLITE_ERROR;
}
+ goto vdbe_return;
}else{
sqlite3SetString(&p->zErrMsg,
(!i)?"cannot start a transaction within a transaction":(
@@ -2513,9 +2517,9 @@
rc = sqlite3BtreeBeginTrans(pBt, pOp->p2);
if( rc==SQLITE_BUSY ){
p->pc = pc;
- p->rc = SQLITE_BUSY;
+ p->rc = rc = SQLITE_BUSY;
p->pTos = pTos;
- return SQLITE_BUSY;
+ goto vdbe_return;
}
if( rc!=SQLITE_OK && rc!=SQLITE_READONLY /* && rc!=SQLITE_BUSY */ ){
goto abort_due_to_error;
@@ -2755,9 +2759,9 @@
switch( rc ){
case SQLITE_BUSY: {
p->pc = pc;
- p->rc = SQLITE_BUSY;
+ p->rc = rc = SQLITE_BUSY;
p->pTos = &pTos[1 + (pOp->p2<=0)]; /* Operands must remain on stack */
- return SQLITE_BUSY;
+ goto vdbe_return;
}
case SQLITE_OK: {
int flags = sqlite3BtreeFlags(pCur->pCursor);
@@ -5193,6 +5197,12 @@
}
sqlite3VdbeHalt(p);
p->pTos = pTos;
+
+ /* This is the only way out of this procedure. We have to
+ ** release the mutexes on btrees that were acquired at the
+ ** top. */
+vdbe_return:
+ sqlite3BtreeMutexSetLeave(&p->mtxSet);
return rc;
/* Jump to here if a string or blob larger than SQLITE_MAX_LENGTH
diff --git a/src/vdbe.h b/src/vdbe.h
index f6b145b..0f3500a 100644
--- a/src/vdbe.h
+++ b/src/vdbe.h
@@ -15,7 +15,7 @@
** or VDBE. The VDBE implements an abstract machine that runs a
** simple program to access and modify the underlying database.
**
-** $Id: vdbe.h,v 1.110 2007/05/08 21:45:28 drh Exp $
+** $Id: vdbe.h,v 1.111 2007/08/28 02:27:52 drh Exp $
*/
#ifndef _SQLITE_VDBE_H_
#define _SQLITE_VDBE_H_
@@ -120,6 +120,7 @@
void sqlite3VdbeJumpHere(Vdbe*, int addr);
void sqlite3VdbeChangeToNoop(Vdbe*, int addr, int N);
void sqlite3VdbeChangeP3(Vdbe*, int addr, const char *zP1, int N);
+void sqlite3VdbeAddMutexBtree(Vdbe*, Btree*);
VdbeOp *sqlite3VdbeGetOp(Vdbe*, int);
int sqlite3VdbeMakeLabel(Vdbe*);
void sqlite3VdbeDelete(Vdbe*);
diff --git a/src/vdbeInt.h b/src/vdbeInt.h
index cef5cfc..78e76c2 100644
--- a/src/vdbeInt.h
+++ b/src/vdbeInt.h
@@ -317,7 +317,7 @@
unsigned uniqueCnt; /* Used by OP_MakeRecord when P2!=0 */
int errorAction; /* Recovery action to do in case of an error */
int inTempTrans; /* True if temp database is transactioned */
- int returnStack[100]; /* Return address stack for OP_Gosub & OP_Return */
+ int returnStack[25]; /* Return address stack for OP_Gosub & OP_Return */
int returnDepth; /* Next unused element in returnStack[] */
int nResColumn; /* Number of columns in one row of the result set */
char **azResColumn; /* Values for one row of result */
@@ -332,6 +332,7 @@
u8 inVtabMethod; /* See comments above */
int nChange; /* Number of db changes made since last reset */
i64 startTime; /* Time when query started - used for profiling */
+ BtreeMutexSet mtxSet; /* Set of Btree mutexes */
int nSql; /* Number of bytes in zSql */
char *zSql; /* Text of the SQL statement that generated this */
#ifdef SQLITE_DEBUG
diff --git a/src/vdbeaux.c b/src/vdbeaux.c
index 8bf6b83..80e14b1 100644
--- a/src/vdbeaux.c
+++ b/src/vdbeaux.c
@@ -658,6 +658,13 @@
}
#endif
+/*
+** Add a btree to the set of btrees that might need a mutex.
+*/
+void sqlite3VdbeAddMutexBtree(Vdbe *p, Btree *pBtree){
+ sqlite3BtreeMutexSetInsert(&p->mtxSet, pBtree);
+}
+
#if defined(VDBE_PROFILE) || defined(SQLITE_DEBUG)
/*