golang sync.Mutex interpretation

Golang sync.Mutex interpretation

The structure definition of Mutex is as follows:

type Mutex struct {<!-- -->
    state int32
    sema uint32
}

const (
    mutexLocked = 1 << iota // mutex is locked
    mutexWoken
    mutexStarving
    mutexWaiterShift = iota
    starvationThresholdNs = 1e6
)
  • mutexLocked: The value is 1, and the first bit is 1, indicating that mutex has been locked. The status of mutex is determined based on the result of mutex.state & amp; mutexLocked: if this bit is 1, it means it is locked, and if it is 0, it means it is not locked.
  • mutexWoken: Value is 2 (binary: 10), the second bit is 1, indicating whether mutex is awakened. Determine whether mutex is awakened based on the result of mutex.state & amp; mutexWoken: if this bit is 1, it means it has been awakened, and 0 means it has not been awakened.
  • mutexStarving: Value is 4 (binary: 100), the third bit is 1, indicating whether mutex is in starving mode. Determine whether mutex is in starvation mode based on the result of mutex.state & amp; mutexWoken: if this bit is 1, it means it is in starvation mode, and 0 means normal mode.
  • mutexWaiterShift: The value is 3, which means that mutex.state is shifted to the right by 3 bits, which is the number of waiting goroutine, which means that the statistics are blocked in The number of goroutines on this mutex that need to be shifted. Get the number of currently waiting goroutine according to mutex.state >> mutexWaiterShift
  • starvationThresholdNs: A value of 1000000 nanoseconds, or 1ms, indicating the waiting time threshold for switching mutex into starvation mode. This constant has a large comment in the source code. Understanding this comment is crucial to understanding the program logic.

state

1111 1111 ...... 1111 1 1 1 1
|_________29__________| ↓ ↓ ↓
          ↓ ↓ ↓ \ Indicates whether the current mutex is locked
          ↓ ↓ \ indicates whether the current mutex is awakened
          ↓ \ indicates whether the mutex is currently in a hungry state
          ↓
  Store the number of waiting goroutines

Hungry mode and normal mode

  • In normal mode, locks are acquired in FIFO (first come, first served) order. In this way, a newly awakened goroutine will compete with the newly requested lock and will most likely fail. At this time, it will be placed If the head of a waiting queue does not acquire the lock after waiting for 1ms, he will turn the lock into starvation mode.
  • In starvation mode, the lock will be transferred directly from the unlocked goroutine to the first one in the starvation queue, and sorting will start from the starvation queue.

If a waiting goroutine acquires the lock and meets any of the following conditions: (1) it is the last one in the waiting queue; (2) it waits for less than 1ms. It will convert the lock’s state to the normal state.

Compared to starvation mode, normal mode has better performance because a goroutine can obtain several mutexs in a row, even if there are blocked waiters. The starvation mode can effectively prevent the waiter at the end of the waiting queue from being able to obtain mutex.

Lock

1. Determine the status of Goroutine to see if it can perform spin and other locks; 

func (m *Mutex) Lock() {<!-- -->
    // Fast path: grab unlocked mutex.
    // Check whether state is 0. If so, it means locking is possible. Convert its state to 1. The current goroutine is locked successfully and the function returns
    if atomic.CompareAndSwapInt32( & amp;m.state, 0, mutexLocked) {<!-- -->
        if race.Enabled {<!-- -->
            race.Acquire(unsafe.Pointer(m))
        }
        return
    }
    // Slow path (outlined so that the fast path can be inlined)
    m.lockSlow()
}

Check to see if the lock is in an idle state. If so, just atomically modify state to indicate that it has been acquired. Just have a rough understanding and know that the method is atomic.

If not idle:

