Decrypt Go: sync.Mutex
Understand the sync.mutex from source code
Background
sync.Mutex is a lock that we commonly use. Many articles about this lock online, but I will summarize them here for personal reference.
The slow path of Sync.Mutex relies on runtime_SemacquireMutex and runtime_Semrelease. If you are unfamiliar with them, you can first read about runtime.semaphore
Sync.Mutex source code
Development History
The initial version of sync.Mutex code was submitted by @rsc in 2008. The early implementation was relatively simple, using a combination of CAS (Compare-And-Swap) and semaphores. You can refer to the article runtime-sema for more details.
In 2011, @dvyukov submitted the first optimization sync: improve Mutex to allow successive acquisitions, which introduced the concepts of mutexWoken (wakeup status) and waiter count.
In 2015, @dvyukov made the second optimization sync: add active spinning to Mutex, which mainly added spinning logic.
In 2016, @dvyukov made the third optimization sync: make Mutex more fair, which introduced the concept of starvation mode to make the lock more fair.
Mutex Structure Analysis
Let's first look at the comment of Mutex:
// 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.Now, let's take a look at the Mutex structure:
type Mutex struct {
state int32
sema uint32
}
const (
mutexLocked = 1 << iota // Indicates whether the mutex is locked: 1 for locked, 0 for unlocked
mutexWoken // Indicates whether it is in wakeup status: 1 for woken up
mutexStarving // Indicates whether it is in starvation mode: 1 for starving
mutexWaiterShift = iota // Shifts the state to represent the number of waiters
starvationThresholdNs = 1e6 // If the wait time exceeds this value, it switches to starvation mode
)The sema field is relatively simple; it is the parameter required for runtime_SemacquireMutex and runtime_Semrelease calls. The state field represents different meanings based on different bits, as shown in the following diagram:
Lock
// If the mutex is already locked, this will block the current goroutine until the mutex is available.
func (m *Mutex) Lock() {
// Fast path: Try CAS to change the state from 0 to locked.
if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
if race.Enabled {
race.Acquire(unsafe.Pointer(m))
}
return
}
// Slow path
m.lockSlow()
}
func (m *Mutex) lockSlow() {
var waitStartTime int64
starving := false
awoke := false
iter := 0
old := m.state
for {
// old&(mutexLocked|mutexStarving) preserves the data on the Locked and Starving bits and clears the rest.
// old&(mutexLocked|mutexStarving) == mutexLocked indicates a locked state without starvation.
// runtime_canSpin checks if spinning is possible and performs the following checks:
// 1. Spin count < 4
// 2. Must be a multicore CPU with GOMAXPROCS > 1
// 3. P and the local run queue are empty.
if old&(mutexLocked|mutexStarving) == mutexLocked && runtime_canSpin(iter) {
// If the "woken" flag is 0 and there are other goroutines waiting,
// try to set the "woken" flag to 1 through CAS.
// This tells other goroutines that we are currently spinning to acquire the lock.
if !awoke && old&mutexWoken == 0 && old>>mutexWaiterShift != 0 &&
atomic.CompareAndSwapInt32(&m.state, old, old|mutexWoken) {
awoke = true
}
runtime_doSpin()
iter++
old = m.state // Read the new value of m.state, which may have been changed by other goroutines.
continue // Retry spinning if the setting fails
}
new := old
if old&mutexStarving == 0 {
// If it is not in starvation mode, try to lock it.
// If it is in starvation mode, no need to set it again. The waiter count will be increased, and it will obediently wait in line.
new |= mutexLocked
}
// If mutexLocked or mutexStarving = 1
// Increase the waiter count.
if old&(mutexLocked|mutexStarving) != 0 {
new += 1 << mutexWaiterShift
}
// If it is currently mutexLocked = 1 (locked state)
// and starving = true (waiting time exceeds 1ms)
// Set mutexStarving to 1.
// If it is not in a locked state, we don't need to set it to starvation mode. It might succeed in the following CAS operation.
if starving && old&mutexLocked != 0 {
new |= mutexStarving
}
if awoke {
// If it has already been set to wakeup status, clear the wakeup flag, as we will either acquire the lock or go to sleep.
if new&mutexWoken == 0 {
throw("sync: inconsistent mutex state")
}
new &^= mutexWoken
}
// CAS update the state
if atomic.CompareAndSwapInt32(&m.state, old, new) {
if old&(mutexLocked|mutexStarving) == 0 {
// If the previous state was not locked or starving, it means we have successfully acquired the lock.
// Return directly.
break // Locked the mutex with CAS
}
// If it reaches here, it means the previous state might be locked or in starvation mode.
// Regardless of whether it is locked or in starvation mode, we need to call the semaphore to wait in line.
// If waitStartTime != 0, it means that this goroutine was awakened after sleep, and queueLifo = true.
// If queueLifo = true, it will be placed at the head of the semTable suodg queue.
// You can refer to this [article](https://fanlv.fun/2022/10/06/runtime-sema/) for more information about semaphores.
// If there are no available semaphores, it will block at this line. It actually calls gopark to put this goroutine to sleep.
runtime_SemacquireMutex(&m.sema, queueLifo, 1)
// This line means that someone has released the lock/semaphore, and this goroutine has been awakened.
// Although we are awakened at the head of the queue, if there is a new Lock call in the business code at this time,
// our awakened goroutine will compete for the lock in the new Lock scenario.
// If the wait time exceeds 1ms, set starving = true.
starving = starving || runtime_nanotime()-waitStartTime > starvationThresholdNs
old = m.state // Read the latest state. We don't know what it has been changed to.
if old&mutexStarving != 0 {
// If it is currently in starvation mode, we don't need to compete for the lock anymore; it will be given to us by default.
if old&(mutexLocked|mutexWoken) != 0 || old>>mutexWaiterShift == 0 {
// It is impossible to have (mutexWoken=0 && mutexLocked==0) in starvation mode.
// mutexWaiter cannot be 0 either because it will exit starvation mode when mutexWaiter = 1.
throw("sync: inconsistent mutex state")
}
// The following bit operation changes three flag states with one AddInt32, which is complicated and hard to understand.
// Set the first bit to 1 and decrease waiter by 1.
// mutexLocked = 1, mutexWaiterShift = 3, delta = -7
// The third bit of delta is 11111 0 0 1.
delta := int32(mutexLocked - 1<<mutexWaiterShift)
if !starving || old>>mutexWaiterShift == 1 {
// If there is no more waiting, it should exit.
delta -= mutexStarving
}
// Modify the state.
atomic.AddInt32(&m.state, delta)
break
}
awoke = true
iter = 0
} else {
// atomic.CompareAndSwapInt32(&m.state, old, new)
// If CAS fails, read the current state again and loop again.
old = m.state
}
}
if race.Enabled {
race.Acquire(unsafe.Pointer(m))
}
}unlock
func (m *Mutex) Unlock() {
if race.Enabled {
_ = m.state
race.Release(unsafe.Pointer(m))
}
// Fast path: CAS cancels the lock if it is unlocked, 0 means no other lock waiters
// If unsuccessful, enter the slow path
new := atomic.AddInt32(&m.state, -mutexLocked)
if new != 0 {
// Outlined slow path to allow inlining the fast path.
// To hide unlockSlow during tracing we skip one extra frame when tracing GoUnblock.
m.unlockSlow(new)
}
}
func (m *Mutex) unlockSlow(new int32) {
if (new+mutexLocked)&mutexLocked == 0 {
// new = m.state-mutexLocked
// m.state&mutexLocked == 0 indicates an unlocked state.
// If it's unlocked, the fast path above succeeded.
// So theoretically, this case should not occur.
fatal("sync: unlock of unlocked mutex")
}
if new&mutexStarving == 0 { // Not in a starving state
old := new
for {
// If there are no waiters for the lock, or if any of the following conditions have already occurred,
// the subsequent work is unnecessary, so return directly:
// 1. The lock is in a locked state, indicating that it has been acquired by another goroutine.
// 2. The lock is in a woken state, indicating that a waiting goroutine has been woken up, so there's no need to try waking up other goroutines.
// 3. The lock is in a starving mode, in which case the lock will be directly handed over to the goroutine at the head of the waiting queue.
if old>>mutexWaiterShift == 0 || old&(mutexLocked|mutexWoken|mutexStarving) != 0 {
return
}
// If the lock is currently idle and there are waiters in the queue, and no goroutines have been woken up,
// decrement the waiter count by 1 and set the woken state to 1.
new = (old - 1<<mutexWaiterShift) | mutexWoken
if atomic.CompareAndSwapInt32(&m.state, old, new) { // If successful in setting the state
runtime_Semrelease(&m.sema, false, 1) // Wake up one semaphore
return
}
old = m.state // Check the latest state again
}
} else {
// In the starving mode, wake up the head of the semaphore's waiting queue.
// Goroutines coming from the starving state will be placed at the end of the semaphore queue.
runtime_Semrelease(&m.sema, true, 1)
}
}An optimization is made in the starving mode, where readyWithTime is called to put the head goroutine of the queue into pp.runnext. Then goyield is called to put the current goroutine into the tail of the p runnable queue. Finally, the schedule function is called, allowing the execution of goroutines in the waiting queue to be prioritized.
For more details, please refer to this CR: sync: yield to the waiter when unlocking a starving mutex
Summary
To understand Sync.Mutex, it is important to first understand runtime.semaphore, and then comprehend the normal and starving modes based on the comments.
Designing a bug-free and high-performance lock is challenging without a certain level of technical depth. Understanding is one thing, but there is still a long way to go before implementing a lock oneself.
If you found my article enjoyable, feel free to follow me and give it a 👏. Your support would be greatly appreciated.
