/*

 ** 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$

 **

 ** 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( sqlite3_mutex_held(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);

   p->locked = 1;

   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;

     }

   }

 }

 #ifndef NDEBUG

 /*

 ** Return true if the BtShared mutex is held on the btree.  

 **

 ** This routine makes no determination one why or another if the

 ** database connection mutex is held.

 **

 ** This routine is used only from within assert() statements.

 */

 int sqlite3BtreeHoldsMutex(Btree *p){

   return (p->sharable==0 ||

              (p->locked && p->wantToLock && sqlite3_mutex_held(p->pBt->mutex)));

 }

 #endif

 #ifndef SQLITE_OMIT_INCRBLOB

 /*

 ** Enter and leave a mutex on a Btree given a cursor owned by that

 ** Btree.  These entry points are used by incremental I/O and can be

 ** omitted if that module is not used.

 */

 void sqlite3BtreeEnterCursor(BtCursor *pCur){

   sqlite3BtreeEnter(pCur->pBtree);

 }

 void sqlite3BtreeLeaveCursor(BtCursor *pCur){

   sqlite3BtreeLeave(pCur->pBtree);

 }

 #endif /* SQLITE_OMIT_INCRBLOB */

 /*

 ** Enter the mutex on every Btree associated with a database

 ** connection.  This is needed (for example) prior to parsing

 ** a statement since we will be comparing table and column names

 ** against all schemas and we do not want those schemas being

 ** reset out from under us.

 **

 ** There is a corresponding leave-all procedures.

 **

 ** Enter the mutexes in accending order by BtShared pointer address

 ** to avoid the possibility of deadlock when two threads with

 ** two or more btrees in common both try to lock all their btrees

 ** at the same instant.

 */

 void sqlite3BtreeEnterAll(sqlite3 *db){

   int i;

   Btree *p, *pLater;

   assert( sqlite3_mutex_held(db->mutex) );

   for(i=0; i<db->nDb; i++){

     p = db->aDb[i].pBt;

     if( p && p->sharable ){

       p->wantToLock++;

       if( !p->locked ){

         assert( p->wantToLock==1 );

         while( p->pPrev ) p = p->pPrev;

         while( p->locked && p->pNext ) p = p->pNext;

         for(pLater = p->pNext; pLater; pLater=pLater->pNext){

           if( pLater->locked ){

             sqlite3_mutex_leave(pLater->pBt->mutex);

             pLater->locked = 0;

           }

         }

         while( p ){

           sqlite3_mutex_enter(p->pBt->mutex);

           p->locked++;

           p = p->pNext;

         }

       }

     }

   }

 }

 void sqlite3BtreeLeaveAll(sqlite3 *db){

   int i;

   Btree *p;

   assert( sqlite3_mutex_held(db->mutex) );

   for(i=0; i<db->nDb; i++){

     p = db->aDb[i].pBt;

     if( p && p->sharable ){

       assert( p->wantToLock>0 );

       p->wantToLock--;

       if( p->wantToLock==0 ){

         assert( p->locked );

         sqlite3_mutex_leave(p->pBt->mutex);

         p->locked = 0;

       }

     }

   }

 }

 #ifndef NDEBUG

 /*

 ** Return true if the current thread holds the database connection

 ** mutex and all required BtShared mutexes.

 **

 ** This routine is used inside assert() statements only.

 */

 int sqlite3BtreeHoldsAllMutexes(sqlite3 *db){

   int i;

   if( !sqlite3_mutex_held(db->mutex) ){

     return 0;

   }

   for(i=0; i<db->nDb; i++){

     Btree *p;

     p = db->aDb[i].pBt;

     if( p && p->sharable &&

          (p->wantToLock==0 || !sqlite3_mutex_held(p->pBt->mutex)) ){

       return 0;

     }

   }

   return 1;

 }

 #endif /* NDEBUG */

 /*

 ** Potentially dd a new Btree pointer to a BtreeMutexArray.

 ** 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 sqlite3BtreeMutexArrayInsert(BtreeMutexArray *pArray, Btree *pBtree){

   int i, j;

   BtShared *pBt;

   if( pBtree==0 || pBtree->sharable==0 ) return;

 #ifndef NDEBUG

   {

     for(i=0; i<pArray->nMutex; i++){

       assert( pArray->aBtree[i]!=pBtree );

     }

   }

 #endif

   assert( pArray->nMutex>=0 );

   assert( pArray->nMutex<sizeof(pArray->aBtree)/sizeof(pArray->aBtree[0])-1 );

   pBt = pBtree->pBt;

   for(i=0; i<pArray->nMutex; i++){

     assert( pArray->aBtree[i]!=pBtree );

     if( pArray->aBtree[i]->pBt>pBt ){

       for(j=pArray->nMutex; j>i; j--){

         pArray->aBtree[j] = pArray->aBtree[j-1];

       }

       pArray->aBtree[i] = pBtree;

       pArray->nMutex++;

       return;

     }

   }

   pArray->aBtree[pArray->nMutex++] = pBtree;

 }

 /*

 ** Enter the mutex of every btree in the array.  This routine is

 ** called at the beginning of sqlite3VdbeExec().  The mutexes are

 ** exited at the end of the same function.

 */

 void sqlite3BtreeMutexArrayEnter(BtreeMutexArray *pArray){

   int i;

   for(i=0; i<pArray->nMutex; i++){

     Btree *p = pArray->aBtree[i];

     /* Some basic sanity checking */

     assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );

     assert( !p->locked || p->wantToLock>0 );

     /* We should already hold a lock on the database connection */

     assert( sqlite3_mutex_held(p->pSqlite->mutex) );

     p->wantToLock++;

     if( !p->locked && p->sharable ){

       sqlite3_mutex_enter(p->pBt->mutex);

       p->locked = 1;

     }

   }

 }

 /*

 ** Leave the mutex of every btree in the group.

 */

 void sqlite3BtreeMutexArrayLeave(BtreeMutexArray *pArray){

   int i;

   for(i=0; i<pArray->nMutex; i++){

     Btree *p = pArray->aBtree[i];

     /* Some basic sanity checking */

     assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );

     assert( p->locked || !p->sharable );

     assert( p->wantToLock>0 );

     /* We should already hold a lock on the database connection */

     assert( sqlite3_mutex_held(p->pSqlite->mutex) );

     p->wantToLock--;

     if( p->wantToLock==0 && p->locked ){

       sqlite3_mutex_leave(p->pBt->mutex);

       p->locked = 0;

     }

   }

 }

 #endif  /* SQLITE_THREADSAFE && !SQLITE_OMIT_SHARED_CACHE */