drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 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 | ** |
danielk1977 | 00e1361 | 2008-11-17 19:18:54 +0000 | [diff] [blame] | 13 | ** $Id: btmutex.c,v 1.12 2008/11/17 19:18:55 danielk1977 Exp $ |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 14 | ** |
| 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 | */ |
| 40 | void 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 ); |
drh | e5fe690 | 2007-12-07 18:55:28 +0000 | [diff] [blame] | 49 | assert( p->pNext==0 || p->pNext->db==p->db ); |
| 50 | assert( p->pPrev==0 || p->pPrev->db==p->db ); |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 51 | 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 */ |
drh | e5fe690 | 2007-12-07 18:55:28 +0000 | [diff] [blame] | 58 | assert( sqlite3_mutex_held(p->db->mutex) ); |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 59 | |
| 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); |
drh | ac32155 | 2007-08-28 16:44:20 +0000 | [diff] [blame] | 88 | p->locked = 1; |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 89 | 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 | */ |
| 100 | void 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 | |
drh | 1fee73e | 2007-08-29 04:00:57 +0000 | [diff] [blame] | 112 | #ifndef NDEBUG |
| 113 | /* |
drh | ff0587c | 2007-08-29 17:43:19 +0000 | [diff] [blame] | 114 | ** 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. |
drh | 1fee73e | 2007-08-29 04:00:57 +0000 | [diff] [blame] | 118 | ** |
| 119 | ** This routine is used only from within assert() statements. |
| 120 | */ |
| 121 | int sqlite3BtreeHoldsMutex(Btree *p){ |
drh | ff0587c | 2007-08-29 17:43:19 +0000 | [diff] [blame] | 122 | return (p->sharable==0 || |
drh | 1fee73e | 2007-08-29 04:00:57 +0000 | [diff] [blame] | 123 | (p->locked && p->wantToLock && sqlite3_mutex_held(p->pBt->mutex))); |
| 124 | } |
| 125 | #endif |
| 126 | |
| 127 | |
drh | ff0587c | 2007-08-29 17:43:19 +0000 | [diff] [blame] | 128 | #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 | */ |
| 134 | void sqlite3BtreeEnterCursor(BtCursor *pCur){ |
| 135 | sqlite3BtreeEnter(pCur->pBtree); |
| 136 | } |
| 137 | void sqlite3BtreeLeaveCursor(BtCursor *pCur){ |
| 138 | sqlite3BtreeLeave(pCur->pBtree); |
| 139 | } |
| 140 | #endif /* SQLITE_OMIT_INCRBLOB */ |
| 141 | |
| 142 | |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 143 | /* |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 144 | ** 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 | */ |
| 157 | void sqlite3BtreeEnterAll(sqlite3 *db){ |
| 158 | int i; |
drh | 1fee73e | 2007-08-29 04:00:57 +0000 | [diff] [blame] | 159 | Btree *p, *pLater; |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 160 | assert( sqlite3_mutex_held(db->mutex) ); |
drh | 1fee73e | 2007-08-29 04:00:57 +0000 | [diff] [blame] | 161 | for(i=0; i<db->nDb; i++){ |
| 162 | p = db->aDb[i].pBt; |
| 163 | if( p && p->sharable ){ |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 164 | p->wantToLock++; |
drh | 1fee73e | 2007-08-29 04:00:57 +0000 | [diff] [blame] | 165 | 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 | } |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 181 | } |
| 182 | } |
| 183 | } |
| 184 | void sqlite3BtreeLeaveAll(sqlite3 *db){ |
| 185 | int i; |
| 186 | Btree *p; |
| 187 | assert( sqlite3_mutex_held(db->mutex) ); |
drh | 1fee73e | 2007-08-29 04:00:57 +0000 | [diff] [blame] | 188 | for(i=0; i<db->nDb; i++){ |
| 189 | p = db->aDb[i].pBt; |
| 190 | if( p && p->sharable ){ |
| 191 | assert( p->wantToLock>0 ); |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 192 | p->wantToLock--; |
| 193 | if( p->wantToLock==0 ){ |
drh | 1fee73e | 2007-08-29 04:00:57 +0000 | [diff] [blame] | 194 | assert( p->locked ); |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 195 | sqlite3_mutex_leave(p->pBt->mutex); |
| 196 | p->locked = 0; |
| 197 | } |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 198 | } |
| 199 | } |
| 200 | } |
| 201 | |
drh | 1fee73e | 2007-08-29 04:00:57 +0000 | [diff] [blame] | 202 | #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 | */ |
| 209 | int 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 | |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 226 | /* |
drh | 65cef1a | 2008-07-14 19:39:16 +0000 | [diff] [blame] | 227 | ** Add a new Btree pointer to a BtreeMutexArray. |
| 228 | ** if the pointer can possibly be shared with |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 229 | ** another database connection. |
| 230 | ** |
drh | 65cef1a | 2008-07-14 19:39:16 +0000 | [diff] [blame] | 231 | ** The pointers are kept in sorted order by pBtree->pBt. That |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 232 | ** 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 | */ |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 239 | void sqlite3BtreeMutexArrayInsert(BtreeMutexArray *pArray, Btree *pBtree){ |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 240 | int i, j; |
| 241 | BtShared *pBt; |
drh | fb98264 | 2007-08-30 01:19:59 +0000 | [diff] [blame] | 242 | if( pBtree==0 || pBtree->sharable==0 ) return; |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 243 | #ifndef NDEBUG |
| 244 | { |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 245 | for(i=0; i<pArray->nMutex; i++){ |
| 246 | assert( pArray->aBtree[i]!=pBtree ); |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 247 | } |
| 248 | } |
| 249 | #endif |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 250 | assert( pArray->nMutex>=0 ); |
danielk1977 | 00e1361 | 2008-11-17 19:18:54 +0000 | [diff] [blame] | 251 | assert( pArray->nMutex<ArraySize(pArray->aBtree)-1 ); |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 252 | pBt = pBtree->pBt; |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 253 | 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]; |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 258 | } |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 259 | pArray->aBtree[i] = pBtree; |
| 260 | pArray->nMutex++; |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 261 | return; |
| 262 | } |
| 263 | } |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 264 | pArray->aBtree[pArray->nMutex++] = pBtree; |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 265 | } |
| 266 | |
| 267 | /* |
drh | 4cf7c7f | 2007-08-28 23:28:07 +0000 | [diff] [blame] | 268 | ** Enter the mutex of every btree in the array. This routine is |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 269 | ** called at the beginning of sqlite3VdbeExec(). The mutexes are |
| 270 | ** exited at the end of the same function. |
| 271 | */ |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 272 | void sqlite3BtreeMutexArrayEnter(BtreeMutexArray *pArray){ |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 273 | int i; |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 274 | for(i=0; i<pArray->nMutex; i++){ |
| 275 | Btree *p = pArray->aBtree[i]; |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 276 | /* Some basic sanity checking */ |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 277 | assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt ); |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 278 | assert( !p->locked || p->wantToLock>0 ); |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 279 | |
| 280 | /* We should already hold a lock on the database connection */ |
drh | e5fe690 | 2007-12-07 18:55:28 +0000 | [diff] [blame] | 281 | assert( sqlite3_mutex_held(p->db->mutex) ); |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 282 | |
| 283 | p->wantToLock++; |
drh | 1fee73e | 2007-08-29 04:00:57 +0000 | [diff] [blame] | 284 | if( !p->locked && p->sharable ){ |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 285 | sqlite3_mutex_enter(p->pBt->mutex); |
drh | ac32155 | 2007-08-28 16:44:20 +0000 | [diff] [blame] | 286 | p->locked = 1; |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 287 | } |
| 288 | } |
| 289 | } |
| 290 | |
| 291 | /* |
drh | 4cf7c7f | 2007-08-28 23:28:07 +0000 | [diff] [blame] | 292 | ** Leave the mutex of every btree in the group. |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 293 | */ |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 294 | void sqlite3BtreeMutexArrayLeave(BtreeMutexArray *pArray){ |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 295 | int i; |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 296 | for(i=0; i<pArray->nMutex; i++){ |
| 297 | Btree *p = pArray->aBtree[i]; |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 298 | /* Some basic sanity checking */ |
drh | b1ab8ea | 2007-08-29 00:33:07 +0000 | [diff] [blame] | 299 | assert( i==0 || pArray->aBtree[i-1]->pBt<p->pBt ); |
drh | 1fee73e | 2007-08-29 04:00:57 +0000 | [diff] [blame] | 300 | assert( p->locked || !p->sharable ); |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 301 | assert( p->wantToLock>0 ); |
| 302 | |
| 303 | /* We should already hold a lock on the database connection */ |
drh | e5fe690 | 2007-12-07 18:55:28 +0000 | [diff] [blame] | 304 | assert( sqlite3_mutex_held(p->db->mutex) ); |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 305 | |
| 306 | p->wantToLock--; |
drh | 1fee73e | 2007-08-29 04:00:57 +0000 | [diff] [blame] | 307 | if( p->wantToLock==0 && p->locked ){ |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 308 | sqlite3_mutex_leave(p->pBt->mutex); |
drh | ac32155 | 2007-08-28 16:44:20 +0000 | [diff] [blame] | 309 | p->locked = 0; |
drh | 900b31e | 2007-08-28 02:27:51 +0000 | [diff] [blame] | 310 | } |
| 311 | } |
| 312 | } |
| 313 | |
| 314 | |
| 315 | #endif /* SQLITE_THREADSAFE && !SQLITE_OMIT_SHARED_CACHE */ |