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