// Copyright 2009 The Go Authors. All rights reserved.
// Use of this source code is governed by a BSD-style
// license that can be found in the LICENSE file.

// Package sync provides basic synchronization primitives such as mutual // exclusion locks. Other than the Once and WaitGroup types, most are intended // for use by low-level library routines. Higher-level synchronization is // better done via channels and communication. // // Values containing the types defined in this package should not be copied.
package sync import ( ) func throw(string) // provided by runtime // A Mutex is a mutual exclusion lock. // The zero value for a Mutex is an unlocked mutex. // // A Mutex must not be copied after first use. type Mutex struct { state int32 sema uint32 } // A Locker represents an object that can be locked and unlocked. type Locker interface { Lock() Unlock() } const ( mutexLocked = 1 << iota // mutex is locked mutexWoken mutexStarving mutexWaiterShift = iota // Mutex fairness. // // Mutex can be in 2 modes of operations: normal and starvation. // In normal mode waiters are queued in FIFO order, but a woken up waiter // does not own the mutex and competes with new arriving goroutines over // the ownership. New arriving goroutines have an advantage -- they are // already running on CPU and there can be lots of them, so a woken up // waiter has good chances of losing. In such case it is queued at front // of the wait queue. If a waiter fails to acquire the mutex for more than 1ms, // it switches mutex to the starvation mode. // // In starvation mode ownership of the mutex is directly handed off from // the unlocking goroutine to the waiter at the front of the queue. // New arriving goroutines don't try to acquire the mutex even if it appears // to be unlocked, and don't try to spin. Instead they queue themselves at // the tail of the wait queue. // // If a waiter receives ownership of the mutex and sees that either // (1) it is the last waiter in the queue, or (2) it waited for less than 1 ms, // it switches mutex back to normal operation mode. // // Normal mode has considerably better performance as a goroutine can acquire // a mutex several times in a row even if there are blocked waiters. // Starvation mode is important to prevent pathological cases of tail latency. starvationThresholdNs = 1e6 ) // Lock locks m. // If the lock is already in use, the calling goroutine // blocks until the mutex is available. func ( *Mutex) () { // Fast path: grab unlocked mutex. if atomic.CompareAndSwapInt32(&.state, 0, mutexLocked) { if race.Enabled { race.Acquire(unsafe.Pointer()) } return } // Slow path (outlined so that the fast path can be inlined) .lockSlow() } func ( *Mutex) () { var int64 := false := false := 0 := .state for { // Don't spin in starvation mode, ownership is handed off to waiters // so we won't be able to acquire the mutex anyway. if &(mutexLocked|mutexStarving) == mutexLocked && runtime_canSpin() { // Active spinning makes sense. // Try to set mutexWoken flag to inform Unlock // to not wake other blocked goroutines. if ! && &mutexWoken == 0 && >>mutexWaiterShift != 0 && atomic.CompareAndSwapInt32(&.state, , |mutexWoken) { = true } runtime_doSpin() ++ = .state continue } := // Don't try to acquire starving mutex, new arriving goroutines must queue. if &mutexStarving == 0 { |= mutexLocked } if &(mutexLocked|mutexStarving) != 0 { += 1 << mutexWaiterShift } // The current goroutine switches mutex to starvation mode. // But if the mutex is currently unlocked, don't do the switch. // Unlock expects that starving mutex has waiters, which will not // be true in this case. if && &mutexLocked != 0 { |= mutexStarving } if { // The goroutine has been woken from sleep, // so we need to reset the flag in either case. if &mutexWoken == 0 { throw("sync: inconsistent mutex state") } &^= mutexWoken } if atomic.CompareAndSwapInt32(&.state, , ) { if &(mutexLocked|mutexStarving) == 0 { break // locked the mutex with CAS } // If we were already waiting before, queue at the front of the queue. := != 0 if == 0 { = runtime_nanotime() } runtime_SemacquireMutex(&.sema, , 1) = || runtime_nanotime()- > starvationThresholdNs = .state if &mutexStarving != 0 { // If this goroutine was woken and mutex is in starvation mode, // ownership was handed off to us but mutex is in somewhat // inconsistent state: mutexLocked is not set and we are still // accounted as waiter. Fix that. if &(mutexLocked|mutexWoken) != 0 || >>mutexWaiterShift == 0 { throw("sync: inconsistent mutex state") } := int32(mutexLocked - 1<<mutexWaiterShift) if ! || >>mutexWaiterShift == 1 { // Exit starvation mode. // Critical to do it here and consider wait time. // Starvation mode is so inefficient, that two goroutines // can go lock-step infinitely once they switch mutex // to starvation mode. -= mutexStarving } atomic.AddInt32(&.state, ) break } = true = 0 } else { = .state } } if race.Enabled { race.Acquire(unsafe.Pointer()) } } // Unlock unlocks m. // It is a run-time error if m is not locked on entry to Unlock. // // A locked Mutex is not associated with a particular goroutine. // It is allowed for one goroutine to lock a Mutex and then // arrange for another goroutine to unlock it. func ( *Mutex) () { if race.Enabled { _ = .state race.Release(unsafe.Pointer()) } // Fast path: drop lock bit. := atomic.AddInt32(&.state, -mutexLocked) if != 0 { // Outlined slow path to allow inlining the fast path. // To hide unlockSlow during tracing we skip one extra frame when tracing GoUnblock. .unlockSlow() } } func ( *Mutex) ( int32) { if (+mutexLocked)&mutexLocked == 0 { throw("sync: unlock of unlocked mutex") } if &mutexStarving == 0 { := for { // If there are no waiters or a goroutine has already // been woken or grabbed the lock, no need to wake anyone. // In starvation mode ownership is directly handed off from unlocking // goroutine to the next waiter. We are not part of this chain, // since we did not observe mutexStarving when we unlocked the mutex above. // So get off the way. if >>mutexWaiterShift == 0 || &(mutexLocked|mutexWoken|mutexStarving) != 0 { return } // Grab the right to wake someone. = ( - 1<<mutexWaiterShift) | mutexWoken if atomic.CompareAndSwapInt32(&.state, , ) { runtime_Semrelease(&.sema, false, 1) return } = .state } } else { // Starving mode: handoff mutex ownership to the next waiter, and yield // our time slice so that the next waiter can start to run immediately. // Note: mutexLocked is not set, the waiter will set it after wakeup. // But mutex is still considered locked if mutexStarving is set, // so new coming goroutines won't acquire it. runtime_Semrelease(&.sema, true, 1) } }