func (m *Mutex) lockSlow() {<!-- -->
    var waitStartTime int64 // Used to store the current goroutine waiting time
    starving := false // Used to store whether the current goroutine is hungry or not
    awoke := false // Used to store whether the current goroutine has been awakened
    iter := 0 // Used to store the number of loops of the current goroutine
    old := m.state //Copy the current lock state
for {<!-- -->
    // There are two types of role goroutines entering this cycle, one is the new goroutine. The other is the awakened goroutine;
    // So they may compete for the lock together in this place. If the new goroutine succeeds in grabbing it, the other one can only block and wait.
    // But after more than 1ms, the lock will switch to starvation mode. In this mode, all new goroutines must be queued at the back of the team and are not eligible to grab locks. That is:
    // If it is a starvation situation, do not spin, because the lock will be given directly to the goroutine at the head of the queue.
    // If the lock is acquired and meets the spin condition (canSpin, see later analysis), then spin and wait for the lock
    if old & amp;(mutexLocked|mutexStarving) == mutexLocked & amp; & amp; runtime_canSpin(iter) {<!-- -->
        // After passing the above test, it makes sense to spin at this time.
        // By marking mutexWoken as true, the Unlock method is informed not to wake up other blocked goroutines.
        if !awoke & amp; & amp; old & amp;mutexWoken == 0 & amp; & amp; old>>mutexWaiterShift != 0 & amp; & amp;
        atomic.CompareAndSwapInt32( & amp;m.state, old, old|mutexWoken) {<!-- -->
            awoke = true
        }
        // After marking the current goroutine as awake, perform a spin operation, add one to the counter, record the current state to old, and continue to wait in a loop
        runtime_doSpin()
        iter++
        old = m.state
        continue
    }
...

In general, it should be noted thatif it is in starvation mode, spin will not be performed, because the ownership of the lock will be directly given to the goroutine at the head of the queue, so in this starvation state, mutex cannot be obtained anyway .

What needs to be understood is that spin is a multi-thread synchronization mechanism. The current process will keep the CPU occupied during the spin process and continue to check whether a certain condition is true. On multi-core CPUs, spin can avoid Goroutine switching. Proper use will bring great performance gains, but improper use will slow down the entire program, so the conditions for Goroutine to enter spin are very strict:

Source code comments believe that because sync.Mutex is collaborative, we should use Spin more conservatively. The conditions for using Spin are quite strict. , see what conditions it needs to meet:

  1. The number of spins is less than active_spin (here 4) times;
  2. Then it should be run on a multi-core machine, and the number of GOMAXPROCS should be greater than 1; (If you don’t understand GOMAXPROCS, you can take a look at Goroutine Corresponding GMP model)
  3. There is also at least one running processor P on the current machine and the processing run queue is empty;

2. Wait for the release of the mutex lock through spin; 

//go:linkname sync_runtime_doSpin sync.runtime_doSpin
//go:nosplit
func sync_runtime_doSpin() {<!-- -->
procyield(active_spin_cnt)
}

3.Calculate the latest status of the mutex lock

If Goroutine cannot perform spin operation at this time, it will enter the remaining code logic; at this step, the state of the state may be:

  1. The lock has not been released and the lock is in a normal state;
  2. The lock has not been released and the lock is in a starved state;
  3. The lock has been released and the lock is in a normal state;
  4. The lock has been released and the lock is in a starved state;
// new copies the current state of state and is used to set the new state
// old is the current state of the lock
new := old

// If the old state is not hungry, the new state sets the lock and tries to obtain the lock through CAS.
// If the old state is hungry, the new state lock is not set, because in the hungry state the lock is directly transferred to the first person in the waiting queue.
if old &mutexStarving == 0 {<!-- -->
    // In non-starvation mode, you can grab the lock and set the first bit of new to 1, that is, lock it.
    new |= mutexLocked
}

// When the mutex is in the locked or hungry state, the newly arrived goroutine enters the waiting queue and increases the number of waiters in the waiting queue by 1.
// old & amp; 0101 != 0, then at least one of the first and third bits of old is 1, that is, the mutex is locked or in starvation mode.
if old & amp;(mutexLocked|mutexStarving) != 0 {<!-- -->
    new + = 1 << mutexWaiterShift
}

// If the current goroutine is already in a hungry state and the old state has been locked,
// Mark the state of new state as hungry state and transform the lock into hungry state.
// But if the current mutex is not locked, there is no need to switch. The Unlock operation hopes that there are waiters in starvation mode.
if starving & amp; & amp; old & amp;mutexLocked != 0 {<!-- -->
    new |= mutexStarving
}

// If the current goroutine is awakened, we need to reset this state.
// Because the goroutine either got the lock or entered sleep.
if awoke {<!-- -->
    // new is set to non-awakened state
    new & amp;^= mutexWoken
}
  • If it is in normal mode, lock it directly
  • If it has been locked｜｜It enters starvation mode, then put the current goroutine into the waiting queue
  • If it is already locked & & enters starvation mode, then set the new lock to enter starvation mode
  • If the current goroutine has been awakened, set it to a non-awakened state

3.Try to set the status of the mutex through CAS

// Call CAS to update the state
if atomic.CompareAndSwapInt32( & amp;m.state, old, new) {<!-- -->
    // If the old state is not a hungry state or an acquired state
    // Then it means that the current goroutine has successfully acquired the lock through CAS
    // (Being able to enter this code block means that the state has changed, that is to say, the state is from idle to acquired)
    if old & amp;(mutexLocked|mutexStarving) == 0 {<!-- -->
        // Locked successfully
        break // locked the mutex with CAS
    }
    // If it has been waited for before, then it should be placed at the head of the queue.
    queueLifo := waitStartTime != 0
    // If you have not waited before, initialize and set the current waiting time.
    if waitStartTime == 0 {<!-- -->
        waitStartTime = runtime_nanotime()
    }
    // Since acquiring the lock failed, use the sleep primitive to block the current goroutine
    // Queue the lock through the semaphore
    // If it is a new goroutine, put it at the end of the queue
    // If it is a goroutine that is awakened and waiting for a lock, put it at the head of the queue.
    runtime_SemacquireMutex( & amp;m.sema, queueLifo, 1)
    
    // End of sleep here, wake up

    // If the current goroutine waiting time exceeds starvationThresholdNs, mutex enters starvation mode
    starving = starving || runtime_nanotime()-waitStartTime > starvationThresholdNs
    
    // Get the current status of the lock again
    old = m.state
    // If the lock is now in a hungry state, it means that the lock is now released, and the current goroutine is awakened by the semaphore.
    // In other words, the lock is directly handed over to the current goroutine
    if old & amp;mutexStarving != 0 {<!-- -->
        // If the current lock status is awakened or acquired, or the waiting queue is empty
        // Then the state is an illegal state, because the current state must have a waiting queue, and the lock must be released and not awakened.
        if old & amp;(mutexLocked|mutexWoken) != 0 || old>>mutexWaiterShift == 0 {<!-- -->
            throw("sync: inconsistent mutex state")
        }
        //The current goroutine has obtained the lock, then set the waiting queue to -1
        delta := int32(mutexLocked - 1<<mutexWaiterShift)
        // If it is not starvation mode or there is only one waiter left, exit starvation mode
        if !starving || old>>mutexWaiterShift == 1 {<!-- -->
            // Set status to normal
            delta -= mutexStarving
        }
        // Set new state, because the lock has been obtained, exit and return
        atomic.AddInt32(&m.state, delta)
        break
    }
    // If the lock is not in starvation mode, set the current goroutine to be awakened and reset iter (reset spin)
    awoke = true
    iter = 0
} else {<!-- -->
    // If CAS is unsuccessful, reacquire the lock state and start again from the beginning of the for loop
    old = m.state
}

Summary of the locking process

  1. First, it checks whether the status of the mutex m.state is 0, that is, whether it is not locked. If it is, it means that you can try to lock, using the atomic.CompareAndSwapInt32 atomic operation to try to convert the state from 0 to mutexLocked (1). If this step is successful, it means that the current goroutine has successfully obtained the lock and can return immediately.
  2. If the above fast path fails, that is, the status of the mutex lock is not 0, or the CAS operation fails, the slow path will be entered and the m.lockSlow() method will be called to further try to obtain the lock.
  3. The main part of the m.lockSlow() method is a for loop, which is used to handle various states and competition conditions of the mutex lock.
  4. First, it checks the state of the lock m.state and attempts to spin waiting for the lock if the lock is acquired or in a starved state. This is to avoid unnecessary waits and system calls.
  5. If the spin wait condition is met and no other waiting goroutine has been awakened before, the current goroutine will set the mutexWoken flag to true to notify Unlock Methods do not wake up other waiting goroutines. Then, it will perform a spin operation and continue trying to acquire the lock.
  6. If the spin operation fails, it updates the iteration counter iter, copies the current lock state to old, and then loops again to try. This iteration counter helps limit the number of spin waits.
  7. If the above conditions are not met, it will calculate the new state new, there are four types, try to update the state through CAS
  8. If it has been waited before, put the current goroutine into the head of the waiting queue (LIFO), otherwise initialize the starting time of waiting.
  9. Use the system call (sleep) to block the current goroutine and queue up to wait to acquire the lock through the semaphore. Newly arrived goroutines are placed at the tail of the queue, and awakened goroutines waiting for locks are placed at the head of the queue.
  10. If the waiting time exceeds starvationThresholdNs, the lock enters starvation mode and newly arrived goroutines no longer have a chance to compete for the lock.
  11. If the current goroutine is awakened, try to acquire the lock again and check the lock status. If it is in starvation mode, directly hand the lock to the head of the queue. If the current goroutine obtains the lock, then set the waiting queue to -1 and set a new state.
  12. If the CAS operation is unsuccessful, reacquire the current lock status and start the cycle again

Unlock

The process will first use the AddInt32 function to quickly unlock. At this time, the following two situations will occur:

  • If the new state returned by this function is equal to 0, the current Goroutine has successfully unlocked the mutex;
  • If the new status returned by this function is not equal to 0, this code will call the sync.Mutex.unlockSlow method to start slow unlocking:

The source code fragment is as follows:

func (m *Mutex) Unlock() {<!-- -->
    if race.Enabled {<!-- -->
        _ = m.state
        race.Release(unsafe.Pointer(m))
    }

//The state of mutex is subtracted by 1, locked state -> not locked, and saved to new
    new := atomic.AddInt32( & amp;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 the state is not in the locked state, then Unlock has no locked mutex at all, panic
    if (new + mutexLocked) & amp;mutexLocked == 0 {<!-- -->
        throw("sync: unlock of unlocked mutex")
    }
    // Non-starvation mode, also known as normal mode
    if new &mutexStarving == 0 {<!-- -->
        old := new
        for {<!-- -->
            // There are no blocked goroutines. Return directly
            // There is a blocking goroutine, but it is in waken mode and returns directly
            // There is a blocked goroutine, but it is locked. This may happen in this for loop and the first CAS is unsuccessful. Because the lock may be grabbed by a new goroutine before CAS. Return directly
            // There is a blocked goroutine, but the lock is in starvation mode. This may occur when the blocked goroutine is not scheduled to be awakened, but is scheduled to run normally. Return directly
            if old>>mutexWaiterShift == 0 || old & amp;(mutexLocked|mutexWoken|mutexStarving) != 0 {<!-- -->
                return
            }
            // Decrement the number of waiters by 1 and change the wake-up bit to 1
            new = (old - 1<<mutexWaiterShift) | mutexWoken
            //Set a new state, where a blocked goroutine will be awakened through the semaphore to acquire the lock.
            if atomic.CompareAndSwapInt32( & amp;m.state, old, new) {<!-- -->
                // Wake up a blocking goroutine, but not the first waiter
                runtime_Semrelease(&m.sema, false, 1)
                return
            }
            old = m.state
        }
    } else {<!-- -->
        // Starvation mode: Pass mutex ownership to the next waiter.
        // Note: mutexLocked is not set, the waiter will set it after waking up.
        // During this period, if a new goroutine requests the lock, because the mutex is in a hungry state, the mutex is still considered to be in the lock state.
        // The new goroutine will not grab the lock.
        runtime_Semrelease(&m.sema, true, 1)
    }
}

Unlock summary

  • When the mutex lock has been unlocked, calling sync.Mutex.Unlock will directly throw an exception;
  • When the mutex lock is in starvation mode, the ownership of the lock will be directly handed over to the next waiter in the queue. The waiter will be responsible for setting the mutexLocked flag, and the goroutine in the waiting queue will be responsible for the mutex. The unlocking operation of the lock. In this way, the unlocking operation of the mutex does not require an explicit executor (unlocker), because the next waiter in the waiting queue will be responsible for releasing the lock state.
  • When the mutex is in normal mode, if there is no Goroutine waiting for the lock to be released or an awakened Goroutine has obtained the lock, it will return directly; in other cases, the state will be updated through csa, and then sync.runtime_Semrelease Wake up the corresponding Goroutine;

Reference

https://dongxiem.github.io/2020/06/05/golang-sync-bao-yuan-ma-pou-xi-1-sync.mutex/