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.cpp 1282 2008-11-13 09:31:33Z LarsPson $

    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   /* In most cases, we should be able to acquire the lock we

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

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

    67   */

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

    69     p->locked = 1;

    70     return;

    71   }

    72 

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

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

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

    76   ** order.

    77   */

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

    79     assert( pLater->sharable );

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

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

    82     if( pLater->locked ){

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

    84       pLater->locked = 0;

    85     }

    86   }

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

    88   p->locked = 1;

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

    90     if( pLater->wantToLock ){

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

    92       pLater->locked = 1;

    93     }

    94   }

    95 }

    96 

    97 /*

    98 ** Exit the recursive mutex on a Btree.

    99 */

   100 void sqlite3BtreeLeave(Btree *p){

   101   if( p->sharable ){

   102     assert( p->wantToLock>0 );

   103     p->wantToLock--;

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

   105       assert( p->locked );

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

   107       p->locked = 0;

   108     }

   109   }

   110 }

   111 

   112 #ifndef NDEBUG

   113 /*

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

   115 **

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

   117 ** database connection mutex is held.

   118 **

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

   120 */

   121 int sqlite3BtreeHoldsMutex(Btree *p){

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

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

   124 }

   125 #endif

   126 

   127 

   128 #ifndef SQLITE_OMIT_INCRBLOB

   129 /*

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

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

   132 ** omitted if that module is not used.

   133 */

   134 void sqlite3BtreeEnterCursor(BtCursor *pCur){

   135   sqlite3BtreeEnter(pCur->pBtree);

   136 }

   137 void sqlite3BtreeLeaveCursor(BtCursor *pCur){

   138   sqlite3BtreeLeave(pCur->pBtree);

   139 }

   140 #endif /* SQLITE_OMIT_INCRBLOB */

   141 

   142 

   143 /*

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

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

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

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

   148 ** reset out from under us.

   149 **

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

   151 **

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

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

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

   155 ** at the same instant.

   156 */

   157 void sqlite3BtreeEnterAll(sqlite3 *db){

   158   int i;

   159   Btree *p, *pLater;

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

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

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

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

   164       p->wantToLock++;

   165       if( !p->locked ){

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

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

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

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

   170           if( pLater->locked ){

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

   172             pLater->locked = 0;

   173           }

   174         }

   175         while( p ){

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

   177           p->locked++;

   178           p = p->pNext;

   179         }

   180       }

   181     }

   182   }

   183 }

   184 void sqlite3BtreeLeaveAll(sqlite3 *db){

   185   int i;

   186   Btree *p;

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

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

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

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

   191       assert( p->wantToLock>0 );

   192       p->wantToLock--;

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

   194         assert( p->locked );

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

   196         p->locked = 0;

   197       }

   198     }

   199   }

   200 }

   201 

   202 #ifndef NDEBUG

   203 /*

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

   205 ** mutex and all required BtShared mutexes.

   206 **

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

   208 */

   209 int sqlite3BtreeHoldsAllMutexes(sqlite3 *db){

   210   int i;

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

   212     return 0;

   213   }

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

   215     Btree *p;

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

   217     if( p && p->sharable &&

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

   219       return 0;

   220     }

   221   }

   222   return 1;

   223 }

   224 #endif /* NDEBUG */

   225 

   226 /*

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

   228 ** Really only add the Btree if it can possibly be shared with

   229 ** another database connection.

   230 **

   231 ** The Btrees are kept in sorted order by pBtree->pBt.  That

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

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

   234 ** worrying about deadlock.

   235 **

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

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

   238 */

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

   240   int i, j;

   241   BtShared *pBt;

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

   243 #ifndef NDEBUG

   244   {

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

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

   247     }

   248   }

   249 #endif

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

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

   252   pBt = pBtree->pBt;

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

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

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

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

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

   258       }

   259       pArray->aBtree[i] = pBtree;

   260       pArray->nMutex++;

   261       return;

   262     }

   263   }

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

   265 }

   266 

   267 /*

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

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

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

   271 */

   272 void sqlite3BtreeMutexArrayEnter(BtreeMutexArray *pArray){

   273   int i;

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

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

   276     /* Some basic sanity checking */

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

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

   279 

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

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

   282 

   283     p->wantToLock++;

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

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

   286       p->locked = 1;

   287     }

   288   }

   289 }

   290 

   291 /*

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

   293 */

   294 void sqlite3BtreeMutexArrayLeave(BtreeMutexArray *pArray){

   295   int i;

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

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

   298     /* Some basic sanity checking */

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

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

   301     assert( p->wantToLock>0 );

   302 

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

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

   305 

   306     p->wantToLock--;

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

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

   309       p->locked = 0;

   310     }

   311   }

   312 }

   313 

   314 

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