engine/sqlite/src/btmutex.cpp
changeset 71 fbd95db6a4e1
parent 69 4a65cc85c4f3
child 72 2e267e7da513
equal deleted inserted replaced
69:4a65cc85c4f3 71:fbd95db6a4e1
     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 */