libgo/go/sync/mutex.go - gofrontend - Git at Google

 // 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
 	}
 	// Slow path (outlined so that the fast path can be inlined)
 	m.lockSlow()
 }

 func (m *Mutex) lockSlow() {
 	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 {
 				throw("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, 1)
 			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 {
 					throw("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 != 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 {
 		throw("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, 1)
 				return
 			}
 			old = m.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(&m.sema, true, 1)
 	}
 }
	// 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
	}
	// Slow path (outlined so that the fast path can be inlined)
	m.lockSlow()
	}

	func (m *Mutex) lockSlow() {
	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 {
	throw("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, 1)
	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 {
	throw("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 != 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 {
	throw("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, 1)
	return
	}
	old = m.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(&m.sema, true, 1)
	}
	}