// 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 (
	
	
	
)

// Provided by runtime via linkname.
func (string)
func (string)

// 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.
//
// In the terminology of the Go memory model,
// the n'th call to Unlock “synchronizes before” the m'th call to Lock
// for any n < m.
// A successful call to TryLock is equivalent to a call to Lock.
// A failed call to TryLock does not establish any “synchronizes before”
// relation at all.
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()
}

// TryLock tries to lock m and reports whether it succeeded.
//
// Note that while correct uses of TryLock do exist, they are rare,
// and use of TryLock is often a sign of a deeper problem
// in a particular use of mutexes.
func ( *Mutex) () bool {
	 := .state
	if &(mutexLocked|mutexStarving) != 0 {
		return false
	}

	// There may be a goroutine waiting for the mutex, but we are
	// running now and can try to grab the mutex before that
	// goroutine wakes up.
	if !atomic.CompareAndSwapInt32(&.state, , |mutexLocked) {
		return false
	}

	if race.Enabled {
		race.Acquire(unsafe.Pointer())
	}
	return true
}

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 {
		fatal("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)
	}
}