1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/os/persistentdata/persistentstorage/sqlite3api/SQLite/btmutex.c Fri Jun 15 03:10:57 2012 +0200
1.3 @@ -0,0 +1,317 @@
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: btmutex.c,v 1.10 2008/07/14 19:39:17 drh Exp $
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->db==p->db );
1.53 + assert( p->pPrev==0 || p->pPrev->db==p->db );
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->db->mutex) );
1.62 +
1.63 + if( !p->sharable ) return;
1.64 + p->wantToLock++;
1.65 + if( p->locked ) return;
1.66 +
1.67 +#ifndef SQLITE_MUTEX_NOOP
1.68 + /* In most cases, we should be able to acquire the lock we
1.69 + ** want without having to go throught the ascending lock
1.70 + ** procedure that follows. Just be sure not to block.
1.71 + */
1.72 + if( sqlite3_mutex_try(p->pBt->mutex)==SQLITE_OK ){
1.73 + p->locked = 1;
1.74 + return;
1.75 + }
1.76 +
1.77 + /* To avoid deadlock, first release all locks with a larger
1.78 + ** BtShared address. Then acquire our lock. Then reacquire
1.79 + ** the other BtShared locks that we used to hold in ascending
1.80 + ** order.
1.81 + */
1.82 + for(pLater=p->pNext; pLater; pLater=pLater->pNext){
1.83 + assert( pLater->sharable );
1.84 + assert( pLater->pNext==0 || pLater->pNext->pBt>pLater->pBt );
1.85 + assert( !pLater->locked || pLater->wantToLock>0 );
1.86 + if( pLater->locked ){
1.87 + sqlite3_mutex_leave(pLater->pBt->mutex);
1.88 + pLater->locked = 0;
1.89 + }
1.90 + }
1.91 + sqlite3_mutex_enter(p->pBt->mutex);
1.92 + p->locked = 1;
1.93 + for(pLater=p->pNext; pLater; pLater=pLater->pNext){
1.94 + if( pLater->wantToLock ){
1.95 + sqlite3_mutex_enter(pLater->pBt->mutex);
1.96 + pLater->locked = 1;
1.97 + }
1.98 + }
1.99 +#endif /* SQLITE_MUTEX_NOOP */
1.100 +}
1.101 +
1.102 +/*
1.103 +** Exit the recursive mutex on a Btree.
1.104 +*/
1.105 +void sqlite3BtreeLeave(Btree *p){
1.106 + if( p->sharable ){
1.107 + assert( p->wantToLock>0 );
1.108 + p->wantToLock--;
1.109 + if( p->wantToLock==0 ){
1.110 + assert( p->locked );
1.111 + sqlite3_mutex_leave(p->pBt->mutex);
1.112 + p->locked = 0;
1.113 + }
1.114 + }
1.115 +}
1.116 +
1.117 +#ifndef NDEBUG
1.118 +/*
1.119 +** Return true if the BtShared mutex is held on the btree.
1.120 +**
1.121 +** This routine makes no determination one why or another if the
1.122 +** database connection mutex is held.
1.123 +**
1.124 +** This routine is used only from within assert() statements.
1.125 +*/
1.126 +int sqlite3BtreeHoldsMutex(Btree *p){
1.127 + return (p->sharable==0 ||
1.128 + (p->locked && p->wantToLock && sqlite3_mutex_held(p->pBt->mutex)));
1.129 +}
1.130 +#endif
1.131 +
1.132 +
1.133 +#ifndef SQLITE_OMIT_INCRBLOB
1.134 +/*
1.135 +** Enter and leave a mutex on a Btree given a cursor owned by that
1.136 +** Btree. These entry points are used by incremental I/O and can be
1.137 +** omitted if that module is not used.
1.138 +*/
1.139 +void sqlite3BtreeEnterCursor(BtCursor *pCur){
1.140 + sqlite3BtreeEnter(pCur->pBtree);
1.141 +}
1.142 +void sqlite3BtreeLeaveCursor(BtCursor *pCur){
1.143 + sqlite3BtreeLeave(pCur->pBtree);
1.144 +}
1.145 +#endif /* SQLITE_OMIT_INCRBLOB */
1.146 +
1.147 +
1.148 +/*
1.149 +** Enter the mutex on every Btree associated with a database
1.150 +** connection. This is needed (for example) prior to parsing
1.151 +** a statement since we will be comparing table and column names
1.152 +** against all schemas and we do not want those schemas being
1.153 +** reset out from under us.
1.154 +**
1.155 +** There is a corresponding leave-all procedures.
1.156 +**
1.157 +** Enter the mutexes in accending order by BtShared pointer address
1.158 +** to avoid the possibility of deadlock when two threads with
1.159 +** two or more btrees in common both try to lock all their btrees
1.160 +** at the same instant.
1.161 +*/
1.162 +void sqlite3BtreeEnterAll(sqlite3 *db){
1.163 + int i;
1.164 + Btree *p, *pLater;
1.165 + assert( sqlite3_mutex_held(db->mutex) );
1.166 + for(i=0; i<db->nDb; i++){
1.167 + p = db->aDb[i].pBt;
1.168 + if( p && p->sharable ){
1.169 + p->wantToLock++;
1.170 + if( !p->locked ){
1.171 + assert( p->wantToLock==1 );
1.172 + while( p->pPrev ) p = p->pPrev;
1.173 + while( p->locked && p->pNext ) p = p->pNext;
1.174 + for(pLater = p->pNext; pLater; pLater=pLater->pNext){
1.175 + if( pLater->locked ){
1.176 + sqlite3_mutex_leave(pLater->pBt->mutex);
1.177 + pLater->locked = 0;
1.178 + }
1.179 + }
1.180 + while( p ){
1.181 + sqlite3_mutex_enter(p->pBt->mutex);
1.182 + p->locked++;
1.183 + p = p->pNext;
1.184 + }
1.185 + }
1.186 + }
1.187 + }
1.188 +}
1.189 +void sqlite3BtreeLeaveAll(sqlite3 *db){
1.190 + int i;
1.191 + Btree *p;
1.192 + assert( sqlite3_mutex_held(db->mutex) );
1.193 + for(i=0; i<db->nDb; i++){
1.194 + p = db->aDb[i].pBt;
1.195 + if( p && p->sharable ){
1.196 + assert( p->wantToLock>0 );
1.197 + p->wantToLock--;
1.198 + if( p->wantToLock==0 ){
1.199 + assert( p->locked );
1.200 + sqlite3_mutex_leave(p->pBt->mutex);
1.201 + p->locked = 0;
1.202 + }
1.203 + }
1.204 + }
1.205 +}
1.206 +
1.207 +#ifndef NDEBUG
1.208 +/*
1.209 +** Return true if the current thread holds the database connection
1.210 +** mutex and all required BtShared mutexes.
1.211 +**
1.212 +** This routine is used inside assert() statements only.
1.213 +*/
1.214 +int sqlite3BtreeHoldsAllMutexes(sqlite3 *db){
1.215 + int i;
1.216 + if( !sqlite3_mutex_held(db->mutex) ){
1.217 + return 0;
1.218 + }
1.219 + for(i=0; i<db->nDb; i++){
1.220 + Btree *p;
1.221 + p = db->aDb[i].pBt;
1.222 + if( p && p->sharable &&
1.223 + (p->wantToLock==0 || !sqlite3_mutex_held(p->pBt->mutex)) ){
1.224 + return 0;
1.225 + }
1.226 + }
1.227 + return 1;
1.228 +}
1.229 +#endif /* NDEBUG */
1.230 +
1.231 +/*
1.232 +** Add a new Btree pointer to a BtreeMutexArray.
1.233 +** if the pointer can possibly be shared with
1.234 +** another database connection.
1.235 +**
1.236 +** The pointers are kept in sorted order by pBtree->pBt. That
1.237 +** way when we go to enter all the mutexes, we can enter them
1.238 +** in order without every having to backup and retry and without
1.239 +** worrying about deadlock.
1.240 +**
1.241 +** The number of shared btrees will always be small (usually 0 or 1)
1.242 +** so an insertion sort is an adequate algorithm here.
1.243 +*/
1.244 +void sqlite3BtreeMutexArrayInsert(BtreeMutexArray *pArray, Btree *pBtree){
1.245 + int i, j;
1.246 + BtShared *pBt;
1.247 + if( pBtree==0 || pBtree->sharable==0 ) return;
1.248 +#ifndef NDEBUG
1.249 + {
1.250 + for(i=0; i<pArray->nMutex; i++){
1.251 + assert( pArray->aBtree[i]!=pBtree );
1.252 + }
1.253 + }
1.254 +#endif
1.255 + assert( pArray->nMutex>=0 );
1.256 + assert( pArray->nMutex<sizeof(pArray->aBtree)/sizeof(pArray->aBtree[0])-1 );
1.257 + pBt = pBtree->pBt;
1.258 + for(i=0; i<pArray->nMutex; i++){
1.259 + assert( pArray->aBtree[i]!=pBtree );
1.260 + if( pArray->aBtree[i]->pBt>pBt ){
1.261 + for(j=pArray->nMutex; j>i; j--){
1.262 + pArray->aBtree[j] = pArray->aBtree[j-1];
1.263 + }
1.264 + pArray->aBtree[i] = pBtree;
1.265 + pArray->nMutex++;
1.266 + return;
1.267 + }
1.268 + }
1.269 + pArray->aBtree[pArray->nMutex++] = pBtree;
1.270 +}
1.271 +
1.272 +/*
1.273 +** Enter the mutex of every btree in the array. This routine is
1.274 +** called at the beginning of sqlite3VdbeExec(). The mutexes are
1.275 +** exited at the end of the same function.
1.276 +*/
1.277 +void sqlite3BtreeMutexArrayEnter(BtreeMutexArray *pArray){
1.278 + int i;
1.279 + for(i=0; i<pArray->nMutex; i++){
1.280 + Btree *p = pArray->aBtree[i];
1.281 + /* Some basic sanity checking */
1.282 + assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );
1.283 + assert( !p->locked || p->wantToLock>0 );
1.284 +
1.285 + /* We should already hold a lock on the database connection */
1.286 + assert( sqlite3_mutex_held(p->db->mutex) );
1.287 +
1.288 + p->wantToLock++;
1.289 + if( !p->locked && p->sharable ){
1.290 + sqlite3_mutex_enter(p->pBt->mutex);
1.291 + p->locked = 1;
1.292 + }
1.293 + }
1.294 +}
1.295 +
1.296 +/*
1.297 +** Leave the mutex of every btree in the group.
1.298 +*/
1.299 +void sqlite3BtreeMutexArrayLeave(BtreeMutexArray *pArray){
1.300 + int i;
1.301 + for(i=0; i<pArray->nMutex; i++){
1.302 + Btree *p = pArray->aBtree[i];
1.303 + /* Some basic sanity checking */
1.304 + assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );
1.305 + assert( p->locked || !p->sharable );
1.306 + assert( p->wantToLock>0 );
1.307 +
1.308 + /* We should already hold a lock on the database connection */
1.309 + assert( sqlite3_mutex_held(p->db->mutex) );
1.310 +
1.311 + p->wantToLock--;
1.312 + if( p->wantToLock==0 && p->locked ){
1.313 + sqlite3_mutex_leave(p->pBt->mutex);
1.314 + p->locked = 0;
1.315 + }
1.316 + }
1.317 +}
1.318 +
1.319 +
1.320 +#endif /* SQLITE_THREADSAFE && !SQLITE_OMIT_SHARED_CACHE */