// 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 [Mutex.Unlock] “synchronizes before” the m'th call to [Mutex.Lock]
// for any n < m.
// A successful call to [Mutex.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()
}

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

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

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