Many hyperlinks are disabled.
Use anonymous login
to enable hyperlinks.
Overview
| Comment: | Merge the latest version of mutexfree-shmlock with this branch. |
|---|---|
| Downloads: | Tarball | ZIP archive | SQL archive |
| Timelines: | family | ancestors | descendants | both | begin-concurrent-pnu-mutexfree-shmlock |
| Files: | files | file ages | folders |
| SHA3-256: |
6007abfe0935a47edc90ef34a4f0a8c4 |
| User & Date: | dan 2018-12-10 15:58:59 |
Context
|
2018-12-10
| ||
| 16:53 | Merge latest mutexfree-shmlock changes into this branch. Leaf check-in: 186b376e user: dan tags: begin-concurrent-pnu-mutexfree-shmlock | |
| 15:58 | Merge the latest version of mutexfree-shmlock with this branch. check-in: 6007abfe user: dan tags: begin-concurrent-pnu-mutexfree-shmlock | |
| 15:51 | Add extra tests to shmlock.test (direct testing of xShmLock methods). check-in: d2c785f9 user: dan tags: mutexfree-shmlock | |
| 09:36 | Avoid a mutex in-and-out in unixShmBarrier() on this branch. Use __sync_synchronize() instead. check-in: 280d1a72 user: dan tags: begin-concurrent-pnu-mutexfree-shmlock | |
Changes
Changes to src/os_unix.c.
44 44 ** plus implementations of sqlite3_os_init() and sqlite3_os_end(). 45 45 */ 46 46 #include "sqliteInt.h" 47 47 #if SQLITE_OS_UNIX /* This file is used on unix only */ 48 48 49 49 /* Turn this feature on in all builds for now */ 50 50 #define SQLITE_MUTEXFREE_SHMLOCK 1 51 +#define SQLITE_MFS_NSHARD 5 52 +#define SQLITE_MFS_EXCLUSIVE 255 51 53 52 54 /* 53 55 ** There are various methods for file locking used for concurrency 54 56 ** control: 55 57 ** 56 58 ** 1. POSIX locking (the default), 57 59 ** 2. No locking, ................................................................................ 4273 4275 ** 0, and so on. 4274 4276 ** 4275 4277 ** If the 8-bits corresponding to a shm-locking locking slot are set to 4276 4278 ** 0xFF, then a write-lock is held on the slot. Or, if they are set to 4277 4279 ** a non-zero value smaller than 0xFF, then they represent the total 4278 4280 ** number of read-locks held on the slot. There is no way to distinguish 4279 4281 ** between a write-lock and 255 read-locks. */ 4280 - u64 lockmask; 4282 + struct LockingSlot { 4283 + u32 nLock; 4284 + u64 aPadding[7]; 4285 + } aMFSlot[3 + SQLITE_MFS_NSHARD*5]; 4281 4286 #endif 4282 4287 }; 4283 4288 4284 4289 /* 4285 4290 ** Atomic CAS primitive used in multi-process mode. Equivalent to: 4286 4291 ** 4287 4292 ** int unixCompareAndSwap(u32 *ptr, u32 oldval, u32 newval){ ................................................................................ 4312 4317 struct unixShm { 4313 4318 unixShmNode *pShmNode; /* The underlying unixShmNode object */ 4314 4319 unixShm *pNext; /* Next unixShm with the same unixShmNode */ 4315 4320 u8 hasMutex; /* True if holding the unixShmNode->pShmMutex */ 4316 4321 u8 id; /* Id of this connection within its unixShmNode */ 4317 4322 u16 sharedMask; /* Mask of shared locks held */ 4318 4323 u16 exclMask; /* Mask of exclusive locks held */ 4324 +#ifdef SQLITE_MUTEXFREE_SHMLOCK 4325 + u8 aMFCurrent[8]; /* Current slot used for each shared lock */ 4326 +#endif 4319 4327 }; 4320 4328 4321 4329 /* 4322 4330 ** Constants used for locking 4323 4331 */ 4324 4332 #define UNIX_SHM_BASE ((22+SQLITE_SHM_NLOCK)*4) /* first lock byte */ 4325 4333 #define UNIX_SHM_DMS (UNIX_SHM_BASE+SQLITE_SHM_NLOCK) /* deadman switch */ ................................................................................ 4816 4824 *pp = 0; 4817 4825 } 4818 4826 if( pShmNode->isReadonly && rc==SQLITE_OK ) rc = SQLITE_READONLY; 4819 4827 sqlite3_mutex_leave(pShmNode->pShmMutex); 4820 4828 return rc; 4821 4829 } 4822 4830 4831 +#ifdef SQLITE_MUTEXFREE_SHMLOCK 4832 +static int unixMutexFreeShmlock( 4833 + unixFile *pFd, /* Database file holding the shared memory */ 4834 + int ofst, /* First lock to acquire or release */ 4835 + int n, /* Number of locks to acquire or release */ 4836 + int flags /* What to do with the lock */ 4837 +){ 4838 + struct LockMapEntry { 4839 + int iFirst; 4840 + int nSlot; 4841 + } aMap[9] = { 4842 + { 0, 1 }, 4843 + { 1, 1 }, 4844 + { 2, 1 }, 4845 + { 3+0*SQLITE_MFS_NSHARD, SQLITE_MFS_NSHARD }, 4846 + { 3+1*SQLITE_MFS_NSHARD, SQLITE_MFS_NSHARD }, 4847 + { 3+2*SQLITE_MFS_NSHARD, SQLITE_MFS_NSHARD }, 4848 + { 3+3*SQLITE_MFS_NSHARD, SQLITE_MFS_NSHARD }, 4849 + { 3+4*SQLITE_MFS_NSHARD, SQLITE_MFS_NSHARD }, 4850 + { 3+5*SQLITE_MFS_NSHARD, 0 }, 4851 + }; 4852 + 4853 + unixShm *p = pFd->pShm; /* The shared memory being locked */ 4854 + unixShm *pX; /* For looping over all siblings */ 4855 + unixShmNode *pShmNode = p->pShmNode; /* The underlying file iNode */ 4856 + int rc = SQLITE_OK; 4857 + int iIncr; 4858 + u16 mask; /* Mask of locks to take or release */ 4859 + 4860 + if( flags & SQLITE_SHM_SHARED ){ 4861 + /* SHARED locks */ 4862 + u32 iOld, iNew, *ptr; 4863 + int iIncr = -1; 4864 + if( (flags & SQLITE_SHM_UNLOCK)==0 ){ 4865 + p->aMFCurrent[ofst] = (p->aMFCurrent[ofst] + 1) % aMap[ofst].nSlot; 4866 + iIncr = 1; 4867 + } 4868 + ptr = &pShmNode->aMFSlot[aMap[ofst].iFirst + p->aMFCurrent[ofst]].nLock; 4869 + do { 4870 + iOld = *ptr; 4871 + iNew = iOld + iIncr; 4872 + if( iNew>SQLITE_MFS_EXCLUSIVE ){ 4873 + return SQLITE_BUSY; 4874 + } 4875 + }while( 0==unixCompareAndSwap(ptr, iOld, iNew) ); 4876 + }else{ 4877 + /* EXCLUSIVE locks */ 4878 + int iFirst = aMap[ofst].iFirst; 4879 + int iLast = aMap[ofst+n].iFirst; 4880 + int i; 4881 + for(i=iFirst; i<iLast; i++){ 4882 + u32 *ptr = &pShmNode->aMFSlot[i].nLock; 4883 + if( flags & SQLITE_SHM_UNLOCK ){ 4884 + assert( (*ptr)==SQLITE_MFS_EXCLUSIVE ); 4885 + *ptr = 0; 4886 + }else{ 4887 + u32 iOld; 4888 + do { 4889 + iOld = *ptr; 4890 + if( iOld>0 ){ 4891 + while( i>iFirst ){ 4892 + i--; 4893 + pShmNode->aMFSlot[i].nLock = 0; 4894 + } 4895 + return SQLITE_BUSY; 4896 + } 4897 + }while( 0==unixCompareAndSwap(ptr, iOld, SQLITE_MFS_EXCLUSIVE) ); 4898 + } 4899 + } 4900 + } 4901 + 4902 + return SQLITE_OK; 4903 +} 4904 +#else 4905 +# define unixMutexFreeShmlock(a,b,c,d) SQLITE_OK 4906 +#endif 4907 + 4823 4908 /* 4824 4909 ** Change the lock state for a shared-memory segment. 4825 4910 ** 4826 4911 ** Note that the relationship between SHAREd and EXCLUSIVE locks is a little 4827 4912 ** different here than in posix. In xShmLock(), one can go from unlocked 4828 4913 ** to shared and back or from unlocked to exclusive and back. But one may 4829 4914 ** not go from shared to exclusive or from exclusive to shared. ................................................................................ 4848 4933 assert( flags==(SQLITE_SHM_LOCK | SQLITE_SHM_SHARED) 4849 4934 || flags==(SQLITE_SHM_LOCK | SQLITE_SHM_EXCLUSIVE) 4850 4935 || flags==(SQLITE_SHM_UNLOCK | SQLITE_SHM_SHARED) 4851 4936 || flags==(SQLITE_SHM_UNLOCK | SQLITE_SHM_EXCLUSIVE) ); 4852 4937 assert( n==1 || (flags & SQLITE_SHM_EXCLUSIVE)!=0 ); 4853 4938 assert( pShmNode->hShm>=0 || pDbFd->pInode->bProcessLock==1 ); 4854 4939 assert( pShmNode->hShm<0 || pDbFd->pInode->bProcessLock==0 ); 4940 + 4941 + if( pDbFd->pInode->bProcessLock ){ 4942 + return unixMutexFreeShmlock(pDbFd, ofst, n, flags); 4943 + } 4855 4944 4856 4945 mask = (1<<(ofst+n)) - (1<<ofst); 4857 4946 assert( n>1 || mask==(1<<ofst) ); 4858 - 4859 -#ifdef SQLITE_MUTEXFREE_SHMLOCK 4860 - if( pDbFd->pInode->bProcessLock ){ 4861 - 4862 - while( 1 ){ 4863 - u64 lockmask = pShmNode->lockmask; 4864 - u64 newmask = lockmask; 4865 - int i; 4866 - for(i=ofst; i<n+ofst; i++){ 4867 - int ix8 = i*8; 4868 - u8 v = (lockmask >> (ix8)) & 0xFF; 4869 - if( flags & SQLITE_SHM_UNLOCK ){ 4870 - if( flags & SQLITE_SHM_EXCLUSIVE ){ 4871 - if( p->exclMask & (1 << i) ){ 4872 - newmask = newmask & ~((u64)0xFF<<ix8); 4873 - } 4874 - }else{ 4875 - if( p->sharedMask & (1 << i) ){ 4876 - newmask = newmask & ~((u64)0xFF<<ix8) | ((u64)(v-1)<<ix8); 4877 - } 4878 - } 4879 - }else{ 4880 - if( flags & SQLITE_SHM_EXCLUSIVE ){ 4881 - if( v ) return SQLITE_BUSY; 4882 - if( (p->exclMask & (1 << i))==0 ){ 4883 - newmask = newmask | ((u64)0xFF<<ix8); 4884 - } 4885 - }else{ 4886 - if( v==0xFF ) return SQLITE_BUSY; 4887 - if( (p->sharedMask & (1 << i))==0 ){ 4888 - newmask = newmask & ~((u64)0xFF<<ix8) | ((u64)(v+1)<<ix8); 4889 - } 4890 - } 4891 - } 4892 - } 4893 - 4894 - if( unixCompareAndSwap(&pShmNode->lockmask, lockmask, newmask) ) break; 4895 - } 4896 - 4897 - if( flags & SQLITE_SHM_UNLOCK ){ 4898 - p->sharedMask &= ~mask; 4899 - p->exclMask &= ~mask; 4900 - }else if( flags & SQLITE_SHM_EXCLUSIVE ){ 4901 - p->exclMask |= mask; 4902 - }else{ 4903 - p->sharedMask |= mask; 4904 - } 4905 - 4906 - return SQLITE_OK; 4947 + if( flags & SQLITE_SHM_LOCK ){ 4948 + assert( !(flags&SQLITE_SHM_SHARED) || (p->sharedMask&mask)==0 ); 4949 + assert( !(flags&SQLITE_SHM_EXCLUSIVE) || !(p->exclMask&mask) ); 4950 + }else{ 4951 + assert( !(flags&SQLITE_SHM_SHARED) || (p->sharedMask&mask)==mask ); 4952 + assert( !(flags&SQLITE_SHM_EXCLUSIVE) || (p->exclMask&mask)==mask ); 4907 4953 } 4908 -#endif 4909 4954 4910 4955 sqlite3_mutex_enter(pShmNode->pShmMutex); 4911 4956 if( flags & SQLITE_SHM_UNLOCK ){ 4912 4957 u16 allMask = 0; /* Mask of locks held by siblings */ 4913 4958 4914 4959 /* See if any siblings hold this same lock */ 4915 4960 for(pX=pShmNode->pFirst; pX; pX=pX->pNext){
Changes to src/test_superlock.c.
37 37 ** An instance of the following structure is allocated for each active 38 38 ** superlock. The opaque handle returned by sqlite3demo_superlock() is 39 39 ** actually a pointer to an instance of this structure. 40 40 */ 41 41 struct Superlock { 42 42 sqlite3 *db; /* Database handle used to lock db */ 43 43 int bWal; /* True if db is a WAL database */ 44 + int bRecoveryLocked; /* True if WAL RECOVERY lock is held */ 45 + int bReaderLocked; /* True if WAL READER locks are held */ 44 46 }; 45 47 typedef struct Superlock Superlock; 46 48 47 49 /* 48 50 ** The pCtx pointer passed to this function is actually a pointer to a 49 51 ** SuperlockBusy structure. Invoke the busy-handler function encapsulated 50 52 ** by the structure and return the result. ................................................................................ 103 105 } 104 106 105 107 /* 106 108 ** Obtain the extra locks on the database file required for WAL databases. 107 109 ** Invoke the supplied busy-handler as required. 108 110 */ 109 111 static int superlockWalLock( 110 - sqlite3 *db, /* Database handle open on WAL database */ 112 + Superlock *pLock, /* Superlock handle */ 111 113 SuperlockBusy *pBusy /* Busy handler wrapper object */ 112 114 ){ 113 115 int rc; /* Return code */ 114 116 sqlite3_file *fd = 0; /* Main database file handle */ 115 117 void volatile *p = 0; /* Pointer to first page of shared memory */ 118 + sqlite3 *db = pLock->db; 116 119 117 120 /* Obtain a pointer to the sqlite3_file object open on the main db file. */ 118 121 rc = sqlite3_file_control(db, "main", SQLITE_FCNTL_FILE_POINTER, (void *)&fd); 119 122 if( rc!=SQLITE_OK ) return rc; 120 123 121 124 /* Obtain the "recovery" lock. Normally, this lock is only obtained by 122 125 ** clients running database recovery. 123 126 */ 127 + assert( pLock->bRecoveryLocked==0 ); 124 128 rc = superlockShmLock(fd, 2, 1, pBusy); 125 129 if( rc!=SQLITE_OK ) return rc; 130 + pLock->bRecoveryLocked = 1; 126 131 127 132 /* Zero the start of the first shared-memory page. This means that any 128 133 ** clients that open read or write transactions from this point on will 129 134 ** have to run recovery before proceeding. Since they need the "recovery" 130 135 ** lock that this process is holding to do that, no new read or write 131 136 ** transactions may now be opened. Nor can a checkpoint be run, for the 132 137 ** same reason. ................................................................................ 135 140 if( rc!=SQLITE_OK ) return rc; 136 141 memset((void *)p, 0, 32); 137 142 138 143 /* Obtain exclusive locks on all the "read-lock" slots. Once these locks 139 144 ** are held, it is guaranteed that there are no active reader, writer or 140 145 ** checkpointer clients. 141 146 */ 147 + assert( pLock->bReaderLocked==0 ); 142 148 rc = superlockShmLock(fd, 3, SQLITE_SHM_NLOCK-3, pBusy); 149 + if( rc==SQLITE_OK ) pLock->bReaderLocked = 1; 143 150 return rc; 144 151 } 145 152 146 153 /* 147 154 ** Release a superlock held on a database file. The argument passed to 148 155 ** this function must have been obtained from a successful call to 149 156 ** sqlite3demo_superlock(). ................................................................................ 152 159 Superlock *p = (Superlock *)pLock; 153 160 if( p->bWal ){ 154 161 int rc; /* Return code */ 155 162 int flags = SQLITE_SHM_UNLOCK | SQLITE_SHM_EXCLUSIVE; 156 163 sqlite3_file *fd = 0; 157 164 rc = sqlite3_file_control(p->db, "main", SQLITE_FCNTL_FILE_POINTER, (void *)&fd); 158 165 if( rc==SQLITE_OK ){ 159 - fd->pMethods->xShmLock(fd, 2, 1, flags); 160 - fd->pMethods->xShmLock(fd, 3, SQLITE_SHM_NLOCK-3, flags); 166 + if( p->bRecoveryLocked ){ 167 + fd->pMethods->xShmLock(fd, 2, 1, flags); 168 + p->bRecoveryLocked = 0; 169 + } 170 + if( p->bReaderLocked ){ 171 + fd->pMethods->xShmLock(fd, 3, SQLITE_SHM_NLOCK-3, flags); 172 + p->bReaderLocked = 0; 173 + } 161 174 } 162 175 } 163 176 sqlite3_close(p->db); 164 177 sqlite3_free(p); 165 178 } 166 179 167 180 /* ................................................................................ 228 241 ** to drop the WAL read and write locks currently held. Otherwise, the 229 242 ** new WAL locks may conflict with the old. 230 243 */ 231 244 if( rc==SQLITE_OK ){ 232 245 if( SQLITE_OK==(rc = superlockIsWal(pLock)) && pLock->bWal ){ 233 246 rc = sqlite3_exec(pLock->db, "COMMIT", 0, 0, 0); 234 247 if( rc==SQLITE_OK ){ 235 - rc = superlockWalLock(pLock->db, &busy); 248 + rc = superlockWalLock(pLock, &busy); 236 249 } 237 250 } 238 251 } 239 252 240 253 if( rc!=SQLITE_OK ){ 241 254 sqlite3demo_superunlock(pLock); 242 255 *ppLock = 0;
Changes to src/wal.c.
2793 2793 ** checkpoint need not have completed for this to cause problems. 2794 2794 */ 2795 2795 volatile WalCkptInfo *pInfo = walCkptInfo(pWal); 2796 2796 2797 2797 assert( pWal->readLock>0 || pWal->hdr.mxFrame==0 ); 2798 2798 assert( pInfo->aReadMark[pWal->readLock]<=pSnapshot->mxFrame ); 2799 2799 2800 - /* It is possible that there is a checkpointer thread running 2801 - ** concurrent with this code. If this is the case, it may be that the 2802 - ** checkpointer has already determined that it will checkpoint 2800 + /* If it were possible for a checkpointer thread to run concurrent 2801 + ** with this code, it would be a problem. In this case, it could be 2802 + ** that the checkpointer has already determined that it will checkpoint 2803 2803 ** snapshot X, where X is later in the wal file than pSnapshot, but 2804 2804 ** has not yet set the pInfo->nBackfillAttempted variable to indicate 2805 - ** its intent. To avoid the race condition this leads to, ensure that 2806 - ** there is no checkpointer process by taking a shared CKPT lock 2807 - ** before checking pInfo->nBackfillAttempted. 2808 - ** 2809 - ** TODO: Does the aReadMark[] lock prevent a checkpointer from doing 2810 - ** this already? 2811 - */ 2812 - rc = walLockShared(pWal, WAL_CKPT_LOCK); 2805 + ** its intent. Fortunately this is not possible, as the call to 2806 + ** sqlite3WalSnapshotOpen() that sets pWal->pSnapshot also takes a 2807 + ** SHARED lock on the checkpointer slot. */ 2813 2808 2814 2809 if( rc==SQLITE_OK ){ 2815 2810 /* Check that the wal file has not been wrapped. Assuming that it has 2816 2811 ** not, also check that no checkpointer has attempted to checkpoint any 2817 2812 ** frames beyond pSnapshot->mxFrame. If either of these conditions are 2818 2813 ** true, return SQLITE_ERROR_SNAPSHOT. Otherwise, overwrite pWal->hdr 2819 2814 ** with *pSnapshot and set *pChanged as appropriate for opening the ................................................................................ 2824 2819 assert( pWal->readLock>0 ); 2825 2820 memcpy(&pWal->hdr, pSnapshot, sizeof(WalIndexHdr)); 2826 2821 *pChanged = bChanged; 2827 2822 }else{ 2828 2823 rc = SQLITE_ERROR_SNAPSHOT; 2829 2824 } 2830 2825 2831 - /* Release the shared CKPT lock obtained above. */ 2832 - walUnlockShared(pWal, WAL_CKPT_LOCK); 2833 2826 pWal->minFrame = 1; 2834 2827 } 2835 2828 2836 2829 2837 2830 if( rc!=SQLITE_OK ){ 2838 2831 sqlite3WalEndReadTransaction(pWal); 2839 2832 }
Changes to test/shmlock.test.
100 100 if {$rc != "SQLITE_OK"} { error $rc } 101 101 } 102 102 103 103 vfs_shmlock db255 main exclusive lock 4 1 104 104 } {SQLITE_OK} 105 105 106 106 vfs_shmlock db255 main exclusive unlock 4 1 107 + 108 + for {set i 0} {$i < 256} {incr i} { 109 + db$i close 110 + } 111 +} 112 + 113 +sqlite3 db0 test.db 114 +sqlite3 db1 test.db 115 +do_test 3.1 { execsql { SELECT * FROM t1 } db0 } {1 2} 116 +do_test 3.2 { execsql { SELECT * FROM t1 } db1 } {1 2} 117 + 118 +set L(0) {n n n n n n n n} 119 +set L(1) {n n n n n n n n} 120 +proc random_lock_test {idx} { 121 + global L 122 + set iSlot [expr int(rand()*8)] 123 + if {[expr int(rand()*2)]} { 124 + # Unlock operation 125 + if {[lindex $L($idx) $iSlot]!="n"} { 126 + vfs_shmlock db$idx main [lindex $L($idx) $iSlot] unlock $iSlot 1 127 + lset L($idx) $iSlot n 128 + } 129 + } else { 130 + # Lock operation 131 + if {[lindex $L($idx) $iSlot]=="n"} { 132 + set locktype [lindex {e s} [expr int(rand()*2)]] 133 + set n 1 134 + if {$locktype=="e"} { 135 + for {set l $iSlot} {$l<8 && [lindex $L($idx) $l]=="n"} {incr l} {} 136 + set n [expr int(rand()*($l-$iSlot))+1] 137 + # puts "iSlot=$iSlot l=$l L=$L($idx)" 138 + # puts "$iSlot $n" 139 + } 140 + set res [vfs_shmlock db$idx main $locktype lock $iSlot $n] 141 + 142 + set bBusy 0 143 + for {set i $iSlot} {$i<($iSlot+$n)} {incr i} { 144 + set other [lindex $L([expr ($idx+1)%2]) $i] 145 + if {($other!="n" && $locktype=="e")||($other=="e" && $locktype=="s")} { 146 + if {$res != "SQLITE_BUSY"} { error "BUSY not detected" } 147 + set bBusy 1 148 + break 149 + } 150 + } 151 + 152 + if {$bBusy==0} { 153 + if {$res != "SQLITE_OK"} { error "BUSY false-positive" } 154 + for {set i $iSlot} {$i<($iSlot+$n)} {incr i} { 155 + lset L($idx) $i $locktype 156 + } 157 + } 158 + } 159 + } 160 +} 161 + 162 +set nStep 100000 163 +for {set i 0} {$i < $nStep} {incr i} { 164 + random_lock_test 0 165 + random_lock_test 1 107 166 } 167 + 168 +db0 close 169 +db1 close 108 170 109 171 finish_test 110 172 111 173