sl@0: /*
sl@0: ** 2007 August 27
sl@0: **
sl@0: ** The author disclaims copyright to this source code.  In place of
sl@0: ** a legal notice, here is a blessing:
sl@0: **
sl@0: **    May you do good and not evil.
sl@0: **    May you find forgiveness for yourself and forgive others.
sl@0: **    May you share freely, never taking more than you give.
sl@0: **
sl@0: *************************************************************************
sl@0: **
sl@0: ** $Id: btmutex.c,v 1.10 2008/07/14 19:39:17 drh Exp $
sl@0: **
sl@0: ** This file contains code used to implement mutexes on Btree objects.
sl@0: ** This code really belongs in btree.c.  But btree.c is getting too
sl@0: ** big and we want to break it down some.  This packaged seemed like
sl@0: ** a good breakout.
sl@0: */
sl@0: #include "btreeInt.h"
sl@0: #if SQLITE_THREADSAFE && !defined(SQLITE_OMIT_SHARED_CACHE)
sl@0: 
sl@0: 
sl@0: /*
sl@0: ** Enter a mutex on the given BTree object.
sl@0: **
sl@0: ** If the object is not sharable, then no mutex is ever required
sl@0: ** and this routine is a no-op.  The underlying mutex is non-recursive.
sl@0: ** But we keep a reference count in Btree.wantToLock so the behavior
sl@0: ** of this interface is recursive.
sl@0: **
sl@0: ** To avoid deadlocks, multiple Btrees are locked in the same order
sl@0: ** by all database connections.  The p->pNext is a list of other
sl@0: ** Btrees belonging to the same database connection as the p Btree
sl@0: ** which need to be locked after p.  If we cannot get a lock on
sl@0: ** p, then first unlock all of the others on p->pNext, then wait
sl@0: ** for the lock to become available on p, then relock all of the
sl@0: ** subsequent Btrees that desire a lock.
sl@0: */
sl@0: void sqlite3BtreeEnter(Btree *p){
sl@0:   Btree *pLater;
sl@0: 
sl@0:   /* Some basic sanity checking on the Btree.  The list of Btrees
sl@0:   ** connected by pNext and pPrev should be in sorted order by
sl@0:   ** Btree.pBt value. All elements of the list should belong to
sl@0:   ** the same connection. Only shared Btrees are on the list. */
sl@0:   assert( p->pNext==0 || p->pNext->pBt>p->pBt );
sl@0:   assert( p->pPrev==0 || p->pPrev->pBt<p->pBt );
sl@0:   assert( p->pNext==0 || p->pNext->db==p->db );
sl@0:   assert( p->pPrev==0 || p->pPrev->db==p->db );
sl@0:   assert( p->sharable || (p->pNext==0 && p->pPrev==0) );
sl@0: 
sl@0:   /* Check for locking consistency */
sl@0:   assert( !p->locked || p->wantToLock>0 );
sl@0:   assert( p->sharable || p->wantToLock==0 );
sl@0: 
sl@0:   /* We should already hold a lock on the database connection */
sl@0:   assert( sqlite3_mutex_held(p->db->mutex) );
sl@0: 
sl@0:   if( !p->sharable ) return;
sl@0:   p->wantToLock++;
sl@0:   if( p->locked ) return;
sl@0: 
sl@0: #ifndef SQLITE_MUTEX_NOOP
sl@0:   /* In most cases, we should be able to acquire the lock we
sl@0:   ** want without having to go throught the ascending lock
sl@0:   ** procedure that follows.  Just be sure not to block.
sl@0:   */
sl@0:   if( sqlite3_mutex_try(p->pBt->mutex)==SQLITE_OK ){
sl@0:     p->locked = 1;
sl@0:     return;
sl@0:   }
sl@0: 
sl@0:   /* To avoid deadlock, first release all locks with a larger
sl@0:   ** BtShared address.  Then acquire our lock.  Then reacquire
sl@0:   ** the other BtShared locks that we used to hold in ascending
sl@0:   ** order.
sl@0:   */
sl@0:   for(pLater=p->pNext; pLater; pLater=pLater->pNext){
sl@0:     assert( pLater->sharable );
sl@0:     assert( pLater->pNext==0 || pLater->pNext->pBt>pLater->pBt );
sl@0:     assert( !pLater->locked || pLater->wantToLock>0 );
sl@0:     if( pLater->locked ){
sl@0:       sqlite3_mutex_leave(pLater->pBt->mutex);
sl@0:       pLater->locked = 0;
sl@0:     }
sl@0:   }
sl@0:   sqlite3_mutex_enter(p->pBt->mutex);
sl@0:   p->locked = 1;
sl@0:   for(pLater=p->pNext; pLater; pLater=pLater->pNext){
sl@0:     if( pLater->wantToLock ){
sl@0:       sqlite3_mutex_enter(pLater->pBt->mutex);
sl@0:       pLater->locked = 1;
sl@0:     }
sl@0:   }
sl@0: #endif /* SQLITE_MUTEX_NOOP */
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Exit the recursive mutex on a Btree.
sl@0: */
sl@0: void sqlite3BtreeLeave(Btree *p){
sl@0:   if( p->sharable ){
sl@0:     assert( p->wantToLock>0 );
sl@0:     p->wantToLock--;
sl@0:     if( p->wantToLock==0 ){
sl@0:       assert( p->locked );
sl@0:       sqlite3_mutex_leave(p->pBt->mutex);
sl@0:       p->locked = 0;
sl@0:     }
sl@0:   }
sl@0: }
sl@0: 
sl@0: #ifndef NDEBUG
sl@0: /*
sl@0: ** Return true if the BtShared mutex is held on the btree.  
sl@0: **
sl@0: ** This routine makes no determination one why or another if the
sl@0: ** database connection mutex is held.
sl@0: **
sl@0: ** This routine is used only from within assert() statements.
sl@0: */
sl@0: int sqlite3BtreeHoldsMutex(Btree *p){
sl@0:   return (p->sharable==0 ||
sl@0:              (p->locked && p->wantToLock && sqlite3_mutex_held(p->pBt->mutex)));
sl@0: }
sl@0: #endif
sl@0: 
sl@0: 
sl@0: #ifndef SQLITE_OMIT_INCRBLOB
sl@0: /*
sl@0: ** Enter and leave a mutex on a Btree given a cursor owned by that
sl@0: ** Btree.  These entry points are used by incremental I/O and can be
sl@0: ** omitted if that module is not used.
sl@0: */
sl@0: void sqlite3BtreeEnterCursor(BtCursor *pCur){
sl@0:   sqlite3BtreeEnter(pCur->pBtree);
sl@0: }
sl@0: void sqlite3BtreeLeaveCursor(BtCursor *pCur){
sl@0:   sqlite3BtreeLeave(pCur->pBtree);
sl@0: }
sl@0: #endif /* SQLITE_OMIT_INCRBLOB */
sl@0: 
sl@0: 
sl@0: /*
sl@0: ** Enter the mutex on every Btree associated with a database
sl@0: ** connection.  This is needed (for example) prior to parsing
sl@0: ** a statement since we will be comparing table and column names
sl@0: ** against all schemas and we do not want those schemas being
sl@0: ** reset out from under us.
sl@0: **
sl@0: ** There is a corresponding leave-all procedures.
sl@0: **
sl@0: ** Enter the mutexes in accending order by BtShared pointer address
sl@0: ** to avoid the possibility of deadlock when two threads with
sl@0: ** two or more btrees in common both try to lock all their btrees
sl@0: ** at the same instant.
sl@0: */
sl@0: void sqlite3BtreeEnterAll(sqlite3 *db){
sl@0:   int i;
sl@0:   Btree *p, *pLater;
sl@0:   assert( sqlite3_mutex_held(db->mutex) );
sl@0:   for(i=0; i<db->nDb; i++){
sl@0:     p = db->aDb[i].pBt;
sl@0:     if( p && p->sharable ){
sl@0:       p->wantToLock++;
sl@0:       if( !p->locked ){
sl@0:         assert( p->wantToLock==1 );
sl@0:         while( p->pPrev ) p = p->pPrev;
sl@0:         while( p->locked && p->pNext ) p = p->pNext;
sl@0:         for(pLater = p->pNext; pLater; pLater=pLater->pNext){
sl@0:           if( pLater->locked ){
sl@0:             sqlite3_mutex_leave(pLater->pBt->mutex);
sl@0:             pLater->locked = 0;
sl@0:           }
sl@0:         }
sl@0:         while( p ){
sl@0:           sqlite3_mutex_enter(p->pBt->mutex);
sl@0:           p->locked++;
sl@0:           p = p->pNext;
sl@0:         }
sl@0:       }
sl@0:     }
sl@0:   }
sl@0: }
sl@0: void sqlite3BtreeLeaveAll(sqlite3 *db){
sl@0:   int i;
sl@0:   Btree *p;
sl@0:   assert( sqlite3_mutex_held(db->mutex) );
sl@0:   for(i=0; i<db->nDb; i++){
sl@0:     p = db->aDb[i].pBt;
sl@0:     if( p && p->sharable ){
sl@0:       assert( p->wantToLock>0 );
sl@0:       p->wantToLock--;
sl@0:       if( p->wantToLock==0 ){
sl@0:         assert( p->locked );
sl@0:         sqlite3_mutex_leave(p->pBt->mutex);
sl@0:         p->locked = 0;
sl@0:       }
sl@0:     }
sl@0:   }
sl@0: }
sl@0: 
sl@0: #ifndef NDEBUG
sl@0: /*
sl@0: ** Return true if the current thread holds the database connection
sl@0: ** mutex and all required BtShared mutexes.
sl@0: **
sl@0: ** This routine is used inside assert() statements only.
sl@0: */
sl@0: int sqlite3BtreeHoldsAllMutexes(sqlite3 *db){
sl@0:   int i;
sl@0:   if( !sqlite3_mutex_held(db->mutex) ){
sl@0:     return 0;
sl@0:   }
sl@0:   for(i=0; i<db->nDb; i++){
sl@0:     Btree *p;
sl@0:     p = db->aDb[i].pBt;
sl@0:     if( p && p->sharable &&
sl@0:          (p->wantToLock==0 || !sqlite3_mutex_held(p->pBt->mutex)) ){
sl@0:       return 0;
sl@0:     }
sl@0:   }
sl@0:   return 1;
sl@0: }
sl@0: #endif /* NDEBUG */
sl@0: 
sl@0: /*
sl@0: ** Add a new Btree pointer to a BtreeMutexArray. 
sl@0: ** if the pointer can possibly be shared with
sl@0: ** another database connection.
sl@0: **
sl@0: ** The pointers are kept in sorted order by pBtree->pBt.  That
sl@0: ** way when we go to enter all the mutexes, we can enter them
sl@0: ** in order without every having to backup and retry and without
sl@0: ** worrying about deadlock.
sl@0: **
sl@0: ** The number of shared btrees will always be small (usually 0 or 1)
sl@0: ** so an insertion sort is an adequate algorithm here.
sl@0: */
sl@0: void sqlite3BtreeMutexArrayInsert(BtreeMutexArray *pArray, Btree *pBtree){
sl@0:   int i, j;
sl@0:   BtShared *pBt;
sl@0:   if( pBtree==0 || pBtree->sharable==0 ) return;
sl@0: #ifndef NDEBUG
sl@0:   {
sl@0:     for(i=0; i<pArray->nMutex; i++){
sl@0:       assert( pArray->aBtree[i]!=pBtree );
sl@0:     }
sl@0:   }
sl@0: #endif
sl@0:   assert( pArray->nMutex>=0 );
sl@0:   assert( pArray->nMutex<sizeof(pArray->aBtree)/sizeof(pArray->aBtree[0])-1 );
sl@0:   pBt = pBtree->pBt;
sl@0:   for(i=0; i<pArray->nMutex; i++){
sl@0:     assert( pArray->aBtree[i]!=pBtree );
sl@0:     if( pArray->aBtree[i]->pBt>pBt ){
sl@0:       for(j=pArray->nMutex; j>i; j--){
sl@0:         pArray->aBtree[j] = pArray->aBtree[j-1];
sl@0:       }
sl@0:       pArray->aBtree[i] = pBtree;
sl@0:       pArray->nMutex++;
sl@0:       return;
sl@0:     }
sl@0:   }
sl@0:   pArray->aBtree[pArray->nMutex++] = pBtree;
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Enter the mutex of every btree in the array.  This routine is
sl@0: ** called at the beginning of sqlite3VdbeExec().  The mutexes are
sl@0: ** exited at the end of the same function.
sl@0: */
sl@0: void sqlite3BtreeMutexArrayEnter(BtreeMutexArray *pArray){
sl@0:   int i;
sl@0:   for(i=0; i<pArray->nMutex; i++){
sl@0:     Btree *p = pArray->aBtree[i];
sl@0:     /* Some basic sanity checking */
sl@0:     assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );
sl@0:     assert( !p->locked || p->wantToLock>0 );
sl@0: 
sl@0:     /* We should already hold a lock on the database connection */
sl@0:     assert( sqlite3_mutex_held(p->db->mutex) );
sl@0: 
sl@0:     p->wantToLock++;
sl@0:     if( !p->locked && p->sharable ){
sl@0:       sqlite3_mutex_enter(p->pBt->mutex);
sl@0:       p->locked = 1;
sl@0:     }
sl@0:   }
sl@0: }
sl@0: 
sl@0: /*
sl@0: ** Leave the mutex of every btree in the group.
sl@0: */
sl@0: void sqlite3BtreeMutexArrayLeave(BtreeMutexArray *pArray){
sl@0:   int i;
sl@0:   for(i=0; i<pArray->nMutex; i++){
sl@0:     Btree *p = pArray->aBtree[i];
sl@0:     /* Some basic sanity checking */
sl@0:     assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );
sl@0:     assert( p->locked || !p->sharable );
sl@0:     assert( p->wantToLock>0 );
sl@0: 
sl@0:     /* We should already hold a lock on the database connection */
sl@0:     assert( sqlite3_mutex_held(p->db->mutex) );
sl@0: 
sl@0:     p->wantToLock--;
sl@0:     if( p->wantToLock==0 && p->locked ){
sl@0:       sqlite3_mutex_leave(p->pBt->mutex);
sl@0:       p->locked = 0;
sl@0:     }
sl@0:   }
sl@0: }
sl@0: 
sl@0: 
sl@0: #endif  /* SQLITE_THREADSAFE && !SQLITE_OMIT_SHARED_CACHE */