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 through 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   assert( sqlite3_mutex_held(p->db->mutex) );
145   if( p->sharable ){
146     assert( p->wantToLock>0 );
147     p->wantToLock--;
148     if( p->wantToLock==0 ){
149       unlockBtreeMutex(p);
150     }
151   }
152 }
153 
154 #ifndef NDEBUG
155 /*
156 ** Return true if the BtShared mutex is held on the btree, or if the
157 ** B-Tree is not marked as sharable.
158 **
159 ** This routine is used only from within assert() statements.
160 */
161 int sqlite3BtreeHoldsMutex(Btree *p){
162   assert( p->sharable==0 || p->locked==0 || p->wantToLock>0 );
163   assert( p->sharable==0 || p->locked==0 || p->db==p->pBt->db );
164   assert( p->sharable==0 || p->locked==0 || sqlite3_mutex_held(p->pBt->mutex) );
165   assert( p->sharable==0 || p->locked==0 || sqlite3_mutex_held(p->db->mutex) );
166 
167   return (p->sharable==0 || p->locked);
168 }
169 #endif
170 
171 
172 /*
173 ** Enter the mutex on every Btree associated with a database
174 ** connection.  This is needed (for example) prior to parsing
175 ** a statement since we will be comparing table and column names
176 ** against all schemas and we do not want those schemas being
177 ** reset out from under us.
178 **
179 ** There is a corresponding leave-all procedures.
180 **
181 ** Enter the mutexes in accending order by BtShared pointer address
182 ** to avoid the possibility of deadlock when two threads with
183 ** two or more btrees in common both try to lock all their btrees
184 ** at the same instant.
185 */
186 static void SQLITE_NOINLINE btreeEnterAll(sqlite3 *db){
187   int i;
188   int skipOk = 1;
189   Btree *p;
190   assert( sqlite3_mutex_held(db->mutex) );
191   for(i=0; i<db->nDb; i++){
192     p = db->aDb[i].pBt;
193     if( p && p->sharable ){
194       sqlite3BtreeEnter(p);
195       skipOk = 0;
196     }
197   }
198   db->noSharedCache = skipOk;
199 }
200 void sqlite3BtreeEnterAll(sqlite3 *db){
201   if( db->noSharedCache==0 ) btreeEnterAll(db);
202 }
203 static void SQLITE_NOINLINE btreeLeaveAll(sqlite3 *db){
204   int i;
205   Btree *p;
206   assert( sqlite3_mutex_held(db->mutex) );
207   for(i=0; i<db->nDb; i++){
208     p = db->aDb[i].pBt;
209     if( p ) sqlite3BtreeLeave(p);
210   }
211 }
212 void sqlite3BtreeLeaveAll(sqlite3 *db){
213   if( db->noSharedCache==0 ) btreeLeaveAll(db);
214 }
215 
216 #ifndef NDEBUG
217 /*
218 ** Return true if the current thread holds the database connection
219 ** mutex and all required BtShared mutexes.
220 **
221 ** This routine is used inside assert() statements only.
222 */
223 int sqlite3BtreeHoldsAllMutexes(sqlite3 *db){
224   int i;
225   if( !sqlite3_mutex_held(db->mutex) ){
226     return 0;
227   }
228   for(i=0; i<db->nDb; i++){
229     Btree *p;
230     p = db->aDb[i].pBt;
231     if( p && p->sharable &&
232          (p->wantToLock==0 || !sqlite3_mutex_held(p->pBt->mutex)) ){
233       return 0;
234     }
235   }
236   return 1;
237 }
238 #endif /* NDEBUG */
239 
240 #ifndef NDEBUG
241 /*
242 ** Return true if the correct mutexes are held for accessing the
243 ** db->aDb[iDb].pSchema structure.  The mutexes required for schema
244 ** access are:
245 **
246 **   (1) The mutex on db
247 **   (2) if iDb!=1, then the mutex on db->aDb[iDb].pBt.
248 **
249 ** If pSchema is not NULL, then iDb is computed from pSchema and
250 ** db using sqlite3SchemaToIndex().
251 */
252 int sqlite3SchemaMutexHeld(sqlite3 *db, int iDb, Schema *pSchema){
253   Btree *p;
254   assert( db!=0 );
255   if( db->pVfs==0 && db->nDb==0 ) return 1;
256   if( pSchema ) iDb = sqlite3SchemaToIndex(db, pSchema);
257   assert( iDb>=0 && iDb<db->nDb );
258   if( !sqlite3_mutex_held(db->mutex) ) return 0;
259   if( iDb==1 ) return 1;
260   p = db->aDb[iDb].pBt;
261   assert( p!=0 );
262   return p->sharable==0 || p->locked==1;
263 }
264 #endif /* NDEBUG */
265 
266 #else /* SQLITE_THREADSAFE>0 above.  SQLITE_THREADSAFE==0 below */
267 /*
268 ** The following are special cases for mutex enter routines for use
269 ** in single threaded applications that use shared cache.  Except for
270 ** these two routines, all mutex operations are no-ops in that case and
271 ** are null #defines in btree.h.
272 **
273 ** If shared cache is disabled, then all btree mutex routines, including
274 ** the ones below, are no-ops and are null #defines in btree.h.
275 */
276 
277 void sqlite3BtreeEnter(Btree *p){
278   p->pBt->db = p->db;
279 }
280 void sqlite3BtreeEnterAll(sqlite3 *db){
281   int i;
282   for(i=0; i<db->nDb; i++){
283     Btree *p = db->aDb[i].pBt;
284     if( p ){
285       p->pBt->db = p->db;
286     }
287   }
288 }
289 #endif /* if SQLITE_THREADSAFE */
290 
291 #ifndef SQLITE_OMIT_INCRBLOB
292 /*
293 ** Enter a mutex on a Btree given a cursor owned by that Btree.
294 **
295 ** These entry points are used by incremental I/O only. Enter() is required
296 ** any time OMIT_SHARED_CACHE is not defined, regardless of whether or not
297 ** the build is threadsafe. Leave() is only required by threadsafe builds.
298 */
299 void sqlite3BtreeEnterCursor(BtCursor *pCur){
300   sqlite3BtreeEnter(pCur->pBtree);
301 }
302 # if SQLITE_THREADSAFE
303 void sqlite3BtreeLeaveCursor(BtCursor *pCur){
304   sqlite3BtreeLeave(pCur->pBtree);
305 }
306 # endif
307 #endif /* ifndef SQLITE_OMIT_INCRBLOB */
308 
309 #endif /* ifndef SQLITE_OMIT_SHARED_CACHE */
310