blob: b1ab5173e68259df0d4111506e6c97864cadb552 [file] [log] [blame]
drh900b31e2007-08-28 02:27:51 +00001/*
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**
danielk197700e13612008-11-17 19:18:54 +000013** $Id: btmutex.c,v 1.12 2008/11/17 19:18:55 danielk1977 Exp $
drh900b31e2007-08-28 02:27:51 +000014**
15** This file contains code used to implement mutexes on Btree objects.
16** This code really belongs in btree.c. But btree.c is getting too
17** big and we want to break it down some. This packaged seemed like
18** a good breakout.
19*/
20#include "btreeInt.h"
21#if SQLITE_THREADSAFE && !defined(SQLITE_OMIT_SHARED_CACHE)
22
23
24/*
25** Enter a mutex on the given BTree object.
26**
27** If the object is not sharable, then no mutex is ever required
28** and this routine is a no-op. The underlying mutex is non-recursive.
29** But we keep a reference count in Btree.wantToLock so the behavior
30** of this interface is recursive.
31**
32** To avoid deadlocks, multiple Btrees are locked in the same order
33** by all database connections. The p->pNext is a list of other
34** Btrees belonging to the same database connection as the p Btree
35** which need to be locked after p. If we cannot get a lock on
36** p, then first unlock all of the others on p->pNext, then wait
37** for the lock to become available on p, then relock all of the
38** subsequent Btrees that desire a lock.
39*/
40void sqlite3BtreeEnter(Btree *p){
41 Btree *pLater;
42
43 /* Some basic sanity checking on the Btree. The list of Btrees
44 ** connected by pNext and pPrev should be in sorted order by
45 ** Btree.pBt value. All elements of the list should belong to
46 ** the same connection. Only shared Btrees are on the list. */
47 assert( p->pNext==0 || p->pNext->pBt>p->pBt );
48 assert( p->pPrev==0 || p->pPrev->pBt<p->pBt );
drhe5fe6902007-12-07 18:55:28 +000049 assert( p->pNext==0 || p->pNext->db==p->db );
50 assert( p->pPrev==0 || p->pPrev->db==p->db );
drh900b31e2007-08-28 02:27:51 +000051 assert( p->sharable || (p->pNext==0 && p->pPrev==0) );
52
53 /* Check for locking consistency */
54 assert( !p->locked || p->wantToLock>0 );
55 assert( p->sharable || p->wantToLock==0 );
56
57 /* We should already hold a lock on the database connection */
drhe5fe6902007-12-07 18:55:28 +000058 assert( sqlite3_mutex_held(p->db->mutex) );
drh900b31e2007-08-28 02:27:51 +000059
60 if( !p->sharable ) return;
61 p->wantToLock++;
62 if( p->locked ) return;
63
64 /* In most cases, we should be able to acquire the lock we
65 ** want without having to go throught the ascending lock
66 ** procedure that follows. Just be sure not to block.
67 */
68 if( sqlite3_mutex_try(p->pBt->mutex)==SQLITE_OK ){
69 p->locked = 1;
70 return;
71 }
72
73 /* To avoid deadlock, first release all locks with a larger
74 ** BtShared address. Then acquire our lock. Then reacquire
75 ** the other BtShared locks that we used to hold in ascending
76 ** order.
77 */
78 for(pLater=p->pNext; pLater; pLater=pLater->pNext){
79 assert( pLater->sharable );
80 assert( pLater->pNext==0 || pLater->pNext->pBt>pLater->pBt );
81 assert( !pLater->locked || pLater->wantToLock>0 );
82 if( pLater->locked ){
83 sqlite3_mutex_leave(pLater->pBt->mutex);
84 pLater->locked = 0;
85 }
86 }
87 sqlite3_mutex_enter(p->pBt->mutex);
drhac321552007-08-28 16:44:20 +000088 p->locked = 1;
drh900b31e2007-08-28 02:27:51 +000089 for(pLater=p->pNext; pLater; pLater=pLater->pNext){
90 if( pLater->wantToLock ){
91 sqlite3_mutex_enter(pLater->pBt->mutex);
92 pLater->locked = 1;
93 }
94 }
95}
96
97/*
98** Exit the recursive mutex on a Btree.
99*/
100void sqlite3BtreeLeave(Btree *p){
101 if( p->sharable ){
102 assert( p->wantToLock>0 );
103 p->wantToLock--;
104 if( p->wantToLock==0 ){
105 assert( p->locked );
106 sqlite3_mutex_leave(p->pBt->mutex);
107 p->locked = 0;
108 }
109 }
110}
111
drh1fee73e2007-08-29 04:00:57 +0000112#ifndef NDEBUG
113/*
drhff0587c2007-08-29 17:43:19 +0000114** Return true if the BtShared mutex is held on the btree.
115**
116** This routine makes no determination one why or another if the
117** database connection mutex is held.
drh1fee73e2007-08-29 04:00:57 +0000118**
119** This routine is used only from within assert() statements.
120*/
121int sqlite3BtreeHoldsMutex(Btree *p){
drhff0587c2007-08-29 17:43:19 +0000122 return (p->sharable==0 ||
drh1fee73e2007-08-29 04:00:57 +0000123 (p->locked && p->wantToLock && sqlite3_mutex_held(p->pBt->mutex)));
124}
125#endif
126
127
drhff0587c2007-08-29 17:43:19 +0000128#ifndef SQLITE_OMIT_INCRBLOB
129/*
130** Enter and leave a mutex on a Btree given a cursor owned by that
131** Btree. These entry points are used by incremental I/O and can be
132** omitted if that module is not used.
133*/
134void sqlite3BtreeEnterCursor(BtCursor *pCur){
135 sqlite3BtreeEnter(pCur->pBtree);
136}
137void sqlite3BtreeLeaveCursor(BtCursor *pCur){
138 sqlite3BtreeLeave(pCur->pBtree);
139}
140#endif /* SQLITE_OMIT_INCRBLOB */
141
142
drh900b31e2007-08-28 02:27:51 +0000143/*
drhb1ab8ea2007-08-29 00:33:07 +0000144** Enter the mutex on every Btree associated with a database
145** connection. This is needed (for example) prior to parsing
146** a statement since we will be comparing table and column names
147** against all schemas and we do not want those schemas being
148** reset out from under us.
149**
150** There is a corresponding leave-all procedures.
151**
152** Enter the mutexes in accending order by BtShared pointer address
153** to avoid the possibility of deadlock when two threads with
154** two or more btrees in common both try to lock all their btrees
155** at the same instant.
156*/
157void sqlite3BtreeEnterAll(sqlite3 *db){
158 int i;
drh1fee73e2007-08-29 04:00:57 +0000159 Btree *p, *pLater;
drhb1ab8ea2007-08-29 00:33:07 +0000160 assert( sqlite3_mutex_held(db->mutex) );
drh1fee73e2007-08-29 04:00:57 +0000161 for(i=0; i<db->nDb; i++){
162 p = db->aDb[i].pBt;
163 if( p && p->sharable ){
drhb1ab8ea2007-08-29 00:33:07 +0000164 p->wantToLock++;
drh1fee73e2007-08-29 04:00:57 +0000165 if( !p->locked ){
166 assert( p->wantToLock==1 );
167 while( p->pPrev ) p = p->pPrev;
168 while( p->locked && p->pNext ) p = p->pNext;
169 for(pLater = p->pNext; pLater; pLater=pLater->pNext){
170 if( pLater->locked ){
171 sqlite3_mutex_leave(pLater->pBt->mutex);
172 pLater->locked = 0;
173 }
174 }
175 while( p ){
176 sqlite3_mutex_enter(p->pBt->mutex);
177 p->locked++;
178 p = p->pNext;
179 }
180 }
drhb1ab8ea2007-08-29 00:33:07 +0000181 }
182 }
183}
184void sqlite3BtreeLeaveAll(sqlite3 *db){
185 int i;
186 Btree *p;
187 assert( sqlite3_mutex_held(db->mutex) );
drh1fee73e2007-08-29 04:00:57 +0000188 for(i=0; i<db->nDb; i++){
189 p = db->aDb[i].pBt;
190 if( p && p->sharable ){
191 assert( p->wantToLock>0 );
drhb1ab8ea2007-08-29 00:33:07 +0000192 p->wantToLock--;
193 if( p->wantToLock==0 ){
drh1fee73e2007-08-29 04:00:57 +0000194 assert( p->locked );
drhb1ab8ea2007-08-29 00:33:07 +0000195 sqlite3_mutex_leave(p->pBt->mutex);
196 p->locked = 0;
197 }
drhb1ab8ea2007-08-29 00:33:07 +0000198 }
199 }
200}
201
drh1fee73e2007-08-29 04:00:57 +0000202#ifndef NDEBUG
203/*
204** Return true if the current thread holds the database connection
205** mutex and all required BtShared mutexes.
206**
207** This routine is used inside assert() statements only.
208*/
209int sqlite3BtreeHoldsAllMutexes(sqlite3 *db){
210 int i;
211 if( !sqlite3_mutex_held(db->mutex) ){
212 return 0;
213 }
214 for(i=0; i<db->nDb; i++){
215 Btree *p;
216 p = db->aDb[i].pBt;
217 if( p && p->sharable &&
218 (p->wantToLock==0 || !sqlite3_mutex_held(p->pBt->mutex)) ){
219 return 0;
220 }
221 }
222 return 1;
223}
224#endif /* NDEBUG */
225
drhb1ab8ea2007-08-29 00:33:07 +0000226/*
drh65cef1a2008-07-14 19:39:16 +0000227** Add a new Btree pointer to a BtreeMutexArray.
228** if the pointer can possibly be shared with
drh900b31e2007-08-28 02:27:51 +0000229** another database connection.
230**
drh65cef1a2008-07-14 19:39:16 +0000231** The pointers are kept in sorted order by pBtree->pBt. That
drh900b31e2007-08-28 02:27:51 +0000232** way when we go to enter all the mutexes, we can enter them
233** in order without every having to backup and retry and without
234** worrying about deadlock.
235**
236** The number of shared btrees will always be small (usually 0 or 1)
237** so an insertion sort is an adequate algorithm here.
238*/
drhb1ab8ea2007-08-29 00:33:07 +0000239void sqlite3BtreeMutexArrayInsert(BtreeMutexArray *pArray, Btree *pBtree){
drh900b31e2007-08-28 02:27:51 +0000240 int i, j;
241 BtShared *pBt;
drhfb982642007-08-30 01:19:59 +0000242 if( pBtree==0 || pBtree->sharable==0 ) return;
drh900b31e2007-08-28 02:27:51 +0000243#ifndef NDEBUG
244 {
drhb1ab8ea2007-08-29 00:33:07 +0000245 for(i=0; i<pArray->nMutex; i++){
246 assert( pArray->aBtree[i]!=pBtree );
drh900b31e2007-08-28 02:27:51 +0000247 }
248 }
249#endif
drhb1ab8ea2007-08-29 00:33:07 +0000250 assert( pArray->nMutex>=0 );
danielk197700e13612008-11-17 19:18:54 +0000251 assert( pArray->nMutex<ArraySize(pArray->aBtree)-1 );
drh900b31e2007-08-28 02:27:51 +0000252 pBt = pBtree->pBt;
drhb1ab8ea2007-08-29 00:33:07 +0000253 for(i=0; i<pArray->nMutex; i++){
254 assert( pArray->aBtree[i]!=pBtree );
255 if( pArray->aBtree[i]->pBt>pBt ){
256 for(j=pArray->nMutex; j>i; j--){
257 pArray->aBtree[j] = pArray->aBtree[j-1];
drh900b31e2007-08-28 02:27:51 +0000258 }
drhb1ab8ea2007-08-29 00:33:07 +0000259 pArray->aBtree[i] = pBtree;
260 pArray->nMutex++;
drh900b31e2007-08-28 02:27:51 +0000261 return;
262 }
263 }
drhb1ab8ea2007-08-29 00:33:07 +0000264 pArray->aBtree[pArray->nMutex++] = pBtree;
drh900b31e2007-08-28 02:27:51 +0000265}
266
267/*
drh4cf7c7f2007-08-28 23:28:07 +0000268** Enter the mutex of every btree in the array. This routine is
drh900b31e2007-08-28 02:27:51 +0000269** called at the beginning of sqlite3VdbeExec(). The mutexes are
270** exited at the end of the same function.
271*/
drhb1ab8ea2007-08-29 00:33:07 +0000272void sqlite3BtreeMutexArrayEnter(BtreeMutexArray *pArray){
drh900b31e2007-08-28 02:27:51 +0000273 int i;
drhb1ab8ea2007-08-29 00:33:07 +0000274 for(i=0; i<pArray->nMutex; i++){
275 Btree *p = pArray->aBtree[i];
drh900b31e2007-08-28 02:27:51 +0000276 /* Some basic sanity checking */
drhb1ab8ea2007-08-29 00:33:07 +0000277 assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );
drh900b31e2007-08-28 02:27:51 +0000278 assert( !p->locked || p->wantToLock>0 );
drh900b31e2007-08-28 02:27:51 +0000279
280 /* We should already hold a lock on the database connection */
drhe5fe6902007-12-07 18:55:28 +0000281 assert( sqlite3_mutex_held(p->db->mutex) );
drh900b31e2007-08-28 02:27:51 +0000282
283 p->wantToLock++;
drh1fee73e2007-08-29 04:00:57 +0000284 if( !p->locked && p->sharable ){
drh900b31e2007-08-28 02:27:51 +0000285 sqlite3_mutex_enter(p->pBt->mutex);
drhac321552007-08-28 16:44:20 +0000286 p->locked = 1;
drh900b31e2007-08-28 02:27:51 +0000287 }
288 }
289}
290
291/*
drh4cf7c7f2007-08-28 23:28:07 +0000292** Leave the mutex of every btree in the group.
drh900b31e2007-08-28 02:27:51 +0000293*/
drhb1ab8ea2007-08-29 00:33:07 +0000294void sqlite3BtreeMutexArrayLeave(BtreeMutexArray *pArray){
drh900b31e2007-08-28 02:27:51 +0000295 int i;
drhb1ab8ea2007-08-29 00:33:07 +0000296 for(i=0; i<pArray->nMutex; i++){
297 Btree *p = pArray->aBtree[i];
drh900b31e2007-08-28 02:27:51 +0000298 /* Some basic sanity checking */
drhb1ab8ea2007-08-29 00:33:07 +0000299 assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt );
drh1fee73e2007-08-29 04:00:57 +0000300 assert( p->locked || !p->sharable );
drh900b31e2007-08-28 02:27:51 +0000301 assert( p->wantToLock>0 );
302
303 /* We should already hold a lock on the database connection */
drhe5fe6902007-12-07 18:55:28 +0000304 assert( sqlite3_mutex_held(p->db->mutex) );
drh900b31e2007-08-28 02:27:51 +0000305
306 p->wantToLock--;
drh1fee73e2007-08-29 04:00:57 +0000307 if( p->wantToLock==0 && p->locked ){
drh900b31e2007-08-28 02:27:51 +0000308 sqlite3_mutex_leave(p->pBt->mutex);
drhac321552007-08-28 16:44:20 +0000309 p->locked = 0;
drh900b31e2007-08-28 02:27:51 +0000310 }
311 }
312}
313
314
315#endif /* SQLITE_THREADSAFE && !SQLITE_OMIT_SHARED_CACHE */