1.1 --- /dev/null	Thu Jan 01 00:00:00 1970 +0000
     1.2 +++ b/extensions/sqlite/sqlite-source/btmutex.c	Sun Oct 28 05:49:37 2007 +0000
     1.3 @@ -0,0 +1,315 @@
     1.4 +/*
     1.5 +** 2007 August 27
     1.6 +**
     1.7 +** The author disclaims copyright to this source code.  In place of
     1.8 +** a legal notice, here is a blessing:
     1.9 +**
    1.10 +**    May you do good and not evil.
    1.11 +**    May you find forgiveness for yourself and forgive others.
    1.12 +**    May you share freely, never taking more than you give.
    1.13 +**
    1.14 +*************************************************************************
    1.15 +**
    1.16 +** $Id$
    1.17 +**
    1.18 +** This file contains code used to implement mutexes on Btree objects.
    1.19 +** This code really belongs in btree.c.  But btree.c is getting too
    1.20 +** big and we want to break it down some.  This packaged seemed like
    1.21 +** a good breakout.
    1.22 +*/
    1.23 +#include "btreeInt.h"
    1.24 +#if SQLITE_THREADSAFE && !defined(SQLITE_OMIT_SHARED_CACHE)
    1.25 +
    1.26 +
    1.27 +/*
    1.28 +** Enter a mutex on the given BTree object.
    1.29 +**
    1.30 +** If the object is not sharable, then no mutex is ever required
    1.31 +** and this routine is a no-op.  The underlying mutex is non-recursive.
    1.32 +** But we keep a reference count in Btree.wantToLock so the behavior
    1.33 +** of this interface is recursive.
    1.34 +**
    1.35 +** To avoid deadlocks, multiple Btrees are locked in the same order
    1.36 +** by all database connections.  The p->pNext is a list of other
    1.37 +** Btrees belonging to the same database connection as the p Btree
    1.38 +** which need to be locked after p.  If we cannot get a lock on
    1.39 +** p, then first unlock all of the others on p->pNext, then wait
    1.40 +** for the lock to become available on p, then relock all of the
    1.41 +** subsequent Btrees that desire a lock.
    1.42 +*/
    1.43 +void sqlite3BtreeEnter(Btree *p){
    1.44 +  Btree *pLater;
    1.45 +
    1.46 +  /* Some basic sanity checking on the Btree.  The list of Btrees
    1.47 +  ** connected by pNext and pPrev should be in sorted order by
    1.48 +  ** Btree.pBt value. All elements of the list should belong to
    1.49 +  ** the same connection. Only shared Btrees are on the list. */
    1.50 +  assert( p->pNext==0 || p->pNext->pBt>p->pBt );
    1.51 +  assert( p->pPrev==0 || p->pPrev->pBt<p->pBt );
    1.52 +  assert( p->pNext==0 || p->pNext->pSqlite==p->pSqlite );
    1.53 +  assert( p->pPrev==0 || p->pPrev->pSqlite==p->pSqlite );
    1.54 +  assert( p->sharable || (p->pNext==0 && p->pPrev==0) );
    1.55 +
    1.56 +  /* Check for locking consistency */
    1.57 +  assert( !p->locked || p->wantToLock>0 );
    1.58 +  assert( p->sharable || p->wantToLock==0 );
    1.59 +
    1.60 +  /* We should already hold a lock on the database connection */
    1.61 +  assert( sqlite3_mutex_held(p->pSqlite->mutex) );
    1.62 +
    1.63 +  if( !p->sharable ) return;
    1.64 +  p->wantToLock++;
    1.65 +  if( p->locked ) return;
    1.66 +
    1.67 +  /* In most cases, we should be able to acquire the lock we
    1.68 +  ** want without having to go throught the ascending lock
    1.69 +  ** procedure that follows.  Just be sure not to block.
    1.70 +  */
    1.71 +  if( sqlite3_mutex_try(p->pBt->mutex)==SQLITE_OK ){
    1.72 +    p->locked = 1;
    1.73 +    return;
    1.74 +  }
    1.75 +
    1.76 +  /* To avoid deadlock, first release all locks with a larger
    1.77 +  ** BtShared address.  Then acquire our lock.  Then reacquire
    1.78 +  ** the other BtShared locks that we used to hold in ascending
    1.79 +  ** order.
    1.80 +  */
    1.81 +  for(pLater=p->pNext; pLater; pLater=pLater->pNext){
    1.82 +    assert( pLater->sharable );
    1.83 +    assert( pLater->pNext==0 || pLater->pNext->pBt>pLater->pBt );
    1.84 +    assert( !pLater->locked || pLater->wantToLock>0 );
    1.85 +    if( pLater->locked ){
    1.86 +      sqlite3_mutex_leave(pLater->pBt->mutex);
    1.87 +      pLater->locked = 0;
    1.88 +    }
    1.89 +  }
    1.90 +  sqlite3_mutex_enter(p->pBt->mutex);
    1.91 +  p->locked = 1;
    1.92 +  for(pLater=p->pNext; pLater; pLater=pLater->pNext){
    1.93 +    if( pLater->wantToLock ){
    1.94 +      sqlite3_mutex_enter(pLater->pBt->mutex);
    1.95 +      pLater->locked = 1;
    1.96 +    }
    1.97 +  }
    1.98 +}
    1.99 +
   1.100 +/*
   1.101 +** Exit the recursive mutex on a Btree.
   1.102 +*/
   1.103 +void sqlite3BtreeLeave(Btree *p){
   1.104 +  if( p->sharable ){
   1.105 +    assert( p->wantToLock>0 );
   1.106 +    p->wantToLock--;
   1.107 +    if( p->wantToLock==0 ){
   1.108 +      assert( p->locked );
   1.109 +      sqlite3_mutex_leave(p->pBt->mutex);
   1.110 +      p->locked = 0;
   1.111 +    }
   1.112 +  }
   1.113 +}
   1.114 +
   1.115 +#ifndef NDEBUG
   1.116 +/*
   1.117 +** Return true if the BtShared mutex is held on the btree.  
   1.118 +**
   1.119 +** This routine makes no determination one why or another if the
   1.120 +** database connection mutex is held.
   1.121 +**
   1.122 +** This routine is used only from within assert() statements.
   1.123 +*/
   1.124 +int sqlite3BtreeHoldsMutex(Btree *p){
   1.125 +  return (p->sharable==0 ||
   1.126 +             (p->locked && p->wantToLock && sqlite3_mutex_held(p->pBt->mutex)));
   1.127 +}
   1.128 +#endif
   1.129 +
   1.130 +
   1.131 +#ifndef SQLITE_OMIT_INCRBLOB
   1.132 +/*
   1.133 +** Enter and leave a mutex on a Btree given a cursor owned by that
   1.134 +** Btree.  These entry points are used by incremental I/O and can be
   1.135 +** omitted if that module is not used.
   1.136 +*/
   1.137 +void sqlite3BtreeEnterCursor(BtCursor *pCur){
   1.138 +  sqlite3BtreeEnter(pCur->pBtree);
   1.139 +}
   1.140 +void sqlite3BtreeLeaveCursor(BtCursor *pCur){
   1.141 +  sqlite3BtreeLeave(pCur->pBtree);
   1.142 +}
   1.143 +#endif /* SQLITE_OMIT_INCRBLOB */
   1.144 +
   1.145 +
   1.146 +/*
   1.147 +** Enter the mutex on every Btree associated with a database
   1.148 +** connection.  This is needed (for example) prior to parsing
   1.149 +** a statement since we will be comparing table and column names
   1.150 +** against all schemas and we do not want those schemas being
   1.151 +** reset out from under us.
   1.152 +**
   1.153 +** There is a corresponding leave-all procedures.
   1.154 +**
   1.155 +** Enter the mutexes in accending order by BtShared pointer address
   1.156 +** to avoid the possibility of deadlock when two threads with
   1.157 +** two or more btrees in common both try to lock all their btrees
   1.158 +** at the same instant.
   1.159 +*/
   1.160 +void sqlite3BtreeEnterAll(sqlite3 *db){
   1.161 +  int i;
   1.162 +  Btree *p, *pLater;
   1.163 +  assert( sqlite3_mutex_held(db->mutex) );
   1.164 +  for(i=0; i<db->nDb; i++){
   1.165 +    p = db->aDb[i].pBt;
   1.166 +    if( p && p->sharable ){
   1.167 +      p->wantToLock++;
   1.168 +      if( !p->locked ){
   1.169 +        assert( p->wantToLock==1 );
   1.170 +        while( p->pPrev ) p = p->pPrev;
   1.171 +        while( p->locked && p->pNext ) p = p->pNext;
   1.172 +        for(pLater = p->pNext; pLater; pLater=pLater->pNext){
   1.173 +          if( pLater->locked ){
   1.174 +            sqlite3_mutex_leave(pLater->pBt->mutex);
   1.175 +            pLater->locked = 0;
   1.176 +          }
   1.177 +        }
   1.178 +        while( p ){
   1.179 +          sqlite3_mutex_enter(p->pBt->mutex);
   1.180 +          p->locked++;
   1.181 +          p = p->pNext;
   1.182 +        }
   1.183 +      }
   1.184 +    }
   1.185 +  }
   1.186 +}
   1.187 +void sqlite3BtreeLeaveAll(sqlite3 *db){
   1.188 +  int i;
   1.189 +  Btree *p;
   1.190 +  assert( sqlite3_mutex_held(db->mutex) );
   1.191 +  for(i=0; i<db->nDb; i++){
   1.192 +    p = db->aDb[i].pBt;
   1.193 +    if( p && p->sharable ){
   1.194 +      assert( p->wantToLock>0 );
   1.195 +      p->wantToLock--;
   1.196 +      if( p->wantToLock==0 ){
   1.197 +        assert( p->locked );
   1.198 +        sqlite3_mutex_leave(p->pBt->mutex);
   1.199 +        p->locked = 0;
   1.200 +      }
   1.201 +    }
   1.202 +  }
   1.203 +}
   1.204 +
   1.205 +#ifndef NDEBUG
   1.206 +/*
   1.207 +** Return true if the current thread holds the database connection
   1.208 +** mutex and all required BtShared mutexes.
   1.209 +**
   1.210 +** This routine is used inside assert() statements only.
   1.211 +*/
   1.212 +int sqlite3BtreeHoldsAllMutexes(sqlite3 *db){
   1.213 +  int i;
   1.214 +  if( !sqlite3_mutex_held(db->mutex) ){
   1.215 +    return 0;
   1.216 +  }
   1.217 +  for(i=0; i<db->nDb; i++){
   1.218 +    Btree *p;
   1.219 +    p = db->aDb[i].pBt;
   1.220 +    if( p && p->sharable &&
   1.221 +         (p->wantToLock==0 || !sqlite3_mutex_held(p->pBt->mutex)) ){
   1.222 +      return 0;
   1.223 +    }
   1.224 +  }
   1.225 +  return 1;
   1.226 +}
   1.227 +#endif /* NDEBUG */
   1.228 +
   1.229 +/*
   1.230 +** Potentially dd a new Btree pointer to a BtreeMutexArray.
   1.231 +** Really only add the Btree if it can possibly be shared with
   1.232 +** another database connection.
   1.233 +**
   1.234 +** The Btrees are kept in sorted order by pBtree->pBt.  That
   1.235 +** way when we go to enter all the mutexes, we can enter them
   1.236 +** in order without every having to backup and retry and without
   1.237 +** worrying about deadlock.
   1.238 +**
   1.239 +** The number of shared btrees will always be small (usually 0 or 1)
   1.240 +** so an insertion sort is an adequate algorithm here.
   1.241 +*/
   1.242 +void sqlite3BtreeMutexArrayInsert(BtreeMutexArray *pArray, Btree *pBtree){
   1.243 +  int i, j;
   1.244 +  BtShared *pBt;
   1.245 +  if( pBtree==0 || pBtree->sharable==0 ) return;
   1.246 +#ifndef NDEBUG
   1.247 +  {
   1.248 +    for(i=0; i<pArray->nMutex; i++){
   1.249 +      assert( pArray->aBtree[i]!=pBtree );
   1.250 +    }
   1.251 +  }
   1.252 +#endif
   1.253 +  assert( pArray->nMutex>=0 );
   1.254 +  assert( pArray->nMutex<sizeof(pArray->aBtree)/sizeof(pArray->aBtree[0])-1 );
   1.255 +  pBt = pBtree->pBt;
   1.256 +  for(i=0; i<pArray->nMutex; i++){
   1.257 +    assert( pArray->aBtree[i]!=pBtree );
   1.258 +    if( pArray->aBtree[i]->pBt>pBt ){
   1.259 +      for(j=pArray->nMutex; j>i; j--){
   1.260 +        pArray->aBtree[j] = pArray->aBtree[j-1];
   1.261 +      }
   1.262 +      pArray->aBtree[i] = pBtree;
   1.263 +      pArray->nMutex++;
   1.264 +      return;
   1.265 +    }
   1.266 +  }
   1.267 +  pArray->aBtree[pArray->nMutex++] = pBtree;
   1.268 +}
   1.269 +
   1.270 +/*
   1.271 +** Enter the mutex of every btree in the array.  This routine is
   1.272 +** called at the beginning of sqlite3VdbeExec().  The mutexes are
   1.273 +** exited at the end of the same function.
   1.274 +*/
   1.275 +void sqlite3BtreeMutexArrayEnter(BtreeMutexArray *pArray){
   1.276 +  int i;
   1.277 +  for(i=0; i<pArray->nMutex; i++){
   1.278 +    Btree *p = pArray->aBtree[i];
   1.279 +    /* Some basic sanity checking */
   1.280 +    assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );
   1.281 +    assert( !p->locked || p->wantToLock>0 );
   1.282 +
   1.283 +    /* We should already hold a lock on the database connection */
   1.284 +    assert( sqlite3_mutex_held(p->pSqlite->mutex) );
   1.285 +
   1.286 +    p->wantToLock++;
   1.287 +    if( !p->locked && p->sharable ){
   1.288 +      sqlite3_mutex_enter(p->pBt->mutex);
   1.289 +      p->locked = 1;
   1.290 +    }
   1.291 +  }
   1.292 +}
   1.293 +
   1.294 +/*
   1.295 +** Leave the mutex of every btree in the group.
   1.296 +*/
   1.297 +void sqlite3BtreeMutexArrayLeave(BtreeMutexArray *pArray){
   1.298 +  int i;
   1.299 +  for(i=0; i<pArray->nMutex; i++){
   1.300 +    Btree *p = pArray->aBtree[i];
   1.301 +    /* Some basic sanity checking */
   1.302 +    assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );
   1.303 +    assert( p->locked || !p->sharable );
   1.304 +    assert( p->wantToLock>0 );
   1.305 +
   1.306 +    /* We should already hold a lock on the database connection */
   1.307 +    assert( sqlite3_mutex_held(p->pSqlite->mutex) );
   1.308 +
   1.309 +    p->wantToLock--;
   1.310 +    if( p->wantToLock==0 && p->locked ){
   1.311 +      sqlite3_mutex_leave(p->pBt->mutex);
   1.312 +      p->locked = 0;
   1.313 +    }
   1.314 +  }
   1.315 +}
   1.316 +
   1.317 +
   1.318 +#endif  /* SQLITE_THREADSAFE && !SQLITE_OMIT_SHARED_CACHE */