1 // Copyright 2017 The Go Authors. All rights reserved. 2 // Use of this source code is governed by a BSD-style 3 // license that can be found in the LICENSE file. 4 5 package runtime 6 7 import ( 8 "runtime/internal/atomic" 9 ) 10 11 // This is a copy of sync/rwmutex.go rewritten to work in the runtime. 12 13 // A rwmutex is a reader/writer mutual exclusion lock. 14 // The lock can be held by an arbitrary number of readers or a single writer. 15 // This is a variant of sync.RWMutex, for the runtime package. 16 // Like mutex, rwmutex blocks the calling M. 17 // It does not interact with the goroutine scheduler. 18 type rwmutex struct { 19 rLock mutex // protects readers, readerPass, writer 20 readers muintptr // list of pending readers 21 readerPass uint32 // number of pending readers to skip readers list 22 23 wLock mutex // serializes writers 24 writer muintptr // pending writer waiting for completing readers 25 26 readerCount atomic.Int32 // number of pending readers 27 readerWait atomic.Int32 // number of departing readers 28 29 readRank lockRank // semantic lock rank for read locking 30 } 31 32 // Lock ranking an rwmutex has two aspects: 33 // 34 // Semantic ranking: this rwmutex represents some higher level lock that 35 // protects some resource (e.g., allocmLock protects creation of new Ms). The 36 // read and write locks of that resource need to be represented in the lock 37 // rank. 38 // 39 // Internal ranking: as an implementation detail, rwmutex uses two mutexes: 40 // rLock and wLock. These have lock order requirements: wLock must be locked 41 // before rLock. This also needs to be represented in the lock rank. 42 // 43 // Semantic ranking is represented by acquiring readRank during read lock and 44 // writeRank during write lock. 45 // 46 // wLock is held for the duration of a write lock, so it uses writeRank 47 // directly, both for semantic and internal ranking. rLock is only held 48 // temporarily inside the rlock/lock methods, so it uses readRankInternal to 49 // represent internal ranking. Semantic ranking is represented by a separate 50 // acquire of readRank for the duration of a read lock. 51 // 52 // The lock ranking must document this ordering: 53 // - readRankInternal is a leaf lock. 54 // - readRank is taken before readRankInternal. 55 // - writeRank is taken before readRankInternal. 56 // - readRank is placed in the lock order wherever a read lock of this rwmutex 57 // belongs. 58 // - writeRank is placed in the lock order wherever a write lock of this 59 // rwmutex belongs. 60 func (rw *rwmutex) init(readRank, readRankInternal, writeRank lockRank) { 61 rw.readRank = readRank 62 63 lockInit(&rw.rLock, readRankInternal) 64 lockInit(&rw.wLock, writeRank) 65 } 66 67 const rwmutexMaxReaders = 1 << 30 68 69 // rlock locks rw for reading. 70 func (rw *rwmutex) rlock() { 71 // The reader must not be allowed to lose its P or else other 72 // things blocking on the lock may consume all of the Ps and 73 // deadlock (issue #20903). Alternatively, we could drop the P 74 // while sleeping. 75 acquirem() 76 77 acquireLockRank(rw.readRank) 78 lockWithRankMayAcquire(&rw.rLock, getLockRank(&rw.rLock)) 79 80 if rw.readerCount.Add(1) < 0 { 81 // A writer is pending. Park on the reader queue. 82 systemstack(func() { 83 lock(&rw.rLock) 84 if rw.readerPass > 0 { 85 // Writer finished. 86 rw.readerPass -= 1 87 unlock(&rw.rLock) 88 } else { 89 // Queue this reader to be woken by 90 // the writer. 91 m := getg().m 92 m.schedlink = rw.readers 93 rw.readers.set(m) 94 unlock(&rw.rLock) 95 notesleep(&m.park) 96 noteclear(&m.park) 97 } 98 }) 99 } 100 } 101 102 // runlock undoes a single rlock call on rw. 103 func (rw *rwmutex) runlock() { 104 if r := rw.readerCount.Add(-1); r < 0 { 105 if r+1 == 0 || r+1 == -rwmutexMaxReaders { 106 throw("runlock of unlocked rwmutex") 107 } 108 // A writer is pending. 109 if rw.readerWait.Add(-1) == 0 { 110 // The last reader unblocks the writer. 111 lock(&rw.rLock) 112 w := rw.writer.ptr() 113 if w != nil { 114 notewakeup(&w.park) 115 } 116 unlock(&rw.rLock) 117 } 118 } 119 releaseLockRank(rw.readRank) 120 releasem(getg().m) 121 } 122 123 // lock locks rw for writing. 124 func (rw *rwmutex) lock() { 125 // Resolve competition with other writers and stick to our P. 126 lock(&rw.wLock) 127 m := getg().m 128 // Announce that there is a pending writer. 129 r := rw.readerCount.Add(-rwmutexMaxReaders) + rwmutexMaxReaders 130 // Wait for any active readers to complete. 131 lock(&rw.rLock) 132 if r != 0 && rw.readerWait.Add(r) != 0 { 133 // Wait for reader to wake us up. 134 systemstack(func() { 135 rw.writer.set(m) 136 unlock(&rw.rLock) 137 notesleep(&m.park) 138 noteclear(&m.park) 139 }) 140 } else { 141 unlock(&rw.rLock) 142 } 143 } 144 145 // unlock unlocks rw for writing. 146 func (rw *rwmutex) unlock() { 147 // Announce to readers that there is no active writer. 148 r := rw.readerCount.Add(rwmutexMaxReaders) 149 if r >= rwmutexMaxReaders { 150 throw("unlock of unlocked rwmutex") 151 } 152 // Unblock blocked readers. 153 lock(&rw.rLock) 154 for rw.readers.ptr() != nil { 155 reader := rw.readers.ptr() 156 rw.readers = reader.schedlink 157 reader.schedlink.set(nil) 158 notewakeup(&reader.park) 159 r -= 1 160 } 161 // If r > 0, there are pending readers that aren't on the 162 // queue. Tell them to skip waiting. 163 rw.readerPass += uint32(r) 164 unlock(&rw.rLock) 165 // Allow other writers to proceed. 166 unlock(&rw.wLock) 167 } 168