libgo/go/sync/mutex.go

   1 // Copyright 2009 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 sync provides basic synchronization primitives such as mutual
   6 // exclusion locks. Other than the Once and WaitGroup types, most are intended
   7 // for use by low-level library routines. Higher-level synchronization is
   8 // better done via channels and communication.
   9 //
  10 // Values containing the types defined in this package should not be copied.
  11 package sync
  12
  13 import (
  14         "internal/race"
  15         "sync/atomic"
  16         "unsafe"
  17 )
  18
  19 func throw(string) // provided by runtime
  20
  21 // A Mutex is a mutual exclusion lock.
  22 // The zero value for a Mutex is an unlocked mutex.
  23 //
  24 // A Mutex must not be copied after first use.
  25 type Mutex struct {
  26         state int32
  27         sema  uint32
  28 }
  29
  30 // A Locker represents an object that can be locked and unlocked.
  31 type Locker interface {
  32         Lock()
  33         Unlock()
  34 }
  35
  36 const (
  37         mutexLocked = 1 << iota // mutex is locked
  38         mutexWoken
  39         mutexStarving
  40         mutexWaiterShift = iota
  41
  42         // Mutex fairness.
  43         //
  44         // Mutex can be in 2 modes of operations: normal and starvation.
  45         // In normal mode waiters are queued in FIFO order, but a woken up waiter
  46         // does not own the mutex and competes with new arriving goroutines over
  47         // the ownership. New arriving goroutines have an advantage -- they are
  48         // already running on CPU and there can be lots of them, so a woken up
  49         // waiter has good chances of losing. In such case it is queued at front
  50         // of the wait queue. If a waiter fails to acquire the mutex for more than 1ms,
  51         // it switches mutex to the starvation mode.
  52         //
  53         // In starvation mode ownership of the mutex is directly handed off from
  54         // the unlocking goroutine to the waiter at the front of the queue.
  55         // New arriving goroutines don't try to acquire the mutex even if it appears
  56         // to be unlocked, and don't try to spin. Instead they queue themselves at
  57         // the tail of the wait queue.
  58         //
  59         // If a waiter receives ownership of the mutex and sees that either
  60         // (1) it is the last waiter in the queue, or (2) it waited for less than 1 ms,
  61         // it switches mutex back to normal operation mode.
  62         //
  63         // Normal mode has considerably better performance as a goroutine can acquire
  64         // a mutex several times in a row even if there are blocked waiters.
  65         // Starvation mode is important to prevent pathological cases of tail latency.
  66         starvationThresholdNs = 1e6
  67 )
  68
  69 // Lock locks m.
  70 // If the lock is already in use, the calling goroutine
  71 // blocks until the mutex is available.
  72 func (m *Mutex) Lock() {
  73         // Fast path: grab unlocked mutex.
  74         if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
  75                 if race.Enabled {
  76                         race.Acquire(unsafe.Pointer(m))
  77                 }
  78                 return
  79         }
  80         // Slow path (outlined so that the fast path can be inlined)
  81         m.lockSlow()
  82 }
  83
  84 // TryLock tries to lock m and reports whether it succeeded.
  85 //
  86 // Note that while correct uses of TryLock do exist, they are rare,
  87 // and use of TryLock is often a sign of a deeper problem
  88 // in a particular use of mutexes.
  89 func (m *Mutex) TryLock() bool {
  90         old := m.state
  91         if old&(mutexLocked|mutexStarving) != 0 {
  92                 return false
  93         }
  94
  95         // There may be a goroutine waiting for the mutex, but we are
  96         // running now and can try to grab the mutex before that
  97         // goroutine wakes up.
  98         if !atomic.CompareAndSwapInt32(&m.state, old, old|mutexLocked) {
  99                 return false
 100         }
 101
 102         if race.Enabled {
 103                 race.Acquire(unsafe.Pointer(m))
 104         }
 105         return true
 106 }
 107
 108 func (m *Mutex) lockSlow() {
 109         var waitStartTime int64
 110         starving := false
 111         awoke := false
 112         iter := 0
 113         old := m.state
 114         for {
 115                 // Don't spin in starvation mode, ownership is handed off to waiters
 116                 // so we won't be able to acquire the mutex anyway.
 117                 if old&(mutexLocked|mutexStarving) == mutexLocked && runtime_canSpin(iter) {
 118                         // Active spinning makes sense.
 119                         // Try to set mutexWoken flag to inform Unlock
 120                         // to not wake other blocked goroutines.
 121                         if !awoke && old&mutexWoken == 0 && old>>mutexWaiterShift != 0 &&
 122                                 atomic.CompareAndSwapInt32(&m.state, old, old|mutexWoken) {
 123                                 awoke = true
 124                         }
 125                         runtime_doSpin()
 126                         iter++
 127                         old = m.state
 128                         continue
 129                 }
 130                 new := old
 131                 // Don't try to acquire starving mutex, new arriving goroutines must queue.
 132                 if old&mutexStarving == 0 {
 133                         new |= mutexLocked
 134                 }
 135                 if old&(mutexLocked|mutexStarving) != 0 {
 136                         new += 1 << mutexWaiterShift
 137                 }
 138                 // The current goroutine switches mutex to starvation mode.
 139                 // But if the mutex is currently unlocked, don't do the switch.
 140                 // Unlock expects that starving mutex has waiters, which will not
 141                 // be true in this case.
 142                 if starving && old&mutexLocked != 0 {
 143                         new |= mutexStarving
 144                 }
 145                 if awoke {
 146                         // The goroutine has been woken from sleep,
 147                         // so we need to reset the flag in either case.
 148                         if new&mutexWoken == 0 {
 149                                 throw("sync: inconsistent mutex state")
 150                         }
 151                         new &^= mutexWoken
 152                 }
 153                 if atomic.CompareAndSwapInt32(&m.state, old, new) {
 154                         if old&(mutexLocked|mutexStarving) == 0 {
 155                                 break // locked the mutex with CAS
 156                         }
 157                         // If we were already waiting before, queue at the front of the queue.
 158                         queueLifo := waitStartTime != 0
 159                         if waitStartTime == 0 {
 160                                 waitStartTime = runtime_nanotime()
 161                         }
 162                         runtime_SemacquireMutex(&m.sema, queueLifo, 1)
 163                         starving = starving || runtime_nanotime()-waitStartTime > starvationThresholdNs
 164                         old = m.state
 165                         if old&mutexStarving != 0 {
 166                                 // If this goroutine was woken and mutex is in starvation mode,
 167                                 // ownership was handed off to us but mutex is in somewhat
 168                                 // inconsistent state: mutexLocked is not set and we are still
 169                                 // accounted as waiter. Fix that.
 170                                 if old&(mutexLocked|mutexWoken) != 0 || old>>mutexWaiterShift == 0 {
 171                                         throw("sync: inconsistent mutex state")
 172                                 }
 173                                 delta := int32(mutexLocked - 1<<mutexWaiterShift)
 174                                 if !starving || old>>mutexWaiterShift == 1 {
 175                                         // Exit starvation mode.
 176                                         // Critical to do it here and consider wait time.
 177                                         // Starvation mode is so inefficient, that two goroutines
 178                                         // can go lock-step infinitely once they switch mutex
 179                                         // to starvation mode.
 180                                         delta -= mutexStarving
 181                                 }
 182                                 atomic.AddInt32(&m.state, delta)
 183                                 break
 184                         }
 185                         awoke = true
 186                         iter = 0
 187                 } else {
 188                         old = m.state
 189                 }
 190         }
 191
 192         if race.Enabled {
 193                 race.Acquire(unsafe.Pointer(m))
 194         }
 195 }
 196
 197 // Unlock unlocks m.
 198 // It is a run-time error if m is not locked on entry to Unlock.
 199 //
 200 // A locked Mutex is not associated with a particular goroutine.
 201 // It is allowed for one goroutine to lock a Mutex and then
 202 // arrange for another goroutine to unlock it.
 203 func (m *Mutex) Unlock() {
 204         if race.Enabled {
 205                 _ = m.state
 206                 race.Release(unsafe.Pointer(m))
 207         }
 208
 209         // Fast path: drop lock bit.
 210         new := atomic.AddInt32(&m.state, -mutexLocked)
 211         if new != 0 {
 212                 // Outlined slow path to allow inlining the fast path.
 213                 // To hide unlockSlow during tracing we skip one extra frame when tracing GoUnblock.
 214                 m.unlockSlow(new)
 215         }
 216 }
 217
 218 func (m *Mutex) unlockSlow(new int32) {
 219         if (new+mutexLocked)&mutexLocked == 0 {
 220                 throw("sync: unlock of unlocked mutex")
 221         }
 222         if new&mutexStarving == 0 {
 223                 old := new
 224                 for {
 225                         // If there are no waiters or a goroutine has already
 226                         // been woken or grabbed the lock, no need to wake anyone.
 227                         // In starvation mode ownership is directly handed off from unlocking
 228                         // goroutine to the next waiter. We are not part of this chain,
 229                         // since we did not observe mutexStarving when we unlocked the mutex above.
 230                         // So get off the way.
 231                         if old>>mutexWaiterShift == 0 || old&(mutexLocked|mutexWoken|mutexStarving) != 0 {
 232                                 return
 233                         }
 234                         // Grab the right to wake someone.
 235                         new = (old - 1<<mutexWaiterShift) | mutexWoken
 236                         if atomic.CompareAndSwapInt32(&m.state, old, new) {
 237                                 runtime_Semrelease(&m.sema, false, 1)
 238                                 return
 239                         }
 240                         old = m.state
 241                 }
 242         } else {
 243                 // Starving mode: handoff mutex ownership to the next waiter, and yield
 244                 // our time slice so that the next waiter can start to run immediately.
 245                 // Note: mutexLocked is not set, the waiter will set it after wakeup.
 246                 // But mutex is still considered locked if mutexStarving is set,
 247                 // so new coming goroutines won't acquire it.
 248                 runtime_Semrelease(&m.sema, true, 1)
 249         }
 250 }