...
Run Format

Source file src/sync/mutex.go

Documentation: sync

  // 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 (
  	"internal/race"
  	"sync/atomic"
  	"unsafe"
  )
  
  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 (m *Mutex) Lock() {
  	// Fast path: grab unlocked mutex.
  	if atomic.CompareAndSwapInt32(&m.state, 0, mutexLocked) {
  		if race.Enabled {
  			race.Acquire(unsafe.Pointer(m))
  		}
  		return
  	}
  
  	var waitStartTime int64
  	starving := false
  	awoke := false
  	iter := 0
  	old := m.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 old&(mutexLocked|mutexStarving) == mutexLocked && runtime_canSpin(iter) {
  			// Active spinning makes sense.
  			// Try to set mutexWoken flag to inform Unlock
  			// to not wake other blocked goroutines.
  			if !awoke && old&mutexWoken == 0 && old>>mutexWaiterShift != 0 &&
  				atomic.CompareAndSwapInt32(&m.state, old, old|mutexWoken) {
  				awoke = true
  			}
  			runtime_doSpin()
  			iter++
  			old = m.state
  			continue
  		}
  		new := old
  		// Don't try to acquire starving mutex, new arriving goroutines must queue.
  		if old&mutexStarving == 0 {
  			new |= mutexLocked
  		}
  		if old&(mutexLocked|mutexStarving) != 0 {
  			new += 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 starving && old&mutexLocked != 0 {
  			new |= mutexStarving
  		}
  		if awoke {
  			// The goroutine has been woken from sleep,
  			// so we need to reset the flag in either case.
  			if new&mutexWoken == 0 {
  				panic("sync: inconsistent mutex state")
  			}
  			new &^= mutexWoken
  		}
  		if atomic.CompareAndSwapInt32(&m.state, old, new) {
  			if old&(mutexLocked|mutexStarving) == 0 {
  				break // locked the mutex with CAS
  			}
  			// If we were already waiting before, queue at the front of the queue.
  			queueLifo := waitStartTime != 0
  			if waitStartTime == 0 {
  				waitStartTime = runtime_nanotime()
  			}
  			runtime_SemacquireMutex(&m.sema, queueLifo)
  			starving = starving || runtime_nanotime()-waitStartTime > starvationThresholdNs
  			old = m.state
  			if old&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 old&(mutexLocked|mutexWoken) != 0 || old>>mutexWaiterShift == 0 {
  					panic("sync: inconsistent mutex state")
  				}
  				delta := int32(mutexLocked - 1<<mutexWaiterShift)
  				if !starving || old>>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.
  					delta -= mutexStarving
  				}
  				atomic.AddInt32(&m.state, delta)
  				break
  			}
  			awoke = true
  			iter = 0
  		} else {
  			old = m.state
  		}
  	}
  
  	if race.Enabled {
  		race.Acquire(unsafe.Pointer(m))
  	}
  }
  
  // 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 (m *Mutex) Unlock() {
  	if race.Enabled {
  		_ = m.state
  		race.Release(unsafe.Pointer(m))
  	}
  
  	// Fast path: drop lock bit.
  	new := atomic.AddInt32(&m.state, -mutexLocked)
  	if (new+mutexLocked)&mutexLocked == 0 {
  		panic("sync: unlock of unlocked mutex")
  	}
  	if new&mutexStarving == 0 {
  		old := new
  		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 old>>mutexWaiterShift == 0 || old&(mutexLocked|mutexWoken|mutexStarving) != 0 {
  				return
  			}
  			// Grab the right to wake someone.
  			new = (old - 1<<mutexWaiterShift) | mutexWoken
  			if atomic.CompareAndSwapInt32(&m.state, old, new) {
  				runtime_Semrelease(&m.sema, false)
  				return
  			}
  			old = m.state
  		}
  	} else {
  		// Starving mode: handoff mutex ownership to the next waiter.
  		// 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(&m.sema, true)
  	}
  }
  

View as plain text