1 /*

     2 ** 2007 August 27

     3 **

     4 ** The author disclaims copyright to this source code.  In place of

     5 ** a legal notice, here is a blessing:

     6 **

     7 **    May you do good and not evil.

     8 **    May you find forgiveness for yourself and forgive others.

     9 **    May you share freely, never taking more than you give.

    10 **

    11 *************************************************************************

    12 **

    13 ** $Id: btmutex.c,v 1.10 2008/07/14 19:39:17 drh Exp $

    14 **

    15 ** This file contains code used to implement mutexes on Btree objects.

    16 ** This code really belongs in btree.c.  But btree.c is getting too

    17 ** big and we want to break it down some.  This packaged seemed like

    18 ** a good breakout.

    19 */

    20 #include "btreeInt.h"

    21 #if SQLITE_THREADSAFE && !defined(SQLITE_OMIT_SHARED_CACHE)

    22 

    23 

    24 /*

    25 ** Enter a mutex on the given BTree object.

    26 **

    27 ** If the object is not sharable, then no mutex is ever required

    28 ** and this routine is a no-op.  The underlying mutex is non-recursive.

    29 ** But we keep a reference count in Btree.wantToLock so the behavior

    30 ** of this interface is recursive.

    31 **

    32 ** To avoid deadlocks, multiple Btrees are locked in the same order

    33 ** by all database connections.  The p->pNext is a list of other

    34 ** Btrees belonging to the same database connection as the p Btree

    35 ** which need to be locked after p.  If we cannot get a lock on

    36 ** p, then first unlock all of the others on p->pNext, then wait

    37 ** for the lock to become available on p, then relock all of the

    38 ** subsequent Btrees that desire a lock.

    39 */

    40 void sqlite3BtreeEnter(Btree *p){

    41   Btree *pLater;

    42 

    43   /* Some basic sanity checking on the Btree.  The list of Btrees

    44   ** connected by pNext and pPrev should be in sorted order by

    45   ** Btree.pBt value. All elements of the list should belong to

    46   ** the same connection. Only shared Btrees are on the list. */

    47   assert( p->pNext==0 || p->pNext->pBt>p->pBt );

    48   assert( p->pPrev==0 || p->pPrev->pBt<p->pBt );

    49   assert( p->pNext==0 || p->pNext->db==p->db );

    50   assert( p->pPrev==0 || p->pPrev->db==p->db );

    51   assert( p->sharable || (p->pNext==0 && p->pPrev==0) );

    52 

    53   /* Check for locking consistency */

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

    55   assert( p->sharable || p->wantToLock==0 );

    56 

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

    58   assert( sqlite3_mutex_held(p->db->mutex) );

    59 

    60   if( !p->sharable ) return;

    61   p->wantToLock++;

    62   if( p->locked ) return;

    63 

    64 #ifndef SQLITE_MUTEX_NOOP

    65   /* In most cases, we should be able to acquire the lock we

    66   ** want without having to go throught the ascending lock

    67   ** procedure that follows.  Just be sure not to block.

    68   */

    69   if( sqlite3_mutex_try(p->pBt->mutex)==SQLITE_OK ){

    70     p->locked = 1;

    71     return;

    72   }

    73 

    74   /* To avoid deadlock, first release all locks with a larger

    75   ** BtShared address.  Then acquire our lock.  Then reacquire

    76   ** the other BtShared locks that we used to hold in ascending

    77   ** order.

    78   */

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

    80     assert( pLater->sharable );

    81     assert( pLater->pNext==0 || pLater->pNext->pBt>pLater->pBt );

    82     assert( !pLater->locked || pLater->wantToLock>0 );

    83     if( pLater->locked ){

    84       sqlite3_mutex_leave(pLater->pBt->mutex);

    85       pLater->locked = 0;

    86     }

    87   }

    88   sqlite3_mutex_enter(p->pBt->mutex);

    89   p->locked = 1;

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

    91     if( pLater->wantToLock ){

    92       sqlite3_mutex_enter(pLater->pBt->mutex);

    93       pLater->locked = 1;

    94     }

    95   }

    96 #endif /* SQLITE_MUTEX_NOOP */

    97 }

    98 

    99 /*

   100 ** Exit the recursive mutex on a Btree.

   101 */

   102 void sqlite3BtreeLeave(Btree *p){

   103   if( p->sharable ){

   104     assert( p->wantToLock>0 );

   105     p->wantToLock--;

   106     if( p->wantToLock==0 ){

   107       assert( p->locked );

   108       sqlite3_mutex_leave(p->pBt->mutex);

   109       p->locked = 0;

   110     }

   111   }

   112 }

   113 

   114 #ifndef NDEBUG

   115 /*

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

   117 **

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

   119 ** database connection mutex is held.

   120 **

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

   122 */

   123 int sqlite3BtreeHoldsMutex(Btree *p){

   124   return (p->sharable==0 ||

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

   126 }

   127 #endif

   128 

   129 

   130 #ifndef SQLITE_OMIT_INCRBLOB

   131 /*

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

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

   134 ** omitted if that module is not used.

   135 */

   136 void sqlite3BtreeEnterCursor(BtCursor *pCur){

   137   sqlite3BtreeEnter(pCur->pBtree);

   138 }

   139 void sqlite3BtreeLeaveCursor(BtCursor *pCur){

   140   sqlite3BtreeLeave(pCur->pBtree);

   141 }

   142 #endif /* SQLITE_OMIT_INCRBLOB */

   143 

   144 

   145 /*

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

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

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

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

   150 ** reset out from under us.

   151 **

   152 ** There is a corresponding leave-all procedures.

   153 **

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

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

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

   157 ** at the same instant.

   158 */

   159 void sqlite3BtreeEnterAll(sqlite3 *db){

   160   int i;

   161   Btree *p, *pLater;

   162   assert( sqlite3_mutex_held(db->mutex) );

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

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

   165     if( p && p->sharable ){

   166       p->wantToLock++;

   167       if( !p->locked ){

   168         assert( p->wantToLock==1 );

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

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

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

   172           if( pLater->locked ){

   173             sqlite3_mutex_leave(pLater->pBt->mutex);

   174             pLater->locked = 0;

   175           }

   176         }

   177         while( p ){

   178           sqlite3_mutex_enter(p->pBt->mutex);

   179           p->locked++;

   180           p = p->pNext;

   181         }

   182       }

   183     }

   184   }

   185 }

   186 void sqlite3BtreeLeaveAll(sqlite3 *db){

   187   int i;

   188   Btree *p;

   189   assert( sqlite3_mutex_held(db->mutex) );

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

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

   192     if( p && p->sharable ){

   193       assert( p->wantToLock>0 );

   194       p->wantToLock--;

   195       if( p->wantToLock==0 ){

   196         assert( p->locked );

   197         sqlite3_mutex_leave(p->pBt->mutex);

   198         p->locked = 0;

   199       }

   200     }

   201   }

   202 }

   203 

   204 #ifndef NDEBUG

   205 /*

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

   207 ** mutex and all required BtShared mutexes.

   208 **

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

   210 */

   211 int sqlite3BtreeHoldsAllMutexes(sqlite3 *db){

   212   int i;

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

   214     return 0;

   215   }

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

   217     Btree *p;

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

   219     if( p && p->sharable &&

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

   221       return 0;

   222     }

   223   }

   224   return 1;

   225 }

   226 #endif /* NDEBUG */

   227 

   228 /*

   229 ** Add a new Btree pointer to a BtreeMutexArray. 

   230 ** if the pointer can possibly be shared with

   231 ** another database connection.

   232 **

   233 ** The pointers are kept in sorted order by pBtree->pBt.  That

   234 ** way when we go to enter all the mutexes, we can enter them

   235 ** in order without every having to backup and retry and without

   236 ** worrying about deadlock.

   237 **

   238 ** The number of shared btrees will always be small (usually 0 or 1)

   239 ** so an insertion sort is an adequate algorithm here.

   240 */

   241 void sqlite3BtreeMutexArrayInsert(BtreeMutexArray *pArray, Btree *pBtree){

   242   int i, j;

   243   BtShared *pBt;

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

   245 #ifndef NDEBUG

   246   {

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

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

   249     }

   250   }

   251 #endif

   252   assert( pArray->nMutex>=0 );

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

   254   pBt = pBtree->pBt;

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

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

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

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

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

   260       }

   261       pArray->aBtree[i] = pBtree;

   262       pArray->nMutex++;

   263       return;

   264     }

   265   }

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

   267 }

   268 

   269 /*

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

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

   272 ** exited at the end of the same function.

   273 */

   274 void sqlite3BtreeMutexArrayEnter(BtreeMutexArray *pArray){

   275   int i;

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

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

   278     /* Some basic sanity checking */

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

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

   281 

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

   283     assert( sqlite3_mutex_held(p->db->mutex) );

   284 

   285     p->wantToLock++;

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

   287       sqlite3_mutex_enter(p->pBt->mutex);

   288       p->locked = 1;

   289     }

   290   }

   291 }

   292 

   293 /*

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

   295 */

   296 void sqlite3BtreeMutexArrayLeave(BtreeMutexArray *pArray){

   297   int i;

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

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

   300     /* Some basic sanity checking */

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

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

   303     assert( p->wantToLock>0 );

   304 

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

   306     assert( sqlite3_mutex_held(p->db->mutex) );

   307 

   308     p->wantToLock--;

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

   310       sqlite3_mutex_leave(p->pBt->mutex);

   311       p->locked = 0;

   312     }

   313   }

   314 }

   315 

   316 

   317 #endif  /* SQLITE_THREADSAFE && !SQLITE_OMIT_SHARED_CACHE */