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 ** This file contains code used to implement mutexes on Btree objects. 14 ** This code really belongs in btree.c. But btree.c is getting too 15 ** big and we want to break it down some. This packaged seemed like 16 ** a good breakout. 17 */ 18 #include "btreeInt.h" 19 #ifndef SQLITE_OMIT_SHARED_CACHE 20 #if SQLITE_THREADSAFE 21 22 /* 23 ** Obtain the BtShared mutex associated with B-Tree handle p. Also, 24 ** set BtShared.db to the database handle associated with p and the 25 ** p->locked boolean to true. 26 */ 27 static void lockBtreeMutex(Btree *p){ 28 assert( p->locked==0 ); 29 assert( sqlite3_mutex_notheld(p->pBt->mutex) ); 30 assert( sqlite3_mutex_held(p->db->mutex) ); 31 32 sqlite3_mutex_enter(p->pBt->mutex); 33 p->pBt->db = p->db; 34 p->locked = 1; 35 } 36 37 /* 38 ** Release the BtShared mutex associated with B-Tree handle p and 39 ** clear the p->locked boolean. 40 */ 41 static void SQLITE_NOINLINE unlockBtreeMutex(Btree *p){ 42 BtShared *pBt = p->pBt; 43 assert( p->locked==1 ); 44 assert( sqlite3_mutex_held(pBt->mutex) ); 45 assert( sqlite3_mutex_held(p->db->mutex) ); 46 assert( p->db==pBt->db ); 47 48 sqlite3_mutex_leave(pBt->mutex); 49 p->locked = 0; 50 } 51 52 /* Forward reference */ 53 static void SQLITE_NOINLINE btreeLockCarefully(Btree *p); 54 55 /* 56 ** Enter a mutex on the given BTree object. 57 ** 58 ** If the object is not sharable, then no mutex is ever required 59 ** and this routine is a no-op. The underlying mutex is non-recursive. 60 ** But we keep a reference count in Btree.wantToLock so the behavior 61 ** of this interface is recursive. 62 ** 63 ** To avoid deadlocks, multiple Btrees are locked in the same order 64 ** by all database connections. The p->pNext is a list of other 65 ** Btrees belonging to the same database connection as the p Btree 66 ** which need to be locked after p. If we cannot get a lock on 67 ** p, then first unlock all of the others on p->pNext, then wait 68 ** for the lock to become available on p, then relock all of the 69 ** subsequent Btrees that desire a lock. 70 */ 71 void sqlite3BtreeEnter(Btree *p){ 72 /* Some basic sanity checking on the Btree. The list of Btrees 73 ** connected by pNext and pPrev should be in sorted order by 74 ** Btree.pBt value. All elements of the list should belong to 75 ** the same connection. Only shared Btrees are on the list. */ 76 assert( p->pNext==0 || p->pNext->pBt>p->pBt ); 77 assert( p->pPrev==0 || p->pPrev->pBt<p->pBt ); 78 assert( p->pNext==0 || p->pNext->db==p->db ); 79 assert( p->pPrev==0 || p->pPrev->db==p->db ); 80 assert( p->sharable || (p->pNext==0 && p->pPrev==0) ); 81 82 /* Check for locking consistency */ 83 assert( !p->locked || p->wantToLock>0 ); 84 assert( p->sharable || p->wantToLock==0 ); 85 86 /* We should already hold a lock on the database connection */ 87 assert( sqlite3_mutex_held(p->db->mutex) ); 88 89 /* Unless the database is sharable and unlocked, then BtShared.db 90 ** should already be set correctly. */ 91 assert( (p->locked==0 && p->sharable) || p->pBt->db==p->db ); 92 93 if( !p->sharable ) return; 94 p->wantToLock++; 95 if( p->locked ) return; 96 btreeLockCarefully(p); 97 } 98 99 /* This is a helper function for sqlite3BtreeLock(). By moving 100 ** complex, but seldom used logic, out of sqlite3BtreeLock() and 101 ** into this routine, we avoid unnecessary stack pointer changes 102 ** and thus help the sqlite3BtreeLock() routine to run much faster 103 ** in the common case. 104 */ 105 static void SQLITE_NOINLINE btreeLockCarefully(Btree *p){ 106 Btree *pLater; 107 108 /* In most cases, we should be able to acquire the lock we 109 ** want without having to go throught the ascending lock 110 ** procedure that follows. Just be sure not to block. 111 */ 112 if( sqlite3_mutex_try(p->pBt->mutex)==SQLITE_OK ){ 113 p->pBt->db = p->db; 114 p->locked = 1; 115 return; 116 } 117 118 /* To avoid deadlock, first release all locks with a larger 119 ** BtShared address. Then acquire our lock. Then reacquire 120 ** the other BtShared locks that we used to hold in ascending 121 ** order. 122 */ 123 for(pLater=p->pNext; pLater; pLater=pLater->pNext){ 124 assert( pLater->sharable ); 125 assert( pLater->pNext==0 || pLater->pNext->pBt>pLater->pBt ); 126 assert( !pLater->locked || pLater->wantToLock>0 ); 127 if( pLater->locked ){ 128 unlockBtreeMutex(pLater); 129 } 130 } 131 lockBtreeMutex(p); 132 for(pLater=p->pNext; pLater; pLater=pLater->pNext){ 133 if( pLater->wantToLock ){ 134 lockBtreeMutex(pLater); 135 } 136 } 137 } 138 139 140 /* 141 ** Exit the recursive mutex on a Btree. 142 */ 143 void sqlite3BtreeLeave(Btree *p){ 144 if( p->sharable ){ 145 assert( p->wantToLock>0 ); 146 p->wantToLock--; 147 if( p->wantToLock==0 ){ 148 unlockBtreeMutex(p); 149 } 150 } 151 } 152 153 #ifndef NDEBUG 154 /* 155 ** Return true if the BtShared mutex is held on the btree, or if the 156 ** B-Tree is not marked as sharable. 157 ** 158 ** This routine is used only from within assert() statements. 159 */ 160 int sqlite3BtreeHoldsMutex(Btree *p){ 161 assert( p->sharable==0 || p->locked==0 || p->wantToLock>0 ); 162 assert( p->sharable==0 || p->locked==0 || p->db==p->pBt->db ); 163 assert( p->sharable==0 || p->locked==0 || sqlite3_mutex_held(p->pBt->mutex) ); 164 assert( p->sharable==0 || p->locked==0 || sqlite3_mutex_held(p->db->mutex) ); 165 166 return (p->sharable==0 || p->locked); 167 } 168 #endif 169 170 171 #ifndef SQLITE_OMIT_INCRBLOB 172 /* 173 ** Enter and leave a mutex on a Btree given a cursor owned by that 174 ** Btree. These entry points are used by incremental I/O and can be 175 ** omitted if that module is not used. 176 */ 177 void sqlite3BtreeEnterCursor(BtCursor *pCur){ 178 sqlite3BtreeEnter(pCur->pBtree); 179 } 180 void sqlite3BtreeLeaveCursor(BtCursor *pCur){ 181 sqlite3BtreeLeave(pCur->pBtree); 182 } 183 #endif /* SQLITE_OMIT_INCRBLOB */ 184 185 186 /* 187 ** Enter the mutex on every Btree associated with a database 188 ** connection. This is needed (for example) prior to parsing 189 ** a statement since we will be comparing table and column names 190 ** against all schemas and we do not want those schemas being 191 ** reset out from under us. 192 ** 193 ** There is a corresponding leave-all procedures. 194 ** 195 ** Enter the mutexes in accending order by BtShared pointer address 196 ** to avoid the possibility of deadlock when two threads with 197 ** two or more btrees in common both try to lock all their btrees 198 ** at the same instant. 199 */ 200 void sqlite3BtreeEnterAll(sqlite3 *db){ 201 int i; 202 Btree *p; 203 assert( sqlite3_mutex_held(db->mutex) ); 204 for(i=0; i<db->nDb; i++){ 205 p = db->aDb[i].pBt; 206 if( p ) sqlite3BtreeEnter(p); 207 } 208 } 209 void sqlite3BtreeLeaveAll(sqlite3 *db){ 210 int i; 211 Btree *p; 212 assert( sqlite3_mutex_held(db->mutex) ); 213 for(i=0; i<db->nDb; i++){ 214 p = db->aDb[i].pBt; 215 if( p ) sqlite3BtreeLeave(p); 216 } 217 } 218 219 /* 220 ** Return true if a particular Btree requires a lock. Return FALSE if 221 ** no lock is ever required since it is not sharable. 222 */ 223 int sqlite3BtreeSharable(Btree *p){ 224 return p->sharable; 225 } 226 227 #ifndef NDEBUG 228 /* 229 ** Return true if the current thread holds the database connection 230 ** mutex and all required BtShared mutexes. 231 ** 232 ** This routine is used inside assert() statements only. 233 */ 234 int sqlite3BtreeHoldsAllMutexes(sqlite3 *db){ 235 int i; 236 if( !sqlite3_mutex_held(db->mutex) ){ 237 return 0; 238 } 239 for(i=0; i<db->nDb; i++){ 240 Btree *p; 241 p = db->aDb[i].pBt; 242 if( p && p->sharable && 243 (p->wantToLock==0 || !sqlite3_mutex_held(p->pBt->mutex)) ){ 244 return 0; 245 } 246 } 247 return 1; 248 } 249 #endif /* NDEBUG */ 250 251 #ifndef NDEBUG 252 /* 253 ** Return true if the correct mutexes are held for accessing the 254 ** db->aDb[iDb].pSchema structure. The mutexes required for schema 255 ** access are: 256 ** 257 ** (1) The mutex on db 258 ** (2) if iDb!=1, then the mutex on db->aDb[iDb].pBt. 259 ** 260 ** If pSchema is not NULL, then iDb is computed from pSchema and 261 ** db using sqlite3SchemaToIndex(). 262 */ 263 int sqlite3SchemaMutexHeld(sqlite3 *db, int iDb, Schema *pSchema){ 264 Btree *p; 265 assert( db!=0 ); 266 if( pSchema ) iDb = sqlite3SchemaToIndex(db, pSchema); 267 assert( iDb>=0 && iDb<db->nDb ); 268 if( !sqlite3_mutex_held(db->mutex) ) return 0; 269 if( iDb==1 ) return 1; 270 p = db->aDb[iDb].pBt; 271 assert( p!=0 ); 272 return p->sharable==0 || p->locked==1; 273 } 274 #endif /* NDEBUG */ 275 276 #else /* SQLITE_THREADSAFE>0 above. SQLITE_THREADSAFE==0 below */ 277 /* 278 ** The following are special cases for mutex enter routines for use 279 ** in single threaded applications that use shared cache. Except for 280 ** these two routines, all mutex operations are no-ops in that case and 281 ** are null #defines in btree.h. 282 ** 283 ** If shared cache is disabled, then all btree mutex routines, including 284 ** the ones below, are no-ops and are null #defines in btree.h. 285 */ 286 287 void sqlite3BtreeEnter(Btree *p){ 288 p->pBt->db = p->db; 289 } 290 void sqlite3BtreeEnterAll(sqlite3 *db){ 291 int i; 292 for(i=0; i<db->nDb; i++){ 293 Btree *p = db->aDb[i].pBt; 294 if( p ){ 295 p->pBt->db = p->db; 296 } 297 } 298 } 299 #endif /* if SQLITE_THREADSAFE */ 300 #endif /* ifndef SQLITE_OMIT_SHARED_CACHE */ 301